Skip to contentSkip to conversation

New: rtable leak in ipv4/route.c

Bug 13339 In review Stephen Hemminger 6 participants 28 messages May 19, 2009 – May 21, 2009

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

           Summary: rtable leak in ipv4/route.c
           Product: Networking
           Version: 2.5
    Kernel Version: 2.6.29
          Platform: All
        OS/Version: Linux
              Tree: Mainline
            Status: NEW
          Severity: high
          Priority: P1
         Component: IPV4
        AssignedTo: [email protected]
        ReportedBy: [email protected]
        Regression: Yes

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

Signature · 6 lines
Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.


-- 
#1 lore raw
Quoted 10 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 10 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

This leak leads to unregister_netdevice problem (usage count > 0).

Quoted 7 lines

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

Thanks,
Jarek P.

#2 lore raw
Quoted 27 lines · Jarek Poplawski
Quoted 10 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 15 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 5 lines
Quoted 2 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

I agree that the corner case in which cand and rthi is a problem (although as you point out easily fixable), and with an alteration to your proposal it can be done without destroying the order.

As for the reordering by reference however, I don't see any move to front heuristic being implemented anywhere in the routing path. Where do you see this happening?

Neil

#3 lore raw
In reply to Jarek Poplawski
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 7 lines
Quoted 3 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

Here is mine, only compiled, not tested yet.

All credits for Stephen for doing the analysis of course :)

net/ipv4/route.c +29 -41
index c4c60e9..fbe77ad 100644
@@ -780,12 +780,37 @@ static void rt_do_flush(int process_context)
 #define FRACT_BITS 3
 #define ONE (1UL << FRACT_BITS)
 
+static unsigned long compute_length(struct rtable *head)
+{
+	struct rtable *rth, *aux;
+	unsigned long length = 0;
+
+	for (rth = head; rth != NULL; rth = rth->u.dst.rt_next) {
+		/*
+		 * We ignore items having same hash inputs
+		 * so that entries for different QOS
+		 * levels, and other non-hash input
+		 * attributes don't unfairly skew
+		 * the length computation
+		 */
+		for (aux = head; ;aux = aux->u.dst.rt_next) {
+			if (aux == rth) {
+				length += ONE;
+				break;
+			}
+			if (compare_hash_inputs(&aux->fl, &rth->fl))
+				break;
+		}
+	}
+	return length;
+}
+
 static void rt_check_expire(void)
 {
 	static unsigned int rover;
 	unsigned int i = rover, goal;
 	struct rtable *rth, **rthp;
-	unsigned long length = 0, samples = 0;
+	unsigned long length, samples = 0;
 	unsigned long sum = 0, sum2 = 0;
 	u64 mult;
 
@@ -795,7 +820,6 @@ static void rt_check_expire(void)
 	goal = (unsigned int)mult;
 	if (goal > rt_hash_mask)
 		goal = rt_hash_mask + 1;
-	length = 0;
 	for (; goal > 0; goal--) {
 		unsigned long tmo = ip_rt_gc_timeout;
 
@@ -821,29 +845,11 @@ static void rt_check_expire(void)
 				if (time_before_eq(jiffies, rth->u.dst.expires)) {
 					tmo >>= 1;
 					rthp = &rth->u.dst.rt_next;
-					/*
-					 * Only bump our length if the hash
-					 * inputs on entries n and n+1 are not
-					 * the same, we only count entries on
-					 * a chain with equal hash inputs once
-					 * so that entries for different QOS
-					 * levels, and other non-hash input
-					 * attributes don't unfairly skew
-					 * the length computation
-					 */
-					if ((*rthp == NULL) ||
-					    !compare_hash_inputs(&(*rthp)->fl,
-								 &rth->fl))
-						length += ONE;
 					continue;
 				}
 			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
 				tmo >>= 1;
 				rthp = &rth->u.dst.rt_next;
-				if ((*rthp == NULL) ||
-				    !compare_hash_inputs(&(*rthp)->fl,
-							 &rth->fl))
-					length += ONE;
 				continue;
 			}
 
@@ -851,6 +857,7 @@ static void rt_check_expire(void)
 			*rthp = rth->u.dst.rt_next;
 			rt_free(rth);
 		}
+		length = compute_length(rt_hash_table[i].chain);
 		spin_unlock_bh(rt_hash_lock_addr(i));
 		sum += length;
 		sum2 += length*length;
@@ -1068,7 +1075,6 @@ out:	return 0;
 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
 {
 	struct rtable	*rth, **rthp;
-	struct rtable	*rthi;
 	unsigned long	now;
 	struct rtable *cand, **candp;
 	u32 		min_score;
@@ -1088,7 +1094,6 @@ restart:
 	}
 
 	rthp = &rt_hash_table[hash].chain;
-	rthi = NULL;
 
 	spin_lock_bh(rt_hash_lock_addr(hash));
 	while ((rth = *rthp) != NULL) {
@@ -1134,17 +1139,6 @@ restart:
 		chain_length++;
 
 		rthp = &rth->u.dst.rt_next;
-
-		/*
-		 * check to see if the next entry in the chain
-		 * contains the same hash input values as rt.  If it does
-		 * This is where we will insert into the list, instead of
-		 * at the head.  This groups entries that differ by aspects not
-		 * relvant to the hash function together, which we use to adjust
-		 * our chain length
-		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
-			rthi = rth;
 	}
 
 	if (cand) {
@@ -1205,10 +1199,7 @@ restart:
 		}
 	}
 
-	if (rthi)
-		rt->u.dst.rt_next = rthi->u.dst.rt_next;
-	else
-		rt->u.dst.rt_next = rt_hash_table[hash].chain;
+	rt->u.dst.rt_next = rt_hash_table[hash].chain;
 
 #if RT_CACHE_DEBUG >= 2
 	if (rt->u.dst.rt_next) {
@@ -1224,10 +1215,7 @@ restart:
 	 * previous writes to rt are comitted to memory
 	 * before making rt visible to other CPUS.
 	 */
-	if (rthi)
-		rcu_assign_pointer(rthi->u.dst.rt_next, rt);
-	else
-		rcu_assign_pointer(rt_hash_table[hash].chain, rt);
+	rcu_assign_pointer(rt_hash_table[hash].chain, rt);
 
 	spin_unlock_bh(rt_hash_lock_addr(hash));
 	*rp = rt;
#4 lore raw
Quoted 27 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 14 lines

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 7 lines
Quoted 3 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

I was thinking something along these lines (also completely untested). The extra check in rt_intern hash prevents us from identifying a 'group leader' that is about to be deleted, and sets rthi to point at the group leader rather than the last entry in the group as it previously did, which we then mark with the new flag in the dst_entry (updating it on rt_free of course). This lets us identify the boundaries of a group, so when we do a move to front heruistic, we
can move the entire group rather than just the single entry. I prefer this to
Erics approach since, even though rt_check_expire isn't in a performance critical path, the addition of the extra list search when the list is unordered makes rt_check_expire run in O(n^2) rather than O(n), which I think will have a significant impact on high traffic systems. Since the ordered list creation was done at almost zero performance cost in rt_intern_hash, I'd like to keep it if at all possible.

There is of course a shortcomming in my patch in that it doesn't actually do anything currently with DST_GRPLDR other than set/clear it appropriately, I've yet to identify where the route cache move to front heruistic is implemented. If someone could show me where that is, I'd be happy to finish this patch.

Neil

#5 lore raw
Quoted 53 lines · Neil Horman
Quoted 26 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 11 lines

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 5 lines
Quoted 2 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

I was thinking something along these lines (also completely untested). The extra check in rt_intern hash prevents us from identifying a 'group leader' that is about to be deleted, and sets rthi to point at the group leader rather than the last entry in the group as it previously did, which we then mark with the new flag in the dst_entry (updating it on rt_free of course). This lets us identify the boundaries of a group, so when we do a move to front heruistic, we
can move the entire group rather than just the single entry. I prefer this to
Erics approach since, even though rt_check_expire isn't in a performance critical path, the addition of the extra list search when the list is unordered makes rt_check_expire run in O(n^2) rather than O(n), which I think will have a significant impact on high traffic systems. Since the ordered list creation was done at almost zero performance cost in rt_intern_hash, I'd like to keep it if at all possible.

Quoted 5 lines

There is of course a shortcomming in my patch in that it doesn't actually do anything currently with DST_GRPLDR other than set/clear it appropriately, I've yet to identify where the route cache move to front heruistic is implemented. If someone could show me where that is, I'd be happy to finish this patch.

O(n^2) ? Not exactly ...

N * (Y + x) instead of N * (Y), where x <= Y/100, and we can make x being 0 in fact with proper prefetching.

Real cost is bringing into CPU cache the information needed, by two orders of magnitude. (one cache line miss : more than 200 cycles, and we need at least two cache lines per rtable.)

Adding 'group' notion to dst entries is overengineering an already too complex ipv4/route.c file, that is almost unreadable these days, since even you can not spot the point where we move the entry at chain front.

Hint : search for /* Put it first */ in rt_intern_hash()

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Here is is a revised patch, doing the length computation inside the loop, while cpu is prefeching next entry into its cache.

BTW, we actually have another bug, since length is set to 0 at the wrong place (before the for (; goal > 0; goal--) loop)

We must of course reset length to 0 for each chain.

All credits for Alexander V. Lukyanov for doing the analysis of course :)

 net/ipv4/route.c |   57 ++++++++++++++-------------------------------
 1 files changed, 18 insertions(+), 39 deletions(-)
net/ipv4/route.c +18 -39
index c4c60e9..769f72e 100644
@@ -784,7 +784,7 @@ static void rt_check_expire(void)
 {
 	static unsigned int rover;
 	unsigned int i = rover, goal;
-	struct rtable *rth, **rthp;
+	struct rtable *rth, *aux, **rthp;
 	unsigned long length = 0, samples = 0;
 	unsigned long sum = 0, sum2 = 0;
 	u64 mult;
@@ -795,7 +795,6 @@ static void rt_check_expire(void)
 	goal = (unsigned int)mult;
 	if (goal > rt_hash_mask)
 		goal = rt_hash_mask + 1;
-	length = 0;
 	for (; goal > 0; goal--) {
 		unsigned long tmo = ip_rt_gc_timeout;
 
@@ -809,8 +808,10 @@ static void rt_check_expire(void)
 
 		if (*rthp == NULL)
 			continue;
+		length = 0;
 		spin_lock_bh(rt_hash_lock_addr(i));
 		while ((rth = *rthp) != NULL) {
+			prefetch(rth->u.dst.rt_next);
 			if (rt_is_expired(rth)) {
 				*rthp = rth->u.dst.rt_next;
 				rt_free(rth);
@@ -819,33 +820,30 @@ static void rt_check_expire(void)
 			if (rth->u.dst.expires) {
 				/* Entry is expired even if it is in use */
 				if (time_before_eq(jiffies, rth->u.dst.expires)) {
+nofree:
 					tmo >>= 1;
 					rthp = &rth->u.dst.rt_next;
 					/*
-					 * Only bump our length if the hash
-					 * inputs on entries n and n+1 are not
-					 * the same, we only count entries on
+					 * We only count entries on
 					 * a chain with equal hash inputs once
 					 * so that entries for different QOS
 					 * levels, and other non-hash input
 					 * attributes don't unfairly skew
 					 * the length computation
 					 */
-					if ((*rthp == NULL) ||
-					    !compare_hash_inputs(&(*rthp)->fl,
-								 &rth->fl))
-						length += ONE;
+					for (aux = rt_hash_table[i].chain;;) {
+						if (aux == rth) {
+							length += ONE;
+							break;
+						}
+						if (compare_hash_inputs(&aux->fl, &rth->fl))
+							break;
+						aux = aux->u.dst.rt_next;
+					}
 					continue;
 				}
-			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
-				tmo >>= 1;
-				rthp = &rth->u.dst.rt_next;
-				if ((*rthp == NULL) ||
-				    !compare_hash_inputs(&(*rthp)->fl,
-							 &rth->fl))
-					length += ONE;
-				continue;
-			}
+			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout))
+				goto nofree;
 
 			/* Cleanup aged off entries. */
 			*rthp = rth->u.dst.rt_next;
@@ -1068,7 +1066,6 @@ out:	return 0;
 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
 {
 	struct rtable	*rth, **rthp;
-	struct rtable	*rthi;
 	unsigned long	now;
 	struct rtable *cand, **candp;
 	u32 		min_score;
@@ -1088,7 +1085,6 @@ restart:
 	}
 
 	rthp = &rt_hash_table[hash].chain;
-	rthi = NULL;
 
 	spin_lock_bh(rt_hash_lock_addr(hash));
 	while ((rth = *rthp) != NULL) {
@@ -1134,17 +1130,6 @@ restart:
 		chain_length++;
 
 		rthp = &rth->u.dst.rt_next;
-
-		/*
-		 * check to see if the next entry in the chain
-		 * contains the same hash input values as rt.  If it does
-		 * This is where we will insert into the list, instead of
-		 * at the head.  This groups entries that differ by aspects not
-		 * relvant to the hash function together, which we use to adjust
-		 * our chain length
-		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
-			rthi = rth;
 	}
 
 	if (cand) {
@@ -1205,10 +1190,7 @@ restart:
 		}
 	}
 
-	if (rthi)
-		rt->u.dst.rt_next = rthi->u.dst.rt_next;
-	else
-		rt->u.dst.rt_next = rt_hash_table[hash].chain;
+	rt->u.dst.rt_next = rt_hash_table[hash].chain;
 
 #if RT_CACHE_DEBUG >= 2
 	if (rt->u.dst.rt_next) {
@@ -1224,10 +1206,7 @@ restart:
 	 * previous writes to rt are comitted to memory
 	 * before making rt visible to other CPUS.
 	 */
-	if (rthi)
-		rcu_assign_pointer(rthi->u.dst.rt_next, rt);
-	else
-		rcu_assign_pointer(rt_hash_table[hash].chain, rt);
+	rcu_assign_pointer(rt_hash_table[hash].chain, rt);
 
 	spin_unlock_bh(rt_hash_lock_addr(hash));
 	*rp = rt;
#6 lore raw
Quoted 54 lines · Eric Dumazet
Quoted 53 lines · Neil Horman
Quoted 26 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 11 lines

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 5 lines
Quoted 2 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

I was thinking something along these lines (also completely untested). The extra check in rt_intern hash prevents us from identifying a 'group leader' that is about to be deleted, and sets rthi to point at the group leader rather than the last entry in the group as it previously did, which we then mark with the new flag in the dst_entry (updating it on rt_free of course). This lets us identify the boundaries of a group, so when we do a move to front heruistic, we
can move the entire group rather than just the single entry. I prefer this to
Erics approach since, even though rt_check_expire isn't in a performance critical path, the addition of the extra list search when the list is unordered makes rt_check_expire run in O(n^2) rather than O(n), which I think will have a significant impact on high traffic systems. Since the ordered list creation was done at almost zero performance cost in rt_intern_hash, I'd like to keep it if at all possible.

Quoted 8 lines
Quoted 5 lines

There is of course a shortcomming in my patch in that it doesn't actually do anything currently with DST_GRPLDR other than set/clear it appropriately, I've yet to identify where the route cache move to front heruistic is implemented. If someone could show me where that is, I'd be happy to finish this patch.

O(n^2) ? Not exactly ...

you're right, on closer examination, its not O(n^2), but its not what you have below either I don't think

Quoted 3 lines

N * (Y + x) instead of N * (Y), where x <= Y/100, and we can make x being 0 in fact with proper prefetching.

From the way I read you patch (which is actually pretty clever as I look at it), you add an extra loop that searches from the start of the given chain to the point at which the outer loop is set looking for a duplicate, so that each rtable entry which varies only by non-hash relevant values is counted only once. Thats good. But that means for a chain of n nodes in which you are checking the ith node for duplicates you need to visit at worst i other nodes, so to process the entire chain we need to visit SUM(i=1..n)(i) == (n(n-1)/2) nodes rather than the simply linear search requireing the inspection of only n nodes. I see how with prefetching the cost of the additional node visitation can be minimized, but thats still a significantly larger set of nodes to check per expiration run.

Quoted 11 lines

Real cost is bringing into CPU cache the information needed, by two orders of magnitude. (one cache line miss : more than 200 cycles, and we need at least two cache lines per rtable.)

Adding 'group' notion to dst entries is overengineering an already too complex ipv4/route.c file, that is almost unreadable these days, since even you can not spot the point where we move the entry at chain front.

Hint : search for /* Put it first */ in rt_intern_hash()

Ah! So its not actually on rtable access (i.e. route lookup) that we do a move-to-front, its only when we're hashing in new entries. That explains why I didn't see it, I was thinking route lookups moved the entry to the front, not inserts.

Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Thanks
Neil

maintainer
#7 lore raw

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

So I would like to see an explicit final patch from Eric so we can get this fixed now.

Thanks!

#8 lore raw
Quoted 21 lines · David Miller

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

Quoted 9 lines

So I would like to see an explicit final patch from Eric so we can get this fixed now.

Thanks!
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Agreed, thanks once again for educating me Eric!
Neil

#9 lore raw

PATCH 1/1 net: fix length computation in rt_check_expire()

In reply to David Miller
Quoted 15 lines · David Miller

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

Quoted 9 lines

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

So I would like to see an explicit final patch from Eric so we can get this fixed now.

I would like to split patches because we have two bugs indeed, and I prefer to get attention for both problems, I dont remember Neil acknowledged the length computation problem.

First and small patch, candidate for net-2.6 and stable (for 2.6.29) :

Thank you

[PATCH] net: fix length computation in rt_check_expire()

rt_check_expire() computes average and standard deviation of chain lengths, but not correclty reset length to 0 at beginning of each chain. This probably gives overflows for sum2 (and sum) on loaded machines instead of meaningful results.

---
 net/ipv4/route.c |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)
net/ipv4/route.c +3 -2
index c4c60e9..869cf1c 100644
@@ -785,7 +785,7 @@ static void rt_check_expire(void)
 	static unsigned int rover;
 	unsigned int i = rover, goal;
 	struct rtable *rth, **rthp;
-	unsigned long length = 0, samples = 0;
+	unsigned long samples = 0;
 	unsigned long sum = 0, sum2 = 0;
 	u64 mult;
 
@@ -795,9 +795,9 @@ static void rt_check_expire(void)
 	goal = (unsigned int)mult;
 	if (goal > rt_hash_mask)
 		goal = rt_hash_mask + 1;
-	length = 0;
 	for (; goal > 0; goal--) {
 		unsigned long tmo = ip_rt_gc_timeout;
+		unsigned long length;
 
 		i = (i + 1) & rt_hash_mask;
 		rthp = &rt_hash_table[i].chain;
@@ -809,6 +809,7 @@ static void rt_check_expire(void)
 
 		if (*rthp == NULL)
 			continue;
+		length = 0;
 		spin_lock_bh(rt_hash_lock_addr(i));
 		while ((rth = *rthp) != NULL) {
 			if (rt_is_expired(rth)) {
maintainer
#10 lore raw

Re: [PATCH] net: fix length computation in rt_check_expire()

From: Eric Dumazet <[email protected]>
Date: Wed, 20 May 2009 06:54:22 +0200

Quoted 8 lines

I would like to split patches because we have two bugs indeed, and I prefer to get attention for both problems, I dont remember Neil acknowledged the length computation problem.

First and small patch, candidate for net-2.6 and stable (for 2.6.29) :

Thank you

Quoted 8 lines

[PATCH] net: fix length computation in rt_check_expire()

rt_check_expire() computes average and standard deviation of chain lengths, but not correclty reset length to 0 at beginning of each chain. This probably gives overflows for sum2 (and sum) on loaded machines instead of meaningful results.

Yes I definitely agree this length initialization is a bug.

I'll integrate this fix soon, thanks Eric. You can send me the other part of the bug fix relative to this if you like.

#11 lore raw

PATCH 1/1 net: fix rtable leak in net/ipv4/route.c

In reply to Eric Dumazet
Quoted 25 lines · Eric Dumazet
Quoted 14 lines · David Miller

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

Quoted 9 lines

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

So I would like to see an explicit final patch from Eric so we can get this fixed now.

Quoted 6 lines

I would like to split patches because we have two bugs indeed, and I prefer to get attention for both problems, I dont remember Neil acknowledged the length computation problem.

First and small patch, candidate for net-2.6 and stable (for 2.6.29) :

Then here is the patch on top on previous one.

Thanks to all

[PATCH] net: fix rtable leak in net/ipv4/route.c

Alexander V. Lukyanov found a regression in 2.6.29 and made a complete analysis found in http://bugzilla.kernel.org/show_bug.cgi?id=13339
Quoted here because its a perfect one :

begin_of_quotation
2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.
end_of_quotation

Problematic commit is 1080d709fb9d8cd4392f93476ee46a9d6ea05a5b (net: implement emergency route cache rebulds when gc_elasticity is exceeded)

Trying to keep dst_entries ordered is too complex and breaks the fact that order should depend on the frequency of use for garbage collection.

A possible fix is to make rt_intern_hash() simpler, and only makes rt_check_expire() a litle bit smarter, being able to cope with an arbitrary entries order. The added loop is running on cache hot data, while cpu is prefetching next object, so should be unnoticied.

---
 net/ipv4/route.c |   55 +++++++++++++--------------------------------
 1 files changed, 17 insertions(+), 38 deletions(-)
net/ipv4/route.c +17 -38
index 869cf1c..28205e5 100644
@@ -784,7 +784,7 @@ static void rt_check_expire(void)
 {
 	static unsigned int rover;
 	unsigned int i = rover, goal;
-	struct rtable *rth, **rthp;
+	struct rtable *rth, *aux, **rthp;
 	unsigned long samples = 0;
 	unsigned long sum = 0, sum2 = 0;
 	u64 mult;
@@ -812,6 +812,7 @@ static void rt_check_expire(void)
 		length = 0;
 		spin_lock_bh(rt_hash_lock_addr(i));
 		while ((rth = *rthp) != NULL) {
+			prefetch(rth->u.dst.rt_next);
 			if (rt_is_expired(rth)) {
 				*rthp = rth->u.dst.rt_next;
 				rt_free(rth);
@@ -820,33 +821,30 @@ static void rt_check_expire(void)
 			if (rth->u.dst.expires) {
 				/* Entry is expired even if it is in use */
 				if (time_before_eq(jiffies, rth->u.dst.expires)) {
+nofree:
 					tmo >>= 1;
 					rthp = &rth->u.dst.rt_next;
 					/*
-					 * Only bump our length if the hash
-					 * inputs on entries n and n+1 are not
-					 * the same, we only count entries on
+					 * We only count entries on
 					 * a chain with equal hash inputs once
 					 * so that entries for different QOS
 					 * levels, and other non-hash input
 					 * attributes don't unfairly skew
 					 * the length computation
 					 */
-					if ((*rthp == NULL) ||
-					    !compare_hash_inputs(&(*rthp)->fl,
-								 &rth->fl))
-						length += ONE;
+					for (aux = rt_hash_table[i].chain;;) {
+						if (aux == rth) {
+							length += ONE;
+							break;
+						}
+						if (compare_hash_inputs(&aux->fl, &rth->fl))
+							break;
+						aux = aux->u.dst.rt_next;
+					}
 					continue;
 				}
-			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
-				tmo >>= 1;
-				rthp = &rth->u.dst.rt_next;
-				if ((*rthp == NULL) ||
-				    !compare_hash_inputs(&(*rthp)->fl,
-							 &rth->fl))
-					length += ONE;
-				continue;
-			}
+			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout))
+				goto nofree;
 
 			/* Cleanup aged off entries. */
 			*rthp = rth->u.dst.rt_next;
@@ -1069,7 +1067,6 @@ out:	return 0;
 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
 {
 	struct rtable	*rth, **rthp;
-	struct rtable	*rthi;
 	unsigned long	now;
 	struct rtable *cand, **candp;
 	u32 		min_score;
@@ -1089,7 +1086,6 @@ restart:
 	}
 
 	rthp = &rt_hash_table[hash].chain;
-	rthi = NULL;
 
 	spin_lock_bh(rt_hash_lock_addr(hash));
 	while ((rth = *rthp) != NULL) {
@@ -1135,17 +1131,6 @@ restart:
 		chain_length++;
 
 		rthp = &rth->u.dst.rt_next;
-
-		/*
-		 * check to see if the next entry in the chain
-		 * contains the same hash input values as rt.  If it does
-		 * This is where we will insert into the list, instead of
-		 * at the head.  This groups entries that differ by aspects not
-		 * relvant to the hash function together, which we use to adjust
-		 * our chain length
-		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
-			rthi = rth;
 	}
 
 	if (cand) {
@@ -1206,10 +1191,7 @@ restart:
 		}
 	}
 
-	if (rthi)
-		rt->u.dst.rt_next = rthi->u.dst.rt_next;
-	else
-		rt->u.dst.rt_next = rt_hash_table[hash].chain;
+	rt->u.dst.rt_next = rt_hash_table[hash].chain;
 
 #if RT_CACHE_DEBUG >= 2
 	if (rt->u.dst.rt_next) {
@@ -1225,10 +1207,7 @@ restart:
 	 * previous writes to rt are comitted to memory
 	 * before making rt visible to other CPUS.
 	 */
-	if (rthi)
-		rcu_assign_pointer(rthi->u.dst.rt_next, rt);
-	else
-		rcu_assign_pointer(rt_hash_table[hash].chain, rt);
+	rcu_assign_pointer(rt_hash_table[hash].chain, rt);
 
 	spin_unlock_bh(rt_hash_lock_addr(hash));
 	*rp = rt;
#12 lore raw

Re: [PATCH] net: fix rtable leak in net/ipv4/route.c

Quoted 123 lines · Eric Dumazet
Quoted 25 lines · Eric Dumazet
Quoted 14 lines · David Miller

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

Quoted 9 lines

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

So I would like to see an explicit final patch from Eric so we can get this fixed now.

Quoted 6 lines

I would like to split patches because we have two bugs indeed, and I prefer to get attention for both problems, I dont remember Neil acknowledged the length computation problem.

First and small patch, candidate for net-2.6 and stable (for 2.6.29) :

Then here is the patch on top on previous one.

Thanks to all

[PATCH] net: fix rtable leak in net/ipv4/route.c

Alexander V. Lukyanov found a regression in 2.6.29 and made a complete analysis found in http://bugzilla.kernel.org/show_bug.cgi?id=13339
Quoted here because its a perfect one :

begin_of_quotation
2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.
end_of_quotation

Problematic commit is 1080d709fb9d8cd4392f93476ee46a9d6ea05a5b (net: implement emergency route cache rebulds when gc_elasticity is exceeded)

Trying to keep dst_entries ordered is too complex and breaks the fact that order should depend on the frequency of use for garbage collection.

A possible fix is to make rt_intern_hash() simpler, and only makes rt_check_expire() a litle bit smarter, being able to cope with an arbitrary entries order. The added loop is running on cache hot data, while cpu is prefetching next object, so should be unnoticied.

---
 net/ipv4/route.c |   55 +++++++++++++--------------------------------
 1 files changed, 17 insertions(+), 38 deletions(-)
net/ipv4/route.c +4 -7
index 869cf1c..28205e5 100644
@@ -784,7 +784,7 @@ static void rt_check_expire(void)
 {
 	static unsigned int rover;
 	unsigned int i = rover, goal;
-	struct rtable *rth, **rthp;
+	struct rtable *rth, *aux, **rthp;
 	unsigned long samples = 0;
 	unsigned long sum = 0, sum2 = 0;
 	u64 mult;
@@ -812,6 +812,7 @@ static void rt_check_expire(void)
 		length = 0;
 		spin_lock_bh(rt_hash_lock_addr(i));
 		while ((rth = *rthp) != NULL) {
+			prefetch(rth->u.dst.rt_next);
 			if (rt_is_expired(rth)) {
 				*rthp = rth->u.dst.rt_next;
 				rt_free(rth);
@@ -820,33 +821,30 @@ static void rt_check_expire(void)
 			if (rth->u.dst.expires) {
 				/* Entry is expired even if it is in use */
 				if (time_before_eq(jiffies, rth->u.dst.expires)) {
+nofree:
 					tmo >>= 1;
 					rthp = &rth->u.dst.rt_next;
 					/*
-					 * Only bump our length if the hash
-					 * inputs on entries n and n+1 are not
-					 * the same, we only count entries on
+					 * We only count entries on
 					 * a chain with equal hash inputs once
 					 * so that entries for different QOS
 					 * levels, and other non-hash input
 					 * attributes don't unfairly skew
 					 * the length computation
 					 */
-					if ((*rthp == NULL) ||
-					    !compare_hash_inputs(&(*rthp)->fl,
-								 &rth->fl))

net/ipv4/route.c static void rt_check_expire(void) · line 843

Quoted 10 lines
net/ipv4/route.c +9 -1
-						length += ONE;
+					for (aux = rt_hash_table[i].chain;;) {
+						if (aux == rth) {
+							length += ONE;
+							break;
+						}
+						if (compare_hash_inputs(&aux->fl, &rth->fl))
+							break;
+						aux = aux->u.dst.rt_next;
+					}

Very "interesting" for() usage, but isn't it more readable like this?:

					aux = rt_hash_table[i].chain;
					while (aux != rth) {
						if (compare_hash_inputs(&aux->fl, &rth->fl))
							break;
						aux = aux->u.dst.rt_next;
					}

					if (aux == rth)
						length += ONE;

Jarek P.

Quoted 75 lines
net/ipv4/route.c +4 -30
 					continue;
 				}
-			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
-				tmo >>= 1;
-				rthp = &rth->u.dst.rt_next;
-				if ((*rthp == NULL) ||
-				    !compare_hash_inputs(&(*rthp)->fl,
-							 &rth->fl))
-					length += ONE;
-				continue;
-			}
+			} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout))
+				goto nofree;
 
 			/* Cleanup aged off entries. */
 			*rthp = rth->u.dst.rt_next;
@@ -1069,7 +1067,6 @@ out:	return 0;
 static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp)
 {
 	struct rtable	*rth, **rthp;
-	struct rtable	*rthi;
 	unsigned long	now;
 	struct rtable *cand, **candp;
 	u32 		min_score;
@@ -1089,7 +1086,6 @@ restart:
 	}
 
 	rthp = &rt_hash_table[hash].chain;
-	rthi = NULL;
 
 	spin_lock_bh(rt_hash_lock_addr(hash));
 	while ((rth = *rthp) != NULL) {
@@ -1135,17 +1131,6 @@ restart:
 		chain_length++;
 
 		rthp = &rth->u.dst.rt_next;
-
-		/*
-		 * check to see if the next entry in the chain
-		 * contains the same hash input values as rt.  If it does
-		 * This is where we will insert into the list, instead of
-		 * at the head.  This groups entries that differ by aspects not
-		 * relvant to the hash function together, which we use to adjust
-		 * our chain length
-		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
-			rthi = rth;
 	}
 
 	if (cand) {
@@ -1206,10 +1191,7 @@ restart:
 		}
 	}
 
-	if (rthi)
-		rt->u.dst.rt_next = rthi->u.dst.rt_next;
-	else
-		rt->u.dst.rt_next = rt_hash_table[hash].chain;
+	rt->u.dst.rt_next = rt_hash_table[hash].chain;
 
 #if RT_CACHE_DEBUG >= 2
 	if (rt->u.dst.rt_next) {
@@ -1225,10 +1207,7 @@ restart:
 	 * previous writes to rt are comitted to memory
 	 * before making rt visible to other CPUS.
 	 */
-	if (rthi)
-		rcu_assign_pointer(rthi->u.dst.rt_next, rt);
-	else
-		rcu_assign_pointer(rt_hash_table[hash].chain, rt);
+	rcu_assign_pointer(rt_hash_table[hash].chain, rt);
 
 	spin_unlock_bh(rt_hash_lock_addr(hash));
 	*rp = rt;
#13 lore raw

Re: [PATCH] net: fix rtable leak in net/ipv4/route.c

Quoted 13 lines · Jarek Poplawski

net/ipv4/route.c static void rt_check_expire(void) · line 843

Quoted 9 lines · Eric Dumazet
net/ipv4/route.c +9 -0
+					for (aux = rt_hash_table[i].chain;;) {
+						if (aux == rth) {
+							length += ONE;
+							break;
+						}
+						if (compare_hash_inputs(&aux->fl, &rth->fl))
+							break;
+						aux = aux->u.dst.rt_next;
+					}

Very "interesting" for() usage, but isn't it more readable like this?:

Quoted 6 lines
					aux = rt_hash_table[i].chain;
					while (aux != rth) {
						if (compare_hash_inputs(&aux->fl, &rth->fl))
							break;
						aux = aux->u.dst.rt_next;
					}

well, this test is done two times, this is the difference...

Quoted 5 lines
					if (aux == rth)
						length += ONE;

Jarek P.

I first wrote :

					for (aux = rt_hash_table[i].chain ; ; aux = aux->u.dst.rt_next) {
						if (aux == rth) {
							length += ONE;
							break;
						}
						if (compare_hash_inputs(&aux->fl, &rth->fl))
							break;
					}

but had to split the too long line, so ended in the form in the patch :)

Thank you

#14 lore raw

Re: [PATCH] net: fix rtable leak in net/ipv4/route.c

Quoted 14 lines · Eric Dumazet
Quoted 13 lines · Jarek Poplawski

net/ipv4/route.c static void rt_check_expire(void) · line 843

Quoted 9 lines · Eric Dumazet
net/ipv4/route.c +9 -0
+					for (aux = rt_hash_table[i].chain;;) {
+						if (aux == rth) {
+							length += ONE;
+							break;
+						}
+						if (compare_hash_inputs(&aux->fl, &rth->fl))
+							break;
+						aux = aux->u.dst.rt_next;
+					}

Very "interesting" for() usage, but isn't it more readable like this?:

Quoted 8 lines
Quoted 6 lines
					aux = rt_hash_table[i].chain;
					while (aux != rth) {
						if (compare_hash_inputs(&aux->fl, &rth->fl))
							break;
						aux = aux->u.dst.rt_next;
					}

well, this test is done two times, this is the difference...

I know, but I guess this is used quite often. And probably it's not very hard optimization for a compiler (while - else). As a matter of fact even this would confuse me less here:

					aux = rt_hash_table[i].chain;
					for (;;) {

But of course, it's a matter of taste, so no big deal.

Jarek P.

Acked-by on v1 1/1
#15 lore raw

Re: [PATCH] net: fix rtable leak in net/ipv4/route.c

In reply to Eric Dumazet
Quoted 70 lines · Eric Dumazet
Quoted 25 lines · Eric Dumazet
Quoted 14 lines · David Miller

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

Quoted 9 lines

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

So I would like to see an explicit final patch from Eric so we can get this fixed now.

Quoted 6 lines

I would like to split patches because we have two bugs indeed, and I prefer to get attention for both problems, I dont remember Neil acknowledged the length computation problem.

First and small patch, candidate for net-2.6 and stable (for 2.6.29) :

Then here is the patch on top on previous one.

Thanks to all

[PATCH] net: fix rtable leak in net/ipv4/route.c

Alexander V. Lukyanov found a regression in 2.6.29 and made a complete analysis found in http://bugzilla.kernel.org/show_bug.cgi?id=13339
Quoted here because its a perfect one :

begin_of_quotation
2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.
end_of_quotation

Problematic commit is 1080d709fb9d8cd4392f93476ee46a9d6ea05a5b (net: implement emergency route cache rebulds when gc_elasticity is exceeded)

Trying to keep dst_entries ordered is too complex and breaks the fact that order should depend on the frequency of use for garbage collection.

Quoted 7 lines

A possible fix is to make rt_intern_hash() simpler, and only makes rt_check_expire() a litle bit smarter, being able to cope with an arbitrary entries order. The added loop is running on cache hot data, while cpu is prefetching next object, so should be unnoticied.

maintainer
#16 lore raw

Re: [PATCH] net: fix rtable leak in net/ipv4/route.c

From: Neil Horman <[email protected]>
Date: Wed, 20 May 2009 06:48:38 -0400

Quoted 2 lines · Eric Dumazet
Quoted 1 line

[PATCH] net: fix rtable leak in net/ipv4/route.c

...

Quoted 4 lines
Quoted 2 lines

Also applied and queued up for -stable, thanks!

Acked-by on v1 1/1
#17 lore raw

Re: [PATCH] net: fix length computation in rt_check_expire()

In reply to Eric Dumazet
Quoted 34 lines · Eric Dumazet
Quoted 15 lines · David Miller

From: Neil Horman <[email protected]>
Date: Tue, 19 May 2009 15:24:50 -0400

Quoted 9 lines
Quoted 4 lines

Moving whole group in front would defeat the purpose of move, actually, since rank in chain is used to decay the timeout in garbage collector. (search for tmo >>= 1; )

Argh, so the list is implicitly ordered by expiration time. That really defeats the entire purpose of doing grouping in the ilst at all. If thats the case, then I agree, its probably better to to take the additional visitation hit in in check_expire above than to try and preserve ordering.

Yes, this seems best.

Quoted 9 lines

I was worried that somehow the ordering also influences lookups, because the TOS bits don't go into the hash so I worried that it would be important that explicit TOS values appear before wildcard ones. But it doesn't appear that this is an issue, we don't have wildcard TOSs in the rtable entries, they are always explicit.

So I would like to see an explicit final patch from Eric so we can get this fixed now.

I would like to split patches because we have two bugs indeed, and I prefer to get attention for both problems, I dont remember Neil acknowledged the length computation problem.

First and small patch, candidate for net-2.6 and stable (for 2.6.29) :

Thank you

Quoted 8 lines

[PATCH] net: fix length computation in rt_check_expire()

rt_check_expire() computes average and standard deviation of chain lengths, but not correclty reset length to 0 at beginning of each chain. This probably gives overflows for sum2 (and sum) on loaded machines instead of meaningful results.

Quoted 1 line
maintainer
#18 lore raw

Re: [PATCH] net: fix length computation in rt_check_expire()

From: Neil Horman <[email protected]>
Date: Wed, 20 May 2009 06:27:54 -0400

Quoted 11 lines · Eric Dumazet
Quoted 8 lines

[PATCH] net: fix length computation in rt_check_expire()

rt_check_expire() computes average and standard deviation of chain lengths, but not correclty reset length to 0 at beginning of each chain. This probably gives overflows for sum2 (and sum) on loaded machines instead of meaningful results.

Applied and queued up for -stable.

#19 lore raw
In reply to Eric Dumazet
Quoted 27 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 14 lines

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 7 lines
Quoted 3 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

Of course, it helps if I attach the patch :)

include/net/dst.h +1 -0
index 6be3b08..a39db6d 100644
@@ -47,6 +47,7 @@ struct dst_entry
 #define DST_NOXFRM		2
 #define DST_NOPOLICY		4
 #define DST_NOHASH		8
+#define DST_GRPLDR		16
 	unsigned long		expires;
 
 	unsigned short		header_len;	/* more space at head required */
net/ipv4/route.c +11 -3
index c4c60e9..0120f0e 100644
@@ -610,6 +610,8 @@ static inline int ip_rt_proc_init(void)
 
 static inline void rt_free(struct rtable *rt)
 {
+	if (rt->u.dst.flags & DST_GRPLDR)
+		rt->u.dst.rt_next->u.dst.flag |= DST_GRPLDR;
 	call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
 }
 
@@ -1143,8 +1145,11 @@ restart:
 		 * relvant to the hash function together, which we use to adjust
 		 * our chain length
 		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
+		if (!*rthi && *rthp && 
+		    compare_hash_inputs(&(*rthp)->fl, &rt->fl) &&
+		    (cand != rth))
 			rthi = rth;
+		}
 	}
 
 	if (cand) {
@@ -1205,11 +1210,14 @@ restart:
 		}
 	}
 
-	if (rthi)
+	if (rthi) {
 		rt->u.dst.rt_next = rthi->u.dst.rt_next;
-	else
+		rthi->u.dst.flags &= ~(DST_GRPLDR);
+	} else
 		rt->u.dst.rt_next = rt_hash_table[hash].chain;
 
+	rt->u.dst.flags |= DST_GRPLDR;
+
 #if RT_CACHE_DEBUG >= 2
 	if (rt->u.dst.rt_next) {
 		struct rtable *trt;
#20 lore raw
Quoted 72 lines · Neil Horman
Quoted 27 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 14 lines

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 7 lines
Quoted 3 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

Of course, it helps if I attach the patch :)

include/net/dst.h +1 -0
index 6be3b08..a39db6d 100644
@@ -47,6 +47,7 @@ struct dst_entry
 #define DST_NOXFRM		2
 #define DST_NOPOLICY		4
 #define DST_NOHASH		8
+#define DST_GRPLDR		16
 	unsigned long		expires;
 
 	unsigned short		header_len;	/* more space at head required */
net/ipv4/route.c +2 -0
index c4c60e9..0120f0e 100644
@@ -610,6 +610,8 @@ static inline int ip_rt_proc_init(void)
 
 static inline void rt_free(struct rtable *rt)
 {
+	if (rt->u.dst.flags & DST_GRPLDR)
+		rt->u.dst.rt_next->u.dst.flag |= DST_GRPLDR;
 	call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
 }
 

net/ipv4/route.c restart: · line 1151

Quoted 8 lines
net/ipv4/route.c +3 -1
@@ -1143,8 +1145,11 @@ restart:
 		 * relvant to the hash function together, which we use to adjust
 		 * our chain length
 		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
+		if (!*rthi && *rthp && 
+		    compare_hash_inputs(&(*rthp)->fl, &rt->fl) &&
+		    (cand != rth))
 			rthi = rth;

Does it really prevent cand == rthi in the next loop?

I didn't check Eric's patch yet, but I really don't know what's wrong with something as simple as below for -stable, until "proper" fix is analyzed and tested.

Jarek P.
---

 net/ipv4/route.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)
net/ipv4/route.c +2 -0
index c4c60e9..f4e6c7a 100644
@@ -1157,6 +1157,8 @@ restart:
 		if (chain_length > ip_rt_gc_elasticity) {
 			*candp = cand->u.dst.rt_next;
 			rt_free(cand);
+			if (rthi == cand)
+				rthi = NULL;
 		}
 	} else {
 		if (chain_length > rt_chain_length_max) {
#21 lore raw
Quoted 72 lines · Jarek Poplawski
Quoted 71 lines · Neil Horman
Quoted 27 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

Quoted 14 lines

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 7 lines
Quoted 3 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

Of course, it helps if I attach the patch :)

include/net/dst.h +1 -0
index 6be3b08..a39db6d 100644
@@ -47,6 +47,7 @@ struct dst_entry
 #define DST_NOXFRM		2
 #define DST_NOPOLICY		4
 #define DST_NOHASH		8
+#define DST_GRPLDR		16
 	unsigned long		expires;
 
 	unsigned short		header_len;	/* more space at head required */
net/ipv4/route.c +2 -0
index c4c60e9..0120f0e 100644
@@ -610,6 +610,8 @@ static inline int ip_rt_proc_init(void)
 
 static inline void rt_free(struct rtable *rt)
 {
+	if (rt->u.dst.flags & DST_GRPLDR)
+		rt->u.dst.rt_next->u.dst.flag |= DST_GRPLDR;
 	call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
 }
 
Quoted 12 lines

net/ipv4/route.c restart: · line 1151

Quoted 9 lines
net/ipv4/route.c +3 -1
@@ -1143,8 +1145,11 @@ restart:
 		 * relvant to the hash function together, which we use to adjust
 		 * our chain length
 		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
+		if (!*rthi && *rthp && 
+		    compare_hash_inputs(&(*rthp)->fl, &rt->fl) &&
+		    (cand != rth))
 			rthi = rth;

Does it really prevent cand == rthi in the next loop?

Yes, because cand and rthi are inspected during the same loop iteration, and both assigned from rth. since I added a check which requires !rthi (which is actually a bug above that I need to fix), once rthi is set, it won't be moved, and on the next iteration, if cand is assigned, it is assigned to rth, which (being the next iteration), is a different rt cache entry

Quoted 4 lines

I didn't check Eric's patch yet, but I really don't know what's wrong with something as simple as below for -stable, until "proper" fix is analyzed and tested.

Because the above fixes it without continuing to break the ordering. You're change below prevents the leak, but still allows for disordered lists to form, which IMHO doesn't really make it a candidate for -stable. I'd much rather fix both the leak and the ordering before pushing anything out

speaking of which, I'm going to ask again, I've been looking all morning, and I'm unable to find the move to front heuristic that you mentioned creates furthe list disordering. If you can point it out to me, I can complete my patch and present something for you to test more throughly.

Neil

Quoted 1 line
#22 lore raw
Quoted 1 line · Neil Horman

On Tue, May 19, 2009 at 07:17:03PM +0200, Jarek Poplawski wrote:

...

Quoted 53 lines
Quoted 25 lines
Quoted 25 lines
include/net/dst.h +1 -0
index 6be3b08..a39db6d 100644
@@ -47,6 +47,7 @@ struct dst_entry
 #define DST_NOXFRM		2
 #define DST_NOPOLICY		4
 #define DST_NOHASH		8
+#define DST_GRPLDR		16
 	unsigned long		expires;
 
 	unsigned short		header_len;	/* more space at head required */
net/ipv4/route.c +2 -0
index c4c60e9..0120f0e 100644
@@ -610,6 +610,8 @@ static inline int ip_rt_proc_init(void)
 
 static inline void rt_free(struct rtable *rt)
 {
+	if (rt->u.dst.flags & DST_GRPLDR)
+		rt->u.dst.rt_next->u.dst.flag |= DST_GRPLDR;
 	call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
 }
 
Quoted 12 lines

net/ipv4/route.c restart: · line 1151

Quoted 9 lines
net/ipv4/route.c +3 -1
@@ -1143,8 +1145,11 @@ restart:
 		 * relvant to the hash function together, which we use to adjust
 		 * our chain length
 		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
+		if (!*rthi && *rthp && 
+		    compare_hash_inputs(&(*rthp)->fl, &rt->fl) &&
+		    (cand != rth))
 			rthi = rth;

Does it really prevent cand == rthi in the next loop?

Yes, because cand and rthi are inspected during the same loop iteration, and both assigned from rth. since I added a check which requires !rthi (which is actually a bug above that I need to fix), once rthi is set, it won't be moved, and on the next iteration, if cand is assigned, it is assigned to rth, which (being the next iteration), is a different rt cache entry

Quoted 4 lines

I didn't check Eric's patch yet, but I really don't know what's wrong with something as simple as below for -stable, until "proper" fix is analyzed and tested.

Because the above fixes it without continuing to break the ordering. You're change below prevents the leak, but still allows for disordered lists to form, which IMHO doesn't really make it a candidate for -stable. I'd much rather fix both the leak and the ordering before pushing anything out

Quoted 4 lines

speaking of which, I'm going to ask again, I've been looking all morning, and I'm unable to find the move to front heuristic that you mentioned creates furthe list disordering. If you can point it out to me, I can complete my patch and present something for you to test more throughly.

As I've written already, your patch looks OK to me.

Thanks,
Jarek P.

#23 lore raw
In reply to Neil Horman

On Tue, May 19, 2009 at 01:45:04PM -0400, Neil Horman wrote:
...

Quoted 2 lines

I'm unable to find the move to front heuristic that you mentioned creates furthe list disordering. [...]

I'd only like to make it clear the analysis you refer to is by Alexander V. Lukyanov <[email protected]>

Jarek P.

#24 lore raw
Quoted 8 lines · Jarek Poplawski

On Tue, May 19, 2009 at 01:45:04PM -0400, Neil Horman wrote:
...

Quoted 2 lines

I'm unable to find the move to front heuristic that you mentioned creates furthe list disordering. [...]

I'd only like to make it clear the analysis you refer to is by Alexander V. Lukyanov <[email protected]>

Ok, thank you for giving credit where its due :). Alexander, can you point out the location of the move-to-front heruistic that you mention in your analysis?

Neil

Quoted 2 lines

Jarek P.

#25 lore raw
Quoted 2 lines · Neil Horman

Alexander, can you point out
the location of the move-to-front heruistic that you mention in your analysis?

It's near /* Put it first */ comment (if I read the code correctly).

Signature · 1 line
   Alexander..
#26 lore raw
In reply to Jarek Poplawski
Quoted 1 line · Jarek Poplawski

On Tue, May 19, 2009 at 12:23:30PM -0400, Neil Horman wrote:

...

Quoted 28 lines
Quoted 28 lines

Of course, it helps if I attach the patch :)

include/net/dst.h +1 -0
index 6be3b08..a39db6d 100644
@@ -47,6 +47,7 @@ struct dst_entry
 #define DST_NOXFRM		2
 #define DST_NOPOLICY		4
 #define DST_NOHASH		8
+#define DST_GRPLDR		16
 	unsigned long		expires;
 
 	unsigned short		header_len;	/* more space at head required */
net/ipv4/route.c +2 -0
index c4c60e9..0120f0e 100644
@@ -610,6 +610,8 @@ static inline int ip_rt_proc_init(void)
 
 static inline void rt_free(struct rtable *rt)
 {
+	if (rt->u.dst.flags & DST_GRPLDR)
+		rt->u.dst.rt_next->u.dst.flag |= DST_GRPLDR;
 	call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
 }
 
Quoted 11 lines

net/ipv4/route.c restart: · line 1151

Quoted 9 lines
net/ipv4/route.c +3 -1
@@ -1143,8 +1145,11 @@ restart:
 		 * relvant to the hash function together, which we use to adjust
 		 * our chain length
 		 */
-		if (*rthp && compare_hash_inputs(&(*rthp)->fl, &rt->fl))
+		if (!*rthi && *rthp && 
+		    compare_hash_inputs(&(*rthp)->fl, &rt->fl) &&
+		    (cand != rth))
 			rthi = rth;

Does it really prevent cand == rthi in the next loop?

Hmm.. It looks OK yet!

Sorry,
Jarek P.

#27 lore raw
In reply to Eric Dumazet
Quoted 37 lines · Eric Dumazet
Quoted 19 lines · Jarek Poplawski
Quoted 9 lines · Stephen Hemminger

Begin forwarded message:

Date: Mon, 18 May 2009 14:10:20 GMT
From: [email protected]
To: [email protected]
Subject: [Bug 13339] New: rtable leak in ipv4/route.c

http://bugzilla.kernel.org/show_bug.cgi?id=13339

...

Quoted 8 lines

2.6.29 patch has introduced flexible route cache rebuilding. Unfortunately the patch has at least one critical flaw, and another problem.

rt_intern_hash calculates rthi pointer, which is later used for new entry insertion. The same loop calculates cand pointer which is used to clean the list. If the pointers are the same, rtable leak occurs, as first the cand is removed then the new entry is appended to it.

Quoted 6 lines
Quoted 6 lines

This leak leads to unregister_netdevice problem (usage count > 0).

Another problem of the patch is that it tries to insert the entries in certain order, to facilitate counting of entries distinct by all but QoS parameters. Unfortunately, referencing an existing rtable entry moves it to list beginning, to speed up further lookups, so the carefully built order is destroyed.

We could change rt_check_expire() to be smarter and handle any order in chains.

This would let rt_intern_hash() be simpler.

As its a more performance critical path, all would be good :)

Quoted 4 lines
Quoted 3 lines

For the first problem the simplest patch it to set rthi=0 when rthi==cand, but it will also destroy the ordering.

Quoted 7 lines
Quoted 3 lines

I think fixing this bug fast is more important than this ordering or counting. Could you send your patch proposal?

Here is mine, only compiled, not tested yet.

All credits for Stephen for doing the analysis of course :)

- All credits for Stephen for doing the analysis of course :)
+ All credits for Alexander V. Lukyanov for doing the analysis of course :)

Jarek P.