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 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
46 // | 46 // |
47 #define bitAllocated ((uintptr)1<<(bitShift*0)) | 47 #define bitAllocated ((uintptr)1<<(bitShift*0)) |
48 #define bitNoPointers ((uintptr)1<<(bitShift*1)) /* when bitAlloc
ated is set */ | 48 #define bitNoPointers ((uintptr)1<<(bitShift*1)) /* when bitAlloc
ated is set */ |
49 #define bitMarked ((uintptr)1<<(bitShift*2)) /* when bitAlloc
ated is set */ | 49 #define bitMarked ((uintptr)1<<(bitShift*2)) /* when bitAlloc
ated is set */ |
50 #define bitSpecial ((uintptr)1<<(bitShift*3)) /* when bitAlloc
ated is set - has finalizer or being profiled */ | 50 #define bitSpecial ((uintptr)1<<(bitShift*3)) /* when bitAlloc
ated is set - has finalizer or being profiled */ |
51 #define bitBlockBoundary ((uintptr)1<<(bitShift*1)) /* when bitAlloc
ated is NOT set */ | 51 #define bitBlockBoundary ((uintptr)1<<(bitShift*1)) /* when bitAlloc
ated is NOT set */ |
52 | 52 |
53 #define bitMask (bitBlockBoundary | bitAllocated | bitMarked | bitSpecial) | 53 #define bitMask (bitBlockBoundary | bitAllocated | bitMarked | bitSpecial) |
54 | 54 |
55 // TODO: Make these per-M. | 55 // TODO: Make these per-M. |
56 static uint64 nlookup; | |
57 static uint64 nsizelookup; | |
58 static uint64 naddrlookup; | |
59 static uint64 nhandoff; | 56 static uint64 nhandoff; |
60 | 57 |
61 static int32 gctrace; | 58 static int32 gctrace; |
62 | 59 |
63 typedef struct Workbuf Workbuf; | 60 typedef struct Workbuf Workbuf; |
64 struct Workbuf | 61 struct Workbuf |
65 { | 62 { |
66 Workbuf *next; | 63 Workbuf *next; |
67 uintptr nobj; | 64 uintptr nobj; |
68 byte *obj[512-2]; | 65 byte *obj[512-2]; |
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
205 if(((xbits>>j) & (bitAllocated|bitBlockBoundary)
) != 0) { | 202 if(((xbits>>j) & (bitAllocated|bitBlockBoundary)
) != 0) { |
206 obj = (byte*)obj - (shift-j)*PtrSize; | 203 obj = (byte*)obj - (shift-j)*PtrSize; |
207 shift = j; | 204 shift = j; |
208 bits = xbits>>shift; | 205 bits = xbits>>shift; |
209 goto found; | 206 goto found; |
210 } | 207 } |
211 } | 208 } |
212 | 209 |
213 // Otherwise consult span table to find beginning. | 210 // Otherwise consult span table to find beginning. |
214 // (Manually inlined copy of MHeap_LookupMaybe.) | 211 // (Manually inlined copy of MHeap_LookupMaybe.) |
215 nlookup++; | |
216 naddrlookup++; | |
217 k = (uintptr)obj>>PageShift; | 212 k = (uintptr)obj>>PageShift; |
218 x = k; | 213 x = k; |
219 if(sizeof(void*) == 8) | 214 if(sizeof(void*) == 8) |
220 x -= (uintptr)arena_start>>PageShift; | 215 x -= (uintptr)arena_start>>PageShift; |
221 s = runtime·mheap.map[x]; | 216 s = runtime·mheap.map[x]; |
222 if(s == nil || k < s->start || k - s->start >= s->npages
|| s->state != MSpanInUse) | 217 if(s == nil || k < s->start || k - s->start >= s->npages
|| s->state != MSpanInUse) |
223 continue; | 218 continue; |
224 p = (byte*)((uintptr)s->start<<PageShift); | 219 p = (byte*)((uintptr)s->start<<PageShift); |
225 if(s->sizeclass == 0) { | 220 if(s->sizeclass == 0) { |
226 obj = p; | 221 obj = p; |
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
294 // Emptied our buffer: refill. | 289 // Emptied our buffer: refill. |
295 wbuf = getfull(wbuf); | 290 wbuf = getfull(wbuf); |
296 if(wbuf == nil) | 291 if(wbuf == nil) |
297 return; | 292 return; |
298 nobj = wbuf->nobj; | 293 nobj = wbuf->nobj; |
299 wp = wbuf->obj + wbuf->nobj; | 294 wp = wbuf->obj + wbuf->nobj; |
300 } | 295 } |
301 b = *--wp; | 296 b = *--wp; |
302 nobj--; | 297 nobj--; |
303 | 298 |
304 » » // Figure out n = size of b. Start by loading bits for b. | 299 » » // Ask span about size class. |
305 » » off = (uintptr*)b - (uintptr*)arena_start; | |
306 » » bitp = (uintptr*)arena_start - off/wordsPerBitmapWord - 1; | |
307 » » shift = off % wordsPerBitmapWord; | |
308 » » xbits = *bitp; | |
309 » » bits = xbits >> shift; | |
310 | |
311 » » // Might be small; look for nearby block boundary. | |
312 » » // A block boundary is marked by either bitBlockBoundary | |
313 » » // or bitAllocated being set (see notes near their definition). | |
314 » » enum { | |
315 » » » boundary = bitBlockBoundary|bitAllocated | |
316 » » }; | |
317 » » // Look for a block boundary both after and before b | |
318 » » // in the same bitmap word. | |
319 » » // | |
320 » » // A block boundary j words after b is indicated by | |
321 » » //» bits>>j & boundary | |
322 » » // assuming shift+j < bitShift. (If shift+j >= bitShift then | |
323 » » // we'll be bleeding other bit types like bitMarked into our tes
t.) | |
324 » » // Instead of inserting the conditional shift+j < bitShift into
the loop, | |
325 » » // we can let j range from 1 to bitShift as long as we first | |
326 » » // apply a mask to keep only the bits corresponding | |
327 » » // to shift+j < bitShift aka j < bitShift-shift. | |
328 » » bits &= (boundary<<(bitShift-shift)) - boundary; | |
329 | |
330 » » // A block boundary j words before b is indicated by | |
331 » » //» xbits>>(shift-j) & boundary | |
332 » » // (assuming shift >= j). There is no cleverness here | |
333 » » // avoid the test, because when j gets too large the shift | |
334 » » // turns negative, which is undefined in C. | |
335 | |
336 » » for(j=1; j<bitShift; j++) { | |
337 » » » if(((bits>>j)&boundary) != 0 || shift>=j && ((xbits>>(sh
ift-j))&boundary) != 0) { | |
338 » » » » n = j*PtrSize; | |
339 » » » » goto scan; | |
340 » » » } | |
341 » » } | |
342 | |
343 » » // Fall back to asking span about size class. | |
344 // (Manually inlined copy of MHeap_Lookup.) | 300 // (Manually inlined copy of MHeap_Lookup.) |
345 nlookup++; | |
346 nsizelookup++; | |
347 x = (uintptr)b>>PageShift; | 301 x = (uintptr)b>>PageShift; |
348 if(sizeof(void*) == 8) | 302 if(sizeof(void*) == 8) |
349 x -= (uintptr)arena_start>>PageShift; | 303 x -= (uintptr)arena_start>>PageShift; |
350 s = runtime·mheap.map[x]; | 304 s = runtime·mheap.map[x]; |
351 if(s->sizeclass == 0) | 305 if(s->sizeclass == 0) |
352 n = s->npages<<PageShift; | 306 n = s->npages<<PageShift; |
353 else | 307 else |
354 n = runtime·class_to_size[s->sizeclass]; | 308 n = runtime·class_to_size[s->sizeclass]; |
355 scan:; | |
356 } | 309 } |
357 } | 310 } |
358 | 311 |
359 // debug_scanblock is the debug copy of scanblock. | 312 // debug_scanblock is the debug copy of scanblock. |
360 // it is simpler, slower, single-threaded, recursive, | 313 // it is simpler, slower, single-threaded, recursive, |
361 // and uses bitSpecial as the mark bit. | 314 // and uses bitSpecial as the mark bit. |
362 static void | 315 static void |
363 debug_scanblock(byte *b, int64 n) | 316 debug_scanblock(byte *b, int64 n) |
364 { | 317 { |
365 byte *obj, *p; | 318 byte *obj, *p; |
(...skipping 587 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
953 if(gcpercent < 0) | 906 if(gcpercent < 0) |
954 return; | 907 return; |
955 | 908 |
956 runtime·semacquire(&gcsema); | 909 runtime·semacquire(&gcsema); |
957 if(!force && mstats.heap_alloc < mstats.next_gc) { | 910 if(!force && mstats.heap_alloc < mstats.next_gc) { |
958 runtime·semrelease(&gcsema); | 911 runtime·semrelease(&gcsema); |
959 return; | 912 return; |
960 } | 913 } |
961 | 914 |
962 t0 = runtime·nanotime(); | 915 t0 = runtime·nanotime(); |
963 nlookup = 0; | |
964 nsizelookup = 0; | |
965 naddrlookup = 0; | |
966 nhandoff = 0; | 916 nhandoff = 0; |
967 | 917 |
968 m->gcing = 1; | 918 m->gcing = 1; |
969 runtime·stoptheworld(); | 919 runtime·stoptheworld(); |
970 | 920 |
971 cachestats(); | 921 cachestats(); |
972 heap0 = mstats.heap_alloc; | 922 heap0 = mstats.heap_alloc; |
973 obj0 = mstats.nmalloc - mstats.nfree; | 923 obj0 = mstats.nmalloc - mstats.nfree; |
974 | 924 |
975 runtime·lock(&work.markgate); | 925 runtime·lock(&work.markgate); |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1021 | 971 |
1022 t3 = runtime·nanotime(); | 972 t3 = runtime·nanotime(); |
1023 mstats.last_gc = t3; | 973 mstats.last_gc = t3; |
1024 mstats.pause_ns[mstats.numgc%nelem(mstats.pause_ns)] = t3 - t0; | 974 mstats.pause_ns[mstats.numgc%nelem(mstats.pause_ns)] = t3 - t0; |
1025 mstats.pause_total_ns += t3 - t0; | 975 mstats.pause_total_ns += t3 - t0; |
1026 mstats.numgc++; | 976 mstats.numgc++; |
1027 if(mstats.debuggc) | 977 if(mstats.debuggc) |
1028 runtime·printf("pause %D\n", t3-t0); | 978 runtime·printf("pause %D\n", t3-t0); |
1029 | 979 |
1030 if(gctrace) { | 980 if(gctrace) { |
1031 » » runtime·printf("gc%d(%d): %D+%D+%D ms %D -> %D MB %D -> %D (%D-%
D) objects %D pointer lookups (%D size, %D addr) %D handoff\n", | 981 » » runtime·printf("gc%d(%d): %D+%D+%D ms %D -> %D MB %D -> %D (%D-%
D) objects %D handoff\n", |
1032 mstats.numgc, work.nproc, (t1-t0)/1000000, (t2-t1)/10000
00, (t3-t2)/1000000, | 982 mstats.numgc, work.nproc, (t1-t0)/1000000, (t2-t1)/10000
00, (t3-t2)/1000000, |
1033 heap0>>20, heap1>>20, obj0, obj1, | 983 heap0>>20, heap1>>20, obj0, obj1, |
1034 mstats.nmalloc, mstats.nfree, | 984 mstats.nmalloc, mstats.nfree, |
1035 » » » nlookup, nsizelookup, naddrlookup, nhandoff); | 985 » » » nhandoff); |
1036 } | 986 } |
1037 | 987 |
1038 runtime·semrelease(&gcsema); | 988 runtime·semrelease(&gcsema); |
1039 | 989 |
1040 // If we could have used another helper proc, start one now, | 990 // If we could have used another helper proc, start one now, |
1041 // in the hope that it will be available next time. | 991 // in the hope that it will be available next time. |
1042 // It would have been even better to start it before the collection, | 992 // It would have been even better to start it before the collection, |
1043 // but doing so requires allocating memory, so it's tricky to | 993 // but doing so requires allocating memory, so it's tricky to |
1044 // coordinate. This lazy approach works out in practice: | 994 // coordinate. This lazy approach works out in practice: |
1045 // we don't mind if the first couple gc rounds don't have quite | 995 // we don't mind if the first couple gc rounds don't have quite |
1046 // the maximum number of procs. | 996 // the maximum number of procs. |
1047 runtime·starttheworld(extra); | 997 runtime·starttheworld(extra); |
1048 | 998 |
1049 // give the queued finalizers, if any, a chance to run·· | 999 // give the queued finalizers, if any, a chance to run·· |
1050 if(finq != nil)· | 1000 if(finq != nil)· |
1051 runtime·gosched(); | 1001 runtime·gosched(); |
1052 | 1002 |
1053 if(gctrace > 1 && !force) | 1003 if(gctrace > 1 && !force) |
1054 runtime·gc(1); | 1004 runtime·gc(1); |
1055 } | 1005 } |
1056 | 1006 |
1057 void | 1007 void |
1058 runtime·UpdateMemStats(void) | 1008 runtime·ReadMemStats(MStats *stats) |
1059 { | 1009 { |
1060 // Have to acquire gcsema to stop the world, | 1010 // Have to acquire gcsema to stop the world, |
1061 // because stoptheworld can only be used by | 1011 // because stoptheworld can only be used by |
1062 // one goroutine at a time, and there might be | 1012 // one goroutine at a time, and there might be |
1063 // a pending garbage collection already calling it. | 1013 // a pending garbage collection already calling it. |
1064 runtime·semacquire(&gcsema); | 1014 runtime·semacquire(&gcsema); |
1065 m->gcing = 1; | 1015 m->gcing = 1; |
1066 runtime·stoptheworld(); | 1016 runtime·stoptheworld(); |
1067 cachestats(); | 1017 cachestats(); |
| 1018 *stats = mstats; |
1068 m->gcing = 0; | 1019 m->gcing = 0; |
1069 runtime·semrelease(&gcsema); | 1020 runtime·semrelease(&gcsema); |
1070 runtime·starttheworld(false); | 1021 runtime·starttheworld(false); |
1071 } | 1022 } |
1072 | 1023 |
1073 static void | 1024 static void |
1074 runfinq(void) | 1025 runfinq(void) |
1075 { | 1026 { |
1076 Finalizer *f; | 1027 Finalizer *f; |
1077 FinBlock *fb, *next; | 1028 FinBlock *fb, *next; |
(...skipping 237 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1315 uintptr n; | 1266 uintptr n; |
1316 | 1267 |
1317 n = (h->arena_used - h->arena_start) / wordsPerBitmapWord; | 1268 n = (h->arena_used - h->arena_start) / wordsPerBitmapWord; |
1318 n = (n+bitmapChunk-1) & ~(bitmapChunk-1); | 1269 n = (n+bitmapChunk-1) & ~(bitmapChunk-1); |
1319 if(h->bitmap_mapped >= n) | 1270 if(h->bitmap_mapped >= n) |
1320 return; | 1271 return; |
1321 | 1272 |
1322 runtime·SysMap(h->arena_start - n, n - h->bitmap_mapped); | 1273 runtime·SysMap(h->arena_start - n, n - h->bitmap_mapped); |
1323 h->bitmap_mapped = n; | 1274 h->bitmap_mapped = n; |
1324 } | 1275 } |
LEFT | RIGHT |