1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/rtree.h" 4 5 rtree_node_alloc_t *rtree_node_alloc_orig; 6 rtree_node_dalloc_t *rtree_node_dalloc_orig; 7 rtree_leaf_alloc_t *rtree_leaf_alloc_orig; 8 rtree_leaf_dalloc_t *rtree_leaf_dalloc_orig; 9 10 /* Potentially too large to safely place on the stack. */ 11 rtree_t test_rtree; 12 13 static rtree_node_elm_t * 14 rtree_node_alloc_intercept(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 15 rtree_node_elm_t *node; 16 17 if (rtree != &test_rtree) { 18 return rtree_node_alloc_orig(tsdn, rtree, nelms); 19 } 20 21 malloc_mutex_unlock(tsdn, &rtree->init_lock); 22 node = (rtree_node_elm_t *)calloc(nelms, sizeof(rtree_node_elm_t)); 23 assert_ptr_not_null(node, "Unexpected calloc() failure"); 24 malloc_mutex_lock(tsdn, &rtree->init_lock); 25 26 return node; 27 } 28 29 static void 30 rtree_node_dalloc_intercept(tsdn_t *tsdn, rtree_t *rtree, 31 rtree_node_elm_t *node) { 32 if (rtree != &test_rtree) { 33 rtree_node_dalloc_orig(tsdn, rtree, node); 34 return; 35 } 36 37 free(node); 38 } 39 40 static rtree_leaf_elm_t * 41 rtree_leaf_alloc_intercept(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 42 rtree_leaf_elm_t *leaf; 43 44 if (rtree != &test_rtree) { 45 return rtree_leaf_alloc_orig(tsdn, rtree, nelms); 46 } 47 48 malloc_mutex_unlock(tsdn, &rtree->init_lock); 49 leaf = (rtree_leaf_elm_t *)calloc(nelms, sizeof(rtree_leaf_elm_t)); 50 assert_ptr_not_null(leaf, "Unexpected calloc() failure"); 51 malloc_mutex_lock(tsdn, &rtree->init_lock); 52 53 return leaf; 54 } 55 56 static void 57 rtree_leaf_dalloc_intercept(tsdn_t *tsdn, rtree_t *rtree, 58 rtree_leaf_elm_t *leaf) { 59 if (rtree != &test_rtree) { 60 rtree_leaf_dalloc_orig(tsdn, rtree, leaf); 61 return; 62 } 63 64 free(leaf); 65 } 66 67 TEST_BEGIN(test_rtree_read_empty) { 68 tsdn_t *tsdn; 69 70 tsdn = tsdn_fetch(); 71 72 rtree_t *rtree = &test_rtree; 73 rtree_ctx_t rtree_ctx; 74 rtree_ctx_data_init(&rtree_ctx); 75 assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure"); 76 assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx, PAGE, 77 false), "rtree_extent_read() should return NULL for empty tree"); 78 rtree_delete(tsdn, rtree); 79 } 80 TEST_END 81 82 #undef NTHREADS 83 #undef NITERS 84 #undef SEED 85 86 TEST_BEGIN(test_rtree_extrema) { 87 extent_t extent_a, extent_b; 88 extent_init(&extent_a, NULL, NULL, LARGE_MINCLASS, false, 89 sz_size2index(LARGE_MINCLASS), 0, extent_state_active, false, 90 false, true); 91 extent_init(&extent_b, NULL, NULL, 0, false, NSIZES, 0, 92 extent_state_active, false, false, true); 93 94 tsdn_t *tsdn = tsdn_fetch(); 95 96 rtree_t *rtree = &test_rtree; 97 rtree_ctx_t rtree_ctx; 98 rtree_ctx_data_init(&rtree_ctx); 99 assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure"); 100 101 assert_false(rtree_write(tsdn, rtree, &rtree_ctx, PAGE, &extent_a, 102 extent_szind_get(&extent_a), extent_slab_get(&extent_a)), 103 "Unexpected rtree_write() failure"); 104 rtree_szind_slab_update(tsdn, rtree, &rtree_ctx, PAGE, 105 extent_szind_get(&extent_a), extent_slab_get(&extent_a)); 106 assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx, PAGE, true), 107 &extent_a, 108 "rtree_extent_read() should return previously set value"); 109 110 assert_false(rtree_write(tsdn, rtree, &rtree_ctx, ~((uintptr_t)0), 111 &extent_b, extent_szind_get_maybe_invalid(&extent_b), 112 extent_slab_get(&extent_b)), "Unexpected rtree_write() failure"); 113 assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx, 114 ~((uintptr_t)0), true), &extent_b, 115 "rtree_extent_read() should return previously set value"); 116 117 rtree_delete(tsdn, rtree); 118 } 119 TEST_END 120 121 TEST_BEGIN(test_rtree_bits) { 122 tsdn_t *tsdn = tsdn_fetch(); 123 124 uintptr_t keys[] = {PAGE, PAGE + 1, 125 PAGE + (((uintptr_t)1) << LG_PAGE) - 1}; 126 127 extent_t extent; 128 extent_init(&extent, NULL, NULL, 0, false, NSIZES, 0, 129 extent_state_active, false, false, true); 130 131 rtree_t *rtree = &test_rtree; 132 rtree_ctx_t rtree_ctx; 133 rtree_ctx_data_init(&rtree_ctx); 134 assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure"); 135 136 for (unsigned i = 0; i < sizeof(keys)/sizeof(uintptr_t); i++) { 137 assert_false(rtree_write(tsdn, rtree, &rtree_ctx, keys[i], 138 &extent, NSIZES, false), 139 "Unexpected rtree_write() failure"); 140 for (unsigned j = 0; j < sizeof(keys)/sizeof(uintptr_t); j++) { 141 assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx, 142 keys[j], true), &extent, 143 "rtree_extent_read() should return previously set " 144 "value and ignore insignificant key bits; i=%u, " 145 "j=%u, set key=%#"FMTxPTR", get key=%#"FMTxPTR, i, 146 j, keys[i], keys[j]); 147 } 148 assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx, 149 (((uintptr_t)2) << LG_PAGE), false), 150 "Only leftmost rtree leaf should be set; i=%u", i); 151 rtree_clear(tsdn, rtree, &rtree_ctx, keys[i]); 152 } 153 154 rtree_delete(tsdn, rtree); 155 } 156 TEST_END 157 158 TEST_BEGIN(test_rtree_random) { 159 #define NSET 16 160 #define SEED 42 161 sfmt_t *sfmt = init_gen_rand(SEED); 162 tsdn_t *tsdn = tsdn_fetch(); 163 uintptr_t keys[NSET]; 164 rtree_t *rtree = &test_rtree; 165 rtree_ctx_t rtree_ctx; 166 rtree_ctx_data_init(&rtree_ctx); 167 168 extent_t extent; 169 extent_init(&extent, NULL, NULL, 0, false, NSIZES, 0, 170 extent_state_active, false, false, true); 171 172 assert_false(rtree_new(rtree, false), "Unexpected rtree_new() failure"); 173 174 for (unsigned i = 0; i < NSET; i++) { 175 keys[i] = (uintptr_t)gen_rand64(sfmt); 176 rtree_leaf_elm_t *elm = rtree_leaf_elm_lookup(tsdn, rtree, 177 &rtree_ctx, keys[i], false, true); 178 assert_ptr_not_null(elm, 179 "Unexpected rtree_leaf_elm_lookup() failure"); 180 rtree_leaf_elm_write(tsdn, rtree, elm, &extent, NSIZES, false); 181 assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx, 182 keys[i], true), &extent, 183 "rtree_extent_read() should return previously set value"); 184 } 185 for (unsigned i = 0; i < NSET; i++) { 186 assert_ptr_eq(rtree_extent_read(tsdn, rtree, &rtree_ctx, 187 keys[i], true), &extent, 188 "rtree_extent_read() should return previously set value, " 189 "i=%u", i); 190 } 191 192 for (unsigned i = 0; i < NSET; i++) { 193 rtree_clear(tsdn, rtree, &rtree_ctx, keys[i]); 194 assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx, 195 keys[i], true), 196 "rtree_extent_read() should return previously set value"); 197 } 198 for (unsigned i = 0; i < NSET; i++) { 199 assert_ptr_null(rtree_extent_read(tsdn, rtree, &rtree_ctx, 200 keys[i], true), 201 "rtree_extent_read() should return previously set value"); 202 } 203 204 rtree_delete(tsdn, rtree); 205 fini_gen_rand(sfmt); 206 #undef NSET 207 #undef SEED 208 } 209 TEST_END 210 211 int 212 main(void) { 213 rtree_node_alloc_orig = rtree_node_alloc; 214 rtree_node_alloc = rtree_node_alloc_intercept; 215 rtree_node_dalloc_orig = rtree_node_dalloc; 216 rtree_node_dalloc = rtree_node_dalloc_intercept; 217 rtree_leaf_alloc_orig = rtree_leaf_alloc; 218 rtree_leaf_alloc = rtree_leaf_alloc_intercept; 219 rtree_leaf_dalloc_orig = rtree_leaf_dalloc; 220 rtree_leaf_dalloc = rtree_leaf_dalloc_intercept; 221 222 return test( 223 test_rtree_read_empty, 224 test_rtree_extrema, 225 test_rtree_bits, 226 test_rtree_random); 227 } 228