zsmalloc.c 47.7 KB
Newer Older
1 2 3 4
/*
 * zsmalloc memory allocator
 *
 * Copyright (C) 2011  Nitin Gupta
M
Minchan Kim 已提交
5
 * Copyright (C) 2012, 2013 Minchan Kim
6 7 8 9 10 11 12 13
 *
 * This code is released using a dual license strategy: BSD/GPL
 * You can choose the license that better fits your requirements.
 *
 * Released under the terms of 3-clause BSD License
 * Released under the terms of GNU General Public License Version 2.0
 */

N
Nitin Gupta 已提交
14 15 16 17 18
/*
 * Following is how we use various fields and flags of underlying
 * struct page(s) to form a zspage.
 *
 * Usage of struct page fields:
19
 *	page->private: points to the first component (0-order) page
N
Nitin Gupta 已提交
20 21 22 23 24 25 26 27 28
 *	page->index (union with page->freelist): offset of the first object
 *		starting in this page. For the first page, this is
 *		always 0, so we use this field (aka freelist) to point
 *		to the first free object in zspage.
 *	page->lru: links together all component pages (except the first page)
 *		of a zspage
 *
 *	For _first_ page only:
 *
29
 *	page->private: refers to the component page after the first page
30 31
 *		If the page is first_page for huge object, it stores handle.
 *		Look at size_class->huge.
N
Nitin Gupta 已提交
32 33 34 35 36 37 38 39
 *	page->freelist: points to the first free object in zspage.
 *		Free objects are linked together using in-place
 *		metadata.
 *	page->objects: maximum number of objects we can store in this
 *		zspage (class->zspage_order * PAGE_SIZE / class->size)
 *	page->lru: links together first pages of various zspages.
 *		Basically forming list of zspages in a fullness group.
 *	page->mapping: class index and fullness group of the zspage
40
 *	page->inuse: the number of objects that are used in this zspage
N
Nitin Gupta 已提交
41 42 43 44 45 46 47
 *
 * Usage of struct page flags:
 *	PG_private: identifies the first component page
 *	PG_private2: identifies the last component page
 *
 */

48 49
#include <linux/module.h>
#include <linux/kernel.h>
M
Minchan Kim 已提交
50
#include <linux/sched.h>
51 52 53 54 55 56 57 58 59
#include <linux/bitops.h>
#include <linux/errno.h>
#include <linux/highmem.h>
#include <linux/string.h>
#include <linux/slab.h>
#include <asm/tlbflush.h>
#include <asm/pgtable.h>
#include <linux/cpumask.h>
#include <linux/cpu.h>
60
#include <linux/vmalloc.h>
61
#include <linux/preempt.h>
62 63
#include <linux/spinlock.h>
#include <linux/types.h>
64
#include <linux/debugfs.h>
M
Minchan Kim 已提交
65
#include <linux/zsmalloc.h>
66
#include <linux/zpool.h>
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

/*
 * This must be power of 2 and greater than of equal to sizeof(link_free).
 * These two conditions ensure that any 'struct link_free' itself doesn't
 * span more than 1 page which avoids complex case of mapping 2 pages simply
 * to restore link_free pointer values.
 */
#define ZS_ALIGN		8

/*
 * A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)
 * pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
 */
#define ZS_MAX_ZSPAGE_ORDER 2
#define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)

83 84
#define ZS_HANDLE_SIZE (sizeof(unsigned long))

85 86
/*
 * Object location (<PFN>, <obj_idx>) is encoded as
N
Nitin Cupta 已提交
87
 * as single (unsigned long) handle value.
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
 *
 * Note that object index <obj_idx> is relative to system
 * page <PFN> it is stored in, so for each sub-page belonging
 * to a zspage, obj_idx starts with 0.
 *
 * This is made more complicated by various memory models and PAE.
 */

#ifndef MAX_PHYSMEM_BITS
#ifdef CONFIG_HIGHMEM64G
#define MAX_PHYSMEM_BITS 36
#else /* !CONFIG_HIGHMEM64G */
/*
 * If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
 * be PAGE_SHIFT
 */
#define MAX_PHYSMEM_BITS BITS_PER_LONG
#endif
#endif
#define _PFN_BITS		(MAX_PHYSMEM_BITS - PAGE_SHIFT)
M
Minchan Kim 已提交
108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

/*
 * Memory for allocating for handle keeps object position by
 * encoding <page, obj_idx> and the encoded value has a room
 * in least bit(ie, look at obj_to_location).
 * We use the bit to synchronize between object access by
 * user and migration.
 */
#define HANDLE_PIN_BIT	0

/*
 * Head in allocated object should have OBJ_ALLOCATED_TAG
 * to identify the object was allocated or not.
 * It's okay to add the status bit in the least bit because
 * header keeps handle which is 4byte-aligned address so we
 * have room for two bit at least.
 */
#define OBJ_ALLOCATED_TAG 1
#define OBJ_TAG_BITS 1
#define OBJ_INDEX_BITS	(BITS_PER_LONG - _PFN_BITS - OBJ_TAG_BITS)
128 129 130 131 132 133
#define OBJ_INDEX_MASK	((_AC(1, UL) << OBJ_INDEX_BITS) - 1)

#define MAX(a, b) ((a) >= (b) ? (a) : (b))
/* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
#define ZS_MIN_ALLOC_SIZE \
	MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
134
/* each chunk includes extra space to keep handle */
135
#define ZS_MAX_ALLOC_SIZE	PAGE_SIZE
136 137

/*
138
 * On systems with 4K page size, this gives 255 size classes! There is a
139 140 141 142 143 144 145 146 147 148 149
 * trader-off here:
 *  - Large number of size classes is potentially wasteful as free page are
 *    spread across these classes
 *  - Small number of size classes causes large internal fragmentation
 *  - Probably its better to use specific size classes (empirically
 *    determined). NOTE: all those class sizes must be set as multiple of
 *    ZS_ALIGN to make sure link_free itself never has to span 2 pages.
 *
 *  ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
 *  (reason above)
 */
150
#define ZS_SIZE_CLASS_DELTA	(PAGE_SIZE >> 8)
151 152 153 154 155 156 157 158 159 160 161 162 163

/*
 * We do not maintain any list for completely empty or full pages
 */
enum fullness_group {
	ZS_ALMOST_FULL,
	ZS_ALMOST_EMPTY,
	_ZS_NR_FULLNESS_GROUPS,

	ZS_EMPTY,
	ZS_FULL
};

164 165 166
enum zs_stat_type {
	OBJ_ALLOCATED,
	OBJ_USED,
M
Minchan Kim 已提交
167 168
	CLASS_ALMOST_FULL,
	CLASS_ALMOST_EMPTY,
169 170
};

171 172 173 174 175 176
#ifdef CONFIG_ZSMALLOC_STAT
#define NR_ZS_STAT_TYPE	(CLASS_ALMOST_EMPTY + 1)
#else
#define NR_ZS_STAT_TYPE	(OBJ_USED + 1)
#endif

177 178 179 180
struct zs_size_stat {
	unsigned long objs[NR_ZS_STAT_TYPE];
};

181 182
#ifdef CONFIG_ZSMALLOC_STAT
static struct dentry *zs_stat_root;
183 184
#endif

185 186 187 188 189
/*
 * number of size_classes
 */
static int zs_size_classes;

190 191 192 193 194
/*
 * We assign a page to ZS_ALMOST_EMPTY fullness group when:
 *	n <= N / f, where
 * n = number of allocated objects
 * N = total number of objects zspage can store
195
 * f = fullness_threshold_frac
196 197 198 199 200 201 202 203 204 205 206
 *
 * Similarly, we assign zspage to:
 *	ZS_ALMOST_FULL	when n > N / f
 *	ZS_EMPTY	when n == 0
 *	ZS_FULL		when n == N
 *
 * (see: fix_fullness_group())
 */
static const int fullness_threshold_frac = 4;

struct size_class {
207 208
	spinlock_t lock;
	struct page *fullness_list[_ZS_NR_FULLNESS_GROUPS];
209 210 211 212 213 214 215 216 217
	/*
	 * Size of objects stored in this class. Must be multiple
	 * of ZS_ALIGN.
	 */
	int size;
	unsigned int index;

	/* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
	int pages_per_zspage;
218
	struct zs_size_stat stats;
219

220 221
	/* huge object: pages_per_zspage == 1 && maxobj_per_zspage == 1 */
	bool huge;
222 223 224 225 226 227 228 229 230
};

/*
 * Placed within free objects to form a singly linked list.
 * For every zspage, first_page->freelist gives head of this list.
 *
 * This must be power of 2 and less than or equal to ZS_ALIGN
 */
struct link_free {
231 232 233 234 235 236 237 238 239 240 241
	union {
		/*
		 * Position of next free chunk (encodes <PFN, obj_idx>)
		 * It's valid for non-allocated object
		 */
		void *next;
		/*
		 * Handle of allocated object.
		 */
		unsigned long handle;
	};
242 243 244
};

struct zs_pool {
245
	const char *name;
246

247
	struct size_class **size_class;
248
	struct kmem_cache *handle_cachep;
249 250

	gfp_t flags;	/* allocation flags used when growing pool */
251
	atomic_long_t pages_allocated;
252

253
	struct zs_pool_stats stats;
254 255 256 257 258 259 260 261

	/* Compact classes */
	struct shrinker shrinker;
	/*
	 * To signify that register_shrinker() was successful
	 * and unregister_shrinker() will not Oops.
	 */
	bool shrinker_enabled;
262 263 264
#ifdef CONFIG_ZSMALLOC_STAT
	struct dentry *stat_dentry;
#endif
265
};
266 267 268 269 270 271 272 273 274 275

/*
 * A zspage's class index and fullness group
 * are encoded in its (first)page->mapping
 */
#define CLASS_IDX_BITS	28
#define FULLNESS_BITS	4
#define CLASS_IDX_MASK	((1 << CLASS_IDX_BITS) - 1)
#define FULLNESS_MASK	((1 << FULLNESS_BITS) - 1)

276
struct mapping_area {
277
#ifdef CONFIG_PGTABLE_MAPPING
278 279 280 281 282 283
	struct vm_struct *vm; /* vm area for mapping object that span pages */
#else
	char *vm_buf; /* copy buffer for objects that span pages */
#endif
	char *vm_addr; /* address of kmap_atomic()'ed pages */
	enum zs_mapmode vm_mm; /* mapping mode */
284
	bool huge;
285 286
};

287 288 289 290 291 292 293 294 295
static int create_handle_cache(struct zs_pool *pool)
{
	pool->handle_cachep = kmem_cache_create("zs_handle", ZS_HANDLE_SIZE,
					0, 0, NULL);
	return pool->handle_cachep ? 0 : 1;
}

static void destroy_handle_cache(struct zs_pool *pool)
{
296
	kmem_cache_destroy(pool->handle_cachep);
297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
}

static unsigned long alloc_handle(struct zs_pool *pool)
{
	return (unsigned long)kmem_cache_alloc(pool->handle_cachep,
		pool->flags & ~__GFP_HIGHMEM);
}

static void free_handle(struct zs_pool *pool, unsigned long handle)
{
	kmem_cache_free(pool->handle_cachep, (void *)handle);
}

static void record_obj(unsigned long handle, unsigned long obj)
{
	*(unsigned long *)handle = obj;
}

315 316 317 318
/* zpool driver */

#ifdef CONFIG_ZPOOL

319
static void *zs_zpool_create(const char *name, gfp_t gfp,
320
			     const struct zpool_ops *zpool_ops,
D
Dan Streetman 已提交
321
			     struct zpool *zpool)
322
{
323
	return zs_create_pool(name, gfp);
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374
}

static void zs_zpool_destroy(void *pool)
{
	zs_destroy_pool(pool);
}

static int zs_zpool_malloc(void *pool, size_t size, gfp_t gfp,
			unsigned long *handle)
{
	*handle = zs_malloc(pool, size);
	return *handle ? 0 : -1;
}
static void zs_zpool_free(void *pool, unsigned long handle)
{
	zs_free(pool, handle);
}

static int zs_zpool_shrink(void *pool, unsigned int pages,
			unsigned int *reclaimed)
{
	return -EINVAL;
}

static void *zs_zpool_map(void *pool, unsigned long handle,
			enum zpool_mapmode mm)
{
	enum zs_mapmode zs_mm;

	switch (mm) {
	case ZPOOL_MM_RO:
		zs_mm = ZS_MM_RO;
		break;
	case ZPOOL_MM_WO:
		zs_mm = ZS_MM_WO;
		break;
	case ZPOOL_MM_RW: /* fallthru */
	default:
		zs_mm = ZS_MM_RW;
		break;
	}

	return zs_map_object(pool, handle, zs_mm);
}
static void zs_zpool_unmap(void *pool, unsigned long handle)
{
	zs_unmap_object(pool, handle);
}

static u64 zs_zpool_total_size(void *pool)
{
375
	return zs_get_total_pages(pool) << PAGE_SHIFT;
376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
}

static struct zpool_driver zs_zpool_driver = {
	.type =		"zsmalloc",
	.owner =	THIS_MODULE,
	.create =	zs_zpool_create,
	.destroy =	zs_zpool_destroy,
	.malloc =	zs_zpool_malloc,
	.free =		zs_zpool_free,
	.shrink =	zs_zpool_shrink,
	.map =		zs_zpool_map,
	.unmap =	zs_zpool_unmap,
	.total_size =	zs_zpool_total_size,
};

391
MODULE_ALIAS("zpool-zsmalloc");
392 393
#endif /* CONFIG_ZPOOL */

M
Minchan Kim 已提交
394 395 396 397 398
static unsigned int get_maxobj_per_zspage(int size, int pages_per_zspage)
{
	return pages_per_zspage * PAGE_SIZE / size;
}

399 400 401 402 403
/* per-cpu VM mapping areas for zspage accesses that cross page boundaries */
static DEFINE_PER_CPU(struct mapping_area, zs_map_area);

static int is_first_page(struct page *page)
{
404
	return PagePrivate(page);
405 406 407 408
}

static int is_last_page(struct page *page)
{
409
	return PagePrivate2(page);
410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
}

static void get_zspage_mapping(struct page *page, unsigned int *class_idx,
				enum fullness_group *fullness)
{
	unsigned long m;
	BUG_ON(!is_first_page(page));

	m = (unsigned long)page->mapping;
	*fullness = m & FULLNESS_MASK;
	*class_idx = (m >> FULLNESS_BITS) & CLASS_IDX_MASK;
}

static void set_zspage_mapping(struct page *page, unsigned int class_idx,
				enum fullness_group fullness)
{
	unsigned long m;
	BUG_ON(!is_first_page(page));

	m = ((class_idx & CLASS_IDX_MASK) << FULLNESS_BITS) |
			(fullness & FULLNESS_MASK);
	page->mapping = (struct address_space *)m;
}

N
Nitin Cupta 已提交
434 435 436 437 438 439 440
/*
 * zsmalloc divides the pool into various size classes where each
 * class maintains a list of zspages where each zspage is divided
 * into equal sized chunks. Each allocation falls into one of these
 * classes depending on its size. This function returns index of the
 * size class which has chunk size big enough to hold the give size.
 */
441 442 443 444 445 446 447 448
static int get_size_class_index(int size)
{
	int idx = 0;

	if (likely(size > ZS_MIN_ALLOC_SIZE))
		idx = DIV_ROUND_UP(size - ZS_MIN_ALLOC_SIZE,
				ZS_SIZE_CLASS_DELTA);

449
	return min(zs_size_classes - 1, idx);
450 451
}

M
Minchan Kim 已提交
452 453 454
static inline void zs_stat_inc(struct size_class *class,
				enum zs_stat_type type, unsigned long cnt)
{
455 456
	if (type < NR_ZS_STAT_TYPE)
		class->stats.objs[type] += cnt;
M
Minchan Kim 已提交
457 458 459 460 461
}

static inline void zs_stat_dec(struct size_class *class,
				enum zs_stat_type type, unsigned long cnt)
{
462 463
	if (type < NR_ZS_STAT_TYPE)
		class->stats.objs[type] -= cnt;
M
Minchan Kim 已提交
464 465 466 467 468
}

static inline unsigned long zs_stat_get(struct size_class *class,
				enum zs_stat_type type)
{
469 470 471
	if (type < NR_ZS_STAT_TYPE)
		return class->stats.objs[type];
	return 0;
M
Minchan Kim 已提交
472 473
}

474 475
#ifdef CONFIG_ZSMALLOC_STAT

M
Minchan Kim 已提交
476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559
static int __init zs_stat_init(void)
{
	if (!debugfs_initialized())
		return -ENODEV;

	zs_stat_root = debugfs_create_dir("zsmalloc", NULL);
	if (!zs_stat_root)
		return -ENOMEM;

	return 0;
}

static void __exit zs_stat_exit(void)
{
	debugfs_remove_recursive(zs_stat_root);
}

static int zs_stats_size_show(struct seq_file *s, void *v)
{
	int i;
	struct zs_pool *pool = s->private;
	struct size_class *class;
	int objs_per_zspage;
	unsigned long class_almost_full, class_almost_empty;
	unsigned long obj_allocated, obj_used, pages_used;
	unsigned long total_class_almost_full = 0, total_class_almost_empty = 0;
	unsigned long total_objs = 0, total_used_objs = 0, total_pages = 0;

	seq_printf(s, " %5s %5s %11s %12s %13s %10s %10s %16s\n",
			"class", "size", "almost_full", "almost_empty",
			"obj_allocated", "obj_used", "pages_used",
			"pages_per_zspage");

	for (i = 0; i < zs_size_classes; i++) {
		class = pool->size_class[i];

		if (class->index != i)
			continue;

		spin_lock(&class->lock);
		class_almost_full = zs_stat_get(class, CLASS_ALMOST_FULL);
		class_almost_empty = zs_stat_get(class, CLASS_ALMOST_EMPTY);
		obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
		obj_used = zs_stat_get(class, OBJ_USED);
		spin_unlock(&class->lock);

		objs_per_zspage = get_maxobj_per_zspage(class->size,
				class->pages_per_zspage);
		pages_used = obj_allocated / objs_per_zspage *
				class->pages_per_zspage;

		seq_printf(s, " %5u %5u %11lu %12lu %13lu %10lu %10lu %16d\n",
			i, class->size, class_almost_full, class_almost_empty,
			obj_allocated, obj_used, pages_used,
			class->pages_per_zspage);

		total_class_almost_full += class_almost_full;
		total_class_almost_empty += class_almost_empty;
		total_objs += obj_allocated;
		total_used_objs += obj_used;
		total_pages += pages_used;
	}

	seq_puts(s, "\n");
	seq_printf(s, " %5s %5s %11lu %12lu %13lu %10lu %10lu\n",
			"Total", "", total_class_almost_full,
			total_class_almost_empty, total_objs,
			total_used_objs, total_pages);

	return 0;
}

static int zs_stats_size_open(struct inode *inode, struct file *file)
{
	return single_open(file, zs_stats_size_show, inode->i_private);
}

static const struct file_operations zs_stat_size_ops = {
	.open           = zs_stats_size_open,
	.read           = seq_read,
	.llseek         = seq_lseek,
	.release        = single_release,
};

560
static int zs_pool_stat_create(const char *name, struct zs_pool *pool)
M
Minchan Kim 已提交
561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
{
	struct dentry *entry;

	if (!zs_stat_root)
		return -ENODEV;

	entry = debugfs_create_dir(name, zs_stat_root);
	if (!entry) {
		pr_warn("debugfs dir <%s> creation failed\n", name);
		return -ENOMEM;
	}
	pool->stat_dentry = entry;

	entry = debugfs_create_file("classes", S_IFREG | S_IRUGO,
			pool->stat_dentry, pool, &zs_stat_size_ops);
	if (!entry) {
		pr_warn("%s: debugfs file entry <%s> creation failed\n",
				name, "classes");
		return -ENOMEM;
	}

	return 0;
}

static void zs_pool_stat_destroy(struct zs_pool *pool)
{
	debugfs_remove_recursive(pool->stat_dentry);
}

#else /* CONFIG_ZSMALLOC_STAT */
static int __init zs_stat_init(void)
{
	return 0;
}

static void __exit zs_stat_exit(void)
{
}

600
static inline int zs_pool_stat_create(const char *name, struct zs_pool *pool)
M
Minchan Kim 已提交
601 602 603 604 605 606 607 608 609 610
{
	return 0;
}

static inline void zs_pool_stat_destroy(struct zs_pool *pool)
{
}
#endif


N
Nitin Cupta 已提交
611 612 613 614 615 616 617
/*
 * For each size class, zspages are divided into different groups
 * depending on how "full" they are. This was done so that we could
 * easily find empty or nearly empty zspages when we try to shrink
 * the pool (not yet implemented). This function returns fullness
 * status of the given page.
 */
618 619 620 621 622 623 624 625 626 627 628 629 630
static enum fullness_group get_fullness_group(struct page *page)
{
	int inuse, max_objects;
	enum fullness_group fg;
	BUG_ON(!is_first_page(page));

	inuse = page->inuse;
	max_objects = page->objects;

	if (inuse == 0)
		fg = ZS_EMPTY;
	else if (inuse == max_objects)
		fg = ZS_FULL;
M
Minchan Kim 已提交
631
	else if (inuse <= 3 * max_objects / fullness_threshold_frac)
632 633 634 635 636 637 638
		fg = ZS_ALMOST_EMPTY;
	else
		fg = ZS_ALMOST_FULL;

	return fg;
}

N
Nitin Cupta 已提交
639 640 641 642 643 644
/*
 * Each size class maintains various freelists and zspages are assigned
 * to one of these freelists based on the number of live objects they
 * have. This functions inserts the given zspage into the freelist
 * identified by <class, fullness_group>.
 */
645 646 647 648 649 650 651 652 653 654
static void insert_zspage(struct page *page, struct size_class *class,
				enum fullness_group fullness)
{
	struct page **head;

	BUG_ON(!is_first_page(page));

	if (fullness >= _ZS_NR_FULLNESS_GROUPS)
		return;

M
Minchan Kim 已提交
655 656
	zs_stat_inc(class, fullness == ZS_ALMOST_EMPTY ?
			CLASS_ALMOST_EMPTY : CLASS_ALMOST_FULL, 1);
657 658 659 660 661 662 663 664 665 666 667 668 669 670

	head = &class->fullness_list[fullness];
	if (!*head) {
		*head = page;
		return;
	}

	/*
	 * We want to see more ZS_FULL pages and less almost
	 * empty/full. Put pages with higher ->inuse first.
	 */
	list_add_tail(&page->lru, &(*head)->lru);
	if (page->inuse >= (*head)->inuse)
		*head = page;
671 672
}

N
Nitin Cupta 已提交
673 674 675 676
/*
 * This function removes the given zspage from the freelist identified
 * by <class, fullness_group>.
 */
677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695
static void remove_zspage(struct page *page, struct size_class *class,
				enum fullness_group fullness)
{
	struct page **head;

	BUG_ON(!is_first_page(page));

	if (fullness >= _ZS_NR_FULLNESS_GROUPS)
		return;

	head = &class->fullness_list[fullness];
	BUG_ON(!*head);
	if (list_empty(&(*head)->lru))
		*head = NULL;
	else if (*head == page)
		*head = (struct page *)list_entry((*head)->lru.next,
					struct page, lru);

	list_del_init(&page->lru);
M
Minchan Kim 已提交
696 697
	zs_stat_dec(class, fullness == ZS_ALMOST_EMPTY ?
			CLASS_ALMOST_EMPTY : CLASS_ALMOST_FULL, 1);
698 699
}

N
Nitin Cupta 已提交
700 701 702 703 704 705 706 707 708
/*
 * Each size class maintains zspages in different fullness groups depending
 * on the number of live objects they contain. When allocating or freeing
 * objects, the fullness status of the page can change, say, from ALMOST_FULL
 * to ALMOST_EMPTY when freeing an object. This function checks if such
 * a status change has occurred for the given page and accordingly moves the
 * page from the freelist of the old fullness group to that of the new
 * fullness group.
 */
709
static enum fullness_group fix_fullness_group(struct size_class *class,
710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734
						struct page *page)
{
	int class_idx;
	enum fullness_group currfg, newfg;

	BUG_ON(!is_first_page(page));

	get_zspage_mapping(page, &class_idx, &currfg);
	newfg = get_fullness_group(page);
	if (newfg == currfg)
		goto out;

	remove_zspage(page, class, currfg);
	insert_zspage(page, class, newfg);
	set_zspage_mapping(page, class_idx, newfg);

out:
	return newfg;
}

/*
 * We have to decide on how many pages to link together
 * to form a zspage for each size class. This is important
 * to reduce wastage due to unusable space left at end of
 * each zspage which is given as:
735 736
 *     wastage = Zp % class_size
 *     usage = Zp - wastage
737 738 739 740 741 742
 * where Zp = zspage size = k * PAGE_SIZE where k = 1, 2, ...
 *
 * For example, for size class of 3/8 * PAGE_SIZE, we should
 * link together 3 PAGE_SIZE sized pages to form a zspage
 * since then we can perfectly fit in 8 such objects.
 */
743
static int get_pages_per_zspage(int class_size)
744 745 746 747 748
{
	int i, max_usedpc = 0;
	/* zspage order which gives maximum used size per KB */
	int max_usedpc_order = 1;

749
	for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) {
750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775
		int zspage_size;
		int waste, usedpc;

		zspage_size = i * PAGE_SIZE;
		waste = zspage_size % class_size;
		usedpc = (zspage_size - waste) * 100 / zspage_size;

		if (usedpc > max_usedpc) {
			max_usedpc = usedpc;
			max_usedpc_order = i;
		}
	}

	return max_usedpc_order;
}

/*
 * A single 'zspage' is composed of many system pages which are
 * linked together using fields in struct page. This function finds
 * the first/head page, given any component page of a zspage.
 */
static struct page *get_first_page(struct page *page)
{
	if (is_first_page(page))
		return page;
	else
776
		return (struct page *)page_private(page);
777 778 779 780 781 782 783 784 785
}

static struct page *get_next_page(struct page *page)
{
	struct page *next;

	if (is_last_page(page))
		next = NULL;
	else if (is_first_page(page))
786
		next = (struct page *)page_private(page);
787 788 789 790 791 792
	else
		next = list_entry(page->lru.next, struct page, lru);

	return next;
}

793 794
/*
 * Encode <page, obj_idx> as a single handle value.
M
Minchan Kim 已提交
795
 * We use the least bit of handle for tagging.
796
 */
M
Minchan Kim 已提交
797
static void *location_to_obj(struct page *page, unsigned long obj_idx)
798
{
M
Minchan Kim 已提交
799
	unsigned long obj;
800 801 802 803 804 805

	if (!page) {
		BUG_ON(obj_idx);
		return NULL;
	}

M
Minchan Kim 已提交
806 807 808
	obj = page_to_pfn(page) << OBJ_INDEX_BITS;
	obj |= ((obj_idx) & OBJ_INDEX_MASK);
	obj <<= OBJ_TAG_BITS;
809

M
Minchan Kim 已提交
810
	return (void *)obj;
811 812
}

813 814 815
/*
 * Decode <page, obj_idx> pair from the given object handle. We adjust the
 * decoded obj_idx back to its original value since it was adjusted in
M
Minchan Kim 已提交
816
 * location_to_obj().
817
 */
M
Minchan Kim 已提交
818
static void obj_to_location(unsigned long obj, struct page **page,
819 820
				unsigned long *obj_idx)
{
M
Minchan Kim 已提交
821 822 823
	obj >>= OBJ_TAG_BITS;
	*page = pfn_to_page(obj >> OBJ_INDEX_BITS);
	*obj_idx = (obj & OBJ_INDEX_MASK);
824 825
}

826 827 828 829 830
static unsigned long handle_to_obj(unsigned long handle)
{
	return *(unsigned long *)handle;
}

831 832
static unsigned long obj_to_head(struct size_class *class, struct page *page,
			void *obj)
M
Minchan Kim 已提交
833
{
834 835
	if (class->huge) {
		VM_BUG_ON(!is_first_page(page));
836
		return page_private(page);
837 838
	} else
		return *(unsigned long *)obj;
M
Minchan Kim 已提交
839 840
}

841 842 843 844 845 846 847 848 849 850 851
static unsigned long obj_idx_to_offset(struct page *page,
				unsigned long obj_idx, int class_size)
{
	unsigned long off = 0;

	if (!is_first_page(page))
		off = page->index;

	return off + obj_idx * class_size;
}

M
Minchan Kim 已提交
852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870
static inline int trypin_tag(unsigned long handle)
{
	unsigned long *ptr = (unsigned long *)handle;

	return !test_and_set_bit_lock(HANDLE_PIN_BIT, ptr);
}

static void pin_tag(unsigned long handle)
{
	while (!trypin_tag(handle));
}

static void unpin_tag(unsigned long handle)
{
	unsigned long *ptr = (unsigned long *)handle;

	clear_bit_unlock(HANDLE_PIN_BIT, ptr);
}

N
Nitin Gupta 已提交
871 872 873 874 875 876 877
static void reset_page(struct page *page)
{
	clear_bit(PG_private, &page->flags);
	clear_bit(PG_private_2, &page->flags);
	set_page_private(page, 0);
	page->mapping = NULL;
	page->freelist = NULL;
878
	page_mapcount_reset(page);
N
Nitin Gupta 已提交
879 880
}

881 882
static void free_zspage(struct page *first_page)
{
N
Nitin Gupta 已提交
883
	struct page *nextp, *tmp, *head_extra;
884 885 886 887

	BUG_ON(!is_first_page(first_page));
	BUG_ON(first_page->inuse);

N
Nitin Gupta 已提交
888
	head_extra = (struct page *)page_private(first_page);
889

N
Nitin Gupta 已提交
890
	reset_page(first_page);
891 892 893
	__free_page(first_page);

	/* zspage with only 1 system page */
N
Nitin Gupta 已提交
894
	if (!head_extra)
895 896
		return;

N
Nitin Gupta 已提交
897
	list_for_each_entry_safe(nextp, tmp, &head_extra->lru, lru) {
898
		list_del(&nextp->lru);
N
Nitin Gupta 已提交
899
		reset_page(nextp);
900 901
		__free_page(nextp);
	}
N
Nitin Gupta 已提交
902 903
	reset_page(head_extra);
	__free_page(head_extra);
904 905 906 907 908 909 910 911 912 913 914 915
}

/* Initialize a newly allocated zspage */
static void init_zspage(struct page *first_page, struct size_class *class)
{
	unsigned long off = 0;
	struct page *page = first_page;

	BUG_ON(!is_first_page(first_page));
	while (page) {
		struct page *next_page;
		struct link_free *link;
916
		unsigned int i = 1;
917
		void *vaddr;
918 919 920 921 922 923 924 925 926 927

		/*
		 * page->index stores offset of first object starting
		 * in the page. For the first page, this is always 0,
		 * so we use first_page->index (aka ->freelist) to store
		 * head of corresponding zspage's freelist.
		 */
		if (page != first_page)
			page->index = off;

928 929
		vaddr = kmap_atomic(page);
		link = (struct link_free *)vaddr + off / sizeof(*link);
930 931

		while ((off += class->size) < PAGE_SIZE) {
M
Minchan Kim 已提交
932
			link->next = location_to_obj(page, i++);
933
			link += class->size / sizeof(*link);
934 935 936 937 938 939 940 941
		}

		/*
		 * We now come to the last (full or partial) object on this
		 * page, which must point to the first object on the next
		 * page (if present)
		 */
		next_page = get_next_page(page);
M
Minchan Kim 已提交
942
		link->next = location_to_obj(next_page, 0);
943
		kunmap_atomic(vaddr);
944
		page = next_page;
945
		off %= PAGE_SIZE;
946 947 948 949 950 951 952 953 954
	}
}

/*
 * Allocate a zspage for the given size class
 */
static struct page *alloc_zspage(struct size_class *class, gfp_t flags)
{
	int i, error;
955
	struct page *first_page = NULL, *uninitialized_var(prev_page);
956 957 958 959 960

	/*
	 * Allocate individual pages and link them together as:
	 * 1. first page->private = first sub-page
	 * 2. all sub-pages are linked together using page->lru
961
	 * 3. each sub-page is linked to the first page using page->private
962 963 964 965 966 967 968
	 *
	 * For each size class, First/Head pages are linked together using
	 * page->lru. Also, we set PG_private to identify the first page
	 * (i.e. no other sub-page has this flag set) and PG_private_2 to
	 * identify the last page.
	 */
	error = -ENOMEM;
969
	for (i = 0; i < class->pages_per_zspage; i++) {
970
		struct page *page;
971 972 973 974 975 976 977

		page = alloc_page(flags);
		if (!page)
			goto cleanup;

		INIT_LIST_HEAD(&page->lru);
		if (i == 0) {	/* first page */
978
			SetPagePrivate(page);
979 980 981 982 983
			set_page_private(page, 0);
			first_page = page;
			first_page->inuse = 0;
		}
		if (i == 1)
984
			set_page_private(first_page, (unsigned long)page);
985
		if (i >= 1)
986
			set_page_private(page, (unsigned long)first_page);
987 988
		if (i >= 2)
			list_add(&page->lru, &prev_page->lru);
989
		if (i == class->pages_per_zspage - 1)	/* last page */
990
			SetPagePrivate2(page);
991 992 993 994 995
		prev_page = page;
	}

	init_zspage(first_page, class);

M
Minchan Kim 已提交
996
	first_page->freelist = location_to_obj(first_page, 0);
997
	/* Maximum number of objects we can store in this zspage */
998
	first_page->objects = class->pages_per_zspage * PAGE_SIZE / class->size;
999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024

	error = 0; /* Success */

cleanup:
	if (unlikely(error) && first_page) {
		free_zspage(first_page);
		first_page = NULL;
	}

	return first_page;
}

static struct page *find_get_zspage(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)
			break;
	}

	return page;
}

1025
#ifdef CONFIG_PGTABLE_MAPPING
1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
static inline int __zs_cpu_up(struct mapping_area *area)
{
	/*
	 * Make sure we don't leak memory if a cpu UP notification
	 * and zs_init() race and both call zs_cpu_up() on the same cpu
	 */
	if (area->vm)
		return 0;
	area->vm = alloc_vm_area(PAGE_SIZE * 2, NULL);
	if (!area->vm)
		return -ENOMEM;
	return 0;
}

static inline void __zs_cpu_down(struct mapping_area *area)
{
	if (area->vm)
		free_vm_area(area->vm);
	area->vm = NULL;
}

static inline void *__zs_map_object(struct mapping_area *area,
				struct page *pages[2], int off, int size)
{
1050
	BUG_ON(map_vm_area(area->vm, PAGE_KERNEL, pages));
1051 1052 1053 1054 1055 1056 1057 1058 1059
	area->vm_addr = area->vm->addr;
	return area->vm_addr + off;
}

static inline void __zs_unmap_object(struct mapping_area *area,
				struct page *pages[2], int off, int size)
{
	unsigned long addr = (unsigned long)area->vm_addr;

1060
	unmap_kernel_range(addr, PAGE_SIZE * 2);
1061 1062
}

1063
#else /* CONFIG_PGTABLE_MAPPING */
1064 1065 1066 1067 1068 1069 1070 1071 1072

static inline int __zs_cpu_up(struct mapping_area *area)
{
	/*
	 * Make sure we don't leak memory if a cpu UP notification
	 * and zs_init() race and both call zs_cpu_up() on the same cpu
	 */
	if (area->vm_buf)
		return 0;
1073
	area->vm_buf = kmalloc(ZS_MAX_ALLOC_SIZE, GFP_KERNEL);
1074 1075 1076 1077 1078 1079 1080
	if (!area->vm_buf)
		return -ENOMEM;
	return 0;
}

static inline void __zs_cpu_down(struct mapping_area *area)
{
1081
	kfree(area->vm_buf);
1082 1083 1084 1085 1086
	area->vm_buf = NULL;
}

static void *__zs_map_object(struct mapping_area *area,
			struct page *pages[2], int off, int size)
1087 1088 1089
{
	int sizes[2];
	void *addr;
1090
	char *buf = area->vm_buf;
1091

1092 1093 1094 1095 1096 1097
	/* disable page faults to match kmap_atomic() return conditions */
	pagefault_disable();

	/* no read fastpath */
	if (area->vm_mm == ZS_MM_WO)
		goto out;
1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108

	sizes[0] = PAGE_SIZE - off;
	sizes[1] = size - sizes[0];

	/* copy object to per-cpu buffer */
	addr = kmap_atomic(pages[0]);
	memcpy(buf, addr + off, sizes[0]);
	kunmap_atomic(addr);
	addr = kmap_atomic(pages[1]);
	memcpy(buf + sizes[0], addr, sizes[1]);
	kunmap_atomic(addr);
1109 1110
out:
	return area->vm_buf;
1111 1112
}

1113 1114
static void __zs_unmap_object(struct mapping_area *area,
			struct page *pages[2], int off, int size)
1115 1116 1117
{
	int sizes[2];
	void *addr;
1118
	char *buf;
1119

1120 1121 1122
	/* no write fastpath */
	if (area->vm_mm == ZS_MM_RO)
		goto out;
1123

1124 1125 1126 1127 1128 1129
	buf = area->vm_buf;
	if (!area->huge) {
		buf = buf + ZS_HANDLE_SIZE;
		size -= ZS_HANDLE_SIZE;
		off += ZS_HANDLE_SIZE;
	}
1130

1131 1132 1133 1134 1135 1136 1137 1138 1139 1140
	sizes[0] = PAGE_SIZE - off;
	sizes[1] = size - sizes[0];

	/* copy per-cpu buffer to object */
	addr = kmap_atomic(pages[0]);
	memcpy(addr + off, buf, sizes[0]);
	kunmap_atomic(addr);
	addr = kmap_atomic(pages[1]);
	memcpy(addr, buf + sizes[0], sizes[1]);
	kunmap_atomic(addr);
1141 1142 1143 1144

out:
	/* enable page faults to match kunmap_atomic() return conditions */
	pagefault_enable();
1145
}
1146

1147
#endif /* CONFIG_PGTABLE_MAPPING */
1148

1149 1150 1151
static int zs_cpu_notifier(struct notifier_block *nb, unsigned long action,
				void *pcpu)
{
1152
	int ret, cpu = (long)pcpu;
1153 1154 1155 1156 1157
	struct mapping_area *area;

	switch (action) {
	case CPU_UP_PREPARE:
		area = &per_cpu(zs_map_area, cpu);
1158 1159 1160
		ret = __zs_cpu_up(area);
		if (ret)
			return notifier_from_errno(ret);
1161 1162 1163 1164
		break;
	case CPU_DEAD:
	case CPU_UP_CANCELED:
		area = &per_cpu(zs_map_area, cpu);
1165
		__zs_cpu_down(area);
1166 1167 1168 1169 1170 1171 1172 1173 1174 1175
		break;
	}

	return NOTIFY_OK;
}

static struct notifier_block zs_cpu_nb = {
	.notifier_call = zs_cpu_notifier
};

1176
static int zs_register_cpu_notifier(void)
1177
{
1178
	int cpu, uninitialized_var(ret);
1179

1180 1181 1182
	cpu_notifier_register_begin();

	__register_cpu_notifier(&zs_cpu_nb);
1183 1184
	for_each_online_cpu(cpu) {
		ret = zs_cpu_notifier(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
1185 1186
		if (notifier_to_errno(ret))
			break;
1187
	}
1188 1189

	cpu_notifier_register_done();
1190 1191
	return notifier_to_errno(ret);
}
1192

1193
static void zs_unregister_cpu_notifier(void)
1194
{
1195
	int cpu;
1196

1197
	cpu_notifier_register_begin();
1198

1199 1200 1201
	for_each_online_cpu(cpu)
		zs_cpu_notifier(NULL, CPU_DEAD, (void *)(long)cpu);
	__unregister_cpu_notifier(&zs_cpu_nb);
1202

1203
	cpu_notifier_register_done();
1204 1205
}

1206
static void init_zs_size_classes(void)
1207
{
1208
	int nr;
1209

1210 1211 1212
	nr = (ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) / ZS_SIZE_CLASS_DELTA + 1;
	if ((ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) % ZS_SIZE_CLASS_DELTA)
		nr += 1;
1213

1214
	zs_size_classes = nr;
1215 1216
}

1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228
static bool can_merge(struct size_class *prev, int size, int pages_per_zspage)
{
	if (prev->pages_per_zspage != pages_per_zspage)
		return false;

	if (get_maxobj_per_zspage(prev->size, prev->pages_per_zspage)
		!= get_maxobj_per_zspage(size, pages_per_zspage))
		return false;

	return true;
}

M
Minchan Kim 已提交
1229 1230 1231 1232 1233 1234 1235
static bool zspage_full(struct page *page)
{
	BUG_ON(!is_first_page(page));

	return page->inuse == page->objects;
}

1236 1237 1238 1239 1240 1241
unsigned long zs_get_total_pages(struct zs_pool *pool)
{
	return atomic_long_read(&pool->pages_allocated);
}
EXPORT_SYMBOL_GPL(zs_get_total_pages);

1242
/**
1243 1244 1245
 * zs_map_object - get address of allocated object from handle.
 * @pool: pool from which the object was allocated
 * @handle: handle returned from zs_malloc
1246
 *
1247 1248 1249
 * Before using an object allocated from zs_malloc, it must be mapped using
 * this function. When done with the object, it must be unmapped using
 * zs_unmap_object.
1250
 *
1251 1252 1253 1254
 * Only one object can be mapped per cpu at a time. There is no protection
 * against nested mappings.
 *
 * This function returns with preemption and page faults disabled.
1255
 */
1256 1257
void *zs_map_object(struct zs_pool *pool, unsigned long handle,
			enum zs_mapmode mm)
1258
{
1259
	struct page *page;
1260
	unsigned long obj, obj_idx, off;
1261

1262 1263 1264 1265 1266
	unsigned int class_idx;
	enum fullness_group fg;
	struct size_class *class;
	struct mapping_area *area;
	struct page *pages[2];
1267
	void *ret;
1268

1269
	BUG_ON(!handle);
1270

1271
	/*
1272 1273 1274
	 * Because we use per-cpu mapping areas shared among the
	 * pools/users, we can't allow mapping in interrupt context
	 * because it can corrupt another users mappings.
1275
	 */
1276
	BUG_ON(in_interrupt());
1277

M
Minchan Kim 已提交
1278 1279 1280
	/* From now on, migration cannot move the object */
	pin_tag(handle);

1281 1282
	obj = handle_to_obj(handle);
	obj_to_location(obj, &page, &obj_idx);
1283 1284 1285
	get_zspage_mapping(get_first_page(page), &class_idx, &fg);
	class = pool->size_class[class_idx];
	off = obj_idx_to_offset(page, obj_idx, class->size);
1286

1287 1288 1289 1290 1291
	area = &get_cpu_var(zs_map_area);
	area->vm_mm = mm;
	if (off + class->size <= PAGE_SIZE) {
		/* this object is contained entirely within a page */
		area->vm_addr = kmap_atomic(page);
1292 1293
		ret = area->vm_addr + off;
		goto out;
1294 1295
	}

1296 1297 1298 1299
	/* this object spans two pages */
	pages[0] = page;
	pages[1] = get_next_page(page);
	BUG_ON(!pages[1]);
1300

1301 1302
	ret = __zs_map_object(area, pages, off, class->size);
out:
1303 1304 1305 1306
	if (!class->huge)
		ret += ZS_HANDLE_SIZE;

	return ret;
1307
}
1308
EXPORT_SYMBOL_GPL(zs_map_object);
1309

1310
void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
1311
{
1312
	struct page *page;
1313
	unsigned long obj, obj_idx, off;
1314

1315 1316 1317 1318
	unsigned int class_idx;
	enum fullness_group fg;
	struct size_class *class;
	struct mapping_area *area;
1319

1320
	BUG_ON(!handle);
1321

1322 1323
	obj = handle_to_obj(handle);
	obj_to_location(obj, &page, &obj_idx);
1324 1325 1326
	get_zspage_mapping(get_first_page(page), &class_idx, &fg);
	class = pool->size_class[class_idx];
	off = obj_idx_to_offset(page, obj_idx, class->size);
1327

1328 1329 1330 1331 1332
	area = this_cpu_ptr(&zs_map_area);
	if (off + class->size <= PAGE_SIZE)
		kunmap_atomic(area->vm_addr);
	else {
		struct page *pages[2];
1333

1334 1335 1336 1337 1338 1339 1340
		pages[0] = page;
		pages[1] = get_next_page(page);
		BUG_ON(!pages[1]);

		__zs_unmap_object(area, pages, off, class->size);
	}
	put_cpu_var(zs_map_area);
M
Minchan Kim 已提交
1341
	unpin_tag(handle);
1342
}
1343
EXPORT_SYMBOL_GPL(zs_unmap_object);
1344

1345 1346 1347 1348 1349 1350 1351 1352 1353 1354
static unsigned long obj_malloc(struct page *first_page,
		struct size_class *class, unsigned long handle)
{
	unsigned long obj;
	struct link_free *link;

	struct page *m_page;
	unsigned long m_objidx, m_offset;
	void *vaddr;

M
Minchan Kim 已提交
1355
	handle |= OBJ_ALLOCATED_TAG;
1356 1357 1358 1359 1360 1361 1362
	obj = (unsigned long)first_page->freelist;
	obj_to_location(obj, &m_page, &m_objidx);
	m_offset = obj_idx_to_offset(m_page, m_objidx, class->size);

	vaddr = kmap_atomic(m_page);
	link = (struct link_free *)vaddr + m_offset / sizeof(*link);
	first_page->freelist = link->next;
1363 1364 1365 1366 1367 1368
	if (!class->huge)
		/* record handle in the header of allocated chunk */
		link->handle = handle;
	else
		/* record handle in first_page->private */
		set_page_private(first_page, handle);
1369 1370 1371 1372 1373 1374 1375 1376
	kunmap_atomic(vaddr);
	first_page->inuse++;
	zs_stat_inc(class, OBJ_USED, 1);

	return obj;
}


1377 1378 1379 1380 1381
/**
 * zs_malloc - Allocate block of given size from pool.
 * @pool: pool to allocate from
 * @size: size of block to allocate
 *
1382
 * On success, handle to the allocated object is returned,
1383
 * otherwise 0.
1384 1385
 * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
 */
1386
unsigned long zs_malloc(struct zs_pool *pool, size_t size)
1387
{
1388
	unsigned long handle, obj;
1389
	struct size_class *class;
1390
	struct page *first_page;
1391

1392
	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
1393 1394 1395 1396
		return 0;

	handle = alloc_handle(pool);
	if (!handle)
1397
		return 0;
1398

1399 1400
	/* extra space in chunk to keep the handle */
	size += ZS_HANDLE_SIZE;
1401
	class = pool->size_class[get_size_class_index(size)];
1402 1403 1404 1405 1406 1407 1408

	spin_lock(&class->lock);
	first_page = find_get_zspage(class);

	if (!first_page) {
		spin_unlock(&class->lock);
		first_page = alloc_zspage(class, pool->flags);
1409 1410
		if (unlikely(!first_page)) {
			free_handle(pool, handle);
1411
			return 0;
1412
		}
1413 1414

		set_zspage_mapping(first_page, class->index, ZS_EMPTY);
1415 1416
		atomic_long_add(class->pages_per_zspage,
					&pool->pages_allocated);
1417

1418
		spin_lock(&class->lock);
1419 1420
		zs_stat_inc(class, OBJ_ALLOCATED, get_maxobj_per_zspage(
				class->size, class->pages_per_zspage));
1421 1422
	}

1423
	obj = obj_malloc(first_page, class, handle);
1424
	/* Now move the zspage to another fullness group, if required */
1425
	fix_fullness_group(class, first_page);
1426
	record_obj(handle, obj);
1427 1428
	spin_unlock(&class->lock);

1429
	return handle;
1430 1431 1432
}
EXPORT_SYMBOL_GPL(zs_malloc);

1433 1434
static void obj_free(struct zs_pool *pool, struct size_class *class,
			unsigned long obj)
1435 1436 1437
{
	struct link_free *link;
	struct page *first_page, *f_page;
1438
	unsigned long f_objidx, f_offset;
1439
	void *vaddr;
1440

1441
	BUG_ON(!obj);
1442

M
Minchan Kim 已提交
1443
	obj &= ~OBJ_ALLOCATED_TAG;
1444
	obj_to_location(obj, &f_page, &f_objidx);
1445 1446 1447 1448
	first_page = get_first_page(f_page);

	f_offset = obj_idx_to_offset(f_page, f_objidx, class->size);

1449
	vaddr = kmap_atomic(f_page);
1450 1451

	/* Insert this object in containing zspage's freelist */
1452
	link = (struct link_free *)(vaddr + f_offset);
1453
	link->next = first_page->freelist;
1454 1455
	if (class->huge)
		set_page_private(first_page, 0);
1456
	kunmap_atomic(vaddr);
1457
	first_page->freelist = (void *)obj;
1458
	first_page->inuse--;
1459
	zs_stat_dec(class, OBJ_USED, 1);
1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472
}

void zs_free(struct zs_pool *pool, unsigned long handle)
{
	struct page *first_page, *f_page;
	unsigned long obj, f_objidx;
	int class_idx;
	struct size_class *class;
	enum fullness_group fullness;

	if (unlikely(!handle))
		return;

M
Minchan Kim 已提交
1473
	pin_tag(handle);
1474 1475 1476 1477 1478 1479 1480 1481 1482 1483
	obj = handle_to_obj(handle);
	obj_to_location(obj, &f_page, &f_objidx);
	first_page = get_first_page(f_page);

	get_zspage_mapping(first_page, &class_idx, &fullness);
	class = pool->size_class[class_idx];

	spin_lock(&class->lock);
	obj_free(pool, class, obj);
	fullness = fix_fullness_group(class, first_page);
M
Minchan Kim 已提交
1484
	if (fullness == ZS_EMPTY) {
1485 1486
		zs_stat_dec(class, OBJ_ALLOCATED, get_maxobj_per_zspage(
				class->size, class->pages_per_zspage));
M
Minchan Kim 已提交
1487 1488 1489 1490
		atomic_long_sub(class->pages_per_zspage,
				&pool->pages_allocated);
		free_zspage(first_page);
	}
1491
	spin_unlock(&class->lock);
M
Minchan Kim 已提交
1492
	unpin_tag(handle);
1493

M
Minchan Kim 已提交
1494 1495 1496 1497
	free_handle(pool, handle);
}
EXPORT_SYMBOL_GPL(zs_free);

1498
static void zs_object_copy(unsigned long dst, unsigned long src,
M
Minchan Kim 已提交
1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532
				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 = obj_idx_to_offset(s_page, s_objidx, class->size);
	d_off = obj_idx_to_offset(d_page, d_objidx, class->size);

	if (s_off + class->size > PAGE_SIZE)
		s_size = PAGE_SIZE - s_off;

	if (d_off + class->size > PAGE_SIZE)
		d_size = PAGE_SIZE - d_off;

	s_addr = kmap_atomic(s_page);
	d_addr = kmap_atomic(d_page);

	while (1) {
		size = min(s_size, d_size);
		memcpy(d_addr + d_off, s_addr + s_off, size);
		written += size;

		if (written == class->size)
			break;

1533 1534 1535 1536 1537 1538
		s_off += size;
		s_size -= size;
		d_off += size;
		d_size -= size;

		if (s_off >= PAGE_SIZE) {
M
Minchan Kim 已提交
1539 1540 1541 1542 1543 1544 1545 1546 1547 1548
			kunmap_atomic(d_addr);
			kunmap_atomic(s_addr);
			s_page = get_next_page(s_page);
			BUG_ON(!s_page);
			s_addr = kmap_atomic(s_page);
			d_addr = kmap_atomic(d_page);
			s_size = class->size - written;
			s_off = 0;
		}

1549
		if (d_off >= PAGE_SIZE) {
M
Minchan Kim 已提交
1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579
			kunmap_atomic(d_addr);
			d_page = get_next_page(d_page);
			BUG_ON(!d_page);
			d_addr = kmap_atomic(d_page);
			d_size = class->size - written;
			d_off = 0;
		}
	}

	kunmap_atomic(d_addr);
	kunmap_atomic(s_addr);
}

/*
 * Find alloced object in zspage from index object and
 * return handle.
 */
static unsigned long find_alloced_obj(struct page *page, int index,
					struct size_class *class)
{
	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) {
1580
		head = obj_to_head(class, page, addr + offset);
M
Minchan Kim 已提交
1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635
		if (head & OBJ_ALLOCATED_TAG) {
			handle = head & ~OBJ_ALLOCATED_TAG;
			if (trypin_tag(handle))
				break;
			handle = 0;
		}

		offset += class->size;
		index++;
	}

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

	while (1) {
		handle = find_alloced_obj(s_page, index, class);
		if (!handle) {
			s_page = get_next_page(s_page);
			if (!s_page)
				break;
			index = 0;
			continue;
		}

		/* Stop if there is no more space */
		if (zspage_full(d_page)) {
			unpin_tag(handle);
			ret = -ENOMEM;
			break;
		}

		used_obj = handle_to_obj(handle);
		free_obj = obj_malloc(d_page, class, handle);
1636
		zs_object_copy(free_obj, used_obj, class);
M
Minchan Kim 已提交
1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649
		index++;
		record_obj(handle, free_obj);
		unpin_tag(handle);
		obj_free(pool, class, used_obj);
	}

	/* Remember last position in this iteration */
	cc->s_page = s_page;
	cc->index = index;

	return ret;
}

1650
static struct page *isolate_target_page(struct size_class *class)
M
Minchan Kim 已提交
1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665
{
	int i;
	struct page *page;

	for (i = 0; i < _ZS_NR_FULLNESS_GROUPS; i++) {
		page = class->fullness_list[i];
		if (page) {
			remove_zspage(page, class, i);
			break;
		}
	}

	return page;
}

1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676
/*
 * putback_zspage - add @first_page into right class's fullness list
 * @pool: target pool
 * @class: destination class
 * @first_page: target page
 *
 * Return @fist_page's fullness_group
 */
static enum fullness_group putback_zspage(struct zs_pool *pool,
			struct size_class *class,
			struct page *first_page)
M
Minchan Kim 已提交
1677 1678 1679 1680 1681
{
	enum fullness_group fullness;

	BUG_ON(!is_first_page(first_page));

1682
	fullness = get_fullness_group(first_page);
M
Minchan Kim 已提交
1683
	insert_zspage(first_page, class, fullness);
1684 1685
	set_zspage_mapping(first_page, class->index, fullness);

1686
	if (fullness == ZS_EMPTY) {
M
Minchan Kim 已提交
1687 1688
		zs_stat_dec(class, OBJ_ALLOCATED, get_maxobj_per_zspage(
			class->size, class->pages_per_zspage));
1689 1690
		atomic_long_sub(class->pages_per_zspage,
				&pool->pages_allocated);
M
Minchan Kim 已提交
1691

1692
		free_zspage(first_page);
1693
	}
1694 1695

	return fullness;
1696
}
M
Minchan Kim 已提交
1697 1698 1699

static struct page *isolate_source_page(struct size_class *class)
{
1700 1701 1702 1703 1704 1705 1706
	int i;
	struct page *page = NULL;

	for (i = ZS_ALMOST_EMPTY; i >= ZS_ALMOST_FULL; i--) {
		page = class->fullness_list[i];
		if (!page)
			continue;
M
Minchan Kim 已提交
1707

1708 1709 1710
		remove_zspage(page, class, i);
		break;
	}
M
Minchan Kim 已提交
1711 1712 1713 1714

	return page;
}

1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729
/*
 *
 * Based on the number of unused allocated objects calculate
 * and return the number of pages that we can free.
 */
static unsigned long zs_can_compact(struct size_class *class)
{
	unsigned long obj_wasted;

	obj_wasted = zs_stat_get(class, OBJ_ALLOCATED) -
		zs_stat_get(class, OBJ_USED);

	obj_wasted /= get_maxobj_per_zspage(class->size,
			class->pages_per_zspage);

1730
	return obj_wasted * class->pages_per_zspage;
1731 1732
}

1733
static void __zs_compact(struct zs_pool *pool, struct size_class *class)
M
Minchan Kim 已提交
1734 1735 1736 1737 1738 1739 1740 1741 1742 1743
{
	struct zs_compact_control cc;
	struct page *src_page;
	struct page *dst_page = NULL;

	spin_lock(&class->lock);
	while ((src_page = isolate_source_page(class))) {

		BUG_ON(!is_first_page(src_page));

1744 1745 1746
		if (!zs_can_compact(class))
			break;

M
Minchan Kim 已提交
1747 1748 1749
		cc.index = 0;
		cc.s_page = src_page;

1750
		while ((dst_page = isolate_target_page(class))) {
M
Minchan Kim 已提交
1751 1752
			cc.d_page = dst_page;
			/*
1753 1754
			 * If there is no more space in dst_page, resched
			 * and see if anyone had allocated another zspage.
M
Minchan Kim 已提交
1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766
			 */
			if (!migrate_zspage(pool, class, &cc))
				break;

			putback_zspage(pool, class, dst_page);
		}

		/* Stop if we couldn't find slot */
		if (dst_page == NULL)
			break;

		putback_zspage(pool, class, dst_page);
1767
		if (putback_zspage(pool, class, src_page) == ZS_EMPTY)
1768
			pool->stats.pages_compacted += class->pages_per_zspage;
M
Minchan Kim 已提交
1769 1770 1771 1772 1773 1774 1775 1776
		spin_unlock(&class->lock);
		cond_resched();
		spin_lock(&class->lock);
	}

	if (src_page)
		putback_zspage(pool, class, src_page);

1777
	spin_unlock(&class->lock);
M
Minchan Kim 已提交
1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790
}

unsigned long zs_compact(struct zs_pool *pool)
{
	int i;
	struct size_class *class;

	for (i = zs_size_classes - 1; i >= 0; i--) {
		class = pool->size_class[i];
		if (!class)
			continue;
		if (class->index != i)
			continue;
1791
		__zs_compact(pool, class);
M
Minchan Kim 已提交
1792 1793
	}

1794
	return pool->stats.pages_compacted;
M
Minchan Kim 已提交
1795 1796
}
EXPORT_SYMBOL_GPL(zs_compact);
1797

1798 1799 1800 1801 1802 1803
void zs_pool_stats(struct zs_pool *pool, struct zs_pool_stats *stats)
{
	memcpy(stats, &pool->stats, sizeof(struct zs_pool_stats));
}
EXPORT_SYMBOL_GPL(zs_pool_stats);

1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861
static unsigned long zs_shrinker_scan(struct shrinker *shrinker,
		struct shrink_control *sc)
{
	unsigned long pages_freed;
	struct zs_pool *pool = container_of(shrinker, struct zs_pool,
			shrinker);

	pages_freed = pool->stats.pages_compacted;
	/*
	 * Compact classes and calculate compaction delta.
	 * Can run concurrently with a manually triggered
	 * (by user) compaction.
	 */
	pages_freed = zs_compact(pool) - pages_freed;

	return pages_freed ? pages_freed : SHRINK_STOP;
}

static unsigned long zs_shrinker_count(struct shrinker *shrinker,
		struct shrink_control *sc)
{
	int i;
	struct size_class *class;
	unsigned long pages_to_free = 0;
	struct zs_pool *pool = container_of(shrinker, struct zs_pool,
			shrinker);

	for (i = zs_size_classes - 1; i >= 0; i--) {
		class = pool->size_class[i];
		if (!class)
			continue;
		if (class->index != i)
			continue;

		pages_to_free += zs_can_compact(class);
	}

	return pages_to_free;
}

static void zs_unregister_shrinker(struct zs_pool *pool)
{
	if (pool->shrinker_enabled) {
		unregister_shrinker(&pool->shrinker);
		pool->shrinker_enabled = false;
	}
}

static int zs_register_shrinker(struct zs_pool *pool)
{
	pool->shrinker.scan_objects = zs_shrinker_scan;
	pool->shrinker.count_objects = zs_shrinker_count;
	pool->shrinker.batch = 0;
	pool->shrinker.seeks = DEFAULT_SEEKS;

	return register_shrinker(&pool->shrinker);
}

1862
/**
1863 1864
 * zs_create_pool - Creates an allocation pool to work from.
 * @flags: allocation flags used to allocate pool metadata
1865
 *
1866 1867
 * This function must be called before anything when using
 * the zsmalloc allocator.
1868
 *
1869 1870
 * On success, a pointer to the newly created pool is returned,
 * otherwise NULL.
1871
 */
1872
struct zs_pool *zs_create_pool(const char *name, gfp_t flags)
1873
{
1874 1875 1876
	int i;
	struct zs_pool *pool;
	struct size_class *prev_class = NULL;
1877

1878 1879 1880
	pool = kzalloc(sizeof(*pool), GFP_KERNEL);
	if (!pool)
		return NULL;
1881

1882 1883 1884 1885 1886 1887
	pool->size_class = kcalloc(zs_size_classes, sizeof(struct size_class *),
			GFP_KERNEL);
	if (!pool->size_class) {
		kfree(pool);
		return NULL;
	}
1888

1889 1890 1891 1892 1893 1894 1895
	pool->name = kstrdup(name, GFP_KERNEL);
	if (!pool->name)
		goto err;

	if (create_handle_cache(pool))
		goto err;

1896
	/*
1897 1898
	 * Iterate reversly, because, size of size_class that we want to use
	 * for merging should be larger or equal to current size.
1899
	 */
1900 1901 1902 1903
	for (i = zs_size_classes - 1; i >= 0; i--) {
		int size;
		int pages_per_zspage;
		struct size_class *class;
1904

1905 1906 1907 1908
		size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
		if (size > ZS_MAX_ALLOC_SIZE)
			size = ZS_MAX_ALLOC_SIZE;
		pages_per_zspage = get_pages_per_zspage(size);
1909

1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932
		/*
		 * size_class is used for normal zsmalloc operation such
		 * as alloc/free for that size. Although it is natural that we
		 * have one size_class for each size, there is a chance that we
		 * can get more memory utilization if we use one size_class for
		 * many different sizes whose size_class have same
		 * characteristics. So, we makes size_class point to
		 * previous size_class if possible.
		 */
		if (prev_class) {
			if (can_merge(prev_class, size, pages_per_zspage)) {
				pool->size_class[i] = prev_class;
				continue;
			}
		}

		class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
		if (!class)
			goto err;

		class->size = size;
		class->index = i;
		class->pages_per_zspage = pages_per_zspage;
1933 1934 1935
		if (pages_per_zspage == 1 &&
			get_maxobj_per_zspage(size, pages_per_zspage) == 1)
			class->huge = true;
1936 1937 1938 1939
		spin_lock_init(&class->lock);
		pool->size_class[i] = class;

		prev_class = class;
1940 1941
	}

1942
	pool->flags = flags;
1943

1944 1945 1946
	if (zs_pool_stat_create(name, pool))
		goto err;

1947 1948 1949 1950 1951 1952
	/*
	 * Not critical, we still can use the pool
	 * and user can trigger compaction manually.
	 */
	if (zs_register_shrinker(pool) == 0)
		pool->shrinker_enabled = true;
1953 1954 1955 1956 1957
	return pool;

err:
	zs_destroy_pool(pool);
	return NULL;
1958
}
1959
EXPORT_SYMBOL_GPL(zs_create_pool);
1960

1961
void zs_destroy_pool(struct zs_pool *pool)
1962
{
1963
	int i;
1964

1965
	zs_unregister_shrinker(pool);
1966 1967
	zs_pool_stat_destroy(pool);

1968 1969 1970
	for (i = 0; i < zs_size_classes; i++) {
		int fg;
		struct size_class *class = pool->size_class[i];
1971

1972 1973
		if (!class)
			continue;
1974

1975 1976
		if (class->index != i)
			continue;
1977

1978 1979 1980 1981 1982 1983 1984 1985
		for (fg = 0; fg < _ZS_NR_FULLNESS_GROUPS; fg++) {
			if (class->fullness_list[fg]) {
				pr_info("Freeing non-empty class with size %db, fullness group %d\n",
					class->size, fg);
			}
		}
		kfree(class);
	}
1986

1987
	destroy_handle_cache(pool);
1988
	kfree(pool->size_class);
1989
	kfree(pool->name);
1990 1991 1992
	kfree(pool);
}
EXPORT_SYMBOL_GPL(zs_destroy_pool);
1993

1994 1995 1996 1997
static int __init zs_init(void)
{
	int ret = zs_register_cpu_notifier();

1998 1999
	if (ret)
		goto notifier_fail;
2000 2001 2002 2003 2004 2005

	init_zs_size_classes();

#ifdef CONFIG_ZPOOL
	zpool_register_driver(&zs_zpool_driver);
#endif
2006 2007 2008 2009 2010 2011

	ret = zs_stat_init();
	if (ret) {
		pr_err("zs stat initialization failed\n");
		goto stat_fail;
	}
2012
	return 0;
2013 2014 2015 2016 2017 2018 2019 2020 2021

stat_fail:
#ifdef CONFIG_ZPOOL
	zpool_unregister_driver(&zs_zpool_driver);
#endif
notifier_fail:
	zs_unregister_cpu_notifier();

	return ret;
2022 2023
}

2024
static void __exit zs_exit(void)
2025
{
2026 2027 2028 2029
#ifdef CONFIG_ZPOOL
	zpool_unregister_driver(&zs_zpool_driver);
#endif
	zs_unregister_cpu_notifier();
2030 2031

	zs_stat_exit();
2032
}
2033 2034 2035 2036 2037 2038

module_init(zs_init);
module_exit(zs_exit);

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Nitin Gupta <ngupta@vflare.org>");