/* Quagga pselect support -- header * Copyright (C) 2009 Chris Hall (GMCH), Highwayman * * This file is part of GNU Zebra. * * GNU Zebra is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published * by the Free Software Foundation; either version 2, or (at your * option) any later version. * * GNU Zebra is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ #include "misc.h" #include #include #include "zassert.h" #include "qpselect.h" #include "qpthreads.h" #include "qtime.h" #include "memory.h" #include "vector.h" /*------------------------------------------------------------------------------ * Sort out QPSELECT_DEBUG. * * Set to 1 if defined, but blank. * Set to QDEBUG if not defined. * * Force to 0 if VTY_NO_DEBUG is defined and not zero. * * So: defaults to same as QDEBUG, but no matter what QDEBUG is set to: * * * can set QPSELECT_DEBUG == 0 to turn off debug * * or set QPSELECT_DEBUG != 0 to turn on debug * * or set QPSELECT_NO_DEBUG != to force debug off */ #ifdef QPSELECT_DEBUG /* If defined, make it 1 or 0 */ # if IS_BLANK_OPTION(QPSELECT_DEBUG) # undef QPSELECT_DEBUG # define QPSELECT_DEBUG 1 # endif #else /* If not defined, follow QDEBUG */ # define QPSELECT_DEBUG QDEBUG #endif #ifdef QPSELECT_NO_DEBUG /* Override, if defined */ # if IS_NOT_ZERO_OPTION(QPSELECT_NO_DEBUG) # undef QPSELECT_DEBUG # define QPSELECT_DEBUG 0 # endif #endif enum { qpselect_debug = QPSELECT_DEBUG } ; /*============================================================================== * Quagga pselect -- qps_xxxx * * Here and in qpselect.h is a data structure for managing multiple file * descriptors and running pselect to wait for I/O activity and to multiplex * between the file descriptors. * * The qps_selection structure manages a collection of file descriptors which * are to be waited on together in a pselect statement. * * NB: it is ASSUMED that a qps_selection will be private to the thread in * which it is created and used. * * There is NO mutex handling here. * * This supports pselect, so supports: * * * waiting for file descriptors, which may each be expecting any combination * of error/read/write events. * * Files may be added or removed from the selection. Files in the selection * may then be enabled/disabled for any combination of error/read/write * "mode" events. * * * a timeout *time* * * This is a qtime monotonic time at which to time out. (This is unlike * pselect() itself, which takes a timeout interval.) * * Infinite timeouts are not supported. * * * an optional signal number and sigmask * * So that a signal may be used to interrupt a waiting pselect. * * For this to work there must be a signal which is generally masked, and * is unmasked for the duration of the pselect. * * When a pselect returns there may be a number of files with events pending. * The qps_dispatch_next() calls the action routine for the next event to be * dealt with. Events are dispatched in the order: error, read and write, and * then in file descriptor order. (So all error events in fd order, then all * read events, and so on.) * * Note that at no time are any modes automatically disabled. So the system is * level triggered. So, for example, a read event that is not dealt with will * be triggered again on the next pselect -- unless the read mode is explicitly * disabled for the file. * * Action Functions * ---------------- * * There is a separate action function for each mode. Each file has its own * set of action functions -- so these may be used to implement a form of * state machine for the file. * * When the action function is called it is passed the qps_file structure and * the file_info pointer from that structure. * * During an action function modes may be enabled/disabled, actions changed, * the file removed from the selection... there are no restrictions. */ /*============================================================================== * qps_selection handling */ /* See qps_make_super_set_map() below. */ static short fd_byte_count[FD_SETSIZE] ; /* number of bytes for fds 0..fd */ /* Forward references */ static void qps_make_super_set_map(void) ; static void qps_selection_re_init(qps_selection qps) ; static qps_file qps_file_lookup_fd(qps_selection qps, fd_t fd, qps_file insert); static void qps_file_remove(qps_selection qps, qps_file qf) ; static void qps_super_set_zero(fd_super_set* p_set, int n) ; static int qps_super_set_cmp(fd_super_set* p_a, fd_super_set* p_b, int n) ; static int qps_next_fd_pending(fd_super_set* pending, fd_t fd, fd_t fd_last) ; static void qps_selection_validate(qps_selection qps) ; /*------------------------------------------------------------------------------ * Initialise a selection -- allocating it if required. * * Returns the qps_selection. */ extern void qps_start_up(void) { qps_make_super_set_map() ; /* map the fd_super_set */ } ; /*------------------------------------------------------------------------------ * Initialise a selection -- allocating it if required. * * Returns the qps_selection. * * NB: when initialising an existing selection which has been used before, it * is the caller's responsibility to have dealt with its contents before * calling this. */ extern qps_selection qps_selection_init_new(qps_selection qps) { if (qps == NULL) qps = XCALLOC(MTYPE_QPS_SELECTION, sizeof(struct qps_selection)) ; qps_selection_re_init(qps) ; return qps ; } ; /*------------------------------------------------------------------------------ * Re-initialise a selection. * * It is the caller's responsibility to have dealt with any active files before * calling this. */ static void qps_selection_re_init(qps_selection qps) { memset(qps, 0, sizeof(struct qps_selection)) ; /* Zeroising initialises: * * fd_count -- no fd's yet * fd_direct -- not direct lookup * * files -- empty vector * * enabled_count -- no fd's enabled in any mode * enabled -- empty bit vectors * * tried_fd_last -- nothing tried yet * tried_count -- nothing tried yet * results -- empty bit vectors * * pend_count -- no results to dispatch * pend_mnum -- unset * pend_fd -- unset * * signum -- no signal to be enabled * sigmask -- unset * * So nothing much else to do: */ qps->fd_last = fd_undef ; /* not an fd in sight. */ } ; /*------------------------------------------------------------------------------ * Add given file to the selection, setting its fd and pointer to further * file information. All modes are disabled. * * This initialises most of the qps_file structure, but not the actions. * * NB: while a file is a member of a selection, the fd MUST be a valid, open * fd -- otherwise, could end up here reusing an fd that was closed and is * now open again. * * Adding a file using the same fd as an existing file is a FATAL error. * * Adding a file which is already a member of a selection is a FATAL error. */ extern void qps_add_file(qps_selection qps, qps_file qf, fd_t fd, void* file_info) { passert((qf->selection == NULL) && (fd >= fd_first)) ; qf->selection = qps ; qf->file_info = file_info ; qf->fd = fd ; qf->enabled_bits = 0 ; qps_file_lookup_fd(qps, fd, qf) ; /* Add. */ } ; /*------------------------------------------------------------------------------ * Remove given file from its selection, if any. * * Note that to be a member of a selection MUST have a valid fd, so... BEFORE * closing an fd, must remove the file from any selection. (If is not a * member, may or may not have a valid fd.) * * It is the callers responsibility to ensure that the file is in a suitable * state to be removed from the selection. * * When the file is removed it is disabled in all modes. */ extern void qps_remove_file(qps_file qf) { if (qf->selection != NULL) qps_file_remove(qf->selection, qf) ; } ; /*------------------------------------------------------------------------------ * Ream (another) file out of the selection. * * If selection is empty, release the qps_selection structure, if required. * * Useful for emptying out and discarding a selection: * * while ((qf = qps_selection_ream(qps, free_it))) * ... do what's required to release the qps_file * * The file is removed from the selection before being returned. If the caller * is able to release the qf, then it should do so, otherwise it can be left * for the owner to release (which they can do without reference to the * selection, which may by then have been released). * * Returns NULL when selection is empty (and has been released, if required). * * If the selection is not released, it may be reused without reinitialisation. * * NB: once reaming has started, the selection MUST NOT be used for anything, * and the process MUST be run to completion. */ extern qps_file qps_selection_ream(qps_selection qps, free_keep_b free_structure) { qps_file qf ; qf = vector_get_last_item(&qps->files) ; if (qf != NULL) qps_file_remove(qps, qf) ; else { passert(qps->fd_count == 0) ; vector_reset(&qps->files, keep_it) ; /* empty vector, free body * but keep embedded vector */ if (free_structure) XFREE(MTYPE_QPS_SELECTION, qps) ; else qps_selection_re_init(qps) ; } ; return qf ; } ; /*------------------------------------------------------------------------------ * Set the signal mask for the selection. * * This supports the unmasking of one or more signals for the duration of the * pselect operation. * * * If the set of signals masked by the thread changes, then this function * should be called again. * * Setting a sigmask == NULL turns OFF the use of the sigmask. */ extern void qps_set_signal(qps_selection qps, const sigset_t* sigmask) { qps->sigmask = sigmask ; } ; /*------------------------------------------------------------------------------ * Execute a pselect for the given selection -- subject to the given maximum * time to wait. * * There is no support for an infinite timeout. * * Returns: -1 => EINTR occurred -- ie a signal has gone off * 0 => hit timeout -- no files are ready * > 0 => there are this many files ready in one or more modes * * All other errors are FATAL. * * The qps_dispatch_next() processes the returns from pselect(). */ extern int qps_pselect(qps_selection qps, qtime_t max_wait) { struct timespec ts ; qps_mnum_t mnum ; fd_set* p_fds[qps_mnum_count] ; int n ; if (qpselect_debug) qps_selection_validate(qps) ; /* If there is stuff still pending, tidy up by zeroising the result */ /* vectors. This is to make sure that when bits are copied from */ /* the enabled vectors, there are none from a previous run of pselect */ /* left hanging about. (pselect SHOULD ignore everything above the */ /* given count of fds -- but it does no harm to be tidy, and should */ /* not have to do this often.) */ if (qps->pend_count != 0) qps_super_set_zero(qps->results, qps_mnum_count) ; /* Prepare the argument/result bitmaps */ /* Capture pend_mnum and tried_count[] */ n = (qps->fd_last >= 0) ? fd_byte_count[qps->fd_last] /* copy up to last sig. byte */ : 0 ; qps->pend_mnum = qps_mnum_count ; for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) if ((qps->tried_count[mnum] = qps->enabled_count[mnum]) != 0) { qassert(n != 0) ; /* n == 0 => no fds ! */ memcpy(&(qps->results[mnum].bytes), &(qps->enabled[mnum].bytes), n) ; p_fds[mnum] = &(qps->results[mnum].fdset) ; if (mnum < qps->pend_mnum) qps->pend_mnum = mnum ; /* collect first active mode */ } else p_fds[mnum] = NULL ; /* Capture tried_fd_last and set initial pend_fd. */ qps->tried_fd_last = qps->fd_last ; qps->pend_fd = 0 ; /* Make sure not trying to do something stupid */ if (max_wait < 0) max_wait = 0 ; /* Finally ready for the main event */ n = pselect(qps->fd_last + 1, p_fds[qps_read_mnum], p_fds[qps_write_mnum], p_fds[qps_error_mnum], qtime2timespec(&ts, max_wait), qps->sigmask) ; /* If have something, set and return the pending count. */ if (n > 0) { assert(qps->pend_mnum < qps_mnum_count) ; /* expected something */ return qps->pend_count = n ; /* set and return pending count */ } ; /* Nothing pending at all */ qps->pend_count = 0 ; /* qps_dispatch_next() does nothing */ /* Flush the results vectors -- not apparently done if n <= 0) */ qps_super_set_zero(qps->results, qps_mnum_count) ; /* Return appropriately, if we can */ if ((n == 0) || (errno == EINTR)) return n ; zabort_errno("Failed in pselect") ; } ; /*------------------------------------------------------------------------------ * Dispatch the next errored/readable/writeable file, as returned by the * most recent qps_pselect(). * * Processes the errored files, then the readable and lastly the writeable. * * Processes one file per call of this function, by invoking the file's * "action" routine. * * If a given file is ready in more than one mode, all modes will be processed, * unless the action routine for one mode disables the file for other modes, or * removes it from the selection. * * Returns the number of files left to process (after the one just processed). * * NB: clears result bits as it finds them -- so at end of process, the * result bit vectors should be zeroised again. Also, this allows the * search to proceed from the last known fd -- won't find it again ! */ extern int qps_dispatch_next(qps_selection qps) { fd_t fd ; qps_file qf ; qps_mnum_t mnum ; if (qpselect_debug) qps_selection_validate(qps) ; if (qps->pend_count == 0) return 0 ; /* quit immediately of nothing to do. */ fd = qps->pend_fd ; /* look for fd >= this */ mnum = qps->pend_mnum ; /* starting with this mode */ qassert( (mnum >= 0) && (mnum < qps_mnum_count) && (qps->tried_count[mnum] != 0) && (qps->pend_count > 0) && (qps->tried_fd_last >= 0)) ; while (1) { fd = qps_next_fd_pending(&(qps->results[mnum]), fd, qps->tried_fd_last) ; if (fd >= 0) break ; /* easy if have another fd in current mode. */ do /* step to next mode that was not empty */ { qps->tried_count[mnum] = 0 ; /* tidy up as we go */ ++mnum ; if (mnum >= qps_mnum_count) zabort("Unexpectedly ran out of pending stuff") ; } while (qps->tried_count[mnum] == 0) ; qps->pend_mnum = mnum ; /* update mode */ fd = 0 ; /* back to the beginning */ } ; qps->pend_count -= 1 ; /* one less pending */ qps->pend_fd = fd ; /* update scan */ qf = qps_file_lookup_fd(qps, fd, NULL) ; qassert( ((qf->enabled_bits && qps_mbit(mnum)) != 0) && (qf->actions[mnum] != NULL) ) ; qf->actions[mnum](qf, qf->file_info) ; /* dispatch the required action */ return qps->pend_count ; } ; /*============================================================================== * qps_file structure handling */ /*------------------------------------------------------------------------------ * Initialise qps_file structure -- allocating one if required. * * If a template is given, then the action functions are copied from there to * the new structure. See above for discussion of action functions. * * Once initialised, the file may be added to a selection. * * Returns the qps_file. */ extern qps_file qps_file_init_new(qps_file qf, qps_file template) { if (qf == NULL) qf = XCALLOC(MTYPE_QPS_FILE, sizeof(struct qps_file)) ; else memset(qf, 0, sizeof(struct qps_file)) ; /* Zeroising has initialised: * * selection -- NULL -- ditto * * file_info -- NULL -- is set by qps_add_file() * fd -- unset -- ditto * * enabled_bits -- nothing enabled * * actions[] -- all set to NULL */ qf->fd = fd_undef ; /* no fd set yet */ if (template != NULL) memcpy(qf->actions, template->actions, sizeof(qf->actions)) ; return qf ; } ; /*------------------------------------------------------------------------------ * Free dynamically allocated qps_file structure -- if any. * * Removes from any selection may be a member of. Note that to be a member of * a selection MUST have a valid fd -- but if is not a member, may or may not * have a valid fd. * * If there is a valid fd -- close it ! * * Returns: NULL */ extern qps_file qps_file_free(qps_file qf) { if (qf != NULL) { if (qf->selection != NULL) qps_file_remove(qf->selection, qf) ; if (qf->fd >= fd_first) { close(qf->fd) ; qf->fd = fd_undef ; } ; XFREE(MTYPE_QPS_FILE, qf) ; } ; return NULL ; } ; /*------------------------------------------------------------------------------ * Enable (or re-enable) file for the given mode. * * If the action argument is not NULL, set the action for the mode. * * NB: It is a FATAL error to enable a mode with a NULL action. * * NB: It is a FATAL error to enable modes for a file which is not in a * selection. */ extern void qps_enable_mode(qps_file qf, qps_mnum_t mnum, qps_action* action) { qps_mbit_t mbit = qps_mbit(mnum) ; qps_selection qps = qf->selection ; qassert(qps != NULL) ; qassert((mnum >= 0) && (mnum <= qps_mnum_count)) ; if (action != NULL) qf->actions[mnum] = action ; else qassert(qf->actions[mnum] != NULL) ; if (qf->enabled_bits & mbit) qassert(FD_ISSET(qf->fd, &(qps->enabled[mnum].fdset))) ; else { qassert( ! FD_ISSET(qf->fd, &(qps->enabled[mnum].fdset))) ; FD_SET(qf->fd, &(qps->enabled[mnum].fdset)) ; ++qps->enabled_count[mnum] ; qf->enabled_bits |= mbit ; } ; } ; /*------------------------------------------------------------------------------ * Set action for given mode -- does not enable/disable. * * May unset an action by setting it NULL ! * * See above for discussion of action functions. * * NB: it is a fatal error to unset an action for a mode which is enabled. */ extern void qps_set_action(qps_file qf, qps_mnum_t mnum, qps_action* action) { qassert((mnum >= 0) && (mnum <= qps_mnum_count)) ; if (action == NULL) passert((qf->enabled_bits & qps_mbit(mnum)) == 0) ; qf->actions[mnum] = action ; } ; /*------------------------------------------------------------------------------ * Disable file for one or more modes. * * If there are any pending results for the modes, those are discarded. * * Note that this is modestly "optimised" to deal with disabling a single mode. * (Much of the time only the write mode will be being disabled !) * * NB: it is safe to disable modes which are not enabled -- even if the file * is not currently a member of a selection. (If it is not a member of a * collection no modes should be enabled !) */ static qps_mnum_t qps_first_mnum[qps_mbit(qps_mnum_count)] = { -1, /* 0 -> -1 -- no bit set */ 0, /* 1 -> 0 -- B0 is first bit */ 1, /* 2 -> 1 -- B1 is first bit */ 1, /* 3 -> 1 -- B1 is first bit */ 2, /* 4 -> 2 -- B2 is first bit */ 2, /* 5 -> 2 -- B2 is first bit */ 2, /* 6 -> 2 -- B2 is first bit */ 2 /* 7 -> 2 -- B2 is first bit */ } ; CONFIRM(qps_mbit(qps_mnum_count) == 8) ; extern void qps_disable_modes(qps_file qf, qps_mbit_t mbits) { qps_mnum_t mnum ; qps_selection qps = qf->selection ; qassert((mbits >= 0) && (mbits <= qps_all_mbits)) ; mbits &= qf->enabled_bits ; /* don't bother with any not enabled */ qf->enabled_bits ^= mbits ; /* unset what we're about to disable */ while (mbits != 0) { mnum = qps_first_mnum[mbits] ; qassert(qps->enabled_count[mnum] > 0) ; qassert(FD_ISSET(qf->fd, &(qps->enabled[mnum].fdset))) ; FD_CLR(qf->fd, &(qps->enabled[mnum].fdset)) ; --qps->enabled_count[mnum] ; if ((qps->pend_count != 0) && (qps->tried_count[mnum] != 0) && (FD_ISSET(qf->fd, &(qps->results[mnum].fdset)))) { FD_CLR(qf->fd, &(qps->results[mnum].fdset)) ; --qps->pend_count ; } ; mbits ^= qps_mbit(mnum) ; } ; } ; /*============================================================================== * Handling the files vector. * * For small numbers of fd's, the files vector is kept as a list, in fd order. * Files are found by binary chop, and added/removed by insert/delete in the * list. * * For large numbers of fd's, the files vector is kept as an array, indexed by * fd. */ /*------------------------------------------------------------------------------ * Comparison function for binary chop */ static int qps_fd_cmp(const int** pp_fd, const qps_file* p_qf) { if (**pp_fd < (*p_qf)->fd) return -1 ; if (**pp_fd > (*p_qf)->fd) return +1 ; return 0 ; } /*------------------------------------------------------------------------------ * Lookup/Insert file by file-descriptor. * * Inserts if insert argument is not NULL. * * Returns the file we found (if any) or the file we just inserted. * * NB: FATAL error to insert file with same fd as an existing one. */ static qps_file qps_file_lookup_fd(qps_selection qps, fd_t fd, qps_file insert) { qps_file qf ; vector_index_t i ; int ret ; qassert((fd >= 0) && (fd < (int)FD_SETSIZE)) ; /* Look-up */ /* */ /* Set i = index for entry in files vector */ /* Set ret = 0 <=> i is exact index. */ /* < 0 <=> i is just after where entry may be inserted */ /* > 0 <=> i is just before where entry may be inserted */ if (qps->fd_direct) { i = fd ; /* index of entry */ ret = 0 ; /* how to insert, if do */ } else i = vector_bsearch(&qps->files, (vector_bsearch_cmp*)qps_fd_cmp, &fd, &ret) ; if (ret == 0) qf = vector_get_item(&qps->files, i) ; /* NULL if not there */ else qf = NULL ; /* not there */ /* Insert now, if required and can: keep fd_count and fd_last up to date. */ if (insert != NULL) { if (qf != NULL) zabort("File with given fd already exists in qps_selection") ; /* If required, change up to a directly addressed files vector. */ if (!qps->fd_direct && (qps->fd_count > 9)) { vector tmp ; tmp = vector_move_here(NULL, &qps->files) ; while ((qf = vector_pop_item(tmp)) != NULL) vector_set_item(&qps->files, qf->fd, qf) ; vector_free(tmp) ; qps->fd_direct = 1 ; i = fd ; /* index is now the fd */ ret = 0 ; /* and insert there */ } ; /* Now can insert accordint to i & ret */ vector_insert_item_here(&qps->files, i, ret, insert) ; ++qps->fd_count ; if (fd > qps->fd_last) qps->fd_last = fd ; qf = insert ; /* will return what we just inserted. */ } ; /* Sanity checking. */ qassert( (qf == NULL) || ((qps == qf->selection) && (fd == qf->fd)) ) ; /* Return the file we found or inserted. */ return qf ; } ; /*------------------------------------------------------------------------------ * Remove file from selection. * * NB: FATAL error if file is not in the selection, or the file-descriptor * is invalid (or refers to some other file !). */ static void qps_file_remove(qps_selection qps, qps_file qf) { qps_file qfd ; fd_t fd_last ; passert((qf->fd >= 0) && (qf->fd <= qps->fd_last) && (qps == qf->selection)) ; /* Look-up and remove. */ if (qps->fd_direct) { qfd = vector_unset_item(&qps->files, qf->fd) ; /* NULL if not there */ fd_last = vector_end(&qps->files) - 1 ; } else { qps_file qf_last ; int ret ; vector_index_t i = vector_bsearch(&qps->files, (vector_bsearch_cmp*)qps_fd_cmp, &qf->fd, &ret) ; if (ret == 0) qfd = vector_delete_item(&qps->files, i) ; else qfd = NULL ; qf_last = vector_get_last_item(&qps->files) ; if (qf_last != NULL) fd_last = qf_last->fd ; else fd_last = -1 ; } ; passert(qfd == qf) ; /* must have been there and be the expected file */ /* Keep fd_count and fd_last up to date. */ qassert(qps->fd_count > 0) ; --qps->fd_count ; qassert(fd_last >= (qps->fd_count - 1)) ; qps->fd_last = fd_last ; /* Also, remove the from all vectors. */ qps_disable_modes(qf, qps_all_mbits) ; /* Is no longer in the selection. */ qf->selection = NULL ; } ; /*============================================================================== * fd_super_set support. * * For large sets of file descriptors something faster than testing for all * possible bits is required. The fd_super_set assumes that the fd_set is a * straightforward bit-vector, and overlays a 32-bit word array and a byte * array over that. * * Cannot tell if the underlying bit vector is arranged in bytes, or some * longer words. Cannot tell if words are held big or little endian. Cannot * tell if lowest numbered fd will be highest or lowest in whatever unit it's * held in. * * So... we have maps for fd -> our word index, and fd -> byte index. * * we have a map for fd -> mask for bit used in its byte. * * We require that fds will be numbered consistently in bytes. That is, * every (fd mod 8) == n will appear in the same bit in a byte, for all fd ( * for n = 0..7). This allows the final map, which takes a byte value and * returns the lowest numbered fd in the byte, mod 8. * * To copy all the bytes for all descriptors 0..fd, also construct * fd_byte_count[] -- which copes with the fact that on a big-endian machine * it is possible that descriptor fd - 8 may be in a higher numbered byte than * fd ! Using this count assumes that the underlying system really does not * look at bits beyond the given maximum fd. */ static short fd_word_map[FD_SETSIZE] ; /* maps fd to word index */ static short fd_byte_map[FD_SETSIZE] ; /* maps fd to byte index */ static uint8_t fd_bit_map [FD_SETSIZE] ; /* maps fd to bit in byte */ static int8_t fd_first_map[256] ; /* maps byte value to 0..7, where that */ /* is the lowest fd bit set in byte. */ /*------------------------------------------------------------------------------ * Cross Check * * Where the shape of the bit map is known, this will test that the correct * bit map has been deduced. * * Requires the following to be defined: * * QPS_CROSS_CHECK -- weebb * * where: w -- number of bytes per word, 1.. * ee -- 10 => big-endian bytes in word * 01 => little-endian * bb -- 70 => b7 is MS bit, b0 is LS bit * 07 => b0 is MS bit, b7 is LS bit * * So: * * 10170 => a bit map handled as bytes * * 40170 => a bit map handled as little-endian 32-bit words * * ...though this is actually no different to handling the bit map * as bytes. * * 41070 => a bit map handled as big-endian 32-bit words * * 10107 => a bit map handled as bytes, where the "leftmost" bit is the first * bit in the bitmap: * * ...a big-endian machine, where the bit map is handled as n-bit * words, with the "leftmost" bit being the first would be like * this too. */ #define QPS_CROSS_CHECK 40170 enum { #ifdef QPS_CROSS_CHECK qps_cross_check = 1, qps_cc_word_bytes = QPS_CROSS_CHECK / 10000, qps_cc_byte_ord = (QPS_CROSS_CHECK / 100) % 100, qps_cc_bit_ord = QPS_CROSS_CHECK % 100, #else qps_cross_check = 0, /* no cross check */ qps_cc_word_bytes = 1, /* byte_wise */ qps_cc_byte_ord = 1, /* little-endian */ qps_cc_bit_ord = 70, /* standard bit order */ #endif qps_cc_word_bits = qps_cc_word_bytes * 8 } ; CONFIRM((qps_cc_word_bytes == 16) || (qps_cc_word_bytes == 8) || (qps_cc_word_bytes == 4) || (qps_cc_word_bytes == 2) || (qps_cc_word_bytes == 1)) ; CONFIRM((qps_cc_byte_ord == 10) || (qps_cc_byte_ord == 1)) ; CONFIRM((qps_cc_bit_ord == 70) || (qps_cc_bit_ord == 7)) ; /* Functions required for the cross check. */ static inline int qpd_cc_word(fd_t fd) { return fd / qps_cc_word_bits ; } ; static inline int qps_cc_byte(fd_t fd) { if (qps_cc_byte_ord == 10) return (qpd_cc_word(fd) * qps_cc_word_bytes) + qps_cc_word_bytes - 1 - ((fd % qps_cc_word_bits) / 8) ; else return fd / 8 ; } ; static inline uint8_t qps_cc_bit(fd_t fd) { if (qps_cc_bit_ord == 70) return 0x01 << (fd & 0x7) ; else return 0x80 >> (fd & 0x7) ; } ; static int ccFD_ISSET(fd_t fd, fd_set* set) { return (*((uint8_t*)set + qps_cc_byte(fd)) & qps_cc_bit(fd)) != 0 ; } ; /*------------------------------------------------------------------------------ * Scan for next fd in given fd set, and clear it. * * Starts at the given fd, will not consider anything above fd_last. * * Returns next fd, or -1 if none. */ static int qps_next_fd_pending(fd_super_set* pending, fd_t fd, fd_t fd_last) { uint8_t b ; qassert((fd >= 0) && (fd <= fd_last)) ; while (pending->words[fd_word_map[fd]] == 0) /* step past zero words */ { fd = (fd & ~ (FD_WORD_BITS - 1)) + FD_WORD_BITS ; /* step to start of next word */ if (fd > fd_last) return -1 ; /* quit if past last */ } ; fd &= ~0x0007 ; /* step back to first in byte */ while ((b = pending->bytes[fd_byte_map[fd]]) == 0) { fd += 8 ; if (fd > fd_last) return -1 ; } ; fd += fd_first_map[b] ; qassert(fd <= fd_last) ; qassert((b & fd_bit_map[fd]) == fd_bit_map[fd]) ; FD_CLR(fd, &pending->fdset) ; qassert((b ^ fd_bit_map[fd]) == pending->bytes[fd_byte_map[fd]]) ; return fd ; } ; /*------------------------------------------------------------------------------ * Make a map of the fd_super_set. * * The form of an fd_set is not defined. This code verifies that it is, in * fact a bit vector, and hence that the fd_super_set works here ! * * It is a FATAL error if things don't work out. */ static void qps_make_super_set_map(void) { fd_super_set test ; fd_t fd ; int i, iw, ib ; /* (1) check that a zeroised fd_super_set is an empty one. */ qps_super_set_zero(&test, 1) ; for (fd = fd_first ; fd < (int)FD_SETSIZE ; ++fd) if (FD_ISSET(fd, &test.fdset)) zabort("Zeroised fd_super_set is not empty") ; /* (2) check that zeroising the fd_set doesn't change things */ FD_ZERO(&test.fdset) ; for (iw = 0 ; iw < (int)FD_SUPER_SET_WORD_SIZE ; ++iw) if (test.words[iw] != 0) zabort("Zeroised fd_super_set is not all zero words") ; /* (3) check that setting one fd sets one bit, and construct the */ /* fd_word_map[], fd_byte_map[] and fd_bit_map[]. */ for (fd = fd_first ; fd < (int)FD_SETSIZE ; ++fd) { fd_word_t w ; FD_SET(fd, &test.fdset) ; w = 0 ; for (iw = 0 ; iw < (int)FD_SUPER_SET_WORD_SIZE ; ++iw) { if (test.words[iw] != 0) { if (w != 0) zabort("FD_SET set a bit in more than one word") ; w = test.words[iw] ; if ((w == 0) || ((w & (w - 1)) != 0)) zabort("FD_SET set more than one bit in a word") ; fd_word_map[fd] = iw ; ib = iw * FD_WORD_BYTES ; while (test.bytes[ib] == 0) { ++ib ; if (ib >= ((iw + 1) * FD_WORD_BYTES)) zabort("FD_SET set something beyond the expected bytes") ; } ; fd_byte_map[fd] = ib ; fd_bit_map[fd] = test.bytes[ib] ; } ; } ; if (w == 0) zabort("FD_SET did not set any bit in any word") ; FD_CLR(fd, &test.fdset) ; for (iw = 0 ; iw < (int)FD_SUPER_SET_WORD_SIZE ; ++iw) if (test.words[iw] != 0) zabort("FD_CLR did not leave the fd_super_set empty") ; } ; /* (4) check the fd_byte_map. */ /* make sure that have 8 contiguous fd to a byte. */ /* make sure that have 32 contiguous fd to a word. */ for (fd = fd_first ; fd < (int)FD_SETSIZE ; fd += 8) { int fds ; ib = fd_byte_map[fd] ; iw = fd_word_map[fd] ; /* Must share the same byte as the next 7 fds */ for (fds = fd + 1 ; fds < (fd + 8) ; ++fds) if (fd_byte_map[fds] != ib) zabort("Broken fd_byte_map -- not 8 contiguous fd's in a byte") ; /* Must not share the same byte as any other set of 8 fd's */ for (fds = 0 ; fds < (int)FD_SETSIZE ; fds += 8) if ((fd_byte_map[fds] == ib) && (fds != fd)) zabort("Broken fd_byte_map -- fd's not in expected bytes") ; /* Must be one of the bytes in the current word's fd's */ if ( (ib < (iw * FD_WORD_BYTES)) || (ib >= ((iw + 1) * FD_WORD_BYTES)) ) zabort("Broken fd_byte_map -- fd's not in expected words") ; } ; /* (5) check the fd_bit_map */ /* make sure that all fd mod 8 map to the same byte value */ for (i = 0 ; i < 8 ; ++i) { uint8_t b = fd_bit_map[i] ; for (fd = 8 + i ; fd < (int)FD_SETSIZE ; fd += 8) if (fd_bit_map[fd] != b) zabort("Broken fd_bit_map -- inconsistent bit mapping") ; } ; /* (6) construct fd_first_map, to get lowest numbered fd (mod 8) from */ /* a given byte value. */ for (i = 0 ; i < 256 ; ++i) fd_first_map[i] = -1 ; for (fd = 0 ; fd < 8 ; ++fd) { uint8_t fdb = fd_bit_map[fd] ; for (i = 1 ; i < 256 ; ++i) if ((fd_first_map[i] == -1) && ((i & fdb) != 0)) fd_first_map[i] = fd ; } ; if (fd_first_map[0] != -1) zabort("Broken fd_first_map -- invalid result for 0") ; for (i = 1 ; i < 256 ; ++i) if (fd_first_map[i] == -1) zabort("Broken fd_first_map -- missing bits") ; /* (7) construct fd_byte_count[] -- number of bytes required to */ /* include fds 0..fd. */ i = 0 ; for (fd = fd_first ; fd < (int)FD_SETSIZE ; ++fd) { int c = fd_byte_map[fd] + 1 ; if (c < i) c = i ; /* use largest so far. => big-endian */ else i = c ; /* keep largest so far up to date */ fd_byte_count[fd] = c ; } ; if (!qps_cross_check) return ; /*---------------------------------------------------------------------------- * Checking that the maps have been correctly deduced -- where know what * the mapping really is ! */ for (fd = fd_first ; fd < (int)FD_SETSIZE ; ++fd) { uint8_t b ; short c ; FD_ZERO(&test.fdset) ; FD_SET(fd, &test.fdset) ; if (!ccFD_ISSET(fd, &test.fdset)) zabort("FD_SET and ccFD_ISSET differ") ; iw = qpd_cc_word(fd) ; ib = qps_cc_byte(fd) ; b = qps_cc_bit(fd) ; if (qps_cc_byte_ord == 10) c = (iw + 1) * 4 ; else c = ib + 1 ; if (fd_word_map[fd] != iw) zabort("Broken fd_word_map") ; if (fd_byte_map[fd] != ib) zabort("Broken fd_byte_map") ; if (fd_bit_map[fd] != b) zabort("Broken fd_bit_map") ; if (fd_byte_count[fd] != c) zabort("Broken fd_byte_count") ; } ; for (i = 1 ; i < 256 ; ++i) { uint8_t b = i ; fd = 0 ; if (qps_cc_bit_ord == 70) { while ((b & 1) == 0) { b >>= 1 ; ++fd ; } ; } else { while ((b & 0x80) == 0) { b <<= 1 ; ++fd ; } ; } ; if (fd_first_map[i] != fd) zabort("Broken fd_first_map") ; } ; return ; } ; /*------------------------------------------------------------------------------ * Zeroise 'n' contiguous fd_super_sets * * NB: this MUST be used in place of FD_ZERO because the fd_set may be shorter * than the overlayed words/bytes vectors. * * NB: it is CONFIRMED elsewhere that the fd_set is no longer than the overlays. */ static void qps_super_set_zero(fd_super_set* p_set, int n) { memset(p_set, 0, SIZE(fd_super_set, n)) ; } ; /*------------------------------------------------------------------------------ * Compare 'n' contiguous fd_super_sets * * Returns 0 <=> equal */ static int qps_super_set_cmp(fd_super_set* p_a, fd_super_set* p_b, int n) { return memcmp(p_a, p_b, SIZE(fd_super_set, n)) ; } ; /*------------------------------------------------------------------------------ * Count the number of bits set in 'n' contiguous fd_super_sets. */ static int qps_super_set_count(fd_super_set* p_set, int n) { fd_word_t* p ; int count = 0 ; n *= FD_SUPER_SET_WORD_SIZE ; confirm(sizeof(fd_super_set) == (FD_SUPER_SET_WORD_SIZE * FD_WORD_BYTES)) ; p = (fd_word_t*)p_set ; while (n--) { fd_word_t w = *p++ ; while (w != 0) { ++count ; w &= (w - 1) ; } ; } ; return count ; } ; /*============================================================================== * Selection state check -- for debug purposes. * * Runs a check across a given selection and verifies that: * * 1) for !fd_direct that the files are in fd order in the vector * and are unique, and there are no NULL entries. * 2) for fd_direct that the file fd and the index match * and the last entry is not NULL * 3) that all files point at the selection * 4) that the enabled modes in each file are valid * 5) the number of files in the selection matches fd_count. * 6) the highest numbered fd matches fd_last * 7) that the enabled counts in the selection are correct * 8) that the enabled modes in each file match the enabled modes in the * selection * 9) that no extraneous fds are set in the enabled vectors * * If there are no pending fds: * * 10) if there are no pending fds, that the results vectors are empty. * * If there are pending fds: * * 11) that pend_mnum is valid and pend_fd <= tried_fd_last. * * 12) that the tried_count for modes 0..pend_mnum-1 is zero, * and the tried_count for pend_mnum is not. * * 13) that the result vectors for modes where tried count == 0 are empty. * * 14) that the remaining result bits are a subset of the enabled bits. * * 15) that no bits beyond tried_fd_last are set in the result vectors. * * 16) that no bits before pend_fd are set in the pemd_mnum result vector. * * 17) that the number of bits remaining matches pend_count. */ static void qps_selection_validate(qps_selection qps) { fd_t fd, fd_last ; int enabled_count[qps_mnum_count] ; fd_full_set enabled ; qps_file qf ; int n, mnum, p_mnum ; vector_index_t i ; /* 1..4) Run down the selection vector and check. */ /* Collect new enabled_count and enabled bit vectors. */ for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) enabled_count[mnum] = 0 ; qps_super_set_zero(enabled, qps_mnum_count) ; n = 0 ; fd_last = -1 ; for (VECTOR_ITEMS(&qps->files, qf, i)) { if (qf != NULL) { ++n ; /* Number of files */ if (qps->fd_direct) { if (qf->fd != (int)i) /* index and fd must match */ zabort("File vector index and fd mismatch") ; } else { if (qf->fd <= fd_last) /* must be unique and in order */ zabort("File vector not in order") ; } ; fd_last = qf->fd ; /* keep track of last fd */ if (qf->selection != qps) /* file must refer to selection */ zabort("File does not refer to its selection") ; if ((qf->enabled_bits < 0) || (qf->enabled_bits > qps_all_mbits)) zabort("File enabled bits are invalid") ; /* Capture enabled state of all files. */ for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) if (qf->enabled_bits & qps_mbit(mnum)) { ++enabled_count[mnum] ; FD_SET(qf->fd, &enabled[mnum].fdset) ; } ; } else if (!qps->fd_direct) zabort("Found NULL entry in !fd_direct files vector") ; } ; if ((n != 0) && (vector_get_last_item(&qps->files) == NULL)) zabort("Last entry in file vector is NULL") ; /* 5) check that the number of files tallies. */ if (n != qps->fd_count) zabort("Number of files in the selection does not tally") ; /* 6) check the last fd */ if ( (qps->fd_last < (n - 1)) || (fd_last != qps->fd_last) ) zabort("The last fd does not tally") ; /* 7) check that the enabled counts tally. */ for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) if (enabled_count[mnum] != qps->enabled_count[mnum]) zabort("Enabled counts do not tally") ; /* 8..9) Check that the enabled vectors are the same as the ones just */ /* created by scanning the files. */ if (qps_super_set_cmp(enabled, qps->enabled, qps_mnum_count) != 0) zabort("Enabled bit vectors do not tally") ; /* 10) if there are no pending fds, check result vectors empty. */ if (qps->pend_count == 0) { if (qps_super_set_count(qps->results, qps_mnum_count) != 0) zabort("Nothing pending, but result vectors not empty") ; return ; } ; /* This is to stop gcc whining about signed/unsigned comparisons. */ p_mnum = qps->pend_mnum ; /* 11) that pend_mnum is valid and pend_fd <= tried_fd_last. */ if ( (p_mnum < 0) || (p_mnum > qps_mnum_count) || (qps->pend_fd < 0) || (qps->pend_fd > qps->tried_fd_last) ) zabort("Invalid pend_mnum or pend_fd") ; /* 12) check tried_count[] */ for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) { if ((mnum < p_mnum) && (qps->tried_count[mnum] != 0)) zabort("Non-zero tried_count for mode < pend_mnum") ; if ((mnum == p_mnum) && (qps->tried_count[qps->pend_mnum] <= 0)) zabort("Zero tried_count for pend_mnum") ; if ((mnum > p_mnum) && (qps->tried_count[mnum] < 0)) zabort("Invalid tried_count for mode > pend_mnum") ; } ; /* 13) check result vectors for modes where tried count == 0 */ n = (qps_super_set_count(qps->results, qps_mnum_count) != 0) ; for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) if ((qps->tried_count[mnum] == 0) && (qps_super_set_count(&qps->results[mnum], 1) != 0)) zabort("Non-empty bit vector where tried count == 0") ; /* 14) check remaining results are a subset of the enableds. */ /* 15) check no bit beyond tried_fd_last is set in the results. */ /* 16) check no bit before pend_fd is set in the pemd_mnum results. */ /* 17) check the number of bits remaining matches pend_count. */ n = 0 ; for (mnum = 0 ; mnum < qps_mnum_count ; ++mnum) if (qps->tried_count[mnum] != 0) { for (fd = 0 ; fd < (int)FD_SETSIZE ; ++fd) if (FD_ISSET(fd, &qps->results[mnum].fdset)) { ++n ; if (fd > qps->tried_fd_last) zabort("Found pending fd beyond tried_fd_last") ; if ( ! FD_ISSET(fd, &qps->results[mnum].fdset)) zabort("Found pending fd which is not enabled") ; if ((mnum == p_mnum) && (fd < qps->pend_fd)) zabort("Found pending fd < current next pending") ; } ; } ; if (n != qps->pend_count) zabort("Non-empty bit vector where tried count == 0") ; } ; /*============================================================================== * Miniature pselect -- for where want to wait for a small number of things. */ /*------------------------------------------------------------------------------ * Initialise a qps_mini and set one fd in the given mode. * * If the fd is < 0, sets nothing (returns empty qps_mini). */ extern qps_mini qps_mini_set(qps_mini qm, int fd, qps_mnum_t mode) { qps_super_set_zero(qm->sets, qps_mnum_count) ; qm->fd_last = -1 ; qps_mini_add(qm, fd, mode) ; return qm ; } ; /*------------------------------------------------------------------------------ * Add given fd in the given mode to the given qps_mini. * * If the fd is < 0, adds nothing (returns qps_mini unchanged). */ extern void qps_mini_add(qps_mini qm, int fd, qps_mnum_t mode) { if (fd >= 0) { FD_SET(fd, &(qm->sets[mode].fdset)) ; if (fd > qm->fd_last) qm->fd_last = fd ; } ; } ; /*------------------------------------------------------------------------------ * Wait for a qps_mini -- with given time-out, in seconds. * * Zero time-out means wait indefinitely. * * If qm->timeout_set is false, sets the given time-out, otherwise uses the * current qm->interval/qm->end_time. * * Will exit on EINTR and that sets qm->timeout_set ! * * Returns what pselect returns: > 0 number of bits set * == 0 no bits set <=> timed out * and: == -1 => error -- see errno * == -2 => EINTR */ extern int qps_mini_wait(qps_mini qm, uint timeout, const sigset_t* sigmask) { struct timespec ts[1] ; qtime_t interval ; int n ; /* If first is set, then we set up the timeout * * Otherwise, we are returning here after an EINTR, or in any case want to * continue the previously set */ interval = 0 ; /* calm down compiler */ if (!qm->timeout_set) { if (timeout == 0) qm->indefinite = true ; else { qm->indefinite = false ; interval = QTIME(timeout) ; /* convert from seconds */ qm->end_time = qt_add_monotonic(interval) ; } } else { if (!qm->indefinite) { interval = qm->end_time - qt_get_monotonic() ; if (interval < 0) interval = 0 ; } ; } ; /* Do the pselect() and worry about the result. */ n = pselect(qm->fd_last + 1, &(qm->sets[qps_read_mnum].fdset), &(qm->sets[qps_write_mnum].fdset), &(qm->sets[qps_error_mnum].fdset), qm->indefinite ? NULL : qtime2timespec(ts, interval), sigmask) ; if (n >= 0) return n ; if (errno != EINTR) return -1 ; qm->timeout_set = true ; return -2 ; /* EINTR seen */ } ;