Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/bart/ide-2.6
[linux-2.6] / fs / squashfs / cache.c
1 /*
2  * Squashfs - a compressed read only filesystem for Linux
3  *
4  * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008
5  * Phillip Lougher <phillip@lougher.demon.co.uk>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2,
10  * or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20  *
21  * cache.c
22  */
23
24 /*
25  * Blocks in Squashfs are compressed.  To avoid repeatedly decompressing
26  * recently accessed data Squashfs uses two small metadata and fragment caches.
27  *
28  * This file implements a generic cache implementation used for both caches,
29  * plus functions layered ontop of the generic cache implementation to
30  * access the metadata and fragment caches.
31  *
32  * To avoid out of memory and fragmentation isssues with vmalloc the cache
33  * uses sequences of kmalloced PAGE_CACHE_SIZE buffers.
34  *
35  * It should be noted that the cache is not used for file datablocks, these
36  * are decompressed and cached in the page-cache in the normal way.  The
37  * cache is only used to temporarily cache fragment and metadata blocks
38  * which have been read as as a result of a metadata (i.e. inode or
39  * directory) or fragment access.  Because metadata and fragments are packed
40  * together into blocks (to gain greater compression) the read of a particular
41  * piece of metadata or fragment will retrieve other metadata/fragments which
42  * have been packed with it, these because of locality-of-reference may be read
43  * in the near future. Temporarily caching them ensures they are available for
44  * near future access without requiring an additional read and decompress.
45  */
46
47 #include <linux/fs.h>
48 #include <linux/vfs.h>
49 #include <linux/slab.h>
50 #include <linux/vmalloc.h>
51 #include <linux/sched.h>
52 #include <linux/spinlock.h>
53 #include <linux/wait.h>
54 #include <linux/zlib.h>
55 #include <linux/pagemap.h>
56
57 #include "squashfs_fs.h"
58 #include "squashfs_fs_sb.h"
59 #include "squashfs_fs_i.h"
60 #include "squashfs.h"
61
62 /*
63  * Look-up block in cache, and increment usage count.  If not in cache, read
64  * and decompress it from disk.
65  */
66 struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
67         struct squashfs_cache *cache, u64 block, int length)
68 {
69         int i, n;
70         struct squashfs_cache_entry *entry;
71
72         spin_lock(&cache->lock);
73
74         while (1) {
75                 for (i = 0; i < cache->entries; i++)
76                         if (cache->entry[i].block == block)
77                                 break;
78
79                 if (i == cache->entries) {
80                         /*
81                          * Block not in cache, if all cache entries are used
82                          * go to sleep waiting for one to become available.
83                          */
84                         if (cache->unused == 0) {
85                                 cache->num_waiters++;
86                                 spin_unlock(&cache->lock);
87                                 wait_event(cache->wait_queue, cache->unused);
88                                 spin_lock(&cache->lock);
89                                 cache->num_waiters--;
90                                 continue;
91                         }
92
93                         /*
94                          * At least one unused cache entry.  A simple
95                          * round-robin strategy is used to choose the entry to
96                          * be evicted from the cache.
97                          */
98                         i = cache->next_blk;
99                         for (n = 0; n < cache->entries; n++) {
100                                 if (cache->entry[i].refcount == 0)
101                                         break;
102                                 i = (i + 1) % cache->entries;
103                         }
104
105                         cache->next_blk = (i + 1) % cache->entries;
106                         entry = &cache->entry[i];
107
108                         /*
109                          * Initialise choosen cache entry, and fill it in from
110                          * disk.
111                          */
112                         cache->unused--;
113                         entry->block = block;
114                         entry->refcount = 1;
115                         entry->pending = 1;
116                         entry->num_waiters = 0;
117                         entry->error = 0;
118                         spin_unlock(&cache->lock);
119
120                         entry->length = squashfs_read_data(sb, entry->data,
121                                 block, length, &entry->next_index,
122                                 cache->block_size, cache->pages);
123
124                         spin_lock(&cache->lock);
125
126                         if (entry->length < 0)
127                                 entry->error = entry->length;
128
129                         entry->pending = 0;
130
131                         /*
132                          * While filling this entry one or more other processes
133                          * have looked it up in the cache, and have slept
134                          * waiting for it to become available.
135                          */
136                         if (entry->num_waiters) {
137                                 spin_unlock(&cache->lock);
138                                 wake_up_all(&entry->wait_queue);
139                         } else
140                                 spin_unlock(&cache->lock);
141
142                         goto out;
143                 }
144
145                 /*
146                  * Block already in cache.  Increment refcount so it doesn't
147                  * get reused until we're finished with it, if it was
148                  * previously unused there's one less cache entry available
149                  * for reuse.
150                  */
151                 entry = &cache->entry[i];
152                 if (entry->refcount == 0)
153                         cache->unused--;
154                 entry->refcount++;
155
156                 /*
157                  * If the entry is currently being filled in by another process
158                  * go to sleep waiting for it to become available.
159                  */
160                 if (entry->pending) {
161                         entry->num_waiters++;
162                         spin_unlock(&cache->lock);
163                         wait_event(entry->wait_queue, !entry->pending);
164                 } else
165                         spin_unlock(&cache->lock);
166
167                 goto out;
168         }
169
170 out:
171         TRACE("Got %s %d, start block %lld, refcount %d, error %d\n",
172                 cache->name, i, entry->block, entry->refcount, entry->error);
173
174         if (entry->error)
175                 ERROR("Unable to read %s cache entry [%llx]\n", cache->name,
176                                                         block);
177         return entry;
178 }
179
180
181 /*
182  * Release cache entry, once usage count is zero it can be reused.
183  */
184 void squashfs_cache_put(struct squashfs_cache_entry *entry)
185 {
186         struct squashfs_cache *cache = entry->cache;
187
188         spin_lock(&cache->lock);
189         entry->refcount--;
190         if (entry->refcount == 0) {
191                 cache->unused++;
192                 /*
193                  * If there's any processes waiting for a block to become
194                  * available, wake one up.
195                  */
196                 if (cache->num_waiters) {
197                         spin_unlock(&cache->lock);
198                         wake_up(&cache->wait_queue);
199                         return;
200                 }
201         }
202         spin_unlock(&cache->lock);
203 }
204
205 /*
206  * Delete cache reclaiming all kmalloced buffers.
207  */
208 void squashfs_cache_delete(struct squashfs_cache *cache)
209 {
210         int i, j;
211
212         if (cache == NULL)
213                 return;
214
215         for (i = 0; i < cache->entries; i++) {
216                 if (cache->entry[i].data) {
217                         for (j = 0; j < cache->pages; j++)
218                                 kfree(cache->entry[i].data[j]);
219                         kfree(cache->entry[i].data);
220                 }
221         }
222
223         kfree(cache->entry);
224         kfree(cache);
225 }
226
227
228 /*
229  * Initialise cache allocating the specified number of entries, each of
230  * size block_size.  To avoid vmalloc fragmentation issues each entry
231  * is allocated as a sequence of kmalloced PAGE_CACHE_SIZE buffers.
232  */
233 struct squashfs_cache *squashfs_cache_init(char *name, int entries,
234         int block_size)
235 {
236         int i, j;
237         struct squashfs_cache *cache = kzalloc(sizeof(*cache), GFP_KERNEL);
238
239         if (cache == NULL) {
240                 ERROR("Failed to allocate %s cache\n", name);
241                 return NULL;
242         }
243
244         cache->entry = kcalloc(entries, sizeof(*(cache->entry)), GFP_KERNEL);
245         if (cache->entry == NULL) {
246                 ERROR("Failed to allocate %s cache\n", name);
247                 goto cleanup;
248         }
249
250         cache->next_blk = 0;
251         cache->unused = entries;
252         cache->entries = entries;
253         cache->block_size = block_size;
254         cache->pages = block_size >> PAGE_CACHE_SHIFT;
255         cache->pages = cache->pages ? cache->pages : 1;
256         cache->name = name;
257         cache->num_waiters = 0;
258         spin_lock_init(&cache->lock);
259         init_waitqueue_head(&cache->wait_queue);
260
261         for (i = 0; i < entries; i++) {
262                 struct squashfs_cache_entry *entry = &cache->entry[i];
263
264                 init_waitqueue_head(&cache->entry[i].wait_queue);
265                 entry->cache = cache;
266                 entry->block = SQUASHFS_INVALID_BLK;
267                 entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);
268                 if (entry->data == NULL) {
269                         ERROR("Failed to allocate %s cache entry\n", name);
270                         goto cleanup;
271                 }
272
273                 for (j = 0; j < cache->pages; j++) {
274                         entry->data[j] = kmalloc(PAGE_CACHE_SIZE, GFP_KERNEL);
275                         if (entry->data[j] == NULL) {
276                                 ERROR("Failed to allocate %s buffer\n", name);
277                                 goto cleanup;
278                         }
279                 }
280         }
281
282         return cache;
283
284 cleanup:
285         squashfs_cache_delete(cache);
286         return NULL;
287 }
288
289
290 /*
291  * Copy upto length bytes from cache entry to buffer starting at offset bytes
292  * into the cache entry.  If there's not length bytes then copy the number of
293  * bytes available.  In all cases return the number of bytes copied.
294  */
295 int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,
296                 int offset, int length)
297 {
298         int remaining = length;
299
300         if (length == 0)
301                 return 0;
302         else if (buffer == NULL)
303                 return min(length, entry->length - offset);
304
305         while (offset < entry->length) {
306                 void *buff = entry->data[offset / PAGE_CACHE_SIZE]
307                                 + (offset % PAGE_CACHE_SIZE);
308                 int bytes = min_t(int, entry->length - offset,
309                                 PAGE_CACHE_SIZE - (offset % PAGE_CACHE_SIZE));
310
311                 if (bytes >= remaining) {
312                         memcpy(buffer, buff, remaining);
313                         remaining = 0;
314                         break;
315                 }
316
317                 memcpy(buffer, buff, bytes);
318                 buffer += bytes;
319                 remaining -= bytes;
320                 offset += bytes;
321         }
322
323         return length - remaining;
324 }
325
326
327 /*
328  * Read length bytes from metadata position <block, offset> (block is the
329  * start of the compressed block on disk, and offset is the offset into
330  * the block once decompressed).  Data is packed into consecutive blocks,
331  * and length bytes may require reading more than one block.
332  */
333 int squashfs_read_metadata(struct super_block *sb, void *buffer,
334                 u64 *block, int *offset, int length)
335 {
336         struct squashfs_sb_info *msblk = sb->s_fs_info;
337         int bytes, copied = length;
338         struct squashfs_cache_entry *entry;
339
340         TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
341
342         while (length) {
343                 entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);
344                 if (entry->error)
345                         return entry->error;
346                 else if (*offset >= entry->length)
347                         return -EIO;
348
349                 bytes = squashfs_copy_data(buffer, entry, *offset, length);
350                 if (buffer)
351                         buffer += bytes;
352                 length -= bytes;
353                 *offset += bytes;
354
355                 if (*offset == entry->length) {
356                         *block = entry->next_index;
357                         *offset = 0;
358                 }
359
360                 squashfs_cache_put(entry);
361         }
362
363         return copied;
364 }
365
366
367 /*
368  * Look-up in the fragmment cache the fragment located at <start_block> in the
369  * filesystem.  If necessary read and decompress it from disk.
370  */
371 struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,
372                                 u64 start_block, int length)
373 {
374         struct squashfs_sb_info *msblk = sb->s_fs_info;
375
376         return squashfs_cache_get(sb, msblk->fragment_cache, start_block,
377                 length);
378 }
379
380
381 /*
382  * Read and decompress the datablock located at <start_block> in the
383  * filesystem.  The cache is used here to avoid duplicating locking and
384  * read/decompress code.
385  */
386 struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,
387                                 u64 start_block, int length)
388 {
389         struct squashfs_sb_info *msblk = sb->s_fs_info;
390
391         return squashfs_cache_get(sb, msblk->read_page, start_block, length);
392 }
393
394
395 /*
396  * Read a filesystem table (uncompressed sequence of bytes) from disk
397  */
398 int squashfs_read_table(struct super_block *sb, void *buffer, u64 block,
399         int length)
400 {
401         int pages = (length + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
402         int i, res;
403         void **data = kcalloc(pages, sizeof(void *), GFP_KERNEL);
404         if (data == NULL)
405                 return -ENOMEM;
406
407         for (i = 0; i < pages; i++, buffer += PAGE_CACHE_SIZE)
408                 data[i] = buffer;
409         res = squashfs_read_data(sb, data, block, length |
410                 SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, length, pages);
411         kfree(data);
412         return res;
413 }