Linux Scalability Effort

On Fri, Feb 22, 2002 at 09:18:41AM -0800, Hanna Linder wrote:
>   3.1%  3.5%  0.6us(1047us)  3.2us( 979us)(0.07%)  25499542 96.5%  3.5%    0%  dcache_lock

IIUC, holding the dcache_lock while walking the path as long as
we can find things in cache should decrease the number of times
we grab dcache_lock, but it seems both 2.4.17 and fast-walk patch
take the lock 25 million times. Is there something missing here ?
Or are there too many cache misses ? Perhaps we need to investigate that.
Decreasing the dcache_lock acquisition should be a goal here.

Dipankar
-- 
Dipankar Sarma  <dipankar@...> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

--On Friday, February 22, 2002 23:52:04 +0530 Dipankar Sarma <dipankar@...> wrote:

> On Fri, Feb 22, 2002 at 09:18:41AM -0800, Hanna Linder wrote:
>>   3.1%  3.5%  0.6us(1047us)  3.2us( 979us)(0.07%)  25499542 96.5%  3.5%    0%  dcache_lock
> 
> IIUC, holding the dcache_lock while walking the path as long as
> we can find things in cache should decrease the number of times
> we grab dcache_lock, but it seems both 2.4.17 and fast-walk patch

	Well, I am actually adding holding the dcache_lock where
it was not held before (instead of incrementing d_count). So my
understanding is the dcache_lock contention should go up a little
bit. Although perhaps there is more tuning that needs to happen.

Hanna

Well, I am actually adding holding the dcache_lock where
    it was not held before (instead of incrementing d_count). So my
    understanding is the dcache_lock contention should go up a little
    bit. Although perhaps there is more tuning that needs to happen.

"contention"? or "use"? I think we need to be precise about these
terms.

I'm defining "contention" as "wanted the lock but it was taken".
Contention is often dependent on other cpu and interrupt code
interactions, whereas use can often be determined from inspection.
Consider the case where a lock is grabbed and released in some
function.  If you split that into two grabs/releases you can increase
the "use" of the lock but if both the original and new hold times are
fairly brief, you may not noticeably affect the "contention".
Similarly, reducing "use" *may* reduce contention, but only if that's
where the bottleneck was.

When I look at lockstat output and want to reduce contention for a
particular lock, I start by looking at the call with the longest hold
time for that lock. The longer a lock is being held, the more likely it
is that other requests will pile up behind it.  The one with the
highest "use" call will frequently be that one.  Can the hold time be
reduced?  If it can't, THEN can that long operation's "use" be reduced?
Picking away at locks held for 20us usually don't yield interesting
results when there are places where it is held for (say) 100ms.

Of course, many many very brief calls for a lock can induce "cache
thrash" where more of the time is spent just getting the data structure
to the proper cpu, not acquiring the actual lock itself.  I'm not sure
if lockstat measures (or can measure) cache thrash.  I'd presume that
time spent acquiring the lock (including waiting for it to be brought
into your cache) counts toward the "wait" rather than the "hold" time.
Does anybody know for sure?

Rick

On Fri, Feb 22, 2002 at 10:35:53AM -0800, Hanna Linder wrote:
> 
> 
> --On Friday, February 22, 2002 23:52:04 +0530 Dipankar Sarma <dipankar@...> wrote:
> 
> > On Fri, Feb 22, 2002 at 09:18:41AM -0800, Hanna Linder wrote:
> >>   3.1%  3.5%  0.6us(1047us)  3.2us( 979us)(0.07%)  25499542 96.5%  3.5%    0%  dcache_lock
> > 
> > IIUC, holding the dcache_lock while walking the path as long as
> > we can find things in cache should decrease the number of times
> > we grab dcache_lock, but it seems both 2.4.17 and fast-walk patch
> 
> 	Well, I am actually adding holding the dcache_lock where
> it was not held before (instead of incrementing d_count). So my
> understanding is the dcache_lock contention should go up a little
> bit. Although perhaps there is more tuning that needs to happen.

That is not what I understood. 

My point is this - if you are walking up /home/hanna/foo/mysql/blah,
in 2.4.17 you would have to do 6 d_lookup()s and thus acquire the
lock 6 times. If you hold the lock during cached lookups as long
as you can find them during walk and assuming all of them are in
cache, you will have only 1 acquisition of dcache_lock. But, yes,
the average lock hold time should increase.

Does this logic make sense or have I missed something ?

Thanks
-- 
Dipankar Sarma  <dipankar@...> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

>> > IIUC, holding the dcache_lock while walking the path as long as
>> > we can find things in cache should decrease the number of times
>> > we grab dcache_lock, but it seems both 2.4.17 and fast-walk patch
>> 
>> 	Well, I am actually adding holding the dcache_lock where
>> it was not held before (instead of incrementing d_count). So my
>> understanding is the dcache_lock contention should go up a little
>> bit. Although perhaps there is more tuning that needs to happen.
> 
> That is not what I understood. 
> 
> My point is this - if you are walking up /home/hanna/foo/mysql/blah,
> in 2.4.17 you would have to do 6 d_lookup()s and thus acquire the
> lock 6 times. If you hold the lock during cached lookups as long

	Yes that is the way I understand it too. But with many CPU's
all trying to access / and home for their path lookups too then wont
that increase contention because the dcache_lock is being held longer
by one cpu?

Hanna

On Fri, Feb 22, 2002 at 11:33:12AM -0800, Hanna Linder wrote:
> 
> > 
> > My point is this - if you are walking up /home/hanna/foo/mysql/blah,
> > in 2.4.17 you would have to do 6 d_lookup()s and thus acquire the
> > lock 6 times. If you hold the lock during cached lookups as long
> 
> 	Yes that is the way I understand it too. But with many CPU's
> all trying to access / and home for their path lookups too then wont
> that increase contention because the dcache_lock is being held longer
> by one cpu?

Yes, that is a possibility. Long avarage lock hold time and
large number of acquisitions with shorter lock hold time, both
can lead to high level of contention. It would depend on the
statistical distribution of the lock requests for that workload.

What we would need to do is to determine which is good for most
"real" workloads. It may happen that slightly longer lock hold time
with a drastic drop in acquisitions would give us good performance
because of less contention *and* reduced cacheline bouncing.

Besides there are always lock-free lookup techniques if necessary ;-)

Thanks
-- 
Dipankar Sarma  <dipankar@...> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

On Fri, Feb 22, 2002 at 11:33:12AM -0800, Hanna Linder wrote:
> 
> >> > IIUC, holding the dcache_lock while walking the path as long as
> >> > we can find things in cache should decrease the number of times
> >> > we grab dcache_lock, but it seems both 2.4.17 and fast-walk patch
> >> 
> >> 	Well, I am actually adding holding the dcache_lock where
> >> it was not held before (instead of incrementing d_count). So my
> >> understanding is the dcache_lock contention should go up a little
> >> bit. Although perhaps there is more tuning that needs to happen.
> > 
> > That is not what I understood. 
> > 
> > My point is this - if you are walking up /home/hanna/foo/mysql/blah,
> > in 2.4.17 you would have to do 6 d_lookup()s and thus acquire the
> > lock 6 times. If you hold the lock during cached lookups as long
> 
> 	Yes that is the way I understand it too. But with many CPU's

Looking at the lockstat output, of the 25 million acquisitions,
21 million comes from d_lookup() roughly the same distribution for
2.4.17. For some reason, cached_lookup() is getting called
without the dcache_lock held most of the time with fast_walk.
I would have expected dcache_lock to be held for a larger
number of cached_lookup()s which would avoid having to acquire
the dcache_lock again  by using __d_lookup().

Thanks
-- 
Dipankar Sarma  <dipankar@...> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

On Fri, Feb 22, 2002 at 11:00:08AM -0800, Rick Lindsley wrote:
> Of course, many many very brief calls for a lock can induce "cache
> thrash" where more of the time is spent just getting the data structure
> to the proper cpu, not acquiring the actual lock itself.  I'm not sure

Hmm... Here is how understood things -

There can be lock cacheline thrashing too if you have a large
number of brief acquisitions. If you have a spinlock implementation
where you spinwait reading the location and then do a atomic
dec/inc or xchg to acquire the lock, with a large number of
consumers, the probability of doing the dec/xchg and then finding
out that somebody else already got the lock increases significantly.
This means that there will be a lot cpus who will modify the
lock cacheline and then realize that somebody else already got the lock
before going back to spin. More modifications of the lock 
cacheline -> more bouncing.

> if lockstat measures (or can measure) cache thrash.  I'd presume that
> time spent acquiring the lock (including waiting for it to be brought
> into your cache) counts toward the "wait" rather than the "hold" time.
> Does anybody know for sure?

As far as I could understand the lockmeter code, yes.

I don't know how we can measure lock cache thrash - maybe
using PMC instrumentation (L2_LINES_IN) ?? IMO, a global lock
with lots of acquisitions is probably bad even if it is not
very contentious.

Thanks
-- 
Dipankar Sarma  <dipankar@...> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

> to the proper cpu, not acquiring the actual lock itself.  I'm not sure
> if lockstat measures (or can measure) cache thrash.  I'd presume that

	I know lockstat does not measure cache thrashing. This was
	brought up at an lse call a while ago to John Hawkes. As far 
	as I recall no one had even heard of a tool that could measure 
	cache hits/misses or thrashing. Sounds like something that 
	we could use...


> time spent acquiring the lock (including waiting for it to be brought
> into your cache) counts toward the "wait" rather than the "hold" time.
> Does anybody know for sure?

	John Hawkes or Ray Bryant might know.

Hanna

> 2.4.17. For some reason, cached_lookup() is getting called
> without the dcache_lock held most of the time with fast_walk.

That is probably because I need to hook up more sys_calls
to use path_lookup (new name for path_init_walk). Everything
except vfs is still using the old path walk path. I am going to
look into extending it to other filesystems.

Hanna

> I'd presume that
> time spent acquiring the lock (including waiting for it to be brought
> into your cache) counts toward the "wait" rather than the "hold" time.
> Does anybody know for sure?

When metering a spin_lock(), lockmeter first does a spin_trylock().  If
that's successful, then "hold" time begins.  If the spin_trylock() is
not successful, then the "wait" start-time is captured and an unmetered
spin_lock() is done.  When that acquisition completes, then the "wait"
end-time is captured.  So the answer is 'no', the "wait" time doesn't
count that initial spin_trylock().  And the "hold" time doesn't count
that initial spin_trylock(), either.  If people think this is important,
I can easily change it.

John Hawkes