From mboxrd@z Thu Jan 1 00:00:00 1970 From: Fabio M. Di Nitto Date: Fri, 19 Mar 2010 16:17:42 +0100 Subject: [Cluster-devel] cluster: STABLE3 - cman: Add improved cluster_id hash function In-Reply-To: <20100319140030.6959712015A@lists.fedorahosted.org> References: <20100319140030.6959712015A@lists.fedorahosted.org> Message-ID: <4BA39596.5070009@redhat.com> List-Id: To: cluster-devel.redhat.com MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Christine, because of the nature of this code (public domain) and specific request NOT to copyright it, can you please move it in its own file and add a proper exception/description in docs/COPYRIGHT? I don't think mixing it with our GPL2+ and copyright is a good idea in the long term. Or alternatively find the the correct way to describe it in docs/COPYRIGHT and LICENCES..... Thanks Fabio On 03/19/2010 03:00 PM, Christine Caulfield wrote: > Gitweb: http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=814faae67c226f6ac9e99438096696479c8aaf2e > Commit: 814faae67c226f6ac9e99438096696479c8aaf2e > Parent: e23761e752f496399c51d74c557f302378eb1427 > Author: Christine Caulfield > AuthorDate: Fri Mar 19 13:57:50 2010 +0000 > Committer: Christine Caulfield > CommitterDate: Fri Mar 19 13:57:50 2010 +0000 > > cman: Add improved cluster_id hash function > > Add a new and vastly improved function for converting the cluster name > into a 16bit ID. This is currently disabled by default but can be enabled > with the stanza > > > > in cluster.conf > > We might make this the default in future .. watch this space. Or some space > closely related to this one that's less intimidating to read on a Friday > afternoon before you've had tea. > > Thanks to Steven Dake for finding and slightly modifying the hash function. > > Signed-off-by: Christine Caulfield > --- > cman/daemon/cman-preconfig.c | 119 ++++++++++++++++++++++++++++++++++++++++-- > 1 files changed, 115 insertions(+), 4 deletions(-) > > diff --git a/cman/daemon/cman-preconfig.c b/cman/daemon/cman-preconfig.c > index f27effa..3339f1d 100644 > --- a/cman/daemon/cman-preconfig.c > +++ b/cman/daemon/cman-preconfig.c > @@ -49,6 +49,7 @@ static char *mcast_name; > static char *cluster_name; > static char error_reason[1024] = { '\0' }; > static hdb_handle_t cluster_parent_handle; > +static int use_hashed_cluster_id = 0; > > /* > * Exports the interface for the service > @@ -283,6 +284,99 @@ static int add_ifaddr(struct objdb_iface_ver0 *objdb, char *mcast, char *ifaddr, > return ret; > } > > + > +/*** > + * > + * Fowler/Noll/Vo hash > + * > + * The basis of this hash algorithm was taken from an idea sent > + * as reviewer comments to the IEEE POSIX P1003.2 committee by: > + * > + * Phong Vo (http://www.research.att.com/info/kpv/) > + * Glenn Fowler (http://www.research.att.com/~gsf/) > + * > + * In a subsequent ballot round: > + * > + * Landon Curt Noll (http://www.isthe.com/chongo/) > + * > + * improved on their algorithm. Some people tried this hash > + * and found that it worked rather well. In an EMail message > + * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. > + * > + * FNV hashes are designed to be fast while maintaining a low > + * collision rate. The FNV speed allows one to quickly hash lots > + * of data while maintaining a reasonable collision rate. See: > + * > + * http://www.isthe.com/chongo/tech/comp/fnv/index.html > + * > + * for more details as well as other forms of the FNV hash. > + *** > + * > + * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the > + * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str(). > + * > + *** > + * > + * Please do not copyright this code. This code is in the public domain. > + * > + * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, > + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO > + * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR > + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF > + * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR > + * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR > + * PERFORMANCE OF THIS SOFTWARE. > + * > + * By: > + * chongo /\oo/\ > + * http://www.isthe.com/chongo/ > + * > + * Share and Enjoy! :-) > + */ > + > +/* > + * Modified to be a little more simple to understand and to provide a 16 bit > + * value rather then 32 bit for cluster id generation > + * > + * sdake at redhat.com > + */ > + > +/* 32 bit magic FNV-1a prime */ > +#define FNV_32_PRIME ((uint32_t)0x01000193) > + > +/* Default initialization for FNV-1a */ > +#define FNV_32_INIT ((uint32_t)0x811c9dc5) > + > +static uint16_t generate_hashed_cluster_id(char *str) > +{ > + unsigned char *s = (unsigned char *)str; > + uint32_t hval = FNV_32_INIT; > + uint32_t ret; > + > + /* > + * FNV-1a hash each octet in the buffer > + */ > + while (*s) { > + /* > + * xor the bottom with the current octet > + */ > + hval ^= (uint32_t)*s++; > + /* > + * multiply by the 32 bit FNV magic prime mod 2^32 > + */ > + hval *= FNV_32_PRIME; > + } > + > + /* > + * Use XOR folding as recommended by authors of algorithm > + * to create a different hash size that is a power of two > + */ > + ret = (hval>> 16) ^ (hval& 0xFFFF); > + > + sprintf(error_reason, "Generated hashed cluster id for '%s' is %d\n", str, ret); > + return (ret); > +} > + > static uint16_t generate_cluster_id(char *name) > { > int i; > @@ -916,8 +1010,12 @@ static int set_noccs_defaults(struct objdb_iface_ver0 *objdb) > return -1; > } > > - if (!cluster_id) > - cluster_id = generate_cluster_id(cluster_name); > + if (!cluster_id) { > + if (use_hashed_cluster_id) > + cluster_id = generate_hashed_cluster_id(cluster_name); > + else > + cluster_id = generate_cluster_id(cluster_name); > + } > > if (!nodename_env) { > int error; > @@ -1084,6 +1182,7 @@ static int get_cman_globals(struct objdb_iface_ver0 *objdb) > { > hdb_handle_t object_handle; > hdb_handle_t find_handle; > + char *use_hash; > > objdb_get_string(objdb, cluster_parent_handle, "name",&cluster_name); > > @@ -1096,11 +1195,21 @@ static int get_cman_globals(struct objdb_iface_ver0 *objdb) > if (!key_filename) > objdb_get_string(objdb, object_handle, "keyfile",&key_filename); > > + objdb_get_string(objdb, object_handle, "hash_cluster_id",&use_hash); > + if (use_hash) { > + if (strncasecmp(use_hash, "yes", 3) == 0 || strncasecmp(use_hash, "on", 2) == 0) > + use_hashed_cluster_id = 1; > + } > + > if (!cluster_id) > objdb_get_int(objdb, object_handle, "cluster_id",&cluster_id, 0); > > - if (!cluster_id) > - cluster_id = generate_cluster_id(cluster_name); > + if (!cluster_id) { > + if (use_hashed_cluster_id) > + cluster_id = generate_hashed_cluster_id(cluster_name); > + else > + cluster_id = generate_cluster_id(cluster_name); > + } > } > objdb->object_find_destroy(find_handle); > return 0; > @@ -1202,6 +1311,8 @@ static void setup_old_compat(struct objdb_iface_ver0 *objdb, hdb_handle_t cluste > hdb_handle_t totem_handle; > hdb_handle_t gfs_handle; > char *value; > + > + use_hashed_cluster_id = 0; > > /* Set groupd to backwards compatibility mode */ > groupd_handle = find_or_create_object(objdb, "group", cluster_handle); > _______________________________________________ > cluster-commits mailing list > cluster-commits at lists.fedorahosted.org > https://fedorahosted.org/mailman/listinfo/cluster-commits