ext2: Resolve 'dereferencing pointer to incomplete type' when enabling EXT2_XATTR_DEBUG
[linux-3.10.git] / fs / mbcache.c
1 /*
2  * linux/fs/mbcache.c
3  * (C) 2001-2002 Andreas Gruenbacher, <a.gruenbacher@computer.org>
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 #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
60 static DECLARE_WAIT_QUEUE_HEAD(mb_cache_queue);
61                 
62 MODULE_AUTHOR("Andreas Gruenbacher <a.gruenbacher@computer.org>");
63 MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
64 MODULE_LICENSE("GPL");
65
66 EXPORT_SYMBOL(mb_cache_create);
67 EXPORT_SYMBOL(mb_cache_shrink);
68 EXPORT_SYMBOL(mb_cache_destroy);
69 EXPORT_SYMBOL(mb_cache_entry_alloc);
70 EXPORT_SYMBOL(mb_cache_entry_insert);
71 EXPORT_SYMBOL(mb_cache_entry_release);
72 EXPORT_SYMBOL(mb_cache_entry_free);
73 EXPORT_SYMBOL(mb_cache_entry_get);
74 #if !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0)
75 EXPORT_SYMBOL(mb_cache_entry_find_first);
76 EXPORT_SYMBOL(mb_cache_entry_find_next);
77 #endif
78
79 /*
80  * Global data: list of all mbcache's, lru list, and a spinlock for
81  * accessing cache data structures on SMP machines. The lru list is
82  * global across all mbcaches.
83  */
84
85 static LIST_HEAD(mb_cache_list);
86 static LIST_HEAD(mb_cache_lru_list);
87 static DEFINE_SPINLOCK(mb_cache_spinlock);
88
89 /*
90  * What the mbcache registers as to get shrunk dynamically.
91  */
92
93 static int mb_cache_shrink_fn(struct shrinker *shrink, int nr_to_scan, gfp_t gfp_mask);
94
95 static struct shrinker mb_cache_shrinker = {
96         .shrink = mb_cache_shrink_fn,
97         .seeks = DEFAULT_SEEKS,
98 };
99
100 static 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
107 static 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
117 static 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
128 static void
129 __mb_cache_entry_release_unlock(struct mb_cache_entry *ce)
130         __releases(mb_cache_spinlock)
131 {
132         /* Wake up all processes queuing for this cache entry. */
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;
146 forget:
147         spin_unlock(&mb_cache_spinlock);
148         __mb_cache_entry_forget(ce, GFP_KERNEL);
149 }
150
151
152 /*
153  * mb_cache_shrink_fn()  memory pressure callback
154  *
155  * This function is called by the kernel memory management when memory
156  * gets low.
157  *
158  * @shrink: (ignored)
159  * @nr_to_scan: Number of objects to scan
160  * @gfp_mask: (ignored)
161  *
162  * Returns the number of objects which are present in the cache.
163  */
164 static int
165 mb_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  * mb_cache_create()  create a new cache
196  *
197  * All entries in one cache are equal size. Cache entries may be from
198  * multiple devices. If this is the first mbcache created, registers
199  * the cache with kernel memory management. Returns NULL if no more
200  * memory was available.
201  *
202  * @name: name of the cache (informal)
203  * @bucket_bits: log2(number of hash buckets)
204  */
205 struct mb_cache *
206 mb_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          * Set an upper limit on the number of cache entries so that the hash
237          * chains won't grow too long.
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
246 fail2:
247         kfree(cache->c_index_hash);
248
249 fail:
250         kfree(cache->c_block_hash);
251         kfree(cache);
252         return NULL;
253 }
254
255
256 /*
257  * mb_cache_shrink()
258  *
259  * Removes all cache entries of a device from the cache. All cache entries
260  * currently in use cannot be freed, and thus remain in the cache. All others
261  * are freed.
262  *
263  * @bdev: which device's cache entries to shrink
264  */
265 void
266 mb_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  * mb_cache_destroy()
290  *
291  * Shrinks the cache to its minimum possible size (hopefully 0 entries),
292  * and then destroys it. If this was the last mbcache, un-registers the
293  * mbcache from kernel memory management.
294  */
295 void
296 mb_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  * mb_cache_entry_alloc()
333  *
334  * Allocates a new cache entry. The new entry will not be valid initially,
335  * and thus cannot be looked up yet. It should be filled with data, and
336  * then inserted into the cache using mb_cache_entry_insert(). Returns NULL
337  * if no more memory was available.
338  */
339 struct mb_cache_entry *
340 mb_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  * mb_cache_entry_insert()
371  *
372  * Inserts an entry that was allocated using mb_cache_entry_alloc() into
373  * the cache. After this, the cache entry can be looked up, but is not yet
374  * in the lru list as the caller still holds a handle to it. Returns 0 on
375  * success, or -EBUSY if a cache entry for that device + inode exists
376  * already (this may happen after a failed lookup, but when another process
377  * has inserted the same cache entry in the meantime).
378  *
379  * @bdev: device the cache entry belongs to
380  * @block: block number
381  * @key: lookup key
382  */
383 int
384 mb_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;
409 out:
410         spin_unlock(&mb_cache_spinlock);
411         return error;
412 }
413
414
415 /*
416  * mb_cache_entry_release()
417  *
418  * Release a handle to a cache entry. When the last handle to a cache entry
419  * is released it is either freed (if it is invalid) or otherwise inserted
420  * in to the lru list.
421  */
422 void
423 mb_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  * mb_cache_entry_free()
432  *
433  * This is equivalent to the sequence mb_cache_entry_takeout() --
434  * mb_cache_entry_release().
435  */
436 void
437 mb_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  * mb_cache_entry_get()
448  *
449  * Get a cache entry  by device / block number. (There can only be one entry
450  * in the cache per device and block.) Returns NULL if no such cache entry
451  * exists. The returned cache entry is locked for exclusive access ("single
452  * writer").
453  */
454 struct mb_cache_entry *
455 mb_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
494 cleanup:
495         spin_unlock(&mb_cache_spinlock);
496         return ce;
497 }
498
499 #if !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0)
500
501 static 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                         /* Incrementing before holding the lock gives readers
515                            priority over writers. */
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  * mb_cache_entry_find_first()
543  *
544  * Find the first cache entry on a given device with a certain key in
545  * an additional index. Additonal matches can be found with
546  * mb_cache_entry_find_next(). Returns NULL if no match was found. The
547  * returned cache entry is locked for shared access ("multiple readers").
548  *
549  * @cache: the cache to search
550  * @bdev: the device the cache entry should belong to
551  * @key: the key in the index
552  */
553 struct mb_cache_entry *
554 mb_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  * mb_cache_entry_find_next()
571  *
572  * Find the next cache entry on a given device with a certain key in an
573  * additional index. Returns NULL if no match could be found. The previous
574  * entry is atomatically released, so that mb_cache_entry_find_next() can
575  * be called like this:
576  *
577  * entry = mb_cache_entry_find_first();
578  * while (entry) {
579  *      ...
580  *      entry = mb_cache_entry_find_next(entry, ...);
581  * }
582  *
583  * @prev: The previous match
584  * @bdev: the device the cache entry should belong to
585  * @key: the key in the index
586  */
587 struct mb_cache_entry *
588 mb_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  /* !defined(MB_CACHE_INDEXES_COUNT) || (MB_CACHE_INDEXES_COUNT > 0) */
604
605 static int __init init_mbcache(void)
606 {
607         register_shrinker(&mb_cache_shrinker);
608         return 0;
609 }
610
611 static void __exit exit_mbcache(void)
612 {
613         unregister_shrinker(&mb_cache_shrinker);
614 }
615
616 module_init(init_mbcache)
617 module_exit(exit_mbcache)
618