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.
26 * The data storage strategy used by icount relies on the observation
27 * that most inode counts are either zero (for non-allocated inodes),
28 * one (for most files), and only a few that are two or more
29 * (directories and files that are linked to more than one directory).
31 * Also, e2fsck tends to load the icount data sequentially.
33 * So, we use an inode bitmap to indicate which inodes have a count of
34 * one, and then use a sorted list to store the counts for inodes
35 * which are greater than one.
37 * We also use an optional bitmap to indicate which inodes are already
38 * in the sorted list, to speed up the use of this abstraction by
39 * e2fsck's pass 2. Pass 2 increments inode counts as it finds them,
40 * so this extra bitmap avoids searching the sorted list to see if a
41 * particular inode is on the sorted list already.
44 struct ext2_icount_el
{
51 ext2fs_inode_bitmap single
;
52 ext2fs_inode_bitmap multiple
;
55 ext2_ino_t num_inodes
;
57 struct ext2_icount_el
*list
;
58 struct ext2_icount_el
*last_lookup
;
64 * We now use a 32-bit counter field because it doesn't cost us
65 * anything extra for the in-memory data structure, due to alignment
66 * padding. But there's no point changing the interface if most of
67 * the time we only care if the number is bigger than 65,000 or not.
68 * So use the following translation function to return a 16-bit count.
70 #define icount_16_xlate(x) (((x) > 65500) ? 65500 : (x))
72 void ext2fs_free_icount(ext2_icount_t icount
)
79 ext2fs_free_mem(&icount
->list
);
81 ext2fs_free_inode_bitmap(icount
->single
);
83 ext2fs_free_inode_bitmap(icount
->multiple
);
85 tdb_close(icount
->tdb
);
87 unlink(icount
->tdb_fn
);
91 ext2fs_free_mem(&icount
);
94 static errcode_t
alloc_icount(ext2_filsys fs
, int flags
, ext2_icount_t
*ret
)
101 retval
= ext2fs_get_mem(sizeof(struct ext2_icount
), &icount
);
104 memset(icount
, 0, sizeof(struct ext2_icount
));
106 retval
= ext2fs_allocate_inode_bitmap(fs
, 0, &icount
->single
);
110 if (flags
& EXT2_ICOUNT_OPT_INCREMENT
) {
111 retval
= ext2fs_allocate_inode_bitmap(fs
, 0,
116 icount
->multiple
= 0;
118 icount
->magic
= EXT2_ET_MAGIC_ICOUNT
;
119 icount
->num_inodes
= fs
->super
->s_inodes_count
;
125 ext2fs_free_icount(icount
);
132 __u16 time_hi_and_version
;
137 static void unpack_uuid(void *in
, struct uuid
*uu
)
143 tmp
= (tmp
<< 8) | *ptr
++;
144 tmp
= (tmp
<< 8) | *ptr
++;
145 tmp
= (tmp
<< 8) | *ptr
++;
149 tmp
= (tmp
<< 8) | *ptr
++;
153 tmp
= (tmp
<< 8) | *ptr
++;
154 uu
->time_hi_and_version
= tmp
;
157 tmp
= (tmp
<< 8) | *ptr
++;
160 memcpy(uu
->node
, ptr
, 6);
163 static void uuid_unparse(void *uu
, char *out
)
167 unpack_uuid(uu
, &uuid
);
169 "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
170 uuid
.time_low
, uuid
.time_mid
, uuid
.time_hi_and_version
,
171 uuid
.clock_seq
>> 8, uuid
.clock_seq
& 0xFF,
172 uuid
.node
[0], uuid
.node
[1], uuid
.node
[2],
173 uuid
.node
[3], uuid
.node
[4], uuid
.node
[5]);
176 errcode_t
ext2fs_create_icount_tdb(ext2_filsys fs
, char *tdb_dir
,
177 int flags
, ext2_icount_t
*ret
)
179 ext2_icount_t icount
;
184 retval
= alloc_icount(fs
, flags
, &icount
);
188 retval
= ext2fs_get_mem(strlen(tdb_dir
) + 64, &fn
);
191 uuid_unparse(fs
->super
->s_uuid
, uuid
);
192 sprintf(fn
, "%s/%s-icount-XXXXXX", tdb_dir
, uuid
);
196 icount
->tdb
= tdb_open(fn
, 0, TDB_CLEAR_IF_FIRST
,
197 O_RDWR
| O_CREAT
| O_TRUNC
, 0600);
208 ext2fs_free_icount(icount
);
212 errcode_t
ext2fs_create_icount2(ext2_filsys fs
, int flags
, unsigned int size
,
213 ext2_icount_t hint
, ext2_icount_t
*ret
)
215 ext2_icount_t icount
;
221 EXT2_CHECK_MAGIC(hint
, EXT2_ET_MAGIC_ICOUNT
);
222 if (hint
->size
> size
)
223 size
= (size_t) hint
->size
;
226 retval
= alloc_icount(fs
, flags
, &icount
);
234 * Figure out how many special case inode counts we will
235 * have. We know we will need one for each directory;
236 * we also need to reserve some extra room for file links
238 retval
= ext2fs_get_num_dirs(fs
, &icount
->size
);
241 icount
->size
+= fs
->super
->s_inodes_count
/ 50;
244 bytes
= (size_t) (icount
->size
* sizeof(struct ext2_icount_el
));
246 printf("Icount allocated %u entries, %d bytes.\n",
247 icount
->size
, bytes
);
249 retval
= ext2fs_get_array(icount
->size
, sizeof(struct ext2_icount_el
),
253 memset(icount
->list
, 0, bytes
);
259 * Populate the sorted list with those entries which were
260 * found in the hint icount (since those are ones which will
261 * likely need to be in the sorted list this time around).
264 for (i
=0; i
< hint
->count
; i
++)
265 icount
->list
[i
].ino
= hint
->list
[i
].ino
;
266 icount
->count
= hint
->count
;
273 ext2fs_free_icount(icount
);
277 errcode_t
ext2fs_create_icount(ext2_filsys fs
, int flags
,
281 return ext2fs_create_icount2(fs
, flags
, size
, 0, ret
);
285 * insert_icount_el() --- Insert a new entry into the sorted list at a
286 * specified position.
288 static struct ext2_icount_el
*insert_icount_el(ext2_icount_t icount
,
289 ext2_ino_t ino
, int pos
)
291 struct ext2_icount_el
*el
;
293 ext2_ino_t new_size
= 0;
296 if (icount
->last_lookup
&& icount
->last_lookup
->ino
== ino
)
297 return icount
->last_lookup
;
299 if (icount
->count
>= icount
->size
) {
301 new_size
= icount
->list
[(unsigned)icount
->count
-1].ino
;
302 new_size
= (ext2_ino_t
) (icount
->count
*
303 ((float) icount
->num_inodes
/ new_size
));
305 if (new_size
< (icount
->size
+ 100))
306 new_size
= icount
->size
+ 100;
308 printf("Reallocating icount %u entries...\n", new_size
);
310 retval
= ext2fs_resize_mem((size_t) icount
->size
*
311 sizeof(struct ext2_icount_el
),
313 sizeof(struct ext2_icount_el
),
317 icount
->size
= new_size
;
319 num
= (int) icount
->count
- pos
;
321 return 0; /* should never happen */
323 memmove(&icount
->list
[pos
+1], &icount
->list
[pos
],
324 sizeof(struct ext2_icount_el
) * num
);
327 el
= &icount
->list
[pos
];
330 icount
->last_lookup
= el
;
335 * get_icount_el() --- given an inode number, try to find icount
336 * information in the sorted list. If the create flag is set,
337 * and we can't find an entry, create one in the sorted list.
339 static struct ext2_icount_el
*get_icount_el(ext2_icount_t icount
,
340 ext2_ino_t ino
, int create
)
344 ext2_ino_t lowval
, highval
;
346 if (!icount
|| !icount
->list
)
349 if (create
&& ((icount
->count
== 0) ||
350 (ino
> icount
->list
[(unsigned)icount
->count
-1].ino
))) {
351 return insert_icount_el(icount
, ino
, (unsigned) icount
->count
);
353 if (icount
->count
== 0)
356 if (icount
->cursor
>= icount
->count
)
358 if (ino
== icount
->list
[icount
->cursor
].ino
)
359 return &icount
->list
[icount
->cursor
++];
361 printf("Non-cursor get_icount_el: %u\n", ino
);
364 high
= (int) icount
->count
-1;
365 while (low
<= high
) {
366 mid
= ((unsigned)low
+ (unsigned)high
) >> 1;
367 if (ino
== icount
->list
[mid
].ino
) {
368 icount
->cursor
= mid
+1;
369 return &icount
->list
[mid
];
371 if (ino
< icount
->list
[mid
].ino
)
377 * If we need to create a new entry, it should be right at
378 * low (where high will be left at low-1).
381 return insert_icount_el(icount
, ino
, low
);
385 static errcode_t
set_inode_count(ext2_icount_t icount
, ext2_ino_t ino
,
388 struct ext2_icount_el
*el
;
392 key
.dptr
= (unsigned char *) &ino
;
393 key
.dsize
= sizeof(ext2_ino_t
);
394 data
.dptr
= (unsigned char *) &count
;
395 data
.dsize
= sizeof(__u32
);
397 if (tdb_store(icount
->tdb
, key
, data
, TDB_REPLACE
))
398 return tdb_error(icount
->tdb
) +
401 if (tdb_delete(icount
->tdb
, key
))
402 return tdb_error(icount
->tdb
) +
408 el
= get_icount_el(icount
, ino
, 1);
410 return EXT2_ET_NO_MEMORY
;
416 static errcode_t
get_inode_count(ext2_icount_t icount
, ext2_ino_t ino
,
419 struct ext2_icount_el
*el
;
423 key
.dptr
= (unsigned char *) &ino
;
424 key
.dsize
= sizeof(ext2_ino_t
);
426 data
= tdb_fetch(icount
->tdb
, key
);
427 if (data
.dptr
== NULL
) {
429 return tdb_error(icount
->tdb
) + EXT2_ET_TDB_SUCCESS
;
432 *count
= *((__u32
*) data
.dptr
);
436 el
= get_icount_el(icount
, ino
, 0);
446 errcode_t
ext2fs_icount_validate(ext2_icount_t icount
, FILE *out
)
450 const char *bad
= "bad icount";
452 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
454 if (icount
->count
> icount
->size
) {
455 fprintf(out
, "%s: count > size\n", bad
);
456 return EXT2_ET_INVALID_ARGUMENT
;
458 for (i
=1; i
< icount
->count
; i
++) {
459 if (icount
->list
[i
-1].ino
>= icount
->list
[i
].ino
) {
460 fprintf(out
, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
461 bad
, i
-1, icount
->list
[i
-1].ino
,
462 i
, icount
->list
[i
].ino
);
463 ret
= EXT2_ET_INVALID_ARGUMENT
;
469 errcode_t
ext2fs_icount_fetch(ext2_icount_t icount
, ext2_ino_t ino
, __u16
*ret
)
472 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
474 if (!ino
|| (ino
> icount
->num_inodes
))
475 return EXT2_ET_INVALID_ARGUMENT
;
477 if (ext2fs_test_inode_bitmap2(icount
->single
, ino
)) {
481 if (icount
->multiple
&&
482 !ext2fs_test_inode_bitmap2(icount
->multiple
, ino
)) {
486 get_inode_count(icount
, ino
, &val
);
487 *ret
= icount_16_xlate(val
);
491 errcode_t
ext2fs_icount_increment(ext2_icount_t icount
, ext2_ino_t ino
,
496 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
498 if (!ino
|| (ino
> icount
->num_inodes
))
499 return EXT2_ET_INVALID_ARGUMENT
;
501 if (ext2fs_test_inode_bitmap2(icount
->single
, ino
)) {
503 * If the existing count is 1, then we know there is
504 * no entry in the list.
506 if (set_inode_count(icount
, ino
, 2))
507 return EXT2_ET_NO_MEMORY
;
509 ext2fs_unmark_inode_bitmap2(icount
->single
, ino
);
510 } else if (icount
->multiple
) {
512 * The count is either zero or greater than 1; if the
513 * inode is set in icount->multiple, then there should
514 * be an entry in the list, so we need to fix it.
516 if (ext2fs_test_inode_bitmap2(icount
->multiple
, ino
)) {
517 get_inode_count(icount
, ino
, &curr_value
);
519 if (set_inode_count(icount
, ino
, curr_value
))
520 return EXT2_ET_NO_MEMORY
;
523 * The count was zero; mark the single bitmap
526 ext2fs_mark_inode_bitmap2(icount
->single
, ino
);
533 * The count is either zero or greater than 1; try to
534 * find an entry in the list to determine which.
536 get_inode_count(icount
, ino
, &curr_value
);
538 if (set_inode_count(icount
, ino
, curr_value
))
539 return EXT2_ET_NO_MEMORY
;
541 if (icount
->multiple
)
542 ext2fs_mark_inode_bitmap2(icount
->multiple
, ino
);
544 *ret
= icount_16_xlate(curr_value
);
548 errcode_t
ext2fs_icount_decrement(ext2_icount_t icount
, ext2_ino_t ino
,
553 if (!ino
|| (ino
> icount
->num_inodes
))
554 return EXT2_ET_INVALID_ARGUMENT
;
556 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
558 if (ext2fs_test_inode_bitmap2(icount
->single
, ino
)) {
559 ext2fs_unmark_inode_bitmap2(icount
->single
, ino
);
560 if (icount
->multiple
)
561 ext2fs_unmark_inode_bitmap2(icount
->multiple
, ino
);
563 set_inode_count(icount
, ino
, 0);
570 if (icount
->multiple
&&
571 !ext2fs_test_inode_bitmap2(icount
->multiple
, ino
))
572 return EXT2_ET_INVALID_ARGUMENT
;
574 get_inode_count(icount
, ino
, &curr_value
);
576 return EXT2_ET_INVALID_ARGUMENT
;
578 if (set_inode_count(icount
, ino
, curr_value
))
579 return EXT2_ET_NO_MEMORY
;
582 ext2fs_mark_inode_bitmap2(icount
->single
, ino
);
583 if ((curr_value
== 0) && icount
->multiple
)
584 ext2fs_unmark_inode_bitmap2(icount
->multiple
, ino
);
587 *ret
= icount_16_xlate(curr_value
);
591 errcode_t
ext2fs_icount_store(ext2_icount_t icount
, ext2_ino_t ino
,
594 if (!ino
|| (ino
> icount
->num_inodes
))
595 return EXT2_ET_INVALID_ARGUMENT
;
597 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
600 ext2fs_mark_inode_bitmap2(icount
->single
, ino
);
601 if (icount
->multiple
)
602 ext2fs_unmark_inode_bitmap2(icount
->multiple
, ino
);
606 ext2fs_unmark_inode_bitmap2(icount
->single
, ino
);
607 if (icount
->multiple
) {
609 * If the icount->multiple bitmap is enabled,
610 * we can just clear both bitmaps and we're done
612 ext2fs_unmark_inode_bitmap2(icount
->multiple
, ino
);
614 set_inode_count(icount
, ino
, 0);
618 if (set_inode_count(icount
, ino
, count
))
619 return EXT2_ET_NO_MEMORY
;
620 ext2fs_unmark_inode_bitmap2(icount
->single
, ino
);
621 if (icount
->multiple
)
622 ext2fs_mark_inode_bitmap2(icount
->multiple
, ino
);
626 ext2_ino_t
ext2fs_get_icount_size(ext2_icount_t icount
)
628 if (!icount
|| icount
->magic
!= EXT2_ET_MAGIC_ICOUNT
)
637 ext2_icount_t icount
;
642 #define INCREMENT 0x03
643 #define DECREMENT 0x04
645 struct test_program
{
652 struct test_program prog
[] = {
653 { STORE
, 42, 42, 42 },
659 { INCREMENT
, 5, 0, 1 },
660 { INCREMENT
, 5, 0, 2 },
661 { INCREMENT
, 5, 0, 3 },
662 { INCREMENT
, 5, 0, 4 },
663 { DECREMENT
, 5, 0, 3 },
664 { DECREMENT
, 5, 0, 2 },
665 { DECREMENT
, 5, 0, 1 },
666 { DECREMENT
, 5, 0, 0 },
671 { INCREMENT
, 1, 0, 2 },
672 { DECREMENT
, 2, 0, 1 },
673 { DECREMENT
, 2, 0, 0 },
678 struct test_program extended
[] = {
713 * Setup the variables for doing the inode scan test.
715 static void setup(void)
718 struct ext2_super_block param
;
720 initialize_ext2_error_table();
722 memset(¶m
, 0, sizeof(param
));
723 ext2fs_blocks_count_set(¶m
, 12000);
725 retval
= ext2fs_initialize("test fs", EXT2_FLAG_64BITS
, ¶m
,
726 test_io_manager
, &test_fs
);
728 com_err("setup", retval
,
729 "while initializing filesystem");
732 retval
= ext2fs_allocate_tables(test_fs
);
734 com_err("setup", retval
,
735 "while allocating tables for test filesystem");
740 int run_test(int flags
, int size
, char *dir
, struct test_program
*prog
)
743 ext2_icount_t icount
;
744 struct test_program
*pc
;
749 retval
= ext2fs_create_icount_tdb(test_fs
, dir
,
752 com_err("run_test", retval
,
753 "while creating icount using tdb");
757 retval
= ext2fs_create_icount2(test_fs
, flags
, size
, 0,
760 com_err("run_test", retval
, "while creating icount");
764 for (pc
= prog
; pc
->cmd
!= EXIT
; pc
++) {
767 printf("icount_fetch(%u) = ", pc
->ino
);
770 retval
= ext2fs_icount_store(icount
, pc
->ino
, pc
->arg
);
772 com_err("run_test", retval
,
773 "while calling icount_store");
776 printf("icount_store(%u, %u) = ", pc
->ino
, pc
->arg
);
779 retval
= ext2fs_icount_increment(icount
, pc
->ino
, 0);
781 com_err("run_test", retval
,
782 "while calling icount_increment");
785 printf("icount_increment(%u) = ", pc
->ino
);
788 retval
= ext2fs_icount_decrement(icount
, pc
->ino
, 0);
790 com_err("run_test", retval
,
791 "while calling icount_decrement");
794 printf("icount_decrement(%u) = ", pc
->ino
);
797 retval
= ext2fs_icount_fetch(icount
, pc
->ino
, &result
);
799 com_err("run_test", retval
,
800 "while calling icount_fetch");
803 printf("%u (%s)\n", result
, (result
== pc
->expected
) ?
805 if (result
!= pc
->expected
)
808 printf("icount size is %u\n", ext2fs_get_icount_size(icount
));
809 retval
= ext2fs_icount_validate(icount
, stdout
);
811 com_err("run_test", retval
, "while calling icount_validate");
814 ext2fs_free_icount(icount
);
819 int main(int argc
, char **argv
)
824 printf("Standard icount run:\n");
825 failed
+= run_test(0, 0, 0, prog
);
826 printf("\nMultiple bitmap test:\n");
827 failed
+= run_test(EXT2_ICOUNT_OPT_INCREMENT
, 0, 0, prog
);
828 printf("\nResizing icount:\n");
829 failed
+= run_test(0, 3, 0, extended
);
830 printf("\nStandard icount run with tdb:\n");
831 failed
+= run_test(0, 0, ".", prog
);
832 printf("\nMultiple bitmap test with tdb:\n");
833 failed
+= run_test(EXT2_ICOUNT_OPT_INCREMENT
, 0, ".", prog
);