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