Understanding Malloc

This issue is continuation of previous instalment, i.e. on Simple List Of Blocks. In previous section we saw the logical perspective of SLOB, In this section we would look into the implementation perspective of SLOB.

Data Structure. To start with, lets first derive data structure necessary to make the implementation work.Usually, the correct selection of data structure is the key to designing a good algorithm. To design for SLOB we primarily need two data structures, one is the list holding the chunks of same size and other to hold the chunk frame itself.

The List. Each element in the list needs to be a collection holding at least two elements, namely a variable holding the size of the chunks and other holding the head of the chunk frames. The list we are intending to design could be of two kinds; contiguous and disjoint. Both has its own advantages and disadvantages; the list being contiguous saves space of holding reference to the next element, but at the same time prevents the list from further expansion. In this implementation we would design blocks as disjoint linked list and list as contiguous. This approach imitates the implementation of many real libraries.

struct list {
    unsigned int size; /// holds the size of the blocks.
    void *head;  /// head of list of blocks.
};

The Blocks. When noticed from implementation perspective, the blocks are simply a list that grows and shrinks in horizontal direction, whereas the list holding blocks is represented vertically remains constant. To understand the data structure that defines the notion of blocks , its basically a collection holding a header element, data and a reference to the next element in the list, else next holds NULL. Creating this structure is quite tricky, which we would discuss in the coming sections. For now we will just stick with the declaration of data structure.

struct block {
     struct list *lst; ///the reference to the list the block belongs.
     struct block *nxt; ///reference to nxt block in the list.
     void *block;  ///The block or payload itself.
};

The beginning of the structure holds the reference to the list to which the block belongs, this enables the return to the list( free) a constant operation, then the list holding the reference to the next block, finally the chunk itself which would be returned to the user on malloc.

Construction of Data structure. Before we start addressing the construction of data structure, we need to think of an approach of calling an init function before the main() function.Calling init before main() provides an abstract view of the library calls. Moreover this is the approach almost all library level implementation follows .

To make this work, GCC has a set of compiler directives named as attributes. The attributes extend the language syntax .i.e. Basically instructs the compiler of how the particular function or variable should be altered during compilation or linking phase. To define a attribute:

__attribute__((attribute_list)) <function or variable>.

Of many attribute_list our area of interest is constructor and destructor.

From horse mouth : “The constructor attribute causes the function to be called automatically before execution enters main (). Similarly, the destructor attribute causes the function to be called automatically after main () has completed or exit () has been called”.

To understand the working of the mentioned attributes, let me make a confession about main(). The main is not the first function to execute when you start executing a process, rather there are many other preparation functionalities that execute before and after main().

so giving a rough view of how the main looks in whole picture is

_start     // First symbol to start execution of a process
.        // stored at location 0x080482d0
.
.
call constructors
ret = main();
call destructors
.
.
copy the ret value into parent
signal parent with sigchld 

Though real implementation is much more complex, I presume this level of explanation would suffice for getting a pictorial understanding.

To make this work, the shared object file contains special sections (.ctors and .dtors on ELF) which contain references to the functions marked with the constructor and destructor attributes, respectively. When the library is loaded/unloaded the dynamic loader program (ld.so ) checks whether such sections exist, and if so, calls the functions referenced therein.

Now lets get back to our implementation on construction of data structure. Rough sketch of the implementation would be

create a contiguous list, i.e. an array of list based on number of heterogeneous blocks needed by the process.
For creating each set of homogeneous block, call sbrk() with size as (sizeof(header)+ BLOCK_SIZE) * number of blocks in the set.
now dissect each allocated block into piece of chunk frames.

Lets make this into a small snippet, where initialisation is done with single element on the list.

#define SLOB_LEN 1
struct list slob[SLOB_LEN];
 
__attribute__((constructor)) void init(void)
{
    int i = 0;
    do {
        slob[i].size = 8; /// hard coded for simplicity
        slob[i].head = make_blocks(8, 2, &slob[i]);
        i++;
     } while(i &lt; SLOB_LEN);
}
 
/*
  @ FUNCTION NAME: make_blocks
  @ DESCRIPTION: makes the blocks with given specifications
  @ INPUT: block_size: size of the block
           no_of_blks: count of the blocks
           list      : list to which the block belongs
  @ OUTPUT: returns the starting address of the blocks created
*/
void* make_blocks(const int block_size, const int no_of_blks, struct list* list)
{
    void *chnk = sbrk((block_size + sizeof(struct list)) * no_of_blks);
    int i = 0;
    struct block *blks = NULL;
 
    do {
        struct block *tmp = (struct block*) chnk;  //type cast chnk into header
 
        /* Header construction*/
        tmp->lst = list;
        tmp->nxt = blk;
        /* Block itself*/
        tmp->block = tmp + 1;
        /* prepend to the list*/
        blks = tmp;
 
        chnk = chnk + (sizeof(struct block) + block_size);
        i++;
    } while(i < no_of_blks);
    return blks;
}

This might look little complicated on first sight but on second glance I can guarantee that its pretty straight forward.

Malloc. This is pretty straightforward, just iterate through the list to find the size that best suits. The SLOB is also best fit, because the list would be arranged in ascending order.

void* Malloc(const int size)
{
   int i = 0;
   void *p = NULL;
   do{
      if(slob[i].size >= size) {
         if(slob[i].head) {
             p = slob[i].head->block;
             slob[i].head = slob[i].head->nxt;
         }
      }
i++;
   }while(i < SLOB_LEN);
   return p;
} 

Free. The field in the struct block holding the reference to the list enables return to the list in constant time.

void free(void* blk){
   struct block *p = blk;
   p--;
   p->nxt = p->lst.head->nxt;
   p->lst.head = p;
} 

Conclusion.

To implement SLOB; In advance we need to know the size of the blocks and count of the blocks which is somehow reducing the real dynamism.
SLOB is among the fastest alloc system in the series.
The real implementation can be found at: SLOB

The next article will take us into true dynamism called Buddy system.

References