OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [ggc-zone.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* "Bag-of-pages" zone garbage collector for the GNU compiler.
2
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
3
   Free Software Foundation, Inc.
4
 
5
   Contributed by Richard Henderson (rth@redhat.com) and Daniel Berlin
6
   (dberlin@dberlin.org).  Rewritten by Daniel Jacobowitz
7
   <dan@codesourcery.com>.
8
 
9
This file is part of GCC.
10
 
11
GCC is free software; you can redistribute it and/or modify it under
12
the terms of the GNU General Public License as published by the Free
13
Software Foundation; either version 3, or (at your option) any later
14
version.
15
 
16
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17
WARRANTY; without even the implied warranty of MERCHANTABILITY or
18
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
19
for more details.
20
 
21
You should have received a copy of the GNU General Public License
22
along with GCC; see the file COPYING3.  If not see
23
<http://www.gnu.org/licenses/>.  */
24
 
25
#include "config.h"
26
#include "system.h"
27
#include "coretypes.h"
28
#include "tm.h"
29
#include "tree.h"
30
#include "rtl.h"
31
#include "tm_p.h"
32
#include "toplev.h"
33
#include "varray.h"
34
#include "flags.h"
35
#include "ggc.h"
36
#include "timevar.h"
37
#include "params.h"
38
#include "bitmap.h"
39
#include "plugin.h"
40
 
41
/* Prefer MAP_ANON(YMOUS) to /dev/zero, since we don't need to keep a
42
   file open.  Prefer either to valloc.  */
43
#ifdef HAVE_MMAP_ANON
44
# undef HAVE_MMAP_DEV_ZERO
45
 
46
# include <sys/mman.h>
47
# ifndef MAP_FAILED
48
#  define MAP_FAILED -1
49
# endif
50
# if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
51
#  define MAP_ANONYMOUS MAP_ANON
52
# endif
53
# define USING_MMAP
54
#endif
55
 
56
#ifdef HAVE_MMAP_DEV_ZERO
57
# include <sys/mman.h>
58
# ifndef MAP_FAILED
59
#  define MAP_FAILED -1
60
# endif
61
# define USING_MMAP
62
#endif
63
 
64
#ifndef USING_MMAP
65
#error Zone collector requires mmap
66
#endif
67
 
68
#if (GCC_VERSION < 3001)
69
#define prefetch(X) ((void) X)
70
#define prefetchw(X) ((void) X)
71
#else
72
#define prefetch(X) __builtin_prefetch (X)
73
#define prefetchw(X) __builtin_prefetch (X, 1, 3)
74
#endif
75
 
76
/* FUTURE NOTES:
77
 
78
   If we track inter-zone pointers, we can mark single zones at a
79
   time.
80
 
81
   If we have a zone where we guarantee no inter-zone pointers, we
82
   could mark that zone separately.
83
 
84
   The garbage zone should not be marked, and we should return 1 in
85
   ggc_set_mark for any object in the garbage zone, which cuts off
86
   marking quickly.  */
87
 
88
/* Strategy:
89
 
90
   This garbage-collecting allocator segregates objects into zones.
91
   It also segregates objects into "large" and "small" bins.  Large
92
   objects are greater than page size.
93
 
94
   Pages for small objects are broken up into chunks.  The page has
95
   a bitmap which marks the start position of each chunk (whether
96
   allocated or free).  Free chunks are on one of the zone's free
97
   lists and contain a pointer to the next free chunk.  Chunks in
98
   most of the free lists have a fixed size determined by the
99
   free list.  Chunks in the "other" sized free list have their size
100
   stored right after their chain pointer.
101
 
102
   Empty pages (of all sizes) are kept on a single page cache list,
103
   and are considered first when new pages are required; they are
104
   deallocated at the start of the next collection if they haven't
105
   been recycled by then.  The free page list is currently per-zone.  */
106
 
107
/* Define GGC_DEBUG_LEVEL to print debugging information.
108
     0: No debugging output.
109
     1: GC statistics only.
110
     2: Page-entry allocations/deallocations as well.
111
     3: Object allocations as well.
112
     4: Object marks as well.  */
113
#define GGC_DEBUG_LEVEL (0)
114
 
115
#ifndef HOST_BITS_PER_PTR
116
#define HOST_BITS_PER_PTR  HOST_BITS_PER_LONG
117
#endif
118
 
119
/* This structure manages small free chunks.  The SIZE field is only
120
   initialized if the chunk is in the "other" sized free list.  Large
121
   chunks are allocated one at a time to their own page, and so don't
122
   come in here.  */
123
 
124
struct alloc_chunk {
125
  struct alloc_chunk *next_free;
126
  unsigned int size;
127
};
128
 
129
/* The size of the fixed-size portion of a small page descriptor.  */
130
#define PAGE_OVERHEAD   (offsetof (struct small_page_entry, alloc_bits))
131
 
132
/* The collector's idea of the page size.  This must be a power of two
133
   no larger than the system page size, because pages must be aligned
134
   to this amount and are tracked at this granularity in the page
135
   table.  We choose a size at compile time for efficiency.
136
 
137
   We could make a better guess at compile time if PAGE_SIZE is a
138
   constant in system headers, and PAGE_SHIFT is defined...  */
139
#define GGC_PAGE_SIZE   4096
140
#define GGC_PAGE_MASK   (GGC_PAGE_SIZE - 1)
141
#define GGC_PAGE_SHIFT  12
142
 
143
#if 0
144
/* Alternative definitions which use the runtime page size.  */
145
#define GGC_PAGE_SIZE   G.pagesize
146
#define GGC_PAGE_MASK   G.page_mask
147
#define GGC_PAGE_SHIFT  G.lg_pagesize
148
#endif
149
 
150
/* The size of a small page managed by the garbage collector.  This
151
   must currently be GGC_PAGE_SIZE, but with a few changes could
152
   be any multiple of it to reduce certain kinds of overhead.  */
153
#define SMALL_PAGE_SIZE GGC_PAGE_SIZE
154
 
155
/* Free bin information.  These numbers may be in need of re-tuning.
156
   In general, decreasing the number of free bins would seem to
157
   increase the time it takes to allocate... */
158
 
159
/* FIXME: We can't use anything but MAX_ALIGNMENT for the bin size
160
   today.  */
161
 
162
#define NUM_FREE_BINS           64
163
#define FREE_BIN_DELTA          MAX_ALIGNMENT
164
#define SIZE_BIN_DOWN(SIZE)     ((SIZE) / FREE_BIN_DELTA)
165
 
166
/* Allocation and marking parameters.  */
167
 
168
/* The smallest allocatable unit to keep track of.  */
169
#define BYTES_PER_ALLOC_BIT     MAX_ALIGNMENT
170
 
171
/* The smallest markable unit.  If we require each allocated object
172
   to contain at least two allocatable units, we can use half as many
173
   bits for the mark bitmap.  But this adds considerable complexity
174
   to sweeping.  */
175
#define BYTES_PER_MARK_BIT      BYTES_PER_ALLOC_BIT
176
 
177
#define BYTES_PER_MARK_WORD     (8 * BYTES_PER_MARK_BIT * sizeof (mark_type))
178
 
179
/* We use this structure to determine the alignment required for
180
   allocations.
181
 
182
   There are several things wrong with this estimation of alignment.
183
 
184
   The maximum alignment for a structure is often less than the
185
   maximum alignment for a basic data type; for instance, on some
186
   targets long long must be aligned to sizeof (int) in a structure
187
   and sizeof (long long) in a variable.  i386-linux is one example;
188
   Darwin is another (sometimes, depending on the compiler in use).
189
 
190
   Also, long double is not included.  Nothing in GCC uses long
191
   double, so we assume that this is OK.  On powerpc-darwin, adding
192
   long double would bring the maximum alignment up to 16 bytes,
193
   and until we need long double (or to vectorize compiler operations)
194
   that's painfully wasteful.  This will need to change, some day.  */
195
 
196
struct max_alignment {
197
  char c;
198
  union {
199
    HOST_WIDEST_INT i;
200
    double d;
201
  } u;
202
};
203
 
204
/* The biggest alignment required.  */
205
 
206
#define MAX_ALIGNMENT (offsetof (struct max_alignment, u))
207
 
208
/* Compute the smallest multiple of F that is >= X.  */
209
 
210
#define ROUND_UP(x, f) (CEIL (x, f) * (f))
211
 
212
/* Types to use for the allocation and mark bitmaps.  It might be
213
   a good idea to add ffsl to libiberty and use unsigned long
214
   instead; that could speed us up where long is wider than int.  */
215
 
216
typedef unsigned int alloc_type;
217
typedef unsigned int mark_type;
218
#define alloc_ffs(x) ffs(x)
219
 
220
/* A page_entry records the status of an allocation page.  This is the
221
   common data between all three kinds of pages - small, large, and
222
   PCH.  */
223
typedef struct page_entry
224
{
225
  /* The address at which the memory is allocated.  */
226
  char *page;
227
 
228
  /* The zone that this page entry belongs to.  */
229
  struct alloc_zone *zone;
230
 
231
#ifdef GATHER_STATISTICS
232
  /* How many collections we've survived.  */
233
  size_t survived;
234
#endif
235
 
236
  /* Does this page contain small objects, or one large object?  */
237
  bool large_p;
238
 
239
  /* Is this page part of the loaded PCH?  */
240
  bool pch_p;
241
} page_entry;
242
 
243
/* Additional data needed for small pages.  */
244
struct small_page_entry
245
{
246
  struct page_entry common;
247
 
248
  /* The next small page entry, or NULL if this is the last.  */
249
  struct small_page_entry *next;
250
 
251
  /* If currently marking this zone, a pointer to the mark bits
252
     for this page.  If we aren't currently marking this zone,
253
     this pointer may be stale (pointing to freed memory).  */
254
  mark_type *mark_bits;
255
 
256
  /* The allocation bitmap.  This array extends far enough to have
257
     one bit for every BYTES_PER_ALLOC_BIT bytes in the page.  */
258
  alloc_type alloc_bits[1];
259
};
260
 
261
/* Additional data needed for large pages.  */
262
struct large_page_entry
263
{
264
  struct page_entry common;
265
 
266
  /* The next large page entry, or NULL if this is the last.  */
267
  struct large_page_entry *next;
268
 
269
  /* The number of bytes allocated, not including the page entry.  */
270
  size_t bytes;
271
 
272
  /* The previous page in the list, so that we can unlink this one.  */
273
  struct large_page_entry *prev;
274
 
275
  /* During marking, is this object marked?  */
276
  bool mark_p;
277
};
278
 
279
/* A two-level tree is used to look up the page-entry for a given
280
   pointer.  Two chunks of the pointer's bits are extracted to index
281
   the first and second levels of the tree, as follows:
282
 
283
                                   HOST_PAGE_SIZE_BITS
284
                           32           |      |
285
       msb +----------------+----+------+------+ lsb
286
                            |    |      |
287
                         PAGE_L1_BITS   |
288
                                 |      |
289
                               PAGE_L2_BITS
290
 
291
   The bottommost HOST_PAGE_SIZE_BITS are ignored, since page-entry
292
   pages are aligned on system page boundaries.  The next most
293
   significant PAGE_L2_BITS and PAGE_L1_BITS are the second and first
294
   index values in the lookup table, respectively.
295
 
296
   For 32-bit architectures and the settings below, there are no
297
   leftover bits.  For architectures with wider pointers, the lookup
298
   tree points to a list of pages, which must be scanned to find the
299
   correct one.  */
300
 
301
#define PAGE_L1_BITS    (8)
302
#define PAGE_L2_BITS    (32 - PAGE_L1_BITS - GGC_PAGE_SHIFT)
303
#define PAGE_L1_SIZE    ((size_t) 1 << PAGE_L1_BITS)
304
#define PAGE_L2_SIZE    ((size_t) 1 << PAGE_L2_BITS)
305
 
306
#define LOOKUP_L1(p) \
307
  (((size_t) (p) >> (32 - PAGE_L1_BITS)) & ((1 << PAGE_L1_BITS) - 1))
308
 
309
#define LOOKUP_L2(p) \
310
  (((size_t) (p) >> GGC_PAGE_SHIFT) & ((1 << PAGE_L2_BITS) - 1))
311
 
312
#if HOST_BITS_PER_PTR <= 32
313
 
314
/* On 32-bit hosts, we use a two level page table, as pictured above.  */
315
typedef page_entry **page_table[PAGE_L1_SIZE];
316
 
317
#else
318
 
319
/* On 64-bit hosts, we use the same two level page tables plus a linked
320
   list that disambiguates the top 32-bits.  There will almost always be
321
   exactly one entry in the list.  */
322
typedef struct page_table_chain
323
{
324
  struct page_table_chain *next;
325
  size_t high_bits;
326
  page_entry **table[PAGE_L1_SIZE];
327
} *page_table;
328
 
329
#endif
330
 
331
/* The global variables.  */
332
static struct globals
333
{
334
  /* The linked list of zones.  */
335
  struct alloc_zone *zones;
336
 
337
  /* Lookup table for associating allocation pages with object addresses.  */
338
  page_table lookup;
339
 
340
  /* The system's page size, and related constants.  */
341
  size_t pagesize;
342
  size_t lg_pagesize;
343
  size_t page_mask;
344
 
345
  /* The size to allocate for a small page entry.  This includes
346
     the size of the structure and the size of the allocation
347
     bitmap.  */
348
  size_t small_page_overhead;
349
 
350
#if defined (HAVE_MMAP_DEV_ZERO)
351
  /* A file descriptor open to /dev/zero for reading.  */
352
  int dev_zero_fd;
353
#endif
354
 
355
  /* Allocate pages in chunks of this size, to throttle calls to memory
356
     allocation routines.  The first page is used, the rest go onto the
357
     free list.  */
358
  size_t quire_size;
359
 
360
  /* The file descriptor for debugging output.  */
361
  FILE *debug_file;
362
} G;
363
 
364
/* A zone allocation structure.  There is one of these for every
365
   distinct allocation zone.  */
366
struct alloc_zone
367
{
368
  /* The most recent free chunk is saved here, instead of in the linked
369
     free list, to decrease list manipulation.  It is most likely that we
370
     will want this one.  */
371
  char *cached_free;
372
  size_t cached_free_size;
373
 
374
  /* Linked lists of free storage.  Slots 1 ... NUM_FREE_BINS have chunks of size
375
     FREE_BIN_DELTA.  All other chunks are in slot 0.  */
376
  struct alloc_chunk *free_chunks[NUM_FREE_BINS + 1];
377
 
378
  /* The highest bin index which might be non-empty.  It may turn out
379
     to be empty, in which case we have to search downwards.  */
380
  size_t high_free_bin;
381
 
382
  /* Bytes currently allocated in this zone.  */
383
  size_t allocated;
384
 
385
  /* Linked list of the small pages in this zone.  */
386
  struct small_page_entry *pages;
387
 
388
  /* Doubly linked list of large pages in this zone.  */
389
  struct large_page_entry *large_pages;
390
 
391
  /* If we are currently marking this zone, a pointer to the mark bits.  */
392
  mark_type *mark_bits;
393
 
394
  /* Name of the zone.  */
395
  const char *name;
396
 
397
  /* The number of small pages currently allocated in this zone.  */
398
  size_t n_small_pages;
399
 
400
  /* Bytes allocated at the end of the last collection.  */
401
  size_t allocated_last_gc;
402
 
403
  /* Total amount of memory mapped.  */
404
  size_t bytes_mapped;
405
 
406
  /* A cache of free system pages.  */
407
  struct small_page_entry *free_pages;
408
 
409
  /* Next zone in the linked list of zones.  */
410
  struct alloc_zone *next_zone;
411
 
412
  /* True if this zone was collected during this collection.  */
413
  bool was_collected;
414
 
415
  /* True if this zone should be destroyed after the next collection.  */
416
  bool dead;
417
 
418
#ifdef GATHER_STATISTICS
419
  struct
420
  {
421
    /* Total memory allocated with ggc_alloc.  */
422
    unsigned long long total_allocated;
423
    /* Total overhead for memory to be allocated with ggc_alloc.  */
424
    unsigned long long total_overhead;
425
 
426
    /* Total allocations and overhead for sizes less than 32, 64 and 128.
427
       These sizes are interesting because they are typical cache line
428
       sizes.  */
429
 
430
    unsigned long long total_allocated_under32;
431
    unsigned long long total_overhead_under32;
432
 
433
    unsigned long long total_allocated_under64;
434
    unsigned long long total_overhead_under64;
435
 
436
    unsigned long long total_allocated_under128;
437
    unsigned long long total_overhead_under128;
438
  } stats;
439
#endif
440
} main_zone;
441
 
442
/* Some default zones.  */
443
struct alloc_zone rtl_zone;
444
struct alloc_zone tree_zone;
445
struct alloc_zone tree_id_zone;
446
 
447
/* The PCH zone does not need a normal zone structure, and it does
448
   not live on the linked list of zones.  */
449
struct pch_zone
450
{
451
  /* The start of the PCH zone.  NULL if there is none.  */
452
  char *page;
453
 
454
  /* The end of the PCH zone.  NULL if there is none.  */
455
  char *end;
456
 
457
  /* The size of the PCH zone.  0 if there is none.  */
458
  size_t bytes;
459
 
460
  /* The allocation bitmap for the PCH zone.  */
461
  alloc_type *alloc_bits;
462
 
463
  /* If we are currently marking, the mark bitmap for the PCH zone.
464
     When it is first read in, we could avoid marking the PCH,
465
     because it will not contain any pointers to GC memory outside
466
     of the PCH; however, the PCH is currently mapped as writable,
467
     so we must mark it in case new pointers are added.  */
468
  mark_type *mark_bits;
469
} pch_zone;
470
 
471
#ifdef USING_MMAP
472
static char *alloc_anon (char *, size_t, struct alloc_zone *);
473
#endif
474
static struct small_page_entry * alloc_small_page (struct alloc_zone *);
475
static struct large_page_entry * alloc_large_page (size_t, struct alloc_zone *);
476
static void free_chunk (char *, size_t, struct alloc_zone *);
477
static void free_small_page (struct small_page_entry *);
478
static void free_large_page (struct large_page_entry *);
479
static void release_pages (struct alloc_zone *);
480
static void sweep_pages (struct alloc_zone *);
481
static bool ggc_collect_1 (struct alloc_zone *, bool);
482
static void new_ggc_zone_1 (struct alloc_zone *, const char *);
483
 
484
/* Traverse the page table and find the entry for a page.
485
   Die (probably) if the object wasn't allocated via GC.  */
486
 
487
static inline page_entry *
488
lookup_page_table_entry (const void *p)
489
{
490
  page_entry ***base;
491
  size_t L1, L2;
492
 
493
#if HOST_BITS_PER_PTR <= 32
494
  base = &G.lookup[0];
495
#else
496
  page_table table = G.lookup;
497
  size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
498
  while (table->high_bits != high_bits)
499
    table = table->next;
500
  base = &table->table[0];
501
#endif
502
 
503
  /* Extract the level 1 and 2 indices.  */
504
  L1 = LOOKUP_L1 (p);
505
  L2 = LOOKUP_L2 (p);
506
 
507
  return base[L1][L2];
508
}
509
 
510
/* Traverse the page table and find the entry for a page.
511
   Return NULL if the object wasn't allocated via the GC.  */
512
 
513
static inline page_entry *
514
lookup_page_table_if_allocated (const void *p)
515
{
516
  page_entry ***base;
517
  size_t L1, L2;
518
 
519
#if HOST_BITS_PER_PTR <= 32
520
  base = &G.lookup[0];
521
#else
522
  page_table table = G.lookup;
523
  size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
524
  while (1)
525
    {
526
      if (table == NULL)
527
        return NULL;
528
      if (table->high_bits == high_bits)
529
        break;
530
      table = table->next;
531
    }
532
  base = &table->table[0];
533
#endif
534
 
535
  /* Extract the level 1 and 2 indices.  */
536
  L1 = LOOKUP_L1 (p);
537
  if (! base[L1])
538
    return NULL;
539
 
540
  L2 = LOOKUP_L2 (p);
541
  if (L2 >= PAGE_L2_SIZE)
542
    return NULL;
543
  /* We might have a page entry which does not correspond exactly to a
544
     system page.  */
545
  if (base[L1][L2] && (const char *) p < base[L1][L2]->page)
546
    return NULL;
547
 
548
  return base[L1][L2];
549
}
550
 
551
/* Set the page table entry for the page that starts at P.  If ENTRY
552
   is NULL, clear the entry.  */
553
 
554
static void
555
set_page_table_entry (void *p, page_entry *entry)
556
{
557
  page_entry ***base;
558
  size_t L1, L2;
559
 
560
#if HOST_BITS_PER_PTR <= 32
561
  base = &G.lookup[0];
562
#else
563
  page_table table;
564
  size_t high_bits = (size_t) p & ~ (size_t) 0xffffffff;
565
  for (table = G.lookup; table; table = table->next)
566
    if (table->high_bits == high_bits)
567
      goto found;
568
 
569
  /* Not found -- allocate a new table.  */
570
  table = XCNEW (struct page_table_chain);
571
  table->next = G.lookup;
572
  table->high_bits = high_bits;
573
  G.lookup = table;
574
found:
575
  base = &table->table[0];
576
#endif
577
 
578
  /* Extract the level 1 and 2 indices.  */
579
  L1 = LOOKUP_L1 (p);
580
  L2 = LOOKUP_L2 (p);
581
 
582
  if (base[L1] == NULL)
583
    base[L1] = XCNEWVEC (page_entry *, PAGE_L2_SIZE);
584
 
585
  base[L1][L2] = entry;
586
}
587
 
588
/* Find the page table entry associated with OBJECT.  */
589
 
590
static inline struct page_entry *
591
zone_get_object_page (const void *object)
592
{
593
  return lookup_page_table_entry (object);
594
}
595
 
596
/* Find which element of the alloc_bits array OBJECT should be
597
   recorded in.  */
598
static inline unsigned int
599
zone_get_object_alloc_word (const void *object)
600
{
601
  return (((size_t) object & (GGC_PAGE_SIZE - 1))
602
          / (8 * sizeof (alloc_type) * BYTES_PER_ALLOC_BIT));
603
}
604
 
605
/* Find which bit of the appropriate word in the alloc_bits array
606
   OBJECT should be recorded in.  */
607
static inline unsigned int
608
zone_get_object_alloc_bit (const void *object)
609
{
610
  return (((size_t) object / BYTES_PER_ALLOC_BIT)
611
          % (8 * sizeof (alloc_type)));
612
}
613
 
614
/* Find which element of the mark_bits array OBJECT should be recorded
615
   in.  */
616
static inline unsigned int
617
zone_get_object_mark_word (const void *object)
618
{
619
  return (((size_t) object & (GGC_PAGE_SIZE - 1))
620
          / (8 * sizeof (mark_type) * BYTES_PER_MARK_BIT));
621
}
622
 
623
/* Find which bit of the appropriate word in the mark_bits array
624
   OBJECT should be recorded in.  */
625
static inline unsigned int
626
zone_get_object_mark_bit (const void *object)
627
{
628
  return (((size_t) object / BYTES_PER_MARK_BIT)
629
          % (8 * sizeof (mark_type)));
630
}
631
 
632
/* Set the allocation bit corresponding to OBJECT in its page's
633
   bitmap.  Used to split this object from the preceding one.  */
634
static inline void
635
zone_set_object_alloc_bit (const void *object)
636
{
637
  struct small_page_entry *page
638
    = (struct small_page_entry *) zone_get_object_page (object);
639
  unsigned int start_word = zone_get_object_alloc_word (object);
640
  unsigned int start_bit = zone_get_object_alloc_bit (object);
641
 
642
  page->alloc_bits[start_word] |= 1L << start_bit;
643
}
644
 
645
/* Clear the allocation bit corresponding to OBJECT in PAGE's
646
   bitmap.  Used to coalesce this object with the preceding
647
   one.  */
648
static inline void
649
zone_clear_object_alloc_bit (struct small_page_entry *page,
650
                             const void *object)
651
{
652
  unsigned int start_word = zone_get_object_alloc_word (object);
653
  unsigned int start_bit = zone_get_object_alloc_bit (object);
654
 
655
  /* Would xor be quicker?  */
656
  page->alloc_bits[start_word] &= ~(1L << start_bit);
657
}
658
 
659
/* Find the size of the object which starts at START_WORD and
660
   START_BIT in ALLOC_BITS, which is at most MAX_SIZE bytes.
661
   Helper function for ggc_get_size and zone_find_object_size.  */
662
 
663
static inline size_t
664
zone_object_size_1 (alloc_type *alloc_bits,
665
                    size_t start_word, size_t start_bit,
666
                    size_t max_size)
667
{
668
  size_t size;
669
  alloc_type alloc_word;
670
  int indx;
671
 
672
  /* Load the first word.  */
673
  alloc_word = alloc_bits[start_word++];
674
 
675
  /* If that was the last bit in this word, we'll want to continue
676
     with the next word.  Otherwise, handle the rest of this word.  */
677
  if (start_bit)
678
    {
679
      indx = alloc_ffs (alloc_word >> start_bit);
680
      if (indx)
681
        /* indx is 1-based.  We started at the bit after the object's
682
           start, but we also ended at the bit after the object's end.
683
           It cancels out.  */
684
        return indx * BYTES_PER_ALLOC_BIT;
685
 
686
      /* The extra 1 accounts for the starting unit, before start_bit.  */
687
      size = (sizeof (alloc_type) * 8 - start_bit + 1) * BYTES_PER_ALLOC_BIT;
688
 
689
      if (size >= max_size)
690
        return max_size;
691
 
692
      alloc_word = alloc_bits[start_word++];
693
    }
694
  else
695
    size = BYTES_PER_ALLOC_BIT;
696
 
697
  while (alloc_word == 0)
698
    {
699
      size += sizeof (alloc_type) * 8 * BYTES_PER_ALLOC_BIT;
700
      if (size >= max_size)
701
        return max_size;
702
      alloc_word = alloc_bits[start_word++];
703
    }
704
 
705
  indx = alloc_ffs (alloc_word);
706
  return size + (indx - 1) * BYTES_PER_ALLOC_BIT;
707
}
708
 
709
/* Find the size of OBJECT on small page PAGE.  */
710
 
711
static inline size_t
712
zone_find_object_size (struct small_page_entry *page,
713
                       const void *object)
714
{
715
  const char *object_midptr = (const char *) object + BYTES_PER_ALLOC_BIT;
716
  unsigned int start_word = zone_get_object_alloc_word (object_midptr);
717
  unsigned int start_bit = zone_get_object_alloc_bit (object_midptr);
718
  size_t max_size = (page->common.page + SMALL_PAGE_SIZE
719
                     - (const char *) object);
720
 
721
  return zone_object_size_1 (page->alloc_bits, start_word, start_bit,
722
                             max_size);
723
}
724
 
725
/* highest_bit assumes that alloc_type is 32 bits.  */
726
extern char check_alloc_type_size[(sizeof (alloc_type) == 4) ? 1 : -1];
727
 
728
/* Find the highest set bit in VALUE.  Returns the bit number of that
729
   bit, using the same values as ffs.  */
730
static inline alloc_type
731
highest_bit (alloc_type value)
732
{
733
  /* This also assumes that alloc_type is unsigned.  */
734
  value |= value >> 1;
735
  value |= value >> 2;
736
  value |= value >> 4;
737
  value |= value >> 8;
738
  value |= value >> 16;
739
  value = value ^ (value >> 1);
740
  return alloc_ffs (value);
741
}
742
 
743
/* Find the offset from the start of an object to P, which may point
744
   into the interior of the object.  */
745
 
746
static unsigned long
747
zone_find_object_offset (alloc_type *alloc_bits, size_t start_word,
748
                         size_t start_bit)
749
{
750
  unsigned int offset_in_bits;
751
  alloc_type alloc_word = alloc_bits[start_word];
752
 
753
  /* Mask off any bits after the initial bit, but make sure to include
754
     the initial bit in the result.  Note that START_BIT is
755
     0-based.  */
756
  if (start_bit < 8 * sizeof (alloc_type) - 1)
757
    alloc_word &= (1 << (start_bit + 1)) - 1;
758
  offset_in_bits = start_bit;
759
 
760
  /* Search for the start of the object.  */
761
  while (alloc_word == 0 && start_word > 0)
762
    {
763
      alloc_word = alloc_bits[--start_word];
764
      offset_in_bits += 8 * sizeof (alloc_type);
765
    }
766
  /* We must always find a set bit.  */
767
  gcc_assert (alloc_word != 0);
768
  /* Note that the result of highest_bit is 1-based.  */
769
  offset_in_bits -= highest_bit (alloc_word) - 1;
770
 
771
  return BYTES_PER_ALLOC_BIT * offset_in_bits;
772
}
773
 
774
/* Allocate the mark bits for every zone, and set the pointers on each
775
   page.  */
776
static void
777
zone_allocate_marks (void)
778
{
779
  struct alloc_zone *zone;
780
 
781
  for (zone = G.zones; zone; zone = zone->next_zone)
782
    {
783
      struct small_page_entry *page;
784
      mark_type *cur_marks;
785
      size_t mark_words, mark_words_per_page;
786
#ifdef ENABLE_CHECKING
787
      size_t n = 0;
788
#endif
789
 
790
      mark_words_per_page
791
        = (GGC_PAGE_SIZE + BYTES_PER_MARK_WORD - 1) / BYTES_PER_MARK_WORD;
792
      mark_words = zone->n_small_pages * mark_words_per_page;
793
      zone->mark_bits = (mark_type *) xcalloc (sizeof (mark_type),
794
                                                   mark_words);
795
      cur_marks = zone->mark_bits;
796
      for (page = zone->pages; page; page = page->next)
797
        {
798
          page->mark_bits = cur_marks;
799
          cur_marks += mark_words_per_page;
800
#ifdef ENABLE_CHECKING
801
          n++;
802
#endif
803
        }
804
#ifdef ENABLE_CHECKING
805
      gcc_assert (n == zone->n_small_pages);
806
#endif
807
    }
808
 
809
  /* We don't collect the PCH zone, but we do have to mark it
810
     (for now).  */
811
  if (pch_zone.bytes)
812
    pch_zone.mark_bits
813
      = (mark_type *) xcalloc (sizeof (mark_type),
814
                               CEIL (pch_zone.bytes, BYTES_PER_MARK_WORD));
815
}
816
 
817
/* After marking and sweeping, release the memory used for mark bits.  */
818
static void
819
zone_free_marks (void)
820
{
821
  struct alloc_zone *zone;
822
 
823
  for (zone = G.zones; zone; zone = zone->next_zone)
824
    if (zone->mark_bits)
825
      {
826
        free (zone->mark_bits);
827
        zone->mark_bits = NULL;
828
      }
829
 
830
  if (pch_zone.bytes)
831
    {
832
      free (pch_zone.mark_bits);
833
      pch_zone.mark_bits = NULL;
834
    }
835
}
836
 
837
#ifdef USING_MMAP
838
/* Allocate SIZE bytes of anonymous memory, preferably near PREF,
839
   (if non-null).  The ifdef structure here is intended to cause a
840
   compile error unless exactly one of the HAVE_* is defined.  */
841
 
842
static inline char *
843
alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size, struct alloc_zone *zone)
844
{
845
#ifdef HAVE_MMAP_ANON
846
  char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
847
                              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
848
#endif
849
#ifdef HAVE_MMAP_DEV_ZERO
850
  char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
851
                              MAP_PRIVATE, G.dev_zero_fd, 0);
852
#endif
853
 
854
  if (page == (char *) MAP_FAILED)
855
    {
856
      perror ("virtual memory exhausted");
857
      exit (FATAL_EXIT_CODE);
858
    }
859
 
860
  /* Remember that we allocated this memory.  */
861
  zone->bytes_mapped += size;
862
 
863
  /* Pretend we don't have access to the allocated pages.  We'll enable
864
     access to smaller pieces of the area in ggc_alloc.  Discard the
865
     handle to avoid handle leak.  */
866
  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (page, size));
867
 
868
  return page;
869
}
870
#endif
871
 
872
/* Allocate a new page for allocating small objects in ZONE, and
873
   return an entry for it.  */
874
 
875
static struct small_page_entry *
876
alloc_small_page (struct alloc_zone *zone)
877
{
878
  struct small_page_entry *entry;
879
 
880
  /* Check the list of free pages for one we can use.  */
881
  entry = zone->free_pages;
882
  if (entry != NULL)
883
    {
884
      /* Recycle the allocated memory from this page ...  */
885
      zone->free_pages = entry->next;
886
    }
887
  else
888
    {
889
      /* We want just one page.  Allocate a bunch of them and put the
890
         extras on the freelist.  (Can only do this optimization with
891
         mmap for backing store.)  */
892
      struct small_page_entry *e, *f = zone->free_pages;
893
      int i;
894
      char *page;
895
 
896
      page = alloc_anon (NULL, GGC_PAGE_SIZE * G.quire_size, zone);
897
 
898
      /* This loop counts down so that the chain will be in ascending
899
         memory order.  */
900
      for (i = G.quire_size - 1; i >= 1; i--)
901
        {
902
          e = XCNEWVAR (struct small_page_entry, G.small_page_overhead);
903
          e->common.page = page + (i << GGC_PAGE_SHIFT);
904
          e->common.zone = zone;
905
          e->next = f;
906
          f = e;
907
          set_page_table_entry (e->common.page, &e->common);
908
        }
909
 
910
      zone->free_pages = f;
911
 
912
      entry = XCNEWVAR (struct small_page_entry, G.small_page_overhead);
913
      entry->common.page = page;
914
      entry->common.zone = zone;
915
      set_page_table_entry (page, &entry->common);
916
    }
917
 
918
  zone->n_small_pages++;
919
 
920
  if (GGC_DEBUG_LEVEL >= 2)
921
    fprintf (G.debug_file,
922
             "Allocating %s page at %p, data %p-%p\n",
923
             entry->common.zone->name, (PTR) entry, entry->common.page,
924
             entry->common.page + SMALL_PAGE_SIZE - 1);
925
 
926
  return entry;
927
}
928
 
929
/* Allocate a large page of size SIZE in ZONE.  */
930
 
931
static struct large_page_entry *
932
alloc_large_page (size_t size, struct alloc_zone *zone)
933
{
934
  struct large_page_entry *entry;
935
  char *page;
936
  size_t needed_size;
937
 
938
  needed_size = size + sizeof (struct large_page_entry);
939
  page = XNEWVAR (char, needed_size);
940
 
941
  entry = (struct large_page_entry *) page;
942
 
943
  entry->next = NULL;
944
  entry->common.page = page + sizeof (struct large_page_entry);
945
  entry->common.large_p = true;
946
  entry->common.pch_p = false;
947
  entry->common.zone = zone;
948
#ifdef GATHER_STATISTICS
949
  entry->common.survived = 0;
950
#endif
951
  entry->mark_p = false;
952
  entry->bytes = size;
953
  entry->prev = NULL;
954
 
955
  set_page_table_entry (entry->common.page, &entry->common);
956
 
957
  if (GGC_DEBUG_LEVEL >= 2)
958
    fprintf (G.debug_file,
959
             "Allocating %s large page at %p, data %p-%p\n",
960
             entry->common.zone->name, (PTR) entry, entry->common.page,
961
             entry->common.page + SMALL_PAGE_SIZE - 1);
962
 
963
  return entry;
964
}
965
 
966
 
967
/* For a page that is no longer needed, put it on the free page list.  */
968
 
969
static inline void
970
free_small_page (struct small_page_entry *entry)
971
{
972
  if (GGC_DEBUG_LEVEL >= 2)
973
    fprintf (G.debug_file,
974
             "Deallocating %s page at %p, data %p-%p\n",
975
             entry->common.zone->name, (PTR) entry,
976
             entry->common.page, entry->common.page + SMALL_PAGE_SIZE - 1);
977
 
978
  gcc_assert (!entry->common.large_p);
979
 
980
  /* Mark the page as inaccessible.  Discard the handle to
981
     avoid handle leak.  */
982
  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (entry->common.page,
983
                                                SMALL_PAGE_SIZE));
984
 
985
  entry->next = entry->common.zone->free_pages;
986
  entry->common.zone->free_pages = entry;
987
  entry->common.zone->n_small_pages--;
988
}
989
 
990
/* Release a large page that is no longer needed.  */
991
 
992
static inline void
993
free_large_page (struct large_page_entry *entry)
994
{
995
  if (GGC_DEBUG_LEVEL >= 2)
996
    fprintf (G.debug_file,
997
             "Deallocating %s page at %p, data %p-%p\n",
998
             entry->common.zone->name, (PTR) entry,
999
             entry->common.page, entry->common.page + SMALL_PAGE_SIZE - 1);
1000
 
1001
  gcc_assert (entry->common.large_p);
1002
 
1003
  set_page_table_entry (entry->common.page, NULL);
1004
  free (entry);
1005
}
1006
 
1007
/* Release the free page cache to the system.  */
1008
 
1009
static void
1010
release_pages (struct alloc_zone *zone)
1011
{
1012
#ifdef USING_MMAP
1013
  struct small_page_entry *p, *next;
1014
  char *start;
1015
  size_t len;
1016
 
1017
  /* Gather up adjacent pages so they are unmapped together.  */
1018
  p = zone->free_pages;
1019
 
1020
  while (p)
1021
    {
1022
      start = p->common.page;
1023
      next = p->next;
1024
      len = SMALL_PAGE_SIZE;
1025
      set_page_table_entry (p->common.page, NULL);
1026
      p = next;
1027
 
1028
      while (p && p->common.page == start + len)
1029
        {
1030
          next = p->next;
1031
          len += SMALL_PAGE_SIZE;
1032
          set_page_table_entry (p->common.page, NULL);
1033
          p = next;
1034
        }
1035
 
1036
      munmap (start, len);
1037
      zone->bytes_mapped -= len;
1038
    }
1039
 
1040
  zone->free_pages = NULL;
1041
#endif
1042
}
1043
 
1044
/* Place the block at PTR of size SIZE on the free list for ZONE.  */
1045
 
1046
static inline void
1047
free_chunk (char *ptr, size_t size, struct alloc_zone *zone)
1048
{
1049
  struct alloc_chunk *chunk = (struct alloc_chunk *) ptr;
1050
  size_t bin = 0;
1051
 
1052
  bin = SIZE_BIN_DOWN (size);
1053
  gcc_assert (bin != 0);
1054
  if (bin > NUM_FREE_BINS)
1055
    {
1056
      bin = 0;
1057
      VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (chunk,
1058
                                                     sizeof (struct
1059
                                                             alloc_chunk)));
1060
      chunk->size = size;
1061
      chunk->next_free = zone->free_chunks[bin];
1062
      VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (ptr
1063
                                                    + sizeof (struct
1064
                                                              alloc_chunk),
1065
                                                    size
1066
                                                    - sizeof (struct
1067
                                                              alloc_chunk)));
1068
    }
1069
  else
1070
    {
1071
      VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (chunk,
1072
                                                     sizeof (struct
1073
                                                             alloc_chunk *)));
1074
      chunk->next_free = zone->free_chunks[bin];
1075
      VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (ptr
1076
                                                    + sizeof (struct
1077
                                                              alloc_chunk *),
1078
                                                    size
1079
                                                    - sizeof (struct
1080
                                                              alloc_chunk *)));
1081
    }
1082
 
1083
  zone->free_chunks[bin] = chunk;
1084
  if (bin > zone->high_free_bin)
1085
    zone->high_free_bin = bin;
1086
  if (GGC_DEBUG_LEVEL >= 3)
1087
    fprintf (G.debug_file, "Deallocating object, chunk=%p\n", (void *)chunk);
1088
}
1089
 
1090
/* Allocate a chunk of memory of at least ORIG_SIZE bytes, in ZONE.  */
1091
 
1092
void *
1093
ggc_alloc_zone_stat (size_t orig_size, struct alloc_zone *zone
1094
                     MEM_STAT_DECL)
1095
{
1096
  size_t bin;
1097
  size_t csize;
1098
  struct small_page_entry *entry;
1099
  struct alloc_chunk *chunk, **pp;
1100
  void *result;
1101
  size_t size = orig_size;
1102
 
1103
  /* Make sure that zero-sized allocations get a unique and freeable
1104
     pointer.  */
1105
  if (size == 0)
1106
    size = MAX_ALIGNMENT;
1107
  else
1108
    size = (size + MAX_ALIGNMENT - 1) & -MAX_ALIGNMENT;
1109
 
1110
  /* Try to allocate the object from several different sources.  Each
1111
     of these cases is responsible for setting RESULT and SIZE to
1112
     describe the allocated block, before jumping to FOUND.  If a
1113
     chunk is split, the allocate bit for the new chunk should also be
1114
     set.
1115
 
1116
     Large objects are handled specially.  However, they'll just fail
1117
     the next couple of conditions, so we can wait to check for them
1118
     below.  The large object case is relatively rare (< 1%), so this
1119
     is a win.  */
1120
 
1121
  /* First try to split the last chunk we allocated.  For best
1122
     fragmentation behavior it would be better to look for a
1123
     free bin of the appropriate size for a small object.  However,
1124
     we're unlikely (1% - 7%) to find one, and this gives better
1125
     locality behavior anyway.  This case handles the lion's share
1126
     of all calls to this function.  */
1127
  if (size <= zone->cached_free_size)
1128
    {
1129
      result = zone->cached_free;
1130
 
1131
      zone->cached_free_size -= size;
1132
      if (zone->cached_free_size)
1133
        {
1134
          zone->cached_free += size;
1135
          zone_set_object_alloc_bit (zone->cached_free);
1136
        }
1137
 
1138
      goto found;
1139
    }
1140
 
1141
  /* Next, try to find a free bin of the exactly correct size.  */
1142
 
1143
  /* We want to round SIZE up, rather than down, but we know it's
1144
     already aligned to at least FREE_BIN_DELTA, so we can just
1145
     shift.  */
1146
  bin = SIZE_BIN_DOWN (size);
1147
 
1148
  if (bin <= NUM_FREE_BINS
1149
      && (chunk = zone->free_chunks[bin]) != NULL)
1150
    {
1151
      /* We have a chunk of the right size.  Pull it off the free list
1152
         and use it.  */
1153
 
1154
      zone->free_chunks[bin] = chunk->next_free;
1155
 
1156
      /* NOTE: SIZE is only guaranteed to be right if MAX_ALIGNMENT
1157
         == FREE_BIN_DELTA.  */
1158
      result = chunk;
1159
 
1160
      /* The allocation bits are already set correctly.  HIGH_FREE_BIN
1161
         may now be wrong, if this was the last chunk in the high bin.
1162
         Rather than fixing it up now, wait until we need to search
1163
         the free bins.  */
1164
 
1165
      goto found;
1166
    }
1167
 
1168
  /* Next, if there wasn't a chunk of the ideal size, look for a chunk
1169
     to split.  We can find one in the too-big bin, or in the largest
1170
     sized bin with a chunk in it.  Try the largest normal-sized bin
1171
     first.  */
1172
 
1173
  if (zone->high_free_bin > bin)
1174
    {
1175
      /* Find the highest numbered free bin.  It will be at or below
1176
         the watermark.  */
1177
      while (zone->high_free_bin > bin
1178
             && zone->free_chunks[zone->high_free_bin] == NULL)
1179
        zone->high_free_bin--;
1180
 
1181
      if (zone->high_free_bin > bin)
1182
        {
1183
          size_t tbin = zone->high_free_bin;
1184
          chunk = zone->free_chunks[tbin];
1185
 
1186
          /* Remove the chunk from its previous bin.  */
1187
          zone->free_chunks[tbin] = chunk->next_free;
1188
 
1189
          result = (char *) chunk;
1190
 
1191
          /* Save the rest of the chunk for future allocation.  */
1192
          if (zone->cached_free_size)
1193
            free_chunk (zone->cached_free, zone->cached_free_size, zone);
1194
 
1195
          chunk = (struct alloc_chunk *) ((char *) result + size);
1196
          zone->cached_free = (char *) chunk;
1197
          zone->cached_free_size = (tbin - bin) * FREE_BIN_DELTA;
1198
 
1199
          /* Mark the new free chunk as an object, so that we can
1200
             find the size of the newly allocated object.  */
1201
          zone_set_object_alloc_bit (chunk);
1202
 
1203
          /* HIGH_FREE_BIN may now be wrong, if this was the last
1204
             chunk in the high bin.  Rather than fixing it up now,
1205
             wait until we need to search the free bins.  */
1206
 
1207
          goto found;
1208
        }
1209
    }
1210
 
1211
  /* Failing that, look through the "other" bucket for a chunk
1212
     that is large enough.  */
1213
  pp = &(zone->free_chunks[0]);
1214
  chunk = *pp;
1215
  while (chunk && chunk->size < size)
1216
    {
1217
      pp = &chunk->next_free;
1218
      chunk = *pp;
1219
    }
1220
 
1221
  if (chunk)
1222
    {
1223
      /* Remove the chunk from its previous bin.  */
1224
      *pp = chunk->next_free;
1225
 
1226
      result = (char *) chunk;
1227
 
1228
      /* Save the rest of the chunk for future allocation, if there's any
1229
         left over.  */
1230
      csize = chunk->size;
1231
      if (csize > size)
1232
        {
1233
          if (zone->cached_free_size)
1234
            free_chunk (zone->cached_free, zone->cached_free_size, zone);
1235
 
1236
          chunk = (struct alloc_chunk *) ((char *) result + size);
1237
          zone->cached_free = (char *) chunk;
1238
          zone->cached_free_size = csize - size;
1239
 
1240
          /* Mark the new free chunk as an object.  */
1241
          zone_set_object_alloc_bit (chunk);
1242
        }
1243
 
1244
      goto found;
1245
    }
1246
 
1247
  /* Handle large allocations.  We could choose any threshold between
1248
     GGC_PAGE_SIZE - sizeof (struct large_page_entry) and
1249
     GGC_PAGE_SIZE.  It can't be smaller, because then it wouldn't
1250
     be guaranteed to have a unique entry in the lookup table.  Large
1251
     allocations will always fall through to here.  */
1252
  if (size > GGC_PAGE_SIZE)
1253
    {
1254
      struct large_page_entry *entry = alloc_large_page (size, zone);
1255
 
1256
#ifdef GATHER_STATISTICS
1257
      entry->common.survived = 0;
1258
#endif
1259
 
1260
      entry->next = zone->large_pages;
1261
      if (zone->large_pages)
1262
        zone->large_pages->prev = entry;
1263
      zone->large_pages = entry;
1264
 
1265
      result = entry->common.page;
1266
 
1267
      goto found;
1268
    }
1269
 
1270
  /* Failing everything above, allocate a new small page.  */
1271
 
1272
  entry = alloc_small_page (zone);
1273
  entry->next = zone->pages;
1274
  zone->pages = entry;
1275
 
1276
  /* Mark the first chunk in the new page.  */
1277
  entry->alloc_bits[0] = 1;
1278
 
1279
  result = entry->common.page;
1280
  if (size < SMALL_PAGE_SIZE)
1281
    {
1282
      if (zone->cached_free_size)
1283
        free_chunk (zone->cached_free, zone->cached_free_size, zone);
1284
 
1285
      zone->cached_free = (char *) result + size;
1286
      zone->cached_free_size = SMALL_PAGE_SIZE - size;
1287
 
1288
      /* Mark the new free chunk as an object.  */
1289
      zone_set_object_alloc_bit (zone->cached_free);
1290
    }
1291
 
1292
 found:
1293
 
1294
  /* We could save TYPE in the chunk, but we don't use that for
1295
     anything yet.  If we wanted to, we could do it by adding it
1296
     either before the beginning of the chunk or after its end,
1297
     and adjusting the size and pointer appropriately.  */
1298
 
1299
  /* We'll probably write to this after we return.  */
1300
  prefetchw (result);
1301
 
1302
#ifdef ENABLE_GC_CHECKING
1303
  /* `Poison' the entire allocated object.  */
1304
  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (result, size));
1305
  memset (result, 0xaf, size);
1306
  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (result + orig_size,
1307
                                                size - orig_size));
1308
#endif
1309
 
1310
  /* Tell Valgrind that the memory is there, but its content isn't
1311
     defined.  The bytes at the end of the object are still marked
1312
     unaccessible.  */
1313
  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (result, orig_size));
1314
 
1315
  /* Keep track of how many bytes are being allocated.  This
1316
     information is used in deciding when to collect.  */
1317
  zone->allocated += size;
1318
 
1319
  timevar_ggc_mem_total += size;
1320
 
1321
#ifdef GATHER_STATISTICS
1322
  ggc_record_overhead (orig_size, size - orig_size, result PASS_MEM_STAT);
1323
 
1324
  {
1325
    size_t object_size = size;
1326
    size_t overhead = object_size - orig_size;
1327
 
1328
    zone->stats.total_overhead += overhead;
1329
    zone->stats.total_allocated += object_size;
1330
 
1331
    if (orig_size <= 32)
1332
      {
1333
        zone->stats.total_overhead_under32 += overhead;
1334
        zone->stats.total_allocated_under32 += object_size;
1335
      }
1336
    if (orig_size <= 64)
1337
      {
1338
        zone->stats.total_overhead_under64 += overhead;
1339
        zone->stats.total_allocated_under64 += object_size;
1340
      }
1341
    if (orig_size <= 128)
1342
      {
1343
        zone->stats.total_overhead_under128 += overhead;
1344
        zone->stats.total_allocated_under128 += object_size;
1345
      }
1346
  }
1347
#endif
1348
 
1349
  if (GGC_DEBUG_LEVEL >= 3)
1350
    fprintf (G.debug_file, "Allocating object, size=%lu at %p\n",
1351
             (unsigned long) size, result);
1352
 
1353
  return result;
1354
}
1355
 
1356
/* Allocate a SIZE of chunk memory of GTE type, into an appropriate zone
1357
   for that type.  */
1358
 
1359
void *
1360
ggc_alloc_typed_stat (enum gt_types_enum gte, size_t size
1361
                      MEM_STAT_DECL)
1362
{
1363
  switch (gte)
1364
    {
1365
    case gt_ggc_e_14lang_tree_node:
1366
      return ggc_alloc_zone_pass_stat (size, &tree_zone);
1367
 
1368
    case gt_ggc_e_7rtx_def:
1369
      return ggc_alloc_zone_pass_stat (size, &rtl_zone);
1370
 
1371
    case gt_ggc_e_9rtvec_def:
1372
      return ggc_alloc_zone_pass_stat (size, &rtl_zone);
1373
 
1374
    default:
1375
      return ggc_alloc_zone_pass_stat (size, &main_zone);
1376
    }
1377
}
1378
 
1379
/* Normal ggc_alloc simply allocates into the main zone.  */
1380
 
1381
void *
1382
ggc_alloc_stat (size_t size MEM_STAT_DECL)
1383
{
1384
  return ggc_alloc_zone_pass_stat (size, &main_zone);
1385
}
1386
 
1387
/* Poison the chunk.  */
1388
#ifdef ENABLE_GC_CHECKING
1389
#define poison_region(PTR, SIZE) \
1390
  memset ((PTR), 0xa5, (SIZE))
1391
#else
1392
#define poison_region(PTR, SIZE)
1393
#endif
1394
 
1395
/* Free the object at P.  */
1396
 
1397
void
1398
ggc_free (void *p)
1399
{
1400
  struct page_entry *page;
1401
 
1402
#ifdef GATHER_STATISTICS
1403
  ggc_free_overhead (p);
1404
#endif
1405
 
1406
  poison_region (p, ggc_get_size (p));
1407
 
1408
  page = zone_get_object_page (p);
1409
 
1410
  if (page->large_p)
1411
    {
1412
      struct large_page_entry *large_page
1413
        = (struct large_page_entry *) page;
1414
 
1415
      /* Remove the page from the linked list.  */
1416
      if (large_page->prev)
1417
        large_page->prev->next = large_page->next;
1418
      else
1419
        {
1420
          gcc_assert (large_page->common.zone->large_pages == large_page);
1421
          large_page->common.zone->large_pages = large_page->next;
1422
        }
1423
      if (large_page->next)
1424
        large_page->next->prev = large_page->prev;
1425
 
1426
      large_page->common.zone->allocated -= large_page->bytes;
1427
 
1428
      /* Release the memory associated with this object.  */
1429
      free_large_page (large_page);
1430
    }
1431
  else if (page->pch_p)
1432
    /* Don't do anything.  We won't allocate a new object from the
1433
       PCH zone so there's no point in releasing anything.  */
1434
    ;
1435
  else
1436
    {
1437
      size_t size = ggc_get_size (p);
1438
 
1439
      page->zone->allocated -= size;
1440
 
1441
      /* Add the chunk to the free list.  We don't bother with coalescing,
1442
         since we are likely to want a chunk of this size again.  */
1443
      free_chunk ((char *)p, size, page->zone);
1444
    }
1445
}
1446
 
1447
/* Mark function for strings.  */
1448
 
1449
void
1450
gt_ggc_m_S (const void *p)
1451
{
1452
  page_entry *entry;
1453
  unsigned long offset;
1454
 
1455
  if (!p)
1456
    return;
1457
 
1458
  /* Look up the page on which the object is alloced.  .  */
1459
  entry = lookup_page_table_if_allocated (p);
1460
  if (! entry)
1461
    return;
1462
 
1463
  if (entry->pch_p)
1464
    {
1465
      size_t alloc_word, alloc_bit, t;
1466
      t = ((const char *) p - pch_zone.page) / BYTES_PER_ALLOC_BIT;
1467
      alloc_word = t / (8 * sizeof (alloc_type));
1468
      alloc_bit = t % (8 * sizeof (alloc_type));
1469
      offset = zone_find_object_offset (pch_zone.alloc_bits, alloc_word,
1470
                                        alloc_bit);
1471
    }
1472
  else if (entry->large_p)
1473
    {
1474
      struct large_page_entry *le = (struct large_page_entry *) entry;
1475
      offset = ((const char *) p) - entry->page;
1476
      gcc_assert (offset < le->bytes);
1477
    }
1478
  else
1479
    {
1480
      struct small_page_entry *se = (struct small_page_entry *) entry;
1481
      unsigned int start_word = zone_get_object_alloc_word (p);
1482
      unsigned int start_bit = zone_get_object_alloc_bit (p);
1483
      offset = zone_find_object_offset (se->alloc_bits, start_word, start_bit);
1484
 
1485
      /* On some platforms a char* will not necessarily line up on an
1486
         allocation boundary, so we have to update the offset to
1487
         account for the leftover bytes.  */
1488
      offset += (size_t) p % BYTES_PER_ALLOC_BIT;
1489
    }
1490
 
1491
  if (offset)
1492
    {
1493
      /* Here we've seen a char* which does not point to the beginning
1494
         of an allocated object.  We assume it points to the middle of
1495
         a STRING_CST.  */
1496
      gcc_assert (offset == offsetof (struct tree_string, str));
1497
      p = ((const char *) p) - offset;
1498
      gt_ggc_mx_lang_tree_node (CONST_CAST(void *, p));
1499
      return;
1500
    }
1501
 
1502
  /* Inefficient, but also unlikely to matter.  */
1503
  ggc_set_mark (p);
1504
}
1505
 
1506
/* If P is not marked, mark it and return false.  Otherwise return true.
1507
   P must have been allocated by the GC allocator; it mustn't point to
1508
   static objects, stack variables, or memory allocated with malloc.  */
1509
 
1510
int
1511
ggc_set_mark (const void *p)
1512
{
1513
  struct page_entry *page;
1514
  const char *ptr = (const char *) p;
1515
 
1516
  page = zone_get_object_page (p);
1517
 
1518
  if (page->pch_p)
1519
    {
1520
      size_t mark_word, mark_bit, offset;
1521
      offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
1522
      mark_word = offset / (8 * sizeof (mark_type));
1523
      mark_bit = offset % (8 * sizeof (mark_type));
1524
 
1525
      if (pch_zone.mark_bits[mark_word] & (1 << mark_bit))
1526
        return 1;
1527
      pch_zone.mark_bits[mark_word] |= (1 << mark_bit);
1528
    }
1529
  else if (page->large_p)
1530
    {
1531
      struct large_page_entry *large_page
1532
        = (struct large_page_entry *) page;
1533
 
1534
      if (large_page->mark_p)
1535
        return 1;
1536
      large_page->mark_p = true;
1537
    }
1538
  else
1539
    {
1540
      struct small_page_entry *small_page
1541
        = (struct small_page_entry *) page;
1542
 
1543
      if (small_page->mark_bits[zone_get_object_mark_word (p)]
1544
          & (1 << zone_get_object_mark_bit (p)))
1545
        return 1;
1546
      small_page->mark_bits[zone_get_object_mark_word (p)]
1547
        |= (1 << zone_get_object_mark_bit (p));
1548
    }
1549
 
1550
  if (GGC_DEBUG_LEVEL >= 4)
1551
    fprintf (G.debug_file, "Marking %p\n", p);
1552
 
1553
  return 0;
1554
}
1555
 
1556
/* Return 1 if P has been marked, zero otherwise.
1557
   P must have been allocated by the GC allocator; it mustn't point to
1558
   static objects, stack variables, or memory allocated with malloc.  */
1559
 
1560
int
1561
ggc_marked_p (const void *p)
1562
{
1563
  struct page_entry *page;
1564
  const char *ptr = (const char *) p;
1565
 
1566
  page = zone_get_object_page (p);
1567
 
1568
  if (page->pch_p)
1569
    {
1570
      size_t mark_word, mark_bit, offset;
1571
      offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
1572
      mark_word = offset / (8 * sizeof (mark_type));
1573
      mark_bit = offset % (8 * sizeof (mark_type));
1574
 
1575
      return (pch_zone.mark_bits[mark_word] & (1 << mark_bit)) != 0;
1576
    }
1577
 
1578
  if (page->large_p)
1579
    {
1580
      struct large_page_entry *large_page
1581
        = (struct large_page_entry *) page;
1582
 
1583
      return large_page->mark_p;
1584
    }
1585
  else
1586
    {
1587
      struct small_page_entry *small_page
1588
        = (struct small_page_entry *) page;
1589
 
1590
      return 0 != (small_page->mark_bits[zone_get_object_mark_word (p)]
1591
                   & (1 << zone_get_object_mark_bit (p)));
1592
    }
1593
}
1594
 
1595
/* Return the size of the gc-able object P.  */
1596
 
1597
size_t
1598
ggc_get_size (const void *p)
1599
{
1600
  struct page_entry *page;
1601
  const char *ptr = (const char *) p;
1602
 
1603
  page = zone_get_object_page (p);
1604
 
1605
  if (page->pch_p)
1606
    {
1607
      size_t alloc_word, alloc_bit, offset, max_size;
1608
      offset = (ptr - pch_zone.page) / BYTES_PER_ALLOC_BIT + 1;
1609
      alloc_word = offset / (8 * sizeof (alloc_type));
1610
      alloc_bit = offset % (8 * sizeof (alloc_type));
1611
      max_size = pch_zone.bytes - (ptr - pch_zone.page);
1612
      return zone_object_size_1 (pch_zone.alloc_bits, alloc_word, alloc_bit,
1613
                                 max_size);
1614
    }
1615
 
1616
  if (page->large_p)
1617
    return ((struct large_page_entry *)page)->bytes;
1618
  else
1619
    return zone_find_object_size ((struct small_page_entry *) page, p);
1620
}
1621
 
1622
/* Initialize the ggc-zone-mmap allocator.  */
1623
void
1624
init_ggc (void)
1625
{
1626
  /* The allocation size must be greater than BYTES_PER_MARK_BIT, and
1627
     a multiple of both BYTES_PER_ALLOC_BIT and FREE_BIN_DELTA, for
1628
     the current assumptions to hold.  */
1629
 
1630
  gcc_assert (FREE_BIN_DELTA == MAX_ALIGNMENT);
1631
 
1632
  /* Set up the main zone by hand.  */
1633
  main_zone.name = "Main zone";
1634
  G.zones = &main_zone;
1635
 
1636
  /* Allocate the default zones.  */
1637
  new_ggc_zone_1 (&rtl_zone, "RTL zone");
1638
  new_ggc_zone_1 (&tree_zone, "Tree zone");
1639
  new_ggc_zone_1 (&tree_id_zone, "Tree identifier zone");
1640
 
1641
  G.pagesize = getpagesize();
1642
  G.lg_pagesize = exact_log2 (G.pagesize);
1643
  G.page_mask = ~(G.pagesize - 1);
1644
 
1645
  /* Require the system page size to be a multiple of GGC_PAGE_SIZE.  */
1646
  gcc_assert ((G.pagesize & (GGC_PAGE_SIZE - 1)) == 0);
1647
 
1648
  /* Allocate 16 system pages at a time.  */
1649
  G.quire_size = 16 * G.pagesize / GGC_PAGE_SIZE;
1650
 
1651
  /* Calculate the size of the allocation bitmap and other overhead.  */
1652
  /* Right now we allocate bits for the page header and bitmap.  These
1653
     are wasted, but a little tricky to eliminate.  */
1654
  G.small_page_overhead
1655
    = PAGE_OVERHEAD + (GGC_PAGE_SIZE / BYTES_PER_ALLOC_BIT / 8);
1656
  /* G.small_page_overhead = ROUND_UP (G.small_page_overhead, MAX_ALIGNMENT); */
1657
 
1658
#ifdef HAVE_MMAP_DEV_ZERO
1659
  G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
1660
  gcc_assert (G.dev_zero_fd != -1);
1661
#endif
1662
 
1663
#if 0
1664
  G.debug_file = fopen ("ggc-mmap.debug", "w");
1665
  setlinebuf (G.debug_file);
1666
#else
1667
  G.debug_file = stdout;
1668
#endif
1669
 
1670
#ifdef USING_MMAP
1671
  /* StunOS has an amazing off-by-one error for the first mmap allocation
1672
     after fiddling with RLIMIT_STACK.  The result, as hard as it is to
1673
     believe, is an unaligned page allocation, which would cause us to
1674
     hork badly if we tried to use it.  */
1675
  {
1676
    char *p = alloc_anon (NULL, G.pagesize, &main_zone);
1677
    struct small_page_entry *e;
1678
    if ((size_t)p & (G.pagesize - 1))
1679
      {
1680
        /* How losing.  Discard this one and try another.  If we still
1681
           can't get something useful, give up.  */
1682
 
1683
        p = alloc_anon (NULL, G.pagesize, &main_zone);
1684
        gcc_assert (!((size_t)p & (G.pagesize - 1)));
1685
      }
1686
 
1687
    if (GGC_PAGE_SIZE == G.pagesize)
1688
      {
1689
        /* We have a good page, might as well hold onto it...  */
1690
        e = XCNEWVAR (struct small_page_entry, G.small_page_overhead);
1691
        e->common.page = p;
1692
        e->common.zone = &main_zone;
1693
        e->next = main_zone.free_pages;
1694
        set_page_table_entry (e->common.page, &e->common);
1695
        main_zone.free_pages = e;
1696
      }
1697
    else
1698
      {
1699
        munmap (p, G.pagesize);
1700
      }
1701
  }
1702
#endif
1703
}
1704
 
1705
/* Start a new GGC zone.  */
1706
 
1707
static void
1708
new_ggc_zone_1 (struct alloc_zone *new_zone, const char * name)
1709
{
1710
  new_zone->name = name;
1711
  new_zone->next_zone = G.zones->next_zone;
1712
  G.zones->next_zone = new_zone;
1713
}
1714
 
1715
struct alloc_zone *
1716
new_ggc_zone (const char * name)
1717
{
1718
  struct alloc_zone *new_zone = XCNEW (struct alloc_zone);
1719
  new_ggc_zone_1 (new_zone, name);
1720
  return new_zone;
1721
}
1722
 
1723
/* Destroy a GGC zone.  */
1724
void
1725
destroy_ggc_zone (struct alloc_zone * dead_zone)
1726
{
1727
  struct alloc_zone *z;
1728
 
1729
  for (z = G.zones; z && z->next_zone != dead_zone; z = z->next_zone)
1730
    /* Just find that zone.  */
1731
    continue;
1732
 
1733
  /* We should have found the zone in the list.  Anything else is fatal.  */
1734
  gcc_assert (z);
1735
 
1736
  /* z is dead, baby. z is dead.  */
1737
  z->dead = true;
1738
}
1739
 
1740
/* Free all empty pages and objects within a page for a given zone  */
1741
 
1742
static void
1743
sweep_pages (struct alloc_zone *zone)
1744
{
1745
  struct large_page_entry **lpp, *lp, *lnext;
1746
  struct small_page_entry **spp, *sp, *snext;
1747
  char *last_free;
1748
  size_t allocated = 0;
1749
  bool nomarksinpage;
1750
 
1751
  /* First, reset the free_chunks lists, since we are going to
1752
     re-free free chunks in hopes of coalescing them into large chunks.  */
1753
  memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
1754
  zone->high_free_bin = 0;
1755
  zone->cached_free = NULL;
1756
  zone->cached_free_size = 0;
1757
 
1758
  /* Large pages are all or none affairs. Either they are completely
1759
     empty, or they are completely full.  */
1760
  lpp = &zone->large_pages;
1761
  for (lp = zone->large_pages; lp != NULL; lp = lnext)
1762
    {
1763
      gcc_assert (lp->common.large_p);
1764
 
1765
      lnext = lp->next;
1766
 
1767
#ifdef GATHER_STATISTICS
1768
      /* This page has now survived another collection.  */
1769
      lp->common.survived++;
1770
#endif
1771
 
1772
      if (lp->mark_p)
1773
        {
1774
          lp->mark_p = false;
1775
          allocated += lp->bytes;
1776
          lpp = &lp->next;
1777
        }
1778
      else
1779
        {
1780
          *lpp = lnext;
1781
#ifdef ENABLE_GC_CHECKING
1782
          /* Poison the page.  */
1783
          memset (lp->common.page, 0xb5, SMALL_PAGE_SIZE);
1784
#endif
1785
          if (lp->prev)
1786
            lp->prev->next = lp->next;
1787
          if (lp->next)
1788
            lp->next->prev = lp->prev;
1789
          free_large_page (lp);
1790
        }
1791
    }
1792
 
1793
  spp = &zone->pages;
1794
  for (sp = zone->pages; sp != NULL; sp = snext)
1795
    {
1796
      char *object, *last_object;
1797
      char *end;
1798
      alloc_type *alloc_word_p;
1799
      mark_type *mark_word_p;
1800
 
1801
      gcc_assert (!sp->common.large_p);
1802
 
1803
      snext = sp->next;
1804
 
1805
#ifdef GATHER_STATISTICS
1806
      /* This page has now survived another collection.  */
1807
      sp->common.survived++;
1808
#endif
1809
 
1810
      /* Step through all chunks, consolidate those that are free and
1811
         insert them into the free lists.  Note that consolidation
1812
         slows down collection slightly.  */
1813
 
1814
      last_object = object = sp->common.page;
1815
      end = sp->common.page + SMALL_PAGE_SIZE;
1816
      last_free = NULL;
1817
      nomarksinpage = true;
1818
      mark_word_p = sp->mark_bits;
1819
      alloc_word_p = sp->alloc_bits;
1820
 
1821
      gcc_assert (BYTES_PER_ALLOC_BIT == BYTES_PER_MARK_BIT);
1822
 
1823
      object = sp->common.page;
1824
      do
1825
        {
1826
          unsigned int i, n;
1827
          alloc_type alloc_word;
1828
          mark_type mark_word;
1829
 
1830
          alloc_word = *alloc_word_p++;
1831
          mark_word = *mark_word_p++;
1832
 
1833
          if (mark_word)
1834
            nomarksinpage = false;
1835
 
1836
          /* There ought to be some way to do this without looping...  */
1837
          i = 0;
1838
          while ((n = alloc_ffs (alloc_word)) != 0)
1839
            {
1840
              /* Extend the current state for n - 1 bits.  We can't
1841
                 shift alloc_word by n, even though it isn't used in the
1842
                 loop, in case only the highest bit was set.  */
1843
              alloc_word >>= n - 1;
1844
              mark_word >>= n - 1;
1845
              object += BYTES_PER_MARK_BIT * (n - 1);
1846
 
1847
              if (mark_word & 1)
1848
                {
1849
                  if (last_free)
1850
                    {
1851
                      VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (last_free,
1852
                                                                     object
1853
                                                                     - last_free));
1854
                      poison_region (last_free, object - last_free);
1855
                      free_chunk (last_free, object - last_free, zone);
1856
                      last_free = NULL;
1857
                    }
1858
                  else
1859
                    allocated += object - last_object;
1860
                  last_object = object;
1861
                }
1862
              else
1863
                {
1864
                  if (last_free == NULL)
1865
                    {
1866
                      last_free = object;
1867
                      allocated += object - last_object;
1868
                    }
1869
                  else
1870
                    zone_clear_object_alloc_bit (sp, object);
1871
                }
1872
 
1873
              /* Shift to just after the alloc bit we handled.  */
1874
              alloc_word >>= 1;
1875
              mark_word >>= 1;
1876
              object += BYTES_PER_MARK_BIT;
1877
 
1878
              i += n;
1879
            }
1880
 
1881
          object += BYTES_PER_MARK_BIT * (8 * sizeof (alloc_type) - i);
1882
        }
1883
      while (object < end);
1884
 
1885
      if (nomarksinpage)
1886
        {
1887
          *spp = snext;
1888
#ifdef ENABLE_GC_CHECKING
1889
          VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (sp->common.page,
1890
                                                         SMALL_PAGE_SIZE));
1891
          /* Poison the page.  */
1892
          memset (sp->common.page, 0xb5, SMALL_PAGE_SIZE);
1893
#endif
1894
          free_small_page (sp);
1895
          continue;
1896
        }
1897
      else if (last_free)
1898
        {
1899
          VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (last_free,
1900
                                                         object - last_free));
1901
          poison_region (last_free, object - last_free);
1902
          free_chunk (last_free, object - last_free, zone);
1903
        }
1904
      else
1905
        allocated += object - last_object;
1906
 
1907
      spp = &sp->next;
1908
    }
1909
 
1910
  zone->allocated = allocated;
1911
}
1912
 
1913
/* mark-and-sweep routine for collecting a single zone.  NEED_MARKING
1914
   is true if we need to mark before sweeping, false if some other
1915
   zone collection has already performed marking for us.  Returns true
1916
   if we collected, false otherwise.  */
1917
 
1918
static bool
1919
ggc_collect_1 (struct alloc_zone *zone, bool need_marking)
1920
{
1921
#if 0
1922
  /* */
1923
  {
1924
    int i;
1925
    for (i = 0; i < NUM_FREE_BINS + 1; i++)
1926
      {
1927
        struct alloc_chunk *chunk;
1928
        int n, tot;
1929
 
1930
        n = 0;
1931
        tot = 0;
1932
        chunk = zone->free_chunks[i];
1933
        while (chunk)
1934
          {
1935
            n++;
1936
            tot += chunk->size;
1937
            chunk = chunk->next_free;
1938
          }
1939
        fprintf (stderr, "Bin %d: %d free chunks (%d bytes)\n",
1940
                 i, n, tot);
1941
      }
1942
  }
1943
  /* */
1944
#endif
1945
 
1946
  if (!quiet_flag)
1947
    fprintf (stderr, " {%s GC %luk -> ",
1948
             zone->name, (unsigned long) zone->allocated / 1024);
1949
 
1950
  /* Zero the total allocated bytes.  This will be recalculated in the
1951
     sweep phase.  */
1952
  zone->allocated = 0;
1953
 
1954
  /* Release the pages we freed the last time we collected, but didn't
1955
     reuse in the interim.  */
1956
  release_pages (zone);
1957
 
1958
  if (need_marking)
1959
    {
1960
      zone_allocate_marks ();
1961
      ggc_mark_roots ();
1962
#ifdef GATHER_STATISTICS
1963
      ggc_prune_overhead_list ();
1964
#endif
1965
    }
1966
 
1967
  sweep_pages (zone);
1968
  zone->was_collected = true;
1969
  zone->allocated_last_gc = zone->allocated;
1970
 
1971
  if (!quiet_flag)
1972
    fprintf (stderr, "%luk}", (unsigned long) zone->allocated / 1024);
1973
  return true;
1974
}
1975
 
1976
#ifdef GATHER_STATISTICS
1977
/* Calculate the average page survival rate in terms of number of
1978
   collections.  */
1979
 
1980
static float
1981
calculate_average_page_survival (struct alloc_zone *zone)
1982
{
1983
  float count = 0.0;
1984
  float survival = 0.0;
1985
  struct small_page_entry *p;
1986
  struct large_page_entry *lp;
1987
  for (p = zone->pages; p; p = p->next)
1988
    {
1989
      count += 1.0;
1990
      survival += p->common.survived;
1991
    }
1992
  for (lp = zone->large_pages; lp; lp = lp->next)
1993
    {
1994
      count += 1.0;
1995
      survival += lp->common.survived;
1996
    }
1997
  return survival/count;
1998
}
1999
#endif
2000
 
2001
/* Top level collection routine.  */
2002
 
2003
void
2004
ggc_collect (void)
2005
{
2006
  struct alloc_zone *zone;
2007
  bool marked = false;
2008
 
2009
  timevar_push (TV_GC);
2010
 
2011
  if (!ggc_force_collect)
2012
    {
2013
      float allocated_last_gc = 0, allocated = 0, min_expand;
2014
 
2015
      for (zone = G.zones; zone; zone = zone->next_zone)
2016
        {
2017
          allocated_last_gc += zone->allocated_last_gc;
2018
          allocated += zone->allocated;
2019
        }
2020
 
2021
      allocated_last_gc =
2022
        MAX (allocated_last_gc,
2023
             (size_t) PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
2024
      min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
2025
 
2026
      if (allocated < allocated_last_gc + min_expand)
2027
        {
2028
          timevar_pop (TV_GC);
2029
          return;
2030
        }
2031
    }
2032
 
2033
  invoke_plugin_callbacks (PLUGIN_GGC_START, NULL);
2034
 
2035
  /* Start by possibly collecting the main zone.  */
2036
  main_zone.was_collected = false;
2037
  marked |= ggc_collect_1 (&main_zone, true);
2038
 
2039
  /* In order to keep the number of collections down, we don't
2040
     collect other zones unless we are collecting the main zone.  This
2041
     gives us roughly the same number of collections as we used to
2042
     have with the old gc.  The number of collection is important
2043
     because our main slowdown (according to profiling) is now in
2044
     marking.  So if we mark twice as often as we used to, we'll be
2045
     twice as slow.  Hopefully we'll avoid this cost when we mark
2046
     zone-at-a-time.  */
2047
  /* NOTE drow/2004-07-28: We now always collect the main zone, but
2048
     keep this code in case the heuristics are further refined.  */
2049
 
2050
  if (main_zone.was_collected)
2051
    {
2052
      struct alloc_zone *zone;
2053
 
2054
      for (zone = main_zone.next_zone; zone; zone = zone->next_zone)
2055
        {
2056
          zone->was_collected = false;
2057
          marked |= ggc_collect_1 (zone, !marked);
2058
        }
2059
    }
2060
 
2061
#ifdef GATHER_STATISTICS
2062
  /* Print page survival stats, if someone wants them.  */
2063
  if (GGC_DEBUG_LEVEL >= 2)
2064
    {
2065
      for (zone = G.zones; zone; zone = zone->next_zone)
2066
        {
2067
          if (zone->was_collected)
2068
            {
2069
              float f = calculate_average_page_survival (zone);
2070
              printf ("Average page survival in zone `%s' is %f\n",
2071
                      zone->name, f);
2072
            }
2073
        }
2074
    }
2075
#endif
2076
 
2077
  if (marked)
2078
    zone_free_marks ();
2079
 
2080
  /* Free dead zones.  */
2081
  for (zone = G.zones; zone && zone->next_zone; zone = zone->next_zone)
2082
    {
2083
      if (zone->next_zone->dead)
2084
        {
2085
          struct alloc_zone *dead_zone = zone->next_zone;
2086
 
2087
          printf ("Zone `%s' is dead and will be freed.\n", dead_zone->name);
2088
 
2089
          /* The zone must be empty.  */
2090
          gcc_assert (!dead_zone->allocated);
2091
 
2092
          /* Unchain the dead zone, release all its pages and free it.  */
2093
          zone->next_zone = zone->next_zone->next_zone;
2094
          release_pages (dead_zone);
2095
          free (dead_zone);
2096
        }
2097
    }
2098
 
2099
  invoke_plugin_callbacks (PLUGIN_GGC_END, NULL);
2100
 
2101
  timevar_pop (TV_GC);
2102
}
2103
 
2104
/* Print allocation statistics.  */
2105
#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
2106
                  ? (x) \
2107
                  : ((x) < 1024*1024*10 \
2108
                     ? (x) / 1024 \
2109
                     : (x) / (1024*1024))))
2110
#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
2111
 
2112
void
2113
ggc_print_statistics (void)
2114
{
2115
  struct alloc_zone *zone;
2116
  struct ggc_statistics stats;
2117
  size_t total_overhead = 0, total_allocated = 0, total_bytes_mapped = 0;
2118
  size_t pte_overhead, i;
2119
 
2120
  /* Clear the statistics.  */
2121
  memset (&stats, 0, sizeof (stats));
2122
 
2123
  /* Make sure collection will really occur.  */
2124
  ggc_force_collect = true;
2125
 
2126
  /* Collect and print the statistics common across collectors.  */
2127
  ggc_print_common_statistics (stderr, &stats);
2128
 
2129
  ggc_force_collect = false;
2130
 
2131
  /* Release free pages so that we will not count the bytes allocated
2132
     there as part of the total allocated memory.  */
2133
  for (zone = G.zones; zone; zone = zone->next_zone)
2134
    release_pages (zone);
2135
 
2136
  /* Collect some information about the various sizes of
2137
     allocation.  */
2138
  fprintf (stderr,
2139
           "Memory still allocated at the end of the compilation process\n");
2140
 
2141
  fprintf (stderr, "%20s %10s  %10s  %10s\n",
2142
           "Zone", "Allocated", "Used", "Overhead");
2143
  for (zone = G.zones; zone; zone = zone->next_zone)
2144
    {
2145
      struct large_page_entry *large_page;
2146
      size_t overhead, allocated, in_use;
2147
 
2148
      /* Skip empty zones.  */
2149
      if (!zone->pages && !zone->large_pages)
2150
        continue;
2151
 
2152
      allocated = in_use = 0;
2153
 
2154
      overhead = sizeof (struct alloc_zone);
2155
 
2156
      for (large_page = zone->large_pages; large_page != NULL;
2157
           large_page = large_page->next)
2158
        {
2159
          allocated += large_page->bytes;
2160
          in_use += large_page->bytes;
2161
          overhead += sizeof (struct large_page_entry);
2162
        }
2163
 
2164
      /* There's no easy way to walk through the small pages finding
2165
         used and unused objects.  Instead, add all the pages, and
2166
         subtract out the free list.  */
2167
 
2168
      allocated += GGC_PAGE_SIZE * zone->n_small_pages;
2169
      in_use += GGC_PAGE_SIZE * zone->n_small_pages;
2170
      overhead += G.small_page_overhead * zone->n_small_pages;
2171
 
2172
      for (i = 0; i <= NUM_FREE_BINS; i++)
2173
        {
2174
          struct alloc_chunk *chunk = zone->free_chunks[i];
2175
          while (chunk)
2176
            {
2177
              in_use -= ggc_get_size (chunk);
2178
              chunk = chunk->next_free;
2179
            }
2180
        }
2181
 
2182
      fprintf (stderr, "%20s %10lu%c %10lu%c %10lu%c\n",
2183
               zone->name,
2184
               SCALE (allocated), LABEL (allocated),
2185
               SCALE (in_use), LABEL (in_use),
2186
               SCALE (overhead), LABEL (overhead));
2187
 
2188
      gcc_assert (in_use == zone->allocated);
2189
 
2190
      total_overhead += overhead;
2191
      total_allocated += zone->allocated;
2192
      total_bytes_mapped += zone->bytes_mapped;
2193
    }
2194
 
2195
  /* Count the size of the page table as best we can.  */
2196
#if HOST_BITS_PER_PTR <= 32
2197
  pte_overhead = sizeof (G.lookup);
2198
  for (i = 0; i < PAGE_L1_SIZE; i++)
2199
    if (G.lookup[i])
2200
      pte_overhead += PAGE_L2_SIZE * sizeof (struct page_entry *);
2201
#else
2202
  {
2203
    page_table table = G.lookup;
2204
    pte_overhead = 0;
2205
    while (table)
2206
      {
2207
        pte_overhead += sizeof (*table);
2208
        for (i = 0; i < PAGE_L1_SIZE; i++)
2209
          if (table->table[i])
2210
            pte_overhead += PAGE_L2_SIZE * sizeof (struct page_entry *);
2211
        table = table->next;
2212
      }
2213
  }
2214
#endif
2215
  fprintf (stderr, "%20s %11s %11s %10lu%c\n", "Page Table",
2216
           "", "", SCALE (pte_overhead), LABEL (pte_overhead));
2217
  total_overhead += pte_overhead;
2218
 
2219
  fprintf (stderr, "%20s %10lu%c %10lu%c %10lu%c\n", "Total",
2220
           SCALE (total_bytes_mapped), LABEL (total_bytes_mapped),
2221
           SCALE (total_allocated), LABEL(total_allocated),
2222
           SCALE (total_overhead), LABEL (total_overhead));
2223
 
2224
#ifdef GATHER_STATISTICS
2225
  {
2226
    unsigned long long all_overhead = 0, all_allocated = 0;
2227
    unsigned long long all_overhead_under32 = 0, all_allocated_under32 = 0;
2228
    unsigned long long all_overhead_under64 = 0, all_allocated_under64 = 0;
2229
    unsigned long long all_overhead_under128 = 0, all_allocated_under128 = 0;
2230
 
2231
    fprintf (stderr, "\nTotal allocations and overheads during the compilation process\n");
2232
 
2233
    for (zone = G.zones; zone; zone = zone->next_zone)
2234
      {
2235
        all_overhead += zone->stats.total_overhead;
2236
        all_allocated += zone->stats.total_allocated;
2237
 
2238
        all_allocated_under32 += zone->stats.total_allocated_under32;
2239
        all_overhead_under32 += zone->stats.total_overhead_under32;
2240
 
2241
        all_allocated_under64 += zone->stats.total_allocated_under64;
2242
        all_overhead_under64 += zone->stats.total_overhead_under64;
2243
 
2244
        all_allocated_under128 += zone->stats.total_allocated_under128;
2245
        all_overhead_under128 += zone->stats.total_overhead_under128;
2246
 
2247
        fprintf (stderr, "%20s:                  %10lld\n",
2248
                 zone->name, zone->stats.total_allocated);
2249
      }
2250
 
2251
    fprintf (stderr, "\n");
2252
 
2253
    fprintf (stderr, "Total Overhead:                        %10lld\n",
2254
             all_overhead);
2255
    fprintf (stderr, "Total Allocated:                       %10lld\n",
2256
             all_allocated);
2257
 
2258
    fprintf (stderr, "Total Overhead  under  32B:            %10lld\n",
2259
             all_overhead_under32);
2260
    fprintf (stderr, "Total Allocated under  32B:            %10lld\n",
2261
             all_allocated_under32);
2262
    fprintf (stderr, "Total Overhead  under  64B:            %10lld\n",
2263
             all_overhead_under64);
2264
    fprintf (stderr, "Total Allocated under  64B:            %10lld\n",
2265
             all_allocated_under64);
2266
    fprintf (stderr, "Total Overhead  under 128B:            %10lld\n",
2267
             all_overhead_under128);
2268
    fprintf (stderr, "Total Allocated under 128B:            %10lld\n",
2269
             all_allocated_under128);
2270
  }
2271
#endif
2272
}
2273
 
2274
/* Precompiled header support.  */
2275
 
2276
/* For precompiled headers, we sort objects based on their type.  We
2277
   also sort various objects into their own buckets; currently this
2278
   covers strings and IDENTIFIER_NODE trees.  The choices of how
2279
   to sort buckets have not yet been tuned.  */
2280
 
2281
#define NUM_PCH_BUCKETS         (gt_types_enum_last + 3)
2282
 
2283
#define OTHER_BUCKET            (gt_types_enum_last + 0)
2284
#define IDENTIFIER_BUCKET       (gt_types_enum_last + 1)
2285
#define STRING_BUCKET           (gt_types_enum_last + 2)
2286
 
2287
struct ggc_pch_ondisk
2288
{
2289
  size_t total;
2290
  size_t type_totals[NUM_PCH_BUCKETS];
2291
};
2292
 
2293
struct ggc_pch_data
2294
{
2295
  struct ggc_pch_ondisk d;
2296
  size_t base;
2297
  size_t orig_base;
2298
  size_t alloc_size;
2299
  alloc_type *alloc_bits;
2300
  size_t type_bases[NUM_PCH_BUCKETS];
2301
  size_t start_offset;
2302
};
2303
 
2304
/* Initialize the PCH data structure.  */
2305
 
2306
struct ggc_pch_data *
2307
init_ggc_pch (void)
2308
{
2309
  return XCNEW (struct ggc_pch_data);
2310
}
2311
 
2312
/* Return which of the page-aligned buckets the object at X, with type
2313
   TYPE, should be sorted into in the PCH.  Strings will have
2314
   IS_STRING set and TYPE will be gt_types_enum_last.  Other objects
2315
   of unknown type will also have TYPE equal to gt_types_enum_last.  */
2316
 
2317
static int
2318
pch_bucket (void *x, enum gt_types_enum type,
2319
            bool is_string)
2320
{
2321
  /* Sort identifiers into their own bucket, to improve locality
2322
     when searching the identifier hash table.  */
2323
  if (type == gt_ggc_e_14lang_tree_node
2324
      && TREE_CODE ((tree) x) == IDENTIFIER_NODE)
2325
    return IDENTIFIER_BUCKET;
2326
  else if (type == gt_types_enum_last)
2327
    {
2328
      if (is_string)
2329
        return STRING_BUCKET;
2330
      return OTHER_BUCKET;
2331
    }
2332
  return type;
2333
}
2334
 
2335
/* Add the size of object X to the size of the PCH data.  */
2336
 
2337
void
2338
ggc_pch_count_object (struct ggc_pch_data *d, void *x ATTRIBUTE_UNUSED,
2339
                      size_t size, bool is_string, enum gt_types_enum type)
2340
{
2341
  /* NOTE: Right now we don't need to align up the size of any objects.
2342
     Strings can be unaligned, and everything else is allocated to a
2343
     MAX_ALIGNMENT boundary already.  */
2344
 
2345
  d->d.type_totals[pch_bucket (x, type, is_string)] += size;
2346
}
2347
 
2348
/* Return the total size of the PCH data.  */
2349
 
2350
size_t
2351
ggc_pch_total_size (struct ggc_pch_data *d)
2352
{
2353
  enum gt_types_enum i;
2354
  size_t alloc_size, total_size;
2355
 
2356
  total_size = 0;
2357
  for (i = 0; i < NUM_PCH_BUCKETS; i++)
2358
    {
2359
      d->d.type_totals[i] = ROUND_UP (d->d.type_totals[i], GGC_PAGE_SIZE);
2360
      total_size += d->d.type_totals[i];
2361
    }
2362
  d->d.total = total_size;
2363
 
2364
  /* Include the size of the allocation bitmap.  */
2365
  alloc_size = CEIL (d->d.total, BYTES_PER_ALLOC_BIT * 8);
2366
  alloc_size = ROUND_UP (alloc_size, MAX_ALIGNMENT);
2367
  d->alloc_size = alloc_size;
2368
 
2369
  return d->d.total + alloc_size;
2370
}
2371
 
2372
/* Set the base address for the objects in the PCH file.  */
2373
 
2374
void
2375
ggc_pch_this_base (struct ggc_pch_data *d, void *base_)
2376
{
2377
  int i;
2378
  size_t base = (size_t) base_;
2379
 
2380
  d->base = d->orig_base = base;
2381
  for (i = 0; i < NUM_PCH_BUCKETS; i++)
2382
    {
2383
      d->type_bases[i] = base;
2384
      base += d->d.type_totals[i];
2385
    }
2386
 
2387
  if (d->alloc_bits == NULL)
2388
    d->alloc_bits = XCNEWVAR (alloc_type, d->alloc_size);
2389
}
2390
 
2391
/* Allocate a place for object X of size SIZE in the PCH file.  */
2392
 
2393
char *
2394
ggc_pch_alloc_object (struct ggc_pch_data *d, void *x,
2395
                      size_t size, bool is_string,
2396
                      enum gt_types_enum type)
2397
{
2398
  size_t alloc_word, alloc_bit;
2399
  char *result;
2400
  int bucket = pch_bucket (x, type, is_string);
2401
 
2402
  /* Record the start of the object in the allocation bitmap.  We
2403
     can't assert that the allocation bit is previously clear, because
2404
     strings may violate the invariant that they are at least
2405
     BYTES_PER_ALLOC_BIT long.  This is harmless - ggc_get_size
2406
     should not be called for strings.  */
2407
  alloc_word = ((d->type_bases[bucket] - d->orig_base)
2408
                / (8 * sizeof (alloc_type) * BYTES_PER_ALLOC_BIT));
2409
  alloc_bit = ((d->type_bases[bucket] - d->orig_base)
2410
               / BYTES_PER_ALLOC_BIT) % (8 * sizeof (alloc_type));
2411
  d->alloc_bits[alloc_word] |= 1L << alloc_bit;
2412
 
2413
  /* Place the object at the current pointer for this bucket.  */
2414
  result = (char *) d->type_bases[bucket];
2415
  d->type_bases[bucket] += size;
2416
  return result;
2417
}
2418
 
2419
/* Prepare to write out the PCH data to file F.  */
2420
 
2421
void
2422
ggc_pch_prepare_write (struct ggc_pch_data *d,
2423
                       FILE *f)
2424
{
2425
  /* We seek around a lot while writing.  Record where the end
2426
     of the padding in the PCH file is, so that we can
2427
     locate each object's offset.  */
2428
  d->start_offset = ftell (f);
2429
}
2430
 
2431
/* Write out object X of SIZE to file F.  */
2432
 
2433
void
2434
ggc_pch_write_object (struct ggc_pch_data *d,
2435
                      FILE *f, void *x, void *newx,
2436
                      size_t size, bool is_string ATTRIBUTE_UNUSED)
2437
{
2438
  if (fseek (f, (size_t) newx - d->orig_base + d->start_offset, SEEK_SET) != 0)
2439
    fatal_error ("can't seek PCH file: %m");
2440
 
2441
  if (fwrite (x, size, 1, f) != 1)
2442
    fatal_error ("can't write PCH file: %m");
2443
}
2444
 
2445
void
2446
ggc_pch_finish (struct ggc_pch_data *d, FILE *f)
2447
{
2448
  /* Write out the allocation bitmap.  */
2449
  if (fseek (f, d->start_offset + d->d.total, SEEK_SET) != 0)
2450
    fatal_error ("can't seek PCH file: %m");
2451
 
2452
  if (fwrite (d->alloc_bits, d->alloc_size, 1, f) != 1)
2453
    fatal_error ("can't write PCH file: %m");
2454
 
2455
  /* Done with the PCH, so write out our footer.  */
2456
  if (fwrite (&d->d, sizeof (d->d), 1, f) != 1)
2457
    fatal_error ("can't write PCH file: %m");
2458
 
2459
  free (d->alloc_bits);
2460
  free (d);
2461
}
2462
 
2463
/* The PCH file from F has been mapped at ADDR.  Read in any
2464
   additional data from the file and set up the GC state.  */
2465
 
2466
void
2467
ggc_pch_read (FILE *f, void *addr)
2468
{
2469
  struct ggc_pch_ondisk d;
2470
  size_t alloc_size;
2471
  struct alloc_zone *zone;
2472
  struct page_entry *pch_page;
2473
  char *p;
2474
 
2475
  if (fread (&d, sizeof (d), 1, f) != 1)
2476
    fatal_error ("can't read PCH file: %m");
2477
 
2478
  alloc_size = CEIL (d.total, BYTES_PER_ALLOC_BIT * 8);
2479
  alloc_size = ROUND_UP (alloc_size, MAX_ALIGNMENT);
2480
 
2481
  pch_zone.bytes = d.total;
2482
  pch_zone.alloc_bits = (alloc_type *) ((char *) addr + pch_zone.bytes);
2483
  pch_zone.page = (char *) addr;
2484
  pch_zone.end = (char *) pch_zone.alloc_bits;
2485
 
2486
  /* We've just read in a PCH file.  So, every object that used to be
2487
     allocated is now free.  */
2488
  for (zone = G.zones; zone; zone = zone->next_zone)
2489
    {
2490
      struct small_page_entry *page, *next_page;
2491
      struct large_page_entry *large_page, *next_large_page;
2492
 
2493
      zone->allocated = 0;
2494
 
2495
      /* Clear the zone's free chunk list.  */
2496
      memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
2497
      zone->high_free_bin = 0;
2498
      zone->cached_free = NULL;
2499
      zone->cached_free_size = 0;
2500
 
2501
      /* Move all the small pages onto the free list.  */
2502
      for (page = zone->pages; page != NULL; page = next_page)
2503
        {
2504
          next_page = page->next;
2505
          memset (page->alloc_bits, 0,
2506
                  G.small_page_overhead - PAGE_OVERHEAD);
2507
          free_small_page (page);
2508
        }
2509
 
2510
      /* Discard all the large pages.  */
2511
      for (large_page = zone->large_pages; large_page != NULL;
2512
           large_page = next_large_page)
2513
        {
2514
          next_large_page = large_page->next;
2515
          free_large_page (large_page);
2516
        }
2517
 
2518
      zone->pages = NULL;
2519
      zone->large_pages = NULL;
2520
    }
2521
 
2522
  /* Allocate the dummy page entry for the PCH, and set all pages
2523
     mapped into the PCH to reference it.  */
2524
  pch_page = XCNEW (struct page_entry);
2525
  pch_page->page = pch_zone.page;
2526
  pch_page->pch_p = true;
2527
 
2528
  for (p = pch_zone.page; p < pch_zone.end; p += GGC_PAGE_SIZE)
2529
    set_page_table_entry (p, pch_page);
2530
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.