![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to st_test.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / f / etc / conf / streams / src|
Return to st_test.c CVS log | Up to [MW Coherent from dump] / coherent / f / etc / conf / streams / src |
1.1 root 1: #include <stdio.h>
2: #include <stdlib.h>
3:
4: #include <kernel/st_alloc.h>
5:
6:
7: /*
8: * Work around some deficiencies in the UNIX library w.r.t. Borland.
9: */
10:
11: #if __BORLANDC__
12:
13: #define RANDOM(n) random (n)
14: #define RANDOMIZE() randomize ()
15:
16: #else
17:
18: /*
19: * While this function is not part of POSIX, many implementations provide
20: * it; random (n) returns a random integer in the range of 0 to (n - 1).
21: *
22: * Note that (rand () % n) is not a sufficient implementation, as the
23: * distribution of (rand () % n) will not be uniform for n not a power of 2.
24: * For instance, with n = 2*RAND_MAX/3, using the modulus will cause the
25: * numbers from 0 to RAND_MAX/2 - 1 to occur twice as often as the second
26: * half of the range.
27: *
28: * The expression "(int) ((long) rand () * range / (RAND_MAX + 1))" as used
29: * by Borland works to distribute the error uniformly across the range 0 to
30: * n-1, but still can cause certain numbers to have a higher probability
31: * than their neighbours.
32: *
33: * The following system minimizes the error at the expense of execution
34: * time by simply throwing away those numbers that cause the error, ie those
35: * numbers from RAND_MAX down to RAND_MAX - ((RAND_MAX + 1) % n). A more
36: * efficient system might use more bits from the LCG, but this works fine.
37: */
38:
39: static int RANDOM (int range) {
40: int error, num;
41:
42: if (range <= 0)
43: return 0;
44:
45: error = ((unsigned) RAND_MAX + 1) % range;
46:
47: while ((num = rand ()) > RAND_MAX - error)
48: ;
49:
50: return num % range;
51: }
52:
53: #include <time.h>
54:
55: /*
56: * And similarly for the randomize () function, which kicks off random number
57: * generation.
58: */
59:
60: static void RANDOMIZE (void) {
61: srand ((int) time (NULL));
62: }
63:
64: #endif /* ! __BORLANDC__ */
65:
66:
67: /*
68: * Dump some arena internals out...
69: */
70:
71: void st_dump (_ST_HEAP_CONTROL_P q) {
72: _ST_ADDR_T scan = _ST_HEAP_FIRST (q, 0);
73: int count, size, cntl;
74:
75: do {
76: size = count = 0;
77: while (! _ST_BLOCK_FREE (cntl = _ST_BLOCK_CONTROL (q, scan))) {
78: size += _ST_BLOCK_SIZE (cntl);
79: count ++;
80: if (_ST_HEAP_NEXT (scan, cntl) >= q->_arena_end)
81: break;
82: scan = _ST_HEAP_NEXT (scan, cntl);
83: }
84: printf ("%d allocated blocks of total size %d\n", count, size);
85:
86: if (! _ST_BLOCK_FREE (cntl))
87: break;
88:
89: size = count = 0;
90: while (_ST_BLOCK_FREE (cntl = _ST_BLOCK_CONTROL (q, scan))) {
91: size += _ST_BLOCK_SIZE (cntl);
92: count ++;
93: if (_ST_HEAP_NEXT (scan, cntl) >= q->_arena_end)
94: break;
95: scan = _ST_HEAP_NEXT (scan, cntl);
96: }
97: printf ("%d free blocks of size %d\n", count, size);
98: } while (_ST_HEAP_NEXT (scan, cntl) < q->_arena_end);
99: }
100:
101: /*
102: * Dump a small selection of buckets in great detail.
103: */
104:
105: void st_detail (_ST_HEAP_CONTROL_P q, int frombkt, int tobkt) {
106: _ST_ADDR_T scan = _ST_HEAP_FIRST (q, frombkt);
107: int i;
108:
109: while (scan < _ST_HEAP_FIRST (q, tobkt + 1)) {
110: if ((i = _ST_HEAP_BUCKET (q, scan)) >= frombkt)
111: while (frombkt <= i)
112: printf ("\nBucket %d, %d biggest free, entry @ %04x : ",
113: frombkt ++,
114: _ST_HEAP_BIGGEST (q, frombkt + q->_buckets_inuse),
115: scan);
116: i = _ST_BLOCK_CONTROL (q, scan);
117: printf (_ST_BLOCK_FREE (i) ? "Free %04x (%d) : " :
118: "Used %04x (%d) : ",
119: scan, _ST_BLOCK_SIZE (i));
120: scan = _ST_HEAP_NEXT (scan, i);
121: }
122: }
123:
124:
125: /*
126: * An assertion mechanism for testing the allocator.
127: */
128:
129: #define ASSERT(q,x,i) (! (x) ? st_fatal (q,i, __LINE__) : (void) 0)
130:
131: static void st_fatal (_ST_HEAP_CONTROL_P q, int i, int line) {
132:
133: printf ("Assertion failure at line %d of file " __FILE__ "\n", line);
134: printf ("Iteration number #%d\n", i);
135:
136: st_dump (q);
137:
138: abort ();
139: }
140:
141:
142: /*
143: * Exercise the heap allocator. We exercise the allocator down to the last
144: * byte, and define the following relationships so we can assume that by the
145: * time we have done TEST_ALLOCS allocations of TEST_ALLOC_SIZE, then we have
146: * consumed all free memory.
147: *
148: * The _ST_WORD_T factor in the TOTALWORDS calculation is for the block
149: * headers used internally by the allocator. The _ST_ADDR_T factor is for the
150: * addr [] array, which is also taken from the managed area. The "+ 2" factor
151: * is for the block headers for (i) the dummy block at the start of the arena
152: * and (ii) the block header for the addr [] block.
153: */
154:
155: #define TEST_ALLOCS 2000 /* number of allocations */
156: #define TEST_ALLOC_SIZE 16 /* in bytes */
157: #define SEGMENTS 256 /* how many partitions in the space */
158:
159: #define TOTALWORDS (TEST_ALLOCS * (TEST_ALLOC_SIZE + sizeof (_ST_WORD_T)\
160: + sizeof (_ST_ADDR_T)) / sizeof (_ST_WORD_T)\
161: + 2)
162:
163: void main (int argc, char ** argv) {
164: _ST_HEAP_CONTROL_P q;
165: void * mem;
166: _ST_ADDR_T * addr;
167: int i, base, leave;
168: int forward = 0, back = 0, shuffle = 1;
169: int growup = 1, growdown = 1, growboth = 1, growmove = 1, shrink = 1;
170:
171: RANDOMIZE ();
172:
173: printf ("TOTALWORDS = %d\n", TOTALWORDS);
174:
175: for (i = 1 ; i < argc ; i ++)
176: if (argv [i][0] == '-')
177: switch (argv [i][1]) {
178:
179: case 'f':
180: forward = argv [i][2] == 0 ? 1 : atoi (argv [i] + 2);
181: break;
182:
183: case 'b':
184: back = argv [i][2] == 0 ? 1 : atoi (argv [i] + 2);
185: break;
186:
187: case 'r':
188: shuffle = argv [i][2] == 0 ? 1 : atoi (argv [i] + 2);
189: break;
190:
191: case 'l':
192: leave = argv [i][2] == 0 ? 1 : atoi (argv [i] + 2);
193: break;
194: }
195:
196: q = (_ST_HEAP_CONTROL_P) malloc (_ST_HEAP_CONTROL_SIZE (SEGMENTS));
197: mem = malloc (TOTALWORDS * sizeof (_ST_WORD_T));
198:
199: st_ctor (q, SEGMENTS, TOTALWORDS, (_ST_ADDR_T) mem);
200:
201: st_assert (q);
202:
203: printf ("Using qheap : ");
204:
205: /*
206: * Initially, why not get this space from the test arena ?
207: */
208:
209: addr = (_ST_ADDR_T *) st_new (q, TEST_ALLOCS * sizeof (* addr));
210:
211:
212: /*
213: * Exercises for realloc (), growing blocks up.
214: */
215:
216: while (growup -- > 0) {
217: for (i = 0 ; i < TEST_ALLOCS ; i ++) {
218: addr [i] = st_new (q, TEST_ALLOC_SIZE);
219: ASSERT (q, addr [i] != NULL, i);
220: }
221:
222: for (i = 0 ; i < TEST_ALLOCS ; i += 2) {
223: ASSERT (q, st_disp (q, addr [i + 1]
224: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
225:
226: addr [i + 1] = st_realloc (q, addr [i], 2 * TEST_ALLOC_SIZE
227: ST_FREE_SIZE (TEST_ALLOC_SIZE));
228: ASSERT (q, addr [i + 1] == addr [i], i);
229:
230: ASSERT (q, st_disp (q, addr [i]
231: ST_FREE_SIZE (2 * TEST_ALLOC_SIZE)) == 0, i);
232: }
233: }
234:
235: st_dump (q);
236:
237:
238: /*
239: * Exercises for realloc (), growing blocks down.
240: */
241:
242: while (growdown -- > 0) {
243: _ST_ADDR_T temp;
244:
245: for (i = 0 ; i < TEST_ALLOCS ; i ++) {
246: addr [i] = st_new (q, TEST_ALLOC_SIZE);
247: ASSERT (q, addr [i] != NULL, i);
248: }
249:
250: temp = addr [0];
251:
252: for (i = 0 ; i < TEST_ALLOCS - 1 ; i += 2) {
253: ASSERT (q, st_disp (q, addr [i]
254: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
255:
256: /* put a pattern in the block to be moved */
257:
258: * addr [i + 1] = (_ST_WORD_T) addr [i + 1];
259:
260: ASSERT (q,
261: st_realloc (q, addr [i + 1], 2 * TEST_ALLOC_SIZE
262: ST_FREE_SIZE (TEST_ALLOC_SIZE))
263: == temp, i);
264:
265: /* check that the data was moved correctly */
266:
267: ASSERT (q, * temp == (_ST_WORD_T) addr [i + 1], i);
268:
269: ASSERT (q, st_disp (q, temp
270: ST_FREE_SIZE (2 * TEST_ALLOC_SIZE)) == 0, i);
271:
272: if (st_assert (q) != 0) {
273: printf ("error %s, i = %d\n",
274: _ST_HEAP_ERROR (q), i);
275: st_dump (q);
276: return;
277: }
278:
279: }
280: }
281:
282: st_dump (q);
283:
284:
285: /*
286: * Exercises for realloc (), growing blocks both up and down.
287: */
288:
289: while (growboth -- > 0) {
290:
291: for (i = 0 ; i < TEST_ALLOCS ; i ++) {
292: addr [i] = st_new (q, TEST_ALLOC_SIZE);
293: ASSERT (q, addr [i] != NULL, i);
294: }
295:
296: for (i = 0 ; i < TEST_ALLOCS - 3 ; i += 4) {
297: ASSERT (q, st_disp (q, addr [i]
298: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
299:
300: if (st_assert (q) != 0) {
301: printf ("st_disp () #1 error %s, i = %d\n",
302: _ST_HEAP_ERROR (q), i);
303: st_dump (q);
304: return;
305: }
306:
307: ASSERT (q, st_disp (q, addr [i + 2]
308: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
309:
310: if (st_assert (q) != 0) {
311: printf ("st_disp () #2 error %s, i = %d\n",
312: _ST_HEAP_ERROR (q), i);
313: st_dump (q);
314: return;
315: }
316:
317: /* put a pattern in the block to be moved */
318:
319: * addr [i + 1] = (_ST_WORD_T) addr [i + 1];
320:
321: ASSERT (q, st_realloc (q, addr [i + 1], 3 * TEST_ALLOC_SIZE
322: ST_FREE_SIZE (TEST_ALLOC_SIZE))
323: == addr [i], i);
324:
325: /* check that the data was moved correctly */
326:
327: ASSERT (q, * addr [i] == (_ST_WORD_T) addr [i + 1], i);
328:
329: if (st_assert (q) != 0) {
330: printf ("error %s, i = %d\n",
331: _ST_HEAP_ERROR (q), i);
332: st_dump (q);
333: return;
334: }
335: }
336:
337: for (i = 0 ; i < TEST_ALLOCS - 3 ; i += 4) {
338: ASSERT (q, st_disp (q, addr [i]
339: ST_FREE_SIZE (3 * TEST_ALLOC_SIZE)) == 0, i);
340: ASSERT (q, st_disp (q, addr [i + 3]
341: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
342: }
343: }
344:
345: st_dump (q);
346:
347:
348: /*
349: * Perform a given number of allocations and shuffled decallocations,
350: * leaving behind a certain number of allocated blocks to clutter the
351: * arena for the next set.
352: */
353:
354: leave = base = 0;
355: while (shuffle -- > 0) {
356: for (i = base ; i < TEST_ALLOCS ; i ++) {
357: addr [i] = st_new (q, TEST_ALLOC_SIZE);
358: if (st_assert (q) != 0) {
359: printf ("Alloc error %s, %d blocks remaining",
360: _ST_HEAP_ERROR (q), i);
361: return;
362: }
363: ASSERT (q, addr [i] != NULL, i);
364: }
365:
366: base = shuffle > 0 ? leave : 0;
367:
368: for (i = TEST_ALLOCS ; i -- > base ;) {
369:
370: /*
371: * Pick an element to free, then exchange that for
372: * the last element, thereby shortening the list.
373: */
374:
375: int elem = RANDOM (i + 1);
376: ASSERT (q, st_disp (q, addr [elem]
377: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
378: if (st_assert (q) != 0) {
379: printf ("Free error %s, %d blocks remaining",
380: _ST_HEAP_ERROR (q), i);
381: return;
382: }
383: addr [elem] = addr [i];
384: }
385: }
386:
387: st_dump (q);
388:
389:
390: /*
391: * Deallocate from the bottom to the top.
392: */
393:
394: while (forward -- > 0) {
395: for (i = 0 ; i < TEST_ALLOCS ; i ++) {
396: addr [i] = st_new (q, TEST_ALLOC_SIZE);
397: ASSERT (q, addr [i] != NULL, i);
398: }
399:
400: for (i = 0 ; i < TEST_ALLOCS ; i ++)
401: ASSERT (q, st_disp (q, addr [i]
402: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
403: }
404:
405:
406: /*
407: * Deallocate from the top to the bottom.
408: */
409:
410: while (back -- > 0) {
411: for (i = 0 ; i < TEST_ALLOCS ; i ++) {
412: addr [i] = st_new (q, TEST_ALLOC_SIZE);
413: ASSERT (q, addr [i] != NULL, i);
414: }
415:
416: for (i = TEST_ALLOCS ; i -- > 0 ;)
417: ASSERT (q, st_disp (q, addr [i]
418: ST_FREE_SIZE (TEST_ALLOC_SIZE)) == 0, i);
419: }
420: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.