Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Dan Carpenter]

Read Al's email again:  https://lkml.org/lkml/2013/3/20/458

I don't know much about VFS locking, but the ashmem locking seems
pretty bogus to me.  Why can't multiple threads read() at the same
time?

One thing is that it should probably be broken into different locks
instead of a mini-BKL.  Instead of taking a bad design and trying to
hack it until it doesn't crash I think it would be better to redo
the locking from scratch.

regards,
dan carpenter

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Robert Love]

On Mon, Apr 22, 2013 at 10:22 AM, Dan Carpenter
<dan.carpenter@oracle.com> wrote:
> Read Al's email again:  https://lkml.org/lkml/2013/3/20/458
>
> I don't know much about VFS locking, but the ashmem locking seems
> pretty bogus to me.  Why can't multiple threads read() at the same
> time?

ashmem originally did not support read or write operations, just mmap,
which is all 99% of users want. The original concurrency model with
per-mapping ashmem_mutex's works fine there. It is only with the later
addition of read and write that locking becomes a cluster. If there
isn't an obvious way to refactor the locking, I'd suggest removing
read and write.

       Robert

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Shankar Brahadeeswaran]

>ashmem originally did not support read or write operations, just mmap,
>which is all 99% of users want. The original concurrency model with
>per-mapping ashmem_mutex's works fine there.

The situation I'm reporting here does not involve read/write. This is
to do with ashmem_mmap and ashmem_shrink.
The following is the control flow that could lead to dead lock
 ashmem_mmap
      |
      ----> ashmem_mutex acquired
      |
      -----> shmem_file_setup
                |
                ------> several calls that leads to __alloc_pages
                |     Now assuming that low memory condition is hit,
we could enter into reclaim path
                ..... ---------> shrink_slab (calls all the shrinker functions)
                   |
                    -----> ashmem_shrink --- Tries to acquire the same
ashmem_mutex that is taken
                              in this same path while in ashmem_mmap
leading to dead lock.

I'm unable to think of a straight forward way to fix this. If you have
any suggestions please provide the same.
If we are unable to solve this too with minor mods, as suggested by
Dan we have to re-look at the locking in this driver.

Warm Regards,
Shankar


On Mon, Apr 22, 2013 at 8:13 PM, Robert Love <rlove@google.com> wrote:
> On Mon, Apr 22, 2013 at 10:22 AM, Dan Carpenter
> <dan.carpenter@oracle.com> wrote:
>> Read Al's email again:  https://lkml.org/lkml/2013/3/20/458
>>
>> I don't know much about VFS locking, but the ashmem locking seems
>> pretty bogus to me.  Why can't multiple threads read() at the same
>> time?
>
> ashmem originally did not support read or write operations, just mmap,
> which is all 99% of users want. The original concurrency model with
> per-mapping ashmem_mutex's works fine there. It is only with the later
> addition of read and write that locking becomes a cluster. If there
> isn't an obvious way to refactor the locking, I'd suggest removing
> read and write.
>
>        Robert

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Robert Love]

[-- Attachment #1: Type: text/plain, Size: 483 bytes --]

On Tue, Apr 23, 2013 at 12:20 PM, Shankar Brahadeeswaran
<shankoo77@gmail.com> wrote:

> I'm unable to think of a straight forward way to fix this. If you have
> any suggestions please provide the same.
> If we are unable to solve this too with minor mods, as suggested by
> Dan we have to re-look at the locking in this driver.

This doesn't look insurmountable. It isn't necessary AFAICT to hold
ashmem_mutex across shmem_file_setup.

Patch attached (untested).

           Robert

[-- Attachment #2: ashmem-lock-fix.patch --]
[-- Type: application/octet-stream, Size: 861 bytes --]

It isn't necessary to hold ashmem_mutex across shmem_file_setup.

 ashmem.c |    5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

Signed-off-by: Robert Love <rlove@rlove.org>

--- linux-base/drivers/staging/android/ashmem.c	2013-04-23 13:18:05.803713678 -0400
+++ linux/drivers/staging/android/ashmem.c	2013-04-23 13:20:26.883238110 -0400
@@ -300,12 +300,15 @@
 	if (!asma->file) {
 		char *name = ASHMEM_NAME_DEF;
 		struct file *vmfile;
+		loff_t size = asma->size;
 
 		if (asma->name[ASHMEM_NAME_PREFIX_LEN] != '\0')
 			name = asma->name;
 
 		/* ... and allocate the backing shmem file */
-		vmfile = shmem_file_setup(name, asma->size, vma->vm_flags);
+		mutex_unlock(&ashmem_mutex);
+		vmfile = shmem_file_setup(name, size, vma->vm_flags);
+		mutex_lock(&ashmem_mutex);
 		if (unlikely(IS_ERR(vmfile))) {
 			ret = PTR_ERR(vmfile);
 			goto out;

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Shankar Brahadeeswaran]

Hi Robert,
Thanks for the feedback.

> This doesn't look insurmountable. It isn't necessary AFAICT to hold
> ashmem_mutex across shmem_file_setup.

I thought it may not be a good idea to do so and hence thought its
difficult to fix.
Dropping the lock in-between mmap may not be any issue if the user land code
follows a given sequence. But assuming that the following sequence of event
happens, it would lead to other races.

Process P1                                          Process P2
--------------                                           --------------
Creates ashmem region                       .....

Shares the fd to P2 via binder             Gets the fd

Does an mmap                                     Does an mmap

Releases the mutex before                  Procees with ashmem_mmap
since mutex is
shmem_file_setup and sleeps             available, checks for a
asma->file, still NUL
within shmem_file_setup                      so this also calls
shmem_file_setup.

The expected behavior is, one of them does the shmem_file_setup, puts
it in asma->file
The other process would just do get_file. With the original code
(without dropping the
mutex in-between) this would have been the behavior.
So IMHO dropping the lock in between could lead to other race conditions.

Also, there are other places in the code where ashmem_mutex is held and memory
allocation functions are called, ex:- range_alloc, calls kmem_cache_zalloc

Since ashmem_shrink holds the ashmem_mutex, any where from ashmem driver
if  a memory allocation function is called with the ashmem_mutex held
&&
if there is a low memory condition that leads to shrinkers being called
we'll hit the deadlock.

I'm trying to see if the ashmem_shrink should really hold the ashmem_mutex,
but looks like its necessary.

Warm Regards,
Shankar

On Tue, Apr 23, 2013 at 10:54 PM, Robert Love <rlove@google.com> wrote:
> On Tue, Apr 23, 2013 at 12:20 PM, Shankar Brahadeeswaran
> <shankoo77@gmail.com> wrote:
>
>> I'm unable to think of a straight forward way to fix this. If you have
>> any suggestions please provide the same.
>> If we are unable to solve this too with minor mods, as suggested by
>> Dan we have to re-look at the locking in this driver.
>
> This doesn't look insurmountable. It isn't necessary AFAICT to hold
> ashmem_mutex across shmem_file_setup.
>
> Patch attached (untested).
>
>            Robert

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Shankar Brahadeeswaran]

Sorry, my deadlock demonstration got messed up.

Process P1:
Creates ashmem region, Shares the fd to P2 via binder API, does an mmap
and from ashmem_mmap releases the ashmem_mutex before shm_file_setup
and sleeps within shmem_file_setup

Process P2:
Gets the fd, does an mmap on it. Since mutex is available and since asma->file
is still NULL, proceeds to call shm_file_setup again (releases the mutex before
doing so).

Now based on who returns last, one of them would overwrite the asma->file
with the others

The desired behavior is that one of them does shmem_file_setup and the other
process uses it.


On Thu, Apr 25, 2013 at 7:24 PM, Shankar Brahadeeswaran
<shankoo77@gmail.com> wrote:
> Hi Robert,
> Thanks for the feedback.
>
>> This doesn't look insurmountable. It isn't necessary AFAICT to hold
>> ashmem_mutex across shmem_file_setup.
>
> I thought it may not be a good idea to do so and hence thought its
> difficult to fix.
> Dropping the lock in-between mmap may not be any issue if the user land code
> follows a given sequence. But assuming that the following sequence of event
> happens, it would lead to other races.
>
> Process P1                                          Process P2
> --------------                                           --------------
> Creates ashmem region                       .....
>
> Shares the fd to P2 via binder             Gets the fd
>
> Does an mmap                                     Does an mmap
>
> Releases the mutex before                  Procees with ashmem_mmap
> since mutex is
> shmem_file_setup and sleeps             available, checks for a
> asma->file, still NUL
> within shmem_file_setup                      so this also calls
> shmem_file_setup.
>
> The expected behavior is, one of them does the shmem_file_setup, puts
> it in asma->file
> The other process would just do get_file. With the original code
> (without dropping the
> mutex in-between) this would have been the behavior.
> So IMHO dropping the lock in between could lead to other race conditions.
>
> Also, there are other places in the code where ashmem_mutex is held and memory
> allocation functions are called, ex:- range_alloc, calls kmem_cache_zalloc
>
> Since ashmem_shrink holds the ashmem_mutex, any where from ashmem driver
> if  a memory allocation function is called with the ashmem_mutex held
> &&
> if there is a low memory condition that leads to shrinkers being called
> we'll hit the deadlock.
>
> I'm trying to see if the ashmem_shrink should really hold the ashmem_mutex,
> but looks like its necessary.
>
> Warm Regards,
> Shankar
>
> On Tue, Apr 23, 2013 at 10:54 PM, Robert Love <rlove@google.com> wrote:
>> On Tue, Apr 23, 2013 at 12:20 PM, Shankar Brahadeeswaran
>> <shankoo77@gmail.com> wrote:
>>
>>> I'm unable to think of a straight forward way to fix this. If you have
>>> any suggestions please provide the same.
>>> If we are unable to solve this too with minor mods, as suggested by
>>> Dan we have to re-look at the locking in this driver.
>>
>> This doesn't look insurmountable. It isn't necessary AFAICT to hold
>> ashmem_mutex across shmem_file_setup.
>>
>> Patch attached (untested).
>>
>>            Robert

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Robert Love]

[-- Attachment #1: Type: text/plain, Size: 956 bytes --]

On Thu, Apr 25, 2013 at 9:54 AM, Shankar Brahadeeswaran
<shankoo77@gmail.com> wrote:

> Also, there are other places in the code where ashmem_mutex is held and memory
> allocation functions are called, ex:- range_alloc, calls kmem_cache_zalloc
>
> Since ashmem_shrink holds the ashmem_mutex, any where from ashmem driver
> if a memory allocation function is called with the ashmem_mutex held
> && if there is a low memory condition that leads to shrinkers being called
> we'll hit the deadlock.

The usual way this is solved is by checking the gfp_mask in the
shrinker code and bailing out (like we do now) for certain masks. So
e.g. the kmem_cache_zalloc in range_alloc is fixed by changing the
mask to GFP_FS.

> I'm trying to see if the ashmem_shrink should really hold the ashmem_mutex,
> but looks like its necessary.

Yes, it needs to hold ashmem_mutex.

There's no reason we have to run ashmem_shrink, though. See attached (untested).

      Robert

[-- Attachment #2: ashmem-lock-fix-rlove-2.patch --]
[-- Type: application/octet-stream, Size: 739 bytes --]

Avoid recursing into ashmem_shrink from within ashmem itself.

Signed-off-by: Robert Love <rlove@rlove.org>

 ashmem.c |    6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

--- linux-base/drivers/staging/android/ashmem.c	2013-04-25 10:58:33.251469472 -0400
+++ linux/drivers/staging/android/ashmem.c	2013-04-25 11:02:29.420644278 -0400
@@ -361,7 +361,11 @@
 	if (!sc->nr_to_scan)
 		return lru_count;
 
-	mutex_lock(&ashmem_mutex);
+	/* avoid recursing into this code from within ashmem itself */
+	if (!mutex_trylock(&ashmem_mutex)) {
+		return -1;
+	}
+
 	list_for_each_entry_safe(range, next, &ashmem_lru_list, lru) {
 		struct inode *inode = range->asma->file->f_dentry->d_inode;
 		loff_t start = range->pgstart * PAGE_SIZE;

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Shankar Brahadeeswaran]

Hi Robert,
Thanks for the patch. In the first email in this thread I was
proposing the same solution and had asked whether doing this has any
side effects.
That is how this discussion started. I did some experiments and have
got the answers for that. Just for every ones benefit I've re-worded
the question again
and put the details of the experiment below.

Question:
On occasions when we return because of the lock unavailability, what
could be the worst case number of ashmem pages that are left
unfreed (lru_count). Will it be very huge and have side effects?

To get the answer for this question, I added some instrumentation code
to ashmem_shrink function on top of the patch. I ran Android monkey
tests with lot of memory hungry applications so as to hit the Low
Memory situation more frequently. After running this for almost a day
I did not see a situation where the shrinker did not have the mutex.
In fact what I found is that (in this use case at-least) most of the
time the "lru_count" is zero, which means the application has not
unpinned the pages. So the shrinker has no job to do (basically
shrink_slab does not call ashmem_shrinker second time). So worst case
if we hit a scenario where the shrinker is called I'm sure the
lru_count would be very low. So even if the shrinker returns without
freeing them (because of unavailability of the lock) its not going to
be costly.

After this experiment, I too think that this patch (returning from
ashmem_shrink if the lock is not available) is good enough and does
not seem to have any major side effects.

PS: Any plans of submitting this patch formally?

Warm Regards,
Shankar

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Robert Love]

On Tue, Apr 30, 2013 at 9:29 AM, Shankar Brahadeeswaran
<shankoo77@gmail.com> wrote:

> Question:
> On occasions when we return because of the lock unavailability, what
> could be the worst case number of ashmem pages that are left
> unfreed (lru_count). Will it be very huge and have side effects?

On that VM shrink path, all of them, but they'll go on the next pass.
Even if they didn't, however, that is fine: The ashmem cache
functionality is advisory. From user-space's point of view, it doesn't
even know when VM pressure will occur, so it can't possibly care.

> To get the answer for this question, I added some instrumentation code
> to ashmem_shrink function on top of the patch. I ran Android monkey
> tests with lot of memory hungry applications so as to hit the Low
> Memory situation more frequently. After running this for almost a day
> I did not see a situation where the shrinker did not have the mutex.
> In fact what I found is that (in this use case at-least) most of the
> time the "lru_count" is zero, which means the application has not
> unpinned the pages. So the shrinker has no job to do (basically
> shrink_slab does not call ashmem_shrinker second time). So worst case
> if we hit a scenario where the shrinker is called I'm sure the
> lru_count would be very low. So even if the shrinker returns without
> freeing them (because of unavailability of the lock) its not going to
> be costly.

That is expected. This race window is very, very small.

> After this experiment, I too think that this patch (returning from
> ashmem_shrink if the lock is not available) is good enough and does
> not seem to have any major side effects.
>
> PS: Any plans of submitting this patch formally?

Sure. Greg? :)

       Robert

Re: [BUG] staging: android: ashmem: Deadlock during ashmem_shrink

[Greg Kroah-Hartman]

On Tue, Apr 30, 2013 at 06:32:54PM -0400, Robert Love wrote:
> > After this experiment, I too think that this patch (returning from
> > ashmem_shrink if the lock is not available) is good enough and does
> > not seem to have any major side effects.
> >
> > PS: Any plans of submitting this patch formally?
> 
> Sure. Greg? :)

I'll be glad to take it if you resend it in a format that I can apply it
in :)

thanks,

greg k-h