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 %d 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 %d 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                         mid = low + ((int) (range * (high-low)));
 254                 }
 255 #endif
 256                 if (ino == icount->list[mid].ino) {
 257                         icount->cursor = mid+1;
 258                         return &icount->list[mid];
 259                 }
 260                 if (ino < icount->list[mid].ino)
 261                         high = mid-1;
 262                 else
 263                         low = mid+1;
 264         }
 265         /*
 266          * If we need to create a new entry, it should be right at
 267          * low (where high will be left at low-1).
 268          */
 269         if (create)
 270                 return insert_icount_el(icount, ino, low);
 271         return 0;
 272 }
 273
 274 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
 275 {
 276         errcode_t       ret = 0;
 277         unsigned int    i;
 278         const char *bad = "bad icount";
 279
 280         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 281
 282         if (icount->count > icount->size) {
 283                 fprintf(out, "%s: count > size\n", bad);
 284                 return EXT2_ET_INVALID_ARGUMENT;
 285         }
 286         for (i=1; i < icount->count; i++) {
 287                 if (icount->list[i-1].ino >= icount->list[i].ino) {
 288                         fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
 289                                 bad, i-1, icount->list[i-1].ino,
 290                                 i, icount->list[i].ino);
 291                         ret = EXT2_ET_INVALID_ARGUMENT;
 292                 }
 293         }
 294         return ret;
 295 }
 296
 297 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
 298 {
 299         struct ext2_icount_el   *el;
 300
 301         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 302
 303         if (!ino || (ino > icount->num_inodes))
 304                 return EXT2_ET_INVALID_ARGUMENT;
 305
 306         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 307                 *ret = 1;
 308                 return 0;
 309         }
 310         if (icount->multiple &&
 311             !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 312                 *ret = 0;
 313                 return 0;
 314         }
 315         el = get_icount_el(icount, ino, 0);
 316         if (!el) {
 317                 *ret = 0;
 318                 return 0;
 319         }
 320         *ret = el->count;
 321         return 0;
 322 }
 323
 324 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
 325                                   __u16 *ret)
 326 {
 327         struct ext2_icount_el   *el;
 328
 329         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 330
 331         if (!ino || (ino > icount->num_inodes))
 332                 return EXT2_ET_INVALID_ARGUMENT;
 333
 334         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 335                 /*
 336                  * If the existing count is 1, then we know there is
 337                  * no entry in the list.
 338                  */
 339                 el = get_icount_el(icount, ino, 1);
 340                 if (!el)
 341                         return EXT2_ET_NO_MEMORY;
 342                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 343                 el->count = 2;
 344         } else if (icount->multiple) {
 345                 /*
 346                  * The count is either zero or greater than 1; if the
 347                  * inode is set in icount->multiple, then there should
 348                  * be an entry in the list, so find it using
 349                  * get_icount_el().
 350                  */
 351                 if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 352                         el = get_icount_el(icount, ino, 1);
 353                         if (!el)
 354                                 return EXT2_ET_NO_MEMORY;
 355                         el->count++;
 356                 } else {
 357                         /*
 358                          * The count was zero; mark the single bitmap
 359                          * and return.
 360                          */
 361                 zero_count:
 362                         ext2fs_mark_inode_bitmap(icount->single, ino);
 363                         if (ret)
 364                                 *ret = 1;
 365                         return 0;
 366                 }
 367         } else {
 368                 /*
 369                  * The count is either zero or greater than 1; try to
 370                  * find an entry in the list to determine which.
 371                  */
 372                 el = get_icount_el(icount, ino, 0);
 373                 if (!el) {
 374                         /* No entry means the count was zero */
 375                         goto zero_count;
 376                 }
 377                 el = get_icount_el(icount, ino, 1);
 378                 if (!el)
 379                         return EXT2_ET_NO_MEMORY;
 380                 el->count++;
 381         }
 382         if (icount->multiple)
 383                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 384         if (ret)
 385                 *ret = el->count;
 386         return 0;
 387 }
 388
 389 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
 390                                   __u16 *ret)
 391 {
 392         struct ext2_icount_el   *el;
 393
 394         if (!ino || (ino > icount->num_inodes))
 395                 return EXT2_ET_INVALID_ARGUMENT;
 396
 397         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 398
 399         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 400                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 401                 if (icount->multiple)
 402                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 403                 else {
 404                         el = get_icount_el(icount, ino, 0);
 405                         if (el)
 406                                 el->count = 0;
 407                 }
 408                 if (ret)
 409                         *ret = 0;
 410                 return 0;
 411         }
 412
 413         if (icount->multiple &&
 414             !ext2fs_test_inode_bitmap(icount->multiple, ino))
 415                 return EXT2_ET_INVALID_ARGUMENT;
 416
 417         el = get_icount_el(icount, ino, 0);
 418         if (!el || el->count == 0)
 419                 return EXT2_ET_INVALID_ARGUMENT;
 420
 421         el->count--;
 422         if (el->count == 1)
 423                 ext2fs_mark_inode_bitmap(icount->single, ino);
 424         if ((el->count == 0) && icount->multiple)
 425                 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 426
 427         if (ret)
 428                 *ret = el->count;
 429         return 0;
 430 }
 431
 432 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
 433                               __u16 count)
 434 {
 435         struct ext2_icount_el   *el;
 436
 437         if (!ino || (ino > icount->num_inodes))
 438                 return EXT2_ET_INVALID_ARGUMENT;
 439
 440         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 441
 442         if (count == 1) {
 443                 ext2fs_mark_inode_bitmap(icount->single, ino);
 444                 if (icount->multiple)
 445                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 446                 return 0;
 447         }
 448         if (count == 0) {
 449                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 450                 if (icount->multiple) {
 451                         /*
 452                          * If the icount->multiple bitmap is enabled,
 453                          * we can just clear both bitmaps and we're done
 454                          */
 455                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 456                 } else {
 457                         el = get_icount_el(icount, ino, 0);
 458                         if (el)
 459                                 el->count = 0;
 460                 }
 461                 return 0;
 462         }
 463
 464         /*
 465          * Get the icount element
 466          */
 467         el = get_icount_el(icount, ino, 1);
 468         if (!el)
 469                 return EXT2_ET_NO_MEMORY;
 470         el->count = count;
 471         ext2fs_unmark_inode_bitmap(icount->single, ino);
 472         if (icount->multiple)
 473                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 474         return 0;
 475 }
 476
 477 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
 478 {
 479         if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
 480                 return 0;
 481
 482         return icount->size;
 483 }