[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20180417170624.GD3094@brightrain.aerifal.cx>
Date: Tue, 17 Apr 2018 13:06:24 -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 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
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.
