Thoughts on Programming

October 30, 2011

Storage Allocator – “malloc”

Filed under: C — shadiyya @ 6:41 am
Tags: , , ,

The dynamic memory allocator malloc will request space from the operating system as needed rather than allocating from a compiled-in fixed-size array. The storage used by a program can be requested by malloc,but also by other sources, so its memory blocks are basically of three types:

  • Not owned by malloc
  • Owned by malloc which are free
  • Owned by malloc which are in useWhen malloc function is called, the free list is scanned until a big-enough block is found.  (big enough for current data to be stored, a first fit algorithm is used meaning that first free block which has a size larger than the one requested is taken)

There are three possibilities:

  • No free big-enough block found, in this case program must a request another piece of memory from operating system 
  • Found a bigger block than the size requested, in this case only the needed space is used and residue storage is returned to the free list
  • Found a block having exactly the needed size, in this case this block is “unlinked” from the free list

When free is called, corresponding “freed” block is added to the free list at proper place. If the block being freed is adjacent to a free block on either side, it is united with it to form a single bigger block, so storage does not become too fragmented. Determining the adjacency is easy because the free list is maintained in order of decreasing address.

Every free block contains three fields as shown in the picture below: a pointer to the next block, the size of the block, and the free space itself.
The control information at the beginning is called the “header” that contains a union of a structure and alignment type. To simplify alignment, all blocks are multiples of the header size.

In malloc, the requested size in characters is rounded up to the proper number of header-sized units; the block that will be allocated contains one more unit, for the header itself, and this is the value recorded in the size field of the header.

For the first call of malloc, a list that contains one block of size zero, and points to itself is created. The free list is then searched for a free block of required size. The search begins at the point where the last block was found. If a too-big block is found, the tail end is returned to the user; in this way the header of the original block needs only to have its size adjusted. In all cases, the pointer returned to the user points to the free space within the block, which begins one unit beyond the header.

             

If no adequate memory block is found, then the function obtains storage from the operating system using the UNIX system call sbrk(). sbrk returns -1 if there is no space.Since asking the system for memory is a comparatively expensive operation, we don’t want to do that on every call to malloc, so the function requests at least NALLOC units which is a larger quantity; this larger block will be chopped up as needed. The extra space is inserted into the free list. It scans the free list, starting at the point where a free block was found the last time, looking for the place to insert the free block. This is either between two existing blocks or at the end of the list. In any case, if the block being freed is adjacent to either neighbor, the adjacent blocks are combined and thus prevents memory becoming too fragmented.

Advertisements

Blog at WordPress.com.

%d bloggers like this: