/src/frr/lib/srcdest_table.c

Source
// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * SRC-DEST Routing Table
 *
 * Copyright (C) 2017 by David Lamparter & Christian Franke,
 *                       Open Source Routing / NetDEF Inc.
 *
 * This file is part of FRRouting (FRR)
 */

#include <zebra.h>

#include "srcdest_table.h"

#include "memory.h"
#include "prefix.h"
#include "table.h"
#include "printfrr.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 = route_table_get_info(table);
  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,
                const 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);
    route_table_set_info(srn->src_table, 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, (const struct prefix *)src_p);
}

static struct route_node *srcdest_srcnode_lookup(
  struct route_node *rn,
  const 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, (const 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(route_table_get_info(rn->table));
  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 prefixconstptr dst_pu,
             const struct prefix_ipv6 *src_p)
{
  const struct prefix_ipv6 *dst_p = dst_pu.p6;
  struct route_node *rn;

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

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

  rn = route_node_lookup_maynull(table, (const 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(const struct route_node *rn,
          const struct prefix **p,
          const struct prefix **src_p)
{
  if (rnode_is_srcnode(rn)) {
    struct route_node *dst_rn = route_table_get_info(rn->table);
    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 *srcdest2str(const struct prefix *dst_p,
      const struct prefix_ipv6 *src_p,
      char *str, int size)
{
  char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN];

  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;
}

const char *srcdest_rnode2str(const struct route_node *rn, char *str, int size)
{
  const struct prefix *dst_p, *src_p;

  srcdest_rnode_prefixes(rn, &dst_p, &src_p);
  return srcdest2str(dst_p, (const struct prefix_ipv6 *)src_p, str, size);
}

printfrr_ext_autoreg_p("RN", printfrr_rn);
static ssize_t printfrr_rn(struct fbuf *buf, struct printfrr_eargs *ea,
         const void *ptr)
{
  const struct route_node *rn = ptr;
  const struct prefix *dst_p, *src_p;
  char cbuf[PREFIX_STRLEN * 2 + 6];

  if (!rn)
    return bputs(buf, "(null)");

  srcdest_rnode_prefixes(rn, &dst_p, &src_p);
  srcdest2str(dst_p, (const struct prefix_ipv6 *)src_p,
        cbuf, sizeof(cbuf));
  return bputs(buf, cbuf);
}

struct route_table *srcdest_srcnode_table(struct route_node *rn)
{
  if (rnode_is_dstnode(rn)) {
    struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);

    return srn->src_table;
  }
  return NULL;
}

Coverage Report

Created: 2025-10-08 06:07

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