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