Message-ID: <YG5roL/l7qt+9WAM@google.com>
Date:   Thu, 8 Apr 2021 02:34:08 +0000
From:   Dennis Zhou <dennis@...nel.org>
To:     Roman Gushchin <guro@...com>
Cc:     Tejun Heo <tj@...nel.org>, Christoph Lameter <cl@...ux.com>,
        Andrew Morton <akpm@...ux-foundation.org>, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 5/5] percpu: implement partial chunk depopulation

Hello,

On Wed, Apr 07, 2021 at 11:26:18AM -0700, Roman Gushchin wrote:
> This patch implements partial depopulation of percpu chunks.
> 
> As now, a chunk can be depopulated only as a part of the final
> destruction, if there are no more outstanding allocations. However
> to minimize a memory waste it might be useful to depopulate a
> partially filed chunk, if a small number of outstanding allocations
> prevents the chunk from being fully reclaimed.
> 
> This patch implements the following depopulation process: it scans
> over the chunk pages, looks for a range of empty and populated pages
> and performs the depopulation. To avoid races with new allocations,
> the chunk is previously isolated. After the depopulation the chunk is
> sidelined to a special list or freed. New allocations can't be served
> using a sidelined chunk. The chunk can be moved back to a corresponding
> slot if there are not enough chunks with empty populated pages.
> 
> The depopulation is scheduled on the free path. Is the chunk:
>   1) has more than 1/4 of total pages free and populated
>   2) the system has enough free percpu pages aside of this chunk
>   3) isn't the reserved chunk
>   4) isn't the first chunk
>   5) isn't entirely free
> it's a good target for depopulation. If it's already depopulated
> but got free populated pages, it's a good target too.
> The chunk is moved to a special pcpu_depopulate_list, chunk->isolate
> flag is set and the async balancing is scheduled.
> 
> The async balancing moves pcpu_depopulate_list to a local list
> (because pcpu_depopulate_list can be changed when pcpu_lock is
> releases), and then tries to depopulate each chunk.  The depopulation
> is performed in the reverse direction to keep populated pages close to
> the beginning, if the global number of empty pages is reached.
> Depopulated chunks are sidelined to prevent further allocations.
> Skipped and fully empty chunks are returned to the corresponding slot.
> 
> On the allocation path, if there are no suitable chunks found,
> the list of sidelined chunks in scanned prior to creating a new chunk.
> If there is a good sidelined chunk, it's placed back to the slot
> and the scanning is restarted.
> 
> Many thanks to Dennis Zhou for his great ideas and a very constructive
> discussion which led to many improvements in this patchset!
> 
> Signed-off-by: Roman Gushchin <guro@...com>
> ---
>  mm/percpu-internal.h |   2 +
>  mm/percpu.c          | 164 ++++++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 164 insertions(+), 2 deletions(-)
> 
> diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h
> index 095d7eaa0db4..8e432663c41e 100644
> --- a/mm/percpu-internal.h
> +++ b/mm/percpu-internal.h
> @@ -67,6 +67,8 @@ struct pcpu_chunk {
>  
>  	void			*data;		/* chunk data */
>  	bool			immutable;	/* no [de]population allowed */
> +	bool			isolated;	/* isolated from chunk slot lists */
> +	bool			depopulated;    /* sidelined after depopulation */
>  	int			start_offset;	/* the overlap with the previous
>  						   region to have a page aligned
>  						   base_addr */
> diff --git a/mm/percpu.c b/mm/percpu.c
> index e20119668c42..0a5a5e84e0a4 100644
> --- a/mm/percpu.c
> +++ b/mm/percpu.c
> @@ -181,6 +181,19 @@ static LIST_HEAD(pcpu_map_extend_chunks);
>   */
>  int pcpu_nr_empty_pop_pages[PCPU_NR_CHUNK_TYPES];
>  
> +/*
> + * List of chunks with a lot of free pages.  Used to depopulate them
> + * asynchronously.
> + */
> +static struct list_head pcpu_depopulate_list[PCPU_NR_CHUNK_TYPES];
> +
> +/*
> + * List of previously depopulated chunks.  They are not usually used for new
> + * allocations, but can be returned back to service if a need arises.
> + */
> +static struct list_head pcpu_sideline_list[PCPU_NR_CHUNK_TYPES];
> +
> +
>  /*
>   * The number of populated pages in use by the allocator, protected by
>   * pcpu_lock.  This number is kept per a unit per chunk (i.e. when a page gets
> @@ -542,6 +555,12 @@ static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
>  {
>  	int nslot = pcpu_chunk_slot(chunk);
>  
> +	/*
> +	 * Keep isolated and depopulated chunks on a sideline.
> +	 */
> +	if (chunk->isolated || chunk->depopulated)
> +		return;
> +
>  	if (oslot != nslot)
>  		__pcpu_chunk_move(chunk, nslot, oslot < nslot);
>  }
> @@ -1778,6 +1797,25 @@ static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved,
>  		}
>  	}
>  
> +	/* search through sidelined depopulated chunks */
> +	list_for_each_entry(chunk, &pcpu_sideline_list[type], list) {
> +		struct pcpu_block_md *chunk_md = &chunk->chunk_md;
> +		int bit_off;
> +
> +		/*
> +		 * If the allocation can fit in the chunk's contig hint,
> +		 * place the chunk back into corresponding slot and restart
> +		 * the scanning.
> +		 */
> +		bit_off = ALIGN(chunk_md->contig_hint_start, align) -
> +			chunk_md->contig_hint_start;
> +		if (bit_off + bits > chunk_md->contig_hint) {
> +			chunk->depopulated = false;
> +			pcpu_chunk_relocate(chunk, -1);
> +			goto restart;
> +		}

This check should be bit_off + bits < chunk_md->contig_hint.
Can you please factor that out to a function:

pcpu_check_chunk_hint(chunk_md, bits)
{
  int bit_off = (ALIGN(chunk_md->contig_hint_start, align) -
                 chunk_md->contig_hint_start);

  return (bit_off + bits < chunk_md->contig_hint);
}

Then your use case can just call pcpu_check_chunk_hint() and the other
user pcpu_find_block_fit() can use !pcpu_check_chunk_hint().

> +	}
> +
>  	spin_unlock_irqrestore(&pcpu_lock, flags);
>  
>  	/*
> @@ -2048,6 +2086,106 @@ static void pcpu_grow_populated(enum pcpu_chunk_type type, int nr_to_pop)
>  	}
>  }
>  
> +/**
> + * pcpu_shrink_populated - scan chunks and release unused pages to the system
> + * @type: chunk type
> + *
> + * Scan over chunks in the depopulate list, try to release unused populated
> + * pages to the system.  Depopulated chunks are sidelined to prevent further
> + * allocations without a need.  Skipped and fully free chunks are returned
> + * to corresponding slots.  Stop depopulating if the number of empty populated
> + * pages reaches the threshold.  Each chunk is scanned in the reverse order to
> + * keep populated pages close to the beginning of the chunk.
> + */
> +static void pcpu_shrink_populated(enum pcpu_chunk_type type)
> +{
> +	struct pcpu_block_md *block;
> +	struct pcpu_chunk *chunk, *tmp;
> +	LIST_HEAD(to_depopulate);
> +	bool depopulated;
> +	int i, end;
> +
> +	spin_lock_irq(&pcpu_lock);
> +
> +	list_splice_init(&pcpu_depopulate_list[type], &to_depopulate);
> +
> +	list_for_each_entry_safe(chunk, tmp, &to_depopulate, list) {
> +		WARN_ON(chunk->immutable);
> +		depopulated = false;
> +
> +		/*
> +		 * Scan chunk's pages in the reverse order to keep populated
> +		 * pages close to the beginning of the chunk.
> +		 */
> +		for (i = chunk->nr_pages - 1, end = -1; i >= 0; i--) {
> +			/*
> +			 * If the chunk has no empty pages or
> +			 * we're short on empty pages in general,
> +			 * just put the chunk back into the original slot.
> +			 */
> +			if (!chunk->nr_empty_pop_pages ||
> +			    pcpu_nr_empty_pop_pages[type] <=
> +			    PCPU_EMPTY_POP_PAGES_HIGH)
> +				break;
> +
> +			/*
> +			 * If the page is empty and populated, start or
> +			 * extend the (i, end) range.  If i == 0, decrease
> +			 * i and perform the depopulation to cover the last
> +			 * (first) page in the chunk.
> +			 */
> +			block = chunk->md_blocks + i;
> +			if (block->contig_hint == PCPU_BITMAP_BLOCK_BITS &&
> +			    test_bit(i, chunk->populated)) {
> +				if (end == -1)
> +					end = i;
> +				if (i > 0)
> +					continue;
> +				i--;
> +			}
> +
> +			/*
> +			 * Otherwise check if there is an active range,
> +			 * and if yes, depopulate it.
> +			 */
> +			if (end == -1)
> +				continue;
> +
> +			depopulated = true;
> +
> +			spin_unlock_irq(&pcpu_lock);
> +			pcpu_depopulate_chunk(chunk, i + 1, end + 1);
> +			cond_resched();
> +			spin_lock_irq(&pcpu_lock);
> +
> +			pcpu_chunk_depopulated(chunk, i + 1, end + 1);
> +
> +			/*
> +			 * Reset the range and continue.
> +			 */
> +			end = -1;
> +		}
> +
> +		chunk->isolated = false;
> +		if (chunk->free_bytes == pcpu_unit_size || !depopulated) {
> +			/*
> +			 * If the chunk is empty or hasn't been depopulated,
> +			 * return it to the original slot.
> +			 */
> +			pcpu_chunk_relocate(chunk, -1);
> +		} else {
> +			/*
> +			 * Otherwise put the chunk to the list of depopulated
> +			 * chunks.
> +			 */
> +			chunk->depopulated = true;
> +			list_move(&chunk->list, &pcpu_sideline_list[type]);
> +		}
> +	}
> +
> +	spin_unlock_irq(&pcpu_lock);
> +}
> +
>  /**
>   * pcpu_balance_populated - manage the amount of populated pages
>   * @type: chunk type
> @@ -2078,6 +2216,8 @@ static void pcpu_balance_populated(enum pcpu_chunk_type type)
>  	} else if (pcpu_nr_empty_pop_pages[type] < PCPU_EMPTY_POP_PAGES_HIGH) {
>  		nr_to_pop = PCPU_EMPTY_POP_PAGES_HIGH - pcpu_nr_empty_pop_pages[type];
>  		pcpu_grow_populated(type, nr_to_pop);
> +	} else if (!list_empty(&pcpu_depopulate_list[type])) {
> +		pcpu_shrink_populated(type);
>  	}
>  }
>  
> @@ -2135,7 +2275,13 @@ void free_percpu(void __percpu *ptr)
>  
>  	pcpu_memcg_free_hook(chunk, off, size);
>  
> -	/* if there are more than one fully free chunks, wake up grim reaper */
> +	/*
> +	 * If there are more than one fully free chunks, wake up grim reaper.
> +	 * Otherwise if at least 1/4 of its pages are empty and there is no
> +	 * system-wide shortage of empty pages aside from this chunk, isolate
> +	 * the chunk and schedule an async depopulation.  If the chunk was
> +	 * depopulated previously and got free pages, depopulate it too.
> +	 */
>  	if (chunk->free_bytes == pcpu_unit_size) {
>  		struct pcpu_chunk *pos;
>  
> @@ -2144,6 +2290,16 @@ void free_percpu(void __percpu *ptr)
>  				need_balance = true;
>  				break;
>  			}
> +	} else if (chunk != pcpu_first_chunk && chunk != pcpu_reserved_chunk &&
> +		   !chunk->isolated &&
> +		   pcpu_nr_empty_pop_pages[pcpu_chunk_type(chunk)] >
> +		   PCPU_EMPTY_POP_PAGES_HIGH + chunk->nr_empty_pop_pages &&

nit: can you add parethesis around this condition?

> +		   ((chunk->depopulated && chunk->nr_empty_pop_pages) ||
> +		    (chunk->nr_empty_pop_pages >= chunk->nr_pages / 4))) {
> +		list_move(&chunk->list, &pcpu_depopulate_list[pcpu_chunk_type(chunk)]);
> +		chunk->isolated = true;
> +		chunk->depopulated = false;
> +		need_balance = true;
>  	}
>  
>  	trace_percpu_free_percpu(chunk->base_addr, off, ptr);
> @@ -2571,10 +2727,14 @@ void __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
>  		      pcpu_nr_slots * sizeof(pcpu_chunk_lists[0]) *
>  		      PCPU_NR_CHUNK_TYPES);
>  
> -	for (type = 0; type < PCPU_NR_CHUNK_TYPES; type++)
> +	for (type = 0; type < PCPU_NR_CHUNK_TYPES; type++) {
>  		for (i = 0; i < pcpu_nr_slots; i++)
>  			INIT_LIST_HEAD(&pcpu_chunk_list(type)[i]);
>  
> +		INIT_LIST_HEAD(&pcpu_depopulate_list[type]);
> +		INIT_LIST_HEAD(&pcpu_sideline_list[type]);
> +	}
> +
>  	/*
>  	 * The end of the static region needs to be aligned with the
>  	 * minimum allocation size as this offsets the reserved and
> -- 
> 2.30.2
> 

Thanks,
Dennis

Powered by blists - more mailing lists