/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- sortints
- initprogname
- vscomplain
- complainx
- complain
- doopen
- doclose
- docreate
- doremove
- getsize
- doread
- doexactread
- dowrite
- dolseek
- dochdir
- domkdir
- dofork
- dowait
- doforkall
- seekmyplace
- getmykeys
- checksum_file
- genkeys_sub
- genkeys
- binname
- mergedname
- bin
- sortbins
- mergebins
- assemble
- checksize_bins
- checksize_merge
- sort
- validname
- checksize_valid
- dovalidate
- validate
- setdir
- unsetdir
- randomize
- usage
- doargs
- main
1 /*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
3 * The President and Fellows of Harvard College.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * psort - parallel sort.
32 *
33 * This is loosely based on some real parallel sort benchmarks, but
34 * because of various limitations of OS/161 it is massively
35 * inefficient. But that's ok; the goal is to stress the VM and buffer
36 * cache.
37 */
38
39 #include <sys/types.h>
40 #include <sys/stat.h>
41 #include <sys/wait.h>
42 #include <stdio.h>
43 #include <stdarg.h>
44 #include <stdlib.h>
45 #include <string.h>
46 #include <assert.h>
47 #include <unistd.h>
48 #include <fcntl.h>
49 #include <errno.h>
50
51 #ifndef RANDOM_MAX
52 /* Note: this is correct for OS/161 but not for some Unix C libraries */
53 #define RANDOM_MAX RAND_MAX
54 #endif
55
56 #define PATH_KEYS "sortkeys"
57 #define PATH_SORTED "output"
58 #define PATH_TESTDIR "psortdir"
59 #define PATH_RANDOM "rand:"
60
61 #define WORKNUM (128*1024)
62
63
64 static int workspace[WORKNUM];
65
66 static const char *progname;
67
68 static int numprocs = 4;
69 static int numkeys = 10000;
70 static long randomseed = 15432753;
71
72 static off_t correctsize;
73 static unsigned long checksum;
74
75 #define NOBODY (-1)
76 static int me = NOBODY;
77
78 ////////////////////////////////////////////////////////////
79
80 static
81 void
82 sortints(int *v, int num)
83 {
84 int pivotval, pivotpoint, pivotcount;
85 int frontpos, readpos, endpos, i, j;
86 int tmp;
87
88 if (num < 2) {
89 return;
90 }
91
92 pivotpoint = num/2;
93 pivotval = v[pivotpoint];
94 pivotcount = 0;
95
96 frontpos = 0;
97 readpos = 0;
98 endpos = num;
99 while (readpos < endpos) {
100 if (v[readpos] < pivotval) {
101 v[frontpos++] = v[readpos++];
102 }
103 else if (v[readpos] == pivotval) {
104 readpos++;
105 pivotcount++;
106 }
107 else {
108 tmp = v[--endpos];
109 v[endpos] = v[readpos];
110 v[readpos] = tmp;
111 }
112 }
113 assert(readpos == endpos);
114 assert(frontpos + pivotcount == readpos);
115
116 for (i=frontpos; i<endpos; i++) {
117 v[i] = pivotval;
118 }
119
120 for (i=endpos, j=num-1; i<j; i++,j--) {
121 tmp = v[i];
122 v[i] = v[j];
123 v[j] = tmp;
124 }
125
126 sortints(v, frontpos);
127 sortints(&v[endpos], num-endpos);
128 }
129
130 ////////////////////////////////////////////////////////////
131
132 static
133 void
134 initprogname(const char *av0)
135 {
136 if (av0) {
137 progname = strrchr(av0, '/');
138 if (progname) {
139 progname++;
140 }
141 else {
142 progname = av0;
143 }
144 }
145 else {
146 progname = "psort";
147 }
148 }
149
150 static
151 void
152 vscomplain(char *buf, size_t len, const char *fmt, va_list ap, int err)
153 {
154 size_t pos;
155
156 if (me >= 0) {
157 snprintf(buf, len, "%s: proc %d: ", progname, me);
158 }
159 else {
160 snprintf(buf, len, "%s: ", progname);
161 }
162 pos = strlen(buf);
163
164 vsnprintf(buf+pos, len-pos, fmt, ap);
165 pos = strlen(buf);
166
167 if (err >= 0) {
168 snprintf(buf+pos, len-pos, ": %s\n", strerror(err));
169 }
170 else {
171 snprintf(buf+pos, len-pos, "\n");
172 }
173 }
174
175 static
176 void
177 complainx(const char *fmt, ...)
178 {
179 int rc;
180 char buf[256];
181 va_list ap;
182
183 va_start(ap, fmt);
184 vscomplain(buf, sizeof(buf), fmt, ap, -1);
185 va_end(ap);
186
187 /* Write the message in one go so it's atomic */
188 rc = write(STDERR_FILENO, buf, strlen(buf));
189 /* suppress compiler warning about setting but not
190 using rc */
191 (void)rc;
192 }
193
194 static
195 void
196 complain(const char *fmt, ...)
197 {
198 int rc;
199 char buf[256];
200 va_list ap;
201 int err = errno;
202
203 va_start(ap, fmt);
204 vscomplain(buf, sizeof(buf), fmt, ap, err);
205 va_end(ap);
206
207 /* Write the message in one go so it's atomic */
208 rc = write(STDERR_FILENO, buf, strlen(buf));
209 /* suppress compiler warning about setting but not
210 using rc */
211 (void)rc;
212 }
213
214 ////////////////////////////////////////////////////////////
215
216 static
217 int
218 doopen(const char *path, int flags, int mode)
219 {
220 int fd;
221
222 fd = open(path, flags, mode);
223 if (fd<0) {
224 complain("%s", path);
225 exit(1);
226 }
227 return fd;
228 }
229
230 static
231 void
232 doclose(const char *path, int fd)
233 {
234 if (close(fd)) {
235 complain("%s: close", path);
236 exit(1);
237 }
238 }
239
240 static
241 void
242 docreate(const char *path)
243 {
244 int fd;
245
246 fd = doopen(path, O_WRONLY|O_CREAT|O_TRUNC, 0664);
247 doclose(path, fd);
248 }
249
250 static
251 void
252 doremove(const char *path)
253 {
254 static int noremove;
255
256 if (noremove) {
257 return;
258 }
259
260 if (remove(path) < 0) {
261 if (errno == ENOSYS) {
262 /* Complain (and try) only once. */
263 noremove = 1;
264 }
265 complain("%s: remove", path);
266 }
267 }
268
269 static
270 off_t
271 getsize(const char *path)
272 {
273 struct stat buf;
274 int fd;
275 static int no_stat, no_fstat;
276
277 if (!no_stat) {
278 if (stat(path, &buf) == 0) {
279 return buf.st_size;
280 }
281 if (errno != ENOSYS) {
282 complain("%s: stat", path);
283 exit(1);
284 }
285 /* Avoid further "Unknown syscall 81" messages */
286 no_stat = 1;
287 }
288
289 fd = doopen(path, O_RDONLY, 0);
290 if (!no_fstat) {
291 if (fstat(fd, &buf) == 0) {
292 close(fd);
293 return buf.st_size;
294 }
295 if (errno != ENOSYS) {
296 complain("%s: stat", path);
297 exit(1);
298 }
299 /* Avoid further "Unknown syscall 82" messages */
300 no_fstat = 1;
301 }
302
303 /* otherwise, lseek */
304 if (lseek(fd, 0, SEEK_END) >= 0) {
305 buf.st_size = lseek(fd, 0, SEEK_CUR);
306 if (buf.st_size >= 0) {
307 return buf.st_size;
308 }
309 }
310 complain("%s: getting file size with lseek", path);
311 close(fd);
312 exit(1);
313 }
314
315 static
316 size_t
317 doread(const char *path, int fd, void *buf, size_t len)
318 {
319 int result;
320
321 result = read(fd, buf, len);
322 if (result < 0) {
323 complain("%s: read", path);
324 exit(1);
325 }
326 return (size_t) result;
327 }
328
329 static
330 void
331 doexactread(const char *path, int fd, void *buf, size_t len)
332 {
333 size_t result;
334
335 result = doread(path, fd, buf, len);
336 if (result != len) {
337 complainx("%s: read: short count", path);
338 exit(1);
339 }
340 }
341
342 static
343 void
344 dowrite(const char *path, int fd, const void *buf, size_t len)
345 {
346 int result;
347
348 result = write(fd, buf, len);
349 if (result < 0) {
350 complain("%s: write", path);
351 exit(1);
352 }
353 if ((size_t) result != len) {
354 complainx("%s: write: short count", path);
355 exit(1);
356 }
357 }
358
359 static
360 void
361 dolseek(const char *name, int fd, off_t offset, int whence)
362 {
363 if (lseek(fd, offset, whence) < 0) {
364 complain("%s: lseek", name);
365 exit(1);
366 }
367 }
368
369 #if 0 /* let's not require subdirs */
370 static
371 void
372 dochdir(const char *path)
373 {
374 if (chdir(path) < 0) {
375 complain("%s: chdir", path);
376 exit(1);
377 }
378 }
379
380 static
381 void
382 domkdir(const char *path, int mode)
383 {
384 if (mkdir(path, mode) < 0) {
385 complain("%s: mkdir", path);
386 exit(1);
387 }
388 }
389 #endif /* 0 */
390
391 static
392 pid_t
393 dofork(void)
394 {
395 pid_t pid;
396
397 pid = fork();
398 if (pid < 0) {
399 complain("fork");
400 /* but don't exit */
401 }
402
403 return pid;
404 }
405
406 ////////////////////////////////////////////////////////////
407
408 static
409 int
410 dowait(int guy, pid_t pid)
411 {
412 int status, result;
413
414 result = waitpid(pid, &status, 0);
415 if (result < 0) {
416 complain("waitpid");
417 return -1;
418 }
419 if (WIFSIGNALED(status)) {
420 complainx("proc %d: signal %d", guy, WTERMSIG(status));
421 return -1;
422 }
423 assert(WIFEXITED(status));
424 status = WEXITSTATUS(status);
425 if (status) {
426 complainx("proc %d: exit %d", guy, status);
427 return -1;
428 }
429 return 0;
430 }
431
432 static
433 void
434 doforkall(const char *phasename, void (*func)(void))
435 {
436 int i, bad = 0;
437 pid_t pids[numprocs];
438
439 for (i=0; i<numprocs; i++) {
440 pids[i] = dofork();
441 if (pids[i] < 0) {
442 bad = 1;
443 }
444 else if (pids[i] == 0) {
445 /* child */
446 me = i;
447 func();
448 exit(0);
449 }
450 }
451
452 for (i=0; i<numprocs; i++) {
453 if (pids[i] > 0 && dowait(i, pids[i])) {
454 bad = 1;
455 }
456 }
457
458 if (bad) {
459 complainx("%s failed.", phasename);
460 exit(1);
461 }
462 }
463
464 static
465 void
466 seekmyplace(const char *name, int fd)
467 {
468 int keys_per, myfirst;
469 off_t offset;
470
471 keys_per = numkeys / numprocs;
472 myfirst = me*keys_per;
473 offset = myfirst * sizeof(int);
474
475 dolseek(name, fd, offset, SEEK_SET);
476 }
477
478 static
479 int
480 getmykeys(void)
481 {
482 int keys_per, myfirst, mykeys;
483
484 keys_per = numkeys / numprocs;
485 myfirst = me*keys_per;
486 mykeys = (me < numprocs-1) ? keys_per : numkeys - myfirst;
487
488 return mykeys;
489 }
490
491 ////////////////////////////////////////////////////////////
492
493 static
494 unsigned long
495 checksum_file(const char *path)
496 {
497 int fd;
498 char buf[512];
499 size_t count, i;
500 unsigned long sum = 0;
501
502 fd = doopen(path, O_RDONLY, 0);
503
504 while ((count = doread(path, fd, buf, sizeof(buf))) > 0) {
505 for (i=0; i<count; i++) {
506 sum += (unsigned char) buf[i];
507 }
508 }
509
510 doclose(path, fd);
511
512 return sum;
513 }
514
515 ////////////////////////////////////////////////////////////
516
517 static long *seeds;
518
519 static
520 void
521 genkeys_sub(void)
522 {
523 int fd, i, mykeys, keys_done, keys_to_do, value;
524
525 fd = doopen(PATH_KEYS, O_WRONLY, 0);
526
527 mykeys = getmykeys();
528 seekmyplace(PATH_KEYS, fd);
529
530 srandom(seeds[me]);
531 keys_done = 0;
532 while (keys_done < mykeys) {
533 keys_to_do = mykeys - keys_done;
534 if (keys_to_do > WORKNUM) {
535 keys_to_do = WORKNUM;
536 }
537
538 for (i=0; i<keys_to_do; i++) {
539 value = random();
540
541 // check bounds of value
542 assert(value >= 0);
543 assert(value <= RANDOM_MAX);
544
545 // do not allow the value to be zero or RANDOM_MAX
546 while (value == 0 || value == RANDOM_MAX) {
547 value = random();
548 }
549
550 workspace[i] = value;
551 }
552
553 dowrite(PATH_KEYS, fd, workspace, keys_to_do*sizeof(int));
554 keys_done += keys_to_do;
555 }
556
557 doclose(PATH_KEYS, fd);
558 }
559
560 static
561 void
562 genkeys(void)
563 {
564 long seedspace[numprocs];
565 int i;
566
567 /* Create the file. */
568 docreate(PATH_KEYS);
569
570 /* Generate random seeds for each subprocess. */
571 srandom(randomseed);
572 for (i=0; i<numprocs; i++) {
573 seedspace[i] = random();
574 }
575
576 /* Do it. */
577 seeds = seedspace;
578 doforkall("Initialization", genkeys_sub);
579 seeds = NULL;
580
581 /* Cross-check the size of the output. */
582 if (getsize(PATH_KEYS) != correctsize) {
583 complainx("%s: file is wrong size", PATH_KEYS);
584 exit(1);
585 }
586
587 /* Checksum the output. */
588 checksum = checksum_file(PATH_KEYS);
589 complainx("Checksum of unsorted keys: %ld", checksum);
590 }
591
592 ////////////////////////////////////////////////////////////
593
594 static
595 const char *
596 binname(int a, int b)
597 {
598 static char rv[32];
599 snprintf(rv, sizeof(rv), "bin-%d-%d", a, b);
600 return rv;
601 }
602
603 static
604 const char *
605 mergedname(int a)
606 {
607 static char rv[32];
608 snprintf(rv, sizeof(rv), "merged-%d", a);
609 return rv;
610 }
611
612 static
613 void
614 bin(void)
615 {
616 int infd, outfds[numprocs];
617 const char *name;
618 int i, mykeys, keys_done, keys_to_do;
619 int key, pivot, binnum;
620
621 infd = doopen(PATH_KEYS, O_RDONLY, 0);
622
623 mykeys = getmykeys();
624 seekmyplace(PATH_KEYS, infd);
625
626 for (i=0; i<numprocs; i++) {
627 name = binname(me, i);
628 outfds[i] = doopen(name, O_WRONLY|O_CREAT|O_TRUNC, 0664);
629 }
630
631 pivot = (RANDOM_MAX / numprocs);
632
633 keys_done = 0;
634 while (keys_done < mykeys) {
635 keys_to_do = mykeys - keys_done;
636 if (keys_to_do > WORKNUM) {
637 keys_to_do = WORKNUM;
638 }
639
640 doexactread(PATH_KEYS, infd, workspace,
641 keys_to_do * sizeof(int));
642
643 for (i=0; i<keys_to_do; i++) {
644 key = workspace[i];
645
646 binnum = key / pivot;
647 if (key <= 0) {
648 complainx("proc %d: garbage key %d", me, key);
649 key = 0;
650 }
651 assert(binnum >= 0);
652 assert(binnum < numprocs);
653 dowrite("bin", outfds[binnum], &key, sizeof(key));
654 }
655
656 keys_done += keys_to_do;
657 }
658 doclose(PATH_KEYS, infd);
659
660 for (i=0; i<numprocs; i++) {
661 doclose(binname(me, i), outfds[i]);
662 }
663 }
664
665 static
666 void
667 sortbins(void)
668 {
669 const char *name;
670 int i, fd;
671 off_t binsize;
672
673 for (i=0; i<numprocs; i++) {
674 name = binname(me, i);
675 binsize = getsize(name);
676 if (binsize % sizeof(int) != 0) {
677 complainx("%s: bin size %ld no good", name,
678 (long) binsize);
679 exit(1);
680 }
681 if (binsize > (off_t) sizeof(workspace)) {
682 complainx("proc %d: %s: bin too large", me, name);
683 exit(1);
684 }
685
686 fd = doopen(name, O_RDWR, 0);
687 doexactread(name, fd, workspace, binsize);
688
689 sortints(workspace, binsize/sizeof(int));
690
691 dolseek(name, fd, 0, SEEK_SET);
692 dowrite(name, fd, workspace, binsize);
693 doclose(name, fd);
694 }
695 }
696
697 static
698 void
699 mergebins(void)
700 {
701 int infds[numprocs], outfd;
702 int values[numprocs], ready[numprocs];
703 const char *name, *outname;
704 int i, result;
705 int numready, place, val, worknum;
706
707 outname = mergedname(me);
708 outfd = doopen(outname, O_WRONLY|O_CREAT|O_TRUNC, 0664);
709
710 for (i=0; i<numprocs; i++) {
711 name = binname(i, me);
712 infds[i] = doopen(name, O_RDONLY, 0);
713 values[i] = 0;
714 ready[i] = 0;
715 }
716
717 worknum = 0;
718
719 while (1) {
720 numready = 0;
721 for (i=0; i<numprocs; i++) {
722 if (infds[i] < 0) {
723 continue;
724 }
725
726 if (!ready[i]) {
727 result = doread("bin", infds[i],
728 &val, sizeof(int));
729 if (result == 0) {
730 doclose("bin", infds[i]);
731 infds[i] = -1;
732 continue;
733 }
734 if ((size_t) result != sizeof(int)) {
735 complainx("%s: read: short count",
736 binname(i, me));
737 exit(1);
738 }
739 values[i] = val;
740 ready[i] = 1;
741 }
742 numready++;
743 }
744 if (numready == 0) {
745 break;
746 }
747
748 /* find the smallest */
749 place = -1;
750 for (i=0; i<numprocs; i++) {
751 if (!ready[i]) {
752 continue;
753 }
754 if (place < 0 || values[i] < val) {
755 val = values[i];
756 place = i;
757 }
758 }
759 assert(place >= 0);
760
761 workspace[worknum++] = val;
762 if (worknum >= WORKNUM) {
763 assert(worknum == WORKNUM);
764 dowrite(outname, outfd, workspace,
765 worknum * sizeof(int));
766 worknum = 0;
767 }
768 ready[place] = 0;
769 }
770
771 dowrite(outname, outfd, workspace, worknum * sizeof(int));
772 doclose(outname, outfd);
773
774 for (i=0; i<numprocs; i++) {
775 assert(infds[i] < 0);
776 }
777 }
778
779 static
780 void
781 assemble(void)
782 {
783 off_t mypos;
784 int i, fd;
785 const char *args[3];
786
787 mypos = 0;
788 for (i=0; i<me; i++) {
789 mypos += getsize(mergedname(i));
790 }
791
792 fd = doopen(PATH_SORTED, O_WRONLY, 0);
793 dolseek(PATH_SORTED, fd, mypos, SEEK_SET);
794
795 if (dup2(fd, STDOUT_FILENO) < 0) {
796 complain("dup2");
797 exit(1);
798 }
799
800 doclose(PATH_SORTED, fd);
801
802 args[0] = "cat";
803 args[1] = mergedname(me);
804 args[2] = NULL;
805 execv("/bin/cat", (char **) args);
806 complain("/bin/cat: exec");
807 exit(1);
808 }
809
810 static
811 void
812 checksize_bins(void)
813 {
814 off_t totsize;
815 int i, j;
816
817 totsize = 0;
818 for (i=0; i<numprocs; i++) {
819 for (j=0; j<numprocs; j++) {
820 totsize += getsize(binname(i, j));
821 }
822 }
823 if (totsize != correctsize) {
824 complain("Sum of bin sizes is wrong (%ld, should be %ld)",
825 (long) totsize, (long) correctsize);
826 exit(1);
827 }
828 }
829
830 static
831 void
832 checksize_merge(void)
833 {
834 off_t totsize;
835 int i;
836
837 totsize = 0;
838 for (i=0; i<numprocs; i++) {
839 totsize += getsize(mergedname(i));
840 }
841 if (totsize != correctsize) {
842 complain("Sum of merged sizes is wrong (%ld, should be %ld)",
843 (long) totsize, (long) correctsize);
844 exit(1);
845 }
846 }
847
848 static
849 void
850 sort(void)
851 {
852 unsigned long sortedsum;
853 int i, j;
854
855 /* Step 1. Toss into bins. */
856 doforkall("Tossing", bin);
857 checksize_bins();
858 complainx("Done tossing into bins.");
859
860 /* Step 2: Sort the bins. */
861 doforkall("Sorting", sortbins);
862 checksize_bins();
863 complainx("Done sorting the bins.");
864
865 /* Step 3: Merge corresponding bins. */
866 doforkall("Merging", mergebins);
867 checksize_merge();
868 complainx("Done merging the bins.");
869
870 /* Step 3a: delete the bins */
871 for (i=0; i<numprocs; i++) {
872 for (j=0; j<numprocs; j++) {
873 doremove(binname(i, j));
874 }
875 }
876
877 /* Step 4: assemble output file */
878 docreate(PATH_SORTED);
879 doforkall("Final assembly", assemble);
880 if (getsize(PATH_SORTED) != correctsize) {
881 complainx("%s: file is wrong size", PATH_SORTED);
882 exit(1);
883 }
884
885 /* Step 4a: delete the merged bins */
886 for (i=0; i<numprocs; i++) {
887 doremove(mergedname(i));
888 }
889
890 /* Step 5: Checksum the result. */
891 sortedsum = checksum_file(PATH_SORTED);
892 complainx("Checksum of sorted keys: %ld", sortedsum);
893
894 if (sortedsum != checksum) {
895 complainx("Sums do not match");
896 exit(1);
897 }
898 }
899
900 ////////////////////////////////////////////////////////////
901
902 static
903 const char *
904 validname(int a)
905 {
906 static char rv[32];
907 snprintf(rv, sizeof(rv), "valid-%d", a);
908 return rv;
909 }
910
911 static
912 void
913 checksize_valid(void)
914 {
915 off_t totvsize, correctvsize;
916 int i;
917
918 correctvsize = (off_t) numprocs*2*sizeof(int);
919
920 totvsize = 0;
921 for (i=0; i<numprocs; i++) {
922 totvsize += getsize(validname(i));
923 }
924 if (totvsize != correctvsize) {
925 complainx("Sum of validation sizes is wrong "
926 "(%ld, should be %ld)",
927 (long) totvsize, (long) correctvsize);
928 exit(1);
929 }
930 }
931
932 static
933 void
934 dovalidate(void)
935 {
936 const char *name;
937 int fd, i, mykeys, keys_done, keys_to_do;
938 int key, smallest, largest;
939
940 name = PATH_SORTED;
941 fd = doopen(name, O_RDONLY, 0);
942
943 mykeys = getmykeys();
944 seekmyplace(name, fd);
945
946 smallest = RANDOM_MAX;
947 largest = 0;
948
949 keys_done = 0;
950 while (keys_done < mykeys) {
951 keys_to_do = mykeys - keys_done;
952 if (keys_to_do > WORKNUM) {
953 keys_to_do = WORKNUM;
954 }
955
956 doexactread(name, fd, workspace, keys_to_do * sizeof(int));
957
958 for (i=0; i<keys_to_do; i++) {
959 key = workspace[i];
960
961 if (key < 0) {
962 complain("%s: found negative key", name);
963 exit(1);
964 }
965 if (key == 0) {
966 complain("%s: found zero key", name);
967 exit(1);
968 }
969 if (key >= RANDOM_MAX) {
970 complain("%s: found too-large key", name);
971 exit(1);
972 }
973
974 if (key < smallest) {
975 smallest = key;
976 }
977 if (key > largest) {
978 largest = key;
979 }
980 }
981
982 keys_done += keys_to_do;
983 }
984 doclose(name, fd);
985
986 name = validname(me);
987 fd = doopen(name, O_WRONLY|O_CREAT|O_TRUNC, 0664);
988 dowrite(name, fd, &smallest, sizeof(smallest));
989 dowrite(name, fd, &largest, sizeof(largest));
990 doclose(name, fd);
991 }
992
993 static
994 void
995 validate(void)
996 {
997 int smallest, largest, prev_largest;
998 int i, fd;
999 const char *name;
1000
1001 doforkall("Validation", dovalidate);
1002 checksize_valid();
1003
1004 prev_largest = 1;
1005
1006 for (i=0; i<numprocs; i++) {
1007 name = validname(i);
1008 fd = doopen(name, O_RDONLY, 0);
1009
1010 doexactread(name, fd, &smallest, sizeof(int));
1011 doexactread(name, fd, &largest, sizeof(int));
1012
1013 if (smallest < 1) {
1014 complainx("Validation: block %d: bad SMALLEST", i);
1015 exit(1);
1016 }
1017 if (largest >= RANDOM_MAX) {
1018 complainx("Validation: block %d: bad LARGEST", i);
1019 exit(1);
1020 }
1021 if (smallest > largest) {
1022 complainx("Validation: block %d: SMALLEST > LARGEST",
1023 i);
1024 exit(1);
1025 }
1026
1027 if (smallest < prev_largest) {
1028 complain("Validation: block %d smallest key %d",
1029 i, smallest);
1030 complain("Validation: previous block largest key %d",
1031 prev_largest);
1032 complain("Validation failed");
1033 exit(1);
1034 }
1035 }
1036
1037
1038 for (i=0; i<numprocs; i++) {
1039 doremove(validname(i));
1040 }
1041 }
1042
1043 ////////////////////////////////////////////////////////////
1044
1045 static
1046 void
1047 setdir(void)
1048 {
1049 #if 0 /* let's not require subdirs */
1050 domkdir(PATH_TESTDIR, 0775);
1051 dochdir(PATH_TESTDIR);
1052 #endif /* 0 */
1053 }
1054
1055 static
1056 void
1057 unsetdir(void)
1058 {
1059 doremove(PATH_KEYS);
1060 doremove(PATH_SORTED);
1061 #if 0 /* let's not require subdirs */
1062 dochdir("..");
1063
1064 if (rmdir(PATH_TESTDIR) < 0) {
1065 complain("%s: rmdir", PATH_TESTDIR);
1066 /* but don't exit */
1067 }
1068 #endif /* 0 */
1069 }
1070
1071 ////////////////////////////////////////////////////////////
1072
1073 static
1074 void
1075 randomize(void)
1076 {
1077 int fd;
1078
1079 fd = doopen(PATH_RANDOM, O_RDONLY, 0);
1080 doexactread(PATH_RANDOM, fd, &randomseed, sizeof(randomseed));
1081 doclose(PATH_RANDOM, fd);
1082 }
1083
1084 static
1085 void
1086 usage(void)
1087 {
1088 complain("Usage: %s [-p procs] [-k keys] [-s seed] [-r]", progname);
1089 exit(1);
1090 }
1091
1092 static
1093 void
1094 doargs(int argc, char *argv[])
1095 {
1096 int i, ch, val, arg;
1097
1098 for (i=1; i<argc; i++) {
1099 if (argv[i][0] != '-') {
1100 usage();
1101 return;
1102 }
1103 ch = argv[i][1];
1104 switch (ch) {
1105 case 'p': arg = 1; break;
1106 case 'k': arg = 1; break;
1107 case 's': arg = 1; break;
1108 case 'r': arg = 0; break;
1109 default: usage(); return;
1110 }
1111 if (arg) {
1112 if (argv[i][2]) {
1113 val = atoi(argv[i]+2);
1114 }
1115 else {
1116 i++;
1117 if (!argv[i]) {
1118 complain("Option -%c requires an "
1119 "argument", ch);
1120 exit(1);
1121 }
1122 val = atoi(argv[i]);
1123 }
1124 switch (ch) {
1125 case 'p': numprocs = val; break;
1126 case 'k': numkeys = val; break;
1127 case 's': randomseed = val; break;
1128 default: assert(0); break;
1129 }
1130 }
1131 else {
1132 switch (ch) {
1133 case 'r': randomize(); break;
1134 default: assert(0); break;
1135 }
1136 }
1137 }
1138 }
1139
1140 int
1141 main(int argc, char *argv[])
1142 {
1143 initprogname(argc > 0 ? argv[0] : NULL);
1144
1145 doargs(argc, argv);
1146 correctsize = (off_t) (numkeys*sizeof(int));
1147
1148 setdir();
1149
1150 genkeys();
1151 sort();
1152 validate();
1153 complainx("Succeeded.");
1154
1155 unsetdir();
1156
1157 return 0;
1158 }