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    If CNT is zero, returns 0.
 231    Bits are set atomically, but testing bits is not atomic with
 232    setting them. */
 233 size_t
 234 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
 235 {
 236   size_t idx = bitmap_scan (b, start, cnt, value);
 237   if (idx != BITMAP_ERROR)
 238     bitmap_set_multiple (b, idx, idx + cnt, !value);
 239   return idx;
 240 }
 241
 242 /* Returns the number of bits in B between START and END,
 243    exclusive, that are set to VALUE. */
 244 size_t
 245 bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value)
 246 {
 247   size_t idx, cnt;
 248
 249   ASSERT (b != NULL);
 250   ASSERT (start <= end);
 251   ASSERT (end <= b->bit_cnt);
 252
 253   cnt = 0;
 254   for (idx = start; idx < end; idx++)
 255     cnt += bitmap_test (b, idx) == value;
 256   return cnt;
 257 }
 258
 259 /* Returns true if any bits in B between START and END,
 260    exclusive, are set to true, and false otherwise.*/
 261 bool
 262 bitmap_any (const struct bitmap *b, size_t start, size_t end)
 263 {
 264   return contains (b, start, end, true);
 265 }
 266
 267 /* Returns true if no bits in B between START and END, exclusive,
 268    are set to true, and false otherwise.*/
 269 bool
 270 bitmap_none (const struct bitmap *b, size_t start, size_t end)
 271 {
 272   return !contains (b, start, end, true);
 273 }
 274
 275 /* Returns true if every bit in B between START and END,
 276    exclusive, is set to true, and false otherwise. */
 277 bool
 278 bitmap_all (const struct bitmap *b, size_t start, size_t end)
 279 {
 280   return !contains (b, start, end, 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);
 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), 0);
 298       b->bits[elem_cnt (b) - 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), 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), 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   struct bitmap b;
 323   b.bit_cnt = bit_cnt;
 324   return byte_cnt (&b) + sizeof b;
 325 }
 326
 327 /* Creates and returns a bitmap with BIT_CNT bits in the
 328    BLOCK_SIZE bytes of storage preallocated at BLOCK.
 329    BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
 330 struct bitmap *
 331 bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
 332 {
 333   struct bitmap *b = block;
 334
 335   ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
 336
 337   b->bit_cnt = bit_cnt;
 338   b->bits = (elem_type *) (b + 1);
 339   bitmap_set_all (b, false);
 340   return b;
 341 }
 342