#include <linux/cache.h>
#include <linux/uaccess.h>
#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/inetdevice.h>
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
#include <linux/rcupdate.h>
#include <linux/rcupdate_wait.h>
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/export.h>
#include <linux/vmalloc.h>
#include <linux/notifier.h>
#include <net/net_namespace.h>
#include <net/inet_dscp.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#include <net/tcp.h>
#include <net/sock.h>
#include <net/ip_fib.h>
#include <net/fib_notifier.h>
#include <trace/events/fib.h>
#include "fib_lookup.h"
static int call_fib_entry_notifier(struct notifier_block *nb,
enum fib_event_type event_type, u32 dst,
int dst_len, struct fib_alias *fa,
struct netlink_ext_ack *extack)
{ … }
static int call_fib_entry_notifiers(struct net *net,
enum fib_event_type event_type, u32 dst,
int dst_len, struct fib_alias *fa,
struct netlink_ext_ack *extack)
{ … }
#define MAX_STAT_DEPTH …
#define KEYLENGTH …
#define KEY_MAX …
t_key;
#define IS_TRIE(n) …
#define IS_TNODE(n) …
#define IS_LEAF(n) …
struct key_vector { … };
struct tnode { … };
#define TNODE_SIZE(n) …
#define LEAF_SIZE …
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats { … };
#endif
struct trie_stat { … };
struct trie { … };
static struct key_vector *resize(struct trie *t, struct key_vector *tn);
static unsigned int tnode_free_size;
unsigned int sysctl_fib_sync_mem = …;
unsigned int sysctl_fib_sync_mem_min = …;
unsigned int sysctl_fib_sync_mem_max = …;
static struct kmem_cache *fn_alias_kmem __ro_after_init;
static struct kmem_cache *trie_leaf_kmem __ro_after_init;
static inline struct tnode *tn_info(struct key_vector *kv)
{ … }
#define node_parent(tn) …
#define get_child(tn, i) …
#define node_parent_rcu(tn) …
#define get_child_rcu(tn, i) …
static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
{ … }
#define NODE_INIT_PARENT(n, p) …
static inline unsigned long child_length(const struct key_vector *tn)
{ … }
#define get_cindex(key, kv) …
static inline unsigned long get_index(t_key key, struct key_vector *kv)
{ … }
static const int halve_threshold = …;
static const int inflate_threshold = …;
static const int halve_threshold_root = …;
static const int inflate_threshold_root = …;
static void __alias_free_mem(struct rcu_head *head)
{ … }
static inline void alias_free_mem_rcu(struct fib_alias *fa)
{ … }
#define TNODE_VMALLOC_MAX …
static void __node_free_rcu(struct rcu_head *head)
{ … }
#define node_free(n) …
static struct tnode *tnode_alloc(int bits)
{ … }
static inline void empty_child_inc(struct key_vector *n)
{ … }
static inline void empty_child_dec(struct key_vector *n)
{ … }
static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
{ … }
static struct key_vector *tnode_new(t_key key, int pos, int bits)
{ … }
static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
{ … }
static void put_child(struct key_vector *tn, unsigned long i,
struct key_vector *n)
{ … }
static void update_children(struct key_vector *tn)
{ … }
static inline void put_child_root(struct key_vector *tp, t_key key,
struct key_vector *n)
{ … }
static inline void tnode_free_init(struct key_vector *tn)
{ … }
static inline void tnode_free_append(struct key_vector *tn,
struct key_vector *n)
{ … }
static void tnode_free(struct key_vector *tn)
{ … }
static struct key_vector *replace(struct trie *t,
struct key_vector *oldtnode,
struct key_vector *tn)
{ … }
static struct key_vector *inflate(struct trie *t,
struct key_vector *oldtnode)
{ … }
static struct key_vector *halve(struct trie *t,
struct key_vector *oldtnode)
{ … }
static struct key_vector *collapse(struct trie *t,
struct key_vector *oldtnode)
{ … }
static unsigned char update_suffix(struct key_vector *tn)
{ … }
static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
{ … }
static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
{ … }
static inline bool should_collapse(struct key_vector *tn)
{ … }
#define MAX_WORK …
static struct key_vector *resize(struct trie *t, struct key_vector *tn)
{ … }
static void node_pull_suffix(struct key_vector *tn, unsigned char slen)
{ … }
static void node_push_suffix(struct key_vector *tn, unsigned char slen)
{ … }
static struct key_vector *fib_find_node(struct trie *t,
struct key_vector **tp, u32 key)
{ … }
static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen,
dscp_t dscp, u32 prio, u32 tb_id,
bool find_first)
{ … }
static struct fib_alias *
fib_find_matching_alias(struct net *net, const struct fib_rt_info *fri)
{ … }
void fib_alias_hw_flags_set(struct net *net, const struct fib_rt_info *fri)
{ … }
EXPORT_SYMBOL_GPL(…);
static void trie_rebalance(struct trie *t, struct key_vector *tn)
{ … }
static int fib_insert_node(struct trie *t, struct key_vector *tp,
struct fib_alias *new, t_key key)
{ … }
static int fib_insert_alias(struct trie *t, struct key_vector *tp,
struct key_vector *l, struct fib_alias *new,
struct fib_alias *fa, t_key key)
{ … }
static bool fib_valid_key_len(u32 key, u8 plen, struct netlink_ext_ack *extack)
{ … }
static void fib_remove_alias(struct trie *t, struct key_vector *tp,
struct key_vector *l, struct fib_alias *old);
int fib_table_insert(struct net *net, struct fib_table *tb,
struct fib_config *cfg, struct netlink_ext_ack *extack)
{ … }
static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
{ … }
bool fib_lookup_good_nhc(const struct fib_nh_common *nhc, int fib_flags,
const struct flowi4 *flp)
{ … }
int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
struct fib_result *res, int fib_flags)
{ … }
EXPORT_SYMBOL_GPL(…);
static void fib_remove_alias(struct trie *t, struct key_vector *tp,
struct key_vector *l, struct fib_alias *old)
{ … }
static void fib_notify_alias_delete(struct net *net, u32 key,
struct hlist_head *fah,
struct fib_alias *fa_to_delete,
struct netlink_ext_ack *extack)
{ … }
int fib_table_delete(struct net *net, struct fib_table *tb,
struct fib_config *cfg, struct netlink_ext_ack *extack)
{ … }
static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
{ … }
static void fib_trie_free(struct fib_table *tb)
{ … }
struct fib_table *fib_trie_unmerge(struct fib_table *oldtb)
{ … }
void fib_table_flush_external(struct fib_table *tb)
{ … }
int fib_table_flush(struct net *net, struct fib_table *tb, bool flush_all)
{ … }
static void __fib_info_notify_update(struct net *net, struct fib_table *tb,
struct nl_info *info)
{ … }
void fib_info_notify_update(struct net *net, struct nl_info *info)
{ … }
static int fib_leaf_notify(struct key_vector *l, struct fib_table *tb,
struct notifier_block *nb,
struct netlink_ext_ack *extack)
{ … }
static int fib_table_notify(struct fib_table *tb, struct notifier_block *nb,
struct netlink_ext_ack *extack)
{ … }
int fib_notify(struct net *net, struct notifier_block *nb,
struct netlink_ext_ack *extack)
{ … }
static void __trie_free_rcu(struct rcu_head *head)
{ … }
void fib_free_table(struct fib_table *tb)
{ … }
static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,
struct sk_buff *skb, struct netlink_callback *cb,
struct fib_dump_filter *filter)
{ … }
int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
struct netlink_callback *cb, struct fib_dump_filter *filter)
{ … }
void __init fib_trie_init(void)
{ … }
struct fib_table *fib_trie_table(u32 id, struct fib_table *alias)
{ … }
#ifdef CONFIG_PROC_FS
struct fib_trie_iter { … };
static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter)
{ … }
static struct key_vector *fib_trie_get_first(struct fib_trie_iter *iter,
struct trie *t)
{ … }
static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{ … }
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
{ … }
#ifdef CONFIG_IP_FIB_TRIE_STATS
static void trie_show_usage(struct seq_file *seq,
const struct trie_use_stats __percpu *stats)
{ … }
#endif
static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
{ … }
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{ … }
static struct key_vector *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
{ … }
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
__acquires(RCU)
{ … }
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{ … }
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
__releases(RCU)
{ … }
static void seq_indent(struct seq_file *seq, int n)
{ … }
static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
{ … }
static const char *const rtn_type_names[__RTN_MAX] = …;
static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
{ … }
static int fib_trie_seq_show(struct seq_file *seq, void *v)
{ … }
static const struct seq_operations fib_trie_seq_ops = …;
struct fib_route_iter { … };
static struct key_vector *fib_route_get_idx(struct fib_route_iter *iter,
loff_t pos)
{ … }
static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
__acquires(RCU)
{ … }
static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{ … }
static void fib_route_seq_stop(struct seq_file *seq, void *v)
__releases(RCU)
{ … }
static unsigned int fib_flag_trans(int type, __be32 mask, struct fib_info *fi)
{ … }
static int fib_route_seq_show(struct seq_file *seq, void *v)
{ … }
static const struct seq_operations fib_route_seq_ops = …;
int __net_init fib_proc_init(struct net *net)
{ … }
void __net_exit fib_proc_exit(struct net *net)
{ … }
#endif