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

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