1
2
3
4
5
6
7
8
9
10
11
12
13
14#include <linux/module.h>
15#include <linux/bitops.h>
16#include <linux/slab.h>
17#include <linux/string.h>
18#include <linux/seq_file.h>
19#include <linux/lru_cache.h>
20
21MODULE_AUTHOR("Philipp Reisner <phil@linbit.com>, "
22 "Lars Ellenberg <lars@linbit.com>");
23MODULE_DESCRIPTION("lru_cache - Track sets of hot objects");
24MODULE_LICENSE("GPL");
25
26
27
28#define PARANOIA_ENTRY() do { \
29 BUG_ON(!lc); \
30 BUG_ON(!lc->nr_elements); \
31 BUG_ON(test_and_set_bit(__LC_PARANOIA, &lc->flags)); \
32} while (0)
33
34#define RETURN(x...) do { \
35 clear_bit_unlock(__LC_PARANOIA, &lc->flags); \
36 return x ; } while (0)
37
38
39#define PARANOIA_LC_ELEMENT(lc, e) do { \
40 struct lru_cache *lc_ = (lc); \
41 struct lc_element *e_ = (e); \
42 unsigned i = e_->lc_index; \
43 BUG_ON(i >= lc_->nr_elements); \
44 BUG_ON(lc_->lc_element[i] != e_); } while (0)
45
46
47
48
49
50
51
52
53
54
55int lc_try_lock(struct lru_cache *lc)
56{
57 unsigned long val;
58 do {
59 val = cmpxchg(&lc->flags, 0, LC_LOCKED);
60 } while (unlikely (val == LC_PARANOIA));
61
62 return 0 == val;
63#if 0
64
65
66 unsigned long old, new, val;
67 do {
68 old = lc->flags & LC_PARANOIA;
69 new = old | LC_LOCKED;
70 val = cmpxchg(&lc->flags, old, new);
71 } while (unlikely (val == (old ^ LC_PARANOIA)));
72 return old == val;
73#endif
74}
75
76
77
78
79
80
81
82
83
84
85
86
87
88struct lru_cache *lc_create(const char *name, struct kmem_cache *cache,
89 unsigned max_pending_changes,
90 unsigned e_count, size_t e_size, size_t e_off)
91{
92 struct hlist_head *slot = NULL;
93 struct lc_element **element = NULL;
94 struct lru_cache *lc;
95 struct lc_element *e;
96 unsigned cache_obj_size = kmem_cache_size(cache);
97 unsigned i;
98
99 WARN_ON(cache_obj_size < e_size);
100 if (cache_obj_size < e_size)
101 return NULL;
102
103
104
105 if (e_count > LC_MAX_ACTIVE)
106 return NULL;
107
108 slot = kcalloc(e_count, sizeof(struct hlist_head), GFP_KERNEL);
109 if (!slot)
110 goto out_fail;
111 element = kcalloc(e_count, sizeof(struct lc_element *), GFP_KERNEL);
112 if (!element)
113 goto out_fail;
114
115 lc = kzalloc(sizeof(*lc), GFP_KERNEL);
116 if (!lc)
117 goto out_fail;
118
119 INIT_LIST_HEAD(&lc->in_use);
120 INIT_LIST_HEAD(&lc->lru);
121 INIT_LIST_HEAD(&lc->free);
122 INIT_LIST_HEAD(&lc->to_be_changed);
123
124 lc->name = name;
125 lc->element_size = e_size;
126 lc->element_off = e_off;
127 lc->nr_elements = e_count;
128 lc->max_pending_changes = max_pending_changes;
129 lc->lc_cache = cache;
130 lc->lc_element = element;
131 lc->lc_slot = slot;
132
133
134 for (i = 0; i < e_count; i++) {
135 void *p = kmem_cache_alloc(cache, GFP_KERNEL);
136 if (!p)
137 break;
138 memset(p, 0, lc->element_size);
139 e = p + e_off;
140 e->lc_index = i;
141 e->lc_number = LC_FREE;
142 e->lc_new_number = LC_FREE;
143 list_add(&e->list, &lc->free);
144 element[i] = e;
145 }
146 if (i == e_count)
147 return lc;
148
149
150 for (i--; i; i--) {
151 void *p = element[i];
152 kmem_cache_free(cache, p - e_off);
153 }
154 kfree(lc);
155out_fail:
156 kfree(element);
157 kfree(slot);
158 return NULL;
159}
160
161static void lc_free_by_index(struct lru_cache *lc, unsigned i)
162{
163 void *p = lc->lc_element[i];
164 WARN_ON(!p);
165 if (p) {
166 p -= lc->element_off;
167 kmem_cache_free(lc->lc_cache, p);
168 }
169}
170
171
172
173
174
175void lc_destroy(struct lru_cache *lc)
176{
177 unsigned i;
178 if (!lc)
179 return;
180 for (i = 0; i < lc->nr_elements; i++)
181 lc_free_by_index(lc, i);
182 kfree(lc->lc_element);
183 kfree(lc->lc_slot);
184 kfree(lc);
185}
186
187
188
189
190
191
192
193
194void lc_reset(struct lru_cache *lc)
195{
196 unsigned i;
197
198 INIT_LIST_HEAD(&lc->in_use);
199 INIT_LIST_HEAD(&lc->lru);
200 INIT_LIST_HEAD(&lc->free);
201 INIT_LIST_HEAD(&lc->to_be_changed);
202 lc->used = 0;
203 lc->hits = 0;
204 lc->misses = 0;
205 lc->starving = 0;
206 lc->locked = 0;
207 lc->changed = 0;
208 lc->pending_changes = 0;
209 lc->flags = 0;
210 memset(lc->lc_slot, 0, sizeof(struct hlist_head) * lc->nr_elements);
211
212 for (i = 0; i < lc->nr_elements; i++) {
213 struct lc_element *e = lc->lc_element[i];
214 void *p = e;
215 p -= lc->element_off;
216 memset(p, 0, lc->element_size);
217
218 e->lc_index = i;
219 e->lc_number = LC_FREE;
220 e->lc_new_number = LC_FREE;
221 list_add(&e->list, &lc->free);
222 }
223}
224
225
226
227
228
229
230void lc_seq_printf_stats(struct seq_file *seq, struct lru_cache *lc)
231{
232
233
234
235
236
237
238
239 seq_printf(seq, "\t%s: used:%u/%u hits:%lu misses:%lu starving:%lu locked:%lu changed:%lu\n",
240 lc->name, lc->used, lc->nr_elements,
241 lc->hits, lc->misses, lc->starving, lc->locked, lc->changed);
242}
243
244static struct hlist_head *lc_hash_slot(struct lru_cache *lc, unsigned int enr)
245{
246 return lc->lc_slot + (enr % lc->nr_elements);
247}
248
249
250static struct lc_element *__lc_find(struct lru_cache *lc, unsigned int enr,
251 bool include_changing)
252{
253 struct lc_element *e;
254
255 BUG_ON(!lc);
256 BUG_ON(!lc->nr_elements);
257 hlist_for_each_entry(e, lc_hash_slot(lc, enr), colision) {
258
259
260
261 if (e->lc_new_number != enr)
262 continue;
263 if (e->lc_new_number == e->lc_number || include_changing)
264 return e;
265 break;
266 }
267 return NULL;
268}
269
270
271
272
273
274
275
276
277
278
279
280
281struct lc_element *lc_find(struct lru_cache *lc, unsigned int enr)
282{
283 return __lc_find(lc, enr, 0);
284}
285
286
287
288
289
290
291
292
293
294
295
296bool lc_is_used(struct lru_cache *lc, unsigned int enr)
297{
298 struct lc_element *e = __lc_find(lc, enr, 1);
299 return e && e->refcnt;
300}
301
302
303
304
305
306
307
308
309
310void lc_del(struct lru_cache *lc, struct lc_element *e)
311{
312 PARANOIA_ENTRY();
313 PARANOIA_LC_ELEMENT(lc, e);
314 BUG_ON(e->refcnt);
315
316 e->lc_number = e->lc_new_number = LC_FREE;
317 hlist_del_init(&e->colision);
318 list_move(&e->list, &lc->free);
319 RETURN();
320}
321
322static struct lc_element *lc_prepare_for_change(struct lru_cache *lc, unsigned new_number)
323{
324 struct list_head *n;
325 struct lc_element *e;
326
327 if (!list_empty(&lc->free))
328 n = lc->free.next;
329 else if (!list_empty(&lc->lru))
330 n = lc->lru.prev;
331 else
332 return NULL;
333
334 e = list_entry(n, struct lc_element, list);
335 PARANOIA_LC_ELEMENT(lc, e);
336
337 e->lc_new_number = new_number;
338 if (!hlist_unhashed(&e->colision))
339 __hlist_del(&e->colision);
340 hlist_add_head(&e->colision, lc_hash_slot(lc, new_number));
341 list_move(&e->list, &lc->to_be_changed);
342
343 return e;
344}
345
346static int lc_unused_element_available(struct lru_cache *lc)
347{
348 if (!list_empty(&lc->free))
349 return 1;
350 if (!list_empty(&lc->lru))
351 return 1;
352
353 return 0;
354}
355
356
357enum {
358 LC_GET_MAY_CHANGE = 1,
359 LC_GET_MAY_USE_UNCOMMITTED = 2,
360};
361
362static struct lc_element *__lc_get(struct lru_cache *lc, unsigned int enr, unsigned int flags)
363{
364 struct lc_element *e;
365
366 PARANOIA_ENTRY();
367 if (lc->flags & LC_STARVING) {
368 ++lc->starving;
369 RETURN(NULL);
370 }
371
372 e = __lc_find(lc, enr, 1);
373
374
375
376
377 if (e) {
378 if (e->lc_new_number != e->lc_number) {
379
380
381
382
383 if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
384 RETURN(NULL);
385
386
387 ++e->refcnt;
388 ++lc->hits;
389 RETURN(e);
390 }
391
392 ++lc->hits;
393 if (e->refcnt++ == 0)
394 lc->used++;
395 list_move(&e->list, &lc->in_use);
396 RETURN(e);
397 }
398
399
400 ++lc->misses;
401 if (!(flags & LC_GET_MAY_CHANGE))
402 RETURN(NULL);
403
404
405
406 test_and_set_bit(__LC_DIRTY, &lc->flags);
407
408
409
410
411 if (test_bit(__LC_LOCKED, &lc->flags)) {
412 ++lc->locked;
413 RETURN(NULL);
414 }
415
416
417
418
419 if (!lc_unused_element_available(lc)) {
420 __set_bit(__LC_STARVING, &lc->flags);
421 RETURN(NULL);
422 }
423
424
425
426
427 if (lc->pending_changes >= lc->max_pending_changes)
428 RETURN(NULL);
429
430 e = lc_prepare_for_change(lc, enr);
431 BUG_ON(!e);
432
433 clear_bit(__LC_STARVING, &lc->flags);
434 BUG_ON(++e->refcnt != 1);
435 lc->used++;
436 lc->pending_changes++;
437
438 RETURN(e);
439}
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481struct lc_element *lc_get(struct lru_cache *lc, unsigned int enr)
482{
483 return __lc_get(lc, enr, LC_GET_MAY_CHANGE);
484}
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501struct lc_element *lc_get_cumulative(struct lru_cache *lc, unsigned int enr)
502{
503 return __lc_get(lc, enr, LC_GET_MAY_CHANGE|LC_GET_MAY_USE_UNCOMMITTED);
504}
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522struct lc_element *lc_try_get(struct lru_cache *lc, unsigned int enr)
523{
524 return __lc_get(lc, enr, 0);
525}
526
527
528
529
530
531
532
533
534
535void lc_committed(struct lru_cache *lc)
536{
537 struct lc_element *e, *tmp;
538
539 PARANOIA_ENTRY();
540 list_for_each_entry_safe(e, tmp, &lc->to_be_changed, list) {
541
542 ++lc->changed;
543 e->lc_number = e->lc_new_number;
544 list_move(&e->list, &lc->in_use);
545 }
546 lc->pending_changes = 0;
547 RETURN();
548}
549
550
551
552
553
554
555
556
557
558
559
560unsigned int lc_put(struct lru_cache *lc, struct lc_element *e)
561{
562 PARANOIA_ENTRY();
563 PARANOIA_LC_ELEMENT(lc, e);
564 BUG_ON(e->refcnt == 0);
565 BUG_ON(e->lc_number != e->lc_new_number);
566 if (--e->refcnt == 0) {
567
568 list_move(&e->list, &lc->lru);
569 lc->used--;
570 clear_bit_unlock(__LC_STARVING, &lc->flags);
571 }
572 RETURN(e->refcnt);
573}
574
575
576
577
578
579
580struct lc_element *lc_element_by_index(struct lru_cache *lc, unsigned i)
581{
582 BUG_ON(i >= lc->nr_elements);
583 BUG_ON(lc->lc_element[i] == NULL);
584 BUG_ON(lc->lc_element[i]->lc_index != i);
585 return lc->lc_element[i];
586}
587
588
589
590
591
592
593unsigned int lc_index_of(struct lru_cache *lc, struct lc_element *e)
594{
595 PARANOIA_LC_ELEMENT(lc, e);
596 return e->lc_index;
597}
598
599
600
601
602
603
604
605
606
607void lc_set(struct lru_cache *lc, unsigned int enr, int index)
608{
609 struct lc_element *e;
610 struct list_head *lh;
611
612 if (index < 0 || index >= lc->nr_elements)
613 return;
614
615 e = lc_element_by_index(lc, index);
616 BUG_ON(e->lc_number != e->lc_new_number);
617 BUG_ON(e->refcnt != 0);
618
619 e->lc_number = e->lc_new_number = enr;
620 hlist_del_init(&e->colision);
621 if (enr == LC_FREE)
622 lh = &lc->free;
623 else {
624 hlist_add_head(&e->colision, lc_hash_slot(lc, enr));
625 lh = &lc->lru;
626 }
627 list_move(&e->list, lh);
628}
629
630
631
632
633
634
635
636
637
638
639void lc_seq_dump_details(struct seq_file *seq, struct lru_cache *lc, char *utext,
640 void (*detail) (struct seq_file *, struct lc_element *))
641{
642 unsigned int nr_elements = lc->nr_elements;
643 struct lc_element *e;
644 int i;
645
646 seq_printf(seq, "\tnn: lc_number (new nr) refcnt %s\n ", utext);
647 for (i = 0; i < nr_elements; i++) {
648 e = lc_element_by_index(lc, i);
649 if (e->lc_number != e->lc_new_number)
650 seq_printf(seq, "\t%5d: %6d %8d %6d ",
651 i, e->lc_number, e->lc_new_number, e->refcnt);
652 else
653 seq_printf(seq, "\t%5d: %6d %-8s %6d ",
654 i, e->lc_number, "-\"-", e->refcnt);
655 if (detail)
656 detail(seq, e);
657 seq_putc(seq, '\n');
658 }
659}
660
661EXPORT_SYMBOL(lc_create);
662EXPORT_SYMBOL(lc_reset);
663EXPORT_SYMBOL(lc_destroy);
664EXPORT_SYMBOL(lc_set);
665EXPORT_SYMBOL(lc_del);
666EXPORT_SYMBOL(lc_try_get);
667EXPORT_SYMBOL(lc_find);
668EXPORT_SYMBOL(lc_get);
669EXPORT_SYMBOL(lc_put);
670EXPORT_SYMBOL(lc_committed);
671EXPORT_SYMBOL(lc_element_by_index);
672EXPORT_SYMBOL(lc_index_of);
673EXPORT_SYMBOL(lc_seq_printf_stats);
674EXPORT_SYMBOL(lc_seq_dump_details);
675EXPORT_SYMBOL(lc_try_lock);
676EXPORT_SYMBOL(lc_is_used);
677EXPORT_SYMBOL(lc_get_cumulative);
678