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 2014 Joyent, Inc. All rights reserved. 14 */ 15 16 #include <sys/scsi/adapters/mpt_sas/mptsas_hash.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 #ifdef lint 24 extern refhash_link_t *obj_to_link(refhash_t *, void *); 25 extern void *link_to_obj(refhash_t *, refhash_link_t *); 26 extern void *obj_to_tag(refhash_t *, void *); 27 #else 28 #define obj_to_link(_h, _o) \ 29 ((refhash_link_t *)(((char *)(_o)) + (_h)->rh_link_off)) 30 #define link_to_obj(_h, _l) \ 31 ((void *)(((char *)(_l)) - (_h)->rh_link_off)) 32 #define obj_to_tag(_h, _o) \ 33 ((void *)(((char *)(_o)) + (_h)->rh_tag_off)) 34 #endif 35 36 refhash_t * 37 refhash_create(uint_t bucket_count, refhash_hash_f hash, 38 refhash_cmp_f cmp, refhash_dtor_f dtor, size_t obj_size, size_t link_off, 39 size_t tag_off, int km_flags) 40 { 41 refhash_t *hp; 42 uint_t i; 43 44 hp = kmem_alloc(sizeof (refhash_t), km_flags); 45 if (hp == NULL) 46 return (NULL); 47 hp->rh_buckets = kmem_zalloc(bucket_count * sizeof (list_t), km_flags); 48 if (hp->rh_buckets == NULL) { 49 kmem_free(hp, sizeof (refhash_t)); 50 return (NULL); 51 } 52 hp->rh_bucket_count = bucket_count; 53 54 for (i = 0; i < bucket_count; i++) { 55 list_create(&hp->rh_buckets[i], sizeof (refhash_link_t), 56 offsetof(refhash_link_t, rhl_chain_link)); 57 } 58 list_create(&hp->rh_objs, sizeof (refhash_link_t), 59 offsetof(refhash_link_t, rhl_global_link)); 60 61 hp->rh_obj_size = obj_size; 62 hp->rh_link_off = link_off; 63 hp->rh_tag_off = tag_off; 64 hp->rh_hash = hash; 65 hp->rh_cmp = cmp; 66 hp->rh_dtor = dtor; 67 68 return (hp); 69 } 70 71 void 72 refhash_destroy(refhash_t *hp) 73 { 74 ASSERT(list_is_empty(&hp->rh_objs)); 75 76 kmem_free(hp->rh_buckets, hp->rh_bucket_count * sizeof (list_t)); 77 kmem_free(hp, sizeof (refhash_t)); 78 } 79 80 void 81 refhash_insert(refhash_t *hp, void *op) 82 { 83 uint_t bucket; 84 refhash_link_t *lp = obj_to_link(hp, op); 85 86 bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count; 87 list_link_init(&lp->rhl_chain_link); 88 list_link_init(&lp->rhl_global_link); 89 lp->rhl_flags = 0; 90 lp->rhl_refcnt = 0; 91 list_insert_tail(&hp->rh_buckets[bucket], lp); 92 list_insert_tail(&hp->rh_objs, lp); 93 } 94 95 static void 96 refhash_delete(refhash_t *hp, void *op) 97 { 98 refhash_link_t *lp = obj_to_link(hp, op); 99 uint_t bucket; 100 101 bucket = hp->rh_hash(obj_to_tag(hp, op)) % hp->rh_bucket_count; 102 list_remove(&hp->rh_buckets[bucket], lp); 103 list_remove(&hp->rh_objs, lp); 104 hp->rh_dtor(op); 105 } 106 107 void 108 refhash_remove(refhash_t *hp, void *op) 109 { 110 refhash_link_t *lp = obj_to_link(hp, op); 111 112 if (lp->rhl_refcnt > 0) { 113 lp->rhl_flags |= RHL_F_DEAD; 114 } else { 115 refhash_delete(hp, op); 116 } 117 } 118 119 void * 120 refhash_lookup(refhash_t *hp, const void *tp) 121 { 122 uint_t bucket; 123 refhash_link_t *lp; 124 void *op; 125 126 bucket = hp->rh_hash(tp) % hp->rh_bucket_count; 127 for (lp = list_head(&hp->rh_buckets[bucket]); lp != NULL; 128 lp = list_next(&hp->rh_buckets[bucket], lp)) { 129 op = link_to_obj(hp, lp); 130 if (hp->rh_cmp(obj_to_tag(hp, op), tp) == 0 && 131 !(lp->rhl_flags & RHL_F_DEAD)) { 132 return (op); 133 } 134 } 135 136 return (NULL); 137 } 138 139 void * 140 refhash_linear_search(refhash_t *hp, refhash_eval_f eval, void *arg) 141 { 142 void *op; 143 refhash_link_t *lp; 144 145 for (lp = list_head(&hp->rh_objs); lp != NULL; 146 lp = list_next(&hp->rh_objs, lp)) { 147 op = link_to_obj(hp, lp); 148 if (eval(op, arg) == 0) 149 return (op); 150 } 151 152 return (NULL); 153 } 154 155 void 156 refhash_hold(refhash_t *hp, void *op) 157 { 158 refhash_link_t *lp = obj_to_link(hp, op); 159 160 ++lp->rhl_refcnt; 161 } 162 163 void 164 refhash_rele(refhash_t *hp, void *op) 165 { 166 refhash_link_t *lp = obj_to_link(hp, op); 167 168 ASSERT(lp->rhl_refcnt > 0); 169 170 if (--lp->rhl_refcnt == 0 && (lp->rhl_flags & RHL_F_DEAD)) 171 refhash_remove(hp, op); 172 } 173 174 void * 175 refhash_first(refhash_t *hp) 176 { 177 refhash_link_t *lp; 178 179 lp = list_head(&hp->rh_objs); 180 if (lp == NULL) 181 return (NULL); 182 183 ++lp->rhl_refcnt; 184 185 return (link_to_obj(hp, lp)); 186 } 187 188 void * 189 refhash_next(refhash_t *hp, void *op) 190 { 191 refhash_link_t *lp; 192 193 lp = obj_to_link(hp, op); 194 while ((lp = list_next(&hp->rh_objs, lp)) != NULL) { 195 if (!(lp->rhl_flags & RHL_F_DEAD)) 196 break; 197 } 198 199 refhash_rele(hp, op); 200 if (lp == NULL) 201 return (NULL); 202 203 ++lp->rhl_refcnt; 204 205 return (link_to_obj(hp, lp)); 206 } 207 208 boolean_t 209 refhash_obj_valid(refhash_t *hp, const void *op) 210 { 211 /* LINTED - E_ARG_INCOMPATIBLE_WITH_ARG_L */ 212 const refhash_link_t *lp = obj_to_link(hp, op); 213 214 return ((lp->rhl_flags & RHL_F_DEAD) != 0); 215 } 216