title: Free List Allocator with Red Black Tree
body: <p>I'm trying to implement a free list allocator using Red Black Tree for optimize <code>O(LogN)</code> best fit search.</p>
  
  <p>My strategy is that when a block is allocated, it's allocated with a <code>Header</code> where</p>
  
  <pre class="lang-cpp prettyprint-override"><code>struct Header {
    std::size_t m_Size;
  };
  </code></pre>
  
  <p>thus <code>sizeof(Header) == sizeof(std::size_t)</code>
  This is done, so when deallocating I could know how much bytes were allocated to give it back as a free node.</p>
  
  <p>Now there's a problem with this solution, because now I have to align the <code>Header</code> itself + the allocated block to the requested alignment, so padding in between the <code>Header</code> and the allocated block start, and padding between the end of the allocated block and a start of a new <code>Header</code> (so next block <code>Header</code> will be already aligned) are needed.</p>
  
  <p>So to illustrate the problem better here's a Red Black Tree with nodes indicating free block sizes minus <code>sizeof(Header)</code>
  <a href="https://i.stack.imgur.com/CskhO.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/CskhO.jpg" alt="enter image description here"></a></p>
  
  <p>Now let's assume a user allocate a block of size 16 with alignment of 16:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>allocate(16, 16);
  </code></pre>
  
  <p>Now best fit will yield us node 17.<br/>
  But we can't count on it, let's assume node 17 is at address <code>0x8</code> and we're on x32 so <code>sizeof(Header) = 4</code>.<br/>
  <code>Header</code>'s address will be from <code>0x8-0xC</code>, now we would need to add a padding so our block will be aligned to 16 as requested, this padding is equal to 4 bytes so our allocated block will start at <code>0x10</code> which is aligned to 16. Now no padding is needed at the end of the block since <code>0x10</code> + <code>16d</code> will be aligned to next block <code>Header</code>.<br/>
  The padding between the end of the allocated block to the start of the new block is easy to calculate before-hand like so:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>std::size_t headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
  </code></pre>
  
  <p>So it's not dependent on the address of the free node.<br/>
  But the padding between the end of the <code>Header</code> and the start of the allocated block <strong>IS</strong> dependent on the address of the free node like I've demonstrated.<br/>
  And for our example the total needed size in the case of this specific node will be 4 (padding between <code>Header</code> and allocated block) + 16 (allocated block size) + 0 (padding needed for next free block header alignment) = 20.<br/>
  Obviously node 17 doesn't match.</p>
  
  <p>Now my strategy to fix this is as follows:<br/>
  - Find best fit
  - See if best fit matches the size requirements as described
  - If yes we're done
  - If not get its successor and check if it matches the size requirements as described
  - If yes we're done
  - If not start over from successor parent until we reach a node that satisfy size requirements or we reach the original best fit again</p>
  
  <p>Here's a code describing the process:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>void FreeTreeAllocator::Find(const std::size_t size, const std::size_t alignment, std::size_t&amp; sizePadding, std::size_t&amp; headerPadding, RBTree::Node*&amp; curr)
  {
      headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
  
      RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
      RBTree::Node* origin = best;
  
      std::vector&lt;std::size_t&gt; visited;
  
      while (visited[visited.size() - 1] != (std::size_t)origin &amp;&amp; !IsNodeBigEnough(size, alignment, sizePadding, headerPadding, best))
      {
          RBTree::Node* successor = m_Tree.Successor(best);
          if (IsNodeBigEnough(size, alignment, sizePadding, headerPadding, successor))
          {
              best = successor;
              break;
          }
          else
          {
              std::vector&lt;std::size_t&gt;::iterator it;
              do {
                  best = successor-&gt;m_Parent;
                  it = std::find(visited.begin(), visited.end(), (std::size_t)best);
              } while (it != visited.end());
          }
          visited.push_back((std::size_t)best);
      }
  }
  
  bool FreeTreeAllocator::IsNodeBigEnough(const std::size_t size, const std::size_t alignment, std::size_t&amp; sizePadding, std::size_t&amp; headerPadding, RBTree::Node* curr)
  {
      if (curr == m_Tree.m_Nil)
          return false;
      void* currentAddress = reinterpret_cast&lt;char*&gt;(curr) + sizeof(Header);
      std::size_t space = curr-&gt;m_Value;
      std::align(alignment, size, currentAddress, space);
      sizePadding = reinterpret_cast&lt;char*&gt;(currentAddress) - reinterpret_cast&lt;char*&gt;(curr) - sizeof(Header);
      return sizePadding + size + headerPadding &lt;= curr-&gt;m_Value;
  }
  </code></pre>
  
  <p>Now for the given allocation request:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>allocate(16, 16);
  </code></pre>
  
  <p>and the given example tree from the picture the following the algorithm described, the search path will be:</p>
  
  <pre><code>17 -&gt; 21 -&gt; 22 -&gt; 23 -&gt; 25 -&gt; 27
  </code></pre>
  
  <p>At worst case this is <code>O(LogN + M)</code> where <code>M</code> is the size of the right sub-tree of the original best fit node.</p>
  
  <p>Now one way this could be solved if I make <code>sizeof(Header)</code> = <code>sizeof(std::max_align_t)</code>, this way the padding between the <code>Header</code> and the start of the allocated block will always be 0, so we won't need this padding anymore because every request will be aligned without this padding, so we could really just do:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>void FreeTreeAllocator::Find(const std::size_t size, std::size_t&amp; headerPadding, RBTree::Node*&amp; curr)
  {
      headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;
  
      RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
      return best;
  </code></pre>
  
  <p>But that will waste alot of memory compared to my proposed idea where I settle on <code>O(LogN + M)</code> best fit search.</p>
  
  <p>Now why do I ask it?<br/>
  Because I see the use of Red Black Tree as optimization for free list allocator to reduce best fit search to <code>O(LogN)</code> while I can't seem to make it really <code>O(LogN)</code>, the flaw with my design I guess is that there need to be a <code>Header</code> for book-keeping on how much bytes to give back to a free block when deallocating, and I don't see a way to do it without this, if I was able to not have a <code>Header</code> at all, or make it so I don't have issues with it's alignment to find padding specific for a node in the list (by making <code>sizeof(Header)</code> = <code>sizeof(std::max_align_t)</code>, or even <code>sizeof(Header)</code> = <code>1</code>) then this could be solved with simple <code>O(LogN)</code> search.</p>
  
  <p>I'm looking for ideas on how to solve this issue, how other implementations are doing this in <code>O(LogN)</code> while keeping inner fragmentation as low as possible?</p>
  
  <p><strong>UPDATE</strong>:<br/>
  I ended up having the node addresses aligned to <code>alignof(std::max_align_t) - sizeof(Header)</code> so that makes <code>Header</code> always aligned no matter if you're on x32/x64 (remember that <code>Header</code> is composed of <code>sizeof(std::size_t)</code>), and no matter if <code>alignof(std::max_align_t)</code> is 8 or 16.<br/>That makes the allocated payload to start at address that is aligned to <code>alignof(std::max_align_t)</code> just like <code>malloc</code>, so no matter what is allocated it will always be aligned to the max alignment and no padding is required between <code>Header</code> and payload.
  The only padding required is after payload to match the next address that is aligned to <code>alignof(std::max_align_t) - sizeof(Header)</code> + any padding required to make it so the allocated block is at least <code>sizeof(RBTree::Node)</code> bytes big (including <code>sizeof(Header)</code> inside the equation) so when deallocation we could safely store an <code>RBTree::Node</code> without overriding other data.<br/>
  Without the padding between <code>Header</code> and the payload, and with the padding needed to align next block to <code>alignof(std::max_align_t) - sizeof(Header)</code> we can easily use the default <code>RBTree::Search</code> of <code>O(LogN)</code> since the padding can be calculated beforehand depending on the size of the block and removing from the equation the start address of a particular node.</p>
  
  <p>The only remaining problem I have with optimizing this free list allocator to <code>O(LogN)</code> is the deallocation part, more precisely the coalescence part.<br/>
  What I can't solve now is how to do <code>O(1)</code> coalescence. I rearranged the <code>RBTree::Node</code> struct such as that <code>m_Parent</code> is first and so its LSB is always set 1 (for every function relying on <code>m_Parent</code> I have a getter function for fixing it) and then I can check if next block of current deallocated block (we can get to next block with size from <code>Header</code>) if the first <code>sizeof(std::size_t)</code> bytes <code>&amp; 0x1</code> is true and if so it's a free node, if not it's a busy block with <code>Header</code> (since <code>Header</code>'s <code>m_Size</code> LSB will always be 0 because we add padding for alignment with <code>std::max_align_t</code>).<br/>The remaining problem is how to get to the previous memory block and know if it's free or busy, that I cannot figure yet and would love to hear suggestions.</p>