Re: [PATCH 03/10] mm: Assign memcg-aware shrinkers bitmap to memcg

[Kirill Tkhai]

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));
>