cache.c revision b1a96ce61f43139b22c7a431c4ae3a14162d4309
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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 20 * 21 * cache.c 22 */ 23 24/* 25 * Metadata and fragments in Squashfs are compressed. To avoid repeatedly 26 * decompressing recently accessed data Squashfs uses two small metadata 27 * and fragment caches. 28 * 29 * This file implements a generic cache implementation used for both caches. 30 */ 31 32#include <linux/fs.h> 33#include <linux/vfs.h> 34#include <linux/slab.h> 35#include <linux/vmalloc.h> 36#include <linux/sched.h> 37#include <linux/spinlock.h> 38#include <linux/wait.h> 39#include <linux/zlib.h> 40#include <linux/squashfs_fs.h> 41#include <linux/squashfs_fs_sb.h> 42#include <linux/squashfs_fs_i.h> 43 44#include "squashfs.h" 45 46struct squashfs_cache_entry *squashfs_cache_get(struct super_block *s, 47 struct squashfs_cache *cache, long long block, int length) 48{ 49 int i, n; 50 struct squashfs_cache_entry *entry; 51 52 spin_lock(&cache->lock); 53 54 while (1) { 55 for (i = 0; i < cache->entries; i++) 56 if (cache->entry[i].block == block) 57 break; 58 59 if (i == cache->entries) { 60 /* Block not in cache, if all cache entries are locked 61 * go to sleep waiting for one to become available */ 62 if (cache->unused == 0) { 63 cache->waiting++; 64 spin_unlock(&cache->lock); 65 wait_event(cache->wait_queue, cache->unused); 66 spin_lock(&cache->lock); 67 cache->waiting--; 68 continue; 69 } 70 71 /* At least one unlocked cache entry. A simple 72 * round-robin strategy is used to choose the entry to 73 * be evicted from the cache */ 74 i = cache->next_blk; 75 for (n = 0; n < cache->entries; n++) { 76 if (cache->entry[i].locked == 0) 77 break; 78 i = (i + 1) % cache->entries; 79 } 80 81 cache->next_blk = (i + 1) % cache->entries; 82 entry = &cache->entry[i]; 83 84 /* Initialise choosen cache entry, and fill it in from 85 * disk. */ 86 cache->unused--; 87 entry->block = block; 88 entry->locked = 1; 89 entry->pending = 1; 90 entry->waiting = 0; 91 entry->error = 0; 92 spin_unlock(&cache->lock); 93 94 entry->length = squashfs_read_data(s, entry->data, 95 block, length, &entry->next_index, 96 cache->block_size); 97 98 spin_lock(&cache->lock); 99 100 if (entry->length == 0) 101 entry->error = 1; 102 103 entry->pending = 0; 104 spin_unlock(&cache->lock); 105 106 /* While filling this entry one or more other processes 107 * have looked it up in the cache, and have slept 108 * waiting for it to become available */ 109 if (entry->waiting) 110 wake_up_all(&entry->wait_queue); 111 goto out; 112 } 113 114 /* Block already in cache. Increment lock so it doesn't 115 * get reused until we're finished with it, if it was 116 * previously unlocked there's one less cache entry available 117 * for reuse */ 118 entry = &cache->entry[i]; 119 if (entry->locked == 0) 120 cache->unused--; 121 entry->locked++; 122 123 /* If the entry is currently being filled in by another process 124 * go to sleep waiting for it to become available */ 125 if (entry->pending) { 126 entry->waiting++; 127 spin_unlock(&cache->lock); 128 wait_event(entry->wait_queue, !entry->pending); 129 goto out; 130 } 131 132 spin_unlock(&cache->lock); 133 goto out; 134 } 135 136out: 137 TRACE("Got %s %d, start block %lld, locked %d, error %d\n", cache->name, 138 i, entry->block, entry->locked, entry->error); 139 140 if (entry->error) 141 ERROR("Unable to read %s cache entry [%llx]\n", cache->name, 142 block); 143 return entry; 144} 145 146 147void squashfs_cache_put(struct squashfs_cache *cache, 148 struct squashfs_cache_entry *entry) 149{ 150 spin_lock(&cache->lock); 151 entry->locked--; 152 if (entry->locked == 0) { 153 cache->unused++; 154 spin_unlock(&cache->lock); 155 if (cache->waiting) 156 wake_up(&cache->wait_queue); 157 } else 158 spin_unlock(&cache->lock); 159} 160 161 162void squashfs_cache_delete(struct squashfs_cache *cache) 163{ 164 int i; 165 166 if (cache == NULL) 167 return; 168 169 for (i = 0; i < cache->entries; i++) 170 if (cache->entry[i].data) { 171 if (cache->use_vmalloc) 172 vfree(cache->entry[i].data); 173 else 174 kfree(cache->entry[i].data); 175 } 176 177 kfree(cache); 178} 179 180 181struct squashfs_cache *squashfs_cache_init(char *name, int entries, 182 int block_size, int use_vmalloc) 183{ 184 int i; 185 struct squashfs_cache *cache = kzalloc(sizeof(struct squashfs_cache) + 186 entries * sizeof(struct squashfs_cache_entry), 187 GFP_KERNEL); 188 189 if (cache == NULL) { 190 ERROR("Failed to allocate %s cache\n", name); 191 goto failed; 192 } 193 194 cache->next_blk = 0; 195 cache->unused = entries; 196 cache->entries = entries; 197 cache->block_size = block_size; 198 cache->use_vmalloc = use_vmalloc; 199 cache->name = name; 200 cache->waiting = 0; 201 spin_lock_init(&cache->lock); 202 init_waitqueue_head(&cache->wait_queue); 203 204 for (i = 0; i < entries; i++) { 205 init_waitqueue_head(&cache->entry[i].wait_queue); 206 cache->entry[i].block = SQUASHFS_INVALID_BLK; 207 cache->entry[i].data = use_vmalloc ? vmalloc(block_size) : 208 kmalloc(block_size, GFP_KERNEL); 209 if (cache->entry[i].data == NULL) { 210 ERROR("Failed to allocate %s cache entry\n", name); 211 goto cleanup; 212 } 213 } 214 215 return cache; 216 217cleanup: 218 squashfs_cache_delete(cache); 219failed: 220 return NULL; 221} 222