/*

   * mm/percpu.c - percpu memory allocator

   *
   * Copyright (C) 2009		SUSE Linux Products GmbH
   * Copyright (C) 2009		Tejun Heo <tj@kernel.org>
   *

   * Copyright (C) 2017		Facebook Inc.
   * Copyright (C) 2017		Dennis Zhou <dennisszhou@gmail.com>
   *

   * This file is released under the GPLv2 license.

   *

   * The percpu allocator handles both static and dynamic areas.  Percpu
   * areas are allocated in chunks which are divided into units.  There is
   * a 1-to-1 mapping for units to possible cpus.  These units are grouped
   * based on NUMA properties of the machine.

   *
   *  c0                           c1                         c2
   *  -------------------          -------------------        ------------
   * | u0 | u1 | u2 | u3 |        | u0 | u1 | u2 | u3 |      | u0 | u1 | u
   *  -------------------  ......  -------------------  ....  ------------
   *

   * Allocation is done by offsets into a unit's address space.  Ie., an
   * area of 512 bytes at 6k in c1 occupies 512 bytes at 6k in c1:u0,
   * c1:u1, c1:u2, etc.  On NUMA machines, the mapping may be non-linear
   * and even sparse.  Access is handled by configuring percpu base
   * registers according to the cpu to unit mappings and offsetting the
   * base address using pcpu_unit_size.
   *
   * There is special consideration for the first chunk which must handle
   * the static percpu variables in the kernel image as allocation services

   * are not online yet.  In short, the first chunk is structured like so:

   *
   *                  <Static | [Reserved] | Dynamic>
   *
   * The static data is copied from the original section managed by the
   * linker.  The reserved section, if non-zero, primarily manages static
   * percpu variables from kernel modules.  Finally, the dynamic section
   * takes care of normal allocations.

   *

   * The allocator organizes chunks into lists according to free size and
   * tries to allocate from the fullest chunk first.  Each chunk is managed
   * by a bitmap with metadata blocks.  The allocation map is updated on
   * every allocation and free to reflect the current state while the boundary
   * map is only updated on allocation.  Each metadata block contains
   * information to help mitigate the need to iterate over large portions
   * of the bitmap.  The reverse mapping from page to chunk is stored in
   * the page's index.  Lastly, units are lazily backed and grow in unison.
   *
   * There is a unique conversion that goes on here between bytes and bits.
   * Each bit represents a fragment of size PCPU_MIN_ALLOC_SIZE.  The chunk
   * tracks the number of pages it is responsible for in nr_pages.  Helper
   * functions are used to convert from between the bytes, bits, and blocks.
   * All hints are managed in bits unless explicitly stated.

   *

   * To use this allocator, arch code should do the following:

   *

   * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate

   *   regular address to percpu pointer and back if they need to be
   *   different from the default

   *

   * - use pcpu_setup_first_chunk() during percpu area initialization to
   *   setup the first chunk containing the kernel static percpu area

   */

  #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

  #include <linux/bitmap.h>
  #include <linux/bootmem.h>

  #include <linux/err.h>

  #include <linux/lcm.h>

  #include <linux/list.h>

  #include <linux/log2.h>

  #include <linux/mm.h>
  #include <linux/module.h>
  #include <linux/mutex.h>
  #include <linux/percpu.h>
  #include <linux/pfn.h>

  #include <linux/slab.h>

  #include <linux/spinlock.h>

  #include <linux/vmalloc.h>

  #include <linux/workqueue.h>

  #include <linux/kmemleak.h>

  #include <linux/sched.h>

  
  #include <asm/cacheflush.h>

  #include <asm/sections.h>

  #include <asm/tlbflush.h>

  #include <asm/io.h>

  #define CREATE_TRACE_POINTS
  #include <trace/events/percpu.h>

  #include "percpu-internal.h"

  /* the slots are sorted by free bytes left, 1-31 bytes share the same slot */
  #define PCPU_SLOT_BASE_SHIFT		5

  #define PCPU_EMPTY_POP_PAGES_LOW	2
  #define PCPU_EMPTY_POP_PAGES_HIGH	4

  #ifdef CONFIG_SMP

  /* default addr <-> pcpu_ptr mapping, override in asm/percpu.h if necessary */
  #ifndef __addr_to_pcpu_ptr
  #define __addr_to_pcpu_ptr(addr)					\

  	(void __percpu *)((unsigned long)(addr) -			\
  			  (unsigned long)pcpu_base_addr	+		\
  			  (unsigned long)__per_cpu_start)

  #endif
  #ifndef __pcpu_ptr_to_addr
  #define __pcpu_ptr_to_addr(ptr)						\

  	(void __force *)((unsigned long)(ptr) +				\
  			 (unsigned long)pcpu_base_addr -		\
  			 (unsigned long)__per_cpu_start)

  #endif

  #else	/* CONFIG_SMP */
  /* on UP, it's always identity mapped */
  #define __addr_to_pcpu_ptr(addr)	(void __percpu *)(addr)
  #define __pcpu_ptr_to_addr(ptr)		(void __force *)(ptr)
  #endif	/* CONFIG_SMP */

  static int pcpu_unit_pages __ro_after_init;
  static int pcpu_unit_size __ro_after_init;
  static int pcpu_nr_units __ro_after_init;
  static int pcpu_atom_size __ro_after_init;

  int pcpu_nr_slots __ro_after_init;

  static size_t pcpu_chunk_struct_size __ro_after_init;

  /* cpus with the lowest and highest unit addresses */

  static unsigned int pcpu_low_unit_cpu __ro_after_init;
  static unsigned int pcpu_high_unit_cpu __ro_after_init;

  /* the address of the first chunk which starts with the kernel static area */

  void *pcpu_base_addr __ro_after_init;

  EXPORT_SYMBOL_GPL(pcpu_base_addr);

  static const int *pcpu_unit_map __ro_after_init;		/* cpu -> unit */
  const unsigned long *pcpu_unit_offsets __ro_after_init;	/* cpu -> unit offset */

  /* group information, used for vm allocation */

  static int pcpu_nr_groups __ro_after_init;
  static const unsigned long *pcpu_group_offsets __ro_after_init;
  static const size_t *pcpu_group_sizes __ro_after_init;

  /*
   * The first chunk which always exists.  Note that unlike other
   * chunks, this one can be allocated and mapped in several different
   * ways and thus often doesn't live in the vmalloc area.
   */

  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.  When the reserved
   * region doesn't exist, the following variable is NULL.

   */

  struct pcpu_chunk *pcpu_reserved_chunk __ro_after_init;

  DEFINE_SPINLOCK(pcpu_lock);	/* all internal data structures */

  static DEFINE_MUTEX(pcpu_alloc_mutex);	/* chunk create/destroy, [de]pop, map ext */

  struct list_head *pcpu_slot __ro_after_init; /* chunk list slots */

  /* chunks which need their map areas extended, protected by pcpu_lock */
  static LIST_HEAD(pcpu_map_extend_chunks);

  /*
   * The number of empty populated pages, protected by pcpu_lock.  The
   * reserved chunk doesn't contribute to the count.
   */

  int pcpu_nr_empty_pop_pages;

  /*
   * Balance work is used to populate or destroy chunks asynchronously.  We
   * try to keep the number of populated free pages between
   * PCPU_EMPTY_POP_PAGES_LOW and HIGH for atomic allocations and at most one
   * empty chunk.
   */

  static void pcpu_balance_workfn(struct work_struct *work);
  static DECLARE_WORK(pcpu_balance_work, pcpu_balance_workfn);

  static bool pcpu_async_enabled __read_mostly;
  static bool pcpu_atomic_alloc_failed;
  
  static void pcpu_schedule_balance_work(void)
  {
  	if (pcpu_async_enabled)
  		schedule_work(&pcpu_balance_work);
  }

  /**

   * pcpu_addr_in_chunk - check if the address is served from this chunk
   * @chunk: chunk of interest
   * @addr: percpu address

   *
   * RETURNS:

   * True if the address is served from this chunk.

   */

  static bool pcpu_addr_in_chunk(struct pcpu_chunk *chunk, void *addr)

  {

  	void *start_addr, *end_addr;

  	if (!chunk)

  		return false;

  	start_addr = chunk->base_addr + chunk->start_offset;
  	end_addr = chunk->base_addr + chunk->nr_pages * PAGE_SIZE -
  		   chunk->end_offset;

  
  	return addr >= start_addr && addr < end_addr;

  }

  static int __pcpu_size_to_slot(int size)

  {

  	int highbit = fls(size);	/* size is in bytes */

  	return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);
  }

  static int pcpu_size_to_slot(int size)
  {
  	if (size == pcpu_unit_size)
  		return pcpu_nr_slots - 1;
  	return __pcpu_size_to_slot(size);
  }

  static int pcpu_chunk_slot(const struct pcpu_chunk *chunk)
  {

  	if (chunk->free_bytes < PCPU_MIN_ALLOC_SIZE || chunk->contig_bits == 0)

  		return 0;

  	return pcpu_size_to_slot(chunk->free_bytes);

  }

  /* set the pointer to a chunk in a page struct */
  static void pcpu_set_page_chunk(struct page *page, struct pcpu_chunk *pcpu)
  {
  	page->index = (unsigned long)pcpu;
  }
  
  /* obtain pointer to a chunk from a page struct */
  static struct pcpu_chunk *pcpu_get_page_chunk(struct page *page)
  {
  	return (struct pcpu_chunk *)page->index;
  }
  
  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_page_offset(cpu, page_idx);

  }

  static void pcpu_next_unpop(unsigned long *bitmap, int *rs, int *re, int end)

  {

  	*rs = find_next_zero_bit(bitmap, end, *rs);
  	*re = find_next_bit(bitmap, end, *rs + 1);

  }

  static void pcpu_next_pop(unsigned long *bitmap, int *rs, int *re, int end)

  {

  	*rs = find_next_bit(bitmap, end, *rs);
  	*re = find_next_zero_bit(bitmap, end, *rs + 1);

  }
  
  /*

   * Bitmap region iterators.  Iterates over the bitmap between
   * [@start, @end) in @chunk.  @rs and @re should be integer variables
   * and will be set to start and end index of the current free region.

   */

  #define pcpu_for_each_unpop_region(bitmap, rs, re, start, end)		     \
  	for ((rs) = (start), pcpu_next_unpop((bitmap), &(rs), &(re), (end)); \
  	     (rs) < (re);						     \
  	     (rs) = (re) + 1, pcpu_next_unpop((bitmap), &(rs), &(re), (end)))

  #define pcpu_for_each_pop_region(bitmap, rs, re, start, end)		     \
  	for ((rs) = (start), pcpu_next_pop((bitmap), &(rs), &(re), (end));   \
  	     (rs) < (re);						     \
  	     (rs) = (re) + 1, pcpu_next_pop((bitmap), &(rs), &(re), (end)))

  /*
   * The following are helper functions to help access bitmaps and convert
   * between bitmap offsets to address offsets.
   */
  static unsigned long *pcpu_index_alloc_map(struct pcpu_chunk *chunk, int index)
  {
  	return chunk->alloc_map +
  	       (index * PCPU_BITMAP_BLOCK_BITS / BITS_PER_LONG);
  }
  
  static unsigned long pcpu_off_to_block_index(int off)
  {
  	return off / PCPU_BITMAP_BLOCK_BITS;
  }
  
  static unsigned long pcpu_off_to_block_off(int off)
  {
  	return off & (PCPU_BITMAP_BLOCK_BITS - 1);
  }

  static unsigned long pcpu_block_off_to_off(int index, int off)
  {
  	return index * PCPU_BITMAP_BLOCK_BITS + off;
  }

  /**

   * pcpu_next_md_free_region - finds the next hint free area
   * @chunk: chunk of interest
   * @bit_off: chunk offset
   * @bits: size of free area
   *
   * Helper function for pcpu_for_each_md_free_region.  It checks
   * block->contig_hint and performs aggregation across blocks to find the
   * next hint.  It modifies bit_off and bits in-place to be consumed in the
   * loop.
   */
  static void pcpu_next_md_free_region(struct pcpu_chunk *chunk, int *bit_off,
  				     int *bits)
  {
  	int i = pcpu_off_to_block_index(*bit_off);
  	int block_off = pcpu_off_to_block_off(*bit_off);
  	struct pcpu_block_md *block;
  
  	*bits = 0;
  	for (block = chunk->md_blocks + i; i < pcpu_chunk_nr_blocks(chunk);
  	     block++, i++) {
  		/* handles contig area across blocks */
  		if (*bits) {
  			*bits += block->left_free;
  			if (block->left_free == PCPU_BITMAP_BLOCK_BITS)
  				continue;
  			return;
  		}
  
  		/*
  		 * This checks three things.  First is there a contig_hint to
  		 * check.  Second, have we checked this hint before by
  		 * comparing the block_off.  Third, is this the same as the
  		 * right contig hint.  In the last case, it spills over into
  		 * the next block and should be handled by the contig area
  		 * across blocks code.
  		 */
  		*bits = block->contig_hint;
  		if (*bits && block->contig_hint_start >= block_off &&
  		    *bits + block->contig_hint_start < PCPU_BITMAP_BLOCK_BITS) {
  			*bit_off = pcpu_block_off_to_off(i,
  					block->contig_hint_start);
  			return;
  		}

  		/* reset to satisfy the second predicate above */
  		block_off = 0;

  
  		*bits = block->right_free;
  		*bit_off = (i + 1) * PCPU_BITMAP_BLOCK_BITS - block->right_free;
  	}
  }

  /**
   * pcpu_next_fit_region - finds fit areas for a given allocation request
   * @chunk: chunk of interest
   * @alloc_bits: size of allocation
   * @align: alignment of area (max PAGE_SIZE)
   * @bit_off: chunk offset
   * @bits: size of free area
   *
   * Finds the next free region that is viable for use with a given size and
   * alignment.  This only returns if there is a valid area to be used for this
   * allocation.  block->first_free is returned if the allocation request fits
   * within the block to see if the request can be fulfilled prior to the contig
   * hint.
   */
  static void pcpu_next_fit_region(struct pcpu_chunk *chunk, int alloc_bits,
  				 int align, int *bit_off, int *bits)
  {
  	int i = pcpu_off_to_block_index(*bit_off);
  	int block_off = pcpu_off_to_block_off(*bit_off);
  	struct pcpu_block_md *block;
  
  	*bits = 0;
  	for (block = chunk->md_blocks + i; i < pcpu_chunk_nr_blocks(chunk);
  	     block++, i++) {
  		/* handles contig area across blocks */
  		if (*bits) {
  			*bits += block->left_free;
  			if (*bits >= alloc_bits)
  				return;
  			if (block->left_free == PCPU_BITMAP_BLOCK_BITS)
  				continue;
  		}
  
  		/* check block->contig_hint */
  		*bits = ALIGN(block->contig_hint_start, align) -
  			block->contig_hint_start;
  		/*
  		 * This uses the block offset to determine if this has been
  		 * checked in the prior iteration.
  		 */
  		if (block->contig_hint &&
  		    block->contig_hint_start >= block_off &&
  		    block->contig_hint >= *bits + alloc_bits) {
  			*bits += alloc_bits + block->contig_hint_start -
  				 block->first_free;
  			*bit_off = pcpu_block_off_to_off(i, block->first_free);
  			return;
  		}

  		/* reset to satisfy the second predicate above */
  		block_off = 0;

  
  		*bit_off = ALIGN(PCPU_BITMAP_BLOCK_BITS - block->right_free,
  				 align);
  		*bits = PCPU_BITMAP_BLOCK_BITS - *bit_off;
  		*bit_off = pcpu_block_off_to_off(i, *bit_off);
  		if (*bits >= alloc_bits)
  			return;
  	}
  
  	/* no valid offsets were found - fail condition */
  	*bit_off = pcpu_chunk_map_bits(chunk);
  }

  /*
   * Metadata free area iterators.  These perform aggregation of free areas
   * based on the metadata blocks and return the offset @bit_off and size in

   * bits of the free area @bits.  pcpu_for_each_fit_region only returns when
   * a fit is found for the allocation request.

   */
  #define pcpu_for_each_md_free_region(chunk, bit_off, bits)		\
  	for (pcpu_next_md_free_region((chunk), &(bit_off), &(bits));	\
  	     (bit_off) < pcpu_chunk_map_bits((chunk));			\
  	     (bit_off) += (bits) + 1,					\
  	     pcpu_next_md_free_region((chunk), &(bit_off), &(bits)))

  #define pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits)     \
  	for (pcpu_next_fit_region((chunk), (alloc_bits), (align), &(bit_off), \
  				  &(bits));				      \
  	     (bit_off) < pcpu_chunk_map_bits((chunk));			      \
  	     (bit_off) += (bits),					      \
  	     pcpu_next_fit_region((chunk), (alloc_bits), (align), &(bit_off), \
  				  &(bits)))

  /**

   * pcpu_mem_zalloc - allocate memory

   * @size: bytes to allocate

   * @gfp: allocation flags

   *

   * Allocate @size bytes.  If @size is smaller than PAGE_SIZE,

   * kzalloc() is used; otherwise, the equivalent of vzalloc() is used.
   * This is to facilitate passing through whitelisted flags.  The
   * returned memory is always zeroed.

   *

   * CONTEXT:
   * Does GFP_KERNEL allocation.
   *

   * RETURNS:

   * Pointer to the allocated area on success, NULL on failure.

   */

  static void *pcpu_mem_zalloc(size_t size, gfp_t gfp)

  {

  	if (WARN_ON_ONCE(!slab_is_available()))
  		return NULL;

  	if (size <= PAGE_SIZE)

  		return kzalloc(size, gfp | GFP_KERNEL);

  	else

  		return __vmalloc(size, gfp | GFP_KERNEL | __GFP_ZERO,
  				 PAGE_KERNEL);

  }

  /**
   * pcpu_mem_free - free memory
   * @ptr: memory to free

   *

   * Free @ptr.  @ptr should have been allocated using pcpu_mem_zalloc().

   */

  static void pcpu_mem_free(void *ptr)

  {

  	kvfree(ptr);

  }
  
  /**
   * pcpu_chunk_relocate - put chunk in the appropriate chunk slot
   * @chunk: chunk of interest
   * @oslot: the previous slot it was on
   *
   * This function is called after an allocation or free changed @chunk.
   * New slot according to the changed state is determined and @chunk is

   * moved to the slot.  Note that the reserved chunk is never put on
   * chunk slots.

   *
   * CONTEXT:
   * pcpu_lock.

   */
  static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
  {
  	int nslot = pcpu_chunk_slot(chunk);

  	if (chunk != pcpu_reserved_chunk && oslot != nslot) {

  		if (oslot < nslot)
  			list_move(&chunk->list, &pcpu_slot[nslot]);
  		else
  			list_move_tail(&chunk->list, &pcpu_slot[nslot]);
  	}
  }

  /**

   * pcpu_cnt_pop_pages- counts populated backing pages in range

   * @chunk: chunk of interest

   * @bit_off: start offset
   * @bits: size of area to check

   *

   * Calculates the number of populated pages in the region
   * [page_start, page_end).  This keeps track of how many empty populated
   * pages are available and decide if async work should be scheduled.

   *

   * RETURNS:

   * The nr of populated pages.

   */

  static inline int pcpu_cnt_pop_pages(struct pcpu_chunk *chunk, int bit_off,
  				     int bits)

  {

  	int page_start = PFN_UP(bit_off * PCPU_MIN_ALLOC_SIZE);
  	int page_end = PFN_DOWN((bit_off + bits) * PCPU_MIN_ALLOC_SIZE);

  	if (page_start >= page_end)

  		return 0;

  	/*
  	 * bitmap_weight counts the number of bits set in a bitmap up to
  	 * the specified number of bits.  This is counting the populated
  	 * pages up to page_end and then subtracting the populated pages
  	 * up to page_start to count the populated pages in
  	 * [page_start, page_end).
  	 */
  	return bitmap_weight(chunk->populated, page_end) -
  	       bitmap_weight(chunk->populated, page_start);

  }
  
  /**

   * pcpu_chunk_update - updates the chunk metadata given a free area

   * @chunk: chunk of interest

   * @bit_off: chunk offset
   * @bits: size of free area

   *

   * This updates the chunk's contig hint and starting offset given a free area.

   * Choose the best starting offset if the contig hint is equal.

   */
  static void pcpu_chunk_update(struct pcpu_chunk *chunk, int bit_off, int bits)
  {

  	if (bits > chunk->contig_bits) {
  		chunk->contig_bits_start = bit_off;

  		chunk->contig_bits = bits;

  	} else if (bits == chunk->contig_bits && chunk->contig_bits_start &&
  		   (!bit_off ||
  		    __ffs(bit_off) > __ffs(chunk->contig_bits_start))) {
  		/* use the start with the best alignment */
  		chunk->contig_bits_start = bit_off;

  	}

  }
  
  /**
   * pcpu_chunk_refresh_hint - updates metadata about a chunk
   * @chunk: chunk of interest

   *

   * Iterates over the metadata blocks to find the largest contig area.
   * It also counts the populated pages and uses the delta to update the
   * global count.

   *

   * Updates:
   *      chunk->contig_bits

   *      chunk->contig_bits_start

   *      nr_empty_pop_pages (chunk and global)

   */

  static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk)

  {

  	int bit_off, bits, nr_empty_pop_pages;

  	/* clear metadata */
  	chunk->contig_bits = 0;

  	bit_off = chunk->first_bit;

  	bits = nr_empty_pop_pages = 0;

  	pcpu_for_each_md_free_region(chunk, bit_off, bits) {
  		pcpu_chunk_update(chunk, bit_off, bits);

  		nr_empty_pop_pages += pcpu_cnt_pop_pages(chunk, bit_off, bits);

  	}

  	/*
  	 * Keep track of nr_empty_pop_pages.
  	 *
  	 * The chunk 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 (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;
  }

  /**

   * pcpu_block_update - updates a block given a free area
   * @block: block of interest
   * @start: start offset in block
   * @end: end offset in block
   *
   * Updates a block given a known free area.  The region [start, end) is

   * expected to be the entirety of the free area within a block.  Chooses
   * the best starting offset if the contig hints are equal.

   */
  static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
  {
  	int contig = end - start;
  
  	block->first_free = min(block->first_free, start);
  	if (start == 0)
  		block->left_free = contig;
  
  	if (end == PCPU_BITMAP_BLOCK_BITS)
  		block->right_free = contig;
  
  	if (contig > block->contig_hint) {
  		block->contig_hint_start = start;
  		block->contig_hint = contig;

  	} else if (block->contig_hint_start && contig == block->contig_hint &&
  		   (!start || __ffs(start) > __ffs(block->contig_hint_start))) {
  		/* use the start with the best alignment */
  		block->contig_hint_start = start;

  	}
  }
  
  /**
   * pcpu_block_refresh_hint
   * @chunk: chunk of interest
   * @index: index of the metadata block
   *
   * Scans over the block beginning at first_free and updates the block
   * metadata accordingly.
   */
  static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index)
  {
  	struct pcpu_block_md *block = chunk->md_blocks + index;
  	unsigned long *alloc_map = pcpu_index_alloc_map(chunk, index);
  	int rs, re;	/* region start, region end */
  
  	/* clear hints */
  	block->contig_hint = 0;
  	block->left_free = block->right_free = 0;
  
  	/* iterate over free areas and update the contig hints */
  	pcpu_for_each_unpop_region(alloc_map, rs, re, block->first_free,
  				   PCPU_BITMAP_BLOCK_BITS) {
  		pcpu_block_update(block, rs, re);
  	}
  }
  
  /**
   * pcpu_block_update_hint_alloc - update hint on allocation path
   * @chunk: chunk of interest
   * @bit_off: chunk offset
   * @bits: size of request

   *
   * Updates metadata for the allocation path.  The metadata only has to be
   * refreshed by a full scan iff the chunk's contig hint is broken.  Block level
   * scans are required if the block's contig hint is broken.

   */
  static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
  					 int bits)
  {
  	struct pcpu_block_md *s_block, *e_block, *block;
  	int s_index, e_index;	/* block indexes of the freed allocation */
  	int s_off, e_off;	/* block offsets of the freed allocation */
  
  	/*
  	 * Calculate per block offsets.
  	 * The calculation uses an inclusive range, but the resulting offsets
  	 * are [start, end).  e_index always points to the last block in the
  	 * range.
  	 */
  	s_index = pcpu_off_to_block_index(bit_off);
  	e_index = pcpu_off_to_block_index(bit_off + bits - 1);
  	s_off = pcpu_off_to_block_off(bit_off);
  	e_off = pcpu_off_to_block_off(bit_off + bits - 1) + 1;
  
  	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_BITS,
  					s_off + bits);
  
  	if (s_off >= s_block->contig_hint_start &&
  	    s_off < s_block->contig_hint_start + s_block->contig_hint) {
  		/* block contig hint is broken - scan to fix it */
  		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_BITS - e_off);
  		else
  			s_block->right_free = 0;
  	}

  
  	/*
  	 * Update e_block.
  	 */
  	if (s_index != e_index) {

  		/*
  		 * When the allocation is across blocks, the end is along
  		 * the left part of the e_block.
  		 */
  		e_block->first_free = find_next_zero_bit(
  				pcpu_index_alloc_map(chunk, e_index),
  				PCPU_BITMAP_BLOCK_BITS, e_off);
  
  		if (e_off == PCPU_BITMAP_BLOCK_BITS) {
  			/* reset the block */
  			e_block++;
  		} else {
  			if (e_off > e_block->contig_hint_start) {
  				/* contig hint is broken - scan to fix it */
  				pcpu_block_refresh_hint(chunk, e_index);
  			} else {
  				e_block->left_free = 0;
  				e_block->right_free =
  					min_t(int, e_block->right_free,
  					      PCPU_BITMAP_BLOCK_BITS - e_off);
  			}
  		}

  
  		/* update in-between md_blocks */
  		for (block = s_block + 1; block < e_block; 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 chunk
  	 * contig hint is broken.  Otherwise, it means a smaller space
  	 * was used and therefore the chunk contig hint is still correct.
  	 */
  	if (bit_off >= chunk->contig_bits_start  &&
  	    bit_off < chunk->contig_bits_start + chunk->contig_bits)
  		pcpu_chunk_refresh_hint(chunk);

  }
  
  /**
   * pcpu_block_update_hint_free - updates the block hints on the free path
   * @chunk: chunk of interest
   * @bit_off: chunk offset
   * @bits: size of request

   *
   * Updates metadata for the allocation path.  This avoids a blind block
   * refresh by making use of the block contig hints.  If this fails, it scans
   * forward and backward to determine the extent of the free area.  This is
   * capped at the boundary of blocks.
   *
   * A chunk update is triggered if a page becomes free, a block becomes free,
   * or the free spans across blocks.  This tradeoff is to minimize iterating
   * over the block metadata to update chunk->contig_bits.  chunk->contig_bits
   * may be off by up to a page, but it will never be more than the available
   * space.  If the contig hint is contained in one block, it will be accurate.

   */
  static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off,
  					int bits)
  {
  	struct pcpu_block_md *s_block, *e_block, *block;
  	int s_index, e_index;	/* block indexes of the freed allocation */
  	int s_off, e_off;	/* block offsets of the freed allocation */

  	int start, end;		/* start and end of the whole free area */

  
  	/*
  	 * Calculate per block offsets.
  	 * The calculation uses an inclusive range, but the resulting offsets
  	 * are [start, end).  e_index always points to the last block in the
  	 * range.
  	 */
  	s_index = pcpu_off_to_block_index(bit_off);
  	e_index = pcpu_off_to_block_index(bit_off + bits - 1);
  	s_off = pcpu_off_to_block_off(bit_off);
  	e_off = pcpu_off_to_block_off(bit_off + bits - 1) + 1;
  
  	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 area
  	 * within each their respective blocks.  This is not necessarily
  	 * the entire free area 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 {
  		/*
  		 * Scan backwards to find the extent of the free area.
  		 * find_last_bit returns the starting bit, so if the start bit
  		 * is returned, that means there was no last bit and the
  		 * remainder of the chunk is free.
  		 */
  		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_BITS, end);

  	/* update s_block */

  	e_off = (s_index == e_index) ? end : PCPU_BITMAP_BLOCK_BITS;
  	pcpu_block_update(s_block, start, e_off);

  
  	/* freeing in the same block */
  	if (s_index != e_index) {
  		/* update e_block */

  		pcpu_block_update(e_block, 0, end);

  
  		/* reset md_blocks in the middle */
  		for (block = s_block + 1; block < e_block; block++) {
  			block->first_free = 0;
  			block->contig_hint_start = 0;
  			block->contig_hint = PCPU_BITMAP_BLOCK_BITS;
  			block->left_free = PCPU_BITMAP_BLOCK_BITS;
  			block->right_free = PCPU_BITMAP_BLOCK_BITS;
  		}
  	}

  	/*
  	 * Refresh chunk metadata when the free makes a page free, a block
  	 * free, or spans across blocks.  The contig hint may be off by up to
  	 * a page, but if the hint is contained in a block, it will be accurate
  	 * with the else condition below.
  	 */
  	if ((ALIGN_DOWN(end, min(PCPU_BITS_PER_PAGE, PCPU_BITMAP_BLOCK_BITS)) >
  	     ALIGN(start, min(PCPU_BITS_PER_PAGE, PCPU_BITMAP_BLOCK_BITS))) ||
  	    s_index != e_index)
  		pcpu_chunk_refresh_hint(chunk);
  	else
  		pcpu_chunk_update(chunk, pcpu_block_off_to_off(s_index, start),
  				  s_block->contig_hint);

  }
  
  /**

   * pcpu_is_populated - determines if the region is populated
   * @chunk: chunk of interest
   * @bit_off: chunk offset
   * @bits: size of area
   * @next_off: return value for the next offset to start searching
   *
   * For atomic allocations, check if the backing pages are populated.
   *
   * RETURNS:
   * Bool if the backing pages are populated.
   * next_index is to skip over unpopulated blocks in pcpu_find_block_fit.
   */
  static bool pcpu_is_populated(struct pcpu_chunk *chunk, int bit_off, int bits,
  			      int *next_off)
  {
  	int page_start, page_end, rs, re;

  	page_start = PFN_DOWN(bit_off * PCPU_MIN_ALLOC_SIZE);
  	page_end = PFN_UP((bit_off + bits) * PCPU_MIN_ALLOC_SIZE);

  	rs = page_start;
  	pcpu_next_unpop(chunk->populated, &rs, &re, page_end);
  	if (rs >= page_end)
  		return true;

  	*next_off = re * PAGE_SIZE / PCPU_MIN_ALLOC_SIZE;
  	return false;

  }
  
  /**

   * pcpu_find_block_fit - finds the block index to start searching
   * @chunk: chunk of interest
   * @alloc_bits: size of request in allocation units
   * @align: alignment of area (max PAGE_SIZE bytes)
   * @pop_only: use populated regions only
   *

   * Given a chunk and an allocation spec, find the offset to begin searching
   * for a free region.  This iterates over the bitmap metadata blocks to
   * find an offset that will be guaranteed to fit the requirements.  It is
   * not quite first fit as if the allocation does not fit in the contig hint
   * of a block or chunk, it is skipped.  This errs on the side of caution
   * to prevent excess iteration.  Poor alignment can cause the allocator to
   * skip over blocks and chunks that have valid free areas.
   *

   * RETURNS:
   * The offset in the bitmap to begin searching.
   * -1 if no offset is found.

   */

  static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits,
  			       size_t align, bool pop_only)

  {

  	int bit_off, bits, next_off;

  	/*
  	 * Check to see if the allocation can fit in the chunk's contig hint.
  	 * This is an optimization to prevent scanning by assuming if it
  	 * cannot fit in the global hint, there is memory pressure and creating
  	 * a new chunk would happen soon.
  	 */
  	bit_off = ALIGN(chunk->contig_bits_start, align) -
  		  chunk->contig_bits_start;
  	if (bit_off + alloc_bits > chunk->contig_bits)
  		return -1;

  	bit_off = chunk->first_bit;
  	bits = 0;
  	pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) {

  		if (!pop_only || pcpu_is_populated(chunk, bit_off, bits,

  						   &next_off))

  			break;

  		bit_off = next_off;

  		bits = 0;

  	}

  
  	if (bit_off == pcpu_chunk_map_bits(chunk))
  		return -1;
  
  	return bit_off;

  }
  
  /**

   * pcpu_alloc_area - allocates an area from a pcpu_chunk

   * @chunk: chunk of interest

   * @alloc_bits: size of request in allocation units
   * @align: alignment of area (max PAGE_SIZE)
   * @start: bit_off to start searching

   *

   * This function takes in a @start offset to begin searching to fit an

   * allocation of @alloc_bits with alignment @align.  It needs to scan
   * the allocation map because if it fits within the block's contig hint,
   * @start will be block->first_free. This is an attempt to fill the
   * allocation prior to breaking the contig hint.  The allocation and
   * boundary maps are updated accordingly if it confirms a valid
   * free area.

   *

   * RETURNS:

   * Allocated addr offset in @chunk on success.
   * -1 if no matching area is found.

   */

  static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits,
  			   size_t align, int start)

  {

  	size_t align_mask = (align) ? (align - 1) : 0;
  	int bit_off, end, oslot;

  	lockdep_assert_held(&pcpu_lock);

  	oslot = pcpu_chunk_slot(chunk);

  	/*
  	 * Search to find a fit.
  	 */

  	end = start + alloc_bits + PCPU_BITMAP_BLOCK_BITS;

  	bit_off = bitmap_find_next_zero_area(chunk->alloc_map, end, start,
  					     alloc_bits, align_mask);
  	if (bit_off >= end)
  		return -1;

  	/* update alloc map */
  	bitmap_set(chunk->alloc_map, bit_off, alloc_bits);

  	/* update boundary map */
  	set_bit(bit_off, chunk->bound_map);
  	bitmap_clear(chunk->bound_map, bit_off + 1, alloc_bits - 1);
  	set_bit(bit_off + alloc_bits, chunk->bound_map);

  	chunk->free_bytes -= alloc_bits * PCPU_MIN_ALLOC_SIZE;

  	/* update first free bit */
  	if (bit_off == chunk->first_bit)
  		chunk->first_bit = find_next_zero_bit(
  					chunk->alloc_map,
  					pcpu_chunk_map_bits(chunk),
  					bit_off + alloc_bits);

  	pcpu_block_update_hint_alloc(chunk, bit_off, alloc_bits);

  	pcpu_chunk_relocate(chunk, oslot);

  	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.

   */

  static void pcpu_free_area(struct pcpu_chunk *chunk, int off)

  {

  	int bit_off, bits, end, oslot;

  	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_chunk_map_bits(chunk),
  			    bit_off + 1);
  	bits = end - bit_off;
  	bitmap_clear(chunk->alloc_map, bit_off, bits);

  	/* update metadata */
  	chunk->free_bytes += bits * PCPU_MIN_ALLOC_SIZE;

  	/* update first free bit */
  	chunk->first_bit = min(chunk->first_bit, bit_off);

  	pcpu_block_update_hint_free(chunk, bit_off, bits);

  	pcpu_chunk_relocate(chunk, oslot);
  }

  static void pcpu_init_md_blocks(struct pcpu_chunk *chunk)
  {
  	struct pcpu_block_md *md_block;
  
  	for (md_block = chunk->md_blocks;
  	     md_block != chunk->md_blocks + pcpu_chunk_nr_blocks(chunk);
  	     md_block++) {
  		md_block->contig_hint = PCPU_BITMAP_BLOCK_BITS;
  		md_block->left_free = PCPU_BITMAP_BLOCK_BITS;
  		md_block->right_free = PCPU_BITMAP_BLOCK_BITS;
  	}
  }

  /**
   * pcpu_alloc_first_chunk - creates chunks that serve the first chunk
   * @tmp_addr: the start of the region served
   * @map_size: size of the region served
   *
   * This is responsible for creating the chunks that serve the first chunk.  The
   * base_addr is page aligned down of @tmp_addr while the region end is page
   * aligned up.  Offsets are kept track of to determine the region served. All
   * this is done to appease the bitmap allocator in avoiding partial blocks.
   *
   * RETURNS:
   * Chunk serving the region at @tmp_addr of @map_size.
   */

  static struct pcpu_chunk * __init pcpu_alloc_first_chunk(unsigned long tmp_addr,

  							 int map_size)

  {
  	struct pcpu_chunk *chunk;

  	unsigned long aligned_addr, lcm_align;

  	int start_offset, offset_bits, region_size, region_bits;

  
  	/* region calculations */
  	aligned_addr = tmp_addr & PAGE_MASK;
  
  	start_offset = tmp_addr - aligned_addr;

  	/*
  	 * Align the end of the region with the LCM of PAGE_SIZE and
  	 * PCPU_BITMAP_BLOCK_SIZE.  One of these constants is a multiple of
  	 * the other.
  	 */
  	lcm_align = lcm(PAGE_SIZE, PCPU_BITMAP_BLOCK_SIZE);
  	region_size = ALIGN(start_offset + map_size, lcm_align);

  	/* allocate chunk */

  	chunk = memblock_virt_alloc(sizeof(struct pcpu_chunk) +
  				    BITS_TO_LONGS(region_size >> PAGE_SHIFT),
  				    0);

  	INIT_LIST_HEAD(&chunk->list);

  
  	chunk->base_addr = (void *)aligned_addr;

  	chunk->start_offset = start_offset;

  	chunk->end_offset = region_size - chunk->start_offset - map_size;

  	chunk->nr_pages = region_size >> PAGE_SHIFT;

  	region_bits = pcpu_chunk_map_bits(chunk);

  	chunk->alloc_map = memblock_virt_alloc(BITS_TO_LONGS(region_bits) *
  					       sizeof(chunk->alloc_map[0]), 0);
  	chunk->bound_map = memblock_virt_alloc(BITS_TO_LONGS(region_bits + 1) *
  					       sizeof(chunk->bound_map[0]), 0);
  	chunk->md_blocks = memblock_virt_alloc(pcpu_chunk_nr_blocks(chunk) *
  					       sizeof(chunk->md_blocks[0]), 0);
  	pcpu_init_md_blocks(chunk);

  
  	/* manage populated page bitmap */
  	chunk->immutable = true;

  	bitmap_fill(chunk->populated, chunk->nr_pages);
  	chunk->nr_populated = chunk->nr_pages;

  	chunk->nr_empty_pop_pages =
  		pcpu_cnt_pop_pages(chunk, start_offset / PCPU_MIN_ALLOC_SIZE,
  				   map_size / PCPU_MIN_ALLOC_SIZE);

  	chunk->contig_bits = map_size / PCPU_MIN_ALLOC_SIZE;
  	chunk->free_bytes = map_size;

  
  	if (chunk->start_offset) {
  		/* hide the beginning of the bitmap */

  		offset_bits = chunk->start_offset / PCPU_MIN_ALLOC_SIZE;
  		bitmap_set(chunk->alloc_map, 0, offset_bits);
  		set_bit(0, chunk->bound_map);
  		set_bit(offset_bits, chunk->bound_map);

  		chunk->first_bit = offset_bits;

  		pcpu_block_update_hint_alloc(chunk, 0, offset_bits);

  	}

  	if (chunk->end_offset) {
  		/* hide the end of the bitmap */

  		offset_bits = chunk->end_offset / PCPU_MIN_ALLOC_SIZE;
  		bitmap_set(chunk->alloc_map,
  			   pcpu_chunk_map_bits(chunk) - offset_bits,
  			   offset_bits);
  		set_bit((start_offset + map_size) / PCPU_MIN_ALLOC_SIZE,
  			chunk->bound_map);
  		set_bit(region_bits, chunk->bound_map);

  		pcpu_block_update_hint_alloc(chunk, pcpu_chunk_map_bits(chunk)
  					     - offset_bits, offset_bits);
  	}

  	return chunk;
  }

  static struct pcpu_chunk *pcpu_alloc_chunk(gfp_t gfp)

  {
  	struct pcpu_chunk *chunk;

  	int region_bits;

  	chunk = pcpu_mem_zalloc(pcpu_chunk_struct_size, gfp);

  	if (!chunk)
  		return NULL;

  	INIT_LIST_HEAD(&chunk->list);
  	chunk->nr_pages = pcpu_unit_pages;
  	region_bits = pcpu_chunk_map_bits(chunk);

  	chunk->alloc_map = pcpu_mem_zalloc(BITS_TO_LONGS(region_bits) *

  					   sizeof(chunk->alloc_map[0]), gfp);

  	if (!chunk->alloc_map)
  		goto alloc_map_fail;

  	chunk->bound_map = pcpu_mem_zalloc(BITS_TO_LONGS(region_bits + 1) *

  					   sizeof(chunk->bound_map[0]), gfp);

  	if (!chunk->bound_map)
  		goto bound_map_fail;

  	chunk->md_blocks = pcpu_mem_zalloc(pcpu_chunk_nr_blocks(chunk) *

  					   sizeof(chunk->md_blocks[0]), gfp);

  	if (!chunk->md_blocks)
  		goto md_blocks_fail;
  
  	pcpu_init_md_blocks(chunk);

  	/* init metadata */
  	chunk->contig_bits = region_bits;
  	chunk->free_bytes = chunk->nr_pages * PAGE_SIZE;

  	return chunk;

  md_blocks_fail:
  	pcpu_mem_free(chunk->bound_map);

  bound_map_fail:
  	pcpu_mem_free(chunk->alloc_map);
  alloc_map_fail:
  	pcpu_mem_free(chunk);
  
  	return NULL;

  }
  
  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);

  }

  /**
   * pcpu_chunk_populated - post-population bookkeeping
   * @chunk: pcpu_chunk which got populated
   * @page_start: the start page
   * @page_end: the end page

   * @for_alloc: if this is to populate for allocation

   *
   * Pages in [@page_start,@page_end) have been populated to @chunk.  Update
   * the bookkeeping information accordingly.  Must be called after each
   * successful population.

   *
   * If this is @for_alloc, do not increment pcpu_nr_empty_pop_pages because it
   * is to serve an allocation in that area.

   */

  static void pcpu_chunk_populated(struct pcpu_chunk *chunk, int page_start,
  				 int page_end, bool for_alloc)

  {
  	int nr = page_end - page_start;
  
  	lockdep_assert_held(&pcpu_lock);
  
  	bitmap_set(chunk->populated, page_start, nr);
  	chunk->nr_populated += nr;

  
  	if (!for_alloc) {
  		chunk->nr_empty_pop_pages += nr;
  		pcpu_nr_empty_pop_pages += nr;
  	}

  }
  
  /**
   * pcpu_chunk_depopulated - post-depopulation bookkeeping
   * @chunk: pcpu_chunk which got depopulated
   * @page_start: the start page
   * @page_end: the end page
   *
   * Pages in [@page_start,@page_end) have been depopulated from @chunk.
   * Update the bookkeeping information accordingly.  Must be called after
   * each successful depopulation.
   */
  static void pcpu_chunk_depopulated(struct pcpu_chunk *chunk,
  				   int page_start, int page_end)
  {
  	int nr = page_end - page_start;
  
  	lockdep_assert_held(&pcpu_lock);
  
  	bitmap_clear(chunk->populated, page_start, nr);
  	chunk->nr_populated -= nr;

  	chunk->nr_empty_pop_pages -= nr;

  	pcpu_nr_empty_pop_pages -= nr;
  }

  /*
   * Chunk management implementation.
   *
   * To allow different implementations, chunk alloc/free and
   * [de]population are implemented in a separate file which is pulled
   * into this file and compiled together.  The following functions
   * should be implemented.
   *
   * pcpu_populate_chunk		- populate the specified range of a chunk
   * pcpu_depopulate_chunk	- depopulate the specified range of a chunk
   * pcpu_create_chunk		- create a new chunk
   * pcpu_destroy_chunk		- destroy a chunk, always preceded by full depop
   * pcpu_addr_to_page		- translate address to physical address
   * pcpu_verify_alloc_info	- check alloc_info is acceptable during init

   */

  static int pcpu_populate_chunk(struct pcpu_chunk *chunk, int off, int size,
  			       gfp_t gfp);

  static void pcpu_depopulate_chunk(struct pcpu_chunk *chunk, int off, int size);

  static struct pcpu_chunk *pcpu_create_chunk(gfp_t gfp);

  static void pcpu_destroy_chunk(struct pcpu_chunk *chunk);
  static struct page *pcpu_addr_to_page(void *addr);
  static int __init pcpu_verify_alloc_info(const struct pcpu_alloc_info *ai);

  #ifdef CONFIG_NEED_PER_CPU_KM
  #include "percpu-km.c"
  #else

  #include "percpu-vm.c"

  #endif

  
  /**

   * 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 dynamic region (first chunk)? */

  	if (pcpu_addr_in_chunk(pcpu_first_chunk, addr))

  		return pcpu_first_chunk;

  
  	/* is it in the reserved region? */

  	if (pcpu_addr_in_chunk(pcpu_reserved_chunk, addr))

  		return pcpu_reserved_chunk;

  
  	/*
  	 * The address is relative to unit0 which might be unused and
  	 * thus unmapped.  Offset the address to the unit space of the
  	 * current processor before looking it up in the vmalloc
  	 * space.  Note that any possible cpu id can be used here, so
  	 * there's no need to worry about preemption or cpu hotplug.
  	 */
  	addr += pcpu_unit_offsets[raw_smp_processor_id()];

  	return pcpu_get_page_chunk(pcpu_addr_to_page(addr));

  }
  
  /**

   * pcpu_alloc - the percpu allocator

   * @size: size of area to allocate in bytes

   * @align: alignment of area (max PAGE_SIZE)

   * @reserved: allocate from the reserved chunk if available

   * @gfp: allocation flags

   *

   * Allocate percpu area of @size bytes aligned at @align.  If @gfp doesn't

   * contain %GFP_KERNEL, the allocation is atomic. If @gfp has __GFP_NOWARN
   * then no warning will be triggered on invalid or failed allocation
   * requests.

   *
   * RETURNS:
   * Percpu pointer to the allocated area on success, NULL on failure.
   */

  static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved,
  				 gfp_t gfp)

  {

  	bool is_atomic = (gfp & GFP_KERNEL) != GFP_KERNEL;
  	bool do_warn = !(gfp & __GFP_NOWARN);

  	static int warn_limit = 10;

  	struct pcpu_chunk *chunk;

  	const char *err;

  	int slot, off, cpu, ret;

  	unsigned long flags;

  	void __percpu *ptr;

  	size_t bits, bit_align;

  	/*

  	 * There is now a minimum allocation size of PCPU_MIN_ALLOC_SIZE,
  	 * therefore alignment must be a minimum of that many bytes.
  	 * An allocation may have internal fragmentation from rounding up
  	 * of 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);

  	bits = size >> PCPU_MIN_ALLOC_SHIFT;
  	bit_align = align >> PCPU_MIN_ALLOC_SHIFT;

  	if (unlikely(!size || size > PCPU_MIN_UNIT_SIZE || align > PAGE_SIZE ||
  		     !is_power_of_2(align))) {

  		WARN(do_warn, "illegal size (%zu) or align (%zu) for percpu allocation
  ",

  		     size, align);

  		return NULL;
  	}

  	if (!is_atomic)
  		mutex_lock(&pcpu_alloc_mutex);

  	spin_lock_irqsave(&pcpu_lock, flags);

  	/* serve reserved allocations from the reserved chunk if available */
  	if (reserved && pcpu_reserved_chunk) {
  		chunk = pcpu_reserved_chunk;

  		off = pcpu_find_block_fit(chunk, bits, bit_align, is_atomic);
  		if (off < 0) {

  			err = "alloc from reserved chunk failed";

  			goto fail_unlock;

  		}

  		off = pcpu_alloc_area(chunk, bits, bit_align, off);

  		if (off >= 0)
  			goto area_found;

  		err = "alloc from reserved chunk failed";

  		goto fail_unlock;

  	}

  restart:

  	/* search through normal chunks */

  	for (slot = pcpu_size_to_slot(size); slot < pcpu_nr_slots; slot++) {
  		list_for_each_entry(chunk, &pcpu_slot[slot], list) {

  			off = pcpu_find_block_fit(chunk, bits, bit_align,
  						  is_atomic);
  			if (off < 0)

  				continue;

  			off = pcpu_alloc_area(chunk, bits, bit_align, off);

  			if (off >= 0)
  				goto area_found;

  		}
  	}

  	spin_unlock_irqrestore(&pcpu_lock, flags);

  	/*
  	 * No space left.  Create a new chunk.  We don't want multiple
  	 * tasks to create chunks simultaneously.  Serialize and create iff
  	 * there's still no empty chunk after grabbing the mutex.
  	 */

  	if (is_atomic) {
  		err = "atomic alloc failed, no space left";

  		goto fail;

  	}

  	if (list_empty(&pcpu_slot[pcpu_nr_slots - 1])) {

  		chunk = pcpu_create_chunk(0);

  		if (!chunk) {
  			err = "failed to allocate new chunk";
  			goto fail;
  		}
  
  		spin_lock_irqsave(&pcpu_lock, flags);
  		pcpu_chunk_relocate(chunk, -1);
  	} else {
  		spin_lock_irqsave(&pcpu_lock, flags);

  	}

  	goto restart;

  
  area_found:

  	pcpu_stats_area_alloc(chunk, size);

  	spin_unlock_irqrestore(&pcpu_lock, flags);

  	/* populate if not all pages are already there */

  	if (!is_atomic) {

  		int page_start, page_end, rs, re;

  		page_start = PFN_DOWN(off);
  		page_end = PFN_UP(off + size);

  		pcpu_for_each_unpop_region(chunk->populated, rs, re,
  					   page_start, page_end) {

  			WARN_ON(chunk->immutable);

  			ret = pcpu_populate_chunk(chunk, rs, re, 0);

  
  			spin_lock_irqsave(&pcpu_lock, flags);
  			if (ret) {

  				pcpu_free_area(chunk, off);

  				err = "failed to populate";
  				goto fail_unlock;
  			}

  			pcpu_chunk_populated(chunk, rs, re, true);

  			spin_unlock_irqrestore(&pcpu_lock, flags);

  		}

  		mutex_unlock(&pcpu_alloc_mutex);
  	}

  	if (pcpu_nr_empty_pop_pages < PCPU_EMPTY_POP_PAGES_LOW)
  		pcpu_schedule_balance_work();

  	/* clear the areas and return address relative to base address */
  	for_each_possible_cpu(cpu)
  		memset((void *)pcpu_chunk_addr(chunk, cpu, 0) + off, 0, size);

  	ptr = __addr_to_pcpu_ptr(chunk->base_addr + off);

  	kmemleak_alloc_percpu(ptr, size, gfp);

  
  	trace_percpu_alloc_percpu(reserved, is_atomic, size, align,
  			chunk->base_addr, off, ptr);

  	return ptr;

  
  fail_unlock:

  	spin_unlock_irqrestore(&pcpu_lock, flags);

  fail:

  	trace_percpu_alloc_percpu_fail(reserved, is_atomic, size, align);

  	if (!is_atomic && do_warn && warn_limit) {

  		pr_warn("allocation failed, size=%zu align=%zu atomic=%d, %s
  ",

  			size, align, is_atomic, err);

  		dump_stack();
  		if (!--warn_limit)

  			pr_info("limit reached, disable warning
  ");

  	}

  	if (is_atomic) {
  		/* see the flag handling in pcpu_blance_workfn() */
  		pcpu_atomic_alloc_failed = true;
  		pcpu_schedule_balance_work();

  	} else {
  		mutex_unlock(&pcpu_alloc_mutex);

  	}

  	return NULL;

  }

  
  /**

   * __alloc_percpu_gfp - allocate dynamic percpu area

   * @size: size of area to allocate in bytes
   * @align: alignment of area (max PAGE_SIZE)

   * @gfp: allocation flags

   *

   * Allocate zero-filled percpu area of @size bytes aligned at @align.  If
   * @gfp doesn't contain %GFP_KERNEL, the allocation doesn't block and can

   * be called from any context but is a lot more likely to fail. If @gfp
   * has __GFP_NOWARN then no warning will be triggered on invalid or failed
   * allocation requests.

   *

   * RETURNS:
   * Percpu pointer to the allocated area on success, NULL on failure.
   */

  void __percpu *__alloc_percpu_gfp(size_t size, size_t align, gfp_t gfp)
  {
  	return pcpu_alloc(size, align, false, gfp);
  }
  EXPORT_SYMBOL_GPL(__alloc_percpu_gfp);
  
  /**
   * __alloc_percpu - allocate dynamic percpu area
   * @size: size of area to allocate in bytes
   * @align: alignment of area (max PAGE_SIZE)
   *
   * Equivalent to __alloc_percpu_gfp(size, align, %GFP_KERNEL).
   */

  void __percpu *__alloc_percpu(size_t size, size_t align)

  {

  	return pcpu_alloc(size, align, false, GFP_KERNEL);

  }

  EXPORT_SYMBOL_GPL(__alloc_percpu);

  /**
   * __alloc_reserved_percpu - allocate reserved percpu area
   * @size: size of area to allocate in bytes
   * @align: alignment of area (max PAGE_SIZE)
   *

   * Allocate zero-filled percpu area of @size bytes aligned at @align
   * from reserved percpu area if arch has set it up; otherwise,
   * allocation is served from the same dynamic area.  Might sleep.
   * Might trigger writeouts.

   *

   * CONTEXT:
   * Does GFP_KERNEL allocation.
   *

   * RETURNS:
   * Percpu pointer to the allocated area on success, NULL on failure.
   */

  void __percpu *__alloc_reserved_percpu(size_t size, size_t align)

  {

  	return pcpu_alloc(size, align, true, GFP_KERNEL);

  }

  /**

   * pcpu_balance_workfn - manage the amount of free chunks and populated pages

   * @work: unused
   *

   * Reclaim all fully free chunks except for the first one.  This is also
   * responsible for maintaining the pool of empty populated pages.  However,
   * it is possible that this is called when physical memory is scarce causing
   * OOM killer to be triggered.  We should avoid doing so until an actual
   * allocation causes the failure as it is possible that requests can be
   * serviced from already backed regions.

   */

  static void pcpu_balance_workfn(struct work_struct *work)

  {

  	/* gfp flags passed to underlying allocators */
  	const gfp_t gfp = __GFP_NORETRY | __GFP_NOWARN;

  	LIST_HEAD(to_free);
  	struct list_head *free_head = &pcpu_slot[pcpu_nr_slots - 1];

  	struct pcpu_chunk *chunk, *next;

  	int slot, nr_to_pop, ret;

  	/*
  	 * There's no reason to keep around multiple unused chunks and VM
  	 * areas can be scarce.  Destroy all free chunks except for one.
  	 */

  	mutex_lock(&pcpu_alloc_mutex);
  	spin_lock_irq(&pcpu_lock);

  	list_for_each_entry_safe(chunk, next, free_head, list) {

  		WARN_ON(chunk->immutable);
  
  		/* spare the first one */

  		if (chunk == list_first_entry(free_head, struct pcpu_chunk, list))

  			continue;

  		list_move(&chunk->list, &to_free);

  	}

  	spin_unlock_irq(&pcpu_lock);

  	list_for_each_entry_safe(chunk, next, &to_free, list) {

  		int rs, re;

  		pcpu_for_each_pop_region(chunk->populated, rs, re, 0,
  					 chunk->nr_pages) {

  			pcpu_depopulate_chunk(chunk, rs, re);

  			spin_lock_irq(&pcpu_lock);
  			pcpu_chunk_depopulated(chunk, rs, re);
  			spin_unlock_irq(&pcpu_lock);

  		}

  		pcpu_destroy_chunk(chunk);

  	}

  	/*
  	 * Ensure there are certain number of free populated pages for
  	 * atomic allocs.  Fill up from the most packed so that atomic
  	 * allocs don't increase fragmentation.  If atomic allocation
  	 * failed previously, always populate the maximum amount.  This
  	 * should prevent atomic allocs larger than PAGE_SIZE from keeping
  	 * failing indefinitely; however, large atomic allocs are not
  	 * something we support properly and can be highly unreliable and
  	 * inefficient.
  	 */
  retry_pop:
  	if (pcpu_atomic_alloc_failed) {
  		nr_to_pop = PCPU_EMPTY_POP_PAGES_HIGH;
  		/* best effort anyway, don't worry about synchronization */
  		pcpu_atomic_alloc_failed = false;
  	} else {
  		nr_to_pop = clamp(PCPU_EMPTY_POP_PAGES_HIGH -
  				  pcpu_nr_empty_pop_pages,
  				  0, PCPU_EMPTY_POP_PAGES_HIGH);
  	}
  
  	for (slot = pcpu_size_to_slot(PAGE_SIZE); slot < pcpu_nr_slots; slot++) {
  		int nr_unpop = 0, rs, re;
  
  		if (!nr_to_pop)
  			break;
  
  		spin_lock_irq(&pcpu_lock);
  		list_for_each_entry(chunk, &pcpu_slot[slot], list) {

  			nr_unpop = chunk->nr_pages - chunk->nr_populated;

  			if (nr_unpop)
  				break;
  		}
  		spin_unlock_irq(&pcpu_lock);
  
  		if (!nr_unpop)
  			continue;
  
  		/* @chunk can't go away while pcpu_alloc_mutex is held */

  		pcpu_for_each_unpop_region(chunk->populated, rs, re, 0,
  					   chunk->nr_pages) {

  			int nr = min(re - rs, nr_to_pop);

  			ret = pcpu_populate_chunk(chunk, rs, rs + nr, gfp);

  			if (!ret) {
  				nr_to_pop -= nr;
  				spin_lock_irq(&pcpu_lock);

  				pcpu_chunk_populated(chunk, rs, rs + nr, false);

  				spin_unlock_irq(&pcpu_lock);
  			} else {
  				nr_to_pop = 0;
  			}
  
  			if (!nr_to_pop)
  				break;
  		}
  	}
  
  	if (nr_to_pop) {
  		/* ran out of chunks to populate, create a new one and retry */

  		chunk = pcpu_create_chunk(gfp);

  		if (chunk) {
  			spin_lock_irq(&pcpu_lock);
  			pcpu_chunk_relocate(chunk, -1);
  			spin_unlock_irq(&pcpu_lock);
  			goto retry_pop;
  		}
  	}

  	mutex_unlock(&pcpu_alloc_mutex);

  }
  
  /**
   * free_percpu - free percpu area
   * @ptr: pointer to area to free
   *

   * Free percpu area @ptr.
   *
   * CONTEXT:
   * Can be called from atomic context.

   */

  void free_percpu(void __percpu *ptr)

  {

  	void *addr;

  	struct pcpu_chunk *chunk;

  	unsigned long flags;

  	int off;

  
  	if (!ptr)
  		return;

  	kmemleak_free_percpu(ptr);

  	addr = __pcpu_ptr_to_addr(ptr);

  	spin_lock_irqsave(&pcpu_lock, flags);

  
  	chunk = pcpu_chunk_addr_search(addr);

  	off = addr - chunk->base_addr;

  	pcpu_free_area(chunk, off);

  	/* if there are more than one fully free chunks, wake up grim reaper */

  	if (chunk->free_bytes == pcpu_unit_size) {

  		struct pcpu_chunk *pos;

  		list_for_each_entry(pos, &pcpu_slot[pcpu_nr_slots - 1], list)

  			if (pos != chunk) {

  				pcpu_schedule_balance_work();

  				break;
  			}
  	}

  	trace_percpu_free_percpu(chunk->base_addr, off, ptr);

  	spin_unlock_irqrestore(&pcpu_lock, flags);