Assignment 9, Solutions

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

  1. Background: The classic interface to a buddy system storage manager uses the following interface:
            void * buddyallocate( int i );
            void buddydeallocate( void * b, int i );
    

    These request a block of size s = 2i from the heap and return a block of that size to the heap.

    The classic interface to the heap manager required by C uses the following interface:

            void * malloc( int s );
            void free( void * b );
    

    There are two glaring incompatabilities between these:

    a) Give C code to solve the first problem. (This is code to compute i as a function of s. It can be done with one line of stylistically reasonable C code, assuming all variables are alread declared.) (0.3 points)

    First, a pedantic version of the code:

    int i = 0;
    int twotothei = 1;
    while (twotothei < s) {
            i = i + 1;
            twotothei = twotothei << 1;
    }
    

    The one-line solution (plus a declaration):

    int i = 0;
    while ((1 << i) < s) i++;
    

    A final note: Neither version of this code justifies writing a full-fledged function that is called for the answer for two reasons, first, the function body is very small, and second, it is likely to be called from only one place.

    b) Give C code to solve the second problem. (This will involve a fragment of code from the malloc() routine that communicates with a fragement of code from the free() routine, probably using space in the block of memory allocated by buddyallocate(). (0.3 points)

    /* in malloc */
    p = buddyallocate( i );
    *(intptr_t *) p = i; /* save the block size in the block */
    return (void *)((intptr_t)p + sizeof( intptr_t ));
    
    /* in free */
    p = (void *)((intptr_t)p - sizeof( intptr_t ));
    i = *(intptr_t *) p; /* recover the block size from the block */
    buddydeallocate( p, i );
    

    c) Give the complete code for malloc() and free() incorporating your answers to parts a) and b). This problem does not involve implementing the buddy system, it involves code that calls buddyallocate() and buddydeallocate(), probably fewer than 15 lines of code total. (0.4 points)

    void * malloc( int s ) {
            void * p;
            int i = 0;
            int twotothei = 1;
    
            s = s + sizeof( intptr_t );
            while (twotothei < s) { /* compute i = log2 s */
                    i = i + 1;
                    twotothei = twotothei << 1;
            }
    
            p = buddyallocate( i );
            *(intptr_t *) p = i; /* save the block size in the block */
            return (void *)((intptr_t)p + sizeof(intptr_t));
    }
    
    void free( void * p ) {
            int i;
    
            p = (void *)((intptr_t)p - sizeof(intptr_t));
            i = *(intptr_t *) p; /* recover the block size from the block */
    
            buddydeallocate( p, i );
    }
    

  2. Background: In a boundary tag storage allocator, consider the following design options:
    linking of boundary tags
    Each tag may contain a pointer to just its successor or to both its successor and predecessor.
    linking of free blocks There may be no free list, or a singly linked free list, or a doubly linked free list; in the latter, each free block contains a pointer to both its successor and predecessor.

    Assume you are writing a boundary tag heap manager that uses prompt merger of free blocks. That is, when a block is freed, it is immediately merged with its neighbors if they are free. Also assume that if a free list is used, newly freed blocks (after merging with their free neighbors) are simply placed at the head end of the free list.

    a) Regardless of how the free list is organized, which of the above boundary tag structures will work for this heap manager? For the option that do not work, explain why. (0.3 points)

    Prompt merger requires that, when block is deallocated, the heap manager can immediately locate both the successor and predecessor of the block in the heap. This, in turn, requires pointers to both neighbors (or equivalent data) in each boundary tag. A pointer to just the successor would not suffice because it would prevent the merger of block b with its free predecessor.

    b) Of the options for linking free blocks, which one or ones can be made to work with this heap manager? For the option or options that do not work, explain why. (0.3 points)

    Prompt merger may require deletion of a free block from the middle of the free list, if there is one. This occurs in the case when a block is merged with its free successor s. In that case, s must be deleted from the free list or replaced with the entry for the merged blocks. In either case, we need to modify pointers in the predecessor of s in the free list, and this forces use of a doubly-linked free list. If the free list were singly linked, removal of a block from the middle of the free list would be impossible.

    If there is no free list, prompt merger is easy, merely requiring editing of the boundary tags themselves.

    c) (0.4 points) The options discussed above have an impact on internal fragmentation because they determine the minimum amount of memory that may be returned to the free list when splitting an oversize block. Assuming that you measure memory in units of one pointer, what is the largest internal fragment size for each of the tag and free list options outlined above -- note that there are 6 total options you must cosider, 2 times 3.

    • Singly linked boundary tags, no free list.
      tag size = 1 pointer,
      so the largest internal fragment is less than 1 pointer.
    • Doubly linked boundary tags, no free list.
      tag size = 2 pointers,
      so the largest internal fragment is less than 2 pointers.
    • Singly linked boundary tags, singly linked free list.
      tag size = 1 pointer,
      free list entry = 1 pointer,
      so the largest internal fragment is less than 2 pointers.
    • Doubly linked boundary tags, singly linked free list.
      tag size = 2 pointers,
      free list entry = 1 pointer,
      so the largest internal fragment is less than 3 pointers.
    • Singly linked boundary tags, doubly linked free list.
      tag size = 1 pointer,
      free list entry = 2 pointers,
      so the largest internal fragment is less than 3 pointers.
    • Doubly linked boundary tags, doubly linked free list.
      tag size = 2 pointers,
      free list entry = 2 pointers,
      so the largest internal fragment is less than 4 pointers.

  3. Background: If all free blocks on the heap are aligned to a word boundary on a machine that supports byte addressing, the least significant bit (or bits) of each word pointer will always be zero. This allows us to store the status of each block on the heap in the least significant bit of one of the pointers in the boundary tag.

    Assume that p points to an aligned block of memory, and assume that status is an integer containing the status bit, so the values are either zero or one. Note that <stdint.h> contains a definition for the type intptr_t, an integer type that is able to hold one pointer.

    a) Give C code to pack status into the least significant bits of p. (0.3 points)

    p = (void *)((intptr_t)p | status);
    

    b) Give C code to extract status from the least significant bits of p. (0.3 points)

    status = (intptr_t)p & 1;
    

    c) Give C code to erase the status bit from p so that it may be safely used as a pointer on a machine that does not ignore the least significant bits of pointers. (0.4 points)

    p = (void *)((intptr_t)p & ~1);
    

    Note that ~1 is the one's complement of one, which has all bits set to one except for the least significant bit.