Nasty Evil Memory Fragmentation fix

[Ove Kaaven]

On Wed, 10 Oct 2001, Gavriel State wrote:

> > Well, after looking at some allocator algorithms, it seems to me there's
> > no reason to change neither the bin sizes nor the data structures. We just
> > have to change the free block selection algorithm - from my reading of the
> > code, right now it seems to always choose the *newest* (most recently
> > added) free block that's big enough. By changing it to always choose the
> > *oldest* free block instead, we'd already have a huge improvement.
> > (That's essentially the effect of Gav's patch, but only for big blocks,
> > but I suspect that could safely be done for *all* block sizes)
> 
> Actually, we originally had it pushing all new free blocks (regardless of
> size) to the end.  Our fear though was that doing that would cause 
> slowdowns as it would lengthen the free-block search time. By doing it 
> only for larger blocks, small block allocations should be faster.

But the free list bins Wine's allocator uses (HEAP_freeListSizes) would
have taken care of that, wouldn't it?

> There are a variety of other issues that are important to consider 
> with an allocator though: locality of reference (memory blocks allocated
> together are likely to be used together, and we should therefore try 
> to allocate them near one another to reduce paging time); speedy allocation
> of small blocks; best-fit efficiency (ie: prefer to take a free block
> that's close to the size we're looking for rather than split a bigger
> block, etc.

Those issues are all part of the "free block selection algorithm" I talked
about above. We just need to change the algorithm used there; its effect
would be the same as plugging in a whole new allocator.

> I've had a brief look at the code referenced by Adam Moss (found at
> http://g.oswego.edu/dl/html/malloc.html), and it looks like it would 
> be a vast improvement over Wine's current Heap manager.

Not that much. Wine's allocator already implements the *features* of that
allocator (boundary tags, bins), it just doesn't implement all the
*strategies* used for selecting which free block to allocate memory from
(though the only big things we lack there is "best fit" and "wilderness
preservation", the latter of which Alexandre talked about). We just need
to make sure Wine's free block selection routine uses the same strategies
as this allocator, and we'd get exactly the same performance as that
allocator, but without replacing the whole thing and sacrificing the
compatibility we have or introducing new bugs.