summaryrefslogtreecommitdiffstats
path: root/sys/netgraph
diff options
context:
space:
mode:
authormav <mav@FreeBSD.org>2008-03-04 18:22:18 +0000
committermav <mav@FreeBSD.org>2008-03-04 18:22:18 +0000
commit3bb463bbf1b4a0167157bf82341abafc8767c974 (patch)
tree912bb4e689e8678a46b081ae94393d35e07aef37 /sys/netgraph
parentecb193faa4d2b7a848279cc57e6917a31a49d29e (diff)
downloadFreeBSD-src-3bb463bbf1b4a0167157bf82341abafc8767c974.zip
FreeBSD-src-3bb463bbf1b4a0167157bf82341abafc8767c974.tar.gz
Implement 128 items node name hash for faster name search.
Increase node ID hash size from 32 to 128 items.
Diffstat (limited to 'sys/netgraph')
-rw-r--r--sys/netgraph/ng_base.c117
1 files changed, 70 insertions, 47 deletions
diff --git a/sys/netgraph/ng_base.c b/sys/netgraph/ng_base.c
index 64963c9..45012d2 100644
--- a/sys/netgraph/ng_base.c
+++ b/sys/netgraph/ng_base.c
@@ -70,14 +70,11 @@
MODULE_VERSION(netgraph, NG_ABI_VERSION);
-/* List of all active nodes */
-static LIST_HEAD(, ng_node) ng_nodelist;
-static struct mtx ng_nodelist_mtx;
-
/* Mutex to protect topology events. */
static struct mtx ng_topo_mtx;
#ifdef NETGRAPH_DEBUG
+static struct mtx ng_nodelist_mtx; /* protects global node/hook lists */
static struct mtx ngq_mtx; /* protects the queue item list */
static SLIST_HEAD(, ng_node) ng_allnodes;
@@ -169,7 +166,7 @@ static struct mtx ng_typelist_mtx;
/* Hash related definitions */
/* XXX Don't need to initialise them because it's a LIST */
-#define NG_ID_HASH_SIZE 32 /* most systems wont need even this many */
+#define NG_ID_HASH_SIZE 128 /* most systems wont need even this many */
static LIST_HEAD(, ng_node) ng_ID_hash[NG_ID_HASH_SIZE];
static struct mtx ng_idhash_mtx;
/* Method to find a node.. used twice so do it here */
@@ -186,6 +183,18 @@ static struct mtx ng_idhash_mtx;
} \
} while (0)
+#define NG_NAME_HASH_SIZE 128 /* most systems wont need even this many */
+static LIST_HEAD(, ng_node) ng_name_hash[NG_NAME_HASH_SIZE];
+static struct mtx ng_namehash_mtx;
+#define NG_NAMEHASH(NAME, HASH) \
+ do { \
+ u_char h = 0; \
+ const u_char *c; \
+ for (c = (const u_char*)(NAME); *c; c++)\
+ h += *c; \
+ (HASH) = h % (NG_NAME_HASH_SIZE); \
+ } while (0)
+
/* Internal functions */
static int ng_add_hook(node_p node, const char *name, hook_p * hookp);
@@ -630,11 +639,10 @@ ng_make_node_common(struct ng_type *type, node_p *nodepp)
/* Initialize hook list for new node */
LIST_INIT(&node->nd_hooks);
- /* Link us into the node linked list */
- mtx_lock(&ng_nodelist_mtx);
- LIST_INSERT_HEAD(&ng_nodelist, node, nd_nodes);
- mtx_unlock(&ng_nodelist_mtx);
-
+ /* Link us into the name hash. */
+ mtx_lock(&ng_namehash_mtx);
+ LIST_INSERT_HEAD(&ng_name_hash[0], node, nd_nodes);
+ mtx_unlock(&ng_namehash_mtx);
/* get an ID and put us in the hash chain */
mtx_lock(&ng_idhash_mtx);
@@ -768,10 +776,10 @@ ng_unref_node(node_p node)
if (v == 0) { /* we were the last */
- mtx_lock(&ng_nodelist_mtx);
+ mtx_lock(&ng_namehash_mtx);
node->nd_type->refs--; /* XXX maybe should get types lock? */
LIST_REMOVE(node, nd_nodes);
- mtx_unlock(&ng_nodelist_mtx);
+ mtx_unlock(&ng_namehash_mtx);
mtx_lock(&ng_idhash_mtx);
LIST_REMOVE(node, nd_idnodes);
@@ -814,7 +822,7 @@ ng_node2ID(node_p node)
int
ng_name_node(node_p node, const char *name)
{
- int i;
+ int i, hash;
node_p node2;
/* Check the name is valid */
@@ -841,6 +849,13 @@ ng_name_node(node_p node, const char *name)
/* copy it */
strlcpy(NG_NODE_NAME(node), name, NG_NODESIZ);
+ /* Update name hash. */
+ NG_NAMEHASH(name, hash);
+ mtx_lock(&ng_namehash_mtx);
+ LIST_REMOVE(node, nd_nodes);
+ LIST_INSERT_HEAD(&ng_name_hash[hash], node, nd_nodes);
+ mtx_unlock(&ng_namehash_mtx);
+
return (0);
}
@@ -859,6 +874,7 @@ ng_name2noderef(node_p here, const char *name)
{
node_p node;
ng_ID_t temp;
+ int hash;
/* "." means "this node" */
if (strcmp(name, ".") == 0) {
@@ -872,17 +888,17 @@ ng_name2noderef(node_p here, const char *name)
}
/* Find node by name */
- mtx_lock(&ng_nodelist_mtx);
- LIST_FOREACH(node, &ng_nodelist, nd_nodes) {
- if (NG_NODE_IS_VALID(node)
- && NG_NODE_HAS_NAME(node)
- && (strcmp(NG_NODE_NAME(node), name) == 0)) {
+ NG_NAMEHASH(name, hash);
+ mtx_lock(&ng_namehash_mtx);
+ LIST_FOREACH(node, &ng_name_hash[hash], nd_nodes) {
+ if (NG_NODE_IS_VALID(node) &&
+ (strcmp(NG_NODE_NAME(node), name) == 0)) {
break;
}
}
if (node)
NG_NODE_REF(node);
- mtx_unlock(&ng_nodelist_mtx);
+ mtx_unlock(&ng_namehash_mtx);
return (node);
}
@@ -2702,17 +2718,19 @@ ng_generic_msg(node_p here, item_p item, hook_p lasthook)
const int unnamed = (msg->header.cmd == NGM_LISTNODES);
struct namelist *nl;
node_p node;
- int num = 0;
+ int num = 0, i;
- mtx_lock(&ng_nodelist_mtx);
+ mtx_lock(&ng_namehash_mtx);
/* Count number of nodes */
- LIST_FOREACH(node, &ng_nodelist, nd_nodes) {
- if (NG_NODE_IS_VALID(node)
- && (unnamed || NG_NODE_HAS_NAME(node))) {
- num++;
+ for (i = 0; i < NG_NAME_HASH_SIZE; i++) {
+ LIST_FOREACH(node, &ng_name_hash[i], nd_nodes) {
+ if (NG_NODE_IS_VALID(node) &&
+ (unnamed || NG_NODE_HAS_NAME(node))) {
+ num++;
+ }
}
}
- mtx_unlock(&ng_nodelist_mtx);
+ mtx_unlock(&ng_namehash_mtx);
/* Get response struct */
NG_MKRESPONSE(resp, msg, sizeof(*nl)
@@ -2725,27 +2743,30 @@ ng_generic_msg(node_p here, item_p item, hook_p lasthook)
/* Cycle through the linked list of nodes */
nl->numnames = 0;
- mtx_lock(&ng_nodelist_mtx);
- LIST_FOREACH(node, &ng_nodelist, nd_nodes) {
- struct nodeinfo *const np = &nl->nodeinfo[nl->numnames];
-
- if (NG_NODE_NOT_VALID(node))
- continue;
- if (!unnamed && (! NG_NODE_HAS_NAME(node)))
- continue;
- if (nl->numnames >= num) {
- log(LOG_ERR, "%s: number of %s changed\n",
- __func__, "nodes");
- break;
+ mtx_lock(&ng_namehash_mtx);
+ for (i = 0; i < NG_NAME_HASH_SIZE; i++) {
+ LIST_FOREACH(node, &ng_name_hash[i], nd_nodes) {
+ struct nodeinfo *const np =
+ &nl->nodeinfo[nl->numnames];
+
+ if (NG_NODE_NOT_VALID(node))
+ continue;
+ if (!unnamed && (! NG_NODE_HAS_NAME(node)))
+ continue;
+ if (nl->numnames >= num) {
+ log(LOG_ERR, "%s: number of nodes changed\n",
+ __func__);
+ break;
+ }
+ if (NG_NODE_HAS_NAME(node))
+ strcpy(np->name, NG_NODE_NAME(node));
+ strcpy(np->type, node->nd_type->name);
+ np->id = ng_node2ID(node);
+ np->hooks = node->nd_numhooks;
+ nl->numnames++;
}
- if (NG_NODE_HAS_NAME(node))
- strcpy(np->name, NG_NODE_NAME(node));
- strcpy(np->type, node->nd_type->name);
- np->id = ng_node2ID(node);
- np->hooks = node->nd_numhooks;
- nl->numnames++;
}
- mtx_unlock(&ng_nodelist_mtx);
+ mtx_unlock(&ng_namehash_mtx);
break;
}
@@ -3138,13 +3159,15 @@ ngb_mod_event(module_t mod, int event, void *data)
NG_WORKLIST_LOCK_INIT();
mtx_init(&ng_typelist_mtx, "netgraph types mutex", NULL,
MTX_DEF);
- mtx_init(&ng_nodelist_mtx, "netgraph nodelist mutex", NULL,
- MTX_DEF);
mtx_init(&ng_idhash_mtx, "netgraph idhash mutex", NULL,
MTX_DEF);
+ mtx_init(&ng_namehash_mtx, "netgraph namehash mutex", NULL,
+ MTX_DEF);
mtx_init(&ng_topo_mtx, "netgraph topology mutex", NULL,
MTX_DEF);
#ifdef NETGRAPH_DEBUG
+ mtx_init(&ng_nodelist_mtx, "netgraph nodelist mutex", NULL,
+ MTX_DEF);
mtx_init(&ngq_mtx, "netgraph item list mutex", NULL,
MTX_DEF);
#endif
OpenPOWER on IntegriCloud