From bfd093f5e7f09c1e41c43e7605893069975cd734 Mon Sep 17 00:00:00 2001 From: Minchan Kim Date: Tue, 26 Jul 2016 15:23:28 -0700 Subject: [PATCH] zsmalloc: use freeobj for index Zsmalloc stores first free object's position into freeobj in each zspage. If we change it with index from first_page instead of position, it makes page migration simple because we don't need to correct other entries for linked list if a page is migrated out. Link: http://lkml.kernel.org/r/1464736881-24886-11-git-send-email-minchan@kernel.org Signed-off-by: Minchan Kim Cc: Sergey Senozhatsky Cc: Vlastimil Babka Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- mm/zsmalloc.c | 139 ++++++++++++++++++++++++++------------------------ 1 file changed, 73 insertions(+), 66 deletions(-) diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c index dd3708611f65..c6fb543cfb98 100644 --- a/mm/zsmalloc.c +++ b/mm/zsmalloc.c @@ -71,9 +71,7 @@ * Object location (, ) is encoded as * as single (unsigned long) handle value. * - * Note that object index is relative to system - * page it is stored in, so for each sub-page belonging - * to a zspage, obj_idx starts with 0. + * Note that object index starts from 0. * * This is made more complicated by various memory models and PAE. */ @@ -214,10 +212,10 @@ struct size_class { struct link_free { union { /* - * Position of next free chunk (encodes ) + * Free object index; * It's valid for non-allocated object */ - void *next; + unsigned long next; /* * Handle of allocated object. */ @@ -261,7 +259,7 @@ struct zspage { unsigned int class:CLASS_BITS; }; unsigned int inuse; - void *freeobj; + unsigned int freeobj; struct page *first_page; struct list_head list; /* fullness list */ }; @@ -459,14 +457,14 @@ static inline void set_first_obj_offset(struct page *page, int offset) page->index = offset; } -static inline unsigned long get_freeobj(struct zspage *zspage) +static inline unsigned int get_freeobj(struct zspage *zspage) { - return (unsigned long)zspage->freeobj; + return zspage->freeobj; } -static inline void set_freeobj(struct zspage *zspage, unsigned long obj) +static inline void set_freeobj(struct zspage *zspage, unsigned int obj) { - zspage->freeobj = (void *)obj; + zspage->freeobj = obj; } static void get_zspage_mapping(struct zspage *zspage, @@ -810,6 +808,10 @@ static int get_pages_per_zspage(int class_size) return max_usedpc_order; } +static struct page *get_first_page(struct zspage *zspage) +{ + return zspage->first_page; +} static struct zspage *get_zspage(struct page *page) { @@ -821,37 +823,33 @@ static struct page *get_next_page(struct page *page) return page->next; } -/* - * Encode as a single handle value. - * We use the least bit of handle for tagging. +/** + * obj_to_location - get (, ) from encoded object value + * @page: page object resides in zspage + * @obj_idx: object index */ -static void *location_to_obj(struct page *page, unsigned long obj_idx) +static void obj_to_location(unsigned long obj, struct page **page, + unsigned int *obj_idx) { - unsigned long obj; + obj >>= OBJ_TAG_BITS; + *page = pfn_to_page(obj >> OBJ_INDEX_BITS); + *obj_idx = (obj & OBJ_INDEX_MASK); +} - if (!page) { - VM_BUG_ON(obj_idx); - return NULL; - } +/** + * location_to_obj - get obj value encoded from (, ) + * @page: page object resides in zspage + * @obj_idx: object index + */ +static unsigned long location_to_obj(struct page *page, unsigned int obj_idx) +{ + unsigned long obj; obj = page_to_pfn(page) << OBJ_INDEX_BITS; - obj |= ((obj_idx) & OBJ_INDEX_MASK); + obj |= obj_idx & OBJ_INDEX_MASK; obj <<= OBJ_TAG_BITS; - return (void *)obj; -} - -/* - * Decode pair from the given object handle. We adjust the - * decoded obj_idx back to its original value since it was adjusted in - * location_to_obj(). - */ -static void obj_to_location(unsigned long obj, struct page **page, - unsigned long *obj_idx) -{ - obj >>= OBJ_TAG_BITS; - *page = pfn_to_page(obj >> OBJ_INDEX_BITS); - *obj_idx = (obj & OBJ_INDEX_MASK); + return obj; } static unsigned long handle_to_obj(unsigned long handle) @@ -869,16 +867,6 @@ static unsigned long obj_to_head(struct size_class *class, struct page *page, return *(unsigned long *)obj; } -static unsigned long obj_idx_to_offset(struct page *page, - unsigned long obj_idx, int class_size) -{ - unsigned long off; - - off = get_first_obj_offset(page); - - return off + obj_idx * class_size; -} - static inline int trypin_tag(unsigned long handle) { return bit_spin_trylock(HANDLE_PIN_BIT, (unsigned long *)handle); @@ -922,13 +910,13 @@ static void free_zspage(struct zs_pool *pool, struct zspage *zspage) /* Initialize a newly allocated zspage */ static void init_zspage(struct size_class *class, struct zspage *zspage) { + unsigned int freeobj = 1; unsigned long off = 0; struct page *page = zspage->first_page; while (page) { struct page *next_page; struct link_free *link; - unsigned int i = 1; void *vaddr; set_first_obj_offset(page, off); @@ -937,7 +925,7 @@ static void init_zspage(struct size_class *class, struct zspage *zspage) link = (struct link_free *)vaddr + off / sizeof(*link); while ((off += class->size) < PAGE_SIZE) { - link->next = location_to_obj(page, i++); + link->next = freeobj++ << OBJ_ALLOCATED_TAG; link += class->size / sizeof(*link); } @@ -947,14 +935,21 @@ static void init_zspage(struct size_class *class, struct zspage *zspage) * page (if present) */ next_page = get_next_page(page); - link->next = location_to_obj(next_page, 0); + if (next_page) { + link->next = freeobj++ << OBJ_ALLOCATED_TAG; + } else { + /* + * Reset OBJ_ALLOCATED_TAG bit to last link to tell + * whether it's allocated object or not. + */ + link->next = -1 << OBJ_ALLOCATED_TAG; + } kunmap_atomic(vaddr); page = next_page; off %= PAGE_SIZE; } - set_freeobj(zspage, - (unsigned long)location_to_obj(zspage->first_page, 0)); + set_freeobj(zspage, 0); } static void create_page_chain(struct zspage *zspage, struct page *pages[], @@ -1271,7 +1266,8 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle, { struct zspage *zspage; struct page *page; - unsigned long obj, obj_idx, off; + unsigned long obj, off; + unsigned int obj_idx; unsigned int class_idx; enum fullness_group fg; @@ -1295,7 +1291,7 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle, zspage = get_zspage(page); get_zspage_mapping(zspage, &class_idx, &fg); class = pool->size_class[class_idx]; - off = obj_idx_to_offset(page, obj_idx, class->size); + off = (class->size * obj_idx) & ~PAGE_MASK; area = &get_cpu_var(zs_map_area); area->vm_mm = mm; @@ -1324,7 +1320,8 @@ void zs_unmap_object(struct zs_pool *pool, unsigned long handle) { struct zspage *zspage; struct page *page; - unsigned long obj, obj_idx, off; + unsigned long obj, off; + unsigned int obj_idx; unsigned int class_idx; enum fullness_group fg; @@ -1336,7 +1333,7 @@ void zs_unmap_object(struct zs_pool *pool, unsigned long handle) zspage = get_zspage(page); get_zspage_mapping(zspage, &class_idx, &fg); class = pool->size_class[class_idx]; - off = obj_idx_to_offset(page, obj_idx, class->size); + off = (class->size * obj_idx) & ~PAGE_MASK; area = this_cpu_ptr(&zs_map_area); if (off + class->size <= PAGE_SIZE) @@ -1358,21 +1355,28 @@ EXPORT_SYMBOL_GPL(zs_unmap_object); static unsigned long obj_malloc(struct size_class *class, struct zspage *zspage, unsigned long handle) { + int i, nr_page, offset; unsigned long obj; struct link_free *link; struct page *m_page; - unsigned long m_objidx, m_offset; + unsigned long m_offset; void *vaddr; handle |= OBJ_ALLOCATED_TAG; obj = get_freeobj(zspage); - obj_to_location(obj, &m_page, &m_objidx); - m_offset = obj_idx_to_offset(m_page, m_objidx, class->size); + + offset = obj * class->size; + nr_page = offset >> PAGE_SHIFT; + m_offset = offset & ~PAGE_MASK; + m_page = get_first_page(zspage); + + for (i = 0; i < nr_page; i++) + m_page = get_next_page(m_page); vaddr = kmap_atomic(m_page); link = (struct link_free *)vaddr + m_offset / sizeof(*link); - set_freeobj(zspage, (unsigned long)link->next); + set_freeobj(zspage, link->next >> OBJ_ALLOCATED_TAG); if (!class->huge) /* record handle in the header of allocated chunk */ link->handle = handle; @@ -1384,6 +1388,8 @@ static unsigned long obj_malloc(struct size_class *class, mod_zspage_inuse(zspage, 1); zs_stat_inc(class, OBJ_USED, 1); + obj = location_to_obj(m_page, obj); + return obj; } @@ -1449,22 +1455,22 @@ static void obj_free(struct size_class *class, unsigned long obj) struct link_free *link; struct zspage *zspage; struct page *f_page; - unsigned long f_objidx, f_offset; + unsigned long f_offset; + unsigned int f_objidx; void *vaddr; obj &= ~OBJ_ALLOCATED_TAG; obj_to_location(obj, &f_page, &f_objidx); + f_offset = (class->size * f_objidx) & ~PAGE_MASK; zspage = get_zspage(f_page); - f_offset = obj_idx_to_offset(f_page, f_objidx, class->size); - vaddr = kmap_atomic(f_page); /* Insert this object in containing zspage's freelist */ link = (struct link_free *)(vaddr + f_offset); - link->next = (void *)get_freeobj(zspage); + link->next = get_freeobj(zspage) << OBJ_ALLOCATED_TAG; kunmap_atomic(vaddr); - set_freeobj(zspage, obj); + set_freeobj(zspage, f_objidx); mod_zspage_inuse(zspage, -1); zs_stat_dec(class, OBJ_USED, 1); } @@ -1473,7 +1479,8 @@ void zs_free(struct zs_pool *pool, unsigned long handle) { struct zspage *zspage; struct page *f_page; - unsigned long obj, f_objidx; + unsigned long obj; + unsigned int f_objidx; int class_idx; struct size_class *class; enum fullness_group fullness; @@ -1510,7 +1517,7 @@ static void zs_object_copy(struct size_class *class, unsigned long dst, unsigned long src) { struct page *s_page, *d_page; - unsigned long s_objidx, d_objidx; + unsigned int s_objidx, d_objidx; unsigned long s_off, d_off; void *s_addr, *d_addr; int s_size, d_size, size; @@ -1521,8 +1528,8 @@ static void zs_object_copy(struct size_class *class, unsigned long dst, obj_to_location(src, &s_page, &s_objidx); obj_to_location(dst, &d_page, &d_objidx); - s_off = obj_idx_to_offset(s_page, s_objidx, class->size); - d_off = obj_idx_to_offset(d_page, d_objidx, class->size); + s_off = (class->size * s_objidx) & ~PAGE_MASK; + d_off = (class->size * d_objidx) & ~PAGE_MASK; if (s_off + class->size > PAGE_SIZE) s_size = PAGE_SIZE - s_off; -- 2.39.5