pintos-os.org Git - pintos-anon/blob - grading/vm/patches/00random.patch

   1 Modifies bitmap_scan() to return a random set of bits instead of the
   2 first set.  Helps to stress-test VM implementation.
   3
   4 Index: pintos/src/lib/kernel/bitmap.c
   5 ===================================================================
   6 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/lib/kernel/bitmap.c,v
   7 retrieving revision 1.11
   8 diff -u -p -r1.11 bitmap.c
   9 --- pintos/src/lib/kernel/bitmap.c      2 Jan 2005 02:09:58 -0000       1.11
  10 +++ pintos/src/lib/kernel/bitmap.c      9 Feb 2005 21:45:27 -0000
  11 @@ -3,6 +3,7 @@
  12  #include <limits.h>
  13  #include <round.h>
  14  #include <stdio.h>
  15 +#include <random.h>
  16  #include "threads/malloc.h"
  17  #ifdef FILESYS
  18  #include "filesys/file.h"
  19 @@ -30,6 +31,8 @@ struct bitmap
  20      elem_type *bits;    /* Elements that represent bits. */
  21    };
  22
  23 +bool randomize_bitmaps;
  24 +
  25  /* Returns the index of the element that contains the bit
  26     numbered BIT_IDX. */
  27  static inline size_t
  28 @@ -227,9 +230,28 @@ bitmap_scan (const struct bitmap *b, siz
  29      {
  30        size_t last = b->bit_cnt - cnt;
  31        size_t i;
  32 +      size_t n = 0;
  33 +
  34 +      /* Count number of matches. */
  35        for (i = start; i <= last; i++)
  36 -        if (!contains (b, i, cnt, !value))
  37 -          return i;
  38 +        if (!contains (b, i, cnt, !value))
  39 +          {
  40 +            if (randomize_bitmaps)
  41 +              n++;
  42 +            else
  43 +              return i;
  44 +          }
  45 +
  46 +      /* Pick one match. */
  47 +      if (n != 0)
  48 +        {
  49 +          random_init (0);
  50 +          n = random_ulong () % n;
  51 +          for (i = start; i <= last; i++)
  52 +            if (!contains (b, i, cnt, !value) && n-- == 0)
  53 +              return i;
  54 +          NOT_REACHED ();
  55 +        }
  56      }
  57    return BITMAP_ERROR;
  58  }
  59 Index: pintos/src/lib/kernel/bitmap.h
  60 ===================================================================
  61 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/lib/kernel/bitmap.h,v
  62 retrieving revision 1.5
  63 diff -u -p -r1.5 bitmap.h
  64 --- pintos/src/lib/kernel/bitmap.h      15 Dec 2004 06:08:55 -0000      1.5
  65 +++ pintos/src/lib/kernel/bitmap.h      9 Feb 2005 21:45:27 -0000
  66 @@ -44,4 +44,6 @@ size_t bitmap_needed_bytes (size_t bit_c
  67  struct bitmap *bitmap_create_preallocated (size_t bit_cnt,
  68                                             void *, size_t byte_cnt);
  69
  70 +extern bool randomize_bitmaps;
  71 +
  72  #endif /* lib/kernel/bitmap.h */
  73 Index: pintos/src/threads/init.c
  74 ===================================================================
  75 RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/init.c,v
  76 retrieving revision 1.53
  77 diff -u -p -r1.53 init.c
  78 --- pintos/src/threads/init.c   7 Feb 2005 05:56:07 -0000       1.53
  79 +++ pintos/src/threads/init.c   9 Feb 2005 21:45:28 -0000
  80 @@ -8,6 +8,7 @@
  81  #include <stdio.h>
  82  #include <stdlib.h>
  83  #include <string.h>
  84 +#include <bitmap.h>
  85  #include "devices/kbd.h"
  86  #include "devices/serial.h"
  87  #include "devices/timer.h"
  88 @@ -193,6 +194,8 @@ paging_init (void)
  89       new page tables immediately.  See [IA32-v2a] "MOV--Move
  90       to/from Control Registers" and [IA32-v3] 3.7.5. */
  91    asm volatile ("mov %%cr3, %0" :: "r" (vtop (base_page_dir)));
  92 +
  93 +  randomize_bitmaps = true;
  94  }
  95
  96  /* Parses the command line. */