From 5a00790518773385e681e6430a4f85245fae957d Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Wed, 18 Mar 2015 12:25:26 +0100 Subject: ipc: replace reverse hash table with a radix tree Currently, there is a hash table mapping (space, object) tuples to `ipc_entry' objects. This hash table is intertwined with the IPC tables. There is one hash table per IPC space, but it is only for the entries in the IPC table. This hash table is called `local' in the source. All IPC entries being spilled into the splay tree are instead mapped by a global hash table. Replace the local (i.e. per IPC space) reverse hash table with a radix tree. * ipc/ipc_entry.c (ipc_entry_grow_table): Adjust accordingly. * ipc/ipc_entry.h (struct ipc_entry): Adjust comment. * ipc/ipc_hash.c: Adjust comment explaining the local lookup table. (IPC_LOCAL_HASH_INVARIANT): New macro. (ipc_hash_local_lookup): Use the new `ipc_reverse_lookup' function. (ipc_hash_local_insert): Use the new `ipc_reverse_insert' function. (ipc_hash_local_delete): Use the new `ipc_reverse_remove' function. * ipc/ipc_space.c (ipc_space_create): Initialize radix tree. (ipc_space_destroy): Free radix tree. * ipc/ipc_space.h (struct ipc_space): Add radix tree. (ipc_reverse_insert): New function. (ipc_reverse_remove): Likewise. (ipc_reverse_remove_all): Likewise. (ipc_reverse_lookup): Likewise. * ipc/ipc_right.c (ipc_right_clean): Update comment. --- ipc/ipc_entry.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'ipc/ipc_entry.c') diff --git a/ipc/ipc_entry.c b/ipc/ipc_entry.c index e78f74e..5b9fd98 100644 --- a/ipc/ipc_entry.c +++ b/ipc/ipc_entry.c @@ -618,6 +618,7 @@ ipc_entry_grow_table(ipc_space_t space) is_write_unlock(space); thread_wakeup((event_t) space); it_entries_free(its, table); + ipc_reverse_remove_all(space); is_write_lock(space); return KERN_SUCCESS; } @@ -641,9 +642,6 @@ ipc_entry_grow_table(ipc_space_t space) memcpy(table, otable, osize * sizeof(struct ipc_entry)); - for (i = 0; i < osize; i++) - table[i].ie_index = 0; - (void) memset((void *) (table + osize), 0, (size - osize) * sizeof(struct ipc_entry)); @@ -651,6 +649,7 @@ ipc_entry_grow_table(ipc_space_t space) * Put old entries into the reverse hash table. */ + ipc_reverse_remove_all(space); for (i = 0; i < osize; i++) { ipc_entry_t entry = &table[i]; -- cgit v1.2.3