Date: Sat, 10 Apr 1999 20:38:58 +0800 From: Peter Wemm <peter@spinner.netplex.com.au> To: Terry Lambert <tlambert@primenet.com> Cc: barney@databus.com, smp@FreeBSD.ORG, dot@dotat.at Subject: Re: concurrent select()s on listen socket broken under SMP Message-ID: <19990410123901.44DD21F4D@spinner.netplex.com.au> In-Reply-To: Your message of "Sat, 10 Apr 1999 00:39:19 GMT." <199904100039.RAA05457@usr01.primenet.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Terry Lambert wrote:
> > This is *NOT* a SMP specific problem, it's a generic problem in the socket
> > API and implementation. You can trigger it on a UP kernel too, it just
> > happens to be real easy under SMP.
> >
> > See rev 1.52 and 1.54 of uipc_socket.c and related files for a description
> > of what's really going on. (the problem there is from a different angle,
> > it deals with remote users being able to trigger the race remotely
> > as a denial-of-service attack).
> >
> > The original poster didn't mention what version of FreeBSD was in use.
> > 3.1-RELEASE has this bug... It's fixed in 4.0 and 3.1-STABLE (after
> > 26-feb-99).
>
> He said he was running a curtrent version of 3.1-STABLE.
Either way, it doesn't matter. As I said, look at the description of the
changes for details of what is going on. The problem in the patch was a
*specific case* where it was possible to provoke this race with a single
process listener. Having multiple processes in a select/accept role
listening role is always vulnerable.. select() and accept() are different
syscalls, and there is no guarantee that you're going to get a continuous
execution run from the select being true and the socket still being ready
for select.
Eg: Process 1 Process 2
[sleeping in select] [sleeping in select]
[incoming connection - socket becomes readable, both become runnable]
Runs.. does accept()
[connection taken - another accept will hang]
Finally runs, does accept(), hangs..
At this point, Process 1 has taken the connection and process 2 is locked
in accept(). The only way out of this is to set the listening socket
non-blocking so that accept() will abort on a false start.
This race is inherent in the design of select() and accept(). It's nothing
to do with SMP etc.
> > Terry, rest assured, select() and poll() are quite SMP safe.
> >
> > The other serious problem is select collisions. I'd strongly advise using
> > a mutex so that only one process is ever in a select() for waiting for
> > connections on a socket. If two or more processes select() waiting for the
> > listening socket to become readable, when it does - a select collision
> > happens. ie: *EVERY SINGLE PROCESS* that was asleep in select gets woken
> > up, and runs, and scans it's select tables, and 99% go back to sleep.
>
> Yes. This is the classic "thundering herd" problem for which wakeup_one()
> (or wake_one()) was invented.
wakeup_one() cannot be used for select(). Look at the example above. What
if Process 1 got selected for the wakeup, and instead it serviced something
else of a higher priority? Suppose it hangs? The connection will be in
limbo with nothing to service it. Suppose it (process 1) core dumps? How
is process 2 going to get woken up instead?
This is not quite 'the' thundering herd BTW. If you have 3 processes
selecting on an event and it happens, all three (by design of select() api)
need to be woken. The bug is that not just those three get worken but every
select process on the system, including those that don't give a damn about
the given event.
> The real problem is that for some type of events, you want all
> of the processes waiting on the event to go, and on other types of
> events, you want only one process to go.
In select() and poll(), you *cannot* "pick one". All the processes listening
on the event *must* be woken - because the processes themselves scan the
vectors and decide what they will do and when. A process can't "send back"
the wakeup if it's going to do something else instead.
> I think for a socket on which a listen has been called, it's pretty
> pbvious that you can only service a single accept at a time, and
> so based on the character of the object selected, wakeup_one() is
> the correct call.
Even then, you can't do this safely. Sure, only one can accept the
connection, but if you pick one, how will you know if it actually will?
Remember, it's doing a select() so that it can look at *multiple* things at
once.
> I think that select collisions should be outlawed, unless the
> descriptor in question explicitly permits them, but I'd be OK
> with having to change the current behaviour by via fcntl on a
> per fd basis.
This won't work for the reasons above.. You'll get missed events all over
the place in a scenario where this is actually activated.. Remember, select
collisions are pretty rare for 99% of the software out there.
> > If you have a couple of hundred processes asleep in select(), this
> > hits like a bomb going off. You can get a spontanious load average
> > jump from 0.2 to 100+ in an instant, depending on when loadav() runs.
>
> And this is a design error, which should be corrected, whether you
> argue that it's a scheduler problem or a wakeup problem. Dynix and
> SVR4.2 both corrected this problem a while ago, using a wake_one()
> approach.
Yes, it is a problem and should be fixed, but wakeup_one() isn't even
remotely the answer..
> > Select collisions are a well understood problem, and there is no cheap,
> > easy, trivial fix that scales well. (Sure, making the selinfo struct have
> > 5 pid's rather than 1 would work for <= 6 processes waiting, but the
> > problem is still there for 6. you can't allocate memory for it due to
> > the nature of the implementation without modifying the driver interface
> > so that there is an "d_unselect()" handler or something - selinfo's get
> > released long after the process has given up and gone onto something
> > else. Changing the driver API _again_ isn't something we want to do
> > yet...)
>
> I think what you want is a LIFO queue for people selecting on an fd,
> and perhaps a per fd fcntl'able flag that can turn that into a FIFO
> policy instead for resources for which there are interactive waits
> (clearly, for a server, LIFO is the correct ordering; at Novell, my
> suggestion that a LIFO service order be used for the NCP streams mux
> resulted in a 35% increase in throughput as a result of reduced
> paging load, making the UNIX soloution faster than Native NetWare).
A list/queue/whatever would be one way, but this requires a driver API
redesign in a big way.
At the moment, the drivers manage the select event wakeups. A process
calls select/poll(), and this eventually translates into a selscan() call
which ends up calling the driver d_select() (now d_poll) entry point. If
the event is not presently active, selrecord() is used to log the event in
the *driver*'s private selinfo struct that it provides for that event.
At some later time, the event "happens", the driver does a selwakeup()
on the selinfo. The driver has *no idea* if the process is asleep and
waiting for the event or not or even if it's died or otherwise, because
there is no call from the select subsystem to tell the driver that it's
no longer interested. As a result, the drivers cannot maintain a LIFO or
anything like that since they never get a chance to clean out the list
of things that are no longer interested in the event.
However, if we're prepared to get a little sloppy and do lazy reclaims of
buffers or something like that, then selrecord() could prune the table if
needed, and selwakeup could do it too. We could probably fudge it a
little, so that instead of selinfo holding a short pid, it could hold a
union and an array of 4 or 8 pid's which transmutes into a list header or
something if all 4 or 8 slots get used up.
> One possibile soloution, which would do dick for the SMP implications,
> would be to add a "time_in_select", and then have wakeup_one() only
> wake the one who called last, using a linear iteration. This is
> basically what it does now (why the hell does it wakeup more than
> one *just* because the first one is swapped out?!?).
If only it were that simple..
> Terry Lambert
> terry@lambert.org
Cheers,
-Peter
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-smp" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19990410123901.44DD21F4D>