aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>2010-11-16 10:19:51 -0500
committerDavid S. Miller <davem@davemloft.net>2010-11-18 13:58:35 -0500
commitcba328fc5ede9091616e7296483840869b615a46 (patch)
tree1ec43203bc3a3e388b0e85a4865cef4702f1d456
parent9e50e3ac5a5bbb1fd2949bdd57444ad1b93e5f41 (diff)
filter: Optimize instruction revalidation code.
Since repeating u16 value to u8 value conversion using switch() clause's case statement is wasteful, this patch introduces u16 to u8 mapping table and removes most of case statements. As a result, the size of net/core/filter.o is reduced by about 29% on x86. Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Acked-by: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat
-rw-r--r--net/core/filter.c231
1 files changed, 72 insertions, 159 deletions
diff --git a/net/core/filter.c b/net/core/filter.c
index 23e9b2a6b4c8..03dc0710194f 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -383,7 +383,57 @@ EXPORT_SYMBOL(sk_run_filter);
383 */ 383 */
384int sk_chk_filter(struct sock_filter *filter, int flen) 384int sk_chk_filter(struct sock_filter *filter, int flen)
385{ 385{
386 struct sock_filter *ftest; 386 /*
387 * Valid instructions are initialized to non-0.
388 * Invalid instructions are initialized to 0.
389 */
390 static const u8 codes[] = {
391 [BPF_ALU|BPF_ADD|BPF_K] = BPF_S_ALU_ADD_K + 1,
392 [BPF_ALU|BPF_ADD|BPF_X] = BPF_S_ALU_ADD_X + 1,
393 [BPF_ALU|BPF_SUB|BPF_K] = BPF_S_ALU_SUB_K + 1,
394 [BPF_ALU|BPF_SUB|BPF_X] = BPF_S_ALU_SUB_X + 1,
395 [BPF_ALU|BPF_MUL|BPF_K] = BPF_S_ALU_MUL_K + 1,
396 [BPF_ALU|BPF_MUL|BPF_X] = BPF_S_ALU_MUL_X + 1,
397 [BPF_ALU|BPF_DIV|BPF_X] = BPF_S_ALU_DIV_X + 1,
398 [BPF_ALU|BPF_AND|BPF_K] = BPF_S_ALU_AND_K + 1,
399 [BPF_ALU|BPF_AND|BPF_X] = BPF_S_ALU_AND_X + 1,
400 [BPF_ALU|BPF_OR|BPF_K] = BPF_S_ALU_OR_K + 1,
401 [BPF_ALU|BPF_OR|BPF_X] = BPF_S_ALU_OR_X + 1,
402 [BPF_ALU|BPF_LSH|BPF_K] = BPF_S_ALU_LSH_K + 1,
403 [BPF_ALU|BPF_LSH|BPF_X] = BPF_S_ALU_LSH_X + 1,
404 [BPF_ALU|BPF_RSH|BPF_K] = BPF_S_ALU_RSH_K + 1,
405 [BPF_ALU|BPF_RSH|BPF_X] = BPF_S_ALU_RSH_X + 1,
406 [BPF_ALU|BPF_NEG] = BPF_S_ALU_NEG + 1,
407 [BPF_LD|BPF_W|BPF_ABS] = BPF_S_LD_W_ABS + 1,
408 [BPF_LD|BPF_H|BPF_ABS] = BPF_S_LD_H_ABS + 1,
409 [BPF_LD|BPF_B|BPF_ABS] = BPF_S_LD_B_ABS + 1,
410 [BPF_LD|BPF_W|BPF_LEN] = BPF_S_LD_W_LEN + 1,
411 [BPF_LD|BPF_W|BPF_IND] = BPF_S_LD_W_IND + 1,
412 [BPF_LD|BPF_H|BPF_IND] = BPF_S_LD_H_IND + 1,
413 [BPF_LD|BPF_B|BPF_IND] = BPF_S_LD_B_IND + 1,
414 [BPF_LD|BPF_IMM] = BPF_S_LD_IMM + 1,
415 [BPF_LDX|BPF_W|BPF_LEN] = BPF_S_LDX_W_LEN + 1,
416 [BPF_LDX|BPF_B|BPF_MSH] = BPF_S_LDX_B_MSH + 1,
417 [BPF_LDX|BPF_IMM] = BPF_S_LDX_IMM + 1,
418 [BPF_MISC|BPF_TAX] = BPF_S_MISC_TAX + 1,
419 [BPF_MISC|BPF_TXA] = BPF_S_MISC_TXA + 1,
420 [BPF_RET|BPF_K] = BPF_S_RET_K + 1,
421 [BPF_RET|BPF_A] = BPF_S_RET_A + 1,
422 [BPF_ALU|BPF_DIV|BPF_K] = BPF_S_ALU_DIV_K + 1,
423 [BPF_LD|BPF_MEM] = BPF_S_LD_MEM + 1,
424 [BPF_LDX|BPF_MEM] = BPF_S_LDX_MEM + 1,
425 [BPF_ST] = BPF_S_ST + 1,
426 [BPF_STX] = BPF_S_STX + 1,
427 [BPF_JMP|BPF_JA] = BPF_S_JMP_JA + 1,
428 [BPF_JMP|BPF_JEQ|BPF_K] = BPF_S_JMP_JEQ_K + 1,
429 [BPF_JMP|BPF_JEQ|BPF_X] = BPF_S_JMP_JEQ_X + 1,
430 [BPF_JMP|BPF_JGE|BPF_K] = BPF_S_JMP_JGE_K + 1,
431 [BPF_JMP|BPF_JGE|BPF_X] = BPF_S_JMP_JGE_X + 1,
432 [BPF_JMP|BPF_JGT|BPF_K] = BPF_S_JMP_JGT_K + 1,
433 [BPF_JMP|BPF_JGT|BPF_X] = BPF_S_JMP_JGT_X + 1,
434 [BPF_JMP|BPF_JSET|BPF_K] = BPF_S_JMP_JSET_K + 1,
435 [BPF_JMP|BPF_JSET|BPF_X] = BPF_S_JMP_JSET_X + 1,
436 };
387 int pc; 437 int pc;
388 438
389 if (flen == 0 || flen > BPF_MAXINSNS) 439 if (flen == 0 || flen > BPF_MAXINSNS)
@@ -391,136 +441,31 @@ int sk_chk_filter(struct sock_filter *filter, int flen)
391 441
392 /* check the filter code now */ 442 /* check the filter code now */
393 for (pc = 0; pc < flen; pc++) { 443 for (pc = 0; pc < flen; pc++) {
394 ftest = &filter[pc]; 444 struct sock_filter *ftest = &filter[pc];
395 445 u16 code = ftest->code;
396 /* Only allow valid instructions */
397 switch (ftest->code) {
398 case BPF_ALU|BPF_ADD|BPF_K:
399 ftest->code = BPF_S_ALU_ADD_K;
400 break;
401 case BPF_ALU|BPF_ADD|BPF_X:
402 ftest->code = BPF_S_ALU_ADD_X;
403 break;
404 case BPF_ALU|BPF_SUB|BPF_K:
405 ftest->code = BPF_S_ALU_SUB_K;
406 break;
407 case BPF_ALU|BPF_SUB|BPF_X:
408 ftest->code = BPF_S_ALU_SUB_X;
409 break;
410 case BPF_ALU|BPF_MUL|BPF_K:
411 ftest->code = BPF_S_ALU_MUL_K;
412 break;
413 case BPF_ALU|BPF_MUL|BPF_X:
414 ftest->code = BPF_S_ALU_MUL_X;
415 break;
416 case BPF_ALU|BPF_DIV|BPF_X:
417 ftest->code = BPF_S_ALU_DIV_X;
418 break;
419 case BPF_ALU|BPF_AND|BPF_K:
420 ftest->code = BPF_S_ALU_AND_K;
421 break;
422 case BPF_ALU|BPF_AND|BPF_X:
423 ftest->code = BPF_S_ALU_AND_X;
424 break;
425 case BPF_ALU|BPF_OR|BPF_K:
426 ftest->code = BPF_S_ALU_OR_K;
427 break;
428 case BPF_ALU|BPF_OR|BPF_X:
429 ftest->code = BPF_S_ALU_OR_X;
430 break;
431 case BPF_ALU|BPF_LSH|BPF_K:
432 ftest->code = BPF_S_ALU_LSH_K;
433 break;
434 case BPF_ALU|BPF_LSH|BPF_X:
435 ftest->code = BPF_S_ALU_LSH_X;
436 break;
437 case BPF_ALU|BPF_RSH|BPF_K:
438 ftest->code = BPF_S_ALU_RSH_K;
439 break;
440 case BPF_ALU|BPF_RSH|BPF_X:
441 ftest->code = BPF_S_ALU_RSH_X;
442 break;
443 case BPF_ALU|BPF_NEG:
444 ftest->code = BPF_S_ALU_NEG;
445 break;
446 case BPF_LD|BPF_W|BPF_ABS:
447 ftest->code = BPF_S_LD_W_ABS;
448 break;
449 case BPF_LD|BPF_H|BPF_ABS:
450 ftest->code = BPF_S_LD_H_ABS;
451 break;
452 case BPF_LD|BPF_B|BPF_ABS:
453 ftest->code = BPF_S_LD_B_ABS;
454 break;
455 case BPF_LD|BPF_W|BPF_LEN:
456 ftest->code = BPF_S_LD_W_LEN;
457 break;
458 case BPF_LD|BPF_W|BPF_IND:
459 ftest->code = BPF_S_LD_W_IND;
460 break;
461 case BPF_LD|BPF_H|BPF_IND:
462 ftest->code = BPF_S_LD_H_IND;
463 break;
464 case BPF_LD|BPF_B|BPF_IND:
465 ftest->code = BPF_S_LD_B_IND;
466 break;
467 case BPF_LD|BPF_IMM:
468 ftest->code = BPF_S_LD_IMM;
469 break;
470 case BPF_LDX|BPF_W|BPF_LEN:
471 ftest->code = BPF_S_LDX_W_LEN;
472 break;
473 case BPF_LDX|BPF_B|BPF_MSH:
474 ftest->code = BPF_S_LDX_B_MSH;
475 break;
476 case BPF_LDX|BPF_IMM:
477 ftest->code = BPF_S_LDX_IMM;
478 break;
479 case BPF_MISC|BPF_TAX:
480 ftest->code = BPF_S_MISC_TAX;
481 break;
482 case BPF_MISC|BPF_TXA:
483 ftest->code = BPF_S_MISC_TXA;
484 break;
485 case BPF_RET|BPF_K:
486 ftest->code = BPF_S_RET_K;
487 break;
488 case BPF_RET|BPF_A:
489 ftest->code = BPF_S_RET_A;
490 break;
491 446
447 if (code >= ARRAY_SIZE(codes))
448 return -EINVAL;
449 code = codes[code];
450 /* Undo the '+ 1' in codes[] after validation. */
451 if (!code--)
452 return -EINVAL;
492 /* Some instructions need special checks */ 453 /* Some instructions need special checks */
493 454 switch (code) {
455 case BPF_S_ALU_DIV_K:
494 /* check for division by zero */ 456 /* check for division by zero */
495 case BPF_ALU|BPF_DIV|BPF_K:
496 if (ftest->k == 0) 457 if (ftest->k == 0)
497 return -EINVAL; 458 return -EINVAL;
498 ftest->code = BPF_S_ALU_DIV_K;
499 break; 459 break;
500 460 case BPF_S_LD_MEM:
501 /* check for invalid memory addresses */ 461 case BPF_S_LDX_MEM:
502 case BPF_LD|BPF_MEM: 462 case BPF_S_ST:
503 if (ftest->k >= BPF_MEMWORDS) 463 case BPF_S_STX:
504 return -EINVAL; 464 /* check for invalid memory addresses */
505 ftest->code = BPF_S_LD_MEM;
506 break;
507 case BPF_LDX|BPF_MEM:
508 if (ftest->k >= BPF_MEMWORDS)
509 return -EINVAL;
510 ftest->code = BPF_S_LDX_MEM;
511 break;
512 case BPF_ST:
513 if (ftest->k >= BPF_MEMWORDS)
514 return -EINVAL;
515 ftest->code = BPF_S_ST;
516 break;
517 case BPF_STX:
518 if (ftest->k >= BPF_MEMWORDS) 465 if (ftest->k >= BPF_MEMWORDS)
519 return -EINVAL; 466 return -EINVAL;
520 ftest->code = BPF_S_STX;
521 break; 467 break;
522 468 case BPF_S_JMP_JA:
523 case BPF_JMP|BPF_JA:
524 /* 469 /*
525 * Note, the large ftest->k might cause loops. 470 * Note, the large ftest->k might cause loops.
526 * Compare this with conditional jumps below, 471 * Compare this with conditional jumps below,
@@ -528,40 +473,7 @@ int sk_chk_filter(struct sock_filter *filter, int flen)
528 */ 473 */
529 if (ftest->k >= (unsigned)(flen-pc-1)) 474 if (ftest->k >= (unsigned)(flen-pc-1))
530 return -EINVAL; 475 return -EINVAL;
531 ftest->code = BPF_S_JMP_JA;
532 break;
533
534 case BPF_JMP|BPF_JEQ|BPF_K:
535 ftest->code = BPF_S_JMP_JEQ_K;
536 break;
537 case BPF_JMP|BPF_JEQ|BPF_X:
538 ftest->code = BPF_S_JMP_JEQ_X;
539 break; 476 break;
540 case BPF_JMP|BPF_JGE|BPF_K:
541 ftest->code = BPF_S_JMP_JGE_K;
542 break;
543 case BPF_JMP|BPF_JGE|BPF_X:
544 ftest->code = BPF_S_JMP_JGE_X;
545 break;
546 case BPF_JMP|BPF_JGT|BPF_K:
547 ftest->code = BPF_S_JMP_JGT_K;
548 break;
549 case BPF_JMP|BPF_JGT|BPF_X:
550 ftest->code = BPF_S_JMP_JGT_X;
551 break;
552 case BPF_JMP|BPF_JSET|BPF_K:
553 ftest->code = BPF_S_JMP_JSET_K;
554 break;
555 case BPF_JMP|BPF_JSET|BPF_X:
556 ftest->code = BPF_S_JMP_JSET_X;
557 break;
558
559 default:
560 return -EINVAL;
561 }
562
563 /* for conditionals both must be safe */
564 switch (ftest->code) {
565 case BPF_S_JMP_JEQ_K: 477 case BPF_S_JMP_JEQ_K:
566 case BPF_S_JMP_JEQ_X: 478 case BPF_S_JMP_JEQ_X:
567 case BPF_S_JMP_JGE_K: 479 case BPF_S_JMP_JGE_K:
@@ -570,10 +482,13 @@ int sk_chk_filter(struct sock_filter *filter, int flen)
570 case BPF_S_JMP_JGT_X: 482 case BPF_S_JMP_JGT_X:
571 case BPF_S_JMP_JSET_X: 483 case BPF_S_JMP_JSET_X:
572 case BPF_S_JMP_JSET_K: 484 case BPF_S_JMP_JSET_K:
485 /* for conditionals both must be safe */
573 if (pc + ftest->jt + 1 >= flen || 486 if (pc + ftest->jt + 1 >= flen ||
574 pc + ftest->jf + 1 >= flen) 487 pc + ftest->jf + 1 >= flen)
575 return -EINVAL; 488 return -EINVAL;
489 break;
576 } 490 }
491 ftest->code = code;
577 } 492 }
578 493
579 /* last instruction must be a RET code */ 494 /* last instruction must be a RET code */
@@ -581,10 +496,8 @@ int sk_chk_filter(struct sock_filter *filter, int flen)
581 case BPF_S_RET_K: 496 case BPF_S_RET_K:
582 case BPF_S_RET_A: 497 case BPF_S_RET_A:
583 return 0; 498 return 0;
584 break; 499 }
585 default: 500 return -EINVAL;
586 return -EINVAL;
587 }
588} 501}
589EXPORT_SYMBOL(sk_chk_filter); 502EXPORT_SYMBOL(sk_chk_filter);
590 503
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-18 19:59:39 -0500