четверг, 9 ноября 2023 г.

kssp library, part 2

Previous part 

I was struck by the idea of how to reduce size of graph before enumerating all K-th shortest paths. We can use cut-points. By definition if we have cut-point in some shortest path it must be visited always - otherwise you can`t reach the destination. So algo is simple
  1. find with Dijkstra algo first shortest paths for whole graph
  2. find all cut-points in whole graph
  3. iterate over found shortest path - if current vertex is cut-point - we can run brute-force from previous cut-point till current

Results are crazy anyway - on the same test 7

  • Yen: 13.86s, 29787, 3501 cycles
  • Node Classification: 118.4s, 30013, 3501 cycles
  • Postponed Node Classification: 104.95s, 30013, 3501 cycles
  • PNC*: 120.33s, 30013, 3501 cycles
  • Parsimonious Sidetrack Based: 4.66s, 29980, 3501 cycles
  • Parsimonious Sidetrack Based v2: 4.79s, 29980, 3501 cycles
  • Parsimonious Sidetrack Based v3: 4.85s, 29980, 3501 cycles
  • Sidetrack Based: 4.18s, 29980, 3501 cycles
  • Sidetrack Based with update: 4.34s, 29980, 3501 cycles
At this time all algos worked to completion and again gave different results...
Source code

вторник, 7 ноября 2023 г.

kssp library

I`ve tried to solve CSES task "visiting cities"

Looks like you can use kind of brute-force - get 1st shortest paths, then all remained with the same cost and make union of cities in each path - nor elegant nor smart algorithm, just to estimate if this approach works at all

I remember from my university course "graph theory" about Yen`s algo to get K-th shortest path so choosed to use some ready (and hopefully well-tested) implementation - kssp library from INRIA (yep - famous place where OCaml was invented)

And then happened real madness - different algos gave me different result and moreover - they didn't match with "correct" results from CSES! Lets see what I got (all results for test 7, compilation options -O3 -DTIME -DNDEBUG):

  • Yen - 470s, 30157 cities
  • node classification - 4.37s, 30140 cities
  • postponed node classification - 3.83s, 30140 cities
  • postponed node classification with star - 3.76s, 30140 cities
  • sidetrack based - consumed 13Gb of memory and met with OOM killer
  • parsimonious sidetrack based - OOM again, perhaps bcs not enough parsimonious :-)

Source code

понедельник, 11 сентября 2023 г.

location lists from dwarf5

I added during past weekend support for var location lists from DWARF5 (located in separate section .debug_loclists) in my dwarfdump. As usually lots of bugs were found

First - they presents only for functions but not for methods. Probably this is real bug and can have serious impact when debugging

Second - generated expressions is not optimal. Lets see example:

locx 53e
4FB5DF - 4FB5F4: DW_OP_piece 0x8, DW_OP_reg0 RAX, DW_OP_piece 0x8, DW_OP_breg0 RAX+0, DW_OP_lit3, DW_OP_lit8, DW_OP_mul, DW_OP_plus, DW_OP_stack_value, DW_OP_piece 0x8
4FB5F4 - 4FB60F: DW_OP_piece 0x8, DW_OP_reg2 RCX, DW_OP_piece 0x8, DW_OP_breg0 RAX+0, DW_OP_lit3, DW_OP_lit8, DW_OP_mul, DW_OP_plus, DW_OP_stack_value, DW_OP_piece 0x8

As you can see this expressions are the same but for adjacent addresses ranges. Why not use single expression for range 4FB5DF - 4FB60F?
Update: I have made patch to estimate amount of identical adjacent location lists. C++ extractor from codeql has total 149850 lists and 116 redudant or 0.077%

DW_OP_mul just pops from stack couple of values and put back result of their multiplication (see evaluation logic in method execute_stack_op), so this sub-expression can be rewritten as just DW_OP_lit24

Also it`s curious to check what other compilers support subj:

gcc

Yes, with options -g -gdwarf-5 -fvar-tracking

golang

No - they even don`t support DWARF5 at all

openwatcom v2

No - judging by the funny comments

WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE DESCRIBE IT HERE!

пятница, 1 сентября 2023 г.

gcc plugin to collect cross-references, part 7

Part 1, 2, 3, 4, 5 & 6

Lets check if we can extract other kind of constants - numerical. Theoretically there are no problems - they have types INTEGER_CST, REAL_CST, COMPLEX_CST and so on. And you even can meet them - mostly in programs written in fortran
In most code they usually replaced with RTX equivalents like
  • INTEGER_CST - const_int (or const_wide_int)
  • REAL_CST - const_double

const_double is easy case but const_ints are really ubiquitous, they can appear in RTX even when they do not occur in operands of asssembler`s code. So main task is to select only small subset of them. Let`s consider what we can filter out

fields offsets

Luckily this hard part has already been solved in previous part

local variables offsets in stack

RTX has field frame_related:
1 in an INSN or a SET if this rtx is related to the call frame, either changing how we compute the frame address or saving and restoring registers in the prologue and epilogue

this flag affects both parts of set, for loading something from stack it looks something like:
set (reg:DI 0 ax [83])
        (mem/f/c:DI (plus:DI (reg/f:DI 6 bp)
                (const_int -8 [0xfffffffffffffff8]))

and for storing to stack like:
set (mem/f/c:DI (plus:DI (reg/f:DI 6 bp)
                (const_int -8 [0xfffffffffffffff8])) [4 this+0 S8 A64])
        (reg:DI 5 di [ _0 ]))

conditions

Yes, if_then_else almost always follows compare: 
(set (reg:CCZ 17 flags)
        (compare:CCZ (reg:QI 2 cx [orig:83 _2 ] [83])
            (const_int 0 [0]))) "vtest.cc":44:19 5 {*cmpqi_ccno_1}
(jump_insn 10 9 11 2 (set (pc)
        (if_then_else (eq (reg:CCZ 17 flags)
                (const_int 0 [0]))
            (label_ref 16)
            (pc))) "vtest.cc":44:19 891 {*jcc}
All these bulky constructions will be translated to just jz, so no const_int 0 will be placed in output

EH block index

like in each function call:

(expr_list:REG_EH_REGION (const_int 0 [0])

воскресенье, 27 августа 2023 г.

dwarf5 from clang 14

It seems that clang in version 14 utilize more advanced features from DWARF5, so I add their support to my dwarfdump. IMHO most exciting features are:

Section .debug_line_str

In old versions of dwarf filenames have duplicates for each compilation unit. Since dwarf version 5 they storing in separate section and thus shared and save some space. Obviously this space reducing is negligible compared to overhead from types duplication

Section .debug_str_offsets

Also for space reducing each compilation unit has so called base index for strings passed via DW_AT_str_offsets_base. But there is problem - some attributes already can have name before DW_AT_str_offsets_base occurs:


  <0><c>: Abbrev Number: 1 (DW_TAG_compile_unit)
    <d>   DW_AT_producer    : (indexed string: 0): clang version 14.0.6 (git@github.com:github/semmle-code 5c87e7737f331823ed8ed280883888566f08cdea)
    <e>   DW_AT_language    : 33        (C++14)
    <10>   DW_AT_name        : (indexed string: 0x1): c/extractor/src/extractor.cpp
    <11>   DW_AT_str_offsets_base: 0x8


As you can see here 2 tags have names before we have value of string base. Much harder to parse in one pass now

New locations format

I think this is the most cool and useful feature - now each variable and parameter has set of locations linked with address ranges (that`s often case for highly optimized code). Sample:

   Offset Entry 2077
    0024ef56 00000000000006b4 (index into .debug_addr) 004fb3c500000000 (base address)
    0024ef59 0000000000000000 000000000000001c DW_OP_reg5 (rdi)

This cryptic message means that starting from address 0x4fb3c5 (note - most tools like objdump or llvm-dwarfdump cannot correctly show this new locations, in this case objdump showed address in bad format) some local variable located in register rdi until next address range. Seems that both IDA Pro and Binary Ninja cannot use this debug information:
.text:00004FB3C5     mov     rdi, cs:compilation_tf
.text:00004FB3CC     cmp     dword ptr [rdi+0Ch], 0

Global var compilation_tf has type a_trap_file_ptr - pointer to a_trap_file. IDA Pro has that types information from debug info but anyway cannot show access to field of a_trap_file at offset 0xC for next instruction

 
As result of all my patches now I can for example inspect IL structures from Microsoft CodeQL C++ extractor:

суббота, 19 августа 2023 г.

gcc plugin to collect cross-references, part 6

Part 1, 2, 3, 4 & 5
Finally I was able to compile and collect cross-references for enough big open-source projects like linux kernel and botan:
wc -l botan.db
2108274 botan.db
grep Err: botan.db | wc -l
540

So lets check how we can extract access to record fields. If you take quick look at tree.def you can notice very prominent type COMPONENT_REF:
Value is structure or union component.
 Operand 0 is the structure or union (an expression).
 Operand 1 is the field (a node of type FIELD_DECL).
 Operand 2, if present, is the value of DECL_FIELD_OFFSET

 

Sounds easy? "In theory there is no difference between theory and practice". In practice you can encounter many other types in any combinations, like in this relative simple RTL:
(call_insn:TI 1482 1481 2856 35 (call (mem:QI (mem/f:DI (plus:DI (reg/f:DI 0 ax [orig:340 MEM[(struct Server_Hello_13 *)_325].D.264452.D.264115._vptr.Handshake_Message ] [340])
                    (const_int 24 [0x18])) [744 MEM[(int (*) () *)_199 + 24B]+0 S8 A64]) [0 *OBJ_TYPE_REF(_200;&MEM[(struct _Uninitialized *)&D.349029].D.305525._M_storage->3B) S1 A8])
        (const_int 0 [0])) "/usr/local/include/c++/12.2.1/bits/stl_construct.h":88:18 898 {*call}
     (expr_list:REG_CALL_ARG_LOCATION (expr_list:REG_DEP_TRUE (concat:DI (reg:DI 5 di)
                (reg/f:DI 41 r13 [386]))
            (nil))
        (expr_list:REG_DEAD (reg:DI 5 di)
            (expr_list:REG_DEAD (reg/f:DI 0 ax [orig:340 MEM[(struct Server_Hello_13 *)_325].D.264452.D.264115._vptr.Handshake_Message ] [340])
                (expr_list:REG_EH_REGION (const_int 0 [0])
                    (expr_list:REG_CALL_DECL (nil)
                        (nil))))))
    (expr_list:DI (use (reg:DI 5 di))
        (nil)))

So I`ll describe in brief some TREE types and how to deal with them to extract something useful

среда, 16 августа 2023 г.

gcc plugin to collect cross-references, part 5

Part 1, 2, 3 & 4

Lets check how RTL describes jump tables. I made simple test and output of gcc -fdump-final-insns looks like:

(jump_insn # 0 0 8 (parallel [
            (set (pc)
                (reg:DI 0 ax [93]))
            (use (label_ref #))
        ]) "swtest.c":14:3# {*tablejump_1}
     (nil)
 -> 8)
(barrier # 0 0)
(code_label # 0 0 8 (nil) [2 uses])
(jump_table_data # 0 0 (addr_vec:DI [
            (label_ref:DI #)
            (label_ref:DI #)
...
        ]))

As you can see jump_insn uses opcode tablejump_1 refering to label 8. Right after this label located RTL with code jump_table_data - perhaps this is bad idea to assume that it always will be true so it`s better to use function jump_table_for_label. Also for some unknown reason option -fdump-final-insns does not show content of jump tables. So at least lets try to find jump_table_datas from plugin

Surprisingly you cannot find then when iterating on instructions within each block (using FOR_ALL_BB_FN/FOR_BB_INSNS macros). I suspect this due to the fact that both label and jump_table belong to block with index 0. So I used another cycle: 
for ( insn = get_insns(); insn; insn = NEXT_INSN(insn) )
Then we can check if current RTL instruction is jump table with JUMP_TABLE_DATA_P. Jump tables have addr_vec in element with index 3 and each element is label_ref. Length of vector can be obtained from field num_elem. Pretty easy, so what we can do with this knowledge?