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

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