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

Wed, 31 Mar 2010 23:32:16 +0000

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.

Advertisements

Alternative Star Trek-Zeitlinie

Tue, 30 Mar 2010 18:35:25 +0000

Bei Star Trek wurden öfters Aussagen zu Zeitpunkten in der Zukunft getroffen, die inzwischen jedoch schon in der Vergangenheit liegen. Viele sind allerdings durch den Lauf der Geschichte widerlegt worden (bei einigen zum Glück), zB. die eugenischen Kriege von 1992-1996. Auch der Bau des Millenium-Gates von 2000-2012 wurde noch nicht begonnen und 2002 ist Nomad auch nicht gestartet. Nun gibt es bei Star Trek allerdings auch Zeitreisen, wobei in Star Trek bei Zeitreisen auch alternative Zeitlinien entstehen können, in denen die Geschichte anders abgelaufen ist/abläuft/ablaufen wird (gramatikalisch korrekt formuliere ich bei Zeitreisen schon seit Jahren nicht mehr ;) ).

Irgendwie fände ich es jetzt witzig, wenn ein Star Trek-Film oder eine Serie jetzt von einer Zeitreise handeln würde, welche Veränderungen in der Erdvergangenheit verursacht, so daß gerade die Zeitlinie der Realität hervorkommt (zumindestens so weit, wie sie zum Drehzeitpunkt bekannt ist). Möglicherweise wird bei einer Zeitreise versehentlich die Geburt von Stavos Keniclius verhindert, oder sowas in der Art. Vielleicht passiert noch mehr, um die Zeitlinie in unsere Richtung zu beeinflussen. Eigentlich bin ich mir aber sicher, daß so etwas nicht gedreht werden wird.


Feiertagsvorschlag: Dunkelnacht

Thu, 25 Mar 2010 00:48:11 +0000

Ich hab mir kürzlich über die Lichtverschutzung Gedanken gemacht und kam dabei auf folgende Idee: Man könnte einen Feiertag einführen, an dem man eine Lichtsauberkeit zumindestens mal erleben könnte. An diesem würde man in einer bestimmten Zeit (nachts) großflächig für einige Stunden jegliches Licht abschalten. Das hätte den Effekt, daß alle Menschen zumindestens einmal im Jahr einen klaren unverschutzten Sternenhimmel sehen könnten. Vielleicht würde so eine Maßnahme auch das Interesse der Menschen an dem Universum etwas stärken. Aber so ein Tag ist bestimmt eh nicht bei uns umsetzbar. Nett wäre er trotzdem.


Randomly Found Software: Xpra

Sat, 20 Mar 2010 17:16:53 +0000

One thing I really liked about Windows 7 was its excellent terminal-server-facilities. I could detach a running local session and reattach it again remotely. I could even tunnel it through ssh with ordinary ssh-x-forwarding by installing rdesktop on cygwin. It supported changing the size of the desktop and logging in without being visible on the physical screen.

X11 under Linux never worked that good, let alone Mac OS X, which is sort of the worst of all, with the worst VNC-Implementation I know so far.

Something none of the solutions knew were suspendable rootless GUIs. I dont know for how long I wished there was something like screen for X11-Applications. Well, there it is: Xpra.

It is a surprisingly small set of software, written in python, and though well done. The installation procedure is unusual but well documented, and for Arch Linux, there is an AUR-Package, which is why I love Arch Linux so much more than Debian – there are a lot more buildscripts available.

Having it installed, it can simply be started using

xpra start :1927

This will start a Server listening on Display 1927. To start an application running on this X-Server, we have to set its $DISPLAY to this, or supply it as an argument. I mostly start an XTerm, from which I then can start the rest.

nohup xterm -display :1927 &

If anything works,  the XTerm can be attached to the current server by running

xpra attach :1337

inside another X-Server. It also works remotely, through SSH X-Forwarding. Killing this process via C-c (or – if it is remote – by just pulling the network cable) the XTerm will disappear. But it can be attached again by simply doing the same command as soon as the connection is there again. Like one would do with screen.

When trying to attach a server inside itself, then the connection gets lost, but – surprisingly – I can attach the server afterwards. It doesnt crash. Now if that isnt solid!

There is no Tray-Bar-Integration (yet – I am sure this is possible), so when using tray applications, I use trayer for that.

Of course, it doesnt always work perfectly. I sometimes have to run

setxkbmap de

multiple times. And I heard of some issues with CapsLock. Sometimes I have to give a window the focus twice (i.e. clicking on its titlebar twice) before it actually gets focus. But well, it hasnt even reached version 1.0, and already made my life a little easier. I think its already worth using, and definitely worth being developed (and hopefully integrated into the default package trees of the major distributions).


Oooh ist der süß …

Fri, 19 Mar 2010 21:18:26 +0000

Und wer räumt jetzt den Müll weg?


Gedankenlesen …

Thu, 18 Mar 2010 12:54:26 +0000

… geht momentan zwar noch nicht nachweislich, aber ich halte es für keine Utopie, dass die Hirnforschung irgendwann soweit kommen kann, Gedanken zu lesen und gezielt zu verändern. Lügendetektoren gibt es zum Beispiel schon lange. Und momentan experimentiert man mit der Steuerung von Bedienelementen durch Hirnströme.

Auf dieses Thema komme ich grade übrigens durch dieses Video, das ich zufällig entdeckt habe. Dort spielt jemand Pinball mit seinen Gedanken.

So faszinierend diese Techniken auch sein mögen, und so sehr ich auch normalerweise modernen Entwicklungen gegenüber positiv eingestellt bin, und zum Beispiel mit Gentechnik und Robotik höchstens moralische Probleme habe, so sehr erfüllt mich die Technologie die in die Richtung Gedankenkontrolle geht doch mit einer gewissen Angst.

Gentechnik führt dazu, dass Tiere zu Produktionsstätten degradiert werden, und dass sich Pflanzen verbreiten, deren langfristige Auswirkungen auf die Umwelt nicht absehbar sind – doch das sind moralische Bedenken. Ich selbst kann mich stets dafür einsetzen, dass man mit dem erlangten Wissen vorsichtig umgeht. Und bisher hat man das wenigstens nach ein paar millionen Toten dann letzten Endes immer getan.

Auch Robotik finde ich eher interessant – klar, man wird Menschen nach und nach ersetzen, und es ist durchaus denkbar, dass irgendwann ein Diktator sich eine Roboterarmee leisten kann (schon heute nutzt man kleine Roboter um an schwer zugängliche Stellen zu kommen) – aber auch hier kann man eine Opposition bilden, die notfalls ihre eigenen Roboter baut.

Doch wenn man die Gedanken eines Menschen kontrollieren kann, fällt jede Möglichkeit des Widerstandes weg. Denn sobald es möglich ist, einen Menschen neural so zu scannen, dass man bestimmte Gedanken und Verhaltensmuster erkennt, wird sicher irgendwer dies ebenfalls tun. Und wenn ich mir ansehe mit wie wenig Widerstand technische Entwicklungen wie Nacktscanner herapplaudiert werden, glaube ich auch kaum, dass sich rechtzeitig ein hinreichender Widerstand finden wird.

Nur um das mal zu veranschaulichen: Man stelle sich vor, morgen käme ein Bericht heraus, dass man eine Technik entwickelt hat, mit der man eindeutig die gesellschaftliche Gesinnung und die Persönlichkeit feststellen kann, und diese Technik ließe sich schön in einem Kasten verpacken, ohne großen Aufwandt – dann würde es mich übermorgen nicht wundern, wenn irgendein Politiker diese Technik an Flughäfen fordert, um festzustellen, welche Passagiere möglicherweise nicht Konform sind und daher zu Terroristen werden könnten. Immigranten würden grundsätzlich auf ihre Verfassungstreue überprüft. Auch die Forderung, die Sexualität von Lehrern zu überprüfen, würde wohl kommen. Es würde wohl früher oder später eine Diskussion losbrechen, ob man diese Technik zur Strafverfolgung verwenden darf, und ob sie als einziges Beweismittel ausreicht, und ob man präventiv jeden Mitbürger gezielt nach betreffenden Gedanken durchsuchen kann, um ihm gegebenenfalls psychologische Hilfe zu geben. Alles für unsere Sicherheit.

Es fiele eine weitere Konstante, auf die unser moralisches System sich so lange stützte, weg: Die Gedanken sind Frei.

Sobald man Gedanken kontrollieren kann, kann man alles kontrollieren – man kann jeden Freidenker eliminieren, bevor Dieser irgendetwas unternehmen kann, was einem schaden könnte.

Ich halte es für töricht, davon auszugehen, dass das niemals funktionieren wird – möglicherweise wird es niemals möglich sein, aber bisher deutet nichts darauf hin. Ich bezweifle aber auch, dass dies in Ansätzen nicht in den nächsten fünfzig Jahren möglich sein wird, ich glaube nicht, dass sich dieses Problem in die Zukunft verschieben lässt, die uns nicht mehr zu interessieren hat.

Eine solche Technik würde uns große und sinnvolle Möglichkeiten bieten. Vom Steuern komplexer Maschinen mittels Gedanken, bis hin zur Möglichkeit, gelähmten Menschen eine Möglichkeit zu geben sich wieder in der Welt zu bewegen, und selbst das Feststellen und Heilen bestimmter Gehirnkrankheiten würde ich mir davon erwarten. Umso wichtiger ist es, sich rechtzeitig Gedanken zu machen, wie die Gesellschaft damit umgehen sollte. In der Hand einer Gesellschaft wie der unsrigen will ich eine solche Technologie aber wirklich nicht sehen.


Software that should exist #5: Suspendable Processes

Tue, 16 Mar 2010 00:44:41 +0000

So far, most OSes support Suspend to Disk. That is, I can take a snapshot of the current state of my computer and restore it later. Thats a good thing, when having opened a lot of programs, which would have to be started again otherwise.

Some Software allows the suspension of itself, too. SBCL and many other Common Lisp Implementations have Coredumps which can be reloaded (in fact, under SBCL, this is the default way of creating an executable). But it would be nice to have this feature inside the OS itself, working for (mostly) all processes.

That is, I would like to be able to suspend a process and all its subprocesses while keeping anything else running, but also being able to shutdown my computer meanwhile.

This – of course – produces several problems. An application could have mmapped or opened some files. So, if the program has opened a file exclusively, i.e. doesnt expect the file to change, then the OS would have to notice that and keep the file locked, even through shutdowns. Of course, this shouldnt really become a problem, and if something fails – well, there can always be IO-Errors anyway.

Same for sockets and other IPC-Stuff. But on the other hand, when changing something on a whole suspended disk-image, then the problem is equal – except that then you can make your whole kernel crash.

That is – of course, the user isnt allowed to break the security mechanisms of the OS – and if he does, then its his fault.

Of course, you can already do something similar – namely use usermode linux or some light virtualization. But having this for all processes would be better and easier.

Update: I seem not to be the only person thinking this. There is a project called CryoPID. Thank you for your comment, Leslie.