Chapter 9, Problem 9.18HW

Explanation of Solution

Modify the allocator to perform constant-time coalescing requires both a header and a footer for each block:

In the “Section 9.9.12 (mm.c)”, remove the red color text and add the highlighted lines which is represented in the below code. The modified “mm.c” file is as follows:

#define MAX(x, y) ((x) > (y)? (x) : (y))

/* Pack a size and allocated bit into a word */

#define PACK(size, alloc)  ((size) | (alloc))

// Define a pack with size and allocated bit

#define PACK(size, alloc, prev_alloc)  ((size) | (alloc) | (prev_alloc << 1))

/* Read and write a word at address p */

#define GET(p)       (*(unsigned int *)(p))

/* Read the size and allocated fields from address p */

#define GET_SIZE(p)  (GET(p) & ~0x7)

#define GET_ALLOC(p) (GET(p) & 0x1) 

// Define allocated fields

#define GET_PREV_ALLOC(p) ((GET(p) >> 1) & 0x1)

/* Given block ptr bp, compute address of its header and footer */

#define HDRP(bp)       ((char *)(bp) - WSIZE)

if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)

return -1;

PUT(heap_listp, 0);                /* Alignment padding */

PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */

PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */

PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* Epilogue header */

// Call PUT() function for Prologue header

PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1, 1)); /* Prologue header */

// Call PUT() function for Prologue footer

PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1, 1));

// Call PUT() function for Epilogue header

PUT(heap_listp + (3 * WSIZE), PACK(0, 1, 1));

heap_listp += (2 * WSIZE);

/* $end mminit */

return NULL;

/* Adjust block size to include overhead and alignment reqs. */

if (size <= DSIZE)                                        

asize = 2 * DSIZE; 

else

asize = DSIZE * ((size + (DSIZE)+(DSIZE - 1)) / DSIZE);

// Check size to adjust block

if (size <= WSIZE)

// Assign size value

asize = DSIZE;

// Otherwise

else

// Compute size to add overhead and alignment requirements

asize = DSIZE * ((size + (WSIZE)+(DSIZE - 1)) / DSIZE);

/* Search the free list for a fit */

if ((bp = find_fit(asize)) != NULL) { 

}

/* $begin mmfree */

PUT(HDRP(bp), PACK(size, 0));

PUT(FTRP(bp), PACK(size, 0));

// Call PUT() function with size and allocated bit

PUT(HDRP(bp), PACK(size, 0, GET_PREV_ALLOC(HDRP(bp))));

PUT(FTRP(bp), PACK(size, 0, GET_PREV_ALLOC(HDRP(bp))));

// Check allocated bit

if (GET_ALLOC(HDRP(NEXT_BLKP(bp))))

// Call PUT() function

PUT(HDRP(NEXT_BLKP(bp)), PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), 1, 0));

// Otherwise

else {

// Call PUT() function for HDRP

PUT(HDRP(NEXT_BLKP(bp)), PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), 0, 0));

// Call PUT() function for FTRP

PUT(FTRP(NEXT_BLKP(bp)), PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), 0, 0));

}

// Call coalesce() function to fill values

coalesce(bp);

 }

/* $begin mmfree */

static void *coalesce(void *bp)

 {

size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));

// Call GET_PREV_ALLOC() function and the return value is assign to prev_alloc

size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));

size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

size_t size = GET_SIZE(HDRP(bp));

else if (prev_alloc && !next_alloc) {      /* Case 2 */

size += GET_SIZE(HDRP(NEXT_BLKP(bp)));

PUT(HDRP(bp), PACK(size, 0));

PUT(FTRP(bp), PACK(size, 0));

// Call PUT() function for HDRP with PACK size

PUT(HDRP(bp), PACK(size, 0, 1));

// Call PUT() function for FTRP with PACK size

PUT(FTRP(bp), PACK(size, 0, 1));

}

else if (!prev_alloc && next_alloc)

   {

/* Case 3 */

   size += GET_SIZE(HDRP(PREV_BLKP(bp)));

   PUT(FTRP(bp), PACK(size, 0));

   PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));

   // Call PUT() function for HDRP with PACK size

   PUT(FTRP(bp), PACK(size, 0, 1));

   // Call PUT() function for FTRP with PACK size

   PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));

   bp = PREV_BLKP(bp);

   }

else {

/* Case 4 */

   size += GET_SIZE(HDRP(PREV_BLKP(bp))) +

   GET_SIZE(FTRP(NEXT_BLKP(bp)));

   PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));

   PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));

   // Call PUT() function for HDRP with PACK size

   PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));

   // Call PUT() function for FTRP with PACK size

   PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0...