Unneeded Code Found??

Unneeded Code Found??

[Randy Appleton]

I think I have found some useless code in the Linux kernel
in the block request functions.
                                                                                         
 
I have modified the __make_request function in ll_rw_blk.c.
Now every request for a block off the hard drive is logged.
                                                                                         
 
The function __make_request has code to attempt to merge the current
block request with some contigious existing request for better
performance. This merge function keeps a one-entry cache pointing to the
last block request made.  An attempt is made to merge the current
request with the last request, and if that is not possible then
a search of the whole queue is done, looking at merger possibililites.
                                                                                         
 
Looking at the data from my logs, I notice that over 50% of all requests
can be merged.  However, a merge only ever happens between the
current request and the previous one.  It never happens between the
current request and any other request that might be in the queue (for
more than 50,000 requests examined).
                                                                                         
 
This is true for several test runs, including "daily usage" and doing
two kernel compiles at the same time.  I have only tested on a
single-CPU machine.
                                                                                         
 
I wonder if the code (and CPU time) used to search the entire request
queue is actually useful.  Would this be a reasonable candidate for code
elimination?

-Much Thanks
-Randy Appleton
rappleto@nmu.edu

Re: Unneeded Code Found??

[Bill Davidsen]

Randy Appleton wrote:
> I think I have found some useless code in the Linux kernel
> in the block request functions.
>                                                                                         
> 
> I have modified the __make_request function in ll_rw_blk.c.
> Now every request for a block off the hard drive is logged.
>                                                                                         
> 
> The function __make_request has code to attempt to merge the current
> block request with some contigious existing request for better
> performance. This merge function keeps a one-entry cache pointing to the
> last block request made.  An attempt is made to merge the current
> request with the last request, and if that is not possible then
> a search of the whole queue is done, looking at merger possibililites.
>                                                                                         
> 
> Looking at the data from my logs, I notice that over 50% of all requests
> can be merged.  However, a merge only ever happens between the
> current request and the previous one.  It never happens between the
> current request and any other request that might be in the queue (for
> more than 50,000 requests examined).
>                                                                                         
> 
> This is true for several test runs, including "daily usage" and doing
> two kernel compiles at the same time.  I have only tested on a
> single-CPU machine.
>                                                                                         
> 
> I wonder if the code (and CPU time) used to search the entire request
> queue is actually useful.  Would this be a reasonable candidate for code
> elimination?

If you never get a hit, it means either (a) your test load actually 
doesn't have one, or (b) the code isn't correctly finding them.

Of course if your disk is keeping up and the queue is short, then you 
may simply not have anything in the queue to match.

Any of this kick a train of thought?


-- 
bill davidsen <davidsen@tmr.com>
   CTO TMR Associates, Inc
   Doing interesting things with small computers since 1979

Re: Unneeded Code Found??

[Randy Appleton]

Bill Davidsen wrote:

> Randy Appleton wrote:
>
>> I think I have found some useless code in the Linux kernel
>> in the block request functions.
>>                                                                                         
>>
>> I have modified the __make_request function in ll_rw_blk.c.
>> Now every request for a block off the hard drive is logged.
>>                                                                                         
>>
>> The function __make_request has code to attempt to merge the current
>> block request with some contigious existing request for better
>> performance. This merge function keeps a one-entry cache pointing to the
>> last block request made.  An attempt is made to merge the current
>> request with the last request, and if that is not possible then
>> a search of the whole queue is done, looking at merger possibililites.
>>                                                                                         
>>
>> Looking at the data from my logs, I notice that over 50% of all requests
>> can be merged.  However, a merge only ever happens between the
>> current request and the previous one.  It never happens between the
>> current request and any other request that might be in the queue (for
>> more than 50,000 requests examined).
>>                                                                                         
>>
>> This is true for several test runs, including "daily usage" and doing
>> two kernel compiles at the same time.  I have only tested on a
>> single-CPU machine.
>>                                                                                         
>>
>> I wonder if the code (and CPU time) used to search the entire request
>> queue is actually useful.  Would this be a reasonable candidate for code
>> elimination?
>
>
> If you never get a hit, it means either (a) your test load actually 
> doesn't have one, or (b) the code isn't correctly finding them.


It might be buggy code on my part, but it looks pretty solid to me.   
I'd be happy to show anyone interested.
My load ought to find such a merge, if they happen with any freqency at 
all.  Compiling two kernels
at the same time and "general running" are my two current loads.  The 
disk queue gets to over 70
entries, which is rather high for a personal workstation, and I'm 
searching tens of thousands to accesses
in total.

Does anyone know that this code is actualy useful?  Has anyone ever seen 
it actually do a merge of consecutive
data accesses for requests that were not issued themselves consequtively?

Re: Unneeded Code Found??

[Mike Fedyk]

On Sun, Jan 18, 2004 at 07:58:55PM -0500, Randy Appleton wrote:
> Bill Davidsen wrote:
> >If you never get a hit, it means either (a) your test load actually 
> >doesn't have one, or (b) the code isn't correctly finding them.
> 
> 
> It might be buggy code on my part, but it looks pretty solid to me.   
> I'd be happy to show anyone interested.
> My load ought to find such a merge, if they happen with any freqency at 
> all.  Compiling two kernels
> at the same time and "general running" are my two current loads.  The 
> disk queue gets to over 70
> entries, which is rather high for a personal workstation, and I'm 
> searching tens of thousands to accesses
> in total.
> 
> Does anyone know that this code is actualy useful?  Has anyone ever seen 
> it actually do a merge of consecutive
> data accesses for requests that were not issued themselves consequtively?


What kernel version are you testing against?

Re: Unneeded Code Found??

[Nick Piggin]

Randy Appleton wrote:

> Bill Davidsen wrote:
>
>> Randy Appleton wrote:
>>
>>> I think I have found some useless code in the Linux kernel
>>> in the block request functions.
>>>                                                                                         
>>>
>>> I have modified the __make_request function in ll_rw_blk.c.
>>> Now every request for a block off the hard drive is logged.
>>>                                                                                         
>>>
>>> The function __make_request has code to attempt to merge the current
>>> block request with some contigious existing request for better
>>> performance. This merge function keeps a one-entry cache pointing to 
>>> the
>>> last block request made.  An attempt is made to merge the current
>>> request with the last request, and if that is not possible then
>>> a search of the whole queue is done, looking at merger possibililites.
>>>                                                                                         
>>>
>>> Looking at the data from my logs, I notice that over 50% of all 
>>> requests
>>> can be merged.  However, a merge only ever happens between the
>>> current request and the previous one.  It never happens between the
>>> current request and any other request that might be in the queue (for
>>> more than 50,000 requests examined).
>>>                                                                                         
>>>
>>> This is true for several test runs, including "daily usage" and doing
>>> two kernel compiles at the same time.  I have only tested on a
>>> single-CPU machine.
>>>                                                                                         
>>>
>>> I wonder if the code (and CPU time) used to search the entire request
>>> queue is actually useful.  Would this be a reasonable candidate for 
>>> code
>>> elimination?
>>
>>
>>
>> If you never get a hit, it means either (a) your test load actually 
>> doesn't have one, or (b) the code isn't correctly finding them.
>
>
>
> It might be buggy code on my part, but it looks pretty solid to me.   
> I'd be happy to show anyone interested.
> My load ought to find such a merge, if they happen with any freqency 
> at all.  Compiling two kernels
> at the same time and "general running" are my two current loads.  The 
> disk queue gets to over 70
> entries, which is rather high for a personal workstation, and I'm 
> searching tens of thousands to accesses
> in total.
>
> Does anyone know that this code is actualy useful?  Has anyone ever 
> seen it actually do a merge of consecutive
> data accesses for requests that were not issued themselves consequtively?
>

Yes it gets used.

I think its a lot more common with direct io and when you have lots of
processes.

Re: Unneeded Code Found??

[Randy Appleton]

Nick Piggin wrote:

>>> Randy Appleton wrote:
>>>
>>>> I think I have found some useless code in the Linux kernel
>>>> in the block request functions.
>>>>                                                                                         
>>>>
>>>> I have modified the __make_request function in ll_rw_blk.c.
>>>> Now every request for a block off the hard drive is logged.
>>>>                                                                                         
>>>>
>>>> The function __make_request has code to attempt to merge the current
>>>> block request with some contigious existing request for better
>>>> performance. This merge function keeps a one-entry cache pointing 
>>>> to the
>>>> last block request made.  An attempt is made to merge the current
>>>> request with the last request, and if that is not possible then
>>>> a search of the whole queue is done, looking at merger possibililites.
>>>>                                                                                         
>>>>
>>>> Looking at the data from my logs, I notice that over 50% of all 
>>>> requests
>>>> can be merged.  However, a merge only ever happens between the
>>>> current request and the previous one.  It never happens between the
>>>> current request and any other request that might be in the queue (for
>>>> more than 50,000 requests examined).
>>>>                                                                                         
>>>>
>>>> This is true for several test runs, including "daily usage" and doing
>>>> two kernel compiles at the same time.  I have only tested on a
>>>> single-CPU machine.
>>>>
>> Does anyone know that this code is actualy useful?  Has anyone ever 
>> seen it actually do a merge of consecutive
>> data accesses for requests that were not issued themselves 
>> consequtively?
>>
> Yes it gets used.
>
> I think its a lot more common with direct io and when you have lots of
> processes.

I'm not arguing, but how do you know this?  I'm trying to convince 
myself that the code is used, and at least on my system
a few days of general use, followed by heavy parallel compiles, doesn't 
use the code even once.

I have not tested direct I/O.  Otherwise it looks unused.

Re: Unneeded Code Found??

[Nick Piggin]

Randy Appleton wrote:

> Nick Piggin wrote: 


>
>> Yes it gets used.
>>
>> I think its a lot more common with direct io and when you have lots of
>> processes.
>
>
> I'm not arguing, but how do you know this?  I'm trying to convince 
> myself that the code is used, and at least on my system
> a few days of general use, followed by heavy parallel compiles, 
> doesn't use the code even once.
>
> I have not tested direct I/O.  Otherwise it looks unused.
>

Because I have seen it - I have instrumented it.

Your usage patterns are pretty tame actually. I remember having 100 
processes
randomly reading from the same part of the disk was one of my test cases.
You need direct IO otherwise everything ends up in pagecache.

I haven't seen workloads where it gets used a lot, but that doesn't mean 
they
don't exist, and I've never seen the code cause any problems, so there is no
need to make any trade offs by removing it.

Re: Unneeded Code Found??

[Randy Appleton]

Nick Piggin wrote:

>
>
> Randy Appleton wrote:
>
>> Nick Piggin wrote: 
>
>
>
>>
>>> Yes it gets used.
>>>
>>> I think its a lot more common with direct io and when you have lots of
>>> processes.
>>
>>
>>
>> I'm not arguing, but how do you know this?  I'm trying to convince 
>> myself that the code is used, and at least on my system
>> a few days of general use, followed by heavy parallel compiles, 
>> doesn't use the code even once.
>>
>> I have not tested direct I/O.  Otherwise it looks unused.
>>
>
> Because I have seen it - I have instrumented it.
>
> Your usage patterns are pretty tame actually. I remember having 100 
> processes
> randomly reading from the same part of the disk was one of my test cases.
> You need direct IO otherwise everything ends up in pagecache.
>
> I haven't seen workloads where it gets used a lot, but that doesn't 
> mean they
> don't exist, and I've never seen the code cause any problems, so there 
> is no
> need to make any trade offs by removing it.
>
O.K.  That's convincing.  Thanks for the time.

Re: Unneeded Code Found??

[Jens Axboe]

On Fri, Jan 09 2004, Randy Appleton wrote:
> I have modified the __make_request function in ll_rw_blk.c.
> Now every request for a block off the hard drive is logged.
>                                                                                         
> 
> The function __make_request has code to attempt to merge the current
> block request with some contigious existing request for better
> performance. This merge function keeps a one-entry cache pointing to the
> last block request made.  An attempt is made to merge the current
> request with the last request, and if that is not possible then
> a search of the whole queue is done, looking at merger possibililites.
>                                                                                         
> 
> Looking at the data from my logs, I notice that over 50% of all requests
> can be merged.  However, a merge only ever happens between the
> current request and the previous one.  It never happens between the
> current request and any other request that might be in the queue (for
> more than 50,000 requests examined).
>                                                                                         
> 
> This is true for several test runs, including "daily usage" and doing
> two kernel compiles at the same time.  I have only tested on a
> single-CPU machine.

It gets used, the fact that you don't hit it for your workload(s) is
pretty uninteresting. Try threaded io tests, for instance.

That said, the one-hit cache is pretty effective since a process usually
gets to submit more than one request at the time (which is why it's
there). In 2.6 merges aren't as important anymore due to large io
submissions. You didn't say what version of the kernel you are looking
at though, so kind of hard to really say anything about your
'investigation'.

> I wonder if the code (and CPU time) used to search the entire request
> queue is actually useful.  Would this be a reasonable candidate for code
> elimination?

In 2.4 it's a O(N) scan, which doubles as an insertion scan (meaning we
have to do it anyways). In 2.6 it's a hash lookup, quick enough.

You also didn't say how you are logging this info. If you are using
printk() to log every request you pretty much already Heisenberged your
test. Even without qualifying the supposedly wasted CPU time.

-- 
Jens Axboe