linux-kernel - Possible lock-less list race in scheduler

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 5 Mar 2015 23:48:51 +0000 (UTC)
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:	Huang Ying <ying.huang@...el.com>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	Lai Jiangshan <eag0628@...il.com>,
	Peter Zijlstra <peterz@...radead.org>,
	LKML <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...nel.org>,
	Steven Rostedt <rostedt@...dmis.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>
Subject: Possible lock-less list race in scheduler_ipi()

Hi,

I recently reviewed the scheduler_ipi() code by
coincidence, and noticed that the use of llist.h
in there seemed a bit odd. So I'd like to have
more eyes to help me look into this.

I've been told that there has been issues with
IPIs lately, so here is one possible scenario
I think might be possible:

- scheduler_ipi()
  - sched_ttwu_pending()
    - llist_del_all()
      (grabs the wake_list with xchg())
    - raw_spin_lock_irqsave(&rq->lock, flags);
    - iteration on the llist (owned locally by interrupt handler)
      (for each item)
        p = llist_entry(llist, struct task_struct, wake_entry);
        llist = llist_next(llist);
        ttwu_do_activate(rq, p, 0);
    - raw_spin_unlock_irqrestore(&rq->lock, flags);

ttwu_do_activate() ends up calling
ttwu_activate() and ttwu_do_wakeup(), 

I'm worried that ttwu_do_wakeup() might end up
indirectly handing off the task to the following
functions (within another execution context):

- try_to_wake_up()
  - ttwu_queue()
    - ttwu_queue_remote adds the process to another
      wake_list with a cmpxchg()

llist_next() is pretty simple:

static inline struct llist_node *llist_next(struct llist_node *node)
{
        return node->next;
}

It is so simple that I wonder if the compiler would be
within its rights to reorder the load of node->next
after some operations within ttwu_do_activate(), thus
causing corruption of this linked-list due to a
concurrent try_to_wake_up() performed by another core.

Am I too paranoid about the possible compiler mishaps
there, or are my concerns justified ?

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/