scheduler/newselect.txt

   1 Design Notes for New Poll/Select API in CUPSD - 2006-06-06
   2 ----------------------------------------------------------
   3
   4 SUPPORTED APIS
   5
   6     OS              select  poll    epoll   kqueue  /dev/poll
   7     --------------  ------  ------  ------  ------  ---------
   8     AIX             YES     YES     NO      NO      NO
   9     FreeBSD         YES     YES     NO      YES     NO
  10     HP-UX           YES     YES     NO      NO      NO
  11     IRIX            YES     YES     NO      NO      NO
  12     Linux           YES     YES     YES     NO      NO
  13     MacOS X         YES     YES     NO      YES     NO
  14     NetBSD          YES     YES     NO      YES     NO
  15     OpenBSD         YES     YES     NO      YES     NO
  16     Solaris         YES     YES     NO      NO      YES
  17     Tru64           YES     YES     NO      NO      NO
  18     Windows         YES     NO      NO      NO      NO
  19
  20
  21 HIGH-LEVEL API
  22
  23     typedef void (*cupsd_selfunc_t)(void *data);
  24
  25     void cupsdStartSelect(void);
  26     void cupsdStopSelect(void);
  27     void cupsdAddSelect(int fd, cupsd_selfunc_t read_cb,
  28                         cupsd_selfunc_t write_cb, void *data);
  29     void cupsdRemoveSelect(int fd);
  30     int cupsdDoSelect(int timeout);
  31
  32
  33 IMPLEMENTATION STRATEGY
  34
  35     0. Common Stuff
  36         a. CUPS array of file descriptor to callback functions
  37            and data.
  38         b. cupsdStartSelect() creates the array
  39         c. cupsdStopSelect() destroys the array and all elements.
  40         d. cupsdAddSelect() adds to the array and allocates a
  41            new callback element.
  42         e. cupsdRemoveSelect() removes from the array and frees
  43            the callback element.
  44
  45     1. select()
  46         a. Input/Output fd_set variables, copied to working
  47            copies and then used with select().
  48         b. Loop through CUPS array, using FD_ISSET and calling
  49            the read/ write callbacks as needed.
  50         c. cupsdRemoveSelect() clears fd_set bit from main and
  51            working sets.
  52         d. cupsdStopSelect() frees all of the memory used by the
  53            CUPS array and fd_set's.
  54
  55     2. poll()
  56         a. Regular array of pollfd, sorted the same as the CUPS
  57            array.
  58         b. Loop through pollfd array, call the corresponding
  59            read/write callbacks as needed.
  60         c. cupsdAddSelect() adds first to CUPS array, then uses
  61            current index to determine insertion point for pollfd
  62            array.
  63         d. cupsdRemoveSelect() needs to update cupsdDoSelect()
  64            loop counter if <= current index.
  65         e. cupsdStopSelect() frees all of the memory used by the
  66            CUPS array and pollfd array.
  67
  68     3. epoll()
  69         a. cupsdStartSelect() creates epoll file descriptor using
  70            epoll_create() with the maximum fd count, and
  71            allocates an events buffer for the maximum fd count.
  72         b. cupsdAdd/RemoveSelect() uses epoll_ctl() to add
  73            (EPOLL_CTL_ADD) or remove (EPOLL_CTL_DEL) a single
  74            event using the level-triggered semantics. The event
  75            user data field is a pointer to the new callback array
  76            element.
  77         c. cupsdDoSelect() uses epoll_wait() with the global event
  78            buffer allocated in cupsdStartSelect() and then loops
  79            through the events, using the user data field to find
  80            the callback record.
  81         d. cupsdStopSelect() closes the epoll file descriptor and
  82            frees all of the memory used by the event buffer.
  83
  84     4. kqueue()
  85         b. cupsdStartSelect() creates kqueue file descriptor
  86            using kqyeue() function and allocates a global event
  87            buffer.
  88         c. cupsdAdd/RemoveSelect() uses EV_SET and kevent() to
  89            register the changes. The event user data field is a
  90            pointer to the new callback array element.
  91         d. cupsdDoSelect() uses kevent() to poll for events and
  92            loops through the events, using the user data field to
  93            find the callback record.
  94         e. cupsdStopSelect() closes the kqyeye() file descriptor
  95            and frees all of the memory used by the event buffer.
  96
  97     5. /dev/poll
  98         a. cupsdStartSelect() opens /dev/poll and allocates an
  99            array of pollfd structs; on failure to open /dev/poll,
 100            revert to poll() system call.
 101         b. cupsdAddSelect() writes a single pollfd struct to
 102            /dev/poll with the new file descriptor and the
 103            POLLIN/POLLOUT flags.
 104         c. cupsdRemoveSelect() writes a single pollfd struct to
 105            /dev/poll with the file descriptor and the POLLREMOVE
 106            flag.
 107         d. cupsdDoSelect() uses the DP_POLL ioctl to retrieve
 108            events from /dev/poll and then loops through the
 109            returned pollfd array, looking up the file descriptors
 110            as needed.
 111         e. cupsdStopSelect() closes /dev/poll and frees the
 112            pollfd array.
 113         f. Need to benchmark to see if it is more efficient than
 114            using poll() - this is the only mechanism that is O(n
 115            log n), all of the others are O(n)...