In embedded software development, there’s frequently a need for a FIFO implementation. Right now, I need to buffer data between my CC3000 Wi-Fi module and an HTTP parser. The CC3000 most efficiently delivers data from a Web server in large blocks (“large” in the embedded world meaning 256 bytes or more). But my HTTP parser will want to consume received data in single-byte increments — looking for breaks between header lines, for instance. So I need something between the two entities to hold on to the extra data that comes out of the CC3000 while the HTTP parser is doing its work. That’s where a FIFO comes in. I can read large blocks from the CC3000 when the FIFO gets empty, filling it back up, and the HTTP parser can grab bytes one at a time.
I had the (perhaps obvious) thought that the Linux kernel developers must also need FIFOs. Sure enough, they have a FIFO implementation called “kfifo“. And what an implementation! Through an exceptionally elegant trick of modular arithmetic, the code is so simple, it’s almost non-existent.
A FIFO needs to keep two indexes into a buffer array — an “in” index to where data is added to the FIFO, and an “out” index to where data is removed from the FIFO. When data is added, the data is placed at the “in” index of the array, and the “in” index is incremented. When data is removed from the FIFO, data is obtained from “out” index in the array, and the “out” index is incremented. This works just fine until the “in” and “out” indexes go past the end of the array. So you have to add code to check the “in” and “out” indexes after you increment them, and wrap them around to the start of the array when they go past the end. It’s also important to prevent adding new data if the FIFO is full, and prevent removing data if the FIFO is empty. More code, more conditionals, more spaghetti.
The kfifo code simplifies all those concerns. Instead of checking for “in” and “out” going past the end of the buffer array, it just lets them keep growing past the end. By observing that the wrap-around is just a form of modular arithmetic, and by requiring kfifos to have a length that’s a power of two, they can take the “in” and “out” indexes and logically-AND them with a bit mask that’s the length of the array minus 1. This turns an index into the value it would’ve been had you done the bounds checking and wrapping I described above. And because the “in” and “out” indexes no longer wrap, you don’t need complex code to calculate the difference between “in” and “out” to know how full the FIFO is — you just subtract “out” from “in”! But wait! What if you get to the point where “in” and “out” are so large that they wrap around the maximum value for their data type (probably an unsigned 32-bit or 64-bit integer)? Well, modular arithmetic again saves the day. If “in” equals 10 and “out” equals 2^32 – 10 (4294967286), and you subtract “out” from “in” using 32-bit math, you get… 20! How cool is that?!