#include "bitmap.h"
#include <debug.h>
#include <limits.h>
+#include <random.h>
#include <round.h>
#include <stdio.h>
#include "threads/malloc.h"
#include "filesys/file.h"
#endif
\f
+/* Element type.
+
+ This must be an unsigned integer type at least as wide as int.
+
+ Each bit represents one bit in the bitmap.
+ If bit 0 in an element represents bit K in the bitmap,
+ then bit 1 in the element represents bit K+1 in the bitmap,
+ and so on. */
+typedef unsigned long elem_type;
+
/* Number of bits in an element. */
#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
+/* From the outside, a bitmap is an array of bits. From the
+ inside, it's an array of elem_type (defined above) that
+ simulates an array of bits. */
+struct bitmap
+ {
+ size_t bit_cnt; /* Number of bits. */
+ elem_type *bits; /* Elements that represent bits. */
+ };
+
/* Returns the index of the element that contains the bit
numbered BIT_IDX. */
static inline size_t
return (elem_type) 1 << (bit_idx % ELEM_BITS);
}
-/* Returns the number of elements required for B's bits. */
+/* Returns the number of elements required for BIT_CNT bits. */
static inline size_t
-elem_cnt (const struct bitmap *b)
+elem_cnt (size_t bit_cnt)
{
- return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
+ return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
}
-/* Returns the number of bytes required by B's elements. */
+/* Returns the number of bytes required for BIT_CNT bits. */
static inline size_t
-byte_cnt (const struct bitmap *b)
+byte_cnt (size_t bit_cnt)
{
- return sizeof (elem_type) * elem_cnt (b);
+ return sizeof (elem_type) * elem_cnt (bit_cnt);
}
/* Returns a bit mask in which the bits actually used in the last
return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
}
\f
-/* Initializes B to be a bitmap of BIT_CNT bits.
- Returns true if successfalse, false if memory allocation
+/* Creation and destruction. */
+
+/* Initializes B to be a bitmap of BIT_CNT bits
+ and sets all of its bits to false.
+ Returns true if success, false if memory allocation
failed. */
-bool
-bitmap_init (struct bitmap *b, size_t bit_cnt)
+struct bitmap *
+bitmap_create (size_t bit_cnt)
{
- b->bit_cnt = bit_cnt;
- b->bits = malloc (byte_cnt (b));
- if (b->bits == NULL && bit_cnt > 0)
- return false;
+ struct bitmap *b = malloc (sizeof *b);
+ if (b != NULL)
+ {
+ b->bit_cnt = bit_cnt;
+ b->bits = malloc (byte_cnt (bit_cnt));
+ if (b->bits != NULL || bit_cnt == 0)
+ {
+ bitmap_set_all (b, false);
+ return b;
+ }
+ free (b);
+ }
+ return NULL;
+}
+/* Creates and returns a bitmap with BIT_CNT bits in the
+ BLOCK_SIZE bytes of storage preallocated at BLOCK.
+ BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
+struct bitmap *
+bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
+{
+ struct bitmap *b = block;
+
+ ASSERT (block_size >= bitmap_buf_size (bit_cnt));
+
+ b->bit_cnt = bit_cnt;
+ b->bits = (elem_type *) (b + 1);
bitmap_set_all (b, false);
- return true;
+ return b;
+}
+
+/* Returns the number of bytes required to accomodate a bitmap
+ with BIT_CNT bits (for use with bitmap_create_in_buf()). */
+size_t
+bitmap_buf_size (size_t bit_cnt)
+{
+ return sizeof (struct bitmap) + byte_cnt (bit_cnt);
}
-/* Destroys bitmap B, freeing its storage. */
+/* Destroys bitmap B, freeing its storage.
+ Not for use on bitmaps created by
+ bitmap_create_preallocated(). */
void
bitmap_destroy (struct bitmap *b)
{
- ASSERT (b);
-
- free (b->bits);
+ if (b != NULL)
+ {
+ free (b->bits);
+ free (b);
+ }
}
+\f
+/* Bitmap size. */
/* Returns the number of bits in B. */
size_t
{
return b->bit_cnt;
}
+\f
+/* Setting and testing single bits. */
-/* Sets the bit numbered IDX in B to VALUE. */
+/* Atomically sets the bit numbered IDX in B to VALUE. */
void
bitmap_set (struct bitmap *b, size_t idx, bool value)
{
ASSERT (b != NULL);
ASSERT (idx < b->bit_cnt);
if (value)
- b->bits[elem_idx (idx)] |= bit_mask (idx);
+ bitmap_mark (b, idx);
else
- b->bits[elem_idx (idx)] &= ~bit_mask (idx);
+ bitmap_reset (b, idx);
}
-/* Sets all bits in B to VALUE. */
+/* Atomically sets the bit numbered BIT_IDX in B to true. */
void
-bitmap_set_all (struct bitmap *b, bool value)
+bitmap_mark (struct bitmap *b, size_t bit_idx)
{
- size_t i;
-
- ASSERT (b != NULL);
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
- if (b->bit_cnt > 0)
- {
- for (i = 0; i < elem_cnt (b); i++)
- b->bits[i] = value ? (elem_type) -1 : 0;
- b->bits[elem_cnt (b) - 1] &= last_mask (b);
- }
+ /* This is equivalent to `b->bits[idx] |= mask' except that it
+ is guaranteed to be atomic on a uniprocessor machine. See
+ the description of the OR instruction in [IA32-v2b]. */
+ asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
-/* Sets the bit numbered IDX in B to true. */
+/* Atomically sets the bit numbered BIT_IDX in B to false. */
void
-bitmap_mark (struct bitmap *b, size_t idx)
+bitmap_reset (struct bitmap *b, size_t bit_idx)
{
- bitmap_set (b, idx, true);
-}
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
-/* Sets the bit numbered IDX in B to false. */
-void
-bitmap_reset (struct bitmap *b, size_t idx)
-{
- bitmap_set (b, idx, false);
+ /* This is equivalent to `b->bits[idx] &= ~mask' except that it
+ is guaranteed to be atomic on a uniprocessor machine. See
+ the description of the AND instruction in [IA32-v2a]. */
+ asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
}
-/* Toggles the bit numbered IDX in B;
+/* Atomically toggles the bit numbered IDX in B;
that is, if it is true, makes it false,
and if it is false, makes it true. */
void
-bitmap_flip (struct bitmap *b, size_t idx)
+bitmap_flip (struct bitmap *b, size_t bit_idx)
{
- ASSERT (b != NULL);
- ASSERT (idx < b->bit_cnt);
- b->bits[elem_idx (idx)] ^= bit_mask (idx);
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
+
+ /* This is equivalent to `b->bits[idx] ^= mask' except that it
+ is guaranteed to be atomic on a uniprocessor machine. See
+ the description of the XOR instruction in [IA32-v2b]. */
+ asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
/* Returns the value of the bit numbered IDX in B. */
ASSERT (idx < b->bit_cnt);
return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}
+\f
+/* Setting and testing multiple bits. */
-/* Returns the smallest index of a bit set to VALUE in B.
- If no bits in B are set to VALUE, returns BITMAP_ERROR. */
-size_t
-bitmap_scan (const struct bitmap *b, bool value)
+/* Sets all bits in B to VALUE. */
+void
+bitmap_set_all (struct bitmap *b, bool value)
{
- elem_type ignore = value ? 0 : (elem_type) -1;
- size_t idx;
-
ASSERT (b != NULL);
- for (idx = 0; idx < elem_cnt (b); idx++)
- {
- elem_type e = b->bits[idx];
- if (e != ignore)
- {
- idx *= ELEM_BITS;
-
- while ((e & 1) != value)
- {
- e >>= 1;
- idx++;
- }
- return idx < b->bit_cnt ? idx : BITMAP_ERROR;
- }
- }
- return BITMAP_ERROR;
+ bitmap_set_multiple (b, 0, bitmap_size (b), value);
}
-/* Finds the smallest index of a bit set to false in B,
- sets it to true, and returns the index.
- If no bits in B are set to false, changes no bits and
- returns BITMAP_ERROR. */
-size_t
-bitmap_find_and_set (struct bitmap *b)
+/* Sets the CNT bits starting at START in B to VALUE. */
+void
+bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
{
- size_t idx = bitmap_scan (b, false);
- if (idx != BITMAP_ERROR)
- bitmap_mark (b, idx);
- return idx;
-}
+ size_t i;
+
+ ASSERT (b != NULL);
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
-/* Finds the smallest index of a bit set to true in B,
- sets it to false, and returns the index.
- If no bits in B are set to true, changes no bits and
- returns BITMAP_ERROR. */
-size_t
-bitmap_find_and_clear (struct bitmap *b)
-{
- size_t idx = bitmap_scan (b, true);
- if (idx != BITMAP_ERROR)
- bitmap_reset (b, idx);
- return idx;
+ for (i = 0; i < cnt; i++)
+ bitmap_set (b, start + i, value);
}
-/* Returns the number of bits in B set to true. */
+/* Returns the number of bits in B between START and START + CNT,
+ exclusive, that are set to VALUE. */
size_t
-bitmap_set_cnt (const struct bitmap *b)
+bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
- size_t cnt;
- size_t i;
+ size_t i, value_cnt;
ASSERT (b != NULL);
- cnt = 0;
- for (i = 0; i < elem_cnt (b); i++)
- {
- elem_type e = b->bits[i];
- while (e != 0)
- {
- cnt++;
- e &= e - 1;
- }
- }
- return cnt;
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
+
+ value_cnt = 0;
+ for (i = 0; i < cnt; i++)
+ if (bitmap_test (b, start + i) == value)
+ value_cnt++;
+ return value_cnt;
}
-/* Returns true if any bits in B are set to true,
- and false otherwise.*/
+/* Returns true if any bits in B between START and START + CNT,
+ exclusive, are set to VALUE, and false otherwise. */
bool
-bitmap_any (const struct bitmap *b)
+bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
size_t i;
-
+
ASSERT (b != NULL);
- for (i = 0; i < elem_cnt (b); i++)
- if (b->bits[i])
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
+
+ for (i = 0; i < cnt; i++)
+ if (bitmap_test (b, start + i) == value)
return true;
return false;
}
-/* Returns the number of bits in B set to false. */
+/* Returns true if any bits in B between START and START + CNT,
+ exclusive, are set to true, and false otherwise.*/
bool
-bitmap_clear_cnt (const struct bitmap *b)
+bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
{
- return b->bit_cnt - bitmap_set_cnt (b);
+ return bitmap_contains (b, start, cnt, true);
}
-/* Returns true if no bits in B are set to true,
- and false otherwise.*/
+/* Returns true if no bits in B between START and START + CNT,
+ exclusive, are set to true, and false otherwise.*/
bool
-bitmap_none (const struct bitmap *b)
+bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
{
- return !bitmap_any (b);
+ return !bitmap_contains (b, start, cnt, true);
}
-/* Returns true if every bit in B is set to true,
- and false otherwise. */
+/* Returns true if every bit in B between START and START + CNT,
+ exclusive, is set to true, and false otherwise. */
bool
-bitmap_all (const struct bitmap *b)
+bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
{
- size_t i;
+ return !bitmap_contains (b, start, cnt, false);
+}
+\f
+/* Finding set or unset bits. */
+/* Finds and returns the starting index of a group of CNT
+ consecutive bits in B at or after START that are all set to
+ VALUE.
+ If there is no such group, returns BITMAP_ERROR. */
+size_t
+bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
+{
ASSERT (b != NULL);
+ ASSERT (start <= b->bit_cnt);
- if (b->bit_cnt == 0)
- return true;
-
- for (i = 0; i < elem_cnt (b) - 1; i++)
- if (b->bits[i] != (elem_type) -1)
- return false;
- return b->bits[i] == last_mask (b);
+ if (cnt <= b->bit_cnt)
+ {
+ size_t last = b->bit_cnt - cnt;
+ size_t middle = start + random_ulong () % (last - start + 1);
+ size_t i = middle;
+ do
+ {
+ if (!bitmap_contains (b, i, cnt, !value))
+ return i;
+ i = i != last ? i + 1 : start;
+ }
+ while (i != middle);
+ }
+ return BITMAP_ERROR;
+}
+
+/* Finds a group of CNT consecutive bits in B at or after
+ START that are all set to VALUE, flips them all to !VALUE,
+ and returns the index of the first bit in the group.
+ If there is no such group, returns BITMAP_ERROR.
+ If CNT is zero, returns 0.
+ Bits are set atomically, but testing bits is not atomic with
+ setting them. */
+size_t
+bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
+{
+ size_t idx = bitmap_scan (b, start, cnt, value);
+ if (idx != BITMAP_ERROR)
+ bitmap_set_multiple (b, idx, cnt, !value);
+ return idx;
}
+\f
+/* File input and output. */
#ifdef FILESYS
/* Returns the number of bytes needed to store B in a file. */
size_t
bitmap_file_size (const struct bitmap *b)
{
- return byte_cnt (b);
+ return byte_cnt (b->bit_cnt);
}
-/* Reads FILE into B, ignoring errors. */
-void
+/* Reads B from FILE. Returns true if successful, false
+ otherwise. */
+bool
bitmap_read (struct bitmap *b, struct file *file)
{
+ bool success = true;
if (b->bit_cnt > 0)
{
- file_read_at (file, b->bits, byte_cnt (b), 0);
- b->bits[elem_cnt (b) - 1] &= last_mask (b);
+ off_t size = byte_cnt (b->bit_cnt);
+ success = file_read_at (file, b->bits, size, 0) == size;
+ b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
}
+ return success;
}
-/* Writes FILE to B, ignoring errors. */
-void
+/* Writes B to FILE. Return true if successful, false
+ otherwise. */
+bool
bitmap_write (const struct bitmap *b, struct file *file)
{
- file_write_at (file, b->bits, byte_cnt (b), 0);
+ off_t size = byte_cnt (b->bit_cnt);
+ return file_write_at (file, b->bits, size, 0) == size;
}
#endif /* FILESYS */
+\f
+/* Debugging. */
/* Dumps the contents of B to the console as hexadecimal. */
void
bitmap_dump (const struct bitmap *b)
{
- hex_dump (b->bits, byte_cnt (b), false);
+ hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
}
+