pintos-os.org Git - pintos-anon/blob - src/tests/vm/page-merge-seq.c

   1 /* Generates about 1 MB of random data that is then divided into
   2    16 chunks.  A separate subprocess sorts each chunk in
   3    sequence.  Then we merge the chunks and verify that the result
   4    is what it should be. */
   5
   6 #include <syscall.h>
   7 #include "tests/arc4.h"
   8 #include "tests/lib.h"
   9 #include "tests/main.h"
  10
  11 /* This is the max file size for an older version of the Pintos
  12    file system that had 126 direct blocks each pointing to a
  13    single disk sector.  We could raise it now. */
  14 #define CHUNK_SIZE (126 * 512)
  15 #define CHUNK_CNT 16                            /* Number of chunks. */
  16 #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE)      /* Buffer size. */
  17
  18 unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
  19 size_t histogram[256];
  20
  21 /* Initialize buf1 with random data,
  22    then count the number of instances of each value within it. */
  23 static void
  24 init (void)
  25 {
  26   struct arc4 arc4;
  27   size_t i;
  28
  29   msg ("init");
  30
  31   arc4_init (&arc4, "foobar", 6);
  32   arc4_crypt (&arc4, buf1, sizeof buf1);
  33   for (i = 0; i < sizeof buf1; i++)
  34     histogram[buf1[i]]++;
  35 }
  36
  37 /* Sort each chunk of buf1 using a subprocess. */
  38 static void
  39 sort_chunks (void)
  40 {
  41   size_t i;
  42
  43   create ("buffer", CHUNK_SIZE);
  44   for (i = 0; i < CHUNK_CNT; i++)
  45     {
  46       pid_t child;
  47       int handle;
  48
  49       msg ("sort chunk %zu", i);
  50
  51       /* Write this chunk to a file. */
  52       quiet = true;
  53       CHECK ((handle = open ("buffer")) > 1, "open \"buffer\"");
  54       write (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  55       close (handle);
  56
  57       /* Sort with subprocess. */
  58       CHECK ((child = exec ("child-sort buffer")) != -1,
  59              "exec \"child-sort buffer\"");
  60       CHECK (wait (child) == 123, "wait for child-sort");
  61
  62       /* Read chunk back from file. */
  63       CHECK ((handle = open ("buffer")) > 1, "open \"buffer\"");
  64       read (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  65       close (handle);
  66
  67       quiet = false;
  68     }
  69 }
  70
  71 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
  72 static void
  73 merge (void)
  74 {
  75   unsigned char *mp[CHUNK_CNT];
  76   size_t mp_left;
  77   unsigned char *op;
  78   size_t i;
  79
  80   msg ("merge");
  81
  82   /* Initialize merge pointers. */
  83   mp_left = CHUNK_CNT;
  84   for (i = 0; i < CHUNK_CNT; i++)
  85     mp[i] = buf1 + CHUNK_SIZE * i;
  86
  87   /* Merge. */
  88   op = buf2;
  89   while (mp_left > 0)
  90     {
  91       /* Find smallest value. */
  92       size_t min = 0;
  93       for (i = 1; i < mp_left; i++)
  94         if (*mp[i] < *mp[min])
  95           min = i;
  96
  97       /* Append value to buf2. */
  98       *op++ = *mp[min];
  99
 100       /* Advance merge pointer.
 101          Delete this chunk from the set if it's emptied. */
 102       if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
 103         mp[min] = mp[--mp_left];
 104     }
 105 }
 106
 107 static void
 108 verify (void)
 109 {
 110   size_t buf_idx;
 111   size_t hist_idx;
 112
 113   msg ("verify");
 114
 115   buf_idx = 0;
 116   for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
 117        hist_idx++)
 118     {
 119       while (histogram[hist_idx]-- > 0)
 120         {
 121           if (buf2[buf_idx] != hist_idx)
 122             fail ("bad value %d in byte %zu", buf2[buf_idx], buf_idx);
 123           buf_idx++;
 124         }
 125     }
 126
 127   msg ("success, buf_idx=%'zu", buf_idx);
 128 }
 129
 130 void
 131 test_main (void)
 132 {
 133   init ();
 134   sort_chunks ();
 135   merge ();
 136   verify ();
 137 }