pintos-os.org Git - pintos-anon/blob - src/lib/kernel/bitmap.c

   1 #include "bitmap.h"
   2 #include <debug.h>
   3 #include <limits.h>
   4 #include <round.h>
   5 #include <stdio.h>
   6 #include "threads/malloc.h"
   7 #ifdef FILESYS
   8 #include "filesys/file.h"
   9 #endif
  10 \f
  11 /* Element type.
  12
  13    This must be an unsigned integer type at least as wide as int.
  14
  15    Each bit represents one bit in the bitmap.
  16    If bit 0 in an element represents bit K in the bitmap,
  17    then bit 1 in the element represents bit K+1 in the bitmap,
  18    and so on. */
  19 typedef unsigned long elem_type;
  20
  21 /* Number of bits in an element. */
  22 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
  23
  24 /* From the outside, a bitmap is an array of bits.  From the
  25    inside, it's an array of elem_type (defined above) that
  26    simulates an array of bits. */
  27 struct bitmap
  28   {
  29     size_t bit_cnt;     /* Number of bits. */
  30     elem_type *bits;    /* Elements that represent bits. */
  31   };
  32
  33 /* Returns the index of the element that contains the bit
  34    numbered BIT_IDX. */
  35 static inline size_t
  36 elem_idx (size_t bit_idx)
  37 {
  38   return bit_idx / ELEM_BITS;
  39 }
  40
  41 /* Returns an elem_type where only the bit corresponding to
  42    BIT_IDX is turned on. */
  43 static inline elem_type
  44 bit_mask (size_t bit_idx)
  45 {
  46   return (elem_type) 1 << (bit_idx % ELEM_BITS);
  47 }
  48
  49 /* Returns the number of elements required for BIT_CNT bits. */
  50 static inline size_t
  51 elem_cnt (size_t bit_cnt)
  52 {
  53   return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
  54 }
  55
  56 /* Returns the number of bytes required for BIT_CNT bits. */
  57 static inline size_t
  58 byte_cnt (size_t bit_cnt)
  59 {
  60   return sizeof (elem_type) * elem_cnt (bit_cnt);
  61 }
  62
  63 /* Returns a bit mask in which the bits actually used in the last
  64    element of B's bits are set to 1 and the rest are set to 0. */
  65 static inline elem_type
  66 last_mask (const struct bitmap *b)
  67 {
  68   int last_bits = b->bit_cnt % ELEM_BITS;
  69   return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
  70 }
  71 \f
  72 /* Creation and destruction. */
  73
  74 /* Creates and returns a pointer to a newly allocated bitmap with room for
  75    BIT_CNT (or more) bits.  Returns a null pointer if memory allocation fails.
  76    The caller is responsible for freeing the bitmap, with bitmap_destroy(),
  77    when it is no longer needed. */
  78 struct bitmap *
  79 bitmap_create (size_t bit_cnt)
  80 {
  81   struct bitmap *b = malloc (sizeof *b);
  82   if (b != NULL)
  83     {
  84       b->bit_cnt = bit_cnt;
  85       b->bits = malloc (byte_cnt (bit_cnt));
  86       if (b->bits != NULL || bit_cnt == 0)
  87         {
  88           bitmap_set_all (b, false);
  89           return b;
  90         }
  91       free (b);
  92     }
  93   return NULL;
  94 }
  95
  96 /* Creates and returns a bitmap with BIT_CNT bits in the
  97    BLOCK_SIZE bytes of storage preallocated at BLOCK.
  98    BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
  99 struct bitmap *
 100 bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
 101 {
 102   struct bitmap *b = block;
 103
 104   ASSERT (block_size >= bitmap_buf_size (bit_cnt));
 105
 106   b->bit_cnt = bit_cnt;
 107   b->bits = (elem_type *) (b + 1);
 108   bitmap_set_all (b, false);
 109   return b;
 110 }
 111
 112 /* Returns the number of bytes required to accomodate a bitmap
 113    with BIT_CNT bits (for use with bitmap_create_in_buf()). */
 114 size_t
 115 bitmap_buf_size (size_t bit_cnt)
 116 {
 117   return sizeof (struct bitmap) + byte_cnt (bit_cnt);
 118 }
 119
 120 /* Destroys bitmap B, freeing its storage.
 121    Not for use on bitmaps created by bitmap_create_in_buf(). */
 122 void
 123 bitmap_destroy (struct bitmap *b)
 124 {
 125   if (b != NULL)
 126     {
 127       free (b->bits);
 128       free (b);
 129     }
 130 }
 131 \f
 132 /* Bitmap size. */
 133
 134 /* Returns the number of bits in B. */
 135 size_t
 136 bitmap_size (const struct bitmap *b)
 137 {
 138   return b->bit_cnt;
 139 }
 140 \f
 141 /* Setting and testing single bits. */
 142
 143 /* Atomically sets the bit numbered IDX in B to VALUE. */
 144 void
 145 bitmap_set (struct bitmap *b, size_t idx, bool value)
 146 {
 147   ASSERT (b != NULL);
 148   ASSERT (idx < b->bit_cnt);
 149   if (value)
 150     bitmap_mark (b, idx);
 151   else
 152     bitmap_reset (b, idx);
 153 }
 154
 155 /* Atomically sets the bit numbered BIT_IDX in B to true. */
 156 void
 157 bitmap_mark (struct bitmap *b, size_t bit_idx)
 158 {
 159   size_t idx = elem_idx (bit_idx);
 160   elem_type mask = bit_mask (bit_idx);
 161
 162   /* This is equivalent to `b->bits[idx] |= mask' except that it
 163      is guaranteed to be atomic on a uniprocessor machine.  See
 164      the description of the OR instruction in [IA32-v2b]. */
 165   asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
 166 }
 167
 168 /* Atomically sets the bit numbered BIT_IDX in B to false. */
 169 void
 170 bitmap_reset (struct bitmap *b, size_t bit_idx)
 171 {
 172   size_t idx = elem_idx (bit_idx);
 173   elem_type mask = bit_mask (bit_idx);
 174
 175   /* This is equivalent to `b->bits[idx] &= ~mask' except that it
 176      is guaranteed to be atomic on a uniprocessor machine.  See
 177      the description of the AND instruction in [IA32-v2a]. */
 178   asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
 179 }
 180
 181 /* Atomically toggles the bit numbered IDX in B;
 182    that is, if it is true, makes it false,
 183    and if it is false, makes it true. */
 184 void
 185 bitmap_flip (struct bitmap *b, size_t bit_idx)
 186 {
 187   size_t idx = elem_idx (bit_idx);
 188   elem_type mask = bit_mask (bit_idx);
 189
 190   /* This is equivalent to `b->bits[idx] ^= mask' except that it
 191      is guaranteed to be atomic on a uniprocessor machine.  See
 192      the description of the XOR instruction in [IA32-v2b]. */
 193   asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
 194 }
 195
 196 /* Returns the value of the bit numbered IDX in B. */
 197 bool
 198 bitmap_test (const struct bitmap *b, size_t idx)
 199 {
 200   ASSERT (b != NULL);
 201   ASSERT (idx < b->bit_cnt);
 202   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 203 }
 204 \f
 205 /* Setting and testing multiple bits. */
 206
 207 /* Sets all bits in B to VALUE. */
 208 void
 209 bitmap_set_all (struct bitmap *b, bool value)
 210 {
 211   ASSERT (b != NULL);
 212
 213   bitmap_set_multiple (b, 0, bitmap_size (b), value);
 214 }
 215
 216 /* Sets the CNT bits starting at START in B to VALUE. */
 217 void
 218 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
 219 {
 220   size_t i;
 221
 222   ASSERT (b != NULL);
 223   ASSERT (start <= b->bit_cnt);
 224   ASSERT (start + cnt <= b->bit_cnt);
 225
 226   for (i = 0; i < cnt; i++)
 227     bitmap_set (b, start + i, value);
 228 }
 229
 230 /* Returns the number of bits in B between START and START + CNT,
 231    exclusive, that are set to VALUE. */
 232 size_t
 233 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
 234 {
 235   size_t i, value_cnt;
 236
 237   ASSERT (b != NULL);
 238   ASSERT (start <= b->bit_cnt);
 239   ASSERT (start + cnt <= b->bit_cnt);
 240
 241   value_cnt = 0;
 242   for (i = 0; i < cnt; i++)
 243     if (bitmap_test (b, start + i) == value)
 244       value_cnt++;
 245   return value_cnt;
 246 }
 247
 248 /* Returns true if any bits in B between START and START + CNT,
 249    exclusive, are set to VALUE, and false otherwise. */
 250 bool
 251 bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
 252 {
 253   size_t i;
 254
 255   ASSERT (b != NULL);
 256   ASSERT (start <= b->bit_cnt);
 257   ASSERT (start + cnt <= b->bit_cnt);
 258
 259   for (i = 0; i < cnt; i++)
 260     if (bitmap_test (b, start + i) == value)
 261       return true;
 262   return false;
 263 }
 264
 265 /* Returns true if any bits in B between START and START + CNT,
 266    exclusive, are set to true, and false otherwise.*/
 267 bool
 268 bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
 269 {
 270   return bitmap_contains (b, start, cnt, true);
 271 }
 272
 273 /* Returns true if no bits in B between START and START + CNT,
 274    exclusive, are set to true, and false otherwise.*/
 275 bool
 276 bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
 277 {
 278   return !bitmap_contains (b, start, cnt, true);
 279 }
 280
 281 /* Returns true if every bit in B between START and START + CNT,
 282    exclusive, is set to true, and false otherwise. */
 283 bool
 284 bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
 285 {
 286   return !bitmap_contains (b, start, cnt, false);
 287 }
 288 \f
 289 /* Finding set or unset bits. */
 290
 291 /* Finds and returns the starting index of the first group of CNT
 292    consecutive bits in B at or after START that are all set to
 293    VALUE.
 294    If there is no such group, returns BITMAP_ERROR. */
 295 size_t
 296 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
 297 {
 298   ASSERT (b != NULL);
 299   ASSERT (start <= b->bit_cnt);
 300
 301   if (cnt <= b->bit_cnt)
 302     {
 303       size_t last = b->bit_cnt - cnt;
 304       size_t i;
 305       for (i = start; i <= last; i++)
 306         if (!bitmap_contains (b, i, cnt, !value))
 307           return i;
 308     }
 309   return BITMAP_ERROR;
 310 }
 311
 312 /* Finds the first group of CNT consecutive bits in B at or after
 313    START that are all set to VALUE, flips them all to !VALUE,
 314    and returns the index of the first bit in the group.
 315    If there is no such group, returns BITMAP_ERROR.
 316    If CNT is zero, returns 0.
 317    Bits are set atomically, but testing bits is not atomic with
 318    setting them. */
 319 size_t
 320 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
 321 {
 322   size_t idx = bitmap_scan (b, start, cnt, value);
 323   if (idx != BITMAP_ERROR)
 324     bitmap_set_multiple (b, idx, cnt, !value);
 325   return idx;
 326 }
 327 \f
 328 /* File input and output. */
 329
 330 #ifdef FILESYS
 331 /* Returns the number of bytes needed to store B in a file. */
 332 size_t
 333 bitmap_file_size (const struct bitmap *b)
 334 {
 335   return byte_cnt (b->bit_cnt);
 336 }
 337
 338 /* Reads B from FILE.  Returns true if successful, false
 339    otherwise. */
 340 bool
 341 bitmap_read (struct bitmap *b, struct file *file)
 342 {
 343   bool success = true;
 344   if (b->bit_cnt > 0)
 345     {
 346       off_t size = byte_cnt (b->bit_cnt);
 347       success = file_read_at (file, b->bits, size, 0) == size;
 348       b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
 349     }
 350   return success;
 351 }
 352
 353 /* Writes B to FILE.  Return true if successful, false
 354    otherwise. */
 355 bool
 356 bitmap_write (const struct bitmap *b, struct file *file)
 357 {
 358   off_t size = byte_cnt (b->bit_cnt);
 359   return file_write_at (file, b->bits, size, 0) == size;
 360 }
 361 #endif /* FILESYS */
 362 \f
 363 /* Debugging. */
 364
 365 /* Dumps the contents of B to the console as hexadecimal. */
 366 void
 367 bitmap_dump (const struct bitmap *b)
 368 {
 369   hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
 370 }
 371