1 | /*
|
---|
2 | * icount.c --- an efficient inode count abstraction
|
---|
3 | *
|
---|
4 | * Copyright (C) 1997 Theodore Ts'o.
|
---|
5 | *
|
---|
6 | * %Begin-Header%
|
---|
7 | * This file may be redistributed under the terms of the GNU Public
|
---|
8 | * License.
|
---|
9 | * %End-Header%
|
---|
10 | */
|
---|
11 |
|
---|
12 | #if HAVE_UNISTD_H
|
---|
13 | #include <unistd.h>
|
---|
14 | #endif
|
---|
15 | #include <string.h>
|
---|
16 | #include <stdio.h>
|
---|
17 |
|
---|
18 | #include "ext2_fs.h"
|
---|
19 | #include "ext2fs.h"
|
---|
20 |
|
---|
21 | /*
|
---|
22 | * The data storage strategy used by icount relies on the observation
|
---|
23 | * that most inode counts are either zero (for non-allocated inodes),
|
---|
24 | * one (for most files), and only a few that are two or more
|
---|
25 | * (directories and files that are linked to more than one directory).
|
---|
26 | *
|
---|
27 | * Also, e2fsck tends to load the icount data sequentially.
|
---|
28 | *
|
---|
29 | * So, we use an inode bitmap to indicate which inodes have a count of
|
---|
30 | * one, and then use a sorted list to store the counts for inodes
|
---|
31 | * which are greater than one.
|
---|
32 | *
|
---|
33 | * We also use an optional bitmap to indicate which inodes are already
|
---|
34 | * in the sorted list, to speed up the use of this abstraction by
|
---|
35 | * e2fsck's pass 2. Pass 2 increments inode counts as it finds them,
|
---|
36 | * so this extra bitmap avoids searching the sorted list to see if a
|
---|
37 | * particular inode is on the sorted list already.
|
---|
38 | */
|
---|
39 |
|
---|
40 | struct ext2_icount_el {
|
---|
41 | ext2_ino_t ino;
|
---|
42 | __u16 count;
|
---|
43 | };
|
---|
44 |
|
---|
45 | struct ext2_icount {
|
---|
46 | errcode_t magic;
|
---|
47 | ext2fs_inode_bitmap single;
|
---|
48 | ext2fs_inode_bitmap multiple;
|
---|
49 | ext2_ino_t count;
|
---|
50 | ext2_ino_t size;
|
---|
51 | ext2_ino_t num_inodes;
|
---|
52 | ext2_ino_t cursor;
|
---|
53 | struct ext2_icount_el *list;
|
---|
54 | };
|
---|
55 |
|
---|
56 | void ext2fs_free_icount(ext2_icount_t icount)
|
---|
57 | {
|
---|
58 | if (!icount)
|
---|
59 | return;
|
---|
60 |
|
---|
61 | icount->magic = 0;
|
---|
62 | ext2fs_free_mem(&icount->list);
|
---|
63 | ext2fs_free_inode_bitmap(icount->single);
|
---|
64 | ext2fs_free_inode_bitmap(icount->multiple);
|
---|
65 | ext2fs_free_mem(&icount);
|
---|
66 | }
|
---|
67 |
|
---|
68 | errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
|
---|
69 | ext2_icount_t hint, ext2_icount_t *ret)
|
---|
70 | {
|
---|
71 | ext2_icount_t icount;
|
---|
72 | errcode_t retval;
|
---|
73 | size_t bytes;
|
---|
74 | ext2_ino_t i;
|
---|
75 |
|
---|
76 | if (hint) {
|
---|
77 | EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
|
---|
78 | if (hint->size > size)
|
---|
79 | size = (size_t) hint->size;
|
---|
80 | }
|
---|
81 |
|
---|
82 | retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
|
---|
83 | if (retval)
|
---|
84 | return retval;
|
---|
85 | memset(icount, 0, sizeof(struct ext2_icount));
|
---|
86 |
|
---|
87 | retval = ext2fs_allocate_inode_bitmap(fs, 0,
|
---|
88 | &icount->single);
|
---|
89 | if (retval)
|
---|
90 | goto errout;
|
---|
91 |
|
---|
92 | if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
|
---|
93 | retval = ext2fs_allocate_inode_bitmap(fs, 0,
|
---|
94 | &icount->multiple);
|
---|
95 | if (retval)
|
---|
96 | goto errout;
|
---|
97 | } else
|
---|
98 | icount->multiple = 0;
|
---|
99 |
|
---|
100 | if (size) {
|
---|
101 | icount->size = size;
|
---|
102 | } else {
|
---|
103 | /*
|
---|
104 | * Figure out how many special case inode counts we will
|
---|
105 | * have. We know we will need one for each directory;
|
---|
106 | * we also need to reserve some extra room for file links
|
---|
107 | */
|
---|
108 | retval = ext2fs_get_num_dirs(fs, &icount->size);
|
---|
109 | if (retval)
|
---|
110 | goto errout;
|
---|
111 | icount->size += fs->super->s_inodes_count / 50;
|
---|
112 | }
|
---|
113 |
|
---|
114 | bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
|
---|
115 | #if 0
|
---|
116 | printf("Icount allocated %d entries, %d bytes.\n",
|
---|
117 | icount->size, bytes);
|
---|
118 | #endif
|
---|
119 | retval = ext2fs_get_mem(bytes, &icount->list);
|
---|
120 | if (retval)
|
---|
121 | goto errout;
|
---|
122 | memset(icount->list, 0, bytes);
|
---|
123 |
|
---|
124 | icount->magic = EXT2_ET_MAGIC_ICOUNT;
|
---|
125 | icount->count = 0;
|
---|
126 | icount->cursor = 0;
|
---|
127 | icount->num_inodes = fs->super->s_inodes_count;
|
---|
128 |
|
---|
129 | /*
|
---|
130 | * Populate the sorted list with those entries which were
|
---|
131 | * found in the hint icount (since those are ones which will
|
---|
132 | * likely need to be in the sorted list this time around).
|
---|
133 | */
|
---|
134 | if (hint) {
|
---|
135 | for (i=0; i < hint->count; i++)
|
---|
136 | icount->list[i].ino = hint->list[i].ino;
|
---|
137 | icount->count = hint->count;
|
---|
138 | }
|
---|
139 |
|
---|
140 | *ret = icount;
|
---|
141 | return 0;
|
---|
142 |
|
---|
143 | errout:
|
---|
144 | ext2fs_free_icount(icount);
|
---|
145 | return(retval);
|
---|
146 | }
|
---|
147 |
|
---|
148 | errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
|
---|
149 | unsigned int size,
|
---|
150 | ext2_icount_t *ret)
|
---|
151 | {
|
---|
152 | return ext2fs_create_icount2(fs, flags, size, 0, ret);
|
---|
153 | }
|
---|
154 |
|
---|
155 | /*
|
---|
156 | * insert_icount_el() --- Insert a new entry into the sorted list at a
|
---|
157 | * specified position.
|
---|
158 | */
|
---|
159 | static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
|
---|
160 | ext2_ino_t ino, int pos)
|
---|
161 | {
|
---|
162 | struct ext2_icount_el *el;
|
---|
163 | errcode_t retval;
|
---|
164 | ext2_ino_t new_size = 0;
|
---|
165 | int num;
|
---|
166 |
|
---|
167 | if (icount->count >= icount->size) {
|
---|
168 | if (icount->count) {
|
---|
169 | new_size = icount->list[(unsigned)icount->count-1].ino;
|
---|
170 | new_size = (ext2_ino_t) (icount->count *
|
---|
171 | ((float) icount->num_inodes / new_size));
|
---|
172 | }
|
---|
173 | if (new_size < (icount->size + 100))
|
---|
174 | new_size = icount->size + 100;
|
---|
175 | #if 0
|
---|
176 | printf("Reallocating icount %d entries...\n", new_size);
|
---|
177 | #endif
|
---|
178 | retval = ext2fs_resize_mem((size_t) icount->size *
|
---|
179 | sizeof(struct ext2_icount_el),
|
---|
180 | (size_t) new_size *
|
---|
181 | sizeof(struct ext2_icount_el),
|
---|
182 | &icount->list);
|
---|
183 | if (retval)
|
---|
184 | return 0;
|
---|
185 | icount->size = new_size;
|
---|
186 | }
|
---|
187 | num = (int) icount->count - pos;
|
---|
188 | if (num < 0)
|
---|
189 | return 0; /* should never happen */
|
---|
190 | if (num) {
|
---|
191 | memmove(&icount->list[pos+1], &icount->list[pos],
|
---|
192 | sizeof(struct ext2_icount_el) * num);
|
---|
193 | }
|
---|
194 | icount->count++;
|
---|
195 | el = &icount->list[pos];
|
---|
196 | el->count = 0;
|
---|
197 | el->ino = ino;
|
---|
198 | return el;
|
---|
199 | }
|
---|
200 |
|
---|
201 | /*
|
---|
202 | * get_icount_el() --- given an inode number, try to find icount
|
---|
203 | * information in the sorted list. If the create flag is set,
|
---|
204 | * and we can't find an entry, create one in the sorted list.
|
---|
205 | */
|
---|
206 | static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
|
---|
207 | ext2_ino_t ino, int create)
|
---|
208 | {
|
---|
209 | float range;
|
---|
210 | int low, high, mid;
|
---|
211 | ext2_ino_t lowval, highval;
|
---|
212 |
|
---|
213 | if (!icount || !icount->list)
|
---|
214 | return 0;
|
---|
215 |
|
---|
216 | if (create && ((icount->count == 0) ||
|
---|
217 | (ino > icount->list[(unsigned)icount->count-1].ino))) {
|
---|
218 | return insert_icount_el(icount, ino, (unsigned) icount->count);
|
---|
219 | }
|
---|
220 | if (icount->count == 0)
|
---|
221 | return 0;
|
---|
222 |
|
---|
223 | if (icount->cursor >= icount->count)
|
---|
224 | icount->cursor = 0;
|
---|
225 | if (ino == icount->list[icount->cursor].ino)
|
---|
226 | return &icount->list[icount->cursor++];
|
---|
227 | #if 0
|
---|
228 | printf("Non-cursor get_icount_el: %u\n", ino);
|
---|
229 | #endif
|
---|
230 | low = 0;
|
---|
231 | high = (int) icount->count-1;
|
---|
232 | while (low <= high) {
|
---|
233 | #if 0
|
---|
234 | mid = (low+high)/2;
|
---|
235 | #else
|
---|
236 | if (low == high)
|
---|
237 | mid = low;
|
---|
238 | else {
|
---|
239 | /* Interpolate for efficiency */
|
---|
240 | lowval = icount->list[low].ino;
|
---|
241 | highval = icount->list[high].ino;
|
---|
242 |
|
---|
243 | if (ino < lowval)
|
---|
244 | range = 0;
|
---|
245 | else if (ino > highval)
|
---|
246 | range = 1;
|
---|
247 | else
|
---|
248 | range = ((float) (ino - lowval)) /
|
---|
249 | (highval - lowval);
|
---|
250 | mid = low + ((int) (range * (high-low)));
|
---|
251 | }
|
---|
252 | #endif
|
---|
253 | if (ino == icount->list[mid].ino) {
|
---|
254 | icount->cursor = mid+1;
|
---|
255 | return &icount->list[mid];
|
---|
256 | }
|
---|
257 | if (ino < icount->list[mid].ino)
|
---|
258 | high = mid-1;
|
---|
259 | else
|
---|
260 | low = mid+1;
|
---|
261 | }
|
---|
262 | /*
|
---|
263 | * If we need to create a new entry, it should be right at
|
---|
264 | * low (where high will be left at low-1).
|
---|
265 | */
|
---|
266 | if (create)
|
---|
267 | return insert_icount_el(icount, ino, low);
|
---|
268 | return 0;
|
---|
269 | }
|
---|
270 |
|
---|
271 | errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
|
---|
272 | {
|
---|
273 | errcode_t ret = 0;
|
---|
274 | unsigned int i;
|
---|
275 | const char *bad = "bad icount";
|
---|
276 |
|
---|
277 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
|
---|
278 |
|
---|
279 | if (icount->count > icount->size) {
|
---|
280 | fprintf(out, "%s: count > size\n", bad);
|
---|
281 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
282 | }
|
---|
283 | for (i=1; i < icount->count; i++) {
|
---|
284 | if (icount->list[i-1].ino >= icount->list[i].ino) {
|
---|
285 | fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
|
---|
286 | bad, i-1, icount->list[i-1].ino,
|
---|
287 | i, icount->list[i].ino);
|
---|
288 | ret = EXT2_ET_INVALID_ARGUMENT;
|
---|
289 | }
|
---|
290 | }
|
---|
291 | return ret;
|
---|
292 | }
|
---|
293 |
|
---|
294 | errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
|
---|
295 | {
|
---|
296 | struct ext2_icount_el *el;
|
---|
297 |
|
---|
298 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
|
---|
299 |
|
---|
300 | if (!ino || (ino > icount->num_inodes))
|
---|
301 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
302 |
|
---|
303 | if (ext2fs_test_inode_bitmap(icount->single, ino)) {
|
---|
304 | *ret = 1;
|
---|
305 | return 0;
|
---|
306 | }
|
---|
307 | if (icount->multiple &&
|
---|
308 | !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
|
---|
309 | *ret = 0;
|
---|
310 | return 0;
|
---|
311 | }
|
---|
312 | el = get_icount_el(icount, ino, 0);
|
---|
313 | if (!el) {
|
---|
314 | *ret = 0;
|
---|
315 | return 0;
|
---|
316 | }
|
---|
317 | *ret = el->count;
|
---|
318 | return 0;
|
---|
319 | }
|
---|
320 |
|
---|
321 | errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
|
---|
322 | __u16 *ret)
|
---|
323 | {
|
---|
324 | struct ext2_icount_el *el;
|
---|
325 |
|
---|
326 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
|
---|
327 |
|
---|
328 | if (!ino || (ino > icount->num_inodes))
|
---|
329 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
330 |
|
---|
331 | if (ext2fs_test_inode_bitmap(icount->single, ino)) {
|
---|
332 | /*
|
---|
333 | * If the existing count is 1, then we know there is
|
---|
334 | * no entry in the list.
|
---|
335 | */
|
---|
336 | el = get_icount_el(icount, ino, 1);
|
---|
337 | if (!el)
|
---|
338 | return EXT2_ET_NO_MEMORY;
|
---|
339 | ext2fs_unmark_inode_bitmap(icount->single, ino);
|
---|
340 | el->count = 2;
|
---|
341 | } else if (icount->multiple) {
|
---|
342 | /*
|
---|
343 | * The count is either zero or greater than 1; if the
|
---|
344 | * inode is set in icount->multiple, then there should
|
---|
345 | * be an entry in the list, so find it using
|
---|
346 | * get_icount_el().
|
---|
347 | */
|
---|
348 | if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
|
---|
349 | el = get_icount_el(icount, ino, 1);
|
---|
350 | if (!el)
|
---|
351 | return EXT2_ET_NO_MEMORY;
|
---|
352 | el->count++;
|
---|
353 | } else {
|
---|
354 | /*
|
---|
355 | * The count was zero; mark the single bitmap
|
---|
356 | * and return.
|
---|
357 | */
|
---|
358 | zero_count:
|
---|
359 | ext2fs_mark_inode_bitmap(icount->single, ino);
|
---|
360 | if (ret)
|
---|
361 | *ret = 1;
|
---|
362 | return 0;
|
---|
363 | }
|
---|
364 | } else {
|
---|
365 | /*
|
---|
366 | * The count is either zero or greater than 1; try to
|
---|
367 | * find an entry in the list to determine which.
|
---|
368 | */
|
---|
369 | el = get_icount_el(icount, ino, 0);
|
---|
370 | if (!el) {
|
---|
371 | /* No entry means the count was zero */
|
---|
372 | goto zero_count;
|
---|
373 | }
|
---|
374 | el = get_icount_el(icount, ino, 1);
|
---|
375 | if (!el)
|
---|
376 | return EXT2_ET_NO_MEMORY;
|
---|
377 | el->count++;
|
---|
378 | }
|
---|
379 | if (icount->multiple)
|
---|
380 | ext2fs_mark_inode_bitmap(icount->multiple, ino);
|
---|
381 | if (ret)
|
---|
382 | *ret = el->count;
|
---|
383 | return 0;
|
---|
384 | }
|
---|
385 |
|
---|
386 | errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
|
---|
387 | __u16 *ret)
|
---|
388 | {
|
---|
389 | struct ext2_icount_el *el;
|
---|
390 |
|
---|
391 | if (!ino || (ino > icount->num_inodes))
|
---|
392 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
393 |
|
---|
394 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
|
---|
395 |
|
---|
396 | if (ext2fs_test_inode_bitmap(icount->single, ino)) {
|
---|
397 | ext2fs_unmark_inode_bitmap(icount->single, ino);
|
---|
398 | if (icount->multiple)
|
---|
399 | ext2fs_unmark_inode_bitmap(icount->multiple, ino);
|
---|
400 | else {
|
---|
401 | el = get_icount_el(icount, ino, 0);
|
---|
402 | if (el)
|
---|
403 | el->count = 0;
|
---|
404 | }
|
---|
405 | if (ret)
|
---|
406 | *ret = 0;
|
---|
407 | return 0;
|
---|
408 | }
|
---|
409 |
|
---|
410 | if (icount->multiple &&
|
---|
411 | !ext2fs_test_inode_bitmap(icount->multiple, ino))
|
---|
412 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
413 |
|
---|
414 | el = get_icount_el(icount, ino, 0);
|
---|
415 | if (!el || el->count == 0)
|
---|
416 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
417 |
|
---|
418 | el->count--;
|
---|
419 | if (el->count == 1)
|
---|
420 | ext2fs_mark_inode_bitmap(icount->single, ino);
|
---|
421 | if ((el->count == 0) && icount->multiple)
|
---|
422 | ext2fs_unmark_inode_bitmap(icount->multiple, ino);
|
---|
423 |
|
---|
424 | if (ret)
|
---|
425 | *ret = el->count;
|
---|
426 | return 0;
|
---|
427 | }
|
---|
428 |
|
---|
429 | errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
|
---|
430 | __u16 count)
|
---|
431 | {
|
---|
432 | struct ext2_icount_el *el;
|
---|
433 |
|
---|
434 | if (!ino || (ino > icount->num_inodes))
|
---|
435 | return EXT2_ET_INVALID_ARGUMENT;
|
---|
436 |
|
---|
437 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
|
---|
438 |
|
---|
439 | if (count == 1) {
|
---|
440 | ext2fs_mark_inode_bitmap(icount->single, ino);
|
---|
441 | if (icount->multiple)
|
---|
442 | ext2fs_unmark_inode_bitmap(icount->multiple, ino);
|
---|
443 | return 0;
|
---|
444 | }
|
---|
445 | if (count == 0) {
|
---|
446 | ext2fs_unmark_inode_bitmap(icount->single, ino);
|
---|
447 | if (icount->multiple) {
|
---|
448 | /*
|
---|
449 | * If the icount->multiple bitmap is enabled,
|
---|
450 | * we can just clear both bitmaps and we're done
|
---|
451 | */
|
---|
452 | ext2fs_unmark_inode_bitmap(icount->multiple, ino);
|
---|
453 | } else {
|
---|
454 | el = get_icount_el(icount, ino, 0);
|
---|
455 | if (el)
|
---|
456 | el->count = 0;
|
---|
457 | }
|
---|
458 | return 0;
|
---|
459 | }
|
---|
460 |
|
---|
461 | /*
|
---|
462 | * Get the icount element
|
---|
463 | */
|
---|
464 | el = get_icount_el(icount, ino, 1);
|
---|
465 | if (!el)
|
---|
466 | return EXT2_ET_NO_MEMORY;
|
---|
467 | el->count = count;
|
---|
468 | ext2fs_unmark_inode_bitmap(icount->single, ino);
|
---|
469 | if (icount->multiple)
|
---|
470 | ext2fs_mark_inode_bitmap(icount->multiple, ino);
|
---|
471 | return 0;
|
---|
472 | }
|
---|
473 |
|
---|
474 | ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
|
---|
475 | {
|
---|
476 | if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
|
---|
477 | return 0;
|
---|
478 |
|
---|
479 | return icount->size;
|
---|
480 | }
|
---|