diff mbox

rib_trie / Fix inflate_threshold_root. Now=15 size=11 bits

Message ID 20090628213602.GA4584@ami.dom.local
State RFC, archived
Delegated to: David Miller
Headers show

Commit Message

Jarek Poplawski June 28, 2009, 9:36 p.m. UTC 
To David Miller:
since among patches tested negatively by Pawel are current 2 fixes
from 2.6.31-rc, I hope they weren't sent to -stable yet. Otherwise,
please withdraw them until they are tested alone. Thanks.

To Pawel:
On Sun, Jun 28, 2009 at 05:48:19PM +0200, Paweł Staszewski wrote:
>
> After apply this patch something is wrong
>
> Traffic is not forwarded
> no info in dmesg / no info from bgp
> and also i can't connect to bgpd process
>
> I revert kernel to past version with first Jarek patch
>

Since checking this can take time I attach here a patch with only
changes which are currently in 2.6.31-rc. Of course, this part can be
broken as well, so it's up to you: if you could try it with caution
somewhere it would be very helpful; otherwise don't bother.

It could be applied to 2.6.29 with or without this currently working
patch.

Thanks,
Jarek P.
--- (for 2.6.29.x, .28 or .27)


--
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

Comments

Paweł Staszewski June 29, 2009, 8:08 a.m. UTC | #1 
Jarek Poplawski pisze:
> To David Miller:
> since among patches tested negatively by Pawel are current 2 fixes
> from 2.6.31-rc, I hope they weren't sent to -stable yet. Otherwise,
> please withdraw them until they are tested alone. Thanks.
>
> To Pawel:
> On Sun, Jun 28, 2009 at 05:48:19PM +0200, Paweł Staszewski wrote:
>   
>> After apply this patch something is wrong
>>
>> Traffic is not forwarded
>> no info in dmesg / no info from bgp
>> and also i can't connect to bgpd process
>>
>> I revert kernel to past version with first Jarek patch
>>
>>     
>
> Since checking this can take time I attach here a patch with only
> changes which are currently in 2.6.31-rc. Of course, this part can be
> broken as well, so it's up to you: if you could try it with caution
> somewhere it would be very helpful; otherwise don't bother.
>
> It could be applied to 2.6.29 with or without this currently working
> patch.
>
>   

Ok.
I applied this patch 15mins ago to 2.6.29.5 and now it's working - 
traffic is forwarded.

Some fib_triestats
cat /proc/net/fib_triestat
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
        Aver depth:     2.29
        Max depth:      6
        Leaves:         277015
        Prefixes:       290493
        Internal nodes: 67115
          1: 35733  2: 13635  3: 9544  4: 4832  5: 2239  6: 1125  7: 5  
9: 1  18: 1
        Pointers: 686614
Null ptrs: 342485
Total size: 18396  kB

Counters:
---------
gets = 3956301
backtracks = 192497
semantic match passed = 3895955
semantic match miss = 133
null node hit= 4306948
skipped node resize = 0

Local:
        Aver depth:     3.75
        Max depth:      5
        Leaves:         12
        Prefixes:       13
        Internal nodes: 10
          1: 9  2: 1
        Pointers: 22
Null ptrs: 1
Total size: 2  kB

Counters:
---------
gets = 3960981
backtracks = 2152441
semantic match passed = 4757
semantic match miss = 0
null node hit= 194997
skipped node resize = 0



> Thanks,
> Jarek P.
> --- (for 2.6.29.x, .28 or .27)
>
> diff -Nurp a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
> --- a/net/ipv4/fib_trie.c	2009-06-27 20:25:06.000000000 +0200
> +++ b/net/ipv4/fib_trie.c	2009-06-28 23:06:02.000000000 +0200
> @@ -123,6 +123,7 @@ struct tnode {
>  	union {
>  		struct rcu_head rcu;
>  		struct work_struct work;
> +		struct tnode *tnode_free;
>  	};
>  	struct node *child[0];
>  };
> @@ -161,6 +162,8 @@ static void tnode_put_child_reorg(struct
>  static struct node *resize(struct trie *t, struct tnode *tn);
>  static struct tnode *inflate(struct trie *t, struct tnode *tn);
>  static struct tnode *halve(struct trie *t, struct tnode *tn);
> +/* tnodes to free after resize(); protected by RTNL */
> +static struct tnode *tnode_free_head;
>  
>  static struct kmem_cache *fn_alias_kmem __read_mostly;
>  static struct kmem_cache *trie_leaf_kmem __read_mostly;
> @@ -385,6 +388,24 @@ static inline void tnode_free(struct tno
>  		call_rcu(&tn->rcu, __tnode_free_rcu);
>  }
>  
> +static void tnode_free_safe(struct tnode *tn)
> +{
> +	BUG_ON(IS_LEAF(tn));
> +	tn->tnode_free = tnode_free_head;
> +	tnode_free_head = tn;
> +}
> +
> +static void tnode_free_flush(void)
> +{
> +	struct tnode *tn;
> +
> +	while ((tn = tnode_free_head)) {
> +		tnode_free_head = tn->tnode_free;
> +		tn->tnode_free = NULL;
> +		tnode_free(tn);
> +	}
> +}
> +
>  static struct leaf *leaf_new(void)
>  {
>  	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
> @@ -495,7 +516,7 @@ static struct node *resize(struct trie *
>  
>  	/* No children */
>  	if (tn->empty_children == tnode_child_length(tn)) {
> -		tnode_free(tn);
> +		tnode_free_safe(tn);
>  		return NULL;
>  	}
>  	/* One child */
> @@ -509,7 +530,7 @@ static struct node *resize(struct trie *
>  
>  			/* compress one level */
>  			node_set_parent(n, NULL);
> -			tnode_free(tn);
> +			tnode_free_safe(tn);
>  			return n;
>  		}
>  	/*
> @@ -670,7 +691,7 @@ static struct node *resize(struct trie *
>  			/* compress one level */
>  
>  			node_set_parent(n, NULL);
> -			tnode_free(tn);
> +			tnode_free_safe(tn);
>  			return n;
>  		}
>  
> @@ -756,7 +777,7 @@ static struct tnode *inflate(struct trie
>  			put_child(t, tn, 2*i, inode->child[0]);
>  			put_child(t, tn, 2*i+1, inode->child[1]);
>  
> -			tnode_free(inode);
> +			tnode_free_safe(inode);
>  			continue;
>  		}
>  
> @@ -801,9 +822,9 @@ static struct tnode *inflate(struct trie
>  		put_child(t, tn, 2*i, resize(t, left));
>  		put_child(t, tn, 2*i+1, resize(t, right));
>  
> -		tnode_free(inode);
> +		tnode_free_safe(inode);
>  	}
> -	tnode_free(oldtnode);
> +	tnode_free_safe(oldtnode);
>  	return tn;
>  nomem:
>  	{
> @@ -885,7 +906,7 @@ static struct tnode *halve(struct trie *
>  		put_child(t, newBinNode, 1, right);
>  		put_child(t, tn, i/2, resize(t, newBinNode));
>  	}
> -	tnode_free(oldtnode);
> +	tnode_free_safe(oldtnode);
>  	return tn;
>  nomem:
>  	{
> @@ -983,12 +1004,14 @@ fib_find_node(struct trie *t, u32 key)
>  	return NULL;
>  }
>  
> -static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
> +static void trie_rebalance(struct trie *t, struct tnode *tn)
>  {
>  	int wasfull;
> -	t_key cindex, key = tn->key;
> +	t_key cindex, key;
>  	struct tnode *tp;
>  
> +	key = tn->key;
> +
>  	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
>  		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
>  		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
> @@ -998,6 +1021,7 @@ static struct node *trie_rebalance(struc
>  				      (struct node *)tn, wasfull);
>  
>  		tp = node_parent((struct node *) tn);
> +		tnode_free_flush();
>  		if (!tp)
>  			break;
>  		tn = tp;
> @@ -1007,7 +1031,10 @@ static struct node *trie_rebalance(struc
>  	if (IS_TNODE(tn))
>  		tn = (struct tnode *)resize(t, (struct tnode *)tn);
>  
> -	return (struct node *)tn;
> +	rcu_assign_pointer(t->trie, (struct node *)tn);
> +	tnode_free_flush();
> +
> +	return;
>  }
>  
>  /* only used from updater-side */
> @@ -1155,7 +1182,7 @@ static struct list_head *fib_insert_node
>  
>  	/* Rebalance the trie */
>  
> -	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
> +	trie_rebalance(t, tp);
>  done:
>  	return fa_head;
>  }
> @@ -1575,7 +1602,7 @@ static void trie_leaf_remove(struct trie
>  	if (tp) {
>  		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
>  		put_child(t, (struct tnode *)tp, cindex, NULL);
> -		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
> +		trie_rebalance(t, tp);
>  	} else
>  		rcu_assign_pointer(t->trie, NULL);
>  
>
>
>
>   

--
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
Paweł Staszewski June 29, 2009, 8:47 a.m. UTC | #2 
But
With all this patches i have the same problem with CPU load
Every time when route cache entries are purged cpu load is increasing 
from 1% to 40 / 80% it depends

I see that on 64bit machine when route cache entries are going down i 
have almost 80% load on each cpu where ethernet card is binded by 
smp_affinity
But on 32bit machine cpu load reported by mpstat is half that on 64bit 
machine
here is example from 32bit machine ( mpstat + rtstat -k entries )

Linux 2.6.29.5 (TM_02_C1)       06/29/09        _i686_  (2 CPU)

12:36:54     CPU    %usr   %nice    %sys %iowait    %irq   %soft  
%steal  %guest   %idle        RT CACHE ENTRIES (from rtstat)
12:36:57     all    0.00    0.00    0.00    0.00    1.51   15.08    
0.00    0.00   83.42        83346
12:36:58     all    0.00    0.00    0.00    0.00    1.01    7.58    
0.00    0.00   91.41        85988
12:36:59     all    0.00    0.00    0.00    0.00    0.50    1.01    
0.00    0.00   98.49        89979
12:37:00     all    0.00    0.00    0.50    0.00    0.00    1.51    
0.00    0.00   97.99        93652
12:37:01     all    0.00    0.00    0.00    0.00    0.00    2.01    
0.00    0.00   97.99        96533
12:37:02     all    0.00    0.00    0.00    0.00    0.51    1.01    
0.00    0.00   98.48        99451
12:37:03     all    0.00    0.00    0.00    0.00    0.00    2.49    
0.00    0.00   97.51        102018
12:37:04     all    0.00    0.00    0.00    0.00    0.00    1.52    
0.00    0.00   98.48        104153
12:37:05     all    0.00    0.00    0.00    0.00    0.00    1.01    
0.00    0.00   98.99        105979
12:37:06     all    0.00    0.00    0.00    0.00    0.00    1.01    
0.00    0.00   98.99        107684
12:37:07     all    0.00    0.00    0.00    0.00    0.00    1.53    
0.00    0.00   98.47        109070
12:37:08     all    0.00    0.00    0.00    0.00    0.00    1.51    
0.00    0.00   98.49        110462
12:37:09     all    0.00    0.00    0.00    0.00    0.00    1.52    
0.00    0.00   98.48        112301
12:37:10     all    0.00    0.00    0.00    0.00    2.00   20.00    
0.00    0.00   78.00        111535
12:37:11     all    0.00    0.00    0.00    0.00    2.49   34.33    
0.00    0.00   63.18        108659
12:37:12     all    0.00    0.00    0.00    0.00    3.03   28.28    
0.00    0.00   68.69        105534
12:37:13     all    0.00    0.00    0.00    0.00    3.98   30.85    
0.00    0.00   65.17        103341
12:37:14     all    0.00    0.00    0.00    0.00    4.50   30.50    
0.00    0.00   65.00        101307
12:37:15     all    5.56    0.00    0.00    0.00    1.52   28.79    
0.00    0.00   64.14        97435
12:37:16     all   11.39    0.00    0.50    0.00    4.95   30.69    
0.00    0.00   52.48        93908
12:37:17     all    1.51    0.00    0.00    0.00    1.01   27.64    
0.00    0.00   69.85        90229
12:37:18     all    0.00    0.00    0.00    0.00    2.99   27.36    
0.00    0.00   69.65        87030
12:37:19     all    0.00    0.00    0.00    0.00    3.02   29.65    
0.00    0.00   67.34        84324
12:37:20     all    0.00    0.00    0.00    0.00    2.99   30.35    
0.00    0.00   66.67        82167
12:37:21     all    0.00    0.00    0.00    0.00    1.98   31.68    
0.00    0.00   66.34        80121
12:37:22     all    0.00    0.00    0.00    0.00    1.51   30.65    
0.00    0.00   67.84        77850
12:37:23     all    0.00    0.00    0.00    0.00    2.50   28.50    
0.00    0.00   69.00        76005
12:37:24     all    0.00    0.00    0.00    0.00    1.98   23.27    
0.00    0.00   74.75        74538
12:37:25     all    0.00    0.00    0.49    0.00    2.93   22.44    
0.00    0.00   74.15        76923
12:37:26     all    0.00    0.00    0.00    0.00    1.51   15.58    
0.00    0.00   82.91        79396
12:37:27     all    0.00    0.00    0.00    0.00    0.50    7.96    
0.00    0.00   91.54        81835
12:37:28     all    0.00    0.00    0.00    0.00    0.50    3.52    
0.00    0.00   95.98        84169
12:37:29     all    0.00    0.00    0.00    0.00    0.00    2.02    
0.00    0.00   97.98        87740
12:37:30     all    0.00    0.00    0.00    0.00    0.51    1.52    
0.00    0.00   97.98        91152
12:37:31     all    0.00    0.00    0.00    0.00    0.00    1.99    
0.00    0.00   98.01        94102
12:37:32     all    0.00    0.00    0.00    0.00    0.00    1.52    
0.00    0.00   98.48        97032
12:37:33     all    0.00    0.00    0.00    0.00    0.00    0.50    
0.00    0.00   99.50        99685
12:37:34     all    0.00    0.00    0.00    0.00    0.00    1.00    
0.00    0.00   99.00        101970
12:37:35     all    0.00    0.00    0.00    0.00    0.50    1.00    
0.00    0.00   98.50        103814
12:37:36     all    0.00    0.00    0.00    0.00    0.00    1.52    
0.00    0.00   98.48        104793
12:37:37     all    0.00    0.00    0.00    0.00    0.00    1.01    
0.00    0.00   98.99        106214
12:37:38     all    0.00    0.00    0.00    0.00    0.50    1.01    
0.00    0.00   98.49        107300
12:37:39     all    0.00    0.00    0.00    0.00    0.00   13.00    
0.00    0.00   87.00        111951
12:37:40     all    0.00    0.00    0.00    0.00    2.50   29.50    
0.00    0.00   68.00        111215
12:37:41     all    0.00    0.00    0.00    0.00    2.01   30.65    
0.00    0.00   67.34        108023
12:37:42     all    0.00    0.00    0.00    0.00    2.99   29.85    
0.00    0.00   67.16        104751
12:37:43     all    0.00    0.00    0.00    0.00    2.00   31.00    
0.00    0.00   67.00        100827
12:37:44     all    0.00    0.00    0.00    0.00    3.00   27.00    
0.00    0.00   70.00        97184
12:37:45     all    0.00    0.00    0.00    0.00    2.50   29.00    
0.00    0.00   68.50        93904
12:37:46     all    0.00    0.00    0.00    0.00    3.02   30.15    
0.00    0.00   66.83        90979
12:37:47     all    0.00    0.00    0.00    0.00    2.49   27.86    
0.00    0.00   69.65        88315
12:37:48     all    0.00    0.00    0.00    0.00    2.48   31.19    
0.00    0.00   66.34        87777
12:37:49     all    0.00    0.00    0.00    0.00    2.94   32.35    
0.00    0.00   64.71        89218
12:37:50     all    0.00    0.00    0.00    0.00    3.00   32.50    
0.00    0.00   64.50        85896
12:37:51     all    0.00    0.00    0.00    0.00    2.50   30.00    
0.00    0.00   67.50        82712
12:37:52     all    0.50    0.00    0.00    0.00    2.49   30.85    
0.00    0.00   66.17        79137
12:37:53     all    0.00    0.00    0.50    0.00    2.00   28.50    
0.00    0.00   69.00        75644
12:37:54     all    0.00    0.00    0.00    0.00    2.51   30.65    
0.00    0.00   66.83        72843
12:37:55     all    0.00    0.00    0.50    0.00    3.48   28.36    
0.00    0.00   67.66        73460


Paweł Staszewski pisze:
> Jarek Poplawski pisze:
>> To David Miller:
>> since among patches tested negatively by Pawel are current 2 fixes
>> from 2.6.31-rc, I hope they weren't sent to -stable yet. Otherwise,
>> please withdraw them until they are tested alone. Thanks.
>>
>> To Pawel:
>> On Sun, Jun 28, 2009 at 05:48:19PM +0200, Paweł Staszewski wrote:
>>  
>>> After apply this patch something is wrong
>>>
>>> Traffic is not forwarded
>>> no info in dmesg / no info from bgp
>>> and also i can't connect to bgpd process
>>>
>>> I revert kernel to past version with first Jarek patch
>>>
>>>     
>>
>> Since checking this can take time I attach here a patch with only
>> changes which are currently in 2.6.31-rc. Of course, this part can be
>> broken as well, so it's up to you: if you could try it with caution
>> somewhere it would be very helpful; otherwise don't bother.
>>
>> It could be applied to 2.6.29 with or without this currently working
>> patch.
>>
>>   
>
> Ok.
> I applied this patch 15mins ago to 2.6.29.5 and now it's working - 
> traffic is forwarded.
>
> Some fib_triestats
> cat /proc/net/fib_triestat
> Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
> Main:
>        Aver depth:     2.29
>        Max depth:      6
>        Leaves:         277015
>        Prefixes:       290493
>        Internal nodes: 67115
>          1: 35733  2: 13635  3: 9544  4: 4832  5: 2239  6: 1125  7: 5  
> 9: 1  18: 1
>        Pointers: 686614
> Null ptrs: 342485
> Total size: 18396  kB
>
> Counters:
> ---------
> gets = 3956301
> backtracks = 192497
> semantic match passed = 3895955
> semantic match miss = 133
> null node hit= 4306948
> skipped node resize = 0
>
> Local:
>        Aver depth:     3.75
>        Max depth:      5
>        Leaves:         12
>        Prefixes:       13
>        Internal nodes: 10
>          1: 9  2: 1
>        Pointers: 22
> Null ptrs: 1
> Total size: 2  kB
>
> Counters:
> ---------
> gets = 3960981
> backtracks = 2152441
> semantic match passed = 4757
> semantic match miss = 0
> null node hit= 194997
> skipped node resize = 0
>
>
>
>> Thanks,
>> Jarek P.
>> --- (for 2.6.29.x, .28 or .27)
>>
>> diff -Nurp a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
>> --- a/net/ipv4/fib_trie.c    2009-06-27 20:25:06.000000000 +0200
>> +++ b/net/ipv4/fib_trie.c    2009-06-28 23:06:02.000000000 +0200
>> @@ -123,6 +123,7 @@ struct tnode {
>>      union {
>>          struct rcu_head rcu;
>>          struct work_struct work;
>> +        struct tnode *tnode_free;
>>      };
>>      struct node *child[0];
>>  };
>> @@ -161,6 +162,8 @@ static void tnode_put_child_reorg(struct
>>  static struct node *resize(struct trie *t, struct tnode *tn);
>>  static struct tnode *inflate(struct trie *t, struct tnode *tn);
>>  static struct tnode *halve(struct trie *t, struct tnode *tn);
>> +/* tnodes to free after resize(); protected by RTNL */
>> +static struct tnode *tnode_free_head;
>>  
>>  static struct kmem_cache *fn_alias_kmem __read_mostly;
>>  static struct kmem_cache *trie_leaf_kmem __read_mostly;
>> @@ -385,6 +388,24 @@ static inline void tnode_free(struct tno
>>          call_rcu(&tn->rcu, __tnode_free_rcu);
>>  }
>>  
>> +static void tnode_free_safe(struct tnode *tn)
>> +{
>> +    BUG_ON(IS_LEAF(tn));
>> +    tn->tnode_free = tnode_free_head;
>> +    tnode_free_head = tn;
>> +}
>> +
>> +static void tnode_free_flush(void)
>> +{
>> +    struct tnode *tn;
>> +
>> +    while ((tn = tnode_free_head)) {
>> +        tnode_free_head = tn->tnode_free;
>> +        tn->tnode_free = NULL;
>> +        tnode_free(tn);
>> +    }
>> +}
>> +
>>  static struct leaf *leaf_new(void)
>>  {
>>      struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
>> @@ -495,7 +516,7 @@ static struct node *resize(struct trie *
>>  
>>      /* No children */
>>      if (tn->empty_children == tnode_child_length(tn)) {
>> -        tnode_free(tn);
>> +        tnode_free_safe(tn);
>>          return NULL;
>>      }
>>      /* One child */
>> @@ -509,7 +530,7 @@ static struct node *resize(struct trie *
>>  
>>              /* compress one level */
>>              node_set_parent(n, NULL);
>> -            tnode_free(tn);
>> +            tnode_free_safe(tn);
>>              return n;
>>          }
>>      /*
>> @@ -670,7 +691,7 @@ static struct node *resize(struct trie *
>>              /* compress one level */
>>  
>>              node_set_parent(n, NULL);
>> -            tnode_free(tn);
>> +            tnode_free_safe(tn);
>>              return n;
>>          }
>>  
>> @@ -756,7 +777,7 @@ static struct tnode *inflate(struct trie
>>              put_child(t, tn, 2*i, inode->child[0]);
>>              put_child(t, tn, 2*i+1, inode->child[1]);
>>  
>> -            tnode_free(inode);
>> +            tnode_free_safe(inode);
>>              continue;
>>          }
>>  
>> @@ -801,9 +822,9 @@ static struct tnode *inflate(struct trie
>>          put_child(t, tn, 2*i, resize(t, left));
>>          put_child(t, tn, 2*i+1, resize(t, right));
>>  
>> -        tnode_free(inode);
>> +        tnode_free_safe(inode);
>>      }
>> -    tnode_free(oldtnode);
>> +    tnode_free_safe(oldtnode);
>>      return tn;
>>  nomem:
>>      {
>> @@ -885,7 +906,7 @@ static struct tnode *halve(struct trie *
>>          put_child(t, newBinNode, 1, right);
>>          put_child(t, tn, i/2, resize(t, newBinNode));
>>      }
>> -    tnode_free(oldtnode);
>> +    tnode_free_safe(oldtnode);
>>      return tn;
>>  nomem:
>>      {
>> @@ -983,12 +1004,14 @@ fib_find_node(struct trie *t, u32 key)
>>      return NULL;
>>  }
>>  
>> -static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
>> +static void trie_rebalance(struct trie *t, struct tnode *tn)
>>  {
>>      int wasfull;
>> -    t_key cindex, key = tn->key;
>> +    t_key cindex, key;
>>      struct tnode *tp;
>>  
>> +    key = tn->key;
>> +
>>      while (tn != NULL && (tp = node_parent((struct node *)tn)) != 
>> NULL) {
>>          cindex = tkey_extract_bits(key, tp->pos, tp->bits);
>>          wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
>> @@ -998,6 +1021,7 @@ static struct node *trie_rebalance(struc
>>                        (struct node *)tn, wasfull);
>>  
>>          tp = node_parent((struct node *) tn);
>> +        tnode_free_flush();
>>          if (!tp)
>>              break;
>>          tn = tp;
>> @@ -1007,7 +1031,10 @@ static struct node *trie_rebalance(struc
>>      if (IS_TNODE(tn))
>>          tn = (struct tnode *)resize(t, (struct tnode *)tn);
>>  
>> -    return (struct node *)tn;
>> +    rcu_assign_pointer(t->trie, (struct node *)tn);
>> +    tnode_free_flush();
>> +
>> +    return;
>>  }
>>  
>>  /* only used from updater-side */
>> @@ -1155,7 +1182,7 @@ static struct list_head *fib_insert_node
>>  
>>      /* Rebalance the trie */
>>  
>> -    rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
>> +    trie_rebalance(t, tp);
>>  done:
>>      return fa_head;
>>  }
>> @@ -1575,7 +1602,7 @@ static void trie_leaf_remove(struct trie
>>      if (tp) {
>>          t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
>>          put_child(t, (struct tnode *)tp, cindex, NULL);
>> -        rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
>> +        trie_rebalance(t, tp);
>>      } else
>>          rcu_assign_pointer(t->trie, NULL);
>>  
>>
>>
>>
>>   
>
> -- 
> 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
>
>

--
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
Jarek Poplawski June 29, 2009, 9:27 a.m. UTC | #3 
On Mon, Jun 29, 2009 at 10:47:44AM +0200, Paweł Staszewski wrote:
> But
> With all this patches i have the same problem with CPU load
> Every time when route cache entries are purged cpu load is increasing  
> from 1% to 40 / 80% it depends
>
> I see that on 64bit machine when route cache entries are going down i  
> have almost 80% load on each cpu where ethernet card is binded by  
> smp_affinity
> But on 32bit machine cpu load reported by mpstat is half that on 64bit  
> machine
> here is example from 32bit machine ( mpstat + rtstat -k entries )
>
> Linux 2.6.29.5 (TM_02_C1)       06/29/09        _i686_  (2 CPU)
>
> 12:36:54     CPU    %usr   %nice    %sys %iowait    %irq   %soft  %steal  
> %guest   %idle        RT CACHE ENTRIES (from rtstat)
> 12:36:57     all    0.00    0.00    0.00    0.00    1.51   15.08    0.00  
>   0.00   83.42        83346

I guess Eric is thinking about this. Btw., two little suggestions:
it should be easier to track if these route cache reports stay in its
starting thread ("weird problem"?), and if you could send these
stats/logs as attachements or turn off line wrapping, please? ;-)

Thanks,
Jarek P.
--
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
Paweł Staszewski June 29, 2009, 9:43 a.m. UTC | #4 
Jarek Poplawski pisze:
> On Mon, Jun 29, 2009 at 10:47:44AM +0200, Paweł Staszewski wrote:
>   
>> But
>> With all this patches i have the same problem with CPU load
>> Every time when route cache entries are purged cpu load is increasing  
>> from 1% to 40 / 80% it depends
>>
>> I see that on 64bit machine when route cache entries are going down i  
>> have almost 80% load on each cpu where ethernet card is binded by  
>> smp_affinity
>> But on 32bit machine cpu load reported by mpstat is half that on 64bit  
>> machine
>> here is example from 32bit machine ( mpstat + rtstat -k entries )
>>
>> Linux 2.6.29.5 (TM_02_C1)       06/29/09        _i686_  (2 CPU)
>>
>> 12:36:54     CPU    %usr   %nice    %sys %iowait    %irq   %soft  %steal  
>> %guest   %idle        RT CACHE ENTRIES (from rtstat)
>> 12:36:57     all    0.00    0.00    0.00    0.00    1.51   15.08    0.00  
>>   0.00   83.42        83346
>>     
>
> I guess Eric is thinking about this. Btw., two little suggestions:
> it should be easier to track if these route cache reports stay in its
> starting thread ("weird problem"?), and if you could send these
> stats/logs as attachements or turn off line wrapping, please? ;-)
>
> Thanks,
> Jarek P.
> --
> 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
>
>
>   
Sorry Jarek for combining problems :)
And yes i will apply next stats in attachements :)

--
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 mbox

Patch

diff -Nurp a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
--- a/net/ipv4/fib_trie.c	2009-06-27 20:25:06.000000000 +0200
+++ b/net/ipv4/fib_trie.c	2009-06-28 23:06:02.000000000 +0200
@@ -123,6 +123,7 @@  struct tnode {
 	union {
 		struct rcu_head rcu;
 		struct work_struct work;
+		struct tnode *tnode_free;
 	};
 	struct node *child[0];
 };
@@ -161,6 +162,8 @@  static void tnode_put_child_reorg(struct
 static struct node *resize(struct trie *t, struct tnode *tn);
 static struct tnode *inflate(struct trie *t, struct tnode *tn);
 static struct tnode *halve(struct trie *t, struct tnode *tn);
+/* tnodes to free after resize(); protected by RTNL */
+static struct tnode *tnode_free_head;
 
 static struct kmem_cache *fn_alias_kmem __read_mostly;
 static struct kmem_cache *trie_leaf_kmem __read_mostly;
@@ -385,6 +388,24 @@  static inline void tnode_free(struct tno
 		call_rcu(&tn->rcu, __tnode_free_rcu);
 }
 
+static void tnode_free_safe(struct tnode *tn)
+{
+	BUG_ON(IS_LEAF(tn));
+	tn->tnode_free = tnode_free_head;
+	tnode_free_head = tn;
+}
+
+static void tnode_free_flush(void)
+{
+	struct tnode *tn;
+
+	while ((tn = tnode_free_head)) {
+		tnode_free_head = tn->tnode_free;
+		tn->tnode_free = NULL;
+		tnode_free(tn);
+	}
+}
+
 static struct leaf *leaf_new(void)
 {
 	struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
@@ -495,7 +516,7 @@  static struct node *resize(struct trie *
 
 	/* No children */
 	if (tn->empty_children == tnode_child_length(tn)) {
-		tnode_free(tn);
+		tnode_free_safe(tn);
 		return NULL;
 	}
 	/* One child */
@@ -509,7 +530,7 @@  static struct node *resize(struct trie *
 
 			/* compress one level */
 			node_set_parent(n, NULL);
-			tnode_free(tn);
+			tnode_free_safe(tn);
 			return n;
 		}
 	/*
@@ -670,7 +691,7 @@  static struct node *resize(struct trie *
 			/* compress one level */
 
 			node_set_parent(n, NULL);
-			tnode_free(tn);
+			tnode_free_safe(tn);
 			return n;
 		}
 
@@ -756,7 +777,7 @@  static struct tnode *inflate(struct trie
 			put_child(t, tn, 2*i, inode->child[0]);
 			put_child(t, tn, 2*i+1, inode->child[1]);
 
-			tnode_free(inode);
+			tnode_free_safe(inode);
 			continue;
 		}
 
@@ -801,9 +822,9 @@  static struct tnode *inflate(struct trie
 		put_child(t, tn, 2*i, resize(t, left));
 		put_child(t, tn, 2*i+1, resize(t, right));
 
-		tnode_free(inode);
+		tnode_free_safe(inode);
 	}
-	tnode_free(oldtnode);
+	tnode_free_safe(oldtnode);
 	return tn;
 nomem:
 	{
@@ -885,7 +906,7 @@  static struct tnode *halve(struct trie *
 		put_child(t, newBinNode, 1, right);
 		put_child(t, tn, i/2, resize(t, newBinNode));
 	}
-	tnode_free(oldtnode);
+	tnode_free_safe(oldtnode);
 	return tn;
 nomem:
 	{
@@ -983,12 +1004,14 @@  fib_find_node(struct trie *t, u32 key)
 	return NULL;
 }
 
-static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
+static void trie_rebalance(struct trie *t, struct tnode *tn)
 {
 	int wasfull;
-	t_key cindex, key = tn->key;
+	t_key cindex, key;
 	struct tnode *tp;
 
+	key = tn->key;
+
 	while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
 		cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 		wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
@@ -998,6 +1021,7 @@  static struct node *trie_rebalance(struc
 				      (struct node *)tn, wasfull);
 
 		tp = node_parent((struct node *) tn);
+		tnode_free_flush();
 		if (!tp)
 			break;
 		tn = tp;
@@ -1007,7 +1031,10 @@  static struct node *trie_rebalance(struc
 	if (IS_TNODE(tn))
 		tn = (struct tnode *)resize(t, (struct tnode *)tn);
 
-	return (struct node *)tn;
+	rcu_assign_pointer(t->trie, (struct node *)tn);
+	tnode_free_flush();
+
+	return;
 }
 
 /* only used from updater-side */
@@ -1155,7 +1182,7 @@  static struct list_head *fib_insert_node
 
 	/* Rebalance the trie */
 
-	rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
+	trie_rebalance(t, tp);
 done:
 	return fa_head;
 }
@@ -1575,7 +1602,7 @@  static void trie_leaf_remove(struct trie
 	if (tp) {
 		t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
 		put_child(t, (struct tnode *)tp, cindex, NULL);
-		rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
+		trie_rebalance(t, tp);
 	} else
 		rcu_assign_pointer(t->trie, NULL);