/
sgen-marksweep.c
2048 lines (1701 loc) · 58.6 KB
/
sgen-marksweep.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* sgen-marksweep.c: The Mark & Sweep major collector.
*
* Author:
* Mark Probst <mark.probst@gmail.com>
*
* Copyright 2009-2010 Novell, Inc.
* Copyright (C) 2012 Xamarin Inc
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License 2.0 as published by the Free Software Foundation;
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License 2.0 along with this library; if not, write to the Free
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#include "config.h"
#ifdef HAVE_SGEN_GC
#include <math.h>
#include <errno.h>
#include "utils/mono-counters.h"
#include "utils/mono-semaphore.h"
#include "utils/mono-time.h"
#include "metadata/object-internals.h"
#include "metadata/profiler-private.h"
#include "metadata/sgen-gc.h"
#include "metadata/sgen-protocol.h"
#include "metadata/sgen-cardtable.h"
#include "metadata/sgen-memory-governor.h"
#include "metadata/sgen-layout-stats.h"
#include "metadata/gc-internal.h"
#include "metadata/sgen-pointer-queue.h"
#include "metadata/sgen-pinning.h"
#include "metadata/sgen-workers.h"
#if defined(ARCH_MIN_MS_BLOCK_SIZE) && defined(ARCH_MIN_MS_BLOCK_SIZE_SHIFT)
#define MS_BLOCK_SIZE ARCH_MIN_MS_BLOCK_SIZE
#define MS_BLOCK_SIZE_SHIFT ARCH_MIN_MS_BLOCK_SIZE_SHIFT
#else
#define MS_BLOCK_SIZE_SHIFT 14 /* INT FASTENABLE */
#define MS_BLOCK_SIZE (1 << MS_BLOCK_SIZE_SHIFT)
#endif
#define MAJOR_SECTION_SIZE MS_BLOCK_SIZE
#define CARDS_PER_BLOCK (MS_BLOCK_SIZE / CARD_SIZE_IN_BYTES)
/*
* Don't allocate single blocks, but alloc a contingent of this many
* blocks in one swoop. This must be a power of two.
*/
#define MS_BLOCK_ALLOC_NUM 32
/*
* Number of bytes before the first object in a block. At the start
* of a block is the MSBlockHeader, then opional padding, then come
* the objects, so this must be >= sizeof (MSBlockHeader).
*/
#define MS_BLOCK_SKIP ((sizeof (MSBlockHeader) + 15) & ~15)
#define MS_BLOCK_FREE (MS_BLOCK_SIZE - MS_BLOCK_SKIP)
#define MS_NUM_MARK_WORDS ((MS_BLOCK_SIZE / SGEN_ALLOC_ALIGN + sizeof (mword) * 8 - 1) / (sizeof (mword) * 8))
typedef struct _MSBlockInfo MSBlockInfo;
struct _MSBlockInfo {
int obj_size;
int obj_size_index;
unsigned int pinned : 1;
unsigned int has_references : 1;
unsigned int has_pinned : 1; /* means cannot evacuate */
unsigned int is_to_space : 1;
unsigned int swept : 1;
void **free_list;
MSBlockInfo *next_free;
size_t pin_queue_first_entry;
size_t pin_queue_last_entry;
guint8 *cardtable_mod_union;
mword mark_words [MS_NUM_MARK_WORDS];
};
#define MS_BLOCK_FOR_BLOCK_INFO(b) ((char*)(b))
#define MS_BLOCK_OBJ(b,i) (MS_BLOCK_FOR_BLOCK_INFO(b) + MS_BLOCK_SKIP + (b)->obj_size * (i))
#define MS_BLOCK_OBJ_FOR_SIZE(b,i,obj_size) (MS_BLOCK_FOR_BLOCK_INFO(b) + MS_BLOCK_SKIP + (obj_size) * (i))
#define MS_BLOCK_DATA_FOR_OBJ(o) ((char*)((mword)(o) & ~(mword)(MS_BLOCK_SIZE - 1)))
typedef struct {
MSBlockInfo info;
} MSBlockHeader;
#define MS_BLOCK_FOR_OBJ(o) (&((MSBlockHeader*)MS_BLOCK_DATA_FOR_OBJ ((o)))->info)
/* object index will always be small */
#define MS_BLOCK_OBJ_INDEX(o,b) ((int)(((char*)(o) - (MS_BLOCK_FOR_BLOCK_INFO(b) + MS_BLOCK_SKIP)) / (b)->obj_size))
//casting to int is fine since blocks are 32k
#define MS_CALC_MARK_BIT(w,b,o) do { \
int i = ((int)((char*)(o) - MS_BLOCK_DATA_FOR_OBJ ((o)))) >> SGEN_ALLOC_ALIGN_BITS; \
if (sizeof (mword) == 4) { \
(w) = i >> 5; \
(b) = i & 31; \
} else { \
(w) = i >> 6; \
(b) = i & 63; \
} \
} while (0)
#define MS_MARK_BIT(bl,w,b) ((bl)->mark_words [(w)] & (ONE_P << (b)))
#define MS_SET_MARK_BIT(bl,w,b) ((bl)->mark_words [(w)] |= (ONE_P << (b)))
#define MS_OBJ_ALLOCED(o,b) (*(void**)(o) && (*(char**)(o) < MS_BLOCK_FOR_BLOCK_INFO (b) || *(char**)(o) >= MS_BLOCK_FOR_BLOCK_INFO (b) + MS_BLOCK_SIZE))
#define MS_BLOCK_OBJ_SIZE_FACTOR (pow (2.0, 1.0 / 3))
/*
* This way we can lookup block object size indexes for sizes up to
* 256 bytes with a single load.
*/
#define MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES 32
static int *block_obj_sizes;
static int num_block_obj_sizes;
static int fast_block_obj_size_indexes [MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES];
#define MS_BLOCK_FLAG_PINNED 1
#define MS_BLOCK_FLAG_REFS 2
#define MS_BLOCK_TYPE_MAX 4
static gboolean *evacuate_block_obj_sizes;
static float evacuation_threshold = 0.666f;
static float concurrent_evacuation_threshold = 0.666f;
static gboolean want_evacuation = FALSE;
static gboolean lazy_sweep = TRUE;
static gboolean have_swept;
static gboolean concurrent_mark;
#define BLOCK_IS_TAGGED_HAS_REFERENCES(bl) SGEN_POINTER_IS_TAGGED_1 ((bl))
#define BLOCK_TAG_HAS_REFERENCES(bl) SGEN_POINTER_TAG_1 ((bl))
#define BLOCK_UNTAG_HAS_REFERENCES(bl) SGEN_POINTER_UNTAG_1 ((bl))
#define BLOCK_TAG(bl) ((bl)->has_references ? BLOCK_TAG_HAS_REFERENCES ((bl)) : (bl))
/* all allocated blocks in the system */
static SgenPointerQueue allocated_blocks;
/* non-allocated block free-list */
static void *empty_blocks = NULL;
static size_t num_empty_blocks = 0;
#define FOREACH_BLOCK(bl) { size_t __index; for (__index = 0; __index < allocated_blocks.next_slot; ++__index) { (bl) = BLOCK_UNTAG_HAS_REFERENCES (allocated_blocks.data [__index]);
#define FOREACH_BLOCK_HAS_REFERENCES(bl,hr) { size_t __index; for (__index = 0; __index < allocated_blocks.next_slot; ++__index) { (bl) = allocated_blocks.data [__index]; (hr) = BLOCK_IS_TAGGED_HAS_REFERENCES ((bl)); (bl) = BLOCK_UNTAG_HAS_REFERENCES ((bl));
#define END_FOREACH_BLOCK } }
#define DELETE_BLOCK_IN_FOREACH() (allocated_blocks.data [__index] = NULL)
static size_t num_major_sections = 0;
/* one free block list for each block object size */
static MSBlockInfo **free_block_lists [MS_BLOCK_TYPE_MAX];
static guint64 stat_major_blocks_alloced = 0;
static guint64 stat_major_blocks_freed = 0;
static guint64 stat_major_blocks_lazy_swept = 0;
static guint64 stat_major_objects_evacuated = 0;
#if SIZEOF_VOID_P != 8
static guint64 stat_major_blocks_freed_ideal = 0;
static guint64 stat_major_blocks_freed_less_ideal = 0;
static guint64 stat_major_blocks_freed_individual = 0;
static guint64 stat_major_blocks_alloced_less_ideal = 0;
#endif
#ifdef SGEN_COUNT_NUMBER_OF_MAJOR_OBJECTS_MARKED
static guint64 num_major_objects_marked = 0;
#define INC_NUM_MAJOR_OBJECTS_MARKED() (++num_major_objects_marked)
#else
#define INC_NUM_MAJOR_OBJECTS_MARKED()
#endif
#ifdef SGEN_HEAVY_BINARY_PROTOCOL
static mono_mutex_t scanned_objects_list_lock;
static SgenPointerQueue scanned_objects_list;
static void
add_scanned_object (void *ptr)
{
if (!binary_protocol_is_enabled ())
return;
mono_mutex_lock (&scanned_objects_list_lock);
sgen_pointer_queue_add (&scanned_objects_list, ptr);
mono_mutex_unlock (&scanned_objects_list_lock);
}
#endif
static void
sweep_block (MSBlockInfo *block, gboolean during_major_collection);
static int
ms_find_block_obj_size_index (size_t size)
{
int i;
SGEN_ASSERT (9, size <= SGEN_MAX_SMALL_OBJ_SIZE, "size %d is bigger than max small object size %d", size, SGEN_MAX_SMALL_OBJ_SIZE);
for (i = 0; i < num_block_obj_sizes; ++i)
if (block_obj_sizes [i] >= size)
return i;
g_error ("no object of size %d\n", size);
}
#define FREE_BLOCKS_FROM(lists,p,r) (lists [((p) ? MS_BLOCK_FLAG_PINNED : 0) | ((r) ? MS_BLOCK_FLAG_REFS : 0)])
#define FREE_BLOCKS(p,r) (FREE_BLOCKS_FROM (free_block_lists, (p), (r)))
#define MS_BLOCK_OBJ_SIZE_INDEX(s) \
(((s)+7)>>3 < MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES ? \
fast_block_obj_size_indexes [((s)+7)>>3] : \
ms_find_block_obj_size_index ((s)))
static void*
major_alloc_heap (mword nursery_size, mword nursery_align, int the_nursery_bits)
{
char *start;
if (nursery_align)
start = sgen_alloc_os_memory_aligned (nursery_size, nursery_align, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, "nursery");
else
start = sgen_alloc_os_memory (nursery_size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, "nursery");
return start;
}
static void
update_heap_boundaries_for_block (MSBlockInfo *block)
{
sgen_update_heap_boundaries ((mword)MS_BLOCK_FOR_BLOCK_INFO (block), (mword)MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE);
}
static void*
ms_get_empty_block (void)
{
char *p;
int i;
void *block, *empty, *next;
retry:
if (!empty_blocks) {
/*
* We try allocating MS_BLOCK_ALLOC_NUM blocks first. If that's
* unsuccessful, we halve the number of blocks and try again, until we're at
* 1. If that doesn't work, either, we assert.
*/
int alloc_num = MS_BLOCK_ALLOC_NUM;
for (;;) {
p = sgen_alloc_os_memory_aligned (MS_BLOCK_SIZE * alloc_num, MS_BLOCK_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE,
alloc_num == 1 ? "major heap section" : NULL);
if (p)
break;
alloc_num >>= 1;
}
for (i = 0; i < alloc_num; ++i) {
block = p;
/*
* We do the free list update one after the
* other so that other threads can use the new
* blocks as quickly as possible.
*/
do {
empty = empty_blocks;
*(void**)block = empty;
} while (SGEN_CAS_PTR ((gpointer*)&empty_blocks, block, empty) != empty);
p += MS_BLOCK_SIZE;
}
SGEN_ATOMIC_ADD_P (num_empty_blocks, alloc_num);
stat_major_blocks_alloced += alloc_num;
#if SIZEOF_VOID_P != 8
if (alloc_num != MS_BLOCK_ALLOC_NUM)
stat_major_blocks_alloced_less_ideal += alloc_num;
#endif
}
do {
empty = empty_blocks;
if (!empty)
goto retry;
block = empty;
next = *(void**)block;
} while (SGEN_CAS_PTR (&empty_blocks, next, empty) != empty);
SGEN_ATOMIC_ADD_P (num_empty_blocks, -1);
*(void**)block = NULL;
g_assert (!((mword)block & (MS_BLOCK_SIZE - 1)));
return block;
}
static void
ms_free_block (void *block)
{
void *empty;
sgen_memgov_release_space (MS_BLOCK_SIZE, SPACE_MAJOR);
memset (block, 0, MS_BLOCK_SIZE);
do {
empty = empty_blocks;
*(void**)block = empty;
} while (SGEN_CAS_PTR (&empty_blocks, block, empty) != empty);
SGEN_ATOMIC_ADD_P (num_empty_blocks, 1);
}
//#define MARKSWEEP_CONSISTENCY_CHECK
#ifdef MARKSWEEP_CONSISTENCY_CHECK
static void
check_block_free_list (MSBlockInfo *block, int size, gboolean pinned)
{
MSBlockInfo *b;
for (; block; block = block->next_free) {
g_assert (block->obj_size == size);
g_assert ((pinned && block->pinned) || (!pinned && !block->pinned));
/* blocks in the free lists must have at least
one free slot */
if (block->swept)
g_assert (block->free_list);
/* the block must be in the allocated_blocks array */
g_assert (sgen_pointer_queue_find (&allocated_blocks, BLOCK_TAG (block)) != (size_t)-1);
}
}
static void
check_empty_blocks (void)
{
void *p;
size_t i = 0;
for (p = empty_blocks; p; p = *(void**)p)
++i;
g_assert (i == num_empty_blocks);
}
static void
consistency_check (void)
{
MSBlockInfo *block;
int i;
/* check all blocks */
FOREACH_BLOCK (block) {
int count = MS_BLOCK_FREE / block->obj_size;
int num_free = 0;
void **free;
/* check block header */
g_assert (((MSBlockHeader*)block->block)->info == block);
/* count number of free slots */
for (i = 0; i < count; ++i) {
void **obj = (void**) MS_BLOCK_OBJ (block, i);
if (!MS_OBJ_ALLOCED (obj, block))
++num_free;
}
/* check free list */
for (free = block->free_list; free; free = (void**)*free) {
g_assert (MS_BLOCK_FOR_OBJ (free) == block);
--num_free;
}
g_assert (num_free == 0);
/* check all mark words are zero */
if (block->swept) {
for (i = 0; i < MS_NUM_MARK_WORDS; ++i)
g_assert (block->mark_words [i] == 0);
}
} END_FOREACH_BLOCK;
/* check free blocks */
for (i = 0; i < num_block_obj_sizes; ++i) {
int j;
for (j = 0; j < MS_BLOCK_TYPE_MAX; ++j)
check_block_free_list (free_block_lists [j][i], block_obj_sizes [i], j & MS_BLOCK_FLAG_PINNED);
}
check_empty_blocks ();
}
#endif
static gboolean
ms_alloc_block (int size_index, gboolean pinned, gboolean has_references)
{
int size = block_obj_sizes [size_index];
int count = MS_BLOCK_FREE / size;
MSBlockInfo *info;
MSBlockInfo **free_blocks = FREE_BLOCKS (pinned, has_references);
char *obj_start;
int i;
if (!sgen_memgov_try_alloc_space (MS_BLOCK_SIZE, SPACE_MAJOR))
return FALSE;
info = (MSBlockInfo*)ms_get_empty_block ();
SGEN_ASSERT (9, count >= 2, "block with %d objects, it must hold at least 2", count);
info->obj_size = size;
info->obj_size_index = size_index;
info->pinned = pinned;
info->has_references = has_references;
info->has_pinned = pinned;
/*
* Blocks that are to-space are not evacuated from. During an major collection
* blocks are allocated for two reasons: evacuating objects from the nursery and
* evacuating them from major blocks marked for evacuation. In both cases we don't
* want further evacuation.
*/
info->is_to_space = (sgen_get_current_collection_generation () == GENERATION_OLD);
info->swept = 1;
info->cardtable_mod_union = NULL;
update_heap_boundaries_for_block (info);
/* build free list */
obj_start = MS_BLOCK_FOR_BLOCK_INFO (info) + MS_BLOCK_SKIP;
info->free_list = (void**)obj_start;
/* we're skipping the last one - it must be nulled */
for (i = 0; i < count - 1; ++i) {
char *next_obj_start = obj_start + size;
*(void**)obj_start = next_obj_start;
obj_start = next_obj_start;
}
/* the last one */
*(void**)obj_start = NULL;
info->next_free = free_blocks [size_index];
free_blocks [size_index] = info;
sgen_pointer_queue_add (&allocated_blocks, BLOCK_TAG (info));
++num_major_sections;
return TRUE;
}
static gboolean
obj_is_from_pinned_alloc (char *ptr)
{
MSBlockInfo *block;
FOREACH_BLOCK (block) {
if (ptr >= MS_BLOCK_FOR_BLOCK_INFO (block) && ptr <= MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE)
return block->pinned;
} END_FOREACH_BLOCK;
return FALSE;
}
static void*
unlink_slot_from_free_list_uncontested (MSBlockInfo **free_blocks, int size_index)
{
MSBlockInfo *block;
void *obj;
block = free_blocks [size_index];
SGEN_ASSERT (9, block, "no free block to unlink from free_blocks %p size_index %d", free_blocks, size_index);
if (G_UNLIKELY (!block->swept)) {
stat_major_blocks_lazy_swept ++;
sweep_block (block, FALSE);
}
obj = block->free_list;
SGEN_ASSERT (9, obj, "block %p in free list had no available object to alloc from", block);
block->free_list = *(void**)obj;
if (!block->free_list) {
free_blocks [size_index] = block->next_free;
block->next_free = NULL;
}
return obj;
}
static void*
alloc_obj (MonoVTable *vtable, size_t size, gboolean pinned, gboolean has_references)
{
int size_index = MS_BLOCK_OBJ_SIZE_INDEX (size);
MSBlockInfo **free_blocks = FREE_BLOCKS (pinned, has_references);
void *obj;
if (!free_blocks [size_index]) {
if (G_UNLIKELY (!ms_alloc_block (size_index, pinned, has_references)))
return NULL;
}
obj = unlink_slot_from_free_list_uncontested (free_blocks, size_index);
*(MonoVTable**)obj = vtable;
return obj;
}
static void*
major_alloc_object (MonoVTable *vtable, size_t size, gboolean has_references)
{
return alloc_obj (vtable, size, FALSE, has_references);
}
/*
* We're not freeing the block if it's empty. We leave that work for
* the next major collection.
*
* This is just called from the domain clearing code, which runs in a
* single thread and has the GC lock, so we don't need an extra lock.
*/
static void
free_object (char *obj, size_t size, gboolean pinned)
{
MSBlockInfo *block = MS_BLOCK_FOR_OBJ (obj);
int word, bit;
if (!block->swept)
sweep_block (block, FALSE);
SGEN_ASSERT (9, (pinned && block->pinned) || (!pinned && !block->pinned), "free-object pinning mixup object %p pinned %d block %p pinned %d", obj, pinned, block, block->pinned);
SGEN_ASSERT (9, MS_OBJ_ALLOCED (obj, block), "object %p is already free", obj);
MS_CALC_MARK_BIT (word, bit, obj);
SGEN_ASSERT (9, !MS_MARK_BIT (block, word, bit), "object %p has mark bit set");
if (!block->free_list) {
MSBlockInfo **free_blocks = FREE_BLOCKS (pinned, block->has_references);
int size_index = MS_BLOCK_OBJ_SIZE_INDEX (size);
SGEN_ASSERT (9, !block->next_free, "block %p doesn't have a free-list of object but belongs to a free-list of blocks");
block->next_free = free_blocks [size_index];
free_blocks [size_index] = block;
}
memset (obj, 0, size);
*(void**)obj = block->free_list;
block->free_list = (void**)obj;
}
static void
major_free_non_pinned_object (char *obj, size_t size)
{
free_object (obj, size, FALSE);
}
/* size is a multiple of SGEN_ALLOC_ALIGN */
static void*
major_alloc_small_pinned_obj (MonoVTable *vtable, size_t size, gboolean has_references)
{
void *res;
res = alloc_obj (vtable, size, TRUE, has_references);
/*If we failed to alloc memory, we better try releasing memory
*as pinned alloc is requested by the runtime.
*/
if (!res) {
sgen_perform_collection (0, GENERATION_OLD, "pinned alloc failure", TRUE);
res = alloc_obj (vtable, size, TRUE, has_references);
}
return res;
}
static void
free_pinned_object (char *obj, size_t size)
{
free_object (obj, size, TRUE);
}
/*
* size is already rounded up and we hold the GC lock.
*/
static void*
major_alloc_degraded (MonoVTable *vtable, size_t size)
{
void *obj;
size_t old_num_sections;
old_num_sections = num_major_sections;
obj = alloc_obj (vtable, size, FALSE, SGEN_VTABLE_HAS_REFERENCES (vtable));
if (G_LIKELY (obj)) {
HEAVY_STAT (++stat_objects_alloced_degraded);
HEAVY_STAT (stat_bytes_alloced_degraded += size);
g_assert (num_major_sections >= old_num_sections);
sgen_register_major_sections_alloced (num_major_sections - old_num_sections);
}
return obj;
}
/*
* obj is some object. If it's not in the major heap (i.e. if it's in
* the nursery or LOS), return FALSE. Otherwise return whether it's
* been marked or copied.
*/
static gboolean
major_is_object_live (char *obj)
{
MSBlockInfo *block;
int word, bit;
mword objsize;
if (sgen_ptr_in_nursery (obj))
return FALSE;
objsize = SGEN_ALIGN_UP (sgen_safe_object_get_size ((MonoObject*)obj));
/* LOS */
if (objsize > SGEN_MAX_SMALL_OBJ_SIZE)
return FALSE;
/* now we know it's in a major block */
block = MS_BLOCK_FOR_OBJ (obj);
SGEN_ASSERT (9, !block->pinned, "block %p is pinned, BTW why is this bad?");
MS_CALC_MARK_BIT (word, bit, obj);
return MS_MARK_BIT (block, word, bit) ? TRUE : FALSE;
}
static gboolean
major_ptr_is_in_non_pinned_space (char *ptr, char **start)
{
MSBlockInfo *block;
FOREACH_BLOCK (block) {
if (ptr >= MS_BLOCK_FOR_BLOCK_INFO (block) && ptr <= MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE) {
int count = MS_BLOCK_FREE / block->obj_size;
int i;
*start = NULL;
for (i = 0; i <= count; ++i) {
if (ptr >= MS_BLOCK_OBJ (block, i) && ptr < MS_BLOCK_OBJ (block, i + 1)) {
*start = MS_BLOCK_OBJ (block, i);
break;
}
}
return !block->pinned;
}
} END_FOREACH_BLOCK;
return FALSE;
}
static void
major_iterate_objects (IterateObjectsFlags flags, IterateObjectCallbackFunc callback, void *data)
{
gboolean sweep = flags & ITERATE_OBJECTS_SWEEP;
gboolean non_pinned = flags & ITERATE_OBJECTS_NON_PINNED;
gboolean pinned = flags & ITERATE_OBJECTS_PINNED;
MSBlockInfo *block;
FOREACH_BLOCK (block) {
int count = MS_BLOCK_FREE / block->obj_size;
int i;
if (block->pinned && !pinned)
continue;
if (!block->pinned && !non_pinned)
continue;
if (sweep && lazy_sweep) {
sweep_block (block, FALSE);
SGEN_ASSERT (0, block->swept, "Block must be swept after sweeping");
}
for (i = 0; i < count; ++i) {
void **obj = (void**) MS_BLOCK_OBJ (block, i);
if (!block->swept) {
int word, bit;
MS_CALC_MARK_BIT (word, bit, obj);
if (!MS_MARK_BIT (block, word, bit))
continue;
}
if (MS_OBJ_ALLOCED (obj, block))
callback ((char*)obj, block->obj_size, data);
}
} END_FOREACH_BLOCK;
}
static gboolean
major_is_valid_object (char *object)
{
MSBlockInfo *block;
FOREACH_BLOCK (block) {
int idx;
char *obj;
if ((MS_BLOCK_FOR_BLOCK_INFO (block) > object) || ((MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE) <= object))
continue;
idx = MS_BLOCK_OBJ_INDEX (object, block);
obj = (char*)MS_BLOCK_OBJ (block, idx);
if (obj != object)
return FALSE;
return MS_OBJ_ALLOCED (obj, block);
} END_FOREACH_BLOCK;
return FALSE;
}
static MonoVTable*
major_describe_pointer (char *ptr)
{
MSBlockInfo *block;
FOREACH_BLOCK (block) {
int idx;
char *obj;
gboolean live;
MonoVTable *vtable;
int w, b;
gboolean marked;
if ((MS_BLOCK_FOR_BLOCK_INFO (block) > ptr) || ((MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE) <= ptr))
continue;
SGEN_LOG (0, "major-ptr (block %p sz %d pin %d ref %d)\n",
MS_BLOCK_FOR_BLOCK_INFO (block), block->obj_size, block->pinned, block->has_references);
idx = MS_BLOCK_OBJ_INDEX (ptr, block);
obj = (char*)MS_BLOCK_OBJ (block, idx);
live = MS_OBJ_ALLOCED (obj, block);
vtable = live ? (MonoVTable*)SGEN_LOAD_VTABLE (obj) : NULL;
MS_CALC_MARK_BIT (w, b, obj);
marked = MS_MARK_BIT (block, w, b);
if (obj == ptr) {
SGEN_LOG (0, "\t(");
if (live)
SGEN_LOG (0, "object");
else
SGEN_LOG (0, "dead-object");
} else {
if (live)
SGEN_LOG (0, "interior-ptr offset %td", ptr - obj);
else
SGEN_LOG (0, "dead-interior-ptr offset %td", ptr - obj);
}
SGEN_LOG (0, " marked %d)\n", marked ? 1 : 0);
return vtable;
} END_FOREACH_BLOCK;
return NULL;
}
static void
major_check_scan_starts (void)
{
}
static void
major_dump_heap (FILE *heap_dump_file)
{
MSBlockInfo *block;
int *slots_available = alloca (sizeof (int) * num_block_obj_sizes);
int *slots_used = alloca (sizeof (int) * num_block_obj_sizes);
int i;
for (i = 0; i < num_block_obj_sizes; ++i)
slots_available [i] = slots_used [i] = 0;
FOREACH_BLOCK (block) {
int index = ms_find_block_obj_size_index (block->obj_size);
int count = MS_BLOCK_FREE / block->obj_size;
slots_available [index] += count;
for (i = 0; i < count; ++i) {
if (MS_OBJ_ALLOCED (MS_BLOCK_OBJ (block, i), block))
++slots_used [index];
}
} END_FOREACH_BLOCK;
fprintf (heap_dump_file, "<occupancies>\n");
for (i = 0; i < num_block_obj_sizes; ++i) {
fprintf (heap_dump_file, "<occupancy size=\"%d\" available=\"%d\" used=\"%d\" />\n",
block_obj_sizes [i], slots_available [i], slots_used [i]);
}
fprintf (heap_dump_file, "</occupancies>\n");
FOREACH_BLOCK (block) {
int count = MS_BLOCK_FREE / block->obj_size;
int i;
int start = -1;
fprintf (heap_dump_file, "<section type=\"%s\" size=\"%zu\">\n", "old", (size_t)MS_BLOCK_FREE);
for (i = 0; i <= count; ++i) {
if ((i < count) && MS_OBJ_ALLOCED (MS_BLOCK_OBJ (block, i), block)) {
if (start < 0)
start = i;
} else {
if (start >= 0) {
sgen_dump_occupied (MS_BLOCK_OBJ (block, start), MS_BLOCK_OBJ (block, i), MS_BLOCK_FOR_BLOCK_INFO (block));
start = -1;
}
}
}
fprintf (heap_dump_file, "</section>\n");
} END_FOREACH_BLOCK;
}
#define LOAD_VTABLE SGEN_LOAD_VTABLE
#define MS_MARK_OBJECT_AND_ENQUEUE_CHECKED(obj,desc,block,queue) do { \
int __word, __bit; \
MS_CALC_MARK_BIT (__word, __bit, (obj)); \
if (!MS_MARK_BIT ((block), __word, __bit) && MS_OBJ_ALLOCED ((obj), (block))) { \
MS_SET_MARK_BIT ((block), __word, __bit); \
if (sgen_gc_descr_has_references (desc)) \
GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
binary_protocol_mark ((obj), (gpointer)LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((MonoObject*)(obj))); \
INC_NUM_MAJOR_OBJECTS_MARKED (); \
} \
} while (0)
#define MS_MARK_OBJECT_AND_ENQUEUE(obj,desc,block,queue) do { \
int __word, __bit; \
MS_CALC_MARK_BIT (__word, __bit, (obj)); \
SGEN_ASSERT (9, MS_OBJ_ALLOCED ((obj), (block)), "object %p not allocated", obj); \
if (!MS_MARK_BIT ((block), __word, __bit)) { \
MS_SET_MARK_BIT ((block), __word, __bit); \
if (sgen_gc_descr_has_references (desc)) \
GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
binary_protocol_mark ((obj), (gpointer)LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((MonoObject*)(obj))); \
INC_NUM_MAJOR_OBJECTS_MARKED (); \
} \
} while (0)
static void
pin_major_object (char *obj, SgenGrayQueue *queue)
{
MSBlockInfo *block;
if (concurrent_mark)
g_assert_not_reached ();
block = MS_BLOCK_FOR_OBJ (obj);
block->has_pinned = TRUE;
MS_MARK_OBJECT_AND_ENQUEUE (obj, sgen_obj_get_descriptor (obj), block, queue);
}
#include "sgen-major-copy-object.h"
static void
major_copy_or_mark_object_with_evacuation_concurrent (void **ptr, void *obj, SgenGrayQueue *queue)
{
SGEN_ASSERT (9, sgen_concurrent_collection_in_progress (), "Why are we scanning concurrently when there's no concurrent collection on?");
SGEN_ASSERT (9, !sgen_workers_are_working () || sgen_is_worker_thread (mono_native_thread_id_get ()), "We must not scan from two threads at the same time!");
g_assert (!SGEN_OBJECT_IS_FORWARDED (obj));
if (!sgen_ptr_in_nursery (obj)) {
mword objsize;
objsize = SGEN_ALIGN_UP (sgen_safe_object_get_size ((MonoObject*)obj));
if (objsize <= SGEN_MAX_SMALL_OBJ_SIZE) {
MSBlockInfo *block = MS_BLOCK_FOR_OBJ (obj);
MS_MARK_OBJECT_AND_ENQUEUE (obj, sgen_obj_get_descriptor (obj), block, queue);
} else {
if (sgen_los_object_is_pinned (obj))
return;
#ifdef ENABLE_DTRACE
if (G_UNLIKELY (MONO_GC_OBJ_PINNED_ENABLED ())) {
MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
MONO_GC_OBJ_PINNED ((mword)obj, sgen_safe_object_get_size (obj), vt->klass->name_space, vt->klass->name, GENERATION_OLD);
}
#endif
sgen_los_pin_object (obj);
if (SGEN_OBJECT_HAS_REFERENCES (obj))
GRAY_OBJECT_ENQUEUE (queue, obj, sgen_obj_get_descriptor (obj));
INC_NUM_MAJOR_OBJECTS_MARKED ();
}
}
}
static long long
major_get_and_reset_num_major_objects_marked (void)
{
#ifdef SGEN_COUNT_NUMBER_OF_MAJOR_OBJECTS_MARKED
long long num = num_major_objects_marked;
num_major_objects_marked = 0;
return num;
#else
return 0;
#endif
}
#define PREFETCH_CARDS 1 /* BOOL FASTENABLE */
#if !PREFETCH_CARDS
#undef PREFETCH_CARDS
#endif
/* gcc 4.2.1 from xcode4 crashes on sgen_card_table_get_card_address () when this is enabled */
#if defined(PLATFORM_MACOSX)
#define GCC_VERSION (__GNUC__ * 10000 \
+ __GNUC_MINOR__ * 100 \
+ __GNUC_PATCHLEVEL__)
#if GCC_VERSION <= 40300
#undef PREFETCH_CARDS
#endif
#endif
#ifdef HEAVY_STATISTICS
static guint64 stat_optimized_copy;
static guint64 stat_optimized_copy_nursery;
static guint64 stat_optimized_copy_nursery_forwarded;
static guint64 stat_optimized_copy_nursery_pinned;
static guint64 stat_optimized_copy_major;
static guint64 stat_optimized_copy_major_small_fast;
static guint64 stat_optimized_copy_major_small_slow;
static guint64 stat_optimized_copy_major_large;
static guint64 stat_optimized_copy_major_forwarded;
static guint64 stat_optimized_copy_major_small_evacuate;
static guint64 stat_optimized_major_scan;
static guint64 stat_optimized_major_scan_no_refs;
static guint64 stat_drain_prefetch_fills;
static guint64 stat_drain_prefetch_fill_failures;
static guint64 stat_drain_loops;
#endif
static void major_scan_object_with_evacuation (char *start, mword desc, SgenGrayQueue *queue);
#define COPY_OR_MARK_FUNCTION_NAME major_copy_or_mark_object_no_evacuation
#define SCAN_OBJECT_FUNCTION_NAME major_scan_object_no_evacuation
#define DRAIN_GRAY_STACK_FUNCTION_NAME drain_gray_stack_no_evacuation
#include "sgen-marksweep-drain-gray-stack.h"
#define COPY_OR_MARK_WITH_EVACUATION
#define COPY_OR_MARK_FUNCTION_NAME major_copy_or_mark_object_with_evacuation
#define SCAN_OBJECT_FUNCTION_NAME major_scan_object_with_evacuation
#define DRAIN_GRAY_STACK_FUNCTION_NAME drain_gray_stack_with_evacuation
#include "sgen-marksweep-drain-gray-stack.h"
static gboolean
drain_gray_stack (ScanCopyContext ctx)
{
gboolean evacuation = FALSE;
int i;
for (i = 0; i < num_block_obj_sizes; ++i) {
if (evacuate_block_obj_sizes [i]) {
evacuation = TRUE;
break;
}
}
if (evacuation)
return drain_gray_stack_with_evacuation (ctx);
else
return drain_gray_stack_no_evacuation (ctx);
}
#include "sgen-marksweep-scan-object-concurrent.h"
static void
major_copy_or_mark_object_canonical (void **ptr, SgenGrayQueue *queue)
{
major_copy_or_mark_object_with_evacuation (ptr, *ptr, queue);
}
static void
major_copy_or_mark_object_concurrent_canonical (void **ptr, SgenGrayQueue *queue)
{
major_copy_or_mark_object_with_evacuation_concurrent (ptr, *ptr, queue);
}
static void
mark_pinned_objects_in_block (MSBlockInfo *block, SgenGrayQueue *queue)
{
void **entry, **end;
int last_index = -1;
if (block->pin_queue_first_entry == block->pin_queue_last_entry)
return;
block->has_pinned = TRUE;
entry = sgen_pinning_get_entry (block->pin_queue_first_entry);
end = sgen_pinning_get_entry (block->pin_queue_last_entry);
for (; entry < end; ++entry) {
int index = MS_BLOCK_OBJ_INDEX (*entry, block);