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)

   If the code had used free() on blocks allocated using sbrk() the conversion would not have worked.

   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)

   It might make inefficient use of memory is the data segment size is rounded to the next page. In that case, memory allocated by sbrk() would be expected to be allocated in minimum increments of one-page.

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)

   void * lastbyte = (void *)((intptr_t) block + (BLOCKSIZE - 1));
   void * lastbyte = (void *)&((char *)block[BLOCKSIZE - 1];
   void * lastbyte = (void *)((char *)block) + BLOCKSIZE - 1;
   

   Any of the above should work. The assignment to lastbyte is not really part of the required answer but is harmless. If you do this assignment, the casting to (void *) is not required on the second two lines because it is legal to assign any pointer type to a voind pointer variable.

   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)

   void * firstpage = (void *)((intptr_t)block & ~(pagesize - 1));
   

   Strictly speaking, the assignment is not part of the required answer. Note that this only works if pagesize is a power of two, which it will be on any binary computer. Should someone stick us with a decimal computer we'd be in trouble. (Back in the 1950s and 1960s, there were several successful decimal computers).

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

   void * lastpage = (void *)((intptr_t)lastbyte & ~(pagesize - 1));
   

   This uses the value computed in part a, and again, the assignnment is not strictly speaking part of the required answer.

   It's somewhat interesting to note that if firstpage and lastpage are equal, the entire allocated block fit in one page. If they differ, the block spanned at least one page boundary.

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)

   void * next( void * p ) {
           /* first, find the address of the next field */
           intptr_t * nextaddr = (intptr_t *)((intptr_t)p - sizeof(void *));
           /* then get and return the value of that field, without the tag bit */
           return (void *)((* nextaddr) & ~1);
   }
   

   The above code is perehaps bit overcommented, but it does the job.

   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)

   int status( void * p ) {
           /* first, find the address of the next field (this holds the tag) */
           intptr_t * nextaddr = (intptr_t *)((intptr_t)p - sizeof(void *));
           /* then get and return the tag, with the next field zeroed out */
           return int ((* nextaddr) & 1);
   }
   

   This code is only a small variant on part a), and still overcommented.

   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)

   void * previous( void * p ) {
           /* first, find the address of the previous field */
           void ** prevaddr = (void **)((intptr_t)p - 2*sizeof(void *));
           /* then get and return the value of that field */
           return *prevaddr;
   }
   

   The above somewhat overcommented code carefully retains much of the structure of part a), but simplified because the pointer does not need any masking to split off a tag bit.