withMulklib.c

   1 #include <stdio.h>
   2 #include <signal.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <udis86.h>
   7 #include <sys/mman.h>
   8 #include <errno.h>
   9 #include "bitmapped_patricia_tree.h"
  10 #define __USE_GNU
  11 #include <ucontext.h>
  12
  13 #include "lists.h"
  14
  15 /* This code is only for x86_64 gcc linux. It is NOT threadsafe. */
  16
  17 void* slice_alloc (size_t length) {
  18   static intptr_t *nextslice = NULL + 1;
  19   static intptr_t *lastslice = NULL;
  20
  21   int num = length / sizeof(intptr_t) + 1;
  22
  23   if (lastslice < nextslice + num) {
  24     nextslice = (intptr_t *)malloc(1024*sizeof(intptr_t));
  25     lastslice = nextslice + 1023;
  26   }
  27
  28   void* ret = (void*) nextslice;
  29   nextslice += num;
  30   return ret;
  31 }
  32
  33 /* w00t, I am a three-star-programmer! */
  34 void ***dereferencedPointer;
  35 void ***lastDereferencedPointer;
  36 void **lockedPointer;
  37 void **lastLockedPointer;
  38
  39 typedef struct {
  40   void* (*function) (void*);
  41   void* argument;
  42   void*** dereferencedPointer;
  43 } tree_entry;
  44
  45 bpt_t pointer_tree;
  46
  47 bpt_t bpt_assoc_and_release(bpt_t bpt, bpt_key_t key, void *value) {
  48   bpt_t new_bpt = bpt_assoc(bpt, key, value);
  49   bpt_release(bpt);
  50   return new_bpt;
  51 }
  52
  53 void maybeAllocateMorePointers () {
  54   if (lastDereferencedPointer > dereferencedPointer) {
  55     lockedPointer = (void**) mmap(NULL,
  56                                   sysconf(_SC_PAGE_SIZE)*sizeof(void*),
  57                                   PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE,
  58                                   -1, 0);
  59     dereferencedPointer = (void***) mmap(NULL,
  60                                          sysconf(_SC_PAGE_SIZE)*sizeof(void**),
  61                                          PROT_READ | PROT_WRITE,
  62                                          MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
  63
  64     if ((dereferencedPointer == MAP_FAILED)) {
  65       printf("Mmap failed 2!\n");
  66       if ((lockedPointer == MAP_FAILED)) {
  67         printf("Mmap failed 1!\n");
  68         exit(-1);
  69       }
  70       exit(-1);
  71     }
  72
  73     lastLockedPointer = lockedPointer + sysconf(_SC_PAGE_SIZE);
  74     lastDereferencedPointer = dereferencedPointer + sysconf(_SC_PAGE_SIZE);
  75
  76     void** lp = lockedPointer;
  77     void*** dp = dereferencedPointer;
  78     while (lp < lastLockedPointer) {
  79       *dp = lp;
  80       lp++; dp++;
  81     }
  82   }
  83 }
  84
  85 inline void initializePointerTree () {
  86   pointer_tree = NULL;
  87   dereferencedPointer = NULL + 2;
  88   lastDereferencedPointer = 1 + dereferencedPointer;
  89   maybeAllocateMorePointers ();
  90 }
  91
  92 void*** lazy_alloc (void* (*calculate) (void*), void* opt) {
  93   maybeAllocateMorePointers ();
  94   void*** ret = dereferencedPointer;
  95
  96   lockedPointer++;
  97   dereferencedPointer++;
  98
  99   tree_entry *en = (tree_entry*) slice_alloc (sizeof(tree_entry));
 100   en->function = calculate;
 101   en->argument = opt;
 102   en->dereferencedPointer = ret;
 103
 104
 105   pointer_tree = bpt_assoc_and_release(pointer_tree, (intptr_t) *ret,
 106                                        (void*) en);
 107   return ret;
 108 }
 109
 110 void initializeSignalHandler();
 111
 112 void handle_segv(int segv, siginfo_t* siginfo, void* ucontext) {
 113   ucontext_t* uc = (ucontext_t*) ucontext;
 114
 115   /* do disassembly at from IP */
 116   ud_t ud_obj;
 117   ud_init(&ud_obj);
 118   ud_set_mode(&ud_obj, 64);
 119   ud_set_syntax(&ud_obj, UD_SYN_ATT);
 120   ud_set_input_buffer(&ud_obj, (unsigned char*) uc->uc_mcontext.gregs[REG_RIP],
 121                       10);
 122
 123   /* was disassembly successful? */
 124   if (!ud_disassemble(&ud_obj)) {
 125     printf("Disassembly fail!\n");
 126     exit(-1);
 127   }
 128
 129   /* is disassembly a memory-operation? */
 130   struct ud_operand op0 = ud_obj.operand[0];
 131   struct ud_operand op1 = ud_obj.operand[1];
 132   struct ud_operand op;
 133
 134   if (op0.type == UD_OP_MEM) {
 135     op = op0;
 136   } else if (op1.type == UD_OP_MEM) {
 137     op = op1;
 138   } else {
 139     printf("Instruction unknown\n");
 140     exit(-1);
 141   }
 142
 143   /* find out the register - this part is clumsy as we have two sets
 144      of constants */
 145
 146   int setreg;
 147   switch (op.base) {
 148   case UD_R_RAX:
 149   case UD_R_EAX:
 150     setreg = REG_RAX;
 151     break;
 152   case UD_R_RCX:
 153   case UD_R_ECX:
 154     setreg = REG_RCX;
 155     break;
 156   case UD_R_RDX:
 157   case UD_R_EDX:
 158     setreg = REG_RDX;
 159     break;
 160   case UD_R_RBX:
 161   case UD_R_EBX:
 162     setreg = REG_RBX;
 163     break;
 164   case UD_R_RSP:
 165   case UD_R_ESP:
 166     setreg = REG_RSP;
 167     break;
 168   case UD_R_RBP:
 169   case UD_R_EBP:
 170     setreg = REG_RBP;
 171     break;
 172   case UD_R_RSI:
 173   case UD_R_ESI:
 174     setreg = REG_RSI;
 175     break;
 176   case UD_R_RDI:
 177   case UD_R_EDI:
 178     setreg = REG_RDI;
 179     break;
 180   case UD_R_R8:
 181   case UD_R_R8D:
 182     setreg = REG_R8;
 183     break;
 184   case UD_R_R9:
 185   case UD_R_R9D:
 186     setreg = REG_R9;
 187     break;
 188   case UD_R_R10:
 189   case UD_R_R10D:
 190     setreg = REG_R10;
 191     break;
 192   case UD_R_R11:
 193   case UD_R_R11D:
 194     setreg = REG_R11;
 195     break;
 196   case UD_R_R12:
 197   case UD_R_R12D:
 198     setreg = REG_R12;
 199     break;
 200   case UD_R_R13:
 201   case UD_R_R13D:
 202     setreg = REG_R13;
 203     break;
 204   case UD_R_R14:
 205   case UD_R_R14D:
 206     setreg = REG_R14;
 207     break;
 208   case UD_R_R15:
 209   case UD_R_R15D:
 210     setreg = REG_R15;
 211     break;
 212   default:
 213     printf("Register not supported!\n");
 214     exit(-1);
 215   }
 216
 217   intptr_t address = uc->uc_mcontext.gregs[setreg];
 218
 219   if (!bpt_has_key(pointer_tree, address)) {
 220     printf("Address not found in Patricia tree: %d.\n", address);
 221     exit(-1);
 222   }
 223
 224   tree_entry *te = (tree_entry*) bpt_get(pointer_tree, address);
 225   void* newAddress = (te->function)(te->argument);
 226   *(te->dereferencedPointer) = newAddress;
 227
 228   /* set the register - as before */
 229   uc->uc_mcontext.gregs[setreg] = (greg_t) newAddress;
 230 }
 231
 232 inline void initializeSignalHandler () {
 233   struct sigaction q;
 234   bzero(&q, sizeof(q));
 235   q.sa_sigaction = handle_segv;
 236   q.sa_flags = SA_SIGINFO | SA_NODEFER;
 237   sigaction(11, &q, NULL);
 238 }
 239
 240 typedef struct {
 241   int i;
 242   int (*fun) (int, list);
 243   list initial;
 244 } listComprehensionRecursorR;
 245
 246 void * listComprehensionRecursor (void* x) {
 247   listComprehensionRecursorR* lcr = (listComprehensionRecursorR*) x;
 248   int value = (lcr->fun)(lcr->i, lcr->initial);
 249   lcr->i++;
 250
 251   list cdr = (list) lazy_alloc(listComprehensionRecursor, (void*)lcr);
 252   cons * ret = (cons*) slice_alloc(sizeof(cons));
 253   doCons(value, cdr, ret);
 254   return (void*) ret;
 255 }
 256
 257 list listComprehension (int (*fun) (int, list)) {
 258   listComprehensionRecursorR* lcr =
 259     (listComprehensionRecursorR*) slice_alloc
 260     (sizeof(listComprehensionRecursorR));
 261   lcr->i = 0;
 262   lcr->fun=fun;
 263   lcr->initial = (list) lazy_alloc(listComprehensionRecursor, (void*)lcr);
 264   return lcr->initial;
 265 }
 266
 267 int fib (int x, list l) {
 268   return x == 0 ? 0 : (x == 1 ? 1 : elt(l, x-1) + elt(l, x-2));
 269 }
 270
 271 int main (void) {
 272   initializePointerTree ();
 273   initializeSignalHandler ();
 274   list lst = listComprehension(fib);
 275   int i;
 276   for (i = 0; i < 10; i++)
 277     printf("%d\n", elt(lst, i));
 278 }