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 /* This is the max file size for an older version of the Pintos
  11    file system that had 126 direct blocks each pointing to a
  12    single disk sector.  We could raise it now. */
  13 #define CHUNK_SIZE (126 * 512)
  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   printf ("(page-merge-par) init\n");
  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 a subprocess. */
  37 static void
  38 sort_chunks (void)
  39 {
  40   pid_t children[CHUNK_CNT];
  41   size_t i;
  42
  43   for (i = 0; i < CHUNK_CNT; i++)
  44     {
  45       char fn[128];
  46       char cmd[128];
  47       int fd;
  48
  49       printf ("(page-merge-par) sort chunk %zu\n", i);
  50
  51       /* Write this chunk to a file. */
  52       snprintf (fn, sizeof fn, "buf%zu", i);
  53       create (fn, CHUNK_SIZE);
  54       fd = open (fn);
  55       if (fd < 0)
  56         {
  57           printf ("(page-merge-par) open() failed\n");
  58           exit (1);
  59         }
  60       write (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  61       close (fd);
  62
  63       /* Sort with subprocess. */
  64       snprintf (cmd, sizeof cmd, "child-sort %s", fn);
  65       children[i] = exec (cmd);
  66       if (children[i] == -1)
  67         {
  68           printf ("(page-merge-par) exec() failed\n");
  69           exit (1);
  70         }
  71     }
  72
  73   for (i = 0; i < CHUNK_CNT; i++)
  74     {
  75       char fn[128];
  76       int fd;
  77
  78       if (wait (children[i]) != 123)
  79         {
  80           printf ("(page-merge-par) wait(exec()) returned bad value\n");
  81           exit (1);
  82         }
  83
  84       /* Read chunk back from file. */
  85       snprintf (fn, sizeof fn, "buf%zu", i);
  86       fd = open (fn);
  87       if (fd < 0)
  88         {
  89           printf ("(page-merge-par) open() failed\n");
  90           exit (1);
  91         }
  92       read (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  93       close (fd);
  94     }
  95 }
  96
  97 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
  98 static void
  99 merge (void)
 100 {
 101   unsigned char *mp[CHUNK_CNT];
 102   size_t mp_left;
 103   unsigned char *op;
 104   size_t i;
 105
 106   printf ("(page-merge-par) merge\n");
 107
 108   /* Initialize merge pointers. */
 109   mp_left = CHUNK_CNT;
 110   for (i = 0; i < CHUNK_CNT; i++)
 111     mp[i] = buf1 + CHUNK_SIZE * i;
 112
 113   /* Merge. */
 114   op = buf2;
 115   while (mp_left > 0)
 116     {
 117       /* Find smallest value. */
 118       size_t min = 0;
 119       for (i = 1; i < mp_left; i++)
 120         if (*mp[i] < *mp[min])
 121           min = i;
 122
 123       /* Append value to buf2. */
 124       *op++ = *mp[min];
 125
 126       /* Advance merge pointer.
 127          Delete this chunk from the set if it's emptied. */
 128       if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
 129         mp[min] = mp[--mp_left];
 130     }
 131 }
 132
 133 static void
 134 verify (void)
 135 {
 136   size_t buf_idx;
 137   size_t hist_idx;
 138
 139   printf ("(page-merge-par) verify\n");
 140
 141   buf_idx = 0;
 142   for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
 143        hist_idx++)
 144     {
 145       while (histogram[hist_idx]-- > 0)
 146         {
 147           if (buf2[buf_idx] != hist_idx)
 148             {
 149               printf ("(page-merge-par) bad value %d in byte %zu\n",
 150                       buf2[buf_idx], buf_idx);
 151               exit (1);
 152             }
 153           buf_idx++;
 154         }
 155     }
 156
 157   printf ("(page-merge-par) success, buf_idx=%zu\n", buf_idx);
 158 }
 159
 160 int
 161 main (void)
 162 {
 163   printf ("(page-merge-par) begin\n");
 164   init ();
 165   sort_chunks ();
 166   merge ();
 167   verify ();
 168   printf ("(page-merge-par) end\n");
 169   return 0;
 170 }