[C] Dynamic Memory (Part 7.0): [My]Free

memory
cprogramming
heap
dynamic

(oaktree) #1

It’s been a while since the last edition (I do say this every time). Behold, a seventh article!

Allow me to restate the prerequisites:

  1. Proficiency in C
  2. Understanding of the Stack vs Heap
  3. Familiarity with this article’s predecessors (all of them).

Disclaimer: what follows are my findings, and my own personal implementation of free(). Do not expect another person’s free() to follow the same logic or routine.


Logic Walkthrough

void my_free(void *ptr);

ptr is expected to be an address previously returned by my_malloc. Note: This function will not be able to correctly or safely free memory allocated by another utility.

Using some pointer arithmetic, my_free() finds the relevant chunk containing ptr's metadata. Let us reexamine what a chunk looks like:

typedef struct _chunk {
    size_t  _chunk_sz;

    struct _chunk *next,
                  *prev,
                  *next_free,
                  *prev_free;


    _free_t _free;

} _chunk;

In the above struct declaration, _free_t is a type I defined. It’s merely an enum that I use as a flag to… you guessed it: tell whether or not a chunk is free.

As you might expect, one of the things my_free does is alter this flag.

Each chunk also contains next_free and prev_free attributes that make up a doubly-linked list. This doubly-linked list is used to “remember” which chunks are free. Note: next and prev are meant to point to memory-adjacent chunks, but next_free and prev_free are not guaranteed to point to adjacent memory; rather, these pointers are used to speed up access to free chunks so that we can avoid looking at chunks that are already in use.

my_free() inserts this newly-freed chunk at the end of the freed chunks linked list. This means that the freed chunks list is not sorted.

There is also one more optimization. If the chunks to either side (memory-adjacent) of this now-freed chunk are free as well, the chunks will be merged. I have written a subroutine to handle this (mainly because linked-list pointer gymnastics look so ugly).


Example

Imagine we have some memory laid out like so (I apologize in advance for the bleh-ness):

In the above photo, assume that the session struct is stored in memory somewhere to the left of A and the program break is somewhere to the right of E.

Our linked list of all chunks is {A,B,C,D,E}. Our linked list of freed chunks is {A,D}.

A user now calls my_free to request the deallocation of C:

C is marked as FREE. While our linked list of all chunks remains the same, our linked list of freed chunks becomes {A,D,C} (remember that newly-freed chunks are just inserted at the end).

my_free realizes that C and D, adjacent chunks, are both free. To adhere to the program design, C and D must now be merged. As C is before D, it will absorb D’s space in memory, essentially making one larger C:

In merging C and D, D is removed from the all chunks linked list, making that list {A,B,C,E}. The free chunks list now becomes {A,C}. The memory session decrements its count of chunks. D no longer exists as its own entity.

I hope this helps you, @_py.


Implementation

Don’t worry. It’s just fifty lines.

void my_free(void *ptr) {

    // 1. Calculate chunk's address.
    _chunk *c = (_chunk*)((char*)ptr - sizeof(_chunk) );

    // 2. Check chunk's validity
    if ( c < _session->_first_chunk || c > _session->_last_chunk + _session->_last_chunk->_chunk_sz) {
        fprintf(stderr, "[!] Invalid Free! %p is out of range!\n", ptr);
        return;
    }

    // 3. Ignore chunk if it's free already.
    if (c->_free == FREE)
        return;

    // 4. Mark chunk as free.
    c->_free = FREE;

    // 5. Put chunk into free chunk list.
    if ( !_session->_first_free_chunk ) {

        /* if there are no chunks... */
        _session->_first_free_chunk = c;
        _session->_last_free_chunk = c;

        c->prev_free = NULL;
        c->next_free = NULL;

    } else {

        if (_session->_last_free_chunk) /* just in case... */
            _session->_last_free_chunk->next_free = c;

        c->prev_free = _session->_last_free_chunk;

        _session->_last_free_chunk = c;

    }

    // 6. Do chunk merging:

    if (c->next != NULL && c->next->_free == FREE)
        _merge_chunks(c, c->next);

    // 6(b) Merge other side, if needed.
    if (c->prev != NULL && c->prev->_free == FREE)
        _merge_chunks(c->prev, c);
}

I have left notes in the code snippet. If you’re confused, feel free to comment a question.


Conclusion

There are many things that can be done differently in this implementation:

  • Newly-freed chunks could be inserted into the freed chunks list by size to speed up allocation lookups.
  • The session’s chunk list could be traversed to ensure that the chunk point is valid. Right now, only a range check is performed. Linear search can be costly, and binary search is out of question for several reasons.
  • One notable optimization is the use of a freed chunks list, but the freed chunks list could be omitted. In its place, the entire list of chunks (free or not) could be scanned. The freed chunks list trades space for speed, however, and most computers can sacrifice a few bytes of RAM (* insert jab about Java here *).

#2

This is the most crucial info in this paper and I think a visual representation or a diagram is a must for this concept, plus, the code would be much more understood imo.

On the other hand, your intention might was code illustration and not in-depth explanation of the inner workings of the algo. In that case, forget what I said above.


(Command-Line Ninja) #3

What would I use this for? #troll

No seriously? For all those who got lost at

Why would we need a custom free implimentation? Isn’t C good enough to do it itself? May as well just use Ruby or Python. C obviously sucks!


(oaktree) #4

@pry0cc: It’s about the learning experience!


(oaktree) #5

I can add a doodle. Give me a few hours.


(Command-Line Ninja) #6

Lol you deflected that troll so well.


#7

Nice update @oaktree. My request wasn’t personal. I was hoping that others will benefit from a simple visualization. When you can draw a concept, you understand it much better.

Moreover, the whole meat of free() seems to rely on the unlink() macro. Just throwing ideas at you for future posts in case you are interested.


(oaktree) #8

This topic was automatically closed after 30 days. New replies are no longer allowed.