Subversion Repositories HelenOS

Rev

Rev 4509 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 4509 Rev 4552
Line 40... Line 40...
40
#include <errno.h>
40
#include <errno.h>
41
#include <string.h>
41
#include <string.h>
42
#include <adt/hash_table.h>
42
#include <adt/hash_table.h>
43
#include <adt/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;
Line 66... Line 66...
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)
Line 87... Line 87...
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.
Line 229... Line 229...
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,
Line 242... Line 242...
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)
Line 300... Line 300...
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. */
Line 333... Line 333...
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;
Line 350... Line 350...
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
 
Line 363... Line 363...
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 *
Line 393... Line 393...
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,
Line 415... Line 415...
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)
Line 429... Line 429...
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
{
Line 457... Line 457...
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
        futex_down(&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.
Line 481... Line 481...
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
}
Line 522... Line 522...
522
 
522
 
523
    u = (unused_t *) malloc(sizeof(unused_t));
523
    u = (unused_t *) malloc(sizeof(unused_t));
524
    if (!u)
524
    if (!u)
525
        return ENOMEM;
525
        return ENOMEM;
526
    unused_initialize(u, dev_handle);
526
    unused_initialize(u, dev_handle);
527
    futex_down(&unused_futex);
527
    fibril_mutex_lock(&unused_lock);
528
    if (!unused_find(dev_handle, false))
528
    if (!unused_find(dev_handle, false))
529
        list_append(&u->link, &unused_head);
529
        list_append(&u->link, &unused_head);
530
    else
530
    else
531
        rc = EEXIST;
531
        rc = EEXIST;
532
    futex_up(&unused_futex);
532
    fibril_mutex_unlock(&unused_lock);
533
    return rc;
533
    return rc;
534
}
534
}
535
 
535
 
536
void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)
536
void fat_idx_fini_by_dev_handle(dev_handle_t dev_handle)
537
{
537
{
538
    unused_t *u;
538
    unused_t *u;
539
 
539
 
540
    u = unused_find(dev_handle, true);
540
    u = unused_find(dev_handle, true);
541
    assert(u);
541
    assert(u);
542
    list_remove(&u->link);
542
    list_remove(&u->link);
543
    futex_up(&unused_futex);
543
    fibril_mutex_unlock(&unused_lock);
544
 
544
 
545
    while (!list_empty(&u->freed_head)) {
545
    while (!list_empty(&u->freed_head)) {
546
        freed_t *f;
546
        freed_t *f;
547
        f = list_get_instance(u->freed_head.next, freed_t, link);
547
        f = list_get_instance(u->freed_head.next, freed_t, link);
548
        list_remove(&f->link);
548
        list_remove(&f->link);