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