[PATCH] rheap: eliminates internal fragments caused by alignment

[PATCH] rheap: eliminates internal fragments caused by alignment

[Li Yang]

The patch adds fragments caused by rh_alloc_align() back to free list, instead
of allocating the whole chunk of memory.  This will greatly improve memory
utilization managed by rheap.

It solves MURAM not enough problem with 3 UCCs enabled on MPC8323.

Signed-off-by: Li Yang <leoli@freescale.com>
---
 arch/powerpc/lib/rheap.c |   48 +++++++++++++++++++++++++++------------------
 1 files changed, 29 insertions(+), 19 deletions(-)

diff --git a/arch/powerpc/lib/rheap.c b/arch/powerpc/lib/rheap.c
index 180ee29..2f24ea0 100644
--- a/arch/powerpc/lib/rheap.c
+++ b/arch/powerpc/lib/rheap.c
@@ -437,27 +437,26 @@ unsigned long rh_alloc_align(rh_info_t * info, int size, int alignment, const ch
 	struct list_head *l;
 	rh_block_t *blk;
 	rh_block_t *newblk;
-	unsigned long start;
+	unsigned long start, sp_size;
 
 	/* Validate size, and alignment must be power of two */
 	if (size <= 0 || (alignment & (alignment - 1)) != 0)
 		return (unsigned long) -EINVAL;
 
-	/* given alignment larger that default rheap alignment */
-	if (alignment > info->alignment)
-		size += alignment - 1;
-
 	/* Align to configured alignment */
 	size = (size + (info->alignment - 1)) & ~(info->alignment - 1);
 
-	if (assure_empty(info, 1) < 0)
+	if (assure_empty(info, 2) < 0)
 		return (unsigned long) -ENOMEM;
 
 	blk = NULL;
 	list_for_each(l, &info->free_list) {
 		blk = list_entry(l, rh_block_t, list);
-		if (size <= blk->size)
-			break;
+		if (size <= blk->size) {
+			start = (blk->start + alignment - 1) & ~(alignment - 1);
+			if (start + size <= blk->start + blk->size)
+				break;
+		}
 		blk = NULL;
 	}
 
@@ -470,25 +469,36 @@ unsigned long rh_alloc_align(rh_info_t * info, int size, int alignment, const ch
 		list_del(&blk->list);
 		newblk = blk;
 	} else {
+		/* Fragment caused, split if needed */
+		/* Create block for fragment in the beginning */
+		sp_size = start - blk->start;
+		if (sp_size) {
+			rh_block_t *spblk;
+
+			spblk = get_slot(info);
+			spblk->start = blk->start;
+			spblk->size = sp_size;
+			/* add before the blk */
+			list_add(&spblk->list, blk->list.prev);
+		}
 		newblk = get_slot(info);
-		newblk->start = blk->start;
+		newblk->start = start;
 		newblk->size = size;
 
-		/* blk still in free list, with updated start, size */
-		blk->start += size;
-		blk->size -= size;
+		/* blk still in free list, with updated start and size
+		 * for fragment in the end */
+		blk->start = start + size;
+		blk->size -= sp_size + size;
+		/* No fragment in the end, remove blk */
+		if (blk->size == 0) {
+			list_del(&blk->list);
+			release_slot(info, blk);
+		}
 	}
 
 	newblk->owner = owner;
-	start = newblk->start;
 	attach_taken_block(info, newblk);
 
-	/* for larger alignment return fixed up pointer  */
-	/* this is no problem with the deallocator since */
-	/* we scan for pointers that lie in the blocks   */
-	if (alignment > info->alignment)
-		start = (start + alignment - 1) & ~(alignment - 1);
-
 	return start;
 }

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Joakim Tjernlund]

On Mon, 2007-06-18 at 19:29 +0800, Li Yang wrote:
> The patch adds fragments caused by rh_alloc_align() back to free list, instead
> of allocating the whole chunk of memory.  This will greatly improve memory
> utilization managed by rheap.
> 
> It solves MURAM not enough problem with 3 UCCs enabled on MPC8323.
> 
> Signed-off-by: Li Yang <leoli@freescale.com>
> ---

For what it is worth:
I have tested this patch and it solves the problem with 3 UCCs
as ethernet for me. This fixes a regression introduced after 2.6.20
Please consider for 2.6.22
Acked-by: Joakim Tjernlund <joakim.tjernlund@transmode.se> 

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Pantelis Antoniou]

Hi Li,

The patch appears fine at first glance.

I'm really curious what kind of alignment do you use in order to have so
much wasted space that re-inserting the leftovers makes so much of a
difference.

-- Pantelis


On 18 =CE=99=CE=BF=CF=85=CE=BD 2007, at 2:29 =CE=9C=CE=9C, Li Yang =
wrote:

> The patch adds fragments caused by rh_alloc_align() back to free =20
> list, instead
> of allocating the whole chunk of memory.  This will greatly improve =20=

> memory
> utilization managed by rheap.
>
> It solves MURAM not enough problem with 3 UCCs enabled on MPC8323.
>
> Signed-off-by: Li Yang <leoli@freescale.com>
> ---
> arch/powerpc/lib/rheap.c |   48 ++++++++++++++++++++++++++=20
> +------------------
> 1 files changed, 29 insertions(+), 19 deletions(-)
>
> diff --git a/arch/powerpc/lib/rheap.c b/arch/powerpc/lib/rheap.c
> index 180ee29..2f24ea0 100644
> --- a/arch/powerpc/lib/rheap.c
> +++ b/arch/powerpc/lib/rheap.c
> @@ -437,27 +437,26 @@ unsigned long rh_alloc_align(rh_info_t * =20
> info, int size, int alignment, const ch
> 	struct list_head *l;
> 	rh_block_t *blk;
> 	rh_block_t *newblk;
> -	unsigned long start;
> +	unsigned long start, sp_size;
> 	/* Validate size, and alignment must be power of two */
> 	if (size <=3D 0 || (alignment & (alignment - 1)) !=3D 0)
> 		return (unsigned long) -EINVAL;
> -	/* given alignment larger that default rheap alignment */
> -	if (alignment > info->alignment)
> -		size +=3D alignment - 1;
> -
> 	/* Align to configured alignment */
> 	size =3D (size + (info->alignment - 1)) & ~(info->alignment - =
1);
> -	if (assure_empty(info, 1) < 0)
> +	if (assure_empty(info, 2) < 0)
> 		return (unsigned long) -ENOMEM;
> 	blk =3D NULL;
> 	list_for_each(l, &info->free_list) {
> 		blk =3D list_entry(l, rh_block_t, list);
> -		if (size <=3D blk->size)
> -			break;
> +		if (size <=3D blk->size) {
> +			start =3D (blk->start + alignment - 1) & =
~(alignment - 1);
> +			if (start + size <=3D blk->start + blk->size)
> +				break;
> +		}
> 		blk =3D NULL;
> 	}
> @@ -470,25 +469,36 @@ unsigned long rh_alloc_align(rh_info_t * =20
> info, int size, int alignment, const ch
> 		list_del(&blk->list);
> 		newblk =3D blk;
> 	} else {
> +		/* Fragment caused, split if needed */
> +		/* Create block for fragment in the beginning */
> +		sp_size =3D start - blk->start;
> +		if (sp_size) {
> +			rh_block_t *spblk;
> +
> +			spblk =3D get_slot(info);
> +			spblk->start =3D blk->start;
> +			spblk->size =3D sp_size;
> +			/* add before the blk */
> +			list_add(&spblk->list, blk->list.prev);
> +		}
> 		newblk =3D get_slot(info);
> -		newblk->start =3D blk->start;
> +		newblk->start =3D start;
> 		newblk->size =3D size;
> -		/* blk still in free list, with updated start, size */
> -		blk->start +=3D size;
> -		blk->size -=3D size;
> +		/* blk still in free list, with updated start and size
> +		 * for fragment in the end */
> +		blk->start =3D start + size;
> +		blk->size -=3D sp_size + size;
> +		/* No fragment in the end, remove blk */
> +		if (blk->size =3D=3D 0) {
> +			list_del(&blk->list);
> +			release_slot(info, blk);
> +		}
> 	}
> 	newblk->owner =3D owner;
> -	start =3D newblk->start;
> 	attach_taken_block(info, newblk);
> -	/* for larger alignment return fixed up pointer  */
> -	/* this is no problem with the deallocator since */
> -	/* we scan for pointers that lie in the blocks   */
> -	if (alignment > info->alignment)
> -		start =3D (start + alignment - 1) & ~(alignment - 1);
> -
> 	return start;
> }
>

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Joakim Tjernlund]

On Mon, 2007-06-18 at 15:14 +0300, Pantelis Antoniou wrote:
> Hi Li,
> 
> The patch appears fine at first glance.
> 
> I'm really curious what kind of alignment do you use in order to have so
> much wasted space that re-inserting the leftovers makes so much of a
> difference.
This I what you get for eth0 with patch,
all hex, decimal within()
MURAM alloc, start:400, size:200(512), align:8(8)
MURAM alloc, start:600, size:208(520), align:8(8)
MURAM alloc, start:880, size:80(128), align:80(128)
MURAM alloc, start:900, size:1a0(416), align:100(256)
MURAM alloc, start:aa0, size:40(64), align:20(32)
MURAM alloc, start:b00, size:100(256), align:100(256)
MURAM alloc, start:c00, size:a0(160), align:100(256)
MURAM alloc, start:cc0, size:c(12), align:40(64)
MURAM alloc, start:cd0, size:30(48), align:8(8)
MURAM alloc, start:d00, size:80(128), align:80(128)
MURAM alloc, start:d80, size:80(128), align:80(128)
MURAM alloc, start:e00, size:80(128), align:80(128)
MURAM alloc, start:e80, size:80(128), align:80(128)
MURAM alloc, start:f00, size:40(64), align:40(64)
MURAM alloc, start:f40, size:40(64), align:40(64)
MURAM alloc, start:f80, size:40(64), align:40(64)
MURAM alloc, start:fc0, size:40(64), align:40(64)
MURAM alloc, start:1000, size:5d(93), align:4(4)

And this is what you get without patch:
MURAM alloc, start:1400, size:200(512), align:8(8)
MURAM alloc, start:1608, size:208(520), align:8(8)
MURAM alloc, start:1880, size:80(128), align:80(128)
MURAM alloc, start:1a00, size:1a0(416), align:100(256)
MURAM alloc, start:1bc0, size:40(64), align:20(32)
MURAM alloc, start:1d00, size:100(256), align:100(256)
MURAM alloc, start:1f00, size:a0(160), align:100(256)
MURAM alloc, start:1fc0, size:c(12), align:40(64)
MURAM alloc, start:2000, size:30(48), align:8(8)
MURAM alloc, start:2080, size:80(128), align:80(128)
MURAM alloc, start:2180, size:80(128), align:80(128)
MURAM alloc, start:2280, size:80(128), align:80(128)
MURAM alloc, start:2380, size:80(128), align:80(128)
MURAM alloc, start:2440, size:40(64), align:40(64)
MURAM alloc, start:24c0, size:40(64), align:40(64)
MURAM alloc, start:2540, size:40(64), align:40(64)
MURAM alloc, start:25c0, size:40(64), align:40(64)
MURAM alloc, start:262c, size:5d(93), align:4(4)

 Jocke

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Pantelis Antoniou]

On 18 =CE=99=CE=BF=CF=85=CE=BD 2007, at 3:25 =CE=9C=CE=9C, Joakim =
Tjernlund wrote:

> On Mon, 2007-06-18 at 15:14 +0300, Pantelis Antoniou wrote:
>> Hi Li,
>>
>> The patch appears fine at first glance.
>>
>> I'm really curious what kind of alignment do you use in order to =20
>> have so
>> much wasted space that re-inserting the leftovers makes so much of a
>> difference.

Jocke,

Ugh, 256?

That's not nice at all.
I'm not sure that even then you're going to have any guarantees that
the allocations will be successful.

I'm afraid that in those case it would be better for the board
platform setup to have the space preallocated according to the BSP
requirements.

Just my $0.02.

-- Pantelis

> This I what you get for eth0 with patch,
> all hex, decimal within()
> MURAM alloc, start:400, size:200(512), align:8(8)
> MURAM alloc, start:600, size:208(520), align:8(8)
> MURAM alloc, start:880, size:80(128), align:80(128)
> MURAM alloc, start:900, size:1a0(416), align:100(256)
> MURAM alloc, start:aa0, size:40(64), align:20(32)
> MURAM alloc, start:b00, size:100(256), align:100(256)
> MURAM alloc, start:c00, size:a0(160), align:100(256)
> MURAM alloc, start:cc0, size:c(12), align:40(64)
> MURAM alloc, start:cd0, size:30(48), align:8(8)
> MURAM alloc, start:d00, size:80(128), align:80(128)
> MURAM alloc, start:d80, size:80(128), align:80(128)
> MURAM alloc, start:e00, size:80(128), align:80(128)
> MURAM alloc, start:e80, size:80(128), align:80(128)
> MURAM alloc, start:f00, size:40(64), align:40(64)
> MURAM alloc, start:f40, size:40(64), align:40(64)
> MURAM alloc, start:f80, size:40(64), align:40(64)
> MURAM alloc, start:fc0, size:40(64), align:40(64)
> MURAM alloc, start:1000, size:5d(93), align:4(4)
>
> And this is what you get without patch:
> MURAM alloc, start:1400, size:200(512), align:8(8)
> MURAM alloc, start:1608, size:208(520), align:8(8)
> MURAM alloc, start:1880, size:80(128), align:80(128)
> MURAM alloc, start:1a00, size:1a0(416), align:100(256)
> MURAM alloc, start:1bc0, size:40(64), align:20(32)
> MURAM alloc, start:1d00, size:100(256), align:100(256)
> MURAM alloc, start:1f00, size:a0(160), align:100(256)
> MURAM alloc, start:1fc0, size:c(12), align:40(64)
> MURAM alloc, start:2000, size:30(48), align:8(8)
> MURAM alloc, start:2080, size:80(128), align:80(128)
> MURAM alloc, start:2180, size:80(128), align:80(128)
> MURAM alloc, start:2280, size:80(128), align:80(128)
> MURAM alloc, start:2380, size:80(128), align:80(128)
> MURAM alloc, start:2440, size:40(64), align:40(64)
> MURAM alloc, start:24c0, size:40(64), align:40(64)
> MURAM alloc, start:2540, size:40(64), align:40(64)
> MURAM alloc, start:25c0, size:40(64), align:40(64)
> MURAM alloc, start:262c, size:5d(93), align:4(4)
>
>  Jocke

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Joakim Tjernlund]

On Mon, 2007-06-18 at 15:31 +0300, Pantelis Antoniou wrote:
> On 18 =CE=99=CE=BF=CF=85=CE=BD 2007, at 3:25 =CE=9C=CE=9C, Joakim Tjernlu=
nd wrote:
>=20
> > On Mon, 2007-06-18 at 15:14 +0300, Pantelis Antoniou wrote:
> >> Hi Li,
> >>
> >> The patch appears fine at first glance.
> >>
> >> I'm really curious what kind of alignment do you use in order to =20
> >> have so
> >> much wasted space that re-inserting the leftovers makes so much of a
> >> difference.
>=20
> Jocke,
>=20
> Ugh, 256?

Yes, the ucc_geth needs lots of alignment. Leo can tell you more :)

>=20
> That's not nice at all.
> I'm not sure that even then you're going to have any guarantees that
> the allocations will be successful.
>=20
> I'm afraid that in those case it would be better for the board
> platform setup to have the space preallocated according to the BSP
> requirements.

Maybe, but without the PATCH you will run out of space very quickly
and you cannot bring up 3 ethernet interfaces. Rheap is plain wrong
as is today and needs this patch.

 Jocke

>=20
> Just my $0.02.
>=20
> -- Pantelis

RE: [PATCH] rheap: eliminates internal fragments caused by alignment

[Li Yang-r58472]

> -----Original Message-----
> From: Pantelis Antoniou [mailto:pantelis.antoniou@gmail.com]
> Sent: Monday, June 18, 2007 8:31 PM
> To: joakim.tjernlund@transmode.se
> Cc: Li Yang-r58472; Paul; Vitaly Bordug; linuxppc-dev Development
> Subject: Re: [PATCH] rheap: eliminates internal fragments caused by =
alignment
>=20
>=20
> On 18 =C9=EF=F5=ED 2007, at 3:25 =CC=CC, Joakim Tjernlund wrote:
>=20
> > On Mon, 2007-06-18 at 15:14 +0300, Pantelis Antoniou wrote:
> >> Hi Li,
> >>
> >> The patch appears fine at first glance.
> >>
> >> I'm really curious what kind of alignment do you use in order to
> >> have so
> >> much wasted space that re-inserting the leftovers makes so much of =
a
> >> difference.
>=20
> Jocke,
>=20
> Ugh, 256?
>=20
> That's not nice at all.
Pantelis,

For QE, most of the MURAM allocation requires relative large alignment.  =
SDMA buffer even needs a 4k alignment.

> I'm not sure that even then you're going to have any guarantees that
> the allocations will be successful.
>=20
> I'm afraid that in those case it would be better for the board
> platform setup to have the space preallocated according to the BSP
> requirements.

Dynamic allocation surely can't match the efficiency of manual =
allocation.  But with this patch applied, the utilization efficiency =
will be good enough for most systems to work correctly, and without the =
great trouble to partition the space yourself.  Moreover, given the fact =
that in QE drivers some MURAM usage can be tunable, it will be more =
suitable to use the dynamic allocation.

A general policy will be helpful, that allocations with huge alignment =
(like 4k) should always be done as early as possible.

- Leo

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Joakim Tjernlund]

On Mon, 2007-06-18 at 13:48 +0200, Joakim Tjernlund wrote:
> On Mon, 2007-06-18 at 19:29 +0800, Li Yang wrote:
> > The patch adds fragments caused by rh_alloc_align() back to free list, instead
> > of allocating the whole chunk of memory.  This will greatly improve memory
> > utilization managed by rheap.
> > 
> > It solves MURAM not enough problem with 3 UCCs enabled on MPC8323.
> > 
> > Signed-off-by: Li Yang <leoli@freescale.com>
> > ---
> 
> For what it is worth:
> I have tested this patch and it solves the problem with 3 UCCs
> as ethernet for me. This fixes a regression introduced after 2.6.20
> Please consider for 2.6.22
> Acked-by: Joakim Tjernlund <joakim.tjernlund@transmode.se> 

I noticed Paulus pull request to Linus and this patch wasn't
included. I really want to see it included.

 Jocke

Re: [PATCH] rheap: eliminates internal fragments caused by alignment

[Kumar Gala]

On Tue, 19 Jun 2007, Joakim Tjernlund wrote:

> On Mon, 2007-06-18 at 13:48 +0200, Joakim Tjernlund wrote:
> > On Mon, 2007-06-18 at 19:29 +0800, Li Yang wrote:
> > > The patch adds fragments caused by rh_alloc_align() back to free list, instead
> > > of allocating the whole chunk of memory.  This will greatly improve memory
> > > utilization managed by rheap.
> > >
> > > It solves MURAM not enough problem with 3 UCCs enabled on MPC8323.
> > >
> > > Signed-off-by: Li Yang <leoli@freescale.com>
> > > ---
> >
> > For what it is worth:
> > I have tested this patch and it solves the problem with 3 UCCs
> > as ethernet for me. This fixes a regression introduced after 2.6.20
> > Please consider for 2.6.22
> > Acked-by: Joakim Tjernlund <joakim.tjernlund@transmode.se>
>
> I noticed Paulus pull request to Linus and this patch wasn't
> included. I really want to see it included.
>

I'll push (or request pull) from Linus tonight for this to go into 2.6.22

- k