From 3bb463bbf1b4a0167157bf82341abafc8767c974 Mon Sep 17 00:00:00 2001 From: mav Date: Tue, 4 Mar 2008 18:22:18 +0000 Subject: Implement 128 items node name hash for faster name search. Increase node ID hash size from 32 to 128 items. --- sys/netgraph/ng_base.c | 117 +++++++++++++++++++++++++++++-------------------- 1 file changed, 70 insertions(+), 47 deletions(-) (limited to 'sys') 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 -- cgit v1.1