Assignment 9 Solutions, due Apr. 6

#define FREEMAX -----
word freelists[FREEMAX]

word buddyalloc( word i ) {
    if (i >= FREEMAX) {
        return NULL;
    } else if (freelists[i] == NULL)
        word p = buddyalloc(i + 1);
        if (p != NULL) {
            word b = p | (1 << i);
            *b = NULL;
            freelists[i] = b;
        }
        return p;
    } else {
        word p = freelists[i];
        freelists[i] = *p;
        return p;
    }
}

A problem: This is not legal C. In C, pointers must have a specific type that is not an integer type. Rewrite this code as legal C, using an appropriate integer for integers, an appropriate pointer type for pointers, and explicit casting to convert between types where needed. Note that the include file <stdint.h> includes the integer type intptr_t that is guaranteed to be the same number of bits as a pointer. (1 point)

#define FREEMAX -----
void * freelists[FREEMAX];

void * buddyalloc( word i ) {
    if (i >= FREEMAX) {
        return NULL;
    } else if (freelists[i] == NULL)
        void * p = buddyalloc(i + 1);
        if (p != NULL) {
            void * b = (void *)(
                ((intptr_t)p) | (1 << i)
            );
            *(void **)b = NULL;
            freelists[i] = b;
        }
        return p;
    } else {
        void * p = freelists[i];
        freelists[i] = *(void **)p;
        return p;
    }
}

#define STATUSFREE 0
#define STATUSUSED 1
struct tag {
    struct tag * next;
    int status;
};

struct tag * heap;

void free( void * p ) {
    struct tag * ptag = ((struct tag *)p) - 1; /****/
    ptag -> status = STATUSFREE;
}

void * malloc( size_t s ) {
    struct tag * ptag = heap;
    for (;;) { /* loop exit is by return */
        if (ptag == NULL) return NULL;
        if (ptag->status == STATUSFREE) {
            struct tag * pnext = ptag->next;
            while (pnext->status == STATUSFREE) {
                pnext = pnext->next;
            }
            ptag->next = pnext;
        }
        ----- block of missing code -----
        ptag = ptag->next;
    }
    return NULL;

a) One line above is marked with a comment /****/. Explain how this line guarantees that the tag and the user's block of memory do not overlap. This hinges on an eccentric feature of C (and C++) array semantics. (0.5 points)

    struct tag * ptag = ((struct tag *)p) - 1; /****/

The term ((struct tag *)p) is a pointer to an item of type struct tag. Incrementing or decrementing a pointer of a particuar pointer type always adjusts the pointer by the size of the item it points to, so given that p is a pointer, p+1 is equivalent to &p[1] and p-1 is equivalent to &p[-1]. The net result, in the above case, is that ptag always points to the tag before the place where p pointed.

b) Concisely describe the initial structure of the heap? How many tags are in the heap, which tag does the pointer heap point to, and how are these tags linked, which pointers are NULL and what are the status fields of the tags? (0.5 points)

You need an initial tag at the start of the heap and a second tag at the end. The heap pointer points to the first tag. The next field of the first tag refers to the second tag. The next field of the second tag is NULL. The status of the first tag is free, indicating that the entire body of the heap is free. The status of the second tag is used, in order to prevent the second tag from ever being a candidate for use.

An aside: An erroneous program could somehow manufacture a pointer to the second tag and then free it, causing untold damage to the heap, but such an error is unlikely.

c) Describe the block policy decisions inherent in this heap manager. Is it lazy or prompt? Is it first-fit or best-fit? (0.5 points)

It must be a lazy heap manager, since deallocated blocks are merely marked as free and abandoned by free(). This is confirmed because the code for merger is included in the fragment of malloc() given.

From the code given, it is difficult to tell if it is first-fit or best-fit, but the merger code keeps merging adjacent free blocks without regard to the size of the merged result, something you would not expect in a best-fit allocator. Therefore, it seems more likely that this would be part of a first-fit allocator that occasionally merges free blocks to make an excessively large free block and then splits off what is required.

d) What does the missing block of code do? (0.5 points)

The missing block of code looks at the current block and, if it is free and big enough, does an allocation. In the process, if the block is large enough, it splits the block before returning the user's pointer pointer to the allocated part of the block.