source: mainline/uspace/srv/fs/locfs/locfs_ops.c

Last change on this file was 0db0df2, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 4 months ago

Hash table improvements

Implement hash_table_foreach macro, analogous to list_foreach.

Remove superfluous argument to hash_table_find_next().
(If the user needs to recheck the part of the list already
checked by hash_table_find(), they can just rerun that function.)

Add hash argument to hash_table_ops_t::key_equal.
The big change here is that users with big keys can store the hash
value alongside key in their entries, and for the low low cost of
sizeof(size_t) bytes eliminate a bunch of expensive key comparisons.

Also added a hash function for strings and arbitrary data.
Found this one by asking ChatGPT, because the latency of accesses
to my book collection is currently a couple of hours.

+ Some drive-by unused #include removal.
  • Property mode set to 100644
File size: 17.1 KB
Line 
1/*
2 * Copyright (c) 2009 Martin Decky
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 locfs
30 * @{
31 */
32
33/**
34 * @file locfs_ops.c
35 * @brief Implementation of VFS operations for the locfs file system server.
36 */
37
38#include <macros.h>
39#include <stdbool.h>
40#include <errno.h>
41#include <stdlib.h>
42#include <str.h>
43#include <libfs.h>
44#include <fibril_synch.h>
45#include <adt/hash_table.h>
46#include <ipc/loc.h>
47#include <assert.h>
48#include "locfs.h"
49#include "locfs_ops.h"
50
51typedef struct {
52 loc_object_type_t type;
53 service_id_t service_id;
54} locfs_node_t;
55
56/** Opened services structure */
57typedef struct {
58 service_id_t service_id;
59 async_sess_t *sess; /**< If NULL, the structure is incomplete. */
60 size_t refcount;
61 ht_link_t link;
62 fibril_condvar_t cv; /**< Broadcast when completed. */
63} service_t;
64
65/** Hash table of opened services */
66static hash_table_t services;
67
68/** Hash table mutex */
69static FIBRIL_MUTEX_INITIALIZE(services_mutex);
70
71/* Implementation of hash table interface for the nodes hash table. */
72
73static size_t services_key_hash(const void *key)
74{
75 const service_id_t *k = key;
76 return *k;
77}
78
79static size_t services_hash(const ht_link_t *item)
80{
81 service_t *dev = hash_table_get_inst(item, service_t, link);
82 return dev->service_id;
83}
84
85static bool services_key_equal(const void *key, size_t hash,
86 const ht_link_t *item)
87{
88 const service_id_t *k = key;
89 service_t *dev = hash_table_get_inst(item, service_t, link);
90 return (dev->service_id == *k);
91}
92
93static void services_remove_callback(ht_link_t *item)
94{
95 free(hash_table_get_inst(item, service_t, link));
96}
97
98static const hash_table_ops_t services_ops = {
99 .hash = services_hash,
100 .key_hash = services_key_hash,
101 .key_equal = services_key_equal,
102 .equal = NULL,
103 .remove_callback = services_remove_callback
104};
105
106static errno_t locfs_node_get_internal(fs_node_t **rfn, loc_object_type_t type,
107 service_id_t service_id)
108{
109 locfs_node_t *node = (locfs_node_t *) malloc(sizeof(locfs_node_t));
110 if (node == NULL) {
111 *rfn = NULL;
112 return ENOMEM;
113 }
114
115 *rfn = (fs_node_t *) malloc(sizeof(fs_node_t));
116 if (*rfn == NULL) {
117 free(node);
118 *rfn = NULL;
119 return ENOMEM;
120 }
121
122 fs_node_initialize(*rfn);
123 node->type = type;
124 node->service_id = service_id;
125
126 (*rfn)->data = node;
127 return EOK;
128}
129
130static errno_t locfs_root_get(fs_node_t **rfn, service_id_t service_id)
131{
132 return locfs_node_get_internal(rfn, LOC_OBJECT_NONE, 0);
133}
134
135static errno_t locfs_match(fs_node_t **rfn, fs_node_t *pfn, const char *component)
136{
137 locfs_node_t *node = (locfs_node_t *) pfn->data;
138 errno_t ret;
139
140 if (node->service_id == 0) {
141 /* Root directory */
142
143 loc_sdesc_t *nspaces;
144 size_t count = loc_get_namespaces(&nspaces);
145
146 if (count > 0) {
147 size_t pos;
148 for (pos = 0; pos < count; pos++) {
149 /* Ignore root namespace */
150 if (str_cmp(nspaces[pos].name, "") == 0)
151 continue;
152
153 if (str_cmp(nspaces[pos].name, component) == 0) {
154 ret = locfs_node_get_internal(rfn, LOC_OBJECT_NAMESPACE, nspaces[pos].id);
155 free(nspaces);
156 return ret;
157 }
158 }
159
160 free(nspaces);
161 }
162
163 /* Search root namespace */
164 service_id_t namespace;
165 loc_sdesc_t *svcs;
166 if (loc_namespace_get_id("", &namespace, 0) == EOK) {
167 count = loc_get_services(namespace, &svcs);
168
169 if (count > 0) {
170 size_t pos;
171 for (pos = 0; pos < count; pos++) {
172 if (str_cmp(svcs[pos].name, component) == 0) {
173 ret = locfs_node_get_internal(rfn, LOC_OBJECT_SERVICE, svcs[pos].id);
174 free(svcs);
175 return ret;
176 }
177 }
178
179 free(svcs);
180 }
181 }
182
183 *rfn = NULL;
184 return EOK;
185 }
186
187 if (node->type == LOC_OBJECT_NAMESPACE) {
188 /* Namespace directory */
189
190 loc_sdesc_t *svcs;
191 size_t count = loc_get_services(node->service_id, &svcs);
192 if (count > 0) {
193 size_t pos;
194 for (pos = 0; pos < count; pos++) {
195 if (str_cmp(svcs[pos].name, component) == 0) {
196 ret = locfs_node_get_internal(rfn, LOC_OBJECT_SERVICE, svcs[pos].id);
197 free(svcs);
198 return ret;
199 }
200 }
201
202 free(svcs);
203 }
204
205 *rfn = NULL;
206 return EOK;
207 }
208
209 *rfn = NULL;
210 return EOK;
211}
212
213static errno_t locfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index)
214{
215 return locfs_node_get_internal(rfn, loc_id_probe(index), index);
216}
217
218static errno_t locfs_node_open(fs_node_t *fn)
219{
220 locfs_node_t *node = (locfs_node_t *) fn->data;
221
222 if (node->service_id == 0) {
223 /* Root directory */
224 return EOK;
225 }
226
227 loc_object_type_t type = loc_id_probe(node->service_id);
228
229 if (type == LOC_OBJECT_NAMESPACE) {
230 /* Namespace directory */
231 return EOK;
232 }
233
234 if (type == LOC_OBJECT_SERVICE) {
235 /* Device node */
236
237 fibril_mutex_lock(&services_mutex);
238 ht_link_t *lnk;
239 restart:
240 lnk = hash_table_find(&services, &node->service_id);
241 if (lnk == NULL) {
242 service_t *dev = (service_t *) malloc(sizeof(service_t));
243 if (dev == NULL) {
244 fibril_mutex_unlock(&services_mutex);
245 return ENOMEM;
246 }
247
248 dev->service_id = node->service_id;
249
250 /* Mark as incomplete */
251 dev->sess = NULL;
252 dev->refcount = 1;
253 fibril_condvar_initialize(&dev->cv);
254
255 /*
256 * Insert the incomplete device structure so that other
257 * fibrils will not race with us when we drop the mutex
258 * below.
259 */
260 hash_table_insert(&services, &dev->link);
261
262 /*
263 * Drop the mutex to allow recursive locfs requests.
264 */
265 fibril_mutex_unlock(&services_mutex);
266
267 async_sess_t *sess = loc_service_connect(node->service_id,
268 INTERFACE_FS, 0);
269
270 fibril_mutex_lock(&services_mutex);
271
272 /*
273 * Notify possible waiters about this device structure
274 * being completed (or destroyed).
275 */
276 fibril_condvar_broadcast(&dev->cv);
277
278 if (!sess) {
279 /*
280 * Connecting failed, need to remove the
281 * entry and free the device structure.
282 */
283 hash_table_remove(&services, &node->service_id);
284 fibril_mutex_unlock(&services_mutex);
285
286 return ENOENT;
287 }
288
289 /* Set the correct session. */
290 dev->sess = sess;
291 } else {
292 service_t *dev = hash_table_get_inst(lnk, service_t, link);
293
294 if (!dev->sess) {
295 /*
296 * Wait until the device structure is completed
297 * and start from the beginning as the device
298 * structure might have entirely disappeared
299 * while we were not holding the mutex in
300 * fibril_condvar_wait().
301 */
302 fibril_condvar_wait(&dev->cv, &services_mutex);
303 goto restart;
304 }
305
306 dev->refcount++;
307 }
308
309 fibril_mutex_unlock(&services_mutex);
310
311 return EOK;
312 }
313
314 return ENOENT;
315}
316
317static errno_t locfs_node_put(fs_node_t *fn)
318{
319 free(fn->data);
320 free(fn);
321 return EOK;
322}
323
324static errno_t locfs_create_node(fs_node_t **rfn, service_id_t service_id, int lflag)
325{
326 assert((lflag & L_FILE) ^ (lflag & L_DIRECTORY));
327
328 *rfn = NULL;
329 return ENOTSUP;
330}
331
332static errno_t locfs_destroy_node(fs_node_t *fn)
333{
334 return ENOTSUP;
335}
336
337static errno_t locfs_link_node(fs_node_t *pfn, fs_node_t *cfn, const char *nm)
338{
339 return ENOTSUP;
340}
341
342static errno_t locfs_unlink_node(fs_node_t *pfn, fs_node_t *cfn, const char *nm)
343{
344 return ENOTSUP;
345}
346
347static errno_t locfs_has_children(bool *has_children, fs_node_t *fn)
348{
349 locfs_node_t *node = (locfs_node_t *) fn->data;
350
351 if (node->service_id == 0) {
352 size_t count = loc_count_namespaces();
353 if (count > 0) {
354 *has_children = true;
355 return EOK;
356 }
357
358 /* Root namespace */
359 service_id_t namespace;
360 if (loc_namespace_get_id("", &namespace, 0) == EOK) {
361 count = loc_count_services(namespace);
362 if (count > 0) {
363 *has_children = true;
364 return EOK;
365 }
366 }
367
368 *has_children = false;
369 return EOK;
370 }
371
372 if (node->type == LOC_OBJECT_NAMESPACE) {
373 size_t count = loc_count_services(node->service_id);
374 if (count > 0) {
375 *has_children = true;
376 return EOK;
377 }
378
379 *has_children = false;
380 return EOK;
381 }
382
383 *has_children = false;
384 return EOK;
385}
386
387static fs_index_t locfs_index_get(fs_node_t *fn)
388{
389 locfs_node_t *node = (locfs_node_t *) fn->data;
390 return node->service_id;
391}
392
393static aoff64_t locfs_size_get(fs_node_t *fn)
394{
395 return 0;
396}
397
398static unsigned int locfs_lnkcnt_get(fs_node_t *fn)
399{
400 locfs_node_t *node = (locfs_node_t *) fn->data;
401
402 if (node->service_id == 0)
403 return 0;
404
405 return 1;
406}
407
408static bool locfs_is_directory(fs_node_t *fn)
409{
410 locfs_node_t *node = (locfs_node_t *) fn->data;
411
412 return ((node->type == LOC_OBJECT_NONE) || (node->type == LOC_OBJECT_NAMESPACE));
413}
414
415static bool locfs_is_file(fs_node_t *fn)
416{
417 locfs_node_t *node = (locfs_node_t *) fn->data;
418
419 return (node->type == LOC_OBJECT_SERVICE);
420}
421
422static service_id_t locfs_service_get(fs_node_t *fn)
423{
424 locfs_node_t *node = (locfs_node_t *) fn->data;
425
426 if (node->type == LOC_OBJECT_SERVICE)
427 return node->service_id;
428
429 return 0;
430}
431
432/** libfs operations */
433libfs_ops_t locfs_libfs_ops = {
434 .root_get = locfs_root_get,
435 .match = locfs_match,
436 .node_get = locfs_node_get,
437 .node_open = locfs_node_open,
438 .node_put = locfs_node_put,
439 .create = locfs_create_node,
440 .destroy = locfs_destroy_node,
441 .link = locfs_link_node,
442 .unlink = locfs_unlink_node,
443 .has_children = locfs_has_children,
444 .index_get = locfs_index_get,
445 .size_get = locfs_size_get,
446 .lnkcnt_get = locfs_lnkcnt_get,
447 .is_directory = locfs_is_directory,
448 .is_file = locfs_is_file,
449 .service_get = locfs_service_get
450};
451
452bool locfs_init(void)
453{
454 if (!hash_table_create(&services, 0, 0, &services_ops))
455 return false;
456
457 return true;
458}
459
460static errno_t locfs_fsprobe(service_id_t service_id, vfs_fs_probe_info_t *info)
461{
462 return ENOTSUP;
463}
464
465static errno_t locfs_mounted(service_id_t service_id, const char *opts,
466 fs_index_t *index, aoff64_t *size)
467{
468 *index = 0;
469 *size = 0;
470 return EOK;
471}
472
473static errno_t locfs_unmounted(service_id_t service_id)
474{
475 return ENOTSUP;
476}
477
478static errno_t
479locfs_read(service_id_t service_id, fs_index_t index, aoff64_t pos,
480 size_t *rbytes)
481{
482 if (index == 0) {
483 ipc_call_t call;
484 size_t size;
485 if (!async_data_read_receive(&call, &size)) {
486 async_answer_0(&call, EINVAL);
487 return EINVAL;
488 }
489
490 loc_sdesc_t *desc;
491 size_t count = loc_get_namespaces(&desc);
492
493 /* Get rid of root namespace */
494 size_t i;
495 for (i = 0; i < count; i++) {
496 if (str_cmp(desc[i].name, "") == 0) {
497 if (pos >= i)
498 pos++;
499
500 break;
501 }
502 }
503
504 if (pos < count) {
505 async_data_read_finalize(&call, desc[pos].name, str_size(desc[pos].name) + 1);
506 free(desc);
507 *rbytes = 1;
508 return EOK;
509 }
510
511 free(desc);
512 pos -= count;
513
514 /* Search root namespace */
515 service_id_t namespace;
516 if (loc_namespace_get_id("", &namespace, 0) == EOK) {
517 count = loc_get_services(namespace, &desc);
518
519 if (pos < count) {
520 async_data_read_finalize(&call, desc[pos].name, str_size(desc[pos].name) + 1);
521 free(desc);
522 *rbytes = 1;
523 return EOK;
524 }
525
526 free(desc);
527 }
528
529 async_answer_0(&call, ENOENT);
530 return ENOENT;
531 }
532
533 loc_object_type_t type = loc_id_probe(index);
534
535 if (type == LOC_OBJECT_NAMESPACE) {
536 /* Namespace directory */
537 ipc_call_t call;
538 size_t size;
539 if (!async_data_read_receive(&call, &size)) {
540 async_answer_0(&call, EINVAL);
541 return EINVAL;
542 }
543
544 loc_sdesc_t *desc;
545 size_t count = loc_get_services(index, &desc);
546
547 if (pos < count) {
548 async_data_read_finalize(&call, desc[pos].name, str_size(desc[pos].name) + 1);
549 free(desc);
550 *rbytes = 1;
551 return EOK;
552 }
553
554 free(desc);
555 async_answer_0(&call, ENOENT);
556 return ENOENT;
557 }
558
559 if (type == LOC_OBJECT_SERVICE) {
560 /* Device node */
561
562 fibril_mutex_lock(&services_mutex);
563 service_id_t service_index = index;
564 ht_link_t *lnk = hash_table_find(&services, &service_index);
565 if (lnk == NULL) {
566 fibril_mutex_unlock(&services_mutex);
567 return ENOENT;
568 }
569
570 service_t *dev = hash_table_get_inst(lnk, service_t, link);
571 assert(dev->sess);
572
573 ipc_call_t call;
574 if (!async_data_read_receive(&call, NULL)) {
575 fibril_mutex_unlock(&services_mutex);
576 async_answer_0(&call, EINVAL);
577 return EINVAL;
578 }
579
580 /* Make a request at the driver */
581 async_exch_t *exch = async_exchange_begin(dev->sess);
582
583 ipc_call_t answer;
584 aid_t msg = async_send_4(exch, VFS_OUT_READ, service_id,
585 index, LOWER32(pos), UPPER32(pos), &answer);
586
587 /* Forward the IPC_M_DATA_READ request to the driver */
588 async_forward_0(&call, exch, 0, IPC_FF_ROUTE_FROM_ME);
589
590 async_exchange_end(exch);
591
592 fibril_mutex_unlock(&services_mutex);
593
594 /* Wait for reply from the driver. */
595 errno_t rc;
596 async_wait_for(msg, &rc);
597
598 /* Do not propagate EHANGUP back to VFS. */
599 if ((errno_t) rc == EHANGUP)
600 rc = ENOTSUP;
601
602 *rbytes = ipc_get_arg1(&answer);
603 return rc;
604 }
605
606 return ENOENT;
607}
608
609static errno_t
610locfs_write(service_id_t service_id, fs_index_t index, aoff64_t pos,
611 size_t *wbytes, aoff64_t *nsize)
612{
613 if (index == 0)
614 return ENOTSUP;
615
616 loc_object_type_t type = loc_id_probe(index);
617
618 if (type == LOC_OBJECT_NAMESPACE) {
619 /* Namespace directory */
620 return ENOTSUP;
621 }
622
623 if (type == LOC_OBJECT_SERVICE) {
624 /* Device node */
625
626 fibril_mutex_lock(&services_mutex);
627 service_id_t service_index = index;
628 ht_link_t *lnk = hash_table_find(&services, &service_index);
629 if (lnk == NULL) {
630 fibril_mutex_unlock(&services_mutex);
631 return ENOENT;
632 }
633
634 service_t *dev = hash_table_get_inst(lnk, service_t, link);
635 assert(dev->sess);
636
637 ipc_call_t call;
638 if (!async_data_write_receive(&call, NULL)) {
639 fibril_mutex_unlock(&services_mutex);
640 async_answer_0(&call, EINVAL);
641 return EINVAL;
642 }
643
644 /* Make a request at the driver */
645 async_exch_t *exch = async_exchange_begin(dev->sess);
646
647 ipc_call_t answer;
648 aid_t msg = async_send_4(exch, VFS_OUT_WRITE, service_id,
649 index, LOWER32(pos), UPPER32(pos), &answer);
650
651 /* Forward the IPC_M_DATA_WRITE request to the driver */
652 async_forward_0(&call, exch, 0, IPC_FF_ROUTE_FROM_ME);
653
654 async_exchange_end(exch);
655
656 fibril_mutex_unlock(&services_mutex);
657
658 /* Wait for reply from the driver. */
659 errno_t rc;
660 async_wait_for(msg, &rc);
661
662 /* Do not propagate EHANGUP back to VFS. */
663 if ((errno_t) rc == EHANGUP)
664 rc = ENOTSUP;
665
666 *wbytes = ipc_get_arg1(&answer);
667 *nsize = 0;
668 return rc;
669 }
670
671 return ENOENT;
672}
673
674static errno_t
675locfs_truncate(service_id_t service_id, fs_index_t index, aoff64_t size)
676{
677 return ENOTSUP;
678}
679
680static errno_t locfs_close(service_id_t service_id, fs_index_t index)
681{
682 if (index == 0)
683 return EOK;
684
685 loc_object_type_t type = loc_id_probe(index);
686
687 if (type == LOC_OBJECT_NAMESPACE) {
688 /* Namespace directory */
689 return EOK;
690 }
691
692 if (type == LOC_OBJECT_SERVICE) {
693
694 fibril_mutex_lock(&services_mutex);
695 service_id_t service_index = index;
696 ht_link_t *lnk = hash_table_find(&services, &service_index);
697 if (lnk == NULL) {
698 fibril_mutex_unlock(&services_mutex);
699 return ENOENT;
700 }
701
702 service_t *dev = hash_table_get_inst(lnk, service_t, link);
703 assert(dev->sess);
704 dev->refcount--;
705
706 if (dev->refcount == 0) {
707 async_hangup(dev->sess);
708 service_id_t service_index = index;
709 hash_table_remove(&services, &service_index);
710 }
711
712 fibril_mutex_unlock(&services_mutex);
713
714 return EOK;
715 }
716
717 return ENOENT;
718}
719
720static errno_t locfs_sync(service_id_t service_id, fs_index_t index)
721{
722 if (index == 0)
723 return EOK;
724
725 loc_object_type_t type = loc_id_probe(index);
726
727 if (type == LOC_OBJECT_NAMESPACE) {
728 /* Namespace directory */
729 return EOK;
730 }
731
732 if (type == LOC_OBJECT_SERVICE) {
733
734 fibril_mutex_lock(&services_mutex);
735 service_id_t service_index = index;
736 ht_link_t *lnk = hash_table_find(&services, &service_index);
737 if (lnk == NULL) {
738 fibril_mutex_unlock(&services_mutex);
739 return ENOENT;
740 }
741
742 service_t *dev = hash_table_get_inst(lnk, service_t, link);
743 assert(dev->sess);
744
745 /* Make a request at the driver */
746 async_exch_t *exch = async_exchange_begin(dev->sess);
747
748 ipc_call_t answer;
749 aid_t msg = async_send_2(exch, VFS_OUT_SYNC, service_id,
750 index, &answer);
751
752 async_exchange_end(exch);
753
754 fibril_mutex_unlock(&services_mutex);
755
756 /* Wait for reply from the driver */
757 errno_t rc;
758 async_wait_for(msg, &rc);
759
760 return rc;
761 }
762
763 return ENOENT;
764}
765
766static errno_t locfs_destroy(service_id_t service_id, fs_index_t index)
767{
768 return ENOTSUP;
769}
770
771vfs_out_ops_t locfs_ops = {
772 .fsprobe = locfs_fsprobe,
773 .mounted = locfs_mounted,
774 .unmounted = locfs_unmounted,
775 .read = locfs_read,
776 .write = locfs_write,
777 .truncate = locfs_truncate,
778 .close = locfs_close,
779 .destroy = locfs_destroy,
780 .sync = locfs_sync,
781};
782
783/**
784 * @}
785 */
Note: See TracBrowser for help on using the repository browser.