How to code debuggers

Coding low-level infrastructure like kernels, compilers, and linkers can be very scary, and most programmers stay as far away from them as they can. And the scariest of all are debuggers, which rip apart warm flesh of innocent programs, and use the dark side of the force to control them. Every decent Computer Science course includes coding at least a toy compiler, most also toy interpretters, virtual machines, and disassemblers, but how many people wrote even the most toyish debugger ? (by debugger I mean any tool for low-level analysis of running programs, wheather it single steps, traces execution, or does something else)

Most debuggers are written in C, so touching their code is pretty much out of the question. It's hard enough without having to use 30 year old and about 32 time less productive tools.

Why would anybody want to write a debugger ? Many people work almost exclusively with high-level languages running on virtual machines, and they probably don't need to - high-level languages provide a lot of reflection and run-time program modification abilities that writing custom debugging tools won't be necessary. Many people are satisfied by available debuggers, or at least find them flexible enough to write custom debugging tools around them. strace plus perl one-liners certainly saved people years of debugging time.

And then there are people who have to do low-level coding, and find perl scripting around existing tools insufficient, but because debuggers seem so scary they simply learned to live with bad tools.

How debuggers work

Debuggers are based on a few simple techniques. I'll talk about Linux and other modern Unices here like Solaris and FreeBSD. On other systems the details differ, but principles are similar.

• System call ptrace lets processes control other processes.
• Binaries in ELF format include a lot of useful information.
• Calls to library functions get resolved only when the program runs. It's very easy to make them point to our functions instead.
• Compilers emit a lot of useful debugging information in DWARF format.
• /proc/ contains a lot of information about running programs.

That's about it. Sometimes these techniques are insufficient, for example when debugging kernel bugs. Then there are fancier tricks like kernel modules and running on a virtual machine, but it's very rarely needed.

ptrace

long ptrace(enum __ptrace_request request, pid_t pid, void *addr, void *data);

Most debugging tools are based on ptrace. ptrace is extremely useful but almost unknown syscall.

To start tracing some process simply include <sys/ptrace.h> in your C program, and attach with ptrace(PTRACE_ATTACH, process_pid, 0, 0).

Then you can read and write its registers:

void *get_instruction_pointer(pid_t pid)
{
  return (void *)ptrace(PTRACE_PEEKUSR, pid, 4 * EIP, 0);
}

void set_instruction_pointer(pid_t pid, void *addr)
{
  ptrace(PTRACE_POKEUSR, pid, 4 * EIP, (long)addr);
}

and data:

void *get_stack_pointer(pid_t pid)
{
  return (void *)ptrace(PTRACE_PEEKUSER, pid, 4 * UESP, 0);
}

void *get_return_addr(pid_t pid, void *stack_pointer)
{
  return (void *)ptrace(PTRACE_PEEKTEXT, pid, stack_pointer, 0);
}

For "historical reasons" PEEK means read, and POKE means write. Available requests are:

• PTRACE_PEEKDATA - read program data
• PTRACE_POKEDATA - write program data
• PTRACE_PEEKTEXT - read program code
• PTRACE_POKETEXT - write program code
• PTRACE_PEEKUSR - read process information (struct user)
• PTRACE_POKEUSR - write process information (struct user)
• PTRACE_GETREGS, PTRACE_GETFPREGS - read general/floating point registers
• PTRACE_SETREGS, PTRACE_SETFPREGS - write general/floating point registers
• PTRACE_SINGLESTEP - let program execute single instruction. There's hardware support for this.
• PTRACE_SYSCALL - trace program until the next syscall
• PTRACE_CONT - let program run until it gets a signal
• PTRACE_DETACH - detach from program
• and a few more.

Under Linux code and data are not separated, so PTRACE_PEEKDATA equals PTRACE_PEEKTEXT and PTRACE_POKEDATA equals PTRACE_POKETEXT. Registers can be read/written either through PEEKUSR/POKEUSR or through GETREGS/SETREGS, whichever is more convenient.

ptrace is very low level. Reads and writes only do one (probably aligned) machine word at time. It's not difficult to wrap these routines in some more convenient interface.

So you know how to manipulate programs. The only missing part is breakpoints. Breakpoints are actually pretty easy:

• Compute location of the break point
• Read byte that was there and save it.
• Put 0xCC byte there (int3 opcode). If program is ptraced, executing int3 will freeze it.

Disabling breakpoits is even easier - just write back the old instruction. Running breakpointed code is a little more tricky:

• Disable breakpoint (write back old instruction)
• Run single step (PTRACE_SINGLESTEP)
• Enable breakpoint (write int3)
• Continue (PTRACE_CONT)

As we can only read and write full words at time, what actually happens is that we read 4 bytes, modify one of them, and write back 4 bytes (one with breakpoint, and 3 around it).

ptrace in action

There are many ptrace-based tools, like strace for tracing syscalls, ltrace for tracing shared library calls, and gdb uses ptrace too.

ptraceing process can be ptraced, so let's see what happens inside a tracing process. strace -o metastrace strace true traces strace as it traces true and saves the trace to metastrace file.

Here's a fragment:

ptrace(PTRACE_SYSCALL, 7973, 0x1, SIG_0) = 0
wait4(-1, [{WIFSTOPPED(s) && WSTOPSIG(s) == SIGTRAP}], __WALL, NULL) = 7973
--- SIGCHLD (Child exited) @ 0 (0) ---
ptrace(PTRACE_PEEKUSER, 7973, 4*ORIG_EAX, [0x5]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EAX, [0xffffffda]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EBX, [0xb7f2ab3c]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*ECX, [0]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EDX, [0]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab3c, [0x62696c2f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab40, [0x736c742f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab44, [0x3836692f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab48, [0x6d632f36]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab4c, [0x6c2f766f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab50, [0x2e636269]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab54, [0x362e6f73]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab58, [0x62696c00]) = 0
write(2, "open(\"/lib/tls/i686/cmov/libc.so"..., 45) = 45
ptrace(PTRACE_SYSCALL, 7973, 0x1, SIG_0) = 0
wait4(-1, [{WIFSTOPPED(s) && WSTOPSIG(s) == SIGTRAP}], __WALL, NULL) = 7973
--- SIGCHLD (Child exited) @ 0 (0) ---
ptrace(PTRACE_PEEKUSER, 7973, 4*ORIG_EAX, [0x5]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EAX, [0x3]) = 0
write(2, ") = 3\n", 6)                  = 6
ptrace(PTRACE_SYSCALL, 7973, 0x1, SIG_0) = 0
wait4(-1, [{WIFSTOPPED(s) && WSTOPSIG(s) == SIGTRAP}], __WALL, NULL) = 7973

In highlighted regions:

• Parent requests ptrace to wait for system calls of its child and waits for something to happen.
• Something happens - child tries to run some system call, and gets virtual signal SIGTRAP. Parent gets SIGCHLD (incorrectly described at "Child exited")
• Parent reads syscall number (5 = open), and arguments - 0xb7f2ab3c is pointer to the path, 0 is O_RDONLY, and the next 0 is mode.
• Parent reads string located at 0xb7f2ab3c (the path), until it finds a 0.
• Parent reports that system call happened.
• Parent waits for system call to return by PTRACE_SYSCALL and wait4.
• Parent reads return value from syscall - 3
• Parent reports that return value of the system call.
• Parent tells ptrace to keep tracking child's system calls and lets the child continue.

That wasn't bad, was it ?

ELF format

Binaries on most modern Unices use ELF format (106-page specification). A lot more can be done with ELF binaries than just executing them. For one we can check which shared library the program uses.

$ ldd /usr/bin/ruby
      linux-gate.so.1 =>  (0xffffe000)
      libruby1.8.so.1.8 => /usr/lib/libruby1.8.so.1.8 (0xb7e3e000)
      libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0 (0xb7e27000)
      libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0xb7e23000)
      libcrypt.so.1 => /lib/tls/i686/cmov/libcrypt.so.1 (0xb7df5000)
      libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0xb7dce000)
      libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0xb7c8d000)
      /lib/ld-linux.so.2 (0xb7f29000)

/lib/ld-linux.so is dynamic loader, which looks for other libraries in the path. linux-gate is a pseudolibrary used for communication with kernel. libdl.so is a dynamic library loader and lets the program load more libraries at runtime. More about that later - what's interesting is that all this information is contained in the ELF binary in easily accessible format.

Two programs most useful for getting information from binaries are objdump and readelf. To get default a basic overview simply run readelf -W --all binary or objdump --all-headers binary.

Here's a fragrent of readelf -W --all /usr/bin/perl's output, listing functions which Perl interpretter gets from shared libraries.

Relocation section '.rel.plt' at offset 0x1688c contains 231 entries:
Offset     Info    Type            Sym.Value  Sym. Name
08142114  00001d07 R_386_JUMP_SLOT   00000000   readlink
08142118  00003907 R_386_JUMP_SLOT   00000000   nl_langinfo
0814211c  00003a07 R_386_JUMP_SLOT   00000000   mkdir
08142120  00004507 R_386_JUMP_SLOT   00000000   pthread_getspecific
08142124  00004807 R_386_JUMP_SLOT   00000000   cos
08142128  00005807 R_386_JUMP_SLOT   00000000   fgetc
0814212c  00006007 R_386_JUMP_SLOT   00000000   chown
08142130  00006907 R_386_JUMP_SLOT   00000000   getgrnam_r
08142134  00006e07 R_386_JUMP_SLOT   00000000   __strtod_internal
08142138  00007107 R_386_JUMP_SLOT   00000000   setservent
0814213c  00007a07 R_386_JUMP_SLOT   00000000   rename
08142140  00008b07 R_386_JUMP_SLOT   00000000   ferror
08142144  00009207 R_386_JUMP_SLOT   00000000   sigaction
08142148  00009b07 R_386_JUMP_SLOT   00000000   getgrent_r
0814214c  00009d07 R_386_JUMP_SLOT   00000000   execl
08142150  0000a207 R_386_JUMP_SLOT   00000000   vsprintf
08142154  0000a307 R_386_JUMP_SLOT   00000000   strchr
08142158  0000b607 R_386_JUMP_SLOT   00000000   fdopen

Here's a partial list of functions provided by libjpeg, found by readelf -all /usr/lib/libjpeg.so:

Symbol table '.dynsym' contains 141 entries:
 Num:    Value  Size Type    Bind   Vis      Ndx Name
  12: 00008581   664 FUNC    GLOBAL DEFAULT   10 jpeg_gen_optimal_table
  13: 00002e6b   652 FUNC    GLOBAL DEFAULT   10 jpeg_copy_critical_parame
  14: 00005ba0   537 FUNC    GLOBAL DEFAULT   10 jinit_c_prep_controller
  16: 0000d1be   115 FUNC    GLOBAL DEFAULT   10 jinit_input_controller
  17: 0000c150   159 FUNC    GLOBAL DEFAULT   10 jpeg_read_scanlines
  18: 0001b414    35 FUNC    GLOBAL DEFAULT   10 jpeg_get_small
  19: 000146b4  1343 FUNC    GLOBAL DEFAULT   10 jpeg_idct_float
  20: 000032c1   969 FUNC    GLOBAL DEFAULT   10 jpeg_set_colorspace
  21: 00003280    65 FUNC    GLOBAL DEFAULT   10 jpeg_quality_scaling
  22: 000037fd   760 FUNC    GLOBAL DEFAULT   10 jpeg_simple_progression
  23: 0000b280   655 FUNC    GLOBAL DEFAULT   10 jpeg_fdct_ifast
  24: 00010487  1045 FUNC    GLOBAL DEFAULT   10 jpeg_make_d_derived_tbl
  25: 000160e3    59 FUNC    GLOBAL DEFAULT   10 jpeg_idct_1x1
  26: 0000fd59   309 FUNC    GLOBAL DEFAULT   10 jpeg_huff_decode
  27: 00014bf4  2667 FUNC    GLOBAL DEFAULT   10 jpeg_idct_islow
  28: 0000cd9e   919 FUNC    GLOBAL DEFAULT   10 jinit_master_decompress
  29: 0000cab6   744 FUNC    GLOBAL DEFAULT   10 jpeg_calc_output_dimensio
  30: 00003cbe   108 FUNC    GLOBAL DEFAULT   10 jpeg_set_linear_quality

Using it on C++ libraries is more difficult, as C++ "mangles" identifiers. Because in C++ multiple functions with the same name are allowed, as long as they use arguments of different types, the compiler "mangles" identifiers to include type information, and it ends up like this: _ZN13nsCOMPtr_base18assign_with_AddRefEP11nsISupports. readelf doesn't seem to provide any demangling, but objdump -C -R /usr/bin/firefox will tell us that the needed function is nsCOMPtr_base::assign_with_AddRef(nsISupports*).

objdump also includes a disassembler, so you can find implementation of geteuid by looking at output of objdump -d /lib/libc.so.6:

0008c750 <geteuid>:
 8c750:       55                      push   %ebp
 8c751:       89 e5                   mov    %esp,%ebp
 8c753:       b8 c9 00 00 00          mov    $0xc9,%eax
 8c758:       cd 80                   int    $0x80
 8c75a:       5d                      pop    %ebp
 8c75b:       c3                      ret

For those that want to know - int 0x80 enters the kernel, and %eax contains syscall number (0xc9 is obviously one for geteuid). At least that's how it used to work. The "real" libc in /lib/tls/i686/cmov/libc.so.6 uses call *%gs:0x10 instead of int $0x80. (that's related to linux-gate.so.1 pseudolibrary)

Shared libraries

Let's get back to ldd:

$ ldd /usr/bin/ruby
      linux-gate.so.1 =>  (0xffffe000)
      libruby1.8.so.1.8 => /usr/lib/libruby1.8.so.1.8 (0xb7e3e000)
      libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0 (0xb7e27000)
      libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0xb7e23000)
      libcrypt.so.1 => /lib/tls/i686/cmov/libcrypt.so.1 (0xb7df5000)
      libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0xb7dce000)
      libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0xb7c8d000)
      /lib/ld-linux.so.2 (0xb7f29000)

Only the dynamic linker is specified by full path. Everything else is resolved at runtime. Like binaries are looked for in PATH, libraries are searched in directories in LD_LIBRARY_PATH. So we can trivially make program use our libraries by changing LD_LIBRARY_PATH (like most techniques presented here, it doesn't work with setuid programs, so don't bother).

Even more effective is LD_PRELOAD, which simply lets us preload another library before the program runs. It can be any shared library, but usually we want to

Let's fool /bin/date into thinking it's noon (UTC) of July 21, 1995.

The library to do so it truly trivial:

#include <time.h>

int clock_gettime(clockid_t clk_id, struct timespec *tp)
{
  tp->tv_sec  = 806328000;
  tp->tv_nsec = 0;
  return 0;
}

We need to tell compiler we're compiling shared library, not a standalone binary by -fPIC -shared flags:

gcc -Wall -W -g -fPIC -shared magic_clock.c -o magic_clock.so

And:

$ date
Thu Mar 22 08:12:36 CET 2007
$ LD_PRELOAD=./magic_clock.so date
Fri Jul 21 14:00:00 CEST 1995

It even remembered to change to summer time.

Usually we want to have the original functionality available. I think it's enough hello worlds for this post, so let's do something useful, like getting statistics for hash lookups in Ruby.

Hash lookups in Ruby go through st_lookup function. We're interested in distribution of sizes of hash tables used. This kind of data is useful for profiling - maybe it will provide hints wheather replacing Ruby hashes by Judy is worthwhile. Or maybe we just want to know. Anyway, here's the debugging tool:

#define _GNU_SOURCE 1
#include <stdio.h>
#include <dlfcn.h>

/* Copied from ruby's st.h - it's the easiest way */
typedef unsigned long st_data_t;
struct st_table {
  struct st_hash_type *type;
  int num_bins;
  int num_entries;
  struct st_table_entry **bins;
};

int statistics[128];

int (*real_st_lookup) (struct st_table *, st_data_t, st_data_t *);

int st_lookup(struct st_table *table, st_data_t key, st_data_t *value)
{
  int size = table->num_entries;
  if(size > 15)
      size = 15 + (size / 16);
  if(size > 127)
      size = 127;
  statistics[size]++;

  return real_st_lookup(table, key, value);
}

void st_lookup_stats_init() __attribute__ ((constructor));
void st_lookup_stats_init()
{
  int i;
  for(i=0; i<128; i++)
      statistics[i] = 0;

  real_st_lookup = dlsym(RTLD_NEXT, "st_lookup");
}

void st_lookup_stats_fini() __attribute__ ((destructor));
void st_lookup_stats_fini()
{
  int i, total=0;

  for(i=0; i<128; i++)
      total += statistics[i];

  printf("Hash lookup statistics by hash size:\n");
  for(i=0; i<16; i++)
      printf("%d-element hashes: %d (%.1f%%)\n", i, statistics[i], 100.0 * statistics[i] / total);
  for(i=16; i<127; i++)
      printf("%d..%d-element hashes: %d (%.1f%%)\n", (i-15)*16, (i-15)*16+15, statistics[i], 100.0 * statistics[i] / total);
  printf("1792+-element hashes: %d (%.1f%%)\n", statistics[127], 100.0 * statistics[127] / total);
}

Compile it with:

gcc -Wall -W -g -fPIC -shared -ldl -lruby1.8 st_lookup_stats.c -o st_lookup_stats.so

and run with:

$ LD_PRELOAD=./st_lookup_stats.so ruby -e 'p 42'
42
Hash lookup statistics by hash size:
0-element hashes: 164 (2.2%)
1-element hashes: 1059 (14.3%)
2-element hashes: 20 (0.3%)
3-element hashes: 18 (0.2%)
4-element hashes: 17 (0.2%)
5-element hashes: 13 (0.2%)
6-element hashes: 17 (0.2%)
7-element hashes: 12 (0.2%)
8-element hashes: 19 (0.3%)
9-element hashes: 192 (2.6%)
10-element hashes: 10 (0.1%)
11-element hashes: 14 (0.2%)
12-element hashes: 10 (0.1%)
13-element hashes: 12 (0.2%)
14-element hashes: 12 (0.2%)
15-element hashes: 12 (0.2%)
16..31-element hashes: 185 (2.5%)
32..47-element hashes: 158 (2.1%)
48..63-element hashes: 171 (2.3%)
64..79-element hashes: 171 (2.3%)
80..95-element hashes: 126 (1.7%)
96..111-element hashes: 171 (2.3%)
112..127-element hashes: 92 (1.2%)
128..143-element hashes: 48 (0.7%)
144..159-element hashes: 103 (1.4%)
160..175-element hashes: 49 (0.7%)
176..191-element hashes: 95 (1.3%)
192..207-element hashes: 60 (0.8%)
[...]
1760..1775-element hashes: 0 (0.0%)
1776..1791-element hashes: 0 (0.0%)
1792+-element hashes: 0 (0.0%)

OK, now the explanations. int statistics[128]; keeps our statistics and st_lookup_stats_fini() function prints them out.

In ELF it's possible to mark some functions as constructors and destructors.

void st_lookup_stats_init() __attribute__ ((constructor)); tells gcc to mark st_lookup_stats_init as constructor, so it runs when the library gets loaded.

void st_lookup_stats_fini() __attribute__ ((destructor)); tells gcc to mark st_lookup_stats_fini as destructor, so it runs when the program exits.

void st_lookup_stats_init() zeroes statistics and find out location of the real st_lookup: real_st_lookup = dlsym(RTLD_NEXT, "st_lookup");

Our fake st_lookup records hash size and calls the genuine st_lookup.

st_data_t and struct st_table are copied from Ruby sources because i was too lazy to do it the "right way", and it doesn't matter anyway.

Debug information

gdb can control program by ptrace, but it still needs to know about its internals somehow. When gcc is run with -g flag, it saves debug information in DWARF format (117-page specification of DWARF-2).

Unfortunately most programs are distributed without this information, so we need to recompile with -g to get it. For all ELF files (programs, shared libraries, .o object files etc.) that contain debugging information, we can get it with readelf -W -w binary. Some of the useful data not available in other ways are types of function arguments, structure members and their offsets, and file/line information for everything.

Unfortunately parsing either binary DWARF or output of readelf is rather complicated. I haven't tried it out yet, but there seems to be a program for converting DWARF-2 information to XML. The XML it produces seems rather low-level, but it's XML, so it won't be hard to get useful information out of it.

/proc

/proc filesystem contains a lot of information about running processes. Most of this information can be extracted by ptrace, but /proc interface is far more convenient.

Some files useful for debugging:

• /proc/<pid>/cmdline - process command line arguments
• /proc/<pid>/cwd - symlink to current working directory of the process
• /proc/<pid>/environ - process environment
• /proc/<pid>/exe - symlink to executable
• /proc/<pid>/fd/* - open file descriptors
• /proc/<pid>/maps - map of process memory
• /proc/<pid>/mem - entire process memory

That's pretty much all you need to know to start. Happy debugger coding.