sys/dev/vmware/vmci/vmci_hashtable.c

   1 /*-
   2  * Copyright (c) 2018 VMware, Inc.
   3  *
   4  * SPDX-License-Identifier: (BSD-2-Clause OR GPL-2.0)
   5  */
   6
   7 /* Implementation of the VMCI Hashtable. */
   8
   9 #include <sys/cdefs.h>
  10 __FBSDID("$FreeBSD$");
  11
  12 #include "vmci.h"
  13 #include "vmci_driver.h"
  14 #include "vmci_hashtable.h"
  15 #include "vmci_kernel_defs.h"
  16 #include "vmci_utils.h"
  17
  18 #define LGPFX   "vmci_hashtable: "
  19
  20 #define VMCI_HASHTABLE_HASH(_h, _sz)                                    \
  21         vmci_hash_id(VMCI_HANDLE_TO_RESOURCE_ID(_h), (_sz))
  22
  23 static int      hashtable_unlink_entry(struct vmci_hashtable *table,
  24                     struct vmci_hash_entry *entry);
  25 static bool     vmci_hashtable_entry_exists_locked(struct vmci_hashtable *table,
  26                     struct vmci_handle handle);
  27
  28 /*
  29  *------------------------------------------------------------------------------
  30  *
  31  * vmci_hashtable_create --
  32  *
  33  *     Creates a hashtable.
  34  *
  35  * Result:
  36  *     None.
  37  *
  38  * Side effects:
  39  *     None.
  40  *
  41  *------------------------------------------------------------------------------
  42  */
  43
  44 struct vmci_hashtable *
  45 vmci_hashtable_create(int size)
  46 {
  47         struct vmci_hashtable *table;
  48
  49         table = vmci_alloc_kernel_mem(sizeof(*table),
  50             VMCI_MEMORY_NORMAL);
  51         if (table == NULL)
  52                 return (NULL);
  53         memset(table, 0, sizeof(*table));
  54
  55         table->entries = vmci_alloc_kernel_mem(sizeof(*table->entries) * size,
  56             VMCI_MEMORY_NORMAL);
  57         if (table->entries == NULL) {
  58                 vmci_free_kernel_mem(table, sizeof(*table));
  59                 return (NULL);
  60         }
  61         memset(table->entries, 0, sizeof(*table->entries) * size);
  62         table->size = size;
  63         if (vmci_init_lock(&table->lock, "VMCI Hashtable lock") <
  64             VMCI_SUCCESS) {
  65                 vmci_free_kernel_mem(table->entries, sizeof(*table->entries) * size);
  66                 vmci_free_kernel_mem(table, sizeof(*table));
  67                 return (NULL);
  68         }
  69
  70         return (table);
  71 }
  72
  73 /*
  74  *------------------------------------------------------------------------------
  75  *
  76  * vmci_hashtable_destroy --
  77  *
  78  *     This function should be called at module exit time. We rely on the
  79  *     module ref count to insure that no one is accessing any hash table
  80  *     entries at this point in time. Hence we should be able to just remove
  81  *     all entries from the hash table.
  82  *
  83  * Result:
  84  *     None.
  85  *
  86  * Side effects:
  87  *     None.
  88  *
  89  *------------------------------------------------------------------------------
  90  */
  91
  92 void
  93 vmci_hashtable_destroy(struct vmci_hashtable *table)
  94 {
  95
  96         ASSERT(table);
  97
  98         vmci_grab_lock_bh(&table->lock);
  99         vmci_free_kernel_mem(table->entries, sizeof(*table->entries) *
 100             table->size);
 101         table->entries = NULL;
 102         vmci_release_lock_bh(&table->lock);
 103         vmci_cleanup_lock(&table->lock);
 104         vmci_free_kernel_mem(table, sizeof(*table));
 105 }
 106
 107 /*
 108  *------------------------------------------------------------------------------
 109  *
 110  * vmci_hashtable_init_entry --
 111  *
 112  *     Initializes a hash entry.
 113  *
 114  * Result:
 115  *     None.
 116  *
 117  * Side effects:
 118  *     None.
 119  *
 120  *------------------------------------------------------------------------------
 121  */
 122 void
 123 vmci_hashtable_init_entry(struct vmci_hash_entry *entry,
 124     struct vmci_handle handle)
 125 {
 126
 127         ASSERT(entry);
 128         entry->handle = handle;
 129         entry->ref_count = 0;
 130 }
 131
 132 /*
 133  *------------------------------------------------------------------------------
 134  *
 135  * vmci_hashtable_add_entry --
 136  *
 137  *     Adds an entry to the hashtable.
 138  *
 139  * Result:
 140  *     None.
 141  *
 142  * Side effects:
 143  *     None.
 144  *
 145  *------------------------------------------------------------------------------
 146  */
 147
 148 int
 149 vmci_hashtable_add_entry(struct vmci_hashtable *table,
 150     struct vmci_hash_entry *entry)
 151 {
 152         int idx;
 153
 154         ASSERT(entry);
 155         ASSERT(table);
 156
 157         vmci_grab_lock_bh(&table->lock);
 158
 159         if (vmci_hashtable_entry_exists_locked(table, entry->handle)) {
 160                 VMCI_LOG_DEBUG(LGPFX"Entry (handle=0x%x:0x%x) already "
 161                     "exists.\n", entry->handle.context,
 162                     entry->handle.resource);
 163                 vmci_release_lock_bh(&table->lock);
 164                 return (VMCI_ERROR_DUPLICATE_ENTRY);
 165         }
 166
 167         idx = VMCI_HASHTABLE_HASH(entry->handle, table->size);
 168         ASSERT(idx < table->size);
 169
 170         /* New entry is added to top/front of hash bucket. */
 171         entry->ref_count++;
 172         entry->next = table->entries[idx];
 173         table->entries[idx] = entry;
 174         vmci_release_lock_bh(&table->lock);
 175
 176         return (VMCI_SUCCESS);
 177 }
 178
 179 /*
 180  *------------------------------------------------------------------------------
 181  *
 182  * vmci_hashtable_remove_entry --
 183  *
 184  *     Removes an entry from the hashtable.
 185  *
 186  * Result:
 187  *     None.
 188  *
 189  * Side effects:
 190  *     None.
 191  *
 192  *------------------------------------------------------------------------------
 193  */
 194
 195 int
 196 vmci_hashtable_remove_entry(struct vmci_hashtable *table,
 197     struct vmci_hash_entry *entry)
 198 {
 199         int result;
 200
 201         ASSERT(table);
 202         ASSERT(entry);
 203
 204         vmci_grab_lock_bh(&table->lock);
 205
 206         /* First unlink the entry. */
 207         result = hashtable_unlink_entry(table, entry);
 208         if (result != VMCI_SUCCESS) {
 209                 /* We failed to find the entry. */
 210                 goto done;
 211         }
 212
 213         /* Decrement refcount and check if this is last reference. */
 214         entry->ref_count--;
 215         if (entry->ref_count == 0) {
 216                 result = VMCI_SUCCESS_ENTRY_DEAD;
 217                 goto done;
 218         }
 219
 220 done:
 221         vmci_release_lock_bh(&table->lock);
 222
 223         return (result);
 224 }
 225
 226 /*
 227  *------------------------------------------------------------------------------
 228  *
 229  * vmci_hashtable_get_entry_locked --
 230  *
 231  *     Looks up an entry in the hash table, that is already locked.
 232  *
 233  * Result:
 234  *     If the element is found, a pointer to the element is returned.
 235  *     Otherwise NULL is returned.
 236  *
 237  * Side effects:
 238  *     The reference count of the returned element is increased.
 239  *
 240  *------------------------------------------------------------------------------
 241  */
 242
 243 static struct vmci_hash_entry *
 244 vmci_hashtable_get_entry_locked(struct vmci_hashtable *table,
 245     struct vmci_handle handle)
 246 {
 247         struct vmci_hash_entry *cur = NULL;
 248         int idx;
 249
 250         ASSERT(!VMCI_HANDLE_EQUAL(handle, VMCI_INVALID_HANDLE));
 251         ASSERT(table);
 252
 253         idx = VMCI_HASHTABLE_HASH(handle, table->size);
 254
 255         cur = table->entries[idx];
 256         while (true) {
 257                 if (cur == NULL)
 258                         break;
 259
 260                 if (VMCI_HANDLE_TO_RESOURCE_ID(cur->handle) ==
 261                     VMCI_HANDLE_TO_RESOURCE_ID(handle)) {
 262                         if ((VMCI_HANDLE_TO_CONTEXT_ID(cur->handle) ==
 263                             VMCI_HANDLE_TO_CONTEXT_ID(handle)) ||
 264                             (VMCI_INVALID_ID == VMCI_HANDLE_TO_CONTEXT_ID(cur->handle))) {
 265                                 cur->ref_count++;
 266                                 break;
 267                         }
 268                 }
 269                 cur = cur->next;
 270         }
 271
 272         return (cur);
 273 }
 274
 275 /*
 276  *------------------------------------------------------------------------------
 277  *
 278  * vmci_hashtable_get_entry --
 279  *
 280  *     Gets an entry from the hashtable.
 281  *
 282  * Result:
 283  *     None.
 284  *
 285  * Side effects:
 286  *     None.
 287  *
 288  *------------------------------------------------------------------------------
 289  */
 290
 291 struct vmci_hash_entry *
 292 vmci_hashtable_get_entry(struct vmci_hashtable *table,
 293     struct vmci_handle handle)
 294 {
 295         struct vmci_hash_entry *entry;
 296
 297         if (VMCI_HANDLE_EQUAL(handle, VMCI_INVALID_HANDLE))
 298                 return (NULL);
 299
 300         ASSERT(table);
 301
 302         vmci_grab_lock_bh(&table->lock);
 303         entry = vmci_hashtable_get_entry_locked(table, handle);
 304         vmci_release_lock_bh(&table->lock);
 305
 306         return (entry);
 307 }
 308
 309 /*
 310  *------------------------------------------------------------------------------
 311  *
 312  * vmci_hashtable_hold_entry --
 313  *
 314  *     Hold the given entry. This will increment the entry's reference count.
 315  *     This is like a GetEntry() but without having to lookup the entry by
 316  *     handle.
 317  *
 318  * Result:
 319  *     None.
 320  *
 321  * Side effects:
 322  *     None.
 323  *
 324  *------------------------------------------------------------------------------
 325  */
 326
 327 void
 328 vmci_hashtable_hold_entry(struct vmci_hashtable *table,
 329     struct vmci_hash_entry *entry)
 330 {
 331
 332         ASSERT(table);
 333         ASSERT(entry);
 334
 335         vmci_grab_lock_bh(&table->lock);
 336         entry->ref_count++;
 337         vmci_release_lock_bh(&table->lock);
 338 }
 339
 340 /*
 341  *------------------------------------------------------------------------------
 342  *
 343  * vmci_hashtable_release_entry_locked --
 344  *
 345  *     Releases an element previously obtained with
 346  *     vmci_hashtable_get_entry_locked.
 347  *
 348  * Result:
 349  *     If the entry is removed from the hash table, VMCI_SUCCESS_ENTRY_DEAD
 350  *     is returned. Otherwise, VMCI_SUCCESS is returned.
 351  *
 352  * Side effects:
 353  *     The reference count of the entry is decreased and the entry is removed
 354  *     from the hash table on 0.
 355  *
 356  *------------------------------------------------------------------------------
 357  */
 358
 359 static int
 360 vmci_hashtable_release_entry_locked(struct vmci_hashtable *table,
 361     struct vmci_hash_entry *entry)
 362 {
 363         int result = VMCI_SUCCESS;
 364
 365         ASSERT(table);
 366         ASSERT(entry);
 367
 368         entry->ref_count--;
 369         /* Check if this is last reference and report if so. */
 370         if (entry->ref_count == 0) {
 371
 372                 /*
 373                  * Remove entry from hash table if not already removed. This
 374                  * could have happened already because VMCIHashTable_RemoveEntry
 375                  * was called to unlink it. We ignore if it is not found.
 376                  * Datagram handles will often have RemoveEntry called, whereas
 377                  * SharedMemory regions rely on ReleaseEntry to unlink the entry
 378                  * , since the creator does not call RemoveEntry when it
 379                  * detaches.
 380                  */
 381
 382                 hashtable_unlink_entry(table, entry);
 383                 result = VMCI_SUCCESS_ENTRY_DEAD;
 384         }
 385
 386         return (result);
 387 }
 388
 389 /*
 390  *------------------------------------------------------------------------------
 391  *
 392  * vmci_hashtable_release_entry --
 393  *
 394  *     Releases an entry from the hashtable.
 395  *
 396  * Result:
 397  *     None.
 398  *
 399  * Side effects:
 400  *     None.
 401  *
 402  *------------------------------------------------------------------------------
 403  */
 404
 405 int
 406 vmci_hashtable_release_entry(struct vmci_hashtable *table,
 407     struct vmci_hash_entry *entry)
 408 {
 409         int result;
 410
 411         ASSERT(table);
 412         vmci_grab_lock_bh(&table->lock);
 413         result = vmci_hashtable_release_entry_locked(table, entry);
 414         vmci_release_lock_bh(&table->lock);
 415
 416         return (result);
 417 }
 418
 419 /*
 420  *------------------------------------------------------------------------------
 421  *
 422  * vmci_hashtable_entry_exists --
 423  *
 424  *     Returns whether an entry exists in the hashtable
 425  *
 426  * Result:
 427  *     true if handle already in hashtable. false otherwise.
 428  *
 429  * Side effects:
 430  *     None.
 431  *
 432  *------------------------------------------------------------------------------
 433  */
 434
 435 bool
 436 vmci_hashtable_entry_exists(struct vmci_hashtable *table,
 437     struct vmci_handle handle)
 438 {
 439         bool exists;
 440
 441         ASSERT(table);
 442
 443         vmci_grab_lock_bh(&table->lock);
 444         exists = vmci_hashtable_entry_exists_locked(table, handle);
 445         vmci_release_lock_bh(&table->lock);
 446
 447         return (exists);
 448 }
 449
 450 /*
 451  *------------------------------------------------------------------------------
 452  *
 453  * vmci_hashtable_entry_exists_locked --
 454  *
 455  *     Unlocked version of vmci_hashtable_entry_exists.
 456  *
 457  * Result:
 458  *     true if handle already in hashtable. false otherwise.
 459  *
 460  * Side effects:
 461  *     None.
 462  *
 463  *------------------------------------------------------------------------------
 464  */
 465
 466 static bool
 467 vmci_hashtable_entry_exists_locked(struct vmci_hashtable *table,
 468     struct vmci_handle handle)
 469
 470 {
 471         struct vmci_hash_entry *entry;
 472         int idx;
 473
 474         ASSERT(table);
 475
 476         idx = VMCI_HASHTABLE_HASH(handle, table->size);
 477
 478         entry = table->entries[idx];
 479         while (entry) {
 480                 if (VMCI_HANDLE_TO_RESOURCE_ID(entry->handle) ==
 481                     VMCI_HANDLE_TO_RESOURCE_ID(handle))
 482                         if ((VMCI_HANDLE_TO_CONTEXT_ID(entry->handle) ==
 483                             VMCI_HANDLE_TO_CONTEXT_ID(handle)) ||
 484                             (VMCI_INVALID_ID == VMCI_HANDLE_TO_CONTEXT_ID(handle)) ||
 485                             (VMCI_INVALID_ID == VMCI_HANDLE_TO_CONTEXT_ID(entry->handle)))
 486                                 return (true);
 487                 entry = entry->next;
 488         }
 489
 490         return (false);
 491 }
 492
 493 /*
 494  *------------------------------------------------------------------------------
 495  *
 496  * hashtable_unlink_entry --
 497  *
 498  *     Assumes caller holds table lock.
 499  *
 500  * Result:
 501  *     None.
 502  *
 503  * Side effects:
 504  *     None.
 505  *
 506  *------------------------------------------------------------------------------
 507  */
 508
 509 static int
 510 hashtable_unlink_entry(struct vmci_hashtable *table,
 511     struct vmci_hash_entry *entry)
 512 {
 513         int result;
 514         struct vmci_hash_entry *prev, *cur;
 515         int idx;
 516
 517         idx = VMCI_HASHTABLE_HASH(entry->handle, table->size);
 518
 519         prev = NULL;
 520         cur = table->entries[idx];
 521         while (true) {
 522                 if (cur == NULL) {
 523                         result = VMCI_ERROR_NOT_FOUND;
 524                         break;
 525                 }
 526                 if (VMCI_HANDLE_EQUAL(cur->handle, entry->handle)) {
 527                         ASSERT(cur == entry);
 528
 529                         /* Remove entry and break. */
 530                         if (prev)
 531                                 prev->next = cur->next;
 532                         else
 533                                 table->entries[idx] = cur->next;
 534                         cur->next = NULL;
 535                         result = VMCI_SUCCESS;
 536                         break;
 537                 }
 538                 prev = cur;
 539                 cur = cur->next;
 540         }
 541         return (result);
 542 }
 543
 544 /*
 545  *------------------------------------------------------------------------------
 546  *
 547  * vmci_hashtable_sync --
 548  *
 549  *     Use this as a synchronization point when setting globals, for example,
 550  *     during device shutdown.
 551  *
 552  * Results:
 553  *     None.
 554  *
 555  * Side effects:
 556  *     None.
 557  *
 558  *------------------------------------------------------------------------------
 559  */
 560
 561 void
 562 vmci_hashtable_sync(struct vmci_hashtable *table)
 563 {
 564
 565         ASSERT(table);
 566         vmci_grab_lock_bh(&table->lock);
 567         vmci_release_lock_bh(&table->lock);
 568 }