Why *just* a ring buffer?
Posted Aug 3, 2006 6:54 UTC (Thu) by AnswerGuy
Parent article: Toward a kernel events interface
So, regarding the level triggering issue, why just having a ring buffer?
Why not have a structure which consists of one fixed region (set of flags, a fixed array of some sort) ... and a ring buffer?
For example one might have a bit vector representing the clear/blocking state of each file descriptor. These are updated by the kernel as it maintains this memory mapping (along with the head/tail pointers of the ring, of course). Then checking for "would block" is simply a matter of an scaled array dereference and some AND masking.
The question becomes ... what are the optimal set of additional fields to this structure. (For example a large bit vector would be a pain to scan through ... searching for "writable" descriptors ... but having the kernel update some tree of indices might be gilding the lily. (This tree of indices might work like this: let's say you had a tree --- one 32-bit value gives status of each of 32-words ... so each bit in the index says that some of the bits in the corresponding word are set. This saves you from having to loop through all 32-words checking for the first non-zero value --- you can determine if they are all clear in one operation and find the first one that has any set bits with only one register fetch and a small number of quick operations. If you extend this structure to two layers then you can manage 32K bits in 1057 words --- the top index, the 32 middle indices, and the 1024 words for your bit vector at the bottom; and finding the first available "set" bit would be a linear three fetches and a handful of masking or shifting operations and bit checks. The kernel would have two extra stores and a handful of OR operations to update these; with just one index into one 32-word bit vector you could over 1024 file descriptors using 33 words, obviously).
Of course I'm only giving a silly example based one specific use case that might arise from the need described in that penultimate paragraph. I really have no idea how many "level triggered" events/checks would be needed in this unified event interface and I have no idea how critical finding the "first set bit" in such a vector might be nor even how many file descriptors might have to be supported.
My point is that the basic technique doesn't have to be limited to just a ring buffer.
to post comments)