nfnetlink_queue: use hash table to speed up entry finding.

use hash table to speed up entry finding.

If verdicts aren't received in order, list isn't efficient, and hash table is better.

Signed-off-by Changli Gao <[email protected]>

use hash table to speed up entry finding.

If verdicts aren't received in order, list isn't efficient, and hash table is better.

Quoted 4 lines · Changli Gao

use hash table to speed up entry finding.

If verdicts aren't received in order, list isn't efficient, and hash table is better.

Any what is the advantage of using flex arrays compared to a simple open code hash table?

Quoted 9 lines · Patrick McHardy

Quoted 4 lines · Changli Gao

use hash table to speed up entry finding.

If verdicts aren't received in order, list isn't efficient, and hash table is better.

Any what is the advantage of using flex arrays compared to a simple open code hash table?

From Documentation/flexible-arrays.txt

Large contiguous memory allocations can be unreliable in the Linux kernel. Kernel programmers will sometimes respond to this problem by allocating pages with vmalloc(). This solution not ideal, though. On 32-bit systems, memory from vmalloc() must be mapped into a relatively small address space; it's easy to run out. On SMP systems, the page table changes required by vmalloc() allocations can require expensive cross-processor interrupts on all CPUs. And, on all systems, use of space in the vmalloc() range increases pressure on the translation lookaside buffer (TLB), reducing the performance of the system.

User may create lots of queues, which have large hash tables. Flex array has better scalability than vmalloc() and kmalloc().

Le mardi 13 avril 2010 à 19:06 +0800, Changli Gao a écrit :

Thats theory. And for sparse arrays, that pro might be true. In your case, you prealloc all the array, using more ram than vmalloc...

In practice, x86 cpu can access vmalloced() data much faster then flex_array_managed data (take a look at all the expensive divides in flex code... :'( )

If vmalloc() happens to be slow, it can trivially be extended to use huge pages too. It will happen one day, when/if necessary.

Thats theory. And for sparse arrays, that pro might be true. In your case, you prealloc all the array, using more ram than vmalloc...

Quoted 4 lines · Eric Dumazet

Thats theory. And for sparse arrays, that pro might be true. In your case, you prealloc all the array, using more ram than vmalloc...

I prealloc all the arrays, because all of them are needed later in any way.

Quoted 6 lines · Changli Gao

Quoted 3 lines · Eric Dumazet

Thats theory. And for sparse arrays, that pro might be true. In your case, you prealloc all the array, using more ram than vmalloc...

I prealloc all the arrays, because all of them are needed later in any way.

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

Quoted 3 lines · Patrick McHardy

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

Quoted 3 lines

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

I need to allocate memory in atomic section, so vmalloc() can't be used. :(

does double check mechanism works?

Quoted 10 lines · Changli Gao

Quoted 6 lines · Patrick McHardy

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

I need to allocate memory in atomic section, so vmalloc() can't be used. :(

Quoted 2 lines

does double check mechanism works?

Allocate memory to setup a hash table in atomic section ?

Changli you can forget this right now, this is not serious.

We are not going to use this thing because your requirements are crazy.

Quoted 5 lines · Patrick McHardy

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

I need to allocate memory in atomic section, so vmalloc() can't be used. :(

Quoted 3 lines · Changli Gao

Quoted 2 lines · Patrick McHardy

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

Quoted 5 lines

Quoted 3 lines

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

I need to allocate memory in atomic section, so vmalloc() can't be used. :(

Why?

Quoted 7 lines · Patrick McHardy

Quoted 6 lines · Changli Gao

Quoted 5 lines · Patrick McHardy

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

Quoted 3 lines

Quoted 1 line

I need to allocate memory in atomic section, so vmalloc() can't be used. :(

Why?

instance_create() is called in rcu read-side critical section, and the whole body of this function is protected by the spinlock instances_lock. All these make memory allocation for queue instances should be atomic.

Quoted 11 lines · Changli Gao

Quoted 10 lines · Patrick McHardy

Quoted 7 lines · Changli Gao

Quoted 5 lines · Patrick McHardy

Quoted 2 lines

Yes, that is why vmalloc() is perfect for this case. No extra memory for management, but one pointer for each page of memory.

I agree, if it works for conntrack, it certainly also works for nfnetlink_queue.

I need to allocate memory in atomic section, so vmalloc() can't be used. :(

Why?

Quoted 4 lines

instance_create() is called in rcu read-side critical section, and the whole body of this function is protected by the spinlock instances_lock. All these make memory allocation for queue instances should be atomic.

That should be easily fixable. For the lookup we can add a reference counter so we don't need the rcu read side critical section.

For creation the lock actually looks unnecessary since all nfnetlink handlers run under nfnl_mutex, so we can't have concurrent creation and removal of queuing instances. Well, we need it for list insertion to avoid races with the seq file handlers, but we don't need it before that.

Quoted 3 lines · Patrick McHardy

That should be easily fixable. For the lookup we can add a reference counter so we don't need the rcu read side critical section.

Actually we don't even need that, since we're holding nfnl_mutex the instance can't go away.

Quoted 6 lines · Patrick McHardy

Quoted 2 lines · Patrick McHardy

That should be easily fixable. For the lookup we can add a reference counter so we don't need the rcu read side critical section.

Actually we don't even need that, since we're holding nfnl_mutex the instance can't go away.

I don't think so. a netlink queue instance maybe destroyed by nfqnl_rcv_nl_event(). And the function is called by netlink directly without nfnl_mutex.

No its not:

static void nfnetlink_rcv(struct sk_buff *skb)
{
       nfnl_lock();
       netlink_rcv_skb(skb, &nfnetlink_rcv_msg);
       nfnl_unlock();
}

static int
nfqnl_rcv_nl_event(struct notifier_block *this,
unsigned long event, void *ptr)

{
        struct netlink_notify *n = ptr;

        if (event == NETLINK_URELEASE && n->protocol == NETLINK_NETFILTER) {
                int i;

                /* destroy all instances for this pid */
                spin_lock(&instances_lock);
                for (i = 0; i < INSTANCE_BUCKETS; i++) {
                        struct hlist_node *tmp, *t2;
                        struct nfqnl_instance *inst;
                        struct hlist_head *head = &instance_table[i];

                        hlist_for_each_entry_safe(inst, tmp, t2, head, hlist) {
                                if ((n->net == &init_net) &&
                                    (n->pid == inst->peer_pid))
                                        __instance_destroy(inst);
                        }
                }
                spin_unlock(&instances_lock);
        }
        return NOTIFY_DONE;
}

static struct notifier_block nfqnl_rtnl_notifier = {
.notifier_call = nfqnl_rcv_nl_event,
};

Quoted 27 lines · Changli Gao

static int
nfqnl_rcv_nl_event(struct notifier_block *this, unsigned long event, void *ptr) {
        struct netlink_notify *n = ptr;

        if (event == NETLINK_URELEASE && n->protocol == NETLINK_NETFILTER) { int i;

                /* destroy all instances for this pid */ spin_lock(&instances_lock);
                for (i = 0; i < INSTANCE_BUCKETS; i++) { struct hlist_node *tmp, *t2; struct nfqnl_instance *inst; struct hlist_head *head = &instance_table[i];

                        hlist_for_each_entry_safe(inst, tmp, t2, head, hlist) { if ((n->net == &init_net) && (n->pid == inst->peer_pid)) __instance_destroy(inst); }
                }
                spin_unlock(&instances_lock);
        }
        return NOTIFY_DONE;
}

Quoted 4 lines

static struct notifier_block nfqnl_rtnl_notifier = { .notifier_call  = nfqnl_rcv_nl_event, };

Ah, right. So call nfnl_lock() or convert the spinlock to a mutex.

Quoted 32 lines · Patrick McHardy

Quoted 31 lines · Changli Gao

static int
nfqnl_rcv_nl_event(struct notifier_block *this,
unsigned long event, void *ptr)

{
        struct netlink_notify *n = ptr;

        if (event == NETLINK_URELEASE && n->protocol == NETLINK_NETFILTER) {
                int i;

                /* destroy all instances for this pid */
                spin_lock(&instances_lock);
                for (i = 0; i < INSTANCE_BUCKETS; i++) {
                        struct hlist_node *tmp, *t2;
                        struct nfqnl_instance *inst;
                        struct hlist_head *head = &instance_table[i];

                        hlist_for_each_entry_safe(inst, tmp, t2, head, hlist) {
                                if ((n->net == &init_net) &&
                                    (n->pid == inst->peer_pid))
                                        __instance_destroy(inst);
                        }
                }
                spin_unlock(&instances_lock);
        }
        return NOTIFY_DONE;
}

static struct notifier_block nfqnl_rtnl_notifier = {
.notifier_call = nfqnl_rcv_nl_event,
};

Quoted 3 lines

Ah, right. So call nfnl_lock() or convert the spinlock to a mutex.

We can't convert the spinlock to a mutex simply. The notifier chain is an atomic notifier chain.