ipc/bit_array.c

   1 /***************************************************************************
   2  * Copyright 1995, Technion, Israel Institute of Technology
   3  * Electrical Eng, Software Lab.
   4  * Author:    Michael Veksler.
   5  ***************************************************************************
   6  * File:      bit_array.c
   7  * Purpose :  manipulate array of bits
   8  * Portability: This is not completely portable, non CISC arcitectures
   9  *              Might not have atomic Clear/Set/Toggle bit. On those
  10  *              architectures semaphores should be used.
  11  * Big Endian Concerns: This code is big endian compatible,
  12  *              but the byte order will be different (i.e. bit 0 will be
  13  *              located in byte 3).
  14  ***************************************************************************
  15  */
  16
  17 #ifdef CONFIG_IPC
  18
  19 /*
  20 ** uncoment the following line to disable assertions,
  21 ** this may boost performance by up to 50%
  22 */
  23 /* #define NDEBUG */
  24
  25 #if defined(linux) && !defined(NO_ASM)
  26 #include <linux/version.h>
  27 #if LINUX_VERSION_CODE <= 131328 /* Linux 2.1.x doesn't return values with clear_bit and set_bit */
  28 #define HAS_BITOPS
  29 #endif
  30 #endif
  31
  32 #include <stdio.h>
  33
  34 #include <assert.h>
  35
  36 #include "bit_array.h"
  37 #ifdef HAS_BITOPS
  38 #include <asm/bitops.h>
  39 #else
  40 static inline int clear_bit(int bit, int *mem);
  41 static inline int set_bit(int bit, int *mem);
  42 #endif /* HAS_BITOPS */
  43
  44
  45 #define INT_NR(bit_nr)       ((bit_nr) >> INT_LOG2)
  46 #define INT_COUNT(bit_count) INT_NR( bit_count + BITS_PER_INT - 1 )
  47 #define BIT_IN_INT(bit_nr)   ((bit_nr) & (BITS_PER_INT - 1))
  48
  49 #if !defined(HAS_BITOPS)
  50
  51 /* first_zero maps bytes value to the index of first zero bit */
  52 static char first_zero[256];
  53 static int arrays_initialized=0;
  54
  55
  56 /*
  57 ** initialize static arrays used for bit operations speedup.
  58 ** Currently initialized: first_zero[256]
  59 ** set "arrays_initialized" to inidate that arrays where initialized
  60 */
  61
  62 static void initialize_arrays()
  63 {
  64   int i;
  65   int bit;
  66
  67   for (i=0 ; i<256 ; i++) {
  68      /* find the first zero bit in `i' */
  69      for (bit=0 ; bit < BITS_PER_BYTE ; bit++)
  70         /* break if the bit is zero */
  71         if ( ( (1 << bit) & i )
  72              == 0)
  73            break;
  74      first_zero[i]= bit;
  75   }
  76   arrays_initialized=1;
  77 }
  78
  79 /*
  80 ** Find first zero bit in the integer.
  81 ** Assume there is at least one zero.
  82 */
  83 static inline int find_zbit_in_integer(unsigned int integer)
  84 {
  85   int i;
  86
  87   /* find the zero bit */
  88   for (i=0 ; i < sizeof(int) ; i++, integer>>=8) {
  89      int byte= integer & 0xff;
  90
  91      if (byte != 0xff)
  92         return ( first_zero[ byte ]
  93                  + (i << BYTE_LOG2) );
  94   }
  95   assert(0);                       /* never reached */
  96   return 0;
  97 }
  98
  99 /* return -1 on failure */
 100 static inline int find_first_zero_bit(unsigned *array, int bits)
 101 {
 102   unsigned int  integer;
 103   int i;
 104   int bytes=INT_COUNT(bits);
 105
 106   if (!arrays_initialized)
 107      initialize_arrays();
 108
 109   for ( i=bytes ; i ; i--, array++) {
 110      integer= *array;
 111
 112      /* test if integer contains a zero bit */
 113      if (integer != ~0U)
 114         return ( find_zbit_in_integer(integer)
 115                  + ((bytes-i) << INT_LOG2) );
 116   }
 117
 118   /* indicate failure */
 119   return -1;
 120 }
 121
 122 static inline int test_bit(int pos, unsigned *array)
 123 {
 124   unsigned int integer;
 125   int bit = BIT_IN_INT(pos);
 126
 127   integer= array[ pos >> INT_LOG2 ];
 128
 129   return (  (integer & (1 << bit)) != 0
 130             ? 1
 131             : 0 ) ;
 132 }
 133
 134 /*
 135 ** The following two functions are x86 specific ,
 136 ** other processors will need porting
 137 */
 138
 139 /* inputs: bit number and memory address (32 bit) */
 140 /* output: Value of the bit before modification */
 141 static inline int clear_bit(int bit, int *mem)
 142 {
 143   int ret;
 144
 145   __asm__("xor %1,%1\n"
 146           "btrl %2,%0\n"
 147           "adcl %1,%1\n"
 148           :"=m" (*mem), "=&r" (ret)
 149           :"r" (bit));
 150   return (ret);
 151 }
 152
 153 static inline int set_bit(int bit, int *mem)
 154 {
 155   int ret;
 156   __asm__("xor %1,%1\n"
 157           "btsl %2,%0\n"
 158           "adcl %1,%1\n"
 159           :"=m" (*mem), "=&r" (ret)
 160           :"r" (bit));
 161   return (ret);
 162 }
 163
 164 #endif /* !deined(HAS_BITOPS) */
 165
 166
 167 /* AssembleArray: assemble an array object using existing data */
 168 bit_array *AssembleArray(bit_array *new_array, unsigned int *buff, int bits)
 169 {
 170   assert(new_array!=NULL);
 171   assert(buff!=NULL);
 172   assert(bits>0);
 173   assert((1 << INT_LOG2) == BITS_PER_INT); /* if fails, redefine INT_LOG2 */
 174
 175   new_array->bits=bits;
 176   new_array->array=buff;
 177   return new_array;
 178 }
 179
 180 /* ResetArray: reset the bit array to zeros */
 181 int ResetArray(bit_array *bits)
 182 {
 183   int i;
 184   int *p;
 185
 186   assert(bits!=NULL);
 187   assert(bits->array!=NULL);
 188
 189   for(i= INT_COUNT(bits->bits), p=bits->array; i ; p++, i--)
 190      *p=0;
 191   return 1;
 192 }
 193
 194
 195 /* VacantBit: find a vacant (zero) bit in the array,
 196  * Return: Bit index on success, -1 on failure.
 197  */
 198 int VacantBit(bit_array *bits)
 199 {
 200   int bit;
 201
 202   assert(bits!=NULL);
 203   assert(bits->array!=NULL);
 204
 205   bit= find_first_zero_bit(bits->array, bits->bits);
 206
 207   if (bit >= bits->bits)           /* failed? */
 208      return -1;
 209
 210   return bit;
 211 }
 212
 213 int SampleBit(bit_array *bits, int i)
 214 {
 215   assert(bits != NULL);
 216   assert(bits->array != NULL);
 217   assert(i >= 0  &&  i < bits->bits);
 218
 219   return ( test_bit(i,bits->array) != 0
 220            ? 1
 221            : 0
 222            );
 223 }
 224
 225
 226 /*
 227 ** Use "compare and exchange" mechanism to make sure
 228 ** that bits are not modified while "integer" value
 229 ** is calculated.
 230 **
 231 ** This may be the slowest technique, but it is the most portable
 232 ** (Since most architectures have compare and exchange command)
 233 */
 234 int AssignBit(bit_array *bits, int bit_nr, int val)
 235 {
 236   int ret;
 237
 238   assert(bits != NULL);
 239   assert(bits->array != NULL);
 240   assert(val==0 || val==1);
 241   assert(bit_nr >= 0  &&  bit_nr < bits->bits);
 242
 243   if (val==0)
 244      ret= clear_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
 245   else
 246      ret= set_bit(BIT_IN_INT(bit_nr), &bits->array[ INT_NR(bit_nr) ]);
 247
 248   return ( (ret!=0) ? 1 : 0);
 249 }
 250
 251 /*
 252 ** Allocate a free bit (==0) and make it used (==1).
 253 ** This operation is guaranteed to resemble an atomic instruction.
 254 **
 255 ** Return: allocated bit index, or -1 on failure.
 256 **
 257 ** There is a crack between locating free bit, and allocating it.
 258 ** We assign 1 to the bit, test it was not '1' before the assignment.
 259 ** If it was, restart the seek and assign cycle.
 260 **
 261 */
 262
 263 int AllocateBit(bit_array *bits)
 264 {
 265   int bit_nr;
 266   int orig_bit;
 267
 268   assert(bits != NULL);
 269   assert(bits->array != NULL);
 270
 271   do {
 272      bit_nr= VacantBit(bits);
 273
 274      if (bit_nr == -1)             /* No vacant bit ? */
 275         return -1;
 276
 277      orig_bit = AssignBit(bits, bit_nr, 1);
 278   } while (orig_bit != 0);         /* it got assigned before we tried */
 279
 280   return bit_nr;
 281 }
 282
 283 #endif  /* CONFIG_IPC */