zsmalloc.c 61 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552
  1. /*
  2. * zsmalloc memory allocator
  3. *
  4. * Copyright (C) 2011 Nitin Gupta
  5. * Copyright (C) 2012, 2013 Minchan Kim
  6. *
  7. * This code is released using a dual license strategy: BSD/GPL
  8. * You can choose the license that better fits your requirements.
  9. *
  10. * Released under the terms of 3-clause BSD License
  11. * Released under the terms of GNU General Public License Version 2.0
  12. */
  13. /*
  14. * Following is how we use various fields and flags of underlying
  15. * struct page(s) to form a zspage.
  16. *
  17. * Usage of struct page fields:
  18. * page->private: points to zspage
  19. * page->freelist(index): links together all component pages of a zspage
  20. * For the huge page, this is always 0, so we use this field
  21. * to store handle.
  22. * page->units: first object offset in a subpage of zspage
  23. *
  24. * Usage of struct page flags:
  25. * PG_private: identifies the first component page
  26. * PG_owner_priv_1: identifies the huge component page
  27. *
  28. */
  29. #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  30. #include <linux/module.h>
  31. #include <linux/kernel.h>
  32. #include <linux/sched.h>
  33. #include <linux/magic.h>
  34. #include <linux/bitops.h>
  35. #include <linux/errno.h>
  36. #include <linux/highmem.h>
  37. #include <linux/string.h>
  38. #include <linux/slab.h>
  39. #include <linux/pgtable.h>
  40. #include <asm/tlbflush.h>
  41. #include <linux/cpumask.h>
  42. #include <linux/cpu.h>
  43. #include <linux/vmalloc.h>
  44. #include <linux/preempt.h>
  45. #include <linux/spinlock.h>
  46. #include <linux/shrinker.h>
  47. #include <linux/types.h>
  48. #include <linux/debugfs.h>
  49. #include <linux/zsmalloc.h>
  50. #include <linux/zpool.h>
  51. #include <linux/mount.h>
  52. #include <linux/pseudo_fs.h>
  53. #include <linux/migrate.h>
  54. #include <linux/wait.h>
  55. #include <linux/pagemap.h>
  56. #include <linux/fs.h>
  57. #define ZSPAGE_MAGIC 0x58
  58. /*
  59. * This must be power of 2 and greater than of equal to sizeof(link_free).
  60. * These two conditions ensure that any 'struct link_free' itself doesn't
  61. * span more than 1 page which avoids complex case of mapping 2 pages simply
  62. * to restore link_free pointer values.
  63. */
  64. #define ZS_ALIGN 8
  65. /*
  66. * A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)
  67. * pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
  68. */
  69. #define ZS_MAX_ZSPAGE_ORDER 2
  70. #define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)
  71. #define ZS_HANDLE_SIZE (sizeof(unsigned long))
  72. /*
  73. * Object location (<PFN>, <obj_idx>) is encoded as
  74. * a single (unsigned long) handle value.
  75. *
  76. * Note that object index <obj_idx> starts from 0.
  77. *
  78. * This is made more complicated by various memory models and PAE.
  79. */
  80. #ifndef MAX_POSSIBLE_PHYSMEM_BITS
  81. #ifdef MAX_PHYSMEM_BITS
  82. #define MAX_POSSIBLE_PHYSMEM_BITS MAX_PHYSMEM_BITS
  83. #else
  84. /*
  85. * If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
  86. * be PAGE_SHIFT
  87. */
  88. #define MAX_POSSIBLE_PHYSMEM_BITS BITS_PER_LONG
  89. #endif
  90. #endif
  91. #define _PFN_BITS (MAX_POSSIBLE_PHYSMEM_BITS - PAGE_SHIFT)
  92. /*
  93. * Memory for allocating for handle keeps object position by
  94. * encoding <page, obj_idx> and the encoded value has a room
  95. * in least bit(ie, look at obj_to_location).
  96. * We use the bit to synchronize between object access by
  97. * user and migration.
  98. */
  99. #define HANDLE_PIN_BIT 0
  100. /*
  101. * Head in allocated object should have OBJ_ALLOCATED_TAG
  102. * to identify the object was allocated or not.
  103. * It's okay to add the status bit in the least bit because
  104. * header keeps handle which is 4byte-aligned address so we
  105. * have room for two bit at least.
  106. */
  107. #define OBJ_ALLOCATED_TAG 1
  108. #define OBJ_TAG_BITS 1
  109. #define OBJ_INDEX_BITS (BITS_PER_LONG - _PFN_BITS - OBJ_TAG_BITS)
  110. #define OBJ_INDEX_MASK ((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
  111. #define FULLNESS_BITS 2
  112. #define CLASS_BITS 8
  113. #define ISOLATED_BITS 3
  114. #define MAGIC_VAL_BITS 8
  115. #define MAX(a, b) ((a) >= (b) ? (a) : (b))
  116. /* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
  117. #define ZS_MIN_ALLOC_SIZE \
  118. MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
  119. /* each chunk includes extra space to keep handle */
  120. #define ZS_MAX_ALLOC_SIZE PAGE_SIZE
  121. /*
  122. * On systems with 4K page size, this gives 255 size classes! There is a
  123. * trader-off here:
  124. * - Large number of size classes is potentially wasteful as free page are
  125. * spread across these classes
  126. * - Small number of size classes causes large internal fragmentation
  127. * - Probably its better to use specific size classes (empirically
  128. * determined). NOTE: all those class sizes must be set as multiple of
  129. * ZS_ALIGN to make sure link_free itself never has to span 2 pages.
  130. *
  131. * ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
  132. * (reason above)
  133. */
  134. #define ZS_SIZE_CLASS_DELTA (PAGE_SIZE >> CLASS_BITS)
  135. #define ZS_SIZE_CLASSES (DIV_ROUND_UP(ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE, \
  136. ZS_SIZE_CLASS_DELTA) + 1)
  137. enum fullness_group {
  138. ZS_EMPTY,
  139. ZS_ALMOST_EMPTY,
  140. ZS_ALMOST_FULL,
  141. ZS_FULL,
  142. NR_ZS_FULLNESS,
  143. };
  144. enum zs_stat_type {
  145. CLASS_EMPTY,
  146. CLASS_ALMOST_EMPTY,
  147. CLASS_ALMOST_FULL,
  148. CLASS_FULL,
  149. OBJ_ALLOCATED,
  150. OBJ_USED,
  151. NR_ZS_STAT_TYPE,
  152. };
  153. struct zs_size_stat {
  154. unsigned long objs[NR_ZS_STAT_TYPE];
  155. };
  156. #ifdef CONFIG_ZSMALLOC_STAT
  157. static struct dentry *zs_stat_root;
  158. #endif
  159. #ifdef CONFIG_COMPACTION
  160. static struct vfsmount *zsmalloc_mnt;
  161. #endif
  162. /*
  163. * We assign a page to ZS_ALMOST_EMPTY fullness group when:
  164. * n <= N / f, where
  165. * n = number of allocated objects
  166. * N = total number of objects zspage can store
  167. * f = fullness_threshold_frac
  168. *
  169. * Similarly, we assign zspage to:
  170. * ZS_ALMOST_FULL when n > N / f
  171. * ZS_EMPTY when n == 0
  172. * ZS_FULL when n == N
  173. *
  174. * (see: fix_fullness_group())
  175. */
  176. static const int fullness_threshold_frac = 4;
  177. static size_t huge_class_size;
  178. struct size_class {
  179. spinlock_t lock;
  180. struct list_head fullness_list[NR_ZS_FULLNESS];
  181. /*
  182. * Size of objects stored in this class. Must be multiple
  183. * of ZS_ALIGN.
  184. */
  185. int size;
  186. int objs_per_zspage;
  187. /* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
  188. int pages_per_zspage;
  189. unsigned int index;
  190. struct zs_size_stat stats;
  191. };
  192. /* huge object: pages_per_zspage == 1 && maxobj_per_zspage == 1 */
  193. static void SetPageHugeObject(struct page *page)
  194. {
  195. SetPageOwnerPriv1(page);
  196. }
  197. static void ClearPageHugeObject(struct page *page)
  198. {
  199. ClearPageOwnerPriv1(page);
  200. }
  201. static int PageHugeObject(struct page *page)
  202. {
  203. return PageOwnerPriv1(page);
  204. }
  205. /*
  206. * Placed within free objects to form a singly linked list.
  207. * For every zspage, zspage->freeobj gives head of this list.
  208. *
  209. * This must be power of 2 and less than or equal to ZS_ALIGN
  210. */
  211. struct link_free {
  212. union {
  213. /*
  214. * Free object index;
  215. * It's valid for non-allocated object
  216. */
  217. unsigned long next;
  218. /*
  219. * Handle of allocated object.
  220. */
  221. unsigned long handle;
  222. };
  223. };
  224. struct zs_pool {
  225. const char *name;
  226. struct size_class *size_class[ZS_SIZE_CLASSES];
  227. struct kmem_cache *handle_cachep;
  228. struct kmem_cache *zspage_cachep;
  229. atomic_long_t pages_allocated;
  230. struct zs_pool_stats stats;
  231. /* Compact classes */
  232. struct shrinker shrinker;
  233. #ifdef CONFIG_ZSMALLOC_STAT
  234. struct dentry *stat_dentry;
  235. #endif
  236. #ifdef CONFIG_COMPACTION
  237. struct inode *inode;
  238. struct work_struct free_work;
  239. /* A wait queue for when migration races with async_free_zspage() */
  240. struct wait_queue_head migration_wait;
  241. atomic_long_t isolated_pages;
  242. bool destroying;
  243. #endif
  244. };
  245. struct zspage {
  246. struct {
  247. unsigned int fullness:FULLNESS_BITS;
  248. unsigned int class:CLASS_BITS + 1;
  249. unsigned int isolated:ISOLATED_BITS;
  250. unsigned int magic:MAGIC_VAL_BITS;
  251. };
  252. unsigned int inuse;
  253. unsigned int freeobj;
  254. struct page *first_page;
  255. struct list_head list; /* fullness list */
  256. #ifdef CONFIG_COMPACTION
  257. rwlock_t lock;
  258. #endif
  259. };
  260. struct mapping_area {
  261. char *vm_buf; /* copy buffer for objects that span pages */
  262. char *vm_addr; /* address of kmap_atomic()'ed pages */
  263. enum zs_mapmode vm_mm; /* mapping mode */
  264. };
  265. #ifdef CONFIG_COMPACTION
  266. static int zs_register_migration(struct zs_pool *pool);
  267. static void zs_unregister_migration(struct zs_pool *pool);
  268. static void migrate_lock_init(struct zspage *zspage);
  269. static void migrate_read_lock(struct zspage *zspage);
  270. static void migrate_read_unlock(struct zspage *zspage);
  271. static void kick_deferred_free(struct zs_pool *pool);
  272. static void init_deferred_free(struct zs_pool *pool);
  273. static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage);
  274. #else
  275. static int zsmalloc_mount(void) { return 0; }
  276. static void zsmalloc_unmount(void) {}
  277. static int zs_register_migration(struct zs_pool *pool) { return 0; }
  278. static void zs_unregister_migration(struct zs_pool *pool) {}
  279. static void migrate_lock_init(struct zspage *zspage) {}
  280. static void migrate_read_lock(struct zspage *zspage) {}
  281. static void migrate_read_unlock(struct zspage *zspage) {}
  282. static void kick_deferred_free(struct zs_pool *pool) {}
  283. static void init_deferred_free(struct zs_pool *pool) {}
  284. static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage) {}
  285. #endif
  286. static int create_cache(struct zs_pool *pool)
  287. {
  288. pool->handle_cachep = kmem_cache_create("zs_handle", ZS_HANDLE_SIZE,
  289. 0, 0, NULL);
  290. if (!pool->handle_cachep)
  291. return 1;
  292. pool->zspage_cachep = kmem_cache_create("zspage", sizeof(struct zspage),
  293. 0, 0, NULL);
  294. if (!pool->zspage_cachep) {
  295. kmem_cache_destroy(pool->handle_cachep);
  296. pool->handle_cachep = NULL;
  297. return 1;
  298. }
  299. return 0;
  300. }
  301. static void destroy_cache(struct zs_pool *pool)
  302. {
  303. kmem_cache_destroy(pool->handle_cachep);
  304. kmem_cache_destroy(pool->zspage_cachep);
  305. }
  306. static unsigned long cache_alloc_handle(struct zs_pool *pool, gfp_t gfp)
  307. {
  308. return (unsigned long)kmem_cache_alloc(pool->handle_cachep,
  309. gfp & ~(__GFP_HIGHMEM|__GFP_MOVABLE|__GFP_CMA));
  310. }
  311. static void cache_free_handle(struct zs_pool *pool, unsigned long handle)
  312. {
  313. kmem_cache_free(pool->handle_cachep, (void *)handle);
  314. }
  315. static struct zspage *cache_alloc_zspage(struct zs_pool *pool, gfp_t flags)
  316. {
  317. return kmem_cache_alloc(pool->zspage_cachep,
  318. flags & ~(__GFP_HIGHMEM|__GFP_MOVABLE|__GFP_CMA));
  319. }
  320. static void cache_free_zspage(struct zs_pool *pool, struct zspage *zspage)
  321. {
  322. kmem_cache_free(pool->zspage_cachep, zspage);
  323. }
  324. static void record_obj(unsigned long handle, unsigned long obj)
  325. {
  326. /*
  327. * lsb of @obj represents handle lock while other bits
  328. * represent object value the handle is pointing so
  329. * updating shouldn't do store tearing.
  330. */
  331. WRITE_ONCE(*(unsigned long *)handle, obj);
  332. }
  333. /* zpool driver */
  334. #ifdef CONFIG_ZPOOL
  335. static void *zs_zpool_create(const char *name, gfp_t gfp,
  336. const struct zpool_ops *zpool_ops,
  337. struct zpool *zpool)
  338. {
  339. /*
  340. * Ignore global gfp flags: zs_malloc() may be invoked from
  341. * different contexts and its caller must provide a valid
  342. * gfp mask.
  343. */
  344. return zs_create_pool(name);
  345. }
  346. static void zs_zpool_destroy(void *pool)
  347. {
  348. zs_destroy_pool(pool);
  349. }
  350. static int zs_zpool_malloc(void *pool, size_t size, gfp_t gfp,
  351. unsigned long *handle)
  352. {
  353. *handle = zs_malloc(pool, size, gfp);
  354. return *handle ? 0 : -1;
  355. }
  356. static void zs_zpool_free(void *pool, unsigned long handle)
  357. {
  358. zs_free(pool, handle);
  359. }
  360. static void *zs_zpool_map(void *pool, unsigned long handle,
  361. enum zpool_mapmode mm)
  362. {
  363. enum zs_mapmode zs_mm;
  364. switch (mm) {
  365. case ZPOOL_MM_RO:
  366. zs_mm = ZS_MM_RO;
  367. break;
  368. case ZPOOL_MM_WO:
  369. zs_mm = ZS_MM_WO;
  370. break;
  371. case ZPOOL_MM_RW:
  372. default:
  373. zs_mm = ZS_MM_RW;
  374. break;
  375. }
  376. return zs_map_object(pool, handle, zs_mm);
  377. }
  378. static void zs_zpool_unmap(void *pool, unsigned long handle)
  379. {
  380. zs_unmap_object(pool, handle);
  381. }
  382. static u64 zs_zpool_total_size(void *pool)
  383. {
  384. return zs_get_total_pages(pool) << PAGE_SHIFT;
  385. }
  386. static struct zpool_driver zs_zpool_driver = {
  387. .type = "zsmalloc",
  388. .owner = THIS_MODULE,
  389. .create = zs_zpool_create,
  390. .destroy = zs_zpool_destroy,
  391. .malloc_support_movable = true,
  392. .malloc = zs_zpool_malloc,
  393. .free = zs_zpool_free,
  394. .map = zs_zpool_map,
  395. .unmap = zs_zpool_unmap,
  396. .total_size = zs_zpool_total_size,
  397. };
  398. MODULE_ALIAS("zpool-zsmalloc");
  399. #endif /* CONFIG_ZPOOL */
  400. /* per-cpu VM mapping areas for zspage accesses that cross page boundaries */
  401. static DEFINE_PER_CPU(struct mapping_area, zs_map_area);
  402. static bool is_zspage_isolated(struct zspage *zspage)
  403. {
  404. return zspage->isolated;
  405. }
  406. static __maybe_unused int is_first_page(struct page *page)
  407. {
  408. return PagePrivate(page);
  409. }
  410. /* Protected by class->lock */
  411. static inline int get_zspage_inuse(struct zspage *zspage)
  412. {
  413. return zspage->inuse;
  414. }
  415. static inline void mod_zspage_inuse(struct zspage *zspage, int val)
  416. {
  417. zspage->inuse += val;
  418. }
  419. static inline struct page *get_first_page(struct zspage *zspage)
  420. {
  421. struct page *first_page = zspage->first_page;
  422. VM_BUG_ON_PAGE(!is_first_page(first_page), first_page);
  423. return first_page;
  424. }
  425. static inline int get_first_obj_offset(struct page *page)
  426. {
  427. return page->units;
  428. }
  429. static inline void set_first_obj_offset(struct page *page, int offset)
  430. {
  431. page->units = offset;
  432. }
  433. static inline unsigned int get_freeobj(struct zspage *zspage)
  434. {
  435. return zspage->freeobj;
  436. }
  437. static inline void set_freeobj(struct zspage *zspage, unsigned int obj)
  438. {
  439. zspage->freeobj = obj;
  440. }
  441. static void get_zspage_mapping(struct zspage *zspage,
  442. unsigned int *class_idx,
  443. enum fullness_group *fullness)
  444. {
  445. BUG_ON(zspage->magic != ZSPAGE_MAGIC);
  446. *fullness = zspage->fullness;
  447. *class_idx = zspage->class;
  448. }
  449. static void set_zspage_mapping(struct zspage *zspage,
  450. unsigned int class_idx,
  451. enum fullness_group fullness)
  452. {
  453. zspage->class = class_idx;
  454. zspage->fullness = fullness;
  455. }
  456. /*
  457. * zsmalloc divides the pool into various size classes where each
  458. * class maintains a list of zspages where each zspage is divided
  459. * into equal sized chunks. Each allocation falls into one of these
  460. * classes depending on its size. This function returns index of the
  461. * size class which has chunk size big enough to hold the give size.
  462. */
  463. static int get_size_class_index(int size)
  464. {
  465. int idx = 0;
  466. if (likely(size > ZS_MIN_ALLOC_SIZE))
  467. idx = DIV_ROUND_UP(size - ZS_MIN_ALLOC_SIZE,
  468. ZS_SIZE_CLASS_DELTA);
  469. return min_t(int, ZS_SIZE_CLASSES - 1, idx);
  470. }
  471. /* type can be of enum type zs_stat_type or fullness_group */
  472. static inline void zs_stat_inc(struct size_class *class,
  473. int type, unsigned long cnt)
  474. {
  475. class->stats.objs[type] += cnt;
  476. }
  477. /* type can be of enum type zs_stat_type or fullness_group */
  478. static inline void zs_stat_dec(struct size_class *class,
  479. int type, unsigned long cnt)
  480. {
  481. class->stats.objs[type] -= cnt;
  482. }
  483. /* type can be of enum type zs_stat_type or fullness_group */
  484. static inline unsigned long zs_stat_get(struct size_class *class,
  485. int type)
  486. {
  487. return class->stats.objs[type];
  488. }
  489. #ifdef CONFIG_ZSMALLOC_STAT
  490. static void __init zs_stat_init(void)
  491. {
  492. if (!debugfs_initialized()) {
  493. pr_warn("debugfs not available, stat dir not created\n");
  494. return;
  495. }
  496. zs_stat_root = debugfs_create_dir("zsmalloc", NULL);
  497. }
  498. static void __exit zs_stat_exit(void)
  499. {
  500. debugfs_remove_recursive(zs_stat_root);
  501. }
  502. static unsigned long zs_can_compact(struct size_class *class);
  503. static int zs_stats_size_show(struct seq_file *s, void *v)
  504. {
  505. int i;
  506. struct zs_pool *pool = s->private;
  507. struct size_class *class;
  508. int objs_per_zspage;
  509. unsigned long class_almost_full, class_almost_empty;
  510. unsigned long obj_allocated, obj_used, pages_used, freeable;
  511. unsigned long total_class_almost_full = 0, total_class_almost_empty = 0;
  512. unsigned long total_objs = 0, total_used_objs = 0, total_pages = 0;
  513. unsigned long total_freeable = 0;
  514. seq_printf(s, " %5s %5s %11s %12s %13s %10s %10s %16s %8s\n",
  515. "class", "size", "almost_full", "almost_empty",
  516. "obj_allocated", "obj_used", "pages_used",
  517. "pages_per_zspage", "freeable");
  518. for (i = 0; i < ZS_SIZE_CLASSES; i++) {
  519. class = pool->size_class[i];
  520. if (class->index != i)
  521. continue;
  522. spin_lock(&class->lock);
  523. class_almost_full = zs_stat_get(class, CLASS_ALMOST_FULL);
  524. class_almost_empty = zs_stat_get(class, CLASS_ALMOST_EMPTY);
  525. obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
  526. obj_used = zs_stat_get(class, OBJ_USED);
  527. freeable = zs_can_compact(class);
  528. spin_unlock(&class->lock);
  529. objs_per_zspage = class->objs_per_zspage;
  530. pages_used = obj_allocated / objs_per_zspage *
  531. class->pages_per_zspage;
  532. seq_printf(s, " %5u %5u %11lu %12lu %13lu"
  533. " %10lu %10lu %16d %8lu\n",
  534. i, class->size, class_almost_full, class_almost_empty,
  535. obj_allocated, obj_used, pages_used,
  536. class->pages_per_zspage, freeable);
  537. total_class_almost_full += class_almost_full;
  538. total_class_almost_empty += class_almost_empty;
  539. total_objs += obj_allocated;
  540. total_used_objs += obj_used;
  541. total_pages += pages_used;
  542. total_freeable += freeable;
  543. }
  544. seq_puts(s, "\n");
  545. seq_printf(s, " %5s %5s %11lu %12lu %13lu %10lu %10lu %16s %8lu\n",
  546. "Total", "", total_class_almost_full,
  547. total_class_almost_empty, total_objs,
  548. total_used_objs, total_pages, "", total_freeable);
  549. return 0;
  550. }
  551. DEFINE_SHOW_ATTRIBUTE(zs_stats_size);
  552. static void zs_pool_stat_create(struct zs_pool *pool, const char *name)
  553. {
  554. if (!zs_stat_root) {
  555. pr_warn("no root stat dir, not creating <%s> stat dir\n", name);
  556. return;
  557. }
  558. pool->stat_dentry = debugfs_create_dir(name, zs_stat_root);
  559. debugfs_create_file("classes", S_IFREG | 0444, pool->stat_dentry, pool,
  560. &zs_stats_size_fops);
  561. }
  562. static void zs_pool_stat_destroy(struct zs_pool *pool)
  563. {
  564. debugfs_remove_recursive(pool->stat_dentry);
  565. }
  566. #else /* CONFIG_ZSMALLOC_STAT */
  567. static void __init zs_stat_init(void)
  568. {
  569. }
  570. static void __exit zs_stat_exit(void)
  571. {
  572. }
  573. static inline void zs_pool_stat_create(struct zs_pool *pool, const char *name)
  574. {
  575. }
  576. static inline void zs_pool_stat_destroy(struct zs_pool *pool)
  577. {
  578. }
  579. #endif
  580. /*
  581. * For each size class, zspages are divided into different groups
  582. * depending on how "full" they are. This was done so that we could
  583. * easily find empty or nearly empty zspages when we try to shrink
  584. * the pool (not yet implemented). This function returns fullness
  585. * status of the given page.
  586. */
  587. static enum fullness_group get_fullness_group(struct size_class *class,
  588. struct zspage *zspage)
  589. {
  590. int inuse, objs_per_zspage;
  591. enum fullness_group fg;
  592. inuse = get_zspage_inuse(zspage);
  593. objs_per_zspage = class->objs_per_zspage;
  594. if (inuse == 0)
  595. fg = ZS_EMPTY;
  596. else if (inuse == objs_per_zspage)
  597. fg = ZS_FULL;
  598. else if (inuse <= 3 * objs_per_zspage / fullness_threshold_frac)
  599. fg = ZS_ALMOST_EMPTY;
  600. else
  601. fg = ZS_ALMOST_FULL;
  602. return fg;
  603. }
  604. /*
  605. * Each size class maintains various freelists and zspages are assigned
  606. * to one of these freelists based on the number of live objects they
  607. * have. This functions inserts the given zspage into the freelist
  608. * identified by <class, fullness_group>.
  609. */
  610. static void insert_zspage(struct size_class *class,
  611. struct zspage *zspage,
  612. enum fullness_group fullness)
  613. {
  614. struct zspage *head;
  615. zs_stat_inc(class, fullness, 1);
  616. head = list_first_entry_or_null(&class->fullness_list[fullness],
  617. struct zspage, list);
  618. /*
  619. * We want to see more ZS_FULL pages and less almost empty/full.
  620. * Put pages with higher ->inuse first.
  621. */
  622. if (head) {
  623. if (get_zspage_inuse(zspage) < get_zspage_inuse(head)) {
  624. list_add(&zspage->list, &head->list);
  625. return;
  626. }
  627. }
  628. list_add(&zspage->list, &class->fullness_list[fullness]);
  629. }
  630. /*
  631. * This function removes the given zspage from the freelist identified
  632. * by <class, fullness_group>.
  633. */
  634. static void remove_zspage(struct size_class *class,
  635. struct zspage *zspage,
  636. enum fullness_group fullness)
  637. {
  638. VM_BUG_ON(list_empty(&class->fullness_list[fullness]));
  639. VM_BUG_ON(is_zspage_isolated(zspage));
  640. list_del_init(&zspage->list);
  641. zs_stat_dec(class, fullness, 1);
  642. }
  643. /*
  644. * Each size class maintains zspages in different fullness groups depending
  645. * on the number of live objects they contain. When allocating or freeing
  646. * objects, the fullness status of the page can change, say, from ALMOST_FULL
  647. * to ALMOST_EMPTY when freeing an object. This function checks if such
  648. * a status change has occurred for the given page and accordingly moves the
  649. * page from the freelist of the old fullness group to that of the new
  650. * fullness group.
  651. */
  652. static enum fullness_group fix_fullness_group(struct size_class *class,
  653. struct zspage *zspage)
  654. {
  655. int class_idx;
  656. enum fullness_group currfg, newfg;
  657. get_zspage_mapping(zspage, &class_idx, &currfg);
  658. newfg = get_fullness_group(class, zspage);
  659. if (newfg == currfg)
  660. goto out;
  661. if (!is_zspage_isolated(zspage)) {
  662. remove_zspage(class, zspage, currfg);
  663. insert_zspage(class, zspage, newfg);
  664. }
  665. set_zspage_mapping(zspage, class_idx, newfg);
  666. out:
  667. return newfg;
  668. }
  669. /*
  670. * We have to decide on how many pages to link together
  671. * to form a zspage for each size class. This is important
  672. * to reduce wastage due to unusable space left at end of
  673. * each zspage which is given as:
  674. * wastage = Zp % class_size
  675. * usage = Zp - wastage
  676. * where Zp = zspage size = k * PAGE_SIZE where k = 1, 2, ...
  677. *
  678. * For example, for size class of 3/8 * PAGE_SIZE, we should
  679. * link together 3 PAGE_SIZE sized pages to form a zspage
  680. * since then we can perfectly fit in 8 such objects.
  681. */
  682. static int get_pages_per_zspage(int class_size)
  683. {
  684. int i, max_usedpc = 0;
  685. /* zspage order which gives maximum used size per KB */
  686. int max_usedpc_order = 1;
  687. for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) {
  688. int zspage_size;
  689. int waste, usedpc;
  690. zspage_size = i * PAGE_SIZE;
  691. waste = zspage_size % class_size;
  692. usedpc = (zspage_size - waste) * 100 / zspage_size;
  693. if (usedpc > max_usedpc) {
  694. max_usedpc = usedpc;
  695. max_usedpc_order = i;
  696. }
  697. }
  698. return max_usedpc_order;
  699. }
  700. static struct zspage *get_zspage(struct page *page)
  701. {
  702. struct zspage *zspage = (struct zspage *)page->private;
  703. BUG_ON(zspage->magic != ZSPAGE_MAGIC);
  704. return zspage;
  705. }
  706. static struct page *get_next_page(struct page *page)
  707. {
  708. if (unlikely(PageHugeObject(page)))
  709. return NULL;
  710. return page->freelist;
  711. }
  712. /**
  713. * obj_to_location - get (<page>, <obj_idx>) from encoded object value
  714. * @obj: the encoded object value
  715. * @page: page object resides in zspage
  716. * @obj_idx: object index
  717. */
  718. static void obj_to_location(unsigned long obj, struct page **page,
  719. unsigned int *obj_idx)
  720. {
  721. obj >>= OBJ_TAG_BITS;
  722. *page = pfn_to_page(obj >> OBJ_INDEX_BITS);
  723. *obj_idx = (obj & OBJ_INDEX_MASK);
  724. }
  725. /**
  726. * location_to_obj - get obj value encoded from (<page>, <obj_idx>)
  727. * @page: page object resides in zspage
  728. * @obj_idx: object index
  729. */
  730. static unsigned long location_to_obj(struct page *page, unsigned int obj_idx)
  731. {
  732. unsigned long obj;
  733. obj = page_to_pfn(page) << OBJ_INDEX_BITS;
  734. obj |= obj_idx & OBJ_INDEX_MASK;
  735. obj <<= OBJ_TAG_BITS;
  736. return obj;
  737. }
  738. static unsigned long handle_to_obj(unsigned long handle)
  739. {
  740. return *(unsigned long *)handle;
  741. }
  742. static unsigned long obj_to_head(struct page *page, void *obj)
  743. {
  744. if (unlikely(PageHugeObject(page))) {
  745. VM_BUG_ON_PAGE(!is_first_page(page), page);
  746. return page->index;
  747. } else
  748. return *(unsigned long *)obj;
  749. }
  750. static inline int testpin_tag(unsigned long handle)
  751. {
  752. return bit_spin_is_locked(HANDLE_PIN_BIT, (unsigned long *)handle);
  753. }
  754. static inline int trypin_tag(unsigned long handle)
  755. {
  756. return bit_spin_trylock(HANDLE_PIN_BIT, (unsigned long *)handle);
  757. }
  758. static void pin_tag(unsigned long handle) __acquires(bitlock)
  759. {
  760. bit_spin_lock(HANDLE_PIN_BIT, (unsigned long *)handle);
  761. }
  762. static void unpin_tag(unsigned long handle) __releases(bitlock)
  763. {
  764. bit_spin_unlock(HANDLE_PIN_BIT, (unsigned long *)handle);
  765. }
  766. static void reset_page(struct page *page)
  767. {
  768. __ClearPageMovable(page);
  769. ClearPagePrivate(page);
  770. set_page_private(page, 0);
  771. page_mapcount_reset(page);
  772. ClearPageHugeObject(page);
  773. page->freelist = NULL;
  774. }
  775. static int trylock_zspage(struct zspage *zspage)
  776. {
  777. struct page *cursor, *fail;
  778. for (cursor = get_first_page(zspage); cursor != NULL; cursor =
  779. get_next_page(cursor)) {
  780. if (!trylock_page(cursor)) {
  781. fail = cursor;
  782. goto unlock;
  783. }
  784. }
  785. return 1;
  786. unlock:
  787. for (cursor = get_first_page(zspage); cursor != fail; cursor =
  788. get_next_page(cursor))
  789. unlock_page(cursor);
  790. return 0;
  791. }
  792. static void __free_zspage(struct zs_pool *pool, struct size_class *class,
  793. struct zspage *zspage)
  794. {
  795. struct page *page, *next;
  796. enum fullness_group fg;
  797. unsigned int class_idx;
  798. get_zspage_mapping(zspage, &class_idx, &fg);
  799. assert_spin_locked(&class->lock);
  800. VM_BUG_ON(get_zspage_inuse(zspage));
  801. VM_BUG_ON(fg != ZS_EMPTY);
  802. next = page = get_first_page(zspage);
  803. do {
  804. VM_BUG_ON_PAGE(!PageLocked(page), page);
  805. next = get_next_page(page);
  806. reset_page(page);
  807. unlock_page(page);
  808. dec_zone_page_state(page, NR_ZSPAGES);
  809. put_page(page);
  810. page = next;
  811. } while (page != NULL);
  812. cache_free_zspage(pool, zspage);
  813. zs_stat_dec(class, OBJ_ALLOCATED, class->objs_per_zspage);
  814. atomic_long_sub(class->pages_per_zspage,
  815. &pool->pages_allocated);
  816. }
  817. static void free_zspage(struct zs_pool *pool, struct size_class *class,
  818. struct zspage *zspage)
  819. {
  820. VM_BUG_ON(get_zspage_inuse(zspage));
  821. VM_BUG_ON(list_empty(&zspage->list));
  822. if (!trylock_zspage(zspage)) {
  823. kick_deferred_free(pool);
  824. return;
  825. }
  826. remove_zspage(class, zspage, ZS_EMPTY);
  827. __free_zspage(pool, class, zspage);
  828. }
  829. /* Initialize a newly allocated zspage */
  830. static void init_zspage(struct size_class *class, struct zspage *zspage)
  831. {
  832. unsigned int freeobj = 1;
  833. unsigned long off = 0;
  834. struct page *page = get_first_page(zspage);
  835. while (page) {
  836. struct page *next_page;
  837. struct link_free *link;
  838. void *vaddr;
  839. set_first_obj_offset(page, off);
  840. vaddr = kmap_atomic(page);
  841. link = (struct link_free *)vaddr + off / sizeof(*link);
  842. while ((off += class->size) < PAGE_SIZE) {
  843. link->next = freeobj++ << OBJ_TAG_BITS;
  844. link += class->size / sizeof(*link);
  845. }
  846. /*
  847. * We now come to the last (full or partial) object on this
  848. * page, which must point to the first object on the next
  849. * page (if present)
  850. */
  851. next_page = get_next_page(page);
  852. if (next_page) {
  853. link->next = freeobj++ << OBJ_TAG_BITS;
  854. } else {
  855. /*
  856. * Reset OBJ_TAG_BITS bit to last link to tell
  857. * whether it's allocated object or not.
  858. */
  859. link->next = -1UL << OBJ_TAG_BITS;
  860. }
  861. kunmap_atomic(vaddr);
  862. page = next_page;
  863. off %= PAGE_SIZE;
  864. }
  865. set_freeobj(zspage, 0);
  866. }
  867. static void create_page_chain(struct size_class *class, struct zspage *zspage,
  868. struct page *pages[])
  869. {
  870. int i;
  871. struct page *page;
  872. struct page *prev_page = NULL;
  873. int nr_pages = class->pages_per_zspage;
  874. /*
  875. * Allocate individual pages and link them together as:
  876. * 1. all pages are linked together using page->freelist
  877. * 2. each sub-page point to zspage using page->private
  878. *
  879. * we set PG_private to identify the first page (i.e. no other sub-page
  880. * has this flag set).
  881. */
  882. for (i = 0; i < nr_pages; i++) {
  883. page = pages[i];
  884. set_page_private(page, (unsigned long)zspage);
  885. page->freelist = NULL;
  886. if (i == 0) {
  887. zspage->first_page = page;
  888. SetPagePrivate(page);
  889. if (unlikely(class->objs_per_zspage == 1 &&
  890. class->pages_per_zspage == 1))
  891. SetPageHugeObject(page);
  892. } else {
  893. prev_page->freelist = page;
  894. }
  895. prev_page = page;
  896. }
  897. }
  898. /*
  899. * Allocate a zspage for the given size class
  900. */
  901. static struct zspage *alloc_zspage(struct zs_pool *pool,
  902. struct size_class *class,
  903. gfp_t gfp)
  904. {
  905. int i;
  906. struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE];
  907. struct zspage *zspage = cache_alloc_zspage(pool, gfp);
  908. if (!zspage)
  909. return NULL;
  910. memset(zspage, 0, sizeof(struct zspage));
  911. zspage->magic = ZSPAGE_MAGIC;
  912. migrate_lock_init(zspage);
  913. for (i = 0; i < class->pages_per_zspage; i++) {
  914. struct page *page;
  915. page = alloc_page(gfp);
  916. if (!page) {
  917. while (--i >= 0) {
  918. dec_zone_page_state(pages[i], NR_ZSPAGES);
  919. __free_page(pages[i]);
  920. }
  921. cache_free_zspage(pool, zspage);
  922. return NULL;
  923. }
  924. inc_zone_page_state(page, NR_ZSPAGES);
  925. pages[i] = page;
  926. }
  927. create_page_chain(class, zspage, pages);
  928. init_zspage(class, zspage);
  929. return zspage;
  930. }
  931. static struct zspage *find_get_zspage(struct size_class *class)
  932. {
  933. int i;
  934. struct zspage *zspage;
  935. for (i = ZS_ALMOST_FULL; i >= ZS_EMPTY; i--) {
  936. zspage = list_first_entry_or_null(&class->fullness_list[i],
  937. struct zspage, list);
  938. if (zspage)
  939. break;
  940. }
  941. return zspage;
  942. }
  943. static inline int __zs_cpu_up(struct mapping_area *area)
  944. {
  945. /*
  946. * Make sure we don't leak memory if a cpu UP notification
  947. * and zs_init() race and both call zs_cpu_up() on the same cpu
  948. */
  949. if (area->vm_buf)
  950. return 0;
  951. area->vm_buf = kmalloc(ZS_MAX_ALLOC_SIZE, GFP_KERNEL);
  952. if (!area->vm_buf)
  953. return -ENOMEM;
  954. return 0;
  955. }
  956. static inline void __zs_cpu_down(struct mapping_area *area)
  957. {
  958. kfree(area->vm_buf);
  959. area->vm_buf = NULL;
  960. }
  961. static void *__zs_map_object(struct mapping_area *area,
  962. struct page *pages[2], int off, int size)
  963. {
  964. int sizes[2];
  965. void *addr;
  966. char *buf = area->vm_buf;
  967. /* disable page faults to match kmap_atomic() return conditions */
  968. pagefault_disable();
  969. /* no read fastpath */
  970. if (area->vm_mm == ZS_MM_WO)
  971. goto out;
  972. sizes[0] = PAGE_SIZE - off;
  973. sizes[1] = size - sizes[0];
  974. /* copy object to per-cpu buffer */
  975. addr = kmap_atomic(pages[0]);
  976. memcpy(buf, addr + off, sizes[0]);
  977. kunmap_atomic(addr);
  978. addr = kmap_atomic(pages[1]);
  979. memcpy(buf + sizes[0], addr, sizes[1]);
  980. kunmap_atomic(addr);
  981. out:
  982. return area->vm_buf;
  983. }
  984. static void __zs_unmap_object(struct mapping_area *area,
  985. struct page *pages[2], int off, int size)
  986. {
  987. int sizes[2];
  988. void *addr;
  989. char *buf;
  990. /* no write fastpath */
  991. if (area->vm_mm == ZS_MM_RO)
  992. goto out;
  993. buf = area->vm_buf;
  994. buf = buf + ZS_HANDLE_SIZE;
  995. size -= ZS_HANDLE_SIZE;
  996. off += ZS_HANDLE_SIZE;
  997. sizes[0] = PAGE_SIZE - off;
  998. sizes[1] = size - sizes[0];
  999. /* copy per-cpu buffer to object */
  1000. addr = kmap_atomic(pages[0]);
  1001. memcpy(addr + off, buf, sizes[0]);
  1002. kunmap_atomic(addr);
  1003. addr = kmap_atomic(pages[1]);
  1004. memcpy(addr, buf + sizes[0], sizes[1]);
  1005. kunmap_atomic(addr);
  1006. out:
  1007. /* enable page faults to match kunmap_atomic() return conditions */
  1008. pagefault_enable();
  1009. }
  1010. static int zs_cpu_prepare(unsigned int cpu)
  1011. {
  1012. struct mapping_area *area;
  1013. area = &per_cpu(zs_map_area, cpu);
  1014. return __zs_cpu_up(area);
  1015. }
  1016. static int zs_cpu_dead(unsigned int cpu)
  1017. {
  1018. struct mapping_area *area;
  1019. area = &per_cpu(zs_map_area, cpu);
  1020. __zs_cpu_down(area);
  1021. return 0;
  1022. }
  1023. static bool can_merge(struct size_class *prev, int pages_per_zspage,
  1024. int objs_per_zspage)
  1025. {
  1026. if (prev->pages_per_zspage == pages_per_zspage &&
  1027. prev->objs_per_zspage == objs_per_zspage)
  1028. return true;
  1029. return false;
  1030. }
  1031. static bool zspage_full(struct size_class *class, struct zspage *zspage)
  1032. {
  1033. return get_zspage_inuse(zspage) == class->objs_per_zspage;
  1034. }
  1035. unsigned long zs_get_total_pages(struct zs_pool *pool)
  1036. {
  1037. return atomic_long_read(&pool->pages_allocated);
  1038. }
  1039. EXPORT_SYMBOL_GPL(zs_get_total_pages);
  1040. /**
  1041. * zs_map_object - get address of allocated object from handle.
  1042. * @pool: pool from which the object was allocated
  1043. * @handle: handle returned from zs_malloc
  1044. * @mm: maping mode to use
  1045. *
  1046. * Before using an object allocated from zs_malloc, it must be mapped using
  1047. * this function. When done with the object, it must be unmapped using
  1048. * zs_unmap_object.
  1049. *
  1050. * Only one object can be mapped per cpu at a time. There is no protection
  1051. * against nested mappings.
  1052. *
  1053. * This function returns with preemption and page faults disabled.
  1054. */
  1055. void *zs_map_object(struct zs_pool *pool, unsigned long handle,
  1056. enum zs_mapmode mm)
  1057. {
  1058. struct zspage *zspage;
  1059. struct page *page;
  1060. unsigned long obj, off;
  1061. unsigned int obj_idx;
  1062. unsigned int class_idx;
  1063. enum fullness_group fg;
  1064. struct size_class *class;
  1065. struct mapping_area *area;
  1066. struct page *pages[2];
  1067. void *ret;
  1068. /*
  1069. * Because we use per-cpu mapping areas shared among the
  1070. * pools/users, we can't allow mapping in interrupt context
  1071. * because it can corrupt another users mappings.
  1072. */
  1073. BUG_ON(in_interrupt());
  1074. /* From now on, migration cannot move the object */
  1075. pin_tag(handle);
  1076. obj = handle_to_obj(handle);
  1077. obj_to_location(obj, &page, &obj_idx);
  1078. zspage = get_zspage(page);
  1079. /* migration cannot move any subpage in this zspage */
  1080. migrate_read_lock(zspage);
  1081. get_zspage_mapping(zspage, &class_idx, &fg);
  1082. class = pool->size_class[class_idx];
  1083. off = (class->size * obj_idx) & ~PAGE_MASK;
  1084. area = &get_cpu_var(zs_map_area);
  1085. area->vm_mm = mm;
  1086. if (off + class->size <= PAGE_SIZE) {
  1087. /* this object is contained entirely within a page */
  1088. area->vm_addr = kmap_atomic(page);
  1089. ret = area->vm_addr + off;
  1090. goto out;
  1091. }
  1092. /* this object spans two pages */
  1093. pages[0] = page;
  1094. pages[1] = get_next_page(page);
  1095. BUG_ON(!pages[1]);
  1096. ret = __zs_map_object(area, pages, off, class->size);
  1097. out:
  1098. if (likely(!PageHugeObject(page)))
  1099. ret += ZS_HANDLE_SIZE;
  1100. return ret;
  1101. }
  1102. EXPORT_SYMBOL_GPL(zs_map_object);
  1103. void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
  1104. {
  1105. struct zspage *zspage;
  1106. struct page *page;
  1107. unsigned long obj, off;
  1108. unsigned int obj_idx;
  1109. unsigned int class_idx;
  1110. enum fullness_group fg;
  1111. struct size_class *class;
  1112. struct mapping_area *area;
  1113. obj = handle_to_obj(handle);
  1114. obj_to_location(obj, &page, &obj_idx);
  1115. zspage = get_zspage(page);
  1116. get_zspage_mapping(zspage, &class_idx, &fg);
  1117. class = pool->size_class[class_idx];
  1118. off = (class->size * obj_idx) & ~PAGE_MASK;
  1119. area = this_cpu_ptr(&zs_map_area);
  1120. if (off + class->size <= PAGE_SIZE)
  1121. kunmap_atomic(area->vm_addr);
  1122. else {
  1123. struct page *pages[2];
  1124. pages[0] = page;
  1125. pages[1] = get_next_page(page);
  1126. BUG_ON(!pages[1]);
  1127. __zs_unmap_object(area, pages, off, class->size);
  1128. }
  1129. put_cpu_var(zs_map_area);
  1130. migrate_read_unlock(zspage);
  1131. unpin_tag(handle);
  1132. }
  1133. EXPORT_SYMBOL_GPL(zs_unmap_object);
  1134. /**
  1135. * zs_huge_class_size() - Returns the size (in bytes) of the first huge
  1136. * zsmalloc &size_class.
  1137. * @pool: zsmalloc pool to use
  1138. *
  1139. * The function returns the size of the first huge class - any object of equal
  1140. * or bigger size will be stored in zspage consisting of a single physical
  1141. * page.
  1142. *
  1143. * Context: Any context.
  1144. *
  1145. * Return: the size (in bytes) of the first huge zsmalloc &size_class.
  1146. */
  1147. size_t zs_huge_class_size(struct zs_pool *pool)
  1148. {
  1149. return huge_class_size;
  1150. }
  1151. EXPORT_SYMBOL_GPL(zs_huge_class_size);
  1152. static unsigned long obj_malloc(struct size_class *class,
  1153. struct zspage *zspage, unsigned long handle)
  1154. {
  1155. int i, nr_page, offset;
  1156. unsigned long obj;
  1157. struct link_free *link;
  1158. struct page *m_page;
  1159. unsigned long m_offset;
  1160. void *vaddr;
  1161. handle |= OBJ_ALLOCATED_TAG;
  1162. obj = get_freeobj(zspage);
  1163. offset = obj * class->size;
  1164. nr_page = offset >> PAGE_SHIFT;
  1165. m_offset = offset & ~PAGE_MASK;
  1166. m_page = get_first_page(zspage);
  1167. for (i = 0; i < nr_page; i++)
  1168. m_page = get_next_page(m_page);
  1169. vaddr = kmap_atomic(m_page);
  1170. link = (struct link_free *)vaddr + m_offset / sizeof(*link);
  1171. set_freeobj(zspage, link->next >> OBJ_TAG_BITS);
  1172. if (likely(!PageHugeObject(m_page)))
  1173. /* record handle in the header of allocated chunk */
  1174. link->handle = handle;
  1175. else
  1176. /* record handle to page->index */
  1177. zspage->first_page->index = handle;
  1178. kunmap_atomic(vaddr);
  1179. mod_zspage_inuse(zspage, 1);
  1180. zs_stat_inc(class, OBJ_USED, 1);
  1181. obj = location_to_obj(m_page, obj);
  1182. return obj;
  1183. }
  1184. /**
  1185. * zs_malloc - Allocate block of given size from pool.
  1186. * @pool: pool to allocate from
  1187. * @size: size of block to allocate
  1188. * @gfp: gfp flags when allocating object
  1189. *
  1190. * On success, handle to the allocated object is returned,
  1191. * otherwise 0.
  1192. * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
  1193. */
  1194. unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
  1195. {
  1196. unsigned long handle, obj;
  1197. struct size_class *class;
  1198. enum fullness_group newfg;
  1199. struct zspage *zspage;
  1200. if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
  1201. return 0;
  1202. handle = cache_alloc_handle(pool, gfp);
  1203. if (!handle)
  1204. return 0;
  1205. /* extra space in chunk to keep the handle */
  1206. size += ZS_HANDLE_SIZE;
  1207. class = pool->size_class[get_size_class_index(size)];
  1208. spin_lock(&class->lock);
  1209. zspage = find_get_zspage(class);
  1210. if (likely(zspage)) {
  1211. obj = obj_malloc(class, zspage, handle);
  1212. /* Now move the zspage to another fullness group, if required */
  1213. fix_fullness_group(class, zspage);
  1214. record_obj(handle, obj);
  1215. spin_unlock(&class->lock);
  1216. return handle;
  1217. }
  1218. spin_unlock(&class->lock);
  1219. zspage = alloc_zspage(pool, class, gfp);
  1220. if (!zspage) {
  1221. cache_free_handle(pool, handle);
  1222. return 0;
  1223. }
  1224. spin_lock(&class->lock);
  1225. obj = obj_malloc(class, zspage, handle);
  1226. newfg = get_fullness_group(class, zspage);
  1227. insert_zspage(class, zspage, newfg);
  1228. set_zspage_mapping(zspage, class->index, newfg);
  1229. record_obj(handle, obj);
  1230. atomic_long_add(class->pages_per_zspage,
  1231. &pool->pages_allocated);
  1232. zs_stat_inc(class, OBJ_ALLOCATED, class->objs_per_zspage);
  1233. /* We completely set up zspage so mark them as movable */
  1234. SetZsPageMovable(pool, zspage);
  1235. spin_unlock(&class->lock);
  1236. return handle;
  1237. }
  1238. EXPORT_SYMBOL_GPL(zs_malloc);
  1239. static void obj_free(struct size_class *class, unsigned long obj)
  1240. {
  1241. struct link_free *link;
  1242. struct zspage *zspage;
  1243. struct page *f_page;
  1244. unsigned long f_offset;
  1245. unsigned int f_objidx;
  1246. void *vaddr;
  1247. obj &= ~OBJ_ALLOCATED_TAG;
  1248. obj_to_location(obj, &f_page, &f_objidx);
  1249. f_offset = (class->size * f_objidx) & ~PAGE_MASK;
  1250. zspage = get_zspage(f_page);
  1251. vaddr = kmap_atomic(f_page);
  1252. /* Insert this object in containing zspage's freelist */
  1253. link = (struct link_free *)(vaddr + f_offset);
  1254. link->next = get_freeobj(zspage) << OBJ_TAG_BITS;
  1255. kunmap_atomic(vaddr);
  1256. set_freeobj(zspage, f_objidx);
  1257. mod_zspage_inuse(zspage, -1);
  1258. zs_stat_dec(class, OBJ_USED, 1);
  1259. }
  1260. void zs_free(struct zs_pool *pool, unsigned long handle)
  1261. {
  1262. struct zspage *zspage;
  1263. struct page *f_page;
  1264. unsigned long obj;
  1265. unsigned int f_objidx;
  1266. int class_idx;
  1267. struct size_class *class;
  1268. enum fullness_group fullness;
  1269. bool isolated;
  1270. if (unlikely(!handle))
  1271. return;
  1272. pin_tag(handle);
  1273. obj = handle_to_obj(handle);
  1274. obj_to_location(obj, &f_page, &f_objidx);
  1275. zspage = get_zspage(f_page);
  1276. migrate_read_lock(zspage);
  1277. get_zspage_mapping(zspage, &class_idx, &fullness);
  1278. class = pool->size_class[class_idx];
  1279. spin_lock(&class->lock);
  1280. obj_free(class, obj);
  1281. fullness = fix_fullness_group(class, zspage);
  1282. if (fullness != ZS_EMPTY) {
  1283. migrate_read_unlock(zspage);
  1284. goto out;
  1285. }
  1286. isolated = is_zspage_isolated(zspage);
  1287. migrate_read_unlock(zspage);
  1288. /* If zspage is isolated, zs_page_putback will free the zspage */
  1289. if (likely(!isolated))
  1290. free_zspage(pool, class, zspage);
  1291. out:
  1292. spin_unlock(&class->lock);
  1293. unpin_tag(handle);
  1294. cache_free_handle(pool, handle);
  1295. }
  1296. EXPORT_SYMBOL_GPL(zs_free);
  1297. static void zs_object_copy(struct size_class *class, unsigned long dst,
  1298. unsigned long src)
  1299. {
  1300. struct page *s_page, *d_page;
  1301. unsigned int s_objidx, d_objidx;
  1302. unsigned long s_off, d_off;
  1303. void *s_addr, *d_addr;
  1304. int s_size, d_size, size;
  1305. int written = 0;
  1306. s_size = d_size = class->size;
  1307. obj_to_location(src, &s_page, &s_objidx);
  1308. obj_to_location(dst, &d_page, &d_objidx);
  1309. s_off = (class->size * s_objidx) & ~PAGE_MASK;
  1310. d_off = (class->size * d_objidx) & ~PAGE_MASK;
  1311. if (s_off + class->size > PAGE_SIZE)
  1312. s_size = PAGE_SIZE - s_off;
  1313. if (d_off + class->size > PAGE_SIZE)
  1314. d_size = PAGE_SIZE - d_off;
  1315. s_addr = kmap_atomic(s_page);
  1316. d_addr = kmap_atomic(d_page);
  1317. while (1) {
  1318. size = min(s_size, d_size);
  1319. memcpy(d_addr + d_off, s_addr + s_off, size);
  1320. written += size;
  1321. if (written == class->size)
  1322. break;
  1323. s_off += size;
  1324. s_size -= size;
  1325. d_off += size;
  1326. d_size -= size;
  1327. if (s_off >= PAGE_SIZE) {
  1328. kunmap_atomic(d_addr);
  1329. kunmap_atomic(s_addr);
  1330. s_page = get_next_page(s_page);
  1331. s_addr = kmap_atomic(s_page);
  1332. d_addr = kmap_atomic(d_page);
  1333. s_size = class->size - written;
  1334. s_off = 0;
  1335. }
  1336. if (d_off >= PAGE_SIZE) {
  1337. kunmap_atomic(d_addr);
  1338. d_page = get_next_page(d_page);
  1339. d_addr = kmap_atomic(d_page);
  1340. d_size = class->size - written;
  1341. d_off = 0;
  1342. }
  1343. }
  1344. kunmap_atomic(d_addr);
  1345. kunmap_atomic(s_addr);
  1346. }
  1347. /*
  1348. * Find alloced object in zspage from index object and
  1349. * return handle.
  1350. */
  1351. static unsigned long find_alloced_obj(struct size_class *class,
  1352. struct page *page, int *obj_idx)
  1353. {
  1354. unsigned long head;
  1355. int offset = 0;
  1356. int index = *obj_idx;
  1357. unsigned long handle = 0;
  1358. void *addr = kmap_atomic(page);
  1359. offset = get_first_obj_offset(page);
  1360. offset += class->size * index;
  1361. while (offset < PAGE_SIZE) {
  1362. head = obj_to_head(page, addr + offset);
  1363. if (head & OBJ_ALLOCATED_TAG) {
  1364. handle = head & ~OBJ_ALLOCATED_TAG;
  1365. if (trypin_tag(handle))
  1366. break;
  1367. handle = 0;
  1368. }
  1369. offset += class->size;
  1370. index++;
  1371. }
  1372. kunmap_atomic(addr);
  1373. *obj_idx = index;
  1374. return handle;
  1375. }
  1376. struct zs_compact_control {
  1377. /* Source spage for migration which could be a subpage of zspage */
  1378. struct page *s_page;
  1379. /* Destination page for migration which should be a first page
  1380. * of zspage. */
  1381. struct page *d_page;
  1382. /* Starting object index within @s_page which used for live object
  1383. * in the subpage. */
  1384. int obj_idx;
  1385. };
  1386. static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
  1387. struct zs_compact_control *cc)
  1388. {
  1389. unsigned long used_obj, free_obj;
  1390. unsigned long handle;
  1391. struct page *s_page = cc->s_page;
  1392. struct page *d_page = cc->d_page;
  1393. int obj_idx = cc->obj_idx;
  1394. int ret = 0;
  1395. while (1) {
  1396. handle = find_alloced_obj(class, s_page, &obj_idx);
  1397. if (!handle) {
  1398. s_page = get_next_page(s_page);
  1399. if (!s_page)
  1400. break;
  1401. obj_idx = 0;
  1402. continue;
  1403. }
  1404. /* Stop if there is no more space */
  1405. if (zspage_full(class, get_zspage(d_page))) {
  1406. unpin_tag(handle);
  1407. ret = -ENOMEM;
  1408. break;
  1409. }
  1410. used_obj = handle_to_obj(handle);
  1411. free_obj = obj_malloc(class, get_zspage(d_page), handle);
  1412. zs_object_copy(class, free_obj, used_obj);
  1413. obj_idx++;
  1414. /*
  1415. * record_obj updates handle's value to free_obj and it will
  1416. * invalidate lock bit(ie, HANDLE_PIN_BIT) of handle, which
  1417. * breaks synchronization using pin_tag(e,g, zs_free) so
  1418. * let's keep the lock bit.
  1419. */
  1420. free_obj |= BIT(HANDLE_PIN_BIT);
  1421. record_obj(handle, free_obj);
  1422. unpin_tag(handle);
  1423. obj_free(class, used_obj);
  1424. }
  1425. /* Remember last position in this iteration */
  1426. cc->s_page = s_page;
  1427. cc->obj_idx = obj_idx;
  1428. return ret;
  1429. }
  1430. static struct zspage *isolate_zspage(struct size_class *class, bool source)
  1431. {
  1432. int i;
  1433. struct zspage *zspage;
  1434. enum fullness_group fg[2] = {ZS_ALMOST_EMPTY, ZS_ALMOST_FULL};
  1435. if (!source) {
  1436. fg[0] = ZS_ALMOST_FULL;
  1437. fg[1] = ZS_ALMOST_EMPTY;
  1438. }
  1439. for (i = 0; i < 2; i++) {
  1440. zspage = list_first_entry_or_null(&class->fullness_list[fg[i]],
  1441. struct zspage, list);
  1442. if (zspage) {
  1443. VM_BUG_ON(is_zspage_isolated(zspage));
  1444. remove_zspage(class, zspage, fg[i]);
  1445. return zspage;
  1446. }
  1447. }
  1448. return zspage;
  1449. }
  1450. /*
  1451. * putback_zspage - add @zspage into right class's fullness list
  1452. * @class: destination class
  1453. * @zspage: target page
  1454. *
  1455. * Return @zspage's fullness_group
  1456. */
  1457. static enum fullness_group putback_zspage(struct size_class *class,
  1458. struct zspage *zspage)
  1459. {
  1460. enum fullness_group fullness;
  1461. VM_BUG_ON(is_zspage_isolated(zspage));
  1462. fullness = get_fullness_group(class, zspage);
  1463. insert_zspage(class, zspage, fullness);
  1464. set_zspage_mapping(zspage, class->index, fullness);
  1465. return fullness;
  1466. }
  1467. #ifdef CONFIG_COMPACTION
  1468. /*
  1469. * To prevent zspage destroy during migration, zspage freeing should
  1470. * hold locks of all pages in the zspage.
  1471. */
  1472. static void lock_zspage(struct zspage *zspage)
  1473. {
  1474. struct page *page = get_first_page(zspage);
  1475. do {
  1476. lock_page(page);
  1477. } while ((page = get_next_page(page)) != NULL);
  1478. }
  1479. static int zs_init_fs_context(struct fs_context *fc)
  1480. {
  1481. return init_pseudo(fc, ZSMALLOC_MAGIC) ? 0 : -ENOMEM;
  1482. }
  1483. static struct file_system_type zsmalloc_fs = {
  1484. .name = "zsmalloc",
  1485. .init_fs_context = zs_init_fs_context,
  1486. .kill_sb = kill_anon_super,
  1487. };
  1488. static int zsmalloc_mount(void)
  1489. {
  1490. int ret = 0;
  1491. zsmalloc_mnt = kern_mount(&zsmalloc_fs);
  1492. if (IS_ERR(zsmalloc_mnt))
  1493. ret = PTR_ERR(zsmalloc_mnt);
  1494. return ret;
  1495. }
  1496. static void zsmalloc_unmount(void)
  1497. {
  1498. kern_unmount(zsmalloc_mnt);
  1499. }
  1500. static void migrate_lock_init(struct zspage *zspage)
  1501. {
  1502. rwlock_init(&zspage->lock);
  1503. }
  1504. static void migrate_read_lock(struct zspage *zspage) __acquires(&zspage->lock)
  1505. {
  1506. read_lock(&zspage->lock);
  1507. }
  1508. static void migrate_read_unlock(struct zspage *zspage) __releases(&zspage->lock)
  1509. {
  1510. read_unlock(&zspage->lock);
  1511. }
  1512. static void migrate_write_lock(struct zspage *zspage)
  1513. {
  1514. write_lock(&zspage->lock);
  1515. }
  1516. static void migrate_write_unlock(struct zspage *zspage)
  1517. {
  1518. write_unlock(&zspage->lock);
  1519. }
  1520. /* Number of isolated subpage for *page migration* in this zspage */
  1521. static void inc_zspage_isolation(struct zspage *zspage)
  1522. {
  1523. zspage->isolated++;
  1524. }
  1525. static void dec_zspage_isolation(struct zspage *zspage)
  1526. {
  1527. zspage->isolated--;
  1528. }
  1529. static void putback_zspage_deferred(struct zs_pool *pool,
  1530. struct size_class *class,
  1531. struct zspage *zspage)
  1532. {
  1533. enum fullness_group fg;
  1534. fg = putback_zspage(class, zspage);
  1535. if (fg == ZS_EMPTY)
  1536. schedule_work(&pool->free_work);
  1537. }
  1538. static inline void zs_pool_dec_isolated(struct zs_pool *pool)
  1539. {
  1540. VM_BUG_ON(atomic_long_read(&pool->isolated_pages) <= 0);
  1541. atomic_long_dec(&pool->isolated_pages);
  1542. /*
  1543. * Checking pool->destroying must happen after atomic_long_dec()
  1544. * for pool->isolated_pages above. Paired with the smp_mb() in
  1545. * zs_unregister_migration().
  1546. */
  1547. smp_mb__after_atomic();
  1548. if (atomic_long_read(&pool->isolated_pages) == 0 && pool->destroying)
  1549. wake_up_all(&pool->migration_wait);
  1550. }
  1551. static void replace_sub_page(struct size_class *class, struct zspage *zspage,
  1552. struct page *newpage, struct page *oldpage)
  1553. {
  1554. struct page *page;
  1555. struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE] = {NULL, };
  1556. int idx = 0;
  1557. page = get_first_page(zspage);
  1558. do {
  1559. if (page == oldpage)
  1560. pages[idx] = newpage;
  1561. else
  1562. pages[idx] = page;
  1563. idx++;
  1564. } while ((page = get_next_page(page)) != NULL);
  1565. create_page_chain(class, zspage, pages);
  1566. set_first_obj_offset(newpage, get_first_obj_offset(oldpage));
  1567. if (unlikely(PageHugeObject(oldpage)))
  1568. newpage->index = oldpage->index;
  1569. __SetPageMovable(newpage, page_mapping(oldpage));
  1570. }
  1571. static bool zs_page_isolate(struct page *page, isolate_mode_t mode)
  1572. {
  1573. struct zs_pool *pool;
  1574. struct size_class *class;
  1575. int class_idx;
  1576. enum fullness_group fullness;
  1577. struct zspage *zspage;
  1578. struct address_space *mapping;
  1579. /*
  1580. * Page is locked so zspage couldn't be destroyed. For detail, look at
  1581. * lock_zspage in free_zspage.
  1582. */
  1583. VM_BUG_ON_PAGE(!PageMovable(page), page);
  1584. VM_BUG_ON_PAGE(PageIsolated(page), page);
  1585. zspage = get_zspage(page);
  1586. /*
  1587. * Without class lock, fullness could be stale while class_idx is okay
  1588. * because class_idx is constant unless page is freed so we should get
  1589. * fullness again under class lock.
  1590. */
  1591. get_zspage_mapping(zspage, &class_idx, &fullness);
  1592. mapping = page_mapping(page);
  1593. pool = mapping->private_data;
  1594. class = pool->size_class[class_idx];
  1595. spin_lock(&class->lock);
  1596. if (get_zspage_inuse(zspage) == 0) {
  1597. spin_unlock(&class->lock);
  1598. return false;
  1599. }
  1600. /* zspage is isolated for object migration */
  1601. if (list_empty(&zspage->list) && !is_zspage_isolated(zspage)) {
  1602. spin_unlock(&class->lock);
  1603. return false;
  1604. }
  1605. /*
  1606. * If this is first time isolation for the zspage, isolate zspage from
  1607. * size_class to prevent further object allocation from the zspage.
  1608. */
  1609. if (!list_empty(&zspage->list) && !is_zspage_isolated(zspage)) {
  1610. get_zspage_mapping(zspage, &class_idx, &fullness);
  1611. atomic_long_inc(&pool->isolated_pages);
  1612. remove_zspage(class, zspage, fullness);
  1613. }
  1614. inc_zspage_isolation(zspage);
  1615. spin_unlock(&class->lock);
  1616. return true;
  1617. }
  1618. static int zs_page_migrate(struct address_space *mapping, struct page *newpage,
  1619. struct page *page, enum migrate_mode mode)
  1620. {
  1621. struct zs_pool *pool;
  1622. struct size_class *class;
  1623. int class_idx;
  1624. enum fullness_group fullness;
  1625. struct zspage *zspage;
  1626. struct page *dummy;
  1627. void *s_addr, *d_addr, *addr;
  1628. int offset, pos;
  1629. unsigned long handle, head;
  1630. unsigned long old_obj, new_obj;
  1631. unsigned int obj_idx;
  1632. int ret = -EAGAIN;
  1633. /*
  1634. * We cannot support the _NO_COPY case here, because copy needs to
  1635. * happen under the zs lock, which does not work with
  1636. * MIGRATE_SYNC_NO_COPY workflow.
  1637. */
  1638. if (mode == MIGRATE_SYNC_NO_COPY)
  1639. return -EINVAL;
  1640. VM_BUG_ON_PAGE(!PageMovable(page), page);
  1641. VM_BUG_ON_PAGE(!PageIsolated(page), page);
  1642. zspage = get_zspage(page);
  1643. /* Concurrent compactor cannot migrate any subpage in zspage */
  1644. migrate_write_lock(zspage);
  1645. get_zspage_mapping(zspage, &class_idx, &fullness);
  1646. pool = mapping->private_data;
  1647. class = pool->size_class[class_idx];
  1648. offset = get_first_obj_offset(page);
  1649. spin_lock(&class->lock);
  1650. if (!get_zspage_inuse(zspage)) {
  1651. /*
  1652. * Set "offset" to end of the page so that every loops
  1653. * skips unnecessary object scanning.
  1654. */
  1655. offset = PAGE_SIZE;
  1656. }
  1657. pos = offset;
  1658. s_addr = kmap_atomic(page);
  1659. while (pos < PAGE_SIZE) {
  1660. head = obj_to_head(page, s_addr + pos);
  1661. if (head & OBJ_ALLOCATED_TAG) {
  1662. handle = head & ~OBJ_ALLOCATED_TAG;
  1663. if (!trypin_tag(handle))
  1664. goto unpin_objects;
  1665. }
  1666. pos += class->size;
  1667. }
  1668. /*
  1669. * Here, any user cannot access all objects in the zspage so let's move.
  1670. */
  1671. d_addr = kmap_atomic(newpage);
  1672. memcpy(d_addr, s_addr, PAGE_SIZE);
  1673. kunmap_atomic(d_addr);
  1674. for (addr = s_addr + offset; addr < s_addr + pos;
  1675. addr += class->size) {
  1676. head = obj_to_head(page, addr);
  1677. if (head & OBJ_ALLOCATED_TAG) {
  1678. handle = head & ~OBJ_ALLOCATED_TAG;
  1679. if (!testpin_tag(handle))
  1680. BUG();
  1681. old_obj = handle_to_obj(handle);
  1682. obj_to_location(old_obj, &dummy, &obj_idx);
  1683. new_obj = (unsigned long)location_to_obj(newpage,
  1684. obj_idx);
  1685. new_obj |= BIT(HANDLE_PIN_BIT);
  1686. record_obj(handle, new_obj);
  1687. }
  1688. }
  1689. replace_sub_page(class, zspage, newpage, page);
  1690. get_page(newpage);
  1691. dec_zspage_isolation(zspage);
  1692. /*
  1693. * Page migration is done so let's putback isolated zspage to
  1694. * the list if @page is final isolated subpage in the zspage.
  1695. */
  1696. if (!is_zspage_isolated(zspage)) {
  1697. /*
  1698. * We cannot race with zs_destroy_pool() here because we wait
  1699. * for isolation to hit zero before we start destroying.
  1700. * Also, we ensure that everyone can see pool->destroying before
  1701. * we start waiting.
  1702. */
  1703. putback_zspage_deferred(pool, class, zspage);
  1704. zs_pool_dec_isolated(pool);
  1705. }
  1706. if (page_zone(newpage) != page_zone(page)) {
  1707. dec_zone_page_state(page, NR_ZSPAGES);
  1708. inc_zone_page_state(newpage, NR_ZSPAGES);
  1709. }
  1710. reset_page(page);
  1711. put_page(page);
  1712. page = newpage;
  1713. ret = MIGRATEPAGE_SUCCESS;
  1714. unpin_objects:
  1715. for (addr = s_addr + offset; addr < s_addr + pos;
  1716. addr += class->size) {
  1717. head = obj_to_head(page, addr);
  1718. if (head & OBJ_ALLOCATED_TAG) {
  1719. handle = head & ~OBJ_ALLOCATED_TAG;
  1720. if (!testpin_tag(handle))
  1721. BUG();
  1722. unpin_tag(handle);
  1723. }
  1724. }
  1725. kunmap_atomic(s_addr);
  1726. spin_unlock(&class->lock);
  1727. migrate_write_unlock(zspage);
  1728. return ret;
  1729. }
  1730. static void zs_page_putback(struct page *page)
  1731. {
  1732. struct zs_pool *pool;
  1733. struct size_class *class;
  1734. int class_idx;
  1735. enum fullness_group fg;
  1736. struct address_space *mapping;
  1737. struct zspage *zspage;
  1738. VM_BUG_ON_PAGE(!PageMovable(page), page);
  1739. VM_BUG_ON_PAGE(!PageIsolated(page), page);
  1740. zspage = get_zspage(page);
  1741. get_zspage_mapping(zspage, &class_idx, &fg);
  1742. mapping = page_mapping(page);
  1743. pool = mapping->private_data;
  1744. class = pool->size_class[class_idx];
  1745. spin_lock(&class->lock);
  1746. dec_zspage_isolation(zspage);
  1747. if (!is_zspage_isolated(zspage)) {
  1748. /*
  1749. * Due to page_lock, we cannot free zspage immediately
  1750. * so let's defer.
  1751. */
  1752. putback_zspage_deferred(pool, class, zspage);
  1753. zs_pool_dec_isolated(pool);
  1754. }
  1755. spin_unlock(&class->lock);
  1756. }
  1757. static const struct address_space_operations zsmalloc_aops = {
  1758. .isolate_page = zs_page_isolate,
  1759. .migratepage = zs_page_migrate,
  1760. .putback_page = zs_page_putback,
  1761. };
  1762. static int zs_register_migration(struct zs_pool *pool)
  1763. {
  1764. pool->inode = alloc_anon_inode(zsmalloc_mnt->mnt_sb);
  1765. if (IS_ERR(pool->inode)) {
  1766. pool->inode = NULL;
  1767. return 1;
  1768. }
  1769. pool->inode->i_mapping->private_data = pool;
  1770. pool->inode->i_mapping->a_ops = &zsmalloc_aops;
  1771. return 0;
  1772. }
  1773. static bool pool_isolated_are_drained(struct zs_pool *pool)
  1774. {
  1775. return atomic_long_read(&pool->isolated_pages) == 0;
  1776. }
  1777. /* Function for resolving migration */
  1778. static void wait_for_isolated_drain(struct zs_pool *pool)
  1779. {
  1780. /*
  1781. * We're in the process of destroying the pool, so there are no
  1782. * active allocations. zs_page_isolate() fails for completely free
  1783. * zspages, so we need only wait for the zs_pool's isolated
  1784. * count to hit zero.
  1785. */
  1786. wait_event(pool->migration_wait,
  1787. pool_isolated_are_drained(pool));
  1788. }
  1789. static void zs_unregister_migration(struct zs_pool *pool)
  1790. {
  1791. pool->destroying = true;
  1792. /*
  1793. * We need a memory barrier here to ensure global visibility of
  1794. * pool->destroying. Thus pool->isolated pages will either be 0 in which
  1795. * case we don't care, or it will be > 0 and pool->destroying will
  1796. * ensure that we wake up once isolation hits 0.
  1797. */
  1798. smp_mb();
  1799. wait_for_isolated_drain(pool); /* This can block */
  1800. flush_work(&pool->free_work);
  1801. iput(pool->inode);
  1802. }
  1803. /*
  1804. * Caller should hold page_lock of all pages in the zspage
  1805. * In here, we cannot use zspage meta data.
  1806. */
  1807. static void async_free_zspage(struct work_struct *work)
  1808. {
  1809. int i;
  1810. struct size_class *class;
  1811. unsigned int class_idx;
  1812. enum fullness_group fullness;
  1813. struct zspage *zspage, *tmp;
  1814. LIST_HEAD(free_pages);
  1815. struct zs_pool *pool = container_of(work, struct zs_pool,
  1816. free_work);
  1817. for (i = 0; i < ZS_SIZE_CLASSES; i++) {
  1818. class = pool->size_class[i];
  1819. if (class->index != i)
  1820. continue;
  1821. spin_lock(&class->lock);
  1822. list_splice_init(&class->fullness_list[ZS_EMPTY], &free_pages);
  1823. spin_unlock(&class->lock);
  1824. }
  1825. list_for_each_entry_safe(zspage, tmp, &free_pages, list) {
  1826. list_del(&zspage->list);
  1827. lock_zspage(zspage);
  1828. get_zspage_mapping(zspage, &class_idx, &fullness);
  1829. VM_BUG_ON(fullness != ZS_EMPTY);
  1830. class = pool->size_class[class_idx];
  1831. spin_lock(&class->lock);
  1832. __free_zspage(pool, pool->size_class[class_idx], zspage);
  1833. spin_unlock(&class->lock);
  1834. }
  1835. };
  1836. static void kick_deferred_free(struct zs_pool *pool)
  1837. {
  1838. schedule_work(&pool->free_work);
  1839. }
  1840. static void init_deferred_free(struct zs_pool *pool)
  1841. {
  1842. INIT_WORK(&pool->free_work, async_free_zspage);
  1843. }
  1844. static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage)
  1845. {
  1846. struct page *page = get_first_page(zspage);
  1847. do {
  1848. WARN_ON(!trylock_page(page));
  1849. __SetPageMovable(page, pool->inode->i_mapping);
  1850. unlock_page(page);
  1851. } while ((page = get_next_page(page)) != NULL);
  1852. }
  1853. #endif
  1854. /*
  1855. *
  1856. * Based on the number of unused allocated objects calculate
  1857. * and return the number of pages that we can free.
  1858. */
  1859. static unsigned long zs_can_compact(struct size_class *class)
  1860. {
  1861. unsigned long obj_wasted;
  1862. unsigned long obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
  1863. unsigned long obj_used = zs_stat_get(class, OBJ_USED);
  1864. if (obj_allocated <= obj_used)
  1865. return 0;
  1866. obj_wasted = obj_allocated - obj_used;
  1867. obj_wasted /= class->objs_per_zspage;
  1868. return obj_wasted * class->pages_per_zspage;
  1869. }
  1870. static unsigned long __zs_compact(struct zs_pool *pool,
  1871. struct size_class *class)
  1872. {
  1873. struct zs_compact_control cc;
  1874. struct zspage *src_zspage;
  1875. struct zspage *dst_zspage = NULL;
  1876. unsigned long pages_freed = 0;
  1877. spin_lock(&class->lock);
  1878. while ((src_zspage = isolate_zspage(class, true))) {
  1879. if (!zs_can_compact(class))
  1880. break;
  1881. cc.obj_idx = 0;
  1882. cc.s_page = get_first_page(src_zspage);
  1883. while ((dst_zspage = isolate_zspage(class, false))) {
  1884. cc.d_page = get_first_page(dst_zspage);
  1885. /*
  1886. * If there is no more space in dst_page, resched
  1887. * and see if anyone had allocated another zspage.
  1888. */
  1889. if (!migrate_zspage(pool, class, &cc))
  1890. break;
  1891. putback_zspage(class, dst_zspage);
  1892. }
  1893. /* Stop if we couldn't find slot */
  1894. if (dst_zspage == NULL)
  1895. break;
  1896. putback_zspage(class, dst_zspage);
  1897. if (putback_zspage(class, src_zspage) == ZS_EMPTY) {
  1898. free_zspage(pool, class, src_zspage);
  1899. pages_freed += class->pages_per_zspage;
  1900. }
  1901. spin_unlock(&class->lock);
  1902. cond_resched();
  1903. spin_lock(&class->lock);
  1904. }
  1905. if (src_zspage)
  1906. putback_zspage(class, src_zspage);
  1907. spin_unlock(&class->lock);
  1908. return pages_freed;
  1909. }
  1910. unsigned long zs_compact(struct zs_pool *pool)
  1911. {
  1912. int i;
  1913. struct size_class *class;
  1914. unsigned long pages_freed = 0;
  1915. for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
  1916. class = pool->size_class[i];
  1917. if (!class)
  1918. continue;
  1919. if (class->index != i)
  1920. continue;
  1921. pages_freed += __zs_compact(pool, class);
  1922. }
  1923. atomic_long_add(pages_freed, &pool->stats.pages_compacted);
  1924. return pages_freed;
  1925. }
  1926. EXPORT_SYMBOL_GPL(zs_compact);
  1927. void zs_pool_stats(struct zs_pool *pool, struct zs_pool_stats *stats)
  1928. {
  1929. memcpy(stats, &pool->stats, sizeof(struct zs_pool_stats));
  1930. }
  1931. EXPORT_SYMBOL_GPL(zs_pool_stats);
  1932. static unsigned long zs_shrinker_scan(struct shrinker *shrinker,
  1933. struct shrink_control *sc)
  1934. {
  1935. unsigned long pages_freed;
  1936. struct zs_pool *pool = container_of(shrinker, struct zs_pool,
  1937. shrinker);
  1938. /*
  1939. * Compact classes and calculate compaction delta.
  1940. * Can run concurrently with a manually triggered
  1941. * (by user) compaction.
  1942. */
  1943. pages_freed = zs_compact(pool);
  1944. return pages_freed ? pages_freed : SHRINK_STOP;
  1945. }
  1946. static unsigned long zs_shrinker_count(struct shrinker *shrinker,
  1947. struct shrink_control *sc)
  1948. {
  1949. int i;
  1950. struct size_class *class;
  1951. unsigned long pages_to_free = 0;
  1952. struct zs_pool *pool = container_of(shrinker, struct zs_pool,
  1953. shrinker);
  1954. for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
  1955. class = pool->size_class[i];
  1956. if (!class)
  1957. continue;
  1958. if (class->index != i)
  1959. continue;
  1960. pages_to_free += zs_can_compact(class);
  1961. }
  1962. return pages_to_free;
  1963. }
  1964. static void zs_unregister_shrinker(struct zs_pool *pool)
  1965. {
  1966. unregister_shrinker(&pool->shrinker);
  1967. }
  1968. static int zs_register_shrinker(struct zs_pool *pool)
  1969. {
  1970. pool->shrinker.scan_objects = zs_shrinker_scan;
  1971. pool->shrinker.count_objects = zs_shrinker_count;
  1972. pool->shrinker.batch = 0;
  1973. pool->shrinker.seeks = DEFAULT_SEEKS;
  1974. return register_shrinker(&pool->shrinker);
  1975. }
  1976. /**
  1977. * zs_create_pool - Creates an allocation pool to work from.
  1978. * @name: pool name to be created
  1979. *
  1980. * This function must be called before anything when using
  1981. * the zsmalloc allocator.
  1982. *
  1983. * On success, a pointer to the newly created pool is returned,
  1984. * otherwise NULL.
  1985. */
  1986. struct zs_pool *zs_create_pool(const char *name)
  1987. {
  1988. int i;
  1989. struct zs_pool *pool;
  1990. struct size_class *prev_class = NULL;
  1991. pool = kzalloc(sizeof(*pool), GFP_KERNEL);
  1992. if (!pool)
  1993. return NULL;
  1994. init_deferred_free(pool);
  1995. pool->name = kstrdup(name, GFP_KERNEL);
  1996. if (!pool->name)
  1997. goto err;
  1998. #ifdef CONFIG_COMPACTION
  1999. init_waitqueue_head(&pool->migration_wait);
  2000. #endif
  2001. if (create_cache(pool))
  2002. goto err;
  2003. /*
  2004. * Iterate reversely, because, size of size_class that we want to use
  2005. * for merging should be larger or equal to current size.
  2006. */
  2007. for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
  2008. int size;
  2009. int pages_per_zspage;
  2010. int objs_per_zspage;
  2011. struct size_class *class;
  2012. int fullness = 0;
  2013. size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
  2014. if (size > ZS_MAX_ALLOC_SIZE)
  2015. size = ZS_MAX_ALLOC_SIZE;
  2016. pages_per_zspage = get_pages_per_zspage(size);
  2017. objs_per_zspage = pages_per_zspage * PAGE_SIZE / size;
  2018. /*
  2019. * We iterate from biggest down to smallest classes,
  2020. * so huge_class_size holds the size of the first huge
  2021. * class. Any object bigger than or equal to that will
  2022. * endup in the huge class.
  2023. */
  2024. if (pages_per_zspage != 1 && objs_per_zspage != 1 &&
  2025. !huge_class_size) {
  2026. huge_class_size = size;
  2027. /*
  2028. * The object uses ZS_HANDLE_SIZE bytes to store the
  2029. * handle. We need to subtract it, because zs_malloc()
  2030. * unconditionally adds handle size before it performs
  2031. * size class search - so object may be smaller than
  2032. * huge class size, yet it still can end up in the huge
  2033. * class because it grows by ZS_HANDLE_SIZE extra bytes
  2034. * right before class lookup.
  2035. */
  2036. huge_class_size -= (ZS_HANDLE_SIZE - 1);
  2037. }
  2038. /*
  2039. * size_class is used for normal zsmalloc operation such
  2040. * as alloc/free for that size. Although it is natural that we
  2041. * have one size_class for each size, there is a chance that we
  2042. * can get more memory utilization if we use one size_class for
  2043. * many different sizes whose size_class have same
  2044. * characteristics. So, we makes size_class point to
  2045. * previous size_class if possible.
  2046. */
  2047. if (prev_class) {
  2048. if (can_merge(prev_class, pages_per_zspage, objs_per_zspage)) {
  2049. pool->size_class[i] = prev_class;
  2050. continue;
  2051. }
  2052. }
  2053. class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
  2054. if (!class)
  2055. goto err;
  2056. class->size = size;
  2057. class->index = i;
  2058. class->pages_per_zspage = pages_per_zspage;
  2059. class->objs_per_zspage = objs_per_zspage;
  2060. spin_lock_init(&class->lock);
  2061. pool->size_class[i] = class;
  2062. for (fullness = ZS_EMPTY; fullness < NR_ZS_FULLNESS;
  2063. fullness++)
  2064. INIT_LIST_HEAD(&class->fullness_list[fullness]);
  2065. prev_class = class;
  2066. }
  2067. /* debug only, don't abort if it fails */
  2068. zs_pool_stat_create(pool, name);
  2069. if (zs_register_migration(pool))
  2070. goto err;
  2071. /*
  2072. * Not critical since shrinker is only used to trigger internal
  2073. * defragmentation of the pool which is pretty optional thing. If
  2074. * registration fails we still can use the pool normally and user can
  2075. * trigger compaction manually. Thus, ignore return code.
  2076. */
  2077. zs_register_shrinker(pool);
  2078. return pool;
  2079. err:
  2080. zs_destroy_pool(pool);
  2081. return NULL;
  2082. }
  2083. EXPORT_SYMBOL_GPL(zs_create_pool);
  2084. void zs_destroy_pool(struct zs_pool *pool)
  2085. {
  2086. int i;
  2087. zs_unregister_shrinker(pool);
  2088. zs_unregister_migration(pool);
  2089. zs_pool_stat_destroy(pool);
  2090. for (i = 0; i < ZS_SIZE_CLASSES; i++) {
  2091. int fg;
  2092. struct size_class *class = pool->size_class[i];
  2093. if (!class)
  2094. continue;
  2095. if (class->index != i)
  2096. continue;
  2097. for (fg = ZS_EMPTY; fg < NR_ZS_FULLNESS; fg++) {
  2098. if (!list_empty(&class->fullness_list[fg])) {
  2099. pr_info("Freeing non-empty class with size %db, fullness group %d\n",
  2100. class->size, fg);
  2101. }
  2102. }
  2103. kfree(class);
  2104. }
  2105. destroy_cache(pool);
  2106. kfree(pool->name);
  2107. kfree(pool);
  2108. }
  2109. EXPORT_SYMBOL_GPL(zs_destroy_pool);
  2110. static int __init zs_init(void)
  2111. {
  2112. int ret;
  2113. ret = zsmalloc_mount();
  2114. if (ret)
  2115. goto out;
  2116. ret = cpuhp_setup_state(CPUHP_MM_ZS_PREPARE, "mm/zsmalloc:prepare",
  2117. zs_cpu_prepare, zs_cpu_dead);
  2118. if (ret)
  2119. goto hp_setup_fail;
  2120. #ifdef CONFIG_ZPOOL
  2121. zpool_register_driver(&zs_zpool_driver);
  2122. #endif
  2123. zs_stat_init();
  2124. return 0;
  2125. hp_setup_fail:
  2126. zsmalloc_unmount();
  2127. out:
  2128. return ret;
  2129. }
  2130. static void __exit zs_exit(void)
  2131. {
  2132. #ifdef CONFIG_ZPOOL
  2133. zpool_unregister_driver(&zs_zpool_driver);
  2134. #endif
  2135. zsmalloc_unmount();
  2136. cpuhp_remove_state(CPUHP_MM_ZS_PREPARE);
  2137. zs_stat_exit();
  2138. }
  2139. module_init(zs_init);
  2140. module_exit(zs_exit);
  2141. MODULE_LICENSE("Dual BSD/GPL");
  2142. MODULE_AUTHOR("Nitin Gupta <ngupta@vflare.org>");