httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "David Harris" <>
Subject RE: [patch] smarter free block allocation to fix leak
Date Thu, 05 Aug 1999 19:20:42 GMT

Charles Randall [] wrote:
> > If one wants to implement hashing, I propose breaking block_freelist down
> > into these three lists:
> >
> > block_freelist_min     x <= BLOCK_MINALLOC
> > block_freelist_small   BLOCK_MINALLOC < x <= BLOCK_MINALLOC*2
> > block_freelist_big     BLOCK_MINALLOC*2 < x
> And doing a best fit search inside each of those lists.
> If you're going to maintain three lists, you've already approximated best
> fit. I don't see the advantage of best fit in the two smaller free-lists.

I thought the hashing was there to help make the best fit search faster. So
that we don't have to search through all of the other blocks searching for a
4MB block.

Anyway, it's still important to have a best fit search on the
block_freelist_big list, because using an 8MB block with a 4MB request is not
so great. And remember, that when doing a best-fit search, if we find an exact
match we don't have to search through the whole list. So, the best-fit vs.
first-fit argument is moot on the block_freelist_min list. And the
block_freelist_small looks like it will mostly have blocks of size 8200, so I
want to best fit search that as we should find an exact match soon.

So, I still like best fit.. but I'm really out of my specialty on this

 - David Harris
   Principal Engineer, DRH Internet Services

View raw message