/*
* 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.
*/
#include <asm/uaccess.h>
#include <asm/system.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/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/slab.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 "fib_lookup.h"
static struct kmem_cache *fn_hash_kmem __read_mostly;
static struct kmem_cache *fn_alias_kmem __read_mostly;
struct fib_node {
struct hlist_node fn_hash;
struct list_head fn_alias;
__be32 fn_key;
struct fib_alias fn_embedded_alias;
};
struct fn_zone {
struct fn_zone *fz_next; /* Next not empty zone */
struct hlist_head *fz_hash; /* Hash table pointer */
int fz_nent; /* Number of entries */
int fz_divisor; /* Hash divisor */
u32 fz_hashmask; /* (fz_divisor - 1) */
#define FZ_HASHMASK(fz) ((fz)->fz_hashmask)
int fz_order; /* Zone order */
__be32 fz_mask;
#define FZ_MASK(fz) ((fz)->fz_mask)
};
/* NOTE. On fast computers evaluation of fz_hashmask and fz_mask
* can be cheaper than memory lookup, so that FZ_* macros are used.
*/
struct fn_hash {
struct fn_zone *fn_zones[33];
struct fn_zone *fn_zone_list;
};
static inline u32 fn_hash(__be32 key, struct fn_zone *fz)
{
u32 h = ntohl(key)>>(32 - fz->fz_order);
h ^= (h>>20);
h ^= (h>>10);
h ^= (h>>5);
h &= FZ_HASHMASK(fz);
return h;
}
static inline __be32 fz_key(__be32 dst, struct fn_zone *fz)
{
return dst & FZ_MASK(fz);
}
static DEFINE_RWLOCK(fib_hash_lock);
static unsigned int fib_hash_genid;
#define FZ_MAX_DIVISOR ((PAGE_SIZE<<MAX_ORDER) / sizeof(struct hlist_head))
static struct hlist_head *fz_hash_alloc(int divisor)
{
unsigned long size = divisor * sizeof(struct hlist_head);
if (size <= PAGE_SIZE) {
return kzalloc(size, GFP_KERNEL);
} else {
return (struct hlist_head *)
__get_free_pages(GFP_KERNEL | __GFP_ZERO, get_order(size));
}
}
/* The fib hash lock must be held when this is called. */
static inline void fn_rebuild_zone(struct fn_zone *fz,
struct hlist_head *old_ht,
int old_divisor)
{
int i;
for (i = 0; i < old_divisor; i++) {
struct hlist_node *node, *n;
struct fib_node *f;
hlist_for_each_entry_safe(f, node, n, &old_ht[i], fn_hash) {
struct hlist_head *new_head;
hlist_del(&f->fn_hash);
new_head = &fz->fz_hash[fn_hash(f->fn_key, fz)];
hlist_add_head(&f->fn_hash, new_head);
}
}
}
static void fz_hash_free(struct hlist_head *hash, int divisor)
{
unsigned long size = divisor * sizeof(struct hlist_head);
if (size <= PAGE_SIZE)
kfree(hash);
else
free_pages((unsigned long)hash, get_order(size));
}
static void fn_rehash_zone(struct fn_zone *fz)
{
struct hlist_head *ht, *old_ht;
int old_divisor