From 8e810f5fd809bad3047ea9224dd058edd20a64ac Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Mon, 8 Oct 2012 07:32:38 +0200 Subject: Keep track of forwarded seqno requests --- ffd/announce.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ffd/ffd.c | 44 ++++++++----------------- ffd/ffd.h | 16 +++++++++ 3 files changed, 132 insertions(+), 30 deletions(-) diff --git a/ffd/announce.c b/ffd/announce.c index 26ced28..00bd78c 100644 --- a/ffd/announce.c +++ b/ffd/announce.c @@ -110,6 +110,26 @@ ffd_metric_seqno_t get_metric(const ffd_announce_t *announce) { return (ffd_metric_seqno_t){0xffff, 0}; } +static inline void seqno_update(ffd_announce_t *announce) { + ffd_seqno_req_t **cur, **next; + for (cur = &announce->seqno_req_list; *cur; cur = next) { + ffd_seqno_req_t *req = *cur; + next = &req->next; + + int16_t diff = announce->selected->metric_seqno.seqno - req->seqno; + + if (diff >= 0) { + *cur = *next; + next = cur; + + fprintf(stderr, "debug: update matches seqno request, forwarding\n"); + ffd_send_update(NULL, req->neigh, announce, false); + ffd_neigh_unref(req->neigh); + free(req); + } + } +} + void ffd_announce_update(ffd_announce_t *announce) { maintain_nexthops(announce); @@ -127,6 +147,9 @@ void ffd_announce_update(ffd_announce_t *announce) { fprintf(stderr, "info: announce metric has changed significantly, sending updates\n"); ffd_send_update(NULL, NULL, announce, false); } + + if (announce->selected) + seqno_update(announce); } void ffd_announce_update_nexthop(ffd_announce_t *announce, ffd_nexthop_t *nexthop, ffd_metric_seqno_t ms, uint16_t interval) { @@ -175,3 +198,82 @@ ffd_announce_t* ffd_announce_get(const ffd_node_id_t *node, uint16_t type, uint1 return announce; } + +ffd_nexthop_t* ffd_announce_nexthop_find(const ffd_announce_t *announce, ffd_neigh_t *neigh) { + ffd_nexthop_t *nexthop; + for (nexthop = announce->nexthop_list; nexthop; nexthop = nexthop->next) { + if (nexthop->neigh == neigh) + return nexthop; + } + + return NULL; +} + +ffd_nexthop_t* ffd_announce_nexthop_new(ffd_announce_t *announce, ffd_neigh_t *neigh) { + ffd_nexthop_t *nexthop = calloc(1, sizeof(ffd_nexthop_t)); + nexthop->neigh = neigh; + + nexthop->next = announce->nexthop_list; + announce->nexthop_list = nexthop; + + ffd_neigh_ref(neigh); + + return nexthop; +} + +static inline bool find_seqno_request(ffd_seqno_req_t **reqp, ffd_announce_t *announce, ffd_neigh_t *neigh, uint16_t seqno) { + ffd_seqno_req_t *req; + bool ret = true; + + *reqp = NULL; + + for (req = announce->seqno_req_list; req; req = req->next) { + if (req->neigh == neigh) + *reqp = req; + + int16_t diff = req->seqno - seqno; + if (timespec_diff(&now, &req->last_req) < FFD_SEQNO_REQUEST_TIMEOUT && diff >= 0) + ret = false; + } + + return ret; +} + +bool ffd_announce_seqno_request(ffd_announce_t *announce, ffd_neigh_t *neigh, uint16_t seqno) { + ffd_seqno_req_t *req; + bool ret = find_seqno_request(&req, announce, neigh, seqno); + + if (!req) { + req = calloc(1, sizeof(ffd_seqno_req_t)); + req->neigh = neigh; + req->seqno = seqno; + req->last_req = now; + + ffd_neigh_ref(neigh); + + req->next = announce->seqno_req_list; + announce->seqno_req_list = req; + } + + int16_t diff = seqno - req->seqno; + if (diff > 0) { + req->seqno = seqno; + req->last_req = now; + } + + if (ret) { + req->last_req = now; + return true; + } + + return false; +} + +void ffd_announce_seqno_request_free_list(ffd_announce_t *announce) { + ffd_seqno_req_t *req, *next; + for (req = announce->seqno_req_list; req; req = next) { + next = req->next; + ffd_neigh_unref(req->neigh); + free(req); + } +} diff --git a/ffd/ffd.c b/ffd/ffd.c index 5e967f3..7af9b29 100644 --- a/ffd/ffd.c +++ b/ffd/ffd.c @@ -284,28 +284,6 @@ static void handle_tlv_node_id(const ffd_tlv_node_id_t *tlv_node_id, size_t len, arg->node_id = tlv_node_id->id; } -static ffd_nexthop_t* find_nexthop(const ffd_announce_t *announce, ffd_neigh_t *neigh) { - ffd_nexthop_t *nexthop; - for (nexthop = announce->nexthop_list; nexthop; nexthop = nexthop->next) { - if (nexthop->neigh == neigh) - return nexthop; - } - - return NULL; -} - -static ffd_nexthop_t* new_nexthop(ffd_announce_t *announce, ffd_neigh_t *neigh) { - ffd_nexthop_t *nexthop = calloc(1, sizeof(ffd_nexthop_t)); - nexthop->neigh = neigh; - - nexthop->next = announce->nexthop_list; - announce->nexthop_list = nexthop; - - ffd_neigh_ref(neigh); - - return nexthop; -} - static void handle_tlv_update(const ffd_tlv_update_t *tlv_update, size_t len, handle_tlv_arg_t *arg) { if (len < sizeof(ffd_tlv_update_t)) { fprintf(stderr, "warn: received short update TLV.\n"); @@ -329,11 +307,11 @@ static void handle_tlv_update(const ffd_tlv_update_t *tlv_update, size_t len, ha bool feasible = ffd_is_feasible(announce, ms); ffd_neigh_t *neigh = get_tlv_neigh(arg); - ffd_nexthop_t *nexthop = find_nexthop(announce, neigh); + ffd_nexthop_t *nexthop = ffd_announce_nexthop_find(announce, neigh); if (!nexthop) { if (feasible && tlv_update->metric != 0xffff /* no need to ntohs */) - nexthop = new_nexthop(announce, neigh); + nexthop = ffd_announce_nexthop_new(announce, neigh); } else { if (!feasible && nexthop == announce->selected) { @@ -397,8 +375,6 @@ static void handle_tlv_seqno_req(const ffd_tlv_seqno_req_t *tlv_req, size_t len, return; } - fprintf(stderr, "debug: received seqno request\n"); - ffd_announce_t *announce = ffd_announce_find(&tlv_req->node, ntohs(tlv_req->type), ntohs(tlv_req->key)); if (!announce) { @@ -416,21 +392,28 @@ static void handle_tlv_seqno_req(const ffd_tlv_seqno_req_t *tlv_req, size_t len, if (announce->selected->neigh == neigh) return; - if ((int16_t)(ntohs(tlv_req->seqno)-announce->selected->metric_seqno.seqno) <= 0) { + uint16_t seqno = ntohs(tlv_req->seqno); + + if ((int16_t)(seqno-announce->selected->metric_seqno.seqno) <= 0) { fprintf(stderr, "debug: received seqno request, seqno already ok\n"); ffd_send_update(NULL, neigh, announce, false); return; } if (!announce->selected->neigh) { - fprintf(stderr, "debug: incrementing seqno\n"); + fprintf(stderr, "debug: received seqno request, incrementing seqno\n"); announce->selected->metric_seqno.seqno++; ffd_send_update(NULL, neigh, announce, false); return; } - fprintf(stderr, "debug: received seqno request, forwarding\n"); - ffd_send_seqno_request(announce->selected->neigh, announce, ntohs(tlv_req->seqno)); + if (ffd_announce_seqno_request(announce, neigh, seqno)) { + fprintf(stderr, "debug: received seqno request, forwarding\n"); + ffd_send_seqno_request(announce->selected->neigh, announce, seqno); + } + else { + fprintf(stderr, "debug: received seqno request, not forwarding again\n"); + } } static void handle_tlv(ffd_tlv_type_t type, const void *data, size_t len, void *arg) { @@ -547,6 +530,7 @@ static void maintenance(void) { if (!announce->nexthop_list) { *cur = *next; next = cur; + ffd_announce_seqno_request_free_list(announce); free(announce); continue; diff --git a/ffd/ffd.h b/ffd/ffd.h index e7c48d7..bf00984 100644 --- a/ffd/ffd.h +++ b/ffd/ffd.h @@ -47,6 +47,8 @@ #define FFD_UPDATE_REQUEST_TIMEOUT(interval) ((interval)*13/4) /* 3.25 intervals */ +#define FFD_SEQNO_REQUEST_TIMEOUT 50 + #define FFD_MAINTENANCE_INTERVAL FFD_HELLO_INTERVAL @@ -73,6 +75,14 @@ typedef struct _ffd_nexthop_t { bool requested_update; } ffd_nexthop_t; +typedef struct _ffd_seqno_req_t { + struct _ffd_seqno_req_t *next; + + struct timespec last_req; + struct _ffd_neigh_t *neigh; + uint16_t seqno; +} ffd_seqno_req_t; + typedef struct _ffd_announce_t { struct _ffd_announce_t *next; @@ -84,6 +94,8 @@ typedef struct _ffd_announce_t { uint16_t last_metric; ffd_metric_seqno_t feasibility_distance; + ffd_seqno_req_t *seqno_req_list; + ffd_nexthop_t *selected; ffd_nexthop_t *nexthop_list; @@ -189,6 +201,10 @@ void ffd_announce_update_nexthop(ffd_announce_t *announce, ffd_nexthop_t *nextho ffd_announce_t* ffd_announce_new(void); ffd_announce_t* ffd_announce_find(const ffd_node_id_t *node, uint16_t type, uint16_t key); ffd_announce_t* ffd_announce_get(const ffd_node_id_t *node, uint16_t type, uint16_t key); +ffd_nexthop_t* ffd_announce_nexthop_find(const ffd_announce_t *announce, ffd_neigh_t *neigh); +ffd_nexthop_t* ffd_announce_nexthop_new(ffd_announce_t *announce, ffd_neigh_t *neigh); +bool ffd_announce_seqno_request(ffd_announce_t *announce, ffd_neigh_t *neigh, uint16_t seqno); +void ffd_announce_seqno_request_free_list(ffd_announce_t *announce); void ffd_send_ack(ffd_neigh_t *neigh, uint16_t nonce); void ffd_send_hellos(void); -- cgit v1.2.3