LEFT | RIGHT |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // Garbage collector. | 5 // Garbage collector. |
6 | 6 |
7 #include "runtime.h" | 7 #include "runtime.h" |
8 #include "arch_GOARCH.h" | 8 #include "arch_GOARCH.h" |
9 #include "malloc.h" | 9 #include "malloc.h" |
10 #include "stack.h" | 10 #include "stack.h" |
(...skipping 145 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
156 enum { | 156 enum { |
157 // TODO(atom): to be expanded in a next CL | 157 // TODO(atom): to be expanded in a next CL |
158 GC_DEFAULT_PTR = GC_NUM_INSTR, | 158 GC_DEFAULT_PTR = GC_NUM_INSTR, |
159 }; | 159 }; |
160 | 160 |
161 // PtrTarget and BitTarget are structures used by intermediate buffers. | 161 // PtrTarget and BitTarget are structures used by intermediate buffers. |
162 // The intermediate buffers hold GC data before it | 162 // The intermediate buffers hold GC data before it |
163 // is moved/flushed to the work buffer (Workbuf). | 163 // is moved/flushed to the work buffer (Workbuf). |
164 // The size of an intermediate buffer is very small, | 164 // The size of an intermediate buffer is very small, |
165 // such as 32 or 64 elements. | 165 // such as 32 or 64 elements. |
| 166 typedef struct PtrTarget PtrTarget; |
166 struct PtrTarget | 167 struct PtrTarget |
167 { | 168 { |
168 void *p; | 169 void *p; |
169 uintptr ti; | 170 uintptr ti; |
170 }; | 171 }; |
171 | 172 |
| 173 typedef struct BitTarget BitTarget; |
172 struct BitTarget | 174 struct BitTarget |
173 { | 175 { |
174 void *p; | 176 void *p; |
175 uintptr ti; | 177 uintptr ti; |
176 uintptr *bitp, shift; | 178 uintptr *bitp, shift; |
177 }; | 179 }; |
178 | 180 |
| 181 typedef struct BufferList BufferList; |
179 struct BufferList | 182 struct BufferList |
180 { | 183 { |
181 » struct PtrTarget ptrtarget[IntermediateBufferCapacity]; | 184 » PtrTarget ptrtarget[IntermediateBufferCapacity]; |
182 » struct BitTarget bittarget[IntermediateBufferCapacity]; | 185 » BitTarget bittarget[IntermediateBufferCapacity]; |
183 » struct BufferList *next; | 186 » BufferList *next; |
184 }; | 187 }; |
185 static struct BufferList *bufferList; | 188 static BufferList *bufferList; |
186 | 189 |
187 static Lock lock; | 190 static Lock lock; |
188 | 191 |
189 // flushptrbuf moves data from the PtrTarget buffer to the work buffer. | 192 // flushptrbuf moves data from the PtrTarget buffer to the work buffer. |
190 // The PtrTarget buffer contains blocks irrespective of whether the blocks have
been marked or scanned, | 193 // The PtrTarget buffer contains blocks irrespective of whether the blocks have
been marked or scanned, |
191 // while the work buffer contains blocks which have been marked | 194 // while the work buffer contains blocks which have been marked |
192 // and are prepared to be scanned by the garbage collector. | 195 // and are prepared to be scanned by the garbage collector. |
193 // | 196 // |
194 // _wp, _wbuf, _nobj are input/output parameters and are specifying the work buf
fer. | 197 // _wp, _wbuf, _nobj are input/output parameters and are specifying the work buf
fer. |
195 // bitbuf holds temporary data generated by this function. | 198 // bitbuf holds temporary data generated by this function. |
196 // | 199 // |
197 // A simplified drawing explaining how the todo-list moves from a structure to a
nother: | 200 // A simplified drawing explaining how the todo-list moves from a structure to a
nother: |
198 // | 201 // |
199 // scanblock | 202 // scanblock |
200 // (find pointers) | 203 // (find pointers) |
201 // Obj ------> PtrTarget (pointer targets) | 204 // Obj ------> PtrTarget (pointer targets) |
202 // ↑ | | 205 // ↑ | |
203 // | | flushptrbuf (1st part, | 206 // | | flushptrbuf (1st part, |
204 // | | find block start) | 207 // | | find block start) |
205 // | ↓ | 208 // | ↓ |
206 // `--------- BitTarget (pointer targets and the corresponding locations in
bitmap) | 209 // `--------- BitTarget (pointer targets and the corresponding locations in
bitmap) |
207 // flushptrbuf | 210 // flushptrbuf |
208 // (2nd part, mark and enqueue) | 211 // (2nd part, mark and enqueue) |
209 static void | 212 static void |
210 flushptrbuf(struct PtrTarget *ptrbuf, uintptr n, Obj **_wp, Workbuf **_wbuf, uin
tptr *_nobj, struct BitTarget *bitbuf) | 213 flushptrbuf(PtrTarget *ptrbuf, uintptr n, Obj **_wp, Workbuf **_wbuf, uintptr *_
nobj, BitTarget *bitbuf) |
211 { | 214 { |
212 byte *p, *arena_start, *obj; | 215 byte *p, *arena_start, *obj; |
213 uintptr size, *bitp, bits, shift, j, x, xbits, off, nobj, ti; | 216 uintptr size, *bitp, bits, shift, j, x, xbits, off, nobj, ti; |
214 MSpan *s; | 217 MSpan *s; |
215 PageID k; | 218 PageID k; |
216 Obj *wp; | 219 Obj *wp; |
217 Workbuf *wbuf; | 220 Workbuf *wbuf; |
218 » struct PtrTarget *ptrbuf_end; | 221 » PtrTarget *ptrbuf_end; |
219 » struct BitTarget *bitbufpos, *bt; | 222 » BitTarget *bitbufpos, *bt; |
220 | 223 |
221 arena_start = runtime·mheap.arena_start; | 224 arena_start = runtime·mheap.arena_start; |
222 | 225 |
223 wp = *_wp; | 226 wp = *_wp; |
224 wbuf = *_wbuf; | 227 wbuf = *_wbuf; |
225 nobj = *_nobj; | 228 nobj = *_nobj; |
226 | 229 |
227 ptrbuf_end = ptrbuf + n; | 230 ptrbuf_end = ptrbuf + n; |
228 | 231 |
229 // If buffer is nearly full, get a new one. | 232 // If buffer is nearly full, get a new one. |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
316 xbits = *bitp; | 319 xbits = *bitp; |
317 bits = xbits >> shift; | 320 bits = xbits >> shift; |
318 | 321 |
319 found: | 322 found: |
320 // Now we have bits, bitp, and shift correct for | 323 // Now we have bits, bitp, and shift correct for |
321 // obj pointing at the base of the object. | 324 // obj pointing at the base of the object. |
322 // Only care about allocated and not marked. | 325 // Only care about allocated and not marked. |
323 if((bits & (bitAllocated|bitMarked)) != bitAllocated) | 326 if((bits & (bitAllocated|bitMarked)) != bitAllocated) |
324 continue; | 327 continue; |
325 | 328 |
326 » » » *bitbufpos = (struct BitTarget){obj, ti, bitp, shift}; | 329 » » » *bitbufpos = (BitTarget){obj, ti, bitp, shift}; |
327 bitbufpos++; | 330 bitbufpos++; |
328 } | 331 } |
329 | 332 |
330 runtime·lock(&lock); | 333 runtime·lock(&lock); |
331 for(bt=bitbuf; bt<bitbufpos; bt++){ | 334 for(bt=bitbuf; bt<bitbufpos; bt++){ |
332 xbits = *bt->bitp; | 335 xbits = *bt->bitp; |
333 bits = xbits >> bt->shift; | 336 bits = xbits >> bt->shift; |
334 if((bits & bitMarked) != 0) | 337 if((bits & bitMarked) != 0) |
335 continue; | 338 continue; |
336 | 339 |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
391 byte *b, *arena_start, *arena_used; | 394 byte *b, *arena_start, *arena_used; |
392 uintptr n, i, end_b; | 395 uintptr n, i, end_b; |
393 void *obj; | 396 void *obj; |
394 | 397 |
395 // TODO(atom): to be expanded in a next CL | 398 // TODO(atom): to be expanded in a next CL |
396 struct Frame {uintptr count, b; uintptr *loop_or_ret;}; | 399 struct Frame {uintptr count, b; uintptr *loop_or_ret;}; |
397 struct Frame stack_top; | 400 struct Frame stack_top; |
398 | 401 |
399 uintptr *pc; | 402 uintptr *pc; |
400 | 403 |
401 » struct BufferList *scanbuffers; | 404 » BufferList *scanbuffers; |
402 » struct PtrTarget *ptrbuf, *ptrbuf_end; | 405 » PtrTarget *ptrbuf, *ptrbuf_end; |
403 » struct BitTarget *bitbuf; | 406 » BitTarget *bitbuf; |
404 | 407 |
405 » struct PtrTarget *ptrbufpos; | 408 » PtrTarget *ptrbufpos; |
406 | 409 |
407 // End of local variable declarations. | 410 // End of local variable declarations. |
408 | 411 |
409 if(sizeof(Workbuf) % PageSize != 0) | 412 if(sizeof(Workbuf) % PageSize != 0) |
410 runtime·throw("scanblock: size of Workbuf is suboptimal"); | 413 runtime·throw("scanblock: size of Workbuf is suboptimal"); |
411 | 414 |
412 // Memory arena parameters. | 415 // Memory arena parameters. |
413 arena_start = runtime·mheap.arena_start; | 416 arena_start = runtime·mheap.arena_start; |
414 arena_used = runtime·mheap.arena_used; | 417 arena_used = runtime·mheap.arena_used; |
415 | 418 |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
455 switch(pc[0]) { | 458 switch(pc[0]) { |
456 case GC_DEFAULT_PTR: | 459 case GC_DEFAULT_PTR: |
457 while(true) { | 460 while(true) { |
458 i = stack_top.b; | 461 i = stack_top.b; |
459 if(i > end_b) | 462 if(i > end_b) |
460 goto next_block; | 463 goto next_block; |
461 stack_top.b += PtrSize; | 464 stack_top.b += PtrSize; |
462 | 465 |
463 obj = *(byte**)i; | 466 obj = *(byte**)i; |
464 if(obj >= arena_start && obj < arena_used) { | 467 if(obj >= arena_start && obj < arena_used) { |
465 » » » » » *ptrbufpos = (struct PtrTarget){obj, 0}; | 468 » » » » » *ptrbufpos = (PtrTarget){obj, 0}; |
466 ptrbufpos++; | 469 ptrbufpos++; |
467 if(ptrbufpos == ptrbuf_end) | 470 if(ptrbufpos == ptrbuf_end) |
468 goto flush_buffers; | 471 goto flush_buffers; |
469 } | 472 } |
470 } | 473 } |
471 | 474 |
472 default: | 475 default: |
473 runtime·throw("scanblock: invalid GC instruction"); | 476 runtime·throw("scanblock: invalid GC instruction"); |
474 return; | 477 return; |
475 } | 478 } |
(...skipping 698 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1174 int32 i; | 1177 int32 i; |
1175 uint64 stacks_inuse; | 1178 uint64 stacks_inuse; |
1176 uint64 *src, *dst; | 1179 uint64 *src, *dst; |
1177 | 1180 |
1178 if(stats) | 1181 if(stats) |
1179 runtime·memclr((byte*)stats, sizeof(*stats)); | 1182 runtime·memclr((byte*)stats, sizeof(*stats)); |
1180 stacks_inuse = 0; | 1183 stacks_inuse = 0; |
1181 for(mp=runtime·allm; mp; mp=mp->alllink) { | 1184 for(mp=runtime·allm; mp; mp=mp->alllink) { |
1182 c = mp->mcache; | 1185 c = mp->mcache; |
1183 runtime·purgecachedstats(c); | 1186 runtime·purgecachedstats(c); |
1184 » » //stacks_inuse += mp->stackalloc->inuse; | 1187 » » stacks_inuse += mp->stackinuse*FixedStack; |
1185 if(stats) { | 1188 if(stats) { |
1186 src = (uint64*)&mp->gcstats; | 1189 src = (uint64*)&mp->gcstats; |
1187 dst = (uint64*)stats; | 1190 dst = (uint64*)stats; |
1188 for(i=0; i<sizeof(*stats)/sizeof(uint64); i++) | 1191 for(i=0; i<sizeof(*stats)/sizeof(uint64); i++) |
1189 dst[i] += src[i]; | 1192 dst[i] += src[i]; |
1190 runtime·memclr((byte*)&mp->gcstats, sizeof(mp->gcstats))
; | 1193 runtime·memclr((byte*)&mp->gcstats, sizeof(mp->gcstats))
; |
1191 } | 1194 } |
1192 for(i=0; i<nelem(c->local_by_size); i++) { | 1195 for(i=0; i<nelem(c->local_by_size); i++) { |
1193 mstats.by_size[i].nmalloc += c->local_by_size[i].nmalloc
; | 1196 mstats.by_size[i].nmalloc += c->local_by_size[i].nmalloc
; |
1194 c->local_by_size[i].nmalloc = 0; | 1197 c->local_by_size[i].nmalloc = 0; |
(...skipping 445 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1640 uintptr n; | 1643 uintptr n; |
1641 | 1644 |
1642 n = (h->arena_used - h->arena_start) / wordsPerBitmapWord; | 1645 n = (h->arena_used - h->arena_start) / wordsPerBitmapWord; |
1643 n = (n+bitmapChunk-1) & ~(bitmapChunk-1); | 1646 n = (n+bitmapChunk-1) & ~(bitmapChunk-1); |
1644 if(h->bitmap_mapped >= n) | 1647 if(h->bitmap_mapped >= n) |
1645 return; | 1648 return; |
1646 | 1649 |
1647 runtime·SysMap(h->arena_start - n, n - h->bitmap_mapped); | 1650 runtime·SysMap(h->arena_start - n, n - h->bitmap_mapped); |
1648 h->bitmap_mapped = n; | 1651 h->bitmap_mapped = n; |
1649 } | 1652 } |
LEFT | RIGHT |