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