WebSVN – HelenOS – Diff – /branches/network/uspace/srv/fs/fat/fat_idx.c


/*
 * Copyright (c) 2008 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/** @addtogroup fs
 * @{
 */
 
/**
 * @file    fat_idx.c
 * @brief   Layer for translating FAT entities to VFS node indices.
 */
 
#include "fat.h"
#include "../../vfs/vfs.h"
#include <errno.h>
#include <string.h>
#include <adt/hash_table.h>
#include <adt/list.h>
#include <assert.h>
#include <fibril_sync.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;
 
/** Mutex protecting the list of unused structures. */
static FIBRIL_MUTEX_INITIALIZE(unused_lock);
 
/** List of unused structures. */
static LIST_INITIALIZE(unused_head);
 
static void unused_initialize(unused_t *u, dev_handle_t dev_handle)
{
    link_initialize(&u->link);
    u->dev_handle = dev_handle;
    u->next = 0;
    u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;
    list_initialize(&u->freed_head);
}
 
static unused_t *unused_find(dev_handle_t dev_handle, bool lock)
{
    unused_t *u;
    link_t *l;
 
    if (lock)
        fibril_mutex_lock(&unused_lock);
    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)
            return u;
    }
    if (lock)
        fibril_mutex_unlock(&unused_lock);
    return NULL;
}
 
/** Mutex protecting the up_hash and ui_hash. */
static FIBRIL_MUTEX_INITIALIZE(used_lock);
 
/**
 * Global hash table of all used fat_idx_t structures.
 * The index structures are hashed by the dev_handle, parent node's first
 * cluster and index within the parent directory.
 */
static hash_table_t up_hash;
 
#define UPH_BUCKETS_LOG 12
#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)
 
#define UPH_DH_KEY  0
#define UPH_PFC_KEY 1
#define UPH_PDI_KEY 2
 
static hash_index_t pos_hash(unsigned long key[])
{
    dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
    fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
    unsigned pdi = (unsigned)key[UPH_PDI_KEY];
 
    hash_index_t h;
 
    /*
     * The least significant half of all bits are the least significant bits
     * of the parent node's first cluster.
     *
     * The least significant half of the most significant half of all bits
     * are the least significant bits of the node's dentry index within the
     * parent directory node.
     *
     * The most significant half of the most significant half of all bits
     * are the least significant bits of the device handle.
     */
    h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
    h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
        (UPH_BUCKETS_LOG / 2);
    h |= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
        (3 * (UPH_BUCKETS_LOG / 4));
 
    return h;
}
 
static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
{
    dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
    fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
    unsigned pdi = (unsigned)key[UPH_PDI_KEY];
    fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
 
    return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
        (pdi == fidx->pdi);
}
 
static void pos_remove_callback(link_t *item)
{
    /* nothing to do */
}
 
static hash_table_operations_t uph_ops = {
    .hash = pos_hash,
    .compare = pos_compare,
    .remove_callback = pos_remove_callback,
};
 
/**
 * Global hash table of all used fat_idx_t structures.
 * The index structures are hashed by the dev_handle and index.
 */
static hash_table_t ui_hash;
 
#define UIH_BUCKETS_LOG 12
#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)
 
#define UIH_DH_KEY  0
#define UIH_INDEX_KEY   1
 
static hash_index_t idx_hash(unsigned long key[])
{
    dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
    fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
 
    hash_index_t h;
 
    h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
    h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
        (UIH_BUCKETS_LOG / 2);
 
    return h;
}
 
static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
{
    dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
    fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
 
    return (dev_handle == fidx->dev_handle) && (index == fidx->index);
}
 
static void idx_remove_callback(link_t *item)
{
    /* nothing to do */
}
 
static hash_table_operations_t uih_ops = {
    .hash = idx_hash,
    .compare = idx_compare,
    .remove_callback = idx_remove_callback,
};
 
/** Allocate a VFS index which is not currently in use. */
static bool fat_index_alloc(dev_handle_t dev_handle, fs_index_t *index)
{
    unused_t *u;
   
    assert(index);
    u = unused_find(dev_handle, true);
    if (!u)
        return false;  
 
    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;
            fibril_mutex_unlock(&unused_lock);
            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);
        }
        fibril_mutex_unlock(&unused_lock);
        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).
     */
    fibril_mutex_unlock(&unused_lock);
    return false;
}
 
/** If possible, coalesce two intervals of freed indices. */
static void try_coalesce_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_index_free(dev_handle_t dev_handle, fs_index_t index)
{
    unused_t *u;
 
    u = unused_find(dev_handle, true);
    assert(u);
 
    if (u->next == index + 1) {
        /* The index can be returned directly to the counter. */
        u->next--;
        u->remaining++;
    } 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_coalesce_intervals(lnk->prev, lnk,
                        lnk);
                fibril_mutex_unlock(&unused_lock);
                return;
            }
            if (f->last == index - 1) {
                f->last++;
                if (lnk->next != &u->freed_head)
                    try_coalesce_intervals(lnk, lnk->next,
                        lnk);
                fibril_mutex_unlock(&unused_lock);
                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);
                fibril_mutex_unlock(&unused_lock);
                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);
    }
    fibril_mutex_unlock(&unused_lock);
}
 
static fat_idx_t *fat_idx_create(dev_handle_t dev_handle)
{
    fat_idx_t *fidx;
 
    fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
    if (!fidx)
        return NULL;
    if (!fat_index_alloc(dev_handle, &fidx->index)) {
        free(fidx);
        return NULL;
    }
       
    link_initialize(&fidx->uph_link);
    link_initialize(&fidx->uih_link);
    fibril_mutex_initialize(&fidx->lock);
    fidx->dev_handle = dev_handle;
    fidx->pfc = FAT_CLST_RES0;  /* no parent yet */
    fidx->pdi = 0;
    fidx->nodep = NULL;
 
    return fidx;
}
 
fat_idx_t *fat_idx_get_new(dev_handle_t dev_handle)
{
    fat_idx_t *fidx;
 
    fibril_mutex_lock(&used_lock);
    fidx = fat_idx_create(dev_handle);
    if (!fidx) {
        fibril_mutex_unlock(&used_lock);
        return NULL;
    }
       
    unsigned long ikey[] = {
        [UIH_DH_KEY] = dev_handle,
        [UIH_INDEX_KEY] = fidx->index,
    };
   
    hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
    fibril_mutex_lock(&fidx->lock);
    fibril_mutex_unlock(&used_lock);
 
    return fidx;
}
 
fat_idx_t *
fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
{
    fat_idx_t *fidx;
    link_t *l;
    unsigned long pkey[] = {
        [UPH_DH_KEY] = dev_handle,
        [UPH_PFC_KEY] = pfc,
        [UPH_PDI_KEY] = pdi,
    };
 
    fibril_mutex_lock(&used_lock);
    l = hash_table_find(&up_hash, pkey);
    if (l) {
        fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
    } else {
        fidx = fat_idx_create(dev_handle);
        if (!fidx) {
            fibril_mutex_unlock(&used_lock);
            return NULL;
        }
       
        unsigned long ikey[] = {
            [UIH_DH_KEY] = dev_handle,
            [UIH_INDEX_KEY] = fidx->index,
        };
   
        fidx->pfc = pfc;
        fidx->pdi = pdi;
 
        hash_table_insert(&up_hash, pkey, &fidx->uph_link);
        hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
    }
    fibril_mutex_lock(&fidx->lock);
    fibril_mutex_unlock(&used_lock);
 
    return fidx;
}
 
void fat_idx_hashin(fat_idx_t *idx)
{
    unsigned long pkey[] = {
        [UPH_DH_KEY] = idx->dev_handle,
        [UPH_PFC_KEY] = idx->pfc,
        [UPH_PDI_KEY] = idx->pdi,
    };
 
    fibril_mutex_lock(&used_lock);
    hash_table_insert(&up_hash, pkey, &idx->uph_link);
    fibril_mutex_unlock(&used_lock);
}
 
void fat_idx_hashout(fat_idx_t *idx)
{
    unsigned long pkey[] = {
        [UPH_DH_KEY] = idx->dev_handle,
        [UPH_PFC_KEY] = idx->pfc,
        [UPH_PDI_KEY] = idx->pdi,
    };
 
    fibril_mutex_lock(&used_lock);
    hash_table_remove(&up_hash, pkey, 3);
    fibril_mutex_unlock(&used_lock);
}
 
fat_idx_t *
fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
{
    fat_idx_t *fidx = NULL;
    link_t *l;
    unsigned long ikey[] = {
        [UIH_DH_KEY] = dev_handle,
        [UIH_INDEX_KEY] = index,
    };
 
    fibril_mutex_lock(&used_lock);
    l = hash_table_find(&ui_hash, ikey);
    if (l) {
        fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
        fibril_mutex_lock(&fidx->lock);
    }
    fibril_mutex_unlock(&used_lock);
 
    return fidx;
}
 
/** Destroy the index structure.
 *
 * @param idx       The index structure to be destroyed.
 */
void fat_idx_destroy(fat_idx_t *idx)
{
    unsigned long ikey[] = {
        [UIH_DH_KEY] = idx->dev_handle,
        [UIH_INDEX_KEY] = idx->index,
    };
 
    assert(idx->pfc == FAT_CLST_RES0);
 
    fibril_mutex_lock(&used_lock);
    /*
     * Since we can only free unlinked nodes, the index structure is not
     * present in the position hash (uph). We therefore hash it out from
     * the index hash only.
     */
    hash_table_remove(&ui_hash, ikey, 2);
    fibril_mutex_unlock(&used_lock);
    /* Release the VFS index. */
    fat_index_free(idx->dev_handle, idx->index);
    /* Deallocate the structure. */
    free(idx);
}
 
int fat_idx_init(void)
{
    if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
        return ENOMEM;
    if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
        hash_table_destroy(&up_hash);
        return ENOMEM;
    }
    return EOK;
}
 
void fat_idx_fini(void)
{
    /* We assume the hash tables are empty. */
    hash_table_destroy(&up_hash);
    hash_table_destroy(&ui_hash);
}
 
int fat_idx_init_by_dev_handle(dev_handle_t dev_handle)
{
    unused_t *u;
    int rc = EOK;
 
    u = (unused_t *) malloc(sizeof(unused_t));
    if (!u)
        return ENOMEM;
    unused_initialize(u, dev_handle);
    fibril_mutex_lock(&unused_lock);
    if (!unused_find(dev_handle, false))
        list_append(&u->link, &unused_head);
    else
        rc = EEXIST;
    fibril_mutex_unlock(&unused_lock);
    return rc;
}
 
void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)
{
    unused_t *u;
 
    u = unused_find(dev_handle, true);
    assert(u);
    list_remove(&u->link);
    fibril_mutex_unlock(&unused_lock);
 
    while (!list_empty(&u->freed_head)) {
        freed_t *f;
        f = list_get_instance(u->freed_head.next, freed_t, link);
        list_remove(&f->link);
        free(f);
    }
    free(u);
}
 
/**
 * @}
 */
 

Rev 4153	Rev 4581
1	/*	1	/*
2	* Copyright (c) 2008 Jakub Jermar	2	* Copyright (c) 2008 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/** @addtogroup fs	29	/** @addtogroup fs
30	* @{	30	* @{
31	*/	31	*/
32		32
33	/**	33	/**
34	* @file fat_idx.c	34	* @file fat_idx.c
35	* @brief Layer for translating FAT entities to VFS node indices.	35	* @brief Layer for translating FAT entities to VFS node indices.
36	*/	36	*/
37		37
38	#include "fat.h"	38	#include "fat.h"
39	#include "../../vfs/vfs.h"	39	#include "../../vfs/vfs.h"
40	#include <errno.h>	40	#include <errno.h>
41	#include <string.h>	41	#include <string.h>
42	#include <libadt/hash_table.h>	42	#include <adt/hash_table.h>
43	#include <libadt/list.h>	43	#include <adt/list.h>
44	#include <assert.h>	44	#include <assert.h>
45	#include <futex.h>	45	#include <fibril_sync.h>
46		46
47	/** Each instance of this type describes one interval of freed VFS indices. */	47	/** Each instance of this type describes one interval of freed VFS indices. */
48	typedef struct {	48	typedef struct {
49	link_t link;	49	link_t link;
50	fs_index_t first;	50	fs_index_t first;
51	fs_index_t last;	51	fs_index_t last;
52	} freed_t;	52	} freed_t;
53		53
54	/**	54	/**
55	* Each instance of this type describes state of all VFS indices that	55	* Each instance of this type describes state of all VFS indices that
56	* are currently unused.	56	* are currently unused.
57	*/	57	*/
58	typedef struct {	58	typedef struct {
59	link_t link;	59	link_t link;
60	dev_handle_t dev_handle;	60	dev_handle_t dev_handle;
61		61
62	/** Next unassigned index. */	62	/** Next unassigned index. */
63	fs_index_t next;	63	fs_index_t next;
64	/** Number of remaining unassigned indices. */	64	/** Number of remaining unassigned indices. */
65	uint64_t remaining;	65	uint64_t remaining;
66		66
67	/** Sorted list of intervals of freed indices. */	67	/** Sorted list of intervals of freed indices. */
68	link_t freed_head;	68	link_t freed_head;
69	} unused_t;	69	} unused_t;
70		70
71	/** Futex protecting the list of unused structures. */	71	/** Mutex protecting the list of unused structures. */
72	static futex_t unused_futex = FUTEX_INITIALIZER;	72	static FIBRIL_MUTEX_INITIALIZE(unused_lock);
73		73
74	/** List of unused structures. */	74	/** List of unused structures. */
75	static LIST_INITIALIZE(unused_head);	75	static LIST_INITIALIZE(unused_head);
76		76
77	static void unused_initialize(unused_t *u, dev_handle_t dev_handle)	77	static void unused_initialize(unused_t *u, dev_handle_t dev_handle)
78	{	78	{
79	link_initialize(&u->link);	79	link_initialize(&u->link);
80	u->dev_handle = dev_handle;	80	u->dev_handle = dev_handle;
81	u->next = 0;	81	u->next = 0;
82	u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;	82	u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;
83	list_initialize(&u->freed_head);	83	list_initialize(&u->freed_head);
84	}	84	}
85		85
86	static unused_t *unused_find(dev_handle_t dev_handle, bool lock)	86	static unused_t *unused_find(dev_handle_t dev_handle, bool lock)
87	{	87	{
88	unused_t *u;	88	unused_t *u;
89	link_t *l;	89	link_t *l;
90		90
91	if (lock)	91	if (lock)
92	futex_down(&unused_futex);	92	fibril_mutex_lock(&unused_lock);
93	for (l = unused_head.next; l != &unused_head; l = l->next) {	93	for (l = unused_head.next; l != &unused_head; l = l->next) {
94	u = list_get_instance(l, unused_t, link);	94	u = list_get_instance(l, unused_t, link);
95	if (u->dev_handle == dev_handle)	95	if (u->dev_handle == dev_handle)
96	return u;	96	return u;
97	}	97	}
98	if (lock)	98	if (lock)
99	futex_up(&unused_futex);	99	fibril_mutex_unlock(&unused_lock);
100	return NULL;	100	return NULL;
101	}	101	}
102		102
103	/** Futex protecting the up_hash and ui_hash. */	103	/** Mutex protecting the up_hash and ui_hash. */
104	static futex_t used_futex = FUTEX_INITIALIZER;	104	static FIBRIL_MUTEX_INITIALIZE(used_lock);
105		105
106	/**	106	/**
107	* Global hash table of all used fat_idx_t structures.	107	* Global hash table of all used fat_idx_t structures.
108	* The index structures are hashed by the dev_handle, parent node's first	108	* The index structures are hashed by the dev_handle, parent node's first
109	* cluster and index within the parent directory.	109	* cluster and index within the parent directory.
110	*/	110	*/
111	static hash_table_t up_hash;	111	static hash_table_t up_hash;
112		112
113	#define UPH_BUCKETS_LOG 12	113	#define UPH_BUCKETS_LOG 12
114	#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)	114	#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)
115		115
116	#define UPH_DH_KEY 0	116	#define UPH_DH_KEY 0
117	#define UPH_PFC_KEY 1	117	#define UPH_PFC_KEY 1
118	#define UPH_PDI_KEY 2	118	#define UPH_PDI_KEY 2
119		119
120	static hash_index_t pos_hash(unsigned long key[])	120	static hash_index_t pos_hash(unsigned long key[])
121	{	121	{
122	dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];	122	dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
123	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];	123	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
124	unsigned pdi = (unsigned)key[UPH_PDI_KEY];	124	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
125		125
126	hash_index_t h;	126	hash_index_t h;
127		127
128	/*	128	/*
129	* The least significant half of all bits are the least significant bits	129	* The least significant half of all bits are the least significant bits
130	* of the parent node's first cluster.	130	* of the parent node's first cluster.
131	*	131	*
132	* The least significant half of the most significant half of all bits	132	* The least significant half of the most significant half of all bits
133	* are the least significant bits of the node's dentry index within the	133	* are the least significant bits of the node's dentry index within the
134	* parent directory node.	134	* parent directory node.
135	*	135	*
136	* The most significant half of the most significant half of all bits	136	* The most significant half of the most significant half of all bits
137	* are the least significant bits of the device handle.	137	* are the least significant bits of the device handle.
138	*/	138	*/
139	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);	139	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
140	h \|= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<	140	h \|= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
141	(UPH_BUCKETS_LOG / 2);	141	(UPH_BUCKETS_LOG / 2);
142	h \|= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<	142	h \|= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
143	(3 * (UPH_BUCKETS_LOG / 4));	143	(3 * (UPH_BUCKETS_LOG / 4));
144		144
145	return h;	145	return h;
146	}	146	}
147		147
148	static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)	148	static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
149	{	149	{
150	dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];	150	dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
151	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];	151	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
152	unsigned pdi = (unsigned)key[UPH_PDI_KEY];	152	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
153	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);	153	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
154		154
155	return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&	155	return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
156	(pdi == fidx->pdi);	156	(pdi == fidx->pdi);
157	}	157	}
158		158
159	static void pos_remove_callback(link_t *item)	159	static void pos_remove_callback(link_t *item)
160	{	160	{
161	/* nothing to do */	161	/* nothing to do */
162	}	162	}
163		163
164	static hash_table_operations_t uph_ops = {	164	static hash_table_operations_t uph_ops = {
165	.hash = pos_hash,	165	.hash = pos_hash,
166	.compare = pos_compare,	166	.compare = pos_compare,
167	.remove_callback = pos_remove_callback,	167	.remove_callback = pos_remove_callback,
168	};	168	};
169		169
170	/**	170	/**
171	* Global hash table of all used fat_idx_t structures.	171	* Global hash table of all used fat_idx_t structures.
172	* The index structures are hashed by the dev_handle and index.	172	* The index structures are hashed by the dev_handle and index.
173	*/	173	*/
174	static hash_table_t ui_hash;	174	static hash_table_t ui_hash;
175		175
176	#define UIH_BUCKETS_LOG 12	176	#define UIH_BUCKETS_LOG 12
177	#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)	177	#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)
178		178
179	#define UIH_DH_KEY 0	179	#define UIH_DH_KEY 0
180	#define UIH_INDEX_KEY 1	180	#define UIH_INDEX_KEY 1
181		181
182	static hash_index_t idx_hash(unsigned long key[])	182	static hash_index_t idx_hash(unsigned long key[])
183	{	183	{
184	dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];	184	dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
185	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];	185	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
186		186
187	hash_index_t h;	187	hash_index_t h;
188		188
189	h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);	189	h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
190	h \|= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<	190	h \|= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
191	(UIH_BUCKETS_LOG / 2);	191	(UIH_BUCKETS_LOG / 2);
192		192
193	return h;	193	return h;
194	}	194	}
195		195
196	static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)	196	static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
197	{	197	{
198	dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];	198	dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
199	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];	199	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
200	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);	200	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
201		201
202	return (dev_handle == fidx->dev_handle) && (index == fidx->index);	202	return (dev_handle == fidx->dev_handle) && (index == fidx->index);
203	}	203	}
204		204
205	static void idx_remove_callback(link_t *item)	205	static void idx_remove_callback(link_t *item)
206	{	206	{
207	/* nothing to do */	207	/* nothing to do */
208	}	208	}
209		209
210	static hash_table_operations_t uih_ops = {	210	static hash_table_operations_t uih_ops = {
211	.hash = idx_hash,	211	.hash = idx_hash,
212	.compare = idx_compare,	212	.compare = idx_compare,
213	.remove_callback = idx_remove_callback,	213	.remove_callback = idx_remove_callback,
214	};	214	};
215		215
216	/** Allocate a VFS index which is not currently in use. */	216	/** Allocate a VFS index which is not currently in use. */
217	static bool fat_index_alloc(dev_handle_t dev_handle, fs_index_t *index)	217	static bool fat_index_alloc(dev_handle_t dev_handle, fs_index_t *index)
218	{	218	{
219	unused_t *u;	219	unused_t *u;
220		220
221	assert(index);	221	assert(index);
222	u = unused_find(dev_handle, true);	222	u = unused_find(dev_handle, true);
223	if (!u)	223	if (!u)
224	return false;	224	return false;
225		225
226	if (list_empty(&u->freed_head)) {	226	if (list_empty(&u->freed_head)) {
227	if (u->remaining) {	227	if (u->remaining) {
228	/*	228	/*
229	* There are no freed indices, allocate one directly	229	* There are no freed indices, allocate one directly
230	* from the counter.	230	* from the counter.
231	*/	231	*/
232	*index = u->next++;	232	*index = u->next++;
233	--u->remaining;	233	--u->remaining;
234	futex_up(&unused_futex);	234	fibril_mutex_unlock(&unused_lock);
235	return true;	235	return true;
236	}	236	}
237	} else {	237	} else {
238	/* There are some freed indices which we can reuse. */	238	/* There are some freed indices which we can reuse. */
239	freed_t *f = list_get_instance(u->freed_head.next, freed_t,	239	freed_t *f = list_get_instance(u->freed_head.next, freed_t,
240	link);	240	link);
241	*index = f->first;	241	*index = f->first;
242	if (f->first++ == f->last) {	242	if (f->first++ == f->last) {
243	/* Destroy the interval. */	243	/* Destroy the interval. */
244	list_remove(&f->link);	244	list_remove(&f->link);
245	free(f);	245	free(f);
246	}	246	}
247	futex_up(&unused_futex);	247	fibril_mutex_unlock(&unused_lock);
248	return true;	248	return true;
249	}	249	}
250	/*	250	/*
251	* We ran out of indices, which is extremely unlikely with FAT16, but	251	* We ran out of indices, which is extremely unlikely with FAT16, but
252	* theoretically still possible (e.g. too many open unlinked nodes or	252	* theoretically still possible (e.g. too many open unlinked nodes or
253	* too many zero-sized nodes).	253	* too many zero-sized nodes).
254	*/	254	*/
255	futex_up(&unused_futex);	255	fibril_mutex_unlock(&unused_lock);
256	return false;	256	return false;
257	}	257	}
258		258
259	/** If possible, coalesce two intervals of freed indices. */	259	/** If possible, coalesce two intervals of freed indices. */
260	static void try_coalesce_intervals(link_t l, link_t r, link_t *cur)	260	static void try_coalesce_intervals(link_t l, link_t r, link_t *cur)
261	{	261	{
262	freed_t *fl = list_get_instance(l, freed_t, link);	262	freed_t *fl = list_get_instance(l, freed_t, link);
263	freed_t *fr = list_get_instance(r, freed_t, link);	263	freed_t *fr = list_get_instance(r, freed_t, link);
264		264
265	if (fl->last + 1 == fr->first) {	265	if (fl->last + 1 == fr->first) {
266	if (cur == l) {	266	if (cur == l) {
267	fl->last = fr->last;	267	fl->last = fr->last;
268	list_remove(r);	268	list_remove(r);
269	free(r);	269	free(r);
270	} else {	270	} else {
271	fr->first = fl->first;	271	fr->first = fl->first;
272	list_remove(l);	272	list_remove(l);
273	free(l);	273	free(l);
274	}	274	}
275	}	275	}
276	}	276	}
277		277
278	/** Free a VFS index, which is no longer in use. */	278	/** Free a VFS index, which is no longer in use. */
279	static void fat_index_free(dev_handle_t dev_handle, fs_index_t index)	279	static void fat_index_free(dev_handle_t dev_handle, fs_index_t index)
280	{	280	{
281	unused_t *u;	281	unused_t *u;
282		282
283	u = unused_find(dev_handle, true);	283	u = unused_find(dev_handle, true);
284	assert(u);	284	assert(u);
285		285
286	if (u->next == index + 1) {	286	if (u->next == index + 1) {
287	/* The index can be returned directly to the counter. */	287	/* The index can be returned directly to the counter. */
288	u->next--;	288	u->next--;
289	u->remaining++;	289	u->remaining++;
290	} else {	290	} else {
291	/*	291	/*
292	* The index must be returned either to an existing freed	292	* The index must be returned either to an existing freed
293	* interval or a new interval must be created.	293	* interval or a new interval must be created.
294	*/	294	*/
295	link_t *lnk;	295	link_t *lnk;
296	freed_t *n;	296	freed_t *n;
297	for (lnk = u->freed_head.next; lnk != &u->freed_head;	297	for (lnk = u->freed_head.next; lnk != &u->freed_head;
298	lnk = lnk->next) {	298	lnk = lnk->next) {
299	freed_t *f = list_get_instance(lnk, freed_t, link);	299	freed_t *f = list_get_instance(lnk, freed_t, link);
300	if (f->first == index + 1) {	300	if (f->first == index + 1) {
301	f->first--;	301	f->first--;
302	if (lnk->prev != &u->freed_head)	302	if (lnk->prev != &u->freed_head)
303	try_coalesce_intervals(lnk->prev, lnk,	303	try_coalesce_intervals(lnk->prev, lnk,
304	lnk);	304	lnk);
305	futex_up(&unused_futex);	305	fibril_mutex_unlock(&unused_lock);
306	return;	306	return;
307	}	307	}
308	if (f->last == index - 1) {	308	if (f->last == index - 1) {
309	f->last++;	309	f->last++;
310	if (lnk->next != &u->freed_head)	310	if (lnk->next != &u->freed_head)
311	try_coalesce_intervals(lnk, lnk->next,	311	try_coalesce_intervals(lnk, lnk->next,
312	lnk);	312	lnk);
313	futex_up(&unused_futex);	313	fibril_mutex_unlock(&unused_lock);
314	return;	314	return;
315	}	315	}
316	if (index > f->first) {	316	if (index > f->first) {
317	n = malloc(sizeof(freed_t));	317	n = malloc(sizeof(freed_t));
318	/* TODO: sleep until allocation succeeds */	318	/* TODO: sleep until allocation succeeds */
319	assert(n);	319	assert(n);
320	link_initialize(&n->link);	320	link_initialize(&n->link);
321	n->first = index;	321	n->first = index;
322	n->last = index;	322	n->last = index;
323	list_insert_before(&n->link, lnk);	323	list_insert_before(&n->link, lnk);
324	futex_up(&unused_futex);	324	fibril_mutex_unlock(&unused_lock);
325	return;	325	return;
326	}	326	}
327		327
328	}	328	}
329	/* The index will form the last interval. */	329	/* The index will form the last interval. */
330	n = malloc(sizeof(freed_t));	330	n = malloc(sizeof(freed_t));
331	/* TODO: sleep until allocation succeeds */	331	/* TODO: sleep until allocation succeeds */
332	assert(n);	332	assert(n);
333	link_initialize(&n->link);	333	link_initialize(&n->link);
334	n->first = index;	334	n->first = index;
335	n->last = index;	335	n->last = index;
336	list_append(&n->link, &u->freed_head);	336	list_append(&n->link, &u->freed_head);
337	}	337	}
338	futex_up(&unused_futex);	338	fibril_mutex_unlock(&unused_lock);
339	}	339	}
340		340
341	static fat_idx_t *fat_idx_create(dev_handle_t dev_handle)	341	static fat_idx_t *fat_idx_create(dev_handle_t dev_handle)
342	{	342	{
343	fat_idx_t *fidx;	343	fat_idx_t *fidx;
344		344
345	fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));	345	fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
346	if (!fidx)	346	if (!fidx)
347	return NULL;	347	return NULL;
348	if (!fat_index_alloc(dev_handle, &fidx->index)) {	348	if (!fat_index_alloc(dev_handle, &fidx->index)) {
349	free(fidx);	349	free(fidx);
350	return NULL;	350	return NULL;
351	}	351	}
352		352
353	link_initialize(&fidx->uph_link);	353	link_initialize(&fidx->uph_link);
354	link_initialize(&fidx->uih_link);	354	link_initialize(&fidx->uih_link);
355	futex_initialize(&fidx->lock, 1);	355	fibril_mutex_initialize(&fidx->lock);
356	fidx->dev_handle = dev_handle;	356	fidx->dev_handle = dev_handle;
357	fidx->pfc = FAT_CLST_RES0; /* no parent yet */	357	fidx->pfc = FAT_CLST_RES0; /* no parent yet */
358	fidx->pdi = 0;	358	fidx->pdi = 0;
359	fidx->nodep = NULL;	359	fidx->nodep = NULL;
360		360
361	return fidx;	361	return fidx;
362	}	362	}
363		363
364	fat_idx_t *fat_idx_get_new(dev_handle_t dev_handle)	364	fat_idx_t *fat_idx_get_new(dev_handle_t dev_handle)
365	{	365	{
366	fat_idx_t *fidx;	366	fat_idx_t *fidx;
367		367
368	futex_down(&used_futex);	368	fibril_mutex_lock(&used_lock);
369	fidx = fat_idx_create(dev_handle);	369	fidx = fat_idx_create(dev_handle);
370	if (!fidx) {	370	if (!fidx) {
371	futex_up(&used_futex);	371	fibril_mutex_unlock(&used_lock);
372	return NULL;	372	return NULL;
373	}	373	}
374		374
375	unsigned long ikey[] = {	375	unsigned long ikey[] = {
376	[UIH_DH_KEY] = dev_handle,	376	[UIH_DH_KEY] = dev_handle,
377	[UIH_INDEX_KEY] = fidx->index,	377	[UIH_INDEX_KEY] = fidx->index,
378	};	378	};
379		379
380	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);	380	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
381	futex_down(&fidx->lock);	381	fibril_mutex_lock(&fidx->lock);
382	futex_up(&used_futex);	382	fibril_mutex_unlock(&used_lock);
383		383
384	return fidx;	384	return fidx;
385	}	385	}
386		386
387	fat_idx_t *	387	fat_idx_t *
388	fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)	388	fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
389	{	389	{
390	fat_idx_t *fidx;	390	fat_idx_t *fidx;
391	link_t *l;	391	link_t *l;
392	unsigned long pkey[] = {	392	unsigned long pkey[] = {
393	[UPH_DH_KEY] = dev_handle,	393	[UPH_DH_KEY] = dev_handle,
394	[UPH_PFC_KEY] = pfc,	394	[UPH_PFC_KEY] = pfc,
395	[UPH_PDI_KEY] = pdi,	395	[UPH_PDI_KEY] = pdi,
396	};	396	};
397		397
398	futex_down(&used_futex);	398	fibril_mutex_lock(&used_lock);
399	l = hash_table_find(&up_hash, pkey);	399	l = hash_table_find(&up_hash, pkey);
400	if (l) {	400	if (l) {
401	fidx = hash_table_get_instance(l, fat_idx_t, uph_link);	401	fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
402	} else {	402	} else {
403	fidx = fat_idx_create(dev_handle);	403	fidx = fat_idx_create(dev_handle);
404	if (!fidx) {	404	if (!fidx) {
405	futex_up(&used_futex);	405	fibril_mutex_unlock(&used_lock);
406	return NULL;	406	return NULL;
407	}	407	}
408		408
409	unsigned long ikey[] = {	409	unsigned long ikey[] = {
410	[UIH_DH_KEY] = dev_handle,	410	[UIH_DH_KEY] = dev_handle,
411	[UIH_INDEX_KEY] = fidx->index,	411	[UIH_INDEX_KEY] = fidx->index,
412	};	412	};
413		413
414	fidx->pfc = pfc;	414	fidx->pfc = pfc;
415	fidx->pdi = pdi;	415	fidx->pdi = pdi;
416		416
417	hash_table_insert(&up_hash, pkey, &fidx->uph_link);	417	hash_table_insert(&up_hash, pkey, &fidx->uph_link);
418	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);	418	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
419	}	419	}
420	futex_down(&fidx->lock);	420	fibril_mutex_lock(&fidx->lock);
421	futex_up(&used_futex);	421	fibril_mutex_unlock(&used_lock);
422		422
423	return fidx;	423	return fidx;
424	}	424	}
425		425
426	void fat_idx_hashin(fat_idx_t *idx)	426	void fat_idx_hashin(fat_idx_t *idx)
427	{	427	{
428	unsigned long pkey[] = {	428	unsigned long pkey[] = {
429	[UPH_DH_KEY] = idx->dev_handle,	429	[UPH_DH_KEY] = idx->dev_handle,
430	[UPH_PFC_KEY] = idx->pfc,	430	[UPH_PFC_KEY] = idx->pfc,
431	[UPH_PDI_KEY] = idx->pdi,	431	[UPH_PDI_KEY] = idx->pdi,
432	};	432	};
433		433
434	futex_down(&used_futex);	434	fibril_mutex_lock(&used_lock);
435	hash_table_insert(&up_hash, pkey, &idx->uph_link);	435	hash_table_insert(&up_hash, pkey, &idx->uph_link);
436	futex_up(&used_futex);	436	fibril_mutex_unlock(&used_lock);
437	}	437	}
438		438
439	void fat_idx_hashout(fat_idx_t *idx)	439	void fat_idx_hashout(fat_idx_t *idx)
440	{	440	{
441	unsigned long pkey[] = {	441	unsigned long pkey[] = {
442	[UPH_DH_KEY] = idx->dev_handle,	442	[UPH_DH_KEY] = idx->dev_handle,
443	[UPH_PFC_KEY] = idx->pfc,	443	[UPH_PFC_KEY] = idx->pfc,
444	[UPH_PDI_KEY] = idx->pdi,	444	[UPH_PDI_KEY] = idx->pdi,
445	};	445	};
446		446
447	futex_down(&used_futex);	447	fibril_mutex_lock(&used_lock);
448	hash_table_remove(&up_hash, pkey, 3);	448	hash_table_remove(&up_hash, pkey, 3);
449	futex_up(&used_futex);	449	fibril_mutex_unlock(&used_lock);
450	}	450	}
451		451
452	fat_idx_t *	452	fat_idx_t *
453	fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)	453	fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
454	{	454	{
455	fat_idx_t *fidx = NULL;	455	fat_idx_t *fidx = NULL;
456	link_t *l;	456	link_t *l;
457	unsigned long ikey[] = {	457	unsigned long ikey[] = {
458	[UIH_DH_KEY] = dev_handle,	458	[UIH_DH_KEY] = dev_handle,
459	[UIH_INDEX_KEY] = index,	459	[UIH_INDEX_KEY] = index,
460	};	460	};
461		461
462	futex_down(&used_futex);	462	fibril_mutex_lock(&used_lock);
463	l = hash_table_find(&ui_hash, ikey);	463	l = hash_table_find(&ui_hash, ikey);
464	if (l) {	464	if (l) {
465	fidx = hash_table_get_instance(l, fat_idx_t, uih_link);	465	fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
466	futex_down(&fidx->lock);	466	fibril_mutex_lock(&fidx->lock);
467	}	467	}
468	futex_up(&used_futex);	468	fibril_mutex_unlock(&used_lock);
469		469
470	return fidx;	470	return fidx;
471	}	471	}
472		472
473	/** Destroy the index structure.	473	/** Destroy the index structure.
474	*	474	*
475	* @param idx The index structure to be destroyed.	475	* @param idx The index structure to be destroyed.
476	*/	476	*/
477	void fat_idx_destroy(fat_idx_t *idx)	477	void fat_idx_destroy(fat_idx_t *idx)
478	{	478	{
479	unsigned long ikey[] = {	479	unsigned long ikey[] = {
480	[UIH_DH_KEY] = idx->dev_handle,	480	[UIH_DH_KEY] = idx->dev_handle,
481	[UIH_INDEX_KEY] = idx->index,	481	[UIH_INDEX_KEY] = idx->index,
482	};	482	};
483		483
484	assert(idx->pfc == FAT_CLST_RES0);	484	assert(idx->pfc == FAT_CLST_RES0);
485		485
486	futex_down(&used_futex);	486	fibril_mutex_lock(&used_lock);
487	/*	487	/*
488	* Since we can only free unlinked nodes, the index structure is not	488	* Since we can only free unlinked nodes, the index structure is not
489	* present in the position hash (uph). We therefore hash it out from	489	* present in the position hash (uph). We therefore hash it out from
490	* the index hash only.	490	* the index hash only.
491	*/	491	*/
492	hash_table_remove(&ui_hash, ikey, 2);	492	hash_table_remove(&ui_hash, ikey, 2);
493	futex_up(&used_futex);	493	fibril_mutex_unlock(&used_lock);
494	/* Release the VFS index. */	494	/* Release the VFS index. */
495	fat_index_free(idx->dev_handle, idx->index);	495	fat_index_free(idx->dev_handle, idx->index);
496	/* Deallocate the structure. */	496	/* Deallocate the structure. */
497	free(idx);	497	free(idx);
498	}	498	}
499		499
500	int fat_idx_init(void)	500	int fat_idx_init(void)

Subversion Repositories HelenOS

(root)/branches/network/uspace/srv/fs/fat/fat_idx.c @ 4718 – Rev 4153 → 4581