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