diff options
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r-- | net/ipv4/fib_trie.c | 119 |
1 files changed, 57 insertions, 62 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 6f818cc7efd0..914a4c2aae42 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c | |||
@@ -167,8 +167,8 @@ static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); | |||
167 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); | 167 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); |
168 | static int tnode_child_length(struct tnode *tn); | 168 | static int tnode_child_length(struct tnode *tn); |
169 | static struct node *resize(struct trie *t, struct tnode *tn); | 169 | static struct node *resize(struct trie *t, struct tnode *tn); |
170 | static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err); | 170 | static struct tnode *inflate(struct trie *t, struct tnode *tn); |
171 | static struct tnode *halve(struct trie *t, struct tnode *tn, int *err); | 171 | static struct tnode *halve(struct trie *t, struct tnode *tn); |
172 | static void tnode_free(struct tnode *tn); | 172 | static void tnode_free(struct tnode *tn); |
173 | static void trie_dump_seq(struct seq_file *seq, struct trie *t); | 173 | static void trie_dump_seq(struct seq_file *seq, struct trie *t); |
174 | extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio); | 174 | extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio); |
@@ -457,6 +457,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
457 | { | 457 | { |
458 | int i; | 458 | int i; |
459 | int err = 0; | 459 | int err = 0; |
460 | struct tnode *old_tn; | ||
460 | 461 | ||
461 | if (!tn) | 462 | if (!tn) |
462 | return NULL; | 463 | return NULL; |
@@ -559,9 +560,10 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
559 | 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= | 560 | 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= |
560 | inflate_threshold * tnode_child_length(tn))) { | 561 | inflate_threshold * tnode_child_length(tn))) { |
561 | 562 | ||
562 | tn = inflate(t, tn, &err); | 563 | old_tn = tn; |
563 | 564 | tn = inflate(t, tn); | |
564 | if (err) { | 565 | if (IS_ERR(tn)) { |
566 | tn = old_tn; | ||
565 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 567 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
566 | t->stats.resize_node_skipped++; | 568 | t->stats.resize_node_skipped++; |
567 | #endif | 569 | #endif |
@@ -581,9 +583,10 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
581 | 100 * (tnode_child_length(tn) - tn->empty_children) < | 583 | 100 * (tnode_child_length(tn) - tn->empty_children) < |
582 | halve_threshold * tnode_child_length(tn)) { | 584 | halve_threshold * tnode_child_length(tn)) { |
583 | 585 | ||
584 | tn = halve(t, tn, &err); | 586 | old_tn = tn; |
585 | 587 | tn = halve(t, tn); | |
586 | if (err) { | 588 | if (IS_ERR(tn)) { |
589 | tn = old_tn; | ||
587 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 590 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
588 | t->stats.resize_node_skipped++; | 591 | t->stats.resize_node_skipped++; |
589 | #endif | 592 | #endif |
@@ -618,7 +621,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
618 | return (struct node *) tn; | 621 | return (struct node *) tn; |
619 | } | 622 | } |
620 | 623 | ||
621 | static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) | 624 | static struct tnode *inflate(struct trie *t, struct tnode *tn) |
622 | { | 625 | { |
623 | struct tnode *inode; | 626 | struct tnode *inode; |
624 | struct tnode *oldtnode = tn; | 627 | struct tnode *oldtnode = tn; |
@@ -629,10 +632,8 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) | |||
629 | 632 | ||
630 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); | 633 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); |
631 | 634 | ||
632 | if (!tn) { | 635 | if (!tn) |
633 | *err = -ENOMEM; | 636 | return ERR_PTR(-ENOMEM); |
634 | return oldtnode; | ||
635 | } | ||
636 | 637 | ||
637 | /* | 638 | /* |
638 | * Preallocate and store tnodes before the actual work so we | 639 | * Preallocate and store tnodes before the actual work so we |
@@ -653,39 +654,22 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) | |||
653 | 654 | ||
654 | left = tnode_new(inode->key&(~m), inode->pos + 1, | 655 | left = tnode_new(inode->key&(~m), inode->pos + 1, |
655 | inode->bits - 1); | 656 | inode->bits - 1); |
656 | 657 | if (!left) | |
657 | if (!left) { | 658 | goto nomem; |
658 | *err = -ENOMEM; | ||
659 | break; | ||
660 | } | ||
661 | 659 | ||
662 | right = tnode_new(inode->key|m, inode->pos + 1, | 660 | right = tnode_new(inode->key|m, inode->pos + 1, |
663 | inode->bits - 1); | 661 | inode->bits - 1); |
664 | 662 | ||
665 | if (!right) { | 663 | if (!right) { |
666 | *err = -ENOMEM; | 664 | tnode_free(left); |
667 | break; | 665 | goto nomem; |
668 | } | 666 | } |
669 | 667 | ||
670 | put_child(t, tn, 2*i, (struct node *) left); | 668 | put_child(t, tn, 2*i, (struct node *) left); |
671 | put_child(t, tn, 2*i+1, (struct node *) right); | 669 | put_child(t, tn, 2*i+1, (struct node *) right); |
672 | } | 670 | } |
673 | } | 671 | } |
674 | 672 | ||
675 | if (*err) { | ||
676 | int size = tnode_child_length(tn); | ||
677 | int j; | ||
678 | |||
679 | for (j = 0; j < size; j++) | ||
680 | if (tn->child[j]) | ||
681 | tnode_free((struct tnode *)tn->child[j]); | ||
682 | |||
683 | tnode_free(tn); | ||
684 | |||
685 | *err = -ENOMEM; | ||
686 | return oldtnode; | ||
687 | } | ||
688 | |||
689 | for (i = 0; i < olen; i++) { | 673 | for (i = 0; i < olen; i++) { |
690 | struct node *node = tnode_get_child(oldtnode, i); | 674 | struct node *node = tnode_get_child(oldtnode, i); |
691 | struct tnode *left, *right; | 675 | struct tnode *left, *right; |
@@ -763,9 +747,22 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err) | |||
763 | } | 747 | } |
764 | tnode_free(oldtnode); | 748 | tnode_free(oldtnode); |
765 | return tn; | 749 | return tn; |
750 | nomem: | ||
751 | { | ||
752 | int size = tnode_child_length(tn); | ||
753 | int j; | ||
754 | |||
755 | for(j = 0; j < size; j++) | ||
756 | if (tn->child[j]) | ||
757 | tnode_free((struct tnode *)tn->child[j]); | ||
758 | |||
759 | tnode_free(tn); | ||
760 | |||
761 | return ERR_PTR(-ENOMEM); | ||
762 | } | ||
766 | } | 763 | } |
767 | 764 | ||
768 | static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) | 765 | static struct tnode *halve(struct trie *t, struct tnode *tn) |
769 | { | 766 | { |
770 | struct tnode *oldtnode = tn; | 767 | struct tnode *oldtnode = tn; |
771 | struct node *left, *right; | 768 | struct node *left, *right; |
@@ -776,10 +773,8 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) | |||
776 | 773 | ||
777 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); | 774 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); |
778 | 775 | ||
779 | if (!tn) { | 776 | if (!tn) |
780 | *err = -ENOMEM; | 777 | return ERR_PTR(-ENOMEM); |
781 | return oldtnode; | ||
782 | } | ||
783 | 778 | ||
784 | /* | 779 | /* |
785 | * Preallocate and store tnodes before the actual work so we | 780 | * Preallocate and store tnodes before the actual work so we |
@@ -794,29 +789,16 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) | |||
794 | 789 | ||
795 | /* Two nonempty children */ | 790 | /* Two nonempty children */ |
796 | if (left && right) { | 791 | if (left && right) { |
797 | struct tnode *newBinNode = | 792 | struct tnode *newn; |
798 | tnode_new(left->key, tn->pos + tn->bits, 1); | 793 | |
799 | 794 | newn = tnode_new(left->key, tn->pos + tn->bits, 1); | |
800 | if (!newBinNode) { | 795 | |
801 | *err = -ENOMEM; | 796 | if (!newn) |
802 | break; | 797 | goto nomem; |
803 | } | 798 | |
804 | put_child(t, tn, i/2, (struct node *)newBinNode); | 799 | put_child(t, tn, i/2, (struct node *)newn); |
805 | } | 800 | } |
806 | } | ||
807 | 801 | ||
808 | if (*err) { | ||
809 | int size = tnode_child_length(tn); | ||
810 | int j; | ||
811 | |||
812 | for (j = 0; j < size; j++) | ||
813 | if (tn->child[j]) | ||
814 | tnode_free((struct tnode *)tn->child[j]); | ||
815 | |||
816 | tnode_free(tn); | ||
817 | |||
818 | *err = -ENOMEM; | ||
819 | return oldtnode; | ||
820 | } | 802 | } |
821 | 803 | ||
822 | for (i = 0; i < olen; i += 2) { | 804 | for (i = 0; i < olen; i += 2) { |
@@ -850,6 +832,19 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err) | |||
850 | } | 832 | } |
851 | tnode_free(oldtnode); | 833 | tnode_free(oldtnode); |
852 | return tn; | 834 | return tn; |
835 | nomem: | ||
836 | { | ||
837 | int size = tnode_child_length(tn); | ||
838 | int j; | ||
839 | |||
840 | for(j = 0; j < size; j++) | ||
841 | if (tn->child[j]) | ||
842 | tnode_free((struct tnode *)tn->child[j]); | ||
843 | |||
844 | tnode_free(tn); | ||
845 | |||
846 | return ERR_PTR(-ENOMEM); | ||
847 | } | ||
853 | } | 848 | } |
854 | 849 | ||
855 | static void trie_init(struct trie *t) | 850 | static void trie_init(struct trie *t) |