Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 17 Apr 2018 15:01:51 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via
 __malloc_donate

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

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.