lustre/obdclass/class_hash.c

   1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
   2  * vim:expandtab:shiftwidth=8:tabstop=8:
   3  *
   4  *  Copyright (C) 2005 Cluster File Systems, Inc.
   5  *   Author: YuZhangyong <yzy@clusterfs.com>
   6  *
   7  *   This file is part of Lustre, http://www.lustre.org/
   8  *
   9  *   No redistribution or use is permitted outside of Cluster File Systems, Inc.
  10  *
  11  *   Implement a hash class for hash process in lustre system.
  12  */
  13
  14 #ifndef __KERNEL__
  15 #include <liblustre.h>
  16 #include <obd.h>
  17 #endif
  18
  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>
  24
  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)
  28 {
  29         int i, n = 0;
  30         struct lustre_class_hash_body *hash_body = NULL;
  31
  32         LASSERT(hashsize > 0);
  33         LASSERT(hash_operations != NULL);
  34         ENTRY;
  35
  36         i = hashsize;
  37         while (i != 0) {
  38                 if (i & 0x1)
  39                         n++;
  40                 i >>= 1;
  41         }
  42
  43         LASSERTF(n == 1, "hashsize %u isn't 2^n\n", hashsize);
  44
  45         /* alloc space for hash_body */
  46         OBD_ALLOC(hash_body, sizeof(*hash_body));
  47
  48         if (hash_body == NULL) {
  49                 CERROR("Cannot alloc space for hash body, hashname = %s \n",
  50                         hashname);
  51                 RETURN(-ENOMEM);
  52         }
  53
  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;
  59
  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);
  63
  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",
  67                         hash_body->hashname);
  68                 RETURN(-ENOMEM);
  69         }
  70
  71         spin_lock_init(&hash_body->lchb_lock); /* initialize the body lock */
  72
  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);
  77         }
  78         *hash_body_new = hash_body;
  79
  80         RETURN(0);
  81 }
  82 EXPORT_SYMBOL(lustre_hash_init);
  83
  84 void lustre_hash_exit(struct lustre_class_hash_body **new_hash_body)
  85 {
  86         int i;
  87         struct lustre_class_hash_body *hash_body = NULL;
  88         ENTRY;
  89
  90         hash_body = *new_hash_body;
  91
  92         if (hash_body == NULL) {
  93                 CWARN("hash body has been deleted\n");
  94                 goto out_hash;
  95         }
  96
  97         spin_lock(&hash_body->lchb_lock); /* lock the hash tables */
  98
  99         if (hash_body->lchb_hash_tables == NULL ) {
 100                 spin_unlock(&hash_body->lchb_lock);
 101                 CWARN("hash tables has been deleted\n");
 102                 goto out_hash;
 103         }
 104
 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;
 108
 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);
 113                 }
 114                 spin_unlock(&bucket->lhb_lock);
 115         }
 116
 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);
 120
 121         hash_body->lchb_hash_tables = NULL;
 122
 123         spin_unlock(&hash_body->lchb_lock);
 124
 125 out_hash :
 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;
 130         }
 131         EXIT;
 132 }
 133 EXPORT_SYMBOL(lustre_hash_exit);
 134
 135 /*
 136  * only allow unique @key in hashtables, if the same @key has existed
 137  * in hashtables, it will return with fails.
 138  */
 139 int lustre_hash_additem_unique(struct lustre_class_hash_body *hash_body,
 140                                void *key, struct hlist_node *actual_hnode)
 141 {
 142         int hashent;
 143         struct lustre_hash_bucket *bucket = NULL;
 144         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 145         ENTRY;
 146
 147         hashent = hop->lustre_hashfn(hash_body, key);
 148
 149         /* get the hash-bucket and lock it */
 150         bucket = &hash_body->lchb_hash_tables[hashent];
 151         spin_lock(&bucket->lhb_lock);
 152
 153         if ( (lustre_hash_getitem_in_bucket_nolock(hash_body, hashent, key)) != NULL) {
 154                 /* the added-item exist in hashtables, so cannot add it again */
 155                 spin_unlock(&bucket->lhb_lock);
 156
 157                 CWARN("Already found the key in hash [%s]\n",
 158                       hash_body->hashname);
 159                 RETURN(-EALREADY);
 160         }
 161
 162         hlist_add_head(actual_hnode, &(bucket->lhb_head));
 163
 164 #ifdef LUSTRE_HASH_DEBUG
 165         /* hash distribute debug */
 166         hash_body->lchb_hash_tables[hashent].lhb_item_count++;
 167         CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
 168                         hash_body->hashname, hashent,
 169                         hash_body->lchb_hash_tables[hashent].lhb_item_count);
 170 #endif
 171         hop->lustre_hash_object_refcount_get(actual_hnode);
 172
 173         spin_unlock(&bucket->lhb_lock);
 174
 175         RETURN(0);
 176 }
 177 EXPORT_SYMBOL(lustre_hash_additem_unique);
 178
 179 /*
 180  * this version of additem, it allow multi same @key <key, value> in hashtables.
 181  * in this additem version, we don't need to check if exist same @key in hash
 182  * tables, we only add it to related hashbucket.
 183  * example: maybe same nid will be related to multi difference export
 184  */
 185 int lustre_hash_additem(struct lustre_class_hash_body *hash_body, void *key,
 186                          struct hlist_node *actual_hnode)
 187 {
 188         int hashent;
 189         struct lustre_hash_bucket *bucket = NULL;
 190         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 191         ENTRY;
 192
 193         hashent = hop->lustre_hashfn(hash_body, key);
 194
 195         /* get the hashbucket and lock it */
 196         bucket = &hash_body->lchb_hash_tables[hashent];
 197         spin_lock(&bucket->lhb_lock);
 198
 199         hlist_add_head(actual_hnode, &(bucket->lhb_head));
 200
 201 #ifdef LUSTRE_HASH_DEBUG
 202         /* hash distribute debug */
 203         hash_body->lchb_hash_tables[hashent].lhb_item_count++;
 204         CDEBUG(D_INFO, "hashname[%s] bucket[%d] has [%d] hashitem\n",
 205                         hash_body->hashname, hashent,
 206                         hash_body->lchb_hash_tables[hashent].lhb_item_count);
 207 #endif
 208         hop->lustre_hash_object_refcount_get(actual_hnode);
 209
 210         spin_unlock(&bucket->lhb_lock);
 211
 212         RETURN(0);
 213 }
 214 EXPORT_SYMBOL(lustre_hash_additem);
 215
 216
 217 /*
 218  * this version of delitem will delete a hashitem with given @key,
 219  * we need to search the <@key, @value> in hashbucket with @key,
 220  * if match, the hashitem will be delete.
 221  * we have a no-search version of delitem, it will directly delete a hashitem,
 222  * doesn't need to search it in hashtables, so it is a O(1) delete.
 223  */
 224 int lustre_hash_delitem_by_key(struct lustre_class_hash_body *hash_body,
 225                                void *key)
 226 {
 227         int hashent ;
 228         struct hlist_node * hash_item;
 229         struct lustre_hash_bucket *bucket = NULL;
 230         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 231         int retval = 0;
 232         ENTRY;
 233
 234         hashent = hop->lustre_hashfn(hash_body, key);
 235
 236         /* first, lock the hashbucket */
 237         bucket = &hash_body->lchb_hash_tables[hashent];
 238         spin_lock(&bucket->lhb_lock);
 239
 240         /* get the hash_item from hash_bucket */
 241         hash_item = lustre_hash_getitem_in_bucket_nolock(hash_body, hashent,
 242                                                          key);
 243
 244         if (hash_item == NULL) {
 245                 RETURN(-ENOENT);
 246         }
 247
 248         /* call delitem_nolock() to delete the hash_item */
 249         retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
 250
 251         spin_unlock(&bucket->lhb_lock);
 252
 253         RETURN(retval);
 254 }
 255 EXPORT_SYMBOL(lustre_hash_delitem_by_key);
 256
 257 /*
 258  * the O(1) version of delete hash item,
 259  * it will directly delete the hashitem with given @hash_item,
 260  * the parameter @key used to get the relation hash bucket and lock it.
 261  */
 262 int lustre_hash_delitem(struct lustre_class_hash_body *hash_body,
 263                         void *key, struct hlist_node * hash_item)
 264 {
 265         int hashent = 0;
 266         int retval = 0;
 267         struct lustre_hash_bucket *bucket = NULL;
 268         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 269         ENTRY;
 270
 271         hashent = hop->lustre_hashfn(hash_body, key);
 272
 273         bucket = &hash_body->lchb_hash_tables[hashent];
 274         spin_lock(&bucket->lhb_lock);
 275
 276         /* call delitem_nolock() to delete the hash_item */
 277         retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
 278
 279         spin_unlock(&bucket->lhb_lock);
 280
 281         RETURN(retval);
 282 }
 283 EXPORT_SYMBOL(lustre_hash_delitem);
 284
 285 void * lustre_hash_get_object_by_key(struct lustre_class_hash_body *hash_body,
 286                                      void *key)
 287 {
 288         int hashent ;
 289         struct hlist_node * hash_item_hnode = NULL;
 290         void * obj_value = NULL;
 291         struct lustre_hash_bucket *bucket = NULL;
 292         struct lustre_hash_operations * hop = hash_body->lchb_hash_operations;
 293         ENTRY;
 294
 295         /* get the hash value from the given item */
 296         hashent = hop->lustre_hashfn(hash_body, key);
 297
 298         bucket = &hash_body->lchb_hash_tables[hashent];
 299         spin_lock(&bucket->lhb_lock); /* lock the bucket */
 300
 301         hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
 302                                                                hashent, key);
 303
 304         if (hash_item_hnode == NULL) {
 305                 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
 306                 RETURN(NULL);
 307         }
 308
 309         obj_value = hop->lustre_hash_object_refcount_get(hash_item_hnode);
 310         spin_unlock(&bucket->lhb_lock); /* lock the bucket */
 311
 312         RETURN(obj_value);
 313 }
 314 EXPORT_SYMBOL(lustre_hash_get_object_by_key);
 315
 316 /*
 317  * define (uuid <-> export) hash operations and function define
 318  */
 319
 320 /* define the uuid hash operations */
 321 struct lustre_hash_operations uuid_hash_operations = {
 322         .lustre_hashfn = uuid_hashfn,
 323         .lustre_hash_key_compare = uuid_hash_key_compare,
 324         .lustre_hash_object_refcount_get = uuid_export_refcount_get,
 325         .lustre_hash_object_refcount_put = uuid_export_refcount_put,
 326 };
 327
 328 /* string hashing using djb2 hash algorithm */
 329 __u32 uuid_hashfn(struct lustre_class_hash_body *hash_body,  void * key)
 330 {
 331         __u32 hash = 5381;
 332         struct obd_uuid * uuid_key = NULL;
 333         int c;
 334         char *ptr = NULL;
 335
 336         LASSERT(key != NULL);
 337
 338         uuid_key = (struct obd_uuid*)key;
 339         ptr = uuid_key->uuid;
 340
 341         while ((c = *ptr++)) {
 342                 hash = hash * 33 + c;
 343         }
 344
 345         hash &= (hash_body->lchb_hash_max_size - 1);
 346
 347         RETURN(hash);
 348 }
 349
 350 int uuid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
 351 {
 352         struct obd_export *export = NULL;
 353         struct obd_uuid *uuid_key = NULL, *compared_uuid = NULL;
 354
 355         LASSERT( key != NULL);
 356
 357         uuid_key = (struct obd_uuid*)key;
 358
 359         export = hlist_entry(compared_hnode, struct obd_export, exp_uuid_hash);
 360
 361         compared_uuid = &export->exp_client_uuid;
 362
 363         RETURN(obd_uuid_equals(uuid_key, compared_uuid));
 364 }
 365
 366 void * uuid_export_refcount_get(struct hlist_node * actual_hnode)
 367 {
 368         struct obd_export *export = NULL;
 369
 370         LASSERT(actual_hnode != NULL);
 371
 372         export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
 373
 374         LASSERT(export != NULL);
 375
 376         class_export_get(export);
 377
 378         RETURN(export);
 379 }
 380
 381 void uuid_export_refcount_put(struct hlist_node * actual_hnode)
 382 {
 383         struct obd_export *export = NULL;
 384
 385         LASSERT(actual_hnode != NULL);
 386
 387         export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
 388
 389         LASSERT(export != NULL);
 390
 391         class_export_put(export);
 392 }
 393
 394 /*
 395  * define (nid <-> export) hash operations and function define
 396  */
 397
 398 /* define the nid hash operations */
 399 struct lustre_hash_operations nid_hash_operations = {
 400         .lustre_hashfn = nid_hashfn,
 401         .lustre_hash_key_compare = nid_hash_key_compare,
 402         .lustre_hash_object_refcount_get = nid_export_refcount_get,
 403         .lustre_hash_object_refcount_put = nid_export_refcount_put,
 404 };
 405
 406 /* string hashing using djb2 hash algorithm */
 407 __u32 nid_hashfn(struct lustre_class_hash_body *hash_body,  void * key)
 408 {
 409         __u32 hash = 5381;
 410         lnet_nid_t *nid_key = NULL;
 411         int c;
 412         char *ptr = NULL;
 413
 414         LASSERT(key != NULL);
 415
 416         nid_key = (lnet_nid_t*)key;
 417         ptr = libcfs_nid2str(*nid_key);
 418
 419         while ((c = *ptr++)) {
 420                 hash = hash * 33 + c;
 421         }
 422
 423         hash &= (hash_body->lchb_hash_max_size - 1);
 424
 425         RETURN(hash);
 426 }
 427
 428 int nid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
 429 {
 430         struct obd_export *export = NULL;
 431         lnet_nid_t *nid_key = NULL;
 432         int retval = 0;
 433
 434         LASSERT( key != NULL);
 435
 436         nid_key = (lnet_nid_t*)key;
 437
 438         export = hlist_entry(compared_hnode, struct obd_export, exp_nid_hash);
 439
 440         if (strcmp(obd_export_nid2str(export), libcfs_nid2str(*nid_key)) == 0)
 441                  retval = 1;
 442
 443         return retval;
 444 }
 445
 446 void * nid_export_refcount_get(struct hlist_node * actual_hnode)
 447 {
 448         struct obd_export *export = NULL;
 449
 450         LASSERT(actual_hnode != NULL);
 451
 452         export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
 453
 454         LASSERT(export != NULL);
 455
 456         class_export_get(export);
 457
 458         RETURN(export);
 459 }
 460
 461 void nid_export_refcount_put(struct hlist_node * actual_hnode)
 462 {
 463         struct obd_export *export = NULL;
 464
 465         LASSERT(actual_hnode != NULL);
 466
 467         export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
 468
 469         LASSERT(export != NULL);
 470
 471         class_export_put(export);
 472 }
 473
 474 /*
 475  * define (net_peer <-> connection) hash operations and function define
 476  */
 477
 478 /* define the conn hash operations */
 479 struct lustre_hash_operations conn_hash_operations = {
 480         .lustre_hashfn = conn_hashfn,
 481         .lustre_hash_key_compare = conn_hash_key_compare,
 482         .lustre_hash_object_refcount_get = conn_refcount_get,
 483         .lustre_hash_object_refcount_put = conn_refcount_put,
 484 };
 485 EXPORT_SYMBOL(conn_hash_operations);
 486
 487 /* string hashing using djb2 hash algorithm */
 488 __u32 conn_hashfn(struct lustre_class_hash_body *hash_body,  void * key)
 489 {
 490         __u32 hash = 5381;
 491         lnet_process_id_t *conn_key = NULL;
 492         char *ptr = NULL;
 493         int c;
 494
 495         LASSERT(key != NULL);
 496
 497         conn_key = (lnet_process_id_t*)key;
 498         ptr = libcfs_id2str(*conn_key);
 499
 500         while ((c = *ptr++)) {
 501                 hash = hash * 33 + c;
 502         }
 503
 504         hash &= (hash_body->lchb_hash_max_size - 1);
 505
 506         RETURN(hash);
 507 }
 508
 509 int conn_hash_key_compare(void *key, struct hlist_node *compared_hnode)
 510 {
 511         struct ptlrpc_connection *c = NULL;
 512         lnet_process_id_t *conn_key = NULL;
 513         int retval = 0;
 514
 515         LASSERT( key != NULL);
 516
 517         conn_key = (lnet_process_id_t*)key;
 518
 519         c = hlist_entry(compared_hnode, struct ptlrpc_connection, c_hash);
 520
 521         if (conn_key->nid == c->c_peer.nid &&
 522             conn_key->pid == c->c_peer.pid)
 523                  retval = 1;
 524
 525         return retval;
 526 }
 527
 528 void * conn_refcount_get(struct hlist_node * actual_hnode)
 529 {
 530         struct ptlrpc_connection *c = NULL;
 531
 532         LASSERT(actual_hnode != NULL);
 533
 534         c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
 535
 536         LASSERT(c != NULL);
 537
 538         atomic_inc(&c->c_refcount);
 539
 540         RETURN(c);
 541 }
 542
 543 void conn_refcount_put(struct hlist_node * actual_hnode)
 544 {
 545         struct ptlrpc_connection *c = NULL;
 546
 547         LASSERT(actual_hnode != NULL);
 548
 549         c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
 550
 551         LASSERT(c != NULL);
 552
 553         atomic_dec(&c->c_refcount);
 554 }
 555