From 24ff01c3b69360c8a7c01d0959f4148688cfeb7a Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
Date: Fri, 11 Feb 2005 03:49:41 +0000
Subject: [PATCH] Fix randomization patches to work with revised bitmap code.
---
grading/userprog/patches/00random.patch | 113 ++++++++++++++++++------
grading/vm/patches/00random.patch | 113 ++++++++++++++++++------
2 files changed, 168 insertions(+), 58 deletions(-)
diff --git a/grading/userprog/patches/00random.patch b/grading/userprog/patches/00random.patch
index 6e74443..3648632 100644
--- a/grading/userprog/patches/00random.patch
+++ b/grading/userprog/patches/00random.patch
@@ -1,41 +1,96 @@
Modifies bitmap_scan() to return a random set of bits instead of the
first set. Helps to stress-test VM implementation.
-diff -u pintos/src/lib/kernel/bitmap.c~ pintos/src/lib/kernel/bitmap.c
---- pintos/src/lib/kernel/bitmap.c~ 2004-10-06 14:29:56.000000000 -0700
-+++ pintos/src/lib/kernel/bitmap.c 2004-11-03 14:35:22.000000000 -0800
-@@ -1,6 +1,7 @@
- #include "bitmap.h"
- #include <debug.h>
+Index: pintos/src/lib/kernel/bitmap.c
+===================================================================
+RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/lib/kernel/bitmap.c,v
+retrieving revision 1.11
+diff -u -p -r1.11 bitmap.c
+--- pintos/src/lib/kernel/bitmap.c 2 Jan 2005 02:09:58 -0000 1.11
++++ pintos/src/lib/kernel/bitmap.c 9 Feb 2005 21:45:27 -0000
+@@ -3,6 +3,7 @@
#include <limits.h>
-+#include <random.h>
#include <round.h>
#include <stdio.h>
++#include <random.h>
#include "threads/malloc.h"
-@@ -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);
- for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
- if (!contains (b, idx, idx + cnt, !value))
-+ n++;
-+ if (n == 0)
-+ return BITMAP_ERROR;
++extern bool randomize_bitmaps;
+
-+ random_init (0);
-+ m = random_ulong () % n;
-+
-+ for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
-+ if (!contains (b, idx, idx + cnt, !value) && m-- == 0)
- return idx;
-- return BITMAP_ERROR;
+ #endif /* lib/kernel/bitmap.h */
+Index: pintos/src/threads/init.c
+===================================================================
+RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/init.c,v
+retrieving revision 1.53
+diff -u -p -r1.53 init.c
+--- pintos/src/threads/init.c 7 Feb 2005 05:56:07 -0000 1.53
++++ pintos/src/threads/init.c 9 Feb 2005 21:45:28 -0000
+@@ -8,6 +8,7 @@
+ #include <stdio.h>
+ #include <stdlib.h>
+ #include <string.h>
++#include <bitmap.h>
+ #include "devices/kbd.h"
+ #include "devices/serial.h"
+ #include "devices/timer.h"
+@@ -193,6 +194,8 @@ paging_init (void)
+ new page tables immediately. See [IA32-v2a] "MOV--Move
+ to/from Control Registers" and [IA32-v3] 3.7.5. */
+ asm volatile ("mov %%cr3, %0" :: "r" (vtop (base_page_dir)));
+
-+ NOT_REACHED ();
++ randomize_bitmaps = true;
}
- /* Finds the first group of CNT consecutive bits in B at or after
+ /* Parses the command line. */
diff --git a/grading/vm/patches/00random.patch b/grading/vm/patches/00random.patch
index 6e74443..3648632 100644
--- a/grading/vm/patches/00random.patch
+++ b/grading/vm/patches/00random.patch
@@ -1,41 +1,96 @@
Modifies bitmap_scan() to return a random set of bits instead of the
first set. Helps to stress-test VM implementation.
-diff -u pintos/src/lib/kernel/bitmap.c~ pintos/src/lib/kernel/bitmap.c
---- pintos/src/lib/kernel/bitmap.c~ 2004-10-06 14:29:56.000000000 -0700
-+++ pintos/src/lib/kernel/bitmap.c 2004-11-03 14:35:22.000000000 -0800
-@@ -1,6 +1,7 @@
- #include "bitmap.h"
- #include <debug.h>
+Index: pintos/src/lib/kernel/bitmap.c
+===================================================================
+RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/lib/kernel/bitmap.c,v
+retrieving revision 1.11
+diff -u -p -r1.11 bitmap.c
+--- pintos/src/lib/kernel/bitmap.c 2 Jan 2005 02:09:58 -0000 1.11
++++ pintos/src/lib/kernel/bitmap.c 9 Feb 2005 21:45:27 -0000
+@@ -3,6 +3,7 @@
#include <limits.h>
-+#include <random.h>
#include <round.h>
#include <stdio.h>
++#include <random.h>
#include "threads/malloc.h"
-@@ -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);
- for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
- if (!contains (b, idx, idx + cnt, !value))
-+ n++;
-+ if (n == 0)
-+ return BITMAP_ERROR;
++extern bool randomize_bitmaps;
+
-+ random_init (0);
-+ m = random_ulong () % n;
-+
-+ for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
-+ if (!contains (b, idx, idx + cnt, !value) && m-- == 0)
- return idx;
-- return BITMAP_ERROR;
+ #endif /* lib/kernel/bitmap.h */
+Index: pintos/src/threads/init.c
+===================================================================
+RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/init.c,v
+retrieving revision 1.53
+diff -u -p -r1.53 init.c
+--- pintos/src/threads/init.c 7 Feb 2005 05:56:07 -0000 1.53
++++ pintos/src/threads/init.c 9 Feb 2005 21:45:28 -0000
+@@ -8,6 +8,7 @@
+ #include <stdio.h>
+ #include <stdlib.h>
+ #include <string.h>
++#include <bitmap.h>
+ #include "devices/kbd.h"
+ #include "devices/serial.h"
+ #include "devices/timer.h"
+@@ -193,6 +194,8 @@ paging_init (void)
+ new page tables immediately. See [IA32-v2a] "MOV--Move
+ to/from Control Registers" and [IA32-v3] 3.7.5. */
+ asm volatile ("mov %%cr3, %0" :: "r" (vtop (base_page_dir)));
+
-+ NOT_REACHED ();
++ randomize_bitmaps = true;
}
- /* Finds the first group of CNT consecutive bits in B at or after
+ /* Parses the command line. */
--
2.30.2