[PATCH] rheap: eliminates internal fragments caused by alignment

Subsystems: linux for powerpc (32-bit and 64-bit), the rest

STALE7021d

9 messages, 4 authors, 2007-06-19 · open the first message on its own page

[PATCH] rheap: eliminates internal fragments caused by alignment

From: Li Yang <hidden>
Date: 2007-06-18 11:27:50

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 <redacted>
---
 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

From: Joakim Tjernlund <hidden>
Date: 2007-06-18 11:48:28

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 <redacted>
---

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 <redacted>

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

From: Pantelis Antoniou <pantelis.antoniou@gmail.com>
Date: 2007-06-18 12:15:08

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=

quoted hunk

memory
utilization managed by rheap.

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

Signed-off-by: Li Yang <redacted>
---
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);

quoted hunk

+			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

From: Joakim Tjernlund <hidden>
Date: 2007-06-18 12:25:51

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

From: Pantelis Antoniou <pantelis.antoniou@gmail.com>
Date: 2007-06-18 12:31:39

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:

quoted

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

From: Joakim Tjernlund <hidden>
Date: 2007-06-18 13:24:44

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

quoted

On Mon, 2007-06-18 at 15:14 +0300, Pantelis Antoniou wrote:

quoted

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

From: Li Yang-r58472 <hidden>
Date: 2007-06-19 04:00:26

-----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

quoted

On Mon, 2007-06-18 at 15:14 +0300, Pantelis Antoniou wrote:

quoted

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 =

quoted

quoted
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

From: Joakim Tjernlund <hidden>
Date: 2007-06-19 16:17:29

On Mon, 2007-06-18 at 13:48 +0200, Joakim Tjernlund wrote:

On Mon, 2007-06-18 at 19:29 +0800, Li Yang wrote:

quoted

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 <redacted>
---

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 <redacted>

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

From: Kumar Gala <hidden>
Date: 2007-06-19 23:04:41


On Tue, 19 Jun 2007, Joakim Tjernlund wrote:

On Mon, 2007-06-18 at 13:48 +0200, Joakim Tjernlund wrote:

quoted

On Mon, 2007-06-18 at 19:29 +0800, Li Yang wrote:

quoted

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 <redacted>
---

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 <redacted>

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

`h`	back out one level
`j`	next message in thread
`k`	previous message in thread
`l`	drill in
`Esc`	close help / fold thread tree
`?`	toggle this help