fib_trie.c revision 1371e37da299d4df6267ad0ddf010435782c28e9
119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* 219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * This program is free software; you can redistribute it and/or 319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * modify it under the terms of the GNU General Public License 419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * as published by the Free Software Foundation; either version 519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2 of the License, or (at your option) any later version. 619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet 819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * & Swedish University of Agricultural Sciences. 919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Jens Laas <jens.laas@data.slu.se> Swedish University of 1119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Agricultural Sciences. 1219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet 1419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * This work is based on the LPC-trie which is originally descibed in: 1619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * An experimental study of compression methods for dynamic tries 1819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002. 1919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/ 2019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson 2319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999 2419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $ 2619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Code from fib_hash has been reused which includes the following header: 2919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 3019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 3119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * INET An implementation of the TCP/IP protocol suite for the LINUX 3219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * operating system. INET is implemented using the BSD Socket 3319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * interface as the means of communication with the user level. 3419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 3519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * IPv4 FIB: lookup engine and maintenance routines. 3619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 3719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 3819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 3919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 4019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * This program is free software; you can redistribute it and/or 4119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * modify it under the terms of the GNU General Public License 4219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * as published by the Free Software Foundation; either version 4319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 2 of the License, or (at your option) any later version. 4419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 4519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 46772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson#define VERSION "0.404" 4719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/config.h> 4919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <asm/uaccess.h> 5019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <asm/system.h> 5119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <asm/bitops.h> 5219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/types.h> 5319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/kernel.h> 5419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/sched.h> 5519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/mm.h> 5619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/string.h> 5719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/socket.h> 5819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/sockios.h> 5919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/errno.h> 6019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/in.h> 6119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/inet.h> 6219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/netdevice.h> 6319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/if_arp.h> 6419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/proc_fs.h> 652373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson#include <linux/rcupdate.h> 6619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/skbuff.h> 6719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/netlink.h> 6819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/init.h> 6919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/list.h> 7019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/ip.h> 7119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/protocol.h> 7219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/route.h> 7319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/tcp.h> 7419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/sock.h> 7519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/ip_fib.h> 7619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include "fib_lookup.h" 7719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#undef CONFIG_IP_FIB_TRIE_STATS 7919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define MAX_CHILDS 16384 8019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define KEYLENGTH (8*sizeof(t_key)) 8219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l)) 8319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset)) 8419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssontypedef unsigned int t_key; 8619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define T_TNODE 0 8819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define T_LEAF 1 8919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define NODE_TYPE_MASK 0x1UL 9091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#define NODE_PARENT(node) \ 912373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK))) 922373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 932373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK) 942373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 952373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson#define NODE_SET_PARENT(node, ptr) \ 962373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer((node)->parent, \ 972373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson ((unsigned long)(ptr)) | NODE_TYPE(node)) 9891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 9991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#define IS_TNODE(n) (!(n->parent & T_LEAF)) 10091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#define IS_LEAF(n) (n->parent & T_LEAF) 10119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 10219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct node { 10391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key; 10491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned long parent; 10519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 10619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 10719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct leaf { 10891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key; 10991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned long parent; 11019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_head list; 1112373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct rcu_head rcu; 11219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 11319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct leaf_info { 11519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node hlist; 1162373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct rcu_head rcu; 11719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen; 11819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head falh; 11919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 12019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct tnode { 12291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key; 12391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned long parent; 12491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */ 12591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */ 12691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short full_children; /* KEYLENGTH bits needed */ 12791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short empty_children; /* KEYLENGTH bits needed */ 1282373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct rcu_head rcu; 12991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *child[0]; 13019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 13119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 13219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 13319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct trie_use_stats { 13419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int gets; 13519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int backtrack; 13619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int semantic_match_passed; 13719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int semantic_match_miss; 13819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int null_node_hit; 1392f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson unsigned int resize_node_skipped; 14019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 14119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 14219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 14319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct trie_stat { 14419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int totdepth; 14519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int maxdepth; 14619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int tnodes; 14719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int leaves; 14819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int nullpointers; 14919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int nodesizes[MAX_CHILDS]; 150c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger}; 15119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct trie { 15391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *trie; 15419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 15519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie_use_stats stats; 15619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 15791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson int size; 15819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int revision; 15919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 16019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); 16219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); 16319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct node *resize(struct trie *t, struct tnode *tn); 1642f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *inflate(struct trie *t, struct tnode *tn); 1652f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *halve(struct trie *t, struct tnode *tn); 16619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void tnode_free(struct tnode *tn); 16719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 168ba89966c1984513f4f2cc0a6c182266be44ddd03Eric Dumazetstatic kmem_cache_t *fn_alias_kmem __read_mostly; 16919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct trie *trie_local = NULL, *trie_main = NULL; 17019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1712373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 1722373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* rcu_read_lock needs to be hold by caller from readside */ 1732373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 174c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic inline struct node *tnode_get_child(struct tnode *tn, int i) 17519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 17691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(i >= 1 << tn->bits); 17719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1782373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return rcu_dereference(tn->child[i]); 17919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 18019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 181bb435b8d816582064ee0ddb1e2a6fbca67f34108Stephen Hemmingerstatic inline int tnode_child_length(const struct tnode *tn) 18219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 18391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return 1 << tn->bits; 18419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 18519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 18619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline t_key tkey_extract_bits(t_key a, int offset, int bits) 18719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 18891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (offset < KEYLENGTH) 18919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return ((t_key)(a << offset)) >> (KEYLENGTH - bits); 19091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson else 19119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 19219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 19319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 19419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline int tkey_equals(t_key a, t_key b) 19519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 196c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger return a == b; 19719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 19819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 19919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b) 20019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 201c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (bits == 0 || offset >= KEYLENGTH) 202c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger return 1; 20391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson bits = bits > KEYLENGTH ? KEYLENGTH : bits; 20491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0; 205c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger} 20619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 20719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline int tkey_mismatch(t_key a, int offset, t_key b) 20819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 20919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key diff = a ^ b; 21019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i = offset; 21119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 212c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!diff) 213c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger return 0; 214c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger while ((diff << i) >> (KEYLENGTH-1) == 0) 21519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i++; 21619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return i; 21719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 21819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 21919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* 22019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson To understand this stuff, an understanding of keys and all their bits is 22119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson necessary. Every node in the trie has a key associated with it, but not 22219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson all of the bits in that key are significant. 22319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 22419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson Consider a node 'n' and its parent 'tp'. 22519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 22619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson If n is a leaf, every bit in its key is significant. Its presence is 227772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson necessitated by path compression, since during a tree traversal (when 22819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson searching for a leaf - unless we are doing an insertion) we will completely 22919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ignore all skipped bits we encounter. Thus we need to verify, at the end of 23019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson a potentially successful search, that we have indeed been walking the 23119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson correct key path. 23219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 23319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson Note that we can never "miss" the correct key in the tree if present by 23419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson following the wrong path. Path compression ensures that segments of the key 23519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson that are the same for all keys with a given prefix are skipped, but the 23619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson skipped part *is* identical for each node in the subtrie below the skipped 23719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson bit! trie_insert() in this implementation takes care of that - note the 23819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson call to tkey_sub_equals() in trie_insert(). 23919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 24019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if n is an internal node - a 'tnode' here, the various parts of its key 24119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson have many different meanings. 24219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 24319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson Example: 24419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson _________________________________________________________________ 24519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C | 24619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ----------------------------------------------------------------- 24719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 24819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 24919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson _________________________________________________________________ 25019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u | 25119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ----------------------------------------------------------------- 25219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 25319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 25419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp->pos = 7 25519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp->bits = 3 25619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n->pos = 15 25791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson n->bits = 4 25819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 25919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson First, let's just ignore the bits that come before the parent tp, that is 26019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson the bits from 0 to (tp->pos-1). They are *known* but at this point we do 26119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson not use them for anything. 26219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 26319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the 26419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson index into the parent's child array. That is, they will be used to find 26519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 'n' among tp's children. 26619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 26719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits 26819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson for the node n. 26919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 27019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson All the bits we have seen so far are significant to the node n. The rest 27119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson of the bits are really not needed or indeed known in n->key. 27219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 27319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into 27419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n's child array, and will of course be different for each child. 27519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 276c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 27719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The rest of the bits, from (n->pos + n->bits) onward, are completely unknown 27819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson at this point. 27919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 28019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson*/ 28119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2820c7770c740156c8802c23d24fc094d06967d997dStephen Hemmingerstatic inline void check_tnode(const struct tnode *tn) 28319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2840c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger WARN_ON(tn && tn->pos+tn->bits > 32); 28519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 28619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 28719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int halve_threshold = 25; 28819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int inflate_threshold = 50; 289e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olssonstatic int halve_threshold_root = 15; 290e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olssonstatic int inflate_threshold_root = 25; 29119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2922373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 2932373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __alias_free_mem(struct rcu_head *head) 29419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2952373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct fib_alias *fa = container_of(head, struct fib_alias, rcu); 2962373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson kmem_cache_free(fn_alias_kmem, fa); 29719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 29819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2992373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void alias_free_mem_rcu(struct fib_alias *fa) 30019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson call_rcu(&fa->rcu, __alias_free_mem); 3022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 30391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 3042373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __leaf_free_rcu(struct rcu_head *head) 3052373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3062373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson kfree(container_of(head, struct leaf, rcu)); 3072373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 30891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 3092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void free_leaf(struct leaf *leaf) 3102373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3112373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson call_rcu(&leaf->rcu, __leaf_free_rcu); 31219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 31319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 3142373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __leaf_info_free_rcu(struct rcu_head *head) 31519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3162373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson kfree(container_of(head, struct leaf_info, rcu)); 31719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 31819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 3192373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void free_leaf_info(struct leaf_info *leaf) 32019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3212373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson call_rcu(&leaf->rcu, __leaf_info_free_rcu); 32219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 32319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 324f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardystatic struct tnode *tnode_alloc(unsigned int size) 325f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy{ 3262373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct page *pages; 3272373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3282373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (size <= PAGE_SIZE) 3292373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return kcalloc(size, 1, GFP_KERNEL); 3302373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3312373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size)); 3322373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!pages) 3332373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return NULL; 3342373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3352373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return page_address(pages); 336f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy} 337f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy 3382373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __tnode_free_rcu(struct rcu_head *head) 339f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy{ 3402373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct tnode *tn = container_of(head, struct tnode, rcu); 341f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy unsigned int size = sizeof(struct tnode) + 3422373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson (1 << tn->bits) * sizeof(struct node *); 343f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy 344f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy if (size <= PAGE_SIZE) 345f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy kfree(tn); 346f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy else 347f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy free_pages((unsigned long)tn, get_order(size)); 348f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy} 349f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy 3502373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void tnode_free(struct tnode *tn) 3512373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3522373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson call_rcu(&tn->rcu, __tnode_free_rcu); 3532373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 3542373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3552373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic struct leaf *leaf_new(void) 3562373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3572373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL); 3582373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (l) { 3592373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson l->parent = T_LEAF; 3602373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson INIT_HLIST_HEAD(&l->list); 3612373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 3622373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return l; 3632373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 3642373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3652373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic struct leaf_info *leaf_info_new(int plen) 3662373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3672373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL); 3682373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (li) { 3692373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson li->plen = plen; 3702373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson INIT_LIST_HEAD(&li->falh); 3712373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 3722373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return li; 3732373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 3742373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 37519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct tnode* tnode_new(t_key key, int pos, int bits) 37619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 37719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int nchildren = 1<<bits; 37819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *); 379f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy struct tnode *tn = tnode_alloc(sz); 38019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 38191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (tn) { 38219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(tn, 0, sz); 3832373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson tn->parent = T_TNODE; 38419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->pos = pos; 38519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->bits = bits; 38619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->key = key; 38719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->full_children = 0; 38819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->empty_children = 1<<bits; 38919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 390c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 3910c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode), 3920c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger (unsigned int) (sizeof(struct node) * 1<<bits)); 39319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tn; 39419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 39519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 39619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* 39719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Check whether a tnode 'n' is "full", i.e. it is an internal node 39819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * and no bits are skipped. See discussion in dyntree paper p. 6 39919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 40019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 401bb435b8d816582064ee0ddb1e2a6fbca67f34108Stephen Hemmingerstatic inline int tnode_full(const struct tnode *tn, const struct node *n) 40219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 403c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n == NULL || IS_LEAF(n)) 40419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 40519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 40619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return ((struct tnode *) n)->pos == tn->pos + tn->bits; 40719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 40819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 409c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n) 41019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 41119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_put_child_reorg(tn, i, n, -1); 41219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 41319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 414c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 41519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Add a child at position i overwriting the old value. 41619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Update the value of full_children and empty_children. 41719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 41819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 419c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull) 42019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 4212373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct node *chi = tn->child[i]; 42219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int isfull; 42319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4240c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger BUG_ON(i >= 1<<tn->bits); 4250c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 42619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 42719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* update emptyChildren */ 42819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (n == NULL && chi != NULL) 42919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->empty_children++; 43019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson else if (n != NULL && chi == NULL) 43119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->empty_children--; 432c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 43319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* update fullChildren */ 43491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (wasfull == -1) 43519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson wasfull = tnode_full(tn, chi); 43619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 43719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson isfull = tnode_full(tn, n); 438c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (wasfull && !isfull) 43919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->full_children--; 440c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger else if (!wasfull && isfull) 44119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->full_children++; 44291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 443c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n) 444c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger NODE_SET_PARENT(n, tn); 44519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4462373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(tn->child[i], n); 44719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 44819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 449c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic struct node *resize(struct trie *t, struct tnode *tn) 45019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 45119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i; 4522f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson int err = 0; 4532f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson struct tnode *old_tn; 454e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson int inflate_threshold_use; 455e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson int halve_threshold_use; 45619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 45719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!tn) 45819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 45919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4600c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n", 4610c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger tn, inflate_threshold, halve_threshold); 46219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 46319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* No children */ 46419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tn->empty_children == tnode_child_length(tn)) { 46519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(tn); 46619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 46719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 46819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* One child */ 46919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tn->empty_children == tnode_child_length(tn) - 1) 47019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson for (i = 0; i < tnode_child_length(tn); i++) { 47191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *n; 47219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 47391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson n = tn->child[i]; 4742373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!n) 47591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 47691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 47791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* compress one level */ 4782373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson NODE_SET_PARENT(n, NULL); 47991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson tnode_free(tn); 48091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return n; 48119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 482c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 48319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Double as long as the resulting node has a number of 48419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * nonempty nodes that are above the threshold. 48519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 48619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 48719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 488c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * From "Implementing a dynamic compressed trie" by Stefan Nilsson of 489c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * the Helsinki University of Technology and Matti Tikkanen of Nokia 49019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Telecommunications, page 6: 491c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * "A node is doubled if the ratio of non-empty children to all 49219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * children in the *doubled* node is at least 'high'." 49319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 494c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 'high' in this instance is the variable 'inflate_threshold'. It 495c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * is expressed as a percentage, so we multiply it with 496c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * tnode_child_length() and instead of multiplying by 2 (since the 497c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * child array will be doubled by inflate()) and multiplying 498c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * the left-hand side by 100 (to handle the percentage thing) we 49919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * multiply the left-hand side by 50. 500c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 501c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * The left-hand side may look a bit weird: tnode_child_length(tn) 502c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * - tn->empty_children is of course the number of non-null children 503c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * in the current node. tn->full_children is the number of "full" 50419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * children, that is non-null tnodes with a skip value of 0. 505c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * All of those will be doubled in the resulting inflated tnode, so 50619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * we just count them one extra time here. 507c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 50819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * A clearer way to write this would be: 509c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 51019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * to_be_doubled = tn->full_children; 511c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - 51219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * tn->full_children; 51319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 51419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * new_child_length = tnode_child_length(tn) * 2; 51519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 516c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / 51719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * new_child_length; 51819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * if (new_fill_factor >= inflate_threshold) 519c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 520c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * ...and so on, tho it would mess up the while () loop. 521c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 52219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * anyway, 52319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >= 52419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * inflate_threshold 525c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 52619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * avoid a division: 52719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 100 * (not_to_be_doubled + 2*to_be_doubled) >= 52819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * inflate_threshold * new_child_length 529c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 53019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * expand not_to_be_doubled and to_be_doubled, and shorten: 531c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 100 * (tnode_child_length(tn) - tn->empty_children + 53291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tn->full_children) >= inflate_threshold * new_child_length 533c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 53419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * expand new_child_length: 535c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 100 * (tnode_child_length(tn) - tn->empty_children + 53691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tn->full_children) >= 53719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * inflate_threshold * tnode_child_length(tn) * 2 538c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 53919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * shorten again: 540c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 50 * (tn->full_children + tnode_child_length(tn) - 54191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tn->empty_children) >= inflate_threshold * 54219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * tnode_child_length(tn) 543c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 54419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 54519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 54619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 547c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 548e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson /* Keep root node larger */ 549e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 550e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson if(!tn->parent) 551e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson inflate_threshold_use = inflate_threshold_root; 552e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson else 553e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson inflate_threshold_use = inflate_threshold; 554e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 5552f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson err = 0; 55619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while ((tn->full_children > 0 && 55719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= 558e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson inflate_threshold_use * tnode_child_length(tn))) { 55919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 5602f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson old_tn = tn; 5612f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = inflate(t, tn); 5622f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (IS_ERR(tn)) { 5632f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = old_tn; 5642f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 5652f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson t->stats.resize_node_skipped++; 5662f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#endif 5672f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson break; 5682f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 56919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 57019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 57119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 57219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 57319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 57419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Halve as long as the number of empty children in this 57519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * node is above threshold. 57619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 5772f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 578e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 579e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson /* Keep root node larger */ 580e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 581e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson if(!tn->parent) 582e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson halve_threshold_use = halve_threshold_root; 583e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson else 584e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson halve_threshold_use = halve_threshold; 585e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 5862f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson err = 0; 58719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (tn->bits > 1 && 58819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 100 * (tnode_child_length(tn) - tn->empty_children) < 589e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson halve_threshold_use * tnode_child_length(tn)) { 5902f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 5912f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson old_tn = tn; 5922f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = halve(t, tn); 5932f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (IS_ERR(tn)) { 5942f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = old_tn; 5952f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 5962f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson t->stats.resize_node_skipped++; 5972f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#endif 5982f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson break; 5992f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 6002f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 60119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 602c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 60319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Only one child remains */ 60419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tn->empty_children == tnode_child_length(tn) - 1) 60519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson for (i = 0; i < tnode_child_length(tn); i++) { 60691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *n; 60719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 60891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson n = tn->child[i]; 6092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!n) 61091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 61191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 61291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* compress one level */ 61391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 6142373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson NODE_SET_PARENT(n, NULL); 61591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson tnode_free(tn); 61691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return n; 61719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 61819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 61919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return (struct node *) tn; 62019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 62119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 6222f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *inflate(struct trie *t, struct tnode *tn) 62319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 62419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *inode; 62519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *oldtnode = tn; 62619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int olen = tnode_child_length(tn); 62719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i; 62819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 6290c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("In inflate\n"); 63019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 63119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); 63219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 6330c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger if (!tn) 6342f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 6352f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6362f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson /* 637c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Preallocate and store tnodes before the actual work so we 638c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * don't get into an inconsistent state if memory allocation 639c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * fails. In case of failure we return the oldnode and inflate 6402f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson * of tnode is ignored. 6412f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson */ 64291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 64391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i++) { 6442f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i); 6452f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6462f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson if (inode && 6472f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson IS_TNODE(inode) && 6482f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->pos == oldtnode->pos + oldtnode->bits && 6492f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->bits > 1) { 6502f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson struct tnode *left, *right; 6512f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson t_key m = TKEY_GET_MASK(inode->pos, 1); 652c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 6532f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson left = tnode_new(inode->key&(~m), inode->pos + 1, 6542f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->bits - 1); 6552f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (!left) 6562f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson goto nomem; 65791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 6582f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson right = tnode_new(inode->key|m, inode->pos + 1, 6592f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->bits - 1); 6602f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6612f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (!right) { 6622f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free(left); 6632f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson goto nomem; 6642f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson } 6652f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6662f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson put_child(t, tn, 2*i, (struct node *) left); 6672f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson put_child(t, tn, 2*i+1, (struct node *) right); 6682f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 6692f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 6702f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 67191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i++) { 67219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *node = tnode_get_child(oldtnode, i); 67391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct tnode *left, *right; 67491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson int size, j; 675c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 67619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* An empty child */ 67719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (node == NULL) 67819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 67919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 68019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* A leaf or an internal node with skipped bits */ 68119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 682c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (IS_LEAF(node) || ((struct tnode *) node)->pos > 68319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->pos + tn->bits - 1) { 684c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits, 68519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1) == 0) 68619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i, node); 68719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson else 68819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i+1, node); 68919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 69019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 69119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 69219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* An internal node with two children */ 69319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson inode = (struct tnode *) node; 69419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 69519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (inode->bits == 1) { 69619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i, inode->child[0]); 69719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i+1, inode->child[1]); 69819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 69919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(inode); 70091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 70119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 70219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 70391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* An internal node with more than two children */ 70491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 70591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* We will replace this node 'inode' with two new 70691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * ones, 'left' and 'right', each with half of the 70791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * original children. The two new nodes will have 70891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * a position one bit further down the key and this 70991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * means that the "significant" part of their keys 71091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * (see the discussion near the top of this file) 71191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * will differ by one bit, which will be "0" in 71291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * left's key and "1" in right's key. Since we are 71391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * moving the key position by one step, the bit that 71491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * we are moving away from - the bit at position 71591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * (inode->pos) - is the one that will differ between 71691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * left and right. So... we synthesize that bit in the 71791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * two new keys. 71891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * The mask 'm' below will be a single "one" bit at 71991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * the position (inode->pos) 72091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 72119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 72291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Use the old key, but set the new significant 72391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * bit to zero. 72491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 7252f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 72691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson left = (struct tnode *) tnode_get_child(tn, 2*i); 72791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i, NULL); 7282f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 72991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(!left); 7302f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 73191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson right = (struct tnode *) tnode_get_child(tn, 2*i+1); 73291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i+1, NULL); 73319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 73491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(!right); 73519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 73691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson size = tnode_child_length(left); 73791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (j = 0; j < size; j++) { 73891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, left, j, inode->child[j]); 73991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, right, j, inode->child[j + size]); 74019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 74191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i, resize(t, left)); 74291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i+1, resize(t, right)); 74391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 74491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson tnode_free(inode); 74519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 74619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(oldtnode); 74719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tn; 7482f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonnomem: 7492f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson { 7502f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int size = tnode_child_length(tn); 7512f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int j; 7522f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 7530c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger for (j = 0; j < size; j++) 7542f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (tn->child[j]) 7552f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free((struct tnode *)tn->child[j]); 7562f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 7572f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free(tn); 7580c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 7592f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 7602f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson } 76119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 76219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7632f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *halve(struct trie *t, struct tnode *tn) 76419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 76519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *oldtnode = tn; 76619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *left, *right; 76719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i; 76819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int olen = tnode_child_length(tn); 76919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7700c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("In halve\n"); 771c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 772c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); 77319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7742f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (!tn) 7752f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 7762f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 7772f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson /* 778c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Preallocate and store tnodes before the actual work so we 779c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * don't get into an inconsistent state if memory allocation 780c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * fails. In case of failure we return the oldnode and halve 7812f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson * of tnode is ignored. 7822f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson */ 7832f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 78491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i += 2) { 7852f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson left = tnode_get_child(oldtnode, i); 7862f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson right = tnode_get_child(oldtnode, i+1); 787c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 7882f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson /* Two nonempty children */ 7890c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger if (left && right) { 7902f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson struct tnode *newn; 7910c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 7922f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson newn = tnode_new(left->key, tn->pos + tn->bits, 1); 7930c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 7940c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger if (!newn) 7952f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson goto nomem; 7960c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 7972f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson put_child(t, tn, i/2, (struct node *)newn); 7982f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 7992f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 8002f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 80119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 80291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i += 2) { 80391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct tnode *newBinNode; 80491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 80519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson left = tnode_get_child(oldtnode, i); 80619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson right = tnode_get_child(oldtnode, i+1); 807c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 80819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* At least one of the children is empty */ 80919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (left == NULL) { 81019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (right == NULL) /* Both are empty */ 81119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 81219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, i/2, right); 81391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 8140c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger } 81591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 81691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (right == NULL) { 81719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, i/2, left); 81891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 81991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 820c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 82119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Two nonempty children */ 82291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson newBinNode = (struct tnode *) tnode_get_child(tn, i/2); 82391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, i/2, NULL); 82491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, newBinNode, 0, left); 82591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, newBinNode, 1, right); 82691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, i/2, resize(t, newBinNode)); 82719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 82819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(oldtnode); 82919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tn; 8302f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonnomem: 8312f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson { 8322f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int size = tnode_child_length(tn); 8332f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int j; 8342f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 8350c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger for (j = 0; j < size; j++) 8362f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (tn->child[j]) 8372f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free((struct tnode *)tn->child[j]); 8382f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 8392f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free(tn); 8400c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 8412f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 8422f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson } 84319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 84419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 84591b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonstatic void trie_init(struct trie *t) 84619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 84791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!t) 84891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return; 84991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 85091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t->size = 0; 8512373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, NULL); 85291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t->revision = 0; 85319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 85491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson memset(&t->stats, 0, sizeof(struct trie_use_stats)); 85519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 85619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 85719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 858772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson/* readside must use rcu_read_lock currently dump routines 8592373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson via get_fa_head and dump */ 8602373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 861772cb712b1373d335ef2874ea357ec681edc754bRobert Olssonstatic struct leaf_info *find_leaf_info(struct leaf *l, int plen) 86219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 863772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct hlist_head *head = &l->list; 86419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node *node; 86519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li; 86619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8672373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_for_each_entry_rcu(li, node, head, hlist) 868c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (li->plen == plen) 86919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return li; 87091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 87119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 87219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 87319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 87419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline struct list_head * get_fa_head(struct leaf *l, int plen) 87519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 876772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct leaf_info *li = find_leaf_info(l, plen); 877c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 87891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!li) 87991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return NULL; 880c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 88191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return &li->falh; 88219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 88319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 88419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void insert_leaf_info(struct hlist_head *head, struct leaf_info *new) 88519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 8862373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct leaf_info *li = NULL, *last = NULL; 8872373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct hlist_node *node; 8882373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 8892373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (hlist_empty(head)) { 8902373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_add_head_rcu(&new->hlist, head); 8912373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } else { 8922373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_for_each_entry(li, node, head, hlist) { 8932373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (new->plen > li->plen) 8942373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson break; 8952373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 8962373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson last = li; 8972373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 8982373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (last) 8992373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_add_after_rcu(&last->hlist, &new->hlist); 9002373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson else 9012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_add_before_rcu(&new->hlist, &li->hlist); 9022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 90319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 90419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 9052373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* rcu_read_lock needs to be hold by caller from readside */ 9062373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 90719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct leaf * 90819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfib_find_node(struct trie *t, u32 key) 90919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 91019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos; 91119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tn; 91219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n; 91319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 91419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = 0; 9152373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson n = rcu_dereference(t->trie); 91619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 91719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (n != NULL && NODE_TYPE(n) == T_TNODE) { 91819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode *) n; 91991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 92019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 92191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 922c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 92391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = tn->pos + tn->bits; 92419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 92591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 92619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 92719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 92819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Case we have found a leaf. Compare prefixes */ 92919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 93091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) 93191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return (struct leaf *)n; 93291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 93319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 93419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 93519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 93619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct node *trie_rebalance(struct trie *t, struct tnode *tn) 93719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 93819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int wasfull; 93919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex, key; 94019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tp = NULL; 94119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 94219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = tn->key; 94319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 94419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (tn != NULL && NODE_PARENT(tn) != NULL) { 94519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 94619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = NODE_PARENT(tn); 94719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 94819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); 94919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode *) resize (t, (struct tnode *)tn); 95019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull); 95191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 952c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!NODE_PARENT(tn)) 95319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 95419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 95519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = NODE_PARENT(tn); 95619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 95719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Handle last (top) tnode */ 958c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (IS_TNODE(tn)) 95919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode*) resize(t, (struct tnode *)tn); 96019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 96119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return (struct node*) tn; 96219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 96319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 9642373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* only used from updater-side */ 9652373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 966f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssonstatic struct list_head * 967f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssonfib_insert_node(struct trie *t, int *err, u32 key, int plen) 96819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 96919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos, newpos; 97019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tp = NULL, *tn = NULL; 97119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n; 97219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 97319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int missbit; 974c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger struct list_head *fa_head = NULL; 97519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li; 97619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex; 97719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 97819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = 0; 979c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger n = t->trie; 98019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 981c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* If we point to NULL, stop. Either the tree is empty and we should 982c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * just put a new leaf in if, or we have reached an empty child slot, 98319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * and we should just put our new leaf in that. 984c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * If we point to a T_TNODE, check if it matches our key. Note that 985c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * a T_TNODE might be skipping any number of bits - its 'pos' need 98619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * not be the parent's 'pos'+'bits'! 98719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 988c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * If it does match the current key, get pos/bits from it, extract 98919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * the index from our key, push the T_TNODE and walk the tree. 99019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 99119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If it doesn't, we have to replace it with a new T_TNODE. 99219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 993c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * If we point to a T_LEAF, it might or might not have the same key 994c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * as we do. If it does, just change the value, update the T_LEAF's 995c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * value, and return it. 99619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If it doesn't, we need to replace it with a T_TNODE. 99719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 99819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 99919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (n != NULL && NODE_TYPE(n) == T_TNODE) { 100019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode *) n; 100191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1002c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger check_tnode(tn); 100391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1004c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 100519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = tn; 100691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = tn->pos + tn->bits; 100719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 100819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 10090c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger BUG_ON(n && NODE_PARENT(n) != tn); 101091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 101119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 101219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 101319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 101419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 101519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * n ----> NULL, LEAF or TNODE 101619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1017c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * tp is n's (parent) ----> NULL or TNODE 101819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 101919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 102091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(tp && IS_LEAF(tp)); 102119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 102219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Case 1: n is a leaf. Compare prefixes */ 102319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1024c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) { 102591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct leaf *l = (struct leaf *) n; 102691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 102719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson li = leaf_info_new(plen); 102891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1029c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!li) { 1030f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1031f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 1032f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 103319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 103419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = &li->falh; 103519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson insert_leaf_info(&l->list, li); 103619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto done; 103719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 103819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->size++; 103919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = leaf_new(); 104019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1041c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!l) { 1042f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1043f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 1044f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 104519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 104619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l->key = key; 104719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson li = leaf_info_new(plen); 104819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1049c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!li) { 1050f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson tnode_free((struct tnode *) l); 1051f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1052f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 1053f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 105419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 105519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = &li->falh; 105619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson insert_leaf_info(&l->list, li); 105719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 105819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (t->trie && n == NULL) { 105991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Case 2: n is NULL, and will just insert a new leaf */ 106019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 106119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson NODE_SET_PARENT(l, tp); 106219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 106391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 106491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, (struct tnode *)tp, cindex, (struct node *)l); 106591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 106691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */ 1067c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 1068c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Add a new tnode here 106919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * first tnode need some special handling 107019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 107119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 107219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tp) 107391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = tp->pos+tp->bits; 107419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson else 107591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = 0; 107691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1077c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n) { 107819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson newpos = tkey_mismatch(key, pos, n->key); 107919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = tnode_new(n->key, newpos, 1); 108091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 108119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson newpos = 0; 1082c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger tn = tnode_new(key, newpos, 1); /* First tnode */ 108319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 108419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1085c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!tn) { 1086f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson free_leaf_info(li); 1087f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson tnode_free((struct tnode *) l); 1088f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1089f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 109091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 109191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 109219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson NODE_SET_PARENT(tn, tp); 109319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 109491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson missbit = tkey_extract_bits(key, newpos, 1); 109519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, missbit, (struct node *)l); 109619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 1-missbit, n); 109719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1098c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tp) { 109919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 110019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, (struct tnode *)tp, cindex, (struct node *)tn); 110191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 11022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */ 110319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = tn; 110419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 110519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 110691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 110791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (tp && tp->pos + tp->bits > 32) 110878c6671a88313fd3c4364dc46e8c8186612616b8Stephen Hemminger printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n", 110919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp, tp->pos, tp->bits, key, plen); 111091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 111119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Rebalance the trie */ 11122373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 11132373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); 1114f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssondone: 1115f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson t->revision++; 111691b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonerr: 111719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return fa_head; 111819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 111919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 112019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int 112119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 112219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct nlmsghdr *nlhdr, struct netlink_skb_parms *req) 112319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 112419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 112519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa, *new_fa; 1126c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger struct list_head *fa_head = NULL; 112719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi; 112819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen = r->rtm_dst_len; 112919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int type = r->rtm_type; 113019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u8 tos = r->rtm_tos; 113119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u32 key, mask; 113219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int err; 113319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 113419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 113519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (plen > 32) 113619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 113719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 113819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = 0; 1139c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (rta->rta_dst) 114019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memcpy(&key, rta->rta_dst, 4); 114119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 114219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = ntohl(key); 114319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11440c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); 114519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 114691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mask = ntohl(inet_make_mask(plen)); 114719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1148c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (key & ~mask) 114919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 115019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 115119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = key & mask; 115219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 115391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson fi = fib_create_info(r, rta, nlhdr, &err); 115491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 115591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!fi) 115619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto err; 115719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 115819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = fib_find_node(t, key); 1159c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger fa = NULL; 116019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1161c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (l) { 116219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, plen); 116319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa = fib_find_alias(fa_head, tos, fi->fib_priority); 116419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 116519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 116619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Now fa, if non-NULL, points to the first fib alias 116719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * with the same keys [prefix,tos,priority], if such key already 116819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * exists or to the node before which we will insert new one. 116919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 117019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If fa is NULL, we will need to allocate a new one and 117119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * insert to the head of f. 117219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 117319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If f is NULL, no fib node matched the destination key 117419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * and we need to allocate a new one of those as well. 117519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 117619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 117791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (fa && fa->fa_info->fib_priority == fi->fib_priority) { 117819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa_orig; 117919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 118019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson err = -EEXIST; 118119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (nlhdr->nlmsg_flags & NLM_F_EXCL) 118219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 118319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 118419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (nlhdr->nlmsg_flags & NLM_F_REPLACE) { 118519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi_drop; 118619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u8 state; 118719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11882373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson err = -ENOBUFS; 11892373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL); 11902373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (new_fa == NULL) 11912373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson goto out; 119219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 119319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fi_drop = fa->fa_info; 11942373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_tos = fa->fa_tos; 11952373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_info = fi; 11962373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_type = type; 11972373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_scope = r->rtm_scope; 119819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson state = fa->fa_state; 11992373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_state &= ~FA_S_ACCESSED; 120019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_replace_rcu(&fa->fa_list, &new_fa->fa_list); 12022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson alias_free_mem_rcu(fa); 120319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 120419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_release_info(fi_drop); 120519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (state & FA_S_ACCESSED) 120691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson rt_cache_flush(-1); 120719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 120891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto succeeded; 120919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 121019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Error if we find a perfect match which 121119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * uses the same scope, type, and nexthop 121219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * information. 121319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 121419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_orig = fa; 121519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) { 121619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_tos != tos) 121719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 121819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_info->fib_priority != fi->fib_priority) 121919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 122019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_type == type && 122119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_scope == r->rtm_scope && 122219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_info == fi) { 122319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 122419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 122519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 122619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!(nlhdr->nlmsg_flags & NLM_F_APPEND)) 122719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa = fa_orig; 122819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 122919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson err = -ENOENT; 123091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!(nlhdr->nlmsg_flags & NLM_F_CREATE)) 123119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 123219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 123319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson err = -ENOBUFS; 123419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL); 123519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (new_fa == NULL) 123619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 123719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 123819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_info = fi; 123919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_tos = tos; 124019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_type = type; 124119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_scope = r->rtm_scope; 124219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_state = 0; 124319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 124419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Insert new entry to the list. 124519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 124619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1247c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!fa_head) { 1248f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson fa_head = fib_insert_node(t, &err, key, plen); 1249f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson err = 0; 1250c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (err) 1251f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto out_free_new_fa; 1252f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 125319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12542373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_add_tail_rcu(&new_fa->fa_list, 12552373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson (fa ? &fa->fa_list : fa_head)); 125619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 125719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson rt_cache_flush(-1); 125819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req); 125919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonsucceeded: 126019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 1261f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson 1262f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssonout_free_new_fa: 1263f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson kmem_cache_free(fn_alias_kmem, new_fa); 126419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout: 126519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_release_info(fi); 126691b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonerr: 126719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return err; 126819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 126919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12702373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 1271772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson/* should be called with rcu_read_lock */ 12720c7770c740156c8802c23d24fc094d06967d997dStephen Hemmingerstatic inline int check_leaf(struct trie *t, struct leaf *l, 12730c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger t_key key, int *plen, const struct flowi *flp, 127406c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy struct fib_result *res) 127519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 127606c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy int err, i; 127719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key mask; 127819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li; 127919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_head *hhead = &l->list; 128019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node *node; 1281c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 12822373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_for_each_entry_rcu(li, node, hhead, hlist) { 128319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i = li->plen; 128419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson mask = ntohl(inet_make_mask(i)); 1285c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (l->key != (key & mask)) 128619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 128719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 128806c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy if ((err = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) <= 0) { 128919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson *plen = i; 129019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 129119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.semantic_match_passed++; 129219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 129306c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy return err; 129419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 129519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 129619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.semantic_match_miss++; 129719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 129819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 129906c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy return 1; 130019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 130119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 130219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int 130319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) 130419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 130519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 130619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen, ret = 0; 130719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n; 130819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *pn; 130919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos, bits; 131091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key = ntohl(flp->fl4_dst); 131119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int chopped_off; 131219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex = 0; 131319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int current_prefix_length = KEYLENGTH; 131491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct tnode *cn; 131591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key node_prefix, key_prefix, pref_mismatch; 131691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson int mp; 131791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 13182373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_lock(); 131991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 13202373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson n = rcu_dereference(t->trie); 1321c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!n) 132219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto failed; 132319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 132419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 132519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.gets++; 132619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 132719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 132819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Just a leaf? */ 132919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (IS_LEAF(n)) { 133006c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) 133119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto found; 133219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto failed; 133319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 133419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pn = (struct tnode *) n; 133519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off = 0; 1336c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 133791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while (pn) { 133819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = pn->pos; 133919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson bits = pn->bits; 134019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1341c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!chopped_off) 134219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits); 134319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 134419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(pn, cindex); 134519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 134619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (n == NULL) { 134719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 134819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.null_node_hit++; 134919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 135019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto backtrace; 135119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 135219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 135391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (IS_LEAF(n)) { 135491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) 135591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto found; 135691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson else 135791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto backtrace; 135891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 135991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 136019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define HL_OPTIMIZE 136119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef HL_OPTIMIZE 136291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cn = (struct tnode *)n; 136319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 136491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* 136591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * It's a tnode, and we can do some extra checks here if we 136691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * like, to avoid descending into a dead-end branch. 136791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * This tnode is in the parent's child array at index 136891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * key[p_pos..p_pos+p_bits] but potentially with some bits 136991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * chopped off, so in reality the index may be just a 137091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * subprefix, padded with zero at the end. 137191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * We can also take a look at any skipped bits in this 137291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tnode - everything up to p_pos is supposed to be ok, 137391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * and the non-chopped bits of the index (se previous 137491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * paragraph) are also guaranteed ok, but the rest is 137591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * considered unknown. 137691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * 137791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * The skipped bits are key[pos+bits..cn->pos]. 137891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 137919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 138091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* If current_prefix_length < pos+bits, we are already doing 138191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * actual prefix matching, which means everything from 138291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * pos+(bits-chopped_off) onward must be zero along some 138391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * branch of this subtree - otherwise there is *no* valid 138491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * prefix present. Here we can only check the skipped 138591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * bits. Remember, since we have already indexed into the 138691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * parent's child array, we know that the bits we chopped of 138791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * *are* zero. 138891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 138919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 139091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */ 139119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 139291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (current_prefix_length < pos+bits) { 139391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (tkey_extract_bits(cn->key, current_prefix_length, 139491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cn->pos - current_prefix_length) != 0 || 139591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson !(cn->child[0])) 139691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto backtrace; 139791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 139819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 139991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* 140091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * If chopped_off=0, the index is fully validated and we 140191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * only need to look at the skipped bits for this, the new, 140291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tnode. What we actually want to do is to find out if 140391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * these skipped bits match our key perfectly, or if we will 140491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * have to count on finding a matching prefix further down, 140591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * because if we do, we would like to have some way of 140691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * verifying the existence of such a prefix at this point. 140791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 140819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 140991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* The only thing we can do at this point is to verify that 141091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * any such matching prefix can indeed be a prefix to our 141191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * key, and if the bits in the node we are inspecting that 141291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * do not match our key are not ZERO, this cannot be true. 141391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * Thus, find out where there is a mismatch (before cn->pos) 141491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * and verify that all the mismatching bits are zero in the 141591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * new tnode's key. 141691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 141719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 141891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Note: We aren't very concerned about the piece of the key 141991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * that precede pn->pos+pn->bits, since these have already been 142091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * checked. The bits after cn->pos aren't checked since these are 142191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * by definition "unknown" at this point. Thus, what we want to 142291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * see is if we are about to enter the "prefix matching" state, 142391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * and in that case verify that the skipped bits that will prevail 142491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * throughout this subtree are zero, as they have to be if we are 142591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * to find a matching prefix. 142691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 142791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 142891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson node_prefix = MASK_PFX(cn->key, cn->pos); 142991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson key_prefix = MASK_PFX(key, cn->pos); 143091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pref_mismatch = key_prefix^node_prefix; 143191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mp = 0; 143291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 143391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* In short: If skipped bits in this node do not match the search 143491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * key, enter the "prefix matching" state.directly. 143591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 143691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (pref_mismatch) { 143791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) { 143891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mp++; 143991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pref_mismatch = pref_mismatch <<1; 144091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 144191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp); 144291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 144391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (key_prefix != 0) 144491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto backtrace; 144591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 144691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (current_prefix_length >= cn->pos) 144791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson current_prefix_length = mp; 1448c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger } 144991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#endif 145091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pn = (struct tnode *)n; /* Descend */ 145191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson chopped_off = 0; 145291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 145391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 145419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonbacktrace: 145519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off++; 145619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 145719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* As zero don't change the child key (cindex) */ 145891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1)))) 145919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off++; 146019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 146119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Decrease current_... with bits chopped off */ 146219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (current_prefix_length > pn->pos + pn->bits - chopped_off) 146319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson current_prefix_length = pn->pos + pn->bits - chopped_off; 146491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 146519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 1466c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Either we do the actual chop off according or if we have 146719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * chopped off all bits in this tnode walk up to our parent. 146819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 146919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 147091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (chopped_off <= pn->bits) { 147119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex &= ~(1 << (chopped_off-1)); 147291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 1473c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (NODE_PARENT(pn) == NULL) 147419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto failed; 147591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 147619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Get Child's index */ 147719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits); 147819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pn = NODE_PARENT(pn); 147919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off = 0; 148019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 148119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 148219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.backtrack++; 148319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 148419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto backtrace; 1485c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger } 148619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 148719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfailed: 1488c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger ret = 1; 148919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfound: 14902373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 149119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return ret; 149219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 149319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 14942373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* only called from updater side */ 149519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int trie_leaf_remove(struct trie *t, t_key key) 149619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 149719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex; 149819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tp = NULL; 149919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n = t->trie; 150019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 150119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15020c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("entering trie_leaf_remove(%p)\n", n); 150319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 150419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Note that in the case skipped bits, those bits are *not* checked! 1505c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * When we finish this, we will have NULL or a T_LEAF, and the 150619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * T_LEAF may or may not match our key. 150719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 150819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 150991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while (n != NULL && IS_TNODE(n)) { 151019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tn = (struct tnode *) n; 151119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 151219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); 151319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15140c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger BUG_ON(n && NODE_PARENT(n) != tn); 151591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 151619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = (struct leaf *) n; 151719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1518c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!n || !tkey_equals(l->key, key)) 151919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 1520c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 1521c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 1522c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Key found. 1523c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Remove the leaf and rebalance the tree 152419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 152519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 152619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->revision++; 152719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->size--; 152819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15292373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson preempt_disable(); 153019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = NODE_PARENT(n); 153119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free((struct tnode *) n); 153219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1533c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tp) { 153419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 153519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, (struct tnode *)tp, cindex, NULL); 15362373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); 153791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 15382373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, NULL); 15392373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson preempt_enable(); 154019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 154119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 1; 154219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 154319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 154419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int 154519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 154691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct nlmsghdr *nlhdr, struct netlink_skb_parms *req) 154719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 154819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 154919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u32 key, mask; 155019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen = r->rtm_dst_len; 155119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u8 tos = r->rtm_tos; 155219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa, *fa_to_delete; 155319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head *fa_head; 155419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 155591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct leaf_info *li; 155691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 155719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1558c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (plen > 32) 155919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 156019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 156119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = 0; 1562c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (rta->rta_dst) 156319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memcpy(&key, rta->rta_dst, 4); 156419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 156519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = ntohl(key); 156691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mask = ntohl(inet_make_mask(plen)); 156719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1568c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (key & ~mask) 156919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 157019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 157119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = key & mask; 157219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = fib_find_node(t, key); 157319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1574c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!l) 157519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -ESRCH; 157619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 157719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, plen); 157819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa = fib_find_alias(fa_head, tos, 0); 157919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 158019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!fa) 158119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -ESRCH; 158219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15830c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t); 158419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 158519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_to_delete = NULL; 158619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = fa->fa_list.prev; 15872373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 158819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson list_for_each_entry(fa, fa_head, fa_list) { 158919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi = fa->fa_info; 159019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 159119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_tos != tos) 159219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 159319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 159419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if ((!r->rtm_type || 159519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_type == r->rtm_type) && 159619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson (r->rtm_scope == RT_SCOPE_NOWHERE || 159719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_scope == r->rtm_scope) && 159819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson (!r->rtm_protocol || 159919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fi->fib_protocol == r->rtm_protocol) && 160019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_nh_match(r, nlhdr, rta, fi) == 0) { 160119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_to_delete = fa; 160219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 160319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 160419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 160519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 160691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!fa_to_delete) 160791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return -ESRCH; 160819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 160991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson fa = fa_to_delete; 161091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req); 161191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 161291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson l = fib_find_node(t, key); 1613772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson li = find_leaf_info(l, plen); 161419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16152373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_del_rcu(&fa->fa_list); 161619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 161791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (list_empty(fa_head)) { 16182373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_del_rcu(&li->hlist); 161991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson free_leaf_info(li); 16202373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 162119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 162291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (hlist_empty(&l->list)) 162391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson trie_leaf_remove(t, key); 162419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 162591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (fa->fa_state & FA_S_ACCESSED) 162691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson rt_cache_flush(-1); 162719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16282373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson fib_release_info(fa->fa_info); 16292373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson alias_free_mem_rcu(fa); 163091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return 0; 163119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 163219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 163319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int trie_flush_list(struct trie *t, struct list_head *head) 163419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 163519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa, *fa_node; 163619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int found = 0; 163719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 163819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson list_for_each_entry_safe(fa, fa_node, head, fa_list) { 163919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi = fa->fa_info; 164019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16412373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (fi && (fi->fib_flags & RTNH_F_DEAD)) { 16422373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_del_rcu(&fa->fa_list); 16432373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson fib_release_info(fa->fa_info); 16442373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson alias_free_mem_rcu(fa); 164519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson found++; 164619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 164719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 164819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return found; 164919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 165019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 165119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int trie_flush_leaf(struct trie *t, struct leaf *l) 165219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 165319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int found = 0; 165419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_head *lih = &l->list; 165519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node *node, *tmp; 165619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li = NULL; 165719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 165819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson hlist_for_each_entry_safe(li, node, tmp, lih, hlist) { 165919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson found += trie_flush_list(t, &li->falh); 166019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 166119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (list_empty(&li->falh)) { 16622373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_del_rcu(&li->hlist); 166319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson free_leaf_info(li); 166419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 166519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 166619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return found; 166719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 166819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16692373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* rcu_read_lock needs to be hold by caller from readside */ 16702373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 167119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf) 167219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 167319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *c = (struct node *) thisleaf; 167419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *p; 167519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int idx; 16762373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct node *trie = rcu_dereference(t->trie); 167719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1678c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (c == NULL) { 16792373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (trie == NULL) 168019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 168119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16822373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (IS_LEAF(trie)) /* trie w. just a leaf */ 16832373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return (struct leaf *) trie; 168419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16852373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson p = (struct tnode*) trie; /* Start */ 168691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 168719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson p = (struct tnode *) NODE_PARENT(c); 1688c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 168919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (p) { 169019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos, last; 169119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 169219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Find the next child of the parent */ 1693c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (c) 1694c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits); 1695c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger else 169619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = 0; 169719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 169819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson last = 1 << p->bits; 169991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (idx = pos; idx < last ; idx++) { 17002373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson c = rcu_dereference(p->child[idx]); 17012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 17022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!c) 170391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 170491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 170591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Decend if tnode */ 17062373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson while (IS_TNODE(c)) { 17072373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson p = (struct tnode *) c; 17082373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson idx = 0; 170991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 171091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Rightmost non-NULL branch */ 171191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (p && IS_TNODE(p)) 17122373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson while (!(c = rcu_dereference(p->child[idx])) 17132373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson && idx < (1<<p->bits)) idx++; 171491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 171591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Done with this tnode? */ 17162373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (idx >= (1 << p->bits) || !c) 171791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto up; 171819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 17192373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return (struct leaf *) c; 172019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 172119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonup: 172219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* No more children go up one step */ 172391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson c = (struct node *) p; 172419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson p = (struct tnode *) NODE_PARENT(p); 172519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 172619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; /* Ready. Root of trie */ 172719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 172819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 172919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int fn_trie_flush(struct fib_table *tb) 173019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 173119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 173219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *ll = NULL, *l = NULL; 173319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int found = 0, h; 173419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 173519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->revision++; 173619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 173791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (h = 0; (l = nextleaf(t, l)) != NULL; h++) { 173819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson found += trie_flush_leaf(t, l); 173919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 174019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (ll && hlist_empty(&ll->list)) 174119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_leaf_remove(t, ll->key); 174219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ll = l; 174319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 174419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 174519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (ll && hlist_empty(&ll->list)) 174619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_leaf_remove(t, ll->key); 174719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 17480c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("trie_flush found=%d\n", found); 174919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return found; 175019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 175119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 175291b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonstatic int trie_last_dflt = -1; 175319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 175419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void 175519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) 175619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 175719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 175819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int order, last_idx; 175919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi = NULL; 176019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *last_resort; 176119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa = NULL; 176219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head *fa_head; 176319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 176419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 176519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson last_idx = -1; 176619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson last_resort = NULL; 176719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson order = -1; 176819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 17692373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_lock(); 1770c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 177119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = fib_find_node(t, 0); 1772c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!l) 177319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 177419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 177519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, 0); 1776c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!fa_head) 177719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 177819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1779c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (list_empty(fa_head)) 178019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 178119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 17822373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_for_each_entry_rcu(fa, fa_head, fa_list) { 178319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *next_fi = fa->fa_info; 178491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 178519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_scope != res->scope || 178619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_type != RTN_UNICAST) 178719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 178891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 178919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (next_fi->fib_priority > res->fi->fib_priority) 179019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 179119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!next_fi->fib_nh[0].nh_gw || 179219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK) 179319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 179419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_state |= FA_S_ACCESSED; 179591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 179619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fi == NULL) { 179719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (next_fi != res->fi) 179819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 179919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } else if (!fib_detect_death(fi, order, &last_resort, 180019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson &last_idx, &trie_last_dflt)) { 180119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (res->fi) 180219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_info_put(res->fi); 180319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson res->fi = fi; 180419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson atomic_inc(&fi->fib_clntref); 180519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = order; 180619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 180719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 180819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fi = next_fi; 180919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson order++; 181019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 181119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (order <= 0 || fi == NULL) { 181219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = -1; 181319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 181419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 181519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 181619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) { 181719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (res->fi) 181819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_info_put(res->fi); 181919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson res->fi = fi; 182019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson atomic_inc(&fi->fib_clntref); 182119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = order; 182219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 182319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 182419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (last_idx >= 0) { 182519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (res->fi) 182619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_info_put(res->fi); 182719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson res->fi = last_resort; 182819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (last_resort) 182919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson atomic_inc(&last_resort->fib_clntref); 183019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 183119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = last_idx; 183219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson out:; 18332373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 183419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 183519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1836c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb, 183719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct sk_buff *skb, struct netlink_callback *cb) 183819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 183919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i, s_i; 184019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa; 184119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 184291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson u32 xkey = htonl(key); 184319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 184491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson s_i = cb->args[3]; 184519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i = 0; 184619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 18472373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson /* rcu_read_lock is hold by caller */ 18482373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 18492373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_for_each_entry_rcu(fa, fah, fa_list) { 185019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (i < s_i) { 185119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i++; 185219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 185319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 185478c6671a88313fd3c4364dc46e8c8186612616b8Stephen Hemminger BUG_ON(!fa->fa_info); 185519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 185619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid, 185719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->nlh->nlmsg_seq, 185819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson RTM_NEWROUTE, 185919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_id, 186019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_type, 186119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_scope, 186219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson &xkey, 186319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson plen, 186419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_tos, 186590f66914c89b0be63548d4387d1211280aa7bc8eDavid S. Miller fa->fa_info, 0) < 0) { 186619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->args[3] = i; 186719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -1; 186891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 186919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i++; 187019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 187191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cb->args[3] = i; 187219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return skb->len; 187319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 187419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1875c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb, 187619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct netlink_callback *cb) 187719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 187819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int h, s_h; 187919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head *fa_head; 188019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l = NULL; 188119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 188291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson s_h = cb->args[2]; 188319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 188491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (h = 0; (l = nextleaf(t, l)) != NULL; h++) { 188519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (h < s_h) 188619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 188719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (h > s_h) 188819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(&cb->args[3], 0, 188919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson sizeof(cb->args) - 3*sizeof(cb->args[0])); 189019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 189119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, plen); 189291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1893c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!fa_head) 189419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 189519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1896c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (list_empty(fa_head)) 189719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 189819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 189919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) { 190091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cb->args[2] = h; 190119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -1; 190219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 190319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 190491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cb->args[2] = h; 190519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return skb->len; 190619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 190719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 190819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb) 190919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 191019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int m, s_m; 191119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 191219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 191319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson s_m = cb->args[1]; 191419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 19152373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_lock(); 191691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (m = 0; m <= 32; m++) { 191719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (m < s_m) 191819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 191919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (m > s_m) 192019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(&cb->args[2], 0, 192191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson sizeof(cb->args) - 2*sizeof(cb->args[0])); 192219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 192319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) { 192419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->args[1] = m; 192519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 192619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 192719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 19282373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 192919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->args[1] = m; 193019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return skb->len; 193191b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonout: 19322373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 193319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -1; 193419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 193519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 193619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* Fix more generic FIB names for init later */ 193719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 193819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_MULTIPLE_TABLES 193919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct fib_table * fib_hash_init(int id) 194019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#else 194119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct fib_table * __init fib_hash_init(int id) 194219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 194319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 194419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_table *tb; 194519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t; 194619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 194719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fn_alias_kmem == NULL) 194819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fn_alias_kmem = kmem_cache_create("ip_fib_alias", 194919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson sizeof(struct fib_alias), 195019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 0, SLAB_HWCACHE_ALIGN, 195119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson NULL, NULL); 195219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 195319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie), 195419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson GFP_KERNEL); 195519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tb == NULL) 195619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 195719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 195819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_id = id; 195919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_lookup = fn_trie_lookup; 196019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_insert = fn_trie_insert; 196119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_delete = fn_trie_delete; 196219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_flush = fn_trie_flush; 196319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_select_default = fn_trie_select_default; 196419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_dump = fn_trie_dump; 196519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(tb->tb_data, 0, sizeof(struct trie)); 196619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 196719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t = (struct trie *) tb->tb_data; 196819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 196919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_init(t); 197019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1971c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (id == RT_TABLE_LOCAL) 197291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson trie_local = t; 1973c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger else if (id == RT_TABLE_MAIN) 197491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson trie_main = t; 197519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 197619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (id == RT_TABLE_LOCAL) 197778c6671a88313fd3c4364dc46e8c8186612616b8Stephen Hemminger printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION); 197819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 197919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tb; 198019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 198119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1982cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#ifdef CONFIG_PROC_FS 1983cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* Depth first Trie walk iterator */ 1984cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstruct fib_trie_iter { 1985cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *tnode; 1986cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct trie *trie; 1987cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned index; 1988cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned depth; 1989cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger}; 199019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1991cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct node *fib_trie_get_next(struct fib_trie_iter *iter) 199219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 1993cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *tn = iter->tnode; 1994cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned cindex = iter->index; 1995cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *p; 199619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1997cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger pr_debug("get_next iter={node=%p index=%d depth=%d}\n", 1998cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode, iter->index, iter->depth); 1999cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerrescan: 2000cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger while (cindex < (1<<tn->bits)) { 2001cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n = tnode_get_child(tn, cindex); 200219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2003cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (n) { 2004cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_LEAF(n)) { 2005cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode = tn; 2006cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->index = cindex + 1; 2007cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } else { 2008cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* push down one level */ 2009cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode = (struct tnode *) n; 2010cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->index = 0; 2011cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger ++iter->depth; 2012cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2013cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 2014cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 201519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2016cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger ++cindex; 2017cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 201891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2019cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* Current node exhausted, pop back up */ 2020cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger p = NODE_PARENT(tn); 2021cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (p) { 2022cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1; 2023cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger tn = p; 2024cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger --iter->depth; 2025cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto rescan; 202619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 2027cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2028cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* got root? */ 2029cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return NULL; 203019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 203119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2032cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct node *fib_trie_get_first(struct fib_trie_iter *iter, 2033cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct trie *t) 203419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2035cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n = rcu_dereference(t->trie); 203619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2037cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (n && IS_TNODE(n)) { 2038cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode = (struct tnode *) n; 2039cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->trie = t; 2040cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->index = 0; 20411d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson iter->depth = 1; 2042cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 204391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 2044cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return NULL; 2045cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 204691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2047cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void trie_collect_stats(struct trie *t, struct trie_stat *s) 2048cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2049cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n; 2050cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter iter; 205191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2052cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(s, 0, sizeof(*s)); 205391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2054cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rcu_read_lock(); 2055cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (n = fib_trie_get_first(&iter, t); n; 2056cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger n = fib_trie_get_next(&iter)) { 2057cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_LEAF(n)) { 2058cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->leaves++; 2059cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->totdepth += iter.depth; 2060cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (iter.depth > s->maxdepth) 2061cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->maxdepth = iter.depth; 2062cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } else { 2063cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger const struct tnode *tn = (const struct tnode *) n; 2064cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger int i; 2065cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2066cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->tnodes++; 2067cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->nodesizes[tn->bits]++; 2068cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i = 0; i < (1<<tn->bits); i++) 2069cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!tn->child[i]) 2070cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->nullpointers++; 207119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 207219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 20732373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 207419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 207519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2076cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* 2077cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * This outputs /proc/net/fib_triestats 2078cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger */ 2079cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void trie_show_stats(struct seq_file *seq, struct trie_stat *stat) 208019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2081cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned i, max, pointers, bytes, avdepth; 2082c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 2083cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (stat->leaves) 2084cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger avdepth = stat->totdepth*100 / stat->leaves; 2085cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger else 2086cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger avdepth = 0; 208791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2088cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tAver depth: %d.%02d\n", avdepth / 100, avdepth % 100 ); 2089cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth); 209091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2091cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tLeaves: %u\n", stat->leaves); 209291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2093cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger bytes = sizeof(struct leaf) * stat->leaves; 2094cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes); 2095cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger bytes += sizeof(struct tnode) * stat->tnodes; 209619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2097cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger max = MAX_CHILDS-1; 2098cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger while (max >= 0 && stat->nodesizes[max] == 0) 2099cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger max--; 210019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2101cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger pointers = 0; 2102cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i = 1; i <= max; i++) 2103cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (stat->nodesizes[i] != 0) { 2104cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, " %d: %d", i, stat->nodesizes[i]); 2105cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger pointers += (1<<i) * stat->nodesizes[i]; 2106cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2107cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_putc(seq, '\n'); 2108cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tPointers: %d\n", pointers); 21092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 2110cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger bytes += sizeof(struct node *) * pointers; 2111cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers); 2112cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Total size: %d kB\n", (bytes + 1023) / 1024); 21132373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 2114cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#ifdef CONFIG_IP_FIB_TRIE_STATS 2115cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Counters:\n---------\n"); 2116cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"gets = %d\n", t->stats.gets); 2117cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"backtracks = %d\n", t->stats.backtrack); 2118cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed); 2119cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss); 2120cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit); 2121cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped); 2122cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#ifdef CLEAR_STATS 2123cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(&(t->stats), 0, sizeof(t->stats)); 2124cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#endif 2125cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#endif /* CONFIG_IP_FIB_TRIE_STATS */ 2126cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 212719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2128cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_triestat_seq_show(struct seq_file *seq, void *v) 2129cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2130cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct trie_stat *stat; 213191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2132cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger stat = kmalloc(sizeof(*stat), GFP_KERNEL); 2133cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!stat) 2134cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return -ENOMEM; 213591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2136cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n", 2137cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger sizeof(struct leaf), sizeof(struct tnode)); 213891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2139cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (trie_local) { 2140cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Local:\n"); 2141cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_collect_stats(trie_local, stat); 2142cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_show_stats(seq, stat); 2143cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 214491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2145cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (trie_main) { 2146cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Main:\n"); 2147cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_collect_stats(trie_main, stat); 2148cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_show_stats(seq, stat); 214919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 2150cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger kfree(stat); 215119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2152cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 215319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 215419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2155cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_triestat_seq_open(struct inode *inode, struct file *file) 215619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2157cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return single_open(file, fib_triestat_seq_show, NULL); 215819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 215919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2160cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct file_operations fib_triestat_fops = { 2161cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .owner = THIS_MODULE, 2162cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .open = fib_triestat_seq_open, 2163cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .read = seq_read, 2164cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .llseek = seq_lseek, 2165cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .release = single_release, 2166cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger}; 2167cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2168cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct node *fib_trie_get_idx(struct fib_trie_iter *iter, 2169cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger loff_t pos) 217019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2171cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger loff_t idx = 0; 2172cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n; 2173cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2174cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (n = fib_trie_get_first(iter, trie_local); 2175cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger n; ++idx, n = fib_trie_get_next(iter)) { 2176cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (pos == idx) 2177cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 2178cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2179cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2180cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (n = fib_trie_get_first(iter, trie_main); 2181cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger n; ++idx, n = fib_trie_get_next(iter)) { 2182cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (pos == idx) 2183cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 2184cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 218519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 218619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 218719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2188cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos) 218919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2190cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rcu_read_lock(); 2191cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (*pos == 0) 219291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return SEQ_START_TOKEN; 2193cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return fib_trie_get_idx(seq->private, *pos - 1); 219419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 219519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2196cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos) 219719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2198cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter *iter = seq->private; 2199cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger void *l = v; 2200cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 220119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ++*pos; 220291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (v == SEQ_START_TOKEN) 2203cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return fib_trie_get_idx(iter, 0); 220419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2205cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger v = fib_trie_get_next(iter); 2206cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger BUG_ON(v == l); 2207cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (v) 2208cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return v; 220919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2210cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* continue scan in next trie */ 2211cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (iter->trie == trie_local) 2212cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return fib_trie_get_first(iter, trie_main); 221319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2214cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return NULL; 2215cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 221619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2217cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void fib_trie_seq_stop(struct seq_file *seq, void *v) 221819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2219cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rcu_read_unlock(); 2220cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 222191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2222cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void seq_indent(struct seq_file *seq, int n) 2223cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2224cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger while (n-- > 0) seq_puts(seq, " "); 2225cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 222619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2227cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic inline const char *rtn_scope(enum rt_scope_t s) 2228cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2229cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger static char buf[32]; 223019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2231cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger switch(s) { 2232cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_UNIVERSE: return "universe"; 2233cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_SITE: return "site"; 2234cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_LINK: return "link"; 2235cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_HOST: return "host"; 2236cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_NOWHERE: return "nowhere"; 2237cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger default: 2238cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(buf, sizeof(buf), "scope=%d", s); 2239cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return buf; 2240cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2241cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 224219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2243cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic const char *rtn_type_names[__RTN_MAX] = { 2244cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_UNSPEC] = "UNSPEC", 2245cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_UNICAST] = "UNICAST", 2246cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_LOCAL] = "LOCAL", 2247cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_BROADCAST] = "BROADCAST", 2248cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_ANYCAST] = "ANYCAST", 2249cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_MULTICAST] = "MULTICAST", 2250cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_BLACKHOLE] = "BLACKHOLE", 2251cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_UNREACHABLE] = "UNREACHABLE", 2252cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_PROHIBIT] = "PROHIBIT", 2253cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_THROW] = "THROW", 2254cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_NAT] = "NAT", 2255cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_XRESOLVE] = "XRESOLVE", 2256cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger}; 225719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2258cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic inline const char *rtn_type(unsigned t) 2259cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2260cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger static char buf[32]; 226119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2262cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (t < __RTN_MAX && rtn_type_names[t]) 2263cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return rtn_type_names[t]; 2264cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(buf, sizeof(buf), "type %d", t); 2265cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return buf; 226619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 226719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2268cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* Pretty print the trie */ 2269cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_trie_seq_show(struct seq_file *seq, void *v) 227019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2271cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger const struct fib_trie_iter *iter = seq->private; 2272cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n = v; 2273c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 2274cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (v == SEQ_START_TOKEN) 2275cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 227619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2277cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_TNODE(n)) { 2278cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *tn = (struct tnode *) n; 2279cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger t_key prf = ntohl(MASK_PFX(tn->key, tn->pos)); 228091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2281cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!NODE_PARENT(n)) { 2282cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (iter->trie == trie_local) 2283cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_puts(seq, "<local>:\n"); 2284cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger else 2285cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_puts(seq, "<main>:\n"); 22861d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson } 22871d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson seq_indent(seq, iter->depth-1); 22881d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n", 22891d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson NIPQUAD(prf), tn->pos, tn->bits, tn->full_children, 22901d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson tn->empty_children); 22911d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson 2292cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } else { 2293cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct leaf *l = (struct leaf *) n; 2294cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger int i; 2295cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger u32 val = ntohl(l->key); 2296cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2297cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_indent(seq, iter->depth); 2298cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val)); 2299cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i = 32; i >= 0; i--) { 2300772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct leaf_info *li = find_leaf_info(l, i); 2301cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (li) { 2302cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_alias *fa; 2303cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger list_for_each_entry_rcu(fa, &li->falh, fa_list) { 2304cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_indent(seq, iter->depth+1); 2305cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, " /%d %s %s", i, 2306cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rtn_scope(fa->fa_scope), 2307cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rtn_type(fa->fa_type)); 2308cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fa->fa_tos) 2309cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "tos =%d\n", 2310cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fa->fa_tos); 2311cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_putc(seq, '\n'); 2312cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2313cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2314cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 231519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 2316cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 231719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 231819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 231919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2320cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct seq_operations fib_trie_seq_ops = { 2321cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .start = fib_trie_seq_start, 2322cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .next = fib_trie_seq_next, 2323cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .stop = fib_trie_seq_stop, 2324cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .show = fib_trie_seq_show, 232519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 232619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2327cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_trie_seq_open(struct inode *inode, struct file *file) 232819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 232919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct seq_file *seq; 233019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int rc = -ENOMEM; 2331cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL); 233219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2333cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!s) 2334cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out; 2335cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2336cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rc = seq_open(file, &fib_trie_seq_ops); 233719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (rc) 233819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out_kfree; 233919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2340cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq = file->private_data; 2341cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq->private = s; 2342cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(s, 0, sizeof(*s)); 234319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout: 234419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return rc; 234519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout_kfree: 2346cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger kfree(s); 234719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 234819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 234919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2350cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct file_operations fib_trie_fops = { 2351cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .owner = THIS_MODULE, 2352cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .open = fib_trie_seq_open, 2353cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .read = seq_read, 2354cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .llseek = seq_lseek, 2355c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger .release = seq_release_private, 235619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 235719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2358cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi) 235919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2360cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger static unsigned type2flags[RTN_MAX + 1] = { 2361cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [7] = RTF_REJECT, [8] = RTF_REJECT, 2362cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger }; 2363cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned flags = type2flags[type]; 236419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2365cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fi && fi->fib_nh->nh_gw) 2366cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger flags |= RTF_GATEWAY; 2367cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (mask == 0xFFFFFFFF) 2368cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger flags |= RTF_HOST; 2369cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger flags |= RTF_UP; 2370cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return flags; 237119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 237219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2373cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* 2374cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * This outputs /proc/net/route. 2375cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * The format of the file is not supposed to be changed 2376cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * and needs to be same as fib_hash output to avoid breaking 2377cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * legacy utilities 2378cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger */ 2379cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_route_seq_show(struct seq_file *seq, void *v) 238019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2381cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct leaf *l = v; 2382cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger int i; 2383cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger char bf[128]; 238419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2385cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (v == SEQ_START_TOKEN) { 2386cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway " 2387cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU" 2388cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "\tWindow\tIRTT"); 2389cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 2390cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 239119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2392cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_TNODE(l)) 2393cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 239419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2395cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i=32; i>=0; i--) { 2396772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct leaf_info *li = find_leaf_info(l, i); 2397cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_alias *fa; 2398cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger u32 mask, prefix; 239991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2400cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!li) 2401cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger continue; 240219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2403cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger mask = inet_make_mask(li->plen); 2404cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger prefix = htonl(l->key); 240519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2406cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger list_for_each_entry_rcu(fa, &li->falh, fa_list) { 24071371e37da299d4df6267ad0ddf010435782c28e9Herbert Xu const struct fib_info *fi = fa->fa_info; 2408cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned flags = fib_flag_trans(fa->fa_type, mask, fi); 240919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2410cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fa->fa_type == RTN_BROADCAST 2411cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger || fa->fa_type == RTN_MULTICAST) 2412cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger continue; 241319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2414cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fi) 2415cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(bf, sizeof(bf), 2416cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u", 2417cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_dev ? fi->fib_dev->name : "*", 2418cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger prefix, 2419cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_nh->nh_gw, flags, 0, 0, 2420cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_priority, 2421cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger mask, 2422cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger (fi->fib_advmss ? fi->fib_advmss + 40 : 0), 2423cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_window, 2424cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_rtt >> 3); 2425cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger else 2426cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(bf, sizeof(bf), 2427cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u", 2428cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger prefix, 0, flags, 0, 0, 0, 2429cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger mask, 0, 0, 0); 243019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2431cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "%-127s\n", bf); 2432cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 243319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 243419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 243519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 243619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 243719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2438cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct seq_operations fib_route_seq_ops = { 2439cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .start = fib_trie_seq_start, 2440cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .next = fib_trie_seq_next, 2441cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .stop = fib_trie_seq_stop, 2442cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .show = fib_route_seq_show, 244319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 244419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2445cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_route_seq_open(struct inode *inode, struct file *file) 244619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 244719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct seq_file *seq; 244819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int rc = -ENOMEM; 2449cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL); 245019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2451cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!s) 2452cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out; 2453cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2454cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rc = seq_open(file, &fib_route_seq_ops); 245519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (rc) 245619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out_kfree; 245719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2458cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq = file->private_data; 2459cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq->private = s; 2460cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(s, 0, sizeof(*s)); 246119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout: 246219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return rc; 246319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout_kfree: 2464cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger kfree(s); 246519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 246619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 246719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2468cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct file_operations fib_route_fops = { 2469cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .owner = THIS_MODULE, 2470cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .open = fib_route_seq_open, 2471cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .read = seq_read, 2472cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .llseek = seq_lseek, 2473cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .release = seq_release_private, 247419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 247519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 247619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonint __init fib_proc_init(void) 247719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2478cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops)) 2479cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out1; 2480cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2481cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops)) 2482cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out2; 2483cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2484cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops)) 2485cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out3; 2486cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 248719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 2488cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2489cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerout3: 2490cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("fib_triestat"); 2491cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerout2: 2492cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("fib_trie"); 2493cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerout1: 2494cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return -ENOMEM; 249519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 249619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 249719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonvoid __init fib_proc_exit(void) 249819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 249919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson proc_net_remove("fib_trie"); 2500cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("fib_triestat"); 2501cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("route"); 250219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 250319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 250419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif /* CONFIG_PROC_FS */ 2505