multithreading - Shared counter using combining tree deadlock issue -

i working on shared counter increment application using combining tree concept. goal make application work on 2^n number of cores such 4, 8, 16, 32, etc. algorithm might err on thread failure. assumption there no thread failure or slow threads.

• two threads compete @ leaf nodes , latter 1 arriving goes tree.
• the first 1 arrives waits until second 1 goes hierarchy , comes down correct return value.
• the second thread wakes first thread up
• each thread gets correct fetchandadd value

but algorithm gets locked inside while (nodes[index].isactive == 1) or while(nodes[index].waiting == 1) loop. don't see possibility of deadlock because 2 threads competing @ each node. guys enlighten me on problem??

int increment(int threadid, int index, int value) {     int lastvalue = __sync_fetch_and_add(&nodes[index].firstvalue, value);     if (index == 0) return lastvalue;     while (nodes[index].isactive == 1) {     }     if (lastvalue == 0) {         while(nodes[index].waiting == 1) {         }         nodes[index].waiting = 1;         nodes[lindex].isactive = 0;     } else {         nodes[index].isactive = 1;         nodes[index].result = increment(threadid, (index - 1)/2, nodes[index].firstvalue);             nodes[index].firstvalue = 0;             nodes[index].waiting = 0;     }     return nodes[index].result + lastvalue; } 

i don't think work on 1 core. infinitely loop on isactive because can't set isactive 0 unless 0.

i'm not sure if you're code has mechanism stop but, here's best crack @ here threads run , cause problems:

ex)

thread1                         thread 2 nodes[10].isactive = 1                                 //next run on index 10                                 while (nodes[index].isactive == 1) {//here deadlock} 

it's hard understand what's going on here/ you're trying recommend somehow need able deactivate nodes[index].isactive. may want set 0 @ end of function