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

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