David Park

How it works so far

· elfq, part 2 · elf, tooling

retained answers the first question from the last post: how many bytes would go away with a function. Here it is on one of elfq’s test samples, a small Cortex-M4 firmware image:

$ elfq app.elf retained process_frame
Removing process_frame would save 1684 bytes:

RETAINED   OWN  ITEM
    1684   376  process_frame
    1076    52  ├─ crc32
    1024  1024  │  └─ crc_table
     172    92  ├─ apply_filter
      80    48  │  └─ filter_tap
      32    32  │     └─ fir_coeffs
      36    36  ├─ decode_header
      12   ~12  ├─ .rodata@0x8000900
      12   ~12  └─ .rodata@0x800090c

Shared with other code, so not counted: dispatch_event, frames_bad, frames_ok, log_msg, memcpy, stats.

OWN is each item’s own size, and RETAINED adds everything under it. The two .rodata items are error strings with no symbol, so their sizes are estimates (~).

It gets there in four steps:

  • Every function and data object is an item, with an address and a size. Most come from the symbol table. Stripped firmware has no symbol table, so elfq follows the code from the entry point and the vector table to find where functions start, and names them by address. In a stripped copy of this firmware, process_frame is fn_0x80002c8, and it keeps the same 1684 bytes.
  • Then elfq finds what each item uses: calls, jumps into other functions and loads of an address, like bl, b.w, adr and literal-pool ldr on Thumb. In firmware, it also reads data word by word, and a word that holds an item’s address counts as a pointer to it.
  • The roots are where the program starts running: the entry point, .init_array, and on Cortex-M the vector table. Without the vector table, interrupt handlers would look like dead code.
  • Last, it builds a dominator tree: an item belongs to process_frame if every path from a root to it goes through process_frame. Only crc32 reads crc_table, and only process_frame calls crc32, so both count. log_msg is called from other places too, so it doesn’t.

A function reached only through a pointer belongs to whatever takes its address. The linker’s --gc-sections uses the same rule, so the number matches what removing the code would save. elfq can’t tell where a call through a pointer goes, so it says when an answer might be missing something.

why answers the second question, what keeps an item in the file. It shows the shortest chain from where the program starts:

$ elfq app.elf why crc_table
crc_table is used by crc32, through this chain:

HOW          ITEM
entry point  Reset_Handler
call         └─ main
call            └─ process_frame
call               └─ crc32
uses                  └─ crc_table

Removing crc32 would remove crc_table too.

callees also takes a range of memory in place of a function, and lists what the code in that range uses outside it. On a Cortex-M7 sample with some code in ITCM, 0x0+256K is the whole ITCM:

$ elfq m7.elf callees 0x0+256K
0x00000000..0x00040000 (.itcm) uses 5 items outside it:

CALLEE         ADDRESS     SIZE  CALLER           HOW                   AT
crc_table      0x20000000  1024  crc32            uses                  0x18
memcpy         0x3000087c   308  apply_filter     call via veneer       0xbc
app_tick       0x300002e4    60  SysTick_Handler  tail call via veneer  0x8
fir_coeffs     0x30000eb4    32  filter_tap       uses                  0x56
systick_count  0x20000444     4  SysTick_Handler  uses                  0x0

The 0x3000... addresses are in flash. elfq exits with 1 when anything leaves the range, so a CI job can fail when code in ITCM starts calling into flash.

Short version: elfq builds the call graph from the machine code, so it works on stripped files too.