source: mainline/uspace/srv/fs/fat/fat_idx.c@ 34b3ce3

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 34b3ce3 was 4797132, checked in by Jakub Jermar <jakub@…>, 17 years ago

Need a way to locate the FAT index structure by VFS index. Also fix code that
locates the FAT index structure by position in the file system namespace.
  • Property mode set to 100644
File size: 9.4 KB
Line 
1/*
2 * Copyright (c) 2008 Jakub Jermar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
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
15 * derived from this software without specific prior written permission.
16 *
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
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
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
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
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup fs
30 * @{
31 */
32
33/**
34 * @file fat_idx.c
35 * @brief Layer for translating FAT entities to VFS node indices.
36 */
37
38#include "fat.h"
39#include "../../vfs/vfs.h"
40#include <errno.h>
41#include <string.h>
42#include <libadt/hash_table.h>
43#include <libadt/list.h>
44#include <assert.h>
45#include <futex.h>
46
47/** Each instance of this type describes one interval of freed VFS indices. */
48typedef struct {
49 link_t link;
50 fs_index_t first;
51 fs_index_t last;
52} freed_t;
53
54/**
55 * Each instance of this type describes state of all VFS indices that
56 * are currently unused.
57 */
58typedef struct {
59 link_t link;
60 dev_handle_t dev_handle;
61
62 /** Next unassigned index. */
63 fs_index_t next;
64 /** Number of remaining unassigned indices. */
65 uint64_t remaining;
66
67 /** Sorted list of intervals of freed indices. */
68 link_t freed_head;
69} unused_t;
70
71static LIST_INITIALIZE(unused_head);
72
73/**
74 * Global hash table of all used fat_idx_t structures.
75 * The index structures are hashed by the dev_handle, parent node's first
76 * cluster and index within the parent directory.
77 */
78static hash_table_t up_hash;
79
80#define UPH_BUCKETS_LOG 12
81#define UPH_BUCKETS (1 << UPH_BUCKETS_LOG)
82
83#define UPH_DH_KEY 0
84#define UPH_PFC_KEY 1
85#define UPH_PDI_KEY 2
86
87static hash_index_t pos_hash(unsigned long key[])
88{
89 dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
90 fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
91 unsigned pdi = (unsigned)key[UPH_PDI_KEY];
92
93 hash_index_t h;
94
95 /*
96 * The least significant half of all bits are the least significant bits
97 * of the parent node's first cluster.
98 *
99 * The least significant half of the most significant half of all bits
100 * are the least significant bits of the node's dentry index within the
101 * parent directory node.
102 *
103 * The most significant half of the most significant half of all bits
104 * are the least significant bits of the device handle.
105 */
106 h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
107 h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
108 (UPH_BUCKETS_LOG / 2);
109 h |= (dev_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
110 (3 * (UPH_BUCKETS_LOG / 4));
111
112 return h;
113}
114
115static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
116{
117 dev_handle_t dev_handle = (dev_handle_t)key[UPH_DH_KEY];
118 fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
119 unsigned pdi = (unsigned)key[UPH_PDI_KEY];
120 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
121
122 return (dev_handle == fidx->dev_handle) && (pfc == fidx->pfc) &&
123 (pdi == fidx->pdi);
124}
125
126static void pos_remove_callback(link_t *item)
127{
128 /* nothing to do */
129}
130
131static hash_table_operations_t uph_ops = {
132 .hash = pos_hash,
133 .compare = pos_compare,
134 .remove_callback = pos_remove_callback,
135};
136
137/**
138 * Global hash table of all used fat_idx_t structures.
139 * The index structures are hashed by the dev_handle and index.
140 */
141static hash_table_t ui_hash;
142
143#define UIH_BUCKETS_LOG 12
144#define UIH_BUCKETS (1 << UIH_BUCKETS_LOG)
145
146#define UIH_DH_KEY 0
147#define UIH_INDEX_KEY 1
148
149static hash_index_t idx_hash(unsigned long key[])
150{
151 dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
152 fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
153
154 hash_index_t h;
155
156 h = dev_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
157 h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
158 (UIH_BUCKETS_LOG / 2);
159
160 return h;
161}
162
163static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
164{
165 dev_handle_t dev_handle = (dev_handle_t)key[UIH_DH_KEY];
166 fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
167 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
168
169 return (dev_handle == fidx->dev_handle) && (index == fidx->index);
170}
171
172static void idx_remove_callback(link_t *item)
173{
174 /* nothing to do */
175}
176
177static hash_table_operations_t uih_ops = {
178 .hash = idx_hash,
179 .compare = idx_compare,
180 .remove_callback = idx_remove_callback,
181};
182
183/** Allocate a VFS index which is not currently in use. */
184static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index)
185{
186 link_t *l;
187 unused_t *u;
188
189 assert(index);
190 for (l = unused_head.next; l != &unused_head; l = l->next) {
191 u = list_get_instance(l, unused_t, link);
192 if (u->dev_handle == dev_handle)
193 goto hit;
194 }
195
196 /* dev_handle not found */
197 return false;
198
199hit:
200 if (list_empty(&u->freed_head)) {
201 if (u->remaining) {
202 /*
203 * There are no freed indices, allocate one directly
204 * from the counter.
205 */
206 *index = u->next++;
207 --u->remaining;
208 return true;
209 }
210 } else {
211 /* There are some freed indices which we can reuse. */
212 freed_t *f = list_get_instance(u->freed_head.next, freed_t,
213 link);
214 *index = f->first;
215 if (f->first++ == f->last) {
216 /* Destroy the interval. */
217 list_remove(&f->link);
218 free(f);
219 }
220 return true;
221 }
222 /*
223 * We ran out of indices, which is extremely unlikely with FAT16, but
224 * theoretically still possible (e.g. too many open unlinked nodes or
225 * too many zero-sized nodes).
226 */
227 return false;
228}
229
230/** If possible, coalesce two intervals of freed indices. */
231static void try_coalesce_intervals(link_t *l, link_t *r, link_t *cur)
232{
233 freed_t *fl = list_get_instance(l, freed_t, link);
234 freed_t *fr = list_get_instance(r, freed_t, link);
235
236 if (fl->last + 1 == fr->first) {
237 if (cur == l) {
238 fl->last = fr->last;
239 list_remove(r);
240 free(r);
241 } else {
242 fr->first = fl->first;
243 list_remove(l);
244 free(l);
245 }
246 }
247}
248
249/** Free a VFS index, which is no longer in use. */
250static void fat_idx_free(dev_handle_t dev_handle, fs_index_t index)
251{
252 link_t *l;
253 unused_t *u;
254
255 for (l = unused_head.next; l != &unused_head; l = l->next) {
256 u = list_get_instance(l, unused_t, link);
257 if (u->dev_handle == dev_handle)
258 goto hit;
259 }
260
261 /* should not happen */
262 assert(0);
263
264hit:
265 if (u->next == index + 1) {
266 /* The index can be returned directly to the counter. */
267 u->next--;
268 u->remaining++;
269 return;
270 } else {
271 /*
272 * The index must be returned either to an existing freed
273 * interval or a new interval must be created.
274 */
275 link_t *lnk;
276 freed_t *n;
277 for (lnk = u->freed_head.next; lnk != &u->freed_head;
278 lnk = lnk->next) {
279 freed_t *f = list_get_instance(lnk, freed_t, link);
280 if (f->first == index + 1) {
281 f->first--;
282 if (lnk->prev != &u->freed_head)
283 try_coalesce_intervals(lnk->prev, lnk,
284 lnk);
285 return;
286 }
287 if (f->last == index - 1) {
288 f->last++;
289 if (lnk->next != &u->freed_head)
290 try_coalesce_intervals(lnk, lnk->next,
291 lnk);
292 return;
293 }
294 if (index > f->first) {
295 n = malloc(sizeof(freed_t));
296 /* TODO: sleep until allocation succeeds */
297 assert(n);
298 link_initialize(&n->link);
299 n->first = index;
300 n->last = index;
301 list_insert_before(&n->link, lnk);
302 return;
303 }
304
305 }
306 /* The index will form the last interval. */
307 n = malloc(sizeof(freed_t));
308 /* TODO: sleep until allocation succeeds */
309 assert(n);
310 link_initialize(&n->link);
311 n->first = index;
312 n->last = index;
313 list_append(&n->link, &u->freed_head);
314 }
315}
316
317fat_idx_t *
318fat_idx_get_by_pos(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi)
319{
320 fat_idx_t *fidx;
321 link_t *l;
322 unsigned long pkey[] = {
323 [UPH_DH_KEY] = dev_handle,
324 [UPH_PFC_KEY] = pfc,
325 [UPH_PDI_KEY] = pdi,
326 };
327
328 l = hash_table_find(&up_hash, pkey);
329 if (l) {
330 fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
331 } else {
332 fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
333 if (!fidx) {
334 return NULL;
335 }
336 if (!fat_idx_alloc(dev_handle, &fidx->index)) {
337 free(fidx);
338 return NULL;
339 }
340
341 unsigned long ikey[] = {
342 [UIH_DH_KEY] = dev_handle,
343 [UIH_INDEX_KEY] = fidx->index,
344 };
345
346 link_initialize(&fidx->uph_link);
347 link_initialize(&fidx->uih_link);
348 fidx->dev_handle = dev_handle;
349 fidx->pfc = pfc;
350 fidx->pdi = pdi;
351 fidx->nodep = NULL;
352
353 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
354 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
355 }
356
357 return fidx;
358}
359
360fat_idx_t *
361fat_idx_get_by_index(dev_handle_t dev_handle, fs_index_t index)
362{
363 fat_idx_t *fidx = NULL;
364 link_t *l;
365 unsigned long ikey[] = {
366 [UIH_DH_KEY] = dev_handle,
367 [UIH_INDEX_KEY] = index,
368 };
369
370 l = hash_table_find(&ui_hash, ikey);
371 if (l) {
372 fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
373 }
374
375 return fidx;
376}
377
Note: See TracBrowser for help on using the repository browser.