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 |
|
---|
41 | struct ext2_icount_el {
|
---|
42 | ext2_ino_t ino;
|
---|
43 | __u16 count;
|
---|
44 | };
|
---|
45 |
|
---|
46 | struct 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 |
|
---|
57 | void 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 |
|
---|
69 | errcode_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 |
|
---|
140 | errout:
|
---|
141 | ext2fs_free_icount(icount);
|
---|
142 | return retval;
|
---|
143 | }
|
---|
144 |
|
---|
145 | errcode_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 | */
|
---|
156 | static 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 | */
|
---|
200 | static 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 |
|
---|
258 | errcode_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 |
|
---|
281 | errcode_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 |
|
---|
308 | errcode_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 |
|
---|
373 | errcode_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 |
|
---|
416 | errcode_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 |
|
---|
461 | ext2_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 | }
|
---|