Fix for (1) power deadlock problem due to incorrect lock implementation. We now use...
[dyninst.git] / dyninstAPI_RT / src / RTthread-index.c
1 /*
2  * Copyright (c) 1996-2004 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  *
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  *
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  *
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  *
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /***********************************************************
43  *
44  * RTthread-index: INDEX calculation for MTDyninst
45  *
46  ***********************************************************/
47
48 #include <stdio.h>
49 #include <stdlib.h>
50 #include <string.h>
51 #include <assert.h>
52 #if !defined(os_windows)
53 #include <unistd.h>
54 #endif
55 #include "RTthread.h"
56 #include "RTcommon.h"
57
58 #define NONE -1
59
60 static DECLARE_TC_LOCK(DYNINST_index_lock);
61
62 static int first_free;
63 static int first_deleted;
64 static int num_free;
65 static int num_deleted;
66
67 DLLEXPORT int DYNINSTthreadCount() { return (DYNINST_max_num_threads - num_free); }
68
69 dyntid_t DYNINST_getThreadFromIndex(unsigned index)
70 {
71     return (dyntid_t) DYNINST_thread_structs[index].tid;
72 }
73
74 void DYNINST_initialize_index_list()
75 {
76   static int init_index_done;
77   unsigned i;
78
79   if (init_index_done) return;
80   init_index_done = 1;
81
82   DYNINST_thread_structs = (dyninst_thread_t *) malloc((DYNINST_max_num_threads+1) * sizeof(dyninst_thread_t));
83   assert( DYNINST_thread_structs != NULL );
84   memset(DYNINST_thread_structs, 0, (DYNINST_max_num_threads+1) * sizeof(dyninst_thread_t));
85
86   DYNINST_thread_hash_size = (int) (DYNINST_max_num_threads * 1.25);
87   DYNINST_thread_hash = (int *) malloc(DYNINST_thread_hash_size * sizeof(int));
88   assert( DYNINST_thread_hash != NULL );
89
90   for (i=0; i < DYNINST_thread_hash_size; i++)
91       DYNINST_thread_hash[i] = NONE;
92
93   for (i=0; i<DYNINST_max_num_threads-1; i++) {
94       DYNINST_thread_structs[i].next_free = i+1;
95       DYNINST_thread_structs[i].thread_state = UNALLOC;
96   }
97   DYNINST_thread_structs[DYNINST_max_num_threads-1].next_free = NONE;
98   DYNINST_thread_structs[DYNINST_max_num_threads-1].thread_state = UNALLOC;
99   
100   /* We reserve 0 for the 'initial thread' */
101   first_free = 1;
102   first_deleted = NONE;
103   num_free = DYNINST_max_num_threads;
104   num_deleted = 0;
105 }
106
107 /**
108  * A guaranteed-if-there index lookup 
109  **/
110 unsigned DYNINSTthreadIndexSLOW(dyntid_t tid)
111 {
112    unsigned hash_id, orig;
113    unsigned retval = DYNINST_NOT_IN_HASHTABLE;
114    int index, result;
115    unsigned long tid_val = (unsigned long) tid;
116    result = tc_lock_lock(&DYNINST_index_lock);
117    if (result == DYNINST_DEAD_LOCK) {
118        rtdebug_printf("%s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, dyn_pthread_self());
119       /* We specifically return DYNINST_max_num_threads so that instrumentation has someplace safe to scribble
120          in case of an error. */
121        /* DO NOT USE print statements here. That's horribly unsafe if we've instrumented
122           the output functions, as we'll infinite recurse and die */
123        return DYNINST_max_num_threads;
124       }
125    /**
126     * Search the hash table
127     **/
128
129    hash_id = tid_val % DYNINST_thread_hash_size;
130    orig = hash_id;
131    for (;;) 
132    {
133       index = DYNINST_thread_hash[hash_id];
134       if (index != NONE && DYNINST_thread_structs[index].tid == tid) {
135
136           if (DYNINST_thread_structs[index].thread_state == LWP_EXITED) {
137               /* "Hey, this guy got cleaned up!" */
138               DYNINST_thread_hash[hash_id] = NONE;
139               break;
140           }
141           else if (DYNINST_thread_structs[index].lwp != dyn_lwp_self()) {
142               /* We must have exited and recreated the thread before we deleted... */
143               /* Copied in effect from free_index... */
144               DYNINST_thread_structs[index].thread_state = THREAD_COMPLETE;
145               num_deleted++;
146               break;
147           }
148           else {
149               retval = index;
150               break;
151           }
152       }
153       hash_id++;
154       if (hash_id == DYNINST_thread_hash_size)
155           hash_id = 0;
156       if (orig == hash_id)
157           break;
158    }
159
160    tc_lock_unlock(&DYNINST_index_lock);
161    return retval;
162 }
163
164 static unsigned get_free_index() {
165     /* Assert: we are locked */
166     unsigned ret = 0;
167     assert(first_free != NONE);
168     ret = first_free;
169     first_free = DYNINST_thread_structs[first_free].next_free;
170     if (first_free != NONE) {
171         assert(DYNINST_thread_structs[first_free].thread_state == UNALLOC);
172     }
173     return ret;
174 }
175
176 /* What we have:
177    Several entries may have set their thread_state to LWP_EXITED (done by
178    the mutator). They are still in the hash table, since up until now thread code
179    may have accessed them. We want to remove them from the hash table,
180    set the thread_state to UNALLOC, and add it to the free list. */
181
182 static void clean_thread_list() {
183     /* Assert: we are locked */
184     unsigned hash_iter = 0;
185     for (hash_iter = 0; hash_iter < DYNINST_thread_hash_size; hash_iter++) {
186         unsigned index = DYNINST_thread_hash[hash_iter];
187         if (index == NONE) continue;
188         
189         if (DYNINST_thread_structs[index].thread_state != LWP_EXITED)
190             continue;
191             
192         /* Okay, this one was deleted. Remove it from the hash... */
193         DYNINST_thread_hash[hash_iter] = NONE;
194         /* Mark it as unallocated... */
195         DYNINST_thread_structs[index].tid = 0;
196         DYNINST_thread_structs[index].thread_state = UNALLOC;
197         /* And add it to the end of the free list*/
198         DYNINST_thread_structs[index].next_free = first_free;
199         first_free = index;
200         num_free++;
201         num_deleted--;
202     }
203 }
204
205     
206
207 unsigned DYNINST_alloc_index(dyntid_t tid)
208 {
209    int result;
210    unsigned hash_id, orig;
211    unsigned t, retval;
212    unsigned long tid_val = (unsigned long) tid;
213
214    /* Return an error if this tid already exists.*/
215    if( DYNINSTthreadIndexSLOW(tid) != DYNINST_NOT_IN_HASHTABLE ) {
216       /* ERROR_HANDLING_BAD */
217       return DYNINST_max_num_threads;
218       }
219
220    result = tc_lock_lock(&DYNINST_index_lock);
221    if (result == DYNINST_DEAD_LOCK) {
222        rtdebug_printf("%s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, dyn_pthread_self());
223       /* ERROR_HANDLING_BAD */
224       return DYNINST_max_num_threads;
225       }
226
227    if (DYNINST_am_initial_thread(tid)) {
228        t = 0;
229    }
230    else  if (num_free) {
231        t = get_free_index();
232    }
233    else if (num_deleted) {
234        clean_thread_list();
235        /* We have deleted, but they weren't freed by the mutator yet.... */
236        while (num_free == 0) {
237            clean_thread_list();
238        }
239        t = get_free_index();
240    }
241    else {
242        /* This might actually be a reasonable thing to do, although we should
243           probably mention that the user needs to recompile Dyninst/Paradyn. */
244        retval = DYNINST_max_num_threads;
245        goto done;
246    }
247
248    /*Initialize the dyninst_thread_t object*/
249    DYNINST_thread_structs[t].tid = tid;
250    DYNINST_thread_structs[t].thread_state = THREAD_ACTIVE;
251    DYNINST_thread_structs[t].next_free = NONE;
252    DYNINST_thread_structs[t].lwp = dyn_lwp_self();
253    
254    /*Put it in the hash table*/
255    hash_id = tid_val % DYNINST_thread_hash_size;
256    orig = hash_id;
257    while (DYNINST_thread_hash[hash_id] != NONE)
258    {
259        hash_id++;
260        if (hash_id == DYNINST_thread_hash_size)
261            hash_id = 0;
262        if (orig == hash_id) {
263            /* Isn't this an error case? - bernat */
264            /* ERROR_HANDLING_BAD */
265            retval = DYNINST_max_num_threads;
266            goto done;
267        }
268    }
269    
270    DYNINST_thread_hash[hash_id] = t;
271    retval = t;
272    num_free--;
273  done:
274    tc_lock_unlock(&DYNINST_index_lock);
275    return retval;
276
277 }
278
279 int DYNINST_free_index(dyntid_t tid)
280 {
281    unsigned hash_id, orig;
282    int index, result, retval;
283    unsigned long tid_val = (unsigned long) tid;
284
285    result = tc_lock_lock(&DYNINST_index_lock);
286    if (result == DYNINST_DEAD_LOCK) {
287        rtdebug_printf("%s[%d]:  DEADLOCK HERE tid %lu \n", __FILE__, __LINE__, dyn_pthread_self());
288       return -1;
289    }
290
291    /**
292     * Find this thread in the hash table
293     **/
294    hash_id = tid_val % DYNINST_thread_hash_size;
295    orig = hash_id;
296    for (;;)
297    {
298       index = DYNINST_thread_hash[hash_id];
299       if (index != NONE && DYNINST_thread_structs[index].tid == tid)
300           break;
301       hash_id++;
302       if (hash_id == DYNINST_thread_hash_size)
303           hash_id = 0;
304       if (orig == hash_id)
305           {
306               rtdebug_printf("%s[%d]:  DESTROY FAILURE:  tid not in hash\n", __FILE__, __LINE__);
307               retval = -1;
308               goto done; /*tid doesn't exist*/
309           }
310    }
311    /* Mark this entry as disabled */
312    DYNINST_thread_structs[index].thread_state = THREAD_COMPLETE;
313
314    num_deleted++;
315    retval = 0;
316  done:    
317    tc_lock_unlock(&DYNINST_index_lock);
318    return retval;
319 }
320
321 #if 0
322 void DYNINST_print_lists()
323 {
324    unsigned i;
325    int index;
326    printf("  Free:    ");
327    for (i = first_free; i != NONE; i = threads[i].next_free)
328       printf("%u@%u ", threads[i].tid, i);
329    printf("\n");
330
331    printf("  Alloced: ");
332    for (i = 0; i<threads_hash_size; i++)
333    {
334       index = threads_hash[i];
335       if (index != NONE)
336          printf("%u@%u ", threads[index].tid, i);
337    }
338    printf("\n");
339 }
340 #endif