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 *
vmci_hashtable_create(int size)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
vmci_hashtable_destroy(struct vmci_hashtable * table)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
vmci_hashtable_init_entry(struct vmci_hash_entry * entry,struct vmci_handle handle)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
vmci_hashtable_add_entry(struct vmci_hashtable * table,struct vmci_hash_entry * entry)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
vmci_hashtable_remove_entry(struct vmci_hashtable * table,struct vmci_hash_entry * entry)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 *
vmci_hashtable_get_entry_locked(struct vmci_hashtable * table,struct vmci_handle handle)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 *
vmci_hashtable_get_entry(struct vmci_hashtable * table,struct vmci_handle handle)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
vmci_hashtable_hold_entry(struct vmci_hashtable * table,struct vmci_hash_entry * entry)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
vmci_hashtable_release_entry_locked(struct vmci_hashtable * table,struct vmci_hash_entry * entry)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
vmci_hashtable_release_entry(struct vmci_hashtable * table,struct vmci_hash_entry * entry)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
vmci_hashtable_entry_exists(struct vmci_hashtable * table,struct vmci_handle handle)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
vmci_hashtable_entry_exists_locked(struct vmci_hashtable * table,struct vmci_handle handle)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
hashtable_unlink_entry(struct vmci_hashtable * table,struct vmci_hash_entry * entry)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
vmci_hashtable_sync(struct vmci_hashtable * table)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 }
569