138 lines
3.1 KiB
C
138 lines
3.1 KiB
C
|
/* 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 ();
|
||
|
|
}
|