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
27
28
29#include <linux/kernel.h>
30#include <linux/module.h>
31
32#include <linux/hash.h>
33#include <linux/fs.h>
34#include <linux/mm.h>
35#include <linux/slab.h>
36#include <linux/sched.h>
37#include <linux/init.h>
38#include <linux/mbcache.h>
39
40
41#ifdef MB_CACHE_DEBUG
42# define mb_debug(f...) do { \
43 printk(KERN_DEBUG f); \
44 printk("\n"); \
45 } while (0)
46#define mb_assert(c) do { if (!(c)) \
47 printk(KERN_ERR "assertion " #c " failed\n"); \
48 } while(0)
49#else
50# define mb_debug(f...) do { } while(0)
51# define mb_assert(c) do { } while(0)
52#endif
53#define mb_error(f...) do { \
54 printk(KERN_ERR f); \
55 printk("\n"); \
56 } while(0)
57
58#define MB_CACHE_WRITER ((unsigned short)~0U >> 1)
59
60static DECLARE_WAIT_QUEUE_HEAD(mb_cache_queue);
61
62MODULE_AUTHOR("Andreas Gruenbacher <a.gruenbacher@computer.org>");
63MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
64MODULE_LICENSE("GPL");
65
66EXPORT_SYMBOL(mb_cache_create);
67EXPORT_SYMBOL(mb_cache_shrink);
68EXPORT_SYMBOL(mb_cache_destroy);
69EXPORT_SYMBOL(mb_cache_entry_alloc);
70EXPORT_SYMBOL(mb_cache_entry_insert);
71EXPORT_SYMBOL(mb_cache_entry_release);
72EXPORT_SYMBOL(mb_cache_entry_free);
73EXPORT_SYMBOL(mb_cache_entry_get);
74#if !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0)
75EXPORT_SYMBOL(mb_cache_entry_find_first);
76EXPORT_SYMBOL(mb_cache_entry_find_next);
77#endif
78
79
80
81
82
83
84
85static LIST_HEAD(mb_cache_list);
86static LIST_HEAD(mb_cache_lru_list);
87static DEFINE_SPINLOCK(mb_cache_spinlock);
88
89
90
91
92
93static int mb_cache_shrink_fn(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask);
94
95static struct shrinker mb_cache_shrinker = {
96 .shrink = mb_cache_shrink_fn,
97 .seeks = DEFAULT_SEEKS,
98};
99
100static inline int
101__mb_cache_entry_is_hashed(struct mb_cache_entry *ce)
102{
103 return !list_empty(&ce->e_block_list);
104}
105
106
107static void
108__mb_cache_entry_unhash(struct mb_cache_entry *ce)
109{
110 if (__mb_cache_entry_is_hashed(ce)) {
111 list_del_init(&ce->e_block_list);
112 list_del(&ce->e_index.o_list);
113 }
114}
115
116
117static void
118__mb_cache_entry_forget(struct mb_cache_entry *ce, gfp_t gfp_mask)
119{
120 struct mb_cache *cache = ce->e_cache;
121
122 mb_assert(!(ce->e_used || ce->e_queued));
123 kmem_cache_free(cache->c_entry_cache, ce);
124 atomic_dec(&cache->c_entry_count);
125}
126
127
128static void
129__mb_cache_entry_release_unlock(struct mb_cache_entry *ce)
130 __releases(mb_cache_spinlock)
131{
132
133 if (ce->e_queued)
134 wake_up_all(&mb_cache_queue);
135 if (ce->e_used >= MB_CACHE_WRITER)
136 ce->e_used -= MB_CACHE_WRITER;
137 ce->e_used--;
138 if (!(ce->e_used || ce->e_queued)) {
139 if (!__mb_cache_entry_is_hashed(ce))
140 goto forget;
141 mb_assert(list_empty(&ce->e_lru_list));
142 list_add_tail(&ce->e_lru_list, &mb_cache_lru_list);
143 }
144 spin_unlock(&mb_cache_spinlock);
145 return;
146forget:
147 spin_unlock(&mb_cache_spinlock);
148 __mb_cache_entry_forget(ce, GFP_KERNEL);
149}
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164static int
165mb_cache_shrink_fn(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask)
166{
167 LIST_HEAD(free_list);
168 struct mb_cache *cache;
169 struct mb_cache_entry *entry, *tmp;
170 int count = 0;
171
172 mb_debug("trying to free %d entries", nr_to_scan);
173 spin_lock(&mb_cache_spinlock);
174 while (nr_to_scan-- && !list_empty(&mb_cache_lru_list)) {
175 struct mb_cache_entry *ce =
176 list_entry(mb_cache_lru_list.next,
177 struct mb_cache_entry, e_lru_list);
178 list_move_tail(&ce->e_lru_list, &free_list);
179 __mb_cache_entry_unhash(ce);
180 }
181 list_for_each_entry(cache, &mb_cache_list, c_cache_list) {
182 mb_debug("cache %s (%d)", cache->c_name,
183 atomic_read(&cache->c_entry_count));
184 count += atomic_read(&cache->c_entry_count);
185 }
186 spin_unlock(&mb_cache_spinlock);
187 list_for_each_entry_safe(entry, tmp, &free_list, e_lru_list) {
188 __mb_cache_entry_forget(entry, gfp_mask);
189 }
190 return (count / 100) * sysctl_vfs_cache_pressure;
191}
192
193
194
195
196
197
198
199
200
201
202
203
204
205struct mb_cache *
206mb_cache_create(const char *name, int bucket_bits)
207{
208 int n, bucket_count = 1 << bucket_bits;
209 struct mb_cache *cache = NULL;
210
211 cache = kmalloc(sizeof(struct mb_cache), GFP_KERNEL);
212 if (!cache)
213 return NULL;
214 cache->c_name = name;
215 atomic_set(&cache->c_entry_count, 0);
216 cache->c_bucket_bits = bucket_bits;
217 cache->c_block_hash = kmalloc(bucket_count * sizeof(struct list_head),
218 GFP_KERNEL);
219 if (!cache->c_block_hash)
220 goto fail;
221 for (n=0; n<bucket_count; n++)
222 INIT_LIST_HEAD(&cache->c_block_hash[n]);
223 cache->c_index_hash = kmalloc(bucket_count * sizeof(struct list_head),
224 GFP_KERNEL);
225 if (!cache->c_index_hash)
226 goto fail;
227 for (n=0; n<bucket_count; n++)
228 INIT_LIST_HEAD(&cache->c_index_hash[n]);
229 cache->c_entry_cache = kmem_cache_create(name,
230 sizeof(struct mb_cache_entry), 0,
231 SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL);
232 if (!cache->c_entry_cache)
233 goto fail2;
234
235
236
237
238
239 cache->c_max_entries = bucket_count << 4;
240
241 spin_lock(&mb_cache_spinlock);
242 list_add(&cache->c_cache_list, &mb_cache_list);
243 spin_unlock(&mb_cache_spinlock);
244 return cache;
245
246fail2:
247 kfree(cache->c_index_hash);
248
249fail:
250 kfree(cache->c_block_hash);
251 kfree(cache);
252 return NULL;
253}
254
255
256
257
258
259
260
261
262
263
264
265void
266mb_cache_shrink(struct block_device *bdev)
267{
268 LIST_HEAD(free_list);
269 struct list_head *l, *ltmp;
270
271 spin_lock(&mb_cache_spinlock);
272 list_for_each_safe(l, ltmp, &mb_cache_lru_list) {
273 struct mb_cache_entry *ce =
274 list_entry(l, struct mb_cache_entry, e_lru_list);
275 if (ce->e_bdev == bdev) {
276 list_move_tail(&ce->e_lru_list, &free_list);
277 __mb_cache_entry_unhash(ce);
278 }
279 }
280 spin_unlock(&mb_cache_spinlock);
281 list_for_each_safe(l, ltmp, &free_list) {
282 __mb_cache_entry_forget(list_entry(l, struct mb_cache_entry,
283 e_lru_list), GFP_KERNEL);
284 }
285}
286
287
288
289
290
291
292
293
294
295void
296mb_cache_destroy(struct mb_cache *cache)
297{
298 LIST_HEAD(free_list);
299 struct list_head *l, *ltmp;
300
301 spin_lock(&mb_cache_spinlock);
302 list_for_each_safe(l, ltmp, &mb_cache_lru_list) {
303 struct mb_cache_entry *ce =
304 list_entry(l, struct mb_cache_entry, e_lru_list);
305 if (ce->e_cache == cache) {
306 list_move_tail(&ce->e_lru_list, &free_list);
307 __mb_cache_entry_unhash(ce);
308 }
309 }
310 list_del(&cache->c_cache_list);
311 spin_unlock(&mb_cache_spinlock);
312
313 list_for_each_safe(l, ltmp, &free_list) {
314 __mb_cache_entry_forget(list_entry(l, struct mb_cache_entry,
315 e_lru_list), GFP_KERNEL);
316 }
317
318 if (atomic_read(&cache->c_entry_count) > 0) {
319 mb_error("cache %s: %d orphaned entries",
320 cache->c_name,
321 atomic_read(&cache->c_entry_count));
322 }
323
324 kmem_cache_destroy(cache->c_entry_cache);
325
326 kfree(cache->c_index_hash);
327 kfree(cache->c_block_hash);
328 kfree(cache);
329}
330
331
332
333
334
335
336
337
338
339struct mb_cache_entry *
340mb_cache_entry_alloc(struct mb_cache *cache, gfp_t gfp_flags)
341{
342 struct mb_cache_entry *ce = NULL;
343
344 if (atomic_read(&cache->c_entry_count) >= cache->c_max_entries) {
345 spin_lock(&mb_cache_spinlock);
346 if (!list_empty(&mb_cache_lru_list)) {
347 ce = list_entry(mb_cache_lru_list.next,
348 struct mb_cache_entry, e_lru_list);
349 list_del_init(&ce->e_lru_list);
350 __mb_cache_entry_unhash(ce);
351 }
352 spin_unlock(&mb_cache_spinlock);
353 }
354 if (!ce) {
355 ce = kmem_cache_alloc(cache->c_entry_cache, gfp_flags);
356 if (!ce)
357 return NULL;
358 atomic_inc(&cache->c_entry_count);
359 INIT_LIST_HEAD(&ce->e_lru_list);
360 INIT_LIST_HEAD(&ce->e_block_list);
361 ce->e_cache = cache;
362 ce->e_queued = 0;
363 }
364 ce->e_used = 1 + MB_CACHE_WRITER;
365 return ce;
366}
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383int
384mb_cache_entry_insert(struct mb_cache_entry *ce, struct block_device *bdev,
385 sector_t block, unsigned int key)
386{
387 struct mb_cache *cache = ce->e_cache;
388 unsigned int bucket;
389 struct list_head *l;
390 int error = -EBUSY;
391
392 bucket = hash_long((unsigned long)bdev + (block & 0xffffffff),
393 cache->c_bucket_bits);
394 spin_lock(&mb_cache_spinlock);
395 list_for_each_prev(l, &cache->c_block_hash[bucket]) {
396 struct mb_cache_entry *ce =
397 list_entry(l, struct mb_cache_entry, e_block_list);
398 if (ce->e_bdev == bdev && ce->e_block == block)
399 goto out;
400 }
401 __mb_cache_entry_unhash(ce);
402 ce->e_bdev = bdev;
403 ce->e_block = block;
404 list_add(&ce->e_block_list, &cache->c_block_hash[bucket]);
405 ce->e_index.o_key = key;
406 bucket = hash_long(key, cache->c_bucket_bits);
407 list_add(&ce->e_index.o_list, &cache->c_index_hash[bucket]);
408 error = 0;
409out:
410 spin_unlock(&mb_cache_spinlock);
411 return error;
412}
413
414
415
416
417
418
419
420
421
422void
423mb_cache_entry_release(struct mb_cache_entry *ce)
424{
425 spin_lock(&mb_cache_spinlock);
426 __mb_cache_entry_release_unlock(ce);
427}
428
429
430
431
432
433
434
435
436void
437mb_cache_entry_free(struct mb_cache_entry *ce)
438{
439 spin_lock(&mb_cache_spinlock);
440 mb_assert(list_empty(&ce->e_lru_list));
441 __mb_cache_entry_unhash(ce);
442 __mb_cache_entry_release_unlock(ce);
443}
444
445
446
447
448
449
450
451
452
453
454struct mb_cache_entry *
455mb_cache_entry_get(struct mb_cache *cache, struct block_device *bdev,
456 sector_t block)
457{
458 unsigned int bucket;
459 struct list_head *l;
460 struct mb_cache_entry *ce;
461
462 bucket = hash_long((unsigned long)bdev + (block & 0xffffffff),
463 cache->c_bucket_bits);
464 spin_lock(&mb_cache_spinlock);
465 list_for_each(l, &cache->c_block_hash[bucket]) {
466 ce = list_entry(l, struct mb_cache_entry, e_block_list);
467 if (ce->e_bdev == bdev && ce->e_block == block) {
468 DEFINE_WAIT(wait);
469
470 if (!list_empty(&ce->e_lru_list))
471 list_del_init(&ce->e_lru_list);
472
473 while (ce->e_used > 0) {
474 ce->e_queued++;
475 prepare_to_wait(&mb_cache_queue, &wait,
476 TASK_UNINTERRUPTIBLE);
477 spin_unlock(&mb_cache_spinlock);
478 schedule();
479 spin_lock(&mb_cache_spinlock);
480 ce->e_queued--;
481 }
482 finish_wait(&mb_cache_queue, &wait);
483 ce->e_used += 1 + MB_CACHE_WRITER;
484
485 if (!__mb_cache_entry_is_hashed(ce)) {
486 __mb_cache_entry_release_unlock(ce);
487 return NULL;
488 }
489 goto cleanup;
490 }
491 }
492 ce = NULL;
493
494cleanup:
495 spin_unlock(&mb_cache_spinlock);
496 return ce;
497}
498
499#if !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0)
500
501static struct mb_cache_entry *
502__mb_cache_entry_find(struct list_head *l, struct list_head *head,
503 struct block_device *bdev, unsigned int key)
504{
505 while (l != head) {
506 struct mb_cache_entry *ce =
507 list_entry(l, struct mb_cache_entry, e_index.o_list);
508 if (ce->e_bdev == bdev && ce->e_index.o_key == key) {
509 DEFINE_WAIT(wait);
510
511 if (!list_empty(&ce->e_lru_list))
512 list_del_init(&ce->e_lru_list);
513
514
515
516 ce->e_used++;
517 while (ce->e_used >= MB_CACHE_WRITER) {
518 ce->e_queued++;
519 prepare_to_wait(&mb_cache_queue, &wait,
520 TASK_UNINTERRUPTIBLE);
521 spin_unlock(&mb_cache_spinlock);
522 schedule();
523 spin_lock(&mb_cache_spinlock);
524 ce->e_queued--;
525 }
526 finish_wait(&mb_cache_queue, &wait);
527
528 if (!__mb_cache_entry_is_hashed(ce)) {
529 __mb_cache_entry_release_unlock(ce);
530 spin_lock(&mb_cache_spinlock);
531 return ERR_PTR(-EAGAIN);
532 }
533 return ce;
534 }
535 l = l->next;
536 }
537 return NULL;
538}
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553struct mb_cache_entry *
554mb_cache_entry_find_first(struct mb_cache *cache, struct block_device *bdev,
555 unsigned int key)
556{
557 unsigned int bucket = hash_long(key, cache->c_bucket_bits);
558 struct list_head *l;
559 struct mb_cache_entry *ce;
560
561 spin_lock(&mb_cache_spinlock);
562 l = cache->c_index_hash[bucket].next;
563 ce = __mb_cache_entry_find(l, &cache->c_index_hash[bucket], bdev, key);
564 spin_unlock(&mb_cache_spinlock);
565 return ce;
566}
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587struct mb_cache_entry *
588mb_cache_entry_find_next(struct mb_cache_entry *prev,
589 struct block_device *bdev, unsigned int key)
590{
591 struct mb_cache *cache = prev->e_cache;
592 unsigned int bucket = hash_long(key, cache->c_bucket_bits);
593 struct list_head *l;
594 struct mb_cache_entry *ce;
595
596 spin_lock(&mb_cache_spinlock);
597 l = prev->e_index.o_list.next;
598 ce = __mb_cache_entry_find(l, &cache->c_index_hash[bucket], bdev, key);
599 __mb_cache_entry_release_unlock(prev);
600 return ce;
601}
602
603#endif
604
605static int __init init_mbcache(void)
606{
607 register_shrinker(&mb_cache_shrinker);
608 return 0;
609}
610
611static void __exit exit_mbcache(void)
612{
613 unregister_shrinker(&mb_cache_shrinker);
614}
615
616module_init(init_mbcache)
617module_exit(exit_mbcache)
618
619