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.
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
On Wed, Apr 01, 2015 at 03:58:58PM -0400, Waiman Long wrote:> On 04/01/2015 02:48 PM, Peter Zijlstra wrote:> 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.Right, that's broken. So we need to do something else to limit the lookup, because without that break, a lookup that needs to iterate the entire array in order to determine -ENOENT, which is expensive. So my alternative proposal is that IFF we can guarantee that every lookup will succeed -- the entry we're looking for is always there, we don't need the break on empty but can probe until we find the entry. This will be bound in cost to the same number if probes we required for insertion and avoids the full array scan. Now I think we can indeed do this, if as said earlier we do not clear the bucket on insert if the cmpxchg succeeds, in that case the unlock will observe _Q_SLOW_VAL and do the lookup, the lookup will then find the entry. And we then need the unlock to clear the entry. Does that explain this? Or should I try again with code?