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.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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.

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 im- plementation 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 CProgramming 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 allo- cation 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.

You will be implementing a multi-pool allocator, which will maintain pools containing allocation blocks with sizes of powers of two between 25 (32) and 212 (4096). These blocks will be used to serve allocations of 24 (32    8) to 4088 (4096      8) bytes, using the remaining 8 bytes between these sizes and the power of two to store metadata. Because the free() function does not accept a size argument, this metadata will be used to store the size of the block for use by free().  Each allocation request will be served from the smallest block that will store the allocation; for example, a 1 byte allocation would come out of a 32 byte block, while a 1000 byte allocation would come out of a 1024 byte block.

 

3  Requirements

You must implement the following functions in the file src/mm.c:

 

• void *malloc(size_t size)

• void *calloc(size_t nmemb, size_t size)

• void *realloc(void *ptr, size_t size)

• void free(void *ptr)

 

Your implementation must satisfy the standard definition of these functions (see man 3 malloc), with the ex- ception that it need not allow for concurrent access from multiple threads, as well as the additional implementation requirements listed here.

Your implementation must be a multi-pool allocator as described in this document. No other type of allocator implementation will receive credit.  It must use pool allocation as described here to implement all allocations between 1 and 4088 bytes, and a simple bulk allocator (described below) for allocations larger than 4088 bytes. (The discrepancy between 4088 bytes and the even-power-of-two 4096 bytes, mentioned in Section 2, will be further explained later.)

All memory returned by your allocation functions (malloc(), calloc(), and realloc()) must be 8 byte aligned. Failure to maintain this requirement will not result in functional failures of your allocator on the x86-64 plat- form (programs using your allocator would continue to work correctly), but may result in degraded perfor- mance for programs using your allocator. On other platforms, failure to maintain this requirement could result in program crashes.

Your implementation must be able to resize an allocation using realloc.  Under certain circumstances it should do this without performing any new allocation, and under other circumstances it should do this by allocating a new block and copying the user’s data from the old block to the new. If it is possible to perform the reallocation without allocating a new block and moving data, your implementation must do so. This is always possible for reallocations which reduce the size of an allocation, as realloc() can return the existing block, and the user will simply use less of it.  For allocations which increase the size of the allocation, it is possible only if the block originally selected to serve the user’s allocation is also large enough to serve the new allocation. For example, if the user calls malloc(32) to request a 32 byte allocation, your allocator will select a 64 byte block containing 56 usable bytes of memory. If the user later wishes to realloc() this block to 48 bytes, this does not require any allocation or copying, as while 48 bytes is more than the original 32 bytes requested, it is less than the 56 bytes available in this block.

If realloc() cannot resize a block without performing allocation, it must use your allocator to acquire a new block of the appropriate size (which is necessarily larger than the original block), copy the user’s data from the old block to the new block, and then free the old block.

When changing the size of an allocation using realloc(), your implementation must attempt to resize the allocation in place, if possible. For reallocations that reduce the size of the allocation, this should always suc- ceed. For reallocations that increase the size of the allocation, it should succeed if there is sufficient space in the allocated block after the allocation being resized. Only if this is not the case should a new allocation be created and the memory of the original allocation be moved to the new location before freeing the original allocation.

Requests for an allocation of size 0 to any of the allocator functions may either use the pool allocator to create a minimum-size allocation or return NULL, as you prefer. You will probably find that simply returning

 

NULL is easier, but if for some reason your algorithm benefits from the possibility of returning a minimum-size allocation, you may do so.

Your allocator must be capable of returning freed memory to the heap and reusing it to serve future allo- cations. In particular, if a program repeatedly allocates and frees many small objects with a constant upper bound on the number of objects and total space required, your allocator should eventually settle on a heap size that requires no additional requests to the operating system for more memory.

You must test your own project. The tests provided in Autograder will be incomplete, and you should not rely upon them to give more than a rough estimate of your final score. There is no requirement to submit your tests for this project.

 

3.1 Metadata and Global Symbols

As described in CS:APP in Section 9.9, a heap allocator must not use any global state of non-constant size that cannot be allocated from the heap itself. Therefore, you should declare only primitive global (or static) variables for your allocator, and you must use the heap for any other data required. A clever implementation will add a few constant bytes to each allocation and store the rest of its variably-sized metadata in free blocks, requiring only a constant allocation at initialization time for its remaining storage.

 

3.1.1 Static Variables

Any global variables or functions declared by your implementation in mm.c should include the keyword static. This will ensure that they are not visible to any other translation units, and that your allocator’s function cannot be disrupted by code that may link to it. (See Section 4.6 of K&R for more discussion of static variables, and the compiler.pdf slide deck for a definition of translation units.)

 

3.1.2  Block Headers

The metadata stored for each block of memory managed by your allocator (allocated or free) should be a 64 bit header word preceding the allocation (or free block), containing the size of the allocation and some flag bits. Note that the minimum possible block size for the pool-allocated blocks is 25, or 32 bytes, and that all pool- allocated blocks have sizes which are powers of two.  Recalling the format of integers in memory, this means that the lowest five bits of the integer size of a block, whether it is free or allocated, will always be zero. Those bits can therefore be used to store flags, and then masked out when retrieving the size of a block.  CS:APP explains this in some detail in Section 9.9.6 (In particular, see Figure 9.35).

You should use the lowest-order bit (the “ones bit”) to indicate whether a block is free or allocated; a one bit will indicate an allocated block, and a zero bit will indicate a free block. While this is not entirely necessary to complete this project, it makes the implementation of a heap validator (suggested in Section 5) much more effective. Remember to account for this when allocating and freeing bulk-allocated blocks, if necessary. You will probably find that bitwise operations are the best way to maintain the allocated bit and other bits in the size field, rather than using + 1 and - 1 (which has for some reason proven both a popular technique and a popular source of bugs in the past).

The pointer returned by the allocation functions, and the pointer given to free() or realloc(), is the first byte of memory after the header word. Your implementation will have to use pointer math to find the header word for a block that is passed to free() or realloc(), and perhaps to calculate the address to be returned from malloc() et al.

This metadata is the reason that your allocator’s effective allocation sizes are 8 bytes smaller than an even power of two. The block from which an allocation is drawn is a power of two in size, but there are 8 bytes of header used from that block for storing metadata.

 

3.2  The sbrk System Call

The operating system provides two system calls to manipulate the program break between the application’s heap and the unmapped memory region above the heap: brk() and sbrk(). The brk() system call accepts an absolute address and immediately sets the program break to that point, while sbrk() accpets a relative size and adjusts the current program break by that amount. It is difficult to use brk() correctly and safely, so we will use

sbrk() for this assignment.

Passing a positive value to sbrk() causes the system to move the program break the requested number of bytes upward in memory, toward larger addresses. It will then return the old value of the program break, which is a memory address. The newly allocated memory therefore begins at the address returnd by sbrk() and continues for the number of bytes requested by the application.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of