freedman@granite.cr.bull.com (Jerome Freedman) (01/10/90)
Gee, it seems like I have been asking questions here a lot recently. Acquiring minds want to know and we don't have a lot of Unix expertise here in house. question: what does "selwakeup" do in the BSD driver code and what is the significance of the "coll" parameter? Jerry Freedman,Jr freedman@granite.cr.bull.com
chris@mimsy.umd.edu (Chris Torek) (01/10/90)
In article <1990Jan9.204911.14984@granite.cr.bull.com> freedman@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@cs.umd.edu Path: uunet!mimsy!chris