Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI_RT / src / RTlinux.c
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 /************************************************************************
33  * $Id: RTlinux.c,v 1.54 2008/04/11 23:30:44 legendre Exp $
34  * RTlinux.c: mutatee-side library function specific to Linux
35  ************************************************************************/
36
37 #include "dyninstAPI_RT/h/dyninstAPI_RT.h"
38 #include "dyninstAPI_RT/src/RTthread.h"
39 #include "dyninstAPI_RT/src/RTcommon.h"
40 #include <assert.h>
41 #include <stdio.h>
42 #include <errno.h>
43 #include <unistd.h>
44 #include <dlfcn.h>
45 #include <sys/types.h>
46 #include <sys/syscall.h>
47 #include <string.h>
48 #include <errno.h>
49 #include <signal.h>
50 #include <sys/mman.h>
51 #include <link.h>
52 #include <pthread.h>
53
54 extern double DYNINSTstaticHeap_512K_lowmemHeap_1[];
55 extern double DYNINSTstaticHeap_16M_anyHeap_1[];
56 extern unsigned long sizeOfLowMemHeap1;
57 extern unsigned long sizeOfAnyHeap1;
58
59 static struct trap_mapping_header *getStaticTrapMap(unsigned long addr);
60
61 #if defined(arch_power) && defined(arch_64bit) && defined(os_linux)
62 unsigned long DYNINSTlinkSave;
63 unsigned long DYNINSTtocSave;
64 #endif
65
66 /************************************************************************
67  * void DYNINSTbreakPoint(void)
68  *
69  * stop oneself.
70 ************************************************************************/
71
72 void DYNINSTbreakPoint()
73 {
74    /* We set a global flag here so that we can tell
75       if we're ever in a call to this when we get a 
76       SIGBUS */
77    if (DYNINSTstaticMode)
78       return;
79
80    DYNINST_break_point_event = 1;
81    while (DYNINST_break_point_event)  {
82       kill(dyn_lwp_self(), DYNINST_BREAKPOINT_SIGNUM);
83    }
84    /* Mutator resets to 0... */
85 }
86
87 static int failed_breakpoint = 0;
88 void uncaught_breakpoint(int sig)
89 {
90    failed_breakpoint = 1;
91 }
92
93 void DYNINSTlinuxBreakPoint()
94 {
95    struct sigaction act, oldact;
96    int result;
97    
98    if (DYNINSTstaticMode)
99       return;
100
101    memset(&oldact, 0, sizeof(struct sigaction));
102    memset(&act, 0, sizeof(struct sigaction));
103
104    result = sigaction(DYNINST_BREAKPOINT_SIGNUM, NULL, &act);
105    if (result == -1) {
106       perror("DyninstRT library failed sigaction1");
107       return;
108    }
109    act.sa_handler = uncaught_breakpoint;
110
111    result = sigaction(DYNINST_BREAKPOINT_SIGNUM, &act, &oldact);
112    if (result == -1) {
113       perror("DyninstRT library failed sigaction2");
114       return;
115    }
116
117    DYNINST_break_point_event = 1;
118    failed_breakpoint = 0;
119    kill(dyn_lwp_self(), DYNINST_BREAKPOINT_SIGNUM);
120    if (failed_breakpoint) {
121       DYNINST_break_point_event = 0;
122       failed_breakpoint = 0;
123    }
124
125    result = sigaction(DYNINST_BREAKPOINT_SIGNUM, &oldact, NULL);
126    if (result == -1) {
127       perror("DyninstRT library failed sigaction3");
128       return;
129    }
130 }
131
132 void DYNINSTsafeBreakPoint()
133 {
134    if (DYNINSTstaticMode)
135       return;
136
137     DYNINST_break_point_event = 2; /* Not the same as above */
138     //    while (DYNINST_break_point_event)
139         kill(dyn_lwp_self(), SIGSTOP);
140 }
141
142 void mark_heaps_exec() {
143         RTprintf( "*** Initializing dyninstAPI runtime.\n" );
144
145         /* Grab the page size, to align the heap pointer. */
146         long int pageSize = sysconf( _SC_PAGESIZE );
147         if( pageSize == 0 || pageSize == - 1 ) {
148                 fprintf( stderr, "*** Failed to obtain page size, guessing 16K.\n" );
149                 perror( "mark_heaps_exec" );
150                 pageSize = 1024 * 16;
151                 } /* end pageSize initialization */
152
153         /* Align the heap pointer. */
154         unsigned long int alignedHeapPointer = (unsigned long int) DYNINSTstaticHeap_16M_anyHeap_1;
155         alignedHeapPointer = (alignedHeapPointer) & ~(pageSize - 1);
156         unsigned long int adjustedSize = (unsigned long int) DYNINSTstaticHeap_16M_anyHeap_1 - alignedHeapPointer + sizeOfAnyHeap1;
157
158         /* Make the heap's page executable. */
159         int result = mprotect( (void *) alignedHeapPointer, (size_t) adjustedSize, PROT_READ | PROT_WRITE | PROT_EXEC );
160         if( result != 0 ) {
161                 fprintf( stderr, "%s[%d]: Couldn't make DYNINSTstaticHeap_16M_anyHeap_1 executable!\n", __FILE__, __LINE__);
162                 perror( "mark_heaps_exec" );
163                 }
164         RTprintf( "*** Marked memory from 0x%lx to 0x%lx executable.\n", alignedHeapPointer, alignedHeapPointer + adjustedSize );
165
166         /* Mark _both_ heaps executable. */
167         alignedHeapPointer = (unsigned long int) DYNINSTstaticHeap_512K_lowmemHeap_1;
168         alignedHeapPointer = (alignedHeapPointer) & ~(pageSize - 1);
169         adjustedSize = (unsigned long int) DYNINSTstaticHeap_512K_lowmemHeap_1 - alignedHeapPointer + sizeOfLowMemHeap1;
170
171         /* Make the heap's page executable. */
172         result = mprotect( (void *) alignedHeapPointer, (size_t) adjustedSize, PROT_READ | PROT_WRITE | PROT_EXEC );
173         if( result != 0 ) {
174                 fprintf( stderr, "%s[%d]: Couldn't make DYNINSTstaticHeap_512K_lowmemHeap_1 executable!\n", __FILE__, __LINE__ );
175                 perror( "mark_heaps_exec" );
176                 }
177         RTprintf( "*** Marked memory from 0x%lx to 0x%lx executable.\n", alignedHeapPointer, alignedHeapPointer + adjustedSize );
178         } /* end mark_heaps_exec() */
179
180 #if defined(arch_ia64)
181 /* Ensure we an executable block of memory. */
182 void R_BRK_TARGET() {
183         /* Make sure we've got room for two bundles. */
184         asm( "nop 0" ); asm( "nop 0" ); asm( "nop 0" );
185         asm( "nop 0" ); asm( "nop 0" ); asm( "nop 0" );
186         }
187 #endif /*arch_ia64*/
188
189 /************************************************************************
190  * void DYNINSTos_init(void)
191  *
192  * OS initialization function
193 ************************************************************************/
194 int DYNINST_sysEntry;
195 void DYNINSTos_init(int calledByFork, int calledByAttach)
196 {
197    RTprintf("DYNINSTos_init(%d,%d)\n", calledByFork, calledByAttach);
198 #if defined(arch_x86)
199    /**
200     * The following line reads the vsyscall entry point directly from
201     * it's stored, which can then be used by the mutator to locate
202     * the vsyscall page.
203     * The problem is, I don't know if this memory read is valid on
204     * older systems--It could cause a segfault.  I'm going to leave
205     * it commented out for now, until further investigation.
206     * -Matt 1/18/06
207     **/
208    //__asm("movl %%gs:0x10, %%eax\n" : "=r" (DYNINST_sysEntry))
209 #endif
210 }
211
212 typedef struct dlopen_args {
213   const char *libname;
214   int mode;
215   void *result;
216   void *caller;
217 } dlopen_args_t;
218
219 void *(*DYNINST_do_dlopen)(dlopen_args_t *) = NULL;
220
221 static int get_dlopen_error() {
222    char *err_str;
223    err_str = dlerror();
224    if (err_str) {
225       strncpy(gLoadLibraryErrorString, err_str, (size_t) ERROR_STRING_LENGTH);
226       return 1;
227    }
228    else {
229       sprintf(gLoadLibraryErrorString,"unknown error with dlopen");
230       return 0;
231    }
232    return 0;
233 }
234
235 int DYNINSTloadLibrary(char *libname)
236 {
237    void *res;
238    gLoadLibraryErrorString[0]='\0';
239    res = dlopen(libname, RTLD_NOW | RTLD_GLOBAL);
240    if (res)
241    {
242       return 1;
243    }
244  
245    get_dlopen_error();
246 #if defined(arch_x86)
247    /* dlopen on recent glibcs has a "security check" so that
248       only registered modules can call it. Unfortunately, progs
249       that don't include libdl break this check, so that we
250       can only call _dl_open (the dlopen worker function) from
251       within glibc. We do this by calling do_dlopen
252       We fool this check by calling an addr written by the
253       mutator */
254    if (strstr(gLoadLibraryErrorString, "invalid caller") != NULL &&
255        DYNINST_do_dlopen != NULL) {
256       dlopen_args_t args;
257       args.libname = libname;
258       args.mode = RTLD_NOW | RTLD_GLOBAL;
259       args.result = 0;
260       args.caller = (void *)DYNINST_do_dlopen;
261       // There's a do_dlopen function in glibc. However, it's _not_
262       // exported; thus, getting the address is a bit of a pain. 
263       
264       (*DYNINST_do_dlopen)(&args);
265       // Duplicate the above
266       if (args.result != NULL)
267       {
268          return 1;
269       }
270       else
271          get_dlopen_error();
272    }
273 #endif
274    return 0;
275 }
276
277 //Define this value so that we can compile on a system that doesn't have
278 // gettid and still run on one that does.
279 #if !defined(SYS_gettid)
280
281 #if defined(arch_x86)
282 #define SYS_gettid 224
283 #elif defined(arch_x86_64)
284 #define SYS_gettid 186
285 #elif defined(arch_ia64)
286 #define SYS_gettid 1105
287 #endif
288
289 #endif
290
291 int dyn_lwp_self()
292 {
293    static int gettid_not_valid = 0;
294    int result;
295
296    if (gettid_not_valid)
297       return getpid();
298
299    result = syscall((long int) SYS_gettid);
300    if (result == -1 && errno == ENOSYS)
301    {
302       gettid_not_valid = 1;
303       return getpid();
304    }
305    return result;  
306 }
307
308 int dyn_pid_self()
309 {
310    return getpid();
311 }
312
313 dyntid_t (*DYNINST_pthread_self)(void);
314
315 dyntid_t dyn_pthread_self()
316 {
317    dyntid_t me;
318    if (DYNINSTstaticMode) {
319       return (dyntid_t) pthread_self();
320    }
321    if (!DYNINST_pthread_self) {
322       return (dyntid_t) DYNINST_SINGLETHREADED;
323    }
324    me = (*DYNINST_pthread_self)();
325    return (dyntid_t) me;
326 }
327
328 /* 
329    We reserve index 0 for the initial thread. This value varies by
330    platform but is always constant for that platform. Wrap that
331    platform-ness here. 
332 */
333 int DYNINST_am_initial_thread( dyntid_t tid ) {
334         if( dyn_lwp_self() == getpid() ) {
335                 return 1;
336    }
337         return 0;
338 } /* end DYNINST_am_initial_thread() */
339
340 /**
341  * We need to extract certain pieces of information from the usually opaque 
342  * type pthread_t.  Unfortunately, libc doesn't export this information so 
343  * we're reverse engineering it out of pthread_t.  The following structure
344  * tells us at what offsets it look off of the return value of pthread_self
345  * for the lwp, pid, initial start function (the one passed to pthread_create)
346  * and the top of this thread's stack.  We have multiple entries in positions, 
347  * one for each different version of libc we've seen.
348  **/
349 #define READ_FROM_BUF(pos, type) *((type *)(buffer+pos))
350
351 typedef struct pthread_offset_t
352 {
353    unsigned lwp_pos;
354    unsigned pid_pos;
355    unsigned start_func_pos;
356    unsigned stck_start_pos;
357 } pthread_offset_t;
358
359 #if defined(arch_x86_64) && defined(MUTATEE_32)
360 //x86_64 32 bit mode
361 #define POS_ENTRIES 4
362 static pthread_offset_t positions[POS_ENTRIES] = { { 72, 476, 516, 576 },
363                                                    { 72, 76, 516, 84 },
364                                                    { 72, 476, 516, 80 },
365                                                    { 72, 76, 532, 96} }; 
366
367 #elif defined(arch_x86_64) || defined(arch_ia64)
368 //x86_64 and ia64 share structrues
369 #define POS_ENTRIES 4
370 static pthread_offset_t positions[POS_ENTRIES] = { { 144, 952, 1008, 160 },
371                                                    { 144, 148, 1000, 160 },
372                                                    { 144, 148, 1000, 688 },
373                                                    { 144, 148, 1024, 192 } };
374
375 #elif defined(arch_x86)
376 //x86 32
377 #define POS_ENTRIES 4
378 static pthread_offset_t positions[POS_ENTRIES] = { { 72, 476, 516, 576 },
379                                                    { 72, 76, 516, 84 },
380                                                    { 72, 76, 532, 592 },
381                                                    { 72, 476, 516, 80 } };
382
383 #elif defined(arch_power)
384 //Power
385 #define POS_ENTRIES 3
386 static pthread_offset_t positions[POS_ENTRIES] = { { 72, 76, 508, 576 },
387                                                    { 144, 148, 992, 160 }, // PPC64
388                                                    { 144, 148, 992, 1072 } };
389 #else
390 #error Need to define thread structures here
391 #endif
392
393 int DYNINSTthreadInfo(BPatch_newThreadEventRecord *ev)
394 {
395    static int err_printed = 0;
396    int i;
397    char *buffer;
398
399    ev->stack_addr = 0x0;
400    ev->start_pc = 0x0;
401    buffer = (char *) ev->tid;
402
403    for (i = 0; i < POS_ENTRIES; i++)
404    {
405       pid_t pid = READ_FROM_BUF(positions[i].pid_pos, pid_t);
406       int lwp = READ_FROM_BUF(positions[i].lwp_pos, int);
407
408       if( pid != ev->ppid || lwp != ev->lwp ) {
409          continue;
410       }
411
412       void *stack_addr;
413 #if defined(arch_x86_64) && defined(MUTATEE_32)
414       asm("movl %%esp,%0" : "=r" (stack_addr));
415 #elif defined(arch_x86_64)
416       asm("mov %%rsp,%0" : "=r" (stack_addr));
417 #elif defined(arch_x86)
418       asm("movl %%esp,%0" : "=r" (stack_addr));
419 #else
420       stack_addr = READ_FROM_BUF(positions[i].stck_start_pos, void *);
421 #endif
422       void *start_pc = READ_FROM_BUF(positions[i].start_func_pos, void *);
423
424 #if defined(arch_power)
425       /* 64-bit POWER architectures also use function descriptors instead of directly
426        * pointing at the function code.  Find the actual address of the function.
427        *
428        * Actually, a process can't read its own OPD section.  Punt for now, but remember
429        * that we're storing the function descriptor address, not the actual function address!
430        */
431       //uint64_t actualAddr = *((uint64_t *)start_pc);
432       //fprintf(stderr, "*** Redirecting start_pc from 0x%lx to 0x%lx\n", start_pc, actualAddr);
433       //start_pc = (void *)actualAddr;
434 #endif
435
436       // Sanity checking. There are multiple different places that we have
437       // found the stack address for a given pair of pid/lwpid locations,
438       // so we need to do the best job we can of verifying that we've
439       // identified the real stack. 
440       //
441       // Currently we just check for known incorrect values. We should
442       // generalize this to check for whether the address is in a valid
443       // memory region, but it is not clear whether that information is
444       // available at this point.
445       //        
446       if(stack_addr == (void*)0 || stack_addr == (void*)0xffffffec) {
447          continue;
448       }
449
450       ev->stack_addr = stack_addr;
451       ev->start_pc = start_pc;
452
453       return 1;
454    }
455
456    if (!err_printed)
457    {
458       //If you get this error, then Dyninst is having trouble figuring out
459       //how to read the information from the positions structure above.
460       //It needs a new entry filled in.  Running the commented out program
461       //at the end of this file can help you collect the necessary data.
462       RTprintf( "[%s:%d] Unable to parse the pthread_t structure for this version of libpthread.  Making a best guess effort.\n",  __FILE__, __LINE__ );
463       err_printed = 1;
464    }
465    
466    return 1;
467 }
468
469 #if defined(cap_mutatee_traps)
470
471 #include <ucontext.h>
472
473 #if defined(arch_x86) || defined(MUTATEE_32)
474
475 #if !defined(REG_EIP)
476 #define REG_EIP 14
477 #endif
478 #if !defined(REG_ESP)
479 #define REG_ESP 7
480 #endif
481 #define REG_IP REG_EIP
482 #define REG_SP REG_ESP
483 #define MAX_REG 18
484
485 #elif defined(arch_x86_64)
486
487 #if !defined(REG_RIP)
488 #define REG_RIP 16
489 #endif
490 #if !defined(REG_RSP)
491 #define REG_RSP 15
492 #endif
493 #define REG_IP REG_RIP
494 #define REG_SP REG_RSP
495 #define MAX_REG 15
496 #if !defined(REG_RAX)
497 #define REG_RAX 13
498 #endif
499 #if !defined(REG_R10)
500 #define REG_R10 2
501 #endif
502 #if !defined(REG_R11)
503 #define REG_R11 3
504 #endif
505
506 #endif
507
508 extern void dyninstSetupContext(ucontext_t *context, unsigned long flags, void *retPoint);
509 extern unsigned long dyninstTrapTableUsed;
510 extern unsigned long dyninstTrapTableVersion;
511 extern trapMapping_t *dyninstTrapTable;
512 extern unsigned long dyninstTrapTableIsSorted;
513
514 /**
515  * Called by the SIGTRAP handler, dyninstTrapHandler.  This function is 
516  * closly intwined with dyninstTrapHandler, don't modify one without 
517  * understanding the other.
518  *
519  * This function sets up the calling context that was passed to the
520  * SIGTRAP handler so that control will be redirected to our instrumentation
521  * when we do the setcontext call.
522  * 
523  * There are a couple things that make this more difficult than it should be:
524  *   1. The OS provided calling context is similar to the GLIBC calling context,
525  *      but not compatible.  We'll create a new GLIBC compatible context and
526  *      copy the possibly stomped registers from the OS context into it.  The
527  *      incompatiblities seem to deal with FP and other special purpose registers.
528  *   2. setcontext doesn't restore the flags register.  Thus dyninstTrapHandler
529  *      will save the flags register first thing and pass us its value in the
530  *      flags parameter.  We'll then push the instrumentation entry and flags
531  *      onto the context's stack.  Instead of transfering control straight to the
532  *      instrumentation, we'll actually go back to dyninstTrapHandler, which will
533  *      do a popf/ret to restore flags and go to instrumentation.  The 'retPoint'
534  *      parameter is the address in dyninstTrapHandler the popf/ret can be found.
535  **/
536 void dyninstSetupContext(ucontext_t *context, unsigned long flags, void *retPoint)
537 {
538    ucontext_t newcontext;
539    unsigned i;
540    unsigned long *orig_sp;
541    void *orig_ip;
542    void *trap_to;
543
544    getcontext(&newcontext);
545    
546    //Set up the 'context' parameter so that when we restore 'context' control
547    // will get transfered to our instrumentation.
548    for (i=0; i<MAX_REG; i++) {
549       newcontext.uc_mcontext.gregs[i] = context->uc_mcontext.gregs[i];
550    }
551
552    orig_sp = (unsigned long *) context->uc_mcontext.gregs[REG_SP];
553    orig_ip = (void *) context->uc_mcontext.gregs[REG_IP];
554
555    assert(orig_ip);
556
557    //Set up the PC to go to the 'ret_point' in RTsignal-x86.s
558    newcontext.uc_mcontext.gregs[REG_IP] = (unsigned long) retPoint;
559
560    //simulate a "push" of the flags and instrumentation entry points onto
561    // the stack.
562    if (DYNINSTstaticMode) {
563       unsigned long zero = 0;
564       unsigned long one = 1;
565       struct trap_mapping_header *hdr = getStaticTrapMap((unsigned long) orig_ip);
566       trapMapping_t *mapping = &(hdr->traps[0]);
567       assert(hdr);
568       trap_to = dyninstTrapTranslate(orig_ip, 
569                                      (unsigned long *) &hdr->num_entries, 
570                                      &zero, 
571                                      (volatile trapMapping_t **) &mapping,
572                                      &one);
573    }
574    else {
575       trap_to = dyninstTrapTranslate(orig_ip, 
576                                      &dyninstTrapTableUsed,
577                                      &dyninstTrapTableVersion,
578                                      (volatile trapMapping_t **) &dyninstTrapTable,
579                                      &dyninstTrapTableIsSorted);
580                                      
581    }
582    *(orig_sp - 1) = (unsigned long) trap_to;
583    *(orig_sp - 2) = flags;
584    unsigned shift = 2;
585 #if defined(arch_x86_64) && !defined(MUTATEE_32)
586    *(orig_sp - 3) = context->uc_mcontext.gregs[REG_R11];
587    *(orig_sp - 4) = context->uc_mcontext.gregs[REG_R10];
588    *(orig_sp - 5) = context->uc_mcontext.gregs[REG_RAX];
589    shift = 5;
590 #endif
591    newcontext.uc_mcontext.gregs[REG_SP] = (unsigned long) (orig_sp - shift);
592
593    //Restore the context.  This will move all the register values of 
594    // context into the actual registers and transfer control away from
595    // this function.  This function shouldn't actually return.
596    setcontext(&newcontext);
597    assert(0);
598 }
599
600 #if defined(cap_binary_rewriter)
601
602 extern struct r_debug _r_debug;
603 struct r_debug _r_debug __attribute__ ((weak));
604
605 #define NUM_LIBRARIES 512 //Important, max number of rewritten libraries
606
607 #define WORD_SIZE (8 * sizeof(unsigned))
608 #define NUM_LIBRARIES_BITMASK_SIZE (1 + NUM_LIBRARIES / WORD_SIZE)
609 struct trap_mapping_header *all_headers[NUM_LIBRARIES];
610
611 static unsigned all_headers_current[NUM_LIBRARIES_BITMASK_SIZE];
612 static unsigned all_headers_last[NUM_LIBRARIES_BITMASK_SIZE];
613
614 #if !defined(arch_x86_64) || defined(MUTATEE_32)
615 typedef Elf32_Dyn ElfX_Dyn;
616 #else
617 typedef Elf64_Dyn ElfX_Dyn;
618 #endif
619
620 struct trap_mapping_header *getStaticTrapMap(unsigned long addr);
621
622 static int parse_libs();
623 static int parse_link_map(struct link_map *l);
624 static void clear_unloaded_libs();
625
626 static void set_bit(unsigned *bit_mask, int bit, char value);
627 //static char get_bit(unsigned *bit_mask, int bit);
628 static void clear_bitmask(unsigned *bit_mask);
629 static unsigned get_next_free_bitmask(unsigned *bit_mask, int last_pos);
630 static unsigned get_next_set_bitmask(unsigned *bit_mask, int last_pos);
631
632 static tc_lock_t trap_mapping_lock;
633
634 static struct trap_mapping_header *getStaticTrapMap(unsigned long addr)
635 {
636    struct trap_mapping_header *header;
637    int i;
638    
639    tc_lock_lock(&trap_mapping_lock);
640    parse_libs();
641
642    i = -1;
643    for (;;) {
644       i = get_next_set_bitmask(all_headers_current, i);
645       assert(i >= 0 && i <= NUM_LIBRARIES);
646       if (i == NUM_LIBRARIES) {
647          header = NULL;
648          goto done;
649       }
650       header = all_headers[i];
651       if (addr >= header->low_entry && addr <= header->high_entry) {
652          goto done;
653       }
654    }  
655  done:
656    tc_lock_unlock(&trap_mapping_lock);
657    return header;
658 }
659
660 static int parse_libs()
661 {
662    struct link_map *l_current;
663
664    l_current = _r_debug.r_map;
665    if (!l_current)
666       return -1;
667
668    clear_bitmask(all_headers_current);
669    while (l_current) {
670       parse_link_map(l_current);
671       l_current = l_current->l_next;
672    }
673    clear_unloaded_libs();
674
675    return 0;
676 }
677
678 //parse_link_map return values
679 #define PARSED 0
680 #define NOT_REWRITTEN 1
681 #define ALREADY_PARSED 2
682 #define ERROR_INTERNAL -1
683 #define ERROR_FULL -2
684 static int parse_link_map(struct link_map *l) 
685 {
686    ElfX_Dyn *dynamic_ptr;
687    struct trap_mapping_header *header;
688    unsigned int i, new_pos;
689
690    dynamic_ptr = (ElfX_Dyn *) l->l_ld;
691    if (!dynamic_ptr)
692       return -1;
693
694    assert(sizeof(dynamic_ptr->d_un.d_ptr) == sizeof(void *));
695    for (; dynamic_ptr->d_tag != DT_NULL && dynamic_ptr->d_tag != DT_DYNINST; dynamic_ptr++);
696    if (dynamic_ptr->d_tag == DT_NULL) {
697       return NOT_REWRITTEN;
698    }
699
700    header = (struct trap_mapping_header *) (dynamic_ptr->d_un.d_val + l->l_addr);
701    
702    if (header->signature != TRAP_HEADER_SIG)
703       return ERROR_INTERNAL;
704    if (header->pos != -1) {
705       set_bit(all_headers_current, header->pos, 1);
706       assert(all_headers[header->pos] == header);
707       return ALREADY_PARSED;
708    }
709  
710    for (i = 0; i < header->num_entries; i++)
711    {
712       header->traps[i].source = (void *) (((unsigned long) header->traps[i].source) + l->l_addr);
713       header->traps[i].target = (void *) (((unsigned long) header->traps[i].target) + l->l_addr);
714       if (!header->low_entry || header->low_entry > (unsigned long) header->traps[i].source)
715          header->low_entry = (unsigned long) header->traps[i].source;
716       if (!header->high_entry || header->high_entry < (unsigned long) header->traps[i].source)
717          header->high_entry = (unsigned long) header->traps[i].source;
718    }
719
720    new_pos = get_next_free_bitmask(all_headers_last, -1);
721    assert(new_pos >= 0 && new_pos < NUM_LIBRARIES);
722    if (new_pos == NUM_LIBRARIES)
723       return ERROR_FULL;
724
725    header->pos = new_pos;
726    all_headers[new_pos] = header;
727    set_bit(all_headers_current, new_pos, 1);
728    set_bit(all_headers_last, new_pos, 1);
729
730    return PARSED;
731 }
732
733 static void clear_unloaded_libs()
734 {
735    unsigned i;
736    for (i = 0; i<NUM_LIBRARIES_BITMASK_SIZE; i++)
737    {
738       all_headers_last[i] = all_headers_current[i];
739    }
740 }
741
742 static void set_bit(unsigned *bit_mask, int bit, char value) {
743    assert(bit < NUM_LIBRARIES);
744    unsigned *word = bit_mask + bit / WORD_SIZE;
745    unsigned shift = bit % WORD_SIZE;
746    if (value) {
747       *word |= (1 << shift);
748    }
749    else {
750       *word &= ~(1 << shift);
751    }
752 }
753
754 //Wasn't actually needed
755 /*
756 static char get_bit(unsigned *bit_mask, int bit) {
757    assert(bit < NUM_LIBRARIES);
758    unsigned *word = bit_mask + bit / WORD_SIZE;
759    unsigned shift = bit % WORD_SIZE;
760    return (*word & (1 << shift)) ? 1 : 0;
761 }
762 */
763
764 static void clear_bitmask(unsigned *bit_mask) {
765    unsigned i;
766    for (i = 0; i < NUM_LIBRARIES_BITMASK_SIZE; i++) {
767       bit_mask[i] = 0;
768    }
769 }
770
771 static unsigned get_next_free_bitmask(unsigned *bit_mask, int last_pos) {
772    unsigned i, j;
773    j = last_pos+1;
774    i = j / WORD_SIZE;
775    for (; j < NUM_LIBRARIES; i++) {
776       if (bit_mask[i] == (unsigned) -1) {
777          j += WORD_SIZE;
778          continue;
779       }
780       for (;;) {
781          if (!((1 << (j % WORD_SIZE) & bit_mask[i]))) {
782             return j;
783          }
784          j++;
785          if (j % WORD_SIZE == 0) {
786             break;
787          }
788       }
789    }
790    return NUM_LIBRARIES;
791 }
792
793 static unsigned get_next_set_bitmask(unsigned *bit_mask, int last_pos) {
794    unsigned i, j;
795    j = last_pos+1;
796    i = j / WORD_SIZE;
797    for (; j < NUM_LIBRARIES; i++) {
798       if (bit_mask[i] == (unsigned) 0) {
799          j += WORD_SIZE;
800          continue;
801       }
802       for (;;) {
803          if ((1 << (j % WORD_SIZE) & bit_mask[i])) {
804             return j;
805          }
806          j++;
807          if (j % WORD_SIZE == 0) {
808             break;
809          }
810       }
811    }
812    return NUM_LIBRARIES;
813 }
814
815 #endif
816
817
818 #endif /* cap_mutatee_traps */
819
820 int dyn_var = 0;
821
822 #if defined(cap_binary_rewriter)
823 extern void DYNINSTBaseInit();
824 void runDYNINSTBaseInit() __attribute__((constructor));
825 void runDYNINSTBaseInit()
826 {
827    DYNINSTBaseInit();
828 }
829 #endif
830
831
832 /*
833 //Small program for finding the correct values to fill in pos_in_pthreadt
834 // above
835 #include <pthread.h>
836 #include <stdio.h>
837 #include <sys/syscall.h>
838 #include <sys/types.h>
839 #include <unistd.h>
840
841 #define gettid() syscall(SYS_gettid)
842
843 pthread_attr_t attr;
844
845 void *foo(void *f) {
846   pid_t pid, tid;
847   unsigned stack_addr;
848   unsigned best_stack = 0xffffffff;
849   int best_stack_pos = 0;
850   void *start_func;
851   int *p;
852   int i = 0;
853   pid = getpid();
854   tid = gettid();
855   start_func = foo;
856   //x86 only.  
857   asm("movl %%ebp,%0" : "=r" (stack_addr));
858   p = (int *) pthread_self();
859   while (i < 1000)
860   {
861     if (*p == (unsigned) pid)
862       printf("pid @ %d\n", i);
863     if (*p == (unsigned) tid)
864       printf("lwp @ %d\n", i);
865     if (*p > stack_addr && *p < best_stack)
866     {
867       best_stack = *p;
868       best_stack_pos = i;
869     }
870     if (*p == (unsigned) start_func)
871       printf("func @ %d\n", i);
872     i += sizeof(int);
873     p++;
874   }  
875   printf("stack @ %d\n", best_stack_pos);
876   return NULL;
877 }
878
879 int main(int argc, char *argv[])
880 {
881   pthread_t t;
882   void *result;
883   pthread_attr_init(&attr);
884   pthread_create(&t, &attr, foo, NULL);
885   pthread_join(t, &result);
886   return 0;
887 }
888 */
889