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