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