6 #include "posix-compat.h"
8 #include "../lib/arc4.h"
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. */
17 unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
18 size_t histogram[256];
20 /* Initialize buf1 with random data,
21 then count the number of instances of each value within it. */
28 printf ("(page-merge-par) init\n");
30 arc4_init (&arc4, "foobar", 6);
31 arc4_crypt (&arc4, buf1, sizeof buf1);
32 for (i = 0; i < sizeof buf1; i++)
36 /* Sort each chunk of buf1 using a subprocess. */
40 pid_t children[CHUNK_CNT];
43 for (i = 0; i < CHUNK_CNT; i++)
49 printf ("(page-merge-par) sort chunk %zu\n", i);
51 /* Write this chunk to a file. */
52 snprintf (fn, sizeof fn, "buf%zu", i);
53 create (fn, CHUNK_SIZE);
57 printf ("(page-merge-par) open() failed\n");
60 write (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
63 /* Sort with subprocess. */
64 snprintf (cmd, sizeof cmd, "child-sort %s", fn);
65 children[i] = exec (cmd);
66 if (children[i] == -1)
68 printf ("(page-merge-par) exec() failed\n");
73 for (i = 0; i < CHUNK_CNT; i++)
78 if (wait (children[i]) != 123)
80 printf ("(page-merge-par) wait(exec()) returned bad value\n");
84 /* Read chunk back from file. */
85 snprintf (fn, sizeof fn, "buf%zu", i);
89 printf ("(page-merge-par) open() failed\n");
92 read (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
97 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
101 unsigned char *mp[CHUNK_CNT];
106 printf ("(page-merge-par) merge\n");
108 /* Initialize merge pointers. */
110 for (i = 0; i < CHUNK_CNT; i++)
111 mp[i] = buf1 + CHUNK_SIZE * i;
117 /* Find smallest value. */
119 for (i = 1; i < mp_left; i++)
120 if (*mp[i] < *mp[min])
123 /* Append value to buf2. */
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];
139 printf ("(page-merge-par) verify\n");
142 for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
145 while (histogram[hist_idx]-- > 0)
147 if (buf2[buf_idx] != hist_idx)
149 printf ("(page-merge-par) bad value %d in byte %zu\n",
150 buf2[buf_idx], buf_idx);
157 printf ("(page-merge-par) success, buf_idx=%zu\n", buf_idx);
163 printf ("(page-merge-par) begin\n");
168 printf ("(page-merge-par) end\n");