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 2008 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26 #include <sys/bitset.h> 27 #include <sys/kmem.h> 28 #include <sys/systm.h> 29 #include <sys/cpuvar.h> 30 #include <sys/cmn_err.h> 31 #include <sys/sysmacros.h> 32 33 /* 34 * Initialize a bitset_t. 35 * After bitset_init(), the bitset will be zero sized. 36 */ 37 void 38 bitset_init(bitset_t *b) 39 { 40 bzero(b, sizeof (bitset_t)); 41 } 42 43 /* 44 * Uninitialize a bitset_t. 45 * This will free the bitset's data, leaving it zero sized. 46 */ 47 void 48 bitset_fini(bitset_t *b) 49 { 50 if (b->bs_words > 0) 51 kmem_free(b->bs_set, b->bs_words * sizeof (ulong_t)); 52 } 53 54 /* 55 * Resize a bitset to where it can hold sz number of bits. 56 * This can either grow or shrink the bitset holding capacity. 57 * In the case of shrinkage, elements that reside outside the new 58 * holding capacity of the bitset are lost. 59 */ 60 void 61 bitset_resize(bitset_t *b, uint_t sz) 62 { 63 uint_t nwords; 64 ulong_t *bset_new, *bset_tmp; 65 66 nwords = BT_BITOUL(sz); 67 if (b->bs_words == nwords) 68 return; /* already properly sized */ 69 70 /* 71 * Allocate the new ulong_t array, and copy the old one, if there 72 * was an old one. 73 */ 74 if (nwords > 0) { 75 bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP); 76 if (b->bs_words > 0) 77 bcopy(b->bs_set, bset_new, 78 MIN(b->bs_words, nwords) * sizeof (ulong_t)); 79 } else { 80 bset_new = NULL; 81 } 82 83 /* swap out the old ulong_t array for new one */ 84 bset_tmp = b->bs_set; 85 b->bs_set = bset_new; 86 87 /* free up the old array */ 88 if (b->bs_words > 0) 89 kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t)); 90 b->bs_words = nwords; 91 } 92 93 /* 94 * Returns the current holding capacity of the bitset 95 */ 96 uint_t 97 bitset_capacity(bitset_t *b) 98 { 99 return (b->bs_words * BT_NBIPUL); 100 } 101 102 /* 103 * Add and delete bits in the bitset. 104 * 105 * Adding a bit that is already set, and clearing a bit that's already clear 106 * is legal. 107 * 108 * Adding or deleting an element that falls outside the bitset's current 109 * holding capacity is illegal. 110 */ 111 112 /* 113 * Set a bit 114 */ 115 void 116 bitset_add(bitset_t *b, uint_t elt) 117 { 118 ASSERT(b->bs_words * BT_NBIPUL > elt); 119 120 BT_SET(b->bs_set, elt); 121 } 122 123 /* 124 * Set a bit in an atomically safe way 125 */ 126 void 127 bitset_atomic_add(bitset_t *b, uint_t elt) 128 { 129 ASSERT(b->bs_words * BT_NBIPUL > elt); 130 131 BT_ATOMIC_SET(b->bs_set, elt); 132 } 133 134 /* 135 * Atomically test that a given bit isn't set, and set it. 136 * Returns -1 if the bit was already set. 137 */ 138 int 139 bitset_atomic_test_and_add(bitset_t *b, uint_t elt) 140 { 141 int r; 142 143 ASSERT(b->bs_words * BT_NBIPUL > elt); 144 BT_ATOMIC_SET_EXCL(b->bs_set, elt, r); 145 146 return (r); 147 } 148 149 /* 150 * Clear a bit 151 */ 152 void 153 bitset_del(bitset_t *b, uint_t elt) 154 { 155 ASSERT(b->bs_words * BT_NBIPUL > elt); 156 157 BT_CLEAR(b->bs_set, elt); 158 } 159 160 /* 161 * Clear a bit in an atomically safe way 162 */ 163 void 164 bitset_atomic_del(bitset_t *b, uint_t elt) 165 { 166 ASSERT(b->bs_words * BT_NBIPUL > elt); 167 168 BT_ATOMIC_CLEAR(b->bs_set, elt); 169 } 170 171 /* 172 * Atomically test that a bit is set, and clear it. 173 * Returns -1 if the bit was already clear. 174 */ 175 int 176 bitset_atomic_test_and_del(bitset_t *b, uint_t elt) 177 { 178 int r; 179 180 ASSERT(b->bs_words * BT_NBIPUL > elt); 181 BT_ATOMIC_CLEAR_EXCL(b->bs_set, elt, r); 182 183 return (r); 184 } 185 186 /* 187 * Return non-zero if the bit is present in the set 188 */ 189 int 190 bitset_in_set(bitset_t *b, uint_t elt) 191 { 192 if (elt >= b->bs_words * BT_NBIPUL) 193 return (0); 194 195 return (BT_TEST(b->bs_set, elt)); 196 } 197 198 /* 199 * Return non-zero if the bitset is empty 200 */ 201 int 202 bitset_is_null(bitset_t *b) 203 { 204 int i; 205 206 for (i = 0; i < b->bs_words; i++) 207 if (b->bs_set[i] != 0) 208 return (0); 209 return (1); 210 } 211 212 /* 213 * Perform a non-victimizing search for a set bit in a word 214 * A "seed" is passed to pseudo-randomize the search. 215 * Return -1 if no set bit was found 216 */ 217 static uint_t 218 bitset_find_in_word(ulong_t w, uint_t seed) 219 { 220 uint_t rotate_bit, elt = (uint_t)-1; 221 ulong_t rotated_word; 222 223 if (w == (ulong_t)0) 224 return (elt); 225 226 rotate_bit = seed % BT_NBIPUL; 227 rotated_word = (w >> rotate_bit) | (w << (BT_NBIPUL - rotate_bit)); 228 elt = (uint_t)(lowbit(rotated_word) - 1); 229 if (elt != (uint_t)-1) 230 elt = ((elt + rotate_bit) % BT_NBIPUL); 231 232 return (elt); 233 } 234 235 /* 236 * Select a bit that is set in the bitset in a non-victimizing fashion 237 * (e.g. doesn't bias the low/high order bits/words). 238 * Return -1 if no set bit was found 239 */ 240 uint_t 241 bitset_find(bitset_t *b) 242 { 243 uint_t start, i; 244 uint_t elt = (uint_t)-1; 245 uint_t seed; 246 247 seed = CPU_PSEUDO_RANDOM(); 248 start = seed % b->bs_words; 249 250 i = start; 251 do { 252 elt = bitset_find_in_word(b->bs_set[i], seed); 253 if (elt != (uint_t)-1) { 254 elt += i * BT_NBIPUL; 255 break; 256 } 257 if (++i == b->bs_words) 258 i = 0; 259 } while (i != start); 260 261 return (elt); 262 } 263