release/src/router/ntfs-3g/libntfs-3g/cache.c

   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 }