Unneeded Code Found??
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
[email protected]
Quoted 23 lines · Randy Appleton
I think I have found some useless code in the Linux kernel in the block request functions.
I have modified the
__make_requestfunction inll_rw_blk.c. Now every request for a block off the hard drive is logged.The function
__make_requesthas 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).
Quoted 8 lines
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?
Signature · 3 lines
bill davidsen <[email protected]> CTO TMR Associates, Inc Doing interesting things with small computers since 1979
Quoted 30 lines · Bill Davidsen
Quoted 28 lines · Randy Appleton
I think I have found some useless code in the Linux kernel in the block request functions.
I have modified the
__make_requestfunction inll_rw_blk.c. Now every request for a block off the hard drive is logged.The function
__make_requesthas 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.
Quoted 6 lines
Quoted 3 lines
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?
Quoted 15 lines · Randy Appleton
Quoted 2 lines · Bill Davidsen
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.
Quoted 3 lines
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?
Quoted 42 lines · Randy Appleton
Quoted 30 lines · Bill Davidsen
Quoted 28 lines · Randy Appleton
I think I have found some useless code in the Linux kernel in the block request functions.
I have modified the
__make_requestfunction inll_rw_blk.c. Now every request for a block off the hard drive is logged.The function
__make_requesthas 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.
Quoted 7 lines
Quoted 3 lines
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.
Quoted 9 lines
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.
Quoted 29 lines · Nick Piggin
Quoted 29 lines
Quoted 29 lines
Quoted 27 lines · Randy Appleton
I think I have found some useless code in the Linux kernel in the block request functions.
I have modified the
__make_requestfunction inll_rw_blk.c. Now every request for a block off the hard drive is logged.The function
__make_requesthas 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.
Quoted 7 lines
Quoted 3 lines
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.
Quoted 19 lines · Randy Appleton
I have modified the
__make_requestfunction inll_rw_blk.c. Now every request for a block off the hard drive is logged.The function
__make_requesthas 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).
Quoted 3 lines
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'.
Quoted 3 lines
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.
Signature · 1 line
Jens Axboe
Quoted 6 lines · Randy Appleton
Quoted 2 lines · Nick Piggin
Yes it gets used.
Quoted 9 lines
Quoted 2 lines
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.
Quoted 24 lines · Nick Piggin
Quoted 12 lines · Randy Appleton
Quoted 4 lines · Nick Piggin
Yes it gets used.
I think its a lot more common with direct io and when you have lots of processes.
Quoted 5 lines
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.
Quoted 8 lines
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.