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

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