> 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 freed entry. at_refcnt will work the same as it does now. its use in art_walk is an elegant hack in my opinion. dlg > >> ok? >> >> Index: art.c >> =================================================================== >> RCS file: /cvs/src/sys/net/art.c,v >> retrieving revision 1.14 >> diff -u -p -r1.14 art.c >> --- art.c 13 Apr 2016 08:04:14 -0000 1.14 >> +++ art.c 1 Jun 2016 05:26:51 -0000 >> @@ -490,10 +490,6 @@ art_table_delete(struct art_root *ar, st >> KASSERT(prev == node); >> #endif >> >> - /* We are removing an entry from this table. */ >> - if (art_table_free(ar, at)) >> - return (node); >> - >> /* Get the next most specific route for the index `i'. */ >> if ((i >> 1) > 1) >> next = at->at_heap[i >> 1].node; >> @@ -512,6 +508,9 @@ art_table_delete(struct art_root *ar, st >> else >> at->at_heap[i].node = next; >> >> + /* We have removed an entry from this table. */ >> + art_table_free(ar, at); >> + >> return (node); >> } >>
