Subversion Repositories HelenOS

#include "../../vfs/vfs.h"

/** Each instance of this type describes one interval of freed VFS indices. */

typedef struct {

    link_t      link;

    fs_index_t  first;

    fs_index_t  last;

} freed_t;

/**

 * Each instance of this type describes state of all VFS indices that

 * are currently unused.

 */

typedef struct {

    link_t      link;

    dev_handle_t    dev_handle;

    /** Next unassigned index. */

    fs_index_t  next;

    /** Number of remaining unassigned indices. */

    uint64_t    remaining;

    /** Sorted list of intervals of freed indices. */

    link_t      freed_head;

} unused_t;

static LIST_INITIALIZE(unused_head);

/** Allocate a VFS index which is not currently in use. */

static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)

{

    link_t *l;

    unused_t *u;

    assert(index);

    for (l = unused_head.next; l != &unused_head; l = l->next) {

        u = list_get_instance(l, unused_t, link);

        if (u->dev_handle == dev_handle)

            goto hit;

    }

    /* dev_handle not found */

    return false;  

hit:

    if (list_empty(&u->freed_head)) {

        if (u->remaining) {

            /*

             * There are no freed indices, allocate one directly

             * from the counter.

             */

            *index = u->next++;

            --u->remaining;

            return true;

        }

    } else {

        /* There are some freed indices which we can reuse. */

        freed_t *f = list_get_instance(u->freed_head.next, freed_t,

            link);

        *index = f->first;

        if (f->first++ == f->last) {

            /* Destroy the interval. */

            list_remove(&f->link);

            free(f);

        }

        return true;

    }

    /*

     * We ran out of indices, which is extremely unlikely with FAT16, but

     * theoretically still possible (e.g. too many open unlinked nodes or

     * too many zero-sized nodes).

     */

    return false;

}

/** If possible, merge two intervals of freed indices. */

static void try_merge_intervals(link_t *l, link_t *r, link_t *cur)

{

    freed_t *fl = list_get_instance(l, freed_t, link);

    freed_t *fr = list_get_instance(r, freed_t, link);

    if (fl->last + 1 == fr->first) {

        if (cur == l) {

            fl->last = fr->last;

            list_remove(r);

            free(r);

        } else {

            fr->first = fl->first;

            list_remove(l);

            free(l);

        }

    }

}

/** Free a VFS index, which is no longer in use. */

static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)

{

    link_t *l;

    unused_t *u;

    for (l = unused_head.next; l != &unused_head; l = l->next) {

        u = list_get_instance(l, unused_t, link);

        if (u->dev_handle == dev_handle)

            goto hit;

    }

    /* should not happen */

    assert(0);

hit:

    if (u->next == index + 1) {

        /* The index can be returned directly to the counter. */

        u->next--;

        u->remaining++;

        return;

    } else {

        /*

         * The index must be returned either to an existing freed

         * interval or a new interval must be created.

         */

        link_t *lnk;

        freed_t *n;

        for (lnk = u->freed_head.next; lnk != &u->freed_head;

            lnk = lnk->next) {

            freed_t *f = list_get_instance(lnk, freed_t, link);

            if (f->first == index + 1) {

                f->first--;

                if (lnk->prev != &u->freed_head)

                    try_merge_intervals(lnk->prev, lnk,

                        lnk);

                return;

            }

            if (f->last == index - 1) {

                f->last++;

                if (lnk->next != &u->freed_head)

                    try_merge_intervals(lnk, lnk->next,

                        lnk);

                return;

            }

            if (index > f->first) {

                n = malloc(sizeof(freed_t));

                /* TODO: sleep until allocation succeeds */

                assert(n);

                link_initialize(&n->link);

                n->first = index;

                n->last = index;

                list_insert_before(&n->link, lnk);

                return;

            }

        }

        /* The index will form the last interval. */

        n = malloc(sizeof(freed_t));

        /* TODO: sleep until allocation succeeds */

        assert(n);

        link_initialize(&n->link);

        n->first = index;

        n->last = index;

        list_append(&n->link, &u->freed_head);

    }

}