In order to prevent routing loops, Babel installs temporary blackhole routes to prefixes that expire or are otherwise lost. These blackhole routes are maintained for a while to ensure the route has been flushed from the whole network; the default hold time is 64 seconds. In the updated IETF version of Babel (rfc6126bis), an alternative procedure was added which replaces this hold time with an explicit acknowledgement procedure. This procedure simply consists of sending a retraction along with an acknowledgement request to all neighbours, and removing the blackhole route once all neighbours have acknowledged the retraction. As this usually happens pretty quickly, the hold time during which the route is blackholed is almost completely avoided. This patch implements the above behaviour. It adds a generic facility to the Babel protocol which allows for sending sequences of acknowledgement requests to a number of neighbours, and executing a callback function once all the requests have been ACKed. This facility is then used to implement the acknowledgement scheme when a route is lost. Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk> --- proto/babel/babel.c | 199 +++++++++++++++++++++++++++++++++++++++++++++++--- proto/babel/babel.h | 25 +++++++ proto/babel/packets.c | 71 +++++++++++++++++- 3 files changed, 283 insertions(+), 12 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 3cf8aaf0..3d235382 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -52,8 +52,10 @@ static void babel_select_route(struct babel_proto *p, struct babel_entry *e, str static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e); static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n); static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr); +static void babel_send_ack_sequence(struct babel_ack_sequence *seq); +static void babel_flush_outgoing_ack(struct babel_outgoing_ack_req *ack); static void babel_update_cost(struct babel_neighbor *n); -static inline void babel_kick_timer(struct babel_proto *p); +static inline void babel_kick_timer(struct babel_proto *p, btime interval); static inline void babel_iface_kick_timer(struct babel_iface *ifa); static inline void babel_lock_neighbor(struct babel_neighbor *nbr) @@ -428,6 +430,7 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) nbr->txcost = BABEL_INFINITY; nbr->cost = BABEL_INFINITY; init_list(&nbr->routes); + init_list(&nbr->ack_reqs); babel_lock_neighbor(nbr); add_tail(&ifa->neigh_list, NODE nbr); @@ -438,6 +441,7 @@ static void babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) { struct babel_route *r; + struct babel_outgoing_ack_req *a; node *n; TRACE(D_EVENTS, "Removing neighbor %I on %s", nbr->addr, nbr->ifa->iface->name); @@ -449,6 +453,12 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) babel_flush_route(p, r); } + WALK_LIST_FIRST(n, nbr->ack_reqs) + { + a = SKIP_BACK(struct babel_outgoing_ack_req, neigh_ack, n); + babel_flush_outgoing_ack(a); + } + nbr->ifa = NULL; rem_node(NODE nbr); babel_unlock_neighbor(nbr); @@ -508,6 +518,69 @@ babel_expire_neighbors(struct babel_proto *p) } } +static void babel_flush_ack_seq(struct babel_ack_sequence *seq) +{ + struct babel_proto *p = seq->p; + struct babel_msg_node *msgn; + + rem_node(NODE seq); + + WALK_LIST_FIRST(msgn, seq->payload) + { + rem_node(NODE msgn); + sl_free(p->msg_slab, msgn); + } + + mb_free(seq); +} + +static int +babel_check_ack_seq(struct babel_ack_sequence *seq) +{ + if (EMPTY_LIST(seq->acks)) + { + seq->callback(seq); + babel_flush_ack_seq(seq); + return 1; + } + return 0; +} + +static void +babel_flush_outgoing_ack(struct babel_outgoing_ack_req *ack) +{ + struct babel_ack_sequence *seq = ack->seq; + rem_node(&ack->neigh_ack); + rem_node(NODE ack); + mb_free(ack); + babel_check_ack_seq(seq); +} + +static void +babel_expire_ack_seqs(struct babel_proto *p) +{ + struct babel_ack_sequence *seq, *nxt; + btime now_ = current_time(); + + WALK_LIST_DELSAFE(seq, nxt, p->ack_seqs) + { + if (now_ >= seq->expires) + { + if (seq->retries > 0) + { + babel_send_ack_sequence(seq); + seq->retries--; + seq->expires = now_ + BABEL_ACK_RETRY_INTERVAL; + babel_kick_timer(p, BABEL_ACK_RETRY_INTERVAL); + } + else + { + babel_flush_ack_seq(seq); + } + } + } +} + /* * Best route selection @@ -784,6 +857,40 @@ babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce) babel_send_unicast(&msg, ifa, dest); } +static void +babel_send_ack_sequence(struct babel_ack_sequence *seq) +{ + struct babel_msg_node msgn = {}; + struct babel_outgoing_ack_req *ack; + + msgn.msg.type = BABEL_TLV_ACK_REQ; + msgn.msg.ack_req.interval = BABEL_ACK_RETRY_INTERVAL; + add_tail(&seq->payload, NODE &msgn); + + WALK_LIST(ack, seq->acks) { + DBG("Sending ACK request to %I with nonce %d\n", ack->nbr->addr, ack->nonce); + msgn.msg.ack_req.nonce = ack->nonce; + babel_send_unicast_list(&seq->payload, ack->nbr->ifa, ack->nbr->addr); + } + rem_node(NODE &msgn); +} + +static void +babel_retraction_ack_complete(struct babel_ack_sequence *seq) +{ + struct babel_proto *p = seq->p; + struct babel_msg_node *msgn = HEAD(seq->payload); + struct babel_entry *e = babel_find_entry(p, &msgn->msg.update.net); + + ASSERT(msgn->msg.type == BABEL_TLV_UPDATE); + + if (e && e->unreachable && e->valid == BABEL_ENTRY_STALE) + { + DBG("ACK sequence for retraction complete, retracting route: %N\n", e->n.addr); + babel_announce_retraction(p, e); + } +} + static void babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n) { @@ -1020,7 +1127,7 @@ babel_send_retraction(struct babel_iface *ifa, net_addr *n) TRACE(D_PACKETS, "Sending retraction for %N seqno %d", n, p->update_seqno); msg.type = BABEL_TLV_UPDATE; - msg.update.interval = ifa->cf->update_interval; + msg.update.interval = BABEL_INFINITY; msg.update.seqno = p->update_seqno; msg.update.metric = BABEL_INFINITY; msg.update.net = *n; @@ -1028,6 +1135,54 @@ babel_send_retraction(struct babel_iface *ifa, net_addr *n) babel_enqueue(&msg, ifa); } +static void +babel_send_retraction_acked(struct babel_proto *p, net_addr *n) +{ + struct babel_ack_sequence *seq = mb_allocz(p->p.pool, sizeof(struct babel_ack_sequence)); + struct babel_msg_node *msgn = sl_alloc(p->msg_slab); + struct babel_iface *ifa; + struct babel_neighbor *nbr; + int i = 0; + + init_list(&seq->acks); + init_list(&seq->payload); + memset(msgn, 0, sizeof(*msgn)); + seq->callback = babel_retraction_ack_complete; + seq->expires = current_time() + BABEL_ACK_RETRY_INTERVAL; + seq->retries = BABEL_ACK_RETRIES; + seq->p = p; + add_tail(&p->ack_seqs, NODE seq); + + msgn->msg.type = BABEL_TLV_UPDATE; + msgn->msg.update.interval = BABEL_INFINITY; + msgn->msg.update.seqno = p->update_seqno; + msgn->msg.update.metric = BABEL_INFINITY; + msgn->msg.update.net = *n; + + add_tail(&seq->payload, NODE msgn); + + WALK_LIST(ifa, p->interfaces) { + WALK_LIST(nbr, ifa->neigh_list) { + struct babel_outgoing_ack_req *ack = mb_allocz(p->p.pool, sizeof(struct babel_outgoing_ack_req)); + ack->nbr = nbr; + ack->seq = seq; + ack->nonce = random(); + add_tail(&seq->acks, NODE ack); + add_tail(&nbr->ack_reqs, &ack->neigh_ack); + i++; + } + } + + DBG("Created ACK sequence for %N with %d requests\n", n, i); + + /* Sequence may be empty if we have no neighbors */ + if (!babel_check_ack_seq(seq)) + { + babel_send_ack_sequence(seq); + babel_kick_timer(p, BABEL_ACK_RETRY_INTERVAL); + } +} + static void babel_send_wildcard_retraction(struct babel_iface *ifa) { @@ -1096,11 +1251,35 @@ babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval) n->last_hello_int = interval; } - /* * TLV handlers */ +void +babel_handle_ack(union babel_msg *m, struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + struct babel_msg_ack *msg = &m->ack; + node *n; + + TRACE(D_PACKETS, "Handling ACK nonce %d from %I", + msg->nonce, msg->sender); + + struct babel_neighbor *nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) + return; + + WALK_LIST(n, nbr->ack_reqs) + { + struct babel_outgoing_ack_req *ack = SKIP_BACK(struct babel_outgoing_ack_req, neigh_ack, n); + if (ack->nonce == msg->nonce) + { + babel_flush_outgoing_ack(ack); + return; + } + } +} + void babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa) { @@ -2044,13 +2223,14 @@ babel_timer(timer *t) babel_expire_routes(p); babel_expire_neighbors(p); + babel_expire_ack_seqs(p); } static inline void -babel_kick_timer(struct babel_proto *p) +babel_kick_timer(struct babel_proto *p, btime interval) { - if (p->timer->expires > (current_time() + 100 MS)) - tm_start(p->timer, 100 MS); + if (p->timer->expires > (current_time() + interval)) + tm_start(p->timer, interval); } @@ -2161,9 +2341,9 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, e->valid = BABEL_ENTRY_STALE; e->metric = BABEL_INFINITY; - - babel_trigger_update(p); e->updated = current_time(); + + babel_send_retraction_acked(p, net->n.addr); } } @@ -2214,6 +2394,7 @@ babel_start(struct proto *P) OFFSETOF(struct babel_entry, n), 0, babel_init_entry); init_list(&p->interfaces); + init_list(&p->ack_seqs); p->timer = tm_new_init(P->pool, babel_timer, p, 1 S, 0); tm_start(p->timer, 1 S); p->update_seqno = 1; @@ -2269,7 +2450,7 @@ babel_reconfigure(struct proto *P, struct proto_config *CF) babel_reconfigure_ifaces(p, new); babel_trigger_update(p); - babel_kick_timer(p); + babel_kick_timer(p, 100 MS); return 1; } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 1128d261..684bad1b 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -56,6 +56,8 @@ #define BABEL_TIME_UNITS 10000 /* On-wire times are counted in centiseconds */ #define BABEL_MIN_INTERVAL (0x0001 * BABEL_TIME_UNITS) #define BABEL_MAX_INTERVAL (0xFFFF * BABEL_TIME_UNITS) +#define BABEL_ACK_RETRY_INTERVAL (1 S_) +#define BABEL_ACK_RETRIES 2 #define BABEL_OVERHEAD (IP6_HEADER_LENGTH+UDP_HEADER_LENGTH) #define BABEL_MIN_MTU (512 + BABEL_OVERHEAD) @@ -142,6 +144,7 @@ struct babel_proto { struct channel *ip6_channel; list interfaces; /* Interfaces we really know about (struct babel_iface) */ + list ack_seqs; /* Outstanding ACK sequences */ u64 router_id; u16 update_seqno; /* To be increased on request */ u8 update_seqno_inc; /* Request for update_seqno increase */ @@ -205,6 +208,7 @@ struct babel_neighbor { btime ihu_expiry; list routes; /* Routes this neighbour has sent us (struct babel_route) */ + list ack_reqs; /* Outstanding ack requests sent to this neighbor */ }; struct babel_source { @@ -263,6 +267,25 @@ struct babel_entry { #define BABEL_ENTRY_VALID 1 /* Valid outgoing route */ #define BABEL_ENTRY_STALE 2 /* Stale outgoing route, waiting for GC */ +struct babel_ack_sequence { + node n; + list acks; /* list of pending acks in sequence (babel_outgoing_ack_req) */ + btime expires; + u8 retries; + list payload; /* list of babel_msg_nodes in outgoing messages */ + + void (*callback)(struct babel_ack_sequence *); /* called when there are no more pending ACKs */ + struct babel_proto *p; +}; + +struct babel_outgoing_ack_req { + node n; /* in struct babel_ack_sequence->acks */ + node neigh_ack; /* in struct babel_neighbor->ack_reqs */ + u16 nonce; + struct babel_neighbor *nbr; + struct babel_ack_sequence *seq; +}; + /* * Internal TLV messages @@ -278,6 +301,7 @@ struct babel_msg_ack_req { struct babel_msg_ack { u8 type; u16 nonce; + ip_addr sender; }; struct babel_msg_hello { @@ -358,6 +382,7 @@ void babel_show_routes(struct proto *P); /* packets.c */ void babel_enqueue(union babel_msg *msg, struct babel_iface *ifa); void babel_send_unicast(union babel_msg *msg, struct babel_iface *ifa, ip_addr dest); +void babel_send_unicast_list(list *lst, struct babel_iface *ifa, ip_addr dest); int babel_open_socket(struct babel_iface *ifa); void babel_send_queue(void *arg); diff --git a/proto/babel/packets.c b/proto/babel/packets.c index dd86222a..5b4c4555 100644 --- a/proto/babel/packets.c +++ b/proto/babel/packets.c @@ -229,6 +229,7 @@ put_ip6_ll(void *p, ip6_addr addr) * TLV read/write functions */ +static int babel_read_ack(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static int babel_read_ack_req(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static int babel_read_hello(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static int babel_read_ihu(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); @@ -239,6 +240,7 @@ static int babel_read_route_request(struct babel_tlv *hdr, union babel_msg *msg, static int babel_read_seqno_request(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static uint babel_write_ack(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); +static uint babel_write_ack_req(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); static uint babel_write_hello(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); static uint babel_write_ihu(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); static uint babel_write_update(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); @@ -256,14 +258,14 @@ static const struct babel_tlv_data tlv_data[BABEL_TLV_MAX] = { [BABEL_TLV_ACK_REQ] = { sizeof(struct babel_tlv_ack_req), babel_read_ack_req, - NULL, + babel_write_ack_req, babel_handle_ack_req }, [BABEL_TLV_ACK] = { sizeof(struct babel_tlv_ack), - NULL, + babel_read_ack, babel_write_ack, - NULL + babel_handle_ack }, [BABEL_TLV_HELLO] = { sizeof(struct babel_tlv_hello), @@ -327,6 +329,36 @@ babel_read_ack_req(struct babel_tlv *hdr, union babel_msg *m, return PARSE_SUCCESS; } +static uint +babel_write_ack_req(struct babel_tlv *hdr, union babel_msg *m, + struct babel_write_state *state UNUSED, uint max_len UNUSED) +{ + struct babel_tlv_ack_req *tlv = (void *) hdr; + struct babel_msg_ack_req *msg = &m->ack_req; + + TLV_HDR0(tlv, BABEL_TLV_ACK_REQ); + put_u16(&tlv->nonce, msg->nonce); + put_time16(&tlv->interval, msg->interval); + + return sizeof(struct babel_tlv_ack_req); +} + + +static int +babel_read_ack(struct babel_tlv *hdr, union babel_msg *m, + struct babel_parse_state *state) +{ + struct babel_tlv_ack *tlv = (void *) hdr; + struct babel_msg_ack *msg = &m->ack; + + msg->type = BABEL_TLV_ACK; + msg->nonce = get_u16(&tlv->nonce); + msg->sender = state->saddr; + + return PARSE_SUCCESS; +} + + static uint babel_write_ack(struct babel_tlv *hdr, union babel_msg *m, struct babel_write_state *state UNUSED, uint max_len UNUSED) @@ -1141,6 +1173,39 @@ babel_send_unicast(union babel_msg *msg, struct babel_iface *ifa, ip_addr dest) babel_kick_queue(ifa); } +/** + * babel_send_unicast_list - send a multi-TLV packet via unicast to a destination + * @lst: list of TLVs to send + * @ifa: Interface to send via + * @dest: Destination of the TLV + * + * This function is used to send a list of TLVs via unicast to a designated + * receiver. This is used for sending messages that comprise multiple TLVs, such + * as those that include an acknowledgement request. + */ +void +babel_send_unicast_list(list *lst, struct babel_iface *ifa, ip_addr dest) +{ + struct babel_proto *p = ifa->proto; + struct babel_msg_node *msgn, *msgn_copy; + list queue; + + init_list(&queue); + WALK_LIST(msgn, *lst) + { + msgn_copy = sl_alloc(p->msg_slab); + memcpy(msgn_copy, msgn, sizeof(*msgn_copy)); + + add_tail(&queue, NODE msgn_copy); + } + babel_write_queue(ifa, &queue); + babel_send_to(ifa, dest); + + /* We could overwrite waiting packet here, we may have to kick TX queue */ + if (!EMPTY_LIST(ifa->msg_queue)) + babel_kick_queue(ifa); +} + /** * babel_enqueue - enqueue a TLV for transmission on an interface * @msg: TLV to enqueue (in internal TLV format) -- 2.16.1