Linear view and bv.get_linear_disassembly() are very slow in certain circumstances

To reproduce the issue:

int main(void) 
{ 
    int dummy=1;
    #pragma GCC unroll 65534   //needs gcc 8
    for (int i=0; i<1000000; i++) 
       dummy=dummy*i;
    return dummy; 
}

compile with: gcc-8 -O3 the unroll factor controls program length The files are pretty small:


-rwxr-xr-x  1 jan jan     450544 Feb 26 09:24  unrolled10000.elf*
-rwxr-xr-x  1 jan jan      53232 Feb 26 09:21  unrolled1000.elf*
-rwxr-xr-x  1 jan jan      12272 Feb 26 09:21  unrolled100.elf*
-rwxr-xr-x  1 jan jan       8176 Feb 26 09:21  unrolled10.elf*
-rwxr-xr-x  1 jan jan    5242864 Feb 26 10:22  unrolled65534.elf*

The largest one is comparable with the BN executable:

-rwxr-xr-x 1 jan jan 6202240 Feb 26 08:56 binaryninja*

On the test machine, unrolled1000.elf is already quite choppy in scrolling in the linear view. 10000 is unusable. On my fastest machine, 10000 is still sort of usable. if I load up the binaryninja executable, scrolling is wicked fast. Branches can't really be the problem, as the above program has basically a single one. Similar for xrefs Furthermore, going back to bncov testing, I ran coverage files on all these executables and did the same test we did previously. I ran this empty python loop:


     start = time.time()
     lines = bv.get_linear_disassembly(None)   
     for index, line in enumerate(lines):  
          if index == 5000: # this loop can take very long, so we limit it here.
             break
     end = time.time()
     binaryninja.log_info(repr(end-start))
     binaryninja.log_info(repr(index))

with each executable, both before and after loading the coverage data (which marks basically the whole program)

unrolled_loop_length      run_time_to_index_5000_without_bncov                run_time_to_index_5000_with_bncov     
10                        0.131317138671875                                   0.09713292121887207
100                       0.2829768657684326                                  0.31766295433044434
1000                      2.3917880058288574                                  2.317965030670166
10000                    29.417006969451904                                  29.606093168258667
65534                   119.57588505744934                                  117.70040512084961


                          run_time_to_index_5000_without_bncov  
binary ninja executable   0.9594550132751465

Peter did a lot of work on this already and suspects that the linear view renderer has trouble when the basic block is very large.

The source, binaries and drcov files are attached.

files.zip

Vector35 / binaryninja-api

Linear view and bv.get_linear_disassembly() are very slow in certain circumstances #1540