cregit-Linux how code gets into the kernel

Release 4.8 net/ipv4/fib_trie.c

Directory: net/ipv4
/*
 *   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 <asm/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 <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 <net/switchdev.h>
#include <trace/events/fib.h>
#include "fib_lookup.h"


#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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck28100.00%1100.00%
Total28100.00%1100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck1957.58%457.14%
eric dumazeteric dumazet1339.39%228.57%
stephen hemmingerstephen hemminger13.03%114.29%
Total33100.00%7100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck1760.71%480.00%
stephen hemmingerstephen hemminger1139.29%120.00%
Total28100.00%5100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck52100.00%2100.00%
Total52100.00%2100.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

PersonTokensPropCommitsCommitProp
robert olssonrobert olsson33100.00%2100.00%
Total33100.00%2100.00%


static inline void alias_free_mem_rcu(struct fib_alias *fa) { call_rcu(&fa->rcu, __alias_free_mem); }

Contributors

PersonTokensPropCommitsCommitProp
robert olssonrobert olsson22100.00%2100.00%
Total22100.00%2100.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

PersonTokensPropCommitsCommitProp
robert olssonrobert olsson1941.30%228.57%
alexander duyckalexander duyck1532.61%228.57%
stephen hemmingerstephen hemminger1123.91%228.57%
tetsuo handatetsuo handa12.17%114.29%
Total46100.00%7100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck2647.27%228.57%
patrick mchardypatrick mchardy2240.00%114.29%
stephen hemmingerstephen hemminger47.27%114.29%
eric dumazeteric dumazet23.64%228.57%
robert olssonrobert olsson11.82%114.29%
Total55100.00%7100.00%


static inline void empty_child_inc(struct key_vector *n) { ++tn_info(n)->empty_children ? : ++tn_info(n)->full_children; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck29100.00%3100.00%
Total29100.00%3100.00%


static inline void empty_child_dec(struct key_vector *n) { tn_info(n)->empty_children-- ? : tn_info(n)->full_children--; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck29100.00%3100.00%
Total29100.00%3100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck5655.45%770.00%
robert olssonrobert olsson2827.72%110.00%
firo yangfiro yang1514.85%110.00%
stephen hemmingerstephen hemminger21.98%110.00%
Total101100.00%10100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck8354.61%675.00%
robert olssonrobert olsson4428.95%112.50%
firo yangfiro yang2516.45%112.50%
Total152100.00%8100.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

PersonTokensPropCommitsCommitProp
robert olssonrobert olsson2356.10%125.00%
alexander duyckalexander duyck1843.90%375.00%
Total41100.00%4100.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

PersonTokensPropCommitsCommitProp
robert olssonrobert olsson10064.10%212.50%
alexander duyckalexander duyck4931.41%1062.50%
eric dumazeteric dumazet31.92%212.50%
stephen hemmingerstephen hemminger21.28%16.25%
ian morrisian morris21.28%16.25%
Total156100.00%16100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck72100.00%4100.00%
Total72100.00%4100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck54100.00%4100.00%
Total54100.00%4100.00%


static inline void tnode_free_init(struct key_vector *tn) { tn_info(tn)->rcu.next = NULL; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck2086.96%480.00%
robert olssonrobert olsson313.04%120.00%
Total23100.00%5100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck52100.00%4100.00%
Total52100.00%4100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck83100.00%5100.00%
Total83100.00%5100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck10891.53%1090.91%
robert olssonrobert olsson108.47%19.09%
Total118100.00%11100.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

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck38790.63%952.94%
robert olssonrobert olsson307.03%423.53%
eric dumazeteric dumazet51.17%15.88%
jens laasjens laas30.70%15.88%
stephen hemmingerstephen hemminger10.23%15.88%
ian morrisian morris10.23%15.88%
Total427100.00%17100.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); nomem: /* all pointers should be clean so we are done */ tnode_free(tn); notnode: return NULL; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck14662.93%1275.00%
robert olssonrobert olsson8536.64%318.75%
stephen hemmingerstephen hemminger10.43%16.25%
Total232100.00%16100.00%


static struct key_vector *collapse(struct trie *t, struct key_vector *oldtnode) { struct key_vector *n, *tp; unsigned long i; /* scan the tnode looking for that one child that might still exist */ for (n = NULL, i = child_length(oldtnode); !n && i;) n = get_child(oldtnode, --i); /* compress one level */ tp = node_parent(oldtnode); put_child_root(tp, oldtnode->key, n); node_set_parent(n, tp); /* drop dead node */ node_free(oldtnode); return tp; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck95100.00%5100.00%
Total95100.00%5100.00%


static unsigned char update_suffix(struct key_vector *tn) { unsigned char slen = tn->pos; unsigned long stride, i; /* search though the list of children looking for nodes that might * have a suffix greater than the one we currently have. This is * why we start with a stride of 2 since a stride of 1 would * represent the nodes with suffix length equal to tn->pos */ for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) { struct key_vector *n = get_child(tn, i); if (!n || (n->slen <= slen)) continue; /* update stride and slen based on new value */ stride <<= (n->slen - slen); slen = n->slen; i &= ~(stride - 1); /* if slen covers all but the last bit we can stop here * there will be nothing longer than that since only node * 0 and 1 << (bits - 1) could have that as their suffix * length. */ if ((slen + 1) >= (tn->pos + tn->bits)) break; } tn->slen = slen; return slen; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck131100.00%4100.00%
Total131100.00%4100.00%

/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of * the Helsinki University of Technology and Matti Tikkanen of Nokia * Telecommunications, page 6: * "A node is doubled if the ratio of non-empty children to all * children in the *doubled* node is at least 'high'." * * 'high' in this instance is the variable 'inflate_threshold'. It * is expressed as a percentage, so we multiply it with * child_length() and instead of multiplying by 2 (since the * child array will be doubled by inflate()) and multiplying * the left-hand side by 100 (to handle the percentage thing) we * multiply the left-hand side by 50. * * The left-hand side may look a bit weird: child_length(tn) * - tn->empty_children is of course the number of non-null children * in the current node. tn->full_children is the number of "full" * children, that is non-null tnodes with a skip value of 0. * All of those will be doubled in the resulting inflated tnode, so * we just count them one extra time here. * * A clearer way to write this would be: * * to_be_doubled = tn->full_children; * not_to_be_doubled = child_length(tn) - tn->empty_children - * tn->full_children; * * new_child_length = child_length(tn) * 2; * * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / * new_child_length; * if (new_fill_factor >= inflate_threshold) * * ...and so on, tho it would mess up the while () loop. * * anyway, * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >= * inflate_threshold * * avoid a division: * 100 * (not_to_be_doubled + 2*to_be_doubled) >= * inflate_threshold * new_child_length * * expand not_to_be_doubled and to_be_doubled, and shorten: * 100 * (child_length(tn) - tn->empty_children + * tn->full_children) >= inflate_threshold * new_child_length * * expand new_child_length: * 100 * (child_length(tn) - tn->empty_children + * tn->full_children) >= * inflate_threshold * child_length(tn) * 2 * * shorten again: * 50 * (tn->full_children + child_length(tn) - * tn->empty_children) >= inflate_threshold * * child_length(tn) * */
static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) { unsigned long used = child_length(tn); unsigned long threshold = used; /* Keep root node larger */ threshold *= IS_TRIE(tp) ? inflate_threshold_root : inflate_threshold; used -= tn_info(tn)->empty_children; used += tn_info(tn)->full_children; /* if bits == KEYLENGTH then pos = 0, and will fail below */ return (used > 1) && tn->pos && ((50 * used) >= threshold); }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck84100.00%7100.00%
Total84100.00%7100.00%


static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) { unsigned long used = child_length(tn); unsigned long threshold = used; /* Keep root node larger */ threshold *= IS_TRIE(tp) ? halve_threshold_root : halve_threshold; used -= tn_info(tn)->empty_children; /* if bits == KEYLENGTH then used = 100% on wrap, and will fail below */ return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold); }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck79100.00%7100.00%
Total79100.00%7100.00%


static inline bool should_collapse(struct key_vector *tn) { unsigned long used = child_length(tn); used -= tn_info(tn)->empty_children; /* account for bits == KEYLENGTH case */ if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children) used -= KEY_MAX; /* One child or none, time to drop us from the trie */ return used < 2; }

Contributors

PersonTokensPropCommitsCommitProp
alexander duyckalexander duyck58100.00%4100.00%
Total58100.00%4100.00%

#define MAX_WORK 10
static struct key_vector *resize(struct trie