From: tip-bot for Tejun Heo <tj@kernel.org>
To: linux-tip-commits@vger.kernel.org
Cc: linux-kernel@vger.kernel.org, hpa@zytor.com, mingo@redhat.com,
benh@kernel.crashing.org, yinghai@kernel.org, tj@kernel.org,
tglx@linutronix.de, hpa@linux.intel.com
Subject: [tip:x86/memblock] memblock: Implement for_each_free_mem_range()
Date: Thu, 14 Jul 2011 21:34:15 GMT [thread overview]
Message-ID: <tip-35fd0808d7d8d001cd72f112e3bca84664b596a3@git.kernel.org> (raw)
In-Reply-To: <1310462166-31469-7-git-send-email-tj@kernel.org>
Commit-ID: 35fd0808d7d8d001cd72f112e3bca84664b596a3
Gitweb: http://git.kernel.org/tip/35fd0808d7d8d001cd72f112e3bca84664b596a3
Author: Tejun Heo <tj@kernel.org>
AuthorDate: Tue, 12 Jul 2011 11:15:59 +0200
Committer: H. Peter Anvin <hpa@linux.intel.com>
CommitDate: Thu, 14 Jul 2011 11:47:47 -0700
memblock: Implement for_each_free_mem_range()
Implement for_each_free_mem_range() which iterates over free memory
areas according to memblock (memory && !reserved). This will be used
to simplify memblock users.
Signed-off-by: Tejun Heo <tj@kernel.org>
Link: http://lkml.kernel.org/r/1310462166-31469-7-git-send-email-tj@kernel.org
Cc: Yinghai Lu <yinghai@kernel.org>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
---
include/linux/memblock.h | 20 ++++++++++++
mm/memblock.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 96 insertions(+), 0 deletions(-)
diff --git a/include/linux/memblock.h b/include/linux/memblock.h
index c36a55d..31def58 100644
--- a/include/linux/memblock.h
+++ b/include/linux/memblock.h
@@ -61,6 +61,26 @@ extern long memblock_remove(phys_addr_t base, phys_addr_t size);
extern long memblock_free(phys_addr_t base, phys_addr_t size);
extern long memblock_reserve(phys_addr_t base, phys_addr_t size);
+extern void __next_free_mem_range(u64 *idx, int nid, phys_addr_t *out_start,
+ phys_addr_t *out_end, int *out_nid);
+
+/**
+ * for_each_free_mem_range - iterate through free memblock areas
+ * @i: u64 used as loop variable
+ * @nid: node selector, %MAX_NUMNODES for all nodes
+ * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
+ * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
+ * @p_nid: ptr to int for nid of the range, can be %NULL
+ *
+ * Walks over free (memory && !reserved) areas of memblock. Available as
+ * soon as memblock is initialized.
+ */
+#define for_each_free_mem_range(i, nid, p_start, p_end, p_nid) \
+ for (i = 0, \
+ __next_free_mem_range(&i, nid, p_start, p_end, p_nid); \
+ i != (u64)ULLONG_MAX; \
+ __next_free_mem_range(&i, nid, p_start, p_end, p_nid))
+
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
extern int memblock_set_node(phys_addr_t base, phys_addr_t size, int nid);
diff --git a/mm/memblock.c b/mm/memblock.c
index e815f4b..c4a8750 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -461,6 +461,82 @@ long __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
return memblock_add_region(_rgn, base, size);
}
+/**
+ * __next_free_mem_range - next function for for_each_free_mem_range()
+ * @idx: pointer to u64 loop variable
+ * @nid: nid: node selector, %MAX_NUMNODES for all nodes
+ * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
+ * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
+ * @p_nid: ptr to int for nid of the range, can be %NULL
+ *
+ * Find the first free area from *@idx which matches @nid, fill the out
+ * parameters, and update *@idx for the next iteration. The lower 32bit of
+ * *@idx contains index into memory region and the upper 32bit indexes the
+ * areas before each reserved region. For example, if reserved regions
+ * look like the following,
+ *
+ * 0:[0-16), 1:[32-48), 2:[128-130)
+ *
+ * The upper 32bit indexes the following regions.
+ *
+ * 0:[0-0), 1:[16-32), 2:[48-128), 3:[130-MAX)
+ *
+ * As both region arrays are sorted, the function advances the two indices
+ * in lockstep and returns each intersection.
+ */
+void __init_memblock __next_free_mem_range(u64 *idx, int nid,
+ phys_addr_t *out_start,
+ phys_addr_t *out_end, int *out_nid)
+{
+ struct memblock_type *mem = &memblock.memory;
+ struct memblock_type *rsv = &memblock.reserved;
+ int mi = *idx & 0xffffffff;
+ int ri = *idx >> 32;
+
+ for ( ; mi < mem->cnt; mi++) {
+ struct memblock_region *m = &mem->regions[mi];
+ phys_addr_t m_start = m->base;
+ phys_addr_t m_end = m->base + m->size;
+
+ /* only memory regions are associated with nodes, check it */
+ if (nid != MAX_NUMNODES && nid != memblock_get_region_node(m))
+ continue;
+
+ /* scan areas before each reservation for intersection */
+ for ( ; ri < rsv->cnt + 1; ri++) {
+ struct memblock_region *r = &rsv->regions[ri];
+ phys_addr_t r_start = ri ? r[-1].base + r[-1].size : 0;
+ phys_addr_t r_end = ri < rsv->cnt ? r->base : ULLONG_MAX;
+
+ /* if ri advanced past mi, break out to advance mi */
+ if (r_start >= m_end)
+ break;
+ /* if the two regions intersect, we're done */
+ if (m_start < r_end) {
+ if (out_start)
+ *out_start = max(m_start, r_start);
+ if (out_end)
+ *out_end = min(m_end, r_end);
+ if (out_nid)
+ *out_nid = memblock_get_region_node(m);
+ /*
+ * The region which ends first is advanced
+ * for the next iteration.
+ */
+ if (m_end <= r_end)
+ mi++;
+ else
+ ri++;
+ *idx = (u32)mi | (u64)ri << 32;
+ return;
+ }
+ }
+ }
+
+ /* signal end of iteration */
+ *idx = ULLONG_MAX;
+}
+
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
/*
* Common iterator interface used to define for_each_mem_range().
next prev parent reply other threads:[~2011-07-14 21:34 UTC|newest]
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 ` [PATCH 02/13] memblock: Reimplement memblock_add_region() Tejun Heo
2011-07-14 21:32 ` [tip:x86/memblock] " 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-bot for Tejun Heo [this message]
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 publicly 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=tip-35fd0808d7d8d001cd72f112e3bca84664b596a3@git.kernel.org \
--to=tj@kernel.org \
--cc=benh@kernel.crashing.org \
--cc=hpa@linux.intel.com \
--cc=hpa@zytor.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-tip-commits@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=tglx@linutronix.de \
--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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).