4 This file is part of DRBD by Philipp Reisner and Lars Ellenberg.
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>.
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)
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.
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.
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>
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");
38 /* this is developers aid only.
39 * it catches concurrent access (lack of locking on the users part) */
40 #define PARANOIA_ENTRY() do { \
42 BUG_ON(!lc->nr_elements); \
43 BUG_ON(test_and_set_bit(__LC_PARANOIA, &lc->flags)); \
46 #define RETURN(x...) do { \
47 clear_bit_unlock(__LC_PARANOIA, &lc->flags); \
48 return x ; } while (0)
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)
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);
67 int lc_try_lock(struct lru_cache
*lc
)
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. */
76 /* Alternative approach, spin in case someone enters or leaves a
77 * PARANOIA_ENTRY()/RETURN() section. */
78 unsigned long old
, new, val
;
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
)));
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
96 * Returns a pointer to a newly initialized struct lru_cache on success,
97 * or NULL on (allocation) failure.
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
)
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
);
110 WARN_ON(cache_obj_size
< e_size
);
111 if (cache_obj_size
< e_size
)
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
)
119 slot
= kcalloc(e_count
, sizeof(struct hlist_head
), GFP_KERNEL
);
122 element
= kzalloc(e_count
* sizeof(struct lc_element
*), GFP_KERNEL
);
126 lc
= kzalloc(sizeof(*lc
), GFP_KERNEL
);
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
);
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
;
144 /* preallocate all objects */
145 for (i
= 0; i
< e_count
; i
++) {
146 void *p
= kmem_cache_alloc(cache
, GFP_KERNEL
);
149 memset(p
, 0, lc
->element_size
);
152 e
->lc_number
= LC_FREE
;
153 e
->lc_new_number
= LC_FREE
;
154 list_add(&e
->list
, &lc
->free
);
160 /* else: could not allocate all elements, give up */
162 void *p
= element
[i
];
163 kmem_cache_free(cache
, p
- e_off
);
172 void lc_free_by_index(struct lru_cache
*lc
, unsigned i
)
174 void *p
= lc
->lc_element
[i
];
177 p
-= lc
->element_off
;
178 kmem_cache_free(lc
->lc_cache
, p
);
183 * lc_destroy - frees memory allocated by lc_create()
184 * @lc: the lru cache to destroy
186 void lc_destroy(struct lru_cache
*lc
)
191 for (i
= 0; i
< lc
->nr_elements
; i
++)
192 lc_free_by_index(lc
, i
);
193 kfree(lc
->lc_element
);
199 * lc_reset - does a full reset for @lc and the hash table slots.
200 * @lc: the lru cache to operate on
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(...);
205 void lc_reset(struct lru_cache
*lc
)
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
);
219 lc
->pending_changes
= 0;
221 memset(lc
->lc_slot
, 0, sizeof(struct hlist_head
) * lc
->nr_elements
);
223 for (i
= 0; i
< lc
->nr_elements
; i
++) {
224 struct lc_element
*e
= lc
->lc_element
[i
];
226 p
-= lc
->element_off
;
227 memset(p
, 0, lc
->element_size
);
230 e
->lc_number
= LC_FREE
;
231 e
->lc_new_number
= LC_FREE
;
232 list_add(&e
->list
, &lc
->free
);
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
241 size_t lc_seq_printf_stats(struct seq_file
*seq
, struct lru_cache
*lc
)
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.
250 return seq_printf(seq
, "\t%s: used:%u/%u "
251 "hits:%lu misses:%lu starving:%lu locked:%lu changed:%lu\n",
252 lc
->name
, lc
->used
, lc
->nr_elements
,
253 lc
->hits
, lc
->misses
, lc
->starving
, lc
->locked
, lc
->changed
);
256 static struct hlist_head
*lc_hash_slot(struct lru_cache
*lc
, unsigned int enr
)
258 return lc
->lc_slot
+ (enr
% lc
->nr_elements
);
262 static struct lc_element
*__lc_find(struct lru_cache
*lc
, unsigned int enr
,
263 bool include_changing
)
265 struct hlist_node
*n
;
266 struct lc_element
*e
;
269 BUG_ON(!lc
->nr_elements
);
270 hlist_for_each_entry(e
, n
, lc_hash_slot(lc
, enr
), colision
) {
271 /* "about to be changed" elements, pending transaction commit,
272 * are hashed by their "new number". "Normal" elements have
273 * lc_number == lc_new_number. */
274 if (e
->lc_new_number
!= enr
)
276 if (e
->lc_new_number
== e
->lc_number
|| include_changing
)
284 * lc_find - find element by label, if present in the hash table
285 * @lc: The lru_cache object
286 * @enr: element number
288 * Returns the pointer to an element, if the element with the requested
289 * "label" or element number is present in the hash table,
290 * or NULL if not found. Does not change the refcnt.
291 * Ignores elements that are "about to be used", i.e. not yet in the active
292 * set, but still pending transaction commit.
294 struct lc_element
*lc_find(struct lru_cache
*lc
, unsigned int enr
)
296 return __lc_find(lc
, enr
, 0);
300 * lc_is_used - find element by label
301 * @lc: The lru_cache object
302 * @enr: element number
304 * Returns true, if the element with the requested "label" or element number is
305 * present in the hash table, and is used (refcnt > 0).
306 * Also finds elements that are not _currently_ used but only "about to be
307 * used", i.e. on the "to_be_changed" list, pending transaction commit.
309 bool lc_is_used(struct lru_cache
*lc
, unsigned int enr
)
311 struct lc_element
*e
= __lc_find(lc
, enr
, 1);
312 return e
&& e
->refcnt
;
316 * lc_del - removes an element from the cache
317 * @lc: The lru_cache object
318 * @e: The element to remove
320 * @e must be unused (refcnt == 0). Moves @e from "lru" to "free" list,
321 * sets @e->enr to %LC_FREE.
323 void lc_del(struct lru_cache
*lc
, struct lc_element
*e
)
326 PARANOIA_LC_ELEMENT(lc
, e
);
329 e
->lc_number
= e
->lc_new_number
= LC_FREE
;
330 hlist_del_init(&e
->colision
);
331 list_move(&e
->list
, &lc
->free
);
335 static struct lc_element
*lc_prepare_for_change(struct lru_cache
*lc
, unsigned new_number
)
338 struct lc_element
*e
;
340 if (!list_empty(&lc
->free
))
342 else if (!list_empty(&lc
->lru
))
347 e
= list_entry(n
, struct lc_element
, list
);
348 PARANOIA_LC_ELEMENT(lc
, e
);
350 e
->lc_new_number
= new_number
;
351 if (!hlist_unhashed(&e
->colision
))
352 __hlist_del(&e
->colision
);
353 hlist_add_head(&e
->colision
, lc_hash_slot(lc
, new_number
));
354 list_move(&e
->list
, &lc
->to_be_changed
);
359 static int lc_unused_element_available(struct lru_cache
*lc
)
361 if (!list_empty(&lc
->free
))
362 return 1; /* something on the free list */
363 if (!list_empty(&lc
->lru
))
364 return 1; /* something to evict */
369 static struct lc_element
*__lc_get(struct lru_cache
*lc
, unsigned int enr
, bool may_change
)
371 struct lc_element
*e
;
374 if (lc
->flags
& LC_STARVING
) {
379 e
= __lc_find(lc
, enr
, 1);
380 /* if lc_new_number != lc_number,
381 * this enr is currently being pulled in already,
382 * and will be available once the pending transaction
383 * has been committed. */
384 if (e
&& e
->lc_new_number
== e
->lc_number
) {
386 if (e
->refcnt
++ == 0)
388 list_move(&e
->list
, &lc
->in_use
); /* Not evictable... */
396 /* It has been found above, but on the "to_be_changed" list, not yet
397 * committed. Don't pull it in twice, wait for the transaction, then
402 /* To avoid races with lc_try_lock(), first, mark us dirty
403 * (using test_and_set_bit, as it implies memory barriers), ... */
404 test_and_set_bit(__LC_DIRTY
, &lc
->flags
);
406 /* ... only then check if it is locked anyways. If lc_unlock clears
407 * the dirty bit again, that's not a problem, we will come here again.
409 if (test_bit(__LC_LOCKED
, &lc
->flags
)) {
414 /* In case there is nothing available and we can not kick out
415 * the LRU element, we have to wait ...
417 if (!lc_unused_element_available(lc
)) {
418 __set_bit(__LC_STARVING
, &lc
->flags
);
422 /* It was not present in the active set. We are going to recycle an
423 * unused (or even "free") element, but we won't accumulate more than
424 * max_pending_changes changes. */
425 if (lc
->pending_changes
>= lc
->max_pending_changes
)
428 e
= lc_prepare_for_change(lc
, enr
);
431 clear_bit(__LC_STARVING
, &lc
->flags
);
432 BUG_ON(++e
->refcnt
!= 1);
434 lc
->pending_changes
++;
440 * lc_get - get element by label, maybe change the active set
441 * @lc: the lru cache to operate on
442 * @enr: the label to look up
444 * Finds an element in the cache, increases its usage count,
445 * "touches" and returns it.
447 * In case the requested number is not present, it needs to be added to the
448 * cache. Therefore it is possible that an other element becomes evicted from
449 * the cache. In either case, the user is notified so he is able to e.g. keep
450 * a persistent log of the cache changes, and therefore the objects in use.
454 * The cache was marked %LC_STARVING,
455 * or the requested label was not in the active set
456 * and a changing transaction is still pending (@lc was marked %LC_DIRTY).
457 * Or no unused or free element could be recycled (@lc will be marked as
458 * %LC_STARVING, blocking further lc_get() operations).
460 * pointer to the element with the REQUESTED element number.
461 * In this case, it can be used right away
463 * pointer to an UNUSED element with some different element number,
464 * where that different number may also be %LC_FREE.
466 * In this case, the cache is marked %LC_DIRTY,
467 * so lc_try_lock() will no longer succeed.
468 * The returned element pointer is moved to the "to_be_changed" list,
469 * and registered with the new element number on the hash collision chains,
470 * so it is possible to pick it up from lc_is_used().
471 * Up to "max_pending_changes" (see lc_create()) can be accumulated.
472 * The user now should do whatever housekeeping is necessary,
473 * typically serialize on lc_try_lock_for_transaction(), then call
474 * lc_committed(lc) and lc_unlock(), to finish the change.
476 * NOTE: The user needs to check the lc_number on EACH use, so he recognizes
477 * any cache set change.
479 struct lc_element
*lc_get(struct lru_cache
*lc
, unsigned int enr
)
481 return __lc_get(lc
, enr
, 1);
485 * lc_try_get - get element by label, if present; do not change the active set
486 * @lc: the lru cache to operate on
487 * @enr: the label to look up
489 * Finds an element in the cache, increases its usage count,
490 * "touches" and returns it.
494 * The cache was marked %LC_STARVING,
495 * or the requested label was not in the active set
497 * pointer to the element with the REQUESTED element number.
498 * In this case, it can be used right away
500 struct lc_element
*lc_try_get(struct lru_cache
*lc
, unsigned int enr
)
502 return __lc_get(lc
, enr
, 0);
506 * lc_committed - tell @lc that pending changes have been recorded
507 * @lc: the lru cache to operate on
509 * User is expected to serialize on explicit lc_try_lock_for_transaction()
510 * before the transaction is started, and later needs to lc_unlock() explicitly
513 void lc_committed(struct lru_cache
*lc
)
515 struct lc_element
*e
, *tmp
;
518 list_for_each_entry_safe(e
, tmp
, &lc
->to_be_changed
, list
) {
519 /* count number of changes, not number of transactions */
521 e
->lc_number
= e
->lc_new_number
;
522 list_move(&e
->list
, &lc
->in_use
);
524 lc
->pending_changes
= 0;
530 * lc_put - give up refcnt of @e
531 * @lc: the lru cache to operate on
532 * @e: the element to put
534 * If refcnt reaches zero, the element is moved to the lru list,
535 * and a %LC_STARVING (if set) is cleared.
536 * Returns the new (post-decrement) refcnt.
538 unsigned int lc_put(struct lru_cache
*lc
, struct lc_element
*e
)
541 PARANOIA_LC_ELEMENT(lc
, e
);
542 BUG_ON(e
->refcnt
== 0);
543 BUG_ON(e
->lc_number
!= e
->lc_new_number
);
544 if (--e
->refcnt
== 0) {
545 /* move it to the front of LRU. */
546 list_move(&e
->list
, &lc
->lru
);
548 clear_bit_unlock(__LC_STARVING
, &lc
->flags
);
554 * lc_element_by_index
555 * @lc: the lru cache to operate on
556 * @i: the index of the element to return
558 struct lc_element
*lc_element_by_index(struct lru_cache
*lc
, unsigned i
)
560 BUG_ON(i
>= lc
->nr_elements
);
561 BUG_ON(lc
->lc_element
[i
] == NULL
);
562 BUG_ON(lc
->lc_element
[i
]->lc_index
!= i
);
563 return lc
->lc_element
[i
];
568 * @lc: the lru cache to operate on
569 * @e: the element to query for its index position in lc->element
571 unsigned int lc_index_of(struct lru_cache
*lc
, struct lc_element
*e
)
573 PARANOIA_LC_ELEMENT(lc
, e
);
578 * lc_set - associate index with label
579 * @lc: the lru cache to operate on
580 * @enr: the label to set
581 * @index: the element index to associate label with.
583 * Used to initialize the active set to some previously recorded state.
585 void lc_set(struct lru_cache
*lc
, unsigned int enr
, int index
)
587 struct lc_element
*e
;
588 struct list_head
*lh
;
590 if (index
< 0 || index
>= lc
->nr_elements
)
593 e
= lc_element_by_index(lc
, index
);
594 BUG_ON(e
->lc_number
!= e
->lc_new_number
);
595 BUG_ON(e
->refcnt
!= 0);
597 e
->lc_number
= e
->lc_new_number
= enr
;
598 hlist_del_init(&e
->colision
);
602 hlist_add_head(&e
->colision
, lc_hash_slot(lc
, enr
));
605 list_move(&e
->list
, lh
);
609 * lc_dump - Dump a complete LRU cache to seq in textual form.
610 * @lc: the lru cache to operate on
611 * @seq: the &struct seq_file pointer to seq_printf into
612 * @utext: user supplied "heading" or other info
613 * @detail: function pointer the user may provide to dump further details
614 * of the object the lc_element is embedded in.
616 void lc_seq_dump_details(struct seq_file
*seq
, struct lru_cache
*lc
, char *utext
,
617 void (*detail
) (struct seq_file
*, struct lc_element
*))
619 unsigned int nr_elements
= lc
->nr_elements
;
620 struct lc_element
*e
;
623 seq_printf(seq
, "\tnn: lc_number refcnt %s\n ", utext
);
624 for (i
= 0; i
< nr_elements
; i
++) {
625 e
= lc_element_by_index(lc
, i
);
626 if (e
->lc_number
== LC_FREE
) {
627 seq_printf(seq
, "\t%2d: FREE\n", i
);
629 seq_printf(seq
, "\t%2d: %4u %4u ", i
,
630 e
->lc_number
, e
->refcnt
);
636 EXPORT_SYMBOL(lc_create
);
637 EXPORT_SYMBOL(lc_reset
);
638 EXPORT_SYMBOL(lc_destroy
);
639 EXPORT_SYMBOL(lc_set
);
640 EXPORT_SYMBOL(lc_del
);
641 EXPORT_SYMBOL(lc_try_get
);
642 EXPORT_SYMBOL(lc_find
);
643 EXPORT_SYMBOL(lc_get
);
644 EXPORT_SYMBOL(lc_put
);
645 EXPORT_SYMBOL(lc_committed
);
646 EXPORT_SYMBOL(lc_element_by_index
);
647 EXPORT_SYMBOL(lc_index_of
);
648 EXPORT_SYMBOL(lc_seq_printf_stats
);
649 EXPORT_SYMBOL(lc_seq_dump_details
);
650 EXPORT_SYMBOL(lc_try_lock
);
651 EXPORT_SYMBOL(lc_is_used
);
This page took 0.044332 seconds and 6 git commands to generate.