[PATCH v1 06/10] zsmalloc: support compaction
This patch provides core functions for migration of zsmalloc.
Migraion policy is simple as follows.
It searches source zspages from ZS_ALMOST_EMPTY and destination
zspages from ZS_ALMOST_FULL and try to move objects in source
zspage into destination zspages. If it is lack of destination
pages in ZS_ALMOST_FULL, it falls back to ZS_ALMOST_EMPTY.
If all objects in source zspage moved out, the zspage could be
freed.
Migrate uses rcu freeing to free source zspage in migration
since migration could race with object accessing via
zs_map_object so that we can access size_class from handle
safely with rcu_read_[un]lock but it needs to recheck
handle's validity.
Signed-off-by: Minchan Kim
---
include/linux/zsmalloc.h | 1 +
mm/zsmalloc.c| 324 ++-
2 files changed, 321 insertions(+), 4 deletions(-)
diff --git a/include/linux/zsmalloc.h b/include/linux/zsmalloc.h
index 3283c6a..1338190 100644
--- a/include/linux/zsmalloc.h
+++ b/include/linux/zsmalloc.h
@@ -47,5 +47,6 @@ void *zs_map_object(struct zs_pool *pool, unsigned long
handle,
void zs_unmap_object(struct zs_pool *pool, unsigned long handle);
unsigned long zs_get_total_pages(struct zs_pool *pool);
+unsigned long zs_compact(struct zs_pool *pool);
#endif
diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index 99555da..99bf5bd 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -663,6 +663,11 @@ static unsigned long handle_to_obj(unsigned long handle)
return *(unsigned long *)handle;
}
+unsigned long obj_to_head(void *obj)
+{
+ return *(unsigned long *)obj;
+}
+
static unsigned long obj_idx_to_offset(struct page *page,
unsigned long obj_idx, int class_size)
{
@@ -1044,6 +1049,13 @@ static bool can_merge(struct size_class *prev, int size,
int pages_per_zspage)
return true;
}
+static bool zspage_full(struct page *page)
+{
+ BUG_ON(!is_first_page(page));
+
+ return page->inuse == page->objects;
+}
+
#ifdef CONFIG_ZSMALLOC_STAT
static inline void zs_stat_inc(struct size_class *class,
@@ -1246,12 +1258,27 @@ void *zs_map_object(struct zs_pool *pool, unsigned long
handle,
*/
BUG_ON(in_interrupt());
- pin_tag(handle);
-
+retry:
+ /*
+* Migrating object will not be destroyed so we can get a first_page
+* safely but need to verify handle again.
+*/
+ rcu_read_lock();
obj = handle_to_obj(handle);
obj_to_location(obj, , _idx);
get_zspage_mapping(get_first_page(page), _idx, );
class = pool->size_class[class_idx];
+ spin_lock(>lock);
+ if (obj != handle_to_obj(handle)) {
+ /* the object was moved by migration. Then fetch new object */
+ spin_unlock(>lock);
+ rcu_read_unlock();
+ goto retry;
+ }
+ rcu_read_unlock();
+ /* From now on, migration cannot move the object */
+ pin_tag(handle);
+ spin_unlock(>lock);
off = obj_idx_to_offset(page, obj_idx, class->size);
area = _cpu_var(zs_map_area);
@@ -1305,7 +1332,9 @@ void zs_unmap_object(struct zs_pool *pool, unsigned long
handle)
__zs_unmap_object(area, pages, off, class->size);
}
put_cpu_var(zs_map_area);
+ spin_lock(>lock);
unpin_tag(handle);
+ spin_unlock(>lock);
}
EXPORT_SYMBOL_GPL(zs_unmap_object);
@@ -1434,9 +1463,9 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
if (unlikely(!handle))
return;
-
+retry:
+ rcu_read_lock();
obj = handle_to_obj(handle);
- free_handle(pool, handle);
obj_to_location(obj, _page, _objidx);
first_page = get_first_page(f_page);
@@ -1444,6 +1473,15 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
class = pool->size_class[class_idx];
spin_lock(>lock);
+ /* Retry if migrate moves object */
+ if (obj != handle_to_obj(handle)) {
+ spin_unlock(>lock);
+ rcu_read_unlock();
+ goto retry;
+ }
+ rcu_read_unlock();
+
+ free_handle(pool, handle);
obj_free(pool, class, obj);
fullness = fix_fullness_group(class, first_page);
if (fullness == ZS_EMPTY)
@@ -1459,6 +1497,284 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
}
EXPORT_SYMBOL_GPL(zs_free);
+static void zs_object_copy(unsigned long src, unsigned long dst,
+ struct size_class *class)
+{
+ struct page *s_page, *d_page;
+ unsigned long s_objidx, d_objidx;
+ unsigned long s_off, d_off;
+ void *s_addr, *d_addr;
+ int s_size, d_size, size;
+ int written = 0;
+
+ s_size = d_size = class->size;
+
+ obj_to_location(src, _page, _objidx);
+ obj_to_location(dst, _page, _objidx);
+
+ s_off = obj_idx_to_offset(s_page, s_objidx, class->size);
+ d_off =
[PATCH v1 06/10] zsmalloc: support compaction
This patch provides core functions for migration of zsmalloc.
Migraion policy is simple as follows.
It searches source zspages from ZS_ALMOST_EMPTY and destination
zspages from ZS_ALMOST_FULL and try to move objects in source
zspage into destination zspages. If it is lack of destination
pages in ZS_ALMOST_FULL, it falls back to ZS_ALMOST_EMPTY.
If all objects in source zspage moved out, the zspage could be
freed.
Migrate uses rcu freeing to free source zspage in migration
since migration could race with object accessing via
zs_map_object so that we can access size_class from handle
safely with rcu_read_[un]lock but it needs to recheck
handle's validity.
Signed-off-by: Minchan Kim minc...@kernel.org
---
include/linux/zsmalloc.h | 1 +
mm/zsmalloc.c| 324 ++-
2 files changed, 321 insertions(+), 4 deletions(-)
diff --git a/include/linux/zsmalloc.h b/include/linux/zsmalloc.h
index 3283c6a..1338190 100644
--- a/include/linux/zsmalloc.h
+++ b/include/linux/zsmalloc.h
@@ -47,5 +47,6 @@ void *zs_map_object(struct zs_pool *pool, unsigned long
handle,
void zs_unmap_object(struct zs_pool *pool, unsigned long handle);
unsigned long zs_get_total_pages(struct zs_pool *pool);
+unsigned long zs_compact(struct zs_pool *pool);
#endif
diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index 99555da..99bf5bd 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -663,6 +663,11 @@ static unsigned long handle_to_obj(unsigned long handle)
return *(unsigned long *)handle;
}
+unsigned long obj_to_head(void *obj)
+{
+ return *(unsigned long *)obj;
+}
+
static unsigned long obj_idx_to_offset(struct page *page,
unsigned long obj_idx, int class_size)
{
@@ -1044,6 +1049,13 @@ static bool can_merge(struct size_class *prev, int size,
int pages_per_zspage)
return true;
}
+static bool zspage_full(struct page *page)
+{
+ BUG_ON(!is_first_page(page));
+
+ return page-inuse == page-objects;
+}
+
#ifdef CONFIG_ZSMALLOC_STAT
static inline void zs_stat_inc(struct size_class *class,
@@ -1246,12 +1258,27 @@ void *zs_map_object(struct zs_pool *pool, unsigned long
handle,
*/
BUG_ON(in_interrupt());
- pin_tag(handle);
-
+retry:
+ /*
+* Migrating object will not be destroyed so we can get a first_page
+* safely but need to verify handle again.
+*/
+ rcu_read_lock();
obj = handle_to_obj(handle);
obj_to_location(obj, page, obj_idx);
get_zspage_mapping(get_first_page(page), class_idx, fg);
class = pool-size_class[class_idx];
+ spin_lock(class-lock);
+ if (obj != handle_to_obj(handle)) {
+ /* the object was moved by migration. Then fetch new object */
+ spin_unlock(class-lock);
+ rcu_read_unlock();
+ goto retry;
+ }
+ rcu_read_unlock();
+ /* From now on, migration cannot move the object */
+ pin_tag(handle);
+ spin_unlock(class-lock);
off = obj_idx_to_offset(page, obj_idx, class-size);
area = get_cpu_var(zs_map_area);
@@ -1305,7 +1332,9 @@ void zs_unmap_object(struct zs_pool *pool, unsigned long
handle)
__zs_unmap_object(area, pages, off, class-size);
}
put_cpu_var(zs_map_area);
+ spin_lock(class-lock);
unpin_tag(handle);
+ spin_unlock(class-lock);
}
EXPORT_SYMBOL_GPL(zs_unmap_object);
@@ -1434,9 +1463,9 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
if (unlikely(!handle))
return;
-
+retry:
+ rcu_read_lock();
obj = handle_to_obj(handle);
- free_handle(pool, handle);
obj_to_location(obj, f_page, f_objidx);
first_page = get_first_page(f_page);
@@ -1444,6 +1473,15 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
class = pool-size_class[class_idx];
spin_lock(class-lock);
+ /* Retry if migrate moves object */
+ if (obj != handle_to_obj(handle)) {
+ spin_unlock(class-lock);
+ rcu_read_unlock();
+ goto retry;
+ }
+ rcu_read_unlock();
+
+ free_handle(pool, handle);
obj_free(pool, class, obj);
fullness = fix_fullness_group(class, first_page);
if (fullness == ZS_EMPTY)
@@ -1459,6 +1497,284 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
}
EXPORT_SYMBOL_GPL(zs_free);
+static void zs_object_copy(unsigned long src, unsigned long dst,
+ struct size_class *class)
+{
+ struct page *s_page, *d_page;
+ unsigned long s_objidx, d_objidx;
+ unsigned long s_off, d_off;
+ void *s_addr, *d_addr;
+ int s_size, d_size, size;
+ int written = 0;
+
+ s_size = d_size = class-size;
+
+ obj_to_location(src, s_page, s_objidx);
+ obj_to_location(dst, d_page, d_objidx);
+
+ s_off =
