lru_cache.c 19 KB

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