kernel/os/bitset.c

   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  */
  36 void
  37 bitset_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  */
  46 void
  47 bitset_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  */
  57 void
  58 bitset_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  */
  70 void
  71 bitset_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  */
 107 uint_t
 108 bitset_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  */
 122 void
 123 bitset_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  */
 134 void
 135 bitset_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  */
 147 int
 148 bitset_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  */
 162 void
 163 bitset_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  */
 174 void
 175 bitset_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  */
 187 int
 188 bitset_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  */
 202 int
 203 bitset_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  */
 216 int
 217 bitset_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  */
 232 static uint_t
 233 bitset_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  */
 255 uint_t
 256 bitset_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  */
 285 int
 286 bitset_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
 300 int
 301 bitset_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
 315 int
 316 bitset_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  */
 333 int
 334 bitset_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  */
 350 void
 351 bitset_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  */
 359 void
 360 bitset_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 }