git.maemo.org Git - busybox4maemo/blob - e2fsprogs/old_e2fsprogs/ext2fs/icount.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * icount.c --- an efficient inode count abstraction
   4  *
   5  * Copyright (C) 1997 Theodore Ts'o.
   6  *
   7  * %Begin-Header%
   8  * This file may be redistributed under the terms of the GNU Public
   9  * License.
  10  * %End-Header%
  11  */
  12
  13 #if HAVE_UNISTD_H
  14 #include <unistd.h>
  15 #endif
  16 #include <string.h>
  17 #include <stdio.h>
  18
  19 #include "ext2_fs.h"
  20 #include "ext2fs.h"
  21
  22 /*
  23  * The data storage strategy used by icount relies on the observation
  24  * that most inode counts are either zero (for non-allocated inodes),
  25  * one (for most files), and only a few that are two or more
  26  * (directories and files that are linked to more than one directory).
  27  *
  28  * Also, e2fsck tends to load the icount data sequentially.
  29  *
  30  * So, we use an inode bitmap to indicate which inodes have a count of
  31  * one, and then use a sorted list to store the counts for inodes
  32  * which are greater than one.
  33  *
  34  * We also use an optional bitmap to indicate which inodes are already
  35  * in the sorted list, to speed up the use of this abstraction by
  36  * e2fsck's pass 2.  Pass 2 increments inode counts as it finds them,
  37  * so this extra bitmap avoids searching the sorted list to see if a
  38  * particular inode is on the sorted list already.
  39  */
  40
  41 struct ext2_icount_el {
  42         ext2_ino_t      ino;
  43         __u16   count;
  44 };
  45
  46 struct ext2_icount {
  47         errcode_t               magic;
  48         ext2fs_inode_bitmap     single;
  49         ext2fs_inode_bitmap     multiple;
  50         ext2_ino_t              count;
  51         ext2_ino_t              size;
  52         ext2_ino_t              num_inodes;
  53         ext2_ino_t              cursor;
  54         struct ext2_icount_el   *list;
  55 };
  56
  57 void ext2fs_free_icount(ext2_icount_t icount)
  58 {
  59         if (!icount)
  60                 return;
  61
  62         icount->magic = 0;
  63         ext2fs_free_mem(&icount->list);
  64         ext2fs_free_inode_bitmap(icount->single);
  65         ext2fs_free_inode_bitmap(icount->multiple);
  66         ext2fs_free_mem(&icount);
  67 }
  68
  69 errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
  70                                 ext2_icount_t hint, ext2_icount_t *ret)
  71 {
  72         ext2_icount_t   icount;
  73         errcode_t       retval;
  74         size_t          bytes;
  75         ext2_ino_t      i;
  76
  77         if (hint) {
  78                 EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
  79                 if (hint->size > size)
  80                         size = (size_t) hint->size;
  81         }
  82
  83         retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
  84         if (retval)
  85                 return retval;
  86         memset(icount, 0, sizeof(struct ext2_icount));
  87
  88         retval = ext2fs_allocate_inode_bitmap(fs, 0,
  89                                               &icount->single);
  90         if (retval)
  91                 goto errout;
  92
  93         if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
  94                 retval = ext2fs_allocate_inode_bitmap(fs, 0,
  95                                                       &icount->multiple);
  96                 if (retval)
  97                         goto errout;
  98         } else
  99                 icount->multiple = 0;
 100
 101         if (size) {
 102                 icount->size = size;
 103         } else {
 104                 /*
 105                  * Figure out how many special case inode counts we will
 106                  * have.  We know we will need one for each directory;
 107                  * we also need to reserve some extra room for file links
 108                  */
 109                 retval = ext2fs_get_num_dirs(fs, &icount->size);
 110                 if (retval)
 111                         goto errout;
 112                 icount->size += fs->super->s_inodes_count / 50;
 113         }
 114
 115         bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
 116         retval = ext2fs_get_mem(bytes, &icount->list);
 117         if (retval)
 118                 goto errout;
 119         memset(icount->list, 0, bytes);
 120
 121         icount->magic = EXT2_ET_MAGIC_ICOUNT;
 122         icount->count = 0;
 123         icount->cursor = 0;
 124         icount->num_inodes = fs->super->s_inodes_count;
 125
 126         /*
 127          * Populate the sorted list with those entries which were
 128          * found in the hint icount (since those are ones which will
 129          * likely need to be in the sorted list this time around).
 130          */
 131         if (hint) {
 132                 for (i=0; i < hint->count; i++)
 133                         icount->list[i].ino = hint->list[i].ino;
 134                 icount->count = hint->count;
 135         }
 136
 137         *ret = icount;
 138         return 0;
 139
 140 errout:
 141         ext2fs_free_icount(icount);
 142         return retval;
 143 }
 144
 145 errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
 146                                unsigned int size,
 147                                ext2_icount_t *ret)
 148 {
 149         return ext2fs_create_icount2(fs, flags, size, 0, ret);
 150 }
 151
 152 /*
 153  * insert_icount_el() --- Insert a new entry into the sorted list at a
 154  *      specified position.
 155  */
 156 static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
 157                                             ext2_ino_t ino, int pos)
 158 {
 159         struct ext2_icount_el   *el;
 160         errcode_t               retval;
 161         ext2_ino_t                      new_size = 0;
 162         int                     num;
 163
 164         if (icount->count >= icount->size) {
 165                 if (icount->count) {
 166                         new_size = icount->list[(unsigned)icount->count-1].ino;
 167                         new_size = (ext2_ino_t) (icount->count *
 168                                 ((float) icount->num_inodes / new_size));
 169                 }
 170                 if (new_size < (icount->size + 100))
 171                         new_size = icount->size + 100;
 172                 retval = ext2fs_resize_mem((size_t) icount->size *
 173                                            sizeof(struct ext2_icount_el),
 174                                            (size_t) new_size *
 175                                            sizeof(struct ext2_icount_el),
 176                                            &icount->list);
 177                 if (retval)
 178                         return 0;
 179                 icount->size = new_size;
 180         }
 181         num = (int) icount->count - pos;
 182         if (num < 0)
 183                 return 0;       /* should never happen */
 184         if (num) {
 185                 memmove(&icount->list[pos+1], &icount->list[pos],
 186                         sizeof(struct ext2_icount_el) * num);
 187         }
 188         icount->count++;
 189         el = &icount->list[pos];
 190         el->count = 0;
 191         el->ino = ino;
 192         return el;
 193 }
 194
 195 /*
 196  * get_icount_el() --- given an inode number, try to find icount
 197  *      information in the sorted list.  If the create flag is set,
 198  *      and we can't find an entry, create one in the sorted list.
 199  */
 200 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
 201                                             ext2_ino_t ino, int create)
 202 {
 203         float   range;
 204         int     low, high, mid;
 205         ext2_ino_t      lowval, highval;
 206
 207         if (!icount || !icount->list)
 208                 return 0;
 209
 210         if (create && ((icount->count == 0) ||
 211                        (ino > icount->list[(unsigned)icount->count-1].ino))) {
 212                 return insert_icount_el(icount, ino, (unsigned) icount->count);
 213         }
 214         if (icount->count == 0)
 215                 return 0;
 216
 217         if (icount->cursor >= icount->count)
 218                 icount->cursor = 0;
 219         if (ino == icount->list[icount->cursor].ino)
 220                 return &icount->list[icount->cursor++];
 221         low = 0;
 222         high = (int) icount->count-1;
 223         while (low <= high) {
 224                 if (low == high)
 225                         mid = low;
 226                 else {
 227                         /* Interpolate for efficiency */
 228                         lowval = icount->list[low].ino;
 229                         highval = icount->list[high].ino;
 230
 231                         if (ino < lowval)
 232                                 range = 0;
 233                         else if (ino > highval)
 234                                 range = 1;
 235                         else
 236                                 range = ((float) (ino - lowval)) /
 237                                         (highval - lowval);
 238                         mid = low + ((int) (range * (high-low)));
 239                 }
 240                 if (ino == icount->list[mid].ino) {
 241                         icount->cursor = mid+1;
 242                         return &icount->list[mid];
 243                 }
 244                 if (ino < icount->list[mid].ino)
 245                         high = mid-1;
 246                 else
 247                         low = mid+1;
 248         }
 249         /*
 250          * If we need to create a new entry, it should be right at
 251          * low (where high will be left at low-1).
 252          */
 253         if (create)
 254                 return insert_icount_el(icount, ino, low);
 255         return 0;
 256 }
 257
 258 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
 259 {
 260         errcode_t       ret = 0;
 261         unsigned int    i;
 262         const char *bad = "bad icount";
 263
 264         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 265
 266         if (icount->count > icount->size) {
 267                 fprintf(out, "%s: count > size\n", bad);
 268                 return EXT2_ET_INVALID_ARGUMENT;
 269         }
 270         for (i=1; i < icount->count; i++) {
 271                 if (icount->list[i-1].ino >= icount->list[i].ino) {
 272                         fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
 273                                 bad, i-1, icount->list[i-1].ino,
 274                                 i, icount->list[i].ino);
 275                         ret = EXT2_ET_INVALID_ARGUMENT;
 276                 }
 277         }
 278         return ret;
 279 }
 280
 281 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
 282 {
 283         struct ext2_icount_el   *el;
 284
 285         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 286
 287         if (!ino || (ino > icount->num_inodes))
 288                 return EXT2_ET_INVALID_ARGUMENT;
 289
 290         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 291                 *ret = 1;
 292                 return 0;
 293         }
 294         if (icount->multiple &&
 295             !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 296                 *ret = 0;
 297                 return 0;
 298         }
 299         el = get_icount_el(icount, ino, 0);
 300         if (!el) {
 301                 *ret = 0;
 302                 return 0;
 303         }
 304         *ret = el->count;
 305         return 0;
 306 }
 307
 308 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
 309                                   __u16 *ret)
 310 {
 311         struct ext2_icount_el   *el;
 312
 313         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 314
 315         if (!ino || (ino > icount->num_inodes))
 316                 return EXT2_ET_INVALID_ARGUMENT;
 317
 318         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 319                 /*
 320                  * If the existing count is 1, then we know there is
 321                  * no entry in the list.
 322                  */
 323                 el = get_icount_el(icount, ino, 1);
 324                 if (!el)
 325                         return EXT2_ET_NO_MEMORY;
 326                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 327                 el->count = 2;
 328         } else if (icount->multiple) {
 329                 /*
 330                  * The count is either zero or greater than 1; if the
 331                  * inode is set in icount->multiple, then there should
 332                  * be an entry in the list, so find it using
 333                  * get_icount_el().
 334                  */
 335                 if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 336                         el = get_icount_el(icount, ino, 1);
 337                         if (!el)
 338                                 return EXT2_ET_NO_MEMORY;
 339                         el->count++;
 340                 } else {
 341                         /*
 342                          * The count was zero; mark the single bitmap
 343                          * and return.
 344                          */
 345                 zero_count:
 346                         ext2fs_mark_inode_bitmap(icount->single, ino);
 347                         if (ret)
 348                                 *ret = 1;
 349                         return 0;
 350                 }
 351         } else {
 352                 /*
 353                  * The count is either zero or greater than 1; try to
 354                  * find an entry in the list to determine which.
 355                  */
 356                 el = get_icount_el(icount, ino, 0);
 357                 if (!el) {
 358                         /* No entry means the count was zero */
 359                         goto zero_count;
 360                 }
 361                 el = get_icount_el(icount, ino, 1);
 362                 if (!el)
 363                         return EXT2_ET_NO_MEMORY;
 364                 el->count++;
 365         }
 366         if (icount->multiple)
 367                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 368         if (ret)
 369                 *ret = el->count;
 370         return 0;
 371 }
 372
 373 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
 374                                   __u16 *ret)
 375 {
 376         struct ext2_icount_el   *el;
 377
 378         if (!ino || (ino > icount->num_inodes))
 379                 return EXT2_ET_INVALID_ARGUMENT;
 380
 381         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 382
 383         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 384                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 385                 if (icount->multiple)
 386                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 387                 else {
 388                         el = get_icount_el(icount, ino, 0);
 389                         if (el)
 390                                 el->count = 0;
 391                 }
 392                 if (ret)
 393                         *ret = 0;
 394                 return 0;
 395         }
 396
 397         if (icount->multiple &&
 398             !ext2fs_test_inode_bitmap(icount->multiple, ino))
 399                 return EXT2_ET_INVALID_ARGUMENT;
 400
 401         el = get_icount_el(icount, ino, 0);
 402         if (!el || el->count == 0)
 403                 return EXT2_ET_INVALID_ARGUMENT;
 404
 405         el->count--;
 406         if (el->count == 1)
 407                 ext2fs_mark_inode_bitmap(icount->single, ino);
 408         if ((el->count == 0) && icount->multiple)
 409                 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 410
 411         if (ret)
 412                 *ret = el->count;
 413         return 0;
 414 }
 415
 416 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
 417                               __u16 count)
 418 {
 419         struct ext2_icount_el   *el;
 420
 421         if (!ino || (ino > icount->num_inodes))
 422                 return EXT2_ET_INVALID_ARGUMENT;
 423
 424         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 425
 426         if (count == 1) {
 427                 ext2fs_mark_inode_bitmap(icount->single, ino);
 428                 if (icount->multiple)
 429                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 430                 return 0;
 431         }
 432         if (count == 0) {
 433                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 434                 if (icount->multiple) {
 435                         /*
 436                          * If the icount->multiple bitmap is enabled,
 437                          * we can just clear both bitmaps and we're done
 438                          */
 439                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 440                 } else {
 441                         el = get_icount_el(icount, ino, 0);
 442                         if (el)
 443                                 el->count = 0;
 444                 }
 445                 return 0;
 446         }
 447
 448         /*
 449          * Get the icount element
 450          */
 451         el = get_icount_el(icount, ino, 1);
 452         if (!el)
 453                 return EXT2_ET_NO_MEMORY;
 454         el->count = count;
 455         ext2fs_unmark_inode_bitmap(icount->single, ino);
 456         if (icount->multiple)
 457                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 458         return 0;
 459 }
 460
 461 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
 462 {
 463         if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
 464                 return 0;
 465
 466         return icount->size;
 467 }