On Sat, Sep 23, 2017 at 05:19:58PM -0400, Daniel Micay wrote:
> On Sat, 2017-09-23 at 09:32 +0200, Otto Moerbeek wrote:
> > On Fri, Sep 22, 2017 at 04:35:39PM -0400, Daniel Micay wrote:
> >
> > > A linear search works well for the current small quarantine (16) but
> > > won't work
> > > well if you ever want to have a larger / configurable quarantine
> > > size. It would
> > > also be nice to make this fast enough to enable by default.
> > >
> > > We (CopperheadOS) use an open addressed hash table for this based on
> > > the
> > > existing hash table since we use a larger quarantine with a FIFO
> > > queue
> > > alongside the random array and a configuration size. Ideally the
> > > code would be
> > > shared with the existing hash table but I didn't want to make it
> > > into an
> > > invasive change downstream.
> > >
> > > These are the three downstream patches for OpenBSD malloc in our
> > > copy of Bionic
> > > (Android libc), so I'd need to port them to the current upstream
> > > code to apply
> > > cleanly. They're currently applied after other changes and it's a
> > > slightly
> > > older copy of the base code (after multi-pool support, but before
> > > the canary
> > > rework since we'll need to adapt that to our needs). Can get the
> > > general idea
> > > from the patches even though they're not going to apply cleanly
> > > though.
> > >
> > > [1] quarantine double-free detection via hash table
> >
> > Thanks for sharing this, I'll take a look soon.
> >
> > Thinking a bit about this: wouldn't a closed hash table be sufficient?
> > A collision would then either be a double free, otherwise just replace
> > old with new. You'll get a O(1) lookup and insert and simpler code.
>
> I wouldn't really want to have a random chance of missing a double-free
> even if the chance is small though.
In the end all double frees still will be caught by the actual free
code, just with a delay. The delayed free buffer double free check is
just a way of catching it as soon as possible to make debugging
easier. That's the reason the originla code could just do the check
on the slot being replaced only.
The only case that could be missed is when the chunk is given out by
malloc in between the original free and the double free. But that
case never be caught in all circumstances since the delay buffer is of
finite size.
-Otto
