From 321ff8c4049ec6c2fa198858b4a7f1814ce05e39 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Tue, 19 Jul 2016 11:57:20 +0200 Subject: Babel: Make sure intervals do not overflow MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Intervals are carried as 16-bit centisecond values, but kept internally in 16-bit second values, which causes a potential for overflow. This adds some checks to make sure this does not happen. Signed-off-by: Toke Høiland-Jørgensen --- proto/babel/babel.h | 4 +++- proto/babel/config.Y | 9 +++++---- 2 files changed, 8 insertions(+), 5 deletions(-) (limited to 'proto/babel') diff --git a/proto/babel/babel.h b/proto/babel/babel.h index aea0dd88..7b5037ab 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -50,10 +50,12 @@ #define BABEL_INITIAL_HOP_COUNT 255 #define BABEL_MAX_SEND_INTERVAL 5 #define BABEL_TIME_UNITS 100 /* On-wire times are counted in centiseconds */ - #define BABEL_SEQNO_REQUEST_EXPIRY 60 #define BABEL_GARBAGE_INTERVAL 300 +/* Max interval that will not overflow when carried as 16-bit centiseconds */ +#define BABEL_MAX_INTERVAL (0xFFFF/BABEL_TIME_UNITS) + #define BABEL_OVERHEAD (SIZE_OF_IP_HEADER+UDP_HEADER_LENGTH) #define BABEL_MIN_MTU (512 + BABEL_OVERHEAD) diff --git a/proto/babel/config.Y b/proto/babel/config.Y index e7ce6a93..b6170852 100644 --- a/proto/babel/config.Y +++ b/proto/babel/config.Y @@ -77,17 +77,18 @@ babel_iface_finish: BABEL_IFACE->rxcost = BABEL_RXCOST_WIRED; } + /* Make sure we do not overflow the 16-bit centisec fields */ if (!BABEL_IFACE->update_interval) - BABEL_IFACE->update_interval = BABEL_IFACE->hello_interval*BABEL_UPDATE_INTERVAL_FACTOR; - BABEL_IFACE->ihu_interval = BABEL_IFACE->hello_interval*BABEL_IHU_INTERVAL_FACTOR; + BABEL_IFACE->update_interval = MIN_(BABEL_IFACE->hello_interval*BABEL_UPDATE_INTERVAL_FACTOR, BABEL_MAX_INTERVAL); + BABEL_IFACE->ihu_interval = MIN_(BABEL_IFACE->hello_interval*BABEL_IHU_INTERVAL_FACTOR, BABEL_MAX_INTERVAL); }; babel_iface_item: | PORT expr { BABEL_IFACE->port = $2; if (($2<1) || ($2>65535)) cf_error("Invalid port number"); } | RXCOST expr { BABEL_IFACE->rxcost = $2; if (($2<1) || ($2>65535)) cf_error("Invalid rxcost"); } - | HELLO INTERVAL expr { BABEL_IFACE->hello_interval = $3; if (($3<1) || ($3>65535)) cf_error("Invalid hello interval"); } - | UPDATE INTERVAL expr { BABEL_IFACE->update_interval = $3; if (($3<1) || ($3>65535)) cf_error("Invalid hello interval"); } + | HELLO INTERVAL expr { BABEL_IFACE->hello_interval = $3; if (($3<1) || ($3>BABEL_MAX_INTERVAL)) cf_error("Invalid hello interval"); } + | UPDATE INTERVAL expr { BABEL_IFACE->update_interval = $3; if (($3<1) || ($3>BABEL_MAX_INTERVAL)) cf_error("Invalid update interval"); } | TYPE WIRED { BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRED; } | TYPE WIRELESS { BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRELESS; } | RX BUFFER expr { BABEL_IFACE->rx_buffer = $3; if (($3<256) || ($3>65535)) cf_error("RX buffer must be in range 256-65535"); } -- cgit v1.2.3 From ecae2f43f37df642e5098201a0472802e6a70e78 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Tue, 19 Jul 2016 13:33:02 +0200 Subject: Babel: Rework handling of retractions MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit An update with wildcard AE and infinite metric should be treated as a global retraction of all prefixes announced by that neighbour, per section 4.4.9 of the RFC. In addition, router ID and seqno in retraction updates should be ignored. This reworks the handling of retractions and adjusts the parser to handle all this correctly. Signed-off-by: Toke Høiland-Jørgensen --- proto/babel/babel.c | 82 ++++++++++++++++++++++++++++++++++++--------------- proto/babel/packets.c | 4 ++- 2 files changed, 61 insertions(+), 25 deletions(-) (limited to 'proto/babel') diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 8e104d60..8204838b 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -1040,17 +1040,18 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) struct babel_proto *p = ifa->proto; struct babel_msg_update *msg = &m->update; - struct babel_neighbor *n; + struct babel_neighbor *nbr; struct babel_entry *e; struct babel_source *s; struct babel_route *r; + node *n; int feasible; TRACE(D_PACKETS, "Handling update for %I/%d with seqno %d metric %d", msg->prefix, msg->plen, msg->seqno, msg->metric); - n = babel_find_neighbor(ifa, msg->sender); - if (!n) + nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) { DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender); return; @@ -1095,55 +1096,88 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) * of the Interval value included in the update. */ + /* Retraction */ if (msg->metric == BABEL_INFINITY) - e = babel_find_entry(p, msg->prefix, msg->plen); - else - e = babel_get_entry(p, msg->prefix, msg->plen); + { + if (msg->ae == BABEL_AE_WILDCARD) + { + /* + * Special case: This is a retraction of all prefixes announced by this + * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC). + */ + WALK_LIST(n, nbr->routes) + { + r = SKIP_BACK(struct babel_route, neigh_route, n); + r->metric = BABEL_INFINITY; + babel_select_route(r->e); + } + } + else + { + e = babel_find_entry(p, msg->prefix, msg->plen); - if (!e) + if (!e) + return; + + /* The route entry indexed by neighbour */ + r = babel_find_route(e, nbr); + + if (!r) + return; + + r->metric = BABEL_INFINITY; + babel_select_route(e); + } + + /* Done with retractions */ return; + } + e = babel_get_entry(p, msg->prefix, msg->plen); + r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */ s = babel_find_source(e, msg->router_id); /* for feasibility */ - r = babel_find_route(e, n); /* the route entry indexed by neighbour */ feasible = babel_is_feasible(s, msg->seqno, msg->metric); if (!r) { - if (!feasible || (msg->metric == BABEL_INFINITY)) + if (!feasible) return; - r = babel_get_route(e, n); + r = babel_get_route(e, nbr); r->advert_metric = msg->metric; r->router_id = msg->router_id; - r->metric = babel_compute_metric(n, msg->metric); + r->metric = babel_compute_metric(nbr, msg->metric); r->next_hop = msg->next_hop; r->seqno = msg->seqno; } else if (r == r->e->selected_in && !feasible) { - /* Route is installed and update is infeasible - we may lose the route, so - send a unicast seqno request (section 3.8.2.2 second paragraph). */ + /* + * Route is installed and update is infeasible - we may lose the route, + * so send a unicast seqno request (section 3.8.2.2 second paragraph). + */ babel_unicast_seqno_request(r); - if (msg->router_id == r->router_id) return; - r->metric = BABEL_INFINITY; /* retraction */ + if (msg->router_id == r->router_id) + return; + + /* Treat as retraction */ + r->metric = BABEL_INFINITY; } else { /* Last paragraph above - update the entry */ r->advert_metric = msg->metric; - r->metric = babel_compute_metric(n, msg->metric); - r->router_id = msg->router_id; + r->metric = babel_compute_metric(nbr, msg->metric); r->next_hop = msg->next_hop; + + r->router_id = msg->router_id; r->seqno = msg->seqno; - if (msg->metric != BABEL_INFINITY) - { - r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval); - r->expires = now + r->expiry_interval; - if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL) - r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL; - } + r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval); + r->expires = now + r->expiry_interval; + if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL) + r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL; /* If the route is not feasible at this point, it means it is from another neighbour than the one currently selected; so send a unicast seqno diff --git a/proto/babel/packets.c b/proto/babel/packets.c index be47aa75..d0cc613e 100644 --- a/proto/babel/packets.c +++ b/proto/babel/packets.c @@ -480,6 +480,7 @@ babel_read_update(struct babel_tlv *hdr, union babel_msg *m, if (tlv->plen > 0) return PARSE_ERROR; + msg->plen = 0; msg->prefix = IPA_NONE; break; @@ -523,7 +524,8 @@ babel_read_update(struct babel_tlv *hdr, union babel_msg *m, return PARSE_IGNORE; } - if (!state->router_id_seen) + /* Update must have Router ID, unless it is retraction */ + if (!state->router_id_seen && (msg->metric != BABEL_INFINITY)) { DBG("Babel: No router ID seen before update\n"); return PARSE_ERROR; -- cgit v1.2.3 From 5d6ca220850c615126ea6820f8c05528269feec6 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Tue, 19 Jul 2016 14:23:41 +0200 Subject: Babel: Send wildcard retractions on shutdown and startup MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This makes BIRD send a wildcard retraction on all interfaces before shutting down and right after starting up. This helps ensure that neighbours will discard the announced routes as soon as possible, rather than only after the normal timeout procedures. Signed-off-by: Toke Høiland-Jørgensen --- proto/babel/babel.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++---- proto/babel/babel.h | 2 +- proto/babel/packets.c | 25 ++++++++++++++++++------- 3 files changed, 65 insertions(+), 12 deletions(-) (limited to 'proto/babel') diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 8204838b..67e1d8be 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -834,8 +834,8 @@ babel_send_retraction(struct babel_iface *ifa, ip_addr prefix, int plen) struct babel_proto *p = ifa->proto; union babel_msg msg = {}; - TRACE(D_PACKETS, "Sending retraction for %I/%d router-id %lR seqno %d", - prefix, plen, p->router_id, p->update_seqno); + TRACE(D_PACKETS, "Sending retraction for %I/%d seqno %d", + prefix, plen, p->update_seqno); msg.type = BABEL_TLV_UPDATE; msg.update.plen = plen; @@ -843,7 +843,23 @@ babel_send_retraction(struct babel_iface *ifa, ip_addr prefix, int plen) msg.update.seqno = p->update_seqno; msg.update.metric = BABEL_INFINITY; msg.update.prefix = prefix; - msg.update.router_id = p->router_id; + + babel_enqueue(&msg, ifa); +} + +static void +babel_send_wildcard_retraction(struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + union babel_msg msg = {}; + + TRACE(D_PACKETS, "Sending wildcard retraction on %s", ifa->ifname); + + msg.type = BABEL_TLV_UPDATE; + msg.update.wildcard = 1; + msg.update.interval = ifa->cf->update_interval; + msg.update.seqno = p->update_seqno; + msg.update.metric = BABEL_INFINITY; babel_enqueue(&msg, ifa); } @@ -1099,7 +1115,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) /* Retraction */ if (msg->metric == BABEL_INFINITY) { - if (msg->ae == BABEL_AE_WILDCARD) + if (msg->wildcard) { /* * Special case: This is a retraction of all prefixes announced by this @@ -1347,6 +1363,7 @@ babel_iface_start(struct babel_iface *ifa) ifa->up = 1; babel_send_hello(ifa, 0); + babel_send_wildcard_retraction(ifa); babel_send_wildcard_request(ifa); babel_send_update(ifa, 0); /* Full update */ } @@ -2056,6 +2073,30 @@ babel_start(struct proto *P) return PS_UP; } +static inline void +babel_iface_shutdown(struct babel_iface *ifa) +{ + if (ifa->sk) + { + babel_send_wildcard_retraction(ifa); + babel_send_queue(ifa); + } +} + +static int +babel_shutdown(struct proto *P) +{ + struct babel_proto *p = (void *) P; + struct babel_iface *ifa; + + TRACE(D_EVENTS, "Shutdown requested"); + + WALK_LIST(ifa, p->interfaces) + babel_iface_shutdown(ifa); + + return PS_DOWN; +} + static int babel_reconfigure(struct proto *P, struct proto_config *c) { @@ -2083,6 +2124,7 @@ struct protocol proto_babel = { .init = babel_init, .dump = babel_dump, .start = babel_start, + .shutdown = babel_shutdown, .reconfigure = babel_reconfigure, .get_route_info = babel_get_route_info, .get_attr = babel_get_attr diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 7b5037ab..481c88a7 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -268,7 +268,7 @@ struct babel_msg_ihu { struct babel_msg_update { u8 type; - u8 ae; + u8 wildcard; u8 plen; u16 interval; u16 seqno; diff --git a/proto/babel/packets.c b/proto/babel/packets.c index d0cc613e..65dd6853 100644 --- a/proto/babel/packets.c +++ b/proto/babel/packets.c @@ -462,7 +462,6 @@ babel_read_update(struct babel_tlv *hdr, union babel_msg *m, struct babel_msg_update *msg = &m->update; msg->type = BABEL_TLV_UPDATE; - msg->ae = tlv->ae; msg->interval = get_time16(&tlv->interval); msg->seqno = get_u16(&tlv->seqno); msg->metric = get_u16(&tlv->metric); @@ -480,8 +479,7 @@ babel_read_update(struct babel_tlv *hdr, union babel_msg *m, if (tlv->plen > 0) return PARSE_ERROR; - msg->plen = 0; - msg->prefix = IPA_NONE; + msg->wildcard = 1; break; case BABEL_AE_IP4: @@ -550,8 +548,11 @@ babel_write_update(struct babel_tlv *hdr, union babel_msg *m, * When needed, we write Router-ID TLV before Update TLV and return size of * both of them. There is enough space for the Router-ID TLV, because * sizeof(struct babel_tlv_router_id) == sizeof(struct babel_tlv_update). + * + * Router ID is not used for retractions, so do not us it in such case. */ - if (!state->router_id_seen || (msg->router_id != state->router_id)) + if ((msg->metric < BABEL_INFINITY) && + (!state->router_id_seen || (msg->router_id != state->router_id))) { len0 = babel_write_router_id(hdr, msg->router_id, state, max_len); tlv = (struct babel_tlv_update *) NEXT_TLV(tlv); @@ -564,12 +565,22 @@ babel_write_update(struct babel_tlv *hdr, union babel_msg *m, memset(tlv, 0, sizeof(struct babel_tlv_update)); TLV_HDR(tlv, BABEL_TLV_UPDATE, len); - tlv->ae = BABEL_AE_IP6; - tlv->plen = msg->plen; + + if (msg->wildcard) + { + tlv->ae = BABEL_AE_WILDCARD; + tlv->plen = 0; + } + else + { + tlv->ae = BABEL_AE_IP6; + tlv->plen = msg->plen; + put_ip6_px(tlv->addr, msg->prefix, msg->plen); + } + put_time16(&tlv->interval, msg->interval); put_u16(&tlv->seqno, msg->seqno); put_u16(&tlv->metric, msg->metric); - put_ip6_px(tlv->addr, msg->prefix, msg->plen); return len0 + len; } -- cgit v1.2.3 From 0f673666017bfc9c05c9495ae53bc323b9dc6660 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Tue, 19 Jul 2016 14:28:53 +0200 Subject: Babel: Do not keep an infeasible route as selected MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit When a route becomes infeasible it should not be kept as selected; this is forbidden by section 3.6 of the RFC and prevents subsequent updates from the same router ID from replacing it. Signed-off-by: Toke Høiland-Jørgensen --- proto/babel/babel.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'proto/babel') diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 67e1d8be..3b3b9870 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -565,6 +565,11 @@ babel_select_route(struct babel_entry *e) babel_send_seqno_request(e); babel_announce_rte(p, e); + + /* Section 3.6 of the RFC forbids an infeasible from being selected. This + is cleared after announcing the route to the core to make sure an + unreachable route is propagated first. */ + e->selected_in = NULL; } else { -- cgit v1.2.3 From c6ed5a0f9925476714d6b351c61dbce704a4f09d Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Tue, 19 Jul 2016 14:38:36 +0200 Subject: Babel: Do not maintain feasibility distance for our own routes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit We do not need to maintain feasibility distances for our own router ID (we ignore the updates anyway). Not doing so makes the routes be garbage collected sooner when export filters change. Signed-off-by: Toke Høiland-Jørgensen --- proto/babel/babel.c | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-) (limited to 'proto/babel') diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 3b3b9870..8164f2f3 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -788,16 +788,21 @@ babel_send_update(struct babel_iface *ifa, bird_clock_t changed) msg.update.prefix = e->n.prefix; msg.update.router_id = r->router_id; - /* Update feasibility distance */ - struct babel_source *s = babel_get_source(e, r->router_id); - s->expires = now + BABEL_GARBAGE_INTERVAL; - if ((msg.update.seqno > s->seqno) || - ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric))) + babel_enqueue(&msg, ifa); + + /* Update feasibility distance for redistributed routes */ + if (!OUR_ROUTE(r)) { - s->seqno = msg.update.seqno; - s->metric = msg.update.metric; + struct babel_source *s = babel_get_source(e, r->router_id); + s->expires = now + BABEL_GARBAGE_INTERVAL; + + if ((msg.update.seqno > s->seqno) || + ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric))) + { + s->seqno = msg.update.seqno; + s->metric = msg.update.metric; + } } - babel_enqueue(&msg, ifa); } FIB_WALK_END; } -- cgit v1.2.3 From 13a31a4001e02ea7c84d26cbeaaa9fea816736f7 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Wed, 20 Jul 2016 15:55:45 +0200 Subject: Babel: Immediately update hello interval on interface reconfigure MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit An interface reconfiguration may change both the hello and update intervals. An update interval change is immediately put into effect, while a hello interval change is not. This also updates the hello interval immediately (if the new interval is shorter than the old one), and sends a hello to notify peers of the change. Signed-off-by: Toke Høiland-Jørgensen --- proto/babel/babel.c | 3 +++ 1 file changed, 3 insertions(+) (limited to 'proto/babel') diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 8164f2f3..9d73a264 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -1590,6 +1590,9 @@ babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct b ifa->cf = new; + if (ifa->next_hello > (now + new->hello_interval)) + ifa->next_hello = now + (random() % new->hello_interval) + 1; + if (ifa->next_regular > (now + new->update_interval)) ifa->next_regular = now + (random() % new->update_interval) + 1; -- cgit v1.2.3