How to Debug Pascal Linked Lists with GDB & Conditional Breakpoints

In the previous article of this series, we saw how GDB can be used to debug FORTRAN programs. This time, we’ll use it to solve problems in another classic programming language: Pascal.

Pascal was designed in 1970, mostly to help teach students structured programming. Although the language’s popularity has declined there are still a few major programs written in it, such as Altium Designer and FL Studio.

We’re going to use GDB to debug a Pascal implementation of the linked list data structure.

The code

A linked list is an ordered data structure consisting of linked elements, each of which contains data and a pointer to the next item in the list. In a doubly linked list, elements also contain pointers to the previous element. The linked list is very flexible, able to easily grow and shrink with the data stored. Our example program consists of a small linked list library, plus a main function to exercise it with some simple operations.

Note that Pascal code looks rather different to the C-style languages most programmers are used to. In Pascal := is used for assignment, <> checks for inequality, ^ derefences pointers and braces are used to delimit comments. Look out for these when reading the code below:

program HelloWorld;

type
  tList =  record
              data : integer;
              next : ^tList;
              prev : ^tList;
           end;

var
   head, last, cur : ^tList;

procedure add(i : integer);
begin
   new(cur);
   cur^.data := i;
   cur^.next := nil;
   if head = nil then
      head := cur
   else
      begin
         last^.next := cur;
         cur^.prev := last;
      end;
   last := cur;
end;

function pop : integer;
var
   data : integer;
begin
   data := last^.data;
   last := last^.prev;
   dispose(last^.next);
   pop := data;
end;

procedure view;
begin
   cur := head;
   while cur <> nil do  {cur is nil at the end of the list}
      begin
         writeln(cur^.data);  {print the value}
         cur := cur^.next;  {set the new cur pointer}
      end;
end;

procedure destroy;
begin
   cur := head;
   while cur <> nil do
      begin
         cur := cur^.next;
         dispose(head);
         head := cur;
      end;
end;

begin
   head := nil;
   add(1);
   add(2);
   add(3);
   add(4);
   write('popped ');
   writeln(pop());
   view;
   destroy;
end.

There are many implementations of Pascal, including Turbo Pascal and Delphi; we will be using Free Pascal. This open source compiler is compatible with Delphi and Turbo Pascal and is supported on all of the popular operating systems and processor architectures.

After compiling and running this code, we would expect to see the following output:

$> ./list
popped 4
1
2
3

Unfortunately we get this instead:

$> ./list
popped 4
1
2
3
24760
Runtime error 204 at $0000000000417442
    $0000000000417442
    $00000000004004B3
    $00000000004001E0

Debugging in GDB

To try and work out what is happening we will use GDB. We’ll need to build our executable with additional debug information, which requires an extra compilation flag:

$> fpc -g list.pas

Lets start this new binary under GDB:

 gdb ./list
 [ ... GDB startup messages ... ]
 
 (gdb) break main
 Breakpoint 1 at 0x400411: file list.pas, line 60.
 (gdb) run
 Starting program: /home/blog_posts/pascal/list 
 
 Breakpoint 1, main () at list.pas:60
 60	   head := nil;

Using tbreak and display

The original output looked OK until we tried to print out the list, in which we saw a bogus output value appear before the Runtime error. Since that bogus value is our first point of interest, we’d like to skip forwards to examine the view function’s execution. We can do this by adding a breakpoint to that function.

The tbreak command is particularly useful for this kind of code navigation; it sets a temporary breakpoint, which will be deleted after it is hit:

 (gdb) tbreak VIEW
 Temporary breakpoint 2 at 0x40031c: file list.pas, line 40.
 (gdb) cont
 Continuing.
 popped 4
 
 Temporary breakpoint 2, VIEW () at list.pas:40
 40          cur := head;
 (gdb) next
 41          while cur <> nil do  {cur is nil at the end of the list}
 (gdb) next
 43                writeln(cur^.data);  {print the value}

(Note that we needed to capitalise the name to VIEW. Pascal is case insensitive and generates the debug info using uppercase letters.)

We’ve reached view and stepped forward so that the program is stopped at the head of the loop. We’ll breakpoint here (with no arguments, break uses the current code position) and then use the display command to make GDB print out interesting values each time we return to the prompt. We can now repeatedly use cont to move forward by single iterations of the loop:

 (gdb) break
 Breakpoint 3 at 0x400334: file list.pas, line 43.
 (gdb) display cur^.data
 1: cur^.data = 1
 (gdb) cont
 Continuing.

 [ ... some cont + inspection steps omitted for brevity,
       until we reach an interesting value               ... ]
 
 Breakpoint 3, VIEW () at list.pas:43
 43                writeln(cur^.data);  {print the value}
 1: cur^.data = 12472
 (gdb) next
 12472
 44                cur := cur^.next;    {set the new cur pointer}
 1: cur^.data = 12472
 (gdb)

As we execute, the displayed value of cur^.data changes and eventually takes on a bogus value of 12472. It looks like view might be iterating into invalid memory. Further investigation (which we’ll skip for this article) would reveal a similar iteration problem in destroy, which additionally produces the Runtime error we originally saw.

From this behaviour, we’d suspect that there’s a phantom element at the end of the list, containing a data value we never inserted. The next pointer for the last valid item leads to this phantom, instead of terminating the list with a nil.

In this program, such corruption could only happen when removing items from the list and we can therefore deduce that the error lies in our pop function. Reviewing that function’s code gives us our answer: the final next pointer is never reset to indicate a new end-of-list. We can fix our bug by setting last^.next to nil before returning:

 function pop : integer;
 var
    data : integer;
 begin
    data := last^.data;  {store the value so we can return it}
    last := last^.prev;  {set the last pointer to be the previous item}
    dispose(last^.next); {deallocate the memory for the item}
    last^.next := nil;   {FIX: set next pointer for last item to nil}
    pop := data;         {return the item data}
 end;

Trying out this fix out is left as an exercise for the reader. Before we wrap up, we’ll see an alternative approach to exploring this bug – one that lets GDB do more of our work for us!

Using conditional breakpoints

We’ve managed to deduce the real problem but we had to do quite a lot of interaction through the debugger prompt; with a long list this approach could be very time-consuming. A cleaner approach is to use a conditional breakpoint. This allows us to set a breakpoint with an associated if statement that determines when it should actually stop the program. If we set the condition carefully then we can stop on bad behaviour, rather than manually inspecting for bad values.

We often know, within a program, that certain data items will be within known bounds. This knowledge is ideal for use with a conditional breakpoint; we can stop when an out-of-bounds value is encountered. In our toy example, all data values will be in the range 1–3 (inclusive). With a bounds check as a breakpoint condition, we’ll stop on out-of-range values and so we don’t need to inspect each execution of the view loop.

After restarting the program, we can set our breakpoint (this time by choosing the source line we’re interested in) and run straight to the phantom value we found earlier:

 (gdb) break list.pas:43 if cur^.data < 1 or cur^.data > 3
 Breakpoint 1 at 0x400334: file list.pas, line 43.
 (gdb) run
 Starting program: /home/blog_posts/list 
 popped 4
 1
 2
 3
 Breakpoint 1, VIEW () at list.pas:43
 43	          writeln(cur^.data);  {print the value}
 (gdb) p cur^.data
 $1 = 12472

(Note that we’re able to specify our breakpoint condition using Pascal syntax.)

We’ve found our corrupted element without having to inspect all the entries manually; from this point, we could proceed with our deductions and bug-fixing as before. The conditional breakpoint has let us execute quickly to the corrupted part of the list, so we’re free to focus our effort on the more interesting parts of the task.

Summary

This time, we’ve seen a simple example of how to find a bug in Pascal code using GDB. By compiling our executable with debug information, we were able to set breakpoints and explore the code just as we’re used to with C/C++ programs. We were also able to interact with GDB in our language of choice, specifying variables and expressions in Pascal syntax.

We’ve seen how GDB’s tbreak lets us run quickly to a point in the code when we’re debugging. Using display we were able to enhance the GDB prompt with additional information about the state of the program. Finally, we made conditional breakpoints do some of our work for us: by automatically stopping on out-of-bounds values we avoided the laborious work of stepping through the code to find them manually.

In future articles we’ll continue to explore GDB’s support for different languages and its further time-saving features for interactive work.