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