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 (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21/*
22 * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
23 */
24
25#include <sys/bitset.h>
26#include <sys/kmem.h>
27#include <sys/systm.h>
28#include <sys/cpuvar.h>
29#include <sys/cmn_err.h>
30#include <sys/sysmacros.h>
31
32/*
33 * Initialize a bitset_t.
34 * After bitset_init(), the bitset will be zero sized.
35 */
36void
37bitset_init(bitset_t *b)
38{
39	bzero(b, sizeof (bitset_t));
40}
41
42/*
43 * Initialize a bitset_t using a fanout. The fanout factor is platform
44 * specific and passed in as a power of two.
45 */
46void
47bitset_init_fanout(bitset_t *b, uint_t fanout)
48{
49	bzero(b, sizeof (bitset_t));
50	b->bs_fanout = fanout;
51}
52
53/*
54 * Uninitialize a bitset_t.
55 * This will free the bitset's data, leaving it zero sized.
56 */
57void
58bitset_fini(bitset_t *b)
59{
60	if (b->bs_words > 0)
61		kmem_free(b->bs_set, b->bs_words * sizeof (ulong_t));
62}
63
64/*
65 * Resize a bitset to where it can hold els number of elements.
66 * This can either grow or shrink the bitset holding capacity.
67 * In the case of shrinkage, elements that reside outside the new
68 * holding capacity of the bitset are lost.
69 */
70void
71bitset_resize(bitset_t *b, uint_t els)
72{
73	uint_t	nwords;
74	ulong_t	*bset_new, *bset_tmp;
75
76	nwords = BT_BITOUL(els << b->bs_fanout);
77	if (b->bs_words == nwords)
78		return;	/* already properly sized */
79
80	/*
81	 * Allocate the new ulong_t array, and copy the old one, if there
82	 * was an old one.
83	 */
84	if (nwords > 0) {
85		bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
86		if (b->bs_words > 0)
87			bcopy(b->bs_set, bset_new,
88			    MIN(b->bs_words, nwords) * sizeof (ulong_t));
89	} else {
90		bset_new = NULL;
91	}
92
93	/* swap out the old ulong_t array for new one */
94	bset_tmp = b->bs_set;
95	b->bs_set = bset_new;
96
97	/* free up the old array */
98	if (b->bs_words > 0)
99		kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t));
100
101	b->bs_words = nwords;
102}
103
104/*
105 * Returns the current holding capacity of the bitset.
106 */
107uint_t
108bitset_capacity(bitset_t *b)
109{
110	return (b->bs_words * BT_NBIPUL);
111}
112
113/*
114 * Add (set) and delete (clear) bits in the bitset.
115 *
116 * Adding a bit that is already set, or removing a bit that's already clear
117 * is legal.
118 *
119 * Adding or deleting an element that falls outside the bitset's current
120 * holding capacity is illegal.
121 */
122void
123bitset_add(bitset_t *b, uint_t elt)
124{
125	uint_t pos = (elt << b->bs_fanout);
126
127	ASSERT(b->bs_words * BT_NBIPUL > pos);
128	BT_SET(b->bs_set, pos);
129}
130
131/*
132 * Set a bit in an atomically safe way.
133 */
134void
135bitset_atomic_add(bitset_t *b, uint_t elt)
136{
137	uint_t pos = (elt << b->bs_fanout);
138
139	ASSERT(b->bs_words * BT_NBIPUL > pos);
140	BT_ATOMIC_SET(b->bs_set, pos);
141}
142
143/*
144 * Atomically test that a given bit isn't set, and set it.
145 * Returns -1 if the bit was already set.
146 */
147int
148bitset_atomic_test_and_add(bitset_t *b, uint_t elt)
149{
150	uint_t pos = (elt << b->bs_fanout);
151	int ret;
152
153	ASSERT(b->bs_words * BT_NBIPUL > pos);
154	BT_ATOMIC_SET_EXCL(b->bs_set, pos, ret);
155
156	return (ret);
157}
158
159/*
160 * Clear a bit.
161 */
162void
163bitset_del(bitset_t *b, uint_t elt)
164{
165	uint_t pos = (elt << b->bs_fanout);
166
167	ASSERT(b->bs_words * BT_NBIPUL > pos);
168	BT_CLEAR(b->bs_set, pos);
169}
170
171/*
172 * Clear a bit in an atomically safe way.
173 */
174void
175bitset_atomic_del(bitset_t *b, uint_t elt)
176{
177	uint_t pos = (elt << b->bs_fanout);
178
179	ASSERT(b->bs_words * BT_NBIPUL > pos);
180	BT_ATOMIC_CLEAR(b->bs_set, pos);
181}
182
183/*
184 * Atomically test that a bit is set, and clear it.
185 * Returns -1 if the bit was already clear.
186 */
187int
188bitset_atomic_test_and_del(bitset_t *b, uint_t elt)
189{
190	uint_t pos = (elt << b->bs_fanout);
191	int ret;
192
193	ASSERT(b->bs_words * BT_NBIPUL > pos);
194	BT_ATOMIC_CLEAR_EXCL(b->bs_set, pos, ret);
195
196	return (ret);
197}
198
199/*
200 * Return non-zero if the bit is present in the set.
201 */
202int
203bitset_in_set(bitset_t *b, uint_t elt)
204{
205	uint_t pos = (elt << b->bs_fanout);
206
207	if (pos >= b->bs_words * BT_NBIPUL)
208		return (0);
209
210	return (BT_TEST(b->bs_set, pos));
211}
212
213/*
214 * Return non-zero if the bitset is empty.
215 */
216int
217bitset_is_null(bitset_t *b)
218{
219	int i;
220
221	for (i = 0; i < b->bs_words; i++)
222		if (b->bs_set[i] != 0)
223			return (0);
224	return (1);
225}
226
227/*
228 * Perform a non-victimizing search for a set bit in a word.
229 * A "seed" is passed to pseudo-randomize the search.
230 * Return -1 if no set bit was found.
231 */
232static uint_t
233bitset_find_in_word(ulong_t w, uint_t seed)
234{
235	uint_t rotate_bit, elt = (uint_t)-1;
236	ulong_t rotated_word;
237
238	if (w == (ulong_t)0)
239		return (elt);
240
241	rotate_bit = seed % BT_NBIPUL;
242	rotated_word = (w >> rotate_bit) | (w << (BT_NBIPUL - rotate_bit));
243	elt = (uint_t)(lowbit(rotated_word) - 1);
244	if (elt != (uint_t)-1)
245		elt = ((elt + rotate_bit) % BT_NBIPUL);
246
247	return (elt);
248}
249
250/*
251 * Select a bit that is set in the bitset in a non-victimizing fashion
252 * (e.g. doesn't bias the low/high order bits/words).
253 * Return -1 if no set bit was found
254 */
255uint_t
256bitset_find(bitset_t *b)
257{
258	uint_t start, i;
259	uint_t elt = (uint_t)-1;
260	uint_t seed;
261
262	seed = CPU_PSEUDO_RANDOM();
263
264	ASSERT(b->bs_words > 0);
265	start = seed % b->bs_words;
266
267	i = start;
268	do {
269		elt = bitset_find_in_word(b->bs_set[i], seed);
270		if (elt != (uint_t)-1) {
271			elt += i * BT_NBIPUL;
272			return (elt >> b->bs_fanout);
273		}
274		if (++i == b->bs_words)
275			i = 0;
276	} while (i != start);
277
278	return (elt);
279}
280
281/*
282 * AND, OR, and XOR bitset computations, returns 1 if resulting bitset has any
283 * set bits. Operands must have the same fanout, if any.
284 */
285int
286bitset_and(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
287{
288	int i, anyset;
289
290	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
291	ASSERT(bs1->bs_fanout == res->bs_fanout);
292
293	for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
294		if ((res->bs_set[i] = (bs1->bs_set[i] & bs2->bs_set[i])) != 0)
295			anyset = 1;
296	}
297	return (anyset);
298}
299
300int
301bitset_or(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
302{
303	int i, anyset;
304
305	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
306	ASSERT(bs1->bs_fanout == res->bs_fanout);
307
308	for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
309		if ((res->bs_set[i] = (bs1->bs_set[i] | bs2->bs_set[i])) != 0)
310			anyset = 1;
311	}
312	return (anyset);
313}
314
315int
316bitset_xor(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
317{
318	int i, anyset = 0;
319
320	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
321	ASSERT(bs1->bs_fanout == res->bs_fanout);
322
323	for (i = 0; i < bs1->bs_words; i++) {
324		if ((res->bs_set[i] = (bs1->bs_set[i] ^ bs2->bs_set[i])) != 0)
325			anyset = 1;
326	}
327	return (anyset);
328}
329
330/*
331 * Return 1 if bitmaps are identical.
332 */
333int
334bitset_match(bitset_t *bs1, bitset_t *bs2)
335{
336	int i;
337
338	if (bs1->bs_words != bs2->bs_words)
339		return (0);
340
341	for (i = 0; i < bs1->bs_words; i++)
342		if (bs1->bs_set[i] != bs2->bs_set[i])
343			return (0);
344	return (1);
345}
346
347/*
348 * Zero a bitset_t.
349 */
350void
351bitset_zero(bitset_t *b)
352{
353	bzero(b->bs_set, sizeof (ulong_t) * b->bs_words);
354}
355
356/*
357 * Copy a bitset_t.
358 */
359void
360bitset_copy(bitset_t *src, bitset_t *dest)
361{
362	ASSERT(src->bs_fanout == dest->bs_fanout);
363	bcopy(src->bs_set, dest->bs_set, sizeof (ulong_t) * src->bs_words);
364}
365