Terminals in *nix

Terminals were hardware devices that consisted of a keyboard and an output device (initially a line printer, later a CRT monitor). A large computer could have several remote terminals connected to it. Each terminal would have a protocol for communicating efficiently with the computer, for CRT-based terminals this includes having special "control sequences" to change cursor position, erase parts of the current line/screen, switch to an alternate full-screen mode, ...

A terminal emulator is an application emulating one of those older terminals. It allows to do functions like cursor positioning, setting foreground and background colors, ... Terminal emulators try to emulate some specific terminal protocol, but each has its own set of quirks and deviations.

Unix systems have databases describing terminals and terminal emulators, so applications are abstracted away from the particular terminal (or terminal emulator) in use. An older database is termcap(5), while terminfo(5) is a newer database. These databases allow applications to query for the capabilities of the terminal in use. Capabilities can be booleans, numeric capabilities, or even string capabilities, e.g.: if a specific terminal type has/supports a F12 key, it will have a capability "key_f12" (long terminfo name), "kf12" (short terminfo name), "F2" (termcap name) describing the string that key produces. Try it with: tput kf12 | od -tx1.

Since programming directly with capabilities can be cumbersome, applications typically use a higher-level library like curses/ncurses, slang, etc...

There is a special environment variable called TERM that tells applications what terminal type they are talking to. This variable should be set to the exact terminal type if it exists in the database, for best results. This just tells the application which precise protocol and protocol deviations does the terminal understand. Changing the TERM variable does not change the terminal type, it just changes the terminal type the application thinks it is talking to.

dmr

I remember SuSE Linux had a motd that simply said: "Have fun..." That has always been the spirit of Unix, having an environment in which it is fun to work and tinker about. We owe that to Ken Thompson, Dennis Ritchie and their colleagues at Bell Labs (http://www.princeton.edu/~hos/Mahoney/unixpeople.htm).

Dennis Ritchie also evolved Thompson's B into C, giving us a concise and practical systems programming language. Kernighan and Ritchie taught many people how to write great code, some of those people taught other people, directly, or simply by sharing great code. The end result has been a ripple effect that has had a profound and positive impact on how many of us code. Not many people in history have influenced the work of others so much.

Dennis Ritchie is no longer with us, he will be greatly missed. He is among those luminaries we will never forget. The computing community will never forget Jon Postel, Richard Stevens and Dennis Ritchie.

Obituaries:
http://www.nytimes.com/2011/10/14/technology/dennis-ritchie-programming-trailblazer-dies-at-70.html?hp
http://www.guardian.co.uk/technology/2011/oct/13/dennis-ritchie
http://www.bbc.co.uk/news/technology-15287391

Introduction to regexes

Let Σ be an alphabet.

• ε (the empty string) is a regular expression.
• If a is a symbol from the alphabet Σ, a is a regular expression.
• If a and b are symbols from the alphabet Σ, ab (a and b concatenated) is a regular expression.
• If a and b are symbols from the alphabet Σ, a|b (a or b) is a regular expression.
• If a is a symbol from the alphabet Σ, a* (a repeated 0 or more times) is a regular expression.

A regular language is the language defined by a regular expression. A regular language is the language matched by a finite automaton. A word w from a regular language can be recognized in O(n).

Unix regexes:

• . means any character.
• Concatenation is represented without any symbol.
• Union (alternation) is represented by |.
• * means Kleene closure (0 or more repetitions).
• + means 1 or more repetitions.
• ? means 0 or 1 repetition.
• ^ means start of line.
• $ means end of line.
• \< means start of word (in some programs).
• \> means end of word (in some programs).
• {n} means n repetitions (in some programs).
• {,m} means from 0 to m repetitions (in some programs).
• {n,m} means from n to m repetitions (in some programs).
• a|b|c|d|e|f can be written as [abcdef] or [a-f].
• a|b|c|d|h|i can be written as [a-dhi] or [a-dh-i], ...
• [^list] matches characters not in list.
• () is used for grouping.
• \ escapes special meaning of a metacharacter, e.g.: \*

Precedence is: repetition, concatenation, union.

The supported regular expression syntax varies among programs, (e.g: gawk vs mawk, vi vs vim, ...).

Back-references:

Many programs allow the use of \n (where n is a number) to match a subexpression enclosed in () or \(\), e.g: in vim, \<\(.\)\(.\).\2\1\> matches five-letter palindromes. Regular expressions using these back-references are no longer true regular expressions, and not all of them can be matched in O(n) time.

Regex/Regexp vs regular expressions:

Since modern regexes match things that cannot be matched with true regular expressions, it's been proposed (by Larry Wall) to call them regexes, not regular expressions. Perl regexes have been gaining expressive power through the years, and have grown, among many other things, support for look-around assertions, support for calling Perl code, and support for recursion. Many regex engines have taken things from Perl's regexes. On the other hand, Google's re2 library uses true regular expressions and a DFA-based implementation (in contrast to the NFA-based implementation of backtracking-regex engines) to achieve very high performance.

vfork()

There are some limitations to using non-MMU CPUs in *nix, e.g: there are restrictions to fork(), mmap(), shmat() and brk(). Let's talk about fork().

fork(2) creates a child process with a copy of the memory of the current process (and a copy of the file descriptors, signal handlers, filesystem namespace, ...) This copy has the same virtual addresses as those used on the parent. In a CPU with a MMU, the MMU translates each process' virtual addresses to different physical addresses, so everything works and everyone is happy.

However, in a MMU-less CPU, virtual addresses are the same as physical addresses (said another way, there are no virtual addresses), so fork() cannot work in a MMU-less system in the general case (at least in an efficient manner, you can always move processes in memory at each context switch).

Often, fork(2) is used to immediately call execve(2) in the child. There is a special system call fot this: vfork(2). Typically, vfork() doesn't create a new copy of the parent's memory, but uses the parent's memory. It's also typical for the parent to remain blocked until the child calls execve() or _exit().

The only safe things you can do after vfork() on the child are the following:

• Calling execve().
• Calling _exit() (Note it's _exit(), not exit(), exit() can run C library finalization code, such as closing and freeing file handles, which in vfork() implementations using the parent's memory would also close and free them for the parent, leading to very bad things).
• Use the pid_t value returned by vfork().

Of course, vfork() can be implemented simply as:

#define vfork fork

As vfork() uses a shared address space, it works perfectly fine on non-MMU CPUs. Also, creating a child to immediately call execve() is a very common use of fork()/vfork().

The other *nix classical API to create processes/threads/tasks is pthread_create(). As the different threads share the memory address space, this works for non-MMU CPUs. POSIX also introduces a posix_spawn() function.

In the specific case of Linux, there is also clone(2). In non-MMU CPUs, clone() works fine if it's passed the CLONE_VM flag.

An interesting detail in vfork() (explained by Jamie Loker at uclinux-dev at http://www.mail-archive.com/uclinux-dev@uclinux.org/msg01290.html) is how it's implemented in uClibc:


__vfork:
popl %ecx
movl $__NR_vfork,%eax
int $0x80
pushl %ecx
cmpl $-4095,%eax
jae __syscall_error
ret


When you call vfork(), Linux first returns control to the child. The parent hasn't yet returned from vfork(). The call to execve() in the child can corrupt vfork()'s stack frame in the parent.

The solution is not depending on vfork()'s stack frame. In the previous i386 example, the first thing that is done is save the return address (which is the only think saved on vfork()'s stack frame, as vfork() has neither parameters nor local variables) in a register, where it is safe. The int $0x80 instruction is the one to pass control to sys_vfork() at the kernel. On return from sys_vfork(), we push the return address into the stack frame again, check for errors, and return from vfork().

(Originally published at http://barrapunto.com/~ninjalj/journal/27731 (in Spanish))

Character by Character Input on *nix

A frequently asked question is how to read a single key on *nix. Many people expect read(2) of a single byte to return immediately, but by default it doesn't.

On Unix you don't deal with keyboards, you deal with a terminal. A terminal can be the physical console, a terminal (or terminal emulator) on a serial port, an xterm, ...

By default, input lines are not made available to programs until the terminal (or terminal emulator) sees a line delimiter.

On POSIX, terminals are controlled by the termios(3) functions. These include tcgetattr(3) and tcsetattr(3), which can be used to modify terminal attributes. These include input modes, output modes, and local modes.

One of the local modes is canonical mode (enabled by default), in which input is made available line by line, and certain line editing characters are enabled.

So, to read input character by character, you need to do something like the following:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include <unistd.h>
#include <poll.h>
#include <signal.h>
#include <termios.h>
#include <sys/ioctl.h>

static volatile sig_atomic_t end = 0;

static void sighandler(int signo)
{
        end = 1;
}

int main()
{
        struct termios oldtio, curtio;
        struct sigaction sa;

        /* Save stdin terminal attributes */
        if (tcgetattr(0, &oldtio) < 0) {
                perror("tcgetattr");
                exit(1);
        }

        /* Make sure we exit cleanly */
        memset(&sa, 0, sizeof(struct sigaction));
        sa.sa_handler = sighandler;
        if (sigaction(SIGINT, &sa, NULL) < 0) {
                perror("sigaction");
                exit(1);
        }
        if (sigaction(SIGQUIT, &sa, NULL) < 0) {
                perror("sigaction");
                exit(1);
        }
        if (sigaction(SIGTERM, &sa, NULL) < 0) {
                perror("sigaction");
                exit(1);
        }

        /* This is needed to be able to tcsetattr() after a hangup (Ctrl-C)
         * see tcsetattr() on POSIX
         */
        memset(&sa, 0, sizeof(struct sigaction));
        sa.sa_handler = SIG_IGN;
        if (sigaction(SIGTTOU, &sa, NULL) < 0) {
                perror("sigaction");
                exit(1);
        }

        /* Set non-canonical no-echo for stdin */
        if (tcgetattr(0, &curtio) < 0) {
                perror("tcgetattr");
                exit(1);
        }
        curtio.c_lflag &= ~(ICANON | ECHO);
        /* This could be interrupted by a signal if it used
         * TCSADRAIN or TCSAFLUSH, but it wouldn't matter, since
         * we would have not changed terminal attributes yet
         */
        if (tcsetattr(0, TCSANOW, &curtio) < 0) {
                perror("tcsetattr");
                exit(1);
        }
        if (tcgetattr(0, &curtio) < 0) {
                perror("tcgetattr");
                exit(1);
        }
        if (curtio.c_lflag & (ICANON | ECHO)) {
                fprintf(stderr, "couldn't set non-canonical no-echo mode\n");
                exit(1);
        }

        /* main loop */
        while (!end) {
                struct pollfd pfds[1];
                int ret;
                char c;

                /* See if there is data available */
                pfds[0].fd = 0;
                pfds[0].events = POLLIN;
                ret = poll(pfds, 1, 0);
                if (ret < 0 && errno != EINTR) {
                        perror("poll");
                        exit(1);
                }

                /* Consume data */
                if (ret > 0) {
                        printf("Data available\n");
                        if (read(0, &c, 1) < 0 && errno != EINTR) {
                                perror("read");
                                exit(1);
                        }
                }
        }

        /* restore terminal attributes */
        /* This could be interrupted by a signal if it used TCSADRAIN
         * or TCSAFLUSH
         */
        if (tcsetattr(0, TCSANOW, &oldtio) < 0) {
                perror("tcsetattr");
                exit(1);
        }

        return 0;
}