lib/ext2fs/icount.c

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