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