From 24ff01c3b69360c8a7c01d0959f4148688cfeb7a Mon Sep 17 00:00:00 2001 From: Ben Pfaff 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 +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 -+#include #include #include ++#include #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 + #include + #include ++#include + #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 +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 -+#include #include #include ++#include #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 + #include + #include ++#include + #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