projects/linux·blob v4.2 · refs

858 lines · 24.1 KiB

1/*
2 * linux/fs/mbcache.c
3 * (C) 2001-2002 Andreas Gruenbacher, <[email protected]>
4 */
5
6/*
7 * Filesystem Meta Information Block Cache (mbcache)
8 *
9 * The mbcache caches blocks of block devices that need to be located
10 * by their device/block number, as well as by other criteria (such
11 * as the block's contents).
12 *
13 * There can only be one cache entry in a cache per device and block number.
14 * Additional indexes need not be unique in this sense. The number of
15 * additional indexes (=other criteria) can be hardwired at compile time
16 * or specified at cache create time.
17 *
18 * Each cache entry is of fixed size. An entry may be `valid' or `invalid'
19 * in the cache. A valid entry is in the main hash tables of the cache,
20 * and may also be in the lru list. An invalid entry is not in any hashes
21 * or lists.
22 *
23 * A valid cache entry is only in the lru list if no handles refer to it.
24 * Invalid cache entries will be freed when the last handle to the cache
25 * entry is released. Entries that cannot be freed immediately are put
26 * back on the lru list.
27 */
28
29/*
30 * Lock descriptions and usage:
31 *
32 * Each hash chain of both the block and index hash tables now contains
33 * a built-in lock used to serialize accesses to the hash chain.
34 *
35 * Accesses to global data structures mb_cache_list and mb_cache_lru_list
36 * are serialized via the global spinlock mb_cache_spinlock.
37 *
38 * Each mb_cache_entry contains a spinlock, e_entry_lock, to serialize
39 * accesses to its local data, such as e_used and e_queued.
40 *
41 * Lock ordering:
42 *
43 * Each block hash chain's lock has the highest lock order, followed by an
44 * index hash chain's lock, mb_cache_bg_lock (used to implement mb_cache_entry's
45 * lock), and mb_cach_spinlock, with the lowest order. While holding
46 * either a block or index hash chain lock, a thread can acquire an
47 * mc_cache_bg_lock, which in turn can also acquire mb_cache_spinlock.
48 *
49 * Synchronization:
50 *
51 * Since both mb_cache_entry_get and mb_cache_entry_find scan the block and
52 * index hash chian, it needs to lock the corresponding hash chain. For each
53 * mb_cache_entry within the chain, it needs to lock the mb_cache_entry to
54 * prevent either any simultaneous release or free on the entry and also
55 * to serialize accesses to either the e_used or e_queued member of the entry.
56 *
57 * To avoid having a dangling reference to an already freed
58 * mb_cache_entry, an mb_cache_entry is only freed when it is not on a
59 * block hash chain and also no longer being referenced, both e_used,
60 * and e_queued are 0's. When an mb_cache_entry is explicitly freed it is
61 * first removed from a block hash chain.
62 */
63
64#include <linux/kernel.h>
65#include <linux/module.h>
66
67#include <linux/hash.h>
68#include <linux/fs.h>
69#include <linux/mm.h>
70#include <linux/slab.h>
71#include <linux/sched.h>
72#include <linux/list_bl.h>
73#include <linux/mbcache.h>
74#include <linux/init.h>
75#include <linux/blockgroup_lock.h>
76#include <linux/log2.h>
77
78#ifdef MB_CACHE_DEBUG
79# define mb_debug(f...) do { \
80 printk(KERN_DEBUG f); \
81 printk("\n"); \
82 } while (0)
83#define mb_assert(c) do { if (!(c)) \
84 printk(KERN_ERR "assertion " #c " failed\n"); \
85 } while(0)
86#else
87# define mb_debug(f...) do { } while(0)
88# define mb_assert(c) do { } while(0)
89#endif
90#define mb_error(f...) do { \
91 printk(KERN_ERR f); \
92 printk("\n"); \
93 } while(0)
94
95#define MB_CACHE_WRITER ((unsigned short)~0U >> 1)
96
97#define MB_CACHE_ENTRY_LOCK_BITS ilog2(NR_BG_LOCKS)
98#define MB_CACHE_ENTRY_LOCK_INDEX(ce) \
99 (hash_long((unsigned long)ce, MB_CACHE_ENTRY_LOCK_BITS))
100
101static DECLARE_WAIT_QUEUE_HEAD(mb_cache_queue);
102static struct blockgroup_lock *mb_cache_bg_lock;
103static struct kmem_cache *mb_cache_kmem_cache;
104
105MODULE_AUTHOR("Andreas Gruenbacher <[email protected]>");
106MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
107MODULE_LICENSE("GPL");
108
109EXPORT_SYMBOL(mb_cache_create);
110EXPORT_SYMBOL(mb_cache_shrink);
111EXPORT_SYMBOL(mb_cache_destroy);
112EXPORT_SYMBOL(mb_cache_entry_alloc);
113EXPORT_SYMBOL(mb_cache_entry_insert);
114EXPORT_SYMBOL(mb_cache_entry_release);
115EXPORT_SYMBOL(mb_cache_entry_free);
116EXPORT_SYMBOL(mb_cache_entry_get);
117#if !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0)
118EXPORT_SYMBOL(mb_cache_entry_find_first);
119EXPORT_SYMBOL(mb_cache_entry_find_next);
120#endif
121
122/*
123 * Global data: list of all mbcache's, lru list, and a spinlock for
124 * accessing cache data structures on SMP machines. The lru list is
125 * global across all mbcaches.
126 */
127
128static LIST_HEAD(mb_cache_list);
129static LIST_HEAD(mb_cache_lru_list);
130static DEFINE_SPINLOCK(mb_cache_spinlock);
131
132static inline void
133__spin_lock_mb_cache_entry(struct mb_cache_entry *ce)
134{
135 spin_lock(bgl_lock_ptr(mb_cache_bg_lock,
136 MB_CACHE_ENTRY_LOCK_INDEX(ce)));
137}
138
139static inline void
140__spin_unlock_mb_cache_entry(struct mb_cache_entry *ce)
141{
142 spin_unlock(bgl_lock_ptr(mb_cache_bg_lock,
143 MB_CACHE_ENTRY_LOCK_INDEX(ce)));
144}
145
146static inline int
147__mb_cache_entry_is_block_hashed(struct mb_cache_entry *ce)
148{
149 return !hlist_bl_unhashed(&ce->e_block_list);
150}
151
152
153static inline void
154__mb_cache_entry_unhash_block(struct mb_cache_entry *ce)
155{
156 if (__mb_cache_entry_is_block_hashed(ce))
157 hlist_bl_del_init(&ce->e_block_list);
158}
159
160static inline int
161__mb_cache_entry_is_index_hashed(struct mb_cache_entry *ce)
162{
163 return !hlist_bl_unhashed(&ce->e_index.o_list);
164}
165
166static inline void
167__mb_cache_entry_unhash_index(struct mb_cache_entry *ce)
168{
169 if (__mb_cache_entry_is_index_hashed(ce))
170 hlist_bl_del_init(&ce->e_index.o_list);
171}
172
173/*
174 * __mb_cache_entry_unhash_unlock()
175 *
176 * This function is called to unhash both the block and index hash
177 * chain.
178 * It assumes both the block and index hash chain is locked upon entry.
179 * It also unlock both hash chains both exit
180 */
181static inline void
182__mb_cache_entry_unhash_unlock(struct mb_cache_entry *ce)
183{
184 __mb_cache_entry_unhash_index(ce);
185 hlist_bl_unlock(ce->e_index_hash_p);
186 __mb_cache_entry_unhash_block(ce);
187 hlist_bl_unlock(ce->e_block_hash_p);
188}
189
190static void
191__mb_cache_entry_forget(struct mb_cache_entry *ce, gfp_t gfp_mask)
192{
193 struct mb_cache *cache = ce->e_cache;
194
195 mb_assert(!(ce->e_used || ce->e_queued || atomic_read(&ce->e_refcnt)));
196 kmem_cache_free(cache->c_entry_cache, ce);
197 atomic_dec(&cache->c_entry_count);
198}
199
200static void
201__mb_cache_entry_release(struct mb_cache_entry *ce)
202{
203 /* First lock the entry to serialize access to its local data. */
204 __spin_lock_mb_cache_entry(ce);
205 /* Wake up all processes queuing for this cache entry. */
206 if (ce->e_queued)
207 wake_up_all(&mb_cache_queue);
208 if (ce->e_used >= MB_CACHE_WRITER)
209 ce->e_used -= MB_CACHE_WRITER;
210 /*
211 * Make sure that all cache entries on lru_list have
212 * both e_used and e_qued of 0s.
213 */
214 ce->e_used--;
215 if (!(ce->e_used || ce->e_queued || atomic_read(&ce->e_refcnt))) {
216 if (!__mb_cache_entry_is_block_hashed(ce)) {
217 __spin_unlock_mb_cache_entry(ce);
218 goto forget;
219 }
220 /*
221 * Need access to lru list, first drop entry lock,
222 * then reacquire the lock in the proper order.
223 */
224 spin_lock(&mb_cache_spinlock);
225 if (list_empty(&ce->e_lru_list))
226 list_add_tail(&ce->e_lru_list, &mb_cache_lru_list);
227 spin_unlock(&mb_cache_spinlock);
228 }
229 __spin_unlock_mb_cache_entry(ce);
230 return;
231forget:
232 mb_assert(list_empty(&ce->e_lru_list));
233 __mb_cache_entry_forget(ce, GFP_KERNEL);
234}
235
236/*
237 * mb_cache_shrink_scan() memory pressure callback
238 *
239 * This function is called by the kernel memory management when memory
240 * gets low.
241 *
242 * @shrink: (ignored)
243 * @sc: shrink_control passed from reclaim
244 *
245 * Returns the number of objects freed.
246 */
247static unsigned long
248mb_cache_shrink_scan(struct shrinker *shrink, struct shrink_control *sc)
249{
250 LIST_HEAD(free_list);
251 struct mb_cache_entry *entry, *tmp;
252 int nr_to_scan = sc->nr_to_scan;
253 gfp_t gfp_mask = sc->gfp_mask;
254 unsigned long freed = 0;
255
256 mb_debug("trying to free %d entries", nr_to_scan);
257 spin_lock(&mb_cache_spinlock);
258 while ((nr_to_scan-- > 0) && !list_empty(&mb_cache_lru_list)) {
259 struct mb_cache_entry *ce =
260 list_entry(mb_cache_lru_list.next,
261 struct mb_cache_entry, e_lru_list);
262 list_del_init(&ce->e_lru_list);
263 if (ce->e_used || ce->e_queued || atomic_read(&ce->e_refcnt))
264 continue;
265 spin_unlock(&mb_cache_spinlock);
266 /* Prevent any find or get operation on the entry */
267 hlist_bl_lock(ce->e_block_hash_p);
268 hlist_bl_lock(ce->e_index_hash_p);
269 /* Ignore if it is touched by a find/get */
270 if (ce->e_used || ce->e_queued || atomic_read(&ce->e_refcnt) ||
271 !list_empty(&ce->e_lru_list)) {
272 hlist_bl_unlock(ce->e_index_hash_p);
273 hlist_bl_unlock(ce->e_block_hash_p);
274 spin_lock(&mb_cache_spinlock);
275 continue;
276 }
277 __mb_cache_entry_unhash_unlock(ce);
278 list_add_tail(&ce->e_lru_list, &free_list);
279 spin_lock(&mb_cache_spinlock);
280 }
281 spin_unlock(&mb_cache_spinlock);
282
283 list_for_each_entry_safe(entry, tmp, &free_list, e_lru_list) {
284 __mb_cache_entry_forget(entry, gfp_mask);
285 freed++;
286 }
287 return freed;
288}
289
290static unsigned long
291mb_cache_shrink_count(struct shrinker *shrink, struct shrink_control *sc)
292{
293 struct mb_cache *cache;
294 unsigned long count = 0;
295
296 spin_lock(&mb_cache_spinlock);
297 list_for_each_entry(cache, &mb_cache_list, c_cache_list) {
298 mb_debug("cache %s (%d)", cache->c_name,
299 atomic_read(&cache->c_entry_count));
300 count += atomic_read(&cache->c_entry_count);
301 }
302 spin_unlock(&mb_cache_spinlock);
303
304 return vfs_pressure_ratio(count);
305}
306
307static struct shrinker mb_cache_shrinker = {
308 .count_objects = mb_cache_shrink_count,
309 .scan_objects = mb_cache_shrink_scan,
310 .seeks = DEFAULT_SEEKS,
311};
312
313/*
314 * mb_cache_create() create a new cache
315 *
316 * All entries in one cache are equal size. Cache entries may be from
317 * multiple devices. If this is the first mbcache created, registers
318 * the cache with kernel memory management. Returns NULL if no more
319 * memory was available.
320 *
321 * @name: name of the cache (informal)
322 * @bucket_bits: log2(number of hash buckets)
323 */
324struct mb_cache *
325mb_cache_create(const char *name, int bucket_bits)
326{
327 int n, bucket_count = 1 << bucket_bits;
328 struct mb_cache *cache = NULL;
329
330 if (!mb_cache_bg_lock) {
331 mb_cache_bg_lock = kmalloc(sizeof(struct blockgroup_lock),
332 GFP_KERNEL);
333 if (!mb_cache_bg_lock)
334 return NULL;
335 bgl_lock_init(mb_cache_bg_lock);
336 }
337
338 cache = kmalloc(sizeof(struct mb_cache), GFP_KERNEL);
339 if (!cache)
340 return NULL;
341 cache->c_name = name;
342 atomic_set(&cache->c_entry_count, 0);
343 cache->c_bucket_bits = bucket_bits;
344 cache->c_block_hash = kmalloc(bucket_count *
345 sizeof(struct hlist_bl_head), GFP_KERNEL);
346 if (!cache->c_block_hash)
347 goto fail;
348 for (n=0; n<bucket_count; n++)
349 INIT_HLIST_BL_HEAD(&cache->c_block_hash[n]);
350 cache->c_index_hash = kmalloc(bucket_count *
351 sizeof(struct hlist_bl_head), GFP_KERNEL);
352 if (!cache->c_index_hash)
353 goto fail;
354 for (n=0; n<bucket_count; n++)
355 INIT_HLIST_BL_HEAD(&cache->c_index_hash[n]);
356 if (!mb_cache_kmem_cache) {
357 mb_cache_kmem_cache = kmem_cache_create(name,
358 sizeof(struct mb_cache_entry), 0,
359 SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL);
360 if (!mb_cache_kmem_cache)
361 goto fail2;
362 }
363 cache->c_entry_cache = mb_cache_kmem_cache;
364
365 /*
366 * Set an upper limit on the number of cache entries so that the hash
367 * chains won't grow too long.
368 */
369 cache->c_max_entries = bucket_count << 4;
370
371 spin_lock(&mb_cache_spinlock);
372 list_add(&cache->c_cache_list, &mb_cache_list);
373 spin_unlock(&mb_cache_spinlock);
374 return cache;
375
376fail2:
377 kfree(cache->c_index_hash);
378
379fail:
380 kfree(cache->c_block_hash);
381 kfree(cache);
382 return NULL;
383}
384
385
386/*
387 * mb_cache_shrink()
388 *
389 * Removes all cache entries of a device from the cache. All cache entries
390 * currently in use cannot be freed, and thus remain in the cache. All others
391 * are freed.
392 *
393 * @bdev: which device's cache entries to shrink
394 */
395void
396mb_cache_shrink(struct block_device *bdev)
397{
398 LIST_HEAD(free_list);
399 struct list_head *l;
400 struct mb_cache_entry *ce, *tmp;
401
402 l = &mb_cache_lru_list;
403 spin_lock(&mb_cache_spinlock);
404 while (!list_is_last(l, &mb_cache_lru_list)) {
405 l = l->next;
406 ce = list_entry(l, struct mb_cache_entry, e_lru_list);
407 if (ce->e_bdev == bdev) {
408 list_del_init(&ce->e_lru_list);
409 if (ce->e_used || ce->e_queued ||
410 atomic_read(&ce->e_refcnt))
411 continue;
412 spin_unlock(&mb_cache_spinlock);
413 /*
414 * Prevent any find or get operation on the entry.
415 */
416 hlist_bl_lock(ce->e_block_hash_p);
417 hlist_bl_lock(ce->e_index_hash_p);
418 /* Ignore if it is touched by a find/get */
419 if (ce->e_used || ce->e_queued ||
420 atomic_read(&ce->e_refcnt) ||
421 !list_empty(&ce->e_lru_list)) {
422 hlist_bl_unlock(ce->e_index_hash_p);
423 hlist_bl_unlock(ce->e_block_hash_p);
424 l = &mb_cache_lru_list;
425 spin_lock(&mb_cache_spinlock);
426 continue;
427 }
428 __mb_cache_entry_unhash_unlock(ce);
429 mb_assert(!(ce->e_used || ce->e_queued ||
430 atomic_read(&ce->e_refcnt)));
431 list_add_tail(&ce->e_lru_list, &free_list);
432 l = &mb_cache_lru_list;
433 spin_lock(&mb_cache_spinlock);
434 }
435 }
436 spin_unlock(&mb_cache_spinlock);
437
438 list_for_each_entry_safe(ce, tmp, &free_list, e_lru_list) {
439 __mb_cache_entry_forget(ce, GFP_KERNEL);
440 }
441}
442
443
444/*
445 * mb_cache_destroy()
446 *
447 * Shrinks the cache to its minimum possible size (hopefully 0 entries),
448 * and then destroys it. If this was the last mbcache, un-registers the
449 * mbcache from kernel memory management.
450 */
451void
452mb_cache_destroy(struct mb_cache *cache)
453{
454 LIST_HEAD(free_list);
455 struct mb_cache_entry *ce, *tmp;
456
457 spin_lock(&mb_cache_spinlock);
458 list_for_each_entry_safe(ce, tmp, &mb_cache_lru_list, e_lru_list) {
459 if (ce->e_cache == cache)
460 list_move_tail(&ce->e_lru_list, &free_list);
461 }
462 list_del(&cache->c_cache_list);
463 spin_unlock(&mb_cache_spinlock);
464
465 list_for_each_entry_safe(ce, tmp, &free_list, e_lru_list) {
466 list_del_init(&ce->e_lru_list);
467 /*
468 * Prevent any find or get operation on the entry.
469 */
470 hlist_bl_lock(ce->e_block_hash_p);
471 hlist_bl_lock(ce->e_index_hash_p);
472 mb_assert(!(ce->e_used || ce->e_queued ||
473 atomic_read(&ce->e_refcnt)));
474 __mb_cache_entry_unhash_unlock(ce);
475 __mb_cache_entry_forget(ce, GFP_KERNEL);
476 }
477
478 if (atomic_read(&cache->c_entry_count) > 0) {
479 mb_error("cache %s: %d orphaned entries",
480 cache->c_name,
481 atomic_read(&cache->c_entry_count));
482 }
483
484 if (list_empty(&mb_cache_list)) {
485 kmem_cache_destroy(mb_cache_kmem_cache);
486 mb_cache_kmem_cache = NULL;
487 }
488 kfree(cache->c_index_hash);
489 kfree(cache->c_block_hash);
490 kfree(cache);
491}
492
493/*
494 * mb_cache_entry_alloc()
495 *
496 * Allocates a new cache entry. The new entry will not be valid initially,
497 * and thus cannot be looked up yet. It should be filled with data, and
498 * then inserted into the cache using mb_cache_entry_insert(). Returns NULL
499 * if no more memory was available.
500 */
501struct mb_cache_entry *
502mb_cache_entry_alloc(struct mb_cache *cache, gfp_t gfp_flags)
503{
504 struct mb_cache_entry *ce;
505
506 if (atomic_read(&cache->c_entry_count) >= cache->c_max_entries) {
507 struct list_head *l;
508
509 l = &mb_cache_lru_list;
510 spin_lock(&mb_cache_spinlock);
511 while (!list_is_last(l, &mb_cache_lru_list)) {
512 l = l->next;
513 ce = list_entry(l, struct mb_cache_entry, e_lru_list);
514 if (ce->e_cache == cache) {
515 list_del_init(&ce->e_lru_list);
516 if (ce->e_used || ce->e_queued ||
517 atomic_read(&ce->e_refcnt))
518 continue;
519 spin_unlock(&mb_cache_spinlock);
520 /*
521 * Prevent any find or get operation on the
522 * entry.
523 */
524 hlist_bl_lock(ce->e_block_hash_p);
525 hlist_bl_lock(ce->e_index_hash_p);
526 /* Ignore if it is touched by a find/get */
527 if (ce->e_used || ce->e_queued ||
528 atomic_read(&ce->e_refcnt) ||
529 !list_empty(&ce->e_lru_list)) {
530 hlist_bl_unlock(ce->e_index_hash_p);
531 hlist_bl_unlock(ce->e_block_hash_p);
532 l = &mb_cache_lru_list;
533 spin_lock(&mb_cache_spinlock);
534 continue;
535 }
536 mb_assert(list_empty(&ce->e_lru_list));
537 mb_assert(!(ce->e_used || ce->e_queued ||
538 atomic_read(&ce->e_refcnt)));
539 __mb_cache_entry_unhash_unlock(ce);
540 goto found;
541 }
542 }
543 spin_unlock(&mb_cache_spinlock);
544 }
545
546 ce = kmem_cache_alloc(cache->c_entry_cache, gfp_flags);
547 if (!ce)
548 return NULL;
549 atomic_inc(&cache->c_entry_count);
550 INIT_LIST_HEAD(&ce->e_lru_list);
551 INIT_HLIST_BL_NODE(&ce->e_block_list);
552 INIT_HLIST_BL_NODE(&ce->e_index.o_list);
553 ce->e_cache = cache;
554 ce->e_queued = 0;
555 atomic_set(&ce->e_refcnt, 0);
556found:
557 ce->e_block_hash_p = &cache->c_block_hash[0];
558 ce->e_index_hash_p = &cache->c_index_hash[0];
559 ce->e_used = 1 + MB_CACHE_WRITER;
560 return ce;
561}
562
563
564/*
565 * mb_cache_entry_insert()
566 *
567 * Inserts an entry that was allocated using mb_cache_entry_alloc() into
568 * the cache. After this, the cache entry can be looked up, but is not yet
569 * in the lru list as the caller still holds a handle to it. Returns 0 on
570 * success, or -EBUSY if a cache entry for that device + inode exists
571 * already (this may happen after a failed lookup, but when another process
572 * has inserted the same cache entry in the meantime).
573 *
574 * @bdev: device the cache entry belongs to
575 * @block: block number
576 * @key: lookup key
577 */
578int
579mb_cache_entry_insert(struct mb_cache_entry *ce, struct block_device *bdev,
580 sector_t block, unsigned int key)
581{
582 struct mb_cache *cache = ce->e_cache;
583 unsigned int bucket;
584 struct hlist_bl_node *l;
585 struct hlist_bl_head *block_hash_p;
586 struct hlist_bl_head *index_hash_p;
587 struct mb_cache_entry *lce;
588
589 mb_assert(ce);
590 bucket = hash_long((unsigned long)bdev + (block & 0xffffffff),
591 cache->c_bucket_bits);
592 block_hash_p = &cache->c_block_hash[bucket];
593 hlist_bl_lock(block_hash_p);
594 hlist_bl_for_each_entry(lce, l, block_hash_p, e_block_list) {
595 if (lce->e_bdev == bdev && lce->e_block == block) {
596 hlist_bl_unlock(block_hash_p);
597 return -EBUSY;
598 }
599 }
600 mb_assert(!__mb_cache_entry_is_block_hashed(ce));
601 __mb_cache_entry_unhash_block(ce);
602 __mb_cache_entry_unhash_index(ce);
603 ce->e_bdev = bdev;
604 ce->e_block = block;
605 ce->e_block_hash_p = block_hash_p;
606 ce->e_index.o_key = key;
607 hlist_bl_add_head(&ce->e_block_list, block_hash_p);
608 hlist_bl_unlock(block_hash_p);
609 bucket = hash_long(key, cache->c_bucket_bits);
610 index_hash_p = &cache->c_index_hash[bucket];
611 hlist_bl_lock(index_hash_p);
612 ce->e_index_hash_p = index_hash_p;
613 hlist_bl_add_head(&ce->e_index.o_list, index_hash_p);
614 hlist_bl_unlock(index_hash_p);
615 return 0;
616}
617
618
619/*
620 * mb_cache_entry_release()
621 *
622 * Release a handle to a cache entry. When the last handle to a cache entry
623 * is released it is either freed (if it is invalid) or otherwise inserted
624 * in to the lru list.
625 */
626void
627mb_cache_entry_release(struct mb_cache_entry *ce)
628{
629 __mb_cache_entry_release(ce);
630}
631
632
633/*
634 * mb_cache_entry_free()
635 *
636 */
637void
638mb_cache_entry_free(struct mb_cache_entry *ce)
639{
640 mb_assert(ce);
641 mb_assert(list_empty(&ce->e_lru_list));
642 hlist_bl_lock(ce->e_index_hash_p);
643 __mb_cache_entry_unhash_index(ce);
644 hlist_bl_unlock(ce->e_index_hash_p);
645 hlist_bl_lock(ce->e_block_hash_p);
646 __mb_cache_entry_unhash_block(ce);
647 hlist_bl_unlock(ce->e_block_hash_p);
648 __mb_cache_entry_release(ce);
649}
650
651
652/*
653 * mb_cache_entry_get()
654 *
655 * Get a cache entry by device / block number. (There can only be one entry
656 * in the cache per device and block.) Returns NULL if no such cache entry
657 * exists. The returned cache entry is locked for exclusive access ("single
658 * writer").
659 */
660struct mb_cache_entry *
661mb_cache_entry_get(struct mb_cache *cache, struct block_device *bdev,
662 sector_t block)
663{
664 unsigned int bucket;
665 struct hlist_bl_node *l;
666 struct mb_cache_entry *ce;
667 struct hlist_bl_head *block_hash_p;
668
669 bucket = hash_long((unsigned long)bdev + (block & 0xffffffff),
670 cache->c_bucket_bits);
671 block_hash_p = &cache->c_block_hash[bucket];
672 /* First serialize access to the block corresponding hash chain. */
673 hlist_bl_lock(block_hash_p);
674 hlist_bl_for_each_entry(ce, l, block_hash_p, e_block_list) {
675 mb_assert(ce->e_block_hash_p == block_hash_p);
676 if (ce->e_bdev == bdev && ce->e_block == block) {
677 /*
678 * Prevent a free from removing the entry.
679 */
680 atomic_inc(&ce->e_refcnt);
681 hlist_bl_unlock(block_hash_p);
682 __spin_lock_mb_cache_entry(ce);
683 atomic_dec(&ce->e_refcnt);
684 if (ce->e_used > 0) {
685 DEFINE_WAIT(wait);
686 while (ce->e_used > 0) {
687 ce->e_queued++;
688 prepare_to_wait(&mb_cache_queue, &wait,
689 TASK_UNINTERRUPTIBLE);
690 __spin_unlock_mb_cache_entry(ce);
691 schedule();
692 __spin_lock_mb_cache_entry(ce);
693 ce->e_queued--;
694 }
695 finish_wait(&mb_cache_queue, &wait);
696 }
697 ce->e_used += 1 + MB_CACHE_WRITER;
698 __spin_unlock_mb_cache_entry(ce);
699
700 if (!list_empty(&ce->e_lru_list)) {
701 spin_lock(&mb_cache_spinlock);
702 list_del_init(&ce->e_lru_list);
703 spin_unlock(&mb_cache_spinlock);
704 }
705 if (!__mb_cache_entry_is_block_hashed(ce)) {
706 __mb_cache_entry_release(ce);
707 return NULL;
708 }
709 return ce;
710 }
711 }
712 hlist_bl_unlock(block_hash_p);
713 return NULL;
714}
715
716#if !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0)
717
718static struct mb_cache_entry *
719__mb_cache_entry_find(struct hlist_bl_node *l, struct hlist_bl_head *head,
720 struct block_device *bdev, unsigned int key)
721{
722
723 /* The index hash chain is alredy acquire by caller. */
724 while (l != NULL) {
725 struct mb_cache_entry *ce =
726 hlist_bl_entry(l, struct mb_cache_entry,
727 e_index.o_list);
728 mb_assert(ce->e_index_hash_p == head);
729 if (ce->e_bdev == bdev && ce->e_index.o_key == key) {
730 /*
731 * Prevent a free from removing the entry.
732 */
733 atomic_inc(&ce->e_refcnt);
734 hlist_bl_unlock(head);
735 __spin_lock_mb_cache_entry(ce);
736 atomic_dec(&ce->e_refcnt);
737 ce->e_used++;
738 /* Incrementing before holding the lock gives readers
739 priority over writers. */
740 if (ce->e_used >= MB_CACHE_WRITER) {
741 DEFINE_WAIT(wait);
742
743 while (ce->e_used >= MB_CACHE_WRITER) {
744 ce->e_queued++;
745 prepare_to_wait(&mb_cache_queue, &wait,
746 TASK_UNINTERRUPTIBLE);
747 __spin_unlock_mb_cache_entry(ce);
748 schedule();
749 __spin_lock_mb_cache_entry(ce);
750 ce->e_queued--;
751 }
752 finish_wait(&mb_cache_queue, &wait);
753 }
754 __spin_unlock_mb_cache_entry(ce);
755 if (!list_empty(&ce->e_lru_list)) {
756 spin_lock(&mb_cache_spinlock);
757 list_del_init(&ce->e_lru_list);
758 spin_unlock(&mb_cache_spinlock);
759 }
760 if (!__mb_cache_entry_is_block_hashed(ce)) {
761 __mb_cache_entry_release(ce);
762 return ERR_PTR(-EAGAIN);
763 }
764 return ce;
765 }
766 l = l->next;
767 }
768 hlist_bl_unlock(head);
769 return NULL;
770}
771
772
773/*
774 * mb_cache_entry_find_first()
775 *
776 * Find the first cache entry on a given device with a certain key in
777 * an additional index. Additional matches can be found with
778 * mb_cache_entry_find_next(). Returns NULL if no match was found. The
779 * returned cache entry is locked for shared access ("multiple readers").
780 *
781 * @cache: the cache to search
782 * @bdev: the device the cache entry should belong to
783 * @key: the key in the index
784 */
785struct mb_cache_entry *
786mb_cache_entry_find_first(struct mb_cache *cache, struct block_device *bdev,
787 unsigned int key)
788{
789 unsigned int bucket = hash_long(key, cache->c_bucket_bits);
790 struct hlist_bl_node *l;
791 struct mb_cache_entry *ce = NULL;
792 struct hlist_bl_head *index_hash_p;
793
794 index_hash_p = &cache->c_index_hash[bucket];
795 hlist_bl_lock(index_hash_p);
796 if (!hlist_bl_empty(index_hash_p)) {
797 l = hlist_bl_first(index_hash_p);
798 ce = __mb_cache_entry_find(l, index_hash_p, bdev, key);
799 } else
800 hlist_bl_unlock(index_hash_p);
801 return ce;
802}
803
804
805/*
806 * mb_cache_entry_find_next()
807 *
808 * Find the next cache entry on a given device with a certain key in an
809 * additional index. Returns NULL if no match could be found. The previous
810 * entry is atomatically released, so that mb_cache_entry_find_next() can
811 * be called like this:
812 *
813 * entry = mb_cache_entry_find_first();
814 * while (entry) {
815 * ...
816 * entry = mb_cache_entry_find_next(entry, ...);
817 * }
818 *
819 * @prev: The previous match
820 * @bdev: the device the cache entry should belong to
821 * @key: the key in the index
822 */
823struct mb_cache_entry *
824mb_cache_entry_find_next(struct mb_cache_entry *prev,
825 struct block_device *bdev, unsigned int key)
826{
827 struct mb_cache *cache = prev->e_cache;
828 unsigned int bucket = hash_long(key, cache->c_bucket_bits);
829 struct hlist_bl_node *l;
830 struct mb_cache_entry *ce;
831 struct hlist_bl_head *index_hash_p;
832
833 index_hash_p = &cache->c_index_hash[bucket];
834 mb_assert(prev->e_index_hash_p == index_hash_p);
835 hlist_bl_lock(index_hash_p);
836 mb_assert(!hlist_bl_empty(index_hash_p));
837 l = prev->e_index.o_list.next;
838 ce = __mb_cache_entry_find(l, index_hash_p, bdev, key);
839 __mb_cache_entry_release(prev);
840 return ce;
841}
842
843#endif /* !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0) */
844
845static int __init init_mbcache(void)
846{
847 register_shrinker(&mb_cache_shrinker);
848 return 0;
849}
850
851static void __exit exit_mbcache(void)
852{
853 unregister_shrinker(&mb_cache_shrinker);
854}
855
856module_init(init_mbcache)
857module_exit(exit_mbcache)
858