pintos-os.org Git - pintos-anon/blob - grading/vm/page-merge-seq.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 16                            /* 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-seq) 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   size_t i;
  41
  42   create ("buffer", CHUNK_SIZE);
  43   for (i = 0; i < CHUNK_CNT; i++)
  44     {
  45       int fd;
  46
  47       printf ("(page-merge-seq) sort chunk %zu\n", i);
  48
  49       /* Write this chunk to a file. */
  50       fd = open ("buffer");
  51
  52       if (fd < 0)
  53         {
  54           printf ("(page-merge-seq) 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       pid_t child = exec ("child-sort buffer");
  62       if (child == -1)
  63         {
  64           printf ("(page-merge-seq) exec() failed\n");
  65           exit (1);
  66         }
  67       if (wait (child) != 123)
  68         {
  69           printf ("(page-merge-seq) wait(exec()) returned bad value\n");
  70           exit (1);
  71         }
  72
  73       /* Read chunk back from file. */
  74       fd = open ("buffer");
  75       if (fd < 0)
  76         {
  77           printf ("(page-merge-seq) open() failed\n");
  78           exit (1);
  79         }
  80       read (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  81       close (fd);
  82     }
  83 }
  84
  85 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
  86 static void
  87 merge (void)
  88 {
  89   unsigned char *mp[CHUNK_CNT];
  90   size_t mp_left;
  91   unsigned char *op;
  92   size_t i;
  93
  94   printf ("(page-merge-seq) merge\n");
  95
  96   /* Initialize merge pointers. */
  97   mp_left = CHUNK_CNT;
  98   for (i = 0; i < CHUNK_CNT; i++)
  99     mp[i] = buf1 + CHUNK_SIZE * i;
 100
 101   /* Merge. */
 102   op = buf2;
 103   while (mp_left > 0)
 104     {
 105       /* Find smallest value. */
 106       size_t min = 0;
 107       for (i = 1; i < mp_left; i++)
 108         if (*mp[i] < *mp[min])
 109           min = i;
 110
 111       /* Append value to buf2. */
 112       *op++ = *mp[min];
 113
 114       /* Advance merge pointer.
 115          Delete this chunk from the set if it's emptied. */
 116       if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
 117         mp[min] = mp[--mp_left];
 118     }
 119 }
 120
 121 static void
 122 verify (void)
 123 {
 124   size_t buf_idx;
 125   size_t hist_idx;
 126
 127   printf ("(page-merge-seq) verify\n");
 128
 129   buf_idx = 0;
 130   for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
 131        hist_idx++)
 132     {
 133       while (histogram[hist_idx]-- > 0)
 134         {
 135           if (buf2[buf_idx] != hist_idx)
 136             {
 137               printf ("(page-merge-seq) bad value %d in byte %zu\n",
 138                       buf2[buf_idx], buf_idx);
 139               exit (1);
 140             }
 141           buf_idx++;
 142         }
 143     }
 144
 145   printf ("(page-merge-seq) success, buf_idx=%zu\n", buf_idx);
 146 }
 147
 148 int
 149 main (void)
 150 {
 151   printf ("(page-merge-seq) begin\n");
 152   init ();
 153   sort_chunks ();
 154   merge ();
 155   verify ();
 156   printf ("(page-merge-seq) end\n");
 157   return 0;
 158 }