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 #if HAVE_UNISTD_H
  13 #include <unistd.h>
  14 #endif
  15 #include <string.h>
  16 #include <stdio.h>
  17
  18 #include "ext2_fs.h"
  19 #include "ext2fs.h"
  20
  21 /*
  22  * The data storage strategy used by icount relies on the observation
  23  * that most inode counts are either zero (for non-allocated inodes),
  24  * one (for most files), and only a few that are two or more
  25  * (directories and files that are linked to more than one directory).
  26  *
  27  * Also, e2fsck tends to load the icount data sequentially.
  28  *
  29  * So, we use an inode bitmap to indicate which inodes have a count of
  30  * one, and then use a sorted list to store the counts for inodes
  31  * which are greater than one.
  32  *
  33  * We also use an optional bitmap to indicate which inodes are already
  34  * in the sorted list, to speed up the use of this abstraction by
  35  * e2fsck's pass 2.  Pass 2 increments inode counts as it finds them,
  36  * so this extra bitmap avoids searching the sorted list to see if a
  37  * particular inode is on the sorted list already.
  38  */
  39
  40 struct ext2_icount_el {
  41         ext2_ino_t      ino;
  42         __u16   count;
  43 };
  44
  45 struct ext2_icount {
  46         errcode_t               magic;
  47         ext2fs_inode_bitmap     single;
  48         ext2fs_inode_bitmap     multiple;
  49         ext2_ino_t              count;
  50         ext2_ino_t              size;
  51         ext2_ino_t              num_inodes;
  52         ext2_ino_t              cursor;
  53         struct ext2_icount_el   *list;
  54 };
  55
  56 void ext2fs_free_icount(ext2_icount_t icount)
  57 {
  58         if (!icount)
  59                 return;
  60
  61         icount->magic = 0;
  62         if (icount->list)
  63                 ext2fs_free_mem(&icount->list);
  64         if (icount->single)
  65                 ext2fs_free_inode_bitmap(icount->single);
  66         if (icount->multiple)
  67                 ext2fs_free_inode_bitmap(icount->multiple);
  68         ext2fs_free_mem(&icount);
  69 }
  70
  71 errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
  72                                 ext2_icount_t hint, ext2_icount_t *ret)
  73 {
  74         ext2_icount_t   icount;
  75         errcode_t       retval;
  76         size_t          bytes;
  77         ext2_ino_t      i;
  78
  79         if (hint) {
  80                 EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
  81                 if (hint->size > size)
  82                         size = (size_t) hint->size;
  83         }
  84
  85         retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
  86         if (retval)
  87                 return retval;
  88         memset(icount, 0, sizeof(struct ext2_icount));
  89
  90         retval = ext2fs_allocate_inode_bitmap(fs, 0,
  91                                               &icount->single);
  92         if (retval)
  93                 goto errout;
  94
  95         if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
  96                 retval = ext2fs_allocate_inode_bitmap(fs, 0,
  97                                                       &icount->multiple);
  98                 if (retval)
  99                         goto errout;
 100         } else
 101                 icount->multiple = 0;
 102
 103         if (size) {
 104                 icount->size = size;
 105         } else {
 106                 /*
 107                  * Figure out how many special case inode counts we will
 108                  * have.  We know we will need one for each directory;
 109                  * we also need to reserve some extra room for file links
 110                  */
 111                 retval = ext2fs_get_num_dirs(fs, &icount->size);
 112                 if (retval)
 113                         goto errout;
 114                 icount->size += fs->super->s_inodes_count / 50;
 115         }
 116
 117         bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
 118 #if 0
 119         printf("Icount allocated %u entries, %d bytes.\n",
 120                icount->size, bytes);
 121 #endif
 122         retval = ext2fs_get_mem(bytes, &icount->list);
 123         if (retval)
 124                 goto errout;
 125         memset(icount->list, 0, bytes);
 126
 127         icount->magic = EXT2_ET_MAGIC_ICOUNT;
 128         icount->count = 0;
 129         icount->cursor = 0;
 130         icount->num_inodes = fs->super->s_inodes_count;
 131
 132         /*
 133          * Populate the sorted list with those entries which were
 134          * found in the hint icount (since those are ones which will
 135          * likely need to be in the sorted list this time around).
 136          */
 137         if (hint) {
 138                 for (i=0; i < hint->count; i++)
 139                         icount->list[i].ino = hint->list[i].ino;
 140                 icount->count = hint->count;
 141         }
 142
 143         *ret = icount;
 144         return 0;
 145
 146 errout:
 147         ext2fs_free_icount(icount);
 148         return(retval);
 149 }
 150
 151 errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
 152                                unsigned 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                                             ext2_ino_t ino, int pos)
 164 {
 165         struct ext2_icount_el   *el;
 166         errcode_t               retval;
 167         ext2_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 = (ext2_ino_t) (icount->count *
 174                                 ((float) icount->num_inodes / new_size));
 175                 }
 176                 if (new_size < (icount->size + 100))
 177                         new_size = icount->size + 100;
 178 #if 0
 179                 printf("Reallocating icount %u entries...\n", new_size);
 180 #endif
 181                 retval = ext2fs_resize_mem((size_t) icount->size *
 182                                            sizeof(struct ext2_icount_el),
 183                                            (size_t) new_size *
 184                                            sizeof(struct ext2_icount_el),
 185                                            &icount->list);
 186                 if (retval)
 187                         return 0;
 188                 icount->size = new_size;
 189         }
 190         num = (int) icount->count - pos;
 191         if (num < 0)
 192                 return 0;       /* should never happen */
 193         if (num) {
 194                 memmove(&icount->list[pos+1], &icount->list[pos],
 195                         sizeof(struct ext2_icount_el) * num);
 196         }
 197         icount->count++;
 198         el = &icount->list[pos];
 199         el->count = 0;
 200         el->ino = ino;
 201         return el;
 202 }
 203
 204 /*
 205  * get_icount_el() --- given an inode number, try to find icount
 206  *      information in the sorted list.  If the create flag is set,
 207  *      and we can't find an entry, create one in the sorted list.
 208  */
 209 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
 210                                             ext2_ino_t ino, int create)
 211 {
 212         float   range;
 213         int     low, high, mid;
 214         ext2_ino_t      lowval, highval;
 215
 216         if (!icount || !icount->list)
 217                 return 0;
 218
 219         if (create && ((icount->count == 0) ||
 220                        (ino > icount->list[(unsigned)icount->count-1].ino))) {
 221                 return insert_icount_el(icount, ino, (unsigned) icount->count);
 222         }
 223         if (icount->count == 0)
 224                 return 0;
 225
 226         if (icount->cursor >= icount->count)
 227                 icount->cursor = 0;
 228         if (ino == icount->list[icount->cursor].ino)
 229                 return &icount->list[icount->cursor++];
 230 #if 0
 231         printf("Non-cursor get_icount_el: %u\n", ino);
 232 #endif
 233         low = 0;
 234         high = (int) icount->count-1;
 235         while (low <= high) {
 236 #if 0
 237                 mid = (low+high)/2;
 238 #else
 239                 if (low == high)
 240                         mid = low;
 241                 else {
 242                         /* Interpolate for efficiency */
 243                         lowval = icount->list[low].ino;
 244                         highval = icount->list[high].ino;
 245
 246                         if (ino < lowval)
 247                                 range = 0;
 248                         else if (ino > highval)
 249                                 range = 1;
 250                         else {
 251                                 range = ((float) (ino - lowval)) /
 252                                         (highval - lowval);
 253                                 if (range > 0.9)
 254                                         range = 0.9;
 255                                 if (range < 0.1)
 256                                         range = 0.1;
 257                         }
 258                         mid = low + ((int) (range * (high-low)));
 259                 }
 260 #endif
 261                 if (ino == icount->list[mid].ino) {
 262                         icount->cursor = mid+1;
 263                         return &icount->list[mid];
 264                 }
 265                 if (ino < icount->list[mid].ino)
 266                         high = mid-1;
 267                 else
 268                         low = mid+1;
 269         }
 270         /*
 271          * If we need to create a new entry, it should be right at
 272          * low (where high will be left at low-1).
 273          */
 274         if (create)
 275                 return insert_icount_el(icount, ino, low);
 276         return 0;
 277 }
 278
 279 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
 280 {
 281         errcode_t       ret = 0;
 282         unsigned int    i;
 283         const char *bad = "bad icount";
 284
 285         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 286
 287         if (icount->count > icount->size) {
 288                 fprintf(out, "%s: count > size\n", bad);
 289                 return EXT2_ET_INVALID_ARGUMENT;
 290         }
 291         for (i=1; i < icount->count; i++) {
 292                 if (icount->list[i-1].ino >= icount->list[i].ino) {
 293                         fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
 294                                 bad, i-1, icount->list[i-1].ino,
 295                                 i, icount->list[i].ino);
 296                         ret = EXT2_ET_INVALID_ARGUMENT;
 297                 }
 298         }
 299         return ret;
 300 }
 301
 302 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
 303 {
 304         struct ext2_icount_el   *el;
 305
 306         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 307
 308         if (!ino || (ino > icount->num_inodes))
 309                 return EXT2_ET_INVALID_ARGUMENT;
 310
 311         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 312                 *ret = 1;
 313                 return 0;
 314         }
 315         if (icount->multiple &&
 316             !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 317                 *ret = 0;
 318                 return 0;
 319         }
 320         el = get_icount_el(icount, ino, 0);
 321         if (!el) {
 322                 *ret = 0;
 323                 return 0;
 324         }
 325         *ret = el->count;
 326         return 0;
 327 }
 328
 329 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
 330                                   __u16 *ret)
 331 {
 332         struct ext2_icount_el   *el;
 333
 334         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 335
 336         if (!ino || (ino > icount->num_inodes))
 337                 return EXT2_ET_INVALID_ARGUMENT;
 338
 339         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 340                 /*
 341                  * If the existing count is 1, then we know there is
 342                  * no entry in the list.
 343                  */
 344                 el = get_icount_el(icount, ino, 1);
 345                 if (!el)
 346                         return EXT2_ET_NO_MEMORY;
 347                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 348                 el->count = 2;
 349         } else if (icount->multiple) {
 350                 /*
 351                  * The count is either zero or greater than 1; if the
 352                  * inode is set in icount->multiple, then there should
 353                  * be an entry in the list, so find it using
 354                  * get_icount_el().
 355                  */
 356                 if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 357                         el = get_icount_el(icount, ino, 1);
 358                         if (!el)
 359                                 return EXT2_ET_NO_MEMORY;
 360                         el->count++;
 361                 } else {
 362                         /*
 363                          * The count was zero; mark the single bitmap
 364                          * and return.
 365                          */
 366                 zero_count:
 367                         ext2fs_mark_inode_bitmap(icount->single, ino);
 368                         if (ret)
 369                                 *ret = 1;
 370                         return 0;
 371                 }
 372         } else {
 373                 /*
 374                  * The count is either zero or greater than 1; try to
 375                  * find an entry in the list to determine which.
 376                  */
 377                 el = get_icount_el(icount, ino, 0);
 378                 if (!el) {
 379                         /* No entry means the count was zero */
 380                         goto zero_count;
 381                 }
 382                 el = get_icount_el(icount, ino, 1);
 383                 if (!el)
 384                         return EXT2_ET_NO_MEMORY;
 385                 el->count++;
 386         }
 387         if (icount->multiple)
 388                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 389         if (ret)
 390                 *ret = el->count;
 391         return 0;
 392 }
 393
 394 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
 395                                   __u16 *ret)
 396 {
 397         struct ext2_icount_el   *el;
 398
 399         if (!ino || (ino > icount->num_inodes))
 400                 return EXT2_ET_INVALID_ARGUMENT;
 401
 402         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 403
 404         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 405                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 406                 if (icount->multiple)
 407                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 408                 else {
 409                         el = get_icount_el(icount, ino, 0);
 410                         if (el)
 411                                 el->count = 0;
 412                 }
 413                 if (ret)
 414                         *ret = 0;
 415                 return 0;
 416         }
 417
 418         if (icount->multiple &&
 419             !ext2fs_test_inode_bitmap(icount->multiple, ino))
 420                 return EXT2_ET_INVALID_ARGUMENT;
 421
 422         el = get_icount_el(icount, ino, 0);
 423         if (!el || el->count == 0)
 424                 return EXT2_ET_INVALID_ARGUMENT;
 425
 426         el->count--;
 427         if (el->count == 1)
 428                 ext2fs_mark_inode_bitmap(icount->single, ino);
 429         if ((el->count == 0) && icount->multiple)
 430                 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 431
 432         if (ret)
 433                 *ret = el->count;
 434         return 0;
 435 }
 436
 437 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
 438                               __u16 count)
 439 {
 440         struct ext2_icount_el   *el;
 441
 442         if (!ino || (ino > icount->num_inodes))
 443                 return EXT2_ET_INVALID_ARGUMENT;
 444
 445         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 446
 447         if (count == 1) {
 448                 ext2fs_mark_inode_bitmap(icount->single, ino);
 449                 if (icount->multiple)
 450                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 451                 return 0;
 452         }
 453         if (count == 0) {
 454                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 455                 if (icount->multiple) {
 456                         /*
 457                          * If the icount->multiple bitmap is enabled,
 458                          * we can just clear both bitmaps and we're done
 459                          */
 460                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 461                 } else {
 462                         el = get_icount_el(icount, ino, 0);
 463                         if (el)
 464                                 el->count = 0;
 465                 }
 466                 return 0;
 467         }
 468
 469         /*
 470          * Get the icount element
 471          */
 472         el = get_icount_el(icount, ino, 1);
 473         if (!el)
 474                 return EXT2_ET_NO_MEMORY;
 475         el->count = count;
 476         ext2fs_unmark_inode_bitmap(icount->single, ino);
 477         if (icount->multiple)
 478                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 479         return 0;
 480 }
 481
 482 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
 483 {
 484         if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
 485                 return 0;
 486
 487         return icount->size;
 488 }
 489
 490 #ifdef DEBUG
 491
 492 ext2_filsys     test_fs;
 493 ext2_icount_t   icount;
 494
 495 #define EXIT            0x00
 496 #define FETCH           0x01
 497 #define STORE           0x02
 498 #define INCREMENT       0x03
 499 #define DECREMENT       0x04
 500
 501 struct test_program {
 502         int             cmd;
 503         ext2_ino_t      ino;
 504         __u16           arg;
 505         __u16           expected;
 506 };
 507
 508 struct test_program prog[] = {
 509         { STORE, 42, 42, 42 },
 510         { STORE, 1,  1, 1 },
 511         { STORE, 2,  2, 2 },
 512         { STORE, 3,  3, 3 },
 513         { STORE, 10, 1, 1 },
 514         { STORE, 42, 0, 0 },
 515         { INCREMENT, 5, 0, 1 },
 516         { INCREMENT, 5, 0, 2 },
 517         { INCREMENT, 5, 0, 3 },
 518         { INCREMENT, 5, 0, 4 },
 519         { DECREMENT, 5, 0, 3 },
 520         { DECREMENT, 5, 0, 2 },
 521         { DECREMENT, 5, 0, 1 },
 522         { DECREMENT, 5, 0, 0 },
 523         { FETCH, 10, 0, 1 },
 524         { FETCH, 1, 0, 1 },
 525         { FETCH, 2, 0, 2 },
 526         { FETCH, 3, 0, 3 },
 527         { INCREMENT, 1, 0, 2 },
 528         { DECREMENT, 2, 0, 1 },
 529         { DECREMENT, 2, 0, 0 },
 530         { FETCH, 12, 0, 0 },
 531         { EXIT, 0, 0, 0 }
 532 };
 533
 534 struct test_program extended[] = {
 535         { STORE, 1,  1, 1 },
 536         { STORE, 2,  2, 2 },
 537         { STORE, 3,  3, 3 },
 538         { STORE, 4,  4, 4 },
 539         { STORE, 5,  5, 5 },
 540         { STORE, 6,  1, 1 },
 541         { STORE, 7,  2, 2 },
 542         { STORE, 8,  3, 3 },
 543         { STORE, 9,  4, 4 },
 544         { STORE, 10, 5, 5 },
 545         { STORE, 11, 1, 1 },
 546         { STORE, 12, 2, 2 },
 547         { STORE, 13, 3, 3 },
 548         { STORE, 14, 4, 4 },
 549         { STORE, 15, 5, 5 },
 550         { STORE, 16, 1, 1 },
 551         { STORE, 17, 2, 2 },
 552         { STORE, 18, 3, 3 },
 553         { STORE, 19, 4, 4 },
 554         { STORE, 20, 5, 5 },
 555         { STORE, 21, 1, 1 },
 556         { STORE, 22, 2, 2 },
 557         { STORE, 23, 3, 3 },
 558         { STORE, 24, 4, 4 },
 559         { STORE, 25, 5, 5 },
 560         { STORE, 26, 1, 1 },
 561         { STORE, 27, 2, 2 },
 562         { STORE, 28, 3, 3 },
 563         { STORE, 29, 4, 4 },
 564         { STORE, 30, 5, 5 },
 565         { EXIT, 0, 0, 0 }
 566 };
 567
 568 /*
 569  * Setup the variables for doing the inode scan test.
 570  */
 571 static void setup(void)
 572 {
 573         errcode_t       retval;
 574         int             i;
 575         struct ext2_super_block param;
 576
 577         initialize_ext2_error_table();
 578
 579         memset(&param, 0, sizeof(param));
 580         param.s_blocks_count = 12000;
 581
 582         retval = ext2fs_initialize("test fs", 0, &param,
 583                                    test_io_manager, &test_fs);
 584         if (retval) {
 585                 com_err("setup", retval,
 586                         "while initializing filesystem");
 587                 exit(1);
 588         }
 589         retval = ext2fs_allocate_tables(test_fs);
 590         if (retval) {
 591                 com_err("setup", retval,
 592                         "while allocating tables for test filesystem");
 593                 exit(1);
 594         }
 595 }
 596
 597 int run_test(int flags, int size, struct test_program *prog)
 598 {
 599         errcode_t       retval;
 600         ext2_icount_t   icount;
 601         struct test_program *pc;
 602         __u16           result;
 603         int             problem = 0;
 604
 605         retval = ext2fs_create_icount2(test_fs, flags, size, 0, &icount);
 606         if (retval) {
 607                 com_err("run_test", retval,
 608                         "While creating icount");
 609                 exit(1);
 610         }
 611         for (pc = prog; pc->cmd != EXIT; pc++) {
 612                 switch (pc->cmd) {
 613                 case FETCH:
 614                         printf("icount_fetch(%u) = ", pc->ino);
 615                         break;
 616                 case STORE:
 617                         retval = ext2fs_icount_store(icount, pc->ino, pc->arg);
 618                         if (retval) {
 619                                 com_err("run_test", retval,
 620                                         "while calling icount_store");
 621                                 exit(1);
 622                         }
 623                         printf("icount_store(%u, %u) = ", pc->ino, pc->arg);
 624                         break;
 625                 case INCREMENT:
 626                         retval = ext2fs_icount_increment(icount, pc->ino, 0);
 627                         if (retval) {
 628                                 com_err("run_test", retval,
 629                                         "while calling icount_increment");
 630                                 exit(1);
 631                         }
 632                         printf("icount_increment(%u) = ", pc->ino);
 633                         break;
 634                 case DECREMENT:
 635                         retval = ext2fs_icount_decrement(icount, pc->ino, 0);
 636                         if (retval) {
 637                                 com_err("run_test", retval,
 638                                         "while calling icount_decrement");
 639                                 exit(1);
 640                         }
 641                         printf("icount_decrement(%u) = ", pc->ino);
 642                         break;
 643                 }
 644                 retval = ext2fs_icount_fetch(icount, pc->ino, &result);
 645                 if (retval) {
 646                         com_err("run_test", retval,
 647                                 "while calling icount_fetch");
 648                         exit(1);
 649                 }
 650                 printf("%u (%s)\n", result, (result == pc->expected) ?
 651                        "OK" : "NOT OK");
 652                 if (result != pc->expected)
 653                         problem++;
 654         }
 655         printf("icount size is %u\n", ext2fs_get_icount_size(icount));
 656         retval = ext2fs_icount_validate(icount, stdout);
 657         if (retval) {
 658                 com_err("run_test", retval, "while calling icount_validate");
 659                 exit(1);
 660         }
 661         ext2fs_free_icount(icount);
 662         return problem;
 663 }
 664
 665
 666 int main(int argc, char **argv)
 667 {
 668         int failed = 0;
 669
 670         setup();
 671         printf("Standard icount run:\n");
 672         failed += run_test(0, 0, prog);
 673         printf("\nMultiple bitmap test:\n");
 674         failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, prog);
 675         printf("\nResizing icount:\n");
 676         failed += run_test(0, 3, extended);
 677         if (failed)
 678                 printf("FAILED!\n");
 679         return failed;
 680 }
 681 #endif