From owner-svn-src-stable-9@FreeBSD.ORG Sat Apr 14 10:13:36 2012 Return-Path: Delivered-To: svn-src-stable-9@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id D23561065672; Sat, 14 Apr 2012 10:13:36 +0000 (UTC) (envelope-from glebius@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id BB6968FC12; Sat, 14 Apr 2012 10:13:36 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id q3EADaSM023925; Sat, 14 Apr 2012 10:13:36 GMT (envelope-from glebius@svn.freebsd.org) Received: (from glebius@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id q3EADaHd023922; Sat, 14 Apr 2012 10:13:36 GMT (envelope-from glebius@svn.freebsd.org) Message-Id: <201204141013.q3EADaHd023922@svn.freebsd.org> From: Gleb Smirnoff Date: Sat, 14 Apr 2012 10:13:36 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-9@freebsd.org X-SVN-Group: stable-9 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r234277 - stable/9/sys/netgraph X-BeenThere: svn-src-stable-9@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for only the 9-stable src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 14 Apr 2012 10:13:36 -0000 Author: glebius Date: Sat Apr 14 10:13:36 2012 New Revision: 234277 URL: http://svn.freebsd.org/changeset/base/234277 Log: Merge 231831: Refactor the name hash and the ID hash, that are used to address nodes: - Make hash sizes growable, to satisfy users running large mpd installations, having thousands of nodes. - NG_NAMEHASH() proved to give a very bad distribution in real life name sets, while generic hash32_str(name, HASHINIT) proved to give an even one, so use the latter for name hash. - Do not store unnamed nodes in slot 0 of name hash, no reason for that. - Use the ID hash in cases when we need to run through all nodes: the NGM_LISTNODES command and in the vnet_netgraph_uninit(). - Implement NGM_LISTNODES and NGM_LISTNAMES as separate code, the former iterates through the ID hash, and the latter through the name hash. - Keep count of all nodes and of named nodes, so that we don't need to count nodes in NGM_LISTNODES and NGM_LISTNAMES. The counters are also used to estimate whether we need to grow hashes. - Close a race between two threads running ng_name_node() assigning same name to different nodes. Modified: stable/9/sys/netgraph/netgraph.h stable/9/sys/netgraph/ng_base.c Directory Properties: stable/9/sys/ (props changed) Modified: stable/9/sys/netgraph/netgraph.h ============================================================================== --- stable/9/sys/netgraph/netgraph.h Sat Apr 14 10:08:07 2012 (r234276) +++ stable/9/sys/netgraph/netgraph.h Sat Apr 14 10:13:36 2012 (r234277) @@ -365,7 +365,7 @@ struct ng_node { void *nd_private; /* node type dependant node ID */ ng_ID_t nd_ID; /* Unique per node */ LIST_HEAD(hooks, ng_hook) nd_hooks; /* linked list of node hooks */ - LIST_ENTRY(ng_node) nd_nodes; /* linked list of all nodes */ + LIST_ENTRY(ng_node) nd_nodes; /* name hash collision list */ LIST_ENTRY(ng_node) nd_idnodes; /* ID hash collision list */ struct ng_queue nd_input_queue; /* input queue for locking */ int nd_refs; /* # of references to this node */ @@ -1202,10 +1202,6 @@ typedef void *meta_p; #define NGI_GET_META(i,m) #define ng_copy_meta(meta) NULL -/* Hash related definitions */ -#define NG_ID_HASH_SIZE 128 /* most systems wont need even this many */ -#define NG_NAME_HASH_SIZE 128 /* most systems wont need even this many */ - /* * Mark the current thread when called from the outbound path of the * network stack, in order to enforce queuing on ng nodes calling into Modified: stable/9/sys/netgraph/ng_base.c ============================================================================== --- stable/9/sys/netgraph/ng_base.c Sat Apr 14 10:08:07 2012 (r234276) +++ stable/9/sys/netgraph/ng_base.c Sat Apr 14 10:13:36 2012 (r234277) @@ -45,6 +45,7 @@ #include #include #include +#include #include #include #include @@ -170,10 +171,20 @@ static struct rwlock ng_typelist_lock; #define TYPELIST_WLOCK() rw_wlock(&ng_typelist_lock) #define TYPELIST_WUNLOCK() rw_wunlock(&ng_typelist_lock) -/* Hash related definitions */ -/* XXX Don't need to initialise them because it's a LIST */ -static VNET_DEFINE(LIST_HEAD(, ng_node), ng_ID_hash[NG_ID_HASH_SIZE]); -#define V_ng_ID_hash VNET(ng_ID_hash) +/* Hash related definitions. */ +LIST_HEAD(nodehash, ng_node); +static VNET_DEFINE(struct nodehash *, ng_ID_hash); +static VNET_DEFINE(u_long, ng_ID_hmask); +static VNET_DEFINE(u_long, ng_nodes); +static VNET_DEFINE(struct nodehash *, ng_name_hash); +static VNET_DEFINE(u_long, ng_name_hmask); +static VNET_DEFINE(u_long, ng_named_nodes); +#define V_ng_ID_hash VNET(ng_ID_hash) +#define V_ng_ID_hmask VNET(ng_ID_hmask) +#define V_ng_nodes VNET(ng_nodes) +#define V_ng_name_hash VNET(ng_name_hash) +#define V_ng_name_hmask VNET(ng_name_hmask) +#define V_ng_named_nodes VNET(ng_named_nodes) static struct rwlock ng_idhash_lock; #define IDHASH_RLOCK() rw_rlock(&ng_idhash_lock) @@ -182,7 +193,7 @@ static struct rwlock ng_idhash_lock; #define IDHASH_WUNLOCK() rw_wunlock(&ng_idhash_lock) /* Method to find a node.. used twice so do it here */ -#define NG_IDHASH_FN(ID) ((ID) % (NG_ID_HASH_SIZE)) +#define NG_IDHASH_FN(ID) ((ID) % (V_ng_ID_hmask + 1)) #define NG_IDHASH_FIND(ID, node) \ do { \ rw_assert(&ng_idhash_lock, RA_LOCKED); \ @@ -195,18 +206,6 @@ static struct rwlock ng_idhash_lock; } \ } while (0) -static VNET_DEFINE(LIST_HEAD(, ng_node), ng_name_hash[NG_NAME_HASH_SIZE]); -#define V_ng_name_hash VNET(ng_name_hash) - -#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) - static struct rwlock ng_namehash_lock; #define NAMEHASH_RLOCK() rw_rlock(&ng_namehash_lock) #define NAMEHASH_RUNLOCK() rw_runlock(&ng_namehash_lock) @@ -227,8 +226,10 @@ static int ng_con_nodes(item_p item, nod node_p node2, const char *name2); static int ng_con_part2(node_p node, item_p item, hook_p hook); static int ng_con_part3(node_p node, item_p item, hook_p hook); -static int ng_mkpeer(node_p node, const char *name, - const char *name2, char *type); +static int ng_mkpeer(node_p node, const char *name, const char *name2, + char *type); +static void ng_name_rehash(void); +static void ng_ID_rehash(void); /* Imported, these used to be externally visible, some may go back. */ void ng_destroy_hook(hook_p hook); @@ -658,12 +659,7 @@ ng_make_node_common(struct ng_type *type /* Initialize hook list for new node */ LIST_INIT(&node->nd_hooks); - /* Link us into the name hash. */ - NAMEHASH_WLOCK(); - LIST_INSERT_HEAD(&V_ng_name_hash[0], node, nd_nodes); - NAMEHASH_WUNLOCK(); - - /* get an ID and put us in the hash chain */ + /* Get an ID and put us in the hash chain. */ IDHASH_WLOCK(); for (;;) { /* wrap protection, even if silly */ node_p node2 = NULL; @@ -675,6 +671,9 @@ ng_make_node_common(struct ng_type *type break; } } + V_ng_nodes++; + if (V_ng_nodes * 2 > V_ng_ID_hmask) + ng_ID_rehash(); LIST_INSERT_HEAD(&V_ng_ID_hash[NG_IDHASH_FN(node->nd_ID)], node, nd_idnodes); IDHASH_WUNLOCK(); @@ -791,10 +790,14 @@ ng_unref_node(node_p node) node->nd_type->refs--; /* XXX maybe should get types lock? */ NAMEHASH_WLOCK(); - LIST_REMOVE(node, nd_nodes); + if (NG_NODE_HAS_NAME(node)) { + V_ng_named_nodes--; + LIST_REMOVE(node, nd_nodes); + } NAMEHASH_WUNLOCK(); IDHASH_WLOCK(); + V_ng_nodes--; LIST_REMOVE(node, nd_idnodes); IDHASH_WUNLOCK(); @@ -810,9 +813,10 @@ static node_p ng_ID2noderef(ng_ID_t ID) { node_p node; + IDHASH_RLOCK(); NG_IDHASH_FIND(ID, node); - if(node) + if (node) NG_NODE_REF(node); IDHASH_RUNLOCK(); return(node); @@ -834,8 +838,9 @@ ng_node2ID(node_p node) int ng_name_node(node_p node, const char *name) { - int i, hash; + uint32_t hash; node_p node2; + int i; /* Check the name is valid */ for (i = 0; i < NG_NODESIZ; i++) { @@ -851,20 +856,26 @@ ng_name_node(node_p node, const char *na return (EINVAL); } - /* Check the name isn't already being used */ - if ((node2 = ng_name2noderef(node, name)) != NULL) { - NG_NODE_UNREF(node2); - TRAP_ERROR(); - return (EADDRINUSE); - } + NAMEHASH_WLOCK(); + if (V_ng_named_nodes * 2 > V_ng_name_hmask) + ng_name_rehash(); - /* copy it */ - strlcpy(NG_NODE_NAME(node), name, NG_NODESIZ); + hash = hash32_str(name, HASHINIT) & V_ng_name_hmask; + /* Check the name isn't already being used. */ + LIST_FOREACH(node2, &V_ng_name_hash[hash], nd_nodes) + if (NG_NODE_IS_VALID(node2) && + (strcmp(NG_NODE_NAME(node2), name) == 0)) { + NAMEHASH_WUNLOCK(); + return (EADDRINUSE); + } + if (NG_NODE_HAS_NAME(node)) + LIST_REMOVE(node, nd_nodes); + else + V_ng_named_nodes++; + /* Copy it. */ + strlcpy(NG_NODE_NAME(node), name, NG_NODESIZ); /* Update name hash. */ - NG_NAMEHASH(name, hash); - NAMEHASH_WLOCK(); - LIST_REMOVE(node, nd_nodes); LIST_INSERT_HEAD(&V_ng_name_hash[hash], node, nd_nodes); NAMEHASH_WUNLOCK(); @@ -899,8 +910,8 @@ ng_name2noderef(node_p here, const char return (ng_ID2noderef(temp)); } - /* Find node by name */ - NG_NAMEHASH(name, hash); + /* Find node by name. */ + hash = hash32_str(name, HASHINIT) & V_ng_name_hmask; NAMEHASH_RLOCK(); LIST_FOREACH(node, &V_ng_name_hash[hash], nd_nodes) if (NG_NODE_IS_VALID(node) && @@ -946,6 +957,68 @@ ng_unname(node_p node) { } +/* + * Allocate a bigger name hash. + */ +static void +ng_name_rehash() +{ + struct nodehash *new; + uint32_t hash; + u_long hmask; + node_p node, node2; + int i; + + new = hashinit_flags((V_ng_name_hmask + 1) * 2, M_NETGRAPH_NODE, &hmask, + HASH_NOWAIT); + if (new == NULL) + return; + + for (i = 0; i <= V_ng_name_hmask; i++) + LIST_FOREACH_SAFE(node, &V_ng_name_hash[i], nd_nodes, node2) { +#ifdef INVARIANTS + LIST_REMOVE(node, nd_nodes); +#endif + hash = hash32_str(NG_NODE_NAME(node), HASHINIT) & hmask; + LIST_INSERT_HEAD(&new[hash], node, nd_nodes); + } + + hashdestroy(V_ng_name_hash, M_NETGRAPH_NODE, V_ng_name_hmask); + V_ng_name_hash = new; + V_ng_name_hmask = hmask; +} + +/* + * Allocate a bigger ID hash. + */ +static void +ng_ID_rehash() +{ + struct nodehash *new; + uint32_t hash; + u_long hmask; + node_p node, node2; + int i; + + new = hashinit_flags((V_ng_ID_hmask + 1) * 2, M_NETGRAPH_NODE, &hmask, + HASH_NOWAIT); + if (new == NULL) + return; + + for (i = 0; i <= V_ng_ID_hmask; i++) + LIST_FOREACH_SAFE(node, &V_ng_ID_hash[i], nd_idnodes, node2) { +#ifdef INVARIANTS + LIST_REMOVE(node, nd_idnodes); +#endif + hash = (node->nd_ID % (hmask + 1)); + LIST_INSERT_HEAD(&new[hash], node, nd_idnodes); + } + + hashdestroy(V_ng_ID_hash, M_NETGRAPH_NODE, V_ng_name_hmask); + V_ng_ID_hash = new; + V_ng_ID_hmask = hmask; +} + /************************************************************************ Hook routines Names are not optional. Hooks are always connected, except for a @@ -2571,28 +2644,55 @@ ng_generic_msg(node_p here, item_p item, break; } - case NGM_LISTNAMES: case NGM_LISTNODES: { - const int unnamed = (msg->header.cmd == NGM_LISTNODES); struct namelist *nl; node_p node; - int num = 0, i; + int i; - NAMEHASH_RLOCK(); - /* Count number of nodes */ - for (i = 0; i < NG_NAME_HASH_SIZE; i++) { - LIST_FOREACH(node, &V_ng_name_hash[i], nd_nodes) { - if (NG_NODE_IS_VALID(node) && - (unnamed || NG_NODE_HAS_NAME(node))) { - num++; - } + IDHASH_RLOCK(); + /* Get response struct. */ + NG_MKRESPONSE(resp, msg, sizeof(*nl) + + (V_ng_nodes * sizeof(struct nodeinfo)), M_NOWAIT | M_ZERO); + if (resp == NULL) { + IDHASH_RUNLOCK(); + error = ENOMEM; + break; + } + nl = (struct namelist *) resp->data; + + /* Cycle through the lists of nodes. */ + nl->numnames = 0; + for (i = 0; i <= V_ng_ID_hmask; i++) { + LIST_FOREACH(node, &V_ng_ID_hash[i], nd_idnodes) { + struct nodeinfo *const np = + &nl->nodeinfo[nl->numnames]; + + if (NG_NODE_NOT_VALID(node)) + continue; + 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; + KASSERT(nl->numnames < V_ng_nodes, + ("%s: no space", __func__)); + nl->numnames++; } } + IDHASH_RUNLOCK(); + break; + } + case NGM_LISTNAMES: + { + struct namelist *nl; + node_p node; + int i; - /* Get response struct */ + NAMEHASH_RLOCK(); + /* Get response struct. */ NG_MKRESPONSE(resp, msg, sizeof(*nl) + - (num * sizeof(struct nodeinfo)), M_NOWAIT); + (V_ng_named_nodes * sizeof(struct nodeinfo)), M_NOWAIT); if (resp == NULL) { NAMEHASH_RUNLOCK(); error = ENOMEM; @@ -2600,24 +2700,21 @@ ng_generic_msg(node_p here, item_p item, } nl = (struct namelist *) resp->data; - /* Cycle through the linked list of nodes */ + /* Cycle through the lists of nodes. */ nl->numnames = 0; - for (i = 0; i < NG_NAME_HASH_SIZE; i++) { + for (i = 0; i <= V_ng_name_hmask; i++) { LIST_FOREACH(node, &V_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 (NG_NODE_HAS_NAME(node)) - strcpy(np->name, NG_NODE_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; - KASSERT(nl->numnames < num, ("%s: no space", - __func__)); + KASSERT(nl->numnames < V_ng_named_nodes, + ("%s: no space", __func__)); nl->numnames++; } } @@ -3024,6 +3121,17 @@ ng_mod_event(module_t mod, int event, vo return (error); } +static void +vnet_netgraph_init(const void *unused __unused) +{ + + /* We start with small hashes, but they can grow. */ + V_ng_ID_hash = hashinit(16, M_NETGRAPH_NODE, &V_ng_ID_hmask); + V_ng_name_hash = hashinit(16, M_NETGRAPH_NODE, &V_ng_name_hmask); +} +VNET_SYSINIT(vnet_netgraph_init, SI_SUB_NETGRAPH, SI_ORDER_FIRST, + vnet_netgraph_init, NULL); + #ifdef VIMAGE static void vnet_netgraph_uninit(const void *unused __unused) @@ -3033,9 +3141,9 @@ vnet_netgraph_uninit(const void *unused do { /* Find a node to kill */ - NAMEHASH_RLOCK(); - for (i = 0; i < NG_NAME_HASH_SIZE; i++) { - LIST_FOREACH(node, &V_ng_name_hash[i], nd_nodes) { + IDHASH_RLOCK(); + for (i = 0; i <= V_ng_ID_hmask; i++) { + LIST_FOREACH(node, &V_ng_ID_hash[i], nd_idnodes) { if (node != &ng_deadnode) { NG_NODE_REF(node); break; @@ -3044,7 +3152,7 @@ vnet_netgraph_uninit(const void *unused if (node != NULL) break; } - NAMEHASH_RUNLOCK(); + IDHASH_RUNLOCK(); /* Attempt to kill it only if it is a regular node */ if (node != NULL) { @@ -3062,6 +3170,9 @@ vnet_netgraph_uninit(const void *unused last_killed = node; } } while (node != NULL); + + hashdestroy(V_ng_name_hash, M_NETGRAPH_NODE, V_ng_name_hmask); + hashdestroy(V_ng_ID_hash, M_NETGRAPH_NODE, V_ng_ID_hmask); } VNET_SYSUNINIT(vnet_netgraph_uninit, SI_SUB_NETGRAPH, SI_ORDER_FIRST, vnet_netgraph_uninit, NULL);