Assignment 9, due Mar. 30

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background: The malloc() routine in the C standard library uses the sbrk() Unix/Linux kernel call to allocate space for the heap. If the default heap was 10000 bytes, for example, and if heapptr was the pointer to the start of the heap, then it would use heapptr=sbrk(10000) to initialize the heap pointer.

   Suppose you used sbrk() instead of malloc() to allocate memory for dynamically created objects in your application. Assume you make this change, without making any other changes, and your code still works. Also assume that your program uses large numbers of small objects.

   a) There must be some heap manager function your code did not use. What function? (0.5 points)

   b) Given what you know about how the memory management unit and the implementation of the data segment in modern Unix/Linux systems, what can you conclude about the efficiency of your program after you make the changes described here? (0.5 points)

2. Background: Consider the following code to allocate a block of memory and find out how big a page is on this machine:

   void * block = malloc( BLOCKSIZE );
   int pagesize = getpagesize();
   void * firstpage = ...
   void * lastpage = ...
   

   Obviously, the address of the first byte in the block is the value of the pointer block itself.

   Note: For some of what follows, you will need to convert between values of type void * and integer values. The type intptr_t, defined in <stdint.h>, is the preferred integer type to use for this.

   a) Give a valid C expression to compute of type void * that gives the address of the last byte in the block. (0.2 points)

   b) Give a valid C expression giving the value of firstpage, the address of the page containing the first byte of the block. (0.4 points)

   c) (0.4 points) Give a valid C expression giving the value of lastpage, the address of the page containing the last byte of the block.

3. Background: Consider a boundary tag heap manager where each tag contains a pointer to the tag for the next block, a pointer to the tag for the previous block, and the status of the block (free or in use). Pointers are one word each, but because the size of each block is always in integer number of words (in order to guarangee that the pointers are aligned on word boundaries), the least significant bit of each pointer can be used. Therefore, boundary tags in this system have the following form:

    __________________________________
   |____________previous______________|-2
   |_____________next_______________|t|-1
   |          this block              | 0
   

   previous: a full word pointer to the previous block
   next: a full word pointer to the next block except the least significant bit
   t: a one bit tag, where 1 means in use, 0 means free.

   In the following, assume that the address of a block is always a void* pointer to the first word of the block itself. Use types void* and intptr_t, where possible, to make your code work with any word size. The next pointer and tag bit is always the word just before the block, and the previous pointer is always the word before that.

   a) Give code for next(p), a function that, given the pointer to a block, returns the pointer to the next block. (0.4 points)

   b) Give code for status(p), a function that, given the pointer to a block, returns the tag bit (0 or 1). (0.3 points)

   c) Give code for previous(p), a function that, given the pointer to a block, returns a pointer to the previous block. (0.3 points)