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 * this version of additem, it allow multi same @key <key, value> in hashtables.
182 * in this additem version, we don't need to check if exist same @key in hash
183 * tables, we only add it to related hashbucket.
184 * example: maybe same nid will be related to multi difference export
186 int lustre_hash_additem(struct lustre_class_hash_body *hash_body, void *key,
187 struct hlist_node *actual_hnode)
190 struct lustre_hash_bucket *bucket = NULL;
191 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
194 LASSERT(hlist_unhashed(actual_hnode));
196 hashent = hop->lustre_hashfn(hash_body, key);
198 /* get the hashbucket and lock it */
199 bucket = &hash_body->lchb_hash_tables[hashent];
200 spin_lock(&bucket->lhb_lock);
202 hlist_add_head(actual_hnode, &(bucket->lhb_head));
204 #ifdef LUSTRE_HASH_DEBUG
205 /* hash distribute debug */
206 hash_body->lchb_hash_tables[hashent].lhb_item_count++;
207 CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
208 hash_body->hashname, hashent,
209 hash_body->lchb_hash_tables[hashent].lhb_item_count);
211 hop->lustre_hash_object_refcount_get(actual_hnode);
213 spin_unlock(&bucket->lhb_lock);
217 EXPORT_SYMBOL(lustre_hash_additem);
221 * this version of delitem will delete a hashitem with given @key,
222 * we need to search the <@key, @value> in hashbucket with @key,
223 * if match, the hashitem will be delete.
224 * we have a no-search version of delitem, it will directly delete a hashitem,
225 * doesn't need to search it in hashtables, so it is a O(1) delete.
227 int lustre_hash_delitem_by_key(struct lustre_class_hash_body *hash_body,
231 struct hlist_node * hash_item;
232 struct lustre_hash_bucket *bucket = NULL;
233 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
237 hashent = hop->lustre_hashfn(hash_body, key);
239 /* first, lock the hashbucket */
240 bucket = &hash_body->lchb_hash_tables[hashent];
241 spin_lock(&bucket->lhb_lock);
243 /* get the hash_item from hash_bucket */
244 hash_item = lustre_hash_getitem_in_bucket_nolock(hash_body, hashent,
247 if (hash_item == NULL) {
248 spin_unlock(&bucket->lhb_lock);
252 /* call delitem_nolock() to delete the hash_item */
253 retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
255 spin_unlock(&bucket->lhb_lock);
259 EXPORT_SYMBOL(lustre_hash_delitem_by_key);
262 * the O(1) version of delete hash item,
263 * it will directly delete the hashitem with given @hash_item,
264 * the parameter @key used to get the relation hash bucket and lock it.
266 int lustre_hash_delitem(struct lustre_class_hash_body *hash_body,
267 void *key, struct hlist_node * hash_item)
271 struct lustre_hash_bucket *bucket = NULL;
272 struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
275 hashent = hop->lustre_hashfn(hash_body, key);
277 bucket = &hash_body->lchb_hash_tables[hashent];
278 spin_lock(&bucket->lhb_lock);
280 /* call delitem_nolock() to delete the hash_item */
281 retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
283 spin_unlock(&bucket->lhb_lock);
287 EXPORT_SYMBOL(lustre_hash_delitem);
289 void * lustre_hash_get_object_by_key(struct lustre_class_hash_body *hash_body,
293 struct hlist_node * hash_item_hnode = NULL;
294 void * obj_value = NULL;
295 struct lustre_hash_bucket *bucket = NULL;
296 struct lustre_hash_operations * hop = hash_body->lchb_hash_operations;
299 /* get the hash value from the given item */
300 hashent = hop->lustre_hashfn(hash_body, key);
302 bucket = &hash_body->lchb_hash_tables[hashent];
303 spin_lock(&bucket->lhb_lock); /* lock the bucket */
305 hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
308 if (hash_item_hnode == NULL) {
309 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
313 obj_value = hop->lustre_hash_object_refcount_get(hash_item_hnode);
314 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
318 EXPORT_SYMBOL(lustre_hash_get_object_by_key);
321 * define (uuid <-> export) hash operations and function define
324 /* define the uuid hash operations */
325 struct lustre_hash_operations uuid_hash_operations = {
326 .lustre_hashfn = uuid_hashfn,
327 .lustre_hash_key_compare = uuid_hash_key_compare,
328 .lustre_hash_object_refcount_get = uuid_export_refcount_get,
329 .lustre_hash_object_refcount_put = uuid_export_refcount_put,
332 /* string hashing using djb2 hash algorithm */
333 __u32 uuid_hashfn(struct lustre_class_hash_body *hash_body, void * key)
336 struct obd_uuid * uuid_key = NULL;
340 LASSERT(key != NULL);
342 uuid_key = (struct obd_uuid*)key;
343 ptr = uuid_key->uuid;
345 while ((c = *ptr++)) {
346 hash = hash * 33 + c;
349 hash &= (hash_body->lchb_hash_max_size - 1);
354 /* Note, it is impossible to find an export that is in failed state with
356 int uuid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
358 struct obd_export *export = NULL;
359 struct obd_uuid *uuid_key = NULL, *compared_uuid = NULL;
361 LASSERT( key != NULL);
363 uuid_key = (struct obd_uuid*)key;
365 export = hlist_entry(compared_hnode, struct obd_export, exp_uuid_hash);
367 compared_uuid = &export->exp_client_uuid;
369 RETURN(obd_uuid_equals(uuid_key, compared_uuid) &&
370 !export->exp_failed);
373 void * uuid_export_refcount_get(struct hlist_node * actual_hnode)
375 struct obd_export *export = NULL;
377 LASSERT(actual_hnode != NULL);
379 export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
381 LASSERT(export != NULL);
383 class_export_get(export);
388 void uuid_export_refcount_put(struct hlist_node * actual_hnode)
390 struct obd_export *export = NULL;
392 LASSERT(actual_hnode != NULL);
394 export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
396 LASSERT(export != NULL);
398 class_export_put(export);
402 * define (nid <-> export) hash operations and function define
405 /* define the nid hash operations */
406 struct lustre_hash_operations nid_hash_operations = {
407 .lustre_hashfn = nid_hashfn,
408 .lustre_hash_key_compare = nid_hash_key_compare,
409 .lustre_hash_object_refcount_get = nid_export_refcount_get,
410 .lustre_hash_object_refcount_put = nid_export_refcount_put,
413 /* string hashing using djb2 hash algorithm */
414 __u32 nid_hashfn(struct lustre_class_hash_body *hash_body, void * key)
420 LASSERT(key != NULL);
422 for(i = 0 ; i < sizeof(lnet_nid_t) ; i ++)
423 hash = hash * 33 + ptr[i];
425 hash &= (hash_body->lchb_hash_max_size - 1);
430 /* Note, it is impossible to find an export that is in failed state with
432 int nid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
434 struct obd_export *export = NULL;
435 lnet_nid_t *nid_key = NULL;
437 LASSERT( key != NULL);
439 nid_key = (lnet_nid_t*)key;
441 export = hlist_entry(compared_hnode, struct obd_export, exp_nid_hash);
443 return (export->exp_connection->c_peer.nid == *nid_key &&
444 !export->exp_failed);
447 void *nid_export_refcount_get(struct hlist_node *actual_hnode)
449 struct obd_export *export = NULL;
451 LASSERT(actual_hnode != NULL);
453 export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
455 LASSERT(export != NULL);
457 class_export_get(export);
462 void nid_export_refcount_put(struct hlist_node *actual_hnode)
464 struct obd_export *export = NULL;
466 LASSERT(actual_hnode != NULL);
468 export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
470 LASSERT(export != NULL);
472 class_export_put(export);
476 * define (net_peer <-> connection) hash operations and function define
479 /* define the conn hash operations */
480 struct lustre_hash_operations conn_hash_operations = {
481 .lustre_hashfn = conn_hashfn,
482 .lustre_hash_key_compare = conn_hash_key_compare,
483 .lustre_hash_object_refcount_get = conn_refcount_get,
484 .lustre_hash_object_refcount_put = conn_refcount_put,
486 EXPORT_SYMBOL(conn_hash_operations);
488 /* string hashing using djb2 hash algorithm */
489 __u32 conn_hashfn(struct lustre_class_hash_body *hash_body, void * key)
495 LASSERT(key != NULL);
497 for(i = 0 ; i < sizeof(lnet_process_id_t) ; i ++)
498 hash = hash * 33 + ptr[i];
500 hash &= (hash_body->lchb_hash_max_size - 1);
505 int conn_hash_key_compare(void *key, struct hlist_node *compared_hnode)
507 struct ptlrpc_connection *c = NULL;
508 lnet_process_id_t *conn_key = NULL;
510 LASSERT( key != NULL);
512 conn_key = (lnet_process_id_t*)key;
514 c = hlist_entry(compared_hnode, struct ptlrpc_connection, c_hash);
516 return (conn_key->nid == c->c_peer.nid &&
517 conn_key->pid == c->c_peer.pid);
520 void *conn_refcount_get(struct hlist_node *actual_hnode)
522 struct ptlrpc_connection *c = NULL;
524 LASSERT(actual_hnode != NULL);
526 c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
530 atomic_inc(&c->c_refcount);
535 void conn_refcount_put(struct hlist_node *actual_hnode)
537 struct ptlrpc_connection *c = NULL;
539 LASSERT(actual_hnode != NULL);
541 c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
545 atomic_dec(&c->c_refcount);