17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
22*badf94ffSPatrick Mooney /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
23*badf94ffSPatrick Mooney /* All Rights Reserved */
247c478bd9Sstevel@tonic-gate
257c478bd9Sstevel@tonic-gate
267c478bd9Sstevel@tonic-gate /*
277c478bd9Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
287c478bd9Sstevel@tonic-gate * Use is subject to license terms.
29*badf94ffSPatrick Mooney * Copyright 2022 Oxide Computer Company
307c478bd9Sstevel@tonic-gate */
317c478bd9Sstevel@tonic-gate
327c478bd9Sstevel@tonic-gate /*
337c478bd9Sstevel@tonic-gate * Operations on bitmaps of arbitrary size
347c478bd9Sstevel@tonic-gate * A bitmap is a vector of 1 or more ulongs.
357c478bd9Sstevel@tonic-gate * The user of the package is responsible for range checks and keeping
367c478bd9Sstevel@tonic-gate * track of sizes.
377c478bd9Sstevel@tonic-gate */
387c478bd9Sstevel@tonic-gate
397c478bd9Sstevel@tonic-gate #include <sys/types.h>
407c478bd9Sstevel@tonic-gate #include <sys/bitmap.h>
41*badf94ffSPatrick Mooney #include <sys/debug.h>
427c478bd9Sstevel@tonic-gate
437c478bd9Sstevel@tonic-gate /*
447c478bd9Sstevel@tonic-gate * Return index of first available bit in denoted bitmap, or -1 for
457c478bd9Sstevel@tonic-gate * failure. Size is the cardinality of the bitmap; that is, the
467c478bd9Sstevel@tonic-gate * number of bits.
477c478bd9Sstevel@tonic-gate * No side-effects. In particular, does not update bitmap.
487c478bd9Sstevel@tonic-gate * Caller is responsible for range checks.
497c478bd9Sstevel@tonic-gate */
507c478bd9Sstevel@tonic-gate index_t
bt_availbit(const ulong_t * bitmap,size_t nbits)51*badf94ffSPatrick Mooney bt_availbit(const ulong_t *bitmap, size_t nbits)
527c478bd9Sstevel@tonic-gate {
537c478bd9Sstevel@tonic-gate index_t maxword; /* index of last in map */
547c478bd9Sstevel@tonic-gate index_t wx; /* word index in map */
557c478bd9Sstevel@tonic-gate
567c478bd9Sstevel@tonic-gate /*
577c478bd9Sstevel@tonic-gate * Look for a word with a bit off.
587c478bd9Sstevel@tonic-gate * Subtract one from nbits because we're converting it to a
597c478bd9Sstevel@tonic-gate * a range of indices.
607c478bd9Sstevel@tonic-gate */
617c478bd9Sstevel@tonic-gate nbits -= 1;
627c478bd9Sstevel@tonic-gate maxword = nbits >> BT_ULSHIFT;
637c478bd9Sstevel@tonic-gate for (wx = 0; wx <= maxword; wx++)
647c478bd9Sstevel@tonic-gate if (bitmap[wx] != ~0)
657c478bd9Sstevel@tonic-gate break;
667c478bd9Sstevel@tonic-gate
677c478bd9Sstevel@tonic-gate if (wx <= maxword) {
687c478bd9Sstevel@tonic-gate /*
697c478bd9Sstevel@tonic-gate * Found a word with a bit off. Now find the bit in the word.
707c478bd9Sstevel@tonic-gate */
717c478bd9Sstevel@tonic-gate index_t bx; /* bit index in word */
727c478bd9Sstevel@tonic-gate index_t maxbit; /* last bit to look at */
737c478bd9Sstevel@tonic-gate ulong_t word;
747c478bd9Sstevel@tonic-gate ulong_t bit;
757c478bd9Sstevel@tonic-gate
767c478bd9Sstevel@tonic-gate maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1;
777c478bd9Sstevel@tonic-gate word = bitmap[wx];
787c478bd9Sstevel@tonic-gate bit = 1;
797c478bd9Sstevel@tonic-gate for (bx = 0; bx <= maxbit; bx++, bit <<= 1) {
807c478bd9Sstevel@tonic-gate if (!(word & bit)) {
817c478bd9Sstevel@tonic-gate return (wx << BT_ULSHIFT | bx);
827c478bd9Sstevel@tonic-gate }
837c478bd9Sstevel@tonic-gate }
847c478bd9Sstevel@tonic-gate }
857c478bd9Sstevel@tonic-gate return (-1);
867c478bd9Sstevel@tonic-gate }
877c478bd9Sstevel@tonic-gate
887c478bd9Sstevel@tonic-gate
897c478bd9Sstevel@tonic-gate /*
907c478bd9Sstevel@tonic-gate * Find highest order bit that is on, and is within or below
917c478bd9Sstevel@tonic-gate * the word specified by wx.
927c478bd9Sstevel@tonic-gate */
937c478bd9Sstevel@tonic-gate int
bt_gethighbit(const ulong_t * mapp,int wx)94*badf94ffSPatrick Mooney bt_gethighbit(const ulong_t *mapp, int wx)
957c478bd9Sstevel@tonic-gate {
967c478bd9Sstevel@tonic-gate ulong_t word;
977c478bd9Sstevel@tonic-gate
987c478bd9Sstevel@tonic-gate while ((word = mapp[wx]) == 0) {
997c478bd9Sstevel@tonic-gate wx--;
1007c478bd9Sstevel@tonic-gate if (wx < 0) {
1017c478bd9Sstevel@tonic-gate return (-1);
1027c478bd9Sstevel@tonic-gate }
1037c478bd9Sstevel@tonic-gate }
1047c478bd9Sstevel@tonic-gate return (wx << BT_ULSHIFT | (highbit(word) - 1));
1057c478bd9Sstevel@tonic-gate }
1067c478bd9Sstevel@tonic-gate
1077c478bd9Sstevel@tonic-gate
1087c478bd9Sstevel@tonic-gate /*
1097c478bd9Sstevel@tonic-gate * Search the bitmap for a consecutive pattern of 1's.
1107c478bd9Sstevel@tonic-gate * Search starts at position pos1.
1117c478bd9Sstevel@tonic-gate * Returns 1 on success and 0 on failure.
1127c478bd9Sstevel@tonic-gate * Side effects.
1137c478bd9Sstevel@tonic-gate * Returns indices to the first bit (pos1)
1147c478bd9Sstevel@tonic-gate * and one past the last bit (pos2) in the pattern.
1157c478bd9Sstevel@tonic-gate */
1167c478bd9Sstevel@tonic-gate int
bt_range(const ulong_t * bitmap,size_t * pos1,size_t * pos2,size_t end_pos)117*badf94ffSPatrick Mooney bt_range(const ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos)
1187c478bd9Sstevel@tonic-gate {
1197c478bd9Sstevel@tonic-gate size_t pos;
1207c478bd9Sstevel@tonic-gate
1217c478bd9Sstevel@tonic-gate for (pos = *pos1; pos < end_pos; pos++)
1227c478bd9Sstevel@tonic-gate if (BT_TEST(bitmap, pos))
1237c478bd9Sstevel@tonic-gate break;
1247c478bd9Sstevel@tonic-gate
1257c478bd9Sstevel@tonic-gate if (pos == end_pos)
1267c478bd9Sstevel@tonic-gate return (0);
1277c478bd9Sstevel@tonic-gate
1287c478bd9Sstevel@tonic-gate *pos1 = pos;
1297c478bd9Sstevel@tonic-gate
1307c478bd9Sstevel@tonic-gate for (; pos < end_pos; pos++)
1317c478bd9Sstevel@tonic-gate if (!BT_TEST(bitmap, pos))
1327c478bd9Sstevel@tonic-gate break;
1337c478bd9Sstevel@tonic-gate *pos2 = pos;
1347c478bd9Sstevel@tonic-gate
1357c478bd9Sstevel@tonic-gate return (1);
1367c478bd9Sstevel@tonic-gate }
1377c478bd9Sstevel@tonic-gate
1387c478bd9Sstevel@tonic-gate
1397c478bd9Sstevel@tonic-gate /*
1407c478bd9Sstevel@tonic-gate * return the parity of the supplied long
1417c478bd9Sstevel@tonic-gate *
1427c478bd9Sstevel@tonic-gate * this works by successively partitioning the argument in half, and
1437c478bd9Sstevel@tonic-gate * setting the parity of the result to the parity of the 2 halfs, until
1447c478bd9Sstevel@tonic-gate * only one bit is left
1457c478bd9Sstevel@tonic-gate */
1467c478bd9Sstevel@tonic-gate int
odd_parity(ulong_t i)1477c478bd9Sstevel@tonic-gate odd_parity(ulong_t i)
1487c478bd9Sstevel@tonic-gate {
1497c478bd9Sstevel@tonic-gate #ifdef _LP64
1507c478bd9Sstevel@tonic-gate i ^= i >> 32;
1517c478bd9Sstevel@tonic-gate #endif
1527c478bd9Sstevel@tonic-gate i ^= i >> 16;
1537c478bd9Sstevel@tonic-gate i ^= i >> 8;
1547c478bd9Sstevel@tonic-gate i ^= i >> 4;
1557c478bd9Sstevel@tonic-gate i ^= i >> 2;
1567c478bd9Sstevel@tonic-gate i ^= i >> 1;
1577c478bd9Sstevel@tonic-gate
1587c478bd9Sstevel@tonic-gate return (i & 0x01);
1597c478bd9Sstevel@tonic-gate }
1607c478bd9Sstevel@tonic-gate
1617c478bd9Sstevel@tonic-gate
1627c478bd9Sstevel@tonic-gate /*
1637c478bd9Sstevel@tonic-gate * get the lowest bit in the range of 'start' and 'stop', inclusive.
1647c478bd9Sstevel@tonic-gate * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y,
1657c478bd9Sstevel@tonic-gate * including X and Y can be returned.
1667c478bd9Sstevel@tonic-gate * Neither start nor stop is required to align with word boundaries.
1677c478bd9Sstevel@tonic-gate * If a bit is set in the range, the bit position is returned; otherwise,
1687c478bd9Sstevel@tonic-gate * a -1 is returned.
1697c478bd9Sstevel@tonic-gate */
1707c478bd9Sstevel@tonic-gate int
bt_getlowbit(const ulong_t * map,size_t start,size_t stop)171*badf94ffSPatrick Mooney bt_getlowbit(const ulong_t *map, size_t start, size_t stop)
1727c478bd9Sstevel@tonic-gate {
1737c478bd9Sstevel@tonic-gate ulong_t word;
1747c478bd9Sstevel@tonic-gate int counter = start >> BT_ULSHIFT;
1757c478bd9Sstevel@tonic-gate int limit = stop >> BT_ULSHIFT;
1767c478bd9Sstevel@tonic-gate index_t partial_start = start & BT_ULMASK;
1777c478bd9Sstevel@tonic-gate index_t partial_stop = stop & BT_ULMASK;
1787c478bd9Sstevel@tonic-gate
1797c478bd9Sstevel@tonic-gate if (start > stop) {
1807c478bd9Sstevel@tonic-gate return (-1);
1817c478bd9Sstevel@tonic-gate }
1827c478bd9Sstevel@tonic-gate
1837c478bd9Sstevel@tonic-gate /*
1847c478bd9Sstevel@tonic-gate * The range between 'start' and 'stop' can be very large, and the
1857c478bd9Sstevel@tonic-gate * '1' bits in this range can be sparse.
1867c478bd9Sstevel@tonic-gate * For performance reason, the underlying implementation operates
1877c478bd9Sstevel@tonic-gate * on words, not on bits.
1887c478bd9Sstevel@tonic-gate */
1897c478bd9Sstevel@tonic-gate word = map[counter];
1907c478bd9Sstevel@tonic-gate
1917c478bd9Sstevel@tonic-gate if (partial_start) {
1927c478bd9Sstevel@tonic-gate /*
1937c478bd9Sstevel@tonic-gate * Since the start is not aligned on word boundary, we
1947c478bd9Sstevel@tonic-gate * need to patch the unwanted low order bits with 0's before
1957c478bd9Sstevel@tonic-gate * operating on the first bitmap word.
1967c478bd9Sstevel@tonic-gate */
1977c478bd9Sstevel@tonic-gate word = word & (BT_ULMAXMASK << partial_start);
1987c478bd9Sstevel@tonic-gate }
1997c478bd9Sstevel@tonic-gate
2007c478bd9Sstevel@tonic-gate /*
2017c478bd9Sstevel@tonic-gate * Locate a word from the map array with one of the bits set.
2027c478bd9Sstevel@tonic-gate */
2037c478bd9Sstevel@tonic-gate
2047c478bd9Sstevel@tonic-gate while ((word == 0) && (counter < limit)) {
2057c478bd9Sstevel@tonic-gate word = map[++counter];
2067c478bd9Sstevel@tonic-gate }
2077c478bd9Sstevel@tonic-gate
2087c478bd9Sstevel@tonic-gate /*
2097c478bd9Sstevel@tonic-gate * The end of range has similar problems if it is not aligned.
2107c478bd9Sstevel@tonic-gate * Taking care of the end which is not aligned.
2117c478bd9Sstevel@tonic-gate */
2127c478bd9Sstevel@tonic-gate
2137c478bd9Sstevel@tonic-gate if ((counter == limit) && (partial_stop != BT_ULMASK)) {
2147c478bd9Sstevel@tonic-gate /*
2157c478bd9Sstevel@tonic-gate * Take care the partial word by patch the high order
2167c478bd9Sstevel@tonic-gate * bits with 0's. Here we dealing with the case that
2177c478bd9Sstevel@tonic-gate * the last word of the bitmap is not aligned.
2187c478bd9Sstevel@tonic-gate */
2197c478bd9Sstevel@tonic-gate
2207c478bd9Sstevel@tonic-gate ASSERT(partial_stop < BT_ULMASK);
2217c478bd9Sstevel@tonic-gate word = word & (~(BT_ULMAXMASK << partial_stop + 1));
2227c478bd9Sstevel@tonic-gate }
2237c478bd9Sstevel@tonic-gate
2247c478bd9Sstevel@tonic-gate /*
2257c478bd9Sstevel@tonic-gate * Examine the word.
2267c478bd9Sstevel@tonic-gate */
2277c478bd9Sstevel@tonic-gate if (word == 0) {
2287c478bd9Sstevel@tonic-gate return (-1);
2297c478bd9Sstevel@tonic-gate } else {
2307c478bd9Sstevel@tonic-gate return ((counter << BT_ULSHIFT) | (lowbit(word) - 1));
2317c478bd9Sstevel@tonic-gate }
2327c478bd9Sstevel@tonic-gate }
2337c478bd9Sstevel@tonic-gate
2347c478bd9Sstevel@tonic-gate /*
2357c478bd9Sstevel@tonic-gate * Copy the bitmap.
2367c478bd9Sstevel@tonic-gate */
2377c478bd9Sstevel@tonic-gate void
bt_copy(const ulong_t * from,ulong_t * to,ulong_t size)238*badf94ffSPatrick Mooney bt_copy(const ulong_t *from, ulong_t *to, ulong_t size)
2397c478bd9Sstevel@tonic-gate {
2407c478bd9Sstevel@tonic-gate ulong_t i;
2417c478bd9Sstevel@tonic-gate for (i = 0; i < size; i++)
2427c478bd9Sstevel@tonic-gate *to++ = *from++;
2437c478bd9Sstevel@tonic-gate }
244