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 11:57:27 -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 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

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.