1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
4 * Copyright (C) 2005 Cluster File Systems, Inc.
5 * Author: YuZhangyong <yzy@clusterfs.com>
7 * This file is part of Lustre, http://www.lustre.org/
9 * No redistribution or use is permitted outside of Cluster File Systems, Inc.
11 * Implement a hash class for hash process in lustre system.
15 #include <liblustre.h>
19 #include <obd_class.h>
20 #include <class_hash.h>
21 #include <lustre_export.h>
22 #include <obd_support.h>
23 #include <lustre_net.h>
25 int lustre_hash_init(struct lustre_class_hash_body **hash_body_new,
26 char *hashname, __u32 hashsize,
27 struct lustre_hash_operations *hash_operations)
30 struct lustre_class_hash_body *hash_body = NULL;
32 LASSERT(hashsize > 0);
33 LASSERT(hash_operations != NULL);
43 LASSERTF(n == 1, "hashsize %u isn't 2^n\n", hashsize);
45 /* alloc space for hash_body */
46 OBD_ALLOC(hash_body, sizeof(*hash_body));
48 if (hash_body == NULL) {
49 CERROR("Cannot alloc space for hash body, hashname = %s \n",
54 LASSERT(hashname != NULL &&
55 strlen(hashname) <= sizeof(hash_body->hashname));
56 strcpy(hash_body->hashname, hashname);
57 hash_body->lchb_hash_max_size = hashsize;
58 hash_body->lchb_hash_operations = hash_operations;
60 /* alloc space for the hash tables */
61 OBD_ALLOC(hash_body->lchb_hash_tables,
62 sizeof(*hash_body->lchb_hash_tables) * hash_body->lchb_hash_max_size);
64 if (hash_body->lchb_hash_tables == NULL) {
65 OBD_FREE(hash_body, sizeof(*hash_body));
66 CERROR("Cannot alloc space for hashtables, hashname = %s \n",
71 spin_lock_init(&hash_body->lchb_lock); /* initialize the body lock */
73 for(i = 0 ; i < hash_body->lchb_hash_max_size; i++) {
74 /* initial the bucket lock and list_head */
75 INIT_HLIST_HEAD(&hash_body->lchb_hash_tables[i].lhb_head);
76 spin_lock_init(&hash_body->lchb_hash_tables[i].lhb_lock);
78 *hash_body_new = hash_body;
82 EXPORT_SYMBOL(lustre_hash_init);
84 void lustre_hash_exit(struct lustre_class_hash_body **new_hash_body)
87 struct lustre_class_hash_body *hash_body = NULL;
90 hash_body = *new_hash_body;
92 if (hash_body == NULL) {
93 CWARN("hash body has been deleted\n");
97 spin_lock(&hash_body->lchb_lock); /* lock the hash tables */
99 if (hash_body->lchb_hash_tables == NULL ) {
100 spin_unlock(&hash_body->lchb_lock);
101 CWARN("hash tables has been deleted\n");
105 for( i = 0; i < hash_body->lchb_hash_max_size; i++ ) {
106 struct lustre_hash_bucket * bucket;
107 struct hlist_node * actual_hnode, *pos;
109 bucket = &hash_body->lchb_hash_tables[i];
110 spin_lock(&bucket->lhb_lock); /* lock the bucket */
111 hlist_for_each_safe(actual_hnode, pos, &(bucket->lhb_head)) {
112 lustre_hash_delitem_nolock(hash_body, i, actual_hnode);
114 spin_unlock(&bucket->lhb_lock);
117 /* free the hash_tables's memory space */
118 OBD_FREE(hash_body->lchb_hash_tables,
119 sizeof(*hash_body->lchb_hash_tables) * hash_body->lchb_hash_max_size);
121 hash_body->lchb_hash_tables = NULL;
123 spin_unlock(&hash_body->lchb_lock);
126 /* free the hash_body's memory space */
127 if (hash_body != NULL) {
128 OBD_FREE(hash_body, sizeof(*hash_body));
129 *new_hash_body = NULL;
133 EXPORT_SYMBOL(lustre_hash_exit);
136 * only allow unique @key in hashtables, if the same @key has existed
137 * in hashtables, it will return with fails.
139 int lustre_hash_additem_unique(struct lustre_class_hash_body *hash_body,
140 void *key, struct hlist_node *actual_hnode)
143 struct lustre_hash_bucket *bucket = NULL;
144 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
147 LASSERT(hlist_unhashed(actual_hnode));
148 hashent = hop->lustre_hashfn(hash_body, key);
150 /* get the hash-bucket and lock it */
151 bucket = &hash_body->lchb_hash_tables[hashent];
152 spin_lock(&bucket->lhb_lock);
154 if ( (lustre_hash_getitem_in_bucket_nolock(hash_body, hashent, key)) != NULL) {
155 /* the added-item exist in hashtables, so cannot add it again */
156 spin_unlock(&bucket->lhb_lock);
158 CWARN("Already found the key in hash [%s]\n",
159 hash_body->hashname);
163 hlist_add_head(actual_hnode, &(bucket->lhb_head));
165 #ifdef LUSTRE_HASH_DEBUG
166 /* hash distribute debug */
167 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
168 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
169 hash_body->hashname, hashent,
170 hash_body->lchb_hash_tables[hashent].lhb_item_count);
172 hop->lustre_hash_object_refcount_get(actual_hnode);
174 spin_unlock(&bucket->lhb_lock);
178 EXPORT_SYMBOL(lustre_hash_additem_unique);
181 * only allow unique @key in hashtables, if the same @key has existed
182 * in hashtables, it will return with fails.
184 void* lustre_hash_findadd_unique(struct lustre_class_hash_body *hash_body,
185 void *key, struct hlist_node *actual_hnode)
188 struct lustre_hash_bucket *bucket = NULL;
189 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
190 struct hlist_node * hash_item_hnode = NULL;
194 LASSERT(hlist_unhashed(actual_hnode));
195 hashent = hop->lustre_hashfn(hash_body, key);
197 /* get the hash-bucket and lock it */
198 bucket = &hash_body->lchb_hash_tables[hashent];
199 spin_lock(&bucket->lhb_lock);
201 hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
203 if ( hash_item_hnode != NULL) {
204 /* the added-item exist in hashtables, so cannot add it again */
205 obj = hop->lustre_hash_object_refcount_get(hash_item_hnode);
206 spin_unlock(&bucket->lhb_lock);
210 hlist_add_head(actual_hnode, &(bucket->lhb_head));
212 #ifdef LUSTRE_HASH_DEBUG
213 /* hash distribute debug */
214 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
215 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
216 hash_body->hashname, hashent,
217 hash_body->lchb_hash_tables[hashent].lhb_item_count);
219 obj = hop->lustre_hash_object_refcount_get(actual_hnode);
221 spin_unlock(&bucket->lhb_lock);
225 EXPORT_SYMBOL(lustre_hash_findadd_unique);
228 * this version of additem, it allow multi same @key <key, value> in hashtables.
229 * in this additem version, we don't need to check if exist same @key in hash
230 * tables, we only add it to related hashbucket.
231 * example: maybe same nid will be related to multi difference export
233 int lustre_hash_additem(struct lustre_class_hash_body *hash_body, void *key,
234 struct hlist_node *actual_hnode)
237 struct lustre_hash_bucket *bucket = NULL;
238 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
241 LASSERT(hlist_unhashed(actual_hnode));
243 hashent = hop->lustre_hashfn(hash_body, key);
245 /* get the hashbucket and lock it */
246 bucket = &hash_body->lchb_hash_tables[hashent];
247 spin_lock(&bucket->lhb_lock);
249 hlist_add_head(actual_hnode, &(bucket->lhb_head));
251 #ifdef LUSTRE_HASH_DEBUG
252 /* hash distribute debug */
253 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
254 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
255 hash_body->hashname, hashent,
256 hash_body->lchb_hash_tables[hashent].lhb_item_count);
258 hop->lustre_hash_object_refcount_get(actual_hnode);
260 spin_unlock(&bucket->lhb_lock);
264 EXPORT_SYMBOL(lustre_hash_additem);
268 * this version of delitem will delete a hashitem with given @key,
269 * we need to search the <@key, @value> in hashbucket with @key,
270 * if match, the hashitem will be delete.
271 * we have a no-search version of delitem, it will directly delete a hashitem,
272 * doesn't need to search it in hashtables, so it is a O(1) delete.
274 int lustre_hash_delitem_by_key(struct lustre_class_hash_body *hash_body,
278 struct hlist_node * hash_item;
279 struct lustre_hash_bucket *bucket = NULL;
280 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
284 hashent = hop->lustre_hashfn(hash_body, key);
286 /* first, lock the hashbucket */
287 bucket = &hash_body->lchb_hash_tables[hashent];
288 spin_lock(&bucket->lhb_lock);
290 /* get the hash_item from hash_bucket */
291 hash_item = lustre_hash_getitem_in_bucket_nolock(hash_body, hashent,
294 if (hash_item == NULL) {
295 spin_unlock(&bucket->lhb_lock);
299 /* call delitem_nolock() to delete the hash_item */
300 retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
302 spin_unlock(&bucket->lhb_lock);
306 EXPORT_SYMBOL(lustre_hash_delitem_by_key);
309 * the O(1) version of delete hash item,
310 * it will directly delete the hashitem with given @hash_item,
311 * the parameter @key used to get the relation hash bucket and lock it.
313 int lustre_hash_delitem(struct lustre_class_hash_body *hash_body,
314 void *key, struct hlist_node * hash_item)
318 struct lustre_hash_bucket *bucket = NULL;
319 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
322 hashent = hop->lustre_hashfn(hash_body, key);
324 bucket = &hash_body->lchb_hash_tables[hashent];
325 spin_lock(&bucket->lhb_lock);
327 /* call delitem_nolock() to delete the hash_item */
328 retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
330 spin_unlock(&bucket->lhb_lock);
334 EXPORT_SYMBOL(lustre_hash_delitem);
336 void lustre_hash_bucket_iterate(struct lustre_class_hash_body *hash_body,
337 void *key, hash_item_iterate_cb func, void *data)
339 int hashent, find = 0;
340 struct lustre_hash_bucket *bucket = NULL;
341 struct hlist_node *hash_item_node = NULL;
342 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
343 struct obd_export *tmp = NULL;
347 hashent = hop->lustre_hashfn(hash_body, key);
348 bucket = &hash_body->lchb_hash_tables[hashent];
350 spin_lock(&bucket->lhb_lock);
351 hlist_for_each(hash_item_node, &(bucket->lhb_head)) {
352 find = hop->lustre_hash_key_compare(key, hash_item_node);
354 tmp = hop->lustre_hash_object_refcount_get(hash_item_node);
356 hop->lustre_hash_object_refcount_put(hash_item_node);
359 spin_unlock(&bucket->lhb_lock);
361 EXPORT_SYMBOL(lustre_hash_bucket_iterate);
363 void lustre_hash_iterate_all(struct lustre_class_hash_body *hash_body,
364 hash_item_iterate_cb func, void *data)
367 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
370 for( i = 0; i < hash_body->lchb_hash_max_size; i++ ) {
371 struct lustre_hash_bucket * bucket;
372 struct hlist_node * actual_hnode, *pos;
375 bucket = &hash_body->lchb_hash_tables[i];
376 #ifdef LUSTRE_HASH_DEBUG
377 CDEBUG(D_INFO, "idx %d - bucket %p\n", i, bucket);
379 spin_lock(&bucket->lhb_lock); /* lock the bucket */
380 hlist_for_each_safe(actual_hnode, pos, &(bucket->lhb_head)) {
381 obj = hop->lustre_hash_object_refcount_get(actual_hnode);
383 hop->lustre_hash_object_refcount_put(actual_hnode);
385 spin_unlock(&bucket->lhb_lock);
389 EXPORT_SYMBOL(lustre_hash_iterate_all);
392 void * lustre_hash_get_object_by_key(struct lustre_class_hash_body *hash_body,
396 struct hlist_node * hash_item_hnode = NULL;
397 void * obj_value = NULL;
398 struct lustre_hash_bucket *bucket = NULL;
399 struct lustre_hash_operations * hop = hash_body->lchb_hash_operations;
402 /* get the hash value from the given item */
403 hashent = hop->lustre_hashfn(hash_body, key);
405 bucket = &hash_body->lchb_hash_tables[hashent];
406 spin_lock(&bucket->lhb_lock); /* lock the bucket */
408 hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
411 if (hash_item_hnode == NULL) {
412 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
416 obj_value = hop->lustre_hash_object_refcount_get(hash_item_hnode);
417 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
421 EXPORT_SYMBOL(lustre_hash_get_object_by_key);
423 /* string hashing using djb2 hash algorithm */
424 __u32 djb2_hashfn(struct lustre_class_hash_body *hash_body, void* key,
431 LASSERT(key != NULL);
433 for( i = 0; i < size; i++ )
434 hash = hash * 33 + ptr[i];
436 hash &= (hash_body->lchb_hash_max_size - 1);
442 * define (uuid <-> export) hash operations and function define
445 /* define the uuid hash operations */
446 struct lustre_hash_operations uuid_hash_operations = {
447 .lustre_hashfn = uuid_hashfn,
448 .lustre_hash_key_compare = uuid_hash_key_compare,
449 .lustre_hash_object_refcount_get = uuid_export_refcount_get,
450 .lustre_hash_object_refcount_put = uuid_export_refcount_put,
453 __u32 uuid_hashfn(struct lustre_class_hash_body *hash_body, void * key)
455 struct obd_uuid * uuid_key = key;
457 return djb2_hashfn(hash_body, uuid_key->uuid, sizeof(uuid_key->uuid));
460 /* Note, it is impossible to find an export that is in failed state with
462 int uuid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
464 struct obd_export *export = NULL;
465 struct obd_uuid *uuid_key = NULL, *compared_uuid = NULL;
467 LASSERT( key != NULL);
469 uuid_key = (struct obd_uuid*)key;
471 export = hlist_entry(compared_hnode, struct obd_export, exp_uuid_hash);
473 compared_uuid = &export->exp_client_uuid;
475 RETURN(obd_uuid_equals(uuid_key, compared_uuid) &&
476 !export->exp_failed);
479 void * uuid_export_refcount_get(struct hlist_node * actual_hnode)
481 struct obd_export *export = NULL;
483 LASSERT(actual_hnode != NULL);
485 export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
487 LASSERT(export != NULL);
489 class_export_get(export);
494 void uuid_export_refcount_put(struct hlist_node * actual_hnode)
496 struct obd_export *export = NULL;
498 LASSERT(actual_hnode != NULL);
500 export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
502 LASSERT(export != NULL);
504 class_export_put(export);
508 * define (nid <-> export) hash operations and function define
511 /* define the nid hash operations */
512 struct lustre_hash_operations nid_hash_operations = {
513 .lustre_hashfn = nid_hashfn,
514 .lustre_hash_key_compare = nid_hash_key_compare,
515 .lustre_hash_object_refcount_get = nid_export_refcount_get,
516 .lustre_hash_object_refcount_put = nid_export_refcount_put,
519 __u32 nid_hashfn(struct lustre_class_hash_body *hash_body, void * key)
521 return djb2_hashfn(hash_body, key, sizeof(lnet_nid_t));
524 /* Note, it is impossible to find an export that is in failed state with
526 int nid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
528 struct obd_export *export = NULL;
529 lnet_nid_t *nid_key = NULL;
531 LASSERT( key != NULL);
533 nid_key = (lnet_nid_t*)key;
535 export = hlist_entry(compared_hnode, struct obd_export, exp_nid_hash);
537 return (export->exp_connection->c_peer.nid == *nid_key &&
538 !export->exp_failed);
541 void *nid_export_refcount_get(struct hlist_node *actual_hnode)
543 struct obd_export *export = NULL;
545 LASSERT(actual_hnode != NULL);
547 export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
549 LASSERT(export != NULL);
551 class_export_get(export);
556 void nid_export_refcount_put(struct hlist_node *actual_hnode)
558 struct obd_export *export = NULL;
560 LASSERT(actual_hnode != NULL);
562 export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
564 LASSERT(export != NULL);
566 class_export_put(export);
570 * define (net_peer <-> connection) hash operations and function define
573 /* define the conn hash operations */
574 struct lustre_hash_operations conn_hash_operations = {
575 .lustre_hashfn = conn_hashfn,
576 .lustre_hash_key_compare = conn_hash_key_compare,
577 .lustre_hash_object_refcount_get = conn_refcount_get,
578 .lustre_hash_object_refcount_put = conn_refcount_put,
580 EXPORT_SYMBOL(conn_hash_operations);
582 __u32 conn_hashfn(struct lustre_class_hash_body *hash_body, void * key)
584 return djb2_hashfn(hash_body, key, sizeof(lnet_process_id_t));
587 int conn_hash_key_compare(void *key, struct hlist_node *compared_hnode)
589 struct ptlrpc_connection *c = NULL;
590 lnet_process_id_t *conn_key = NULL;
592 LASSERT( key != NULL);
594 conn_key = (lnet_process_id_t*)key;
596 c = hlist_entry(compared_hnode, struct ptlrpc_connection, c_hash);
598 return (conn_key->nid == c->c_peer.nid &&
599 conn_key->pid == c->c_peer.pid);
602 void *conn_refcount_get(struct hlist_node *actual_hnode)
604 struct ptlrpc_connection *c = NULL;
606 LASSERT(actual_hnode != NULL);
608 c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
612 atomic_inc(&c->c_refcount);
617 void conn_refcount_put(struct hlist_node *actual_hnode)
619 struct ptlrpc_connection *c = NULL;
621 LASSERT(actual_hnode != NULL);
623 c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
627 atomic_dec(&c->c_refcount);
630 /*******************************************************************************/
631 /* ( nid<>nidstats ) hash operations define */
633 struct lustre_hash_operations nid_stat_hash_operations = {
634 .lustre_hashfn = nid_hashfn,
635 .lustre_hash_key_compare = nidstats_hash_key_compare,
636 .lustre_hash_object_refcount_get = nidstats_refcount_get,
637 .lustre_hash_object_refcount_put = nidstats_refcount_put,
639 EXPORT_SYMBOL(nid_stat_hash_operations);
641 int nidstats_hash_key_compare(void *key, struct hlist_node * compared_hnode)
643 struct nid_stat *data;
646 LASSERT( key != NULL);
648 nid_key = (lnet_nid_t*)key;
649 data = hlist_entry(compared_hnode, struct nid_stat, nid_hash);
651 return (data->nid == *nid_key);
654 void* nidstats_refcount_get(struct hlist_node * actual_hnode)
656 struct nid_stat *data;
658 data = hlist_entry(actual_hnode, struct nid_stat, nid_hash);
659 data->nid_exp_ref_count++;
664 void nidstats_refcount_put(struct hlist_node * actual_hnode)
666 struct nid_stat *data;
668 data = hlist_entry(actual_hnode, struct nid_stat, nid_hash);
669 data->nid_exp_ref_count--;
673 /*******************************************************************************/