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 B's bits. */
  50 static inline size_t
  51 elem_cnt (const struct bitmap *b)
  52 {
  53   return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
  54 }
  55
  56 /* Returns the number of bytes required by B's elements. */
  57 static inline size_t
  58 byte_cnt (const struct bitmap *b)
  59 {
  60   return sizeof (elem_type) * elem_cnt (b);
  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 (b));
  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 /* 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     b->bits[elem_idx (idx)] |= bit_mask (idx);
 122   else
 123     b->bits[elem_idx (idx)] &= ~bit_mask (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 bits numbered START through END, exclusive, in B to
 136    VALUE. */
 137 void
 138 bitmap_set_multiple (struct bitmap *b, size_t start, size_t end, bool value)
 139 {
 140   size_t idx;
 141
 142   ASSERT (b != NULL);
 143   ASSERT (start <= end);
 144   ASSERT (end <= b->bit_cnt);
 145
 146   for (idx = start; idx < end; idx++)
 147     bitmap_set (b, idx, value);
 148 }
 149
 150 /* Atomically sets the bit numbered IDX in B to true. */
 151 void
 152 bitmap_mark (struct bitmap *b, size_t idx)
 153 {
 154   asm ("orl %1, %0"
 155        : "=m" (b->bits[elem_idx (idx)])
 156        : "r" (bit_mask (idx)));
 157 }
 158
 159 /* Atomically sets the bit numbered IDX in B to false. */
 160 void
 161 bitmap_reset (struct bitmap *b, size_t idx)
 162 {
 163   asm ("andl %1, %0"
 164        : "=m" (b->bits[elem_idx (idx)])
 165        : "r" (~bit_mask (idx)));
 166 }
 167
 168 /* Atomically toggles the bit numbered IDX in B;
 169    that is, if it is true, makes it false,
 170    and if it is false, makes it true. */
 171 void
 172 bitmap_flip (struct bitmap *b, size_t idx)
 173 {
 174   ASSERT (b != NULL);
 175   ASSERT (idx < b->bit_cnt);
 176   asm ("xorl %1, %0"
 177        : "=m" (b->bits[elem_idx (idx)])
 178        : "r" (bit_mask (idx)));
 179 }
 180
 181 /* Returns the value of the bit numbered IDX in B. */
 182 bool
 183 bitmap_test (const struct bitmap *b, size_t idx)
 184 {
 185   ASSERT (b != NULL);
 186   ASSERT (idx < b->bit_cnt);
 187   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 188 }
 189
 190 /* Returns true if any bit from START to END, exclusive, is set
 191    to VALUE. */
 192 static bool
 193 contains (const struct bitmap *b, size_t start, size_t end, bool value)
 194 {
 195   size_t idx;
 196
 197   ASSERT (b != NULL);
 198   ASSERT (start <= end);
 199   ASSERT (end <= b->bit_cnt);
 200
 201   for (idx = start; idx < end; idx++)
 202     if (bitmap_test (b, idx) == value)
 203       return true;
 204   return false;
 205 }
 206
 207 /* Finds and returns the starting index of the first group of CNT
 208    consecutive bits in B at or after START that are all set to
 209    VALUE.
 210    If there is no such group, returns BITMAP_ERROR. */
 211 size_t
 212 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
 213 {
 214   size_t idx, last;
 215
 216   ASSERT (b != NULL);
 217   ASSERT (start <= b->bit_cnt);
 218
 219   if (cnt <= b->bit_cnt)
 220     for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
 221       if (!contains (b, idx, idx + cnt, !value))
 222         return idx;
 223   return BITMAP_ERROR;
 224 }
 225
 226 /* Finds the first group of CNT consecutive bits in B at or after
 227    START that are all set to VALUE, flips them all to !VALUE,
 228    and returns the index of the first bit in the group.
 229    If there is no such group, returns BITMAP_ERROR.
 230    Bits are set atomically, but testing bits is not atomic with
 231    setting them. */
 232 size_t
 233 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
 234 {
 235   size_t idx = bitmap_scan (b, start, cnt, value);
 236   if (idx != BITMAP_ERROR)
 237     bitmap_set_multiple (b, idx, idx + cnt, !value);
 238   return idx;
 239 }
 240
 241 /* Returns the number of bits in B between START and END,
 242    exclusive, that are set to VALUE. */
 243 size_t
 244 bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value)
 245 {
 246   size_t idx, cnt;
 247
 248   ASSERT (b != NULL);
 249   ASSERT (start <= end);
 250   ASSERT (end <= b->bit_cnt);
 251
 252   cnt = 0;
 253   for (idx = start; idx < end; idx++)
 254     cnt += bitmap_test (b, idx) == value;
 255   return cnt;
 256 }
 257
 258 /* Returns true if any bits in B between START and END,
 259    exclusive, are set to true, and false otherwise.*/
 260 bool
 261 bitmap_any (const struct bitmap *b, size_t start, size_t end)
 262 {
 263   return contains (b, start, end, true);
 264 }
 265
 266 /* Returns true if no bits in B between START and END, exclusive,
 267    are set to true, and false otherwise.*/
 268 bool
 269 bitmap_none (const struct bitmap *b, size_t start, size_t end)
 270 {
 271   return !contains (b, start, end, true);
 272 }
 273
 274 /* Returns true if every bit in B between START and END,
 275    exclusive, is set to true, and false otherwise. */
 276 bool
 277 bitmap_all (const struct bitmap *b, size_t start, size_t end)
 278 {
 279   return !contains (b, start, end, false);
 280 }
 281
 282 #ifdef FILESYS
 283 /* Returns the number of bytes needed to store B in a file. */
 284 size_t
 285 bitmap_file_size (const struct bitmap *b)
 286 {
 287   return byte_cnt (b);
 288 }
 289
 290 /* Reads FILE into B, ignoring errors. */
 291 void
 292 bitmap_read (struct bitmap *b, struct file *file)
 293 {
 294   if (b->bit_cnt > 0)
 295     {
 296       file_read_at (file, b->bits, byte_cnt (b), 0);
 297       b->bits[elem_cnt (b) - 1] &= last_mask (b);
 298     }
 299 }
 300
 301 /* Writes FILE to B, ignoring errors. */
 302 void
 303 bitmap_write (const struct bitmap *b, struct file *file)
 304 {
 305   file_write_at (file, b->bits, byte_cnt (b), 0);
 306 }
 307 #endif /* FILESYS */
 308
 309 /* Dumps the contents of B to the console as hexadecimal. */
 310 void
 311 bitmap_dump (const struct bitmap *b)
 312 {
 313   hex_dump (0, b->bits, byte_cnt (b), false);
 314 }
 315
 316 /* Returns the number of bytes required to accomodate a bitmap
 317    with BIT_CNT bits. */
 318 size_t
 319 bitmap_needed_bytes (size_t bit_cnt)
 320 {
 321   struct bitmap b;
 322   b.bit_cnt = bit_cnt;
 323   return byte_cnt (&b) + sizeof b;
 324 }
 325
 326 /* Creates and returns a bitmap with BIT_CNT bits in the
 327    BLOCK_SIZE bytes of storage preallocated at BLOCK.
 328    BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
 329 struct bitmap *
 330 bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
 331 {
 332   struct bitmap *b = block;
 333
 334   ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
 335
 336   b->bit_cnt = bit_cnt;
 337   b->bits = (elem_type *) (b + 1);
 338   bitmap_set_all (b, false);
 339   return b;
 340 }
 341