From bb7392551ed8578171941b81cf3ed2cfc4ad2b1b Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Fri, 5 Oct 2012 04:26:02 +0200 Subject: Lots of update handling --- ffd/announce.c | 42 +++++++++++++---------- ffd/ffd.c | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- ffd/ffd.h | 30 ++++++++++++----- ffd/neigh.c | 5 ++- ffd/send.c | 34 +++++++++++++++---- ffd/tlv_types.h | 6 ++++ 6 files changed, 179 insertions(+), 39 deletions(-) diff --git a/ffd/announce.c b/ffd/announce.c index eade2f1..4e8e07a 100644 --- a/ffd/announce.c +++ b/ffd/announce.c @@ -25,35 +25,37 @@ #include "ffd.h" +#include "neigh.h" -static bool is_feasable(const ffd_announce_t *announce, const ffd_nexthop_t *nexthop) { - if (FFD_IS_INFINITY(announce->feasability_distance)) +bool ffd_is_feasable(const ffd_announce_t *announce, ffd_metric_seqno_t ms) { + if (FFD_IS_INFINITY(ms) || FFD_IS_INFINITY(announce->feasability_distance)) return true; - int16_t seqno_diff = nexthop->metric_seqno.seqno - announce->feasability_distance.seqno; + int16_t seqno_diff = ms.seqno - announce->feasability_distance.seqno; if (seqno_diff < 0) return true; - if (seqno_diff == 0 && nexthop->metric_seqno.metric < announce->feasability_distance.metric) + if (seqno_diff == 0 && ms.metric < announce->feasability_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; ffd_nexthop_t *nexthop; - for (nexthop = announce->nexthop_list->next; nexthop; nexthop = nexthop->next) { - if (is_feasable(announce, nexthop)) + for (nexthop = announce->nexthop_list; nexthop; nexthop = nexthop->next) { + if (!ffd_is_feasable(announce, nexthop->metric_seqno)) continue; - int16_t seqno_diff = nexthop->metric_seqno.seqno - ret->metric_seqno.seqno; + uint32_t metric = nexthop->metric_seqno.metric + ffd_neigh_get_cost(nexthop->neigh); - if (nexthop->metric_seqno.metric < ret->metric_seqno.metric - || (nexthop->metric_seqno.metric == ret->metric_seqno.metric && seqno_diff < 0)) { + if (metric < ret_metric) { ret = nexthop; + ret_metric = metric; } } @@ -61,20 +63,24 @@ static ffd_nexthop_t* select_nexthop(const ffd_announce_t *announce) { } ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce) { - ffd_nexthop_t *nexthop = select_nexthop(announce); + if (announce->selected) { + uint32_t metric = announce->selected->metric_seqno.metric + ffd_neigh_get_cost(announce->selected->neigh); - if (nexthop) - return nexthop->metric_seqno; - else - return (ffd_metric_seqno_t){0xffff, 0}; + if (metric < 0xffff) + return (ffd_metric_seqno_t){metric, announce->selected->metric_seqno.seqno}; + } + + return (ffd_metric_seqno_t){0xffff, 0}; } +void ffd_announce_update_nexthop(ffd_announce_t *announce) { + announce->selected = select_nexthop(announce); +} -ffd_announce_t* ffd_announce_new(size_t len) { - ffd_announce_t *a = calloc(1, sizeof(ffd_announce_t)+len); +ffd_announce_t* ffd_announce_new(void) { + ffd_announce_t *a = calloc(1, sizeof(ffd_announce_t)); - a->len = len; - a->feasability_distance = (ffd_metric_seqno_t){0xffff, 0}; + a->feasability_distance.metric = 0xffff; a->next = announce_list; announce_list = a; diff --git a/ffd/ffd.c b/ffd/ffd.c index 3512906..5f17446 100644 --- a/ffd/ffd.c +++ b/ffd/ffd.c @@ -98,9 +98,8 @@ static bool init_self(void) { announce->node = self; announce->type = 1; announce->key = 1337; - announce->interval = 6000; - announce->nexthop_list = calloc(1, sizeof(ffd_nexthop_t)); + announce->nexthop_list = announce->selected = calloc(1, sizeof(ffd_nexthop_t)); return true; } @@ -273,13 +272,107 @@ 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 void handle_tlv_update(const ffd_tlv_node_id_t *tlv_node_id, size_t len, handle_tlv_arg_t *arg) { +static ffd_announce_t* get_announce(const ffd_node_id_t *node, uint16_t type, uint16_t key) { + ffd_announce_t *announce; + for (announce = announce_list; announce; announce = announce->next) { + if (ffd_are_node_ids_equal(&announce->node, node) + && announce->type == type + && announce->key == key) + return announce; + } + + /* not found */ + announce = ffd_announce_new(); + announce->node = *node; + announce->type = type; + announce->key = key; + + return announce; +} + +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; + + 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"); return; } + if (ffd_is_node_id_unspec(&arg->node_id)) { + fprintf(stderr, "warn: received update TLV without node id TLV.\n"); + return; + } + + if (ffd_are_node_ids_equal(&arg->node_id, &self)) { + fprintf(stderr, "debug: update source is myself.\n"); + return; + } + fprintf(stderr, "debug: update received from %04x%04x.\n", ntohl(*(uint32_t*)arg->node_id.id), ntohl(*(uint32_t*)(arg->node_id.id+4))); + + ffd_announce_t *announce = get_announce(&arg->node_id, ntohs(tlv_update->type), ntohs(tlv_update->key)); + ffd_metric_seqno_t ms = { ntohs(tlv_update->metric), ntohs(tlv_update->seqno) }; + bool feasable = ffd_is_feasable(announce, ms); + + ffd_neigh_t *neigh = get_tlv_neigh(arg); + ffd_nexthop_t *nexthop = find_nexthop(announce, neigh); + + if (!nexthop) { + if (!feasable || tlv_update->metric == 0xffff /* no need to ntohs */) + return; + + nexthop = new_nexthop(announce, neigh); + } + else { + if (!feasable && nexthop == announce->selected) + return; + } + + nexthop->metric_seqno.metric = ntohs(tlv_update->metric); + nexthop->metric_seqno.seqno = ntohs(tlv_update->seqno); + nexthop->interval = ntohs(tlv_update->interval); + + fprintf(stderr, "debug: the update was accepted.\n"); + + if (nexthop->metric_seqno.metric == 0xffff) + return; + + /* only update the timestamp for finite metrics */ + nexthop->last_update = now; + + if ((tlv_update->flags & FFD_UPDATE_WITH_DATA) && !announce->data) { + if (len > sizeof(ffd_tlv_update_t)) { + announce->len = len - sizeof(ffd_tlv_update_t); + announce->data = malloc(announce->len); + memcpy(announce->data, tlv_update->data, announce->len); + } + else { + announce->len = 0xff; + + /* request data */ + ffd_send_announce_request(arg->iface, neigh, announce->node, announce->type, announce->key, true); + } + } + + ffd_announce_update_nexthop(announce); } static void handle_tlv_announce_req(const ffd_tlv_announce_req_t *tlv_req, size_t len, handle_tlv_arg_t *arg) { @@ -294,7 +387,7 @@ static void handle_tlv_announce_req(const ffd_tlv_announce_req_t *tlv_req, size_ announce = NULL; } - ffd_send_update(arg->iface, get_tlv_neigh(arg), announce); + ffd_send_update(arg->iface, get_tlv_neigh(arg), announce, tlv_req->flags & FFD_UPDATE_WITH_DATA); } static void handle_tlv(ffd_tlv_type_t type, const void *data, size_t len, void *arg) { diff --git a/ffd/ffd.h b/ffd/ffd.h index cf9d59c..e0f1954 100644 --- a/ffd/ffd.h +++ b/ffd/ffd.h @@ -40,6 +40,11 @@ #define FFD_HELLO_INTERVAL 400 #define FFD_IHU_INTERVAL (3*FFD_HELLO_INTERVAL) +#define FFD_UPDATE_INTERVAL 400 + + +#define FFD_UPDATE_WITH_DATA 0x01 + typedef struct __attribute__((packed)) _ffd_node_id_t { uint8_t id[8]; @@ -77,9 +82,11 @@ typedef struct _ffd_metric_seqno_t { typedef struct _ffd_nexthop_t { struct _ffd_nexthop_t *next; - struct timespec last_update; - eth_addr_t addr; + struct _ffd_neigh_t *neigh; ffd_metric_seqno_t metric_seqno; + + struct timespec last_update; + uint16_t interval; } ffd_nexthop_t; typedef struct _ffd_announce_t { @@ -88,21 +95,22 @@ typedef struct _ffd_announce_t { ffd_node_id_t node; uint16_t type; uint16_t key; - uint16_t interval; - - uint8_t len; ffd_metric_seqno_t feasability_distance; ffd_nexthop_t *selected; ffd_nexthop_t *nexthop_list; - uint8_t data[]; + /* an incomplete announcement is specified by a len value of 0xff with NULL data */ + uint8_t len; + uint8_t *data; } ffd_announce_t; typedef struct _ffd_neigh_t { struct _ffd_neigh_t *next; + /* for actual routing, we'd also have to link back to the iface + this neighbour belongs to */ eth_addr_t addr; uint16_t hello_log; @@ -130,6 +138,8 @@ typedef struct _ffd_iface_t { extern const eth_addr_t ffd_addr; +extern ffd_node_id_t self; + extern ffd_iface_t *iface_list; extern ffd_announce_t *announce_list; @@ -137,11 +147,13 @@ extern int sockfd; extern struct timespec now; +bool ffd_is_feasable(const ffd_announce_t *announce, ffd_metric_seqno_t ms); ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce); -ffd_announce_t* ffd_announce_new(size_t len); +void ffd_announce_update_nexthop(ffd_announce_t *announce); +ffd_announce_t* ffd_announce_new(void); void ffd_send_hellos(void); -void ffd_send_update(ffd_iface_t *iface, ffd_neigh_t *neigh, const ffd_announce_t *announce); -void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_node_id_t node, uint16_t type, uint16_t key); +void ffd_send_update(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_announce_t *announce, bool with_data); +void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_node_id_t node, uint16_t type, uint16_t key, bool with_data); #endif /* _FFD_FFD_H_ */ diff --git a/ffd/neigh.c b/ffd/neigh.c index 9788d3f..02a3318 100644 --- a/ffd/neigh.c +++ b/ffd/neigh.c @@ -64,6 +64,9 @@ uint16_t ffd_neigh_get_rxcost(const ffd_neigh_t *neigh) { } uint16_t ffd_neigh_get_cost(const ffd_neigh_t *neigh) { + if (!neigh) /* self */ + return 0; + uint16_t txcost = neigh->txcost; if (txcost < 256) txcost = 256; @@ -77,5 +80,5 @@ uint16_t ffd_neigh_get_cost(const ffd_neigh_t *neigh) { } void ffd_neigh_reset(ffd_iface_t *iface, ffd_neigh_t *neigh) { - ffd_send_announce_request(iface, neigh, FFD_NODE_ID_UNSPEC, 0, 0); + ffd_send_announce_request(iface, neigh, FFD_NODE_ID_UNSPEC, 0, 0, true /* XXX change this later */); } diff --git a/ffd/send.c b/ffd/send.c index fe5035d..48c44fc 100644 --- a/ffd/send.c +++ b/ffd/send.c @@ -126,7 +126,12 @@ static bool add_node_id(ffd_packet_t *packet, size_t max_len, ffd_node_id_t node return true; } -static bool add_update(ffd_packet_t *packet, size_t max_len, ffd_node_id_t *node_id, const ffd_announce_t *announce) { +static bool add_update(ffd_packet_t *packet, size_t max_len, ffd_node_id_t *node_id, ffd_announce_t *announce, bool with_data) { + if (announce->len && !announce->data) { + /* incomplete announce, handle like non-existant announce */ + return true; + } + uint16_t len = packet->len; if (!node_id || !ffd_are_node_ids_equal(node_id, &announce->node)) { @@ -145,32 +150,42 @@ static bool add_update(ffd_packet_t *packet, size_t max_len, ffd_node_id_t *node ffd_metric_seqno_t metric = ffd_announce_get_metric(announce); - update->interval = htons(announce->interval); + update->flags = 0; + update->reserved = 0; + update->interval = htons(FFD_UPDATE_INTERVAL); update->seqno = htons(metric.seqno); update->metric = htons(metric.metric); update->type = htons(announce->type); update->key = htons(announce->key); - memcpy(update->data, announce->data, announce->len); + if (announce->len) { + update->flags |= FFD_UPDATE_WITH_DATA; + + if (with_data) { + memcpy(update->data, announce->data, announce->len); + } + } + + announce->feasability_distance = metric; return true; } -void ffd_send_update(ffd_iface_t *iface, ffd_neigh_t *neigh, const ffd_announce_t *announce) { +void ffd_send_update(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_announce_t *announce, bool with_data) { ffd_packet_t *packet = alloca(sizeof(ffd_packet_t)+FFD_PACKET_MAX); packet->version_magic = htons(FFD_VERSION_MAGIC); packet->len = 0; if (announce) { - add_update(packet, FFD_PACKET_MAX, NULL, announce); + add_update(packet, FFD_PACKET_MAX, NULL, announce, with_data); } else { ffd_node_id_t node_id = FFD_NODE_ID_UNSPEC; ffd_announce_t *a; for (a = announce_list; a; a = a->next) { - if (!add_update(packet, FFD_PACKET_MAX, &node_id, a)) { + if (!add_update(packet, FFD_PACKET_MAX, &node_id, a, with_data)) { if (!send_eth(&ffd_addr, iface->ifindex, packet, sizeof(ffd_packet_t)+ntohs(packet->len))) fprintf(stderr, "send_eth: %m\n"); @@ -186,7 +201,7 @@ void ffd_send_update(ffd_iface_t *iface, ffd_neigh_t *neigh, const ffd_announce_ } } -void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_node_id_t node, uint16_t type, uint16_t key) { +void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_node_id_t node, uint16_t type, uint16_t key, bool with_data) { ffd_packet_t *packet = alloca(sizeof(ffd_packet_t)+FFD_PACKET_MAX); packet->version_magic = htons(FFD_VERSION_MAGIC); @@ -197,9 +212,14 @@ void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_node_ return; req->node = node; + req->flags = 0; + req->reserved = 0; req->type = htons(type); req->key = htons(key); + if (with_data) + req->flags |= FFD_UPDATE_WITH_DATA; + if (!send_eth(&ffd_addr, iface->ifindex, packet, sizeof(ffd_packet_t)+ntohs(packet->len))) fprintf(stderr, "send_eth: %m\n"); } diff --git a/ffd/tlv_types.h b/ffd/tlv_types.h index a37e095..afe793a 100644 --- a/ffd/tlv_types.h +++ b/ffd/tlv_types.h @@ -49,6 +49,8 @@ typedef struct __attribute__((packed)) _ffd_tlv_node_id_t { } ffd_tlv_node_id_t; typedef struct __attribute__((packed)) _ffd_tlv_update_t { + uint8_t flags; + uint8_t reserved; uint16_t interval; uint16_t seqno; uint16_t metric; @@ -59,12 +61,16 @@ typedef struct __attribute__((packed)) _ffd_tlv_update_t { typedef struct __attribute__((packed)) _ffd_tlv_announce_req_t { ffd_node_id_t node; + uint8_t flags; + uint8_t reserved; uint16_t type; uint16_t key; } ffd_tlv_announce_req_t; typedef struct __attribute__((packed)) _ffd_tlv_seqno_req_t { ffd_node_id_t node; + uint8_t flags; + uint8_t reserved; uint16_t type; uint16_t key; uint16_t seqno; -- cgit v1.2.3