[Tinyos-devel] SimpleArbiterP bug

[Razvan Musaloiu-E.]

Hi!

On Wed, 15 Oct 2008, Philip Levis wrote:

> 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]();

Is this signal absolutely necessary here? Could we move it to a taks? What 
we have here is basically an instance of the first programming hint:
 	It dangerous to signal events from commands, as you might cause a
 	very long call loop, corrupt memory and crash your program.

--
Razvan ME

>     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
>
>
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>