ggc-page.c File Reference

Data Structures
struct	max_alignment
struct	page_entry
struct	page_group
struct	page_table_chain
struct	free_object
struct	globals
struct	ggc_pch_ondisk
struct	ggc_pch_data

Typedefs
typedef struct page_entry	page_entry
typedef struct page_group	page_group
typedef page_entry **	page_table [PAGE_L1_SIZE]

Functions
static int	ggc_allocated_p (const void *)
static page_entry *	lookup_page_table_entry (const void *)
static void	set_page_table_entry (void *, page_entry *)
static char *	alloc_anon (char *, size_t, bool check)
static size_t	page_group_index (char *, char *)
static void	set_page_group_in_use (page_group *, char *)
static void	clear_page_group_in_use (page_group *, char *)
static struct page_entry *	alloc_page (unsigned)
static void	free_page (struct page_entry *)
static void	release_pages (void)
static void	clear_marks (void)
static void	sweep_pages (void)
static void	ggc_recalculate_in_use_p (page_entry *)
static void	compute_inverse (unsigned)
static void	adjust_depth (void)
static void	move_ptes_to_front (int, int)
void	debug_print_page_list (int)
static void	push_depth (unsigned int)
static void	push_by_depth (page_entry *, unsigned long *)
static void	push_depth ()
static void	push_by_depth ()
static int	ggc_allocated_p ()
static page_entry *	lookup_page_table_entry ()
static void	set_page_table_entry ()
DEBUG_FUNCTION void	debug_print_page_list ()
static char *	alloc_anon ()
static size_t	page_group_index ()
static void	set_page_group_in_use ()
static void	clear_page_group_in_use ()
static struct page_entry *	alloc_page ()
static void	free_page ()
static void	ggc_round_alloc_size_1 (size_t requested_size, size_t *size_order, size_t *alloced_size)
size_t	ggc_round_alloc_size ()
void *	ggc_internal_alloc_stat ()
void	gt_ggc_m_S ()
void	gt_ggc_mx ()
int	ggc_set_mark ()
int	ggc_marked_p ()
size_t	ggc_get_size ()
void	ggc_free ()
static void	compute_inverse ()
void	init_ggc ()
static void	ggc_recalculate_in_use_p ()
static void	poison_pages ()
static void	validate_free_objects ()
void	ggc_collect ()
void	ggc_print_statistics ()
struct ggc_pch_data *	init_ggc_pch ()
void	ggc_pch_count_object (struct ggc_pch_data *d, void *x, size_t size, bool is_string)
size_t	ggc_pch_total_size ()
void	ggc_pch_this_base ()
char *	ggc_pch_alloc_object (struct ggc_pch_data *d, void *x, size_t size, bool is_string)
void	ggc_pch_prepare_write (struct ggc_pch_data *d, FILE *f)
void	ggc_pch_write_object (struct ggc_pch_data *d, FILE *f, void *x, void *newx, size_t size, bool is_string)
void	ggc_pch_finish ()
static void	move_ptes_to_front ()
void	ggc_pch_read ()

Variables
static const size_t	extra_order_size_table []
static unsigned	objects_per_page_table [NUM_ORDERS]
static size_t	object_size_table [NUM_ORDERS]
struct {
size_t   mult
unsigned int   shift
}	inverse_table [NUM_ORDERS]
static struct globals	G
static unsigned char	size_lookup [NUM_SIZE_LOOKUP]

---

Typedef Documentation

typedef struct page_entry page_entry

A page_entry records the status of an allocation page.  This
   structure is dynamically sized to fit the bitmap in_use_p.   

typedef struct page_group page_group

A page_group describes a large allocation from malloc, from which
   we parcel out aligned pages.   

typedef struct page_table_chain * page_table

On 32-bit hosts, we use a two level page table, as pictured above.   

On 64-bit hosts, we use the same two level page tables plus a linked
   list that disambiguates the top 32-bits.  There will almost always be
   exactly one entry in the list.   

---

Function Documentation

static void adjust_depth ( )

inlinestatic

Adjust the size of G.depth so that no index greater than the one
   used by the top of the G.by_depth is used.   

References globals::by_depth, globals::by_depth_in_use, page_entry::context_depth, globals::depth_in_use, and G.

Referenced by free_page().

static char* alloc_anon ( char *  , size_t  , bool  check  )

static

Referenced by alloc_page(), and init_ggc().

static char* alloc_anon ( )

inlinestatic

Allocate SIZE bytes of anonymous memory, preferably near PREF,
   (if non-null).  The ifdef structure here is intended to cause a
   compile error unless exactly one of the HAVE_* is defined.   

References globals::bytes_mapped, globals::dev_zero_fd, G, page_entry::page, and pref.

static struct page_entry* alloc_page ( unsigned  )

staticread

Referenced by ggc_internal_alloc_stat().

static struct page_entry* alloc_page ( )

staticread

Allocate a new page for allocating objects of size 2^ORDER,
   and return an entry for it.  The entry is not added to the
   appropriate page_table list.   

References alloc_anon(), page_group::alloc_size, page_group::allocation, page_entry::bytes, globals::bytes_mapped, page_entry::context_depth, globals::context_depth, globals::context_depth_allocations, globals::debug_file, page_entry::discarded, free(), globals::free_pages, G, page_entry::group, HOST_BITS_PER_LONG, page_group::in_use, page_entry::in_use_p, globals::lg_pagesize, memset(), page_entry::next, page_group::next, page_entry::next_bit_hint, page_entry::num_free_objects, page_entry::order, order, page_entry::page, globals::page_groups, globals::pagesize, set_page_group_in_use(), and set_page_table_entry().

static void clear_marks ( )

static

Unmark all objects.   

References page_entry::context_depth, globals::context_depth, G, HOST_BITS_PER_LONG, page_entry::in_use_p, memcpy(), memset(), page_entry::next, page_entry::num_free_objects, order, page_entry::page, globals::pages, and globals::pagesize.

Referenced by ggc_collect(), and ggc_pch_read().

static void clear_page_group_in_use ( page_group *  , char *    )

static

Referenced by free_page().

static void clear_page_group_in_use ( )

inlinestatic

References page_group::allocation, page_group::in_use, and page_group_index().

static void compute_inverse ( unsigned  )

static

Referenced by init_ggc().

static void compute_inverse ( )

static

Subroutine of init_ggc which computes the pair of numbers used to
   perform division by OBJECT_SIZE (order) and fills in inverse_table[].

   This algorithm is taken from Granlund and Montgomery's paper
   "Division by Invariant Integers using Multiplication"
   (Proc. SIGPLAN PLDI, 1994), section 9 (Exact division by
   constants).   

References inv().

void debug_print_page_list

(

int

)

DEBUG_FUNCTION void debug_print_page_list

(

)

Prints the page-entry for object size ORDER, for debugging.   

References page_entry::context_depth, G, page_entry::next, page_entry::num_free_objects, order, globals::page_tails, and globals::pages.

static void free_page ( struct page_entry *  )

static

Referenced by sweep_pages().

static void free_page ( )

static

For a page that is no longer needed, put it on the free page list.   

References adjust_depth(), globals::by_depth, globals::by_depth_in_use, page_entry::bytes, clear_page_group_in_use(), page_entry::context_depth, globals::debug_file, globals::free_pages, G, page_entry::group, page_entry::index_by_depth, page_entry::next, page_entry::page, globals::save_in_use, and set_page_table_entry().

static int ggc_allocated_p ( const void *  )

static

Referenced by gt_ggc_m_S().

static int ggc_allocated_p ( )

inlinestatic

Returns nonzero if P was allocated in GC'able memory.   

References G, globals::lookup, and table.

void ggc_collect

(

void

)

Top level mark-and-sweep routine.   

References globals::allocated, globals::allocated_last_gc, clear_marks(), globals::context_depth, globals::context_depth_collections, globals::debug_file, G, ggc_force_collect, ggc_mark_roots(), ggc_prune_overhead_list(), invoke_plugin_callbacks(), poison_pages(), release_pages(), sweep_pages(), timevar_pop(), timevar_push(), and validate_free_objects().

Referenced by analyze_functions(), cgraph_finalize_function(), do_per_function(), do_per_function_toporder(), dump_ggc_loc_statistics(), execute_one_ipa_transform_pass(), execute_one_pass(), expand_function(), and ggc_print_common_statistics().

void ggc_free

(

)

Release the memory for object P.   

References globals::allocated, globals::debug_file, globals::free_object_list, G, ggc_free_overhead(), HOST_BITS_PER_LONG, page_entry::in_use_p, lookup_page_table_entry(), memset(), page_entry::next, free_object::next, page_entry::next_bit_hint, page_entry::num_free_objects, free_object::object, page_entry::order, order, page_entry::page, globals::page_tails, globals::pages, and page_entry::prev.

size_t ggc_get_size

(

)

Return the size of the gc-able object P.   

References lookup_page_table_entry(), and page_entry::order.

void* ggc_internal_alloc_stat

(

)

Allocate a chunk of memory of SIZE bytes.  Its contents are undefined.   

References alloc_page(), globals::allocated, globals::by_depth_in_use, page_entry::context_depth, globals::debug_file, globals::depth_in_use, G, ggc_record_overhead(), ggc_round_alloc_size_1(), HOST_BITS_PER_LONG, page_entry::in_use_p, page_entry::index_by_depth, memset(), page_entry::next, page_entry::next_bit_hint, page_entry::num_free_objects, order, page_entry::page, globals::page_tails, globals::pages, page_entry::prev, push_by_depth(), push_depth(), globals::stats, timevar_ggc_mem_total, globals::total_allocated, globals::total_allocated_per_order, globals::total_allocated_under128, globals::total_allocated_under32, globals::total_allocated_under64, globals::total_overhead, globals::total_overhead_per_order, globals::total_overhead_under128, globals::total_overhead_under32, and globals::total_overhead_under64.

int ggc_marked_p

(

)

Return 1 if P has been marked, zero otherwise.
   P must have been allocated by the GC allocator; it mustn't point to
   static objects, stack variables, or memory allocated with malloc.   

References HOST_BITS_PER_LONG, page_entry::in_use_p, lookup_page_table_entry(), page_entry::order, and page_entry::page.

Referenced by ggc_prune_ptr(), maybe_delete_ident(), tree_map_base_marked_p(), and type_hash_marked_p().

char* ggc_pch_alloc_object	(	struct ggc_pch_data *	,
		void *	,
		size_t	,
		bool
	)

Assuming that the objects really do end up at the address
   passed to ggc_pch_this_base, return the address of this object.
   The bool argument should be true if the object is a string.   

References ggc_pch_data::base, and order.

Referenced by ggc_call_alloc().

void ggc_pch_count_object	(	struct ggc_pch_data *	,
		void *	,
		size_t	,
		bool
	)

The second parameter and third parameters give the address and size
   of an object.  Update the ggc_pch_data structure with as much of
   that information as is necessary. The bool argument should be true
   if the object is a string.   

References ggc_pch_data::d, order, and ggc_pch_ondisk::totals.

Referenced by ggc_call_count().

void ggc_pch_finish

(

)

References ggc_pch_data::d, fatal_error(), and free().

void ggc_pch_prepare_write	(	struct ggc_pch_data *	,
		FILE *
	)

Write out any initial information required.   

Referenced by gt_pch_save().

void ggc_pch_read

(

)

References globals::allocated, globals::allocated_last_gc, globals::by_depth_in_use, page_entry::bytes, clear_marks(), page_entry::context_depth, globals::context_depth, fatal_error(), G, HOST_BITS_PER_LONG, page_entry::in_use_p, move_ptes_to_front(), page_entry::next, page_entry::num_free_objects, page_entry::order, page_entry::page, globals::page_tails, globals::pages, globals::pagesize, poison_pages(), push_by_depth(), set_page_table_entry(), ggc_pch_ondisk::totals, and validate_free_objects().

void ggc_pch_this_base

(

)

References ggc_pch_data::base, ggc_pch_data::d, and ggc_pch_ondisk::totals.

size_t ggc_pch_total_size

(

)

References ggc_pch_data::d, and ggc_pch_ondisk::totals.

void ggc_pch_write_object	(	struct ggc_pch_data *	,
		FILE *	,
		void *	,
		void *	,
		size_t	,
		bool
	)

Write out this object, including any padding.  The last argument should be
   true if the object is a string.   

References ggc_pch_data::d, fatal_error(), G, order, globals::pagesize, ggc_pch_ondisk::totals, and ggc_pch_data::written.

Referenced by gt_pch_save().

void ggc_print_statistics

(

void

)

Statistics.   

Print allocation statistics.   

References globals::allocated, globals::allocated_last_gc, page_entry::bytes, globals::bytes_mapped, G, ggc_print_common_statistics(), HOST_LONG_LONG_FORMAT, memset(), page_entry::next, page_entry::num_free_objects, globals::pages, release_pages(), globals::stats, globals::total_allocated, globals::total_allocated_per_order, globals::total_allocated_under128, globals::total_allocated_under32, globals::total_allocated_under64, globals::total_overhead, globals::total_overhead_per_order, globals::total_overhead_under128, globals::total_overhead_under32, and globals::total_overhead_under64.

Referenced by dump_memory_report().

static void ggc_recalculate_in_use_p ( page_entry *  )

static

Referenced by sweep_pages().

static void ggc_recalculate_in_use_p ( )

static

Merge the SAVE_IN_USE_P and IN_USE_P arrays in P so that IN_USE_P
   reflects reality.  Recalculate NUM_FREE_OBJECTS as well.   

References page_entry::in_use_p, and page_entry::num_free_objects.

size_t ggc_round_alloc_size

(

)

For a given size of memory requested for allocation, return the
   actual size that is going to be allocated.   

References ggc_round_alloc_size_1().

static void ggc_round_alloc_size_1 ( size_t  requested_size, size_t *  size_order, size_t *  alloced_size  )

static

For a given size of memory requested for allocation, return the
   actual size that is going to be allocated, as well as the size
   order.   

References order.

Referenced by ggc_internal_alloc_stat(), and ggc_round_alloc_size().

int ggc_set_mark

(

)

If P is not marked, marks it and return false.  Otherwise return true.
   P must have been allocated by the GC allocator; it mustn't point to
   static objects, stack variables, or memory allocated with malloc.   

References globals::debug_file, G, HOST_BITS_PER_LONG, page_entry::in_use_p, lookup_page_table_entry(), page_entry::num_free_objects, page_entry::order, and page_entry::page.

Referenced by ggc_scan_cache_tab().

void gt_ggc_m_S

(

)

Mark function for strings.   

References globals::debug_file, G, ggc_allocated_p(), HOST_BITS_PER_LONG, page_entry::in_use_p, lookup_page_table_entry(), page_entry::num_free_objects, offset, page_entry::order, and page_entry::page.

Referenced by gt_ggc_mx().

void gt_ggc_mx

(

)

User-callable entry points for marking string X.   

References gt_ggc_m_S().

void init_ggc

(

void

)

Initialize the ggc-mmap allocator.   

References alloc_anon(), globals::by_depth, globals::by_depth_in_use, globals::by_depth_max, page_entry::bytes, compute_inverse(), globals::debug_file, globals::depth, globals::depth_in_use, globals::depth_max, globals::dev_zero_fd, exact_log2(), extra_order_size_table, globals::free_pages, G, getpagesize(), internal_error(), globals::lg_pagesize, page_entry::next, order, page_entry::page, globals::pagesize, and globals::save_in_use.

Referenced by general_init().

struct ggc_pch_data* init_ggc_pch ( void  )

read

Return a new ggc_pch_data structure.   

Referenced by gt_pch_save().

static page_entry* lookup_page_table_entry ( const void *  )

static

Referenced by ggc_free(), ggc_get_size(), ggc_marked_p(), ggc_set_mark(), gt_ggc_m_S(), and validate_free_objects().

static page_entry* lookup_page_table_entry ( )

inlinestatic

Traverse the page table and find the entry for a page.
   Die (probably) if the object wasn't allocated via GC.   

References G, globals::lookup, and table.

static void move_ptes_to_front ( int  , int    )

static

Referenced by ggc_pch_read().

static void move_ptes_to_front ( )

static

Move the PCH PTE entries just added to the end of by_depth, to the
   front.   

References globals::by_depth, globals::by_depth_in_use, globals::by_depth_max, free(), G, page_entry::index_by_depth, memcpy(), push_depth(), and globals::save_in_use.

static size_t page_group_index ( char *  , char *    )

static

Referenced by clear_page_group_in_use(), and set_page_group_in_use().

static size_t page_group_index ( )

inlinestatic

Compute the index for this page into the page group.   

References G, and globals::lg_pagesize.

static void poison_pages ( )

static

Clobber all free objects.   

References page_entry::context_depth, globals::context_depth, G, HOST_BITS_PER_LONG, page_entry::in_use_p, memset(), page_entry::next, order, page_entry::page, and globals::pages.

Referenced by ggc_collect(), and ggc_pch_read().

static void push_by_depth ( page_entry *  , unsigned long *    )

static

Referenced by ggc_internal_alloc_stat(), and ggc_pch_read().

static void push_by_depth ( )

inlinestatic

Push an entry onto G.by_depth and G.save_in_use.   

References globals::by_depth, globals::by_depth_in_use, globals::by_depth_max, G, and globals::save_in_use.

static void push_depth ( unsigned  int )

static

Referenced by ggc_internal_alloc_stat(), and move_ptes_to_front().

static void push_depth ( )

inlinestatic

Push an entry onto G.depth.   

References globals::depth, globals::depth_in_use, globals::depth_max, and G.

static void release_pages ( )

static

Release the free page cache to the system.   

References page_group::alloc_size, page_group::allocation, page_entry::bytes, globals::bytes_mapped, page_entry::discarded, free(), globals::free_pages, g, G, page_entry::group, page_group::in_use, len, page_entry::next, page_group::next, page_entry::page, globals::page_groups, globals::pagesize, and page_entry::prev.

Referenced by ggc_collect(), and ggc_print_statistics().

static void set_page_group_in_use ( page_group *  , char *    )

static

Referenced by alloc_page().

static void set_page_group_in_use ( )

inlinestatic

Set and clear the in_use bit for this page in the page group.   

References page_group::allocation, page_group::in_use, and page_group_index().

static void set_page_table_entry ( void *  , page_entry *    )

static

Referenced by alloc_page(), free_page(), and ggc_pch_read().

static void set_page_table_entry ( )

static

Set the page table entry for a page.   

References G, globals::lookup, and table.

static void sweep_pages ( )

static

Free all empty pages.  Partially empty pages need no attention
   because the `mark' bit doubles as an `unused' bit.   

References globals::allocated, page_entry::context_depth, globals::context_depth, free_page(), G, ggc_recalculate_in_use_p(), last, page_entry::next, page_entry::num_free_objects, order, globals::page_tails, globals::pages, and page_entry::prev.

Referenced by ggc_collect().

static void validate_free_objects ( )

static

Validate that the reportedly free objects actually are.   

References page_entry::context_depth, globals::context_depth, free(), globals::free_object_list, G, HOST_BITS_PER_LONG, page_entry::in_use_p, lookup_page_table_entry(), free_object::next, free_object::object, page_entry::order, and page_entry::page.

Referenced by ggc_collect(), and ggc_pch_read().

---

Variable Documentation

const size_t extra_order_size_table[]

static

Initial value:

 {
  
  MAX_ALIGNMENT * 3,
  MAX_ALIGNMENT * 5,
  MAX_ALIGNMENT * 6,
  MAX_ALIGNMENT * 7,
  MAX_ALIGNMENT * 9,
  MAX_ALIGNMENT * 10,
  MAX_ALIGNMENT * 11,
  MAX_ALIGNMENT * 12,
  MAX_ALIGNMENT * 13,
  MAX_ALIGNMENT * 14,
  MAX_ALIGNMENT * 15,
  sizeof (struct tree_decl_non_common),
  sizeof (struct tree_field_decl),
  sizeof (struct tree_parm_decl),
  sizeof (struct tree_var_decl),
  sizeof (struct tree_type_non_common),
  sizeof (struct function),
  sizeof (struct basic_block_def),
  sizeof (struct cgraph_node),
  sizeof (struct loop),
}

The Ith entry is the maximum size of an object to be stored in the
   Ith extra order.  Adding a new entry to this array is the *only*
   thing you need to do to add a new special allocation size.   

Referenced by init_ggc().

struct globals G

static

Referenced by adjust_depth(), alloc_anon(), alloc_page(), clear_marks(), debug_print_page_list(), free_page(), ggc_allocated_p(), ggc_collect(), ggc_free(), ggc_internal_alloc_stat(), ggc_pch_read(), ggc_pch_write_object(), ggc_print_statistics(), ggc_set_mark(), gt_ggc_m_S(), init_ggc(), lookup_page_table_entry(), move_ptes_to_front(), page_group_index(), poison_pages(), push_by_depth(), push_depth(), release_pages(), set_page_table_entry(), sweep_pages(), and validate_free_objects().

struct { ... } inverse_table[NUM_ORDERS]

The Ith entry is a pair of numbers (mult, shift) such that
   ((k * mult) >> shift) mod 2^32 == (k / OBJECT_SIZE(I)) mod 2^32,
   for all k evenly divisible by OBJECT_SIZE(I).   

size_t mult

Referenced by categorize_ctor_elements_1(), coalesce_cost_edge(), force_expr_to_var_cost(), setup_allocno_priorities(), and update_conflict_hard_regno_costs().

size_t object_size_table[NUM_ORDERS]

static

The Ith entry is the size of an object on a page of order I.   

unsigned objects_per_page_table[NUM_ORDERS]

static

The Ith entry is the number of objects on a page or order I.   

unsigned int shift

Referenced by adjust_address_1(), bit_value_binop_1(), bp_unpack_var_len_int(), bp_unpack_var_len_unsigned(), canonicalize_address(), const_rtx_hash_1(), cse_insn(), do_jump(), emit_group_load_1(), emit_group_store(), emit_library_call_value_1(), expand_mult(), expand_smod_pow2(), fold_binary_loc(), get_stored_val(), hash1(), load_register_parameters(), mem_loc_descriptor(), minmax_loc_descriptor(), mul_mod(), normalize(), output_constructor_bitfield(), scompare_loc_descriptor(), sext_hwi(), shift_return_value(), streamer_read_hwi(), streamer_read_uhwi(), and vect_recog_divmod_pattern().

unsigned char size_lookup[NUM_SIZE_LOOKUP]

static