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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.