1 /* vi: set sw=4 ts=4: */
3 * icount.c --- an efficient inode count abstraction
5 * Copyright (C) 1997 Theodore Ts'o.
8 * This file may be redistributed under the terms of the GNU Public
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).
28 * Also, e2fsck tends to load the icount data sequentially.
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.
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.
41 struct ext2_icount_el
{
48 ext2fs_inode_bitmap single
;
49 ext2fs_inode_bitmap multiple
;
52 ext2_ino_t num_inodes
;
54 struct ext2_icount_el
*list
;
57 void ext2fs_free_icount(ext2_icount_t icount
)
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
);
69 errcode_t
ext2fs_create_icount2(ext2_filsys fs
, int flags
, unsigned int size
,
70 ext2_icount_t hint
, ext2_icount_t
*ret
)
78 EXT2_CHECK_MAGIC(hint
, EXT2_ET_MAGIC_ICOUNT
);
79 if (hint
->size
> size
)
80 size
= (size_t) hint
->size
;
83 retval
= ext2fs_get_mem(sizeof(struct ext2_icount
), &icount
);
86 memset(icount
, 0, sizeof(struct ext2_icount
));
88 retval
= ext2fs_allocate_inode_bitmap(fs
, 0,
93 if (flags
& EXT2_ICOUNT_OPT_INCREMENT
) {
94 retval
= ext2fs_allocate_inode_bitmap(fs
, 0,
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
109 retval
= ext2fs_get_num_dirs(fs
, &icount
->size
);
112 icount
->size
+= fs
->super
->s_inodes_count
/ 50;
115 bytes
= (size_t) (icount
->size
* sizeof(struct ext2_icount_el
));
116 retval
= ext2fs_get_mem(bytes
, &icount
->list
);
119 memset(icount
->list
, 0, bytes
);
121 icount
->magic
= EXT2_ET_MAGIC_ICOUNT
;
124 icount
->num_inodes
= fs
->super
->s_inodes_count
;
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).
132 for (i
=0; i
< hint
->count
; i
++)
133 icount
->list
[i
].ino
= hint
->list
[i
].ino
;
134 icount
->count
= hint
->count
;
141 ext2fs_free_icount(icount
);
145 errcode_t
ext2fs_create_icount(ext2_filsys fs
, int flags
,
149 return ext2fs_create_icount2(fs
, flags
, size
, 0, ret
);
153 * insert_icount_el() --- Insert a new entry into the sorted list at a
154 * specified position.
156 static struct ext2_icount_el
*insert_icount_el(ext2_icount_t icount
,
157 ext2_ino_t ino
, int pos
)
159 struct ext2_icount_el
*el
;
161 ext2_ino_t new_size
= 0;
164 if (icount
->count
>= icount
->size
) {
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
));
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
),
175 sizeof(struct ext2_icount_el
),
179 icount
->size
= new_size
;
181 num
= (int) icount
->count
- pos
;
183 return 0; /* should never happen */
185 memmove(&icount
->list
[pos
+1], &icount
->list
[pos
],
186 sizeof(struct ext2_icount_el
) * num
);
189 el
= &icount
->list
[pos
];
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.
200 static struct ext2_icount_el
*get_icount_el(ext2_icount_t icount
,
201 ext2_ino_t ino
, int create
)
205 ext2_ino_t lowval
, highval
;
207 if (!icount
|| !icount
->list
)
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
);
214 if (icount
->count
== 0)
217 if (icount
->cursor
>= icount
->count
)
219 if (ino
== icount
->list
[icount
->cursor
].ino
)
220 return &icount
->list
[icount
->cursor
++];
222 high
= (int) icount
->count
-1;
223 while (low
<= high
) {
227 /* Interpolate for efficiency */
228 lowval
= icount
->list
[low
].ino
;
229 highval
= icount
->list
[high
].ino
;
233 else if (ino
> highval
)
236 range
= ((float) (ino
- lowval
)) /
238 mid
= low
+ ((int) (range
* (high
-low
)));
240 if (ino
== icount
->list
[mid
].ino
) {
241 icount
->cursor
= mid
+1;
242 return &icount
->list
[mid
];
244 if (ino
< icount
->list
[mid
].ino
)
250 * If we need to create a new entry, it should be right at
251 * low (where high will be left at low-1).
254 return insert_icount_el(icount
, ino
, low
);
258 errcode_t
ext2fs_icount_validate(ext2_icount_t icount
, FILE *out
)
262 const char *bad
= "bad icount";
264 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
266 if (icount
->count
> icount
->size
) {
267 fprintf(out
, "%s: count > size\n", bad
);
268 return EXT2_ET_INVALID_ARGUMENT
;
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
;
281 errcode_t
ext2fs_icount_fetch(ext2_icount_t icount
, ext2_ino_t ino
, __u16
*ret
)
283 struct ext2_icount_el
*el
;
285 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
287 if (!ino
|| (ino
> icount
->num_inodes
))
288 return EXT2_ET_INVALID_ARGUMENT
;
290 if (ext2fs_test_inode_bitmap(icount
->single
, ino
)) {
294 if (icount
->multiple
&&
295 !ext2fs_test_inode_bitmap(icount
->multiple
, ino
)) {
299 el
= get_icount_el(icount
, ino
, 0);
308 errcode_t
ext2fs_icount_increment(ext2_icount_t icount
, ext2_ino_t ino
,
311 struct ext2_icount_el
*el
;
313 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
315 if (!ino
|| (ino
> icount
->num_inodes
))
316 return EXT2_ET_INVALID_ARGUMENT
;
318 if (ext2fs_test_inode_bitmap(icount
->single
, ino
)) {
320 * If the existing count is 1, then we know there is
321 * no entry in the list.
323 el
= get_icount_el(icount
, ino
, 1);
325 return EXT2_ET_NO_MEMORY
;
326 ext2fs_unmark_inode_bitmap(icount
->single
, ino
);
328 } else if (icount
->multiple
) {
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
335 if (ext2fs_test_inode_bitmap(icount
->multiple
, ino
)) {
336 el
= get_icount_el(icount
, ino
, 1);
338 return EXT2_ET_NO_MEMORY
;
342 * The count was zero; mark the single bitmap
346 ext2fs_mark_inode_bitmap(icount
->single
, ino
);
353 * The count is either zero or greater than 1; try to
354 * find an entry in the list to determine which.
356 el
= get_icount_el(icount
, ino
, 0);
358 /* No entry means the count was zero */
361 el
= get_icount_el(icount
, ino
, 1);
363 return EXT2_ET_NO_MEMORY
;
366 if (icount
->multiple
)
367 ext2fs_mark_inode_bitmap(icount
->multiple
, ino
);
373 errcode_t
ext2fs_icount_decrement(ext2_icount_t icount
, ext2_ino_t ino
,
376 struct ext2_icount_el
*el
;
378 if (!ino
|| (ino
> icount
->num_inodes
))
379 return EXT2_ET_INVALID_ARGUMENT
;
381 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
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
);
388 el
= get_icount_el(icount
, ino
, 0);
397 if (icount
->multiple
&&
398 !ext2fs_test_inode_bitmap(icount
->multiple
, ino
))
399 return EXT2_ET_INVALID_ARGUMENT
;
401 el
= get_icount_el(icount
, ino
, 0);
402 if (!el
|| el
->count
== 0)
403 return EXT2_ET_INVALID_ARGUMENT
;
407 ext2fs_mark_inode_bitmap(icount
->single
, ino
);
408 if ((el
->count
== 0) && icount
->multiple
)
409 ext2fs_unmark_inode_bitmap(icount
->multiple
, ino
);
416 errcode_t
ext2fs_icount_store(ext2_icount_t icount
, ext2_ino_t ino
,
419 struct ext2_icount_el
*el
;
421 if (!ino
|| (ino
> icount
->num_inodes
))
422 return EXT2_ET_INVALID_ARGUMENT
;
424 EXT2_CHECK_MAGIC(icount
, EXT2_ET_MAGIC_ICOUNT
);
427 ext2fs_mark_inode_bitmap(icount
->single
, ino
);
428 if (icount
->multiple
)
429 ext2fs_unmark_inode_bitmap(icount
->multiple
, ino
);
433 ext2fs_unmark_inode_bitmap(icount
->single
, ino
);
434 if (icount
->multiple
) {
436 * If the icount->multiple bitmap is enabled,
437 * we can just clear both bitmaps and we're done
439 ext2fs_unmark_inode_bitmap(icount
->multiple
, ino
);
441 el
= get_icount_el(icount
, ino
, 0);
449 * Get the icount element
451 el
= get_icount_el(icount
, ino
, 1);
453 return EXT2_ET_NO_MEMORY
;
455 ext2fs_unmark_inode_bitmap(icount
->single
, ino
);
456 if (icount
->multiple
)
457 ext2fs_mark_inode_bitmap(icount
->multiple
, ino
);
461 ext2_ino_t
ext2fs_get_icount_size(ext2_icount_t icount
)
463 if (!icount
|| icount
->magic
!= EXT2_ET_MAGIC_ICOUNT
)