Skip to contentSkip to conversation

iptables very slow after commit784544739a25c30637397ace5489eeb6e15d7d49

PATCH In review Jeff Chua 22 participants 218 messages Apr 10, 2009 – May 1, 2009 Page 2 of 2

Subsystems (4)
lore
Share & tools
lore
#117 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Lai Jiangshan
Quoted 20 lines · On Tue, 21 Apr 2009 13:22:27 +0800 Lai Jiangshan <[email protected]> wrote:
Quoted 19 lines · Eric Dumazet
Quoted 17 lines · Lai Jiangshan
Quoted 4 lines · Stephen Hemminger
net/netfilter/x_tables.c +4 -0
+/**
+ * xt_table_info_rdlock_bh - recursive read lock for xt table info
+ *
+ * Table processing calls this to hold off any changes to table

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697

Quoted 10 lines
net/netfilter/x_tables.c +10 -0
+ * (on current CPU). Always leaves with bottom half disabled.
+ * If called recursively, then assumes bh/preempt already disabled.
+ */
+void xt_info_rdlock_bh(void)
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))

Maybe I missed something. I think softirq may be still enabled here. So what happen when xt_info_rdlock_bh() called recursively here?

Quoted 5 lines
Quoted 2 lines

well, first time its called, you are right softirqs are enabled until the point we call spin_lock_bh(), right after this line :

xt_info_rdlock_bh() called recursively here will enter the critical region without &__get_cpu_var(xt_info_locks)->lock.

NO spin_lock_bh always does a preempt_disable

xt_info_rdlock_bh (depth = -1)
+1 preempt_disable
spin_lock_bh
+1 preempt_disable
-1 preempt_enable_no_resched
---
+1

Second call preempt_count=1 (depth = 0)
xt_info_rdlock_bh
+1 preempt_disable
-1 preempt_enable_no_resched
---

Result is preempt_count=1 (depth = 1)

Now lets do unlocks
xt_info_rdunlock_bh preempt_count=1 depth=1
does nothing
xt_info_rdunlock_bh preempt_count=1 depth = 0
-1 spin_unlock_bh

Resulting preempt_count=0 depth = -1

Same as starting point.

Quoted 9 lines

Because xt_info_rdlock_bh() called recursively here sees lock->depth >= 0, and "++lock->depth == 0" is false.

Quoted 6 lines
Quoted 4 lines

Review

Quoted 4 lines
(quoted diff) +2 -0
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();

After this line, both softirqs and preempt are disabled.

No. spin_lock_bh on first pass does this.

Quoted 27 lines
Quoted 8 lines

Future calls to this function temporarly raise preemptcount and decrease it. (Null effect)

Quoted 5 lines

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702

Quoted 3 lines
net/netfilter/x_tables.c +3 -0
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);
+

Is this OK for you:

Quoted 14 lines
Quoted 5 lines

void xt_info_rdlock_bh(void)

{
	struct xt_info_lock *lock;

	local_bh_disable();

well, Stephen was trying to not change preempt count for the 2nd, 3rd, 4th?... invocation of this function. This is how I understood the code.

Quoted 5 lines
	lock = &__get_cpu_var(xt_info_locks);
	if (likely(++lock->depth == 0))
		spin_lock(&lock->lock);
}

Sorry for it.
Is this OK:

void xt_info_rdlock_bh(void)

Quoted 10 lines
{
	struct xt_info_lock *lock;

	local_bh_disable();
	lock = &__get_cpu_var(xt_info_locks);
	if (likely(++lock->depth == 0))
		spin_lock(&lock->lock);
	else
		local_bh_enable();
}

Unnecessary.

Quoted 4 lines

I did not think things carefully enough, and I do know nothing about ip/ip6/arp.

Lai

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

#118 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 13 lines · Stephen Hemminger
Quoted 2 lines

xt_info_rdlock_bh() called recursively here will enter the critical region without &__get_cpu_var(xt_info_locks)->lock.

NO spin_lock_bh always does a preempt_disable

xt_info_rdlock_bh (depth = -1)
+1 preempt_disable
spin_lock_bh
+1 preempt_disable
-1 preempt_enable_no_resched
---
+1

Quoted 6 lines

Second call preempt_count=1 (depth = 0)
xt_info_rdlock_bh
+1 preempt_disable
-1 preempt_enable_no_resched
---

I think I had made you mistook my email.

The preempt_count is correct, but I thought about lock-save:
we must hold &__get_cpu_var(xt_info_locks)->lock when we enter the read-side critical region.

--------------------
xt_info_rdlock_bh() (depth = -1)
preempt_disable()
depth++
==========>interrupt here
==========>
==========>xt_info_rdlock_bh() (depth = 0)

  ==========>  preempt_disable()
  ==========>  depth++
  ==========>  preempt_enable_no_resched()

==========>
==========>enter the read-side critical region *without* lock. ==========> it may get trashy data.
==========>
==========>xt_info_rdunlock_bh()
==========>
==========>interrupt return.
spin_lock_bh()
preempt_enable_no_resched()

enter the read-side critical region *with* lock.

xt_info_rdunlock_bh().
----------------------

So I asked:

Quoted 7 lines

+void xt_info_rdlock_bh(void)

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697

Quoted 6 lines
net/netfilter/x_tables.c +6 -0
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))

So what happen when xt_info_rdlock_bh() called recursively here?

Quoted 5 lines

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702

Quoted 5 lines
net/netfilter/x_tables.c +5 -0
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);
+

----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)

void xt_info_rdlock_bh(void)

{
	unsigned long flags;
	struct xt_info_lock *lock;

	local_irq_save(flags);
	lock = &__get_cpu_var(xt_info_locks);
	if (likely(++lock->depth == 0))
		spin_lock_bh(&lock->lock);
	local_irq_restore(flags);
}

Lai

#119 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Hi.

Quoted 21 lines · Lai Jiangshan
Quoted 7 lines

+void xt_info_rdlock_bh(void)

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697

Quoted 6 lines
net/netfilter/x_tables.c +6 -0
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))

So what happen when xt_info_rdlock_bh() called recursively here?

Quoted 5 lines

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702

Quoted 5 lines
net/netfilter/x_tables.c +5 -0
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);
+

----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)

void xt_info_rdlock_bh(void)

Quoted 10 lines
{
	unsigned long flags;
	struct xt_info_lock *lock;

	local_irq_save(flags);
	lock = &__get_cpu_var(xt_info_locks);
	if (likely(++lock->depth == 0))
		spin_lock_bh(&lock->lock);
	local_irq_restore(flags);
}

Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.

Stephen, should preempt_disable() be replaced with local_bh_disable() to prevent softirq to race on the same cpu for the lock's depth field? Or can it be made atomic?

Signature · 1 line
	Evgeniy Polyakov
#120 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 5 lines · Evgeniy Polyakov

Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.

A question:

softirq is always not nesting. Why we need recursive lock?

Lai.

maintainer
#121 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

From: Lai Jiangshan <[email protected]>
Date: Tue, 21 Apr 2009 16:42:40 +0800

Quoted 1 line

softirq is always not nesting. Why we need recursive lock?

Netfilter itself, is nesting.

When using bridging netfilter, iptables can be entered twice in the same call chain.

#122 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Evgeniy Polyakov
Quoted 33 lines · Evgeniy Polyakov

Hi.

Quoted 19 lines · Lai Jiangshan
Quoted 7 lines

+void xt_info_rdlock_bh(void)

Review

Quoted 6 lines
(quoted diff) +6 -0
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))

So what happen when xt_info_rdlock_bh() called recursively here?

Quoted 5 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);
+

----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)

void xt_info_rdlock_bh(void)

Quoted 10 lines
{
	unsigned long flags;
	struct xt_info_lock *lock;

	local_irq_save(flags);
	lock = &__get_cpu_var(xt_info_locks);
	if (likely(++lock->depth == 0))
		spin_lock_bh(&lock->lock);
	local_irq_restore(flags);
}
Quoted 8 lines

Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.

Stephen, should preempt_disable() be replaced with local_bh_disable() to prevent softirq to race on the same cpu for the lock's depth field? Or can it be made atomic?

Maybe just dont care about calling several time local_bh_disable() (since we were doing this in previous kernels anyway, we used to call read_lock_bh())

This shortens fastpath, is faster than local_irq_save()/local_irq_restore(), and looks better.

void xt_info_rdlock_bh(void)

{
	struct xt_info_lock *lock;

	local_bh_disable();

lock = &__get_cpu_var(xt_info_locks);
if (likely(++lock->depth == 0))
spin_lock(&lock->lock);
}

void xt_info_rdunlock_bh(void)

{
	struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks);

	BUG_ON(lock->depth < 0);
	if (likely(--lock->depth < 0))
		 spin_unlock(&lock->lock);
	local_bh_enable();
}
#123 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 5 lines · Eric Dumazet

Maybe just dont care about calling several time local_bh_disable() (since we were doing this in previous kernels anyway, we used to call read_lock_bh())

This shortens fastpath, is faster than local_irq_save()/local_irq_restore(), and looks better.

Yeah, given that non-nested locking is more likely condition, it will be even faster than preemption case.

Quoted 21 lines

void xt_info_rdlock_bh(void)

{
	struct xt_info_lock *lock;

	local_bh_disable();
(quoted diff) +0 -0
 	lock = &__get_cpu_var(xt_info_locks);
 	if (likely(++lock->depth == 0))
 		spin_lock(&lock->lock);

}

void xt_info_rdunlock_bh(void)

{
	struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks);

	BUG_ON(lock->depth < 0);
	if (likely(--lock->depth < 0))
		 spin_unlock(&lock->lock);
	local_bh_enable();
}
Signature · 1 line
	Evgeniy Polyakov
#124 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Eric Dumazet
Quoted 57 lines · Eric Dumazet
Quoted 32 lines · Evgeniy Polyakov

Hi.

Quoted 19 lines · Lai Jiangshan
Quoted 7 lines

+void xt_info_rdlock_bh(void)

Review

Quoted 6 lines
(quoted diff) +6 -0
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))

So what happen when xt_info_rdlock_bh() called recursively here?

Quoted 5 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);
+

----------
Is this OK? (Now I suppose we can enter the read-side critical region in irq context)

void xt_info_rdlock_bh(void)

Quoted 10 lines
{
	unsigned long flags;
	struct xt_info_lock *lock;

	local_irq_save(flags);
	lock = &__get_cpu_var(xt_info_locks);
	if (likely(++lock->depth == 0))
		spin_lock_bh(&lock->lock);
	local_irq_restore(flags);
}
Quoted 8 lines

Netfilter as long as other generic network pathes are never accessed from interrupt context, but your analysis looks right for the softirq case.

Stephen, should preempt_disable() be replaced with local_bh_disable() to prevent softirq to race on the same cpu for the lock's depth field? Or can it be made atomic?

Maybe just dont care about calling several time local_bh_disable() (since we were doing this in previous kernels anyway, we used to call read_lock_bh())

This shortens fastpath, is faster than local_irq_save()/local_irq_restore(), and looks better.

void xt_info_rdlock_bh(void)

{
	struct xt_info_lock *lock;

	local_bh_disable();
(quoted diff) +0 -0
 	lock = &__get_cpu_var(xt_info_locks);
 	if (likely(++lock->depth == 0))
 		spin_lock(&lock->lock);
Quoted 1 line

}

This two functions is OK. But...

Quoted 12 lines

void xt_info_rdunlock_bh(void)

{
	struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks);

	BUG_ON(lock->depth < 0);
	if (likely(--lock->depth < 0))
		 spin_unlock(&lock->lock);
	local_bh_enable();
}

David said:
Netfilter itself, is nesting.

When using bridging netfilter, iptables can be entered twice in the same call chain.

And Stephen said:
In this version, I was trying to use/preserve the optimizations that are done in spin_unlock_bh().

So:

void xt_info_rdlock_bh(void)

{
	struct xt_info_lock *lock;

	preempt_disable();
 	lock = &__get_cpu_var(xt_info_locks);
 	if (likely(lock->depth < 0))
 		spin_lock_bh(&lock->lock);
	/* softirq is disabled now */
	++lock->depth;
	preempt_enable_no_resched();
}

xt_info_rdunlock_bh() is the same as v11.

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

#125 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Eric Dumazet
Quoted 19 lines · Eric Dumazet
Quoted 17 lines · Lai Jiangshan
Quoted 4 lines · Stephen Hemminger
net/netfilter/x_tables.c +4 -0
+/**
+ * xt_table_info_rdlock_bh - recursive read lock for xt table info
+ *
+ * Table processing calls this to hold off any changes to table

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 697

Quoted 10 lines
net/netfilter/x_tables.c +10 -0
+ * (on current CPU). Always leaves with bottom half disabled.
+ * If called recursively, then assumes bh/preempt already disabled.
+ */
+void xt_info_rdlock_bh(void)
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))

Maybe I missed something. I think softirq may be still enabled here. So what happen when xt_info_rdlock_bh() called recursively here?

Quoted 4 lines

well, first time its called, you are right softirqs are enabled until the point we call spin_lock_bh(), right after this line :

Which context can enter the critical region?
Can irq and softirq? or softirq only?

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

#126 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Stephen Hemminger
Quoted 20 lines · Stephen Hemminger

This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested. It is sort of like existing kernel_lock, rwlock_t and even old 2.4 brlock.

"Reader" is ip/arp/ip6 tables rule processing which runs per-cpu. It needs to ensure that the rules are not being changed while packet is being processed.

"Writer" is used in two cases: first is replacing rules in which case all packets in flight have to be processed before rules are swapped, then counters are read from the old (stale) info. Second case is where counters need to be read on the fly, in this case all CPU's are blocked from further rule processing until values are aggregated.

The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).

Quoted 4 lines

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

I reviewed this patch believe its in quite good shape, thanks Stephen.

Then I tested it on a x86_32 8 cpus machine and got no obvious problem.

Hopefully, next rcu_bh (or whatever name is used) will permit us to switch back to pure RCU in 2.6.31

oprofile snapshot of a tbench session, with light iptables rules. (4 rules in INPUT chain, 3 rules on OUTPUT)

xt_info_rdlock_bh() uses 0.6786 % of cpu
xt_info_rdunlock_bh() uses 0.1743 % of cpu

CPU: Core 2, speed 3000.77 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100000

samples  cum. samples  %        cum. %     symbol name
1248350  1248350       11.3285  11.3285    copy_from_user
534049   1782399        4.8464  16.1749    copy_to_user
480898   2263297        4.3641  20.5390    __schedule
325581   2588878        2.9546  23.4936    ipt_do_table
312697   2901575        2.8377  26.3312    tcp_ack
309381   3210956        2.8076  29.1388    tcp_sendmsg
248238   3459194        2.2527  31.3915    tcp_v4_rcv
230405   3689599        2.0909  33.4824    tcp_transmit_skb
220638   3910237        2.0022  35.4847    ip_queue_xmit
217099   4127336        1.9701  37.4548    tcp_recvmsg
175885   4303221        1.5961  39.0509    tcp_rcv_established
173112   4476333        1.5710  40.6219    __switch_to
165138   4641471        1.4986  42.1205    sysenter_past_esp
149367   4790838        1.3555  43.4759    dst_release
138619   4929457        1.2579  44.7339    sched_clock_cpu
132724   5062181        1.2044  45.9383    lock_sock_nested
121353   5183534        1.1013  47.0396    nf_iterate
119205   5302739        1.0818  48.1214    netif_receive_skb
118859   5421598        1.0786  49.2000    release_sock
112597   5534195        1.0218  50.2218    __inet_lookup_established
112195   5646390        1.0181  51.2399    sys_socketcall
110018   5756408        0.9984  52.2383    tcp_write_xmit
106466   5862874        0.9662  53.2045    __alloc_skb
93386    5956260        0.8475  54.0519    dev_queue_xmit
89229    6045489        0.8097  54.8617    tcp_event_data_recv
85972    6131461        0.7802  55.6418    local_bh_enable
82882    6214343        0.7521  56.3940    skb_release_data
80898    6295241        0.7341  57.1281    ip_rcv
76380    6371621        0.6931  57.8213    skb_copy_datagram_iovec
74782    6446403        0.6786  58.4999    xt_info_rdlock_bh
73593    6519996        0.6678  59.1677    mod_timer
72884    6592880        0.6614  59.8291    sock_recvmsg
71789    6664669        0.6515  60.4806    __copy_skb_header
70560    6735229        0.6403  61.1209    fget_light
68756    6803985        0.6239  61.7449    get_page_from_freelist
68378    6872363        0.6205  62.3654    put_page
68042    6940405        0.6175  62.9829    ip_finish_output
67618    7008023        0.6136  63.5965    page_address
64894    7072917        0.5889  64.1854    tcp_cleanup_rbuf
Quoted 10 lines

---
CHANGES
- optimize for UP
- disable bottom half in info_rdlock
- prevent preempt count overflow
- turn off lockdep in writer to avoid bogus warning
- optimize unlock_bh

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

#127 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

On Tue, Apr 21, 2009 at 06:59:29AM +0200, Eric Dumazet wrote:

[ . . . ]

Quoted 2 lines

Hopefully, next rcu_bh (or whatever name is used) will permit us to switch back to pure RCU in 2.6.31

My excursion in to rcu_fgp can be thought of as a training exercise for doing this, though perhaps others are also working on an upgraded rcu_bh as well.

Thanx, Paul

#128 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Stephen Hemminger

My silly opinion about lockdep in this patch:

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 672

Quoted 3 lines
net/netfilter/x_tables.c +3 -0
+
+struct xt_info_lock {
+	spinlock_t 	   lock;

+ struct lock_class_key key;

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 680

Quoted 8 lines
net/netfilter/x_tables.c +8 -0
+	int   	   	   depth;	/* # readers - 1 */
+};
+static DEFINE_PER_CPU(struct xt_info_lock, xt_info_locks);
+
+
+static inline void xt_info_lock_init(struct xt_info_lock *lock)
+{
+	spin_lock_init(&lock->lock);

+ lockdep_set_class(&lock->lock, &lock->key);

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 683

Quoted 3 lines
net/netfilter/x_tables.c +3 -0
+	lock->depth = -1;
+}
+

And remove lockdep_xxx()s.

#129 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Stephen Hemminger

Ok, so others already pointed out how dangerous/buggy this looks, but I'd like to strengthen that a bit more:

Quoted 9 lines · Stephen Hemminger
net/netfilter/x_tables.c +9 -0
+
+/**
+ * xt_table_info_rdlock_bh - recursive read lock for xt table info
+ *
+ * Table processing calls this to hold off any changes to table
+ * (on current CPU). Always leaves with bottom half disabled.
+ * If called recursively, then assumes bh/preempt already disabled.
+ */
+void xt_info_rdlock_bh(void)

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 701

Quoted 10 lines
net/netfilter/x_tables.c +10 -0
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);

This function is FUCKED UP.

It's total crap for several reasons"

- the already-mentioned race with bottom half locking.

If bottom halfs aren't already disabled, then if a bottom half comes in after the "++lock->depth" and before the spin_lock_bh(), then you will have no locking AT ALL for the processing of that bottom half - it will just increment the lock depth again, and nobody will have locked anything at all.

And if for some reason, you can prove that bottom half processing is already disabled, then ALL THAT OTHER CRAP is just that - CRAP. The whole preemption disabling, the whole "_bh()" thing, everything.

So either it's horribly buggy, or it's horribly broken and pointless. Take your pick.

- the total lack of comments. Why does that "count" protect anything? It's not a recursive lock, since there is no ownership (two independent accessors could call this and both "get" the lock), so you had damn well better create some big-ass comments about why it's ok in this case, and what the rules are that make it ok.

So DON'T GO AROUND CALLING IT A RECURSIVE LOCK! Don't write comments that are TOTAL AND UTTER SH*T! Just DON'T!

It's a "reader lock". It's not "recursive". It never was recursive, it never will be, and calling it that is just a sign that whoever wrote the function is a moron and doesn't know what he is doing. STOP DOING THIS!

- that _idiotic_ "preempt_enable_no_resched()". F*ck me, but the comment already says that preemption is disabled when exiting, so why does it even bother to enable it? Why play those mindless games with preemption counts, knowing that they are bogus?

Do it readably. Disable preemption first, and just re-enable it at UNLOCK time. No odd pseudo-reenables anywhere.

Oh, I know very well that the spli-locking will disable preemption, so it's "correct" to play those games, but the point is, it's just damn stupid and annoying. It just makes the source code actively _misleading_ to see crap like that - it looks like you enabled preemption, when in fact the code very much on purpose does _not_ enable preemption at all.

In other words, I really REALLY hate that patch. I think it looks slightly better than Eric Dumazet's original patch (at least the locking subtlety is now in a function of its own and _could_ be commented upon sanely and if it wasn't broken it might be acceptable), but quite frankly, I'd still horribly disgusted with the crap.

Why are you doing this insane thing? If you want a read-lock, just use the damned read-write locks already! Ad far as I can tell, this lock is in _no_ way better than just using those counting reader-writer locks, except it is open-coded and looks buggy.

There is basically _never_ a good reason to re-implement locking
primitives: you'll just introduce bugs. As proven very ably by the amount of crap above in what is supposed to be a very simple function.

If you want a counting read-lock (in _order_ to allow recursion, but not because the lock itself is somehow recursive!), then that function should look like this:

	void xt_info_rdlock_bh(void)
	{
		struct xt_info_lock *lock

		local_bh_disable();
		lock = &__get_cpu_var(xt_info_locks);
		read_lock(&lock->lock);
	}

And then the "unlock" should be the reverse. No games, no crap, and hopefully then no bugs. And if you do it that way, you don't even need the comments, although quite frankly, it probably makes a lot of sense to talk about the interaction between "local_bh_disable()" and the preempt count, and why you're not using "read_lock_bh()".

And if you don't want a read-lock, then fine - don't use a read-lock, do something else. But then don't just re-implement it (badly) either and call it something else!

Linus

PS: Ingo, why do the *_bh() functions in kernel/spinlock.c do _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the above rdlock_bh too.

#130 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 109 lines · On Tue, 21 Apr 2009 09:13:52 -0700 (PDT) Linus Torvalds…

Ok, so others already pointed out how dangerous/buggy this looks, but I'd like to strengthen that a bit more:

Quoted 9 lines · Stephen Hemminger
net/netfilter/x_tables.c +9 -0
+
+/**
+ * xt_table_info_rdlock_bh - recursive read lock for xt table info
+ *
+ * Table processing calls this to hold off any changes to table
+ * (on current CPU). Always leaves with bottom half disabled.
+ * If called recursively, then assumes bh/preempt already disabled.
+ */
+void xt_info_rdlock_bh(void)

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 701

Quoted 10 lines
net/netfilter/x_tables.c +10 -0
+{
+	struct xt_info_lock *lock;
+
+	preempt_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (likely(++lock->depth == 0))
+		spin_lock_bh(&lock->lock);
+	preempt_enable_no_resched();
+}
+EXPORT_SYMBOL_GPL(xt_info_rdlock_bh);

This function is FUCKED UP.

It's total crap for several reasons"

- the already-mentioned race with bottom half locking.

If bottom halfs aren't already disabled, then if a bottom half comes in after the "++lock->depth" and before the spin_lock_bh(), then you will have no locking AT ALL for the processing of that bottom half - it will just increment the lock depth again, and nobody will have locked anything at all.

And if for some reason, you can prove that bottom half processing is already disabled, then ALL THAT OTHER CRAP is just that - CRAP. The whole preemption disabling, the whole "_bh()" thing, everything.

So either it's horribly buggy, or it's horribly broken and pointless. Take your pick.

- the total lack of comments. Why does that "count" protect anything? It's not a recursive lock, since there is no ownership (two independent accessors could call this and both "get" the lock), so you had damn well better create some big-ass comments about why it's ok in this case, and what the rules are that make it ok.

So DON'T GO AROUND CALLING IT A RECURSIVE LOCK! Don't write comments that are TOTAL AND UTTER SH*T! Just DON'T!

It's a "reader lock". It's not "recursive". It never was recursive, it never will be, and calling it that is just a sign that whoever wrote the function is a moron and doesn't know what he is doing. STOP DOING THIS!

- that _idiotic_ "preempt_enable_no_resched()". F*ck me, but the comment already says that preemption is disabled when exiting, so why does it even bother to enable it? Why play those mindless games with preemption counts, knowing that they are bogus?

Do it readably. Disable preemption first, and just re-enable it at UNLOCK time. No odd pseudo-reenables anywhere.

Oh, I know very well that the spli-locking will disable preemption, so it's "correct" to play those games, but the point is, it's just damn stupid and annoying. It just makes the source code actively _misleading_ to see crap like that - it looks like you enabled preemption, when in fact the code very much on purpose does _not_ enable preemption at all.

In other words, I really REALLY hate that patch. I think it looks slightly better than Eric Dumazet's original patch (at least the locking subtlety is now in a function of its own and _could_ be commented upon sanely and if it wasn't broken it might be acceptable), but quite frankly, I'd still horribly disgusted with the crap.

Why are you doing this insane thing? If you want a read-lock, just use the damned read-write locks already! Ad far as I can tell, this lock is in _no_ way better than just using those counting reader-writer locks, except it is open-coded and looks buggy.

There is basically _never_ a good reason to re-implement locking
primitives: you'll just introduce bugs. As proven very ably by the amount of crap above in what is supposed to be a very simple function.

If you want a counting read-lock (in _order_ to allow recursion, but not because the lock itself is somehow recursive!), then that function should look like this:

	void xt_info_rdlock_bh(void)
	{
		struct xt_info_lock *lock

		local_bh_disable();
		lock = &__get_cpu_var(xt_info_locks);
		read_lock(&lock->lock);
	}

And then the "unlock" should be the reverse. No games, no crap, and hopefully then no bugs. And if you do it that way, you don't even need the comments, although quite frankly, it probably makes a lot of sense to talk about the interaction between "local_bh_disable()" and the preempt count, and why you're not using "read_lock_bh()".

And if you don't want a read-lock, then fine - don't use a read-lock, do something else. But then don't just re-implement it (badly) either and call it something else!

Quoted 6 lines

Linus

PS: Ingo, why do the *_bh() functions in kernel/spinlock.c do _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the above rdlock_bh too.

Ah a nice day, with Linus giving constructive feedback. Too bad he has to channel it out of the dark side.

#131 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 3 lines · Stephen Hemminger

Ah a nice day, with Linus giving constructive feedback. Too bad he has to channel it out of the dark side.

I already flamed that patch at least once before. People didn't react.

What do I have to do to make people listen? I'm sorry, but I'm not going to send you flowers with a card saying "Hope you do better next time!".

I realize that the flowers might be friendlier, but I have absolutely no incentive to be friendly to just bad code. I have even _less_ incentive when my first "that sucks" is apparently totally ignored. So now I spelled it out why it sucks, but I sure as hell didn't have any reason to be polite about it.

Linus

#132 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Linus Torvalds
Quoted 4 lines · Linus Torvalds

PS: Ingo, why do the *_bh() functions in kernel/spinlock.c do _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the above rdlock_bh too.

i think there might be (are?) uses of:

	spin_lock_bh(&some->lock);
	...
	spin_unlock(&some->lock);
	...
	local_bh_enable();

So we have to have two preemption control levels for that, as there's no knowledge at the spin_lock_bh() place whether it will be followed by a spin_unlock_bh() [in which case it would be safe to do SOFTIRQ_OFFSET only] - or by a spin_unlock() + local_bh_enable() pair..

[ That locking pattrn even makes a certain amount of sense: keep the
lock held for a short amount of time - then weaken locking to bh context exclusion only. ]

What we could do is an optimization to do a compound increase the preempt count by SOFTIRQ_OFFSET+1 - instead of a local_bh_disable()
+ preempt_disable()? Symmetrically we could do a compound decrease in the unlock case.

It might even be called: local_bh_preempt_disable() or so?

Ingo

#133 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Linus Torvalds

Subject: netfilter: use per-cpu recursive lock (v12)

This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.

The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

I don't like the NR_CPUS preempt count kludge, it is working around an issue that should be handled in a more generic way.

---
CHANGES
- go back to read/write lock
- reader case is now inline
- more comments
- always disables bottom half
- only play preempt count mindgames if really necessary
- add lockdep keys

 include/linux/netfilter/x_tables.h |   42 ++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  110 ++++++++-----------------------------
 net/ipv4/netfilter/ip_tables.c     |  110 +++++++------------------------------
 net/ipv6/netfilter/ip6_tables.c    |  108 ++++++++----------------------------
 net/netfilter/x_tables.c           |   77 ++++++++++++++++++-------
 5 files changed, 165 insertions(+), 282 deletions(-)
include/linux/netfilter/x_tables.h +37 -5
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,43 @@ extern void xt_proto_fini(struct net *ne
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+
+/*
+ * Per-CPU read/write lock. This makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since write must iterate over all
+ * possible CPU's. Readers read lock their per-cpu lock, and writers
+ * write lock on all CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing rules
+ *       all packets in flight have to be processed before rules are swapped,
+ *       then counters are read from the old (stale) info.
+ *
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	local_bh_disable();
+	read_lock(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+
+extern void xt_info_wrlock_bh(void);
+extern void xt_info_wrunlock_bh(void);
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/ip_tables.c +23 -87

169 lines not on this page · raw message

net/netfilter/x_tables.c +55 -22

117 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +25 -83

166 lines not on this page · raw message

net/ipv4/netfilter/arp_tables.c +25 -85

173 lines not on this page · raw message

#134 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 6 lines · Stephen Hemminger
net/netfilter/x_tables.c +6 -0
+void xt_info_wrlock_bh(void)
+{
+	unsigned int i;
+
+	local_bh_disable();
+	for_each_possible_cpu(i) {

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 683

Quoted 10 lines
net/netfilter/x_tables.c +10 -0
+		write_lock(&per_cpu(xt_info_locks, i));
+#if NR_CPUS > (PREEMPT_MASK - 1)
+		/*
+		 * Since spin_lock disables preempt, the following is
+		 * required to avoid overflowing the preempt counter
+		 */
+		preempt_enable_no_resched();
+#endif
+	}
+}

hm, this is rather ugly and it will make a lot of instrumentation code explode.

Why not use the obvious solution: a _single_ wrlock for global access and read_can_lock() plus per cpu locks in the fastpath?

That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized - on NUMA too) - and we will hold at most 1-2 locks at once!

Something like:

	__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

	DEFINE_PER_CPU(rwlock_t local_lock);


	void local_read_lock(void)
	{
	again:
		read_lock(&per_cpu(local_lock, this_cpu));

		if (unlikely(!read_can_lock(&global_wrlock))) {
			read_unlock(&per_cpu(local_lock, this_cpu));
			/*
			 * Just wait for any global write activity:
			 */
			read_unlock_wait(&global_wrlock);
			goto again;
		}
	}

	void global_write_lock(void)
	{
		write_lock(&global_wrlock);

		for_each_possible_cpu(i)
			write_unlock_wait(&per_cpu(local_lock, i));
	}

Note how nesting friendly this construct is: we dont actually _hold_ NR_CPUS locks all at once, we simply cycle through all CPUs and make sure they have our attention.

No preempt overflow. No lockdep explosion. A very fast and scalable read path.

Okay - we need to implement read_unlock_wait() and write_unlock_wait() which is similar to spin_unlock_wait(). The trivial first-approximation is:

	read_unlock_wait(x)
	{
		read_lock(x);
		read_unlock(x);
	}

	write_unlock_wait(x)
	{
		write_lock(x);
		write_unlock(x);
	}

Hm?

Ingo

#135 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 3 lines · Ingo Molnar

Why not use the obvious solution: a _single_ wrlock for global access and read_can_lock() plus per cpu locks in the fastpath?

Obvious is not the qualifier I would use :)

Brilliant yes :)

Quoted 7 lines

That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized - on NUMA too) - and we will hold at most 1-2 locks at once!

Something like:

Quoted 9 lines
	__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

	DEFINE_PER_CPU(rwlock_t local_lock);


	void local_read_lock(void)
	{
	again:
		read_lock(&per_cpu(local_lock, this_cpu));

Hmm... here we can see global_wrlock locked by on writer, while this cpu already called local_read_lock(), and calls again this function -> Deadlock, because we hold our local_lock locked.

Quoted 30 lines
		if (unlikely(!read_can_lock(&global_wrlock))) {
			read_unlock(&per_cpu(local_lock, this_cpu));
			/*
			 * Just wait for any global write activity:
			 */
			read_unlock_wait(&global_wrlock);
			goto again;
		}
	}

	void global_write_lock(void)
	{
		write_lock(&global_wrlock);

		for_each_possible_cpu(i)
			write_unlock_wait(&per_cpu(local_lock, i));
	}

Note how nesting friendly this construct is: we dont actually _hold_ NR_CPUS locks all at once, we simply cycle through all CPUs and make sure they have our attention.

No preempt overflow. No lockdep explosion. A very fast and scalable read path.

Okay - we need to implement read_unlock_wait() and write_unlock_wait() which is similar to spin_unlock_wait(). The trivial first-approximation is:

Quoted 12 lines
	read_unlock_wait(x)
	{
		read_lock(x);
		read_unlock(x);
	}

	write_unlock_wait(x)
	{
		write_lock(x);
		write_unlock(x);
	}

Very interesting and could be changed to use spinlock + depth per cpu.

-> we can detect recursion and avoid the deadlock, and we only use one atomic operation per lock/unlock pair in fastpath (this was the reason we tried hard to use a percpu spinlock during this thread)

__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

struct ingo_local_lock {
	spinlock_t lock;
	int depth;
};

DEFINE_PER_CPU(struct ingo_local_lock local_lock);

void local_read_lock(void)

{
	struct ingo_local_lock *lck;

	local_bh_and_preempt_disable();
	lck = &get_cpu_var(local_lock);
	if (++lck->depth > 0) /* already locked */
		return;
again:
	spin_lock(&lck->lock);

	if (unlikely(!read_can_lock(&global_wrlock))) {
		spin_unlock(&lck->lock);
		/*
		 * Just wait for any global write activity:
		 */
		read_unlock_wait(&global_wrlock);
		goto again;
	}
}

void global_write_lock(void)

{
	write_lock(&global_wrlock);

	for_each_possible_cpu(i)
		spin_unlock_wait(&per_cpu(local_lock, i));
}

Hmm ?

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

#136 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 8 lines · Eric Dumazet
Quoted 3 lines · Ingo Molnar

Why not use the obvious solution: a _single_ wrlock for global access and read_can_lock() plus per cpu locks in the fastpath?

Obvious is not the qualifier I would use :)

Brilliant yes :)

thanks :)

Quoted 11 lines
Quoted 11 lines

That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized
- on NUMA too) - and we will hold at most 1-2 locks at once!

Something like:

	__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

	DEFINE_PER_CPU(rwlock_t local_lock);
Quoted 8 lines
Quoted 4 lines
	void local_read_lock(void)
	{
	again:
		read_lock(&per_cpu(local_lock, this_cpu));

Hmm... here we can see global_wrlock locked by on writer, while this cpu already called local_read_lock(), and calls again this function -> Deadlock, because we hold our local_lock locked.

Yeah, indeed.

I wasnt really concentrating on the nested case, i was concentrating on the scalability and lock nesting angle. I think the code submitted here looks rather incestous in that regard.

Allowing nested locking _on the same CPU_ is asking for trouble. Use short critical sections and if there's any exclusion needed, use an irq-safe lock or a softirq-safe lock. Problem solved.

Quoted 40 lines

Very interesting and could be changed to use spinlock + depth per cpu.

-> we can detect recursion and avoid the deadlock, and we only use one atomic operation per lock/unlock pair in fastpath (this was the reason we tried hard to use a percpu spinlock during this thread)

__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

struct ingo_local_lock {
	spinlock_t lock;
	int depth;
};

DEFINE_PER_CPU(struct ingo_local_lock local_lock);

void local_read_lock(void)

{
	struct ingo_local_lock *lck;

	local_bh_and_preempt_disable();
	lck = &get_cpu_var(local_lock);
	if (++lck->depth > 0) /* already locked */
		return;
again:
	spin_lock(&lck->lock);

	if (unlikely(!read_can_lock(&global_wrlock))) {
		spin_unlock(&lck->lock);
		/*
		 * Just wait for any global write activity:
		 */
		read_unlock_wait(&global_wrlock);
		goto again;
	}
}

void global_write_lock(void)

Quoted 8 lines
{
	write_lock(&global_wrlock);

	for_each_possible_cpu(i)
		spin_unlock_wait(&per_cpu(local_lock, i));
}

Hmm ?

Yeah, this looks IRQ-nesting safe. But i really have to ask: why does this code try so hard to allow same-CPU nesting?

Nesting on the same CPU is _bad_ for several reasons:

1) Performance: it rips apart critical sections cache-wise. Instead of a nice:

       C1 ... C2 ... C3 ... C4

serial sequence of critical sections, we get:

       C1A ... ( C2 ) ... C1B ... C3 ... C4

Note that C1 got "ripped apart" into C1A and C1B with C2 injected
- reducing cache locality between C1A and C1B. We have to execute C1B no matter what, so we didnt actually win anything in terms of total work to do, by processing C2 out of order.

[ Preemption of work (which this kind of nesting is really about)
is _the anti-thesis of performance_, and we try to delay it as much as possible and we try to batch up as much as possible. For example the CPU scheduler will try _real_ hard to not preempt a typical workload, as long as external latency boundaries allow that. ]

2) Locking complexity and robustness. Nested locking is rank #1 in terms of introducing regressions into the kernel.

3) Instrumentation/checking complexity. Checking locking dependencies is good and catches a boatload of bugs before they hit upstream, and nested locks are supported but cause an exponential explosion in terms of dependencies to check.

Also, whenever instrumentation explodes is typically the sign of some true, physical complexity that has been introduced into the code. So it often is a canary for a misdesign at a fundamental level, not a failure in the instrumentation framework.

In the past i saw lock nesting often used as a wrong solution when the critical sections were too long (causing too long latencies for critical work - e.g. delaying hardirq completion processing unreasonably), or just plain out of confusion about the items above.

I dont know whether that's the case here - it could be one of the rare exceptions calling for a new locking primitive (which should then be introduced at the core kernel level IMHO) - i dont know the code that well.

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

#137 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 128 lines · Ingo Molnar
Quoted 6 lines · Eric Dumazet
Quoted 2 lines · Ingo Molnar

Why not use the obvious solution: a _single_ wrlock for global access and read_can_lock() plus per cpu locks in the fastpath?

Obvious is not the qualifier I would use :)

Brilliant yes :)

thanks :)

Quoted 11 lines
Quoted 11 lines

That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized
- on NUMA too) - and we will hold at most 1-2 locks at once!

Something like:

	__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

	DEFINE_PER_CPU(rwlock_t local_lock);
Quoted 7 lines
Quoted 4 lines
	void local_read_lock(void)
	{
	again:
		read_lock(&per_cpu(local_lock, this_cpu));

Hmm... here we can see global_wrlock locked by on writer, while this cpu already called local_read_lock(), and calls again this function -> Deadlock, because we hold our local_lock locked.

Yeah, indeed.

I wasnt really concentrating on the nested case, i was concentrating on the scalability and lock nesting angle. I think the code submitted here looks rather incestous in that regard.

Allowing nested locking _on the same CPU_ is asking for trouble. Use short critical sections and if there's any exclusion needed, use an irq-safe lock or a softirq-safe lock. Problem solved.

Quoted 40 lines

Very interesting and could be changed to use spinlock + depth per cpu.

-> we can detect recursion and avoid the deadlock, and we only use one atomic operation per lock/unlock pair in fastpath (this was the reason we tried hard to use a percpu spinlock during this thread)

__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

struct ingo_local_lock {
	spinlock_t lock;
	int depth;
};

DEFINE_PER_CPU(struct ingo_local_lock local_lock);

void local_read_lock(void)

{
	struct ingo_local_lock *lck;

	local_bh_and_preempt_disable();
	lck = &get_cpu_var(local_lock);
	if (++lck->depth > 0) /* already locked */
		return;
again:
	spin_lock(&lck->lock);

	if (unlikely(!read_can_lock(&global_wrlock))) {
		spin_unlock(&lck->lock);
		/*
		 * Just wait for any global write activity:
		 */
		read_unlock_wait(&global_wrlock);
		goto again;
	}
}

void global_write_lock(void)

Quoted 8 lines
{
	write_lock(&global_wrlock);

	for_each_possible_cpu(i)
		spin_unlock_wait(&per_cpu(local_lock, i));
}

Hmm ?

Yeah, this looks IRQ-nesting safe. But i really have to ask: why does this code try so hard to allow same-CPU nesting?

Nesting on the same CPU is _bad_ for several reasons:

1) Performance: it rips apart critical sections cache-wise. Instead of a nice:

       C1 ... C2 ... C3 ... C4

serial sequence of critical sections, we get:

       C1A ... ( C2 ) ... C1B ... C3 ... C4

Note that C1 got "ripped apart" into C1A and C1B with C2 injected
- reducing cache locality between C1A and C1B. We have to execute C1B no matter what, so we didnt actually win anything in terms of total work to do, by processing C2 out of order.

[ Preemption of work (which this kind of nesting is really about)
is _the anti-thesis of performance_, and we try to delay it as much as possible and we try to batch up as much as possible. For example the CPU scheduler will try _real_ hard to not preempt a typical workload, as long as external latency boundaries allow that. ]

2) Locking complexity and robustness. Nested locking is rank #1 in terms of introducing regressions into the kernel.

3) Instrumentation/checking complexity. Checking locking dependencies is good and catches a boatload of bugs before they hit upstream, and nested locks are supported but cause an exponential explosion in terms of dependencies to check.

Also, whenever instrumentation explodes is typically the sign of some true, physical complexity that has been introduced into the code. So it often is a canary for a misdesign at a fundamental level, not a failure in the instrumentation framework.

Quoted 5 lines

In the past i saw lock nesting often used as a wrong solution when the critical sections were too long (causing too long latencies for critical work - e.g. delaying hardirq completion processing unreasonably), or just plain out of confusion about the items above.

I agree with all this Ingo.

Quoted 4 lines

I dont know whether that's the case here - it could be one of the rare exceptions calling for a new locking primitive (which should then be introduced at the core kernel level IMHO) - i dont know the code that well.

The netfilter case is real simple Ingo, (note I did not use "obvious" here ;) )

netfilter in 2.6.2[0-9] used :

CPU 1

sofirq handles one packet from a NIC

ipt_do_table() /* to handle INPUT table for example, or FORWARD */ read_lock_bh(&a_central_and_damn_rwlock)
... parse rules
-> calling some netfilter sub-function
re-entering network IP stack to send some packet (say a RST packet)
...
ipt_do_table() /* to handle OUPUT table rules for example */ read_lock_bh() ; /* WE RECURSE here, but once in a while (if ever) */

This is one of the case, but other can happens with virtual networks, tunnels, ... and so on. (Stephen had some cases with KVM if I remember well)

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

I was pleased by your locking schem, that was *very* interesting, even if not yet ready.

1) We can discuss of how bad recursion is.

We know loopback_xmit() could be way faster if we could avoid queeing packet to softirq handler.
(Remember you and I suggested this patch some months ago ? Please remember David rejected this because of recursion and possibility to overflow stack)

So yes, people are aware of recursion problems.

2) We can discuss how bad rwlocks are

We did lot of work on last months to delete some of rwlocks we had in kernel. UDP stack for example dont use them anymore.

We tried to delete them on x_tables, but we must take care of ipt_do_table() nesting, that is legal on 2.6.30.
Maybe netfilter guys can work to avoid this nesting on 2.6.31,
I dont know how hard it is, definitly not 2.6.30 material.

Solutions were discussed many times and Stephen provided 13 versions of the patch. If this was that obvious, one or two iterations would have been OK.

3) About last patch (v13)
Stephen did not agreed with you (well... maybe after all ..), he only submitted again a previous version.

With linux-2.6.2[0-9], "iptables -L" used to block all cpus from entering netfilter because we did a write_lock_bh() on the central rwlock while folding counters.

On v13, we dont try to freeze whole x_table context, but cpu per cpu. Thats a minor change against previous versions, and should not lead to strange application behavior. Its so much scalable that we should accept this change.

#138 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

On 22-04-2009 10:53, Eric Dumazet wrote:
...

Quoted 3 lines

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

Right, looks like 100% (Scandinavian?!) troll. I wonder where is the admin of this mess...

Jarek P.

#139 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 9 lines · Jarek Poplawski

On 22-04-2009 10:53, Eric Dumazet wrote:
...

Quoted 4 lines

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

Right, looks like 100% (Scandinavian?!) troll. I wonder where is the admin of this mess...

You might disagree with me on an honest technical basis, but note that this kind of childish, knee-jerk reaction against dissenting people is what gives netdev its bad reputation.

Ingo

#140 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 10 lines · Ingo Molnar
Quoted 7 lines · Jarek Poplawski

On 22-04-2009 10:53, Eric Dumazet wrote:
...

Quoted 4 lines

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

Quoted 6 lines
Quoted 2 lines

Right, looks like 100% (Scandinavian?!) troll. I wonder where is the admin of this mess...

You might disagree with me on an honest technical basis, but note that this kind of childish, knee-jerk reaction against dissenting people is what gives netdev its bad reputation.

How did you find I disagree with you? There was nothing about you, neither anything technical. Actually, I forgot to mention I agree with Eric about your locking proposal.

Jarek P.

#141 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Eric Dumazet
Quoted 15 lines · Eric Dumazet

netfilter in 2.6.2[0-9] used :

CPU 1

sofirq handles one packet from a NIC

ipt_do_table() /* to handle INPUT table for example, or FORWARD */ read_lock_bh(&a_central_and_damn_rwlock)
... parse rules
-> calling some netfilter sub-function
re-entering network IP stack to send some packet (say a RST packet)
...
ipt_do_table() /* to handle OUPUT table rules for example */ read_lock_bh() ; /* WE RECURSE here, but once in a while (if ever) */

Quoted 8 lines

This is one of the case, but other can happens with virtual networks, tunnels, ... and so on. (Stephen had some cases with KVM if I remember well)

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

Again ... i dont know this code well, but you yourself describe it as "a_central_and_damn_rwlock" above.

"Central and damn" locks of any type, anywhere tend to cause such trouble.

Often they are mini-BKL's in the making. Here's some historic patterns:

1- First there's a convenient lock around a popular and useful
piece of data and code.

2- As popularity (and reach of code) grows, and some non-trivial
interaction ensues, a little bit of self-recursion is added to the mix (this is often easier to do than to fix the root cause of the problem) - making critical sections even easier to grow in size.

3- Then attempts are made to make it scale all (it's a popular
piece of code), it's extended along a per-cpu axis, but complexity of locking explode by taking a ton of locks all at once. The solution: yell at the lock validator for not allowing this (or for exploding due to the sheer mathematically large complexity of the locking rules). Frequent requests for an exclusion from those pesky validations are made, and various hacks are done to work it around. It's all the fault of the lock validator, of course.

4- At this point it's rarely a clean, tidy data lock anymore - it
tends to grow into a code lock nobody really knows how it works, except that it better be taken more often than not, badness may ensue otherwise. Nobody really knows when to take it, only that it should be taken widely enough, that it should be recursive enough to call even _more_ code from under it. Efforts to reduce critical section length are rebuffed with: "this adds unlocking and relocking overhead". And it should then all scale as well.

5- In the end it's a lock everyone curses but nobody is able to fix
anymore. "If it was easy to fix we'd have fixed it long ago already" kind of fatalist thinking becomes widespread.

We saw many examples of this in the past: beyond the BKL (which is a bit special as its more of an UP legacy - but which hurt us the most), we had the tasklist_lock which was problematic for a long time, then there's also the reiser3 locking which was extremely monolithic. [ i'm only naming safe examples here, where nobody will flame me =B-) ]

Whether this particular case applies is up to you. I see certain matches up to phase 3 or so - but i also see certain dissimilarities as well. Nor do i claim that it's easy to fix or improve.

Ingo

#142 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Eric Dumazet
Quoted 4 lines · Eric Dumazet

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

You don't _understand_ do you?

There is a huge difference between recursive code, and a recursive lock.

The netfilter code may need to occasionally re-enter itself. Nobody ever contested _that_ part.

What I have disagreed with the whole time is

(a) doing local ad-hoc locking primitives without any comments what-so-ever.

(b) Doing them _wrong_ in many cases

(c) Calling the _lock_ a "recursive" lock.

The fact that a lock works with recursion doesn't make it "recursive". That generally has a very special meaning for locking primitives, and means something else.

In contrast, a read-write lock actually has known properties, and we have existing locking mechanisms for those. And we call them read-write locks DESPITE THE FACT that the reading part can be done recursively.

If you call a read-write lock a "recursive" lock, then you're a moron. It simply is _not_ a recursive lock. And neither is the lock you actually implemented, even though you (and Stephen) continually call it that.

SO STOP CALLING IT A RECURSIVE LOCK. Look at your very own code: you can actually only use that lock in a recursive context in a _very_ specific place. Notice how it's only "recursive" when taken in the per-CPU context, but _not_ recursive when the filter-updating code ("writer") takes it?

Do you understand now? It really shouldn't be so hard for you.

Naming is important. Locking is important. You did both things wrong. You named your locks something incorrect and mis-leading that didn't actually describe them, and you did your own private locking code without then documenting what the rules for this special lock were.

Maybe in your world that's ok. But no, in mine it's not. I've seen too many damn _non-functioning_ locks to ever want to see stuff like that again.

Linus

#143 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 41 lines · Linus Torvalds
Quoted 3 lines · Eric Dumazet

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

You don't _understand_ do you?

There is a huge difference between recursive code, and a recursive lock.

The netfilter code may need to occasionally re-enter itself. Nobody ever contested _that_ part.

What I have disagreed with the whole time is

(a) doing local ad-hoc locking primitives without any comments what-so-ever.

(b) Doing them _wrong_ in many cases

(c) Calling the _lock_ a "recursive" lock.

The fact that a lock works with recursion doesn't make it "recursive". That generally has a very special meaning for locking primitives, and means something else.

In contrast, a read-write lock actually has known properties, and we have existing locking mechanisms for those. And we call them read-write locks DESPITE THE FACT that the reading part can be done recursively.

If you call a read-write lock a "recursive" lock, then you're a moron. It simply is _not_ a recursive lock. And neither is the lock you actually implemented, even though you (and Stephen) continually call it that.

SO STOP CALLING IT A RECURSIVE LOCK. Look at your very own code: you can actually only use that lock in a recursive context in a _very_ specific place. Notice how it's only "recursive" when taken in the per-CPU context, but _not_ recursive when the filter-updating code ("writer") takes it?

Do you understand now? It really shouldn't be so hard for you.

Quoted 10 lines

Naming is important. Locking is important. You did both things wrong. You named your locks something incorrect and mis-leading that didn't actually describe them, and you did your own private locking code without then documenting what the rules for this special lock were.

Maybe in your world that's ok. But no, in mine it's not. I've seen too many damn _non-functioning_ locks to ever want to see stuff like that again.

Linus,

I actually sent *one* buggy patch, and you already gave your feedback and NACK.

Fine

I even relayed this to Stephen suggesting him not calling this a recursive lock. (Note how I use 'suggesting' here)

So, what do you want from me ? Should I copy 100 times :

"I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron." "I should not call it a recursive lock. I shall not invent new locking infra. I am a moron."
...

OK done

Can we now proceed and continue ?

Thank you

#144 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 3 lines · Eric Dumazet

I actually sent *one* buggy patch, and you already gave your feedback and NACK.

Actually, the thing is, I don't even think your original patch was even buggy. The bug crept in later. I NAK'ed it not because it was buggy, but because of the ad-hoc'ness and the naming. Really.

And I actually even said so in my original rant:

'The fact that code "happens to work by mistake" (and I'm not saying that
your does - but it might just because of the per-cpu'ness of it [..]'

because your original patch still had the

	rcu_read_lock_bh();

in place before the whole

	rl = &__get_cpu_var(arp_tables_lock);
	if (likely(rl->count++ == 0))
		spin_lock(&rl->lock);

and that should have protected against both BH callers and preemption.

So I actually believe that your original patch probably worked fine (but as I said in my reaction to it, I thought it was almost by mistake and I wasn't going to review it)

So the actual _bug_ crept in later, when the RCU lock was removed, and the lock was cleaned up and separated into a function of its own.

And in fact, that is kind of my point: "uncommented locking with ad-hoc semantics is very fragile". Even _correct_ code ends up not being correct in the long run, because people don't realize all the subtle issues.

Quoted 4 lines

I even relayed this to Stephen suggesting him not calling this a recursive lock. (Note how I use 'suggesting' here)

So, what do you want from me ? Should I copy 100 times :

So I consider this thread ended from a technical standpoint.

[ That said, I will not be at all shocked to hear if people decide later
that the RCU method was better after all, and that even the per-cpu rwlock or spinlock is just too expensive. ]

My problem today (apart from the relatively minor issue of also wanting to get the commit log fixed up) is just that I see emails from you finding my reaction shocking and from Jarek Poplawski that seem to still think that I'm a troll.

Just because I pointed out real technical problems? Is that shocking or trolling?

Really - please go back to my _original_ email. No, it was not polite. But here's another quote from it:

"Because even if it works today, it's just a bug waiting to happen."

and dammit, I sent that out _before_ the very next version of the patch that actually _did_ introduce that exact bug.

So dammit - what part of my email was "shocking" or "trolling"? The part where I was right? Or what?

Linus

#145 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Linus Torvalds wrote, On 04/22/2009 07:18 PM:

...

Quoted 7 lines

My problem today (apart from the relatively minor issue of also wanting to get the commit log fixed up) is just that I see emails from you finding my reaction shocking and from Jarek Poplawski that seem to still think that I'm a troll.

Just because I pointed out real technical problems? Is that shocking or trolling?

Very funny! For newbies only: http://en.wikipedia.org/wiki/Troll_(Internet)

Actually, I admit you could be the best "Ozzy" Osbourne imposter instead. (At least at netdev.) Stephen's words seem to fit very well:

Quoted 2 lines

Ah a nice day, with Linus giving constructive feedback. Too bad he has to channel it out of the dark side.

Jarek P.

#146 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Eric Dumazet
Quoted 4 lines · Eric Dumazet

If this could be done without recursion, I am pretty sure netfilter and network guys would have done it. I found Linus reaction quite shocking IMHO, considering hard work done by all people on this.

Btw., i didnt find Linus's reaction shocking at all, nor did i understand it as any criticism of prior (and future) good work of the people involved. I found it to be what it was: a forceful (because repeated) criticism of a bad patch.

Ingo

#147 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Ingo Molnar
Quoted 14 lines · On Tue, 21 Apr 2009 21:10:07 +0200 Ingo Molnar <[email protected]> wrote:
Quoted 11 lines · Stephen Hemminger
net/netfilter/x_tables.c +11 -0
+void xt_info_wrlock_bh(void)
+{
+	unsigned int i;
+
+	local_bh_disable();
+	for_each_possible_cpu(i) {
+		write_lock(&per_cpu(xt_info_locks, i));
+#if NR_CPUS > (PREEMPT_MASK - 1)
+		/*
+		 * Since spin_lock disables preempt, the following is
+		 * required to avoid overflowing the preempt counter
Quoted 8 lines

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 683

Quoted 5 lines
net/netfilter/x_tables.c +5 -0
+		 */
+		preempt_enable_no_resched();
+#endif
+	}
+}

hm, this is rather ugly and it will make a lot of instrumentation code explode.

Better general solutions:
* use raw_spin_lock
* increase PREEMPT_BITS on 64 bit machine and limit to 128 CPU or less on 32 bit
* get rid of default preempt_disable in spin_lock

You choose. It is a general problem.

Quoted 20 lines

Why not use the obvious solution: a _single_ wrlock for global access and read_can_lock() plus per cpu locks in the fastpath?

That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized - on NUMA too) - and we will hold at most 1-2 locks at once!

Something like:

	__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

	DEFINE_PER_CPU(rwlock_t local_lock);


	void local_read_lock(void)
	{
	again:
		read_lock(&per_cpu(local_lock, this_cpu));

		if (unlikely(!read_can_lock(&global_wrlock))) {
Quoted 8 lines
			read_unlock(&per_cpu(local_lock, this_cpu));
			/*
			 * Just wait for any global write activity:
			 */
			read_unlock_wait(&global_wrlock);
			goto again;
		}
	}

Quit trying to be so damn f*cking cool. We don't build the software for locking instrumentation. Locking instrumentation needs to serve the kernel, not the other way around.

Your version fails for the case of nested local rules. Which was the whole reason I switched to read/writer locks.

CPU 1 CPU 2
local_read_lock
... global_write_lock
local_read_lock
Stuck...

CPU 2 is waiting for CPU 1 to get out of its nested table processing CPU 1 is waiting for write lock to get done

#148 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 26 lines · Stephen Hemminger
Quoted 17 lines

That way there's no global cacheline bouncing (just the _reading_ of a global cacheline - which will be nicely localized
- on NUMA too) - and we will hold at most 1-2 locks at once!

Something like:

	__cacheline_aligned DEFINE_RWLOCK(global_wrlock);

	DEFINE_PER_CPU(rwlock_t local_lock);


	void local_read_lock(void)
	{
	again:
		read_lock(&per_cpu(local_lock, this_cpu));

		if (unlikely(!read_can_lock(&global_wrlock))) {
Quoted 8 lines
			read_unlock(&per_cpu(local_lock, this_cpu));
			/*
			 * Just wait for any global write activity:
			 */
			read_unlock_wait(&global_wrlock);
			goto again;
		}
	}
Quoted 1 line

Quit trying to be so damn f*cking cool. [...]

You make it quite hard to give reasonable feedback to your code :-/ First you attack me personally here, then - 30 minutes later - in the next iteration of your patch, you do:

+ /* wait for each other cpu to see new table */
+ for_each_possible_cpu(i)
+ if (i != smp_processor_id()) {
+ xt_info_wrlock(i);
+ xt_info_wrunlock(i);
+ }

... which i have not seen in your previous patch and which looks awfully similar to the write_lock_wait() based primitive i suggested.

( Just open-coded in an ugly fashion and slower than a real, proper
wait-unlock would be, because it dirties all those locks needlessly. )

So you must have agreed with me to a certain degree - i just dont see that in any of the discussion. (you seem to totally disagree with me to the level of ridiculing me.) Which makes it hard to discuss this on a rational basis.

Quoted 1 line

Your version fails for the case of nested local rules. [...]

Yes, as Eric pointed it out, more than an hour before your reply. I find the nesting uninteresting (in fact i find it harmful - see my reply to Eric). If you were only interested in nesting then a plain old-fashioned rwlock would have done the job.

The detail that is interesting here is how to avoid the global rwlock cacheline bounce - not the recursion. (the same-CPU recursion is avoidable via proper design or workaround-able via a counter in so many ways)

Anyway, i'm back into lurker mode.

Ingo

#149 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Stephen Hemminger
Quoted 7 lines · Stephen Hemminger
net/netfilter/x_tables.c +7 -0
+void xt_info_wrunlock_bh(void)
+	__releases(xt_info_lock)
+{
+	unsigned int i;
+
+	for_each_possible_cpu(i) {
+#if NR_CPUS > (PREEMPT_MASK - 1)

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 702

Quoted 10 lines
net/netfilter/x_tables.c +10 -0
+		/*
+		 * Spin_unlock calls preempt_enable, but since we had
+		 * to adjust the count in xt_info_wrlock_bh, do it again
+		 */
+		preempt_disable();
+#endif
+		write_unlock(&per_cpu(xt_info_locks, i));
+	}
+	local_bh_enable();
+}

In the global/local lock scheme i proposed this would become:

	global_write_unlock(void)
	{
		write_unlock(&global_lock);
	}

As we dont hold the local locks during the write-locked critical section. No loop needed over CPUs, no preempt nesting complications, no lockdep complications, etc.

Ingo

#150 lore raw

PATCH 1/1 netfilter: use per-cpu recursive lock (v13)

This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.

The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

---
CHANGES
- reader and write now inline
- only acquire one cpu write lock at a time
- write lock pushed down into get_counters

 include/linux/netfilter/x_tables.h |   50 +++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  121 ++++++++++---------------------------
 net/ipv4/netfilter/ip_tables.c     |  120 +++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  120 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 +++++++++-------
 5 files changed, 174 insertions(+), 292 deletions(-)
include/linux/netfilter/x_tables.h +45 -5
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,51 @@ extern void xt_proto_fini(struct net *ne
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+
+/*
+ * Per-CPU read/write lock. This makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since write must iterate over all
+ * possible CPU's. Readers read lock their per-cpu lock, and writers
+ * write lock on all CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing rules
+ *       all packets in flight have to be processed before rules are swapped,
+ *       then counters are read from the old (stale) info.
+ *
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	local_bh_disable();
+	read_lock(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	write_lock(&per_cpu(xt_info_locks, cpu));
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+
+	write_unlock(&per_cpu(xt_info_locks, cpu));
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/ip_tables.c +31 -89

204 lines not on this page · raw message

net/netfilter/x_tables.c +30 -25

96 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +35 -85

204 lines not on this page · raw message

net/ipv4/netfilter/arp_tables.c +33 -88

210 lines not on this page · raw message

Reviewed-by on v1 1/1
#151 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v13)

Quoted 11 lines · Stephen Hemminger

This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.

The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

Looks good from a concurrency viewpoint!

Quoted 6 lines

---
CHANGES
- reader and write now inline
- only acquire one cpu write lock at a time

This is very good -- gets rid of problems with preemption nesting depth limitations and lockdep limitations. In addition, it gets rid of the period of time during which all packet processing might otherwise be blocked. Not a big deal on a small machine, but could be a real problem on a large one.

Very cool!!!

Quoted 45 lines

- write lock pushed down into get_counters

 include/linux/netfilter/x_tables.h |   50 +++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  121 ++++++++++---------------------------
 net/ipv4/netfilter/ip_tables.c     |  120 +++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  120 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 +++++++++-------
 5 files changed, 174 insertions(+), 292 deletions(-)
include/linux/netfilter/x_tables.h +18 -5
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,51 @@ extern void xt_proto_fini(struct net *ne
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+
+/*
+ * Per-CPU read/write lock. This makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since write must iterate over all
+ * possible CPU's. Readers read lock their per-cpu lock, and writers
+ * write lock on all CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing rules

include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *ne · line 461

Quoted 10 lines
include/linux/netfilter/x_tables.h +10 -0
+ *       all packets in flight have to be processed before rules are swapped,
+ *       then counters are read from the old (stale) info.
+ *
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	local_bh_disable();
+	read_lock(&__get_cpu_var(xt_info_locks));

Good, you do indeed need to prevent migration before you acquire this CPU's lock. Otherwise, you could have more than one CPU attempting to update the same counter.

Quoted 47 lines
include/linux/netfilter/x_tables.h +17 -0
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	write_lock(&per_cpu(xt_info_locks, cpu));
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+
+	write_unlock(&per_cpu(xt_info_locks, cpu));
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/ip_tables.c +4 -6
@@ -338,10 +338,9 @@ ipt_do_table(struct sk_buff *skb,
 	tgpar.hooknum = hook;
 
 	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
-
-	rcu_read_lock_bh();
-	private = rcu_dereference(table->private);
-	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+	xt_info_rdlock_bh();
+	private = table->private;
+	table_base = private->entries[smp_processor_id()];
 
 	e = get_entry(table_base, private->hook_entry[hook]);
 
@@ -436,8 +435,7 @@ ipt_do_table(struct sk_buff *skb,
 			e = (void *)e + e->next_offset;
 		}
 	} while (!hotdrop);
-
-	rcu_read_unlock_bh();
+	xt_info_rdunlock_bh();
 
 #ifdef DEBUG_ALLOW_ALL
 	return NF_ACCEPT;

net/ipv4/netfilter/ip_tables.c get_counters(const struct xt_table_info · line 900

Quoted 4 lines
net/ipv4/netfilter/ip_tables.c +0 -1
@@ -897,89 +895,39 @@ get_counters(const struct xt_table_info 
 	/* Instead of clearing (by a previous call to memset())
 	 * the counters and using adds, we set the counters
 	 * with data used by 'current' CPU
-	 * We dont care about preemption here.

Good. Of course, the reason we care about preemption here is that otherwise some other task could mess up this CPU's counters.

Bad for real-time response, but then again, what the heck are you doing updating netfilter rules while a system is running a real-time workload?

Quoted 205 lines
net/ipv4/netfilter/ip_tables.c +27 -82
 	 */
-	curcpu = raw_smp_processor_id();
+	local_bh_disable();
+	curcpu = smp_processor_id();
 
 	i = 0;
+	xt_info_wrlock(curcpu);
 	IPT_ENTRY_ITERATE(t->entries[curcpu],
 			  t->size,
 			  set_entry_to_counter,
 			  counters,
 			  &i);
+	xt_info_wrunlock(curcpu);
 
 	for_each_possible_cpu(cpu) {
 		if (cpu == curcpu)
 			continue;
 		i = 0;
+		xt_info_wrlock(cpu);
 		IPT_ENTRY_ITERATE(t->entries[cpu],
 				  t->size,
 				  add_entry_to_counter,
 				  counters,
 				  &i);
+		xt_info_wrunlock(cpu);
 	}
-
-}
-
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct ipt_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
-/* Take values from counters and add them back onto the current cpu */
-static void put_counters(struct xt_table_info *t,
-			 const struct xt_counters counters[])
-{
-	unsigned int i, cpu;
-
-	local_bh_disable();
-	cpu = smp_processor_id();
-	i = 0;
-	IPT_ENTRY_ITERATE(t->entries[cpu],
-			  t->size,
-			  add_counter_to_entry,
-			  counters,
-			  &i);
 	local_bh_enable();
 }
 
-
-static inline int
-zero_entry_counter(struct ipt_entry *e, void *arg)
-{
-	e->counters.bcnt = 0;
-	e->counters.pcnt = 0;
-	return 0;
-}
-
-static void
-clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
-{
-	unsigned int cpu;
-	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
-
-	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
-	for_each_possible_cpu(cpu) {
-		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
-		IPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
-				  zero_entry_counter, NULL);
-	}
-}
-
 static struct xt_counters * alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
 	struct xt_table_info *private = table->private;
-	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	   (other than comefrom, which userspace doesn't care
@@ -988,30 +936,11 @@ static struct xt_counters * alloc_counte
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		goto nomem;
+		return ERR_PTR(-ENOMEM);
 
-	info = xt_alloc_table_info(private->size);
-	if (!info)
-		goto free_counters;
-
-	clone_counters(info, private);
-
-	mutex_lock(&table->lock);
-	xt_table_entry_swap_rcu(private, info);
-	synchronize_net();	/* Wait until smoke has cleared */
-
-	get_counters(info, counters);
-	put_counters(private, counters);
-	mutex_unlock(&table->lock);
-
-	xt_free_table_info(info);
+	get_counters(private, counters);
 
 	return counters;
-
- free_counters:
-	vfree(counters);
- nomem:
-	return ERR_PTR(-ENOMEM);
 }
 
 static int
@@ -1377,11 +1306,23 @@ do_replace(struct net *net, void __user 
 	return ret;
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct ipt_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
 
 static int
 do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
 {
-	unsigned int i;
+	unsigned int i, curcpu;
 	struct xt_counters_info tmp;
 	struct xt_counters *paddc;
 	unsigned int num_counters;
@@ -1437,25 +1378,26 @@ do_add_counters(struct net *net, void __
 		goto free;
 	}
 
-	mutex_lock(&t->lock);
+	local_bh_disable();
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
-	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
-	loc_cpu_entry = private->entries[raw_smp_processor_id()];
+	curcpu = smp_processor_id();
+	loc_cpu_entry = private->entries[curcpu];
+	xt_info_wrlock(curcpu);
 	IPT_ENTRY_ITERATE(loc_cpu_entry,
 			  private->size,
 			  add_counter_to_entry,
 			  paddc,
 			  &i);
-	preempt_enable();
+	xt_info_wrunlock(curcpu);
  unlock_up_free:
-	mutex_unlock(&t->lock);
+	local_bh_enable();
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
net/netfilter/x_tables.c +0 -14
@@ -625,20 +625,6 @@ void xt_free_table_info(struct xt_table_
 }
 EXPORT_SYMBOL(xt_free_table_info);
 
-void xt_table_entry_swap_rcu(struct xt_table_info *oldinfo,
-			     struct xt_table_info *newinfo)
-{
-	unsigned int cpu;
-
-	for_each_possible_cpu(cpu) {
-		void *p = oldinfo->entries[cpu];
-		rcu_assign_pointer(oldinfo->entries[cpu], newinfo->entries[cpu]);
-		newinfo->entries[cpu] = p;
-	}
-
-}
-EXPORT_SYMBOL_GPL(xt_table_entry_swap_rcu);
-
 /* Find table by name, grabs mutex & ref.  Returns ERR_PTR() on error. */
 struct xt_table *xt_find_table_lock(struct net *net, u_int8_t af,
 				    const char *name)

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 666

Quoted 5 lines
net/netfilter/x_tables.c +2 -0
@@ -676,32 +662,43 @@ void xt_compat_unlock(u_int8_t af)
 EXPORT_SYMBOL_GPL(xt_compat_unlock);
 #endif
 
+DEFINE_PER_CPU(rwlock_t, xt_info_locks);
+EXPORT_PER_CPU_SYMBOL_GPL(xt_info_locks);

Hmmm... Not sure I want to know what module uses this.

Ah, that is right -- a bunch of the comms stack can be built as a module.

Quoted 5 lines
net/netfilter/x_tables.c +2 -0
+
+
 struct xt_table_info *
 xt_replace_table(struct xt_table *table,
 	      unsigned int num_counters,

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 679

Quoted 10 lines
net/netfilter/x_tables.c +3 -2
 	      struct xt_table_info *newinfo,
 	      int *error)
 {
-	struct xt_table_info *oldinfo, *private;
+	unsigned int i;
+	struct xt_table_info *private;
 
 	/* Do the substitution. */
-	mutex_lock(&table->lock);
+	local_bh_disable();

Good, disabling preemption prevents other readers from messing with this CPU's local state.

Quoted 16 lines
net/netfilter/x_tables.c +1 -6
 	private = table->private;
 	/* Check inside lock: is the old number correct? */
 	if (num_counters != private->number) {
 		duprintf("num_counters != table->private->number (%u/%u)\n",
 			 num_counters, private->number);
-		mutex_unlock(&table->lock);
+		local_bh_enable();
 		*error = -EAGAIN;
 		return NULL;
 	}
-	oldinfo = private;
-	rcu_assign_pointer(table->private, newinfo);
-	newinfo->initial_entries = oldinfo->initial_entries;
-	mutex_unlock(&table->lock);
 
-	synchronize_net();

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 698

Quoted 10 lines
net/netfilter/x_tables.c +9 -1
-	return oldinfo;
+	table->private = newinfo;
+	newinfo->initial_entries = private->initial_entries;
+
+	/* wait for each other cpu to see new table */
+	for_each_possible_cpu(i)
+		if (i != smp_processor_id()) {
+			xt_info_wrlock(i);
+			xt_info_wrunlock(i);
+		}

And the above loop acts sort of like a lock-based synchronize_rcu().

Quoted 57 lines
net/netfilter/x_tables.c +13 -2
+	local_bh_enable();
+
+	return private;
 }
 EXPORT_SYMBOL_GPL(xt_replace_table);
 
@@ -734,7 +731,6 @@ struct xt_table *xt_register_table(struc
 
 	/* Simplifies replace_table code. */
 	table->private = bootstrap;
-	mutex_init(&table->lock);
 
 	if (!xt_replace_table(table, 0, newinfo, &ret))
 		goto unlock;
@@ -1147,7 +1143,16 @@ static struct pernet_operations xt_net_o
 
 static int __init xt_init(void)
 {
-	int i, rv;
+	unsigned int i;
+	int rv;
+	static struct lock_class_key xt_lock_key[NR_CPUS];
+
+	for_each_possible_cpu(i) {
+		rwlock_t *lock = &per_cpu(xt_info_locks, i);
+
+		rwlock_init(lock);
+		lockdep_set_class(lock, xt_lock_key+i);
+	}
 
 	xt = kmalloc(sizeof(struct xt_af) * NFPROTO_NUMPROTO, GFP_KERNEL);
 	if (!xt)
net/ipv6/netfilter/ip6_tables.c +4 -4
@@ -365,9 +365,9 @@ ip6t_do_table(struct sk_buff *skb,
 
 	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
 
-	rcu_read_lock_bh();
-	private = rcu_dereference(table->private);
-	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+	xt_info_rdlock_bh();
+	private = table->private;
+	table_base = private->entries[smp_processor_id()];
 
 	e = get_entry(table_base, private->hook_entry[hook]);
 
@@ -466,7 +466,7 @@ ip6t_do_table(struct sk_buff *skb,
 #ifdef CONFIG_NETFILTER_DEBUG
 	((struct ip6t_entry *)table_base)->comefrom = NETFILTER_LINK_POISON;
 #endif
-	rcu_read_unlock_bh();
+	xt_info_rdunlock_bh();
 
 #ifdef DEBUG_ALLOW_ALL
 	return NF_ACCEPT;

net/ipv6/netfilter/ip6_tables.c get_counters(const struct xt_table_info · line 931

Quoted 8 lines
net/ipv6/netfilter/ip6_tables.c +2 -2
@@ -926,87 +926,40 @@ get_counters(const struct xt_table_info 
 	/* Instead of clearing (by a previous call to memset())
 	 * the counters and using adds, we set the counters
 	 * with data used by 'current' CPU
-	 * We dont care about preemption here.
 	 */
-	curcpu = raw_smp_processor_id();
+	local_bh_disable();
+	curcpu = smp_processor_id();

Same story, but for IPv6.

Quoted 212 lines
net/ipv6/netfilter/ip6_tables.c +29 -79
 	i = 0;
+	xt_info_wrlock(curcpu);
 	IP6T_ENTRY_ITERATE(t->entries[curcpu],
 			   t->size,
 			   set_entry_to_counter,
 			   counters,
 			   &i);
+	xt_info_wrunlock(curcpu);
+
 
 	for_each_possible_cpu(cpu) {
 		if (cpu == curcpu)
 			continue;
 		i = 0;
+		xt_info_wrlock(cpu);
 		IP6T_ENTRY_ITERATE(t->entries[cpu],
 				  t->size,
 				  add_entry_to_counter,
 				  counters,
 				  &i);
+		xt_info_wrunlock(cpu);
 	}
-}
-
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct ip6t_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
-/* Take values from counters and add them back onto the current cpu */
-static void put_counters(struct xt_table_info *t,
-			 const struct xt_counters counters[])
-{
-	unsigned int i, cpu;
-
-	local_bh_disable();
-	cpu = smp_processor_id();
-	i = 0;
-	IP6T_ENTRY_ITERATE(t->entries[cpu],
-			   t->size,
-			   add_counter_to_entry,
-			   counters,
-			   &i);
 	local_bh_enable();
 }
 
-static inline int
-zero_entry_counter(struct ip6t_entry *e, void *arg)
-{
-	e->counters.bcnt = 0;
-	e->counters.pcnt = 0;
-	return 0;
-}
-
-static void
-clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
-{
-	unsigned int cpu;
-	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
-
-	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
-	for_each_possible_cpu(cpu) {
-		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
-		IP6T_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
-				   zero_entry_counter, NULL);
-	}
-}
-
 static struct xt_counters *alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
 	struct xt_table_info *private = table->private;
-	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	   (other than comefrom, which userspace doesn't care
@@ -1015,30 +968,11 @@ static struct xt_counters *alloc_counter
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		goto nomem;
-
-	info = xt_alloc_table_info(private->size);
-	if (!info)
-		goto free_counters;
-
-	clone_counters(info, private);
+		return ERR_PTR(-ENOMEM);
 
-	mutex_lock(&table->lock);
-	xt_table_entry_swap_rcu(private, info);
-	synchronize_net();	/* Wait until smoke has cleared */
-
-	get_counters(info, counters);
-	put_counters(private, counters);
-	mutex_unlock(&table->lock);
-
-	xt_free_table_info(info);
+	get_counters(private, counters);
 
 	return counters;
-
- free_counters:
-	vfree(counters);
- nomem:
-	return ERR_PTR(-ENOMEM);
 }
 
 static int
@@ -1405,11 +1339,24 @@ do_replace(struct net *net, void __user 
 	return ret;
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct ip6t_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
 static int
 do_add_counters(struct net *net, void __user *user, unsigned int len,
 		int compat)
 {
-	unsigned int i;
+	unsigned int i, curcpu;
 	struct xt_counters_info tmp;
 	struct xt_counters *paddc;
 	unsigned int num_counters;
@@ -1465,25 +1412,28 @@ do_add_counters(struct net *net, void __
 		goto free;
 	}
 
-	mutex_lock(&t->lock);
+
+	local_bh_disable();
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
-	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
-	loc_cpu_entry = private->entries[raw_smp_processor_id()];
+	curcpu = smp_processor_id();
+	xt_info_wrlock(curcpu);
+	loc_cpu_entry = private->entries[curcpu];
 	IP6T_ENTRY_ITERATE(loc_cpu_entry,
 			  private->size,
 			  add_counter_to_entry,
 			  paddc,
 			  &i);
-	preempt_enable();
+	xt_info_wrunlock(curcpu);
+
  unlock_up_free:
-	mutex_unlock(&t->lock);
+	local_bh_enable();
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
net/ipv4/netfilter/arp_tables.c +5 -5
@@ -253,9 +253,9 @@ unsigned int arpt_do_table(struct sk_buf
 	indev = in ? in->name : nulldevname;
 	outdev = out ? out->name : nulldevname;
 
-	rcu_read_lock_bh();
-	private = rcu_dereference(table->private);
-	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+	xt_info_rdlock_bh();
+	private = table->private;
+	table_base = private->entries[smp_processor_id()];
 
 	e = get_entry(table_base, private->hook_entry[hook]);
 	back = get_entry(table_base, private->underflow[hook]);
@@ -273,6 +273,7 @@ unsigned int arpt_do_table(struct sk_buf
 
 			hdr_len = sizeof(*arp) + (2 * sizeof(struct in_addr)) +
 				(2 * skb->dev->addr_len);
+
 			ADD_COUNTER(e->counters, hdr_len, 1);
 
 			t = arpt_get_target(e);
@@ -328,8 +329,7 @@ unsigned int arpt_do_table(struct sk_buf
 			e = (void *)e + e->next_offset;
 		}
 	} while (!hotdrop);
-
-	rcu_read_unlock_bh();
+	xt_info_rdunlock_bh();
 
 	if (hotdrop)
 		return NF_DROP;

net/ipv4/netfilter/arp_tables.c static void get_counters(const struct xt · line 715

Quoted 7 lines
net/ipv4/netfilter/arp_tables.c +1 -2
@@ -711,88 +711,39 @@ static void get_counters(const struct xt
 	/* Instead of clearing (by a previous call to memset())
 	 * the counters and using adds, we set the counters
 	 * with data used by 'current' CPU
-	 * We dont care about preemption here.
 	 */
-	curcpu = raw_smp_processor_id();
+	local_bh_disable();

Same story, but for ARP.

Quoted 178 lines
net/ipv4/netfilter/arp_tables.c +27 -81
+	curcpu = smp_processor_id();
 
 	i = 0;
+	xt_info_wrlock(curcpu);
 	ARPT_ENTRY_ITERATE(t->entries[curcpu],
 			   t->size,
 			   set_entry_to_counter,
 			   counters,
 			   &i);
+	xt_info_wrunlock(curcpu);
 
 	for_each_possible_cpu(cpu) {
 		if (cpu == curcpu)
 			continue;
 		i = 0;
+		xt_info_wrlock(cpu);
 		ARPT_ENTRY_ITERATE(t->entries[cpu],
 				   t->size,
 				   add_entry_to_counter,
 				   counters,
 				   &i);
+		xt_info_wrunlock(cpu);
 	}
-}
-
-
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct arpt_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
-/* Take values from counters and add them back onto the current cpu */
-static void put_counters(struct xt_table_info *t,
-			 const struct xt_counters counters[])
-{
-	unsigned int i, cpu;
-
-	local_bh_disable();
-	cpu = smp_processor_id();
-	i = 0;
-	ARPT_ENTRY_ITERATE(t->entries[cpu],
-			  t->size,
-			  add_counter_to_entry,
-			  counters,
-			  &i);
 	local_bh_enable();
 }
 
-static inline int
-zero_entry_counter(struct arpt_entry *e, void *arg)
-{
-	e->counters.bcnt = 0;
-	e->counters.pcnt = 0;
-	return 0;
-}
-
-static void
-clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
-{
-	unsigned int cpu;
-	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
-
-	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
-	for_each_possible_cpu(cpu) {
-		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
-		ARPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
-				  zero_entry_counter, NULL);
-	}
-}
-
 static struct xt_counters *alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
 	struct xt_table_info *private = table->private;
-	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	 * (other than comefrom, which userspace doesn't care
@@ -802,30 +753,11 @@ static struct xt_counters *alloc_counter
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		goto nomem;
-
-	info = xt_alloc_table_info(private->size);
-	if (!info)
-		goto free_counters;
-
-	clone_counters(info, private);
+		return ERR_PTR(-ENOMEM);
 
-	mutex_lock(&table->lock);
-	xt_table_entry_swap_rcu(private, info);
-	synchronize_net();	/* Wait until smoke has cleared */
-
-	get_counters(info, counters);
-	put_counters(private, counters);
-	mutex_unlock(&table->lock);
-
-	xt_free_table_info(info);
+	get_counters(private, counters);
 
 	return counters;
-
- free_counters:
-	vfree(counters);
- nomem:
-	return ERR_PTR(-ENOMEM);
 }
 
 static int copy_entries_to_user(unsigned int total_size,
@@ -1165,10 +1097,23 @@ static int do_replace(struct net *net, v
 	return ret;
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct arpt_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
 static int do_add_counters(struct net *net, void __user *user, unsigned int len,
 			   int compat)
 {
-	unsigned int i;
+	unsigned int i, curcpu;
 	struct xt_counters_info tmp;
 	struct xt_counters *paddc;
 	unsigned int num_counters;
@@ -1224,26 +1169,26 @@ static int do_add_counters(struct net *n
 		goto free;
 	}
 
-	mutex_lock(&t->lock);
+	local_bh_disable();
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
-	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
-	loc_cpu_entry = private->entries[smp_processor_id()];
+	curcpu = smp_processor_id();
+	loc_cpu_entry = private->entries[curcpu];
+	xt_info_wrlock(curcpu);
 	ARPT_ENTRY_ITERATE(loc_cpu_entry,
 			   private->size,
 			   add_counter_to_entry,
 			   paddc,
 			   &i);
-	preempt_enable();
+	xt_info_wrunlock(curcpu);
  unlock_up_free:
-	mutex_unlock(&t->lock);
-
+	local_bh_enable();
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
#152 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v13)

In reply to Stephen Hemminger
Quoted 9 lines · Stephen Hemminger

This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.

The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. This reduces the contention of a single reader lock (in 2.6.29) without the delay of synchronize_net() (in 2.6.30-rc2).

Quoted 4 lines

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

Tested today on various machines and no problem so far tbench/oprofile results, 3.7236% cpu spent in ipt_do_table, and 0.84% used on read_lock/read_unlock

c04a5c30 <ipt_do_table>: /* ipt_do_table total: 217134 3.7236 */
...

   349  0.0060 :c04a5ccc:   call   c04ce380 <_read_lock>
 23914  0.4101 :c04a5cd1:   mov    0xc(%edi),%eax
...
               :c04a5ecb:   call   c04ce5f0 <_read_unlock_bh>
 25279  0.4335 :c04a5ed0:   cmpb   $0x0,-0xd(%ebp)

"iptables -L" fetches its data very fast too.
150 us on a 8 cpus machine, small firewall rules.
400-700 us on same machine, 1000 fw rules set (160000 bytes per cpu)
depending on network trafic (from light to flood)

Thanks

Quoted 14 lines

---
CHANGES
- reader and write now inline
- only acquire one cpu write lock at a time
- write lock pushed down into get_counters

 include/linux/netfilter/x_tables.h |   50 +++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  121 ++++++++++---------------------------
 net/ipv4/netfilter/ip_tables.c     |  120 +++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  120 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 +++++++++-------
 5 files changed, 174 insertions(+), 292 deletions(-)
#153 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v13)

In reply to Stephen Hemminger
Quoted 3 lines · Stephen Hemminger

This version of x_tables (ip/ip6/arp) locking uses a per-cpu recursive lock that can be nested.

Ack on the code.

But the comment is _still_ crap. Please update. It's not a recursive lock, as clearly shown by the code itself. It's a per-cpu read-write lock, and only the reader is "recursive" (but that's how read-write locks with in Linux, and that has nothing to do with anything).

So make the explanations match the code and the intent. Write it something like

This version of x_tables (ip/ip6/arp) locking uses a per-cpu reader-writer lock lock where the readers can nest.

and don't confuse it with incorrect commit messages. The lock is very much not recursive - on purpose - for half the people taking it.

[ That, btw, was always true, even in the original random open-coded
version. Because you can't actually do a real recursive lock without having notion of "current ownership" either by making the count be <per-thread,per-lock> - like the BKL - or by saving the ownership information in the lock. A plain counter simply doesn't do it. ]

Linus

#154 lore raw

PATCH 1/1 netfilter: use per-CPU recursive lock {XIV}

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

---
What hath changed over the last two setting suns:
* more words, mostly correct...

* no need to locketh for writeh on current cpu tis always so

* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing

 include/linux/netfilter/x_tables.h |   55 ++++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  125 ++++++++++--------------------------
 net/ipv4/netfilter/ip_tables.c     |  126 ++++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 ++++++++--------
 5 files changed, 188 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +50 -5
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,56 @@ extern void xt_proto_fini(struct net *ne
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+/*
+ * Per-CPU read/write lock associated with per-cpu table entries.
+ * This is not a general solution but makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since update must lock all
+ * possible CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because read locks handle nesting.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *	  as a side effect of reading counters
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	/*
+	 * Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
+	 * because need to ensure that preemption is disable before
+	 * acquiring per-cpu-variable, so do it as a two step process
+	 */
+	local_bh_disable();
+	read_lock(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	write_lock(&per_cpu(xt_info_locks, cpu));
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+
+	write_unlock(&per_cpu(xt_info_locks, cpu));
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89

215 lines not on this page · raw message

net/ipv4/netfilter/ip_tables.c +35 -91

211 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +37 -86

208 lines not on this page · raw message

net/netfilter/x_tables.c +30 -25

96 lines not on this page · raw message

#155 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}

Quoted 14 lines · Stephen Hemminger

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

Quoted 7 lines

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

Philip Davis of the university’s School of English said :

"Shakespeare surprises the brain and catches it off guard in a manner that produces a sudden burst of activity - a sense of drama created out of the simplest of things."

http://www.physorg.com/news85664210.html

Quoted 24 lines

---
What hath changed over the last two setting suns:
* more words, mostly correct...

* no need to locketh for writeh on current cpu tis always so

* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing

 include/linux/netfilter/x_tables.h |   55 ++++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  125 ++++++++++--------------------------
 net/ipv4/netfilter/ip_tables.c     |  126 ++++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 ++++++++--------
 5 files changed, 188 insertions(+), 296 deletions(-)

static int __init xt_init(void)
{

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148

Quoted 4 lines
net/netfilter/x_tables.c +3 -1
-	int i, rv;
+	unsigned int i;
+	int rv;
+	static struct lock_class_key xt_lock_key[NR_CPUS];

Could we avoid this [NR_CPUS] thing ?

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155

Quoted 7 lines
net/netfilter/x_tables.c +7 -0
+
+	for_each_possible_cpu(i) {
+		rwlock_t *lock = &per_cpu(xt_info_locks, i);
+
+		rwlock_init(lock);
+		lockdep_set_class(lock, xt_lock_key+i);
+	}

Did you tried :

static DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);

static int __init xt_init(void)

 {
	unsigned int i;
	int rv;

	for_each_possible_cpu(i) {
		rwlock_t *lock = &per_cpu(xt_info_locks, i);

		rwlock_init(lock);
		lockdep_set_class(lock, &per_cpu(&xt_locks_key, i));
	}

...

Thanks

#156 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}

Quoted 14 lines · Eric Dumazet
Quoted 13 lines · Stephen Hemminger

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant
did replace the tables. This sucketh and caused the single
lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

Quoted 5 lines
Quoted 5 lines

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

Hehe.

Quoted 20 lines

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148

Quoted 6 lines

static int __init xt_init(void)
{

net/netfilter/x_tables.c +3 -1
-	int i, rv;
+	unsigned int i;
+	int rv;
+	static struct lock_class_key xt_lock_key[NR_CPUS];

Could we avoid this [NR_CPUS] thing ?

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155

Quoted 7 lines
net/netfilter/x_tables.c +7 -0
+
+	for_each_possible_cpu(i) {
+		rwlock_t *lock = &per_cpu(xt_info_locks, i);
+
+		rwlock_init(lock);
+		lockdep_set_class(lock, xt_lock_key+i);
+	}

Did you tried :

Quoted 1 line

static DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);

Either way is fine with me, I'll wait for Stephen to state his opinion. --
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#157 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}

In reply to Eric Dumazet
Quoted 74 lines · On Fri, 24 Apr 2009 06:58:39 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 14 lines · Stephen Hemminger

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

Quoted 7 lines

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

Philip Davis of the university’s School of English said :

"Shakespeare surprises the brain and catches it off guard in a manner that produces a sudden burst of activity - a sense of drama created out of the simplest of things."

http://www.physorg.com/news85664210.html

Quoted 24 lines

---
What hath changed over the last two setting suns:
* more words, mostly correct...

* no need to locketh for writeh on current cpu tis always so

* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing

 include/linux/netfilter/x_tables.h |   55 ++++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  125 ++++++++++--------------------------
 net/ipv4/netfilter/ip_tables.c     |  126 ++++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 ++++++++--------
 5 files changed, 188 insertions(+), 296 deletions(-)

static int __init xt_init(void)
{

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148

Quoted 4 lines
net/netfilter/x_tables.c +3 -1
-	int i, rv;
+	unsigned int i;
+	int rv;
+	static struct lock_class_key xt_lock_key[NR_CPUS];

Could we avoid this [NR_CPUS] thing ?

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155

Quoted 7 lines
net/netfilter/x_tables.c +7 -0
+
+	for_each_possible_cpu(i) {
+		rwlock_t *lock = &per_cpu(xt_info_locks, i);
+
+		rwlock_init(lock);
+		lockdep_set_class(lock, xt_lock_key+i);
+	}

Did you tried :

Quoted 2 lines

static DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);

The lock keys are really only used by lock dep, and I thought per cpu space was more scarce on some arch.

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

#158 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XIV}

Stephen Hemminger wrote, On 04/24/2009 06:18 PM:

Quoted 72 lines
Quoted 69 lines · On Fri, 24 Apr 2009 06:58:39 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 14 lines · Stephen Hemminger

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

Quoted 7 lines

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

Philip Davis of the university’s School of English said :

"Shakespeare surprises the brain and catches it off guard in a manner that produces a sudden burst of activity - a sense of drama created out of the simplest of things."

http://www.physorg.com/news85664210.html

Quoted 22 lines

---
What hath changed over the last two setting suns:
* more words, mostly correct...

* no need to locketh for writeh on current cpu tis always so

* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing

 include/linux/netfilter/x_tables.h |   55 ++++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  125 ++++++++++--------------------------
 net/ipv4/netfilter/ip_tables.c     |  126 ++++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   55 ++++++++--------
 5 files changed, 188 insertions(+), 296 deletions(-)

static int __init xt_init(void)
{

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1148

Quoted 4 lines
net/netfilter/x_tables.c +3 -1
-	int i, rv;
+	unsigned int i;
+	int rv;
+	static struct lock_class_key xt_lock_key[NR_CPUS];

Could we avoid this [NR_CPUS] thing ?

net/netfilter/x_tables.c static struct pernet_operations xt_net_o · line 1155

Quoted 7 lines
net/netfilter/x_tables.c +7 -0
+
+	for_each_possible_cpu(i) {
+		rwlock_t *lock = &per_cpu(xt_info_locks, i);
+
+		rwlock_init(lock);
+		lockdep_set_class(lock, xt_lock_key+i);
+	}

Did you tried :

Quoted 6 lines
Quoted 2 lines

static DECLARE_PER_CPU(struct lock_class_key, xt_locks_key);

The lock keys are really only used by lock dep, and I thought per cpu space was more scarce on some arch.

Maybe I'm wrong but after this change: "- only acquire one cpu write lock at a time" lockdep_set_class() might be unnecessary. Alas I'm not able to test it.

Jarek P.

#159 lore raw

PATCH 1/1 netfilter: iptables no lockdep is needed..

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

---
 net/netfilter/x_tables.c |    9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)
net/netfilter/x_tables.c +2 -7
@@ -1145,14 +1145,9 @@ static int __init xt_init(void)
 {
 	unsigned int i;
 	int rv;
-	static struct lock_class_key xt_lock_key[NR_CPUS];
 
-	for_each_possible_cpu(i) {
-		rwlock_t *lock = &per_cpu(xt_info_locks, i);
-
-		rwlock_init(lock);
-		lockdep_set_class(lock, xt_lock_key+i);
-	}
+	for_each_possible_cpu(i)
+		rwlock_init(&per_cpu(xt_info_locks, i));
 
 	xt = kmalloc(sizeof(struct xt_af) * NFPROTO_NUMPROTO, GFP_KERNEL);
 	if (!xt)
#160 lore raw

Re: [PATCH] netfilter: iptables no lockdep is needed..

Quoted 4 lines · Stephen Hemminger

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

Very nice! I guess this Shakespeare guy Will sign off this all too. ;-)

Thanks,
Jarek P.

Quoted 24 lines
---
 net/netfilter/x_tables.c |    9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)
net/netfilter/x_tables.c +2 -7
@@ -1145,14 +1145,9 @@ static int __init xt_init(void)
 {
 	unsigned int i;
 	int rv;
-	static struct lock_class_key xt_lock_key[NR_CPUS];
 
-	for_each_possible_cpu(i) {
-		rwlock_t *lock = &per_cpu(xt_info_locks, i);
-
-		rwlock_init(lock);
-		lockdep_set_class(lock, xt_lock_key+i);
-	}
+	for_each_possible_cpu(i)
+		rwlock_init(&per_cpu(xt_info_locks, i));
 
 	xt = kmalloc(sizeof(struct xt_af) * NFPROTO_NUMPROTO, GFP_KERNEL);
 	if (!xt)
#161 lore raw

PATCH 1/1 netfilter: use per-CPU recursive lock {XV}

In reply to Stephen Hemminger

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

Thanks to all for your help and patience

[PATCH] netfilter: use per-CPU recursive lock {XV}

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

---
What hath changed over the last two setting suns:

* more words, mostly correct...

* no need to locketh for writeh on current cpu tis always so

* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing

* Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

 include/linux/netfilter/x_tables.h |   55 ++++++++++-
 net/ipv4/netfilter/arp_tables.c    |  125 +++++++-------------------
 net/ipv4/netfilter/ip_tables.c     |  126 +++++++--------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 +++++++-------------------
 net/netfilter/x_tables.c           |   50 +++++-----
 5 files changed, 183 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +50 -5
index 7b1a652..511debb 100644
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,56 @@ extern void xt_proto_fini(struct net *net, u_int8_t af);
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+/*
+ * Per-CPU read/write lock associated with per-cpu table entries.
+ * This is not a general solution but makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since update must lock all
+ * possible CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because read locks handle nesting.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *	  as a side effect of reading counters
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	/*
+	 * Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
+	 * because need to ensure that preemption is disable before
+	 * acquiring per-cpu-variable, so do it as a two step process
+	 */
+	local_bh_disable();
+	read_lock(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	write_lock(&per_cpu(xt_info_locks, cpu));
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+
+	write_unlock(&per_cpu(xt_info_locks, cpu));
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89

215 lines not on this page · raw message

net/ipv4/netfilter/ip_tables.c +35 -91

211 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +37 -86

208 lines not on this page · raw message

net/netfilter/x_tables.c +25 -25

91 lines not on this page · raw message

#162 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

Quoted 9 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

Quoted 7 lines

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

Thanks to all for your help and patience

[PATCH] netfilter: use per-CPU recursive lock {XV}

Hi Eric,

Please... could you rename this patch according to Linus'comments ?

Suitable name would probably be :

[PATCH] netfilter: use bh disabling with per-cpu read-write lock

Quoted 76 lines

In days of old in 2.6.29, netfilter did locketh using a lock of the reader kind when doing its table business, and do a writer when with pen in hand like a overworked accountant did replace the tables. This sucketh and caused the single lock to fly back and forth like a poor errant boy.

But then netfilter was blessed with RCU and the performance was divine, but alas there were those that suffered for trying to replace their many rules one at a time.

So now RCU must be vanquished from the scene, and better chastity belts be placed upon this valuable asset most dear. The locks that were but one are now replaced by one per suitor.

The repair was made after much discussion involving Eric the wise, and Linus the foul. With flowers springing up amid the thorns some peace has finally prevailed and all is soothed. This patch and purple prose was penned by in honor of "Talk like Shakespeare" day.

---
What hath changed over the last two setting suns:

* more words, mostly correct...

* no need to locketh for writeh on current cpu tis always so

* the locking of all cpu's on replace is always done as part of the get_counters cycle, so the sychronize swip in replace tables is gone with only a comment remaing

* Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

 include/linux/netfilter/x_tables.h |   55 ++++++++++-
 net/ipv4/netfilter/arp_tables.c    |  125 +++++++-------------------
 net/ipv4/netfilter/ip_tables.c     |  126 +++++++--------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 +++++++-------------------
 net/netfilter/x_tables.c           |   50 +++++-----
 5 files changed, 183 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +11 -5
index 7b1a652..511debb 100644
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,56 @@ extern void xt_proto_fini(struct net *net, u_int8_t af);
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+/*
+ * Per-CPU read/write lock associated with per-cpu table entries.
+ * This is not a general solution but makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since update must lock all
+ * possible CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed. In some cases, the read lock will be acquired

include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 454

Quoted 10 lines
include/linux/netfilter/x_tables.h +10 -0
+ * twice on the same CPU; this is okay because read locks handle nesting.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *	  as a side effect of reading counters

Stating that the write lock must _always_ be taken with bh disabled might not hurt here.

Quoted 50 lines
include/linux/netfilter/x_tables.h +29 -0
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	/*
+	 * Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
+	 * because need to ensure that preemption is disable before
+	 * acquiring per-cpu-variable, so do it as a two step process
+	 */
+	local_bh_disable();
+	read_lock(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	write_lock(&per_cpu(xt_info_locks, cpu));
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+
+	write_unlock(&per_cpu(xt_info_locks, cpu));
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +3 -3
index 5ba533d..831fe18 100644
@@ -253,9 +253,9 @@ unsigned int arpt_do_table(struct sk_buff *skb,
 	indev = in ? in->name : nulldevname;
 	outdev = out ? out->name : nulldevname;
 
-	rcu_read_lock_bh();
-	private = rcu_dereference(table->private);
-	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+	xt_info_rdlock_bh();
+	private = table->private;
+	table_base = private->entries[smp_processor_id()];
 
 	e = get_entry(table_base, private->hook_entry[hook]);
 	back = get_entry(table_base, private->underflow[hook]);

net/ipv4/netfilter/arp_tables.c unsigned int arpt_do_table(struct sk_buff *skb, · line 276

Quoted 4 lines
net/ipv4/netfilter/arp_tables.c +1 -0
@@ -273,6 +273,7 @@ unsigned int arpt_do_table(struct sk_buff *skb,
 
 			hdr_len = sizeof(*arp) + (2 * sizeof(struct in_addr)) +
 				(2 * skb->dev->addr_len);
+

This is not a whitespace cleanup patch.

net/ipv4/netfilter/arp_tables.c unsigned int arpt_do_table(struct sk_buff *skb, · line 331

Quoted 8 lines
net/ipv4/netfilter/arp_tables.c +0 -1
 			ADD_COUNTER(e->counters, hdr_len, 1);
 
 			t = arpt_get_target(e);
@@ -328,8 +329,7 @@ unsigned int arpt_do_table(struct sk_buff *skb,
 			e = (void *)e + e->next_offset;
 		}
 	} while (!hotdrop);
-

Whitespace cleanup ?

Quoted 54 lines
net/ipv4/netfilter/arp_tables.c +8 -25
-	rcu_read_unlock_bh();
+	xt_info_rdunlock_bh();
 
 	if (hotdrop)
 		return NF_DROP;
@@ -711,9 +711,12 @@ static void get_counters(const struct xt_table_info *t,
 	/* Instead of clearing (by a previous call to memset())
 	 * the counters and using adds, we set the counters
 	 * with data used by 'current' CPU
-	 * We dont care about preemption here.
+	 *
+	 * Bottom half has to be disabled to prevent deadlock
+	 * if new softirq were to run and call ipt_do_table
 	 */
-	curcpu = raw_smp_processor_id();
+	local_bh_disable();
+	curcpu = smp_processor_id();
 
 	i = 0;
 	ARPT_ENTRY_ITERATE(t->entries[curcpu],
@@ -726,73 +729,22 @@ static void get_counters(const struct xt_table_info *t,
 		if (cpu == curcpu)
 			continue;
 		i = 0;
+		xt_info_wrlock(cpu);
 		ARPT_ENTRY_ITERATE(t->entries[cpu],
 				   t->size,
 				   add_entry_to_counter,
 				   counters,
 				   &i);
+		xt_info_wrunlock(cpu);
 	}
-}
-
-
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct arpt_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
-/* Take values from counters and add them back onto the current cpu */
-static void put_counters(struct xt_table_info *t,
-			 const struct xt_counters counters[])
-{
-	unsigned int i, cpu;
-

net/ipv4/netfilter/arp_tables.c static void get_counters(const struct xt_table_info *t, · line 741

Quoted 10 lines
net/ipv4/netfilter/arp_tables.c +0 -8
-	local_bh_disable();
-	cpu = smp_processor_id();
-	i = 0;
-	ARPT_ENTRY_ITERATE(t->entries[cpu],
-			  t->size,
-			  add_counter_to_entry,
-			  counters,
-			  &i);
 	local_bh_enable();
 }

Did you really need to move add_counter_to_entry and put_counters in this patch ? This also seems more like a cleanup to me, if it is even one. It does make the patch harder to follow though.

Quoted 544 lines
net/ipv4/netfilter/arp_tables.c +24 -52
-static inline int
-zero_entry_counter(struct arpt_entry *e, void *arg)
-{
-	e->counters.bcnt = 0;
-	e->counters.pcnt = 0;
-	return 0;
-}
-
-static void
-clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
-{
-	unsigned int cpu;
-	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
-
-	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
-	for_each_possible_cpu(cpu) {
-		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
-		ARPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
-				  zero_entry_counter, NULL);
-	}
-}
-
 static struct xt_counters *alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
 	struct xt_table_info *private = table->private;
-	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	 * (other than comefrom, which userspace doesn't care
@@ -802,30 +754,11 @@ static struct xt_counters *alloc_counters(struct xt_table *table)
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		goto nomem;
-
-	info = xt_alloc_table_info(private->size);
-	if (!info)
-		goto free_counters;
-
-	clone_counters(info, private);
-
-	mutex_lock(&table->lock);
-	xt_table_entry_swap_rcu(private, info);
-	synchronize_net();	/* Wait until smoke has cleared */
+		return ERR_PTR(-ENOMEM);
 
-	get_counters(info, counters);
-	put_counters(private, counters);
-	mutex_unlock(&table->lock);
-
-	xt_free_table_info(info);
+	get_counters(private, counters);
 
 	return counters;
-
- free_counters:
-	vfree(counters);
- nomem:
-	return ERR_PTR(-ENOMEM);
 }
 
 static int copy_entries_to_user(unsigned int total_size,
@@ -1094,8 +1027,9 @@ static int __do_replace(struct net *net, const char *name,
 	    (newinfo->number <= oldinfo->initial_entries))
 		module_put(t->me);
 
-	/* Get the old counters. */
+	/* Get the old counters, and synchronize with replace */
 	get_counters(oldinfo, counters);
+
 	/* Decrease module usage counts and free resource */
 	loc_cpu_old_entry = oldinfo->entries[raw_smp_processor_id()];
 	ARPT_ENTRY_ITERATE(loc_cpu_old_entry, oldinfo->size, cleanup_entry,
@@ -1165,10 +1099,23 @@ static int do_replace(struct net *net, void __user *user, unsigned int len)
 	return ret;
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct arpt_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
 static int do_add_counters(struct net *net, void __user *user, unsigned int len,
 			   int compat)
 {
-	unsigned int i;
+	unsigned int i, curcpu;
 	struct xt_counters_info tmp;
 	struct xt_counters *paddc;
 	unsigned int num_counters;
@@ -1224,26 +1171,26 @@ static int do_add_counters(struct net *net, void __user *user, unsigned int len,
 		goto free;
 	}
 
-	mutex_lock(&t->lock);
+	local_bh_disable();
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
-	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
-	loc_cpu_entry = private->entries[smp_processor_id()];
+	curcpu = smp_processor_id();
+	loc_cpu_entry = private->entries[curcpu];
+	xt_info_wrlock(curcpu);
 	ARPT_ENTRY_ITERATE(loc_cpu_entry,
 			   private->size,
 			   add_counter_to_entry,
 			   paddc,
 			   &i);
-	preempt_enable();
+	xt_info_wrunlock(curcpu);
  unlock_up_free:
-	mutex_unlock(&t->lock);
-
+	local_bh_enable();
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
net/ipv4/netfilter/ip_tables.c +35 -91
index 810c0b6..2ec8d72 100644
@@ -338,10 +338,9 @@ ipt_do_table(struct sk_buff *skb,
 	tgpar.hooknum = hook;
 
 	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
-
-	rcu_read_lock_bh();
-	private = rcu_dereference(table->private);
-	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+	xt_info_rdlock_bh();
+	private = table->private;
+	table_base = private->entries[smp_processor_id()];
 
 	e = get_entry(table_base, private->hook_entry[hook]);
 
@@ -436,8 +435,7 @@ ipt_do_table(struct sk_buff *skb,
 			e = (void *)e + e->next_offset;
 		}
 	} while (!hotdrop);
-
-	rcu_read_unlock_bh();
+	xt_info_rdunlock_bh();
 
 #ifdef DEBUG_ALLOW_ALL
 	return NF_ACCEPT;
@@ -896,10 +894,13 @@ get_counters(const struct xt_table_info *t,
 
 	/* Instead of clearing (by a previous call to memset())
 	 * the counters and using adds, we set the counters
-	 * with data used by 'current' CPU
-	 * We dont care about preemption here.
+	 * with data used by 'current' CPU.
+	 *
+	 * Bottom half has to be disabled to prevent deadlock
+	 * if new softirq were to run and call ipt_do_table
 	 */
-	curcpu = raw_smp_processor_id();
+	local_bh_disable();
+	curcpu = smp_processor_id();
 
 	i = 0;
 	IPT_ENTRY_ITERATE(t->entries[curcpu],
@@ -912,74 +913,22 @@ get_counters(const struct xt_table_info *t,
 		if (cpu == curcpu)
 			continue;
 		i = 0;
+		xt_info_wrlock(cpu);
 		IPT_ENTRY_ITERATE(t->entries[cpu],
 				  t->size,
 				  add_entry_to_counter,
 				  counters,
 				  &i);
+		xt_info_wrunlock(cpu);
 	}
-
-}
-
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct ipt_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
-/* Take values from counters and add them back onto the current cpu */
-static void put_counters(struct xt_table_info *t,
-			 const struct xt_counters counters[])
-{
-	unsigned int i, cpu;
-
-	local_bh_disable();
-	cpu = smp_processor_id();
-	i = 0;
-	IPT_ENTRY_ITERATE(t->entries[cpu],
-			  t->size,
-			  add_counter_to_entry,
-			  counters,
-			  &i);
 	local_bh_enable();
 }
 
-
-static inline int
-zero_entry_counter(struct ipt_entry *e, void *arg)
-{
-	e->counters.bcnt = 0;
-	e->counters.pcnt = 0;
-	return 0;
-}
-
-static void
-clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
-{
-	unsigned int cpu;
-	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
-
-	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
-	for_each_possible_cpu(cpu) {
-		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
-		IPT_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
-				  zero_entry_counter, NULL);
-	}
-}
-
 static struct xt_counters * alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
 	struct xt_table_info *private = table->private;
-	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	   (other than comefrom, which userspace doesn't care
@@ -988,30 +937,11 @@ static struct xt_counters * alloc_counters(struct xt_table *table)
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		goto nomem;
+		return ERR_PTR(-ENOMEM);
 
-	info = xt_alloc_table_info(private->size);
-	if (!info)
-		goto free_counters;
-
-	clone_counters(info, private);
-
-	mutex_lock(&table->lock);
-	xt_table_entry_swap_rcu(private, info);
-	synchronize_net();	/* Wait until smoke has cleared */
-
-	get_counters(info, counters);
-	put_counters(private, counters);
-	mutex_unlock(&table->lock);
-
-	xt_free_table_info(info);
+	get_counters(private, counters);
 
 	return counters;
-
- free_counters:
-	vfree(counters);
- nomem:
-	return ERR_PTR(-ENOMEM);
 }
 
 static int
@@ -1306,8 +1236,9 @@ __do_replace(struct net *net, const char *name, unsigned int valid_hooks,
 	    (newinfo->number <= oldinfo->initial_entries))
 		module_put(t->me);
 
-	/* Get the old counters. */
+	/* Get the old counters, and synchronize with replace */
 	get_counters(oldinfo, counters);
+
 	/* Decrease module usage counts and free resource */
 	loc_cpu_old_entry = oldinfo->entries[raw_smp_processor_id()];
 	IPT_ENTRY_ITERATE(loc_cpu_old_entry, oldinfo->size, cleanup_entry,
@@ -1377,11 +1308,23 @@ do_replace(struct net *net, void __user *user, unsigned int len)
 	return ret;
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct ipt_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
 
 static int
 do_add_counters(struct net *net, void __user *user, unsigned int len, int compat)
 {
-	unsigned int i;
+	unsigned int i, curcpu;
 	struct xt_counters_info tmp;
 	struct xt_counters *paddc;
 	unsigned int num_counters;
@@ -1437,25 +1380,26 @@ do_add_counters(struct net *net, void __user *user, unsigned int len, int compat
 		goto free;
 	}
 
-	mutex_lock(&t->lock);
+	local_bh_disable();
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
-	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
-	loc_cpu_entry = private->entries[raw_smp_processor_id()];
+	curcpu = smp_processor_id();
+	loc_cpu_entry = private->entries[curcpu];
+	xt_info_wrlock(curcpu);
 	IPT_ENTRY_ITERATE(loc_cpu_entry,
 			  private->size,
 			  add_counter_to_entry,
 			  paddc,
 			  &i);
-	preempt_enable();
+	xt_info_wrunlock(curcpu);
  unlock_up_free:
-	mutex_unlock(&t->lock);
+	local_bh_enable();
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
net/ipv6/netfilter/ip6_tables.c +29 -81
index 800ae85..219e165 100644
@@ -365,9 +365,9 @@ ip6t_do_table(struct sk_buff *skb,
 
 	IP_NF_ASSERT(table->valid_hooks & (1 << hook));
 
-	rcu_read_lock_bh();
-	private = rcu_dereference(table->private);
-	table_base = rcu_dereference(private->entries[smp_processor_id()]);
+	xt_info_rdlock_bh();
+	private = table->private;
+	table_base = private->entries[smp_processor_id()];
 
 	e = get_entry(table_base, private->hook_entry[hook]);
 
@@ -466,7 +466,7 @@ ip6t_do_table(struct sk_buff *skb,
 #ifdef CONFIG_NETFILTER_DEBUG
 	((struct ip6t_entry *)table_base)->comefrom = NETFILTER_LINK_POISON;
 #endif
-	rcu_read_unlock_bh();
+	xt_info_rdunlock_bh();
 
 #ifdef DEBUG_ALLOW_ALL
 	return NF_ACCEPT;
@@ -926,9 +926,12 @@ get_counters(const struct xt_table_info *t,
 	/* Instead of clearing (by a previous call to memset())
 	 * the counters and using adds, we set the counters
 	 * with data used by 'current' CPU
-	 * We dont care about preemption here.
+	 *
+	 * Bottom half has to be disabled to prevent deadlock
+	 * if new softirq were to run and call ipt_do_table
 	 */
-	curcpu = raw_smp_processor_id();
+	local_bh_disable();
+	curcpu = smp_processor_id();
 
 	i = 0;
 	IP6T_ENTRY_ITERATE(t->entries[curcpu],
@@ -941,72 +944,22 @@ get_counters(const struct xt_table_info *t,
 		if (cpu == curcpu)
 			continue;
 		i = 0;
+		xt_info_wrlock(cpu);
 		IP6T_ENTRY_ITERATE(t->entries[cpu],
 				  t->size,
 				  add_entry_to_counter,
 				  counters,
 				  &i);
+		xt_info_wrunlock(cpu);
 	}
-}
-
-/* We're lazy, and add to the first CPU; overflow works its fey magic
- * and everything is OK. */
-static int
-add_counter_to_entry(struct ip6t_entry *e,
-		     const struct xt_counters addme[],
-		     unsigned int *i)
-{
-	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
-
-	(*i)++;
-	return 0;
-}
-
-/* Take values from counters and add them back onto the current cpu */
-static void put_counters(struct xt_table_info *t,
-			 const struct xt_counters counters[])
-{
-	unsigned int i, cpu;
-
-	local_bh_disable();
-	cpu = smp_processor_id();
-	i = 0;
-	IP6T_ENTRY_ITERATE(t->entries[cpu],
-			   t->size,
-			   add_counter_to_entry,
-			   counters,
-			   &i);
 	local_bh_enable();
 }
 
-static inline int
-zero_entry_counter(struct ip6t_entry *e, void *arg)
-{
-	e->counters.bcnt = 0;
-	e->counters.pcnt = 0;
-	return 0;
-}
-
-static void
-clone_counters(struct xt_table_info *newinfo, const struct xt_table_info *info)
-{
-	unsigned int cpu;
-	const void *loc_cpu_entry = info->entries[raw_smp_processor_id()];
-
-	memcpy(newinfo, info, offsetof(struct xt_table_info, entries));
-	for_each_possible_cpu(cpu) {
-		memcpy(newinfo->entries[cpu], loc_cpu_entry, info->size);
-		IP6T_ENTRY_ITERATE(newinfo->entries[cpu], newinfo->size,
-				   zero_entry_counter, NULL);
-	}
-}
-
 static struct xt_counters *alloc_counters(struct xt_table *table)
 {
 	unsigned int countersize;
 	struct xt_counters *counters;
 	struct xt_table_info *private = table->private;
-	struct xt_table_info *info;
 
 	/* We need atomic snapshot of counters: rest doesn't change
 	   (other than comefrom, which userspace doesn't care
@@ -1015,30 +968,11 @@ static struct xt_counters *alloc_counters(struct xt_table *table)
 	counters = vmalloc_node(countersize, numa_node_id());
 
 	if (counters == NULL)
-		goto nomem;
+		return ERR_PTR(-ENOMEM);
 
-	info = xt_alloc_table_info(private->size);
-	if (!info)
-		goto free_counters;
-
-	clone_counters(info, private);
-
-	mutex_lock(&table->lock);
-	xt_table_entry_swap_rcu(private, info);
-	synchronize_net();	/* Wait until smoke has cleared */
-
-	get_counters(info, counters);
-	put_counters(private, counters);
-	mutex_unlock(&table->lock);
-
-	xt_free_table_info(info);
+	get_counters(private, counters);
 
 	return counters;
-
- free_counters:
-	vfree(counters);
- nomem:
-	return ERR_PTR(-ENOMEM);
 }
 
 static int
@@ -1334,8 +1268,9 @@ __do_replace(struct net *net, const char *name, unsigned int valid_hooks,
 	    (newinfo->number <= oldinfo->initial_entries))
 		module_put(t->me);
 
-	/* Get the old counters. */
+	/* Get the old counters, and synchronize with replace */
 	get_counters(oldinfo, counters);
+
 	/* Decrease module usage counts and free resource */
 	loc_cpu_old_entry = oldinfo->entries[raw_smp_processor_id()];
 	IP6T_ENTRY_ITERATE(loc_cpu_old_entry, oldinfo->size, cleanup_entry,
@@ -1405,11 +1340,24 @@ do_replace(struct net *net, void __user *user, unsigned int len)
 	return ret;
 }
 
+/* We're lazy, and add to the first CPU; overflow works its fey magic
+ * and everything is OK. */
+static int
+add_counter_to_entry(struct ip6t_entry *e,
+		     const struct xt_counters addme[],
+		     unsigned int *i)
+{
+	ADD_COUNTER(e->counters, addme[*i].bcnt, addme[*i].pcnt);
+
+	(*i)++;
+	return 0;
+}
+
 static int
 do_add_counters(struct net *net, void __user *user, unsigned int len,
 		int compat)
 {
-	unsigned int i;
+	unsigned int i, curcpu;
 	struct xt_counters_info tmp;
 	struct xt_counters *paddc;
 	unsigned int num_counters;

net/ipv6/netfilter/ip6_tables.c do_add_counters(struct net *net, void __user *user, unsigned int len, · line 1416

Quoted 5 lines
net/ipv6/netfilter/ip6_tables.c +1 -1
@@ -1465,25 +1413,28 @@ do_add_counters(struct net *net, void __user *user, unsigned int len,
 		goto free;
 	}
 
-	mutex_lock(&t->lock);
+

Incorrect whiteline added.

Quoted 12 lines
net/ipv6/netfilter/ip6_tables.c +2 -2
+	local_bh_disable();
 	private = t->private;
 	if (private->number != num_counters) {
 		ret = -EINVAL;
 		goto unlock_up_free;
 	}
 
-	preempt_disable();
 	i = 0;
 	/* Choose the copy that is on our node */
-	loc_cpu_entry = private->entries[raw_smp_processor_id()];
+	curcpu = smp_processor_id();

net/ipv6/netfilter/ip6_tables.c do_add_counters(struct net *net, void __user *user, unsigned int len, · line 1435

Quoted 10 lines
net/ipv6/netfilter/ip6_tables.c +4 -1
+	xt_info_wrlock(curcpu);
+	loc_cpu_entry = private->entries[curcpu];
 	IP6T_ENTRY_ITERATE(loc_cpu_entry,
 			  private->size,
 			  add_counter_to_entry,
 			  paddc,
 			  &i);
-	preempt_enable();
+	xt_info_wrunlock(curcpu);
+

Inconsistent whiteline.

Quoted 57 lines
net/ipv6/netfilter/ip6_tables.c +1 -1
  unlock_up_free:
-	mutex_unlock(&t->lock);
+	local_bh_enable();
 	xt_table_unlock(t);
 	module_put(t->me);
  free:
net/netfilter/x_tables.c +7 -16
index 509a956..5807a4d 100644
@@ -625,20 +625,6 @@ void xt_free_table_info(struct xt_table_info *info)
 }
 EXPORT_SYMBOL(xt_free_table_info);
 
-void xt_table_entry_swap_rcu(struct xt_table_info *oldinfo,
-			     struct xt_table_info *newinfo)
-{
-	unsigned int cpu;
-
-	for_each_possible_cpu(cpu) {
-		void *p = oldinfo->entries[cpu];
-		rcu_assign_pointer(oldinfo->entries[cpu], newinfo->entries[cpu]);
-		newinfo->entries[cpu] = p;
-	}
-
-}
-EXPORT_SYMBOL_GPL(xt_table_entry_swap_rcu);
-
 /* Find table by name, grabs mutex & ref.  Returns ERR_PTR() on error. */
 struct xt_table *xt_find_table_lock(struct net *net, u_int8_t af,
 				    const char *name)
@@ -676,32 +662,43 @@ void xt_compat_unlock(u_int8_t af)
 EXPORT_SYMBOL_GPL(xt_compat_unlock);
 #endif
 
+DEFINE_PER_CPU(rwlock_t, xt_info_locks);
+EXPORT_PER_CPU_SYMBOL_GPL(xt_info_locks);
+
+
 struct xt_table_info *
 xt_replace_table(struct xt_table *table,
 	      unsigned int num_counters,
 	      struct xt_table_info *newinfo,
 	      int *error)
 {
-	struct xt_table_info *oldinfo, *private;
+	struct xt_table_info *private;
 
 	/* Do the substitution. */
-	mutex_lock(&table->lock);
+	local_bh_disable();
 	private = table->private;
+
 	/* Check inside lock: is the old number correct? */
 	if (num_counters != private->number) {
 		duprintf("num_counters != table->private->number (%u/%u)\n",
 			 num_counters, private->number);

net/netfilter/x_tables.c void xt_compat_unlock(u_int8_t af) · line 689

Quoted 10 lines
net/netfilter/x_tables.c +1 -5
-		mutex_unlock(&table->lock);
+		local_bh_enable();
 		*error = -EAGAIN;
 		return NULL;
 	}
-	oldinfo = private;
-	rcu_assign_pointer(table->private, newinfo);
-	newinfo->initial_entries = oldinfo->initial_entries;
-	mutex_unlock(&table->lock);
 

Whiteline.....

Mathieu

Quoted 38 lines
net/netfilter/x_tables.c +17 -4
-	synchronize_net();
-	return oldinfo;
+	table->private = newinfo;
+	newinfo->initial_entries = private->initial_entries;
+
+	/*
+	 * Even though table entries have now been swapped, other CPU's
+	 * may still be using the old entries. This is okay, because
+	 * resynchronization happens because of the locking done
+	 * during the get_counters() routine.
+	 */
+	local_bh_enable();
+
+	return private;
 }
 EXPORT_SYMBOL_GPL(xt_replace_table);
 
@@ -734,7 +731,6 @@ struct xt_table *xt_register_table(struct net *net, struct xt_table *table,
 
 	/* Simplifies replace_table code. */
 	table->private = bootstrap;
-	mutex_init(&table->lock);
 
 	if (!xt_replace_table(table, 0, newinfo, &ret))
 		goto unlock;
@@ -1147,7 +1143,11 @@ static struct pernet_operations xt_net_ops = {
 
 static int __init xt_init(void)
 {
-	int i, rv;
+	unsigned int i;
+	int rv;
+
+	for_each_possible_cpu(i)
+		rwlock_init(&per_cpu(xt_info_locks, i));
 
 	xt = kmalloc(sizeof(struct xt_af) * NFPROTO_NUMPROTO, GFP_KERNEL);
 	if (!xt)
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#163 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

Quoted 8 lines
Quoted 3 lines

Thanks to all for your help and patience

[PATCH] netfilter: use per-CPU recursive lock {XV}

Hi Eric,

Suitable name would probably be :

But Linus is trying to delude himself.

This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.

#164 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

Quoted 17 lines · * Stephen Hemminger ([email protected]) wrote:
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines

Thanks to all for your help and patience

[PATCH] netfilter: use per-CPU recursive lock {XV}

Hi Eric,

Suitable name would probably be :

Hi Stephen,

[I see that you have cutted my name proposal from the original email, which might make it difficult for others to follow. I will assume you did it by mistake.]

(re-added)
[PATCH] netfilter: use bh disabling with per-cpu read-write lock

Quoted 10 lines

But Linus is trying to delude himself.

This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.

Reading Documentation/spinlocks.txt, which states the lock usage guidelines :

"Note that you can be clever with read-write locks and interrupts. For example, if you know that the interrupt only ever gets a read-lock, then you can use a non-irq version of read locks everywhere - because they don't block on each other (and thus there is no dead-lock wrt interrupts. But when you do the write-lock, you have to use the irq-safe version."

So it's assumed in the kernel-wide read lock usage that nested read locks are OK. I'm adding Thomas and Steven in CC, but I'm quite sure they must have dealt with nested read-lock transformation into mutexes by detecting nesting in some way in -rt. But I'll let them confirm this.

So I don't see why you are dreaming about a different semantic than the one of the primitives you are using. I guess I'll leave the semantics to you. I just find it astonishing that you persist saying that everbody is wrong on a topic like semantic, which is in the end a mean to communicate ideas clearly within the overall community you disagree with.

Good luck !

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#165 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

In reply to Stephen Hemminger
Quoted 28 lines · Stephen Hemminger
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

Quoted 8 lines
Quoted 3 lines

Thanks to all for your help and patience

[PATCH] netfilter: use per-CPU recursive lock {XV}

Hi Eric,

Suitable name would probably be :

But Linus is trying to delude himself.

Quoted 7 lines

This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.

A recursive lock has the property:

lock()
{

  if (lock->owner == current) {
    lock->depth++;
    return;

}

/* regular lock stuff */
}

unlock()
{
if (!--lock->depth)

    /* regular unlock */
}

non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.

What rwlock_t has, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.

This is not what is called a recursive lock. A recursive lock would have each owner only once, this rwlock_t thing is simply so unfair that it can have unlimited owners, including multiple copies of the same one.

rwsem has fifo fairness, and therefore can deadlock in this scenario, suppose thread A does a read, thread B tries a write and blocks, then thread A recurses and tries to obtain another read ownership -- deadlock, as the FIFO fairness will demand the second read ownership will wait on the pending writer, which will wait on the outstanding read owner.

Now if rwsem were a fifo-fair recursive lock, the above would not deadlock, since it would detect that the task already had (read) ownership and simply increment the depth, instead of trying to acquire a second ownership.

This is all common and well understood terminology, not something Linus invented just to harras you with.

Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing rwlock_t unfairness) are the only offenders.

Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.

Linus is very much right on what he said, and you calling him delusional only high-lights your ignorance on the issue.

[ PS. -rt implements rwlock_t as a proper recursive lock (either a mutex
or a full multi-owner reader-writer lock with PI fairness) so if anybody abuses rwlock_t unfairness in a way that is not strict owner recursive we have a problem. ]

#166 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 46 lines · On Mon, 27 Apr 2009 19:44:57 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 28 lines · Stephen Hemminger
Quoted 14 lines · On Sun, 26 Apr 2009 14:56:46 -0400 Mathieu Desnoyers…
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

Quoted 8 lines
Quoted 3 lines

Thanks to all for your help and patience

[PATCH] netfilter: use per-CPU recursive lock {XV}

Hi Eric,

Suitable name would probably be :

But Linus is trying to delude himself.

Quoted 7 lines

This usage is recursive even if he doesn't like the terminology. The same CPU has to be able to reacquire the read lock without deadlocking. If reader/writer locks were implemented in a pure writer gets priority method, then this code would break! So yes read locks can be used recursively now in Linux, but if the were implemented differently then this code would break. For example, the -rt kernel turns all read/write locks into mutexs, so the -rt kernel developers will have to address this.

A recursive lock has the property:

lock()
{

  if (lock->owner == current) {
    lock->depth++;
    return;

}

Quoted 8 lines

/* regular lock stuff */
}

unlock()
{
if (!--lock->depth)

    /* regular unlock */
}

Only on Linux, and only because you look at locking from the point of view of the magic variable "current" process point of view.

Quoted 6 lines

non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.

What rwlock_t has, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.

But what happens when this side effect disappears?

Quoted 11 lines

This is not what is called a recursive lock. A recursive lock would have each owner only once, this rwlock_t thing is simply so unfair that it can have unlimited owners, including multiple copies of the same one.

rwsem has fifo fairness, and therefore can deadlock in this scenario, suppose thread A does a read, thread B tries a write and blocks, then thread A recurses and tries to obtain another read ownership -- deadlock, as the FIFO fairness will demand the second read ownership will wait on the pending writer, which will wait on the outstanding read owner.

Quoted 7 lines

Now if rwsem were a fifo-fair recursive lock, the above would not deadlock, since it would detect that the task already had (read) ownership and simply increment the depth, instead of trying to acquire a second ownership.

This is all common and well understood terminology, not something Linus invented just to harras you with.

In Documentation/ ? online ? Where is the definition? The only reference I se is indirectly in DocBook/kernel-locking.tmpl.

Quoted 8 lines

Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing rwlock_t unfairness) are the only offenders.

Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.

The people complaining about naming never seem to be the ones providing workable suggestions or patches.

Quoted 7 lines

Linus is very much right on what he said, and you calling him delusional only high-lights your ignorance on the issue.

[ PS. -rt implements rwlock_t as a proper recursive lock (either a mutex
or a full multi-owner reader-writer lock with PI fairness) so if anybody abuses rwlock_t unfairness in a way that is not strict owner recursive we have a problem. ]

Name it "dog's breath locking" for all I care. I am not bothering with arguments over names; there is real work to do elsewhere.

#167 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 8 lines · Stephen Hemminger
Quoted 6 lines

non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.

What rwlock_t has, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.

But what happens when this side effect disappears?

Then well written code works, badly written code breaks.

Quoted 7 lines
Quoted 4 lines

[...]

This is all common and well understood terminology, not something Linus invented just to harras you with.

In Documentation/ ? online ? Where is the definition? The only reference I se is indirectly in DocBook/kernel-locking.tmpl.

Sure, see:

http://tinyurl.com/c6fakc

Quoted 5 lines
Quoted 5 lines

Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing rwlock_t unfairness) are the only offenders.

Quoted 7 lines
Quoted 4 lines

Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.

The people complaining about naming never seem to be the ones providing workable suggestions or patches.

The thing is, while you now have named your locking primitive correctly, you are still abusing it by using it recursively.

So it's not 'just about naming'. You should not use read-locks as recursive locks. It's poor code.

Ingo

#168 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 19 lines · On Mon, 27 Apr 2009 20:54:23 +0200 Ingo Molnar <[email protected]> wrote:
Quoted 8 lines · Stephen Hemminger
Quoted 6 lines

non of the linux kernel locking primitives have this -- with the possible exception of the cpu-hotplug lock.

What rwlock_t has, is reader bias to the point where you can utterly starve writers, with the side effect that you can obtain multiple read ownerships without causing a deadlock.

But what happens when this side effect disappears?

Then well written code works, badly written code breaks.

Quoted 5 lines
Quoted 4 lines

[...]

This is all common and well understood terminology, not something Linus invented just to harras you with.

Quoted 6 lines
Quoted 2 lines

In Documentation/ ? online ? Where is the definition? The only reference I se is indirectly in DocBook/kernel-locking.tmpl.

Sure, see:

http://tinyurl.com/c6fakc

All those references support my argument that the lock is being used recursively in this case. It is being acquired multiple times by the same CPU. This is not new, it has always been acquired multiple times, so my change does not break anything.

If other implementations of reader locks to not nest the same way, then on those system iptables can deadlock. Nothing was changed by this.

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines

Generally speaking we do not condone recursive locking strategies -- and afaik reiserfs (as per the BKL) and the network code (as per abusing rwlock_t unfairness) are the only offenders.

Like Linus stated, recursive locking is generally poor taste and indicates you basically gave up on trying to find a proper locking scheme. We should very much work towards getting rid of these abberations instead of adding new ones.

Quoted 8 lines
Quoted 2 lines

The people complaining about naming never seem to be the ones providing workable suggestions or patches.

The thing is, while you now have named your locking primitive correctly, you are still abusing it by using it recursively.

So it's not 'just about naming'. You should not use read-locks as recursive locks. It's poor code.

If you don't like the proposal please, think of a better alternative. Not just pseudo code that is broken with handwaving arguments.

#169 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 3 lines · Stephen Hemminger

All those references support my argument that the lock is being used recursively in this case.

What's so hard between understanding the difference between "used recursively" and "recursive lock"?

THEY MEAN TWO TOTALLY DIFFERENT THINGS!

The fact that you don't seem to understand that is one of the things I've been complaining about all along.

So here's a final set of clue-bat:

Clue bat #1:

- "can be used in a recursive context" is not the same as "is recursive".

Analogy time: Look at "strtok_r()", and the difference between that and "strtok()". "strtok_r()" can be used in a threaded environment. Does that mean that 'strtok_r()' is threaded? No. When you call 'strtok_r()', it's still signle-threaded - it's just that it _can_ be called in a threaded environment and then still has sane semantics.

Now, replace "threaded" with "recursive". Do you get it?

Clue bat #2:

- a lock that can count does not mean that it is recursive.

Counting and recursion are TWO TOTALLY DIFFERENT ISSUES. The "countingness" means that there can be multiple users inside of it, and that, in turn, implies that maybe it can be used in a recursive context. But again, counting and recursion are not about the same thing at all.

Put another way: a read-write lock is not a "recursive lock" despite the fact that you can recursively take the lock for reading. It just happens to count readers, and allow more than one (from _any_ context, not just from the "same context").

Clue bat #3:

- A recursive lock is very much _about_ recursion. It is explicitly about the fact that the _same_ thread re-enters the lock, not about another thread being in the locked region at the same time.

See the difference? Big, big difference. A recursive lock will lock out other thread contexts, even if it allows the current one to recurse. Notice how the _only_ thing a recursive lock allows is that recursive behavior, and nothing else.

IOW, a "recursive lock" is explicitly designed for recursion. But that doesn't mean that recursive algorithms cannot use functions that aren't.

Can you use "memcpy()" in a recursive algorithm? Yes. Does that mean that "memcpy()" is suddenly a "recursive memory copy"? No.

See the difference?

Clue bat #3:

- if you do not understand the difference between these two things, don't then try to claim that somebody _else_ who does understand it is "deluding himself".

Analogy time: Ethernet and a modem line can both get you on the internet. Now, let's say that Mr Peter Paste-Eater has heard of ethernet, and knows you can get on the internet with an ethernet connection, but he happens to use a modem line to do it.

Now, Peter Paste-Eater talks to you, and tells you he is connecting to the internet with ethernet, and proudly shows you his serial line and modem, and tells you how he uses ethernet to get onto the internet. You correct him, and tell him it's not ethernet. He argues for several days about how he gets on the internet, and that it must thus be ethernet, and that you're obviously just "deluding yourself".

Now, can you see why people react badly to you talking about "recursive locks"? You're acting like Peter Paste-Eater calling his serial line ethernet. The fact that two _different_ things can be used for the same end result DOES NOT MAKE THEM THE SAME THING.

In other words:

- "Recursive locks" are different from reader-writer locks.

- The ability to count is different from recursion, although in a lock it can obviously be _related_ to whether it can be used in a recursive environment or not. If you don't have a counter, you probably cannot recurse, but it's also not true that a counter implies that you always can.

A traditional counting lock is the old-fasioned 'semaphore' we have, where the count allows for more than just simple mutual exclusion, and is used when you might want to allow concurrency, but need to limit it to some number 'n' (although, almost always, n==1)

- What the netfilter code wants is simply not a recursive lock. It wants a form of locking that allows recursive _use_, but as mentioned, that is totally and utterly irrelevant from what we call it.

You _could_ use a recursive lock for it. BUT NONE OF THE PATCHES THAT HAVE EVER BEEN POSTED HAVE BEEN RECURSIVE LOCKS! Nada. None. Zero. Zilch.

So don't talk about recursive locks.

Get it? Finally? Or are you going to continue to be that Paste-Eater guy who refuses to understand that he is talking about something else than ethernet?

Linus

#170 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 8 lines · Linus Torvalds

Clue bat #1:

Clue bat #2:

Clue bat #3:

Clue bat #3:

Note to self: learn to count beyond three one of these days.

Linus

#171 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

In reply to Linus Torvalds

Hi.

Quoted 10 lines · Linus Torvalds
Quoted 2 lines

All those references support my argument that the lock is being used recursively in this case.

What's so hard between understanding the difference between "used recursively" and "recursive lock"?

THEY MEAN TWO TOTALLY DIFFERENT THINGS!

The fact that you don't seem to understand that is one of the things I've been complaining about all along.

Just ot be sure readers will not lose the discssion topic: do you object against naming or realizaion? If its about the former, does 'dog's breath lock' proposed by Stephen fit?

Signature · 1 line
	Evgeniy Polyakov
#172 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 3 lines · Evgeniy Polyakov

Just ot be sure readers will not lose the discssion topic: do you object against naming or realizaion?

I said _long_ ago that I thought the patch was fine.

What I object to is people mis-representing the lock, and apparently having a really hard time admitting that having a good grounding in networking doesn't necessarily mean that you know everything about something as basic as locking.

Quoted 2 lines

If its about the former, does 'dog's breath lock' proposed by Stephen fit?

Is that just an attempt to avoid admitting that they were wrong about lock naming? And then trying to trivialize it by calling things by a _different_ wrong name, but silly enough that they hope people won't call them on it?

Why not just use the correct name? I think it was Mathieu that just suggested:

[PATCH] netfilter: use bh disabling with per-cpu read-write lock

or just call it "netfilter: use per-CPU read-write lock".

Why are people so against calling things by their correct names? Why do certain network people seem to force a stupid and incorrect description, when they have been told (a) that it's wrong and (b) why it's wrong several times?

What's so hard with just doing the TechnicallyRightThing(tm) and describing it as such?

And btw - don't get me wrong. There are _other_ ways to do that locking too. You don't have to use a rwlock. You can do it with explicit counting, the way Eric's original patch did. But it would be wrong to call that one "recursive lock" too.

Or you _could_ use a recursive lock, but nobody has actually posted such patches. It would work. No question about it. And if it actually _were_ a recursive lock, I wouldn't have objected about the description saying it is (although I would probably have objected to it being unnecessarily complex, when a simpler rwlock or the explicit count thing would be sufficient).

But since the current simple patch is using a rwlock, why not just say that? Why call it something incorrect ("recursive lock") or nonsensical ("dog's breath lock").

As I tried to explain with an analogy, networking people would (quite correctly) object to me calling a serial line an "ethernet cable". Why is it so hard for netfilter people to then see why it's wrong to call a rwlock a "recursive lock".

I mean, guys, if you don't want to read up on decades of locking work, just google for it. Google for "recursive lock" (_with_ the quotes). At least for me, the very first hit gives a reasonable explanation for it, and it says:

"POSIX allows mutexes to be recursive. That means the same thread can
lock the same mutex twice and won't deadlock."

and realize that the "same thread" part is very much a keyword, not juat a random implementation detail (the first answer to the question is better than the question, but even the question at the top really does get at the basics).

And please do realize that neither rwlocks nor the counting locks from Dumazet's original patch do that. Never did. They simply aren't recursive locks.

So just don't call them that. But is "dog's breath" any better? Yes, maybe it's less _misleading_, but it sure as hell isn't any more descriptive.

Linus

#173 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 14 lines · On Mon, 27 Apr 2009 13:58:48 -0700 (PDT) Linus Torvalds…
Quoted 3 lines · Evgeniy Polyakov

Just ot be sure readers will not lose the discssion topic: do you object against naming or realizaion?

I said _long_ ago that I thought the patch was fine.

What I object to is people mis-representing the lock, and apparently having a really hard time admitting that having a good grounding in networking doesn't necessarily mean that you know everything about something as basic as locking.

Quoted 7 lines
Quoted 2 lines

If its about the former, does 'dog's breath lock' proposed by Stephen fit?

Is that just an attempt to avoid admitting that they were wrong about lock naming? And then trying to trivialize it by calling things by a _different_ wrong name, but silly enough that they hope people won't call them on it?

The part that concerns me is that the reader lock used in a nested manner on same cpu may still be broken on -rt. Other than that it is just language lawyering; violent agreement that the lock gets used multiple times by same CPU. I never had the occasion to address this before
(and avoided such usage), but this legacy code exists and needs to be dealt with.

Quoted 6 lines

Why not just use the correct name? I think it was Mathieu that just suggested:

[PATCH] netfilter: use bh disabling with per-cpu read-write lock

or just call it "netfilter: use per-CPU read-write lock".

[PATCH] netfilter: Ceci n'est pas une serrure récurrente

I don't care. I don't care. Don't you get the point yet.

Quoted 5 lines

Why are people so against calling things by their correct names? Why do certain network people seem to force a stupid and incorrect description, when they have been told (a) that it's wrong and (b) why it's wrong several times?

Because meaning comes from context, and my meaning comes from different context. So we disagree on correct names.

Quoted 37 lines

What's so hard with just doing the TechnicallyRightThing(tm) and describing it as such?

And btw - don't get me wrong. There are _other_ ways to do that locking too. You don't have to use a rwlock. You can do it with explicit counting, the way Eric's original patch did. But it would be wrong to call that one "recursive lock" too.

Or you _could_ use a recursive lock, but nobody has actually posted such patches. It would work. No question about it. And if it actually _were_ a recursive lock, I wouldn't have objected about the description saying it is (although I would probably have objected to it being unnecessarily complex, when a simpler rwlock or the explicit count thing would be sufficient).

But since the current simple patch is using a rwlock, why not just say that? Why call it something incorrect ("recursive lock") or nonsensical ("dog's breath lock").

As I tried to explain with an analogy, networking people would (quite correctly) object to me calling a serial line an "ethernet cable". Why is it so hard for netfilter people to then see why it's wrong to call a rwlock a "recursive lock".

I mean, guys, if you don't want to read up on decades of locking work, just google for it. Google for "recursive lock" (_with_ the quotes). At least for me, the very first hit gives a reasonable explanation for it, and it says:

"POSIX allows mutexes to be recursive. That means the same thread can
lock the same mutex twice and won't deadlock."

and realize that the "same thread" part is very much a keyword, not juat a random implementation detail (the first answer to the question is better than the question, but even the question at the top really does get at the basics).

Quoted 8 lines

And please do realize that neither rwlocks nor the counting locks from Dumazet's original patch do that. Never did. They simply aren't recursive locks.

So just don't call them that. But is "dog's breath" any better? Yes, maybe it's less _misleading_, but it sure as hell isn't any more descriptive.

Linus

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

#174 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 3 lines · Stephen Hemminger

The part that concerns me is that the reader lock used in a nested manner on same cpu may still be broken on -rt.

I think that's a valid concern, and I don't actually object to not using a rwlock, but using the "explicit counting + spinlock" that we had at one point. It _might_ even be faster, since a spinlock can be faster than a rwlock, and the (rare) case where you recurse you can then avoid the atomic entirely.

But EVEN IF YOU DO THAT, it's still wrong to call it a "recursive lock". Because it still wouldn't be one.

That's kind of my point, and always has been. It was why I objected to the original patch description by Dumazet. It wasn't a recursive lock back then _either_. For all the reasons I tried to explain to you, and you seem to not care about.

Btw, if you do use the "explicit count" case, then please please please make sure it's documented and bug-free. And dammit, correct documentation in this case very much talks about how it is _not_ a "recursive lock", but a spinlock that then has an explicit counter that avoids taking the lock entirely in one very specific path (that happens to be recursive).

The thing is, using a rwlock kind of implicitly documents all of that, because you can tell somebody who doesn't even read the code that it's a "per-cpu rwlock", and they then know what the semantics are (given that they know the kernel semantics for locking in the first place).

But once you start doing your own locking rules, you really have to explain why it works, and what it does. And you do have to be very careful, because it's so easy to get locking wrong.

Quoted 1 line

I don't care. I don't care. Don't you get the point yet.

If you don't care about the naming, then use the right one.

And if you don't care about the naming, why do you then say I'm deluding myself, when I'm _correct_, and I _do_ happen to care about correct naming.

Locking really is important. Code that gets locking wrong breaks in really subtle and nasty ways. And it sadly tends to "work" in testing, since the breakage cases require just the right timing. So locking should be robust and as "obviously correct" as possible.

And naming really is important. Misnaming things makes people make assumptions that aren't true. If you talk about recursive locks, it should be reasonable that people who know how recursive locks work would then make assumptions about them. If the code then doesn't actually match those rules, that's bad.

It's like having a comment in front of a piece of code that says something totally different than what the code actually does. It's _bad_. That's why naming matters so much - because naming is commentary. If you mis-name things on purpose, it's simply a bug.

Do _you_ get the point?

You _do_ care about bugs, don't you?

Linus

#175 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 6 lines · Linus Torvalds

Btw, if you do use the "explicit count" case, then please please please make sure it's documented and bug-free. And dammit, correct documentation in this case very much talks about how it is _not_ a "recursive lock", but a spinlock that then has an explicit counter that avoids taking the lock entirely in one very specific path (that happens to be recursive).

So, just as an example, I would not object to the counter approach, as long as it really talks about the issues, and why it works (and as long that doesn't call the locks "recursive locks").

So if you are just nervous about rwlocks, then something like this might work (needs testing, and other people to sanity-check it).

I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.

Now, it would actually be a really _bad_ reader-writer lock in general, exactly because it's not very "atomic" (ie this would be a truly sucky and broken lock if we didn't have the strict per-cpu usage rules).

So it just so happens that the per-cpu'ness of the lock, together with the very limited way in which it is used, make that sucky implementation possible - and indeed possibly faster than the standard (and generic) kernel rwlock implementation.

So it's basically a special-case rwlock that happens to work due to the specific rules.

And exactly because it really wouldn't work in the absense of those rules, those rules really do need to have big comments on them so that people don't then later forget about the limitations.

BTW: THIS IS TOTALLY UNTESTED. I just cut-and-pasted the existing rwlock version from one of the later patches, used the counting approach from one of the earlier ones, and basically just added what I think would be minimal required comments for this special case. All of it was written inside the mail reader, none of it has been compiled or tested in any other way.

Because it's exactly the "lock semantics awareness" that I think is so important here (and that's why all the naming and commentary is so critical).

Btw, the "counter" could probably be just a single bit, since apparently the nesting level is always supposed to be just one. I made it "unsigned char" just because sometimes spinlocks can be small, and it seemed the simplest type. But perhaps it would be better as an "unsigned int", since some architectures potentially could do that faster (eg old alphas).

Linus

---
/*
* Per-CPU spinlock associated with per-cpu table entries, and
* with a counter for the "reading" side that allows a recursive
* reader to avoid taking the lock and deadlocking.
*
* "reading" is used by ip/arp/ip6 tables rule processing which runs per-cpu.
* It needs to ensure that the rules are not being changed while the packet
* is being processed. In some cases, the read lock will be acquired
* twice on the same CPU; this is okay because of the count.
*
* The write lock is used in two cases:
* 1. reading counter values
* all rule processing need to be stopped and the per-CPU values are summed.
*
* 2. replacing tables

 *       any readers that are using the old tables have to complete
 *       before freeing the old table. This is handled by reading
 *       as a side effect of reading counters
 */
struct xt_info_lock {
	spin_lock_t lock;
	unsigned char readers;
};

DECLARE_PER_CPU(struct xt_info_lock, xt_info_locks);

/*
* Note: we need to ensure that preemption is disabled before acquiring
* the per-cpu-variable, so we do it as a two step process rather than
* using "spin_lock_bh()".
*
* We _also_ need to disable bottom half processing before updating our
* nesting count, to make sure that the only kind of re-entrancy is this
* code being called by itself: since the count+lock is not an atomic
* operation, we can allow no races.
*
* _Only_ that special combination of being per-cpu and never getting
* re-entered asynchronously means that the count is safe. */
static inline void xt_info_rdlock_bh(void)

{
	struct xt_info_lock *lock;

	local_bh_disable();
	lock = &__get_cpu_var(xt_info_locks);
	if (!lock->readers++)
		spin_lock(&lock->lock);
}

static inline void xt_info_rdunlock_bh(void)

{
	struct xt_info_lock *lock;

	lock = &__get_cpu_var(xt_info_locks);
	if (!--lock->readers)
		spin_unlock(&lock->lock);
}

/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. This must be called with bottom half
* processing (and thus also preemption) disabled.
*/
static inline void xt_info_wrlock(unsigned int cpu)

{
	spin_lock(&per_cpu(xt_info_locks, cpu).lock);
}

static inline void xt_info_wrunlock(unsigned int cpu)

{
	spin_unlock(&per_cpu(xt_info_locks, cpu).lock);
}
#176 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 2 lines · Linus Torvalds

BTW: THIS IS TOTALLY UNTESTED.

Gaah. I should have read through it one more time before sending.

Quoted 8 lines

static inline void xt_info_rdunlock_bh(void)

{
	struct xt_info_lock *lock;

	lock = &__get_cpu_var(xt_info_locks);
	if (!--lock->readers)
		spin_unlock(&lock->lock);
}

This one was missing the "local_bh_enable()" at the end.

There may be other bugs, but that's the one I noticed immediately when reading what I sent out. Oops.

Linus

#177 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 15 lines · Linus Torvalds
Quoted 1 line · Linus Torvalds

BTW: THIS IS TOTALLY UNTESTED.

Gaah. I should have read through it one more time before sending.

Quoted 8 lines

static inline void xt_info_rdunlock_bh(void)

{
	struct xt_info_lock *lock;

	lock = &__get_cpu_var(xt_info_locks);
	if (!--lock->readers)
		spin_unlock(&lock->lock);
}
Quoted 4 lines

This one was missing the "local_bh_enable()" at the end.

There may be other bugs, but that's the one I noticed immediately when reading what I sent out. Oops.

I am not sure my day job will permit me to polish a patch mixing all the bits and comments. But I am glad we eventually got back spinlocks which are probably better than rwlocks for implementing this stuff.

Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?

This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in Documentation/ )

Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?

Instead of local/global name that Paul suggested, that was about 'global' locking all locks at the same time. Not any more the good name IMHO

Maybe something like local/remote or owner/foreigner ?

xt_info_owner_lock_bh(), xt_info_owner_unlock_bh() xt_info_foreigner_lock(), xt_info_foreigner_unlock()

One comment about this comment you wrote :

/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. This must be called with bottom half
* processing (and thus also preemption) disabled.
*/
static inline void xt_info_wrlock(unsigned int cpu)

{
	spin_lock(&per_cpu(xt_info_locks, cpu).lock);
}

static inline void xt_info_wrunlock(unsigned int cpu)

{
	spin_unlock(&per_cpu(xt_info_locks, cpu).lock);
}

Its true that BH should be disabled if caller runs on the cpu it wants to lock.
For other ones (true foreigners), there is
no requirement about BH (current cpu could be interrupted by a softirq and packets could fly)

We could use following construct and not require disabling BH more than a short period of time.
(But preemption disabled for the whole duration)

preempt_disable(); // could be cpu_migration_disable();

int curcpu = smp_processor_id();
/*
* Gather stats for current cpu : must disable BH
* before trying to lock.
*/
local_bh_disable();
xt_info_wrlock(curcpu);
// copy stats of this cpu on my private data (not shown here) xt_info_wrunlock(curcpu);
local_bh_enable();

for_each_possible_cpu(cpu) {
	if (cpu == curcpu)
		continue;
	xt_info_wrlock(cpu);
	// fold stats of "cpu" on my private data (not shown here)
	xt_info_wrunlock((cpu);
}

preempt_enable(); // could be cpu_migration_enable();

So your initial comment could be changed to :

/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. If caller is about to lock its own lock,
* he must have disabled BH before. For other cpus, no special
* care but preemption disabled to guarantee no cpu migration. */

Back to work now :)

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

maintainer
#178 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Apr 2009 08:58:05 +0200

Quoted 4 lines

I am not sure my day job will permit me to polish a patch mixing all the bits and comments. But I am glad we eventually got back spinlocks which are probably better than rwlocks for implementing this stuff.

Quoted 8 lines

Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?

This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in Documentation/ )

Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?

I say we merge Linus's locking idea into the XV patch, fixup the commit message wording, and move on with life.

For something that's going to get deleted as soon as the faster grace period RCU stuff is available, it has consumed an inordinate amount of our time :-)

I might take a stab at this before hittng bed tonight, no promises :)

#179 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 16 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Tue, 28 Apr 2009 08:58:05 +0200

Quoted 4 lines

I am not sure my day job will permit me to polish a patch mixing all the bits and comments. But I am glad we eventually got back spinlocks which are probably better than rwlocks for implementing this stuff.

Quoted 8 lines

Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?

This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in Documentation/ )

Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?

Quoted 6 lines

I say we merge Linus's locking idea into the XV patch, fixup the commit message wording, and move on with life.

For something that's going to get deleted as soon as the faster grace period RCU stuff is available, it has consumed an inordinate amount of our time :-)

One more reason to factor out this code into general locking code.

The latest code looks a bit similar to the old big-reader-locks hack (which got dropped for good many eons ago and with which i deny any involvement with, such as having authored it. [oh, did i say that out loud? crap.]), implemented cleanly and properly.

IMHO this locking construct should be considered for linux/local_lock.h and kernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)

[ The _only_ thing i am worried about is the apparent fact that
there's so much confusion about recursion versus read-access. Recursion might be hard to factor out of the netfilter code, and maybe it's not even possible realistically (we fought years with the BKL and are still fighting it) but if its harms are not even _realized_ that difficult task turns into an impossible task ;-) ]

Ingo

maintainer
#180 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

From: Ingo Molnar <[email protected]>
Date: Tue, 28 Apr 2009 14:40:33 +0200

Quoted 3 lines

IMHO this locking construct should be considered for linux/local_lock.h and kernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)

If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)

It has to be dereferenced after local_bh_disable() for the read side acquisition.

#181 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 7 lines · * David Miller ([email protected]) wrote:

From: Ingo Molnar <[email protected]>
Date: Tue, 28 Apr 2009 14:40:33 +0200

Quoted 3 lines

IMHO this locking construct should be considered for linux/local_lock.h and kernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)

Quoted 6 lines

If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)

It has to be dereferenced after local_bh_disable() for the read side acquisition.

The local_bh_disable() could be outside of the locking construct. This would make it easier to adapt it to various users (irq disable, bh disable, preempt disable) depending on the contexts from which they much be protected.

And if it still does not work for some reason, using a #define is discouraged, but could work.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
maintainer
#182 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

From: Mathieu Desnoyers <[email protected]>
Date: Tue, 28 Apr 2009 09:52:19 -0400

Quoted 7 lines

The local_bh_disable() could be outside of the locking construct. This would make it easier to adapt it to various users (irq disable, bh disable, preempt disable) depending on the contexts from which they much be protected.

And if it still does not work for some reason, using a #define is discouraged, but could work.

That's what I was hoping to avoid, things like macros and having the callers of this thing expand the two parts of the operation.

What's the point in making this generic if it ends up being ugly as hell?

#183 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 8 lines · * David Miller ([email protected]) wrote:

From: Mathieu Desnoyers <[email protected]>
Date: Tue, 28 Apr 2009 09:52:19 -0400

Quoted 5 lines

The local_bh_disable() could be outside of the locking construct. This would make it easier to adapt it to various users (irq disable, bh disable, preempt disable) depending on the contexts from which they much be protected.

Quoted 8 lines
Quoted 2 lines

And if it still does not work for some reason, using a #define is discouraged, but could work.

That's what I was hoping to avoid, things like macros and having the callers of this thing expand the two parts of the operation.

What's the point in making this generic if it ends up being ugly as hell?

.. and what's the point in making it generic if it can be replaced by a proper RCU implementation ? :-) I am not convinced of the added value we get in making it a generic header this soon. I would wait for other users to express similar needs, otherwise this could soon become an orphaned piece of locking code.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
maintainer
#184 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

From: Mathieu Desnoyers <[email protected]>
Date: Tue, 28 Apr 2009 10:49:20 -0400

Quoted 5 lines

.. and what's the point in making it generic if it can be replaced by a proper RCU implementation ? :-) I am not convinced of the added value we get in making it a generic header this soon. I would wait for other users to express similar needs, otherwise this could soon become an orphaned piece of locking code.

That is my opinion as well.

Anyways, here is a patch that builds, I haven't started working on the commit message yet.

include/linux/netfilter/x_tables.h +73 -5
index 7b1a652..086e976 100644
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,79 @@ extern void xt_proto_fini(struct net *net, u_int8_t af);
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+/*
+ * Per-CPU spinlock associated with per-cpu table entries, and
+ * with a counter for the "reading" side that allows a recursive
+ * reader to avoid taking the lock and deadlocking.
+ *
+ * "reading" is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while the packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because of the count.
+ *
+ * The write lock is used in two cases:
+ *    1. reading counter values
+ *       all rule processing need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *       as a side effect of reading counters
+ */
+struct xt_info_lock {
+	spinlock_t lock;
+	unsigned char readers;
+};
+DECLARE_PER_CPU(struct xt_info_lock, xt_info_locks);
+
+/*
+ * Note: we need to ensure that preemption is disabled before acquiring
+ * the per-cpu-variable, so we do it as a two step process rather than
+ * using "spin_lock_bh()". 
+ *
+ * We _also_ need to disable bottom half processing before updating our
+ * nesting count, to make sure that the only kind of re-entrancy is this
+ * code being called by itself: since the count+lock is not an atomic
+ * operation, we can allow no races. 
+ *
+ * _Only_ that special combination of being per-cpu and never getting
+ * re-entered asynchronously means that the count is safe. 
+ */
+static inline void xt_info_rdlock_bh(void)
+{
+	struct xt_info_lock *lock;
+
+	local_bh_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (!lock->readers++)
+		spin_lock(&lock->lock);
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	struct xt_info_lock *lock;
+
+	lock = &__get_cpu_var(xt_info_locks);
+	if (!--lock->readers)
+		spin_unlock(&lock->lock);
+	local_bh_enable();
+}
+
+/*
+ * The "writer" side needs to get exclusive access to the lock,
+ * regardless of readers.  This must be called with bottom half
+ * processing (and thus also preemption) disabled. 
+ */
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	spin_lock(&per_cpu(xt_info_locks, cpu).lock);
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+	spin_unlock(&per_cpu(xt_info_locks, cpu).lock);
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89

215 lines not on this page · raw message

net/ipv4/netfilter/ip_tables.c +35 -91

211 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +37 -86

208 lines not on this page · raw message

net/netfilter/x_tables.c +25 -25

91 lines not on this page · raw message

#185 lore raw

PATCH 1/1 netfilter: revised locking for x_tables

The x_tables are organized with a table structure and a per-cpu copies of the counters and rules. On older kernels there was a reader/writer lock per table which was a performance bottleneck. In 2.6.30-rc, this was converted to use RCU and the counters/rules which solved the performance problems for do_table but made replacing rules much slower because of the necessary RCU grace period.

This version uses a per-cpu set of spinlocks and counters to allow to table processing to proceed without the cache thrashing of a global reader lock and keeps the same performance for table updates.

---
Probably same as dave/linus but with different comments.

 include/linux/netfilter/x_tables.h |   73 +++++++++++++++++++--
 net/ipv4/netfilter/arp_tables.c    |  125 ++++++++++--------------------------
 net/ipv4/netfilter/ip_tables.c     |  126 ++++++++++---------------------------
 net/ipv6/netfilter/ip6_tables.c    |  123 ++++++++++--------------------------
 net/netfilter/x_tables.c           |   53 ++++++++-------
 5 files changed, 204 insertions(+), 296 deletions(-)
include/linux/netfilter/x_tables.h +68 -5
@@ -354,9 +354,6 @@ struct xt_table
 	/* What hooks you will enter on */
 	unsigned int valid_hooks;
 
-	/* Lock for the curtain */
-	struct mutex lock;
-
 	/* Man behind the curtain... */
 	struct xt_table_info *private;
 
@@ -434,8 +431,74 @@ extern void xt_proto_fini(struct net *ne
 
 extern struct xt_table_info *xt_alloc_table_info(unsigned int size);
 extern void xt_free_table_info(struct xt_table_info *info);
-extern void xt_table_entry_swap_rcu(struct xt_table_info *old,
-				    struct xt_table_info *new);
+
+/*
+ * Per-CPU spinlock associated with per-cpu table entries, and
+ * with a counter for the "reading" side that allows a recursive
+ * reader to avoid taking the lock and deadlocking.
+ *
+ * "reading" is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while the packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because of the count.
+ *
+ * "writing" is used when reading counters.
+ *  During replace any readers that are using the old tables have to complete
+ *  before freeing the old table. This is handled by the write locking
+ *  necessary for reading the counters.
+ */
+struct xt_info_lock {
+	spinlock_t lock;
+	unsigned char readers;
+};
+DECLARE_PER_CPU(struct xt_info_lock, xt_info_locks);
+
+/*
+ * Note: we need to ensure that preemption is disabled before acquiring
+ * the per-cpu-variable, so we do it as a two step process rather than
+ * using "spin_lock_bh()".
+ *
+ * We _also_ need to disable bottom half processing before updating our
+ * nesting count, to make sure that the only kind of re-entrancy is this
+ * code being called by itself: since the count+lock is not an atomic
+ * operation, we can allow no races.
+ *
+ * _Only_ that special combination of being per-cpu and never getting
+ * re-entered asynchronously means that the count is safe.
+ */
+static inline void xt_info_rdlock_bh(void)
+{
+	struct xt_info_lock *lock;
+
+	local_bh_disable();
+	lock = &__get_cpu_var(xt_info_locks);
+	if (!lock->readers++)
+		spin_lock(&lock->lock);
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks);
+
+	if (!--lock->readers)
+		spin_unlock(&lock->lock);
+	local_bh_enable();
+}
+
+/*
+ * The "writer" side needs to get exclusive access to the lock,
+ * regardless of readers.  This must be called with bottom half
+ * processing (and thus also preemption) disabled.
+ */
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	spin_lock(&per_cpu(xt_info_locks, cpu).lock);
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+	spin_unlock(&per_cpu(xt_info_locks, cpu).lock);
+}
 
 /*
  * This helper is performance critical and must be inlined
net/ipv4/netfilter/arp_tables.c +36 -89

215 lines not on this page · raw message

net/ipv4/netfilter/ip_tables.c +35 -91

211 lines not on this page · raw message

net/ipv6/netfilter/ip6_tables.c +37 -86

208 lines not on this page · raw message

net/netfilter/x_tables.c +28 -25

94 lines not on this page · raw message

#186 lore raw

Re: [PATCH] netfilter: revised locking for x_tables

Ack.

It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around get_counters() (and then the local_bh_disable() only around the current-CPU case).

I _think_ get_counters() is the only case that can use that optimization, but it's quite possible that it's worth doing especially for machines with lots of cores, if BH latency is an issue (and it might be).

Of course, for the lots-and-lots of cores case, even the preemption disable might be an issue. And then it really does get much more complicated. At that point, you probably want the RCU thing.

Linus

#187 lore raw

Re: [PATCH] netfilter: revised locking for x_tables

Quoted 6 lines · Linus Torvalds

Ack.

It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around get_counters() (and then the local_bh_disable() only around the current-CPU case).

Btw, regardless, that's an incremental improvement, and does not negate the "Ack" part.

Linus

maintainer Applied
#188 lore raw

Re: [PATCH] netfilter: revised locking for x_tables

From: Linus Torvalds <[email protected]>
Date: Tue, 28 Apr 2009 09:55:32 -0700 (PDT)

Quoted 10 lines · Linus Torvalds
Quoted 6 lines

Ack.

It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around get_counters() (and then the local_bh_disable() only around the current-CPU case).

Btw, regardless, that's an incremental improvement, and does not negate the "Ack" part.

I've applied this, thanks everyone!

author
#189 lore raw

Re: [PATCH] netfilter: revised locking for x_tables

Quoted 1 line · David Miller

I've applied this, thanks everyone!

I see the patch is already in Linus's tree that I just git pulled. Tested for 200 iptables rules ... as fast as before the slow down.

real    0m0.211s
user    0m0.060s
sys     0m0.144s

Thank you all for fixing this bug!

Quoted 6 lines · Rafael J. Wysocki

Bug-Entry : http://bugzilla.kernel.org/show_bug.cgi?id=13118
Subject : iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49
Submitter : Jeff Chua <[email protected]>
Date : 2009-04-10 16:05 (16 days old)
References : http://lkml.org/lkml/2009/4/10/111

Rafael, it's fixed. Please close the case.

Thanks,
Jeff.

maintainer
#190 lore raw

Re: [PATCH] netfilter: revised locking for x_tables

From: Jeff Chua <[email protected]>
Date: Thu, 30 Apr 2009 11:26:40 +0800

Quoted 11 lines · David Miller
Quoted 1 line

I've applied this, thanks everyone!

I see the patch is already in Linus's tree that I just git pulled. Tested for 200 iptables rules ... as fast as before the slow down.

real    0m0.211s
user    0m0.060s
sys     0m0.144s

Thank you all for fixing this bug!

Thanks for testing.

#191 lore raw

PATCH 1/1 netfilter: use likely() in xt_info_rdlock_bh()

In reply to David Miller
Quoted 6 lines · David Miller

From: Linus Torvalds <[email protected]>
Date: Tue, 28 Apr 2009 09:55:32 -0700 (PDT)

Quoted 3 lines · Linus Torvalds
Quoted 2 lines

Ack.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

It could do with the update from Eric about how non-current CPU writelocks only require preemp-disable around get_counters() (and then the local_bh_disable() only around the current-CPU case).

Btw, regardless, that's an incremental improvement, and does not negate the "Ack" part.

I've applied this, thanks everyone!

Small followup on this one, since the likely() were forgotten. (I trimmed down CCed list, which was insane)

It makes a difference on my x86_32 machine, gcc-4.4.0

Thank you

[PATCH] netfilter: use likely() in xt_info_rdlock_bh()

---

include/linux/netfilter/x_tables.h +2 -2
index 1b2e435..c9efe03 100644
@@ -472,7 +472,7 @@ static inline void xt_info_rdlock_bh(void)
 
 	local_bh_disable();
 	lock = &__get_cpu_var(xt_info_locks);
-	if (!lock->readers++)
+	if (likely(!lock->readers++))
 		spin_lock(&lock->lock);
 }
 
@@ -480,7 +480,7 @@ static inline void xt_info_rdunlock_bh(void)
 {
 	struct xt_info_lock *lock = &__get_cpu_var(xt_info_locks);
 
-	if (!--lock->readers)
+	if (likely(!--lock->readers))
 		spin_unlock(&lock->lock);
 	local_bh_enable();
 }

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

#193 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

In reply to David Miller
Quoted 7 lines · David Miller

From: Ingo Molnar <[email protected]>
Date: Tue, 28 Apr 2009 14:40:33 +0200

Quoted 3 lines

IMHO this locking construct should be considered for linux/local_lock.h and kernel/local_lock.c. Even if the netfilter code drops its use soon afterwards ;-)

Quoted 6 lines

If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)

It has to be dereferenced after local_bh_disable() for the read side acquisition.

The way I did this in treercu.c was to create an array of references to the per-CPU data in question. Not necessarily recommended, but one way of doing it. That said, one could argue that we should wait until we have at least three users before creating a generic primitive.

And I just know that I am going to regret this deeply, but I cannot resist posting the following URL:

http://en.wikipedia.org/wiki/Wikipedia:Avoid_Parkinson's_Bicycle_Shed_Effect

Thanx, Paul

#194 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 11 lines · Paul E. McKenney
Quoted 6 lines

If you can show me have to pass a per-cpu variable (the variable, not a dereference of it) as an argument to an inline function, I'll implement this :-)

It has to be dereferenced after local_bh_disable() for the read side acquisition.

The way I did this in treercu.c was to create an array of references to the per-CPU data in question. Not necessarily recommended, but one way of doing it. That said, one could argue that we should wait until we have at least three users before creating a generic primitive.

The new percpu allocator allows you to create a per cpu pointer and pass it to functions.

per_cpu_ptr(pointer,cpu) is used to select an instance.

#195 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

In reply to Eric Dumazet
Quoted 3 lines · Eric Dumazet

Instead of submitting a full patch again, we could first submit a new
include file containg all comments and inline functions ?

Well, I actually already suggested to David that he should just merge the last patch I saw floating around (with the "recursive" -> "readwrite" fix in the comment ;), so that we can at least get the basic issue fixed, and then we can tweak it a bit with smaller patches flying around.

And at least right now, the difference between the rwlock and the "count+spinlock" should be basically almost unnoticeable, and a very small implementation issue. They're entirely interchangeable, after all.

Quoted 5 lines

This include file could be local to netfilter, with a big stick on it to forbids its use on other areas (No changes in Documentation/ )

Then, as soon as we can go back to pure RCU solution, we can safely delete this controversial-locking-nesting-per-cpu-thing ?

I don't have any strogn preferences, but I'd almost prefer to not abstract things out even that much. It's already pretty well hidden inside <netfilter/x_tables.h>, I'd hate to add a new file just for this.

As to just adding more commenting that it must not be used anywhere else, I certainly agree with that.

Quoted 5 lines

Instead of local/global name that Paul suggested, that was about 'global' locking all locks at the same time. Not any more the good name IMHO

Maybe something like local/remote or owner/foreigner ?

local/remote works for me, and yes, since we only take the remote side one CPU at a time, I guess "global" is misleading. But "owner/foreigner" sounds pretty odd.

Quoted 8 lines

One comment about this comment you wrote :

/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. This must be called with bottom half
* processing (and thus also preemption) disabled.
*/

Quoted 5 lines

Its true that BH should be disabled if caller runs on the cpu it wants to lock.
For other ones (true foreigners), there is
no requirement about BH (current cpu could be interrupted by a softirq and packets could fly)

Yes. Other CPU's just require preemption protection.

Quoted 17 lines

We could use following construct and not require disabling BH more than a short period of time.
(But preemption disabled for the whole duration)

preempt_disable(); // could be cpu_migration_disable();

int curcpu = smp_processor_id();
/*
* Gather stats for current cpu : must disable BH
* before trying to lock.
*/
local_bh_disable();
xt_info_wrlock(curcpu);
// copy stats of this cpu on my private data (not shown here) xt_info_wrunlock(curcpu);
local_bh_enable();

Quoted 8 lines
for_each_possible_cpu(cpu) {
	if (cpu == curcpu)
		continue;
	xt_info_wrlock(cpu);
	// fold stats of "cpu" on my private data (not shown here)
	xt_info_wrunlock((cpu);
}

preempt_enable(); // could be cpu_migration_enable();

Agreed.

Quoted 8 lines

So your initial comment could be changed to :

/*
* The "writer" side needs to get exclusive access to the lock,
* regardless of readers. If caller is about to lock its own lock,
* he must have disabled BH before. For other cpus, no special
* care but preemption disabled to guarantee no cpu migration. */

Ack.

Linus

#196 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

In reply to Linus Torvalds
Quoted 5 lines · Linus Torvalds

I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.

Btw, I think it was Paul who pointed out that technically it's probably better to call them "local" and "global" lockers instead of "readers" and "writers".

That also probably clarifies the rules on when you use one over the other (ie reading off all the statistics is a "global" operation, as is obviously replacing the tables).

Of course, "readers" and "writers" is something most Linux lock people are more used to. Or "brlock" for the old-timers, but that involves a heavy dose of bad taste. The new use is much nicer, especially since it never takes the global lock on _all_ cpu's (which was really a killer in so many ways).

Linus

#197 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 11 lines · Linus Torvalds
Quoted 5 lines · Linus Torvalds

I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.

Btw, I think it was Paul who pointed out that technically it's probably better to call them "local" and "global" lockers instead of "readers" and "writers".

exclusive vs non-exclusive is what the literature would call them in most cases I think.

Quoted 11 lines

That also probably clarifies the rules on when you use one over the other (ie reading off all the statistics is a "global" operation, as is obviously replacing the tables).

Of course, "readers" and "writers" is something most Linux lock people are more used to. Or "brlock" for the old-timers, but that involves a heavy dose of bad taste. The new use is much nicer, especially since it never takes the global lock on _all_ cpu's (which was really a killer in so many ways).

Linus

#198 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Linus Torvalds
Quoted 5 lines · Linus Torvalds

I left the commentary about "readers" and "writers", because in many ways it's correct, and what the code actually does is very much to emulate a reader-writer lock. I put quotes around the uses in the comments to high-light that it largely _acts_ as a reader-writer lock.

Quoted 6 lines
Quoted 3 lines

Btw, I think it was Paul who pointed out that technically it's probably better to call them "local" and "global" lockers instead of "readers" and "writers".

exclusive vs non-exclusive is what the literature would call them in most cases I think.

I would argue that the non-exclusive category includes both reader-writer locking and local-global locking. That said, we have an unusual variant of local-global in this case, as the global processing acquires only one of the locks at a time.

Thanx, Paul

#199 lore raw

Re: [PATCH] netfilter: use per-CPU r**ursive lock {XV}

In reply to Linus Torvalds
Quoted 18 lines · Linus Torvalds

Clue bat #3 [sic #4]:

- if you do not understand the difference between these two things, don't then try to claim that somebody _else_ who does understand it is "deluding himself".

Analogy time: Ethernet and a modem line can both get you on the internet. Now, let's say that Mr Peter Paste-Eater has heard of ethernet, and knows you can get on the internet with an ethernet connection, but he happens to use a modem line to do it.

Now, Peter Paste-Eater talks to you, and tells you he is connecting to the internet with ethernet, and proudly shows you his serial line and modem, and tells you how he uses ethernet to get onto the internet. You correct him, and tell him it's not ethernet. He argues for several days about how he gets on the internet, and that it must thus be ethernet, and that you're obviously just "deluding yourself".

Quoted 3 lines

Now, can you see why people react badly to you talking about "recursive locks"? You're acting like Peter Paste-Eater calling his serial line ethernet.

It could be worse. He could be running Ethernet over serial, e.g. L2TP. Or his serial line is a TP cable with RJ45 plugs - consumers like to call that Ethernet (cable) too.

#200 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

In reply to Eric Dumazet
Quoted 13 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

[...]

Quoted 21 lines
include/linux/netfilter/x_tables.h +21 -0
+/*
+ * Per-CPU read/write lock associated with per-cpu table entries.
+ * This is not a general solution but makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since update must lock all
+ * possible CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because read locks handle nesting.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *	  as a side effect of reading counters
+ */

include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 465

Quoted 10 lines
include/linux/netfilter/x_tables.h +10 -0
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	/*
+	 * Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
+	 * because need to ensure that preemption is disable before
+	 * acquiring per-cpu-variable, so do it as a two step process
+	 */
+	local_bh_disable();

Why do you need to disable bottom halves on the read-side ? You could probably just disable preemption, given this lock is nestable on the read-side anyway. Or I'm missing something obvious ?

Quoted 9 lines
include/linux/netfilter/x_tables.h +8 -0
+	read_lock(&__get_cpu_var(xt_info_locks));
+}
+
+static inline void xt_info_rdunlock_bh(void)
+{
+	read_unlock_bh(&__get_cpu_var(xt_info_locks));
+}
+

include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 483

Quoted 10 lines
include/linux/netfilter/x_tables.h +10 -0
+static inline void xt_info_wrlock(unsigned int cpu)
+{
+	write_lock(&per_cpu(xt_info_locks, cpu));
+}
+
+static inline void xt_info_wrunlock(unsigned int cpu)
+{
+
+	write_unlock(&per_cpu(xt_info_locks, cpu));
+}

[...]

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#201 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

Quoted 41 lines · Mathieu Desnoyers
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

[...]

Quoted 27 lines
include/linux/netfilter/x_tables.h +27 -0
+/*
+ * Per-CPU read/write lock associated with per-cpu table entries.
+ * This is not a general solution but makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since update must lock all
+ * possible CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because read locks handle nesting.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *	  as a side effect of reading counters
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	/*
+	 * Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
Quoted 8 lines

include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 465

Quoted 4 lines
include/linux/netfilter/x_tables.h +4 -0
+	 * because need to ensure that preemption is disable before
+	 * acquiring per-cpu-variable, so do it as a two step process
+	 */
+	local_bh_disable();

Why do you need to disable bottom halves on the read-side ? You could probably just disable preemption, given this lock is nestable on the read-side anyway. Or I'm missing something obvious ?

It may not be obvious, but subject already raised on this list, so I'll try to be as precise as possible (But may be wrong on some points, I'll let Patrick correct me if necessary)

ipt_do_table() is not a readonly function returning a verdict.

1) It handles a stack (check how is used next->comefrom) that seems to be stored on rules themselves. (This is how I understand this code) This is safe as each cpu has its own copy of rules/counters, and BH protected.

2) It also updates two 64 bit counters (bytes/packets) on each matched rule.

3) Some netfilter matches/targets probably rely on the fact their handlers are run with BH disabled by their caller (ipt_do_table()/arp/ip6...)

These must be BH protected (and preempt disabled too), or else :

1) A softirq could interrupt a process in the middle of ipt_do_table() and corrupt its "stack".

2) A softirq could interrupt a process in ipt_do_table() in the middle of the ADD_COUNTER(). Some counters could be corrupted.

3) Some netfiler extensions would break.

Previous linux versions already used a read_lock_bh() here, on a single and shared rwlock, there is nothing new on this BH locking AFAIK.

Thank you

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

#202 lore raw

Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

Quoted 74 lines · * Eric Dumazet ([email protected]) wrote:
Quoted 41 lines · Mathieu Desnoyers
Quoted 12 lines · * Eric Dumazet ([email protected]) wrote:

From: Stephen Hemminger <[email protected]>

Quoted 4 lines

Epilogue due to master Jarek. Lockdep carest not about the locking doth bestowed. Therefore no keys are needed.

So far, so good, should be ready for inclusion now, nobody complained :)

I include the final patch, merge of your last two patches.

David, could you please review it once again and apply it if it's OK ?

[...]

Quoted 27 lines
include/linux/netfilter/x_tables.h +27 -0
+/*
+ * Per-CPU read/write lock associated with per-cpu table entries.
+ * This is not a general solution but makes reader locking fast since
+ * there is no shared variable to cause cache ping-pong; but adds an
+ * additional write-side penalty since update must lock all
+ * possible CPU's.
+ *
+ * Read lock is used by ip/arp/ip6 tables rule processing which runs per-cpu.
+ * It needs to ensure that the rules are not being changed while packet
+ * is being processed. In some cases, the read lock will be acquired
+ * twice on the same CPU; this is okay because read locks handle nesting.
+ *
+ * Write lock is used in two cases:
+ *    1. reading counter values
+ *       all readers need to be stopped and the per-CPU values are summed.
+ *
+ *    2. replacing tables
+ *       any readers that are using the old tables have to complete
+ *       before freeing the old table. This is handled by reading
+ *	  as a side effect of reading counters
+ */
+DECLARE_PER_CPU(rwlock_t, xt_info_locks);
+
+static inline void xt_info_rdlock_bh(void)
+{
+	/*
+	 * Note: can not use read_lock_bh(&__get_cpu_var(xt_info_locks))
Quoted 8 lines

include/linux/netfilter/x_tables.h extern void xt_proto_fini(struct net *net, u_int8_t af); · line 465

Quoted 4 lines
include/linux/netfilter/x_tables.h +4 -0
+	 * because need to ensure that preemption is disable before
+	 * acquiring per-cpu-variable, so do it as a two step process
+	 */
+	local_bh_disable();

Why do you need to disable bottom halves on the read-side ? You could probably just disable preemption, given this lock is nestable on the read-side anyway. Or I'm missing something obvious ?

It may not be obvious, but subject already raised on this list, so I'll try to be as precise as possible (But may be wrong on some points, I'll let Patrick correct me if necessary)

ipt_do_table() is not a readonly function returning a verdict.

1) It handles a stack (check how is used next->comefrom) that seems to be stored on rules themselves. (This is how I understand this code) This is safe as each cpu has its own copy of rules/counters, and BH protected.

2) It also updates two 64 bit counters (bytes/packets) on each matched rule.

3) Some netfilter matches/targets probably rely on the fact their handlers are run with BH disabled by their caller (ipt_do_table()/arp/ip6...)

These must be BH protected (and preempt disabled too), or else :

1) A softirq could interrupt a process in the middle of ipt_do_table() and corrupt its "stack".

2) A softirq could interrupt a process in ipt_do_table() in the middle of the ADD_COUNTER(). Some counters could be corrupted.

Quoted 6 lines

3) Some netfiler extensions would break.

Previous linux versions already used a read_lock_bh() here, on a single and shared rwlock, there is nothing new on this BH locking AFAIK.

Thank you

Thanks for the explanation. It might help to document the role of bh disabling for the reader in a supplementary code comment, otherwise one might think it's been put there to match the bottom half disabling used on the write-side, which has the supplementary role of making sure bh will not deadlock (and this precise behavior is not needed usually on the read-side).

One more point :

* 1. reading counter values
* all readers need to be stopped and the per-CPU values are summed.

Maybe it's just me, but this sentence does not seem to clearly indicate that we have :

for_each_cpu()
write lock()
read data
write unlock()

One might interpret it as :

for_each_cpu()
write lock()

read data

for_each_cpu()
write unlock()

Or maybe it's just my understanding of English that's not perfect. Anyhow, rewording this sentence might not hurt. Something along the lines of :

"reading counter values
all readers are iteratively stopped to have their per-CPU values summed"

This is an important difference, as this behaves more like a RCU-based mechanism than a global per-cpu read/write lock where all the write locks would be taken at once.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#203 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

In reply to Linus Torvalds
Quoted 3 lines · Linus Torvalds

Ok, so others already pointed out how dangerous/buggy this looks, but I'd like to strengthen that a bit more:

I believe that at least some of this is naming...

Quoted 1 line · Stephen Hemminger

[ . . . ]

Quoted 19 lines

If you want a counting read-lock (in _order_ to allow recursion, but not because the lock itself is somehow recursive!), then that function should look like this:

	void xt_info_rdlock_bh(void)
	{
		struct xt_info_lock *lock

		local_bh_disable();
		lock = &__get_cpu_var(xt_info_locks);
		read_lock(&lock->lock);
	}

And then the "unlock" should be the reverse. No games, no crap, and hopefully then no bugs. And if you do it that way, you don't even need the comments, although quite frankly, it probably makes a lot of sense to talk about the interaction between "local_bh_disable()" and the preempt count, and why you're not using "read_lock_bh()".

Quoted 3 lines

And if you don't want a read-lock, then fine - don't use a read-lock, do something else. But then don't just re-implement it (badly) either and call it something else!

Sigh!!!

Part of the problem is that back in 1971, Courtois, Heymans, and Parnas foolishly named their article "Concurrent Control with 'Readers' and 'Writers'", which lead to the name "reader-writer lock". This started really biting around 1991, when Hsieh and Weihl created a reader-optimized lock similar to brlock, but with each of the per-CPU locks being exclusive rather than each being an rwlock.

The problem was that Hsieh's and Weihl's lock was more than just a reader-writer lock. It could also be used (and -was- used) as a local/global lock, where for example you acquire your own lock to make local changes, and acquire all of the locks to obtain a consistent view of global state. In which case, you would read-acquire the lock in order to write, and write-acquire the lock in order to read. Blech.

So, would it help if the function names names in this patch said something about "local" and "global" rather than "read" and "write"?

Thanx, Paul

Quoted 6 lines

Linus

PS: Ingo, why do the *_bh() functions in kernel/spinlock.c do _both_ a "local_bh_disable()" and a "preempt_disable()"? BH disable should disable preemption too, no? Or am I confused? In which case we need that in the above rdlock_bh too.

#204 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v11)

Quoted 2 lines · Paul E. McKenney

I believe that at least some of this is naming...

Maybe.

I do agree that the way netfilter would use the lock is somewhat different from a normal 'reader-writer' lock, since this special case of readers is about a per-cpu thing.

Quoted 2 lines

So, would it help if the function names names in this patch said something about "local" and "global" rather than "read" and "write"?

Oh, I would have no problem at all with 'local' and 'global', in fact it would explain _why_ that read-write lock works.

The problem with naming I have is with the 'recursive' part. There is no ambiguity what-so-ever about what a "recursive lock" is (at least of the traditional kind), and the lock described here is not it.

So don't get me wrong - I could certainly live with a special lock in the networking. BUT:

- it had damn well be documented as to what it does, and why it works

- and it had better actually _work_, and not be buggy.

I suspect that using our regular reader-writer locks works well enough, and yes, it's probably worth making it really clear that the reader variety can only ever be used in the "local" form. That kind of is implied by the whole function, though.

And if somebody wants to open-code it as a per-cpu spinlock and a per-cpu 'local counter', I can live with that too, but at that point I want people to just be a lot more careful, and also document it a lot more.

Linus

#205 lore raw

Re: [PATCH] netfilter: use per-cpu recursive lock (v10)

In reply to Paul Mackerras
Quoted 5 lines · Paul Mackerras
Quoted 2 lines · Paul E. McKenney

But a single CPU is acquiring one lock per CPU, so all the increments are to one CPU's preempt_count. :-(

Quoted 7 lines

OK, I see, so a task can't take more than 255 spinlocks without overflowing the preempt count, which seems a bit limiting.

There are 6 free bits in the preempt_count currently, so the preempt count could be expanded to 14 bits, which would be enough for all current systems. Beyond that I guess we could make preempt_count be a long and allow bigger counts on 64-bit architectures.

Or we use the trick Eric suggested and Steve employed in the most recent patch. ;-)

An alternative would be for the update code to acquire but one lock at a time, but this would likely require another lock to exclude other updaters and I believe would also require restructuring the count accumulation.

So Steve's current patch seems a bit less intrusive, overall.

Thanx, Paul

#206 lore raw

Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)

In reply to David Miller
Quoted 5 lines · David Miller

I really think we should entertain the idea where we don't RCU quiesce when adding rules. That was dismissed as not workable because the new rule must be "visible" as soon as we return to userspace but let's get real, effectively it will be.

I never understood that dismissal.

The new rule _will_ be visible as we return to user space. It's just that old packets may still be in flight in other queues.

But that is true even _without_ the "synchronize_net()". The old packets just had to make it slightly further in the queueing - but as far as user space is concerned, there is absolutely _zero_ difference between the two. In both cases it may see packets queued with the old rules.

Quoted 2 lines

I almost cringed when the per-spinlock idea was proposed, but per-cpu rwlocks just takes things too far for my tastes.

I really personally would prefer the RCU approach too. I don't think rwlocks are any more cringe-worthy than spinlocks, although it is true that they tend to be slightly more expensive.

The pure RCU "just get rid of the unnecessary 'serialze_net()'" approach seems to be clearly superior to either.

Linus

#207 lore raw

Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)

In reply to David Miller
Quoted 11 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Wed, 15 Apr 2009 23:07:29 +0200

Quoted 7 lines

Well, it seems original patch was not so bad after all

http://lists.netfilter.org/pipermail/netfilter-devel/2006-January/023175.html

So change per-cpu spinlocks to per-cpu rwlocks

and use read_lock() in ipt_do_table() to allow recursion...

Quoted 7 lines

Grumble, one more barrier to getting rid of rwlocks in the whole tree. :-/

I really think we should entertain the idea where we don't RCU quiesce when adding rules. That was dismissed as not workable because the new rule must be "visible" as soon as we return to userspace but let's get real, effectively it will be.

We had to RCU quiesce to be sure old rules were not any more used before freeing them. Alternative is to defer freeing via call_rcu() but subject to OOM.

With 200 basic rules, size of rules table is about 40960 bytes per cpu. (88 pages taken on vmalloc virtual space on my 8 cpus machine)

0xfcaf8000-0xfcb03000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb04000-0xfcb0f000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb10000-0xfcb1b000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb1c000-0xfcb27000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb28000-0xfcb33000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb34000-0xfcb3f000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb40000-0xfcb4b000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb4c000-0xfcb57000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc

This kind of monolithic huge object is hard to handle with RCU semantic, more suitable for handling set of small objects (struct file for example), even if RCU can have a backoff of 10000 elements in its queue...

Quoted 6 lines

If there are any stale object reference issues, we can use RCU object destruction to handle that kind of thing.

I almost cringed when the per-spinlock idea was proposed, but per-cpu rwlocks just takes things too far for my tastes.

In my humble opinion, this is a reasonnable compromise, and Stephen patch version 4 is ok for me.

#208 lore raw

Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)

Quoted 35 lines · Eric Dumazet
Quoted 11 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Wed, 15 Apr 2009 23:07:29 +0200

Quoted 7 lines

Well, it seems original patch was not so bad after all

http://lists.netfilter.org/pipermail/netfilter-devel/2006-January/023175.html

So change per-cpu spinlocks to per-cpu rwlocks

and use read_lock() in ipt_do_table() to allow recursion...

Quoted 7 lines

Grumble, one more barrier to getting rid of rwlocks in the whole tree. :-/

I really think we should entertain the idea where we don't RCU quiesce when adding rules. That was dismissed as not workable because the new rule must be "visible" as soon as we return to userspace but let's get real, effectively it will be.

We had to RCU quiesce to be sure old rules were not any more used before freeing them. Alternative is to defer freeing via call_rcu() but subject to OOM.

With 200 basic rules, size of rules table is about 40960 bytes per cpu. (88 pages taken on vmalloc virtual space on my 8 cpus machine)

0xfcaf8000-0xfcb03000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb04000-0xfcb0f000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb10000-0xfcb1b000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb1c000-0xfcb27000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb28000-0xfcb33000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb34000-0xfcb3f000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb40000-0xfcb4b000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
0xfcb4c000-0xfcb57000   45056 xt_alloc_table_info+0xa8/0xd0 pages=10 vmalloc
Quoted 3 lines

This kind of monolithic huge object is hard to handle with RCU semantic, more suitable for handling set of small objects (struct file for example), even if RCU can have a backoff of 10000 elements in its queue...

To be honest, the per-CPU-locking approach looks pretty good to me for this particular case. That said, the problem you mention above does have some straightforward solutions.

One solution to consider would be to do the call_rcu(), but to keep a counter of the number of calls, perhaps something like the following:

	call_rcu(...);
	if (++count > 50) {
		synchronize_rcu();
		count = 0;
	}

Of course, you might (or might not) need to atomically increment count, and you of course would want to replace the "50" with some symbolic constant, or perhaps even a variable whose value might be determined by the size of the object and/or the amount of memory available.

Would this help?

Quoted 8 lines
Quoted 5 lines

If there are any stale object reference issues, we can use RCU object destruction to handle that kind of thing.

I almost cringed when the per-spinlock idea was proposed, but per-cpu rwlocks just takes things too far for my tastes.

In my humble opinion, this is a reasonnable compromise, and Stephen patch version 4 is ok for me.

Again, the per-CPU-locking approach looks good to me, as well.

But if it turns out that we really do need an RCU implementation with really short grace periods (tens of microseconds typical latency on mid-range multiprocessors, those with SGI Altix systems would suffer a bit more), then it can be done. It would need to be yet another implementation of RCU for the following reasons:

o High update-side overhead (broadcast IPIs via
smp_call_function(). This is not a problem in this case, but would be a showstopper for (say) dcache. I don't know of any way of fixing this.

o Defeats power-conservation measures by waking up every CPU
at every grace period. (Might be fixable, for example, by using
the same dyntick tricks used by preemptable and hierarchical RCU. But not recommended for first implementation.)

o Poor update-side scalability. (Definitely fixable, but the
fix should be to the underlying smp_call_function() primitives.)

o No ability to share grace periods among concurrent
synchronize_rcu() primitves. (Definitely fixable, but not recommended until needed. Unlikely to be needed -- after all, if your grace period completes in 10 microseconds, just how many concurrent updates do you expect there to be???)

o No call_rcu() style primtive. (Definitely fixable, but not
recommended until needed. Besides, if the grace period only takes a few tens of microseconds, why exactly do you need an asynchronous interface?

If this is needed, one good starting point would be Mathieu Desnoyers's user-level RCU primitive. The main change would be replacing the POSIX signals with smp_call_function().

Yet again, I don't see a real problem with the per-CPU locking approach in this case, but anything to prevent Dave Miller from having to suffer the pain of hashed locks! (Can't say that I have ever used hashed locks myself, but I could imagine that they might impose cache-thrashing and deadlock issues.)

Thanx, Paul

maintainer
#209 lore raw

Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU (v3)

In reply to Stephen Hemminger

From: Stephen Hemminger <[email protected]>
Date: Tue, 14 Apr 2009 14:13:51 -0700

Quoted 9 lines

This is an alternative version of ip/ip6/arp tables locking using per-cpu locks. This avoids the overhead of synchronize_net() during update but still removes the expensive rwlock in earlier versions.

The idea for this came from an earlier version done by Eric Dumazet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. The slow case involves acquiring the locks on all cpu's.

Quoted 4 lines

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

Things seem to be winding down, good. :-)

I'll let Patrick McHardy merge this to me with his other pending netfilter fixes.

Thanks!

#210 lore raw

Re: [PATCH] netfilter: use per-cpu spinlock rather than RCU

In reply to Eric Dumazet
Quoted 51 lines · On Tue, 14 Apr 2009 17:49:57 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 17 lines · Stephen Hemminger
Quoted 14 lines · On Tue, 14 Apr 2009 16:23:33 +0200 Eric Dumazet <[email protected]> wrote:
Quoted 13 lines · Patrick McHardy
Quoted 12 lines · Stephen Hemminger

This is an alternative version of ip/ip6/arp tables locking using per-cpu locks. This avoids the overhead of synchronize_net() during update but still removes the expensive rwlock in earlier versions.

The idea for this came from an earlier version done by Eric Duzamet. Locking is done per-cpu, the fast path locks on the current cpu and updates counters. The slow case involves acquiring the locks on all cpu's.

The mutex that was added for 2.6.30 in xt_table is unnecessary since there already is a mutex for xt[af].mutex that is held.

Quoted 6 lines
Quoted 4 lines
Quoted 3 lines
Quoted 2 lines

Tested basic functionality (add/remove/list), but don't have test cases for stress, ip6tables or arptables.

Thanks Stephen, I'll do some testing with ip6tables.

Here is the patch I cooked on top of Stephen one to get proper locking.

I see no demonstrated problem with locking in my version.

Yes, I did not crash any machine around there, should we wait for a bug report ? :)

Quoted 13 lines

The reader/writer race is already handled. On replace the race of

CPU 0 CPU 1
lock (iptables(1))
refer to oldinfo
swap in new info
foreach CPU
lock iptables(i)
(spin) unlock(iptables(1))
read oldinfo
unlock
...

Quoted 2 lines

The point is my locking works, you just seem to feel more comfortable with a global "stop all CPU's" solution.

Oh right, I missed that xt_replace_table() was *followed* by a get_counters() call, but I am pretty sure something is needed in xt_replace_table().

A memory barrier at least (smp_wmb())

As soon as we do "table->private = newinfo;", other cpus might fetch incorrect values for newinfo->fields.

Quoted 8 lines

In the past, we had a write_lock_bh()/write_unlock_bh() pair that was doing this for us.
Then we had rcu_assign_pointer() that also had this memory barrier implied.

Even if vmalloc() calls we do before calling xt_replace_table() probably already force barriers, add one for reference, just in case we change callers logic to call kmalloc() instead of vmalloc() or whatever...

You are right, doing something with barrier would be safer there. How about using xchg?

@@ -682,26 +668,19 @@ xt_replace_table(struct xt_table *table,
struct xt_table_info *newinfo,
int *error)
{
- struct xt_table_info *oldinfo, *private;
+ struct xt_table_info *private;

/* Do the substitution. */
- mutex_lock(&table->lock);
private = table->private;
/* Check inside lock: is the old number correct? */
if (num_counters != private->number) {
duprintf("num_counters != table->private->number (%u/%u)\n",
num_counters, private->number);
- mutex_unlock(&table->lock);
*error = -EAGAIN;
return NULL;
}
- oldinfo = private;
- rcu_assign_pointer(table->private, newinfo);
- newinfo->initial_entries = oldinfo->initial_entries;
- mutex_unlock(&table->lock);
-
- synchronize_net();
- return oldinfo;
+ newinfo->initial_entries = private->initial_entries;
+ return xchg(&table->private, newinfo);
}
EXPORT_SYMBOL_GPL(xt_replace_table);

P.s: we all missed the ordering bug in the RCU version??

#211 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

In reply to Paul E. McKenney
Quoted 28 lines · On Fri, 10 Apr 2009 21:15:33 -0700 "Paul E. McKenney"…
Quoted 17 lines · Linus Torvalds
Quoted 2 lines · David Miller

[ CC:'ing netfilter-devel and netdev... ]

I wonder if we should bring in the RCU people too, for them to tell you that the networking people are beign silly, and should not synchronize with the very heavy-handed

synchronize_net()

but instead of doing synchronization (which is probably why adding a few hundred rules then takes several seconds - each synchronizes and that takes a timer tick or so), add the rules to be free'd on some rcu-freeing list for later freeing.

Quoted 6 lines

Or whatever. Paul? synchronize_net() just calls synchronize_rcu(), and with that knowledge and a simple

	git show 784544739a25c30637397ace5489eeb6e15d7d49

I bet you can already tell people how to fix their performance issue.

Well, I am certainly happy to demonstrate my ignorance of the networking code by throwing out a few suggestions.

Quoted 6 lines

So, Dave and Steve, you might want to get out your barf bag before reading further. You have been warned! ;-)

1. Assuming that the synchronize_net() is intended to guarantee
that the new rules will be in effect before returning to user space:

In this case it is to make sure that the old counter table is no longer being used by other cpu's receiving.

Quoted 17 lines

a. Split this functionality, so that there is a new
user-space primitive that installs a new rule, but without waiting. They provide an additional user-space primitive that waits for the rules to take effect. Then, when loading a long list of rules, load them using the non-waiting primitive, and wait at the end.

b. As above, but provide a flag that says whether or not
to wait. Same general effect.

But I am not seeing the direct connection between this patch and netfilter, so...

2. For the xt_replace_table() case, it would be necessary to add an
rcu_head to the xt_table_info, and replace each caller's direct calls to xt_free_table_info() with call_rcu().

Quoted 8 lines

Now this has an issue in that the caller wants to return the final counter values. My assumption is that these values do not in fact need to be exact. If I am wrong about that, then my suggestion would lose the counts from late readers. I must defer to the networking guys as to whether this is acceptable or not. If not, more head-scratching would be required. (But it looks to me that the rule is being trashed, so who cares about the extra counts?)

The problem is that users want to account for every byte.

Quoted 4 lines

In addition, a malicious user might be able to force this to happen extremely frequently, running the system out of memory. One way to fix this is to invoke synchronize_net() one out of 20 times or some such.

Malicious user == root, therefore don't care.

Quoted 5 lines

3. For the alloc_counters() case, the comments indicate that we
really truly do want an atomic sampling of the counters. The counters are 64-bit entities, which is a bit inconvenient. Though people using this functionality are no doubt quite happy to never have to worry about overflow, I hasten to add!

And we need snapshot of all counters (which are not even an array but a skip list).

Quoted 90 lines

I will nevertheless suggest the following egregious hack to get a consistent sample of one counter for some other CPU:

a. Disable interrupts
b. Atomically exchange the bottom 32 bits of the
counter with the value zero.
c. Atomically exchange the top 32 bits of the counter
with the value zero.
d. Concatenate the values obtained in (b) and (c), which
is the snapshot value.
e. Re-enable interrupts. Yes, for each counter. Do it
for the honor of the -rt patchset. ;-)

Disabling interrupts should make it impossible for the low-order 32 bits of the counter to overflow before we get around to zeroing the upper 32 bits. Yes, this is horribly paranoid, but please keep in mind that even my level of paranoia is not always sufficient to keep RCU working correctly. :-/

Architectures with 64-bit atomics can simply do a 64-bit exchange (or cmpxchg(), for that matter).

Now we still have the possibility that the other CPU is still hammering away on the counter that we just zeroed from a long-running RCU read-side critical section.

So, we also need to add an rcu_head somewhere, perhaps reuse the one in xt_table_info, create a second one, or squirrel one away somewhere else. As long as there is a way to get to the old counter values. And a flag to indicate that the rcu_head is in use. It is socially irresponsible to pass a given rcu_head to call_rcu() before it has been invoked after the previous time it was passed to call_rcu(). But you guys all knew that already.

We replace the synchronize_net() with call_rcu(), more or less. The call_rcu() probably needs to be under the lock -- or at the very least, setting the flag saying that it is in use needs to be under the lock.

The RCU callback function traverses the old counters one last time, adding their values to the new set of counters. No atomic exchange tricks are required this time, since all the RCU readers that could possibly have held a reference to the old set of counters must now be done. We now clear the flag, allowing the next counter snapshot to proceed.

OK, OK, Dave and Steve, I should have suggested that you get two barf bags. Maybe three. ;-)

Additional caveat: coward that I am, I looked only at the IPv4 code. There might well be additional complications in the arp and IPv6 code.

However, I do believe that something like this might actually work.

Thoughts?

Thanx, Paul

Quoted 30 lines

Linus

---

Quoted 13 lines
Quoted 13 lines
Quoted 10 lines · On Fri, 10 Apr 2009 17:15:52 +0800 (SGT) Jeff Chua <[email protected]>…

Adding 200 records in iptables took 6.0sec in 2.6.30-rc1 compared to 0.2sec in 2.6.29. I've bisected down this commit.

There are a few patches on top of the original patch. When I reverted the original commit + changing rcu_read() to rcu_read_bh(), it speeds up the inserts back to .2sec again.

I'm loading all the firewall rules during boot-up and this 6 secs slowness is really not very nice to wait for.

Quoted 10 lines
Quoted 9 lines

The performance benefit during operation is more important. The load time is fixable. The problem is probably generic to any set of rules, but could you post some info about your configuration (like the rule set), and the system configuration (# of cpu's, config etc). --
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

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

#212 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

Quoted 67 lines · Stephen Hemminger
Quoted 28 lines · On Fri, 10 Apr 2009 21:15:33 -0700 "Paul E. McKenney"…
Quoted 17 lines · Linus Torvalds
Quoted 2 lines · David Miller

[ CC:'ing netfilter-devel and netdev... ]

I wonder if we should bring in the RCU people too, for them to tell you that the networking people are beign silly, and should not synchronize with the very heavy-handed

synchronize_net()

but instead of doing synchronization (which is probably why adding a few hundred rules then takes several seconds - each synchronizes and that takes a timer tick or so), add the rules to be free'd on some rcu-freeing list for later freeing.

Quoted 6 lines

Or whatever. Paul? synchronize_net() just calls synchronize_rcu(), and with that knowledge and a simple

	git show 784544739a25c30637397ace5489eeb6e15d7d49

I bet you can already tell people how to fix their performance issue.

Well, I am certainly happy to demonstrate my ignorance of the networking code by throwing out a few suggestions.

Quoted 6 lines

So, Dave and Steve, you might want to get out your barf bag before reading further. You have been warned! ;-)

1. Assuming that the synchronize_net() is intended to guarantee
that the new rules will be in effect before returning to user space:

In this case it is to make sure that the old counter table is no longer being used by other cpu's receiving.

Quoted 17 lines

a. Split this functionality, so that there is a new
user-space primitive that installs a new rule, but without waiting. They provide an additional user-space primitive that waits for the rules to take effect. Then, when loading a long list of rules, load them using the non-waiting primitive, and wait at the end.

b. As above, but provide a flag that says whether or not
to wait. Same general effect.

But I am not seeing the direct connection between this patch and netfilter, so...

2. For the xt_replace_table() case, it would be necessary to add an
rcu_head to the xt_table_info, and replace each caller's direct calls to xt_free_table_info() with call_rcu().

Quoted 8 lines

Now this has an issue in that the caller wants to return the final counter values. My assumption is that these values do not in fact need to be exact. If I am wrong about that, then my suggestion would lose the counts from late readers. I must defer to the networking guys as to whether this is acceptable or not. If not, more head-scratching would be required. (But it looks to me that the rule is being trashed, so who cares about the extra counts?)

Quoted 1 line

The problem is that users want to account for every byte.

Ah!!!

Is this particular code path one of the ones responsible for the slowdown?

Quoted 6 lines
Quoted 4 lines

In addition, a malicious user might be able to force this to happen extremely frequently, running the system out of memory. One way to fix this is to invoke synchronize_net() one out of 20 times or some such.

Malicious user == root, therefore don't care.

Sometimes things work out OK. ;-)

Quoted 8 lines
Quoted 5 lines

3. For the alloc_counters() case, the comments indicate that we
really truly do want an atomic sampling of the counters. The counters are 64-bit entities, which is a bit inconvenient. Though people using this functionality are no doubt quite happy to never have to worry about overflow, I hasten to add!

And we need snapshot of all counters (which are not even an array but a skip list).

OK. However, the code seems to swap in a new set of counters intended to account for subsequent packets. So I was assuming that "snapshot" meant that a given packet had to be accounted for precisely, but that it was OK to do so either in the old set or the new set, as long as it appeared in exactly one of the two sets.

If this assumption is accurate, then something like the following should work.

If my assumption is wrong, what exactly does this snapshot need to do?

Thanx, Paul

Quoted 90 lines
Quoted 90 lines

I will nevertheless suggest the following egregious hack to get a consistent sample of one counter for some other CPU:

a. Disable interrupts
b. Atomically exchange the bottom 32 bits of the
counter with the value zero.
c. Atomically exchange the top 32 bits of the counter
with the value zero.
d. Concatenate the values obtained in (b) and (c), which
is the snapshot value.
e. Re-enable interrupts. Yes, for each counter. Do it
for the honor of the -rt patchset. ;-)

Disabling interrupts should make it impossible for the low-order 32 bits of the counter to overflow before we get around to zeroing the upper 32 bits. Yes, this is horribly paranoid, but please keep in mind that even my level of paranoia is not always sufficient to keep RCU working correctly. :-/

Architectures with 64-bit atomics can simply do a 64-bit exchange (or cmpxchg(), for that matter).

Now we still have the possibility that the other CPU is still hammering away on the counter that we just zeroed from a long-running RCU read-side critical section.

So, we also need to add an rcu_head somewhere, perhaps reuse the one in xt_table_info, create a second one, or squirrel one away somewhere else. As long as there is a way to get to the old counter values. And a flag to indicate that the rcu_head is in use. It is socially irresponsible to pass a given rcu_head to call_rcu() before it has been invoked after the previous time it was passed to call_rcu(). But you guys all knew that already.

We replace the synchronize_net() with call_rcu(), more or less. The call_rcu() probably needs to be under the lock -- or at the very least, setting the flag saying that it is in use needs to be under the lock.

The RCU callback function traverses the old counters one last time, adding their values to the new set of counters. No atomic exchange tricks are required this time, since all the RCU readers that could possibly have held a reference to the old set of counters must now be done. We now clear the flag, allowing the next counter snapshot to proceed.

OK, OK, Dave and Steve, I should have suggested that you get two barf bags. Maybe three. ;-)

Additional caveat: coward that I am, I looked only at the IPv4 code. There might well be additional complications in the arp and IPv6 code.

However, I do believe that something like this might actually work.

Thoughts?

Thanx, Paul

Quoted 30 lines

Linus

---

Quoted 13 lines
Quoted 13 lines
Quoted 10 lines · On Fri, 10 Apr 2009 17:15:52 +0800 (SGT) Jeff Chua <[email protected]>…

Adding 200 records in iptables took 6.0sec in 2.6.30-rc1 compared to 0.2sec in 2.6.29. I've bisected down this commit.

There are a few patches on top of the original patch. When I reverted the original commit + changing rcu_read() to rcu_read_bh(), it speeds up the inserts back to .2sec again.

I'm loading all the firewall rules during boot-up and this 6 secs slowness is really not very nice to wait for.

Quoted 10 lines
Quoted 9 lines

The performance benefit during operation is more important. The load time is fixable. The problem is probably generic to any set of rules, but could you post some info about your configuration (like the rule set), and the system configuration (# of cpu's, config etc). --
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

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

#213 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

In reply to Paul E. McKenney
Quoted 4 lines · Paul E. McKenney

1. Assuming that the synchronize_net() is intended to guarantee
that the new rules will be in effect before returning to user space:

Btw, I think that's a bad assumption.

The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.

And those incoming packets might have been incoming before the rules were set up too.

So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!

So I would suggest:

- remove the synchronize_net() entirely. Replace it with just freeing the old rules using RCU.

- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.

- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "synchronize_net()" in no way protects against any race conditions anyway.

Am I missing something?

Linus

#214 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney

1. Assuming that the synchronize_net() is intended to guarantee
that the new rules will be in effect before returning to user space:

Btw, I think that's a bad assumption.

It does indeed appear to be!

Quoted 20 lines

The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.

And those incoming packets might have been incoming before the rules were set up too.

So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!

So I would suggest:

- remove the synchronize_net() entirely. Replace it with just freeing the old rules using RCU.

- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.

Quoted 6 lines

- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "synchronize_net()" in no way protects against any race conditions anyway.

Am I missing something?

The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However, it is also necessary to update these counters very efficiently, given that they are updated on a per-packet basis. The current approach is as follows:

1. Install a new set of counters.

2. Wait for a grace period to elapse.

3. At this point, we know that all subsequent counting will happen
on the new set of counters.

4. Add the value of the old set of counters to the new set of
counters.

5. Copy the old set of counters up to user space.

So we get a good snapshot in #5, while #4 ensures that we don't lose any counts when taking future snapshots. Unfortunately, #2 hits us with grace-period latencies on the critical path.

We are going through the following possibilities:

o Stick with the current approach, and ask people to move to

	new batch-oriented interfaces.  However, a 30x decrease in
	performance is pretty grim, even for an old-style interface.

o Use various atomic tricks to get an immediate snapshot of the
old counters after step 1. Make step 3 use call_rcu() instead of synchronize_rcu(), and then step 4 happens off the critical path.

This approach moves the RCU grace period off of the critical path, but the atomic tricks are extremely ugly on 32-bit SMP machines. 32-bit UP machines and 64-bit machines are not too bad, though the 32-bit UP case does add preemption-disable overhead on the counter-update fastpath.

o Provide some sort of expedited synchronize_rcu(). This might
be able to decrease the hit from 30x down to maybe 5x. But I might need to do this for the fast-boot folks anyway, though I am first trying to get away with just speeding up synchronized_rcu(). Though I was not thinking in terms of 6x, let alone 30x.

Please note that this would not be a drop-in replacement for synchronize_rcu(). One would use synchronize_rcu_expedited() (or whatever) only when the system really could not get any useful work done while the grace period was in progress. The general approach would be to keep the whole machine busy trying to get the grace period done as soon as possible.

Thanx, Paul

#215 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

Hi.

Quoted 3 lines · Paul E. McKenney

The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However,

If we add or change the rule we can not know if iptables' return to userspace does mean that rule started to act. There may be other queues already filled with the packets which could match the new rule (like receiving socket buffer). So effectively we want it to take effect very soon. What if there will be a timer which will synchronize RCU-added states, so if we update single rule - it will take effect in a second, and if we update bunch of them - during the delay second we pretty much can load them all.

Signature · 1 line
	Evgeniy Polyakov
#216 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

In reply to Paul E. McKenney
Quoted 87 lines · On Sat, 11 Apr 2009 17:34:45 -0700 "Paul E. McKenney"…
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney

1. Assuming that the synchronize_net() is intended to guarantee
that the new rules will be in effect before returning to user space:

Btw, I think that's a bad assumption.

It does indeed appear to be!

Quoted 20 lines

The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.

And those incoming packets might have been incoming before the rules were set up too.

So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!

So I would suggest:

- remove the synchronize_net() entirely. Replace it with just freeing the old rules using RCU.

- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.

Quoted 6 lines

- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "synchronize_net()" in no way protects against any race conditions anyway.

Am I missing something?

The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However, it is also necessary to update these counters very efficiently, given that they are updated on a per-packet basis. The current approach is as follows:

1. Install a new set of counters.

2. Wait for a grace period to elapse.

3. At this point, we know that all subsequent counting will happen
on the new set of counters.

4. Add the value of the old set of counters to the new set of
counters.

5. Copy the old set of counters up to user space.

So we get a good snapshot in #5, while #4 ensures that we don't lose any counts when taking future snapshots. Unfortunately, #2 hits us with grace-period latencies on the critical path.

We are going through the following possibilities:

o Stick with the current approach, and ask people to move to

	new batch-oriented interfaces.  However, a 30x decrease in
	performance is pretty grim, even for an old-style interface.

o Use various atomic tricks to get an immediate snapshot of the
old counters after step 1. Make step 3 use call_rcu() instead of synchronize_rcu(), and then step 4 happens off the critical path.

This approach moves the RCU grace period off of the critical path, but the atomic tricks are extremely ugly on 32-bit SMP machines. 32-bit UP machines and 64-bit machines are not too bad, though the 32-bit UP case does add preemption-disable overhead on the counter-update fastpath.

o Provide some sort of expedited synchronize_rcu(). This might
be able to decrease the hit from 30x down to maybe 5x. But I might need to do this for the fast-boot folks anyway, though I am first trying to get away with just speeding up synchronized_rcu(). Though I was not thinking in terms of 6x, let alone 30x.

Quoted 8 lines

Please note that this would not be a drop-in replacement for synchronize_rcu(). One would use synchronize_rcu_expedited() (or whatever) only when the system really could not get any useful work done while the grace period was in progress. The general approach would be to keep the whole machine busy trying to get the grace period done as soon as possible.

Thanx, Paul

We could also try:
* per-cpu spinlock on counters (instead of synchronize_net). When doing update, just acquire
lock on that cpu and futz with counters then. Overhead should still be less than 2.6.29 and earlier global rwlock

* synchonize_rcu/synchronize_net is more guarantee than needed?

* use on_each_cpu() somehow to do grace periood?

* Add a cond_resched() into net_rx_action which might cause rx processing to get out of rcu sooner? also in transmit packet scheduler.

#217 lore raw

Re: iptables very slow after commit 784544739a25c30637397ace5489eeb6e15d7d49

Quoted 97 lines · Stephen Hemminger
Quoted 94 lines · On Sat, 11 Apr 2009 17:34:45 -0700 "Paul E. McKenney"…
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney

1. Assuming that the synchronize_net() is intended to guarantee
that the new rules will be in effect before returning to user space:

Btw, I think that's a bad assumption.

It does indeed appear to be!

Quoted 20 lines

The thing is, nobody can really care if the new rules are in effect or not, because the thing you race with is not the "return to user space" part, but the incoming packets.

And those incoming packets might have been incoming before the rules were set up too.

So I seriously doubt you need to synchronize with any returning to user space. What you want to synchronize with is then later actions that do things like turning on the interface that the rules are attached to etc!

So I would suggest:

- remove the synchronize_net() entirely. Replace it with just freeing the old rules using RCU.

- new packets will always end up seeing the new rules. That includes the case of somebody doing "ifconfig eth0 up" that enables a new source of packets, so there are no real security issues.

Quoted 6 lines

- if you enabled your network interfaces before you updated your packet filtering rules, you already had a window where packets would come in with the old rules, so doing a "synchronize_net()" in no way protects against any race conditions anyway.

Am I missing something?

The issue at this point seems to be the need to get accurate snapshots of various counters -- there are a number of Linux networking users who need to account for every byte flowing through their systems. However, it is also necessary to update these counters very efficiently, given that they are updated on a per-packet basis. The current approach is as follows:

1. Install a new set of counters.

2. Wait for a grace period to elapse.

3. At this point, we know that all subsequent counting will happen
on the new set of counters.

4. Add the value of the old set of counters to the new set of
counters.

5. Copy the old set of counters up to user space.

So we get a good snapshot in #5, while #4 ensures that we don't lose any counts when taking future snapshots. Unfortunately, #2 hits us with grace-period latencies on the critical path.

We are going through the following possibilities:

o Stick with the current approach, and ask people to move to

	new batch-oriented interfaces.  However, a 30x decrease in
	performance is pretty grim, even for an old-style interface.

o Use various atomic tricks to get an immediate snapshot of the
old counters after step 1. Make step 3 use call_rcu() instead of synchronize_rcu(), and then step 4 happens off the critical path.

This approach moves the RCU grace period off of the critical path, but the atomic tricks are extremely ugly on 32-bit SMP machines. 32-bit UP machines and 64-bit machines are not too bad, though the 32-bit UP case does add preemption-disable overhead on the counter-update fastpath.

o Provide some sort of expedited synchronize_rcu(). This might
be able to decrease the hit from 30x down to maybe 5x. But I might need to do this for the fast-boot folks anyway, though I am first trying to get away with just speeding up synchronized_rcu(). Though I was not thinking in terms of 6x, let alone 30x.

Please note that this would not be a drop-in replacement for synchronize_rcu(). One would use synchronize_rcu_expedited() (or whatever) only when the system really could not get any useful work done while the grace period was in progress. The general approach would be to keep the whole machine busy trying to get the grace period done as soon as possible.

Quoted 7 lines
Quoted 1 line

Thanx, Paul

We could also try:
* per-cpu spinlock on counters (instead of synchronize_net). When doing update, just acquire
lock on that cpu and futz with counters then. Overhead should still be less than 2.6.29 and earlier global rwlock

This one makes a lot of sense to me. The overhead of an uncontended lock is pretty small on most systems. This would also mean that you don't have to actually swap the counters, correct?

Quoted 1 line

* synchonize_rcu/synchronize_net is more guarantee than needed?

If you really do need to swap the counters themselves, you -might- also need call_rcu() to dispose of them. But it should possible to do that under the per-CPU lock instead.

Quoted 1 line

* use on_each_cpu() somehow to do grace periood?

You could certainly use something like smp_call_function() to collect the other CPUs' counter values -- just disable interrupts across the increments for architectures that cannot atomically increment a 64-bit value. (And it only needs to be atomic with respect to an interrupt, not necessarily to some other CPU.)

Quoted 2 lines

* Add a cond_resched() into net_rx_action which might cause rx processing to get out of rcu sooner? also in transmit packet scheduler.

This might help some, but would probably only give a few tens of percent improvement.

Thanx, Paul