1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 only,
10 * as published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License version 2 for more details (a copy is included
16 * in the LICENSE file that accompanied this code).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see
20 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
29 * Copyright 2008 Sun Microsystems, Inc. All rights reserved
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
36 * lustre/obdclass/class_hash.c
38 * Implement a hash class for hash process in lustre system.
40 * Author: YuZhangyong <yzy@clusterfs.com>
44 #include <liblustre.h>
48 #include <obd_class.h>
49 #include <class_hash.h>
50 #include <lustre_export.h>
51 #include <obd_support.h>
52 #include <lustre_net.h>
54 int lustre_hash_init(struct lustre_class_hash_body **hash_body_new,
55 char *hashname, __u32 hashsize,
56 struct lustre_hash_operations *hash_operations)
59 struct lustre_class_hash_body *hash_body = NULL;
61 LASSERT(hashsize > 0);
62 LASSERT(hash_operations != NULL);
72 LASSERTF(n == 1, "hashsize %u isn't 2^n\n", hashsize);
74 /* alloc space for hash_body */
75 OBD_ALLOC(hash_body, sizeof(*hash_body));
77 if (hash_body == NULL) {
78 CERROR("Cannot alloc space for hash body, hashname = %s \n",
83 LASSERT(hashname != NULL &&
84 strlen(hashname) <= sizeof(hash_body->hashname));
85 strcpy(hash_body->hashname, hashname);
86 hash_body->lchb_hash_max_size = hashsize;
87 hash_body->lchb_hash_operations = hash_operations;
89 /* alloc space for the hash tables */
90 OBD_ALLOC(hash_body->lchb_hash_tables,
91 sizeof(*hash_body->lchb_hash_tables) * hash_body->lchb_hash_max_size);
93 if (hash_body->lchb_hash_tables == NULL) {
94 OBD_FREE(hash_body, sizeof(*hash_body));
95 CERROR("Cannot alloc space for hashtables, hashname = %s \n",
100 spin_lock_init(&hash_body->lchb_lock); /* initialize the body lock */
102 for(i = 0 ; i < hash_body->lchb_hash_max_size; i++) {
103 /* initial the bucket lock and list_head */
104 INIT_HLIST_HEAD(&hash_body->lchb_hash_tables[i].lhb_head);
105 spin_lock_init(&hash_body->lchb_hash_tables[i].lhb_lock);
107 *hash_body_new = hash_body;
111 EXPORT_SYMBOL(lustre_hash_init);
113 void lustre_hash_exit(struct lustre_class_hash_body **new_hash_body)
116 struct lustre_class_hash_body *hash_body = NULL;
119 hash_body = *new_hash_body;
121 if (hash_body == NULL) {
122 CWARN("hash body has been deleted\n");
126 spin_lock(&hash_body->lchb_lock); /* lock the hash tables */
128 if (hash_body->lchb_hash_tables == NULL ) {
129 spin_unlock(&hash_body->lchb_lock);
130 CWARN("hash tables has been deleted\n");
134 for( i = 0; i < hash_body->lchb_hash_max_size; i++ ) {
135 struct lustre_hash_bucket * bucket;
136 struct hlist_node * actual_hnode, *pos;
138 bucket = &hash_body->lchb_hash_tables[i];
139 spin_lock(&bucket->lhb_lock); /* lock the bucket */
140 hlist_for_each_safe(actual_hnode, pos, &(bucket->lhb_head)) {
141 lustre_hash_delitem_nolock(hash_body, i, actual_hnode);
143 spin_unlock(&bucket->lhb_lock);
146 /* free the hash_tables's memory space */
147 OBD_FREE(hash_body->lchb_hash_tables,
148 sizeof(*hash_body->lchb_hash_tables) * hash_body->lchb_hash_max_size);
150 hash_body->lchb_hash_tables = NULL;
152 spin_unlock(&hash_body->lchb_lock);
155 /* free the hash_body's memory space */
156 if (hash_body != NULL) {
157 OBD_FREE(hash_body, sizeof(*hash_body));
158 *new_hash_body = NULL;
162 EXPORT_SYMBOL(lustre_hash_exit);
165 * only allow unique @key in hashtables, if the same @key has existed
166 * in hashtables, it will return with fails.
168 int lustre_hash_additem_unique(struct lustre_class_hash_body *hash_body,
169 void *key, struct hlist_node *actual_hnode)
172 struct lustre_hash_bucket *bucket = NULL;
173 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
176 LASSERT(hlist_unhashed(actual_hnode));
177 hashent = hop->lustre_hashfn(hash_body, key);
179 /* get the hash-bucket and lock it */
180 bucket = &hash_body->lchb_hash_tables[hashent];
181 spin_lock(&bucket->lhb_lock);
183 if ( (lustre_hash_getitem_in_bucket_nolock(hash_body, hashent, key)) != NULL) {
184 /* the added-item exist in hashtables, so cannot add it again */
185 spin_unlock(&bucket->lhb_lock);
187 CWARN("Already found the key in hash [%s]\n",
188 hash_body->hashname);
192 hlist_add_head(actual_hnode, &(bucket->lhb_head));
194 #ifdef LUSTRE_HASH_DEBUG
195 /* hash distribute debug */
196 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
197 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
198 hash_body->hashname, hashent,
199 hash_body->lchb_hash_tables[hashent].lhb_item_count);
201 hop->lustre_hash_object_refcount_get(actual_hnode);
203 spin_unlock(&bucket->lhb_lock);
207 EXPORT_SYMBOL(lustre_hash_additem_unique);
210 * only allow unique @key in hashtables, if the same @key has existed
211 * in hashtables, it will return with fails.
213 void* lustre_hash_findadd_unique(struct lustre_class_hash_body *hash_body,
214 void *key, struct hlist_node *actual_hnode)
217 struct lustre_hash_bucket *bucket = NULL;
218 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
219 struct hlist_node * hash_item_hnode = NULL;
223 LASSERT(hlist_unhashed(actual_hnode));
224 hashent = hop->lustre_hashfn(hash_body, key);
226 /* get the hash-bucket and lock it */
227 bucket = &hash_body->lchb_hash_tables[hashent];
228 spin_lock(&bucket->lhb_lock);
230 hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
232 if ( hash_item_hnode != NULL) {
233 /* the added-item exist in hashtables, so cannot add it again */
234 obj = hop->lustre_hash_object_refcount_get(hash_item_hnode);
235 spin_unlock(&bucket->lhb_lock);
239 hlist_add_head(actual_hnode, &(bucket->lhb_head));
241 #ifdef LUSTRE_HASH_DEBUG
242 /* hash distribute debug */
243 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
244 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
245 hash_body->hashname, hashent,
246 hash_body->lchb_hash_tables[hashent].lhb_item_count);
248 obj = hop->lustre_hash_object_refcount_get(actual_hnode);
250 spin_unlock(&bucket->lhb_lock);
254 EXPORT_SYMBOL(lustre_hash_findadd_unique);
257 * this version of additem, it allow multi same @key <key, value> in hashtables.
258 * in this additem version, we don't need to check if exist same @key in hash
259 * tables, we only add it to related hashbucket.
260 * example: maybe same nid will be related to multi difference export
262 int lustre_hash_additem(struct lustre_class_hash_body *hash_body, void *key,
263 struct hlist_node *actual_hnode)
266 struct lustre_hash_bucket *bucket = NULL;
267 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
270 LASSERT(hlist_unhashed(actual_hnode));
272 hashent = hop->lustre_hashfn(hash_body, key);
274 /* get the hashbucket and lock it */
275 bucket = &hash_body->lchb_hash_tables[hashent];
276 spin_lock(&bucket->lhb_lock);
278 hlist_add_head(actual_hnode, &(bucket->lhb_head));
280 #ifdef LUSTRE_HASH_DEBUG
281 /* hash distribute debug */
282 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
283 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
284 hash_body->hashname, hashent,
285 hash_body->lchb_hash_tables[hashent].lhb_item_count);
287 hop->lustre_hash_object_refcount_get(actual_hnode);
289 spin_unlock(&bucket->lhb_lock);
293 EXPORT_SYMBOL(lustre_hash_additem);
297 * this version of delitem will delete a hashitem with given @key,
298 * we need to search the <@key, @value> in hashbucket with @key,
299 * if match, the hashitem will be delete.
300 * we have a no-search version of delitem, it will directly delete a hashitem,
301 * doesn't need to search it in hashtables, so it is a O(1) delete.
303 int lustre_hash_delitem_by_key(struct lustre_class_hash_body *hash_body,
307 struct hlist_node * hash_item;
308 struct lustre_hash_bucket *bucket = NULL;
309 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
313 hashent = hop->lustre_hashfn(hash_body, key);
315 /* first, lock the hashbucket */
316 bucket = &hash_body->lchb_hash_tables[hashent];
317 spin_lock(&bucket->lhb_lock);
319 /* get the hash_item from hash_bucket */
320 hash_item = lustre_hash_getitem_in_bucket_nolock(hash_body, hashent,
323 if (hash_item == NULL) {
324 spin_unlock(&bucket->lhb_lock);
328 /* call delitem_nolock() to delete the hash_item */
329 retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
331 spin_unlock(&bucket->lhb_lock);
335 EXPORT_SYMBOL(lustre_hash_delitem_by_key);
338 * the O(1) version of delete hash item,
339 * it will directly delete the hashitem with given @hash_item,
340 * the parameter @key used to get the relation hash bucket and lock it.
342 int lustre_hash_delitem(struct lustre_class_hash_body *hash_body,
343 void *key, struct hlist_node * hash_item)
347 struct lustre_hash_bucket *bucket = NULL;
348 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
351 hashent = hop->lustre_hashfn(hash_body, key);
353 bucket = &hash_body->lchb_hash_tables[hashent];
354 spin_lock(&bucket->lhb_lock);
356 /* call delitem_nolock() to delete the hash_item */
357 retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
359 spin_unlock(&bucket->lhb_lock);
363 EXPORT_SYMBOL(lustre_hash_delitem);
365 void lustre_hash_bucket_iterate(struct lustre_class_hash_body *hash_body,
366 void *key, hash_item_iterate_cb func, void *data)
368 int hashent, find = 0;
369 struct lustre_hash_bucket *bucket = NULL;
370 struct hlist_node *hash_item_node = NULL;
371 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
372 struct obd_export *tmp = NULL;
376 hashent = hop->lustre_hashfn(hash_body, key);
377 bucket = &hash_body->lchb_hash_tables[hashent];
379 spin_lock(&bucket->lhb_lock);
380 hlist_for_each(hash_item_node, &(bucket->lhb_head)) {
381 find = hop->lustre_hash_key_compare(key, hash_item_node);
383 tmp = hop->lustre_hash_object_refcount_get(hash_item_node);
385 hop->lustre_hash_object_refcount_put(hash_item_node);
388 spin_unlock(&bucket->lhb_lock);
390 EXPORT_SYMBOL(lustre_hash_bucket_iterate);
392 void lustre_hash_iterate_all(struct lustre_class_hash_body *hash_body,
393 hash_item_iterate_cb func, void *data)
396 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
399 for( i = 0; i < hash_body->lchb_hash_max_size; i++ ) {
400 struct lustre_hash_bucket * bucket;
401 struct hlist_node * actual_hnode, *pos;
404 bucket = &hash_body->lchb_hash_tables[i];
405 #ifdef LUSTRE_HASH_DEBUG
406 CDEBUG(D_INFO, "idx %d - bucket %p\n", i, bucket);
408 spin_lock(&bucket->lhb_lock); /* lock the bucket */
409 hlist_for_each_safe(actual_hnode, pos, &(bucket->lhb_head)) {
410 obj = hop->lustre_hash_object_refcount_get(actual_hnode);
412 hop->lustre_hash_object_refcount_put(actual_hnode);
414 spin_unlock(&bucket->lhb_lock);
418 EXPORT_SYMBOL(lustre_hash_iterate_all);
421 void * lustre_hash_get_object_by_key(struct lustre_class_hash_body *hash_body,
425 struct hlist_node * hash_item_hnode = NULL;
426 void * obj_value = NULL;
427 struct lustre_hash_bucket *bucket = NULL;
428 struct lustre_hash_operations * hop = hash_body->lchb_hash_operations;
431 /* get the hash value from the given item */
432 hashent = hop->lustre_hashfn(hash_body, key);
434 bucket = &hash_body->lchb_hash_tables[hashent];
435 spin_lock(&bucket->lhb_lock); /* lock the bucket */
437 hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
440 if (hash_item_hnode == NULL) {
441 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
445 obj_value = hop->lustre_hash_object_refcount_get(hash_item_hnode);
446 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
450 EXPORT_SYMBOL(lustre_hash_get_object_by_key);
452 /* string hashing using djb2 hash algorithm */
453 __u32 djb2_hashfn(struct lustre_class_hash_body *hash_body, void* key,
460 LASSERT(key != NULL);
462 for( i = 0; i < size; i++ )
463 hash = hash * 33 + ptr[i];
465 hash &= (hash_body->lchb_hash_max_size - 1);
471 * define (uuid <-> export) hash operations and function define
474 /* define the uuid hash operations */
475 struct lustre_hash_operations uuid_hash_operations = {
476 .lustre_hashfn = uuid_hashfn,
477 .lustre_hash_key_compare = uuid_hash_key_compare,
478 .lustre_hash_object_refcount_get = uuid_export_refcount_get,
479 .lustre_hash_object_refcount_put = uuid_export_refcount_put,
482 __u32 uuid_hashfn(struct lustre_class_hash_body *hash_body, void * key)
484 struct obd_uuid * uuid_key = key;
486 return djb2_hashfn(hash_body, uuid_key->uuid, sizeof(uuid_key->uuid));
489 /* Note, it is impossible to find an export that is in failed state with
491 int uuid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
493 struct obd_export *export = NULL;
494 struct obd_uuid *uuid_key = NULL, *compared_uuid = NULL;
496 LASSERT( key != NULL);
498 uuid_key = (struct obd_uuid*)key;
500 export = hlist_entry(compared_hnode, struct obd_export, exp_uuid_hash);
502 compared_uuid = &export->exp_client_uuid;
504 RETURN(obd_uuid_equals(uuid_key, compared_uuid) &&
505 !export->exp_failed);
508 void * uuid_export_refcount_get(struct hlist_node * actual_hnode)
510 struct obd_export *export = NULL;
512 LASSERT(actual_hnode != NULL);
514 export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
516 LASSERT(export != NULL);
518 class_export_get(export);
523 void uuid_export_refcount_put(struct hlist_node * actual_hnode)
525 struct obd_export *export = NULL;
527 LASSERT(actual_hnode != NULL);
529 export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
531 LASSERT(export != NULL);
533 class_export_put(export);
537 * define (nid <-> export) hash operations and function define
540 /* define the nid hash operations */
541 struct lustre_hash_operations nid_hash_operations = {
542 .lustre_hashfn = nid_hashfn,
543 .lustre_hash_key_compare = nid_hash_key_compare,
544 .lustre_hash_object_refcount_get = nid_export_refcount_get,
545 .lustre_hash_object_refcount_put = nid_export_refcount_put,
548 __u32 nid_hashfn(struct lustre_class_hash_body *hash_body, void * key)
550 return djb2_hashfn(hash_body, key, sizeof(lnet_nid_t));
553 /* Note, it is impossible to find an export that is in failed state with
555 int nid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
557 struct obd_export *export = NULL;
558 lnet_nid_t *nid_key = NULL;
560 LASSERT( key != NULL);
562 nid_key = (lnet_nid_t*)key;
564 export = hlist_entry(compared_hnode, struct obd_export, exp_nid_hash);
566 return (export->exp_connection->c_peer.nid == *nid_key &&
567 !export->exp_failed);
570 void *nid_export_refcount_get(struct hlist_node *actual_hnode)
572 struct obd_export *export = NULL;
574 LASSERT(actual_hnode != NULL);
576 export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
578 LASSERT(export != NULL);
580 class_export_get(export);
585 void nid_export_refcount_put(struct hlist_node *actual_hnode)
587 struct obd_export *export = NULL;
589 LASSERT(actual_hnode != NULL);
591 export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
593 LASSERT(export != NULL);
595 class_export_put(export);
599 * define (net_peer <-> connection) hash operations and function define
602 /* define the conn hash operations */
603 struct lustre_hash_operations conn_hash_operations = {
604 .lustre_hashfn = conn_hashfn,
605 .lustre_hash_key_compare = conn_hash_key_compare,
606 .lustre_hash_object_refcount_get = conn_refcount_get,
607 .lustre_hash_object_refcount_put = conn_refcount_put,
609 EXPORT_SYMBOL(conn_hash_operations);
611 __u32 conn_hashfn(struct lustre_class_hash_body *hash_body, void * key)
613 return djb2_hashfn(hash_body, key, sizeof(lnet_process_id_t));
616 int conn_hash_key_compare(void *key, struct hlist_node *compared_hnode)
618 struct ptlrpc_connection *c = NULL;
619 lnet_process_id_t *conn_key = NULL;
621 LASSERT( key != NULL);
623 conn_key = (lnet_process_id_t*)key;
625 c = hlist_entry(compared_hnode, struct ptlrpc_connection, c_hash);
627 return (conn_key->nid == c->c_peer.nid &&
628 conn_key->pid == c->c_peer.pid);
631 void *conn_refcount_get(struct hlist_node *actual_hnode)
633 struct ptlrpc_connection *c = NULL;
635 LASSERT(actual_hnode != NULL);
637 c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
641 atomic_inc(&c->c_refcount);
646 void conn_refcount_put(struct hlist_node *actual_hnode)
648 struct ptlrpc_connection *c = NULL;
650 LASSERT(actual_hnode != NULL);
652 c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
656 atomic_dec(&c->c_refcount);
659 /*******************************************************************************/
660 /* ( nid<>nidstats ) hash operations define */
662 struct lustre_hash_operations nid_stat_hash_operations = {
663 .lustre_hashfn = nid_hashfn,
664 .lustre_hash_key_compare = nidstats_hash_key_compare,
665 .lustre_hash_object_refcount_get = nidstats_refcount_get,
666 .lustre_hash_object_refcount_put = nidstats_refcount_put,
668 EXPORT_SYMBOL(nid_stat_hash_operations);
670 int nidstats_hash_key_compare(void *key, struct hlist_node * compared_hnode)
672 struct nid_stat *data;
675 LASSERT( key != NULL);
677 nid_key = (lnet_nid_t*)key;
678 data = hlist_entry(compared_hnode, struct nid_stat, nid_hash);
680 return (data->nid == *nid_key);
683 void* nidstats_refcount_get(struct hlist_node * actual_hnode)
685 struct nid_stat *data;
687 data = hlist_entry(actual_hnode, struct nid_stat, nid_hash);
688 data->nid_exp_ref_count++;
693 void nidstats_refcount_put(struct hlist_node * actual_hnode)
695 struct nid_stat *data;
697 data = hlist_entry(actual_hnode, struct nid_stat, nid_hash);
698 data->nid_exp_ref_count--;
702 /*******************************************************************************/