Release 4.11 net/ipv4/fib_trie.c
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version
* 2 of the License, or (at your option) any later version.
*
* Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
* & Swedish University of Agricultural Sciences.
*
* Jens Laas <jens.laas@data.slu.se> Swedish University of
* Agricultural Sciences.
*
* Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
*
* This work is based on the LPC-trie which is originally described in:
*
* An experimental study of compression methods for dynamic tries
* Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
* http://www.csc.kth.se/~snilsson/software/dyntrie2/
*
*
* IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
* IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
*
*
* Code from fib_hash has been reused which includes the following header:
*
*
* INET An implementation of the TCP/IP protocol suite for the LINUX
* operating system. INET is implemented using the BSD Socket
* interface as the means of communication with the user level.
*
* IPv4 FIB: lookup engine and maintenance routines.
*
*
* Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version
* 2 of the License, or (at your option) any later version.
*
* Substantial contributions to this work comes from:
*
* David S. Miller, <davem@davemloft.net>
* Stephen Hemminger <shemminger@osdl.org>
* Paul E. McKenney <paulmck@us.ibm.com>
* Patrick McHardy <kaber@trash.net>
*/
#define VERSION "0.409"
#include <linux/uaccess.h>
#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/inetdevice.h>
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
#include <linux/rcupdate.h>
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/export.h>
#include <linux/vmalloc.h>
#include <linux/notifier.h>
#include <net/net_namespace.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#include <net/tcp.h>
#include <net/sock.h>
#include <net/ip_fib.h>
#include <trace/events/fib.h>
#include "fib_lookup.h"
static unsigned int fib_seq_sum(void)
{
unsigned int fib_seq = 0;
struct net *net;
rtnl_lock();
for_each_net(net)
fib_seq += net->ipv4.fib_seq;
rtnl_unlock();
return fib_seq;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 33 | 80.49% | 1 | 50.00% |
| Jiri Pirko | 8 | 19.51% | 1 | 50.00% |
| Total | 41 | 100.00% | 2 | 100.00% |
static ATOMIC_NOTIFIER_HEAD(fib_chain);
static int call_fib_notifier(struct notifier_block *nb, struct net *net,
enum fib_event_type event_type,
struct fib_notifier_info *info)
{
info->net = net;
return nb->notifier_call(nb, event_type, info);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 29 | 67.44% | 1 | 50.00% |
| Jiri Pirko | 14 | 32.56% | 1 | 50.00% |
| Total | 43 | 100.00% | 2 | 100.00% |
static void fib_rules_notify(struct net *net, struct notifier_block *nb,
enum fib_event_type event_type)
{
#ifdef CONFIG_IP_MULTIPLE_TABLES
struct fib_notifier_info info;
if (net->ipv4.fib_has_custom_rules)
call_fib_notifier(nb, net, event_type, &info);
#endif
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 30 | 61.22% | 2 | 66.67% |
| Jiri Pirko | 19 | 38.78% | 1 | 33.33% |
| Total | 49 | 100.00% | 3 | 100.00% |
static void fib_notify(struct net *net, struct notifier_block *nb,
enum fib_event_type event_type);
static int call_fib_entry_notifier(struct notifier_block *nb, struct net *net,
enum fib_event_type event_type, u32 dst,
int dst_len, struct fib_info *fi,
u8 tos, u8 type, u32 tb_id)
{
struct fib_entry_notifier_info info = {
.dst = dst,
.dst_len = dst_len,
.fi = fi,
.tos = tos,
.type = type,
.tb_id = tb_id,
};
return call_fib_notifier(nb, net, event_type, &info.info);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Jiri Pirko | 82 | 90.11% | 1 | 50.00% |
| Ido Schimmel | 9 | 9.89% | 1 | 50.00% |
| Total | 91 | 100.00% | 2 | 100.00% |
static bool fib_dump_is_consistent(struct notifier_block *nb,
void (*cb)(struct notifier_block *nb),
unsigned int fib_seq)
{
atomic_notifier_chain_register(&fib_chain, nb);
if (fib_seq == fib_seq_sum())
return true;
atomic_notifier_chain_unregister(&fib_chain, nb);
if (cb)
cb(nb);
return false;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 60 | 92.31% | 1 | 33.33% |
| Robert Olsson | 4 | 6.15% | 1 | 33.33% |
| Alexander Duyck | 1 | 1.54% | 1 | 33.33% |
| Total | 65 | 100.00% | 3 | 100.00% |
#define FIB_DUMP_MAX_RETRIES 5
int register_fib_notifier(struct notifier_block *nb,
void (*cb)(struct notifier_block *nb))
{
int retries = 0;
do {
unsigned int fib_seq = fib_seq_sum();
struct net *net;
/* Mutex semantics guarantee that every change done to
* FIB tries before we read the change sequence counter
* is now visible to us.
*/
rcu_read_lock();
for_each_net_rcu(net) {
fib_rules_notify(net, nb, FIB_EVENT_RULE_ADD);
fib_notify(net, nb, FIB_EVENT_ENTRY_ADD);
}
rcu_read_unlock();
if (fib_dump_is_consistent(nb, cb, fib_seq))
return 0;
} while (++retries < FIB_DUMP_MAX_RETRIES);
return -EBUSY;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 99 | 100.00% | 1 | 100.00% |
| Total | 99 | 100.00% | 1 | 100.00% |
EXPORT_SYMBOL(register_fib_notifier);
int unregister_fib_notifier(struct notifier_block *nb)
{
return atomic_notifier_chain_unregister(&fib_chain, nb);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 19 | 100.00% | 1 | 100.00% |
| Total | 19 | 100.00% | 1 | 100.00% |
EXPORT_SYMBOL(unregister_fib_notifier);
int call_fib_notifiers(struct net *net, enum fib_event_type event_type,
struct fib_notifier_info *info)
{
net->ipv4.fib_seq++;
info->net = net;
return atomic_notifier_call_chain(&fib_chain, event_type, info);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 43 | 100.00% | 1 | 100.00% |
| Total | 43 | 100.00% | 1 | 100.00% |
static int call_fib_entry_notifiers(struct net *net,
enum fib_event_type event_type, u32 dst,
int dst_len, struct fib_info *fi,
u8 tos, u8 type, u32 tb_id)
{
struct fib_entry_notifier_info info = {
.dst = dst,
.dst_len = dst_len,
.fi = fi,
.tos = tos,
.type = type,
.tb_id = tb_id,
};
return call_fib_notifiers(net, event_type, &info.info);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Ido Schimmel | 84 | 100.00% | 1 | 100.00% |
| Total | 84 | 100.00% | 1 | 100.00% |
#define MAX_STAT_DEPTH 32
#define KEYLENGTH (8*sizeof(t_key))
#define KEY_MAX ((t_key)~0)
typedef unsigned int t_key;
#define IS_TRIE(n) ((n)->pos >= KEYLENGTH)
#define IS_TNODE(n) ((n)->bits)
#define IS_LEAF(n) (!(n)->bits)
struct key_vector {
t_key key;
unsigned char pos; /* 2log(KEYLENGTH) bits needed */
unsigned char bits; /* 2log(KEYLENGTH) bits needed */
unsigned char slen;
union {
/* This list pointer if valid if (pos | bits) == 0 (LEAF) */
struct hlist_head leaf;
/* This array is valid if (pos | bits) > 0 (TNODE) */
struct key_vector __rcu *tnode[0];
};
};
struct tnode {
struct rcu_head rcu;
t_key empty_children; /* KEYLENGTH bits needed */
t_key full_children; /* KEYLENGTH bits needed */
struct key_vector __rcu *parent;
struct key_vector kv[1];
#define tn_bits kv[0].bits
};
#define TNODE_SIZE(n) offsetof(struct tnode, kv[0].tnode[n])
#define LEAF_SIZE TNODE_SIZE(1)
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats {
unsigned int gets;
unsigned int backtrack;
unsigned int semantic_match_passed;
unsigned int semantic_match_miss;
unsigned int null_node_hit;
unsigned int resize_node_skipped;
};
#endif
struct trie_stat {
unsigned int totdepth;
unsigned int maxdepth;
unsigned int tnodes;
unsigned int leaves;
unsigned int nullpointers;
unsigned int prefixes;
unsigned int nodesizes[MAX_STAT_DEPTH];
};
struct trie {
struct key_vector kv[1];
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats __percpu *stats;
#endif
};
static struct key_vector *resize(struct trie *t, struct key_vector *tn);
static size_t tnode_free_size;
/*
* synchronize_rcu after call_rcu for that many pages; it should be especially
* useful before resizing the root node with PREEMPT_NONE configs; the value was
* obtained experimentally, aiming to avoid visible slowdown.
*/
static const int sync_pages = 128;
static struct kmem_cache *fn_alias_kmem __read_mostly;
static struct kmem_cache *trie_leaf_kmem __read_mostly;
static inline struct tnode *tn_info(struct key_vector *kv)
{
return container_of(kv, struct tnode, kv[0]);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 28 | 100.00% | 1 | 100.00% |
| Total | 28 | 100.00% | 1 | 100.00% |
/* caller must hold RTNL */
#define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
#define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
/* caller must hold RCU read lock or RTNL */
#define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
#define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
/* wrapper for rcu_assign_pointer */
static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
{
if (n)
rcu_assign_pointer(tn_info(n)->parent, tp);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 19 | 57.58% | 4 | 57.14% |
| Eric Dumazet | 13 | 39.39% | 2 | 28.57% |
| Stephen Hemminger | 1 | 3.03% | 1 | 14.29% |
| Total | 33 | 100.00% | 7 | 100.00% |
#define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p)
/* This provides us with the number of children in this node, in the case of a
* leaf this will return 0 meaning none of the children are accessible.
*/
static inline unsigned long child_length(const struct key_vector *tn)
{
return (1ul << tn->bits) & ~(1ul);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 17 | 60.71% | 4 | 80.00% |
| Stephen Hemminger | 11 | 39.29% | 1 | 20.00% |
| Total | 28 | 100.00% | 5 | 100.00% |
#define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)
static inline unsigned long get_index(t_key key, struct key_vector *kv)
{
unsigned long index = key ^ kv->key;
if ((BITS_PER_LONG <= KEYLENGTH) && (KEYLENGTH == kv->pos))
return 0;
return index >> kv->pos;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 52 | 100.00% | 2 | 100.00% |
| Total | 52 | 100.00% | 2 | 100.00% |
/* To understand this stuff, an understanding of keys and all their bits is
* necessary. Every node in the trie has a key associated with it, but not
* all of the bits in that key are significant.
*
* Consider a node 'n' and its parent 'tp'.
*
* If n is a leaf, every bit in its key is significant. Its presence is
* necessitated by path compression, since during a tree traversal (when
* searching for a leaf - unless we are doing an insertion) we will completely
* ignore all skipped bits we encounter. Thus we need to verify, at the end of
* a potentially successful search, that we have indeed been walking the
* correct key path.
*
* Note that we can never "miss" the correct key in the tree if present by
* following the wrong path. Path compression ensures that segments of the key
* that are the same for all keys with a given prefix are skipped, but the
* skipped part *is* identical for each node in the subtrie below the skipped
* bit! trie_insert() in this implementation takes care of that.
*
* if n is an internal node - a 'tnode' here, the various parts of its key
* have many different meanings.
*
* Example:
* _________________________________________________________________
* | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
* -----------------------------------------------------------------
* 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16
*
* _________________________________________________________________
* | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
* -----------------------------------------------------------------
* 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
*
* tp->pos = 22
* tp->bits = 3
* n->pos = 13
* n->bits = 4
*
* First, let's just ignore the bits that come before the parent tp, that is
* the bits from (tp->pos + tp->bits) to 31. They are *known* but at this
* point we do not use them for anything.
*
* The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
* index into the parent's child array. That is, they will be used to find
* 'n' among tp's children.
*
* The bits from (n->pos + n->bits) to (tp->pos - 1) - "S" - are skipped bits
* for the node n.
*
* All the bits we have seen so far are significant to the node n. The rest
* of the bits are really not needed or indeed known in n->key.
*
* The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
* n's child array, and will of course be different for each child.
*
* The rest of the bits, from 0 to (n->pos -1) - "u" - are completely unknown
* at this point.
*/
static const int halve_threshold = 25;
static const int inflate_threshold = 50;
static const int halve_threshold_root = 15;
static const int inflate_threshold_root = 30;
static void __alias_free_mem(struct rcu_head *head)
{
struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
kmem_cache_free(fn_alias_kmem, fa);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Robert Olsson | 33 | 100.00% | 2 | 100.00% |
| Total | 33 | 100.00% | 2 | 100.00% |
static inline void alias_free_mem_rcu(struct fib_alias *fa)
{
call_rcu(&fa->rcu, __alias_free_mem);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Robert Olsson | 22 | 100.00% | 2 | 100.00% |
| Total | 22 | 100.00% | 2 | 100.00% |
#define TNODE_KMALLOC_MAX \
ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
#define TNODE_VMALLOC_MAX \
ilog2((SIZE_MAX - TNODE_SIZE(0)) / sizeof(struct key_vector *))
static void __node_free_rcu(struct rcu_head *head)
{
struct tnode *n = container_of(head, struct tnode, rcu);
if (!n->tn_bits)
kmem_cache_free(trie_leaf_kmem, n);
else
kvfree(n);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Robert Olsson | 19 | 41.30% | 2 | 28.57% |
| Alexander Duyck | 15 | 32.61% | 2 | 28.57% |
| Stephen Hemminger | 11 | 23.91% | 2 | 28.57% |
| Tetsuo Handa | 1 | 2.17% | 1 | 14.29% |
| Total | 46 | 100.00% | 7 | 100.00% |
#define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu)
static struct tnode *tnode_alloc(int bits)
{
size_t size;
/* verify bits is within bounds */
if (bits > TNODE_VMALLOC_MAX)
return NULL;
/* determine size and verify it is non-zero and didn't overflow */
size = TNODE_SIZE(1ul << bits);
if (size <= PAGE_SIZE)
return kzalloc(size, GFP_KERNEL);
else
return vzalloc(size);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 26 | 47.27% | 2 | 28.57% |
| Patrick McHardy | 22 | 40.00% | 1 | 14.29% |
| Stephen Hemminger | 4 | 7.27% | 1 | 14.29% |
| Eric Dumazet | 2 | 3.64% | 2 | 28.57% |
| Robert Olsson | 1 | 1.82% | 1 | 14.29% |
| Total | 55 | 100.00% | 7 | 100.00% |
static inline void empty_child_inc(struct key_vector *n)
{
++tn_info(n)->empty_children ? : ++tn_info(n)->full_children;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 29 | 100.00% | 3 | 100.00% |
| Total | 29 | 100.00% | 3 | 100.00% |
static inline void empty_child_dec(struct key_vector *n)
{
tn_info(n)->empty_children-- ? : tn_info(n)->full_children--;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 29 | 100.00% | 3 | 100.00% |
| Total | 29 | 100.00% | 3 | 100.00% |
static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
{
struct key_vector *l;
struct tnode *kv;
kv = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
if (!kv)
return NULL;
/* initialize key vector */
l = kv->kv;
l->key = key;
l->pos = 0;
l->bits = 0;
l->slen = fa->fa_slen;
/* link leaf to fib alias */
INIT_HLIST_HEAD(&l->leaf);
hlist_add_head(&fa->fa_list, &l->leaf);
return l;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 56 | 55.45% | 7 | 70.00% |
| Robert Olsson | 28 | 27.72% | 1 | 10.00% |
| Firo Yang | 15 | 14.85% | 1 | 10.00% |
| Stephen Hemminger | 2 | 1.98% | 1 | 10.00% |
| Total | 101 | 100.00% | 10 | 100.00% |
static struct key_vector *tnode_new(t_key key, int pos, int bits)
{
unsigned int shift = pos + bits;
struct key_vector *tn;
struct tnode *tnode;
/* verify bits and pos their msb bits clear and values are valid */
BUG_ON(!bits || (shift > KEYLENGTH));
tnode = tnode_alloc(bits);
if (!tnode)
return NULL;
pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
sizeof(struct key_vector *) << bits);
if (bits == KEYLENGTH)
tnode->full_children = 1;
else
tnode->empty_children = 1ul << bits;
tn = tnode->kv;
tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
tn->pos = pos;
tn->bits = bits;
tn->slen = pos;
return tn;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 83 | 54.61% | 6 | 75.00% |
| Robert Olsson | 44 | 28.95% | 1 | 12.50% |
| Firo Yang | 25 | 16.45% | 1 | 12.50% |
| Total | 152 | 100.00% | 8 | 100.00% |
/* Check whether a tnode 'n' is "full", i.e. it is an internal node
* and no bits are skipped. See discussion in dyntree paper p. 6
*/
static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
{
return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Robert Olsson | 23 | 56.10% | 1 | 25.00% |
| Alexander Duyck | 18 | 43.90% | 3 | 75.00% |
| Total | 41 | 100.00% | 4 | 100.00% |
/* Add a child at position i overwriting the old value.
* Update the value of full_children and empty_children.
*/
static void put_child(struct key_vector *tn, unsigned long i,
struct key_vector *n)
{
struct key_vector *chi = get_child(tn, i);
int isfull, wasfull;
BUG_ON(i >= child_length(tn));
/* update emptyChildren, overflow into fullChildren */
if (!n && chi)
empty_child_inc(tn);
if (n && !chi)
empty_child_dec(tn);
/* update fullChildren */
wasfull = tnode_full(tn, chi);
isfull = tnode_full(tn, n);
if (wasfull && !isfull)
tn_info(tn)->full_children--;
else if (!wasfull && isfull)
tn_info(tn)->full_children++;
if (n && (tn->slen < n->slen))
tn->slen = n->slen;
rcu_assign_pointer(tn->tnode[i], n);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Robert Olsson | 100 | 64.10% | 2 | 12.50% |
| Alexander Duyck | 49 | 31.41% | 10 | 62.50% |
| Eric Dumazet | 3 | 1.92% | 2 | 12.50% |
| Stephen Hemminger | 2 | 1.28% | 1 | 6.25% |
| Ian Morris | 2 | 1.28% | 1 | 6.25% |
| Total | 156 | 100.00% | 16 | 100.00% |
static void update_children(struct key_vector *tn)
{
unsigned long i;
/* update all of the child parent pointers */
for (i = child_length(tn); i;) {
struct key_vector *inode = get_child(tn, --i);
if (!inode)
continue;
/* Either update the children of a tnode that
* already belongs to us or update the child
* to point to ourselves.
*/
if (node_parent(inode) == tn)
update_children(inode);
else
node_set_parent(inode, tn);
}
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 72 | 100.00% | 4 | 100.00% |
| Total | 72 | 100.00% | 4 | 100.00% |
static inline void put_child_root(struct key_vector *tp, t_key key,
struct key_vector *n)
{
if (IS_TRIE(tp))
rcu_assign_pointer(tp->tnode[0], n);
else
put_child(tp, get_index(key, tp), n);
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 54 | 100.00% | 4 | 100.00% |
| Total | 54 | 100.00% | 4 | 100.00% |
static inline void tnode_free_init(struct key_vector *tn)
{
tn_info(tn)->rcu.next = NULL;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 20 | 86.96% | 4 | 80.00% |
| Robert Olsson | 3 | 13.04% | 1 | 20.00% |
| Total | 23 | 100.00% | 5 | 100.00% |
static inline void tnode_free_append(struct key_vector *tn,
struct key_vector *n)
{
tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
tn_info(tn)->rcu.next = &tn_info(n)->rcu;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 52 | 100.00% | 4 | 100.00% |
| Total | 52 | 100.00% | 4 | 100.00% |
static void tnode_free(struct key_vector *tn)
{
struct callback_head *head = &tn_info(tn)->rcu;
while (head) {
head = head->next;
tnode_free_size += TNODE_SIZE(1ul << tn->bits);
node_free(tn);
tn = container_of(head, struct tnode, rcu)->kv;
}
if (tnode_free_size >= PAGE_SIZE * sync_pages) {
tnode_free_size = 0;
synchronize_rcu();
}
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 83 | 100.00% | 5 | 100.00% |
| Total | 83 | 100.00% | 5 | 100.00% |
static struct key_vector *replace(struct trie *t,
struct key_vector *oldtnode,
struct key_vector *tn)
{
struct key_vector *tp = node_parent(oldtnode);
unsigned long i;
/* setup the parent pointer out of and back into this node */
NODE_INIT_PARENT(tn, tp);
put_child_root(tp, tn->key, tn);
/* update all of the child parent pointers */
update_children(tn);
/* all pointers should be clean so we are done */
tnode_free(oldtnode);
/* resize children now that oldtnode is freed */
for (i = child_length(tn); i;) {
struct key_vector *inode = get_child(tn, --i);
/* resize child node */
if (tnode_full(tn, inode))
tn = resize(t, inode);
}
return tp;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 108 | 91.53% | 10 | 90.91% |
| Robert Olsson | 10 | 8.47% | 1 | 9.09% |
| Total | 118 | 100.00% | 11 | 100.00% |
static struct key_vector *inflate(struct trie *t,
struct key_vector *oldtnode)
{
struct key_vector *tn;
unsigned long i;
t_key m;
pr_debug("In inflate\n");
tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
if (!tn)
goto notnode;
/* prepare oldtnode to be freed */
tnode_free_init(oldtnode);
/* Assemble all of the pointers in our cluster, in this case that
* represents all of the pointers out of our allocated nodes that
* point to existing tnodes and the links between our allocated
* nodes.
*/
for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
struct key_vector *inode = get_child(oldtnode, --i);
struct key_vector *node0, *node1;
unsigned long j, k;
/* An empty child */
if (!inode)
continue;
/* A leaf or an internal node with skipped bits */
if (!tnode_full(oldtnode, inode)) {
put_child(tn, get_index(inode->key, tn), inode);
continue;
}
/* drop the node in the old tnode free list */
tnode_free_append(oldtnode, inode);
/* An internal node with two children */
if (inode->bits == 1) {
put_child(tn, 2 * i + 1, get_child(inode, 1));
put_child(tn, 2 * i, get_child(inode, 0));
continue;
}
/* We will replace this node 'inode' with two new
* ones, 'node0' and 'node1', each with half of the
* original children. The two new nodes will have
* a position one bit further down the key and this
* means that the "significant" part of their keys
* (see the discussion near the top of this file)
* will differ by one bit, which will be "0" in
* node0's key and "1" in node1's key. Since we are
* moving the key position by one step, the bit that
* we are moving away from - the bit at position
* (tn->pos) - is the one that will differ between
* node0 and node1. So... we synthesize that bit in the
* two new keys.
*/
node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
if (!node1)
goto nomem;
node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
tnode_free_append(tn, node1);
if (!node0)
goto nomem;
tnode_free_append(tn, node0);
/* populate child pointers in new nodes */
for (k = child_length(inode), j = k / 2; j;) {
put_child(node1, --j, get_child(inode, --k));
put_child(node0, j, get_child(inode, j));
put_child(node1, --j, get_child(inode, --k));
put_child(node0, j, get_child(inode, j));
}
/* link new nodes to parent */
NODE_INIT_PARENT(node1, tn);
NODE_INIT_PARENT(node0, tn);
/* link parent to nodes */
put_child(tn, 2 * i + 1, node1);
put_child(tn, 2 * i, node0);
}
/* setup the parent pointers into and out of this node */
return replace(t, oldtnode, tn);
nomem:
/* all pointers should be clean so we are done */
tnode_free(tn);
notnode:
return NULL;
}
Contributors
| Person | Tokens | Prop | Commits | CommitProp |
| Alexander Duyck | 387 | 90.63% | 9 | 52.94% |
| Robert Olsson | 30 | 7.03% | 4 | 23.53% |
| Eric Dumazet | 5 | 1.17% | 1 | 5.88% |
| Jens Låås | 3 | 0.70% | 1 | 5.88% |
| Stephen Hemminger | 1 | 0.23% | 1 | 5.88% |
| Ian Morris | 1 | 0.23% | 1 | 5.88% |
| Total | 427 | 100.00% | 17 | 100.00% |
static struct key_vector *halve(struct trie *t,
struct key_vector *oldtnode)
{
struct key_vector *tn;
unsigned long i;
pr_debug("In halve\n");
tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
if (!tn)
goto notnode;
/* prepare oldtnode to be freed */
tnode_free_init(oldtnode);
/* Assemble all of the pointers in our cluster, in this case that
* represents all of the pointers out of our allocated nodes that
* point to existing tnodes and the links between our allocated
* nodes.
*/
for (i = child_length(oldtnode); i;) {
struct key_vector *node1 = get_child(oldtnode, --i);
struct key_vector *node0 = get_child(oldtnode, --i);
struct key_vector *inode;
/* At least one of the children is empty */
if (!node1 || !node0) {
put_child(tn, i / 2, node1 ? : node0);
continue;
}
/* Two nonempty children */
inode = tnode_new(node0->key, oldtnode->pos, 1);
if (!inode)
goto nomem;
tnode_free_append(tn, inode);
/* initialize pointers out of node */
put_child(inode, 1, node1);
put_child(inode, 0, node0);
NODE_INIT_PARENT(inode, tn);
/* link parent to node */
put_child(tn, i / 2, inode);
}
/* setup the parent pointers into and out of this node */
return replace(t, oldtnode, tn