Fix comment.

[pintos-anon] / src / lib / kernel / bitmap.c

diff --git a/src/lib/kernel/bitmap.c b/src/lib/kernel/bitmap.c
index df23cc34c1b8c9dddf86d8cc3796904838e36dac..77edf2270b35435538fbbb5adeec52096403f50b 100644 (file)
--- 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"
@@ -163,7 +164,7 @@ bitmap_mark (struct bitmap *b, size_t 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 OR instruction in [IA32-v2b]. */
-  asm ("or %0, %1" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
+  asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
 }
 
 /* Atomically sets the bit numbered BIT_IDX in B to false. */
@@ -176,7 +177,7 @@ bitmap_reset (struct bitmap *b, size_t 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 AND instruction in [IA32-v2a]. */
-  asm ("and %0, %1" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
+  asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
 }
 
 /* Atomically toggles the bit numbered IDX in B;
@@ -191,7 +192,7 @@ bitmap_flip (struct bitmap *b, size_t 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 ("xor %0, %1" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
+  asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
 }
 
 /* Returns the value of the bit numbered IDX in B. */
@@ -289,7 +290,7 @@ bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
 \f
 /* Finding set or unset bits. */
 
-/* Finds and returns the starting index of the first group of CNT
+/* 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. */
@@ -302,15 +303,20 @@ bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
   if (cnt <= b->bit_cnt) 
     {
       size_t last = b->bit_cnt - cnt;
-      size_t i;
-      for (i = start; i <= last; i++)
-        if (!bitmap_contains (b, i, cnt, !value))
-          return i; 
+      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 the first group of CNT consecutive bits in B at or after
+/* 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.