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