Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI_RT / src / RTcommon.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 /* $Id: RTcommon.c,v 1.78 2008/04/15 16:43:44 roundy Exp $ */
33
34 #include <assert.h>
35 #include <stdlib.h>
36 #include <stdarg.h>
37 #include <stdio.h>
38 #include <assert.h>
39 #include "dyninstAPI_RT/h/dyninstAPI_RT.h"
40 #include "RTcommon.h"
41 #include "RTthread.h"
42
43 #if defined(rs6000_ibm_aix4_1)
44 #include <sys/mman.h>
45 #include <sys/types.h>
46 #endif
47
48 unsigned int DYNINSTobsCostLow;
49 unsigned int DYNINSThasInitialized = 0;
50 unsigned DYNINST_max_num_threads;
51 struct DYNINST_bootstrapStruct DYNINST_bootstrap_info;
52 char gLoadLibraryErrorString[ERROR_STRING_LENGTH];
53 int DYNINSTdebugRTlib;
54
55 dyninst_thread_t *DYNINST_thread_structs;
56 int *DYNINST_thread_hash;
57 unsigned DYNINST_thread_hash_size;
58 int DYNINSTstaticMode = 1;
59
60 /**
61  * Allocate the Dyninst heaps
62  * 
63  * The IA-64 requires that instruction be 16-byte aligned, so we have to 
64  * align the heaps if we want to use them for inferior RPCs. 
65  **/
66 #if defined(arch_ia64)
67 typedef struct { uint64_t low; uint64_t high; } ia64_bundle_t;
68 #define HEAP_TYPE ia64_bundle_t
69 #define ALIGN_ATTRIB __attribute((aligned))
70 #else
71 #define HEAP_TYPE double
72 #define ALIGN_ATTRIB 
73 #endif
74
75 #if defined(os_linux)
76 #define HEAP_LOCAL extern
77 #else
78 #define HEAP_LOCAL
79 #endif
80
81
82 HEAP_LOCAL HEAP_TYPE DYNINSTglobalData[SYN_INST_BUF_SIZE/sizeof(HEAP_TYPE)] ALIGN_ATTRIB;
83 HEAP_LOCAL HEAP_TYPE DYNINSTstaticHeap_512K_lowmemHeap_1[512*1024/sizeof(HEAP_TYPE)] ALIGN_ATTRIB;
84 HEAP_LOCAL HEAP_TYPE DYNINSTstaticHeap_16M_anyHeap_1[16*1024*1024/sizeof(HEAP_TYPE)] ALIGN_ATTRIB;
85
86 /* These are necessary because of silly C-style 'extern'/linking conventions. */
87 const unsigned long sizeOfLowMemHeap1 = sizeof( DYNINSTstaticHeap_512K_lowmemHeap_1 );
88 const unsigned long sizeOfAnyHeap1 = sizeof( DYNINSTstaticHeap_16M_anyHeap_1 );
89
90 /**
91  * One some platforms we can tell when a fork or exec is occurring through 
92  * system-provided events. On others we do it ourselves.  Enumerated type 
93  * defined in header file
94  **/
95 DYNINST_synch_event_t DYNINST_synch_event_id = DSE_undefined;
96 void *DYNINST_synch_event_arg1;
97 /* Code to read args 2,3 would have to be moved from dyninstAPI's*/
98 /* process::handleStopThread to signalgenerator::decodeRTSignal in*/
99 /* order for other signals to make use of them, as currently only the*/
100 /* stopThread event needs makes use of them.  */
101 void *DYNINST_synch_event_arg2 = NULL; /* not read in dyninst's decodeRTSignal*/
102 void *DYNINST_synch_event_arg3 = NULL; /* not read in dyninst's decodeRTSignal*/
103 int DYNINST_break_point_event = 0;
104
105 /**
106  * These variables are used to pass arguments into DYNINSTinit
107  * when it is called as an _init function 
108  **/
109 int libdyninstAPI_RT_init_localCause=-1;
110 int libdyninstAPI_RT_init_localPid=-1;
111 int libdyninstAPI_RT_init_maxthreads=-1;
112 int libdyninstAPI_RT_init_debug_flag=0;
113
114 int DYNINST_mutatorPid;
115 int DYNINSTdebugPrintRT = 0;
116 int isMutatedExec = 0;
117
118 unsigned *DYNINST_tramp_guards;
119
120 unsigned DYNINST_default_tramp_guards[MAX_THREADS+1];
121
122 #if defined(os_linux)
123 void DYNINSTlinuxBreakPoint();
124 #endif
125
126 DECLARE_DYNINST_LOCK(DYNINST_trace_lock);
127
128 /**
129  * Init the FPU.  We've seen bugs with Linux (e.g., Redhat 6.2 stock kernel on 
130  * PIIIs) where processes started by Paradyn started with FPU uninitialized. 
131  * DYNINSTdummydouble is global so the compiler won't optimize away FP code
132  * in initFPU
133  **/
134 double DYNINSTdummydouble = 4321.71;                                    
135 static void initFPU()
136 {
137    double x = 17.1234;
138    DYNINSTdummydouble *= x;
139 }
140
141 static void initTrampGuards(unsigned maxthreads)
142 {
143
144    unsigned i;
145 #if defined(rs6000_ibm_aix4_1)
146         /*      WHAT IS GOING ON HERE?
147                 For save the world to work, the DYNINST_tramp_guards must be reloaded in the
148                 exact same place when the mutated binary is run.  Normally, DYNINST_tramp_guards
149                 is allocated by malloc (See below).  This does not work for AIX because before
150                 we get to the init section of the RT lib, which reloads DYNINST_tramp_guards, the
151                 address DYNINST_tramp_guards needs to be loaded at has been allocated and is in
152                 use.  To get around this, I am using mmap to allocate DYNINST_tramp_guards on
153                 AIX.  I am allocating to a MAP_VARIABLE location because there is no address that
154                 is always known to be free that we can allocate.  This way, when the init section
155                 of the RT lib is run this address will probably be free (with a little magic in 
156                 loadFile() in RTmutatedBinary_XCOFF.c.
157
158                 Just in case we cannot mmap the space we need here (at this point in execution I
159                 cannot imagine this happening, if you want to do anything useful with Dyninst) I fall
160                 back to malloc and print a warning that save the world will probably not work.
161         */
162         
163 /* http://publibn.boulder.ibm.com/doc_link/en_US/a_doc_lib/aixprggd/genprogc/sys_mem_alloc.htm#HDRA9E4A4C9921SYLV */
164         unsigned int memLoc = sbrk(0);
165         int pageSize = getpagesize();
166         int arraySize = ((maxthreads +1) * sizeof(unsigned));
167         arraySize -= (arraySize  % pageSize);
168         arraySize +=  pageSize;
169
170         /*fprintf(stderr,"TRAMP GUARDS (sbrk 0x%x)\n",sbrk(0));*/
171
172         /*fprintf(stderr, "MMAP: 0x%x,0x%x,,,1,0x0\n",memLoc,arraySize);*/
173         DYNINST_tramp_guards = (unsigned *) mmap(0x0, arraySize, PROT_READ|PROT_WRITE, MAP_VARIABLE|MAP_ANONYMOUS, -1,0x0);
174
175         if (DYNINST_tramp_guards == (unsigned *) -1){
176                 perror("mmap: DYNINST_tramp_guards ");
177                 fprintf(stderr,"Warning: DYNINST_tramp_guards may not be allocated correctly for save the world code!\n");
178                 DYNINST_tramp_guards = (unsigned *) malloc((maxthreads+1)*sizeof(unsigned));
179         }
180
181         /*fprintf(stderr,"TRAMP GUARDS 0x%x (sbrk 0x%x)\n", DYNINST_tramp_guards,sbrk(0));*/
182
183 #else
184    /*We allocate maxthreads+1 because maxthreads is sometimes used as an*/
185    /*error value to mean we don't know what thread this is.  Sometimes used*/
186    /*during the early setup phases.*/
187    if (maxthreads <= MAX_THREADS) {
188       DYNINST_tramp_guards = DYNINST_default_tramp_guards;
189    }
190    else {
191       DYNINST_tramp_guards = (unsigned *) malloc((maxthreads+1)*sizeof(unsigned));
192    }
193 #endif
194    for (i=0; i<maxthreads; i++)
195    {
196       DYNINST_tramp_guards[i] = 1;
197    }
198 }
199
200 /**
201  * This function is called in both static and dynamic rewriting, on
202  * all platforms that support binary rewriting, but before DYNINSTinit
203  **/
204 void DYNINSTBaseInit()
205 {
206    unsigned i;
207    DYNINST_max_num_threads = MAX_THREADS;
208    DYNINST_tramp_guards = DYNINST_default_tramp_guards;
209    for (i=0; i<DYNINST_max_num_threads+1; i++)
210       DYNINST_tramp_guards[i] = 1;
211 #if defined(cap_mutatee_traps)
212    DYNINSTinitializeTrapHandler();
213 #endif
214    DYNINST_initialize_index_list();
215    DYNINSThasInitialized = 1;
216 }
217
218 /**
219  * The Dyninst API arranges for this function to be called at the entry to
220  * main() via libdyninstAPI_RT_init (defined in RTposix.c and RTwinnt.c).
221  * libdyninstAPI_RT_init is called by one of the following methods:
222  *    GCC: link with gcc -shared, and use __attribute__((constructor));
223  *    AIX: ld with -binitfini:libdyninstAPI_RT_init
224  *    Solaris: ld with -z initarray=libdyninstAPI_RT_init
225  *    Linux: ld with -init libdyninstAPI_RT_init
226  *           gcc with -Wl,-init -Wl,...
227  *
228  * This is only called in the Dynamic instrumentation case.  Static
229  * libraries don't call this.
230  **/
231 void DYNINSTinit(int cause, int pid, int maxthreads, int debug_flag)
232 {
233    int calledByFork = 0, calledByAttach = 0;
234    rtdebug_printf("%s[%d]:  DYNINSTinit:  welcome to DYNINSTinit()\n", __FILE__, __LINE__);
235    initFPU();
236
237    DYNINSTstaticMode = 0;
238    tc_lock_init(&DYNINST_trace_lock);
239    DYNINST_mutatorPid = pid;
240    
241    if (isMutatedExec) {
242       fflush(stdout);
243       cause = 9;
244    }
245
246    calledByFork = (cause == 2);
247    calledByAttach = (cause == 3);
248    DYNINSThasInitialized = 1;
249    DYNINST_max_num_threads = maxthreads;
250    DYNINSTdebugRTlib = debug_flag; /* set by mutator on request */
251    rtdebug_printf("%s[%d]:  welcome to DYNINSTinit\n", __FILE__, __LINE__);
252
253    /* sanity check */
254    assert(sizeof(int64_t) == 8);
255    assert(sizeof(int32_t) == 4);
256    
257    initTrampGuards(DYNINST_max_num_threads);
258
259    DYNINSTos_init(calledByFork, calledByAttach);
260    DYNINST_initialize_index_list();
261
262    DYNINST_bootstrap_info.pid = dyn_pid_self();
263    DYNINST_bootstrap_info.ppid = pid;    
264    DYNINST_bootstrap_info.event = cause;
265    rtdebug_printf("%s[%d]:  leaving DYNINSTinit\n", __FILE__, __LINE__);
266 }
267
268  
269 /**
270  * Does what it's called. Used by the paradyn daemon as a default in certain 
271  * cases (MT in particular)
272  **/
273 int DYNINSTreturnZero()
274 {
275    return 0;
276 }
277
278 /* Used to by dyninst breakpoint snippet */
279 void DYNINST_snippetBreakpoint() {
280    /* Set the state so the mutator knows what's up */
281    DYNINST_synch_event_id = DSE_snippetBreakpoint;
282    DYNINST_synch_event_arg1 = NULL;
283    /* Stop ourselves */
284    DYNINSTbreakPoint();
285    /* Once the stop completes, clean up */
286    DYNINST_synch_event_id = DSE_undefined;
287 }
288
289 /* Used to instrument (and report) the entry of fork */
290 void DYNINST_instForkEntry() {
291    /* Set the state so the mutator knows what's up */
292    DYNINST_synch_event_id = DSE_forkEntry;
293    DYNINST_synch_event_arg1 = NULL;
294    /* Stop ourselves */
295    DYNINSTbreakPoint();
296    /* Once the stop completes, clean up */
297    DYNINST_synch_event_id = DSE_undefined;
298    DYNINST_synch_event_arg1 = NULL;
299 }
300
301        
302 /* Used to instrument (and report) the exit of fork */
303 /* We use the safe breakpoint on the child side of fork
304    as we may not be attached at that point. The parent
305    side uses the normal version. */
306 void DYNINST_instForkExit(void *arg1) {
307    /* Set the state so the mutator knows what's up */    
308    DYNINST_synch_event_id = DSE_forkExit;
309    DYNINST_synch_event_arg1 = arg1;
310    /* Stop ourselves */
311    if ((long int)arg1 == 0) {
312        /* Child... */
313        DYNINSTsafeBreakPoint();
314    }
315    else {
316        DYNINSTbreakPoint();
317    }
318    /* Once the stop completes, clean up */
319    DYNINST_synch_event_id = DSE_undefined;
320    DYNINST_synch_event_arg1 = NULL;
321 }
322
323        
324 /* Used to instrument (and report) the entry of exec */
325 void DYNINST_instExecEntry(void *arg1) {
326    /* Set the state so the mutator knows what's up */
327    DYNINST_synch_event_id = DSE_execEntry;
328    DYNINST_synch_event_arg1 = arg1;
329    /* Stop ourselves */
330 #if defined(os_linux)
331    DYNINSTlinuxBreakPoint();
332 #else
333    DYNINSTbreakPoint();
334 #endif
335    /* Once the stop completes, clean up */
336    DYNINST_synch_event_id = DSE_undefined;
337    DYNINST_synch_event_arg1 = NULL;
338 }
339
340        
341 /* Used to instrument (and report) the exit of exec */
342 void DYNINST_instExecExit(void *arg1) {
343    /* Set the state so the mutator knows what's up */
344    DYNINST_synch_event_id = DSE_execExit;
345    DYNINST_synch_event_arg1 = arg1;
346    /* Stop ourselves */
347    DYNINSTbreakPoint();
348    /* Once the stop completes, clean up */
349    DYNINST_synch_event_id = DSE_undefined;
350    DYNINST_synch_event_arg1 = NULL;
351 }
352
353        
354 /* Used to instrument (and report) the entry of exit */
355 void DYNINST_instExitEntry(void *arg1) {
356    /* Set the state so the mutator knows what's up */
357    DYNINST_synch_event_id = DSE_exitEntry;
358    DYNINST_synch_event_arg1 = arg1;
359    /* Stop ourselves */
360    DYNINSTbreakPoint();
361    /* Once the stop completes, clean up */
362    DYNINST_synch_event_id = DSE_undefined;
363    DYNINST_synch_event_arg1 = NULL;
364 }
365
366 /* Used to instrument (and report) the entry of exit */
367 void DYNINST_instLoadLibrary(void *arg1) {
368    /* Set the state so the mutator knows what's up */
369    DYNINST_synch_event_id = DSE_loadLibrary;
370    DYNINST_synch_event_arg1 = arg1;
371    /* Stop ourselves */
372    DYNINSTbreakPoint();
373    /* Once the stop completes, clean up */
374    DYNINST_synch_event_id = DSE_undefined;
375    DYNINST_synch_event_arg1 = NULL;
376 }
377
378 /* Used to instrument (and report) the entry of exit */
379 void DYNINST_instLwpExit(void) {
380    /* Set the state so the mutator knows what's up */
381    DYNINST_synch_event_id = DSE_lwpExit;
382    DYNINST_synch_event_arg1 = NULL;
383    /* Stop ourselves */
384    DYNINSTbreakPoint();
385    /* Once the stop completes, clean up */
386    DYNINST_synch_event_id = DSE_undefined;
387    DYNINST_synch_event_arg1 = NULL;
388 }
389
390
391 /** 
392  * Receives two snippets as arguments, stops the mutator, and sends
393  * the arguments back to the mutator
394  **/     
395 void DYNINST_stopThread (void * pointAddr, void *callBackID, void *calculation)
396 {
397    /* Set the state so the mutator knows what's up */
398    DYNINST_synch_event_id = DSE_stopThread;
399    DYNINST_synch_event_arg1 = pointAddr;
400    DYNINST_synch_event_arg2 = callBackID;
401    DYNINST_synch_event_arg3 = calculation;
402    /* Stop ourselves */
403    DYNINSTbreakPoint();
404    /* Once the stop completes, clean up */
405    DYNINST_synch_event_id = DSE_undefined;
406    DYNINST_synch_event_arg1 = NULL;
407    DYNINST_synch_event_arg2 = NULL;
408    DYNINST_synch_event_arg3 = NULL;
409 }
410
411
412 /**
413  * Used to report addresses of functions called at dynamic call sites 
414  **/     
415 int DYNINSTasyncDynFuncCall (void * call_target, void *call_addr)
416 {
417   int err = 0;
418   int result;
419   rtBPatch_asyncEventRecord ev;
420   BPatch_dynamicCallRecord call_ev;
421
422   if (DYNINSTstaticMode)
423      return 0;
424
425   rtdebug_printf("%s[%d]:  welcome to DYNINSTasyncDynFuncCall\n", __FILE__, __LINE__);
426   result = tc_lock_lock(&DYNINST_trace_lock);
427   if (result == DYNINST_DEAD_LOCK)
428   {
429      fprintf(stderr, "[%s:%d] - Error in libdyninstAPI_RT: trace pipe deadlock\n",
430              __FILE__, __LINE__);
431      return DYNINST_TRACEPIPE_ERRVAL;
432   }
433  
434   ev.type = rtBPatch_dynamicCallEvent;
435   ev.pid = dyn_pid_self();
436   err = DYNINSTwriteEvent((void *) &ev, sizeof(rtBPatch_asyncEventRecord));
437
438   if (err) {
439     fprintf(stderr, "%s[%d]:  write error\n",
440             __FILE__, __LINE__);
441     goto done;
442   }
443
444   call_ev.call_site_addr = call_addr;
445   call_ev.call_target = call_target;
446   err = DYNINSTwriteEvent((void *) &call_ev, sizeof(BPatch_dynamicCallRecord));
447
448   if (err) {
449     fprintf(stderr, "%s[%d]:  write error\n",
450             __FILE__, __LINE__);
451     goto done;
452   }
453
454  done:
455   tc_lock_unlock(&DYNINST_trace_lock);
456
457   rtdebug_printf("%s[%d]:  leaving DYNINSTasyncDynFuncCall: status = %s\n", 
458                  __FILE__, __LINE__, err ? "error" : "ok");
459   return err;
460 }
461
462 int DYNINSTuserMessage(void *msg, unsigned int msg_size)
463 {
464   int err = 0, result;
465   rtBPatch_asyncEventRecord ev;
466
467   if (DYNINSTstaticMode)
468      return 0;
469
470   rtdebug_printf("%s[%d]:  welcome to DYNINSTuserMessage\n", __FILE__, __LINE__);
471   result = tc_lock_lock(&DYNINST_trace_lock);
472   if (result == DYNINST_DEAD_LOCK)
473   {
474      fprintf(stderr, "[%s:%d] - Error in libdyninstAPI_RT: trace pipe deadlock\n",
475              __FILE__, __LINE__);
476      return DYNINST_TRACEPIPE_ERRVAL;
477   }
478
479   ev.type = rtBPatch_userEvent;
480   ev.pid = dyn_pid_self();
481   ev.size = msg_size;
482   err = DYNINSTwriteEvent((void *) &ev, sizeof(rtBPatch_asyncEventRecord));
483
484   if (err) {
485     fprintf(stderr, "%s[%d]:  write error\n",
486             __FILE__, __LINE__);
487     goto done;
488   }
489
490   err = DYNINSTwriteEvent(msg, msg_size);
491
492   if (err) {
493     fprintf(stderr, "%s[%d]:  write error\n",
494             __FILE__, __LINE__);
495     goto done;
496   }
497
498  done:
499   tc_lock_unlock(&DYNINST_trace_lock);
500   rtdebug_printf("%s[%d]:  leaving DYNINSTuserMessage: status = %s\n", 
501                  __FILE__, __LINE__, err ? "error" : "ok");
502   return err;
503 }
504
505 int tc_lock_init(tc_lock_t *t)
506 {
507   t->mutex = 0;
508   t->tid = (dyntid_t) DYNINST_INITIAL_LOCK_PID;
509   return 0;
510 }
511
512 int tc_lock_unlock(tc_lock_t *t)
513 {
514   t->tid = (dyntid_t) DYNINST_INITIAL_LOCK_PID;
515   t->mutex = 0;
516   return 0;
517 }
518     
519 int tc_lock_destroy(tc_lock_t *t)
520 {
521   t->tid = (dyntid_t) DYNINST_INITIAL_LOCK_PID;
522   t->mutex = 0;
523   return 0;
524 }
525
526 void dyninst_init_lock(dyninst_lock_t *lock)
527 {
528    lock->tid = (dyntid_t) DYNINST_INITIAL_LOCK_PID;
529    lock->mutex = 0;
530 }
531
532 void dyninst_free_lock(dyninst_lock_t *lock)
533 {
534 }
535
536 int dyninst_lock(dyninst_lock_t *lock)
537 {
538    return tc_lock_lock(lock);
539 }
540
541 void dyninst_unlock(dyninst_lock_t *lock)
542 {
543    tc_lock_unlock(lock);
544 }
545
546 unsigned dyninst_maxNumOfThreads()
547 {
548 #if !defined(cap_threads)
549    return 1;
550 #else
551    if (!DYNINSThasInitialized)
552       return 0;
553    if (!DYNINST_multithread_capable)
554       return 1;
555    return DYNINST_max_num_threads;
556 #endif
557 }
558
559 #if !(os_solaris==8)
560 int rtdebug_printf(char *format, ...)
561 {
562   int ret;
563   va_list va;
564   if (!DYNINSTdebugRTlib) return 0;
565   if (NULL == format) return DYNINST_PRINTF_ERRVAL;
566
567   fprintf(stderr, "[RTLIB]");
568   va_start(va, format);
569   ret = vfprintf(stderr, format, va);
570   va_end(va);
571
572   return ret;
573 }
574 #endif
575
576 #ifndef CASE_RETURN_STR
577 #define CASE_RETURN_STR(x) case x: return #x
578 #endif
579
580 char *asyncEventType2str(rtBPatch_asyncEventType t)
581 {
582   switch (t) {
583   CASE_RETURN_STR(rtBPatch_nullEvent);
584   CASE_RETURN_STR(rtBPatch_newConnectionEvent);
585   CASE_RETURN_STR(rtBPatch_internalShutDownEvent);
586   CASE_RETURN_STR(rtBPatch_threadCreateEvent);
587   CASE_RETURN_STR(rtBPatch_threadDestroyEvent);
588   CASE_RETURN_STR(rtBPatch_dynamicCallEvent);
589   CASE_RETURN_STR(rtBPatch_userEvent);
590   default: return "bad_async_event_type";
591   }
592
593
594 volatile unsigned long dyninstTrapTableUsed;
595 volatile unsigned long dyninstTrapTableVersion;
596 volatile trapMapping_t *dyninstTrapTable;
597 volatile unsigned long dyninstTrapTableIsSorted;
598
599 void* dyninstTrapTranslate(void *source, 
600                            volatile unsigned long *table_used,
601                            volatile unsigned long *table_version,
602                            volatile trapMapping_t **trap_table,
603                            volatile unsigned long *is_sorted)
604 {
605    volatile unsigned local_version;
606    unsigned i;
607    void *target;
608
609    do {
610       local_version = *table_version;
611       target = NULL;
612
613       if (*is_sorted) 
614       {
615          unsigned min = 0;
616          unsigned mid = 0;
617          unsigned max = *table_used;
618          unsigned prev = max+1;
619          
620          for (;;) {
621             mid = (min + max) / 2;
622             if (mid == prev)
623                break;
624             prev = mid;
625             
626             if ((*trap_table)[mid].source < source)
627                min = mid;
628             else if ((*trap_table)[mid].source > source)
629                max = mid;
630             else {
631                target = (*trap_table)[mid].target;
632                break;
633             }
634          }
635       } 
636       else { /*!dyninstTrapTableIsSorted*/
637          for (i = 0; i<*table_used; i++) {
638             if ((*trap_table)[i].source == source) {
639                target = (*trap_table)[i].target;
640                break;
641             }
642          }
643       }         
644    } while (local_version != *table_version);
645
646    /*   fprintf(stderr, "Mapped %p to %p\n", source, target);*/
647    return target;
648 }
649