Segfaulting own programs for fun and profit

Most people hate segfaults - and no wonder, getting one usually indicates a serious and difficult to debug problem, very likely also a security hole. People tend to be grateful that their language doesn't have segfaults.

I'm going to propose something seemingly insane - segfaulting your own programs on purpose. It will be necessary to switch to a low-level point of view, but if you stay with me, you'll get a great new tool.

Magical complex numbers

The program I'm going to show simply prints complex numbers. These numbers are magical - in addition to the usual re and im fields they contain a as_string field which always magically contains textual representation of them. You don't have to follow any special API - as_string updates itself automagically on demand. From user point of view the only way complex_t differs from a run-of-the-mill complex type are special allocation and deallocation routines (nothing unusual in C APIs), and the magical as_string field.

/* magic_complex.h */
typedef struct {
   double re, im;
   char *as_string;
} complex_t;

complex_t *complex_new();
void complex_free(complex_t *complex);

/* main.c */
#include <stdio.h>
#include "magic_complex.h"

int main()
{
   complex_t *a = complex_new();
   a->re = 5.0;
   a->im = -2.0;

   printf("%s\n", a->as_string);
   printf("%s\n", a->as_string);

   a->re = 3.0;
   printf("%s\n", a->as_string);

   return 0;
}

Compiling the program and running it produces the expected output. But how ?

$ ./main
5.000000-2.000000i
5.000000-2.000000i
3.000000-2.000000i

What really happens in hardware

Before I show the implementation of magical complex numbers, let's take a look at hardware. Back in the early days of x86, "real" memory model was used. Reading memory cell 0x1234 meant physical hardware cell 0x1234. If program accessed memory which wasn't physically there, program stopped and a special operating system procedure was called to decide what to do next.

On modern x86 the situation is different. Programs don't access memory directly. Instead, they access virtual memory, which is organized in 4096-byte "pages". So reading memory cell 0xb7fcb123 actually means reading cell 0x123 of whatever physical memory corresponds to virtual memory page 0xb7fcb***.

It's possible for a page to point nowhere, or to have restricted access (typically read only). If such page is accessed, a special operating system procedure is called to decide what next. Many such invalid accesses are handled within the operating system, and the operation which caused them reruns. If the operating system doesn't know what to do, it delivers Segmentation Fault signal to the program.

Many invalid accesses can be fixed by the operating system, by making the page active or increasing its permissions. For example if programs use too much memory, some of their memory gets swapped to disk, and corresponding pages are marked as inactive. If they're accessed, the operating system gets informed of access violation, reads the page from disk, and reruns the operation which caused the problem.

Another example are mmap-ed files. Instead of reading and writing files, programs can mmap them. mmap associates some pages of memory with contents of some file. When program accesses this memory, it's read from the disk. mmaping is easier than reading files (file contents appear as if they were in memory), often faster (as reading is only done on-demand), and takes less physical memory, because if multiple programs mmap the same file, the operating system can load it just once. This is much more common than it seems at first - all executables and shared libraries are mmaped, so if you run 15 copies of bash and 540 programs use libc, code of both is present in the physical memory only once.

The operating system performs even more interesting tricks. When a program forks, instead of duplicating all its memory the operating system only marks it as read-only. When either parent or child writes to one of such pages, the operating system copies them and marks as read/write. This way memory is used only when necessary.

When the operating system doesn't know what to do with an access violation, it signals segmentation fault. Most programs upon getting a segmentation fault simply an print error message and exit. But there are so many cool things one can do with virtual memory, it would be a shame not to use them.

Magical complex number library

The library consists of two parts. One part (laziness.c) handles ugly low-level issues and hides them behind a pretty interface. The other part (magic_complex.c) implements magic complex numbers.

The interface to the laziness library looks like that:

/* laziness.h */
#define PAGE_SIZE 4096
#define LAZY_SIZE PAGE_SIZE

typedef void (*fault_handler_t)(void*, void*);

void *lazy_alloc_rw(void);
void *lazy_alloc_ro(fault_handler_t fault_handler, void *data);
void *lazy_alloc_none(fault_handler_t fault_handler, void *data);

void lazy_make_rw(void *obj);
void lazy_make_ro(void *obj, fault_handler_t fault_handler, void *data);
void lazy_make_none(void *obj, fault_handler_t fault_handler, void *data);

void lazy_free(void *obj);

lazy_alloc_* functions allocate pages of memory with read-write, read-only, or no-access permissions. lazy_make_* functions change access permissions to existing memory. lazy_free frees such memory. Read-only and no-access versions of lazy_alloc_* and lazy_make_* also register a fault_handler argument, which will be run if such memory is accessed illegally. Always exactly 4096 bytes are allocated (or whatever is your hardware page size). It wouldn't be difficult to allocate multiples of 4096, but I wanted to keep the code simple.

Finally, the magic complex numbers library:

/* magic_complex.c */
#include <stdio.h>
#include "laziness.h"
#include "magic_complex.h"

void complex_main_fault(complex_t *complex, void *data);
void complex_string_fault(char *as_string, complex_t *complex);

void complex_main_fault(complex_t *complex, void *data)
{
   lazy_make_rw(complex);
   lazy_make_none(complex->as_string, complex_string_fault, complex);
}

void complex_string_fault(char *as_string, complex_t *complex)
{
   lazy_make_ro(complex, complex_main_fault, 0);
   lazy_make_rw(as_string);
   snprintf(as_string, LAZY_SIZE, "%f%+fi", complex->re, complex->im);
   as_string[LAZY_SIZE-1] = 0;
}

complex_t *complex_new()
{
   complex_t *complex = lazy_alloc_rw();
   complex->as_string = lazy_alloc_none(complex_string_fault, complex);
   return complex;
}

void complex_free(complex_t *complex)
{
   lazy_free(complex->as_string);
   lazy_free(complex);
}

Some explanations are needed. When new number is allocated (complex_new), the library allocated two hardware pages - one read/write for the object itself, and one no-access for the magical as_string.

When as_string is used, complex_string_fault runs. It marks the string read/write, and the object read-only. Then it generates as_string using snprintf. As the object is read-only now, we can be sure the string doesn't go out of sync.

When the read-only object is written to, complex_main_fault is run, the object page is marked read/write, the as_string page is marked no-access, and so we can be sure that when as_string is requested it will be generated anew.

Laziness library

Low-level part of the library is bigger and more complex, so I'll describe it part by part.

/* laziness.c */
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <signal.h>
#include <unistd.h>

#include "laziness.h"

struct fault_handlers_list
{
   void *obj;
   fault_handler_t fault_handler;
   void *data;
   struct fault_handlers_list *next;
};

struct fault_handlers_list *fault_handlers_list_root;

void remove_fault_handler(void *obj)
{
   struct fault_handlers_list **prev = &fault_handlers_list_root;
   struct fault_handlers_list *node;
   while(*prev)
   {
       node = *prev;
       if(node->obj == obj)
       {
           *prev = node->next;
           free(node);
           return;
       }
       prev = &(node->next);
   }
   /* No fault handler for obj */
}

void install_fault_handler(void *obj, fault_handler_t fault_handler, void *data)
{

   struct fault_handlers_list *node = malloc(sizeof(struct fault_handlers_list));
   node->obj = obj;
   node->fault_handler = fault_handler;
   node->data = data;
   node->next = fault_handlers_list_root;
   fault_handlers_list_root = node;
}

install_fault_handler and remove_fault_handler maintain a list of fault handlers, in form of a linked list. It's of course extremely lame - in practice a hash table would be used, or a few bytes of the object would be reserved for fault handler. It's also extremely simple, so let's ignore performance for now.

void *lazy_alloc_rw(void)
{
   void *obj = mmap(0, PAGE_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
   return obj;
}

void *lazy_alloc_ro(fault_handler_t fault_handler, void *data)
{
   void *obj = mmap(0, PAGE_SIZE, PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
   if(fault_handler)
       install_fault_handler(obj, fault_handler, data);
   return obj;
}

void *lazy_alloc_none(fault_handler_t fault_handler, void *data)
{
   void *obj = mmap(0, PAGE_SIZE, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
   if(fault_handler)
       install_fault_handler(obj, fault_handler, data);
   return obj;
}

lazy_alloc_* routines mmap an anonymous (that is - not associated with any file) page of memory with appropriate permissions and register a fault handler if any was given.

void lazy_make_rw(void *obj)
{
   remove_fault_handler(obj);
   mprotect(obj, PAGE_SIZE, PROT_READ|PROT_WRITE);
}

void lazy_make_ro(void *obj, fault_handler_t fault_handler, void *data)
{
   remove_fault_handler(obj);
   mprotect(obj, PAGE_SIZE, PROT_READ);
   if(fault_handler)
       install_fault_handler(obj, fault_handler, data);
}

void lazy_make_none(void *obj, fault_handler_t fault_handler, void *data)
{
   remove_fault_handler(obj);
   mprotect(obj, PAGE_SIZE, PROT_NONE);
   if(fault_handler)
       install_fault_handler(obj, fault_handler, data);
}

void lazy_free(void *obj)
{
   remove_fault_handler(obj);
   munmap(obj, PAGE_SIZE);
}

lazy_make_* functions remove the old fault handler, change access permissions, and install a new fault handler. lazy_free removes the old handler and unmaps the memory page.

And the last part:

void lazy_segfault_handler(int signum, siginfo_t *siginfo, void *something)
{
   void *obj = (void*)((unsigned int)(siginfo->si_addr) & ~(PAGE_SIZE-1));
   struct fault_handlers_list *node = fault_handlers_list_root;

   while(node)
   {
       if(obj == node->obj)
       {
           node->fault_handler(obj, node->data);
           return;
       }
       node = node->next;
   }
   fprintf(stderr, "Segmentation fault: %p\n", siginfo->si_addr);
   exit(1);
}

void lazy_init() __attribute__((constructor));
void lazy_init()
{
   struct sigaction segfault_handler;
   segfault_handler.sa_sigaction = lazy_segfault_handler;
   segfault_handler.sa_flags = SA_SIGINFO;
   sigemptyset(&segfault_handler.sa_mask);

   sigaction(SIGSEGV, &segfault_handler, 0);
}

lazy_init function is marked as constructor, so it runs automatically when the program starts. I wrote about it in the post about debuggers. It tell the operating system to run lazy_segfault_handler whenever a segmentation fault occurs.

lazy_segfault_handler finds and runs the fault handler. When it returns, the operating system automatically returns the operation which faulted. If none is found, it prints an error message and exits.

Let's take a look at main.c again. What happens inside.

/* main.c */
#include <stdio.h>
#include "magic_complex.h"

int main()
{
   /* a allocated as read/write */
   /* a->as_string allocated as no-access */
   complex_t *a = complex_new();

   /* a is read/write, nothing special happens */
   a->re = 5.0;
   a->im = -2.0;

   /* a->as_string is no-access, segfault */
   /* a becomes read-only */
   /* a->as_string becomes read-write */
   /* a->as_string generated */
   printf("%s\n", a->as_string);

   /* a->as_string is ok, nothing special happens */
   printf("%s\n", a->as_string);

   /* a is read only, segfault */
   /* a becomes read-write */
   /* a->as_string becomes no-access */
   a->re = 3.0;

   /* a->as_string is no-access, segfault */
   /* a becomes read-only */
   /* a->as_string becomes read-write */
   /* a->as_string generated */
   printf("%s\n", a->as_string);

   return 0;
}

Why ?

So now that you see how such things can be done, there's a why question left. Obviously, nobody is going to use the magic complex library in any real program.

Here are a few examples where segfaults may be useful:

• We can make mmap work for http connections, not only local files.
• Some compilers make program reside the stack automatically if it grows too big.
• Some compilers implement the tail call optimization by waiting for the stack to grow too big, and then compressing it.
• Lazy data structures are possible, without user even knowing it ! A plain C list can be produced on-demand.
• Some data structures exist in both C world and other world at the same time and need to be kept in sync. For example in GNOME programs arrays are represented by both glib's GArray and Ruby's RArray. By smart segfaulting it's possible to always keep only one of them active.
• It also works for complex data structures. If the array contains other translatable objects, the magic segfault will make them appear as Ruby objects in Ruby code and as glib objects in glib code.

The example library always allocates 4kB of memory at time. It's trivial to extend it to multiples of 4kB. Resizable objects and objects which take less than a full page are possible, but more complicated. Thread-safety wasn't even attempted. Doing strange things with segfaults can confuse optimizing compilers.

Happy segfaulting.