1 // SPDX-License-Identifier: CDDL-1.0
2 /*
3 * CDDL HEADER START
4 *
5 * The contents of this file are subject to the terms of the
6 * Common Development and Distribution License (the "License").
7 * You may not use this file except in compliance with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or https://opensource.org/licenses/CDDL-1.0.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27
28
29 #include <sys/zfs_context.h>
30 #include <sys/avl.h>
31 #include <sys/unique.h>
32
33 static avl_tree_t unique_avl;
34 static kmutex_t unique_mtx;
35
36 typedef struct unique {
37 avl_node_t un_link;
38 uint64_t un_value;
39 } unique_t;
40
41 #define UNIQUE_MASK ((1ULL << UNIQUE_BITS) - 1)
42
43 static int
unique_compare(const void * a,const void * b)44 unique_compare(const void *a, const void *b)
45 {
46 const unique_t *una = (const unique_t *)a;
47 const unique_t *unb = (const unique_t *)b;
48
49 return (TREE_CMP(una->un_value, unb->un_value));
50 }
51
52 void
unique_init(void)53 unique_init(void)
54 {
55 avl_create(&unique_avl, unique_compare,
56 sizeof (unique_t), offsetof(unique_t, un_link));
57 mutex_init(&unique_mtx, NULL, MUTEX_DEFAULT, NULL);
58 }
59
60 void
unique_fini(void)61 unique_fini(void)
62 {
63 avl_destroy(&unique_avl);
64 mutex_destroy(&unique_mtx);
65 }
66
67 uint64_t
unique_create(void)68 unique_create(void)
69 {
70 uint64_t value = unique_insert(0);
71 unique_remove(value);
72 return (value);
73 }
74
75 uint64_t
unique_insert(uint64_t value)76 unique_insert(uint64_t value)
77 {
78 avl_index_t idx;
79 unique_t *un = kmem_alloc(sizeof (unique_t), KM_SLEEP);
80
81 un->un_value = value;
82
83 mutex_enter(&unique_mtx);
84 while (un->un_value == 0 || un->un_value & ~UNIQUE_MASK ||
85 avl_find(&unique_avl, un, &idx)) {
86 mutex_exit(&unique_mtx);
87 (void) random_get_pseudo_bytes((void*)&un->un_value,
88 sizeof (un->un_value));
89 un->un_value &= UNIQUE_MASK;
90 mutex_enter(&unique_mtx);
91 }
92
93 avl_insert(&unique_avl, un, idx);
94 mutex_exit(&unique_mtx);
95
96 return (un->un_value);
97 }
98
99 void
unique_remove(uint64_t value)100 unique_remove(uint64_t value)
101 {
102 unique_t un_tofind;
103 unique_t *un;
104
105 un_tofind.un_value = value;
106 mutex_enter(&unique_mtx);
107 un = avl_find(&unique_avl, &un_tofind, NULL);
108 if (un != NULL) {
109 avl_remove(&unique_avl, un);
110 kmem_free(un, sizeof (unique_t));
111 }
112 mutex_exit(&unique_mtx);
113 }
114