Changeset 0ca7286 in mainline for uspace/app/trace/ipcp.c

Timestamp:

2012-07-21T11:19:27Z (12 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

2732c94

Parents:

1c1da4b

Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

File:

• uspace/app/trace/ipcp.c (modified) (9 diffs)

uspace/app/trace/ipcp.c

@@ -38 +38 @@
 #include <sys/typefmt.h>
 #include <abi/ipc/methods.h>
+#include <macros.h>
 #include "ipc_desc.h"
 #include "proto.h"
@@ -64 +65 @@
 int have_conn[MAX_PHONE];
 
-#define PCALL_TABLE_CHAINS 32
-hash_table_t pending_calls;
+static hash_table_t pending_calls;
 
 /*
@@ -73 +73 @@
 proto_t *proto_unknown;         /**< Protocol with no known methods. */
 
-static hash_index_t pending_call_hash(unsigned long key[]);
-static int pending_call_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void pending_call_remove_callback(link_t *item);
-
-hash_table_operations_t pending_call_ops = {
+static size_t pending_call_key_hash(unsigned long key[]);
+static size_t pending_call_hash(const link_t *item);
+static bool pending_call_match(unsigned long key[], size_t keys,
+    const link_t *item);
+
+static hash_table_ops_t pending_call_ops = {
         .hash = pending_call_hash,
-        .compare = pending_call_compare,
-        .remove_callback = pending_call_remove_callback
+        .key_hash = pending_call_key_hash,
+        .match = pending_call_match,
+        .equal = 0,
+        .remove_callback = 0
 };
 
 
-static hash_index_t pending_call_hash(unsigned long key[])
-{
-//      printf("pending_call_hash\n");
-        return key[0] % PCALL_TABLE_CHAINS;
-}
-
-static int pending_call_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-        pending_call_t *hs;
-
-//      printf("pending_call_compare\n");
-        hs = hash_table_get_instance(item, pending_call_t, link);
-
-        // FIXME: this will fail if sizeof(long) < sizeof(void *).
-        return key[0] == hs->call_hash;
-}
-
-static void pending_call_remove_callback(link_t *item)
-{
-//      printf("pending_call_remove_callback\n");
-}
+static size_t pending_call_key_hash(unsigned long key[])
+{
+        size_t hash = 17;
+        hash = 31 * hash + key[1];
+        hash = 31 * hash + key[0];
+        return hash;
+}
+
+static size_t pending_call_hash(const link_t *item)
+{
+        pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link);
+        unsigned long key[] = {
+                LOWER32(hs->call_hash),
+                UPPER32(hs->call_hash)
+        };
+        return pending_call_key_hash(key);
+}
+
+static bool pending_call_match(unsigned long key[], size_t keys, 
+        const link_t *item)
+{
+        assert(keys == 2);
+        pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link);
+
+        return MERGE_LOUP32(key[0], key[1]) == hs->call_hash;
+}
+
 
 
@@ -177 +184 @@
         }
 
-        hash_table_create(&pending_calls, PCALL_TABLE_CHAINS, 1, &pending_call_ops);
+        hash_table_create(&pending_calls, 0, 2, &pending_call_ops);
 }
 
@@ -190 +197 @@
         pending_call_t *pcall;
         proto_t *proto;
-        unsigned long key[1];
         oper_t *oper;
         sysarg_t *args;
@@ -254 +260 @@
         pcall->oper = oper;
 
-        key[0] = hash;
-
-        hash_table_insert(&pending_calls, key, &pcall->link);
+        hash_table_insert(&pending_calls, &pcall->link);
 }
 
@@ -336 +340 @@
         link_t *item;
         pending_call_t *pcall;
-        unsigned long key[1];
         
         if ((hash & IPC_CALLID_ANSWERED) == 0 && hash != IPCP_CALLID_SYNC) {
@@ -347 +350 @@
         
         hash = hash & ~IPC_CALLID_ANSWERED;
-        key[0] = hash;
+        unsigned long key[] = {
+                LOWER32(hash),
+                UPPER32(hash)
+        };
         
         item = hash_table_find(&pending_calls, key);
@@ -358 +364 @@
         
         pcall = hash_table_get_instance(item, pending_call_t, link);
-        hash_table_remove(&pending_calls, key, 1);
+        hash_table_remove(&pending_calls, key, 2);
         
         parse_answer(hash, pcall, call);