From 468f548e6848498767eb6ac7b55ab9bca06de462 Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
Date: Thu, 18 May 2006 19:02:35 +0000
Subject: [PATCH] Randomize the bits that bitmap_scan() returns, to make
 student errors that assume contiguous memory allocation show up.

---
 src/lib/kernel/bitmap.c | 18 ++++++++++++------
 src/threads/init.c      |  6 +++---
 2 files changed, 15 insertions(+), 9 deletions(-)

diff --git a/src/lib/kernel/bitmap.c b/src/lib/kernel/bitmap.c
index d323b89..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"
@@ -289,7 +290,7 @@ bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
 
 /* 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.
diff --git a/src/threads/init.c b/src/threads/init.c
index 57797be..ef82cb1 100644
--- a/src/threads/init.c
+++ b/src/threads/init.c
@@ -90,6 +90,9 @@ main (void)
   argv = read_command_line ();
   argv = parse_options (argv);
 
+  /* Set random seed if parse_options() didn't. */
+  random_init (0);
+
   /* Initialize memory system. */
   palloc_init ();
   malloc_init ();
@@ -101,9 +104,6 @@ main (void)
   gdt_init ();
 #endif
 
-  /* Set random seed if parse_options() didn't. */
-  random_init (0);
-
   /* Initialize interrupt handlers. */
   intr_init ();
   timer_init ();
-- 
2.30.2