Re: [libmicrohttpd] Sockets on Windows

[Christian Grothoff]

On Friday 08 January 2010 06:21:21 pm Michael Lenaghan wrote:
> >> So you'd only see that condition--ie, too many sockets for select--if
> >> someone increases max connections beyond FD_SETSIZE. Of course, at
> >> that point you have a problem waiting in the wings.
> >
> > Not the only case.  You could also have an application using MHD that
> > runs with the default but opens other files at the side (likely, in
> > fact).  Then you might get socket numbers (!) >= FD_SETSIZE but the total
> > number of connections (!) is still <= MHD_MAX_CONNECTIONS_DEFAULT.  So we
> > need that check to avoid accessing memory out of bounds even if the
> > maximum number of connections is less than FD_SETSIZE.
> 
> On Windows select() only works for sockets. So you could exceed
> FD_SETSIZE only if a) you're opening sockets outside of libmicro and
> b) you're asking libmicro to select() on both its own sockets and your
> sockets. I see no way to do (b) in libmicro 0.4.4--so libmicro itself
> will never select() on more than "connections + 1" sockets. (There's
> no relationship between a socket fd value and FD_SETSIZE; a socket fd
> can be any pointer-sized unsigned int value other than INVALID_HANDLE.
> Indeed, the only things that cares about FD_SETSIZE are the fd_set
> struct and the FD_* macros; select() will accept a struct of any size
> as long as the struct's count is set correctly.)

Ah, yes, my point was that for UNIX we need the checks as they are.  We can 
certainly #ifdef this one out for W32.
 
> >> On Windows FD_SETSIZE defaults to 64. Some people might think that's a
> >> bit small. There's a tradeoff in making it too big, though: if you
> >> selected on, say, 64 sockets you have to scan through 64 slots to find
> >> each socket after the call to select(). So it's an O(n^2) operation
> >> right in your innermost loop.
> >
> > Also not entirely true; it's O(n), and the number of slots the app scans
> > through is exactly the number of open connections, not FD_SETSIZE.
> >  Similarly, the OS only scans from 0 to max where max it the largest
> > socket number (which will be most likely very close to the number of open
> > connections).
> 
> On Windows an fd_set is an array of *of* socket values--not an array
> indexed *by* socket values. So finding a given socket is O(n). If you
> have n sockets you have to do that n times--resulting in O(n^2) worst
> case. (Btw, if you take a look at the Windows docs you'll see that the
> first parameter to select() is ignored.)
 
Ah, W32 vs. POSIX again.  Still, if the W32 API guarantees that the sockets 
are left in the same order as they were put in, then this can still be done in 
O(n); however, I didn't check this.  And clearly with just 64 entries it 
doesn't really matter anyway...

Best,

Christian