This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Make extra_order_size_table effective on targets with MAX_ALIGNMENT > 4


On Wed, 21 Jun 2006, Mark Mitchell wrote:

> Richard Guenther wrote:
> 
> > !       /* Build an alignment mask we can use for testing
> > !          size % 2*align.  */
> 
> Why 2*align?
> 
> I find this code very confusing.  Let's see if we can clear it up.  I
> might be very dense, but maybe the next person will be too.

Ok, I added some more commentary to the code (see below for an updated
patch).  Basically we want to use this mask to test if a size has
the same or a smaller alignment requirement as the bin we're about to
create guarantees.  New bits now read:

      /* Build an alignment mask that can be used for testing
         size % 2*align.  If (size | MAX_ALIGNMENT) & mask is non-zero
         then the requested size appearant alignment requirement
         (which is at most MAX_ALIGNMENT) is less or equal than what
         the OBJECT_SIZE bin can guarantee.  */
      mask = ~(((unsigned)-1) << ffs (OBJECT_SIZE (order)));
      mask &= 2 * MAX_ALIGNMENT - 1;

> 
> !       /* Walk until we find a smaller bin with same or better
> alignment.  */
> 
> How about:
> 
>   /* All objects smaller than the OBJECT_SIZE for this ORDER could go
> into ORDER.  Determine the cases for which that is profitable.  */

That would not be quite correct - it's not only about profitability but
about correctness, so I changed it to read

      /* All objects smaller than the OBJECT_SIZE for this ORDER could go
         into ORDER.  Determine the cases for which that is profitable
         and fulfilling the alignment requirements.  Stop searching
         once a smaller bin with same or better alignment guarantee is
         found.  */

> 
> For this:
> 
> ! 	  unsigned int old_sz = OBJECT_SIZE (size_lookup [i]);
> ! 	  if (!(old_sz & (align >> 1))
> ! 	      && old_sz < OBJECT_SIZE (order))
> ! 	    break;
> 
> why not just if "(old_sz >= OBJECT_SIZE (order)) break;"?  Is the point
> that even though an object of size I might be in some smaller order, an
> object of size J < I might be in a bigger order, due to alignment
> constraints?   How can that be?

Consider the following, which I have added to the head comment of the
outer loop:

     Enforce alignment during lookup.  The resulting bin size must
     have the same or bigger alignment than the appearant alignment
     requirement from the size request (but not bigger alignment
     than MAX_ALIGNMENT).  Consider an extra bin of size 76 (in
     addition to the 64 and 128 byte sized bins).  A request of
     allocation size of 72 bytes must be served from the 128 bytes
     bin, because 72 bytes looks like a request for 8 byte aligned
     memory, while the 76 byte bin can only serve chunks with a
     guaranteed alignment of 4 bytes.  */

so we indeed can have larger bins inside a region that is served
from smaller ones.  Like in the example above, sizes between 65
and 76 are served from the 76 byte sized bin _except_ all multiples
of 8 (only 72 here), that must be served from the 128 byte pool.
With the previous code we didn't need to worry, as we rounded up
76 to 80 and so MAX_ALIGNMENT alignment could be guaranteed from
any size bin.

> 
> ! 	  /* Do not touch lookup entries which represent bigger
> ! 	     alignment than what we provide and do not override
> ! 	     smaller bins.  */
> 
> /* If object of size I are presently using a larger bin, we would like
> to move them to ORDER.  However, we can only do that if we can be sure
> they will be properly aligned.  They will be properly aligned if either
> the ORDER bin is maximally aligned, or if objects of size I cannot be
> more strictly aligned than the alignment of this order.  */

Sounds nice, I copied this.

> 
>   if (old_sz > OBJECT_SIZE (order)
>       && ((i & align) || !(OBJECT_SIZE ...))
> 
> But, why is the check for MAX_ALIGNMENT required here; you've already
> masked higher bits out of ALIGN above?

I changed this to read (i | MAX_ALIGNMENT) & mask, because we want
to check if the appearant alignment of i is less or equal(!) than
the alignment of ORDER.  An alignment of >= MAX_ALIGNMENT is special, as
it doesn't fit nicely with the mask test, but ORing in MAX_ALIGNMENT
fixes this in a prettier way.

Thanks,
Richard.


2006-06-21  Richard Guenther  <rguenther@suse.de>

	* ggc-page.c (init_ggc): Do not round up the extra_order_size_table
	sizes to MAX_ALIGNMENT.  Fix the size_lookup table to honour
	alignment requests instead.  Add verification code.
	Add struct tree_function_decl and struct tree_binfo size to
	extra_order_size_table.  Add missing element to size_lookup
	table.

Index: ggc-page.c
===================================================================
*** ggc-page.c	(revision 114850)
--- ggc-page.c	(working copy)
*************** static const size_t extra_order_size_tab
*** 193,198 ****
--- 193,200 ----
    sizeof (struct tree_var_decl),
    sizeof (struct tree_list),
    sizeof (struct tree_ssa_name),
+   sizeof (struct tree_function_decl),
+   sizeof (struct tree_binfo),
    sizeof (struct function),
    sizeof (struct basic_block_def),
    sizeof (bitmap_element),
*************** release_pages (void)
*** 1030,1036 ****
  /* This table provides a fast way to determine ceil(log_2(size)) for
     allocation requests.  The minimum allocation size is eight bytes.  */
  
! static unsigned char size_lookup[511] =
  {
    3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
    4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
--- 1032,1038 ----
  /* This table provides a fast way to determine ceil(log_2(size)) for
     allocation requests.  The minimum allocation size is eight bytes.  */
  
! static unsigned char size_lookup[512] =
  {
    3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
    4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
*************** static unsigned char size_lookup[511] =
*** 1063,1069 ****
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
!   9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
  };
  
  /* Typed allocation function.  Does nothing special in this collector.  */
--- 1065,1071 ----
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
!   9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
  };
  
  /* Typed allocation function.  Does nothing special in this collector.  */
*************** init_ggc (void)
*** 1509,1518 ****
    for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
      {
        size_t s = extra_order_size_table[order - HOST_BITS_PER_PTR];
- 
-       /* If S is not a multiple of the MAX_ALIGNMENT, then round it up
- 	 so that we're sure of getting aligned memory.  */
-       s = ROUND_UP (s, MAX_ALIGNMENT);
        object_size_table[order] = s;
      }
  
--- 1511,1516 ----
*************** init_ggc (void)
*** 1528,1544 ****
    /* Reset the size_lookup array to put appropriately sized objects in
       the special orders.  All objects bigger than the previous power
       of two, but no greater than the special size, should go in the
!      new order.  */
    for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
      {
!       int o;
!       int i;
  
!       o = size_lookup[OBJECT_SIZE (order)];
!       for (i = OBJECT_SIZE (order); size_lookup [i] == o; --i)
! 	size_lookup[i] = order;
      }
  
    G.depth_in_use = 0;
    G.depth_max = 10;
    G.depth = XNEWVEC (unsigned int, G.depth_max);
--- 1526,1582 ----
    /* Reset the size_lookup array to put appropriately sized objects in
       the special orders.  All objects bigger than the previous power
       of two, but no greater than the special size, should go in the
!      new order.
!      Enforce alignment during lookup.  The resulting bin size must
!      have the same or bigger alignment than the appearant alignment
!      requirement from the size request (but not bigger alignment
!      than MAX_ALIGNMENT).  Consider an extra bin of size 76 (in
!      addition to the 64 and 128 byte sized bins).  A request of
!      allocation size of 72 bytes must be served from the 128 bytes
!      bin, because 72 bytes looks like a request for 8 byte aligned
!      memory, while the 76 byte bin can only serve chunks with a
!      guaranteed alignment of 4 bytes.  */
    for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
      {
!       int i, mask;
  
!       /* Build an alignment mask that can be used for testing
!          size % 2*align.  If (size | MAX_ALIGNMENT) & mask is non-zero
! 	 then the requested size appearant alignment requirement 
! 	 (which is at most MAX_ALIGNMENT) is less or equal than what
! 	 the OBJECT_SIZE bin can guarantee.  */
!       mask = ~(((unsigned)-1) << ffs (OBJECT_SIZE (order)));
!       mask &= 2 * MAX_ALIGNMENT - 1;
! 
!       /* All objects smaller than the OBJECT_SIZE for this ORDER could go
! 	 into ORDER.  Determine the cases for which that is profitable
! 	 and fulfilling the alignment requirements.  Stop searching
! 	 once a smaller bin with same or better alignment guarantee is
! 	 found.  */
!       for (i = OBJECT_SIZE (order); ; --i)
! 	{
! 	  unsigned int old_sz = OBJECT_SIZE (size_lookup [i]);
! 	  if (!(old_sz & (mask >> 1))
! 	      && old_sz < OBJECT_SIZE (order))
! 	    break;
! 
! 	  /* If object of size I are presently using a larger bin, we would
! 	     like to move them to ORDER.  However, we can only do that if we
! 	     can be sure they will be properly aligned.  They will be properly
! 	     aligned if either the ORDER bin is maximally aligned, or if
! 	     objects of size I cannot be more strictly aligned than the
! 	     alignment of this order.  */
! 	  if ((i | MAX_ALIGNMENT) & mask
! 	      && old_sz > OBJECT_SIZE (order))
! 	    size_lookup[i] = order;
! 	}
      }
  
+   /* Verify we got everything right with respect to alignment requests.  */
+   for (order = 1; order < 512; ++order)
+     gcc_assert (ffs (OBJECT_SIZE (size_lookup [order]))
+ 		>= ffs (order | MAX_ALIGNMENT));
+ 
    G.depth_in_use = 0;
    G.depth_max = 10;
    G.depth = XNEWVEC (unsigned int, G.depth_max);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]