xfs_mru_cache.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (c) 2006-2007 Silicon Graphics, Inc.
  4. * All Rights Reserved.
  5. */
  6. #include "xfs.h"
  7. #include "xfs_mru_cache.h"
  8. /*
  9. * The MRU Cache data structure consists of a data store, an array of lists and
  10. * a lock to protect its internal state. At initialisation time, the client
  11. * supplies an element lifetime in milliseconds and a group count, as well as a
  12. * function pointer to call when deleting elements. A data structure for
  13. * queueing up work in the form of timed callbacks is also included.
  14. *
  15. * The group count controls how many lists are created, and thereby how finely
  16. * the elements are grouped in time. When reaping occurs, all the elements in
  17. * all the lists whose time has expired are deleted.
  18. *
  19. * To give an example of how this works in practice, consider a client that
  20. * initialises an MRU Cache with a lifetime of ten seconds and a group count of
  21. * five. Five internal lists will be created, each representing a two second
  22. * period in time. When the first element is added, time zero for the data
  23. * structure is initialised to the current time.
  24. *
  25. * All the elements added in the first two seconds are appended to the first
  26. * list. Elements added in the third second go into the second list, and so on.
  27. * If an element is accessed at any point, it is removed from its list and
  28. * inserted at the head of the current most-recently-used list.
  29. *
  30. * The reaper function will have nothing to do until at least twelve seconds
  31. * have elapsed since the first element was added. The reason for this is that
  32. * if it were called at t=11s, there could be elements in the first list that
  33. * have only been inactive for nine seconds, so it still does nothing. If it is
  34. * called anywhere between t=12 and t=14 seconds, it will delete all the
  35. * elements that remain in the first list. It's therefore possible for elements
  36. * to remain in the data store even after they've been inactive for up to
  37. * (t + t/g) seconds, where t is the inactive element lifetime and g is the
  38. * number of groups.
  39. *
  40. * The above example assumes that the reaper function gets called at least once
  41. * every (t/g) seconds. If it is called less frequently, unused elements will
  42. * accumulate in the reap list until the reaper function is eventually called.
  43. * The current implementation uses work queue callbacks to carefully time the
  44. * reaper function calls, so this should happen rarely, if at all.
  45. *
  46. * From a design perspective, the primary reason for the choice of a list array
  47. * representing discrete time intervals is that it's only practical to reap
  48. * expired elements in groups of some appreciable size. This automatically
  49. * introduces a granularity to element lifetimes, so there's no point storing an
  50. * individual timeout with each element that specifies a more precise reap time.
  51. * The bonus is a saving of sizeof(long) bytes of memory per element stored.
  52. *
  53. * The elements could have been stored in just one list, but an array of
  54. * counters or pointers would need to be maintained to allow them to be divided
  55. * up into discrete time groups. More critically, the process of touching or
  56. * removing an element would involve walking large portions of the entire list,
  57. * which would have a detrimental effect on performance. The additional memory
  58. * requirement for the array of list heads is minimal.
  59. *
  60. * When an element is touched or deleted, it needs to be removed from its
  61. * current list. Doubly linked lists are used to make the list maintenance
  62. * portion of these operations O(1). Since reaper timing can be imprecise,
  63. * inserts and lookups can occur when there are no free lists available. When
  64. * this happens, all the elements on the LRU list need to be migrated to the end
  65. * of the reap list. To keep the list maintenance portion of these operations
  66. * O(1) also, list tails need to be accessible without walking the entire list.
  67. * This is the reason why doubly linked list heads are used.
  68. */
  69. /*
  70. * An MRU Cache is a dynamic data structure that stores its elements in a way
  71. * that allows efficient lookups, but also groups them into discrete time
  72. * intervals based on insertion time. This allows elements to be efficiently
  73. * and automatically reaped after a fixed period of inactivity.
  74. *
  75. * When a client data pointer is stored in the MRU Cache it needs to be added to
  76. * both the data store and to one of the lists. It must also be possible to
  77. * access each of these entries via the other, i.e. to:
  78. *
  79. * a) Walk a list, removing the corresponding data store entry for each item.
  80. * b) Look up a data store entry, then access its list entry directly.
  81. *
  82. * To achieve both of these goals, each entry must contain both a list entry and
  83. * a key, in addition to the user's data pointer. Note that it's not a good
  84. * idea to have the client embed one of these structures at the top of their own
  85. * data structure, because inserting the same item more than once would most
  86. * likely result in a loop in one of the lists. That's a sure-fire recipe for
  87. * an infinite loop in the code.
  88. */
  89. struct xfs_mru_cache {
  90. struct radix_tree_root store; /* Core storage data structure. */
  91. struct list_head *lists; /* Array of lists, one per grp. */
  92. struct list_head reap_list; /* Elements overdue for reaping. */
  93. spinlock_t lock; /* Lock to protect this struct. */
  94. unsigned int grp_count; /* Number of discrete groups. */
  95. unsigned int grp_time; /* Time period spanned by grps. */
  96. unsigned int lru_grp; /* Group containing time zero. */
  97. unsigned long time_zero; /* Time first element was added. */
  98. xfs_mru_cache_free_func_t free_func; /* Function pointer for freeing. */
  99. struct delayed_work work; /* Workqueue data for reaping. */
  100. unsigned int queued; /* work has been queued */
  101. void *data;
  102. };
  103. static struct workqueue_struct *xfs_mru_reap_wq;
  104. /*
  105. * When inserting, destroying or reaping, it's first necessary to update the
  106. * lists relative to a particular time. In the case of destroying, that time
  107. * will be well in the future to ensure that all items are moved to the reap
  108. * list. In all other cases though, the time will be the current time.
  109. *
  110. * This function enters a loop, moving the contents of the LRU list to the reap
  111. * list again and again until either a) the lists are all empty, or b) time zero
  112. * has been advanced sufficiently to be within the immediate element lifetime.
  113. *
  114. * Case a) above is detected by counting how many groups are migrated and
  115. * stopping when they've all been moved. Case b) is detected by monitoring the
  116. * time_zero field, which is updated as each group is migrated.
  117. *
  118. * The return value is the earliest time that more migration could be needed, or
  119. * zero if there's no need to schedule more work because the lists are empty.
  120. */
  121. STATIC unsigned long
  122. _xfs_mru_cache_migrate(
  123. struct xfs_mru_cache *mru,
  124. unsigned long now)
  125. {
  126. unsigned int grp;
  127. unsigned int migrated = 0;
  128. struct list_head *lru_list;
  129. /* Nothing to do if the data store is empty. */
  130. if (!mru->time_zero)
  131. return 0;
  132. /* While time zero is older than the time spanned by all the lists. */
  133. while (mru->time_zero <= now - mru->grp_count * mru->grp_time) {
  134. /*
  135. * If the LRU list isn't empty, migrate its elements to the tail
  136. * of the reap list.
  137. */
  138. lru_list = mru->lists + mru->lru_grp;
  139. if (!list_empty(lru_list))
  140. list_splice_init(lru_list, mru->reap_list.prev);
  141. /*
  142. * Advance the LRU group number, freeing the old LRU list to
  143. * become the new MRU list; advance time zero accordingly.
  144. */
  145. mru->lru_grp = (mru->lru_grp + 1) % mru->grp_count;
  146. mru->time_zero += mru->grp_time;
  147. /*
  148. * If reaping is so far behind that all the elements on all the
  149. * lists have been migrated to the reap list, it's now empty.
  150. */
  151. if (++migrated == mru->grp_count) {
  152. mru->lru_grp = 0;
  153. mru->time_zero = 0;
  154. return 0;
  155. }
  156. }
  157. /* Find the first non-empty list from the LRU end. */
  158. for (grp = 0; grp < mru->grp_count; grp++) {
  159. /* Check the grp'th list from the LRU end. */
  160. lru_list = mru->lists + ((mru->lru_grp + grp) % mru->grp_count);
  161. if (!list_empty(lru_list))
  162. return mru->time_zero +
  163. (mru->grp_count + grp) * mru->grp_time;
  164. }
  165. /* All the lists must be empty. */
  166. mru->lru_grp = 0;
  167. mru->time_zero = 0;
  168. return 0;
  169. }
  170. /*
  171. * When inserting or doing a lookup, an element needs to be inserted into the
  172. * MRU list. The lists must be migrated first to ensure that they're
  173. * up-to-date, otherwise the new element could be given a shorter lifetime in
  174. * the cache than it should.
  175. */
  176. STATIC void
  177. _xfs_mru_cache_list_insert(
  178. struct xfs_mru_cache *mru,
  179. struct xfs_mru_cache_elem *elem)
  180. {
  181. unsigned int grp = 0;
  182. unsigned long now = jiffies;
  183. /*
  184. * If the data store is empty, initialise time zero, leave grp set to
  185. * zero and start the work queue timer if necessary. Otherwise, set grp
  186. * to the number of group times that have elapsed since time zero.
  187. */
  188. if (!_xfs_mru_cache_migrate(mru, now)) {
  189. mru->time_zero = now;
  190. if (!mru->queued) {
  191. mru->queued = 1;
  192. queue_delayed_work(xfs_mru_reap_wq, &mru->work,
  193. mru->grp_count * mru->grp_time);
  194. }
  195. } else {
  196. grp = (now - mru->time_zero) / mru->grp_time;
  197. grp = (mru->lru_grp + grp) % mru->grp_count;
  198. }
  199. /* Insert the element at the tail of the corresponding list. */
  200. list_add_tail(&elem->list_node, mru->lists + grp);
  201. }
  202. /*
  203. * When destroying or reaping, all the elements that were migrated to the reap
  204. * list need to be deleted. For each element this involves removing it from the
  205. * data store, removing it from the reap list, calling the client's free
  206. * function and deleting the element from the element zone.
  207. *
  208. * We get called holding the mru->lock, which we drop and then reacquire.
  209. * Sparse need special help with this to tell it we know what we are doing.
  210. */
  211. STATIC void
  212. _xfs_mru_cache_clear_reap_list(
  213. struct xfs_mru_cache *mru)
  214. __releases(mru->lock) __acquires(mru->lock)
  215. {
  216. struct xfs_mru_cache_elem *elem, *next;
  217. struct list_head tmp;
  218. INIT_LIST_HEAD(&tmp);
  219. list_for_each_entry_safe(elem, next, &mru->reap_list, list_node) {
  220. /* Remove the element from the data store. */
  221. radix_tree_delete(&mru->store, elem->key);
  222. /*
  223. * remove to temp list so it can be freed without
  224. * needing to hold the lock
  225. */
  226. list_move(&elem->list_node, &tmp);
  227. }
  228. spin_unlock(&mru->lock);
  229. list_for_each_entry_safe(elem, next, &tmp, list_node) {
  230. list_del_init(&elem->list_node);
  231. mru->free_func(mru->data, elem);
  232. }
  233. spin_lock(&mru->lock);
  234. }
  235. /*
  236. * We fire the reap timer every group expiry interval so
  237. * we always have a reaper ready to run. This makes shutdown
  238. * and flushing of the reaper easy to do. Hence we need to
  239. * keep when the next reap must occur so we can determine
  240. * at each interval whether there is anything we need to do.
  241. */
  242. STATIC void
  243. _xfs_mru_cache_reap(
  244. struct work_struct *work)
  245. {
  246. struct xfs_mru_cache *mru =
  247. container_of(work, struct xfs_mru_cache, work.work);
  248. unsigned long now, next;
  249. ASSERT(mru && mru->lists);
  250. if (!mru || !mru->lists)
  251. return;
  252. spin_lock(&mru->lock);
  253. next = _xfs_mru_cache_migrate(mru, jiffies);
  254. _xfs_mru_cache_clear_reap_list(mru);
  255. mru->queued = next;
  256. if ((mru->queued > 0)) {
  257. now = jiffies;
  258. if (next <= now)
  259. next = 0;
  260. else
  261. next -= now;
  262. queue_delayed_work(xfs_mru_reap_wq, &mru->work, next);
  263. }
  264. spin_unlock(&mru->lock);
  265. }
  266. int
  267. xfs_mru_cache_init(void)
  268. {
  269. xfs_mru_reap_wq = alloc_workqueue("xfs_mru_cache",
  270. WQ_MEM_RECLAIM|WQ_FREEZABLE, 1);
  271. if (!xfs_mru_reap_wq)
  272. return -ENOMEM;
  273. return 0;
  274. }
  275. void
  276. xfs_mru_cache_uninit(void)
  277. {
  278. destroy_workqueue(xfs_mru_reap_wq);
  279. }
  280. /*
  281. * To initialise a struct xfs_mru_cache pointer, call xfs_mru_cache_create()
  282. * with the address of the pointer, a lifetime value in milliseconds, a group
  283. * count and a free function to use when deleting elements. This function
  284. * returns 0 if the initialisation was successful.
  285. */
  286. int
  287. xfs_mru_cache_create(
  288. struct xfs_mru_cache **mrup,
  289. void *data,
  290. unsigned int lifetime_ms,
  291. unsigned int grp_count,
  292. xfs_mru_cache_free_func_t free_func)
  293. {
  294. struct xfs_mru_cache *mru = NULL;
  295. int err = 0, grp;
  296. unsigned int grp_time;
  297. if (mrup)
  298. *mrup = NULL;
  299. if (!mrup || !grp_count || !lifetime_ms || !free_func)
  300. return -EINVAL;
  301. if (!(grp_time = msecs_to_jiffies(lifetime_ms) / grp_count))
  302. return -EINVAL;
  303. if (!(mru = kmem_zalloc(sizeof(*mru), 0)))
  304. return -ENOMEM;
  305. /* An extra list is needed to avoid reaping up to a grp_time early. */
  306. mru->grp_count = grp_count + 1;
  307. mru->lists = kmem_zalloc(mru->grp_count * sizeof(*mru->lists), 0);
  308. if (!mru->lists) {
  309. err = -ENOMEM;
  310. goto exit;
  311. }
  312. for (grp = 0; grp < mru->grp_count; grp++)
  313. INIT_LIST_HEAD(mru->lists + grp);
  314. /*
  315. * We use GFP_KERNEL radix tree preload and do inserts under a
  316. * spinlock so GFP_ATOMIC is appropriate for the radix tree itself.
  317. */
  318. INIT_RADIX_TREE(&mru->store, GFP_ATOMIC);
  319. INIT_LIST_HEAD(&mru->reap_list);
  320. spin_lock_init(&mru->lock);
  321. INIT_DELAYED_WORK(&mru->work, _xfs_mru_cache_reap);
  322. mru->grp_time = grp_time;
  323. mru->free_func = free_func;
  324. mru->data = data;
  325. *mrup = mru;
  326. exit:
  327. if (err && mru && mru->lists)
  328. kmem_free(mru->lists);
  329. if (err && mru)
  330. kmem_free(mru);
  331. return err;
  332. }
  333. /*
  334. * Call xfs_mru_cache_flush() to flush out all cached entries, calling their
  335. * free functions as they're deleted. When this function returns, the caller is
  336. * guaranteed that all the free functions for all the elements have finished
  337. * executing and the reaper is not running.
  338. */
  339. static void
  340. xfs_mru_cache_flush(
  341. struct xfs_mru_cache *mru)
  342. {
  343. if (!mru || !mru->lists)
  344. return;
  345. spin_lock(&mru->lock);
  346. if (mru->queued) {
  347. spin_unlock(&mru->lock);
  348. cancel_delayed_work_sync(&mru->work);
  349. spin_lock(&mru->lock);
  350. }
  351. _xfs_mru_cache_migrate(mru, jiffies + mru->grp_count * mru->grp_time);
  352. _xfs_mru_cache_clear_reap_list(mru);
  353. spin_unlock(&mru->lock);
  354. }
  355. void
  356. xfs_mru_cache_destroy(
  357. struct xfs_mru_cache *mru)
  358. {
  359. if (!mru || !mru->lists)
  360. return;
  361. xfs_mru_cache_flush(mru);
  362. kmem_free(mru->lists);
  363. kmem_free(mru);
  364. }
  365. /*
  366. * To insert an element, call xfs_mru_cache_insert() with the data store, the
  367. * element's key and the client data pointer. This function returns 0 on
  368. * success or ENOMEM if memory for the data element couldn't be allocated.
  369. */
  370. int
  371. xfs_mru_cache_insert(
  372. struct xfs_mru_cache *mru,
  373. unsigned long key,
  374. struct xfs_mru_cache_elem *elem)
  375. {
  376. int error;
  377. ASSERT(mru && mru->lists);
  378. if (!mru || !mru->lists)
  379. return -EINVAL;
  380. if (radix_tree_preload(GFP_NOFS))
  381. return -ENOMEM;
  382. INIT_LIST_HEAD(&elem->list_node);
  383. elem->key = key;
  384. spin_lock(&mru->lock);
  385. error = radix_tree_insert(&mru->store, key, elem);
  386. radix_tree_preload_end();
  387. if (!error)
  388. _xfs_mru_cache_list_insert(mru, elem);
  389. spin_unlock(&mru->lock);
  390. return error;
  391. }
  392. /*
  393. * To remove an element without calling the free function, call
  394. * xfs_mru_cache_remove() with the data store and the element's key. On success
  395. * the client data pointer for the removed element is returned, otherwise this
  396. * function will return a NULL pointer.
  397. */
  398. struct xfs_mru_cache_elem *
  399. xfs_mru_cache_remove(
  400. struct xfs_mru_cache *mru,
  401. unsigned long key)
  402. {
  403. struct xfs_mru_cache_elem *elem;
  404. ASSERT(mru && mru->lists);
  405. if (!mru || !mru->lists)
  406. return NULL;
  407. spin_lock(&mru->lock);
  408. elem = radix_tree_delete(&mru->store, key);
  409. if (elem)
  410. list_del(&elem->list_node);
  411. spin_unlock(&mru->lock);
  412. return elem;
  413. }
  414. /*
  415. * To remove and element and call the free function, call xfs_mru_cache_delete()
  416. * with the data store and the element's key.
  417. */
  418. void
  419. xfs_mru_cache_delete(
  420. struct xfs_mru_cache *mru,
  421. unsigned long key)
  422. {
  423. struct xfs_mru_cache_elem *elem;
  424. elem = xfs_mru_cache_remove(mru, key);
  425. if (elem)
  426. mru->free_func(mru->data, elem);
  427. }
  428. /*
  429. * To look up an element using its key, call xfs_mru_cache_lookup() with the
  430. * data store and the element's key. If found, the element will be moved to the
  431. * head of the MRU list to indicate that it's been touched.
  432. *
  433. * The internal data structures are protected by a spinlock that is STILL HELD
  434. * when this function returns. Call xfs_mru_cache_done() to release it. Note
  435. * that it is not safe to call any function that might sleep in the interim.
  436. *
  437. * The implementation could have used reference counting to avoid this
  438. * restriction, but since most clients simply want to get, set or test a member
  439. * of the returned data structure, the extra per-element memory isn't warranted.
  440. *
  441. * If the element isn't found, this function returns NULL and the spinlock is
  442. * released. xfs_mru_cache_done() should NOT be called when this occurs.
  443. *
  444. * Because sparse isn't smart enough to know about conditional lock return
  445. * status, we need to help it get it right by annotating the path that does
  446. * not release the lock.
  447. */
  448. struct xfs_mru_cache_elem *
  449. xfs_mru_cache_lookup(
  450. struct xfs_mru_cache *mru,
  451. unsigned long key)
  452. {
  453. struct xfs_mru_cache_elem *elem;
  454. ASSERT(mru && mru->lists);
  455. if (!mru || !mru->lists)
  456. return NULL;
  457. spin_lock(&mru->lock);
  458. elem = radix_tree_lookup(&mru->store, key);
  459. if (elem) {
  460. list_del(&elem->list_node);
  461. _xfs_mru_cache_list_insert(mru, elem);
  462. __release(mru_lock); /* help sparse not be stupid */
  463. } else
  464. spin_unlock(&mru->lock);
  465. return elem;
  466. }
  467. /*
  468. * To release the internal data structure spinlock after having performed an
  469. * xfs_mru_cache_lookup() or an xfs_mru_cache_peek(), call xfs_mru_cache_done()
  470. * with the data store pointer.
  471. */
  472. void
  473. xfs_mru_cache_done(
  474. struct xfs_mru_cache *mru)
  475. __releases(mru->lock)
  476. {
  477. spin_unlock(&mru->lock);
  478. }