| 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
| ||
|
Message-ID: <491A7345.4090500@linux.vnet.ibm.com>
Date: Wed, 12 Nov 2008 11:40:13 +0530
From: Balbir Singh <balbir@...ux.vnet.ibm.com>
To: KAMEZAWA Hiroyuki <kamezawa.hiroyu@...fujitsu.com>
CC: linux-mm@...ck.org, YAMAMOTO Takashi <yamamoto@...inux.co.jp>,
Paul Menage <menage@...gle.com>, lizf@...fujitsu.com,
linux-kernel@...r.kernel.org,
Nick Piggin <nickpiggin@...oo.com.au>,
David Rientjes <rientjes@...gle.com>,
Pavel Emelianov <xemul@...nvz.org>,
Dhaval Giani <dhaval@...ux.vnet.ibm.com>,
Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [RFC][mm] [PATCH 3/4] Memory cgroup hierarchical reclaim (v3)
KAMEZAWA Hiroyuki wrote:
> On Wed, 12 Nov 2008 11:19:37 +0530
> Balbir Singh <balbir@...ux.vnet.ibm.com> wrote:
>
>> KAMEZAWA Hiroyuki wrote:
>>> On Tue, 11 Nov 2008 18:04:17 +0530
>>> Balbir Singh <balbir@...ux.vnet.ibm.com> wrote:
>>>
>>>> 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.
>>>>
>>>> +/*
>>>> + * 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)
>>>> + 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;
>>> ==
>>>
>> 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.
>>
> 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.)
>
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.
> 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.
--
Balbir
--
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/
Powered by blists - more mailing lists