xref: /freebsd/sys/dev/vmware/vmci/vmci_hashtable.c (revision fe6060f10f634930ff71b7c50291ddc610da2475) 
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 
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 		 * 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 
404 int
405 vmci_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 
434 bool
435 vmci_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 
465 static bool
466 vmci_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 
508 static int
509 hashtable_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 
560 void
561 vmci_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