[SOLVED] Extract Stack Usage Information from binary/object files

Issue

I'm facing a problem with a program that is using too much stack space, and is crashing on certain execution path. I do not have the source code of the program (getting static compiled libraries) - I believe it's using dynamic allocation (VLA) and/or allocating large structures on the stack.

During compilation, it's possible to get "stack usage" (-fstack-usage) that show approximate utilization of stack by function. My question: Is is possible to use debugger information (or other information stored in the objects/executable) to extract the stack usage - identify the functions that uses most space.

Ideally, format should be similar to -fstack-usage - including minimum stack usage, maximum stack usage and indication if it's unbounded (when VLA are used). On surface, this should be possible to calculate (or estimate) by examining the local variables in the function - their offsets from the base pointer.

Solution

My question: Is is possible to use debugger information (or other information stored in the objects/executable) to extract the stack usage - identify the functions that uses most space.

Update:

Yes, it's possible to extract approximately the same info as you would get for -fstack-usage from an object file, and you don't need any debug info.

Using the example source below (on x86_64):

objdump -d t.o | egrep '>:|sub .*%rsp|add.*0xffff.*%rsp'
0000000000000000 <leaf>:
000000000000000b <f1>:
   f:   48 83 ec 08             sub    $0x8,%rsp
0000000000000026 <f2>:
  2a:   48 81 ec 00 04 00 00    sub    $0x400,%rsp
000000000000005a <f3>:
  5e:   48 83 c4 80             add    $0xffffffffffffff80,%rsp
000000000000007f <main>:
  83:   48 83 ec 10             sub    $0x10,%rsp

This tells you that leaf uses ~no stack, f2 uses at least 1024 bytes, and f3 uses at least 128 bytes.

You would need to adjust this for a different instruction set if you are not on x86_64, but a similar approach should work.

---

At runtime, getting this info is easy: all you have to do is get a stack trace with frame addresses.

The stack usage of a given function is then the delta between the frame of the current function, and and the function it called.

For example:

void leaf(char a[]) {}
void f1(char a[]) { leaf(a); }
void f2(char a[]) {
  char b[1000];
  b[0] = a[0];
  f1(b);
}
void f3(char a[]) {
  char b[100];
  b[0] = a[0];
  f2(b);
}
int main()
{
  char c[1];
  f3(c);
  return 0;
}

gcc -g f.c && gdb -q ./a.out
(gdb) b leaf
Breakpoint 1 at 0x1131: file f.c, line 1.
(gdb) run

Breakpoint 1, leaf (a=0x7fffffffd390 "") at f.c:1
1       void leaf(char a[]) {}
(gdb) bt
#0  leaf (a=0x7fffffffd390 "") at f.c:1
#1  0x000055555555514c in f1 (a=0x7fffffffd390 "") at f.c:2
#2  0x0000555555555180 in f2 (a=0x7fffffffd7a0 "") at f.c:6
#3  0x00005555555551a5 in f3 (a=0x7fffffffd82f "") at f.c:11
#4  0x00005555555551bc in main () at f.c:16
(gdb) p/x $rsp
$1 = 0x7fffffffd358
(gdb) up
#1  0x000055555555514c in f1 (a=0x7fffffffd390 "") at f.c:2
2       void f1(char a[]) { leaf(a); }
(gdb) p/x $rsp
$2 = 0x7fffffffd368
(gdb) up
#2  0x0000555555555180 in f2 (a=0x7fffffffd7a0 "") at f.c:6
6         f1(b);
(gdb) p/x $rsp
$3 = 0x7fffffffd380
(gdb) up
#3  0x00005555555551a5 in f3 (a=0x7fffffffd82f "") at f.c:11
11        f2(b);
(gdb) p/x $rsp
$4 = 0x7fffffffd790
(gdb) up
#4  0x00005555555551bc in main () at f.c:16
16        f3(c);
(gdb) p/x $rsp
$5 = 0x7fffffffd820
(gdb) up
Initial frame selected; you cannot go up.
(gdb) p $5 - $4
$6 = 144
(gdb) p $4 - $3
$7 = 1040
(gdb) p $3 - $2
$8 = 24
(gdb) p $2 - $1
$9 = 16

Without running the program, the problem is equivalent to the halting problem (i.e. undecidable) if you have any recursive functions or any VLA or alloca uses.

Answered By - Employed Russian

Answer Checked By - Mary Flores (WPSolving Volunteer)