2009-12-02

Post date: Dec 3, 2009 4:22:24 AM

    • Discussed yet another memory allocator implementation (see mm.c attached).
      • Object is prefixed with a size_t header regardless it's free or not. The first word of free object is also used to store the "next object" pointer. Allocated objects do not have a next pointer. The free objects form a singly linked list.
      • Does not sort objects to address order.
      • Splits large objects into smaller ones.
      • No coalescing.
      • LIFO (as opposed to first fit).
    • Demonstrated that the allocator works with a simple program "tac" which reads each line from stdin into memory and prints them out last line first.
      • Compile tac.c against standard C malloc: gcc -o tac tac.c
      • Compile tac.c against mm.c implementation: gcc -DUSE_MM -o tac tac.c
    • Possible improvements:
      • Calling mm_malloc() with request n >= ZONE_SIZE causes infinite loop. However, using a ZONE_SIZE that is too big will penalize your utilization score. This should be an easy fix.
      • Currently all objects are sizeof(size_t) aligned. Will need to modify pointer arithmetic to make it align to 8 bytes on any architecture. The malloclab requires all objects to be 8-byte aligned.
      • Deferred coalescing: wait until the free list runs out; before asking for more memory from sbrk(), perform a merge sort, then coalesce all coalesceable free blocks in one pass.
      • The malloc() routine spends most of its time searching through the linear free list, which is O(n). Use a log(n) time lookup data structure such as binary search tree.
      • Approximate best fit strategy using segregated size class bins. See the design of Doug Lea malloc for some ideas. The "hash table" like data structure could provide close to O(1) malloc(), and best fit is known to minimize fragmentation.
      • To improve small object allocation, consider a special "headerless" class that is simply an array of same-sized small objects.
    • Note: if you want to use this mm.c with malloclab, remember to reinitialize mm_first_free to NULL in mm_init(). Otherwise mdriver will clear the heap and cause objects already in the free list to be freed again, creating a cyclic list that causes infinite loop in mm_malloc().