summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2015-11-10 18:26:37 +0100
committerMatthias Schiffer <mschiffer@universe-factory.net>2015-11-10 18:26:37 +0100
commit9bd967affaafb10e8262253bc746dac234f39443 (patch)
tree248c56773a1b71ee82f95545b23c86724487d2ef /src
parent181deb932074de613e33f955978af579e52e1feb (diff)
downloadfastd-9bd967affaafb10e8262253bc746dac234f39443.tar
fastd-9bd967affaafb10e8262253bc746dac234f39443.zip
Use heap-based priority queue to schedule handshakes instead of a linked list
Diffstat (limited to 'src')
-rw-r--r--src/fastd.h3
-rw-r--r--src/peer.c21
-rw-r--r--src/peer.h9
-rw-r--r--src/poll.c6
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