kernel/os/bitmap.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, 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  */
  30
  31 #pragma ident   "%Z%%M% %I%     %E% SMI"
  32
  33 /*
  34  * Operations on bitmaps of arbitrary size
  35  * A bitmap is a vector of 1 or more ulongs.
  36  * The user of the package is responsible for range checks and keeping
  37  * track of sizes.
  38  */
  39
  40 #include <sys/types.h>
  41 #include <sys/bitmap.h>
  42 #include <sys/debug.h>          /* ASSERT */
  43
  44 /*
  45  * Return index of first available bit in denoted bitmap, or -1 for
  46  * failure.  Size is the cardinality of the bitmap; that is, the
  47  * number of bits.
  48  * No side-effects.  In particular, does not update bitmap.
  49  * Caller is responsible for range checks.
  50  */
  51 index_t
  52 bt_availbit(ulong_t *bitmap, size_t nbits)
  53 {
  54         index_t maxword;        /* index of last in map */
  55         index_t wx;             /* word index in map */
  56
  57         /*
  58          * Look for a word with a bit off.
  59          * Subtract one from nbits because we're converting it to a
  60          * a range of indices.
  61          */
  62         nbits -= 1;
  63         maxword = nbits >> BT_ULSHIFT;
  64         for (wx = 0; wx <= maxword; wx++)
  65                 if (bitmap[wx] != ~0)
  66                         break;
  67
  68         if (wx <= maxword) {
  69                 /*
  70                  * Found a word with a bit off.  Now find the bit in the word.
  71                  */
  72                 index_t bx;     /* bit index in word */
  73                 index_t maxbit; /* last bit to look at */
  74                 ulong_t         word;
  75                 ulong_t         bit;
  76
  77                 maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1;
  78                 word = bitmap[wx];
  79                 bit = 1;
  80                 for (bx = 0; bx <= maxbit; bx++, bit <<= 1) {
  81                         if (!(word & bit)) {
  82                                 return (wx << BT_ULSHIFT | bx);
  83                         }
  84                 }
  85         }
  86         return (-1);
  87 }
  88
  89
  90 /*
  91  * Find highest order bit that is on, and is within or below
  92  * the word specified by wx.
  93  */
  94 int
  95 bt_gethighbit(ulong_t *mapp, int wx)
  96 {
  97         ulong_t word;
  98
  99         while ((word = mapp[wx]) == 0) {
 100                 wx--;
 101                 if (wx < 0) {
 102                         return (-1);
 103                 }
 104         }
 105         return (wx << BT_ULSHIFT | (highbit(word) - 1));
 106 }
 107
 108
 109 /*
 110  * Search the bitmap for a consecutive pattern of 1's.
 111  * Search starts at position pos1.
 112  * Returns 1 on success and 0 on failure.
 113  * Side effects.
 114  * Returns indices to the first bit (pos1)
 115  * and one past the last bit (pos2) in the pattern.
 116  */
 117 int
 118 bt_range(ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos)
 119 {
 120         size_t pos;
 121
 122         for (pos = *pos1; pos < end_pos; pos++)
 123                 if (BT_TEST(bitmap, pos))
 124                         break;
 125
 126         if (pos == end_pos)
 127                 return (0);
 128
 129         *pos1 = pos;
 130
 131         for (; pos < end_pos; pos++)
 132                 if (!BT_TEST(bitmap, pos))
 133                         break;
 134         *pos2 = pos;
 135
 136         return (1);
 137 }
 138
 139
 140 /*
 141  * return the parity of the supplied long
 142  *
 143  * this works by successively partitioning the argument in half, and
 144  * setting the parity of the result to the parity of the 2 halfs, until
 145  * only one bit is left
 146  */
 147 int
 148 odd_parity(ulong_t i)
 149 {
 150 #ifdef _LP64
 151         i ^= i >> 32;
 152 #endif
 153         i ^= i >> 16;
 154         i ^= i >> 8;
 155         i ^= i >> 4;
 156         i ^= i >> 2;
 157         i ^= i >> 1;
 158
 159         return (i & 0x01);
 160 }
 161
 162
 163 /*
 164  * get the lowest bit in the range of 'start' and 'stop', inclusive.
 165  * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y,
 166  * including X and Y can be returned.
 167  * Neither start nor stop is required to align with word boundaries.
 168  * If a bit is set in the range, the bit position is returned; otherwise,
 169  * a -1 is returned.
 170  */
 171 int
 172 bt_getlowbit(ulong_t *map, size_t start, size_t stop)
 173 {
 174         ulong_t         word;
 175         int             counter = start >> BT_ULSHIFT;
 176         int             limit = stop >> BT_ULSHIFT;
 177         index_t         partial_start = start & BT_ULMASK;
 178         index_t         partial_stop = stop & BT_ULMASK;
 179
 180         if (start > stop) {
 181                 return (-1);
 182         }
 183
 184         /*
 185          * The range between 'start' and 'stop' can be very large, and the
 186          * '1' bits in this range can be sparse.
 187          * For performance reason, the underlying implementation operates
 188          * on words, not on bits.
 189          */
 190         word = map[counter];
 191
 192         if (partial_start) {
 193                 /*
 194                  * Since the start is not aligned on word boundary, we
 195                  * need to patch the unwanted low order bits with 0's before
 196                  * operating on the first bitmap word.
 197                  */
 198                 word = word & (BT_ULMAXMASK << partial_start);
 199         }
 200
 201         /*
 202          * Locate a word from the map array with one of the bits set.
 203          */
 204
 205         while ((word == 0) && (counter < limit)) {
 206                 word = map[++counter];
 207         }
 208
 209         /*
 210          * The end of range has similar problems if it is not aligned.
 211          * Taking care of the end which is not aligned.
 212          */
 213
 214         if ((counter == limit) && (partial_stop != BT_ULMASK)) {
 215                 /*
 216                  * Take care the partial word by patch the high order
 217                  * bits with 0's. Here we dealing with the case that
 218                  * the last word of the bitmap is not aligned.
 219                  */
 220
 221                 ASSERT(partial_stop < BT_ULMASK);
 222                 word = word & (~(BT_ULMAXMASK << partial_stop + 1));
 223         }
 224
 225         /*
 226          * Examine the word.
 227          */
 228         if (word == 0) {
 229                 return (-1);
 230         } else {
 231                 return ((counter << BT_ULSHIFT) | (lowbit(word) - 1));
 232         }
 233 }
 234
 235 /*
 236  * Copy the bitmap.
 237  */
 238 void
 239 bt_copy(ulong_t *from, ulong_t *to, ulong_t size)
 240 {
 241         ulong_t i;
 242         for (i = 0; i < size; i++)
 243                 *to++ = *from++;
 244 }