[Tinyos-devel] SimpleArbiterP bug

[Philip Levis]

I think this is a bug in SimpleArbiterP, but wanted to check with  
everyone to make sure. In particular, whether there are existing  
systems which depend on the current behavior, such that fixing it  
would break them.

A bit of background: arbiters (power locks) are built around  
SimpleArbiterP. SimpleArbiterP uses a queue interface, and the  
implementation of that queue interface controls its locking policy  
(e.g., First-come, first-served vs. round-robin).

The test case is as follows. I'm using indentation to show the call  
graph. E.g., 2a is called on 2's stack frame.

1. Client A requests and acquires power lock P
2. Client B requests power lock P
2a.  P signals to Client A that the lock has been requested
2aa.   Client A releases P
2ab.   Client A re-requests P

In this case, I think that P should grant to B; 2aa and 2ab are a  
yield from A. When B releases the lock, A will re-acquire it. However,  
the request code looks like this (immediateRequest is similar):

   async command error_t Resource.request[uint8_t id]() {
     signal ResourceRequested.requested[resId]();
     atomic {
       if(state == RES_CONTROLLED) {
         state = RES_GRANTING;
         reqResId = id;
       }
       else return call Queue.enqueue(id);
     }
     signal ResourceDefaultOwner.requested();
     return SUCCESS;
   }

Because requested() is signaled before the caller's request is put on  
the queue, then in the case above, this is what happens:

1. Client A requests and acquires power lock P
2. Client B requests power lock P
2a.  P signals to Client A that the lock has been requested
2aa.   Client A releases P
2ab.   Client A re-requests P
2aba.    P puts A at head of queue
2abb.    P posts a task to grant A the lock
2b.  P puts B on queue
....
3. A re-acquires lock, while B is waiting on queue

I think the code should be this:

   async command error_t Resource.request[uint8_t id]() {
     bool getsNow = TRUE;
     atomic {
       if(state == RES_CONTROLLED) {
         state = RES_GRANTING;
         reqResId = id;
         getsNow = FALSE;
       }
     }
     if (getsNow == FALSE) {
       error_t rval = call Queue.enqueue(id);
       signal ResourceRequested.requested[resId]();
       return rval;
     }
     else {
       signal ResourceDefaultOwner.requested();
       return SUCCESS;
     }
   }

Thoughts?

Phil