aboutsummaryrefslogtreecommitdiff
path: root/e2fsprogs/ext2fs/icount.c
diff options
context:
space:
mode:
Diffstat (limited to 'e2fsprogs/ext2fs/icount.c')
-rw-r--r--e2fsprogs/ext2fs/icount.c467
1 files changed, 0 insertions, 467 deletions
diff --git a/e2fsprogs/ext2fs/icount.c b/e2fsprogs/ext2fs/icount.c
deleted file mode 100644
index 7ab5f51f4..000000000
--- a/e2fsprogs/ext2fs/icount.c
+++ /dev/null
@@ -1,467 +0,0 @@
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
41struct ext2_icount_el {
42 ext2_ino_t ino;
43 __u16 count;
44};
45
46struct 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
57void 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
69errcode_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
140errout:
141 ext2fs_free_icount(icount);
142 return retval;
143}
144
145errcode_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 */
156static 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 */
200static 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
258errcode_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
281errcode_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
308errcode_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
373errcode_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
416errcode_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
461ext2_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}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-14 13:21:29 +0000