xref: /freebsd/sys/dev/vmware/vmci/vmci_hashtable.c (revision 22cf89c938886d14f5796fc49f9f020c23ea8eaf) 
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 *
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
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
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
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
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 *
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 *
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
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
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
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
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
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
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
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