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. It's a copy of the hash table used to track regions with minor tweaks so it'd be possible to make the existing code able to handle both but it would mean turning it into macros. I'm not sure which is the lesser evil for just 2 uses of a fairly simple data structure.
