1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include <linux/module.h>
27#include <linux/bitops.h>
28#include <linux/slab.h>
29#include <linux/string.h>
30#include <linux/seq_file.h>
31#include <linux/lru_cache.h>
32
33MODULE_AUTHOR("Philipp Reisner <phil@linbit.com>, "
34 "Lars Ellenberg <lars@linbit.com>");
35MODULE_DESCRIPTION("lru_cache - Track sets of hot objects");
36MODULE_LICENSE("GPL");
37
38
39
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
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
60
61
62
63
64
65
66
67int 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
74 return 0 == val;
75#if 0
76
77
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
90
91
92
93
94
95
96
97
98
99struct 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
115
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
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
161 for (i--; i; i--) {
162 void *p = element[i];
163 kmem_cache_free(cache, p - e_off);
164 }
165 kfree(lc);
166out_fail:
167 kfree(element);
168 kfree(slot);
169 return NULL;
170}
171
172static 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
184
185
186void 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
200
201
202
203
204
205void 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
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
238
239
240
241void lc_seq_printf_stats(struct seq_file *seq, struct lru_cache *lc)
242{
243
244
245
246
247
248
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
255static 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
261static 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
270
271
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
283
284
285
286
287
288
289
290
291
292struct lc_element *lc_find(struct lru_cache *lc, unsigned int enr)
293{
294 return __lc_find(lc, enr, 0);
295}
296
297
298
299
300
301
302
303
304
305
306
307bool 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
315
316
317
318
319
320
321void 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
333static 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
357static int lc_unused_element_available(struct lru_cache *lc)
358{
359 if (!list_empty(&lc->free))
360 return 1;
361 if (!list_empty(&lc->lru))
362 return 1;
363
364 return 0;
365}
366
367
368enum {
369 LC_GET_MAY_CHANGE = 1,
370 LC_GET_MAY_USE_UNCOMMITTED = 2,
371};
372
373static 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
385
386
387
388 if (e) {
389 if (e->lc_new_number != e->lc_number) {
390
391
392
393
394 if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
395 RETURN(NULL);
396
397
398 ++e->refcnt;
399 ++lc->hits;
400 RETURN(e);
401 }
402
403 ++lc->hits;
404 if (e->refcnt++ == 0)
405 lc->used++;
406 list_move(&e->list, &lc->in_use);
407 RETURN(e);
408 }
409
410
411 ++lc->misses;
412 if (!(flags & LC_GET_MAY_CHANGE))
413 RETURN(NULL);
414
415
416
417 test_and_set_bit(__LC_DIRTY, &lc->flags);
418
419
420
421
422 if (test_bit(__LC_LOCKED, &lc->flags)) {
423 ++lc->locked;
424 RETURN(NULL);
425 }
426
427
428
429
430 if (!lc_unused_element_available(lc)) {
431 __set_bit(__LC_STARVING, &lc->flags);
432 RETURN(NULL);
433 }
434
435
436
437
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
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
481
482
483
484
485
486
487
488
489
490
491
492struct 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
499
500
501
502
503
504
505
506
507
508
509
510
511
512struct 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
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533struct lc_element *lc_try_get(struct lru_cache *lc, unsigned int enr)
534{
535 return __lc_get(lc, enr, 0);
536}
537
538
539
540
541
542
543
544
545
546void 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
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
564
565
566
567
568
569
570
571unsigned 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
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
588
589
590
591struct 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
601
602
603
604unsigned 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
612
613
614
615
616
617
618void 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
643
644
645
646
647
648
649
650void 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
672EXPORT_SYMBOL(lc_create);
673EXPORT_SYMBOL(lc_reset);
674EXPORT_SYMBOL(lc_destroy);
675EXPORT_SYMBOL(lc_set);
676EXPORT_SYMBOL(lc_del);
677EXPORT_SYMBOL(lc_try_get);
678EXPORT_SYMBOL(lc_find);
679EXPORT_SYMBOL(lc_get);
680EXPORT_SYMBOL(lc_put);
681EXPORT_SYMBOL(lc_committed);
682EXPORT_SYMBOL(lc_element_by_index);
683EXPORT_SYMBOL(lc_index_of);
684EXPORT_SYMBOL(lc_seq_printf_stats);
685EXPORT_SYMBOL(lc_seq_dump_details);
686EXPORT_SYMBOL(lc_try_lock);
687EXPORT_SYMBOL(lc_is_used);
688EXPORT_SYMBOL(lc_get_cumulative);
689