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
23static int	hashtable_unlink_entry(struct vmci_hashtable *table,
24		    struct vmci_hash_entry *entry);
25static 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
44struct vmci_hashtable *
45vmci_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
92void
93vmci_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 */
122void
123vmci_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
148int
149vmci_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
195int
196vmci_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
220done:
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
243static struct vmci_hash_entry *
244vmci_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
291struct vmci_hash_entry *
292vmci_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
327void
328vmci_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
359static int
360vmci_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
404int
405vmci_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
434bool
435vmci_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
465static bool
466vmci_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
508static int
509hashtable_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
560void
561vmci_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}
568