source: mainline/uspace/srv/fs/fat/fat_idx.c@ 0ca7286

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 0ca7286 was 0ca7286, checked in by Adam Hraska <adam.hraska+hos@…>, 13 years ago

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.
  • Property mode set to 100644
File size: 13.7 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 <str.h>
42#include <adt/hash_table.h>
43#include <adt/list.h>
44#include <assert.h>
45#include <fibril_synch.h>
46#include <malloc.h>
47
48
49/** Each instance of this type describes one interval of freed VFS indices. */
50typedef struct {
51 link_t link;
52 fs_index_t first;
53 fs_index_t last;
54} freed_t;
55
56/**
57 * Each instance of this type describes state of all VFS indices that
58 * are currently unused.
59 */
60typedef struct {
61 link_t link;
62 service_id_t service_id;
63
64 /** Next unassigned index. */
65 fs_index_t next;
66 /** Number of remaining unassigned indices. */
67 uint64_t remaining;
68
69 /** Sorted list of intervals of freed indices. */
70 list_t freed_list;
71} unused_t;
72
73/** Mutex protecting the list of unused structures. */
74static FIBRIL_MUTEX_INITIALIZE(unused_lock);
75
76/** List of unused structures. */
77static LIST_INITIALIZE(unused_list);
78
79static void unused_initialize(unused_t *u, service_id_t service_id)
80{
81 link_initialize(&u->link);
82 u->service_id = service_id;
83 u->next = 0;
84 u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;
85 list_initialize(&u->freed_list);
86}
87
88static unused_t *unused_find(service_id_t service_id, bool lock)
89{
90 unused_t *u;
91
92 if (lock)
93 fibril_mutex_lock(&unused_lock);
94
95 list_foreach(unused_list, l) {
96 u = list_get_instance(l, unused_t, link);
97 if (u->service_id == service_id)
98 return u;
99 }
100
101 if (lock)
102 fibril_mutex_unlock(&unused_lock);
103 return NULL;
104}
105
106/** Mutex protecting the up_hash and ui_hash. */
107static FIBRIL_MUTEX_INITIALIZE(used_lock);
108
109/**
110 * Global hash table of all used fat_idx_t structures.
111 * The index structures are hashed by the service_id, parent node's first
112 * cluster and index within the parent directory.
113 */
114static hash_table_t up_hash;
115
116#define UPH_SID_KEY 0
117#define UPH_PFC_KEY 1
118#define UPH_PDI_KEY 2
119
120static size_t pos_key_hash(unsigned long key[])
121{
122 /* Inspired by Effective Java, 2nd edition. */
123 size_t hash = 17;
124
125 hash = 31 * hash + key[UPH_PFC_KEY];
126 hash = 31 * hash + key[UPH_PDI_KEY];
127 hash = 31 * hash + key[UPH_SID_KEY];
128
129 return hash;
130}
131
132static size_t pos_hash(const link_t *item)
133{
134 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
135
136 unsigned long pkey[] = {
137 [UPH_SID_KEY] = fidx->service_id,
138 [UPH_PFC_KEY] = fidx->pfc,
139 [UPH_PDI_KEY] = fidx->pdi,
140 };
141
142 return pos_key_hash(pkey);
143}
144
145static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
146{
147 service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
148 fat_cluster_t pfc;
149 unsigned pdi;
150 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
151
152 switch (keys) {
153 case 1:
154 return (service_id == fidx->service_id);
155 case 3:
156 pfc = (fat_cluster_t) key[UPH_PFC_KEY];
157 pdi = (unsigned) key[UPH_PDI_KEY];
158 return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
159 (pdi == fidx->pdi);
160 default:
161 assert((keys == 1) || (keys == 3));
162 }
163
164 return 0;
165}
166
167static hash_table_ops_t uph_ops = {
168 .hash = pos_hash,
169 .key_hash = pos_key_hash,
170 .match = pos_match,
171 .equal = 0,
172 .remove_callback = 0,
173};
174
175/**
176 * Global hash table of all used fat_idx_t structures.
177 * The index structures are hashed by the service_id and index.
178 */
179static hash_table_t ui_hash;
180
181#define UIH_SID_KEY 0
182#define UIH_INDEX_KEY 1
183
184static size_t idx_key_hash(unsigned long key[])
185{
186 /*
187 * Compute a simple hash unlimited by specific table size as per:
188 * Effective Java, 2nd edition.
189 */
190 size_t hash = 17;
191 hash = 31 * hash + key[UIH_SID_KEY];
192 hash = 31 * hash + key[UIH_INDEX_KEY];
193 return hash;
194}
195
196static size_t idx_hash(const link_t *item)
197{
198 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
199
200 unsigned long ikey[] = {
201 [UIH_SID_KEY] = fidx->service_id,
202 [UIH_INDEX_KEY] = fidx->index,
203 };
204
205 return idx_key_hash(ikey);
206}
207
208static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
209{
210 service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
211 fs_index_t index;
212 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
213
214 switch (keys) {
215 case 1:
216 return (service_id == fidx->service_id);
217 case 2:
218 index = (fs_index_t) key[UIH_INDEX_KEY];
219 return (service_id == fidx->service_id) &&
220 (index == fidx->index);
221 default:
222 assert((keys == 1) || (keys == 2));
223 }
224
225 return 0;
226}
227
228static void idx_remove_callback(link_t *item)
229{
230 fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
231
232 free(fidx);
233}
234
235static hash_table_ops_t uih_ops = {
236 .hash = idx_hash,
237 .key_hash = idx_key_hash,
238 .match = idx_match,
239 .equal = 0,
240 .remove_callback = idx_remove_callback,
241};
242
243/** Allocate a VFS index which is not currently in use. */
244static bool fat_index_alloc(service_id_t service_id, fs_index_t *index)
245{
246 unused_t *u;
247
248 assert(index);
249 u = unused_find(service_id, true);
250 if (!u)
251 return false;
252
253 if (list_empty(&u->freed_list)) {
254 if (u->remaining) {
255 /*
256 * There are no freed indices, allocate one directly
257 * from the counter.
258 */
259 *index = u->next++;
260 --u->remaining;
261 fibril_mutex_unlock(&unused_lock);
262 return true;
263 }
264 } else {
265 /* There are some freed indices which we can reuse. */
266 freed_t *f = list_get_instance(list_first(&u->freed_list),
267 freed_t, link);
268 *index = f->first;
269 if (f->first++ == f->last) {
270 /* Destroy the interval. */
271 list_remove(&f->link);
272 free(f);
273 }
274 fibril_mutex_unlock(&unused_lock);
275 return true;
276 }
277 /*
278 * We ran out of indices, which is extremely unlikely with FAT16, but
279 * theoretically still possible (e.g. too many open unlinked nodes or
280 * too many zero-sized nodes).
281 */
282 fibril_mutex_unlock(&unused_lock);
283 return false;
284}
285
286/** If possible, coalesce two intervals of freed indices. */
287static void try_coalesce_intervals(link_t *l, link_t *r, link_t *cur)
288{
289 freed_t *fl = list_get_instance(l, freed_t, link);
290 freed_t *fr = list_get_instance(r, freed_t, link);
291
292 if (fl->last + 1 == fr->first) {
293 if (cur == l) {
294 fl->last = fr->last;
295 list_remove(r);
296 free(r);
297 } else {
298 fr->first = fl->first;
299 list_remove(l);
300 free(l);
301 }
302 }
303}
304
305/** Free a VFS index, which is no longer in use. */
306static void fat_index_free(service_id_t service_id, fs_index_t index)
307{
308 unused_t *u;
309
310 u = unused_find(service_id, true);
311 assert(u);
312
313 if (u->next == index + 1) {
314 /* The index can be returned directly to the counter. */
315 u->next--;
316 u->remaining++;
317 } else {
318 /*
319 * The index must be returned either to an existing freed
320 * interval or a new interval must be created.
321 */
322 link_t *lnk;
323 freed_t *n;
324 for (lnk = u->freed_list.head.next; lnk != &u->freed_list.head;
325 lnk = lnk->next) {
326 freed_t *f = list_get_instance(lnk, freed_t, link);
327 if (f->first == index + 1) {
328 f->first--;
329 if (lnk->prev != &u->freed_list.head)
330 try_coalesce_intervals(lnk->prev, lnk,
331 lnk);
332 fibril_mutex_unlock(&unused_lock);
333 return;
334 }
335 if (f->last == index - 1) {
336 f->last++;
337 if (lnk->next != &u->freed_list.head)
338 try_coalesce_intervals(lnk, lnk->next,
339 lnk);
340 fibril_mutex_unlock(&unused_lock);
341 return;
342 }
343 if (index > f->first) {
344 n = malloc(sizeof(freed_t));
345 /* TODO: sleep until allocation succeeds */
346 assert(n);
347 link_initialize(&n->link);
348 n->first = index;
349 n->last = index;
350 list_insert_before(&n->link, lnk);
351 fibril_mutex_unlock(&unused_lock);
352 return;
353 }
354
355 }
356 /* The index will form the last interval. */
357 n = malloc(sizeof(freed_t));
358 /* TODO: sleep until allocation succeeds */
359 assert(n);
360 link_initialize(&n->link);
361 n->first = index;
362 n->last = index;
363 list_append(&n->link, &u->freed_list);
364 }
365 fibril_mutex_unlock(&unused_lock);
366}
367
368static int fat_idx_create(fat_idx_t **fidxp, service_id_t service_id)
369{
370 fat_idx_t *fidx;
371
372 fidx = (fat_idx_t *) malloc(sizeof(fat_idx_t));
373 if (!fidx)
374 return ENOMEM;
375 if (!fat_index_alloc(service_id, &fidx->index)) {
376 free(fidx);
377 return ENOSPC;
378 }
379
380 link_initialize(&fidx->uph_link);
381 link_initialize(&fidx->uih_link);
382 fibril_mutex_initialize(&fidx->lock);
383 fidx->service_id = service_id;
384 fidx->pfc = FAT_CLST_RES0; /* no parent yet */
385 fidx->pdi = 0;
386 fidx->nodep = NULL;
387
388 *fidxp = fidx;
389 return EOK;
390}
391
392int fat_idx_get_new(fat_idx_t **fidxp, service_id_t service_id)
393{
394 fat_idx_t *fidx;
395 int rc;
396
397 fibril_mutex_lock(&used_lock);
398 rc = fat_idx_create(&fidx, service_id);
399 if (rc != EOK) {
400 fibril_mutex_unlock(&used_lock);
401 return rc;
402 }
403
404 hash_table_insert(&ui_hash, &fidx->uih_link);
405 fibril_mutex_lock(&fidx->lock);
406 fibril_mutex_unlock(&used_lock);
407
408 *fidxp = fidx;
409 return EOK;
410}
411
412fat_idx_t *
413fat_idx_get_by_pos(service_id_t service_id, fat_cluster_t pfc, unsigned pdi)
414{
415 fat_idx_t *fidx;
416 link_t *l;
417 unsigned long pkey[] = {
418 [UPH_SID_KEY] = service_id,
419 [UPH_PFC_KEY] = pfc,
420 [UPH_PDI_KEY] = pdi,
421 };
422
423 fibril_mutex_lock(&used_lock);
424 l = hash_table_find(&up_hash, pkey);
425 if (l) {
426 fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
427 } else {
428 int rc;
429
430 rc = fat_idx_create(&fidx, service_id);
431 if (rc != EOK) {
432 fibril_mutex_unlock(&used_lock);
433 return NULL;
434 }
435
436 fidx->pfc = pfc;
437 fidx->pdi = pdi;
438
439 hash_table_insert(&up_hash, &fidx->uph_link);
440 hash_table_insert(&ui_hash, &fidx->uih_link);
441 }
442 fibril_mutex_lock(&fidx->lock);
443 fibril_mutex_unlock(&used_lock);
444
445 return fidx;
446}
447
448void fat_idx_hashin(fat_idx_t *idx)
449{
450 fibril_mutex_lock(&used_lock);
451 hash_table_insert(&up_hash, &idx->uph_link);
452 fibril_mutex_unlock(&used_lock);
453}
454
455void fat_idx_hashout(fat_idx_t *idx)
456{
457 fibril_mutex_lock(&used_lock);
458 hash_table_remove_item(&up_hash, &idx->uph_link);
459 fibril_mutex_unlock(&used_lock);
460}
461
462fat_idx_t *
463fat_idx_get_by_index(service_id_t service_id, fs_index_t index)
464{
465 fat_idx_t *fidx = NULL;
466 link_t *l;
467 unsigned long ikey[] = {
468 [UIH_SID_KEY] = service_id,
469 [UIH_INDEX_KEY] = index,
470 };
471
472 fibril_mutex_lock(&used_lock);
473 l = hash_table_find(&ui_hash, ikey);
474 if (l) {
475 fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
476 fibril_mutex_lock(&fidx->lock);
477 }
478 fibril_mutex_unlock(&used_lock);
479
480 return fidx;
481}
482
483/** Destroy the index structure.
484 *
485 * @param idx The index structure to be destroyed.
486 */
487void fat_idx_destroy(fat_idx_t *idx)
488{
489 unsigned long ikey[] = {
490 [UIH_SID_KEY] = idx->service_id,
491 [UIH_INDEX_KEY] = idx->index,
492 };
493 service_id_t service_id = idx->service_id;
494 fs_index_t index = idx->index;
495
496 assert(idx->pfc == FAT_CLST_RES0);
497
498 fibril_mutex_lock(&used_lock);
499 /*
500 * Since we can only free unlinked nodes, the index structure is not
501 * present in the position hash (uph). We therefore hash it out from
502 * the index hash only.
503 */
504 hash_table_remove(&ui_hash, ikey, 2);
505 fibril_mutex_unlock(&used_lock);
506 /* Release the VFS index. */
507 fat_index_free(service_id, index);
508 /* The index structure itself is freed in idx_remove_callback(). */
509}
510
511int fat_idx_init(void)
512{
513 if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
514 return ENOMEM;
515 if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
516 hash_table_destroy(&up_hash);
517 return ENOMEM;
518 }
519 return EOK;
520}
521
522void fat_idx_fini(void)
523{
524 /* We assume the hash tables are empty. */
525 hash_table_destroy(&up_hash);
526 hash_table_destroy(&ui_hash);
527}
528
529int fat_idx_init_by_service_id(service_id_t service_id)
530{
531 unused_t *u;
532 int rc = EOK;
533
534 u = (unused_t *) malloc(sizeof(unused_t));
535 if (!u)
536 return ENOMEM;
537 unused_initialize(u, service_id);
538 fibril_mutex_lock(&unused_lock);
539 if (!unused_find(service_id, false)) {
540 list_append(&u->link, &unused_list);
541 } else {
542 free(u);
543 rc = EEXIST;
544 }
545 fibril_mutex_unlock(&unused_lock);
546 return rc;
547}
548
549void fat_idx_fini_by_service_id(service_id_t service_id)
550{
551 unsigned long ikey[] = {
552 [UIH_SID_KEY] = service_id
553 };
554 unsigned long pkey[] = {
555 [UPH_SID_KEY] = service_id
556 };
557
558 /*
559 * Remove this instance's index structure from up_hash and ui_hash.
560 * Process up_hash first and ui_hash second because the index structure
561 * is actually removed in idx_remove_callback().
562 */
563 fibril_mutex_lock(&used_lock);
564 hash_table_remove(&up_hash, pkey, 1);
565 hash_table_remove(&ui_hash, ikey, 1);
566 fibril_mutex_unlock(&used_lock);
567
568 /*
569 * Free the unused and freed structures for this instance.
570 */
571 unused_t *u = unused_find(service_id, true);
572 assert(u);
573 list_remove(&u->link);
574 fibril_mutex_unlock(&unused_lock);
575
576 while (!list_empty(&u->freed_list)) {
577 freed_t *f;
578 f = list_get_instance(list_first(&u->freed_list), freed_t, link);
579 list_remove(&f->link);
580 free(f);
581 }
582 free(u);
583}
584
585/**
586 * @}
587 */
Note: See TracBrowser for help on using the repository browser.