Assignment 8, Solutions

Part of the homework for 22C:112, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: Consider the following implementaton of the C library malloc() function:
    #include <unistd.h>
    void * malloc( int size ) {
            void * p = sbrk( size );
            if (p = -1) {
                    p = NULL;
                    errno = ENOMEM;
            }
            return p;
    }
    

    a) Explain how this works. (0.5 points)

    Each call to malloc() uses sbrk() to increase the size of the static data segment by the requested amount, returning a pointer to the base of the newly allocated region.

    b) Give at least two completely different reasons why this is a bad idea. One reason will become clear if you read the man page for sbrk(). The other reason depends on information in the man page for malloc(). (0.5 points)

    First, this provides no way to deallocate memory except by "cheating" and using a negative size. Cheating in this way allows LIFO (stack-style) allocation and deallocation, but it is dangerous because it is up to the user to decrement the break in step sizes that deallocate entire objects and not just parts of objects.

    Second, on a virtual memory system, the actual segment size is always a multiple of the page size. It is quite likely that sbrk() rounds up the requestd size to the next page size. If this is the case, there can be considerable waste when allocating large numbers of small objects.

  2. Background: The buddy system requires that all memory blocks begin on an address that is a multiple of the block size. This makes it easy to initialize a heap where the heap begins on an address that is a multiple of the heap size. Consider a heap of size 2n bytes beginning at address i×2n. In this case, freelists[n] is set to i×2n and all of the other entries in freelists[] are set to null.

    The Problem Suppose you are on a 32-bit machine with 4-byte pointers and the heap begins at address 50 and runs to address 100. Divide this heap into blocks that meet the constraints of the buddy system and give a plausible set of initial values for the array freelists[], indicating, for each free list, which blocks are in that list. (one point)

    The minimum block size will be 4 bytes, and all addresses must be divisible by 4. So, the initial heap will have:

    50: 2 byte fragment because 50 is not divisible by 4
    52: 4 byte free block
    56: 8 byte free block
    64: 32 byte free block
    96: 4 byte free block

    freelists[0] = NULL
    freelists[1] = NULL
    freelists[2] = 4
    and block 4 contains a pointer to block 96.
    freelists[3] = 56
    freelists[4] = NULL
    freelists[5] = 64

    Background: Consider the problem of exercising a heap implementation. To do this, you need to perform large numbers of allocations and deallocations. Consider the following test program:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main() {
            void * blocks[1000];
            int i;
            for (i = 0; i < 1000; i++) blocks[i] = NULL;
            for (i = 0; i < 100000; i++) {
                    int b = random() % 1000;
                    if (blocks[b] == NULL) {
                            int s = (random() % 1000) + 1;
                            blocks[b] = malloc( s );
                    } else {
                            free( blocks[b] );
                            blocks[b] = NULL
                    }
            }
    }
    

    a) How many bytes, on average, does this test program use from the heap? (0.5 points)

    On the average, each block has a 50% chance of being allocated, in the steady state, so where will typically be 500 allocated blocks. Each block has an average size of 500 bytes, so the average expected demand for memory is 500×500 or 250,000 bytes.

    b) This test program exercises the heap manager, but it does not test the heap manager. To test it, you need to do some computation to prove that each block of memory returned by malloc() is distinct and that, between the time a block of memory is allocated and the time it is deallocated, nothing the heap manager does damages the contents of that block. Suggest how the heap manager could be expanded to demonstrate this. (Don't write code, just outline in a sentence or two what that code would do.) (0.5 points)

    After each block of N bytes is allocated, fill it with a sequence of N one-byte values, where the values used depend on the block size and on the address of the block. For example, for a block of size S starting at address P, if we saved the block size in a second field of each array entry, we coul initialize the bytes in the block to some function of the block size and the starting address. (Any function will do, so pick something easy like the sum mod 256.) Before deallocating a block, we could then check that these values are still there.