/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- geti
- markblock
- checkblock
- test1
- test2
- test3
- test4
- test567
- test5
- test6
- test7
- dotest
- 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 * malloctest.c
32 *
33 * This program contains a variety of tests for malloc and free.
34 * XXX most tests leak on error.
35 *
36 * These tests (subject to restrictions and limitations noted below) should
37 * work once user-level malloc is implemented.
38 */
39
40 #include <stdint.h>
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <unistd.h>
44 #include <fcntl.h>
45 #include <err.h>
46
47
48 #define _PATH_RANDOM "random:"
49
50 #define SMALLSIZE 72
51 #define MEDIUMSIZE 896
52 #define BIGSIZE 16384
53 #define HUGESIZE (1024 * 1024 * 1024)
54
55 /* Maximum amount of space per block we allow for indexing structures */
56 #define OVERHEAD 32
57
58 /* Point past which we assume something else is going on */
59 #define ABSURD_OVERHEAD 256
60
61 static
62 int
63 geti(void)
64 {
65 int val=0;
66 int ch, digits=0;
67
68 while (1) {
69 ch = getchar();
70 if (ch=='\n' || ch=='\r') {
71 putchar('\n');
72 break;
73 }
74 else if ((ch=='\b' || ch==127) && digits>0) {
75 printf("\b \b");
76 val = val/10;
77 digits--;
78 }
79 else if (ch>='0' && ch<='9') {
80 putchar(ch);
81 val = val*10 + (ch-'0');
82 digits++;
83 }
84 else {
85 putchar('\a');
86 }
87 }
88
89 if (digits==0) {
90 return -1;
91 }
92 return val;
93 }
94
95 ////////////////////////////////////////////////////////////
96
97 /*
98 * Fill a block of memory with a test pattern.
99 */
100 static
101 void
102 markblock(volatile void *ptr, size_t size, unsigned bias, int doprint)
103 {
104 size_t n, i;
105 unsigned long *pl;
106 unsigned long val;
107
108 pl = (unsigned long *)ptr;
109 n = size / sizeof(unsigned long);
110
111 for (i=0; i<n; i++) {
112 val = ((unsigned long)i ^ (unsigned long)bias);
113 pl[i] = val;
114 if (doprint && (i%64==63)) {
115 printf(".");
116 }
117 }
118 if (doprint) {
119 printf("\n");
120 }
121 }
122
123 /*
124 * Check a block marked with markblock()
125 */
126 static
127 int
128 checkblock(volatile void *ptr, size_t size, unsigned bias, int doprint)
129 {
130 size_t n, i;
131 unsigned long *pl;
132 unsigned long val;
133
134 pl = (unsigned long *)ptr;
135 n = size / sizeof(unsigned long);
136
137 for (i=0; i<n; i++) {
138 val = ((unsigned long)i ^ (unsigned long)bias);
139 if (pl[i] != val) {
140 if (doprint) {
141 printf("\n");
142 }
143 printf("FAILED: data mismatch at offset %lu of block "
144 "at 0x%lx: %lu vs. %lu\n",
145 (unsigned long) (i*sizeof(unsigned long)),
146 (unsigned long)(uintptr_t)pl,
147 pl[i], val);
148 return -1;
149 }
150 if (doprint && (i%64==63)) {
151 printf(".");
152 }
153 }
154 if (doprint) {
155 printf("\n");
156 }
157
158 return 0;
159 }
160
161 ////////////////////////////////////////////////////////////
162
163 /*
164 * Test 1
165 *
166 * This test checks if all the bytes we asked for are getting
167 * allocated.
168 */
169
170 static
171 void
172 test1(void)
173 {
174 volatile unsigned *x;
175
176 printf("*** Malloc test 1 ***\n");
177 printf("Allocating %u bytes\n", BIGSIZE);
178 x = malloc(BIGSIZE);
179 if (x==NULL) {
180 printf("FAILED: malloc failed\n");
181 return;
182 }
183
184 markblock(x, BIGSIZE, 0, 0);
185 if (checkblock(x, BIGSIZE, 0, 0)) {
186 printf("FAILED: data corrupt\n");
187 return;
188 }
189
190 free((void *)x);
191
192 printf("Passed malloc test 1.\n");
193 }
194
195
196 ////////////////////////////////////////////////////////////
197
198 /*
199 * Test 2
200 *
201 * Tests if malloc gracefully handles failing requests.
202 *
203 * This test assumes that one of the following conditions holds:
204 * 1. swap is not overcommitted; or
205 * 2. user processes are limited to some maximum size, and enough
206 * swap exists to hold a maximal user process.
207 *
208 * That is, it assumes that malloc returns NULL when out of memory,
209 * and that the process will not be killed for running out of
210 * memory/swap at other times.
211 *
212 * If mallocing more memory than the system can actually provide
213 * backing for succeeds, this test will blow up. That's ok, but please
214 * provide a way to switch on one of the above conditions so this test
215 * can be run.
216 *
217 * This test works by trying a huge malloc, and then trying
218 * successively smaller mallocs until one works. Then it touches the
219 * whole block to make sure the memory is actually successfully
220 * allocated. Then it frees the block and allocates it again, which
221 * should succeed.
222 *
223 * Note that this test may give spurious failures if anything else is
224 * running at the same time and changing the amount of memory
225 * available.
226 */
227
228 static
229 void
230 test2(void)
231 {
232 volatile unsigned *x;
233 size_t size;
234
235 printf("Entering malloc test 2.\n");
236 printf("Make sure you read and understand the comment in malloctest.c "
237 "that\nexplains the conditions this test assumes.\n\n");
238
239 printf("Testing how much memory we can allocate:\n");
240
241 for (size = HUGESIZE; (x = malloc(size))==NULL; size = size/2) {
242 printf(" %9lu bytes: failed\n", (unsigned long) size);
243 }
244 printf(" %9lu bytes: succeeded\n", (unsigned long) size);
245
246 printf("Passed part 1\n");
247
248 printf("Touching all the words in the block.\n");
249 markblock(x, size, 0, 1);
250
251 printf("Validating the words in the block.\n");
252 if (checkblock(x, size, 0, 1)) {
253 printf("FAILED: data corrupt\n");
254 return;
255 }
256 printf("Passed part 2\n");
257
258
259 printf("Freeing the block\n");
260 free((void *)x);
261 printf("Passed part 3\n");
262 printf("Allocating another block\n");
263
264 x = malloc(size);
265 if (x==NULL) {
266 printf("FAILED: free didn't return the memory?\n");
267 return;
268 }
269 free((void *)x);
270
271 printf("Passed malloc test 2.\n");
272 }
273
274
275 ////////////////////////////////////////////////////////////
276
277 /*
278 * Test 3
279 *
280 * Tests if malloc gracefully handles failing requests.
281 *
282 * This test assumes the same conditions as test 2.
283 *
284 * This test works by mallocing a lot of small blocks in a row until
285 * malloc starts failing.
286 */
287
288 struct test3 {
289 struct test3 *next;
290 char junk[(SMALLSIZE - sizeof(struct test3 *))];
291 };
292
293 static
294 void
295 test3(void)
296 {
297 struct test3 *list = NULL, *tmp;
298 size_t tot=0;
299 int ct=0, failed=0;
300 void *x;
301
302 printf("Entering malloc test 3.\n");
303 printf("Make sure you read and understand the comment in malloctest.c "
304 "that\nexplains the conditions this test assumes.\n\n");
305
306 printf("Testing how much memory we can allocate:\n");
307
308 while ((tmp = malloc(sizeof(struct test3))) != NULL) {
309
310 tmp->next = list;
311 list = tmp;
312
313 tot += sizeof(struct test3);
314
315 markblock(list->junk, sizeof(list->junk), (uintptr_t)list, 0);
316
317 ct++;
318 if (ct%128==0) {
319 printf(".");
320 }
321 }
322
323 printf("Allocated %lu bytes\n", (unsigned long) tot);
324
325 printf("Trying some more allocations which I expect to fail...\n");
326
327 x = malloc(SMALLSIZE);
328 if (x != NULL) {
329 printf("FAILED: malloc(%u) succeeded\n", SMALLSIZE);
330 return;
331 }
332
333 x = malloc(MEDIUMSIZE);
334 if (x != NULL) {
335 printf("FAILED: malloc(%u) succeeded\n", MEDIUMSIZE);
336 return;
337 }
338
339 x = malloc(BIGSIZE);
340 if (x != NULL) {
341 printf("FAILED: malloc(%u) succeeded\n", BIGSIZE);
342 return;
343 }
344
345 printf("Ok, now I'm going to free everything...\n");
346
347 while (list != NULL) {
348 tmp = list->next;
349
350 if (checkblock(list->junk, sizeof(list->junk),
351 (uintptr_t)list, 0)) {
352 failed = 1;
353 }
354
355 free(list);
356 list = tmp;
357 }
358
359 if (failed) {
360 printf("FAILED: data corruption\n");
361 return;
362 }
363
364 printf("Let me see if I can allocate some more now...\n");
365
366 x = malloc(MEDIUMSIZE);
367 if (x == NULL) {
368 printf("FAIL: Nope, I couldn't.\n");
369 return;
370 }
371 free(x);
372
373 printf("Passed malloc test 3\n");
374 }
375
376 ////////////////////////////////////////////////////////////
377
378 /*
379 * Test 4
380 *
381 * Tries to test in detail if malloc coalesces the free list properly.
382 *
383 * This test will likely fail if something other than a basic first-fit/
384 * next-fit/best-fit algorithm is used.
385 */
386
387 static
388 void
389 test4(void)
390 {
391 void *x, *y, *z;
392 unsigned long lx, ly, lz, overhead, zsize;
393
394 printf("Entering malloc test 4.\n");
395 printf("This test is intended for first/best-fit based mallocs.\n");
396 printf("This test may not work correctly if run after other tests.\n");
397
398 printf("Testing free list coalescing:\n");
399
400 x = malloc(SMALLSIZE);
401 if (x==NULL) {
402 printf("FAILED: malloc(%u) failed\n", SMALLSIZE);
403 return;
404 }
405
406 y = malloc(MEDIUMSIZE);
407 if (y==NULL) {
408 printf("FAILED: malloc(%u) failed\n", MEDIUMSIZE);
409 return;
410 }
411
412 if (sizeof(unsigned long) < sizeof(void *)) {
413 printf("Buh? I can't fit a void * in an unsigned long\n");
414 printf("ENVIRONMENT FAILED...\n");
415 return;
416 }
417
418 lx = (unsigned long)x;
419 ly = (unsigned long)y;
420
421 printf("x is 0x%lx; y is 0x%lx\n", lx, ly);
422
423 /*
424 * The memory should look something like this:
425 *
426 * OXXXOYYYYYYYYYYY
427 *
428 * where O are optional overhead (indexing) blocks.
429 */
430
431 /* This is obviously wrong. */
432 if (lx == ly) {
433 printf("FAIL: x == y\n");
434 return;
435 }
436
437 /*
438 * Check for overlap. It is sufficient to check if the start
439 * of each block is within the other block. (If the end of a
440 * block is within the other block, either the start is too,
441 * or the other block's start is within the first block.)
442 */
443 if (lx < ly && lx + SMALLSIZE > ly) {
444 printf("FAIL: y starts within x\n");
445 return;
446 }
447 if (ly < lx && ly + MEDIUMSIZE > lx) {
448 printf("FAIL: x starts within y\n");
449 return;
450 }
451
452 /*
453 * If y is lower than x, some memory scheme we don't
454 * understand is in use, or else there's already stuff on the
455 * free list.
456 */
457 if (ly < lx) {
458 printf("TEST UNSUITABLE: y is below x\n");
459 return;
460 }
461
462 /*
463 * Compute the space used by index structures.
464 */
465 overhead = ly - (lx + SMALLSIZE);
466 printf("Apparent block overhead: %lu\n", overhead);
467
468 if (overhead > ABSURD_OVERHEAD) {
469 printf("TEST UNSUITABLE: block overhead absurdly large.\n");
470 return;
471 }
472 if (overhead > OVERHEAD) {
473 printf("FAIL: block overhead is too large.\n");
474 return;
475 }
476
477 printf("Freeing blocks...\n");
478 free(x);
479 free(y);
480
481 zsize = SMALLSIZE + MEDIUMSIZE + overhead;
482
483 printf("Now allocating %lu bytes... should reuse the space.\n", zsize);
484 z = malloc(zsize);
485 if (z == NULL) {
486 printf("FAIL: Allocation failed...\n");
487 return;
488 }
489
490 lz = (unsigned long) z;
491
492 printf("z is 0x%lx (x was 0x%lx, y 0x%lx)\n", lz, lx, ly);
493
494 if (lz==lx) {
495 printf("Passed.\n");
496 }
497 else {
498 printf("Failed.\n");
499 }
500
501 free(z);
502 }
503
504 ////////////////////////////////////////////////////////////
505
506 /*
507 * Test 5/6/7
508 *
509 * Generally beats on malloc/free.
510 *
511 * Test 5 uses random seed 0.
512 * Test 6 seeds the random number generator from random:.
513 * Test 7 asks for a seed.
514 */
515
516 static
517 void
518 test567(int testno, unsigned long seed)
519 {
520 static const int sizes[8] = { 13, 17, 69, 176, 433, 871, 1150, 6060 };
521
522 void *ptrs[32];
523 int psizes[32];
524 int i, n, size, failed=0;
525
526 srandom(seed);
527 printf("Seeded random number generator with %lu.\n", seed);
528
529 for (i=0; i<32; i++) {
530 ptrs[i] = NULL;
531 psizes[i] = 0;
532 }
533
534 for (i=0; i<100000; i++) {
535 n = random()%32;
536 if (ptrs[n] == NULL) {
537 size = sizes[random()%8];
538 ptrs[n] = malloc(size);
539 psizes[n] = size;
540 if (ptrs[n] == NULL) {
541 printf("\nmalloc %u failed\n", size);
542 failed = 1;
543 break;
544 }
545 markblock(ptrs[n], size, n, 0);
546 }
547 else {
548 size = psizes[n];
549 if (checkblock(ptrs[n], size, n, 0)) {
550 failed = 1;
551 break;
552 }
553 free(ptrs[n]);
554 ptrs[n] = NULL;
555 psizes[n] = 0;
556 }
557 if (i%256==0) {
558 printf(".");
559 }
560 }
561 printf("\n");
562
563 for (i=0; i<32; i++) {
564 if (ptrs[i] != NULL) {
565 free(ptrs[i]);
566 }
567 }
568
569 if (failed) {
570 printf("FAILED malloc test %d\n", testno);
571 }
572 else {
573 printf("Passed malloc test %d\n", testno);
574 }
575 }
576
577 static
578 void
579 test5(void)
580 {
581 printf("Beginning malloc test 5\n");
582 test567(5, 0);
583 }
584
585 static
586 void
587 test6(void)
588 {
589 int fd, len;
590 unsigned long seed;
591
592 printf("Beginning malloc test 6\n");
593
594 fd = open(_PATH_RANDOM, O_RDONLY);
595 if (fd < 0) {
596 err(1, "%s", _PATH_RANDOM);
597 }
598 len = read(fd, &seed, sizeof(seed));
599 if (len < 0) {
600 err(1, "%s", _PATH_RANDOM);
601 }
602 else if (len < (int)sizeof(seed)) {
603 errx(1, "%s: Short read", _PATH_RANDOM);
604 }
605 close(fd);
606
607 test567(6, seed);
608 }
609
610 static
611 void
612 test7(void)
613 {
614 unsigned long seed;
615
616 printf("Beginning malloc test 7\n");
617
618 printf("Enter random seed: ");
619 seed = geti();
620
621 test567(7, seed);
622 }
623
624 ////////////////////////////////////////////////////////////
625
626 static struct {
627 int num;
628 const char *desc;
629 void (*func)(void);
630 } tests[] = {
631 { 1, "Simple allocation test", test1 },
632 { 2, "Allocate all memory in a big chunk", test2 },
633 { 3, "Allocate all memory in small chunks", test3 },
634 { 4, "Free list coalescing test (first/next/best-fit only)", test4 },
635 { 5, "Stress test", test5 },
636 { 6, "Randomized stress test", test6 },
637 { 7, "Stress test with particular seed", test7 },
638 { -1, NULL, NULL }
639 };
640
641 static
642 int
643 dotest(int tn)
644 {
645 int i;
646 for (i=0; tests[i].num>=0; i++) {
647 if (tests[i].num == tn) {
648 tests[i].func();
649 return 0;
650 }
651 }
652 return -1;
653 }
654
655 int
656 main(int argc, char *argv[])
657 {
658 int i, tn, menu=1;
659
660 if (argc > 1) {
661 for (i=1; i<argc; i++) {
662 dotest(atoi(argv[i]));
663 }
664 return 0;
665 }
666
667 while (1) {
668 if (menu) {
669 for (i=0; tests[i].num>=0; i++) {
670 printf(" %2d %s\n", tests[i].num,
671 tests[i].desc);
672 }
673 menu = 0;
674 }
675 printf("malloctest: ");
676 tn = geti();
677 if (tn < 0) {
678 break;
679 }
680
681 if (dotest(tn)) {
682 menu = 1;
683 }
684 }
685
686 return 0;
687 }
688