„Lazy Evaluation“ in POSIX-C, using sigaction(2)

It amazes me time and again how flexible POSIX (and other lowlevel-stuff in common unix-like environments in general) is. Surprising enough that fork(3)-ing doesnt result in a doubled memory-consumption in general, because the Pages are mapped Copy-On-Write – which is a nice thing, but still done by the kernel – it even gives the userspace-processes a lot of control about paging. So I wonder why most of the programmers just use malloc(3) – maybe because its the most portable non-gc-possibility to organize memory. I know that SBCL uses libsigsegv to optimize its memory management.

For a long time now I had the idea of implementing lazy evaluation with pure C using libsigsegv. The plan was to allocate some address-space and mprotect(2) it, and then, as soon as someone accesses it, a sigsegv is thrown, and the handler calculates the contents of the accessed memory block, unprotects it, and saves the calculated value, and then returns back, so the calculated value can be accessed from this point on. Ok, this is not quite lazy evaluation – for example you cannot (at least not trivially) create infinite lists with this, but it goes into that direction, its like „calculating on demand“.

So I wrote a program doing this using libsigsegv, but unfortunately, I couldnt work recursively with libsigsegv, i.e. if I accessed a protected part of the memory during the sigsegv-handler, the program would exit. But libsigsegv is only a wrapper, probably around sigagtion(2). Sigaction itself allows recursive handling of signals, when using the flag SA_NODEFER. So I wrote the below Program. It calculates the fibonacci-sequence „blockwise“ – an array fib is allocated, and – on an x86-processor – split into 1024-wise arrays of integers. It also prints out the registers of the context of the error (that is, it produces a lot of output – be carefull when compiling it). And – well, I only tested it on x86 linux 2.6.26 and x86_64 linux 2.6.32, in the latter case, it doesnt work, it traps in an infinite loop.

#include <sys/mman.h>
#include <sys/user.h>
#include <malloc.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <strings.h>
#include <ucontext.h>
#define __USE_GNU
#include <sys/ucontext.h>
#include <signal.h>

int * fib;
int * fib_e;

#define PAGE_FIBNUM (PAGE_SIZE / sizeof(int))

void sa_sigac (int sig, siginfo_t * siginfo, void* vcontext) {
 struct ucontext* context = (struct ucontext*) vcontext;

 size_t regs_size = sizeof(context->uc_mcontext.gregs);
 char format_hex[(3*regs_size)+10], format_dec[(3*regs_size)+9];
 memcpy (&format_hex, (void*) "Regshex:", 8);
 memcpy (&format_dec, (void*) "Regsdec:", 8);
 format_hex[(3*regs_size)+8] = format_dec[(3*regs_size)+8] = '\n';
 format_hex[(3*regs_size)+9] = format_dec[(3*regs_size)+9] = '';
 int i;
 for (i=8; i < (3*regs_size)+8; i+=3) {
 format_hex[i] = format_dec[i] = ' ';
 format_hex[i+1] = format_dec[i+1] ='%';
 format_hex[i+2] = 'x';
 format_dec[i+2] = 'u';
 }

 printf(format_hex, context->uc_mcontext.gregs);
 printf(format_dec, context->uc_mcontext.gregs); 

 void* failt_address = siginfo->si_addr;
 int number = ((int)failt_address - (int)fib) / sizeof(int);
 printf("Accessed: %d\n", number);
 int firstcalc = number - (number % PAGE_FIBNUM);
 int lastcalc = firstcalc + PAGE_FIBNUM;
 printf("Calculating Fibonacci-Sequence from %d to %d\n",
 firstcalc, lastcalc);
 mprotect(fib+firstcalc, PAGE_SIZE*sizeof(int), PROT_READ | PROT_WRITE);

 if (firstcalc == 0) {
 /* initial elements of fibonacci sequence */
 *(fib+firstcalc) = 0;
 *(fib+firstcalc+1) = 1;
 } else {
 *(fib+firstcalc) = *(fib+firstcalc-1) + *(fib+firstcalc-2);
 *(fib+firstcalc+1) = *(fib+firstcalc) + *(fib+firstcalc-1);
 }

 int * ccalc;

 for (ccalc = fib+firstcalc+2; ccalc < fib+lastcalc; ccalc++) {
 *ccalc = *(ccalc-1) + *(ccalc-2);
 }
}

int main (int argc, char* argv[]) {

 int fnum;

 if (argc == 1) {
 printf ("Please supply a number.\n");
 return -1;
 } else {
 sscanf(argv[1], "%d", &fnum);
 if (fnum > 20*PAGE_SIZE) {
 printf ("The number must not be greater than %u.\n",
 20*PAGE_SIZE);
 return -1;}
 }

 struct sigaction myaction;
 myaction.sa_sigaction = &sa_sigac;
 bzero(&myaction.sa_mask, sizeof(sigset_t));
 myaction.sa_flags = SA_NODEFER | SA_SIGINFO;
 myaction.sa_restorer = NULL;

 sigaction(SIGSEGV, &myaction, NULL);

 int fib_begin[24*PAGE_SIZE];
 int fb = (int) (&fib_begin);
 fib = (int*) ((fb - (fb % PAGE_SIZE)) + PAGE_SIZE);
 fib_e = fib + PAGE_SIZE;
 int e = mprotect (fib, 20*PAGE_SIZE*sizeof(int), PROT_NONE);
 perror("");
 printf("fib(%d) %% %u := %u\n", fnum, -1, fib[fnum]);
 return 0;

}

There are a few flaws in this source: It doesnt work under x86_64, even though I dont really see which part is not independent of the bus-width. Of course, handling it that way is highly unportable, but most unix-derivates should be able to do at least something like that.

The major flaw I dont like is that I am bound to calculating a whole block at once, and not being able to mprotect this block again afterwards. In theory, it should be possible to find out in which register the value should have been read and then manipulating the context and setjmp(3)-ing to it, so it doesnt try to read it again afterwards. But I myself cannot even access the registers directly by their name, though in sys/ucontext.h there is an enumeration with defined index-names, but they seem not to be defined when I am trying to use them. I dont know why. I just print them all out in the hope that I see some structure inside them, but so far, I didnt see much. I guess one has to know a lot of lowlevel-stuff about x86 to understand whats actually going on, which I dont have.

Anyway, I think this is very interesting. It may not be usefull at all, but its a nice thing.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: