On Tue, 02 Nov 2004 22:41:44 +0100
Pablo Neira <pablo@xxxxxxxxxxx> wrote:
> This patch introduces the netlink bucket struct, it joins three arrays
> into an array of netlink bucket.
>
> Signed-off-by: Pablo Neira Ayuso <pablo@xxxxxxxxxxx>
Here is the work Herbert and I were talking about. It kind
of makes your patch taken care of already :-)
Herbert, this is what I actually checked into my tree. If
you could cook up a 2.4.x version, that would be really great.
# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
# 2004/11/03 15:34:53-08:00 herbert@xxxxxxxxxxxxxxxxxxx
# [NETLINK]: Hash sockets by pid if not multicast.
#
# Collaborative work between David S. Miller and
# Herbert Xu.
#
# Signed-off-by: Herbert Xu <herbert@xxxxxxxxxxxxxxxxxxx>
# Signed-off-by: David S. Miller <davem@xxxxxxxxxxxxx>
#
# net/netlink/af_netlink.c
# 2004/11/03 15:33:45-08:00 herbert@xxxxxxxxxxxxxxxxxxx +374 -109
# [NETLINK]: Hash sockets by pid if not multicast.
#
diff -Nru a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
--- a/net/netlink/af_netlink.c 2004-11-03 15:35:38 -08:00
+++ b/net/netlink/af_netlink.c 2004-11-03 15:35:38 -08:00
@@ -44,6 +44,12 @@
#include <linux/smp_lock.h>
#include <linux/notifier.h>
#include <linux/security.h>
+#include <linux/jhash.h>
+#include <linux/jiffies.h>
+#include <linux/random.h>
+#include <linux/bitops.h>
+#include <linux/mm.h>
+#include <linux/types.h>
#include <net/sock.h>
#include <net/scm.h>
@@ -56,9 +62,9 @@
struct netlink_opt
{
u32 pid;
- unsigned groups;
+ unsigned int groups;
u32 dst_pid;
- unsigned dst_groups;
+ unsigned int dst_groups;
unsigned long state;
int (*handler)(int unit, struct sk_buff *skb);
wait_queue_head_t wait;
@@ -69,9 +75,28 @@
#define nlk_sk(__sk) ((struct netlink_opt *)(__sk)->sk_protinfo)
-static struct hlist_head nl_table[MAX_LINKS];
+struct nl_pid_hash {
+ struct hlist_head *table;
+ unsigned long rehash_time;
+
+ unsigned int mask;
+ unsigned int shift;
+
+ unsigned int entries;
+ unsigned int max_shift;
+
+ u32 rnd;
+};
+
+struct netlink_table {
+ struct nl_pid_hash hash;
+ struct hlist_head mc_list;
+};
+
+static struct netlink_table *nl_table;
+
static DECLARE_WAIT_QUEUE_HEAD(nl_table_wait);
-static unsigned nl_nonroot[MAX_LINKS];
+static unsigned int nl_nonroot[MAX_LINKS];
#ifdef NL_EMULATE_DEV
static struct socket *netlink_kernel[MAX_LINKS];
@@ -85,6 +110,11 @@
static struct notifier_block *netlink_chain;
+static struct hlist_head *nl_pid_hashfn(struct nl_pid_hash *hash, u32 pid)
+{
+ return &hash->table[jhash_1word(pid, hash->rnd) & hash->mask];
+}
+
static void netlink_sock_destruct(struct sock *sk)
{
skb_queue_purge(&sk->sk_receive_queue);
@@ -153,11 +183,14 @@
static __inline__ struct sock *netlink_lookup(int protocol, u32 pid)
{
+ struct nl_pid_hash *hash = &nl_table[protocol].hash;
+ struct hlist_head *head;
struct sock *sk;
struct hlist_node *node;
read_lock(&nl_table_lock);
- sk_for_each(sk, node, &nl_table[protocol]) {
+ head = nl_pid_hashfn(hash, pid);
+ sk_for_each(sk, node, head) {
if (nlk_sk(sk)->pid == pid) {
sock_hold(sk);
goto found;
@@ -169,27 +202,118 @@
return sk;
}
+static inline struct hlist_head *nl_pid_hash_alloc(size_t size)
+{
+ if (size <= PAGE_SIZE)
+ return kmalloc(size, GFP_ATOMIC);
+ else
+ return (struct hlist_head *)
+ __get_free_pages(GFP_ATOMIC, get_order(size));
+}
+
+static inline void nl_pid_hash_free(struct hlist_head *table, size_t size)
+{
+ if (size <= PAGE_SIZE)
+ kfree(table);
+ else
+ free_pages((unsigned long)table, get_order(size));
+}
+
+static int nl_pid_hash_rehash(struct nl_pid_hash *hash, int grow)
+{
+ unsigned int omask, mask, shift;
+ size_t osize, size;
+ struct hlist_head *otable, *table;
+ int i;
+
+ omask = mask = hash->mask;
+ osize = size = (mask + 1) * sizeof(*table);
+ shift = hash->shift;
+
+ if (grow) {
+ if (++shift > hash->max_shift)
+ return 0;
+ mask = mask * 2 + 1;
+ size *= 2;
+ }
+
+ table = nl_pid_hash_alloc(size);
+ if (!table)
+ return 0;
+
+ memset(table, 0, size);
+ otable = hash->table;
+ hash->table = table;
+ hash->mask = mask;
+ hash->shift = shift;
+ get_random_bytes(&hash->rnd, sizeof(hash->rnd));
+
+ for (i = 0; i <= omask; i++) {
+ struct sock *sk;
+ struct hlist_node *node, *tmp;
+
+ sk_for_each_safe(sk, node, tmp, &otable[i])
+ __sk_add_node(sk, nl_pid_hashfn(hash, nlk_sk(sk)->pid));
+ }
+
+ nl_pid_hash_free(otable, osize);
+ hash->rehash_time = jiffies + 10 * 60 * HZ;
+ return 1;
+}
+
+static inline int nl_pid_hash_dilute(struct nl_pid_hash *hash, int len)
+{
+ int avg = hash->entries >> hash->shift;
+
+ if (unlikely(avg > 1) && nl_pid_hash_rehash(hash, 1))
+ return 1;
+
+ if (unlikely(len > avg) && time_after(jiffies, hash->rehash_time)) {
+ nl_pid_hash_rehash(hash, 0);
+ return 1;
+ }
+
+ return 0;
+}
+
static struct proto_ops netlink_ops;
static int netlink_insert(struct sock *sk, u32 pid)
{
+ struct nl_pid_hash *hash = &nl_table[sk->sk_protocol].hash;
+ struct hlist_head *head;
int err = -EADDRINUSE;
struct sock *osk;
struct hlist_node *node;
+ int len;
netlink_table_grab();
- sk_for_each(osk, node, &nl_table[sk->sk_protocol]) {
+ head = nl_pid_hashfn(hash, pid);
+ len = 0;
+ sk_for_each(osk, node, head) {
if (nlk_sk(osk)->pid == pid)
break;
+ len++;
}
- if (!node) {
- err = -EBUSY;
- if (nlk_sk(sk)->pid == 0) {
- nlk_sk(sk)->pid = pid;
- sk_add_node(sk, &nl_table[sk->sk_protocol]);
- err = 0;
- }
- }
+ if (node)
+ goto err;
+
+ err = -EBUSY;
+ if (nlk_sk(sk)->pid)
+ goto err;
+
+ err = -ENOMEM;
+ if (BITS_PER_LONG > 32 && unlikely(hash->entries >= UINT_MAX))
+ goto err;
+
+ if (len && nl_pid_hash_dilute(hash, len))
+ head = nl_pid_hashfn(hash, pid);
+ hash->entries++;
+ nlk_sk(sk)->pid = pid;
+ sk_add_node(sk, head);
+ err = 0;
+
+err:
netlink_table_ungrab();
return err;
}
@@ -197,7 +321,10 @@
static void netlink_remove(struct sock *sk)
{
netlink_table_grab();
+ nl_table[sk->sk_protocol].hash.entries--;
sk_del_node_init(sk);
+ if (nlk_sk(sk)->groups)
+ __sk_del_bind_node(sk);
netlink_table_ungrab();
}
@@ -282,19 +409,25 @@
static int netlink_autobind(struct socket *sock)
{
struct sock *sk = sock->sk;
+ struct nl_pid_hash *hash = &nl_table[sk->sk_protocol].hash;
+ struct hlist_head *head;
struct sock *osk;
struct hlist_node *node;
s32 pid = current->pid;
int err;
+ static s32 rover = -4097;
retry:
+ cond_resched();
netlink_table_grab();
- sk_for_each(osk, node, &nl_table[sk->sk_protocol]) {
+ head = nl_pid_hashfn(hash, pid);
+ sk_for_each(osk, node, head) {
if (nlk_sk(osk)->pid == pid) {
/* Bind collision, search negative pid values. */
if (pid > 0)
- pid = -4096;
- pid--;
+ pid = rover;
+ else if (--pid > 0)
+ pid = -4097;
netlink_table_ungrab();
goto retry;
}
@@ -308,7 +441,7 @@
return 0;
}
-static inline int netlink_capable(struct socket *sock, unsigned flag)
+static inline int netlink_capable(struct socket *sock, unsigned int flag)
{
return (nl_nonroot[sock->sk->sk_protocol] & flag) ||
capable(CAP_NET_ADMIN);
@@ -331,21 +464,19 @@
if (nlk->pid) {
if (nladdr->nl_pid != nlk->pid)
return -EINVAL;
- nlk->groups = nladdr->nl_groups;
- return 0;
+ } else {
+ err = nladdr->nl_pid ?
+ netlink_insert(sk, nladdr->nl_pid) :
+ netlink_autobind(sock);
+ if (err)
+ return err;
}
- if (nladdr->nl_pid == 0) {
- err = netlink_autobind(sock);
- if (err == 0)
- nlk->groups = nladdr->nl_groups;
- return err;
- }
+ nlk->groups = nladdr->nl_groups;
+ if (nladdr->nl_groups)
+ sk_add_bind_node(sk, &nl_table[sk->sk_protocol].mc_list);
- err = netlink_insert(sk, nladdr->nl_pid);
- if (err == 0)
- nlk->groups = nladdr->nl_groups;
- return err;
+ return 0;
}
static int netlink_connect(struct socket *sock, struct sockaddr *addr,
@@ -590,16 +721,76 @@
return -1;
}
+struct netlink_broadcast_data {
+ struct sock *exclude_sk;
+ u32 pid;
+ u32 group;
+ int failure;
+ int congested;
+ int delivered;
+ int allocation;
+ struct sk_buff *skb, *skb2;
+};
+
+static inline int do_one_broadcast(struct sock *sk,
+ struct netlink_broadcast_data *p)
+{
+ struct netlink_opt *nlk = nlk_sk(sk);
+ int val;
+
+ if (p->exclude_sk == sk)
+ goto out;
+
+ if (nlk->pid == p->pid || !(nlk->groups & p->group))
+ goto out;
+
+ if (p->failure) {
+ netlink_overrun(sk);
+ goto out;
+ }
+
+ sock_hold(sk);
+ if (p->skb2 == NULL) {
+ if (atomic_read(&p->skb->users) != 1) {
+ p->skb2 = skb_clone(p->skb, p->allocation);
+ } else {
+ p->skb2 = p->skb;
+ atomic_inc(&p->skb->users);
+ }
+ }
+ if (p->skb2 == NULL) {
+ netlink_overrun(sk);
+ /* Clone failed. Notify ALL listeners. */
+ p->failure = 1;
+ } else if ((val = netlink_broadcast_deliver(sk, p->skb2)) < 0) {
+ netlink_overrun(sk);
+ } else {
+ p->congested |= val;
+ p->delivered = 1;
+ p->skb2 = NULL;
+ }
+ sock_put(sk);
+
+out:
+ return 0;
+}
+
int netlink_broadcast(struct sock *ssk, struct sk_buff *skb, u32 pid,
u32 group, int allocation)
{
- struct sock *sk;
+ struct netlink_broadcast_data info;
struct hlist_node *node;
- struct sk_buff *skb2 = NULL;
- int protocol = ssk->sk_protocol;
- int failure = 0, delivered = 0;
- int congested = 0;
- int val;
+ struct sock *sk;
+
+ info.exclude_sk = ssk;
+ info.pid = pid;
+ info.group = group;
+ info.failure = 0;
+ info.congested = 0;
+ info.delivered = 0;
+ info.allocation = allocation;
+ info.skb = skb;
+ info.skb2 = NULL;
netlink_trim(skb, allocation);
@@ -607,77 +798,65 @@
netlink_lock_table();
- sk_for_each(sk, node, &nl_table[protocol]) {
- struct netlink_opt *nlk = nlk_sk(sk);
-
- if (ssk == sk)
- continue;
-
- if (nlk->pid == pid || !(nlk->groups & group))
- continue;
-
- if (failure) {
- netlink_overrun(sk);
- continue;
- }
-
- sock_hold(sk);
- if (skb2 == NULL) {
- if (atomic_read(&skb->users) != 1) {
- skb2 = skb_clone(skb, allocation);
- } else {
- skb2 = skb;
- atomic_inc(&skb->users);
- }
- }
- if (skb2 == NULL) {
- netlink_overrun(sk);
- /* Clone failed. Notify ALL listeners. */
- failure = 1;
- } else if ((val = netlink_broadcast_deliver(sk, skb2)) < 0) {
- netlink_overrun(sk);
- } else {
- congested |= val;
- delivered = 1;
- skb2 = NULL;
- }
- sock_put(sk);
- }
+ sk_for_each_bound(sk, node, &nl_table[ssk->sk_protocol].mc_list)
+ do_one_broadcast(sk, &info);
netlink_unlock_table();
- if (skb2)
- kfree_skb(skb2);
+ if (info.skb2)
+ kfree_skb(info.skb2);
kfree_skb(skb);
- if (delivered) {
- if (congested && (allocation & __GFP_WAIT))
+ if (info.delivered) {
+ if (info.congested && (allocation & __GFP_WAIT))
yield();
return 0;
}
- if (failure)
+ if (info.failure)
return -ENOBUFS;
return -ESRCH;
}
+struct netlink_set_err_data {
+ struct sock *exclude_sk;
+ u32 pid;
+ u32 group;
+ int code;
+};
+
+static inline int do_one_set_err(struct sock *sk,
+ struct netlink_set_err_data *p)
+{
+ struct netlink_opt *nlk = nlk_sk(sk);
+
+ if (sk == p->exclude_sk)
+ goto out;
+
+ if (nlk->pid == p->pid || !(nlk->groups & p->group))
+ goto out;
+
+ sk->sk_err = p->code;
+ sk->sk_error_report(sk);
+out:
+ return 0;
+}
+
void netlink_set_err(struct sock *ssk, u32 pid, u32 group, int code)
{
- struct sock *sk;
+ struct netlink_set_err_data info;
struct hlist_node *node;
- int protocol = ssk->sk_protocol;
+ struct sock *sk;
+
+ info.exclude_sk = ssk;
+ info.pid = pid;
+ info.group = group;
+ info.code = code;
read_lock(&nl_table_lock);
- sk_for_each(sk, node, &nl_table[protocol]) {
- struct netlink_opt *nlk = nlk_sk(sk);
- if (ssk == sk)
- continue;
- if (nlk->pid == pid || !(nlk->groups & group))
- continue;
+ sk_for_each_bound(sk, node, &nl_table[ssk->sk_protocol].mc_list)
+ do_one_set_err(sk, &info);
- sk->sk_err = code;
- sk->sk_error_report(sk);
- }
read_unlock(&nl_table_lock);
}
@@ -853,6 +1032,9 @@
struct socket *sock;
struct sock *sk;
+ if (!nl_table)
+ return NULL;
+
if (unit<0 || unit>=MAX_LINKS)
return NULL;
@@ -875,9 +1057,9 @@
return sk;
}
-void netlink_set_nonroot(int protocol, unsigned flags)
+void netlink_set_nonroot(int protocol, unsigned int flags)
{
- if ((unsigned)protocol < MAX_LINKS)
+ if ((unsigned int)protocol < MAX_LINKS)
nl_nonroot[protocol] = flags;
}
@@ -1070,20 +1252,31 @@
#endif
#ifdef CONFIG_PROC_FS
+struct nl_seq_iter {
+ int link;
+ int hash_idx;
+};
+
static struct sock *netlink_seq_socket_idx(struct seq_file *seq, loff_t pos)
{
- long i;
+ struct nl_seq_iter *iter = seq->private;
+ int i, j;
struct sock *s;
struct hlist_node *node;
loff_t off = 0;
for (i=0; i<MAX_LINKS; i++) {
- sk_for_each(s, node, &nl_table[i]) {
- if (off == pos) {
- seq->private = (void *) i;
- return s;
+ struct nl_pid_hash *hash = &nl_table[i].hash;
+
+ for (j = 0; j <= hash->mask; j++) {
+ sk_for_each(s, node, &hash->table[j]) {
+ if (off == pos) {
+ iter->link = i;
+ iter->hash_idx = j;
+ return s;
+ }
+ ++off;
}
- ++off;
}
}
return NULL;
@@ -1098,6 +1291,8 @@
static void *netlink_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{
struct sock *s;
+ struct nl_seq_iter *iter;
+ int i, j;
++*pos;
@@ -1105,18 +1300,29 @@
return netlink_seq_socket_idx(seq, 0);
s = sk_next(v);
- if (!s) {
- long i = (long)seq->private;
+ if (s)
+ return s;
+
+ iter = seq->private;
+ i = iter->link;
+ j = iter->hash_idx + 1;
- while (++i < MAX_LINKS) {
- s = sk_head(&nl_table[i]);
+ do {
+ struct nl_pid_hash *hash = &nl_table[i].hash;
+
+ for (; j <= hash->mask; j++) {
+ s = sk_head(&hash->table[j]);
if (s) {
- seq->private = (void *) i;
- break;
+ iter->link = i;
+ iter->hash_idx = j;
+ return s;
}
}
- }
- return s;
+
+ j = 0;
+ } while (++i < MAX_LINKS);
+
+ return NULL;
}
static void netlink_seq_stop(struct seq_file *seq, void *v)
@@ -1160,7 +1366,24 @@
static int netlink_seq_open(struct inode *inode, struct file *file)
{
- return seq_open(file, &netlink_seq_ops);
+ struct seq_file *seq;
+ struct nl_seq_iter *iter;
+ int err;
+
+ iter = kmalloc(sizeof(*iter), GFP_KERNEL);
+ if (!iter)
+ return -ENOMEM;
+
+ err = seq_open(file, &netlink_seq_ops);
+ if (err) {
+ kfree(iter);
+ return err;
+ }
+
+ memset(iter, 0, sizeof(*iter));
+ seq = file->private_data;
+ seq->private = iter;
+ return 0;
}
static struct file_operations netlink_seq_fops = {
@@ -1168,7 +1391,7 @@
.open = netlink_seq_open,
.read = seq_read,
.llseek = seq_lseek,
- .release = seq_release,
+ .release = seq_release_private,
};
#endif
@@ -1210,14 +1433,54 @@
.owner = THIS_MODULE, /* for consistency 8) */
};
+extern void netlink_skb_parms_too_large(void);
+
static int __init netlink_proto_init(void)
{
struct sk_buff *dummy_skb;
+ int i;
+ unsigned long max;
+ unsigned int order;
+
+ if (sizeof(struct netlink_skb_parms) > sizeof(dummy_skb->cb))
+ netlink_skb_parms_too_large();
+
+ nl_table = kmalloc(sizeof(*nl_table) * MAX_LINKS, GFP_KERNEL);
+ if (!nl_table) {
+enomem:
+ printk(KERN_CRIT "netlink_init: Cannot allocate nl_table\n");
+ return -ENOMEM;
+ }
+
+ memset(nl_table, 0, sizeof(*nl_table) * MAX_LINKS);
- if (sizeof(struct netlink_skb_parms) > sizeof(dummy_skb->cb)) {
- printk(KERN_CRIT "netlink_init: panic\n");
- return -1;
+ if (num_physpages >= (128 * 1024))
+ max = num_physpages >> (21 - PAGE_SHIFT);
+ else
+ max = num_physpages >> (23 - PAGE_SHIFT);
+
+ order = get_bitmask_order(max) - 1 + PAGE_SHIFT;
+ max = (1UL << order) / sizeof(struct hlist_head);
+ order = get_bitmask_order(max > UINT_MAX ? UINT_MAX : max) - 1;
+
+ for (i = 0; i < MAX_LINKS; i++) {
+ struct nl_pid_hash *hash = &nl_table[i].hash;
+
+ hash->table = nl_pid_hash_alloc(1 * sizeof(*hash->table));
+ if (!hash->table) {
+ while (i-- > 0)
+ nl_pid_hash_free(nl_table[i].hash.table,
+ 1 * sizeof(*hash->table));
+ kfree(nl_table);
+ goto enomem;
+ }
+ memset(hash->table, 0, 1 * sizeof(*hash->table));
+ hash->max_shift = order;
+ hash->shift = 0;
+ hash->mask = 0;
+ hash->rehash_time = jiffies;
}
+
sock_register(&netlink_family_ops);
#ifdef CONFIG_PROC_FS
proc_net_fops_create("netlink", 0, &netlink_seq_fops);
@@ -1231,6 +1494,8 @@
{
sock_unregister(PF_NETLINK);
proc_net_remove("netlink");
+ kfree(nl_table);
+ nl_table = NULL;
}
core_initcall(netlink_proto_init);
|