Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1688037 > unrolled thread

[PATCH 00/10] percpu: replace percpu area map allocator with bitmap allocator

Back to article view | Back to linux.kernel

Contents

  [PATCH 00/10] percpu: replace percpu area map allocator with bitmap allocator Dennis Zhou <dennisz@fb.com> - 2017-07-16 04:30 +0200
    [PATCH 07/10] percpu: fix misnomer in schunk/dchunk variable names Dennis Zhou <dennisz@fb.com> - 2017-07-16 04:30 +0200
      Re: [PATCH 07/10] percpu: fix misnomer in schunk/dchunk variable  names Tejun Heo <tj@kernel.org> - 2017-07-17 21:20 +0200
    [PATCH 10/10] percpu: add optimizations on allocation path for the bitmap allocator Dennis Zhou <dennisz@fb.com> - 2017-07-16 04:30 +0200
      Re: [PATCH 10/10] percpu: add optimizations on allocation path for  the bitmap allocator Tejun Heo <tj@kernel.org> - 2017-07-18 01:40 +0200
    [PATCH 06/10] percpu: modify base_addr to be region specific Dennis Zhou <dennisz@fb.com> - 2017-07-16 04:30 +0200
      Re: [PATCH 06/10] percpu: modify base_addr to be region specific Tejun Heo <tj@kernel.org> - 2017-07-17 21:00 +0200
      Re: [PATCH 06/10] percpu: modify base_addr to be region specific Josef Bacik <josef@toxicpanda.com> - 2017-07-18 21:30 +0200
        Re: [PATCH 06/10] percpu: modify base_addr to be region specific Matthew Wilcox <willy@infradead.org> - 2017-07-18 21:40 +0200
          Re: [PATCH 06/10] percpu: modify base_addr to be region specific Josef Bacik <josef@toxicpanda.com> - 2017-07-19 16:30 +0200
    Re: [PATCH 09/10] percpu: replace area map allocator with bitmap  allocator Tejun Heo <tj@kernel.org> - 2017-07-18 01:30 +0200
    Re: [PATCH 00/10] percpu: replace percpu area map allocator with  bitmap allocator Josef Bacik <josef@toxicpanda.com> - 2017-07-18 21:20 +0200
    Re: [PATCH 09/10] percpu: replace area map allocator with bitmap  allocator Josef Bacik <josef@toxicpanda.com> - 2017-07-19 21:20 +0200

#1688037 — [PATCH 00/10] percpu: replace percpu area map allocator with bitmap allocator

Hi everyone,

The Linux kernel percpu memory allocator is responsible for managing
percpu memory. It allocates memory from chunks of percpu areas and uses a
simple first-fit area allocator to manage allocations inside each chunk.
There now exist use cases where allocating and deallocating a million or
more objects occurs making the current implementation inadequate.

The two primary problems with the current area map allocator are:
  1. The backing data structure is an array of the areas. To manage this
     array, it is possible to need to memmove a large portion of it.
  2. On allocation, chunks are considered based on the contig_hint. It is
     possible that the contig_hint may be large enough while the alignment 
     could not meet the request. This causes scanning over every free
     fragment that could spill over into scanning chunks.

The primary considerations for the new allocator were the following:
 - Remove the memmove operation from the critical path
 - Be conservative with additional use of memory
 - Provide consistency in performance and memory footprint
 - Focus on small allocations < 64 bytes

This patchset introduces a simple bitmap allocator backed by metadata
blocks as a replacement for the area map allocator for percpu memory. Each
chunk has an allocation bitmap, a boundary bitmap, and a set of metadata
blocks. The allocation map serves as the ground truth for allocations
while the boundary map serves as a way to distinguish between consecutive
allocations. The minimum allocation size has been increased to 4-bytes.

The key property behind the bitmap allocator is its static metadata. The
main problem it solves is that a memmove is no longer part of the critical
path for freeing, which was the primary source of latency. This also helps
bound the metadata overhead. The area map allocator prior required an
integer per allocation. This may be beneficial with larger allocations,
but as mentioned, allocating a significant number of small objects is
becoming more common. This causes worst-case scenarios for metadata
overhead.

There is one caveat with this implementation. In an effort to make freeing
fast, the only time metadata is updated on the free path is if a whole
block becomes free or the freed area spans across metadata blocks. This
causes the chunk’s contig_hint to be potentially smaller than what it
could allocate by up to a block. If the chunk’s contig_hint is smaller
than a block, a check occurs and the hint is kept accurate. Metadata is
always kept accurate on allocation and therefore the situation where a
chunk has a larger contig_hint than available will never occur.

I have primarily done testing against a simple workload of allocation of
1 million objects of varying size. Deallocation was done by in order,
alternating, and in reverse. These numbers were collected after rebasing
ontop of a80099a152. I present the worst-case numbers here:

  Area Map Allocator:

        Object Size | Alloc Time (ms) | Free Time (ms)
        ----------------------------------------------
              4B    |        335      |     4960
             16B    |        485      |     1150
             64B    |        445      |      280
            128B    |        505      |      177
           1024B    |       3385      |      140

  Bitmap Allocator:

        Object Size | Alloc Time (ms) | Free Time (ms)
        ----------------------------------------------
              4B    |        725      |       70
             16B    |        760      |       70
             64B    |        855      |       80
            128B    |        910      |       90
           1024B    |       3770      |      260

This data demonstrates the inability for the area map allocator to
handle less than ideal situations. In the best case of reverse
deallocation, the area map allocator was able to perform within range
of the bitmap allocator. In the worst case situation, freeing took
nearly 5 seconds for 1 million 4-byte objects. The bitmap allocator
dramatically improves the consistency of the free path. The small
allocations performed nearly identical regardless of the freeing
pattern.

While it does add to the allocation latency, the allocation scenario
here is optimal for the area map allocator. The second problem of
additional scanning can result in the area map allocator completing in
52 minutes. The same workload takes only 14 seconds to complete for the
bitmap allocator. This was produced under a more contrived scenario of
allocating 1 milion 4-byte objects with 8-byte alignment.

Alternative implementations were evaluated including: linked lists, trees,
and buddy systems. These all suffer from either high metadata overhead for
small allocations or from the amplified costs of fragmentation with percpu
memory.

This patchset contains the following ten patches:

  0001-percpu-pcpu-stats-change-void-buffer-to-int-buffer.patch
  0002-percpu-change-the-format-for-percpu_stats-output.patch
  0003-percpu-expose-pcpu_nr_empty_pop_pages-in-pcpu_stats.patch
  0004-percpu-update-the-header-comment-and-pcpu_build_allo.patch
  0005-percpu-change-reserved_size-to-end-page-aligned.patch
  0006-percpu-modify-base_addr-to-be-region-specific.patch
  0007-percpu-fix-misnomer-in-schunk-dchunk-variable-names.patch
  0008-percpu-change-the-number-of-pages-marked-in-the-firs.patch
  0009-percpu-replace-area-map-allocator-with-bitmap-alloca.patch
  0010-percpu-add-optimizations-on-allocation-path-for-the-.patch

0001-0002 are minor fixes to percpu_stats. 0003 exposes a new field via
percpu_stats. 0004 updates comments in the percpu allocator. 0005-0006 are
preparatory patches that modify the first_chunk's base_addr management and
the reserved region. 0007 does some variable renaming for clarity. 0008
modifies the population map and the variables surrounding population. 0009
is the bitmap allocator backed by metadata blocks implementation. 0010
adds two optimizations on top of the allocator.

This patchset is on top of linus#master a80099a152.

diffstats below:

Dennis Zhou (Facebook) (10):
  percpu: pcpu-stats change void buffer to int buffer
  percpu: change the format for percpu_stats output
  percpu: expose pcpu_nr_empty_pop_pages in pcpu_stats
  percpu: update the header comment and pcpu_build_alloc_info comments
  percpu: change reserved_size to end page aligned
  percpu: modify base_addr to be region specific
  percpu: fix misnomer in schunk/dchunk variable names
  percpu: change the number of pages marked in the first_chunk bitmaps
  percpu: replace area map allocator with bitmap allocator
  percpu: add optimizations on allocation path for the bitmap allocator

 arch/ia64/mm/contig.c    |    3 +-
 arch/ia64/mm/discontig.c |    3 +-
 include/linux/percpu.h   |   43 +-
 init/main.c              |    1 -
 mm/percpu-internal.h     |   84 ++-
 mm/percpu-stats.c        |  111 ++--
 mm/percpu.c              | 1461 +++++++++++++++++++++++++++++-----------------
 7 files changed, 1107 insertions(+), 599 deletions(-)

Thanks,
Dennis

[toc] | [next] | [standalone]

#1688038 — [PATCH 07/10] percpu: fix misnomer in schunk/dchunk variable names

From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>

With moving the base_addr in the chunks responsible for serving the
first chunk up, the use of schunk/dchunk in pcpu_setup_first_chunk no
longer makes sense. This makes the linking in the first chunk code not
rely on a ternary and renames the variables to a shared variable, chunk,
because the allocation path is sequential.

Signed-off-by: Dennis Zhou <dennisszhou@gmail.com>
---
 mm/percpu.c | 96 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 48 insertions(+), 48 deletions(-)

diff --git a/mm/percpu.c b/mm/percpu.c
index c74ad68..9dd28a2 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -1597,7 +1597,7 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
 	static int dmap[PERCPU_DYNAMIC_EARLY_SLOTS] __initdata;
 	size_t dyn_size = ai->dyn_size;
 	size_t size_sum = ai->static_size + ai->reserved_size + dyn_size;
-	struct pcpu_chunk *schunk, *dchunk = NULL;
+	struct pcpu_chunk *chunk;
 	unsigned long *group_offsets;
 	size_t *group_sizes;
 	unsigned long *unit_off;
@@ -1709,13 +1709,13 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
 		INIT_LIST_HEAD(&pcpu_slot[i]);
 
 	/*
-	 * Initialize static chunk.
-	 * The static region is dropped as those addresses are already
-	 * allocated and do not rely on chunk->base_addr.
-	 * reserved_size == 0:
-	 *      the static chunk covers the dynamic area
-	 * reserved_size > 0:
-	 *      the static chunk covers the reserved area
+	 * Initialize first chunk.
+	 * pcpu_first_chunk will always manage the dynamic region of the
+	 * first chunk.  The static region is dropped as those addresses
+	 * are already allocated and do not rely on chunk->base_addr.
+	 *
+	 * ai->reserved == 0:
+	 *	reserved_chunk == NULL;
 	 *
 	 * If the static area is not page aligned, the region adjacent
 	 * to the static area must have its base_addr be offset into
@@ -1730,61 +1730,61 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
 	map_size_bytes = (ai->reserved_size ?: ai->dyn_size) +
 			 pcpu_reserved_offset;
 
-	/* schunk allocation */
-	schunk = memblock_virt_alloc(pcpu_chunk_struct_size, 0);
-	INIT_LIST_HEAD(&schunk->list);
-	INIT_LIST_HEAD(&schunk->map_extend_list);
-	schunk->base_addr = (void *)aligned_addr;
-	schunk->map = smap;
-	schunk->map_alloc = ARRAY_SIZE(smap);
-	schunk->immutable = true;
-	bitmap_fill(schunk->populated, pcpu_unit_pages);
-	schunk->nr_populated = pcpu_unit_pages;
+	/* chunk adjacent to static region allocation */
+	chunk = memblock_virt_alloc(pcpu_chunk_struct_size, 0);
+	INIT_LIST_HEAD(&chunk->list);
+	INIT_LIST_HEAD(&chunk->map_extend_list);
+	chunk->base_addr = (void *)aligned_addr;
+	chunk->map = smap;
+	chunk->map_alloc = ARRAY_SIZE(smap);
+	chunk->immutable = true;
+	bitmap_fill(chunk->populated, pcpu_unit_pages);
+	chunk->nr_populated = pcpu_unit_pages;
 
-	schunk->nr_pages = map_size_bytes >> PAGE_SHIFT;
+	chunk->nr_pages = map_size_bytes >> PAGE_SHIFT;
 
 	if (ai->reserved_size) {
-		schunk->free_size = ai->reserved_size;
-		pcpu_reserved_chunk = schunk;
+		chunk->free_size = ai->reserved_size;
+		pcpu_reserved_chunk = chunk;
 	} else {
-		schunk->free_size = dyn_size;
+		chunk->free_size = dyn_size;
 		dyn_size = 0;			/* dynamic area covered */
 	}
-	schunk->contig_hint = schunk->free_size;
+	chunk->contig_hint = chunk->free_size;
 
 	if (pcpu_reserved_offset) {
-		schunk->has_reserved = true;
-		schunk->map[0] = 1;
-		schunk->map[1] = pcpu_reserved_offset;
-		schunk->map_used = 1;
+		chunk->has_reserved = true;
+		chunk->map[0] = 1;
+		chunk->map[1] = pcpu_reserved_offset;
+		chunk->map_used = 1;
 	}
-	if (schunk->free_size)
-		schunk->map[++schunk->map_used] = map_size_bytes;
-	schunk->map[schunk->map_used] |= 1;
+	if (chunk->free_size)
+		chunk->map[++chunk->map_used] = map_size_bytes;
+	chunk->map[chunk->map_used] |= 1;
 
-	/* init dynamic chunk if necessary */
+	/* init dynamic region of first chunk if necessary */
 	if (dyn_size) {
-		dchunk = memblock_virt_alloc(pcpu_chunk_struct_size, 0);
-		INIT_LIST_HEAD(&dchunk->list);
-		INIT_LIST_HEAD(&dchunk->map_extend_list);
-		dchunk->base_addr = base_addr + ai->static_size +
+		chunk = memblock_virt_alloc(pcpu_chunk_struct_size, 0);
+		INIT_LIST_HEAD(&chunk->list);
+		INIT_LIST_HEAD(&chunk->map_extend_list);
+		chunk->base_addr = base_addr + ai->static_size +
 				    ai->reserved_size;
-		dchunk->map = dmap;
-		dchunk->map_alloc = ARRAY_SIZE(dmap);
-		dchunk->immutable = true;
-		bitmap_fill(dchunk->populated, pcpu_unit_pages);
-		dchunk->nr_populated = pcpu_unit_pages;
-
-		dchunk->contig_hint = dchunk->free_size = dyn_size;
-		dchunk->map[0] = 0;
-		dchunk->map[1] = dchunk->free_size | 1;
-		dchunk->map_used = 1;
-
-		dchunk->nr_pages = dyn_size >> PAGE_SHIFT;
+		chunk->map = dmap;
+		chunk->map_alloc = ARRAY_SIZE(dmap);
+		chunk->immutable = true;
+		bitmap_fill(chunk->populated, pcpu_unit_pages);
+		chunk->nr_populated = pcpu_unit_pages;
+
+		chunk->contig_hint = chunk->free_size = dyn_size;
+		chunk->map[0] = 0;
+		chunk->map[1] = chunk->free_size | 1;
+		chunk->map_used = 1;
+
+		chunk->nr_pages = dyn_size >> PAGE_SHIFT;
 	}
 
 	/* link the first chunk in */
-	pcpu_first_chunk = dchunk ?: schunk;
+	pcpu_first_chunk = chunk;
 	pcpu_nr_empty_pop_pages +=
 		pcpu_count_occupied_pages(pcpu_first_chunk, 1);
 	pcpu_chunk_relocate(pcpu_first_chunk, -1);
-- 
2.9.3

[toc] | [prev] | [next] | [standalone]

#1689375 — Re: [PATCH 07/10] percpu: fix misnomer in schunk/dchunk variable names

On Sat, Jul 15, 2017 at 10:23:12PM -0400, Dennis Zhou wrote:
> From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>
> 
> With moving the base_addr in the chunks responsible for serving the
> first chunk up, the use of schunk/dchunk in pcpu_setup_first_chunk no
> longer makes sense. This makes the linking in the first chunk code not
> rely on a ternary and renames the variables to a shared variable, chunk,
> because the allocation path is sequential.

Ah cool, please disregard my previous comment on the misnomer.  You
can explain in the previous patch's description that a follow-up patch
will resolve the situation tho.

> @@ -1709,13 +1709,13 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  		INIT_LIST_HEAD(&pcpu_slot[i]);
>  
>  	/*
> +	 * Initialize first chunk.
> +	 * pcpu_first_chunk will always manage the dynamic region of the
> +	 * first chunk.  The static region is dropped as those addresses

Would "not covered by any chunk" be clearer than "dropped"?

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1688039 — [PATCH 10/10] percpu: add optimizations on allocation path for the bitmap allocator

From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>

This patch adds two optimizations to the allocation path. The first is
to not consider a chunk if the requested allocation cannot fit in the
chunk's contig_hint. The benefit is that this avoids unncessary scanning
over a chunk as the assumption is memory pressure is high and creating a
new chunk has minimal consequences. This may fail when the contig_hint
has poor alignment, but again we fall back on the high memory pressure
argument.

The second is just a fail-fast mechanism. When allocating, a offset is
identified within a block and then scanning is used to see if it will
fit. An offset should never be returned unless it is known to fit, so
here we just bind the scanning to the size of a block.

Signed-off-by: Dennis Zhou <dennisszhou@gmail.com>
---
 mm/percpu.c | 22 ++++++++++++++++------
 1 file changed, 16 insertions(+), 6 deletions(-)

diff --git a/mm/percpu.c b/mm/percpu.c
index 569df63..7496571 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -885,6 +885,12 @@ static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int bit_size,
 
 	lockdep_assert_held(&pcpu_lock);
 
+	/* check chunk->contig_hint to see if alloc can fit - see note above */
+	block_off = ALIGN(chunk->contig_hint_start, align) -
+		    chunk->contig_hint_start;
+	if (block_off + bit_size > chunk->contig_hint)
+		return -1;
+
 	cur_free = block_off = 0;
 	s_index = chunk->first_free_block;
 	for (i = chunk->first_free_block; i < pcpu_nr_pages_to_blocks(chunk);
@@ -973,19 +979,23 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int bit_size,
 			   size_t align, int start)
 {
 	size_t align_mask = (align) ? (align - 1) : 0;
-	int i, bit_off, oslot;
+	int i, bit_off, end, oslot;
 	struct pcpu_bitmap_md *block;
 
 	lockdep_assert_held(&pcpu_lock);
 
 	oslot = pcpu_chunk_slot(chunk);
 
-	/* search to find fit */
-	bit_off = bitmap_find_next_zero_area(chunk->alloc_map,
-					     pcpu_nr_pages_to_bits(chunk),
-					     start, bit_size, align_mask);
+	/*
+	 * Search to find fit.  The search for the start is limited to
+	 * be within a block_size, but should in reality never be hit
+	 * as the contig_hint should be a valid placement.
+	 */
+	end = start + bit_size + PCPU_BITMAP_BLOCK_SIZE;
+	bit_off = bitmap_find_next_zero_area(chunk->alloc_map, end, start,
+					     bit_size, align_mask);
 
-	if (bit_off >= pcpu_nr_pages_to_bits(chunk))
+	if (bit_off >= end)
 		return -1;
 
 	/* update alloc map */
-- 
2.9.3

[toc] | [prev] | [next] | [standalone]

#1689566 — Re: [PATCH 10/10] percpu: add optimizations on allocation path for the bitmap allocator

On Sat, Jul 15, 2017 at 10:23:15PM -0400, Dennis Zhou wrote:
> From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>
> 
> This patch adds two optimizations to the allocation path. The first is
> to not consider a chunk if the requested allocation cannot fit in the
> chunk's contig_hint. The benefit is that this avoids unncessary scanning
> over a chunk as the assumption is memory pressure is high and creating a
> new chunk has minimal consequences. This may fail when the contig_hint
> has poor alignment, but again we fall back on the high memory pressure
> argument.
> 
> The second is just a fail-fast mechanism. When allocating, a offset is
> identified within a block and then scanning is used to see if it will
> fit. An offset should never be returned unless it is known to fit, so
> here we just bind the scanning to the size of a block.
> 
> Signed-off-by: Dennis Zhou <dennisszhou@gmail.com>

Looks good to me and there's nothing wrong with these two
optimizations being in a separate patch but they might be too little
to help reviewing / debugging in any noticeable way.  It'd be great if
more significant parts can be separated out.  If not, this is fine
too.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1688040 — [PATCH 06/10] percpu: modify base_addr to be region specific

From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>

Originally, the first chunk is served by up to three chunks, each given
a region they are responsible for. Despite this, the arithmetic was based
off of the base_addr making it require offsets or be overly inclusive.
This patch changes percpu checks for first chunk to consider the only
the dynamic region and the reserved check to be only the reserved
region. There is no impact here besides making these checks a little
more accurate.

This patch also adds the ground work increasing the minimum allocation
size to 4 bytes. The new field nr_pages in pcpu_chunk will be used to
keep track of the number of pages the bitmap serves. The arithmetic for
identifying first chunk and reserved chunk reflect this change.

Signed-off-by: Dennis Zhou <dennisszhou@gmail.com>
---
 include/linux/percpu.h |   4 ++
 mm/percpu-internal.h   |  12 +++--
 mm/percpu.c            | 127 ++++++++++++++++++++++++++++++++++---------------
 3 files changed, 100 insertions(+), 43 deletions(-)

diff --git a/include/linux/percpu.h b/include/linux/percpu.h
index 98a371c..a5cedcd 100644
--- a/include/linux/percpu.h
+++ b/include/linux/percpu.h
@@ -21,6 +21,10 @@
 /* minimum unit size, also is the maximum supported allocation size */
 #define PCPU_MIN_UNIT_SIZE		PFN_ALIGN(32 << 10)
 
+/* minimum allocation size and shift in bytes */
+#define PCPU_MIN_ALLOC_SIZE		(1 << PCPU_MIN_ALLOC_SHIFT)
+#define PCPU_MIN_ALLOC_SHIFT		2
+
 /*
  * Percpu allocator can serve percpu allocations before slab is
  * initialized which allows slab to depend on the percpu allocator.
diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h
index c9158a4..56e1aba 100644
--- a/mm/percpu-internal.h
+++ b/mm/percpu-internal.h
@@ -23,11 +23,12 @@ struct pcpu_chunk {
 	void			*data;		/* chunk data */
 	int			first_free;	/* no free below this */
 	bool			immutable;	/* no [de]population allowed */
-	bool			has_reserved;	/* Indicates if chunk has reserved space
-						   at the beginning. Reserved chunk will
-						   contain reservation for static chunk.
-						   Dynamic chunk will contain reservation
-						   for static and reserved chunks. */
+	bool			has_reserved;	/* indicates if the region this chunk
+						   is responsible for overlaps with
+						   the prior adjacent region */
+
+	int                     nr_pages;       /* # of PAGE_SIZE pages served
+						   by this chunk */
 	int			nr_populated;	/* # of populated pages */
 	unsigned long		populated[];	/* populated bitmap */
 };
@@ -40,6 +41,7 @@ extern int pcpu_nr_empty_pop_pages;
 
 extern struct pcpu_chunk *pcpu_first_chunk;
 extern struct pcpu_chunk *pcpu_reserved_chunk;
+extern unsigned long pcpu_reserved_offset;
 
 #ifdef CONFIG_PERCPU_STATS
 
diff --git a/mm/percpu.c b/mm/percpu.c
index 7704db9..c74ad68 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -144,14 +144,14 @@ static const size_t *pcpu_group_sizes __ro_after_init;
 struct pcpu_chunk *pcpu_first_chunk __ro_after_init;
 
 /*
- * Optional reserved chunk.  This chunk reserves part of the first
- * chunk and serves it for reserved allocations.  The amount of
- * reserved offset is in pcpu_reserved_chunk_limit.  When reserved
- * area doesn't exist, the following variables contain NULL and 0
- * respectively.
+ * Optional reserved chunk.  This is the part of the first chunk that
+ * serves reserved allocations.  The pcpu_reserved_offset is the amount
+ * the pcpu_reserved_chunk->base_addr is push back into the static
+ * region for the base_addr to be page aligned.  When the reserved area
+ * doesn't exist, the following variables contain NULL and 0 respectively.
  */
 struct pcpu_chunk *pcpu_reserved_chunk __ro_after_init;
-static int pcpu_reserved_chunk_limit __ro_after_init;
+unsigned long pcpu_reserved_offset __ro_after_init;
 
 DEFINE_SPINLOCK(pcpu_lock);	/* all internal data structures */
 static DEFINE_MUTEX(pcpu_alloc_mutex);	/* chunk create/destroy, [de]pop, map ext */
@@ -184,19 +184,32 @@ static void pcpu_schedule_balance_work(void)
 		schedule_work(&pcpu_balance_work);
 }
 
+/*
+ * Static addresses should never be passed into the allocator.  They
+ * are accessed using the group_offsets and therefore do not rely on
+ * chunk->base_addr.
+ */
 static bool pcpu_addr_in_first_chunk(void *addr)
 {
 	void *first_start = pcpu_first_chunk->base_addr;
 
-	return addr >= first_start && addr < first_start + pcpu_unit_size;
+	return addr >= first_start &&
+	       addr < first_start +
+	       pcpu_first_chunk->nr_pages * PAGE_SIZE;
 }
 
 static bool pcpu_addr_in_reserved_chunk(void *addr)
 {
-	void *first_start = pcpu_first_chunk->base_addr;
+	void *first_start;
 
-	return addr >= first_start &&
-		addr < first_start + pcpu_reserved_chunk_limit;
+	if (!pcpu_reserved_chunk)
+		return false;
+
+	first_start = pcpu_reserved_chunk->base_addr;
+
+	return addr >= first_start + pcpu_reserved_offset &&
+	       addr < first_start +
+	       pcpu_reserved_chunk->nr_pages * PAGE_SIZE;
 }
 
 static int __pcpu_size_to_slot(int size)
@@ -237,11 +250,16 @@ static int __maybe_unused pcpu_page_idx(unsigned int cpu, int page_idx)
 	return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx;
 }
 
+static unsigned long pcpu_unit_page_offset(unsigned int cpu, int page_idx)
+{
+	return pcpu_unit_offsets[cpu] + (page_idx << PAGE_SHIFT);
+}
+
 static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
 				     unsigned int cpu, int page_idx)
 {
-	return (unsigned long)chunk->base_addr + pcpu_unit_offsets[cpu] +
-		(page_idx << PAGE_SHIFT);
+	return (unsigned long)chunk->base_addr +
+		pcpu_unit_page_offset(cpu, page_idx);
 }
 
 static void __maybe_unused pcpu_next_unpop(struct pcpu_chunk *chunk,
@@ -737,6 +755,8 @@ static struct pcpu_chunk *pcpu_alloc_chunk(void)
 	chunk->free_size = pcpu_unit_size;
 	chunk->contig_hint = pcpu_unit_size;
 
+	chunk->nr_pages = pcpu_unit_pages;
+
 	return chunk;
 }
 
@@ -824,18 +844,20 @@ static int __init pcpu_verify_alloc_info(const struct pcpu_alloc_info *ai);
  * pcpu_chunk_addr_search - determine chunk containing specified address
  * @addr: address for which the chunk needs to be determined.
  *
+ * This is an internal function that handles all but static allocations.
+ * Static percpu address values should never be passed into the allocator.
+ *
  * RETURNS:
  * The address of the found chunk.
  */
 static struct pcpu_chunk *pcpu_chunk_addr_search(void *addr)
 {
 	/* is it in the first chunk? */
-	if (pcpu_addr_in_first_chunk(addr)) {
-		/* is it in the reserved area? */
-		if (pcpu_addr_in_reserved_chunk(addr))
-			return pcpu_reserved_chunk;
+	if (pcpu_addr_in_first_chunk(addr))
 		return pcpu_first_chunk;
-	}
+	/* is it in the reserved chunk? */
+	if (pcpu_addr_in_reserved_chunk(addr))
+		return pcpu_reserved_chunk;
 
 	/*
 	 * The address is relative to unit0 which might be unused and
@@ -1366,10 +1388,17 @@ phys_addr_t per_cpu_ptr_to_phys(void *addr)
 	 * The following test on unit_low/high isn't strictly
 	 * necessary but will speed up lookups of addresses which
 	 * aren't in the first chunk.
+	 *
+	 * The address check is of high granularity checking against full
+	 * chunk sizes.  pcpu_base_addr points to the beginning of the first
+	 * chunk including the static region.  This allows us to examine all
+	 * regions of the first chunk. Assumes good intent as the first
+	 * chunk may not be full (ie. < pcpu_unit_pages in size).
 	 */
-	first_low = pcpu_chunk_addr(pcpu_first_chunk, pcpu_low_unit_cpu, 0);
-	first_high = pcpu_chunk_addr(pcpu_first_chunk, pcpu_high_unit_cpu,
-				     pcpu_unit_pages);
+	first_low = (unsigned long) pcpu_base_addr +
+		    pcpu_unit_page_offset(pcpu_low_unit_cpu, 0);
+	first_high = (unsigned long) pcpu_base_addr +
+		     pcpu_unit_page_offset(pcpu_high_unit_cpu, pcpu_unit_pages);
 	if ((unsigned long)addr >= first_low &&
 	    (unsigned long)addr < first_high) {
 		for_each_possible_cpu(cpu) {
@@ -1575,6 +1604,8 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
 	unsigned int cpu;
 	int *unit_map;
 	int group, unit, i;
+	unsigned long tmp_addr, aligned_addr;
+	unsigned long map_size_bytes;
 
 #define PCPU_SETUP_BUG_ON(cond)	do {					\
 	if (unlikely(cond)) {						\
@@ -1678,46 +1709,66 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
 		INIT_LIST_HEAD(&pcpu_slot[i]);
 
 	/*
-	 * Initialize static chunk.  If reserved_size is zero, the
-	 * static chunk covers static area + dynamic allocation area
-	 * in the first chunk.  If reserved_size is not zero, it
-	 * covers static area + reserved area (mostly used for module
-	 * static percpu allocation).
+	 * Initialize static chunk.
+	 * The static region is dropped as those addresses are already
+	 * allocated and do not rely on chunk->base_addr.
+	 * reserved_size == 0:
+	 *      the static chunk covers the dynamic area
+	 * reserved_size > 0:
+	 *      the static chunk covers the reserved area
+	 *
+	 * If the static area is not page aligned, the region adjacent
+	 * to the static area must have its base_addr be offset into
+	 * the static area to have it be page aligned.  The overlap is
+	 * then allocated preserving the alignment in the metadata for
+	 * the actual region.
 	 */
+	tmp_addr = (unsigned long)base_addr + ai->static_size;
+	aligned_addr = tmp_addr & PAGE_MASK;
+	pcpu_reserved_offset = tmp_addr - aligned_addr;
+
+	map_size_bytes = (ai->reserved_size ?: ai->dyn_size) +
+			 pcpu_reserved_offset;
+
+	/* schunk allocation */
 	schunk = memblock_virt_alloc(pcpu_chunk_struct_size, 0);
 	INIT_LIST_HEAD(&schunk->list);
 	INIT_LIST_HEAD(&schunk->map_extend_list);
-	schunk->base_addr = base_addr;
+	schunk->base_addr = (void *)aligned_addr;
 	schunk->map = smap;
 	schunk->map_alloc = ARRAY_SIZE(smap);
 	schunk->immutable = true;
 	bitmap_fill(schunk->populated, pcpu_unit_pages);
 	schunk->nr_populated = pcpu_unit_pages;
 
+	schunk->nr_pages = map_size_bytes >> PAGE_SHIFT;
+
 	if (ai->reserved_size) {
 		schunk->free_size = ai->reserved_size;
 		pcpu_reserved_chunk = schunk;
-		pcpu_reserved_chunk_limit = ai->static_size + ai->reserved_size;
 	} else {
 		schunk->free_size = dyn_size;
 		dyn_size = 0;			/* dynamic area covered */
 	}
 	schunk->contig_hint = schunk->free_size;
 
-	schunk->map[0] = 1;
-	schunk->map[1] = ai->static_size;
-	schunk->map_used = 1;
+	if (pcpu_reserved_offset) {
+		schunk->has_reserved = true;
+		schunk->map[0] = 1;
+		schunk->map[1] = pcpu_reserved_offset;
+		schunk->map_used = 1;
+	}
 	if (schunk->free_size)
-		schunk->map[++schunk->map_used] = ai->static_size + schunk->free_size;
+		schunk->map[++schunk->map_used] = map_size_bytes;
 	schunk->map[schunk->map_used] |= 1;
-	schunk->has_reserved = true;
 
 	/* init dynamic chunk if necessary */
 	if (dyn_size) {
 		dchunk = memblock_virt_alloc(pcpu_chunk_struct_size, 0);
 		INIT_LIST_HEAD(&dchunk->list);
 		INIT_LIST_HEAD(&dchunk->map_extend_list);
-		dchunk->base_addr = base_addr;
+		dchunk->base_addr = base_addr + ai->static_size +
+				    ai->reserved_size;
 		dchunk->map = dmap;
 		dchunk->map_alloc = ARRAY_SIZE(dmap);
 		dchunk->immutable = true;
@@ -1725,11 +1776,11 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
 		dchunk->nr_populated = pcpu_unit_pages;
 
 		dchunk->contig_hint = dchunk->free_size = dyn_size;
-		dchunk->map[0] = 1;
-		dchunk->map[1] = pcpu_reserved_chunk_limit;
-		dchunk->map[2] = (pcpu_reserved_chunk_limit + dchunk->free_size) | 1;
-		dchunk->map_used = 2;
-		dchunk->has_reserved = true;
+		dchunk->map[0] = 0;
+		dchunk->map[1] = dchunk->free_size | 1;
+		dchunk->map_used = 1;
+
+		dchunk->nr_pages = dyn_size >> PAGE_SHIFT;
 	}
 
 	/* link the first chunk in */
-- 
2.9.3

[toc] | [prev] | [next] | [standalone]

#1689349 — Re: [PATCH 06/10] percpu: modify base_addr to be region specific

Hello,

On Sat, Jul 15, 2017 at 10:23:11PM -0400, Dennis Zhou wrote:
> From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>
> 
> Originally, the first chunk is served by up to three chunks, each given
> a region they are responsible for. Despite this, the arithmetic was based
> off of the base_addr making it require offsets or be overly inclusive.
> This patch changes percpu checks for first chunk to consider the only
> the dynamic region and the reserved check to be only the reserved
> region. There is no impact here besides making these checks a little
> more accurate.
> 
> This patch also adds the ground work increasing the minimum allocation
> size to 4 bytes. The new field nr_pages in pcpu_chunk will be used to
> keep track of the number of pages the bitmap serves. The arithmetic for
> identifying first chunk and reserved chunk reflect this change.

However small the patch might end up being, I'd much prefer changing
the minimum alloc size to be a separate patch with rationale.

> diff --git a/include/linux/percpu.h b/include/linux/percpu.h
> index 98a371c..a5cedcd 100644
> --- a/include/linux/percpu.h
> +++ b/include/linux/percpu.h
> @@ -21,6 +21,10 @@
>  /* minimum unit size, also is the maximum supported allocation size */
>  #define PCPU_MIN_UNIT_SIZE		PFN_ALIGN(32 << 10)
>  
> +/* minimum allocation size and shift in bytes */
> +#define PCPU_MIN_ALLOC_SIZE		(1 << PCPU_MIN_ALLOC_SHIFT)
> +#define PCPU_MIN_ALLOC_SHIFT		2

nitpick: Put SHIFT def above SIZE def?

> +/*
> + * Static addresses should never be passed into the allocator.  They
> + * are accessed using the group_offsets and therefore do not rely on
> + * chunk->base_addr.
> + */
>  static bool pcpu_addr_in_first_chunk(void *addr)
>  {
>  	void *first_start = pcpu_first_chunk->base_addr;
>  
> -	return addr >= first_start && addr < first_start + pcpu_unit_size;
> +	return addr >= first_start &&
> +	       addr < first_start +
> +	       pcpu_first_chunk->nr_pages * PAGE_SIZE;

Does the above line need line break?  If so, it'd probably be easier
to read if the broken line is indented (preferably to align with the
start of the sub expression).  e.g.

	return addr < first_start +
		      pcpu_first_chunk->nr_pages * PAGE_SIZE;

>  static bool pcpu_addr_in_reserved_chunk(void *addr)
>  {
> -	void *first_start = pcpu_first_chunk->base_addr;
> +	void *first_start;
>  
> -	return addr >= first_start &&
> -		addr < first_start + pcpu_reserved_chunk_limit;
> +	if (!pcpu_reserved_chunk)
> +		return false;
> +
> +	first_start = pcpu_reserved_chunk->base_addr;
> +
> +	return addr >= first_start + pcpu_reserved_offset &&
> +	       addr < first_start +
> +	       pcpu_reserved_chunk->nr_pages * PAGE_SIZE;

Ditto on indentation.

> @@ -1366,10 +1388,17 @@ phys_addr_t per_cpu_ptr_to_phys(void *addr)
>  	 * The following test on unit_low/high isn't strictly
>  	 * necessary but will speed up lookups of addresses which
>  	 * aren't in the first chunk.
> +	 *
> +	 * The address check is of high granularity checking against full
> +	 * chunk sizes.  pcpu_base_addr points to the beginning of the first
> +	 * chunk including the static region.  This allows us to examine all
> +	 * regions of the first chunk. Assumes good intent as the first
> +	 * chunk may not be full (ie. < pcpu_unit_pages in size).
>  	 */
> -	first_low = pcpu_chunk_addr(pcpu_first_chunk, pcpu_low_unit_cpu, 0);
> -	first_high = pcpu_chunk_addr(pcpu_first_chunk, pcpu_high_unit_cpu,
> -				     pcpu_unit_pages);
> +	first_low = (unsigned long) pcpu_base_addr +
                                   ^
			 no space for type casts

> @@ -1575,6 +1604,8 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  	unsigned int cpu;
>  	int *unit_map;
>  	int group, unit, i;
> +	unsigned long tmp_addr, aligned_addr;
> +	unsigned long map_size_bytes;

How about just map_size or map_bytes?

> @@ -1678,46 +1709,66 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  		INIT_LIST_HEAD(&pcpu_slot[i]);
>  
>  	/*
> -	 * Initialize static chunk.  If reserved_size is zero, the
> -	 * static chunk covers static area + dynamic allocation area
> -	 * in the first chunk.  If reserved_size is not zero, it
> -	 * covers static area + reserved area (mostly used for module
> -	 * static percpu allocation).
> +	 * Initialize static chunk.
> +	 * The static region is dropped as those addresses are already
> +	 * allocated and do not rely on chunk->base_addr.
> +	 * reserved_size == 0:
> +	 *      the static chunk covers the dynamic area
> +	 * reserved_size > 0:
> +	 *      the static chunk covers the reserved area
> +	 *
> +	 * If the static area is not page aligned, the region adjacent
> +	 * to the static area must have its base_addr be offset into
> +	 * the static area to have it be page aligned.  The overlap is
> +	 * then allocated preserving the alignment in the metadata for
> +	 * the actual region.

We can address this later but static chunk not covering static area is
kinda confusing.  The original complication came from trying to make
the static chunk service either reserved or first dynamic chunk.  We
don't need that anymore and might as well use separate rchunk and
dchunk.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1690587 — Re: [PATCH 06/10] percpu: modify base_addr to be region specific

On Sat, Jul 15, 2017 at 10:23:11PM -0400, Dennis Zhou wrote:
> From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>
> 
> Originally, the first chunk is served by up to three chunks, each given
> a region they are responsible for. Despite this, the arithmetic was based
> off of the base_addr making it require offsets or be overly inclusive.
> This patch changes percpu checks for first chunk to consider the only
> the dynamic region and the reserved check to be only the reserved
> region. There is no impact here besides making these checks a little
> more accurate.
> 
> This patch also adds the ground work increasing the minimum allocation
> size to 4 bytes. The new field nr_pages in pcpu_chunk will be used to
> keep track of the number of pages the bitmap serves. The arithmetic for
> identifying first chunk and reserved chunk reflect this change.
> 
> Signed-off-by: Dennis Zhou <dennisszhou@gmail.com>
> ---
>  include/linux/percpu.h |   4 ++
>  mm/percpu-internal.h   |  12 +++--
>  mm/percpu.c            | 127 ++++++++++++++++++++++++++++++++++---------------
>  3 files changed, 100 insertions(+), 43 deletions(-)
> 
> diff --git a/include/linux/percpu.h b/include/linux/percpu.h
> index 98a371c..a5cedcd 100644
> --- a/include/linux/percpu.h
> +++ b/include/linux/percpu.h
> @@ -21,6 +21,10 @@
>  /* minimum unit size, also is the maximum supported allocation size */
>  #define PCPU_MIN_UNIT_SIZE		PFN_ALIGN(32 << 10)
>  
> +/* minimum allocation size and shift in bytes */
> +#define PCPU_MIN_ALLOC_SIZE		(1 << PCPU_MIN_ALLOC_SHIFT)
> +#define PCPU_MIN_ALLOC_SHIFT		2
> +
>  /*
>   * Percpu allocator can serve percpu allocations before slab is
>   * initialized which allows slab to depend on the percpu allocator.
> diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h
> index c9158a4..56e1aba 100644
> --- a/mm/percpu-internal.h
> +++ b/mm/percpu-internal.h
> @@ -23,11 +23,12 @@ struct pcpu_chunk {
>  	void			*data;		/* chunk data */
>  	int			first_free;	/* no free below this */
>  	bool			immutable;	/* no [de]population allowed */
> -	bool			has_reserved;	/* Indicates if chunk has reserved space
> -						   at the beginning. Reserved chunk will
> -						   contain reservation for static chunk.
> -						   Dynamic chunk will contain reservation
> -						   for static and reserved chunks. */
> +	bool			has_reserved;	/* indicates if the region this chunk
> +						   is responsible for overlaps with
> +						   the prior adjacent region */
> +
> +	int                     nr_pages;       /* # of PAGE_SIZE pages served
> +						   by this chunk */
>  	int			nr_populated;	/* # of populated pages */
>  	unsigned long		populated[];	/* populated bitmap */
>  };
> @@ -40,6 +41,7 @@ extern int pcpu_nr_empty_pop_pages;
>  
>  extern struct pcpu_chunk *pcpu_first_chunk;
>  extern struct pcpu_chunk *pcpu_reserved_chunk;
> +extern unsigned long pcpu_reserved_offset;
>  
>  #ifdef CONFIG_PERCPU_STATS
>  
> diff --git a/mm/percpu.c b/mm/percpu.c
> index 7704db9..c74ad68 100644
> --- a/mm/percpu.c
> +++ b/mm/percpu.c
> @@ -144,14 +144,14 @@ static const size_t *pcpu_group_sizes __ro_after_init;
>  struct pcpu_chunk *pcpu_first_chunk __ro_after_init;
>  
>  /*
> - * Optional reserved chunk.  This chunk reserves part of the first
> - * chunk and serves it for reserved allocations.  The amount of
> - * reserved offset is in pcpu_reserved_chunk_limit.  When reserved
> - * area doesn't exist, the following variables contain NULL and 0
> - * respectively.
> + * Optional reserved chunk.  This is the part of the first chunk that
> + * serves reserved allocations.  The pcpu_reserved_offset is the amount
> + * the pcpu_reserved_chunk->base_addr is push back into the static
> + * region for the base_addr to be page aligned.  When the reserved area
> + * doesn't exist, the following variables contain NULL and 0 respectively.
>   */
>  struct pcpu_chunk *pcpu_reserved_chunk __ro_after_init;
> -static int pcpu_reserved_chunk_limit __ro_after_init;
> +unsigned long pcpu_reserved_offset __ro_after_init;
>  
>  DEFINE_SPINLOCK(pcpu_lock);	/* all internal data structures */
>  static DEFINE_MUTEX(pcpu_alloc_mutex);	/* chunk create/destroy, [de]pop, map ext */
> @@ -184,19 +184,32 @@ static void pcpu_schedule_balance_work(void)
>  		schedule_work(&pcpu_balance_work);
>  }
>  
> +/*
> + * Static addresses should never be passed into the allocator.  They
> + * are accessed using the group_offsets and therefore do not rely on
> + * chunk->base_addr.
> + */
>  static bool pcpu_addr_in_first_chunk(void *addr)
>  {
>  	void *first_start = pcpu_first_chunk->base_addr;
>  
> -	return addr >= first_start && addr < first_start + pcpu_unit_size;
> +	return addr >= first_start &&
> +	       addr < first_start +
> +	       pcpu_first_chunk->nr_pages * PAGE_SIZE;
>  }
>  
>  static bool pcpu_addr_in_reserved_chunk(void *addr)
>  {
> -	void *first_start = pcpu_first_chunk->base_addr;
> +	void *first_start;
>  
> -	return addr >= first_start &&
> -		addr < first_start + pcpu_reserved_chunk_limit;
> +	if (!pcpu_reserved_chunk)
> +		return false;
> +
> +	first_start = pcpu_reserved_chunk->base_addr;
> +
> +	return addr >= first_start + pcpu_reserved_offset &&
> +	       addr < first_start +
> +	       pcpu_reserved_chunk->nr_pages * PAGE_SIZE;
>  }
>  
>  static int __pcpu_size_to_slot(int size)
> @@ -237,11 +250,16 @@ static int __maybe_unused pcpu_page_idx(unsigned int cpu, int page_idx)
>  	return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx;
>  }
>  
> +static unsigned long pcpu_unit_page_offset(unsigned int cpu, int page_idx)
> +{
> +	return pcpu_unit_offsets[cpu] + (page_idx << PAGE_SHIFT);
> +}
> +
>  static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
>  				     unsigned int cpu, int page_idx)
>  {
> -	return (unsigned long)chunk->base_addr + pcpu_unit_offsets[cpu] +
> -		(page_idx << PAGE_SHIFT);
> +	return (unsigned long)chunk->base_addr +
> +		pcpu_unit_page_offset(cpu, page_idx);
>  }
>  
>  static void __maybe_unused pcpu_next_unpop(struct pcpu_chunk *chunk,
> @@ -737,6 +755,8 @@ static struct pcpu_chunk *pcpu_alloc_chunk(void)
>  	chunk->free_size = pcpu_unit_size;
>  	chunk->contig_hint = pcpu_unit_size;
>  
> +	chunk->nr_pages = pcpu_unit_pages;
> +
>  	return chunk;
>  }
>  
> @@ -824,18 +844,20 @@ static int __init pcpu_verify_alloc_info(const struct pcpu_alloc_info *ai);
>   * pcpu_chunk_addr_search - determine chunk containing specified address
>   * @addr: address for which the chunk needs to be determined.
>   *
> + * This is an internal function that handles all but static allocations.
> + * Static percpu address values should never be passed into the allocator.
> + *
>   * RETURNS:
>   * The address of the found chunk.
>   */
>  static struct pcpu_chunk *pcpu_chunk_addr_search(void *addr)
>  {
>  	/* is it in the first chunk? */
> -	if (pcpu_addr_in_first_chunk(addr)) {
> -		/* is it in the reserved area? */
> -		if (pcpu_addr_in_reserved_chunk(addr))
> -			return pcpu_reserved_chunk;
> +	if (pcpu_addr_in_first_chunk(addr))
>  		return pcpu_first_chunk;
> -	}
> +	/* is it in the reserved chunk? */
> +	if (pcpu_addr_in_reserved_chunk(addr))
> +		return pcpu_reserved_chunk;
>  
>  	/*
>  	 * The address is relative to unit0 which might be unused and
> @@ -1366,10 +1388,17 @@ phys_addr_t per_cpu_ptr_to_phys(void *addr)
>  	 * The following test on unit_low/high isn't strictly
>  	 * necessary but will speed up lookups of addresses which
>  	 * aren't in the first chunk.
> +	 *
> +	 * The address check is of high granularity checking against full
> +	 * chunk sizes.  pcpu_base_addr points to the beginning of the first
> +	 * chunk including the static region.  This allows us to examine all
> +	 * regions of the first chunk. Assumes good intent as the first
> +	 * chunk may not be full (ie. < pcpu_unit_pages in size).
>  	 */
> -	first_low = pcpu_chunk_addr(pcpu_first_chunk, pcpu_low_unit_cpu, 0);
> -	first_high = pcpu_chunk_addr(pcpu_first_chunk, pcpu_high_unit_cpu,
> -				     pcpu_unit_pages);
> +	first_low = (unsigned long) pcpu_base_addr +
> +		    pcpu_unit_page_offset(pcpu_low_unit_cpu, 0);
> +	first_high = (unsigned long) pcpu_base_addr +
> +		     pcpu_unit_page_offset(pcpu_high_unit_cpu, pcpu_unit_pages);
>  	if ((unsigned long)addr >= first_low &&
>  	    (unsigned long)addr < first_high) {
>  		for_each_possible_cpu(cpu) {
> @@ -1575,6 +1604,8 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  	unsigned int cpu;
>  	int *unit_map;
>  	int group, unit, i;
> +	unsigned long tmp_addr, aligned_addr;
> +	unsigned long map_size_bytes;
>  
>  #define PCPU_SETUP_BUG_ON(cond)	do {					\
>  	if (unlikely(cond)) {						\
> @@ -1678,46 +1709,66 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  		INIT_LIST_HEAD(&pcpu_slot[i]);
>  
>  	/*
> -	 * Initialize static chunk.  If reserved_size is zero, the
> -	 * static chunk covers static area + dynamic allocation area
> -	 * in the first chunk.  If reserved_size is not zero, it
> -	 * covers static area + reserved area (mostly used for module
> -	 * static percpu allocation).
> +	 * Initialize static chunk.
> +	 * The static region is dropped as those addresses are already
> +	 * allocated and do not rely on chunk->base_addr.
> +	 * reserved_size == 0:
> +	 *      the static chunk covers the dynamic area
> +	 * reserved_size > 0:
> +	 *      the static chunk covers the reserved area
> +	 *
> +	 * If the static area is not page aligned, the region adjacent
> +	 * to the static area must have its base_addr be offset into
> +	 * the static area to have it be page aligned.  The overlap is
> +	 * then allocated preserving the alignment in the metadata for
> +	 * the actual region.
>  	 */
> +	tmp_addr = (unsigned long)base_addr + ai->static_size;
> +	aligned_addr = tmp_addr & PAGE_MASK;
> +	pcpu_reserved_offset = tmp_addr - aligned_addr;
> +
> +	map_size_bytes = (ai->reserved_size ?: ai->dyn_size) +
> +			 pcpu_reserved_offset;

This confused me for a second, better to be explicit with

(ai->reserved_size ? 0 : ai->dyn_size) + pcpu_reserved_offset;

Thanks,

Josef

[toc] | [prev] | [next] | [standalone]

#1690593 — Re: [PATCH 06/10] percpu: modify base_addr to be region specific

On Tue, Jul 18, 2017 at 03:26:02PM -0400, Josef Bacik wrote:
> On Sat, Jul 15, 2017 at 10:23:11PM -0400, Dennis Zhou wrote:
> > +	map_size_bytes = (ai->reserved_size ?: ai->dyn_size) +
> > +			 pcpu_reserved_offset;
> 
> This confused me for a second, better to be explicit with
> 
> (ai->reserved_size ? 0 : ai->dyn_size) + pcpu_reserved_offset;

You're still confused ;-)  What Dennis wrote is equivalent to:

(ai->reserved_size ? ai->reserved_size : ai->dyn_size) + pcpu_reserved_offset;

[toc] | [prev] | [next] | [standalone]

#1691717 — Re: [PATCH 06/10] percpu: modify base_addr to be region specific

On Tue, Jul 18, 2017 at 12:36:27PM -0700, Matthew Wilcox wrote:
> On Tue, Jul 18, 2017 at 03:26:02PM -0400, Josef Bacik wrote:
> > On Sat, Jul 15, 2017 at 10:23:11PM -0400, Dennis Zhou wrote:
> > > +	map_size_bytes = (ai->reserved_size ?: ai->dyn_size) +
> > > +			 pcpu_reserved_offset;
> > 
> > This confused me for a second, better to be explicit with
> > 
> > (ai->reserved_size ? 0 : ai->dyn_size) + pcpu_reserved_offset;
> 
> You're still confused ;-)  What Dennis wrote is equivalent to:
> 
> (ai->reserved_size ? ai->reserved_size : ai->dyn_size) + pcpu_reserved_offset;

Lol jesus, made my point even harder with me being an idiot.  Thanks,

Josef

[toc] | [prev] | [next] | [standalone]

#1689563 — Re: [PATCH 09/10] percpu: replace area map allocator with bitmap allocator

On Sat, Jul 15, 2017 at 10:23:14PM -0400, Dennis Zhou wrote:
...
> While it does add to the allocation latency, the allocation scenario
> here is optimal for the area map allocator. The second problem of
> additional scanning can result in the area map allocator completing in
> 52 minutes. The same workload takes only 14 seconds to complete for the
> bitmap allocator. This was produced under a more contrived scenario of
> allocating 1 milion 4-byte objects with 8-byte alignment.

I think it'd be nice to have a similar table for allocation patterns
which aren't ideal for the original allocator.  The biggest goal is
avoiding cases where the allocator collapses and just glancing at the
table doesn't seem very compelling.

>  /*
> + * This determines the size of each metadata block.  There are several subtle
> + * constraints around this variable.  The reserved_region and dynamic_region
                              ^
			      constant
			      
> + * of the first chunk must be multiples of PCPU_BITMAP_BLOCK_SIZE.  This is
> + * not a problem if the BLOCK_SIZE encompasses a page, but if exploring blocks
> + * that are backing multiple pages, this needs to be accounted for.
> + */
> +#define PCPU_BITMAP_BLOCK_SIZE		(PAGE_SIZE >> PCPU_MIN_ALLOC_SHIFT)

Given that percpu allocator can align only upto a page, the
restriction makes sense to me.  I'm kinda curious whether PAGE_SIZE
blocks is optimal tho.  Why did you pick PAGE_SIZE?

> @@ -44,6 +62,44 @@ extern struct pcpu_chunk *pcpu_first_chunk;
>  extern struct pcpu_chunk *pcpu_reserved_chunk;
>  extern unsigned long pcpu_reserved_offset;
>  
> +/*
   ^^
   /**

Ditto for other comments.

> + * pcpu_nr_pages_to_blocks - converts nr_pages to # of md_blocks
> + * @chunk: chunk of interest
> + *
> + * This conversion is from the number of physical pages that the chunk
> + * serves to the number of bitmap blocks required.  It converts to bytes
> + * served to bits required and then blocks used.
> + */
> +static inline int pcpu_nr_pages_to_blocks(struct pcpu_chunk *chunk)

Maybe just pcpu_chunk_nr_blocks()?

> +{
> +	return chunk->nr_pages * PAGE_SIZE / PCPU_MIN_ALLOC_SIZE /
> +	       PCPU_BITMAP_BLOCK_SIZE;
> +}
> +
> +/*
> + * pcpu_pages_to_bits - converts the pages to size of bitmap
> + * @pages: number of physical pages
> + *
> + * This conversion is from physical pages to the number of bits
> + * required in the bitmap.
> + */
> +static inline int pcpu_pages_to_bits(int pages)

pcpu_nr_pages_to_map_bits()?

> +{
> +	return pages * PAGE_SIZE / PCPU_MIN_ALLOC_SIZE;
> +}
> +
> +/*
> + * pcpu_nr_pages_to_bits - helper to convert nr_pages to size of bitmap
> + * @chunk: chunk of interest
> + *
> + * This conversion is from the number of physical pages that the chunk
> + * serves to the number of bits in the bitmap.
> + */
> +static inline int pcpu_nr_pages_to_bits(struct pcpu_chunk *chunk)

pcpu_chunk_map_bits()?

> @@ -86,10 +90,13 @@
>  
>  #include "percpu-internal.h"
>  
> -#define PCPU_SLOT_BASE_SHIFT		5	/* 1-31 shares the same slot */
> -#define PCPU_DFL_MAP_ALLOC		16	/* start a map with 16 ents */
> -#define PCPU_ATOMIC_MAP_MARGIN_LOW	32
> -#define PCPU_ATOMIC_MAP_MARGIN_HIGH	64
> +/*
> + * The metadata is managed in terms of bits with each bit mapping to
> + * a fragment of size PCPU_MIN_ALLOC_SIZE.  Thus, the slots are calculated
> + * with respect to the number of bits available.
> + */
> +#define PCPU_SLOT_BASE_SHIFT		3

Ah, so this is actually the same as before 3 + 2, order 5.  Can you
please note the explicit number in the comment?

>  #define PCPU_EMPTY_POP_PAGES_LOW	2
>  #define PCPU_EMPTY_POP_PAGES_HIGH	4

and these numbers too.  I can't tell how these numbers would map.
Also, any chance we can have these numbers in a more intuitive unit?

> @@ -212,25 +220,25 @@ static bool pcpu_addr_in_reserved_chunk(void *addr)
>  	       pcpu_reserved_chunk->nr_pages * PAGE_SIZE;
>  }
>  
> -static int __pcpu_size_to_slot(int size)
> +static int __pcpu_size_to_slot(int bit_size)

Wouldn't sth like @map_bits more intuitive than @bit_size?  We can
just use @bits too.

>  {
> -	int highbit = fls(size);	/* size is in bytes */
> +	int highbit = fls(bit_size);	/* size is in bits */
>  	return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);
>  }
>  
> -static int pcpu_size_to_slot(int size)
> +static int pcpu_size_to_slot(int bit_size)

Ditto.

> +static void pcpu_chunk_update_hint(struct pcpu_chunk *chunk)
> +{
> +	bool is_page_empty = true;
> +	int i, off, cur_contig, nr_empty_pop_pages, l_pop_off;
> +	struct pcpu_bitmap_md *block;
> +
> +	chunk->contig_hint = cur_contig = 0;
> +	off = nr_empty_pop_pages = 0;
> +	l_pop_off = pcpu_block_get_first_page(chunk->first_free_block);
> +
> +	for (i = chunk->first_free_block, block = chunk->md_blocks + i;
> +	     i < pcpu_nr_pages_to_blocks(chunk); i++, block++) {
> +		/* Manage nr_empty_pop_pages.

		The first line of a winged comment should be blank, so...

		/*
		 * Manage nr_empty_pop_pages.

> +		 *
> +		 * This is tricky.  So the the background work function is
                                       ^^^^^^^

> +		 * triggered when there are not enough free populated pages.
> +		 * This is necessary to make sure atomic allocations can
> +		 * succeed.
> +		 *
> +		 * The first page of each block is kept track of here allowing
> +		 * this to scale in both situations where there are > 1 page
> +		 * per block and where a block may be a portion of a page.
> +		 */
> +		int pop_off = pcpu_block_get_first_page(i);
> +
> +		if (pop_off > l_pop_off) {
> +			if (is_page_empty)
> +				nr_empty_pop_pages +=
> +					pcpu_cnt_pop_pages(chunk, l_pop_off,
> +							   pop_off);

IIUC, this is trying to handle multi-page block size, right?

> +			l_pop_off = pop_off;
> +			is_page_empty = true;
> +		}
> +		if (block->contig_hint != PCPU_BITMAP_BLOCK_SIZE)

But isn't this assuming that each block is page sized?

> +			is_page_empty = false;
>  
> +		/* continue from prev block adding to the cur_contig hint */
> +		if (cur_contig) {
> +			cur_contig += block->left_free;
> +			if (block->left_free == PCPU_BITMAP_BLOCK_SIZE) {
> +				continue;
> +			} else if (cur_contig > chunk->contig_hint) {

The "else" here is superflous, right?  The if block always continues.

> +				chunk->contig_hint = cur_contig;
> +				chunk->contig_hint_start = off;
>  			}
> +			cur_contig = 0;
>  		}
> +		/* check if the block->contig_hint is larger */
> +		if (block->contig_hint > chunk->contig_hint) {
> +			chunk->contig_hint = block->contig_hint;
> +			chunk->contig_hint_start =
> +				pcpu_block_off_to_off(i,
> +						      block->contig_hint_start);
> +		}
> +		/* let the next iteration catch the right_free */
> +		cur_contig = block->right_free;
> +		off = (i + 1) * PCPU_BITMAP_BLOCK_SIZE - block->right_free;
>  	}
>  
> +	/* catch last iteration if the last block ends with free space */
> +	if (cur_contig > chunk->contig_hint) {
> +		chunk->contig_hint = cur_contig;
> +		chunk->contig_hint_start = off;
> +	}
>  
> +	/*
> +	 * Keep track of nr_empty_pop_pages.
> +	 *
> +	 * The chunk is maintains the previous number of free pages it held,
> +	 * so the delta is used to update the global counter.  The reserved
> +	 * chunk is not part of the free page count as they are populated
> +	 * at init and are special to serving reserved allocations.
> +	 */
> +	if (is_page_empty) {
> +		nr_empty_pop_pages += pcpu_cnt_pop_pages(chunk, l_pop_off,
> +							 chunk->nr_pages);
> +	}

Unnecessary {}.

> +	if (chunk != pcpu_reserved_chunk)
> +		pcpu_nr_empty_pop_pages +=
> +			(nr_empty_pop_pages - chunk->nr_empty_pop_pages);
> +	chunk->nr_empty_pop_pages = nr_empty_pop_pages;
>  }

I am really not a big fan of the above implementation.  All it wants
to do is calculating the biggest free span and count unpopulated pages
in the chunk.  There gotta be a more readable way to implement this.
For example, would it be possible to implement span iterator over a
chunk which walks free spans of the chunk so that the above function
can do something similar to the following?

	for_each_free_span(blah blah) {
		nr_pop_free += count populated whole pages in the span;
		update contig hint;
	}

It's a span iteration problem.  When abstracted properly, it shouldn't
be too difficult to follow.

>  /**
> + * pcpu_block_update_hint
>   * @chunk: chunk of interest
> + * @index: block index of the metadata block
>   *
> + * Full scan over the entire block to recalculate block-level metadata.
> + */
> +static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index)
> +{
> +	unsigned long *alloc_map = pcpu_index_alloc_map(chunk, index);
> +	struct pcpu_bitmap_md *block = chunk->md_blocks + index;
> +	bool is_left_free = false, is_right_free = false;
> +	int contig;
> +	unsigned long start, end;
> +
> +	block->contig_hint = 0;
> +	start = end = block->first_free;
> +	while (start < PCPU_BITMAP_BLOCK_SIZE) {
> +		/*
> +		 * Scans the allocation map corresponding to this block
> +		 * to find free fragments and update metadata accordingly.
> +		 */
> +		start = find_next_zero_bit(alloc_map, PCPU_BITMAP_BLOCK_SIZE,
> +					   start);
> +		if (start >= PCPU_BITMAP_BLOCK_SIZE)
> +			break;

It's a lot simpler here but this too might look simpler with an
appropriate interation abstraction.

> +		/* returns PCPU_BITMAP_BLOCK_SIZE if no next bit is found */
> +		end = find_next_bit(alloc_map, PCPU_BITMAP_BLOCK_SIZE, start);

This isn't by no means a hard rule but it's often easier on the eyes
to have a blank line when code and comment are packed like this.

> +		/* update left_free */
> +		contig = end - start;
> +		if (start == 0) {
> +			block->left_free = contig;
> +			is_left_free = true;
> +		}
> +		/* update right_free */
> +		if (end == PCPU_BITMAP_BLOCK_SIZE) {
> +			block->right_free = contig;
> +			is_right_free = true;
> +		}
> +		/* update block contig_hints */
> +		if (block->contig_hint < contig) {
> +			block->contig_hint = contig;
> +			block->contig_hint_start = start;
> +		}
> +		start = end;
> +	}
> +
> +	/* clear left/right free hints */
> +	if (!is_left_free)
> +		block->left_free = 0;
> +	if (!is_right_free)
> +		block->right_free = 0;

Hmm... why do we need is_left/right_free?  Can't we reset them to zero
at the top and update directly during the loop?

> +static bool pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
> +					 int bit_size)
>  {
> +	bool update_chunk = false;
> +	int i;
> +	int s_index, e_index, s_off, e_off;
> +	struct pcpu_bitmap_md *s_block, *e_block, *block;
>  
> +	/* calculate per block offsets */
> +	s_index = pcpu_off_to_block_index(bit_off);
> +	e_index = pcpu_off_to_block_index(bit_off + bit_size);
> +	s_off = pcpu_off_to_block_off(bit_off);
> +	e_off = pcpu_off_to_block_off(bit_off + bit_size);
>  
> +	/*
> +	 * If the offset is the beginning of the next block, set it to the
> +	 * end of the previous block as the last bit is the exclusive.
> +	 */
> +	if (e_off == 0) {
> +		e_off = PCPU_BITMAP_BLOCK_SIZE;
> +		e_index--;
> +	}
>  
> +	s_block = chunk->md_blocks + s_index;
> +	e_block = chunk->md_blocks + e_index;
>  
> +	/*
> +	 * Update s_block.
> +	 *
> +	 * block->first_free must be updated if the allocation takes its place.
> +	 * If the allocation breaks the contig_hint, a scan is required to
> +	 * restore this hint.
> +	 */
> +	if (s_off == s_block->first_free)
> +		s_block->first_free = find_next_zero_bit(
> +					pcpu_index_alloc_map(chunk, s_index),
> +					PCPU_BITMAP_BLOCK_SIZE,
> +					s_off + bit_size);
> +
> +	if (s_off >= s_block->contig_hint_start &&
> +	    s_off < s_block->contig_hint_start + s_block->contig_hint) {
> +		pcpu_block_refresh_hint(chunk, s_index);
> +	} else {
> +		/* update left and right contig manually */
> +		s_block->left_free = min(s_block->left_free, s_off);
> +		if (s_index == e_index)
> +			s_block->right_free = min_t(int, s_block->right_free,
> +					PCPU_BITMAP_BLOCK_SIZE - e_off);
> +		else
> +			s_block->right_free = 0;
> +	}
>  
> +	/*
> +	 * Update e_block.
> +	 * If they are different, then e_block's first_free is guaranteed to
> +	 * be the extend of e_off.  first_free must be updated and a scan
> +	 * over e_block is issued.
> +	 */
> +	if (s_index != e_index) {
> +		e_block->first_free = find_next_zero_bit(
> +				pcpu_index_alloc_map(chunk, e_index),
> +				PCPU_BITMAP_BLOCK_SIZE, e_off);
>  
> +		pcpu_block_refresh_hint(chunk, e_index);
> +	}
>  
> +	/* update in-between md_blocks */
> +	for (i = s_index + 1, block = chunk->md_blocks + i; i < e_index;
> +	     i++, block++) {
> +		block->contig_hint = 0;
> +		block->left_free = 0;
> +		block->right_free = 0;
> +	}
>  
>  	/*
> +	 * The only time a full chunk scan is required is if the global
> +	 * contig_hint is broken.  Otherwise, it means a smaller space
> +	 * was used and therefore the global contig_hint is still correct.
>  	 */
> +	if (bit_off >= chunk->contig_hint_start &&
> +	    bit_off < chunk->contig_hint_start + chunk->contig_hint)
> +		update_chunk = true;
>  
> +	return update_chunk;

@update_chunk seems unnecessary.

> +static bool pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off,
> +					int bit_size)
>  {
> +	bool update_chunk = false;
> +	int i;
> +	int s_index, e_index, s_off, e_off;
> +	int start, end, contig;
> +	struct pcpu_bitmap_md *s_block, *e_block, *block;
>  
> +	/* calculate per block offsets */
> +	s_index = pcpu_off_to_block_index(bit_off);
> +	e_index = pcpu_off_to_block_index(bit_off + bit_size);
> +	s_off = pcpu_off_to_block_off(bit_off);
> +	e_off = pcpu_off_to_block_off(bit_off + bit_size);
> +
> +	/*
> +	 * If the offset is the beginning of the next block, set it to the
> +	 * end of the previous block as the last bit is the exclusive.
> +	 */
> +	if (e_off == 0) {
> +		e_off = PCPU_BITMAP_BLOCK_SIZE;
> +		e_index--;
> +	}

So, if you do the above with inclusive range, it becomes

	s_index = pcpu_off_to_block_index(start_bit);
	e_index = pcpu_off_to_block_index(end_bit - 1);
	s_off = pcpu_off_to_block_off(start_bit);
	e_off = pcpu_off_to_block_off(end_bit - 1) + 1;

and you can just comment that you're using inclusive range so that the
e_index always points to the last block in the range.  Wouldn't that
be easier?  People do use inclusive ranges for these sorts of
calculations.

> +	s_block = chunk->md_blocks + s_index;
> +	e_block = chunk->md_blocks + e_index;
> +
> +	/*
> +	 * Check if the freed area aligns with the block->contig_hint.
> +	 * If it does, then the scan to find the beginning/end of the
> +	 * larger free area can be avoided.
> +	 *
> +	 * start and end refer to beginning and end of the free region
> +	 * within each their respective blocks.  This is not necessarily
> +	 * the entire free region as it may span blocks past the beginning
> +	 * or end of the block.
> +	 */
> +	start = s_off;
> +	if (s_off == s_block->contig_hint + s_block->contig_hint_start) {
> +		start = s_block->contig_hint_start;
> +	} else {
> +		int l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index),
> +					  start);
> +		start = (start == l_bit) ? 0 : l_bit + 1;
> +	}
> +
> +	end = e_off;
> +	if (e_off == e_block->contig_hint_start)
> +		end = e_block->contig_hint_start + e_block->contig_hint;
> +	else
> +		end = find_next_bit(pcpu_index_alloc_map(chunk, e_index),
> +				    PCPU_BITMAP_BLOCK_SIZE, end);
>  
> +	/* freeing in the same block */
> +	if (s_index == e_index) {
> +		contig = end - start;
>  
> +		if (start == 0)
> +			s_block->left_free = contig;
>  
> +		if (end == PCPU_BITMAP_BLOCK_SIZE)
> +			s_block->right_free = contig;
> +
> +		s_block->first_free = min(s_block->first_free, start);
> +		if (contig > s_block->contig_hint) {
> +			s_block->contig_hint = contig;
> +			s_block->contig_hint_start = start;
> +		}
> +
> +	} else {
>  		/*
> +		 * Freeing across md_blocks.
> +		 *
> +		 * If the start is at the beginning of the block, just
> +		 * reset the block instead.
>  		 */
> +		if (start == 0) {

The above comment can be moved here and lose the if in the sentence.
ie. "As the start is ..., just .."

> +			s_index--;
> +		} else {
> +			/*
> +			 * Knowing that the free is across blocks, this means
> +			 * the hint can be updated on the right side and the
> +			 * left side does not need to be touched.
> +			 */
> +			s_block->first_free = min(s_block->first_free, start);
> +			contig = PCPU_BITMAP_BLOCK_SIZE - start;
> +			s_block->right_free = contig;
> +			if (contig > s_block->contig_hint) {
> +				s_block->contig_hint = contig;
> +				s_block->contig_hint_start = start;
> +			}
> +		}

Blank line, please.

> +		/*
> +		 * If end is the entire e_block, just reset the block
> +		 * as well.
> +		 */
> +		if (end == PCPU_BITMAP_BLOCK_SIZE) {

ditto

> +			e_index++;
> +		} else {
> +			/*
> +			 * The hint must only be on the left side, so
> +			 * update accordingly.
> +			 */
> +			e_block->first_free = 0;
> +			e_block->left_free = end;
> +			if (end > e_block->contig_hint) {
> +				e_block->contig_hint = end;
> +				e_block->contig_hint_start = 0;
> +			}
> +		}
> +
> +		/* reset md_blocks in the middle */
> +		for (i = s_index + 1, block = chunk->md_blocks + i;
> +		     i < e_index; i++, block++) {

How about something like the following?  It's kinda weird to have an
extra loop var which isn't really used for anything.  The same goes
for other places too.

		for (block = chunk->md_blocks + s_index + 1;
		     block < chunk->md_blocks + e_index; block++)

> +			block->first_free = 0;
> +			block->contig_hint_start = 0;
> +			block->contig_hint = PCPU_BITMAP_BLOCK_SIZE;
> +			block->left_free = PCPU_BITMAP_BLOCK_SIZE;
> +			block->right_free = PCPU_BITMAP_BLOCK_SIZE;
> +		}
>  	}
> +
> +	/*
> +	 * The hint is only checked in the s_block and e_block when
> +	 * freeing and particularly only when it is self contained within
> +	 * its own block.  A scan is required if the free space spans
> +	 * blocks or makes a block whole as the scan will take into
> +	 * account free space across blocks.
> +	 */
> +	if ((start == 0 && end == PCPU_BITMAP_BLOCK_SIZE) ||
> +	    s_index != e_index) {
> +		update_chunk = true;
> +	} else if (s_block->contig_hint > chunk->contig_hint) {
> +		/* check if block contig_hint is bigger */
> +		chunk->contig_hint = s_block->contig_hint;
> +		chunk->contig_hint_start =
> +			pcpu_block_off_to_off(s_index,
> +					      s_block->contig_hint_start);
> +	}
> +
> +	return update_chunk;

Ditto with @update_chunk.

> +static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int bit_size,
> +			       size_t align, bool pop_only)
>  {
> +	int i, cur_free;
> +	int s_index, block_off, next_index, end_off; /* interior alloc index */
> +	struct pcpu_bitmap_md *block;
> +	unsigned long *alloc_map;
>  
> +	lockdep_assert_held(&pcpu_lock);
>  
> +	cur_free = block_off = 0;
> +	s_index = chunk->first_free_block;
> +	for (i = chunk->first_free_block; i < pcpu_nr_pages_to_blocks(chunk);
> +	     i++) {
> +		alloc_map = pcpu_index_alloc_map(chunk, i);
> +		block = chunk->md_blocks + i;
> +
> +		/* continue from prev block */
> +		cur_free += block->left_free;
> +		if (cur_free >= bit_size) {
> +			end_off = bit_size;
> +			goto check_populated;
> +		} else if (block->left_free == PCPU_BITMAP_BLOCK_SIZE) {
>  			continue;
>  		}
>  
>  		/*
> +		 * Can this block hold this alloc?
> +		 *
> +		 * Here the block->contig_hint is used to guarantee a fit,
> +		 * but the block->first_free is returned as we may be able
> +		 * to serve the allocation earlier.  The population check
> +		 * must take into account the area beginning at first_free
> +		 * through the end of the contig_hint.
>  		 */
> +		cur_free = 0;
> +		s_index = i;
> +		block_off = ALIGN(block->contig_hint_start, align);
> +		block_off -= block->contig_hint_start;
> +		if (block->contig_hint >= block_off + bit_size) {
> +			block_off = block->first_free;
> +			end_off = block->contig_hint_start - block_off +
> +				  bit_size;
> +			goto check_populated;
>  		}
>  
> +		/* check right */
> +		block_off = ALIGN(PCPU_BITMAP_BLOCK_SIZE - block->right_free,
> +				  align);
> +		/* reset to start looking in the next block */
> +		if (block_off >= PCPU_BITMAP_BLOCK_SIZE) {
> +			s_index++;
> +			cur_free = block_off = 0;
> +			continue;
>  		}
> +		cur_free = PCPU_BITMAP_BLOCK_SIZE - block_off;
> +		if (cur_free >= bit_size) {
> +			end_off = bit_size;
> +check_populated:
> +			if (!pop_only ||
> +			    pcpu_is_populated(chunk, s_index, block_off,
> +					      end_off, &next_index))
> +				break;
>  
> +			i = next_index - 1;
> +			s_index = next_index;
> +			cur_free = block_off = 0;
>  		}
> +	}
>  
> +	/* nothing found */
> +	if (i == pcpu_nr_pages_to_blocks(chunk))
> +		return -1;
>  
> +	return s_index * PCPU_BITMAP_BLOCK_SIZE + block_off;
> +}

Wouldn't this function be a lot simpler too if there were free span
iterator?

> +static int pcpu_alloc_area(struct pcpu_chunk *chunk, int bit_size,
> +			   size_t align, int start)
> +{
> +	size_t align_mask = (align) ? (align - 1) : 0;
> +	int i, bit_off, oslot;
> +	struct pcpu_bitmap_md *block;
> +
> +	lockdep_assert_held(&pcpu_lock);
> +
> +	oslot = pcpu_chunk_slot(chunk);
> +
> +	/* search to find fit */
> +	bit_off = bitmap_find_next_zero_area(chunk->alloc_map,
> +					     pcpu_nr_pages_to_bits(chunk),
> +					     start, bit_size, align_mask);
> +
> +	if (bit_off >= pcpu_nr_pages_to_bits(chunk))
> +		return -1;
> +
> +	/* update alloc map */
> +	bitmap_set(chunk->alloc_map, bit_off, bit_size);

blank line

> +	/* update boundary map */
> +	set_bit(bit_off, chunk->bound_map);
> +	bitmap_clear(chunk->bound_map, bit_off + 1, bit_size - 1);
> +	set_bit(bit_off + bit_size, chunk->bound_map);
> +
> +	chunk->free_bits -= bit_size;
> +
> +	if (pcpu_block_update_hint_alloc(chunk, bit_off, bit_size))
> +		pcpu_chunk_update_hint(chunk);
> +
> +	/* update chunk first_free */
> +	for (i = chunk->first_free_block, block = chunk->md_blocks + i;
> +	     i < pcpu_nr_pages_to_blocks(chunk); i++, block++)
> +		if (block->contig_hint != 0)
> +			break;
> +
> +	chunk->first_free_block = i;
>  
>  	pcpu_chunk_relocate(chunk, oslot);
>  
> +	return bit_off * PCPU_MIN_ALLOC_SIZE;
>  }
>  
>  /**
> + * pcpu_free_area - frees the corresponding offset
>   * @chunk: chunk of interest
> + * @off: addr offset into chunk
>   *
> + * This function determines the size of an allocation to free using
> + * the boundary bitmap and clears the allocation map.  A block metadata
> + * update is triggered and potentially a chunk update occurs.
>   */
> +static void pcpu_free_area(struct pcpu_chunk *chunk, int off)
>  {
> +	int bit_off, bit_size, index, end, oslot;
> +	struct pcpu_bitmap_md *block;
>  
>  	lockdep_assert_held(&pcpu_lock);
>  	pcpu_stats_area_dealloc(chunk);
>  
> +	oslot = pcpu_chunk_slot(chunk);
>  
> +	bit_off = off / PCPU_MIN_ALLOC_SIZE;
>  
> +	/* find end index */
> +	end = find_next_bit(chunk->bound_map, pcpu_nr_pages_to_bits(chunk),
> +			    bit_off + 1);
> +	bit_size = end - bit_off;
>  
> +	bitmap_clear(chunk->alloc_map, bit_off, bit_size);
>  
> +	chunk->free_bits += bit_size;
> +
> +	/* update first_free */
> +	index = pcpu_off_to_block_index(bit_off);
> +	block = chunk->md_blocks + index;
> +	block->first_free = min_t(int, block->first_free,
> +				  bit_off % PCPU_BITMAP_BLOCK_SIZE);
> +
> +	chunk->first_free_block = min(chunk->first_free_block, index);
> +
> +	if (pcpu_block_update_hint_free(chunk, bit_off, bit_size))
> +		pcpu_chunk_update_hint(chunk);

Do we ever not update chunk hint when block hint indicates that it's
necessary?  If not, maybe just call it from the previous function?

>  static void pcpu_free_chunk(struct pcpu_chunk *chunk)
>  {
>  	if (!chunk)
>  		return;
> +	pcpu_mem_free(chunk->md_blocks);
> +	pcpu_mem_free(chunk->bound_map);
> +	pcpu_mem_free(chunk->alloc_map);
>  	pcpu_mem_free(chunk);
>  }
>  
> @@ -787,6 +1179,7 @@ static void pcpu_chunk_populated(struct pcpu_chunk *chunk,
>  
>  	bitmap_set(chunk->populated, page_start, nr);
>  	chunk->nr_populated += nr;
> +	chunk->nr_empty_pop_pages += nr;
>  	pcpu_nr_empty_pop_pages += nr;
>  }
>  
> @@ -809,6 +1202,7 @@ static void pcpu_chunk_depopulated(struct pcpu_chunk *chunk,
>  
>  	bitmap_clear(chunk->populated, page_start, nr);
>  	chunk->nr_populated -= nr;
> +	chunk->nr_empty_pop_pages -= nr;
>  	pcpu_nr_empty_pop_pages -= nr;
>  }

Didn't we add this field in an earlier patch?  Do the above changes
belong in this patch?

> @@ -890,19 +1284,23 @@ static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved,
>  	struct pcpu_chunk *chunk;
>  	const char *err;
>  	bool is_atomic = (gfp & GFP_KERNEL) != GFP_KERNEL;
> +	int slot, off, cpu, ret;
>  	unsigned long flags;
>  	void __percpu *ptr;
> +	size_t bit_size, bit_align;
>  
>  	/*
> +	 * There is now a minimum allocation size of PCPU_MIN_ALLOC_SIZE.
> +	 * Therefore alignment must be a minimum of that many bytes as well
> +	 * as the allocation will have internal fragmentation from
> +	 * rounding up by up to PCPU_MIN_ALLOC_SIZE - 1 bytes.
>  	 */
> +	if (unlikely(align < PCPU_MIN_ALLOC_SIZE))
> +		align = PCPU_MIN_ALLOC_SIZE;
> +	size = ALIGN(size, PCPU_MIN_ALLOC_SIZE);
> +	bit_size = size >> PCPU_MIN_ALLOC_SHIFT;
> +	bit_align = align >> PCPU_MIN_ALLOC_SHIFT;

Shouldn't the above have happened earlier when MIN_ALLOC_SIZE was
introduced?

> @@ -1363,15 +1710,15 @@ bool is_kernel_percpu_address(unsigned long addr)
>   * address.  The caller is responsible for ensuring @addr stays valid
>   * until this function finishes.
>   *
> - * percpu allocator has special setup for the first chunk, which currently
> + * Percpu allocator has special setup for the first chunk, which currently
>   * supports either embedding in linear address space or vmalloc mapping,
>   * and, from the second one, the backing allocator (currently either vm or
>   * km) provides translation.
>   *
>   * The addr can be translated simply without checking if it falls into the
> - * first chunk. But the current code reflects better how percpu allocator
> + * first chunk.  But the current code reflects better how percpu allocator
>   * actually works, and the verification can discover both bugs in percpu
> - * allocator itself and per_cpu_ptr_to_phys() callers. So we keep current
> + * allocator itself and per_cpu_ptr_to_phys() callers.  So we keep current

Let's please move out what can be to other patches.  This patch is big
enough as it is.

> @@ -1417,9 +1764,10 @@ phys_addr_t per_cpu_ptr_to_phys(void *addr)
>  		else
>  			return page_to_phys(vmalloc_to_page(addr)) +
>  			       offset_in_page(addr);
> -	} else
> +	} else {
>  		return page_to_phys(pcpu_addr_to_page(addr)) +
>  		       offset_in_page(addr);
> +	}

Ditto.

> @@ -1555,10 +1903,12 @@ static void pcpu_dump_alloc_info(const char *lvl,
>   * static areas on architectures where the addressing model has
>   * limited offset range for symbol relocations to guarantee module
>   * percpu symbols fall inside the relocatable range.
> + * @ai->static_size + @ai->reserved_size is expected to be page aligned.
>   *
>   * @ai->dyn_size determines the number of bytes available for dynamic
> - * allocation in the first chunk.  The area between @ai->static_size +
> - * @ai->reserved_size + @ai->dyn_size and @ai->unit_size is unused.
> + * allocation in the first chunk. Both the start and the end are expected
> + * to be page aligned. The area between @ai->static_size + @ai->reserved_size
> + * + @ai->dyn_size and @ai->unit_size is unused.
     ^^^
     contam

>   *
>   * @ai->unit_size specifies unit size and must be aligned to PAGE_SIZE
>   * and equal to or larger than @ai->static_size + @ai->reserved_size +
> @@ -1581,11 +1931,11 @@ static void pcpu_dump_alloc_info(const char *lvl,
>   * copied static data to each unit.
>   *
>   * If the first chunk ends up with both reserved and dynamic areas, it
> - * is served by two chunks - one to serve the core static and reserved
> - * areas and the other for the dynamic area.  They share the same vm
> - * and page map but uses different area allocation map to stay away
> - * from each other.  The latter chunk is circulated in the chunk slots
> - * and available for dynamic allocation like any other chunks.
> + * is served by two chunks - one to serve the reserved area and the other
> + * for the dynamic area.  They share the same vm and page map but use
> + * different area allocation map to stay away from each other.  The latter
> + * chunk is circulated in the chunk slots and available for dynamic allocation
> + * like any other chunks.

ditto

> @@ -1703,7 +2051,8 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  	 * Allocate chunk slots.  The additional last slot is for
>  	 * empty chunks.
>  	 */
> -	pcpu_nr_slots = __pcpu_size_to_slot(pcpu_unit_size) + 2;
> +	pcpu_nr_slots = __pcpu_size_to_slot(
> +				pcpu_pages_to_bits(pcpu_unit_pages)) + 2;

I get that we wanna be using bits inside the area allocator proper but
can we keep things outside in bytes?  These things don't really have
anything to do with what granularity the area allocator is operating
at.

> @@ -1727,69 +2076,50 @@ int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  	tmp_addr = (unsigned long)base_addr + ai->static_size;
>  	aligned_addr = tmp_addr & PAGE_MASK;
>  	pcpu_reserved_offset = tmp_addr - aligned_addr;
> +	begin_fill_bits = pcpu_reserved_offset / PCPU_MIN_ALLOC_SIZE;
>  
>  	map_size_bytes = (ai->reserved_size ?: ai->dyn_size) +
>  			 pcpu_reserved_offset;
> +
>  	chunk_pages = map_size_bytes >> PAGE_SHIFT;
>  
>  	/* chunk adjacent to static region allocation */
> +	chunk = pcpu_alloc_first_chunk(chunk_pages);
>  	chunk->base_addr = (void *)aligned_addr;
>  	chunk->immutable = true;
>  
> +	/* set metadata */
> +	chunk->contig_hint = pcpu_nr_pages_to_bits(chunk) - begin_fill_bits;
> +	chunk->free_bits = pcpu_nr_pages_to_bits(chunk) - begin_fill_bits;
>  
> +	/*
> +	 * If the beginning of the reserved region overlaps the end of the
> +	 * static region, hide that portion in the metadata.
> +	 */
> +	if (begin_fill_bits) {
>  		chunk->has_reserved = true;
> +		bitmap_fill(chunk->alloc_map, begin_fill_bits);
> +		set_bit(0, chunk->bound_map);
> +		set_bit(begin_fill_bits, chunk->bound_map);
> +
> +		if (pcpu_block_update_hint_alloc(chunk, 0, begin_fill_bits))
> +			pcpu_chunk_update_hint(chunk);
>  	}
>  
> +	/* init dynamic chunk if necessary */
> +	if (ai->reserved_size) {
> +		pcpu_reserved_chunk = chunk;
> +
>  		chunk_pages = dyn_size >> PAGE_SHIFT;
>  
>  		/* chunk allocation */
> +		chunk = pcpu_alloc_first_chunk(chunk_pages);
>  		chunk->base_addr = base_addr + ai->static_size +
>  				    ai->reserved_size;
> +
> +		/* set metadata */
> +		chunk->contig_hint = pcpu_nr_pages_to_bits(chunk);
> +		chunk->free_bits = pcpu_nr_pages_to_bits(chunk);
>  	}
>  
>  	/* link the first chunk in */

I *think* that quite a bit of the above can be moved into a separate
patch.

Thanks a lot!

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1690578 — Re: [PATCH 00/10] percpu: replace percpu area map allocator with bitmap allocator

On Sat, Jul 15, 2017 at 10:23:05PM -0400, Dennis Zhou wrote:
> Hi everyone,
> 
> The Linux kernel percpu memory allocator is responsible for managing
> percpu memory. It allocates memory from chunks of percpu areas and uses a
> simple first-fit area allocator to manage allocations inside each chunk.
> There now exist use cases where allocating and deallocating a million or
> more objects occurs making the current implementation inadequate.
> 
> The two primary problems with the current area map allocator are:
>   1. The backing data structure is an array of the areas. To manage this
>      array, it is possible to need to memmove a large portion of it.
>   2. On allocation, chunks are considered based on the contig_hint. It is
>      possible that the contig_hint may be large enough while the alignment 
>      could not meet the request. This causes scanning over every free
>      fragment that could spill over into scanning chunks.
> 
> The primary considerations for the new allocator were the following:
>  - Remove the memmove operation from the critical path
>  - Be conservative with additional use of memory
>  - Provide consistency in performance and memory footprint
>  - Focus on small allocations < 64 bytes
> 
> This patchset introduces a simple bitmap allocator backed by metadata
> blocks as a replacement for the area map allocator for percpu memory. Each
> chunk has an allocation bitmap, a boundary bitmap, and a set of metadata
> blocks. The allocation map serves as the ground truth for allocations
> while the boundary map serves as a way to distinguish between consecutive
> allocations. The minimum allocation size has been increased to 4-bytes.
> 
> The key property behind the bitmap allocator is its static metadata. The
> main problem it solves is that a memmove is no longer part of the critical
> path for freeing, which was the primary source of latency. This also helps
> bound the metadata overhead. The area map allocator prior required an
> integer per allocation. This may be beneficial with larger allocations,
> but as mentioned, allocating a significant number of small objects is
> becoming more common. This causes worst-case scenarios for metadata
> overhead.
> 
> There is one caveat with this implementation. In an effort to make freeing
> fast, the only time metadata is updated on the free path is if a whole
> block becomes free or the freed area spans across metadata blocks. This
> causes the chunk’s contig_hint to be potentially smaller than what it
> could allocate by up to a block. If the chunk’s contig_hint is smaller
> than a block, a check occurs and the hint is kept accurate. Metadata is
> always kept accurate on allocation and therefore the situation where a
> chunk has a larger contig_hint than available will never occur.
> 
> I have primarily done testing against a simple workload of allocation of
> 1 million objects of varying size. Deallocation was done by in order,
> alternating, and in reverse. These numbers were collected after rebasing
> ontop of a80099a152. I present the worst-case numbers here:
> 
>   Area Map Allocator:
> 
>         Object Size | Alloc Time (ms) | Free Time (ms)
>         ----------------------------------------------
>               4B    |        335      |     4960
>              16B    |        485      |     1150
>              64B    |        445      |      280
>             128B    |        505      |      177
>            1024B    |       3385      |      140
> 
>   Bitmap Allocator:
> 
>         Object Size | Alloc Time (ms) | Free Time (ms)
>         ----------------------------------------------
>               4B    |        725      |       70
>              16B    |        760      |       70
>              64B    |        855      |       80
>             128B    |        910      |       90
>            1024B    |       3770      |      260
> 
> This data demonstrates the inability for the area map allocator to
> handle less than ideal situations. In the best case of reverse
> deallocation, the area map allocator was able to perform within range
> of the bitmap allocator. In the worst case situation, freeing took
> nearly 5 seconds for 1 million 4-byte objects. The bitmap allocator
> dramatically improves the consistency of the free path. The small
> allocations performed nearly identical regardless of the freeing
> pattern.
> 
> While it does add to the allocation latency, the allocation scenario
> here is optimal for the area map allocator. The second problem of
> additional scanning can result in the area map allocator completing in
> 52 minutes. The same workload takes only 14 seconds to complete for the
> bitmap allocator. This was produced under a more contrived scenario of
> allocating 1 milion 4-byte objects with 8-byte alignment.
> 

Ok so you say that this test is better for the area map allocator, so presumably
this is worst case for the bitmap allocator?  What does the average case look
like?  Trading 2x allocation latency for a pretty significant free latency
reduction seems ok, but are we allocating or freeing more?  Are both allocations
and free's done in performance critical areas, or do allocations only happen in
performance critical areas, making the increased allocation latency hurt more?
And lastly, why are we paying a 2x latency cost?  What is it about the bitmap
allocator that makes it much worse than the area map allocator?  Thanks,

Josef

[toc] | [prev] | [next] | [standalone]

#1692120 — Re: [PATCH 09/10] percpu: replace area map allocator with bitmap allocator

On Sat, Jul 15, 2017 at 10:23:14PM -0400, Dennis Zhou wrote:
> From: "Dennis Zhou (Facebook)" <dennisszhou@gmail.com>
> 
> The percpu memory allocator is experiencing scalability issues when
> allocating and freeing large numbers of counters as in BPF.
> Additionally, there is a corner case where iteration is triggered over
> all chunks if the contig_hint is the right size, but wrong alignment.
> 
> Implementation:
> This patch removes the area map allocator in favor of a bitmap allocator
> backed by metadata blocks. The primary goal is to provide consistency
> in performance and memory footprint with a focus on small allocations
> (< 64 bytes). The bitmap removes the heavy memmove from the freeing
> critical path and provides a consistent memory footprint. The metadata
> blocks provide a bound on the amount of scanning required by maintaining
> a set of hints.
> 
> The chunks previously were managed by free_size, a value maintained in
> bytes. Now, the chunks are managed in terms of bits, which is just a
> scaled value of free_size down by PCPU_MIN_ALLOC_SIZE.
> 
> There is one caveat with this implementation. In an effort to make
> freeing fast, the only time metadata is updated on the free path is if a
> whole block becomes free or the freed area spans across metadata blocks.
> This causes the chunk’s contig_hint to be potentially smaller than what
> it could allocate by up to a block. If the chunk’s contig_hint is
> smaller than a block, a check occurs and the hint is kept accurate.
> Metadata is always kept accurate on allocation and therefore the
> situation where a chunk has a larger contig_hint than available will
> never occur.
> 
> Evaluation:
> I have primarily done testing against a simple workload of allocation of
> 1 million objects of varying size. Deallocation was done by in order,
> alternating, and in reverse. These numbers were collected after rebasing
> ontop of a80099a152. I present the worst-case numbers here:
> 
>   Area Map Allocator:
> 
>         Object Size | Alloc Time (ms) | Free Time (ms)
>         ----------------------------------------------
>               4B    |        335      |     4960
>              16B    |        485      |     1150
>              64B    |        445      |      280
>             128B    |        505      |      177
>            1024B    |       3385      |      140
> 
>   Bitmap Allocator:
> 
>         Object Size | Alloc Time (ms) | Free Time (ms)
>         ----------------------------------------------
>               4B    |        725      |       70
>              16B    |        760      |       70
>              64B    |        855      |       80
>             128B    |        910      |       90
>            1024B    |       3770      |      260
> 
> This data demonstrates the inability for the area map allocator to
> handle less than ideal situations. In the best case of reverse
> deallocation, the area map allocator was able to perform within range
> of the bitmap allocator. In the worst case situation, freeing took
> nearly 5 seconds for 1 million 4-byte objects. The bitmap allocator
> dramatically improves the consistency of the free path. The small
> allocations performed nearly identical regardless of the freeing
> pattern.
> 
> While it does add to the allocation latency, the allocation scenario
> here is optimal for the area map allocator. The second problem of
> additional scanning can result in the area map allocator completing in
> 52 minutes. The same workload takes only 14 seconds to complete for the
> bitmap allocator. This was produced under a more contrived scenario of
> allocating 1 milion 4-byte objects with 8-byte alignment.
> 

This was a bear to review, I feel like it could be split into a few smaller
pieces.  You are changing hinting, allocating/freeing, and how you find chunks.
Those seem like good logical divisions to me.  Overall the design seems sound
and I didn't spot any major problems.  Once you've split them up I'll do another
thorough comb through and then add my reviewed by.  Thanks,

Josef

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web