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