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