Pipes

18 Dec 2013

In most unix-like systems, pipes can be used to make processes communicate with each other. To the processes the pipe looks just like any other file, but when one process tries to read from it, it will get the data the other process wrote.

With a couple of hints from the people at #osdev on irc.freenode.net, I finally got pipes to work - although a bit inefficiently - the way I wanted a few days ago.

I implemented pipes as circular buffers, which makes them a perfect example of the "producer-consumer problem" which is well known in operating system theory. The schoolbook solution to the problem uses sleeping processes in roughly the following way:

Producer/Writer:

  • Write until all bytes are written or until the buffer is full.
  • Wake any processes that are sleeping on the buffer.
  • If you have more bytes to write, go to sleep on the buffer and then repeat.

Consumer/Reader:

  • Read until all bytes are read or until the buffer is empty.
  • Wake any processes that are sleeping on the buffer.
  • If there were no bytes to read, go to sleep on the buffer and then repeat.

In code this translates to

uint32_t pipe_write(INODE ino, void *buffer, uint32_t size, uint32_t offset)
{
    vfs_pipe_t *pipe = (vfs_pipe_t *)ino->data;
    char *buf = (char *)buffer;
    uint32_t bytes_written = 0;
    while(bytes_written < size)
    {
        while((pipe->write_pos - pipe->read_pos) < pipe->size && bytes_written < size)
        {
            pipe->buffer[pipe->write_pos % pipe->size] = buf[bytes_written];
            bytes_written++;
            pipe->write_pos++;
        }
        scheduler_wake(&pipe->waiting);
        if(bytes_written < size)
        {
            scheduler_sleep(current, &pipe->waiting);
            schedule();
        }
    }
    return bytes_written;
}

uint32_t pipe_read(INODE ino, void *buffer, uint32_t size, uint32_t offset)
{
    vfs_pipe_t *pipe = (vfs_pipe_t *)ino->data;
    char *buf = (char *)buffer;
    uint32_t bytes_read = 0;
    while(bytes_read == 0)
    {
        while((pipe->write_pos - pipe->read_pos) > 0 && bytes_read < size)
        {
            buf[bytes_read] = pipe->buffer[pipe->read_pos % pipe->size];
            bytes_read++;
            pipe->read_pos++;
        }
        scheduler_wake(&pipe->waiting);
        if(bytes_read == 0)
        {
            scheduler_sleep(current, &pipe->waiting);
            schedule();
        }
    }
    return bytes_read;
}

Of course there should also be:

  • Sanity checking.
  • A lock to prevent reading and writing at the same time.
  • Handling of the cases where there are no readers or no writers.

Note that the reader only blocks if no bytes at all have been read, while the writer blocks if not all bytes have been written.

Creating a new pipe is a bit special, though. An ordinary pipe has two ends, one for writing and one for reading. The best way I found to implement this is to have the pipe represented by two separate inodes - one that can be written to and one that can be read from. The data field of the vfs_node_st struct of the two inodes point to the same pipe struct.

typedef struct vfs_pipe
{
    char *buffer;
    uint32_t size;
    uint32_t read_pos;
    uint32_t write_pos;
    uint32_t readers;
    uint32_t writers;
    semaphore_t semaphore;
    list_head_t waiting;
} vfs_pipe_t;

The readers and writers fields are incremented or decremented when the read or write end respectively are opened or closed... respectively...

Creating a new pipe (somewhat simplified):

uint32_t new_pipe(uint32_t size, INODE *nodes)
{
    vfs_pipe_t *pipe = calloc(1, sizeof(vfs_pipe_t));
    pipe->buffer = malloc(size);
    pipe->size = size;

    nodes[0] = calloc(1, sizeof(vfs_node_t));
    nodes[0]->d = &pipe_driver;
    nodes[0]->data = pipe;
    nodes[0]->flags = PIPE_READ;

    nodes[1] = calloc(1, sizeof(vfs_node_t));
    nodes[1]->d = &pipe_driver;
    nodes[1]->data = pipe;
    nodes[1]->flags = PIPE_WRITE;

    return 0;
}

Using pipes

When starting up the keyboard driver, a pipe is created and connected to stdin - the first file descriptor - of the current process.

void keyboard_init()
{
    INODE tmp[2];
    new_pipe(1024, tmp);

    keyboard_pipe = tmp[1];
    vfs_open(keyboard_pipe, O_WRONLY);

    process_t *p = current->proc;
    p->fd[0] = calloc(1, sizeof(file_desc_t));
    fd_get(p->fd[0]);
    p->fd[0]->ino = tmp[0];
    p->fd[0]->flags = O_RDONLY;
    vfs_open(tmp[0], O_RDONLY);

    register_int_handler(IRQ2INT(IRQ_KBD), keyboard_handler);
}

The keyboard handler (based off Brandon Friesen's tutorial writes each decoded key to the pipe:

registers_t *keyboard_handler(registers_t *r)
{
    char code[2];

    [...]

    while(inb(KBD_STATUS_PORT) & 0x2);
    scancode = inb(KBD_DATA_PORT);
    code[0] = keyboard_decode(scancode);
    code[1] = '\0';
    if(code[0])
    {
        vfs_write(keyboard_pipe, (char *)code, 1, 0);
    }

    [...]

}

At a later stage, I'll probably make the keyboard driver in the kernel just pass the scancodes to the pipe and have the decoding done by a terminal process which in turn pipes the decoded keys on to the shell, and so on...

Next step is to add an actual filesystem! Of sorts...

Comments

comments powered by Disqus
© 2012 Thomas Lovén - @thomasloven - GitHub