1 /* Generates about 1 MB of random data that is then divided into
2 16 chunks. A separate subprocess sorts each chunk; the
3 subprocesses run in parallel. Then we merge the chunks and
4 verify that the result is what it should be. */
6 #include "tests/vm/parallel-merge.h"
9 #include "tests/arc4.h"
10 #include "tests/lib.h"
11 #include "tests/main.h"
13 #define CHUNK_SIZE (128 * 1024)
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. */
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 SUBPROCESS,
37 which is expected to return EXIT_STATUS. */
39 sort_chunks (const char *subprocess, int exit_status)
41 pid_t children[CHUNK_CNT];
44 for (i = 0; i < CHUNK_CNT; i++)
50 msg ("sort chunk %zu", i);
52 /* Write this chunk to a file. */
53 snprintf (fn, sizeof fn, "buf%zu", i);
54 create (fn, CHUNK_SIZE);
56 CHECK ((handle = open (fn)) > 1, "open \"%s\"", fn);
57 write (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
60 /* Sort with subprocess. */
61 snprintf (cmd, sizeof cmd, "%s %s", subprocess, fn);
62 CHECK ((children[i] = exec (cmd)) != -1, "exec \"%s\"", cmd);
66 for (i = 0; i < CHUNK_CNT; i++)
71 CHECK (wait (children[i]) == exit_status, "wait for child %zu", i);
73 /* Read chunk back from file. */
75 snprintf (fn, sizeof fn, "buf%zu", i);
76 CHECK ((handle = open (fn)) > 1, "open \"%s\"", fn);
77 read (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
83 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
87 unsigned char *mp[CHUNK_CNT];
94 /* Initialize merge pointers. */
96 for (i = 0; i < CHUNK_CNT; i++)
97 mp[i] = buf1 + CHUNK_SIZE * i;
103 /* Find smallest value. */
105 for (i = 1; i < mp_left; i++)
106 if (*mp[i] < *mp[min])
109 /* Append value to buf2. */
112 /* Advance merge pointer.
113 Delete this chunk from the set if it's emptied. */
114 if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
115 mp[min] = mp[--mp_left];
128 for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
131 while (histogram[hist_idx]-- > 0)
133 if (buf2[buf_idx] != hist_idx)
134 fail ("bad value %d in byte %zu", buf2[buf_idx], buf_idx);
139 msg ("success, buf_idx=%'zu", buf_idx);
143 parallel_merge (const char *child_name, int exit_status)
146 sort_chunks (child_name, exit_status);