| 1 |
/* |
| 2 |
* Copyright (c) 2018 Petter A. Urkedal |
| 3 |
* |
| 4 |
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED |
| 5 |
* OR IMPLIED. ANY USE IS AT YOUR OWN RISK. |
| 6 |
* |
| 7 |
* Permission is hereby granted to use or copy this program |
| 8 |
* for any purpose, provided the above notices are retained on all copies. |
| 9 |
* Permission to modify the code and to distribute modified code is granted, |
| 10 |
* provided the above notices are retained, and a notice that the code was |
| 11 |
* modified is included with the above copyright notice. |
| 12 |
*/ |
| 13 |
|
| 14 |
/* This tests a case where disclaim notifiers sometimes return non-zero */ |
| 15 |
/* in order to protect objects from collection. */ |
| 16 |
|
| 17 |
#include <stdio.h> |
| 18 |
#include <stdlib.h> |
| 19 |
#include <string.h> |
| 20 |
|
| 21 |
#ifdef HAVE_CONFIG_H |
| 22 |
/* For GC_[P]THREADS */ |
| 23 |
# include "config.h" |
| 24 |
#endif |
| 25 |
|
| 26 |
#include "gc_disclaim.h" /* includes gc.h */ |
| 27 |
|
| 28 |
#define NOT_GCBUILD |
| 29 |
#include "private/gc_priv.h" |
| 30 |
#undef rand |
| 31 |
static GC_RAND_STATE_T seed; /* concurrent update does not hurt the test */ |
| 32 |
#define rand() GC_RAND_NEXT(&seed) |
| 33 |
|
| 34 |
#include "gc_mark.h" /* should not precede include gc_priv.h */ |
| 35 |
|
| 36 |
#ifdef GC_PTHREADS |
| 37 |
# ifndef NTHREADS |
| 38 |
# define NTHREADS 8 |
| 39 |
# endif |
| 40 |
# include <errno.h> /* for EAGAIN, EBUSY */ |
| 41 |
# include <pthread.h> |
| 42 |
# include "private/gc_atomic_ops.h" /* for AO_t and AO_fetch_and_add1 */ |
| 43 |
#else |
| 44 |
# undef NTHREADS |
| 45 |
# define NTHREADS 1 |
| 46 |
# ifndef AO_HAVE_compiler_barrier |
| 47 |
# define AO_t GC_word |
| 48 |
# endif |
| 49 |
#endif |
| 50 |
|
| 51 |
#define POP_SIZE 200 |
| 52 |
#define MUTATE_CNT (5000000 / NTHREADS) |
| 53 |
#define GROW_LIMIT (MUTATE_CNT / 10) |
| 54 |
|
| 55 |
#define WEAKMAP_CAPACITY 256 |
| 56 |
#define WEAKMAP_MUTEX_COUNT 32 |
| 57 |
|
| 58 |
/* FINALIZER_CLOSURE_FLAG definition matches the one in fnlz_mlc.c. */ |
| 59 |
#if defined(KEEP_BACK_PTRS) || defined(MAKE_BACK_GRAPH) |
| 60 |
# define FINALIZER_CLOSURE_FLAG 0x2 |
| 61 |
# define INVALIDATE_FLAG 0x1 |
| 62 |
#else |
| 63 |
# define FINALIZER_CLOSURE_FLAG 0x1 |
| 64 |
# define INVALIDATE_FLAG 0x2 |
| 65 |
#endif |
| 66 |
|
| 67 |
#define my_assert(e) \ |
| 68 |
if (!(e)) { \ |
| 69 |
fflush(stdout); \ |
| 70 |
fprintf(stderr, "Assertion failure, line %d: %s\n", __LINE__, #e); \ |
| 71 |
exit(70); \ |
| 72 |
} |
| 73 |
|
| 74 |
#define CHECK_OOM(p) \ |
| 75 |
do { \ |
| 76 |
if (NULL == (p)) { \ |
| 77 |
fprintf(stderr, "Out of memory\n"); \ |
| 78 |
exit(69); \ |
| 79 |
} \ |
| 80 |
} while (0) |
| 81 |
|
| 82 |
#ifndef AO_HAVE_fetch_and_add1 |
| 83 |
# define AO_fetch_and_add1(p) ((*(p))++) |
| 84 |
/* This is used only to update counters. */ |
| 85 |
#endif |
| 86 |
|
| 87 |
unsigned memhash(void *src, size_t len) |
| 88 |
{ |
| 89 |
unsigned acc = 0; |
| 90 |
size_t i; |
| 91 |
|
| 92 |
my_assert(len % sizeof(GC_word) == 0); |
| 93 |
for (i = 0; i < len / sizeof(GC_word); ++i) { |
| 94 |
acc = (unsigned)((2003 * (GC_word)acc + ((GC_word *)src)[i]) / 3); |
| 95 |
} |
| 96 |
return acc; |
| 97 |
} |
| 98 |
|
| 99 |
static volatile AO_t stat_added; |
| 100 |
static volatile AO_t stat_found; |
| 101 |
static volatile AO_t stat_removed; |
| 102 |
static volatile AO_t stat_skip_locked; |
| 103 |
static volatile AO_t stat_skip_marked; |
| 104 |
|
| 105 |
struct weakmap_link { |
| 106 |
GC_hidden_pointer obj; |
| 107 |
struct weakmap_link *next; |
| 108 |
}; |
| 109 |
|
| 110 |
struct weakmap { |
| 111 |
# ifdef GC_PTHREADS |
| 112 |
pthread_mutex_t mutex[WEAKMAP_MUTEX_COUNT]; |
| 113 |
# endif |
| 114 |
size_t key_size; |
| 115 |
size_t obj_size; |
| 116 |
size_t capacity; |
| 117 |
unsigned weakobj_kind; |
| 118 |
struct weakmap_link **links; /* NULL means weakmap is destroyed */ |
| 119 |
}; |
| 120 |
|
| 121 |
void weakmap_lock(struct weakmap *wm, unsigned h) |
| 122 |
{ |
| 123 |
# ifdef GC_PTHREADS |
| 124 |
int err = pthread_mutex_lock(&wm->mutex[h % WEAKMAP_MUTEX_COUNT]); |
| 125 |
my_assert(0 == err); |
| 126 |
# else |
| 127 |
(void)wm; (void)h; |
| 128 |
# endif |
| 129 |
} |
| 130 |
|
| 131 |
int weakmap_trylock(struct weakmap *wm, unsigned h) |
| 132 |
{ |
| 133 |
# ifdef GC_PTHREADS |
| 134 |
int err = pthread_mutex_trylock(&wm->mutex[h % WEAKMAP_MUTEX_COUNT]); |
| 135 |
if (err != 0 && err != EBUSY) { |
| 136 |
fprintf(stderr, "pthread_mutex_trylock: %s\n", strerror(err)); |
| 137 |
exit(69); |
| 138 |
} |
| 139 |
return err; |
| 140 |
# else |
| 141 |
(void)wm; (void)h; |
| 142 |
return 0; |
| 143 |
# endif |
| 144 |
} |
| 145 |
|
| 146 |
void weakmap_unlock(struct weakmap *wm, unsigned h) |
| 147 |
{ |
| 148 |
# ifdef GC_PTHREADS |
| 149 |
int err = pthread_mutex_unlock(&wm->mutex[h % WEAKMAP_MUTEX_COUNT]); |
| 150 |
my_assert(0 == err); |
| 151 |
# else |
| 152 |
(void)wm; (void)h; |
| 153 |
# endif |
| 154 |
} |
| 155 |
|
| 156 |
void *GC_CALLBACK set_mark_bit(void *obj) |
| 157 |
{ |
| 158 |
GC_set_mark_bit(obj); |
| 159 |
return NULL; |
| 160 |
} |
| 161 |
|
| 162 |
void *weakmap_add(struct weakmap *wm, void *obj, size_t obj_size) |
| 163 |
{ |
| 164 |
struct weakmap_link *link, *new_link, **first; |
| 165 |
GC_word *new_base; |
| 166 |
void *new_obj; |
| 167 |
unsigned h; |
| 168 |
size_t key_size = wm->key_size; |
| 169 |
|
| 170 |
/* Lock and look for an existing entry. */ |
| 171 |
my_assert(key_size <= obj_size); |
| 172 |
h = memhash(obj, key_size); |
| 173 |
first = &wm->links[h % wm->capacity]; |
| 174 |
weakmap_lock(wm, h); |
| 175 |
|
| 176 |
for (link = *first; link != NULL; link = link->next) { |
| 177 |
void *old_obj = GC_get_find_leak() ? (void *)link->obj |
| 178 |
: GC_REVEAL_POINTER(link->obj); |
| 179 |
|
| 180 |
if (memcmp(old_obj, obj, key_size) == 0) { |
| 181 |
GC_call_with_alloc_lock(set_mark_bit, (GC_word *)old_obj - 1); |
| 182 |
/* Pointers in the key part may have been freed and reused, */ |
| 183 |
/* changing the keys without memcmp noticing. This is okay */ |
| 184 |
/* as long as we update the mapped value. */ |
| 185 |
if (memcmp((char *)old_obj + key_size, (char *)obj + key_size, |
| 186 |
wm->obj_size - key_size) != 0) { |
| 187 |
memcpy((char *)old_obj + key_size, (char *)obj + key_size, |
| 188 |
wm->obj_size - key_size); |
| 189 |
GC_end_stubborn_change((char *)old_obj + key_size); |
| 190 |
} |
| 191 |
weakmap_unlock(wm, h); |
| 192 |
AO_fetch_and_add1(&stat_found); |
| 193 |
# ifdef DEBUG_DISCLAIM_WEAKMAP |
| 194 |
printf("Found %p, hash= %p\n", old_obj, (void *)(GC_word)h); |
| 195 |
# endif |
| 196 |
return old_obj; |
| 197 |
} |
| 198 |
} |
| 199 |
|
| 200 |
/* Create new object. */ |
| 201 |
new_base = (GC_word *)GC_generic_malloc(sizeof(GC_word) + wm->obj_size, |
| 202 |
wm->weakobj_kind); |
| 203 |
CHECK_OOM(new_base); |
| 204 |
*new_base = (GC_word)wm | FINALIZER_CLOSURE_FLAG; |
| 205 |
new_obj = (void *)(new_base + 1); |
| 206 |
memcpy(new_obj, obj, wm->obj_size); |
| 207 |
GC_end_stubborn_change(new_base); |
| 208 |
|
| 209 |
/* Add the object to the map. */ |
| 210 |
new_link = (struct weakmap_link *)GC_malloc(sizeof(struct weakmap_link)); |
| 211 |
CHECK_OOM(new_link); |
| 212 |
new_link->obj = GC_get_find_leak() ? (GC_word)new_obj |
| 213 |
: GC_HIDE_POINTER(new_obj); |
| 214 |
new_link->next = *first; |
| 215 |
GC_END_STUBBORN_CHANGE(new_link); |
| 216 |
GC_ptr_store_and_dirty(first, new_link); |
| 217 |
weakmap_unlock(wm, h); |
| 218 |
AO_fetch_and_add1(&stat_added); |
| 219 |
# ifdef DEBUG_DISCLAIM_WEAKMAP |
| 220 |
printf("Added %p, hash= %p\n", new_obj, (void *)(GC_word)h); |
| 221 |
# endif |
| 222 |
return new_obj; |
| 223 |
} |
| 224 |
|
| 225 |
int GC_CALLBACK weakmap_disclaim(void *obj_base) |
| 226 |
{ |
| 227 |
struct weakmap *wm; |
| 228 |
struct weakmap_link **link; |
| 229 |
GC_word hdr; |
| 230 |
void *obj; |
| 231 |
unsigned h; |
| 232 |
|
| 233 |
/* Decode header word. */ |
| 234 |
hdr = *(GC_word *)obj_base; |
| 235 |
if ((hdr & FINALIZER_CLOSURE_FLAG) == 0) |
| 236 |
return 0; /* on GC free list, ignore it. */ |
| 237 |
|
| 238 |
my_assert((hdr & INVALIDATE_FLAG) == 0); |
| 239 |
wm = (struct weakmap *)(hdr & ~(GC_word)FINALIZER_CLOSURE_FLAG); |
| 240 |
if (NULL == wm->links) |
| 241 |
return 0; /* weakmap has been already destroyed */ |
| 242 |
obj = (GC_word *)obj_base + 1; |
| 243 |
|
| 244 |
/* Lock and check for mark. */ |
| 245 |
h = memhash(obj, wm->key_size); |
| 246 |
if (weakmap_trylock(wm, h) != 0) { |
| 247 |
AO_fetch_and_add1(&stat_skip_locked); |
| 248 |
# ifdef DEBUG_DISCLAIM_WEAKMAP |
| 249 |
printf("Skipping locked %p, hash= %p\n", obj, (void *)(GC_word)h); |
| 250 |
# endif |
| 251 |
return 1; |
| 252 |
} |
| 253 |
if (GC_is_marked(obj_base)) { |
| 254 |
weakmap_unlock(wm, h); |
| 255 |
AO_fetch_and_add1(&stat_skip_marked); |
| 256 |
# ifdef DEBUG_DISCLAIM_WEAKMAP |
| 257 |
printf("Skipping marked %p, hash= %p\n", obj, (void *)(GC_word)h); |
| 258 |
# endif |
| 259 |
return 1; |
| 260 |
} |
| 261 |
|
| 262 |
/* Remove obj from wm. */ |
| 263 |
AO_fetch_and_add1(&stat_removed); |
| 264 |
# ifdef DEBUG_DISCLAIM_WEAKMAP |
| 265 |
printf("Removing %p, hash= %p\n", obj, (void *)(GC_word)h); |
| 266 |
# endif |
| 267 |
*(GC_word *)obj_base |= INVALIDATE_FLAG; |
| 268 |
for (link = &wm->links[h % wm->capacity];; link = &(*link)->next) { |
| 269 |
void *old_obj; |
| 270 |
|
| 271 |
if (NULL == *link) { |
| 272 |
fprintf(stderr, "Did not find %p\n", obj); |
| 273 |
exit(70); |
| 274 |
} |
| 275 |
old_obj = GC_get_find_leak() ? (void *)(*link)->obj |
| 276 |
: GC_REVEAL_POINTER((*link)->obj); |
| 277 |
if (old_obj == obj) |
| 278 |
break; |
| 279 |
my_assert(memcmp(old_obj, obj, wm->key_size) != 0); |
| 280 |
} |
| 281 |
GC_ptr_store_and_dirty(link, (*link)->next); |
| 282 |
weakmap_unlock(wm, h); |
| 283 |
return 0; |
| 284 |
} |
| 285 |
|
| 286 |
struct weakmap *weakmap_new(size_t capacity, size_t key_size, size_t obj_size, |
| 287 |
unsigned weakobj_kind) |
| 288 |
{ |
| 289 |
struct weakmap *wm = (struct weakmap *)GC_malloc(sizeof(struct weakmap)); |
| 290 |
|
| 291 |
CHECK_OOM(wm); |
| 292 |
# ifdef GC_PTHREADS |
| 293 |
{ |
| 294 |
int i; |
| 295 |
for (i = 0; i < WEAKMAP_MUTEX_COUNT; ++i) { |
| 296 |
int err = pthread_mutex_init(&wm->mutex[i], NULL); |
| 297 |
my_assert(err == 0); |
| 298 |
} |
| 299 |
} |
| 300 |
# endif |
| 301 |
wm->key_size = key_size; |
| 302 |
wm->obj_size = obj_size; |
| 303 |
wm->capacity = capacity; |
| 304 |
wm->weakobj_kind = weakobj_kind; |
| 305 |
GC_ptr_store_and_dirty(&wm->links, |
| 306 |
GC_malloc(sizeof(struct weakmap_link *) * capacity)); |
| 307 |
CHECK_OOM(wm->links); |
| 308 |
return wm; |
| 309 |
} |
| 310 |
|
| 311 |
void weakmap_destroy(struct weakmap *wm) |
| 312 |
{ |
| 313 |
# ifdef GC_PTHREADS |
| 314 |
int i; |
| 315 |
|
| 316 |
for (i = 0; i < WEAKMAP_MUTEX_COUNT; ++i) { |
| 317 |
(void)pthread_mutex_destroy(&wm->mutex[i]); |
| 318 |
} |
| 319 |
# endif |
| 320 |
wm->links = NULL; /* weakmap is destroyed */ |
| 321 |
} |
| 322 |
|
| 323 |
struct weakmap *pair_hcset; |
| 324 |
|
| 325 |
#define PAIR_MAGIC_SIZE 16 /* should not exceed sizeof(pair_magic) */ |
| 326 |
|
| 327 |
struct pair_key { |
| 328 |
struct pair *car, *cdr; |
| 329 |
}; |
| 330 |
|
| 331 |
struct pair { |
| 332 |
struct pair *car; |
| 333 |
struct pair *cdr; |
| 334 |
char magic[PAIR_MAGIC_SIZE]; |
| 335 |
int checksum; |
| 336 |
}; |
| 337 |
|
| 338 |
static const char * const pair_magic = "PAIR_MAGIC_BYTES"; |
| 339 |
|
| 340 |
struct pair *pair_new(struct pair *car, struct pair *cdr) |
| 341 |
{ |
| 342 |
struct pair tmpl; |
| 343 |
|
| 344 |
memset(&tmpl, 0, sizeof(tmpl)); /* To clear the paddings (to avoid */ |
| 345 |
/* a compiler warning). */ |
| 346 |
tmpl.car = car; |
| 347 |
tmpl.cdr = cdr; |
| 348 |
memcpy(tmpl.magic, pair_magic, PAIR_MAGIC_SIZE); |
| 349 |
tmpl.checksum = 782 + (car? car->checksum : 0) + (cdr? cdr->checksum : 0); |
| 350 |
return (struct pair *)weakmap_add(pair_hcset, &tmpl, sizeof(tmpl)); |
| 351 |
} |
| 352 |
|
| 353 |
void pair_check_rec(struct pair *p, int line) |
| 354 |
{ |
| 355 |
while (p != NULL) { |
| 356 |
int checksum = 782; |
| 357 |
|
| 358 |
if (memcmp(p->magic, pair_magic, PAIR_MAGIC_SIZE) != 0) { |
| 359 |
fprintf(stderr, "Magic bytes wrong for %p at %d\n", (void *)p, line); |
| 360 |
exit(70); |
| 361 |
} |
| 362 |
if (p->car != NULL) |
| 363 |
checksum += p->car->checksum; |
| 364 |
if (p->cdr != NULL) |
| 365 |
checksum += p->cdr->checksum; |
| 366 |
if (p->checksum != checksum) { |
| 367 |
fprintf(stderr, "Checksum failure for %p: (car= %p, cdr= %p) at %d\n", |
| 368 |
(void *)p, (void *)p->car, (void *)p->cdr, line); |
| 369 |
exit(70); |
| 370 |
} |
| 371 |
p = (rand() & 1) != 0 ? p->cdr : p->car; |
| 372 |
} |
| 373 |
} |
| 374 |
|
| 375 |
void *test(void *data) |
| 376 |
{ |
| 377 |
int i; |
| 378 |
struct pair *p0, *p1; |
| 379 |
struct pair *pop[POP_SIZE]; |
| 380 |
|
| 381 |
memset(pop, 0, sizeof(pop)); |
| 382 |
for (i = 0; i < MUTATE_CNT; ++i) { |
| 383 |
int bits = rand(); |
| 384 |
int t = (bits >> 3) % POP_SIZE; |
| 385 |
|
| 386 |
switch (bits % (i > GROW_LIMIT ? 5 : 3)) { |
| 387 |
case 0: |
| 388 |
case 3: |
| 389 |
if (pop[t] != NULL) |
| 390 |
pop[t] = pop[t]->car; |
| 391 |
break; |
| 392 |
case 1: |
| 393 |
case 4: |
| 394 |
if (pop[t] != NULL) |
| 395 |
pop[t] = pop[t]->cdr; |
| 396 |
break; |
| 397 |
case 2: |
| 398 |
p0 = pop[rand() % POP_SIZE]; |
| 399 |
p1 = pop[rand() % POP_SIZE]; |
| 400 |
pop[t] = pair_new(p0, p1); |
| 401 |
my_assert(pair_new(p0, p1) == pop[t]); |
| 402 |
my_assert(pop[t]->car == p0); |
| 403 |
my_assert(pop[t]->cdr == p1); |
| 404 |
break; |
| 405 |
} |
| 406 |
pair_check_rec(pop[rand() % POP_SIZE], __LINE__); |
| 407 |
} |
| 408 |
return data; |
| 409 |
} |
| 410 |
|
| 411 |
int main(void) |
| 412 |
{ |
| 413 |
unsigned weakobj_kind; |
| 414 |
# ifdef GC_PTHREADS |
| 415 |
int i, n; |
| 416 |
pthread_t th[NTHREADS]; |
| 417 |
# endif |
| 418 |
|
| 419 |
GC_set_all_interior_pointers(0); /* for a stricter test */ |
| 420 |
# ifdef TEST_MANUAL_VDB |
| 421 |
GC_set_manual_vdb_allowed(1); |
| 422 |
# endif |
| 423 |
GC_INIT(); |
| 424 |
GC_init_finalized_malloc(); /* to register the displacements */ |
| 425 |
# ifndef NO_INCREMENTAL |
| 426 |
GC_enable_incremental(); |
| 427 |
# endif |
| 428 |
if (GC_get_find_leak()) |
| 429 |
printf("This test program is not designed for leak detection mode\n"); |
| 430 |
weakobj_kind = GC_new_kind(GC_new_free_list(), /* 0 | */ GC_DS_LENGTH, |
| 431 |
1 /* adjust */, 1 /* clear */); |
| 432 |
GC_register_disclaim_proc(weakobj_kind, weakmap_disclaim, |
| 433 |
1 /* mark_unconditionally */); |
| 434 |
pair_hcset = weakmap_new(WEAKMAP_CAPACITY, sizeof(struct pair_key), |
| 435 |
sizeof(struct pair), weakobj_kind); |
| 436 |
|
| 437 |
# ifdef GC_PTHREADS |
| 438 |
for (i = 0; i < NTHREADS; ++i) { |
| 439 |
int err = pthread_create(&th[i], NULL, test, NULL); |
| 440 |
if (err != 0) { |
| 441 |
fprintf(stderr, "Failed to create thread #%d: %s\n", |
| 442 |
i, strerror(err)); |
| 443 |
if (i > 1 && EAGAIN == err) break; |
| 444 |
exit(1); |
| 445 |
} |
| 446 |
} |
| 447 |
n = i; |
| 448 |
for (i = 0; i < n; ++i) { |
| 449 |
int err = pthread_join(th[i], NULL); |
| 450 |
if (err != 0) { |
| 451 |
fprintf(stderr, "Failed to join thread #%d: %s\n", i, strerror(err)); |
| 452 |
exit(69); |
| 453 |
} |
| 454 |
} |
| 455 |
# else |
| 456 |
(void)test(NULL); |
| 457 |
# endif |
| 458 |
weakmap_destroy(pair_hcset); |
| 459 |
printf("%u added, %u found; %u removed, %u locked, %u marked; %u remains\n", |
| 460 |
(unsigned)stat_added, (unsigned)stat_found, (unsigned)stat_removed, |
| 461 |
(unsigned)stat_skip_locked, (unsigned)stat_skip_marked, |
| 462 |
(unsigned)stat_added - (unsigned)stat_removed); |
| 463 |
return 0; |
| 464 |
} |