3 ms·

"There are well known data-structures that work with shared memory with well-understood behaviors with a malicious writer." I'm very interested in learning abo

"There are well known data-structures that work with shared memory with well-understood behaviors with a malicious writer." I'm very interested in learning about these shared memory data structures, would you mind providing a few links or mention some papers I could read. We implemented a real-time microkernel in university where QNX has its roots [0]. It used traditional copy based IPC however. I'd like to see how these shared-memory data structures could have been used. Thanks. [0] https://www.student.cs.uwaterloo.ca/~cs452/ https://www.student.cs.uwaterloo.ca/~cs452/

aidenn0 11y ago
I'm actually struggling to find this in the literature, but I've seen it used more than once. Here's the most simple version: Minimum two pages, each readable from both sides and one is writable from each side. You need this even for a single-directional queue. Have a simple post/ack counter that is modulo something much larger than the size of the queue (i.e. an unsigned long on most architectures). If (post - ack) is ever greater than the size of the queue, the queue should be considered no longer safe to use; both readers and writers should check this anytime they access these values. Otherwise there are (post - ack) bytes pending in the queue. To write, write bytes at (post MOD size) and increment post; to read, read from (ack MOD size) and increment ack. That is a simple one-to-one byte-stream queue; fixed-size message queues are an obvious change, non-fixed size message queues are significantly more complex, but proceed from the same idea. Many-to-one queues are a lot more complex, and one-to-many is more complex if you want reliable data transfer, but much simpler if you don't (just eliminate the ack completely) If all you care about is throughput and you have more than 2 cores, then just spinning on post/ack is sufficient. Otherwise some synchronization primitive is needed. On many real-world architectures, particularly SMP ones there are a lot of fiddly details to get right with the MMU &ct. but the underlying idea is simple.

aidenn0 11y ago

I'm actually struggling to find this in the literature, but I've seen it used more than once. Here's the most simple version: Minimum two pages, each readable from both sides and one is writable from each side. You need this even for a single-directional queue. Have a simple post/ack counter that is modulo something much larger than the size of the queue (i.e. an unsigned long on most architectures). If (post - ack) is ever greater than the size of the queue, the queue should be considered no longer safe to use; both readers and writers should check this anytime they access these values. Otherwise there are (post - ack) bytes pending in the queue. To write, write bytes at (post MOD size) and increment post; to read, read from (ack MOD size) and increment ack. That is a simple one-to-one byte-stream queue; fixed-size message queues are an obvious change, non-fixed size message queues are significantly more complex, but proceed from the same idea. Many-to-one queues are a lot more complex, and one-to-many is more complex if you want reliable data transfer, but much simpler if you don't (just eliminate the ack completely) If all you care about is throughput and you have more than 2 cores, then just spinning on post/ack is sufficient. Otherwise some synchronization primitive is needed. On many real-world architectures, particularly SMP ones there are a lot of fiddly details to get right with the MMU &ct. but the underlying idea is simple.