On Tue, May 10, 2005 at 09:32:07AM -0400, Joe Seigh wrote:
> I think you need a release memory barrier if you store into a hazard
> pointer that is non null to prevent prior accesses from occurring after
> the store. That's an extra memory barrier for hazard pointers that I
> overlooked. One thing that could be done is wait an extra RCU grace
> period after the hazard pointer scan to ensure prior accesses have
> completed before freeing the resource. That would lengthen the delay
> to approximately 2 RCU grace periods. Could be a problem if you have
> a high write rate and are trying to keep that delay minimal.
>
> There might be another way. I'd have to investigate it a little more.
Here is what I thought you were suggesting for the updater:
Remove item from list
Send IPIs to all CPUs, relying on exact interrupts (which might
not be present on all CPUs) to serialize the instruction
streams of the other CPUs
Wait for all IPIs to complete
Wait until there are no hazard pointers referencing the item
before freeing.
For the traverser:
1. allocate hazard pointer (SW engr problem: what to do if
allocation fails? If deeply nested, holding locks, &c?)
2. retry:
3. Pick up pointer, store into hazard pointer.
4. Tell the compiler not to reorder memory references across this point
5. If hazard pointer does not match the pointer, goto retry.
6. begin critical section
If the updater and traverser run concurrently, the interrupt forces
serialization -- look at all the possible interleavings to see this:
1. Before this point, the traverser cannot see the removed element.
2. Ditto.
3. Ditto.
4. Before this point, the traverser might have stored a pointer to
the remove element into the hazard pointer, but will see the
disappearance when it returns from interrupt.
5. Ditto.
6. At this point, the hazard pointer has been set, and the
interrupt will force memory ordering.
Similar reasoning when the traverser NULLs the hazard pointer.
Or am I missing something? Or is there some CPU that Linux supports that
does inexact interrupts?
I must admit that I am not completely comfortable with this approach -- it
needs to be beaten up pretty thoroughly with both testing and theoretical
analysis. And there might well be a flaw in my reasoning above. ;-)
Thanx, Paul
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
