vmci_hashtable.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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                  * Remove entry from hash table if not already removed. This
  373                  * could have happened already because VMCIHashTable_RemoveEntry
  374                  * was called to unlink it. We ignore if it is not found.
  375                  * Datagram handles will often have RemoveEntry called, whereas
  376                  * SharedMemory regions rely on ReleaseEntry to unlink the entry
  377                  * , since the creator does not call RemoveEntry when it
  378                  * detaches.
  379                  */
  380 
  381                 hashtable_unlink_entry(table, entry);
  382                 result = VMCI_SUCCESS_ENTRY_DEAD;
  383         }
  384 
  385         return (result);
  386 }
  387 
  388 /*
  389  *------------------------------------------------------------------------------
  390  *
  391  * vmci_hashtable_release_entry --
  392  *
  393  *     Releases an entry from the hashtable.
  394  *
  395  * Result:
  396  *     None.
  397  *
  398  * Side effects:
  399  *     None.
  400  *
  401  *------------------------------------------------------------------------------
  402  */
  403 
  404 int
  405 vmci_hashtable_release_entry(struct vmci_hashtable *table,
  406     struct vmci_hash_entry *entry)
  407 {
  408         int result;
  409 
  410         ASSERT(table);
  411         vmci_grab_lock_bh(&table->lock);
  412         result = vmci_hashtable_release_entry_locked(table, entry);
  413         vmci_release_lock_bh(&table->lock);
  414 
  415         return (result);
  416 }
  417 
  418 /*
  419  *------------------------------------------------------------------------------
  420  *
  421  * vmci_hashtable_entry_exists --
  422  *
  423  *     Returns whether an entry exists in the hashtable
  424  *
  425  * Result:
  426  *     true if handle already in hashtable. false otherwise.
  427  *
  428  * Side effects:
  429  *     None.
  430  *
  431  *------------------------------------------------------------------------------
  432  */
  433 
  434 bool
  435 vmci_hashtable_entry_exists(struct vmci_hashtable *table,
  436     struct vmci_handle handle)
  437 {
  438         bool exists;
  439 
  440         ASSERT(table);
  441 
  442         vmci_grab_lock_bh(&table->lock);
  443         exists = vmci_hashtable_entry_exists_locked(table, handle);
  444         vmci_release_lock_bh(&table->lock);
  445 
  446         return (exists);
  447 }
  448 
  449 /*
  450  *------------------------------------------------------------------------------
  451  *
  452  * vmci_hashtable_entry_exists_locked --
  453  *
  454  *     Unlocked version of vmci_hashtable_entry_exists.
  455  *
  456  * Result:
  457  *     true if handle already in hashtable. false otherwise.
  458  *
  459  * Side effects:
  460  *     None.
  461  *
  462  *------------------------------------------------------------------------------
  463  */
  464 
  465 static bool
  466 vmci_hashtable_entry_exists_locked(struct vmci_hashtable *table,
  467     struct vmci_handle handle)
  468 
  469 {
  470         struct vmci_hash_entry *entry;
  471         int idx;
  472 
  473         ASSERT(table);
  474 
  475         idx = VMCI_HASHTABLE_HASH(handle, table->size);
  476 
  477         entry = table->entries[idx];
  478         while (entry) {
  479                 if (VMCI_HANDLE_TO_RESOURCE_ID(entry->handle) ==
  480                     VMCI_HANDLE_TO_RESOURCE_ID(handle))
  481                         if ((VMCI_HANDLE_TO_CONTEXT_ID(entry->handle) ==
  482                             VMCI_HANDLE_TO_CONTEXT_ID(handle)) ||
  483                             (VMCI_INVALID_ID == VMCI_HANDLE_TO_CONTEXT_ID(handle)) ||
  484                             (VMCI_INVALID_ID == VMCI_HANDLE_TO_CONTEXT_ID(entry->handle)))
  485                                 return (true);
  486                 entry = entry->next;
  487         }
  488 
  489         return (false);
  490 }
  491 
  492 /*
  493  *------------------------------------------------------------------------------
  494  *
  495  * hashtable_unlink_entry --
  496  *
  497  *     Assumes caller holds table lock.
  498  *
  499  * Result:
  500  *     None.
  501  *
  502  * Side effects:
  503  *     None.
  504  *
  505  *------------------------------------------------------------------------------
  506  */
  507 
  508 static int
  509 hashtable_unlink_entry(struct vmci_hashtable *table,
  510     struct vmci_hash_entry *entry)
  511 {
  512         int result;
  513         struct vmci_hash_entry *prev, *cur;
  514         int idx;
  515 
  516         idx = VMCI_HASHTABLE_HASH(entry->handle, table->size);
  517 
  518         prev = NULL;
  519         cur = table->entries[idx];
  520         while (true) {
  521                 if (cur == NULL) {
  522                         result = VMCI_ERROR_NOT_FOUND;
  523                         break;
  524                 }
  525                 if (VMCI_HANDLE_EQUAL(cur->handle, entry->handle)) {
  526                         ASSERT(cur == entry);
  527 
  528                         /* Remove entry and break. */
  529                         if (prev)
  530                                 prev->next = cur->next;
  531                         else
  532                                 table->entries[idx] = cur->next;
  533                         cur->next = NULL;
  534                         result = VMCI_SUCCESS;
  535                         break;
  536                 }
  537                 prev = cur;
  538                 cur = cur->next;
  539         }
  540         return (result);
  541 }
  542 
  543 /*
  544  *------------------------------------------------------------------------------
  545  *
  546  * vmci_hashtable_sync --
  547  *
  548  *     Use this as a synchronization point when setting globals, for example,
  549  *     during device shutdown.
  550  *
  551  * Results:
  552  *     None.
  553  *
  554  * Side effects:
  555  *     None.
  556  *
  557  *------------------------------------------------------------------------------
  558  */
  559 
  560 void
  561 vmci_hashtable_sync(struct vmci_hashtable *table)
  562 {
  563 
  564         ASSERT(table);
  565         vmci_grab_lock_bh(&table->lock);
  566         vmci_release_lock_bh(&table->lock);
  567 }
Cache object: d1eacd0e37251a7f7ba41b0cdf6ae5a8
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/dev/vmware/vmci/vmci_hashtable.c

FreeBSD/Linux Kernel Cross Reference
sys/dev/vmware/vmci/vmci_hashtable.c
