68,8 → 68,23 |
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); |
|
/** Futex protecting the up_hash and ui_hash. |
* |
* The locking strategy assumes that there will be at most one fibril for each |
* dev_handle. Therefore it will be sufficient to hold the futex for shorter |
* times (i.e. only during hash table operations as opposed to holding it the |
* whole time between an unsuccessful find and the following insert). Should the |
* assumption break, the locking strategy for this futex will have to be |
* reconsidered. |
*/ |
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 |
187,12 → 202,14 |
unused_t *u; |
|
assert(index); |
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) |
goto hit; |
} |
|
futex_up(&unused_futex); |
|
/* dev_handle not found */ |
return false; |
|
205,6 → 222,7 |
*/ |
*index = u->next++; |
--u->remaining; |
futex_up(&unused_futex); |
return true; |
} |
} else { |
217,6 → 235,7 |
list_remove(&f->link); |
free(f); |
} |
futex_up(&unused_futex); |
return true; |
} |
/* |
224,6 → 243,7 |
* theoretically still possible (e.g. too many open unlinked nodes or |
* too many zero-sized nodes). |
*/ |
futex_up(&unused_futex); |
return false; |
} |
|
252,11 → 272,13 |
link_t *l; |
unused_t *u; |
|
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) |
goto hit; |
} |
futex_up(&unused_futex); |
|
/* should not happen */ |
assert(0); |
266,7 → 288,6 |
/* 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 |
282,6 → 303,7 |
if (lnk->prev != &u->freed_head) |
try_coalesce_intervals(lnk->prev, lnk, |
lnk); |
futex_up(&unused_futex); |
return; |
} |
if (f->last == index - 1) { |
289,6 → 311,7 |
if (lnk->next != &u->freed_head) |
try_coalesce_intervals(lnk, lnk->next, |
lnk); |
futex_up(&unused_futex); |
return; |
} |
if (index > f->first) { |
299,6 → 322,7 |
n->first = index; |
n->last = index; |
list_insert_before(&n->link, lnk); |
futex_up(&unused_futex); |
return; |
} |
|
312,6 → 336,7 |
n->last = index; |
list_append(&n->link, &u->freed_head); |
} |
futex_up(&unused_futex); |
} |
|
fat_idx_t * |
325,7 → 350,9 |
[UPH_PDI_KEY] = pdi, |
}; |
|
futex_down(&used_futex); |
l = hash_table_find(&up_hash, pkey); |
futex_up(&used_futex); |
if (l) { |
fidx = hash_table_get_instance(l, fat_idx_t, uph_link); |
} else { |
350,8 → 377,10 |
fidx->pdi = pdi; |
fidx->nodep = NULL; |
|
futex_down(&used_futex); |
hash_table_insert(&up_hash, pkey, &fidx->uph_link); |
hash_table_insert(&ui_hash, ikey, &fidx->uih_link); |
futex_up(&used_futex); |
} |
|
return fidx; |
367,7 → 396,9 |
[UIH_INDEX_KEY] = index, |
}; |
|
futex_down(&used_futex); |
l = hash_table_find(&ui_hash, ikey); |
futex_up(&used_futex); |
if (l) { |
fidx = hash_table_get_instance(l, fat_idx_t, uih_link); |
} |