[PATCH] nfnetlink_queue: Use hash to speed up finding entries in nfqueue

[PATCH] nfnetlink_queue: Use hash to speed up finding entries in nfqueue

[Changli Gao]

Use hash to speed up finding entries in nfqueue.

If user implements QoS in userland, packet verdict won't be received in order. At this moment, a hash table is faster than a double linked list when finding the corresponding entries in nfqueue.

This patch also fixes a potential bug, which will allows more than one entries with the same id are in the same nfqueue in the extreme.

Signed-off-by: Changli Gao <xiaosuo@gmail.com>
----
 nfnetlink_queue.c |   86 ++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 61 insertions(+), 25 deletions(-)

diff --git a/net/netfilter/nfnetlink_queue.c b/net/netfilter/nfnetlink_queue.c
index 7a9dec9..38c7af1 100644
--- a/net/netfilter/nfnetlink_queue.c
+++ b/net/netfilter/nfnetlink_queue.c
@@ -37,6 +37,9 @@
 #endif
 
 #define NFQNL_QMAX_DEFAULT 1024
+#define NFQNL_QHT_BITS 8
+#define NFQNL_QHT_SIZE (1 << NFQNL_QHT_BITS)
+#define NFQNL_QHT_MASK (NFQNL_QHT_SIZE - 1)
 
 struct nfqnl_instance {
 	struct hlist_node hlist;		/* global list of queues */
@@ -56,7 +59,7 @@ struct nfqnl_instance {
 
 	spinlock_t lock;
 
-	struct list_head queue_list;		/* packets in queue */
+	struct list_head *queue_list;
 };
 
 typedef int (*nfqnl_cmpfn)(struct nf_queue_entry *, unsigned long);
@@ -111,12 +114,19 @@ instance_create(u_int16_t queue_num, int pid)
 	inst->copy_range = 0xfffff;
 	inst->copy_mode = NFQNL_COPY_NONE;
 	spin_lock_init(&inst->lock);
-	INIT_LIST_HEAD(&inst->queue_list);
+	inst->queue_list = kcalloc(NFQNL_QHT_SIZE, sizeof(*inst->queue_list),
+				   GFP_ATOMIC);
+	if (inst->queue_list == NULL) {
+		err = -ENOMEM;
+		goto out_free;
+	}
+	for (h = 0; h < NFQNL_QHT_SIZE; h++)
+		INIT_LIST_HEAD(&inst->queue_list[h]);
 	INIT_RCU_HEAD(&inst->rcu);
 
 	if (!try_module_get(THIS_MODULE)) {
 		err = -EAGAIN;
-		goto out_free;
+		goto out_free_queue;
 	}
 
 	h = instance_hashfn(queue_num);
@@ -126,6 +136,8 @@ instance_create(u_int16_t queue_num, int pid)
 
 	return inst;
 
+out_free_queue:
+	kfree(inst->queue_list);
 out_free:
 	kfree(inst);
 out_unlock:
@@ -143,6 +155,7 @@ instance_destroy_rcu(struct rcu_head *head)
 						   rcu);
 
 	nfqnl_flush(inst, NULL, 0);
+	kfree(inst->queue_list);
 	kfree(inst);
 	module_put(THIS_MODULE);
 }
@@ -162,32 +175,51 @@ instance_destroy(struct nfqnl_instance *inst)
 	spin_unlock(&instances_lock);
 }
 
+static struct nf_queue_entry *
+__find_entry(struct nfqnl_instance *queue, unsigned int id)
+{
+	struct nf_queue_entry *i;
+
+	list_for_each_entry(i, &queue->queue_list[id & NFQNL_QHT_MASK], list) {
+		if (i->id == id)
+			return i;
+	}
+
+	return NULL;
+}
+
 static inline void
 __enqueue_entry(struct nfqnl_instance *queue, struct nf_queue_entry *entry)
 {
-       list_add_tail(&entry->list, &queue->queue_list);
-       queue->queue_total++;
+	do {
+		entry->id = queue->id_sequence++;
+	} while (__find_entry(queue, entry->id) != NULL);
+	list_add_tail(&entry->list,
+		      &queue->queue_list[entry->id & NFQNL_QHT_MASK]);
+	queue->queue_total++;
 }
 
 static struct nf_queue_entry *
-find_dequeue_entry(struct nfqnl_instance *queue, unsigned int id)
+__dequeue_entry(struct nfqnl_instance *queue, unsigned int id)
 {
-	struct nf_queue_entry *entry = NULL, *i;
-
-	spin_lock_bh(&queue->lock);
-
-	list_for_each_entry(i, &queue->queue_list, list) {
-		if (i->id == id) {
-			entry = i;
-			break;
-		}
-	}
+	struct nf_queue_entry *entry;
 
+	entry = __find_entry(queue, id);
 	if (entry) {
 		list_del(&entry->list);
 		queue->queue_total--;
 	}
 
+	return entry;
+}
+
+static struct nf_queue_entry *
+dequeue_entry(struct nfqnl_instance *queue, unsigned int id)
+{
+	struct nf_queue_entry *entry;
+
+	spin_lock_bh(&queue->lock);
+	entry = __dequeue_entry(queue, id);
 	spin_unlock_bh(&queue->lock);
 
 	return entry;
@@ -197,13 +229,17 @@ static void
 nfqnl_flush(struct nfqnl_instance *queue, nfqnl_cmpfn cmpfn, unsigned long data)
 {
 	struct nf_queue_entry *entry, *next;
+	int i;
 
 	spin_lock_bh(&queue->lock);
-	list_for_each_entry_safe(entry, next, &queue->queue_list, list) {
-		if (!cmpfn || cmpfn(entry, data)) {
-			list_del(&entry->list);
-			queue->queue_total--;
-			nf_reinject(entry, NF_DROP);
+	for (i = 0; i < NFQNL_QHT_SIZE; i++) {
+		list_for_each_entry_safe(entry, next, &queue->queue_list[i],
+					 list) {
+			if (!cmpfn || cmpfn(entry, data)) {
+				list_del(&entry->list);
+				queue->queue_total--;
+				nf_reinject(entry, NF_DROP);
+			}
 		}
 	}
 	spin_unlock_bh(&queue->lock);
@@ -262,7 +298,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 		break;
 	}
 
-	entry->id = queue->id_sequence++;
+	__enqueue_entry(queue, entry);
 
 	spin_unlock_bh(&queue->lock);
 
@@ -379,6 +415,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 
 nlmsg_failure:
 nla_put_failure:
+	dequeue_entry(queue, entry->id);
 	if (skb)
 		kfree_skb(skb);
 	if (net_ratelimit())
@@ -426,14 +463,13 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 		goto err_out_unlock;
 	}
 
-	__enqueue_entry(queue, entry);
-
 	spin_unlock_bh(&queue->lock);
 	return 0;
 
 err_out_free_nskb:
 	kfree_skb(nskb);
 err_out_unlock:
+	__dequeue_entry(queue, entry->id);
 	spin_unlock_bh(&queue->lock);
 err_out:
 	return -1;
@@ -645,7 +681,7 @@ nfqnl_recv_verdict(struct sock *ctnl, struct sk_buff *skb,
 		goto err_out_unlock;
 	}
 
-	entry = find_dequeue_entry(queue, ntohl(vhdr->id));
+	entry = dequeue_entry(queue, ntohl(vhdr->id));
 	if (entry == NULL) {
 		err = -ENOENT;
 		goto err_out_unlock;

Re: [PATCH] nfnetlink_queue: Use hash to speed up finding entries in nfqueue

[Patrick McHardy]

Changli Gao wrote:
> Use hash to speed up finding entries in nfqueue.
> 
> If user implements QoS in userland, packet verdict won't be received in order. At this moment, a hash table is faster than a double linked list when finding the corresponding entries in nfqueue.
> 
> This patch also fixes a potential bug, which will allows more than one entries with the same id are in the same nfqueue in the extreme.

Instead of a double ID in a purely hypothetical case, we'd now
get an endless loop. This part doesn't make much sense to me,
please remove it from the patch.

> diff --git a/net/netfilter/nfnetlink_queue.c b/net/netfilter/nfnetlink_queue.c
> index 7a9dec9..38c7af1 100644
> --- a/net/netfilter/nfnetlink_queue.c
> +++ b/net/netfilter/nfnetlink_queue.c
> @@ -37,6 +37,9 @@
>  #endif
>  
>  #define NFQNL_QMAX_DEFAULT 1024
> +#define NFQNL_QHT_BITS 8
> +#define NFQNL_QHT_SIZE (1 << NFQNL_QHT_BITS)
> +#define NFQNL_QHT_MASK (NFQNL_QHT_SIZE - 1)

Have you considered making the size configurable by passing a new
attribute in the NFQNL_CFG_CMD_BIND cmd message?

Re: [PATCH] nfnetlink_queue: Use hash to speed up finding entries in nfqueue

[Changli Gao]

On Fri, Nov 20, 2009 at 9:12 PM, Patrick McHardy <kaber@trash.net> wrote:
> Changli Gao wrote:
>> Use hash to speed up finding entries in nfqueue.
>>
>> If user implements QoS in userland, packet verdict won't be received in order. At this moment, a hash table is faster than a double linked list when finding the corresponding entries in nfqueue.
>>
>> This patch also fixes a potential bug, which will allows more than one entries with the same id are in the same nfqueue in the extreme.
>
> Instead of a double ID in a purely hypothetical case, we'd now
> get an endless loop. This part doesn't make much sense to me,
> please remove it from the patch.
>

It isn't a endless loop, as we limite the queue size.

>> diff --git a/net/netfilter/nfnetlink_queue.c b/net/netfilter/nfnetlink_queue.c
>> index 7a9dec9..38c7af1 100644
>> --- a/net/netfilter/nfnetlink_queue.c
>> +++ b/net/netfilter/nfnetlink_queue.c
>> @@ -37,6 +37,9 @@
>>  #endif
>>
>>  #define NFQNL_QMAX_DEFAULT 1024
>> +#define NFQNL_QHT_BITS 8
>> +#define NFQNL_QHT_SIZE (1 << NFQNL_QHT_BITS)
>> +#define NFQNL_QHT_MASK (NFQNL_QHT_SIZE - 1)
>
> Have you considered making the size configurable by passing a new
> attribute in the NFQNL_CFG_CMD_BIND cmd message?
>

OK. It's better users can config the size.

-- 
Regards，
Changli Gao(xiaosuo@gmail.com)
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] nfnetlink_queue: Use hash to speed up finding entries in nfqueue

[Patrick McHardy]

Changli Gao wrote:
> On Fri, Nov 20, 2009 at 9:12 PM, Patrick McHardy <kaber@trash.net> wrote:
>> Changli Gao wrote:
>>> Use hash to speed up finding entries in nfqueue.
>>>
>>> If user implements QoS in userland, packet verdict won't be received in order. At this moment, a hash table is faster than a double linked list when finding the corresponding entries in nfqueue.
>>>
>>> This patch also fixes a potential bug, which will allows more than one entries with the same id are in the same nfqueue in the extreme.
>> Instead of a double ID in a purely hypothetical case, we'd now
>> get an endless loop. This part doesn't make much sense to me,
>> please remove it from the patch.
>>
> 
> It isn't a endless loop, as we limite the queue size.

It is if queue_maxlen is set to the maximum. In any case this change
adds a new lookup for ID assignment and complicates the code for a
case which I still consider purely hypothetical. Additionally it is
not related to the hashing change and shouldn't be in the same patch.

Re: [PATCH] nfnetlink_queue: Use hash to speed up finding entries in nfqueue

[Changli Gao]

On Fri, Nov 20, 2009 at 9:56 PM, Patrick McHardy <kaber@trash.net> wrote:
> Changli Gao wrote:
>> On Fri, Nov 20, 2009 at 9:12 PM, Patrick McHardy <kaber@trash.net> wrote:
>>> Changli Gao wrote:
>>>> Use hash to speed up finding entries in nfqueue.
>>>>
>>>> If user implements QoS in userland, packet verdict won't be received in order. At this moment, a hash table is faster than a double linked list when finding the corresponding entries in nfqueue.
>>>>
>>>> This patch also fixes a potential bug, which will allows more than one entries with the same id are in the same nfqueue in the extreme.
>>> Instead of a double ID in a purely hypothetical case, we'd now
>>> get an endless loop. This part doesn't make much sense to me,
>>> please remove it from the patch.
>>>
>>
>> It isn't a endless loop, as we limite the queue size.
>
> It is if queue_maxlen is set to the maximum. In any case this change
> adds a new lookup for ID assignment and complicates the code for a
> case which I still consider purely hypothetical. Additionally it is
> not related to the hashing change and shouldn't be in the same patch.
>

Agree.

-- 
Regards，
Changli Gao(xiaosuo@gmail.com)
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html