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 Library
   8  * General Public License, version 2.
   9  * %End-Header%
  10  */
  11
  12 #include "config.h"
  13 #if HAVE_UNISTD_H
  14 #include <unistd.h>
  15 #endif
  16 #include <assert.h>
  17 #include <string.h>
  18 #include <stdio.h>
  19 #include <sys/stat.h>
  20 #include <fcntl.h>
  21 #include <errno.h>
  22
  23 #include "ext2_fs.h"
  24 #include "ext2fs.h"
  25 #include "tdb.h"
  26
  27 /*
  28  * The data storage strategy used by icount relies on the observation
  29  * that most inode counts are either zero (for non-allocated inodes),
  30  * one (for most files), and only a few that are two or more
  31  * (directories and files that are linked to more than one directory).
  32  *
  33  * Also, e2fsck tends to load the icount data sequentially.
  34  *
  35  * So, we use an inode bitmap to indicate which inodes have a count of
  36  * one, and then use a sorted list to store the counts for inodes
  37  * which are greater than one.
  38  *
  39  * We also use an optional bitmap to indicate which inodes are already
  40  * in the sorted list, to speed up the use of this abstraction by
  41  * e2fsck's pass 2.  Pass 2 increments inode counts as it finds them,
  42  * so this extra bitmap avoids searching the sorted list to see if a
  43  * particular inode is on the sorted list already.
  44  */
  45
  46 struct ext2_icount_el {
  47         ext2_ino_t      ino;
  48         __u32           count;
  49 };
  50
  51 struct ext2_icount {
  52         errcode_t               magic;
  53         ext2fs_inode_bitmap     single;
  54         ext2fs_inode_bitmap     multiple;
  55         ext2_ino_t              count;
  56         ext2_ino_t              size;
  57         ext2_ino_t              num_inodes;
  58         ext2_ino_t              cursor;
  59         struct ext2_icount_el   *list;
  60         struct ext2_icount_el   *last_lookup;
  61 #ifdef CONFIG_TDB
  62         char                    *tdb_fn;
  63         TDB_CONTEXT             *tdb;
  64 #endif
  65         __u16                   *fullmap;
  66 };
  67
  68 /*
  69  * We now use a 32-bit counter field because it doesn't cost us
  70  * anything extra for the in-memory data structure, due to alignment
  71  * padding.  But there's no point changing the interface if most of
  72  * the time we only care if the number is bigger than 65,000 or not.
  73  * So use the following translation function to return a 16-bit count.
  74  */
  75 #define icount_16_xlate(x) (((x) > 65500) ? 65500 : (x))
  76
  77 void ext2fs_free_icount(ext2_icount_t icount)
  78 {
  79         if (!icount)
  80                 return;
  81
  82         icount->magic = 0;
  83         if (icount->list)
  84                 ext2fs_free_mem(&icount->list);
  85         if (icount->single)
  86                 ext2fs_free_inode_bitmap(icount->single);
  87         if (icount->multiple)
  88                 ext2fs_free_inode_bitmap(icount->multiple);
  89 #ifdef CONFIG_TDB
  90         if (icount->tdb)
  91                 tdb_close(icount->tdb);
  92         if (icount->tdb_fn) {
  93                 (void) unlink(icount->tdb_fn);
  94                 free(icount->tdb_fn);
  95         }
  96 #endif
  97
  98         if (icount->fullmap)
  99                 ext2fs_free_mem(&icount->fullmap);
 100
 101         ext2fs_free_mem(&icount);
 102 }
 103
 104 static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret)
 105 {
 106         ext2_icount_t   icount;
 107         errcode_t       retval;
 108
 109         *ret = 0;
 110
 111         retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
 112         if (retval)
 113                 return retval;
 114         memset(icount, 0, sizeof(struct ext2_icount));
 115         icount->magic = EXT2_ET_MAGIC_ICOUNT;
 116         icount->num_inodes = fs->super->s_inodes_count;
 117
 118         if ((flags & EXT2_ICOUNT_OPT_FULLMAP) &&
 119             (flags & EXT2_ICOUNT_OPT_INCREMENT)) {
 120                 unsigned sz = sizeof(*icount->fullmap) * icount->num_inodes;
 121
 122                 retval = ext2fs_get_mem(sz, &icount->fullmap);
 123                 /* If we can't allocate, fall back */
 124                 if (!retval) {
 125                         memset(icount->fullmap, 0, sz);
 126                         *ret = icount;
 127                         return 0;
 128                 }
 129         }
 130
 131         retval = ext2fs_allocate_inode_bitmap(fs, "icount", &icount->single);
 132         if (retval)
 133                 goto errout;
 134
 135         if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
 136                 retval = ext2fs_allocate_inode_bitmap(fs, "icount_inc",
 137                                                       &icount->multiple);
 138                 if (retval)
 139                         goto errout;
 140         } else
 141                 icount->multiple = 0;
 142
 143         *ret = icount;
 144         return 0;
 145
 146 errout:
 147         ext2fs_free_icount(icount);
 148         return(retval);
 149 }
 150
 151 #ifdef CONFIG_TDB
 152 struct uuid {
 153         __u32   time_low;
 154         __u16   time_mid;
 155         __u16   time_hi_and_version;
 156         __u16   clock_seq;
 157         __u8    node[6];
 158 };
 159
 160 static void unpack_uuid(void *in, struct uuid *uu)
 161 {
 162         __u8    *ptr = in;
 163         __u32   tmp;
 164
 165         tmp = *ptr++;
 166         tmp = (tmp << 8) | *ptr++;
 167         tmp = (tmp << 8) | *ptr++;
 168         tmp = (tmp << 8) | *ptr++;
 169         uu->time_low = tmp;
 170
 171         tmp = *ptr++;
 172         tmp = (tmp << 8) | *ptr++;
 173         uu->time_mid = tmp;
 174
 175         tmp = *ptr++;
 176         tmp = (tmp << 8) | *ptr++;
 177         uu->time_hi_and_version = tmp;
 178
 179         tmp = *ptr++;
 180         tmp = (tmp << 8) | *ptr++;
 181         uu->clock_seq = tmp;
 182
 183         memcpy(uu->node, ptr, 6);
 184 }
 185
 186 static void uuid_unparse(void *uu, char *out)
 187 {
 188         struct uuid uuid;
 189
 190         unpack_uuid(uu, &uuid);
 191         sprintf(out,
 192                 "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
 193                 uuid.time_low, uuid.time_mid, uuid.time_hi_and_version,
 194                 uuid.clock_seq >> 8, uuid.clock_seq & 0xFF,
 195                 uuid.node[0], uuid.node[1], uuid.node[2],
 196                 uuid.node[3], uuid.node[4], uuid.node[5]);
 197 }
 198 #endif
 199
 200 errcode_t ext2fs_create_icount_tdb(ext2_filsys fs EXT2FS_NO_TDB_UNUSED,
 201                                    char *tdb_dir EXT2FS_NO_TDB_UNUSED,
 202                                    int flags EXT2FS_NO_TDB_UNUSED,
 203                                    ext2_icount_t *ret EXT2FS_NO_TDB_UNUSED)
 204 {
 205 #ifdef CONFIG_TDB
 206         ext2_icount_t   icount;
 207         errcode_t       retval;
 208         char            *fn, uuid[40];
 209         ext2_ino_t      num_inodes;
 210         mode_t          save_umask;
 211         int             fd;
 212
 213         retval = alloc_icount(fs, flags,  &icount);
 214         if (retval)
 215                 return retval;
 216
 217         retval = ext2fs_get_mem(strlen(tdb_dir) + 64, &fn);
 218         if (retval)
 219                 goto errout;
 220         uuid_unparse(fs->super->s_uuid, uuid);
 221         sprintf(fn, "%s/%s-icount-XXXXXX", tdb_dir, uuid);
 222         save_umask = umask(077);
 223         fd = mkstemp(fn);
 224         if (fd < 0) {
 225                 retval = errno;
 226                 ext2fs_free_mem(&fn);
 227                 goto errout;
 228         }
 229         icount->tdb_fn = fn;
 230         umask(save_umask);
 231         /*
 232          * This is an overestimate of the size that we will need; the
 233          * ideal value is the number of used inodes with a count
 234          * greater than 1.  OTOH the times when we really need this is
 235          * with the backup programs that use lots of hard links, in
 236          * which case the number of inodes in use approaches the ideal
 237          * value.
 238          */
 239         num_inodes = fs->super->s_inodes_count - fs->super->s_free_inodes_count;
 240         if (fs->fs_num_threads)
 241                 num_inodes /= fs->fs_num_threads;
 242
 243         icount->tdb = tdb_open(fn, num_inodes, TDB_NOLOCK | TDB_NOSYNC,
 244                                O_RDWR | O_CREAT | O_TRUNC, 0600);
 245         close(fd);
 246         if (icount->tdb == NULL) {
 247                 retval = errno;
 248                 goto errout;
 249         }
 250         *ret = icount;
 251         return 0;
 252 errout:
 253         ext2fs_free_icount(icount);
 254         return(retval);
 255 #else
 256         return EXT2_ET_UNIMPLEMENTED;
 257 #endif
 258 }
 259
 260 errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
 261                                 ext2_icount_t hint, ext2_icount_t *ret)
 262 {
 263         ext2_icount_t   icount;
 264         errcode_t       retval;
 265         size_t          bytes;
 266         ext2_ino_t      i;
 267
 268         if (hint) {
 269                 EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
 270                 if (hint->size > size)
 271                         size = (size_t) hint->size;
 272         }
 273
 274         retval = alloc_icount(fs, flags, &icount);
 275         if (retval)
 276                 return retval;
 277
 278         if (icount->fullmap)
 279                 goto successout;
 280
 281         if (size) {
 282                 icount->size = size;
 283         } else {
 284                 /*
 285                  * Figure out how many special case inode counts we will
 286                  * have.  We know we will need one for each directory;
 287                  * we also need to reserve some extra room for file links
 288                  */
 289                 retval = ext2fs_get_num_dirs(fs, &icount->size);
 290                 if (retval)
 291                         goto errout;
 292                 icount->size += fs->super->s_inodes_count / 50;
 293                 if (fs->fs_num_threads)
 294                         icount->size /= fs->fs_num_threads;
 295         }
 296
 297         bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
 298 #if 0
 299         printf("Icount allocated %u entries, %d bytes.\n",
 300                icount->size, bytes);
 301 #endif
 302         retval = ext2fs_get_array(icount->size, sizeof(struct ext2_icount_el),
 303                          &icount->list);
 304         if (retval)
 305                 goto errout;
 306         memset(icount->list, 0, bytes);
 307
 308         icount->count = 0;
 309         icount->cursor = 0;
 310
 311         /*
 312          * Populate the sorted list with those entries which were
 313          * found in the hint icount (since those are ones which will
 314          * likely need to be in the sorted list this time around).
 315          */
 316         if (hint) {
 317                 for (i=0; i < hint->count; i++)
 318                         icount->list[i].ino = hint->list[i].ino;
 319                 icount->count = hint->count;
 320         }
 321
 322 successout:
 323         *ret = icount;
 324         return 0;
 325
 326 errout:
 327         ext2fs_free_icount(icount);
 328         return(retval);
 329 }
 330
 331 errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
 332                                unsigned int size,
 333                                ext2_icount_t *ret)
 334 {
 335         return ext2fs_create_icount2(fs, flags, size, 0, ret);
 336 }
 337
 338 /*
 339  * insert_icount_el() --- Insert a new entry into the sorted list at a
 340  *      specified position.
 341  */
 342 static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
 343                                             ext2_ino_t ino, int pos)
 344 {
 345         struct ext2_icount_el   *el;
 346         errcode_t               retval;
 347         ext2_ino_t              new_size = 0;
 348         int                     num;
 349
 350         if (icount->last_lookup && icount->last_lookup->ino == ino)
 351                 return icount->last_lookup;
 352
 353         if (icount->count >= icount->size) {
 354                 if (icount->count) {
 355                         new_size = icount->list[(unsigned)icount->count-1].ino;
 356                         new_size = (ext2_ino_t) (icount->count *
 357                                 ((float) icount->num_inodes / new_size));
 358                 }
 359                 if (new_size < (icount->size + 100))
 360                         new_size = icount->size + 100;
 361 #if 0
 362                 printf("Reallocating icount %u entries...\n", new_size);
 363 #endif
 364                 retval = ext2fs_resize_mem((size_t) icount->size *
 365                                            sizeof(struct ext2_icount_el),
 366                                            (size_t) new_size *
 367                                            sizeof(struct ext2_icount_el),
 368                                            &icount->list);
 369                 if (retval)
 370                         return 0;
 371                 icount->size = new_size;
 372         }
 373         num = (int) icount->count - pos;
 374         if (num < 0)
 375                 return 0;       /* should never happen */
 376         if (num) {
 377                 memmove(&icount->list[pos+1], &icount->list[pos],
 378                         sizeof(struct ext2_icount_el) * num);
 379         }
 380         icount->count++;
 381         el = &icount->list[pos];
 382         el->count = 0;
 383         el->ino = ino;
 384         icount->last_lookup = el;
 385         return el;
 386 }
 387
 388 /*
 389  * get_icount_el() --- given an inode number, try to find icount
 390  *      information in the sorted list.  If the create flag is set,
 391  *      and we can't find an entry, create one in the sorted list.
 392  */
 393 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
 394                                             ext2_ino_t ino, int create)
 395 {
 396         int     low, high, mid;
 397
 398         if (!icount || !icount->list)
 399                 return 0;
 400
 401         if (create && ((icount->count == 0) ||
 402                        (ino > icount->list[(unsigned)icount->count-1].ino))) {
 403                 return insert_icount_el(icount, ino, (unsigned) icount->count);
 404         }
 405         if (icount->count == 0)
 406                 return 0;
 407
 408         if (icount->cursor >= icount->count)
 409                 icount->cursor = 0;
 410         if (ino == icount->list[icount->cursor].ino)
 411                 return &icount->list[icount->cursor++];
 412 #if 0
 413         printf("Non-cursor get_icount_el: %u\n", ino);
 414 #endif
 415         low = 0;
 416         high = (int) icount->count-1;
 417         while (low <= high) {
 418                 mid = ((unsigned)low + (unsigned)high) >> 1;
 419                 if (ino == icount->list[mid].ino) {
 420                         icount->cursor = mid+1;
 421                         return &icount->list[mid];
 422                 }
 423                 if (ino < icount->list[mid].ino)
 424                         high = mid-1;
 425                 else
 426                         low = mid+1;
 427         }
 428         /*
 429          * If we need to create a new entry, it should be right at
 430          * low (where high will be left at low-1).
 431          */
 432         if (create)
 433                 return insert_icount_el(icount, ino, low);
 434         return 0;
 435 }
 436
 437 static errcode_t set_inode_count(ext2_icount_t icount, ext2_ino_t ino,
 438                                  __u32 count)
 439 {
 440         struct ext2_icount_el   *el;
 441 #ifdef CONFIG_TDB
 442         TDB_DATA key, data;
 443
 444         if (icount->tdb) {
 445                 key.dptr = (unsigned char *) &ino;
 446                 key.dsize = sizeof(ext2_ino_t);
 447                 data.dptr = (unsigned char *) &count;
 448                 data.dsize = sizeof(__u32);
 449                 if (count) {
 450                         if (tdb_store(icount->tdb, key, data, TDB_REPLACE))
 451                                 return tdb_error(icount->tdb) +
 452                                         EXT2_ET_TDB_SUCCESS;
 453                 } else {
 454                         if (tdb_delete(icount->tdb, key))
 455                                 return tdb_error(icount->tdb) +
 456                                         EXT2_ET_TDB_SUCCESS;
 457                 }
 458                 return 0;
 459         }
 460 #endif
 461         if (icount->fullmap) {
 462                 icount->fullmap[ino] = icount_16_xlate(count);
 463                 return 0;
 464         }
 465
 466         el = get_icount_el(icount, ino, 1);
 467         if (!el)
 468                 return EXT2_ET_NO_MEMORY;
 469
 470         el->count = count;
 471         return 0;
 472 }
 473
 474 static errcode_t get_inode_count(ext2_icount_t icount, ext2_ino_t ino,
 475                                  __u32 *count)
 476 {
 477         struct ext2_icount_el   *el;
 478 #ifdef CONFIG_TDB
 479         TDB_DATA key, data;
 480
 481         if (icount->tdb) {
 482                 key.dptr = (unsigned char *) &ino;
 483                 key.dsize = sizeof(ext2_ino_t);
 484
 485                 data = tdb_fetch(icount->tdb, key);
 486                 if (data.dptr == NULL) {
 487                         *count = 0;
 488                         return tdb_error(icount->tdb) + EXT2_ET_TDB_SUCCESS;
 489                 }
 490
 491                 *count = *((__u32 *) data.dptr);
 492                 free(data.dptr);
 493                 return 0;
 494         }
 495 #endif
 496         if (icount->fullmap) {
 497                 *count = icount->fullmap[ino];
 498                 return 0;
 499         }
 500
 501         el = get_icount_el(icount, ino, 0);
 502         if (!el) {
 503                 *count = 0;
 504                 return ENOENT;
 505         }
 506
 507         *count = el->count;
 508         return 0;
 509 }
 510
 511 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
 512 {
 513         errcode_t       ret = 0;
 514         unsigned int    i;
 515         const char *bad = "bad icount";
 516
 517         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 518
 519         if (icount->count > icount->size) {
 520                 fprintf(out, "%s: count > size\n", bad);
 521                 return EXT2_ET_INVALID_ARGUMENT;
 522         }
 523         for (i=1; i < icount->count; i++) {
 524                 if (icount->list[i-1].ino >= icount->list[i].ino) {
 525                         fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
 526                                 bad, i-1, icount->list[i-1].ino,
 527                                 i, icount->list[i].ino);
 528                         ret = EXT2_ET_INVALID_ARGUMENT;
 529                 }
 530         }
 531         return ret;
 532 }
 533
 534 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
 535 {
 536         __u32   val;
 537         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 538
 539         if (!ino || (ino > icount->num_inodes))
 540                 return EXT2_ET_INVALID_ARGUMENT;
 541
 542         if (!icount->fullmap) {
 543                 if (ext2fs_test_inode_bitmap2(icount->single, ino)) {
 544                         *ret = 1;
 545                         return 0;
 546                 }
 547                 if (icount->multiple &&
 548                         !ext2fs_test_inode_bitmap2(icount->multiple, ino)) {
 549                         *ret = 0;
 550                         return 0;
 551                 }
 552         }
 553         get_inode_count(icount, ino, &val);
 554         *ret = icount_16_xlate(val);
 555         return 0;
 556 }
 557
 558 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
 559                                   __u16 *ret)
 560 {
 561         __u32                   curr_value;
 562
 563         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 564
 565         if (!ino || (ino > icount->num_inodes))
 566                 return EXT2_ET_INVALID_ARGUMENT;
 567
 568         if (icount->fullmap) {
 569                 curr_value = icount_16_xlate(icount->fullmap[ino] + 1);
 570                 icount->fullmap[ino] = curr_value;
 571         } else if (ext2fs_test_inode_bitmap2(icount->single, ino)) {
 572                 /*
 573                  * If the existing count is 1, then we know there is
 574                  * no entry in the list.
 575                  */
 576                 if (set_inode_count(icount, ino, 2))
 577                         return EXT2_ET_NO_MEMORY;
 578                 curr_value = 2;
 579                 ext2fs_unmark_inode_bitmap2(icount->single, ino);
 580         } else if (icount->multiple) {
 581                 /*
 582                  * The count is either zero or greater than 1; if the
 583                  * inode is set in icount->multiple, then there should
 584                  * be an entry in the list, so we need to fix it.
 585                  */
 586                 if (ext2fs_test_inode_bitmap2(icount->multiple, ino)) {
 587                         get_inode_count(icount, ino, &curr_value);
 588                         curr_value++;
 589                         if (set_inode_count(icount, ino, curr_value))
 590                                 return EXT2_ET_NO_MEMORY;
 591                 } else {
 592                         /*
 593                          * The count was zero; mark the single bitmap
 594                          * and return.
 595                          */
 596                         ext2fs_mark_inode_bitmap2(icount->single, ino);
 597                         if (ret)
 598                                 *ret = 1;
 599                         return 0;
 600                 }
 601         } else {
 602                 /*
 603                  * The count is either zero or greater than 1; try to
 604                  * find an entry in the list to determine which.
 605                  */
 606                 get_inode_count(icount, ino, &curr_value);
 607                 curr_value++;
 608                 if (set_inode_count(icount, ino, curr_value))
 609                         return EXT2_ET_NO_MEMORY;
 610         }
 611         if (icount->multiple)
 612                 ext2fs_mark_inode_bitmap2(icount->multiple, ino);
 613         if (ret)
 614                 *ret = icount_16_xlate(curr_value);
 615         return 0;
 616 }
 617
 618 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
 619                                   __u16 *ret)
 620 {
 621         __u32                   curr_value;
 622
 623         if (!ino || (ino > icount->num_inodes))
 624                 return EXT2_ET_INVALID_ARGUMENT;
 625
 626         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 627
 628         if (icount->fullmap) {
 629                 if (!icount->fullmap[ino])
 630                         return EXT2_ET_INVALID_ARGUMENT;
 631
 632                 curr_value = --icount->fullmap[ino];
 633                 if (ret)
 634                         *ret = icount_16_xlate(curr_value);
 635                 return 0;
 636         }
 637
 638         if (ext2fs_test_inode_bitmap2(icount->single, ino)) {
 639                 ext2fs_unmark_inode_bitmap2(icount->single, ino);
 640                 if (icount->multiple)
 641                         ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
 642                 else {
 643                         set_inode_count(icount, ino, 0);
 644                 }
 645                 if (ret)
 646                         *ret = 0;
 647                 return 0;
 648         }
 649
 650         if (icount->multiple &&
 651             !ext2fs_test_inode_bitmap2(icount->multiple, ino))
 652                 return EXT2_ET_INVALID_ARGUMENT;
 653
 654         get_inode_count(icount, ino, &curr_value);
 655         if (!curr_value)
 656                 return EXT2_ET_INVALID_ARGUMENT;
 657         curr_value--;
 658         if (set_inode_count(icount, ino, curr_value))
 659                 return EXT2_ET_NO_MEMORY;
 660
 661         if (curr_value == 1)
 662                 ext2fs_mark_inode_bitmap2(icount->single, ino);
 663         if ((curr_value == 0) && icount->multiple)
 664                 ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
 665
 666         if (ret)
 667                 *ret = icount_16_xlate(curr_value);
 668         return 0;
 669 }
 670
 671 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
 672                               __u16 count)
 673 {
 674         if (!ino || (ino > icount->num_inodes))
 675                 return EXT2_ET_INVALID_ARGUMENT;
 676
 677         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 678
 679         if (icount->fullmap)
 680                 return set_inode_count(icount, ino, count);
 681
 682         if (count == 1) {
 683                 ext2fs_mark_inode_bitmap2(icount->single, ino);
 684                 if (icount->multiple)
 685                         ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
 686                 return 0;
 687         }
 688         if (count == 0) {
 689                 ext2fs_unmark_inode_bitmap2(icount->single, ino);
 690                 if (icount->multiple) {
 691                         /*
 692                          * If the icount->multiple bitmap is enabled,
 693                          * we can just clear both bitmaps and we're done
 694                          */
 695                         ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
 696                 } else
 697                         set_inode_count(icount, ino, 0);
 698                 return 0;
 699         }
 700
 701         if (set_inode_count(icount, ino, count))
 702                 return EXT2_ET_NO_MEMORY;
 703         ext2fs_unmark_inode_bitmap2(icount->single, ino);
 704         if (icount->multiple)
 705                 ext2fs_mark_inode_bitmap2(icount->multiple, ino);
 706         return 0;
 707 }
 708
 709 errcode_t ext2fs_icount_merge_full_map(ext2_icount_t src, ext2_icount_t dest)
 710 {
 711         /* TODO: add the support for full map */
 712         return EOPNOTSUPP;
 713 }
 714
 715 errcode_t ext2fs_icount_merge_el(ext2_icount_t src, ext2_icount_t dest)
 716 {
 717         int                      src_count = src->count;
 718         int                      dest_count = dest->count;
 719         int                      size = src_count + dest_count;
 720         int                      size_entry = sizeof(struct ext2_icount_el);
 721         struct ext2_icount_el   *array;
 722         struct ext2_icount_el   *array_ptr;
 723         struct ext2_icount_el   *src_array = src->list;
 724         struct ext2_icount_el   *dest_array = dest->list;
 725         int                      src_index = 0;
 726         int                      dest_index = 0;
 727         errcode_t                retval;
 728
 729         if (src_count == 0)
 730                 return 0;
 731
 732         retval = ext2fs_get_array(size, size_entry, &array);
 733         if (retval)
 734                 return retval;
 735
 736         array_ptr = array;
 737         /*
 738          * This can be improved by binary search and memcpy, but codes
 739          * would be more complex. And if number of bad blocks is small,
 740          * the optimization won't improve performance a lot.
 741          */
 742         while (src_index < src_count || dest_index < dest_count) {
 743                 if (src_index >= src_count) {
 744                         memcpy(array_ptr, &dest_array[dest_index],
 745                                (dest_count - dest_index) * size_entry);
 746                         break;
 747                 }
 748                 if (dest_index >= dest_count) {
 749                         memcpy(array_ptr, &src_array[src_index],
 750                                (src_count - src_index) * size_entry);
 751                         break;
 752                 }
 753                 if (src_array[src_index].ino < dest_array[dest_index].ino) {
 754                         *array_ptr = src_array[src_index];
 755                         src_index++;
 756                 } else {
 757                         assert(src_array[src_index].ino >
 758                                dest_array[dest_index].ino);
 759                         *array_ptr = dest_array[dest_index];
 760                         dest_index++;
 761                 }
 762                 array_ptr++;
 763         }
 764
 765         ext2fs_free_mem(&dest->list);
 766         dest->list = array;
 767         dest->count = src_count + dest_count;
 768         dest->size = size;
 769         dest->last_lookup = NULL;
 770         return 0;
 771 }
 772
 773 errcode_t ext2fs_icount_merge(ext2_icount_t src, ext2_icount_t dest)
 774 {
 775         errcode_t       retval;
 776
 777         if (src->fullmap && !dest->fullmap)
 778                 return EINVAL;
 779
 780         if (!src->fullmap && dest->fullmap)
 781                 return EINVAL;
 782
 783         if (src->multiple && !dest->multiple)
 784                 return EINVAL;
 785
 786         if (!src->multiple && dest->multiple)
 787                 return EINVAL;
 788
 789         if (src->fullmap)
 790                 return ext2fs_icount_merge_full_map(src, dest);
 791
 792         retval = ext2fs_merge_bitmap(src->single, dest->single, NULL,
 793                                      NULL);
 794         if (retval)
 795                 return retval;
 796
 797         if (src->multiple) {
 798                 retval = ext2fs_merge_bitmap(src->multiple, dest->multiple,
 799                                              NULL, NULL);
 800                 if (retval)
 801                         return retval;
 802         }
 803
 804         retval = ext2fs_icount_merge_el(src, dest);
 805         if (retval)
 806                 return retval;
 807
 808         return 0;
 809 }
 810
 811 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
 812 {
 813         if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
 814                 return 0;
 815
 816         return icount->size;
 817 }
 818
 819 #ifdef DEBUG
 820
 821 ext2_filsys     test_fs;
 822 ext2_icount_t   icount;
 823
 824 #define EXIT            0x00
 825 #define FETCH           0x01
 826 #define STORE           0x02
 827 #define INCREMENT       0x03
 828 #define DECREMENT       0x04
 829
 830 struct test_program {
 831         int             cmd;
 832         ext2_ino_t      ino;
 833         __u16           arg;
 834         __u16           expected;
 835 };
 836
 837 struct test_program prog[] = {
 838         { STORE, 42, 42, 42 },
 839         { STORE, 1,  1, 1 },
 840         { STORE, 2,  2, 2 },
 841         { STORE, 3,  3, 3 },
 842         { STORE, 10, 1, 1 },
 843         { STORE, 42, 0, 0 },
 844         { INCREMENT, 5, 0, 1 },
 845         { INCREMENT, 5, 0, 2 },
 846         { INCREMENT, 5, 0, 3 },
 847         { INCREMENT, 5, 0, 4 },
 848         { DECREMENT, 5, 0, 3 },
 849         { DECREMENT, 5, 0, 2 },
 850         { DECREMENT, 5, 0, 1 },
 851         { DECREMENT, 5, 0, 0 },
 852         { FETCH, 10, 0, 1 },
 853         { FETCH, 1, 0, 1 },
 854         { FETCH, 2, 0, 2 },
 855         { FETCH, 3, 0, 3 },
 856         { INCREMENT, 1, 0, 2 },
 857         { DECREMENT, 2, 0, 1 },
 858         { DECREMENT, 2, 0, 0 },
 859         { FETCH, 12, 0, 0 },
 860         { EXIT, 0, 0, 0 }
 861 };
 862
 863 struct test_program extended[] = {
 864         { STORE, 1,  1, 1 },
 865         { STORE, 2,  2, 2 },
 866         { STORE, 3,  3, 3 },
 867         { STORE, 4,  4, 4 },
 868         { STORE, 5,  5, 5 },
 869         { STORE, 6,  1, 1 },
 870         { STORE, 7,  2, 2 },
 871         { STORE, 8,  3, 3 },
 872         { STORE, 9,  4, 4 },
 873         { STORE, 10, 5, 5 },
 874         { STORE, 11, 1, 1 },
 875         { STORE, 12, 2, 2 },
 876         { STORE, 13, 3, 3 },
 877         { STORE, 14, 4, 4 },
 878         { STORE, 15, 5, 5 },
 879         { STORE, 16, 1, 1 },
 880         { STORE, 17, 2, 2 },
 881         { STORE, 18, 3, 3 },
 882         { STORE, 19, 4, 4 },
 883         { STORE, 20, 5, 5 },
 884         { STORE, 21, 1, 1 },
 885         { STORE, 22, 2, 2 },
 886         { STORE, 23, 3, 3 },
 887         { STORE, 24, 4, 4 },
 888         { STORE, 25, 5, 5 },
 889         { STORE, 26, 1, 1 },
 890         { STORE, 27, 2, 2 },
 891         { STORE, 28, 3, 3 },
 892         { STORE, 29, 4, 4 },
 893         { STORE, 30, 5, 5 },
 894         { EXIT, 0, 0, 0 }
 895 };
 896
 897 /*
 898  * Setup the variables for doing the inode scan test.
 899  */
 900 static void setup(void)
 901 {
 902         errcode_t       retval;
 903         struct ext2_super_block param;
 904
 905         initialize_ext2_error_table();
 906
 907         memset(&param, 0, sizeof(param));
 908         ext2fs_blocks_count_set(&param, 12000);
 909
 910         retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, &param,
 911                                    test_io_manager, &test_fs);
 912         if (retval) {
 913                 com_err("setup", retval,
 914                         "while initializing filesystem");
 915                 exit(1);
 916         }
 917         retval = ext2fs_allocate_tables(test_fs);
 918         if (retval) {
 919                 com_err("setup", retval,
 920                         "while allocating tables for test filesystem");
 921                 exit(1);
 922         }
 923 }
 924
 925 int run_test(int flags, int size, char *dir, struct test_program *prog)
 926 {
 927         errcode_t       retval;
 928         ext2_icount_t   icount;
 929         struct test_program *pc;
 930         __u16           result;
 931         int             problem = 0;
 932
 933         if (dir) {
 934 #ifdef CONFIG_TDB
 935                 retval = ext2fs_create_icount_tdb(test_fs, dir,
 936                                                   flags, &icount);
 937                 if (retval) {
 938                         com_err("run_test", retval,
 939                                 "while creating icount using tdb");
 940                         exit(1);
 941                 }
 942 #else
 943                 printf("Skipped\n");
 944                 return 0;
 945 #endif
 946         } else {
 947                 retval = ext2fs_create_icount2(test_fs, flags, size, 0,
 948                                                &icount);
 949                 if (retval) {
 950                         com_err("run_test", retval, "while creating icount");
 951                         exit(1);
 952                 }
 953         }
 954         for (pc = prog; pc->cmd != EXIT; pc++) {
 955                 switch (pc->cmd) {
 956                 case FETCH:
 957                         printf("icount_fetch(%u) = ", pc->ino);
 958                         break;
 959                 case STORE:
 960                         retval = ext2fs_icount_store(icount, pc->ino, pc->arg);
 961                         if (retval) {
 962                                 com_err("run_test", retval,
 963                                         "while calling icount_store");
 964                                 exit(1);
 965                         }
 966                         printf("icount_store(%u, %u) = ", pc->ino, pc->arg);
 967                         break;
 968                 case INCREMENT:
 969                         retval = ext2fs_icount_increment(icount, pc->ino, 0);
 970                         if (retval) {
 971                                 com_err("run_test", retval,
 972                                         "while calling icount_increment");
 973                                 exit(1);
 974                         }
 975                         printf("icount_increment(%u) = ", pc->ino);
 976                         break;
 977                 case DECREMENT:
 978                         retval = ext2fs_icount_decrement(icount, pc->ino, 0);
 979                         if (retval) {
 980                                 com_err("run_test", retval,
 981                                         "while calling icount_decrement");
 982                                 exit(1);
 983                         }
 984                         printf("icount_decrement(%u) = ", pc->ino);
 985                         break;
 986                 }
 987                 retval = ext2fs_icount_fetch(icount, pc->ino, &result);
 988                 if (retval) {
 989                         com_err("run_test", retval,
 990                                 "while calling icount_fetch");
 991                         exit(1);
 992                 }
 993                 printf("%u (%s)\n", result, (result == pc->expected) ?
 994                        "OK" : "NOT OK");
 995                 if (result != pc->expected)
 996                         problem++;
 997         }
 998         printf("icount size is %u\n", ext2fs_get_icount_size(icount));
 999         retval = ext2fs_icount_validate(icount, stdout);
1000         if (retval) {
1001                 com_err("run_test", retval, "while calling icount_validate");
1002                 exit(1);
1003         }
1004         ext2fs_free_icount(icount);
1005         return problem;
1006 }
1007
1008
1009 int main(int argc, char **argv)
1010 {
1011         int failed = 0;
1012
1013         setup();
1014         printf("Standard icount run:\n");
1015         failed += run_test(0, 0, 0, prog);
1016         printf("\nMultiple bitmap test:\n");
1017         failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, 0, prog);
1018         printf("\nResizing icount:\n");
1019         failed += run_test(0, 3, 0, extended);
1020         printf("\nStandard icount run with tdb:\n");
1021         failed += run_test(0, 0, ".", prog);
1022         printf("\nMultiple bitmap test with tdb:\n");
1023         failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, ".", prog);
1024         if (failed)
1025                 printf("FAILED!\n");
1026         return failed;
1027 }
1028 #endif