Implementing FIFOs

[alethiophile]

I'm trying to implement buffered I/O for serial and keyboard drivers. It seems obvious that what I need is a FIFO, but apparently those are usually implemented as linked lists, which seems overkill and high-memory for a simple character FIFO. My current thought is a large buffer, with read and write pointers, which are increased modulo the buffer size (making it a circular buffer). Is there any overpowering reason not to use that idea? Does anyone have any other thoughts?

[manonthemoon]

Is there any overpowering reason not to use that idea?

Not that I can think of. Just make sure that the pointers never cross each other, if the buffer fills up.

This is a perfect example of something that you should have tried on your own. You can easily do this to see if it works. You should probably familiarize yourself with basic data structures before making an OS.

Also, I believe this is how the BIOS handles keyboard input. A small circular buffer (16 or 32 bytes, can't remember) in the BDA with two pointers.

[pcmattman]

You probably want a ring buffer. As an added bonus you can usually implement them in a static or dynamic linear array (with a reader/writer pointer or offset).

Naturally this is best for single bytes, like what you expect in your keyboard buffer. For larger buffers your ring buffer will be more or less a linked list (as already pointed out by manonthemoon).

[Brendan]

Hi,

For larger buffers your ring buffer will be more or less a linked list (as already pointed out by manonthemoon).

That's my first question - how large do the buffers need to be?

A serial port running at full speed (115200 bps using "7n1") works out to 12800 characters (bytes with the high bit clear) per second. If some application checks the FIFO and removes all data every 2 seconds, then maybe you need a 32 KiB buffer "just in case". Of course it's also possible that the application can't keep up - maybe it removes 1 KiB of data per second until all of the data has arrived (and the application catches up after the data stops arriving).

Allocating huge buffers so that they are enough for rare cases seems a little silly. The alternative is to increase the size of the buffer, but a ring buffer is a pain in this case - there might be newer data at start of the buffer and older data at the end of the buffer, where the "head" and "tail" pointers point to somewhere in the middle; and you might need to allocate a new area, copy everything from the old buffer to the new area, then free the old area (which can be time consuming for large amounts of data, especially if this happens inside an IRQ handler).

I'd probably consider a linked list of buffers. For e.g. use several pages. When the "head" pointer reaches the end of the current page it allocates a new page, stores the address to the new page in the end of the old page, then begins storing new data in the new page. When the "tail" pointer reaches the end of a page it follows the link to the next page and frees the old page. Then I'd add something like "object stacks" to this - have a cache of previously used pages to reduce the need to actually allocate/free pages. When a page is freed by the FIFO buffer it's put on the top of the object stack, and when a page is allocated by the FIFO buffer it's taken from the top of the object stack if possible (and actually allocated if the object stack is empty), and if the object stack gets too large (too many free pages waiting to be reused) then you could actually free the page. You could reduce the size of the object stack (if possible) when the OS is running out of free RAM too. The end result is a FIFO buffer that grows dynamically if necessary (up to some arbitrary limit?), with no severe "overhead spikes" (e.g. caused by copying potentially large amounts of data).

However, I use asynchronous messaging (which means I'm biased), and because of this I see several problems with the design. If a thread is expecting data from many different places, then it'd need to poll many different things just to see if any data arrived from anywhere; and you'd end up with lots of pieces of code to handle lots of different FIFO buffers (in the keyboard driver, in the serial port driver, in each ethernet driver, in the mouse driver, etc, etc), rather than one piece of code to handle one FIFO buffer (or message queue) per thread; and if a thread is waiting for data the scheduler won't know when data has been received for that thread so you end up with poor latency (e.g. the thread isn't immediately given CPU time so it can process data it received, and needs to wait until the scheduler gives it CPU time for some other reason, and therefore there's a possible huge delay before the thread can process the data); and you may end up with lots of threads waking up regularly just to check if they have received something when they haven't. Of course I am biased - your way is the "traditional" way that's been used by OSs since the 1950's, and there are potential work-arounds for some of the problems (e.g. try to pretend everything is a stream and use the "select()" function) and potential problems with those work-arounds (e.g. receiving 2 bytes of a 4 byte unicode character and not knowing what to do with them until the remaining 2 bytes are received)...


Cheers,

Brendan