fib_trie.c revision 550e29bc96e6f1ced2bca82dace197b009434367
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. 44fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * 45fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * Substantial contributions to this work comes from: 46fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * 47fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * David S. Miller, <davem@davemloft.net> 48fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * Stephen Hemminger <shemminger@osdl.org> 49fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * Paul E. McKenney <paulmck@us.ibm.com> 50fd9662555cc35f8bf9242cd7bba8b44ae168a68bRobert Olsson * Patrick McHardy <kaber@trash.net> 5119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 5219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 53550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson#define VERSION "0.407" 5419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 5519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/config.h> 5619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <asm/uaccess.h> 5719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <asm/system.h> 5819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <asm/bitops.h> 5919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/types.h> 6019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/kernel.h> 6119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/sched.h> 6219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/mm.h> 6319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/string.h> 6419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/socket.h> 6519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/sockios.h> 6619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/errno.h> 6719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/in.h> 6819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/inet.h> 69cd8787ab04d23f925f440b712b43a6fd5cb31eceStephen Hemminger#include <linux/inetdevice.h> 7019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/netdevice.h> 7119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/if_arp.h> 7219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/proc_fs.h> 732373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson#include <linux/rcupdate.h> 7419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/skbuff.h> 7519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/netlink.h> 7619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/init.h> 7719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <linux/list.h> 7819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/ip.h> 7919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/protocol.h> 8019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/route.h> 8119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/tcp.h> 8219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/sock.h> 8319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include <net/ip_fib.h> 8419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#include "fib_lookup.h" 8519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#undef CONFIG_IP_FIB_TRIE_STATS 8706ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson#define MAX_STAT_DEPTH 32 8819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define KEYLENGTH (8*sizeof(t_key)) 9019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l)) 9119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset)) 9219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 9319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssontypedef unsigned int t_key; 9419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 9519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define T_TNODE 0 9619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define T_LEAF 1 9719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define NODE_TYPE_MASK 0x1UL 9891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#define NODE_PARENT(node) \ 992373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK))) 1002373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 1012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK) 1022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 1032373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson#define NODE_SET_PARENT(node, ptr) \ 1042373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer((node)->parent, \ 1052373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson ((unsigned long)(ptr)) | NODE_TYPE(node)) 10691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 10791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#define IS_TNODE(n) (!(n->parent & T_LEAF)) 10891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#define IS_LEAF(n) (n->parent & T_LEAF) 10919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct node { 11191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key; 11291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned long parent; 11319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 11419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct leaf { 11691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key; 11791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned long parent; 11819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_head list; 1192373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct rcu_head rcu; 12019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 12119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct leaf_info { 12319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node hlist; 1242373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct rcu_head rcu; 12519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen; 12619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head falh; 12719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 12819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct tnode { 13091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key; 13191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned long parent; 13291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */ 13391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */ 13491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short full_children; /* KEYLENGTH bits needed */ 13591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson unsigned short empty_children; /* KEYLENGTH bits needed */ 1362373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct rcu_head rcu; 13791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *child[0]; 13819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 13919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 14019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 14119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct trie_use_stats { 14219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int gets; 14319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int backtrack; 14419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int semantic_match_passed; 14519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int semantic_match_miss; 14619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int null_node_hit; 1472f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson unsigned int resize_node_skipped; 14819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 14919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 15019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct trie_stat { 15219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int totdepth; 15319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int maxdepth; 15419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int tnodes; 15519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int leaves; 15619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int nullpointers; 15706ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson unsigned int nodesizes[MAX_STAT_DEPTH]; 158c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger}; 15919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct trie { 16191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *trie; 16219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 16319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie_use_stats stats; 16419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 16591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson int size; 16619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson unsigned int revision; 16719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 16819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); 17019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); 17119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct node *resize(struct trie *t, struct tnode *tn); 1722f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *inflate(struct trie *t, struct tnode *tn); 1732f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *halve(struct trie *t, struct tnode *tn); 17419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void tnode_free(struct tnode *tn); 17519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 176ba89966c1984513f4f2cc0a6c182266be44ddd03Eric Dumazetstatic kmem_cache_t *fn_alias_kmem __read_mostly; 17719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct trie *trie_local = NULL, *trie_main = NULL; 17819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1792373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 1802373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* rcu_read_lock needs to be hold by caller from readside */ 1812373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 182c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic inline struct node *tnode_get_child(struct tnode *tn, int i) 18319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 18491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(i >= 1 << tn->bits); 18519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1862373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return rcu_dereference(tn->child[i]); 18719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 18819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 189bb435b8d816582064ee0ddb1e2a6fbca67f34108Stephen Hemmingerstatic inline int tnode_child_length(const struct tnode *tn) 19019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 19191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return 1 << tn->bits; 19219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 19319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 19419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline t_key tkey_extract_bits(t_key a, int offset, int bits) 19519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 19691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (offset < KEYLENGTH) 19719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return ((t_key)(a << offset)) >> (KEYLENGTH - bits); 19891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson else 19919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 20019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 20119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 20219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline int tkey_equals(t_key a, t_key b) 20319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 204c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger return a == b; 20519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 20619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 20719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b) 20819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 209c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (bits == 0 || offset >= KEYLENGTH) 210c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger return 1; 21191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson bits = bits > KEYLENGTH ? KEYLENGTH : bits; 21291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0; 213c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger} 21419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 21519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline int tkey_mismatch(t_key a, int offset, t_key b) 21619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 21719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key diff = a ^ b; 21819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i = offset; 21919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 220c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!diff) 221c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger return 0; 222c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger while ((diff << i) >> (KEYLENGTH-1) == 0) 22319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i++; 22419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return i; 22519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 22619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 22719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* 22819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson To understand this stuff, an understanding of keys and all their bits is 22919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson necessary. Every node in the trie has a key associated with it, but not 23019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson all of the bits in that key are significant. 23119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 23219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson Consider a node 'n' and its parent 'tp'. 23319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 23419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson If n is a leaf, every bit in its key is significant. Its presence is 235772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson necessitated by path compression, since during a tree traversal (when 23619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson searching for a leaf - unless we are doing an insertion) we will completely 23719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ignore all skipped bits we encounter. Thus we need to verify, at the end of 23819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson a potentially successful search, that we have indeed been walking the 23919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson correct key path. 24019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 24119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson Note that we can never "miss" the correct key in the tree if present by 24219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson following the wrong path. Path compression ensures that segments of the key 24319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson that are the same for all keys with a given prefix are skipped, but the 24419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson skipped part *is* identical for each node in the subtrie below the skipped 24519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson bit! trie_insert() in this implementation takes care of that - note the 24619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson call to tkey_sub_equals() in trie_insert(). 24719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 24819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if n is an internal node - a 'tnode' here, the various parts of its key 24919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson have many different meanings. 25019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 25119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson Example: 25219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson _________________________________________________________________ 25319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C | 25419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ----------------------------------------------------------------- 25519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 25619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 25719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson _________________________________________________________________ 25819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u | 25919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ----------------------------------------------------------------- 26019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 26119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 26219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp->pos = 7 26319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp->bits = 3 26419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n->pos = 15 26591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson n->bits = 4 26619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 26719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson First, let's just ignore the bits that come before the parent tp, that is 26819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson the bits from 0 to (tp->pos-1). They are *known* but at this point we do 26919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson not use them for anything. 27019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 27119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the 27219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson index into the parent's child array. That is, they will be used to find 27319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 'n' among tp's children. 27419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 27519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits 27619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson for the node n. 27719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 27819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson All the bits we have seen so far are significant to the node n. The rest 27919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson of the bits are really not needed or indeed known in n->key. 28019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 28119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into 28219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n's child array, and will of course be different for each child. 28319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 284c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 28519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson The rest of the bits, from (n->pos + n->bits) onward, are completely unknown 28619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson at this point. 28719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 28819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson*/ 28919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2900c7770c740156c8802c23d24fc094d06967d997dStephen Hemmingerstatic inline void check_tnode(const struct tnode *tn) 29119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2920c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger WARN_ON(tn && tn->pos+tn->bits > 32); 29319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 29419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 29519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int halve_threshold = 25; 29619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int inflate_threshold = 50; 297e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olssonstatic int halve_threshold_root = 15; 298e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olssonstatic int inflate_threshold_root = 25; 29919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 3002373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __alias_free_mem(struct rcu_head *head) 30219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3032373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct fib_alias *fa = container_of(head, struct fib_alias, rcu); 3042373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson kmem_cache_free(fn_alias_kmem, fa); 30519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 30619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 3072373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void alias_free_mem_rcu(struct fib_alias *fa) 30819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson call_rcu(&fa->rcu, __alias_free_mem); 3102373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 31191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 3122373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __leaf_free_rcu(struct rcu_head *head) 3132373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3142373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson kfree(container_of(head, struct leaf, rcu)); 3152373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 31691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 3172373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __leaf_info_free_rcu(struct rcu_head *head) 31819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3192373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson kfree(container_of(head, struct leaf_info, rcu)); 32019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 32119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 3222373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void free_leaf_info(struct leaf_info *leaf) 32319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 3242373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson call_rcu(&leaf->rcu, __leaf_info_free_rcu); 32519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 32619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 327f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardystatic struct tnode *tnode_alloc(unsigned int size) 328f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy{ 3292373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct page *pages; 3302373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3312373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (size <= PAGE_SIZE) 3322373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return kcalloc(size, 1, GFP_KERNEL); 3332373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3342373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size)); 3352373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!pages) 3362373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return NULL; 3372373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3382373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return page_address(pages); 339f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy} 340f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy 3412373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic void __tnode_free_rcu(struct rcu_head *head) 342f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy{ 3432373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct tnode *tn = container_of(head, struct tnode, rcu); 344f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy unsigned int size = sizeof(struct tnode) + 3452373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson (1 << tn->bits) * sizeof(struct node *); 346f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy 347f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy if (size <= PAGE_SIZE) 348f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy kfree(tn); 349f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy else 350f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy free_pages((unsigned long)tn, get_order(size)); 351f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy} 352f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy 3532373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic inline void tnode_free(struct tnode *tn) 3542373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 355550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson if(IS_LEAF(tn)) { 356550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson struct leaf *l = (struct leaf *) tn; 357550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson call_rcu_bh(&l->rcu, __leaf_free_rcu); 358550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson } 359550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson else 360550e29bc96e6f1ced2bca82dace197b009434367Robert Olsson call_rcu(&tn->rcu, __tnode_free_rcu); 3612373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 3622373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3632373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic struct leaf *leaf_new(void) 3642373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3652373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL); 3662373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (l) { 3672373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson l->parent = T_LEAF; 3682373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson INIT_HLIST_HEAD(&l->list); 3692373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 3702373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return l; 3712373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 3722373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 3732373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olssonstatic struct leaf_info *leaf_info_new(int plen) 3742373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson{ 3752373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL); 3762373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (li) { 3772373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson li->plen = plen; 3782373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson INIT_LIST_HEAD(&li->falh); 3792373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 3802373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return li; 3812373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson} 3822373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 38319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct tnode* tnode_new(t_key key, int pos, int bits) 38419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 38519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int nchildren = 1<<bits; 38619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *); 387f0e36f8cee8101604378085171c980d9cc71d779Patrick McHardy struct tnode *tn = tnode_alloc(sz); 38819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 38991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (tn) { 39019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(tn, 0, sz); 3912373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson tn->parent = T_TNODE; 39219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->pos = pos; 39319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->bits = bits; 39419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->key = key; 39519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->full_children = 0; 39619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->empty_children = 1<<bits; 39719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 398c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 3990c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode), 4000c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger (unsigned int) (sizeof(struct node) * 1<<bits)); 40119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tn; 40219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 40319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 40419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* 40519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Check whether a tnode 'n' is "full", i.e. it is an internal node 40619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * and no bits are skipped. See discussion in dyntree paper p. 6 40719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 40819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 409bb435b8d816582064ee0ddb1e2a6fbca67f34108Stephen Hemmingerstatic inline int tnode_full(const struct tnode *tn, const struct node *n) 41019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 411c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n == NULL || IS_LEAF(n)) 41219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 41319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 41419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return ((struct tnode *) n)->pos == tn->pos + tn->bits; 41519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 41619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 417c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n) 41819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 41919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_put_child_reorg(tn, i, n, -1); 42019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 42119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 422c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 42319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Add a child at position i overwriting the old value. 42419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Update the value of full_children and empty_children. 42519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 42619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 427c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull) 42819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 4292373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct node *chi = tn->child[i]; 43019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int isfull; 43119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4320c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger BUG_ON(i >= 1<<tn->bits); 4330c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 43419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 43519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* update emptyChildren */ 43619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (n == NULL && chi != NULL) 43719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->empty_children++; 43819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson else if (n != NULL && chi == NULL) 43919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->empty_children--; 440c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 44119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* update fullChildren */ 44291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (wasfull == -1) 44319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson wasfull = tnode_full(tn, chi); 44419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 44519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson isfull = tnode_full(tn, n); 446c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (wasfull && !isfull) 44719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->full_children--; 448c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger else if (!wasfull && isfull) 44919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->full_children++; 45091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 451c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n) 452c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger NODE_SET_PARENT(n, tn); 45319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4542373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(tn->child[i], n); 45519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 45619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 457c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic struct node *resize(struct trie *t, struct tnode *tn) 45819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 45919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i; 4602f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson int err = 0; 4612f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson struct tnode *old_tn; 462e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson int inflate_threshold_use; 463e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson int halve_threshold_use; 46419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 46519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!tn) 46619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 46719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 4680c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n", 4690c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger tn, inflate_threshold, halve_threshold); 47019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 47119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* No children */ 47219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tn->empty_children == tnode_child_length(tn)) { 47319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(tn); 47419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 47519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 47619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* One child */ 47719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tn->empty_children == tnode_child_length(tn) - 1) 47819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson for (i = 0; i < tnode_child_length(tn); i++) { 47991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *n; 48019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 48191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson n = tn->child[i]; 4822373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!n) 48391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 48491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 48591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* compress one level */ 4862373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson NODE_SET_PARENT(n, NULL); 48791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson tnode_free(tn); 48891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return n; 48919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 490c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 49119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Double as long as the resulting node has a number of 49219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * nonempty nodes that are above the threshold. 49319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 49419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 49519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 496c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * From "Implementing a dynamic compressed trie" by Stefan Nilsson of 497c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * the Helsinki University of Technology and Matti Tikkanen of Nokia 49819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Telecommunications, page 6: 499c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * "A node is doubled if the ratio of non-empty children to all 50019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * children in the *doubled* node is at least 'high'." 50119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 502c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 'high' in this instance is the variable 'inflate_threshold'. It 503c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * is expressed as a percentage, so we multiply it with 504c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * tnode_child_length() and instead of multiplying by 2 (since the 505c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * child array will be doubled by inflate()) and multiplying 506c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * the left-hand side by 100 (to handle the percentage thing) we 50719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * multiply the left-hand side by 50. 508c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 509c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * The left-hand side may look a bit weird: tnode_child_length(tn) 510c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * - tn->empty_children is of course the number of non-null children 511c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * in the current node. tn->full_children is the number of "full" 51219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * children, that is non-null tnodes with a skip value of 0. 513c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * All of those will be doubled in the resulting inflated tnode, so 51419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * we just count them one extra time here. 515c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 51619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * A clearer way to write this would be: 517c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 51819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * to_be_doubled = tn->full_children; 519c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - 52019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * tn->full_children; 52119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 52219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * new_child_length = tnode_child_length(tn) * 2; 52319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 524c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / 52519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * new_child_length; 52619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * if (new_fill_factor >= inflate_threshold) 527c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 528c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * ...and so on, tho it would mess up the while () loop. 529c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 53019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * anyway, 53119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >= 53219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * inflate_threshold 533c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 53419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * avoid a division: 53519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 100 * (not_to_be_doubled + 2*to_be_doubled) >= 53619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * inflate_threshold * new_child_length 537c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 53819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * expand not_to_be_doubled and to_be_doubled, and shorten: 539c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 100 * (tnode_child_length(tn) - tn->empty_children + 54091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tn->full_children) >= inflate_threshold * new_child_length 541c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 54219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * expand new_child_length: 543c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 100 * (tnode_child_length(tn) - tn->empty_children + 54491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tn->full_children) >= 54519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * inflate_threshold * tnode_child_length(tn) * 2 546c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 54719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * shorten again: 548c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 50 * (tn->full_children + tnode_child_length(tn) - 54991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tn->empty_children) >= inflate_threshold * 55019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * tnode_child_length(tn) 551c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * 55219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 55319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 55419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 555c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 556e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson /* Keep root node larger */ 557e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 558e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson if(!tn->parent) 559e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson inflate_threshold_use = inflate_threshold_root; 560e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson else 561e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson inflate_threshold_use = inflate_threshold; 562e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 5632f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson err = 0; 56419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while ((tn->full_children > 0 && 56519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= 566e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson inflate_threshold_use * tnode_child_length(tn))) { 56719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 5682f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson old_tn = tn; 5692f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = inflate(t, tn); 5702f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (IS_ERR(tn)) { 5712f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = old_tn; 5722f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 5732f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson t->stats.resize_node_skipped++; 5742f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#endif 5752f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson break; 5762f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 57719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 57819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 57919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 58019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 58119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 58219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Halve as long as the number of empty children in this 58319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * node is above threshold. 58419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 5852f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 586e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 587e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson /* Keep root node larger */ 588e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 589e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson if(!tn->parent) 590e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson halve_threshold_use = halve_threshold_root; 591e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson else 592e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson halve_threshold_use = halve_threshold; 593e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson 5942f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson err = 0; 59519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (tn->bits > 1 && 59619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 100 * (tnode_child_length(tn) - tn->empty_children) < 597e6308be85afee685347fa3440bed10faaa5d6c1aRobert Olsson halve_threshold_use * tnode_child_length(tn)) { 5982f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 5992f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson old_tn = tn; 6002f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = halve(t, tn); 6012f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (IS_ERR(tn)) { 6022f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tn = old_tn; 6032f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 6042f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson t->stats.resize_node_skipped++; 6052f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson#endif 6062f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson break; 6072f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 6082f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 60919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 610c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 61119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Only one child remains */ 61219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tn->empty_children == tnode_child_length(tn) - 1) 61319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson for (i = 0; i < tnode_child_length(tn); i++) { 61491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct node *n; 61519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 61691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson n = tn->child[i]; 6172373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!n) 61891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 61991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 62091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* compress one level */ 62191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 6222373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson NODE_SET_PARENT(n, NULL); 62391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson tnode_free(tn); 62491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return n; 62519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 62619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 62719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return (struct node *) tn; 62819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 62919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 6302f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *inflate(struct trie *t, struct tnode *tn) 63119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 63219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *inode; 63319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *oldtnode = tn; 63419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int olen = tnode_child_length(tn); 63519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i; 63619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 6370c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("In inflate\n"); 63819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 63919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); 64019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 6410c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger if (!tn) 6422f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 6432f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6442f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson /* 645c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Preallocate and store tnodes before the actual work so we 646c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * don't get into an inconsistent state if memory allocation 647c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * fails. In case of failure we return the oldnode and inflate 6482f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson * of tnode is ignored. 6492f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson */ 65091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 65191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i++) { 6522f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i); 6532f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6542f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson if (inode && 6552f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson IS_TNODE(inode) && 6562f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->pos == oldtnode->pos + oldtnode->bits && 6572f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->bits > 1) { 6582f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson struct tnode *left, *right; 6592f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson t_key m = TKEY_GET_MASK(inode->pos, 1); 660c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 6612f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson left = tnode_new(inode->key&(~m), inode->pos + 1, 6622f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->bits - 1); 6632f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (!left) 6642f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson goto nomem; 66591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 6662f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson right = tnode_new(inode->key|m, inode->pos + 1, 6672f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson inode->bits - 1); 6682f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6692f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (!right) { 6702f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free(left); 6712f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson goto nomem; 6722f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson } 6732f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 6742f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson put_child(t, tn, 2*i, (struct node *) left); 6752f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson put_child(t, tn, 2*i+1, (struct node *) right); 6762f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 6772f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 6782f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 67991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i++) { 68019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *node = tnode_get_child(oldtnode, i); 68191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct tnode *left, *right; 68291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson int size, j; 683c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 68419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* An empty child */ 68519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (node == NULL) 68619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 68719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 68819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* A leaf or an internal node with skipped bits */ 68919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 690c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (IS_LEAF(node) || ((struct tnode *) node)->pos > 69119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn->pos + tn->bits - 1) { 692c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits, 69319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1) == 0) 69419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i, node); 69519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson else 69619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i+1, node); 69719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 69819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 69919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 70019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* An internal node with two children */ 70119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson inode = (struct tnode *) node; 70219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 70319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (inode->bits == 1) { 70419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i, inode->child[0]); 70519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 2*i+1, inode->child[1]); 70619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 70719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(inode); 70891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 70919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 71019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 71191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* An internal node with more than two children */ 71291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 71391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* We will replace this node 'inode' with two new 71491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * ones, 'left' and 'right', each with half of the 71591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * original children. The two new nodes will have 71691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * a position one bit further down the key and this 71791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * means that the "significant" part of their keys 71891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * (see the discussion near the top of this file) 71991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * will differ by one bit, which will be "0" in 72091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * left's key and "1" in right's key. Since we are 72191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * moving the key position by one step, the bit that 72291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * we are moving away from - the bit at position 72391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * (inode->pos) - is the one that will differ between 72491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * left and right. So... we synthesize that bit in the 72591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * two new keys. 72691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * The mask 'm' below will be a single "one" bit at 72791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * the position (inode->pos) 72891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 72919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 73091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Use the old key, but set the new significant 73191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * bit to zero. 73291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 7332f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 73491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson left = (struct tnode *) tnode_get_child(tn, 2*i); 73591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i, NULL); 7362f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 73791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(!left); 7382f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 73991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson right = (struct tnode *) tnode_get_child(tn, 2*i+1); 74091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i+1, NULL); 74119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 74291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(!right); 74319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 74491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson size = tnode_child_length(left); 74591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (j = 0; j < size; j++) { 74691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, left, j, inode->child[j]); 74791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, right, j, inode->child[j + size]); 74819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 74991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i, resize(t, left)); 75091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, 2*i+1, resize(t, right)); 75191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 75291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson tnode_free(inode); 75319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 75419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(oldtnode); 75519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tn; 7562f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonnomem: 7572f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson { 7582f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int size = tnode_child_length(tn); 7592f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int j; 7602f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 7610c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger for (j = 0; j < size; j++) 7622f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (tn->child[j]) 7632f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free((struct tnode *)tn->child[j]); 7642f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 7652f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free(tn); 7660c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 7672f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 7682f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson } 76919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 77019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7712f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonstatic struct tnode *halve(struct trie *t, struct tnode *tn) 77219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 77319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *oldtnode = tn; 77419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *left, *right; 77519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i; 77619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int olen = tnode_child_length(tn); 77719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7780c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("In halve\n"); 779c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 780c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); 78119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 7822f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (!tn) 7832f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 7842f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 7852f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson /* 786c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Preallocate and store tnodes before the actual work so we 787c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * don't get into an inconsistent state if memory allocation 788c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * fails. In case of failure we return the oldnode and halve 7892f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson * of tnode is ignored. 7902f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson */ 7912f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 79291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i += 2) { 7932f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson left = tnode_get_child(oldtnode, i); 7942f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson right = tnode_get_child(oldtnode, i+1); 795c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 7962f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson /* Two nonempty children */ 7970c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger if (left && right) { 7982f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson struct tnode *newn; 7990c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 8002f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson newn = tnode_new(left->key, tn->pos + tn->bits, 1); 8010c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 8020c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger if (!newn) 8032f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson goto nomem; 8040c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 8052f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson put_child(t, tn, i/2, (struct node *)newn); 8062f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 8072f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson 8082f36895aa774cf4d1c3d68921e0209e796b66600Robert Olsson } 80919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 81091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (i = 0; i < olen; i += 2) { 81191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct tnode *newBinNode; 81291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 81319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson left = tnode_get_child(oldtnode, i); 81419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson right = tnode_get_child(oldtnode, i+1); 815c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 81619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* At least one of the children is empty */ 81719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (left == NULL) { 81819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (right == NULL) /* Both are empty */ 81919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 82019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, i/2, right); 82191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 8220c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger } 82391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 82491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (right == NULL) { 82519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, i/2, left); 82691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 82791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 828c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 82919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Two nonempty children */ 83091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson newBinNode = (struct tnode *) tnode_get_child(tn, i/2); 83191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, i/2, NULL); 83291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, newBinNode, 0, left); 83391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, newBinNode, 1, right); 83491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, tn, i/2, resize(t, newBinNode)); 83519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 83619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free(oldtnode); 83719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tn; 8382f80b3c8262d0d646812f776db024d88d569a0c1Robert Olssonnomem: 8392f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson { 8402f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int size = tnode_child_length(tn); 8412f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson int j; 8422f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 8430c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger for (j = 0; j < size; j++) 8442f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson if (tn->child[j]) 8452f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free((struct tnode *)tn->child[j]); 8462f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson 8472f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson tnode_free(tn); 8480c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger 8492f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson return ERR_PTR(-ENOMEM); 8502f80b3c8262d0d646812f776db024d88d569a0c1Robert Olsson } 85119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 85219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 85391b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonstatic void trie_init(struct trie *t) 85419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 85591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!t) 85691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return; 85791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 85891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t->size = 0; 8592373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, NULL); 86091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t->revision = 0; 86119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 86291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson memset(&t->stats, 0, sizeof(struct trie_use_stats)); 86319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 86419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 86519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 866772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson/* readside must use rcu_read_lock currently dump routines 8672373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson via get_fa_head and dump */ 8682373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 869772cb712b1373d335ef2874ea357ec681edc754bRobert Olssonstatic struct leaf_info *find_leaf_info(struct leaf *l, int plen) 87019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 871772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct hlist_head *head = &l->list; 87219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node *node; 87319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li; 87419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 8752373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_for_each_entry_rcu(li, node, head, hlist) 876c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (li->plen == plen) 87719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return li; 87891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 87919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 88019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 88119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 88219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic inline struct list_head * get_fa_head(struct leaf *l, int plen) 88319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 884772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct leaf_info *li = find_leaf_info(l, plen); 885c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 88691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!li) 88791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return NULL; 888c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 88991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return &li->falh; 89019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 89119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 89219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void insert_leaf_info(struct hlist_head *head, struct leaf_info *new) 89319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 8942373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct leaf_info *li = NULL, *last = NULL; 8952373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct hlist_node *node; 8962373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 8972373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (hlist_empty(head)) { 8982373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_add_head_rcu(&new->hlist, head); 8992373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } else { 9002373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_for_each_entry(li, node, head, hlist) { 9012373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (new->plen > li->plen) 9022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson break; 9032373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 9042373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson last = li; 9052373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 9062373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (last) 9072373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_add_after_rcu(&last->hlist, &new->hlist); 9082373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson else 9092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_add_before_rcu(&new->hlist, &li->hlist); 9102373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 91119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 91219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 9132373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* rcu_read_lock needs to be hold by caller from readside */ 9142373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 91519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct leaf * 91619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfib_find_node(struct trie *t, u32 key) 91719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 91819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos; 91919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tn; 92019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n; 92119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 92219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = 0; 9232373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson n = rcu_dereference(t->trie); 92419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 92519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (n != NULL && NODE_TYPE(n) == T_TNODE) { 92619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode *) n; 92791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 92819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 92991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 930c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 93191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = tn->pos + tn->bits; 93219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 93391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 93419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 93519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 93619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Case we have found a leaf. Compare prefixes */ 93719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 93891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) 93991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return (struct leaf *)n; 94091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 94119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 94219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 94319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 94419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct node *trie_rebalance(struct trie *t, struct tnode *tn) 94519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 94619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int wasfull; 94719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex, key; 94819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tp = NULL; 94919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 95019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = tn->key; 95119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 95219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (tn != NULL && NODE_PARENT(tn) != NULL) { 95319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 95419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = NODE_PARENT(tn); 95519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 95619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); 95719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode *) resize (t, (struct tnode *)tn); 95819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull); 95991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 960c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!NODE_PARENT(tn)) 96119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 96219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 96319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = NODE_PARENT(tn); 96419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 96519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Handle last (top) tnode */ 966c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (IS_TNODE(tn)) 96719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode*) resize(t, (struct tnode *)tn); 96819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 96919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return (struct node*) tn; 97019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 97119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 9722373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* only used from updater-side */ 9732373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 974f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssonstatic struct list_head * 975f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssonfib_insert_node(struct trie *t, int *err, u32 key, int plen) 97619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 97719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos, newpos; 97819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tp = NULL, *tn = NULL; 97919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n; 98019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 98119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int missbit; 982c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger struct list_head *fa_head = NULL; 98319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li; 98419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex; 98519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 98619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = 0; 987c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger n = t->trie; 98819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 989c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* If we point to NULL, stop. Either the tree is empty and we should 990c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * just put a new leaf in if, or we have reached an empty child slot, 99119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * and we should just put our new leaf in that. 992c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * If we point to a T_TNODE, check if it matches our key. Note that 993c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * a T_TNODE might be skipping any number of bits - its 'pos' need 99419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * not be the parent's 'pos'+'bits'! 99519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 996c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * If it does match the current key, get pos/bits from it, extract 99719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * the index from our key, push the T_TNODE and walk the tree. 99819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 99919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If it doesn't, we have to replace it with a new T_TNODE. 100019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1001c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * If we point to a T_LEAF, it might or might not have the same key 1002c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * as we do. If it does, just change the value, update the T_LEAF's 1003c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * value, and return it. 100419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If it doesn't, we need to replace it with a T_TNODE. 100519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 100619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 100719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (n != NULL && NODE_TYPE(n) == T_TNODE) { 100819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = (struct tnode *) n; 100991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1010c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger check_tnode(tn); 101191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1012c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 101319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = tn; 101491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = tn->pos + tn->bits; 101519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 101619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 10170c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger BUG_ON(n && NODE_PARENT(n) != tn); 101891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 101919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 102019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 102119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 102219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 102319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * n ----> NULL, LEAF or TNODE 102419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 1025c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * tp is n's (parent) ----> NULL or TNODE 102619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 102719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 102891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson BUG_ON(tp && IS_LEAF(tp)); 102919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 103019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Case 1: n is a leaf. Compare prefixes */ 103119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1032c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) { 103391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct leaf *l = (struct leaf *) n; 103491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 103519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson li = leaf_info_new(plen); 103691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1037c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!li) { 1038f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1039f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 1040f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 104119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 104219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = &li->falh; 104319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson insert_leaf_info(&l->list, li); 104419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto done; 104519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 104619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->size++; 104719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = leaf_new(); 104819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1049c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!l) { 1050f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1051f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 1052f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 105319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 105419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l->key = key; 105519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson li = leaf_info_new(plen); 105619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1057c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!li) { 1058f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson tnode_free((struct tnode *) l); 1059f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1060f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 1061f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 106219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 106319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = &li->falh; 106419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson insert_leaf_info(&l->list, li); 106519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 106619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (t->trie && n == NULL) { 106791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Case 2: n is NULL, and will just insert a new leaf */ 106819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 106919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson NODE_SET_PARENT(l, tp); 107019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 107191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 107291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson put_child(t, (struct tnode *)tp, cindex, (struct node *)l); 107391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 107491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */ 1075c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 1076c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Add a new tnode here 107719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * first tnode need some special handling 107819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 107919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 108019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tp) 108191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = tp->pos+tp->bits; 108219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson else 108391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pos = 0; 108491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1085c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (n) { 108619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson newpos = tkey_mismatch(key, pos, n->key); 108719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tn = tnode_new(n->key, newpos, 1); 108891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 108919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson newpos = 0; 1090c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger tn = tnode_new(key, newpos, 1); /* First tnode */ 109119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 109219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1093c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!tn) { 1094f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson free_leaf_info(li); 1095f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson tnode_free((struct tnode *) l); 1096f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson *err = -ENOMEM; 1097f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto err; 109891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 109991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 110019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson NODE_SET_PARENT(tn, tp); 110119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 110291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson missbit = tkey_extract_bits(key, newpos, 1); 110319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, missbit, (struct node *)l); 110419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, tn, 1-missbit, n); 110519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1106c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tp) { 110719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 110819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, (struct tnode *)tp, cindex, (struct node *)tn); 110991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 11102373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */ 111119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = tn; 111219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 111319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 111491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 111591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (tp && tp->pos + tp->bits > 32) 111678c6671a88313fd3c4364dc46e8c8186612616b8Stephen Hemminger printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n", 111719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp, tp->pos, tp->bits, key, plen); 111891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 111919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Rebalance the trie */ 11202373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 11212373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); 1122f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssondone: 1123f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson t->revision++; 112491b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonerr: 112519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return fa_head; 112619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 112719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 112819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int 112919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 113019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct nlmsghdr *nlhdr, struct netlink_skb_parms *req) 113119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 113219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 113319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa, *new_fa; 1134c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger struct list_head *fa_head = NULL; 113519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi; 113619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen = r->rtm_dst_len; 113719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int type = r->rtm_type; 113819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u8 tos = r->rtm_tos; 113919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u32 key, mask; 114019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int err; 114119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 114219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 114319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (plen > 32) 114419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 114519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 114619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = 0; 1147c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (rta->rta_dst) 114819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memcpy(&key, rta->rta_dst, 4); 114919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 115019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = ntohl(key); 115119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11520c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); 115319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 115491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mask = ntohl(inet_make_mask(plen)); 115519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1156c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (key & ~mask) 115719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 115819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 115919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = key & mask; 116019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 116191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson fi = fib_create_info(r, rta, nlhdr, &err); 116291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 116391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!fi) 116419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto err; 116519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 116619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = fib_find_node(t, key); 1167c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger fa = NULL; 116819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1169c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (l) { 117019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, plen); 117119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa = fib_find_alias(fa_head, tos, fi->fib_priority); 117219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 117319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 117419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Now fa, if non-NULL, points to the first fib alias 117519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * with the same keys [prefix,tos,priority], if such key already 117619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * exists or to the node before which we will insert new one. 117719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 117819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If fa is NULL, we will need to allocate a new one and 117919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * insert to the head of f. 118019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * 118119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * If f is NULL, no fib node matched the destination key 118219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * and we need to allocate a new one of those as well. 118319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 118419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 118591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (fa && fa->fa_info->fib_priority == fi->fib_priority) { 118619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa_orig; 118719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 118819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson err = -EEXIST; 118919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (nlhdr->nlmsg_flags & NLM_F_EXCL) 119019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 119119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 119219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (nlhdr->nlmsg_flags & NLM_F_REPLACE) { 119319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi_drop; 119419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u8 state; 119519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 11962373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson err = -ENOBUFS; 11972373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL); 11982373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (new_fa == NULL) 11992373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson goto out; 120019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 120119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fi_drop = fa->fa_info; 12022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_tos = fa->fa_tos; 12032373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_info = fi; 12042373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_type = type; 12052373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_scope = r->rtm_scope; 120619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson state = fa->fa_state; 12072373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson new_fa->fa_state &= ~FA_S_ACCESSED; 120819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_replace_rcu(&fa->fa_list, &new_fa->fa_list); 12102373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson alias_free_mem_rcu(fa); 121119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 121219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_release_info(fi_drop); 121319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (state & FA_S_ACCESSED) 121491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson rt_cache_flush(-1); 121519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 121691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto succeeded; 121719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 121819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Error if we find a perfect match which 121919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * uses the same scope, type, and nexthop 122019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * information. 122119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 122219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_orig = fa; 122319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) { 122419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_tos != tos) 122519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 122619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_info->fib_priority != fi->fib_priority) 122719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 122819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_type == type && 122919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_scope == r->rtm_scope && 123019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_info == fi) { 123119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 123219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 123319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 123419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!(nlhdr->nlmsg_flags & NLM_F_APPEND)) 123519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa = fa_orig; 123619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 123719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson err = -ENOENT; 123891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!(nlhdr->nlmsg_flags & NLM_F_CREATE)) 123919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 124019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 124119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson err = -ENOBUFS; 124219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL); 124319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (new_fa == NULL) 124419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 124519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 124619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_info = fi; 124719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_tos = tos; 124819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_type = type; 124919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_scope = r->rtm_scope; 125019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson new_fa->fa_state = 0; 125119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 125219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * Insert new entry to the list. 125319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 125419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1255c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!fa_head) { 1256f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson fa_head = fib_insert_node(t, &err, key, plen); 1257f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson err = 0; 1258c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (err) 1259f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson goto out_free_new_fa; 1260f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson } 126119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12622373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_add_tail_rcu(&new_fa->fa_list, 12632373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson (fa ? &fa->fa_list : fa_head)); 126419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 126519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson rt_cache_flush(-1); 126619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req); 126719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonsucceeded: 126819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 1269f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson 1270f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olssonout_free_new_fa: 1271f835e471b557c45d2e5701ea5215f6e739b4eb39Robert Olsson kmem_cache_free(fn_alias_kmem, new_fa); 127219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout: 127319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_release_info(fi); 127491b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonerr: 127519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return err; 127619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 127719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 12782373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 1279772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson/* should be called with rcu_read_lock */ 12800c7770c740156c8802c23d24fc094d06967d997dStephen Hemmingerstatic inline int check_leaf(struct trie *t, struct leaf *l, 12810c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger t_key key, int *plen, const struct flowi *flp, 128206c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy struct fib_result *res) 128319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 128406c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy int err, i; 128519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key mask; 128619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li; 128719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_head *hhead = &l->list; 128819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node *node; 1289c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 12902373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_for_each_entry_rcu(li, node, hhead, hlist) { 129119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i = li->plen; 129219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson mask = ntohl(inet_make_mask(i)); 1293c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (l->key != (key & mask)) 129419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 129519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 129606c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy if ((err = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) <= 0) { 129719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson *plen = i; 129819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 129919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.semantic_match_passed++; 130019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 130106c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy return err; 130219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 130319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 130419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.semantic_match_miss++; 130519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 130619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 130706c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy return 1; 130819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 130919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 131019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int 131119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) 131219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 131319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 131419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen, ret = 0; 131519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n; 131619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *pn; 131719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos, bits; 131891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key key = ntohl(flp->fl4_dst); 131919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int chopped_off; 132019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex = 0; 132119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int current_prefix_length = KEYLENGTH; 132291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct tnode *cn; 132391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson t_key node_prefix, key_prefix, pref_mismatch; 132491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson int mp; 132591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 13262373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_lock(); 132791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 13282373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson n = rcu_dereference(t->trie); 1329c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!n) 133019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto failed; 133119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 133219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 133319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.gets++; 133419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 133519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 133619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Just a leaf? */ 133719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (IS_LEAF(n)) { 133806c7427021f1cc83703f14659d8405ca773ba1efPatrick McHardy if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) 133919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto found; 134019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto failed; 134119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 134219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pn = (struct tnode *) n; 134319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off = 0; 1344c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 134591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while (pn) { 134619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = pn->pos; 134719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson bits = pn->bits; 134819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1349c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!chopped_off) 135019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits); 135119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 135219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(pn, cindex); 135319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 135419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (n == NULL) { 135519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 135619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.null_node_hit++; 135719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 135819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto backtrace; 135919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 136019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 136191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (IS_LEAF(n)) { 136291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) 136391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto found; 136491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson else 136591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto backtrace; 136691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 136791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 136819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#define HL_OPTIMIZE 136919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef HL_OPTIMIZE 137091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cn = (struct tnode *)n; 137119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 137291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* 137391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * It's a tnode, and we can do some extra checks here if we 137491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * like, to avoid descending into a dead-end branch. 137591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * This tnode is in the parent's child array at index 137691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * key[p_pos..p_pos+p_bits] but potentially with some bits 137791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * chopped off, so in reality the index may be just a 137891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * subprefix, padded with zero at the end. 137991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * We can also take a look at any skipped bits in this 138091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tnode - everything up to p_pos is supposed to be ok, 138191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * and the non-chopped bits of the index (se previous 138291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * paragraph) are also guaranteed ok, but the rest is 138391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * considered unknown. 138491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * 138591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * The skipped bits are key[pos+bits..cn->pos]. 138691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 138719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 138891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* If current_prefix_length < pos+bits, we are already doing 138991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * actual prefix matching, which means everything from 139091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * pos+(bits-chopped_off) onward must be zero along some 139191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * branch of this subtree - otherwise there is *no* valid 139291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * prefix present. Here we can only check the skipped 139391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * bits. Remember, since we have already indexed into the 139491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * parent's child array, we know that the bits we chopped of 139591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * *are* zero. 139691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 139719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 139891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */ 139919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 140091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (current_prefix_length < pos+bits) { 140191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (tkey_extract_bits(cn->key, current_prefix_length, 140291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cn->pos - current_prefix_length) != 0 || 140391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson !(cn->child[0])) 140491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto backtrace; 140591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 140619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 140791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* 140891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * If chopped_off=0, the index is fully validated and we 140991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * only need to look at the skipped bits for this, the new, 141091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * tnode. What we actually want to do is to find out if 141191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * these skipped bits match our key perfectly, or if we will 141291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * have to count on finding a matching prefix further down, 141391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * because if we do, we would like to have some way of 141491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * verifying the existence of such a prefix at this point. 141591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 141619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 141791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* The only thing we can do at this point is to verify that 141891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * any such matching prefix can indeed be a prefix to our 141991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * key, and if the bits in the node we are inspecting that 142091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * do not match our key are not ZERO, this cannot be true. 142191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * Thus, find out where there is a mismatch (before cn->pos) 142291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * and verify that all the mismatching bits are zero in the 142391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * new tnode's key. 142491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 142519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 142691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Note: We aren't very concerned about the piece of the key 142791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * that precede pn->pos+pn->bits, since these have already been 142891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * checked. The bits after cn->pos aren't checked since these are 142991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * by definition "unknown" at this point. Thus, what we want to 143091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * see is if we are about to enter the "prefix matching" state, 143191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * and in that case verify that the skipped bits that will prevail 143291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * throughout this subtree are zero, as they have to be if we are 143391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * to find a matching prefix. 143491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 143591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 143691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson node_prefix = MASK_PFX(cn->key, cn->pos); 143791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson key_prefix = MASK_PFX(key, cn->pos); 143891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pref_mismatch = key_prefix^node_prefix; 143991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mp = 0; 144091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 144191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* In short: If skipped bits in this node do not match the search 144291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson * key, enter the "prefix matching" state.directly. 144391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson */ 144491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (pref_mismatch) { 144591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) { 144691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mp++; 144791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pref_mismatch = pref_mismatch <<1; 144891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 144991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp); 145091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 145191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (key_prefix != 0) 145291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto backtrace; 145391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 145491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (current_prefix_length >= cn->pos) 145591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson current_prefix_length = mp; 1456c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger } 145791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson#endif 145891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson pn = (struct tnode *)n; /* Descend */ 145991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson chopped_off = 0; 146091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 146191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 146219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonbacktrace: 146319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off++; 146419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 146519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* As zero don't change the child key (cindex) */ 146691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1)))) 146719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off++; 146819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 146919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Decrease current_... with bits chopped off */ 147019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (current_prefix_length > pn->pos + pn->bits - chopped_off) 147119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson current_prefix_length = pn->pos + pn->bits - chopped_off; 147291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 147319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* 1474c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Either we do the actual chop off according or if we have 147519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * chopped off all bits in this tnode walk up to our parent. 147619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 147719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 147891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (chopped_off <= pn->bits) { 147919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex &= ~(1 << (chopped_off-1)); 148091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else { 1481c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (NODE_PARENT(pn) == NULL) 148219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto failed; 148391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 148419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Get Child's index */ 148519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits); 148619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pn = NODE_PARENT(pn); 148719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson chopped_off = 0; 148819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 148919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_FIB_TRIE_STATS 149019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->stats.backtrack++; 149119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 149219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto backtrace; 1493c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger } 149419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 149519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfailed: 1496c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger ret = 1; 149719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfound: 14982373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 149919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return ret; 150019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 150119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15022373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* only called from updater side */ 150319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int trie_leaf_remove(struct trie *t, t_key key) 150419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 150519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t_key cindex; 150619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tp = NULL; 150719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *n = t->trie; 150819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 150919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15100c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("entering trie_leaf_remove(%p)\n", n); 151119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 151219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Note that in the case skipped bits, those bits are *not* checked! 1513c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * When we finish this, we will have NULL or a T_LEAF, and the 151419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson * T_LEAF may or may not match our key. 151519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 151619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 151791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson while (n != NULL && IS_TNODE(n)) { 151819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *tn = (struct tnode *) n; 151919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson check_tnode(tn); 152019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); 152119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15220c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger BUG_ON(n && NODE_PARENT(n) != tn); 152391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 152419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = (struct leaf *) n; 152519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1526c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!n || !tkey_equals(l->key, key)) 152719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 1528c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 1529c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger /* 1530c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Key found. 1531c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger * Remove the leaf and rebalance the tree 153219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson */ 153319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 153419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->revision++; 153519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->size--; 153619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15372373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson preempt_disable(); 153819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tp = NODE_PARENT(n); 153919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tnode_free((struct tnode *) n); 154019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1541c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (tp) { 154219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cindex = tkey_extract_bits(key, tp->pos, tp->bits); 154319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson put_child(t, (struct tnode *)tp, cindex, NULL); 15442373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, trie_rebalance(t, tp)); 154591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 15462373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_assign_pointer(t->trie, NULL); 15472373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson preempt_enable(); 154819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 154919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 1; 155019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 155119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 155219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int 155319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 155491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct nlmsghdr *nlhdr, struct netlink_skb_parms *req) 155519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 155619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 155719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u32 key, mask; 155819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int plen = r->rtm_dst_len; 155919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson u8 tos = r->rtm_tos; 156019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa, *fa_to_delete; 156119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head *fa_head; 156219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 156391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson struct leaf_info *li; 156491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 156519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1566c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (plen > 32) 156719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 156819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 156919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = 0; 1570c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (rta->rta_dst) 157119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memcpy(&key, rta->rta_dst, 4); 157219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 157319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = ntohl(key); 157491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson mask = ntohl(inet_make_mask(plen)); 157519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1576c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (key & ~mask) 157719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -EINVAL; 157819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 157919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson key = key & mask; 158019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = fib_find_node(t, key); 158119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1582c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!l) 158319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -ESRCH; 158419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 158519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, plen); 158619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa = fib_find_alias(fa_head, tos, 0); 158719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 158819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!fa) 158919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -ESRCH; 159019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 15910c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t); 159219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 159319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_to_delete = NULL; 159419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = fa->fa_list.prev; 15952373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 159619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson list_for_each_entry(fa, fa_head, fa_list) { 159719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi = fa->fa_info; 159819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 159919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_tos != tos) 160019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 160119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 160219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if ((!r->rtm_type || 160319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_type == r->rtm_type) && 160419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson (r->rtm_scope == RT_SCOPE_NOWHERE || 160519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_scope == r->rtm_scope) && 160619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson (!r->rtm_protocol || 160719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fi->fib_protocol == r->rtm_protocol) && 160819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_nh_match(r, nlhdr, rta, fi) == 0) { 160919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_to_delete = fa; 161019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 161119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 161219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 161319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 161491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (!fa_to_delete) 161591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return -ESRCH; 161619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 161791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson fa = fa_to_delete; 161891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req); 161991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 162091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson l = fib_find_node(t, key); 1621772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson li = find_leaf_info(l, plen); 162219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16232373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_del_rcu(&fa->fa_list); 162419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 162591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (list_empty(fa_head)) { 16262373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_del_rcu(&li->hlist); 162791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson free_leaf_info(li); 16282373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson } 162919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 163091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (hlist_empty(&l->list)) 163191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson trie_leaf_remove(t, key); 163219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 163391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (fa->fa_state & FA_S_ACCESSED) 163491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson rt_cache_flush(-1); 163519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16362373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson fib_release_info(fa->fa_info); 16372373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson alias_free_mem_rcu(fa); 163891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return 0; 163919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 164019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 164119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int trie_flush_list(struct trie *t, struct list_head *head) 164219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 164319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa, *fa_node; 164419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int found = 0; 164519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 164619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson list_for_each_entry_safe(fa, fa_node, head, fa_list) { 164719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi = fa->fa_info; 164819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16492373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (fi && (fi->fib_flags & RTNH_F_DEAD)) { 16502373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_del_rcu(&fa->fa_list); 16512373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson fib_release_info(fa->fa_info); 16522373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson alias_free_mem_rcu(fa); 165319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson found++; 165419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 165519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 165619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return found; 165719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 165819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 165919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int trie_flush_leaf(struct trie *t, struct leaf *l) 166019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 166119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int found = 0; 166219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_head *lih = &l->list; 166319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct hlist_node *node, *tmp; 166419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf_info *li = NULL; 166519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 166619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson hlist_for_each_entry_safe(li, node, tmp, lih, hlist) { 166719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson found += trie_flush_list(t, &li->falh); 166819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 166919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (list_empty(&li->falh)) { 16702373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson hlist_del_rcu(&li->hlist); 167119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson free_leaf_info(li); 167219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 167319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 167419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return found; 167519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 167619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16772373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson/* rcu_read_lock needs to be hold by caller from readside */ 16782373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 167919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf) 168019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 168119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct node *c = (struct node *) thisleaf; 168219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct tnode *p; 168319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int idx; 16842373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson struct node *trie = rcu_dereference(t->trie); 168519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1686c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (c == NULL) { 16872373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (trie == NULL) 168819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 168919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16902373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (IS_LEAF(trie)) /* trie w. just a leaf */ 16912373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return (struct leaf *) trie; 169219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 16932373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson p = (struct tnode*) trie; /* Start */ 169491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } else 169519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson p = (struct tnode *) NODE_PARENT(c); 1696c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 169719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson while (p) { 169819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int pos, last; 169919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 170019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* Find the next child of the parent */ 1701c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (c) 1702c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits); 1703c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger else 170419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson pos = 0; 170519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 170619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson last = 1 << p->bits; 170791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (idx = pos; idx < last ; idx++) { 17082373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson c = rcu_dereference(p->child[idx]); 17092373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 17102373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (!c) 171191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson continue; 171291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 171391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Decend if tnode */ 17142373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson while (IS_TNODE(c)) { 17152373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson p = (struct tnode *) c; 17162373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson idx = 0; 171791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 171891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Rightmost non-NULL branch */ 171991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (p && IS_TNODE(p)) 17202373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson while (!(c = rcu_dereference(p->child[idx])) 17212373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson && idx < (1<<p->bits)) idx++; 172291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 172391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson /* Done with this tnode? */ 17242373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson if (idx >= (1 << p->bits) || !c) 172591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson goto up; 172619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 17272373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson return (struct leaf *) c; 172819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 172919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonup: 173019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson /* No more children go up one step */ 173191b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson c = (struct node *) p; 173219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson p = (struct tnode *) NODE_PARENT(p); 173319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 173419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; /* Ready. Root of trie */ 173519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 173619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 173719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int fn_trie_flush(struct fib_table *tb) 173819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 173919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 174019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *ll = NULL, *l = NULL; 174119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int found = 0, h; 174219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 174319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t->revision++; 174419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 174591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (h = 0; (l = nextleaf(t, l)) != NULL; h++) { 174619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson found += trie_flush_leaf(t, l); 174719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 174819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (ll && hlist_empty(&ll->list)) 174919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_leaf_remove(t, ll->key); 175019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ll = l; 175119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 175219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 175319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (ll && hlist_empty(&ll->list)) 175419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_leaf_remove(t, ll->key); 175519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 17560c7770c740156c8802c23d24fc094d06967d997dStephen Hemminger pr_debug("trie_flush found=%d\n", found); 175719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return found; 175819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 175919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 176091b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonstatic int trie_last_dflt = -1; 176119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 176219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic void 176319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonfn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) 176419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 176519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 176619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int order, last_idx; 176719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *fi = NULL; 176819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *last_resort; 176919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa = NULL; 177019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head *fa_head; 177119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l; 177219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 177319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson last_idx = -1; 177419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson last_resort = NULL; 177519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson order = -1; 177619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 17772373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_lock(); 1778c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 177919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson l = fib_find_node(t, 0); 1780c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!l) 178119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 178219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 178319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, 0); 1784c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!fa_head) 178519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 178619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1787c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (list_empty(fa_head)) 178819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 178919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 17902373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_for_each_entry_rcu(fa, fa_head, fa_list) { 179119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_info *next_fi = fa->fa_info; 179291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 179319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fa->fa_scope != res->scope || 179419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_type != RTN_UNICAST) 179519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 179691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 179719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (next_fi->fib_priority > res->fi->fib_priority) 179819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 179919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!next_fi->fib_nh[0].nh_gw || 180019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK) 180119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 180219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_state |= FA_S_ACCESSED; 180391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 180419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fi == NULL) { 180519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (next_fi != res->fi) 180619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson break; 180719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } else if (!fib_detect_death(fi, order, &last_resort, 180819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson &last_idx, &trie_last_dflt)) { 180919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (res->fi) 181019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_info_put(res->fi); 181119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson res->fi = fi; 181219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson atomic_inc(&fi->fib_clntref); 181319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = order; 181419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 181519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 181619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fi = next_fi; 181719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson order++; 181819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 181919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (order <= 0 || fi == NULL) { 182019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = -1; 182119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 182219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 182319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 182419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) { 182519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (res->fi) 182619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_info_put(res->fi); 182719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson res->fi = fi; 182819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson atomic_inc(&fi->fib_clntref); 182919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = order; 183019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 183119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 183219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (last_idx >= 0) { 183319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (res->fi) 183419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fib_info_put(res->fi); 183519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson res->fi = last_resort; 183619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (last_resort) 183719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson atomic_inc(&last_resort->fib_clntref); 183819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 183919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_last_dflt = last_idx; 184019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson out:; 18412373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 184219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 184319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1844c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb, 184519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct sk_buff *skb, struct netlink_callback *cb) 184619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 184719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int i, s_i; 184819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_alias *fa; 184919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 185091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson u32 xkey = htonl(key); 185119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 185291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson s_i = cb->args[3]; 185319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i = 0; 185419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 18552373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson /* rcu_read_lock is hold by caller */ 18562373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 18572373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson list_for_each_entry_rcu(fa, fah, fa_list) { 185819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (i < s_i) { 185919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i++; 186019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 186119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 186278c6671a88313fd3c4364dc46e8c8186612616b8Stephen Hemminger BUG_ON(!fa->fa_info); 186319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 186419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid, 186519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->nlh->nlmsg_seq, 186619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson RTM_NEWROUTE, 186719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_id, 186819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_type, 186919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_scope, 187019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson &xkey, 187119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson plen, 187219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa->fa_tos, 187390f66914c89b0be63548d4387d1211280aa7bc8eDavid S. Miller fa->fa_info, 0) < 0) { 187419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->args[3] = i; 187519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -1; 187691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 187719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson i++; 187819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 187991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cb->args[3] = i; 188019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return skb->len; 188119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 188219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1883c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemmingerstatic int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb, 188419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct netlink_callback *cb) 188519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 188619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int h, s_h; 188719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct list_head *fa_head; 188819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct leaf *l = NULL; 188919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 189091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson s_h = cb->args[2]; 189119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 189291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (h = 0; (l = nextleaf(t, l)) != NULL; h++) { 189319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (h < s_h) 189419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 189519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (h > s_h) 189619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(&cb->args[3], 0, 189719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson sizeof(cb->args) - 3*sizeof(cb->args[0])); 189819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 189919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fa_head = get_fa_head(l, plen); 190091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 1901c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (!fa_head) 190219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 190319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1904c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (list_empty(fa_head)) 190519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 190619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 190719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) { 190891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cb->args[2] = h; 190919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -1; 191019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 191119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 191291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson cb->args[2] = h; 191319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return skb->len; 191419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 191519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 191619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstatic int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb) 191719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 191819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int m, s_m; 191919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t = (struct trie *) tb->tb_data; 192019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 192119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson s_m = cb->args[1]; 192219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 19232373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_lock(); 192491b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson for (m = 0; m <= 32; m++) { 192519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (m < s_m) 192619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson continue; 192719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (m > s_m) 192819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(&cb->args[2], 0, 192991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson sizeof(cb->args) - 2*sizeof(cb->args[0])); 193019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 193119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) { 193219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->args[1] = m; 193319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 193419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 193519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 19362373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 193719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson cb->args[1] = m; 193819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return skb->len; 193991b9a277fc4d207249e459a455abf804ebb5499dOlof Johanssonout: 19402373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 194119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return -1; 194219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 194319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 194419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson/* Fix more generic FIB names for init later */ 194519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 194619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#ifdef CONFIG_IP_MULTIPLE_TABLES 194719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct fib_table * fib_hash_init(int id) 194819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#else 194919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonstruct fib_table * __init fib_hash_init(int id) 195019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif 195119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 195219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct fib_table *tb; 195319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct trie *t; 195419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 195519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (fn_alias_kmem == NULL) 195619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson fn_alias_kmem = kmem_cache_create("ip_fib_alias", 195719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson sizeof(struct fib_alias), 195819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 0, SLAB_HWCACHE_ALIGN, 195919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson NULL, NULL); 196019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 196119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie), 196219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson GFP_KERNEL); 196319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (tb == NULL) 196419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 196519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 196619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_id = id; 196719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_lookup = fn_trie_lookup; 196819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_insert = fn_trie_insert; 196919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_delete = fn_trie_delete; 197019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_flush = fn_trie_flush; 197119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_select_default = fn_trie_select_default; 197219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson tb->tb_dump = fn_trie_dump; 197319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson memset(tb->tb_data, 0, sizeof(struct trie)); 197419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 197519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson t = (struct trie *) tb->tb_data; 197619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 197719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson trie_init(t); 197819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1979c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger if (id == RT_TABLE_LOCAL) 198091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson trie_local = t; 1981c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger else if (id == RT_TABLE_MAIN) 198291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson trie_main = t; 198319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 198419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (id == RT_TABLE_LOCAL) 198578c6671a88313fd3c4364dc46e8c8186612616b8Stephen Hemminger printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION); 198619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 198719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return tb; 198819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 198919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1990cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#ifdef CONFIG_PROC_FS 1991cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* Depth first Trie walk iterator */ 1992cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstruct fib_trie_iter { 1993cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *tnode; 1994cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct trie *trie; 1995cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned index; 1996cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned depth; 1997cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger}; 199819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 1999cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct node *fib_trie_get_next(struct fib_trie_iter *iter) 200019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2001cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *tn = iter->tnode; 2002cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned cindex = iter->index; 2003cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *p; 200419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2005cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger pr_debug("get_next iter={node=%p index=%d depth=%d}\n", 2006cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode, iter->index, iter->depth); 2007cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerrescan: 2008cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger while (cindex < (1<<tn->bits)) { 2009cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n = tnode_get_child(tn, cindex); 201019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2011cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (n) { 2012cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_LEAF(n)) { 2013cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode = tn; 2014cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->index = cindex + 1; 2015cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } else { 2016cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* push down one level */ 2017cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode = (struct tnode *) n; 2018cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->index = 0; 2019cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger ++iter->depth; 2020cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2021cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 2022cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 202319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2024cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger ++cindex; 2025cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 202691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2027cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* Current node exhausted, pop back up */ 2028cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger p = NODE_PARENT(tn); 2029cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (p) { 2030cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1; 2031cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger tn = p; 2032cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger --iter->depth; 2033cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto rescan; 203419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 2035cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2036cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* got root? */ 2037cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return NULL; 203819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 203919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2040cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct node *fib_trie_get_first(struct fib_trie_iter *iter, 2041cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct trie *t) 204219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 20435ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson struct node *n ; 20445ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson 20455ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson if(!t) 20465ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson return NULL; 20475ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson 20485ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson n = rcu_dereference(t->trie); 20495ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson 20505ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson if(!iter) 20515ddf0eb2bfd613e941dd8748870c71da2e5ad409Robert Olsson return NULL; 205219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2053cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (n && IS_TNODE(n)) { 2054cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->tnode = (struct tnode *) n; 2055cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->trie = t; 2056cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger iter->index = 0; 20571d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson iter->depth = 1; 2058cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 205991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson } 2060cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return NULL; 2061cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 206291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2063cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void trie_collect_stats(struct trie *t, struct trie_stat *s) 2064cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2065cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n; 2066cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter iter; 206791b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2068cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(s, 0, sizeof(*s)); 206991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2070cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rcu_read_lock(); 2071cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (n = fib_trie_get_first(&iter, t); n; 2072cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger n = fib_trie_get_next(&iter)) { 2073cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_LEAF(n)) { 2074cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->leaves++; 2075cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->totdepth += iter.depth; 2076cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (iter.depth > s->maxdepth) 2077cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->maxdepth = iter.depth; 2078cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } else { 2079cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger const struct tnode *tn = (const struct tnode *) n; 2080cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger int i; 2081cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2082cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->tnodes++; 208306ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson if(tn->bits < MAX_STAT_DEPTH) 208406ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson s->nodesizes[tn->bits]++; 208506ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson 2086cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i = 0; i < (1<<tn->bits); i++) 2087cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!tn->child[i]) 2088cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger s->nullpointers++; 208919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 209019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 20912373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson rcu_read_unlock(); 209219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 209319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2094cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* 2095cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * This outputs /proc/net/fib_triestats 2096cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger */ 2097cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void trie_show_stats(struct seq_file *seq, struct trie_stat *stat) 209819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2099cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned i, max, pointers, bytes, avdepth; 2100c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 2101cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (stat->leaves) 2102cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger avdepth = stat->totdepth*100 / stat->leaves; 2103cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger else 2104cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger avdepth = 0; 210591b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2106cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tAver depth: %d.%02d\n", avdepth / 100, avdepth % 100 ); 2107cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth); 210891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2109cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tLeaves: %u\n", stat->leaves); 211091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2111cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger bytes = sizeof(struct leaf) * stat->leaves; 2112cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes); 2113cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger bytes += sizeof(struct tnode) * stat->tnodes; 211419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 211506ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson max = MAX_STAT_DEPTH; 211606ef921d60bbf6f765d1b9492fb4fc88ac7814bdRobert Olsson while (max > 0 && stat->nodesizes[max-1] == 0) 2117cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger max--; 211819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2119cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger pointers = 0; 2120cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i = 1; i <= max; i++) 2121cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (stat->nodesizes[i] != 0) { 2122cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, " %d: %d", i, stat->nodesizes[i]); 2123cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger pointers += (1<<i) * stat->nodesizes[i]; 2124cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2125cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_putc(seq, '\n'); 2126cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "\tPointers: %d\n", pointers); 21272373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 2128cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger bytes += sizeof(struct node *) * pointers; 2129cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers); 2130cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Total size: %d kB\n", (bytes + 1023) / 1024); 21312373ce1ca04dd46bf2b8b0f9a799eb2a90da92fbRobert Olsson 2132cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#ifdef CONFIG_IP_FIB_TRIE_STATS 2133cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Counters:\n---------\n"); 2134cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"gets = %d\n", t->stats.gets); 2135cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"backtracks = %d\n", t->stats.backtrack); 2136cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed); 2137cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss); 2138cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit); 2139cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped); 2140cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#ifdef CLEAR_STATS 2141cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(&(t->stats), 0, sizeof(t->stats)); 2142cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#endif 2143cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger#endif /* CONFIG_IP_FIB_TRIE_STATS */ 2144cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 214519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2146cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_triestat_seq_show(struct seq_file *seq, void *v) 2147cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2148cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct trie_stat *stat; 214991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2150cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger stat = kmalloc(sizeof(*stat), GFP_KERNEL); 2151cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!stat) 2152cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return -ENOMEM; 215391b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2154cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n", 2155cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger sizeof(struct leaf), sizeof(struct tnode)); 215691b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2157cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (trie_local) { 2158cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Local:\n"); 2159cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_collect_stats(trie_local, stat); 2160cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_show_stats(seq, stat); 2161cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 216291b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2163cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (trie_main) { 2164cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "Main:\n"); 2165cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_collect_stats(trie_main, stat); 2166cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger trie_show_stats(seq, stat); 216719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 2168cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger kfree(stat); 216919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2170cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 217119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 217219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2173cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_triestat_seq_open(struct inode *inode, struct file *file) 217419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2175cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return single_open(file, fib_triestat_seq_show, NULL); 217619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 217719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2178cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct file_operations fib_triestat_fops = { 2179cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .owner = THIS_MODULE, 2180cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .open = fib_triestat_seq_open, 2181cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .read = seq_read, 2182cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .llseek = seq_lseek, 2183cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .release = single_release, 2184cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger}; 2185cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2186cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct node *fib_trie_get_idx(struct fib_trie_iter *iter, 2187cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger loff_t pos) 218819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2189cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger loff_t idx = 0; 2190cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n; 2191cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2192cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (n = fib_trie_get_first(iter, trie_local); 2193cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger n; ++idx, n = fib_trie_get_next(iter)) { 2194cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (pos == idx) 2195cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 2196cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2197cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2198cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (n = fib_trie_get_first(iter, trie_main); 2199cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger n; ++idx, n = fib_trie_get_next(iter)) { 2200cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (pos == idx) 2201cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return n; 2202cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 220319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return NULL; 220419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 220519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2206cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos) 220719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2208cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rcu_read_lock(); 2209cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (*pos == 0) 221091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson return SEQ_START_TOKEN; 2211cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return fib_trie_get_idx(seq->private, *pos - 1); 221219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 221319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2214cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos) 221519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2216cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter *iter = seq->private; 2217cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger void *l = v; 2218cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 221919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson ++*pos; 222091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson if (v == SEQ_START_TOKEN) 2221cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return fib_trie_get_idx(iter, 0); 222219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2223cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger v = fib_trie_get_next(iter); 2224cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger BUG_ON(v == l); 2225cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (v) 2226cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return v; 222719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2228cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger /* continue scan in next trie */ 2229cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (iter->trie == trie_local) 2230cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return fib_trie_get_first(iter, trie_main); 223119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2232cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return NULL; 2233cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 223419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2235cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void fib_trie_seq_stop(struct seq_file *seq, void *v) 223619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2237cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rcu_read_unlock(); 2238cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 223991b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2240cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic void seq_indent(struct seq_file *seq, int n) 2241cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2242cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger while (n-- > 0) seq_puts(seq, " "); 2243cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 224419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2245cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic inline const char *rtn_scope(enum rt_scope_t s) 2246cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2247cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger static char buf[32]; 224819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2249cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger switch(s) { 2250cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_UNIVERSE: return "universe"; 2251cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_SITE: return "site"; 2252cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_LINK: return "link"; 2253cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_HOST: return "host"; 2254cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger case RT_SCOPE_NOWHERE: return "nowhere"; 2255cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger default: 2256cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(buf, sizeof(buf), "scope=%d", s); 2257cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return buf; 2258cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2259cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger} 226019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2261cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic const char *rtn_type_names[__RTN_MAX] = { 2262cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_UNSPEC] = "UNSPEC", 2263cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_UNICAST] = "UNICAST", 2264cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_LOCAL] = "LOCAL", 2265cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_BROADCAST] = "BROADCAST", 2266cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_ANYCAST] = "ANYCAST", 2267cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_MULTICAST] = "MULTICAST", 2268cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_BLACKHOLE] = "BLACKHOLE", 2269cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_UNREACHABLE] = "UNREACHABLE", 2270cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_PROHIBIT] = "PROHIBIT", 2271cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_THROW] = "THROW", 2272cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_NAT] = "NAT", 2273cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [RTN_XRESOLVE] = "XRESOLVE", 2274cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger}; 227519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2276cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic inline const char *rtn_type(unsigned t) 2277cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger{ 2278cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger static char buf[32]; 227919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2280cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (t < __RTN_MAX && rtn_type_names[t]) 2281cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return rtn_type_names[t]; 2282cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(buf, sizeof(buf), "type %d", t); 2283cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return buf; 228419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 228519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2286cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* Pretty print the trie */ 2287cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_trie_seq_show(struct seq_file *seq, void *v) 228819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2289cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger const struct fib_trie_iter *iter = seq->private; 2290cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct node *n = v; 2291c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger 2292cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (v == SEQ_START_TOKEN) 2293cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 229419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2295cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_TNODE(n)) { 2296cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct tnode *tn = (struct tnode *) n; 2297cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger t_key prf = ntohl(MASK_PFX(tn->key, tn->pos)); 229891b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2299cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!NODE_PARENT(n)) { 2300cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (iter->trie == trie_local) 2301cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_puts(seq, "<local>:\n"); 2302cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger else 2303cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_puts(seq, "<main>:\n"); 23041d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson } 23051d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson seq_indent(seq, iter->depth-1); 23061d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n", 23071d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson NIPQUAD(prf), tn->pos, tn->bits, tn->full_children, 23081d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson tn->empty_children); 23091d25cd6cc2528e4af12ab18e84fe95ed78f3f21aRobert Olsson 2310cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } else { 2311cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct leaf *l = (struct leaf *) n; 2312cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger int i; 2313cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger u32 val = ntohl(l->key); 2314cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2315cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_indent(seq, iter->depth); 2316cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val)); 2317cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i = 32; i >= 0; i--) { 2318772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct leaf_info *li = find_leaf_info(l, i); 2319cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (li) { 2320cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_alias *fa; 2321cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger list_for_each_entry_rcu(fa, &li->falh, fa_list) { 2322cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_indent(seq, iter->depth+1); 2323cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, " /%d %s %s", i, 2324cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rtn_scope(fa->fa_scope), 2325cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rtn_type(fa->fa_type)); 2326cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fa->fa_tos) 2327cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "tos =%d\n", 2328cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fa->fa_tos); 2329cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_putc(seq, '\n'); 2330cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2331cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 2332cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 233319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 2334cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 233519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 233619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 233719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2338cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct seq_operations fib_trie_seq_ops = { 2339cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .start = fib_trie_seq_start, 2340cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .next = fib_trie_seq_next, 2341cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .stop = fib_trie_seq_stop, 2342cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .show = fib_trie_seq_show, 234319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 234419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2345cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_trie_seq_open(struct inode *inode, struct file *file) 234619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 234719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct seq_file *seq; 234819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int rc = -ENOMEM; 2349cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL); 235019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2351cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!s) 2352cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out; 2353cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2354cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rc = seq_open(file, &fib_trie_seq_ops); 235519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (rc) 235619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out_kfree; 235719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2358cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq = file->private_data; 2359cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq->private = s; 2360cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(s, 0, sizeof(*s)); 236119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout: 236219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return rc; 236319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout_kfree: 2364cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger kfree(s); 236519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 236619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 236719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2368cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct file_operations fib_trie_fops = { 2369cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .owner = THIS_MODULE, 2370cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .open = fib_trie_seq_open, 2371cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .read = seq_read, 2372cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .llseek = seq_lseek, 2373c877efb207bf4629cfa97ac13412f7392a873485Stephen Hemminger .release = seq_release_private, 237419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 237519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2376cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi) 237719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2378cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger static unsigned type2flags[RTN_MAX + 1] = { 2379cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger [7] = RTF_REJECT, [8] = RTF_REJECT, 2380cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger }; 2381cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned flags = type2flags[type]; 238219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2383cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fi && fi->fib_nh->nh_gw) 2384cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger flags |= RTF_GATEWAY; 2385cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (mask == 0xFFFFFFFF) 2386cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger flags |= RTF_HOST; 2387cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger flags |= RTF_UP; 2388cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return flags; 238919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 239019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2391cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger/* 2392cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * This outputs /proc/net/route. 2393cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * The format of the file is not supposed to be changed 2394cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * and needs to be same as fib_hash output to avoid breaking 2395cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger * legacy utilities 2396cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger */ 2397cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_route_seq_show(struct seq_file *seq, void *v) 239819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2399c9e53cbe7ad6eabb3c7c5140b6127b4e5f9ee840Patrick McHardy const struct fib_trie_iter *iter = seq->private; 2400cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct leaf *l = v; 2401cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger int i; 2402cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger char bf[128]; 240319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2404cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (v == SEQ_START_TOKEN) { 2405cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway " 2406cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU" 2407cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "\tWindow\tIRTT"); 2408cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 2409cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 241019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2411c9e53cbe7ad6eabb3c7c5140b6127b4e5f9ee840Patrick McHardy if (iter->trie == trie_local) 2412c9e53cbe7ad6eabb3c7c5140b6127b4e5f9ee840Patrick McHardy return 0; 2413cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (IS_TNODE(l)) 2414cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return 0; 241519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2416cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger for (i=32; i>=0; i--) { 2417772cb712b1373d335ef2874ea357ec681edc754bRobert Olsson struct leaf_info *li = find_leaf_info(l, i); 2418cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_alias *fa; 2419cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger u32 mask, prefix; 242091b9a277fc4d207249e459a455abf804ebb5499dOlof Johansson 2421cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!li) 2422cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger continue; 242319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2424cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger mask = inet_make_mask(li->plen); 2425cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger prefix = htonl(l->key); 242619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2427cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger list_for_each_entry_rcu(fa, &li->falh, fa_list) { 24281371e37da299d4df6267ad0ddf010435782c28e9Herbert Xu const struct fib_info *fi = fa->fa_info; 2429cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger unsigned flags = fib_flag_trans(fa->fa_type, mask, fi); 243019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2431cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fa->fa_type == RTN_BROADCAST 2432cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger || fa->fa_type == RTN_MULTICAST) 2433cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger continue; 243419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2435cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (fi) 2436cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(bf, sizeof(bf), 2437cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u", 2438cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_dev ? fi->fib_dev->name : "*", 2439cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger prefix, 2440cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_nh->nh_gw, flags, 0, 0, 2441cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_priority, 2442cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger mask, 2443cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger (fi->fib_advmss ? fi->fib_advmss + 40 : 0), 2444cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_window, 2445cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger fi->fib_rtt >> 3); 2446cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger else 2447cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger snprintf(bf, sizeof(bf), 2448cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u", 2449cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger prefix, 0, flags, 0, 0, 0, 2450cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger mask, 0, 0, 0); 245119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2452cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq_printf(seq, "%-127s\n", bf); 2453cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger } 245419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson } 245519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 245619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 245719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 245819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2459cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct seq_operations fib_route_seq_ops = { 2460cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .start = fib_trie_seq_start, 2461cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .next = fib_trie_seq_next, 2462cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .stop = fib_trie_seq_stop, 2463cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .show = fib_route_seq_show, 246419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 246519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2466cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic int fib_route_seq_open(struct inode *inode, struct file *file) 246719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 246819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson struct seq_file *seq; 246919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson int rc = -ENOMEM; 2470cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL); 247119baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2472cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!s) 2473cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out; 2474cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2475cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger rc = seq_open(file, &fib_route_seq_ops); 247619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson if (rc) 247719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out_kfree; 247819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2479cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq = file->private_data; 2480cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger seq->private = s; 2481cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger memset(s, 0, sizeof(*s)); 248219baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout: 248319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return rc; 248419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonout_kfree: 2485cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger kfree(s); 248619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson goto out; 248719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 248819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 2489cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerstatic struct file_operations fib_route_fops = { 2490cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .owner = THIS_MODULE, 2491cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .open = fib_route_seq_open, 2492cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .read = seq_read, 2493cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .llseek = seq_lseek, 2494cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger .release = seq_release_private, 249519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson}; 249619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 249719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonint __init fib_proc_init(void) 249819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 2499cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops)) 2500cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out1; 2501cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2502cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops)) 2503cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out2; 2504cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2505cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops)) 2506cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger goto out3; 2507cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 250819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson return 0; 2509cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger 2510cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerout3: 2511cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("fib_triestat"); 2512cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerout2: 2513cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("fib_trie"); 2514cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemmingerout1: 2515cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger return -ENOMEM; 251619baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 251719baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 251819baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olssonvoid __init fib_proc_exit(void) 251919baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson{ 252019baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson proc_net_remove("fib_trie"); 2521cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("fib_triestat"); 2522cb7b593c2c808b32a1ea188599713c434b95f849Stephen Hemminger proc_net_remove("route"); 252319baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson} 252419baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson 252519baf839ff4a8daa1f2a7400897094fc18e4f5e9Robert Olsson#endif /* CONFIG_PROC_FS */ 2526