/home/travis/build/MoarVM/MoarVM/src/gc/worklist.h
Line | Count | Source |
1 | | /* A worklist holds the current set of pointers we have got in the queue |
2 | | * to scan. We hide away the details of it behind this abstraction since |
3 | | * the order in which we hand things back from it can have a big influence |
4 | | * on locality in the copied/compacted heap, and thus mutator performance. |
5 | | * |
6 | | * For the time being, we do the simplest possible thing: just make it a |
7 | | * stack. This actually has reasonable properties if we scan objects right |
8 | | * after they are copied/moved, since an object's children will then come |
9 | | * right after the object itself - unless they were copied/moved earlier. |
10 | | * But things aren't quite so rosy for deeply nested data structures, where |
11 | | * two siblings may thus end up far apart. Lots of stuff in the literature |
12 | | * on these issues, but for now this is probably less bad than some of the |
13 | | * other options. |
14 | | */ |
15 | | struct MVMGCWorklist { |
16 | | /* The worklist itself. An array of addresses which hold pointers to |
17 | | * collectables (yes, two levels of indirection, since we need to |
18 | | * update addresses in copying/moving algorithms.) */ |
19 | | MVMCollectable ***list; |
20 | | |
21 | | /* The number of items on the worklist. */ |
22 | | MVMuint32 items; |
23 | | |
24 | | /* The number of items the work list is allocated to hold. */ |
25 | | MVMuint32 alloc; |
26 | | |
27 | | /* Whether we should include gen2 entries. */ |
28 | | MVMuint8 include_gen2; |
29 | | }; |
30 | | |
31 | | /* Some macros for doing stuff fast with worklists, defined to look like |
32 | | * functions since perhaps they become them in the future if needed. */ |
33 | | #if MVM_GC_DEBUG |
34 | | #define MVM_gc_worklist_add(tc, worklist, item) \ |
35 | | do { \ |
36 | | MVMCollectable **item_to_add = (MVMCollectable **)(item);\ |
37 | | if (*item_to_add) { \ |
38 | | if ((*item_to_add)->owner == 0) \ |
39 | | MVM_panic(1, "Zeroed owner in item added to GC worklist"); \ |
40 | | if ((*item_to_add)->owner > tc->instance->next_user_thread_id) \ |
41 | | MVM_panic(1, "Invalid owner in item added to GC worklist"); \ |
42 | | if ((*item_to_add)->flags & MVM_CF_DEBUG_IN_GEN2_FREE_LIST) \ |
43 | | MVM_panic(1, "Adding item to worklist already freed in gen2\n"); \ |
44 | | if ((*item_to_add)->flags & MVM_CF_FRAME && !((MVMFrame *)(*item_to_add))->static_info) \ |
45 | | MVM_panic(1, "Frame with NULL static_info added to worklist"); \ |
46 | | else if ((*item_to_add)->flags & MVM_CF_STABLE == 0 && !STABLE(*item_to_add)) \ |
47 | | MVM_panic(1, "NULL STable in item added to GC worklist"); \ |
48 | | if ((char *)*item_to_add >= (char *)tc->nursery_alloc && \ |
49 | | (char *)*item_to_add < (char *)tc->nursery_alloc_limit) \ |
50 | | MVM_panic(1, "Adding pointer %p to past fromspace to GC worklist", \ |
51 | | *item_to_add); \ |
52 | | } \ |
53 | | if (*item_to_add && (worklist->include_gen2 || !((*item_to_add)->flags & MVM_CF_SECOND_GEN))) { \ |
54 | | if (worklist->items == worklist->alloc) \ |
55 | | MVM_gc_worklist_add_slow(tc, worklist, item_to_add); \ |
56 | | else \ |
57 | | worklist->list[worklist->items++] = item_to_add; \ |
58 | | } \ |
59 | | } while (0) |
60 | | #else |
61 | | #define MVM_gc_worklist_add(tc, worklist, item) \ |
62 | 26.4M | do { \ |
63 | 26.4M | MVMCollectable **item_to_add = (MVMCollectable **)(item);\ |
64 | 26.4M | if (*item_to_add && (worklist->include_gen2 || !((*item_to_add)->flags & MVM_CF_SECOND_GEN))) { \ |
65 | 4.40M | if (worklist->items == worklist->alloc) \ |
66 | 230 | MVM_gc_worklist_add_slow(tc, worklist, item_to_add); \ |
67 | 4.40M | else \ |
68 | 4.40M | worklist->list[worklist->items++] = item_to_add; \ |
69 | 4.40M | } \ |
70 | 26.4M | } while (0) |
71 | | #endif |
72 | | |
73 | | #define MVM_gc_worklist_get(tc, worklist) \ |
74 | 4.40M | (worklist->items ? \ |
75 | 4.40M | worklist->list[--worklist->items] : \ |
76 | 4.40M | NULL) |
77 | | |
78 | | /* Various functions for worklist manipulation. */ |
79 | | MVMGCWorklist * MVM_gc_worklist_create(MVMThreadContext *tc, MVMuint8 include_gen2); |
80 | | MVM_PUBLIC void MVM_gc_worklist_add_slow(MVMThreadContext *tc, MVMGCWorklist *worklist, MVMCollectable **item); |
81 | | void MVM_gc_worklist_presize_for(MVMThreadContext *tc, MVMGCWorklist *worklist, MVMint32 items); |
82 | | void MVM_gc_worklist_destroy(MVMThreadContext *tc, MVMGCWorklist *worklist); |
83 | | |
84 | | /* The number of pointers we assume the list may need to hold initially; |
85 | | * it will be resized as needed. */ |
86 | 778 | #define MVM_GC_WORKLIST_START_SIZE 256 |