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 Public
12 #include <et/com_err.h>
21 #include <linux/ext2_fs.h>
25 * The data storage strategy used by icount relies on the observation
26 * that most inode counts are either zero (for non-allocated inodes),
27 * one (for most files), and only a few that are two or more
28 * (directories and files that are linked to more than one directory).
30 * Also, e2fsck tends to load the icount data sequentially.
32 * So, we use an inode bitmap to indicate which inodes have a count of
33 * one, and then use a sorted list to store the counts for inodes
34 * which are greater than one.
36 * We also use an optional bitmap to indicate which inodes are already
37 * in the sorted list, to speed up the use of this abstraction by
38 * e2fsck's pass 2. Pass 2 increments inode counts as it finds them,
39 * so this extra bitmap avoids searching the sorted list to see if a
40 * particular inode is on the sorted list already.
43 struct ext2_icount_el
{
50 ext2fs_inode_bitmap single
;
51 ext2fs_inode_bitmap multiple
;
56 struct ext2_icount_el
*list
;
59 void ext2fs_free_icount(ext2_icount_t icount
)
68 ext2fs_free_inode_bitmap(icount
->single
);
70 ext2fs_free_inode_bitmap(icount
->multiple
);
74 errcode_t
ext2fs_create_icount2(ext2_filsys fs
, int flags
, int size
,
75 ext2_icount_t hint
, ext2_icount_t
*ret
)
83 EXT2_CHECK_MAGIC(hint
, EXT2_ET_MAGIC_ICOUNT
);
84 if (hint
->size
> size
)
88 icount
= malloc(sizeof(struct ext2_icount
));
91 memset(icount
, 0, sizeof(struct ext2_icount
));
93 retval
= ext2fs_allocate_inode_bitmap(fs
, 0,
98 if (flags
& EXT2_ICOUNT_OPT_INCREMENT
) {
99 retval
= ext2fs_allocate_inode_bitmap(fs
, 0,
104 icount
->multiple
= 0;
110 * Figure out how many special case inode counts we will
111 * have. We know we will need one for each directory;
112 * we also need to reserve some extra room for file links
114 retval
= ext2fs_get_num_dirs(fs
, &icount
->size
);
117 icount
->size
+= fs
->super
->s_inodes_count
/ 50;
120 bytes
= icount
->size
* sizeof(struct ext2_icount_el
);
122 printf("Icount allocated %d entries, %d bytes.\n",
123 icount
->size
, bytes
);
125 icount
->list
= malloc(bytes
);
128 memset(icount
->list
, 0, bytes
);
130 icount
->magic
= EXT2_ET_MAGIC_ICOUNT
;
133 icount
->num_inodes
= fs
->super
->s_inodes_count
;
136 * Populate the sorted list with those entries which were
137 * found in the hint icount (since those are ones which will
138 * likely need to be in the sorted list this time around).
141 for (i
=0; i
< hint
->count
; i
++)
142 icount
->list
[i
].ino
= hint
->list
[i
].ino
;
143 icount
->count
= hint
->count
;
150 ext2fs_free_icount(icount
);
154 errcode_t
ext2fs_create_icount(ext2_filsys fs
, int flags
, int size
,
157 return ext2fs_create_icount2(fs
, flags
, size
, 0, ret
);
161 * insert_icount_el() --- Insert a new entry into the sorted list at a
162 * specified position.
164 static struct ext2_icount_el
*insert_icount_el(ext2_icount_t icount
,
167 struct ext2_icount_el
*el
, *new_list
;
171 if (icount
->count
>= icount
->size
) {
173 new_size
= icount
->list
[icount
->count
-1].ino
;
174 new_size
= icount
->count
*
175 ((float) new_size
/ icount
->num_inodes
);
177 if (new_size
< (icount
->size
+ 100))
178 new_size
= icount
->size
+ 100;
180 printf("Reallocating icount %d entries...\n", new_size
);
182 new_list
= realloc(icount
->list
,
183 new_size
* sizeof(struct ext2_icount_el
));
186 icount
->size
= new_size
;
187 icount
->list
= new_list
;
189 num
= icount
->count
- pos
;
191 return 0; /* should never happen */
193 memmove(&icount
->list
[pos
+1], &icount
->list
[pos
],
194 sizeof(struct ext2_icount_el
) * num
);
197 el
= &icount
->list
[pos
];
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.
208 static struct ext2_icount_el
*get_icount_el(ext2_icount_t icount
,
209 ino_t ino
, int create
)
213 ino_t lowval
, highval
;
215 if (!icount
|| !icount
->list
)
218 if (create
&& ((icount
->count
== 0) ||
219 (ino
> icount
->list
[icount
->count
-1].ino
))) {
220 return insert_icount_el(icount
, ino
, icount
->count
);
222 if (icount
->count
== 0)
225 if (icount
->cursor
>= icount
->count
)
227 if (ino
== icount
->list
[icount
->cursor
].ino
)
228 return &icount
->list
[icount
->cursor
++];
230 printf("Non-cursor get_icount_el: %u\n", ino
);
233 high
= icount
->count
-1;
234 while (low
<= high
) {
241 /* Interpolate for efficiency */
242 lowval
= icount
->list
[low
].ino
;
243 highval
= icount
->list
[high
].ino
;
247 else if (ino
> highval
)
250 range
= ((float) (ino
- lowval
)) /
252 mid
= low
+ ((int) (range
* (high
-low
)));
255 if (ino
== icount
->list
[mid
].ino
) {
256 icount
->cursor
= mid
+1;
257 return &icount
->list
[mid
];
259 if (ino
< icount
->list
[mid
].ino
)
265 * If we need to create a new entry, it should be right at
266 * low (where high will be left at low-1).
269 return insert_icount_el(icount
, ino
, low
);
273 errcode_t
ext2fs_icount_validate(ext2_icount_t icount
, FILE *out
)
277 const char *bad
= "bad icount";
279 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
281 if (icount
->count
> icount
->size
) {
282 fprintf(out
, "%s: count > size\n", bad
);
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
);
296 errcode_t
ext2fs_icount_fetch(ext2_icount_t icount
, ino_t ino
, __u16
*ret
)
298 struct ext2_icount_el
*el
;
300 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
302 if (!ino
|| (ino
> icount
->num_inodes
))
305 if (ext2fs_test_inode_bitmap(icount
->single
, ino
)) {
309 if (icount
->multiple
&&
310 !ext2fs_test_inode_bitmap(icount
->multiple
, ino
)) {
314 el
= get_icount_el(icount
, ino
, 0);
323 errcode_t
ext2fs_icount_increment(ext2_icount_t icount
, ino_t ino
,
326 struct ext2_icount_el
*el
;
328 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
330 if (!ino
|| (ino
> icount
->num_inodes
))
333 if (ext2fs_test_inode_bitmap(icount
->single
, ino
)) {
335 * If the existing count is 1, then we know there is
336 * no entry in the list.
338 el
= get_icount_el(icount
, ino
, 1);
341 ext2fs_unmark_inode_bitmap(icount
->single
, ino
);
343 } else if (icount
->multiple
) {
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
350 if (ext2fs_test_inode_bitmap(icount
->multiple
, ino
)) {
351 el
= get_icount_el(icount
, ino
, 1);
357 * The count was zero; mark the single bitmap
361 ext2fs_mark_inode_bitmap(icount
->single
, ino
);
368 * The count is either zero or greater than 1; try to
369 * find an entry in the list to determine which.
371 el
= get_icount_el(icount
, ino
, 0);
373 /* No entry means the count was zero */
376 el
= get_icount_el(icount
, ino
, 1);
381 if (icount
->multiple
)
382 ext2fs_mark_inode_bitmap(icount
->multiple
, ino
);
388 errcode_t
ext2fs_icount_decrement(ext2_icount_t icount
, ino_t ino
,
391 struct ext2_icount_el
*el
;
393 if (!ino
|| (ino
> icount
->num_inodes
))
396 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
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
);
403 el
= get_icount_el(icount
, ino
, 0);
412 if (icount
->multiple
&&
413 !ext2fs_test_inode_bitmap(icount
->multiple
, ino
))
416 el
= get_icount_el(icount
, ino
, 0);
417 if (!el
|| el
->count
== 0)
422 ext2fs_mark_inode_bitmap(icount
->single
, ino
);
423 if ((el
->count
== 0) && icount
->multiple
)
424 ext2fs_unmark_inode_bitmap(icount
->multiple
, ino
);
431 errcode_t
ext2fs_icount_store(ext2_icount_t icount
, ino_t ino
,
434 struct ext2_icount_el
*el
;
436 if (!ino
|| (ino
> icount
->num_inodes
))
439 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
442 ext2fs_mark_inode_bitmap(icount
->single
, ino
);
443 if (icount
->multiple
)
444 ext2fs_unmark_inode_bitmap(icount
->multiple
, ino
);
448 ext2fs_unmark_inode_bitmap(icount
->single
, ino
);
449 if (icount
->multiple
) {
451 * If the icount->multiple bitmap is enabled,
452 * we can just clear both bitmaps and we're done
454 ext2fs_unmark_inode_bitmap(icount
->multiple
, ino
);
456 el
= get_icount_el(icount
, ino
, 0);
464 * Get the icount element
466 el
= get_icount_el(icount
, ino
, 1);
470 ext2fs_unmark_inode_bitmap(icount
->single
, ino
);
471 if (icount
->multiple
)
472 ext2fs_mark_inode_bitmap(icount
->multiple
, ino
);
476 ino_t
ext2fs_get_icount_size(ext2_icount_t icount
)
478 if (!icount
|| icount
->magic
!= EXT2_ET_MAGIC_ICOUNT
)