From: "Paweł Staszewski" <pstaszewski@itcare.pl>
To: Robert Olsson <robert@robur.slu.se>
Cc: Jarek Poplawski <jarkao2@gmail.com>,
Robert Olsson <Robert.Olsson@data.slu.se>,
"Jorge Boncompte [DTI2]" <jorge@dti2.net>,
Eric Dumazet <dada1@cosmosbay.com>,
Robert Olsson <robert.olsson@its.uu.se>,
Linux Network Development list <netdev@vger.kernel.org>
Subject: Re: rib_trie / Fix inflate_threshold_root. Now=15 size=11 bits
Date: Mon, 29 Jun 2009 09:57:25 +0200 [thread overview]
Message-ID: <4A4873E5.2000402@itcare.pl> (raw)
In-Reply-To: <19015.20442.620760.399214@robur.slu.se>
Robert Olsson pisze:
> When testing please monitor size of root node and and aver depth
>
> Cheers
> --ro
>
Some fib_triestats - kernel.2.6.29.5 with first Jarek patch.
Dump every 10sec:
Mon Jun 29 11:54:31 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276978
Prefixes: 290448
Internal nodes: 66813
1: 34703 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691606
Null ptrs: 347816
Total size: 18403 kB
Counters:
---------
gets = 390981859
backtracks = 5332465
semantic match passed = 390452936
semantic match miss = 30198
null node hit= 375522207
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 = 391017445
backtracks = 121012874
semantic match passed = 37565
semantic match miss = 0
null node hit= 261583
skipped node resize = 0
Mon Jun 29 11:54:41 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276976
Prefixes: 290446
Internal nodes: 66813
1: 34703 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691606
Null ptrs: 347818
Total size: 18403 kB
Counters:
---------
gets = 391061852
backtracks = 5334173
semantic match passed = 390532664
semantic match miss = 30199
null node hit= 375595706
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 = 391097445
backtracks = 121039213
semantic match passed = 37570
semantic match miss = 0
null node hit= 261589
skipped node resize = 0
Mon Jun 29 11:54:51 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276978
Prefixes: 290448
Internal nodes: 66813
1: 34703 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691606
Null ptrs: 347816
Total size: 18403 kB
Counters:
---------
gets = 391177325
backtracks = 5336127
semantic match passed = 390647917
semantic match miss = 30208
null node hit= 375699713
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 = 391212932
backtracks = 121075919
semantic match passed = 37586
semantic match miss = 0
null node hit= 261701
skipped node resize = 0
Mon Jun 29 11:55:01 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276978
Prefixes: 290448
Internal nodes: 66813
1: 34703 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691606
Null ptrs: 347816
Total size: 18403 kB
Counters:
---------
gets = 391254016
backtracks = 5337816
semantic match passed = 390724361
semantic match miss = 30214
null node hit= 375768712
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 = 391289631
backtracks = 121101285
semantic match passed = 37598
semantic match miss = 0
null node hit= 261707
skipped node resize = 0
Mon Jun 29 11:55:11 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276976
Prefixes: 290445
Internal nodes: 66812
1: 34702 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691604
Null ptrs: 347817
Total size: 18402 kB
Counters:
---------
gets = 391317389
backtracks = 5339175
semantic match passed = 390787523
semantic match miss = 30215
null node hit= 375827612
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 = 391353001
backtracks = 121122087
semantic match passed = 37599
semantic match miss = 0
null node hit= 261709
skipped node resize = 0
Mon Jun 29 11:55:21 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276981
Prefixes: 290451
Internal nodes: 66813
1: 34704 2: 13943 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691604
Null ptrs: 347811
Total size: 18403 kB
Counters:
---------
gets = 391434307
backtracks = 5340855
semantic match passed = 390904256
semantic match miss = 30225
null node hit= 375931780
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 = 391469942
backtracks = 121157220
semantic match passed = 37619
semantic match miss = 0
null node hit= 261753
skipped node resize = 0
Mon Jun 29 11:55:31 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276981
Prefixes: 290451
Internal nodes: 66813
1: 34704 2: 13943 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691604
Null ptrs: 347811
Total size: 18403 kB
Counters:
---------
gets = 391519852
backtracks = 5342208
semantic match passed = 390989658
semantic match miss = 30234
null node hit= 376010537
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 = 391555492
backtracks = 121181992
semantic match passed = 37625
semantic match miss = 0
null node hit= 261762
skipped node resize = 0
Mon Jun 29 11:55:42 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276978
Prefixes: 290447
Internal nodes: 66812
1: 34703 2: 13943 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691602
Null ptrs: 347813
Total size: 18403 kB
Counters:
---------
gets = 391589032
backtracks = 5343757
semantic match passed = 391058601
semantic match miss = 30237
null node hit= 376075389
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 = 391624673
backtracks = 121202115
semantic match passed = 37628
semantic match miss = 0
null node hit= 261763
skipped node resize = 0
Mon Jun 29 11:55:52 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276985
Prefixes: 290455
Internal nodes: 66814
1: 34704 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691608
Null ptrs: 347810
Total size: 18403 kB
Counters:
---------
gets = 391723925
backtracks = 5345934
semantic match passed = 391193292
semantic match miss = 30242
null node hit= 376195655
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 = 391759578
backtracks = 121241080
semantic match passed = 37640
semantic match miss = 0
null node hit= 261804
skipped node resize = 0
Mon Jun 29 11:56:02 2009
Basic info: size of leaf: 20 bytes, size of tnode: 36 bytes.
Main:
Aver depth: 2.28
Max depth: 7
Leaves: 276985
Prefixes: 290455
Internal nodes: 66814
1: 34704 2: 13944 3: 9921 4: 4807 5: 2273 6: 1158 7: 5
9: 1 18: 1
Pointers: 691608
Null ptrs: 347810
Total size: 18403 kB
Counters:
---------
gets = 391811219
backtracks = 5347635
semantic match passed = 391280357
semantic match miss = 30250
null node hit= 376276182
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 = 391846880
backtracks = 121265316
semantic match passed = 37648
semantic match miss = 0
null node hit= 261813
skipped node resize = 0
>
>
> Jarek Poplawski writes:
> > On Sat, Jun 27, 2009 at 09:20:57PM +0200, Jarek Poplawski wrote:
> > ...
> > > Then these settable thresholds might be more useful here than memory
> > > fixes, but here is some idea to try handle this automatically within
> > > some limits. The patch below increases inflate_threshold_root (only)
> > > up to ~50% of its initial value if needed, and should be able to go
> > > back sometimes.
> > >
> > > Pawel and Jorge, could you try this? (It applies to 2.6.29 too, with
> > > some offsets.)
> >
> > A tiny adjustment in the last if...
> >
> > Jarek P.
> > --- (take 2)
> >
> > net/ipv4/fib_trie.c | 23 ++++++++++++++++-------
> > 1 files changed, 16 insertions(+), 7 deletions(-)
> >
> > diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
> > index 012cf5a..1dc1bb4 100644
> > --- a/net/ipv4/fib_trie.c
> > +++ b/net/ipv4/fib_trie.c
> > @@ -318,6 +318,7 @@ static const int halve_threshold = 25;
> > static const int inflate_threshold = 50;
> > static const int halve_threshold_root = 8;
> > static const int inflate_threshold_root = 15;
> > +static int inflate_threshold_root_fix;
> >
> >
> > static void __alias_free_mem(struct rcu_head *head)
> > @@ -602,7 +603,8 @@ static struct node *resize(struct trie *t, struct tnode *tn)
> > /* Keep root node larger */
> >
> > if (!tn->parent)
> > - inflate_threshold_use = inflate_threshold_root;
> > + inflate_threshold_use = inflate_threshold_root +
> > + inflate_threshold_root_fix;
> > else
> > inflate_threshold_use = inflate_threshold;
> >
> > @@ -626,15 +628,22 @@ static struct node *resize(struct trie *t, struct tnode *tn)
> > }
> >
> > if (max_resize < 0) {
> > - if (!tn->parent)
> > - pr_warning("Fix inflate_threshold_root."
> > - " Now=%d size=%d bits\n",
> > - inflate_threshold_root, tn->bits);
> > - else
> > + if (!tn->parent) {
> > + if (inflate_threshold_root_fix * 2 <
> > + inflate_threshold_root)
> > + inflate_threshold_root_fix++;
> > + else
> > + pr_warning("Fix inflate_threshold_root."
> > + " Now=%d size=%d bits fix=%d\n",
> > + inflate_threshold_root, tn->bits,
> > + inflate_threshold_root_fix);
> > + } else {
> > pr_warning("Fix inflate_threshold."
> > " Now=%d size=%d bits\n",
> > inflate_threshold, tn->bits);
> > - }
> > + }
> > + } else if (max_resize > 4 && !tn->parent && inflate_threshold_root_fix)
> > + inflate_threshold_root_fix--;
> >
> > check_tnode(tn);
> >
> > --
> > 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
>
>
>
next prev parent reply other threads:[~2009-06-29 7:57 UTC|newest]
Thread overview: 99+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-06-25 15:48 rib_trie / Fix inflate_threshold_root. Now=15 size=11 bits Paweł Staszewski
2009-06-25 21:19 ` Eric Dumazet
2009-06-25 21:52 ` Paweł Staszewski
2009-06-25 22:54 ` Eric Dumazet
2009-06-26 10:06 ` Paweł Staszewski
2009-06-26 10:34 ` Eric Dumazet
2009-06-26 10:47 ` Paweł Staszewski
2009-06-26 10:52 ` Eric Dumazet
2009-06-26 17:26 ` Paweł Staszewski
2009-06-26 8:03 ` Jarek Poplawski
2009-06-26 9:19 ` Robert Olsson
2009-06-26 9:37 ` Jarek Poplawski
2009-06-26 10:26 ` Jorge Boncompte [DTI2]
2009-06-26 12:42 ` Robert Olsson
2009-06-26 12:54 ` Jarek Poplawski
2009-06-26 13:28 ` Jarek Poplawski
2009-06-26 13:52 ` Robert Olsson
2009-06-26 15:10 ` Jarek Poplawski
2009-06-26 15:30 ` Paul E. McKenney
2009-06-26 15:54 ` Jarek Poplawski
2009-06-26 16:15 ` Jarek Poplawski
2009-06-26 16:23 ` Paul E. McKenney
2009-06-26 16:45 ` Jarek Poplawski
2009-06-26 17:05 ` Paul E. McKenney
2009-06-26 18:05 ` Jarek Poplawski
2009-06-26 18:21 ` Paul E. McKenney
2009-06-26 20:19 ` Jarek Poplawski
2009-06-26 20:26 ` Robert Olsson
2009-06-26 20:37 ` Jarek Poplawski
2009-06-26 21:20 ` Jarek Poplawski
2009-06-27 19:20 ` Jarek Poplawski
2009-06-27 20:51 ` Jarek Poplawski
2009-06-28 0:28 ` Paweł Staszewski
2009-06-28 11:11 ` Robert Olsson
2009-06-29 7:57 ` Paweł Staszewski [this message]
2009-06-28 11:04 ` Robert Olsson
2009-06-28 12:03 ` Jarek Poplawski
2009-06-28 14:35 ` Jarek Poplawski
2009-06-28 15:32 ` Paweł Staszewski
2009-06-28 15:48 ` Paweł Staszewski
2009-06-28 19:56 ` Jarek Poplawski
2009-06-28 21:36 ` Jarek Poplawski
2009-06-29 8:08 ` Paweł Staszewski
2009-06-29 8:47 ` Paweł Staszewski
2009-06-29 9:27 ` Jarek Poplawski
2009-06-29 9:43 ` Paweł Staszewski
2009-06-29 8:33 ` [PATCH net-2.6] " Jarek Poplawski
2009-06-29 9:51 ` Paweł Staszewski
2009-06-29 10:47 ` Jarek Poplawski
2009-06-29 16:24 ` Paweł Staszewski
2009-06-29 17:09 ` Jarek Poplawski
2009-06-30 7:09 ` Jarek Poplawski
2009-06-30 20:16 ` Paweł Staszewski
2009-06-30 20:41 ` Jarek Poplawski
2009-06-30 23:31 ` Paweł Staszewski
2009-07-01 6:36 ` Jarek Poplawski
[not found] ` <20090701072409.GA12592@ff.dom.local>
2009-07-01 9:43 ` Paweł Staszewski
2009-07-01 9:50 ` Paweł Staszewski
2009-07-01 10:13 ` Jarek Poplawski
2009-07-01 11:04 ` Jarek Poplawski
2009-07-01 22:17 ` Paweł Staszewski
2009-07-02 5:32 ` Jarek Poplawski
2009-07-02 5:43 ` Paweł Staszewski
2009-07-02 6:00 ` Jarek Poplawski
2009-07-02 15:31 ` Robert Olsson
2009-07-02 19:06 ` Jarek Poplawski
2009-07-02 21:32 ` Robert Olsson
2009-07-02 22:13 ` Jarek Poplawski
2009-07-05 0:26 ` Paweł Staszewski
2009-07-05 0:30 ` Paweł Staszewski
2009-07-05 16:20 ` Jarek Poplawski
2009-07-05 17:32 ` Jarek Poplawski
2009-07-05 21:32 ` Paul E. McKenney
2009-07-05 22:23 ` Jarek Poplawski
2009-07-05 23:53 ` Paweł Staszewski
2009-07-06 9:02 ` Jarek Poplawski
2009-07-07 22:56 ` Paweł Staszewski
2009-07-07 23:50 ` Jarek Poplawski
2009-07-09 20:34 ` Paweł Staszewski
2009-07-14 19:41 ` [PATCH net-next] " Jarek Poplawski
2009-07-15 7:43 ` Robert Olsson
2009-07-15 13:05 ` Jarek Poplawski
2009-07-17 8:08 ` Robert Olsson
2009-07-20 14:41 ` David Miller
2009-07-07 23:23 ` [PATCH net-2.6] " Paweł Staszewski
2009-07-07 23:30 ` Paweł Staszewski
2009-07-14 18:33 ` [PATCH net-next] " Jarek Poplawski
2009-07-20 14:41 ` David Miller
2009-07-14 21:20 ` [PATCH net-next] ipv4: fib_trie: Use tnode_get_child_rcu() and node_parent_rcu() in lookups Jarek Poplawski
2009-07-20 14:41 ` David Miller
2009-07-05 0:31 ` [PATCH net-2.6] Re: rib_trie / Fix inflate_threshold_root. Now=15 size=11 bits Paweł Staszewski
2009-07-05 12:56 ` [PATCH -stable] " Jarek Poplawski
2009-07-05 13:08 ` [PATCH v2 " Jarek Poplawski
2009-07-08 2:42 ` David Miller
2009-07-08 6:44 ` Jarek Poplawski
2009-06-29 10:58 ` [PATCH net-2.6] " Jarek Poplawski
2009-06-30 19:48 ` David Miller
2009-06-30 20:14 ` Jarek Poplawski
2009-07-10 15:29 ` Stephen Hemminger
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4A4873E5.2000402@itcare.pl \
--to=pstaszewski@itcare.pl \
--cc=Robert.Olsson@data.slu.se \
--cc=dada1@cosmosbay.com \
--cc=jarkao2@gmail.com \
--cc=jorge@dti2.net \
--cc=netdev@vger.kernel.org \
--cc=robert.olsson@its.uu.se \
--cc=robert@robur.slu.se \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).