Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI_RT / src / RTthread-index.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  *
34  * RTthread-index: INDEX calculation for MTDyninst
35  *
36  ***********************************************************/
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <assert.h>
42 #if !defined(os_windows)
43 #include <unistd.h>
44 #endif
45 #include "RTthread.h"
46 #include "RTcommon.h"
47
48 #define NONE -1
49
50 static DECLARE_TC_LOCK(DYNINST_index_lock);
51
52 static int first_free;
53 static int first_deleted;
54 static int num_free;
55 static int num_deleted;
56
57 static dyninst_thread_t default_thread_structs[MAX_THREADS];
58 static int default_thread_hash[THREADS_HASH_SIZE];
59
60 DLLEXPORT int DYNINSTthreadCount() { return (DYNINST_max_num_threads - num_free); }
61
62 dyntid_t DYNINST_getThreadFromIndex(unsigned index)
63 {
64     return (dyntid_t) DYNINST_thread_structs[index].tid;
65 }
66
67 void DYNINST_initialize_index_list()
68 {
69   static int init_index_done;
70   unsigned i;
71
72   if (init_index_done) return;
73   init_index_done = 1;
74
75   if (DYNINST_max_num_threads == MAX_THREADS)
76      DYNINST_thread_structs = default_thread_structs;
77   else
78      DYNINST_thread_structs = (dyninst_thread_t *) malloc((DYNINST_max_num_threads+1) * sizeof(dyninst_thread_t));
79   assert( DYNINST_thread_structs != NULL );
80   memset(DYNINST_thread_structs, 0, (DYNINST_max_num_threads+1) * sizeof(dyninst_thread_t));
81
82   if (DYNINST_max_num_threads == MAX_THREADS) {
83      DYNINST_thread_hash_size = THREADS_HASH_SIZE;
84      DYNINST_thread_hash = default_thread_hash;
85   }
86   else {
87      DYNINST_thread_hash_size = (int) (DYNINST_max_num_threads * 1.25);
88      DYNINST_thread_hash = (int *) malloc(DYNINST_thread_hash_size * sizeof(int));
89   }
90   assert( DYNINST_thread_hash != NULL );
91
92   for (i=0; i < DYNINST_thread_hash_size; i++)
93       DYNINST_thread_hash[i] = NONE;
94
95   for (i=0; i<DYNINST_max_num_threads-1; i++) {
96       DYNINST_thread_structs[i].next_free = i+1;
97       DYNINST_thread_structs[i].thread_state = UNALLOC;
98   }
99   DYNINST_thread_structs[DYNINST_max_num_threads-1].next_free = NONE;
100   DYNINST_thread_structs[DYNINST_max_num_threads-1].thread_state = UNALLOC;
101   
102   /* We reserve 0 for the 'initial thread' */
103   first_free = 1;
104   first_deleted = NONE;
105   num_free = DYNINST_max_num_threads;
106   num_deleted = 0;
107 }
108
109 /**
110  * A guaranteed-if-there index lookup 
111  **/
112 unsigned DYNINSTthreadIndexSLOW(dyntid_t tid)
113 {
114    unsigned hash_id, orig;
115    unsigned retval = DYNINST_NOT_IN_HASHTABLE;
116    int index, result;
117    unsigned long tid_val = (unsigned long) tid;
118    result = tc_lock_lock(&DYNINST_index_lock);
119    if (result == DYNINST_DEAD_LOCK) {
120        rtdebug_printf("%s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, dyn_pthread_self());
121       /* We specifically return DYNINST_max_num_threads so that instrumentation has someplace safe to scribble
122          in case of an error. */
123        /* DO NOT USE print statements here. That's horribly unsafe if we've instrumented
124           the output functions, as we'll infinite recurse and die */
125        return DYNINST_max_num_threads;
126       }
127    /**
128     * Search the hash table
129     **/
130    if (!DYNINST_thread_hash_size) {
131       //Uninitialized tramp guard.
132       return DYNINST_max_num_threads;
133    }
134
135    hash_id = tid_val % DYNINST_thread_hash_size;
136    orig = hash_id;
137    for (;;) 
138    {
139       index = DYNINST_thread_hash[hash_id];
140       if (index != NONE && DYNINST_thread_structs[index].tid == tid) {
141
142           if (DYNINST_thread_structs[index].thread_state == LWP_EXITED) {
143               /* "Hey, this guy got cleaned up!" */
144               DYNINST_thread_hash[hash_id] = NONE;
145               break;
146           }
147           else if (DYNINST_thread_structs[index].lwp != dyn_lwp_self()) {
148               /* We must have exited and recreated the thread before we deleted... */
149               /* Copied in effect from free_index... */
150               DYNINST_thread_structs[index].thread_state = THREAD_COMPLETE;
151               num_deleted++;
152               break;
153           }
154           else {
155               retval = index;
156               break;
157           }
158       }
159       hash_id++;
160       if (hash_id == DYNINST_thread_hash_size)
161           hash_id = 0;
162       if (orig == hash_id)
163           break;
164    }
165
166    tc_lock_unlock(&DYNINST_index_lock);
167    return retval;
168 }
169
170 static unsigned get_free_index() {
171     /* Assert: we are locked */
172     unsigned ret = 0;
173     assert(first_free != NONE);
174     ret = first_free;
175     first_free = DYNINST_thread_structs[first_free].next_free;
176     if (first_free != NONE) {
177         assert(DYNINST_thread_structs[first_free].thread_state == UNALLOC);
178     }
179     return ret;
180 }
181
182 /* What we have:
183    Several entries may have set their thread_state to LWP_EXITED (done by
184    the mutator). They are still in the hash table, since up until now thread code
185    may have accessed them. We want to remove them from the hash table,
186    set the thread_state to UNALLOC, and add it to the free list. */
187
188 static void clean_thread_list() {
189     /* Assert: we are locked */
190     unsigned hash_iter = 0;
191     for (hash_iter = 0; hash_iter < DYNINST_thread_hash_size; hash_iter++) {
192         unsigned index = DYNINST_thread_hash[hash_iter];
193         if (index == NONE) continue;
194         
195         if (DYNINST_thread_structs[index].thread_state != LWP_EXITED)
196             continue;
197             
198         /* Okay, this one was deleted. Remove it from the hash... */
199         DYNINST_thread_hash[hash_iter] = NONE;
200         /* Mark it as unallocated... */
201         DYNINST_thread_structs[index].tid = 0;
202         DYNINST_thread_structs[index].thread_state = UNALLOC;
203         /* And add it to the end of the free list*/
204         DYNINST_thread_structs[index].next_free = first_free;
205         first_free = index;
206         num_free++;
207         num_deleted--;
208     }
209 }
210
211     
212
213 unsigned DYNINST_alloc_index(dyntid_t tid)
214 {
215    int result;
216    unsigned hash_id, orig;
217    unsigned t, retval;
218    unsigned long tid_val = (unsigned long) tid;
219
220    /* Return an error if this tid already exists.*/
221    if( DYNINSTthreadIndexSLOW(tid) != DYNINST_NOT_IN_HASHTABLE ) {
222       /* ERROR_HANDLING_BAD */
223       return DYNINST_max_num_threads;
224       }
225
226    result = tc_lock_lock(&DYNINST_index_lock);
227    if (result == DYNINST_DEAD_LOCK) {
228        rtdebug_printf("%s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, dyn_pthread_self());
229        fprintf(stderr," %s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, (unsigned long) dyn_pthread_self());
230       /* ERROR_HANDLING_BAD */
231       return DYNINST_max_num_threads;
232       }
233
234    if (DYNINST_am_initial_thread(tid)) {
235        t = 0;
236    }
237    else  if (num_free) {
238        t = get_free_index();
239    }
240    else if (num_deleted) {
241        clean_thread_list();
242        /* We have deleted, but they weren't freed by the mutator yet.... */
243        while (num_free == 0) {
244            clean_thread_list();
245        }
246        t = get_free_index();
247    }
248    else {
249        /* This might actually be a reasonable thing to do, although we should
250           probably mention that the user needs to recompile Dyninst/Paradyn. */
251        retval = DYNINST_max_num_threads;
252        goto done;
253    }
254
255    /*Initialize the dyninst_thread_t object*/
256    DYNINST_thread_structs[t].tid = tid;
257    DYNINST_thread_structs[t].thread_state = THREAD_ACTIVE;
258    DYNINST_thread_structs[t].next_free = NONE;
259    DYNINST_thread_structs[t].lwp = dyn_lwp_self();
260    
261    /*Put it in the hash table*/
262    hash_id = tid_val % DYNINST_thread_hash_size;
263    orig = hash_id;
264    while (DYNINST_thread_hash[hash_id] != NONE)
265    {
266        hash_id++;
267        if (hash_id == DYNINST_thread_hash_size)
268            hash_id = 0;
269        if (orig == hash_id) {
270            /* Isn't this an error case? - bernat */
271            /* ERROR_HANDLING_BAD */
272            retval = DYNINST_max_num_threads;
273            goto done;
274        }
275    }
276    
277    DYNINST_thread_hash[hash_id] = t;
278    retval = t;
279    num_free--;
280  done:
281    tc_lock_unlock(&DYNINST_index_lock);
282    return retval;
283
284 }
285
286 int DYNINST_free_index(dyntid_t tid)
287 {
288    unsigned hash_id, orig;
289    int index, result, retval;
290    unsigned long tid_val = (unsigned long) tid;
291
292    result = tc_lock_lock(&DYNINST_index_lock);
293    if (result == DYNINST_DEAD_LOCK) {
294        rtdebug_printf("%s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, dyn_pthread_self());
295        fprintf(stderr," %s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, (unsigned long) dyn_pthread_self());
296       return -1;
297    }
298
299    /**
300     * Find this thread in the hash table
301     **/
302    hash_id = tid_val % DYNINST_thread_hash_size;
303    orig = hash_id;
304    for (;;)
305    {
306       index = DYNINST_thread_hash[hash_id];
307       if (index != NONE && DYNINST_thread_structs[index].tid == tid)
308           break;
309       hash_id++;
310       if (hash_id == DYNINST_thread_hash_size)
311           hash_id = 0;
312       if (orig == hash_id)
313           {
314               rtdebug_printf("%s[%d]:  DESTROY FAILURE:  tid not in hash\n", __FILE__, __LINE__);
315               retval = -1;
316               goto done; /*tid doesn't exist*/
317           }
318    }
319    /* Mark this entry as disabled */
320    DYNINST_thread_structs[index].thread_state = THREAD_COMPLETE;
321
322    num_deleted++;
323    retval = 0;
324  done:    
325    tc_lock_unlock(&DYNINST_index_lock);
326    return retval;
327 }
328
329 #if 0
330 void DYNINST_print_lists()
331 {
332    unsigned i;
333    int index;
334    printf("  Free:    ");
335    for (i = first_free; i != NONE; i = threads[i].next_free)
336       printf("%u@%u ", threads[i].tid, i);
337    printf("\n");
338
339    printf("  Alloced: ");
340    for (i = 0; i<threads_hash_size; i++)
341    {
342       index = threads_hash[i];
343       if (index != NONE)
344          printf("%u@%u ", threads[index].tid, i);
345    }
346    printf("\n");
347 }
348 #endif