ABNORMAL CONTROL FLOW Professor Ken Birman

ABSTRACTIONS CS4414 Lecture 7

CORNELL CS4414 - FALL 2020. 1

 IDEA MAP FOR TODAY
In many situations, we Linux offers programmable signal handling
have a normal control flow mechanisms that mimic interrupts.
but must also deal with The hardware has this
abnormal events. issue: an I/O event might
finish more or less at any C++ offers a similar concept via its throw
Can Dijkstra’s concept of instant. Interrupts are like statement, and the try/catch control structure.
creating abstractions offer procedure calls that occur
a unified way to deal with “when needed”.
All forms of exceptions can disrupt computation,
abnormal control flow?
making it very hard to write a “safe” handler!

CORNELL CS4414 - FALL 2020. 2

PRINTERS APPARENTLY USED TO CATCH FIRE
FAIRLY OFTEN!

CORNELL CS4414 - FALL 2020. 3

HIGHLY EXCEPTIONAL CONTROL FLOW

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/char/lp.c?h=v5.0-rc3
CORNELL CS4414 - FALL 2020. 4
TODAY
Exceptional Control Flow
Linux signals
Programming language-level exceptions
C++ features for handling exceptions

CORNELL CS4414 - FALL 2020. 5

 CONTROL FLOW
Processors do only one thing:
 From startup to shutdown, a CPU simply reads and executes
(interprets) a sequence of instructions, one at a time
 This sequence is the CPU’s control flow (or flow of control)
Physical control flow
<startup>
inst1
inst2
Time
inst3
…
instn
<shutdown>

CORNELL CS4414 - FALL 2020. 6

ALTERING THE CONTROL FLOW
Up to now: two mechanisms for changing control flow:
 Jumps and branches… Call and return
 In effect, we change control flow to react to changes in program state

Insufficient: We also need to react to changes in system state

 Data arrives from a disk or a network adapter
 Instruction divides by zero
 User hits Ctrl-C at the keyboard… Timer expires…

CORNELL CS4414 - FALL 2020. 7

EXCEPTIONS: SEVERAL “FLAVORS” BUT
MANY COMMONALITIES
All exceptions “seize control,” generally by forcing the immediate execution
of a handler procedure, no matter what your process was doing.

When a hardware device wants to signal that something needs attention, or

has gone wrong, we say that the device triggers an interrupt. Linux
generalizes this and views all forms of exceptions as being like interrupts.

Once this occurs, we can “handle” the exception in ways that might hide it, or
we may need to stop some task entirely (like with ^C).

CORNELL CS4414 - FALL 2020. 8

BIGGEST CONCERN
An exception can occur in the middle of some sort of expression
evaluation, or data structure update.

For example, if your code manages a linked list, the exception

could occur in the middle of adding a node!

So… the handler cannot assume that data structures are intact!
CORNELL CS4414 - FALL 2020. 9
HOW WE HANDLE THIS
We think in terms of “recoverable” exceptions and “non-
recoverable” ones.

A recoverable exception occurs if the kernel or the program can

handle the exception, then resume normal execution.

A non-recoverable exception terminates the task (or perhaps just

part of some task).
CORNELL CS4414 - FALL 2020. 10
LET’S LOOK FIRST AT MECHANISMS, BUT THEN WE
WILL SEE AN ABSTRACTION EMERGE
A mechanistic perspective looks at how each class of event
arises. Each form of abnormal control flow has a concrete cause

Because the hardware features are diverse, we could end up

with a diverse set of language features to deal with them.

In practice, there is a surprisingly degree of uniformity

representing one abstraction that is applies in various ways
CORNELL CS4414 - FALL 2020. 11
THIS ILLUSTRATES CONCEPTUAL ABSTRACTION
Rather than abstracting storage, the way a file system abstracts
the storage blocks on a device, control flow abstractions have a
conceptual flavor.

They illustrate a reused design pattern and a way of thinking

about abnormal control flow. This concept is universal, yet the
embodiment varies.

CORNELL CS4414 - FALL 2020. 12

THIS DESIGN PATTERN IS A LINUX FEATURE
An exception often causes a transfer of control to the OS kernel
in response to some event (i.e., change in processor state)
 Examples: Divide by 0, arithmetic overflow, page fault, I/O request
completes, typing Ctrl-C

User code Kernel code

Event I_current Exception

I_next Exception processing
by exception handler
• Return to I_current
• Return to I_next
• Abort

CORNELL CS4414 - FALL 2020. 13

EXCEPTION TABLES
Exception
numbers

Each type of event has a Code for

unique exception number k exception handler 0
Exception Code for
Table exception handler 1
0
1
k = index into exception table 2
Code for
exception handler 2
(a.k.a. interrupt vector) ...
n-1 ...
Code for
Handler k is called each time exception handler n-1

exception k occurs
CORNELL CS4414 - FALL 2020. 14
EXCEPTION TABLES
The kernel has one for interrupts.

Each process has one for signals.

The entries are simply the addresses of the handler methods. A

special exception handler turns the exception into a kind of
procedure call, at which the handler runs like normal code.
CORNELL CS4414 - FALL 2020. 15
(PARTIAL) TAXONOMY
ECF

Asynchronous Synchronous

Interrupts Traps Faults Aborts

CORNELL CS4414 - FALL 2020. 16

ASYNCHRONOUS EXCEPTIONS (INTERRUPTS)
Caused by events external to the processor
 Indicated by setting the processor’s interrupt pin
 Handler returns to the instruction that was about to execute
Examples:
 Timer interrupt
 Every few ms, an external timer chip triggers an interrupt.
 Used by the kernel to take back control from user programs
 I/O interrupt from external device
 Typing a character or hitting Ctrl-C at the keyboard
 Arrival of a packet from a network, or data from a disk
CORNELL CS4414 - FALL 2020. 17
SYNCHRONOUS EXCEPTIONS
Caused by events that occur as a result of executing an instruction:
 Traps
 Intentional, set program up to “trip the trap” and do something
 Examples: system calls, gdb breakpoints. Control resumes at “next” instruction
 Faults
 Unintentional but possibly recoverable
 Examples: page faults (recoverable), protection faults (unrecoverable), floating point exceptions
 Either re-executes faulting (“current”) instruction or aborts
 Aborts
 Unintentional and unrecoverable… Aborts current program
 Examples: illegal instruction, parity error, machine check

CORNELL CS4414 - FALL 2020. 18

SYSTEM CALLS
 Each Linux system call has a unique ID number
 Examples:
Number Name Description
0 read Read file
1 write Write file
2 open Open file
3 close Close file
4 stat Get info about file
57 fork Create process
59 execve Execute a program
60 _exit Terminate process
62 kill Send signal to process
CORNELL CS4414 - FALL 2020. 19
SYSTEM CALL EXAMPLE: OPENING FILE
User calls: open(filename, options)
Calls __open function, which invokes system call instruction syscall

00000000000e5d70 <__open>:
...
e5d79: b8 02 00 00 00 mov $0x2,%eax # open is syscall #2
e5d7e: 0f 05 syscall # Return value in %rax
e5d80: 48 3d 01 f0 ff ff cmp $0xfffffffffffff001,%rax
...
e5dfa: c3 retq

User code Kernel code  %rax contains syscall number

 Other arguments in %rdi,
syscall
Exception %rsi, %rdx, %r10, %r8, %r9
cmp
Open file
 Return value in %rax
Returns  Negative value is an error
corresponding to negative
errno
SYSTEM CALL EXAMPLE: OPENING FILE
Almost like a function call
• Transfer of control
User calls: open(filename, options)
• On return, executes next instruction
• Passes arguments using calling convention
Calls __open function, which
• Getsinvokes %raxcall instruction syscall
system
result in

00000000000e5d70 <__open>: One Important exception!

... • Executed by Kernel
e5d79: b8 02 00 00 00 mov $0x2,%eax # open is syscall #2
e5d7e: 0f 05
• Different
syscall
set of privileges
# Return value in %rax
• $0xfffffffffffff001,%rax
e5d80: 48 3d 01 f0 ff ff cmp And other differences:
... • e.g., “address” of “function” is in %rax
e5dfa: c3 retq • Uses errno
• Etc.

User code Kernel code  %rax contains syscall number

 Other arguments in %rdi,
syscall
Exception %rsi, %rdx, %r10, %r8, %r9
cmp
Open file
 Return value in %rax
Returns  Negative value is an error
corresponding to negative
errno
FAULT EXAMPLE: PAGE FAULT int a[1000];
main ()
{
a[500] = 13;
User writes to memory location }

That portion (page) of user’s memory is

currently paged out (on disk)
80483b7: c7 05 10 9d 04 08 0d movl $0xd,0x8049d10

User code Kernel code

Exception: page fault

movl
Copy page from
disk to memory
Return and
reexecute movl
FAULT EXAMPLE: INVALID MEMORY REFERENCE
int a[1000];
main ()
{
a[5000] = 13;
}
80483b7: c7 05 10 9d 04 08 0d movl $0xd,0x8049d10

User code Kernel code

Exception: page fault

movl
Detect invalid address
Signal process

CORNELL CS4414 - FALL 2020. 23

SOME FLAVORS OF SEGMENT FAULTS
Trying to read or write into memory that isn’t part of your
address space.

Trying to modify a write-protected data or code segment.

Trying to jump into (execute) a data segment (this is actually

possible, but you have to do something special).
CORNELL CS4414 - FALL 2020. 24
YET EXCEPTIONS ALSO ALLOW US TO
EMULATE “INFINITE NUMBER OF CORES”
Basic idea: if we have more threads than cores, we can use timer
exceptions to switch from thread to thread (or process to process)

This is called a “context switch” and involves saving the state of

the interrupted thread: the contents of the registers.

Then we can load the state of the thread we wish to switch to.
CORNELL CS4414 - FALL 2020. 25
CONTEXT SWITCHES BETWEEN PROCESSES
For the hardware, a process is simply a set of threads plus a
memory map that tells which memory pages belong to the
process, and what protection rules to apply.

As part of the context switch, the kernel simply tells the

hardware which “page table” to use for this process.

CORNELL CS4414 - FALL 2020. 26

TODAY
Exceptional Control Flow
Linux signals
Programming language-level exceptions
C++ features for handling exceptions

CORNELL CS4414 - FALL 2020. 27

LINUX SIGNALS
Linux uses a variety of signals to “tell” an active process about exceptions
relevant to it. The approach mimics what the hardware does for interrupts.

The signal must be caught or ignored. Some signals are ignored by default.
Others must be caught and will terminate the process if not.

To catch a signal, a process (or some library it uses) must register a “signal
handler” procedure. Linux will pause normal execution and call the handler.
When the handler returns, the interrupted logic resumes.

CORNELL CS4414 - FALL 2020. 28

LIST OF LINUX SIGNALS
SIGABRT Abort signal from abort(3) SIGPROF Profiling timer expired
SIGALRM Timer signal from alarm(2) SIGPWR Power failure (System V)
SIGBUS Bus error (bad memory access) SIGQUIT Quit from keyboard
SIGCHLD Child stopped or terminated SIGSEGV Invalid memory reference
SIGCONT Continue if stopped SIGSTOP Stop process
SIGEMT Emulator trap SIGTSTP Stop typed at terminal
SIGFPE Floating-point exception
SIGSYS Bad system call (SVr4)
SIGTERM Termination signal
SIGHUP User logged out or controlling process SIGTRAP Trace/breakpoint trap
terminated SIGTTIN Terminal input for background process
SIGILL Illegal Instruction SIGTTOU Terminal output for background process
SIGINFO A synonym for SIGPWR SIGURG Urgent condition on socket (4.2BSD)
SIGINT Interrupt from keyboard SIGUSR1 User-defined signal 1
SIGIO I/O now possible (4.2BSD) SIGUSR2 User-defined signal 2
SIGIOT IOT trap. A synonym for SIGABRT SIGVTALRM Virtual alarm clock (4.2BSD)
SIGKILL Kill signal (cannot be caught or ignored) SIGXCPU CPU time limit exceeded (4.2BSD)
SIGLOST File lock lost (unused) SIGXFSZ File size limit exceeded (4.2BSD)
SIGPIPE Broken pipe: write to pipe with no readers SIGWINCH Window resize signal (4.3BSD, Sun)
SIGPOLL Pollable event (Sys V); synonym for SIGIO

CORNELL CS4414 - FALL 2020. 29

GDB – LINUX DEBUGGER
Allows you to understand where an exception occurred.

You can set breakpoints, examine variables, see the call stack

You can even watch individual variables

Uses exception handlers for all of this!

CORNELL CS4414 - FALL 2020. 30
PAUSE FOR A DEMO: LETS SEE WHAT HAPPENS
IF A PROGRAM TRIES TO ACCESS MEMORY
INAPPROPRIATELY, AND HOW GDB HELPS US
TRACK SUCH AN ISSUE DOWN.

CORNELL CS4414 - FALL 2020. 31

 GDB cheatsheet - page 1
Running <where> next
# gdb <program> [core dump] function_name Go to next instruction (source line) but
Start GDB (with optional core dump). Break/watch the named function. donʻt dive into functions.
# gdb --args <program> <args…> line_number finish
Start GDB and pass arguments Break/watch the line number in the cur- Continue until the current function re-
rent source file. turns.
# gdb --pid <pid>
Start GDB and attach to process. file:line_number continue
Break/watch the line number in the Continue normal execution.
set args <args...>
named source file.
Set arguments to pass to program to Variables and memory
be debugged. Conditions print/format <what>
run break/watch <where> if <condition> Print content of variable/memory locati-
Break/watch at the given location if the on/register.
Run the program to be debugged.
condition is met. display/format <what>
kill
Conditions may be almost any C ex- Like „print“, but print the information
Kill the running program.
pression that evaluate to true or false. after each stepping instruction.
Breakpoints condition <breakpoint#> <condition> undisplay <display#>
break <where> Set/change the condition of an existing Remove the „display“ with the given
Set a new breakpoint. break- or watchpoint. number.
delete <breakpoint#>
Examining the stack enable display <display#>
Remove a breakpoint. backtrace disable display <display#>
clear where En- or disable the „display“ with the gi-
Delete all breakpoints. Show call stack. ven number.
enable <breakpoint#> backtrace full x/nfu <address>
Enable a disabled breakpoint. where full Print memory.
Show call stack, also print the local va- n: How many units to print (default 1).
disable <breakpoint#>
riables in each frame. f: Format character (like „print“).
Disable a breakpoint. u: Unit.
frame <frame#>
Watchpoints Select the stack frame to operate on. Unit is one of:
watch <where>
b: Byte,
Set a new watchpoint. Stepping h: Half-word (two bytes)
step
delete/enable/disable <watchpoint#> w: Word (four bytes)
Go to next instruction (source line), di-
Like breakpoints. g: Giant word (eight bytes)).
ving into function.

© 2007 Marc Haisenko <marc@darkdust.net>

 GDB cheatsheet - page 2
Format Manipulating the program Informations
a Pointer. set var <variable_name>=<value> disassemble
c Read as integer, print as character. Change the content of a variable to the disassemble <where>
d Integer, signed decimal. given value. Disassemble the current function or
f Floating point number. given location.
return <expression>
o Integer, print as octal. Force the current function to return im- info args
s Try to treat as C string. mediately, passing the given value. Print the arguments to the function of
t Integer, print as binary (t = „two“). the current stack frame.
u Integer, unsigned decimal. Sources
x Integer, print as hexadecimal. directory <directory> info breakpoints
Print informations about the break- and
<what> Add directory to the list of directories
expression that is searched for sources. watchpoints.
Almost any C expression, including list info display
function calls (must be prefixed with a list <filename>:<function> Print informations about the „displays“.
cast to tell GDB the return value type). list <filename>:<line_number> info locals
file_name::variable_name list <first>,<last> Print the local variables in the currently
Content of the variable defined in the Shows the current or given source con- selected stack frame.
named file (static variables). text. The filename may be omitted. If
last is omitted the context starting at info sharedlibrary
function::variable_name start is printed instead of centered a- List loaded shared libraries.
Content of the variable defined in the round it. info signals
named function (if on the stack).
set listsize <count> List all signals and how they are cur-
{type}address Set how many lines to show in „list“. rently handled.
Content at address, interpreted as info threads
being of the C type type. Signals List all threads.
handle <signal> <options>
$register show directories
Set how to handle signles. Options are:
Content of named register. Interesting Print all directories in which GDB sear-
registers are $esp (stack pointer), $ebp (no)print: (Donʻt) print a message when ches for source files.
(frame pointer) and $eip (instruction signals occurs.
pointer). show listsize
(no)stop: (Donʻt) stop the program Print how many are shown in the „list“
Threads when signals occurs. command.
thread <thread#> (no)pass: (Donʻt) pass the signal to the
Chose thread to operate on. whatis variable_name
program. Print type of named variable.

© 2007 Marc Haisenko <marc@darkdust.net>

TODAY
Exceptional Control Flow
Linux signals
Programming language-level exceptions
C++ features for handling exceptions

CORNELL CS4414 - FALL 2020. 34

UNHANDLED SEGMENTATION FAULTS
Our program dereferenced a null pointer, causing a segmentation
fault. gdb showed us the line and variable responsible for the crash.

Notice the contrast with the cases where Linux was able to handle the
fault: page faults and stack faults… in those, the program hadn’t done
anything wrong... The instruction that caused the fault can be retried
(and will succeed) once the new page is mapped in.

With a segmentation fault, there is no way to “repair” the issue.

CORNELL CS4414 - FALL 2020. 35

WHAT CAN WE DO?
Segmentation faults terminate the process.

But you could also “imagine” catching them and just terminating
some thread that triggered the fault.

Other kinds of exceptions might be user-designed ones intended

to reflect program logic, like “divide by 0” in Bignum
CORNELL CS4414 - FALL 2020. 36
… LEADING TO
The C++ concept of a “thrown” exception, and try/catch

We use this feature to manage many kinds of exceptions that

we anticipated and want to handle in code

But it can be a bit tricky to get this right without leaking memory
or other kinds of resources, as we will see next
CORNELL CS4414 - FALL 2020. 37
TODAY
Exceptional Control Flow
Linux signals
Programming language-level exceptions
C++ features for handling exceptions

CORNELL CS4414 - FALL 2020. 38

EXCEPTIONS AT THE LANGUAGE LEVEL
Many programming languages have features to help you manage exceptions.

For Linux signals, this is done purely through library procedures that register that register the
desired handler method.

But for program exceptions, a program might halt, or there may be a way to manage the
exception and resume execution.

One big difference: Linux can restart a program at the exact instruction and in the exact state
it was in prior to an interrupt or signal. But a programming language generally can’t resume
the same instruction after an event like a zero divide, so we need a way to transfer control to
“alternative logic”
CORNELL CS4414 - FALL 2020. 39
WHAT CAN WE DO IF A FAULT MIGHT OCCUR,
BUT CAN BE HANDLED?
Most languages, including C++, offer a way to attempt some
action, but then “catch” exceptions that might occur.

As part of these mechanisms the application is given a way to

“throw” an exception if the logic detects a problem.

CORNELL CS4414 - FALL 2020. 40

C++ CONSTRUCT
try
{
do_something…
}
catch (exception-type) // Something went wrong!
{
handler for exception // “Fix” the issue (or report it)
}

CORNELL CS4414 - FALL 2020. 41

C++ CONSTRUCT
try
{
salaries[employee] *= 1.05;// Give a raise…
}
catch (EmployeeUnknown) // “Employee unknown”
{
handler for exception // Print an error msg
}

CORNELL CS4414 - FALL 2020. 42

“DO_SOMETHING” WON’T BE RETRIED
When Linux handled a page fault, it restarted the program on
the same instruction and in the same state as it had at the fault.

When C++ catches this “not found” error and prints the error
message, we just continue with the next line of code.

CORNELL CS4414 - FALL 2020. 43

A COMMON ISSUE THIS CAN RAISE
Suppose that your program was working with a resource such as
an open file, or was holding a lock (we’ll discuss locks soon…)

The try/catch can jump to a caller, exiting from one or more

code blocks and method calls that were active.

Thus the resource could be left “dangling”, causing memory

leaks or open files or other potential problems.
CORNELL CS4414 - FALL 2020. 44
 VISUALIZING THIS ISSUE
void annual_sip(float standard_raise)
{
for(auto emp: emp_list)
{ void give_raise(char* name, float raise)
try {
{ FILE *fp = fopen(“Paychecks.dat”);
give_raise(emp.name, .05); salaries[name] *= 1.0 + raise;
} …. write a record in the paychecks file…
catch(EmployeeNotFound) fclose(fp);
{ }
cout << “Salary DB is missing an employee!” << endl;
}
}

CORNELL CS4414 - FALL 2020. 45

 VISUALIZING THIS ISSUE
void annual_sip(float standard_raise)
{
for(auto emp: emp_list) If this employee is not in
{ the salaries database, void give_raise(char* name, float raise)
try exception is thrown here. {
{ FILE *fp = fopen(“Paychecks.dat”);
give_raise(emp.name, .05); salaries[name] *= 1.0 + raise;
} …. write a record in the paychecks file…
catch(EmployeeNotFound) fclose(fp);
{ }
cout << “Salary DB is missing an employee!” << endl;
}
}

CORNELL CS4414 - FALL 2020. 46

 VISUALIZING THIS ISSUE
void annual_sip(float standard_raise)
{
for(auto emp: emp_list)
{ void give_raise(char* name, float raise)
Thetryexception transfers control to the catch block {
in{ annual_sip. The stack frame of give_raise is FILE *fp = fopen(“Paychecks.dat”);
released. But this means that.05);
give_raise(emp.name, the line that calls salaries[name] *= 1.0 + raise;
fclose
} will never execute, so we “leak” open files! …. write a record in the paychecks file…
catch(EmployeeNotFound) fclose(fp);
{ }
cout << “Salary DB is missing an employee!” << endl;
}
}

CORNELL CS4414 - FALL 2020. 47

LINKED LIST EXAMPLE
Suppose that your code is adding a node in a linked list. Now
the exception handler tries to access that list data structure.

The list might sometimes “seem to be broken” because not all the
pointers will have their correct values!

Any data that your program updates could be seen during the
update, rather than just before or after!
CORNELL CS4414 - FALL 2020. 48
EXCEPTIONS RUN A RISK OF BUGS!
If an exception handler were to look at this list while it was
changing, it could crash! Similarly, an exception handler can’t
allocate new memory objects, or print a message – all of those
could be unsafe at some random moment when the handler runs!

Solution? Sometimes you can temporarily disable exception

handling. Additionally, it is always best for exceptional handlers
to be short, self-contained, and to not invoke library methods!
CORNELL CS4414 - FALL 2020. 49
THAT ISSUE WON’T ARISE WITH C++ CATCH
A throw/catch sequence won’t resume the code that threw the
exception.

Moreover, in C++ we will have run the destructors for all stack
allocated objects that went out of scope before running catch.

This gives a very predicable, controlled behavior

CORNELL CS4414 - FALL 2020. 50
COULD C++ THROW/CATCH REPLACE
SIGNALS?
It may seem natural to think about using throw/catch as a signal
replacement, but this won’t work.

The problem is that a signal is asynchronous and unpredictable.

With throw/catch the exception is synchronous and usually involves a
software “choice” to throw the exception.

This is a shame, in fact, because it is so hard to write safe signal

handlers.

CORNELL CS4414 - FALL 2020. 51

SUMMARY
The exception pattern is very widely seen in Linux and C++. Broadly,
exception handling mimics hardware interrupts. But hardware
interrupts and signals can be “inhibited”.

C++ try/catch control flow can’t be inhibited and can easily disrupt
updates and resource management: a potential source of serious bugs.

Per-resource wrappers offer an elegant solution.

CORNELL CS4414 - FALL 2020. 52