]>
Commit | Line | Data |
---|---|---|
21341cfd | 1 | /* "Bag-of-pages" garbage collector for the GNU compiler. |
a945c346 | 2 | Copyright (C) 1999-2024 Free Software Foundation, Inc. |
21341cfd | 3 | |
1322177d | 4 | This file is part of GCC. |
21341cfd | 5 | |
1322177d LB |
6 | GCC is free software; you can redistribute it and/or modify it under |
7 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 8 | Software Foundation; either version 3, or (at your option) any later |
1322177d | 9 | version. |
21341cfd | 10 | |
1322177d LB |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
21341cfd | 15 | |
b9bfacf0 | 16 | You should have received a copy of the GNU General Public License |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
21341cfd | 19 | |
21341cfd | 20 | #include "config.h" |
21341cfd | 21 | #include "system.h" |
4977bab6 | 22 | #include "coretypes.h" |
c7131fb2 | 23 | #include "backend.h" |
40e23961 | 24 | #include "alias.h" |
21341cfd | 25 | #include "tree.h" |
e5ecd4ea | 26 | #include "rtl.h" |
4d0cdd0c | 27 | #include "memmodel.h" |
1b42a6a9 | 28 | #include "tm_p.h" |
718f9c0f | 29 | #include "diagnostic-core.h" |
21341cfd | 30 | #include "flags.h" |
a9429e29 | 31 | #include "ggc-internal.h" |
2a9a326b | 32 | #include "timevar.h" |
442b4905 | 33 | #include "cgraph.h" |
b78cd885 | 34 | #include "cfgloop.h" |
ae2392a9 | 35 | #include "plugin.h" |
e5ecd4ea | 36 | |
825b6926 ZW |
37 | /* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a |
38 | file open. Prefer either to valloc. */ | |
39 | #ifdef HAVE_MMAP_ANON | |
40 | # undef HAVE_MMAP_DEV_ZERO | |
825b6926 | 41 | # define USING_MMAP |
005537df | 42 | #endif |
21341cfd | 43 | |
825b6926 | 44 | #ifdef HAVE_MMAP_DEV_ZERO |
825b6926 | 45 | # define USING_MMAP |
8342b467 RH |
46 | #endif |
47 | ||
130fadbb RH |
48 | #ifndef USING_MMAP |
49 | #define USING_MALLOC_PAGE_GROUPS | |
5b918807 | 50 | #endif |
21341cfd | 51 | |
87fb500b RO |
52 | #if defined(HAVE_MADVISE) && HAVE_DECL_MADVISE && defined(MADV_DONTNEED) \ |
53 | && defined(USING_MMAP) | |
711a3d82 AK |
54 | # define USING_MADVISE |
55 | #endif | |
56 | ||
0fa2e4df | 57 | /* Strategy: |
21341cfd AS |
58 | |
59 | This garbage-collecting allocator allocates objects on one of a set | |
60 | of pages. Each page can allocate objects of a single size only; | |
61 | available sizes are powers of two starting at four bytes. The size | |
62 | of an allocation request is rounded up to the next power of two | |
63 | (`order'), and satisfied from the appropriate page. | |
64 | ||
65 | Each page is recorded in a page-entry, which also maintains an | |
66 | in-use bitmap of object positions on the page. This allows the | |
67 | allocation state of a particular object to be flipped without | |
68 | touching the page itself. | |
69 | ||
70 | Each page-entry also has a context depth, which is used to track | |
71 | pushing and popping of allocation contexts. Only objects allocated | |
589005ff | 72 | in the current (highest-numbered) context may be collected. |
21341cfd AS |
73 | |
74 | Page entries are arranged in an array of singly-linked lists. The | |
75 | array is indexed by the allocation size, in bits, of the pages on | |
76 | it; i.e. all pages on a list allocate objects of the same size. | |
77 | Pages are ordered on the list such that all non-full pages precede | |
78 | all full pages, with non-full pages arranged in order of decreasing | |
79 | context depth. | |
80 | ||
81 | Empty pages (of all orders) are kept on a single page cache list, | |
82 | and are considered first when new pages are required; they are | |
83 | deallocated at the start of the next collection if they haven't | |
84 | been recycled by then. */ | |
85 | ||
21341cfd AS |
86 | /* Define GGC_DEBUG_LEVEL to print debugging information. |
87 | 0: No debugging output. | |
88 | 1: GC statistics only. | |
89 | 2: Page-entry allocations/deallocations as well. | |
90 | 3: Object allocations as well. | |
6d2f8887 | 91 | 4: Object marks as well. */ |
21341cfd | 92 | #define GGC_DEBUG_LEVEL (0) |
21341cfd AS |
93 | \f |
94 | /* A two-level tree is used to look up the page-entry for a given | |
95 | pointer. Two chunks of the pointer's bits are extracted to index | |
96 | the first and second levels of the tree, as follows: | |
97 | ||
98 | HOST_PAGE_SIZE_BITS | |
99 | 32 | | | |
100 | msb +----------------+----+------+------+ lsb | |
101 | | | | | |
102 | PAGE_L1_BITS | | |
103 | | | | |
104 | PAGE_L2_BITS | |
105 | ||
106 | The bottommost HOST_PAGE_SIZE_BITS are ignored, since page-entry | |
107 | pages are aligned on system page boundaries. The next most | |
108 | significant PAGE_L2_BITS and PAGE_L1_BITS are the second and first | |
589005ff | 109 | index values in the lookup table, respectively. |
21341cfd | 110 | |
005537df RH |
111 | For 32-bit architectures and the settings below, there are no |
112 | leftover bits. For architectures with wider pointers, the lookup | |
113 | tree points to a list of pages, which must be scanned to find the | |
114 | correct one. */ | |
21341cfd AS |
115 | |
116 | #define PAGE_L1_BITS (8) | |
117 | #define PAGE_L2_BITS (32 - PAGE_L1_BITS - G.lg_pagesize) | |
2a6e6fea TG |
118 | #define PAGE_L1_SIZE ((uintptr_t) 1 << PAGE_L1_BITS) |
119 | #define PAGE_L2_SIZE ((uintptr_t) 1 << PAGE_L2_BITS) | |
21341cfd AS |
120 | |
121 | #define LOOKUP_L1(p) \ | |
2a6e6fea | 122 | (((uintptr_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1)) |
21341cfd AS |
123 | |
124 | #define LOOKUP_L2(p) \ | |
2a6e6fea | 125 | (((uintptr_t) (p) >> G.lg_pagesize) & ((1 << PAGE_L2_BITS) - 1)) |
21341cfd | 126 | |
2be510b8 MM |
127 | /* The number of objects per allocation page, for objects on a page of |
128 | the indicated ORDER. */ | |
129 | #define OBJECTS_PER_PAGE(ORDER) objects_per_page_table[ORDER] | |
130 | ||
17211ab5 GK |
131 | /* The number of objects in P. */ |
132 | #define OBJECTS_IN_PAGE(P) ((P)->bytes / OBJECT_SIZE ((P)->order)) | |
133 | ||
2be510b8 MM |
134 | /* The size of an object on a page of the indicated ORDER. */ |
135 | #define OBJECT_SIZE(ORDER) object_size_table[ORDER] | |
136 | ||
8537ed68 ZW |
137 | /* For speed, we avoid doing a general integer divide to locate the |
138 | offset in the allocation bitmap, by precalculating numbers M, S | |
139 | such that (O * M) >> S == O / Z (modulo 2^32), for any offset O | |
140 | within the page which is evenly divisible by the object size Z. */ | |
141 | #define DIV_MULT(ORDER) inverse_table[ORDER].mult | |
142 | #define DIV_SHIFT(ORDER) inverse_table[ORDER].shift | |
143 | #define OFFSET_TO_BIT(OFFSET, ORDER) \ | |
144 | (((OFFSET) * DIV_MULT (ORDER)) >> DIV_SHIFT (ORDER)) | |
145 | ||
b78cd885 RG |
146 | /* We use this structure to determine the alignment required for |
147 | allocations. For power-of-two sized allocations, that's not a | |
148 | problem, but it does matter for odd-sized allocations. | |
149 | We do not care about alignment for floating-point types. */ | |
150 | ||
151 | struct max_alignment { | |
152 | char c; | |
153 | union { | |
a9243bfc | 154 | int64_t i; |
b78cd885 RG |
155 | void *p; |
156 | } u; | |
157 | }; | |
158 | ||
159 | /* The biggest alignment required. */ | |
160 | ||
161 | #define MAX_ALIGNMENT (offsetof (struct max_alignment, u)) | |
162 | ||
163 | ||
2be510b8 MM |
164 | /* The number of extra orders, not corresponding to power-of-two sized |
165 | objects. */ | |
166 | ||
ca7558fc | 167 | #define NUM_EXTRA_ORDERS ARRAY_SIZE (extra_order_size_table) |
2be510b8 | 168 | |
d1f1cc6a | 169 | #define RTL_SIZE(NSLOTS) \ |
e1de1560 | 170 | (RTX_HDR_SIZE + (NSLOTS) * sizeof (rtunion)) |
d1f1cc6a | 171 | |
5e26df64 SB |
172 | #define TREE_EXP_SIZE(OPS) \ |
173 | (sizeof (struct tree_exp) + ((OPS) - 1) * sizeof (tree)) | |
174 | ||
2be510b8 MM |
175 | /* The Ith entry is the maximum size of an object to be stored in the |
176 | Ith extra order. Adding a new entry to this array is the *only* | |
177 | thing you need to do to add a new special allocation size. */ | |
178 | ||
179 | static const size_t extra_order_size_table[] = { | |
b78cd885 RG |
180 | /* Extra orders for small non-power-of-two multiples of MAX_ALIGNMENT. |
181 | There are a lot of structures with these sizes and explicitly | |
182 | listing them risks orders being dropped because they changed size. */ | |
183 | MAX_ALIGNMENT * 3, | |
184 | MAX_ALIGNMENT * 5, | |
185 | MAX_ALIGNMENT * 6, | |
186 | MAX_ALIGNMENT * 7, | |
187 | MAX_ALIGNMENT * 9, | |
188 | MAX_ALIGNMENT * 10, | |
189 | MAX_ALIGNMENT * 11, | |
190 | MAX_ALIGNMENT * 12, | |
191 | MAX_ALIGNMENT * 13, | |
192 | MAX_ALIGNMENT * 14, | |
193 | MAX_ALIGNMENT * 15, | |
820cc88f DB |
194 | sizeof (struct tree_decl_non_common), |
195 | sizeof (struct tree_field_decl), | |
196 | sizeof (struct tree_parm_decl), | |
197 | sizeof (struct tree_var_decl), | |
51545682 | 198 | sizeof (struct tree_type_non_common), |
f5938dcd RG |
199 | sizeof (struct function), |
200 | sizeof (struct basic_block_def), | |
b78cd885 | 201 | sizeof (struct cgraph_node), |
99b1c316 | 202 | sizeof (class loop), |
2be510b8 MM |
203 | }; |
204 | ||
205 | /* The total number of orders. */ | |
206 | ||
207 | #define NUM_ORDERS (HOST_BITS_PER_PTR + NUM_EXTRA_ORDERS) | |
208 | ||
17211ab5 GK |
209 | /* Compute the smallest nonnegative number which when added to X gives |
210 | a multiple of F. */ | |
211 | ||
212 | #define ROUND_UP_VALUE(x, f) ((f) - 1 - ((f) - 1 + (x)) % (f)) | |
213 | ||
3bc50163 AK |
214 | /* Round X to next multiple of the page size */ |
215 | ||
54070b51 | 216 | #define PAGE_ALIGN(x) ROUND_UP ((x), G.pagesize) |
3bc50163 | 217 | |
2be510b8 MM |
218 | /* The Ith entry is the number of objects on a page or order I. */ |
219 | ||
220 | static unsigned objects_per_page_table[NUM_ORDERS]; | |
221 | ||
222 | /* The Ith entry is the size of an object on a page of order I. */ | |
223 | ||
224 | static size_t object_size_table[NUM_ORDERS]; | |
21341cfd | 225 | |
8537ed68 ZW |
226 | /* The Ith entry is a pair of numbers (mult, shift) such that |
227 | ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32, | |
228 | for all k evenly divisible by OBJECT_SIZE(I). */ | |
229 | ||
230 | static struct | |
231 | { | |
75d75435 | 232 | size_t mult; |
8537ed68 ZW |
233 | unsigned int shift; |
234 | } | |
235 | inverse_table[NUM_ORDERS]; | |
236 | ||
21341cfd AS |
237 | /* A page_entry records the status of an allocation page. This |
238 | structure is dynamically sized to fit the bitmap in_use_p. */ | |
a79683d5 | 239 | struct page_entry |
21341cfd AS |
240 | { |
241 | /* The next page-entry with objects of the same size, or NULL if | |
242 | this is the last page-entry. */ | |
243 | struct page_entry *next; | |
244 | ||
9bf793f9 JL |
245 | /* The previous page-entry with objects of the same size, or NULL if |
246 | this is the first page-entry. The PREV pointer exists solely to | |
71cc389b | 247 | keep the cost of ggc_free manageable. */ |
9bf793f9 JL |
248 | struct page_entry *prev; |
249 | ||
21341cfd AS |
250 | /* The number of bytes allocated. (This will always be a multiple |
251 | of the host system page size.) */ | |
252 | size_t bytes; | |
253 | ||
254 | /* The address at which the memory is allocated. */ | |
255 | char *page; | |
256 | ||
130fadbb RH |
257 | #ifdef USING_MALLOC_PAGE_GROUPS |
258 | /* Back pointer to the page group this page came from. */ | |
259 | struct page_group *group; | |
260 | #endif | |
261 | ||
c4775f82 MS |
262 | /* This is the index in the by_depth varray where this page table |
263 | can be found. */ | |
264 | unsigned long index_by_depth; | |
21341cfd AS |
265 | |
266 | /* Context depth of this page. */ | |
ae373eda | 267 | unsigned short context_depth; |
21341cfd AS |
268 | |
269 | /* The number of free objects remaining on this page. */ | |
270 | unsigned short num_free_objects; | |
271 | ||
272 | /* A likely candidate for the bit position of a free object for the | |
273 | next allocation from this page. */ | |
274 | unsigned short next_bit_hint; | |
275 | ||
ae373eda MM |
276 | /* The lg of size of objects allocated from this page. */ |
277 | unsigned char order; | |
278 | ||
711a3d82 AK |
279 | /* Discarded page? */ |
280 | bool discarded; | |
281 | ||
21341cfd AS |
282 | /* A bit vector indicating whether or not objects are in use. The |
283 | Nth bit is one if the Nth object on this page is allocated. This | |
284 | array is dynamically sized. */ | |
285 | unsigned long in_use_p[1]; | |
a79683d5 | 286 | }; |
21341cfd | 287 | |
130fadbb RH |
288 | #ifdef USING_MALLOC_PAGE_GROUPS |
289 | /* A page_group describes a large allocation from malloc, from which | |
290 | we parcel out aligned pages. */ | |
a79683d5 | 291 | struct page_group |
130fadbb RH |
292 | { |
293 | /* A linked list of all extant page groups. */ | |
294 | struct page_group *next; | |
295 | ||
296 | /* The address we received from malloc. */ | |
297 | char *allocation; | |
298 | ||
299 | /* The size of the block. */ | |
300 | size_t alloc_size; | |
301 | ||
302 | /* A bitmask of pages in use. */ | |
303 | unsigned int in_use; | |
a79683d5 | 304 | }; |
130fadbb | 305 | #endif |
21341cfd AS |
306 | |
307 | #if HOST_BITS_PER_PTR <= 32 | |
308 | ||
309 | /* On 32-bit hosts, we use a two level page table, as pictured above. */ | |
310 | typedef page_entry **page_table[PAGE_L1_SIZE]; | |
311 | ||
312 | #else | |
313 | ||
005537df RH |
314 | /* On 64-bit hosts, we use the same two level page tables plus a linked |
315 | list that disambiguates the top 32-bits. There will almost always be | |
21341cfd AS |
316 | exactly one entry in the list. */ |
317 | typedef struct page_table_chain | |
318 | { | |
319 | struct page_table_chain *next; | |
320 | size_t high_bits; | |
321 | page_entry **table[PAGE_L1_SIZE]; | |
322 | } *page_table; | |
323 | ||
324 | #endif | |
325 | ||
de49ce19 TS |
326 | class finalizer |
327 | { | |
328 | public: | |
329 | finalizer (void *addr, void (*f)(void *)) : m_addr (addr), m_function (f) {} | |
330 | ||
331 | void *addr () const { return m_addr; } | |
332 | ||
333 | void call () const { m_function (m_addr); } | |
334 | ||
335 | private: | |
336 | void *m_addr; | |
337 | void (*m_function)(void *); | |
338 | }; | |
339 | ||
340 | class vec_finalizer | |
341 | { | |
342 | public: | |
343 | vec_finalizer (uintptr_t addr, void (*f)(void *), size_t s, size_t n) : | |
344 | m_addr (addr), m_function (f), m_object_size (s), m_n_objects (n) {} | |
345 | ||
346 | void call () const | |
347 | { | |
348 | for (size_t i = 0; i < m_n_objects; i++) | |
349 | m_function (reinterpret_cast<void *> (m_addr + (i * m_object_size))); | |
350 | } | |
351 | ||
352 | void *addr () const { return reinterpret_cast<void *> (m_addr); } | |
353 | ||
354 | private: | |
355 | uintptr_t m_addr; | |
356 | void (*m_function)(void *); | |
357 | size_t m_object_size; | |
358 | size_t m_n_objects; | |
2a304777 | 359 | }; |
de49ce19 | 360 | |
9957322d DK |
361 | #ifdef ENABLE_GC_ALWAYS_COLLECT |
362 | /* List of free objects to be verified as actually free on the | |
363 | next collection. */ | |
364 | struct free_object | |
365 | { | |
366 | void *object; | |
367 | struct free_object *next; | |
368 | }; | |
369 | #endif | |
370 | ||
21341cfd | 371 | /* The rest of the global variables. */ |
11478306 | 372 | static struct ggc_globals |
21341cfd AS |
373 | { |
374 | /* The Nth element in this array is a page with objects of size 2^N. | |
375 | If there are any pages with free objects, they will be at the | |
376 | head of the list. NULL if there are no page-entries for this | |
377 | object size. */ | |
2be510b8 | 378 | page_entry *pages[NUM_ORDERS]; |
21341cfd AS |
379 | |
380 | /* The Nth element in this array is the last page with objects of | |
381 | size 2^N. NULL if there are no page-entries for this object | |
382 | size. */ | |
2be510b8 | 383 | page_entry *page_tails[NUM_ORDERS]; |
21341cfd AS |
384 | |
385 | /* Lookup table for associating allocation pages with object addresses. */ | |
386 | page_table lookup; | |
387 | ||
388 | /* The system's page size. */ | |
389 | size_t pagesize; | |
390 | size_t lg_pagesize; | |
391 | ||
392 | /* Bytes currently allocated. */ | |
393 | size_t allocated; | |
394 | ||
395 | /* Bytes currently allocated at the end of the last collection. */ | |
396 | size_t allocated_last_gc; | |
397 | ||
3277221c MM |
398 | /* Total amount of memory mapped. */ |
399 | size_t bytes_mapped; | |
400 | ||
52895e1a RH |
401 | /* Bit N set if any allocations have been done at context depth N. */ |
402 | unsigned long context_depth_allocations; | |
403 | ||
404 | /* Bit N set if any collections have been done at context depth N. */ | |
405 | unsigned long context_depth_collections; | |
406 | ||
21341cfd | 407 | /* The current depth in the context stack. */ |
d416576b | 408 | unsigned short context_depth; |
21341cfd AS |
409 | |
410 | /* A file descriptor open to /dev/zero for reading. */ | |
825b6926 | 411 | #if defined (HAVE_MMAP_DEV_ZERO) |
21341cfd AS |
412 | int dev_zero_fd; |
413 | #endif | |
414 | ||
415 | /* A cache of free system pages. */ | |
416 | page_entry *free_pages; | |
417 | ||
130fadbb RH |
418 | #ifdef USING_MALLOC_PAGE_GROUPS |
419 | page_group *page_groups; | |
420 | #endif | |
421 | ||
21341cfd AS |
422 | /* The file descriptor for debugging output. */ |
423 | FILE *debug_file; | |
c4775f82 MS |
424 | |
425 | /* Current number of elements in use in depth below. */ | |
426 | unsigned int depth_in_use; | |
427 | ||
428 | /* Maximum number of elements that can be used before resizing. */ | |
429 | unsigned int depth_max; | |
430 | ||
fa10beec | 431 | /* Each element of this array is an index in by_depth where the given |
c4775f82 MS |
432 | depth starts. This structure is indexed by that given depth we |
433 | are interested in. */ | |
434 | unsigned int *depth; | |
435 | ||
436 | /* Current number of elements in use in by_depth below. */ | |
437 | unsigned int by_depth_in_use; | |
438 | ||
439 | /* Maximum number of elements that can be used before resizing. */ | |
440 | unsigned int by_depth_max; | |
441 | ||
442 | /* Each element of this array is a pointer to a page_entry, all | |
443 | page_entries can be found in here by increasing depth. | |
444 | index_by_depth in the page_entry is the index into this data | |
445 | structure where that page_entry can be found. This is used to | |
446 | speed up finding all page_entries at a particular depth. */ | |
447 | page_entry **by_depth; | |
448 | ||
449 | /* Each element is a pointer to the saved in_use_p bits, if any, | |
450 | zero otherwise. We allocate them all together, to enable a | |
451 | better runtime data access pattern. */ | |
452 | unsigned long **save_in_use; | |
685fe032 | 453 | |
2a304777 JM |
454 | /* Finalizers for single objects. The first index is collection_depth. */ |
455 | vec<vec<finalizer> > finalizers; | |
de49ce19 TS |
456 | |
457 | /* Finalizers for vectors of objects. */ | |
2a304777 | 458 | vec<vec<vec_finalizer> > vec_finalizers; |
de49ce19 | 459 | |
685fe032 RH |
460 | #ifdef ENABLE_GC_ALWAYS_COLLECT |
461 | /* List of free objects to be verified as actually free on the | |
462 | next collection. */ | |
9957322d | 463 | struct free_object *free_object_list; |
685fe032 RH |
464 | #endif |
465 | ||
adc4adcd GP |
466 | struct |
467 | { | |
a9429e29 | 468 | /* Total GC-allocated memory. */ |
adc4adcd | 469 | unsigned long long total_allocated; |
a9429e29 | 470 | /* Total overhead for GC-allocated memory. */ |
adc4adcd GP |
471 | unsigned long long total_overhead; |
472 | ||
473 | /* Total allocations and overhead for sizes less than 32, 64 and 128. | |
474 | These sizes are interesting because they are typical cache line | |
938d968e | 475 | sizes. */ |
b8698a0f | 476 | |
adc4adcd GP |
477 | unsigned long long total_allocated_under32; |
478 | unsigned long long total_overhead_under32; | |
b8698a0f | 479 | |
adc4adcd GP |
480 | unsigned long long total_allocated_under64; |
481 | unsigned long long total_overhead_under64; | |
b8698a0f | 482 | |
adc4adcd GP |
483 | unsigned long long total_allocated_under128; |
484 | unsigned long long total_overhead_under128; | |
b8698a0f | 485 | |
439a7e54 DN |
486 | /* The allocations for each of the allocation orders. */ |
487 | unsigned long long total_allocated_per_order[NUM_ORDERS]; | |
488 | ||
938d968e | 489 | /* The overhead for each of the allocation orders. */ |
adc4adcd GP |
490 | unsigned long long total_overhead_per_order[NUM_ORDERS]; |
491 | } stats; | |
21341cfd AS |
492 | } G; |
493 | ||
b086d530 TS |
494 | /* True if a gc is currently taking place. */ |
495 | ||
496 | static bool in_gc = false; | |
497 | ||
21341cfd AS |
498 | /* The size in bytes required to maintain a bitmap for the objects |
499 | on a page-entry. */ | |
500 | #define BITMAP_SIZE(Num_objects) \ | |
c3284718 | 501 | (CEIL ((Num_objects), HOST_BITS_PER_LONG) * sizeof (long)) |
21341cfd | 502 | |
130fadbb RH |
503 | /* Allocate pages in chunks of this size, to throttle calls to memory |
504 | allocation routines. The first page is used, the rest go onto the | |
505 | free list. This cannot be larger than HOST_BITS_PER_INT for the | |
772299b3 | 506 | in_use bitmask for page_group. Hosts that need a different value |
471854f8 | 507 | can override this by defining GGC_QUIRE_SIZE explicitly. */ |
772299b3 MA |
508 | #ifndef GGC_QUIRE_SIZE |
509 | # ifdef USING_MMAP | |
6c995fa5 | 510 | # define GGC_QUIRE_SIZE 512 /* 2MB for 4K pages */ |
772299b3 MA |
511 | # else |
512 | # define GGC_QUIRE_SIZE 16 | |
513 | # endif | |
514 | #endif | |
c4775f82 MS |
515 | |
516 | /* Initial guess as to how many page table entries we might need. */ | |
517 | #define INITIAL_PTE_COUNT 128 | |
21341cfd | 518 | \f |
20c1dc5e AJ |
519 | static page_entry *lookup_page_table_entry (const void *); |
520 | static void set_page_table_entry (void *, page_entry *); | |
130fadbb | 521 | #ifdef USING_MMAP |
25f0ea81 | 522 | static char *alloc_anon (char *, size_t, bool check); |
130fadbb RH |
523 | #endif |
524 | #ifdef USING_MALLOC_PAGE_GROUPS | |
20c1dc5e AJ |
525 | static size_t page_group_index (char *, char *); |
526 | static void set_page_group_in_use (page_group *, char *); | |
527 | static void clear_page_group_in_use (page_group *, char *); | |
130fadbb | 528 | #endif |
20c1dc5e AJ |
529 | static struct page_entry * alloc_page (unsigned); |
530 | static void free_page (struct page_entry *); | |
20c1dc5e AJ |
531 | static void clear_marks (void); |
532 | static void sweep_pages (void); | |
533 | static void ggc_recalculate_in_use_p (page_entry *); | |
534 | static void compute_inverse (unsigned); | |
535 | static inline void adjust_depth (void); | |
536 | static void move_ptes_to_front (int, int); | |
21341cfd | 537 | |
20c1dc5e AJ |
538 | void debug_print_page_list (int); |
539 | static void push_depth (unsigned int); | |
540 | static void push_by_depth (page_entry *, unsigned long *); | |
b6f61163 | 541 | |
c4775f82 MS |
542 | /* Push an entry onto G.depth. */ |
543 | ||
544 | inline static void | |
20c1dc5e | 545 | push_depth (unsigned int i) |
c4775f82 MS |
546 | { |
547 | if (G.depth_in_use >= G.depth_max) | |
548 | { | |
549 | G.depth_max *= 2; | |
d3bfe4de | 550 | G.depth = XRESIZEVEC (unsigned int, G.depth, G.depth_max); |
c4775f82 MS |
551 | } |
552 | G.depth[G.depth_in_use++] = i; | |
553 | } | |
554 | ||
555 | /* Push an entry onto G.by_depth and G.save_in_use. */ | |
556 | ||
557 | inline static void | |
20c1dc5e | 558 | push_by_depth (page_entry *p, unsigned long *s) |
c4775f82 MS |
559 | { |
560 | if (G.by_depth_in_use >= G.by_depth_max) | |
561 | { | |
562 | G.by_depth_max *= 2; | |
d3bfe4de KG |
563 | G.by_depth = XRESIZEVEC (page_entry *, G.by_depth, G.by_depth_max); |
564 | G.save_in_use = XRESIZEVEC (unsigned long *, G.save_in_use, | |
565 | G.by_depth_max); | |
c4775f82 MS |
566 | } |
567 | G.by_depth[G.by_depth_in_use] = p; | |
568 | G.save_in_use[G.by_depth_in_use++] = s; | |
569 | } | |
570 | ||
571 | #if (GCC_VERSION < 3001) | |
572 | #define prefetch(X) ((void) X) | |
573 | #else | |
574 | #define prefetch(X) __builtin_prefetch (X) | |
575 | #endif | |
576 | ||
577 | #define save_in_use_p_i(__i) \ | |
578 | (G.save_in_use[__i]) | |
579 | #define save_in_use_p(__p) \ | |
580 | (save_in_use_p_i (__p->index_by_depth)) | |
581 | ||
acb14262 RB |
582 | /* Traverse the page table and find the entry for a page. |
583 | If the object wasn't allocated in GC return NULL. */ | |
21341cfd | 584 | |
acb14262 RB |
585 | static inline page_entry * |
586 | safe_lookup_page_table_entry (const void *p) | |
21341cfd AS |
587 | { |
588 | page_entry ***base; | |
005537df | 589 | size_t L1, L2; |
21341cfd AS |
590 | |
591 | #if HOST_BITS_PER_PTR <= 32 | |
592 | base = &G.lookup[0]; | |
593 | #else | |
594 | page_table table = G.lookup; | |
2a6e6fea | 595 | uintptr_t high_bits = (uintptr_t) p & ~ (uintptr_t) 0xffffffff; |
005537df RH |
596 | while (1) |
597 | { | |
598 | if (table == NULL) | |
acb14262 | 599 | return NULL; |
005537df RH |
600 | if (table->high_bits == high_bits) |
601 | break; | |
602 | table = table->next; | |
603 | } | |
21341cfd AS |
604 | base = &table->table[0]; |
605 | #endif | |
606 | ||
eaec9b3d | 607 | /* Extract the level 1 and 2 indices. */ |
74c937ca MM |
608 | L1 = LOOKUP_L1 (p); |
609 | L2 = LOOKUP_L2 (p); | |
acb14262 RB |
610 | if (! base[L1]) |
611 | return NULL; | |
74c937ca | 612 | |
acb14262 | 613 | return base[L1][L2]; |
74c937ca MM |
614 | } |
615 | ||
589005ff | 616 | /* Traverse the page table and find the entry for a page. |
74c937ca MM |
617 | Die (probably) if the object wasn't allocated via GC. */ |
618 | ||
619 | static inline page_entry * | |
20c1dc5e | 620 | lookup_page_table_entry (const void *p) |
74c937ca MM |
621 | { |
622 | page_entry ***base; | |
623 | size_t L1, L2; | |
624 | ||
005537df RH |
625 | #if HOST_BITS_PER_PTR <= 32 |
626 | base = &G.lookup[0]; | |
627 | #else | |
628 | page_table table = G.lookup; | |
2a6e6fea | 629 | uintptr_t high_bits = (uintptr_t) p & ~ (uintptr_t) 0xffffffff; |
005537df RH |
630 | while (table->high_bits != high_bits) |
631 | table = table->next; | |
632 | base = &table->table[0]; | |
633 | #endif | |
74c937ca | 634 | |
eaec9b3d | 635 | /* Extract the level 1 and 2 indices. */ |
21341cfd AS |
636 | L1 = LOOKUP_L1 (p); |
637 | L2 = LOOKUP_L2 (p); | |
638 | ||
639 | return base[L1][L2]; | |
640 | } | |
641 | ||
21341cfd | 642 | /* Set the page table entry for a page. */ |
cb2ec151 | 643 | |
21341cfd | 644 | static void |
20c1dc5e | 645 | set_page_table_entry (void *p, page_entry *entry) |
21341cfd AS |
646 | { |
647 | page_entry ***base; | |
648 | size_t L1, L2; | |
649 | ||
650 | #if HOST_BITS_PER_PTR <= 32 | |
651 | base = &G.lookup[0]; | |
652 | #else | |
653 | page_table table; | |
2a6e6fea | 654 | uintptr_t high_bits = (uintptr_t) p & ~ (uintptr_t) 0xffffffff; |
21341cfd AS |
655 | for (table = G.lookup; table; table = table->next) |
656 | if (table->high_bits == high_bits) | |
657 | goto found; | |
658 | ||
659 | /* Not found -- allocate a new table. */ | |
4dc6c528 | 660 | table = XCNEW (struct page_table_chain); |
21341cfd AS |
661 | table->next = G.lookup; |
662 | table->high_bits = high_bits; | |
663 | G.lookup = table; | |
664 | found: | |
665 | base = &table->table[0]; | |
666 | #endif | |
667 | ||
eaec9b3d | 668 | /* Extract the level 1 and 2 indices. */ |
21341cfd AS |
669 | L1 = LOOKUP_L1 (p); |
670 | L2 = LOOKUP_L2 (p); | |
671 | ||
672 | if (base[L1] == NULL) | |
5ed6ace5 | 673 | base[L1] = XCNEWVEC (page_entry *, PAGE_L2_SIZE); |
21341cfd AS |
674 | |
675 | base[L1][L2] = entry; | |
676 | } | |
677 | ||
21341cfd | 678 | /* Prints the page-entry for object size ORDER, for debugging. */ |
cb2ec151 | 679 | |
24e47c76 | 680 | DEBUG_FUNCTION void |
20c1dc5e | 681 | debug_print_page_list (int order) |
21341cfd AS |
682 | { |
683 | page_entry *p; | |
20c1dc5e AJ |
684 | printf ("Head=%p, Tail=%p:\n", (void *) G.pages[order], |
685 | (void *) G.page_tails[order]); | |
21341cfd AS |
686 | p = G.pages[order]; |
687 | while (p != NULL) | |
688 | { | |
20c1dc5e | 689 | printf ("%p(%1d|%3d) -> ", (void *) p, p->context_depth, |
683eb0e9 | 690 | p->num_free_objects); |
21341cfd AS |
691 | p = p->next; |
692 | } | |
693 | printf ("NULL\n"); | |
694 | fflush (stdout); | |
695 | } | |
696 | ||
130fadbb | 697 | #ifdef USING_MMAP |
21341cfd | 698 | /* Allocate SIZE bytes of anonymous memory, preferably near PREF, |
825b6926 ZW |
699 | (if non-null). The ifdef structure here is intended to cause a |
700 | compile error unless exactly one of the HAVE_* is defined. */ | |
cb2ec151 | 701 | |
21341cfd | 702 | static inline char * |
25f0ea81 | 703 | alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size, bool check) |
21341cfd | 704 | { |
825b6926 | 705 | #ifdef HAVE_MMAP_ANON |
d3bfe4de KG |
706 | char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE, |
707 | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); | |
825b6926 ZW |
708 | #endif |
709 | #ifdef HAVE_MMAP_DEV_ZERO | |
d3bfe4de KG |
710 | char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE, |
711 | MAP_PRIVATE, G.dev_zero_fd, 0); | |
21341cfd | 712 | #endif |
825b6926 ZW |
713 | |
714 | if (page == (char *) MAP_FAILED) | |
005537df | 715 | { |
25f0ea81 AK |
716 | if (!check) |
717 | return NULL; | |
1f978f5f | 718 | perror ("virtual memory exhausted"); |
bd0f0717 | 719 | exit (FATAL_EXIT_CODE); |
005537df | 720 | } |
21341cfd | 721 | |
3277221c MM |
722 | /* Remember that we allocated this memory. */ |
723 | G.bytes_mapped += size; | |
724 | ||
9a0a7d5d | 725 | /* Pretend we don't have access to the allocated pages. We'll enable |
a9429e29 | 726 | access to smaller pieces of the area in ggc_internal_alloc. Discard the |
9a0a7d5d | 727 | handle to avoid handle leak. */ |
35dee980 | 728 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (page, size)); |
9a0a7d5d | 729 | |
21341cfd AS |
730 | return page; |
731 | } | |
130fadbb RH |
732 | #endif |
733 | #ifdef USING_MALLOC_PAGE_GROUPS | |
734 | /* Compute the index for this page into the page group. */ | |
735 | ||
736 | static inline size_t | |
20c1dc5e | 737 | page_group_index (char *allocation, char *page) |
130fadbb | 738 | { |
c4f2c499 | 739 | return (size_t) (page - allocation) >> G.lg_pagesize; |
130fadbb RH |
740 | } |
741 | ||
742 | /* Set and clear the in_use bit for this page in the page group. */ | |
743 | ||
744 | static inline void | |
20c1dc5e | 745 | set_page_group_in_use (page_group *group, char *page) |
130fadbb RH |
746 | { |
747 | group->in_use |= 1 << page_group_index (group->allocation, page); | |
748 | } | |
749 | ||
750 | static inline void | |
20c1dc5e | 751 | clear_page_group_in_use (page_group *group, char *page) |
130fadbb RH |
752 | { |
753 | group->in_use &= ~(1 << page_group_index (group->allocation, page)); | |
754 | } | |
755 | #endif | |
21341cfd AS |
756 | |
757 | /* Allocate a new page for allocating objects of size 2^ORDER, | |
758 | and return an entry for it. The entry is not added to the | |
759 | appropriate page_table list. */ | |
cb2ec151 | 760 | |
21341cfd | 761 | static inline struct page_entry * |
20c1dc5e | 762 | alloc_page (unsigned order) |
21341cfd AS |
763 | { |
764 | struct page_entry *entry, *p, **pp; | |
765 | char *page; | |
766 | size_t num_objects; | |
767 | size_t bitmap_size; | |
768 | size_t page_entry_size; | |
769 | size_t entry_size; | |
130fadbb RH |
770 | #ifdef USING_MALLOC_PAGE_GROUPS |
771 | page_group *group; | |
772 | #endif | |
21341cfd AS |
773 | |
774 | num_objects = OBJECTS_PER_PAGE (order); | |
775 | bitmap_size = BITMAP_SIZE (num_objects + 1); | |
776 | page_entry_size = sizeof (page_entry) - sizeof (long) + bitmap_size; | |
2be510b8 | 777 | entry_size = num_objects * OBJECT_SIZE (order); |
ca79429a RH |
778 | if (entry_size < G.pagesize) |
779 | entry_size = G.pagesize; | |
3bc50163 | 780 | entry_size = PAGE_ALIGN (entry_size); |
21341cfd AS |
781 | |
782 | entry = NULL; | |
783 | page = NULL; | |
784 | ||
785 | /* Check the list of free pages for one we can use. */ | |
bd0f0717 | 786 | for (pp = &G.free_pages, p = *pp; p; pp = &p->next, p = *pp) |
21341cfd AS |
787 | if (p->bytes == entry_size) |
788 | break; | |
789 | ||
790 | if (p != NULL) | |
791 | { | |
711a3d82 AK |
792 | if (p->discarded) |
793 | G.bytes_mapped += p->bytes; | |
794 | p->discarded = false; | |
795 | ||
dc297297 | 796 | /* Recycle the allocated memory from this page ... */ |
21341cfd AS |
797 | *pp = p->next; |
798 | page = p->page; | |
bd0f0717 | 799 | |
130fadbb RH |
800 | #ifdef USING_MALLOC_PAGE_GROUPS |
801 | group = p->group; | |
802 | #endif | |
bd0f0717 | 803 | |
21341cfd AS |
804 | /* ... and, if possible, the page entry itself. */ |
805 | if (p->order == order) | |
806 | { | |
807 | entry = p; | |
808 | memset (entry, 0, page_entry_size); | |
809 | } | |
810 | else | |
811 | free (p); | |
812 | } | |
825b6926 | 813 | #ifdef USING_MMAP |
054f5e69 | 814 | else if (entry_size == G.pagesize) |
21341cfd | 815 | { |
054f5e69 ZW |
816 | /* We want just one page. Allocate a bunch of them and put the |
817 | extras on the freelist. (Can only do this optimization with | |
818 | mmap for backing store.) */ | |
819 | struct page_entry *e, *f = G.free_pages; | |
25f0ea81 | 820 | int i, entries = GGC_QUIRE_SIZE; |
054f5e69 | 821 | |
25f0ea81 AK |
822 | page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE, false); |
823 | if (page == NULL) | |
824 | { | |
c3284718 | 825 | page = alloc_anon (NULL, G.pagesize, true); |
25f0ea81 AK |
826 | entries = 1; |
827 | } | |
bd0f0717 | 828 | |
054f5e69 ZW |
829 | /* This loop counts down so that the chain will be in ascending |
830 | memory order. */ | |
25f0ea81 | 831 | for (i = entries - 1; i >= 1; i--) |
054f5e69 | 832 | { |
d3bfe4de | 833 | e = XCNEWVAR (struct page_entry, page_entry_size); |
ca79429a RH |
834 | e->order = order; |
835 | e->bytes = G.pagesize; | |
836 | e->page = page + (i << G.lg_pagesize); | |
054f5e69 ZW |
837 | e->next = f; |
838 | f = e; | |
839 | } | |
bd0f0717 | 840 | |
054f5e69 | 841 | G.free_pages = f; |
21341cfd | 842 | } |
054f5e69 | 843 | else |
25f0ea81 | 844 | page = alloc_anon (NULL, entry_size, true); |
130fadbb RH |
845 | #endif |
846 | #ifdef USING_MALLOC_PAGE_GROUPS | |
847 | else | |
848 | { | |
849 | /* Allocate a large block of memory and serve out the aligned | |
850 | pages therein. This results in much less memory wastage | |
851 | than the traditional implementation of valloc. */ | |
852 | ||
853 | char *allocation, *a, *enda; | |
854 | size_t alloc_size, head_slop, tail_slop; | |
855 | int multiple_pages = (entry_size == G.pagesize); | |
856 | ||
857 | if (multiple_pages) | |
858 | alloc_size = GGC_QUIRE_SIZE * G.pagesize; | |
859 | else | |
860 | alloc_size = entry_size + G.pagesize - 1; | |
ec4d7730 | 861 | allocation = XNEWVEC (char, alloc_size); |
130fadbb | 862 | |
2a6e6fea | 863 | page = (char *) (((uintptr_t) allocation + G.pagesize - 1) & -G.pagesize); |
130fadbb RH |
864 | head_slop = page - allocation; |
865 | if (multiple_pages) | |
866 | tail_slop = ((size_t) allocation + alloc_size) & (G.pagesize - 1); | |
867 | else | |
868 | tail_slop = alloc_size - entry_size - head_slop; | |
869 | enda = allocation + alloc_size - tail_slop; | |
870 | ||
871 | /* We allocated N pages, which are likely not aligned, leaving | |
872 | us with N-1 usable pages. We plan to place the page_group | |
873 | structure somewhere in the slop. */ | |
874 | if (head_slop >= sizeof (page_group)) | |
875 | group = (page_group *)page - 1; | |
876 | else | |
877 | { | |
878 | /* We magically got an aligned allocation. Too bad, we have | |
879 | to waste a page anyway. */ | |
880 | if (tail_slop == 0) | |
881 | { | |
882 | enda -= G.pagesize; | |
883 | tail_slop += G.pagesize; | |
884 | } | |
282899df | 885 | gcc_assert (tail_slop >= sizeof (page_group)); |
130fadbb RH |
886 | group = (page_group *)enda; |
887 | tail_slop -= sizeof (page_group); | |
888 | } | |
889 | ||
890 | /* Remember that we allocated this memory. */ | |
891 | group->next = G.page_groups; | |
892 | group->allocation = allocation; | |
893 | group->alloc_size = alloc_size; | |
894 | group->in_use = 0; | |
895 | G.page_groups = group; | |
896 | G.bytes_mapped += alloc_size; | |
897 | ||
898 | /* If we allocated multiple pages, put the rest on the free list. */ | |
899 | if (multiple_pages) | |
900 | { | |
901 | struct page_entry *e, *f = G.free_pages; | |
902 | for (a = enda - G.pagesize; a != page; a -= G.pagesize) | |
903 | { | |
ec4d7730 | 904 | e = XCNEWVAR (struct page_entry, page_entry_size); |
130fadbb RH |
905 | e->order = order; |
906 | e->bytes = G.pagesize; | |
907 | e->page = a; | |
908 | e->group = group; | |
909 | e->next = f; | |
910 | f = e; | |
911 | } | |
912 | G.free_pages = f; | |
913 | } | |
914 | } | |
915 | #endif | |
21341cfd AS |
916 | |
917 | if (entry == NULL) | |
d3bfe4de | 918 | entry = XCNEWVAR (struct page_entry, page_entry_size); |
21341cfd AS |
919 | |
920 | entry->bytes = entry_size; | |
921 | entry->page = page; | |
922 | entry->context_depth = G.context_depth; | |
923 | entry->order = order; | |
924 | entry->num_free_objects = num_objects; | |
925 | entry->next_bit_hint = 1; | |
926 | ||
52895e1a RH |
927 | G.context_depth_allocations |= (unsigned long)1 << G.context_depth; |
928 | ||
130fadbb RH |
929 | #ifdef USING_MALLOC_PAGE_GROUPS |
930 | entry->group = group; | |
931 | set_page_group_in_use (group, page); | |
932 | #endif | |
933 | ||
21341cfd AS |
934 | /* Set the one-past-the-end in-use bit. This acts as a sentry as we |
935 | increment the hint. */ | |
936 | entry->in_use_p[num_objects / HOST_BITS_PER_LONG] | |
937 | = (unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG); | |
938 | ||
939 | set_page_table_entry (page, entry); | |
940 | ||
941 | if (GGC_DEBUG_LEVEL >= 2) | |
589005ff | 942 | fprintf (G.debug_file, |
89e93ce8 JJ |
943 | "Allocating page at %p, object size=" |
944 | HOST_SIZE_T_PRINT_UNSIGNED ", data %p-%p\n", | |
945 | (void *) entry, (fmt_size_t) OBJECT_SIZE (order), | |
c53930bb | 946 | (void *) page, (void *) (page + entry_size - 1)); |
21341cfd AS |
947 | |
948 | return entry; | |
949 | } | |
950 | ||
c4775f82 MS |
951 | /* Adjust the size of G.depth so that no index greater than the one |
952 | used by the top of the G.by_depth is used. */ | |
953 | ||
954 | static inline void | |
20c1dc5e | 955 | adjust_depth (void) |
c4775f82 MS |
956 | { |
957 | page_entry *top; | |
958 | ||
959 | if (G.by_depth_in_use) | |
960 | { | |
961 | top = G.by_depth[G.by_depth_in_use-1]; | |
962 | ||
e0bb17a8 KH |
963 | /* Peel back indices in depth that index into by_depth, so that |
964 | as new elements are added to by_depth, we note the indices | |
c4775f82 MS |
965 | of those elements, if they are for new context depths. */ |
966 | while (G.depth_in_use > (size_t)top->context_depth+1) | |
967 | --G.depth_in_use; | |
968 | } | |
969 | } | |
970 | ||
cb2ec151 | 971 | /* For a page that is no longer needed, put it on the free page list. */ |
21341cfd | 972 | |
685fe032 | 973 | static void |
20c1dc5e | 974 | free_page (page_entry *entry) |
21341cfd AS |
975 | { |
976 | if (GGC_DEBUG_LEVEL >= 2) | |
589005ff | 977 | fprintf (G.debug_file, |
20c1dc5e | 978 | "Deallocating page at %p, data %p-%p\n", (void *) entry, |
c53930bb | 979 | (void *) entry->page, (void *) (entry->page + entry->bytes - 1)); |
21341cfd | 980 | |
9a0a7d5d HPN |
981 | /* Mark the page as inaccessible. Discard the handle to avoid handle |
982 | leak. */ | |
35dee980 | 983 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (entry->page, entry->bytes)); |
9a0a7d5d | 984 | |
21341cfd AS |
985 | set_page_table_entry (entry->page, NULL); |
986 | ||
130fadbb RH |
987 | #ifdef USING_MALLOC_PAGE_GROUPS |
988 | clear_page_group_in_use (entry->group, entry->page); | |
989 | #endif | |
990 | ||
c4775f82 MS |
991 | if (G.by_depth_in_use > 1) |
992 | { | |
993 | page_entry *top = G.by_depth[G.by_depth_in_use-1]; | |
282899df NS |
994 | int i = entry->index_by_depth; |
995 | ||
996 | /* We cannot free a page from a context deeper than the current | |
997 | one. */ | |
998 | gcc_assert (entry->context_depth == top->context_depth); | |
b8698a0f | 999 | |
282899df NS |
1000 | /* Put top element into freed slot. */ |
1001 | G.by_depth[i] = top; | |
1002 | G.save_in_use[i] = G.save_in_use[G.by_depth_in_use-1]; | |
1003 | top->index_by_depth = i; | |
c4775f82 MS |
1004 | } |
1005 | --G.by_depth_in_use; | |
1006 | ||
1007 | adjust_depth (); | |
1008 | ||
21341cfd AS |
1009 | entry->next = G.free_pages; |
1010 | G.free_pages = entry; | |
1011 | } | |
1012 | ||
cb2ec151 | 1013 | /* Release the free page cache to the system. */ |
21341cfd | 1014 | |
4934cc53 | 1015 | static void |
20c1dc5e | 1016 | release_pages (void) |
21341cfd | 1017 | { |
e5207f1a JH |
1018 | size_t n1 = 0; |
1019 | size_t n2 = 0; | |
711a3d82 AK |
1020 | #ifdef USING_MADVISE |
1021 | page_entry *p, *start_p; | |
1022 | char *start; | |
1023 | size_t len; | |
d33ef9a5 AK |
1024 | size_t mapped_len; |
1025 | page_entry *next, *prev, *newprev; | |
1026 | size_t free_unit = (GGC_QUIRE_SIZE/2) * G.pagesize; | |
1027 | ||
1028 | /* First free larger continuous areas to the OS. | |
1029 | This allows other allocators to grab these areas if needed. | |
1030 | This is only done on larger chunks to avoid fragmentation. | |
1031 | This does not always work because the free_pages list is only | |
1032 | approximately sorted. */ | |
1033 | ||
1034 | p = G.free_pages; | |
1035 | prev = NULL; | |
1036 | while (p) | |
1037 | { | |
1038 | start = p->page; | |
1039 | start_p = p; | |
1040 | len = 0; | |
1041 | mapped_len = 0; | |
1042 | newprev = prev; | |
1043 | while (p && p->page == start + len) | |
1044 | { | |
1045 | len += p->bytes; | |
1046 | if (!p->discarded) | |
1047 | mapped_len += p->bytes; | |
1048 | newprev = p; | |
1049 | p = p->next; | |
1050 | } | |
1051 | if (len >= free_unit) | |
1052 | { | |
1053 | while (start_p != p) | |
1054 | { | |
1055 | next = start_p->next; | |
1056 | free (start_p); | |
1057 | start_p = next; | |
1058 | } | |
1059 | munmap (start, len); | |
1060 | if (prev) | |
1061 | prev->next = p; | |
1062 | else | |
1063 | G.free_pages = p; | |
1064 | G.bytes_mapped -= mapped_len; | |
e5207f1a | 1065 | n1 += len; |
d33ef9a5 AK |
1066 | continue; |
1067 | } | |
1068 | prev = newprev; | |
1069 | } | |
1070 | ||
1071 | /* Now give back the fragmented pages to the OS, but keep the address | |
1072 | space to reuse it next time. */ | |
711a3d82 AK |
1073 | |
1074 | for (p = G.free_pages; p; ) | |
1075 | { | |
1076 | if (p->discarded) | |
1077 | { | |
1078 | p = p->next; | |
1079 | continue; | |
1080 | } | |
1081 | start = p->page; | |
1082 | len = p->bytes; | |
1083 | start_p = p; | |
1084 | p = p->next; | |
1085 | while (p && p->page == start + len) | |
1086 | { | |
1087 | len += p->bytes; | |
1088 | p = p->next; | |
1089 | } | |
1090 | /* Give the page back to the kernel, but don't free the mapping. | |
1091 | This avoids fragmentation in the virtual memory map of the | |
1092 | process. Next time we can reuse it by just touching it. */ | |
1093 | madvise (start, len, MADV_DONTNEED); | |
1094 | /* Don't count those pages as mapped to not touch the garbage collector | |
1095 | unnecessarily. */ | |
1096 | G.bytes_mapped -= len; | |
e5207f1a | 1097 | n2 += len; |
711a3d82 AK |
1098 | while (start_p != p) |
1099 | { | |
1100 | start_p->discarded = true; | |
1101 | start_p = start_p->next; | |
1102 | } | |
1103 | } | |
1104 | #endif | |
1105 | #if defined(USING_MMAP) && !defined(USING_MADVISE) | |
130fadbb | 1106 | page_entry *p, *next; |
21341cfd AS |
1107 | char *start; |
1108 | size_t len; | |
1109 | ||
054f5e69 | 1110 | /* Gather up adjacent pages so they are unmapped together. */ |
21341cfd | 1111 | p = G.free_pages; |
21341cfd AS |
1112 | |
1113 | while (p) | |
1114 | { | |
054f5e69 | 1115 | start = p->page; |
21341cfd | 1116 | next = p->next; |
054f5e69 | 1117 | len = p->bytes; |
21341cfd AS |
1118 | free (p); |
1119 | p = next; | |
21341cfd | 1120 | |
054f5e69 ZW |
1121 | while (p && p->page == start + len) |
1122 | { | |
1123 | next = p->next; | |
1124 | len += p->bytes; | |
1125 | free (p); | |
1126 | p = next; | |
1127 | } | |
1128 | ||
1129 | munmap (start, len); | |
e5207f1a | 1130 | n1 += len; |
054f5e69 ZW |
1131 | G.bytes_mapped -= len; |
1132 | } | |
005537df | 1133 | |
21341cfd | 1134 | G.free_pages = NULL; |
130fadbb RH |
1135 | #endif |
1136 | #ifdef USING_MALLOC_PAGE_GROUPS | |
1137 | page_entry **pp, *p; | |
1138 | page_group **gp, *g; | |
1139 | ||
1140 | /* Remove all pages from free page groups from the list. */ | |
1141 | pp = &G.free_pages; | |
1142 | while ((p = *pp) != NULL) | |
1143 | if (p->group->in_use == 0) | |
1144 | { | |
1145 | *pp = p->next; | |
1146 | free (p); | |
1147 | } | |
1148 | else | |
1149 | pp = &p->next; | |
1150 | ||
1151 | /* Remove all free page groups, and release the storage. */ | |
1152 | gp = &G.page_groups; | |
1153 | while ((g = *gp) != NULL) | |
1154 | if (g->in_use == 0) | |
1155 | { | |
1156 | *gp = g->next; | |
589005ff | 1157 | G.bytes_mapped -= g->alloc_size; |
e5207f1a | 1158 | n1 += g->alloc_size; |
9e0d2031 | 1159 | free (g->allocation); |
130fadbb RH |
1160 | } |
1161 | else | |
1162 | gp = &g->next; | |
1163 | #endif | |
e5207f1a JH |
1164 | if (!quiet_flag && (n1 || n2)) |
1165 | { | |
1166 | fprintf (stderr, " {GC"); | |
1167 | if (n1) | |
79f4e20d | 1168 | fprintf (stderr, " released " PRsa (0), SIZE_AMOUNT (n1)); |
e5207f1a | 1169 | if (n2) |
79f4e20d | 1170 | fprintf (stderr, " madv_dontneed " PRsa (0), SIZE_AMOUNT (n2)); |
e5207f1a JH |
1171 | fprintf (stderr, "}"); |
1172 | } | |
21341cfd AS |
1173 | } |
1174 | ||
21341cfd | 1175 | /* This table provides a fast way to determine ceil(log_2(size)) for |
9fd51e67 | 1176 | allocation requests. The minimum allocation size is eight bytes. */ |
6583cf15 NC |
1177 | #define NUM_SIZE_LOOKUP 512 |
1178 | static unsigned char size_lookup[NUM_SIZE_LOOKUP] = | |
9fd51e67 | 1179 | { |
589005ff KH |
1180 | 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, |
1181 | 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | |
1182 | 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, | |
1183 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, | |
1184 | 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
1185 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
1186 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
21341cfd | 1187 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
21341cfd AS |
1188 | 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, |
1189 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
1190 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
1191 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
1192 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
1193 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
1194 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
1195 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
f5938dcd RG |
1196 | 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, |
1197 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1198 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1199 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1200 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1201 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1202 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1203 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1204 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1205 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1206 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1207 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1208 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1209 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
1210 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
ecf7b86f | 1211 | 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 |
21341cfd AS |
1212 | }; |
1213 | ||
b9bd6f74 TT |
1214 | /* For a given size of memory requested for allocation, return the |
1215 | actual size that is going to be allocated, as well as the size | |
1216 | order. */ | |
1217 | ||
1218 | static void | |
1219 | ggc_round_alloc_size_1 (size_t requested_size, | |
1220 | size_t *size_order, | |
1221 | size_t *alloced_size) | |
1222 | { | |
1223 | size_t order, object_size; | |
1224 | ||
1225 | if (requested_size < NUM_SIZE_LOOKUP) | |
1226 | { | |
1227 | order = size_lookup[requested_size]; | |
1228 | object_size = OBJECT_SIZE (order); | |
1229 | } | |
1230 | else | |
1231 | { | |
1232 | order = 10; | |
1233 | while (requested_size > (object_size = OBJECT_SIZE (order))) | |
1234 | order++; | |
1235 | } | |
1236 | ||
1237 | if (size_order) | |
1238 | *size_order = order; | |
1239 | if (alloced_size) | |
1240 | *alloced_size = object_size; | |
1241 | } | |
1242 | ||
1243 | /* For a given size of memory requested for allocation, return the | |
1244 | actual size that is going to be allocated. */ | |
1245 | ||
1246 | size_t | |
1247 | ggc_round_alloc_size (size_t requested_size) | |
1248 | { | |
1249 | size_t size = 0; | |
1250 | ||
1251 | ggc_round_alloc_size_1 (requested_size, NULL, &size); | |
1252 | return size; | |
1253 | } | |
1254 | ||
2a304777 JM |
1255 | /* Push a finalizer onto the appropriate vec. */ |
1256 | ||
1257 | static void | |
1258 | add_finalizer (void *result, void (*f)(void *), size_t s, size_t n) | |
1259 | { | |
1260 | if (f == NULL) | |
1261 | /* No finalizer. */; | |
1262 | else if (n == 1) | |
1263 | { | |
1264 | finalizer fin (result, f); | |
1265 | G.finalizers[G.context_depth].safe_push (fin); | |
1266 | } | |
1267 | else | |
1268 | { | |
1269 | vec_finalizer fin (reinterpret_cast<uintptr_t> (result), f, s, n); | |
1270 | G.vec_finalizers[G.context_depth].safe_push (fin); | |
1271 | } | |
1272 | } | |
1273 | ||
aa40083d | 1274 | /* Allocate a chunk of memory of SIZE bytes. Its contents are undefined. */ |
cb2ec151 | 1275 | |
005537df | 1276 | void * |
de49ce19 TS |
1277 | ggc_internal_alloc (size_t size, void (*f)(void *), size_t s, size_t n |
1278 | MEM_STAT_DECL) | |
21341cfd | 1279 | { |
685fe032 | 1280 | size_t order, word, bit, object_offset, object_size; |
21341cfd AS |
1281 | struct page_entry *entry; |
1282 | void *result; | |
1283 | ||
b9bd6f74 | 1284 | ggc_round_alloc_size_1 (size, &order, &object_size); |
21341cfd AS |
1285 | |
1286 | /* If there are non-full pages for this size allocation, they are at | |
1287 | the head of the list. */ | |
1288 | entry = G.pages[order]; | |
1289 | ||
1290 | /* If there is no page for this object size, or all pages in this | |
1291 | context are full, allocate a new page. */ | |
4934cc53 | 1292 | if (entry == NULL || entry->num_free_objects == 0) |
21341cfd AS |
1293 | { |
1294 | struct page_entry *new_entry; | |
1295 | new_entry = alloc_page (order); | |
589005ff | 1296 | |
c4775f82 MS |
1297 | new_entry->index_by_depth = G.by_depth_in_use; |
1298 | push_by_depth (new_entry, 0); | |
1299 | ||
1300 | /* We can skip context depths, if we do, make sure we go all the | |
1301 | way to the new depth. */ | |
1302 | while (new_entry->context_depth >= G.depth_in_use) | |
1303 | push_depth (G.by_depth_in_use-1); | |
1304 | ||
9bf793f9 JL |
1305 | /* If this is the only entry, it's also the tail. If it is not |
1306 | the only entry, then we must update the PREV pointer of the | |
1307 | ENTRY (G.pages[order]) to point to our new page entry. */ | |
21341cfd AS |
1308 | if (entry == NULL) |
1309 | G.page_tails[order] = new_entry; | |
9bf793f9 JL |
1310 | else |
1311 | entry->prev = new_entry; | |
589005ff | 1312 | |
9bf793f9 JL |
1313 | /* Put new pages at the head of the page list. By definition the |
1314 | entry at the head of the list always has a NULL pointer. */ | |
21341cfd | 1315 | new_entry->next = entry; |
9bf793f9 | 1316 | new_entry->prev = NULL; |
21341cfd AS |
1317 | entry = new_entry; |
1318 | G.pages[order] = new_entry; | |
1319 | ||
1320 | /* For a new page, we know the word and bit positions (in the | |
1321 | in_use bitmap) of the first available object -- they're zero. */ | |
1322 | new_entry->next_bit_hint = 1; | |
1323 | word = 0; | |
1324 | bit = 0; | |
1325 | object_offset = 0; | |
1326 | } | |
1327 | else | |
1328 | { | |
1329 | /* First try to use the hint left from the previous allocation | |
1330 | to locate a clear bit in the in-use bitmap. We've made sure | |
1331 | that the one-past-the-end bit is always set, so if the hint | |
1332 | has run over, this test will fail. */ | |
1333 | unsigned hint = entry->next_bit_hint; | |
1334 | word = hint / HOST_BITS_PER_LONG; | |
1335 | bit = hint % HOST_BITS_PER_LONG; | |
589005ff | 1336 | |
21341cfd AS |
1337 | /* If the hint didn't work, scan the bitmap from the beginning. */ |
1338 | if ((entry->in_use_p[word] >> bit) & 1) | |
1339 | { | |
1340 | word = bit = 0; | |
1341 | while (~entry->in_use_p[word] == 0) | |
1342 | ++word; | |
6f0947e4 SB |
1343 | |
1344 | #if GCC_VERSION >= 3004 | |
1345 | bit = __builtin_ctzl (~entry->in_use_p[word]); | |
1346 | #else | |
21341cfd AS |
1347 | while ((entry->in_use_p[word] >> bit) & 1) |
1348 | ++bit; | |
6f0947e4 SB |
1349 | #endif |
1350 | ||
21341cfd AS |
1351 | hint = word * HOST_BITS_PER_LONG + bit; |
1352 | } | |
1353 | ||
1354 | /* Next time, try the next bit. */ | |
1355 | entry->next_bit_hint = hint + 1; | |
1356 | ||
685fe032 | 1357 | object_offset = hint * object_size; |
21341cfd AS |
1358 | } |
1359 | ||
1360 | /* Set the in-use bit. */ | |
1361 | entry->in_use_p[word] |= ((unsigned long) 1 << bit); | |
1362 | ||
1363 | /* Keep a running total of the number of free objects. If this page | |
1364 | fills up, we may have to move it to the end of the list if the | |
1365 | next page isn't full. If the next page is full, all subsequent | |
1366 | pages are full, so there's no need to move it. */ | |
1367 | if (--entry->num_free_objects == 0 | |
1368 | && entry->next != NULL | |
1369 | && entry->next->num_free_objects > 0) | |
1370 | { | |
9bf793f9 | 1371 | /* We have a new head for the list. */ |
21341cfd | 1372 | G.pages[order] = entry->next; |
9bf793f9 JL |
1373 | |
1374 | /* We are moving ENTRY to the end of the page table list. | |
1375 | The new page at the head of the list will have NULL in | |
1376 | its PREV field and ENTRY will have NULL in its NEXT field. */ | |
1377 | entry->next->prev = NULL; | |
21341cfd | 1378 | entry->next = NULL; |
9bf793f9 JL |
1379 | |
1380 | /* Append ENTRY to the tail of the list. */ | |
1381 | entry->prev = G.page_tails[order]; | |
21341cfd AS |
1382 | G.page_tails[order]->next = entry; |
1383 | G.page_tails[order] = entry; | |
1384 | } | |
1385 | ||
1386 | /* Calculate the object's address. */ | |
1387 | result = entry->page + object_offset; | |
7aa6d18a SB |
1388 | if (GATHER_STATISTICS) |
1389 | ggc_record_overhead (OBJECT_SIZE (order), OBJECT_SIZE (order) - size, | |
1390 | result FINAL_PASS_MEM_STAT); | |
21341cfd | 1391 | |
3788cc17 | 1392 | #ifdef ENABLE_GC_CHECKING |
9a0a7d5d HPN |
1393 | /* Keep poisoning-by-writing-0xaf the object, in an attempt to keep the |
1394 | exact same semantics in presence of memory bugs, regardless of | |
1395 | ENABLE_VALGRIND_CHECKING. We override this request below. Drop the | |
1396 | handle to avoid handle leak. */ | |
35dee980 | 1397 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (result, object_size)); |
9a0a7d5d | 1398 | |
f8a83ee3 ZW |
1399 | /* `Poison' the entire allocated object, including any padding at |
1400 | the end. */ | |
685fe032 | 1401 | memset (result, 0xaf, object_size); |
9a0a7d5d HPN |
1402 | |
1403 | /* Make the bytes after the end of the object unaccessible. Discard the | |
1404 | handle to avoid handle leak. */ | |
35dee980 HPN |
1405 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS ((char *) result + size, |
1406 | object_size - size)); | |
21341cfd | 1407 | #endif |
cb2ec151 | 1408 | |
9a0a7d5d HPN |
1409 | /* Tell Valgrind that the memory is there, but its content isn't |
1410 | defined. The bytes at the end of the object are still marked | |
1411 | unaccessible. */ | |
35dee980 | 1412 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (result, size)); |
9a0a7d5d | 1413 | |
21341cfd AS |
1414 | /* Keep track of how many bytes are being allocated. This |
1415 | information is used in deciding when to collect. */ | |
685fe032 | 1416 | G.allocated += object_size; |
21341cfd | 1417 | |
8d18c628 ZD |
1418 | /* For timevar statistics. */ |
1419 | timevar_ggc_mem_total += object_size; | |
1420 | ||
2a304777 JM |
1421 | if (f) |
1422 | add_finalizer (result, f, s, n); | |
de49ce19 | 1423 | |
7aa6d18a SB |
1424 | if (GATHER_STATISTICS) |
1425 | { | |
1426 | size_t overhead = object_size - size; | |
adc4adcd | 1427 | |
7aa6d18a SB |
1428 | G.stats.total_overhead += overhead; |
1429 | G.stats.total_allocated += object_size; | |
1430 | G.stats.total_overhead_per_order[order] += overhead; | |
1431 | G.stats.total_allocated_per_order[order] += object_size; | |
adc4adcd | 1432 | |
7aa6d18a SB |
1433 | if (size <= 32) |
1434 | { | |
1435 | G.stats.total_overhead_under32 += overhead; | |
1436 | G.stats.total_allocated_under32 += object_size; | |
1437 | } | |
1438 | if (size <= 64) | |
1439 | { | |
1440 | G.stats.total_overhead_under64 += overhead; | |
1441 | G.stats.total_allocated_under64 += object_size; | |
1442 | } | |
1443 | if (size <= 128) | |
1444 | { | |
1445 | G.stats.total_overhead_under128 += overhead; | |
1446 | G.stats.total_allocated_under128 += object_size; | |
1447 | } | |
1448 | } | |
685fe032 | 1449 | |
21341cfd | 1450 | if (GGC_DEBUG_LEVEL >= 3) |
589005ff | 1451 | fprintf (G.debug_file, |
89e93ce8 JJ |
1452 | "Allocating object, requested size=" |
1453 | HOST_SIZE_T_PRINT_UNSIGNED ", actual=" HOST_SIZE_T_PRINT_UNSIGNED | |
1454 | " at %p on %p\n", | |
1455 | (fmt_size_t) size, (fmt_size_t) object_size, result, | |
20c1dc5e | 1456 | (void *) entry); |
21341cfd AS |
1457 | |
1458 | return result; | |
1459 | } | |
1460 | ||
dae4174e TT |
1461 | /* Mark function for strings. */ |
1462 | ||
1463 | void | |
1464 | gt_ggc_m_S (const void *p) | |
1465 | { | |
1466 | page_entry *entry; | |
1467 | unsigned bit, word; | |
1468 | unsigned long mask; | |
1469 | unsigned long offset; | |
1470 | ||
acb14262 | 1471 | if (!p) |
dae4174e TT |
1472 | return; |
1473 | ||
acb14262 RB |
1474 | /* Look up the page on which the object is alloced. If it was not |
1475 | GC allocated, gracefully bail out. */ | |
1476 | entry = safe_lookup_page_table_entry (p); | |
1477 | if (!entry) | |
1478 | return; | |
dae4174e TT |
1479 | |
1480 | /* Calculate the index of the object on the page; this is its bit | |
1481 | position in the in_use_p bitmap. Note that because a char* might | |
1482 | point to the middle of an object, we need special code here to | |
1483 | make sure P points to the start of an object. */ | |
1484 | offset = ((const char *) p - entry->page) % object_size_table[entry->order]; | |
1485 | if (offset) | |
1486 | { | |
1487 | /* Here we've seen a char* which does not point to the beginning | |
1488 | of an allocated object. We assume it points to the middle of | |
1489 | a STRING_CST. */ | |
1490 | gcc_assert (offset == offsetof (struct tree_string, str)); | |
1491 | p = ((const char *) p) - offset; | |
d3bfe4de | 1492 | gt_ggc_mx_lang_tree_node (CONST_CAST (void *, p)); |
dae4174e TT |
1493 | return; |
1494 | } | |
1495 | ||
1496 | bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order); | |
1497 | word = bit / HOST_BITS_PER_LONG; | |
1498 | mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG); | |
1499 | ||
1500 | /* If the bit was previously set, skip it. */ | |
1501 | if (entry->in_use_p[word] & mask) | |
1502 | return; | |
1503 | ||
1504 | /* Otherwise set it, and decrement the free object count. */ | |
1505 | entry->in_use_p[word] |= mask; | |
1506 | entry->num_free_objects -= 1; | |
1507 | ||
1508 | if (GGC_DEBUG_LEVEL >= 4) | |
1509 | fprintf (G.debug_file, "Marking %p\n", p); | |
1510 | ||
1511 | return; | |
1512 | } | |
1513 | ||
0823efed DN |
1514 | |
1515 | /* User-callable entry points for marking string X. */ | |
1516 | ||
1517 | void | |
1518 | gt_ggc_mx (const char *& x) | |
e69ac020 BE |
1519 | { |
1520 | gt_ggc_m_S (x); | |
1521 | } | |
1522 | ||
1523 | void | |
1524 | gt_ggc_mx (char *& x) | |
0823efed DN |
1525 | { |
1526 | gt_ggc_m_S (x); | |
1527 | } | |
1528 | ||
1529 | void | |
1530 | gt_ggc_mx (unsigned char *& x) | |
1531 | { | |
1532 | gt_ggc_m_S (x); | |
1533 | } | |
1534 | ||
1535 | void | |
1536 | gt_ggc_mx (unsigned char& x ATTRIBUTE_UNUSED) | |
1537 | { | |
1538 | } | |
1539 | ||
cb2ec151 | 1540 | /* If P is not marked, marks it and return false. Otherwise return true. |
21341cfd AS |
1541 | P must have been allocated by the GC allocator; it mustn't point to |
1542 | static objects, stack variables, or memory allocated with malloc. */ | |
cb2ec151 | 1543 | |
9a856f67 | 1544 | bool |
20c1dc5e | 1545 | ggc_set_mark (const void *p) |
21341cfd AS |
1546 | { |
1547 | page_entry *entry; | |
1548 | unsigned bit, word; | |
1549 | unsigned long mask; | |
1550 | ||
1551 | /* Look up the page on which the object is alloced. If the object | |
1552 | wasn't allocated by the collector, we'll probably die. */ | |
74c937ca | 1553 | entry = lookup_page_table_entry (p); |
282899df | 1554 | gcc_assert (entry); |
21341cfd AS |
1555 | |
1556 | /* Calculate the index of the object on the page; this is its bit | |
1557 | position in the in_use_p bitmap. */ | |
8537ed68 | 1558 | bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order); |
21341cfd AS |
1559 | word = bit / HOST_BITS_PER_LONG; |
1560 | mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG); | |
589005ff | 1561 | |
dc297297 | 1562 | /* If the bit was previously set, skip it. */ |
21341cfd | 1563 | if (entry->in_use_p[word] & mask) |
9a856f67 | 1564 | return true; |
21341cfd AS |
1565 | |
1566 | /* Otherwise set it, and decrement the free object count. */ | |
1567 | entry->in_use_p[word] |= mask; | |
1568 | entry->num_free_objects -= 1; | |
1569 | ||
21341cfd AS |
1570 | if (GGC_DEBUG_LEVEL >= 4) |
1571 | fprintf (G.debug_file, "Marking %p\n", p); | |
1572 | ||
9a856f67 | 1573 | return false; |
21341cfd AS |
1574 | } |
1575 | ||
9a856f67 | 1576 | /* Return true if P has been marked, zero otherwise. |
4c160717 RK |
1577 | P must have been allocated by the GC allocator; it mustn't point to |
1578 | static objects, stack variables, or memory allocated with malloc. */ | |
1579 | ||
9a856f67 | 1580 | bool |
20c1dc5e | 1581 | ggc_marked_p (const void *p) |
4c160717 RK |
1582 | { |
1583 | page_entry *entry; | |
1584 | unsigned bit, word; | |
1585 | unsigned long mask; | |
1586 | ||
1587 | /* Look up the page on which the object is alloced. If the object | |
1588 | wasn't allocated by the collector, we'll probably die. */ | |
1589 | entry = lookup_page_table_entry (p); | |
282899df | 1590 | gcc_assert (entry); |
4c160717 RK |
1591 | |
1592 | /* Calculate the index of the object on the page; this is its bit | |
1593 | position in the in_use_p bitmap. */ | |
8537ed68 | 1594 | bit = OFFSET_TO_BIT (((const char *) p) - entry->page, entry->order); |
4c160717 RK |
1595 | word = bit / HOST_BITS_PER_LONG; |
1596 | mask = (unsigned long) 1 << (bit % HOST_BITS_PER_LONG); | |
589005ff | 1597 | |
a4b5b2ae | 1598 | return (entry->in_use_p[word] & mask) != 0; |
4c160717 RK |
1599 | } |
1600 | ||
cb2ec151 RH |
1601 | /* Return the size of the gc-able object P. */ |
1602 | ||
3277221c | 1603 | size_t |
20c1dc5e | 1604 | ggc_get_size (const void *p) |
3277221c MM |
1605 | { |
1606 | page_entry *pe = lookup_page_table_entry (p); | |
2be510b8 | 1607 | return OBJECT_SIZE (pe->order); |
3277221c | 1608 | } |
685fe032 RH |
1609 | |
1610 | /* Release the memory for object P. */ | |
1611 | ||
1612 | void | |
1613 | ggc_free (void *p) | |
1614 | { | |
b086d530 TS |
1615 | if (in_gc) |
1616 | return; | |
1617 | ||
685fe032 RH |
1618 | page_entry *pe = lookup_page_table_entry (p); |
1619 | size_t order = pe->order; | |
1620 | size_t size = OBJECT_SIZE (order); | |
1621 | ||
7aa6d18a SB |
1622 | if (GATHER_STATISTICS) |
1623 | ggc_free_overhead (p); | |
07724022 | 1624 | |
685fe032 RH |
1625 | if (GGC_DEBUG_LEVEL >= 3) |
1626 | fprintf (G.debug_file, | |
89e93ce8 JJ |
1627 | "Freeing object, actual size=" |
1628 | HOST_SIZE_T_PRINT_UNSIGNED ", at %p on %p\n", | |
1629 | (fmt_size_t) size, p, (void *) pe); | |
685fe032 RH |
1630 | |
1631 | #ifdef ENABLE_GC_CHECKING | |
1632 | /* Poison the data, to indicate the data is garbage. */ | |
35dee980 | 1633 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (p, size)); |
685fe032 RH |
1634 | memset (p, 0xa5, size); |
1635 | #endif | |
1636 | /* Let valgrind know the object is free. */ | |
35dee980 | 1637 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (p, size)); |
685fe032 RH |
1638 | |
1639 | #ifdef ENABLE_GC_ALWAYS_COLLECT | |
1640 | /* In the completely-anal-checking mode, we do *not* immediately free | |
b8698a0f | 1641 | the data, but instead verify that the data is *actually* not |
685fe032 RH |
1642 | reachable the next time we collect. */ |
1643 | { | |
5ed6ace5 | 1644 | struct free_object *fo = XNEW (struct free_object); |
685fe032 RH |
1645 | fo->object = p; |
1646 | fo->next = G.free_object_list; | |
1647 | G.free_object_list = fo; | |
1648 | } | |
1649 | #else | |
1650 | { | |
1651 | unsigned int bit_offset, word, bit; | |
1652 | ||
1653 | G.allocated -= size; | |
1654 | ||
1655 | /* Mark the object not-in-use. */ | |
1656 | bit_offset = OFFSET_TO_BIT (((const char *) p) - pe->page, order); | |
1657 | word = bit_offset / HOST_BITS_PER_LONG; | |
1658 | bit = bit_offset % HOST_BITS_PER_LONG; | |
1659 | pe->in_use_p[word] &= ~(1UL << bit); | |
1660 | ||
1661 | if (pe->num_free_objects++ == 0) | |
1662 | { | |
9bf793f9 JL |
1663 | page_entry *p, *q; |
1664 | ||
685fe032 RH |
1665 | /* If the page is completely full, then it's supposed to |
1666 | be after all pages that aren't. Since we've freed one | |
1667 | object from a page that was full, we need to move the | |
b8698a0f | 1668 | page to the head of the list. |
685fe032 | 1669 | |
9bf793f9 JL |
1670 | PE is the node we want to move. Q is the previous node |
1671 | and P is the next node in the list. */ | |
1672 | q = pe->prev; | |
685fe032 RH |
1673 | if (q && q->num_free_objects == 0) |
1674 | { | |
1675 | p = pe->next; | |
9bf793f9 | 1676 | |
685fe032 | 1677 | q->next = p; |
9bf793f9 JL |
1678 | |
1679 | /* If PE was at the end of the list, then Q becomes the | |
1680 | new end of the list. If PE was not the end of the | |
1681 | list, then we need to update the PREV field for P. */ | |
685fe032 RH |
1682 | if (!p) |
1683 | G.page_tails[order] = q; | |
9bf793f9 JL |
1684 | else |
1685 | p->prev = q; | |
1686 | ||
1687 | /* Move PE to the head of the list. */ | |
685fe032 | 1688 | pe->next = G.pages[order]; |
9bf793f9 JL |
1689 | pe->prev = NULL; |
1690 | G.pages[order]->prev = pe; | |
685fe032 RH |
1691 | G.pages[order] = pe; |
1692 | } | |
1693 | ||
1694 | /* Reset the hint bit to point to the only free object. */ | |
1695 | pe->next_bit_hint = bit_offset; | |
1696 | } | |
1697 | } | |
1698 | #endif | |
1699 | } | |
21341cfd | 1700 | \f |
8537ed68 ZW |
1701 | /* Subroutine of init_ggc which computes the pair of numbers used to |
1702 | perform division by OBJECT_SIZE (order) and fills in inverse_table[]. | |
1703 | ||
1704 | This algorithm is taken from Granlund and Montgomery's paper | |
1705 | "Division by Invariant Integers using Multiplication" | |
1706 | (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by | |
1707 | constants). */ | |
1708 | ||
1709 | static void | |
20c1dc5e | 1710 | compute_inverse (unsigned order) |
8537ed68 | 1711 | { |
b8698a0f | 1712 | size_t size, inv; |
75d75435 | 1713 | unsigned int e; |
280cf02a | 1714 | |
8537ed68 ZW |
1715 | size = OBJECT_SIZE (order); |
1716 | e = 0; | |
1717 | while (size % 2 == 0) | |
1718 | { | |
1719 | e++; | |
1720 | size >>= 1; | |
1721 | } | |
cb2ec151 | 1722 | |
8537ed68 ZW |
1723 | inv = size; |
1724 | while (inv * size != 1) | |
1725 | inv = inv * (2 - inv*size); | |
1726 | ||
1727 | DIV_MULT (order) = inv; | |
1728 | DIV_SHIFT (order) = e; | |
1729 | } | |
1730 | ||
1731 | /* Initialize the ggc-mmap allocator. */ | |
21341cfd | 1732 | void |
20c1dc5e | 1733 | init_ggc (void) |
21341cfd | 1734 | { |
3edf64aa | 1735 | static bool init_p = false; |
2be510b8 MM |
1736 | unsigned order; |
1737 | ||
3edf64aa DM |
1738 | if (init_p) |
1739 | return; | |
1740 | init_p = true; | |
1741 | ||
c3284718 | 1742 | G.pagesize = getpagesize (); |
21341cfd AS |
1743 | G.lg_pagesize = exact_log2 (G.pagesize); |
1744 | ||
825b6926 | 1745 | #ifdef HAVE_MMAP_DEV_ZERO |
21341cfd AS |
1746 | G.dev_zero_fd = open ("/dev/zero", O_RDONLY); |
1747 | if (G.dev_zero_fd == -1) | |
c770ac2b | 1748 | internal_error ("open /dev/zero: %m"); |
21341cfd AS |
1749 | #endif |
1750 | ||
1751 | #if 0 | |
1752 | G.debug_file = fopen ("ggc-mmap.debug", "w"); | |
1753 | #else | |
1754 | G.debug_file = stdout; | |
1755 | #endif | |
1756 | ||
825b6926 | 1757 | #ifdef USING_MMAP |
1b3e1423 RH |
1758 | /* StunOS has an amazing off-by-one error for the first mmap allocation |
1759 | after fiddling with RLIMIT_STACK. The result, as hard as it is to | |
1760 | believe, is an unaligned page allocation, which would cause us to | |
1761 | hork badly if we tried to use it. */ | |
1762 | { | |
25f0ea81 | 1763 | char *p = alloc_anon (NULL, G.pagesize, true); |
825b6926 | 1764 | struct page_entry *e; |
2a6e6fea | 1765 | if ((uintptr_t)p & (G.pagesize - 1)) |
1b3e1423 RH |
1766 | { |
1767 | /* How losing. Discard this one and try another. If we still | |
1768 | can't get something useful, give up. */ | |
1769 | ||
25f0ea81 | 1770 | p = alloc_anon (NULL, G.pagesize, true); |
2a6e6fea | 1771 | gcc_assert (!((uintptr_t)p & (G.pagesize - 1))); |
1b3e1423 | 1772 | } |
825b6926 | 1773 | |
dc297297 | 1774 | /* We have a good page, might as well hold onto it... */ |
5ed6ace5 | 1775 | e = XCNEW (struct page_entry); |
825b6926 ZW |
1776 | e->bytes = G.pagesize; |
1777 | e->page = p; | |
1778 | e->next = G.free_pages; | |
1779 | G.free_pages = e; | |
1b3e1423 RH |
1780 | } |
1781 | #endif | |
2be510b8 MM |
1782 | |
1783 | /* Initialize the object size table. */ | |
1784 | for (order = 0; order < HOST_BITS_PER_PTR; ++order) | |
1785 | object_size_table[order] = (size_t) 1 << order; | |
1786 | for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order) | |
b1095f9c MM |
1787 | { |
1788 | size_t s = extra_order_size_table[order - HOST_BITS_PER_PTR]; | |
a469a4f2 RG |
1789 | |
1790 | /* If S is not a multiple of the MAX_ALIGNMENT, then round it up | |
1791 | so that we're sure of getting aligned memory. */ | |
1792 | s = ROUND_UP (s, MAX_ALIGNMENT); | |
b1095f9c MM |
1793 | object_size_table[order] = s; |
1794 | } | |
2be510b8 | 1795 | |
8537ed68 | 1796 | /* Initialize the objects-per-page and inverse tables. */ |
2be510b8 MM |
1797 | for (order = 0; order < NUM_ORDERS; ++order) |
1798 | { | |
1799 | objects_per_page_table[order] = G.pagesize / OBJECT_SIZE (order); | |
1800 | if (objects_per_page_table[order] == 0) | |
1801 | objects_per_page_table[order] = 1; | |
8537ed68 | 1802 | compute_inverse (order); |
2be510b8 MM |
1803 | } |
1804 | ||
1805 | /* Reset the size_lookup array to put appropriately sized objects in | |
1806 | the special orders. All objects bigger than the previous power | |
1807 | of two, but no greater than the special size, should go in the | |
a469a4f2 | 1808 | new order. */ |
2be510b8 MM |
1809 | for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order) |
1810 | { | |
a469a4f2 RG |
1811 | int o; |
1812 | int i; | |
c4775f82 | 1813 | |
6583cf15 NC |
1814 | i = OBJECT_SIZE (order); |
1815 | if (i >= NUM_SIZE_LOOKUP) | |
1816 | continue; | |
1817 | ||
1818 | for (o = size_lookup[i]; o == size_lookup [i]; --i) | |
a469a4f2 RG |
1819 | size_lookup[i] = order; |
1820 | } | |
ecf7b86f | 1821 | |
c4775f82 MS |
1822 | G.depth_in_use = 0; |
1823 | G.depth_max = 10; | |
5ed6ace5 | 1824 | G.depth = XNEWVEC (unsigned int, G.depth_max); |
c4775f82 MS |
1825 | |
1826 | G.by_depth_in_use = 0; | |
1827 | G.by_depth_max = INITIAL_PTE_COUNT; | |
5ed6ace5 MD |
1828 | G.by_depth = XNEWVEC (page_entry *, G.by_depth_max); |
1829 | G.save_in_use = XNEWVEC (unsigned long *, G.by_depth_max); | |
2a304777 JM |
1830 | |
1831 | /* Allocate space for the depth 0 finalizers. */ | |
1832 | G.finalizers.safe_push (vNULL); | |
1833 | G.vec_finalizers.safe_push (vNULL); | |
1834 | gcc_assert (G.finalizers.length() == 1); | |
21341cfd AS |
1835 | } |
1836 | ||
4934cc53 MM |
1837 | /* Merge the SAVE_IN_USE_P and IN_USE_P arrays in P so that IN_USE_P |
1838 | reflects reality. Recalculate NUM_FREE_OBJECTS as well. */ | |
1839 | ||
1840 | static void | |
20c1dc5e | 1841 | ggc_recalculate_in_use_p (page_entry *p) |
4934cc53 MM |
1842 | { |
1843 | unsigned int i; | |
1844 | size_t num_objects; | |
1845 | ||
589005ff | 1846 | /* Because the past-the-end bit in in_use_p is always set, we |
4934cc53 | 1847 | pretend there is one additional object. */ |
17211ab5 | 1848 | num_objects = OBJECTS_IN_PAGE (p) + 1; |
4934cc53 MM |
1849 | |
1850 | /* Reset the free object count. */ | |
1851 | p->num_free_objects = num_objects; | |
1852 | ||
1853 | /* Combine the IN_USE_P and SAVE_IN_USE_P arrays. */ | |
589005ff | 1854 | for (i = 0; |
2be510b8 MM |
1855 | i < CEIL (BITMAP_SIZE (num_objects), |
1856 | sizeof (*p->in_use_p)); | |
4934cc53 MM |
1857 | ++i) |
1858 | { | |
1859 | unsigned long j; | |
1860 | ||
1861 | /* Something is in use if it is marked, or if it was in use in a | |
1862 | context further down the context stack. */ | |
c4775f82 | 1863 | p->in_use_p[i] |= save_in_use_p (p)[i]; |
4934cc53 MM |
1864 | |
1865 | /* Decrement the free object count for every object allocated. */ | |
1866 | for (j = p->in_use_p[i]; j; j >>= 1) | |
1867 | p->num_free_objects -= (j & 1); | |
1868 | } | |
1869 | ||
282899df | 1870 | gcc_assert (p->num_free_objects < num_objects); |
4934cc53 | 1871 | } |
21341cfd | 1872 | \f |
cb2ec151 RH |
1873 | /* Unmark all objects. */ |
1874 | ||
685fe032 | 1875 | static void |
20c1dc5e | 1876 | clear_marks (void) |
21341cfd AS |
1877 | { |
1878 | unsigned order; | |
1879 | ||
2be510b8 | 1880 | for (order = 2; order < NUM_ORDERS; order++) |
21341cfd | 1881 | { |
21341cfd AS |
1882 | page_entry *p; |
1883 | ||
1884 | for (p = G.pages[order]; p != NULL; p = p->next) | |
1885 | { | |
17211ab5 GK |
1886 | size_t num_objects = OBJECTS_IN_PAGE (p); |
1887 | size_t bitmap_size = BITMAP_SIZE (num_objects + 1); | |
1888 | ||
21341cfd | 1889 | /* The data should be page-aligned. */ |
2a6e6fea | 1890 | gcc_assert (!((uintptr_t) p->page & (G.pagesize - 1))); |
21341cfd AS |
1891 | |
1892 | /* Pages that aren't in the topmost context are not collected; | |
1893 | nevertheless, we need their in-use bit vectors to store GC | |
1894 | marks. So, back them up first. */ | |
4934cc53 | 1895 | if (p->context_depth < G.context_depth) |
21341cfd | 1896 | { |
c4775f82 | 1897 | if (! save_in_use_p (p)) |
d3bfe4de | 1898 | save_in_use_p (p) = XNEWVAR (unsigned long, bitmap_size); |
c4775f82 | 1899 | memcpy (save_in_use_p (p), p->in_use_p, bitmap_size); |
21341cfd AS |
1900 | } |
1901 | ||
1902 | /* Reset reset the number of free objects and clear the | |
1903 | in-use bits. These will be adjusted by mark_obj. */ | |
1904 | p->num_free_objects = num_objects; | |
1905 | memset (p->in_use_p, 0, bitmap_size); | |
1906 | ||
1907 | /* Make sure the one-past-the-end bit is always set. */ | |
589005ff | 1908 | p->in_use_p[num_objects / HOST_BITS_PER_LONG] |
21341cfd AS |
1909 | = ((unsigned long) 1 << (num_objects % HOST_BITS_PER_LONG)); |
1910 | } | |
1911 | } | |
1912 | } | |
1913 | ||
c3af645c TS |
1914 | /* Check if any blocks with a registered finalizer have become unmarked. If so |
1915 | run the finalizer and unregister it because the block is about to be freed. | |
1916 | Note that no garantee is made about what order finalizers will run in so | |
1917 | touching other objects in gc memory is extremely unwise. */ | |
1918 | ||
de49ce19 TS |
1919 | static void |
1920 | ggc_handle_finalizers () | |
1921 | { | |
2a304777 JM |
1922 | unsigned dlen = G.finalizers.length(); |
1923 | for (unsigned d = G.context_depth; d < dlen; ++d) | |
de49ce19 | 1924 | { |
2a304777 JM |
1925 | vec<finalizer> &v = G.finalizers[d]; |
1926 | unsigned length = v.length (); | |
1927 | for (unsigned int i = 0; i < length;) | |
de49ce19 | 1928 | { |
2a304777 JM |
1929 | finalizer &f = v[i]; |
1930 | if (!ggc_marked_p (f.addr ())) | |
1931 | { | |
1932 | f.call (); | |
1933 | v.unordered_remove (i); | |
1934 | length--; | |
1935 | } | |
1936 | else | |
1937 | i++; | |
de49ce19 | 1938 | } |
de49ce19 TS |
1939 | } |
1940 | ||
2a304777 JM |
1941 | gcc_assert (dlen == G.vec_finalizers.length()); |
1942 | for (unsigned d = G.context_depth; d < dlen; ++d) | |
de49ce19 | 1943 | { |
2a304777 JM |
1944 | vec<vec_finalizer> &vv = G.vec_finalizers[d]; |
1945 | unsigned length = vv.length (); | |
1946 | for (unsigned int i = 0; i < length;) | |
de49ce19 | 1947 | { |
2a304777 JM |
1948 | vec_finalizer &f = vv[i]; |
1949 | if (!ggc_marked_p (f.addr ())) | |
1950 | { | |
1951 | f.call (); | |
1952 | vv.unordered_remove (i); | |
1953 | length--; | |
1954 | } | |
1955 | else | |
1956 | i++; | |
de49ce19 | 1957 | } |
de49ce19 TS |
1958 | } |
1959 | } | |
1960 | ||
cb2ec151 RH |
1961 | /* Free all empty pages. Partially empty pages need no attention |
1962 | because the `mark' bit doubles as an `unused' bit. */ | |
1963 | ||
685fe032 | 1964 | static void |
20c1dc5e | 1965 | sweep_pages (void) |
21341cfd AS |
1966 | { |
1967 | unsigned order; | |
1968 | ||
2be510b8 | 1969 | for (order = 2; order < NUM_ORDERS; order++) |
21341cfd AS |
1970 | { |
1971 | /* The last page-entry to consider, regardless of entries | |
1972 | placed at the end of the list. */ | |
1973 | page_entry * const last = G.page_tails[order]; | |
1974 | ||
17211ab5 | 1975 | size_t num_objects; |
054f5e69 | 1976 | size_t live_objects; |
21341cfd AS |
1977 | page_entry *p, *previous; |
1978 | int done; | |
589005ff | 1979 | |
21341cfd AS |
1980 | p = G.pages[order]; |
1981 | if (p == NULL) | |
1982 | continue; | |
1983 | ||
1984 | previous = NULL; | |
1985 | do | |
1986 | { | |
1987 | page_entry *next = p->next; | |
1988 | ||
1989 | /* Loop until all entries have been examined. */ | |
1990 | done = (p == last); | |
20c1dc5e | 1991 | |
17211ab5 | 1992 | num_objects = OBJECTS_IN_PAGE (p); |
21341cfd | 1993 | |
054f5e69 ZW |
1994 | /* Add all live objects on this page to the count of |
1995 | allocated memory. */ | |
1996 | live_objects = num_objects - p->num_free_objects; | |
1997 | ||
2be510b8 | 1998 | G.allocated += OBJECT_SIZE (order) * live_objects; |
054f5e69 | 1999 | |
21341cfd AS |
2000 | /* Only objects on pages in the topmost context should get |
2001 | collected. */ | |
2002 | if (p->context_depth < G.context_depth) | |
2003 | ; | |
2004 | ||
2005 | /* Remove the page if it's empty. */ | |
054f5e69 | 2006 | else if (live_objects == 0) |
21341cfd | 2007 | { |
9bf793f9 JL |
2008 | /* If P was the first page in the list, then NEXT |
2009 | becomes the new first page in the list, otherwise | |
2010 | splice P out of the forward pointers. */ | |
21341cfd AS |
2011 | if (! previous) |
2012 | G.pages[order] = next; | |
2013 | else | |
2014 | previous->next = next; | |
b8698a0f | 2015 | |
9bf793f9 JL |
2016 | /* Splice P out of the back pointers too. */ |
2017 | if (next) | |
2018 | next->prev = previous; | |
21341cfd AS |
2019 | |
2020 | /* Are we removing the last element? */ | |
2021 | if (p == G.page_tails[order]) | |
2022 | G.page_tails[order] = previous; | |
2023 | free_page (p); | |
2024 | p = previous; | |
2025 | } | |
2026 | ||
2027 | /* If the page is full, move it to the end. */ | |
2028 | else if (p->num_free_objects == 0) | |
2029 | { | |
2030 | /* Don't move it if it's already at the end. */ | |
2031 | if (p != G.page_tails[order]) | |
2032 | { | |
2033 | /* Move p to the end of the list. */ | |
2034 | p->next = NULL; | |
9bf793f9 | 2035 | p->prev = G.page_tails[order]; |
21341cfd AS |
2036 | G.page_tails[order]->next = p; |
2037 | ||
2038 | /* Update the tail pointer... */ | |
2039 | G.page_tails[order] = p; | |
2040 | ||
2041 | /* ... and the head pointer, if necessary. */ | |
2042 | if (! previous) | |
2043 | G.pages[order] = next; | |
2044 | else | |
2045 | previous->next = next; | |
9bf793f9 JL |
2046 | |
2047 | /* And update the backpointer in NEXT if necessary. */ | |
2048 | if (next) | |
2049 | next->prev = previous; | |
2050 | ||
21341cfd AS |
2051 | p = previous; |
2052 | } | |
2053 | } | |
2054 | ||
2055 | /* If we've fallen through to here, it's a page in the | |
2056 | topmost context that is neither full nor empty. Such a | |
2057 | page must precede pages at lesser context depth in the | |
2058 | list, so move it to the head. */ | |
2059 | else if (p != G.pages[order]) | |
2060 | { | |
2061 | previous->next = p->next; | |
9bf793f9 JL |
2062 | |
2063 | /* Update the backchain in the next node if it exists. */ | |
2064 | if (p->next) | |
2065 | p->next->prev = previous; | |
2066 | ||
2067 | /* Move P to the head of the list. */ | |
21341cfd | 2068 | p->next = G.pages[order]; |
9bf793f9 JL |
2069 | p->prev = NULL; |
2070 | G.pages[order]->prev = p; | |
2071 | ||
2072 | /* Update the head pointer. */ | |
21341cfd | 2073 | G.pages[order] = p; |
9bf793f9 | 2074 | |
21341cfd AS |
2075 | /* Are we moving the last element? */ |
2076 | if (G.page_tails[order] == p) | |
2077 | G.page_tails[order] = previous; | |
2078 | p = previous; | |
2079 | } | |
2080 | ||
2081 | previous = p; | |
2082 | p = next; | |
589005ff | 2083 | } |
21341cfd | 2084 | while (! done); |
4934cc53 MM |
2085 | |
2086 | /* Now, restore the in_use_p vectors for any pages from contexts | |
2087 | other than the current one. */ | |
2088 | for (p = G.pages[order]; p; p = p->next) | |
2089 | if (p->context_depth != G.context_depth) | |
2090 | ggc_recalculate_in_use_p (p); | |
21341cfd AS |
2091 | } |
2092 | } | |
2093 | ||
3788cc17 | 2094 | #ifdef ENABLE_GC_CHECKING |
cb2ec151 RH |
2095 | /* Clobber all free objects. */ |
2096 | ||
685fe032 | 2097 | static void |
20c1dc5e | 2098 | poison_pages (void) |
21341cfd AS |
2099 | { |
2100 | unsigned order; | |
2101 | ||
2be510b8 | 2102 | for (order = 2; order < NUM_ORDERS; order++) |
21341cfd | 2103 | { |
2be510b8 | 2104 | size_t size = OBJECT_SIZE (order); |
21341cfd AS |
2105 | page_entry *p; |
2106 | ||
2107 | for (p = G.pages[order]; p != NULL; p = p->next) | |
2108 | { | |
17211ab5 | 2109 | size_t num_objects; |
21341cfd | 2110 | size_t i; |
c831fdea MM |
2111 | |
2112 | if (p->context_depth != G.context_depth) | |
2113 | /* Since we don't do any collection for pages in pushed | |
2114 | contexts, there's no need to do any poisoning. And | |
2115 | besides, the IN_USE_P array isn't valid until we pop | |
2116 | contexts. */ | |
2117 | continue; | |
2118 | ||
17211ab5 | 2119 | num_objects = OBJECTS_IN_PAGE (p); |
21341cfd AS |
2120 | for (i = 0; i < num_objects; i++) |
2121 | { | |
2122 | size_t word, bit; | |
2123 | word = i / HOST_BITS_PER_LONG; | |
2124 | bit = i % HOST_BITS_PER_LONG; | |
2125 | if (((p->in_use_p[word] >> bit) & 1) == 0) | |
9a0a7d5d HPN |
2126 | { |
2127 | char *object = p->page + i * size; | |
2128 | ||
2129 | /* Keep poison-by-write when we expect to use Valgrind, | |
2130 | so the exact same memory semantics is kept, in case | |
2131 | there are memory errors. We override this request | |
2132 | below. */ | |
35dee980 HPN |
2133 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (object, |
2134 | size)); | |
9a0a7d5d HPN |
2135 | memset (object, 0xa5, size); |
2136 | ||
2137 | /* Drop the handle to avoid handle leak. */ | |
35dee980 | 2138 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size)); |
9a0a7d5d | 2139 | } |
21341cfd AS |
2140 | } |
2141 | } | |
2142 | } | |
2143 | } | |
685fe032 RH |
2144 | #else |
2145 | #define poison_pages() | |
2146 | #endif | |
2147 | ||
2148 | #ifdef ENABLE_GC_ALWAYS_COLLECT | |
2149 | /* Validate that the reportedly free objects actually are. */ | |
2150 | ||
2151 | static void | |
2152 | validate_free_objects (void) | |
2153 | { | |
2154 | struct free_object *f, *next, *still_free = NULL; | |
2155 | ||
2156 | for (f = G.free_object_list; f ; f = next) | |
2157 | { | |
2158 | page_entry *pe = lookup_page_table_entry (f->object); | |
2159 | size_t bit, word; | |
2160 | ||
2161 | bit = OFFSET_TO_BIT ((char *)f->object - pe->page, pe->order); | |
2162 | word = bit / HOST_BITS_PER_LONG; | |
2163 | bit = bit % HOST_BITS_PER_LONG; | |
2164 | next = f->next; | |
2165 | ||
2166 | /* Make certain it isn't visible from any root. Notice that we | |
2167 | do this check before sweep_pages merges save_in_use_p. */ | |
282899df | 2168 | gcc_assert (!(pe->in_use_p[word] & (1UL << bit))); |
685fe032 RH |
2169 | |
2170 | /* If the object comes from an outer context, then retain the | |
2171 | free_object entry, so that we can verify that the address | |
2172 | isn't live on the stack in some outer context. */ | |
2173 | if (pe->context_depth != G.context_depth) | |
2174 | { | |
2175 | f->next = still_free; | |
2176 | still_free = f; | |
2177 | } | |
2178 | else | |
2179 | free (f); | |
2180 | } | |
2181 | ||
2182 | G.free_object_list = still_free; | |
2183 | } | |
2184 | #else | |
2185 | #define validate_free_objects() | |
21341cfd AS |
2186 | #endif |
2187 | ||
cb2ec151 RH |
2188 | /* Top level mark-and-sweep routine. */ |
2189 | ||
21341cfd | 2190 | void |
602fca42 | 2191 | ggc_collect (enum ggc_collect mode) |
21341cfd | 2192 | { |
21341cfd AS |
2193 | /* Avoid frequent unnecessary work by skipping collection if the |
2194 | total allocations haven't expanded much since the last | |
2195 | collection. */ | |
19cc0dd4 | 2196 | float allocated_last_gc = |
da871904 | 2197 | MAX (G.allocated_last_gc, (size_t)param_ggc_min_heapsize * ONE_K); |
3788cc17 | 2198 | |
9fd052e7 JH |
2199 | /* It is also good time to get memory block pool into limits. */ |
2200 | memory_block_pool::trim (); | |
2201 | ||
028d4092 | 2202 | float min_expand = allocated_last_gc * param_ggc_min_expand / 100; |
602fca42 TS |
2203 | if (mode == GGC_COLLECT_HEURISTIC |
2204 | && G.allocated < allocated_last_gc + min_expand) | |
21341cfd | 2205 | return; |
21341cfd | 2206 | |
2a9a326b | 2207 | timevar_push (TV_GC); |
685fe032 RH |
2208 | if (GGC_DEBUG_LEVEL >= 2) |
2209 | fprintf (G.debug_file, "BEGIN COLLECTING\n"); | |
21341cfd | 2210 | |
054f5e69 ZW |
2211 | /* Zero the total allocated bytes. This will be recalculated in the |
2212 | sweep phase. */ | |
e5207f1a | 2213 | size_t allocated = G.allocated; |
21341cfd AS |
2214 | G.allocated = 0; |
2215 | ||
589005ff | 2216 | /* Release the pages we freed the last time we collected, but didn't |
21341cfd AS |
2217 | reuse in the interim. */ |
2218 | release_pages (); | |
2219 | ||
e5207f1a JH |
2220 | /* Output this later so we do not interfere with release_pages. */ |
2221 | if (!quiet_flag) | |
79f4e20d | 2222 | fprintf (stderr, " {GC " PRsa (0) " -> ", SIZE_AMOUNT (allocated)); |
e5207f1a | 2223 | |
52895e1a RH |
2224 | /* Indicate that we've seen collections at this context depth. */ |
2225 | G.context_depth_collections = ((unsigned long)1 << (G.context_depth + 1)) - 1; | |
2226 | ||
ae2392a9 BS |
2227 | invoke_plugin_callbacks (PLUGIN_GGC_START, NULL); |
2228 | ||
b086d530 | 2229 | in_gc = true; |
21341cfd AS |
2230 | clear_marks (); |
2231 | ggc_mark_roots (); | |
de49ce19 | 2232 | ggc_handle_finalizers (); |
7aa6d18a SB |
2233 | |
2234 | if (GATHER_STATISTICS) | |
2235 | ggc_prune_overhead_list (); | |
2236 | ||
21341cfd | 2237 | poison_pages (); |
685fe032 | 2238 | validate_free_objects (); |
cb2ec151 RH |
2239 | sweep_pages (); |
2240 | ||
b086d530 | 2241 | in_gc = false; |
21341cfd AS |
2242 | G.allocated_last_gc = G.allocated; |
2243 | ||
ae2392a9 BS |
2244 | invoke_plugin_callbacks (PLUGIN_GGC_END, NULL); |
2245 | ||
2a9a326b | 2246 | timevar_pop (TV_GC); |
21341cfd | 2247 | |
21341cfd | 2248 | if (!quiet_flag) |
79f4e20d | 2249 | fprintf (stderr, PRsa (0) "}", SIZE_AMOUNT (G.allocated)); |
685fe032 RH |
2250 | if (GGC_DEBUG_LEVEL >= 2) |
2251 | fprintf (G.debug_file, "END COLLECTING\n"); | |
21341cfd | 2252 | } |
3277221c | 2253 | |
e5207f1a JH |
2254 | /* Return free pages to the system. */ |
2255 | ||
2256 | void | |
2257 | ggc_trim () | |
2258 | { | |
2259 | timevar_push (TV_GC); | |
2260 | G.allocated = 0; | |
2261 | sweep_pages (); | |
2262 | release_pages (); | |
2263 | if (!quiet_flag) | |
79f4e20d ML |
2264 | fprintf (stderr, " {GC trimmed to " PRsa (0) ", " PRsa (0) " mapped}", |
2265 | SIZE_AMOUNT (G.allocated), SIZE_AMOUNT (G.bytes_mapped)); | |
e5207f1a JH |
2266 | timevar_pop (TV_GC); |
2267 | } | |
2268 | ||
2269 | /* Assume that all GGC memory is reachable and grow the limits for next | |
2270 | collection. With checking, trigger GGC so -Q compilation outputs how much | |
2271 | of memory really is reachable. */ | |
fd1e9302 JH |
2272 | |
2273 | void | |
2274 | ggc_grow (void) | |
2275 | { | |
b2b29377 MM |
2276 | if (!flag_checking) |
2277 | G.allocated_last_gc = MAX (G.allocated_last_gc, | |
2278 | G.allocated); | |
2279 | else | |
2280 | ggc_collect (); | |
fd1e9302 | 2281 | if (!quiet_flag) |
79f4e20d | 2282 | fprintf (stderr, " {GC " PRsa (0) "} ", SIZE_AMOUNT (G.allocated)); |
fd1e9302 JH |
2283 | } |
2284 | ||
3277221c | 2285 | void |
20c1dc5e | 2286 | ggc_print_statistics (void) |
3277221c MM |
2287 | { |
2288 | struct ggc_statistics stats; | |
4934cc53 | 2289 | unsigned int i; |
fba0bfd4 | 2290 | size_t total_overhead = 0; |
3277221c MM |
2291 | |
2292 | /* Clear the statistics. */ | |
d219c7f1 | 2293 | memset (&stats, 0, sizeof (stats)); |
589005ff | 2294 | |
3277221c MM |
2295 | /* Make sure collection will really occur. */ |
2296 | G.allocated_last_gc = 0; | |
2297 | ||
2298 | /* Collect and print the statistics common across collectors. */ | |
fba0bfd4 | 2299 | ggc_print_common_statistics (stderr, &stats); |
3277221c | 2300 | |
4934cc53 MM |
2301 | /* Release free pages so that we will not count the bytes allocated |
2302 | there as part of the total allocated memory. */ | |
2303 | release_pages (); | |
2304 | ||
589005ff | 2305 | /* Collect some information about the various sizes of |
3277221c | 2306 | allocation. */ |
439a7e54 DN |
2307 | fprintf (stderr, |
2308 | "Memory still allocated at the end of the compilation process\n"); | |
b2b43e33 | 2309 | fprintf (stderr, "%-8s %10s %10s %10s\n", |
9fd51e67 | 2310 | "Size", "Allocated", "Used", "Overhead"); |
2be510b8 | 2311 | for (i = 0; i < NUM_ORDERS; ++i) |
3277221c MM |
2312 | { |
2313 | page_entry *p; | |
2314 | size_t allocated; | |
2315 | size_t in_use; | |
fba0bfd4 | 2316 | size_t overhead; |
3277221c MM |
2317 | |
2318 | /* Skip empty entries. */ | |
2319 | if (!G.pages[i]) | |
2320 | continue; | |
2321 | ||
fba0bfd4 | 2322 | overhead = allocated = in_use = 0; |
3277221c MM |
2323 | |
2324 | /* Figure out the total number of bytes allocated for objects of | |
fba0bfd4 ZW |
2325 | this size, and how many of them are actually in use. Also figure |
2326 | out how much memory the page table is using. */ | |
3277221c MM |
2327 | for (p = G.pages[i]; p; p = p->next) |
2328 | { | |
2329 | allocated += p->bytes; | |
20c1dc5e | 2330 | in_use += |
17211ab5 | 2331 | (OBJECTS_IN_PAGE (p) - p->num_free_objects) * OBJECT_SIZE (i); |
fba0bfd4 ZW |
2332 | |
2333 | overhead += (sizeof (page_entry) - sizeof (long) | |
17211ab5 | 2334 | + BITMAP_SIZE (OBJECTS_IN_PAGE (p) + 1)); |
3277221c | 2335 | } |
a0b48080 MM |
2336 | fprintf (stderr, "%-8" PRIu64 " " PRsa (10) " " PRsa (10) " " |
2337 | PRsa (10) "\n", | |
2338 | (uint64_t)OBJECT_SIZE (i), | |
40ce7fa6 ML |
2339 | SIZE_AMOUNT (allocated), |
2340 | SIZE_AMOUNT (in_use), | |
2341 | SIZE_AMOUNT (overhead)); | |
fba0bfd4 | 2342 | total_overhead += overhead; |
3277221c | 2343 | } |
a0b48080 | 2344 | fprintf (stderr, "%-8s " PRsa (10) " " PRsa (10) " " PRsa (10) "\n", |
40ce7fa6 ML |
2345 | "Total", |
2346 | SIZE_AMOUNT (G.bytes_mapped), | |
2347 | SIZE_AMOUNT (G.allocated), | |
2348 | SIZE_AMOUNT (total_overhead)); | |
adc4adcd | 2349 | |
7aa6d18a SB |
2350 | if (GATHER_STATISTICS) |
2351 | { | |
b2b43e33 ML |
2352 | fprintf (stderr, "\nTotal allocations and overheads during " |
2353 | "the compilation process\n"); | |
7aa6d18a | 2354 | |
a0b48080 MM |
2355 | fprintf (stderr, "Total Overhead: " |
2356 | PRsa (9) "\n", | |
40ce7fa6 | 2357 | SIZE_AMOUNT (G.stats.total_overhead)); |
a0b48080 MM |
2358 | fprintf (stderr, "Total Allocated: " |
2359 | PRsa (9) "\n", | |
40ce7fa6 ML |
2360 | SIZE_AMOUNT (G.stats.total_allocated)); |
2361 | ||
a0b48080 MM |
2362 | fprintf (stderr, "Total Overhead under 32B: " |
2363 | PRsa (9) "\n", | |
40ce7fa6 | 2364 | SIZE_AMOUNT (G.stats.total_overhead_under32)); |
a0b48080 MM |
2365 | fprintf (stderr, "Total Allocated under 32B: " |
2366 | PRsa (9) "\n", | |
40ce7fa6 | 2367 | SIZE_AMOUNT (G.stats.total_allocated_under32)); |
a0b48080 MM |
2368 | fprintf (stderr, "Total Overhead under 64B: " |
2369 | PRsa (9) "\n", | |
40ce7fa6 | 2370 | SIZE_AMOUNT (G.stats.total_overhead_under64)); |
a0b48080 MM |
2371 | fprintf (stderr, "Total Allocated under 64B: " |
2372 | PRsa (9) "\n", | |
40ce7fa6 | 2373 | SIZE_AMOUNT (G.stats.total_allocated_under64)); |
a0b48080 MM |
2374 | fprintf (stderr, "Total Overhead under 128B: " |
2375 | PRsa (9) "\n", | |
40ce7fa6 | 2376 | SIZE_AMOUNT (G.stats.total_overhead_under128)); |
a0b48080 MM |
2377 | fprintf (stderr, "Total Allocated under 128B: " |
2378 | PRsa (9) "\n", | |
40ce7fa6 | 2379 | SIZE_AMOUNT (G.stats.total_allocated_under128)); |
7aa6d18a SB |
2380 | |
2381 | for (i = 0; i < NUM_ORDERS; i++) | |
2382 | if (G.stats.total_allocated_per_order[i]) | |
2383 | { | |
a0b48080 MM |
2384 | fprintf (stderr, "Total Overhead page size %9" PRIu64 ": " |
2385 | PRsa (9) "\n", | |
2386 | (uint64_t)OBJECT_SIZE (i), | |
40ce7fa6 | 2387 | SIZE_AMOUNT (G.stats.total_overhead_per_order[i])); |
a0b48080 MM |
2388 | fprintf (stderr, "Total Allocated page size %9" PRIu64 ": " |
2389 | PRsa (9) "\n", | |
2390 | (uint64_t)OBJECT_SIZE (i), | |
40ce7fa6 | 2391 | SIZE_AMOUNT (G.stats.total_allocated_per_order[i])); |
7aa6d18a | 2392 | } |
adc4adcd | 2393 | } |
3277221c | 2394 | } |
17211ab5 | 2395 | \f |
24b97832 ILT |
2396 | struct ggc_pch_ondisk |
2397 | { | |
2398 | unsigned totals[NUM_ORDERS]; | |
2399 | }; | |
2400 | ||
17211ab5 GK |
2401 | struct ggc_pch_data |
2402 | { | |
24b97832 | 2403 | struct ggc_pch_ondisk d; |
2a6e6fea | 2404 | uintptr_t base[NUM_ORDERS]; |
17211ab5 GK |
2405 | size_t written[NUM_ORDERS]; |
2406 | }; | |
2407 | ||
2408 | struct ggc_pch_data * | |
20c1dc5e | 2409 | init_ggc_pch (void) |
17211ab5 | 2410 | { |
5ed6ace5 | 2411 | return XCNEW (struct ggc_pch_data); |
17211ab5 GK |
2412 | } |
2413 | ||
20c1dc5e AJ |
2414 | void |
2415 | ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED, | |
bbbe2dc1 | 2416 | size_t size) |
17211ab5 GK |
2417 | { |
2418 | unsigned order; | |
2419 | ||
6583cf15 | 2420 | if (size < NUM_SIZE_LOOKUP) |
17211ab5 GK |
2421 | order = size_lookup[size]; |
2422 | else | |
2423 | { | |
f5938dcd | 2424 | order = 10; |
17211ab5 GK |
2425 | while (size > OBJECT_SIZE (order)) |
2426 | order++; | |
2427 | } | |
20c1dc5e | 2428 | |
17211ab5 GK |
2429 | d->d.totals[order]++; |
2430 | } | |
20c1dc5e | 2431 | |
17211ab5 | 2432 | size_t |
20c1dc5e | 2433 | ggc_pch_total_size (struct ggc_pch_data *d) |
17211ab5 GK |
2434 | { |
2435 | size_t a = 0; | |
2436 | unsigned i; | |
2437 | ||
2438 | for (i = 0; i < NUM_ORDERS; i++) | |
3bc50163 | 2439 | a += PAGE_ALIGN (d->d.totals[i] * OBJECT_SIZE (i)); |
17211ab5 GK |
2440 | return a; |
2441 | } | |
2442 | ||
2443 | void | |
20c1dc5e | 2444 | ggc_pch_this_base (struct ggc_pch_data *d, void *base) |
17211ab5 | 2445 | { |
2a6e6fea | 2446 | uintptr_t a = (uintptr_t) base; |
17211ab5 | 2447 | unsigned i; |
20c1dc5e | 2448 | |
17211ab5 GK |
2449 | for (i = 0; i < NUM_ORDERS; i++) |
2450 | { | |
2451 | d->base[i] = a; | |
3bc50163 | 2452 | a += PAGE_ALIGN (d->d.totals[i] * OBJECT_SIZE (i)); |
17211ab5 GK |
2453 | } |
2454 | } | |
2455 | ||
2456 | ||
2457 | char * | |
20c1dc5e | 2458 | ggc_pch_alloc_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED, |
bbbe2dc1 | 2459 | size_t size) |
17211ab5 GK |
2460 | { |
2461 | unsigned order; | |
2462 | char *result; | |
20c1dc5e | 2463 | |
6583cf15 | 2464 | if (size < NUM_SIZE_LOOKUP) |
17211ab5 GK |
2465 | order = size_lookup[size]; |
2466 | else | |
2467 | { | |
f5938dcd | 2468 | order = 10; |
17211ab5 GK |
2469 | while (size > OBJECT_SIZE (order)) |
2470 | order++; | |
2471 | } | |
2472 | ||
2473 | result = (char *) d->base[order]; | |
2474 | d->base[order] += OBJECT_SIZE (order); | |
2475 | return result; | |
2476 | } | |
2477 | ||
20c1dc5e AJ |
2478 | void |
2479 | ggc_pch_prepare_write (struct ggc_pch_data *d ATTRIBUTE_UNUSED, | |
2480 | FILE *f ATTRIBUTE_UNUSED) | |
17211ab5 GK |
2481 | { |
2482 | /* Nothing to do. */ | |
2483 | } | |
2484 | ||
2485 | void | |
8ed00d76 | 2486 | ggc_pch_write_object (struct ggc_pch_data *d, |
20c1dc5e | 2487 | FILE *f, void *x, void *newx ATTRIBUTE_UNUSED, |
bbbe2dc1 | 2488 | size_t size) |
17211ab5 GK |
2489 | { |
2490 | unsigned order; | |
642324bb | 2491 | static const char emptyBytes[256] = { 0 }; |
17211ab5 | 2492 | |
6583cf15 | 2493 | if (size < NUM_SIZE_LOOKUP) |
17211ab5 GK |
2494 | order = size_lookup[size]; |
2495 | else | |
2496 | { | |
f5938dcd | 2497 | order = 10; |
17211ab5 GK |
2498 | while (size > OBJECT_SIZE (order)) |
2499 | order++; | |
2500 | } | |
20c1dc5e | 2501 | |
17211ab5 | 2502 | if (fwrite (x, size, 1, f) != 1) |
a9c697b8 | 2503 | fatal_error (input_location, "cannot write PCH file: %m"); |
17211ab5 | 2504 | |
674c7ef1 | 2505 | /* If SIZE is not the same as OBJECT_SIZE(order), then we need to pad the |
0ee55ad8 | 2506 | object out to OBJECT_SIZE(order). This happens for strings. */ |
674c7ef1 RB |
2507 | |
2508 | if (size != OBJECT_SIZE (order)) | |
2509 | { | |
c3284718 | 2510 | unsigned padding = OBJECT_SIZE (order) - size; |
674c7ef1 RB |
2511 | |
2512 | /* To speed small writes, we use a nulled-out array that's larger | |
2513 | than most padding requests as the source for our null bytes. This | |
2514 | permits us to do the padding with fwrite() rather than fseek(), and | |
3f117656 | 2515 | limits the chance the OS may try to flush any outstanding writes. */ |
c3284718 | 2516 | if (padding <= sizeof (emptyBytes)) |
674c7ef1 RB |
2517 | { |
2518 | if (fwrite (emptyBytes, 1, padding, f) != padding) | |
a9c697b8 | 2519 | fatal_error (input_location, "cannot write PCH file"); |
674c7ef1 RB |
2520 | } |
2521 | else | |
2522 | { | |
0ee55ad8 | 2523 | /* Larger than our buffer? Just default to fseek. */ |
674c7ef1 | 2524 | if (fseek (f, padding, SEEK_CUR) != 0) |
a9c697b8 | 2525 | fatal_error (input_location, "cannot write PCH file"); |
674c7ef1 RB |
2526 | } |
2527 | } | |
17211ab5 GK |
2528 | |
2529 | d->written[order]++; | |
2530 | if (d->written[order] == d->d.totals[order] | |
2531 | && fseek (f, ROUND_UP_VALUE (d->d.totals[order] * OBJECT_SIZE (order), | |
2532 | G.pagesize), | |
2533 | SEEK_CUR) != 0) | |
a9c697b8 | 2534 | fatal_error (input_location, "cannot write PCH file: %m"); |
17211ab5 GK |
2535 | } |
2536 | ||
2537 | void | |
20c1dc5e | 2538 | ggc_pch_finish (struct ggc_pch_data *d, FILE *f) |
17211ab5 GK |
2539 | { |
2540 | if (fwrite (&d->d, sizeof (d->d), 1, f) != 1) | |
a9c697b8 | 2541 | fatal_error (input_location, "cannot write PCH file: %m"); |
17211ab5 GK |
2542 | free (d); |
2543 | } | |
2544 | ||
c4775f82 MS |
2545 | /* Move the PCH PTE entries just added to the end of by_depth, to the |
2546 | front. */ | |
2547 | ||
2548 | static void | |
20c1dc5e | 2549 | move_ptes_to_front (int count_old_page_tables, int count_new_page_tables) |
c4775f82 | 2550 | { |
c4775f82 MS |
2551 | /* First, we swap the new entries to the front of the varrays. */ |
2552 | page_entry **new_by_depth; | |
2553 | unsigned long **new_save_in_use; | |
2554 | ||
5ed6ace5 MD |
2555 | new_by_depth = XNEWVEC (page_entry *, G.by_depth_max); |
2556 | new_save_in_use = XNEWVEC (unsigned long *, G.by_depth_max); | |
c4775f82 MS |
2557 | |
2558 | memcpy (&new_by_depth[0], | |
2559 | &G.by_depth[count_old_page_tables], | |
2560 | count_new_page_tables * sizeof (void *)); | |
2561 | memcpy (&new_by_depth[count_new_page_tables], | |
2562 | &G.by_depth[0], | |
2563 | count_old_page_tables * sizeof (void *)); | |
2564 | memcpy (&new_save_in_use[0], | |
2565 | &G.save_in_use[count_old_page_tables], | |
2566 | count_new_page_tables * sizeof (void *)); | |
2567 | memcpy (&new_save_in_use[count_new_page_tables], | |
2568 | &G.save_in_use[0], | |
2569 | count_old_page_tables * sizeof (void *)); | |
2570 | ||
2571 | free (G.by_depth); | |
2572 | free (G.save_in_use); | |
20c1dc5e | 2573 | |
c4775f82 MS |
2574 | G.by_depth = new_by_depth; |
2575 | G.save_in_use = new_save_in_use; | |
2576 | ||
2577 | /* Now update all the index_by_depth fields. */ | |
3608eff9 | 2578 | for (unsigned i = G.by_depth_in_use; i--;) |
c4775f82 | 2579 | { |
3608eff9 NS |
2580 | page_entry *p = G.by_depth[i]; |
2581 | p->index_by_depth = i; | |
c4775f82 MS |
2582 | } |
2583 | ||
2584 | /* And last, we update the depth pointers in G.depth. The first | |
2585 | entry is already 0, and context 0 entries always start at index | |
2586 | 0, so there is nothing to update in the first slot. We need a | |
2587 | second slot, only if we have old ptes, and if we do, they start | |
2588 | at index count_new_page_tables. */ | |
2589 | if (count_old_page_tables) | |
2590 | push_depth (count_new_page_tables); | |
2591 | } | |
2592 | ||
17211ab5 | 2593 | void |
20c1dc5e | 2594 | ggc_pch_read (FILE *f, void *addr) |
17211ab5 GK |
2595 | { |
2596 | struct ggc_pch_ondisk d; | |
2597 | unsigned i; | |
d3bfe4de | 2598 | char *offs = (char *) addr; |
c4775f82 MS |
2599 | unsigned long count_old_page_tables; |
2600 | unsigned long count_new_page_tables; | |
2601 | ||
2602 | count_old_page_tables = G.by_depth_in_use; | |
2603 | ||
22f8849d IS |
2604 | if (fread (&d, sizeof (d), 1, f) != 1) |
2605 | fatal_error (input_location, "cannot read PCH file: %m"); | |
2606 | ||
c4775f82 MS |
2607 | /* We've just read in a PCH file. So, every object that used to be |
2608 | allocated is now free. */ | |
17211ab5 | 2609 | clear_marks (); |
c5d6d04a | 2610 | #ifdef ENABLE_GC_CHECKING |
17211ab5 GK |
2611 | poison_pages (); |
2612 | #endif | |
ead8827d LB |
2613 | /* Since we free all the allocated objects, the free list becomes |
2614 | useless. Validate it now, which will also clear it. */ | |
c3284718 | 2615 | validate_free_objects (); |
17211ab5 GK |
2616 | |
2617 | /* No object read from a PCH file should ever be freed. So, set the | |
2618 | context depth to 1, and set the depth of all the currently-allocated | |
2619 | pages to be 1 too. PCH pages will have depth 0. */ | |
282899df | 2620 | gcc_assert (!G.context_depth); |
17211ab5 | 2621 | G.context_depth = 1; |
2a304777 JM |
2622 | /* Allocate space for the depth 1 finalizers. */ |
2623 | G.finalizers.safe_push (vNULL); | |
2624 | G.vec_finalizers.safe_push (vNULL); | |
2625 | gcc_assert (G.finalizers.length() == 2); | |
17211ab5 GK |
2626 | for (i = 0; i < NUM_ORDERS; i++) |
2627 | { | |
2628 | page_entry *p; | |
2629 | for (p = G.pages[i]; p != NULL; p = p->next) | |
2630 | p->context_depth = G.context_depth; | |
2631 | } | |
2632 | ||
2633 | /* Allocate the appropriate page-table entries for the pages read from | |
2634 | the PCH file. */ | |
20c1dc5e | 2635 | |
17211ab5 GK |
2636 | for (i = 0; i < NUM_ORDERS; i++) |
2637 | { | |
2638 | struct page_entry *entry; | |
2639 | char *pte; | |
2640 | size_t bytes; | |
2641 | size_t num_objs; | |
2642 | size_t j; | |
c4775f82 | 2643 | |
17211ab5 GK |
2644 | if (d.totals[i] == 0) |
2645 | continue; | |
c4775f82 | 2646 | |
3bc50163 | 2647 | bytes = PAGE_ALIGN (d.totals[i] * OBJECT_SIZE (i)); |
17211ab5 | 2648 | num_objs = bytes / OBJECT_SIZE (i); |
d3bfe4de KG |
2649 | entry = XCNEWVAR (struct page_entry, (sizeof (struct page_entry) |
2650 | - sizeof (long) | |
2651 | + BITMAP_SIZE (num_objs + 1))); | |
17211ab5 GK |
2652 | entry->bytes = bytes; |
2653 | entry->page = offs; | |
2654 | entry->context_depth = 0; | |
2655 | offs += bytes; | |
2656 | entry->num_free_objects = 0; | |
2657 | entry->order = i; | |
2658 | ||
20c1dc5e | 2659 | for (j = 0; |
17211ab5 GK |
2660 | j + HOST_BITS_PER_LONG <= num_objs + 1; |
2661 | j += HOST_BITS_PER_LONG) | |
2662 | entry->in_use_p[j / HOST_BITS_PER_LONG] = -1; | |
2663 | for (; j < num_objs + 1; j++) | |
20c1dc5e | 2664 | entry->in_use_p[j / HOST_BITS_PER_LONG] |
17211ab5 GK |
2665 | |= 1L << (j % HOST_BITS_PER_LONG); |
2666 | ||
20c1dc5e AJ |
2667 | for (pte = entry->page; |
2668 | pte < entry->page + entry->bytes; | |
17211ab5 GK |
2669 | pte += G.pagesize) |
2670 | set_page_table_entry (pte, entry); | |
2671 | ||
2672 | if (G.page_tails[i] != NULL) | |
2673 | G.page_tails[i]->next = entry; | |
2674 | else | |
2675 | G.pages[i] = entry; | |
2676 | G.page_tails[i] = entry; | |
c4775f82 MS |
2677 | |
2678 | /* We start off by just adding all the new information to the | |
2679 | end of the varrays, later, we will move the new information | |
2680 | to the front of the varrays, as the PCH page tables are at | |
2681 | context 0. */ | |
2682 | push_by_depth (entry, 0); | |
17211ab5 GK |
2683 | } |
2684 | ||
c4775f82 MS |
2685 | /* Now, we update the various data structures that speed page table |
2686 | handling. */ | |
2687 | count_new_page_tables = G.by_depth_in_use - count_old_page_tables; | |
2688 | ||
2689 | move_ptes_to_front (count_old_page_tables, count_new_page_tables); | |
2690 | ||
17211ab5 GK |
2691 | /* Update the statistics. */ |
2692 | G.allocated = G.allocated_last_gc = offs - (char *)addr; | |
2693 | } |