is select() being misused by the majority of programmers? - Linux

This is a discussion on is select() being misused by the majority of programmers? - Linux ; I've come across something that doesn't make much sense to me. The standard Linux manpage for select() defines the first parameter as the "maximum file descriptor in the set, plus one"...This never made any sense to me because it would ...

+ Reply to Thread
Results 1 to 14 of 14

Thread: is select() being misused by the majority of programmers?

  1. is select() being misused by the majority of programmers?


    I've come across something that doesn't make much sense to me. The
    standard Linux manpage for select() defines the first parameter as the
    "maximum file descriptor in the set, plus one"...This never made any sense
    to me because it would cause one to assume that all file descriptors in a
    contiguous range will be polled, and thus negates the need for even
    filling a descriptor set prior to calling select.

    I've since found other documentation stating that in select(n,&inset...) n
    is really the number of entries in the set inset. This makes much more
    sense from a programmatic point of view. We're not going to be concerned
    with a contiguous range of descriptors, but only the ones that were
    explicitly set before calling select. Passing the length of the set makes
    infinitely more sense.

    All the programmers and examples I've seen use the first (and more likely
    incorrect) semantics for the select() parameter.

    What follows is from manpages found on my system that seems to back up my
    position.
    ----------------------------------------
    PSELECT(P) PSELECT(P)

    NAME
    pselect, select - synchronous I/O multiplexing

    SYNOPSIS
    #include

    int pselect(int nfds, fd_set *restrict readfds,
    fd_set *restrict writefds, fd_set *restrict errorfds,
    const struct timespec *restrict timeout,
    const sigset_t *restrict sigmask);
    int select(int nfds, fd_set *restrict readfds,
    fd_set *restrict writefds, fd_set *restrict errorfds,
    struct timeval *restrict timeout);
    void FD_CLR(int fd, fd_set *fdset);
    int FD_ISSET(int fd, fd_set *fdset);
    void FD_SET(int fd, fd_set *fdset);
    void FD_ZERO(fd_set *fdset);

    DESCRIPTION
    The pselect() function shall examine the file descriptor sets whose addresses are passed in
    the readfds, writefds, and errorfds parameters to see whether some of their descriptors are
    ready for reading, are ready for writing, or have an exceptional condition pending, respec-
    tively.

    The select() function shall be equivalent to the pselect() function, except as follows:

    * For the select() function, the timeout period is given in seconds and microseconds in an
    argument of type struct timeval, whereas for the pselect() function the timeout period is
    given in seconds and nanoseconds in an argument of type struct timespec.

    * The select() function has no sigmask argument; it shall behave as pselect() does when
    sigmask is a null pointer.

    * Upon successful completion, the select() function may modify the object pointed to by the
    timeout argument.

    The pselect() and select() functions shall support regular files, terminal and pseudo-termi-
    nal devices, STREAMS-based files, FIFOs, pipes, and sockets. The behavior of pselect() and
    select() on file descriptors that refer to other types of file is unspecified.

    The nfds argument specifies the range of descriptors to be tested. The first nfds descrip-
    tors shall be checked in each set; that is, the descriptors from zero through nfds-1 in the
    descriptor sets shall be examined.

    If the readfds argument is not a null pointer, it points to an object of type fd_set that on
    input specifies the file descriptors to be checked for being ready to read, and on output
    indicates which file descriptors are ready to read.

    ------------------------------------------------------------


    So, which is correct, and why?



  2. Re: is select() being misused by the majority of programmers?

    noone@all.com wrote:
    > I've come across something that doesn't make much sense to me. The
    > standard Linux manpage for select() defines the first parameter as the
    > "maximum file descriptor in the set, plus one"...This never made any sense
    > to me because it would cause one to assume that all file descriptors ina
    > contiguous range will be polled, and thus negates the need for even
    > filling a descriptor set prior to calling select.
    >
    > I've since found other documentation stating that in select(n,&inset...) n
    > is really the number of entries in the set inset. This makes much more
    > sense from a programmatic point of view. We're not going to be concerned
    > with a contiguous range of descriptors, but only the ones that were
    > explicitly set before calling select. Passing the length of the set makes
    > infinitely more sense.


    > The nfds argument specifies the range of descriptors to be tested. The first nfds descrip-
    > tors shall be checked in each set; that is, the descriptors from zero through nfds-1 in the
    > descriptor sets shall be examined.
    >
    > If the readfds argument is not a null pointer, it points to an object of type fd_set that on
    > input specifies the file descriptors to be checked for being ready to read, and on output
    > indicates which file descriptors are ready to read.


    > So, which is correct, and why?


    Where do you see a difference?

    If the set of file descriptors were [0, 10, 20], then your wording above
    would mean that the first parameter be set to the "maximum file
    descriptor in the set, plus one", i.e. 20+1 == 21.

    The manpage says: "The first nfds descriptors shall be checked in each
    set", so the first 21 file descriptors will be checked and only 0, 10
    and 20 will be found set.


    I guess the confusion arises from the fact that on one hand there are 3
    file descriptors in the set [0, 10, 20], but 21 file descriptors in the
    array which is used to implement the set when passing it.

    Josef
    --
    Josef Möllers (Pinguinpfleger bei FSC)
    If failure had no penalty success would not be a prize
    -- T. Pratchett


  3. Re: is select() being misused by the majority of programmers?

    noone@all.com wrote:
    > I've come across something that doesn't make much sense to me. The
    > standard Linux manpage for select() defines the first parameter as the
    > "maximum file descriptor in the set, plus one"...


    That's correct.

    > This never made any sense
    > to me because it would cause one to assume that all file descriptors in a
    > contiguous range will be polled, and thus negates the need for even
    > filling a descriptor set prior to calling select.


    No, all file descriptors in a contiguous range that are also specified
    in the descriptor set will be polled.

    > DESCRIPTION


    ....snip...
    >
    > The nfds argument specifies the range of descriptors to be tested. The first nfds descrip-
    > tors shall be checked in each set; that is, the descriptors from zero through nfds-1 in the
    > descriptor sets shall be examined.


    > So, which is correct, and why?


    It examines the descriptors from 0 to "nfds-1" that are in the sets.
    Basically it will construct a bitmask of the actual descriptors that
    exist in the specified range, AND it with the specified fd_set, and then
    scan those sockets to see if anything happened.

    Chris

  4. Re: is select() being misused by the majority of programmers?

    On Mon, 06 Nov 2006 17:00:06 +0100, Josef Moellers wrote:

    >
    > Where do you see a difference?
    >
    > If the set of file descriptors were [0, 10, 20], then your wording above
    > would mean that the first parameter be set to the "maximum file
    > descriptor in the set, plus one", i.e. 20+1 == 21.
    >
    > The manpage says: "The first nfds descriptors shall be checked in each
    > set", so the first 21 file descriptors will be checked and only 0, 10
    > and 20 will be found set.
    >
    >
    > I guess the confusion arises from the fact that on one hand there are 3
    > file descriptors in the set [0, 10, 20], but 21 file descriptors in the
    > array which is used to implement the set when passing it.


    YES! That is the confusion that needs to be better addressed in the
    documentation. My mind wants to put 3 in the first parameter since I'm
    interested in three descriptors, and we know what those descriptor numbers
    are based on their being in the inset.

    The other problem with the previous way of doing it is that you need to
    keep track of the maximum file descriptor used. Is there an easy way to
    query the set to retrieve that information? I've seen FD_SET, FD_ISSET,
    and FD_ZERO, but I haven't seen an x=FD_MAX.



  5. Re: is select() being misused by the majority of programmers?

    noone@all.com wrote:
    > I've come across something that doesn't make much sense to me. The
    > standard Linux manpage for select() defines the first parameter as the
    > "maximum file descriptor in the set, plus one"...This never made any sense
    > to me because it would cause one to assume that all file descriptors in a
    > contiguous range will be polled, and thus negates the need for even
    > filling a descriptor set prior to calling select.


    What you are missing is that there can be thousands of file
    descriptors. They are allocated in the bottom range: whenever a socket
    or file is opened, the lowest available descriptor is given to it. This
    means that the high numbers are never used in most processes. It would
    be a waste of cycles in the kernel to loop over empty portions of the
    fd_set bitmasks. This is why there is an argument which allows the
    process to specify the highest number (plus one).

    That doesn't mean that all of the descriptors below that value are in
    the set. It just establishes a boundary on the range of fd_set that is
    in use.

    For instance suppose you have a process which only wants to monitor
    sockets for input. It does not care about STDIN_FILENO, STDOUT_FILENO
    and STDERR_FILENO. It has five sockets and no other open files. So
    these sockets are probably 3, 4, 5, 6, and 7. These are the
    descriptors that are added to the set. The descriptors 0, 1 and 2 are
    left out. The value that is specified for the nfds parameter is 8. It
    means: ``monitor the entries from 0 to 7; do not bother looking at any
    of the hundreds of entries in fd_set which are higher than 7''. Of
    course, this does not imply that 0, 1 and 2 are monitored; they have
    not been added to the set. Their entries are still checked, but ignored
    when they are found to be zero in all three sets.

    > I've since found other documentation stating that in select(n,&inset...) n
    > is really the number of entries in the set inset.


    Which proves that if you insist on misunderstanding something bad
    enough, and misinterpret enough documentation, you can often manage to
    confirm your misunderstanding.

    The above isn't incorrect, if you do not insist on interpreting
    ``entries'' of a set as being elements, but rather places that hold
    elements, and which can be empty.

    > explicitly set before calling select. Passing the length of the set makes
    > infinitely more sense.


    The only thing that makes sense to pass to select is what the operating
    system requires. You can jump up and down yearning for that value to
    have different semantics, but it's not going to happen.

    > All the programmers and examples I've seen use the first (and more likely
    > incorrect) semantics for the select() parameter.


    Sure, everybody is wrong, yet networking software runs somehow.

    > The nfds argument specifies the range of descriptors to be tested. The first nfds descrip-
    > tors shall be checked in each set; that is, the descriptors from zero through nfds-1 in the
    > descriptor sets shall be examined.


    What part of this isn't clear?


  6. Re: is select() being misused by the majority of programmers?

    noone@all.com wrote:
    > YES! That is the confusion that needs to be better addressed in the
    > documentation.


    In 17 years of working with sockets and select, I've never come across
    anyone who didn't understand this.

    > My mind wants to put 3 in the first parameter since I'm
    > interested in three descriptors.


    The API is geared toward making select easier to write (not just the
    kernel code but the system call wrapper also).

    The nfds parameter not only determines which bits of the mask have to
    be examined, but also which part of the mask needs to be copied into
    the kernel at all.

    The value 3 would require select to iterate over the mask and count all
    the 1's just to discover how much of the mask is relevant.

    Also, keep in mind that there are three masks, with independent
    contents. So you would need three different values representing the
    individual set cardinalities.

    The entire select API is braindamaged, I will give you that. If you
    want an API that will take the number 3 in that situation, use poll.
    Poll is better, and it's closer to what the kernel guts are built on.
    The select system call basically has to be converted to poll.

    > The other problem with the previous way of doing it is that you need to
    > keep track of the maximum file descriptor used. Is there an easy way to
    > query the set to retrieve that information?


    How it's done is that the application code which sets up the fd_set
    does it all in one scope, where it can use a local variable to compute
    the maximum. The application has some data structure, or perhaps a set
    of disjoint data structures, from which it pulls out information about
    the sockets that have to be monitored. The fd_set is constructed all at
    once, and the max value is computed at the same time.

    If you can't do it that way, you can create an augmented data structure
    which holds the fd_set's as well as the maximum:

    struct select_sets {
    fd_set readfs, writefds, exfds;
    int highest_fd;
    };

    When it comes time to call select, you initialize one of these and pass
    it around to various routines in the program which add descriptors to
    the set and update the maximum value.

    > I've seen FD_SET, FD_ISSET, and FD_ZERO, but I haven't seen an x=FD_MAX.


    That would require iterating over the bitmask. One way to do it would
    be to start from the high end of the bitmask and look for the first
    non-zero word in the reverse direction. Then within that word, find the
    highest non-zero bit.

    Sucn an operation would spoil some of the the optimization of the nfds
    parameter, whose reason is to prevent such iteration over unused
    portions of the bitmask.


  7. Re: is select() being misused by the majority of programmers?

    "Kaz Kylheku" writes:

    [...]

    > The entire select API is braindamaged, I will give you that. If you
    > want an API that will take the number 3 in that situation, use poll.
    > Poll is better, and it's closer to what the kernel guts are built
    > on.


    NB: The following is partly based on hearsay and partly speculation.

    'select' originated in 4.2BSD. A 4.2BSD process had a fixed size
    descriptor table which had a guaranteed minimum size of 20 (and I have
    read something about a maximum of 32 somewhere). This means the fdset
    arguments could be passed in three 32-bit machine words (VAX) and
    those word-sized fdsets could be manipulated very efficiently. The
    select-interface is therefore likely just an 'efficiency hack' from
    the past (1983) that managed to survive until today (where it is
    actually very inefficient, especially for small descriptor sets).

  8. Re: is select() being misused by the majority of programmers?

    noone@all.com wrote:
    > On Mon, 06 Nov 2006 17:00:06 +0100, Josef Moellers wrote:
    >
    >
    >>Where do you see a difference?
    >>
    >>If the set of file descriptors were [0, 10, 20], then your wording above
    >>would mean that the first parameter be set to the "maximum file
    >>descriptor in the set, plus one", i.e. 20+1 == 21.
    >>
    >>The manpage says: "The first nfds descriptors shall be checked in each
    >>set", so the first 21 file descriptors will be checked and only 0, 10
    >>and 20 will be found set.
    >>
    >>
    >>I guess the confusion arises from the fact that on one hand there are 3
    >>file descriptors in the set [0, 10, 20], but 21 file descriptors in the
    >>array which is used to implement the set when passing it.

    >
    >
    > YES! That is the confusion that needs to be better addressed in the
    > documentation. My mind wants to put 3 in the first parameter since I'm
    > interested in three descriptors, and we know what those descriptor numbers
    > are based on their being in the inset.


    poll(2) has this notion.

    > The other problem with the previous way of doing it is that you need to
    > keep track of the maximum file descriptor used. Is there an easy way to
    > query the set to retrieve that information? I've seen FD_SET, FD_ISSET,
    > and FD_ZERO, but I haven't seen an x=FD_MAX.


    While you could set n (the first parameter) to the maximum number
    allowed (FD_SETSIZE), this would cause the kernel to check each and
    every of these bits, even if only a single one is set.

    OTOH, it could be a function (FD_MAX(fdsetp)) which would scan the
    entire set to determine the largest one set, this, too, would scan the
    entire set (of even all three sets!).

    The usual way is to keep track of this number yourself and, I guess,
    this has proved to be optimal: n comparisons, n assignments (n = number
    of used fds). From a complexity point of view:

    if (newfd > max_fd_up_to_now)
    max_fd_up_to_now = newfd;

    vs.

    for (fd = 0; fd < FD_SETSIZE; fd++)
    if (FD_ISSET(fd, &fdset))
    max_fd_up_to_now = fd;

    This is FD_SETSIZE * 2 comparisons (fd < FD_SETSIZE and FD_ISSET(fd,
    &fdset)) + n assignments + whatever else the loop takes (assignments,
    additions).

    Besides, you'd have to do this for each of the three sets!

    Nothing keeps you from rolling your own, though.

    --
    Josef Möllers (Pinguinpfleger bei FSC)
    If failure had no penalty success would not be a prize
    -- T. Pratchett


  9. Re: is select() being misused by the majority of programmers?

    On 2006-11-06, noone@all.com wrote:

    > I've come across something that doesn't make much sense to me.


    Life's like that.

    > The standard Linux manpage for select() defines the first
    > parameter as the "maximum file descriptor in the set, plus
    > one"...This never made any sense to me because it would cause
    > one to assume that all file descriptors in a contiguous range
    > will be polled, and thus negates the need for even filling a
    > descriptor set prior to calling select.
    >
    > I've since found other documentation stating that in
    > select(n,&inset...) n is really the number of entries in the
    > set inset. This makes much more sense from a programmatic
    > point of view. We're not going to be concerned with a
    > contiguous range of descriptors, but only the ones that were
    > explicitly set before calling select. Passing the length of
    > the set makes infinitely more sense.


    Except I don't think you're proposing passing the length of the
    set. You're propsing passing the number of set members that
    have true values. The length of the set is fixed by the OS (I
    don't even know what it is for Linux, but 256 bits comes to
    mind). It's a set of bits. Each member of the set has a value
    of either true or false. You're telling the system call how
    many of those bits it needs to examine in order to cover the
    file descriptors you care about.

    I agree that passing the count of true set members is much more
    intuitive, and I don't see how it would be any more difficult
    or inefficient to implement.

    But, that ship sailed many years ago (like about 20?). The
    semantics of select() have been standardized since BSD days,
    and they're not going to change no matter how much you dislike
    them.

    > All the programmers and examples I've seen use the first (and
    > more likely incorrect) semantics for the select() parameter.


    The examples you have seen are correct.

    --
    Grant Edwards grante Yow! BEEP-BEEP!! I'm a
    at '49 STUDEBAKER!!
    visi.com

  10. Re: is select() being misused by the majority of programmers?


    Grant Edwards wrote:

    > I agree that passing the count of true set members is much more
    > intuitive, and I don't see how it would be any more difficult
    > or inefficient to implement.


    That would largely defeat the purpose of the size. The purpose of
    passing the size to 'select' is just as much to stop the library from
    having to pass the entire fd set to the kernel as to stop the kernel
    from having to scan the whole set. Do you think the library should have
    to scan all three fd sets until it found the number in the count just
    to tell how many bytes to pass to the kernel?

    Current scheme (roughly):

    bytes_to_pass=(maxfd+7)/8;

    Your scheme (roughly):

    for(i=0; i++; (num_fds>0) && (i {
    if (FD_ISSET(i, first_set) || FD_ISSET(i, second_set) || FD_ISSET(i,
    third_set) )
    num_fds--;
    }
    bytes_to_pass=(i+7)/8;

    In the worst case of sparse sets, your proposed scheme is dramatically
    worse, having to scan most of all three sets. It can be optimized (to
    use byte checks rather than bit checks), but you can't get avoid three
    bits of ugliness:

    1) You may have to scan a significant fraction of all three sets just
    to figure out how many bytes to pass.

    2) If the count passed by the user is one too high or more, you will
    wind up scanning all of all the sets.

    3) You have to count the number of bits set in the logical AND of all
    three fd sets to figure out when you can stop looking at bits. This is
    likely free for the kernel, which has to more or less do so anyway, but
    expensive for the library, which otherwise wouldn't have to.

    DS


  11. Re: is select() being misused by the majority of programmers?

    On 2006-11-08, David Schwartz wrote:

    >> I agree that passing the count of true set members is much more
    >> intuitive, and I don't see how it would be any more difficult
    >> or inefficient to implement.

    >
    > That would largely defeat the purpose of the size. The purpose of
    > passing the size to 'select' is just as much to stop the library from
    > having to pass the entire fd set to the kernel


    My bad. I never realized it did that.

    > as to stop the kernel from having to scan the whole set. Do
    > you think the library should have to scan all three fd sets
    > until it found the number in the count just to tell how many
    > bytes to pass to the kernel?


    No. I was under the distinct impression that FDSETs were all
    passed as a fixed size array. I know I've seen the fixed-size
    implementation somewhere, but it must not have been Linux.

    > Current scheme (roughly):
    >
    > bytes_to_pass=(maxfd+7)/8;


    > [...]



    --
    Grant Edwards grante Yow! Hand me a pair of
    at leather pants and a CASIO
    visi.com keyboard -- I'm living
    for today!

  12. Re: is select() being misused by the majority of programmers?


    Grant Edwards wrote:

    > No. I was under the distinct impression that FDSETs were all
    > passed as a fixed size array. I know I've seen the fixed-size
    > implementation somewhere, but it must not have been Linux.


    Last I checked, Linux was an odd hybrid. The headers presented to
    user-space all implemented fixed-sized arrays and you had to manually
    edit header files to get anything different. You had to change code
    like:

    #define FD_SETSIZE 1024

    To code like:

    #ifndef FD_SETSIZE
    #define FD_SETSIZE 1024
    #endif

    And code like:

    #define __FD_SETSIZE 1024

    To code like:

    #ifndef FD_SETSIZE
    #define __FD_SETSIZE 1024
    #else
    #define __FD_SETSIZE FD_SETSIZE
    #endif

    That would allows code to define its own value of the FD_SETSIZE macro,
    provided that was done before including any headers.

    But its libc implementation ignored FD_SETSIZE and did not contain
    'sizeof(struct fd_set)' or anything like that. It used the first
    parameter to determine how many bytes to pass. So modifying the header
    files works fine.

    DS


  13. Re: is select() being misused by the majority of programmers?

    David Schwartz wrote:
    > Grant Edwards wrote:
    >
    > > I agree that passing the count of true set members is much more
    > > intuitive, and I don't see how it would be any more difficult
    > > or inefficient to implement.

    >
    > That would largely defeat the purpose of the size. The purpose of
    > passing the size to 'select' is just as much to stop the library from
    > having to pass the entire fd set to the kernel as to stop the kernel
    > from having to scan the whole set.


    The size does indeed optimize the copying of the fd_set.

    But library does not pass the entire fd_set to the kernel. It passes a
    pointer only. It's the kernel's job to make a copy of the fd_set.

    The nfds parameter indicates how much of the memory behind each bitmask
    pointer is valid.

    This is analogous to the buffer and size in the write system call. The
    approach obviously leaves a bit of flexibility in how the user space
    will represent the API to the user.

    Instead of a fixed-size fd_set type, there could be something more
    flexible.

    > Do you think the library should have
    > to scan all three fd sets until it found the number in the count just
    > to tell how many bytes to pass to the kernel?


    With the kernel doing the copying, this translates to a bigger problem.
    The kernel needs to know that it has a valid piece of user space
    memory.

    If a count of the set size was passed for each fd_set, you have a
    chicken and egg problem. The kernel does not know how much of the
    bitmask is accessible. Some silly algorithm has to be implemented to
    verify the bitvector a piece at a time while doing the scan.

    With the nfds parameter, it's easy. It can simply be converted to a
    number of bytes, and then each bitmask can be verified that it's valid
    memory up to that number of words using a simple call to verify_area()
    before being copied in.


  14. Re: is select() being misused by the majority of programmers?


    Kaz Kylheku wrote:

    > With the kernel doing the copying, this translates to a bigger problem.
    > The kernel needs to know that it has a valid piece of user space
    > memory.


    > If a count of the set size was passed for each fd_set, you have a
    > chicken and egg problem. The kernel does not know how much of the
    > bitmask is accessible. Some silly algorithm has to be implemented to
    > verify the bitvector a piece at a time while doing the scan.


    You are right. I had the right problem (too hard to determine how big
    the fd_set's are) but for the wrong reason (to validate them, not to
    copy them).

    DS


+ Reply to Thread