[PATCH 1/2] malloc: fix an over-allocation bug

[PATCH 1/2] malloc: fix an over-allocation bug

[Alexander Monakov]

Fix an instance where realloc code would overallocate by OVERHEAD bytes
amount. Manually arrange for reuse of memcpy-free-return exit sequence.
---
 src/malloc/malloc.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
index 9e05e1d6..1af4ae5a 100644
--- a/src/malloc/malloc.c
+++ b/src/malloc/malloc.c
@@ -397,10 +397,9 @@ void *realloc(void *p, size_t n)
 		size_t newlen = n + extra;
 		/* Crash on realloc of freed chunk */
 		if (extra & 1) a_crash();
-		if (newlen < PAGE_SIZE && (new = malloc(n))) {
-			memcpy(new, p, n-OVERHEAD);
-			free(p);
-			return new;
+		if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
+			n0 = n;
+			goto copy_free_ret;
 		}
 		newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
 		if (oldlen == newlen) return p;
@@ -443,6 +442,7 @@ copy_realloc:
 	/* As a last resort, allocate a new chunk and copy to it. */
 	new = malloc(n-OVERHEAD);
 	if (!new) return 0;
+copy_free_ret:
 	memcpy(new, p, n0-OVERHEAD);
 	free(CHUNK_TO_MEM(self));
 	return new;
-- 
2.11.0

[PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Alexander Monakov]

Split 'free' into unmap_chunk and bin_chunk, use the latter to introduce
__malloc_donate and use it in reclaim_gaps instead of calling 'free'.
---
v2:
* drop attribute-cold annotation
* adjust __malloc_donate:
	 * drop comparison against MMAP_THRESHOLD
	 * check donated chunk size just once

 ldso/dynlink.c      | 15 +++-----------
 src/malloc/malloc.c | 60 +++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 45 insertions(+), 30 deletions(-)

diff --git a/ldso/dynlink.c b/ldso/dynlink.c
index 9bf6924b..bdf901dd 100644
--- a/ldso/dynlink.c
+++ b/ldso/dynlink.c
@@ -476,23 +476,14 @@ static void redo_lazy_relocs()
 /* A huge hack: to make up for the wastefulness of shared libraries
  * needing at least a page of dirty memory even if they have no global
  * data, we reclaim the gaps at the beginning and end of writable maps
- * and "donate" them to the heap by setting up minimal malloc
- * structures and then freeing them. */
+ * and "donate" them to the heap. */
 
 static void reclaim(struct dso *dso, size_t start, size_t end)
 {
-	size_t *a, *z;
+	void __malloc_donate(char *, char *);
 	if (start >= dso->relro_start && start < dso->relro_end) start = dso->relro_end;
 	if (end   >= dso->relro_start && end   < dso->relro_end) end = dso->relro_start;
-	start = start + 6*sizeof(size_t)-1 & -4*sizeof(size_t);
-	end = (end & -4*sizeof(size_t)) - 2*sizeof(size_t);
-	if (start>end || end-start < 4*sizeof(size_t)) return;
-	a = laddr(dso, start);
-	z = laddr(dso, end);
-	a[-2] = 1;
-	a[-1] = z[0] = end-start + 2*sizeof(size_t) | 1;
-	z[1] = 1;
-	free(a);
+	__malloc_donate(laddr(dso, start), laddr(dso, end));
 }
 
 static void reclaim_gaps(struct dso *dso)
diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
index 1af4ae5a..2666fe1b 100644
--- a/src/malloc/malloc.c
+++ b/src/malloc/malloc.c
@@ -299,6 +299,8 @@ static int pretrim(struct chunk *self, size_t n, int i, int j)
 	return 1;
 }
 
+static void bin_chunk(struct chunk *);
+
 static void trim(struct chunk *self, size_t n)
 {
 	size_t n1 = CHUNK_SIZE(self);
@@ -314,7 +316,7 @@ static void trim(struct chunk *self, size_t n)
 	next->psize = n1-n | C_INUSE;
 	self->csize = n | C_INUSE;
 
-	free(CHUNK_TO_MEM(split));
+	bin_chunk(split);
 }
 
 void *malloc(size_t n)
@@ -448,29 +450,14 @@ copy_free_ret:
 	return new;
 }
 
-void free(void *p)
+static void bin_chunk(struct chunk *self)
 {
-	struct chunk *self, *next;
+	struct chunk *next = NEXT_CHUNK(self);
 	size_t final_size, new_size, size;
 	int reclaim=0;
 	int i;
 
-	if (!p) return;
-
-	self = MEM_TO_CHUNK(p);
-
-	if (IS_MMAPPED(self)) {
-		size_t extra = self->psize;
-		char *base = (char *)self - extra;
-		size_t len = CHUNK_SIZE(self) + extra;
-		/* Crash on double free */
-		if (extra & 1) a_crash();
-		__munmap(base, len);
-		return;
-	}
-
 	final_size = new_size = CHUNK_SIZE(self);
-	next = NEXT_CHUNK(self);
 
 	/* Crash on corrupted footer (likely from buffer overflow) */
 	if (next->psize != self->csize) a_crash();
@@ -531,3 +518,40 @@ void free(void *p)
 
 	unlock_bin(i);
 }
+
+static void unmap_chunk(struct chunk *self)
+{
+	size_t extra = self->psize;
+	char *base = (char *)self - extra;
+	size_t len = CHUNK_SIZE(self) + extra;
+	/* Crash on double free */
+	if (extra & 1) a_crash();
+	__munmap(base, len);
+}
+
+void free(void *p)
+{
+	if (!p) return;
+
+	struct chunk *self = MEM_TO_CHUNK(p);
+
+	if (IS_MMAPPED(self))
+		unmap_chunk(self);
+	else
+		bin_chunk(self);
+}
+
+void __malloc_donate(char *start, char *end)
+{
+	ssize_t align_start_up = (SIZE_ALIGN - 1) & -(uintptr_t)start;
+	ssize_t align_end_down = (SIZE_ALIGN - 1) &  (uintptr_t)end;
+	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
+	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
+	start += align_start_up;
+	end   -= align_end_down;
+
+	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
+	c->psize = n->csize = C_INUSE;
+	c->csize = n->psize = C_INUSE | chunk_size;
+	bin_chunk(c);
+}
-- 
2.11.0

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Rich Felker]

On Mon, Apr 16, 2018 at 08:54:36PM +0300, Alexander Monakov wrote:
> Split 'free' into unmap_chunk and bin_chunk, use the latter to introduce
> __malloc_donate and use it in reclaim_gaps instead of calling 'free'.
> ---
> v2:
> * drop attribute-cold annotation
> * adjust __malloc_donate:
> 	 * drop comparison against MMAP_THRESHOLD
> 	 * check donated chunk size just once
> 
>  ldso/dynlink.c      | 15 +++-----------
>  src/malloc/malloc.c | 60 +++++++++++++++++++++++++++++++++++++----------------
>  2 files changed, 45 insertions(+), 30 deletions(-)
> 
> [...]
> 
> +void __malloc_donate(char *start, char *end)
> +{
> +	ssize_t align_start_up = (SIZE_ALIGN - 1) & -(uintptr_t)start;
> +	ssize_t align_end_down = (SIZE_ALIGN - 1) &  (uintptr_t)end;
> +	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
> +	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
> +	start += align_start_up;
> +	end   -= align_end_down;
> +
> +	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
> +	c->psize = n->csize = C_INUSE;
> +	c->csize = n->psize = C_INUSE | chunk_size;
> +	bin_chunk(c);
> +}

I think this version of the size logic is harder to read than the old
one, and inconsistent with how malloc does accounting internally. In
the notation used everywhere else, "chunk size" always includes
OVERHEAD plus the usable space; it's the distance between the chunk
header and the next chunk header.

I also don't like use of signed arithmetic with sizes. I thought all
the values were nonnegative anyway, so I wasn't sure why you
introduced signed types, but apparently chunk_size can be negative and
the comparison against OVERHEAD+SIZE_ALIGN relies on the RHS being
signed (and on the unsigned result of the expression initializing
chunk_size getting coerced to signed) to work.

I think the above code may also be wrong. start is aligned mod
SIZE_ALIGN, so start+OVERHEAD is misaligned, and therefore not a valid
argument to MEM_TO_CHUNK. Continuing further along this line of
reasoning, aligning start up mod SIZE_ALIGN like you're doing is not
sufficient. There must also be space for a header below the aligned
point.

What about the following version, based on your original?

	// Ensure that adjustment can't move start past end.
	if (end-start < SIZE_ALIGN + OVERFLOW) return;

	// Reserve space for header below start and then align.
	start += OVERHEAD + SIZE_ALIGN - 1;
	start -= (uintptr_t)start & (SIZE_ALIGN - 1);
	end -= (uintptr_t)end & (SIZE_ALIGN - 1);

	// At this point, end-start is a multiple of SIZE_ALIGN,
	// and is thus a valid size unless it's zero.
	if (start == end) return;

	// Setup chunk headers and bin the new free chunk.
	struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
	c->psize = n->csize = C_INUSE;
	c->csize = n->psize = C_INUSE | chunk_size;
	bin_chunk(c);

I don't see any clean way to write the first size check such that it
encompasses the second one, and trying to wait til the second one to
do any checking risks overflow issues that move end past start and
thus give wrong results when computing end-start. That could be
avoided by checking end-start<PTRDIFF_MAX explicitly, but then we
reintroduce 2 branches and it seems just as expensive, but less
obvious, than doing it the above way.

Rich

Re: [PATCH 1/2] malloc: fix an over-allocation bug

[Rich Felker]

On Mon, Apr 16, 2018 at 08:54:35PM +0300, Alexander Monakov wrote:
> Fix an instance where realloc code would overallocate by OVERHEAD bytes
> amount. Manually arrange for reuse of memcpy-free-return exit sequence.
> ---
>  src/malloc/malloc.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
> index 9e05e1d6..1af4ae5a 100644
> --- a/src/malloc/malloc.c
> +++ b/src/malloc/malloc.c
> @@ -397,10 +397,9 @@ void *realloc(void *p, size_t n)
>  		size_t newlen = n + extra;
>  		/* Crash on realloc of freed chunk */
>  		if (extra & 1) a_crash();
> -		if (newlen < PAGE_SIZE && (new = malloc(n))) {
> -			memcpy(new, p, n-OVERHEAD);
> -			free(p);
> -			return new;
> +		if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
> +			n0 = n;
> +			goto copy_free_ret;
>  		}
>  		newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
>  		if (oldlen == newlen) return p;
> @@ -443,6 +442,7 @@ copy_realloc:
>  	/* As a last resort, allocate a new chunk and copy to it. */
>  	new = malloc(n-OVERHEAD);
>  	if (!new) return 0;
> +copy_free_ret:
>  	memcpy(new, p, n0-OVERHEAD);
>  	free(CHUNK_TO_MEM(self));
>  	return new;

Looks ok. I've got this queued as submitted.

Rich

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Alexander Monakov]

> > +void __malloc_donate(char *start, char *end)
> > +{
> > +	ssize_t align_start_up = (SIZE_ALIGN - 1) & -(uintptr_t)start;
> > +	ssize_t align_end_down = (SIZE_ALIGN - 1) &  (uintptr_t)end;
> > +	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
> > +	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
> > +	start += align_start_up;
> > +	end   -= align_end_down;
> > +
> > +	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
> > +	c->psize = n->csize = C_INUSE;
> > +	c->csize = n->psize = C_INUSE | chunk_size;
> > +	bin_chunk(c);
> > +}
> 
> I think this version of the size logic is harder to read than the old
> one, and inconsistent with how malloc does accounting internally. In
> the notation used everywhere else, "chunk size" always includes
> OVERHEAD plus the usable space; it's the distance between the chunk
> header and the next chunk header.

Same here. In 'ssize_t chunk_size = ...', OVERHEAD is subtracted once to
account for the sentinel/footer; to compute usable size, OVERHEAD would
need to be subtracted twice.

> I also don't like use of signed arithmetic with sizes. I thought all
> the values were nonnegative anyway, so I wasn't sure why you
> introduced signed types, but apparently chunk_size can be negative and
> the comparison against OVERHEAD+SIZE_ALIGN relies on the RHS being
> signed (and on the unsigned result of the expression initializing
> chunk_size getting coerced to signed) to work.

Well, 'end - start' is a signed expression to begin with, so I doubt a
coercion is taking place there.

Is there a problem with assuming OVERHEAD+SIZE_ALIGN is signed?

> I think the above code may also be wrong. start is aligned mod
> SIZE_ALIGN, so start+OVERHEAD is misaligned, and therefore not a valid
> argument to MEM_TO_CHUNK. Continuing further along this line of
> reasoning, aligning start up mod SIZE_ALIGN like you're doing is not
> sufficient. There must also be space for a header below the aligned
> point.

Yes, that's an oversight, but easily corrected: we need to adjust 'start'
so it's congruent to -OVERHEAD (rather than 0) modulo SIZE_ALIGN:

void __malloc_donate(char *start, char *end)
{
	ssize_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD);
	ssize_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end;
	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
	start += align_start_up;
	end   -= align_end_down;

	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
	c->psize = n->csize = C_INUSE;
	c->csize = n->psize = C_INUSE | chunk_size;
	bin_chunk(c);
}

The above addresses the alignment issue, and I've responded to other
concerns. Do you need a new patch with this?

Alexander

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Rich Felker]

On Tue, Apr 17, 2018 at 08:30:40AM +0300, Alexander Monakov wrote:
> > > +void __malloc_donate(char *start, char *end)
> > > +{
> > > +	ssize_t align_start_up = (SIZE_ALIGN - 1) & -(uintptr_t)start;
> > > +	ssize_t align_end_down = (SIZE_ALIGN - 1) &  (uintptr_t)end;
> > > +	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
> > > +	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
> > > +	start += align_start_up;
> > > +	end   -= align_end_down;
> > > +
> > > +	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
> > > +	c->psize = n->csize = C_INUSE;
> > > +	c->csize = n->psize = C_INUSE | chunk_size;
> > > +	bin_chunk(c);
> > > +}
> > 
> > I think this version of the size logic is harder to read than the old
> > one, and inconsistent with how malloc does accounting internally. In
> > the notation used everywhere else, "chunk size" always includes
> > OVERHEAD plus the usable space; it's the distance between the chunk
> > header and the next chunk header.
> 
> Same here. In 'ssize_t chunk_size = ...', OVERHEAD is subtracted once to
> account for the sentinel/footer; to compute usable size, OVERHEAD would
> need to be subtracted twice.

In the above code,
	-start - align_start_up = 0 mod SIZE_ALIGN
	end - align_end_down = 0 mod SIZE_ALIGN
	-OVERHEAD = -OVERHEAD mod SIZE_ALIGN
so chunk_size is -OVERHEAD mod SIZE_ALIGN, not 0 mod SIZE_ALIGN.

With the below fix to the definition of align_start_up, I think it's
correct, but I still don't understand what you meant by the above
"subtracted once for the sentinel/footer".

> > I also don't like use of signed arithmetic with sizes. I thought all
> > the values were nonnegative anyway, so I wasn't sure why you
> > introduced signed types, but apparently chunk_size can be negative and
> > the comparison against OVERHEAD+SIZE_ALIGN relies on the RHS being
> > signed (and on the unsigned result of the expression initializing
> > chunk_size getting coerced to signed) to work.
> 
> Well, 'end - start' is a signed expression to begin with, so I doubt a
> coercion is taking place there.

Indeed. I was mistakenly thinking they had type uintptr_t, which would
probably be preferable when working with addresses that aren't
actually pointers to objects, but as-written the difference is signed
and it seems ok.

> Is there a problem with assuming OVERHEAD+SIZE_ALIGN is signed?

Indeed, I didn't notice but it's actually false:

#define SIZE_ALIGN (4*sizeof(size_t))
#define OVERHEAD (2*sizeof(size_t))

So yes it's a problem.

Note that with things fixed so chunk_size is a multiple of SIZE_ALIGN,
this issue goes away, because all you need is:

	if (chunk_size <= 0) return;

This is because (chunk_size>0 && chunk_size%SIZE_ALIGN==0) implies
(algebraically) chunk_size>=SIZE_ALIGN.

> > I think the above code may also be wrong. start is aligned mod
> > SIZE_ALIGN, so start+OVERHEAD is misaligned, and therefore not a valid
> > argument to MEM_TO_CHUNK. Continuing further along this line of
> > reasoning, aligning start up mod SIZE_ALIGN like you're doing is not
> > sufficient. There must also be space for a header below the aligned
> > point.
> 
> Yes, that's an oversight, but easily corrected: we need to adjust 'start'
> so it's congruent to -OVERHEAD (rather than 0) modulo SIZE_ALIGN:
> 
> void __malloc_donate(char *start, char *end)
> {
> 	ssize_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD);

Upon first reading I thought this was just wrong -- it doesn't reserve
space and align, it only aligns to OVERHEAD mod SIZE_ALIGN, possibly
without reserving any space. However, I see the space is later
reserved via start+OVERHEAD (passed to MEM_TO_CHUNK).

> 	ssize_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end;
> 	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);

Because OVERHEAD is unsigned, this transits through unsigned and back
to signed by assignment, but it should be safe anyway...

> 	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
> 	start += align_start_up;
> 	end   -= align_end_down;
> 
> 	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
> 	c->psize = n->csize = C_INUSE;
> 	c->csize = n->psize = C_INUSE | chunk_size;
> 	bin_chunk(c);
> }
> 
> The above addresses the alignment issue, and I've responded to other
> concerns. Do you need a new patch with this?

I want something that I'm confident is safe to apply. And I want
progress made reviewing to be a step towards commit, not something
that gets thrown out every time there's a new version of the patch
with a completely different approach.

I'm perfectly ok with committing the slightly-fixed variant of your
first version I posted, and that's probably my leaning unless there's
a strong reason to prefer a different approach. If there is, the new
patch needs to be convincing that it's correct, and should not require
restarting the review process all over again...

Rich

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Rich Felker]

On Tue, Apr 17, 2018 at 11:57:27AM -0400, Rich Felker wrote:
> > Is there a problem with assuming OVERHEAD+SIZE_ALIGN is signed?
> 
> Indeed, I didn't notice but it's actually false:
> 
> #define SIZE_ALIGN (4*sizeof(size_t))
> #define OVERHEAD (2*sizeof(size_t))
> 
> So yes it's a problem.
> 
> Note that with things fixed so chunk_size is a multiple of SIZE_ALIGN,
> this issue goes away, because all you need is:
> 
> 	if (chunk_size <= 0) return;
> 
> This is because (chunk_size>0 && chunk_size%SIZE_ALIGN==0) implies
> (algebraically) chunk_size>=SIZE_ALIGN.
> 
> > > I think the above code may also be wrong. start is aligned mod
> > > SIZE_ALIGN, so start+OVERHEAD is misaligned, and therefore not a valid
> > > argument to MEM_TO_CHUNK. Continuing further along this line of
> > > reasoning, aligning start up mod SIZE_ALIGN like you're doing is not
> > > sufficient. There must also be space for a header below the aligned
> > > point.
> > 
> > Yes, that's an oversight, but easily corrected: we need to adjust 'start'
> > so it's congruent to -OVERHEAD (rather than 0) modulo SIZE_ALIGN:
> > 
> > void __malloc_donate(char *start, char *end)
> > {
> > 	ssize_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD);
> 
> Upon first reading I thought this was just wrong -- it doesn't reserve
> space and align, it only aligns to OVERHEAD mod SIZE_ALIGN, possibly
> without reserving any space. However, I see the space is later
> reserved via start+OVERHEAD (passed to MEM_TO_CHUNK).
> 
> > 	ssize_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end;
> > 	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
> 
> Because OVERHEAD is unsigned, this transits through unsigned and back
> to signed by assignment, but it should be safe anyway...
> 
> > 	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
> > 	start += align_start_up;
> > 	end   -= align_end_down;
> > 
> > 	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
> > 	c->psize = n->csize = C_INUSE;
> > 	c->csize = n->psize = C_INUSE | chunk_size;
> > 	bin_chunk(c);
> > }
> > 
> > The above addresses the alignment issue, and I've responded to other
> > concerns. Do you need a new patch with this?
> 
> I want something that I'm confident is safe to apply. And I want
> progress made reviewing to be a step towards commit, not something
> that gets thrown out every time there's a new version of the patch
> with a completely different approach.
> 
> I'm perfectly ok with committing the slightly-fixed variant of your
> first version I posted, and that's probably my leaning unless there's
> a strong reason to prefer a different approach. If there is, the new
> patch needs to be convincing that it's correct, and should not require
> restarting the review process all over again...

If you prefer the new approach, is the following version okay? It
avoids mixing signed and unsigned arithmetic (or any expressions where
the the value could exceed the range [0,SIZE_MAX/2-1]).

void __malloc_donate(char *start, char *end)
{
	size_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD);
	size_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end;

	if (end - start <= OVERHEAD + align_start_up + align_end_down)
		return;
	start += align_start_up + OVERHEAD;
	end   -= align_end_down;

	struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
	c->psize = n->csize = C_INUSE;
	c->csize = n->psize = C_INUSE | (end-start);
	bin_chunk(c);
}

Strictly speaking moving +OVERHEAD into start wasn't needed, but I did
it so the idiomatic end-start could be used for the size below rather
than recomputing it in a potentially inconsistent or un-idiomatic way.

At this point it's actually very close to the proposed fix-up (with
another small fix) I made for your original version:

void __malloc_donate(char *start, char *end)
{
	if (end-start < SIZE_ALIGN + OVERFLOW) return;
	start += OVERHEAD + SIZE_ALIGN - 1;
	start -= (uintptr_t)start & (SIZE_ALIGN - 1);
	end -= (uintptr_t)end & (SIZE_ALIGN - 1);
	if (start == end) return;

	struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
	c->psize = n->csize = C_INUSE;
	c->csize = n->psize = C_INUSE | (end-start);
	bin_chunk(c);
}

The last 4 lines are identical; your newer approach just has one
conditional instead of 2, but more temp vars.

Rich

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Rich Felker]

On Tue, Apr 17, 2018 at 01:06:24PM -0400, Rich Felker wrote:
> On Tue, Apr 17, 2018 at 11:57:27AM -0400, Rich Felker wrote:
> > > Is there a problem with assuming OVERHEAD+SIZE_ALIGN is signed?
> > 
> > Indeed, I didn't notice but it's actually false:
> > 
> > #define SIZE_ALIGN (4*sizeof(size_t))
> > #define OVERHEAD (2*sizeof(size_t))
> > 
> > So yes it's a problem.
> > 
> > Note that with things fixed so chunk_size is a multiple of SIZE_ALIGN,
> > this issue goes away, because all you need is:
> > 
> > 	if (chunk_size <= 0) return;
> > 
> > This is because (chunk_size>0 && chunk_size%SIZE_ALIGN==0) implies
> > (algebraically) chunk_size>=SIZE_ALIGN.
> > 
> > > > I think the above code may also be wrong. start is aligned mod
> > > > SIZE_ALIGN, so start+OVERHEAD is misaligned, and therefore not a valid
> > > > argument to MEM_TO_CHUNK. Continuing further along this line of
> > > > reasoning, aligning start up mod SIZE_ALIGN like you're doing is not
> > > > sufficient. There must also be space for a header below the aligned
> > > > point.
> > > 
> > > Yes, that's an oversight, but easily corrected: we need to adjust 'start'
> > > so it's congruent to -OVERHEAD (rather than 0) modulo SIZE_ALIGN:
> > > 
> > > void __malloc_donate(char *start, char *end)
> > > {
> > > 	ssize_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD);
> > 
> > Upon first reading I thought this was just wrong -- it doesn't reserve
> > space and align, it only aligns to OVERHEAD mod SIZE_ALIGN, possibly
> > without reserving any space. However, I see the space is later
> > reserved via start+OVERHEAD (passed to MEM_TO_CHUNK).
> > 
> > > 	ssize_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end;
> > > 	ssize_t chunk_size = end - start - (OVERHEAD + align_start_up + align_end_down);
> > 
> > Because OVERHEAD is unsigned, this transits through unsigned and back
> > to signed by assignment, but it should be safe anyway...
> > 
> > > 	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;
> > > 	start += align_start_up;
> > > 	end   -= align_end_down;
> > > 
> > > 	struct chunk *c = MEM_TO_CHUNK(start + OVERHEAD), *n = MEM_TO_CHUNK(end);
> > > 	c->psize = n->csize = C_INUSE;
> > > 	c->csize = n->psize = C_INUSE | chunk_size;
> > > 	bin_chunk(c);
> > > }
> > > 
> > > The above addresses the alignment issue, and I've responded to other
> > > concerns. Do you need a new patch with this?
> > 
> > I want something that I'm confident is safe to apply. And I want
> > progress made reviewing to be a step towards commit, not something
> > that gets thrown out every time there's a new version of the patch
> > with a completely different approach.
> > 
> > I'm perfectly ok with committing the slightly-fixed variant of your
> > first version I posted, and that's probably my leaning unless there's
> > a strong reason to prefer a different approach. If there is, the new
> > patch needs to be convincing that it's correct, and should not require
> > restarting the review process all over again...
> 
> If you prefer the new approach, is the following version okay? It
> avoids mixing signed and unsigned arithmetic (or any expressions where
> the the value could exceed the range [0,SIZE_MAX/2-1]).
> 
> void __malloc_donate(char *start, char *end)
> {
> 	size_t align_start_up = (SIZE_ALIGN - 1) & (-(uintptr_t)start - OVERHEAD);
> 	size_t align_end_down = (SIZE_ALIGN - 1) & (uintptr_t)end;
> 
> 	if (end - start <= OVERHEAD + align_start_up + align_end_down)
> 		return;
> 	start += align_start_up + OVERHEAD;
> 	end   -= align_end_down;
> 
> 	struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
> 	c->psize = n->csize = C_INUSE;
> 	c->csize = n->psize = C_INUSE | (end-start);
> 	bin_chunk(c);
> }
> 
> Strictly speaking moving +OVERHEAD into start wasn't needed, but I did
> it so the idiomatic end-start could be used for the size below rather
> than recomputing it in a potentially inconsistent or un-idiomatic way.
> 
> At this point it's actually very close to the proposed fix-up (with
> [...]

Testing now, at least one problem still remains: end<start is actually
possible due to the way ldso calls __malloc_donate. The current
upstream reclaim() checked that explicitly and bailed out; the patch
removes the check.

The form:

	if (chunk_size < OVERHEAD + SIZE_ALIGN) return;

would catch this if not for the signedness issue. But at this point
I'm really tired of trying to work out all sorts of fragile subtleties
like that. I'm just going to put the check back where it was and
commit something based on this, and we can make further improvements
later if desired.

Rich

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Alexander Monakov]

> I'm really tired of trying to work out all sorts of fragile subtleties
> like that.

... and I regret pinging the patch :)

I did not anticipate this to cause a sizeable distraction and hoped on
balance it'd be a positive experience. Seems not.

Is a roll back to a non-irritated state possible?

Alexander

Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate

[Rich Felker]

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

On Tue, Apr 17, 2018 at 11:52:59PM +0300, Alexander Monakov wrote:
> > I'm really tired of trying to work out all sorts of fragile subtleties
> > like that.
> 
> .... and I regret pinging the patch :)

:)

Don't worry, the outcome is better than if you hadn't I think. It was
a prerequisite for other stuff people are requesting about
interposable malloc and sparked some other fixes I have pending now.

> I did not anticipate this to cause a sizeable distraction and hoped on
> balance it'd be a positive experience. Seems not.
> 
> Is a roll back to a non-irritated state possible?

Yes. I'll attach what I have queued up for possible push. Let me know
if it looks okay with you.

Rich

[-- Attachment #2: 0001-ldso-malloc-implement-reclaim_gaps-via-__malloc_dona.patch --]
[-- Type: text/plain, Size: 4068 bytes --]

From 4c651a999f00f5be3a2882c2e8f37a0431fc4347 Mon Sep 17 00:00:00 2001
From: Alexander Monakov <amonakov@ispras.ru>
Date: Mon, 16 Apr 2018 20:54:36 +0300
Subject: [PATCH] ldso, malloc: implement reclaim_gaps via __malloc_donate

Split 'free' into unmap_chunk and bin_chunk, use the latter to introduce
__malloc_donate and use it in reclaim_gaps instead of calling 'free'.
---
 ldso/dynlink.c      | 16 ++++----------
 src/malloc/malloc.c | 61 +++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 47 insertions(+), 30 deletions(-)

diff --git a/ldso/dynlink.c b/ldso/dynlink.c
index 9bf6924..b9ff41b 100644
--- a/ldso/dynlink.c
+++ b/ldso/dynlink.c
@@ -476,23 +476,15 @@ static void redo_lazy_relocs()
 /* A huge hack: to make up for the wastefulness of shared libraries
  * needing at least a page of dirty memory even if they have no global
  * data, we reclaim the gaps at the beginning and end of writable maps
- * and "donate" them to the heap by setting up minimal malloc
- * structures and then freeing them. */
+ * and "donate" them to the heap. */
 
 static void reclaim(struct dso *dso, size_t start, size_t end)
 {
-	size_t *a, *z;
+	void __malloc_donate(char *, char *);
 	if (start >= dso->relro_start && start < dso->relro_end) start = dso->relro_end;
 	if (end   >= dso->relro_start && end   < dso->relro_end) end = dso->relro_start;
-	start = start + 6*sizeof(size_t)-1 & -4*sizeof(size_t);
-	end = (end & -4*sizeof(size_t)) - 2*sizeof(size_t);
-	if (start>end || end-start < 4*sizeof(size_t)) return;
-	a = laddr(dso, start);
-	z = laddr(dso, end);
-	a[-2] = 1;
-	a[-1] = z[0] = end-start + 2*sizeof(size_t) | 1;
-	z[1] = 1;
-	free(a);
+	if (start >= end) return;
+	__malloc_donate(laddr(dso, start), laddr(dso, end));
 }
 
 static void reclaim_gaps(struct dso *dso)
diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
index db19bc3..6605ec3 100644
--- a/src/malloc/malloc.c
+++ b/src/malloc/malloc.c
@@ -299,6 +299,8 @@ static int pretrim(struct chunk *self, size_t n, int i, int j)
 	return 1;
 }
 
+static void bin_chunk(struct chunk *);
+
 static void trim(struct chunk *self, size_t n)
 {
 	size_t n1 = CHUNK_SIZE(self);
@@ -314,7 +316,7 @@ static void trim(struct chunk *self, size_t n)
 	next->psize = n1-n | C_INUSE;
 	self->csize = n | C_INUSE;
 
-	free(CHUNK_TO_MEM(split));
+	bin_chunk(split);
 }
 
 void *malloc(size_t n)
@@ -465,29 +467,14 @@ copy_free_ret:
 	return new;
 }
 
-void free(void *p)
+static void bin_chunk(struct chunk *self)
 {
-	struct chunk *self, *next;
+	struct chunk *next = NEXT_CHUNK(self);
 	size_t final_size, new_size, size;
 	int reclaim=0;
 	int i;
 
-	if (!p) return;
-
-	self = MEM_TO_CHUNK(p);
-
-	if (IS_MMAPPED(self)) {
-		size_t extra = self->psize;
-		char *base = (char *)self - extra;
-		size_t len = CHUNK_SIZE(self) + extra;
-		/* Crash on double free */
-		if (extra & 1) a_crash();
-		__munmap(base, len);
-		return;
-	}
-
 	final_size = new_size = CHUNK_SIZE(self);
-	next = NEXT_CHUNK(self);
 
 	/* Crash on corrupted footer (likely from buffer overflow) */
 	if (next->psize != self->csize) a_crash();
@@ -548,3 +535,41 @@ void free(void *p)
 
 	unlock_bin(i);
 }
+
+static void unmap_chunk(struct chunk *self)
+{
+	size_t extra = self->psize;
+	char *base = (char *)self - extra;
+	size_t len = CHUNK_SIZE(self) + extra;
+	/* Crash on double free */
+	if (extra & 1) a_crash();
+	__munmap(base, len);
+}
+
+void free(void *p)
+{
+	if (!p) return;
+
+	struct chunk *self = MEM_TO_CHUNK(p);
+
+	if (IS_MMAPPED(self))
+		unmap_chunk(self);
+	else
+		bin_chunk(self);
+}
+
+void __malloc_donate(char *start, char *end)
+{
+	size_t align_start_up = (SIZE_ALIGN-1) & (-(uintptr_t)start - OVERHEAD);
+	size_t align_end_down = (SIZE_ALIGN-1) & (uintptr_t)end;
+
+	if (end - start <= OVERHEAD + align_start_up + align_end_down)
+		return;
+	start += align_start_up + OVERHEAD;
+	end   -= align_end_down;
+
+	struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
+	c->psize = n->csize = C_INUSE;
+	c->csize = n->psize = C_INUSE | (end-start);
+	bin_chunk(c);
+}
-- 
2.10.0