On 04/01/2015 02:48 PM, Peter Zijlstra wrote:
On Wed, Apr 01, 2015 at 02:54:45PM -0400, Waiman Long wrote:
On 04/01/2015 02:17 PM, Peter Zijlstra wrote:
On Wed, Apr 01, 2015 at 07:42:39PM +0200, Peter Zijlstra wrote:
Hohumm.. time to think more I think ;-)
So bear with me, I've not really pondered this well so it could be full
of holes (again).
After the cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL) succeeds the
spin_unlock() must do the hash lookup, right? We can make the lookup
unhash.
If the cmpxchg() fails the unlock will not do the lookup and we must
unhash.
The idea being that the result is that any lookup is guaranteed to find
an entry, which reduces our worst case lookup cost to whatever the worst
case insertion cost was.
I think it doesn't matter who did the unhashing. Multiple independent locks
can be hashed to the same value. Since they can be unhashed independently,
there is no way to know whether you have checked all the possible buckets.
oh but the crux is that you guarantee a lookup will find an entry. it will
never need to iterate the entire array.
I am sorry that I don't quite get what you mean here. My point is that
in the hashing step, a cpu will need to scan an empty bucket to put the
lock in. In the interim, an previously used bucket before the empty one
may get freed. In the lookup step for that lock, the scanning will stop
because of an empty bucket in front of the target one.
-Longman
_______________________________________________
Virtualization mailing list
Virtualization@xxxxxxxxxxxxxxxxxxxxxxxxxx
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
