10.6. C-lists The terminal I/O system deals with data in blocks of widely varying sizes. Most input and output operations deal with single characters (typed input characters and their output echoes). Input characters are usually aggregated with previous input to form lines of varying sizes. Some output operations involve larger amounts of data, such as screen updates or other command output. The data structures originally designed for terminal drivers, the character block, C-block, and character list, C-list, are still in use in FreeBSD. Each C-block is a fixed-size buffer that contains a linkage pointer and space for buffered characters and quoting information. Its size is a power of 2, and it is aligned such that the system can compute boundaries between blocks by masking off the low-order bits of a pointer. FreeBSD uses 128-byte C-blocks, storing 108 characters and an array of quoting flags (1-bit per character). A queue of input or output characters is described by a C-list, which contains pointers to the first and final characters and a count of the number of characters in the queue (see Figure 10.1). Both of the pointers point to characters stored in C-blocks. When a character is removed from a C-list queue, the count is decremented, and the pointer to the first character is incremented. If the pointer has advanced beyond the end of the first C-block on the queue, the pointer to the next C-block is obtained from the forward pointer at the start of the current C-block. After the forward pointer is updated, the empty C-block is placed on a free chain. A similar process adds a character to a queue. If there is no room in the current buffer, another buffer is allocated from the free list, the linkage pointer of the last buffer is set to point at the new buffer, and the tail pointer is set to the first storage location of the new buffer. The character is stored at the location pointed to by the tail pointer, the tail pointer is incremented, and the character count is incremented. A set of utility routines manipulates C-lists: getc() removes the next character from a C-list and returns that character and putc() adds a character to the end of a C-list. The getc() routine returns an integer, and the putc() routine takes an integer as an argument. The lower 8 bits of this value are the actual character. The upper bits are used to provide quoting and other information. Groups of characters may be added to or removed from C-lists with b_to_q() and q_to_b(), respectively, in which case no additional information (e.g., quoting information) can be specified or returned. The terminal driver also requires the ability to remove a character from the end of a queue with unputc(), to examine characters in the queue with nextc(), and to concatenate queues with catq(). Figure 10.1. A C-list structure.
When UNIX was developed on computers with small address spaces, the design of buffers for the use of terminal drivers was a challenge. The C-list and C-block provided an elegant solution to the problem of storing arbitrary-length queues of data for terminal input and output queues when the latter were designed for machines with small memories. On modern machines that have far larger address spaces, it would be better to use a data structure that uses less CPU time per character at a cost of reduced space efficiency. FreeBSD still uses the original C-list data structure because of the high labor cost of converting to a new data structure; a change to the queue structure would require changes to all the line disciplines and to all the terminal device drivers, which would be a substantial amount of work. The developers could change just the implementations of the interface routines, but the routines would still be called once per character unless the actual interface was changed, and changing the interface would require changing the drivers. |