代写内存分配函数，用来取代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.
