Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cache.c
Go to the documentation of this file.
1 /*
2  * Squashfs - a compressed read only filesystem for Linux
3  *
4  * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008
5  * Phillip Lougher <[email protected]>
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 issues 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/pagemap.h>
55 
56 #include "squashfs_fs.h"
57 #include "squashfs_fs_sb.h"
58 #include "squashfs.h"
59 
60 /*
61  * Look-up block in cache, and increment usage count. If not in cache, read
62  * and decompress it from disk.
63  */
65  struct squashfs_cache *cache, u64 block, int length)
66 {
67  int i, n;
69 
70  spin_lock(&cache->lock);
71 
72  while (1) {
73  for (i = cache->curr_blk, n = 0; n < cache->entries; n++) {
74  if (cache->entry[i].block == block) {
75  cache->curr_blk = i;
76  break;
77  }
78  i = (i + 1) % cache->entries;
79  }
80 
81  if (n == cache->entries) {
82  /*
83  * Block not in cache, if all cache entries are used
84  * go to sleep waiting for one to become available.
85  */
86  if (cache->unused == 0) {
87  cache->num_waiters++;
88  spin_unlock(&cache->lock);
89  wait_event(cache->wait_queue, cache->unused);
90  spin_lock(&cache->lock);
91  cache->num_waiters--;
92  continue;
93  }
94 
95  /*
96  * At least one unused cache entry. A simple
97  * round-robin strategy is used to choose the entry to
98  * be evicted from the cache.
99  */
100  i = cache->next_blk;
101  for (n = 0; n < cache->entries; n++) {
102  if (cache->entry[i].refcount == 0)
103  break;
104  i = (i + 1) % cache->entries;
105  }
106 
107  cache->next_blk = (i + 1) % cache->entries;
108  entry = &cache->entry[i];
109 
110  /*
111  * Initialise chosen cache entry, and fill it in from
112  * disk.
113  */
114  cache->unused--;
115  entry->block = block;
116  entry->refcount = 1;
117  entry->pending = 1;
118  entry->num_waiters = 0;
119  entry->error = 0;
120  spin_unlock(&cache->lock);
121 
122  entry->length = squashfs_read_data(sb, entry->data,
123  block, length, &entry->next_index,
124  cache->block_size, cache->pages);
125 
126  spin_lock(&cache->lock);
127 
128  if (entry->length < 0)
129  entry->error = entry->length;
130 
131  entry->pending = 0;
132 
133  /*
134  * While filling this entry one or more other processes
135  * have looked it up in the cache, and have slept
136  * waiting for it to become available.
137  */
138  if (entry->num_waiters) {
139  spin_unlock(&cache->lock);
140  wake_up_all(&entry->wait_queue);
141  } else
142  spin_unlock(&cache->lock);
143 
144  goto out;
145  }
146 
147  /*
148  * Block already in cache. Increment refcount so it doesn't
149  * get reused until we're finished with it, if it was
150  * previously unused there's one less cache entry available
151  * for reuse.
152  */
153  entry = &cache->entry[i];
154  if (entry->refcount == 0)
155  cache->unused--;
156  entry->refcount++;
157 
158  /*
159  * If the entry is currently being filled in by another process
160  * go to sleep waiting for it to become available.
161  */
162  if (entry->pending) {
163  entry->num_waiters++;
164  spin_unlock(&cache->lock);
165  wait_event(entry->wait_queue, !entry->pending);
166  } else
167  spin_unlock(&cache->lock);
168 
169  goto out;
170  }
171 
172 out:
173  TRACE("Got %s %d, start block %lld, refcount %d, error %d\n",
174  cache->name, i, entry->block, entry->refcount, entry->error);
175 
176  if (entry->error)
177  ERROR("Unable to read %s cache entry [%llx]\n", cache->name,
178  block);
179  return entry;
180 }
181 
182 
183 /*
184  * Release cache entry, once usage count is zero it can be reused.
185  */
187 {
188  struct squashfs_cache *cache = entry->cache;
189 
190  spin_lock(&cache->lock);
191  entry->refcount--;
192  if (entry->refcount == 0) {
193  cache->unused++;
194  /*
195  * If there's any processes waiting for a block to become
196  * available, wake one up.
197  */
198  if (cache->num_waiters) {
199  spin_unlock(&cache->lock);
200  wake_up(&cache->wait_queue);
201  return;
202  }
203  }
204  spin_unlock(&cache->lock);
205 }
206 
207 /*
208  * Delete cache reclaiming all kmalloced buffers.
209  */
211 {
212  int i, j;
213 
214  if (cache == NULL)
215  return;
216 
217  for (i = 0; i < cache->entries; i++) {
218  if (cache->entry[i].data) {
219  for (j = 0; j < cache->pages; j++)
220  kfree(cache->entry[i].data[j]);
221  kfree(cache->entry[i].data);
222  }
223  }
224 
225  kfree(cache->entry);
226  kfree(cache);
227 }
228 
229 
230 /*
231  * Initialise cache allocating the specified number of entries, each of
232  * size block_size. To avoid vmalloc fragmentation issues each entry
233  * is allocated as a sequence of kmalloced PAGE_CACHE_SIZE buffers.
234  */
236  int block_size)
237 {
238  int i, j;
239  struct squashfs_cache *cache = kzalloc(sizeof(*cache), GFP_KERNEL);
240 
241  if (cache == NULL) {
242  ERROR("Failed to allocate %s cache\n", name);
243  return NULL;
244  }
245 
246  cache->entry = kcalloc(entries, sizeof(*(cache->entry)), GFP_KERNEL);
247  if (cache->entry == NULL) {
248  ERROR("Failed to allocate %s cache\n", name);
249  goto cleanup;
250  }
251 
252  cache->curr_blk = 0;
253  cache->next_blk = 0;
254  cache->unused = entries;
255  cache->entries = entries;
256  cache->block_size = block_size;
257  cache->pages = block_size >> PAGE_CACHE_SHIFT;
258  cache->pages = cache->pages ? cache->pages : 1;
259  cache->name = name;
260  cache->num_waiters = 0;
261  spin_lock_init(&cache->lock);
263 
264  for (i = 0; i < entries; i++) {
265  struct squashfs_cache_entry *entry = &cache->entry[i];
266 
267  init_waitqueue_head(&cache->entry[i].wait_queue);
268  entry->cache = cache;
269  entry->block = SQUASHFS_INVALID_BLK;
270  entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);
271  if (entry->data == NULL) {
272  ERROR("Failed to allocate %s cache entry\n", name);
273  goto cleanup;
274  }
275 
276  for (j = 0; j < cache->pages; j++) {
278  if (entry->data[j] == NULL) {
279  ERROR("Failed to allocate %s buffer\n", name);
280  goto cleanup;
281  }
282  }
283  }
284 
285  return cache;
286 
287 cleanup:
288  squashfs_cache_delete(cache);
289  return NULL;
290 }
291 
292 
293 /*
294  * Copy up to length bytes from cache entry to buffer starting at offset bytes
295  * into the cache entry. If there's not length bytes then copy the number of
296  * bytes available. In all cases return the number of bytes copied.
297  */
299  int offset, int length)
300 {
301  int remaining = length;
302 
303  if (length == 0)
304  return 0;
305  else if (buffer == NULL)
306  return min(length, entry->length - offset);
307 
308  while (offset < entry->length) {
309  void *buff = entry->data[offset / PAGE_CACHE_SIZE]
310  + (offset % PAGE_CACHE_SIZE);
311  int bytes = min_t(int, entry->length - offset,
312  PAGE_CACHE_SIZE - (offset % PAGE_CACHE_SIZE));
313 
314  if (bytes >= remaining) {
315  memcpy(buffer, buff, remaining);
316  remaining = 0;
317  break;
318  }
319 
320  memcpy(buffer, buff, bytes);
321  buffer += bytes;
322  remaining -= bytes;
323  offset += bytes;
324  }
325 
326  return length - remaining;
327 }
328 
329 
330 /*
331  * Read length bytes from metadata position <block, offset> (block is the
332  * start of the compressed block on disk, and offset is the offset into
333  * the block once decompressed). Data is packed into consecutive blocks,
334  * and length bytes may require reading more than one block.
335  */
337  u64 *block, int *offset, int length)
338 {
339  struct squashfs_sb_info *msblk = sb->s_fs_info;
340  int bytes, res = length;
341  struct squashfs_cache_entry *entry;
342 
343  TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
344 
345  while (length) {
346  entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);
347  if (entry->error) {
348  res = entry->error;
349  goto error;
350  } else if (*offset >= entry->length) {
351  res = -EIO;
352  goto error;
353  }
354 
355  bytes = squashfs_copy_data(buffer, entry, *offset, length);
356  if (buffer)
357  buffer += bytes;
358  length -= bytes;
359  *offset += bytes;
360 
361  if (*offset == entry->length) {
362  *block = entry->next_index;
363  *offset = 0;
364  }
365 
366  squashfs_cache_put(entry);
367  }
368 
369  return res;
370 
371 error:
372  squashfs_cache_put(entry);
373  return res;
374 }
375 
376 
377 /*
378  * Look-up in the fragmment cache the fragment located at <start_block> in the
379  * filesystem. If necessary read and decompress it from disk.
380  */
382  u64 start_block, int length)
383 {
384  struct squashfs_sb_info *msblk = sb->s_fs_info;
385 
386  return squashfs_cache_get(sb, msblk->fragment_cache, start_block,
387  length);
388 }
389 
390 
391 /*
392  * Read and decompress the datablock located at <start_block> in the
393  * filesystem. The cache is used here to avoid duplicating locking and
394  * read/decompress code.
395  */
397  u64 start_block, int length)
398 {
399  struct squashfs_sb_info *msblk = sb->s_fs_info;
400 
401  return squashfs_cache_get(sb, msblk->read_page, start_block, length);
402 }
403 
404 
405 /*
406  * Read a filesystem table (uncompressed sequence of bytes) from disk
407  */
409 {
410  int pages = (length + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
411  int i, res;
412  void *table, *buffer, **data;
413 
414  table = buffer = kmalloc(length, GFP_KERNEL);
415  if (table == NULL)
416  return ERR_PTR(-ENOMEM);
417 
418  data = kcalloc(pages, sizeof(void *), GFP_KERNEL);
419  if (data == NULL) {
420  res = -ENOMEM;
421  goto failed;
422  }
423 
424  for (i = 0; i < pages; i++, buffer += PAGE_CACHE_SIZE)
425  data[i] = buffer;
426 
427  res = squashfs_read_data(sb, data, block, length |
428  SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, length, pages);
429 
430  kfree(data);
431 
432  if (res < 0)
433  goto failed;
434 
435  return table;
436 
437 failed:
438  kfree(table);
439  return ERR_PTR(res);
440 }