ldpd: schedule the sending of label messages when necessary

Once we send a Label Withdraw, we can't send a Label Mapping for the
same FEC until we receive a Label Release from the peer. This is due to
some limitations in the LDP algorithms described in Appendix A. ("LDP
Label Distribution Procedures") of RFC 5036.

To workaround this issue, make it possible to schedule the sending of
a Label Mapping as soon as a Label Release is received for the same FEC.

The easiest way to test this patch is by typing the "label local advertise
explicit-null" command. ldpd will withdraw all null labels using a
Wildcard FEC and then send new Label Mappings as soon the corresponding
Label Releases are received.

Signed-off-by: Renato Westphal <renato@opensourcerouting.org>

3 files changed, 72 insertions, 14 deletions

diff --git a/ldpd/lde.c b/ldpd/lde.c
index 1c7458ce7..e5d140283 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -917,10 +917,23 @@ lde_map2fec(struct map *map, struct in_addr lsr_id, struct fec *fec)
 void
 lde_send_labelmapping(struct lde_nbr *ln, struct fec_node *fn, int single)
 {
-	struct lde_req	*lre;
-	struct lde_map	*me;
-	struct map	 map;
-	struct l2vpn_pw	*pw;
+	struct lde_wdraw	*lw;
+	struct lde_map		*me;
+	struct lde_req		*lre;
+	struct map		 map;
+	struct l2vpn_pw		*pw;
+
+	/*
+	 * We shouldn't send a new label mapping if we have a pending
+	 * label release to receive. In this case, schedule to send a
+	 * label mapping as soon as a label release is received.
+	 */
+	lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
+	if (lw) {
+		if (!fec_find(&ln->sent_map_pending, &fn->fec))
+			lde_map_pending_add(ln, fn);
+		return;
+	}
 
 	/*
 	 * This function skips SL.1 - 3 and SL.9 - 14 because the label
@@ -1226,6 +1239,7 @@ lde_nbr_new(uint32_t peerid, struct lde_nbr *new)
 	ln->peerid = peerid;
 	fec_init(&ln->recv_map);
 	fec_init(&ln->sent_map);
+	fec_init(&ln->sent_map_pending);
 	fec_init(&ln->recv_req);
 	fec_init(&ln->sent_req);
 	fec_init(&ln->sent_wdraw);
@@ -1281,6 +1295,7 @@ lde_nbr_del(struct lde_nbr *ln)
 
 	fec_clear(&ln->recv_map, lde_map_free);
 	fec_clear(&ln->sent_map, lde_map_free);
+	fec_clear(&ln->sent_map_pending, free);
 	fec_clear(&ln->recv_req, free);
 	fec_clear(&ln->sent_req, free);
 	fec_clear(&ln->sent_wdraw, free);
@@ -1431,6 +1446,30 @@ lde_map_free(void *ptr)
 	free(map);
 }
 
+struct fec *
+lde_map_pending_add(struct lde_nbr *ln, struct fec_node *fn)
+{
+	struct fec	*map;
+
+	map = calloc(1, sizeof(*map));
+	if (map == NULL)
+		fatal(__func__);
+
+	*map = fn->fec;
+	if (fec_insert(&ln->sent_map_pending, map))
+		log_warnx("failed to add %s to sent map (pending)",
+		    log_fec(map));
+
+	return (map);
+}
+
+void
+lde_map_pending_del(struct lde_nbr *ln, struct fec *map)
+{
+	fec_remove(&ln->sent_map_pending, map);
+	free(map);
+}
+
 struct lde_req *
 lde_req_add(struct lde_nbr *ln, struct fec *fec, int sent)
 {
diff --git a/ldpd/lde.h b/ldpd/lde.h
index c1d66f9ff..1cce48383 100644
--- a/ldpd/lde.h
+++ b/ldpd/lde.h
@@ -95,6 +95,7 @@ struct lde_nbr {
 	struct fec_tree		 sent_req;
 	struct fec_tree		 recv_map;
 	struct fec_tree		 sent_map;
+	struct fec_tree		 sent_map_pending;
 	struct fec_tree		 sent_wdraw;
 	TAILQ_HEAD(, lde_addr)	 addr_list;
 };
@@ -171,6 +172,8 @@ struct lde_nbr	*lde_nbr_find_by_lsrid(struct in_addr);
 struct lde_nbr	*lde_nbr_find_by_addr(int, union ldpd_addr *);
 struct lde_map	*lde_map_add(struct lde_nbr *, struct fec_node *, int);
 void		 lde_map_del(struct lde_nbr *, struct lde_map *, int);
+struct fec 	*lde_map_pending_add(struct lde_nbr *, struct fec_node *);
+void		 lde_map_pending_del(struct lde_nbr *, struct fec *);
 struct lde_req	*lde_req_add(struct lde_nbr *, struct fec *, int);
 void		 lde_req_del(struct lde_nbr *, struct lde_req *, int);
 struct lde_wdraw *lde_wdraw_add(struct lde_nbr *, struct fec_node *);
diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c
index b074bf349..37a670bc8 100644
--- a/ldpd/lde_lib.c
+++ b/ldpd/lde_lib.c
@@ -662,6 +662,7 @@ lde_check_release(struct map *map, struct lde_nbr *ln)
 	struct fec_node		*fn;
 	struct lde_wdraw	*lw;
 	struct lde_map		*me;
+	struct fec		*pending_map;
 
 	/* wildcard label release */
 	if (map->type == MAP_TYPE_WILDCARD ||
@@ -677,17 +678,24 @@ lde_check_release(struct map *map, struct lde_nbr *ln)
 	if (fn == NULL)
 		return;
 
+	/* LRl.6: check sent map list and remove it if available */
+	me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
+	if (me && (map->label == NO_LABEL || map->label == me->map.label))
+		lde_map_del(ln, me, 1);
+
 	/* LRl.3: first check if we have a pending withdraw running */
 	lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
 	if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
 		/* LRl.4: delete record of outstanding label withdraw */
 		lde_wdraw_del(ln, lw);
-	}
 
-	/* LRl.6: check sent map list and remove it if available */
-	me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
-	if (me && (map->label == NO_LABEL || map->label == me->map.label))
-		lde_map_del(ln, me, 1);
+		/* send pending label mapping if any */
+		pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
+		if (pending_map) {
+			lde_send_labelmapping(ln, fn, 1);
+			lde_map_pending_del(ln, pending_map);
+		}
+	}
 
 	/*
 	 * LRl.11 - 13 are unnecessary since we remove the label from
@@ -702,6 +710,7 @@ lde_check_release_wcard(struct map *map, struct lde_nbr *ln)
 	struct fec_node		*fn;
 	struct lde_wdraw	*lw;
 	struct lde_map		*me;
+	struct fec		*pending_map;
 
 	RB_FOREACH(f, fec_tree, &ft) {
 		fn = (struct fec_node *)f;
@@ -711,17 +720,24 @@ lde_check_release_wcard(struct map *map, struct lde_nbr *ln)
 		if (lde_wildcard_apply(map, &fn->fec, me) == 0)
 			continue;
 
+		/* LRl.6: check sent map list and remove it if available */
+		if (me &&
+		    (map->label == NO_LABEL || map->label == me->map.label))
+			lde_map_del(ln, me, 1);
+
 		/* LRl.3: first check if we have a pending withdraw running */
 		lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
 		if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
 			/* LRl.4: delete record of outstanding lbl withdraw */
 			lde_wdraw_del(ln, lw);
-		}
 
-		/* LRl.6: check sent map list and remove it if available */
-		if (me &&
-		    (map->label == NO_LABEL || map->label == me->map.label))
-			lde_map_del(ln, me, 1);
+			/* send pending label mapping if any */
+			pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
+			if (pending_map) {
+				lde_send_labelmapping(ln, fn, 1);
+				lde_map_pending_del(ln, pending_map);
+			}
+		}
 
 		/*
 		 * LRl.11 - 13 are unnecessary since we remove the label from