| Message ID | 201011162208.BHC17628.SVtFMJOOLFQFOH@I-love.SAKURA.ne.jp |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
16.11.2010 16:08, Tetsuo Handa wrote: [] > net/core/filter.c | 214 ++++++++++++++++------------------------------------- > 1 files changed, 65 insertions(+), 149 deletions(-) > > diff --git a/net/core/filter.c b/net/core/filter.c > index 23e9b2a..85be3d8 100644 > --- a/net/core/filter.c > +++ b/net/core/filter.c > @@ -383,7 +383,57 @@ EXPORT_SYMBOL(sk_run_filter); > */ > int sk_chk_filter(struct sock_filter *filter, int flen) > { > - struct sock_filter *ftest; > + /* > + * Valid instructions are initialized to non-0. > + * Invalid instructions are initialized to 0. > + */ > + static u16 codes[] = { > + [BPF_ALU|BPF_ADD|BPF_K] = BPF_S_ALU_ADD_K + 1, How about using some "const" there? :) /mjt -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Le mardi 16 novembre 2010 à 22:08 +0900, Tetsuo Handa a écrit : > In the wake of commit 57fe93b3 "filter: make sure filters dont read > uninitialized memory", I came up with this patch. I don't know how to test. > Please review and do tests. > > This patch optimizes sk_chk_filter(). Using gcc 4.1.2 on x86_32, the size of > net/core/filter.o changed from 7416 bytes to 5260 bytes > ("make allnoconfig" + CONFIG_NET=y). > > By the way, if "struct sock_filter *filter" argument of sk_run_filter() does > not change after it was revalidated at sk_chk_filter(), can't we detect and > reject "BPF_S_LD_MEM/BPF_S_LDX_MEM before BPF_S_ST/BPF_S_STX" at > sk_chk_filter()? Sure, this was the idea, but seems complex because of branches. Patches are welcomed ;) > ---------------------------------------- > From 2bf36130bd4912590b409b47a6a9a82e2884e035 Mon Sep 17 00:00:00 2001 > From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> > Date: Tue, 16 Nov 2010 21:39:50 +0900 > Subject: [PATCH] filter: Optimize instruction revalidation code. > > Since repeating small value to small value conversion using switch() clause's > case statement is wasteful, this patch instroduces u16 to u16 mapping table > and removes most of case statements. As a result, the size of net/core/filter.o > is reduced by about 30% on x86. > > Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> > --- Patch seems fine to me, with the 'const' codes[] Michael Tokarev already spotted. Thanks -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
* Tetsuo Handa | 2010-11-16 22:08:50 [+0900]: >--- a/net/core/filter.c >+++ b/net/core/filter.c >@@ -383,7 +383,57 @@ EXPORT_SYMBOL(sk_run_filter); > */ > int sk_chk_filter(struct sock_filter *filter, int flen) > { >- struct sock_filter *ftest; >+ /* >+ * Valid instructions are initialized to non-0. >+ * Invalid instructions are initialized to 0. >+ */ >+ static u16 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, [...] Maybe I don't get it, but you increment the opcode by one, but you never increment the opcode in sk_run_filter() - do I miss something? Did you test the your patch (a trivial tcpdump rule should be sufficient)? If this question is answered (or fixed): Signed-off-by: Hagen Paul Pfeifer <hagen@jauu.net> HGN -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Nov 16, 2010 at 9:08 PM, Tetsuo Handa <penguin-kernel@i-love.sakura.ne.jp> wrote: > In the wake of commit 57fe93b3 "filter: make sure filters dont read > uninitialized memory", I came up with this patch. I don't know how to test. > Please review and do tests. > > This patch optimizes sk_chk_filter(). Using gcc 4.1.2 on x86_32, the size of > net/core/filter.o changed from 7416 bytes to 5260 bytes > ("make allnoconfig" + CONFIG_NET=y). > > By the way, if "struct sock_filter *filter" argument of sk_run_filter() does > not change after it was revalidated at sk_chk_filter(), can't we detect and > reject "BPF_S_LD_MEM/BPF_S_LDX_MEM before BPF_S_ST/BPF_S_STX" at > sk_chk_filter()? > ---------------------------------------- > From 2bf36130bd4912590b409b47a6a9a82e2884e035 Mon Sep 17 00:00:00 2001 > From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> > Date: Tue, 16 Nov 2010 21:39:50 +0900 > Subject: [PATCH] filter: Optimize instruction revalidation code. > > Since repeating small value to small value conversion using switch() clause's > case statement is wasteful, this patch instroduces u16 to u16 mapping table > and removes most of case statements. As a result, the size of net/core/filter.o > is reduced by about 30% on x86. > > Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> > --- > net/core/filter.c | 214 ++++++++++++++++------------------------------------- > 1 files changed, 65 insertions(+), 149 deletions(-) > > diff --git a/net/core/filter.c b/net/core/filter.c > index 23e9b2a..85be3d8 100644 > --- a/net/core/filter.c > +++ b/net/core/filter.c > @@ -383,7 +383,57 @@ EXPORT_SYMBOL(sk_run_filter); > */ > int sk_chk_filter(struct sock_filter *filter, int flen) > { > - struct sock_filter *ftest; > + /* > + * Valid instructions are initialized to non-0. > + * Invalid instructions are initialized to 0. > + */ > + static u16 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, > + }; > int pc; > > if (flen == 0 || flen > BPF_MAXINSNS) > @@ -391,135 +441,26 @@ int sk_chk_filter(struct sock_filter *filter, int flen) > > /* check the filter code now */ > for (pc = 0; pc < flen; pc++) { > - ftest = &filter[pc]; > - > - /* Only allow valid instructions */ > - switch (ftest->code) { > - case BPF_ALU|BPF_ADD|BPF_K: > - ftest->code = BPF_S_ALU_ADD_K; > - break; > - case BPF_ALU|BPF_ADD|BPF_X: > - ftest->code = BPF_S_ALU_ADD_X; > - break; > - case BPF_ALU|BPF_SUB|BPF_K: > - ftest->code = BPF_S_ALU_SUB_K; > - break; > - case BPF_ALU|BPF_SUB|BPF_X: > - ftest->code = BPF_S_ALU_SUB_X; > - break; > - case BPF_ALU|BPF_MUL|BPF_K: > - ftest->code = BPF_S_ALU_MUL_K; > - break; > - case BPF_ALU|BPF_MUL|BPF_X: > - ftest->code = BPF_S_ALU_MUL_X; > - break; > - case BPF_ALU|BPF_DIV|BPF_X: > - ftest->code = BPF_S_ALU_DIV_X; > - break; > - case BPF_ALU|BPF_AND|BPF_K: > - ftest->code = BPF_S_ALU_AND_K; > - break; > - case BPF_ALU|BPF_AND|BPF_X: > - ftest->code = BPF_S_ALU_AND_X; > - break; > - case BPF_ALU|BPF_OR|BPF_K: > - ftest->code = BPF_S_ALU_OR_K; > - break; > - case BPF_ALU|BPF_OR|BPF_X: > - ftest->code = BPF_S_ALU_OR_X; > - break; > - case BPF_ALU|BPF_LSH|BPF_K: > - ftest->code = BPF_S_ALU_LSH_K; > - break; > - case BPF_ALU|BPF_LSH|BPF_X: > - ftest->code = BPF_S_ALU_LSH_X; > - break; > - case BPF_ALU|BPF_RSH|BPF_K: > - ftest->code = BPF_S_ALU_RSH_K; > - break; > - case BPF_ALU|BPF_RSH|BPF_X: > - ftest->code = BPF_S_ALU_RSH_X; > - break; > - case BPF_ALU|BPF_NEG: > - ftest->code = BPF_S_ALU_NEG; > - break; > - case BPF_LD|BPF_W|BPF_ABS: > - ftest->code = BPF_S_LD_W_ABS; > - break; > - case BPF_LD|BPF_H|BPF_ABS: > - ftest->code = BPF_S_LD_H_ABS; > - break; > - case BPF_LD|BPF_B|BPF_ABS: > - ftest->code = BPF_S_LD_B_ABS; > - break; > - case BPF_LD|BPF_W|BPF_LEN: > - ftest->code = BPF_S_LD_W_LEN; > - break; > - case BPF_LD|BPF_W|BPF_IND: > - ftest->code = BPF_S_LD_W_IND; > - break; > - case BPF_LD|BPF_H|BPF_IND: > - ftest->code = BPF_S_LD_H_IND; > - break; > - case BPF_LD|BPF_B|BPF_IND: > - ftest->code = BPF_S_LD_B_IND; > - break; > - case BPF_LD|BPF_IMM: > - ftest->code = BPF_S_LD_IMM; > - break; > - case BPF_LDX|BPF_W|BPF_LEN: > - ftest->code = BPF_S_LDX_W_LEN; > - break; > - case BPF_LDX|BPF_B|BPF_MSH: > - ftest->code = BPF_S_LDX_B_MSH; > - break; > - case BPF_LDX|BPF_IMM: > - ftest->code = BPF_S_LDX_IMM; > - break; > - case BPF_MISC|BPF_TAX: > - ftest->code = BPF_S_MISC_TAX; > - break; > - case BPF_MISC|BPF_TXA: > - ftest->code = BPF_S_MISC_TXA; > - break; > - case BPF_RET|BPF_K: > - ftest->code = BPF_S_RET_K; > - break; > - case BPF_RET|BPF_A: > - ftest->code = BPF_S_RET_A; > - break; > + struct sock_filter *ftest = &filter[pc]; Why move the define here? > + u16 code = ftest->code; > > + if (code >= ARRAY_SIZE(codes)) > + return 0; return -EINVAL; > /* Some instructions need special checks */ > - > - /* check for division by zero */ > + switch (code) { > case BPF_ALU|BPF_DIV|BPF_K: > + /* check for division by zero */ > if (ftest->k == 0) > return -EINVAL; > - ftest->code = BPF_S_ALU_DIV_K; > break; > - > - /* check for invalid memory addresses */ > case BPF_LD|BPF_MEM: > - if (ftest->k >= BPF_MEMWORDS) > - return -EINVAL; > - ftest->code = BPF_S_LD_MEM; > - break; > case BPF_LDX|BPF_MEM: > - if (ftest->k >= BPF_MEMWORDS) > - return -EINVAL; > - ftest->code = BPF_S_LDX_MEM; > - break; > case BPF_ST: > - if (ftest->k >= BPF_MEMWORDS) > - return -EINVAL; > - ftest->code = BPF_S_ST; > - break; > case BPF_STX: > + /* check for invalid memory addresses */ > if (ftest->k >= BPF_MEMWORDS) > return -EINVAL; > - ftest->code = BPF_S_STX; > break; > - > case BPF_JMP|BPF_JA: > /* > * Note, the large ftest->k might cause loops. > @@ -528,40 +469,14 @@ int sk_chk_filter(struct sock_filter *filter, int flen) > */ > if (ftest->k >= (unsigned)(flen-pc-1)) > return -EINVAL; > - ftest->code = BPF_S_JMP_JA; > - break; > - > - case BPF_JMP|BPF_JEQ|BPF_K: > - ftest->code = BPF_S_JMP_JEQ_K; > - break; > - case BPF_JMP|BPF_JEQ|BPF_X: > - ftest->code = BPF_S_JMP_JEQ_X; > - break; > - case BPF_JMP|BPF_JGE|BPF_K: > - ftest->code = BPF_S_JMP_JGE_K; > - break; > - case BPF_JMP|BPF_JGE|BPF_X: > - ftest->code = BPF_S_JMP_JGE_X; > - break; > - case BPF_JMP|BPF_JGT|BPF_K: > - ftest->code = BPF_S_JMP_JGT_K; > - break; > - case BPF_JMP|BPF_JGT|BPF_X: > - ftest->code = BPF_S_JMP_JGT_X; > break; > - case BPF_JMP|BPF_JSET|BPF_K: > - ftest->code = BPF_S_JMP_JSET_K; > - break; > - case BPF_JMP|BPF_JSET|BPF_X: > - ftest->code = BPF_S_JMP_JSET_X; > - break; > - > - default: > - return -EINVAL; > } > - > - /* for conditionals both must be safe */ > - switch (ftest->code) { > + code = codes[code]; > + if (!code--) > + return -EINVAL; > + > + /* for conditionals both must be safe */ > + switch (code) { > case BPF_S_JMP_JEQ_K: > case BPF_S_JMP_JEQ_X: > case BPF_S_JMP_JGE_K: > @@ -574,6 +489,7 @@ int sk_chk_filter(struct sock_filter *filter, int flen) > pc + ftest->jf + 1 >= flen) > return -EINVAL; > } > + ftest->code = code; > } > > /* last instruction must be a RET code */ > -- > 1.6.1 > -- > To unsubscribe from this list: send the line "unsubscribe netdev" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html >
On Wed, Nov 17, 2010 at 6:13 AM, Hagen Paul Pfeifer <hagen@jauu.net> wrote: > * Tetsuo Handa | 2010-11-16 22:08:50 [+0900]: > >>--- a/net/core/filter.c >>+++ b/net/core/filter.c >>@@ -383,7 +383,57 @@ EXPORT_SYMBOL(sk_run_filter); >> */ >> int sk_chk_filter(struct sock_filter *filter, int flen) >> { >>- struct sock_filter *ftest; >>+ /* >>+ * Valid instructions are initialized to non-0. >>+ * Invalid instructions are initialized to 0. >>+ */ >>+ static u16 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, > [...] > > Maybe I don't get it, but you increment the opcode by one, but you never > increment the opcode in sk_run_filter() - do I miss something? Did you test > the your patch (a trivial tcpdump rule should be sufficient)? > + code = codes[code]; + if (!code--) + return -EINVAL; But how about this: enum { BPF_S_RET_K = 1,
* Changli Gao | 2010-11-17 07:31:51 [+0800]: >> Maybe I don't get it, but you increment the opcode by one, but you never >> increment the opcode in sk_run_filter() - do I miss something? Did you test >> the your patch (a trivial tcpdump rule should be sufficient)? >> > >+ code = codes[code]; >+ if (!code--) >+ return -EINVAL; Right, temporary in sk_chk_filter() but as I wrote earlier not in sk_run_filter(). >But how about this: > >enum { > BPF_S_RET_K = 1, better. Best regards, Hagen BTW: you can verify your code by construct some artificial filter rules via struct sock_filter { uint16_t code; /* Actual filter code */ uint8_t jt; /* Jump true */ uint8_t jf; /* Jump false */ uint32_t k; /* Generic multiuse field }; and attach them to a socket with setsockopt. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/net/core/filter.c b/net/core/filter.c index 23e9b2a..85be3d8 100644 --- a/net/core/filter.c +++ b/net/core/filter.c @@ -383,7 +383,57 @@ EXPORT_SYMBOL(sk_run_filter); */ int sk_chk_filter(struct sock_filter *filter, int flen) { - struct sock_filter *ftest; + /* + * Valid instructions are initialized to non-0. + * Invalid instructions are initialized to 0. + */ + static u16 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, + }; int pc; if (flen == 0 || flen > BPF_MAXINSNS) @@ -391,135 +441,26 @@ int sk_chk_filter(struct sock_filter *filter, int flen) /* check the filter code now */ for (pc = 0; pc < flen; pc++) { - ftest = &filter[pc]; - - /* Only allow valid instructions */ - switch (ftest->code) { - case BPF_ALU|BPF_ADD|BPF_K: - ftest->code = BPF_S_ALU_ADD_K; - break; - case BPF_ALU|BPF_ADD|BPF_X: - ftest->code = BPF_S_ALU_ADD_X; - break; - case BPF_ALU|BPF_SUB|BPF_K: - ftest->code = BPF_S_ALU_SUB_K; - break; - case BPF_ALU|BPF_SUB|BPF_X: - ftest->code = BPF_S_ALU_SUB_X; - break; - case BPF_ALU|BPF_MUL|BPF_K: - ftest->code = BPF_S_ALU_MUL_K; - break; - case BPF_ALU|BPF_MUL|BPF_X: - ftest->code = BPF_S_ALU_MUL_X; - break; - case BPF_ALU|BPF_DIV|BPF_X: - ftest->code = BPF_S_ALU_DIV_X; - break; - case BPF_ALU|BPF_AND|BPF_K: - ftest->code = BPF_S_ALU_AND_K; - break; - case BPF_ALU|BPF_AND|BPF_X: - ftest->code = BPF_S_ALU_AND_X; - break; - case BPF_ALU|BPF_OR|BPF_K: - ftest->code = BPF_S_ALU_OR_K; - break; - case BPF_ALU|BPF_OR|BPF_X: - ftest->code = BPF_S_ALU_OR_X; - break; - case BPF_ALU|BPF_LSH|BPF_K: - ftest->code = BPF_S_ALU_LSH_K; - break; - case BPF_ALU|BPF_LSH|BPF_X: - ftest->code = BPF_S_ALU_LSH_X; - break; - case BPF_ALU|BPF_RSH|BPF_K: - ftest->code = BPF_S_ALU_RSH_K; - break; - case BPF_ALU|BPF_RSH|BPF_X: - ftest->code = BPF_S_ALU_RSH_X; - break; - case BPF_ALU|BPF_NEG: - ftest->code = BPF_S_ALU_NEG; - break; - case BPF_LD|BPF_W|BPF_ABS: - ftest->code = BPF_S_LD_W_ABS; - break; - case BPF_LD|BPF_H|BPF_ABS: - ftest->code = BPF_S_LD_H_ABS; - break; - case BPF_LD|BPF_B|BPF_ABS: - ftest->code = BPF_S_LD_B_ABS; - break; - case BPF_LD|BPF_W|BPF_LEN: - ftest->code = BPF_S_LD_W_LEN; - break; - case BPF_LD|BPF_W|BPF_IND: - ftest->code = BPF_S_LD_W_IND; - break; - case BPF_LD|BPF_H|BPF_IND: - ftest->code = BPF_S_LD_H_IND; - break; - case BPF_LD|BPF_B|BPF_IND: - ftest->code = BPF_S_LD_B_IND; - break; - case BPF_LD|BPF_IMM: - ftest->code = BPF_S_LD_IMM; - break; - case BPF_LDX|BPF_W|BPF_LEN: - ftest->code = BPF_S_LDX_W_LEN; - break; - case BPF_LDX|BPF_B|BPF_MSH: - ftest->code = BPF_S_LDX_B_MSH; - break; - case BPF_LDX|BPF_IMM: - ftest->code = BPF_S_LDX_IMM; - break; - case BPF_MISC|BPF_TAX: - ftest->code = BPF_S_MISC_TAX; - break; - case BPF_MISC|BPF_TXA: - ftest->code = BPF_S_MISC_TXA; - break; - case BPF_RET|BPF_K: - ftest->code = BPF_S_RET_K; - break; - case BPF_RET|BPF_A: - ftest->code = BPF_S_RET_A; - break; + struct sock_filter *ftest = &filter[pc]; + u16 code = ftest->code; + if (code >= ARRAY_SIZE(codes)) + return 0; /* Some instructions need special checks */ - - /* check for division by zero */ + switch (code) { case BPF_ALU|BPF_DIV|BPF_K: + /* check for division by zero */ if (ftest->k == 0) return -EINVAL; - ftest->code = BPF_S_ALU_DIV_K; break; - - /* check for invalid memory addresses */ case BPF_LD|BPF_MEM: - if (ftest->k >= BPF_MEMWORDS) - return -EINVAL; - ftest->code = BPF_S_LD_MEM; - break; case BPF_LDX|BPF_MEM: - if (ftest->k >= BPF_MEMWORDS) - return -EINVAL; - ftest->code = BPF_S_LDX_MEM; - break; case BPF_ST: - if (ftest->k >= BPF_MEMWORDS) - return -EINVAL; - ftest->code = BPF_S_ST; - break; case BPF_STX: + /* check for invalid memory addresses */ if (ftest->k >= BPF_MEMWORDS) return -EINVAL; - ftest->code = BPF_S_STX; break; - case BPF_JMP|BPF_JA: /* * Note, the large ftest->k might cause loops. @@ -528,40 +469,14 @@ int sk_chk_filter(struct sock_filter *filter, int flen) */ if (ftest->k >= (unsigned)(flen-pc-1)) return -EINVAL; - ftest->code = BPF_S_JMP_JA; - break; - - case BPF_JMP|BPF_JEQ|BPF_K: - ftest->code = BPF_S_JMP_JEQ_K; - break; - case BPF_JMP|BPF_JEQ|BPF_X: - ftest->code = BPF_S_JMP_JEQ_X; - break; - case BPF_JMP|BPF_JGE|BPF_K: - ftest->code = BPF_S_JMP_JGE_K; - break; - case BPF_JMP|BPF_JGE|BPF_X: - ftest->code = BPF_S_JMP_JGE_X; - break; - case BPF_JMP|BPF_JGT|BPF_K: - ftest->code = BPF_S_JMP_JGT_K; - break; - case BPF_JMP|BPF_JGT|BPF_X: - ftest->code = BPF_S_JMP_JGT_X; break; - case BPF_JMP|BPF_JSET|BPF_K: - ftest->code = BPF_S_JMP_JSET_K; - break; - case BPF_JMP|BPF_JSET|BPF_X: - ftest->code = BPF_S_JMP_JSET_X; - break; - - default: - return -EINVAL; } - - /* for conditionals both must be safe */ - switch (ftest->code) { + code = codes[code]; + if (!code--) + return -EINVAL; + + /* for conditionals both must be safe */ + switch (code) { case BPF_S_JMP_JEQ_K: case BPF_S_JMP_JEQ_X: case BPF_S_JMP_JGE_K: @@ -574,6 +489,7 @@ int sk_chk_filter(struct sock_filter *filter, int flen) pc + ftest->jf + 1 >= flen) return -EINVAL; } + ftest->code = code; } /* last instruction must be a RET code */
In the wake of commit 57fe93b3 "filter: make sure filters dont read uninitialized memory", I came up with this patch. I don't know how to test. Please review and do tests. This patch optimizes sk_chk_filter(). Using gcc 4.1.2 on x86_32, the size of net/core/filter.o changed from 7416 bytes to 5260 bytes ("make allnoconfig" + CONFIG_NET=y). By the way, if "struct sock_filter *filter" argument of sk_run_filter() does not change after it was revalidated at sk_chk_filter(), can't we detect and reject "BPF_S_LD_MEM/BPF_S_LDX_MEM before BPF_S_ST/BPF_S_STX" at sk_chk_filter()? ---------------------------------------- From 2bf36130bd4912590b409b47a6a9a82e2884e035 Mon Sep 17 00:00:00 2001 From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Date: Tue, 16 Nov 2010 21:39:50 +0900 Subject: [PATCH] filter: Optimize instruction revalidation code. Since repeating small value to small value conversion using switch() clause's case statement is wasteful, this patch instroduces u16 to u16 mapping table and removes most of case statements. As a result, the size of net/core/filter.o is reduced by about 30% on x86. Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> --- net/core/filter.c | 214 ++++++++++++++++------------------------------------- 1 files changed, 65 insertions(+), 149 deletions(-)