Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
To:     Waiman Long <longman@redhat.com>,
        Davidlohr Bueso <dave@stgolabs.net>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        Peter Zijlstra <peterz@infradead.org>
Cc:     1vier1@web.de, "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
From:   Manfred Spraul <manfred@colorfullife.com>
Subject: wake_q memory ordering
Message-ID: <990690aa-8281-41da-4a46-99bb8f9fec31@colorfullife.com>
Date:   Thu, 10 Oct 2019 12:41:11 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.1.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Content-Language: en-US
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Hi,

Waiman Long noticed that the memory barriers in sem_lock() are not 
really documented, and while adding documentation, I ended up with one 
case where I'm not certain about the wake_q code:

Questions:
- Does smp_mb__before_atomic() + a (failed) cmpxchg_relaxed provide an
   ordering guarantee?
- Is it ok that wake_up_q just writes wake_q->next, shouldn't
   smp_store_acquire() be used? I.e.: guarantee that wake_up_process()
   happens after cmpxchg_relaxed(), assuming that a failed cmpxchg_relaxed
   provides any ordering.

Example:
- CPU2 never touches lock a. It is just an unrelated wake_q user that also
   wants to wake up task 1234.
- I've noticed already that smp_store_acquire() doesn't exist.
   So smp_store_mb() is required. But from semantical point of view, we 
would
   need an ACQUIRE: the wake_up_process() must happen after cmpxchg().
- May wake_up_q() rely on the spinlocks/memory barriers in try_to_wake_up,
   or should the function be safe by itself?

CPU1: /current=1234, inside do_semtimedop()/
         g_wakee = current;
         current->state = TASK_INTERRUPTIBLE;
         spin_unlock(a);

CPU2: / arbitrary kernel thread that uses wake_q /
                 wake_q_add(&unrelated_q, 1234);
                 wake_up_q(&unrelated_q);
                 <...ongoing>

CPU3: / do_semtimedop() + wake_up_sem_queue_prepare() /
                         spin_lock(a);
                         wake_q_add(,g_wakee);
                         < within wake_q_add() >:
                           smp_mb__before_atomic();
                           if (unlikely(cmpxchg_relaxed(&node->next, 
NULL, WAKE_Q_TAIL)))
                               return false; /* -> this happens */

CPU2:
                 <within wake_up_q>
                 1234->wake_q.next = NULL; <<<<<<<<< Ok? Is 
store_acquire() missing? >>>>>>>>>>>>
                 wake_up_process(1234);
                 < within wake_up_process/try_to_wake_up():
                     raw_spin_lock_irqsave()
                     smp_mb__after_spinlock()
                     if(1234->state = TASK_RUNNING) return;
                  >


rewritten:

start condition: A = 1; B = 0;

CPU1:
     B = 1;
     RELEASE, unlock LockX;

CPU2:
     lock LockX, ACQUIRE
     if (LOAD A == 1) return; /* using cmp_xchg_relaxed */

CPU2:
     A = 0;
     ACQUIRE, lock LockY
     smp_mb__after_spinlock();
     READ B

Question: is A = 1, B = 0 possible?

--

     Manfred