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