From 9bd967affaafb10e8262253bc746dac234f39443 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Tue, 10 Nov 2015 18:26:37 +0100 Subject: Use heap-based priority queue to schedule handshakes instead of a linked list --- src/fastd.h | 3 +-- src/peer.c | 21 ++++++--------------- src/peer.h | 9 ++++----- src/poll.c | 6 ++---- 4 files changed, 13 insertions(+), 26 deletions(-) diff --git a/src/fastd.h b/src/fastd.h index 88bd9a2..d15033c 100644 --- a/src/fastd.h +++ b/src/fastd.h @@ -36,7 +36,6 @@ #pragma once -#include "dlist.h" #include "buffer.h" #include "log.h" #include "poll.h" @@ -313,7 +312,7 @@ struct fastd_context { size_t peer_addr_ht_used; /**< The current number of entries in the peer address hashtable */ VECTOR(fastd_peer_t *) *peer_addr_ht; /**< An array of hash buckets for the peer hash table */ - fastd_dlist_head_t handshake_queue; /**< A doubly linked list of the peers currently queued for handshakes (ordered by the time of the next handshake) */ + fastd_pqueue_t *handshake_queue; /**< A priority queue of the peers currently queued for handshakes (ordered by the time of the next handshake) */ fastd_timeout_t next_maintenance; /**< The time of the next maintenance call */ VECTOR(pid_t) async_pids; /**< PIDs of asynchronously executed commands which still have to be reaped */ diff --git a/src/peer.c b/src/peer.c index 67ce50d..87df22d 100644 --- a/src/peer.c +++ b/src/peer.c @@ -265,17 +265,8 @@ void fastd_peer_reset_socket(fastd_peer_t *peer) { void fastd_peer_schedule_handshake(fastd_peer_t *peer, int delay) { fastd_peer_unschedule_handshake(peer); - peer->next_handshake = ctx.now + delay; - - fastd_dlist_head_t *list; - for (list = &ctx.handshake_queue; list->next; list = list->next) { - fastd_peer_t *entry = container_of(list->next, fastd_peer_t, handshake_entry); - - if (entry->next_handshake > peer->next_handshake) - break; - } - - fastd_dlist_insert(list, &peer->handshake_entry); + peer->handshake_entry.value = ctx.now + delay; + fastd_pqueue_insert(&ctx.handshake_queue, &peer->handshake_entry); } /** Checks if the peer group \e group1 lies in \e group2 */ @@ -829,13 +820,13 @@ static void send_handshake(fastd_peer_t *peer, fastd_remote_t *next_remote) { /** Sends a handshake to one peer, if a scheduled handshake is due */ void fastd_peer_handle_handshake_queue(void) { - if (!ctx.handshake_queue.next) + if (!ctx.handshake_queue) return; - - fastd_peer_t *peer = container_of(ctx.handshake_queue.next, fastd_peer_t, handshake_entry); - if (!fastd_timed_out(peer->next_handshake)) + if (!fastd_timed_out(ctx.handshake_queue->value)) return; + fastd_peer_t *peer = container_of(ctx.handshake_queue, fastd_peer_t, handshake_entry); + fastd_peer_schedule_handshake_default(peer); if (!fastd_peer_may_connect(peer)) { diff --git a/src/peer.h b/src/peer.h index 298adf4..5f5da54 100644 --- a/src/peer.h +++ b/src/peer.h @@ -33,6 +33,7 @@ #pragma once #include "fastd.h" +#include "pqueue.h" /** The state of a peer */ @@ -90,7 +91,7 @@ struct fastd_peer { fastd_peer_state_t state; /**< The peer's state */ - fastd_timeout_t next_handshake; /**< The time of the next handshake */ + fastd_pqueue_t handshake_entry; /**< Entry in the handshake queue */ fastd_timeout_t last_handshake_timeout; /**< No handshakes are sent to the peer until this timeout has occured to avoid flooding the peer */ fastd_timeout_t last_handshake_response_timeout; /**< All handshakes from last_handshake_address will be ignored until this timeout has occured */ fastd_timeout_t establish_handshake_timeout; /**< A timeout during which all handshakes for this peer will be ignored after a new connection has been established */ @@ -101,8 +102,6 @@ struct fastd_peer { fastd_stats_t stats; /**< Traffic statistics */ - fastd_dlist_head_t handshake_entry; /**< Entry in the handshake queue */ - #ifdef WITH_DYNAMIC_PEERS fastd_timeout_t verify_timeout; /**< Specifies the minimum time after which on-verify may be run again */ fastd_timeout_t verify_valid_timeout; /**< Specifies how long a peer stays valid after a successful on-verify run */ @@ -176,7 +175,7 @@ static inline void fastd_peer_schedule_handshake_default(fastd_peer_t *peer) { /** Cancels a scheduled handshake */ static inline void fastd_peer_unschedule_handshake(fastd_peer_t *peer) { - fastd_dlist_remove(&peer->handshake_entry); + fastd_pqueue_remove(&peer->handshake_entry); } #ifdef WITH_DYNAMIC_PEERS @@ -193,7 +192,7 @@ static inline void fastd_peer_set_verified(fastd_peer_t *peer, bool ok) { /** Checks if there's a handshake queued for the peer */ static inline bool fastd_peer_handshake_scheduled(fastd_peer_t *peer) { - return fastd_dlist_linked(&peer->handshake_entry); + return fastd_pqueue_linked(&peer->handshake_entry); } /** Checks if a peer is floating (is has at least one floating remote or no remotes at all) */ diff --git a/src/poll.c b/src/poll.c index 2ae6867..0c4dfa9 100644 --- a/src/poll.c +++ b/src/poll.c @@ -53,12 +53,10 @@ /** Returns the time to the next handshake or -1 */ static inline int handshake_timeout(void) { - if (!ctx.handshake_queue.next) + if (!ctx.handshake_queue) return -1; - fastd_peer_t *peer = container_of(ctx.handshake_queue.next, fastd_peer_t, handshake_entry); - - int diff_msec = peer->next_handshake - ctx.now; + int diff_msec = ctx.handshake_queue->value - ctx.now; if (diff_msec < 0) return 0; else -- cgit v1.2.3