net: reduce the lines of code
Subsystems (6)
PATCH 1/1 net: reduce the lines of code
Use macros to reduce the regularity lines.
--- net/core/filter.c | 96 +++----------------------------------------------- net/core/filter_def.h | 55 ++++++++++++++++++++++++++++ 2 files changed, 61 insertions(+), 90 deletions(-)
net/core/filter.c +6 -90
@@ -39,51 +39,9 @@#include <linux/filter.h> enum { -BPF_S_RET_K =0 , -BPF_S_RET_A , -BPF_S_ALU_ADD_K , -BPF_S_ALU_ADD_X , -BPF_S_ALU_SUB_K , -BPF_S_ALU_SUB_X , -BPF_S_ALU_MUL_K , -BPF_S_ALU_MUL_X , -BPF_S_ALU_DIV_X , -BPF_S_ALU_AND_K , -BPF_S_ALU_AND_X , -BPF_S_ALU_OR_K , -BPF_S_ALU_OR_X , -BPF_S_ALU_LSH_K , -BPF_S_ALU_LSH_X , -BPF_S_ALU_RSH_K , -BPF_S_ALU_RSH_X , -BPF_S_ALU_NEG , -BPF_S_LD_W_ABS , -BPF_S_LD_H_ABS , -BPF_S_LD_B_ABS , -BPF_S_LD_W_LEN , -BPF_S_LD_W_IND , -BPF_S_LD_H_IND , -BPF_S_LD_B_IND , -BPF_S_LD_IMM , -BPF_S_LDX_W_LEN , -BPF_S_LDX_B_MSH , -BPF_S_LDX_IMM , -BPF_S_MISC_TAX , -BPF_S_MISC_TXA , -BPF_S_ALU_DIV_K , -BPF_S_LD_MEM , -BPF_S_LDX_MEM , -BPF_S_ST , -BPF_S_STX , -BPF_S_JMP_JA , -BPF_S_JMP_JEQ_K , -BPF_S_JMP_JEQ_X , -BPF_S_JMP_JGE_K , -BPF_S_JMP_JGE_X , -BPF_S_JMP_JGT_K , -BPF_S_JMP_JGT_X , -BPF_S_JMP_JSET_K , -BPF_S_JMP_JSET_X , +#define BPF_DEFINE(user, kernel) kernel +#include "filter_def.h" +#undef BPF_DEFINE };/* No hurry in this branch */
@@ -436,51 +394,9 @@ int sk_chk_filter(struct sock_filter *filter, int flen)* Invalid instructions are initialized to 0. */ static const u8 codes[] = { - [BPF_ALU |BPF_ADD |BPF_K ] =BPF_S_ALU_ADD_K +1 , - [BPF_ALU |BPF_ADD |BPF_X ] =BPF_S_ALU_ADD_X +1 , - [BPF_ALU |BPF_SUB |BPF_K ] =BPF_S_ALU_SUB_K +1 , - [BPF_ALU |BPF_SUB |BPF_X ] =BPF_S_ALU_SUB_X +1 , - [BPF_ALU |BPF_MUL |BPF_K ] =BPF_S_ALU_MUL_K +1 , - [BPF_ALU |BPF_MUL |BPF_X ] =BPF_S_ALU_MUL_X +1 , - [BPF_ALU |BPF_DIV |BPF_X ] =BPF_S_ALU_DIV_X +1 , - [BPF_ALU |BPF_AND |BPF_K ] =BPF_S_ALU_AND_K +1 , - [BPF_ALU |BPF_AND |BPF_X ] =BPF_S_ALU_AND_X +1 , - [BPF_ALU |BPF_OR |BPF_K ] =BPF_S_ALU_OR_K +1 , - [BPF_ALU |BPF_OR |BPF_X ] =BPF_S_ALU_OR_X +1 , - [BPF_ALU |BPF_LSH |BPF_K ] =BPF_S_ALU_LSH_K +1 , - [BPF_ALU |BPF_LSH |BPF_X ] =BPF_S_ALU_LSH_X +1 , - [BPF_ALU |BPF_RSH |BPF_K ] =BPF_S_ALU_RSH_K +1 , - [BPF_ALU |BPF_RSH |BPF_X ] =BPF_S_ALU_RSH_X +1 , - [BPF_ALU |BPF_NEG ] =BPF_S_ALU_NEG +1 , - [BPF_LD |BPF_W |BPF_ABS ] =BPF_S_LD_W_ABS +1 , - [BPF_LD |BPF_H |BPF_ABS ] =BPF_S_LD_H_ABS +1 , - [BPF_LD |BPF_B |BPF_ABS ] =BPF_S_LD_B_ABS +1 , - [BPF_LD |BPF_W |BPF_LEN ] =BPF_S_LD_W_LEN +1 , - [BPF_LD |BPF_W |BPF_IND ] =BPF_S_LD_W_IND +1 , - [BPF_LD |BPF_H |BPF_IND ] =BPF_S_LD_H_IND +1 , - [BPF_LD |BPF_B |BPF_IND ] =BPF_S_LD_B_IND +1 , - [BPF_LD |BPF_IMM ] =BPF_S_LD_IMM +1 , - [BPF_LDX |BPF_W |BPF_LEN ] =BPF_S_LDX_W_LEN +1 , - [BPF_LDX |BPF_B |BPF_MSH ] =BPF_S_LDX_B_MSH +1 , - [BPF_LDX |BPF_IMM ] =BPF_S_LDX_IMM +1 , - [BPF_MISC |BPF_TAX ] =BPF_S_MISC_TAX +1 , - [BPF_MISC |BPF_TXA ] =BPF_S_MISC_TXA +1 , - [BPF_RET |BPF_K ] =BPF_S_RET_K +1 , - [BPF_RET |BPF_A ] =BPF_S_RET_A +1 , - [BPF_ALU |BPF_DIV |BPF_K ] =BPF_S_ALU_DIV_K +1 , - [BPF_LD |BPF_MEM ] =BPF_S_LD_MEM +1 , - [BPF_LDX |BPF_MEM ] =BPF_S_LDX_MEM +1 , - [BPF_ST ] =BPF_S_ST +1 , - [BPF_STX ] =BPF_S_STX +1 , - [BPF_JMP |BPF_JA ] =BPF_S_JMP_JA +1 , - [BPF_JMP |BPF_JEQ |BPF_K ] =BPF_S_JMP_JEQ_K +1 , - [BPF_JMP |BPF_JEQ |BPF_X ] =BPF_S_JMP_JEQ_X +1 , - [BPF_JMP |BPF_JGE |BPF_K ] =BPF_S_JMP_JGE_K +1 , - [BPF_JMP |BPF_JGE |BPF_X ] =BPF_S_JMP_JGE_X +1 , - [BPF_JMP |BPF_JGT |BPF_K ] =BPF_S_JMP_JGT_K +1 , - [BPF_JMP |BPF_JGT |BPF_X ] =BPF_S_JMP_JGT_X +1 , - [BPF_JMP |BPF_JSET |BPF_K ] =BPF_S_JMP_JSET_K +1 , - [BPF_JMP |BPF_JSET |BPF_X ] =BPF_S_JMP_JSET_X +1 , +#define BPF_DEFINE(user, kernel) [user] = kernel + 1 +#include "filter_def.h" +#undef BPF_DEFINE };int pc;
net/core/filter_def.h new file +55 -0
55 lines not on this page · raw message
Quoted 1 line · Changli Gao
Use macros to reduce the regularity lines.
This is complete awkward and does not fix anything - on the contrary it
makes it harder to understand the code and no advantage is achieved.
Hagen
Quoted 7 lines · Hagen Paul Pfeifer
Quoted 1 line · Changli Gao
Use macros to reduce the regularity lines.
This is complete awkward and does not fix anything - on the contrary it makes it harder to understand the code and no advantage is achieved.
Although it doesn't fix anything, It can simplify the adding of new BPF instructions, one place in filter_def.h instead of two in filter.c. I think if some code can be generated automatically, we'd better not write it manually, as the chance of error is less when the code is generated automatically.
Signature · 2 lines
Regards, Changli Gao([email protected])
Quoted 9 lines · Changli Gao
Quoted 7 lines · Hagen Paul Pfeifer
Quoted 1 line · Changli Gao
Use macros to reduce the regularity lines.
This is complete awkward and does not fix anything - on the contrary it makes it harder to understand the code and no advantage is achieved.
Quoted 6 lines
Although it doesn't fix anything, It can simplify the adding of new BPF instructions, one place in
filter_def.hinstead of two infilter.c. I think if some code can be generated automatically, we'd better not write it manually, as the chance of error is less when the code is generated automatically.
Idea is good, but the way you did it is not.
I have two patches in testing. I'll post them today.
One to remove all the "+ 1" we do in codes[] init
One at check time to replace the divide by a constant instruction (DIV_K) by a reciprocal one (a multiply at exec time)
PATCH 1/1 filter: cleanup codes[] init
Starting the translated instruction to 1 instead of 0 allows us to remove one descrement at check time and makes codes[] array init cleaner.
--- net/core/filter.c | 95 +++++++++++++++++++++----------------------- 1 file changed, 47 insertions(+), 48 deletions(-)
net/core/filter.c +47 -48
@@ -39,7 +39,7 @@#include <linux/filter.h> enum { -BPF_S_RET_K =0 , +BPF_S_RET_K =1 ,BPF_S_RET_A ,BPF_S_ALU_ADD_K ,BPF_S_ALU_ADD_X ,
@@ -436,51 +436,51 @@ int sk_chk_filter(struct sock_filter *filter, int flen)* Invalid instructions are initialized to 0. */ static const u8 codes[] = { - [BPF_ALU |BPF_ADD |BPF_K ] =BPF_S_ALU_ADD_K +1 , - [BPF_ALU |BPF_ADD |BPF_X ] =BPF_S_ALU_ADD_X +1 , - [BPF_ALU |BPF_SUB |BPF_K ] =BPF_S_ALU_SUB_K +1 , - [BPF_ALU |BPF_SUB |BPF_X ] =BPF_S_ALU_SUB_X +1 , - [BPF_ALU |BPF_MUL |BPF_K ] =BPF_S_ALU_MUL_K +1 , - [BPF_ALU |BPF_MUL |BPF_X ] =BPF_S_ALU_MUL_X +1 , - [BPF_ALU |BPF_DIV |BPF_X ] =BPF_S_ALU_DIV_X +1 , - [BPF_ALU |BPF_AND |BPF_K ] =BPF_S_ALU_AND_K +1 , - [BPF_ALU |BPF_AND |BPF_X ] =BPF_S_ALU_AND_X +1 , - [BPF_ALU |BPF_OR |BPF_K ] =BPF_S_ALU_OR_K +1 , - [BPF_ALU |BPF_OR |BPF_X ] =BPF_S_ALU_OR_X +1 , - [BPF_ALU |BPF_LSH |BPF_K ] =BPF_S_ALU_LSH_K +1 , - [BPF_ALU |BPF_LSH |BPF_X ] =BPF_S_ALU_LSH_X +1 , - [BPF_ALU |BPF_RSH |BPF_K ] =BPF_S_ALU_RSH_K +1 , - [BPF_ALU |BPF_RSH |BPF_X ] =BPF_S_ALU_RSH_X +1 , - [BPF_ALU |BPF_NEG ] =BPF_S_ALU_NEG +1 , - [BPF_LD |BPF_W |BPF_ABS ] =BPF_S_LD_W_ABS +1 , - [BPF_LD |BPF_H |BPF_ABS ] =BPF_S_LD_H_ABS +1 , - [BPF_LD |BPF_B |BPF_ABS ] =BPF_S_LD_B_ABS +1 , - [BPF_LD |BPF_W |BPF_LEN ] =BPF_S_LD_W_LEN +1 , - [BPF_LD |BPF_W |BPF_IND ] =BPF_S_LD_W_IND +1 , - [BPF_LD |BPF_H |BPF_IND ] =BPF_S_LD_H_IND +1 , - [BPF_LD |BPF_B |BPF_IND ] =BPF_S_LD_B_IND +1 , - [BPF_LD |BPF_IMM ] =BPF_S_LD_IMM +1 , - [BPF_LDX |BPF_W |BPF_LEN ] =BPF_S_LDX_W_LEN +1 , - [BPF_LDX |BPF_B |BPF_MSH ] =BPF_S_LDX_B_MSH +1 , - [BPF_LDX |BPF_IMM ] =BPF_S_LDX_IMM +1 , - [BPF_MISC |BPF_TAX ] =BPF_S_MISC_TAX +1 , - [BPF_MISC |BPF_TXA ] =BPF_S_MISC_TXA +1 , - [BPF_RET |BPF_K ] =BPF_S_RET_K +1 , - [BPF_RET |BPF_A ] =BPF_S_RET_A +1 , - [BPF_ALU |BPF_DIV |BPF_K ] =BPF_S_ALU_DIV_K +1 , - [BPF_LD |BPF_MEM ] =BPF_S_LD_MEM +1 , - [BPF_LDX |BPF_MEM ] =BPF_S_LDX_MEM +1 , - [BPF_ST ] =BPF_S_ST +1 , - [BPF_STX ] =BPF_S_STX +1 , - [BPF_JMP |BPF_JA ] =BPF_S_JMP_JA +1 , - [BPF_JMP |BPF_JEQ |BPF_K ] =BPF_S_JMP_JEQ_K +1 , - [BPF_JMP |BPF_JEQ |BPF_X ] =BPF_S_JMP_JEQ_X +1 , - [BPF_JMP |BPF_JGE |BPF_K ] =BPF_S_JMP_JGE_K +1 , - [BPF_JMP |BPF_JGE |BPF_X ] =BPF_S_JMP_JGE_X +1 , - [BPF_JMP |BPF_JGT |BPF_K ] =BPF_S_JMP_JGT_K +1 , - [BPF_JMP |BPF_JGT |BPF_X ] =BPF_S_JMP_JGT_X +1 , - [BPF_JMP |BPF_JSET |BPF_K ] =BPF_S_JMP_JSET_K +1 , - [BPF_JMP |BPF_JSET |BPF_X ] =BPF_S_JMP_JSET_X +1 , + [BPF_ALU |BPF_ADD |BPF_K ] =BPF_S_ALU_ADD_K , + [BPF_ALU |BPF_ADD |BPF_X ] =BPF_S_ALU_ADD_X , + [BPF_ALU |BPF_SUB |BPF_K ] =BPF_S_ALU_SUB_K , + [BPF_ALU |BPF_SUB |BPF_X ] =BPF_S_ALU_SUB_X , + [BPF_ALU |BPF_MUL |BPF_K ] =BPF_S_ALU_MUL_K , + [BPF_ALU |BPF_MUL |BPF_X ] =BPF_S_ALU_MUL_X , + [BPF_ALU |BPF_DIV |BPF_X ] =BPF_S_ALU_DIV_X , + [BPF_ALU |BPF_AND |BPF_K ] =BPF_S_ALU_AND_K , + [BPF_ALU |BPF_AND |BPF_X ] =BPF_S_ALU_AND_X , + [BPF_ALU |BPF_OR |BPF_K ] =BPF_S_ALU_OR_K , + [BPF_ALU |BPF_OR |BPF_X ] =BPF_S_ALU_OR_X , + [BPF_ALU |BPF_LSH |BPF_K ] =BPF_S_ALU_LSH_K , + [BPF_ALU |BPF_LSH |BPF_X ] =BPF_S_ALU_LSH_X , + [BPF_ALU |BPF_RSH |BPF_K ] =BPF_S_ALU_RSH_K , + [BPF_ALU |BPF_RSH |BPF_X ] =BPF_S_ALU_RSH_X , + [BPF_ALU |BPF_NEG ] =BPF_S_ALU_NEG , + [BPF_LD |BPF_W |BPF_ABS ] =BPF_S_LD_W_ABS , + [BPF_LD |BPF_H |BPF_ABS ] =BPF_S_LD_H_ABS , + [BPF_LD |BPF_B |BPF_ABS ] =BPF_S_LD_B_ABS , + [BPF_LD |BPF_W |BPF_LEN ] =BPF_S_LD_W_LEN , + [BPF_LD |BPF_W |BPF_IND ] =BPF_S_LD_W_IND , + [BPF_LD |BPF_H |BPF_IND ] =BPF_S_LD_H_IND , + [BPF_LD |BPF_B |BPF_IND ] =BPF_S_LD_B_IND , + [BPF_LD |BPF_IMM ] =BPF_S_LD_IMM , + [BPF_LDX |BPF_W |BPF_LEN ] =BPF_S_LDX_W_LEN , + [BPF_LDX |BPF_B |BPF_MSH ] =BPF_S_LDX_B_MSH , + [BPF_LDX |BPF_IMM ] =BPF_S_LDX_IMM , + [BPF_MISC |BPF_TAX ] =BPF_S_MISC_TAX , + [BPF_MISC |BPF_TXA ] =BPF_S_MISC_TXA , + [BPF_RET |BPF_K ] =BPF_S_RET_K , + [BPF_RET |BPF_A ] =BPF_S_RET_A , + [BPF_ALU |BPF_DIV |BPF_K ] =BPF_S_ALU_DIV_K , + [BPF_LD |BPF_MEM ] =BPF_S_LD_MEM , + [BPF_LDX |BPF_MEM ] =BPF_S_LDX_MEM , + [BPF_ST ] =BPF_S_ST , + [BPF_STX ] =BPF_S_STX , + [BPF_JMP |BPF_JA ] =BPF_S_JMP_JA , + [BPF_JMP |BPF_JEQ |BPF_K ] =BPF_S_JMP_JEQ_K , + [BPF_JMP |BPF_JEQ |BPF_X ] =BPF_S_JMP_JEQ_X , + [BPF_JMP |BPF_JGE |BPF_K ] =BPF_S_JMP_JGE_K , + [BPF_JMP |BPF_JGE |BPF_X ] =BPF_S_JMP_JGE_X , + [BPF_JMP |BPF_JGT |BPF_K ] =BPF_S_JMP_JGT_K , + [BPF_JMP |BPF_JGT |BPF_X ] =BPF_S_JMP_JGT_X , + [BPF_JMP |BPF_JSET |BPF_K ] =BPF_S_JMP_JSET_K , + [BPF_JMP |BPF_JSET |BPF_X ] =BPF_S_JMP_JSET_X , };int pc;
@@ -495,8 +495,7 @@ int sk_chk_filter(struct sock_filter *filter, int flen)if (code >=ARRAY_SIZE (codes))return -EINVAL ; code = codes[code]; -/* Undo the '+ 1' in codes[] after validation. */ -if (!code--) +if (!code)return -EINVAL ;/* Some instructions need special checks */ switch (code) {
PATCH 1/1 filter: use reciprocal divide
At compile time, we can replace the DIV_K instruction (divide by a constant value) by a reciprocal divide.
At exec time, the expensive divide is replaced by a multiply, a less expensive operation on most processors.
--- net/core/filter.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
net/core/filter.c +3 -1
@@ -37,6 +37,7 @@#include <asm/uaccess.h> #include <asm/unaligned.h> #include <linux/filter.h> +#include <linux/reciprocal_div.h> enum {BPF_S_RET_K =1 ,
@@ -202,7 +203,7 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, intA /=X ;continue ;case BPF_S_ALU_DIV_K : -A /= f_k; +A =reciprocal_divide (A , f_k);continue ;case BPF_S_ALU_AND_X :A &=X ;
@@ -503,6 +504,7 @@ int sk_chk_filter(struct sock_filter *filter, int flen)/* check for division by zero */ if (ftest->k ==0 )return -EINVAL ; + ftest->k =reciprocal_value (ftest->k);break ;case BPF_S_LD_MEM :case BPF_S_LDX_MEM :
Re: [PATCH net-next-2.6] filter: use reciprocal divide
Quoted 7 lines · Eric Dumazet
At compile time, we can replace the
DIV_Kinstruction (divide by a constant value) by a reciprocal divide.At exec time, the expensive divide is replaced by a multiply, a less expensive operation on most processors.
Signed-off-by Eric Dumazet <[email protected]>
Signature · 2 lines
Regards, Changli Gao([email protected])
Re: [PATCH net-next-2.6] filter: use reciprocal divide
From: Changli Gao <[email protected]>
Date: Fri, 19 Nov 2010 16:18:05 +0800
Quoted 10 lines · Eric Dumazet
Quoted 7 lines
At compile time, we can replace the
DIV_Kinstruction (divide by a constant value) by a reciprocal divide.At exec time, the expensive divide is replaced by a multiply, a less expensive operation on most processors.
Signed-off-by Eric Dumazet <[email protected]>Acked-by Changli Gao <[email protected]>
Applied.
Re: [PATCH net-next-2.6] filter: cleanup codes[] init
In reply to Eric DumazetQuoted 123 lines · Eric Dumazet
Starting the translated instruction to 1 instead of 0 allows us to remove one descrement at check time and makes codes[] array init cleaner.
Signed-off-by Eric Dumazet <[email protected]>---
net/core/filter.c | 95 +++++++++++++++++++++-----------------------1 file changed, 47 insertions(+), 48 deletions(-)net/core/filter.c +46
-46@@ -39,7 +39,7 @@ #include <linux/filter.h> enum { - BPF_S_RET_K = 0, + BPF_S_RET_K = 1, BPF_S_RET_A, BPF_S_ALU_ADD_K, BPF_S_ALU_ADD_X,@@ -436,51 +436,51 @@ int sk_chk_filter(struct sock_filter *filter, int flen)* Invalid instructions are initialized to 0. */ static const u8 codes[] = { - [BPF_ALU|BPF_ADD|BPF_K] = BPF_S_ALU_ADD_K + 1, - [BPF_ALU|BPF_ADD|BPF_X] = BPF_S_ALU_ADD_X + 1, - [BPF_ALU|BPF_SUB|BPF_K] = BPF_S_ALU_SUB_K + 1, - [BPF_ALU|BPF_SUB|BPF_X] = BPF_S_ALU_SUB_X + 1, - [BPF_ALU|BPF_MUL|BPF_K] = BPF_S_ALU_MUL_K + 1, - [BPF_ALU|BPF_MUL|BPF_X] = BPF_S_ALU_MUL_X + 1, - [BPF_ALU|BPF_DIV|BPF_X] = BPF_S_ALU_DIV_X + 1, - [BPF_ALU|BPF_AND|BPF_K] = BPF_S_ALU_AND_K + 1, - [BPF_ALU|BPF_AND|BPF_X] = BPF_S_ALU_AND_X + 1, - [BPF_ALU|BPF_OR|BPF_K] = BPF_S_ALU_OR_K + 1, - [BPF_ALU|BPF_OR|BPF_X] = BPF_S_ALU_OR_X + 1, - [BPF_ALU|BPF_LSH|BPF_K] = BPF_S_ALU_LSH_K + 1, - [BPF_ALU|BPF_LSH|BPF_X] = BPF_S_ALU_LSH_X + 1, - [BPF_ALU|BPF_RSH|BPF_K] = BPF_S_ALU_RSH_K + 1, - [BPF_ALU|BPF_RSH|BPF_X] = BPF_S_ALU_RSH_X + 1, - [BPF_ALU|BPF_NEG] = BPF_S_ALU_NEG + 1, - [BPF_LD|BPF_W|BPF_ABS] = BPF_S_LD_W_ABS + 1, - [BPF_LD|BPF_H|BPF_ABS] = BPF_S_LD_H_ABS + 1, - [BPF_LD|BPF_B|BPF_ABS] = BPF_S_LD_B_ABS + 1, - [BPF_LD|BPF_W|BPF_LEN] = BPF_S_LD_W_LEN + 1, - [BPF_LD|BPF_W|BPF_IND] = BPF_S_LD_W_IND + 1, - [BPF_LD|BPF_H|BPF_IND] = BPF_S_LD_H_IND + 1, - [BPF_LD|BPF_B|BPF_IND] = BPF_S_LD_B_IND + 1, - [BPF_LD|BPF_IMM] = BPF_S_LD_IMM + 1, - [BPF_LDX|BPF_W|BPF_LEN] = BPF_S_LDX_W_LEN + 1, - [BPF_LDX|BPF_B|BPF_MSH] = BPF_S_LDX_B_MSH + 1, - [BPF_LDX|BPF_IMM] = BPF_S_LDX_IMM + 1, - [BPF_MISC|BPF_TAX] = BPF_S_MISC_TAX + 1, - [BPF_MISC|BPF_TXA] = BPF_S_MISC_TXA + 1, - [BPF_RET|BPF_K] = BPF_S_RET_K + 1, - [BPF_RET|BPF_A] = BPF_S_RET_A + 1, - [BPF_ALU|BPF_DIV|BPF_K] = BPF_S_ALU_DIV_K + 1, - [BPF_LD|BPF_MEM] = BPF_S_LD_MEM + 1, - [BPF_LDX|BPF_MEM] = BPF_S_LDX_MEM + 1, - [BPF_ST] = BPF_S_ST + 1, - [BPF_STX] = BPF_S_STX + 1, - [BPF_JMP|BPF_JA] = BPF_S_JMP_JA + 1, - [BPF_JMP|BPF_JEQ|BPF_K] = BPF_S_JMP_JEQ_K + 1, - [BPF_JMP|BPF_JEQ|BPF_X] = BPF_S_JMP_JEQ_X + 1, - [BPF_JMP|BPF_JGE|BPF_K] = BPF_S_JMP_JGE_K + 1, - [BPF_JMP|BPF_JGE|BPF_X] = BPF_S_JMP_JGE_X + 1, - [BPF_JMP|BPF_JGT|BPF_K] = BPF_S_JMP_JGT_K + 1, - [BPF_JMP|BPF_JGT|BPF_X] = BPF_S_JMP_JGT_X + 1, - [BPF_JMP|BPF_JSET|BPF_K] = BPF_S_JMP_JSET_K + 1, - [BPF_JMP|BPF_JSET|BPF_X] = BPF_S_JMP_JSET_X + 1, + [BPF_ALU|BPF_ADD|BPF_K] = BPF_S_ALU_ADD_K, + [BPF_ALU|BPF_ADD|BPF_X] = BPF_S_ALU_ADD_X, + [BPF_ALU|BPF_SUB|BPF_K] = BPF_S_ALU_SUB_K, + [BPF_ALU|BPF_SUB|BPF_X] = BPF_S_ALU_SUB_X, + [BPF_ALU|BPF_MUL|BPF_K] = BPF_S_ALU_MUL_K, + [BPF_ALU|BPF_MUL|BPF_X] = BPF_S_ALU_MUL_X, + [BPF_ALU|BPF_DIV|BPF_X] = BPF_S_ALU_DIV_X, + [BPF_ALU|BPF_AND|BPF_K] = BPF_S_ALU_AND_K, + [BPF_ALU|BPF_AND|BPF_X] = BPF_S_ALU_AND_X, + [BPF_ALU|BPF_OR|BPF_K] = BPF_S_ALU_OR_K, + [BPF_ALU|BPF_OR|BPF_X] = BPF_S_ALU_OR_X, + [BPF_ALU|BPF_LSH|BPF_K] = BPF_S_ALU_LSH_K, + [BPF_ALU|BPF_LSH|BPF_X] = BPF_S_ALU_LSH_X, + [BPF_ALU|BPF_RSH|BPF_K] = BPF_S_ALU_RSH_K, + [BPF_ALU|BPF_RSH|BPF_X] = BPF_S_ALU_RSH_X, + [BPF_ALU|BPF_NEG] = BPF_S_ALU_NEG, + [BPF_LD|BPF_W|BPF_ABS] = BPF_S_LD_W_ABS, + [BPF_LD|BPF_H|BPF_ABS] = BPF_S_LD_H_ABS, + [BPF_LD|BPF_B|BPF_ABS] = BPF_S_LD_B_ABS, + [BPF_LD|BPF_W|BPF_LEN] = BPF_S_LD_W_LEN, + [BPF_LD|BPF_W|BPF_IND] = BPF_S_LD_W_IND, + [BPF_LD|BPF_H|BPF_IND] = BPF_S_LD_H_IND, + [BPF_LD|BPF_B|BPF_IND] = BPF_S_LD_B_IND, + [BPF_LD|BPF_IMM] = BPF_S_LD_IMM, + [BPF_LDX|BPF_W|BPF_LEN] = BPF_S_LDX_W_LEN, + [BPF_LDX|BPF_B|BPF_MSH] = BPF_S_LDX_B_MSH, + [BPF_LDX|BPF_IMM] = BPF_S_LDX_IMM, + [BPF_MISC|BPF_TAX] = BPF_S_MISC_TAX, + [BPF_MISC|BPF_TXA] = BPF_S_MISC_TXA, + [BPF_RET|BPF_K] = BPF_S_RET_K, + [BPF_RET|BPF_A] = BPF_S_RET_A, + [BPF_ALU|BPF_DIV|BPF_K] = BPF_S_ALU_DIV_K, + [BPF_LD|BPF_MEM] = BPF_S_LD_MEM, + [BPF_LDX|BPF_MEM] = BPF_S_LDX_MEM, + [BPF_ST] = BPF_S_ST, + [BPF_STX] = BPF_S_STX, + [BPF_JMP|BPF_JA] = BPF_S_JMP_JA, + [BPF_JMP|BPF_JEQ|BPF_K] = BPF_S_JMP_JEQ_K, + [BPF_JMP|BPF_JEQ|BPF_X] = BPF_S_JMP_JEQ_X, + [BPF_JMP|BPF_JGE|BPF_K] = BPF_S_JMP_JGE_K, + [BPF_JMP|BPF_JGE|BPF_X] = BPF_S_JMP_JGE_X, + [BPF_JMP|BPF_JGT|BPF_K] = BPF_S_JMP_JGT_K, + [BPF_JMP|BPF_JGT|BPF_X] = BPF_S_JMP_JGT_X, + [BPF_JMP|BPF_JSET|BPF_K] = BPF_S_JMP_JSET_K, + [BPF_JMP|BPF_JSET|BPF_X] = BPF_S_JMP_JSET_X, }; int pc;
net/core/filter.c int sk_chk_filter(struct sock_filter *filter, int flen) · line 501
Quoted 9 lines
net/core/filter.c +1
-2@@ -495,8 +495,7 @@ int sk_chk_filter(struct sock_filter *filter, int flen) if (code >= ARRAY_SIZE(codes)) return -EINVAL; code = codes[code]; - /* Undo the '+ 1' in codes[] after validation. */ - if (!code--) + if (!code) return -EINVAL; /* Some instructions need special checks */ switch (code) {
I compared the asm code of sk_run_filter.
Here is the original:
switch (fentry->code) {
ffffffff8138c70c: 66 83 38 2c cmpw $0x2c,(%rax)
/*
* Process array of filter instructions.
*/
for (pc = 0; pc < flen; pc++) {
const struct sock_filter *fentry = &filter[pc];
u32 f_k = fentry->k;ffffffff8138c710: 44 8b 78 04 mov 0x4(%rax),%r15d
switch (fentry->code) {
ffffffff8138c714: 0f 87 53 02 00 00 ja
ffffffff8138c96d <sk_run_filter+0x2a8>
ffffffff8138c71a: 0f b7 10 movzwl (%rax),%edx
ffffffff8138c71d: ff 24 d5 00 00 00 00 jmpq *0x0(,%rdx,8)And here is the patched:
switch (fentry->code) {
ffffffff8138c708: 8b 10 mov (%rax),%edx
/*
* Process array of filter instructions.
*/
for (pc = 0; pc < flen; pc++) {
const struct sock_filter *fentry = &filter[pc];
u32 f_k = fentry->k;ffffffff8138c70a: 44 8b 78 04 mov 0x4(%rax),%r15d
switch (fentry->code) {
ffffffff8138c70e: ff ca dec %edx
ffffffff8138c710: 66 83 fa 2c cmp $0x2c,%dx
ffffffff8138c714: 0f 87 53 02 00 00 ja
ffffffff8138c96d <sk_run_filter+0x2ac>
ffffffff8138c71a: 0f b7 d2 movzwl %dx,%edx
ffffffff8138c71d: ff 24 d5 00 00 00 00 jmpq *0x0(,%rdx,8)As you see, an additional 'dec %edx' instruction is inserted. sk_chk_filter() only runs 1 times, I think we can afford the 'dec instruction' and 'dirty' code, but sk_run_filter() runs much often, this additional dec instruction isn't affordable.
Signature · 2 lines
Regards, Changli Gao([email protected])
Re: [PATCH net-next-2.6] filter: cleanup codes[] init
Quoted 7 lines · Changli Gao
I compared the asm code of
sk_run_filter.As you see, an additional 'dec %edx' instruction is inserted.
sk_chk_filter()only runs 1 times, I think we can afford the 'dec instruction' and 'dirty' code, butsk_run_filter()runs much often, this additional dec instruction isn't affordable.
Maybe on your setup. By the way, the
u32 f_k = fentry->k;
that David added in commit 57fe93b374a6b871
was much more a problem on arches with not enough registers.
x86_32 for example : compiler use a register (%esi on my gcc-4.5.1) to store f_k, and more important A register is now stored in stack instead of a cpu register.
On my compilers
gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5) 64bit gcc-4.5.1 (self compiled) 32bit
result code was the same, before and after patch
Most probably you have "CONFIG_CC_OPTIMIZE_FOR_SIZE=y" which unfortunately is known to generate poor looking code.
39b: 49 8d 14 c6 lea (%r14,%rax,8),%rdx 39f: 66 83 3a 2d cmpw $0x2d,(%rdx) 3a3: 8b 42 04 mov 0x4(%rdx),%eax // f_k = fentry->k; 3a6: 76 28 jbe 3d0 <sk_run_filter+0x70>
3d0: 0f b7 0a movzwl (%rdx),%ecx
3d3: ff 24 cd 00 00 00 00 jmpq *0x0(,%rcx,8)
32bit code:
2e0: 8d 04 df lea (%edi,%ebx,8),%eax 2e3: 66 83 38 2d cmpw $0x2d,(%eax) 2e7: 8b 70 04 mov 0x4(%eax),%esi // f_k = fentry->k; 2ea: 76 1c jbe 308 <sk_run_filter+0x58>
308: 0f b7 10 movzwl (%eax),%edx
30b: ff 24 95 38 00 00 00 jmp *0x38(,%edx,4)
DIV_X instruction :
480: 8b 45 a4 mov -0x5c(%ebp),%eax 483: 85 c0 test %eax,%eax 485: 0f 84 9d fe ff ff je 328 <sk_run_filter+0x78> 48b: 8b 45 ac mov -0x54(%ebp),%eax // A 48e: 31 d2 xor %edx,%edx 490: f7 75 a4 divl -0x5c(%ebp) 493: 89 45 ac mov %eax,-0x54(%ebp) // A 496: e9 85 fe ff ff jmp 320 <sk_run_filter+0x70>
I believe we should revert the u32 f_k = fentry->k; part
fentry->k as is fast as f_k if stored on stack, and avoids one instruction if fentry->k is not needed.
PATCH 1/1 filter: optimize sk_run_filter
Quoted 6 lines · Eric Dumazet
I believe we should revert the u32
f_k=fentry->k; part
fentry->kas is fast asf_kif stored on stack, and avoids one instruction iffentry->kis not needed.
A revert is not good on arches with decent number of registers (x86_64 for example).
Maybe have some CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS is needed, (or already exist ?)
Here is the patch to save 400 bytes on x86_32, and really speedup the damn thing on all arches.
Thanks
[PATCH net-next-2.6] filter: optimize sk_run_filter
remove pc variable to avoid arithmetic to compute fentry at each filter instruction. Jumps directly manipulate fentry pointer.
As the last instruction of filter[] is guaranteed to be a RETURN, and all jumps are before the last instruction, we dont need to check filter bounds (number of instructions in filter array) at each iteration, so we remove it from sk_run_filter() params.
On x86_32 remove f_k var introduced in commit 57fe93b374a6b871 (filter: make sure filters dont read uninitialized memory)
Note : We could use a CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS in order to avoid too many ifdefs in this code.
This helps compiler to use cpu registers to hold fentry and A accumulator.
On x86_32, this saves 401 bytes, and more important, sk_run_filter() runs much faster because less register pressure (One less conditional branch per BPF instruction)
# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 2948 0 0 2948 b84 net/core/filter.o 3349 0 0 3349 d15 net/core/filter_pre.o
on x86_64 :
# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 5173 0 0 5173 1435 net/core/filter.o 5224 0 0 5224 1468 net/core/filter_pre.o
--- include/linux/filter.h | 2 net/core/filter.c | 93 +++++++++++++++++++------------------- net/core/timestamping.c | 2 net/packet/af_packet.c | 2 4 files changed, 51 insertions(+), 48 deletions(-)
include/linux/filter.h +1 -1
@@ -147,7 +147,7 @@ struct sock;extern int sk_filter (struct sock *sk,struct sk_buff *skb);extern unsigned int sk_run_filter (struct sk_buff *skb, -struct sock_filter *filter,int flen); +const struct sock_filter *filter);extern int sk_attach_filter (struct sock_fprog *fprog,struct sock *sk);extern int sk_detach_filter (struct sock *sk);extern int sk_chk_filter (struct sock_filter *filter,int flen);
net/core/filter.c +48 -45
231 lines not on this page · raw message
net/core/timestamping.c +1 -1
@@ -31,7 +31,7 @@ static unsigned int classify(struct sk_buff *skb)if (likely (skb->dev && skb->dev->phydev && skb->dev->phydev->drv)) -return sk_run_filter (skb, ptp_filter,ARRAY_SIZE (ptp_filter)); +return sk_run_filter (skb, ptp_filter);else return PTP_CLASS_NONE ; }
net/packet/af_packet.c +1 -1
@@ -519,7 +519,7 @@ static inline unsigned int run_filter(struct sk_buff *skb, struct sock *sk,rcu_read_lock_bh (); filter =rcu_dereference_bh (sk->sk_filter);if (filter !=NULL ) - res =sk_run_filter (skb, filter->insns, filter->len); + res =sk_run_filter (skb, filter->insns);rcu_read_unlock_bh ();return res;
Re: [PATCH net-next-2.6] filter: optimize sk_run_filter
Quoted 57 lines · Eric Dumazet
Quoted 6 lines · Eric Dumazet
I believe we should revert the u32
f_k=fentry->k; part
fentry->kas is fast asf_kif stored on stack, and avoids one instruction iffentry->kis not needed.A revert is not good on arches with decent number of registers (
x86_64for example).Maybe have some CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS is needed, (or already exist ?)
Here is the patch to save 400 bytes on
x86_32, and really speedup the damn thing on all arches.Thanks
[PATCH net-next-2.6] filter: optimize
sk_run_filterremove pc variable to avoid arithmetic to compute fentry at each filter instruction. Jumps directly manipulate fentry pointer.
As the last instruction of filter[] is guaranteed to be a RETURN, and all jumps are before the last instruction, we dont need to check filter bounds (number of instructions in filter array) at each iteration, so we remove it from
sk_run_filter()params.On
x86_32removef_kvar introduced in commit57fe93b374a6b871(filter: make sure filters dont read uninitialized memory)Note : We could use a CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS in order to avoid too many ifdefs in this code.
This helps compiler to use cpu registers to hold fentry and A accumulator.
On
x86_32, this saves 401 bytes, and more important,sk_run_filter()runs much faster because less register pressure (One less conditional branch per BPF instruction)# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 2948 0 0 2948 b84 net/core/filter.o 3349 0 0 3349 d15 net/core/filter_pre.oon
x86_64:# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 5173 0 0 5173 1435 net/core/filter.o 5224 0 0 5224 1468 net/core/filter_pre.oSigned-off-by Eric Dumazet <[email protected]>Cc Changli Gao <[email protected]>Cc Hagen Paul Pfeifer <[email protected]>
Quoted 7 lines
---
include/linux/filter.h | 2
net/core/filter.c | 93 +++++++++++++++++++-------------------net/core/timestamping.c| 2
net/packet/af_packet.c | 24 files changed, 51 insertions(+), 48 deletions(-)
you missed the users of sk_run_filter in directory dev/.
Signature · 2 lines
Regards, Changli Gao([email protected])
Re: [PATCH net-next-2.6] filter: optimize sk_run_filter
Quoted 3 lines · Changli Gao
you missed the users of
sk_run_filterin directory dev/.
Sorry, the directory is drivers/.
Signature · 2 lines
Regards, Changli Gao([email protected])
PATCH v2 1/1 filter: optimize sk_run_filter
Quoted 8 lines · Changli Gao
Quoted 3 lines · Changli Gao
you missed the users of
sk_run_filterin directory dev/.Sorry, the directory is
drivers/.
You're right, thanks !
[PATCH net-next-2.6 v2] filter: optimize sk_run_filter
Remove pc variable to avoid arithmetic to compute fentry at each filter instruction. Jumps directly manipulate fentry pointer.
As the last instruction of filter[] is guaranteed to be a RETURN, and all jumps are before the last instruction, we dont need to check filter bounds (number of instructions in filter array) at each iteration, so we remove it from sk_run_filter() params.
On x86_32 remove f_k var introduced in commit 57fe93b374a6b871 (filter: make sure filters dont read uninitialized memory)
Note : We could use a CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS in order to avoid too many ifdefs in this code.
This helps compiler to use cpu registers to hold fentry and A accumulator.
On x86_32, this saves 401 bytes, and more important, sk_run_filter() runs much faster because less register pressure (One less conditional branch per BPF instruction)
# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 2948 0 0 2948 b84 net/core/filter.o 3349 0 0 3349 d15 net/core/filter_pre.o
on x86_64 :
# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 5173 0 0 5173 1435 net/core/filter.o 5224 0 0 5224 1468 net/core/filter_pre.o
---
V2: add missing changes for drivers/isdn/i4l/isdn_ppp.c & drivers/net/ppp_generic.c
drivers/isdn/i4l/isdn_ppp.c | 14 ++--- drivers/net/ppp_generic.c | 12 +--- include/linux/filter.h | 2 net/core/filter.c | 93 +++++++++++++++++----------------- net/core/timestamping.c | 2 net/packet/af_packet.c | 2 6 files changed, 61 insertions(+), 64 deletions(-)
drivers/isdn/i4l/isdn_ppp.c +6 -8
@@ -1147,15 +1147,14 @@ isdn_ppp_push_higher(isdn_net_dev * net_dev, isdn_net_local * lp, struct sk_buff }if (is->pass_filter - &&sk_run_filter (skb, is->pass_filter, is->pass_len) ==0 ) { + &&sk_run_filter (skb, is->pass_filter) ==0 ) {if (is->debug &0x2 )printk (KERN_DEBUG "IPPP: inbound frame filtered.\n" );kfree_skb (skb);return ; }if (!(is->active_filter - &&sk_run_filter (skb, is->active_filter, - is->active_len) ==0 )) { + &&sk_run_filter (skb, is->active_filter) ==0 )) {if (is->debug &0x2 )printk (KERN_DEBUG "IPPP: link-active filter: reseting huptimer.\n" ); lp->huptimer =0 ;
@@ -1294,15 +1293,14 @@ isdn_ppp_xmit(struct sk_buff *skb, struct net_device *netdev) }if (ipt->pass_filter - &&sk_run_filter (skb, ipt->pass_filter, ipt->pass_len) ==0 ) { + &&sk_run_filter (skb, ipt->pass_filter) ==0 ) {if (ipt->debug &0x4 )printk (KERN_DEBUG "IPPP: outbound frame filtered.\n" );kfree_skb (skb); goto unlock; }if (!(ipt->active_filter - &&sk_run_filter (skb, ipt->active_filter, - ipt->active_len) ==0 )) { + &&sk_run_filter (skb, ipt->active_filter) ==0 )) {if (ipt->debug &0x4 )printk (KERN_DEBUG "IPPP: link-active filter: reseting huptimer.\n" ); lp->huptimer =0 ;
@@ -1492,9 +1490,9 @@ int isdn_ppp_autodial_filter(struct sk_buff *skb, isdn_net_local *lp) } drop |= is->pass_filter - &&sk_run_filter (skb, is->pass_filter, is->pass_len) ==0 ; + &&sk_run_filter (skb, is->pass_filter) ==0 ; drop |= is->active_filter - &&sk_run_filter (skb, is->active_filter, is->active_len) ==0 ; + &&sk_run_filter (skb, is->active_filter) ==0 ;skb_push (skb,IPPP_MAX_HEADER -4 );return drop;
drivers/net/ppp_generic.c +4 -8
@@ -1136,8 +1136,7 @@ ppp_send_frame(struct ppp *ppp, struct sk_buff *skb)a four-byte PPP header on each packet */ *skb_push (skb,2 ) =1 ;if (ppp->pass_filter && -sk_run_filter (skb, ppp->pass_filter, - ppp->pass_len) ==0 ) { +sk_run_filter (skb, ppp->pass_filter) ==0 ) {if (ppp->debug &1 )printk (KERN_DEBUG "PPP: outbound frame not passed\n" );kfree_skb (skb);
@@ -1145,8 +1144,7 @@ ppp_send_frame(struct ppp *ppp, struct sk_buff *skb) }/* if this packet passes the active filter, record the time */ if (!(ppp->active_filter && -sk_run_filter (skb, ppp->active_filter, - ppp->active_len) ==0 )) +sk_run_filter (skb, ppp->active_filter) ==0 )) ppp->last_xmit = jiffies;skb_pull (skb,2 );#else
@@ -1758,8 +1756,7 @@ ppp_receive_nonmp_frame(struct ppp *ppp, struct sk_buff *skb) *skb_push (skb,2 ) =0 ;if (ppp->pass_filter && -sk_run_filter (skb, ppp->pass_filter, - ppp->pass_len) ==0 ) { +sk_run_filter (skb, ppp->pass_filter) ==0 ) {if (ppp->debug &1 )printk (KERN_DEBUG "PPP: inbound frame " "not passed\n" );
@@ -1767,8 +1764,7 @@ ppp_receive_nonmp_frame(struct ppp *ppp, struct sk_buff *skb)return ; }if (!(ppp->active_filter && -sk_run_filter (skb, ppp->active_filter, - ppp->active_len) ==0 )) +sk_run_filter (skb, ppp->active_filter) ==0 )) ppp->last_recv = jiffies;__skb_pull (skb,2 ); }else
include/linux/filter.h +1 -1
@@ -147,7 +147,7 @@ struct sock;extern int sk_filter (struct sock *sk,struct sk_buff *skb);extern unsigned int sk_run_filter (struct sk_buff *skb, -struct sock_filter *filter,int flen); +const struct sock_filter *filter);extern int sk_attach_filter (struct sock_fprog *fprog,struct sock *sk);extern int sk_detach_filter (struct sock *sk);extern int sk_chk_filter (struct sock_filter *filter,int flen);
net/core/filter.c +48 -45
231 lines not on this page · raw message
net/core/timestamping.c +1 -1
@@ -31,7 +31,7 @@ static unsigned int classify(struct sk_buff *skb)if (likely (skb->dev && skb->dev->phydev && skb->dev->phydev->drv)) -return sk_run_filter (skb, ptp_filter,ARRAY_SIZE (ptp_filter)); +return sk_run_filter (skb, ptp_filter);else return PTP_CLASS_NONE ; }
net/packet/af_packet.c +1 -1
@@ -519,7 +519,7 @@ static inline unsigned int run_filter(struct sk_buff *skb, struct sock *sk,rcu_read_lock_bh (); filter =rcu_dereference_bh (sk->sk_filter);if (filter !=NULL ) - res =sk_run_filter (skb, filter->insns, filter->len); + res =sk_run_filter (skb, filter->insns);rcu_read_unlock_bh ();return res;
Re: [PATCH net-next-2.6 v2] filter: optimize sk_run_filter
Quoted 41 lines · Eric Dumazet
Quoted 8 lines · Changli Gao
Quoted 3 lines · Changli Gao
you missed the users of
sk_run_filterin directory dev/.Sorry, the directory is
drivers/.You're right, thanks !
[PATCH net-next-2.6 v2] filter: optimize
sk_run_filterRemove pc variable to avoid arithmetic to compute fentry at each filter instruction. Jumps directly manipulate fentry pointer.
As the last instruction of filter[] is guaranteed to be a RETURN, and all jumps are before the last instruction, we dont need to check filter bounds (number of instructions in filter array) at each iteration, so we remove it from
sk_run_filter()params.On
x86_32removef_kvar introduced in commit57fe93b374a6b871(filter: make sure filters dont read uninitialized memory)Note : We could use a CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS in order to avoid too many ifdefs in this code.
This helps compiler to use cpu registers to hold fentry and A accumulator.
On
x86_32, this saves 401 bytes, and more important,sk_run_filter()runs much faster because less register pressure (One less conditional branch per BPF instruction)# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 2948 0 0 2948 b84 net/core/filter.o 3349 0 0 3349 d15 net/core/filter_pre.oon
x86_64:
Quoted 8 lines
# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 5173 0 0 5173 1435 net/core/filter.o 5224 0 0 5224 1468 net/core/filter_pre.oSigned-off-by Eric Dumazet <[email protected]>Cc Changli Gao <[email protected]>Cc Hagen Paul Pfeifer <[email protected]>
Signature · 2 lines
Regards, Changli Gao([email protected])
David Miller
maintainerRe: [PATCH net-next-2.6 v2] filter: optimize sk_run_filter
From: Changli Gao <[email protected]>
Date: Fri, 19 Nov 2010 22:13:07 +0800
Quoted 35 lines · Eric Dumazet
Quoted 34 lines
[PATCH net-next-2.6 v2] filter: optimize
sk_run_filterRemove pc variable to avoid arithmetic to compute fentry at each filter instruction. Jumps directly manipulate fentry pointer.
As the last instruction of filter[] is guaranteed to be a RETURN, and all jumps are before the last instruction, we dont need to check filter bounds (number of instructions in filter array) at each iteration, so we remove it from
sk_run_filter()params.On
x86_32removef_kvar introduced in commit57fe93b374a6b871(filter: make sure filters dont read uninitialized memory)Note : We could use a CONFIG_ARCH_HAS_{FEW|MANY}_REGISTERS in order to avoid too many ifdefs in this code.
This helps compiler to use cpu registers to hold fentry and A accumulator.
On
x86_32, this saves 401 bytes, and more important,sk_run_filter()runs much faster because less register pressure (One less conditional branch per BPF instruction)# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 2948 0 0 2948 b84 net/core/filter.o 3349 0 0 3349 d15 net/core/filter_pre.oon
x86_64:# size net/core/filter.o net/core/filter_pre.o text data bss dec hex filename 5173 0 0 5173 1435 net/core/filter.o 5224 0 0 5224 1468 net/core/filter_pre.o
Quoted 5 lines
Quoted 3 lines
Signed-off-by Eric Dumazet <[email protected]>Cc Changli Gao <[email protected]>Cc Hagen Paul Pfeifer <[email protected]>Acked-by Changli Gao <[email protected]>
Ok, I'm applying this to net-next-2.6 for now. It keeps the "f_k" situation optimal for all cases, on every platform I've taken a look at the asm output (sparc64, x86-32, x86-64).
I can't currently think of a way to get rid of that ifdef, so for now it's a small price to pay to get this optimal.
Thanks Eric!
Re: [PATCH net-next-2.6 v2] filter: optimize sk_run_filter
In reply to Eric DumazetJust my thought again...
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 170
Quoted 4 lines · Eric Dumazet
net/core/filter.c +0
-0@@ -167,34 +168,36 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, intunsigned long memvalid =0 ;u32 tmp;int k;
Is this 'k' useful?
Quoted 4 lines
net/core/filter.c +0
-1-int pc;BUILD_BUG_ON (BPF_MEMWORDS >BITS_PER_LONG );/*
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 180
Quoted 10 lines
net/core/filter.c +5
-3* Process array of filter instructions. */ -for (pc =0 ; pc < flen; pc++) { -const struct sock_filter *fentry = &filter[pc]; -u32 f_k = fentry->k; +for (;; fentry++) { +#if defined(CONFIG_X86_32 ) +#define K (fentry->k) +#else +const u32 K = fentry->k;
What happens if we use
u32 f_k = fentry->k;
and
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 265
Quoted 3 lines
net/core/filter.c +1
-1case BPF_S_LD_W_ABS : - k = f_k; + k =K ;
remove this assignment and
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 267
Quoted 2 lines
net/core/filter.c +0
-0load_w: ptr =load_pointer (skb, k,4 , &tmp);
change to
ptr = load_pointer(skb, (int) f_k, 4, &tmp);
and
net/core/filter.c load_b: · line 298
Quoted 3 lines
net/core/filter.c +1
-1case BPF_S_LD_W_IND : - k =X + f_k; + k =X +K ;
change to
f_k += X;
?
Quoted 1 line
net/core/filter.c +0
-0goto load_w;
Re: [PATCH net-next-2.6 v2] filter: optimize sk_run_filter
Quoted 10 lines · Tetsuo Handa
Just my thought again...
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 170
Quoted 4 lines · Eric Dumazet
net/core/filter.c +0
-0@@ -167,34 +168,36 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, intunsigned long memvalid =0 ;u32 tmp;int k;Is this 'k' useful?
Yes this is useful, please read later we have :
k = X + K; goto load_w;
K is readonly, k is a rw temp variable (on stack)
Quoted 42 lines
Quoted 4 lines
net/core/filter.c +0
-1-int pc;BUILD_BUG_ON (BPF_MEMWORDS >BITS_PER_LONG );/* net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 180
Quoted 10 lines
net/core/filter.c +5
-3* Process array of filter instructions. */ -for (pc =0 ; pc < flen; pc++) { -const struct sock_filter *fentry = &filter[pc]; -u32 f_k = fentry->k; +for (;; fentry++) { +#if defined(CONFIG_X86_32 ) +#define K (fentry->k) +#else +const u32 K = fentry->k;What happens if we use
u32 f_k = fentry->k;and
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 265
Quoted 3 lines
net/core/filter.c +1
-1case BPF_S_LD_W_ABS : - k = f_k; + k =K ;remove this assignment and
net/core/filter.c unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int · line 267
Quoted 2 lines
net/core/filter.c +0
-0load_w: ptr =load_pointer (skb, k,4 , &tmp);change to
ptr = load_pointer(skb, (int) f_k, 4, &tmp);and
net/core/filter.c load_b: · line 298
Quoted 3 lines
net/core/filter.c +1
-1case BPF_S_LD_W_IND : - k =X + f_k; + k =X +K ;change to
Quoted 4 lines
f_k += X;?
Quoted 1 line
net/core/filter.c +0
-0goto load_w;
This wont work, K is really a constant, part of the filter program, while k is the (existing) temp variable.
David Miller
maintainerRe: [PATCH net-next-2.6] filter: optimize sk_run_filter
In reply to Eric DumazetFrom: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 12:17:52 +0100
Quoted 11 lines · Eric Dumazet
Quoted 7 lines
I believe we should revert the u32
f_k=fentry->k; part
fentry->kas is fast asf_kif stored on stack, and avoids one instruction iffentry->kis not needed.A revert is not good on arches with decent number of registers (
x86_64for example).
-EFIX_THE_DAMN_COMPILER
We never make calls out of this function or touch volatile memory or create a full memory barrier between the assignment of f_k and it's uses.
Therefore if common sub-expression elimination is working the compiler will be able to decide properly whether to access things via memory or use a register for the value.
Remember this is why we have that ACCESS_ONCE() thing.
We can't have it both ways, either ACCESS_ONCE() should be removed or we should never make changes like your's and instead should submit compiler bug reports :-)
Re: [PATCH net-next-2.6] filter: optimize sk_run_filter
Quoted 10 lines · David Miller
-EFIX_THE_DAMN_COMPILER
We never make calls out of this function or touch volatile memory or create a full memory barrier between the assignment of
f_kand it's uses.Therefore if common sub-expression elimination is working the compiler will be able to decide properly whether to access things via memory or use a register for the value.
Quoted 5 lines
Remember this is why we have that
ACCESS_ONCE()thing.We can't have it both ways, either
ACCESS_ONCE()should be removed or we should never make changes like your's and instead should submit compiler bug reports :-)
Compiler is OK IMHO in this case. It does exactly what is required.
Compiler cannot load fentry->k before the switch() if some expression dont use it, as it could trigger a fault.
After the "f_k = fentry->k;" commit, it was requested to do so.
Unfortunatly on x86_32 it also chose that f_k was more valuable in a cpu register and accumulator A lost its register to get a stack slot instead.
Not many BPF instructions use K, and if used, its used _once_ per BPF instruction. There is no real gain to put it on a register, but code size if (and only if) it is held in a cpu register, because each assembler instruction using a register instead of stack is a bit shorter.
In the end, I believe the "f_k = fentry->k;" was a good looking idea, and good for some arches, but we forgot x86_32 (and probably some others) have few available registers to play with.
Have a good week end !
David Miller
maintainerRe: [PATCH net-next-2.6] filter: optimize sk_run_filter
From: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 17:55:59 +0100
Quoted 3 lines
Unfortunatly on
x86_32it also chose thatf_kwas more valuable in a cpu register and accumulator A lost its register to get a stack slot instead.
Ok that tradeoff is terrible, but it depends upon knowledge we haven't given to the compiler (yet).
Let me think about this a bit...
Re: [PATCH net-next-2.6] filter: optimize sk_run_filter
Quoted 11 lines · On Fri, 19 Nov 2010 09:05:16 -0800 (PST) David Miller <[email protected]>…
From: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 17:55:59 +0100Quoted 3 lines
Unfortunatly on
x86_32it also chose thatf_kwas more valuable in a cpu register and accumulator A lost its register to get a stack slot instead.Ok that tradeoff is terrible, but it depends upon knowledge we haven't given to the compiler (yet).
Let me think about this a bit...
Are 'register' modifiers a no-op on current GCC?
David Miller
maintainerRe: [PATCH net-next-2.6] filter: optimize sk_run_filter
From: Stephen Hemminger <[email protected]>
Date: Fri, 19 Nov 2010 09:15:37 -0800
Quoted 10 lines
Quoted 7 lines · On Fri, 19 Nov 2010 09:05:16 -0800 (PST) David Miller <[email protected]>…
From: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 17:55:59 +0100Quoted 3 lines
Unfortunatly on
x86_32it also chose thatf_kwas more valuable in a cpu register and accumulator A lost its register to get a stack slot instead.
Quoted 6 lines
Quoted 4 lines
Ok that tradeoff is terrible, but it depends upon knowledge we haven't given to the compiler (yet).
Let me think about this a bit...
Are 'register' modifiers a no-op on current GCC?
Yes, they are.
Re: [PATCH net-next-2.6] filter: optimize sk_run_filter
In reply to David MillerQuoted 11 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 17:55:59 +0100Quoted 3 lines
Unfortunatly on
x86_32it also chose thatf_kwas more valuable in a cpu register and accumulator A lost its register to get a stack slot instead.Ok that tradeoff is terrible, but it depends upon knowledge we haven't given to the compiler (yet).
Let me think about this a bit...
By the way, I tried the 'register' keyword, and I knew it was a stupid idea before even trying, since compiler ignored me : "What the hell do you think you can tell me how to optimize this code ?"
(I am quite sure my laptop even smiled and sent to his neighbours a broadcast saying "Hey buddies, this dumb guy tried the register C keyword, isnt it funny ?")
Oh well...
David Miller
maintainerRe: [PATCH net-next-2.6] filter: optimize sk_run_filter
From: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 18:16:24 +0100
Quoted 13 lines · David Miller
Quoted 11 lines
From: Eric Dumazet <[email protected]>
Date: Fri, 19 Nov 2010 17:55:59 +0100Quoted 3 lines
Unfortunatly on
x86_32it also chose thatf_kwas more valuable in a cpu register and accumulator A lost its register to get a stack slot instead.Ok that tradeoff is terrible, but it depends upon knowledge we haven't given to the compiler (yet).
Let me think about this a bit...
Quoted 7 lines
By the way, I tried the 'register' keyword, and I knew it was a stupid idea before even trying, since compiler ignored me : "What the hell do you think you can tell me how to optimize this code ?"
(I am quite sure my laptop even smiled and sent to his neighbours a broadcast saying "Hey buddies, this dumb guy tried the register C keyword, isnt it funny ?")
:-)
I wonder though, since "fentry" is const in your recent patch, you might not even need that X86_32 ifdef thing. GCC should actually now be able to see that fentry->k cannot change, even when we make external function calls via load_pointer() and such.
Changli Gao
Acked-byRe: [PATCH net-next-2.6] filter: cleanup codes[] init
In reply to Eric DumazetQuoted 3 lines · Eric Dumazet
Most probably you have "
CONFIG_CC_OPTIMIZE_FOR_SIZE=y" which unfortunately is known to generate poor looking code.
Yes. So
Signature · 2 lines
Regards, Changli Gao([email protected])
Re: [PATCH net-next-2.6] filter: cleanup codes[] init
From: Changli Gao <[email protected]>
Date: Fri, 19 Nov 2010 20:21:57 +0800
Quoted 8 lines · Eric Dumazet
Quoted 3 lines
Most probably you have "
CONFIG_CC_OPTIMIZE_FOR_SIZE=y" which unfortunately is known to generate poor looking code.Yes. So
Acked-by Changli Gao <[email protected]>
Applied.