~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/squashfs/cache.c

Version: ~ [ linux-5.11-rc3 ] ~ [ linux-5.10.7 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.89 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.167 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.215 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.251 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.251 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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@squashfs.org.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 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  */
 64 struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 65         struct squashfs_cache *cache, u64 block, int length)
 66 {
 67         int i, n;
 68         struct squashfs_cache_entry *entry;
 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  */
186 void squashfs_cache_put(struct squashfs_cache_entry *entry)
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  */
210 void squashfs_cache_delete(struct squashfs_cache *cache)
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  */
235 struct squashfs_cache *squashfs_cache_init(char *name, int entries,
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);
262         init_waitqueue_head(&cache->wait_queue);
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++) {
277                         entry->data[j] = kmalloc(PAGE_CACHE_SIZE, GFP_KERNEL);
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  */
298 int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,
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  */
336 int squashfs_read_metadata(struct super_block *sb, void *buffer,
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  */
381 struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,
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  */
396 struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,
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  */
408 void *squashfs_read_table(struct super_block *sb, u64 block, int length)
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 }
441 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp