-@@ -212,14 +213,25 @@ size_t
- bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
- {
- size_t idx, last;
-+ size_t n = 0, m;
-
- ASSERT (b != NULL);
- ASSERT (start <= b->bit_cnt);
+ #ifdef FILESYS
+ #include "filesys/file.h"
+@@ -30,6 +31,8 @@ struct bitmap
+ elem_type *bits; /* Elements that represent bits. */
+ };
+
++bool randomize_bitmaps;
++
+ /* Returns the index of the element that contains the bit
+ numbered BIT_IDX. */
+ static inline size_t
+@@ -227,9 +230,28 @@ bitmap_scan (const struct bitmap *b, siz
+ {
+ size_t last = b->bit_cnt - cnt;
+ size_t i;
++ size_t n = 0;
++
++ /* Count number of matches. */
+ for (i = start; i <= last; i++)
+- if (!contains (b, i, cnt, !value))
+- return i;
++ if (!contains (b, i, cnt, !value))
++ {
++ if (randomize_bitmaps)
++ n++;
++ else
++ return i;
++ }
++
++ /* Pick one match. */
++ if (n != 0)
++ {
++ random_init (0);
++ n = random_ulong () % n;
++ for (i = start; i <= last; i++)
++ if (!contains (b, i, cnt, !value) && n-- == 0)
++ return i;
++ NOT_REACHED ();
++ }
+ }
+ return BITMAP_ERROR;
+ }
+Index: pintos/src/lib/kernel/bitmap.h
+===================================================================
+RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/lib/kernel/bitmap.h,v
+retrieving revision 1.5
+diff -u -p -r1.5 bitmap.h
+--- pintos/src/lib/kernel/bitmap.h 15 Dec 2004 06:08:55 -0000 1.5
++++ pintos/src/lib/kernel/bitmap.h 9 Feb 2005 21:45:27 -0000
+@@ -44,4 +44,6 @@ size_t bitmap_needed_bytes (size_t bit_c
+ struct bitmap *bitmap_create_preallocated (size_t bit_cnt,
+ void *, size_t byte_cnt);