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 diff -u pintos/src/lib/kernel/bitmap.c~ pintos/src/lib/kernel/bitmap.c
   5 --- pintos/src/lib/kernel/bitmap.c~     2004-10-06 14:29:56.000000000 -0700
   6 +++ pintos/src/lib/kernel/bitmap.c      2004-11-03 14:35:22.000000000 -0800
   7 @@ -1,6 +1,7 @@
   8  #include "bitmap.h"
   9  #include <debug.h>
  10  #include <limits.h>
  11 +#include <random.h>
  12  #include <round.h>
  13  #include <stdio.h>
  14  #include "threads/malloc.h"
  15 @@ -212,14 +213,25 @@ size_t
  16  bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
  17  {
  18    size_t idx, last;
  19 +  size_t n = 0, m;
  20
  21    ASSERT (b != NULL);
  22    ASSERT (start <= b->bit_cnt);
  23
  24    for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
  25      if (!contains (b, idx, idx + cnt, !value))
  26 +      n++;
  27 +  if (n == 0)
  28 +    return BITMAP_ERROR;
  29 +
  30 +  random_init (0);
  31 +  m = random_ulong () % n;
  32 +
  33 +  for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
  34 +    if (!contains (b, idx, idx + cnt, !value) && m-- == 0)
  35        return idx;
  36 -  return BITMAP_ERROR;
  37 +
  38 +  NOT_REACHED ();
  39  }
  40
  41  /* Finds the first group of CNT consecutive bits in B at or after