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         LASSERT(hlist_unhashed(actual_hnode));
 148         hashent = hop->lustre_hashfn(hash_body, key);
 149
 150         /* get the hash-bucket and lock it */
 151         bucket = &hash_body->lchb_hash_tables[hashent];
 152         spin_lock(&bucket->lhb_lock);
 153
 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);
 157
 158                 CWARN("Already found the key in hash [%s]\n",
 159                       hash_body->hashname);
 160                 RETURN(-EALREADY);
 161         }
 162
 163         hlist_add_head(actual_hnode, &(bucket->lhb_head));
 164
 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);
 171 #endif
 172         hop->lustre_hash_object_refcount_get(actual_hnode);
 173
 174         spin_unlock(&bucket->lhb_lock);
 175
 176         RETURN(0);
 177 }
 178 EXPORT_SYMBOL(lustre_hash_additem_unique);
 179
 180 /*
 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
 185  */
 186 int lustre_hash_additem(struct lustre_class_hash_body *hash_body, void *key,
 187                          struct hlist_node *actual_hnode)
 188 {
 189         int hashent;
 190         struct lustre_hash_bucket *bucket = NULL;
 191         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 192         ENTRY;
 193
 194         LASSERT(hlist_unhashed(actual_hnode));
 195
 196         hashent = hop->lustre_hashfn(hash_body, key);
 197
 198         /* get the hashbucket and lock it */
 199         bucket = &hash_body->lchb_hash_tables[hashent];
 200         spin_lock(&bucket->lhb_lock);
 201
 202         hlist_add_head(actual_hnode, &(bucket->lhb_head));
 203
 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);
 210 #endif
 211         hop->lustre_hash_object_refcount_get(actual_hnode);
 212
 213         spin_unlock(&bucket->lhb_lock);
 214
 215         RETURN(0);
 216 }
 217 EXPORT_SYMBOL(lustre_hash_additem);
 218
 219
 220 /*
 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.
 226  */
 227 int lustre_hash_delitem_by_key(struct lustre_class_hash_body *hash_body,
 228                                void *key)
 229 {
 230         int hashent ;
 231         struct hlist_node * hash_item;
 232         struct lustre_hash_bucket *bucket = NULL;
 233         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 234         int retval = 0;
 235         ENTRY;
 236
 237         hashent = hop->lustre_hashfn(hash_body, key);
 238
 239         /* first, lock the hashbucket */
 240         bucket = &hash_body->lchb_hash_tables[hashent];
 241         spin_lock(&bucket->lhb_lock);
 242
 243         /* get the hash_item from hash_bucket */
 244         hash_item = lustre_hash_getitem_in_bucket_nolock(hash_body, hashent,
 245                                                          key);
 246
 247         if (hash_item == NULL) {
 248                 spin_unlock(&bucket->lhb_lock);
 249                 RETURN(-ENOENT);
 250         }
 251
 252         /* call delitem_nolock() to delete the hash_item */
 253         retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
 254
 255         spin_unlock(&bucket->lhb_lock);
 256
 257         RETURN(retval);
 258 }
 259 EXPORT_SYMBOL(lustre_hash_delitem_by_key);
 260
 261 /*
 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.
 265  */
 266 int lustre_hash_delitem(struct lustre_class_hash_body *hash_body,
 267                         void *key, struct hlist_node * hash_item)
 268 {
 269         int hashent = 0;
 270         int retval = 0;
 271         struct lustre_hash_bucket *bucket = NULL;
 272         struct lustre_hash_operations *hop = hash_body->lchb_hash_operations;
 273         ENTRY;
 274
 275         hashent = hop->lustre_hashfn(hash_body, key);
 276
 277         bucket = &hash_body->lchb_hash_tables[hashent];
 278         spin_lock(&bucket->lhb_lock);
 279
 280         /* call delitem_nolock() to delete the hash_item */
 281         retval = lustre_hash_delitem_nolock(hash_body, hashent, hash_item);
 282
 283         spin_unlock(&bucket->lhb_lock);
 284
 285         RETURN(retval);
 286 }
 287 EXPORT_SYMBOL(lustre_hash_delitem);
 288
 289 void * lustre_hash_get_object_by_key(struct lustre_class_hash_body *hash_body,
 290                                      void *key)
 291 {
 292         int hashent ;
 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;
 297         ENTRY;
 298
 299         /* get the hash value from the given item */
 300         hashent = hop->lustre_hashfn(hash_body, key);
 301
 302         bucket = &hash_body->lchb_hash_tables[hashent];
 303         spin_lock(&bucket->lhb_lock); /* lock the bucket */
 304
 305         hash_item_hnode = lustre_hash_getitem_in_bucket_nolock(hash_body,
 306                                                                hashent, key);
 307
 308         if (hash_item_hnode == NULL) {
 309                 spin_unlock(&bucket->lhb_lock); /* lock the bucket */
 310                 RETURN(NULL);
 311         }
 312
 313         obj_value = hop->lustre_hash_object_refcount_get(hash_item_hnode);
 314         spin_unlock(&bucket->lhb_lock); /* lock the bucket */
 315
 316         RETURN(obj_value);
 317 }
 318 EXPORT_SYMBOL(lustre_hash_get_object_by_key);
 319
 320 /*
 321  * define (uuid <-> export) hash operations and function define
 322  */
 323
 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,
 330 };
 331
 332 /* string hashing using djb2 hash algorithm */
 333 __u32 uuid_hashfn(struct lustre_class_hash_body *hash_body,  void * key)
 334 {
 335         __u32 hash = 5381;
 336         struct obd_uuid * uuid_key = NULL;
 337         int c;
 338         char *ptr = NULL;
 339
 340         LASSERT(key != NULL);
 341
 342         uuid_key = (struct obd_uuid*)key;
 343         ptr = uuid_key->uuid;
 344
 345         while ((c = *ptr++)) {
 346                 hash = hash * 33 + c;
 347         }
 348
 349         hash &= (hash_body->lchb_hash_max_size - 1);
 350
 351         RETURN(hash);
 352 }
 353
 354 /* Note, it is impossible to find an export that is in failed state with
 355  * this function */
 356 int uuid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
 357 {
 358         struct obd_export *export = NULL;
 359         struct obd_uuid *uuid_key = NULL, *compared_uuid = NULL;
 360
 361         LASSERT( key != NULL);
 362
 363         uuid_key = (struct obd_uuid*)key;
 364
 365         export = hlist_entry(compared_hnode, struct obd_export, exp_uuid_hash);
 366
 367         compared_uuid = &export->exp_client_uuid;
 368
 369         RETURN(obd_uuid_equals(uuid_key, compared_uuid) &&
 370                !export->exp_failed);
 371 }
 372
 373 void * uuid_export_refcount_get(struct hlist_node * actual_hnode)
 374 {
 375         struct obd_export *export = NULL;
 376
 377         LASSERT(actual_hnode != NULL);
 378
 379         export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
 380
 381         LASSERT(export != NULL);
 382
 383         class_export_get(export);
 384
 385         RETURN(export);
 386 }
 387
 388 void uuid_export_refcount_put(struct hlist_node * actual_hnode)
 389 {
 390         struct obd_export *export = NULL;
 391
 392         LASSERT(actual_hnode != NULL);
 393
 394         export = hlist_entry(actual_hnode, struct obd_export, exp_uuid_hash);
 395
 396         LASSERT(export != NULL);
 397
 398         class_export_put(export);
 399 }
 400
 401 /*
 402  * define (nid <-> export) hash operations and function define
 403  */
 404
 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,
 411 };
 412
 413 /* string hashing using djb2 hash algorithm */
 414 __u32 nid_hashfn(struct lustre_class_hash_body *hash_body,  void * key)
 415 {
 416         __u32 hash = 5381;
 417         int i;
 418         char *ptr = key;
 419
 420         LASSERT(key != NULL);
 421
 422         for(i = 0 ; i < sizeof(lnet_nid_t) ; i ++)
 423                 hash = hash * 33 + ptr[i];
 424
 425         hash &= (hash_body->lchb_hash_max_size - 1);
 426
 427         RETURN(hash);
 428 }
 429
 430 /* Note, it is impossible to find an export that is in failed state with
 431  * this function */
 432 int nid_hash_key_compare(void *key, struct hlist_node *compared_hnode)
 433 {
 434         struct obd_export *export = NULL;
 435         lnet_nid_t *nid_key = NULL;
 436
 437         LASSERT( key != NULL);
 438
 439         nid_key = (lnet_nid_t*)key;
 440
 441         export = hlist_entry(compared_hnode, struct obd_export, exp_nid_hash);
 442
 443         return (export->exp_connection->c_peer.nid == *nid_key &&
 444                 !export->exp_failed);
 445 }
 446
 447 void *nid_export_refcount_get(struct hlist_node *actual_hnode)
 448 {
 449         struct obd_export *export = NULL;
 450
 451         LASSERT(actual_hnode != NULL);
 452
 453         export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
 454
 455         LASSERT(export != NULL);
 456
 457         class_export_get(export);
 458
 459         RETURN(export);
 460 }
 461
 462 void nid_export_refcount_put(struct hlist_node *actual_hnode)
 463 {
 464         struct obd_export *export = NULL;
 465
 466         LASSERT(actual_hnode != NULL);
 467
 468         export = hlist_entry(actual_hnode, struct obd_export, exp_nid_hash);
 469
 470         LASSERT(export != NULL);
 471
 472         class_export_put(export);
 473 }
 474
 475 /*
 476  * define (net_peer <-> connection) hash operations and function define
 477  */
 478
 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,
 485 };
 486 EXPORT_SYMBOL(conn_hash_operations);
 487
 488 /* string hashing using djb2 hash algorithm */
 489 __u32 conn_hashfn(struct lustre_class_hash_body *hash_body,  void * key)
 490 {
 491         __u32 hash = 5381;
 492         char *ptr = key;
 493         int i;
 494
 495         LASSERT(key != NULL);
 496
 497         for(i = 0 ; i < sizeof(lnet_process_id_t) ; i ++)
 498                 hash = hash * 33 + ptr[i];
 499
 500         hash &= (hash_body->lchb_hash_max_size - 1);
 501
 502         RETURN(hash);
 503 }
 504
 505 int conn_hash_key_compare(void *key, struct hlist_node *compared_hnode)
 506 {
 507         struct ptlrpc_connection *c = NULL;
 508         lnet_process_id_t *conn_key = NULL;
 509
 510         LASSERT( key != NULL);
 511
 512         conn_key = (lnet_process_id_t*)key;
 513
 514         c = hlist_entry(compared_hnode, struct ptlrpc_connection, c_hash);
 515
 516         return (conn_key->nid == c->c_peer.nid &&
 517                 conn_key->pid == c->c_peer.pid);
 518 }
 519
 520 void *conn_refcount_get(struct hlist_node *actual_hnode)
 521 {
 522         struct ptlrpc_connection *c = NULL;
 523
 524         LASSERT(actual_hnode != NULL);
 525
 526         c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
 527
 528         LASSERT(c != NULL);
 529
 530         atomic_inc(&c->c_refcount);
 531
 532         RETURN(c);
 533 }
 534
 535 void conn_refcount_put(struct hlist_node *actual_hnode)
 536 {
 537         struct ptlrpc_connection *c = NULL;
 538
 539         LASSERT(actual_hnode != NULL);
 540
 541         c = hlist_entry(actual_hnode, struct ptlrpc_connection, c_hash);
 542
 543         LASSERT(c != NULL);
 544
 545         atomic_dec(&c->c_refcount);
 546 }
 547