From 6798a76ffa1b4de4ec0ea07286c3510d86c0e3b6 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sat, 19 Apr 2014 20:00:36 +0200 Subject: Store peers as vectors of pointers instead of linked lists --- src/async.c | 6 +- src/fastd.c | 122 ++++++++++++++++--------------- src/fastd.h | 6 +- src/peer.c | 54 +++++++------- src/peer.h | 2 - src/protocols/ec25519_fhmqvc/handshake.c | 16 ++-- src/receive.c | 5 +- src/send.c | 7 +- src/vector.h | 3 +- 9 files changed, 115 insertions(+), 106 deletions(-) diff --git a/src/async.c b/src/async.c index 28895b3..0c37842 100644 --- a/src/async.c +++ b/src/async.c @@ -45,8 +45,10 @@ static void handle_resolve_return(fastd_context_t *ctx) { exit_errno(ctx, "handle_resolve_return: read"); } - fastd_peer_t *peer; - for (peer = ctx->peers; peer; peer = peer->next) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + if (!peer->config) continue; diff --git a/src/fastd.c b/src/fastd.c index 7459d6d..0f8194b 100644 --- a/src/fastd.c +++ b/src/fastd.c @@ -336,30 +336,31 @@ static void init_peers(fastd_context_t *ctx) { peer_conf->enabled = enable; } - fastd_peer_t *peer, *next; - for (peer = ctx->peers; peer; peer = next) { - next = peer->next; + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers);) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); if (peer->config) { if (!peer->config->enabled) { pr_info(ctx, "previously enabled peer %P disabled, deleting.", peer); fastd_peer_delete(ctx, peer); + continue; } } else { - if (!ctx->conf->protocol->peer_check_temporary(ctx, peer)) + if (!ctx->conf->protocol->peer_check_temporary(ctx, peer)) { fastd_peer_delete(ctx, peer); + continue; + } } + + i++; } } static void delete_peers(fastd_context_t *ctx) { - fastd_peer_t *peer, *next; - for (peer = ctx->peers; peer; peer = next) { - next = peer->next; - - fastd_peer_delete(ctx, peer); - } + while (VECTOR_LEN(ctx->peers)) + fastd_peer_delete(ctx, VECTOR_INDEX(ctx->peers, VECTOR_LEN(ctx->peers)-1)); } static void dump_state(fastd_context_t *ctx) { @@ -369,8 +370,10 @@ static void dump_state(fastd_context_t *ctx) { pr_info(ctx, "dumping peers:"); - fastd_peer_t *peer; - for (peer = ctx->peers; peer; peer = peer->next) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers);) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + if (!fastd_peer_is_established(peer)) { pr_info(ctx, "peer %P not connected, address: %I", peer, &peer->address); continue; @@ -522,34 +525,30 @@ static inline int handshake_timeout(fastd_context_t *ctx) { } static void handle_input(fastd_context_t *ctx) { - const size_t n_fds = 2 + ctx->n_socks + ctx->n_peers; + const size_t n_fds = 2 + ctx->n_socks + VECTOR_LEN(ctx->peers); struct pollfd fds[n_fds]; fds[0].fd = ctx->tunfd; fds[0].events = POLLIN; fds[1].fd = ctx->async_rfd; fds[1].events = POLLIN; - unsigned i; - for (i = 2; i < ctx->n_socks+2; i++) { - fds[i].fd = ctx->socks[i-2].fd; - fds[i].events = POLLIN; + size_t i; + for (i = 0; i < ctx->n_socks; i++) { + fds[2+i].fd = ctx->socks[i].fd; + fds[2+i].events = POLLIN; } - fastd_peer_t *peer; - for (peer = ctx->peers; peer; peer = peer->next) { + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + if (peer->sock && fastd_peer_is_socket_dynamic(peer)) - fds[i].fd = peer->sock->fd; + fds[2+ctx->n_socks+i].fd = peer->sock->fd; else - fds[i].fd = -1; - - fds[i].events = POLLIN; + fds[2+ctx->n_socks+i].fd = -1; - i++; + fds[i+2+ctx->n_socks].events = POLLIN; } - if (i != n_fds) - exit_bug(ctx, "fd count mismatch"); - int maintenance_timeout = timespec_diff(&ctx->next_maintenance, &ctx->now); if (maintenance_timeout < 0) @@ -574,66 +573,68 @@ static void handle_input(fastd_context_t *ctx) { if (fds[1].revents & POLLIN) fastd_async_handle(ctx); - for (i = 2; i < ctx->n_socks+2; i++) { - if (fds[i].revents & (POLLERR|POLLHUP|POLLNVAL)) - fastd_socket_error(ctx, &ctx->socks[i-2]); - else if (fds[i].revents & POLLIN) - fastd_receive(ctx, &ctx->socks[i-2]); + for (i = 0; i < ctx->n_socks; i++) { + if (fds[2+i].revents & (POLLERR|POLLHUP|POLLNVAL)) + fastd_socket_error(ctx, &ctx->socks[i]); + else if (fds[2+i].revents & POLLIN) + fastd_receive(ctx, &ctx->socks[i]); } - for (peer = ctx->peers; peer; peer = peer->next) { - if (fds[i].revents & (POLLERR|POLLHUP|POLLNVAL)) + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + + if (fds[2+ctx->n_socks+i].revents & (POLLERR|POLLHUP|POLLNVAL)) fastd_peer_reset_socket(ctx, peer); - else if (fds[i].revents & POLLIN) + else if (fds[2+ctx->n_socks+i].revents & POLLIN) fastd_receive(ctx, peer->sock); - - i++; } +} - if (i != n_fds) - exit_bug(ctx, "fd count mismatch"); +static void enable_temporaries(fastd_context_t *ctx) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers_temp); i++) + fastd_peer_enable_temporary(ctx, VECTOR_INDEX(ctx->peers_temp, i)); + + VECTOR_RESIZE(ctx->peers_temp, 0); } -static void maintain_peer(fastd_context_t *ctx, fastd_peer_t *peer) { +static bool maintain_peer(fastd_context_t *ctx, fastd_peer_t *peer) { if (fastd_peer_is_temporary(peer) || fastd_peer_is_established(peer)) { /* check for peer timeout */ if (fastd_timed_out(ctx, &peer->timeout)) { - if (fastd_peer_is_temporary(peer)) + if (fastd_peer_is_temporary(peer)) { fastd_peer_delete(ctx, peer); - else + return false; + } + else { fastd_peer_reset(ctx, peer); - - return; + return true; + } } /* check for keepalive timeout */ if (!fastd_peer_is_established(peer)) - return; + return true; if (!fastd_timed_out(ctx, &peer->keepalive_timeout)) - return; + return true; pr_debug2(ctx, "sending keepalive to %P", peer); ctx->conf->protocol->send(ctx, peer, fastd_buffer_alloc(ctx, 0, ctx->conf->min_encrypt_head_space, ctx->conf->min_encrypt_tail_space)); } -} - -static void enable_temporaries(fastd_context_t *ctx) { - while (ctx->peers_temp) { - fastd_peer_t *peer = ctx->peers_temp; - ctx->peers_temp = ctx->peers_temp->next; - fastd_peer_enable_temporary(ctx, peer); - } + return true; } static void maintenance(fastd_context_t *ctx) { fastd_socket_handle_binds(ctx); - fastd_peer_t *peer, *next; - for (peer = ctx->peers; peer; peer = next) { - next = peer->next; - maintain_peer(ctx, peer); + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers);) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + + if (maintain_peer(ctx, peer)) + i++; } fastd_peer_eth_addr_cleanup(ctx); @@ -967,6 +968,9 @@ int main(int argc, char *argv[]) { fastd_config_load_peer_dirs(&ctx, &conf); VECTOR_ALLOC(ctx.eth_addrs, 0); + VECTOR_ALLOC(ctx.peers, 0); + VECTOR_ALLOC(ctx.peers_temp, 0); + init_peers(&ctx); while (!terminate) { @@ -1013,6 +1017,8 @@ int main(int argc, char *argv[]) { on_post_down(&ctx); + VECTOR_FREE(ctx.peers_temp); + VECTOR_FREE(ctx.peers); VECTOR_FREE(ctx.eth_addrs); free(ctx.protocol_state); diff --git a/src/fastd.h b/src/fastd.h index b7f3532..9cd6b2a 100644 --- a/src/fastd.h +++ b/src/fastd.h @@ -237,10 +237,10 @@ struct fastd_context { struct timespec now; - unsigned n_peers; fastd_peer_group_t *peer_group; - fastd_peer_t *peers; - fastd_peer_t *peers_temp; + + VECTOR(fastd_peer_t*) peers; + VECTOR(fastd_peer_t*) peers_temp; fastd_dlist_head_t handshake_queue; struct timespec next_maintenance; diff --git a/src/peer.c b/src/peer.c index 1de0911..67aa622 100644 --- a/src/peer.c +++ b/src/peer.c @@ -234,18 +234,18 @@ static void setup_peer(fastd_context_t *ctx, fastd_peer_t *peer) { static void delete_peer(fastd_context_t *ctx, fastd_peer_t *peer) { pr_debug(ctx, "deleting peer %P", peer); - fastd_peer_t **cur_peer; - for (cur_peer = &ctx->peers; *cur_peer; cur_peer = &(*cur_peer)->next) { - if ((*cur_peer) == peer) { - *cur_peer = peer->next; - ctx->n_peers--; + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + if (VECTOR_INDEX(ctx->peers, i) == peer) { + VECTOR_DELETE(ctx->peers, i); break; } } - if (!*cur_peer) { - for (cur_peer = &ctx->peers_temp; *cur_peer; cur_peer = &(*cur_peer)->next) { - if ((*cur_peer) == peer) { - *cur_peer = peer->next; + + if (i == VECTOR_LEN(ctx->peers)) { + for (i = 0; i < VECTOR_LEN(ctx->peers_temp); i++) { + if (VECTOR_INDEX(ctx->peers_temp, i) == peer) { + VECTOR_DELETE(ctx->peers_temp, i); break; } } @@ -300,12 +300,14 @@ void fastd_peer_config_delete(fastd_context_t *ctx UNUSED, fastd_config_t *conf) } void fastd_peer_config_purge(fastd_context_t *ctx, fastd_peer_config_t *conf) { - fastd_peer_t *peer, *next; - for (peer = ctx->peers; peer; peer = next) { - next = peer->next; + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); - if (peer->config == conf) + if (peer->config == conf) { fastd_peer_delete(ctx, peer); + break; + } } fastd_peer_config_free(conf); @@ -410,8 +412,10 @@ bool fastd_peer_claim_address(fastd_context_t *ctx, fastd_peer_t *new_peer, fast fastd_peer_reset(ctx, new_peer); } else { - fastd_peer_t *peer; - for (peer = ctx->peers; peer; peer = peer->next) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + if (peer == new_peer) continue; @@ -488,8 +492,10 @@ void fastd_peer_delete(fastd_context_t *ctx, fastd_peer_t *peer) { static inline unsigned count_established_group_peers(fastd_context_t *ctx, fastd_peer_group_t *group) { unsigned ret = 0; - fastd_peer_t *peer; - for (peer = ctx->peers; peer; peer = peer->next) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); + if (fastd_peer_is_established(peer) && is_peer_in_group(peer, group)) ret++; } @@ -517,9 +523,6 @@ bool fastd_peer_may_connect(fastd_context_t *ctx, fastd_peer_t *peer) { fastd_peer_t* fastd_peer_add(fastd_context_t *ctx, fastd_peer_config_t *peer_conf) { fastd_peer_t *peer = calloc(1, sizeof(fastd_peer_t)); - peer->next = ctx->peers; - ctx->peers = peer; - peer->config = peer_conf; peer->group = find_peer_group(ctx->peer_group, peer_conf->group); peer->protocol_config = peer_conf->protocol_config; @@ -546,7 +549,7 @@ fastd_peer_t* fastd_peer_add(fastd_context_t *ctx, fastd_peer_config_t *peer_con setup_peer(ctx, peer); - ctx->n_peers++; + VECTOR_ADD(ctx->peers, peer); return peer; } @@ -557,9 +560,6 @@ fastd_peer_t* fastd_peer_add_temporary(fastd_context_t *ctx) { fastd_peer_t *peer = calloc(1, sizeof(fastd_peer_t)); - peer->next = ctx->peers_temp; - ctx->peers_temp = peer; - peer->group = ctx->peer_group; fastd_peer_seen(ctx, peer); @@ -567,6 +567,8 @@ fastd_peer_t* fastd_peer_add_temporary(fastd_context_t *ctx) { setup_peer(ctx, peer); + VECTOR_ADD(ctx->peers_temp, peer); + return peer; } @@ -596,9 +598,7 @@ void fastd_peer_enable_temporary(fastd_context_t *ctx, fastd_peer_t *peer) { if (peer->config) exit_bug(ctx, "trying to re-enable non-temporary peer"); - peer->next = ctx->peers; - ctx->peers = peer; - ctx->n_peers++; + VECTOR_ADD(ctx->peers, peer); } void fastd_peer_set_established(fastd_context_t *ctx, fastd_peer_t *peer) { diff --git a/src/peer.h b/src/peer.h index 7e3bf08..2d3c2f3 100644 --- a/src/peer.h +++ b/src/peer.h @@ -30,8 +30,6 @@ struct fastd_peer { - fastd_peer_t *next; - const fastd_peer_config_t *config; fastd_peer_group_t *group; diff --git a/src/protocols/ec25519_fhmqvc/handshake.c b/src/protocols/ec25519_fhmqvc/handshake.c index 9339475..ef601df 100644 --- a/src/protocols/ec25519_fhmqvc/handshake.c +++ b/src/protocols/ec25519_fhmqvc/handshake.c @@ -391,12 +391,15 @@ static void handle_finish_handshake(fastd_context_t *ctx, fastd_socket_t *sock, clear_shared_handshake_key(ctx, peer); } -static fastd_peer_t* find_sender_key(fastd_context_t *ctx, const fastd_peer_address_t *address, const unsigned char key[32], fastd_peer_t *peers) { +static fastd_peer_t* find_sender_key(fastd_context_t *ctx, const fastd_peer_address_t *address, const unsigned char key[32]) { errno = 0; - fastd_peer_t *ret = NULL, *peer; + fastd_peer_t *ret = NULL; + size_t i; + + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *peer = VECTOR_INDEX(ctx->peers, i); - for (peer = peers; peer; peer = peer->next) { if (memcmp(&peer->protocol_config->public_key, key, PUBLICKEYBYTES) == 0) { if (!fastd_peer_matches_address(ctx, peer, address)) { errno = EPERM; @@ -435,12 +438,7 @@ static fastd_peer_t* match_sender_key(fastd_context_t *ctx, const fastd_socket_t } } - peer = find_sender_key(ctx, address, key, ctx->peers); - - if (!peer && errno == ENOENT) - peer = find_sender_key(ctx, address, key, ctx->peers_temp); - - return peer; + return find_sender_key(ctx, address, key); } static size_t key_count(fastd_context_t *ctx, const unsigned char key[32]) { diff --git a/src/receive.c b/src/receive.c index f53b263..5bbab23 100644 --- a/src/receive.c +++ b/src/receive.c @@ -163,7 +163,10 @@ static inline void handle_socket_receive(fastd_context_t *ctx, fastd_socket_t *s peer = sock->peer; } else { - for (peer = ctx->peers; peer; peer = peer->next) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + peer = VECTOR_INDEX(ctx->peers, i); + if (fastd_peer_address_equal(&peer->address, remote_addr)) break; } diff --git a/src/send.c b/src/send.c index 04fd846..3e18483 100644 --- a/src/send.c +++ b/src/send.c @@ -177,13 +177,14 @@ void fastd_send_handshake(fastd_context_t *ctx, const fastd_socket_t *sock, cons } void fastd_send_all(fastd_context_t *ctx, fastd_peer_t *source_peer, fastd_buffer_t buffer) { - fastd_peer_t *dest_peer; - for (dest_peer = ctx->peers; dest_peer; dest_peer = dest_peer->next) { + size_t i; + for (i = 0; i < VECTOR_LEN(ctx->peers); i++) { + fastd_peer_t *dest_peer = VECTOR_INDEX(ctx->peers, i); if (dest_peer == source_peer || !fastd_peer_is_established(dest_peer)) continue; /* optimization, primarily for TUN mode: don't duplicate the buffer for the last (or only) peer */ - if (!dest_peer->next) { + if (i == VECTOR_LEN(ctx->peers)-1) { ctx->conf->protocol->send(ctx, dest_peer, buffer); return; } diff --git a/src/vector.h b/src/vector.h index 0d9d9be..701b64e 100644 --- a/src/vector.h +++ b/src/vector.h @@ -73,7 +73,8 @@ void _fastd_vector_delete(fastd_vector_desc_t *desc, void **data, size_t pos, si #define VECTOR_ADD(v, elem) ({ \ __typeof__(v) *_v = &(v); \ - VECTOR_INSERT(*_v, (elem), _v->desc.length); \ + __typeof__(*_v->data) _e = (elem); \ + _fastd_vector_insert(&_v->desc, (void**)&_v->data, &_e, _v->desc.length, sizeof(_e)); \ }) #define VECTOR_DELETE(v, pos) ({ \ -- cgit v1.2.3