Process level smart pointers
Joe Seigh
SMR hazard pointers. Maybe VZOOM. It's a bit of a pain but it could be
done.
Once you have this capability you can put your shared data in a read only
shared memory segment and access it that way. No expensive interprocess
communication require. Just direct memory access.
A possible application would be nscd, the name services cache daemon. Just
read cache directly. The formula for the cost of cached look ups would be
ci + p*cx
where
ci = cost of cache lookup
cx = cost of not in cache lookup
p = probability not in cache
You could assume the difference between ci and cx is significant, otherwise why
have nscd. A couple of complications. I've written host lookups using libbind
and they are mind boggling fast, like faster than some in host stuff. And the
nscd's I've see just use the old non thread-safe libresolve (gethostbyname) made
threadsafe (gethostbyname_r) by adding an internal global lock. So even though
the lookups are super fast, a HOST NOT FOUND slows every thing down, since
it is basically a timeout and everything is queued up behind that request gets
their response time delayed as well. nscd is faster since you can avoid that
global lock by resolving from cache which would use a different lock. And cache
lookups are fast, no timeouts.
So nice idea but maybe nscd is just too brain damaged to try it out on.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
> plain
> SMR hazard pointers. Maybe VZOOM. It's a bit of a pain but it could be
> done.
Yeah, VZOOM would work well with this scheme. I did something kind of like
that for a shared-memory allocator/garbage-collector I had to create during
VZOOM's development stage. It used a prototype of VZOOM to count the total
number of references to a global shared memory-heap object, and the
individual blocks within the heap. A process was basically a global
distributed proxy count, and a local distributed proxy count. A single
global instance of VZOOM managed the registered processes global counts, and
a per-process instance of VZOOM managed the local counts. It guaranteed that
a shared-memory heap object would never be "decommited" if any thread in any
registered process owned a reference to it, or any block within it. A
processes reader threads could access the shared objects that exist within
the blocks without any storeload memsync. I used the scheme to create a
robust futex emulation for windows.
Joe Seigh
>>You can make process level smart pointers using RCU, RCU+SMR, or just
>>plain
>>SMR hazard pointers. Maybe VZOOM. It's a bit of a pain but it could be
>>done.
> the blocks without any storeload memsync. I used the scheme to create a
> robust futex emulation for windows.
That robust futex in Linux is a little strange for a number of reasons.
One, they're hard coding more of their mutex implementation into what
was supposed to be a general purpose synchronization primative. Secondly,
they've hard coded probably not the best solution to the problem. I did
robust rwlocks with ipc semaphores. The original version just gave an
error return and didn't have the fix capability but I proposed somewhere
that you could do it like Linux robust futex is doing or have a designated
thread be responsible for fixing things. It would block until the lock
was broken. That's probably a better idea since you can control who's
responsible to fix things up and given that one thread screwed up would
you trust another thread from the same process to do the right thing.
But they've pretty much painted themselves into a corner. And they can't
do a robust rwlock which you can do with process level smart pointers. Not
unless they hard code rwlock logic into the futex internals.
Note that if you have the shared data protected by a robust read lock
in a read only shared segment then you are pretty much guaranteed that
the data wasn't corrupted by the rogue thread. The reason for the read
lock isn't to protect the data but to ensure a consistent view of the
shared data. Futexes are at risk here since they have writable shared
state. Process level smart pointers (some of them anyway) don't share
any writable state with any other processes.
Chris Thomasson
news:wY2dnZ6e14N...@comcast.com...
> Chris Thomasson wrote:
>>>You can make process level smart pointers using RCU, RCU+SMR, or just
>>>plain
>>>SMR hazard pointers. Maybe VZOOM. It's a bit of a pain but it could be
>>>done.
> [...]
>> the blocks without any storeload memsync. I used the scheme to create a
>> robust futex emulation for windows.
>
> That robust futex in Linux is a little strange for a number of reasons.
> One, they're hard coding more of their mutex implementation into what
> was supposed to be a general purpose synchronization primative. Secondly,
> they've hard coded probably not the best solution to the problem. I did
> robust rwlocks with ipc semaphores. The original version just gave an
> error return and didn't have the fix capability but I proposed somewhere
> that you could do it like Linux robust futex is doing or have a designated
> thread be responsible for fixing things. It would block until the lock
> was broken.
That's kind of how I did it. The global instance of VZOOM assigned a unique
id to a process and each shared futex had an owner field in the high-word of
the 64-bit futex value. A locking process stored the id in that field. If
the polling logic of the global instance of VZOOM found a "dead" process, it
would search a list of pointers to "active" shared futex values for a
high-word that matched the dead processes id. If it found one it would
adjust/fix the waitqueue and use CAS to swing the mutex into and "abandoned"
state and then signal the waitqueue. Very crude but it seemed to work...
;)
> Note that if you have the shared data protected by a robust read lock
> in a read only shared segment then you are pretty much guaranteed that
> the data wasn't corrupted by the rogue thread. The reason for the read
> lock isn't to protect the data but to ensure a consistent view of the
> shared data.
Yeah, certain embodiment of VZOOM uses something similar to ensure
visibility.
> Futexes are at risk here since they have writable shared state.
Definitely.
> Process level smart pointers (some of them anyway) don't share
> any writable state with any other processes.
Yup.
Chris Thomasson
Off-Topic---
Did your RCU+SMR require a release barrier before you set a hazard to null?
Joe Seigh
or any smart pointer for that matter. Even for references to immutable
objects. That's a load/store barrier on systems that require it. RCU+SMR
doesn't require it because it's really RCU+SMR+RCU. There's an extra RCU
grace period to effect the release semantics.
Chris Thomasson
> Chris Thomasson wrote:
>>>You can make process level smart pointers using RCU, RCU+SMR
>>
>>
>> Off-Topic---
>>
>> Did your RCU+SMR require a release barrier before you set a hazard to
>> null?
> Release semantics are required anytime you store into a non-null hazard
> pointer
> or any smart pointer for that matter. Even for references to immutable
> objects. That's a load/store barrier on systems that require it. RCU+SMR
> doesn't require it because it's really RCU+SMR+RCU. There's an extra RCU
> grace period to effect the release semantics.
Drop object to zero; wait for "another" sync-epoch; dtor?
VZOOM can use a couple of methods to get rid of the release barrier. One is
a purely thread-local solution. A thread simply performs persistent
reference adjustments during an epoch transition. Another solution is
basically the same as yours. I kind of like the first solution because it
keeps things local, and the actual polling logic doesn't need to be
adjusted.
Joe Seigh
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:dI6dnREi4NJ...@comcast.com...
>
>>Chris Thomasson wrote:
>>>Did your RCU+SMR require a release barrier before you set a hazard to
>>>null?
>>
>>Release semantics are required anytime you store into a non-null hazard
>>pointer
>>or any smart pointer for that matter. Even for references to immutable
>>objects. That's a load/store barrier on systems that require it. RCU+SMR
>>doesn't require it because it's really RCU+SMR+RCU. There's an extra RCU
>>grace period to effect the release semantics.
>
>
> Drop object to zero; wait for "another" sync-epoch; dtor?
Basicallly.
>
> VZOOM can use a couple of methods to get rid of the release barrier. One is
> a purely thread-local solution. A thread simply performs persistent
> reference adjustments during an epoch transition. Another solution is
> basically the same as yours. I kind of like the first solution because it
> keeps things local, and the actual polling logic doesn't need to be
> adjusted.
>
The release semantics are for accesses to the object itself, not the
pointer to the object. So having thread local operations on the
pointer doesn't help. Fortunately, if you're using a proxy scheme,
the overhead of a release barrier won't impact performance all that
greatly. For hazard pointers which get stored into multiple times
every time a collection is traversed, it does matter greatly.
Chris Thomasson
>
> Basicallly.
>
>>
>> VZOOM can use a couple of methods to get rid of the release barrier. One
>> is a purely thread-local solution. A thread simply performs persistent
>> reference adjustments during an epoch transition. Another solution is
>> basically the same as yours. I kind of like the first solution because it
>> keeps things local, and the actual polling logic doesn't need to be
>> adjusted.
>
> The release semantics are for accesses to the object itself, not the
> pointer to the object.
Yes. In my implementation a threads epoch transition executes an implicit
release barrier. I can perform the count adjustments after the barrier, and
before the next epoch. That ensures that all of the effects of the prior
epoch are applied and made visible before any of the adjustments were
applied. It also ensures that the adjustments are made visible before the
next epoch executes. VZOOM can do this portably by relying on POSIX mutex
semantics...
> For hazard pointers which get stored into multiple times
> every time a collection is traversed, it does matter greatly.
Absolutely.
Chris Thomasson
> release barrier. I can perform the count adjustments after the barrier,
> and before the next epoch.
I should clarify that only reference count "decrements" need to be applied
after the release barrier. Reference increments don't apply here as they can
safely occur within "proxy gc regions".