Drawing a Boundary Tag Allocator

Some code that can be used in conjunction with the malloc code here. It adds an additional function to draw what the memory sort of looks like according to the boundary-tag allocator. It also tries to make the size of the regions appropriate.

Sample Output :

************
*ssssssssss*  1048568  ( 0x239dff8 )
*          *
*          *
*          *
*          *
*pppppppppp*  55952  ( 0x22aba90 )
*ssssssssss*  55944  ( 0x22aba88 )
*//////////*
*//////////*
*//////////*
*pppppppppp*  3600  ( 0x229ee10 )
*ssssssssss*  3592  ( 0x229ee08 )
*          *
*pppppppppp*  3248  ( 0x229ecb0 )
*ssssssssss*  3240  ( 0x229eca8 )
*//////////*
*//////////*
*pppppppppp*  0  ( 0x229e000 )
************

Additional code, just put this in myAllocator.c, maybe somewhere near the bottom? It will add some warnings about unsafe casting etc.


#define FREE ' '
#define ALLOC '/'
#define PREFIX 'p'
#define SUFFIX 's'
#define EDGE '*'
#define mem0(x) (void*)(x) - (void*)arenaBegin
#define MAXBLOCKS 1000

typedef struct RLine_s{
    int lines, sz;
    BlockPrefix_t *pfx;
}RLine;

//cannot dynamically allocate memory...assumes less than 1000 blocks will be allocated
RLine lpp[MAXBLOCKS];

void printMemLine(char type, int width, void* address){
    assert(width > 2);
    putc(EDGE, stderr);
    int i;
    for(i = 0; i < width - 2; i++) putc(type, stderr);
    putc(EDGE, stderr);
    if(type == PREFIX || type == SUFFIX)
        printf("  %d  ( 0x%x )", mem0((int)address), address);
    printf("\n");
}

int compRLineLoc(void *b, void *a){
    return (void*)((RLine*)a)->pfx - (void*)((RLine*)b)->pfx;
}

int compRLineSize(void *b, void *a){
    return ((RLine*)a)->sz - ((RLine*)b)->sz;
}

/* Draws the arena vertically, with each line representing a pseudo-address
 * The prefixes and suffixes for each block are always drawn along with their
 * addresses, however the size of the regions is somewhat arbitrary. It is true,
 * however that |A| > |B| ==> lines(A) >= lines(B) where A, B are two regions
 * and lines denotes how much space is left between them.
 * 
 * The leftmost address is base-10 and 0 is at arenaBegin, the rightmost is the
 * actual address in memory. 
 * 
 * Example Output: 
 *  ************
 *  *ssssssssss*  1048568  ( 0x225aff8 )
 *  *          *
 *  *          *
 *  *pppppppppp*  3248  ( 0x215bcb0 )
 *  *ssssssssss*  3240  ( 0x215bca8 )
 *  *xxxxxxxxxx*
 *  *pppppppppp*  0  ( 0x215b000 )
 *  ************ 
*/
void visualizeMemory(){
    assert(arenaBegin); //this would be boring if you havent allocated memory
    
    int LINES = 25, WIDTH = 12, rcount = 1, i,j;
    int MAXSZ = 5, smallr;
    int lines_left = LINES - 2;
    
    //count the number of regions
    BlockPrefix_t* p = arenaBegin;
    while((p = getNextPrefix(p)) && ++rcount);
    assert(rcount < MAXBLOCKS); //We do not have enough memory to do this
    lines_left -= 2*rcount;
    
    p = arenaBegin;
    for(i = 0; i < rcount; i++){
        lpp[i].pfx = p;
        lpp[i].sz = computeUsableSpace(p);
        lpp[i].lines = 1;
        p = getNextPrefix(p);
    }
    
    /* An algorithm to make larger regions look larger */
    if (lines_left >= 0){
        qsort(lpp, rcount, sizeof(RLine), compRLineSize);
        smallr = rcount - 1;
        while(lines_left >= 0 && smallr > 0){
            for(i = 0; i < smallr && lines_left>=0; i++){
                if(lpp[i].lines < MAXSZ) lpp[i].lines++;
            }
            smallr--;
        }
    }
    
    //sort them in reverse order of their location, so we can print them backwards
    qsort(lpp, rcount, sizeof(RLine), compRLineLoc);
    
    //do the printing!!!
    printMemLine(EDGE, WIDTH, 0);
    for(i = 0; i < rcount; i++){
        p = lpp[i].pfx;
        printMemLine(SUFFIX, WIDTH, p->suffix);
        for(j = 0; j < lpp[i].lines; j++)
            printMemLine(p->allocated ? ALLOC : FREE, WIDTH, 0);
        printMemLine(PREFIX, WIDTH, p);
    }
    printMemLine(EDGE, WIDTH, 0);
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>