lru_cache.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. lru_cache.c
  4. This file is part of DRBD by Philipp Reisner and Lars Ellenberg.
  5. Copyright (C) 2003-2008, LINBIT Information Technologies GmbH.
  6. Copyright (C) 2003-2008, Philipp Reisner <[email protected]>.
  7. Copyright (C) 2003-2008, Lars Ellenberg <[email protected]>.
  8. */
  9. #include <linux/module.h>
  10. #include <linux/bitops.h>
  11. #include <linux/slab.h>
  12. #include <linux/string.h> /* for memset */
  13. #include <linux/seq_file.h> /* for seq_printf */
  14. #include <linux/lru_cache.h>
  15. MODULE_AUTHOR("Philipp Reisner <[email protected]>, "
  16. "Lars Ellenberg <[email protected]>");
  17. MODULE_DESCRIPTION("lru_cache - Track sets of hot objects");
  18. MODULE_LICENSE("GPL");
  19. /* this is developers aid only.
  20. * it catches concurrent access (lack of locking on the users part) */
  21. #define PARANOIA_ENTRY() do { \
  22. BUG_ON(!lc); \
  23. BUG_ON(!lc->nr_elements); \
  24. BUG_ON(test_and_set_bit(__LC_PARANOIA, &lc->flags)); \
  25. } while (0)
  26. #define RETURN(x...) do { \
  27. clear_bit_unlock(__LC_PARANOIA, &lc->flags); \
  28. return x ; } while (0)
  29. /* BUG() if e is not one of the elements tracked by lc */
  30. #define PARANOIA_LC_ELEMENT(lc, e) do { \
  31. struct lru_cache *lc_ = (lc); \
  32. struct lc_element *e_ = (e); \
  33. unsigned i = e_->lc_index; \
  34. BUG_ON(i >= lc_->nr_elements); \
  35. BUG_ON(lc_->lc_element[i] != e_); } while (0)
  36. /* We need to atomically
  37. * - try to grab the lock (set LC_LOCKED)
  38. * - only if there is no pending transaction
  39. * (neither LC_DIRTY nor LC_STARVING is set)
  40. * Because of PARANOIA_ENTRY() above abusing lc->flags as well,
  41. * it is not sufficient to just say
  42. * return 0 == cmpxchg(&lc->flags, 0, LC_LOCKED);
  43. */
  44. int lc_try_lock(struct lru_cache *lc)
  45. {
  46. unsigned long val;
  47. do {
  48. val = cmpxchg(&lc->flags, 0, LC_LOCKED);
  49. } while (unlikely (val == LC_PARANOIA));
  50. /* Spin until no-one is inside a PARANOIA_ENTRY()/RETURN() section. */
  51. return 0 == val;
  52. #if 0
  53. /* Alternative approach, spin in case someone enters or leaves a
  54. * PARANOIA_ENTRY()/RETURN() section. */
  55. unsigned long old, new, val;
  56. do {
  57. old = lc->flags & LC_PARANOIA;
  58. new = old | LC_LOCKED;
  59. val = cmpxchg(&lc->flags, old, new);
  60. } while (unlikely (val == (old ^ LC_PARANOIA)));
  61. return old == val;
  62. #endif
  63. }
  64. /**
  65. * lc_create - prepares to track objects in an active set
  66. * @name: descriptive name only used in lc_seq_printf_stats and lc_seq_dump_details
  67. * @cache: cache root pointer
  68. * @max_pending_changes: maximum changes to accumulate until a transaction is required
  69. * @e_count: number of elements allowed to be active simultaneously
  70. * @e_size: size of the tracked objects
  71. * @e_off: offset to the &struct lc_element member in a tracked object
  72. *
  73. * Returns a pointer to a newly initialized struct lru_cache on success,
  74. * or NULL on (allocation) failure.
  75. */
  76. struct lru_cache *lc_create(const char *name, struct kmem_cache *cache,
  77. unsigned max_pending_changes,
  78. unsigned e_count, size_t e_size, size_t e_off)
  79. {
  80. struct hlist_head *slot = NULL;
  81. struct lc_element **element = NULL;
  82. struct lru_cache *lc;
  83. struct lc_element *e;
  84. unsigned cache_obj_size = kmem_cache_size(cache);
  85. unsigned i;
  86. WARN_ON(cache_obj_size < e_size);
  87. if (cache_obj_size < e_size)
  88. return NULL;
  89. /* e_count too big; would probably fail the allocation below anyways.
  90. * for typical use cases, e_count should be few thousand at most. */
  91. if (e_count > LC_MAX_ACTIVE)
  92. return NULL;
  93. slot = kcalloc(e_count, sizeof(struct hlist_head), GFP_KERNEL);
  94. if (!slot)
  95. goto out_fail;
  96. element = kcalloc(e_count, sizeof(struct lc_element *), GFP_KERNEL);
  97. if (!element)
  98. goto out_fail;
  99. lc = kzalloc(sizeof(*lc), GFP_KERNEL);
  100. if (!lc)
  101. goto out_fail;
  102. INIT_LIST_HEAD(&lc->in_use);
  103. INIT_LIST_HEAD(&lc->lru);
  104. INIT_LIST_HEAD(&lc->free);
  105. INIT_LIST_HEAD(&lc->to_be_changed);
  106. lc->name = name;
  107. lc->element_size = e_size;
  108. lc->element_off = e_off;
  109. lc->nr_elements = e_count;
  110. lc->max_pending_changes = max_pending_changes;
  111. lc->lc_cache = cache;
  112. lc->lc_element = element;
  113. lc->lc_slot = slot;
  114. /* preallocate all objects */
  115. for (i = 0; i < e_count; i++) {
  116. void *p = kmem_cache_alloc(cache, GFP_KERNEL);
  117. if (!p)
  118. break;
  119. memset(p, 0, lc->element_size);
  120. e = p + e_off;
  121. e->lc_index = i;
  122. e->lc_number = LC_FREE;
  123. e->lc_new_number = LC_FREE;
  124. list_add(&e->list, &lc->free);
  125. element[i] = e;
  126. }
  127. if (i == e_count)
  128. return lc;
  129. /* else: could not allocate all elements, give up */
  130. while (i) {
  131. void *p = element[--i];
  132. kmem_cache_free(cache, p - e_off);
  133. }
  134. kfree(lc);
  135. out_fail:
  136. kfree(element);
  137. kfree(slot);
  138. return NULL;
  139. }
  140. static void lc_free_by_index(struct lru_cache *lc, unsigned i)
  141. {
  142. void *p = lc->lc_element[i];
  143. WARN_ON(!p);
  144. if (p) {
  145. p -= lc->element_off;
  146. kmem_cache_free(lc->lc_cache, p);
  147. }
  148. }
  149. /**
  150. * lc_destroy - frees memory allocated by lc_create()
  151. * @lc: the lru cache to destroy
  152. */
  153. void lc_destroy(struct lru_cache *lc)
  154. {
  155. unsigned i;
  156. if (!lc)
  157. return;
  158. for (i = 0; i < lc->nr_elements; i++)
  159. lc_free_by_index(lc, i);
  160. kfree(lc->lc_element);
  161. kfree(lc->lc_slot);
  162. kfree(lc);
  163. }
  164. /**
  165. * lc_reset - does a full reset for @lc and the hash table slots.
  166. * @lc: the lru cache to operate on
  167. *
  168. * It is roughly the equivalent of re-allocating a fresh lru_cache object,
  169. * basically a short cut to lc_destroy(lc); lc = lc_create(...);
  170. */
  171. void lc_reset(struct lru_cache *lc)
  172. {
  173. unsigned i;
  174. INIT_LIST_HEAD(&lc->in_use);
  175. INIT_LIST_HEAD(&lc->lru);
  176. INIT_LIST_HEAD(&lc->free);
  177. INIT_LIST_HEAD(&lc->to_be_changed);
  178. lc->used = 0;
  179. lc->hits = 0;
  180. lc->misses = 0;
  181. lc->starving = 0;
  182. lc->locked = 0;
  183. lc->changed = 0;
  184. lc->pending_changes = 0;
  185. lc->flags = 0;
  186. memset(lc->lc_slot, 0, sizeof(struct hlist_head) * lc->nr_elements);
  187. for (i = 0; i < lc->nr_elements; i++) {
  188. struct lc_element *e = lc->lc_element[i];
  189. void *p = e;
  190. p -= lc->element_off;
  191. memset(p, 0, lc->element_size);
  192. /* re-init it */
  193. e->lc_index = i;
  194. e->lc_number = LC_FREE;
  195. e->lc_new_number = LC_FREE;
  196. list_add(&e->list, &lc->free);
  197. }
  198. }
  199. /**
  200. * lc_seq_printf_stats - print stats about @lc into @seq
  201. * @seq: the seq_file to print into
  202. * @lc: the lru cache to print statistics of
  203. */
  204. void lc_seq_printf_stats(struct seq_file *seq, struct lru_cache *lc)
  205. {
  206. /* NOTE:
  207. * total calls to lc_get are
  208. * (starving + hits + misses)
  209. * misses include "locked" count (update from an other thread in
  210. * progress) and "changed", when this in fact lead to an successful
  211. * update of the cache.
  212. */
  213. seq_printf(seq, "\t%s: used:%u/%u hits:%lu misses:%lu starving:%lu locked:%lu changed:%lu\n",
  214. lc->name, lc->used, lc->nr_elements,
  215. lc->hits, lc->misses, lc->starving, lc->locked, lc->changed);
  216. }
  217. static struct hlist_head *lc_hash_slot(struct lru_cache *lc, unsigned int enr)
  218. {
  219. return lc->lc_slot + (enr % lc->nr_elements);
  220. }
  221. static struct lc_element *__lc_find(struct lru_cache *lc, unsigned int enr,
  222. bool include_changing)
  223. {
  224. struct lc_element *e;
  225. BUG_ON(!lc);
  226. BUG_ON(!lc->nr_elements);
  227. hlist_for_each_entry(e, lc_hash_slot(lc, enr), colision) {
  228. /* "about to be changed" elements, pending transaction commit,
  229. * are hashed by their "new number". "Normal" elements have
  230. * lc_number == lc_new_number. */
  231. if (e->lc_new_number != enr)
  232. continue;
  233. if (e->lc_new_number == e->lc_number || include_changing)
  234. return e;
  235. break;
  236. }
  237. return NULL;
  238. }
  239. /**
  240. * lc_find - find element by label, if present in the hash table
  241. * @lc: The lru_cache object
  242. * @enr: element number
  243. *
  244. * Returns the pointer to an element, if the element with the requested
  245. * "label" or element number is present in the hash table,
  246. * or NULL if not found. Does not change the refcnt.
  247. * Ignores elements that are "about to be used", i.e. not yet in the active
  248. * set, but still pending transaction commit.
  249. */
  250. struct lc_element *lc_find(struct lru_cache *lc, unsigned int enr)
  251. {
  252. return __lc_find(lc, enr, 0);
  253. }
  254. /**
  255. * lc_is_used - find element by label
  256. * @lc: The lru_cache object
  257. * @enr: element number
  258. *
  259. * Returns true, if the element with the requested "label" or element number is
  260. * present in the hash table, and is used (refcnt > 0).
  261. * Also finds elements that are not _currently_ used but only "about to be
  262. * used", i.e. on the "to_be_changed" list, pending transaction commit.
  263. */
  264. bool lc_is_used(struct lru_cache *lc, unsigned int enr)
  265. {
  266. struct lc_element *e = __lc_find(lc, enr, 1);
  267. return e && e->refcnt;
  268. }
  269. /**
  270. * lc_del - removes an element from the cache
  271. * @lc: The lru_cache object
  272. * @e: The element to remove
  273. *
  274. * @e must be unused (refcnt == 0). Moves @e from "lru" to "free" list,
  275. * sets @e->enr to %LC_FREE.
  276. */
  277. void lc_del(struct lru_cache *lc, struct lc_element *e)
  278. {
  279. PARANOIA_ENTRY();
  280. PARANOIA_LC_ELEMENT(lc, e);
  281. BUG_ON(e->refcnt);
  282. e->lc_number = e->lc_new_number = LC_FREE;
  283. hlist_del_init(&e->colision);
  284. list_move(&e->list, &lc->free);
  285. RETURN();
  286. }
  287. static struct lc_element *lc_prepare_for_change(struct lru_cache *lc, unsigned new_number)
  288. {
  289. struct list_head *n;
  290. struct lc_element *e;
  291. if (!list_empty(&lc->free))
  292. n = lc->free.next;
  293. else if (!list_empty(&lc->lru))
  294. n = lc->lru.prev;
  295. else
  296. return NULL;
  297. e = list_entry(n, struct lc_element, list);
  298. PARANOIA_LC_ELEMENT(lc, e);
  299. e->lc_new_number = new_number;
  300. if (!hlist_unhashed(&e->colision))
  301. __hlist_del(&e->colision);
  302. hlist_add_head(&e->colision, lc_hash_slot(lc, new_number));
  303. list_move(&e->list, &lc->to_be_changed);
  304. return e;
  305. }
  306. static int lc_unused_element_available(struct lru_cache *lc)
  307. {
  308. if (!list_empty(&lc->free))
  309. return 1; /* something on the free list */
  310. if (!list_empty(&lc->lru))
  311. return 1; /* something to evict */
  312. return 0;
  313. }
  314. /* used as internal flags to __lc_get */
  315. enum {
  316. LC_GET_MAY_CHANGE = 1,
  317. LC_GET_MAY_USE_UNCOMMITTED = 2,
  318. };
  319. static struct lc_element *__lc_get(struct lru_cache *lc, unsigned int enr, unsigned int flags)
  320. {
  321. struct lc_element *e;
  322. PARANOIA_ENTRY();
  323. if (lc->flags & LC_STARVING) {
  324. ++lc->starving;
  325. RETURN(NULL);
  326. }
  327. e = __lc_find(lc, enr, 1);
  328. /* if lc_new_number != lc_number,
  329. * this enr is currently being pulled in already,
  330. * and will be available once the pending transaction
  331. * has been committed. */
  332. if (e) {
  333. if (e->lc_new_number != e->lc_number) {
  334. /* It has been found above, but on the "to_be_changed"
  335. * list, not yet committed. Don't pull it in twice,
  336. * wait for the transaction, then try again...
  337. */
  338. if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
  339. RETURN(NULL);
  340. /* ... unless the caller is aware of the implications,
  341. * probably preparing a cumulative transaction. */
  342. ++e->refcnt;
  343. ++lc->hits;
  344. RETURN(e);
  345. }
  346. /* else: lc_new_number == lc_number; a real hit. */
  347. ++lc->hits;
  348. if (e->refcnt++ == 0)
  349. lc->used++;
  350. list_move(&e->list, &lc->in_use); /* Not evictable... */
  351. RETURN(e);
  352. }
  353. /* e == NULL */
  354. ++lc->misses;
  355. if (!(flags & LC_GET_MAY_CHANGE))
  356. RETURN(NULL);
  357. /* To avoid races with lc_try_lock(), first, mark us dirty
  358. * (using test_and_set_bit, as it implies memory barriers), ... */
  359. test_and_set_bit(__LC_DIRTY, &lc->flags);
  360. /* ... only then check if it is locked anyways. If lc_unlock clears
  361. * the dirty bit again, that's not a problem, we will come here again.
  362. */
  363. if (test_bit(__LC_LOCKED, &lc->flags)) {
  364. ++lc->locked;
  365. RETURN(NULL);
  366. }
  367. /* In case there is nothing available and we can not kick out
  368. * the LRU element, we have to wait ...
  369. */
  370. if (!lc_unused_element_available(lc)) {
  371. __set_bit(__LC_STARVING, &lc->flags);
  372. RETURN(NULL);
  373. }
  374. /* It was not present in the active set. We are going to recycle an
  375. * unused (or even "free") element, but we won't accumulate more than
  376. * max_pending_changes changes. */
  377. if (lc->pending_changes >= lc->max_pending_changes)
  378. RETURN(NULL);
  379. e = lc_prepare_for_change(lc, enr);
  380. BUG_ON(!e);
  381. clear_bit(__LC_STARVING, &lc->flags);
  382. BUG_ON(++e->refcnt != 1);
  383. lc->used++;
  384. lc->pending_changes++;
  385. RETURN(e);
  386. }
  387. /**
  388. * lc_get - get element by label, maybe change the active set
  389. * @lc: the lru cache to operate on
  390. * @enr: the label to look up
  391. *
  392. * Finds an element in the cache, increases its usage count,
  393. * "touches" and returns it.
  394. *
  395. * In case the requested number is not present, it needs to be added to the
  396. * cache. Therefore it is possible that an other element becomes evicted from
  397. * the cache. In either case, the user is notified so he is able to e.g. keep
  398. * a persistent log of the cache changes, and therefore the objects in use.
  399. *
  400. * Return values:
  401. * NULL
  402. * The cache was marked %LC_STARVING,
  403. * or the requested label was not in the active set
  404. * and a changing transaction is still pending (@lc was marked %LC_DIRTY).
  405. * Or no unused or free element could be recycled (@lc will be marked as
  406. * %LC_STARVING, blocking further lc_get() operations).
  407. *
  408. * pointer to the element with the REQUESTED element number.
  409. * In this case, it can be used right away
  410. *
  411. * pointer to an UNUSED element with some different element number,
  412. * where that different number may also be %LC_FREE.
  413. *
  414. * In this case, the cache is marked %LC_DIRTY,
  415. * so lc_try_lock() will no longer succeed.
  416. * The returned element pointer is moved to the "to_be_changed" list,
  417. * and registered with the new element number on the hash collision chains,
  418. * so it is possible to pick it up from lc_is_used().
  419. * Up to "max_pending_changes" (see lc_create()) can be accumulated.
  420. * The user now should do whatever housekeeping is necessary,
  421. * typically serialize on lc_try_lock_for_transaction(), then call
  422. * lc_committed(lc) and lc_unlock(), to finish the change.
  423. *
  424. * NOTE: The user needs to check the lc_number on EACH use, so he recognizes
  425. * any cache set change.
  426. */
  427. struct lc_element *lc_get(struct lru_cache *lc, unsigned int enr)
  428. {
  429. return __lc_get(lc, enr, LC_GET_MAY_CHANGE);
  430. }
  431. /**
  432. * lc_get_cumulative - like lc_get; also finds to-be-changed elements
  433. * @lc: the lru cache to operate on
  434. * @enr: the label to look up
  435. *
  436. * Unlike lc_get this also returns the element for @enr, if it is belonging to
  437. * a pending transaction, so the return values are like for lc_get(),
  438. * plus:
  439. *
  440. * pointer to an element already on the "to_be_changed" list.
  441. * In this case, the cache was already marked %LC_DIRTY.
  442. *
  443. * Caller needs to make sure that the pending transaction is completed,
  444. * before proceeding to actually use this element.
  445. */
  446. struct lc_element *lc_get_cumulative(struct lru_cache *lc, unsigned int enr)
  447. {
  448. return __lc_get(lc, enr, LC_GET_MAY_CHANGE|LC_GET_MAY_USE_UNCOMMITTED);
  449. }
  450. /**
  451. * lc_try_get - get element by label, if present; do not change the active set
  452. * @lc: the lru cache to operate on
  453. * @enr: the label to look up
  454. *
  455. * Finds an element in the cache, increases its usage count,
  456. * "touches" and returns it.
  457. *
  458. * Return values:
  459. * NULL
  460. * The cache was marked %LC_STARVING,
  461. * or the requested label was not in the active set
  462. *
  463. * pointer to the element with the REQUESTED element number.
  464. * In this case, it can be used right away
  465. */
  466. struct lc_element *lc_try_get(struct lru_cache *lc, unsigned int enr)
  467. {
  468. return __lc_get(lc, enr, 0);
  469. }
  470. /**
  471. * lc_committed - tell @lc that pending changes have been recorded
  472. * @lc: the lru cache to operate on
  473. *
  474. * User is expected to serialize on explicit lc_try_lock_for_transaction()
  475. * before the transaction is started, and later needs to lc_unlock() explicitly
  476. * as well.
  477. */
  478. void lc_committed(struct lru_cache *lc)
  479. {
  480. struct lc_element *e, *tmp;
  481. PARANOIA_ENTRY();
  482. list_for_each_entry_safe(e, tmp, &lc->to_be_changed, list) {
  483. /* count number of changes, not number of transactions */
  484. ++lc->changed;
  485. e->lc_number = e->lc_new_number;
  486. list_move(&e->list, &lc->in_use);
  487. }
  488. lc->pending_changes = 0;
  489. RETURN();
  490. }
  491. /**
  492. * lc_put - give up refcnt of @e
  493. * @lc: the lru cache to operate on
  494. * @e: the element to put
  495. *
  496. * If refcnt reaches zero, the element is moved to the lru list,
  497. * and a %LC_STARVING (if set) is cleared.
  498. * Returns the new (post-decrement) refcnt.
  499. */
  500. unsigned int lc_put(struct lru_cache *lc, struct lc_element *e)
  501. {
  502. PARANOIA_ENTRY();
  503. PARANOIA_LC_ELEMENT(lc, e);
  504. BUG_ON(e->refcnt == 0);
  505. BUG_ON(e->lc_number != e->lc_new_number);
  506. if (--e->refcnt == 0) {
  507. /* move it to the front of LRU. */
  508. list_move(&e->list, &lc->lru);
  509. lc->used--;
  510. clear_bit_unlock(__LC_STARVING, &lc->flags);
  511. }
  512. RETURN(e->refcnt);
  513. }
  514. /**
  515. * lc_element_by_index
  516. * @lc: the lru cache to operate on
  517. * @i: the index of the element to return
  518. */
  519. struct lc_element *lc_element_by_index(struct lru_cache *lc, unsigned i)
  520. {
  521. BUG_ON(i >= lc->nr_elements);
  522. BUG_ON(lc->lc_element[i] == NULL);
  523. BUG_ON(lc->lc_element[i]->lc_index != i);
  524. return lc->lc_element[i];
  525. }
  526. /**
  527. * lc_index_of
  528. * @lc: the lru cache to operate on
  529. * @e: the element to query for its index position in lc->element
  530. */
  531. unsigned int lc_index_of(struct lru_cache *lc, struct lc_element *e)
  532. {
  533. PARANOIA_LC_ELEMENT(lc, e);
  534. return e->lc_index;
  535. }
  536. /**
  537. * lc_set - associate index with label
  538. * @lc: the lru cache to operate on
  539. * @enr: the label to set
  540. * @index: the element index to associate label with.
  541. *
  542. * Used to initialize the active set to some previously recorded state.
  543. */
  544. void lc_set(struct lru_cache *lc, unsigned int enr, int index)
  545. {
  546. struct lc_element *e;
  547. struct list_head *lh;
  548. if (index < 0 || index >= lc->nr_elements)
  549. return;
  550. e = lc_element_by_index(lc, index);
  551. BUG_ON(e->lc_number != e->lc_new_number);
  552. BUG_ON(e->refcnt != 0);
  553. e->lc_number = e->lc_new_number = enr;
  554. hlist_del_init(&e->colision);
  555. if (enr == LC_FREE)
  556. lh = &lc->free;
  557. else {
  558. hlist_add_head(&e->colision, lc_hash_slot(lc, enr));
  559. lh = &lc->lru;
  560. }
  561. list_move(&e->list, lh);
  562. }
  563. /**
  564. * lc_seq_dump_details - Dump a complete LRU cache to seq in textual form.
  565. * @lc: the lru cache to operate on
  566. * @seq: the &struct seq_file pointer to seq_printf into
  567. * @utext: user supplied additional "heading" or other info
  568. * @detail: function pointer the user may provide to dump further details
  569. * of the object the lc_element is embedded in. May be NULL.
  570. * Note: a leading space ' ' and trailing newline '\n' is implied.
  571. */
  572. void lc_seq_dump_details(struct seq_file *seq, struct lru_cache *lc, char *utext,
  573. void (*detail) (struct seq_file *, struct lc_element *))
  574. {
  575. unsigned int nr_elements = lc->nr_elements;
  576. struct lc_element *e;
  577. int i;
  578. seq_printf(seq, "\tnn: lc_number (new nr) refcnt %s\n ", utext);
  579. for (i = 0; i < nr_elements; i++) {
  580. e = lc_element_by_index(lc, i);
  581. if (e->lc_number != e->lc_new_number)
  582. seq_printf(seq, "\t%5d: %6d %8d %6d ",
  583. i, e->lc_number, e->lc_new_number, e->refcnt);
  584. else
  585. seq_printf(seq, "\t%5d: %6d %-8s %6d ",
  586. i, e->lc_number, "-\"-", e->refcnt);
  587. if (detail)
  588. detail(seq, e);
  589. seq_putc(seq, '\n');
  590. }
  591. }
  592. EXPORT_SYMBOL(lc_create);
  593. EXPORT_SYMBOL(lc_reset);
  594. EXPORT_SYMBOL(lc_destroy);
  595. EXPORT_SYMBOL(lc_set);
  596. EXPORT_SYMBOL(lc_del);
  597. EXPORT_SYMBOL(lc_try_get);
  598. EXPORT_SYMBOL(lc_find);
  599. EXPORT_SYMBOL(lc_get);
  600. EXPORT_SYMBOL(lc_put);
  601. EXPORT_SYMBOL(lc_committed);
  602. EXPORT_SYMBOL(lc_element_by_index);
  603. EXPORT_SYMBOL(lc_index_of);
  604. EXPORT_SYMBOL(lc_seq_printf_stats);
  605. EXPORT_SYMBOL(lc_seq_dump_details);
  606. EXPORT_SYMBOL(lc_try_lock);
  607. EXPORT_SYMBOL(lc_is_used);
  608. EXPORT_SYMBOL(lc_get_cumulative);