[Cluster-devel] cluster: STABLE3 - cman: Add improved cluster_id hash function

[Fabio M. Di Nitto <fdinitto@redhat.com>]

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<ccaulfie@redhat.com>
> AuthorDate:    Fri Mar 19 13:57:50 2010 +0000
> Committer:     Christine Caulfield<ccaulfie@redhat.com>
> 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
>
> <cman hash_cluster_id="yes"/>
>
> 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<ccaulfie@redhat.com>
> ---
>   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<Landon Curt Noll>  /\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