On Thu, Oct 16, 2014 at 8:03 AM, Ryan Johnson
<ryan.johnson@cs.utoronto.ca> wrote:
> Why not use an RCU mechanism [1] and ditch the hazard pointers? Seems like
> an ideal fit...
>
> In brief, RCU has the following requirements:
>
> Read-heavy access pattern
> Writers must be able to make dead objects unreachable to new readers (easily
> done for most data structures)
> Writers must be able to mark dead objects in such a way that existing
> readers know to ignore their contents but can still traverse the data
> structure properly (usually straightforward)
> Readers must occasionally inform the system that they are not currently
> using any RCU-protected pointers (to allow resource reclamation)
Have a look at http://lwn.net/Articles/573424/ and specifically the
"URCU overview" section. Basically, that last requirement - that
readers inform the system tat they are not currently using any
RCU-protected pointers - turns out to require either memory barriers
or signals.
All of the many techniques that have been developed in this area are
merely minor variations on a very old theme: set some kind of flag
variable in shared memory to let people know that you are reading a
shared data structure, and clear it when you are done. Then, other
people can figure out when it's safe to recycle memory that was
previously part of that data structure. In Linux's RCU, the flag
variable is "whether the process is currently scheduled on a CPU",
which is obviously not workable from user-space. Lacking that, you
need an explicit flag variable, which means you need memory barriers,
since the protected operation is a load and the flag variable is
updated via a store. You can try to avoid some of the overhead by
updating the flag variable less often (say, when a signal arrives) or
you can make it more fine-grained (in my case, we only prevent reclaim
of a fraction of the data structure at a time, rather than all of it)
or various other variants, but none of this is unfortunately so simple
as "apply technique X and your problem just goes away".
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company