Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 1 | /* |
| 2 | * zsmalloc memory allocator |
| 3 | * |
| 4 | * Copyright (C) 2011 Nitin Gupta |
| 5 | * |
| 6 | * This code is released using a dual license strategy: BSD/GPL |
| 7 | * You can choose the license that better fits your requirements. |
| 8 | * |
| 9 | * Released under the terms of 3-clause BSD License |
| 10 | * Released under the terms of GNU General Public License Version 2.0 |
| 11 | */ |
| 12 | |
| 13 | #ifdef CONFIG_ZSMALLOC_DEBUG |
| 14 | #define DEBUG |
| 15 | #endif |
| 16 | |
| 17 | #include <linux/module.h> |
| 18 | #include <linux/kernel.h> |
| 19 | #include <linux/bitops.h> |
| 20 | #include <linux/errno.h> |
| 21 | #include <linux/highmem.h> |
| 22 | #include <linux/init.h> |
| 23 | #include <linux/string.h> |
| 24 | #include <linux/slab.h> |
| 25 | #include <asm/tlbflush.h> |
| 26 | #include <asm/pgtable.h> |
| 27 | #include <linux/cpumask.h> |
| 28 | #include <linux/cpu.h> |
Seth Jennings | 0cbb613 | 2012-02-13 08:47:49 -0600 | [diff] [blame] | 29 | #include <linux/vmalloc.h> |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 30 | |
| 31 | #include "zsmalloc.h" |
| 32 | #include "zsmalloc_int.h" |
| 33 | |
| 34 | /* |
| 35 | * A zspage's class index and fullness group |
| 36 | * are encoded in its (first)page->mapping |
| 37 | */ |
| 38 | #define CLASS_IDX_BITS 28 |
| 39 | #define FULLNESS_BITS 4 |
| 40 | #define CLASS_IDX_MASK ((1 << CLASS_IDX_BITS) - 1) |
| 41 | #define FULLNESS_MASK ((1 << FULLNESS_BITS) - 1) |
| 42 | |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 43 | /* per-cpu VM mapping areas for zspage accesses that cross page boundaries */ |
| 44 | static DEFINE_PER_CPU(struct mapping_area, zs_map_area); |
| 45 | |
| 46 | static int is_first_page(struct page *page) |
| 47 | { |
| 48 | return test_bit(PG_private, &page->flags); |
| 49 | } |
| 50 | |
| 51 | static int is_last_page(struct page *page) |
| 52 | { |
| 53 | return test_bit(PG_private_2, &page->flags); |
| 54 | } |
| 55 | |
| 56 | static void get_zspage_mapping(struct page *page, unsigned int *class_idx, |
| 57 | enum fullness_group *fullness) |
| 58 | { |
| 59 | unsigned long m; |
| 60 | BUG_ON(!is_first_page(page)); |
| 61 | |
| 62 | m = (unsigned long)page->mapping; |
| 63 | *fullness = m & FULLNESS_MASK; |
| 64 | *class_idx = (m >> FULLNESS_BITS) & CLASS_IDX_MASK; |
| 65 | } |
| 66 | |
| 67 | static void set_zspage_mapping(struct page *page, unsigned int class_idx, |
| 68 | enum fullness_group fullness) |
| 69 | { |
| 70 | unsigned long m; |
| 71 | BUG_ON(!is_first_page(page)); |
| 72 | |
| 73 | m = ((class_idx & CLASS_IDX_MASK) << FULLNESS_BITS) | |
| 74 | (fullness & FULLNESS_MASK); |
| 75 | page->mapping = (struct address_space *)m; |
| 76 | } |
| 77 | |
| 78 | static int get_size_class_index(int size) |
| 79 | { |
| 80 | int idx = 0; |
| 81 | |
| 82 | if (likely(size > ZS_MIN_ALLOC_SIZE)) |
| 83 | idx = DIV_ROUND_UP(size - ZS_MIN_ALLOC_SIZE, |
| 84 | ZS_SIZE_CLASS_DELTA); |
| 85 | |
| 86 | return idx; |
| 87 | } |
| 88 | |
| 89 | static enum fullness_group get_fullness_group(struct page *page) |
| 90 | { |
| 91 | int inuse, max_objects; |
| 92 | enum fullness_group fg; |
| 93 | BUG_ON(!is_first_page(page)); |
| 94 | |
| 95 | inuse = page->inuse; |
| 96 | max_objects = page->objects; |
| 97 | |
| 98 | if (inuse == 0) |
| 99 | fg = ZS_EMPTY; |
| 100 | else if (inuse == max_objects) |
| 101 | fg = ZS_FULL; |
| 102 | else if (inuse <= max_objects / fullness_threshold_frac) |
| 103 | fg = ZS_ALMOST_EMPTY; |
| 104 | else |
| 105 | fg = ZS_ALMOST_FULL; |
| 106 | |
| 107 | return fg; |
| 108 | } |
| 109 | |
| 110 | static void insert_zspage(struct page *page, struct size_class *class, |
| 111 | enum fullness_group fullness) |
| 112 | { |
| 113 | struct page **head; |
| 114 | |
| 115 | BUG_ON(!is_first_page(page)); |
| 116 | |
| 117 | if (fullness >= _ZS_NR_FULLNESS_GROUPS) |
| 118 | return; |
| 119 | |
| 120 | head = &class->fullness_list[fullness]; |
| 121 | if (*head) |
| 122 | list_add_tail(&page->lru, &(*head)->lru); |
| 123 | |
| 124 | *head = page; |
| 125 | } |
| 126 | |
| 127 | static void remove_zspage(struct page *page, struct size_class *class, |
| 128 | enum fullness_group fullness) |
| 129 | { |
| 130 | struct page **head; |
| 131 | |
| 132 | BUG_ON(!is_first_page(page)); |
| 133 | |
| 134 | if (fullness >= _ZS_NR_FULLNESS_GROUPS) |
| 135 | return; |
| 136 | |
| 137 | head = &class->fullness_list[fullness]; |
| 138 | BUG_ON(!*head); |
| 139 | if (list_empty(&(*head)->lru)) |
| 140 | *head = NULL; |
| 141 | else if (*head == page) |
| 142 | *head = (struct page *)list_entry((*head)->lru.next, |
| 143 | struct page, lru); |
| 144 | |
| 145 | list_del_init(&page->lru); |
| 146 | } |
| 147 | |
| 148 | static enum fullness_group fix_fullness_group(struct zs_pool *pool, |
| 149 | struct page *page) |
| 150 | { |
| 151 | int class_idx; |
| 152 | struct size_class *class; |
| 153 | enum fullness_group currfg, newfg; |
| 154 | |
| 155 | BUG_ON(!is_first_page(page)); |
| 156 | |
| 157 | get_zspage_mapping(page, &class_idx, &currfg); |
| 158 | newfg = get_fullness_group(page); |
| 159 | if (newfg == currfg) |
| 160 | goto out; |
| 161 | |
| 162 | class = &pool->size_class[class_idx]; |
| 163 | remove_zspage(page, class, currfg); |
| 164 | insert_zspage(page, class, newfg); |
| 165 | set_zspage_mapping(page, class_idx, newfg); |
| 166 | |
| 167 | out: |
| 168 | return newfg; |
| 169 | } |
| 170 | |
| 171 | /* |
| 172 | * We have to decide on how many pages to link together |
| 173 | * to form a zspage for each size class. This is important |
| 174 | * to reduce wastage due to unusable space left at end of |
| 175 | * each zspage which is given as: |
| 176 | * wastage = Zp - Zp % size_class |
| 177 | * where Zp = zspage size = k * PAGE_SIZE where k = 1, 2, ... |
| 178 | * |
| 179 | * For example, for size class of 3/8 * PAGE_SIZE, we should |
| 180 | * link together 3 PAGE_SIZE sized pages to form a zspage |
| 181 | * since then we can perfectly fit in 8 such objects. |
| 182 | */ |
| 183 | static int get_zspage_order(int class_size) |
| 184 | { |
| 185 | int i, max_usedpc = 0; |
| 186 | /* zspage order which gives maximum used size per KB */ |
| 187 | int max_usedpc_order = 1; |
| 188 | |
Seth Jennings | 84d4faa | 2012-03-05 11:33:21 -0600 | [diff] [blame] | 189 | for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) { |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 190 | int zspage_size; |
| 191 | int waste, usedpc; |
| 192 | |
| 193 | zspage_size = i * PAGE_SIZE; |
| 194 | waste = zspage_size % class_size; |
| 195 | usedpc = (zspage_size - waste) * 100 / zspage_size; |
| 196 | |
| 197 | if (usedpc > max_usedpc) { |
| 198 | max_usedpc = usedpc; |
| 199 | max_usedpc_order = i; |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | return max_usedpc_order; |
| 204 | } |
| 205 | |
| 206 | /* |
| 207 | * A single 'zspage' is composed of many system pages which are |
| 208 | * linked together using fields in struct page. This function finds |
| 209 | * the first/head page, given any component page of a zspage. |
| 210 | */ |
| 211 | static struct page *get_first_page(struct page *page) |
| 212 | { |
| 213 | if (is_first_page(page)) |
| 214 | return page; |
| 215 | else |
| 216 | return page->first_page; |
| 217 | } |
| 218 | |
| 219 | static struct page *get_next_page(struct page *page) |
| 220 | { |
| 221 | struct page *next; |
| 222 | |
| 223 | if (is_last_page(page)) |
| 224 | next = NULL; |
| 225 | else if (is_first_page(page)) |
| 226 | next = (struct page *)page->private; |
| 227 | else |
| 228 | next = list_entry(page->lru.next, struct page, lru); |
| 229 | |
| 230 | return next; |
| 231 | } |
| 232 | |
| 233 | /* Encode <page, obj_idx> as a single handle value */ |
| 234 | static void *obj_location_to_handle(struct page *page, unsigned long obj_idx) |
| 235 | { |
| 236 | unsigned long handle; |
| 237 | |
| 238 | if (!page) { |
| 239 | BUG_ON(obj_idx); |
| 240 | return NULL; |
| 241 | } |
| 242 | |
| 243 | handle = page_to_pfn(page) << OBJ_INDEX_BITS; |
| 244 | handle |= (obj_idx & OBJ_INDEX_MASK); |
| 245 | |
| 246 | return (void *)handle; |
| 247 | } |
| 248 | |
| 249 | /* Decode <page, obj_idx> pair from the given object handle */ |
| 250 | static void obj_handle_to_location(void *handle, struct page **page, |
| 251 | unsigned long *obj_idx) |
| 252 | { |
| 253 | unsigned long hval = (unsigned long)handle; |
| 254 | |
| 255 | *page = pfn_to_page(hval >> OBJ_INDEX_BITS); |
| 256 | *obj_idx = hval & OBJ_INDEX_MASK; |
| 257 | } |
| 258 | |
| 259 | static unsigned long obj_idx_to_offset(struct page *page, |
| 260 | unsigned long obj_idx, int class_size) |
| 261 | { |
| 262 | unsigned long off = 0; |
| 263 | |
| 264 | if (!is_first_page(page)) |
| 265 | off = page->index; |
| 266 | |
| 267 | return off + obj_idx * class_size; |
| 268 | } |
| 269 | |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 270 | static void reset_page(struct page *page) |
| 271 | { |
| 272 | clear_bit(PG_private, &page->flags); |
| 273 | clear_bit(PG_private_2, &page->flags); |
| 274 | set_page_private(page, 0); |
| 275 | page->mapping = NULL; |
| 276 | page->freelist = NULL; |
| 277 | reset_page_mapcount(page); |
| 278 | } |
| 279 | |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 280 | static void free_zspage(struct page *first_page) |
| 281 | { |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 282 | struct page *nextp, *tmp, *head_extra; |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 283 | |
| 284 | BUG_ON(!is_first_page(first_page)); |
| 285 | BUG_ON(first_page->inuse); |
| 286 | |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 287 | head_extra = (struct page *)page_private(first_page); |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 288 | |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 289 | reset_page(first_page); |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 290 | __free_page(first_page); |
| 291 | |
| 292 | /* zspage with only 1 system page */ |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 293 | if (!head_extra) |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 294 | return; |
| 295 | |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 296 | list_for_each_entry_safe(nextp, tmp, &head_extra->lru, lru) { |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 297 | list_del(&nextp->lru); |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 298 | reset_page(nextp); |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 299 | __free_page(nextp); |
| 300 | } |
Nitin Gupta | f4477e9 | 2012-04-02 09:13:56 -0500 | [diff] [blame^] | 301 | reset_page(head_extra); |
| 302 | __free_page(head_extra); |
Nitin Gupta | 61989a8 | 2012-01-09 16:51:56 -0600 | [diff] [blame] | 303 | } |
| 304 | |
| 305 | /* Initialize a newly allocated zspage */ |
| 306 | static void init_zspage(struct page *first_page, struct size_class *class) |
| 307 | { |
| 308 | unsigned long off = 0; |
| 309 | struct page *page = first_page; |
| 310 | |
| 311 | BUG_ON(!is_first_page(first_page)); |
| 312 | while (page) { |
| 313 | struct page *next_page; |
| 314 | struct link_free *link; |
| 315 | unsigned int i, objs_on_page; |
| 316 | |
| 317 | /* |
| 318 | * page->index stores offset of first object starting |
| 319 | * in the page. For the first page, this is always 0, |
| 320 | * so we use first_page->index (aka ->freelist) to store |
| 321 | * head of corresponding zspage's freelist. |
| 322 | */ |
| 323 | if (page != first_page) |
| 324 | page->index = off; |
| 325 | |
| 326 | link = (struct link_free *)kmap_atomic(page) + |
| 327 | off / sizeof(*link); |
| 328 | objs_on_page = (PAGE_SIZE - off) / class->size; |
| 329 | |
| 330 | for (i = 1; i <= objs_on_page; i++) { |
| 331 | off += class->size; |
| 332 | if (off < PAGE_SIZE) { |
| 333 | link->next = obj_location_to_handle(page, i); |
| 334 | link += class->size / sizeof(*link); |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | /* |
| 339 | * We now come to the last (full or partial) object on this |
| 340 | * page, which must point to the first object on the next |
| 341 | * page (if present) |
| 342 | */ |
| 343 | next_page = get_next_page(page); |
| 344 | link->next = obj_location_to_handle(next_page, 0); |
| 345 | kunmap_atomic(link); |
| 346 | page = next_page; |
| 347 | off = (off + class->size) % PAGE_SIZE; |
| 348 | } |
| 349 | } |
| 350 | |
| 351 | /* |
| 352 | * Allocate a zspage for the given size class |
| 353 | */ |
| 354 | static struct page *alloc_zspage(struct size_class *class, gfp_t flags) |
| 355 | { |
| 356 | int i, error; |
| 357 | struct page *first_page = NULL; |
| 358 | |
| 359 | /* |
| 360 | * Allocate individual pages and link them together as: |
| 361 | * 1. first page->private = first sub-page |
| 362 | * 2. all sub-pages are linked together using page->lru |
| 363 | * 3. each sub-page is linked to the first page using page->first_page |
| 364 | * |
| 365 | * For each size class, First/Head pages are linked together using |
| 366 | * page->lru. Also, we set PG_private to identify the first page |
| 367 | * (i.e. no other sub-page has this flag set) and PG_private_2 to |
| 368 | * identify the last page. |
| 369 | */ |
| 370 | error = -ENOMEM; |
| 371 | for (i = 0; i < class->zspage_order; i++) { |
| 372 | struct page *page, *prev_page; |
| 373 | |
| 374 | page = alloc_page(flags); |
| 375 | if (!page) |
| 376 | goto cleanup; |
| 377 | |
| 378 | INIT_LIST_HEAD(&page->lru); |
| 379 | if (i == 0) { /* first page */ |
| 380 | set_bit(PG_private, &page->flags); |
| 381 | set_page_private(page, 0); |
| 382 | first_page = page; |
| 383 | first_page->inuse = 0; |
| 384 | } |
| 385 | if (i == 1) |
| 386 | first_page->private = (unsigned long)page; |
| 387 | if (i >= 1) |
| 388 | page->first_page = first_page; |
| 389 | if (i >= 2) |
| 390 | list_add(&page->lru, &prev_page->lru); |
| 391 | if (i == class->zspage_order - 1) /* last page */ |
| 392 | set_bit(PG_private_2, &page->flags); |
| 393 | |
| 394 | prev_page = page; |
| 395 | } |
| 396 | |
| 397 | init_zspage(first_page, class); |
| 398 | |
| 399 | first_page->freelist = obj_location_to_handle(first_page, 0); |
| 400 | /* Maximum number of objects we can store in this zspage */ |
| 401 | first_page->objects = class->zspage_order * PAGE_SIZE / class->size; |
| 402 | |
| 403 | error = 0; /* Success */ |
| 404 | |
| 405 | cleanup: |
| 406 | if (unlikely(error) && first_page) { |
| 407 | free_zspage(first_page); |
| 408 | first_page = NULL; |
| 409 | } |
| 410 | |
| 411 | return first_page; |
| 412 | } |
| 413 | |
| 414 | static struct page *find_get_zspage(struct size_class *class) |
| 415 | { |
| 416 | int i; |
| 417 | struct page *page; |
| 418 | |
| 419 | for (i = 0; i < _ZS_NR_FULLNESS_GROUPS; i++) { |
| 420 | page = class->fullness_list[i]; |
| 421 | if (page) |
| 422 | break; |
| 423 | } |
| 424 | |
| 425 | return page; |
| 426 | } |
| 427 | |
| 428 | |
| 429 | /* |
| 430 | * If this becomes a separate module, register zs_init() with |
| 431 | * module_init(), zs_exit with module_exit(), and remove zs_initialized |
| 432 | */ |
| 433 | static int zs_initialized; |
| 434 | |
| 435 | static int zs_cpu_notifier(struct notifier_block *nb, unsigned long action, |
| 436 | void *pcpu) |
| 437 | { |
| 438 | int cpu = (long)pcpu; |
| 439 | struct mapping_area *area; |
| 440 | |
| 441 | switch (action) { |
| 442 | case CPU_UP_PREPARE: |
| 443 | area = &per_cpu(zs_map_area, cpu); |
| 444 | if (area->vm) |
| 445 | break; |
| 446 | area->vm = alloc_vm_area(2 * PAGE_SIZE, area->vm_ptes); |
| 447 | if (!area->vm) |
| 448 | return notifier_from_errno(-ENOMEM); |
| 449 | break; |
| 450 | case CPU_DEAD: |
| 451 | case CPU_UP_CANCELED: |
| 452 | area = &per_cpu(zs_map_area, cpu); |
| 453 | if (area->vm) |
| 454 | free_vm_area(area->vm); |
| 455 | area->vm = NULL; |
| 456 | break; |
| 457 | } |
| 458 | |
| 459 | return NOTIFY_OK; |
| 460 | } |
| 461 | |
| 462 | static struct notifier_block zs_cpu_nb = { |
| 463 | .notifier_call = zs_cpu_notifier |
| 464 | }; |
| 465 | |
| 466 | static void zs_exit(void) |
| 467 | { |
| 468 | int cpu; |
| 469 | |
| 470 | for_each_online_cpu(cpu) |
| 471 | zs_cpu_notifier(NULL, CPU_DEAD, (void *)(long)cpu); |
| 472 | unregister_cpu_notifier(&zs_cpu_nb); |
| 473 | } |
| 474 | |
| 475 | static int zs_init(void) |
| 476 | { |
| 477 | int cpu, ret; |
| 478 | |
| 479 | register_cpu_notifier(&zs_cpu_nb); |
| 480 | for_each_online_cpu(cpu) { |
| 481 | ret = zs_cpu_notifier(NULL, CPU_UP_PREPARE, (void *)(long)cpu); |
| 482 | if (notifier_to_errno(ret)) |
| 483 | goto fail; |
| 484 | } |
| 485 | return 0; |
| 486 | fail: |
| 487 | zs_exit(); |
| 488 | return notifier_to_errno(ret); |
| 489 | } |
| 490 | |
| 491 | struct zs_pool *zs_create_pool(const char *name, gfp_t flags) |
| 492 | { |
| 493 | int i, error, ovhd_size; |
| 494 | struct zs_pool *pool; |
| 495 | |
| 496 | if (!name) |
| 497 | return NULL; |
| 498 | |
| 499 | ovhd_size = roundup(sizeof(*pool), PAGE_SIZE); |
| 500 | pool = kzalloc(ovhd_size, GFP_KERNEL); |
| 501 | if (!pool) |
| 502 | return NULL; |
| 503 | |
| 504 | for (i = 0; i < ZS_SIZE_CLASSES; i++) { |
| 505 | int size; |
| 506 | struct size_class *class; |
| 507 | |
| 508 | size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA; |
| 509 | if (size > ZS_MAX_ALLOC_SIZE) |
| 510 | size = ZS_MAX_ALLOC_SIZE; |
| 511 | |
| 512 | class = &pool->size_class[i]; |
| 513 | class->size = size; |
| 514 | class->index = i; |
| 515 | spin_lock_init(&class->lock); |
| 516 | class->zspage_order = get_zspage_order(size); |
| 517 | |
| 518 | } |
| 519 | |
| 520 | /* |
| 521 | * If this becomes a separate module, register zs_init with |
| 522 | * module_init, and remove this block |
| 523 | */ |
| 524 | if (!zs_initialized) { |
| 525 | error = zs_init(); |
| 526 | if (error) |
| 527 | goto cleanup; |
| 528 | zs_initialized = 1; |
| 529 | } |
| 530 | |
| 531 | pool->flags = flags; |
| 532 | pool->name = name; |
| 533 | |
| 534 | error = 0; /* Success */ |
| 535 | |
| 536 | cleanup: |
| 537 | if (error) { |
| 538 | zs_destroy_pool(pool); |
| 539 | pool = NULL; |
| 540 | } |
| 541 | |
| 542 | return pool; |
| 543 | } |
| 544 | EXPORT_SYMBOL_GPL(zs_create_pool); |
| 545 | |
| 546 | void zs_destroy_pool(struct zs_pool *pool) |
| 547 | { |
| 548 | int i; |
| 549 | |
| 550 | for (i = 0; i < ZS_SIZE_CLASSES; i++) { |
| 551 | int fg; |
| 552 | struct size_class *class = &pool->size_class[i]; |
| 553 | |
| 554 | for (fg = 0; fg < _ZS_NR_FULLNESS_GROUPS; fg++) { |
| 555 | if (class->fullness_list[fg]) { |
| 556 | pr_info("Freeing non-empty class with size " |
| 557 | "%db, fullness group %d\n", |
| 558 | class->size, fg); |
| 559 | } |
| 560 | } |
| 561 | } |
| 562 | kfree(pool); |
| 563 | } |
| 564 | EXPORT_SYMBOL_GPL(zs_destroy_pool); |
| 565 | |
| 566 | /** |
| 567 | * zs_malloc - Allocate block of given size from pool. |
| 568 | * @pool: pool to allocate from |
| 569 | * @size: size of block to allocate |
| 570 | * @page: page no. that holds the object |
| 571 | * @offset: location of object within page |
| 572 | * |
| 573 | * On success, <page, offset> identifies block allocated |
| 574 | * and 0 is returned. On failure, <page, offset> is set to |
| 575 | * 0 and -ENOMEM is returned. |
| 576 | * |
| 577 | * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail. |
| 578 | */ |
| 579 | void *zs_malloc(struct zs_pool *pool, size_t size) |
| 580 | { |
| 581 | void *obj; |
| 582 | struct link_free *link; |
| 583 | int class_idx; |
| 584 | struct size_class *class; |
| 585 | |
| 586 | struct page *first_page, *m_page; |
| 587 | unsigned long m_objidx, m_offset; |
| 588 | |
| 589 | if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE)) |
| 590 | return NULL; |
| 591 | |
| 592 | class_idx = get_size_class_index(size); |
| 593 | class = &pool->size_class[class_idx]; |
| 594 | BUG_ON(class_idx != class->index); |
| 595 | |
| 596 | spin_lock(&class->lock); |
| 597 | first_page = find_get_zspage(class); |
| 598 | |
| 599 | if (!first_page) { |
| 600 | spin_unlock(&class->lock); |
| 601 | first_page = alloc_zspage(class, pool->flags); |
| 602 | if (unlikely(!first_page)) |
| 603 | return NULL; |
| 604 | |
| 605 | set_zspage_mapping(first_page, class->index, ZS_EMPTY); |
| 606 | spin_lock(&class->lock); |
| 607 | class->pages_allocated += class->zspage_order; |
| 608 | } |
| 609 | |
| 610 | obj = first_page->freelist; |
| 611 | obj_handle_to_location(obj, &m_page, &m_objidx); |
| 612 | m_offset = obj_idx_to_offset(m_page, m_objidx, class->size); |
| 613 | |
| 614 | link = (struct link_free *)kmap_atomic(m_page) + |
| 615 | m_offset / sizeof(*link); |
| 616 | first_page->freelist = link->next; |
| 617 | memset(link, POISON_INUSE, sizeof(*link)); |
| 618 | kunmap_atomic(link); |
| 619 | |
| 620 | first_page->inuse++; |
| 621 | /* Now move the zspage to another fullness group, if required */ |
| 622 | fix_fullness_group(pool, first_page); |
| 623 | spin_unlock(&class->lock); |
| 624 | |
| 625 | return obj; |
| 626 | } |
| 627 | EXPORT_SYMBOL_GPL(zs_malloc); |
| 628 | |
| 629 | void zs_free(struct zs_pool *pool, void *obj) |
| 630 | { |
| 631 | struct link_free *link; |
| 632 | struct page *first_page, *f_page; |
| 633 | unsigned long f_objidx, f_offset; |
| 634 | |
| 635 | int class_idx; |
| 636 | struct size_class *class; |
| 637 | enum fullness_group fullness; |
| 638 | |
| 639 | if (unlikely(!obj)) |
| 640 | return; |
| 641 | |
| 642 | obj_handle_to_location(obj, &f_page, &f_objidx); |
| 643 | first_page = get_first_page(f_page); |
| 644 | |
| 645 | get_zspage_mapping(first_page, &class_idx, &fullness); |
| 646 | class = &pool->size_class[class_idx]; |
| 647 | f_offset = obj_idx_to_offset(f_page, f_objidx, class->size); |
| 648 | |
| 649 | spin_lock(&class->lock); |
| 650 | |
| 651 | /* Insert this object in containing zspage's freelist */ |
| 652 | link = (struct link_free *)((unsigned char *)kmap_atomic(f_page) |
| 653 | + f_offset); |
| 654 | link->next = first_page->freelist; |
| 655 | kunmap_atomic(link); |
| 656 | first_page->freelist = obj; |
| 657 | |
| 658 | first_page->inuse--; |
| 659 | fullness = fix_fullness_group(pool, first_page); |
| 660 | |
| 661 | if (fullness == ZS_EMPTY) |
| 662 | class->pages_allocated -= class->zspage_order; |
| 663 | |
| 664 | spin_unlock(&class->lock); |
| 665 | |
| 666 | if (fullness == ZS_EMPTY) |
| 667 | free_zspage(first_page); |
| 668 | } |
| 669 | EXPORT_SYMBOL_GPL(zs_free); |
| 670 | |
| 671 | void *zs_map_object(struct zs_pool *pool, void *handle) |
| 672 | { |
| 673 | struct page *page; |
| 674 | unsigned long obj_idx, off; |
| 675 | |
| 676 | unsigned int class_idx; |
| 677 | enum fullness_group fg; |
| 678 | struct size_class *class; |
| 679 | struct mapping_area *area; |
| 680 | |
| 681 | BUG_ON(!handle); |
| 682 | |
| 683 | obj_handle_to_location(handle, &page, &obj_idx); |
| 684 | get_zspage_mapping(get_first_page(page), &class_idx, &fg); |
| 685 | class = &pool->size_class[class_idx]; |
| 686 | off = obj_idx_to_offset(page, obj_idx, class->size); |
| 687 | |
| 688 | area = &get_cpu_var(zs_map_area); |
| 689 | if (off + class->size <= PAGE_SIZE) { |
| 690 | /* this object is contained entirely within a page */ |
| 691 | area->vm_addr = kmap_atomic(page); |
| 692 | } else { |
| 693 | /* this object spans two pages */ |
| 694 | struct page *nextp; |
| 695 | |
| 696 | nextp = get_next_page(page); |
| 697 | BUG_ON(!nextp); |
| 698 | |
| 699 | |
| 700 | set_pte(area->vm_ptes[0], mk_pte(page, PAGE_KERNEL)); |
| 701 | set_pte(area->vm_ptes[1], mk_pte(nextp, PAGE_KERNEL)); |
| 702 | |
| 703 | /* We pre-allocated VM area so mapping can never fail */ |
| 704 | area->vm_addr = area->vm->addr; |
| 705 | } |
| 706 | |
| 707 | return area->vm_addr + off; |
| 708 | } |
| 709 | EXPORT_SYMBOL_GPL(zs_map_object); |
| 710 | |
| 711 | void zs_unmap_object(struct zs_pool *pool, void *handle) |
| 712 | { |
| 713 | struct page *page; |
| 714 | unsigned long obj_idx, off; |
| 715 | |
| 716 | unsigned int class_idx; |
| 717 | enum fullness_group fg; |
| 718 | struct size_class *class; |
| 719 | struct mapping_area *area; |
| 720 | |
| 721 | BUG_ON(!handle); |
| 722 | |
| 723 | obj_handle_to_location(handle, &page, &obj_idx); |
| 724 | get_zspage_mapping(get_first_page(page), &class_idx, &fg); |
| 725 | class = &pool->size_class[class_idx]; |
| 726 | off = obj_idx_to_offset(page, obj_idx, class->size); |
| 727 | |
| 728 | area = &__get_cpu_var(zs_map_area); |
| 729 | if (off + class->size <= PAGE_SIZE) { |
| 730 | kunmap_atomic(area->vm_addr); |
| 731 | } else { |
| 732 | set_pte(area->vm_ptes[0], __pte(0)); |
| 733 | set_pte(area->vm_ptes[1], __pte(0)); |
| 734 | __flush_tlb_one((unsigned long)area->vm_addr); |
| 735 | __flush_tlb_one((unsigned long)area->vm_addr + PAGE_SIZE); |
| 736 | } |
| 737 | put_cpu_var(zs_map_area); |
| 738 | } |
| 739 | EXPORT_SYMBOL_GPL(zs_unmap_object); |
| 740 | |
| 741 | u64 zs_get_total_size_bytes(struct zs_pool *pool) |
| 742 | { |
| 743 | int i; |
| 744 | u64 npages = 0; |
| 745 | |
| 746 | for (i = 0; i < ZS_SIZE_CLASSES; i++) |
| 747 | npages += pool->size_class[i].pages_allocated; |
| 748 | |
| 749 | return npages << PAGE_SHIFT; |
| 750 | } |
| 751 | EXPORT_SYMBOL_GPL(zs_get_total_size_bytes); |