Re: [PATCH net-next-2.6] filter: cleanup codes[] init

Changli Gao
2010-11-19T08:38:35Z

On Fri, Nov 19, 2010 at 3:56 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> 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 <eric.dumazet@gmail.com>
> ---
>  net/core/filter.c |   95 +++++++++++++++++++++-----------------------
>  1 file changed, 47 insertions(+), 48 deletions(-)
>
> diff --git a/net/core/filter.c b/net/core/filter.c
> index 15a545d..a1edb5d 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -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) {
>
>
>

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.

--
Regards,
Changli Gao(xiaosuo@gmail.com)