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