Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 26 Jul 2015 13:10:48 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Multithreaded program VSZ increasing due to bad free()
 strategy

On Sun, Jul 26, 2015 at 05:17:11PM +0300, Timo Teras wrote:
> Hi,
> 
> It seems that the current free() strategy of "allocate all free
> neighbors" has results in huge VSZ sizes (while RSS size keeps small).
> 
> The problem is that when the free() is made release most of the heap,
> and simultaneous malloc() occurs on another thread it is likely to
> extend heap. This is because free() has all memory allocated, and is
> executing madvise() (or several of them) which is slow.

That's not how I would characterize the problem. Rather, I would say
the problem is that the bins which are only empty because free is in
the middle of merging their chunks get marked empty and unlocked
momentarily, allowing another thread calling malloc to see them as
empty rather than busy. Fixing this looks complicated, though.

> The result is that heap keeps getting extended all the time increasing
> VSZ, and the slowing down the program (madvise is slower, the larger
> area it's telling about). Though, due to madvise calls RSS stays low,
> and it's not actually using any of that memory.
> 
> It would probably help a bit, to just move madvise() out from the for
> loop as one free() can result in multiple madvise() calls if other
> thread simultaneously free()'s neighboring areas and retried test of
> (self->psize & next->csize & C_INUSE) while locks held fails. It would
> probably make sense to move madvise() just out of loop when the final
> block size is known.

That makes sense, but I don't think it will solve the problem.

> But the strategy really needs to be better. When a multithreaded
> reactive program is mainly allocating temporary space and frees it
> soon after, it almost always end up in the race that free() holds
> locked most of the heap in preparation to merge it to one big
> continuous chunk. Causing the unwanted consequences.
> 
> Ideas?

I want to get rid of the current madvise strategy and instead have
excessive amounts of contiguous free memory (beyond a few times the
largest chunk that could be allocated in them) get put in an
_allocated_ state rather than a free state, with the malloc system
"owning" them and preventing their reuse until free chunks are
exhausted. This would prevent a lot of the madvise "ping-pong" and we
could actually recover commit charge by replacing the body of the
mapping with PROT_NONE rather than using MADV_DONTNEED. (There are
also proposals for faster ways to achieve the same thing kernelside
but afaik they're stalled.)

But in the mean time I'm not sure what the best solution is. I think
we need to find a way to prevent the "wrongly empty" bins from being
visible. Perhaps alloc_fwd and alloc_rev could refrain from using
unbin and unlock_bin and instead help the caller keep a mask of bins
it has locked and which need to be masked off when the free is
finished...

Rich

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.