<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Oluwatimileyin Dada on Medium]]></title>
        <description><![CDATA[Stories by Oluwatimileyin Dada on Medium]]></description>
        <link>https://medium.com/@oluwatimileyin?source=rss-6f4ea30ff5a8------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Stories by Oluwatimileyin Dada on Medium</title>
            <link>https://medium.com/@oluwatimileyin?source=rss-6f4ea30ff5a8------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 05:18:56 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@oluwatimileyin/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Custom Memory Allocator (Part 1: Malloc)]]></title>
            <link>https://medium.com/@oluwatimileyin/how-i-built-a-memory-allocator-part-1-malloc-b5bf8218f31b?source=rss-6f4ea30ff5a8------2</link>
            <guid isPermaLink="false">https://medium.com/p/b5bf8218f31b</guid>
            <category><![CDATA[malloc]]></category>
            <category><![CDATA[c]]></category>
            <category><![CDATA[low-level-programming]]></category>
            <dc:creator><![CDATA[Oluwatimileyin Dada]]></dc:creator>
            <pubDate>Mon, 01 Sep 2025 15:10:33 GMT</pubDate>
            <atom:updated>2025-09-01T16:54:53.476Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>I’m a horrible writer (I’ll update the writing as I see fit in the future).</strong></p><p>I’ve grown weary of performing CRUD operations with Python and Django, and I’m eager to dive into a project that challenges me to apply the concepts I learned during my postgraduate diploma in computer science, particularly in data structures and algorithms. How can I solve this weariness? Building tools, no more CRUD applications. This decision became the beginning of my journey into the world of system programming (low-level programming). I started reading the book THE LINUX PROGRAMMING INTERFACE (TLPI), where the only tool needed is Linux and a C compiler. Each chapter of the book has some exercises.</p><p>Chapter 7 of TLPI, Memory Allocation, explained everything I needed to know about memory allocation and the implementation of malloc and free. The exercise for this chapter is “<em>(Advanced) Implement malloc() and free().”</em></p><p><strong>Tool: </strong>all I needed was a C compiler and my brain.</p><h3>Implementation</h3><p>When you call malloc in C, it doesn’t magically hand you memory out of thin air—it has to get that memory from somewhere. Under the hood, one of the ways this happens is through the sbrk() system call.</p><p>Before sbrk() is used, the program sets aside a region called the <strong>heap</strong>. This is where dynamic memory allocations live. Think of the heap as an expandable playground that grows whenever your program asks for more space.</p><p>The function sbrk(int num) adjusts something called the <strong>program break</strong>. The program break marks the end of your process’s data segment. Moving it forward by num bytes extends the heap, giving malloc more room to work with. Interestingly, sbrk() returns the old position of the program break, which serves as the starting address of the new chunk of memory.</p><p>But raw memory alone isn’t enough. To keep track of which parts of the heap are allocated and which are free, malloc needs bookkeeping. This is where <strong>metadata</strong> and helper variables come in; they act like a map of the heap, making sure memory can be allocated, freed, and reused safely.</p><pre>#include &lt;unistd.h&gt;<br><br>#define TRUE 1<br>#define FALSE 0<br>// a page of memory is 4096 bytes.<br>#define PAGE 4096<br><br>/*<br> * meta_data to keep track of our structure<br> * size: size of memory in this block<br> * next: next memory block<br> * previous: previous memory block<br>*/<br>typedef struct meta_data {<br>  size_t size; // size of block<br>  struct meta_data *next; // address next block<br>  struct meta_data *previous; // address of previous block<br>  short free; // determine if the block is free or in use<br>}block_t;<br><br>#define BLOCK_T sizeof(block_t)<br><br>block_t *heap = NULL; // the beginning of the sbrk<br>block_t *heap_end = NULL; // the end of the <br>block_t *next_free = NULL; // free block closest to the beginning<br>block_t *new = NULL; // An iterator to look for memory chunk;</pre><h3>Malloc</h3><p>malloc(size_t size)<em> </em>returns a void pointer to an address of sizebytes; on error, NULL is returned. If size is less than 1, return NULL; if heapis NULL, heap is declared as the return value of sbrk.</p><pre>/*<br> * every varibale used but not defined in this code snippet<br> * was defined in the code snippet above while defining variables and metadata<br>*/<br>void *malloc(size_t size) {<br>    if(size &lt;= 0)<br>        return NULL;<br>  <br>    if(heap == NULL)<br>    {<br>      heap = (block_t)sbrk(PAGE); // creates the heap memory<br>      heap-&gt;size = PAGE - BLOCK_T; // The size of memory created - the size of metadata<br>      heap-&gt;previous = heap-&gt;next = NULL; // previous and next block are NULL<br>      heap_end = (block_t)sbrk(0); // returns the current sbrk without moving the sbrk<br>      heap-&gt;free = TRUE;<br>      next_free = heap;<br>    }<br>}</pre><p>When initializing the heap, it’s important to remember that it begins as one large chunk of memory. This chunk is then divided into smaller <strong>blocks</strong> (each represented by a structure, say block_t), and those blocks are handed over to the caller of malloc. Each block contains some <strong>metadata</strong> at its beginning, which malloc uses to keep track of the block’s size, status, and neighbors. The <strong>metadata</strong> at the start of each block isn’t meant to be writable by the programmer, but in practice, there’s no mechanism preventing it. If you accidentally (or intentionally) overwrite that memory, you’ll corrupt the allocator’s bookkeeping, which usually leads to crashes or undefined behavior.</p><p>Iterate through the chunk using the new variable. Check for a free block whose size is wide enough to accommodate the metadata and size needed by user. Hence, we have Chunk-&gt;size &gt;= BLOCK_T + size. If the chunk/block is big enough and not at the end of the heap i.e not the tail, carry on with allocation; else, extend the heap.</p><pre>// The code here should come within the curly braces of malloc<br>size_t total = size + BLOCK_T;<br>new = next_free;<br>while(new) {<br>  if(new-&gt;size &gt;= total &amp;&amp; new-&gt;free)<br>      break; // found a suitable chunk of memory<br>  new = new-&gt;next;<br>}<br><br>if(new &amp;&amp; new-&gt;next == NULL &amp;&amp; new-&gt;free &amp;&amp; new-&gt;size &lt; total){<br>  size_t more = PAGE;<br>  sbrk(more);<br>  next_free = sbrk(0);<br>  new-&gt;size += more;<br>}</pre><h3>Creating the new block out of the old block</h3><p>The new free block, next, will be created from the block new is pointing to. This need to be done before the values of the new is adjusted. So we have something like the code below.</p><pre>// The code here should come within the curly braces of malloc<br>/**<br> * add total bytes to the address of new this make the beginning of the new block<br> * new will be casted into a char *, in order for the correct pointer arithmetic to take place<br> * after the addition, cast the new address into block_t * and save in the new pointer<br>*/<br>block_t *next = (block_t *)((char *)new + total);<br>next-&gt;free = TRUE;<br>next-&gt;size = new-&gt;size - total;<br>next-&gt;next = new-&gt;next; // point to what new is pointing at as next block<br>next-&gt;previous = new; // point to new as previous block</pre><p>Now adjust the values of new</p><pre>// The code here should come within the curly braces of malloc<br>new-&gt;next = next; // points to the newly formed block<br>new-&gt;size = size; // the size passed to malloc<br>new-&gt;free = FALSE; // mark it as being in use</pre><p>Finally</p><p>Adjust next_free if need be, and return the memory address after the metadata of new</p><pre>if((char *)next_free &gt; (char *)next)<br>  next_free = next;<br>return (char *)new + BLOCK_T;</pre><h3>PS</h3><p>I found a bug in the loop while I was writing this; I will fix it later. I am still learning.</p><h3><strong>THANK YOU.</strong></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b5bf8218f31b" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>