[PATCH next] netfilter: nfqueue: batch verdict support

[PATCH next] netfilter: nfqueue: batch verdict support

[Florian Westphal]

Introduces a new nfnetlink type that applies a given
verdict to all queued packets with an id <= the id in the verdict
message.

If a mark is provided it is applied to all matched packets.

This reduces the number of verdicts that have to be sent.
Applications that make use of this feature need to maintain
a timeout to send a batchverdict periodically to avoid starvation.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/linux/netfilter/nfnetlink_queue.h |    1 +
 net/netfilter/nfnetlink_queue.c           |  132 ++++++++++++++++++++++++----
 2 files changed, 114 insertions(+), 19 deletions(-)

diff --git a/include/linux/netfilter/nfnetlink_queue.h b/include/linux/netfilter/nfnetlink_queue.h
index af94e00..24b32e6 100644
--- a/include/linux/netfilter/nfnetlink_queue.h
+++ b/include/linux/netfilter/nfnetlink_queue.h
@@ -8,6 +8,7 @@ enum nfqnl_msg_types {
 	NFQNL_MSG_PACKET,		/* packet from kernel to userspace */
 	NFQNL_MSG_VERDICT,		/* verdict from userspace to kernel */
 	NFQNL_MSG_CONFIG,		/* connect to a particular queue */
+	NFQNL_MSG_VERDICT_BATCH,	/* batchv from userspace to kernel */
 
 	NFQNL_MSG_MAX
 };
diff --git a/net/netfilter/nfnetlink_queue.c b/net/netfilter/nfnetlink_queue.c
index b83123f..4d4264e 100644
--- a/net/netfilter/nfnetlink_queue.c
+++ b/net/netfilter/nfnetlink_queue.c
@@ -171,6 +171,13 @@ __enqueue_entry(struct nfqnl_instance *queue, struct nf_queue_entry *entry)
        queue->queue_total++;
 }
 
+static void
+__dequeue_entry(struct nfqnl_instance *queue, struct nf_queue_entry *entry)
+{
+	list_del(&entry->list);
+	queue->queue_total--;
+}
+
 static struct nf_queue_entry *
 find_dequeue_entry(struct nfqnl_instance *queue, unsigned int id)
 {
@@ -185,10 +192,8 @@ find_dequeue_entry(struct nfqnl_instance *queue, unsigned int id)
 		}
 	}
 
-	if (entry) {
-		list_del(&entry->list);
-		queue->queue_total--;
-	}
+	if (entry)
+		__dequeue_entry(queue, entry);
 
 	spin_unlock_bh(&queue->lock);
 
@@ -607,6 +612,102 @@ static const struct nla_policy nfqa_verdict_policy[NFQA_MAX+1] = {
 	[NFQA_PAYLOAD]		= { .type = NLA_UNSPEC },
 };
 
+static const struct nla_policy nfqa_verdict_batch_policy[NFQA_MAX+1] = {
+	[NFQA_VERDICT_HDR]	= { .len = sizeof(struct nfqnl_msg_verdict_hdr) },
+	[NFQA_MARK]		= { .type = NLA_U32 },
+};
+
+static struct nfqnl_instance *verdict_instance_lookup(u16 queue_num, int nlpid)
+{
+	struct nfqnl_instance *queue;
+
+	queue = instance_lookup(queue_num);
+	if (!queue)
+		return ERR_PTR(-ENODEV);
+
+	if (queue->peer_pid != nlpid)
+		return ERR_PTR(-EPERM);
+
+	return queue;
+}
+
+static struct nfqnl_msg_verdict_hdr*
+verdicthdr_get(const struct nlattr * const nfqa[])
+{
+	struct nfqnl_msg_verdict_hdr *vhdr;
+	unsigned int verdict;
+
+	if (!nfqa[NFQA_VERDICT_HDR])
+		return NULL;
+
+	vhdr = nla_data(nfqa[NFQA_VERDICT_HDR]);
+	verdict = ntohl(vhdr->verdict);
+	if ((verdict & NF_VERDICT_MASK) > NF_MAX_VERDICT)
+		return NULL;
+	return vhdr;
+}
+
+static int nfq_id_after(unsigned int id, unsigned int max)
+{
+	return (int)(id - max) > 0;
+}
+
+static int
+nfqnl_recv_verdict_batch(struct sock *ctnl, struct sk_buff *skb,
+		   const struct nlmsghdr *nlh,
+		   const struct nlattr * const nfqa[])
+{
+	struct nfgenmsg *nfmsg = NLMSG_DATA(nlh);
+	struct nf_queue_entry *entry, *tmp;
+	unsigned int verdict, maxid;
+	struct nfqnl_msg_verdict_hdr *vhdr;
+	struct nfqnl_instance *queue;
+	int err;
+	LIST_HEAD(batch_list);
+	u16 queue_num = ntohs(nfmsg->res_id);
+
+	rcu_read_lock();
+	queue = verdict_instance_lookup(queue_num, NETLINK_CB(skb).pid);
+	if (IS_ERR(queue)) {
+		err = PTR_ERR(queue);
+		goto err_out_unlock;
+	}
+
+	vhdr = verdicthdr_get(nfqa);
+	if (!vhdr) {
+		err = -EINVAL;
+		goto err_out_unlock;
+	}
+	verdict = ntohl(vhdr->verdict);
+	maxid = ntohl(vhdr->id);
+
+	spin_lock_bh(&queue->lock);
+
+	list_for_each_entry_safe(entry, tmp, &queue->queue_list, list) {
+		if (nfq_id_after(entry->id, maxid))
+			break;
+		__dequeue_entry(queue, entry);
+		list_add_tail(&entry->list, &batch_list);
+	}
+
+	spin_unlock_bh(&queue->lock);
+	rcu_read_unlock();
+
+	if (list_empty(&batch_list))
+		return -ENOENT;
+
+	list_for_each_entry_safe(entry, tmp, &batch_list, list) {
+		if (nfqa[NFQA_MARK])
+			entry->skb->mark = ntohl(nla_get_be32(nfqa[NFQA_MARK]));
+		nf_reinject(entry, verdict);
+	}
+	return 0;
+
+ err_out_unlock:
+	rcu_read_unlock();
+	return err;
+}
+
 static int
 nfqnl_recv_verdict(struct sock *ctnl, struct sk_buff *skb,
 		   const struct nlmsghdr *nlh,
@@ -622,30 +723,20 @@ nfqnl_recv_verdict(struct sock *ctnl, struct sk_buff *skb,
 	int err;
 
 	rcu_read_lock();
-	queue = instance_lookup(queue_num);
-	if (!queue) {
-		err = -ENODEV;
+	queue = verdict_instance_lookup(queue_num, NETLINK_CB(skb).pid);
+	if (IS_ERR(queue)) {
+		err = PTR_ERR(queue);
 		goto err_out_unlock;
 	}
 
-	if (queue->peer_pid != NETLINK_CB(skb).pid) {
-		err = -EPERM;
-		goto err_out_unlock;
-	}
-
-	if (!nfqa[NFQA_VERDICT_HDR]) {
+	vhdr = verdicthdr_get(nfqa);
+	if (!vhdr) {
 		err = -EINVAL;
 		goto err_out_unlock;
 	}
 
-	vhdr = nla_data(nfqa[NFQA_VERDICT_HDR]);
 	verdict = ntohl(vhdr->verdict);
 
-	if ((verdict & NF_VERDICT_MASK) > NF_MAX_VERDICT) {
-		err = -EINVAL;
-		goto err_out_unlock;
-	}
-
 	entry = find_dequeue_entry(queue, ntohl(vhdr->id));
 	if (entry == NULL) {
 		err = -ENOENT;
@@ -788,6 +879,9 @@ static const struct nfnl_callback nfqnl_cb[NFQNL_MSG_MAX] = {
 	[NFQNL_MSG_CONFIG]	= { .call = nfqnl_recv_config,
 				    .attr_count = NFQA_CFG_MAX,
 				    .policy = nfqa_cfg_policy },
+	[NFQNL_MSG_VERDICT_BATCH]={ .call = nfqnl_recv_verdict_batch,
+				    .attr_count = NFQA_MAX,
+				    .policy = nfqa_verdict_batch_policy },
 };
 
 static const struct nfnetlink_subsystem nfqnl_subsys = {
-- 
1.7.3.4

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Eric Dumazet]

Le vendredi 10 juin 2011 à 00:14 +0200, Florian Westphal a écrit :
> Introduces a new nfnetlink type that applies a given
> verdict to all queued packets with an id <= the id in the verdict
> message.
> 
> If a mark is provided it is applied to all matched packets.
> 
> This reduces the number of verdicts that have to be sent.
> Applications that make use of this feature need to maintain
> a timeout to send a batchverdict periodically to avoid starvation.
> 
> Signed-off-by: Florian Westphal <fw@strlen.de>

The real question hidden here is : "Should packet ids be monotonic" in
current implementation and all future ones ?

Before we accept this patch, we should make sure packets id are
monotonic, and I am afraid its not the case right now.

I suggest following patch then.

[PATCH] netfilter: nfqueue: assert monotonic packet ids

Packet identifier is currently setup in nfqnl_build_packet_message(),
using one atomic_inc_return().

Problem is that since several cpus might concurrently call
nfqnl_enqueue_packet() for the same queue, we can deliver packets to
consumer in non monotonic way (packet N+1 being delivered after packet
N)

This patch moves the packet id setup from nfqnl_build_packet_message()
to nfqnl_enqueue_packet() to guarantee correct delivery order.

This also removes one atomic operation.

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
CC: Florian Westphal <fw@strlen.de>
CC: Pablo Neira Ayuso <pablo@netfilter.org>
CC: Eric Leblond <eric@regit.org>
---
 net/netfilter/nfnetlink_queue.c |   26 +++++++++++++++-----------
 1 file changed, 15 insertions(+), 11 deletions(-)

diff --git a/net/netfilter/nfnetlink_queue.c b/net/netfilter/nfnetlink_queue.c
index fdd2faf..bccaf3b 100644
--- a/net/netfilter/nfnetlink_queue.c
+++ b/net/netfilter/nfnetlink_queue.c
@@ -58,7 +58,7 @@ struct nfqnl_instance {
  */
 	spinlock_t	lock;
 	unsigned int	queue_total;
-	atomic_t	id_sequence;		/* 'sequence' of pkt ids */
+	unsigned int	id_sequence;		/* 'sequence' of pkt ids */
 	struct list_head queue_list;		/* packets in queue */
 };
 
@@ -213,13 +213,15 @@ nfqnl_flush(struct nfqnl_instance *queue, nfqnl_cmpfn cmpfn, unsigned long data)
 
 static struct sk_buff *
 nfqnl_build_packet_message(struct nfqnl_instance *queue,
-			   struct nf_queue_entry *entry)
+			   struct nf_queue_entry *entry,
+			   __be32 **packet_id_ptr)
 {
 	sk_buff_data_t old_tail;
 	size_t size;
 	size_t data_len = 0;
 	struct sk_buff *skb;
-	struct nfqnl_msg_packet_hdr pmsg;
+	struct nlattr *nla;
+	struct nfqnl_msg_packet_hdr *pmsg;
 	struct nlmsghdr *nlh;
 	struct nfgenmsg *nfmsg;
 	struct sk_buff *entskb = entry->skb;
@@ -272,12 +274,11 @@ nfqnl_build_packet_message(struct nfqnl_instance *queue,
 	nfmsg->version = NFNETLINK_V0;
 	nfmsg->res_id = htons(queue->queue_num);
 
-	entry->id = atomic_inc_return(&queue->id_sequence);
-	pmsg.packet_id 		= htonl(entry->id);
-	pmsg.hw_protocol	= entskb->protocol;
-	pmsg.hook		= entry->hook;
-
-	NLA_PUT(skb, NFQA_PACKET_HDR, sizeof(pmsg), &pmsg);
+	nla = __nla_reserve(skb, NFQA_PACKET_HDR, sizeof(*pmsg));
+	pmsg = nla_data(nla);
+	pmsg->hw_protocol	= entskb->protocol;
+	pmsg->hook		= entry->hook;
+	*packet_id_ptr		= &pmsg->packet_id;
 
 	indev = entry->indev;
 	if (indev) {
@@ -389,6 +390,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 	struct sk_buff *nskb;
 	struct nfqnl_instance *queue;
 	int err = -ENOBUFS;
+	__be32 *packet_id_ptr;
 
 	/* rcu_read_lock()ed by nf_hook_slow() */
 	queue = instance_lookup(queuenum);
@@ -402,7 +404,7 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 		goto err_out;
 	}
 
-	nskb = nfqnl_build_packet_message(queue, entry);
+	nskb = nfqnl_build_packet_message(queue, entry, &packet_id_ptr);
 	if (nskb == NULL) {
 		err = -ENOMEM;
 		goto err_out;
@@ -421,6 +423,8 @@ nfqnl_enqueue_packet(struct nf_queue_entry *entry, unsigned int queuenum)
 				 queue->queue_total);
 		goto err_out_free_nskb;
 	}
+	entry->id = ++queue->id_sequence;
+	*packet_id_ptr = htonl(entry->id);
 
 	/* nfnetlink_unicast will either free the nskb or add it to a socket */
 	err = nfnetlink_unicast(nskb, &init_net, queue->peer_pid, MSG_DONTWAIT);
@@ -870,7 +874,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,
-			  atomic_read(&inst->id_sequence), 1);
+			  inst->id_sequence, 1);
 }
 
 static const struct seq_operations nfqnl_seq_ops = {

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Florian Westphal]

Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > Introduces a new nfnetlink type that applies a given
> > verdict to all queued packets with an id <= the id in the verdict
> > message.
> > 
> > If a mark is provided it is applied to all matched packets.
> > 
> > This reduces the number of verdicts that have to be sent.
> > Applications that make use of this feature need to maintain
> > a timeout to send a batchverdict periodically to avoid starvation.
> > 
> > Signed-off-by: Florian Westphal <fw@strlen.de>
> 
> The real question hidden here is : "Should packet ids be monotonic" in
> current implementation and all future ones ?
> 
> Before we accept this patch, we should make sure packets id are
> monotonic, and I am afraid its not the case right now.

You're right, good catch.

I was fooled by atomic_inc being monotonically increasing, but since
packet building is not protected by the queue spin lock
reordering can indeed happen.

> [PATCH] netfilter: nfqueue: assert monotonic packet ids
> 
> Packet identifier is currently setup in nfqnl_build_packet_message(),
> using one atomic_inc_return().
> 
> Problem is that since several cpus might concurrently call
> nfqnl_enqueue_packet() for the same queue, we can deliver packets to
> consumer in non monotonic way (packet N+1 being delivered after packet
> N)

I would actually consider your patch a bug fix...

Thanks a lot for spending time on this!

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Patrick McHardy]

On 10.06.2011 00:14, Florian Westphal wrote:
> Introduces a new nfnetlink type that applies a given
> verdict to all queued packets with an id <= the id in the verdict
> message.
> 
> If a mark is provided it is applied to all matched packets.
> 
> This reduces the number of verdicts that have to be sent.
> Applications that make use of this feature need to maintain
> a timeout to send a batchverdict periodically to avoid starvation.

Thanks Florian. Do you have any throughput numbers with this patch?

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Florian Westphal]

Patrick McHardy <kaber@trash.net> wrote:
> On 10.06.2011 00:14, Florian Westphal wrote:
> > Introduces a new nfnetlink type that applies a given
> > verdict to all queued packets with an id <= the id in the verdict
> > message.
> > 
> > If a mark is provided it is applied to all matched packets.
> > 
> > This reduces the number of verdicts that have to be sent.
> > Applications that make use of this feature need to maintain
> > a timeout to send a batchverdict periodically to avoid starvation.
> 
> Thanks Florian. Do you have any throughput numbers with this patch?

Sorry, not off the top of my head, but I'll post numbers
once I am back in the office.

(I should also re-run my tests with Erics patch applied anyway...)

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Florian Westphal]

Patrick McHardy <kaber@trash.net> wrote:
> On 10.06.2011 00:14, Florian Westphal wrote:
> > Introduces a new nfnetlink type that applies a given
> > verdict to all queued packets with an id <= the id in the verdict
> > message.
> > 
> > If a mark is provided it is applied to all matched packets.
> > 
> > This reduces the number of verdicts that have to be sent.
> > Applications that make use of this feature need to maintain
> > a timeout to send a batchverdict periodically to avoid starvation.
> 
> Thanks Florian. Do you have any throughput numbers with this patch?

I re-ran some tests via lo, with Eric Dumazets
"netfilter: nfqueue: assert monotonic packet ids" patch applied on top of
a 2.6.39.2 kernel.

With "one accept per packet", the rest program needs
about two minutes to process 10000000 1024-Byte udp packets
sent via lo (queueing via
-t mangle -I INPUT -i lo -p udp -m udp --dport 6666 -j NFQUEUE --queue-num 0
; no other queueing rules active)

When sending batch accept verdicts for every tenth packet received,
run time was reduced to about 72 seconds.

I ran this several times and the results were similar.

Just to be sure I also tried with the Erics RCU patch applied but I
did not see any changes (not surprising because nfnl_mutex should
not cause contention in the "single queue" case).

If anyone else wants to do some tests or verify these results, i've
put the test program and a patch for libnetfilter_queue here:
http://strlen.de/nfqueue/

Some earlier tests (which i cannot reproduce at the moment because the
setup no longer exists) showed throughput increases from ~800 mbit
to about 1050 mbit, also using UDP frames (but via 10G Ethernet instead
of lo; this was with a 2.6.32.y based kernel).

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Patrick McHardy]

Am 07.07.2011 15:45, schrieb Florian Westphal:
> Patrick McHardy <kaber@trash.net> wrote:
>> On 10.06.2011 00:14, Florian Westphal wrote:
>>> Introduces a new nfnetlink type that applies a given
>>> verdict to all queued packets with an id <= the id in the verdict
>>> message.
>>>
>>> If a mark is provided it is applied to all matched packets.
>>>
>>> This reduces the number of verdicts that have to be sent.
>>> Applications that make use of this feature need to maintain
>>> a timeout to send a batchverdict periodically to avoid starvation.
>>
>> Thanks Florian. Do you have any throughput numbers with this patch?
> 
> I re-ran some tests via lo, with Eric Dumazets
> "netfilter: nfqueue: assert monotonic packet ids" patch applied on top of
> a 2.6.39.2 kernel.
> 
> With "one accept per packet", the rest program needs
> about two minutes to process 10000000 1024-Byte udp packets
> sent via lo (queueing via
> -t mangle -I INPUT -i lo -p udp -m udp --dport 6666 -j NFQUEUE --queue-num 0
> ; no other queueing rules active)
> 
> When sending batch accept verdicts for every tenth packet received,
> run time was reduced to about 72 seconds.
> 
> I ran this several times and the results were similar.

Thanks, that sounds pretty promising.

> Just to be sure I also tried with the Erics RCU patch applied but I
> did not see any changes (not surprising because nfnl_mutex should
> not cause contention in the "single queue" case).

I'll have another look at this patch later. As I wrote, I'm unsure
whether we want to do a full move to RCU because of ctnetlink, but
the optional RCU callbacks seem fine for now.

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Patrick McHardy]

On 07.07.2011 15:45, Florian Westphal wrote:
> Patrick McHardy <kaber@trash.net> wrote:
>> On 10.06.2011 00:14, Florian Westphal wrote:
>>> Introduces a new nfnetlink type that applies a given
>>> verdict to all queued packets with an id <= the id in the verdict
>>> message.
>>>
>>> If a mark is provided it is applied to all matched packets.
>>>
>>> This reduces the number of verdicts that have to be sent.
>>> Applications that make use of this feature need to maintain
>>> a timeout to send a batchverdict periodically to avoid starvation.
>>
>> Thanks Florian. Do you have any throughput numbers with this patch?
> 
> I re-ran some tests via lo, with Eric Dumazets
> "netfilter: nfqueue: assert monotonic packet ids" patch applied on top of
> a 2.6.39.2 kernel.
> 
> With "one accept per packet", the rest program needs
> about two minutes to process 10000000 1024-Byte udp packets
> sent via lo (queueing via
> -t mangle -I INPUT -i lo -p udp -m udp --dport 6666 -j NFQUEUE --queue-num 0
> ; no other queueing rules active)
> 
> When sending batch accept verdicts for every tenth packet received,
> run time was reduced to about 72 seconds.
> 
> I ran this several times and the results were similar.
> 
> Just to be sure I also tried with the Erics RCU patch applied but I
> did not see any changes (not surprising because nfnl_mutex should
> not cause contention in the "single queue" case).

Could you resend the patches rebased to Eric's nfnetlink_queue
changes please (I just pushed them out)? Thanks!

Re: [PATCH next] netfilter: nfqueue: batch verdict support

[Patrick McHardy]

On 03.07.2011 12:24, Eric Dumazet wrote:
> The real question hidden here is : "Should packet ids be monotonic" in
> current implementation and all future ones ?
> 
> Before we accept this patch, we should make sure packets id are
> monotonic, and I am afraid its not the case right now.
> 
> I suggest following patch then.
> 
> [PATCH] netfilter: nfqueue: assert monotonic packet ids
> 
> Packet identifier is currently setup in nfqnl_build_packet_message(),
> using one atomic_inc_return().
> 
> Problem is that since several cpus might concurrently call
> nfqnl_enqueue_packet() for the same queue, we can deliver packets to
> consumer in non monotonic way (packet N+1 being delivered after packet
> N)
> 
> This patch moves the packet id setup from nfqnl_build_packet_message()
> to nfqnl_enqueue_packet() to guarantee correct delivery order.
> 
> This also removes one atomic operation.
> 
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
> CC: Florian Westphal <fw@strlen.de>
> CC: Pablo Neira Ayuso <pablo@netfilter.org>
> CC: Eric Leblond <eric@regit.org>

Applied, thanks Eric.