Jason Evans | 0657f12 | 2011-03-18 17:56:14 -0700 | [diff] [blame] | 1 | #define JEMALLOC_RTREE_C_ |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 2 | #include "jemalloc/internal/jemalloc_internal.h" |
| 3 | |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 4 | static unsigned |
| 5 | hmin(unsigned ha, unsigned hb) |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 6 | { |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 7 | |
| 8 | return (ha < hb ? ha : hb); |
| 9 | } |
| 10 | |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 11 | /* |
| 12 | * Only the most significant bits of keys passed to rtree_{read,write}() are |
| 13 | * used. |
| 14 | */ |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 15 | bool |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 16 | rtree_new(rtree_t *rtree, unsigned bits) |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 17 | { |
| 18 | unsigned bits_in_leaf, height, i; |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 19 | |
Jason Evans | 6c460ad | 2016-03-22 17:54:35 -0700 | [diff] [blame] | 20 | assert(RTREE_HEIGHT_MAX == ((ZU(1) << (LG_SIZEOF_PTR+3)) / |
| 21 | RTREE_BITS_PER_LEVEL)); |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 22 | assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); |
| 23 | |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 24 | bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL |
| 25 | : (bits % RTREE_BITS_PER_LEVEL); |
Jason Evans | b954bc5 | 2014-01-02 17:36:38 -0800 | [diff] [blame] | 26 | if (bits > bits_in_leaf) { |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 27 | height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL; |
| 28 | if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits) |
Jason Evans | b954bc5 | 2014-01-02 17:36:38 -0800 | [diff] [blame] | 29 | height++; |
Jason Evans | b954bc5 | 2014-01-02 17:36:38 -0800 | [diff] [blame] | 30 | } else |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 31 | height = 1; |
| 32 | assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits); |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 33 | |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 34 | rtree->height = height; |
| 35 | |
| 36 | /* Root level. */ |
| 37 | rtree->levels[0].subtree = NULL; |
| 38 | rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL : |
| 39 | bits_in_leaf; |
| 40 | rtree->levels[0].cumbits = rtree->levels[0].bits; |
| 41 | /* Interior levels. */ |
| 42 | for (i = 1; i < height-1; i++) { |
| 43 | rtree->levels[i].subtree = NULL; |
| 44 | rtree->levels[i].bits = RTREE_BITS_PER_LEVEL; |
| 45 | rtree->levels[i].cumbits = rtree->levels[i-1].cumbits + |
| 46 | RTREE_BITS_PER_LEVEL; |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 47 | } |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 48 | /* Leaf level. */ |
| 49 | if (height > 1) { |
| 50 | rtree->levels[height-1].subtree = NULL; |
| 51 | rtree->levels[height-1].bits = bits_in_leaf; |
| 52 | rtree->levels[height-1].cumbits = bits; |
| 53 | } |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 54 | |
Jason Evans | 6f29a83 | 2016-06-02 18:43:10 -0700 | [diff] [blame^] | 55 | /* Compute lookup table to be used by rtree_[ctx_]start_level(). */ |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 56 | for (i = 0; i < RTREE_HEIGHT_MAX; i++) { |
| 57 | rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height - |
| 58 | 1); |
| 59 | } |
Jason Evans | 6f29a83 | 2016-06-02 18:43:10 -0700 | [diff] [blame^] | 60 | rtree->start_level[RTREE_HEIGHT_MAX] = 0; |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 61 | |
| 62 | return (false); |
Jason Evans | 2dbecf1 | 2010-09-05 10:35:13 -0700 | [diff] [blame] | 63 | } |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 64 | |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 65 | #ifdef JEMALLOC_JET |
| 66 | #undef rtree_node_alloc |
| 67 | #define rtree_node_alloc JEMALLOC_N(rtree_node_alloc_impl) |
| 68 | #endif |
| 69 | static rtree_elm_t * |
| 70 | rtree_node_alloc(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) |
| 71 | { |
| 72 | |
| 73 | return ((rtree_elm_t *)base_alloc(tsdn, nelms * sizeof(rtree_elm_t))); |
| 74 | } |
| 75 | #ifdef JEMALLOC_JET |
| 76 | #undef rtree_node_alloc |
| 77 | #define rtree_node_alloc JEMALLOC_N(rtree_node_alloc) |
| 78 | rtree_node_alloc_t *rtree_node_alloc = JEMALLOC_N(rtree_node_alloc_impl); |
| 79 | #endif |
| 80 | |
| 81 | #ifdef JEMALLOC_JET |
| 82 | #undef rtree_node_dalloc |
| 83 | #define rtree_node_dalloc JEMALLOC_N(rtree_node_dalloc_impl) |
| 84 | #endif |
| 85 | UNUSED static void |
| 86 | rtree_node_dalloc(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *node) |
| 87 | { |
| 88 | |
| 89 | /* Nodes are never deleted during normal operation. */ |
| 90 | not_reached(); |
| 91 | } |
| 92 | #ifdef JEMALLOC_JET |
| 93 | #undef rtree_node_dalloc |
| 94 | #define rtree_node_dalloc JEMALLOC_N(rtree_node_dalloc) |
| 95 | rtree_node_dalloc_t *rtree_node_dalloc = JEMALLOC_N(rtree_node_dalloc_impl); |
| 96 | #endif |
| 97 | |
| 98 | #ifdef JEMALLOC_JET |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 99 | static void |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 100 | rtree_delete_subtree(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *node, |
| 101 | unsigned level) |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 102 | { |
| 103 | |
Jason Evans | fbd8d77 | 2015-03-11 23:14:50 -0700 | [diff] [blame] | 104 | if (level + 1 < rtree->height) { |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 105 | size_t nchildren, i; |
| 106 | |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 107 | nchildren = ZU(1) << rtree->levels[level].bits; |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 108 | for (i = 0; i < nchildren; i++) { |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 109 | rtree_elm_t *child = node[i].child; |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 110 | if (child != NULL) { |
| 111 | rtree_delete_subtree(tsdn, rtree, child, level + |
| 112 | 1); |
| 113 | } |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 114 | } |
| 115 | } |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 116 | rtree_node_dalloc(tsdn, rtree, node); |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 117 | } |
| 118 | |
| 119 | void |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 120 | rtree_delete(tsdn_t *tsdn, rtree_t *rtree) |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 121 | { |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 122 | unsigned i; |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 123 | |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 124 | for (i = 0; i < rtree->height; i++) { |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 125 | rtree_elm_t *subtree = rtree->levels[i].subtree; |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 126 | if (subtree != NULL) |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 127 | rtree_delete_subtree(tsdn, rtree, subtree, i); |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 128 | } |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 129 | } |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 130 | #endif |
Jason Evans | b980cc7 | 2014-01-02 16:08:28 -0800 | [diff] [blame] | 131 | |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 132 | static rtree_elm_t * |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 133 | rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level, |
| 134 | rtree_elm_t **elmp) |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 135 | { |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 136 | rtree_elm_t *node; |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 137 | |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 138 | if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) { |
| 139 | /* |
| 140 | * Another thread is already in the process of initializing. |
| 141 | * Spin-wait until initialization is complete. |
| 142 | */ |
| 143 | do { |
| 144 | CPU_SPINWAIT; |
| 145 | node = atomic_read_p((void **)elmp); |
| 146 | } while (node == RTREE_NODE_INITIALIZING); |
| 147 | } else { |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 148 | node = rtree_node_alloc(tsdn, rtree, ZU(1) << |
| 149 | rtree->levels[level].bits); |
Jason Evans | 8d0e04d | 2015-01-30 22:54:08 -0800 | [diff] [blame] | 150 | if (node == NULL) |
| 151 | return (NULL); |
| 152 | atomic_write_p((void **)elmp, node); |
| 153 | } |
| 154 | |
| 155 | return (node); |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 156 | } |
| 157 | |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 158 | rtree_elm_t * |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 159 | rtree_subtree_read_hard(tsdn_t *tsdn, rtree_t *rtree, unsigned level) |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 160 | { |
| 161 | |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 162 | return (rtree_node_init(tsdn, rtree, level, |
| 163 | &rtree->levels[level].subtree)); |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 164 | } |
| 165 | |
Jason Evans | 2d2b4e9 | 2016-03-28 03:06:35 -0700 | [diff] [blame] | 166 | rtree_elm_t * |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 167 | rtree_child_read_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *elm, |
| 168 | unsigned level) |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 169 | { |
| 170 | |
Jason Evans | 8c9be3e | 2016-04-16 00:36:11 -0700 | [diff] [blame] | 171 | return (rtree_node_init(tsdn, rtree, level, &elm->child)); |
Jason Evans | 20f1fc9 | 2012-10-09 14:46:22 -0700 | [diff] [blame] | 172 | } |
Jason Evans | e75e9be | 2016-04-17 12:55:10 -0700 | [diff] [blame] | 173 | |
| 174 | static int |
| 175 | rtree_elm_witness_comp(const witness_t *a, void *oa, const witness_t *b, |
| 176 | void *ob) |
| 177 | { |
| 178 | uintptr_t ka = (uintptr_t)oa; |
| 179 | uintptr_t kb = (uintptr_t)ob; |
| 180 | |
| 181 | assert(ka != 0); |
| 182 | assert(kb != 0); |
| 183 | |
| 184 | return ((ka > kb) - (ka < kb)); |
| 185 | } |
| 186 | |
| 187 | static witness_t * |
| 188 | rtree_elm_witness_alloc(tsd_t *tsd, uintptr_t key, const rtree_elm_t *elm) |
| 189 | { |
| 190 | witness_t *witness; |
| 191 | size_t i; |
| 192 | rtree_elm_witness_tsd_t *witnesses = tsd_rtree_elm_witnessesp_get(tsd); |
| 193 | |
| 194 | /* Iterate over entire array to detect double allocation attempts. */ |
| 195 | witness = NULL; |
| 196 | for (i = 0; i < sizeof(rtree_elm_witness_tsd_t) / sizeof(witness_t); |
| 197 | i++) { |
| 198 | rtree_elm_witness_t *rew = &witnesses->witnesses[i]; |
| 199 | |
| 200 | assert(rew->elm != elm); |
| 201 | if (rew->elm == NULL && witness == NULL) { |
| 202 | rew->elm = elm; |
| 203 | witness = &rew->witness; |
| 204 | witness_init(witness, "rtree_elm", |
| 205 | WITNESS_RANK_RTREE_ELM, rtree_elm_witness_comp, |
| 206 | (void *)key); |
| 207 | } |
| 208 | } |
| 209 | assert(witness != NULL); |
| 210 | return (witness); |
| 211 | } |
| 212 | |
| 213 | static witness_t * |
| 214 | rtree_elm_witness_find(tsd_t *tsd, const rtree_elm_t *elm) |
| 215 | { |
| 216 | size_t i; |
| 217 | rtree_elm_witness_tsd_t *witnesses = tsd_rtree_elm_witnessesp_get(tsd); |
| 218 | |
| 219 | for (i = 0; i < sizeof(rtree_elm_witness_tsd_t) / sizeof(witness_t); |
| 220 | i++) { |
| 221 | rtree_elm_witness_t *rew = &witnesses->witnesses[i]; |
| 222 | |
| 223 | if (rew->elm == elm) |
| 224 | return (&rew->witness); |
| 225 | } |
| 226 | not_reached(); |
| 227 | } |
| 228 | |
| 229 | static void |
| 230 | rtree_elm_witness_dalloc(tsd_t *tsd, witness_t *witness, const rtree_elm_t *elm) |
| 231 | { |
| 232 | size_t i; |
| 233 | rtree_elm_witness_tsd_t *witnesses = tsd_rtree_elm_witnessesp_get(tsd); |
| 234 | |
| 235 | for (i = 0; i < sizeof(rtree_elm_witness_tsd_t) / sizeof(witness_t); |
| 236 | i++) { |
| 237 | rtree_elm_witness_t *rew = &witnesses->witnesses[i]; |
| 238 | |
| 239 | if (rew->elm == elm) { |
| 240 | rew->elm = NULL; |
| 241 | witness_init(&rew->witness, "rtree_elm", |
| 242 | WITNESS_RANK_RTREE_ELM, rtree_elm_witness_comp, |
| 243 | NULL); |
| 244 | return; |
| 245 | } |
| 246 | } |
| 247 | not_reached(); |
| 248 | } |
| 249 | |
| 250 | void |
| 251 | rtree_elm_witness_acquire(tsdn_t *tsdn, const rtree_t *rtree, uintptr_t key, |
| 252 | const rtree_elm_t *elm) |
| 253 | { |
| 254 | witness_t *witness; |
| 255 | |
| 256 | if (tsdn_null(tsdn)) |
| 257 | return; |
| 258 | |
| 259 | witness = rtree_elm_witness_alloc(tsdn_tsd(tsdn), key, elm); |
| 260 | witness_lock(tsdn, witness); |
| 261 | } |
| 262 | |
| 263 | void |
| 264 | rtree_elm_witness_access(tsdn_t *tsdn, const rtree_t *rtree, |
| 265 | const rtree_elm_t *elm) |
| 266 | { |
| 267 | witness_t *witness; |
| 268 | |
| 269 | if (tsdn_null(tsdn)) |
| 270 | return; |
| 271 | |
| 272 | witness = rtree_elm_witness_find(tsdn_tsd(tsdn), elm); |
| 273 | witness_assert_owner(tsdn, witness); |
| 274 | } |
| 275 | |
| 276 | void |
| 277 | rtree_elm_witness_release(tsdn_t *tsdn, const rtree_t *rtree, |
| 278 | const rtree_elm_t *elm) |
| 279 | { |
| 280 | witness_t *witness; |
| 281 | |
| 282 | if (tsdn_null(tsdn)) |
| 283 | return; |
| 284 | |
| 285 | witness = rtree_elm_witness_find(tsdn_tsd(tsdn), elm); |
| 286 | witness_unlock(tsdn, witness); |
| 287 | rtree_elm_witness_dalloc(tsdn_tsd(tsdn), witness, elm); |
| 288 | } |