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