netfilter: use idr instead of list to speed up packet lookup by id

use idr instead of list to speed up packet lookup by id.

The current implementations of nfnetlink_queue, ip_queue and ip6_queue are all use list to save the packets queued. If the verdicts aren't received in order, the lookup for the corresponding packets isn't efficient. As the ids is generated and maintained in kernel, we can use idr to speed up the lookup. The side effect of this patch is fixing the potential id overlap in nfnetlink_queue.

net/netfilter/nfnetlink_queue.c +1 -0

@@ -223,6 +211,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 	struct sk_buff *entskb = entry->skb;
 	struct net_device *indev;
 	struct net_device *outdev;
+	u32 id;
 
 	size =    NLMSG_SPACE(sizeof(struct nfgenmsg))
 		+ nla_total_size(sizeof(struct nfqnl_msg_packet_hdr))

@@ -262,7 +251,11 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 		break;

net/netfilter/nfnetlink_queue.c +10 -5

@@ -279,7 +272,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 	nfmsg->version = NFNETLINK_V0;
 	nfmsg->res_id = htons(queue->queue_num);
 
-	pmsg.packet_id 		= htonl(entry->id);
+	pmsg.packet_id 		= htonl(id);
 	pmsg.hw_protocol	= entskb->protocol;
 	pmsg.hook		= entry->hook;
 

@@ -375,6 +368,7 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 	}
 
 	nlh->nlmsg_len = skb->tail - old_tail;
+	*pid = id;
 	return skb;
 
 nlmsg_failure:

@@ -383,6 +377,9 @@ nla_put_failure:
 		kfree_skb(skb);
 	if (net_ratelimit())
 		printk(KERN_ERR "nf_queue: error creating packet message\n");
+	spin_lock_bh(&queue->lock);
+	idr_remove(&queue->idr, id);
+	spin_unlock_bh(&queue->lock);
 	return NULL;
 }
 

@@ -392,6 +389,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 	struct sk_buff *nskb;
 	struct nfqnl_instance *queue;
 	int err;
+	u32 id;
 
 	/* rcu_read_lock()ed by nf_hook_slow() */
 	queue = instance_lookup(queuenum);

@@ -401,7 +399,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 	if (queue->copy_mode == NFQNL_COPY_NONE)
 		goto err_out;
 
-	nskb = nfqnl_build_packet_message(queue, entry);
+	nskb = nfqnl_build_packet_message(queue, entry, &id);
 	if (nskb == NULL)
 		goto err_out;
 

@@ -426,7 +424,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 		goto err_out_unlock;
 	}
 
-	__enqueue_entry(queue, entry);
+	queue->queue_total++;
 
 	spin_unlock_bh(&queue->lock);
 	return 0;

@@ -434,6 +432,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 err_out_free_nskb:
 	kfree_skb(nskb);
 err_out_unlock:
+	idr_remove(&queue->idr, id);
 	spin_unlock_bh(&queue->lock);
 err_out:
 	return -1;

@@ -867,7 +866,7 @@ static int seq_show(struct seq_file *s, void *v)
 			  inst->peer_pid, inst->queue_total,
 			  inst->copy_mode, inst->copy_range,
 			  inst->queue_dropped, inst->queue_user_dropped,
-			  inst->id_sequence, 1);
+			  0, 1);
 }
 
 static const struct seq_operations nfqnl_seq_ops = {
 
--

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 8 lines · Changli Gao

use idr instead of list to speed up packet lookup by id.

The current implementations of nfnetlink_queue, ip_queue and ip6_queue are all use list to save the packets queued. If the verdicts aren't received in order, the lookup for the corresponding packets isn't efficient. As the ids is generated and maintained in kernel, we can use idr to speed up the lookup. The side effect of this patch is fixing the potential id overlap in nfnetlink_queue.

I'm interested in how this affects performance for the vast majority of users, which process messages in order. A simple hash table looks like a better choice here since we know the maximum number of entries in advance and also could have the user specify the desired hash size.

Quoted 9 lines · Patrick McHardy

Quoted 8 lines · Changli Gao

use idr instead of list to speed up packet lookup by id.

The current implementations of nfnetlink_queue, ip_queue and ip6_queue are all use list to save the packets queued. If the verdicts aren't received in order, the lookup for the corresponding packets isn't efficient. As the ids is generated and maintained in kernel, we can use idr to speed up the lookup. The side effect of this patch is fixing the potential id overlap in nfnetlink_queue.

Quoted 4 lines

I'm interested in how this affects performance for the vast majority of users, which process messages in order. A simple hash table looks like a better choice here since we know the maximum number of entries in advance and also could have the user specify the desired hash size.

Yes, a hash table would be good, but cost 8 bytes per slot.

Changli, did you tried RBL tree ? It might fit better both your needs and Patrick concerns...

Changli Gao wrote:

This doesn't compile:

net/netfilter/nfnetlink_queue.c:57: error: field 'idr' has incomplete type net/netfilter/nfnetlink_queue.c: In function 'instance_create':
net/netfilter/nfnetlink_queue.c:112: error: implicit declaration of function 'idr_init'
net/netfilter/nfnetlink_queue.c: In function 'instance_destroy_rcu':
net/netfilter/nfnetlink_queue.c:143: error: implicit declaration of function 'idr_destroy'
net/netfilter/nfnetlink_queue.c: In function 'find_dequeue_entry':
net/netfilter/nfnetlink_queue.c:170: error: implicit declaration of function 'idr_find'
net/netfilter/nfnetlink_queue.c:170: warning: assignment makes pointer from integer without a cast net/netfilter/nfnetlink_queue.c:172: error: implicit declaration of function 'idr_remove'
net/netfilter/nfnetlink_queue.c: In function 'nfqnl_flush':
net/netfilter/nfnetlink_queue.c:188: error: implicit declaration of

function 'idr_get_next'
net/netfilter/nfnetlink_queue.c:188: warning: assignment makes pointer from integer without a cast
net/netfilter/nfnetlink_queue.c: In function 'nfqnl_build_packet_message':
net/netfilter/nfnetlink_queue.c:253: error: implicit declaration of function 'idr_pre_get'
net/netfilter/nfnetlink_queue.c:254: error: implicit declaration of function 'idr_get_new'

I'm interested in how this affects performance for the vast majority of users, which process messages in order. A simple hash table looks like a better choice here since we know the maximum number of entries in advance and also could have the user specify the desired hash size.

You probably shouldn't be making the entry visible before the message is successfully built and sent.

Quoted 7 lines · Patrick McHardy

Changli Gao wrote:

I'm interested in how this affects performance for the vast majority of users, which process messages in order. A simple hash table looks like a better choice here since we know the maximum number of entries in advance and also could have the user specify the desired hash size.

If there aren't much packets queued, the packet ids will be around 0, and idr isn't much slower.

Quoted 2 lines

You probably shouldn't be making the entry visible before the message is successfully built and sent.

I wanted to keep the changeset small. But it seems wrong.

Yes, a hash table would be good, but cost 8 bytes per slot.

Changli, did you tried RBL tree ? It might fit better both your needs and Patrick concerns...

Processing packets in order doesn't necessarily mean that there aren't many packets queued. Its just that the current scheme is pretty much optimal for this case since the verdict will always refer to the first entry in the list.

Quoted 5 lines · Patrick McHardy

Processing packets in order doesn't necessarily mean that there aren't many packets queued. Its just that the current scheme is pretty much optimal for this case since the verdict will always refer to the first entry in the list.

How about keeping the old behavior by default, and replace the single list with idr when an unorder vedict is received.

You only know that during runtime, so this will get more complicated than necessary. Why not simply use a hash table with a size specified by userspace in the queue creation command?  The default behaviour would be a size of 1, which is equivalent to the currently used single list.

Quoted 6 lines · Patrick McHardy

You only know that during runtime, so this will get more complicated than necessary. Why not simply use a hash table with a size specified by userspace in the queue creation command? The default behaviour would be a size of 1, which is equivalent to the currently used single list.

We'd better not expose too many internal implementation details to userspace. If we do so, we can't change its implementation easily later. And letting user choose the size of hash table is much like the orginal epoll(2) design, there will be security consern, such as too much memory usage.