Re: best-fit algorithm with bitmap heap

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

On Tue, Mar 06, 2018 at 11:25:31PM +0000, Wilco Dijkstra wrote:
> Hi,
> 
> I think before going into the details it is worth considering whether it is even
> feasible to use a bitmap search for first-fit, let alone best-fit. What you seem
> to be saying is there will be lots of small pages for allocation, each of which
> has its own bitmap. If say we have 100MBytes worth of data allocated, you will
> need to start searching every single bitmap that has free space. That would imply
> adding a fast data structure that keeps track of all the free space across all
> the bitmaps. Then this needs to be kept up to date by both malloc and free, as
> well as supporting multiple threads. It seems to me this would become the key
> bottleneck - so it's essential to sort out the overall allocation strategy first.
> 
No, there is no searching and as I described it is really easy.

I could do this for all sizes by making these structures two-level,
larger size are above mmap threshold.

For multiple frees done with bitmap one uses simple trick that if on
free free_bitmap is zero and add it to list pending_pages. When it is
time to do free it just traverses pending_pages, does free and resets 
corresponding free_bitmap to zero. 

For given capacity best fit would just point you to array with all free
pointers of given capacity. Here idea is that instead of deleting
pointer from linked list on free free we delete it in malloc with few 
bit operations if free region starts and ends at claimed points.

Problem of this is that we need to store those pointers separately and
to limit space usage delete invalid pointers when we exceed capacity.

Without this idea free is more complicated, it needs another bitmap with
free chunks that are double linked list, following formula should
identify those excluding start of new free region which should be handled
separately.

free_in_list & (alloc_first_updated ^ (alloc_first_updated - free_bitmap)).

In my previous mail I wrote check if chunk is valid incorrecty, previous one should be correct.