Return to st_test.c CVS log

Up to [MW Coherent from dump] / coherent / f / etc / conf / streams / src

Annotation of coherent/f/etc/conf/streams/src/st_test.c, revision 1.1

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.