1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
23 /* All Rights Reserved */
24
25
26 /*
27 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
28 * Use is subject to license terms.
29 * Copyright 2022 Oxide Computer Company
30 */
31
32 /*
33 * Operations on bitmaps of arbitrary size
34 * A bitmap is a vector of 1 or more ulongs.
35 * The user of the package is responsible for range checks and keeping
36 * track of sizes.
37 */
38
39 #include <sys/types.h>
40 #include <sys/bitmap.h>
41 #include <sys/debug.h>
42
43 /*
44 * Return index of first available bit in denoted bitmap, or -1 for
45 * failure. Size is the cardinality of the bitmap; that is, the
46 * number of bits.
47 * No side-effects. In particular, does not update bitmap.
48 * Caller is responsible for range checks.
49 */
50 index_t
bt_availbit(const ulong_t * bitmap,size_t nbits)51 bt_availbit(const ulong_t *bitmap, size_t nbits)
52 {
53 index_t maxword; /* index of last in map */
54 index_t wx; /* word index in map */
55
56 /*
57 * Look for a word with a bit off.
58 * Subtract one from nbits because we're converting it to a
59 * a range of indices.
60 */
61 nbits -= 1;
62 maxword = nbits >> BT_ULSHIFT;
63 for (wx = 0; wx <= maxword; wx++)
64 if (bitmap[wx] != ~0)
65 break;
66
67 if (wx <= maxword) {
68 /*
69 * Found a word with a bit off. Now find the bit in the word.
70 */
71 index_t bx; /* bit index in word */
72 index_t maxbit; /* last bit to look at */
73 ulong_t word;
74 ulong_t bit;
75
76 maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1;
77 word = bitmap[wx];
78 bit = 1;
79 for (bx = 0; bx <= maxbit; bx++, bit <<= 1) {
80 if (!(word & bit)) {
81 return (wx << BT_ULSHIFT | bx);
82 }
83 }
84 }
85 return (-1);
86 }
87
88
89 /*
90 * Find highest order bit that is on, and is within or below
91 * the word specified by wx.
92 */
93 int
bt_gethighbit(const ulong_t * mapp,int wx)94 bt_gethighbit(const ulong_t *mapp, int wx)
95 {
96 ulong_t word;
97
98 while ((word = mapp[wx]) == 0) {
99 wx--;
100 if (wx < 0) {
101 return (-1);
102 }
103 }
104 return (wx << BT_ULSHIFT | (highbit(word) - 1));
105 }
106
107
108 /*
109 * Search the bitmap for a consecutive pattern of 1's.
110 * Search starts at position pos1.
111 * Returns 1 on success and 0 on failure.
112 * Side effects.
113 * Returns indices to the first bit (pos1)
114 * and one past the last bit (pos2) in the pattern.
115 */
116 int
bt_range(const ulong_t * bitmap,size_t * pos1,size_t * pos2,size_t end_pos)117 bt_range(const ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos)
118 {
119 size_t pos;
120
121 for (pos = *pos1; pos < end_pos; pos++)
122 if (BT_TEST(bitmap, pos))
123 break;
124
125 if (pos == end_pos)
126 return (0);
127
128 *pos1 = pos;
129
130 for (; pos < end_pos; pos++)
131 if (!BT_TEST(bitmap, pos))
132 break;
133 *pos2 = pos;
134
135 return (1);
136 }
137
138
139 /*
140 * return the parity of the supplied long
141 *
142 * this works by successively partitioning the argument in half, and
143 * setting the parity of the result to the parity of the 2 halfs, until
144 * only one bit is left
145 */
146 int
odd_parity(ulong_t i)147 odd_parity(ulong_t i)
148 {
149 #ifdef _LP64
150 i ^= i >> 32;
151 #endif
152 i ^= i >> 16;
153 i ^= i >> 8;
154 i ^= i >> 4;
155 i ^= i >> 2;
156 i ^= i >> 1;
157
158 return (i & 0x01);
159 }
160
161
162 /*
163 * get the lowest bit in the range of 'start' and 'stop', inclusive.
164 * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y,
165 * including X and Y can be returned.
166 * Neither start nor stop is required to align with word boundaries.
167 * If a bit is set in the range, the bit position is returned; otherwise,
168 * a -1 is returned.
169 */
170 int
bt_getlowbit(const ulong_t * map,size_t start,size_t stop)171 bt_getlowbit(const ulong_t *map, size_t start, size_t stop)
172 {
173 ulong_t word;
174 int counter = start >> BT_ULSHIFT;
175 int limit = stop >> BT_ULSHIFT;
176 index_t partial_start = start & BT_ULMASK;
177 index_t partial_stop = stop & BT_ULMASK;
178
179 if (start > stop) {
180 return (-1);
181 }
182
183 /*
184 * The range between 'start' and 'stop' can be very large, and the
185 * '1' bits in this range can be sparse.
186 * For performance reason, the underlying implementation operates
187 * on words, not on bits.
188 */
189 word = map[counter];
190
191 if (partial_start) {
192 /*
193 * Since the start is not aligned on word boundary, we
194 * need to patch the unwanted low order bits with 0's before
195 * operating on the first bitmap word.
196 */
197 word = word & (BT_ULMAXMASK << partial_start);
198 }
199
200 /*
201 * Locate a word from the map array with one of the bits set.
202 */
203
204 while ((word == 0) && (counter < limit)) {
205 word = map[++counter];
206 }
207
208 /*
209 * The end of range has similar problems if it is not aligned.
210 * Taking care of the end which is not aligned.
211 */
212
213 if ((counter == limit) && (partial_stop != BT_ULMASK)) {
214 /*
215 * Take care the partial word by patch the high order
216 * bits with 0's. Here we dealing with the case that
217 * the last word of the bitmap is not aligned.
218 */
219
220 ASSERT(partial_stop < BT_ULMASK);
221 word = word & (~(BT_ULMAXMASK << partial_stop + 1));
222 }
223
224 /*
225 * Examine the word.
226 */
227 if (word == 0) {
228 return (-1);
229 } else {
230 return ((counter << BT_ULSHIFT) | (lowbit(word) - 1));
231 }
232 }
233
234 /*
235 * Copy the bitmap.
236 */
237 void
bt_copy(const ulong_t * from,ulong_t * to,ulong_t size)238 bt_copy(const ulong_t *from, ulong_t *to, ulong_t size)
239 {
240 ulong_t i;
241 for (i = 0; i < size; i++)
242 *to++ = *from++;
243 }
244