source: branches/stable/mindi-busybox/e2fsprogs/ext2fs/icount.c @ 821

Last change on this file since 821 was 821, checked in by Bruno Cornec, 14 years ago

Addition of busybox 1.2.1 as a mindi-busybox new package
This should avoid delivering binary files in mindi not built there (Fedora and Debian are quite serious about that)

File size: 11.2 KB
Line 
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
40struct ext2_icount_el {
41    ext2_ino_t  ino;
42    __u16   count;
43};
44
45struct 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
56void 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
68errcode_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
143errout:
144    ext2fs_free_icount(icount);
145    return(retval);
146}
147
148errcode_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 */
159static 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 */
206static 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
271errcode_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
294errcode_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
321errcode_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
386errcode_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
429errcode_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
474ext2_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}
Note: See TracBrowser for help on using the repository browser.