1 /** 2 * cache.c : deal with LRU caches 3 * 4 * Copyright (c) 2008-2009 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->fixed, item->fixed, 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 *previous; 380 struct CACHED_GENERIC *next; 381 struct HASH_ENTRY *link; 382 int count; 383 int h; 384 385 current = (struct CACHED_GENERIC*)NULL; 386 count = 0; 387 if (cache) { 388 if (!(flags & CACHE_NOHASH) && cache->dohash) { 389 /* 390 * When possible, use the hash table to 391 * find out whether the entry if present 392 */ 393 h = cache->dohash(item); 394 link = cache->first_hash[h]; 395 while (link) { 396 if (compare(link->entry, item)) 397 link = link->next; 398 else { 399 current = link->entry; 400 link = link->next; 401 if (current) { 402 drophashindex(cache,current,h); 403 do_invalidate(cache, 404 current,flags); 405 count++; 406 } 407 } 408 } 409 } 410 if ((flags & CACHE_NOHASH) || !cache->dohash) { 411 /* 412 * Search sequentially in LRU list 413 */ 414 current = cache->most_recent_entry; 415 previous = (struct CACHED_GENERIC*)NULL; 416 while (current) { 417 if (!compare(current, item)) { 418 next = current->next; 419 if (cache->dohash) 420 drophashindex(cache,current, 421 cache->dohash(current)); 422 do_invalidate(cache,current,flags); 423 current = next; 424 count++; 425 } else { 426 previous = current; 427 current = current->next; 428 } 429 } 430 } 431 } 432 return (count); 433 } 434 435 int ntfs_remove_cache(struct CACHE_HEADER *cache, 436 struct CACHED_GENERIC *item, int flags) 437 { 438 int count; 439 440 count = 0; 441 if (cache) { 442 if (cache->dohash) 443 drophashindex(cache,item,cache->dohash(item)); 444 do_invalidate(cache,item,flags); 445 count++; 446 } 447 return (count); 448 } 449 450 /* 451 * Free memory allocated to a cache 452 */ 453 454 static void ntfs_free_cache(struct CACHE_HEADER *cache) 455 { 456 struct CACHED_GENERIC *entry; 457 458 if (cache) { 459 for (entry=cache->most_recent_entry; entry; entry=entry->next) { 460 if (cache->dofree) 461 cache->dofree(entry); 462 if (entry->variable) 463 free(entry->variable); 464 } 465 free(cache); 466 } 467 } 468 469 /* 470 * Create a cache 471 * 472 * Returns the cache header, or NULL if the cache could not be created 473 */ 474 475 static struct CACHE_HEADER *ntfs_create_cache(const char *name, 476 cache_free dofree, cache_hash dohash, 477 int full_item_size, 478 int item_count, int max_hash) 479 { 480 struct CACHE_HEADER *cache; 481 struct CACHED_GENERIC *pc; 482 struct CACHED_GENERIC *qc; 483 struct HASH_ENTRY *ph; 484 struct HASH_ENTRY *qh; 485 struct HASH_ENTRY **px; 486 size_t size; 487 int i; 488 489 size = sizeof(struct CACHE_HEADER) + item_count*full_item_size; 490 if (max_hash) 491 size += item_count*sizeof(struct HASH_ENTRY) 492 + max_hash*sizeof(struct HASH_ENTRY*); 493 cache = (struct CACHE_HEADER*)ntfs_malloc(size); 494 if (cache) { 495 /* header */ 496 cache->name = name; 497 cache->dofree = dofree; 498 if (dohash && max_hash) { 499 cache->dohash = dohash; 500 cache->max_hash = max_hash; 501 } else { 502 cache->dohash = (cache_hash)NULL; 503 cache->max_hash = 0; 504 } 505 cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC); 506 cache->reads = 0; 507 cache->writes = 0; 508 cache->hits = 0; 509 /* chain the data entries, and mark an invalid entry */ 510 cache->most_recent_entry = (struct CACHED_GENERIC*)NULL; 511 cache->oldest_entry = (struct CACHED_GENERIC*)NULL; 512 cache->free_entry = &cache->entry[0]; 513 pc = &cache->entry[0]; 514 for (i=0; i<(item_count - 1); i++) { 515 qc = (struct CACHED_GENERIC*)((char*)pc 516 + full_item_size); 517 pc->next = qc; 518 pc->variable = (void*)NULL; 519 pc->varsize = 0; 520 pc = qc; 521 } 522 /* special for the last entry */ 523 pc->next = (struct CACHED_GENERIC*)NULL; 524 pc->variable = (void*)NULL; 525 pc->varsize = 0; 526 527 if (max_hash) { 528 /* chain the hash entries */ 529 ph = (struct HASH_ENTRY*)(((char*)pc) + full_item_size); 530 cache->free_hash = ph; 531 for (i=0; i<(item_count - 1); i++) { 532 qh = &ph[1]; 533 ph->next = qh; 534 ph = qh; 535 } 536 /* special for the last entry */ 537 if (item_count) { 538 ph->next = (struct HASH_ENTRY*)NULL; 539 } 540 /* create and initialize the hash indexes */ 541 px = (struct HASH_ENTRY**)&ph[1]; 542 cache->first_hash = px; 543 for (i=0; i<max_hash; i++) 544 px[i] = (struct HASH_ENTRY*)NULL; 545 } else { 546 cache->free_hash = (struct HASH_ENTRY*)NULL; 547 cache->first_hash = (struct HASH_ENTRY**)NULL; 548 } 549 } 550 return (cache); 551 } 552 553 /* 554 * Create all LRU caches 555 * 556 * No error return, if creation is not possible, cacheing will 557 * just be not available 558 */ 559 560 void ntfs_create_lru_caches(ntfs_volume *vol) 561 { 562 #if CACHE_INODE_SIZE 563 /* inode cache */ 564 vol->xinode_cache = ntfs_create_cache("inode",(cache_free)NULL, 565 ntfs_dir_inode_hash, sizeof(struct CACHED_INODE), 566 CACHE_INODE_SIZE, 2*CACHE_INODE_SIZE); 567 #endif 568 #if CACHE_NIDATA_SIZE 569 /* idata cache */ 570 vol->nidata_cache = ntfs_create_cache("nidata", 571 ntfs_inode_nidata_free, ntfs_inode_nidata_hash, 572 sizeof(struct CACHED_NIDATA), 573 CACHE_NIDATA_SIZE, 2*CACHE_NIDATA_SIZE); 574 #endif 575 #if CACHE_LOOKUP_SIZE 576 /* lookup cache */ 577 vol->lookup_cache = ntfs_create_cache("lookup", 578 (cache_free)NULL, ntfs_dir_lookup_hash, 579 sizeof(struct CACHED_LOOKUP), 580 CACHE_LOOKUP_SIZE, 2*CACHE_LOOKUP_SIZE); 581 #endif 582 vol->securid_cache = ntfs_create_cache("securid",(cache_free)NULL, 583 (cache_hash)NULL,sizeof(struct CACHED_SECURID), CACHE_SECURID_SIZE, 0); 584 #if CACHE_LEGACY_SIZE 585 vol->legacy_cache = ntfs_create_cache("legacy",(cache_free)NULL, 586 (cache_hash)NULL, sizeof(struct CACHED_PERMISSIONS_LEGACY), CACHE_LEGACY_SIZE, 0); 587 #endif 588 } 589 590 /* 591 * Free all LRU caches 592 */ 593 594 void ntfs_free_lru_caches(ntfs_volume *vol) 595 { 596 #if CACHE_INODE_SIZE 597 ntfs_free_cache(vol->xinode_cache); 598 #endif 599 #if CACHE_NIDATA_SIZE 600 ntfs_free_cache(vol->nidata_cache); 601 #endif 602 #if CACHE_LOOKUP_SIZE 603 ntfs_free_cache(vol->lookup_cache); 604 #endif 605 ntfs_free_cache(vol->securid_cache); 606 #if CACHE_LEGACY_SIZE 607 ntfs_free_cache(vol->legacy_cache); 608 #endif 609 } 610