linux-kernel - Re: [PATCH 1/2] sched: Enforce order of leaf CFS runqueues

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-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1311254423-25484-1-git-send-email-schnhrr@cs.tu-berlin.de>
Date:	Thu, 21 Jul 2011 15:20:20 +0200
From:	Jan H. Schönherr <schnhrr@...tu-berlin.de>
To:	Paul Turner <pjt@...gle.com>
Cc:	Ingo Molnar <mingo@...e.hu>, Peter Zijlstra <peterz@...radead.org>,
	linux-kernel@...r.kernel.org,
	Jan H. Schönherr <schnhrr@...tu-berlin.de>
Subject: Re: [PATCH 1/2] sched: Enforce order of leaf CFS runqueues

Am 19.07.2011 01:24, schrieb Paul Turner:
> I wonder if we could move this logic to the enqueue_task_fair path()
> as that is the gating condition to become a leaf for load tracking.
> Ideally we could build up a list of the untracked entities and then
> splice it, but alas we have to use an rculist to track leaf cfs_rq's
> so that we can walk it without locks in update shares.

Out of curiosity I took a closer look at your "ideal" approach.

If I am not mistaken, this should actually work.
The results come as a reply to this mail.

The problem with the rcu-list is, that we cannot put individual
leaves on a different list, as this would irritate concurrent
readers. But what we can do without problems is to assemble
the leaves into something like a "detached list". That is:
while we modify the next-pointers of deleted leaves, we only
let them point to other (possibly deleted) leaves of the same 
list, so that concurrent readers will still find their way back.

As long as there is no error in my RCU reasoning, we get your
ideal approach that is also not subject to Peter's "We do more
work than before" statement.

What do you think of this?

Patch 1: After inventing __list_link(), I realized, that this
	 function already existed, but with a different name.

	 This patch just does some renaming. Not really needed,
	 but if I use the old naming in patch 2+3 it's really 
	 hard to understand what's actually going on.

Patch 2: This introduces new list functions to splice RCU lists.

Patch 3: The actual change to the leaf handling.

Regards
Jan

Jan H. Schönherr (3):
  list, treewide: Rename __list_del() to __list_link()
  rcu: More rcu-variants for list manipulation
  sched: Handle on_list ancestor in list_add_leaf_cfs_rq()

 drivers/firewire/core-topology.c     |    2 +-
 drivers/gpu/drm/ttm/ttm_page_alloc.c |    4 +-
 include/linux/list.h                 |    6 ++--
 include/linux/rculist.h              |   28 +++++++++++++++-
 kernel/sched_fair.c                  |   59 ++++++++++++++++++++++-----------
 lib/list_debug.c                     |    2 +-
 6 files changed, 73 insertions(+), 28 deletions(-)

-- 
1.7.6

--
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/