1
\$\begingroup\$

I have implemented malloc and free in C based on first-fit algo and using a circular linked list for free blocks of memory. It seems to be working based on the basic test in the main function. I would appreciate review comments related to coding style, correctness, and performance.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MYHEAPSIZE    2000000         // 2MB
#define MAXALLOCS     120
#define BLOCKOVHEAD   16              // sizeof(node_t*)+sizeof(size_t)
#define MINALLOCSIZE  BLOCKOVHEAD + 8 // +sizeof(long long)
#define ALIGN         8               // 8 bytes =sizeof(long long)

typedef union {
    struct {
        struct node *next;        // pointer to the next free block
        size_t       size;        // size of the whole memory out of system
    } s;
    long long    align;
} header_t;

typedef struct node {
    header_t     header;
    void        *retaddress;  // the memory address returned to user
} node_t;

typedef struct head {
    struct node *first;
    struct node *last;
    struct node *curr;
    size_t       len;
} head_t;

static char     MYHEAP[MYHEAPSIZE];  // in reality this comes from OS via a syscall
static head_t   freelist;            // header for the circular linked list of free blocks

void *my_malloc( size_t sz);
void  my_free( void *p );
void  print_list( head_t *head );

int main( void )
{
    void    *alloclist[MAXALLOCS] = {0}; // list of allocated blocks
    size_t   reqsize = 0;
    int      i;
    node_t  *nodeptr;

    freelist.len = 1;
    freelist.first = freelist.last = freelist.curr = nodeptr = (node_t *)MYHEAP;

    nodeptr->header.s.size = (MYHEAPSIZE/sizeof(header_t))*sizeof(header_t); 
    nodeptr->header.s.next = nodeptr;
    nodeptr->retaddress = MYHEAP+sizeof(header_t);

    printf("(%p,%p)%u\n",freelist.first,nodeptr->retaddress, (unsigned)sizeof(header_t));

    srand (time(NULL));

    for(i=0; i<MAXALLOCS; ++i ) {
        reqsize = (size_t)rand();
        alloclist[i] = my_malloc(reqsize);
    }
    print_list( &freelist );
    for(i=0; i<MAXALLOCS; ++i ) {
        my_free(alloclist[i]);  
        alloclist[i] = 0;
    }
    print_list( &freelist );

    return 0;
}

// Allocate memory using first-fit algo
void *my_malloc( size_t sz )
{
    size_t    count = 0;
    node_t   *prevnode = NULL;
    size_t    allocsz = 0;;
    header_t *retadd = NULL;

    // total size = sz + overhead (due to quantiaztion of size in multiples of sizeof(header_t))
    //allocsz = ((sz + ALIGN - 1)/ALIGN + 1)*ALIGN;
    allocsz = (sz + ALIGN - 1) & ~(ALIGN-1);
    if( allocsz > MYHEAPSIZE) return NULL;
    // make sure not less than specific amount is allocated to minimize external frag
    if( allocsz < 2*sizeof(header_t)) allocsz = 2*sizeof(header_t);

    // find the first block of size greater than or equal to sz
    // start searching form the next to the recently allocated block
    while( count < freelist.len ) {
        prevnode = freelist.curr;
        freelist.curr = freelist.curr->header.s.next;
        if( freelist.curr->header.s.size == allocsz ) {
            // found a block, remove it from the list to provide for requested memory
            if( freelist.len == 1 ) {
                // special handling if only one node is present
                retadd = freelist.curr->retaddress;
                freelist.first = NULL;
                freelist.last = NULL;
                freelist.curr = NULL;
                freelist.len--;
                break;
            }
            else {
                retadd = freelist.curr->retaddress;
                if( freelist.curr == freelist.first ) {
                    freelist.first = freelist.curr->header.s.next;
                }
                else if( freelist.curr == freelist.last ) {
                    freelist.last = freelist.curr->header.s.next;
                }
                freelist.curr = prevnode->header.s.next = freelist.curr->header.s.next;
                freelist.len--;
                break;
            }
        }
        else if( freelist.curr->header.s.size > sz ) {
            // found a block, reduce it by taking off the tail end for required memory
            freelist.curr->header.s.size -= allocsz;
            retadd = (header_t *)((char*)freelist.curr + freelist.curr->header.s.size);
            retadd->s.size = allocsz;
            retadd = (header_t *)((char*)retadd + sizeof(header_t));
            break;

        }
        count++;
    }
    printf("reqsz=%u,allocsz=%u,add=%p\n",(unsigned)sz,(unsigned)allocsz,retadd);

    if( retadd == NULL ) {
        printf("OUT OF MEMORY\n");
    }

    return (void *)retadd;
}

void my_free( void *p )
{
    size_t    pos = 0;
    node_t   *inode = NULL, *prevnode=NULL;
    header_t *pheader = NULL;

    if( p == NULL ) {
        printf("Null ptr to free!\n");
        return;
    }
    pheader = (header_t *)( (char*)p - sizeof(header_t) );
    if( pheader->s.size == 0 || pheader->s.size > MYHEAPSIZE ) return;

    static int i=0;
    printf("i=%d,totsz=%u,add2free=%p\n",i++,(unsigned)pheader->s.size,p);
    // Q1. where to place the freed mem block pointed by p
    // The freelist cirualr link list is maintained in increasing order of start address of each node
    // The newly freed mem block is placed in this list while maintaining this order.
    // 2. how to determine if it is adjacent to a free block on either side or both
    // 3. how to combine it with adjacent free blocks
    for( inode=freelist.first; pos<freelist.len; prevnode=inode, inode=inode->header.s.next ) {
        if( (char*)inode > (char*)pheader ) 
            break;
        pos++;
    }
    // pos (0-based) indicates the pos of the node bigger than size of p
    if( pos == freelist.len ) {
        // insert at the end, but first check if it can be combined with last node
        if( (char*)freelist.last + freelist.last->header.s.size == (char*)pheader ) {
            freelist.last->header.s.size += pheader->s.size;
        }
        else { // insert at end
            freelist.last->header.s.next = (node_t *)pheader;
            pheader->s.next = freelist.first;
            freelist.last = (node_t *)pheader;
            freelist.len++;
        }
    }
    else if( pos == 0) {
        // insert at the front, but first check if it can be combined with front node
        if( (char*)freelist.first == (char*)pheader + pheader->s.size ) {
            freelist.first->header.s.size += pheader->s.size;
            freelist.first = (node_t *)pheader;
        }
        else { // insert at front
            freelist.last->header.s.next = (node_t *)pheader;
            pheader->s.next = freelist.first;
            freelist.first = (node_t *)pheader;
            freelist.len++;
        }
    }
    else {
        // insert before pos in the middle (between prevnode and inode)
        // before that check if it can be combined with any of the adjacent blocks (or both maybe)
        if( (char*)prevnode + prevnode->header.s.size == (char*)pheader ) {    // combine with prev
            prevnode->header.s.size += pheader->s.size;   
            if( (char*)prevnode + prevnode->header.s.size == (char*)inode ) {  // combine with next as well
                prevnode->header.s.size += inode->header.s.size;
                prevnode->header.s.next = inode->header.s.next;
                if( freelist.last == inode ) 
                    freelist.last = inode->header.s.next;
                freelist.len--;
            }
        }
        else if( (char*)inode == (char*)pheader + pheader->s.size ) {     // combine with next only
            prevnode->header.s.next = (node_t *)pheader;
            pheader->s.next = inode->header.s.next;
            pheader->s.size += inode->header.s.size;
            if( freelist.last == inode ) 
                    freelist.last = (node_t *)pheader;
        }
        else { // insert between prevnode and inode
            prevnode->header.s.next = (node_t *)pheader;
            pheader->s.next = inode;
            freelist.len++;
        }
    }

}

// Print a list
void print_list( head_t *head )
{
    unsigned    count = 0;
    node_t     *temp_ptr=NULL;
    size_t      sz;
    void       *ptr;

    // traverse the list from the list head
    if( head == NULL || head->len == 0 ) {
        printf("Empty queue.\n");
        return;
    }
    else {
        temp_ptr = head->first;
    }

    printf("*<- ");
    while( count < head->len ) {
        sz = temp_ptr->header.s.size;
        ptr = temp_ptr->header.s.next;
        printf("[%u, %p]", (unsigned)sz, ptr);
        temp_ptr = temp_ptr->header.s.next;
        count++;
    }
    printf("NULL-<*\n");

}
\$\endgroup\$
2
\$\begingroup\$

Constant Values
The value for MYHEAPSIZE is 2000000, however the comment indicates this is 2MB, and it's not. The difference is important when writing this kind of code. Two Mega Bytes can be expressed as 2097152 in base 10, 0x200000 in hex or 1 << 21.

#define MYHEAPSIZE 0x200000
#define MYHEAPSIZE 2097152
#define MYHEAPSIZE (1 << 21)

For the following keep in mind that sizeof(expression) is a compile time expression for the following cases. The following suggestions might make the code more portable between different devices.

It might be better to express ALIGN as sizeof(long long) rather than putting that in the comment

#define ALIGN      sizeof(long long);

If the constants are defined after the structs then BLOCKOVHEAD can be expressed as

#define BLOCKOVHEAD sizeof(node_t) + sizeof(size_t)

If MINALLOCSIZE is moved to the bottom of the list then

#define MINALLOCSIZE      BLOCKOVHEAD + ALIGN

Separate the Implementation From the Test
If this to be implemented as a library, it would be better to put the functions into another C source file and provide a header file. This would allow for hiding the implementation from the users. It might also be better to move the initialization of the heap and other variables into an initialization function in the C source file. This all would prevent user access of MYHEAP.

Control the Output of Rand()
When I ran this on my MacBook Pro running El Capitan nothing was ever allocated because ALL the values returned from rand() were greater than 2000000. You might want to limit the values returned to be under 2500000.

    reqsize = (size_t)rand() % 2500000;

Make it as Close to the Real World as Possible During Testing
If you are testing performance, then it would be better to actually do the malloc or sbrk here. The system call sbrk is what malloc calls for memory, or it did in the Sun OS and Solaris versions of Unix. This would provide a true measure of the performance of the algorithm.

static char     MYHEAP[MYHEAPSIZE];  // in reality this comes from OS via a syscall

The code in main() doesn't do any error checking for failure of malloc, rather than check retadd in my_malloc it might be better to check in main which would be more realistic.

The code calls my_free() without checking that the memory was actually allocated. This could cause any application to crash.

This code assumes that only one application is running, in embedded programming where memory is a precious and limited resource this might be a shared library that controls all free memory in the system.

There is no consideration here for MT or MP.

Limit Code Complexity, Think About the SRP
The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows:
    `A class should have only one reason to change.`

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines in procedural languages like C as well.

The my_malloc function could be broken up into at least 3 functions to simplify development and maintenance. This is also true of my_free().

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks @pacmaninbw. I have taken care of #defines as per your suggestion. I will be writing a better test driver and that would be a separate file as you said. I overlooked the point that rand has a different behavior on windows and unix-like. Thanks for catching that. Regarding your comment "calls my_free() without checking that the memory was actually allocated" , how do I go about checking if a memory was allocated by dmm or not? \$\endgroup\$ – Vikas Yadav Nov 29 '17 at 19:41
  • \$\begingroup\$ And you are right about no consideration for MT/MP, this is not rentrant code. That was intentional for the current purpose. For real MT/MP use i have to make it rentrant. I will spend some time reviewing the code for my_malloc and my_free to get them more modular to meet your SRP suggestion. Thanks a ton! \$\endgroup\$ – Vikas Yadav Nov 29 '17 at 19:41
  • \$\begingroup\$ basic test for safe free is if (pointer != NULL) { free(pointer); pointer = NULL; } \$\endgroup\$ – pacmaninbw Nov 29 '17 at 20:32
  • \$\begingroup\$ Very nice answer but there's just one teeny thing I disagree with, and that's with respect to checking for null pointers on freeing. I'd rather the allocator conform to the standard behavior of free which does the null check/branching. 7.20.3.2/2 from ISO-IEC 9899: "If ptr is a null pointer, no action occurs." I find that really helpful to lean on, especially in the context of error handling, to not have to check which pointers are null prior to freeing. \$\endgroup\$ – Dragon Energy Dec 2 '17 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.