blob: 7ab5f51f480cd531820b35e0e9516dae4ce63068
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 | } |
468 |