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