Kernel memory allocation

The kernel should allocate memory dynamically to other kernel subsystems and to user processes. The KMA (kernel memory allocation) API usually consists of two functions:
void* malloc(size_t nbytes);
void free(void* ptr);
There are various issues associated with allocation of memory.
  1. realloc() routine. The size of an already allocated buffer is extended using this routine.
  2. Allocated memory should be aligned for proper access. For most systems, long word alignment is sufficient, but some machines need alignment on an eight-byte boundary.
  3. Some allocation systems require the size of the released buffer supplied as part of free. This allows partial freeing.
In this assignment, you will implement a simple memory allocator.

Your memory allocator

Your memory allocator starts with an inital pool of 1 megabyte. The bookkeeping can be done using additional memory. Your allocator should support the following API.
void* MemAlloc(int n)
Allocate memory of size n and return a pointer to it. Return NULL on error.
int MemFree(void* ptr)
Free the memory region pointed to by ptr. The routine returns the size of the freed region. If ptr does not correspond to a memory object created by MemAlloc, the routine should return -1.
struct memStat* GetStat(void)
Return statistics about the memory usage. The returned structure is defined as
struct memStat {
    int memAllocated;
               /* total size of the memory allocated */
    int memFree;
               /* total size of free regions */
    int minFree;
               /* size of the smallest free region */
    int maxFree;
               /* size of the largest free region */
    int numFrag;
               /* number of fragments in the free region */
}
Sample header and driver files can be found in public/p3 on "ieng9".

Report

A realistic kernel memory allocator should consider lot of issues.
  1. speed of memory allocation
  2. speed of memory release
  3. space wasted due to fragmentation (external and internal)
  4. typical sizes of requests
  5. storing allocator state

    Some allocators keep track of memory allocation information (size, etc.) in extra data structures. Can this information be stored in the memory pool itself? For example, instead of allocating and returning memory, the allocator stores the bookkeeping information in the allocated memory itself. (The size of the allocated region is the size requested + the size of the header.)

        ptr ===>+----------------+                   +----------------+
                |                |                   | header info.   |
                |  allocated     |                   | (size, etc.)   |
                |  memory        |           ptr ===>+----------------+
                |                |                   |                |
                |                |                   |  allocated     |
                +----------------+                   |  memory        |
                                                     |                |
                                                     |                |
                                                     +----------------+
    
    Each scheme has its advantages and disadvantages.
You should read the following papers on realistic memory allocators.
  1. M K McKusick and M J Karels, Design of a general purpose memory allocator for the 4.3BSD UNIX kernel. Avaliable from docs.freebsd.org
  2. R E Barkley and T P Lee, A lazy buddy system bounded by two coalescing delays per class. Available from www.acm.org
Your report should discuss the following issues.
  1. The algorithm used in your memory allocator
  2. The typical statistics of kernel memory requests.
  3. The applicability of your memory allocator to KMA.
  4. The applicability of keeping state information in allocated buffers themselves for KMA.
  5. Advantages and disadvantages of compaction
  6. Discussion of the 4.3BSD memory allocation
  7. Discussion of lazy buddy allocation.
  8. If you were to design a KMA, which scheme (4.3BSD or lazy buddy) would you choose and why?

Submission

Your program should be called memAlloc.c. You should tar your source files, header files, your driver code, and the Makefile to memAlloc.tar. Use bundleP3 to submit the code before 11:59 PM on May 19, 2000.

You should submit your report (of around 8 pages) to Allen Chu during his office hours on May 19, 2000.