Merge tag 'pm+acpi-3.17-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/rafael/linux-pm

Pull ACPI and power management updates from Rafael Wysocki:
 "Again, ACPICA leads the pack (47 commits), followed by cpufreq (18
  commits) and system suspend/hibernation (9 commits).

  From the new code perspective, the ACPICA update brings ACPI 5.1 to
  the table, including a new device configuration object called _DSD
  (Device Specific Data) that will hopefully help us to operate device
  properties like Device Trees do (at least to some extent) and changes
  related to supporting ACPI on ARM.

  Apart from that we have hibernation changes making it use radix trees
  to store memory bitmaps which should speed up some operations carried
  out by it quite significantly.  We also have some power management
  changes related to suspend-to-idle (the "freeze" sleep state) support
  and more preliminary changes needed to support ACPI on ARM (outside of
  ACPICA).

  The rest is fixes and cleanups pretty much everywhere.

  Specifics:

   - ACPICA update to upstream version 20140724.  That includes ACPI 5.1
     material (support for the _CCA and _DSD predefined names, changes
     related to the DMAR and PCCT tables and ARM support among other
     things) and cleanups related to using ACPICA's header files.  A
     major part of it is related to acpidump and the core code used by
     that utility.  Changes from Bob Moore, David E Box, Lv Zheng,
     Sascha Wildner, Tomasz Nowicki, Hanjun Guo.

   - Radix trees for memory bitmaps used by the hibernation core from
     Joerg Roedel.

   - Support for waking up the system from suspend-to-idle (also known
     as the "freeze" sleep state) using ACPI-based PCI wakeup signaling
     (Rafael J Wysocki).

   - Fixes for issues related to ACPI button events (Rafael J Wysocki).

   - New device ID for an ACPI-enumerated device included into the
     Wildcat Point PCH from Jie Yang.

   - ACPI video updates related to backlight handling from Hans de Goede
     and Linus Torvalds.

   - Preliminary changes needed to support ACPI on ARM from Hanjun Guo
     and Graeme Gregory.

   - ACPI PNP core cleanups from Arjun Sreedharan and Zhang Rui.

   - Cleanups related to ACPI_COMPANION() and ACPI_HANDLE() macros
     (Rafael J Wysocki).

   - ACPI-based device hotplug cleanups from Wei Yongjun and Rafael J
     Wysocki.

   - Cleanups and improvements related to system suspend from Lan
     Tianyu, Randy Dunlap and Rafael J Wysocki.

   - ACPI battery cleanup from Wei Yongjun.

   - cpufreq core fixes from Viresh Kumar.

   - Elimination of a deadband effect from the cpufreq ondemand governor
     and intel_pstate driver cleanups from Stratos Karafotis.

   - 350MHz CPU support for the powernow-k6 cpufreq driver from Mikulas
     Patocka.

   - Fix for the imx6 cpufreq driver from Anson Huang.

   - cpuidle core and governor cleanups from Daniel Lezcano, Sandeep
     Tripathy and Mohammad Merajul Islam Molla.

   - Build fix for the big_little cpuidle driver from Sachin Kamat.

   - Configuration fix for the Operation Performance Points (OPP)
     framework from Mark Brown.

   - APM cleanup from Jean Delvare.

   - cpupower utility fixes and cleanups from Peter Senna Tschudin,
     Andrey Utkin, Himangi Saraogi, Rickard Strandqvist, Thomas
     Renninger"

* tag 'pm+acpi-3.17-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/rafael/linux-pm: (118 commits)
  ACPI / LPSS: add LPSS device for Wildcat Point PCH
  ACPI / PNP: Replace faulty is_hex_digit() by isxdigit()
  ACPICA: Update version to 20140724.
  ACPICA: ACPI 5.1: Update for PCCT table changes.
  ACPICA/ARM: ACPI 5.1: Update for GTDT table changes.
  ACPICA/ARM: ACPI 5.1: Update for MADT changes.
  ACPICA/ARM: ACPI 5.1: Update for FADT changes.
  ACPICA: ACPI 5.1: Support for the _CCA predifined name.
  ACPICA: ACPI 5.1: New notify value for System Affinity Update.
  ACPICA: ACPI 5.1: Support for the _DSD predefined name.
  ACPICA: Debug object: Add current value of Timer() to debug line prefix.
  ACPICA: acpihelp: Add UUID support, restructure some existing files.
  ACPICA: Utilities: Fix local printf issue.
  ACPICA: Tables: Update for DMAR table changes.
  ACPICA: Remove some extraneous printf arguments.
  ACPICA: Update for comments/formatting. No functional changes.
  ACPICA: Disassembler: Add support for the ToUUID opererator (macro).
  ACPICA: Remove a redundant cast to acpi_size for ACPI_OFFSET() macro.
  ACPICA: Work around an ancient GCC bug.
  ACPI / processor: Make it possible to get local x2apic id via _MAT
  ...

6 files changed, 475 insertions, 218 deletions

diff --git a/kernel/power/Kconfig b/kernel/power/Kconfig
index 9a83d780facd..e4e4121fa327 100644
--- a/kernel/power/Kconfig
+++ b/kernel/power/Kconfig
@@ -253,9 +253,6 @@ config APM_EMULATION
           anything, try disabling/enabling this option (or disabling/enabling
           APM in your BIOS).
 
-config ARCH_HAS_OPP
-        bool
-
 config PM_OPP
         bool
         ---help---
diff --git a/kernel/power/main.c b/kernel/power/main.c
index 8e90f330f139..9a59d042ea84 100644
--- a/kernel/power/main.c
+++ b/kernel/power/main.c
@@ -296,8 +296,8 @@ static ssize_t state_show(struct kobject *kobj, struct kobj_attribute *attr,
         suspend_state_t i;
 
         for (i = PM_SUSPEND_MIN; i < PM_SUSPEND_MAX; i++)
-                if (pm_states[i].state)
-                        s += sprintf(s,"%s ", pm_states[i].label);
+                if (pm_states[i])
+                        s += sprintf(s,"%s ", pm_states[i]);
 
 #endif
         if (hibernation_available())
@@ -311,8 +311,7 @@ static ssize_t state_show(struct kobject *kobj, struct kobj_attribute *attr,
 static suspend_state_t decode_state(const char *buf, size_t n)
 {
 #ifdef CONFIG_SUSPEND
-        suspend_state_t state = PM_SUSPEND_MIN;
-        struct pm_sleep_state *s;
+        suspend_state_t state;
 #endif
         char *p;
         int len;
@@ -325,10 +324,12 @@ static suspend_state_t decode_state(const char *buf, size_t n)
                 return PM_SUSPEND_MAX;
 
 #ifdef CONFIG_SUSPEND
-        for (s = &pm_states[state]; state < PM_SUSPEND_MAX; s++, state++)
-                if (s->state && len == strlen(s->label)
-                    && !strncmp(buf, s->label, len))
-                        return s->state;
+        for (state = PM_SUSPEND_MIN; state < PM_SUSPEND_MAX; state++) {
+                const char *label = pm_states[state];
+
+                if (label && len == strlen(label) && !strncmp(buf, label, len))
+                        return state;
+        }
 #endif
 
         return PM_SUSPEND_ON;
@@ -446,8 +447,8 @@ static ssize_t autosleep_show(struct kobject *kobj,
 
 #ifdef CONFIG_SUSPEND
         if (state < PM_SUSPEND_MAX)
-                return sprintf(buf, "%s\n", pm_states[state].state ?
-                                        pm_states[state].label : "error");
+                return sprintf(buf, "%s\n", pm_states[state] ?
+                                        pm_states[state] : "error");
 #endif
 #ifdef CONFIG_HIBERNATION
         return sprintf(buf, "disk\n");
@@ -615,7 +616,6 @@ static struct attribute_group attr_group = {
         .attrs = g,
 };
 
-#ifdef CONFIG_PM_RUNTIME
 struct workqueue_struct *pm_wq;
 EXPORT_SYMBOL_GPL(pm_wq);
 
@@ -625,9 +625,6 @@ static int __init pm_start_workqueue(void)
 
         return pm_wq ? 0 : -ENOMEM;
 }
-#else
-static inline int pm_start_workqueue(void) { return 0; }
-#endif
 
 static int __init pm_init(void)
 {
diff --git a/kernel/power/power.h b/kernel/power/power.h
index c60f13b5270a..5d49dcac2537 100644
--- a/kernel/power/power.h
+++ b/kernel/power/power.h
@@ -178,13 +178,8 @@ extern void swsusp_show_speed(struct timeval *, struct timeval *,
                                 unsigned int, char *);
 
 #ifdef CONFIG_SUSPEND
-struct pm_sleep_state {
-        const char *label;
-        suspend_state_t state;
-};
-
 /* kernel/power/suspend.c */
-extern struct pm_sleep_state pm_states[];
+extern const char *pm_states[];
 
 extern int suspend_devices_and_enter(suspend_state_t state);
 #else /* !CONFIG_SUSPEND */
diff --git a/kernel/power/snapshot.c b/kernel/power/snapshot.c
index 1ea328aafdc9..4fc5c32422b3 100644
--- a/kernel/power/snapshot.c
+++ b/kernel/power/snapshot.c
@@ -248,33 +248,61 @@ 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 */
-        unsigned long start_pfn;        /* pfn represented by the first bit */
-        unsigned long end_pfn;  /* pfn represented by the last bit plus 1 */
-        unsigned long *data;    /* bitmap representing pages */
+/*
+ * 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;
 };
 
-static inline unsigned long bm_block_bits(struct bm_block *bb)
-{
-        return bb->end_pfn - bb->start_pfn;
-}
+/*
+ * 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 {
-        struct bm_block *block;
-        int bit;
+        struct mem_zone_bm_rtree *zone;
+        struct rtree_node *node;
+        unsigned long node_pfn;
+        int node_bit;
 };
 
 struct memory_bitmap {
-        struct list_head blocks;        /* list of bitmap blocks */
+        struct list_head zones;
         struct linked_page *p_list;     /* list of pages used to store zone
                                          * bitmap objects and bitmap block
                                          * objects
@@ -284,38 +312,178 @@ struct memory_bitmap {
 
 /* Functions that operate on memory bitmaps */
 
-static void memory_bm_position_reset(struct memory_bitmap *bm)
+#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.
+ *
+ *      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)
 {
-        bm->cur.block = list_entry(bm->blocks.next, struct bm_block, hook);
-        bm->cur.bit = 0;
-}
+        struct rtree_node *node;
 
-static void memory_bm_free(struct memory_bitmap *bm, int clear_nosave_free);
+        node = chain_alloc(ca, sizeof(struct rtree_node));
+        if (!node)
+                return NULL;
 
-/**
- *      create_bm_block_list - create a list of block bitmap objects
- *      @pages - number of pages to track
- *      @list - list to put the allocated blocks into
- *      @ca - chain allocator to be used for allocating memory
+        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 create_bm_block_list(unsigned long pages,
-                                struct list_head *list,
-                                struct chain_allocator *ca)
+static int add_rtree_block(struct mem_zone_bm_rtree *zone, gfp_t gfp_mask,
+                           int safe_needed, struct chain_allocator *ca)
 {
-        unsigned int nr_blocks = DIV_ROUND_UP(pages, BM_BITS_PER_BLOCK);
+        struct rtree_node *node, *block, **dst;
+        unsigned int levels_needed, block_nr;
+        int i;
 
-        while (nr_blocks-- > 0) {
-                struct bm_block *bb;
+        block_nr = zone->blocks;
+        levels_needed = 0;
 
-                bb = chain_alloc(ca, sizeof(struct bm_block));
-                if (!bb)
+        /* How many levels do we need for this block nr? */
+        while (block_nr) {
+                levels_needed += 1;
+                block_nr >>= BM_RTREE_LEVEL_SHIFT;
+        }
+
+        /* Make sure the rtree has enough levels */
+        for (i = zone->levels; i < levels_needed; i++) {
+                node = alloc_rtree_node(gfp_mask, safe_needed, ca,
+                                        &zone->nodes);
+                if (!node)
                         return -ENOMEM;
-                list_add(&bb->hook, list);
+
+                node->data[0] = (unsigned long)zone->rtree;
+                zone->rtree = node;
+                zone->levels += 1;
+        }
+
+        /* Allocate new block */
+        block = alloc_rtree_node(gfp_mask, safe_needed, ca, &zone->leaves);
+        if (!block)
+                return -ENOMEM;
+
+        /* Now walk the rtree to insert the block */
+        node = zone->rtree;
+        dst = &zone->rtree;
+        block_nr = zone->blocks;
+        for (i = zone->levels; i > 0; i--) {
+                int index;
+
+                if (!node) {
+                        node = alloc_rtree_node(gfp_mask, safe_needed, ca,
+                                                &zone->nodes);
+                        if (!node)
+                                return -ENOMEM;
+                        *dst = node;
+                }
+
+                index = block_nr >> ((i - 1) * BM_RTREE_LEVEL_SHIFT);
+                index &= BM_RTREE_LEVEL_MASK;
+                dst = (struct rtree_node **)&((*dst)->data[index]);
+                node = *dst;
         }
 
+        zone->blocks += 1;
+        *dst = block;
+
         return 0;
 }
 
+static void free_zone_bm_rtree(struct mem_zone_bm_rtree *zone,
+                               int clear_nosave_free);
+
+/*
+ *      create_zone_bm_rtree - create a radix tree for one zone
+ *
+ *      Allocated the mem_zone_bm_rtree structure and initializes it.
+ *      This function also allocated and builds the radix tree for the
+ *      zone.
+ */
+static struct mem_zone_bm_rtree *
+create_zone_bm_rtree(gfp_t gfp_mask, int safe_needed,
+                     struct chain_allocator *ca,
+                     unsigned long start, unsigned long end)
+{
+        struct mem_zone_bm_rtree *zone;
+        unsigned int i, nr_blocks;
+        unsigned long pages;
+
+        pages = end - start;
+        zone  = chain_alloc(ca, sizeof(struct mem_zone_bm_rtree));
+        if (!zone)
+                return NULL;
+
+        INIT_LIST_HEAD(&zone->nodes);
+        INIT_LIST_HEAD(&zone->leaves);
+        zone->start_pfn = start;
+        zone->end_pfn = end;
+        nr_blocks = DIV_ROUND_UP(pages, BM_BITS_PER_BLOCK);
+
+        for (i = 0; i < nr_blocks; i++) {
+                if (add_rtree_block(zone, gfp_mask, safe_needed, ca)) {
+                        free_zone_bm_rtree(zone, PG_UNSAFE_CLEAR);
+                        return NULL;
+                }
+        }
+
+        return zone;
+}
+
+/*
+ *      free_zone_bm_rtree - Free the memory of the radix tree
+ *
+ *      Free all node pages of the radix tree. The mem_zone_bm_rtree
+ *      structure itself is not freed here nor are the rtree_node
+ *      structs.
+ */
+static void free_zone_bm_rtree(struct mem_zone_bm_rtree *zone,
+                               int clear_nosave_free)
+{
+        struct rtree_node *node;
+
+        list_for_each_entry(node, &zone->nodes, list)
+                free_image_page(node->data, clear_nosave_free);
+
+        list_for_each_entry(node, &zone->leaves, list)
+                free_image_page(node->data, clear_nosave_free);
+}
+
+static void memory_bm_position_reset(struct memory_bitmap *bm)
+{
+        bm->cur.zone = list_entry(bm->zones.next, struct mem_zone_bm_rtree,
+                                  list);
+        bm->cur.node = list_entry(bm->cur.zone->leaves.next,
+                                  struct rtree_node, list);
+        bm->cur.node_pfn = 0;
+        bm->cur.node_bit = 0;
+}
+
+static void memory_bm_free(struct memory_bitmap *bm, int clear_nosave_free);
+
 struct mem_extent {
         struct list_head hook;
         unsigned long start;
@@ -407,40 +575,22 @@ memory_bm_create(struct memory_bitmap *bm, gfp_t gfp_mask, int safe_needed)
         int error;
 
         chain_init(&ca, gfp_mask, safe_needed);
-        INIT_LIST_HEAD(&bm->blocks);
+        INIT_LIST_HEAD(&bm->zones);
 
         error = create_mem_extents(&mem_extents, gfp_mask);
         if (error)
                 return error;
 
         list_for_each_entry(ext, &mem_extents, hook) {
-                struct bm_block *bb;
-                unsigned long pfn = ext->start;
-                unsigned long pages = ext->end - ext->start;
-
-                bb = list_entry(bm->blocks.prev, struct bm_block, hook);
+                struct mem_zone_bm_rtree *zone;
 
-                error = create_bm_block_list(pages, bm->blocks.prev, &ca);
-                if (error)
+                zone = create_zone_bm_rtree(gfp_mask, safe_needed, &ca,
+                                            ext->start, ext->end);
+                if (!zone) {
+                        error = -ENOMEM;
                         goto Error;
-
-                list_for_each_entry_continue(bb, &bm->blocks, hook) {
-                        bb->data = get_image_page(gfp_mask, safe_needed);
-                        if (!bb->data) {
-                                error = -ENOMEM;
-                                goto Error;
-                        }
-
-                        bb->start_pfn = pfn;
-                        if (pages >= BM_BITS_PER_BLOCK) {
-                                pfn += BM_BITS_PER_BLOCK;
-                                pages -= BM_BITS_PER_BLOCK;
-                        } else {
-                                /* This is executed only once in the loop */
-                                pfn += pages;
-                        }
-                        bb->end_pfn = pfn;
                 }
+                list_add_tail(&zone->list, &bm->zones);
         }
 
         bm->p_list = ca.chain;
@@ -460,51 +610,83 @@ memory_bm_create(struct memory_bitmap *bm, gfp_t gfp_mask, int safe_needed)
   */
 static void memory_bm_free(struct memory_bitmap *bm, int clear_nosave_free)
 {
-        struct bm_block *bb;
+        struct mem_zone_bm_rtree *zone;
 
-        list_for_each_entry(bb, &bm->blocks, hook)
-                if (bb->data)
-                        free_image_page(bb->data, clear_nosave_free);
+        list_for_each_entry(zone, &bm->zones, list)
+                free_zone_bm_rtree(zone, clear_nosave_free);
 
         free_list_of_pages(bm->p_list, clear_nosave_free);
 
-        INIT_LIST_HEAD(&bm->blocks);
+        INIT_LIST_HEAD(&bm->zones);
 }
 
 /**
- *      memory_bm_find_bit - find the bit in the bitmap @bm that corresponds
- *      to given pfn.  The cur_zone_bm member of @bm and the cur_block member
- *      of @bm->cur_zone_bm are updated.
+ *      memory_bm_find_bit - Find the bit for pfn in the memory
+ *                           bitmap
+ *
+ *      Find the bit in the bitmap @bm that corresponds to given pfn.
+ *      The cur.zone, cur.block and cur.node_pfn member of @bm are
+ *      updated.
+ *      It walks the radix tree to find the page which contains the bit for
+ *      pfn and returns the bit position in **addr and *bit_nr.
  */
 static int memory_bm_find_bit(struct memory_bitmap *bm, unsigned long pfn,
-                                void **addr, unsigned int *bit_nr)
+                              void **addr, unsigned int *bit_nr)
 {
-        struct bm_block *bb;
+        struct mem_zone_bm_rtree *curr, *zone;
+        struct rtree_node *node;
+        int i, block_nr;
 
+        zone = bm->cur.zone;
+
+        if (pfn >= zone->start_pfn && pfn < zone->end_pfn)
+                goto zone_found;
+
+        zone = NULL;
+
+        /* Find the right zone */
+        list_for_each_entry(curr, &bm->zones, list) {
+                if (pfn >= curr->start_pfn && pfn < curr->end_pfn) {
+                        zone = curr;
+                        break;
+                }
+        }
+
+        if (!zone)
+                return -EFAULT;
+
+zone_found:
         /*
-         * Check if the pfn corresponds to the current bitmap block and find
-         * the block where it fits if this is not the case.
+         * We have a zone. Now walk the radix tree to find the leave
+         * node for our pfn.
          */
-        bb = bm->cur.block;
-        if (pfn < bb->start_pfn)
-                list_for_each_entry_continue_reverse(bb, &bm->blocks, hook)
-                        if (pfn >= bb->start_pfn)
-                                break;
 
-        if (pfn >= bb->end_pfn)
-                list_for_each_entry_continue(bb, &bm->blocks, hook)
-                        if (pfn >= bb->start_pfn && pfn < bb->end_pfn)
-                                break;
+        node = bm->cur.node;
+        if (((pfn - zone->start_pfn) & ~BM_BLOCK_MASK) == bm->cur.node_pfn)
+                goto node_found;
 
-        if (&bb->hook == &bm->blocks)
-                return -EFAULT;
+        node      = zone->rtree;
+        block_nr  = (pfn - zone->start_pfn) >> BM_BLOCK_SHIFT;
+
+        for (i = zone->levels; i > 0; i--) {
+                int index;
+
+                index = block_nr >> ((i - 1) * BM_RTREE_LEVEL_SHIFT);
+                index &= BM_RTREE_LEVEL_MASK;
+                BUG_ON(node->data[index] == 0);
+                node = (struct rtree_node *)node->data[index];
+        }
+
+node_found:
+        /* Update last position */
+        bm->cur.zone = zone;
+        bm->cur.node = node;
+        bm->cur.node_pfn = (pfn - zone->start_pfn) & ~BM_BLOCK_MASK;
+
+        /* Set return values */
+        *addr = node->data;
+        *bit_nr = (pfn - zone->start_pfn) & BM_BLOCK_MASK;
 
-        /* The block has been found */
-        bm->cur.block = bb;
-        pfn -= bb->start_pfn;
-        bm->cur.bit = pfn + 1;
-        *bit_nr = pfn;
-        *addr = bb->data;
         return 0;
 }
 
@@ -528,6 +710,7 @@ static int mem_bm_set_bit_check(struct memory_bitmap *bm, unsigned long pfn)
         error = memory_bm_find_bit(bm, pfn, &addr, &bit);
         if (!error)
                 set_bit(bit, addr);
+
         return error;
 }
 
@@ -542,6 +725,14 @@ static void memory_bm_clear_bit(struct memory_bitmap *bm, unsigned long pfn)
         clear_bit(bit, addr);
 }
 
+static void memory_bm_clear_current(struct memory_bitmap *bm)
+{
+        int bit;
+
+        bit = max(bm->cur.node_bit - 1, 0);
+        clear_bit(bit, bm->cur.node->data);
+}
+
 static int memory_bm_test_bit(struct memory_bitmap *bm, unsigned long pfn)
 {
         void *addr;
@@ -561,38 +752,70 @@ static bool memory_bm_pfn_present(struct memory_bitmap *bm, unsigned long pfn)
         return !memory_bm_find_bit(bm, pfn, &addr, &bit);
 }
 
-/**
- *      memory_bm_next_pfn - find the pfn that corresponds to the next set bit
- *      in the bitmap @bm.  If the pfn cannot be found, BM_END_OF_MAP is
- *      returned.
+/*
+ *      rtree_next_node - Jumps to the next leave node
+ *
+ *      Sets the position to the beginning of the next node in the
+ *      memory bitmap. This is either the next node in the current
+ *      zone's radix tree or the first node in the radix tree of the
+ *      next zone.
  *
- *      It is required to run memory_bm_position_reset() before the first call to
- *      this function.
+ *      Returns true if there is a next node, false otherwise.
  */
+static bool rtree_next_node(struct memory_bitmap *bm)
+{
+        bm->cur.node = list_entry(bm->cur.node->list.next,
+                                  struct rtree_node, list);
+        if (&bm->cur.node->list != &bm->cur.zone->leaves) {
+                bm->cur.node_pfn += BM_BITS_PER_BLOCK;
+                bm->cur.node_bit  = 0;
+                touch_softlockup_watchdog();
+                return true;
+        }
+
+        /* No more nodes, goto next zone */
+        bm->cur.zone = list_entry(bm->cur.zone->list.next,
+                                  struct mem_zone_bm_rtree, list);
+        if (&bm->cur.zone->list != &bm->zones) {
+                bm->cur.node = list_entry(bm->cur.zone->leaves.next,
+                                          struct rtree_node, list);
+                bm->cur.node_pfn = 0;
+                bm->cur.node_bit = 0;
+                return true;
+        }
 
+        /* No more zones */
+        return false;
+}
+
+/**
+ *      memory_bm_rtree_next_pfn - Find the next set bit in the bitmap @bm
+ *
+ *      Starting from the last returned position this function searches
+ *      for the next set bit in the memory bitmap and returns its
+ *      number. If no more bit is set BM_END_OF_MAP is returned.
+ *
+ *      It is required to run memory_bm_position_reset() before the
+ *      first call to this function.
+ */
 static unsigned long memory_bm_next_pfn(struct memory_bitmap *bm)
 {
-        struct bm_block *bb;
+        unsigned long bits, pfn, pages;
         int bit;
 
-        bb = bm->cur.block;
         do {
-                bit = bm->cur.bit;
-                bit = find_next_bit(bb->data, bm_block_bits(bb), bit);
-                if (bit < bm_block_bits(bb))
-                        goto Return_pfn;
-
-                bb = list_entry(bb->hook.next, struct bm_block, hook);
-                bm->cur.block = bb;
-                bm->cur.bit = 0;
-        } while (&bb->hook != &bm->blocks);
+                pages     = bm->cur.zone->end_pfn - bm->cur.zone->start_pfn;
+                bits      = min(pages - bm->cur.node_pfn, BM_BITS_PER_BLOCK);
+                bit       = find_next_bit(bm->cur.node->data, bits,
+                                          bm->cur.node_bit);
+                if (bit < bits) {
+                        pfn = bm->cur.zone->start_pfn + bm->cur.node_pfn + bit;
+                        bm->cur.node_bit = bit + 1;
+                        return pfn;
+                }
+        } while (rtree_next_node(bm));
 
-        memory_bm_position_reset(bm);
         return BM_END_OF_MAP;
-
- Return_pfn:
-        bm->cur.bit = bit + 1;
-        return bb->start_pfn + bit;
 }
 
 /**
@@ -816,12 +1039,17 @@ void free_basic_memory_bitmaps(void)
 
 unsigned int snapshot_additional_pages(struct zone *zone)
 {
-        unsigned int res;
+        unsigned int rtree, nodes;
+
+        rtree = nodes = DIV_ROUND_UP(zone->spanned_pages, BM_BITS_PER_BLOCK);
+        rtree += DIV_ROUND_UP(rtree * sizeof(struct rtree_node),
+                              LINKED_PAGE_DATA_SIZE);
+        while (nodes > 1) {
+                nodes = DIV_ROUND_UP(nodes, BM_ENTRIES_PER_LEVEL);
+                rtree += nodes;
+        }
 
-        res = DIV_ROUND_UP(zone->spanned_pages, BM_BITS_PER_BLOCK);
-        res += DIV_ROUND_UP(res * sizeof(struct bm_block),
-                            LINKED_PAGE_DATA_SIZE);
-        return 2 * res;
+        return 2 * rtree;
 }
 
 #ifdef CONFIG_HIGHMEM
@@ -1094,23 +1322,35 @@ static struct memory_bitmap copy_bm;
 
 void swsusp_free(void)
 {
-        struct zone *zone;
-        unsigned long pfn, max_zone_pfn;
+        unsigned long fb_pfn, fr_pfn;
 
-        for_each_populated_zone(zone) {
-                max_zone_pfn = zone_end_pfn(zone);
-                for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
-                        if (pfn_valid(pfn)) {
-                                struct page *page = pfn_to_page(pfn);
-
-                                if (swsusp_page_is_forbidden(page) &&
-                                    swsusp_page_is_free(page)) {
-                                        swsusp_unset_page_forbidden(page);
-                                        swsusp_unset_page_free(page);
-                                        __free_page(page);
-                                }
-                        }
+        memory_bm_position_reset(forbidden_pages_map);
+        memory_bm_position_reset(free_pages_map);
+
+loop:
+        fr_pfn = memory_bm_next_pfn(free_pages_map);
+        fb_pfn = memory_bm_next_pfn(forbidden_pages_map);
+
+        /*
+         * Find the next bit set in both bitmaps. This is guaranteed to
+         * terminate when fb_pfn == fr_pfn == BM_END_OF_MAP.
+         */
+        do {
+                if (fb_pfn < fr_pfn)
+                        fb_pfn = memory_bm_next_pfn(forbidden_pages_map);
+                if (fr_pfn < fb_pfn)
+                        fr_pfn = memory_bm_next_pfn(free_pages_map);
+        } while (fb_pfn != fr_pfn);
+
+        if (fr_pfn != BM_END_OF_MAP && pfn_valid(fr_pfn)) {
+                struct page *page = pfn_to_page(fr_pfn);
+
+                memory_bm_clear_current(forbidden_pages_map);
+                memory_bm_clear_current(free_pages_map);
+                __free_page(page);
+                goto loop;
         }
+
         nr_copy_pages = 0;
         nr_meta_pages = 0;
         restore_pblist = NULL;
diff --git a/kernel/power/suspend.c b/kernel/power/suspend.c
index 4b736b4dfa96..6dadb25cb0d8 100644
--- a/kernel/power/suspend.c
+++ b/kernel/power/suspend.c
@@ -31,20 +31,11 @@
 
 #include "power.h"
 
-struct pm_sleep_state pm_states[PM_SUSPEND_MAX] = {
-        [PM_SUSPEND_FREEZE] = { .label = "freeze", .state = PM_SUSPEND_FREEZE },
-        [PM_SUSPEND_STANDBY] = { .label = "standby", },
-        [PM_SUSPEND_MEM] = { .label = "mem", },
-};
+static const char *pm_labels[] = { "mem", "standby", "freeze", };
+const char *pm_states[PM_SUSPEND_MAX];
 
 static const struct platform_suspend_ops *suspend_ops;
 static const struct platform_freeze_ops *freeze_ops;
-
-static bool need_suspend_ops(suspend_state_t state)
-{
-        return state > PM_SUSPEND_FREEZE;
-}
-
 static DECLARE_WAIT_QUEUE_HEAD(suspend_freeze_wait_head);
 static bool suspend_freeze_wake;
 
@@ -97,10 +88,7 @@ static bool relative_states;
 static int __init sleep_states_setup(char *str)
 {
         relative_states = !strncmp(str, "1", 1);
-        if (relative_states) {
-                pm_states[PM_SUSPEND_MEM].state = PM_SUSPEND_FREEZE;
-                pm_states[PM_SUSPEND_FREEZE].state = 0;
-        }
+        pm_states[PM_SUSPEND_FREEZE] = pm_labels[relative_states ? 0 : 2];
         return 1;
 }
 
@@ -113,20 +101,20 @@ __setup("relative_sleep_states=", sleep_states_setup);
 void suspend_set_ops(const struct platform_suspend_ops *ops)
 {
         suspend_state_t i;
-        int j = PM_SUSPEND_MAX - 1;
+        int j = 0;
 
         lock_system_sleep();
 
         suspend_ops = ops;
         for (i = PM_SUSPEND_MEM; i >= PM_SUSPEND_STANDBY; i--)
-                if (valid_state(i))
-                        pm_states[j--].state = i;
-                else if (!relative_states)
-                        pm_states[j--].state = 0;
+                if (valid_state(i)) {
+                        pm_states[i] = pm_labels[j++];
+                } else if (!relative_states) {
+                        pm_states[i] = NULL;
+                        j++;
+                }
 
-        pm_states[j--].state = PM_SUSPEND_FREEZE;
-        while (j >= PM_SUSPEND_MIN)
-                pm_states[j--].state = 0;
+        pm_states[PM_SUSPEND_FREEZE] = pm_labels[j];
 
         unlock_system_sleep();
 }
@@ -145,6 +133,65 @@ int suspend_valid_only_mem(suspend_state_t state)
 }
 EXPORT_SYMBOL_GPL(suspend_valid_only_mem);
 
+static bool sleep_state_supported(suspend_state_t state)
+{
+        return state == PM_SUSPEND_FREEZE || (suspend_ops && suspend_ops->enter);
+}
+
+static int platform_suspend_prepare(suspend_state_t state)
+{
+        return state != PM_SUSPEND_FREEZE && suspend_ops->prepare ?
+                suspend_ops->prepare() : 0;
+}
+
+static int platform_suspend_prepare_late(suspend_state_t state)
+{
+        return state != PM_SUSPEND_FREEZE && suspend_ops->prepare_late ?
+                suspend_ops->prepare_late() : 0;
+}
+
+static void platform_suspend_wake(suspend_state_t state)
+{
+        if (state != PM_SUSPEND_FREEZE && suspend_ops->wake)
+                suspend_ops->wake();
+}
+
+static void platform_suspend_finish(suspend_state_t state)
+{
+        if (state != PM_SUSPEND_FREEZE && suspend_ops->finish)
+                suspend_ops->finish();
+}
+
+static int platform_suspend_begin(suspend_state_t state)
+{
+        if (state == PM_SUSPEND_FREEZE && freeze_ops && freeze_ops->begin)
+                return freeze_ops->begin();
+        else if (suspend_ops->begin)
+                return suspend_ops->begin(state);
+        else
+                return 0;
+}
+
+static void platform_suspend_end(suspend_state_t state)
+{
+        if (state == PM_SUSPEND_FREEZE && freeze_ops && freeze_ops->end)
+                freeze_ops->end();
+        else if (suspend_ops->end)
+                suspend_ops->end();
+}
+
+static void platform_suspend_recover(suspend_state_t state)
+{
+        if (state != PM_SUSPEND_FREEZE && suspend_ops->recover)
+                suspend_ops->recover();
+}
+
+static bool platform_suspend_again(suspend_state_t state)
+{
+        return state != PM_SUSPEND_FREEZE && suspend_ops->suspend_again ?
+                suspend_ops->suspend_again() : false;
+}
+
 static int suspend_test(int level)
 {
 #ifdef CONFIG_PM_DEBUG
@@ -168,7 +215,7 @@ static int suspend_prepare(suspend_state_t state)
 {
         int error;
 
-        if (need_suspend_ops(state) && (!suspend_ops || !suspend_ops->enter))
+        if (!sleep_state_supported(state))
                 return -EPERM;
 
         pm_prepare_console();
@@ -214,23 +261,18 @@ static int suspend_enter(suspend_state_t state, bool *wakeup)
 {
         int error;
 
-        if (need_suspend_ops(state) && suspend_ops->prepare) {
-                error = suspend_ops->prepare();
-                if (error)
-                        goto Platform_finish;
-        }
+        error = platform_suspend_prepare(state);
+        if (error)
+                goto Platform_finish;
 
         error = dpm_suspend_end(PMSG_SUSPEND);
         if (error) {
                 printk(KERN_ERR "PM: Some devices failed to power down\n");
                 goto Platform_finish;
         }
-
-        if (need_suspend_ops(state) && suspend_ops->prepare_late) {
-                error = suspend_ops->prepare_late();
-                if (error)
-                        goto Platform_wake;
-        }
+        error = platform_suspend_prepare_late(state);
+        if (error)
+                goto Platform_wake;
 
         if (suspend_test(TEST_PLATFORM))
                 goto Platform_wake;
@@ -276,15 +318,11 @@ static int suspend_enter(suspend_state_t state, bool *wakeup)
         enable_nonboot_cpus();
 
  Platform_wake:
-        if (need_suspend_ops(state) && suspend_ops->wake)
-                suspend_ops->wake();
-
+        platform_suspend_wake(state);
         dpm_resume_start(PMSG_RESUME);
 
  Platform_finish:
-        if (need_suspend_ops(state) && suspend_ops->finish)
-                suspend_ops->finish();
-
+        platform_suspend_finish(state);
         return error;
 }
 
@@ -297,18 +335,13 @@ int suspend_devices_and_enter(suspend_state_t state)
         int error;
         bool wakeup = false;
 
-        if (need_suspend_ops(state) && !suspend_ops)
+        if (!sleep_state_supported(state))
                 return -ENOSYS;
 
-        if (need_suspend_ops(state) && suspend_ops->begin) {
-                error = suspend_ops->begin(state);
-                if (error)
-                        goto Close;
-        } else if (state == PM_SUSPEND_FREEZE && freeze_ops && freeze_ops->begin) {
-                error = freeze_ops->begin();
-                if (error)
-                        goto Close;
-        }
+        error = platform_suspend_begin(state);
+        if (error)
+                goto Close;
+
         suspend_console();
         suspend_test_start();
         error = dpm_suspend_start(PMSG_SUSPEND);
@@ -322,25 +355,20 @@ int suspend_devices_and_enter(suspend_state_t state)
 
         do {
                 error = suspend_enter(state, &wakeup);
-        } while (!error && !wakeup && need_suspend_ops(state)
-                && suspend_ops->suspend_again && suspend_ops->suspend_again());
+        } while (!error && !wakeup && platform_suspend_again(state));
 
  Resume_devices:
         suspend_test_start();
         dpm_resume_end(PMSG_RESUME);
         suspend_test_finish("resume devices");
         resume_console();
- Close:
-        if (need_suspend_ops(state) && suspend_ops->end)
-                suspend_ops->end();
-        else if (state == PM_SUSPEND_FREEZE && freeze_ops && freeze_ops->end)
-                freeze_ops->end();
 
+ Close:
+        platform_suspend_end(state);
         return error;
 
  Recover_platform:
-        if (need_suspend_ops(state) && suspend_ops->recover)
-                suspend_ops->recover();
+        platform_suspend_recover(state);
         goto Resume_devices;
 }
 
@@ -393,7 +421,7 @@ static int enter_state(suspend_state_t state)
         printk("done.\n");
         trace_suspend_resume(TPS("sync_filesystems"), 0, false);
 
-        pr_debug("PM: Preparing system for %s sleep\n", pm_states[state].label);
+        pr_debug("PM: Preparing system for %s sleep\n", pm_states[state]);
         error = suspend_prepare(state);
         if (error)
                 goto Unlock;
@@ -402,7 +430,7 @@ static int enter_state(suspend_state_t state)
                 goto Finish;
 
         trace_suspend_resume(TPS("suspend_enter"), state, false);
-        pr_debug("PM: Entering %s sleep\n", pm_states[state].label);
+        pr_debug("PM: Entering %s sleep\n", pm_states[state]);
         pm_restrict_gfp_mask();
         error = suspend_devices_and_enter(state);
         pm_restore_gfp_mask();
diff --git a/kernel/power/suspend_test.c b/kernel/power/suspend_test.c
index 269b097e78ea..2f524928b6aa 100644
--- a/kernel/power/suspend_test.c
+++ b/kernel/power/suspend_test.c
@@ -92,13 +92,13 @@ static void __init test_wakealarm(struct rtc_device *rtc, suspend_state_t state)
         }
 
         if (state == PM_SUSPEND_MEM) {
-                printk(info_test, pm_states[state].label);
+                printk(info_test, pm_states[state]);
                 status = pm_suspend(state);
                 if (status == -ENODEV)
                         state = PM_SUSPEND_STANDBY;
         }
         if (state == PM_SUSPEND_STANDBY) {
-                printk(info_test, pm_states[state].label);
+                printk(info_test, pm_states[state]);
                 status = pm_suspend(state);
         }
         if (status < 0)
@@ -141,8 +141,8 @@ static int __init setup_test_suspend(char *value)
         /* "=mem" ==> "mem" */
         value++;
         for (i = PM_SUSPEND_MIN; i < PM_SUSPEND_MAX; i++)
-                if (!strcmp(pm_states[i].label, value)) {
-                        test_state = pm_states[i].state;
+                if (!strcmp(pm_states[i], value)) {
+                        test_state = i;
                         return 0;
                 }
 
@@ -162,8 +162,8 @@ static int __init test_suspend(void)
         /* PM is initialized by now; is that state testable? */
         if (test_state == PM_SUSPEND_ON)
                 goto done;
-        if (!pm_states[test_state].state) {
-                printk(warn_bad_state, pm_states[test_state].label);
+        if (!pm_states[test_state]) {
+                printk(warn_bad_state, pm_states[test_state]);
                 goto done;
         }