Dynamic Storage Allocation Source Code Test Program

Article

Organization

Home » Linoleum Source Code » Dynamic Storage Allocation » Source Code Test Program

Scope

This is the source code of the Dynamic Storage Allocation Test Program, testing the Dynamic Storage Allocation library, implemented in the Linoleum programming language.

Author

Herbert Glarner

Usage

This test program tests long-term functionality of the Dynamic Storage Allocation library.

Make sure you have the library named dsa.txt in the same folder as this test program before assembling the latter.

Run the assembled exe.

Source Code

(Longterm test application, using the DSA Library Routines "DSA.txt".)

(*****************************************************************************)
(What is tested)

    (This library does not test the speed of the DSA, it rather visualizes
    fragmentation. Reduction of fragmentation was the primary goal when
    developing the DSA: this test program makes the outcome of these efforts
    visible.)

(*****************************************************************************)
(Usage)

    (The test program runs until either a failure occurs or until any key is
    pressed.

    If there is a failure, the error code is shown in register B: look them up
    in the DSA ERR XXX constants of the DSA library.

    If it is stopped manually by pressing any key, B and A contains the number
    of loop iterations, i.e the number of issued allocations and frees: B
    counts billions, A the portion below the current billion.)

(*****************************************************************************)
(Color interpretation while the test runs)

    (The window maps the portion of the memory allocated by this test program.
    Note, that this is 'upside down': The lowest address of the designated Ram
    is in the upper left corner. Higher addresses grow to the right and down.

    Yellow pixels:
        Assigned userdata; the red pixel before any yellow smaller or larger
        line is the internal memory chunk header.
    Blue pixels:
        Deallocated chunks. Were once in use, but are available for further
        allocations, if the space is suitable. The smaller this is, the less
        fragmentation we have. The blue pixels near the black area is not
        fragmented: that is area returned to the pool; it thus should be
        displayed in black; however, leaving it blue shows, which portion of
        the memory pool was allocated once.
    Black area:
        Available RAM, but was never used so far.

    The small right line at the lower right corner is the AVL Tree 'controller':
        Red pixels indicates the area occipied by existing nodes,
        green shows to what extent the tree ever has grown maximally.
)
(*****************************************************************************)
(Technical description)

    (We allocate 1,600,000 units of RAM and have a pixel area of 400,000 px.
    Each px can take 4 units. The goal of this demonstration is, to in average
    have slightly more than half of the allocated RAM, i.e. > 800,000 units,
    but < 1,600,000 units allocated all the time, including all management
    units.

    We need to store the allocated 'pseudo objects' somewhere, because we need
    their address to deallocate them later on. For this reason, vector
    'dsa chunks' exists.

    The 'pseudo objects', called memory chunks, consist of a chunk header,
    represented by a red pixel, and the effective user data, shown as yellow
    pixels. No use is made of userdata.

    The number of memory chunks and the maximum chunk size shall be
    synchronized such, that in average more than 800,000 units are allocated.
    Because we decide randomly with a probability of 0.5 each, if we allocate
    or free a chunk, the whole area of 1,600,000 units is used as the basis.

    With the completely arbitrary decision to have an average of approx.
    4,000 memory chunks allocated, we can create chunks of an average size of
    approx. 200 units, since 4,000 * 200 = 800,000. Chunk sizes must come in
    multiples of 4 to be represented well on the screen, i.e. 4 units per
    pixel. Thus, the number of /different/ sizes is effectively just 1/4 of
    the maximum chunk size. However, in real it seems to be rare to have so
    many different object sizes. On the other hand, there may be many more
    objects.

    To be able to use the generated random numbers bits, we work with suitable
    powers of 2. Therefore, the test layout is:

        We manage 8,192 chunks. In average 50% = 4,096 are allocated.

        Chunk sizes are in the range of 4...512 in steps of 4. In average a
        chunk's size will be 258.

        With an average chunk size of 258 units and in average 4,096 allocated
        chunks, we will have an average of 258 * 4,096 = 1,056,768 allocated
        units of RAM, plus chunk headers, plus fragmentation, plus the AVL
        'controller'.

    Chunk headers always consume 4 units. They are shown as the red pixel before
    the yellow userdata area.

    Fragmentation is shown with blue pixels. The library was designed with the
    primary goal of keeping fragmentation minimal. The blue area right adjacent
    to the black one is not fragmentation: it is what was returned to the pool
    and should be black, but leaving it in blue shows the highest ever
    allocated addresses.

    The AVL tree controller is negligible. It uses 6 units per existing chunk
    /size/. Since there are a max. of 128 different sizes, the AVL area will
    occupy a maximum of 128 * 6 = 768 units. It is shown in the lower right
    corner, i.e. the 'top' of the dedicated area.)

(*****************************************************************************)
"libraries"

    (=========================================================================)
    (DSA Dynamic Storage Allocation)
    (-------------------------------------------------------------------------)
    (The library which is tested with this test program.)
    (-------------------------------------------------------------------------)
        DSA;
    (=========================================================================)

    (=========================================================================)
    (Random Number Generator)
    (-------------------------------------------------------------------------)
    (We feed the DSA tree with a high number of allocations of random size.
    To generate random sizes, and as well to decide if we allocate or free a
    chunk, we need to generate random numbers. RNG is a very fast Random Number 
    Generator implementation by me, using the Mersenne Twister algorithm from 
    Takuji Nishimura and Makoto Matsumoto. The Linoleum source can be found at 
    following link.
        http://herbert.wikispaces.com/MT19937+Library
    Copy the source and save as 'RNG.txt' in the same folder as this library
    before compiling. Note that you find also a test program for the RNG
    there, if you want to explore the RNG separately.)
    (-------------------------------------------------------------------------)
        RNG;
    (=========================================================================)

(*****************************************************************************)
"directors"
        program name = { DSA Test };
        unit = 32;

    (=========================================================================)
    (Test screen reflecting what's allocated and what's free)
    (-------------------------------------------------------------------------)
        display width = DSA TEST SCREEN WIDTH;
        display height = DSA TEST SCREEN HEIGHT;
    (=========================================================================)

(*****************************************************************************)
"constants"                             (Convention: "DSA ...", UPPER CASE)

    (=========================================================================)
    (Define the size of the testing screen here. 800 * 500 are 400,000 pixels.)
    (-------------------------------------------------------------------------)
        DSA TEST SCREEN WIDTH = 500;
        DSA TEST SCREEN HEIGHT = 800;
    (=========================================================================)

    (=========================================================================)
    (We define the RAM so, that 4 units are represented by 1 pixel. If the
    defined screen is 400,000 pixels large, then this would be 1,600,000 units
    or 6,400,000 bytes.)
    (-------------------------------------------------------------------------)
        DSA TEST RAM = DSA TEST SCREEN WIDTH mtp
                       DSA TEST SCREEN HEIGHT mtp 4;
    (=========================================================================)

    (=========================================================================)
    (Define the size of maximally managed memory chunks. Half of these are
    allocated.)
    (-------------------------------------------------------------------------)
        DSA TEST CHUNKS = 8 192;
    (=========================================================================)

(*****************************************************************************)
"variables"                             (Convention: "dsa ...", lower case)

    (=========================================================================)
    (Keeping track of space consumed by the AVL tree)
    (-------------------------------------------------------------------------)
        dsa test last avl tree extent = 0;
    (=========================================================================)

    (=========================================================================)
    (Counting billions of loop iterations for long time tests)
    (-------------------------------------------------------------------------)
        dsa test billions = 0;
    (=========================================================================)

(*****************************************************************************)
"workspace"                             (Convention: "dsa ...", lower case)

    (=========================================================================)
    (Random Number Generator)
    (-------------------------------------------------------------------------)
        rng init key = 4;
    (=========================================================================)

    (=========================================================================)
    (Display area)
    (-------------------------------------------------------------------------)
        dsa window = DSA TEST SCREEN WIDTH mtp DSA TEST SCREEN HEIGHT;
    (=========================================================================)

    (=========================================================================)
    (Managed chunks)
    (-------------------------------------------------------------------------)
        dsa chunks = DSA TEST CHUNKS;
    (=========================================================================)

(*****************************************************************************)
"programme"                             (Convention: "Dsa ...", Mixed case)

    (=========================================================================)
    (Initialize the Random Number Generator for the generation of random keys.)
    (Source of the RNG library: http://herbert.wikispaces.com/MT19937+Library)
    (-------------------------------------------------------------------------)
        [rng init key plus 0] = 123h;
        [rng init key plus 1] = 234h;
        [rng init key plus 2] = 345h;
        [rng init key plus 3] = 456h;
        E = rng init key;                   (Address of init key)
        D = 4;                              (Length of init key)
        => Rng Init;
    (Now each call to 'Rng Long' returns a random number in the range between
    0 and 2^32-1, both values inclusive.)
    (=========================================================================)


    (=========================================================================)
    (Screen init)
    (-------------------------------------------------------------------------)
        [Display Origin] = dsa window;      (Defined in the work area)
    (=========================================================================)


    (=========================================================================)
    (Allocation from memory pool)
    (-------------------------------------------------------------------------)
    (Creating a dedicated DSA space of 1,600,000 Units = approx. 6.4 MB to
    play with allocations and deallocations.)
        D = DSA TEST RAM; => Dsa Create;
        ? failed -> Dsa Test Error;
    (=========================================================================)


    (=========================================================================)
    (Start value for screen updates)
    (-------------------------------------------------------------------------)
        [dsa test last avl tree extent] = [avl tree extent];
    (=========================================================================)


    (=========================================================================)
    (Endless Test loop - BREAK IT BY HITTING ANY KEY)
    (-------------------------------------------------------------------------)
    "Dsa Test Randomize"
        => Rng Long;                        (return a 32 bit random in E)
    (-------------------------------------------------------------------------)
    (The LSB tells us if to allocate or deallocate.)
        ? E + 1 -> Dsa Test Alloc;
    (-------------------------------------------------------------------------)
    ("Dsa Test Free")
        E > 1;                              (1 bit used)
    (The 13 LSB give us an index 0...8191 into the workarea 'dsa chunks'.)
        E & 1111111111111b;                 (Number of vector unit)
        E + dsa chunks;                     (Address of vector unit)
    (If there is not 0 there, it is a memory chunk address, which can be
    deallocated. Else ignore.)
        ? [E] = 0 -> Dsa Test Skip Test Body;
        C = E;                              (Still need address of vector unit)
    (Get its size, then deallocate it.)
        E = [E];                            (Userdata Address of chunk)
        => Dsa Size;                        (The allocated usersize in D)
        ? failed -> Dsa Test Error;
        => Dsa Free;
        ? failed -> Dsa Test Error;
        [C] = 0;                            (Slot available again)
    (Effective size and address)
        D + DSA HEADER SIZE;                (Effective size includes Header)
        E - DSA HEADER SIZE;                (Which is located before userdata)
    (Convert address and size to screen position)
        E - [dsa ram bottom];               (Transpose to range 0...n)
        D > 2; E > 2;                       (4 pixels per unit)
        E + dsa window;                     (Transpose to screen start)
    (Visualize deallocation by making the pixels blue. This has the nice side
    effect, that we can instantly see the highest so far used portion of the
    memory pool, which is interesting especially in long-term tests.)
    "Dsa Test Blue"
        [E] = 00 00 ffh;
        E +;
        D ^ Dsa Test Blue;
        -> Dsa Update Avl;                  (Update AVL Tree area now)
    (-------------------------------------------------------------------------)
    "Dsa Test Alloc"
        E > 1;                              (1 bit used)
    (The 13 LSB give us an index 0...8191 into the workarea 'dsa chunks'.)
        D = E;
        E & 1111111111111b; E + dsa chunks;
        D > 13;                             (13 bits used)
    (If there is 0 there, it is a free slot and we can allocate it. Else
    ignore.)
        ? [E] != 0 -> Dsa Test Skip Test Body;
        C = E;                              (Unit in workarea vector)
    (We need a random size between approx 1...128. 7 random bits give 0...127.
    Add 1. Then scale by 4. This gives us the chunk's size of 4...512. Each
    pixel represents 4 units.)
        D & 1111111b; D +; D < 2;           (Usable size)
        => Dsa Alloc;                       (E: Userdata address)
        ? failed -> Dsa Test Error;
    (A real application might wish to clear the returned area now. This job
    is not done by 'Dsa Alloc', because often it does not matter, as the user
    writes his data into the whole content anyway. Doing so in any case would
    just cost performance for nothing. However, if the user needs to have this
    area clean, 'Dsa Clear' is to be called now.)
        (E = E;)                            (Is in place as 'Dsa Alloc' result)
        (=> Dsa Clear;)                     (This test does not write userdata)
    (Store address into workarea vector to be able to free it later)
        [C] = E;
    (Effective size and address)
        D + DSA HEADER SIZE;                (Effective size includes Header)
        E - DSA HEADER SIZE;                (Which is located before userdata)
    (Convert address and size to screen position)
        E - [dsa ram bottom];               (Transpose to range 0...n)
        D > 2; E > 2;                       (4 pixels per unit)
        E + dsa window;                     (Transpose to screen start)
    (Visualize allocation by making the pixels yellow, except the first pixel,
    which is in red to give an idea what amount the chunk headers consume in
    relation to the yellow area.)
        [E] = ff 00 00h;
        E +; D -;
    "Dsa Test Yellow"
        [E] = ff ff 00h;
        E +;
        D ^ Dsa Test Yellow;
        (-> Dsa Update Avl;)                    (Update AVL Tree area now)
    (-------------------------------------------------------------------------)
    "Dsa Update Avl"

    (With a max. of 128 different sizes {4...512 in steps of 4}, there can not
    be more than 128 AVL nodes. They consume a max. of 6*128=768 units from the
    RAM. At a displayed resolution of 4 units per pixel, the max. consumed area
    is 192 px, which at a screen width of 500 px is just about 2/5 of a line.
    It is visible in the lower right corner. The max area ever consumed is
    shown in green, the actually consumed area in red.)

    (If the AVL tree has grown, i.e. is smaller than before, then the growth
    between [dsa test last avl tree extent] and [avl tree extent] is shown in
    red pixels. If it shrunk, then the area returned to the pool now unused
    area becomes green.)
        ? [avl tree extent] = [dsa test last avl tree extent]
                                                        -> Dsa Avl Updated;
        ? [avl tree extent] > [dsa test last avl tree extent]
                                                        -> Dsa Avl Not Grown;
    ("Dsa Avl Grown")
        E = [avl tree extent];
        D = [dsa test last avl tree extent];
        D - E;
    (Convert address and size to screen position)
        E - [dsa ram bottom];               (Transpose to range 0...n)
        E > 2;                              (4 pixels per unit)
    (1 node = 6 units consumes 1.5 pixels, 2 nodes = 12 units consume 3 pixels 
    etc.)
        D + 2;                              (AVL nodes are 6 units, round up)
        D > 2;                              (4 pixels per unit)
        E + dsa window;                     (Transpose to screen start)
    "Dsa Test Red"
        [E] = ff 00 00h;
        E +;
        D ^ Dsa Test Red;
        -> Dsa Avl Updated;
    (-------------------------------------------------------------------------)
    "Dsa Avl Not Grown"
        E = [dsa test last avl tree extent];
        D = [avl tree extent];
        D - E;
    (Convert address and size to screen position)
        E - [dsa ram bottom];               (Transpose to range 0...n)
        E > 2;                              (4 pixels per unit)
        D + 2;                              (AVL nodes are 6 units, round up)
        D > 2;                              (4 pixels per unit)
        E + dsa window;                     (Transpose to screen start)
    "Dsa Test Green"
        [E] = 00 ff 00h;
        E +;
        D ^ Dsa Test Green;
        (-> Dsa Avl Updated;)
    "Dsa Avl Updated"
        [dsa test last avl tree extent] = [avl tree extent];
    (-------------------------------------------------------------------------)
    "Dsa Test Skip Test Body"

    (Update screen every 4096th alloc/free call only: its still more fps
    than our eyes can handle.)

    (TOO SEE THE DSA WORKING IN TRUE SLOW MOTION, COMMENT THE FOLLOWING LINE
    OUT.)
        ? A + 111111111111b -> Dsa Test Skip Retrace;
    (-------------------------------------------------------------------------)
    (Update the screen.)
        [Display Command] = RETRACE;
        isocall;
    (-------------------------------------------------------------------------)
    (Allow user to exit the loop by hitting any key.)
        [Console Command] = GETCONSOLEINPUT;
        isocall;
        ? ok -> Dsa Test End;               (Break on any key)
    (-------------------------------------------------------------------------)
    "Dsa Test Skip Retrace"
    (Count number of done allocs/frees. Whole billions and fragments below a
    billion are counted separately. However, these numbers are not suitable
    for speed measurements.)
        A +;
        ? A < 1 000 000 000 -> Dsa Test Randomize;
        [dsa test billions] +;              (Counts billions)
        A = 0;                              (Counts fragments of billions only)
        -> Dsa Test Randomize;
    "Dsa Test End"
    (=========================================================================)


    (=========================================================================)
    (Destroy the DSA area, must return ok)
    (-------------------------------------------------------------------------)
        => Dsa Destroy;
        ? failed -> Dsa Test Error;
    (=========================================================================)

    (=========================================================================)
    (If we arrive here, there were no errors in all test phases)
    (-------------------------------------------------------------------------)
    (When breaking manually, we arrive here. B contains completed billions of
    test loops, or 0 if none completed yet; A the number within the begun
    billion. Calculate the total number of loop iterations with B*10^9 + A.)
        B = [dsa test billions];
        -> Dsa Test Exit;
    (=========================================================================)

"Dsa Test Error"
    (=========================================================================)
    (Error handling.)
    (-------------------------------------------------------------------------)
    (If NOT breaking manually, but the program interrupts itself, the error
    number with the reason for the interruption will be displayed in B. This
    will most likely be 8, the constant for DSA ERR OUT OF MEMORY. This
    happens, when the memory pool and the AVL tree area would have overlapped
    each other. With the original settings, this won't happen within a really
    long time, if ever.)
        B = [dsa error];                (Maintain test phase in A)
        -> Dsa Test Exit;
    (=========================================================================)

"Dsa Test Exit"
    (=========================================================================)
        show registers;                 (A = B = 0 if no errors)
    (=========================================================================)

(*****************************************************************************)

Linoleum Syntax Highlighting produced with LSH (© 2007 by Herbert Glarner)