On 01/06/16(Wed) 19:27, David Gwynne wrote: > > > On 1 Jun 2016, at 4:13 PM, Martin Pieuchot <[email protected]> wrote: > > > > On 01/06/16(Wed) 15:31, David Gwynne wrote: > >> currently it leaves early if it is the last entry being removed, > >> which is an optimisation. in the future it is possible for another > >> cpu to have a reference to the table while the last reference is > >> being dropped, so we need to scrub it in case it gets read. > > > > Are you saying that the counter of routes inside a table will be > > incremented in other places? > > > > Currently the only place where I used it as a "reference" counter is > > in art_table_walk(). Note that this is a difference with the original > > design, so I'd appreciate a commenter explaining why we do not remove > > the table at this point. > > > > I tried to keep the code as close as the pseudo algorithm described in > > the paper as possible. I thought that this would help readers > > understanding it. > > > > Or should we use a different field? > > hrm. > > the context of this is i hope to allow reads/traversals of the art data > structures via srp_enter/follow/leave, but with modifications serialised by a > mutex. when i say reference above i mean via srp, not a count with at_refcnt. > > the at_refcnts do the same amount of counting before and after this diff. > currently at_refcnt is dropped before the heap is updated, and if at_refcnt > drops to 0 we dont bother updating the heap cos it will be freed and nothing > will read it. after this diff heap is unconditionally cleaned up before > at_refcnt is dropped and the table gets made available for freeing. the > reason for this is i hope to make the tables readable via srps. > > assume the following where cpu0 is walking a table with a single entry on it, > and cpu1 is removing that same entry it: > > 1. cpu0 srp refs the table > 2. cpu1 searches for the entry and reaches the same table > 3. cpu1 begins gc of the table (which waits cos cpu0 has a ref) > 4. cpu1 frees the entry because it is no longer referenced anywhere (srp or > counted) > 5. cpu0 srp_follows an entry in the heap > > scrubbing the heap between 2 and 3 mean that step 5 wont access the free > entry.
So if I understand correctly you're saying that a heap should always be cleaned up before being freed? Because you're about to use a reference on a heap as a proxy for a reference on a node, right? In this case I'm ok with your diff. Note that the current code does not clear the default entry of a table, we might need to take care of it as well for the same reason. > at_refcnt will work the same as it does now. its use in art_walk is an > elegant hack in my opinion. /blush
