Re: best-fit algorithm with bitmap heap

[Ondřej Bílka <neleai at seznam dot cz>]

Correction as I initially discovered better solution but forgot about
that when writing previous post. Operations are lot simpler.

Description below is mostly same except that free is simpler. I could do
multiple frees with free_bitmap with 1 at start of each chunk to be freed.
Bitmaps alloc_first and alloc_last with 1 at start/end of allocated
chunk stay. Removing bits corresponding to freed chunk is actually
simple with following formulas

alloc_first = alloc_first - free_bitmap;
alloc_last = alloc_last & (alloc_last - free_bitmap);

Endpoints (noninclusive) of free areas that changed are given by following bitmap

free_last = alloc_first & (alloc_first ^ (alloc_first - free_bitmap))

When processing these you get starts from highest bit in alloc_last & mask

Forgot to add that cross page allocation is possible by adding more
cases but I don't know if bit better space utilization is worth worse
performance.

Check if block is valid could be also simplified and we could use same
formulas as those to remove bits, to allocate offset s and size l we
check and change bitmaps with following checks:

if (((alloc_first ^ (~ (1<<s))) != alloc_first) &&
    alloc_last & (alloc_last - (1<<s)) == alloc_last & (~(1<<(s+l))))
  {
    alloc_first = alloc_first ^ (~ (1<<s));
    alloc_last = alloc_last & (~(1<<(s+l)));
    /* valid, do allocation */
  }


On Tue, Mar 06, 2018 at 09:42:43PM +0100, Ondřej Bílka wrote:
> On Thu, Mar 01, 2018 at 10:33:18PM +0100, Ondřej Bílka wrote:
> > Like I mentioned in other thread I plan to make improved malloc+friends.
> > It will be split to several aspects.
> > 
> I got idea when I pondered about merging chunks and deleting old data
> that you don't have to delete them from data structure. 
> It requires to save data about free chunks separately and data to check 
> if chunk information is up-to-date.
> To limit space usage one would need to use fixed size buffer with these, when its full one
> needs to delete all invalid entries from buffer, and add/remove elements from bigger
> storage to make buffer half full.
> 
> I could do this quickly with bitmaps and some conditions for sake of simplicity.
> 1. It would consider only allocation where capacity is 1-16 integer multiple of block 
> 2. Data would be in 64-block pages where first and last block are reserved by allocator.
> 
> As data structure for page start of allocated chunk would be denoted by
> 1 in corresponding  bit of alloc_first and end in corresponding bit of alloc_last. 
> Reserved blocks are there to put sentinel 1 at end of bitmaps. 
> For faster operations bits in alloc_first could be in reversed order.
> 
> When one has address and capacity of b blocks testing if it is valid free area is easy,
> from address we determine header and number s of starting block.
> First we check that free space starts there with formula (alloc_last & (1<<(s-1)))
> To test that it is free space until s+b which should be start of chunk
> it should be formula like this(maybe its off by one somewhere, didn't test that)
> ((alloc_first>>s)<<(64-b)) == 1<<63
> 
> On free with offset s one zeroes allocated bits with 
> 
> alloc_first = alloc_first ^ (1<<s);
> 
> Start of free region is just after index of highest 1 bit of alloc_first & ((1<<s) - 1)
> Here comes comment that alloc_first could have reversed order as lowest
> 1 bit could be easier to compute
> 
> End of allocation could be zeroes just with easy bit operations like
> following:
> 
> ml = alloc_last & (~((1<<s)-1));
> mask = ml ^ (ml - 1);
> alloc_last = alloc_last ^ mask ^ (mask / 2);
> 
> end of free region is last 1 bit of alloc_last & (~mask)
>