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