/* Copyright (C) 2013 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*/
#ifndef _IP_SET_HASH_GEN_H
#define _IP_SET_HASH_GEN_H
#include <linux/rcupdate.h>
#include <linux/jhash.h>
#include <linux/types.h>
#include <linux/netfilter/ipset/ip_set_timeout.h>
#define __ipset_dereference_protected(p, c) rcu_dereference_protected(p, c)
#define ipset_dereference_protected(p, set) \
__ipset_dereference_protected(p, spin_is_locked(&(set)->lock))
#define rcu_dereference_bh_nfnl(p) rcu_dereference_bh_check(p, 1)
/* Hashing which uses arrays to resolve clashing. The hash table is resized
* (doubled) when searching becomes too long.
* Internally jhash is used with the assumption that the size of the
* stored data is a multiple of sizeof(u32).
*
* Readers and resizing
*
* Resizing can be triggered by userspace command only, and those
* are serialized by the nfnl mutex. During resizing the set is
* read-locked, so the only possible concurrent operations are
* the kernel side readers. Those must be protected by proper RCU locking.
*/
/* Number of elements to store in an initial array block */
#define AHASH_INIT_SIZE 4
/* Max number of elements to store in an array block */
#define AHASH_MAX_SIZE (3 * AHASH_INIT_SIZE)
/* Max muber of elements in the array block when tuned */
#define AHASH_MAX_TUNED 64
/* Max number of elements can be tuned */
#ifdef IP_SET_HASH_WITH_MULTI
#define AHASH_MAX(h) ((h)->ahash_max)
static inline u8
tune_ahash_max(u8 curr, u32 multi)
{
u32 n;
if (multi < curr)
return curr;
n = curr + AHASH_INIT_SIZE;
/* Currently, at listing one hash bucket must fit into a message.
* Therefore we have a hard limit here.
*/
return n > curr && n <= AHASH_MAX_TUNED ? n : curr;
}
#define TUNE_AHASH_MAX(h, multi) \
((h)->ahash_max = tune_ahash_max((h)->ahash_max, multi))
#else
#define AHASH_MAX(h) AHASH_MAX_SIZE
#define TUNE_AHASH_MAX(h, multi)
#endif
/* A hash bucket */
struct hbucket {
struct rcu_head rcu; /* for call_rcu_bh */
/* Which positions are used in the array */
DECLARE_BITMAP(used, AHASH_MAX_TUNED);
u8 size; /* size of the array */
u8 pos; /* position of the first free entry */
unsigned char value[0] /* the array of the values */
__aligned(__alignof__(u64));
};
/* The hash table: the table size stored here in order to make resizing easy */
struct htable {
atomic_t ref; /* References for resizing */
atomic_t uref; /* References for dumping */
u8 htable_bits; /* size of hash table == 2^htable_bits */
struct hbucket __rcu *bucket[0]; /* hashtable buckets */
};
#define hbucket(h, i) ((h)->bucket[i])
#define ext_size(n, dsize) \
(sizeof(struct hbucket) + (n) * (dsize))
#ifndef IPSET_NET_COUNT
#define IPSET_NET_COUNT 1
#endif
/* Book-keeping of the prefixes added to the set */
struct net_prefixes {
u32 nets[IPSET_NET_COUNT]; /* number of elements for this cidr */
u8 cidr[IPSET_NET_COUNT]; /* the cidr value */
};
/* Compute the hash table size */
static size_t
htable_size(u8 hbits)
{
size_t hsize;
/* We must fit both into u32 in jhash