Change lde_check_request(), lde_check_mapping(), lde_send_labelmapping(),

lde_send_labelrequest(), and lde_nbr_do_mappings() to follow the
algorithms defined in Appendix A of RFC 5036. Added comments and
markers for better understanding and to find missing bits.
OK michele@

3 files changed, 165 insertions, 113 deletions

diff --git a/usr.sbin/ldpd/lde.c b/usr.sbin/ldpd/lde.c
index 94aeea73317..eec2a492611 100644
--- a/usr.sbin/ldpd/lde.c
+++ b/usr.sbin/ldpd/lde.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lde.c,v 1.21 2010/10/21 08:24:06 claudio Exp $ */
+/*	$OpenBSD: lde.c,v 1.22 2010/10/26 12:08:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org>
@@ -474,29 +474,84 @@ lde_send_delete_klabel(struct rt_node *rr, struct rt_lsp *rl)
 }
 
 void
-lde_send_labelrequest(u_int32_t peerid, struct map *map)
+lde_send_labelrequest(struct lde_nbr *ln, struct rt_node *rn)
 {
-	imsg_compose_event(iev_ldpe, IMSG_REQUEST_ADD, peerid, 0,
-	     -1, map, sizeof(*map));
-	imsg_compose_event(iev_ldpe, IMSG_REQUEST_ADD_END, peerid, 0,
+	struct map	 map;
+
+	/* TODO check if status of peer is OK to send requests (SLRq.2 & 6)
+	 * For now assume no peer will send no-label-resource notifications */
+
+	/* check if request is already pending */
+	if (fec_find(&ln->sent_req, &rn->fec) != NULL)
+		return;
+	/* and try to add request to pending list */
+	lde_req_add(ln, &rn->fec, 1);
+	/* msgid does not matter since only one req can be pending */
+
+	bzero(&map, sizeof(map));
+	map.prefix = rn->fec.prefix;
+	map.prefixlen = rn->fec.prefixlen;
+
+	imsg_compose_event(iev_ldpe, IMSG_REQUEST_ADD, ln->peerid, 0,
+	     -1, &map, sizeof(map));
+	imsg_compose_event(iev_ldpe, IMSG_REQUEST_ADD_END, ln->peerid, 0,
 	     -1, NULL, 0);
 }
 
 void
-lde_send_labelmapping(u_int32_t peerid, struct map *map)
+lde_send_labelmapping(struct lde_nbr *ln, struct rt_node *rn)
 {
-	imsg_compose_event(iev_ldpe, IMSG_MAPPING_ADD, peerid, 0,
-	     -1, map, sizeof(*map));
-	imsg_compose_event(iev_ldpe, IMSG_MAPPING_ADD_END, peerid, 0,
+	struct lde_req	*lre;
+	struct lde_map	*me;
+	struct map	 map;
+
+	/*
+	 * This function skips SL.1 - 3 and SL.9 - 14 because the lable
+	 * allocation is done way earlier (because of the merging nature of
+	 * ldpd).
+	 */
+
+	bzero(&map, sizeof(map));
+	map.label = rn->local_label;
+	map.prefix = rn->fec.prefix;
+	map.prefixlen = rn->fec.prefixlen;
+
+	/* is there a pending request for this mapping? */
+	lre = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
+	if (lre) {
+		/* set label request msg id in the mapping response. */
+		map.requestid = lre->msgid;
+		map.flags = F_MAP_REQ_ID;
+		lde_req_del(ln, lre, 0);
+	}
+
+	me = (struct lde_map *)fec_find(&ln->sent_map, &rn->fec);
+	if (me == NULL)
+		me = lde_map_add(ln, rn, 1);
+	me->label = map.label;
+
+	imsg_compose_event(iev_ldpe, IMSG_MAPPING_ADD, ln->peerid, 0,
+	     -1, &map, sizeof(map));
+	imsg_compose_event(iev_ldpe, IMSG_MAPPING_ADD_END, ln->peerid, 0,
 	     -1, NULL, 0);
 }
 
 void
-lde_send_labelrelease(u_int32_t peerid, struct map *map)
+lde_send_labelrelease(struct lde_nbr *ln, struct rt_node *rn, u_int32_t label)
 {
-	imsg_compose_event(iev_ldpe, IMSG_RELEASE_ADD, peerid, 0,
-	    -1, map, sizeof(*map));
-	imsg_compose_event(iev_ldpe, IMSG_RELEASE_ADD_END, peerid, 0,
+	struct map	 map;
+
+	bzero(&map, sizeof(map));
+	map.prefix = rn->fec.prefix;
+	map.prefixlen = rn->fec.prefixlen;
+	if (label != NO_LABEL) {
+		map.flags = F_MAP_OPTLABEL;
+		map.label = label;
+	}
+	
+	imsg_compose_event(iev_ldpe, IMSG_RELEASE_ADD, ln->peerid, 0,
+	    -1, &map, sizeof(map));
+	imsg_compose_event(iev_ldpe, IMSG_RELEASE_ADD_END, ln->peerid, 0,
 	    -1, NULL, 0);
 }
 
@@ -599,54 +654,31 @@ lde_nbr_clear(void)
 void
 lde_nbr_do_mappings(struct rt_node *rn)
 {
-	struct map	 map;
 	struct lde_nbr	*ln;
-	struct lde_map	*lm;
-	struct lde_req	*lr;
-	struct rt_lsp	*rl;
+	struct lde_map	*me;
+	struct lde_req	*lre;
 
-	map.label = rn->local_label;
-	map.prefix = rn->fec.prefix;
-	map.prefixlen = rn->fec.prefixlen;
+	/* This handles LMp.17-31 for lde_check_mapping() */
 
 	RB_FOREACH(ln, nbr_tree, &lde_nbrs) {
-		/* Did we already send a mapping to this peer? */
-		lm = (struct lde_map *)fec_find(&ln->sent_map, &rn->fec);
-		if (lm && lm->label == map.label) {
+		/* LMp.18 Did we already send a mapping to this peer? */
+		me = (struct lde_map *)fec_find(&ln->sent_map, &rn->fec);
+		if (me && me->label == rn->local_label)
 			/* same mapping already sent, skip */
+			/* TODO LMp.22-27 Loop detection check */
 			continue;
-		}
 
-		/* Is this from a pending request? */
-		lr = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
-		if (ldeconf->mode & MODE_ADV_ONDEMAND && lr == NULL)
+		/* LMp.28 Is this from a pending request? */
+		lre = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
+
+		/* Check for the only case where no mapping should be sent.
+		 * This is the On Demand case of LMp.29  */
+		if (ldeconf->mode & MODE_ADV_ONDEMAND && lre == NULL)
 			/* adv. on demand but no req pending, skip */
 			continue;
 
-		if (ldeconf->mode & MODE_DIST_ORDERED) {
-			/* ordered mode needs the downstream path to be
-			 * ready before we can send the mapping upstream */
-			LIST_FOREACH(rl, &rn->lsp, entry) {
-				if (rl->remote_label != NO_LABEL)
-					/* at least on LSP exists */
-					break;
-			}
-			if (rl == NULL)
-				continue;
-		}
-
-		if (lr) {
-			/* set label request msg id in the mapping response. */
-			map.requestid = lr->msgid;
-			map.flags = F_MAP_REQ_ID;
-			fec_remove(&ln->sent_req, &lr->fec);
-		}
-
-		if (lm == NULL)
-			lm = lde_map_add(ln, rn, 1);
-		lm->label = map.label;
-
-		lde_send_labelmapping(ln->peerid, &map);
+		lde_send_labelmapping(ln, rn);
+		/* LMp.30 & 31 are not needed because labels are always added */
 	}
 }
 
@@ -667,6 +699,7 @@ lde_map_add(struct lde_nbr *ln, struct rt_node *rn, int sent)
 		if (fec_insert(&ln->sent_map, &me->fec))
 			log_warnx("failed to add %s/%u to sent map",
 			    inet_ntoa(me->fec.prefix), me->fec.prefixlen);
+			/* XXX on failure more cleanup is needed */
 	} else {
 		LIST_INSERT_HEAD(&rn->downstream, me, entry);
 		if (fec_insert(&ln->recv_map, &me->fec))
@@ -697,6 +730,41 @@ lde_map_free(void *ptr)
 	free(map);
 }
 
+struct lde_req *
+lde_req_add(struct lde_nbr *ln, struct fec *fec, int sent)
+{
+	struct fec_tree	*ft;
+	struct lde_req	*lre;
+
+	ft = sent ? &ln->sent_req : &ln->recv_req;
+
+	lre = calloc(1, sizeof(*lre));
+	if (lre != NULL) {
+		lre->fec = *fec;
+
+		if (fec_insert(ft, &lre->fec)) {
+			log_warnx("failed to add %s/%u to %s req",
+			    inet_ntoa(lre->fec.prefix), lre->fec.prefixlen,
+			    sent ? "sent" : "recv");
+			free(lre);
+			return (NULL);
+		}
+	}
+
+	return (lre);
+}
+
+void
+lde_req_del(struct lde_nbr *ln, struct lde_req *lre, int sent)
+{
+	if (sent)
+		fec_remove(&ln->sent_req, &lre->fec);
+	else
+		fec_remove(&ln->recv_req, &lre->fec);
+	
+	free(lre);
+}
+
 int
 lde_address_add(struct lde_nbr *lr, struct in_addr *addr)
 {
diff --git a/usr.sbin/ldpd/lde.h b/usr.sbin/ldpd/lde.h
index a36c6385c3f..4ef44e90de1 100644
--- a/usr.sbin/ldpd/lde.h
+++ b/usr.sbin/ldpd/lde.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lde.h,v 1.16 2010/10/21 08:24:06 claudio Exp $ */
+/*	$OpenBSD: lde.h,v 1.17 2010/10/26 12:08:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -100,18 +100,20 @@ struct rt_node {
 pid_t		lde(struct ldpd_conf *, int [2], int [2], int [2]);
 int		lde_imsg_compose_ldpe(int, u_int32_t, pid_t, void *, u_int16_t);
 u_int32_t	lde_assign_label(void);
-void		lde_send_change_klabel(struct rt_node *, struct rt_lsp *);
-void		lde_send_delete_klabel(struct rt_node *, struct rt_lsp *);
-void		lde_send_labelmapping(u_int32_t, struct map *);
-void		lde_send_labelrequest(u_int32_t, struct map *);
-void		lde_send_labelrelease(u_int32_t, struct map *);
-void		lde_send_notification(u_int32_t, u_int32_t, u_int32_t,
-		   u_int32_t);
+
+void	lde_send_change_klabel(struct rt_node *, struct rt_lsp *);
+void	lde_send_delete_klabel(struct rt_node *, struct rt_lsp *);
+void	lde_send_labelmapping(struct lde_nbr *, struct rt_node *);
+void	lde_send_labelrequest(struct lde_nbr *, struct rt_node *);
+void	lde_send_labelrelease(struct lde_nbr *, struct rt_node *, u_int32_t);
+void	lde_send_notification(u_int32_t, u_int32_t, u_int32_t, u_int32_t);
 
 void		lde_nbr_del(struct lde_nbr *);
 void		lde_nbr_do_mappings(struct rt_node *);
 struct lde_map *lde_map_add(struct lde_nbr *, struct rt_node *, int);
 void		lde_map_del(struct lde_nbr *, struct lde_map *, int);
+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_nbr *lde_find_address(struct in_addr);
 
 
diff --git a/usr.sbin/ldpd/lde_lib.c b/usr.sbin/ldpd/lde_lib.c
index 81647de6ecf..da78b53b4e9 100644
--- a/usr.sbin/ldpd/lde_lib.c
+++ b/usr.sbin/ldpd/lde_lib.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lde_lib.c,v 1.27 2010/10/21 08:24:06 claudio Exp $ */
+/*	$OpenBSD: lde_lib.c,v 1.28 2010/10/26 12:08:14 claudio Exp $ */
 
 /*
  * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
@@ -375,42 +375,45 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 
 	/* first check if we have a pending request running */
 	lre = (struct lde_req *)fec_find(&ln->sent_req, &rn->fec);
-	if (lre) {
-		fec_remove(&ln->sent_req, &lre->fec);
-		free(lre);
-	}
+	if (lre)
+		lde_req_del(ln, lre, 1);
 
 	/* TODO Loop detection LMp.3 - LMp.8 */
 
 	LIST_FOREACH(me, &rn->downstream, entry) {
-		if (ln == me->nexthop) {
-			if (me->label == map->label) {
-				/* Duplicate: RFC says to send back a release,
-				 * even though we did not release the actual
-				 * mapping. This is confusing.
-				 */
-				log_debug("duplicate FEC %s, label %u",
-				    log_fec(map), map->label);
-				lde_send_labelrelease(ln->peerid, map);
-				return;
-			}
-			/* old mapping that is now changed */
+		if (ln != me->nexthop)				/* LMp.9 */
+			continue;
+		if (lre)
+			/* LMp.10 Note 6: req. mappings are always new */
 			break;
+		if (me->label != map->label) {			/* LMp.10 */
+			/*
+			 * This is, according to the RFC, a try to install a
+			 * multipath LSP which is not supported by the RFC.
+			 * So instead release the old label and install the
+			 * new one.
+			 */
+			log_debug("possible multipath FEC %s, "
+			    "label %u, old label %u",
+			    log_fec(map), map->label, me->label);
+			lde_send_labelrelease(ln, rn, me->label);
 		}
+		/* there can only be one mapping */
+		break;
 	}
 
+	/* LMp.11: get nexthop */
 	LIST_FOREACH(rl, &rn->lsp, entry) {
 		addr = lde_address_find(ln, &rl->nexthop);
 		if (addr)
 			break;
 	}
-
 	if (addr == NULL) {
-		/* route not yet available */
+		/* route not yet available LMp.13 */
 		if (ldeconf->mode & MODE_RET_CONSERVATIVE) {
 			log_debug("FEC %s: conservative ret but no route",
 			    log_fec(map));
-			lde_send_labelrelease(ln->peerid, map);
+			lde_send_labelrelease(ln, rn, map->label);
 			return;
 		}
 		/* in liberal mode just note the mapping */
@@ -421,16 +424,18 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 		return;
 	}
 
+	/* LMp.14 do we actually need this FEC for now this is always true */
 	rl->remote_label = map->label;
 
-	/* Record the mapping from this peer */	
+	/* LMp.15 install FEC in FIB */
+	lde_send_change_klabel(rn, rl);
+
+	/* Record the mapping from this peer LMp.16 */	
 	if (me == NULL)
 		me = lde_map_add(ln, rn, 0);
 	me->label = map->label;
 
-	lde_send_change_klabel(rn, rl);
-
-	/* Redistribute the current mapping to every nbr */
+	/* Redistribute the current mapping to every nbr LMp.17-31 */
 	lde_nbr_do_mappings(rn);
 }
 
@@ -441,8 +446,6 @@ lde_check_request(struct map *map, struct lde_nbr *ln)
 	struct rt_node	*rn;
 	struct rt_lsp	*rl;
 	struct lde_nbr	*lnn;
-	struct lde_map	*me;
-	struct map	 localmap;
 
 	log_debug("label request from nbr %s, FEC %s",
 	    inet_ntoa(ln->id), log_fec(map));
@@ -470,46 +473,25 @@ lde_check_request(struct map *map, struct lde_nbr *ln)
 	lre = (struct lde_req *)fec_find(&ln->recv_req, &rn->fec);
 	if (lre != NULL)
 		return;
+	/* else record label request */
+	lre = lde_req_add(ln, &rn->fec, 0);
+	if (lre != NULL)
+		lre->msgid = map->messageid;
 
 	/* there is a valid mapping available */
 	if (rl != NULL) {
-		bzero(&localmap, sizeof(localmap));
-		localmap.prefix = map->prefix;
-		localmap.prefixlen = map->prefixlen;
-		localmap.label = rn->local_label;
-
-		me = lde_map_add(ln, rn, 1);
-		me->label = rn->local_label;
-
 		/* TODO loop protection handling (LRq.9) */
-		lde_send_labelmapping(ln->peerid, &localmap);
+		lde_send_labelmapping(ln, rn);
 		return;
 	}
 
-	/* else record label request */
-	lre = calloc(1, sizeof(*lre));
-	if (lre == NULL)
-		fatal("lde_check_request");
-
-	lre->fec = rn->fec;
-	lre->msgid = map->messageid;
-
-	if (fec_insert(&ln->recv_req, &lre->fec)) {
-		log_warnx("failed to add %s/%u to recv req",
-		    inet_ntoa(lre->fec.prefix), lre->fec.prefixlen);
-		free(lre);
-	}
-
-	/* XXX  map should not be * reused, especially the messageid */
 	/* no mapping available, try to request */
 	/* XXX depending on the request behaviour we could return here */
 	LIST_FOREACH(rl, &rn->lsp, entry) {
 		lnn = lde_find_address(rl->nexthop);
 		if (lnn == NULL)
 			continue;
-
-		/* TODO record request on the sent_req list of lnn */
-		lde_send_labelrequest(lnn->peerid, map);
+		lde_send_labelrequest(lnn, rn);
 	}
 }
 
@@ -563,7 +545,7 @@ lde_check_withdraw(struct map *map, struct lde_nbr *ln)
 	rn = (struct rt_node *)fec_find_prefix(&rt, map->prefix.s_addr,
 	    map->prefixlen);
 
-	lde_send_labelrelease(ln->peerid, map);
+	lde_send_labelrelease(ln, rn, map->label);
 
 	if (rn == NULL)
 		/* LSP not available, nothing to do */