Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1726305 > unrolled thread

a competition when some threads acquire futex

Back to article view | Back to linux.kernel

Contents

  a competition when some threads acquire futex "chengjian (D)" <cj.chengjian@huawei.com> - 2017-09-05 04:00 +0200
    Re: a competition when some threads acquire futex Thomas Gleixner <tglx@linutronix.de> - 2017-09-05 21:40 +0200
      Re: a competition when some threads acquire futex "chengjian (D)" <cj.chengjian@huawei.com> - 2017-09-06 02:30 +0200
        Re: a competition when some threads acquire futex Thomas Gleixner <tglx@linutronix.de> - 2017-09-06 10:40 +0200
          Re: a competition when some threads acquire futex Peter Zijlstra <peterz@infradead.org> - 2017-09-06 11:00 +0200
            Re: a competition when some threads acquire futex Peter Zijlstra <peterz@infradead.org> - 2017-09-06 11:10 +0200
          Re: a competition when some threads acquire futex "chengjian (D)" <cj.chengjian@huawei.com> - 2017-09-06 11:20 +0200

#1726305 — a competition when some threads acquire futex

A competition happend when some thread use pthread_mutex(futex in 
kernel). I make a demo about this : two thread get a lock and then sleep 
for a few time, finally unlock when waked up.

```cpp
         pthread_mutex_lock(&mutex);

         //printf("tid = %lu, count = %d\n", pthread_self( ), i);
         printf("tid = %lu, count = %d\n", gettid( ), i);
         i++;

         //sleep(6);
         usleep(6000000);
         pthread_mutex_unlock(&mutex);
```

What we expect is that these processes are fairly executing and 
acquiring locks.

The actual phenomenon, however, is that the process which get the lock 
first (assume A) will acquire the lock immediately after release it. It 
leads to that another thread B can't  access the lock for a long tim, 
especially when the two thread run on the same CPU.

code follows :

```c
//  muext_bug.c

pid_t gettid(void)
{
         return syscall(SYS_gettid);
}

pthread_mutex_t mutex ;

void *print_msg(void *arg){

         int         i = 0;
         cpu_set_t   mask;

         printf("tid = %lu(%lu) START\n", gettid( ), pthread_self( ), i);

         CPU_ZERO(&mask);
         CPU_SET(0, &mask);

         if (pthread_setaffinity_np(pthread_self( ), sizeof(mask), 
&mask) < 0)
         {
                 fprintf(stderr, "set thread affinity failed\n");
         }
         else
         {
                 printf("tid = %lu affinity to CPU%d\n", gettid( ), 0);
         }

         while( 1 )
         {
                 pthread_mutex_lock(&mutex);

                 //printf("tid = %lu, count = %d\n", pthread_self( ), i);
                 printf("tid = %lu, count = %d\n", gettid( ), i);
                 i++;

                 //sleep(6);
                 usleep(6000000);
                 pthread_mutex_unlock(&mutex);
         }

}

int main(int argc, char** argv)
{
         pthread_t id1;
         pthread_t id2;

         printf("main pid = %d\n", getpid( ));

         pthread_mutex_init(&mutex, NULL);
         pthread_create(&id1, NULL, print_msg, NULL);
         pthread_create(&id2, NULL, print_msg, NULL);

         pthread_join(id1, NULL);
         pthread_join(id2, NULL);

         pthread_mutex_destroy(&mutex);

         return EXIT_SUCCESS;
}
```

result :

```cpp
./mutex_bug
main pid = 17326
tid = 17327(140113713104640) START
tid = 17328(140113704711936) START
tid = 17327 affinity to CPU0
tid = 17327, count = 0
tid = 17328 affinity to CPU0
tid = 17327, count = 1
tid = 17327, count = 2
tid = 17327, count = 3
tid = 17327, count = 4
tid = 17327, count = 5
tid = 17327, count = 6
tid = 17327, count = 7
tid = 17327, count = 8
tid = 17327, count = 9
tid = 17327, count = 10

......

tid = 17327, count = 838
^C
```

use perf ftrace to shows the graph of the function calls. We found that 
the process 17327 auquire the lock quickly after call futex_wake( ), so 
the process 17328 futex_wait( ) all the time.

We can solve this problem by scheduling once after release the lock. But 
what i don't understand is, when the process return to the user space 
from kernel, the scheduler is used to select a new process to run, but 
it doesn'tt work, what's happended.

Signed-off-by: Cheng Jian <cj.chengjian@huawei.com>
Signed-off-by: Li Bin <huawei.libin@huawei.com>
---
  kernel/futex.c | 1 +
  1 file changed, 1 insertion(+)

diff --git a/kernel/futex.c b/kernel/futex.c
index 3d38eaf..0b2d17a 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1545,6 +1545,7 @@ static int wake_futex_pi(u32 __user *uaddr, u32 
uval, struct futex_pi_state *pi_
   	spin_unlock(&hb->lock);
  	wake_up_q(&wake_q);
+        _cond_resched( );
  out_put_key:
  	put_futex_key(&key);
  out:
-- 
1.8.3.1


.

[toc] | [next] | [standalone]

#1726955

On Tue, 5 Sep 2017, chengjian (D) wrote:

> int main(int argc, char** argv)
> {
>         pthread_t id1;
>         pthread_t id2;
> 
>         printf("main pid = %d\n", getpid( ));
> 
>         pthread_mutex_init(&mutex, NULL);

So this is a plain mutex, which maps to a plain futex.

> use perf ftrace to shows the graph of the function calls. We found that the
> process 17327 auquire the lock quickly after call futex_wake( ), so the
> process 17328 futex_wait( ) all the time.

The observed functions look correct for that futex type.

> diff --git a/kernel/futex.c b/kernel/futex.c
> index 3d38eaf..0b2d17a 100644
> --- a/kernel/futex.c
> +++ b/kernel/futex.c
> @@ -1545,6 +1545,7 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval,
> struct futex_pi_state *pi_
>   	spin_unlock(&hb->lock);
>  	wake_up_q(&wake_q);
> +        _cond_resched( );

What's less correct is the placement of the cond_resched() which you patch
into the function:

       wake_futex_pi() 

wake_futex_pi() is not even remotely involved in this problem, so I have a
hard time to understand how this patch 'solves' it.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1727086

>> diff --git a/kernel/futex.c b/kernel/futex.c
>> index 3d38eaf..0b2d17a 100644
>> --- a/kernel/futex.c
>> +++ b/kernel/futex.c
>> @@ -1545,6 +1545,7 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval,
>> struct futex_pi_state *pi_
>>    	spin_unlock(&hb->lock);
>>   	wake_up_q(&wake_q);
>> +        _cond_resched( );
>

Hi Thomas,

I wrote _cond_resched( ) in futex_wake( ) which will be called to wake 
up waiters
when the process release the futex.


But the patch producted by git format-patch displayed in wake_futex_pi( ).


```c

/*
  * Wake up waiters matching bitset queued on this futex (uaddr).
  */
static int
futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
{
     struct futex_hash_bucket *hb;
     struct futex_q *this, *next;
     union futex_key key = FUTEX_KEY_INIT;
     int ret;
     DEFINE_WAKE_Q(wake_q);

     if (!bitset)
         return -EINVAL;

     ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, VERIFY_READ);
     if (unlikely(ret != 0))
         goto out;

     hb = hash_futex(&key);

     /* Make sure we really have tasks to wakeup */
     if (!hb_waiters_pending(hb))
         goto out_put_key;

     spin_lock(&hb->lock);

     plist_for_each_entry_safe(this, next, &hb->chain, list) {
         if (match_futex (&this->key, &key)) {
             if (this->pi_state || this->rt_waiter) {
                 ret = -EINVAL;
                 break;
             }

             /* Check if one of the bits is set in both bitsets */
             if (!(this->bitset & bitset))
                 continue;

             mark_wake_futex(&wake_q, this);
             if (++ret >= nr_wake)
                 break;
         }
     }

     spin_unlock(&hb->lock);
     wake_up_q(&wake_q);

+ _cond_resched( );
out_put_key:
     put_futex_key(&key);
out:
     return ret;
}
```



Thanks.

Cheng Jian

[toc] | [prev] | [next] | [standalone]

#1727224

On Wed, 6 Sep 2017, chengjian (D) wrote:

> > > diff --git a/kernel/futex.c b/kernel/futex.c
> > > index 3d38eaf..0b2d17a 100644
> > > --- a/kernel/futex.c
> > > +++ b/kernel/futex.c
> > > @@ -1545,6 +1545,7 @@ static int wake_futex_pi(u32 __user *uaddr, u32
> > > uval,
> > > struct futex_pi_state *pi_
> > >    	spin_unlock(&hb->lock);
> > >   	wake_up_q(&wake_q);
> > > +        _cond_resched( );
> > 

> I wrote _cond_resched( ) in futex_wake( ) which will be called to wake up
> waiters
> when the process release the futex.
> 
> 
> But the patch producted by git format-patch displayed in wake_futex_pi( ).

Ok. Still that patch has issues.

1) It's white space damaged. Please use TAB not spaces for
   indentation. checkpatch.pl would have told you.

2) Why are you using _cond_resched() instead of plain cond_resched().

   cond_resched() is what you want to use.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1727246

On Wed, Sep 06, 2017 at 10:36:29AM +0200, Thomas Gleixner wrote:
> On Wed, 6 Sep 2017, chengjian (D) wrote:
> 
> > > > diff --git a/kernel/futex.c b/kernel/futex.c
> > > > index 3d38eaf..0b2d17a 100644
> > > > --- a/kernel/futex.c
> > > > +++ b/kernel/futex.c
> > > > @@ -1545,6 +1545,7 @@ static int wake_futex_pi(u32 __user *uaddr, u32
> > > > uval,
> > > > struct futex_pi_state *pi_
> > > >    	spin_unlock(&hb->lock);
> > > >   	wake_up_q(&wake_q);
> > > > +        _cond_resched( );
> > > 
> 
> > I wrote _cond_resched( ) in futex_wake( ) which will be called to wake up
> > waiters
> > when the process release the futex.
> > 
> > 
> > But the patch producted by git format-patch displayed in wake_futex_pi( ).
> 
> Ok. Still that patch has issues.
> 
> 1) It's white space damaged. Please use TAB not spaces for
>    indentation. checkpatch.pl would have told you.
> 
> 2) Why are you using _cond_resched() instead of plain cond_resched().
> 
>    cond_resched() is what you want to use.

Right, but even if it was a coherent patch, I'm not sure it makes sense.

futex_wait() / futex_wake() don't make ordering guarantees and in
general you don't get to have wakeup preemption if you don't run a
PREEMPT kernel.

So what makes this wakeup so special? Any changelog would need to have a
convincing argument.

[toc] | [prev] | [next] | [standalone]

#1727262

On Wed, Sep 06, 2017 at 10:56:08AM +0200, Peter Zijlstra wrote:

> Right, but even if it was a coherent patch, I'm not sure it makes sense.
> 
> futex_wait() / futex_wake() don't make ordering guarantees and in
> general you don't get to have wakeup preemption if you don't run a
> PREEMPT kernel.
> 
> So what makes this wakeup so special? Any changelog would need to have a
> convincing argument.

Also, even on !PREEMPT, if that wakeup sets NEED_RESCHED, the return to
userspace after futex_wake() should reschedule.


So I'm really not getting it.

[toc] | [prev] | [next] | [standalone]

#1727280

On 2017/9/6 16:36, Thomas Gleixner write:
> Ok. Still that patch has issues.
>
> 1) It's white space damaged. Please use TAB not spaces for
>     indentation. checkpatch.pl would have told you.
>
> 2) Why are you using _cond_resched() instead of plain cond_resched().
>
>     cond_resched() is what you want to use.


Hi Thomas.

I am very sorry about the issues of my patch.
I am a kernel newbie and i set expandtab in my .vimrc file
which means tab characters are converted to spaces.
I have fixed it and will check my patch first next time.


Thanks.
    Cheng Jian

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web