From 11bda4752b314848c793c25023c57b40968f9b9f Mon Sep 17 00:00:00 2001 From: Davin McCall Date: Fri, 14 Sep 2018 16:54:01 +0100 Subject: [PATCH] Updated bundled Dasynq to 1.1.5. --- README.md | 5 +- src/dasynq/dasynq-basewatchers.h | 54 +++++++++++++++++++- src/dasynq/dasynq-btree_set.h | 87 ++++++++++++++++---------------- src/dasynq/dasynq-daryheap.h | 2 + src/dasynq/dasynq-kqueue.h | 31 +++++------- src/dasynq/dasynq.h | 9 ++-- 6 files changed, 120 insertions(+), 68 deletions(-) diff --git a/README.md b/README.md index 6c295dc..41c2400 100644 --- a/README.md +++ b/README.md @@ -36,7 +36,10 @@ down and restarting the system. Dinit is designed to work on POSIXy operating systems such as Linux and OpenBSD. It is written in C++ and uses the [Dasynq](http://davmac.org/projects/dasynq/) -event handling library, which was written especially to support Dinit. +event handling library, which was written especially to support Dinit. (Note +that a copy of Dasynq is bundled with Dinit, so a separate copy is not +required for compilation; however, the bundled copy does not include the +documentation or test suite). Development goals include clean design, robustness, portability, and avoiding feature bloat (whilst still handling a variety of use cases). diff --git a/src/dasynq/dasynq-basewatchers.h b/src/dasynq/dasynq-basewatchers.h index fc5f6f5..cc8dc7f 100644 --- a/src/dasynq/dasynq-basewatchers.h +++ b/src/dasynq/dasynq-basewatchers.h @@ -6,6 +6,8 @@ // In general access to the members of the basewatcher should be protected by a mutex. The // event_dispatch lock is used for this purpose. +#include + namespace dasynq { namespace dprivate { @@ -51,8 +53,31 @@ namespace dprivate { // (non-public API) class base_watcher; + + class empty_node + { + DASYNQ_EMPTY_BODY + }; + + // heap_def decides the queue implementation that we use. It must be stable: template using dary_heap_def = dary_heap; - using prio_queue = stable_heap; + template using heap_def = stable_heap; + + namespace { + // use empty handles (not containing basewatcher *) if the handles returned from the + // queue are handle references, because we can derive a pointer to the containing basewatcher + // via the address of the handle in that case: + constexpr bool use_empty_node = std::is_same< + typename heap_def::handle_t_r, + typename heap_def::handle_t &>::value; + + using node_type = std::conditional::type; + } + + using prio_queue = heap_def; + + using prio_queue_emptynode = heap_def; + using prio_queue_bwnode = heap_def; template class fd_watcher; template class bidi_fd_watcher; @@ -138,6 +163,33 @@ namespace dprivate { } }; + // Retrieve watcher from queue handle: + inline base_watcher * get_watcher(prio_queue_emptynode &q, prio_queue_emptynode::handle_t &n) + { + uintptr_t bptr = (uintptr_t)&n; + _Pragma ("GCC diagnostic push") + _Pragma ("GCC diagnostic ignored \"-Winvalid-offsetof\"") + bptr -= offsetof(base_watcher, heap_handle); + _Pragma ("GCC diagnostic pop") + return (base_watcher *)bptr; + } + + inline dprivate::base_watcher * get_watcher(prio_queue_bwnode &q, prio_queue_bwnode::handle_t &n) + { + return q.node_data(n); + } + + // Allocate queue handle: + inline void allocate_handle(prio_queue_emptynode &q, prio_queue_emptynode::handle_t &n, base_watcher *bw) + { + q.allocate(n); + } + + inline void allocate_handle(prio_queue_bwnode &q, prio_queue_bwnode::handle_t &n, base_watcher *bw) + { + q.allocate(n, bw); + } + // Base signal event - not part of public API template class base_signal_watcher : public base_watcher diff --git a/src/dasynq/dasynq-btree_set.h b/src/dasynq/dasynq-btree_set.h index 2e2c090..bc547a2 100644 --- a/src/dasynq/dasynq-btree_set.h +++ b/src/dasynq/dasynq-btree_set.h @@ -10,22 +10,22 @@ namespace dasynq { template , int N = 8> class btree_set { - struct HeapNode; + struct heapnode; public: - using handle_t = HeapNode; - using handle_t_r = HeapNode &; + using handle_t = heapnode; + using handle_t_r = heapnode &; private: - struct SeptNode + struct septnode { P prio[N]; handle_t * hn_p[N]; // pointer to handle - SeptNode * children[N + 1]; - SeptNode * parent; + septnode * children[N + 1]; + septnode * parent; - SeptNode() + septnode() { // Do nothing; initialisation will be run later } @@ -83,30 +83,32 @@ class btree_set } }; - struct HeapNode + struct heapnode { - T data; // TODO this should be obscured to avoid early construction - SeptNode * parent = nullptr; - - HeapNode() + union nodedata_u { + T data; // TODO this should be obscured to avoid early construction - } + nodedata_u() {} + }; + + nodedata_u nodedata; + septnode * parent = nullptr; - template HeapNode(U... u) : data(u...) + heapnode() { - parent = nullptr; + } }; - SeptNode * root_sept = nullptr; // root of the B-Tree - SeptNode * left_sept = nullptr; // leftmost child (cache) - SeptNode * sn_reserve = nullptr; + septnode * root_sept = nullptr; // root of the B-Tree + septnode * left_sept = nullptr; // leftmost child (cache) + septnode * sn_reserve = nullptr; int num_alloced = 0; int num_septs = 0; int num_septs_needed = 0; - int next_sept = 1; // next num_allocd for which we need another SeptNode in reserve. + int next_sept = 1; // next num_allocd for which we need another septnode in reserve. // Note that sept nodes are always at least half full, except for the root sept node. // For up to N nodes, one sept node is needed; @@ -123,7 +125,7 @@ class btree_set if (__builtin_expect(num_alloced == next_sept, 0)) { if (++num_septs_needed > num_septs) { try { - SeptNode *new_res = new SeptNode(); + septnode *new_res = new septnode(); new_res->parent = sn_reserve; sn_reserve = new_res; num_septs++; @@ -138,15 +140,15 @@ class btree_set } } - SeptNode * alloc_sept() + septnode * alloc_sept() { - SeptNode * r = sn_reserve; + septnode * r = sn_reserve; sn_reserve = r->parent; r->init(); return r; } - void release_sept(SeptNode *s) + void release_sept(septnode *s) { s->parent = sn_reserve; sn_reserve = s; @@ -154,7 +156,7 @@ class btree_set // Merge rsibling, and one value from the parent, into lsibling. // Index is the index of the parent value. - void merge(SeptNode *lsibling, SeptNode *rsibling, int index) noexcept + void merge(septnode *lsibling, septnode *rsibling, int index) noexcept { int lchildren = lsibling->num_vals(); lsibling->hn_p[lchildren] = lsibling->parent->hn_p[index]; @@ -195,10 +197,10 @@ class btree_set // borrow values from, or merge with, a sibling node so that the node // is suitably (~>=50%) populated. - void repop_node(SeptNode *sept, int children) noexcept + void repop_node(septnode *sept, int children) noexcept { start: - SeptNode *parent = sept->parent; + septnode *parent = sept->parent; if (parent == nullptr) { // It's the root node, so don't worry about it, unless empty if (sept->hn_p[0] == nullptr) { @@ -212,7 +214,7 @@ class btree_set // Find a suitable sibling to the left or right: if (parent->children[0] == sept) { // take right sibling - SeptNode *rsibling = parent->children[1]; + septnode *rsibling = parent->children[1]; if (rsibling->num_vals() + children + 1 <= N) { // We can merge merge(sept, rsibling, 0); @@ -249,7 +251,7 @@ class btree_set } } - SeptNode *lsibling = parent->children[i-1]; + septnode *lsibling = parent->children[i-1]; int lchildren = lsibling->num_vals(); if (lchildren + children + 1 <= N) { // merge @@ -285,7 +287,7 @@ class btree_set T & node_data(handle_t & hn) noexcept { - return hn.data; + return hn.nodedata.data; } static void init_handle(handle_t &hn) noexcept @@ -294,18 +296,15 @@ class btree_set } // Allocate a slot, but do not incorporate into the heap: - template void allocate(handle_t &hndl, U... u) + template void allocate(handle_t &hn, U... u) { alloc_slot(); - // TODO should not really new over an existing object. - // T element in HeapNode should be obscured so we don't need a default-constructed - // T in it. - new (& hndl) HeapNode(u...); + new (& hn.nodedata.data) T(u...); } void deallocate(handle_t & hn) noexcept { - // hn.HeapNode::~HeapNode(); + hn.nodedata.data.T::~T(); num_alloced--; // Potentially release reserved sept node @@ -314,7 +313,7 @@ class btree_set num_septs_needed--; if (num_septs_needed < num_septs - 1) { // Note the "-1" margin is to alleviate bouncing allocation/deallocation - SeptNode * r = sn_reserve; + septnode * r = sn_reserve; sn_reserve = r->parent; delete r; num_septs--; @@ -331,7 +330,7 @@ class btree_set left_sept = root_sept; } - SeptNode * srch_sept = root_sept; + septnode * srch_sept = root_sept; bool leftmost = true; @@ -384,15 +383,15 @@ class btree_set } } - SeptNode * left_down = nullptr; // left node going down - SeptNode * right_down = nullptr; // right node going down + septnode * left_down = nullptr; // left node going down + septnode * right_down = nullptr; // right node going down leftmost = leftmost && pval < srch_sept->prio[0]; handle_t * hndl_p = &hndl; while (children == N) { // split and push value towards root - SeptNode * new_sibling = alloc_sept(); + septnode * new_sibling = alloc_sept(); new_sibling->parent = srch_sept->parent; // create new sibling to the right: @@ -498,14 +497,14 @@ class btree_set // Pull nodes from a child, all the way down // the tree. Then re-balance back up the tree, // merging nodes if necessary. - SeptNode * sept = hndl.parent; + septnode * sept = hndl.parent; int i; for (i = 0; i < N; i++) { if (sept->hn_p[i] == &hndl) { // Ok, go right, then as far as we can to the left: - SeptNode * lsrch = sept->children[i+1]; - SeptNode * prev = sept; + septnode * lsrch = sept->children[i+1]; + septnode * prev = sept; while (lsrch != nullptr) { prev = lsrch; lsrch = lsrch->children[0]; @@ -547,7 +546,7 @@ class btree_set handle_t *find(const P &pval) { - SeptNode * cursept = root_sept; + septnode * cursept = root_sept; while (cursept != nullptr) { int i; for (i = 0; i < N && cursept->hn_p[i] != nullptr; i++) { diff --git a/src/dasynq/dasynq-daryheap.h b/src/dasynq/dasynq-daryheap.h index 9bb61ca..bf98c7d 100644 --- a/src/dasynq/dasynq-daryheap.h +++ b/src/dasynq/dasynq-daryheap.h @@ -67,6 +67,8 @@ class dary_heap hindex_t heap_index; handle_t(const handle_t &) = delete; + void operator=(const handle_t &) = delete; + handle_t() { } }; diff --git a/src/dasynq/dasynq-kqueue.h b/src/dasynq/dasynq-kqueue.h index 0b1c0e5..9d5f46c 100644 --- a/src/dasynq/dasynq-kqueue.h +++ b/src/dasynq/dasynq-kqueue.h @@ -100,35 +100,29 @@ class kqueue_traits constexpr static bool supports_non_oneshot_fd = false; }; +namespace dprivate { +namespace dkqueue { + #if _POSIX_REALTIME_SIGNALS > 0 + static inline void prepare_signal(int signo) { } static inline void unprep_signal(int signo) { } +// get_siginfo is not required in this case. -inline bool get_siginfo(int signo, siginfo_t *siginfo) -{ - struct timespec timeout; - timeout.tv_sec = 0; - timeout.tv_nsec = 0; - - sigset_t mask; - sigemptyset(&mask); - sigaddset(&mask, signo); - return (sigtimedwait(&mask, siginfo, &timeout) != -1); -} #else // If we have no sigtimedwait implementation, we have to retrieve signal data by establishing a // signal handler. // We need to declare and define a non-static data variable, "siginfo_p", in this header, without -// violating the "one definition rule". The only way to do that is via a template, even though we -// don't otherwise need a template here: +// violating the "one definition rule". The only way to do that (before C++17) is via a template, +// even though we don't otherwise need a template here: template class sig_capture_templ { public: static siginfo_t * siginfo_p; - static void signalHandler(int signo, siginfo_t *siginfo, void *v) + static void signal_handler(int signo, siginfo_t *siginfo, void *v) { *siginfo_p = *siginfo; } @@ -140,7 +134,7 @@ using sig_capture = sig_capture_templ<>; inline void prepare_signal(int signo) { struct sigaction the_action; - the_action.sa_sigaction = sig_capture::signalHandler; + the_action.sa_sigaction = sig_capture::signal_handler; the_action.sa_flags = SA_SIGINFO; sigfillset(&the_action.sa_mask); @@ -164,6 +158,7 @@ inline bool get_siginfo(int signo, siginfo_t *siginfo) } #endif +} } // namespace dprivate :: dkqueue template class kqueue_loop : public Base { @@ -264,7 +259,7 @@ template class kqueue_loop : public Base sigset_t pending_sigs; sigpending(&pending_sigs); while (sigismember(&pending_sigs, signo)) { - get_siginfo(signo, &siginfo.info); + dprivate::dkqueue::get_siginfo(signo, &siginfo.info); if (Base::receive_signal(*this, siginfo, userdata)) { enable_filt = false; break; @@ -487,7 +482,7 @@ template class kqueue_loop : public Base // Note signal should be masked before call. void add_signal_watch_nolock(int signo, void *userdata) { - prepare_signal(signo); + dprivate::dkqueue::prepare_signal(signo); // We need to register the filter with the kqueue early, to avoid a race where we miss // signals: @@ -526,7 +521,7 @@ template class kqueue_loop : public Base void remove_signal_watch_nolock(int signo) noexcept { - unprep_signal(signo); + dprivate::dkqueue::unprep_signal(signo); struct kevent evt; EV_SET(&evt, signo, EVFILT_SIGNAL, EV_DELETE, 0, 0, 0); diff --git a/src/dasynq/dasynq.h b/src/dasynq/dasynq.h index 97beecd..e65bad6 100644 --- a/src/dasynq/dasynq.h +++ b/src/dasynq/dasynq.h @@ -396,7 +396,7 @@ namespace dprivate { // may throw: std::bad_alloc void prepare_watcher(base_watcher *bwatcher) { - event_queue.allocate(bwatcher->heap_handle, bwatcher); + allocate_handle(event_queue, bwatcher->heap_handle, bwatcher); } void queue_watcher(base_watcher *bwatcher) noexcept @@ -509,7 +509,7 @@ namespace dprivate { } auto & rhndl = event_queue.get_root(); - base_watcher *r = event_queue.node_data(rhndl); + base_watcher *r = dprivate::get_watcher(event_queue, rhndl); event_queue.pull_root(); return r; } @@ -1326,8 +1326,9 @@ class event_loop // (Above variables are initialised only to silence compiler warnings). if (pqueue->watchType == watch_type_t::SECONDARYFD) { - // construct a pointer to the main watcher (using char* arithmetic): - char * rp = (char *)pqueue; + // construct a pointer to the main watcher, using integer arithmetic to avoid undefined + // pointer arithmetic: + uintptr_t rp = (uintptr_t)pqueue; // Here we take the offset of a member from a non-standard-layout class, which is // specified to have undefined result by the C++ language standard, but which -- 2.25.1