[PATCH v2 0/2] lmb: remove overlapping region with next range

[PATCH v2 0/2] lmb: remove overlapping region with next range

[Udit Kumar]

In case, newly address range to be added is coalescing with some region
but also overlapping with next region.
In such, case overlapped region was getting created.
This patch series, detect such overlap and coalescing such region as one

Change logs:
test logs
https://gist.github.com/uditkumarti/7be37a662fabfcfefb74d1a67ccde2bd

Changes in v2:
Patch 1/2: Corrected typo
Patch 2/2 : Added test case as suggested by Simon
Link to v1:
https://lore.kernel.org/all/20230924111832.3741245-1-u-kumar1@ti.com/#t

Udit Kumar (2):
  lmb: remove overlapping region with next range
  test: lmb: Added test case for coaleacse with first and overlap with
    Second

 lib/lmb.c      | 37 +++++++++++++++++++++++++++++++++----
 test/lib/lmb.c | 13 ++++++++++++-
 2 files changed, 45 insertions(+), 5 deletions(-)

-- 
2.34.1

[PATCH v2 1/2] lmb: remove overlapping region with next range

[Udit Kumar]

In case of new memory range to be added is coalesced
with any already added non last lmb region.

And there is possibility that, then region in which new memory
range added is not adjacent to next region. But have some
sections are overlapping.

So along with adjacency check with next lmb region,
check for overlap should be done.

In case overlap  is found, adjust and merge these two lmb
region into one.

Reported-by: Suman Anna <s-anna@ti.com>
Signed-off-by: Udit Kumar <u-kumar1@ti.com>
---
 lib/lmb.c | 37 +++++++++++++++++++++++++++++++++----
 1 file changed, 33 insertions(+), 4 deletions(-)

diff --git a/lib/lmb.c b/lib/lmb.c
index b2c233edb6..da924c6789 100644
--- a/lib/lmb.c
+++ b/lib/lmb.c
@@ -74,6 +74,16 @@ static long lmb_addrs_adjacent(phys_addr_t base1, phys_size_t size1,
 	return 0;
 }
 
+static long lmb_regions_overlap(struct lmb_region *rgn, unsigned long r1,
+				unsigned long r2)
+{
+	phys_addr_t base1 = rgn->region[r1].base;
+	phys_size_t size1 = rgn->region[r1].size;
+	phys_addr_t base2 = rgn->region[r2].base;
+	phys_size_t size2 = rgn->region[r2].size;
+
+	return lmb_addrs_overlap(base1, size1, base2, size2);
+}
 static long lmb_regions_adjacent(struct lmb_region *rgn, unsigned long r1,
 				 unsigned long r2)
 {
@@ -81,7 +91,6 @@ static long lmb_regions_adjacent(struct lmb_region *rgn, unsigned long r1,
 	phys_size_t size1 = rgn->region[r1].size;
 	phys_addr_t base2 = rgn->region[r2].base;
 	phys_size_t size2 = rgn->region[r2].size;
-
 	return lmb_addrs_adjacent(base1, size1, base2, size2);
 }
 
@@ -105,6 +114,23 @@ static void lmb_coalesce_regions(struct lmb_region *rgn, unsigned long r1,
 	lmb_remove_region(rgn, r2);
 }
 
+/*Assumption : base addr of region 1 < base addr of region 2*/
+static void lmb_fix_over_lap_regions(struct lmb_region *rgn, unsigned long r1,
+				     unsigned long r2)
+{
+	phys_addr_t base1 = rgn->region[r1].base;
+	phys_size_t size1 = rgn->region[r1].size;
+	phys_addr_t base2 = rgn->region[r2].base;
+	phys_size_t size2 = rgn->region[r2].size;
+
+	if (base1 + size1 > base2 + size2) {
+		printf("This will not be a case any time\n");
+		return;
+	}
+	rgn->region[r1].size = base2 + size2 - base1;
+	lmb_remove_region(rgn, r2);
+}
+
 void lmb_init(struct lmb *lmb)
 {
 #if IS_ENABLED(CONFIG_LMB_USE_MAX_REGIONS)
@@ -249,7 +275,6 @@ static long lmb_add_region_flags(struct lmb_region *rgn, phys_addr_t base,
 		phys_size_t rgnflags = rgn->region[i].flags;
 		phys_addr_t end = base + size - 1;
 		phys_addr_t rgnend = rgnbase + rgnsize - 1;
-
 		if (rgnbase <= base && end <= rgnend) {
 			if (flags == rgnflags)
 				/* Already have this region, so we're done */
@@ -278,10 +303,14 @@ static long lmb_add_region_flags(struct lmb_region *rgn, phys_addr_t base,
 		}
 	}
 
-	if ((i < rgn->cnt - 1) && lmb_regions_adjacent(rgn, i, i + 1)) {
-		if (rgn->region[i].flags == rgn->region[i + 1].flags) {
+	if (i < rgn->cnt - 1 && rgn->region[i].flags == rgn->region[i + 1].flags)  {
+		if (lmb_regions_adjacent(rgn, i, i + 1)) {
 			lmb_coalesce_regions(rgn, i, i + 1);
 			coalesced++;
+		} else if (lmb_regions_overlap(rgn, i, i + 1)) {
+			/* fix overlapping area */
+			lmb_fix_over_lap_regions(rgn, i, i + 1);
+			coalesced++;
 		}
 	}
 
-- 
2.34.1

[PATCH v2 2/2] test: lmb: Add test for coalescing and overlap range

[Udit Kumar]

Add test case for an address range which is coalescing with one of
range and overlapping with next range 

Cc: Simon Glass <sjg@google.com>
Signed-off-by: Udit Kumar <u-kumar1@ti.com>
---
 test/lib/lmb.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/test/lib/lmb.c b/test/lib/lmb.c
index 1628875035..15c68ce396 100644
--- a/test/lib/lmb.c
+++ b/test/lib/lmb.c
@@ -451,12 +451,23 @@ static int lib_test_lmb_overlapping_reserve(struct unit_test_state *uts)
 	ut_asserteq(ret, 0);
 	ASSERT_LMB(&lmb, ram, ram_size, 2, 0x40010000, 0x10000,
 		   0x40030000, 0x10000, 0, 0);
-	/* allocate 2nd region */
+	/* allocate 2nd region , This should coalesced all region into one */
 	ret = lmb_reserve(&lmb, 0x40020000, 0x10000);
 	ut_assert(ret >= 0);
 	ASSERT_LMB(&lmb, ram, ram_size, 1, 0x40010000, 0x30000,
 		   0, 0, 0, 0);
 
+	/* allocate 2nd region, which should be added as first region */
+	ret = lmb_reserve(&lmb, 0x40000000, 0x8000);
+	ut_assert(ret >= 0);
+	ASSERT_LMB(&lmb, ram, ram_size, 2, 0x40000000, 0x8000,
+		   0x40010000, 0x30000, 0, 0);
+
+	/* allocate 3rd region, coalesce with first and overlap with second */
+	ret = lmb_reserve(&lmb, 0x40008000, 0x10000);
+	ut_assert(ret >= 0);
+	ASSERT_LMB(&lmb, ram, ram_size, 1, 0x40000000, 0x40000,
+		   0, 0, 0, 0);
 	return 0;
 }
 
-- 
2.34.1

Re: [PATCH v2 2/2] test: lmb: Add test for coalescing and overlap range

[Simon Glass]

On Tue, 26 Sept 2023 at 05:25, Udit Kumar <u-kumar1@ti.com> wrote:
>
> Add test case for an address range which is coalescing with one of
> range and overlapping with next range
>
> Cc: Simon Glass <sjg@google.com>
> Signed-off-by: Udit Kumar <u-kumar1@ti.com>
> ---
>  test/lib/lmb.c | 13 ++++++++++++-
>  1 file changed, 12 insertions(+), 1 deletion(-)
>

Reviewed-by: Simon Glass <sjg@chromium.org>

Re: [PATCH v2 1/2] lmb: remove overlapping region with next range

[Tom Rini]

[-- Attachment #1: Type: text/plain, Size: 650 bytes --]

On Tue, Sep 26, 2023 at 04:54:42PM +0530, Udit Kumar wrote:

> In case of new memory range to be added is coalesced
> with any already added non last lmb region.
> 
> And there is possibility that, then region in which new memory
> range added is not adjacent to next region. But have some
> sections are overlapping.
> 
> So along with adjacency check with next lmb region,
> check for overlap should be done.
> 
> In case overlap  is found, adjust and merge these two lmb
> region into one.
> 
> Reported-by: Suman Anna <s-anna@ti.com>
> Signed-off-by: Udit Kumar <u-kumar1@ti.com>

Applied to u-boot/master, thanks!

-- 
Tom

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 659 bytes --]

Re: [PATCH v2 2/2] test: lmb: Add test for coalescing and overlap range

[Tom Rini]

[-- Attachment #1: Type: text/plain, Size: 358 bytes --]

On Tue, Sep 26, 2023 at 04:54:43PM +0530, Udit Kumar wrote:

> Add test case for an address range which is coalescing with one of
> range and overlapping with next range 
> 
> Cc: Simon Glass <sjg@google.com>
> Signed-off-by: Udit Kumar <u-kumar1@ti.com>
> Reviewed-by: Simon Glass <sjg@chromium.org>

Applied to u-boot/master, thanks!

-- 
Tom

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 659 bytes --]