Memory cgroup hierarchy introduction

That's not a very intuitive interface. Why not memory.use_hierarchy?

Quoted 1 line · Paul Menage

That's not a very intuitive interface. Why not memory.use_hierarchy?

Or for consistency with the existing cpuset.memory_pressure_enabled, just memory.hierarchy_enabled ?

Add support for building hierarchies in resource counters. Cgroups allows us to build a deep hierarchy, but we currently don't link the resource counters belonging to the memory controller control groups, which are linked in cgroup hiearchy. This patch provides the infrastructure for resource counters that have the same hiearchy as their cgroup counter parts.

These set of patches are based on the resource counter hiearchy patches posted by Pavel Emelianov.

NOTE: Building hiearchies is expensive, deeper hierarchies imply charging the all the way up to the root. It is known that hiearchies are expensive, so the user needs to be careful and aware of the trade-offs before creating very deep ones.

Signed-off-by Balbir Singh <[email protected]>

---

 include/linux/res_counter.h |    8 ++++++--
 kernel/res_counter.c        |   42 ++++++++++++++++++++++++++++++++++--------
 mm/memcontrol.c             |    9 ++++++---
 3 files changed, 46 insertions(+), 13 deletions(-)

diff -puN include/linux/res_counter.h~resource-counters-hierarchy-support include/linux/res_counter.h

include/linux/res_counter.h renamed from include/linux/res_counter.h~resource-counters-hierarchy-support +6 -2

@@ -43,6 +43,10 @@ struct res_counter {
 	 * the routines below consider this to be IRQ-safe
 	 */
 	spinlock_t lock;
+	/*
+	 * Parent counter, used for hierarchial resource accounting
+	 */
+	struct res_counter *parent;
 };
 
 /**

@@ -87,7 +91,7 @@ enum {
  * helpers for accounting
  */
 
-void res_counter_init(struct res_counter *counter);
+void res_counter_init(struct res_counter *counter, struct res_counter *parent);
 
 /*
  * charge - try to consume more resource.

@@ -103,7 +107,7 @@ void res_counter_init(struct res_counter
 int __must_check res_counter_charge_locked(struct res_counter *counter,
 		unsigned long val);
 int __must_check res_counter_charge(struct res_counter *counter,
-		unsigned long val);
+		unsigned long val, struct res_counter **limit_fail_at);
 
 /*
  * uncharge - tell that some portion of the resource is released

diff -puN kernel/res_counter.c~resource-counters-hierarchy-support kernel/res_counter.c

kernel/res_counter.c renamed from kernel/res_counter.c~resource-counters-hierarchy-support +34 -8

@@ -15,10 +15,11 @@
 #include <linux/uaccess.h>
 #include <linux/mm.h>
 
-void res_counter_init(struct res_counter *counter)
+void res_counter_init(struct res_counter *counter, struct res_counter *parent)
 {
 	spin_lock_init(&counter->lock);
 	counter->limit = (unsigned long long)LLONG_MAX;
+	counter->parent = parent;
 }
 
 int res_counter_charge_locked(struct res_counter *counter, unsigned long val)

@@ -34,14 +35,34 @@ int res_counter_charge_locked(struct res
 	return 0;
 }
 
-int res_counter_charge(struct res_counter *counter, unsigned long val)
+int res_counter_charge(struct res_counter *counter, unsigned long val,
+			struct res_counter **limit_fail_at)
 {
 	int ret;
 	unsigned long flags;
+	struct res_counter *c, *u;
 
-	spin_lock_irqsave(&counter->lock, flags);
-	ret = res_counter_charge_locked(counter, val);
-	spin_unlock_irqrestore(&counter->lock, flags);
+	*limit_fail_at = NULL;
+	local_irq_save(flags);
+	for (c = counter; c != NULL; c = c->parent) {
+		spin_lock(&c->lock);
+		ret = res_counter_charge_locked(c, val);
+		spin_unlock(&c->lock);
+		if (ret < 0) {
+			*limit_fail_at = c;
+			goto undo;
+		}
+	}
+	ret = 0;
+	goto done;
+undo:
+	for (u = counter; u != c; u = u->parent) {
+		spin_lock(&u->lock);
+		res_counter_uncharge_locked(u, val);
+		spin_unlock(&u->lock);
+	}
+done:
+	local_irq_restore(flags);
 	return ret;
 }
 

@@ -56,10 +77,15 @@ void res_counter_uncharge_locked(struct 
 void res_counter_uncharge(struct res_counter *counter, unsigned long val)
 {
 	unsigned long flags;
+	struct res_counter *c;
 
-	spin_lock_irqsave(&counter->lock, flags);
-	res_counter_uncharge_locked(counter, val);
-	spin_unlock_irqrestore(&counter->lock, flags);
+	local_irq_save(flags);
+	for (c = counter; c != NULL; c = c->parent) {
+		spin_lock(&c->lock);
+		res_counter_uncharge_locked(c, val);
+		spin_unlock(&c->lock);
+	}
+	local_irq_restore(flags);
 }
 
 

diff -puN mm/memcontrol.c~resource-counters-hierarchy-support mm/memcontrol.c

mm/memcontrol.c renamed from mm/memcontrol.c~resource-counters-hierarchy-support +6 -3

@@ -485,6 +485,7 @@ int mem_cgroup_try_charge(struct mm_stru
 {
 	struct mem_cgroup *mem;
 	int nr_retries = MEM_CGROUP_RECLAIM_RETRIES;
+	struct res_counter *fail_res;
 	/*
 	 * We always charge the cgroup the mm_struct belongs to.
 	 * The mm_struct's mem_cgroup changes on task migration if the

@@ -510,7 +511,7 @@ int mem_cgroup_try_charge(struct mm_stru
 	}
 
 
-	while (unlikely(res_counter_charge(&mem->res, PAGE_SIZE))) {
+	while (unlikely(res_counter_charge(&mem->res, PAGE_SIZE, &fail_res))) {
 		if (!(gfp_mask & __GFP_WAIT))
 			goto nomem;
 

@@ -1175,18 +1176,20 @@ static void mem_cgroup_free(struct mem_c
 static struct cgroup_subsys_state *
 mem_cgroup_create(struct cgroup_subsys *ss, struct cgroup *cont)
 {
-	struct mem_cgroup *mem;
+	struct mem_cgroup *mem, *parent;
 	int node;
 
 	if (unlikely((cont->parent) == NULL)) {
 		mem = &init_mem_cgroup;
+		parent = NULL;
 	} else {
 		mem = mem_cgroup_alloc();
+		parent = mem_cgroup_from_cont(cont->parent);
 		if (!mem)
 			return ERR_PTR(-ENOMEM);
 	}
 
-	res_counter_init(&mem->res);
+	res_counter_init(&mem->res, parent ? &parent->res : NULL);
 
 	for_each_node_state(node, N_POSSIBLE)
 		if (alloc_mem_cgroup_per_zone_info(mem, node))

_

Signature · 6 lines

	Balbir
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 6 lines · On Sun, 02 Nov 2008 00:18:37 +0530 Balbir Singh <[email protected]>…

Add support for building hierarchies in resource counters. Cgroups allows us to build a deep hierarchy, but we currently don't link the resource counters belonging to the memory controller control groups, which are linked in cgroup hiearchy. This patch provides the infrastructure for resource counters that have the same hiearchy as their cgroup counter parts.

Quoted 8 lines

These set of patches are based on the resource counter hiearchy patches posted by Pavel Emelianov.

NOTE: Building hiearchies is expensive, deeper hierarchies imply charging the all the way up to the root. It is known that hiearchies are expensive, so the user needs to be careful and aware of the trade-offs before creating very deep ones.

...isn't it better to add "root_lock" to res_counter rather than taking all levels of lock one by one ?

spin_lock(&res_counter->hierarchy_root->lock);
do all charge/uncharge to hierarchy
spin_unlock(&res_counter->hierarchy_root->lock);

Hmm ?

Quoted 24 lines · KAMEZAWA Hiroyuki

Quoted 6 lines · On Sun, 02 Nov 2008 00:18:37 +0530 Balbir Singh <[email protected]>…

Add support for building hierarchies in resource counters. Cgroups allows us to build a deep hierarchy, but we currently don't link the resource counters belonging to the memory controller control groups, which are linked in cgroup hiearchy. This patch provides the infrastructure for resource counters that have the same hiearchy as their cgroup counter parts.

Quoted 8 lines

These set of patches are based on the resource counter hiearchy patches posted by Pavel Emelianov.

NOTE: Building hiearchies is expensive, deeper hierarchies imply charging the all the way up to the root. It is known that hiearchies are expensive, so the user needs to be careful and aware of the trade-offs before creating very deep ones.

...isn't it better to add "root_lock" to res_counter rather than taking all levels of lock one by one ?

spin_lock(&res_counter->hierarchy_root->lock);
do all charge/uncharge to hierarchy
spin_unlock(&res_counter->hierarchy_root->lock);

Quoted 2 lines

Hmm ?

Good thought process, but that affects and adds code complexity for the case when hierarchy is enabled/disabled. It is also inefficient, since all charges will now contend on root lock, in the current process, it is step by step, the contention only occurs on common parts of the hierarchy (root being the best case).

Quoted 27 lines · On Sun, 02 Nov 2008 11:19:38 +0530 Balbir Singh <[email protected]>…

Quoted 26 lines · KAMEZAWA Hiroyuki

Quoted 6 lines · On Sun, 02 Nov 2008 00:18:37 +0530 Balbir Singh <[email protected]>…

Add support for building hierarchies in resource counters. Cgroups allows us to build a deep hierarchy, but we currently don't link the resource counters belonging to the memory controller control groups, which are linked in cgroup hiearchy. This patch provides the infrastructure for resource counters that have the same hiearchy as their cgroup counter parts.

Quoted 8 lines

These set of patches are based on the resource counter hiearchy patches posted by Pavel Emelianov.

NOTE: Building hiearchies is expensive, deeper hierarchies imply charging the all the way up to the root. It is known that hiearchies are expensive, so the user needs to be careful and aware of the trade-offs before creating very deep ones.

...isn't it better to add "root_lock" to res_counter rather than taking all levels of lock one by one ?

spin_lock(&res_counter->hierarchy_root->lock);
do all charge/uncharge to hierarchy
spin_unlock(&res_counter->hierarchy_root->lock);

Hmm ?

Quoted 5 lines

Good thought process, but that affects and adds code complexity for the case when hierarchy is enabled/disabled. It is also inefficient, since all charges will now contend on root lock, in the current process, it is step by step, the contention only occurs on common parts of the hierarchy (root being the best case).

Above code's contention level is not different from "only root no children" case. Just inside-lock is heavier.

This patch introduces hierarchical reclaim. When an ancestor goes over its limit, the charging routine points to the parent that is above its limit. The reclaim process then starts from the last scanned child of the ancestor and reclaims until the ancestor goes below its limit.

Signed-off-by Balbir Singh <[email protected]>

---

 mm/memcontrol.c |  153 +++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 129 insertions(+), 24 deletions(-)

diff -puN mm/memcontrol.c~memcg-hierarchical-reclaim mm/memcontrol.c

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +63 -0

@@ -132,6 +132,11 @@ struct mem_cgroup {
 	 * statistics.
 	 */
 	struct mem_cgroup_stat stat;
+	/*
+	 * While reclaiming in a hiearchy, we cache the last child we
+	 * reclaimed from.
+	 */
+	struct mem_cgroup *last_scanned_child;
 };
 static struct mem_cgroup init_mem_cgroup;
 

@@ -467,6 +472,125 @@ unsigned long mem_cgroup_isolate_pages(u
 	return nr_taken;
 }
 
+static struct mem_cgroup *
+mem_cgroup_from_res_counter(struct res_counter *counter)
+{
+	return container_of(counter, struct mem_cgroup, res);
+}
+
+/*
+ * Dance down the hierarchy if needed to reclaim memory. We remember the
+ * last child we reclaimed from, so that we don't end up penalizing
+ * one child extensively based on its position in the children list
+ */
+static int
+mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem, gfp_t gfp_mask)
+{
+	struct cgroup *cg, *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	if (try_to_free_mem_cgroup_pages(mem, gfp_mask))
+		return -ENOMEM;
+
+	/*
+	 * try_to_free_mem_cgroup_pages() might not give us a full
+	 * picture of reclaim. Some pages are reclaimed and might be
+	 * moved to swap cache or just unmapped from the cgroup.
+	 * Check the limit again to see if the reclaim reduced the
+	 * current usage of the cgroup before giving up
+	 */
+	if (res_counter_check_under_limit(&mem->res))
+		return 0;
+
+	/*
+	 * Scan all children under the mem_cgroup mem
+	 */
+	if (!mem->last_scanned_child)
+		cgroup = list_first_entry(&mem->css.cgroup->children,
+				struct cgroup, sibling);
+	else
+		cgroup = mem->last_scanned_child->css.cgroup;
+
+	cg_current = cgroup;
+
+	/*
+	 * We iterate twice, one of it is fundamental list issue, where
+	 * the elements are inserted using list_add and hence the list
+	 * behaves like a stack and list_for_entry_safe_from() stops
+	 * after seeing the first child. The two loops help us work
+	 * independently of the insertion and it helps us get a full pass at
+	 * scanning all list entries for reclaim
+	 */
+	list_for_each_entry_safe_from(cgroup, cg, &cg_current->parent->children,
+						 sibling) {
+		mem_child = mem_cgroup_from_cont(cgroup);
+
+		/*
+		 * Move beyond last scanned child
+		 */
+		if (mem_child == mem->last_scanned_child)

Quoted 92 lines · On Sun, 02 Nov 2008 00:18:49 +0530 Balbir Singh <[email protected]>…

This patch introduces hierarchical reclaim. When an ancestor goes over its limit, the charging routine points to the parent that is above its limit. The reclaim process then starts from the last scanned child of the ancestor and reclaims until the ancestor goes below its limit.

Signed-off-by Balbir Singh <[email protected]>

---

 mm/memcontrol.c |  153 +++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 129 insertions(+), 24 deletions(-)

diff -puN mm/memcontrol.c~memcg-hierarchical-reclaim mm/memcontrol.c

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +67 -0

@@ -132,6 +132,11 @@ struct mem_cgroup {
 	 * statistics.
 	 */
 	struct mem_cgroup_stat stat;
+	/*
+	 * While reclaiming in a hiearchy, we cache the last child we
+	 * reclaimed from.
+	 */
+	struct mem_cgroup *last_scanned_child;
 };
 static struct mem_cgroup init_mem_cgroup;
 

@@ -467,6 +472,125 @@ unsigned long mem_cgroup_isolate_pages(u
 	return nr_taken;
 }
 
+static struct mem_cgroup *
+mem_cgroup_from_res_counter(struct res_counter *counter)
+{
+	return container_of(counter, struct mem_cgroup, res);
+}
+
+/*
+ * Dance down the hierarchy if needed to reclaim memory. We remember the
+ * last child we reclaimed from, so that we don't end up penalizing
+ * one child extensively based on its position in the children list
+ */
+static int
+mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem, gfp_t gfp_mask)
+{
+	struct cgroup *cg, *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	if (try_to_free_mem_cgroup_pages(mem, gfp_mask))
+		return -ENOMEM;
+
+	/*
+	 * try_to_free_mem_cgroup_pages() might not give us a full
+	 * picture of reclaim. Some pages are reclaimed and might be
+	 * moved to swap cache or just unmapped from the cgroup.
+	 * Check the limit again to see if the reclaim reduced the
+	 * current usage of the cgroup before giving up
+	 */
+	if (res_counter_check_under_limit(&mem->res))
+		return 0;
+
+	/*
+	 * Scan all children under the mem_cgroup mem
+	 */
+	if (!mem->last_scanned_child)
+		cgroup = list_first_entry(&mem->css.cgroup->children,
+				struct cgroup, sibling);
+	else
+		cgroup = mem->last_scanned_child->css.cgroup;
+
+	cg_current = cgroup;
+
+	/*
+	 * We iterate twice, one of it is fundamental list issue, where
+	 * the elements are inserted using list_add and hence the list
+	 * behaves like a stack and list_for_entry_safe_from() stops
+	 * after seeing the first child. The two loops help us work
+	 * independently of the insertion and it helps us get a full pass at
+	 * scanning all list entries for reclaim
+	 */
+	list_for_each_entry_safe_from(cgroup, cg, &cg_current->parent->children,
+						 sibling) {
+		mem_child = mem_cgroup_from_cont(cgroup);
+
+		/*
+		 * Move beyond last scanned child
+		 */
+		if (mem_child == mem->last_scanned_child)
+			continue;
+
+		ret = try_to_free_mem_cgroup_pages(mem_child, gfp_mask);
+		mem->last_scanned_child = mem_child;

mm/memcontrol.c unsigned long mem_cgroup_isolate_pages(u · line 542

Quoted 6 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +6 -0

+
+		if (res_counter_check_under_limit(&mem->res)) {
+			ret = 0;
+			goto done;
+		}
+	}

Is this safe against cgroup create/remove ? cgroup_mutex is held ?

Quoted 95 lines · KAMEZAWA Hiroyuki

Quoted 92 lines · On Sun, 02 Nov 2008 00:18:49 +0530 Balbir Singh <[email protected]>…

This patch introduces hierarchical reclaim. When an ancestor goes over its limit, the charging routine points to the parent that is above its limit. The reclaim process then starts from the last scanned child of the ancestor and reclaims until the ancestor goes below its limit.

Signed-off-by Balbir Singh <[email protected]>

---

 mm/memcontrol.c |  153 +++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 129 insertions(+), 24 deletions(-)

diff -puN mm/memcontrol.c~memcg-hierarchical-reclaim mm/memcontrol.c

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +67 -0

@@ -132,6 +132,11 @@ struct mem_cgroup {
 	 * statistics.
 	 */
 	struct mem_cgroup_stat stat;
+	/*
+	 * While reclaiming in a hiearchy, we cache the last child we
+	 * reclaimed from.
+	 */
+	struct mem_cgroup *last_scanned_child;
 };
 static struct mem_cgroup init_mem_cgroup;
 

@@ -467,6 +472,125 @@ unsigned long mem_cgroup_isolate_pages(u
 	return nr_taken;
 }
 
+static struct mem_cgroup *
+mem_cgroup_from_res_counter(struct res_counter *counter)
+{
+	return container_of(counter, struct mem_cgroup, res);
+}
+
+/*
+ * Dance down the hierarchy if needed to reclaim memory. We remember the
+ * last child we reclaimed from, so that we don't end up penalizing
+ * one child extensively based on its position in the children list
+ */
+static int
+mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem, gfp_t gfp_mask)
+{
+	struct cgroup *cg, *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	if (try_to_free_mem_cgroup_pages(mem, gfp_mask))
+		return -ENOMEM;
+
+	/*
+	 * try_to_free_mem_cgroup_pages() might not give us a full
+	 * picture of reclaim. Some pages are reclaimed and might be
+	 * moved to swap cache or just unmapped from the cgroup.
+	 * Check the limit again to see if the reclaim reduced the
+	 * current usage of the cgroup before giving up
+	 */
+	if (res_counter_check_under_limit(&mem->res))
+		return 0;
+
+	/*
+	 * Scan all children under the mem_cgroup mem
+	 */
+	if (!mem->last_scanned_child)
+		cgroup = list_first_entry(&mem->css.cgroup->children,
+				struct cgroup, sibling);
+	else
+		cgroup = mem->last_scanned_child->css.cgroup;
+
+	cg_current = cgroup;
+
+	/*
+	 * We iterate twice, one of it is fundamental list issue, where
+	 * the elements are inserted using list_add and hence the list
+	 * behaves like a stack and list_for_entry_safe_from() stops
+	 * after seeing the first child. The two loops help us work
+	 * independently of the insertion and it helps us get a full pass at
+	 * scanning all list entries for reclaim
+	 */
+	list_for_each_entry_safe_from(cgroup, cg, &cg_current->parent->children,
+						 sibling) {
+		mem_child = mem_cgroup_from_cont(cgroup);
+
+		/*
+		 * Move beyond last scanned child
+		 */
+		if (mem_child == mem->last_scanned_child)
+			continue;
+
+		ret = try_to_free_mem_cgroup_pages(mem_child, gfp_mask);
+		mem->last_scanned_child = mem_child;

Quoted 8 lines

mm/memcontrol.c unsigned long mem_cgroup_isolate_pages(u · line 542

Quoted 6 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +6 -0

+
+		if (res_counter_check_under_limit(&mem->res)) {
+			ret = 0;
+			goto done;
+		}
+	}

Is this safe against cgroup create/remove ? cgroup_mutex is held ?

Yes, I thought about it, but with the setup, each parent will be busy since they have children and hence cannot be removed. The leaf child itself has tasks, so it cannot be removed. IOW, it should be safe against removal.

Quoted 103 lines · On Sun, 02 Nov 2008 11:14:48 +0530 Balbir Singh <[email protected]>…

Quoted 94 lines · KAMEZAWA Hiroyuki

Quoted 91 lines · On Sun, 02 Nov 2008 00:18:49 +0530 Balbir Singh <[email protected]>…

This patch introduces hierarchical reclaim. When an ancestor goes over its limit, the charging routine points to the parent that is above its limit. The reclaim process then starts from the last scanned child of the ancestor and reclaims until the ancestor goes below its limit.

Signed-off-by Balbir Singh <[email protected]>

---

 mm/memcontrol.c |  153 +++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 129 insertions(+), 24 deletions(-)

diff -puN mm/memcontrol.c~memcg-hierarchical-reclaim mm/memcontrol.c

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +66 -0

@@ -132,6 +132,11 @@ struct mem_cgroup {
 	 * statistics.
 	 */
 	struct mem_cgroup_stat stat;
+	/*
+	 * While reclaiming in a hiearchy, we cache the last child we
+	 * reclaimed from.
+	 */
+	struct mem_cgroup *last_scanned_child;
 };
 static struct mem_cgroup init_mem_cgroup;
 

@@ -467,6 +472,125 @@ unsigned long mem_cgroup_isolate_pages(u
 	return nr_taken;
 }
 
+static struct mem_cgroup *
+mem_cgroup_from_res_counter(struct res_counter *counter)
+{
+	return container_of(counter, struct mem_cgroup, res);
+}
+
+/*
+ * Dance down the hierarchy if needed to reclaim memory. We remember the
+ * last child we reclaimed from, so that we don't end up penalizing
+ * one child extensively based on its position in the children list
+ */
+static int
+mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem, gfp_t gfp_mask)
+{
+	struct cgroup *cg, *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	if (try_to_free_mem_cgroup_pages(mem, gfp_mask))
+		return -ENOMEM;
+
+	/*
+	 * try_to_free_mem_cgroup_pages() might not give us a full
+	 * picture of reclaim. Some pages are reclaimed and might be
+	 * moved to swap cache or just unmapped from the cgroup.
+	 * Check the limit again to see if the reclaim reduced the
+	 * current usage of the cgroup before giving up
+	 */
+	if (res_counter_check_under_limit(&mem->res))
+		return 0;
+
+	/*
+	 * Scan all children under the mem_cgroup mem
+	 */
+	if (!mem->last_scanned_child)
+		cgroup = list_first_entry(&mem->css.cgroup->children,
+				struct cgroup, sibling);
+	else
+		cgroup = mem->last_scanned_child->css.cgroup;
+
+	cg_current = cgroup;
+
+	/*
+	 * We iterate twice, one of it is fundamental list issue, where
+	 * the elements are inserted using list_add and hence the list
+	 * behaves like a stack and list_for_entry_safe_from() stops
+	 * after seeing the first child. The two loops help us work
+	 * independently of the insertion and it helps us get a full pass at
+	 * scanning all list entries for reclaim
+	 */
+	list_for_each_entry_safe_from(cgroup, cg, &cg_current->parent->children,
+						 sibling) {
+		mem_child = mem_cgroup_from_cont(cgroup);
+
+		/*
+		 * Move beyond last scanned child
+		 */
+		if (mem_child == mem->last_scanned_child)
+			continue;
+
+		ret = try_to_free_mem_cgroup_pages(mem_child, gfp_mask);

Quoted 8 lines

mm/memcontrol.c unsigned long mem_cgroup_isolate_pages(u · line 542

Quoted 7 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +7 -0

+		mem->last_scanned_child = mem_child;
+
+		if (res_counter_check_under_limit(&mem->res)) {
+			ret = 0;
+			goto done;
+		}
+	}

Is this safe against cgroup create/remove ? cgroup_mutex is held ?

Quoted 4 lines

Yes, I thought about it, but with the setup, each parent will be busy since they have children and hence cannot be removed. The leaf child itself has tasks, so it cannot be removed. IOW, it should be safe against removal.

I'm sorry if I misunderstand something. could you explain folloing ?

In following tree,

level-1
- level-2
- level-3
- level-4
level-1's usage = level-1 + level-2 + level-3 + level-4 level-2's usage = level-2 + level-3 + level-4 level-3's usage = level-3 + level-4
level-4's usage = level-4

Assume that a task in level-2 hits its limit. It has to reclaim memory from level-2 and level-3, level-4.

How can we guarantee level-4 has a task in this case ?

Quoted 43 lines

Quoted 20 lines

Quoted 12 lines

Quoted 12 lines

(quoted diff) +1 -0

+	list_for_each_entry_safe_from(cgroup, cg,

&cg_current->parent->children,

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +10 -0

+						 sibling) {
+		mem_child = mem_cgroup_from_cont(cgroup);
+
+		/*
+		 * Move beyond last scanned child
+		 */
+		if (mem_child == mem->last_scanned_child)
+			continue;
+
+		ret = try_to_free_mem_cgroup_pages(mem_child, gfp_mask);

Quoted 8 lines

mm/memcontrol.c unsigned long mem_cgroup_isolate_pages(u · line 542

Quoted 7 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +7 -0

+		mem->last_scanned_child = mem_child;
+
+		if (res_counter_check_under_limit(&mem->res)) {
+			ret = 0;
+			goto done;
+		}
+	}

Is this safe against cgroup create/remove ? cgroup_mutex is held ?

Quoted 6 lines

Yes, I thought about it, but with the setup, each parent will be busy since they
have children and hence cannot be removed. The leaf child itself has tasks, so
it cannot be removed. IOW, it should be safe against removal.

I'm sorry if I misunderstand something. could you explain folloing ?

In following tree,

level-1
- level-2
- level-3
- level-4
level-1's usage = level-1 + level-2 + level-3 + level-4 level-2's usage = level-2 + level-3 + level-4 level-3's usage = level-3 + level-4
level-4's usage = level-4

Assume that a task in level-2 hits its limit. It has to reclaim memory from
level-2 and level-3, level-4.

Quoted 1 line

How can we guarantee level-4 has a task in this case ?

Good question. If there is no task, the LRU's will be empty and reclaim will
return. We could also add other checks if needed.

Quoted 39 lines · Balbir Singh

Quoted 39 lines

Quoted 20 lines

Quoted 12 lines

Quoted 12 lines

(quoted diff) +1 -0

+	list_for_each_entry_safe_from(cgroup, cg,

&cg_current->parent->children,

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +10 -0

+						 sibling) {
+		mem_child = mem_cgroup_from_cont(cgroup);
+
+		/*
+		 * Move beyond last scanned child
+		 */
+		if (mem_child == mem->last_scanned_child)
+			continue;
+
+		ret = try_to_free_mem_cgroup_pages(mem_child, gfp_mask);

Quoted 8 lines

mm/memcontrol.c unsigned long mem_cgroup_isolate_pages(u · line 542

Quoted 7 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-hierarchical-reclaim +7 -0

+		mem->last_scanned_child = mem_child;
+
+		if (res_counter_check_under_limit(&mem->res)) {
+			ret = 0;
+			goto done;
+		}
+	}

Is this safe against cgroup create/remove ? cgroup_mutex is held ?

Quoted 6 lines

Yes, I thought about it, but with the setup, each parent will be busy since they
have children and hence cannot be removed. The leaf child itself has tasks, so
it cannot be removed. IOW, it should be safe against removal.

I'm sorry if I misunderstand something. could you explain folloing ?

In following tree,

level-1
- level-2
- level-3
- level-4
level-1's usage = level-1 + level-2 + level-3 + level-4 level-2's usage = level-2 + level-3 + level-4 level-3's usage = level-3 + level-4
level-4's usage = level-4

Quoted 9 lines

Quoted 5 lines

Assume that a task in level-2 hits its limit. It has to reclaim memory from
level-2 and level-3, level-4.

How can we guarantee level-4 has a task in this case ?

Good question. If there is no task, the LRU's will be empty and reclaim will
return. We could also add other checks if needed.

If needed ?, yes, you need.
The problem is that you are walking a list in usual way without any lock or guarantee that the list will never be modified.

My quick idea is following.
==
Before start reclaim.
1. take lock_cgroup()
2. scan the tree and create "private" list as snapshot of tree to be scanned.

Don't enable multiple hierarchy support by default. This patch introduces a features element that can be set to enable the nested depth hierarchy feature. This feature can only be enabled when there is just one cgroup (the root cgroup).

Signed-off-by Balbir Singh <[email protected]>

---

 mm/memcontrol.c |   38 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 37 insertions(+), 1 deletion(-)

diff -puN mm/memcontrol.c~memcg-add-hierarchy-selector mm/memcontrol.c

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-add-hierarchy-selector +37 -1

@@ -40,6 +40,9 @@
 struct cgroup_subsys mem_cgroup_subsys __read_mostly;
 #define MEM_CGROUP_RECLAIM_RETRIES	5
 
+static unsigned long mem_cgroup_features;
+#define MEM_CGROUP_FEAT_HIERARCHY	0x1
+
 /*
  * Statistics for memory cgroup.
  */

@@ -1080,6 +1083,31 @@ out:
 	return ret;
 }
 
+static u64 mem_cgroup_feature_read(struct cgroup *cont, struct cftype *cft)
+{
+	return mem_cgroup_features;
+}
+
+static int mem_cgroup_feature_write(struct cgroup *cont, struct cftype *cft,
+			    		u64 val)
+{
+	int retval = 0;
+	struct cgroup *cgroup = init_mem_cgroup.css.cgroup;
+
+	if (val & MEM_CGROUP_FEAT_HIERARCHY) {
+		if (list_empty(&cgroup->children))
+			mem_cgroup_features |= MEM_CGROUP_FEAT_HIERARCHY;
+		else
+			retval = -EBUSY;
+	} else {
+		if (list_empty(&cgroup->children))
+			mem_cgroup_features &= ~MEM_CGROUP_FEAT_HIERARCHY;
+		else
+			retval = -EBUSY;
+	}
+	return retval;
+}
+
 static u64 mem_cgroup_read(struct cgroup *cont, struct cftype *cft)
 {
 	return res_counter_read_u64(&mem_cgroup_from_cont(cont)->res,

@@ -1214,6 +1242,11 @@ static struct cftype mem_cgroup_files[] 
 		.name = "stat",
 		.read_map = mem_control_stat_show,
 	},
+	{
+		.name = "features",
+		.write_u64 = mem_cgroup_feature_write,
+		.read_u64 = mem_cgroup_feature_read,
+	},
 };
 
 static int alloc_mem_cgroup_per_zone_info(struct mem_cgroup *mem, int node)

@@ -1292,7 +1325,10 @@ mem_cgroup_create(struct cgroup_subsys *
 			return ERR_PTR(-ENOMEM);
 	}
 
-	res_counter_init(&mem->res, parent ? &parent->res : NULL);
+	if ((mem_cgroup_features & MEM_CGROUP_FEAT_HIERARCHY) && parent)
+		res_counter_init(&mem->res, &parent->res);
+	else
+		res_counter_init(&mem->res, NULL);
 
 	for_each_node_state(node, N_POSSIBLE)
 		if (alloc_mem_cgroup_per_zone_info(mem, node))

_

Signature · 1 line

	Balbir

Quoted 5 lines · On Sun, 02 Nov 2008 00:19:02 +0530 Balbir Singh <[email protected]>…

Don't enable multiple hierarchy support by default. This patch introduces a features element that can be set to enable the nested depth hierarchy feature. This feature can only be enabled when there is just one cgroup (the root cgroup).

Why the flag is for the whole system ?
flag-per-subtree is of no use ?

Quoted 8 lines · KAMEZAWA Hiroyuki

Quoted 5 lines · On Sun, 02 Nov 2008 00:19:02 +0530 Balbir Singh <[email protected]>…

Don't enable multiple hierarchy support by default. This patch introduces a features element that can be set to enable the nested depth hierarchy feature. This feature can only be enabled when there is just one cgroup (the root cgroup).

Quoted 2 lines

Why the flag is for the whole system ?
flag-per-subtree is of no use ?

Flag per subtree might not be useful, since we charge all the way up to root,

Quoted 11 lines · On Sun, 02 Nov 2008 11:33:51 +0530 Balbir Singh <[email protected]>…

Quoted 10 lines · KAMEZAWA Hiroyuki

Quoted 5 lines · On Sun, 02 Nov 2008 00:19:02 +0530 Balbir Singh <[email protected]>…

Don't enable multiple hierarchy support by default. This patch introduces a features element that can be set to enable the nested depth hierarchy feature. This feature can only be enabled when there is just one cgroup (the root cgroup).

Why the flag is for the whole system ?
flag-per-subtree is of no use ?

Quoted 1 line

Flag per subtree might not be useful, since we charge all the way up to root,

Ah, what I said is "How about enabling/disabling hierarhcy support per subtree ?" Sorry for bad text.

like this.
- you can set hierarchy mode of a cgroup turned on/off when...
* you don't have any tasks under it && it doesn't have any child cgroup.

That should not be hard, but having it per-subtree sounds a little complex in terms of exploiting from the end-user perspective and from symmetry perspective (the CPU cgroup controller provides hierarchy control for the full hierarchy).

Quoted 4 lines · Balbir Singh

That should not be hard, but having it per-subtree sounds a little complex in terms of exploiting from the end-user perspective and from symmetry perspective (the CPU cgroup controller provides hierarchy control for the full hierarchy).

The difference is that the CPU controller works in terms of shares, whereas memory works in terms of absolute memory size. So it pretty much has to limit the hierarchy to a single tree. Also, I didn't think that you could modify the shares for the root cgroup - what would that mean if so?

With this patch set as it is now, the root cgroup's lock becomes a global memory allocation/deallocation lock, which seems a bit painful.

Having a bunch of top-level cgroups each with their own independent memory limits, and allowing sub cgroups of them to be constrained by the parent's memory limit, seems more useful than a single hierarchy connected at the root.

In what realistic circumstances do you actually want to limit the root cgroup's memory usage?

Quoted 11 lines · Paul Menage

Quoted 4 lines · Balbir Singh

That should not be hard, but having it per-subtree sounds a little complex in terms of exploiting from the end-user perspective and from symmetry perspective (the CPU cgroup controller provides hierarchy control for the full hierarchy).

The difference is that the CPU controller works in terms of shares, whereas memory works in terms of absolute memory size. So it pretty much has to limit the hierarchy to a single tree. Also, I didn't think that you could modify the shares for the root cgroup - what would that mean if so?

The shares are proportional for the CPU controller. I am confused as to which shares (CPU you are talking about?

Quoted 2 lines

With this patch set as it is now, the root cgroup's lock becomes a global memory allocation/deallocation lock, which seems a bit painful.

Yes, true, but then that is the cost associated with using a hierarchy.

Quoted 4 lines

Having a bunch of top-level cgroups each with their own independent memory limits, and allowing sub cgroups of them to be constrained by the parent's memory limit, seems more useful than a single hierarchy connected at the root.

That is certainly do-able, but can be confusing to users, given how other controllers work. We can document that

Quoted 3 lines

In what realistic circumstances do you actually want to limit the root cgroup's memory usage?

Good point, I would expect that people would mostly use the hierarchy with soft-limits or shares. I am now beginning to like Kamezawa and your suggestion of limiting usage to subtrees.

Quoted 11 lines · On Sun, 02 Nov 2008 11:33:51 +0530 Balbir Singh <[email protected]>…

Quoted 10 lines · KAMEZAWA Hiroyuki

Quoted 5 lines · On Sun, 02 Nov 2008 00:19:02 +0530 Balbir Singh <[email protected]>…

Don't enable multiple hierarchy support by default. This patch introduces a features element that can be set to enable the nested depth hierarchy feature. This feature can only be enabled when there is just one cgroup (the root cgroup).

Why the flag is for the whole system ?
flag-per-subtree is of no use ?

Quoted 1 line

Flag per subtree might not be useful, since we charge all the way up to root,

Ah, what I said is "How about enabling/disabling hierarhcy support per subtree ?" Sorry for bad text.

like this.
- you can set hierarchy mode of a cgroup turned on/off when...
* you don't have any tasks under it && it doesn't have any child cgroup.

Quoted 18 lines · KAMEZAWA Hiroyuki

Quoted 4 lines · On Sun, 02 Nov 2008 11:33:51 +0530 Balbir Singh <[email protected]>…

Quoted 3 lines · KAMEZAWA Hiroyuki

On Sun, 02 Nov 2008 00:19:02 +0530
Balbir Singh <[email protected]> wrote:

Quoted 8 lines

Quoted 7 lines

Quoted 5 lines

Don't enable multiple hierarchy support by default. This patch introduces a features element that can be set to enable the nested depth hierarchy feature. This feature can only be enabled when there is just one cgroup (the root cgroup).

Why the flag is for the whole system ?
flag-per-subtree is of no use ?

Flag per subtree might not be useful, since we charge all the way up to root,

Ah, what I said is "How about enabling/disabling hierarhcy support per subtree ?" Sorry for bad text.

Quoted 3 lines

like this.
- you can set hierarchy mode of a cgroup turned on/off when...
* you don't have any tasks under it && it doesn't have any child cgroup.

I see.. the presence of tasks don't matter, since the root cgroup will always have tasks. Presence of child groups does matter.

This patch follows several iterations of the memory controller hierarchy patches. The hardwall approach by Kamezawa-San[1]. Version 1 of this patchset at [2].

The current approach is based on [2] and has the following properties

1. Hierarchies are very natural in a filesystem like the cgroup filesystem. A multi-tree hierarchy has been supported for a long time in filesystems. When the feature is turned on, we honor hierarchies such that the root accounts for resource usage of all children and limits can be set at any point in the hierarchy. Any memory cgroup is limited by limits along the hierarchy. The total usage of all children of a node cannot exceed the limit of the node.
2. The hierarchy feature is selectable and off by default
3. Hierarchies are expensive and the trade off is depth versus performance. Hierarchies can also be completely turned off.

The patches are against 2.6.28-rc2-mm1 and were tested in a KVM instance with SMP and swap turned on.

Quoted 17 lines · On Sun, 02 Nov 2008 00:18:12 +0530 Balbir Singh <[email protected]>…

This patch follows several iterations of the memory controller hierarchy patches. The hardwall approach by Kamezawa-San[1]. Version 1 of this patchset at [2].

The current approach is based on [2] and has the following properties

1. Hierarchies are very natural in a filesystem like the cgroup filesystem. A multi-tree hierarchy has been supported for a long time in filesystems. When the feature is turned on, we honor hierarchies such that the root accounts for resource usage of all children and limits can be set at any point in the hierarchy. Any memory cgroup is limited by limits along the hierarchy. The total usage of all children of a node cannot exceed the limit of the node.
2. The hierarchy feature is selectable and off by default
3. Hierarchies are expensive and the trade off is depth versus performance. Hierarchies can also be completely turned off.

Quoted 3 lines

The patches are against 2.6.28-rc2-mm1 and were tested in a KVM instance with SMP and swap turned on.

As first impression, I think hierarchical LRU management is not good...means not fair from viewpoint of memory management.

I'd like to show some other possible implementation of try_to_free_mem_cgroup_pages() if I can.

Anyway, I have to merge this with mem+swap controller.

Quoted 5 lines · KAMEZAWA Hiroyuki

On Sun, 02 Nov 2008 00:18:12 +0530
Balbir Singh <[email protected]> wrote:
As first impression, I think hierarchical LRU management is not good...means
not fair from viewpoint of memory management.

Could you elaborate on this further? Is scanning of children during reclaim the
issue? Do you want weighted reclaim for each of the children?

Quoted 3 lines

I'd like to show some other possible implementation of try_to_free_mem_cgroup_pages() if I can.

Elaborate please!

Quoted 1 line

Anyway, I have to merge this with mem+swap controller.

Cool! I'll send you an updated version.

Quoted 10 lines · Balbir Singh

Quoted 5 lines · KAMEZAWA Hiroyuki

On Sun, 02 Nov 2008 00:18:12 +0530
Balbir Singh <[email protected]> wrote:
As first impression, I think hierarchical LRU management is not good...means
not fair from viewpoint of memory management.

Could you elaborate on this further? Is scanning of children during reclaim the
issue? Do you want weighted reclaim for each of the children?

No. Consider follwing case
/root/group_root/group_A
/group_B
/group_C

sum of group A, B, C is limited by group_root's limit.

Now,
/group_root limit=1G, usage=990M
/group_A usage=600M , no limit, no tasks for a while /group_B usage=10M , no limit, no tasks /group_C usage=380M , no limit, 2 tasks

A user run a new task in group_B.
In your algorithm, group_A and B and C's memory are reclaimed to the same extent becasue there is no information to show "group A's memory are not accessed recently rather than B or C".

This information is what we want for managing memory.

Quoted 5 lines

Quoted 3 lines

I'd like to show some other possible implementation of try_to_free_mem_cgroup_pages() if I can.

Elaborate please!

ok. but, at least, please add
- per-subtree hierarchy flag.
- cgroup_lock to walk list of cgroups somewhere.

I already sent my version "shared LRU" just as a hint for you. It is something extreme but contains something good, I think.

Quoted 3 lines

Quoted 1 line

Anyway, I have to merge this with mem+swap controller.

Cool! I'll send you an updated version.

Synchronized LRU patch may help you.

Quoted 6 lines

Now,
/group_root limit=1G, usage=990M
/group_A usage=600M , no limit, no tasks for a while /group_B usage=10M , no limit, no tasks /group_C usage=380M , no limit, 2 tasks

Quoted 7 lines

A user run a new task in group_B.
In your algorithm, group_A and B and C's memory are reclaimed to the same extent becasue there is no information to show "group A's memory are not accessed recently rather than B or C".

This information is what we want for managing memory.

For that sort of implementation, we'll need a common LRU. I actually thought of implementing it by sharing a common LRU, but then we would end up with just one common LRU at the root :)

The reclaim algorithm is smart in that it knows what pages are commonly accessed. group A will get reclaimed more since those pages are not actively referenced. reclaim on group_C will be harder.

Simple experiments seem to show that.

Quoted 12 lines

Quoted 5 lines

Quoted 3 lines

I'd like to show some other possible implementation of try_to_free_mem_cgroup_pages() if I can.

Elaborate please!

ok. but, at least, please add
- per-subtree hierarchy flag.
- cgroup_lock to walk list of cgroups somewhere.

I already sent my version "shared LRU" just as a hint for you. It is something extreme but contains something good, I think.

Quoted 5 lines

Quoted 3 lines

Quoted 1 line

Anyway, I have to merge this with mem+swap controller.

Cool! I'll send you an updated version.

Synchronized LRU patch may help you.

Let me get a good working version against current -mm and then we'll integrate our patches.