Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [PATCH 03/10] mm: Assign memcg-aware shrinkers bitmap to memcg
To:     Matthew Wilcox <willy@infradead.org>
Cc:     viro@zeniv.linux.org.uk, hannes@cmpxchg.org, mhocko@kernel.org,
        vdavydov.dev@gmail.com, akpm@linux-foundation.org,
        tglx@linutronix.de, pombredanne@nexb.com, stummala@codeaurora.org,
        gregkh@linuxfoundation.org, sfr@canb.auug.org.au, guro@fb.com,
        mka@chromium.org, penguin-kernel@I-love.SAKURA.ne.jp,
        chris@chris-wilson.co.uk, longman@redhat.com, minchan@kernel.org,
        hillf.zj@alibaba-inc.com, ying.huang@intel.com,
        mgorman@techsingularity.net, shakeelb@google.com, jbacik@fb.com,
        linux@roeck-us.net, linux-kernel@vger.kernel.org,
        linux-mm@kvack.org
References: <152163840790.21546.980703278415599202.stgit@localhost.localdomain>
 <152163850081.21546.6969747084834474733.stgit@localhost.localdomain>
 <20180321145625.GA4780@bombadil.infradead.org>
 <eda62454-5788-4f65-c2b5-719d4a98cb2a@virtuozzo.com>
 <20180321152647.GB4780@bombadil.infradead.org>
 <638887a1-35f8-a71d-6e45-4e779eb62dc4@virtuozzo.com>
 <20180321162039.GC4780@bombadil.infradead.org>
 <d738c32f-78fd-7e95-803d-2c48594d14e2@virtuozzo.com>
 <20180321175453.GG4780@bombadil.infradead.org>
From:   Kirill Tkhai <ktkhai@virtuozzo.com>
Message-ID: <ef34c7c8-0ce7-f427-6743-2cbd8d844298@virtuozzo.com>
Date:   Thu, 22 Mar 2018 19:39:06 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.6.0
MIME-Version: 1.0
In-Reply-To: <20180321175453.GG4780@bombadil.infradead.org>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Received-SPF: None (protection.outlook.com: virtuozzo.com does not designate
 permitted sender hosts)
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 22 Mar 2018 16:39:10.0562 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: 9dd0ffdf-e337-4c51-0871-08d590137087
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 0bc7f26d-0264-416e-a6fc-8352af79c58f
X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0801MB1337
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On 21.03.2018 20:54, Matthew Wilcox wrote:
> On Wed, Mar 21, 2018 at 07:42:38PM +0300, Kirill Tkhai wrote:
>> On 21.03.2018 19:20, Matthew Wilcox wrote:
>>>> Sound great, thanks for explaining this. The big problem I see is
>>>> that IDA/IDR add primitives allocate memory, while they will be used
>>>> in the places, where they mustn't fail. There is list_lru_add(), and
>>>> it's called unconditionally in current kernel code. The patchset makes
>>>> the bitmap be populated in this function. So, we can't use IDR there.
>>>
>>> Maybe we can use GFP_NOFAIL here.  They're small allocations, so we're
>>> only asking for single-page allocations to not fail, which shouldn't
>>> put too much strain on the VM.
>>  
>> Oh. I'm not sure about this. Even if each allocation is small, there is
>> theoretically possible a situation, when many lists will want to add first
>> element. list_lru_add() is called from iput() for example.
> 
> I see.  Maybe we could solve this with an IDA_NO_SHRINK flag and an
> ida_resize(ida, max); call.

But what will be the difference to bitmap, if we allocate maximal map anyway?

> You'll also want something like this:
> 
> 
> diff --git a/include/linux/idr.h b/include/linux/idr.h
> index 0f650b90ced0..ee7185354fb2 100644
> --- a/include/linux/idr.h
> +++ b/include/linux/idr.h
> @@ -273,6 +273,22 @@ static inline void ida_init(struct ida *ida)
>  			ida_alloc_range(ida, start, (end) - 1, gfp)
>  #define ida_simple_remove(ida, id)	ida_free(ida, id)
>  
> +int ida_find(struct ida *, unsigned int id);
> +
> +/**
> + * ida_for_each() - Iterate over all allocated IDs.
> + * @ida: IDA handle.
> + * @id: Loop cursor.
> + *
> + * For each iteration of this loop, @id will be set to an allocated ID.
> + * No locks are held across the body of the loop, so you can call ida_free()
> + * if you want or adjust @id to skip IDs or re-process earlier IDs.
> + *
> + * On successful loop exit, @id will be less than 0.
> + */
> +#define ida_for_each(ida, i)			\
> +	for (i = ida_find(ida, 0); i >= 0; i = ida_find(ida, i + 1))
> +
>  /**
>   * ida_get_new - allocate new ID
>   * @ida:	idr handle
> diff --git a/lib/idr.c b/lib/idr.c
> index fab3763e8c2a..ba9fae7eb2f5 100644
> --- a/lib/idr.c
> +++ b/lib/idr.c
> @@ -612,3 +612,54 @@ void ida_free(struct ida *ida, unsigned int id)
>  	spin_unlock_irqrestore(&simple_ida_lock, flags);
>  }
>  EXPORT_SYMBOL(ida_free);
> +
> +/**
> + * ida_find() - Find an allocated ID.
> + * @ida: IDA handle.
> + * @id: Minimum ID to return.
> + *
> + * Context: Any context.
> + * Return: An ID which is at least as large as @id or %-ENOSPC if @id is
> + * higher than any allocated ID.
> + */
> +int ida_find(struct ida *ida, unsigned int id)
> +{
> +	unsigned long flags;
> +	unsigned long index = id / IDA_BITMAP_BITS;
> +	unsigned bit = id % IDA_BITMAP_BITS;
> +	struct ida_bitmap *bitmap;
> +	struct radix_tree_iter iter;
> +	void __rcu **slot;
> +	int ret = -ENOSPC;
> +
> +	spin_lock_irqsave(&simple_ida_lock, flags);
> +advance:
> +	slot = radix_tree_iter_find(&ida->ida_rt, &iter, index);
> +	if (!slot)
> +		goto unlock;
> +	bitmap = rcu_dereference_raw(*slot);
> +	if (radix_tree_exception(bitmap)) {
> +		if (bit < (BITS_PER_LONG - RADIX_TREE_EXCEPTIONAL_SHIFT)) {
> +			unsigned long bits = (unsigned long)bitmap;
> +
> +			bits >>= bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
> +			if (bits) {
> +				bit += __ffs(bits);
> +				goto found;
> +			}
> +		}
> +	} else {
> +		bit = find_next_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);
> +		if (bit < IDA_BITMAP_BITS)
> +			goto found;
> +	}
> +	bit = 0;
> +	index++;
> +	goto advance;
> +found:
> +	ret = iter.index * IDA_BITMAP_BITS + bit;
> +unlock:
> +	spin_unlock_irqrestore(&simple_ida_lock, flags);
> +	return ret;
> +}
> +EXPORT_SYMBOL(ida_find);
> diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
> index 6c645eb77d42..a9b5a33a4ef3 100644
> --- a/tools/testing/radix-tree/idr-test.c
> +++ b/tools/testing/radix-tree/idr-test.c
> @@ -358,8 +358,12 @@ void ida_check_conv(void)
>  		assert(ida_pre_get(&ida, GFP_KERNEL));
>  		assert(!ida_get_new_above(&ida, i + 1, &id));
>  		assert(id == i + 1);
> +		ida_for_each(&ida, id)
> +			BUG_ON(id != (i + 1));
>  		assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id));
>  		assert(id == i + BITS_PER_LONG);
> +		ida_for_each(&ida, id)
> +			BUG_ON((id != (i + 1)) && (id != (i + BITS_PER_LONG)));
>  		ida_remove(&ida, i + 1);
>  		ida_remove(&ida, i + BITS_PER_LONG);
>  		assert(ida_is_empty(&ida));
> @@ -484,7 +488,7 @@ void ida_simple_get_remove_test(void)
>  void ida_checks(void)
>  {
>  	DEFINE_IDA(ida);
> -	int id;
> +	int id, id2;
>  	unsigned long i;
>  
>  	radix_tree_cpu_dead(1);
> @@ -496,8 +500,22 @@ void ida_checks(void)
>  		assert(id == i);
>  	}
>  
> +	id2 = 0;
> +	ida_for_each(&ida, id) {
> +		BUG_ON(id != id2++);
> +	}
> +	BUG_ON(id >= 0);
> +	BUG_ON(id2 != 10000);
> +
>  	ida_remove(&ida, 20);
>  	ida_remove(&ida, 21);
> +	id2 = 0;
> +	ida_for_each(&ida, id) {
> +		if (id != id2++) {
> +			BUG_ON(id != 22 || id2 != 21);
> +			id2 = 23;
> +		}
> +	}
>  	for (i = 0; i < 3; i++) {
>  		assert(ida_pre_get(&ida, GFP_KERNEL));
>  		assert(!ida_get_new(&ida, &id));
>