From 7601e582848ef68c565f3d88ab1265e4c86d5ac0 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sat, 6 Oct 2012 04:13:01 +0200 Subject: Fix feasibility distance maintenance --- ffd/announce.c | 19 +++------------ ffd/ffd.h | 75 ++++++++++++++++++++++++++++++++++++++-------------------- ffd/send.c | 9 ++++--- 3 files changed, 56 insertions(+), 47 deletions(-) diff --git a/ffd/announce.c b/ffd/announce.c index e1f7ae0..8911feb 100644 --- a/ffd/announce.c +++ b/ffd/announce.c @@ -28,20 +28,6 @@ #include "neigh.h" -bool ffd_is_feasible(const ffd_announce_t *announce, ffd_metric_seqno_t ms) { - if (FFD_IS_INFINITY(ms) || FFD_IS_INFINITY(announce->feasibility_distance)) - return true; - - int16_t seqno_diff = ms.seqno - announce->feasibility_distance.seqno; - - if (seqno_diff < 0) - return true; - if (seqno_diff == 0 && ms.metric < announce->feasibility_distance.metric) - return true; - - return false; -} - static ffd_nexthop_t* select_nexthop(const ffd_announce_t *announce) { uint16_t ret_metric = 0xffff; ffd_nexthop_t *ret = NULL; @@ -62,7 +48,7 @@ static ffd_nexthop_t* select_nexthop(const ffd_announce_t *announce) { return ret; } -ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce) { +ffd_metric_seqno_t get_metric(const ffd_announce_t *announce) { if (announce->selected) { uint32_t metric = announce->selected->metric_seqno.metric + ffd_neigh_get_cost(announce->selected->neigh); @@ -75,6 +61,7 @@ ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce) { static inline void update_selected(ffd_announce_t *announce) { announce->selected = select_nexthop(announce); + announce->metric = get_metric(announce); } void ffd_announce_update(ffd_announce_t *announce, ffd_nexthop_t *nexthop, ffd_metric_seqno_t ms, uint16_t interval) { @@ -90,7 +77,7 @@ void ffd_announce_update(ffd_announce_t *announce, ffd_nexthop_t *nexthop, ffd_m ffd_announce_t* ffd_announce_new(void) { ffd_announce_t *a = calloc(1, sizeof(ffd_announce_t)); - a->feasibility_distance.metric = 0xffff; + a->metric.metric = a->feasibility_distance.metric = 0xffff; a->next = announce_list; announce_list = a; diff --git a/ffd/ffd.h b/ffd/ffd.h index 0b1c296..f498f4e 100644 --- a/ffd/ffd.h +++ b/ffd/ffd.h @@ -50,35 +50,11 @@ typedef struct __attribute__((packed)) _ffd_node_id_t { uint8_t id[8]; } ffd_node_id_t; - -#define FFD_NODE_ID_UNSPEC ((ffd_node_id_t){}) - - -static inline bool ffd_is_node_id_unspec(const ffd_node_id_t *node) { - const uint8_t *id = node->id; - - if (id[0]||id[1]||id[2]||id[3]||id[4]||id[5]||id[6]||id[7]) - return false; - else - return true; -} - -static inline bool ffd_are_node_ids_equal(const ffd_node_id_t *id1, const ffd_node_id_t *id2) { - const uint8_t *a = id1->id; - const uint8_t *b = id2->id; - - return (a[0]==b[0] && a[1]==b[1] && a[2]==b[2] && a[3]==b[3] - && a[4]==b[4] && a[5]==b[5] && a[6]==b[6] && a[7]==b[7]); -} - - typedef struct _ffd_metric_seqno_t { uint16_t metric; uint16_t seqno; } ffd_metric_seqno_t; -#define FFD_IS_INFINITY(m) ((m).metric == 0xffff) - typedef struct _ffd_nexthop_t { struct _ffd_nexthop_t *next; @@ -96,6 +72,7 @@ typedef struct _ffd_announce_t { uint16_t type; uint16_t key; + ffd_metric_seqno_t metric; ffd_metric_seqno_t feasibility_distance; ffd_nexthop_t *selected; @@ -147,8 +124,54 @@ extern int sockfd; extern struct timespec now; -bool ffd_is_feasible(const ffd_announce_t *announce, ffd_metric_seqno_t ms); -ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce); +#define FFD_NODE_ID_UNSPEC ((ffd_node_id_t){}) + + +static inline bool ffd_is_node_id_unspec(const ffd_node_id_t *node) { + const uint8_t *id = node->id; + + if (id[0]||id[1]||id[2]||id[3]||id[4]||id[5]||id[6]||id[7]) + return false; + else + return true; +} + +static inline bool ffd_are_node_ids_equal(const ffd_node_id_t *id1, const ffd_node_id_t *id2) { + const uint8_t *a = id1->id; + const uint8_t *b = id2->id; + + return (a[0]==b[0] && a[1]==b[1] && a[2]==b[2] && a[3]==b[3] + && a[4]==b[4] && a[5]==b[5] && a[6]==b[6] && a[7]==b[7]); +} + +#define FFD_IS_INFINITY(m) ((m).metric == 0xffff) + +/* returns true if ms1 is better than ms2 */ +static inline bool ffd_is_metric_better(ffd_metric_seqno_t ms1, ffd_metric_seqno_t ms2) { + if (FFD_IS_INFINITY(ms1)) + return false; + + if (FFD_IS_INFINITY(ms2)) + return true; + + int16_t seqno_diff = ms2.seqno - ms1.seqno; + + if (seqno_diff < 0) + return true; + if (seqno_diff == 0 && ms1.metric < ms2.metric) + return true; + + return false; +} + +static inline bool ffd_is_feasible(const ffd_announce_t *announce, ffd_metric_seqno_t ms) { + if (FFD_IS_INFINITY(ms)) + return true; + + return ffd_is_metric_better(ms, announce->feasibility_distance); +} + + void ffd_announce_update(ffd_announce_t *announce, ffd_nexthop_t *nexthop, ffd_metric_seqno_t ms, uint16_t interval); ffd_announce_t* ffd_announce_new(void); diff --git a/ffd/send.c b/ffd/send.c index 142d07a..ac5b250 100644 --- a/ffd/send.c +++ b/ffd/send.c @@ -164,13 +164,11 @@ static bool add_update(ffd_packet_t *packet, size_t max_len, ffd_node_id_t *node return false; } - ffd_metric_seqno_t metric = ffd_announce_get_metric(announce); - update->flags = 0; update->reserved = 0; update->interval = htons(FFD_UPDATE_INTERVAL); - update->seqno = htons(metric.seqno); - update->metric = htons(metric.metric); + update->seqno = htons(announce->metric.seqno); + update->metric = htons(announce->metric.metric); update->type = htons(announce->type); update->key = htons(announce->key); @@ -182,7 +180,8 @@ static bool add_update(ffd_packet_t *packet, size_t max_len, ffd_node_id_t *node } } - announce->feasibility_distance = metric; + if (ffd_is_metric_better(announce->metric, announce->feasibility_distance)) + announce->feasibility_distance = announce->metric; return true; } -- cgit v1.2.3