Unix Prog: Deadlock Avoidance(2)

1. Simplified Example:
In prevoious example, hashlock mutex is used to control the modification for hash table, struct foo lock mutex f_lock is used to control the modification of the local struct foo. We can change it to "use hashlock mutex to control everything" to considerably reduce the complexity of the code, but worsen the performance of program, since it is possible that many threads are blocked by one mutex: hashlock.

deadlock.c:

 #include<stdio.h>  
 #include<stdlib.h>  
 #include<unistd.h>  
 #include<pthread.h>  
   
 #define NHASH 29  
 #define HASH(fp) (((unsigned long)fp) % NHASH)  
 struct foo *fh[NHASH];  
   
 pthread_mutex_t hashlock = PTHREAD_MUTEX_INITIALIZER;  
   
 struct foo {  
  int f_count;  
  pthread_mutex_t f_lock;  
  struct foo *f_next;  
  int f_id;  
 };  
   
 struct foo *foo_alloc(int id)  
 {  
  struct foo *fp;  
  int idx;  
   
  // Create the struct foo and insert into hash table  
  if ((fp = malloc(sizeof(struct foo))) != NULL) {  
   fp->f_count = 1;  
   fp->f_id = id;  
   if(pthread_mutex_init(&fp->f_lock, NULL) != 0) {  
    free(fp);  
    return NULL;  
   }  
   idx = HASH(fp);  
   pthread_mutex_lock(&hashlock);  
   fp->f_next = fh[idx];  
   fh[idx] = fp;  
   
   // We lock the f_lock here, and don't unlock it, this doesn't  
   // affect anything  
   // 1) no other threads can come here again  
   // 2) it is impossible to malloc a struct while locking on the  
   //  same mutex  
   pthread_mutex_lock(&fp->f_lock);  
   pthread_mutex_unlock(&hashlock);  
  }  
   
  return (fp);  
 }  
   
 void foo_hold(struct foo *fp)  
 {  
  // Right now hash lock is used to control the modification  
  // of any struct foo  
  pthread_mutex_lock(&hashlock);  
  fp->f_count++;  
  pthread_mutex_unlock(&hashlock);  
 }  
   
 struct foo * foo_find(int id)  
 {  
  struct foo *fp;  
  int idx;  
   
  pthread_mutex_lock(&hashlock);  
   
  // Find the struct with specified id  
  for(idx = 0; idx < NHASH; idx++) {  
   for(fp = fh[idx]; fp != NULL; fp = fp->f_next) {  
    if(fp->f_id == id) {  
     // Note that we are still using hashlock to control the  
     // modification of struct foo  
     fp->f_count++;  
     pthread_mutex_unlock(&hashlock);  
     return fp;  
    }  
   }  
  }  
   
  // If not found the struct, return NULL  
  pthread_mutex_unlock(&hashlock);  
  return NULL;  
 }  
   
 void foo_rele(struct foo*fp)  
 {  
  struct foo *tfp;  
  int idx;  
   
  pthread_mutex_lock(&hashlock);  
  // We only use the haslock to control modification of  
  // any struct  
  if(--fp->f_count == 0) {  
   idx = HASH(fp);  
   tfp = fh[idx];  
   if(tfp == fp) {  
    fh[idx] = fp->f_next;  
   } else {  
    while(tfp->f_next != fp)  
     tfp = tfp->f_next;  
    tfp->f_next = fp->f_next;  
   }  
   
   pthread_mutex_unlock(&hashlock);  
   pthread_mutex_destroy(&fp->f_lock);  
   free(fp);  
  }  
  else {  
   pthread_mutex_unlock(&hashlock);  
  }  
 }  
   
 int main(int argc, char* argv[])  
 {  
  struct foo *fp1;  
  struct foo *fp2;  
  fp1 = foo_alloc(1);  
  fp2 = foo_alloc(2);  
   
  foo_rele(fp1);  
  foo_rele(fp2);  
  exit(0);  
 }  

trade-off for multithreading programming:
If locking granularity is too coarse, you end up with too many threads blocking behind the same mutex, while little improvement possible from concurrency.
If locking granularity is too fine, then you suffer bad performance from excess locking overhead, and you end up with complex code.