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

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

Version: ~ [ linux-5.14-rc3 ] ~ [ linux-5.13.5 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.53 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.135 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.198 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.240 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.276 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.276 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ 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_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 #include "page_actor.h"
 60 
 61 /*
 62  * Look-up block in cache, and increment usage count.  If not in cache, read
 63  * and decompress it from disk.
 64  */
 65 struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
 66         struct squashfs_cache *cache, u64 block, int length)
 67 {
 68         int i, n;
 69         struct squashfs_cache_entry *entry;
 70 
 71         spin_lock(&cache->lock);
 72 
 73         while (1) {
 74                 for (i = cache->curr_blk, n = 0; n < cache->entries; n++) {
 75                         if (cache->entry[i].block == block) {
 76                                 cache->curr_blk = i;
 77                                 break;
 78                         }
 79                         i = (i + 1) % cache->entries;
 80                 }
 81 
 82                 if (n == cache->entries) {
 83                         /*
 84                          * Block not in cache, if all cache entries are used
 85                          * go to sleep waiting for one to become available.
 86                          */
 87                         if (cache->unused == 0) {
 88                                 cache->num_waiters++;
 89                                 spin_unlock(&cache->lock);
 90                                 wait_event(cache->wait_queue, cache->unused);
 91                                 spin_lock(&cache->lock);
 92                                 cache->num_waiters--;
 93                                 continue;
 94                         }
 95 
 96                         /*
 97                          * At least one unused cache entry.  A simple
 98                          * round-robin strategy is used to choose the entry to
 99                          * be evicted from the cache.
100                          */
101                         i = cache->next_blk;
102                         for (n = 0; n < cache->entries; n++) {
103                                 if (cache->entry[i].refcount == 0)
104                                         break;
105                                 i = (i + 1) % cache->entries;
106                         }
107 
108                         cache->next_blk = (i + 1) % cache->entries;
109                         entry = &cache->entry[i];
110 
111                         /*
112                          * Initialise chosen cache entry, and fill it in from
113                          * disk.
114                          */
115                         cache->unused--;
116                         entry->block = block;
117                         entry->refcount = 1;
118                         entry->pending = 1;
119                         entry->num_waiters = 0;
120                         entry->error = 0;
121                         spin_unlock(&cache->lock);
122 
123                         entry->length = squashfs_read_data(sb, block, length,
124                                 &entry->next_index, entry->actor);
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                 kfree(cache->entry[i].actor);
224         }
225 
226         kfree(cache->entry);
227         kfree(cache);
228 }
229 
230 
231 /*
232  * Initialise cache allocating the specified number of entries, each of
233  * size block_size.  To avoid vmalloc fragmentation issues each entry
234  * is allocated as a sequence of kmalloced PAGE_SIZE buffers.
235  */
236 struct squashfs_cache *squashfs_cache_init(char *name, int entries,
237         int block_size)
238 {
239         int i, j;
240         struct squashfs_cache *cache = kzalloc(sizeof(*cache), GFP_KERNEL);
241 
242         if (cache == NULL) {
243                 ERROR("Failed to allocate %s cache\n", name);
244                 return NULL;
245         }
246 
247         cache->entry = kcalloc(entries, sizeof(*(cache->entry)), GFP_KERNEL);
248         if (cache->entry == NULL) {
249                 ERROR("Failed to allocate %s cache\n", name);
250                 goto cleanup;
251         }
252 
253         cache->curr_blk = 0;
254         cache->next_blk = 0;
255         cache->unused = entries;
256         cache->entries = entries;
257         cache->block_size = block_size;
258         cache->pages = block_size >> PAGE_SHIFT;
259         cache->pages = cache->pages ? cache->pages : 1;
260         cache->name = name;
261         cache->num_waiters = 0;
262         spin_lock_init(&cache->lock);
263         init_waitqueue_head(&cache->wait_queue);
264 
265         for (i = 0; i < entries; i++) {
266                 struct squashfs_cache_entry *entry = &cache->entry[i];
267 
268                 init_waitqueue_head(&cache->entry[i].wait_queue);
269                 entry->cache = cache;
270                 entry->block = SQUASHFS_INVALID_BLK;
271                 entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);
272                 if (entry->data == NULL) {
273                         ERROR("Failed to allocate %s cache entry\n", name);
274                         goto cleanup;
275                 }
276 
277                 for (j = 0; j < cache->pages; j++) {
278                         entry->data[j] = kmalloc(PAGE_SIZE, GFP_KERNEL);
279                         if (entry->data[j] == NULL) {
280                                 ERROR("Failed to allocate %s buffer\n", name);
281                                 goto cleanup;
282                         }
283                 }
284 
285                 entry->actor = squashfs_page_actor_init(entry->data,
286                                                 cache->pages, 0);
287                 if (entry->actor == NULL) {
288                         ERROR("Failed to allocate %s cache entry\n", name);
289                         goto cleanup;
290                 }
291         }
292 
293         return cache;
294 
295 cleanup:
296         squashfs_cache_delete(cache);
297         return NULL;
298 }
299 
300 
301 /*
302  * Copy up to length bytes from cache entry to buffer starting at offset bytes
303  * into the cache entry.  If there's not length bytes then copy the number of
304  * bytes available.  In all cases return the number of bytes copied.
305  */
306 int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,
307                 int offset, int length)
308 {
309         int remaining = length;
310 
311         if (length == 0)
312                 return 0;
313         else if (buffer == NULL)
314                 return min(length, entry->length - offset);
315 
316         while (offset < entry->length) {
317                 void *buff = entry->data[offset / PAGE_SIZE]
318                                 + (offset % PAGE_SIZE);
319                 int bytes = min_t(int, entry->length - offset,
320                                 PAGE_SIZE - (offset % PAGE_SIZE));
321 
322                 if (bytes >= remaining) {
323                         memcpy(buffer, buff, remaining);
324                         remaining = 0;
325                         break;
326                 }
327 
328                 memcpy(buffer, buff, bytes);
329                 buffer += bytes;
330                 remaining -= bytes;
331                 offset += bytes;
332         }
333 
334         return length - remaining;
335 }
336 
337 
338 /*
339  * Read length bytes from metadata position <block, offset> (block is the
340  * start of the compressed block on disk, and offset is the offset into
341  * the block once decompressed).  Data is packed into consecutive blocks,
342  * and length bytes may require reading more than one block.
343  */
344 int squashfs_read_metadata(struct super_block *sb, void *buffer,
345                 u64 *block, int *offset, int length)
346 {
347         struct squashfs_sb_info *msblk = sb->s_fs_info;
348         int bytes, res = length;
349         struct squashfs_cache_entry *entry;
350 
351         TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
352 
353         while (length) {
354                 entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);
355                 if (entry->error) {
356                         res = entry->error;
357                         goto error;
358                 } else if (*offset >= entry->length) {
359                         res = -EIO;
360                         goto error;
361                 }
362 
363                 bytes = squashfs_copy_data(buffer, entry, *offset, length);
364                 if (buffer)
365                         buffer += bytes;
366                 length -= bytes;
367                 *offset += bytes;
368 
369                 if (*offset == entry->length) {
370                         *block = entry->next_index;
371                         *offset = 0;
372                 }
373 
374                 squashfs_cache_put(entry);
375         }
376 
377         return res;
378 
379 error:
380         squashfs_cache_put(entry);
381         return res;
382 }
383 
384 
385 /*
386  * Look-up in the fragmment cache the fragment located at <start_block> in the
387  * filesystem.  If necessary read and decompress it from disk.
388  */
389 struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,
390                                 u64 start_block, int length)
391 {
392         struct squashfs_sb_info *msblk = sb->s_fs_info;
393 
394         return squashfs_cache_get(sb, msblk->fragment_cache, start_block,
395                 length);
396 }
397 
398 
399 /*
400  * Read and decompress the datablock located at <start_block> in the
401  * filesystem.  The cache is used here to avoid duplicating locking and
402  * read/decompress code.
403  */
404 struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,
405                                 u64 start_block, int length)
406 {
407         struct squashfs_sb_info *msblk = sb->s_fs_info;
408 
409         return squashfs_cache_get(sb, msblk->read_page, start_block, length);
410 }
411 
412 
413 /*
414  * Read a filesystem table (uncompressed sequence of bytes) from disk
415  */
416 void *squashfs_read_table(struct super_block *sb, u64 block, int length)
417 {
418         int pages = (length + PAGE_SIZE - 1) >> PAGE_SHIFT;
419         int i, res;
420         void *table, *buffer, **data;
421         struct squashfs_page_actor *actor;
422 
423         table = buffer = kmalloc(length, GFP_KERNEL);
424         if (table == NULL)
425                 return ERR_PTR(-ENOMEM);
426 
427         data = kcalloc(pages, sizeof(void *), GFP_KERNEL);
428         if (data == NULL) {
429                 res = -ENOMEM;
430                 goto failed;
431         }
432 
433         actor = squashfs_page_actor_init(data, pages, length);
434         if (actor == NULL) {
435                 res = -ENOMEM;
436                 goto failed2;
437         }
438 
439         for (i = 0; i < pages; i++, buffer += PAGE_SIZE)
440                 data[i] = buffer;
441 
442         res = squashfs_read_data(sb, block, length |
443                 SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, actor);
444 
445         kfree(data);
446         kfree(actor);
447 
448         if (res < 0)
449                 goto failed;
450 
451         return table;
452 
453 failed2:
454         kfree(data);
455 failed:
456         kfree(table);
457         return ERR_PTR(res);
458 }
459 

~ [ 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