linux-mm.kvack.org archive mirror
 help / color / mirror / Atom feed
From: Dennis Zhou <dennis@kernel.org>
To: Dennis Zhou <dennis@kernel.org>, Tejun Heo <tj@kernel.org>,
	Christoph Lameter <cl@linux.com>
Cc: Vlad Buslov <vladbu@mellanox.com>,
	kernel-team@fb.com, linux-mm@kvack.org,
	linux-kernel@vger.kernel.org
Subject: [PATCH 03/12] percpu: introduce helper to determine if two regions overlap
Date: Wed, 27 Feb 2019 21:18:30 -0500	[thread overview]
Message-ID: <20190228021839.55779-4-dennis@kernel.org> (raw)
In-Reply-To: <20190228021839.55779-1-dennis@kernel.org>

While block hints were always accurate, it's possible when spanning
across blocks that we miss updating the chunk's contig_hint. Rather than
rely on correctness of the boundaries of hints, do a full overlap
comparison.

Signed-off-by: Dennis Zhou <dennis@kernel.org>
---
 mm/percpu.c | 31 +++++++++++++++++++++++++++----
 1 file changed, 27 insertions(+), 4 deletions(-)

diff --git a/mm/percpu.c b/mm/percpu.c
index 69ca51d238b5..b40112b2fc59 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -546,6 +546,24 @@ static inline int pcpu_cnt_pop_pages(struct pcpu_chunk *chunk, int bit_off,
 	       bitmap_weight(chunk->populated, page_start);
 }
 
+/*
+ * pcpu_region_overlap - determines if two regions overlap
+ * @a: start of first region, inclusive
+ * @b: end of first region, exclusive
+ * @x: start of second region, inclusive
+ * @y: end of second region, exclusive
+ *
+ * This is used to determine if the hint region [a, b) overlaps with the
+ * allocated region [x, y).
+ */
+static inline bool pcpu_region_overlap(int a, int b, int x, int y)
+{
+	if ((x >= a && x < b) || (y > a && y <= b) ||
+	    (x <= a && y >= b))
+		return true;
+	return false;
+}
+
 /**
  * pcpu_chunk_update - updates the chunk metadata given a free area
  * @chunk: chunk of interest
@@ -710,8 +728,11 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
 					PCPU_BITMAP_BLOCK_BITS,
 					s_off + bits);
 
-	if (s_off >= s_block->contig_hint_start &&
-	    s_off < s_block->contig_hint_start + s_block->contig_hint) {
+	if (pcpu_region_overlap(s_block->contig_hint_start,
+				s_block->contig_hint_start +
+				s_block->contig_hint,
+				s_off,
+				s_off + bits)) {
 		/* block contig hint is broken - scan to fix it */
 		pcpu_block_refresh_hint(chunk, s_index);
 	} else {
@@ -764,8 +785,10 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
 	 * contig hint is broken.  Otherwise, it means a smaller space
 	 * was used and therefore the chunk contig hint is still correct.
 	 */
-	if (bit_off >= chunk->contig_bits_start  &&
-	    bit_off < chunk->contig_bits_start + chunk->contig_bits)
+	if (pcpu_region_overlap(chunk->contig_bits_start,
+				chunk->contig_bits_start + chunk->contig_bits,
+				bit_off,
+				bit_off + bits))
 		pcpu_chunk_refresh_hint(chunk);
 }
 
-- 
2.17.1


  parent reply	other threads:[~2019-02-28  2:18 UTC|newest]

Thread overview: 35+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-02-28  2:18 [PATCH 00/12] introduce percpu block scan_hint Dennis Zhou
2019-02-28  2:18 ` [PATCH 01/12] percpu: update free path with correct new free region Dennis Zhou
2019-03-02 12:56   ` Peng Fan
2019-02-28  2:18 ` [PATCH 02/12] percpu: do not search past bitmap when allocating an area Dennis Zhou
2019-03-02 13:32   ` Peng Fan
2019-03-02 22:23     ` Dennis Zhou
2019-03-03  8:41       ` Peng Fan
2019-02-28  2:18 ` Dennis Zhou [this message]
2019-03-02 13:37   ` [PATCH 03/12] percpu: introduce helper to determine if two regions overlap Peng Fan
2019-03-02 22:24     ` Dennis Zhou
2019-02-28  2:18 ` [PATCH 04/12] percpu: manage chunks based on contig_bits instead of free_bytes Dennis Zhou
2019-03-02 13:48   ` Peng Fan
2019-03-02 22:32     ` Dennis Zhou
2019-03-03  8:42       ` Peng Fan
2019-02-28  2:18 ` [PATCH 05/12] percpu: relegate chunks unusable when failing small allocations Dennis Zhou
2019-03-02 13:55   ` Peng Fan
2019-03-02 22:34     ` Dennis Zhou
2019-02-28  2:18 ` [PATCH 06/12] percpu: set PCPU_BITMAP_BLOCK_SIZE to PAGE_SIZE Dennis Zhou
2019-03-03  4:56   ` Peng Fan
2019-02-28  2:18 ` [PATCH 07/12] percpu: add block level scan_hint Dennis Zhou
2019-03-03  6:01   ` Peng Fan
2019-03-03 20:23     ` Dennis Zhou
2019-03-04  9:36       ` Peng Fan
2019-02-28  2:18 ` [PATCH 08/12] percpu: remember largest area skipped during allocation Dennis Zhou
2019-02-28  2:18 ` [PATCH 09/12] percpu: use block scan_hint to only scan forward Dennis Zhou
2019-02-28  2:18 ` [PATCH 10/12] percpu: make pcpu_block_md generic Dennis Zhou
2019-03-03  6:35   ` Peng Fan
2019-02-28  2:18 ` [PATCH 11/12] percpu: convert chunk hints to be based on pcpu_block_md Dennis Zhou
2019-03-03  8:18   ` Peng Fan
2019-03-03 20:22     ` Dennis Zhou
2019-03-04  6:36       ` Peng Fan
2019-02-28  2:18 ` [PATCH 12/12] percpu: use chunk scan_hint to skip some scanning Dennis Zhou
2019-03-03  8:38   ` Peng Fan
2019-02-28 14:47 ` [PATCH 00/12] introduce percpu block scan_hint Vlad Buslov
2019-03-13 20:19 ` Dennis Zhou

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=20190228021839.55779-4-dennis@kernel.org \
    --to=dennis@kernel.org \
    --cc=cl@linux.com \
    --cc=kernel-team@fb.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=tj@kernel.org \
    --cc=vladbu@mellanox.com \
    /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).