Re: [PATCH 1/6] PM / Hibernate: Create a Radix-Tree to store memory bitmap

["Rafael J. Wysocki" <rjw@rjwysocki.net>]

On Friday, July 18, 2014 01:57:18 PM Joerg Roedel wrote:
> From: Joerg Roedel <jroedel@suse.de>
> 
> This patch adds the code to allocate and build the radix
> tree to store the memory bitmap. The old data structure is
> left in place until the radix tree implementation is
> finished.
> 
> Signed-off-by: Joerg Roedel <jroedel@suse.de>
> ---
>  kernel/power/snapshot.c | 224 +++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 223 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/power/snapshot.c b/kernel/power/snapshot.c
> index 1ea328a..d0f11ec 100644
> --- a/kernel/power/snapshot.c
> +++ b/kernel/power/snapshot.c
> @@ -248,11 +248,24 @@ static void *chain_alloc(struct chain_allocator *ca, unsigned int size)
>   *	information is stored (in the form of a block of bitmap)
>   *	It also contains the pfns that correspond to the start and end of
>   *	the represented memory area.
> + *
> + *	The memory bitmap is organized as a radix tree to guarantee fast random
> + *	access to the bits. There is one radix tree for each zone (as returned
> + *	from create_mem_extents).
> + *
> + *	One radix tree is represented by one struct mem_zone_bm_rtree. There are
> + *	two linked lists for the nodes of the tree, one for the inner nodes and
> + *	one for the leave nodes. The linked leave nodes are used for fast linear
> + *	access of the memory bitmap.
> + *
> + *	The struct rtree_node represents one node of the radix tree.
>   */
>  
>  #define BM_END_OF_MAP	(~0UL)
>  
>  #define BM_BITS_PER_BLOCK	(PAGE_SIZE * BITS_PER_BYTE)
> +#define BM_BLOCK_SHIFT		(PAGE_SHIFT + 3)
> +#define BM_BLOCK_MASK		((1UL << BM_BLOCK_SHIFT) - 1)
>  
>  struct bm_block {
>  	struct list_head hook;	/* hook into a list of bitmap blocks */
> @@ -266,6 +279,31 @@ static inline unsigned long bm_block_bits(struct bm_block *bb)
>  	return bb->end_pfn - bb->start_pfn;
>  }
>  
> +/*
> + * struct rtree_node is a wrapper struct to link the nodes
> + * of the rtree together for easy linear iteration over
> + * bits and easy freeing
> + */
> +struct rtree_node {
> +	struct list_head list;
> +	unsigned long *data;
> +};
> +
> +/*
> + * struct mem_zone_bm_rtree represents a bitmap used for one
> + * populated memory zone.
> + */
> +struct mem_zone_bm_rtree {
> +	struct list_head list;		/* Link Zones together         */
> +	struct list_head nodes;		/* Radix Tree inner nodes      */
> +	struct list_head leaves;	/* Radix Tree leaves           */
> +	unsigned long start_pfn;	/* Zone start page frame       */
> +	unsigned long end_pfn;		/* Zone end page frame + 1     */
> +	struct rtree_node *rtree;	/* Radix Tree Root             */
> +	int levels;			/* Number of Radix Tree Levels */
> +	unsigned int blocks;		/* Number of Bitmap Blocks     */
> +};
> +
>  /* strcut bm_position is used for browsing memory bitmaps */
>  
>  struct bm_position {
> @@ -274,6 +312,7 @@ struct bm_position {
>  };
>  
>  struct memory_bitmap {
> +	struct list_head zones;
>  	struct list_head blocks;	/* list of bitmap blocks */
>  	struct linked_page *p_list;	/* list of pages used to store zone
>  					 * bitmap objects and bitmap block
> @@ -284,6 +323,167 @@ struct memory_bitmap {
>  
>  /* Functions that operate on memory bitmaps */
>  
> +#define BM_ENTRIES_PER_LEVEL	(PAGE_SIZE / sizeof(unsigned long))
> +#if BITS_PER_LONG == 32
> +#define BM_RTREE_LEVEL_SHIFT	(PAGE_SHIFT - 2)
> +#else
> +#define BM_RTREE_LEVEL_SHIFT	(PAGE_SHIFT - 3)
> +#endif
> +#define BM_RTREE_LEVEL_MASK	((1UL << BM_RTREE_LEVEL_SHIFT) - 1)
> +
> +/*
> + *	alloc_rtree_node - Allocate a new node and add it to the radix
> + *			   tree.

Please make this a single line.

> + *
> + *	This function is used to allocate inner nodes as well as the
> + *	leave nodes of the radix tree. It also adds the node to the
> + *	corresponding linked list passed in by the *list parameter.
> + */
> +static struct rtree_node *alloc_rtree_node(gfp_t gfp_mask, int safe_needed,
> +					   struct chain_allocator *ca,
> +					   struct list_head *list)
> +{
> +	struct rtree_node *node;
> +
> +	node = chain_alloc(ca, sizeof(struct rtree_node));
> +	if (!node)
> +		return NULL;
> +
> +	node->data = get_image_page(gfp_mask, safe_needed);
> +	if (!node->data)
> +		return NULL;
> +
> +	list_add_tail(&node->list, list);
> +
> +	return node;
> +}
> +
> +/*
> + *	add_rtree_block - Add a new leave node to the radix tree
> + *
> + *	The leave nodes need to be allocated in order to keep the leaves
> + *	linked list in order. This is guaranteed by the zone->blocks
> + *	counter.
> + */
> +static int add_rtree_block(struct mem_zone_bm_rtree *zone, gfp_t gfp_mask,
> +			   int safe_needed, struct chain_allocator *ca)
> +{
> +	struct rtree_node *node, *block, **dst;
> +	unsigned int levels_needed, block_nr;
> +	int i;
> +
> +	block_nr	= zone->blocks;

This isn't proper kernel coding style.  Please use spaces as separators
before the "=" here and elsewhere.

Rafael