Description

Introduction 

In this assignment, you will implement a dynamic memory allocator suitable for replacing malloc() for heap memory in a Unix process. You will learn about dynamic memory management, pointer manipulation, and pointer casting. The type of allocator you will implement is a pool allocator, using multiple memory pools. Each memory pool consists of allocations of a fixed size. Allocations are served out of the smallest pool that supports the user’s request, and allocations too large for any memory pool are requested from the OS directly. The memory pools in this project will contain allocations ranging from 32 bytes to 4096 bytes. Your allocator is designed in such a way that you will be able to use it to run standard Unix binaries! Because you will not be implementing support for concurrency, some programs may fail through no fault of your own; however, many programs will operate correctly. You may find it interesting and enjoyable to use your allocator implementation to learn about the memory accesses of standard applications. This document is long, but there is a reason for that. Please read it carefully and in its entirety before starting your assignment! There are many subtle requirements in this document that will require critical thinking about program structure; for example, the relationship between allocation sizes and the free list table. Plan to sit down and draw out your data structures and implementation when you begin. You will not “save time” by skipping this step!

1 Getting Started 

You should have received a GitHub Classroom invitation for this assignment. Follow it, then check out your repository. Chapter 9, Section 9.9 of Computer Systems: A Programmer’s Perspective describes a dynamic allocator implementation in some detail. You may want to read this section before starting your project, and will certainly want to read it carefully while implementing your project. Chapter 8, Section 8.7 of The C Programming Language also describes a dynamic allocator of similar structure to that described in CS:APP. This allocator is described in somewhat less detail, but uses techniques (such as declaring structures to hold metadata, rather than using macros and pointer math) that are to be preferred over the approach in CS:APP, so you should read and try to understand it, as well. Again, you may want to read this section before you begin, and will certainly want to read it carefully during implementation. You will absolutely need to read man 3 malloc. It is not long. We will not answer questions that are clearly answered in man 3 malloc. Some parts of this handout may not make much sense until you have read the above readings.

2 Pool Allocators 

Pool allocators are designed to allow applications to efficiently allocate, free, and reallocate chunks of memory in sizes that they use frequently. This is an effective strategy for many applications because it is common for an application to allocate many objects that are the same size — for example, nodes in a linked list or tree, or buffers for communication. Placing such frequently-used objects in a pool where they can be rapidly reallocated improves application performance. Allocation pools are maintained by requesting large-ish blocks of memory from the operating system, then breaking those blocks up into the allocation size stored in a pool. These “free” blocks are then used to serve allocations requested by the user. When blocks are freed by the user, they are simply placed back in the pool, preventing future allocations from having to request more memory from the operating system. When an allocation is requested from a pool that does not contain any free blocks, the allocator will request another large chunk from the operating system to be broken up again. 1