/home/travis/build/MoarVM/MoarVM/src/gc/gen2.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "moar.h" |
2 | | |
3 | | /* Creates a new second generation allocator. */ |
4 | 317 | MVMGen2Allocator * MVM_gc_gen2_create(MVMInstance *i) { |
5 | 317 | /* Create allocator data structure. */ |
6 | 317 | MVMGen2Allocator *al = MVM_malloc(sizeof(MVMGen2Allocator)); |
7 | 317 | |
8 | 317 | /* Create empty size classes array data structure. */ |
9 | 317 | al->size_classes = (MVMGen2SizeClass *)MVM_calloc(MVM_GEN2_BINS, sizeof(MVMGen2SizeClass)); |
10 | 317 | |
11 | 317 | /* Set up overflows area. */ |
12 | 317 | al->alloc_overflows = MVM_GEN2_OVERFLOWS; |
13 | 317 | al->num_overflows = 0; |
14 | 317 | al->overflows = MVM_malloc(al->alloc_overflows * sizeof(MVMCollectable *)); |
15 | 317 | |
16 | 317 | return al; |
17 | 317 | } |
18 | | |
19 | | /* Sets up a size class bin in the second generation. */ |
20 | 1.98k | static void setup_bin(MVMGen2Allocator *al, MVMuint32 bin) { |
21 | 1.98k | /* Work out page size we want. */ |
22 | 1.98k | MVMuint32 page_size = MVM_GEN2_PAGE_ITEMS * ((bin + 1) << MVM_GEN2_BIN_BITS); |
23 | 1.98k | |
24 | 1.98k | /* We'll just allocate a single page to start off with. */ |
25 | 1.98k | al->size_classes[bin].num_pages = 1; |
26 | 1.98k | al->size_classes[bin].pages = MVM_malloc(sizeof(void *) * al->size_classes[bin].num_pages); |
27 | 1.98k | al->size_classes[bin].pages[0] = MVM_malloc(page_size); |
28 | 1.98k | |
29 | 1.98k | /* Set up allocation position and limit. */ |
30 | 1.98k | al->size_classes[bin].alloc_pos = al->size_classes[bin].pages[0]; |
31 | 1.98k | al->size_classes[bin].alloc_limit = al->size_classes[bin].alloc_pos + page_size; |
32 | 1.98k | |
33 | 1.98k | /* Free list is empty until GC run (and we just do page by page allocation). */ |
34 | 1.98k | al->size_classes[bin].free_list = NULL; |
35 | 1.98k | } |
36 | | |
37 | | /* Adds a new page to a size class bin. */ |
38 | 19.1k | static void add_page(MVMGen2Allocator *al, MVMuint32 bin) { |
39 | 19.1k | /* Work out page size. */ |
40 | 19.1k | MVMuint32 page_size = MVM_GEN2_PAGE_ITEMS * ((bin + 1) << MVM_GEN2_BIN_BITS); |
41 | 19.1k | |
42 | 19.1k | /* Add the extra page. */ |
43 | 19.1k | MVMuint32 cur_page = al->size_classes[bin].num_pages; |
44 | 19.1k | al->size_classes[bin].num_pages++; |
45 | 19.1k | al->size_classes[bin].pages = MVM_realloc(al->size_classes[bin].pages, |
46 | 19.1k | sizeof(void *) * al->size_classes[bin].num_pages); |
47 | 19.1k | al->size_classes[bin].pages[cur_page] = MVM_malloc(page_size); |
48 | 19.1k | |
49 | 19.1k | /* Set up allocation position and limit. */ |
50 | 19.1k | al->size_classes[bin].alloc_pos = al->size_classes[bin].pages[cur_page]; |
51 | 19.1k | al->size_classes[bin].alloc_limit = al->size_classes[bin].alloc_pos + page_size; |
52 | 19.1k | |
53 | 19.1k | /* set the cur_page to a proper value */ |
54 | 19.1k | al->size_classes[bin].cur_page = cur_page; |
55 | 19.1k | } |
56 | | |
57 | | /* Allocates space using the second generation allocator and returns |
58 | | * a pointer to the allocated space. Does not zero the space or set |
59 | | * it up in any way. */ |
60 | 5.14M | void * MVM_gc_gen2_allocate(MVMGen2Allocator *al, MVMuint32 size) { |
61 | 5.14M | void *result; |
62 | 5.14M | |
63 | 5.14M | /* Determine the bin. If we hit a bin exactly then it's off-by-one, |
64 | 5.14M | * since the bins list is base-0. Otherwise we've some extra bits, |
65 | 5.14M | * which round us up to the next bin, but that's a no-op. */ |
66 | 5.14M | MVMuint32 bin = (size >> MVM_GEN2_BIN_BITS); |
67 | 5.14M | if ((size & MVM_GEN2_BIN_MASK) == 0) |
68 | 5.14M | bin--; |
69 | 5.14M | |
70 | 5.14M | /* If the selected bin is in range... */ |
71 | 5.14M | if (bin < MVM_GEN2_BINS) { |
72 | 5.14M | /* If we've no pages yet, never encountered this bin; set it up. */ |
73 | 5.14M | if (al->size_classes[bin].pages == NULL) |
74 | 1.98k | setup_bin(al, bin); |
75 | 5.14M | |
76 | 5.14M | /* If there's a free list entry, use that. */ |
77 | 5.14M | if (al->size_classes[bin].free_list) { |
78 | 107 | result = (void *)al->size_classes[bin].free_list; |
79 | 107 | al->size_classes[bin].free_list = (char **)*(al->size_classes[bin].free_list); |
80 | 107 | } |
81 | 5.14M | else { |
82 | 5.14M | /* If we're at the page limit, add a new page. */ |
83 | 5.14M | if (al->size_classes[bin].alloc_pos == al->size_classes[bin].alloc_limit) |
84 | 19.1k | add_page(al, bin); |
85 | 5.14M | |
86 | 5.14M | /* Now we can allocate. */ |
87 | 5.14M | result = al->size_classes[bin].alloc_pos; |
88 | 5.14M | al->size_classes[bin].alloc_pos += (bin + 1) << MVM_GEN2_BIN_BITS; |
89 | 5.14M | } |
90 | 5.14M | } |
91 | 18.4E | else { |
92 | 18.4E | /* We're beyond the size class bins, so resort to malloc. */ |
93 | 18.4E | result = MVM_malloc(size); |
94 | 18.4E | |
95 | 18.4E | /* Add to overflows list. */ |
96 | 18.4E | if (al->num_overflows == al->alloc_overflows) { |
97 | 0 | al->alloc_overflows *= 2; |
98 | 0 | al->overflows = MVM_realloc(al->overflows, |
99 | 0 | al->alloc_overflows * sizeof(MVMCollectable *)); |
100 | 0 | } |
101 | 18.4E | al->overflows[al->num_overflows++] = result; |
102 | 18.4E | } |
103 | 5.14M | |
104 | 5.14M | return result; |
105 | 5.14M | } |
106 | | |
107 | | /* Allocates space using the second generation allocator and returns |
108 | | * a pointer to the allocated space. Promises the memory will be |
109 | | * zeroed, except that the MVMCollectable gen 2 flag will get set. */ |
110 | 4.22M | void * MVM_gc_gen2_allocate_zeroed(MVMGen2Allocator *al, MVMuint32 size) { |
111 | 4.22M | void *a = MVM_gc_gen2_allocate(al, size); |
112 | 4.22M | memset(a, 0, size); |
113 | 4.22M | ((MVMCollectable *)a)->flags = MVM_CF_SECOND_GEN; |
114 | 4.22M | return a; |
115 | 4.22M | } |
116 | | |
117 | | /* Frees all memory associated with the second generation. */ |
118 | 23 | void MVM_gc_gen2_destroy(MVMInstance *i, MVMGen2Allocator *al) { |
119 | 23 | MVMint32 j, k; |
120 | 23 | |
121 | 23 | /* Remove all pages. */ |
122 | 943 | for (j = 0; j < MVM_GEN2_BINS; j++) { |
123 | 920 | for (k = 0; k < al->size_classes[j].num_pages; k++) |
124 | 0 | MVM_free(al->size_classes[j].pages[k]); |
125 | 920 | MVM_free(al->size_classes[j].pages); |
126 | 920 | } |
127 | 23 | |
128 | 23 | /* Free any allocated overflows. */ |
129 | 23 | for (j = 0; j < al->num_overflows; j++) |
130 | 0 | if (al->overflows[j]) |
131 | 0 | MVM_free(al->overflows[j]); |
132 | 23 | |
133 | 23 | /* Clean up allocator data structure. */ |
134 | 23 | MVM_free(al->size_classes); |
135 | 23 | al->size_classes = NULL; |
136 | 23 | MVM_free(al->overflows); |
137 | 23 | al->overflows = NULL; |
138 | 23 | MVM_free(al); |
139 | 23 | } |
140 | | |
141 | | /* blindly move pages from one gen2 to another */ |
142 | 23 | void MVM_gc_gen2_transfer(MVMThreadContext *src, MVMThreadContext *dest) { |
143 | 23 | MVMGen2Allocator *gen2 = src->gen2, *dest_gen2 = dest->gen2; |
144 | 23 | MVMuint32 bin, obj_size, page; |
145 | 23 | char ***freelist_insert_pos; |
146 | 23 | |
147 | 943 | for (bin = 0; bin < MVM_GEN2_BINS; bin++) { |
148 | 920 | MVMuint32 orig_dest_num_pages = dest_gen2->size_classes[bin].num_pages; |
149 | 920 | char *cur_ptr, *end_ptr; |
150 | 920 | /* If we've nothing allocated in this size class, skip it. */ |
151 | 920 | if (gen2->size_classes[bin].pages == NULL) |
152 | 860 | continue; |
153 | 920 | |
154 | 60 | if (dest_gen2->size_classes[bin].pages == NULL) |
155 | 1 | dest_gen2->size_classes[bin].free_list = NULL; |
156 | 60 | |
157 | 60 | /* Calculate object size for this bin. */ |
158 | 60 | obj_size = (bin + 1) << MVM_GEN2_BIN_BITS; |
159 | 60 | |
160 | 60 | /* freelist_insert_pos is a pointer to a memory location that |
161 | 60 | * stores the address of the last traversed free list node (char **). */ |
162 | 60 | /* Initialize freelist insertion position to free list head. */ |
163 | 60 | freelist_insert_pos = &gen2->size_classes[bin].free_list; |
164 | 60 | |
165 | 60 | if (dest_gen2->size_classes[bin].pages == NULL) { |
166 | 1 | dest_gen2->size_classes[bin].pages |
167 | 1 | = MVM_malloc(sizeof(void *) * gen2->size_classes[bin].num_pages); |
168 | 1 | dest_gen2->size_classes[bin].num_pages = gen2->size_classes[bin].num_pages; |
169 | 1 | } |
170 | 59 | else { |
171 | 59 | dest_gen2->size_classes[bin].num_pages |
172 | 59 | += gen2->size_classes[bin].num_pages; |
173 | 59 | dest_gen2->size_classes[bin].pages |
174 | 59 | = MVM_realloc(dest_gen2->size_classes[bin].pages, |
175 | 59 | sizeof(void *) * dest_gen2->size_classes[bin].num_pages); |
176 | 59 | } |
177 | 60 | |
178 | 60 | /* Visit each page in the source. */ |
179 | 127 | for (page = 0; page < gen2->size_classes[bin].num_pages; page++) { |
180 | 67 | /* Visit all the objects, looking for dead ones and swap the |
181 | 67 | * owner for each of them. */ |
182 | 67 | cur_ptr = gen2->size_classes[bin].pages[page]; |
183 | 67 | end_ptr = page + 1 == gen2->size_classes[bin].num_pages |
184 | 60 | ? gen2->size_classes[bin].alloc_pos |
185 | 7 | : cur_ptr + obj_size * MVM_GEN2_PAGE_ITEMS; |
186 | 1.92k | while (cur_ptr < end_ptr) { |
187 | 1.86k | if (cur_ptr == (char *)freelist_insert_pos) { |
188 | 0 | /* skip */ |
189 | 0 | } |
190 | 1.86k | else if (cur_ptr == (char *)*freelist_insert_pos) { |
191 | 1.78k | /* printf("found a free list slot in bin %d page %d: %d with value %d and start %d and limit %d\n", |
192 | 1.78k | bin, page, cur_ptr, *(void **)cur_ptr, gen2->size_classes[bin].pages[page], |
193 | 1.78k | dest_gen2->size_classes[bin].alloc_limit);*/ |
194 | 1.78k | freelist_insert_pos = (char ***)cur_ptr; |
195 | 1.78k | } |
196 | 78 | else { /* note: we don't have tests that exercise this path yet. */ |
197 | 78 | /* printf("updating an owner from %d to %d\n", ((MVMCollectable *)cur_ptr)->owner, dest->thread_id);*/ |
198 | 78 | ((MVMCollectable *)cur_ptr)->owner = dest->thread_id; |
199 | 78 | } |
200 | 1.86k | |
201 | 1.86k | /* Move to the next object. */ |
202 | 1.86k | cur_ptr += obj_size; |
203 | 1.86k | } |
204 | 67 | dest_gen2->size_classes[bin].pages[page + orig_dest_num_pages] = gen2->size_classes[bin].pages[page]; |
205 | 67 | } |
206 | 60 | |
207 | 60 | freelist_insert_pos = &dest_gen2->size_classes[bin].free_list; |
208 | 37.4k | while (*freelist_insert_pos) { |
209 | 37.3k | freelist_insert_pos = (char ***)*freelist_insert_pos; |
210 | 37.3k | } |
211 | 60 | /* chain the destination's freelist through any remaining unallocated area */ |
212 | 60 | if (dest_gen2->size_classes[bin].alloc_pos) { |
213 | 59 | cur_ptr = dest_gen2->size_classes[bin].alloc_pos; |
214 | 59 | end_ptr = dest_gen2->size_classes[bin].alloc_limit; |
215 | 13.6k | while (cur_ptr < end_ptr) { |
216 | 13.6k | *freelist_insert_pos = (char **)cur_ptr; |
217 | 13.6k | freelist_insert_pos = (char ***)cur_ptr; |
218 | 13.6k | cur_ptr += obj_size; |
219 | 13.6k | } |
220 | 59 | } |
221 | 60 | |
222 | 60 | /* link to the new pages, if any */ |
223 | 60 | *freelist_insert_pos = gen2->size_classes[bin].free_list; |
224 | 60 | |
225 | 60 | dest_gen2->size_classes[bin].alloc_pos = gen2->size_classes[bin].alloc_pos; |
226 | 60 | dest_gen2->size_classes[bin].alloc_limit = gen2->size_classes[bin].alloc_limit; |
227 | 60 | |
228 | 60 | MVM_free(gen2->size_classes[bin].pages); |
229 | 60 | gen2->size_classes[bin].pages = NULL; |
230 | 60 | gen2->size_classes[bin].num_pages = 0; |
231 | 60 | } |
232 | 23 | { /* copy the roots... */ |
233 | 23 | MVMuint32 i, n = src->num_gen2roots; |
234 | 26 | for ( i = 0; i < n; i++) { |
235 | 3 | MVM_gc_root_gen2_add(dest, src->gen2roots[i]); |
236 | 3 | } |
237 | 23 | src->num_gen2roots = 0; |
238 | 23 | src->alloc_gen2roots = 0; |
239 | 23 | MVM_free(src->gen2roots); |
240 | 23 | src->gen2roots = NULL; |
241 | 23 | } |
242 | 23 | } |
243 | | |
244 | | |
245 | 0 | void MVM_gc_gen2_compact_overflows(MVMGen2Allocator *al) { |
246 | 0 | /* compact the overflow list to prevent it from growing without bounds */ |
247 | 0 | MVMCollectable **overflows = al->overflows; |
248 | 0 | const MVMuint32 num_overflows = al->num_overflows; |
249 | 0 | MVMuint32 cursor = 0; |
250 | 0 | MVMuint32 live; |
251 | 0 |
|
252 | 0 | /* Find the first NULL object. */ |
253 | 0 | while (cursor < num_overflows && overflows[cursor]) |
254 | 0 | cursor++; |
255 | 0 | live = cursor; |
256 | 0 |
|
257 | 0 | /* Slide others back so the alive ones are at the start of the list. */ |
258 | 0 | while (cursor < num_overflows) { |
259 | 0 | if (overflows[cursor]) { |
260 | 0 | overflows[live++] = overflows[cursor]; |
261 | 0 | } |
262 | 0 | cursor++; |
263 | 0 | } |
264 | 0 |
|
265 | 0 | al->num_overflows = live; |
266 | 0 | } |