1 /* 2 * This file and its contents are supplied under the terms of the 3 * Common Development and Distribution License ("CDDL"), version 1.0. 4 * You may only use this file in accordance with the terms of version 5 * 1.0 of the CDDL. 6 * 7 * A full copy of the text of the CDDL should have accompanied this 8 * source. A copy of the CDDL is also available via the Internet at 9 * http://www.illumos.org/license/CDDL. 10 */ 11 12 /* 13 * Copyright 2015 Joyent, Inc. 14 */ 15 16 #include <sys/refhash.h> 17 #include <sys/sysmacros.h> 18 #include <sys/types.h> 19 #include <sys/kmem.h> 20 #include <sys/list.h> 21 #include <sys/ddi.h> 22 23 #define obj_to_link(_h, _o) \ 24 ((refhash_link_t *)(((char *)(_o)) + (_h)->rh_link_off)) 25 #define link_to_obj(_h, _l) \ 26 ((void *)(((char *)(_l)) - (_h)->rh_link_off)) 27 #define obj_to_tag(_h, _o) \ 28 ((void *)(((char *)(_o)) + (_h)->rh_tag_off)) 29 30 refhash_t * 31 refhash_create(uint_t bucket_count, refhash_hash_f hash, 32 refhash_cmp_f cmp, refhash_dtor_f dtor, size_t obj_size, size_t link_off, 33 size_t tag_off, int km_flags) 34 { 35 refhash_t *hp; 36 uint_t i; 37 38 hp = kmem_alloc(sizeof (refhash_t), km_flags); 39 if (hp == NULL) 40 return (NULL); 41 hp->rh_buckets = kmem_zalloc(bucket_count * sizeof (list_t), km_flags); 42 if (hp->rh_buckets == NULL) { 43 kmem_free(hp, sizeof (refhash_t)); 44 return (NULL); 45 } 46 hp->rh_bucket_count = bucket_count; 47 48 for (i = 0; i < bucket_count; i++) { 49 list_create(&hp->rh_buckets[i], sizeof (refhash_link_t), 50 offsetof(refhash_link_t, rhl_chain_link)); 51 } 52 list_create(&hp->rh_objs, sizeof (refhash_link_t), 53 offsetof(refhash_link_t, rhl_global_link)); 54 55 hp->rh_obj_size = obj_size; 56 hp->rh_link_off = link_off; 57 hp->rh_tag_off = tag_off; 58 hp->rh_hash = hash; 59 hp->rh_cmp = cmp; 60 hp->rh_dtor = dtor; 61 62 return (hp); 63 } 64 65 void 66 refhash_destroy(refhash_t *hp) 67 { 68 ASSERT(list_is_empty(&hp->rh_objs)); 69 70 kmem_free(hp->rh_buckets, hp->rh_bucket_count * sizeof (list_t)); 71 kmem_free(hp, sizeof (refhash_t)); 72 } 73 74 void 75 refhash_insert(refhash_t *hp, void *op) 76 { 77 uint_t bucket; 78 refhash_link_t *lp = obj_to_link(hp, op); 79 80 bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count; 81 list_link_init(&lp->rhl_chain_link); 82 list_link_init(&lp->rhl_global_link); 83 lp->rhl_flags = 0; 84 lp->rhl_refcnt = 0; 85 list_insert_tail(&hp->rh_buckets[bucket], lp); 86 list_insert_tail(&hp->rh_objs, lp); 87 } 88 89 static void 90 refhash_delete(refhash_t *hp, void *op) 91 { 92 refhash_link_t *lp = obj_to_link(hp, op); 93 uint_t bucket; 94 95 bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count; 96 list_remove(&hp->rh_buckets[bucket], lp); 97 list_remove(&hp->rh_objs, lp); 98 hp->rh_dtor(op); 99 } 100 101 void 102 refhash_remove(refhash_t *hp, void *op) 103 { 104 refhash_link_t *lp = obj_to_link(hp, op); 105 106 if (lp->rhl_refcnt > 0) { 107 lp->rhl_flags |= RHL_F_DEAD; 108 } else { 109 refhash_delete(hp, op); 110 } 111 } 112 113 void * 114 refhash_lookup(refhash_t *hp, const void *tp) 115 { 116 uint_t bucket; 117 refhash_link_t *lp; 118 void *op; 119 120 bucket = hp->rh_hash(tp) % hp->rh_bucket_count; 121 for (lp = list_head(&hp->rh_buckets[bucket]); lp != NULL; 122 lp = list_next(&hp->rh_buckets[bucket], lp)) { 123 op = link_to_obj(hp, lp); 124 if (hp->rh_cmp(obj_to_tag(hp, op), tp) == 0 && 125 !(lp->rhl_flags & RHL_F_DEAD)) { 126 return (op); 127 } 128 } 129 130 return (NULL); 131 } 132 133 void * 134 refhash_linear_search(refhash_t *hp, refhash_eval_f eval, void *arg) 135 { 136 void *op; 137 refhash_link_t *lp; 138 139 for (lp = list_head(&hp->rh_objs); lp != NULL; 140 lp = list_next(&hp->rh_objs, lp)) { 141 op = link_to_obj(hp, lp); 142 if (eval(op, arg) == 0) 143 return (op); 144 } 145 146 return (NULL); 147 } 148 149 void 150 refhash_hold(refhash_t *hp, void *op) 151 { 152 refhash_link_t *lp = obj_to_link(hp, op); 153 154 ++lp->rhl_refcnt; 155 } 156 157 void 158 refhash_rele(refhash_t *hp, void *op) 159 { 160 refhash_link_t *lp = obj_to_link(hp, op); 161 162 ASSERT(lp->rhl_refcnt > 0); 163 164 if (--lp->rhl_refcnt == 0 && (lp->rhl_flags & RHL_F_DEAD)) 165 refhash_remove(hp, op); 166 } 167 168 void * 169 refhash_first(refhash_t *hp) 170 { 171 refhash_link_t *lp; 172 173 lp = list_head(&hp->rh_objs); 174 if (lp == NULL) 175 return (NULL); 176 177 ++lp->rhl_refcnt; 178 179 return (link_to_obj(hp, lp)); 180 } 181 182 void * 183 refhash_next(refhash_t *hp, void *op) 184 { 185 refhash_link_t *lp; 186 187 lp = obj_to_link(hp, op); 188 while ((lp = list_next(&hp->rh_objs, lp)) != NULL) { 189 if (!(lp->rhl_flags & RHL_F_DEAD)) 190 break; 191 } 192 193 refhash_rele(hp, op); 194 if (lp == NULL) 195 return (NULL); 196 197 ++lp->rhl_refcnt; 198 199 return (link_to_obj(hp, lp)); 200 } 201 202 boolean_t 203 refhash_obj_valid(refhash_t *hp, const void *op) 204 { 205 const refhash_link_t *lp = obj_to_link(hp, op); 206 207 return ((lp->rhl_flags & RHL_F_DEAD) != 0); 208 } 209