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		/*
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
405int
406vmci_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
435bool
436vmci_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
466static bool
467vmci_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
509static int
510hashtable_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
561void
562vmci_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