Debian Codegraph @

gc/tests/disclaim_weakmap_test.c

raw
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 }