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

[Dave Anderson]

----- Original Message -----
> 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

I like the idea...

But it won't work on ia64 machines, where the vmalloc space is contained
within the region starting at a000000000000000, which is below the unity-mapped
region starting at e000000000000000.

I put in a debug statement to show the "start" and "end" values passed
to search():

  crash> mach
                MACHINE TYPE: ia64
                 MEMORY SIZE: 15.7 GB
                        CPUS: 2
             PROCESSOR SPEED: 1594 Mhz
                          HZ: 1000
                   PAGE SIZE: 16384
           KERNEL STACK SIZE: 32768
        KERNEL CACHED REGION: e000000000000000
      KERNEL UNCACHED REGION: c000000000000000
       KERNEL VMALLOC REGION: a000000000000000
      USER DATA/STACK REGION: 8000000000000000
      USER DATA/STACK REGION: 6000000000000000
            USER TEXT REGION: 4000000000000000
   USER SHARED MEMORY REGION: 2000000000000000
  USER IA32 EMULATION REGION: 0000000000000000
  crash> search -k deadbeef
  start: a000000100000000 end: ffffffffffffffff
  ... [ cut ] ...
  crash> search -K deadbeef
  start: a000000100000000 end: a000000200000000
  ... [ cut ] ...
  crash>

So it looks like it might need a hack for ia64 anyway, which
already has a few.  I don't think any of the other arches have
their vmalloc regions below their unity-mapped regions.

Dave