Memory cgroup hierarchy introduction (v3)

mm/memcontrol.c static int mem_cgroup_force_empty(struct · line 1075

Quoted 10 lines · On Tue, 11 Nov 2008 18:04:17 +0530 Balbir Singh <[email protected]>…

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

+
+		/*
+		 * We need to give up the cgroup lock if it is held, since
+		 * it creates the potential for deadlock. cgroup_mutex should
+		 * be acquired after cpu_hotplug lock. In this path, we
+		 * acquire the cpu_hotplug lock after acquiring the cgroup_mutex
+		 * Giving it up should be OK
+		 */
+		if (cgroup_locked)
+			cgroup_unlock();

nice catch. I'll post a fix to this as its own patch.

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.

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

+/*
+ * 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.
+ *
+ * root_mem is the original ancestor that we've been reclaim from.
+ */
+static int mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem,
+						struct mem_cgroup *root_mem,
+						gfp_t gfp_mask)
+{
+	struct cgroup *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	/*
+	 * Reclaim unconditionally and don't check for return value.
+	 * We need to reclaim in the current group and down the tree.
+	 * One might think about checking for children before reclaiming,
+	 * but there might be left over accounting, even after children
+	 * have left.
+	 */
+	try_to_free_mem_cgroup_pages(mem, gfp_mask);
+
+	if (res_counter_check_under_limit(&root_mem->res))
+		return 0;
+
+	cgroup_lock();
+
+	if (list_empty(&mem->css.cgroup->children)) {
+		cgroup_unlock();
+		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;
+
+	do {
+		struct list_head *next;
+
+		mem_child = mem_cgroup_from_cont(cgroup);
+		cgroup_unlock();
+
+		ret = mem_cgroup_hierarchical_reclaim(mem_child, root_mem,
+							gfp_mask);
+		cgroup_lock();
+		mem->last_scanned_child = mem_child;
+		if (res_counter_check_under_limit(&root_mem->res)) {
+			ret = 0;
+			goto done;
+		}
+
+		/*
+		 * Since we gave up the lock, it is time to
+		 * start from last cgroup
+		 */
+		cgroup = mem->last_scanned_child->css.cgroup;
+		next = cgroup->sibling.next;
+
+		if (next == &cg_current->parent->children)

Quoted 74 lines · On Tue, 11 Nov 2008 18:04:17 +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.

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

+/*
+ * 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.
+ *
+ * root_mem is the original ancestor that we've been reclaim from.
+ */
+static int mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem,
+						struct mem_cgroup *root_mem,
+						gfp_t gfp_mask)
+{
+	struct cgroup *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	/*
+	 * Reclaim unconditionally and don't check for return value.
+	 * We need to reclaim in the current group and down the tree.
+	 * One might think about checking for children before reclaiming,
+	 * but there might be left over accounting, even after children
+	 * have left.
+	 */
+	try_to_free_mem_cgroup_pages(mem, gfp_mask);
+
+	if (res_counter_check_under_limit(&root_mem->res))
+		return 0;
+
+	cgroup_lock();
+
+	if (list_empty(&mem->css.cgroup->children)) {
+		cgroup_unlock();
+		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;
+
+	do {
+		struct list_head *next;
+
+		mem_child = mem_cgroup_from_cont(cgroup);
+		cgroup_unlock();
+
+		ret = mem_cgroup_hierarchical_reclaim(mem_child, root_mem,
+							gfp_mask);
+		cgroup_lock();
+		mem->last_scanned_child = mem_child;
+		if (res_counter_check_under_limit(&root_mem->res)) {
+			ret = 0;
+			goto done;
+		}
+
+		/*
+		 * Since we gave up the lock, it is time to
+		 * start from last cgroup
+		 */
+		cgroup = mem->last_scanned_child->css.cgroup;
+		next = cgroup->sibling.next;
+
+		if (next == &cg_current->parent->children)

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

Quoted 10 lines

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

+			cgroup = list_first_entry(&mem->css.cgroup->children,
+							struct cgroup, sibling);
+		else
+			cgroup = container_of(next, struct cgroup, sibling);
+	} while (cgroup != cg_current);
+
+done:
+	cgroup_unlock();
+	return ret;
+}

Hmm, does this function is necessary to be complex as this ?
I'm sorry I don't have enough time to review now. (chasing memory online/offline bug.)

But I can't convice this is a good way to reclaim in hierachical manner.

In following tree, Assume that processes hit limitation of Level_2.

   Level_1 (no limit)
	-> Level_2	(limit=1G)
		-> Level_3_A (usage=30M)
		-> Level_3_B (usage=100M)
			-> Level_4_A (usage=50M)
			-> Level_4_B (usage=400M)
			-> Level_4_C (usage=420M)

Even if we know Level_4_C incudes tons of Inactive file caches, some amount of swap-out will occur until reachin Level_4_C.

Can't we do this hierarchical reclaim in another way ? (start from Level_4_C because we know it has tons of inactive caches.)

This style of recursive call doesn't have chance to do kind of optimization. Can we do this reclaim in more flat manner as loop like following =
try:
select the most inactive one

	-> try_to_fre_memory
		-> check limit
			-> go to try;

==

Quoted 114 lines · KAMEZAWA Hiroyuki

Quoted 74 lines · On Tue, 11 Nov 2008 18:04:17 +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.

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

+/*
+ * 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.
+ *
+ * root_mem is the original ancestor that we've been reclaim from.
+ */
+static int mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem,
+						struct mem_cgroup *root_mem,
+						gfp_t gfp_mask)
+{
+	struct cgroup *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	/*
+	 * Reclaim unconditionally and don't check for return value.
+	 * We need to reclaim in the current group and down the tree.
+	 * One might think about checking for children before reclaiming,
+	 * but there might be left over accounting, even after children
+	 * have left.
+	 */
+	try_to_free_mem_cgroup_pages(mem, gfp_mask);
+
+	if (res_counter_check_under_limit(&root_mem->res))
+		return 0;
+
+	cgroup_lock();
+
+	if (list_empty(&mem->css.cgroup->children)) {
+		cgroup_unlock();
+		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;
+
+	do {
+		struct list_head *next;
+
+		mem_child = mem_cgroup_from_cont(cgroup);
+		cgroup_unlock();
+
+		ret = mem_cgroup_hierarchical_reclaim(mem_child, root_mem,
+							gfp_mask);
+		cgroup_lock();
+		mem->last_scanned_child = mem_child;
+		if (res_counter_check_under_limit(&root_mem->res)) {
+			ret = 0;
+			goto done;
+		}
+
+		/*
+		 * Since we gave up the lock, it is time to
+		 * start from last cgroup
+		 */
+		cgroup = mem->last_scanned_child->css.cgroup;
+		next = cgroup->sibling.next;
+
+		if (next == &cg_current->parent->children)

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

Quoted 10 lines

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

+			cgroup = list_first_entry(&mem->css.cgroup->children,
+							struct cgroup, sibling);
+		else
+			cgroup = container_of(next, struct cgroup, sibling);
+	} while (cgroup != cg_current);
+
+done:
+	cgroup_unlock();
+	return ret;
+}

Hmm, does this function is necessary to be complex as this ?
I'm sorry I don't have enough time to review now. (chasing memory online/offline bug.)

But I can't convice this is a good way to reclaim in hierachical manner.

In following tree, Assume that processes hit limitation of Level_2.

   Level_1 (no limit)
	-> Level_2	(limit=1G)
		-> Level_3_A (usage=30M)
		-> Level_3_B (usage=100M)
			-> Level_4_A (usage=50M)
			-> Level_4_B (usage=400M)
			-> Level_4_C (usage=420M)

Even if we know Level_4_C incudes tons of Inactive file caches, some amount of swap-out will occur until reachin Level_4_C.

Can't we do this hierarchical reclaim in another way ? (start from Level_4_C because we know it has tons of inactive caches.)

This style of recursive call doesn't have chance to do kind of optimization. Can we do this reclaim in more flat manner as loop like following =
try:
select the most inactive one

Quoted 5 lines

	-> try_to_fre_memory
		-> check limit
			-> go to try;

==

I've been thinking along those lines as well and that will get more important as we try to implement soft limits. However, for the current version I wanted correctness. Fairness, I've seen is achieved, since groups with large number of inactive pages, does get reclaimed from more than others (in my simple experiments).

As far the pseudo code is concerned, select the most inactive one is an O(c) operation, where c is the number of nodes under the subtree and is expensive. The data structure and select algorithm get expensive. I am thinking about a more suitable approach for implementation, but I want to focus on correctness as the first step. Since the hierarchy is not enabled by default, I am not adding any additional overhead, so I think that this approach is suitable.

Quoted 124 lines · On Wed, 12 Nov 2008 11:19:37 +0530 Balbir Singh <[email protected]>…

Quoted 112 lines · KAMEZAWA Hiroyuki

Quoted 73 lines · On Tue, 11 Nov 2008 18:04:17 +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.

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

+/*
+ * 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.
+ *
+ * root_mem is the original ancestor that we've been reclaim from.
+ */
+static int mem_cgroup_hierarchical_reclaim(struct mem_cgroup *mem,
+						struct mem_cgroup *root_mem,
+						gfp_t gfp_mask)
+{
+	struct cgroup *cg_current, *cgroup;
+	struct mem_cgroup *mem_child;
+	int ret = 0;
+
+	/*
+	 * Reclaim unconditionally and don't check for return value.
+	 * We need to reclaim in the current group and down the tree.
+	 * One might think about checking for children before reclaiming,
+	 * but there might be left over accounting, even after children
+	 * have left.
+	 */
+	try_to_free_mem_cgroup_pages(mem, gfp_mask);
+
+	if (res_counter_check_under_limit(&root_mem->res))
+		return 0;
+
+	cgroup_lock();
+
+	if (list_empty(&mem->css.cgroup->children)) {
+		cgroup_unlock();
+		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;
+
+	do {
+		struct list_head *next;
+
+		mem_child = mem_cgroup_from_cont(cgroup);
+		cgroup_unlock();
+
+		ret = mem_cgroup_hierarchical_reclaim(mem_child, root_mem,
+							gfp_mask);
+		cgroup_lock();
+		mem->last_scanned_child = mem_child;
+		if (res_counter_check_under_limit(&root_mem->res)) {
+			ret = 0;
+			goto done;
+		}
+
+		/*
+		 * Since we gave up the lock, it is time to
+		 * start from last cgroup
+		 */
+		cgroup = mem->last_scanned_child->css.cgroup;
+		next = cgroup->sibling.next;
+
+		if (next == &cg_current->parent->children)

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

Quoted 10 lines

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

+			cgroup = list_first_entry(&mem->css.cgroup->children,
+							struct cgroup, sibling);
+		else
+			cgroup = container_of(next, struct cgroup, sibling);
+	} while (cgroup != cg_current);
+
+done:
+	cgroup_unlock();
+	return ret;
+}

Hmm, does this function is necessary to be complex as this ?
I'm sorry I don't have enough time to review now. (chasing memory online/offline bug.)

But I can't convice this is a good way to reclaim in hierachical manner.

In following tree, Assume that processes hit limitation of Level_2.

   Level_1 (no limit)
	-> Level_2	(limit=1G)
		-> Level_3_A (usage=30M)
		-> Level_3_B (usage=100M)
			-> Level_4_A (usage=50M)
			-> Level_4_B (usage=400M)
			-> Level_4_C (usage=420M)

Even if we know Level_4_C incudes tons of Inactive file caches, some amount of swap-out will occur until reachin Level_4_C.

Can't we do this hierarchical reclaim in another way ? (start from Level_4_C because we know it has tons of inactive caches.)

This style of recursive call doesn't have chance to do kind of optimization. Can we do this reclaim in more flat manner as loop like following =
try:
select the most inactive one

Quoted 5 lines

	-> try_to_fre_memory
		-> check limit
			-> go to try;

==

I've been thinking along those lines as well and that will get more important as we try to implement soft limits. However, for the current version I wanted correctness. Fairness, I've seen is achieved, since groups with large number of inactive pages, does get reclaimed from more than others (in my simple experiments).

Quoted 7 lines

As far the pseudo code is concerned, select the most inactive one is an O(c) operation, where c is the number of nodes under the subtree and is expensive. The data structure and select algorithm get expensive. I am thinking about a more suitable approach for implementation, but I want to focus on correctness as the first step. Since the hierarchy is not enabled by default, I am not adding any additional overhead, so I think that this approach is suitable.

What I say here is not "implement fairness" but "please make this algorithm easy to be updated." If you'll implement soft-limit, please design this code to be easily reused. (Again, I don't say do it now but please make code simpler.)

Can you make this code iterative rather than recursive ?

I don't like this kind of recursive call with complexed lock/unlock.

I think of it as easy to update - as in the modularity, you can plug out hierarchical reclaim easily and implement your own hierarchical reclaim.

Quoted 3 lines

Can you make this code iterative rather than recursive ?

I don't like this kind of recursive call with complexed lock/unlock.

I tried an iterative version, which ended up looking very ugly. I think the recursive version is easier to understand. What we do is a DFS walk - pretty standard algorithm.

Quoted 3 lines · On Wed, 12 Nov 2008 11:40:13 +0530 Balbir Singh <[email protected]>…

I think of it as easy to update - as in the modularity, you can plug out hierarchical reclaim easily and implement your own hierarchical reclaim.

When I do so, I'll rewrite all, again.

Quoted 7 lines

Quoted 3 lines

Can you make this code iterative rather than recursive ?

I don't like this kind of recursive call with complexed lock/unlock.

I tried an iterative version, which ended up looking very ugly. I think the recursive version is easier to understand. What we do is a DFS walk - pretty standard algorithm.

But recursive one is not good for search-and-try algorithm.

Quoted 7 lines · KAMEZAWA Hiroyuki

Quoted 3 lines · On Wed, 12 Nov 2008 11:40:13 +0530 Balbir Singh <[email protected]>…

I think of it as easy to update - as in the modularity, you can plug out hierarchical reclaim easily and implement your own hierarchical reclaim.

When I do so, I'll rewrite all, again.

I don't intend to ask you to rewrite it, rewrite all, I meant you as in a generic person. With hierarchy we will need weighted reclaim, which I'll add in later.

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Can you make this code iterative rather than recursive ?

Quoted 6 lines

Quoted 5 lines

Quoted 1 line

I don't like this kind of recursive call with complexed lock/unlock.

I tried an iterative version, which ended up looking very ugly. I think the recursive version is easier to understand. What we do is a DFS walk - pretty standard algorithm.

But recursive one is not good for search-and-try algorithm.

OK, I'll post the iterative algorithm, but it is going to be dirty :)

Quoted 20 lines · On Wed, 12 Nov 2008 11:52:47 +0530 Balbir Singh <[email protected]>…

Quoted 7 lines · KAMEZAWA Hiroyuki

Quoted 3 lines · On Wed, 12 Nov 2008 11:40:13 +0530 Balbir Singh <[email protected]>…

I think of it as easy to update - as in the modularity, you can plug out hierarchical reclaim easily and implement your own hierarchical reclaim.

When I do so, I'll rewrite all, again.

I don't intend to ask you to rewrite it, rewrite all, I meant you as in a generic person. With hierarchy we will need weighted reclaim, which I'll add in later.

Quoted 7 lines

Quoted 7 lines

Quoted 3 lines

Can you make this code iterative rather than recursive ?

I don't like this kind of recursive call with complexed lock/unlock.

I tried an iterative version, which ended up looking very ugly. I think the recursive version is easier to understand. What we do is a DFS walk - pretty standard algorithm.

Quoted 4 lines

Quoted 1 line

But recursive one is not good for search-and-try algorithm.

OK, I'll post the iterative algorithm, but it is going to be dirty :)

Ah, thanks. I think maybe you're right that ittrative one is dirty. I want to compare before going further.
Thank you for your patience.

Here is the iterative version of this patch. I tested it in my test environment. NOTE: The cgroup_locked check is still present, I'll remove that shortly after your patch is accepted.

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.

Quoted 9 lines · On Wed, 12 Nov 2008 16:51:41 +0530 Balbir Singh <[email protected]>…

Here is the iterative version of this patch. I tested it in my test environment. NOTE: The cgroup_locked check is still present, I'll remove that shortly after your patch is accepted.

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.

complicated as you said but it seems it's from style.

I expected following kind of one.

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-add-hierarchy-selector +9 -0

+	/*
+	 * If parent's use_hiearchy is set, we can't make any modifications
+	 * in the child subtrees. If it is unset, then the change can
+	 * occur, provided the current cgroup has no children.
+	 *
+	 * For the root cgroup, parent_mem is NULL, we allow value to be
+	 * set if there are no children.
+	 */
+	if (!parent_mem || (!parent_mem->use_hierarchy &&

Quoted 9 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-add-hierarchy-selector +9 -0

+	/*
+	 * If parent's use_hiearchy is set, we can't make any modifications
+	 * in the child subtrees. If it is unset, then the change can
+	 * occur, provided the current cgroup has no children.
+	 *
+	 * For the root cgroup, parent_mem is NULL, we allow value to be
+	 * set if there are no children.
+	 */
+	if (!parent_mem || (!parent_mem->use_hierarchy &&

mm/memcontrol.c out: · line 1135

Quoted 10 lines

mm/memcontrol.c renamed from mm/memcontrol.c~memcg-add-hierarchy-selector +10 -0

+				(val == 1 || val == 0))) {
+		if (list_empty(&cont->children))
+			mem->use_hierarchy = val;
+		else
+			retval = -EBUSY;
+	} else
+		retval = -EINVAL;
+
+	return retval;
+}

As I mentioned there is a race here. :(

echo 1 > /memcg/memory.use_hierarchy
=>if (list_empty(&cont->children))

                                      mkdir /memcg/0
                                       => mem->use_hierarchy = 0
       mem->use_hierarchy = 1;