9 #include "bitmapped_patricia_tree.h"
15 /* This code is only for x86_64 gcc linux. It is NOT threadsafe. */
17 void* slice_alloc (size_t length) {
18 static intptr_t *nextslice = NULL + 1;
19 static intptr_t *lastslice = NULL;
21 int num = length / sizeof(intptr_t) + 1;
23 if (lastslice < nextslice + num) {
24 nextslice = (intptr_t *)malloc(1024*sizeof(intptr_t));
25 lastslice = nextslice + 1023;
28 void* ret = (void*) nextslice;
33 /* w00t, I am a three-star-programmer! */
34 void ***dereferencedPointer;
35 void ***lastDereferencedPointer;
37 void **lastLockedPointer;
40 void* (*function) (void*);
42 void*** dereferencedPointer;
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);
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,
59 dereferencedPointer = (void***) mmap(NULL,
60 sysconf(_SC_PAGE_SIZE)*sizeof(void**),
61 PROT_READ | PROT_WRITE,
62 MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
64 if ((dereferencedPointer == MAP_FAILED)) {
65 printf("Mmap failed 2!\n");
66 if ((lockedPointer == MAP_FAILED)) {
67 printf("Mmap failed 1!\n");
73 lastLockedPointer = lockedPointer + sysconf(_SC_PAGE_SIZE);
74 lastDereferencedPointer = dereferencedPointer + sysconf(_SC_PAGE_SIZE);
76 void** lp = lockedPointer;
77 void*** dp = dereferencedPointer;
78 while (lp < lastLockedPointer) {
85 inline void initializePointerTree () {
87 dereferencedPointer = NULL + 2;
88 lastDereferencedPointer = 1 + dereferencedPointer;
89 maybeAllocateMorePointers ();
92 void*** lazy_alloc (void* (*calculate) (void*), void* opt) {
93 maybeAllocateMorePointers ();
94 void*** ret = dereferencedPointer;
97 dereferencedPointer++;
99 tree_entry *en = (tree_entry*) slice_alloc (sizeof(tree_entry));
100 en->function = calculate;
102 en->dereferencedPointer = ret;
105 pointer_tree = bpt_assoc_and_release(pointer_tree, (intptr_t) *ret,
110 void initializeSignalHandler();
112 void handle_segv(int segv, siginfo_t* siginfo, void* ucontext) {
113 ucontext_t* uc = (ucontext_t*) ucontext;
115 /* do disassembly at from IP */
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],
123 /* was disassembly successful? */
124 if (!ud_disassemble(&ud_obj)) {
125 printf("Disassembly fail!\n");
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;
134 if (op0.type == UD_OP_MEM) {
136 } else if (op1.type == UD_OP_MEM) {
139 printf("Instruction unknown\n");
143 /* find out the register - this part is clumsy as we have two sets
213 printf("Register not supported!\n");
217 intptr_t address = uc->uc_mcontext.gregs[setreg];
219 if (!bpt_has_key(pointer_tree, address)) {
220 printf("Address not found in Patricia tree: %d.\n", address);
224 tree_entry *te = (tree_entry*) bpt_get(pointer_tree, address);
225 void* newAddress = (te->function)(te->argument);
226 *(te->dereferencedPointer) = newAddress;
228 /* set the register - as before */
229 uc->uc_mcontext.gregs[setreg] = (greg_t) newAddress;
232 inline void initializeSignalHandler () {
234 bzero(&q, sizeof(q));
235 q.sa_sigaction = handle_segv;
236 q.sa_flags = SA_SIGINFO | SA_NODEFER;
237 sigaction(11, &q, NULL);
242 int (*fun) (int, list);
244 } listComprehensionRecursorR;
246 void * listComprehensionRecursor (void* x) {
247 listComprehensionRecursorR* lcr = (listComprehensionRecursorR*) x;
248 int value = (lcr->fun)(lcr->i, lcr->initial);
251 list cdr = (list) lazy_alloc(listComprehensionRecursor, (void*)lcr);
252 cons * ret = (cons*) slice_alloc(sizeof(cons));
253 doCons(value, cdr, ret);
257 list listComprehension (int (*fun) (int, list)) {
258 listComprehensionRecursorR* lcr =
259 (listComprehensionRecursorR*) slice_alloc
260 (sizeof(listComprehensionRecursorR));
263 lcr->initial = (list) lazy_alloc(listComprehensionRecursor, (void*)lcr);
267 int fib (int x, list l) {
268 return x == 0 ? 0 : (x == 1 ? 1 : elt(l, x-1) + elt(l, x-2));
272 initializePointerTree ();
273 initializeSignalHandler ();
274 list lst = listComprehension(fib);
276 for (i = 0; i < 10; i++)
277 printf("%d\n", elt(lst, i));