[PATCH] malloc: retire mechanism for older non used tcached chunks

[Wilco Dijkstra]

Hi Cuptertino,

>> Instead
>> tcache_location_large first moves any out of date blocks to the
>> return_to_arena list and only then checks the count of the current tcache
>> bin.
> The count is not used in tcache_location_large at all. The num_slots is
> passed to tcache_get_n and is decremented, even if it would mean that it
> would get to become a negative value.
> That value is later used to check if the mechanism should traverse this
> bin to attempt to retire further elements (code in the end of
> tcache_put_large)

That means that a bin can contain many thousands of blocks if recently
released. And once the count goes negative, we check each block on
average 1.5 times. And we keep doing these repeated whole-list checks
for every insert until the count goes positive again. If we keep inserting
new blocks, the list won't reduce in size even as we retire older blocks -
it can actually keep growing. That's an O(N^2) bug.

>> So doesn't that mean you can end up adding an unlimited number of
>> blocks into the return_to_arena list without ever cleaning it?
> Yes and no, because eventually they will start to be retired. And once
> num_slots <= 0 it will be eager to retire them in tcache_put_large.

Eventually, but one can keep inserting and walking the whole list 1.5 times
on every insert starts to become very expensive.

>> To make things
>> worse, the default value of tcache_retire_size is set to 0 which means any
>> freed block is considered out of date by definition...
> No! Unless I made some terrible unnoticed mistake. Please look into
> do_set_tcache_max and do_set_tcache_unsorted_limit.

OK, so you require one to use the tunable first - it seems better to set a good
default value. There is definitely something wrong there:

-  if (tc_idx < TCACHE_MAX_BINS)
+  if (tc_idx < TCACHE_MAX_BINS || mp_.tcache_retire_size == 0)

This will allow huge tcache_max values that result in indexing beyond the tcache.

>> Also this adds a large overhead since you always check for out of date blocks
>> during every free/malloc of a large block. If we only call tcache_large_cleanup
>> if a large bin is full or empty, and then need the RETIRE_OLD_CACHED_CHUNKS
>> scan, doesn't it make more sense to do this only in tcache_large_cleanup?
> Well, in a practical use case, and considering it is only used for large
> chunks, I did not experience any overhead of this mechanism, unless it
> is somehow affecting the smaller chunks overhead too.

Obviously it adds more overhead to smaller chunks since you can free ~20000
1K chunks before you consider releasing them. That's a serious O(N^2) bug.

> Regarding only doing it is tcache_large_cleanup, when the num_slots ==
> 0, it could still mean that 6*4MB could be retained in that largest
> tcache bin forever, if the program allocates and deallocates those sizes
> and never really allocates or deallocates something so big.

Tcache_count=16 today and we're discussing increasing it to 24 or 32.
So it means today you could have like 384MB of chunks cached in large tcache
if you use a 4MB tcache_max. But even with the retire code, it will not retire
anything if you don't happen to use those sizes ever again...

These are serious numbers, so we do need to find a robust way to limit the amount
of memory cached by tcache.

>> That way you avoid all the overheads and only do some extra work if the bin
>> is full or empty. Also don't you need to do a full scan of all bins every now and
>> again anyway?
> I would personally leave that for the program to call tcache_trim, on
> idle times.

Most applications don't do that. There was a reason for the recently removed
consolidation phase. You want something that mostly works automatically.

>> So I'm wondering whether doing this when a bin is full/empty will work at all.
>> Wouldn't it be simpler to use an allocation counter and if it goes below zero
>> flush the current bin, and every now and again flush everything?
> IMHO, considering that large chunks do not have single sized chunks, the
> counter is really useless to evaluate if the elements should be retired
> or not. Flushing everything will really be awful in the mysql use case I
> presented in Cauldron. I get performance improvements even with
> MAX_TCACHE==1.

But so is only checking bins that are used. It's the bins that are unused but not
empty that need to be checked...

I don't see how flushing is a particular issue. The point is to give back old blocks,
and any block that is used frequently will quickly end up in tcache again.

>> In terms of implementation, there is a huge amount of special case code
>> being force inlined into the fast paths, including adding lots of calls.
> Do you mean that small chunk sizes are also being affected? If that is
> the case we should definitely fix it. If it is about the fast paths of
> the large chunks, that might be something that we will need to live
> with. Again, in practice I have seen no performance degradation.

I believe it is both. It should be easy to come up with testcases that show
dramatic slowdowns due to all the redundant linked list traversals.

>> This is
>> terrible for performance - even for the small bins. The correct approach is to
>> call a no-inline function to handle the special cases outside the fast paths.
> Ok. That is surprising and unexpected to me. Can you please detail how
> it is affecting the small bins.

Well adding huge amounts of code and function calls always makes code slow,
especially if it was already highly optimized. Just keep only fastpath code in
libc_malloc/free and use tailcalls to handle the slow paths.

Cheers,
Wilco