selwakeup and its parameters

[Chris Torek]

In article <1990Jan9.204911.14984 at granite.cr.bull.com>
freedman at granite.cr.bull.com (Jerome Freedman) writes:
>  question: what does "selwakeup" do in the BSD driver code
>and what is the significance of the "coll" parameter?

The `coll' parameter stands for `collision'.  To understand it,
you need to know how select is implemented.

The `top half' of select is fairly simple.  select() scans the
given file descriptors, calling (*fp->f_ops->fo_select) (the select
function for the underlying object, either a socket or an inode;
an inode further calls (*cdevsw[].d_select) for a character device)
on each, and if any say `ready', it returns.  If none were ready,
however, it has to do more work.  Some of this is done in advance.

The process is as follows:

a. Look at the timeval argument.  If there is one:
    i.  If it is 0 (or less than 0), return immediately (poll).
    ii. Otherwise, calculate the time by which select() should
	return (by adding this timer to the current time).

b. (top of a loop)
   Make a copy of the global variable `nselcoll' (number of select
   collisions).  Mark the process as `selecting', and scan the given
   file descriptors.  If there is an error, or some descriptors are
   ready, or there was a timeval and it has expired, turn off the
   `selecting' flag and go return.

c. If the process is no longer marked `selecting', or if some collisions
   have occurred, go back to step b.  (We will see why this happens
   in a moment.)

d. Turn off the `selecting' bit.  If there is a timeval argument:
    i.  Catch signals.  If one occurs, disable the unselect from
        step d-ii and go return.
    ii. Schedule a call to unselect to happen at the time the process
	should stop selecting.

e. Sleep on `&selwait'.

f. If there was a timeval, stop catching signals and disable the call
   to unselect (whether it has happened or not; if not, this is a no-op).
   Go back to step b.

Now, while scanning the given file descriptors, each selection function
not only tests to see if the condition (readable, writable, exception)
is met.  In particular, if the condition is *not* met, each function
does the following:

	if (condition is met)
		return 1;
	if (this_device_info->last_proc_to_select &&
	    this_device_info->last_proc_to_select->p_wchan == &selwait)
		this_device_info->flags |= SELECT_COLLISION;
	else
		this_device_info->last_proc_to_select = u.u_procp;

That is, if some other process was selecting before, and that process
is also waiting for select now (not necessarily on this particular device
or socket), remember that there was a `select collision'.  Otherwise,
just record the current process as the last one to try selecting.

Later, when the condition on which a device might have been selecting
is met---whatever that condition might be---the same device does this:

	if (this_device_info->last_proc_to_select) {
		selwakeup(this_device_info->last_proc_to_select,
		    this_device_info->flags & SELECT_COLLISION);
		this_device_info->flags &= ~SELECT_COLLISION;
		this_device_info->last_proc_to_select = NULL;
	}

In other words, if there was someone (or several someones) selecting,
do a selwakeup() on the first, and tell it whether there was a collision.
Then (always) clear the collision flag and forget about that process.

Selwakeup, in turn, looks something like this:

	selwakeup(struct proc *p, int coll) {
		if (coll) {
			nselcoll++;
			wakeup(&selwait);
		}
		if (p) {
			if (p->p_wchan == &selwait)
				make p (but only p) stop sleeping,
					but without using wakeup();
			else if (p is marked selecting)
				turn off p's selecting flag;
		}
	}

Now, if only one process ever selects on any given device or socket
at a time, and if it waits forever, the operation is fairly simple.
The device's select function records the process, and selwakeup()
never does a wakeup(), but rather simply makes the given process stop
sleeping.

Similarly, if only one process selects, and it uses the timer, selwakeup()
sees that both p->p_wchan != &selwait and p is not marked selecting.

If several processes select, we have more possibilities.

Suppose one process calls select, then a second one does.  Here the
device select function checks the first process's p_wchan.  There are
two possibilities:

      - That process is not selecting (p_wchan != &selwait).  The
        device simply replaces its remembered process with the new one.

      + That process is selecting (on anything): p_wchan==&selwait,
	and the device records a collision.  If the condition never
	becomes true, nothing interesting happens, so we can ignore
	that.  Instead, when it does become true, the device calls
	selwakeup(first_proc, 1); selwakeup() increments nselcoll and
	does a wakeup(&selwait).  This causes every process in the
	system that is selecting to wake up.  They all, in turn,
	go back to their step `b', and make copies of nselcoll and
	scan their files.  This time the second process---the one
	that caused the collision---gets a ready indication, and so
	it returns.  The first one also gets a ready if it is selecting
	on this file, or a not-ready if it is selecting on some other
	file.

Okay, so what are `nselcoll' and the process `selecting' flag for?

Well, scanning the set of file descriptors could take a while.  In
particular, suppose a process wants to select on several devices.
The first one is not ready, so that device records the process and
the process looks at the next.  In the meantime the first device
becomes ready.  In this case, the first device calls selwakeup(),
which sees that p->p_wchan != &selwait (since the process is still
looking around), so selwakeup() clears the selecting flag for that
process.  When that process gets around to step `c', it will start
over, this time finding that the first device is ready.

Now suppose that one process has started a select(), and is waiting
for some particular device, when another starts a select() on the same
device.  The device records the first process and sets its collision
flag and returns, and the second process moves on to another file
descriptor.  Suddenly the device becomes ready.  It calls selwakeup(),
passing the address of the first process, but also saying `there was
a collision'.  Selwakeup() wakes up everyone (as in `+' above), but
also increments `nselcoll'.  This way, the second device---which did
not have its selecting flag cleared---can tell in step `c' that it
should try again.

As the BSD book says, collisions are inefficient, but occur quite rarely
statistically, so it has not been worthwhile to do something fancier.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at cs.umd.edu	Path:	uunet!mimsy!chris