Is module refcounting racy?

Is module refcounting racy?

[Nick Piggin]

Hey,

I've been looking at weird and wonderful ways to do scalable refcounting,
for the vfs...

Sadly, module refcounting doesn't fit my bill. But as far as I could see,
it is racy. Can someone confirm that we do or do not have a race (and
if so, whether this patch would solve it?)

Race described in the comment below.

Thanks,
Nick

Index: linux-2.6/include/linux/module.h
===================================================================
--- linux-2.6.orig/include/linux/module.h
+++ linux-2.6/include/linux/module.h
@@ -365,7 +365,8 @@ struct module
 	void (*exit)(void);
 
 	struct module_ref {
-		int count;
+		unsigned int incs;
+		unsigned int decs;
 	} __percpu *refptr;
 #endif
 
@@ -459,9 +460,9 @@ static inline void __module_get(struct m
 {
 	if (module) {
 		preempt_disable();
-		__this_cpu_inc(module->refptr->count);
+		__this_cpu_inc(module->refptr->incs);
 		trace_module_get(module, _THIS_IP_,
-				 __this_cpu_read(module->refptr->count));
+				 __this_cpu_read(module->refptr->incs));
 		preempt_enable();
 	}
 }
@@ -474,11 +475,10 @@ static inline int try_module_get(struct
 		preempt_disable();
 
 		if (likely(module_is_live(module))) {
-			__this_cpu_inc(module->refptr->count);
+			__this_cpu_inc(module->refptr->incs);
 			trace_module_get(module, _THIS_IP_,
-				__this_cpu_read(module->refptr->count));
-		}
-		else
+				__this_cpu_read(module->refptr->incs));
+		} else
 			ret = 0;
 
 		preempt_enable();
Index: linux-2.6/kernel/module.c
===================================================================
--- linux-2.6.orig/kernel/module.c
+++ linux-2.6/kernel/module.c
@@ -473,11 +473,13 @@ static void module_unload_init(struct mo
 	int cpu;
 
 	INIT_LIST_HEAD(&mod->modules_which_use_me);
-	for_each_possible_cpu(cpu)
-		per_cpu_ptr(mod->refptr, cpu)->count = 0;
+	for_each_possible_cpu(cpu) {
+		per_cpu_ptr(mod->refptr, cpu)->incs = 0;
+		per_cpu_ptr(mod->refptr, cpu)->decs = 0;
+	}
 
 	/* Hold reference count during initialization. */
-	__this_cpu_write(mod->refptr->count, 1);
+	__this_cpu_write(mod->refptr->incs, 1);
 	/* Backwards compatibility macros put refcount during init. */
 	mod->waiter = current;
 }
@@ -616,12 +618,28 @@ static int try_stop_module(struct module
 
 unsigned int module_refcount(struct module *mod)
 {
-	unsigned int total = 0;
+	unsigned int incs = 0, decs = 0;
 	int cpu;
 
 	for_each_possible_cpu(cpu)
-		total += per_cpu_ptr(mod->refptr, cpu)->count;
-	return total;
+		decs += per_cpu_ptr(mod->refptr, cpu)->decs;
+	/*
+	 * ensure the incs are added up after the decs.
+	 * module_put ensures incs are visible before decs with smp_wmb.
+	 *
+	 * This 2-count scheme avoids the situation where the refcount
+	 * for CPU0 is read, then CPU0 increments the module refcount,
+	 * then CPU1 drops that refcount, then the refcount for CPU1 is
+	 * read. We would record a decrement but not its corresponding
+	 * increment so we would see a low count (disaster).
+	 *
+	 * Rare situation? But module_refcount can be preempted, and we
+	 * might be tallying up 4096+ CPUs. So it is not impossible.
+	 */
+	smp_rmb();
+	for_each_possible_cpu(cpu)
+		incs += per_cpu_ptr(mod->refptr, cpu)->incs;
+	return incs - decs;
 }
 EXPORT_SYMBOL(module_refcount);
 
@@ -798,10 +816,11 @@ void module_put(struct module *module)
 {
 	if (module) {
 		preempt_disable();
-		__this_cpu_dec(module->refptr->count);
+		smp_wmb(); /* see comment in module_refcount */
+		__this_cpu_inc(module->refptr->decs);
 
 		trace_module_put(module, _RET_IP_,
-				 __this_cpu_read(module->refptr->count));
+				 __this_cpu_read(module->refptr->decs));
 		/* Maybe they're waiting for us to drop reference? */
 		if (unlikely(!module_is_live(module)))
 			wake_up_process(module->waiter);

Re: Is module refcounting racy?

[Rusty Russell]

On Thu, 18 Mar 2010 09:25:34 pm Nick Piggin wrote:
> Hey,
> 
> I've been looking at weird and wonderful ways to do scalable refcounting,
> for the vfs...
> 
> Sadly, module refcounting doesn't fit my bill. But as far as I could see,
> it is racy.

Other than for advisory purposes, the refcount is only checked against zero
under stop_machine.  For exactly this reason.

Hope that helps,
Rusty.

Re: Is module refcounting racy?

[Nick Piggin]

On Mon, Mar 29, 2010 at 8:12 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> On Thu, 18 Mar 2010 09:25:34 pm Nick Piggin wrote:
>> Hey,
>>
>> I've been looking at weird and wonderful ways to do scalable refcounting,
>> for the vfs...
>>
>> Sadly, module refcounting doesn't fit my bill. But as far as I could see,
>> it is racy.
>
> Other than for advisory purposes, the refcount is only checked against zero
> under stop_machine.  For exactly this reason.

There definitely looks to me like there is code that checks the refcount
*without* stop_machine. module_refcount is an exported function, and you
expect drivers to get this right (scsi_device_put for a trivial example), but
it even looks like it is used in a racy way in kernel/module.c code.

Either we need to take my patch, or audit t, and put a WARN_ON
if it is called while not under stop_machine.

Re: Is module refcounting racy?

[Rusty Russell]

On Tue, 30 Mar 2010 03:28:49 am Nick Piggin wrote:
> On Mon, Mar 29, 2010 at 8:12 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> > On Thu, 18 Mar 2010 09:25:34 pm Nick Piggin wrote:
> >> Hey,
> >>
> >> I've been looking at weird and wonderful ways to do scalable refcounting,
> >> for the vfs...
> >>
> >> Sadly, module refcounting doesn't fit my bill. But as far as I could see,
> >> it is racy.
> >
> > Other than for advisory purposes, the refcount is only checked against zero
> > under stop_machine.  For exactly this reason.
> 
> There definitely looks to me like there is code that checks the refcount
> *without* stop_machine. module_refcount is an exported function, and you
> expect drivers to get this right (scsi_device_put for a trivial example)

No, but there's a lot of history of crap drivers which wanted to poke at it.
And it's cute for debugging.

The scsi code is simply wrong.  But noone cares, since module removal is
so rare.

> , but
> it even looks like it is used in a racy way in kernel/module.c code.

Yep, though I don't know if anyone uses waiting module removal AFAICT
though; there's not even a modprobe option for it.

> Either we need to take my patch, or audit t, and put a WARN_ON
> if it is called while not under stop_machine.

So can you send me a proper annotated signed-off patch to queue?

Note that years ago it was decided that module reference counting would be
best effort, rather than perfect.  I disagreed, but we've lived with it
surprisingly well.

I wonder if by caring even *less*, we can lose a lot of complexity without
noticeably increasing the bug count.  Make modules run their own reference
counts and just sleep for a while to see if the reference count changes.
If not, assume it's good to be removed.  If reference count still hasn't
moved after another minute or so, actually free the memory.

Thanks,
Rusty.

Re: Is module refcounting racy?

[Nick Piggin]

On Wed, Mar 31, 2010 at 02:14:49PM +1030, Rusty Russell wrote:
> On Tue, 30 Mar 2010 03:28:49 am Nick Piggin wrote:
> > On Mon, Mar 29, 2010 at 8:12 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> > > On Thu, 18 Mar 2010 09:25:34 pm Nick Piggin wrote:
> > >> Hey,
> > >>
> > >> I've been looking at weird and wonderful ways to do scalable refcounting,
> > >> for the vfs...
> > >>
> > >> Sadly, module refcounting doesn't fit my bill. But as far as I could see,
> > >> it is racy.
> > >
> > > Other than for advisory purposes, the refcount is only checked against zero
> > > under stop_machine.  For exactly this reason.
> > 
> > There definitely looks to me like there is code that checks the refcount
> > *without* stop_machine. module_refcount is an exported function, and you
> > expect drivers to get this right (scsi_device_put for a trivial example)
> 
> No, but there's a lot of history of crap drivers which wanted to poke at it.
> And it's cute for debugging.
> 
> The scsi code is simply wrong.  But noone cares, since module removal is
> so rare.

Well maybe true (and I'm sure we have more important and frequently hit
bugs), but if we offer a feature it should be without bugs IMO.


> > , but
> > it even looks like it is used in a racy way in kernel/module.c code.
> 
> Yep, though I don't know if anyone uses waiting module removal AFAICT
> though; there's not even a modprobe option for it.
> 
> > Either we need to take my patch, or audit t, and put a WARN_ON
> > if it is called while not under stop_machine.
> 
> So can you send me a proper annotated signed-off patch to queue?

Sure.


> Note that years ago it was decided that module reference counting would be
> best effort, rather than perfect.  I disagreed, but we've lived with it
> surprisingly well.
> 
> I wonder if by caring even *less*, we can lose a lot of complexity without
> noticeably increasing the bug count.  Make modules run their own reference
> counts and just sleep for a while to see if the reference count changes.
> If not, assume it's good to be removed.  If reference count still hasn't
> moved after another minute or so, actually free the memory.

I think it can be done racelessly with my patch, which is not really too
much overhead. I think if this is considered too much, then we should
either fix code and preferably de-export and remove module_refcount from
drivers, or remove module removal completely.

--
Module refcounting is implemented with a per-cpu counter for speed. However
there is a race when tallying the counter where a reference may be taken
by one CPU and released by another. Reference count summation may then see
the decrement without having seen the previous increment, leading to lower
than expected count. A module which never has its actual reference drop below
1 may return a reference count of 0 due to this race.

Module removal generally runs under stop_machine, which prevents this race
causing bugs due to removal of in-use modules. However there are other real
bugs in module.c code and driver code (module_refcount is exported) where the
callers do not run under stop_machine.

Fix this by maintaining running per-cpu counters for the number of module
refcount increments and the number of refcount decrements. The increments
are tallied after the decrements, so any decrement seen will always have its
corresponding increment counted. The final refcount is the difference of the
total increments and decrements, preventing a low-refcount from being
returned.

Signed-off-by: Nick Piggin <npiggin@suse.de>
---
Index: linux-2.6/include/linux/module.h
===================================================================
--- linux-2.6.orig/include/linux/module.h
+++ linux-2.6/include/linux/module.h
@@ -365,7 +365,8 @@ struct module
 	void (*exit)(void);
 
 	struct module_ref {
-		int count;
+		unsigned int incs;
+		unsigned int decs;
 	} __percpu *refptr;
 #endif
 
@@ -459,9 +460,9 @@ static inline void __module_get(struct m
 {
 	if (module) {
 		preempt_disable();
-		__this_cpu_inc(module->refptr->count);
+		__this_cpu_inc(module->refptr->incs);
 		trace_module_get(module, _THIS_IP_,
-				 __this_cpu_read(module->refptr->count));
+				 __this_cpu_read(module->refptr->incs));
 		preempt_enable();
 	}
 }
@@ -474,11 +475,10 @@ static inline int try_module_get(struct
 		preempt_disable();
 
 		if (likely(module_is_live(module))) {
-			__this_cpu_inc(module->refptr->count);
+			__this_cpu_inc(module->refptr->incs);
 			trace_module_get(module, _THIS_IP_,
-				__this_cpu_read(module->refptr->count));
-		}
-		else
+				__this_cpu_read(module->refptr->incs));
+		} else
 			ret = 0;
 
 		preempt_enable();
Index: linux-2.6/kernel/module.c
===================================================================
--- linux-2.6.orig/kernel/module.c
+++ linux-2.6/kernel/module.c
@@ -473,11 +473,13 @@ static void module_unload_init(struct mo
 	int cpu;
 
 	INIT_LIST_HEAD(&mod->modules_which_use_me);
-	for_each_possible_cpu(cpu)
-		per_cpu_ptr(mod->refptr, cpu)->count = 0;
+	for_each_possible_cpu(cpu) {
+		per_cpu_ptr(mod->refptr, cpu)->incs = 0;
+		per_cpu_ptr(mod->refptr, cpu)->decs = 0;
+	}
 
 	/* Hold reference count during initialization. */
-	__this_cpu_write(mod->refptr->count, 1);
+	__this_cpu_write(mod->refptr->incs, 1);
 	/* Backwards compatibility macros put refcount during init. */
 	mod->waiter = current;
 }
@@ -616,12 +618,28 @@ static int try_stop_module(struct module
 
 unsigned int module_refcount(struct module *mod)
 {
-	unsigned int total = 0;
+	unsigned int incs = 0, decs = 0;
 	int cpu;
 
 	for_each_possible_cpu(cpu)
-		total += per_cpu_ptr(mod->refptr, cpu)->count;
-	return total;
+		decs += per_cpu_ptr(mod->refptr, cpu)->decs;
+	/*
+	 * ensure the incs are added up after the decs.
+	 * module_put ensures incs are visible before decs with smp_wmb.
+	 *
+	 * This 2-count scheme avoids the situation where the refcount
+	 * for CPU0 is read, then CPU0 increments the module refcount,
+	 * then CPU1 drops that refcount, then the refcount for CPU1 is
+	 * read. We would record a decrement but not its corresponding
+	 * increment so we would see a low count (disaster).
+	 *
+	 * Rare situation? But module_refcount can be preempted, and we
+	 * might be tallying up 4096+ CPUs. So it is not impossible.
+	 */
+	smp_rmb();
+	for_each_possible_cpu(cpu)
+		incs += per_cpu_ptr(mod->refptr, cpu)->incs;
+	return incs - decs;
 }
 EXPORT_SYMBOL(module_refcount);
 
@@ -798,10 +816,11 @@ void module_put(struct module *module)
 {
 	if (module) {
 		preempt_disable();
-		__this_cpu_dec(module->refptr->count);
+		smp_wmb(); /* see comment in module_refcount */
+		__this_cpu_inc(module->refptr->decs);
 
 		trace_module_put(module, _RET_IP_,
-				 __this_cpu_read(module->refptr->count));
+				 __this_cpu_read(module->refptr->decs));
 		/* Maybe they're waiting for us to drop reference? */
 		if (unlikely(!module_is_live(module)))
 			wake_up_process(module->waiter);

Re: Is module refcounting racy?

[Linus Torvalds]

On Thu, 1 Apr 2010, Nick Piggin wrote:
> 
> I think it can be done racelessly with my patch, which is not really too
> much overhead. I think if this is considered too much, then we should
> either fix code and preferably de-export and remove module_refcount from
> drivers, or remove module removal completely.

I doubt your patch matters too much, but I like it conceptually and it 
seems to be a nice basis for perhaps doing something clever in the long 
run.

[ ie avoiding the stop_machine and instead perhaps doing some optimistic 
  thing like "see if we seem to be unused right now, then unregister us, 
  and see - after unregistering - that the usage counts haven't increased, 
  and re-register if they have. ]

So I'd like to apply it as a "good improvement, even if module unloading 
which is the only thing that _should_ care deeply should already be under 
stop-machine".

But I'd like an ack or two first.

		Linus

Re: Is module refcounting racy?

[Rusty Russell]

On Fri, 2 Apr 2010 02:25:59 am Linus Torvalds wrote:
> 
> On Thu, 1 Apr 2010, Nick Piggin wrote:
> > 
> > I think it can be done racelessly with my patch, which is not really too
> > much overhead. I think if this is considered too much, then we should
> > either fix code and preferably de-export and remove module_refcount from
> > drivers, or remove module removal completely.
> 
> I doubt your patch matters too much, but I like it conceptually and it 
> seems to be a nice basis for perhaps doing something clever in the long 
> run.
> 
> [ ie avoiding the stop_machine and instead perhaps doing some optimistic 
>   thing like "see if we seem to be unused right now, then unregister us, 
>   and see - after unregistering - that the usage counts haven't increased, 
>   and re-register if they have. ]

I dislike that we can see spurious failure for some random try_module_get
caller.

But perhaps that's inherent in module removal: someone can miss out, and if
you care, don't try to remove modules.

And grepping for try_module_get() reveals a suspicious (growing) number of
try_module_get(THIS_MODULE) which is almost always wrong.  If we're not
perfect, maybe we should aim for simple?

> So I'd like to apply it as a "good improvement, even if module unloading 
> which is the only thing that _should_ care deeply should already be under 
> stop-machine".
> 
> But I'd like an ack or two first.

Yep.

Acked-by: Rusty Russell <rusty@rustcorp.com.au>

Cheers,
Rusty.

Re: Is module refcounting racy?

[Nick Piggin]

On Thu, Apr 01, 2010 at 08:55:59AM -0700, Linus Torvalds wrote:
> 
> 
> On Thu, 1 Apr 2010, Nick Piggin wrote:
> > 
> > I think it can be done racelessly with my patch, which is not really too
> > much overhead. I think if this is considered too much, then we should
> > either fix code and preferably de-export and remove module_refcount from
> > drivers, or remove module removal completely.
> 
> I doubt your patch matters too much, but I like it conceptually and it 
> seems to be a nice basis for perhaps doing something clever in the long 
> run.
> 
> [ ie avoiding the stop_machine and instead perhaps doing some optimistic 
>   thing like "see if we seem to be unused right now, then unregister us, 
>   and see - after unregistering - that the usage counts haven't increased, 
>   and re-register if they have. ]

That's true, reducing the requirement for stop_machine is always a nice
thing to have.

Also if anyone else is looking at a way to do _really_ scalable
refcounting elsewhere, this could be a good template (I certainly looked
here first when trying to get ideas for vfsmount refcounting).

 
> So I'd like to apply it as a "good improvement, even if module unloading 
> which is the only thing that _should_ care deeply should already be under 
> stop-machine".
> 
> But I'd like an ack or two first.

Sure, I'll let Rusty push it to you when he's happy with it.

Re: Is module refcounting racy?

[Eric Dumazet]

Le mardi 06 avril 2010 à 15:05 +1000, Nick Piggin a écrit :

> Also if anyone else is looking at a way to do _really_ scalable
> refcounting elsewhere, this could be a good template (I certainly looked
> here first when trying to get ideas for vfsmount refcounting).

Yes, nice trick Nick, I was thinking about it for network code :)

Acked-by: Eric Dumazet <eric.dumazet@gmail.com>

I confess the smp_wmb() in module_put() bothered me a bit until I saw it
was only a barrier() on X86 (if !CONFIG_X86_OOSTORE)

Re: Is module refcounting racy?

[Nick Piggin]

On Tue, Apr 06, 2010 at 08:19:23AM +0200, Eric Dumazet wrote:
> Le mardi 06 avril 2010 à 15:05 +1000, Nick Piggin a écrit :
> 
> > Also if anyone else is looking at a way to do _really_ scalable
> > refcounting elsewhere, this could be a good template (I certainly looked
> > here first when trying to get ideas for vfsmount refcounting).
> 
> Yes, nice trick Nick, I was thinking about it for network code :)
> 
> Acked-by: Eric Dumazet <eric.dumazet@gmail.com>
> 
> I confess the smp_wmb() in module_put() bothered me a bit until I saw it
> was only a barrier() on X86 (if !CONFIG_X86_OOSTORE)

Yep. smp_wmb() and smp_rmb() are both noops on x86 (OOSTORE is some
really obscure thing that we don't need to worry about really). On
POWER6/7 CPUs, it uses lwsync which is fairly cheap as well.

I think refcounting in _general_ needs a smp_wmb() (or, to be more
precise, probably a release barrier) before decrements because you don't
want previous futzing with the object to leak into after a final
decrement may be observed by another CPU. So it might be hard to avoid
anyway.