[mirror_frr.git] / lib / srcdest_table.c

/*
 * SRC-DEST Routing Table
 *
 * Copyright (C) 2017 by David Lamparter & Christian Franke,
 *                       Open Source Routing / NetDEF Inc.
 *
 * This file is part of FreeRangeRouting (FRR)
 *
 * FRR is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * FRR is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <zebra.h>

#include "srcdest_table.h"

#include "memory.h"
#include "prefix.h"
#include "table.h"

DEFINE_MTYPE_STATIC(LIB, ROUTE_SRC_NODE, "Route source node")

/* ----- functions to manage rnodes _with_ srcdest table ----- */
struct srcdest_rnode {
	/* must be first in structure for casting to/from route_node */
	ROUTE_NODE_FIELDS;

	struct route_table *src_table;
};

static struct srcdest_rnode *srcdest_rnode_from_rnode(struct route_node *rn)
{
	assert(rnode_is_dstnode(rn));
	return (struct srcdest_rnode *)rn;
}

static struct route_node *srcdest_rnode_to_rnode(struct srcdest_rnode *srn)
{
	return (struct route_node *)srn;
}

static struct route_node *srcdest_rnode_create(route_table_delegate_t *delegate,
					       struct route_table *table)
{
	struct srcdest_rnode *srn;
	srn = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct srcdest_rnode));
	return srcdest_rnode_to_rnode(srn);
}

static void srcdest_rnode_destroy(route_table_delegate_t *delegate,
				  struct route_table *table,
				  struct route_node *rn)
{
	struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
	struct route_table *src_table;

	/* Clear route node's src_table here already, otherwise the
	 * deletion of the last node in the src_table will trigger
	 * another call to route_table_finish for the src_table.
	 *
	 * (Compare with srcdest_srcnode_destroy)
	 */
	src_table = srn->src_table;
	srn->src_table = NULL;
	route_table_finish(src_table);
	XFREE(MTYPE_ROUTE_NODE, rn);
}

route_table_delegate_t _srcdest_dstnode_delegate = {
	.create_node = srcdest_rnode_create,
	.destroy_node = srcdest_rnode_destroy};

/* ----- functions to manage rnodes _in_ srcdest table ----- */

/* node creation / deletion for srcdest source prefix nodes.
 * the route_node isn't actually different from the normal route_node,
 * but the cleanup is special to free the table (and possibly the
 * destination prefix's route_node) */

static struct route_node *
srcdest_srcnode_create(route_table_delegate_t *delegate,
		       struct route_table *table)
{
	return XCALLOC(MTYPE_ROUTE_SRC_NODE, sizeof(struct route_node));
}

static void srcdest_srcnode_destroy(route_table_delegate_t *delegate,
				    struct route_table *table,
				    struct route_node *rn)
{
	struct srcdest_rnode *srn;

	XFREE(MTYPE_ROUTE_SRC_NODE, rn);

	srn = table->info;
	if (srn->src_table && route_table_count(srn->src_table) == 0) {
		/* deleting the route_table from inside destroy_node is ONLY
		 * permitted IF table->count is 0!  see lib/table.c
		 * route_node_delete()
		 * for details */
		route_table_finish(srn->src_table);
		srn->src_table = NULL;

		/* drop the ref we're holding in srcdest_node_get().  there
		 * might be
		 * non-srcdest routes, so the route_node may still exist.
		 * hence, it's
		 * important to clear src_table above. */
		route_unlock_node(srcdest_rnode_to_rnode(srn));
	}
}

route_table_delegate_t _srcdest_srcnode_delegate = {
	.create_node = srcdest_srcnode_create,
	.destroy_node = srcdest_srcnode_destroy};

/* NB: read comments in code for refcounting before using! */
static struct route_node *srcdest_srcnode_get(struct route_node *rn,
					      struct prefix_ipv6 *src_p)
{
	struct srcdest_rnode *srn;

	if (!src_p || src_p->prefixlen == 0)
		return rn;

	srn = srcdest_rnode_from_rnode(rn);
	if (!srn->src_table) {
		/* this won't use srcdest_rnode, we're already on the source
		 * here */
		srn->src_table = route_table_init_with_delegate(
			&_srcdest_srcnode_delegate);
		srn->src_table->info = srn;

		/* there is no route_unlock_node on the original rn here.
		 * The reference is kept for the src_table. */
	} else {
		/* only keep 1 reference for the src_table, makes the
		 * refcounting
		 * more similar to the non-srcdest case.  Either way after
		 * return from
		 * function, the only reference held is the one on the return
		 * value.
		 *
		 * We can safely drop our reference here because src_table is
		 * holding
		 * another reference, so this won't free rn */
		route_unlock_node(rn);
	}

	return route_node_get(srn->src_table, (struct prefix *)src_p);
}

static struct route_node *srcdest_srcnode_lookup(struct route_node *rn,
						 struct prefix_ipv6 *src_p)
{
	struct srcdest_rnode *srn;

	if (!rn || !src_p || src_p->prefixlen == 0)
		return rn;

	/* We got this rn from a lookup, so its refcnt was incremented. As we
	 * won't
	 * return return rn from any point beyond here, we should decrement its
	 * refcnt.
	 */
	route_unlock_node(rn);

	srn = srcdest_rnode_from_rnode(rn);
	if (!srn->src_table)
		return NULL;

	return route_node_lookup(srn->src_table, (struct prefix *)src_p);
}

/* ----- exported functions ----- */

struct route_table *srcdest_table_init(void)
{
	return route_table_init_with_delegate(&_srcdest_dstnode_delegate);
}

struct route_node *srcdest_route_next(struct route_node *rn)
{
	struct route_node *next, *parent;

	/* For a non src-dest node, just return route_next */
	if (!(rnode_is_dstnode(rn) || rnode_is_srcnode(rn)))
		return route_next(rn);

	if (rnode_is_dstnode(rn)) {
		/* This means the route_node is part of the top hierarchy
		 * and refers to a destination prefix. */
		struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);

		if (srn->src_table)
			next = route_top(srn->src_table);
		else
			next = NULL;

		if (next) {
			/* There is a source prefix. Return the node for it */
			route_unlock_node(rn);
			return next;
		} else {
			/* There is no source prefix, just continue as usual */
			return route_next(rn);
		}
	}

	/* This part handles the case of iterating source nodes. */
	parent = route_lock_node(rn->table->info);
	next = route_next(rn);

	if (next) {
		/* There is another source node, continue in the source table */
		route_unlock_node(parent);
		return next;
	} else {
		/* The source table is complete, continue in the parent table */
		return route_next(parent);
	}
}

struct route_node *srcdest_rnode_get(struct route_table *table,
				     union prefixptr dst_pu,
				     struct prefix_ipv6 *src_p)
{
	struct prefix_ipv6 *dst_p = dst_pu.p6;
	struct route_node *rn;

	rn = route_node_get(table, (struct prefix *)dst_p);
	return srcdest_srcnode_get(rn, src_p);
}

struct route_node *srcdest_rnode_lookup(struct route_table *table,
					union prefixptr dst_pu,
					struct prefix_ipv6 *src_p)
{
	struct prefix_ipv6 *dst_p = dst_pu.p6;
	struct route_node *rn;
	struct route_node *srn;

	rn = route_node_lookup_maynull(table, (struct prefix *)dst_p);
	srn = srcdest_srcnode_lookup(rn, src_p);

	if (rn != NULL && rn == srn && !rn->info) {
		/* Match the behavior of route_node_lookup and don't return an
		 * empty route-node for a dest-route */
		route_unlock_node(rn);
		return NULL;
	}
	return srn;
}

void srcdest_rnode_prefixes(struct route_node *rn, struct prefix **p,
			    struct prefix **src_p)
{
	if (rnode_is_srcnode(rn)) {
		struct route_node *dst_rn = rn->table->info;
		if (p)
			*p = &dst_rn->p;
		if (src_p)
			*src_p = &rn->p;
	} else {
		if (p)
			*p = &rn->p;
		if (src_p)
			*src_p = NULL;
	}
}

const char *srcdest_rnode2str(struct route_node *rn, char *str, int size)
{
	struct prefix *dst_p, *src_p;
	char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN];

	srcdest_rnode_prefixes(rn, &dst_p, &src_p);

	snprintf(str, size, "%s%s%s",
		 prefix2str(dst_p, dst_buf, sizeof(dst_buf)),
		 (src_p && src_p->prefixlen) ? " from " : "",
		 (src_p && src_p->prefixlen)
			 ? prefix2str(src_p, src_buf, sizeof(src_buf))
			 : "");
	return str;
}
Commit	Line	Data
0964ad9c DL	1	/*
	2	* SRC-DEST Routing Table
	3	*
	4	* Copyright (C) 2017 by David Lamparter & Christian Franke,
	5	* Open Source Routing / NetDEF Inc.
	6	*
	7	* This file is part of FreeRangeRouting (FRR)
	8	*
	9	* FRR is free software; you can redistribute it and/or modify it
	10	* under the terms of the GNU General Public License as published by the
	11	* Free Software Foundation; either version 2, or (at your option) any
	12	* later version.
	13	*
	14	* FRR is distributed in the hope that it will be useful, but
	15	* WITHOUT ANY WARRANTY; without even the implied warranty of
	16	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	17	* General Public License for more details.
	18	*
896014f4 DL	19	* You should have received a copy of the GNU General Public License along
	20	* with this program; see the file COPYING; if not, write to the Free Software
	21	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
0964ad9c DL	22	*/
	23
	24	#include <zebra.h>
	25
	26	#include "srcdest_table.h"
	27
	28	#include "memory.h"
	29	#include "prefix.h"
	30	#include "table.h"
	31
	32	DEFINE_MTYPE_STATIC(LIB, ROUTE_SRC_NODE, "Route source node")
	33
	34	/* ----- functions to manage rnodes _with_ srcdest table ----- */
d62a17ae	35	struct srcdest_rnode {
	36	/* must be first in structure for casting to/from route_node */
	37	ROUTE_NODE_FIELDS;
0964ad9c	38
d62a17ae	39	struct route_table *src_table;
0964ad9c DL	40	};
0964ad9c DL	41
d62a17ae	42	static struct srcdest_rnode srcdest_rnode_from_rnode(struct route_node rn)
0964ad9c	43	{
d62a17ae	44	assert(rnode_is_dstnode(rn));
d62a17ae	45	return (struct srcdest_rnode *)rn;
0964ad9c DL	46	}
0964ad9c DL	47
d62a17ae	48	static struct route_node srcdest_rnode_to_rnode(struct srcdest_rnode srn)
0964ad9c	49	{
d62a17ae	50	return (struct route_node *)srn;
0964ad9c DL	51	}
0964ad9c DL	52
d62a17ae	53	static struct route_node srcdest_rnode_create(route_table_delegate_t delegate,
d62a17ae	54	struct route_table *table)
0964ad9c	55	{
d62a17ae	56	struct srcdest_rnode *srn;
	57	srn = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct srcdest_rnode));
	58	return srcdest_rnode_to_rnode(srn);
0964ad9c DL	59	}
0964ad9c DL	60
d62a17ae	61	static void srcdest_rnode_destroy(route_table_delegate_t *delegate,
	62	struct route_table *table,
	63	struct route_node *rn)
0964ad9c	64	{
d62a17ae	65	struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
	66	struct route_table *src_table;
	67
	68	/* Clear route node's src_table here already, otherwise the
	69	* deletion of the last node in the src_table will trigger
	70	* another call to route_table_finish for the src_table.
	71	*
	72	* (Compare with srcdest_srcnode_destroy)
	73	*/
	74	src_table = srn->src_table;
	75	srn->src_table = NULL;
	76	route_table_finish(src_table);
	77	XFREE(MTYPE_ROUTE_NODE, rn);
0964ad9c DL	78	}
	79
	80	route_table_delegate_t _srcdest_dstnode_delegate = {
d62a17ae	81	.create_node = srcdest_rnode_create,
d62a17ae	82	.destroy_node = srcdest_rnode_destroy};
0964ad9c DL	83
	84	/* ----- functions to manage rnodes _in_ srcdest table ----- */
	85
	86	/* node creation / deletion for srcdest source prefix nodes.
	87	* the route_node isn't actually different from the normal route_node,
	88	* but the cleanup is special to free the table (and possibly the
	89	* destination prefix's route_node) */
	90
	91	static struct route_node *
d62a17ae	92	srcdest_srcnode_create(route_table_delegate_t *delegate,
d62a17ae	93	struct route_table *table)
0964ad9c	94	{
d62a17ae	95	return XCALLOC(MTYPE_ROUTE_SRC_NODE, sizeof(struct route_node));
0964ad9c DL	96	}
0964ad9c DL	97
d62a17ae	98	static void srcdest_srcnode_destroy(route_table_delegate_t *delegate,
	99	struct route_table *table,
	100	struct route_node *rn)
0964ad9c	101	{
d62a17ae	102	struct srcdest_rnode *srn;
	103
	104	XFREE(MTYPE_ROUTE_SRC_NODE, rn);
	105
	106	srn = table->info;
	107	if (srn->src_table && route_table_count(srn->src_table) == 0) {
	108	/* deleting the route_table from inside destroy_node is ONLY
	109	* permitted IF table->count is 0! see lib/table.c
	110	* route_node_delete()
	111	* for details */
	112	route_table_finish(srn->src_table);
	113	srn->src_table = NULL;
	114
	115	/* drop the ref we're holding in srcdest_node_get(). there
	116	* might be
	117	* non-srcdest routes, so the route_node may still exist.
	118	* hence, it's
	119	* important to clear src_table above. */
	120	route_unlock_node(srcdest_rnode_to_rnode(srn));
	121	}
0964ad9c DL	122	}
	123
	124	route_table_delegate_t _srcdest_srcnode_delegate = {
d62a17ae	125	.create_node = srcdest_srcnode_create,
d62a17ae	126	.destroy_node = srcdest_srcnode_destroy};
0964ad9c DL	127
0964ad9c DL	128	/* NB: read comments in code for refcounting before using! */
d62a17ae	129	static struct route_node srcdest_srcnode_get(struct route_node rn,
d62a17ae	130	struct prefix_ipv6 *src_p)
0964ad9c	131	{
d62a17ae	132	struct srcdest_rnode *srn;
	133
	134	if (!src_p \|\| src_p->prefixlen == 0)
	135	return rn;
	136
	137	srn = srcdest_rnode_from_rnode(rn);
	138	if (!srn->src_table) {
	139	/* this won't use srcdest_rnode, we're already on the source
	140	* here */
	141	srn->src_table = route_table_init_with_delegate(
	142	&_srcdest_srcnode_delegate);
	143	srn->src_table->info = srn;
	144
	145	/* there is no route_unlock_node on the original rn here.
	146	* The reference is kept for the src_table. */
	147	} else {
	148	/* only keep 1 reference for the src_table, makes the
	149	* refcounting
	150	* more similar to the non-srcdest case. Either way after
	151	* return from
	152	* function, the only reference held is the one on the return
	153	* value.
	154	*
	155	* We can safely drop our reference here because src_table is
	156	* holding
	157	* another reference, so this won't free rn */
	158	route_unlock_node(rn);
	159	}
	160
	161	return route_node_get(srn->src_table, (struct prefix *)src_p);
0964ad9c DL	162	}
0964ad9c DL	163
d62a17ae	164	static struct route_node srcdest_srcnode_lookup(struct route_node rn,
d62a17ae	165	struct prefix_ipv6 *src_p)
0964ad9c	166	{
d62a17ae	167	struct srcdest_rnode *srn;
0964ad9c	168
d62a17ae	169	if (!rn \|\| !src_p \|\| src_p->prefixlen == 0)
d62a17ae	170	return rn;
0964ad9c	171
d62a17ae	172	/* We got this rn from a lookup, so its refcnt was incremented. As we
	173	* won't
	174	* return return rn from any point beyond here, we should decrement its
	175	* refcnt.
	176	*/
	177	route_unlock_node(rn);
0964ad9c	178
d62a17ae	179	srn = srcdest_rnode_from_rnode(rn);
	180	if (!srn->src_table)
	181	return NULL;
0964ad9c	182
d62a17ae	183	return route_node_lookup(srn->src_table, (struct prefix *)src_p);
0964ad9c DL	184	}
	185
	186	/* ----- exported functions ----- */
	187
d62a17ae	188	struct route_table *srcdest_table_init(void)
0964ad9c	189	{
d62a17ae	190	return route_table_init_with_delegate(&_srcdest_dstnode_delegate);
0964ad9c DL	191	}
0964ad9c DL	192
d62a17ae	193	struct route_node srcdest_route_next(struct route_node rn)
0964ad9c	194	{
d62a17ae	195	struct route_node next, parent;
	196
	197	/* For a non src-dest node, just return route_next */
	198	if (!(rnode_is_dstnode(rn) \|\| rnode_is_srcnode(rn)))
	199	return route_next(rn);
	200
	201	if (rnode_is_dstnode(rn)) {
	202	/* This means the route_node is part of the top hierarchy
	203	* and refers to a destination prefix. */
	204	struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
	205
	206	if (srn->src_table)
	207	next = route_top(srn->src_table);
	208	else
	209	next = NULL;
	210
	211	if (next) {
	212	/* There is a source prefix. Return the node for it */
	213	route_unlock_node(rn);
	214	return next;
	215	} else {
	216	/* There is no source prefix, just continue as usual */
	217	return route_next(rn);
	218	}
	219	}
	220
	221	/* This part handles the case of iterating source nodes. */
	222	parent = route_lock_node(rn->table->info);
	223	next = route_next(rn);
	224
	225	if (next) {
	226	/* There is another source node, continue in the source table */
	227	route_unlock_node(parent);
	228	return next;
	229	} else {
	230	/* The source table is complete, continue in the parent table */
	231	return route_next(parent);
	232	}
0964ad9c DL	233	}
0964ad9c DL	234
d62a17ae	235	struct route_node srcdest_rnode_get(struct route_table table,
	236	union prefixptr dst_pu,
	237	struct prefix_ipv6 *src_p)
0964ad9c	238	{
d62a17ae	239	struct prefix_ipv6 *dst_p = dst_pu.p6;
d62a17ae	240	struct route_node *rn;
0964ad9c	241
d62a17ae	242	rn = route_node_get(table, (struct prefix *)dst_p);
d62a17ae	243	return srcdest_srcnode_get(rn, src_p);
0964ad9c DL	244	}
0964ad9c DL	245
d62a17ae	246	struct route_node srcdest_rnode_lookup(struct route_table table,
	247	union prefixptr dst_pu,
	248	struct prefix_ipv6 *src_p)
0964ad9c	249	{
d62a17ae	250	struct prefix_ipv6 *dst_p = dst_pu.p6;
	251	struct route_node *rn;
	252	struct route_node *srn;
	253
	254	rn = route_node_lookup_maynull(table, (struct prefix *)dst_p);
	255	srn = srcdest_srcnode_lookup(rn, src_p);
	256
	257	if (rn != NULL && rn == srn && !rn->info) {
	258	/* Match the behavior of route_node_lookup and don't return an
	259	* empty route-node for a dest-route */
	260	route_unlock_node(rn);
	261	return NULL;
	262	}
	263	return srn;
0964ad9c DL	264	}
0964ad9c DL	265
d62a17ae	266	void srcdest_rnode_prefixes(struct route_node rn, struct prefix *p,
d62a17ae	267	struct prefix **src_p)
0964ad9c	268	{
d62a17ae	269	if (rnode_is_srcnode(rn)) {
	270	struct route_node *dst_rn = rn->table->info;
	271	if (p)
	272	*p = &dst_rn->p;
	273	if (src_p)
	274	*src_p = &rn->p;
	275	} else {
	276	if (p)
	277	*p = &rn->p;
	278	if (src_p)
	279	*src_p = NULL;
	280	}
0964ad9c DL	281	}
0964ad9c DL	282
d62a17ae	283	const char srcdest_rnode2str(struct route_node rn, char *str, int size)
0964ad9c	284	{
d62a17ae	285	struct prefix dst_p, src_p;
	286	char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN];
	287
	288	srcdest_rnode_prefixes(rn, &dst_p, &src_p);
	289
	290	snprintf(str, size, "%s%s%s",
	291	prefix2str(dst_p, dst_buf, sizeof(dst_buf)),
	292	(src_p && src_p->prefixlen) ? " from " : "",
	293	(src_p && src_p->prefixlen)
	294	? prefix2str(src_p, src_buf, sizeof(src_buf))
	295	: "");
	296	return str;
0964ad9c	297	}