LKML Archive on lore.kernel.org
 help / color / Atom feed
From: Tejun Heo <tj@kernel.org>
To: mingo@redhat.com, hpa@zytor.com, tglx@linutronix.de,
	benh@kernel.crashing.org, yinghai@kernel.org,
	davem@davemloft.net
Cc: linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org,
	x86@kernel.org, Tejun Heo <tj@kernel.org>
Subject: [PATCH 02/13] memblock: Reimplement memblock_add_region()
Date: Tue, 12 Jul 2011 11:15:55 +0200
Message-ID: <1310462166-31469-3-git-send-email-tj@kernel.org> (raw)
In-Reply-To: <1310462166-31469-1-git-send-email-tj@kernel.org>

memblock_add_region() carefully checked for merge and overlap
conditions while adding a new region, which is complicated and makes
it difficult to allow arbitrary overlaps or add more merge conditions
(e.g. node ID).

This re-implements memblock_add_region() such that insertion is done
in two steps - all non-overlapping portions of new area are inserted
as separate regions first and then memblock_merge_regions() scan and
merge all neighbouring compatible regions.

This makes addition logic simpler and more versatile and enables
adding node information to memblock.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
---
 mm/memblock.c |  197 ++++++++++++++++++++++++++++++++-------------------------
 1 files changed, 111 insertions(+), 86 deletions(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index bd3a3a9..992aa18 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -251,117 +251,142 @@ static int __init_memblock memblock_double_array(struct memblock_type *type)
 	return 0;
 }
 
-static long __init_memblock memblock_add_region(struct memblock_type *type,
-						phys_addr_t base, phys_addr_t size)
+/**
+ * memblock_merge_regions - merge neighboring compatible regions
+ * @type: memblock type to scan
+ *
+ * Scan @type and merge neighboring compatible regions.
+ */
+static void __init_memblock memblock_merge_regions(struct memblock_type *type)
 {
-	phys_addr_t end = base + size;
-	int i, slot = -1;
+	int i = 0;
 
-	/* First try and coalesce this MEMBLOCK with others */
-	for (i = 0; i < type->cnt; i++) {
-		struct memblock_region *rgn = &type->regions[i];
-		phys_addr_t rend = rgn->base + rgn->size;
+	/* cnt never goes below 1 */
+	while (i < type->cnt - 1) {
+		struct memblock_region *this = &type->regions[i];
+		struct memblock_region *next = &type->regions[i + 1];
 
-		/* Exit if there's no possible hits */
-		if (rgn->base > end || rgn->size == 0)
-			break;
-
-		/* Check if we are fully enclosed within an existing
-		 * block
-		 */
-		if (rgn->base <= base && rend >= end)
-			return 0;
+		if (this->base + this->size != next->base) {
+			BUG_ON(this->base + this->size > next->base);
+			i++;
+			continue;
+		}
 
-		/* Check if we overlap or are adjacent with the bottom
-		 * of a block.
-		 */
-		if (base < rgn->base && end >= rgn->base) {
-			/* We extend the bottom of the block down to our
-			 * base
-			 */
-			rgn->base = base;
-			rgn->size = rend - base;
+		this->size += next->size;
+		memmove(next, next + 1, (type->cnt - (i + 1)) * sizeof(*next));
+		type->cnt--;
+	}
+}
 
-			/* Return if we have nothing else to allocate
-			 * (fully coalesced)
-			 */
-			if (rend >= end)
-				return 0;
+/**
+ * memblock_insert_region - insert new memblock region
+ * @type: memblock type to insert into
+ * @idx: index for the insertion point
+ * @base: base address of the new region
+ * @size: size of the new region
+ *
+ * Insert new memblock region [@base,@base+@size) into @type at @idx.
+ * @type must already have extra room to accomodate the new region.
+ */
+static void __init_memblock memblock_insert_region(struct memblock_type *type,
+						   int idx, phys_addr_t base,
+						   phys_addr_t size)
+{
+	struct memblock_region *rgn = &type->regions[idx];
 
-			/* We continue processing from the end of the
-			 * coalesced block.
-			 */
-			base = rend;
-			size = end - base;
-		}
+	BUG_ON(type->cnt >= type->max);
+	memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
+	rgn->base = base;
+	rgn->size = size;
+	type->cnt++;
+}
 
-		/* Now check if we overlap or are adjacent with the
-		 * top of a block
-		 */
-		if (base <= rend && end >= rend) {
-			/* We adjust our base down to enclose the
-			 * original block and destroy it. It will be
-			 * part of our new allocation. Since we've
-			 * freed an entry, we know we won't fail
-			 * to allocate one later, so we won't risk
-			 * losing the original block allocation.
-			 */
-			size += (base - rgn->base);
-			base = rgn->base;
-			memblock_remove_region(type, i--);
-		}
-	}
+/**
+ * memblock_add_region - add new memblock region
+ * @type: memblock type to add new region into
+ * @base: base address of the new region
+ * @size: size of the new region
+ *
+ * Add new memblock region [@base,@base+@size) into @type.  The new region
+ * is allowed to overlap with existing ones - overlaps don't affect already
+ * existing regions.  @type is guaranteed to be minimal (all neighbouring
+ * compatible regions are merged) after the addition.
+ *
+ * RETURNS:
+ * 0 on success, -errno on failure.
+ */
+static long __init_memblock memblock_add_region(struct memblock_type *type,
+						phys_addr_t base, phys_addr_t size)
+{
+	bool insert = false;
+	phys_addr_t obase = base, end = base + size;
+	int i, nr_new;
 
-	/* If the array is empty, special case, replace the fake
-	 * filler region and return
-	 */
-	if ((type->cnt == 1) && (type->regions[0].size == 0)) {
+	/* special case for empty array */
+	if (type->regions[0].size == 0) {
+		WARN_ON(type->cnt != 1);
 		type->regions[0].base = base;
 		type->regions[0].size = size;
 		return 0;
 	}
-
-	/* If we are out of space, we fail. It's too late to resize the array
-	 * but then this shouldn't have happened in the first place.
+repeat:
+	/*
+	 * The following is executed twice.  Once with %false @insert and
+	 * then with %true.  The first counts the number of regions needed
+	 * to accomodate the new area.  The second actually inserts them.
 	 */
-	if (WARN_ON(type->cnt >= type->max))
-		return -1;
+	base = obase;
+	nr_new = 0;
+
+	for (i = 0; i < type->cnt; i++) {
+		struct memblock_region *rgn = &type->regions[i];
+		phys_addr_t rbase = rgn->base;
+		phys_addr_t rend = rbase + rgn->size;
 
-	/* Couldn't coalesce the MEMBLOCK, so add it to the sorted table. */
-	for (i = type->cnt - 1; i >= 0; i--) {
-		if (base < type->regions[i].base) {
-			type->regions[i+1].base = type->regions[i].base;
-			type->regions[i+1].size = type->regions[i].size;
-		} else {
-			type->regions[i+1].base = base;
-			type->regions[i+1].size = size;
-			slot = i + 1;
+		if (rbase >= end)
 			break;
+		if (rend <= base)
+			continue;
+		/*
+		 * @rgn overlaps.  If it separates the lower part of new
+		 * area, insert that portion.
+		 */
+		if (rbase > base) {
+			nr_new++;
+			if (insert)
+				memblock_insert_region(type, i++, base,
+						       rbase - base);
 		}
+		/* area below @rend is dealt with, forget about it */
+		base = min(rend, end);
 	}
-	if (base < type->regions[0].base) {
-		type->regions[0].base = base;
-		type->regions[0].size = size;
-		slot = 0;
+
+	/* insert the remaining portion */
+	if (base < end) {
+		nr_new++;
+		if (insert)
+			memblock_insert_region(type, i, base, end - base);
 	}
-	type->cnt++;
 
-	/* The array is full ? Try to resize it. If that fails, we undo
-	 * our allocation and return an error
+	/*
+	 * If this was the first round, resize array and repeat for actual
+	 * insertions; otherwise, merge and return.
 	 */
-	if (type->cnt == type->max && memblock_double_array(type)) {
-		BUG_ON(slot < 0);
-		memblock_remove_region(type, slot);
-		return -1;
+	if (!insert) {
+		while (type->cnt + nr_new > type->max)
+			if (memblock_double_array(type) < 0)
+				return -ENOMEM;
+		insert = true;
+		goto repeat;
+	} else {
+		memblock_merge_regions(type);
+		return 0;
 	}
-
-	return 0;
 }
 
 long __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
 {
 	return memblock_add_region(&memblock.memory, base, size);
-
 }
 
 static long __init_memblock __memblock_remove(struct memblock_type *type,
-- 
1.7.6


  parent reply index

Thread overview: 54+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-07-12  9:15 [PATCHSET x86/mm] memblock, x86: Allow node info in memblock and remove x86 specific memblock code Tejun Heo
2011-07-12  9:15 ` [PATCH 01/13] memblock: Remove memblock_memory_can_coalesce() Tejun Heo
2011-07-14 21:31   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:15 ` Tejun Heo [this message]
2011-07-14 21:32   ` [tip:x86/memblock] memblock: Reimplement memblock_add_region() tip-bot for Tejun Heo
2011-07-12  9:15 ` [PATCH 03/13] memblock: Add optional region->nid Tejun Heo
2011-07-14  9:43   ` [PATCH UPDATED " Tejun Heo
2011-07-14 21:32     ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:15 ` [PATCH 04/13] x86: Use HAVE_MEMBLOCK_NODE_MAP Tejun Heo
2011-07-14  1:35   ` H. Peter Anvin
2011-07-14  9:44   ` [PATCH UPDATED " Tejun Heo
2011-07-14 21:33     ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:15 ` [PATCH 05/13] x86: Use __memblock_alloc_base() in early_reserve_e820() Tejun Heo
2011-07-14 21:33   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:15 ` [PATCH 06/13] memblock: Implement for_each_free_mem_range() Tejun Heo
2011-07-14 21:34   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 07/13] x86: Replace memblock_x86_find_in_range_size() with for_each_free_mem_range() Tejun Heo
2011-07-14 21:34   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 08/13] memblock, x86: Make free_all_memory_core_early() explicitly free lowmem only Tejun Heo
2011-07-14 21:35   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 09/13] memblock, x86: Replace __get_free_all_memory_range() with for_each_free_mem_range() Tejun Heo
2011-07-14 21:35   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 10/13] memblock, x86: Reimplement memblock_find_dma_reserve() using iterators Tejun Heo
2011-07-14 21:36   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 11/13] x86: Use absent_pages_in_range() instead of memblock_x86_hole_size() Tejun Heo
2011-07-14 21:36   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 12/13] memblock, x86: Make ARCH_DISCARD_MEMBLOCK a config option Tejun Heo
2011-07-14  9:46   ` [PATCH UPDATED " Tejun Heo
2011-07-14 21:37     ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-12  9:16 ` [PATCH 13/13] memblock, x86: Replace memblock_x86_reserve/free_range() with generic ones Tejun Heo
2011-07-14 20:10   ` H. Peter Anvin
2011-07-14 20:20     ` Tejun Heo
2011-07-14 20:23       ` H. Peter Anvin
2011-07-14 20:32         ` Tejun Heo
2011-07-14 20:38           ` H. Peter Anvin
2011-07-14 20:41             ` Tejun Heo
2011-07-14 20:43               ` H. Peter Anvin
2011-07-14 21:38     ` [tip:x86/memblock] memblock: Cast phys_addr_t to unsigned long long for printf use tip-bot for H. Peter Anvin
2011-07-14 21:37   ` [tip:x86/memblock] memblock, x86: Replace memblock_x86_reserve/free_range() with generic ones tip-bot for Tejun Heo
2011-07-26 21:06   ` [PATCH 13/13] " Yinghai Lu
2011-07-26 21:46     ` Tejun Heo
2011-07-27  0:59       ` Yinghai Lu
2011-07-27  8:07         ` Tejun Heo
2011-07-12 23:26 ` [PATCHSET x86/mm] memblock, x86: Allow node info in memblock and remove x86 specific memblock code Yinghai Lu
2011-07-13  3:21   ` H. Peter Anvin
2011-07-13  9:16     ` Tejun Heo
2011-07-13  9:11   ` Tejun Heo
2011-07-13 19:06     ` Yinghai Lu
2011-07-14  9:42 ` [PATCH 2.5/13] memblock: Use __meminit[data] instead of __init[data] Tejun Heo
2011-07-14 21:00   ` Yinghai Lu
2011-07-14 21:24     ` H. Peter Anvin
2011-07-15  5:45     ` Tejun Heo
2011-07-14 21:32   ` [tip:x86/memblock] " tip-bot for Tejun Heo
2011-07-14  9:49 ` [PATCHSET x86/mm] memblock, x86: Allow node info in memblock and remove x86 specific memblock code Tejun Heo

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1310462166-31469-3-git-send-email-tj@kernel.org \
    --to=tj@kernel.org \
    --cc=benh@kernel.crashing.org \
    --cc=davem@davemloft.net \
    --cc=hpa@zytor.com \
    --cc=linux-arch@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@redhat.com \
    --cc=tglx@linutronix.de \
    --cc=x86@kernel.org \
    --cc=yinghai@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lore.kernel.org/lkml/8 lkml/git/8.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git