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         int                     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, 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         int             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, int size,
 152                                ext2_icount_t *ret)
 153 {
 154         return ext2fs_create_icount2(fs, flags, size, 0, ret);
 155 }
 156
 157 /*
 158  * insert_icount_el() --- Insert a new entry into the sorted list at a
 159  *      specified position.
 160  */
 161 static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
 162                                             ext2_ino_t ino, int pos)
 163 {
 164         struct ext2_icount_el   *el;
 165         errcode_t               retval;
 166         ext2_ino_t                      new_size = 0;
 167         int                     num;
 168
 169         if (icount->count >= icount->size) {
 170                 if (icount->count) {
 171                         new_size = icount->list[(unsigned)icount->count-1].ino;
 172                         new_size = (ext2_ino_t) (icount->count *
 173                                 ((float) icount->num_inodes / new_size));
 174                 }
 175                 if (new_size < (icount->size + 100))
 176                         new_size = icount->size + 100;
 177 #if 0
 178                 printf("Reallocating icount %d entries...\n", new_size);
 179 #endif
 180                 retval = ext2fs_resize_mem((size_t) icount->size *
 181                                            sizeof(struct ext2_icount_el),
 182                                            (size_t) new_size *
 183                                            sizeof(struct ext2_icount_el),
 184                                            &icount->list);
 185                 if (retval)
 186                         return 0;
 187                 icount->size = new_size;
 188         }
 189         num = (int) icount->count - pos;
 190         if (num < 0)
 191                 return 0;       /* should never happen */
 192         if (num) {
 193                 memmove(&icount->list[pos+1], &icount->list[pos],
 194                         sizeof(struct ext2_icount_el) * num);
 195         }
 196         icount->count++;
 197         el = &icount->list[pos];
 198         el->count = 0;
 199         el->ino = ino;
 200         return el;
 201 }
 202
 203 /*
 204  * get_icount_el() --- given an inode number, try to find icount
 205  *      information in the sorted list.  If the create flag is set,
 206  *      and we can't find an entry, create one in the sorted list.
 207  */
 208 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
 209                                             ext2_ino_t ino, int create)
 210 {
 211         float   range;
 212         int     low, high, mid;
 213         ext2_ino_t      lowval, highval;
 214
 215         if (!icount || !icount->list)
 216                 return 0;
 217
 218         if (create && ((icount->count == 0) ||
 219                        (ino > icount->list[(unsigned)icount->count-1].ino))) {
 220                 return insert_icount_el(icount, ino, (unsigned) icount->count);
 221         }
 222         if (icount->count == 0)
 223                 return 0;
 224
 225         if (icount->cursor >= icount->count)
 226                 icount->cursor = 0;
 227         if (ino == icount->list[icount->cursor].ino)
 228                 return &icount->list[icount->cursor++];
 229 #if 0
 230         printf("Non-cursor get_icount_el: %u\n", ino);
 231 #endif
 232         low = 0;
 233         high = (int) icount->count-1;
 234         while (low <= high) {
 235 #if 0
 236                 mid = (low+high)/2;
 237 #else
 238                 if (low == high)
 239                         mid = low;
 240                 else {
 241                         /* Interpolate for efficiency */
 242                         lowval = icount->list[low].ino;
 243                         highval = icount->list[high].ino;
 244
 245                         if (ino < lowval)
 246                                 range = 0;
 247                         else if (ino > highval)
 248                                 range = 1;
 249                         else
 250                                 range = ((float) (ino - lowval)) /
 251                                         (highval - lowval);
 252                         mid = low + ((int) (range * (high-low)));
 253                 }
 254 #endif
 255                 if (ino == icount->list[mid].ino) {
 256                         icount->cursor = mid+1;
 257                         return &icount->list[mid];
 258                 }
 259                 if (ino < icount->list[mid].ino)
 260                         high = mid-1;
 261                 else
 262                         low = mid+1;
 263         }
 264         /*
 265          * If we need to create a new entry, it should be right at
 266          * low (where high will be left at low-1).
 267          */
 268         if (create)
 269                 return insert_icount_el(icount, ino, low);
 270         return 0;
 271 }
 272
 273 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
 274 {
 275         errcode_t       ret = 0;
 276         int             i;
 277         const char *bad = "bad icount";
 278
 279         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 280
 281         if (icount->count > icount->size) {
 282                 fprintf(out, "%s: count > size\n", bad);
 283                 return EXT2_ET_INVALID_ARGUMENT;
 284         }
 285         for (i=1; i < icount->count; i++) {
 286                 if (icount->list[i-1].ino >= icount->list[i].ino) {
 287                         fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
 288                                 bad, i-1, icount->list[i-1].ino,
 289                                 i, icount->list[i].ino);
 290                         ret = EXT2_ET_INVALID_ARGUMENT;
 291                 }
 292         }
 293         return ret;
 294 }
 295
 296 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
 297 {
 298         struct ext2_icount_el   *el;
 299
 300         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 301
 302         if (!ino || (ino > icount->num_inodes))
 303                 return EXT2_ET_INVALID_ARGUMENT;
 304
 305         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 306                 *ret = 1;
 307                 return 0;
 308         }
 309         if (icount->multiple &&
 310             !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 311                 *ret = 0;
 312                 return 0;
 313         }
 314         el = get_icount_el(icount, ino, 0);
 315         if (!el) {
 316                 *ret = 0;
 317                 return 0;
 318         }
 319         *ret = el->count;
 320         return 0;
 321 }
 322
 323 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
 324                                   __u16 *ret)
 325 {
 326         struct ext2_icount_el   *el;
 327
 328         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 329
 330         if (!ino || (ino > icount->num_inodes))
 331                 return EXT2_ET_INVALID_ARGUMENT;
 332
 333         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 334                 /*
 335                  * If the existing count is 1, then we know there is
 336                  * no entry in the list.
 337                  */
 338                 el = get_icount_el(icount, ino, 1);
 339                 if (!el)
 340                         return EXT2_ET_NO_MEMORY;
 341                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 342                 el->count = 2;
 343         } else if (icount->multiple) {
 344                 /*
 345                  * The count is either zero or greater than 1; if the
 346                  * inode is set in icount->multiple, then there should
 347                  * be an entry in the list, so find it using
 348                  * get_icount_el().
 349                  */
 350                 if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
 351                         el = get_icount_el(icount, ino, 1);
 352                         if (!el)
 353                                 return EXT2_ET_NO_MEMORY;
 354                         el->count++;
 355                 } else {
 356                         /*
 357                          * The count was zero; mark the single bitmap
 358                          * and return.
 359                          */
 360                 zero_count:
 361                         ext2fs_mark_inode_bitmap(icount->single, ino);
 362                         if (ret)
 363                                 *ret = 1;
 364                         return 0;
 365                 }
 366         } else {
 367                 /*
 368                  * The count is either zero or greater than 1; try to
 369                  * find an entry in the list to determine which.
 370                  */
 371                 el = get_icount_el(icount, ino, 0);
 372                 if (!el) {
 373                         /* No entry means the count was zero */
 374                         goto zero_count;
 375                 }
 376                 el = get_icount_el(icount, ino, 1);
 377                 if (!el)
 378                         return EXT2_ET_NO_MEMORY;
 379                 el->count++;
 380         }
 381         if (icount->multiple)
 382                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 383         if (ret)
 384                 *ret = el->count;
 385         return 0;
 386 }
 387
 388 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
 389                                   __u16 *ret)
 390 {
 391         struct ext2_icount_el   *el;
 392
 393         if (!ino || (ino > icount->num_inodes))
 394                 return EXT2_ET_INVALID_ARGUMENT;
 395
 396         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 397
 398         if (ext2fs_test_inode_bitmap(icount->single, ino)) {
 399                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 400                 if (icount->multiple)
 401                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 402                 else {
 403                         el = get_icount_el(icount, ino, 0);
 404                         if (el)
 405                                 el->count = 0;
 406                 }
 407                 if (ret)
 408                         *ret = 0;
 409                 return 0;
 410         }
 411
 412         if (icount->multiple &&
 413             !ext2fs_test_inode_bitmap(icount->multiple, ino))
 414                 return EXT2_ET_INVALID_ARGUMENT;
 415
 416         el = get_icount_el(icount, ino, 0);
 417         if (!el || el->count == 0)
 418                 return EXT2_ET_INVALID_ARGUMENT;
 419
 420         el->count--;
 421         if (el->count == 1)
 422                 ext2fs_mark_inode_bitmap(icount->single, ino);
 423         if ((el->count == 0) && icount->multiple)
 424                 ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 425
 426         if (ret)
 427                 *ret = el->count;
 428         return 0;
 429 }
 430
 431 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
 432                               __u16 count)
 433 {
 434         struct ext2_icount_el   *el;
 435
 436         if (!ino || (ino > icount->num_inodes))
 437                 return EXT2_ET_INVALID_ARGUMENT;
 438
 439         EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
 440
 441         if (count == 1) {
 442                 ext2fs_mark_inode_bitmap(icount->single, ino);
 443                 if (icount->multiple)
 444                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 445                 return 0;
 446         }
 447         if (count == 0) {
 448                 ext2fs_unmark_inode_bitmap(icount->single, ino);
 449                 if (icount->multiple) {
 450                         /*
 451                          * If the icount->multiple bitmap is enabled,
 452                          * we can just clear both bitmaps and we're done
 453                          */
 454                         ext2fs_unmark_inode_bitmap(icount->multiple, ino);
 455                 } else {
 456                         el = get_icount_el(icount, ino, 0);
 457                         if (el)
 458                                 el->count = 0;
 459                 }
 460                 return 0;
 461         }
 462
 463         /*
 464          * Get the icount element
 465          */
 466         el = get_icount_el(icount, ino, 1);
 467         if (!el)
 468                 return EXT2_ET_NO_MEMORY;
 469         el->count = count;
 470         ext2fs_unmark_inode_bitmap(icount->single, ino);
 471         if (icount->multiple)
 472                 ext2fs_mark_inode_bitmap(icount->multiple, ino);
 473         return 0;
 474 }
 475
 476 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
 477 {
 478         if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
 479                 return 0;
 480
 481         return icount->size;
 482 }