2 * icount.c --- an efficient inode count abstraction
4 * Copyright (C) 1997 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
27 * The data storage strategy used by icount relies on the observation
28 * that most inode counts are either zero (for non-allocated inodes),
29 * one (for most files), and only a few that are two or more
30 * (directories and files that are linked to more than one directory).
32 * Also, e2fsck tends to load the icount data sequentially.
34 * So, we use an inode bitmap to indicate which inodes have a count of
35 * one, and then use a sorted list to store the counts for inodes
36 * which are greater than one.
38 * We also use an optional bitmap to indicate which inodes are already
39 * in the sorted list, to speed up the use of this abstraction by
40 * e2fsck's pass 2. Pass 2 increments inode counts as it finds them,
41 * so this extra bitmap avoids searching the sorted list to see if a
42 * particular inode is on the sorted list already.
45 struct ext2_icount_el {
52 ext2fs_inode_bitmap single;
53 ext2fs_inode_bitmap multiple;
56 ext2_ino_t num_inodes;
58 struct ext2_icount_el *list;
59 struct ext2_icount_el *last_lookup;
68 * We now use a 32-bit counter field because it doesn't cost us
69 * anything extra for the in-memory data structure, due to alignment
70 * padding. But there's no point changing the interface if most of
71 * the time we only care if the number is bigger than 65,000 or not.
72 * So use the following translation function to return a 16-bit count.
74 #define icount_16_xlate(x) (((x) > 65500) ? 65500 : (x))
76 void ext2fs_free_icount(ext2_icount_t icount)
83 ext2fs_free_mem(&icount->list);
85 ext2fs_free_inode_bitmap(icount->single);
87 ext2fs_free_inode_bitmap(icount->multiple);
90 tdb_close(icount->tdb);
92 (void) unlink(icount->tdb_fn);
98 ext2fs_free_mem(&icount->fullmap);
100 ext2fs_free_mem(&icount);
103 static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret)
105 ext2_icount_t icount;
110 retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
113 memset(icount, 0, sizeof(struct ext2_icount));
114 icount->magic = EXT2_ET_MAGIC_ICOUNT;
115 icount->num_inodes = fs->super->s_inodes_count;
117 if ((flags & EXT2_ICOUNT_OPT_FULLMAP) &&
118 (flags & EXT2_ICOUNT_OPT_INCREMENT)) {
119 unsigned sz = sizeof(*icount->fullmap) * icount->num_inodes;
121 retval = ext2fs_get_mem(sz, &icount->fullmap);
122 /* If we can't allocate, fall back */
124 memset(icount->fullmap, 0, sz);
130 retval = ext2fs_allocate_inode_bitmap(fs, "icount", &icount->single);
134 if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
135 retval = ext2fs_allocate_inode_bitmap(fs, "icount_inc",
140 icount->multiple = 0;
146 ext2fs_free_icount(icount);
154 __u16 time_hi_and_version;
159 static void unpack_uuid(void *in, struct uuid *uu)
165 tmp = (tmp << 8) | *ptr++;
166 tmp = (tmp << 8) | *ptr++;
167 tmp = (tmp << 8) | *ptr++;
171 tmp = (tmp << 8) | *ptr++;
175 tmp = (tmp << 8) | *ptr++;
176 uu->time_hi_and_version = tmp;
179 tmp = (tmp << 8) | *ptr++;
182 memcpy(uu->node, ptr, 6);
185 static void uuid_unparse(void *uu, char *out)
189 unpack_uuid(uu, &uuid);
191 "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
192 uuid.time_low, uuid.time_mid, uuid.time_hi_and_version,
193 uuid.clock_seq >> 8, uuid.clock_seq & 0xFF,
194 uuid.node[0], uuid.node[1], uuid.node[2],
195 uuid.node[3], uuid.node[4], uuid.node[5]);
199 errcode_t ext2fs_create_icount_tdb(ext2_filsys fs EXT2FS_NO_TDB_UNUSED,
200 char *tdb_dir EXT2FS_NO_TDB_UNUSED,
201 int flags EXT2FS_NO_TDB_UNUSED,
202 ext2_icount_t *ret EXT2FS_NO_TDB_UNUSED)
205 ext2_icount_t icount;
208 ext2_ino_t num_inodes;
212 retval = alloc_icount(fs, flags, &icount);
216 retval = ext2fs_get_mem(strlen(tdb_dir) + 64, &fn);
219 uuid_unparse(fs->super->s_uuid, uuid);
220 sprintf(fn, "%s/%s-icount-XXXXXX", tdb_dir, uuid);
221 save_umask = umask(077);
225 ext2fs_free_mem(&fn);
231 * This is an overestimate of the size that we will need; the
232 * ideal value is the number of used inodes with a count
233 * greater than 1. OTOH the times when we really need this is
234 * with the backup programs that use lots of hard links, in
235 * which case the number of inodes in use approaches the ideal
238 num_inodes = fs->super->s_inodes_count - fs->super->s_free_inodes_count;
240 icount->tdb = tdb_open(fn, num_inodes, TDB_NOLOCK | TDB_NOSYNC,
241 O_RDWR | O_CREAT | O_TRUNC, 0600);
243 if (icount->tdb == NULL) {
250 ext2fs_free_icount(icount);
253 return EXT2_ET_UNIMPLEMENTED;
257 errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
258 ext2_icount_t hint, ext2_icount_t *ret)
260 ext2_icount_t icount;
266 EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
267 if (hint->size > size)
268 size = (size_t) hint->size;
271 retval = alloc_icount(fs, flags, &icount);
282 * Figure out how many special case inode counts we will
283 * have. We know we will need one for each directory;
284 * we also need to reserve some extra room for file links
286 retval = ext2fs_get_num_dirs(fs, &icount->size);
289 icount->size += fs->super->s_inodes_count / 50;
292 bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
294 printf("Icount allocated %u entries, %d bytes.\n",
295 icount->size, bytes);
297 retval = ext2fs_get_array(icount->size, sizeof(struct ext2_icount_el),
301 memset(icount->list, 0, bytes);
307 * Populate the sorted list with those entries which were
308 * found in the hint icount (since those are ones which will
309 * likely need to be in the sorted list this time around).
312 for (i=0; i < hint->count; i++)
313 icount->list[i].ino = hint->list[i].ino;
314 icount->count = hint->count;
322 ext2fs_free_icount(icount);
326 errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
330 return ext2fs_create_icount2(fs, flags, size, 0, ret);
334 * insert_icount_el() --- Insert a new entry into the sorted list at a
335 * specified position.
337 static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
338 ext2_ino_t ino, int pos)
340 struct ext2_icount_el *el;
342 ext2_ino_t new_size = 0;
345 if (icount->last_lookup && icount->last_lookup->ino == ino)
346 return icount->last_lookup;
348 if (icount->count >= icount->size) {
350 new_size = icount->list[(unsigned)icount->count-1].ino;
351 new_size = (ext2_ino_t) (icount->count *
352 ((float) icount->num_inodes / new_size));
354 if (new_size < (icount->size + 100))
355 new_size = icount->size + 100;
357 printf("Reallocating icount %u entries...\n", new_size);
359 retval = ext2fs_resize_mem((size_t) icount->size *
360 sizeof(struct ext2_icount_el),
362 sizeof(struct ext2_icount_el),
366 icount->size = new_size;
368 num = (int) icount->count - pos;
370 return 0; /* should never happen */
372 memmove(&icount->list[pos+1], &icount->list[pos],
373 sizeof(struct ext2_icount_el) * num);
376 el = &icount->list[pos];
379 icount->last_lookup = el;
384 * get_icount_el() --- given an inode number, try to find icount
385 * information in the sorted list. If the create flag is set,
386 * and we can't find an entry, create one in the sorted list.
388 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
389 ext2_ino_t ino, int create)
393 if (!icount || !icount->list)
396 if (create && ((icount->count == 0) ||
397 (ino > icount->list[(unsigned)icount->count-1].ino))) {
398 return insert_icount_el(icount, ino, (unsigned) icount->count);
400 if (icount->count == 0)
403 if (icount->cursor >= icount->count)
405 if (ino == icount->list[icount->cursor].ino)
406 return &icount->list[icount->cursor++];
408 printf("Non-cursor get_icount_el: %u\n", ino);
411 high = (int) icount->count-1;
412 while (low <= high) {
413 mid = ((unsigned)low + (unsigned)high) >> 1;
414 if (ino == icount->list[mid].ino) {
415 icount->cursor = mid+1;
416 return &icount->list[mid];
418 if (ino < icount->list[mid].ino)
424 * If we need to create a new entry, it should be right at
425 * low (where high will be left at low-1).
428 return insert_icount_el(icount, ino, low);
432 static errcode_t set_inode_count(ext2_icount_t icount, ext2_ino_t ino,
435 struct ext2_icount_el *el;
440 key.dptr = (unsigned char *) &ino;
441 key.dsize = sizeof(ext2_ino_t);
442 data.dptr = (unsigned char *) &count;
443 data.dsize = sizeof(__u32);
445 if (tdb_store(icount->tdb, key, data, TDB_REPLACE))
446 return tdb_error(icount->tdb) +
449 if (tdb_delete(icount->tdb, key))
450 return tdb_error(icount->tdb) +
456 if (icount->fullmap) {
457 icount->fullmap[ino] = icount_16_xlate(count);
461 el = get_icount_el(icount, ino, 1);
463 return EXT2_ET_NO_MEMORY;
469 static errcode_t get_inode_count(ext2_icount_t icount, ext2_ino_t ino,
472 struct ext2_icount_el *el;
477 key.dptr = (unsigned char *) &ino;
478 key.dsize = sizeof(ext2_ino_t);
480 data = tdb_fetch(icount->tdb, key);
481 if (data.dptr == NULL) {
483 return tdb_error(icount->tdb) + EXT2_ET_TDB_SUCCESS;
486 *count = *((__u32 *) data.dptr);
491 if (icount->fullmap) {
492 *count = icount->fullmap[ino];
496 el = get_icount_el(icount, ino, 0);
506 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
510 const char *bad = "bad icount";
512 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
514 if (icount->count > icount->size) {
515 fprintf(out, "%s: count > size\n", bad);
516 return EXT2_ET_INVALID_ARGUMENT;
518 for (i=1; i < icount->count; i++) {
519 if (icount->list[i-1].ino >= icount->list[i].ino) {
520 fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
521 bad, i-1, icount->list[i-1].ino,
522 i, icount->list[i].ino);
523 ret = EXT2_ET_INVALID_ARGUMENT;
529 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
532 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
534 if (!ino || (ino > icount->num_inodes))
535 return EXT2_ET_INVALID_ARGUMENT;
537 if (!icount->fullmap) {
538 if (ext2fs_test_inode_bitmap2(icount->single, ino)) {
542 if (icount->multiple &&
543 !ext2fs_test_inode_bitmap2(icount->multiple, ino)) {
548 get_inode_count(icount, ino, &val);
549 *ret = icount_16_xlate(val);
553 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
558 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
560 if (!ino || (ino > icount->num_inodes))
561 return EXT2_ET_INVALID_ARGUMENT;
563 if (icount->fullmap) {
564 curr_value = icount_16_xlate(icount->fullmap[ino] + 1);
565 icount->fullmap[ino] = curr_value;
566 } else if (ext2fs_test_inode_bitmap2(icount->single, ino)) {
568 * If the existing count is 1, then we know there is
569 * no entry in the list.
571 if (set_inode_count(icount, ino, 2))
572 return EXT2_ET_NO_MEMORY;
574 ext2fs_unmark_inode_bitmap2(icount->single, ino);
575 } else if (icount->multiple) {
577 * The count is either zero or greater than 1; if the
578 * inode is set in icount->multiple, then there should
579 * be an entry in the list, so we need to fix it.
581 if (ext2fs_test_inode_bitmap2(icount->multiple, ino)) {
582 get_inode_count(icount, ino, &curr_value);
584 if (set_inode_count(icount, ino, curr_value))
585 return EXT2_ET_NO_MEMORY;
588 * The count was zero; mark the single bitmap
591 ext2fs_mark_inode_bitmap2(icount->single, ino);
598 * The count is either zero or greater than 1; try to
599 * find an entry in the list to determine which.
601 get_inode_count(icount, ino, &curr_value);
603 if (set_inode_count(icount, ino, curr_value))
604 return EXT2_ET_NO_MEMORY;
606 if (icount->multiple)
607 ext2fs_mark_inode_bitmap2(icount->multiple, ino);
609 *ret = icount_16_xlate(curr_value);
613 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
618 if (!ino || (ino > icount->num_inodes))
619 return EXT2_ET_INVALID_ARGUMENT;
621 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
623 if (icount->fullmap) {
624 if (!icount->fullmap[ino])
625 return EXT2_ET_INVALID_ARGUMENT;
627 curr_value = --icount->fullmap[ino];
629 *ret = icount_16_xlate(curr_value);
633 if (ext2fs_test_inode_bitmap2(icount->single, ino)) {
634 ext2fs_unmark_inode_bitmap2(icount->single, ino);
635 if (icount->multiple)
636 ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
638 set_inode_count(icount, ino, 0);
645 if (icount->multiple &&
646 !ext2fs_test_inode_bitmap2(icount->multiple, ino))
647 return EXT2_ET_INVALID_ARGUMENT;
649 get_inode_count(icount, ino, &curr_value);
651 return EXT2_ET_INVALID_ARGUMENT;
653 if (set_inode_count(icount, ino, curr_value))
654 return EXT2_ET_NO_MEMORY;
657 ext2fs_mark_inode_bitmap2(icount->single, ino);
658 if ((curr_value == 0) && icount->multiple)
659 ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
662 *ret = icount_16_xlate(curr_value);
666 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
669 if (!ino || (ino > icount->num_inodes))
670 return EXT2_ET_INVALID_ARGUMENT;
672 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
675 return set_inode_count(icount, ino, count);
678 ext2fs_mark_inode_bitmap2(icount->single, ino);
679 if (icount->multiple)
680 ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
684 ext2fs_unmark_inode_bitmap2(icount->single, ino);
685 if (icount->multiple) {
687 * If the icount->multiple bitmap is enabled,
688 * we can just clear both bitmaps and we're done
690 ext2fs_unmark_inode_bitmap2(icount->multiple, ino);
692 set_inode_count(icount, ino, 0);
696 if (set_inode_count(icount, ino, count))
697 return EXT2_ET_NO_MEMORY;
698 ext2fs_unmark_inode_bitmap2(icount->single, ino);
699 if (icount->multiple)
700 ext2fs_mark_inode_bitmap2(icount->multiple, ino);
704 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
706 if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
715 ext2_icount_t icount;
720 #define INCREMENT 0x03
721 #define DECREMENT 0x04
723 struct test_program {
730 struct test_program prog[] = {
731 { STORE, 42, 42, 42 },
737 { INCREMENT, 5, 0, 1 },
738 { INCREMENT, 5, 0, 2 },
739 { INCREMENT, 5, 0, 3 },
740 { INCREMENT, 5, 0, 4 },
741 { DECREMENT, 5, 0, 3 },
742 { DECREMENT, 5, 0, 2 },
743 { DECREMENT, 5, 0, 1 },
744 { DECREMENT, 5, 0, 0 },
749 { INCREMENT, 1, 0, 2 },
750 { DECREMENT, 2, 0, 1 },
751 { DECREMENT, 2, 0, 0 },
756 struct test_program extended[] = {
791 * Setup the variables for doing the inode scan test.
793 static void setup(void)
796 struct ext2_super_block param;
798 initialize_ext2_error_table();
800 memset(¶m, 0, sizeof(param));
801 ext2fs_blocks_count_set(¶m, 12000);
803 retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, ¶m,
804 test_io_manager, &test_fs);
806 com_err("setup", retval,
807 "while initializing filesystem");
810 retval = ext2fs_allocate_tables(test_fs);
812 com_err("setup", retval,
813 "while allocating tables for test filesystem");
818 int run_test(int flags, int size, char *dir, struct test_program *prog)
821 ext2_icount_t icount;
822 struct test_program *pc;
828 retval = ext2fs_create_icount_tdb(test_fs, dir,
831 com_err("run_test", retval,
832 "while creating icount using tdb");
840 retval = ext2fs_create_icount2(test_fs, flags, size, 0,
843 com_err("run_test", retval, "while creating icount");
847 for (pc = prog; pc->cmd != EXIT; pc++) {
850 printf("icount_fetch(%u) = ", pc->ino);
853 retval = ext2fs_icount_store(icount, pc->ino, pc->arg);
855 com_err("run_test", retval,
856 "while calling icount_store");
859 printf("icount_store(%u, %u) = ", pc->ino, pc->arg);
862 retval = ext2fs_icount_increment(icount, pc->ino, 0);
864 com_err("run_test", retval,
865 "while calling icount_increment");
868 printf("icount_increment(%u) = ", pc->ino);
871 retval = ext2fs_icount_decrement(icount, pc->ino, 0);
873 com_err("run_test", retval,
874 "while calling icount_decrement");
877 printf("icount_decrement(%u) = ", pc->ino);
880 retval = ext2fs_icount_fetch(icount, pc->ino, &result);
882 com_err("run_test", retval,
883 "while calling icount_fetch");
886 printf("%u (%s)\n", result, (result == pc->expected) ?
888 if (result != pc->expected)
891 printf("icount size is %u\n", ext2fs_get_icount_size(icount));
892 retval = ext2fs_icount_validate(icount, stdout);
894 com_err("run_test", retval, "while calling icount_validate");
897 ext2fs_free_icount(icount);
902 int main(int argc, char **argv)
907 printf("Standard icount run:\n");
908 failed += run_test(0, 0, 0, prog);
909 printf("\nMultiple bitmap test:\n");
910 failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, 0, prog);
911 printf("\nResizing icount:\n");
912 failed += run_test(0, 3, 0, extended);
913 printf("\nStandard icount run with tdb:\n");
914 failed += run_test(0, 0, ".", prog);
915 printf("\nMultiple bitmap test with tdb:\n");
916 failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, ".", prog);