in_fib_algo.c File Reference

#include <sys/cdefs.h>
#include "opt_inet.h"
#include <sys/param.h>
#include <sys/kernel.h>
#include <sys/lock.h>
#include <sys/rmlock.h>
#include <sys/malloc.h>
#include <sys/priv.h>
#include <sys/socket.h>
#include <sys/sysctl.h>
#include <net/vnet.h>
#include <net/if.h>
#include <netinet/in.h>
#include <net/route.h>
#include <net/route/nhop.h>
#include <net/route/route_ctl.h>
#include <net/route/route_var.h>
#include <net/route/fib_algo.h>

Include dependency graph for in_fib_algo.c:

Go to the source code of this file.

Data Structures
struct	bsearch4_record
struct	bsearch4_data
struct	bsearch4_array
struct	radix4_addr_entry
struct	lradix4_data
struct	radix4_data

Macros
#define	KEY_LEN_INET   (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
#define	OFF_LEN_INET   (8 * offsetof(struct sockaddr_in, sin_addr))
#define	LRADIX4_ITEM_SZ   roundup2(sizeof(struct radix4_addr_entry), 64)

Functions
	__FBSDID ("$FreeBSD$")
static struct nhop_object *	bsearch4_lookup (void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
static uint8_t	bsearch4_get_pref (const struct rib_rtable_info *rinfo)
static enum flm_op_result	bsearch4_init (uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
static void	bsearch4_destroy (void *_data)
static enum flm_op_result	bsearch4_add_route_cb (struct rtentry *rt, void *_data)
static int	rr_cmp (const void *_rec1, const void *_rec2)
static bool	add_array_entry (struct bsearch4_array *ba, struct bsearch4_record *br_new)
static struct bsearch4_record *	get_last_entry (struct bsearch4_array *ba)
static bool	pop_stack_entry (struct bsearch4_array *dst_array, struct bsearch4_array *stack)
static bool	bsearch4_process_record (struct bsearch4_array *dst_array, struct bsearch4_array *stack, struct bsearch4_record *rib_entry)
static enum flm_op_result	bsearch4_build_array (struct bsearch4_array *dst_array, struct bsearch4_array *src_array)
static enum flm_op_result	bsearch4_build (struct bsearch4_data *bd)
static enum flm_op_result	bsearch4_end_dump (void *_data, struct fib_dp *dp)
static enum flm_op_result	bsearch4_change_cb (struct rib_head *rnh, struct rib_cmd_info *rc, void *_data)
static struct nhop_object *	lradix4_lookup (void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
static uint8_t	lradix4_get_pref (const struct rib_rtable_info *rinfo)
static enum flm_op_result	lradix4_init (uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
static void	lradix4_destroy (void *_data)
static enum flm_op_result	lradix4_add_route_cb (struct rtentry *rt, void *_data)
static enum flm_op_result	lradix4_end_dump (void *_data, struct fib_dp *dp)
static enum flm_op_result	lradix4_change_cb (struct rib_head *rnh, struct rib_cmd_info *rc, void *_data)
static struct nhop_object *	radix4_lookup (void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
static uint8_t	radix4_get_pref (const struct rib_rtable_info *rinfo)
static enum flm_op_result	radix4_init (uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
static void	radix4_destroy (void *_data)
static enum flm_op_result	radix4_add_route_cb (struct rtentry *rt, void *_data)
static enum flm_op_result	radix4_end_dump (void *_data, struct fib_dp *dp)
static enum flm_op_result	radix4_change_cb (struct rib_head *rnh, struct rib_cmd_info *rc, void *_data)
static void	fib4_algo_init (void)
	SYSINIT (fib4_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib4_algo_init, NULL)

Variables
struct fib_lookup_module	flm_bsearch4
struct fib_lookup_module	flm_radix4_lockless
struct fib_lookup_module	flm_radix4

Macro Definition Documentation

KEY_LEN_INET

#define KEY_LEN_INET   (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))

Definition at line 509 of file in_fib_algo.c.

LRADIX4_ITEM_SZ

#define LRADIX4_ITEM_SZ   roundup2(sizeof(struct radix4_addr_entry), 64)

Definition at line 516 of file in_fib_algo.c.

OFF_LEN_INET

#define OFF_LEN_INET   (8 * offsetof(struct sockaddr_in, sin_addr))

Definition at line 510 of file in_fib_algo.c.

Function Documentation

__FBSDID()

__FBSDID

(

"$FreeBSD$"

)

add_array_entry()

static bool add_array_entry ( struct bsearch4_array *  ba, struct bsearch4_record *  br_new  )

static

Definition at line 252 of file in_fib_algo.c.

References bsearch4_array::alloc_items, bsearch4_array::arr, and bsearch4_array::num_items.

Referenced by bsearch4_build(), bsearch4_process_record(), and pop_stack_entry().

Here is the caller graph for this function:

bsearch4_add_route_cb()

static enum flm_op_result bsearch4_add_route_cb ( struct rtentry *  rt, void *  _data  )

static

Definition at line 198 of file in_fib_algo.c.

References bsearch4_record::addr4, bsearch4_data::alloc_items, bsearch4_record::mask4, bsearch4_record::nh, bsearch4_data::num_items, bsearch4_data::rr, and in_addr::s_addr.

bsearch4_build()

static enum flm_op_result bsearch4_build ( struct bsearch4_data *  bd )

static

Definition at line 422 of file in_fib_algo.c.

References add_array_entry(), bsearch4_data::alloc_items, bsearch4_array::alloc_items, bsearch4_array::arr, bsearch4_data::br, bsearch4_build_array(), bsearch4_record::mask4, bsearch4_data::num_items, bsearch4_array::num_items, bsearch4_data::rr, and rr_cmp().

Referenced by bsearch4_end_dump().

Here is the call graph for this function:

Here is the caller graph for this function:

bsearch4_build_array()

static enum flm_op_result bsearch4_build_array ( struct bsearch4_array *  dst_array, struct bsearch4_array *  src_array  )

static

Definition at line 385 of file in_fib_algo.c.

References bsearch4_array::alloc_items, bsearch4_array::arr, bsearch4_process_record(), bsearch4_array::num_items, and pop_stack_entry().

Referenced by bsearch4_build().

Here is the call graph for this function:

Here is the caller graph for this function:

bsearch4_change_cb()

static enum flm_op_result bsearch4_change_cb ( struct rib_head *  rnh, struct rib_cmd_info *  rc, void *  _data  )

static

Definition at line 480 of file in_fib_algo.c.

bsearch4_destroy()

static void bsearch4_destroy ( void *  _data )

static

Definition at line 184 of file in_fib_algo.c.

References bsearch4_data::mem, and bsearch4_data::rr.

bsearch4_end_dump()

static enum flm_op_result bsearch4_end_dump ( void *  _data, struct fib_dp *  dp  )

static

Definition at line 465 of file in_fib_algo.c.

References bsearch4_build(), and bsearch4_lookup().

Here is the call graph for this function:

bsearch4_get_pref()

static uint8_t bsearch4_get_pref ( const struct rib_rtable_info *  rinfo )

static

Definition at line 135 of file in_fib_algo.c.

bsearch4_init()

static enum flm_op_result bsearch4_init ( uint32_t  fibnum, struct fib_data *  fd, void *  _old_data, void **  _data  )

static

Definition at line 147 of file in_fib_algo.c.

References bsearch4_data::alloc_items, count, bsearch4_data::fd, bsearch4_data::mem, and bsearch4_data::rr.

bsearch4_lookup()

static struct nhop_object * bsearch4_lookup ( void *  algo_data, const struct flm_lookup_key  key, uint32_t  scopeid  )

static

Definition at line 97 of file in_fib_algo.c.

References bsearch4_record::addr4, bsearch4_data::br, bsearch4_record::nh, and bsearch4_data::num_items.

Referenced by bsearch4_end_dump().

Here is the caller graph for this function:

bsearch4_process_record()

static bool bsearch4_process_record ( struct bsearch4_array *  dst_array, struct bsearch4_array *  stack, struct bsearch4_record *  rib_entry  )

static

Definition at line 314 of file in_fib_algo.c.

References add_array_entry(), bsearch4_record::addr4, get_last_entry(), bsearch4_record::mask4, bsearch4_record::nh, bsearch4_array::num_items, and pop_stack_entry().

Referenced by bsearch4_build_array().

Here is the call graph for this function:

Here is the caller graph for this function:

fib4_algo_init()

static void fib4_algo_init ( void  )

static

Definition at line 771 of file in_fib_algo.c.

References flm_bsearch4, flm_radix4, and flm_radix4_lockless.

get_last_entry()

static struct bsearch4_record * get_last_entry ( struct bsearch4_array *  ba )

static

Definition at line 263 of file in_fib_algo.c.

References bsearch4_array::arr, and bsearch4_array::num_items.

Referenced by bsearch4_process_record(), and pop_stack_entry().

Here is the caller graph for this function:

lradix4_add_route_cb()

static enum flm_op_result lradix4_add_route_cb ( struct rtentry *  rt, void *  _data  )

static

Definition at line 600 of file in_fib_algo.c.

References radix4_addr_entry::addr, lradix4_data::alloc_items, INADDR_BROADCAST, KEY_LEN_INET, LRADIX4_ITEM_SZ, radix4_addr_entry::nhop, lradix4_data::num_items, radix4_addr_entry::rn, lradix4_data::rnh, lradix4_data::rt_base, in_addr::s_addr, sockaddr_in::sin_addr, and sockaddr_in::sin_len.

lradix4_change_cb()

static enum flm_op_result lradix4_change_cb ( struct rib_head *  rnh, struct rib_cmd_info *  rc, void *  _data  )

static

Definition at line 650 of file in_fib_algo.c.

lradix4_destroy()

static void lradix4_destroy ( void *  _data )

static

Definition at line 588 of file in_fib_algo.c.

References lradix4_data::mem, and lradix4_data::rnh.

lradix4_end_dump()

static enum flm_op_result lradix4_end_dump ( void *  _data, struct fib_dp *  dp  )

static

Definition at line 639 of file in_fib_algo.c.

References lradix4_lookup(), and lradix4_data::rnh.

Here is the call graph for this function:

lradix4_get_pref()

static uint8_t lradix4_get_pref ( const struct rib_rtable_info *  rinfo )

static

Definition at line 548 of file in_fib_algo.c.

lradix4_init()

static enum flm_op_result lradix4_init ( uint32_t  fibnum, struct fib_data *  fd, void *  _old_data, void **  _data  )

static

Definition at line 560 of file in_fib_algo.c.

References lradix4_data::alloc_items, count, lradix4_data::fd, LRADIX4_ITEM_SZ, lradix4_data::mem, OFF_LEN_INET, lradix4_data::rnh, and lradix4_data::rt_base.

lradix4_lookup()

static struct nhop_object * lradix4_lookup ( void *  algo_data, const struct flm_lookup_key  key, uint32_t  scopeid  )

static

Definition at line 528 of file in_fib_algo.c.

References KEY_LEN_INET, radix4_addr_entry::nhop, and sockaddr_in::sin_len.

Referenced by lradix4_end_dump().

Here is the caller graph for this function:

pop_stack_entry()

static bool pop_stack_entry ( struct bsearch4_array *  dst_array, struct bsearch4_array *  stack  )

static

Definition at line 277 of file in_fib_algo.c.

References add_array_entry(), bsearch4_record::addr4, get_last_entry(), bsearch4_record::mask4, bsearch4_record::nh, and bsearch4_array::num_items.

Referenced by bsearch4_build_array(), and bsearch4_process_record().

Here is the call graph for this function:

Here is the caller graph for this function:

radix4_add_route_cb()

static enum flm_op_result radix4_add_route_cb ( struct rtentry *  rt, void *  _data  )

static

Definition at line 734 of file in_fib_algo.c.

radix4_change_cb()

static enum flm_op_result radix4_change_cb ( struct rib_head *  rnh, struct rib_cmd_info *  rc, void *  _data  )

static

Definition at line 752 of file in_fib_algo.c.

radix4_destroy()

static void radix4_destroy ( void *  _data )

static

Definition at line 727 of file in_fib_algo.c.

radix4_end_dump()

static enum flm_op_result radix4_end_dump ( void *  _data, struct fib_dp *  dp  )

static

Definition at line 741 of file in_fib_algo.c.

References radix4_lookup(), and radix4_data::rh.

Here is the call graph for this function:

radix4_get_pref()

static uint8_t radix4_get_pref ( const struct rib_rtable_info *  rinfo )

static

Definition at line 704 of file in_fib_algo.c.

radix4_init()

static enum flm_op_result radix4_init ( uint32_t  fibnum, struct fib_data *  fd, void *  _old_data, void **  _data  )

static

Definition at line 711 of file in_fib_algo.c.

References radix4_data::fd, and radix4_data::rh.

radix4_lookup()

static struct nhop_object * radix4_lookup ( void *  algo_data, const struct flm_lookup_key  key, uint32_t  scopeid  )

static

Definition at line 679 of file in_fib_algo.c.

References sockaddr_in::sin_addr, and sockaddr_in::sin_family.

Referenced by radix4_end_dump().

Here is the caller graph for this function:

rr_cmp()

static int rr_cmp ( const void *  _rec1, const void *  _rec2  )

static

Definition at line 223 of file in_fib_algo.c.

References bsearch4_record::addr4, and bsearch4_record::mask4.

Referenced by bsearch4_build().

Here is the caller graph for this function:

SYSINIT()

SYSINIT	(	fib4_algo_init	,
		SI_SUB_PROTO_DOMAIN	,
		SI_ORDER_THIRD	,
		fib4_algo_init	,
		NULL
	)

Variable Documentation

flm_bsearch4

struct fib_lookup_module flm_bsearch4

Initial value:

= {
        .flm_name = "bsearch4",
        .flm_family = AF_INET,
        .flm_init_cb = bsearch4_init,
        .flm_destroy_cb = bsearch4_destroy,
        .flm_dump_rib_item_cb = bsearch4_add_route_cb,
        .flm_dump_end_cb = bsearch4_end_dump,
        .flm_change_rib_item_cb = bsearch4_change_cb,
        .flm_get_pref = bsearch4_get_pref,
}

Definition at line 487 of file in_fib_algo.c.

Referenced by fib4_algo_init().

flm_radix4

struct fib_lookup_module flm_radix4

Initial value:

= {
        .flm_name = "radix4",
        .flm_family = AF_INET,
        .flm_init_cb = radix4_init,
        .flm_destroy_cb = radix4_destroy,
        .flm_dump_rib_item_cb = radix4_add_route_cb,
        .flm_dump_end_cb = radix4_end_dump,
        .flm_change_rib_item_cb = radix4_change_cb,
        .flm_get_pref = radix4_get_pref,
}

Definition at line 759 of file in_fib_algo.c.

Referenced by fib4_algo_init().

flm_radix4_lockless

struct fib_lookup_module flm_radix4_lockless

Initial value:

= {
        .flm_name = "radix4_lockless",
        .flm_family = AF_INET,
        .flm_init_cb = lradix4_init,
        .flm_destroy_cb = lradix4_destroy,
        .flm_dump_rib_item_cb = lradix4_add_route_cb,
        .flm_dump_end_cb = lradix4_end_dump,
        .flm_change_rib_item_cb = lradix4_change_cb,
        .flm_get_pref = lradix4_get_pref,
}

Definition at line 657 of file in_fib_algo.c.

Referenced by fib4_algo_init().