The seqno request retransmission handling was tracking the destination that a forwarded request was being sent to and always retransmitting to that same sender. Instead, we should really be tracking the originator of the request (i.e., the neighbour on behalf of which we're forwarding the request), and always selecting the best candidate to send the request to whenever we do a retransmission. Tying the seqno request entry to the destination had the problem that when that destination neighbour entry was removed, we'd remove the entire request, and thus no longer retransmit it. Tying the entry to the neighbour on whose behalf we are forwarding the entry instead means that we can just clear out the neighbour from the request entry when we're removing it, as long as we keep a separate flag specifying that it's a unicast request. One complication that arises from this change is that seqno requests sent in response to unfeasible updates (section 3.8.2.2 of the RFC) have to be sent as unicast, but not necessarily to the "best" candidate according to the selection logic. Rather than complicate the request tracking, we just change the requests sent in response to an unfeasible update to be one-off unicast messages without any retransmission tracking. This should be OK, as we'll send another request the next time we receive the unfeasible update anyway. Also make sure to discard incoming requests with a hop count of zero (as they are forbidden by the RFC). Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk> --- Ondrej originally noticed this issue back in May[0], I only just got around to fixing it now. We can't remove the neighbour tracking entirely, as we need it to make sure we don't send a unicasted request back to the neighbour it came from. [0] https://bird.network.cz/pipermail/bird-users/2022-May/016140.html proto/babel/babel.c | 172 ++++++++++++++++++++++++++++++-------------- proto/babel/babel.h | 3 +- 2 files changed, 122 insertions(+), 53 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ecfd2763d737..0cc59ce26d8f 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -53,7 +53,7 @@ static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e); static void babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod); 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_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr, struct babel_neighbor *tgt); static void babel_update_cost(struct babel_neighbor *n); static inline void babel_kick_timer(struct babel_proto *p); static inline void babel_iface_kick_timer(struct babel_iface *ifa); @@ -288,9 +288,6 @@ babel_expire_routes(struct babel_proto *p) babel_expire_routes_(p, &p->ip6_rtable); } -static inline int seqno_request_valid(struct babel_seqno_request *sr) -{ return !sr->nbr || sr->nbr->ifa; } - /* * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send * it to network. Do nothing if it is already in the table. @@ -299,21 +296,25 @@ static inline int seqno_request_valid(struct babel_seqno_request *sr) static void babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e, u64 router_id, u16 seqno, u8 hop_count, - struct babel_neighbor *nbr) + struct babel_neighbor *fwd_from) { struct babel_seqno_request *sr; + /* + * To suppress duplicates, check if we already have a newer (higher seqno) + * outstanding request; if this one is newer, replace the old one. Consider + * unicast and multicast requests separately. + */ WALK_LIST(sr, e->requests) - if (sr->router_id == router_id) + if (sr->router_id == router_id && sr->unicast == !!fwd_from) { - /* Found matching or newer */ - if (ge_mod64k(sr->seqno, seqno) && seqno_request_valid(sr)) + if (ge_mod64k(sr->seqno, seqno)) return; /* Found older */ rem_node(NODE sr); - if (sr->nbr) + if (sr->from) rem_node(&sr->nbr_node); goto found; @@ -325,22 +326,48 @@ babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e, found: sr->router_id = router_id; sr->seqno = seqno; - sr->hop_count = hop_count; + sr->hop_count = hop_count ?: BABEL_INITIAL_HOP_COUNT; sr->count = 0; sr->expires = current_time() + BABEL_SEQNO_REQUEST_EXPIRY; - if (sr->nbr = nbr) - add_tail(&nbr->requests, &sr->nbr_node); + sr->from = fwd_from; + if (sr->from) { + add_tail(&fwd_from->requests, &sr->nbr_node); + sr->unicast = 1; + } add_tail(&e->requests, NODE sr); - babel_send_seqno_request(p, e, sr); + babel_send_seqno_request(p, e, sr, NULL); +} + +static void +babel_generate_seqno_request(struct babel_proto *p, struct babel_entry *e, + u64 router_id, u16 seqno, struct babel_neighbor *tgt) +{ + struct babel_seqno_request *sr, req = { + .router_id = router_id, + .seqno = seqno, + .hop_count = BABEL_INITIAL_HOP_COUNT, + .unicast = 1, + }; + + WALK_LIST(sr, e->requests) + /* + * We only suppress targeted seqno requests if we already have an + * outstanding *multicast* request for the same prefix (as other outstanding + * requests may not be sent to the same target) + */ + if (sr->router_id == router_id && ge_mod64k(sr->seqno, seqno) && !sr->from) + return; + + babel_send_seqno_request(p, e, &req, tgt); } static void babel_remove_seqno_request(struct babel_proto *p UNUSED, struct babel_seqno_request *sr) { - if (sr->nbr) + if (sr->from) rem_node(&sr->nbr_node); rem_node(NODE sr); @@ -351,17 +378,17 @@ static int babel_satisfy_seqno_request(struct babel_proto *p, struct babel_entry *e, u64 router_id, u16 seqno) { - struct babel_seqno_request *sr; + struct babel_seqno_request *sr, *srx; + int ret = 0; - WALK_LIST(sr, e->requests) + WALK_LIST_DELSAFE(sr, srx, e->requests) if ((sr->router_id == router_id) && ge_mod64k(seqno, sr->seqno)) { - /* Found the request, remove it */ babel_remove_seqno_request(p, sr); - return 1; + ret = 1; } - return 0; + return ret; } static void @@ -372,13 +399,6 @@ babel_expire_requests(struct babel_proto *p, struct babel_entry *e) WALK_LIST_DELSAFE(sr, srx, e->requests) { - /* Remove seqno requests sent to dead neighbors */ - if (!seqno_request_valid(sr)) - { - babel_remove_seqno_request(p, sr); - continue; - } - /* Handle expired requests - resend or remove */ if (sr->expires && sr->expires <= now_) { @@ -386,7 +406,7 @@ babel_expire_requests(struct babel_proto *p, struct babel_entry *e) { sr->count++; sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count); - babel_send_seqno_request(p, e, sr); + babel_send_seqno_request(p, e, sr, NULL); } else { @@ -454,7 +474,16 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) struct babel_seqno_request *sr; WALK_LIST_FIRST2(sr, nbr_node, nbr->requests) - babel_remove_seqno_request(p, sr); + { + /* + * There may be other neighbours who sent the same request but were + * suppressed as duplicates, so keep the request alive but remove the + * neighbour entry (which is only used to make sure the request is not + * sent back where it came from). + */ + rem_node(&sr->nbr_node); + sr->from = NULL; + } nbr->ifa = NULL; rem_node(NODE nbr); @@ -902,23 +931,66 @@ babel_send_wildcard_request(struct babel_iface *ifa) babel_enqueue(&msg, ifa); } +static struct babel_neighbor * +babel_find_seqno_request_tgt(struct babel_entry *e, struct babel_neighbor *skip) +{ + struct babel_route *r, *best_feasible = NULL, *best_any = NULL; + + WALK_LIST(r, e->routes) + { + if (r->neigh == skip) + continue; + + if (r->feasible && (!best_feasible || r->metric < best_feasible->metric)) + best_feasible = r; + + if (!best_any || r->metric < best_any->metric) + best_any = r; + } + + if (best_feasible) + return best_feasible->neigh; + + if (best_any) + return best_any->neigh; + + return NULL; +} + static void -babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr) +babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, + struct babel_seqno_request *sr, struct babel_neighbor *tgt) { union babel_msg msg = {}; msg.type = BABEL_TLV_SEQNO_REQUEST; - msg.seqno_request.hop_count = sr->hop_count ?: BABEL_INITIAL_HOP_COUNT; + msg.seqno_request.hop_count = sr->hop_count; msg.seqno_request.seqno = sr->seqno; msg.seqno_request.router_id = sr->router_id; net_copy(&msg.seqno_request.net, e->n.addr); - if (sr->nbr) + if (tgt || sr->unicast) { + if (!tgt) + { + /* + * If we don't have a target to send to, but we're forwarding this request + * on behalf of another node, select a new target from the routing table + */ + + tgt = babel_find_seqno_request_tgt(e, sr->from); + if (!tgt) + { + TRACE(D_PACKETS, "Couldn't find a neighbour to forward seqno request for %N router-id %lR seqno %d to", + e->n.addr, sr->router_id, sr->seqno); + return; + } + } + TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d to %I on %s", - e->n.addr, sr->router_id, sr->seqno, sr->nbr->addr, sr->nbr->ifa->ifname); + e->n.addr, sr->router_id, sr->seqno, tgt->addr, tgt->ifa->ifname); - babel_send_unicast(&msg, sr->nbr->ifa, sr->nbr->addr); + babel_send_unicast(&msg, tgt->ifa, tgt->addr); } else { @@ -1285,10 +1357,13 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) metric = babel_compute_metric(nbr, msg->metric); best = e->selected; - /* RFC section 3.8.2.2 - Dealing with unfeasible updates */ + /* + * RFC section 3.8.2.2 - Dealing with unfeasible updates. Generate a one-off + * (not retransmitted) unicast seqno request to the originator of this update + */ if (!feasible && (metric != BABEL_INFINITY) && (!best || (r == best) || (metric < best->metric))) - babel_add_seqno_request(p, e, s->router_id, s->seqno + 1, 0, nbr); + babel_generate_seqno_request(p, e, s->router_id, s->seqno + 1, nbr); /* Special case - ignore unfeasible update to best route */ if (r == best && !feasible && (msg->router_id == r->router_id)) @@ -1361,6 +1436,12 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) /* RFC 6126 3.8.1.2 */ + if (!msg->hop_count) { + TRACE(D_PACKETS, "Discarding seqno request for %N router-id %lR with hop count 0 from %I", + &msg->net, msg->router_id, msg->sender); + return; + } + TRACE(D_PACKETS, "Handling seqno request for %N router-id %lR seqno %d hop count %d", &msg->net, msg->router_id, msg->seqno, msg->hop_count); @@ -1389,26 +1470,13 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) { /* Not ours; forward if TTL allows it */ - /* Find best admissible route */ - struct babel_route *r, *best1 = NULL, *best2 = NULL; - WALK_LIST(r, e->routes) - if ((r->router_id == msg->router_id) && !ipa_equal(r->neigh->addr, msg->sender)) - { - /* Find best feasible route */ - if ((!best1 || r->metric < best1->metric) && r->feasible) - best1 = r; - - /* Find best not necessary feasible route */ - if (!best2 || r->metric < best2->metric) - best2 = r; - } + struct babel_neighbor *nbr; - /* If no route is found, do nothing */ - r = best1 ?: best2; - if (!r) + nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) return; - babel_add_seqno_request(p, e, msg->router_id, msg->seqno, msg->hop_count-1, r->neigh); + babel_add_seqno_request(p, e, msg->router_id, msg->seqno, msg->hop_count-1, nbr); } } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 8b6da3c8ce91..a87a11ff3620 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -276,7 +276,8 @@ struct babel_seqno_request { u8 hop_count; u8 count; btime expires; - struct babel_neighbor *nbr; + struct babel_neighbor *from; + u8 unicast; }; struct babel_entry { -- 2.38.1