Malloc and Memory Management

#CS252#Computer-Science

Explicit Memory Management §

• We call malloc() to get memory at runtime
• In explicit memory managment, a program frees objects explicitly with free() or delete
• The program uses a “malloc library” usually provided by the C standard library
  • Memory is requested from the OS and added to a free list
  • Subsequent requests are then pulled from the free list
  • Free/delete returns memory to the free list
  • Memory is requeste from the OS in large chunks
    • This decreases the number of times that memory is requested from the OS
    • It is difficult to return memory to the OS since the OS handles memory in pages, and the memory allocater handles memory in bytes
  • When the memory allocator runs out of memory in the free list it callls sbrk(s)
    • sbrk(s) increases the size of the heap by s bytes and returns a pointer to the old heap limit
    • You can shrink the heap and decrease its size with a negative size in sbrk()

Malloc Implementations §

• There are several data structures that can be used for memory allocation
• In our lab we used Boundary Tags and Segregated Free Lists based on Dog Lea’s memory allocator used in Linux

Single Free List Implementation §

• Here all the free memory is stored in one free list
• Each chunk in the free list has a header with the size of the chunk and a pointer to the next one
• During allocation, a chunk of the right size is searched for, split if necessary, and returned to the user with the remainder returned to the free list
• When an object is freed, the free list is traversed to find the right place of insertion and its coalesced if possible
• If the request cannot be satisfied in the existing free list, the allocator gets memory from the OS
• Memory is requested in larger chunks so as to reduce the amount of times it is requested
• There are two primary allocation policies
  • First fit: Use the first chunk in the free list that satisfies the request
    • Faster
    • If the search always starts at the beginning, then there will end up being a lot of small objects at the beginning
    • An alternative is Next fit: like first fit except it starts where the last search ended, solving the above issue
  • Best fit: Choose the smallest chunk that satisfies the request
    • Uses less space

Segregated Free Lists §

• There are multiple free lists for different sizes of blocks
• 
• Very often the sizes are powers of two
• Objects are allocated from the free list of the nearest size
• If a free list is empty, the allocator gets more memory and populates the free list
• Some implementations don’t coalesce and just leave objects at the set size
• Coalescing an object would require traversing all the blocks to find out if neighboring blocks are free
• Segregated free list allocators are fast but use a lot more memory
• The BSD UNIX allocator uses segregated free lists

Boundary Tags §

• Boundary tags allow identifying the neighboring objects in O(1), which allows coalescing of objects in O(1)
• Each object, whether allocated or free, has a header
  • Each object is delimited by a footer as well, the header of the next object
• The header contains the size of the object, the size of the object before, as well as a flag that tells whether the object is allocated
• When freeing an object, this lets us check if the neighbors are free and coalesce them easily
• 
• When the object is free, the header also contains a pointer to the next object in the list and a pointer to the previous object in the list
  • This allow removal of an object in the middle of a list from a list in constant time

Allocation Algorithm §

1. Round up the requested size to the next 8 byte boundary (if size == 0 assume 1 byte data)
2. Add the size of the header:
   • real_size = rondup8(requested size) + sizeof(header)
3. Search for the first object that is large enough to satisfy the request and split it. Use on portion of the object to satisfy the allocation request and return the reaminder to the free list
4. If the remainder is smaller than the size of the header plus the next/prev pointers making the object unusable, then do not split the object and use the entire object to satisfy the allocation
5. If there is not enough memory in the free lists to satsify the allocation, request more from the OS using sbrk(). Roudn up the request of memory to the OS to the arena size. Request mulotiple times from the OS if the ojbect is larger than the arena.

Free Algorithm §

1. Check the header of the left neighbor object (the object just befojre the object being freed) to see if it is also free. If that is the case, remove the left neighbro from its free list using the previous/next pointers and coalesce this object with the object being freed
2. Check the right neighbor object to see if it is also freee. If that is the case remove it from its free list and coalesce it
3. Place the freed object in the corresponding free list and update the header and header of the next object

Fenceposts §

• If an object is freed at the beginning of the heap, your allocator will try and coalesce beyond the beginning of the heap
• There is also a chance other libraries call sbrk() causing a whole in the heap
• To prevent coalescing with memory beyond our chunks, we set a fencepost that is flagged as allocated at the ends of the chunks.
• If two chunks are consecutive, we remove the fenceposts between them.

Memory Allocation Errors §

Memory Leaks §

• When objects in memory are not freed, but no longer in use by the program
• This causes excessive memory usage and eventual running out of physical memory
• Server programs often need to be restarted due to slowdowns from memory leaks
• These are usually problems for long lived applications (24/7)
• Memory leaks a re a “slow but persistent disease”

while (1) { 
	ptr = malloc(100);
}

Premature Frees §

• When an object that is still in use is freed
• Also called a “Use After Free” error
• The freed object is added to the free list, modifying the pointers
• If the object is then modified, the next/prev pointers may be overwritten causing further calls to malloc/free to crash
• Premature frees are often hard to debug because the crash can happen far away from the source of the error
• They also lead to security vulnerabilities

int * p = (int *)malloc(sizeof(int));
* p = 8;
* free(p); // free adds object to free list
// updating next and prev 
… 
*p = 9; // next ptr will be modified. 
… 
int q = (int *)malloc(sizeof(int)); // this call or other future malloc/free 
// calls will crash because the free list is corrupted

• To minimize the impact of premature frees (and double frees) set p=NULL after its freed

Double Free §

• Double free caused by freeing an object that is already free
• This can cause the object to be added to the free list twice, corrupting the free list
• After a double free, future calls to malloc/free may crash

int * p = (int *)malloc(sizeof(int));
...
free(p);
...
free(p);

• You can also mitigate the problem by assigning NULL to p after freeing it

Wild Frees §

• Wild frees happen when a program frees something that was not returned by malloc
• Since the memory doesn’t come from malloc, it doesn’t have a header
• This can lead free to crash, and even if it succeeds it will corrupt the free list, causing future calls to crash
• Memory allocated with malloc() should only be deallocated with free() and memory allocated with new should only be deallocated with delete
• Wild frees are also called “free of non-heap objects”

int q;
int * p = &q;
free(p);

Memory Smashing §

• Memory smashing is what happens when less memory is allocated than the memory that is used
• Also called a “Heap Buffer Overflow” memory error
• Causes overwriting the header of the object that follows, corrupting the free list
• Subsequent calls may crash
• Sometimes the smashing happens in the unused portion of the object, causing no immediate errors

char * s = malloc(8);
strcpy(s, "hello world cs252 students");
// allocating less memory for the string than the memory being used
// which will overwrite the pointers of the object AFTER s