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
21static int	hashtable_unlink_entry(struct vmci_hashtable *table,
22		    struct vmci_hash_entry *entry);
23static 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
42struct vmci_hashtable *
43vmci_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
90void
91vmci_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 */
120void
121vmci_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
146int
147vmci_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
193int
194vmci_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
218done:
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
241static struct vmci_hash_entry *
242vmci_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
289struct vmci_hash_entry *
290vmci_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
325void
326vmci_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
357static int
358vmci_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
402int
403vmci_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
432bool
433vmci_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
463static bool
464vmci_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
506static int
507hashtable_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
558void
559vmci_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