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

   1 /**
   2  * misc.c : miscellaneous :
   3  *              - dealing with errors in memory allocation
   4  *              - data caching
   5  *
   6  * Copyright (c) 2008 Jean-Pierre Andre
   7  *
   8  * This program/include file is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License as published
  10  * by the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program/include file is distributed in the hope that it will be
  14  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  15  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program (in the main directory of the NTFS-3G
  20  * distribution in the file COPYING); if not, write to the Free Software
  21  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include "config.h"
  26 #endif
  27
  28 #ifdef HAVE_STDLIB_H
  29 #include <stdlib.h>
  30 #endif
  31 #ifdef HAVE_STRING_H
  32 #include <string.h>
  33 #endif
  34
  35 #include "types.h"
  36 #include "security.h"
  37 #include "misc.h"
  38 #include "logging.h"
  39
  40 /**
  41  * ntfs_calloc
  42  *
  43  * Return a pointer to the allocated memory or NULL if the request fails.
  44  */
  45 void *ntfs_calloc(size_t size)
  46 {
  47         void *p;
  48
  49         p = calloc(1, size);
  50         if (!p)
  51                 ntfs_log_perror("Failed to calloc %lld bytes", (long long)size);
  52         return p;
  53 }
  54
  55 void *ntfs_malloc(size_t size)
  56 {
  57         void *p;
  58
  59         p = malloc(size);
  60         if (!p)
  61                 ntfs_log_perror("Failed to malloc %lld bytes", (long long)size);
  62         return p;
  63 }
  64
  65 /*
  66  *              General functions to deal with LRU caches
  67  *
  68  *      The cached data have to be organized in a structure in which
  69  *      the first fields must follow a mandatory pattern and further
  70  *      fields may contain any fixed size data. They are stored in an
  71  *      LRU list.
  72  *
  73  *      A compare function must be provided for finding a wanted entry
  74  *      in the cache. Another function may be provided for invalidating
  75  *      an entry to facilitate multiple invalidation.
  76  *
  77  *      These functions never return error codes. When there is a
  78  *      shortage of memory, data is simply not cached.
  79  */
  80
  81 /*
  82  *              Fetch an entry from cache
  83  *
  84  *      returns the cache entry, or NULL if not available
  85  */
  86
  87 struct CACHED_GENERIC *ntfs_fetch_cache(struct CACHE_HEADER *cache,
  88                 const struct CACHED_GENERIC *wanted, cache_compare compare)
  89 {
  90         struct CACHED_GENERIC *current;
  91         struct CACHED_GENERIC *previous;
  92
  93         current = (struct CACHED_GENERIC*)NULL;
  94         if (cache) {
  95                         /*
  96                          * Search sequentially in LRU list
  97                          */
  98                 current = cache->most_recent_entry;
  99                 previous = (struct CACHED_GENERIC*)NULL;
 100                 while (current
 101                            && compare(current, wanted)) {
 102                         previous = current;
 103                         current = current->next;
 104                         }
 105                 if (current)
 106                         cache->hits++;
 107                 if (current && previous) {
 108                         /*
 109                          * found and not at head of list, unlink from current
 110                          * position and relink as head of list
 111                          */
 112                         previous->next = current->next;
 113                         current->next = cache->most_recent_entry;
 114                         cache->most_recent_entry = current;
 115                 }
 116                 cache->reads++;
 117         }
 118         return (current);
 119 }
 120
 121 /*
 122  *              Enter an inode number into cache
 123  *      returns the cache entry or NULL if not possible
 124  */
 125
 126 struct CACHED_GENERIC *ntfs_enter_cache(struct CACHE_HEADER *cache,
 127                         const struct CACHED_GENERIC *item, cache_compare compare)
 128 {
 129         struct CACHED_GENERIC *current;
 130         struct CACHED_GENERIC *previous;
 131         struct CACHED_GENERIC *before;
 132
 133         current = (struct CACHED_GENERIC*)NULL;
 134         if (cache) {
 135
 136                         /*
 137                          * Search sequentially in LRU list to locate the end,
 138                          * and find out whether the entry is already in list
 139                          * As we normally go to the end, no statistics is
 140                          * kept.
 141                          */
 142                 current = cache->most_recent_entry;
 143                 previous = (struct CACHED_GENERIC*)NULL;
 144                 before = (struct CACHED_GENERIC*)NULL;
 145                 while (current
 146                    && compare(current, item)) {
 147                         before = previous;
 148                         previous = current;
 149                         current = current->next;
 150                         }
 151
 152                 if (!current) {
 153                         /*
 154                          * Not in list, get a free entry or reuse the
 155                          * last entry, and relink as head of list
 156                          * Note : we assume at least three entries, so
 157                          * before, previous and first are different when
 158                          * an entry is reused.
 159                          */
 160
 161                         if (cache->free_entry) {
 162                                 current = cache->free_entry;
 163                                 cache->free_entry = cache->free_entry->next;
 164                                 if (item->varsize) {
 165                                         current->variable = ntfs_malloc(
 166                                                 item->varsize);
 167                                 } else
 168                                         current->variable = (void*)NULL;
 169                                 current->varsize = item->varsize;
 170                         } else {
 171                                 before->next = (struct CACHED_GENERIC*)NULL;
 172                                 current = previous;
 173                                 if (item->varsize) {
 174                                         if (current->varsize)
 175                                                 current->variable = realloc(
 176                                                         current->variable,
 177                                                         item->varsize);
 178                                         else
 179                                                 current->variable = ntfs_malloc(
 180                                                         item->varsize);
 181                                 } else {
 182                                         if (current->varsize)
 183                                                 free(current->variable);
 184                                         current->variable = (void*)NULL;
 185                                 }
 186                                 current->varsize = item->varsize;
 187                         }
 188                         current->next = cache->most_recent_entry;
 189                         cache->most_recent_entry = current;
 190                         memcpy(current->fixed, item->fixed, cache->fixed_size);
 191                         if (item->varsize) {
 192                                 if (current->variable) {
 193                                         memcpy(current->variable,
 194                                                 item->variable, item->varsize);
 195                                 } else {
 196                                         /*
 197                                          * no more memory for variable part
 198                                          * recycle entry in free list
 199                                          * not an error, just uncacheable
 200                                          */
 201                                         cache->most_recent_entry = current->next;
 202                                         current->next = cache->free_entry;
 203                                         cache->free_entry = current;
 204                                         current = (struct CACHED_GENERIC*)NULL;
 205                                 }
 206                         } else {
 207                                 current->variable = (void*)NULL;
 208                                 current->varsize = 0;
 209                         }
 210                 }
 211                 cache->writes++;
 212         }
 213         return (current);
 214 }
 215
 216 /*
 217  *              Invalidate entries in cache
 218  *
 219  *      Several entries may have to be invalidated (at least for inodes
 220  *      associated to directories which have been renamed), a different
 221  *      compare function may be provided to select entries to invalidate
 222  *
 223  *      Returns the number of deleted entries, this can be used by
 224  *      the caller to signal a cache corruption if the entry was
 225  *      supposed to be found.
 226  */
 227
 228 int ntfs_invalidate_cache(struct CACHE_HEADER *cache,
 229                 const struct CACHED_GENERIC *item, cache_compare compare)
 230 {
 231         struct CACHED_GENERIC *current;
 232         struct CACHED_GENERIC *previous;
 233         int count;
 234
 235         current = (struct CACHED_GENERIC*)NULL;
 236         count = 0;
 237         if (cache) {
 238                         /*
 239                          * Search sequentially in LRU list
 240                          */
 241                 current = cache->most_recent_entry;
 242                 previous = (struct CACHED_GENERIC*)NULL;
 243                 while (current) {
 244                         if (!compare(current, item)) {
 245                                 /*
 246                                  * Relink into free list
 247                                  */
 248                                 if (previous)
 249                                         previous->next = current->next;
 250                                 else
 251                                         cache->most_recent_entry = current->next;
 252                                 current->next = cache->free_entry;
 253                                 cache->free_entry = current;
 254                                 if (current->variable)
 255                                         free(current->variable);
 256                                 current->varsize = 0;
 257                                 if (previous)
 258                                         current = previous->next;
 259                                 else
 260                                         current = cache->most_recent_entry;
 261                                 count++;
 262                         } else {
 263                                 previous = current;
 264                                 current = current->next;
 265                         }
 266                 }
 267         }
 268         return (count);
 269 }
 270
 271 /*
 272  *              Free memory allocated to a cache
 273  */
 274
 275 static void ntfs_free_cache(struct CACHE_HEADER *cache)
 276 {
 277         struct CACHED_GENERIC *entry;
 278
 279         if (cache) {
 280                 for (entry=cache->most_recent_entry; entry; entry=entry->next)
 281                         if (entry->variable)
 282                                 free(entry->variable);
 283                 free(cache);
 284         }
 285 }
 286
 287 /*
 288  *              Create a cache
 289  *
 290  *      Returns the cache header, or NULL if the cache could not be created
 291  */
 292
 293 static struct CACHE_HEADER *ntfs_create_cache(const char *name,
 294                         int full_item_size, int item_count)
 295 {
 296         struct CACHE_HEADER *cache;
 297         struct CACHED_GENERIC *p;
 298         struct CACHED_GENERIC *q;
 299         int i;
 300
 301         cache = (struct CACHE_HEADER*)
 302                 ntfs_malloc(sizeof(struct CACHE_HEADER)
 303                          + item_count*full_item_size);
 304         if (cache) {
 305                 cache->name = name;
 306                 cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC);
 307                 cache->reads = 0;
 308                 cache->writes = 0;
 309                 cache->hits = 0;
 310                 /* chain the entries, and mark an invalid entry */
 311                 cache->most_recent_entry = (struct CACHED_GENERIC*)NULL;
 312                 cache->free_entry = &cache->entry[0];
 313                 p = &cache->entry[0];
 314                 for (i=0; i<(item_count - 1); i++) {
 315                         q = (struct CACHED_GENERIC*)((char*)p + full_item_size);
 316                         p->next = q;
 317                         p->variable = (void*)NULL;
 318                         p->varsize = 0;
 319                         p = q;
 320                 }
 321                         /* special for the last entry */
 322                 p->next =  (struct CACHED_GENERIC*)NULL;
 323                 p->variable = (void*)NULL;
 324                 p->varsize = 0;
 325         }
 326         return (cache);
 327 }
 328
 329 /*
 330  *              Create all LRU caches
 331  *
 332  *      No error return, if creation is not possible, cacheing will
 333  *      just be not available
 334  */
 335
 336 void ntfs_create_lru_caches(ntfs_volume *vol)
 337 {
 338 #if CACHE_INODE_SIZE
 339                  /* inode cache */
 340         vol->xinode_cache = ntfs_create_cache("inode",
 341                 sizeof(struct CACHED_INODE), CACHE_INODE_SIZE);
 342 #endif
 343         vol->securid_cache = ntfs_create_cache("securid",
 344                 sizeof(struct CACHED_SECURID), CACHE_SECURID_SIZE);
 345 #if CACHE_LEGACY_SIZE
 346         vol->legacy_cache = ntfs_create_cache("legacy",
 347                 sizeof(struct CACHED_PERMISSIONS_LEGACY), CACHE_LEGACY_SIZE);
 348 #endif
 349 }
 350
 351 /*
 352  *              Free all LRU caches
 353  */
 354
 355 void ntfs_free_lru_caches(ntfs_volume *vol)
 356 {
 357 #if CACHE_INODE_SIZE
 358         ntfs_free_cache(vol->xinode_cache);
 359 #endif
 360         ntfs_free_cache(vol->securid_cache);
 361 #if CACHE_LEGACY_SIZE
 362         ntfs_free_cache(vol->legacy_cache);
 363 #endif
 364 }