X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flib%2Fkernel%2Fbitmap.c;h=77edf2270b35435538fbbb5adeec52096403f50b;hb=468f548e6848498767eb6ac7b55ab9bca06de462;hp=9dfded55b64578dce328c53ea6fd2da7275777ff;hpb=9818aeac330907b5b314ac58c861d3dba8b15e5e;p=pintos-anon

diff --git a/src/lib/kernel/bitmap.c b/src/lib/kernel/bitmap.c
index 9dfded5..77edf22 100644
--- a/src/lib/kernel/bitmap.c
+++ b/src/lib/kernel/bitmap.c
@@ -1,6 +1,7 @@
 #include "bitmap.h"
 #include <debug.h>
 #include <limits.h>
+#include <random.h>
 #include <round.h>
 #include <stdio.h>
 #include "threads/malloc.h"
@@ -69,6 +70,8 @@ last_mask (const struct bitmap *b)
   return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
 }
 
+/* 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
@@ -91,6 +94,30 @@ bitmap_create (size_t bit_cnt)
   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 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.
    Not for use on bitmaps created by
    bitmap_create_preallocated(). */
@@ -103,6 +130,8 @@ bitmap_destroy (struct bitmap *b)
       free (b);
     }
 }
+
+/* Bitmap size. */
 
 /* Returns the number of bits in B. */
 size_t
@@ -110,6 +139,8 @@ bitmap_size (const struct bitmap *b)
 {
   return b->bit_cnt;
 }
+
+/* Setting and testing single bits. */
 
 /* Atomically sets the bit numbered IDX in B to VALUE. */
 void
@@ -123,29 +154,6 @@ bitmap_set (struct bitmap *b, size_t idx, bool value)
     bitmap_reset (b, idx);
 }
 
-/* Sets all bits in B to VALUE. */
-void
-bitmap_set_all (struct bitmap *b, bool value) 
-{
-  ASSERT (b != NULL);
-
-  bitmap_set_multiple (b, 0, bitmap_size (b), value);
-}
-
-/* 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 i;
-  
-  ASSERT (b != NULL);
-  ASSERT (start <= b->bit_cnt);
-  ASSERT (start + cnt <= b->bit_cnt);
-
-  for (i = 0; i < cnt; i++)
-    bitmap_set (b, start + i, value);
-}
-
 /* Atomically sets the bit numbered BIT_IDX in B to true. */
 void
 bitmap_mark (struct bitmap *b, size_t bit_idx) 
@@ -195,59 +203,30 @@ bitmap_test (const struct bitmap *b, size_t idx)
   ASSERT (idx < b->bit_cnt);
   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
 }
+
+/* Setting and testing multiple bits. */
 
-/* Returns true if any of the CNT bits starting at START is set
-   to VALUE. */
-static bool
-contains (const struct bitmap *b, size_t start, size_t cnt, bool value) 
+/* Sets all bits in B to VALUE. */
+void
+bitmap_set_all (struct bitmap *b, bool value) 
 {
-  size_t i;
-  
   ASSERT (b != NULL);
-  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;
+  bitmap_set_multiple (b, 0, bitmap_size (b), value);
 }
 
-/* Finds and returns the starting index of the first 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) 
+/* 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 i;
+  
   ASSERT (b != NULL);
   ASSERT (start <= b->bit_cnt);
+  ASSERT (start + cnt <= b->bit_cnt);
 
-  if (cnt <= b->bit_cnt) 
-    {
-      size_t last = b->bit_cnt - cnt;
-      size_t i;
-      for (i = start; i <= last; i++)
-        if (!contains (b, i, cnt, !value))
-          return i; 
-    }
-  return BITMAP_ERROR;
-}
-
-/* Finds the first 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;
+  for (i = 0; i < cnt; i++)
+    bitmap_set (b, start + i, value);
 }
 
 /* Returns the number of bits in B between START and START + CNT,
@@ -268,12 +247,29 @@ bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
   return value_cnt;
 }
 
+/* Returns true if any bits in B between START and START + CNT,
+   exclusive, are set to VALUE, and false otherwise. */
+bool
+bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value) 
+{
+  size_t i;
+  
+  ASSERT (b != NULL);
+  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 true if any bits in B between START and START + CNT,
    exclusive, are set to true, and false otherwise.*/
 bool
 bitmap_any (const struct bitmap *b, size_t start, size_t cnt) 
 {
-  return contains (b, start, cnt, true);
+  return bitmap_contains (b, start, cnt, true);
 }
 
 /* Returns true if no bits in B between START and START + CNT,
@@ -281,7 +277,7 @@ bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
 bool
 bitmap_none (const struct bitmap *b, size_t start, size_t cnt) 
 {
-  return !contains (b, start, cnt, true);
+  return !bitmap_contains (b, start, cnt, true);
 }
 
 /* Returns true if every bit in B between START and START + CNT,
@@ -289,9 +285,55 @@ bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
 bool
 bitmap_all (const struct bitmap *b, size_t start, size_t cnt) 
 {
-  return !contains (b, start, cnt, false);
+  return !bitmap_contains (b, start, cnt, false);
+}
+
+/* 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 (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;
+}
+
+/* File input and output. */
+
 #ifdef FILESYS
 /* Returns the number of bytes needed to store B in a file. */
 size_t
@@ -300,24 +342,32 @@ bitmap_file_size (const struct bitmap *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->bit_cnt), 0);
+      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->bit_cnt), 0);
+  off_t size = byte_cnt (b->bit_cnt);
+  return file_write_at (file, b->bits, size, 0) == size;
 }
 #endif /* FILESYS */
+
+/* Debugging. */
 
 /* Dumps the contents of B to the console as hexadecimal. */
 void
@@ -326,27 +376,3 @@ bitmap_dump (const struct bitmap *b)
   hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
 }
 
-/* Returns the number of bytes required to accomodate a bitmap
-   with BIT_CNT bits. */
-size_t
-bitmap_needed_bytes (size_t bit_cnt) 
-{
-  return sizeof (struct bitmap) + byte_cnt (bit_cnt);
-}
-
-/* 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_preallocated (size_t bit_cnt, void *block, size_t block_size) 
-{
-  struct bitmap *b = block;
-  
-  ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
-
-  b->bit_cnt = bit_cnt;
-  b->bits = (elem_type *) (b + 1);
-  bitmap_set_all (b, false);
-  return b;
-}
-