代写内存分配函数，用来取代glibc中的malloc()和free().
Learning Goals
The purpose of this program is to help you understand the nuances of building a memory allocator, to further increase your C programming skills by working a lot more with pointers and to start using Makefiles.
Specifications
For this assignment, you will be given the structure for a simple shared library that is used in place of the heap memory allocation functions malloc() and free(). You’ll code two functions in this library, named Mem_Alloc() and Mem_Free().
Memory Allocation Background
Memory allocators have two distinct tasks. First, the memory allocator asks the operating system to expand the heap portion of the process’s address space by using the sbrk() system call, but we’ll use mmap() to simulate a heap in the memory mapped area. Second, the memory allocator doles out this memory to the calling process that requests heap memory. This involves managing a list of free memory blocks. When the process requests memory the allocator searches that list for a free block that is large enough to satisfy the request and marks it as allocated. When the process later frees memory, the allocator marks that block as free.
This memory allocator is usually provided as part of a standard library rather than being part of the operating system. Thus, the memory allocator operates entirely within the virtual address space of a single process and knows nothing about which physical pages have been allocated to this process or the mapping from virtual addresses to physical addresses.
The C programming language defines its allocator with the functions malloc() and free() found in “stdlib.h” as follows:
- void *malloc(size_t s): allocates s bytes and returns a pointer to the allocated memory. The memory is not cleared.
- void free(void *ptr): frees the memory pointed to by ptr that was previously allocated by malloc() (or calloc() or realloc()). Otherwise, undefined behavior occurs as it also does or if an attempt is made to free an allocation more than once. If ptr is NULL, the function does nothing and simply returns.
Understand the Code
Copy the entire contents from following directory into your working directory for this assignment:
/p/course/cs354-skrentny/public/code/p3
In this directory you’ll find the files named “Makefile”, “mem.c” and “mem.h” as well as a directory named “tests”. In “mem.c” is the completed codefor two functions: Mem_Init(int sizeOfRegion) and Mem_Dump(). Look at these functions to understand what they do and how they do it. Also note the global block header pointer list_head is the head of our linked list of memory blocks, where each block would be marked as either free or allocated. Very carefully read the comments for the provided block header structure to understand the conventions used in this program. These functions we’ve completed are described below:
Mem_Init(int sizeOfRegion)
This function sets up and initializes the “heap” space that the allocator will manage. sizeOfRegion is the number of bytes desired for the heap.
This function should be called once at the start of any main program before calling any of the other allocator functions. In your main programs to test your code call this function first to initialize enough space so that subsequent calls to Mem_Alloc() function properly. The test main programs we’ve provided (discussed below) already do this.
Note that for improved performance, Mem_Init(int sizeOfRegion) rounds up the amount memory requested to the nearest page so it is possible that more memory might be allocated than originally specified by sizeOfRegion. All of this memory is initialized as the first and only block in the free list to be used by your allocator and is accessed via list_head, which will be pointing to that block’s header. This is the free list that your allocator uses to allocate blocks via Mem_Alloc() calls. Your allocator will need to divide this block into smaller pieces as memory is requested.
Mem_Dump()
This function is used for debugging. It prints the list of all the memory blocks (both free and allocated). Use this to determine if your code works properly. Implementing functions like this are very helpful and well worth your time when working on complex programs. It produces lots of useful information about the data structure so take a closer look at what it does.
Implement the Allocator
Note: Do not change the interface. Do not change anything within file “mem.h”. Do not change any part of functions Mem_Init() or Mem_Dump().
Write the code to implement Mem_Alloc() and Mem_Free(). Use best fit placement policy when allocating blocks with Mem_Alloc() and splitting the block if possible. When freeing memory, use immediate coalescing with the adjacent memory blocks if they’re free. Recall that list_head is the free list structure as defined and described in the file “mem.c”. It uses ideas as discussed in lecture (textbook in section 9.9.6) but adds a next pointer in the headers in order to make it easier to traverse through the free list. We’ll also use address ordering of the blocks in this list.
The functions you’ll code are described below:
void *Mem_Alloc(int size):
This function is similar to the C library function malloc(). It returns a pointer to the start of allocated payload of size bytes. The function returns NULL if there isn’t a free block large enough to satisfy the request. Note we won’t request more memory from the OS than what’s originally allocated by Mem_Init(). Mem_Alloc() returns single word (4 bytes) aligned chunks of memory, which improves performance. For example, a request for 1 byte of memory uses 4 bytes - 1 byte for the payload and 3 bytes for padding to achieve word alignment. To verify that you’re returning 4-byte aligned pointers, you can print the pointer in hexadecimal this way:
printf("%08x", ptr)
The last digit displayed should be a multiple of 4 (that is, 0, 4, 8, or C). For example, 0xb7b2c04c is okay, and 0xb7b2c043 indicates a problem with your alignment.
Once the best fitting free block is located we’ll split the block in two to minimize internal fragmentation. The first part becomes the allocated block, and the remainder becomes a new free block. If the remaining free block doesn’t meet the minimum size (the header plus its minimum payload of 4 bytes) then don’t split the block. Note, you are not to remove the final allocated block from the list of blocks.
int Mem_Free(void *ptr)
This function is similar to the C library function free(). It frees the block of heap memory containing ptr’s payload and returns 0 to indicate success. Before you free a block, you must check that ptr is indeed pointing to the payload of a previously allocated block. If it is not, then the function just returns -1 to indicate failure. If ptr is NULL the function just returns -1. When freeing a block you must coalesce it with its adjacent blocks that are free. Remember, this leaves only one header in the coalesced free block.
Test the Code
You have a provided a file, named “Makefile”, that is used to compile your code in “mem.c” and “mem.h” into a shared library named “libmem.so”. To compile, enter the command make on the Linux command line while you are working in your project directory.
Once the shared library is created, you can then test if your allocator works properly by writing a test main program. Your test program links in this shared library, and makes calls to the functions Mem_Alloc() and Mem_Free(). We’ve already written some small programs that do this, and to help you get started in writing your own tests. Our test programs are in the “tests” subdirectory that you copied along with a second Makefile used to compile those test using the same make command.
You’ll also find the file “testlist.txt” that contains a brief description of the tests we provided ordered by increasing difficulty. Please note that these tests are not exhaustive. They cover a good range of test cases, but there will be additional tests that we’ll use to grade your code. To compile these tests change your working directory to the “tests” subdirectory and enter make on the Linux command line. This will make executables for all the test programs in this directory and link them to the shared library that you’ve compiled beforehand.
Notes and Hints
- Keep in mind that the value of size_status excludes the space for the block header. Make use of sizeof(block_header) to set the appropriate size of requested block.
- Write and thoroughly test small helper functions for common bitwise operations and checks. For example, code a helper isFree() that checks the block header bit to see if a block is free, setFreed() to set that bit to the freed state, setAllocated() to set that bit to the allocated state.
- Double check your pointer arithmetic. (int*)+1 changes the address by 4, (void*)+1 and (char*)+1 changes it by 1. What does (block_header*)+1 change it by?
- For main programs that you write to test your allocator, make sure you call Mem_Init() first to allocate the initial space.
- Check return values for all function calls to make sure you don’t get unexpected behavior.
- Incrementally build up your program by testing against the tests in the order that they are listed in “testlist.txt”. For e.g, focus on making sure your best fit algorithm is correct before you implement coalescing.