MIME-version: 1.0
Content-type: text/plain; charset=UTF-8; format=flowed
Content-transfer-encoding: 8BIT
Subject: Re: [PATCH v3 12/16] zsmalloc: zs_compact refactoring
To: Minchan Kim <minchan@kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>
References: <1459321935-3655-1-git-send-email-minchan@kernel.org>
 <1459321935-3655-13-git-send-email-minchan@kernel.org>
Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org
From: Chulmin Kim <cmlaika.kim@samsung.com>
Message-id: <57022000.9030705@samsung.com>
Date: Mon, 04 Apr 2016 17:04:16 +0900
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.6.0
In-reply-to: <1459321935-3655-13-git-send-email-minchan@kernel.org>
DLP-Filter: Pass
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 17312
Lines: 593

On 2016년 03월 30일 16:12, Minchan Kim wrote:
> Currently, we rely on class->lock to prevent zspage destruction.
> It was okay until now because the critical section is short but
> with run-time migration, it could be long so class->lock is not
> a good apporach any more.
>
> So, this patch introduces [un]freeze_zspage functions which
> freeze allocated objects in the zspage with pinning tag so
> user cannot free using object. With those functions, this patch
> redesign compaction.
>
> Those functions will be used for implementing zspage runtime
> migrations, too.
>
> Signed-off-by: Minchan Kim <minchan@kernel.org>
> ---
>   mm/zsmalloc.c | 393 ++++++++++++++++++++++++++++++++++++++--------------------
>   1 file changed, 257 insertions(+), 136 deletions(-)
>
> diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
> index b11dcd718502..ac8ca7b10720 100644
> --- a/mm/zsmalloc.c
> +++ b/mm/zsmalloc.c
> @@ -922,6 +922,13 @@ static unsigned long obj_to_head(struct size_class *class, struct page *page,
>   		return *(unsigned long *)obj;
>   }
>
> +static inline int testpin_tag(unsigned long handle)
> +{
> +	unsigned long *ptr = (unsigned long *)handle;
> +
> +	return test_bit(HANDLE_PIN_BIT, ptr);
> +}
> +
>   static inline int trypin_tag(unsigned long handle)
>   {
>   	unsigned long *ptr = (unsigned long *)handle;
> @@ -949,8 +956,7 @@ static void reset_page(struct page *page)
>   	page->freelist = NULL;
>   }
>
> -static void free_zspage(struct zs_pool *pool, struct size_class *class,
> -			struct page *first_page)
> +static void free_zspage(struct zs_pool *pool, struct page *first_page)
>   {
>   	struct page *nextp, *tmp, *head_extra;
>
> @@ -973,11 +979,6 @@ static void free_zspage(struct zs_pool *pool, struct size_class *class,
>   	}
>   	reset_page(head_extra);
>   	__free_page(head_extra);
> -
> -	zs_stat_dec(class, OBJ_ALLOCATED, get_maxobj_per_zspage(
> -			class->size, class->pages_per_zspage));
> -	atomic_long_sub(class->pages_per_zspage,
> -				&pool->pages_allocated);
>   }
>
>   /* Initialize a newly allocated zspage */
> @@ -1325,6 +1326,11 @@ static bool zspage_full(struct size_class *class, struct page *first_page)
>   	return get_zspage_inuse(first_page) == class->objs_per_zspage;
>   }
>
> +static bool zspage_empty(struct size_class *class, struct page *first_page)
> +{
> +	return get_zspage_inuse(first_page) == 0;
> +}
> +
>   unsigned long zs_get_total_pages(struct zs_pool *pool)
>   {
>   	return atomic_long_read(&pool->pages_allocated);
> @@ -1455,7 +1461,6 @@ static unsigned long obj_malloc(struct size_class *class,
>   		set_page_private(first_page, handle | OBJ_ALLOCATED_TAG);
>   	kunmap_atomic(vaddr);
>   	mod_zspage_inuse(first_page, 1);
> -	zs_stat_inc(class, OBJ_USED, 1);
>
>   	obj = location_to_obj(m_page, obj);
>
> @@ -1510,6 +1515,7 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size)
>   	}
>
>   	obj = obj_malloc(class, first_page, handle);
> +	zs_stat_inc(class, OBJ_USED, 1);
>   	/* Now move the zspage to another fullness group, if required */
>   	fix_fullness_group(class, first_page);
>   	record_obj(handle, obj);
> @@ -1540,7 +1546,6 @@ static void obj_free(struct size_class *class, unsigned long obj)
>   	kunmap_atomic(vaddr);
>   	set_freeobj(first_page, f_objidx);
>   	mod_zspage_inuse(first_page, -1);
> -	zs_stat_dec(class, OBJ_USED, 1);
>   }
>
>   void zs_free(struct zs_pool *pool, unsigned long handle)
> @@ -1564,10 +1569,19 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
>
>   	spin_lock(&class->lock);
>   	obj_free(class, obj);
> +	zs_stat_dec(class, OBJ_USED, 1);
>   	fullness = fix_fullness_group(class, first_page);
> -	if (fullness == ZS_EMPTY)
> -		free_zspage(pool, class, first_page);
> +	if (fullness == ZS_EMPTY) {
> +		zs_stat_dec(class, OBJ_ALLOCATED, get_maxobj_per_zspage(
> +				class->size, class->pages_per_zspage));
> +		spin_unlock(&class->lock);
> +		atomic_long_sub(class->pages_per_zspage,
> +					&pool->pages_allocated);
> +		free_zspage(pool, first_page);
> +		goto out;
> +	}
>   	spin_unlock(&class->lock);
> +out:
>   	unpin_tag(handle);
>
>   	free_handle(pool, handle);
> @@ -1637,127 +1651,66 @@ static void zs_object_copy(struct size_class *class, unsigned long dst,
>   	kunmap_atomic(s_addr);
>   }
>
> -/*
> - * Find alloced object in zspage from index object and
> - * return handle.
> - */
> -static unsigned long find_alloced_obj(struct size_class *class,
> -					struct page *page, int index)
> +static unsigned long handle_from_obj(struct size_class *class,
> +				struct page *first_page, int obj_idx)
>   {
> -	unsigned long head;
> -	int offset = 0;
> -	unsigned long handle = 0;
> -	void *addr = kmap_atomic(page);
> -
> -	if (!is_first_page(page))
> -		offset = page->index;
> -	offset += class->size * index;
> -
> -	while (offset < PAGE_SIZE) {
> -		head = obj_to_head(class, page, addr + offset);
> -		if (head & OBJ_ALLOCATED_TAG) {
> -			handle = head & ~OBJ_ALLOCATED_TAG;
> -			if (trypin_tag(handle))
> -				break;
> -			handle = 0;
> -		}
> +	struct page *page;
> +	unsigned long offset_in_page;
> +	void *addr;
> +	unsigned long head, handle = 0;
>
> -		offset += class->size;
> -		index++;
> -	}
> +	objidx_to_page_and_offset(class, first_page, obj_idx,
> +			&page, &offset_in_page);
>
> +	addr = kmap_atomic(page);
> +	head = obj_to_head(class, page, addr + offset_in_page);
> +	if (head & OBJ_ALLOCATED_TAG)
> +		handle = head & ~OBJ_ALLOCATED_TAG;
>   	kunmap_atomic(addr);
> +
>   	return handle;
>   }
>
> -struct zs_compact_control {
> -	/* Source page for migration which could be a subpage of zspage. */
> -	struct page *s_page;
> -	/* Destination page for migration which should be a first page
> -	 * of zspage. */
> -	struct page *d_page;
> -	 /* Starting object index within @s_page which used for live object
> -	  * in the subpage. */
> -	int index;
> -};
> -
> -static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
> -				struct zs_compact_control *cc)
> +static int migrate_zspage(struct size_class *class, struct page *dst_page,
> +				struct page *src_page)
>   {
> -	unsigned long used_obj, free_obj;
>   	unsigned long handle;
> -	struct page *s_page = cc->s_page;
> -	struct page *d_page = cc->d_page;
> -	unsigned long index = cc->index;
> -	int ret = 0;
> +	unsigned long old_obj, new_obj;
> +	int i;
> +	int nr_migrated = 0;
>
> -	while (1) {
> -		handle = find_alloced_obj(class, s_page, index);
> -		if (!handle) {
> -			s_page = get_next_page(s_page);
> -			if (!s_page)
> -				break;
> -			index = 0;
> +	for (i = 0; i < class->objs_per_zspage; i++) {
> +		handle = handle_from_obj(class, src_page, i);
> +		if (!handle)
>   			continue;
> -		}
> -
> -		/* Stop if there is no more space */
> -		if (zspage_full(class, d_page)) {
> -			unpin_tag(handle);
> -			ret = -ENOMEM;
> +		if (zspage_full(class, dst_page))
>   			break;
> -		}
> -
> -		used_obj = handle_to_obj(handle);
> -		free_obj = obj_malloc(class, d_page, handle);
> -		zs_object_copy(class, free_obj, used_obj);
> -		index++;
> +		old_obj = handle_to_obj(handle);
> +		new_obj = obj_malloc(class, dst_page, handle);
> +		zs_object_copy(class, new_obj, old_obj);
> +		nr_migrated++;
>   		/*
>   		 * record_obj updates handle's value to free_obj and it will
>   		 * invalidate lock bit(ie, HANDLE_PIN_BIT) of handle, which
>   		 * breaks synchronization using pin_tag(e,g, zs_free) so
>   		 * let's keep the lock bit.
>   		 */
> -		free_obj |= BIT(HANDLE_PIN_BIT);
> -		record_obj(handle, free_obj);
> -		unpin_tag(handle);
> -		obj_free(class, used_obj);
> +		new_obj |= BIT(HANDLE_PIN_BIT);
> +		record_obj(handle, new_obj);
> +		obj_free(class, old_obj);
>   	}
> -
> -	/* Remember last position in this iteration */
> -	cc->s_page = s_page;
> -	cc->index = index;
> -
> -	return ret;
> -}
> -
> -static struct page *isolate_target_page(struct size_class *class)
> -{
> -	int i;
> -	struct page *page;
> -
> -	for (i = 0; i < _ZS_NR_FULLNESS_GROUPS; i++) {
> -		page = class->fullness_list[i];
> -		if (page) {
> -			remove_zspage(class, i, page);
> -			break;
> -		}
> -	}
> -
> -	return page;
> +	return nr_migrated;
>   }
>
>   /*
>    * putback_zspage - add @first_page into right class's fullness list
> - * @pool: target pool
>    * @class: destination class
>    * @first_page: target page
>    *
>    * Return @first_page's updated fullness_group
>    */
> -static enum fullness_group putback_zspage(struct zs_pool *pool,
> -			struct size_class *class,
> -			struct page *first_page)
> +static enum fullness_group putback_zspage(struct size_class *class,
> +					struct page *first_page)
>   {
>   	enum fullness_group fullness;
>
> @@ -1768,17 +1721,155 @@ static enum fullness_group putback_zspage(struct zs_pool *pool,
>   	return fullness;
>   }
>
> +/*
> + * freeze_zspage - freeze all objects in a zspage
> + * @class: size class of the page
> + * @first_page: first page of zspage
> + *
> + * Freeze all allocated objects in a zspage so objects couldn't be
> + * freed until unfreeze objects. It should be called under class->lock.
> + *
> + * RETURNS:
> + * the number of pinned objects
> + */
> +static int freeze_zspage(struct size_class *class, struct page *first_page)
> +{
> +	unsigned long obj_idx;
> +	struct page *obj_page;
> +	unsigned long offset;
> +	void *addr;
> +	int nr_freeze = 0;
> +
> +	for (obj_idx = 0; obj_idx < class->objs_per_zspage; obj_idx++) {
> +		unsigned long head;
> +
> +		objidx_to_page_and_offset(class, first_page, obj_idx,
> +					&obj_page, &offset);
> +		addr = kmap_atomic(obj_page);
> +		head = obj_to_head(class, obj_page, addr + offset);
> +		if (head & OBJ_ALLOCATED_TAG) {
> +			unsigned long handle = head & ~OBJ_ALLOCATED_TAG;
> +
> +			if (!trypin_tag(handle)) {
> +				kunmap_atomic(addr);
> +				break;
> +			}
> +			nr_freeze++;
> +		}
> +		kunmap_atomic(addr);
> +	}
> +
> +	return nr_freeze;
> +}
> +
> +/*
> + * unfreeze_page - unfreeze objects freezed by freeze_zspage in a zspage
> + * @class: size class of the page
> + * @first_page: freezed zspage to unfreeze
> + * @nr_obj: the number of objects to unfreeze
> + *
> + * unfreeze objects in a zspage.
> + */
> +static void unfreeze_zspage(struct size_class *class, struct page *first_page,
> +			int nr_obj)
> +{
> +	unsigned long obj_idx;
> +	struct page *obj_page;
> +	unsigned long offset;
> +	void *addr;
> +	int nr_unfreeze = 0;
> +
> +	for (obj_idx = 0; obj_idx < class->objs_per_zspage &&
> +			nr_unfreeze < nr_obj; obj_idx++) {
> +		unsigned long head;
> +
> +		objidx_to_page_and_offset(class, first_page, obj_idx,
> +					&obj_page, &offset);
> +		addr = kmap_atomic(obj_page);
> +		head = obj_to_head(class, obj_page, addr + offset);
> +		if (head & OBJ_ALLOCATED_TAG) {
> +			unsigned long handle = head & ~OBJ_ALLOCATED_TAG;
> +
> +			VM_BUG_ON(!testpin_tag(handle));
> +			unpin_tag(handle);
> +			nr_unfreeze++;
> +		}
> +		kunmap_atomic(addr);
> +	}
> +}
> +
> +/*
> + * isolate_source_page - isolate a zspage for migration source
> + * @class: size class of zspage for isolation
> + *
> + * Returns a zspage which are isolated from list so anyone can
> + * allocate a object from that page. As well, freeze all objects
> + * allocated in the zspage so anyone cannot access that objects
> + * (e.g., zs_map_object, zs_free).
> + */
>   static struct page *isolate_source_page(struct size_class *class)
>   {
>   	int i;
>   	struct page *page = NULL;
>
>   	for (i = ZS_ALMOST_EMPTY; i >= ZS_ALMOST_FULL; i--) {
> +		int inuse, freezed;
> +
>   		page = class->fullness_list[i];
>   		if (!page)
>   			continue;
>
>   		remove_zspage(class, i, page);
> +
> +		inuse = get_zspage_inuse(page);
> +		freezed = freeze_zspage(class, page);
> +
> +		if (inuse != freezed) {
> +			unfreeze_zspage(class, page, freezed);
> +			putback_zspage(class, page);
> +			page = NULL;
> +			continue;
> +		}
> +
> +		break;
> +	}
> +
> +	return page;
> +}
> +
> +/*
> + * isolate_target_page - isolate a zspage for migration target
> + * @class: size class of zspage for isolation
> + *
> + * Returns a zspage which are isolated from list so anyone can
> + * allocate a object from that page. As well, freeze all objects
> + * allocated in the zspage so anyone cannot access that objects
> + * (e.g., zs_map_object, zs_free).
> + */
> +static struct page *isolate_target_page(struct size_class *class)
> +{
> +	int i;
> +	struct page *page;
> +
> +	for (i = 0; i < _ZS_NR_FULLNESS_GROUPS; i++) {
> +		int inuse, freezed;
> +
> +		page = class->fullness_list[i];
> +		if (!page)
> +			continue;
> +
> +		remove_zspage(class, i, page);
> +
> +		inuse = get_zspage_inuse(page);
> +		freezed = freeze_zspage(class, page);
> +
> +		if (inuse != freezed) {
> +			unfreeze_zspage(class, page, freezed);
> +			putback_zspage(class, page);
> +			page = NULL;
> +			continue;
> +		}
> +
>   		break;
>   	}
>
> @@ -1793,9 +1884,11 @@ static struct page *isolate_source_page(struct size_class *class)
>   static unsigned long zs_can_compact(struct size_class *class)
>   {
>   	unsigned long obj_wasted;
> +	unsigned long obj_allocated, obj_used;
>
> -	obj_wasted = zs_stat_get(class, OBJ_ALLOCATED) -
> -		zs_stat_get(class, OBJ_USED);
> +	obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
> +	obj_used = zs_stat_get(class, OBJ_USED);
> +	obj_wasted = obj_allocated - obj_used;
>
>   	obj_wasted /= get_maxobj_per_zspage(class->size,
>   			class->pages_per_zspage);
> @@ -1805,53 +1898,81 @@ static unsigned long zs_can_compact(struct size_class *class)
>
>   static void __zs_compact(struct zs_pool *pool, struct size_class *class)
>   {
> -	struct zs_compact_control cc;
> -	struct page *src_page;
> +	struct page *src_page = NULL;
>   	struct page *dst_page = NULL;
>
> -	spin_lock(&class->lock);
> -	while ((src_page = isolate_source_page(class))) {
> +	while (1) {
> +		int nr_migrated;
>
> -		if (!zs_can_compact(class))
> +		spin_lock(&class->lock);
> +		if (!zs_can_compact(class)) {
> +			spin_unlock(&class->lock);
>   			break;
> +		}
>
> -		cc.index = 0;
> -		cc.s_page = src_page;
> +		/*
> +		 * Isolate source page and freeze all objects in a zspage
> +		 * to prevent zspage destroying.
> +		 */
> +		if (!src_page) {
> +			src_page = isolate_source_page(class);
> +			if (!src_page) {
> +				spin_unlock(&class->lock);
> +				break;
> +			}
> +		}
>
> -		while ((dst_page = isolate_target_page(class))) {
> -			cc.d_page = dst_page;
> -			/*
> -			 * If there is no more space in dst_page, resched
> -			 * and see if anyone had allocated another zspage.
> -			 */
> -			if (!migrate_zspage(pool, class, &cc))
> +		/* Isolate target page and freeze all objects in the zspage */
> +		if (!dst_page) {
> +			dst_page = isolate_target_page(class);
> +			if (!dst_page) {
> +				spin_unlock(&class->lock);
>   				break;
> +			}
> +		}
> +		spin_unlock(&class->lock);

(Sorry to delete individual recipients due to my compliance issues.)

Hello, Minchan.


Is it safe to unlock?


(I assume that the system has 2 cores
and a swap device is using zsmalloc pool.)
If a zs compact context scheduled out after this "spin_unlock" line,


    CPU A (Swap In)                CPU B (zs_free by process killed)
---------------------           -------------------------
                                 ...
                                 spin_lock(&si->lock)
                                 ...
                                # assume it is pinned by zs_compact context.
                                 pin_tag(handle) --> block

...
spin_lock(&si->lock) --> block


I think CPU A and CPU B may not be released forever.
Am I missing something?

Thanks.
Chulmin


> +
> +		nr_migrated = migrate_zspage(class, dst_page, src_page);
>
> -			VM_BUG_ON_PAGE(putback_zspage(pool, class,
> -				dst_page) == ZS_EMPTY, dst_page);
> +		if (zspage_full(class, dst_page)) {
> +			spin_lock(&class->lock);
> +			putback_zspage(class, dst_page);
> +			unfreeze_zspage(class, dst_page,
> +				class->objs_per_zspage);
> +			spin_unlock(&class->lock);
> +			dst_page = NULL;
>   		}
>
> -		/* Stop if we couldn't find slot */
> -		if (dst_page == NULL)
> -			break;
> +		if (zspage_empty(class, src_page)) {
> +			free_zspage(pool, src_page);
> +			spin_lock(&class->lock);
> +			zs_stat_dec(class, OBJ_ALLOCATED,
> +				get_maxobj_per_zspage(
> +				class->size, class->pages_per_zspage));
> +			atomic_long_sub(class->pages_per_zspage,
> +					&pool->pages_allocated);
>
> -		VM_BUG_ON_PAGE(putback_zspage(pool, class,
> -				dst_page) == ZS_EMPTY, dst_page);
> -		if (putback_zspage(pool, class, src_page) == ZS_EMPTY) {
>   			pool->stats.pages_compacted += class->pages_per_zspage;
>   			spin_unlock(&class->lock);
> -			free_zspage(pool, class, src_page);
> -		} else {
> -			spin_unlock(&class->lock);
> +			src_page = NULL;
>   		}
> +	}
>
> -		cond_resched();
> -		spin_lock(&class->lock);
> +	if (!src_page && !dst_page)
> +		return;
> +
> +	spin_lock(&class->lock);
> +	if (src_page) {
> +		putback_zspage(class, src_page);
> +		unfreeze_zspage(class, src_page,
> +				class->objs_per_zspage);
>   	}
>
> -	if (src_page)
> -		VM_BUG_ON_PAGE(putback_zspage(pool, class,
> -				src_page) == ZS_EMPTY, src_page);
> +	if (dst_page) {
> +		putback_zspage(class, dst_page);
> +		unfreeze_zspage(class, dst_page,
> +				class->objs_per_zspage);
> +	}
>
>   	spin_unlock(&class->lock);
>   }
>