FIFO Optimization

FIFO and pipe and both interprocess communication approaches. They have a lot in common. In fact, a fifo is often referred to as a named pipe. A fifo has properties identical to a pipe, except that it appears in the filesystem. Historically, FIFO and pipe are both implemented as socket but it has been observed that socket creation, initialization and connection cause significant overhead. For performance reason, pipe no longer use sockets since FreeBSD 2.0 but surprisingly FIFO remains unchanged until today(I don't know why). Re-implement FIFO for improved performance is greatly needed and it will benefit those applications using FIFO.

Because FIFO and pipe are similar, it is very likely that FIFO can be implemented using existing pipe code. One of the project tasks is to evaluate the possibility of merging the FIFO implementation with the pipe implementation. I have done the evaluation in this application period and the conclusion is FIFO can be implemented using pipe. The conclusion is derived from my investigation into the FreeBSD's FIFO and pipe code. Experience from other operating systems also supports the conclusion: in Linux, FIFO uses pipe implementation.

What will be delivered at the end of this project is a new FIFO system implemented using existing pipe code and test results for the new system. Possible extension is some improvements in the pipe code.

Details about the implementation: a FIFO can be considered as a special file and has its vnode interface. So major part of the project is writing vnode operations and file operations of FIFO. To merge with the pipe code, it roughly works as follows: when a FIFO is first opened, create a pipe(actually a pipe_pair), associate it with the FIFO (i.e. set FIFO's vnode->v_data to this pipe and file->f_data to either read or write end of the pipe). If a FIFO has been opened by other process, a pipe must have been created and we just set file->f_data to its read/write end. The following file operations on FIFO will be re-directed to operate on the corresponding pipe and thus we can use pipe code. Ideally the pipe code will not be touched but there are chances that pipe code need minor changes in order to be used by FIFO.

After re-writing the FIFO system, tests will be performed. There will be tests both for functionality and performance. Functionality tests will ensure that the new FIFO implementation behaves correctly. There have been FIFO bug reports, e.g. kern/74242, kern/76525, kern/94772, kern/76144, kern/116770. Most of them are for FIFO's strange behavior. Special attention will be put on these bugs and conformance testing will be written. Performance tests will be done using benchmarks. There are some universal OS benchmarks such as LMbench and HBench-OS. AFAIK, LMbench contains FIFO benchmarks and I will use it. Besides that, I will write new benchmark programs and compare the previous and new fifo implementation. This paper demonstrates some testing method, I will take them for reference:

It is probable that we will have some time to review the pipe implementation. The pipe code was written ten years ago and some tradeoffs (e.g. kva memory, pipe lock, etc) may not be suitable considering today's CPU and memory. The evaluation will be based on performance test and the same testing approach as FIFO will be adopted.

Project Status

The project status is available at

SOC2009ZhaoShuai (last edited 2009-07-07T03:27:15+0000 by ZhaoShuai)