]>
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% | |
543547a5 TT |
7 | * This file may be redistributed under the terms of the GNU Library |
8 | * General Public License, version 2. | |
19c78dc0 TT |
9 | * %End-Header% |
10 | */ | |
11 | ||
d1154eb4 | 12 | #include "config.h" |
4cbe8af4 | 13 | #if HAVE_UNISTD_H |
19c78dc0 | 14 | #include <unistd.h> |
4cbe8af4 | 15 | #endif |
19c78dc0 TT |
16 | #include <string.h> |
17 | #include <stdio.h> | |
1b9d8cb7 TT |
18 | #include <sys/stat.h> |
19 | #include <fcntl.h> | |
20 | #include <errno.h> | |
19c78dc0 | 21 | |
b5abe6fa | 22 | #include "ext2_fs.h" |
19c78dc0 | 23 | #include "ext2fs.h" |
1b9d8cb7 | 24 | #include "tdb.h" |
19c78dc0 TT |
25 | |
26 | /* | |
27 | * The data storage strategy used by icount relies on the observation | |
28 | * that most inode counts are either zero (for non-allocated inodes), | |
29 | * one (for most files), and only a few that are two or more | |
30 | * (directories and files that are linked to more than one directory). | |
31 | * | |
32 | * Also, e2fsck tends to load the icount data sequentially. | |
33 | * | |
34 | * So, we use an inode bitmap to indicate which inodes have a count of | |
35 | * one, and then use a sorted list to store the counts for inodes | |
36 | * which are greater than one. | |
37 | * | |
38 | * We also use an optional bitmap to indicate which inodes are already | |
39 | * in the sorted list, to speed up the use of this abstraction by | |
40 | * e2fsck's pass 2. Pass 2 increments inode counts as it finds them, | |
41 | * so this extra bitmap avoids searching the sorted list to see if a | |
42 | * particular inode is on the sorted list already. | |
43 | */ | |
44 | ||
45 | struct ext2_icount_el { | |
31dbecd4 | 46 | ext2_ino_t ino; |
60bbd1af | 47 | __u32 count; |
19c78dc0 TT |
48 | }; |
49 | ||
50 | struct ext2_icount { | |
3cb6c502 | 51 | errcode_t magic; |
19c78dc0 TT |
52 | ext2fs_inode_bitmap single; |
53 | ext2fs_inode_bitmap multiple; | |
31dbecd4 TT |
54 | ext2_ino_t count; |
55 | ext2_ino_t size; | |
56 | ext2_ino_t num_inodes; | |
54434927 | 57 | ext2_ino_t cursor; |
19c78dc0 | 58 | struct ext2_icount_el *list; |
1b9d8cb7 | 59 | struct ext2_icount_el *last_lookup; |
749f0712 | 60 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
61 | char *tdb_fn; |
62 | TDB_CONTEXT *tdb; | |
749f0712 | 63 | #endif |
6304d212 | 64 | __u16 *fullmap; |
19c78dc0 TT |
65 | }; |
66 | ||
60bbd1af TT |
67 | /* |
68 | * We now use a 32-bit counter field because it doesn't cost us | |
69 | * anything extra for the in-memory data structure, due to alignment | |
70 | * padding. But there's no point changing the interface if most of | |
71 | * the time we only care if the number is bigger than 65,000 or not. | |
72 | * So use the following translation function to return a 16-bit count. | |
73 | */ | |
74 | #define icount_16_xlate(x) (((x) > 65500) ? 65500 : (x)) | |
75 | ||
19c78dc0 TT |
76 | void ext2fs_free_icount(ext2_icount_t icount) |
77 | { | |
78 | if (!icount) | |
79 | return; | |
80 | ||
81 | icount->magic = 0; | |
82 | if (icount->list) | |
c4e3d3f3 | 83 | ext2fs_free_mem(&icount->list); |
19c78dc0 TT |
84 | if (icount->single) |
85 | ext2fs_free_inode_bitmap(icount->single); | |
86 | if (icount->multiple) | |
87 | ext2fs_free_inode_bitmap(icount->multiple); | |
749f0712 | 88 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
89 | if (icount->tdb) |
90 | tdb_close(icount->tdb); | |
91 | if (icount->tdb_fn) { | |
e97319e2 | 92 | (void) unlink(icount->tdb_fn); |
1b9d8cb7 TT |
93 | free(icount->tdb_fn); |
94 | } | |
749f0712 | 95 | #endif |
1b9d8cb7 | 96 | |
6304d212 JK |
97 | if (icount->fullmap) |
98 | ext2fs_free_mem(&icount->fullmap); | |
99 | ||
c4e3d3f3 | 100 | ext2fs_free_mem(&icount); |
19c78dc0 TT |
101 | } |
102 | ||
1b9d8cb7 | 103 | static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret) |
19c78dc0 TT |
104 | { |
105 | ext2_icount_t icount; | |
106 | errcode_t retval; | |
19c78dc0 | 107 | |
1b9d8cb7 TT |
108 | *ret = 0; |
109 | ||
c4e3d3f3 | 110 | retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount); |
7b4e4534 TT |
111 | if (retval) |
112 | return retval; | |
19c78dc0 | 113 | memset(icount, 0, sizeof(struct ext2_icount)); |
6304d212 JK |
114 | icount->magic = EXT2_ET_MAGIC_ICOUNT; |
115 | icount->num_inodes = fs->super->s_inodes_count; | |
116 | ||
117 | if ((flags & EXT2_ICOUNT_OPT_FULLMAP) && | |
118 | (flags & EXT2_ICOUNT_OPT_INCREMENT)) { | |
119 | unsigned sz = sizeof(*icount->fullmap) * icount->num_inodes; | |
120 | ||
121 | retval = ext2fs_get_mem(sz, &icount->fullmap); | |
122 | /* If we can't allocate, fall back */ | |
123 | if (!retval) { | |
124 | memset(icount->fullmap, 0, sz); | |
125 | *ret = icount; | |
126 | return 0; | |
127 | } | |
128 | } | |
19c78dc0 | 129 | |
9288e3be | 130 | retval = ext2fs_allocate_inode_bitmap(fs, "icount", &icount->single); |
19c78dc0 TT |
131 | if (retval) |
132 | goto errout; | |
133 | ||
134 | if (flags & EXT2_ICOUNT_OPT_INCREMENT) { | |
9288e3be | 135 | retval = ext2fs_allocate_inode_bitmap(fs, "icount_inc", |
19c78dc0 TT |
136 | &icount->multiple); |
137 | if (retval) | |
138 | goto errout; | |
139 | } else | |
140 | icount->multiple = 0; | |
141 | ||
1b9d8cb7 TT |
142 | *ret = icount; |
143 | return 0; | |
144 | ||
145 | errout: | |
146 | ext2fs_free_icount(icount); | |
147 | return(retval); | |
148 | } | |
149 | ||
749f0712 | 150 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
151 | struct uuid { |
152 | __u32 time_low; | |
153 | __u16 time_mid; | |
154 | __u16 time_hi_and_version; | |
155 | __u16 clock_seq; | |
156 | __u8 node[6]; | |
157 | }; | |
158 | ||
159 | static void unpack_uuid(void *in, struct uuid *uu) | |
160 | { | |
161 | __u8 *ptr = in; | |
162 | __u32 tmp; | |
163 | ||
164 | tmp = *ptr++; | |
165 | tmp = (tmp << 8) | *ptr++; | |
166 | tmp = (tmp << 8) | *ptr++; | |
167 | tmp = (tmp << 8) | *ptr++; | |
168 | uu->time_low = tmp; | |
169 | ||
170 | tmp = *ptr++; | |
171 | tmp = (tmp << 8) | *ptr++; | |
172 | uu->time_mid = tmp; | |
173 | ||
174 | tmp = *ptr++; | |
175 | tmp = (tmp << 8) | *ptr++; | |
176 | uu->time_hi_and_version = tmp; | |
177 | ||
178 | tmp = *ptr++; | |
179 | tmp = (tmp << 8) | *ptr++; | |
180 | uu->clock_seq = tmp; | |
181 | ||
182 | memcpy(uu->node, ptr, 6); | |
183 | } | |
184 | ||
185 | static void uuid_unparse(void *uu, char *out) | |
186 | { | |
187 | struct uuid uuid; | |
188 | ||
189 | unpack_uuid(uu, &uuid); | |
190 | sprintf(out, | |
191 | "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x", | |
192 | uuid.time_low, uuid.time_mid, uuid.time_hi_and_version, | |
193 | uuid.clock_seq >> 8, uuid.clock_seq & 0xFF, | |
194 | uuid.node[0], uuid.node[1], uuid.node[2], | |
195 | uuid.node[3], uuid.node[4], uuid.node[5]); | |
196 | } | |
749f0712 | 197 | #endif |
1b9d8cb7 | 198 | |
749f0712 TT |
199 | errcode_t ext2fs_create_icount_tdb(ext2_filsys fs EXT2FS_NO_TDB_UNUSED, |
200 | char *tdb_dir EXT2FS_NO_TDB_UNUSED, | |
201 | int flags EXT2FS_NO_TDB_UNUSED, | |
202 | ext2_icount_t *ret EXT2FS_NO_TDB_UNUSED) | |
1b9d8cb7 | 203 | { |
749f0712 | 204 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
205 | ext2_icount_t icount; |
206 | errcode_t retval; | |
207 | char *fn, uuid[40]; | |
4e523bbe | 208 | ext2_ino_t num_inodes; |
253a9650 | 209 | mode_t save_umask; |
1b9d8cb7 TT |
210 | int fd; |
211 | ||
212 | retval = alloc_icount(fs, flags, &icount); | |
213 | if (retval) | |
214 | return retval; | |
215 | ||
216 | retval = ext2fs_get_mem(strlen(tdb_dir) + 64, &fn); | |
217 | if (retval) | |
218 | goto errout; | |
219 | uuid_unparse(fs->super->s_uuid, uuid); | |
220 | sprintf(fn, "%s/%s-icount-XXXXXX", tdb_dir, uuid); | |
253a9650 | 221 | save_umask = umask(077); |
1b9d8cb7 | 222 | fd = mkstemp(fn); |
1fb1a498 TT |
223 | if (fd < 0) { |
224 | retval = errno; | |
8a6cc1ae | 225 | ext2fs_free_mem(&fn); |
1fb1a498 TT |
226 | goto errout; |
227 | } | |
8a6cc1ae | 228 | icount->tdb_fn = fn; |
253a9650 | 229 | umask(save_umask); |
4e523bbe TT |
230 | /* |
231 | * This is an overestimate of the size that we will need; the | |
232 | * ideal value is the number of used inodes with a count | |
233 | * greater than 1. OTOH the times when we really need this is | |
234 | * with the backup programs that use lots of hard links, in | |
235 | * which case the number of inodes in use approaches the ideal | |
236 | * value. | |
237 | */ | |
238 | num_inodes = fs->super->s_inodes_count - fs->super->s_free_inodes_count; | |
239 | ||
4e523bbe | 240 | icount->tdb = tdb_open(fn, num_inodes, TDB_NOLOCK | TDB_NOSYNC, |
1b9d8cb7 | 241 | O_RDWR | O_CREAT | O_TRUNC, 0600); |
1b9d8cb7 | 242 | close(fd); |
1fb1a498 TT |
243 | if (icount->tdb == NULL) { |
244 | retval = errno; | |
245 | goto errout; | |
246 | } | |
247 | *ret = icount; | |
248 | return 0; | |
1b9d8cb7 TT |
249 | errout: |
250 | ext2fs_free_icount(icount); | |
251 | return(retval); | |
749f0712 TT |
252 | #else |
253 | return EXT2_ET_UNIMPLEMENTED; | |
254 | #endif | |
1b9d8cb7 TT |
255 | } |
256 | ||
257 | errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size, | |
258 | ext2_icount_t hint, ext2_icount_t *ret) | |
259 | { | |
260 | ext2_icount_t icount; | |
261 | errcode_t retval; | |
262 | size_t bytes; | |
263 | ext2_ino_t i; | |
264 | ||
265 | if (hint) { | |
266 | EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT); | |
267 | if (hint->size > size) | |
268 | size = (size_t) hint->size; | |
269 | } | |
270 | ||
271 | retval = alloc_icount(fs, flags, &icount); | |
272 | if (retval) | |
273 | return retval; | |
274 | ||
6304d212 JK |
275 | if (icount->fullmap) |
276 | goto successout; | |
277 | ||
19c78dc0 TT |
278 | if (size) { |
279 | icount->size = size; | |
280 | } else { | |
281 | /* | |
282 | * Figure out how many special case inode counts we will | |
283 | * have. We know we will need one for each directory; | |
284 | * we also need to reserve some extra room for file links | |
285 | */ | |
286 | retval = ext2fs_get_num_dirs(fs, &icount->size); | |
287 | if (retval) | |
288 | goto errout; | |
289 | icount->size += fs->super->s_inodes_count / 50; | |
290 | } | |
1b9d8cb7 | 291 | |
3cb6c502 | 292 | bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el)); |
19c78dc0 | 293 | #if 0 |
d0ff90d5 | 294 | printf("Icount allocated %u entries, %d bytes.\n", |
19c78dc0 TT |
295 | icount->size, bytes); |
296 | #endif | |
ee01079a TT |
297 | retval = ext2fs_get_array(icount->size, sizeof(struct ext2_icount_el), |
298 | &icount->list); | |
7b4e4534 | 299 | if (retval) |
19c78dc0 TT |
300 | goto errout; |
301 | memset(icount->list, 0, bytes); | |
302 | ||
19c78dc0 TT |
303 | icount->count = 0; |
304 | icount->cursor = 0; | |
19c78dc0 | 305 | |
521e3685 TT |
306 | /* |
307 | * Populate the sorted list with those entries which were | |
308 | * found in the hint icount (since those are ones which will | |
309 | * likely need to be in the sorted list this time around). | |
310 | */ | |
311 | if (hint) { | |
312 | for (i=0; i < hint->count; i++) | |
313 | icount->list[i].ino = hint->list[i].ino; | |
314 | icount->count = hint->count; | |
315 | } | |
19c78dc0 | 316 | |
6304d212 | 317 | successout: |
521e3685 | 318 | *ret = icount; |
19c78dc0 TT |
319 | return 0; |
320 | ||
321 | errout: | |
322 | ext2fs_free_icount(icount); | |
323 | return(retval); | |
324 | } | |
325 | ||
1b9d8cb7 | 326 | errcode_t ext2fs_create_icount(ext2_filsys fs, int flags, |
54434927 | 327 | unsigned int size, |
521e3685 | 328 | ext2_icount_t *ret) |
19c78dc0 | 329 | { |
521e3685 | 330 | return ext2fs_create_icount2(fs, flags, size, 0, ret); |
19c78dc0 TT |
331 | } |
332 | ||
333 | /* | |
521e3685 TT |
334 | * insert_icount_el() --- Insert a new entry into the sorted list at a |
335 | * specified position. | |
19c78dc0 | 336 | */ |
521e3685 | 337 | static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount, |
31dbecd4 | 338 | ext2_ino_t ino, int pos) |
19c78dc0 | 339 | { |
7b4e4534 TT |
340 | struct ext2_icount_el *el; |
341 | errcode_t retval; | |
1b9d8cb7 | 342 | ext2_ino_t new_size = 0; |
521e3685 | 343 | int num; |
19c78dc0 | 344 | |
1b9d8cb7 TT |
345 | if (icount->last_lookup && icount->last_lookup->ino == ino) |
346 | return icount->last_lookup; | |
347 | ||
19c78dc0 TT |
348 | if (icount->count >= icount->size) { |
349 | if (icount->count) { | |
3cb6c502 | 350 | new_size = icount->list[(unsigned)icount->count-1].ino; |
1b9d8cb7 | 351 | new_size = (ext2_ino_t) (icount->count * |
30e50b7c | 352 | ((float) icount->num_inodes / new_size)); |
19c78dc0 TT |
353 | } |
354 | if (new_size < (icount->size + 100)) | |
355 | new_size = icount->size + 100; | |
356 | #if 0 | |
d0ff90d5 | 357 | printf("Reallocating icount %u entries...\n", new_size); |
1b9d8cb7 | 358 | #endif |
76f875da TT |
359 | retval = ext2fs_resize_mem((size_t) icount->size * |
360 | sizeof(struct ext2_icount_el), | |
361 | (size_t) new_size * | |
7b4e4534 | 362 | sizeof(struct ext2_icount_el), |
c4e3d3f3 | 363 | &icount->list); |
7b4e4534 | 364 | if (retval) |
19c78dc0 TT |
365 | return 0; |
366 | icount->size = new_size; | |
19c78dc0 | 367 | } |
3cb6c502 | 368 | num = (int) icount->count - pos; |
521e3685 TT |
369 | if (num < 0) |
370 | return 0; /* should never happen */ | |
371 | if (num) { | |
372 | memmove(&icount->list[pos+1], &icount->list[pos], | |
373 | sizeof(struct ext2_icount_el) * num); | |
374 | } | |
375 | icount->count++; | |
376 | el = &icount->list[pos]; | |
377 | el->count = 0; | |
378 | el->ino = ino; | |
1b9d8cb7 | 379 | icount->last_lookup = el; |
521e3685 TT |
380 | return el; |
381 | } | |
382 | ||
383 | /* | |
384 | * get_icount_el() --- given an inode number, try to find icount | |
385 | * information in the sorted list. If the create flag is set, | |
386 | * and we can't find an entry, create one in the sorted list. | |
387 | */ | |
388 | static struct ext2_icount_el *get_icount_el(ext2_icount_t icount, | |
31dbecd4 | 389 | ext2_ino_t ino, int create) |
521e3685 | 390 | { |
521e3685 | 391 | int low, high, mid; |
521e3685 TT |
392 | |
393 | if (!icount || !icount->list) | |
394 | return 0; | |
19c78dc0 | 395 | |
521e3685 | 396 | if (create && ((icount->count == 0) || |
3cb6c502 TT |
397 | (ino > icount->list[(unsigned)icount->count-1].ino))) { |
398 | return insert_icount_el(icount, ino, (unsigned) icount->count); | |
521e3685 TT |
399 | } |
400 | if (icount->count == 0) | |
401 | return 0; | |
1b9d8cb7 | 402 | |
521e3685 TT |
403 | if (icount->cursor >= icount->count) |
404 | icount->cursor = 0; | |
405 | if (ino == icount->list[icount->cursor].ino) | |
406 | return &icount->list[icount->cursor++]; | |
407 | #if 0 | |
408 | printf("Non-cursor get_icount_el: %u\n", ino); | |
409 | #endif | |
410 | low = 0; | |
3cb6c502 | 411 | high = (int) icount->count-1; |
521e3685 | 412 | while (low <= high) { |
a4aff9ca | 413 | mid = ((unsigned)low + (unsigned)high) >> 1; |
521e3685 TT |
414 | if (ino == icount->list[mid].ino) { |
415 | icount->cursor = mid+1; | |
416 | return &icount->list[mid]; | |
417 | } | |
418 | if (ino < icount->list[mid].ino) | |
419 | high = mid-1; | |
420 | else | |
421 | low = mid+1; | |
422 | } | |
19c78dc0 | 423 | /* |
521e3685 TT |
424 | * If we need to create a new entry, it should be right at |
425 | * low (where high will be left at low-1). | |
19c78dc0 | 426 | */ |
521e3685 TT |
427 | if (create) |
428 | return insert_icount_el(icount, ino, low); | |
429 | return 0; | |
430 | } | |
431 | ||
1b9d8cb7 | 432 | static errcode_t set_inode_count(ext2_icount_t icount, ext2_ino_t ino, |
60bbd1af | 433 | __u32 count) |
1b9d8cb7 TT |
434 | { |
435 | struct ext2_icount_el *el; | |
749f0712 | 436 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
437 | TDB_DATA key, data; |
438 | ||
439 | if (icount->tdb) { | |
440 | key.dptr = (unsigned char *) &ino; | |
441 | key.dsize = sizeof(ext2_ino_t); | |
442 | data.dptr = (unsigned char *) &count; | |
60bbd1af | 443 | data.dsize = sizeof(__u32); |
1b9d8cb7 TT |
444 | if (count) { |
445 | if (tdb_store(icount->tdb, key, data, TDB_REPLACE)) | |
446 | return tdb_error(icount->tdb) + | |
447 | EXT2_ET_TDB_SUCCESS; | |
448 | } else { | |
449 | if (tdb_delete(icount->tdb, key)) | |
450 | return tdb_error(icount->tdb) + | |
451 | EXT2_ET_TDB_SUCCESS; | |
452 | } | |
453 | return 0; | |
454 | } | |
749f0712 | 455 | #endif |
6304d212 JK |
456 | if (icount->fullmap) { |
457 | icount->fullmap[ino] = icount_16_xlate(count); | |
458 | return 0; | |
459 | } | |
460 | ||
1b9d8cb7 TT |
461 | el = get_icount_el(icount, ino, 1); |
462 | if (!el) | |
463 | return EXT2_ET_NO_MEMORY; | |
464 | ||
465 | el->count = count; | |
466 | return 0; | |
467 | } | |
468 | ||
469 | static errcode_t get_inode_count(ext2_icount_t icount, ext2_ino_t ino, | |
60bbd1af | 470 | __u32 *count) |
1b9d8cb7 TT |
471 | { |
472 | struct ext2_icount_el *el; | |
749f0712 | 473 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
474 | TDB_DATA key, data; |
475 | ||
476 | if (icount->tdb) { | |
477 | key.dptr = (unsigned char *) &ino; | |
478 | key.dsize = sizeof(ext2_ino_t); | |
479 | ||
480 | data = tdb_fetch(icount->tdb, key); | |
481 | if (data.dptr == NULL) { | |
482 | *count = 0; | |
483 | return tdb_error(icount->tdb) + EXT2_ET_TDB_SUCCESS; | |
484 | } | |
485 | ||
60bbd1af | 486 | *count = *((__u32 *) data.dptr); |
a1f64272 | 487 | free(data.dptr); |
1b9d8cb7 TT |
488 | return 0; |
489 | } | |
749f0712 | 490 | #endif |
6304d212 JK |
491 | if (icount->fullmap) { |
492 | *count = icount->fullmap[ino]; | |
493 | return 0; | |
494 | } | |
495 | ||
1b9d8cb7 TT |
496 | el = get_icount_el(icount, ino, 0); |
497 | if (!el) { | |
498 | *count = 0; | |
499 | return ENOENT; | |
500 | } | |
501 | ||
502 | *count = el->count; | |
503 | return 0; | |
504 | } | |
505 | ||
521e3685 TT |
506 | errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out) |
507 | { | |
508 | errcode_t ret = 0; | |
54434927 | 509 | unsigned int i; |
521e3685 | 510 | const char *bad = "bad icount"; |
1b9d8cb7 | 511 | |
521e3685 TT |
512 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); |
513 | ||
514 | if (icount->count > icount->size) { | |
515 | fprintf(out, "%s: count > size\n", bad); | |
1f0b6c1f | 516 | return EXT2_ET_INVALID_ARGUMENT; |
521e3685 TT |
517 | } |
518 | for (i=1; i < icount->count; i++) { | |
519 | if (icount->list[i-1].ino >= icount->list[i].ino) { | |
31dbecd4 | 520 | fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n", |
521e3685 TT |
521 | bad, i-1, icount->list[i-1].ino, |
522 | i, icount->list[i].ino); | |
1f0b6c1f | 523 | ret = EXT2_ET_INVALID_ARGUMENT; |
19c78dc0 | 524 | } |
19c78dc0 | 525 | } |
521e3685 | 526 | return ret; |
19c78dc0 | 527 | } |
19c78dc0 | 528 | |
31dbecd4 | 529 | errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret) |
19c78dc0 | 530 | { |
60bbd1af | 531 | __u32 val; |
19c78dc0 TT |
532 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); |
533 | ||
521e3685 | 534 | if (!ino || (ino > icount->num_inodes)) |
1f0b6c1f | 535 | return EXT2_ET_INVALID_ARGUMENT; |
521e3685 | 536 | |
6304d212 JK |
537 | if (!icount->fullmap) { |
538 | if (ext2fs_test_inode_bitmap2(icount->single, ino)) { | |
539 | *ret = 1; | |
540 | return 0; | |
541 | } | |
542 | if (icount->multiple && | |
543 | !ext2fs_test_inode_bitmap2(icount->multiple, ino)) { | |
544 | *ret = 0; | |
545 | return 0; | |
546 | } | |
521e3685 | 547 | } |
60bbd1af TT |
548 | get_inode_count(icount, ino, &val); |
549 | *ret = icount_16_xlate(val); | |
19c78dc0 TT |
550 | return 0; |
551 | } | |
552 | ||
31dbecd4 | 553 | errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino, |
19c78dc0 TT |
554 | __u16 *ret) |
555 | { | |
60bbd1af | 556 | __u32 curr_value; |
19c78dc0 TT |
557 | |
558 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); | |
559 | ||
521e3685 | 560 | if (!ino || (ino > icount->num_inodes)) |
1f0b6c1f | 561 | return EXT2_ET_INVALID_ARGUMENT; |
521e3685 | 562 | |
6304d212 JK |
563 | if (icount->fullmap) { |
564 | curr_value = icount_16_xlate(icount->fullmap[ino] + 1); | |
565 | icount->fullmap[ino] = curr_value; | |
566 | } else if (ext2fs_test_inode_bitmap2(icount->single, ino)) { | |
19c78dc0 TT |
567 | /* |
568 | * If the existing count is 1, then we know there is | |
521e3685 | 569 | * no entry in the list. |
19c78dc0 | 570 | */ |
1b9d8cb7 | 571 | if (set_inode_count(icount, ino, 2)) |
1f0b6c1f | 572 | return EXT2_ET_NO_MEMORY; |
1b9d8cb7 | 573 | curr_value = 2; |
8f82ef98 | 574 | ext2fs_unmark_inode_bitmap2(icount->single, ino); |
19c78dc0 TT |
575 | } else if (icount->multiple) { |
576 | /* | |
577 | * The count is either zero or greater than 1; if the | |
578 | * inode is set in icount->multiple, then there should | |
1b9d8cb7 | 579 | * be an entry in the list, so we need to fix it. |
19c78dc0 | 580 | */ |
8f82ef98 | 581 | if (ext2fs_test_inode_bitmap2(icount->multiple, ino)) { |
1b9d8cb7 TT |
582 | get_inode_count(icount, ino, &curr_value); |
583 | curr_value++; | |
584 | if (set_inode_count(icount, ino, curr_value)) | |
1f0b6c1f | 585 | return EXT2_ET_NO_MEMORY; |
19c78dc0 TT |
586 | } else { |
587 | /* | |
588 | * The count was zero; mark the single bitmap | |
589 | * and return. | |
590 | */ | |
8f82ef98 | 591 | ext2fs_mark_inode_bitmap2(icount->single, ino); |
19c78dc0 TT |
592 | if (ret) |
593 | *ret = 1; | |
594 | return 0; | |
595 | } | |
596 | } else { | |
597 | /* | |
598 | * The count is either zero or greater than 1; try to | |
599 | * find an entry in the list to determine which. | |
600 | */ | |
1b9d8cb7 TT |
601 | get_inode_count(icount, ino, &curr_value); |
602 | curr_value++; | |
603 | if (set_inode_count(icount, ino, curr_value)) | |
1f0b6c1f | 604 | return EXT2_ET_NO_MEMORY; |
521e3685 | 605 | } |
19c78dc0 | 606 | if (icount->multiple) |
8f82ef98 | 607 | ext2fs_mark_inode_bitmap2(icount->multiple, ino); |
19c78dc0 | 608 | if (ret) |
60bbd1af | 609 | *ret = icount_16_xlate(curr_value); |
19c78dc0 TT |
610 | return 0; |
611 | } | |
612 | ||
31dbecd4 | 613 | errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino, |
19c78dc0 TT |
614 | __u16 *ret) |
615 | { | |
60bbd1af | 616 | __u32 curr_value; |
19c78dc0 | 617 | |
521e3685 | 618 | if (!ino || (ino > icount->num_inodes)) |
1f0b6c1f | 619 | return EXT2_ET_INVALID_ARGUMENT; |
521e3685 | 620 | |
19c78dc0 TT |
621 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); |
622 | ||
6304d212 JK |
623 | if (icount->fullmap) { |
624 | if (!icount->fullmap[ino]) | |
625 | return EXT2_ET_INVALID_ARGUMENT; | |
626 | ||
627 | curr_value = --icount->fullmap[ino]; | |
628 | if (ret) | |
629 | *ret = icount_16_xlate(curr_value); | |
630 | return 0; | |
631 | } | |
632 | ||
8f82ef98 VAH |
633 | if (ext2fs_test_inode_bitmap2(icount->single, ino)) { |
634 | ext2fs_unmark_inode_bitmap2(icount->single, ino); | |
19c78dc0 | 635 | if (icount->multiple) |
8f82ef98 | 636 | ext2fs_unmark_inode_bitmap2(icount->multiple, ino); |
19c78dc0 | 637 | else { |
1b9d8cb7 | 638 | set_inode_count(icount, ino, 0); |
19c78dc0 TT |
639 | } |
640 | if (ret) | |
641 | *ret = 0; | |
642 | return 0; | |
643 | } | |
644 | ||
521e3685 | 645 | if (icount->multiple && |
8f82ef98 | 646 | !ext2fs_test_inode_bitmap2(icount->multiple, ino)) |
1f0b6c1f | 647 | return EXT2_ET_INVALID_ARGUMENT; |
1b9d8cb7 TT |
648 | |
649 | get_inode_count(icount, ino, &curr_value); | |
650 | if (!curr_value) | |
1f0b6c1f | 651 | return EXT2_ET_INVALID_ARGUMENT; |
1b9d8cb7 TT |
652 | curr_value--; |
653 | if (set_inode_count(icount, ino, curr_value)) | |
654 | return EXT2_ET_NO_MEMORY; | |
19c78dc0 | 655 | |
1b9d8cb7 | 656 | if (curr_value == 1) |
8f82ef98 | 657 | ext2fs_mark_inode_bitmap2(icount->single, ino); |
1b9d8cb7 | 658 | if ((curr_value == 0) && icount->multiple) |
8f82ef98 | 659 | ext2fs_unmark_inode_bitmap2(icount->multiple, ino); |
19c78dc0 TT |
660 | |
661 | if (ret) | |
60bbd1af | 662 | *ret = icount_16_xlate(curr_value); |
19c78dc0 TT |
663 | return 0; |
664 | } | |
665 | ||
31dbecd4 | 666 | errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino, |
19c78dc0 TT |
667 | __u16 count) |
668 | { | |
521e3685 | 669 | if (!ino || (ino > icount->num_inodes)) |
1f0b6c1f | 670 | return EXT2_ET_INVALID_ARGUMENT; |
521e3685 | 671 | |
19c78dc0 TT |
672 | EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); |
673 | ||
6304d212 JK |
674 | if (icount->fullmap) |
675 | return set_inode_count(icount, ino, count); | |
676 | ||
19c78dc0 | 677 | if (count == 1) { |
8f82ef98 | 678 | ext2fs_mark_inode_bitmap2(icount->single, ino); |
19c78dc0 | 679 | if (icount->multiple) |
8f82ef98 | 680 | ext2fs_unmark_inode_bitmap2(icount->multiple, ino); |
19c78dc0 TT |
681 | return 0; |
682 | } | |
683 | if (count == 0) { | |
8f82ef98 | 684 | ext2fs_unmark_inode_bitmap2(icount->single, ino); |
19c78dc0 TT |
685 | if (icount->multiple) { |
686 | /* | |
687 | * If the icount->multiple bitmap is enabled, | |
688 | * we can just clear both bitmaps and we're done | |
689 | */ | |
8f82ef98 | 690 | ext2fs_unmark_inode_bitmap2(icount->multiple, ino); |
1b9d8cb7 TT |
691 | } else |
692 | set_inode_count(icount, ino, 0); | |
19c78dc0 TT |
693 | return 0; |
694 | } | |
695 | ||
1b9d8cb7 | 696 | if (set_inode_count(icount, ino, count)) |
1f0b6c1f | 697 | return EXT2_ET_NO_MEMORY; |
8f82ef98 | 698 | ext2fs_unmark_inode_bitmap2(icount->single, ino); |
19c78dc0 | 699 | if (icount->multiple) |
8f82ef98 | 700 | ext2fs_mark_inode_bitmap2(icount->multiple, ino); |
19c78dc0 TT |
701 | return 0; |
702 | } | |
703 | ||
31dbecd4 | 704 | ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount) |
19c78dc0 TT |
705 | { |
706 | if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT) | |
707 | return 0; | |
708 | ||
709 | return icount->size; | |
710 | } | |
1cb78d84 TT |
711 | |
712 | #ifdef DEBUG | |
713 | ||
714 | ext2_filsys test_fs; | |
715 | ext2_icount_t icount; | |
716 | ||
717 | #define EXIT 0x00 | |
718 | #define FETCH 0x01 | |
719 | #define STORE 0x02 | |
720 | #define INCREMENT 0x03 | |
721 | #define DECREMENT 0x04 | |
722 | ||
723 | struct test_program { | |
724 | int cmd; | |
725 | ext2_ino_t ino; | |
726 | __u16 arg; | |
727 | __u16 expected; | |
728 | }; | |
729 | ||
730 | struct test_program prog[] = { | |
731 | { STORE, 42, 42, 42 }, | |
732 | { STORE, 1, 1, 1 }, | |
733 | { STORE, 2, 2, 2 }, | |
734 | { STORE, 3, 3, 3 }, | |
735 | { STORE, 10, 1, 1 }, | |
736 | { STORE, 42, 0, 0 }, | |
737 | { INCREMENT, 5, 0, 1 }, | |
738 | { INCREMENT, 5, 0, 2 }, | |
739 | { INCREMENT, 5, 0, 3 }, | |
740 | { INCREMENT, 5, 0, 4 }, | |
741 | { DECREMENT, 5, 0, 3 }, | |
742 | { DECREMENT, 5, 0, 2 }, | |
743 | { DECREMENT, 5, 0, 1 }, | |
744 | { DECREMENT, 5, 0, 0 }, | |
745 | { FETCH, 10, 0, 1 }, | |
746 | { FETCH, 1, 0, 1 }, | |
747 | { FETCH, 2, 0, 2 }, | |
748 | { FETCH, 3, 0, 3 }, | |
749 | { INCREMENT, 1, 0, 2 }, | |
750 | { DECREMENT, 2, 0, 1 }, | |
751 | { DECREMENT, 2, 0, 0 }, | |
752 | { FETCH, 12, 0, 0 }, | |
753 | { EXIT, 0, 0, 0 } | |
754 | }; | |
755 | ||
756 | struct test_program extended[] = { | |
757 | { STORE, 1, 1, 1 }, | |
758 | { STORE, 2, 2, 2 }, | |
759 | { STORE, 3, 3, 3 }, | |
760 | { STORE, 4, 4, 4 }, | |
761 | { STORE, 5, 5, 5 }, | |
762 | { STORE, 6, 1, 1 }, | |
763 | { STORE, 7, 2, 2 }, | |
764 | { STORE, 8, 3, 3 }, | |
765 | { STORE, 9, 4, 4 }, | |
766 | { STORE, 10, 5, 5 }, | |
767 | { STORE, 11, 1, 1 }, | |
768 | { STORE, 12, 2, 2 }, | |
769 | { STORE, 13, 3, 3 }, | |
770 | { STORE, 14, 4, 4 }, | |
771 | { STORE, 15, 5, 5 }, | |
772 | { STORE, 16, 1, 1 }, | |
773 | { STORE, 17, 2, 2 }, | |
774 | { STORE, 18, 3, 3 }, | |
775 | { STORE, 19, 4, 4 }, | |
776 | { STORE, 20, 5, 5 }, | |
777 | { STORE, 21, 1, 1 }, | |
778 | { STORE, 22, 2, 2 }, | |
779 | { STORE, 23, 3, 3 }, | |
780 | { STORE, 24, 4, 4 }, | |
781 | { STORE, 25, 5, 5 }, | |
782 | { STORE, 26, 1, 1 }, | |
783 | { STORE, 27, 2, 2 }, | |
784 | { STORE, 28, 3, 3 }, | |
785 | { STORE, 29, 4, 4 }, | |
786 | { STORE, 30, 5, 5 }, | |
787 | { EXIT, 0, 0, 0 } | |
788 | }; | |
789 | ||
790 | /* | |
791 | * Setup the variables for doing the inode scan test. | |
792 | */ | |
793 | static void setup(void) | |
794 | { | |
795 | errcode_t retval; | |
1cb78d84 TT |
796 | struct ext2_super_block param; |
797 | ||
798 | initialize_ext2_error_table(); | |
799 | ||
800 | memset(¶m, 0, sizeof(param)); | |
4efbac6f | 801 | ext2fs_blocks_count_set(¶m, 12000); |
1cb78d84 | 802 | |
8f82ef98 | 803 | retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, ¶m, |
1cb78d84 TT |
804 | test_io_manager, &test_fs); |
805 | if (retval) { | |
806 | com_err("setup", retval, | |
807 | "while initializing filesystem"); | |
808 | exit(1); | |
809 | } | |
810 | retval = ext2fs_allocate_tables(test_fs); | |
811 | if (retval) { | |
812 | com_err("setup", retval, | |
813 | "while allocating tables for test filesystem"); | |
814 | exit(1); | |
815 | } | |
816 | } | |
817 | ||
1b9d8cb7 | 818 | int run_test(int flags, int size, char *dir, struct test_program *prog) |
1cb78d84 TT |
819 | { |
820 | errcode_t retval; | |
821 | ext2_icount_t icount; | |
822 | struct test_program *pc; | |
823 | __u16 result; | |
824 | int problem = 0; | |
825 | ||
1b9d8cb7 | 826 | if (dir) { |
749f0712 | 827 | #ifdef CONFIG_TDB |
1b9d8cb7 TT |
828 | retval = ext2fs_create_icount_tdb(test_fs, dir, |
829 | flags, &icount); | |
830 | if (retval) { | |
831 | com_err("run_test", retval, | |
832 | "while creating icount using tdb"); | |
833 | exit(1); | |
834 | } | |
749f0712 TT |
835 | #else |
836 | printf("Skipped\n"); | |
837 | return 0; | |
838 | #endif | |
1b9d8cb7 TT |
839 | } else { |
840 | retval = ext2fs_create_icount2(test_fs, flags, size, 0, | |
841 | &icount); | |
842 | if (retval) { | |
843 | com_err("run_test", retval, "while creating icount"); | |
844 | exit(1); | |
845 | } | |
1cb78d84 TT |
846 | } |
847 | for (pc = prog; pc->cmd != EXIT; pc++) { | |
848 | switch (pc->cmd) { | |
849 | case FETCH: | |
850 | printf("icount_fetch(%u) = ", pc->ino); | |
851 | break; | |
852 | case STORE: | |
853 | retval = ext2fs_icount_store(icount, pc->ino, pc->arg); | |
854 | if (retval) { | |
855 | com_err("run_test", retval, | |
856 | "while calling icount_store"); | |
857 | exit(1); | |
858 | } | |
859 | printf("icount_store(%u, %u) = ", pc->ino, pc->arg); | |
860 | break; | |
861 | case INCREMENT: | |
862 | retval = ext2fs_icount_increment(icount, pc->ino, 0); | |
863 | if (retval) { | |
864 | com_err("run_test", retval, | |
865 | "while calling icount_increment"); | |
866 | exit(1); | |
867 | } | |
868 | printf("icount_increment(%u) = ", pc->ino); | |
869 | break; | |
870 | case DECREMENT: | |
871 | retval = ext2fs_icount_decrement(icount, pc->ino, 0); | |
872 | if (retval) { | |
873 | com_err("run_test", retval, | |
874 | "while calling icount_decrement"); | |
875 | exit(1); | |
876 | } | |
877 | printf("icount_decrement(%u) = ", pc->ino); | |
878 | break; | |
879 | } | |
880 | retval = ext2fs_icount_fetch(icount, pc->ino, &result); | |
881 | if (retval) { | |
882 | com_err("run_test", retval, | |
883 | "while calling icount_fetch"); | |
884 | exit(1); | |
885 | } | |
886 | printf("%u (%s)\n", result, (result == pc->expected) ? | |
887 | "OK" : "NOT OK"); | |
888 | if (result != pc->expected) | |
889 | problem++; | |
890 | } | |
891 | printf("icount size is %u\n", ext2fs_get_icount_size(icount)); | |
892 | retval = ext2fs_icount_validate(icount, stdout); | |
893 | if (retval) { | |
894 | com_err("run_test", retval, "while calling icount_validate"); | |
895 | exit(1); | |
896 | } | |
897 | ext2fs_free_icount(icount); | |
898 | return problem; | |
899 | } | |
900 | ||
901 | ||
902 | int main(int argc, char **argv) | |
903 | { | |
904 | int failed = 0; | |
905 | ||
906 | setup(); | |
907 | printf("Standard icount run:\n"); | |
1b9d8cb7 | 908 | failed += run_test(0, 0, 0, prog); |
1cb78d84 | 909 | printf("\nMultiple bitmap test:\n"); |
1b9d8cb7 | 910 | failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, 0, prog); |
1cb78d84 | 911 | printf("\nResizing icount:\n"); |
1b9d8cb7 TT |
912 | failed += run_test(0, 3, 0, extended); |
913 | printf("\nStandard icount run with tdb:\n"); | |
914 | failed += run_test(0, 0, ".", prog); | |
915 | printf("\nMultiple bitmap test with tdb:\n"); | |
916 | failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, ".", prog); | |
917 | if (failed) | |
1cb78d84 TT |
918 | printf("FAILED!\n"); |
919 | return failed; | |
920 | } | |
921 | #endif |