Multithreaded program VSZ increasing due to bad free() strategy

Multithreaded program VSZ increasing due to bad free() strategy

[Timo Teras]

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.

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.

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?

Thanks,
Timo

Re: Multithreaded program VSZ increasing due to bad free() strategy

[Rich Felker]

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

Re: Multithreaded program VSZ increasing due to bad free() strategy

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 800 bytes --]

On Sun, Jul 26, 2015 at 01:10:48PM -0400, Rich Felker wrote:
> 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...

The attached patch should mitigate the issue in practice by performing
madvise with the bin lock held and the binmap bit already set, so that
malloc waits for the lock while madvise is running rather than trying
to map new memory. There is still a race window when unnecessary
allocation will occur, but it should be much harder to hit. We can
work on better fixes later.

Rich

[-- Attachment #2: free_madv.diff --]
[-- Type: text/plain, Size: 1299 bytes --]

diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
index eb68d55..efe1f5e 100644
--- a/src/malloc/malloc.c
+++ b/src/malloc/malloc.c
@@ -464,18 +464,6 @@ void free(void *p)
 	if (next->psize != self->csize) a_crash();
 
 	for (;;) {
-		/* Replace middle of large chunks with fresh zero pages */
-		if (reclaim && (self->psize & next->csize & C_INUSE)) {
-			uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
-			uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
-#if 1
-			__madvise((void *)a, b-a, MADV_DONTNEED);
-#else
-			__mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
-				MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
-#endif
-		}
-
 		if (self->psize & next->csize & C_INUSE) {
 			self->csize = final_size | C_INUSE;
 			next->psize = final_size | C_INUSE;
@@ -517,5 +505,17 @@ void free(void *p)
 	if (!(mal.binmap & 1ULL<<i))
 		a_or_64(&mal.binmap, 1ULL<<i);
 
+	/* Replace middle of large chunks with fresh zero pages */
+	if (reclaim) {
+		uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
+		uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
+#if 1
+		__madvise((void *)a, b-a, MADV_DONTNEED);
+#else
+		__mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
+			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
+#endif
+	}
+
 	unlock_bin(i);
 }