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 /* Initializes B to be a bitmap of BIT_CNT bits
  73    and sets all of its bits to false.
  74    Returns true if success, false if memory allocation
  75    failed. */
  76 struct bitmap *
  77 bitmap_create (size_t bit_cnt)
  78 {
  79   struct bitmap *b = malloc (sizeof *b);
  80   if (b != NULL)
  81     {
  82       b->bit_cnt = bit_cnt;
  83       b->bits = malloc (byte_cnt (bit_cnt));
  84       if (b->bits != NULL || bit_cnt == 0)
  85         {
  86           bitmap_set_all (b, false);
  87           return b;
  88         }
  89       free (b);
  90     }
  91   return NULL;
  92 }
  93
  94 /* Destroys bitmap B, freeing its storage.
  95    Not for use on bitmaps created by
  96    bitmap_create_preallocated(). */
  97 void
  98 bitmap_destroy (struct bitmap *b)
  99 {
 100   if (b != NULL)
 101     {
 102       free (b->bits);
 103       free (b);
 104     }
 105 }
 106
 107 /* Returns the number of bits in B. */
 108 size_t
 109 bitmap_size (const struct bitmap *b)
 110 {
 111   return b->bit_cnt;
 112 }
 113
 114 /* Atomically sets the bit numbered IDX in B to VALUE. */
 115 void
 116 bitmap_set (struct bitmap *b, size_t idx, bool value)
 117 {
 118   ASSERT (b != NULL);
 119   ASSERT (idx < b->bit_cnt);
 120   if (value)
 121     bitmap_mark (b, idx);
 122   else
 123     bitmap_reset (b, idx);
 124 }
 125
 126 /* Sets all bits in B to VALUE. */
 127 void
 128 bitmap_set_all (struct bitmap *b, bool value)
 129 {
 130   ASSERT (b != NULL);
 131
 132   bitmap_set_multiple (b, 0, bitmap_size (b), value);
 133 }
 134
 135 /* Sets the CNT bits starting at START in B to VALUE. */
 136 void
 137 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
 138 {
 139   size_t i;
 140
 141   ASSERT (b != NULL);
 142   ASSERT (start <= b->bit_cnt);
 143   ASSERT (start + cnt <= b->bit_cnt);
 144
 145   for (i = 0; i < cnt; i++)
 146     bitmap_set (b, start + i, value);
 147 }
 148
 149 /* Atomically sets the bit numbered BIT_IDX in B to true. */
 150 void
 151 bitmap_mark (struct bitmap *b, size_t bit_idx)
 152 {
 153   size_t idx = elem_idx (bit_idx);
 154   elem_type mask = bit_mask (bit_idx);
 155
 156   /* This is equivalent to `b->bits[idx] |= mask' except that it
 157      is guaranteed to be atomic on a uniprocessor machine.  See
 158      the description of the OR instruction in [IA32-v2b]. */
 159   asm ("or %0, %1" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
 160 }
 161
 162 /* Atomically sets the bit numbered BIT_IDX in B to false. */
 163 void
 164 bitmap_reset (struct bitmap *b, size_t bit_idx)
 165 {
 166   size_t idx = elem_idx (bit_idx);
 167   elem_type mask = bit_mask (bit_idx);
 168
 169   /* This is equivalent to `b->bits[idx] &= ~mask' except that it
 170      is guaranteed to be atomic on a uniprocessor machine.  See
 171      the description of the AND instruction in [IA32-v2a]. */
 172   asm ("and %0, %1" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
 173 }
 174
 175 /* Atomically toggles the bit numbered IDX in B;
 176    that is, if it is true, makes it false,
 177    and if it is false, makes it true. */
 178 void
 179 bitmap_flip (struct bitmap *b, size_t bit_idx)
 180 {
 181   size_t idx = elem_idx (bit_idx);
 182   elem_type mask = bit_mask (bit_idx);
 183
 184   /* This is equivalent to `b->bits[idx] ^= mask' except that it
 185      is guaranteed to be atomic on a uniprocessor machine.  See
 186      the description of the XOR instruction in [IA32-v2b]. */
 187   asm ("xor %0, %1" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
 188 }
 189
 190 /* Returns the value of the bit numbered IDX in B. */
 191 bool
 192 bitmap_test (const struct bitmap *b, size_t idx)
 193 {
 194   ASSERT (b != NULL);
 195   ASSERT (idx < b->bit_cnt);
 196   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 197 }
 198
 199 /* Returns true if any of the CNT bits starting at START is set
 200    to VALUE. */
 201 static bool
 202 contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
 203 {
 204   size_t i;
 205
 206   ASSERT (b != NULL);
 207   ASSERT (start <= b->bit_cnt);
 208   ASSERT (start + cnt <= b->bit_cnt);
 209
 210   for (i = 0; i < cnt; i++)
 211     if (bitmap_test (b, start + i) == value)
 212       return true;
 213   return false;
 214 }
 215
 216 /* Finds and returns the starting index of the first group of CNT
 217    consecutive bits in B at or after START that are all set to
 218    VALUE.
 219    If there is no such group, returns BITMAP_ERROR. */
 220 size_t
 221 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
 222 {
 223   ASSERT (b != NULL);
 224   ASSERT (start <= b->bit_cnt);
 225
 226   if (cnt <= b->bit_cnt)
 227     {
 228       size_t last = b->bit_cnt - cnt;
 229       size_t i;
 230       for (i = start; i <= last; i++)
 231         if (!contains (b, i, cnt, !value))
 232           return i;
 233     }
 234   return BITMAP_ERROR;
 235 }
 236
 237 /* Finds the first group of CNT consecutive bits in B at or after
 238    START that are all set to VALUE, flips them all to !VALUE,
 239    and returns the index of the first bit in the group.
 240    If there is no such group, returns BITMAP_ERROR.
 241    If CNT is zero, returns 0.
 242    Bits are set atomically, but testing bits is not atomic with
 243    setting them. */
 244 size_t
 245 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
 246 {
 247   size_t idx = bitmap_scan (b, start, cnt, value);
 248   if (idx != BITMAP_ERROR)
 249     bitmap_set_multiple (b, idx, cnt, !value);
 250   return idx;
 251 }
 252
 253 /* Returns the number of bits in B between START and START + CNT,
 254    exclusive, that are set to VALUE. */
 255 size_t
 256 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
 257 {
 258   size_t i, value_cnt;
 259
 260   ASSERT (b != NULL);
 261   ASSERT (start <= b->bit_cnt);
 262   ASSERT (start + cnt <= b->bit_cnt);
 263
 264   value_cnt = 0;
 265   for (i = 0; i < cnt; i++)
 266     if (bitmap_test (b, start + i) == value)
 267       value_cnt++;
 268   return value_cnt;
 269 }
 270
 271 /* Returns true if any bits in B between START and START + CNT,
 272    exclusive, are set to true, and false otherwise.*/
 273 bool
 274 bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
 275 {
 276   return contains (b, start, cnt, true);
 277 }
 278
 279 /* Returns true if no bits in B between START and START + CNT,
 280    exclusive, are set to true, and false otherwise.*/
 281 bool
 282 bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
 283 {
 284   return !contains (b, start, cnt, true);
 285 }
 286
 287 /* Returns true if every bit in B between START and START + CNT,
 288    exclusive, is set to true, and false otherwise. */
 289 bool
 290 bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
 291 {
 292   return !contains (b, start, cnt, false);
 293 }
 294
 295 #ifdef FILESYS
 296 /* Returns the number of bytes needed to store B in a file. */
 297 size_t
 298 bitmap_file_size (const struct bitmap *b)
 299 {
 300   return byte_cnt (b->bit_cnt);
 301 }
 302
 303 /* Reads FILE into B, ignoring errors. */
 304 void
 305 bitmap_read (struct bitmap *b, struct file *file)
 306 {
 307   if (b->bit_cnt > 0)
 308     {
 309       file_read_at (file, b->bits, byte_cnt (b->bit_cnt), 0);
 310       b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
 311     }
 312 }
 313
 314 /* Writes FILE to B, ignoring errors. */
 315 void
 316 bitmap_write (const struct bitmap *b, struct file *file)
 317 {
 318   file_write_at (file, b->bits, byte_cnt (b->bit_cnt), 0);
 319 }
 320 #endif /* FILESYS */
 321
 322 /* Dumps the contents of B to the console as hexadecimal. */
 323 void
 324 bitmap_dump (const struct bitmap *b)
 325 {
 326   hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
 327 }
 328
 329 /* Returns the number of bytes required to accomodate a bitmap
 330    with BIT_CNT bits. */
 331 size_t
 332 bitmap_needed_bytes (size_t bit_cnt)
 333 {
 334   return sizeof (struct bitmap) + byte_cnt (bit_cnt);
 335 }
 336
 337 /* Creates and returns a bitmap with BIT_CNT bits in the
 338    BLOCK_SIZE bytes of storage preallocated at BLOCK.
 339    BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
 340 struct bitmap *
 341 bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
 342 {
 343   struct bitmap *b = block;
 344
 345   ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
 346
 347   b->bit_cnt = bit_cnt;
 348   b->bits = (elem_type *) (b + 1);
 349   bitmap_set_all (b, false);
 350   return b;
 351 }
 352