From: Dennis Zhou <dennisz@fb.com>
To: Tejun Heo <tj@kernel.org>, Christoph Lameter <cl@linux.com>,
Josef Bacik <josef@toxicpanda.com>
Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org,
kernel-team@fb.com, Dennis Zhou <dennisszhou@gmail.com>
Subject: [PATCH v2 16/23] percpu: add first_bit to keep track of the first free in the bitmap
Date: Mon, 24 Jul 2017 19:02:13 -0400 [thread overview]
Message-ID: <20170724230220.21774-17-dennisz@fb.com> (raw)
In-Reply-To: <20170724230220.21774-1-dennisz@fb.com>
From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>
This patch adds first_bit to keep track of the first free bit in the
bitmap. This hint helps prevent scanning of fully allocated blocks.
Signed-off-by: Dennis Zhou <dennisszhou@gmail.com>
---
mm/percpu-internal.h | 2 +-
mm/percpu-stats.c | 1 +
mm/percpu.c | 17 +++++++++++++++--
3 files changed, 17 insertions(+), 3 deletions(-)
diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h
index 252ae9e..e60e049 100644
--- a/mm/percpu-internal.h
+++ b/mm/percpu-internal.h
@@ -36,7 +36,7 @@ struct pcpu_chunk {
struct pcpu_block_md *md_blocks; /* metadata blocks */
void *data; /* chunk data */
- int first_free; /* no free below this */
+ int first_bit; /* no free below this */
bool immutable; /* no [de]population allowed */
int start_offset; /* the overlap with the previous
region to have a page aligned
diff --git a/mm/percpu-stats.c b/mm/percpu-stats.c
index ad03d73..6142484 100644
--- a/mm/percpu-stats.c
+++ b/mm/percpu-stats.c
@@ -121,6 +121,7 @@ static void chunk_map_stats(struct seq_file *m, struct pcpu_chunk *chunk,
P("nr_alloc", chunk->nr_alloc);
P("max_alloc_size", chunk->max_alloc_size);
P("empty_pop_pages", chunk->nr_empty_pop_pages);
+ P("first_bit", chunk->first_bit);
P("free_bytes", chunk->free_bytes);
P("contig_bytes", chunk->contig_bits * PCPU_MIN_ALLOC_SIZE);
P("sum_frag", sum_frag);
diff --git a/mm/percpu.c b/mm/percpu.c
index 6bddc02..ad70c67 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -420,7 +420,7 @@ static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk)
chunk->contig_bits = 0;
bits = nr_empty_pop_pages = 0;
- pcpu_for_each_unpop_region(chunk->alloc_map, rs, re, 0,
+ pcpu_for_each_unpop_region(chunk->alloc_map, rs, re, chunk->first_bit,
pcpu_chunk_map_bits(chunk)) {
bits = re - rs;
@@ -639,7 +639,8 @@ static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits,
int bit_off, bits;
int re; /* region end */
- pcpu_for_each_unpop_region(chunk->alloc_map, bit_off, re, 0,
+ pcpu_for_each_unpop_region(chunk->alloc_map, bit_off, re,
+ chunk->first_bit,
pcpu_chunk_map_bits(chunk)) {
bits = re - bit_off;
@@ -708,6 +709,13 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits,
chunk->free_bytes -= alloc_bits * PCPU_MIN_ALLOC_SIZE;
+ /* update first free bit */
+ if (bit_off == chunk->first_bit)
+ chunk->first_bit = find_next_zero_bit(
+ chunk->alloc_map,
+ pcpu_chunk_map_bits(chunk),
+ bit_off + alloc_bits);
+
pcpu_block_update_hint_alloc(chunk, bit_off, alloc_bits);
pcpu_chunk_relocate(chunk, oslot);
@@ -743,6 +751,9 @@ static void pcpu_free_area(struct pcpu_chunk *chunk, int off)
/* update metadata */
chunk->free_bytes += bits * PCPU_MIN_ALLOC_SIZE;
+ /* update first free bit */
+ chunk->first_bit = min(chunk->first_bit, bit_off);
+
pcpu_block_update_hint_free(chunk, bit_off, bits);
pcpu_chunk_relocate(chunk, oslot);
@@ -834,6 +845,8 @@ static struct pcpu_chunk * __init pcpu_alloc_first_chunk(unsigned long tmp_addr,
set_bit(0, chunk->bound_map);
set_bit(offset_bits, chunk->bound_map);
+ chunk->first_bit = offset_bits;
+
pcpu_block_update_hint_alloc(chunk, 0, offset_bits);
}
--
2.9.3
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2017-07-24 23:02 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-07-24 23:01 [PATCH v2 00/23] percpu: replace percpu area map allocator with bitmap allocator Dennis Zhou
2017-07-24 23:01 ` [PATCH v2 01/23] percpu: setup_first_chunk enforce dynamic region must exist Dennis Zhou
2017-07-25 18:03 ` Josef Bacik
2017-07-24 23:01 ` [PATCH v2 02/23] percpu: introduce start_offset to pcpu_chunk Dennis Zhou
2017-07-25 18:04 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 03/23] percpu: remove has_reserved from pcpu_chunk Dennis Zhou
2017-07-25 18:05 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 04/23] percpu: setup_first_chunk remove dyn_size and consolidate logic Dennis Zhou
2017-07-25 18:07 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 05/23] percpu: unify allocation of schunk and dchunk Dennis Zhou
2017-07-25 18:10 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 06/23] percpu: end chunk area maps page aligned for the populated bitmap Dennis Zhou
2017-07-25 18:14 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 07/23] percpu: setup_first_chunk rename schunk/dchunk to chunk Dennis Zhou
2017-07-25 18:15 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 08/23] percpu: modify base_addr to be region specific Dennis Zhou
2017-07-25 18:24 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 09/23] percpu: combine percpu address checks Dennis Zhou
2017-07-25 18:25 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 10/23] percpu: change the number of pages marked in the first_chunk pop bitmap Dennis Zhou
2017-07-25 18:27 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 11/23] percpu: introduce nr_empty_pop_pages to help empty page accounting Dennis Zhou
2017-07-25 18:29 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 12/23] percpu: increase minimum percpu allocation size and align first regions Dennis Zhou
2017-07-25 18:33 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 13/23] percpu: generalize bitmap (un)populated iterators Dennis Zhou
2017-07-25 18:35 ` Josef Bacik
2017-07-26 14:08 ` Tejun Heo
2017-07-24 23:02 ` [PATCH v2 14/23] percpu: replace area map allocator with bitmap allocator Dennis Zhou
2017-07-25 17:36 ` [percpu] ec1f2e572e: WARNING:at_lib/list_debug.c:#__list_add_valid kernel test robot
2017-07-25 19:15 ` [PATCH v2 14/23] percpu: replace area map allocator with bitmap allocator Josef Bacik
2017-07-25 20:24 ` [PATCH updated 14/23] percpu: replace area map allocator with bitmap Dennis Zhou
2017-07-24 23:02 ` [PATCH v2 15/23] percpu: introduce bitmap metadata blocks Dennis Zhou
2017-07-25 19:20 ` Josef Bacik
2017-07-24 23:02 ` Dennis Zhou [this message]
2017-07-25 19:21 ` [PATCH v2 16/23] percpu: add first_bit to keep track of the first free in the bitmap Josef Bacik
2017-07-24 23:02 ` [PATCH v2 17/23] percpu: skip chunks if the alloc does not fit in the contig hint Dennis Zhou
2017-07-25 19:25 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 18/23] percpu: keep track of the best offset for contig hints Dennis Zhou
2017-07-25 19:29 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 19/23] percpu: update alloc path to only scan if contig hints are broken Dennis Zhou
2017-07-25 19:32 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 20/23] percpu: update free path to take advantage of contig hints Dennis Zhou
2017-07-25 19:38 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 21/23] percpu: use metadata blocks to update the chunk contig hint Dennis Zhou
2017-07-25 19:40 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 22/23] percpu: update pcpu_find_block_fit to use an iterator Dennis Zhou
2017-07-25 19:47 ` Josef Bacik
2017-07-24 23:02 ` [PATCH v2 23/23] percpu: update header to contain bitmap allocator explanation Dennis Zhou
2017-07-25 19:49 ` Josef Bacik
2017-07-26 21:42 ` 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=20170724230220.21774-17-dennisz@fb.com \
--to=dennisz@fb.com \
--cc=cl@linux.com \
--cc=dennisszhou@gmail.com \
--cc=josef@toxicpanda.com \
--cc=kernel-team@fb.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=tj@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).