rheap: eliminates internal fragments caused by alignment

PATCH In review Li Yang 4 participants 9 messages Jun 18, 2007 – Jun 19, 2007 PowerPC

Share & tools

Li Yang

author

2007-06-18 11:27 UTC #0 lore raw

PATCH 1/1 rheap: eliminates internal fragments caused by alignment

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 <[email protected]>

---
arch/powerpc/lib/rheap.c | 48 +++++++++++++++++++++++++++------------------

1 files changed, 29 insertions(+), 19 deletions(-)

arch/powerpc/lib/rheap.c +0 -0

index 180ee29..2f24ea0 100644
@@ -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;
}

Joakim Tjernlund

Acked-by on v1 1/1

2007-06-18 11:48 UTC #1 lore raw

Quoted 8 lines · 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 <[email protected]>
---

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 <[email protected]>

Pantelis Antoniou

2007-06-18 12:15 UTC #4 lore raw

In reply to Li Yang

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

Quoted 33 lines · Li Yang =

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 <[email protected]>
---
arch/powerpc/lib/rheap.c | 48 ++++++++++++++++++++++++++=20
+------------------
1 files changed, 29 insertions(+), 19 deletions(-)
arch/powerpc/lib/rheap.c +0 -0
index 180ee29..2f24ea0 100644
@@ -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;
arch/powerpc/lib/rheap.c +1 -1
-	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;
arch/powerpc/lib/rheap.c +0 -4
-	/* given alignment larger that default rheap alignment */
-	if (alignment > info->alignment)
-		size +=3D alignment - 1;
-

Quoted 2 lines

	/* Align to configured alignment */
	size =3D (size + (info->alignment - 1)) & ~(info->alignment - =

1);

arch/powerpc/lib/rheap.c

Quoted 10 lines

arch/powerpc/lib/rheap.c +1 -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);

arch/powerpc/lib/rheap.c +2 -2

-		if (size <=3D blk->size)
-			break;
+		if (size <=3D blk->size) {
+			start =3D (blk->start + alignment - 1) & =

~(alignment - 1);

Quoted 51 lines

arch/powerpc/lib/rheap.c +3 -0

+			if (start + size <=3D blk->start + blk->size)
+				break;
+		}

		blk =3D NULL;
	}

arch/powerpc/lib/rheap.c +0 -0

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

arch/powerpc/lib/rheap.c +12 -0

+		/* 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);

arch/powerpc/lib/rheap.c +1 -1

-		newblk->start =3D blk->start;
+		newblk->start =3D start;

		newblk->size =3D size;

arch/powerpc/lib/rheap.c +9 -3

-		/* 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;

arch/powerpc/lib/rheap.c +0 -1

-	start =3D newblk->start;

	attach_taken_block(info, newblk);

arch/powerpc/lib/rheap.c +0 -6

-	/* 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;
}

Joakim Tjernlund

2007-06-18 12:25 UTC #5 lore raw

Quoted 7 lines · 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.

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

Pantelis Antoniou

2007-06-18 12:31 UTC #6 lore raw

Quoted 9 lines · Joakim = Tjernlund

Quoted 8 lines · 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 =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

Quoted 42 lines

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

Joakim Tjernlund

2007-06-18 13:24 UTC #7 lore raw

Quoted 1 line · Pantelis Antoniou

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

Quoted 6 lines · nd

=20
Quoted 5 lines · Pantelis Antoniou
Quoted 4 lines
Hi Li,
The patch appears fine at first glance.

Quoted 8 lines

Quoted 4 lines
Quoted 4 lines
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 :)

Quoted 8 lines

=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

Quoted 4 lines

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

Li Yang-r58472

author

2007-06-19 04:00 UTC #8 lore raw

In reply to Pantelis Antoniou

Quoted 6 lines

-----Original Message-----
From: Pantelis Antoniou [mailto:[email protected]]
Sent: Monday, June 18, 2007 8:31 PM
To: [email protected]
Cc: Li Yang-r58472; Paul; Vitaly Bordug; linuxppc-dev Development
Subject: Re: [PATCH] rheap: eliminates internal fragments caused by =

alignment

Quoted 12 lines

=20
=20
On 18 =C9=EF=F5=ED 2007, at 3:25 =CC=CC, Joakim Tjernlund wrote:
=20
Quoted 8 lines · Pantelis Antoniou
Quoted 7 lines
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 7 lines

Quoted 1 line
Quoted 1 line
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.

Quoted 6 lines

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

Joakim Tjernlund

2007-06-19 16:17 UTC #2 lore raw

In reply to Joakim Tjernlund

Quoted 7 lines · Joakim Tjernlund

Quoted 6 lines · 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.

Quoted 8 lines

Quoted 2 lines
Signed-off-by Li Yang <[email protected]>
---
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 <[email protected]>

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

Jocke

Kumar Gala

2007-06-19 23:04 UTC #3 lore raw

Quoted 11 lines · Joakim Tjernlund

Quoted 10 lines · Joakim Tjernlund
Quoted 8 lines · 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 <[email protected]>
---

Quoted 9 lines

Quoted 5 lines
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 <[email protected]>
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