nfnetlink_queue: Use hash to speed up finding entries in nfqueue
Subsystems (2)
PATCH 1/1 nfnetlink_queue: Use hash to speed up finding entries in nfqueue
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.
----
nfnetlink_queue.c | 86 ++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 61 insertions(+), 25 deletions(-)
net/netfilter/nfnetlink_queue.c +61 -25
@@ -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;
Quoted 5 lines · 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.
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.
net/netfilter/nfnetlink_queue.c line 42
Quoted 11 lines
net/netfilter/nfnetlink_queue.c +3
-0@@ -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?
Quoted 11 lines · Patrick McHardy
Quoted 5 lines · 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.
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.
Quoted 7 lines
Quoted 7 lines
net/netfilter/nfnetlink_queue.c +0
-0@@ -37,6 +37,9 @@ #endif
Quoted 8 lines
net/netfilter/nfnetlink_queue.c line 42
Quoted 4 lines
net/netfilter/nfnetlink_queue.c +3
-0#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_BINDcmd message?
OK. It's better users can config the size.
Signature · 6 lines
Regards, Changli Gao([email protected]) -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 6 lines · Changli Gao
Quoted 5 lines · Patrick McHardy
Quoted 4 lines · 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.
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
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.
Quoted 13 lines · Patrick McHardy
Quoted 12 lines · Changli Gao
Quoted 10 lines · Patrick McHardy
Quoted 5 lines · 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.
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.
Quoted 7 lines
Quoted 1 line
It isn't a endless loop, as we limite the queue size.
It is if
queue_maxlenis 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.
Signature · 6 lines
Regards, Changli Gao([email protected]) -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html