Merge pull request #1634 from StephenMcConnel/bug-28025
[mono.git] / mono / metadata / sgen-los.c
1 /*
2  * sgen-los.c: Large objects space.
3  *
4  * Author:
5  *      Paolo Molaro (lupus@ximian.com)
6  *
7  * Copyright 2005-2010 Novell, Inc (http://www.novell.com)
8  *
9  * Thread start/stop adapted from Boehm's GC:
10  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
11  * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
12  * Copyright (c) 1998 by Fergus Henderson.  All rights reserved.
13  * Copyright (c) 2000-2004 by Hewlett-Packard Company.  All rights reserved.
14  * Copyright 2001-2003 Ximian, Inc
15  * Copyright 2003-2010 Novell, Inc.
16  * Copyright (C) 2012 Xamarin Inc
17  *
18  * This library is free software; you can redistribute it and/or
19  * modify it under the terms of the GNU Library General Public
20  * License 2.0 as published by the Free Software Foundation;
21  *
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Library General Public License for more details.
26  *
27  * You should have received a copy of the GNU Library General Public
28  * License 2.0 along with this library; if not, write to the Free
29  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
30  */
31
32 #include "config.h"
33
34 #ifdef HAVE_SGEN_GC
35
36 #include "metadata/sgen-gc.h"
37 #include "metadata/sgen-protocol.h"
38 #include "metadata/sgen-cardtable.h"
39 #include "metadata/sgen-memory-governor.h"
40 #include "utils/mono-mmap.h"
41 #include "utils/mono-compiler.h"
42
43 #define LOS_SECTION_SIZE        (1024 * 1024)
44
45 /*
46  * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
47  * Must be at least sizeof (LOSSection).
48  */
49 #define LOS_CHUNK_SIZE          4096
50 #define LOS_CHUNK_BITS          12
51
52 /* Largest object that can be allocated in a section. */
53 #define LOS_SECTION_OBJECT_LIMIT        (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
54 //#define LOS_SECTION_OBJECT_LIMIT      0
55 #define LOS_SECTION_NUM_CHUNKS          ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
56
57 #define LOS_SECTION_FOR_OBJ(obj)        ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
58 #define LOS_CHUNK_INDEX(obj,section)    (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
59
60 #define LOS_NUM_FAST_SIZES              32
61
62 typedef struct _LOSFreeChunks LOSFreeChunks;
63 struct _LOSFreeChunks {
64         LOSFreeChunks *next_size;
65         size_t size;
66 };
67
68 typedef struct _LOSSection LOSSection;
69 struct _LOSSection {
70         LOSSection *next;
71         size_t num_free_chunks;
72         unsigned char *free_chunk_map;
73 };
74
75 LOSObject *los_object_list = NULL;
76 mword los_memory_usage = 0;
77
78 static LOSSection *los_sections = NULL;
79 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
80 static mword los_num_objects = 0;
81 static int los_num_sections = 0;
82
83 //#define USE_MALLOC
84 //#define LOS_CONSISTENCY_CHECK
85 //#define LOS_DUMMY
86
87 #ifdef LOS_DUMMY
88 #define LOS_SEGMENT_SIZE        (4096 * 1024)
89
90 static char *los_segment = NULL;
91 static int los_segment_index = 0;
92 #endif
93
94 #ifdef LOS_CONSISTENCY_CHECK
95 static void
96 los_consistency_check (void)
97 {
98         LOSSection *section;
99         LOSObject *obj;
100         int i;
101         mword memory_usage = 0;
102
103         for (obj = los_object_list; obj; obj = obj->next) {
104                 char *end = obj->data + obj->size;
105                 int start_index, num_chunks;
106
107                 memory_usage += obj->size;
108
109                 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
110                         continue;
111
112                 section = LOS_SECTION_FOR_OBJ (obj);
113
114                 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
115
116                 start_index = LOS_CHUNK_INDEX (obj, section);
117                 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
118                 for (i = start_index; i < start_index + num_chunks; ++i)
119                         g_assert (!section->free_chunk_map [i]);
120         }
121
122         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
123                 LOSFreeChunks *size_chunks;
124                 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
125                         LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
126                         int j, num_chunks, start_index;
127
128                         if (i == 0)
129                                 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
130                         else
131                                 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
132
133                         num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
134                         start_index = LOS_CHUNK_INDEX (size_chunks, section);
135                         for (j = start_index; j < start_index + num_chunks; ++j)
136                                 g_assert (section->free_chunk_map [j]);
137                 }
138         }
139
140         g_assert (los_memory_usage == memory_usage);
141 }
142 #endif
143
144 static void
145 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
146 {
147         size_t num_chunks = size >> LOS_CHUNK_BITS;
148
149         free_chunks->size = size;
150
151         if (num_chunks >= LOS_NUM_FAST_SIZES)
152                 num_chunks = 0;
153         free_chunks->next_size = los_fast_free_lists [num_chunks];
154         los_fast_free_lists [num_chunks] = free_chunks;
155 }
156
157 static LOSFreeChunks*
158 get_from_size_list (LOSFreeChunks **list, size_t size)
159 {
160         LOSFreeChunks *free_chunks = NULL;
161         LOSSection *section;
162         size_t i, num_chunks, start_index;
163
164
165         g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
166
167         while (*list) {
168                 free_chunks = *list;
169                 if (free_chunks->size >= size)
170                         break;
171                 list = &(*list)->next_size;
172         }
173
174         if (!*list)
175                 return NULL;
176
177         *list = free_chunks->next_size;
178
179         if (free_chunks->size > size)
180                 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
181
182         num_chunks = size >> LOS_CHUNK_BITS;
183
184         section = LOS_SECTION_FOR_OBJ (free_chunks);
185
186         start_index = LOS_CHUNK_INDEX (free_chunks, section);
187         for (i = start_index; i < start_index + num_chunks; ++i) {
188                 g_assert (section->free_chunk_map [i]);
189                 section->free_chunk_map [i] = 0;
190         }
191
192         section->num_free_chunks -= size >> LOS_CHUNK_BITS;
193         g_assert (section->num_free_chunks >= 0);
194
195         return free_chunks;
196 }
197
198 static LOSObject*
199 get_los_section_memory (size_t size)
200 {
201         LOSSection *section;
202         LOSFreeChunks *free_chunks;
203         size_t num_chunks;
204
205         size += LOS_CHUNK_SIZE - 1;
206         size &= ~(LOS_CHUNK_SIZE - 1);
207
208         num_chunks = size >> LOS_CHUNK_BITS;
209
210         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
211         g_assert (num_chunks > 0);
212
213  retry:
214         if (num_chunks >= LOS_NUM_FAST_SIZES) {
215                 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
216         } else {
217                 size_t i;
218                 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
219                         free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
220                         if (free_chunks)
221                                 break;
222                 }
223                 if (!free_chunks)
224                         free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
225         }
226
227         if (free_chunks)
228                 return (LOSObject*)free_chunks;
229
230         if (!sgen_memgov_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
231                 return NULL;
232
233         section = sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
234
235         if (!section)
236                 return NULL;
237
238         free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
239         free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
240         free_chunks->next_size = los_fast_free_lists [0];
241         los_fast_free_lists [0] = free_chunks;
242
243         section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
244
245         section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
246         g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
247         section->free_chunk_map [0] = 0;
248         memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
249
250         section->next = los_sections;
251         los_sections = section;
252
253         ++los_num_sections;
254
255         goto retry;
256 }
257
258 static void
259 free_los_section_memory (LOSObject *obj, size_t size)
260 {
261         LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
262         size_t num_chunks, i, start_index;
263
264         size += LOS_CHUNK_SIZE - 1;
265         size &= ~(LOS_CHUNK_SIZE - 1);
266
267         num_chunks = size >> LOS_CHUNK_BITS;
268
269         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
270         g_assert (num_chunks > 0);
271
272         section->num_free_chunks += num_chunks;
273         g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
274
275         /*
276          * We could free the LOS section here if it's empty, but we
277          * can't unless we also remove its free chunks from the fast
278          * free lists.  Instead, we do it in los_sweep().
279          */
280
281         start_index = LOS_CHUNK_INDEX (obj, section);
282         for (i = start_index; i < start_index + num_chunks; ++i) {
283                 g_assert (!section->free_chunk_map [i]);
284                 section->free_chunk_map [i] = 1;
285         }
286
287         add_free_chunk ((LOSFreeChunks*)obj, size);
288 }
289
290 static int pagesize;
291
292 void
293 sgen_los_free_object (LOSObject *obj)
294 {
295 #ifndef LOS_DUMMY
296         size_t size = obj->size;
297         SGEN_LOG (4, "Freed large object %p, size %lu", obj->data, (unsigned long)obj->size);
298         binary_protocol_empty (obj->data, obj->size);
299
300         los_memory_usage -= size;
301         los_num_objects--;
302
303 #ifdef USE_MALLOC
304         free (obj);
305 #else
306         if (size > LOS_SECTION_OBJECT_LIMIT) {
307                 if (!pagesize)
308                         pagesize = mono_pagesize ();
309                 size += sizeof (LOSObject);
310                 size += pagesize - 1;
311                 size &= ~(pagesize - 1);
312                 sgen_free_os_memory (obj, size, SGEN_ALLOC_HEAP);
313                 sgen_memgov_release_space (size, SPACE_LOS);
314         } else {
315                 free_los_section_memory (obj, size + sizeof (LOSObject));
316 #ifdef LOS_CONSISTENCY_CHECKS
317                 los_consistency_check ();
318 #endif
319         }
320 #endif
321 #endif
322 }
323
324 /*
325  * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
326  * They are currently kept track of with a linked list.
327  * They don't move, so there is no need to pin them during collection
328  * and we avoid the memcpy overhead.
329  */
330 void*
331 sgen_los_alloc_large_inner (MonoVTable *vtable, size_t size)
332 {
333         LOSObject *obj = NULL;
334         void **vtslot;
335
336         g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
337         g_assert ((size & 1) == 0);
338
339         /*
340          * size + sizeof (LOSObject) <= SSIZE_MAX - (mono_pagesize () - 1)
341          *
342          * therefore:
343          *
344          * size <= SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject)
345          */
346         if (size > SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject))
347                 return NULL;
348
349 #ifdef LOS_DUMMY
350         if (!los_segment)
351                 los_segment = sgen_alloc_os_memory (LOS_SEGMENT_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
352         los_segment_index = ALIGN_UP (los_segment_index);
353
354         obj = (LOSObject*)(los_segment + los_segment_index);
355         los_segment_index += size + sizeof (LOSObject);
356         g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
357 #else
358         sgen_ensure_free_space (size);
359
360 #ifdef USE_MALLOC
361         obj = malloc (size + sizeof (LOSObject));
362         memset (obj, 0, size + sizeof (LOSObject));
363 #else
364         if (size > LOS_SECTION_OBJECT_LIMIT) {
365                 size_t alloc_size = size;
366                 if (!pagesize)
367                         pagesize = mono_pagesize ();
368                 alloc_size += sizeof (LOSObject);
369                 alloc_size += pagesize - 1;
370                 alloc_size &= ~(pagesize - 1);
371                 if (sgen_memgov_try_alloc_space (alloc_size, SPACE_LOS)) {
372                         obj = sgen_alloc_os_memory (alloc_size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
373                 }
374         } else {
375                 obj = get_los_section_memory (size + sizeof (LOSObject));
376                 if (obj)
377                         memset (obj, 0, size + sizeof (LOSObject));
378         }
379 #endif
380 #endif
381         if (!obj)
382                 return NULL;
383         g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
384         obj->size = size;
385         vtslot = (void**)obj->data;
386         *vtslot = vtable;
387         sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
388         obj->next = los_object_list;
389         los_object_list = obj;
390         los_memory_usage += size;
391         los_num_objects++;
392         SGEN_LOG (4, "Allocated large object %p, vtable: %p (%s), size: %zd", obj->data, vtable, vtable->klass->name, size);
393         binary_protocol_alloc (obj->data, vtable, size);
394
395 #ifdef LOS_CONSISTENCY_CHECK
396         los_consistency_check ();
397 #endif
398
399         return obj->data;
400 }
401
402 void
403 sgen_los_sweep (void)
404 {
405         LOSSection *section, *prev;
406         int i;
407         int num_sections = 0;
408
409         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
410                 los_fast_free_lists [i] = NULL;
411
412         prev = NULL;
413         section = los_sections;
414         while (section) {
415                 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
416                         LOSSection *next = section->next;
417                         if (prev)
418                                 prev->next = next;
419                         else
420                                 los_sections = next;
421                         sgen_free_os_memory (section, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP);
422                         sgen_memgov_release_space (LOS_SECTION_SIZE, SPACE_LOS);
423                         section = next;
424                         --los_num_sections;
425                         continue;
426                 }
427
428                 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
429                         if (section->free_chunk_map [i]) {
430                                 int j;
431                                 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
432                                         ;
433                                 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
434                                 i = j - 1;
435                         }
436                 }
437
438                 prev = section;
439                 section = section->next;
440
441                 ++num_sections;
442         }
443
444 #ifdef LOS_CONSISTENCY_CHECK
445         los_consistency_check ();
446 #endif
447
448         /*
449         g_print ("LOS sections: %d  objects: %d  usage: %d\n", num_sections, los_num_objects, los_memory_usage);
450         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
451                 int num_chunks = 0;
452                 LOSFreeChunks *free_chunks;
453                 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
454                         ++num_chunks;
455                 g_print ("  %d: %d\n", i, num_chunks);
456         }
457         */
458
459         g_assert (los_num_sections == num_sections);
460 }
461
462 gboolean
463 sgen_ptr_is_in_los (char *ptr, char **start)
464 {
465         LOSObject *obj;
466
467         *start = NULL;
468         for (obj = los_object_list; obj; obj = obj->next) {
469                 char *end = obj->data + obj->size;
470
471                 if (ptr >= obj->data && ptr < end) {
472                         *start = obj->data;
473                         return TRUE;
474                 }
475         }
476         return FALSE;
477 }
478
479 void
480 sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
481 {
482         LOSObject *obj;
483
484         for (obj = los_object_list; obj; obj = obj->next)
485                 cb (obj->data, obj->size, user_data);
486 }
487
488 gboolean
489 sgen_los_is_valid_object (char *object)
490 {
491         LOSObject *obj;
492
493         for (obj = los_object_list; obj; obj = obj->next) {
494                 if (obj->data == object)
495                         return TRUE;
496         }
497         return FALSE;
498 }
499
500 gboolean
501 mono_sgen_los_describe_pointer (char *ptr)
502 {
503         LOSObject *obj;
504
505         for (obj = los_object_list; obj; obj = obj->next) {
506                 const char *los_kind;
507                 mword size;
508                 gboolean pinned;
509
510                 if (obj->data > ptr || obj->data + obj->size <= ptr)
511                         continue;
512
513                 size = sgen_los_object_size (obj);
514                 pinned = sgen_los_object_is_pinned (obj->data);
515
516                 if (size > LOS_SECTION_OBJECT_LIMIT)
517                         los_kind = "huge-los-ptr";
518                 else
519                         los_kind = "los-ptr";
520
521                 if (obj->data == ptr) {
522                         SGEN_LOG (0, "%s (size %d pin %d)\n", los_kind, (int)size, pinned ? 1 : 0);
523                 } else {
524                         SGEN_LOG (0, "%s (interior-ptr offset %td size %d pin %d)",
525                                           los_kind, ptr - obj->data, (int)size, pinned ? 1 : 0);
526                 }
527
528                 return TRUE;
529         }
530         return FALSE;
531 }
532
533 void
534 sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
535 {
536         LOSObject *obj;
537         for (obj = los_object_list; obj; obj = obj->next) {
538                 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
539                 if (SGEN_VTABLE_HAS_REFERENCES (vt))
540                         callback ((mword)obj->data, (mword)obj->size);
541         }
542 }
543
544 void
545 sgen_los_scan_card_table (gboolean mod_union, SgenGrayQueue *queue)
546 {
547         LOSObject *obj;
548
549         for (obj = los_object_list; obj; obj = obj->next) {
550                 guint8 *cards;
551
552                 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
553                         continue;
554
555                 if (mod_union) {
556                         if (!sgen_los_object_is_pinned (obj->data))
557                                 continue;
558
559                         cards = obj->cardtable_mod_union;
560                         g_assert (cards);
561                 } else {
562                         cards = NULL;
563                 }
564
565                 sgen_cardtable_scan_object (obj->data, obj->size, cards, mod_union, queue);
566         }
567 }
568
569 void
570 sgen_los_count_cards (long long *num_total_cards, long long *num_marked_cards)
571 {
572         LOSObject *obj;
573         long long total_cards = 0;
574         long long marked_cards = 0;
575
576         for (obj = los_object_list; obj; obj = obj->next) {
577                 int i;
578                 guint8 *cards = sgen_card_table_get_card_scan_address ((mword) obj->data);
579                 guint8 *cards_end = sgen_card_table_get_card_scan_address ((mword) obj->data + obj->size - 1);
580                 mword num_cards = (cards_end - cards) + 1;
581
582                 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
583                         continue;
584
585                 total_cards += num_cards;
586                 for (i = 0; i < num_cards; ++i) {
587                         if (cards [i])
588                                 ++marked_cards;
589                 }
590         }
591
592         *num_total_cards = total_cards;
593         *num_marked_cards = marked_cards;
594 }
595
596 void
597 sgen_los_update_cardtable_mod_union (void)
598 {
599         LOSObject *obj;
600
601         for (obj = los_object_list; obj; obj = obj->next) {
602                 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
603                         continue;
604                 obj->cardtable_mod_union = sgen_card_table_update_mod_union (obj->cardtable_mod_union,
605                                 obj->data, obj->size, NULL);
606         }
607 }
608
609 mword
610 sgen_los_object_size (LOSObject *obj)
611 {
612         return obj->size & ~1L;
613 }
614
615 LOSObject*
616 sgen_los_header_for_object (char *data)
617 {
618 #if _MSC_VER
619         return (LOSObject*)(data - (int)(&(((LOSObject*)0)->data)));
620 #else
621         return (LOSObject*)(data - sizeof (LOSObject));
622 #endif
623 }
624
625 void
626 sgen_los_pin_object (char *data)
627 {
628         LOSObject *obj = sgen_los_header_for_object (data);
629         obj->size = obj->size | 1;
630         binary_protocol_pin (data, (gpointer)SGEN_LOAD_VTABLE (data), sgen_safe_object_get_size ((MonoObject*)data));
631 }
632
633 void
634 sgen_los_unpin_object (char *data)
635 {
636         LOSObject *obj = sgen_los_header_for_object (data);
637         obj->size = sgen_los_object_size (obj);
638 }
639
640 gboolean
641 sgen_los_object_is_pinned (char *data)
642 {
643         LOSObject *obj = sgen_los_header_for_object (data);
644         return obj->size & 1;
645 }
646
647 #endif /* HAVE_SGEN_GC */