[Cluster-devel] cluster: STABLE3 - cman: Add improved cluster_id hash function
Fabio M. Di Nitto
fdinitto at redhat.com
Fri Mar 19 15:17:42 UTC 2010
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 at redhat.com>
> AuthorDate: Fri Mar 19 13:57:50 2010 +0000
> Committer: Christine Caulfield<ccaulfie at 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 at 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
More information about the Cluster-devel
mailing list