Anatomy of a bug in select

In the previous article we discussed problems with multiplexing Linux facilities informally.

Here we are going to discuss

select

using more precise language and with more technical details.

Preliminary Notes:
It is assumed that readers can run commands

man

and

info

and read

header files on a Linux machine, or can read POSIX docs, manpages, infopages, and header files on Internet. It lets us refer to the documentation without extensive quoting.

What file descriptors are assigned to sockets
When files, sockets and other file-like objects are opened or created, Linux usually assigns them the smallest

fd

not occupied by another object. After the objects close, their

fd

are recycled. If there was no «holes» in the range of active

fd

, or after all the «holes» were reused,

fd

are assigned sequentially in a sense that a freshly assigned

fd

is a number directly following the biggest active

fd

It follows that a socket with

fd

equal to, for example, 1234, was created when all

fd

in a range 0 – 1233 were in use, but

fd

slot #1234 was free to grab. At least 1233 files, sockets, or similar objects where open at the moment. More if slot #1234 was inside a «hole» between active

fd

Let us emphasize that the thousands active

fd

may belong not only to sockets, but also to «usual» files and objects of other types, like pipes, devices, or events.

Let us notice also that one or multiple smaller

fd

may be closed and released after a socket with a high

fd

was created. The latter still will retain its big

fd

Anatomy of
select

To represent what

fd

to watch,

select

uses data type

fd_set

. The type is opaque, but documentation provides a general guidance on its internal structure.

Opaque means that internal details of the structure are not defined nor described in POSIX. System programmers who develop operation systems and libraries have a leeway in implementation. Application developers should not expect the structure to be the same on different operation systems. It even may change in future versions of the same operation system. It follows that the application programmers should not access and manipulate the content of

fd_set

directly. They should use functions, or rather macros, that POSIX provides for the purpose:

  void FD_ZERO (fd_set *set) /* erases all elements from a set of fd */
  void FD_SET (int fd, fd_set *set) /* adds a specific fd to a set */
  void FD_CLR (int fd, fd_set *set) /* removes a specific fd from a set */
  int FD_ISSET (int fd, const fd_set *set) /* queries, if a specific fd is an element of a set */

However, the freedom of system developers in designing the internal structure is limited by POSIX. According to the standard,

fd_set

must be «file descriptor masks». POSIX tells also that

FD_SET

and

FD_CLR

have undefined behavior when their argument

fd

is equal or higher than

FD_SETSIZE

- even if the

fd

is a valid file descriptor.

Linux implementation follows the guidance. According to Linux infopage,

fd_set

«is actually a bit array». Linux manpage says that

fd_set

is «a fixed size buffer».

To get more detailed info on Linux implementation, i.e. to see the internal structure of Linux

fd_set

and how the macros are defined, we can peek into the two header files:

12	/usr/include/sys/select.h /usr/include/bits/select.h

Strictly speaking, the headers are for a specific version of Linux, but the data structure should be reasonably stable, because changing it would break a binary compatibility. People would not happy if a compiled code stop working after an upgrade to a next version of operation system.

As it was expected,

fd_set

is a bit arrays of a fixed size. With 8 bits per byte, the size of the array is

FD_SETSIZE

/ 8 bytes. On a typical Linux system it is 128 bytes. Each

fd

in the set is represented by a binary 1.

fd

not included in a set are represented by binary 0.

We can see also that in a current Linux implementation

FD_SET

and

FD_CLR

macros do not check if argument

fd

is out of the array bounds. It follows that, if called with an argument

fd >= FD_SETSIZE

, the macros would modify bytes located out of the array bounds.

Function

   int select (int stop, /* can be used for optimization, see below */
               /* pointers to three monitored sets of fd: */
               fd_set *rd, /* Ready to read */
               fd_set *wrt, /* Ready to write */
               fd_set *excpt, /* Exceptional conditions */

               struct timeval *timeout) /* timeout structure, irrelevant for our discussion */

has five arguments. Generally, it monitors the three sets of

fd

Ready to read:
- Data sent from a remote side appeared on a regular socket.
- A request to connect was received by a listening socket.
Ready to write: A socket connection is established.
Exceptional conditions: Out of Band message («urgent message») is on the socket.

Let us consider, for simplicity, a case when only «Ready to read» condition is monitored. We do not need anything more elaborate to show how problems occur with

select

. Also, it is a very typical usage case, particularly for TCP/IP sockets.

The function returns the total number of

fd

on which monitored conditions occurred. The value is zero when the function returns because of a timeout. It is equal to −1 when the function returns because of errors in data. In a typical case, when an event occurs on a single socket, it returns 1. However, it may return bigger values - when data arrives simultaneously on several sockets.

The function also returns, in calling arguments passed by pointers, information on what

fd

a monitored condition occurred. For this,

select

overwrites the content of

fd_set

arguments.

select

supports two optimization:

A calling code can supply pointers to empty
```
fd_set
```
when not interested in monitoring some of conditions, but it is less than optimal. The empty
```
fd_set
```
will eat memory, they must be initialized, and
```
select
```
must scan their content. Alternatively, NULL pointers may be passed to
```
select
```
, meaning that the respective events should not be monitored. In the most usual case, when
```
fd
```
are monitored only for read,
```
select
```
is called as following:
1
select (FD_SETSIZE, &rd_set, NULL, NULL, &the_timeout);

It happens often that all
```
fd
```
to watch have small values. For example, our codes watch for requests to connect on a single listener socket that was created during startup. It is very likely that operation system will assign the socket a small
```
fd
```
, something like 5 or 10 or 20. It would be inefficient for
```
select
```
to scan all
```
FD_SETSIZE
```
, i.e. 1024 bits in fd_set, if we know already that it should stop much earlier. The first argument of
```
select
```
tells the function where to stop the scan:
1
select (fd + 1, &read_set, NULL, NULL, &the_timeout);
Yes, the first argument is not
```
fd
```
, but
```
fd+1
```
.

Another example: we know that data are going to be sent to our server by dozens of slow clients. We can multiplex the input to process all the data in a single thread. For this we will watch all respective sockets. An optimization is still possible:

1234	/* maximal fd over a watched set of sockets */ int max_fd = ... ... select (max_fd + 1, &read_set, NULL, NULL, &the_timeout);

By the way, when the first argument is equal to zero,

select

does not watch for conditions on any

fd

, but still returns on a timeout. The behavior is often used to implement timers.

What is wrong with
select

In short,

select

does not scale well with a number of

fd

, even when the

fd

are not monitored and/or are not sockets:

Initially,
```
select
```
becomes inefficient.
After the number of
```
fd
```
exceeds
```
FD_SETSIZE
```
, the behavior of
```
select
```
becomes undefined. In a practice, the behavior is catastrophic:
```
select
```
corrupts stack.

Inefficiency
The optimization using a first argument of

select

stops to work as an optimization when a maximum value of a

fd

set is big. The function has to scan a long sub‑array of

fd_set

looking for binary 1. It would be OK when most of

fd

are sockets and you really need to monitor most of them. However, more typically most of the scanned

fd

never will be watched. Many of them belong to «usual» files, not sockets. Or the

fd

may be closed already. In more general terms, the

fd_set

bit array is sparse - and, as usual, it is inefficient to represent a sparse array the same way as a dense one.

Another inefficiency is caused by returning results in the same structures in which input data are passed to function

select

: the data structures must be filled again and again before every call to the function.

Catastrophic behavior
Let us consider, step by step, what happens with a typical program code involving

select

when we attempt to watch for a

socket_fd

bigger than

FD_SETSIZE - 1

fd_set read_set; /* fixed size data structure in a stack */
FD_ZERO (read_set); /* clears all fd smaller than FD_SETSIZE */
FD_SET (socket_fd, read_set); /* modifies bit socket_fd % 8 of a byte at
                                 address &read_set + (socket_fd / 8). 
                                 The address is higher than the upper bound of read_set. */
int ret_value = select (socket_fd + 1, &read_set, NULL, NULL, &the_timeout);

Even before

select

is called,

FD_SET

may already corrupt one bit located out of the bounds of a bit array

read_set

. The bit may be a part of local data. Or, if a stack grows down, as it is standard for x86, x86-64, and many other architectures, the bit may be located in a stack frame. For example, it can be a part of a return address used by a calling function.

A set of

fd

passed to the function to monitor is represented by binary 1 stored between 0-th bit of a byte at address

&read_set

and

socket_fd

inclusive. All bits corresponding to

fd

smaller than

FD_SETSIZE

were cleared by

FD_ZERO

, i.e. they are equal zero. However, bits starting from

FD_SETSIZE

and till

socket_fd - 1

were neither cleaned nor set by macros. They may store arbitrary values. A programmer likely would expect that the bits also were cleared by

FD_ZERO

Function

select

does the following:

Should and may verify the validity of its first argument,
```
socket_fd+1
```
. According to POSIX, it is not an options: when the argument is bigger than
```
FD_SETSIZE-1
```
, function
```
select
```
should return immediately with
```
ret_value
```
equal −1 and
```
errno
```
equal
```
EINVAL
```
. However, a Linux implementation of
```
select
```
does not conform to POSIX in the respect.

Verifies that a set of
```
fd
```
passed in a second argument are valid, i.e. all "1" bits correspond to open files, sockets, and similar objects. If even one of these bits does not correspond to an open file, function
```
select
```
returns with
```
ret_value
```
equal −1 and
```
errno
```
equal
```
EBADF
```
.

Please, notice that the set of
```
fd
```
spills out the upper border of
```
read_set
```
up to a bit with index
```
socket_fd
```
.

Monitors the above set of
```
fd
```
for «Ready to read» conditions. As we mentioned above, in addition to
```
socket_fd
```
that we intended to monitor, the function may also monitor bits between
```
FD_SETSIZE
```
inclusive and
```
socket_fd
```
, that accidentally happen to have value 1.

Returns with
```
ret_value
```
equal to a number of
```
fd
```
that have a «Ready to read» condition occured. Before returning, the function builds a set of
```
fd
```
on which the condition was encountered. For this it sets the corresponding bits to 1 and clears all other bits to 0.

As we can see,
```
select
```
never modifies bits that had value zero when passed to the function in a second argument, because it does not monitor the respective
```
fd
```
. Bits 1 on which read condition was encountered retain their values. All other bits 1 are cleared to zero.

The bits 1 are out of
```
read_set
```
bounds. It follows, that on the step
```
select
```
changes, i.e. corrupts, at least one bit of local data or a stack frame. It may corrupt multiple bits.

Summary
When used with

fd

exceeding

FD_SETSIZE-1

select

and its helper macro

FD_SET

tend to corrupt local data or stack frames. Given the function normally runs in a loop, it has multiple opportunities to corrupt a stack.

Yuriy Koblents-Mishke