[Tinyos-devel] SimpleArbiterP bug

[Kevin Klues]

Its definitely necessary in the case of immediateRequest().  Not so
necessary in the normal request() case.

Kevin

On Wed, Oct 15, 2008 at 10:48 AM, Razvan Musaloiu-E. <razvanm at cs.jhu.edu> wrote:
> 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
>>
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>



-- 
~Kevin