Changes in uspace/srv/fs/exfat/exfat_idx.c [e090244c:4e00f87] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/srv/fs/exfat/exfat_idx.c
re090244c r4e00f87 41 41 #include <str.h> 42 42 #include <adt/hash_table.h> 43 #include <adt/hash.h> 43 44 #include <adt/list.h> 44 45 #include <assert.h> … … 59 60 typedef struct { 60 61 link_t link; 61 devmap_handle_t devmap_handle;62 service_id_t service_id; 62 63 63 64 /** Next unassigned index. */ … … 76 77 static LIST_INITIALIZE(unused_list); 77 78 78 static void unused_initialize(unused_t *u, devmap_handle_t devmap_handle)79 static void unused_initialize(unused_t *u, service_id_t service_id) 79 80 { 80 81 link_initialize(&u->link); 81 u-> devmap_handle = devmap_handle;82 u->service_id = service_id; 82 83 u->next = 0; 83 84 u->remaining = ((uint64_t)((fs_index_t)-1)) + 1; … … 85 86 } 86 87 87 static unused_t *unused_find( devmap_handle_t devmap_handle, bool lock)88 static unused_t *unused_find(service_id_t service_id, bool lock) 88 89 { 89 90 unused_t *u; … … 91 92 if (lock) 92 93 fibril_mutex_lock(&unused_lock); 94 93 95 list_foreach(unused_list, l) { 94 96 u = list_get_instance(l, unused_t, link); 95 if (u-> devmap_handle == devmap_handle)97 if (u->service_id == service_id) 96 98 return u; 97 99 } … … 107 109 /** 108 110 * Global hash table of all used exfat_idx_t structures. 109 * The index structures are hashed by the devmap_handle, parent node's first111 * The index structures are hashed by the service_id, parent node's first 110 112 * cluster and index within the parent directory. 111 113 */ 112 114 static hash_table_t up_hash; 113 115 114 #define UPH_BUCKETS_LOG 12 115 #define UPH_BUCKETS (1 << UPH_BUCKETS_LOG) 116 117 #define UPH_DH_KEY 0 118 #define UPH_PFC_KEY 1 119 #define UPH_PDI_KEY 2 120 121 static hash_index_t pos_hash(unsigned long key[]) 122 { 123 devmap_handle_t devmap_handle = (devmap_handle_t)key[UPH_DH_KEY]; 124 exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY]; 125 unsigned pdi = (unsigned)key[UPH_PDI_KEY]; 126 127 hash_index_t h; 128 129 /* 130 * The least significant half of all bits are the least significant bits 131 * of the parent node's first cluster. 132 * 133 * The least significant half of the most significant half of all bits 134 * are the least significant bits of the node's dentry index within the 135 * parent directory node. 136 * 137 * The most significant half of the most significant half of all bits 138 * are the least significant bits of the device handle. 139 */ 140 h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1); 141 h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << 142 (UPH_BUCKETS_LOG / 2); 143 h |= (devmap_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) << 144 (3 * (UPH_BUCKETS_LOG / 4)); 145 146 return h; 147 } 148 149 static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item) 150 { 151 devmap_handle_t devmap_handle = (devmap_handle_t)key[UPH_DH_KEY]; 116 typedef struct { 117 service_id_t service_id; 152 118 exfat_cluster_t pfc; 153 119 unsigned pdi; 154 exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link); 155 156 switch (keys) { 157 case 1: 158 return (devmap_handle == fidx->devmap_handle); 159 case 3: 160 pfc = (exfat_cluster_t) key[UPH_PFC_KEY]; 161 pdi = (unsigned) key[UPH_PDI_KEY]; 162 return (devmap_handle == fidx->devmap_handle) && (pfc == fidx->pfc) && 163 (pdi == fidx->pdi); 164 default: 165 assert((keys == 1) || (keys == 3)); 166 } 167 168 return 0; 169 } 170 171 static void pos_remove_callback(link_t *item) 172 { 173 /* nothing to do */ 174 } 175 176 static hash_table_operations_t uph_ops = { 120 } pos_key_t; 121 122 static inline size_t pos_key_hash(void *key) 123 { 124 pos_key_t *pos = (pos_key_t*)key; 125 126 size_t hash = 0; 127 hash = hash_combine(pos->pfc, pos->pdi); 128 return hash_combine(hash, pos->service_id); 129 } 130 131 static size_t pos_hash(const ht_link_t *item) 132 { 133 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link); 134 135 pos_key_t pkey = { 136 .service_id = fidx->service_id, 137 .pfc = fidx->pfc, 138 .pdi = fidx->pdi, 139 }; 140 141 return pos_key_hash(&pkey); 142 } 143 144 static bool pos_key_equal(void *key, const ht_link_t *item) 145 { 146 pos_key_t *pos = (pos_key_t*)key; 147 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link); 148 149 return pos->service_id == fidx->service_id 150 && pos->pdi == fidx->pdi 151 && pos->pfc == fidx->pfc; 152 } 153 154 static hash_table_ops_t uph_ops = { 177 155 .hash = pos_hash, 178 .compare = pos_compare, 179 .remove_callback = pos_remove_callback, 156 .key_hash = pos_key_hash, 157 .key_equal = pos_key_equal, 158 .equal = NULL, 159 .remove_callback = NULL, 180 160 }; 181 161 182 162 /** 183 163 * Global hash table of all used fat_idx_t structures. 184 * The index structures are hashed by the devmap_handleand index.164 * The index structures are hashed by the service_id and index. 185 165 */ 186 166 static hash_table_t ui_hash; 187 167 188 #define UIH_BUCKETS_LOG 12 189 #define UIH_BUCKETS (1 << UIH_BUCKETS_LOG) 190 191 #define UIH_DH_KEY 0 192 #define UIH_INDEX_KEY 1 193 194 static hash_index_t idx_hash(unsigned long key[]) 195 { 196 devmap_handle_t devmap_handle = (devmap_handle_t)key[UIH_DH_KEY]; 197 fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY]; 198 199 hash_index_t h; 200 201 h = devmap_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1); 202 h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) << 203 (UIH_BUCKETS_LOG / 2); 204 205 return h; 206 } 207 208 static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item) 209 { 210 devmap_handle_t devmap_handle = (devmap_handle_t)key[UIH_DH_KEY]; 168 typedef struct { 169 service_id_t service_id; 211 170 fs_index_t index; 212 exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link); 213 214 switch (keys) { 215 case 1: 216 return (devmap_handle == fidx->devmap_handle); 217 case 2: 218 index = (fs_index_t) key[UIH_INDEX_KEY]; 219 return (devmap_handle == fidx->devmap_handle) && 220 (index == fidx->index); 221 default: 222 assert((keys == 1) || (keys == 2)); 223 } 224 225 return 0; 226 } 227 228 static void idx_remove_callback(link_t *item) 229 { 230 exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link); 171 } idx_key_t; 172 173 static size_t idx_key_hash(void *key_arg) 174 { 175 idx_key_t *key = (idx_key_t*)key_arg; 176 return hash_combine(key->service_id, key->index); 177 } 178 179 static size_t idx_hash(const ht_link_t *item) 180 { 181 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); 182 return hash_combine(fidx->service_id, fidx->index); 183 } 184 185 static bool idx_key_equal(void *key_arg, const ht_link_t *item) 186 { 187 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); 188 idx_key_t *key = (idx_key_t*)key_arg; 189 190 return key->index == fidx->index && key->service_id == fidx->service_id; 191 } 192 193 static void idx_remove_callback(ht_link_t *item) 194 { 195 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); 231 196 232 197 free(fidx); 233 198 } 234 199 235 static hash_table_op erations_t uih_ops = {200 static hash_table_ops_t uih_ops = { 236 201 .hash = idx_hash, 237 .compare = idx_compare, 202 .key_hash = idx_key_hash, 203 .key_equal = idx_key_equal, 204 .equal = NULL, 238 205 .remove_callback = idx_remove_callback, 239 206 }; 240 207 241 208 /** Allocate a VFS index which is not currently in use. */ 242 static bool exfat_index_alloc( devmap_handle_t devmap_handle, fs_index_t *index)209 static bool exfat_index_alloc(service_id_t service_id, fs_index_t *index) 243 210 { 244 211 unused_t *u; 245 212 246 213 assert(index); 247 u = unused_find( devmap_handle, true);214 u = unused_find(service_id, true); 248 215 if (!u) 249 216 return false; … … 302 269 303 270 /** Free a VFS index, which is no longer in use. */ 304 static void exfat_index_free( devmap_handle_t devmap_handle, fs_index_t index)271 static void exfat_index_free(service_id_t service_id, fs_index_t index) 305 272 { 306 273 unused_t *u; 307 274 308 u = unused_find( devmap_handle, true);275 u = unused_find(service_id, true); 309 276 assert(u); 310 277 … … 364 331 } 365 332 366 static int exfat_idx_create(exfat_idx_t **fidxp, devmap_handle_t devmap_handle)333 static int exfat_idx_create(exfat_idx_t **fidxp, service_id_t service_id) 367 334 { 368 335 exfat_idx_t *fidx; … … 371 338 if (!fidx) 372 339 return ENOMEM; 373 if (!exfat_index_alloc( devmap_handle, &fidx->index)) {340 if (!exfat_index_alloc(service_id, &fidx->index)) { 374 341 free(fidx); 375 342 return ENOSPC; 376 343 } 377 344 378 link_initialize(&fidx->uph_link);379 link_initialize(&fidx->uih_link);380 345 fibril_mutex_initialize(&fidx->lock); 381 fidx-> devmap_handle = devmap_handle;346 fidx->service_id = service_id; 382 347 fidx->pfc = 0; /* no parent yet */ 383 348 fidx->pdi = 0; … … 388 353 } 389 354 390 int exfat_idx_get_new(exfat_idx_t **fidxp, devmap_handle_t devmap_handle)355 int exfat_idx_get_new(exfat_idx_t **fidxp, service_id_t service_id) 391 356 { 392 357 exfat_idx_t *fidx; … … 394 359 395 360 fibril_mutex_lock(&used_lock); 396 rc = exfat_idx_create(&fidx, devmap_handle);361 rc = exfat_idx_create(&fidx, service_id); 397 362 if (rc != EOK) { 398 363 fibril_mutex_unlock(&used_lock); … … 400 365 } 401 366 402 unsigned long ikey[] = { 403 [UIH_DH_KEY] = devmap_handle, 404 [UIH_INDEX_KEY] = fidx->index, 405 }; 406 407 hash_table_insert(&ui_hash, ikey, &fidx->uih_link); 367 hash_table_insert(&ui_hash, &fidx->uih_link); 408 368 fibril_mutex_lock(&fidx->lock); 409 369 fibril_mutex_unlock(&used_lock); … … 414 374 415 375 exfat_idx_t * 416 exfat_idx_get_by_pos( devmap_handle_t devmap_handle, exfat_cluster_t pfc, unsigned pdi)376 exfat_idx_get_by_pos(service_id_t service_id, exfat_cluster_t pfc, unsigned pdi) 417 377 { 418 378 exfat_idx_t *fidx; 419 link_t *l;420 unsigned long pkey[]= {421 [UPH_DH_KEY] = devmap_handle,422 [UPH_PFC_KEY]= pfc,423 [UPH_PDI_KEY]= pdi,379 380 pos_key_t pos_key = { 381 .service_id = service_id, 382 .pfc = pfc, 383 .pdi = pdi, 424 384 }; 425 385 426 386 fibril_mutex_lock(&used_lock); 427 l = hash_table_find(&up_hash, pkey);387 ht_link_t *l = hash_table_find(&up_hash, &pos_key); 428 388 if (l) { 429 fidx = hash_table_get_inst ance(l, exfat_idx_t, uph_link);389 fidx = hash_table_get_inst(l, exfat_idx_t, uph_link); 430 390 } else { 431 391 int rc; 432 392 433 rc = exfat_idx_create(&fidx, devmap_handle);393 rc = exfat_idx_create(&fidx, service_id); 434 394 if (rc != EOK) { 435 395 fibril_mutex_unlock(&used_lock); … … 437 397 } 438 398 439 unsigned long ikey[] = {440 [UIH_DH_KEY] = devmap_handle,441 [UIH_INDEX_KEY] = fidx->index,442 };443 444 399 fidx->pfc = pfc; 445 400 fidx->pdi = pdi; 446 401 447 hash_table_insert(&up_hash, pkey,&fidx->uph_link);448 hash_table_insert(&ui_hash, ikey,&fidx->uih_link);402 hash_table_insert(&up_hash, &fidx->uph_link); 403 hash_table_insert(&ui_hash, &fidx->uih_link); 449 404 } 450 405 fibril_mutex_lock(&fidx->lock); … … 456 411 void exfat_idx_hashin(exfat_idx_t *idx) 457 412 { 458 unsigned long pkey[] = { 459 [UPH_DH_KEY] = idx->devmap_handle, 460 [UPH_PFC_KEY] = idx->pfc, 461 [UPH_PDI_KEY] = idx->pdi, 413 fibril_mutex_lock(&used_lock); 414 hash_table_insert(&up_hash, &idx->uph_link); 415 fibril_mutex_unlock(&used_lock); 416 } 417 418 void exfat_idx_hashout(exfat_idx_t *idx) 419 { 420 fibril_mutex_lock(&used_lock); 421 hash_table_remove_item(&up_hash, &idx->uph_link); 422 fibril_mutex_unlock(&used_lock); 423 } 424 425 exfat_idx_t * 426 exfat_idx_get_by_index(service_id_t service_id, fs_index_t index) 427 { 428 exfat_idx_t *fidx = NULL; 429 430 idx_key_t idx_key = { 431 .service_id = service_id, 432 .index = index, 462 433 }; 463 434 464 435 fibril_mutex_lock(&used_lock); 465 hash_table_insert(&up_hash, pkey, &idx->uph_link); 466 fibril_mutex_unlock(&used_lock); 467 } 468 469 void exfat_idx_hashout(exfat_idx_t *idx) 470 { 471 unsigned long pkey[] = { 472 [UPH_DH_KEY] = idx->devmap_handle, 473 [UPH_PFC_KEY] = idx->pfc, 474 [UPH_PDI_KEY] = idx->pdi, 475 }; 476 477 fibril_mutex_lock(&used_lock); 478 hash_table_remove(&up_hash, pkey, 3); 479 fibril_mutex_unlock(&used_lock); 480 } 481 482 exfat_idx_t * 483 exfat_idx_get_by_index(devmap_handle_t devmap_handle, fs_index_t index) 484 { 485 exfat_idx_t *fidx = NULL; 486 link_t *l; 487 unsigned long ikey[] = { 488 [UIH_DH_KEY] = devmap_handle, 489 [UIH_INDEX_KEY] = index, 490 }; 491 492 fibril_mutex_lock(&used_lock); 493 l = hash_table_find(&ui_hash, ikey); 436 ht_link_t *l = hash_table_find(&ui_hash, &idx_key); 494 437 if (l) { 495 fidx = hash_table_get_inst ance(l, exfat_idx_t, uih_link);438 fidx = hash_table_get_inst(l, exfat_idx_t, uih_link); 496 439 fibril_mutex_lock(&fidx->lock); 497 440 } … … 507 450 void exfat_idx_destroy(exfat_idx_t *idx) 508 451 { 509 unsigned long ikey[]= {510 [UIH_DH_KEY] = idx->devmap_handle,511 [UIH_INDEX_KEY]= idx->index,452 idx_key_t idx_key = { 453 .service_id = idx->service_id, 454 .index = idx->index, 512 455 }; 513 devmap_handle_t devmap_handle = idx->devmap_handle;514 fs_index_t index = idx->index;515 456 516 457 /* TODO: assert(idx->pfc == FAT_CLST_RES0); */ … … 523 464 * the index hash only. 524 465 */ 525 hash_table_remove(&ui_hash, ikey, 2);466 hash_table_remove(&ui_hash, &idx_key); 526 467 fibril_mutex_unlock(&used_lock); 527 468 /* Release the VFS index. */ 528 exfat_index_free( devmap_handle,index);469 exfat_index_free(idx_key.service_id, idx_key.index); 529 470 /* The index structure itself is freed in idx_remove_callback(). */ 530 471 } … … 532 473 int exfat_idx_init(void) 533 474 { 534 if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))475 if (!hash_table_create(&up_hash, 0, 0, &uph_ops)) 535 476 return ENOMEM; 536 if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {477 if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) { 537 478 hash_table_destroy(&up_hash); 538 479 return ENOMEM; … … 544 485 { 545 486 /* We assume the hash tables are empty. */ 487 assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash)); 546 488 hash_table_destroy(&up_hash); 547 489 hash_table_destroy(&ui_hash); 548 490 } 549 491 550 int exfat_idx_init_by_ devmap_handle(devmap_handle_t devmap_handle)492 int exfat_idx_init_by_service_id(service_id_t service_id) 551 493 { 552 494 unused_t *u; … … 556 498 if (!u) 557 499 return ENOMEM; 558 unused_initialize(u, devmap_handle);500 unused_initialize(u, service_id); 559 501 fibril_mutex_lock(&unused_lock); 560 if (!unused_find( devmap_handle, false)) {502 if (!unused_find(service_id, false)) { 561 503 list_append(&u->link, &unused_list); 562 504 } else { … … 568 510 } 569 511 570 void exfat_idx_fini_by_devmap_handle(devmap_handle_t devmap_handle) 571 { 572 unsigned long ikey[] = { 573 [UIH_DH_KEY] = devmap_handle 574 }; 575 unsigned long pkey[] = { 576 [UPH_DH_KEY] = devmap_handle 577 }; 578 512 static bool rm_pos_service_id(ht_link_t *item, void *arg) 513 { 514 service_id_t service_id = *(service_id_t*)arg; 515 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link); 516 517 if (fidx->service_id == service_id) { 518 hash_table_remove_item(&up_hash, item); 519 } 520 521 return true; 522 } 523 524 static bool rm_idx_service_id(ht_link_t *item, void *arg) 525 { 526 service_id_t service_id = *(service_id_t*)arg; 527 exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link); 528 529 if (fidx->service_id == service_id) { 530 hash_table_remove_item(&ui_hash, item); 531 } 532 533 return true; 534 } 535 536 void exfat_idx_fini_by_service_id(service_id_t service_id) 537 { 579 538 /* 580 539 * Remove this instance's index structure from up_hash and ui_hash. … … 583 542 */ 584 543 fibril_mutex_lock(&used_lock); 585 hash_table_ remove(&up_hash, pkey, 1);586 hash_table_ remove(&ui_hash, ikey, 1);544 hash_table_apply(&up_hash, rm_pos_service_id, &service_id); 545 hash_table_apply(&ui_hash, rm_idx_service_id, &service_id); 587 546 fibril_mutex_unlock(&used_lock); 588 547 … … 590 549 * Free the unused and freed structures for this instance. 591 550 */ 592 unused_t *u = unused_find( devmap_handle, true);551 unused_t *u = unused_find(service_id, true); 593 552 assert(u); 594 553 list_remove(&u->link);
Note:
See TracChangeset
for help on using the changeset viewer.