36,6 → 36,7 |
*/ |
|
#include "fat.h" |
#include "../../vfs/vfs.h" |
#include <errno.h> |
#include <string.h> |
#include <libadt/hash_table.h> |
43,7 → 44,167 |
#include <assert.h> |
#include <futex.h> |
|
fat_idx_t *fat_idx_map(fat_cluster_t pfc, unsigned pdi) |
/** 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; |
|
static LIST_INITIALIZE(unused_head); |
|
/** Allocate a VFS index which is not currently in use. */ |
static bool fat_idx_alloc(dev_handle_t dev_handle, fs_index_t *index) |
{ |
link_t *l; |
unused_t *u; |
|
assert(index); |
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) |
goto hit; |
} |
|
/* dev_handle not found */ |
return false; |
|
hit: |
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; |
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); |
} |
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). |
*/ |
return false; |
} |
|
/** If possible, merge two intervals of freed indices. */ |
static void try_merge_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) |
{ |
link_t *l; |
unused_t *u; |
|
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) |
goto hit; |
} |
|
/* should not happen */ |
assert(0); |
|
hit: |
if (u->next == index + 1) { |
/* The index can be returned directly to the counter. */ |
u->next--; |
u->remaining++; |
return; |
} 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_merge_intervals(lnk->prev, lnk, |
lnk); |
return; |
} |
if (f->last == index - 1) { |
f->last++; |
if (lnk->next != &u->freed_head) |
try_merge_intervals(lnk, lnk->next, |
lnk); |
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); |
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); |
} |
} |
|
fat_idx_t *fat_idx_map(dev_handle_t dev_handle, fat_cluster_t pfc, unsigned pdi) |
{ |
return NULL; /* TODO */ |
} |