123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677 |
- #include <linux/module.h>
- #include <linux/bitops.h>
- #include <linux/slab.h>
- #include <linux/string.h> /* for memset */
- #include <linux/seq_file.h> /* for seq_printf */
- #include <linux/lru_cache.h>
- MODULE_AUTHOR("Philipp Reisner <phil@linbit.com>, "
- "Lars Ellenberg <lars@linbit.com>");
- MODULE_DESCRIPTION("lru_cache - Track sets of hot objects");
- MODULE_LICENSE("GPL");
- #define PARANOIA_ENTRY() do { \
- BUG_ON(!lc); \
- BUG_ON(!lc->nr_elements); \
- BUG_ON(test_and_set_bit(__LC_PARANOIA, &lc->flags)); \
- } while (0)
- #define RETURN(x...) do { \
- clear_bit_unlock(__LC_PARANOIA, &lc->flags); \
- return x ; } while (0)
- #define PARANOIA_LC_ELEMENT(lc, e) do { \
- struct lru_cache *lc_ = (lc); \
- struct lc_element *e_ = (e); \
- unsigned i = e_->lc_index; \
- BUG_ON(i >= lc_->nr_elements); \
- BUG_ON(lc_->lc_element[i] != e_); } while (0)
- int lc_try_lock(struct lru_cache *lc)
- {
- unsigned long val;
- do {
- val = cmpxchg(&lc->flags, 0, LC_LOCKED);
- } while (unlikely (val == LC_PARANOIA));
-
- return 0 == val;
- #if 0
-
- unsigned long old, new, val;
- do {
- old = lc->flags & LC_PARANOIA;
- new = old | LC_LOCKED;
- val = cmpxchg(&lc->flags, old, new);
- } while (unlikely (val == (old ^ LC_PARANOIA)));
- return old == val;
- #endif
- }
- struct lru_cache *lc_create(const char *name, struct kmem_cache *cache,
- unsigned max_pending_changes,
- unsigned e_count, size_t e_size, size_t e_off)
- {
- struct hlist_head *slot = NULL;
- struct lc_element **element = NULL;
- struct lru_cache *lc;
- struct lc_element *e;
- unsigned cache_obj_size = kmem_cache_size(cache);
- unsigned i;
- WARN_ON(cache_obj_size < e_size);
- if (cache_obj_size < e_size)
- return NULL;
-
- if (e_count > LC_MAX_ACTIVE)
- return NULL;
- slot = kcalloc(e_count, sizeof(struct hlist_head), GFP_KERNEL);
- if (!slot)
- goto out_fail;
- element = kcalloc(e_count, sizeof(struct lc_element *), GFP_KERNEL);
- if (!element)
- goto out_fail;
- lc = kzalloc(sizeof(*lc), GFP_KERNEL);
- if (!lc)
- goto out_fail;
- INIT_LIST_HEAD(&lc->in_use);
- INIT_LIST_HEAD(&lc->lru);
- INIT_LIST_HEAD(&lc->free);
- INIT_LIST_HEAD(&lc->to_be_changed);
- lc->name = name;
- lc->element_size = e_size;
- lc->element_off = e_off;
- lc->nr_elements = e_count;
- lc->max_pending_changes = max_pending_changes;
- lc->lc_cache = cache;
- lc->lc_element = element;
- lc->lc_slot = slot;
-
- for (i = 0; i < e_count; i++) {
- void *p = kmem_cache_alloc(cache, GFP_KERNEL);
- if (!p)
- break;
- memset(p, 0, lc->element_size);
- e = p + e_off;
- e->lc_index = i;
- e->lc_number = LC_FREE;
- e->lc_new_number = LC_FREE;
- list_add(&e->list, &lc->free);
- element[i] = e;
- }
- if (i == e_count)
- return lc;
-
- while (i) {
- void *p = element[--i];
- kmem_cache_free(cache, p - e_off);
- }
- kfree(lc);
- out_fail:
- kfree(element);
- kfree(slot);
- return NULL;
- }
- static void lc_free_by_index(struct lru_cache *lc, unsigned i)
- {
- void *p = lc->lc_element[i];
- WARN_ON(!p);
- if (p) {
- p -= lc->element_off;
- kmem_cache_free(lc->lc_cache, p);
- }
- }
- void lc_destroy(struct lru_cache *lc)
- {
- unsigned i;
- if (!lc)
- return;
- for (i = 0; i < lc->nr_elements; i++)
- lc_free_by_index(lc, i);
- kfree(lc->lc_element);
- kfree(lc->lc_slot);
- kfree(lc);
- }
- void lc_reset(struct lru_cache *lc)
- {
- unsigned i;
- INIT_LIST_HEAD(&lc->in_use);
- INIT_LIST_HEAD(&lc->lru);
- INIT_LIST_HEAD(&lc->free);
- INIT_LIST_HEAD(&lc->to_be_changed);
- lc->used = 0;
- lc->hits = 0;
- lc->misses = 0;
- lc->starving = 0;
- lc->locked = 0;
- lc->changed = 0;
- lc->pending_changes = 0;
- lc->flags = 0;
- memset(lc->lc_slot, 0, sizeof(struct hlist_head) * lc->nr_elements);
- for (i = 0; i < lc->nr_elements; i++) {
- struct lc_element *e = lc->lc_element[i];
- void *p = e;
- p -= lc->element_off;
- memset(p, 0, lc->element_size);
-
- e->lc_index = i;
- e->lc_number = LC_FREE;
- e->lc_new_number = LC_FREE;
- list_add(&e->list, &lc->free);
- }
- }
- void lc_seq_printf_stats(struct seq_file *seq, struct lru_cache *lc)
- {
-
- seq_printf(seq, "\t%s: used:%u/%u hits:%lu misses:%lu starving:%lu locked:%lu changed:%lu\n",
- lc->name, lc->used, lc->nr_elements,
- lc->hits, lc->misses, lc->starving, lc->locked, lc->changed);
- }
- static struct hlist_head *lc_hash_slot(struct lru_cache *lc, unsigned int enr)
- {
- return lc->lc_slot + (enr % lc->nr_elements);
- }
- static struct lc_element *__lc_find(struct lru_cache *lc, unsigned int enr,
- bool include_changing)
- {
- struct lc_element *e;
- BUG_ON(!lc);
- BUG_ON(!lc->nr_elements);
- hlist_for_each_entry(e, lc_hash_slot(lc, enr), colision) {
-
- if (e->lc_new_number != enr)
- continue;
- if (e->lc_new_number == e->lc_number || include_changing)
- return e;
- break;
- }
- return NULL;
- }
- struct lc_element *lc_find(struct lru_cache *lc, unsigned int enr)
- {
- return __lc_find(lc, enr, 0);
- }
- bool lc_is_used(struct lru_cache *lc, unsigned int enr)
- {
- struct lc_element *e = __lc_find(lc, enr, 1);
- return e && e->refcnt;
- }
- void lc_del(struct lru_cache *lc, struct lc_element *e)
- {
- PARANOIA_ENTRY();
- PARANOIA_LC_ELEMENT(lc, e);
- BUG_ON(e->refcnt);
- e->lc_number = e->lc_new_number = LC_FREE;
- hlist_del_init(&e->colision);
- list_move(&e->list, &lc->free);
- RETURN();
- }
- static struct lc_element *lc_prepare_for_change(struct lru_cache *lc, unsigned new_number)
- {
- struct list_head *n;
- struct lc_element *e;
- if (!list_empty(&lc->free))
- n = lc->free.next;
- else if (!list_empty(&lc->lru))
- n = lc->lru.prev;
- else
- return NULL;
- e = list_entry(n, struct lc_element, list);
- PARANOIA_LC_ELEMENT(lc, e);
- e->lc_new_number = new_number;
- if (!hlist_unhashed(&e->colision))
- __hlist_del(&e->colision);
- hlist_add_head(&e->colision, lc_hash_slot(lc, new_number));
- list_move(&e->list, &lc->to_be_changed);
- return e;
- }
- static int lc_unused_element_available(struct lru_cache *lc)
- {
- if (!list_empty(&lc->free))
- return 1;
- if (!list_empty(&lc->lru))
- return 1;
- return 0;
- }
- enum {
- LC_GET_MAY_CHANGE = 1,
- LC_GET_MAY_USE_UNCOMMITTED = 2,
- };
- static struct lc_element *__lc_get(struct lru_cache *lc, unsigned int enr, unsigned int flags)
- {
- struct lc_element *e;
- PARANOIA_ENTRY();
- if (lc->flags & LC_STARVING) {
- ++lc->starving;
- RETURN(NULL);
- }
- e = __lc_find(lc, enr, 1);
-
- if (e) {
- if (e->lc_new_number != e->lc_number) {
-
- if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
- RETURN(NULL);
-
- ++e->refcnt;
- ++lc->hits;
- RETURN(e);
- }
-
- ++lc->hits;
- if (e->refcnt++ == 0)
- lc->used++;
- list_move(&e->list, &lc->in_use);
- RETURN(e);
- }
-
- ++lc->misses;
- if (!(flags & LC_GET_MAY_CHANGE))
- RETURN(NULL);
-
- test_and_set_bit(__LC_DIRTY, &lc->flags);
-
- if (test_bit(__LC_LOCKED, &lc->flags)) {
- ++lc->locked;
- RETURN(NULL);
- }
-
- if (!lc_unused_element_available(lc)) {
- __set_bit(__LC_STARVING, &lc->flags);
- RETURN(NULL);
- }
-
- if (lc->pending_changes >= lc->max_pending_changes)
- RETURN(NULL);
- e = lc_prepare_for_change(lc, enr);
- BUG_ON(!e);
- clear_bit(__LC_STARVING, &lc->flags);
- BUG_ON(++e->refcnt != 1);
- lc->used++;
- lc->pending_changes++;
- RETURN(e);
- }
- struct lc_element *lc_get(struct lru_cache *lc, unsigned int enr)
- {
- return __lc_get(lc, enr, LC_GET_MAY_CHANGE);
- }
- struct lc_element *lc_get_cumulative(struct lru_cache *lc, unsigned int enr)
- {
- return __lc_get(lc, enr, LC_GET_MAY_CHANGE|LC_GET_MAY_USE_UNCOMMITTED);
- }
- struct lc_element *lc_try_get(struct lru_cache *lc, unsigned int enr)
- {
- return __lc_get(lc, enr, 0);
- }
- void lc_committed(struct lru_cache *lc)
- {
- struct lc_element *e, *tmp;
- PARANOIA_ENTRY();
- list_for_each_entry_safe(e, tmp, &lc->to_be_changed, list) {
-
- ++lc->changed;
- e->lc_number = e->lc_new_number;
- list_move(&e->list, &lc->in_use);
- }
- lc->pending_changes = 0;
- RETURN();
- }
- unsigned int lc_put(struct lru_cache *lc, struct lc_element *e)
- {
- PARANOIA_ENTRY();
- PARANOIA_LC_ELEMENT(lc, e);
- BUG_ON(e->refcnt == 0);
- BUG_ON(e->lc_number != e->lc_new_number);
- if (--e->refcnt == 0) {
-
- list_move(&e->list, &lc->lru);
- lc->used--;
- clear_bit_unlock(__LC_STARVING, &lc->flags);
- }
- RETURN(e->refcnt);
- }
- struct lc_element *lc_element_by_index(struct lru_cache *lc, unsigned i)
- {
- BUG_ON(i >= lc->nr_elements);
- BUG_ON(lc->lc_element[i] == NULL);
- BUG_ON(lc->lc_element[i]->lc_index != i);
- return lc->lc_element[i];
- }
- unsigned int lc_index_of(struct lru_cache *lc, struct lc_element *e)
- {
- PARANOIA_LC_ELEMENT(lc, e);
- return e->lc_index;
- }
- void lc_set(struct lru_cache *lc, unsigned int enr, int index)
- {
- struct lc_element *e;
- struct list_head *lh;
- if (index < 0 || index >= lc->nr_elements)
- return;
- e = lc_element_by_index(lc, index);
- BUG_ON(e->lc_number != e->lc_new_number);
- BUG_ON(e->refcnt != 0);
- e->lc_number = e->lc_new_number = enr;
- hlist_del_init(&e->colision);
- if (enr == LC_FREE)
- lh = &lc->free;
- else {
- hlist_add_head(&e->colision, lc_hash_slot(lc, enr));
- lh = &lc->lru;
- }
- list_move(&e->list, lh);
- }
- void lc_seq_dump_details(struct seq_file *seq, struct lru_cache *lc, char *utext,
- void (*detail) (struct seq_file *, struct lc_element *))
- {
- unsigned int nr_elements = lc->nr_elements;
- struct lc_element *e;
- int i;
- seq_printf(seq, "\tnn: lc_number (new nr) refcnt %s\n ", utext);
- for (i = 0; i < nr_elements; i++) {
- e = lc_element_by_index(lc, i);
- if (e->lc_number != e->lc_new_number)
- seq_printf(seq, "\t%5d: %6d %8d %6d ",
- i, e->lc_number, e->lc_new_number, e->refcnt);
- else
- seq_printf(seq, "\t%5d: %6d %-8s %6d ",
- i, e->lc_number, "-\"-", e->refcnt);
- if (detail)
- detail(seq, e);
- seq_putc(seq, '\n');
- }
- }
- EXPORT_SYMBOL(lc_create);
- EXPORT_SYMBOL(lc_reset);
- EXPORT_SYMBOL(lc_destroy);
- EXPORT_SYMBOL(lc_set);
- EXPORT_SYMBOL(lc_del);
- EXPORT_SYMBOL(lc_try_get);
- EXPORT_SYMBOL(lc_find);
- EXPORT_SYMBOL(lc_get);
- EXPORT_SYMBOL(lc_put);
- EXPORT_SYMBOL(lc_committed);
- EXPORT_SYMBOL(lc_element_by_index);
- EXPORT_SYMBOL(lc_index_of);
- EXPORT_SYMBOL(lc_seq_printf_stats);
- EXPORT_SYMBOL(lc_seq_dump_details);
- EXPORT_SYMBOL(lc_try_lock);
- EXPORT_SYMBOL(lc_is_used);
- EXPORT_SYMBOL(lc_get_cumulative);
|