From: Rich Felker <dalias@libc.org>
To: musl@lists.openwall.com
Subject: Re: [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate
Date: Tue, 17 Apr 2018 11:57:27 -0400 [thread overview]
Message-ID: <20180417155727.GC3094@brightrain.aerifal.cx> (raw)
In-Reply-To: <alpine.LNX.2.20.13.1804170733330.29823@monopod.intra.ispras.ru>
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
next prev parent reply other threads:[~2018-04-17 15:57 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-04-16 17:54 [PATCH 1/2] malloc: fix an over-allocation bug Alexander Monakov
2018-04-16 17:54 ` [PATCH 2/2] ldso, malloc: implement reclaim_gaps via __malloc_donate Alexander Monakov
2018-04-16 22:39 ` Rich Felker
2018-04-17 5:30 ` Alexander Monakov
2018-04-17 15:57 ` Rich Felker [this message]
2018-04-17 17:06 ` Rich Felker
2018-04-17 19:01 ` Rich Felker
2018-04-17 20:52 ` Alexander Monakov
2018-04-17 22:21 ` Rich Felker
2018-04-16 22:40 ` [PATCH 1/2] malloc: fix an over-allocation bug Rich Felker
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180417155727.GC3094@brightrain.aerifal.cx \
--to=dalias@libc.org \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).