ip_queue.c inefficiencies?

ip_queue.c inefficiencies?

[Michael StJohns]

We've got an application that needs to process a lot of packets through the 
filters.  For a while we were getting a large number of "ip_queue: full at 
1024 entries" messages, but we managed to improve our processing to the 
point where we're staying ahead of the queue filling up.  In the process of 
doing the analysis I noticed that ipq_enqueue_packet sends the packet to 
user space prior to checking whether it can add it to the kernel level 
queue.  That means the user space application that's validating the packet 
would be spending cycles on a packet that it can't actually set a verdict on.

The patch below does two things:  It adds some /proc visible counters to 
count the packets dropped because they couldn't be queued to either kernel 
or user space; it adds a check early on in ipq_enqueue_packet to check and 
see if the kernel queue is full before trying to send the packet to user space.

A further optimization would move the check even earlier in 
ipq_enqueue_packet - right after the copy_mode check.

So the questions I have:  Does this change make sense?  Do I need to make 
this behavior configurable (since it changes the visibility in user 
space)?  For the latter one possibility is to add another two copy_mode 
values (IPQ_COPY_PACKET_FAST and IPQ_COPY_META_FAST) to control the 
behavior, or another is to do this via sysctl.


--- kern1/net/ipv4/netfilter/ip_queue.c	2005-01-13 22:37:02.000000000 -0800
+++ kern2/net/ipv4/netfilter/ip_queue.c	2005-01-16 11:04:31.000000000 -0800
@@ -10,6 +10,9 @@
   *             Zander).
   * 2000-08-01: Added Nick Williams' MAC support.
   * 2002-06-25: Code cleanup.
+ * 2005-01-10: Added /proc counter for dropped packets; fixed so
+ * packets aren't delivered to user space if they're going to be
+ * dropped.
   *
   */
  #include <linux/module.h>
@@ -55,6 +58,8 @@
  static int peer_pid;
  static unsigned int copy_range;
  static unsigned int queue_total;
+static unsigned int queue_dropped = 0;
+static unsigned int queue_user_dropped = 0;
  static struct sock *ipqnl;
  static LIST_HEAD(queue_list);
  static DECLARE_MUTEX(ipqnl_sem);
@@ -70,6 +75,7 @@
  __ipq_enqueue_entry(struct ipq_queue_entry *entry)
  {
         if (queue_total >= queue_maxlen) {
+	       queue_dropped++;
                 if (net_ratelimit())
                         printk(KERN_WARNING "ip_queue: full at %d entries, "
                                "dropping packet(s).\n", queue_total);
@@ -302,10 +308,22 @@
  	if (!peer_pid)
  		goto err_out_free_nskb;

+	if (queue_total >= queue_maxlen) {
+                queue_dropped++;
+		status = -ENOSPC;
+		if (net_ratelimit())
+		  printk (KERN_WARNING "ip_queue: full at %d entries, "
+			  "dropping packets(s). Dropped: %d\n",queue_total,
+			  queue_dropped);
+		goto err_out_free_nskb;
+	}
+
   	/* netlink_unicast will either free the nskb or attach it to a socket */
  	status = netlink_unicast(ipqnl, nskb, peer_pid, MSG_DONTWAIT);
-	if (status < 0)
+	if (status < 0) {
+	        queue_user_dropped++;
  		goto err_out_unlock;
+	}
  	
  	status = __ipq_enqueue_entry(entry);
  	if (status < 0)
@@ -615,12 +633,16 @@
  	              "Copy mode         : %hu\n"
  	              "Copy range        : %u\n"
  	              "Queue length      : %u\n"
-	              "Queue max. length : %u\n",
+	              "Queue max. length : %u\n"
+		      "Queue dropped     : %u\n"
+		      "Netlink dropped   : %u\n",
  	              peer_pid,
  	              copy_mode,
  	              copy_range,
  	              queue_total,
-	              queue_maxlen);
+	              queue_maxlen,
+		      queue_dropped,
+		      queue_user_dropped);

  	read_unlock_bh(&queue_lock);
  	

Re: ip_queue.c inefficiencies?

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 923 bytes --]

On Tue, Jan 18, 2005 at 07:18:32PM -0500, Michael StJohns wrote:
> The patch below does two things:  It adds some /proc visible counters to 
> count the packets dropped because they couldn't be queued to either kernel 
> or user space; it adds a check early on in ipq_enqueue_packet to check and 
> see if the kernel queue is full before trying to send the packet to user 
> space.

I think your patch is perfectly valid and looks fine.  

Patrick, if you don't see any problems, could you add it to your queue
of pending patches? Thanks!

-- 
- Harald Welte <laforge@netfilter.org>             http://www.netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: ip_queue.c inefficiencies?

[Patrick McHardy]

Harald Welte wrote:

>On Tue, Jan 18, 2005 at 07:18:32PM -0500, Michael StJohns wrote:
>
>>The patch below does two things:  It adds some /proc visible counters to 
>>count the packets dropped because they couldn't be queued to either kernel 
>>or user space; it adds a check early on in ipq_enqueue_packet to check and 
>>see if the kernel queue is full before trying to send the packet to user 
>>space.
>>
>
>I think your patch is perfectly valid and looks fine.  
>
>Patrick, if you don't see any problems, could you add it to your queue
>of pending patches? Thanks!
>
The patch doesn't apply to current -bk. Michael, can you please send a new
patch against the latest -bk kernel ?

Regards
Patrick

Re: ip_queue.c inefficiencies?

[Patrick McHardy]

[-- Attachment #1: Type: text/plain, Size: 690 bytes --]

Michael StJohns wrote:

> The original patch was against the ip_queue.c 1.10 version - which was 
> 2.4.21 Kernel.  (RHEL3).  Below is a version against the ip_queue.c 
> 1.20 version for the 2.6 kernel which seems to be the current version 
> in bk.

Thanks, I've added it to my 2.6.12 tree with one small change.
We hold queue_lock in your new check for queue_total >= queue_maxlen,
so the similar check in __ipq_enqueue_entry will never be true.
Therefore I removed it.

>
> Do you want a version of this against net/ipv6/netfilter/ip6_queue.c 
> as well?  It has the same inefficiency issue.

Yes, please.

Regards
Patrick

BTW: Please add a Signed-off-by: line when you send a patch.


[-- Attachment #2: x --]
[-- Type: text/plain, Size: 3293 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2005/02/03 19:33:24+01:00 mstjohns@mindspring.com 
#   [NETFILTER]: fix ip_queue inefficiencies
#   
#   Check if packet exceeds max queue length before netlink_unicast(),
#   add drop statistics.
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
# net/ipv4/netfilter/ip_queue.c
#   2005/02/03 19:33:13+01:00 mstjohns@mindspring.com +27 -15
#   [NETFILTER]: fix ip_queue inefficiencies
#   
#   Check if packet exceeds max queue length before netlink_unicast(),
#   add drop statistics.
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
diff -Nru a/net/ipv4/netfilter/ip_queue.c b/net/ipv4/netfilter/ip_queue.c
--- a/net/ipv4/netfilter/ip_queue.c	2005-02-03 19:34:12 +01:00
+++ b/net/ipv4/netfilter/ip_queue.c	2005-02-03 19:34:12 +01:00
@@ -14,6 +14,9 @@
  *             Zander).
  * 2000-08-01: Added Nick Williams' MAC support.
  * 2002-06-25: Code cleanup.
+ * 2005-01-10: Added /proc counter for dropped packets; fixed so
+ *             packets aren't delivered to user space if they're going 
+ *             to be dropped. 
  *
  */
 #include <linux/module.h>
@@ -59,6 +62,8 @@
 static int peer_pid;
 static unsigned int copy_range;
 static unsigned int queue_total;
+static unsigned int queue_dropped = 0;
+static unsigned int queue_user_dropped = 0;
 static struct sock *ipqnl;
 static LIST_HEAD(queue_list);
 static DECLARE_MUTEX(ipqnl_sem);
@@ -70,18 +75,11 @@
 	kfree(entry);
 }
 
-static inline int
+static inline void
 __ipq_enqueue_entry(struct ipq_queue_entry *entry)
 {
-       if (queue_total >= queue_maxlen) {
-               if (net_ratelimit()) 
-                       printk(KERN_WARNING "ip_queue: full at %d entries, "
-                              "dropping packet(s).\n", queue_total);
-               return -ENOSPC;
-       }
        list_add(&entry->list, &queue_list);
        queue_total++;
-       return 0;
 }
 
 /*
@@ -308,14 +306,24 @@
 	if (!peer_pid)
 		goto err_out_free_nskb; 
 
+	if (queue_total >= queue_maxlen) {
+                queue_dropped++;
+		status = -ENOSPC;
+		if (net_ratelimit())
+		          printk (KERN_WARNING "ip_queue: full at %d entries, "
+				  "dropping packets(s). Dropped: %d\n", queue_total,
+				  queue_dropped);
+		goto err_out_free_nskb;
+	}
+
  	/* netlink_unicast will either free the nskb or attach it to a socket */ 
 	status = netlink_unicast(ipqnl, nskb, peer_pid, MSG_DONTWAIT);
-	if (status < 0)
-		goto err_out_unlock;
-	
-	status = __ipq_enqueue_entry(entry);
-	if (status < 0)
+	if (status < 0) {
+	        queue_user_dropped++;
 		goto err_out_unlock;
+	}
+
+	__ipq_enqueue_entry(entry);
 
 	write_unlock_bh(&queue_lock);
 	return status;
@@ -637,12 +645,16 @@
 	              "Copy mode         : %hu\n"
 	              "Copy range        : %u\n"
 	              "Queue length      : %u\n"
-	              "Queue max. length : %u\n",
+	              "Queue max. length : %u\n"
+		      "Queue dropped     : %u\n"
+		      "Netlink dropped   : %u\n",
 	              peer_pid,
 	              copy_mode,
 	              copy_range,
 	              queue_total,
-	              queue_maxlen);
+	              queue_maxlen,
+		      queue_dropped,
+		      queue_user_dropped);
 
 	read_unlock_bh(&queue_lock);
 	

Re: ip_queue.c inefficiencies?

[Michael StJohns]

At 01:39 PM 2/3/2005, Patrick McHardy wrote:
>Michael StJohns wrote:
>
>>The original patch was against the ip_queue.c 1.10 version - which was 
>>2.4.21 Kernel.  (RHEL3).  Below is a version against the ip_queue.c 1.20 
>>version for the 2.6 kernel which seems to be the current version in bk.
>
>Thanks, I've added it to my 2.6.12 tree with one small change.
>We hold queue_lock in your new check for queue_total >= queue_maxlen,
>so the similar check in __ipq_enqueue_entry will never be true.
>Therefore I removed it.

Makes sense.  I had left it in because I wasn't sure if anyone else was 
calling it (__ipq_enqueue_entry).  Given the changes, it might actually 
make sense to eliminate __ipq_enqueue_entry by moving the last two lines of 
code into ipq_enqueue_entry



>>Do you want a version of this against net/ipv6/netfilter/ip6_queue.c as 
>>well?  It has the same inefficiency issue.
>
>Yes, please.

Will do.


>Regards
>Patrick
>
>BTW: Please add a Signed-off-by: line when you send a patch.

You're looking for "Signed-off-by: Mike StJohns <stjohns@nominum.com>" line 
in the patch file?  No problems - I'll provide one for the ip6_queue.c 
change.  I'm actually generating these by hand rather than through 
BitKeeper but will add appropriate text.

Thanks - Mike


># This is a BitKeeper generated diff -Nru style patch.
>#
># ChangeSet
>#   2005/02/03 19:33:24+01:00 mstjohns@mindspring.com
>#   [NETFILTER]: fix ip_queue inefficiencies
>#
>#   Check if packet exceeds max queue length before netlink_unicast(),
>#   add drop statistics.
>#
>#   Signed-off-by: Patrick McHardy <kaber@trash.net>
>#
># net/ipv4/netfilter/ip_queue.c
>#   2005/02/03 19:33:13+01:00 mstjohns@mindspring.com +27 -15
>#   [NETFILTER]: fix ip_queue inefficiencies
>#
>#   Check if packet exceeds max queue length before netlink_unicast(),
>#   add drop statistics.
>#
>#   Signed-off-by: Patrick McHardy <kaber@trash.net>
>#
>diff -Nru a/net/ipv4/netfilter/ip_queue.c b/net/ipv4/netfilter/ip_queue.c
>--- a/net/ipv4/netfilter/ip_queue.c     2005-02-03 19:34:12 +01:00
>+++ b/net/ipv4/netfilter/ip_queue.c     2005-02-03 19:34:12 +01:00
>@@ -14,6 +14,9 @@
>   *             Zander).
>   * 2000-08-01: Added Nick Williams' MAC support.
>   * 2002-06-25: Code cleanup.
>+ * 2005-01-10: Added /proc counter for dropped packets; fixed so
>+ *             packets aren't delivered to user space if they're going
>+ *             to be dropped.
>   *
>   */
>  #include <linux/module.h>
>@@ -59,6 +62,8 @@
>  static int peer_pid;
>  static unsigned int copy_range;
>  static unsigned int queue_total;
>+static unsigned int queue_dropped = 0;
>+static unsigned int queue_user_dropped = 0;
>  static struct sock *ipqnl;
>  static LIST_HEAD(queue_list);
>  static DECLARE_MUTEX(ipqnl_sem);
>@@ -70,18 +75,11 @@
>         kfree(entry);
>  }
>
>-static inline int
>+static inline void
>  __ipq_enqueue_entry(struct ipq_queue_entry *entry)
>  {
>-       if (queue_total >= queue_maxlen) {
>-               if (net_ratelimit())
>-                       printk(KERN_WARNING "ip_queue: full at %d entries, "
>-                              "dropping packet(s).\n", queue_total);
>-               return -ENOSPC;
>-       }
>         list_add(&entry->list, &queue_list);
>         queue_total++;
>-       return 0;
>  }
>
>  /*
>@@ -308,14 +306,24 @@
>         if (!peer_pid)
>                 goto err_out_free_nskb;
>
>+       if (queue_total >= queue_maxlen) {
>+                queue_dropped++;
>+               status = -ENOSPC;
>+               if (net_ratelimit())
>+                         printk (KERN_WARNING "ip_queue: full at %d 
>entries, "
>+                                 "dropping packets(s). Dropped: %d\n", 
>queue_total,
>+                                 queue_dropped);
>+               goto err_out_free_nskb;
>+       }
>+
>         /* netlink_unicast will either free the nskb or attach it to a 
> socket */
>         status = netlink_unicast(ipqnl, nskb, peer_pid, MSG_DONTWAIT);
>-       if (status < 0)
>-               goto err_out_unlock;
>-
>-       status = __ipq_enqueue_entry(entry);
>-       if (status < 0)
>+       if (status < 0) {
>+               queue_user_dropped++;
>                 goto err_out_unlock;
>+       }
>+
>+       __ipq_enqueue_entry(entry);
>
>         write_unlock_bh(&queue_lock);
>         return status;
>@@ -637,12 +645,16 @@
>                       "Copy mode         : %hu\n"
>                       "Copy range        : %u\n"
>                       "Queue length      : %u\n"
>-                     "Queue max. length : %u\n",
>+                     "Queue max. length : %u\n"
>+                     "Queue dropped     : %u\n"
>+                     "Netlink dropped   : %u\n",
>                       peer_pid,
>                       copy_mode,
>                       copy_range,
>                       queue_total,
>-                     queue_maxlen);
>+                     queue_maxlen,
>+                     queue_dropped,
>+                     queue_user_dropped);
>
>         read_unlock_bh(&queue_lock);
>

Re: ip_queue.c inefficiencies?

[Patrick McHardy]

Michael StJohns wrote:

> At 01:39 PM 2/3/2005, Patrick McHardy wrote:
>
>> We hold queue_lock in your new check for queue_total >= queue_maxlen,
>> so the similar check in __ipq_enqueue_entry will never be true.
>> Therefore I removed it.
>
>
> Makes sense.  I had left it in because I wasn't sure if anyone else 
> was calling it (__ipq_enqueue_entry).  Given the changes, it might 
> actually make sense to eliminate __ipq_enqueue_entry by moving the 
> last two lines of code into ipq_enqueue_entry
>

Yes, I just left it in as counterpart to __ipq_dequeue_entry,
although it would make the code clearer to remove both. Both
functions are inlined, so it doesn't really matter.

Regards
Patrick

Re: ip_queue.c inefficiencies?

[Michael StJohns]

[-- Attachment #1: Type: text/plain, Size: 328 bytes --]



At 01:39 PM 2/3/2005, Patrick McHardy wrote:


>>Do you want a version of this against net/ipv6/netfilter/ip6_queue.c as 
>>well?  It has the same inefficiency issue.
>
>Yes, please.


Attached. Includes the changes you made to the v4 patch.


>Regards
>Patrick
>
>BTW: Please add a Signed-off-by: line when you send a patch.

[-- Attachment #2: ip6queue.patch --]
[-- Type: application/octet-stream, Size: 2752 bytes --]

# Manually generated diff -Nur patch
# net/ipv6/netfilter/ip6_queue.c
#
# Signed-off-by: Mike StJohns <stjohns@nominum.com>
#
--- old/net/ipv6/netfilter/ip6_queue.c	2005-02-04 17:28:13.544688888 -0500
+++ new/net/ipv6/netfilter/ip6_queue.c	2005-02-04 17:38:45.780574424 -0500
@@ -20,6 +20,9 @@
  *             Few changes needed, mainly the hard_routing code and
  *             the netlink socket protocol (we're NETLINK_IP6_FW).
  * 2002-06-25: Code cleanup. [JM: ported cleanup over from ip_queue.c]
+ * 2005-02-04: Added /proc counter for dropped packets; fixed so
+ *             packets aren't delivered to user space if they're going
+ *             to be dropped.
  */
 #include <linux/module.h>
 #include <linux/skbuff.h>
@@ -64,6 +67,8 @@
 static int peer_pid;
 static unsigned int copy_range;
 static unsigned int queue_total;
+static unsigned int queue_dropped = 0;
+static unsigned int queue_user_dropped = 0;
 static struct sock *ipqnl;
 static LIST_HEAD(queue_list);
 static DECLARE_MUTEX(ipqnl_sem);
@@ -75,18 +80,11 @@
 	kfree(entry);
 }
 
-static inline int
+static inline void
 __ipq_enqueue_entry(struct ipq_queue_entry *entry)
 {
-       if (queue_total >= queue_maxlen) {
-               if (net_ratelimit()) 
-                       printk(KERN_WARNING "ip6_queue: full at %d entries, "
-                              "dropping packet(s).\n", queue_total);
-               return -ENOSPC;
-       }
        list_add(&entry->list, &queue_list);
        queue_total++;
-       return 0;
 }
 
 /*
@@ -312,10 +310,22 @@
 	if (!peer_pid)
 		goto err_out_free_nskb; 
 
+	if (queue_total >= queue_maxlen) {
+                queue_dropped++;
+		status = -ENOSPC;
+		if (net_ratelimit())
+		        printk (KERN_WARNING "ip6_queue: fill at %d entries, "
+				"dropping packet(s).  Dropped: %d\n", queue_total,
+				queue_dropped);
+		goto err_out_free_nskb;
+	}
+
  	/* netlink_unicast will either free the nskb or attach it to a socket */ 
 	status = netlink_unicast(ipqnl, nskb, peer_pid, MSG_DONTWAIT);
-	if (status < 0)
+	if (status < 0) {
+ 	        queue_user_dropped++;
 		goto err_out_unlock;
+	}
 	
 	status = __ipq_enqueue_entry(entry);
 	if (status < 0)
@@ -639,12 +649,16 @@
 	              "Copy mode         : %hu\n"
 	              "Copy range        : %u\n"
 	              "Queue length      : %u\n"
-	              "Queue max. length : %u\n",
+	              "Queue max. length : %u\n"
+		      "Queue dropped     : %u\n"
+		      "Netfilter dropped : %u\n",
 	              peer_pid,
 	              copy_mode,
 	              copy_range,
 	              queue_total,
-	              queue_maxlen);
+	              queue_maxlen,
+		      queue_dropped,
+		      queue_user_dropped);
 
 	read_unlock_bh(&queue_lock);
 	

[-- Attachment #3: Type: text/plain, Size: 0 bytes --]

Re: ip_queue.c inefficiencies?

[Patrick McHardy]

Michael StJohns wrote:

> Attached. Includes the changes you made to the v4 patch.


Great, thanks. I still need a Signed-off-by: line though.
Please have a look at Documentation/SubmittingPatches.

Regards
Patrick