data queue

[mcsummation]

NXC: Does anyone know of a library containing a queue/dequeue for simple blocks of data?

[afanofosc]

Something like that is what I am writing for my bluetooth reference implementation. What do you mean by "simple blocks of data"? Here's what I have written so far. It could use some safety checks for full queue and stuff like that.

Code: Select all

string __bt_msg_queue[];
byte __bt_msg_queue_first;
byte __bt_msg_queue_last;
mutex __bt_msg_queue_mutex;

#define QUEUE_SIZE 100

inline void ClearBTQueue() {
  ArrayInit(__bt_msg_queue, "", QUEUE_SIZE);
  __bt_msg_queue_first = 0;
  __bt_msg_queue_last  = 0;
}

#define InitBTQueue() ClearBTQueue()

inline bool IsBTQueueEmpty() { return __bt_msg_queue_first == __bt_msg_queue_last; }

safecall void __pushMsgOnBTQueue(string msg) {
  Acquire(__bt_msg_queue_mutex);
  asm {
    replace __bt_msg_queue, __bt_msg_queue, __bt_msg_queue_last, msg
    add __bt_msg_queue_last, __bt_msg_queue_last, 1
    mod __bt_msg_queue_last, __bt_msg_queue_last, QUEUE_SIZE
  }
  Release(__bt_msg_queue_mutex);
}

safecall void __popMsgOffBTQueue(string & msg) {
  if (IsBTQueueEmpty()) return;
  Acquire(__bt_msg_queue_mutex);
  asm {
    index msg, __bt_msg_queue, __bt_msg_queue_first
    add __bt_msg_queue_first, __bt_msg_queue_first, 1
    mod __bt_msg_queue_first, __bt_msg_queue_first, QUEUE_SIZE
  }
  Release(__bt_msg_queue_mutex);
}

struct FuncWith10Params {
  byte Func;
  byte ConnMailbox; // combined mailbox number and connection number
  long lparam1;
  long lparam2;
  long lparam3;
  long lparam4;
  int  iparam5;
  int  iparam6;
  int  iparam7;
  int  iparam8;
  byte bparam9;
  byte bparam10;
}; // 28 bytes

inline void SendFuncWith10Params(FuncWith10Params cmd)
{
  string msg;
  asm { flatten msg, cmd }
  __pushMsgOnBTQueue(msg);
}

It's not done yet, as you can see, but the gist of it is there. On the receiving side of this I'll be retrieving a string from a mailbox, checking the value of the first byte (Func) and calling unflatten with the correct structure type based on the value of Func. So the queue effectively becomes a template that can store up to 100 structures with each one being any type you like so long as they all start with a byte that tells the code the type of the structure.

John Hansen

[mcsummation]

Well, that is certainly different than what I was looking for, but I think it will work for what I am doing, assuming you expose the push/pop to the user level API.

Is not "safecall" and the mutexes you have doing the same thing? I understand requiring the mutexes, but it seems to me that the safecall would not be needed. Isn't safecall simply a hidden mutex?

[mattallen37]

from what I understand, safecall wraps the entire function in a mutex, so that two tasks can't even call it at the same time.

It would be like this:

Code: Select all

int add(int x, int y){
  return x+y;
}

mutex safe_add

task other(){
  while(true){
    Acquire(safe_add);
    NumOut(0, LCD_LINE1, add(Random(), Random());
    Release(safe_add);
  }
}

task main(){
  start other;
  while(true){
    Acquire(safe_add);
    NumOut(0, LCD_LINE2, add(Random(), Random());
    Release(safe_add);
  }
}

Edit: The reason for his user-code mutex(s) is to protect common resources (buffer).

[mcsummation]

Edit: The reason for his user-code mutex(s) is to protect common resources (buffer).

Isn't that what the __pushMsgOnBTQueue routine did? The mutex protects the data area much better than the safecall does. The safecall only protects that one routine, the mutex protects the data manipulated. Now, if there were code between, say the top of the routine and the mutex, then I would understand it. However, it looks to me like the actual code generated would have the safecall mutex, immediately followed by the user mutex. (Maybe John was in a hurry and didn't proof read his code for stuff like that. ) I think his code is going to get a through going over.

[afanofosc]

Marking the function as safecall means two threads can't call that particular function simultaneously. But since there are two functions you could have a case where one thread was calling push at the same time as another thread was calling pop. So you need a mutex specifically to protect access to the queue and its two pointers.

Without "safecall" the push and pop functions would not be thread-safe unless you made them inline instead. If there is a chance that two separate threads could try to push at the same time then the function either needs to be inline or safecall. If the resources used inside the function can be used by another function at the same time then you also need a mutex to protect that resource - really only for write operations or when two or more things need to be updated all together before another thread can access the resources.

John Hansen

[mcsummation]

Wait, wait, (don't tell me). (Listeners to PBS radio in the US might recognize that cry.)

Methinks I finally have it! If the compiler copies arguments into local space (call by value), then SAFECALL is needed to protect the local variable space. The mutex comes too late for that.

Now, if all the arguments are (call by reference), are the variables copied into local space and then copied back out at function end? If you are really using the callers variable space, then the mutex should do the trick.

Yes, it IS Not eXactly C. I'm slowly wending my way through the minefield that is the difference between the 2 languages.

[afanofosc]

Even if it were not for parameters, the way function calling works in the NXT firmware is inherently not thread safe. The actual call looks like this:

Code: Select all

subcall funcname, func_return_address_variable

The return inside function looks like this:

Code: Select all

subret func_return_address_variable

So if two threads tried to call this function at the same time one of them would overwrite the other's return address variable. Functions are only thread safe if they are marked as either inline or safecall.

John Hansen

[mcsummation]

My kingdom for a real, honest to gosh, stack!

Edit: So is the SAFECALL "acquire mutex" actually before the subroutine is actually called and released after the return? I guess it would have to be.

I've got to go rethink my BT wrappers.

Nope! Sometimes dumb luck wins over skill and cunning. They are all INLINE.

"dumb luck winning over skill and cunning" ought to cause doc-helmut's translation software to upchuck.