[Crash-utility] RFC: Improving crash's search speed

[Bob Montgomery]

I like using the search command in crash, but noticed that it takes much
longer than my own dump search tools.

As an example, on a level 31 (lots of exclusions) dump from a 4 GB
x86_64 system, this search command in (benchmarked with a command file)
finds these results and takes almost 2 minutes:

$ cat cmdfile2
search -k 0xffff88012491b240

$ time crash-5.1.1 kernel_link dump.201101161845 <cmdfile2
...

ffff88012491b280: ffff88012491b240
ffff880126dcca18: ffff88012491b240
ffff880126dcca20: ffff88012491b240
ffff880126dcca30: ffff88012491b240
ffff880126dcca88: ffff88012491b240
ffff880126eca148: ffff88012491b240
ffffc9000468d148: ffff88012491b240

real	1m52.834s
user	1m50.571s
sys	0m2.220s

When you watch it search, the first 6 results come out in a few seconds,
then nothing happens for a long time.

The first six are coming from searching the identity mapped region which
covers every page in the dump.  Note the forms of the addresses for the
first six hits.  

The majority of the search time is spent going through the kernel
vmalloc address range and checking to see if pages are mapped to any of
those addresses.  Any page searched through these addresses should have
already been searched in the identity mapped search.

So, for the last hit: (ffffc9000468d148: ffff88012491b240), converting
to physical, and then back to identity-mapped virtual gives:

crash-5.1.1> vtop 0xffffc9000468d148
VIRTUAL           PHYSICAL        
ffffc9000468d148  126eca148  
...

And:
crash-5.1.1> ptov 0x126eca148
VIRTUAL           PHYSICAL        
ffff880126eca148  126eca148 

And so the hit at 0xffffc9000468d148 was already caught by the earlier
hit in the identity-mapped range:
ffff880126eca148: ffff88012491b240

If you don't want to wait, you can find the vmalloc_start_addr from
"help -m" and use it to restrict the search range:

$ cat cmdfile2a
search -k -e 0xffffc90000000000 0xffff88012491b240

$ time crash-5.1.1 dump.201101161845 kernel_link <cmdfile2a

...
ffff88012491b280: ffff88012491b240
ffff880126dcca18: ffff88012491b240
ffff880126dcca20: ffff88012491b240
ffff880126dcca30: ffff88012491b240
ffff880126dcca88: ffff88012491b240
ffff880126eca148: ffff88012491b240

real	0m4.243s
user	0m4.088s
sys	0m0.156s

This command finishes with the first 6 hits in 4 seconds.

Once you have those hits, if you have to know if any virtual mappings
exist, you can use kmem on the physical address:

crash-5.1.1> vtop 0xffff880126eca148
VIRTUAL           PHYSICAL        
ffff880126eca148  126eca148 
...

crash-5.1.1> kmem -v 126eca148
   VM_STRUCT                 ADDRESS RANGE               SIZE
ffff8801277f8180  ffffc90004682000 -    1052672

Which shows the virtual range that contains the mapping for the page.
Then this command takes no time:

crash-5.1.1> search -k -s ffffc90004682000 -e ffffc90004783000
ffff88012491b240
ffffc9000468d148: ffff88012491b240



I think the drastic reduction of search time from 2 minutes to 4 seconds
is interesting enough to warrant a shortcut.

The attached patch implements the -K option that is the same as doing
"-k -e <vmalloc_start_addr>".

Comments?
Bob Montgomery





      





-------------- next part --------------
A non-text attachment was scrubbed...
Name: fastKsearch.patch
Type: text/x-patch
Size: 1347 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/crash-utility/attachments/20110125/11f605c3/attachment.bin>