1 /** 2 * cache.c : deal with LRU caches 3 * 4 * Copyright (c) 2008-2010 Jean-Pierre Andre 5 * 6 * This program/include file is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU General Public License as published 8 * by the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program/include file is distributed in the hope that it will be 12 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program (in the main directory of the NTFS-3G 18 * distribution in the file COPYING); if not, write to the Free Software 19 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21 22 #ifdef HAVE_CONFIG_H 23 #include "config.h" 24 #endif 25 26 #ifdef HAVE_STDLIB_H 27 #include <stdlib.h> 28 #endif 29 #ifdef HAVE_STRING_H 30 #include <string.h> 31 #endif 32 33 #include "types.h" 34 #include "security.h" 35 #include "cache.h" 36 #include "misc.h" 37 #include "logging.h" 38 39 /* 40 * General functions to deal with LRU caches 41 * 42 * The cached data have to be organized in a structure in which 43 * the first fields must follow a mandatory pattern and further 44 * fields may contain any fixed size data. They are stored in an 45 * LRU list. 46 * 47 * A compare function must be provided for finding a wanted entry 48 * in the cache. Another function may be provided for invalidating 49 * an entry to facilitate multiple invalidation. 50 * 51 * These functions never return error codes. When there is a 52 * shortage of memory, data is simply not cached. 53 * When there is a hashing bug, hashing is dropped, and sequential 54 * searches are used. 55 */ 56 57 /* 58 * Enter a new hash index, after a new record has been inserted 59 * 60 * Do not call when a record has been modified (with no key change) 61 */ 62 63 static void inserthashindex(struct CACHE_HEADER *cache, 64 struct CACHED_GENERIC *current) 65 { 66 int h; 67 struct HASH_ENTRY *link; 68 struct HASH_ENTRY *first; 69 70 if (cache->dohash) { 71 h = cache->dohash(current); 72 if ((h >= 0) && (h < cache->max_hash)) { 73 /* get a free link and insert at top of hash list */ 74 link = cache->free_hash; 75 if (link) { 76 cache->free_hash = link->next; 77 first = cache->first_hash[h]; 78 if (first) 79 link->next = first; 80 else 81 link->next = NULL; 82 link->entry = current; 83 cache->first_hash[h] = link; 84 } else { 85 ntfs_log_error("No more hash entries," 86 " cache %s hashing dropped\n", 87 cache->name); 88 cache->dohash = (cache_hash)NULL; 89 } 90 } else { 91 ntfs_log_error("Illegal hash value," 92 " cache %s hashing dropped\n", 93 cache->name); 94 cache->dohash = (cache_hash)NULL; 95 } 96 } 97 } 98 99 /* 100 * Drop a hash index when a record is about to be deleted 101 */ 102 103 static void drophashindex(struct CACHE_HEADER *cache, 104 const struct CACHED_GENERIC *current, int hash) 105 { 106 struct HASH_ENTRY *link; 107 struct HASH_ENTRY *previous; 108 109 if (cache->dohash) { 110 if ((hash >= 0) && (hash < cache->max_hash)) { 111 /* find the link and unlink */ 112 link = cache->first_hash[hash]; 113 previous = (struct HASH_ENTRY*)NULL; 114 while (link && (link->entry != current)) { 115 previous = link; 116 link = link->next; 117 } 118 if (link) { 119 if (previous) 120 previous->next = link->next; 121 else 122 cache->first_hash[hash] = link->next; 123 link->next = cache->free_hash; 124 cache->free_hash = link; 125 } else { 126 ntfs_log_error("Bad hash list," 127 " cache %s hashing dropped\n", 128 cache->name); 129 cache->dohash = (cache_hash)NULL; 130 } 131 } else { 132 ntfs_log_error("Illegal hash value," 133 " cache %s hashing dropped\n", 134 cache->name); 135 cache->dohash = (cache_hash)NULL; 136 } 137 } 138 } 139 140 /* 141 * Fetch an entry from cache 142 * 143 * returns the cache entry, or NULL if not available 144 * The returned entry may be modified, but not freed 145 */ 146 147 struct CACHED_GENERIC *ntfs_fetch_cache(struct CACHE_HEADER *cache, 148 const struct CACHED_GENERIC *wanted, cache_compare compare) 149 { 150 struct CACHED_GENERIC *current; 151 struct CACHED_GENERIC *previous; 152 struct HASH_ENTRY *link; 153 int h; 154 155 current = (struct CACHED_GENERIC*)NULL; 156 if (cache) { 157 if (cache->dohash) { 158 /* 159 * When possible, use the hash table to 160 * locate the entry if present 161 */ 162 h = cache->dohash(wanted); 163 link = cache->first_hash[h]; 164 while (link && compare(link->entry, wanted)) 165 link = link->next; 166 if (link) 167 current = link->entry; 168 } 169 if (!cache->dohash) { 170 /* 171 * Search sequentially in LRU list if no hash table 172 * or if hashing has just failed 173 */ 174 current = cache->most_recent_entry; 175 while (current 176 && compare(current, wanted)) { 177 current = current->next; 178 } 179 } 180 if (current) { 181 previous = current->previous; 182 cache->hits++; 183 if (previous) { 184 /* 185 * found and not at head of list, unlink from current 186 * position and relink as head of list 187 */ 188 previous->next = current->next; 189 if (current->next) 190 current->next->previous 191 = current->previous; 192 else 193 cache->oldest_entry 194 = current->previous; 195 current->next = cache->most_recent_entry; 196 current->previous 197 = (struct CACHED_GENERIC*)NULL; 198 cache->most_recent_entry->previous = current; 199 cache->most_recent_entry = current; 200 } 201 } 202 cache->reads++; 203 } 204 return (current); 205 } 206 207 /* 208 * Enter an inode number into cache 209 * returns the cache entry or NULL if not possible 210 */ 211 212 struct CACHED_GENERIC *ntfs_enter_cache(struct CACHE_HEADER *cache, 213 const struct CACHED_GENERIC *item, 214 cache_compare compare) 215 { 216 struct CACHED_GENERIC *current; 217 struct CACHED_GENERIC *before; 218 struct HASH_ENTRY *link; 219 int h; 220 221 current = (struct CACHED_GENERIC*)NULL; 222 if (cache) { 223 if (cache->dohash) { 224 /* 225 * When possible, use the hash table to 226 * find out whether the entry if present 227 */ 228 h = cache->dohash(item); 229 link = cache->first_hash[h]; 230 while (link && compare(link->entry, item)) 231 link = link->next; 232 if (link) { 233 current = link->entry; 234 } 235 } 236 if (!cache->dohash) { 237 /* 238 * Search sequentially in LRU list to locate the end, 239 * and find out whether the entry is already in list 240 * As we normally go to the end, no statistics is 241 * kept. 242 */ 243 current = cache->most_recent_entry; 244 while (current 245 && compare(current, item)) { 246 current = current->next; 247 } 248 } 249 250 if (!current) { 251 /* 252 * Not in list, get a free entry or reuse the 253 * last entry, and relink as head of list 254 * Note : we assume at least three entries, so 255 * before, previous and first are different when 256 * an entry is reused. 257 */ 258 259 if (cache->free_entry) { 260 current = cache->free_entry; 261 cache->free_entry = cache->free_entry->next; 262 if (item->varsize) { 263 current->variable = ntfs_malloc( 264 item->varsize); 265 } else 266 current->variable = (void*)NULL; 267 current->varsize = item->varsize; 268 if (!cache->oldest_entry) 269 cache->oldest_entry = current; 270 } else { 271 /* reusing the oldest entry */ 272 current = cache->oldest_entry; 273 before = current->previous; 274 before->next = (struct CACHED_GENERIC*)NULL; 275 if (cache->dohash) 276 drophashindex(cache,current, 277 cache->dohash(current)); 278 if (cache->dofree) 279 cache->dofree(current); 280 cache->oldest_entry = current->previous; 281 if (item->varsize) { 282 if (current->varsize) 283 current->variable = realloc( 284 current->variable, 285 item->varsize); 286 else 287 current->variable = ntfs_malloc( 288 item->varsize); 289 } else { 290 if (current->varsize) 291 free(current->variable); 292 current->variable = (void*)NULL; 293 } 294 current->varsize = item->varsize; 295 } 296 current->next = cache->most_recent_entry; 297 current->previous = (struct CACHED_GENERIC*)NULL; 298 if (cache->most_recent_entry) 299 cache->most_recent_entry->previous = current; 300 cache->most_recent_entry = current; 301 memcpy(current->payload, item->payload, cache->fixed_size); 302 if (item->varsize) { 303 if (current->variable) { 304 memcpy(current->variable, 305 item->variable, item->varsize); 306 } else { 307 /* 308 * no more memory for variable part 309 * recycle entry in free list 310 * not an error, just uncacheable 311 */ 312 cache->most_recent_entry = current->next; 313 current->next = cache->free_entry; 314 cache->free_entry = current; 315 current = (struct CACHED_GENERIC*)NULL; 316 } 317 } else { 318 current->variable = (void*)NULL; 319 current->varsize = 0; 320 } 321 if (cache->dohash && current) 322 inserthashindex(cache,current); 323 } 324 cache->writes++; 325 } 326 return (current); 327 } 328 329 /* 330 * Invalidate a cache entry 331 * The entry is moved to the free entry list 332 * A specific function may be called for entry deletion 333 */ 334 335 static void do_invalidate(struct CACHE_HEADER *cache, 336 struct CACHED_GENERIC *current, int flags) 337 { 338 struct CACHED_GENERIC *previous; 339 340 previous = current->previous; 341 if ((flags & CACHE_FREE) && cache->dofree) 342 cache->dofree(current); 343 /* 344 * Relink into free list 345 */ 346 if (current->next) 347 current->next->previous = current->previous; 348 else 349 cache->oldest_entry = current->previous; 350 if (previous) 351 previous->next = current->next; 352 else 353 cache->most_recent_entry = current->next; 354 current->next = cache->free_entry; 355 cache->free_entry = current; 356 if (current->variable) 357 free(current->variable); 358 current->varsize = 0; 359 } 360 361 362 /* 363 * Invalidate entries in cache 364 * 365 * Several entries may have to be invalidated (at least for inodes 366 * associated to directories which have been renamed), a different 367 * compare function may be provided to select entries to invalidate 368 * 369 * Returns the number of deleted entries, this can be used by 370 * the caller to signal a cache corruption if the entry was 371 * supposed to be found. 372 */ 373 374 int ntfs_invalidate_cache(struct CACHE_HEADER *cache, 375 const struct CACHED_GENERIC *item, cache_compare compare, 376 int flags) 377 { 378 struct CACHED_GENERIC *current; 379 struct CACHED_GENERIC *next; 380 struct HASH_ENTRY *link; 381 int count; 382 int h; 383 384 current = (struct CACHED_GENERIC*)NULL; 385 count = 0; 386 if (cache) { 387 if (!(flags & CACHE_NOHASH) && cache->dohash) { 388 /* 389 * When possible, use the hash table to 390 * find out whether the entry if present 391 */ 392 h = cache->dohash(item); 393 link = cache->first_hash[h]; 394 while (link) { 395 if (compare(link->entry, item)) 396 link = link->next; 397 else { 398 current = link->entry; 399 link = link->next; 400 if (current) { 401 drophashindex(cache,current,h); 402 do_invalidate(cache, 403 current,flags); 404 count++; 405 } 406 } 407 } 408 } 409 if ((flags & CACHE_NOHASH) || !cache->dohash) { 410 /* 411 * Search sequentially in LRU list 412 */ 413 current = cache->most_recent_entry; 414 while (current) { 415 if (!compare(current, item)) { 416 next = current->next; 417 if (cache->dohash) 418 drophashindex(cache,current, 419 cache->dohash(current)); 420 do_invalidate(cache,current,flags); 421 current = next; 422 count++; 423 } else { 424 current = current->next; 425 } 426 } 427 } 428 } 429 return (count); 430 } 431 432 int ntfs_remove_cache(struct CACHE_HEADER *cache, 433 struct CACHED_GENERIC *item, int flags) 434 { 435 int count; 436 437 count = 0; 438 if (cache) { 439 if (cache->dohash) 440 drophashindex(cache,item,cache->dohash(item)); 441 do_invalidate(cache,item,flags); 442 count++; 443 } 444 return (count); 445 } 446 447 /* 448 * Free memory allocated to a cache 449 */ 450 451 static void ntfs_free_cache(struct CACHE_HEADER *cache) 452 { 453 struct CACHED_GENERIC *entry; 454 455 if (cache) { 456 for (entry=cache->most_recent_entry; entry; entry=entry->next) { 457 if (cache->dofree) 458 cache->dofree(entry); 459 if (entry->variable) 460 free(entry->variable); 461 } 462 free(cache); 463 } 464 } 465 466 /* 467 * Create a cache 468 * 469 * Returns the cache header, or NULL if the cache could not be created 470 */ 471 472 static struct CACHE_HEADER *ntfs_create_cache(const char *name, 473 cache_free dofree, cache_hash dohash, 474 int full_item_size, 475 int item_count, int max_hash) 476 { 477 struct CACHE_HEADER *cache; 478 struct CACHED_GENERIC *pc; 479 struct CACHED_GENERIC *qc; 480 struct HASH_ENTRY *ph; 481 struct HASH_ENTRY *qh; 482 struct HASH_ENTRY **px; 483 size_t size; 484 int i; 485 486 size = sizeof(struct CACHE_HEADER) + item_count*full_item_size; 487 if (max_hash) 488 size += item_count*sizeof(struct HASH_ENTRY) 489 + max_hash*sizeof(struct HASH_ENTRY*); 490 cache = (struct CACHE_HEADER*)ntfs_malloc(size); 491 if (cache) { 492 /* header */ 493 cache->name = name; 494 cache->dofree = dofree; 495 if (dohash && max_hash) { 496 cache->dohash = dohash; 497 cache->max_hash = max_hash; 498 } else { 499 cache->dohash = (cache_hash)NULL; 500 cache->max_hash = 0; 501 } 502 cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC); 503 cache->reads = 0; 504 cache->writes = 0; 505 cache->hits = 0; 506 /* chain the data entries, and mark an invalid entry */ 507 cache->most_recent_entry = (struct CACHED_GENERIC*)NULL; 508 cache->oldest_entry = (struct CACHED_GENERIC*)NULL; 509 cache->free_entry = &cache->entry[0]; 510 pc = &cache->entry[0]; 511 for (i=0; i<(item_count - 1); i++) { 512 qc = (struct CACHED_GENERIC*)((char*)pc 513 + full_item_size); 514 pc->next = qc; 515 pc->variable = (void*)NULL; 516 pc->varsize = 0; 517 pc = qc; 518 } 519 /* special for the last entry */ 520 pc->next = (struct CACHED_GENERIC*)NULL; 521 pc->variable = (void*)NULL; 522 pc->varsize = 0; 523 524 if (max_hash) { 525 /* chain the hash entries */ 526 ph = (struct HASH_ENTRY*)(((char*)pc) + full_item_size); 527 cache->free_hash = ph; 528 for (i=0; i<(item_count - 1); i++) { 529 qh = &ph[1]; 530 ph->next = qh; 531 ph = qh; 532 } 533 /* special for the last entry */ 534 if (item_count) { 535 ph->next = (struct HASH_ENTRY*)NULL; 536 } 537 /* create and initialize the hash indexes */ 538 px = (struct HASH_ENTRY**)&ph[1]; 539 cache->first_hash = px; 540 for (i=0; i<max_hash; i++) 541 px[i] = (struct HASH_ENTRY*)NULL; 542 } else { 543 cache->free_hash = (struct HASH_ENTRY*)NULL; 544 cache->first_hash = (struct HASH_ENTRY**)NULL; 545 } 546 } 547 return (cache); 548 } 549 550 /* 551 * Create all LRU caches 552 * 553 * No error return, if creation is not possible, cacheing will 554 * just be not available 555 */ 556 557 void ntfs_create_lru_caches(ntfs_volume *vol) 558 { 559 #if CACHE_INODE_SIZE 560 /* inode cache */ 561 vol->xinode_cache = ntfs_create_cache("inode",(cache_free)NULL, 562 ntfs_dir_inode_hash, sizeof(struct CACHED_INODE), 563 CACHE_INODE_SIZE, 2*CACHE_INODE_SIZE); 564 #endif 565 #if CACHE_NIDATA_SIZE 566 /* idata cache */ 567 vol->nidata_cache = ntfs_create_cache("nidata", 568 ntfs_inode_nidata_free, ntfs_inode_nidata_hash, 569 sizeof(struct CACHED_NIDATA), 570 CACHE_NIDATA_SIZE, 2*CACHE_NIDATA_SIZE); 571 #endif 572 #if CACHE_LOOKUP_SIZE 573 /* lookup cache */ 574 vol->lookup_cache = ntfs_create_cache("lookup", 575 (cache_free)NULL, ntfs_dir_lookup_hash, 576 sizeof(struct CACHED_LOOKUP), 577 CACHE_LOOKUP_SIZE, 2*CACHE_LOOKUP_SIZE); 578 #endif 579 vol->securid_cache = ntfs_create_cache("securid",(cache_free)NULL, 580 (cache_hash)NULL,sizeof(struct CACHED_SECURID), CACHE_SECURID_SIZE, 0); 581 #if CACHE_LEGACY_SIZE 582 vol->legacy_cache = ntfs_create_cache("legacy",(cache_free)NULL, 583 (cache_hash)NULL, sizeof(struct CACHED_PERMISSIONS_LEGACY), CACHE_LEGACY_SIZE, 0); 584 #endif 585 } 586 587 /* 588 * Free all LRU caches 589 */ 590 591 void ntfs_free_lru_caches(ntfs_volume *vol) 592 { 593 #if CACHE_INODE_SIZE 594 ntfs_free_cache(vol->xinode_cache); 595 #endif 596 #if CACHE_NIDATA_SIZE 597 ntfs_free_cache(vol->nidata_cache); 598 #endif 599 #if CACHE_LOOKUP_SIZE 600 ntfs_free_cache(vol->lookup_cache); 601 #endif 602 ntfs_free_cache(vol->securid_cache); 603 #if CACHE_LEGACY_SIZE 604 ntfs_free_cache(vol->legacy_cache); 605 #endif 606 } 607