xref: /illumos-gate/usr/src/uts/common/os/bitmap.c (revision badf94ff3599fab15963f6c532929e9bc411757a)
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