Contents

1. Malloc Lab - Initial Step
2. Free List Data Structure
3. Common Macros
4. Linked List Macros
5. Binary Tree Macros
6. Linked List Functions
7. Binary Tree Functions
8. mm_init
9. mm_init
10. Checking mm_init
11. gdb init file
12. Running gdb
13. Testing mm_init

Malloc Lab - Initial Step[top]

---

Free List Data Structure[top]

Decide which data structure you will use to hold the free blocks:

• Doubly linked circular list with head sentinel
• Binary Search Tree

Common Macros[top]

You may want to define a constant PROLOGSIZE to reflect the changed size if you want to use the payload of the prolog block for either the head sentinel of the linked list or the the root pointer of the binary tree.

It will be helpful to define these parameterized macros:

• getsize(x) - extract the size from an integer x that contains both a block size and an allocation bit
• getalloc(x) - extract the allocation (1 or 0) from the integer x that contains both a block size and an allocation bit
• HD(bp) - an alias for the header of a block whose payload is at address bp.
• FT(bp) - an alias for the footer of a block whose payload is at address bp

Linked List Macros[top]

If you are using the linked list data structure, you will need to define these macros

• PREV(bp) - an alias for the previous pointer in the free block whose payload is at address bp
• NEXT(bp) - an alias for the next pointer in the free block whose payload is at address bp

Binary Tree Macros[top]

If you are using the binary tree for the free blocks, you will need to define these macros:

• ROOT() - an alias for the root pointer in the payload of the prolog block
• LEFT(bp) - an alias for the left pointer in the free block whose payload is at address bp
• RIGHT(bp) - an alias for the right pointer in the free block whose payload is at address bp

Linked List Functions[top]

You will need to write functions to manage the free list

• void mm_insert(void *bp) - insert block bp into the free list. (See the specification of mm_insert)
• void mm_remove(void *bp) - remove block bp from the free list.

Binary Tree Functions[top]

If you are using a binary tree for the free blocks, you will need to write functions to manage the binary tree of free blocks:

• void mm_insert(void *bp) - insert block bp into the free list. (See the specification of mm_insert)
• void * mm_findMax(bp)
• void * mm_ceiling(bp, size_t asize)
• void mm_remove(void *bp) - remove block bp from the free list.

mm_init[top]

For step 1, the goal is to modify mm_init to initialize your heap and insert the initial free block into your free block data structure AND to test that it is correct.

For testing mm_init and later functions, you will need to modify the functions:

• void printblock(void *bp)
• void mm_checkheap(int verbose)

You will then use the debugger, gdb, to check that your modifications to mm_init are correct and what you expect.

mm_init[top]

• The Prolog block size should change to be 16 bytes (not 8)

  The initial call to mem_sbrk returns the initial storage for your heap (and stores it in the global variable heap_listp).

  You need 4 bytes for the padding (for alignment), PROLOGSIZE bytes (16) for the prolog block and 4 bytes for the Epilog header.

  Use macros to initialize the prolog header and footer. Be sure to use the correct offset from the beginning of your heap memory.

  Increment heap_listp to point to the payload of the prolog block.

  Use macros to intialize NEXT and PREV fields of the head sentinel (if using a linked list) or ROOT if using a binary search tree.

  Declare a void *bp to hold the return value from extend_heap.

  Call mm_insert(bp) to insert this initial free block into your free block data structure.

Checking mm_init[top]

Compile the malloc lab with the -g option to include debugging information.

• Edit the makefile and change the line:

  	  CFLAGS = -Wall -O2
  	

  to be

  	  CFLAGS = -Wall -g
  	

The first compiles with optimization level 2 (no debuggin info); the second compiles with debugging info (not optimized)

When switching between optimized and debugging versions, be sure to remove the other version by typing

      make clean
    

Then just type

      make 
    

to rebuild using your current settings for CFLAGS.

gdb init file[top]

You may find it handy to have several things automatically defined each time you start gdb.

To do so create a file - say gdbinit - in the malloc lab directory and type in these gdb statements:

      set listsize 35

      define hh
      call mm_checkheap(1)
      end

      b mm_init
      b mm_malloc
      b mm_free
    

As a result, each time you start gdb:

• The default number of lines displayed by the list command will be 35
• hh will be defined as a new gdb command to call the mm_checkheap function with parameter 1
• Break points will be set at mm_init, mm_malloc, and mm_free

Running gdb[top]

Start gdb:

      gdb mdriver
or
      gdb -x gdbinit mdriver    (to read and execute the commands in gdbinit)
    

At the gdb prompt type r to run mdriver optionally with any command line arguments that mdriver accepts (such as -a and -f)

To run mdriver, without checking the team structure, with throughput turned off (debug set to 1) on the sample trace file trace0.rep in the traces subdirectory:

      (gdb) r -a -d 1 -f traces/trace0.rep

    

Common gdb commands

• s step one statement
• n step over one statement
• c continue executing until the next break point
• l list the next listsize ines of source code
• l func_name list source code lines centered at func_name
• l line_number list source code lines centered at line_number
• q quit gdb
• hh call mm_checkheap(1) (if you defined this)

Testing mm_init[top]

After you have made the changes to mm_init (and printblock and mm_checkheap), run the debugger.

After the initializations, execute the hh command to print out your heap before and after the call to extend_heap and after the call to mm_insert.

Check the output printed by hh to see if your initializations and your mm_insert are working as you expect.