One of my current projects at Hacker School is to (attempt) to solve the knapsack problem using 64-bit assembly. I've never done anything in assembly before — before I started this project, I didn't even know what a register was. It's been an educational, if frustrating project. Today's frustrations have revolved around macho64 and debugging.

As detailed in my first assembly blog post, I assemble my knapsack.asm file on OSX with this shell script:

# Generate object file from assembly:
nasm -f macho64 -o knapsack.o knapsack.asm

# Link object file:
ld knapsack.o -o knapsack

This creates a binary file knapsack, which I can easily run from the command line with ./knapsack. This works perfectly fine on OS X, no problem.

I started running into trouble, however, when I tried to use gdb, a debugging tool. It's great for stepping through assembly code one instruction at a time, looking at the registers, and seeing where the code is screwing up. Installing gdb wasn't too difficult, a simple brew install command...

brew install

...followed by some simple certificate setup, and I was good to go. It worked fine, at first.

sudo gdb -tui ./knapsack # gdb seems to need sudo on OS X
(gdb) run

I could see my program execute, and all the values of the registers. Setting breakpoints with break <function name> worked fine as well. However, step had problems.

(gdb) break open_file
Breakpoint 1 at 0x1f8f
(gdb) run
Starting program: /Users/robert/Desktop/knapsack-asm/knapsack 

Breakpoint 1, 0x0000000000001f8f in open_file ()
(gdb) step
Single stepping until exit from function open_file,
which has no line number information.
0x0000000000001fd2 in open_file_success ()

I couldn't get gdb to single step through individual lines of assembly code, only entire function calls. I looked on the internet for information about adding debug information to nasm. It looked like you could tell nasm to enable debug information with -g -F <debug format>, and list available debug formats with -y. I checked out the list of formats for macho64.

nasm -f macho64 -y

valid debug formats for 'macho64' output format are ('*' denotes default):
  * null      Null debug format

Damn. A nasm forum post from 2011 confirmed it — nasm does not support the macho debug format yet.

I definitely wasn't going to try the knapsack problem without a working assembly debugger, so I searched for a solution. nasm has an alternative called yasm, but yasm doesn't have any macho64-compatible debug formats either. Some suggestions online involved some sort of hack to convert elf64 into macho64, and it didn't even sound like that worked. I eventually decided that macho64 just wasn't going to cut it.

elf64 runs on Linux, and nasm can output debug information for elf64, so I decided to spin up a quick Linux machine with Vagrant.

vagrant init hashicorp/precise64

Note the precise64...we're running 64-bit assembly, so we need 64-bit Ubuntu, not the 32-bit that Vagrant docs have you set up normally by default.

I also added the following shell provision to the auto generated Vagrantfile, to install nasm and gdb by default on the VM.

config.vm.provision "shell",
  inline: "apt-get update --yes; apt-get install nasm gdb --yes"

Now, spinning up and sshing into a VM is a simple command away.

vagrant up
vagrant ssh

Once I'm sshed into the VM, I can easily compile my .asm file with debug information and run gdb on it.

cd /vagrant/
nasm -f elf64 -o knapsack.o -g -F dwarf knapsack.asm
ld knapsack.o -o knapsack
gdb -tui ./knapsack

Inside gdb, I can set up a breakpoint and step forward from it...

(gdb) break open_file 
Breakpoint 1 at 0x400147: file knapsack.asm, line 76.
(gdb) run
Starting program: /vagrant/knapsack 

Breakpoint 1, open_file () at knapsack.asm:76
(gdb) step

Success! The program steps forward a line. I can also actually see the assembly source code in the top half of the gdb screen. I've definitely never been this excited about a debugger before.

I definitely don't know what I'm doing with this project, and I've had strong feelings of "wow I am seriously just bumbling around here," but I think that's a healthy thing to feel at Hacker School. On the first day, the facilitators told us to "seek out what we're scared of." I'd say I've definitely lived up to that today.

← More Posts