cregit-Linux how code gets into the kernel

Release 4.11 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 <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

PersonTokensPropCommitsCommitProp
Ido Schimmel3380.49%150.00%
Jiri Pirko819.51%150.00%
Total41100.00%2100.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

PersonTokensPropCommitsCommitProp
Ido Schimmel2967.44%150.00%
Jiri Pirko1432.56%150.00%
Total43100.00%2100.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

PersonTokensPropCommitsCommitProp
Ido Schimmel3061.22%266.67%
Jiri Pirko1938.78%133.33%
Total49100.00%3100.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

PersonTokensPropCommitsCommitProp
Jiri Pirko8290.11%150.00%
Ido Schimmel99.89%150.00%
Total91100.00%2100.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

PersonTokensPropCommitsCommitProp
Ido Schimmel6092.31%133.33%
Robert Olsson46.15%133.33%
Alexander Duyck11.54%133.33%
Total65100.00%3100.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

PersonTokensPropCommitsCommitProp
Ido Schimmel99100.00%1100.00%
Total99100.00%1100.00%

EXPORT_SYMBOL(register_fib_notifier);
int unregister_fib_notifier(struct notifier_block *nb) { return atomic_notifier_chain_unregister(&fib_chain, nb); }

Contributors

PersonTokensPropCommitsCommitProp
Ido Schimmel19100.00%1100.00%
Total19100.00%1100.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

PersonTokensPropCommitsCommitProp
Ido Schimmel43100.00%1100.00%
Total43100.00%1100.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

PersonTokensPropCommitsCommitProp
Ido Schimmel84100.00%1100.00%
Total84100.00%1100.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

PersonTokensPropCommitsCommitProp
Alexander 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 Duyck1957.58%457.14%
Eric Dumazet1339.39%228.57%
Stephen 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 Duyck1760.71%480.00%
Stephen 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 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 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 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 Olsson1941.30%228.57%
Alexander Duyck1532.61%228.57%
Stephen Hemminger1123.91%228.57%
Tetsuo 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 Duyck2647.27%228.57%
Patrick McHardy2240.00%114.29%
Stephen Hemminger47.27%114.29%
Eric Dumazet23.64%228.57%
Robert 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 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 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 Duyck5655.45%770.00%
Robert Olsson2827.72%110.00%
Firo Yang1514.85%110.00%
Stephen 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 Duyck8354.61%675.00%
Robert Olsson4428.95%112.50%
Firo 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 Olsson2356.10%125.00%
Alexander 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 Olsson10064.10%212.50%
Alexander Duyck4931.41%1062.50%
Eric Dumazet31.92%212.50%
Stephen Hemminger21.28%16.25%
Ian 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 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 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 Duyck2086.96%480.00%
Robert 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 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 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 Duyck10891.53%1090.91%
Robert 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 Duyck38790.63%952.94%
Robert Olsson307.03%423.53%
Eric Dumazet51.17%15.88%
Jens Låås30.70%15.88%
Stephen Hemminger10.23%15.88%
Ian 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