From 4a4482017978e360a0ae1ca7645e5e9e084c92b4 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Tue, 2 Oct 2012 23:13:00 +0200 Subject: Add data structures to store announcements and partly implement updates --- ffd/CMakeLists.txt | 1 + ffd/announce.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++++++++ ffd/ffd.c | 52 ++++++++++++++++++++++++++------- ffd/ffd.h | 62 +++++++++++++++++++++++++++++++++++++-- ffd/neigh.c | 5 +++- ffd/send.c | 86 +++++++++++++++++++++++++++++++++++++++++++++++++++++- ffd/tlv_types.h | 26 +++++++++++++++++ ffd/types.h | 2 +- 8 files changed, 300 insertions(+), 17 deletions(-) create mode 100644 ffd/announce.c diff --git a/ffd/CMakeLists.txt b/ffd/CMakeLists.txt index 2a661a3..1571580 100644 --- a/ffd/CMakeLists.txt +++ b/ffd/CMakeLists.txt @@ -1,6 +1,7 @@ include_directories(${CMAKE_CURRENT_SOURCE_DIR} ${FFD_BINARY_DIR} ${CMAKE_CURRENT_BINARY_DIR}) add_executable(ffd + announce.c ffd.c neigh.c netif.c diff --git a/ffd/announce.c b/ffd/announce.c new file mode 100644 index 0000000..eade2f1 --- /dev/null +++ b/ffd/announce.c @@ -0,0 +1,83 @@ +/* + Copyright (c) 2012, Matthias Schiffer + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + 1. Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + 2. Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + + +#include "ffd.h" + + +static bool is_feasable(const ffd_announce_t *announce, const ffd_nexthop_t *nexthop) { + if (FFD_IS_INFINITY(announce->feasability_distance)) + return true; + + int16_t seqno_diff = nexthop->metric_seqno.seqno - announce->feasability_distance.seqno; + + if (seqno_diff < 0) + return true; + if (seqno_diff == 0 && nexthop->metric_seqno.metric < announce->feasability_distance.metric) + return true; + + return false; +} + +static ffd_nexthop_t* select_nexthop(const ffd_announce_t *announce) { + ffd_nexthop_t *ret = NULL; + + ffd_nexthop_t *nexthop; + for (nexthop = announce->nexthop_list->next; nexthop; nexthop = nexthop->next) { + if (is_feasable(announce, nexthop)) + continue; + + int16_t seqno_diff = nexthop->metric_seqno.seqno - ret->metric_seqno.seqno; + + if (nexthop->metric_seqno.metric < ret->metric_seqno.metric + || (nexthop->metric_seqno.metric == ret->metric_seqno.metric && seqno_diff < 0)) { + ret = nexthop; + } + } + + return ret; +} + +ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce) { + ffd_nexthop_t *nexthop = select_nexthop(announce); + + if (nexthop) + return nexthop->metric_seqno; + else + return (ffd_metric_seqno_t){0xffff, 0}; +} + + +ffd_announce_t* ffd_announce_new(size_t len) { + ffd_announce_t *a = calloc(1, sizeof(ffd_announce_t)+len); + + a->len = len; + a->feasability_distance = (ffd_metric_seqno_t){0xffff, 0}; + + a->next = announce_list; + announce_list = a; + + return a; +} diff --git a/ffd/ffd.c b/ffd/ffd.c index c4ddb5b..879d710 100644 --- a/ffd/ffd.c +++ b/ffd/ffd.c @@ -51,14 +51,11 @@ static char *mesh = "bat0"; int sockfd; struct timespec now; -ffd_iface_t *iface_list = NULL; +ffd_node_id_t self; -static ffd_neigh_t self; -//static ffd_orig_t own_data; +ffd_iface_t *iface_list = NULL; -/* neighs and origs that have been changed must be moved to front */ -//static ffd_neigh_t *neigh_data = NULL; -//static ffd_orig_t *orig_data = NULL; +ffd_announce_t *announce_list = NULL; static inline bool use_netif(const char *ifname) { @@ -87,13 +84,27 @@ static bool init_self() { if (is_eth_addr_unspec(&primary_addr)) return false; - memset(&self, 0, sizeof(self)); - //memset(&own_data, 0, sizeof(own_data)); + self.id[0] = primary_addr.d[0]^0x02; + self.id[1] = primary_addr.d[1]; + self.id[2] = primary_addr.d[2]; + self.id[3] = 0xff; + self.id[4] = 0xfe; + self.id[5] = primary_addr.d[3]; + self.id[6] = primary_addr.d[4]; + self.id[7] = primary_addr.d[5]; + + ffd_announce_t *announce = announce_list = calloc(1, sizeof(ffd_announce_t)); + + announce->node = self; + announce->type = 1; + announce->key = 1337; + announce->interval = 6000; - //self.addr = own_data.addr = primary_addr; + ffd_nexthop_t *nexthop = announce->nexthop_list = malloc(sizeof(ffd_nexthop_t)); - //random_bytes(&self.rev, sizeof(self.rev)); - //random_bytes(&own_data.rev, sizeof(own_data.rev)); + nexthop->addr = ETH_ADDR_UNSPEC; + nexthop->metric_seqno.metric = 0; + nexthop->metric_seqno.seqno = 0; return true; } @@ -246,6 +257,21 @@ static void handle_tlv_ihu(const ffd_tlv_ihu_t *tlv_ihu, size_t len, const eth_a fprintf(stderr, "debug: accepted IHU, txcost is %u, cost is %u now.\n", neigh->txcost, ffd_neigh_get_cost(neigh)); } +static void handle_tlv_announce_req(const ffd_tlv_announce_req_t *tlv_req, size_t len, const eth_addr_t *addr, ffd_iface_t *iface) { + if (len < sizeof(ffd_tlv_announce_req_t)) { + fprintf(stderr, "warn: received short announce request TLV.\n"); + return; + } + + ffd_announce_t *announce = NULL; + + if (!ffd_is_node_id_unspec(&tlv_req->node)) { + announce = NULL; + } + + ffd_send_update(iface, ffd_neigh_get(iface, addr), announce); +} + static void handle_tlv(ffd_tlv_type_t type, const void *data, size_t len, void *arg) { const struct sockaddr_ll *from = arg; const eth_addr_t *addr = (const eth_addr_t*)from->sll_addr; @@ -263,6 +289,10 @@ static void handle_tlv(ffd_tlv_type_t type, const void *data, size_t len, void * handle_tlv_ihu(data, len, addr, iface); return; + case TLV_ANNOUNCE_REQ: + handle_tlv_announce_req(data, len, addr, iface); + return; + default: fprintf(stderr, "debug: received unknown TLV %u on %s.\n", type, iface->name); return; diff --git a/ffd/ffd.h b/ffd/ffd.h index 4d70f17..5d59a23 100644 --- a/ffd/ffd.h +++ b/ffd/ffd.h @@ -41,13 +41,64 @@ #define FFD_IHU_INTERVAL (3*FFD_HELLO_INTERVAL) +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; + + struct timespec last_update; + eth_addr_t addr; + ffd_metric_seqno_t metric_seqno; +} ffd_nexthop_t; + typedef struct _ffd_announce_t { struct _ffd_announce_t *next; - uint8_t type; + 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[]; -} ffd_announce_head_t; +} ffd_announce_t; typedef struct _ffd_neigh_t { struct _ffd_neigh_t *next; @@ -80,12 +131,17 @@ typedef struct _ffd_iface_t { extern const eth_addr_t ffd_addr; extern ffd_iface_t *iface_list; +extern ffd_announce_t *announce_list; extern int sockfd; extern struct timespec now; +ffd_metric_seqno_t ffd_announce_get_metric(const ffd_announce_t *announce); +ffd_announce_t* ffd_announce_new(); + void ffd_send_hellos(); -void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, void *announce); +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); #endif /* _FFD_FFD_H_ */ diff --git a/ffd/neigh.c b/ffd/neigh.c index 6cfd5e8..9788d3f 100644 --- a/ffd/neigh.c +++ b/ffd/neigh.c @@ -50,6 +50,9 @@ void ffd_neigh_free_list(ffd_neigh_t *neigh) { } uint16_t ffd_neigh_get_rxcost(const ffd_neigh_t *neigh) { + if (!neigh->hello_log || !neigh->hello_interval) + return 0xffff; + int timediff = timespec_diff(&now, &neigh->last_hello)/10; int shift = (timediff - neigh->hello_interval/2)/neigh->hello_interval; int received = __builtin_popcount(neigh->hello_log << shift); @@ -74,5 +77,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, NULL); + ffd_send_announce_request(iface, neigh, FFD_NODE_ID_UNSPEC, 0, 0); } diff --git a/ffd/send.c b/ffd/send.c index d020aca..3478e80 100644 --- a/ffd/send.c +++ b/ffd/send.c @@ -116,6 +116,90 @@ void ffd_send_hellos() { } } -void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, void *announce) { +static bool add_node_id(ffd_packet_t *packet, size_t max_len, ffd_node_id_t node_id) { + ffd_tlv_node_id_t *tlv = ffd_tlv_add(packet, FFD_PACKET_MAX, TLV_NODE_ID, sizeof(ffd_tlv_node_id_t)); + if (!tlv) + return false; + tlv->id = node_id; + + 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) { + uint16_t len = packet->len; + + if (!node_id || !ffd_are_node_ids_equal(node_id, &announce->node)) { + if (!add_node_id(packet, max_len, announce->node)) + return false; + + if (node_id) + *node_id = announce->node; + } + + ffd_tlv_update_t *update = ffd_tlv_add(packet, FFD_PACKET_MAX, TLV_UPDATE, sizeof(ffd_tlv_update_t)+announce->len); + if (!update) { + packet->len = len; + return false; + } + + ffd_metric_seqno_t metric = ffd_announce_get_metric(announce); + + update->interval = htons(announce->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); + + return true; +} + +void ffd_send_update(ffd_iface_t *iface, ffd_neigh_t *neigh, const ffd_announce_t *announce) { + 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); + } + 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 (!send_eth(&ffd_addr, iface->ifindex, packet, sizeof(ffd_packet_t)+ntohs(packet->len))) + fprintf(stderr, "send_eth: %m\n"); + + node_id = FFD_NODE_ID_UNSPEC; + packet->len = 0; + } + } + + if (packet->len) { + if (!send_eth(&ffd_addr, iface->ifindex, packet, sizeof(ffd_packet_t)+ntohs(packet->len))) + fprintf(stderr, "send_eth: %m\n"); + } + } +} + +void ffd_send_announce_request(ffd_iface_t *iface, ffd_neigh_t *neigh, ffd_node_id_t node, uint16_t type, uint16_t key) { + ffd_packet_t *packet = alloca(sizeof(ffd_packet_t)+FFD_PACKET_MAX); + + packet->version_magic = htons(FFD_VERSION_MAGIC); + packet->len = 0; + + ffd_tlv_announce_req_t *req = ffd_tlv_add(packet, FFD_PACKET_MAX, TLV_ANNOUNCE_REQ, sizeof(ffd_tlv_announce_req_t)); + if (!req) + return; + + req->node = node; + req->type = htons(type); + req->key = htons(key); + + 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 dcb44b4..a37e095 100644 --- a/ffd/tlv_types.h +++ b/ffd/tlv_types.h @@ -44,4 +44,30 @@ typedef struct __attribute__((packed)) _ffd_tlv_ihu_t { uint8_t address[]; } ffd_tlv_ihu_t; +typedef struct __attribute__((packed)) _ffd_tlv_node_id_t { + ffd_node_id_t id; +} ffd_tlv_node_id_t; + +typedef struct __attribute__((packed)) _ffd_tlv_update_t { + uint16_t interval; + uint16_t seqno; + uint16_t metric; + uint16_t type; + uint16_t key; + uint8_t data[]; +} ffd_tlv_update_t; + +typedef struct __attribute__((packed)) _ffd_tlv_announce_req_t { + ffd_node_id_t node; + 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; + uint16_t type; + uint16_t key; + uint16_t seqno; +} ffd_tlv_seqno_req_t; + #endif /* _FFD_TLV_TYPES_H_ */ diff --git a/ffd/types.h b/ffd/types.h index cd2cbd2..f0c6c39 100644 --- a/ffd/types.h +++ b/ffd/types.h @@ -33,7 +33,7 @@ #include -typedef struct __attribute__((__packed__)) _eth_addr_t { +typedef struct __attribute__((packed)) _eth_addr_t { uint8_t d[ETH_ALEN]; } eth_addr_t; -- cgit v1.2.3