xref: /freebsd/sys/dev/vmware/vmci/vmci_hashtable.c (revision 8c302b2e) 
1 /*-
2  * Copyright (c) 2018 VMware, Inc. All Rights Reserved.
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 *
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
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
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
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
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 *
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 *
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
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
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
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
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
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
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
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