Skip to contentSkip to conversation

sched/numa: Implement per task memory placement for 'big' processes

tip:sched/numa tip-bot for Peter Zijlstra 1 participant 1 message Sep 28, 2012

Subsystems (5)
lore
Share & tools
lore
#0 lore raw
Commit-ID:  fa74ef9e42df04b671b77baf516012987da2034e
Gitweb:     http://git.kernel.org/tip/fa74ef9e42df04b671b77baf516012987da2034e
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Wed, 18 Jul 2012 22:06:47 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 27 Sep 2012 19:17:09 +0200

sched/numa: Implement per task memory placement for 'big' processes

Implement a per-task memory placement scheme for 'big' tasks (as per the last patch). It relies on a regular PROT_NONE 'migration' fault to scan the memory space of the procress and uses a two stage migration scheme to reduce the invluence of unlikely usage relations.

It relies on the assumption that the compute part is tied to a paticular task and builds a task<->page relation set to model the compute<->data relation.

Probability says that the task faulting on a page after we protect it, is most likely to be the task that uses that page most.

To decrease the likelyhood of acting on a false relation, we only migrate a page when two consecutive samples are from the same task.

I'm still not entirely convinced this scheme is sound, esp. for things like virtualization and n:m threading solutions in general the compute<->task relation is fundamentally untrue.

NOTES:

- we don't actually sample the task, but the task's home-node as a migration target, so we're effectively building home-node<->page relations not task<->page relations.

- we migrate to the task's home-node, not the node the task is currently running on, since the home-node is the long term target for the task to run on, irrespective of whatever node it might temporarily run on.

---
 include/linux/mempolicy.h |    6 +++-
 include/linux/mm_types.h  |   15 +++++++++++++
 kernel/sched/fair.c       |   51 ++++++++++++++++++++++++++++++++++----------
 kernel/sched/features.h   |    1 +
 mm/huge_memory.c          |    3 +-
 mm/memory.c               |    2 +-
 mm/mempolicy.c            |   39 ++++++++++++++++++++++++++++++++-
 7 files changed, 99 insertions(+), 18 deletions(-)
include/linux/mempolicy.h +4 -2
index 17cf9da..7f303d1 100644
@@ -69,6 +69,7 @@ enum mpol_rebind_step {
 #define MPOL_F_LOCAL   (1 << 1)	/* preferred local allocation */
 #define MPOL_F_REBINDING (1 << 2)	/* identify policies in rebinding */
 #define MPOL_F_MOF	(1 << 3) /* this policy wants migrate on fault */
+#define MPOL_F_HOME	(1 << 4) /* this is the home-node policy */
 
 #ifdef __KERNEL__
 
@@ -263,7 +264,8 @@ static inline int vma_migratable(struct vm_area_struct *vma)
 	return 1;
 }
 
-extern int mpol_misplaced(struct page *, struct vm_area_struct *, unsigned long);
+extern int mpol_misplaced(struct page *, struct vm_area_struct *,
+			  unsigned long, int);
 
 extern void lazy_migrate_process(struct mm_struct *mm);
 
@@ -393,7 +395,7 @@ static inline int mpol_to_str(char *buffer, int maxlen, struct mempolicy *pol,
 }
 
 static inline int mpol_misplaced(struct page *page, struct vm_area_struct *vma,
-				 unsigned long address)
+				 unsigned long address, int multi)
 {
 	return -1; /* no node preference */
 }
include/linux/mm_types.h +15 -0
index 930c006..f306cbb 100644
@@ -176,6 +176,12 @@ struct page {
 	 */
 	void *shadow;
 #endif
+#ifdef CONFIG_SCHED_NUMA
+	/*
+	 * XXX fold this into flags for 64bit.. see next patch.
+	 */
+	int nid_last;
+#endif
 }
 /*
  * The struct page can be forced to be double word aligned so that atomic ops
@@ -411,6 +417,15 @@ struct mm_struct {
 	struct uprobes_state uprobes_state;
 };
 
+static inline bool mm_numa_big(struct mm_struct *mm)
+{
+#ifdef CONFIG_SCHED_NUMA
+	return mm->numa_big;
+#else
+	return false;
+#endif
+}
+
 static inline void mm_init_cpumask(struct mm_struct *mm)
 {
 #ifdef CONFIG_CPUMASK_OFFSTACK
kernel/sched/fair.c +39 -12

105 lines not on this page · raw message

kernel/sched/features.h +1 -0
index fa6a0ac..845b838 100644
@@ -64,6 +64,7 @@ SCHED_FEAT(LB_MIN, false)
 
 #ifdef CONFIG_SCHED_NUMA
 SCHED_FEAT(NUMA,           true)
+SCHED_FEAT(NUMA_FORCE_BIG, false)
 SCHED_FEAT(NUMA_HOT,       true)
 SCHED_FEAT(NUMA_BIAS,      true)
 SCHED_FEAT(NUMA_PULL,      true)
mm/huge_memory.c +2 -1
index a147d29..45b11f1 100644
@@ -791,7 +791,7 @@ void do_huge_pmd_prot_none(struct mm_struct *mm, struct vm_area_struct *vma,
 	 * XXX should we serialize against split_huge_page ?
 	 */
 
-	node = mpol_misplaced(page, vma, haddr);
+	node = mpol_misplaced(page, vma, haddr, mm->numa_big);
 	if (node == -1)
 		goto do_fixup;
 
@@ -1377,6 +1377,7 @@ static void __split_huge_page_refcount(struct page *page)
 		page_tail->mapping = page->mapping;
 
 		page_tail->index = page->index + i;
+		page_tail->nid_last = page->nid_last;
 
 		BUG_ON(!PageAnon(page_tail));
 		BUG_ON(!PageUptodate(page_tail));
mm/memory.c +1 -1
index 965eeef..7dbdd85 100644
@@ -3448,7 +3448,7 @@ static void do_prot_none_numa(struct mm_struct *mm, struct vm_area_struct *vma,
 	 * For NUMA systems we use the special PROT_NONE maps to drive
 	 * lazy page migration, see MPOL_MF_LAZY and related.
 	 */
-	node = mpol_misplaced(page, vma, address);
+	node = mpol_misplaced(page, vma, address, mm_numa_big(mm));
 	if (node != -1)
 		migrate_misplaced_page(mm, page, node);
 }
mm/mempolicy.c +37 -2
index 6c6490b..861190f 100644
@@ -2174,6 +2174,7 @@ mpol_shared_policy_lookup(struct shared_policy *sp, unsigned long idx)
  * @page   - page to be checked
  * @vma    - vm area where page mapped
  * @addr   - virtual address where page mapped
+ * @multi  - use multi-stage node binding
  *
  * Lookup current policy node id for vma,addr and "compare to" page's
  * node id.
@@ -2185,7 +2186,8 @@ mpol_shared_policy_lookup(struct shared_policy *sp, unsigned long idx)
  * Policy determination "mimics" alloc_page_vma().
  * Called from fault path where we know the vma and faulting address.
  */
-int mpol_misplaced(struct page *page, struct vm_area_struct *vma, unsigned long addr)
+int mpol_misplaced(struct page *page, struct vm_area_struct *vma,
+		   unsigned long addr, int multi)
 {
 	struct mempolicy *pol;
 	struct zone *zone;
@@ -2236,6 +2238,39 @@ int mpol_misplaced(struct page *page, struct vm_area_struct *vma, unsigned long
 	default:
 		BUG();
 	}
+
+	/*
+	 * Multi-stage node selection is used in conjunction with a periodic
+	 * migration fault to build a temporal task<->page relation. By
+	 * using a two-stage filter we remove short/unlikely relations.
+	 *
+	 * Using P(p) ~ n_p / n_t as per frequentist probability, we can
+	 * equate a task's usage of a particular page (n_p) per total usage
+	 * of this page (n_t) (in a given time-span) to a probability.
+	 *
+	 * Our periodic faults will then sample this probability and getting
+	 * the same result twice in a row, given these samples are fully
+	 * independent, is then given by P(n)^2, provided our sample period
+	 * is sufficiently short compared to the usage pattern.
+	 *
+	 * This quadric squishes small probabilities, making it less likely
+	 * we act on an unlikely task<->page relation.
+	 *
+	 * NOTE: effectively we're using task-home-node<->page-node relations
+	 * since those are the only thing we can affect.
+	 *
+	 * NOTE: we're using task-home-node as opposed to the current node
+	 * the task might be running on, since the task-home-node is the
+	 * long-term node of this task, further reducing noise. Also see
+	 * task_tick_numa().
+	 */
+	if (multi && (pol->flags & MPOL_F_HOME)) {
+		if (page->nid_last != polnid) {
+			page->nid_last = polnid;
+			goto out;
+		}
+	}
+
 	if (curnid != polnid)
 		ret = polnid;
 out:
@@ -2427,7 +2462,7 @@ void __init numa_policy_init(void)
 		preferred_node_policy[nid] = (struct mempolicy) {
 			.refcnt = ATOMIC_INIT(1),
 			.mode = MPOL_PREFERRED,
-			.flags = MPOL_F_MOF,
+			.flags = MPOL_F_MOF | MPOL_F_HOME,
 			.v = { .preferred_node = nid, },
 		};
 	}