On Friday, July 18, 2014 01:57:18 PM Joerg Roedel wrote:
> From: Joerg Roedel <jroe...@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 <jroe...@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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
