WebSVN – HelenOS – Diff – /trunk/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 <libadt/hash_table.h>
#include <libadt/list.h>
#include <assert.h>
#include <futex.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;
 
/** Futex protecting the list of unused structures. */
static futex_t unused_futex = FUTEX_INITIALIZER;
 
/** 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)
        futex_down(&unused_futex);
    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)
        futex_up(&unused_futex);
    return NULL;
}
 
/** Futex protecting the up_hash and ui_hash. */
static futex_t used_futex = FUTEX_INITIALIZER;
 
/**
 * 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_idx_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;
            futex_up(&unused_futex);
            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);
        }
        futex_up(&unused_futex);
        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).
     */
    futex_up(&unused_futex);
    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_idx_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);
                futex_up(&unused_futex);
                return;
            }
            if (f->last == index - 1) {
                f->last++;
                if (lnk->next != &u->freed_head)
                    try_coalesce_intervals(lnk, lnk->next,
                        lnk);
                futex_up(&unused_futex);
                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);
                futex_up(&unused_futex);
                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);
    }
    futex_up(&unused_futex);
}
 
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,
    };
 
    futex_down(&used_futex);
    l = hash_table_find(&up_hash, pkey);
    if (l) {
        fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
    } else {
        fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
        if (!fidx) {
            futex_up(&used_futex);
            return NULL;
        }
        if (!fat_idx_alloc(dev_handle, &fidx->index)) {
            free(fidx);
            futex_up(&used_futex);
            return NULL;
        }
       
        unsigned long ikey[] = {
            [UIH_DH_KEY] = dev_handle,
            [UIH_INDEX_KEY] = fidx->index,
        };
   
        link_initialize(&fidx->uph_link);
        link_initialize(&fidx->uih_link);
        futex_initialize(&fidx->lock, 1);
        fidx->dev_handle = dev_handle;
        fidx->pfc = pfc;
        fidx->pdi = pdi;
        fidx->nodep = NULL;
 
        hash_table_insert(&up_hash, pkey, &fidx->uph_link);
        hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
    }
    futex_down(&fidx->lock);
    futex_up(&used_futex);
 
    return fidx;
}
 
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,
    };
 
    futex_down(&used_futex);
    l = hash_table_find(&ui_hash, ikey);
    if (l) {
        fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
        futex_down(&fidx->lock);
    }
    futex_up(&used_futex);
 
    return fidx;
}
 
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);
    futex_down(&unused_futex);
    if (!unused_find(dev_handle, false))
        list_append(&u->link, &unused_head);
    else
        rc = EEXIST;
    futex_up(&unused_futex);
    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);
    futex_up(&unused_futex);
 
    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 3110	Rev 3111
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 <libadt/hash_table.h>
43	#include <libadt/list.h>	43	#include <libadt/list.h>
44	#include <assert.h>	44	#include <assert.h>
45	#include <futex.h>	45	#include <futex.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	/** Futex protecting the list of unused structures. */
72	static futex_t unused_futex = FUTEX_INITIALIZER;	72	static futex_t unused_futex = FUTEX_INITIALIZER;
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)
-		87	{
-		88	unused_t *u;
-		89	link_t *l;
-		90
-		91	if (lock)
-		92	futex_down(&unused_futex);
-		93	for (l = unused_head.next; l != &unused_head; l = l->next) {
-		94	u = list_get_instance(l, unused_t, link);
-		95	if (u->dev_handle == dev_handle)
-		96	return u;
-		97	}
-		98	if (lock)
-		99	futex_up(&unused_futex);
-		100	return NULL;
-		101	}
-		102
86	/** Futex protecting the up_hash and ui_hash. */	103	/** Futex protecting the up_hash and ui_hash. */
87	static futex_t used_futex = FUTEX_INITIALIZER;	104	static futex_t used_futex = FUTEX_INITIALIZER;
88		105
89	/**	106	/**
90	* Global hash table of all used fat_idx_t structures.	107	* Global hash table of all used fat_idx_t structures.
91	* 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
92	* cluster and index within the parent directory.	109	* cluster and index within the parent directory.
93	*/	110	*/
94	static hash_table_t up_hash;	111	static hash_table_t up_hash;
95		112
96	#define UPH_BUCKETS_LOG 12	113	#define UPH_BUCKETS_LOG 12
97	#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)	114	#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)
98		115
99	#define UPH_DH_KEY 0	116	#define UPH_DH_KEY 0
100	#define UPH_PFC_KEY 1	117	#define UPH_PFC_KEY 1
101	#define UPH_PDI_KEY 2	118	#define UPH_PDI_KEY 2
102		119
103	static hash_index_t pos_hash(unsigned long key[])	120	static hash_index_t pos_hash(unsigned long key[])
104	{	121	{
105	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];
106	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];	123	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
107	unsigned pdi = (unsigned)key[UPH_PDI_KEY];	124	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
108		125
109	hash_index_t h;	126	hash_index_t h;
110		127
111	/*	128	/*
112	* 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
113	* of the parent node's first cluster.	130	* of the parent node's first cluster.
114	*	131	*
115	* 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
116	* 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
117	* parent directory node.	134	* parent directory node.
118	*	135	*
119	* 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
120	* are the least significant bits of the device handle.	137	* are the least significant bits of the device handle.
121	*/	138	*/
122	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);	139	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
123	h \|= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<	140	h \|= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
124	(UPH_BUCKETS_LOG / 2);	141	(UPH_BUCKETS_LOG / 2);
125	h \|= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<	142	h \|= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
126	(3 * (UPH_BUCKETS_LOG / 4));	143	(3 * (UPH_BUCKETS_LOG / 4));
127		144
128	return h;	145	return h;
129	}	146	}
130		147
131	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)
132	{	149	{
133	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];
134	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];	151	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
135	unsigned pdi = (unsigned)key[UPH_PDI_KEY];	152	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
136	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);
137		154
138	return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&	155	return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
139	(pdi == fidx->pdi);	156	(pdi == fidx->pdi);
140	}	157	}
141		158
142	static void pos_remove_callback(link_t *item)	159	static void pos_remove_callback(link_t *item)
143	{	160	{
144	/* nothing to do */	161	/* nothing to do */
145	}	162	}
146		163
147	static hash_table_operations_t uph_ops = {	164	static hash_table_operations_t uph_ops = {
148	.hash = pos_hash,	165	.hash = pos_hash,
149	.compare = pos_compare,	166	.compare = pos_compare,
150	.remove_callback = pos_remove_callback,	167	.remove_callback = pos_remove_callback,
151	};	168	};
152		169
153	/**	170	/**
154	* Global hash table of all used fat_idx_t structures.	171	* Global hash table of all used fat_idx_t structures.
155	* The index structures are hashed by the dev_handle and index.	172	* The index structures are hashed by the dev_handle and index.
156	*/	173	*/
157	static hash_table_t ui_hash;	174	static hash_table_t ui_hash;
158		175
159	#define UIH_BUCKETS_LOG 12	176	#define UIH_BUCKETS_LOG 12
160	#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)	177	#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)
161		178
162	#define UIH_DH_KEY 0	179	#define UIH_DH_KEY 0
163	#define UIH_INDEX_KEY 1	180	#define UIH_INDEX_KEY 1
164		181
165	static hash_index_t idx_hash(unsigned long key[])	182	static hash_index_t idx_hash(unsigned long key[])
166	{	183	{
167	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];
168	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];	185	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
169		186
170	hash_index_t h;	187	hash_index_t h;
171		188
172	h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);	189	h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
173	h \|= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<	190	h \|= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
174	(UIH_BUCKETS_LOG / 2);	191	(UIH_BUCKETS_LOG / 2);
175		192
176	return h;	193	return h;
177	}	194	}
178		195
179	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)
180	{	197	{
181	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];
182	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];	199	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
183	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);
184		201
185	return (dev_handle == fidx->dev_handle) && (index == fidx->index);	202	return (dev_handle == fidx->dev_handle) && (index == fidx->index);
186	}	203	}
187		204
188	static void idx_remove_callback(link_t *item)	205	static void idx_remove_callback(link_t *item)
189	{	206	{
190	/* nothing to do */	207	/* nothing to do */
191	}	208	}
192		209
193	static hash_table_operations_t uih_ops = {	210	static hash_table_operations_t uih_ops = {
194	.hash = idx_hash,	211	.hash = idx_hash,
195	.compare = idx_compare,	212	.compare = idx_compare,
196	.remove_callback = idx_remove_callback,	213	.remove_callback = idx_remove_callback,
197	};	214	};
198		215
199	/** Allocate a VFS index which is not currently in use. */	216	/** Allocate a VFS index which is not currently in use. */
200	static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)	217	static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)
201	{	218	{
202	link_t *l;	-
203	unused_t *u;	219	unused_t *u;
204		220
205	assert(index);	221	assert(index);
206	futex_down(&unused_futex);	-
207	for (l = unused_head.next; l != &unused_head; l = l->next) {	-
208	u = list_get_instance(l, unused_t, link);	-
209	if (u->dev_handle == dev_handle)	222	u = unused_find(dev_handle, true);
210	goto hit;	223	if (!u)
211	}	-
212	futex_up(&unused_futex);	-
213		-
214	/* dev_handle not found */	-
215	return false;	224	return false;
216		225
217	hit:	-
218	if (list_empty(&u->freed_head)) {	226	if (list_empty(&u->freed_head)) {
219	if (u->remaining) {	227	if (u->remaining) {
220	/*	228	/*
221	* There are no freed indices, allocate one directly	229	* There are no freed indices, allocate one directly
222	* from the counter.	230	* from the counter.
223	*/	231	*/
224	*index = u->next++;	232	*index = u->next++;
225	--u->remaining;	233	--u->remaining;
226	futex_up(&unused_futex);	234	futex_up(&unused_futex);
227	return true;	235	return true;
228	}	236	}
229	} else {	237	} else {
230	/* There are some freed indices which we can reuse. */	238	/* There are some freed indices which we can reuse. */
231	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,
232	link);	240	link);
233	*index = f->first;	241	*index = f->first;
234	if (f->first++ == f->last) {	242	if (f->first++ == f->last) {
235	/* Destroy the interval. */	243	/* Destroy the interval. */
236	list_remove(&f->link);	244	list_remove(&f->link);
237	free(f);	245	free(f);
238	}	246	}
239	futex_up(&unused_futex);	247	futex_up(&unused_futex);
240	return true;	248	return true;
241	}	249	}
242	/*	250	/*
243	* 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
244	* theoretically still possible (e.g. too many open unlinked nodes or	252	* theoretically still possible (e.g. too many open unlinked nodes or
245	* too many zero-sized nodes).	253	* too many zero-sized nodes).
246	*/	254	*/
247	futex_up(&unused_futex);	255	futex_up(&unused_futex);
248	return false;	256	return false;
249	}	257	}
250		258
251	/** If possible, coalesce two intervals of freed indices. */	259	/** If possible, coalesce two intervals of freed indices. */
252	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)
253	{	261	{
254	freed_t *fl = list_get_instance(l, freed_t, link);	262	freed_t *fl = list_get_instance(l, freed_t, link);
255	freed_t *fr = list_get_instance(r, freed_t, link);	263	freed_t *fr = list_get_instance(r, freed_t, link);
256		264
257	if (fl->last + 1 == fr->first) {	265	if (fl->last + 1 == fr->first) {
258	if (cur == l) {	266	if (cur == l) {
259	fl->last = fr->last;	267	fl->last = fr->last;
260	list_remove(r);	268	list_remove(r);
261	free(r);	269	free(r);
262	} else {	270	} else {
263	fr->first = fl->first;	271	fr->first = fl->first;
264	list_remove(l);	272	list_remove(l);
265	free(l);	273	free(l);
266	}	274	}
267	}	275	}
268	}	276	}
269		277
270	/** Free a VFS index, which is no longer in use. */	278	/** Free a VFS index, which is no longer in use. */
271	static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)	279	static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)
272	{	280	{
273	link_t *l;	-
274	unused_t *u;	281	unused_t *u;
275		282
276	futex_down(&unused_futex);	-
277	for (l = unused_head.next; l != &unused_head; l = l->next) {	-
278	u = list_get_instance(l, unused_t, link);	-
279	if (u->dev_handle == dev_handle)	283	u = unused_find(dev_handle, true);
280	goto hit;	-
281	}	-
282	futex_up(&unused_futex);	-
283		-
284	/* should not happen */	-
285	assert(0);	284	assert(u);
286		285
287	hit:	-
288	if (u->next == index + 1) {	286	if (u->next == index + 1) {
289	/* The index can be returned directly to the counter. */	287	/* The index can be returned directly to the counter. */
290	u->next--;	288	u->next--;
291	u->remaining++;	289	u->remaining++;
292	} else {	290	} else {
293	/*	291	/*
294	* The index must be returned either to an existing freed	292	* The index must be returned either to an existing freed
295	* interval or a new interval must be created.	293	* interval or a new interval must be created.
296	*/	294	*/
297	link_t *lnk;	295	link_t *lnk;
298	freed_t *n;	296	freed_t *n;
299	for (lnk = u->freed_head.next; lnk != &u->freed_head;	297	for (lnk = u->freed_head.next; lnk != &u->freed_head;
300	lnk = lnk->next) {	298	lnk = lnk->next) {
301	freed_t *f = list_get_instance(lnk, freed_t, link);	299	freed_t *f = list_get_instance(lnk, freed_t, link);
302	if (f->first == index + 1) {	300	if (f->first == index + 1) {
303	f->first--;	301	f->first--;
304	if (lnk->prev != &u->freed_head)	302	if (lnk->prev != &u->freed_head)
305	try_coalesce_intervals(lnk->prev, lnk,	303	try_coalesce_intervals(lnk->prev, lnk,
306	lnk);	304	lnk);
307	futex_up(&unused_futex);	305	futex_up(&unused_futex);
308	return;	306	return;
309	}	307	}
310	if (f->last == index - 1) {	308	if (f->last == index - 1) {
311	f->last++;	309	f->last++;
312	if (lnk->next != &u->freed_head)	310	if (lnk->next != &u->freed_head)
313	try_coalesce_intervals(lnk, lnk->next,	311	try_coalesce_intervals(lnk, lnk->next,
314	lnk);	312	lnk);
315	futex_up(&unused_futex);	313	futex_up(&unused_futex);
316	return;	314	return;
317	}	315	}
318	if (index > f->first) {	316	if (index > f->first) {
319	n = malloc(sizeof(freed_t));	317	n = malloc(sizeof(freed_t));
320	/* TODO: sleep until allocation succeeds */	318	/* TODO: sleep until allocation succeeds */
321	assert(n);	319	assert(n);
322	link_initialize(&n->link);	320	link_initialize(&n->link);
323	n->first = index;	321	n->first = index;
324	n->last = index;	322	n->last = index;
325	list_insert_before(&n->link, lnk);	323	list_insert_before(&n->link, lnk);
326	futex_up(&unused_futex);	324	futex_up(&unused_futex);
327	return;	325	return;
328	}	326	}
329		327
330	}	328	}
331	/* The index will form the last interval. */	329	/* The index will form the last interval. */
332	n = malloc(sizeof(freed_t));	330	n = malloc(sizeof(freed_t));
333	/* TODO: sleep until allocation succeeds */	331	/* TODO: sleep until allocation succeeds */
334	assert(n);	332	assert(n);
335	link_initialize(&n->link);	333	link_initialize(&n->link);
336	n->first = index;	334	n->first = index;
337	n->last = index;	335	n->last = index;
338	list_append(&n->link, &u->freed_head);	336	list_append(&n->link, &u->freed_head);
339	}	337	}
340	futex_up(&unused_futex);	338	futex_up(&unused_futex);
341	}	339	}
342		340
343	fat_idx_t *	341	fat_idx_t *
344	fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)	342	fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
345	{	343	{
346	fat_idx_t *fidx;	344	fat_idx_t *fidx;
347	link_t *l;	345	link_t *l;
348	unsigned long pkey[] = {	346	unsigned long pkey[] = {
349	[UPH_DH_KEY] = dev_handle,	347	[UPH_DH_KEY] = dev_handle,
350	[UPH_PFC_KEY] = pfc,	348	[UPH_PFC_KEY] = pfc,
351	[UPH_PDI_KEY] = pdi,	349	[UPH_PDI_KEY] = pdi,
352	};	350	};
353		351
354	futex_down(&used_futex);	352	futex_down(&used_futex);
355	l = hash_table_find(&up_hash, pkey);	353	l = hash_table_find(&up_hash, pkey);
356	if (l) {	354	if (l) {
357	fidx = hash_table_get_instance(l, fat_idx_t, uph_link);	355	fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
358	} else {	356	} else {
359	fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));	357	fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
360	if (!fidx) {	358	if (!fidx) {
361	futex_up(&used_futex);	359	futex_up(&used_futex);
362	return NULL;	360	return NULL;
363	}	361	}
364	if (!fat_idx_alloc(dev_handle, &fidx->index)) {	362	if (!fat_idx_alloc(dev_handle, &fidx->index)) {
365	free(fidx);	363	free(fidx);
366	futex_up(&used_futex);	364	futex_up(&used_futex);
367	return NULL;	365	return NULL;
368	}	366	}
369		367
370	unsigned long ikey[] = {	368	unsigned long ikey[] = {
371	[UIH_DH_KEY] = dev_handle,	369	[UIH_DH_KEY] = dev_handle,
372	[UIH_INDEX_KEY] = fidx->index,	370	[UIH_INDEX_KEY] = fidx->index,
373	};	371	};
374		372
375	link_initialize(&fidx->uph_link);	373	link_initialize(&fidx->uph_link);
376	link_initialize(&fidx->uih_link);	374	link_initialize(&fidx->uih_link);
377	futex_initialize(&fidx->lock, 1);	375	futex_initialize(&fidx->lock, 1);
378	fidx->dev_handle = dev_handle;	376	fidx->dev_handle = dev_handle;
379	fidx->pfc = pfc;	377	fidx->pfc = pfc;
380	fidx->pdi = pdi;	378	fidx->pdi = pdi;
381	fidx->nodep = NULL;	379	fidx->nodep = NULL;
382		380
383	hash_table_insert(&up_hash, pkey, &fidx->uph_link);	381	hash_table_insert(&up_hash, pkey, &fidx->uph_link);
384	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);	382	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
385	}	383	}
386	futex_down(&fidx->lock);	384	futex_down(&fidx->lock);
387	futex_up(&used_futex);	385	futex_up(&used_futex);
388		386
389	return fidx;	387	return fidx;
390	}	388	}
391		389
392	fat_idx_t *	390	fat_idx_t *
393	fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)	391	fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
394	{	392	{
395	fat_idx_t *fidx = NULL;	393	fat_idx_t *fidx = NULL;
396	link_t *l;	394	link_t *l;
397	unsigned long ikey[] = {	395	unsigned long ikey[] = {
398	[UIH_DH_KEY] = dev_handle,	396	[UIH_DH_KEY] = dev_handle,
399	[UIH_INDEX_KEY] = index,	397	[UIH_INDEX_KEY] = index,
400	};	398	};
401		399
402	futex_down(&used_futex);	400	futex_down(&used_futex);
403	l = hash_table_find(&ui_hash, ikey);	401	l = hash_table_find(&ui_hash, ikey);
404	if (l) {	402	if (l) {
405	fidx = hash_table_get_instance(l, fat_idx_t, uih_link);	403	fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
406	futex_down(&fidx->lock);	404	futex_down(&fidx->lock);
407	}	405	}
408	futex_up(&used_futex);	406	futex_up(&used_futex);
409		407
410	return fidx;	408	return fidx;
411	}	409	}
412		410
413	int fat_idx_init(void)	411	int fat_idx_init(void)
414	{	412	{
415	if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))	413	if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
416	return ENOMEM;	414	return ENOMEM;
417	if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {	415	if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
418	hash_table_destroy(&up_hash);	416	hash_table_destroy(&up_hash);
419	return ENOMEM;	417	return ENOMEM;
420	}	418	}
421	return EOK;	419	return EOK;
422	}	420	}
423		421
424	void fat_idx_fini(void)	422	void fat_idx_fini(void)
425	{	423	{
426	/* We assume the hash tables are empty. */	424	/* We assume the hash tables are empty. */
427	hash_table_destroy(&up_hash);	425	hash_table_destroy(&up_hash);
428	hash_table_destroy(&ui_hash);	426	hash_table_destroy(&ui_hash);
429	}	427	}
430		428
431	int fat_idx_init_by_dev_handle(dev_handle_t dev_handle)	429	int fat_idx_init_by_dev_handle(dev_handle_t dev_handle)
432	{	430	{
-		431	unused_t *u;
-		432	int rc = EOK;
-		433
433	unused_t u = (unused_t ) malloc(sizeof(unused_t));	434	u = (unused_t *) malloc(sizeof(unused_t));
434	if (!u)	435	if (!u)
435	return ENOMEM;	436	return ENOMEM;
436	unused_initialize(u, dev_handle);	437	unused_initialize(u, dev_handle);
437	futex_down(&unused_futex);	438	futex_down(&unused_futex);
-		439	if (!unused_find(dev_handle, false))
438	list_append(&u->link, &unused_head);	440	list_append(&u->link, &unused_head);
-		441	else
-		442	rc = EEXIST;
439	futex_up(&unused_futex);	443	futex_up(&unused_futex);
440	return EOK;	444	return rc;
441	}	445	}
442		446
443	void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)	447	void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)
444	{	448	{
445	unused_t *u;	449	unused_t *u;
446	link_t *l;	-
447		-
448	futex_down(&unused_futex);	-
449	for (l = unused_head.next; l != &unused_head; l = l->next) {	-
450	u = list_get_instance(l, unused_t, link);	-
451	if (u->dev_handle == dev_handle)	-
452	goto hit;	-
453	}	-
454	futex_up(&unused_futex);	-
455		-
456	assert(false); /* should not happen */	-
457		450
-		451	u = unused_find(dev_handle, true);
458	hit:	452	assert(u);
459	list_remove(&u->link);	453	list_remove(&u->link);
460	futex_up(&unused_futex);	454	futex_up(&unused_futex);
461		455
462	while (!list_empty(&u->freed_head)) {	456	while (!list_empty(&u->freed_head)) {
463	freed_t *f;	457	freed_t *f;
464	f = list_get_instance(u->freed_head.next, freed_t, link);	458	f = list_get_instance(u->freed_head.next, freed_t, link);
465	list_remove(&f->link);	459	list_remove(&f->link);
466	free(f);	460	free(f);
467	}	461	}
468	free(u);	462	free(u);
469	}	463	}
470		464
471	/**	465	/**
472	* @}	466	* @}
473	*/	467	*/
474		468

Subversion Repositories HelenOS

(root)/trunk/uspace/srv/fs/fat/fat_idx.c – Rev 3110 → 3111