diff --git a/xen/common/page_alloc.c b/xen/common/page_alloc.c
index 5cc489a..1c23991 100644
--- a/xen/common/page_alloc.c
+++ b/xen/common/page_alloc.c
@@ -1000,7 +1000,8 @@ static bool_t can_merge(struct page_info *buddy, unsigned int node,
 
 /* Returns new buddy head. */
 static struct page_info *merge_chunks(struct page_info *pg, unsigned int node,
-                                      unsigned int zone, unsigned int order)
+                                      unsigned int zone, unsigned int order,
+                                      bool_t is_frag)
 {
     bool_t need_scrub = !!test_bit(_PGC_need_scrub, &pg->count_info);
 
@@ -1025,9 +1026,12 @@ static struct page_info *merge_chunks(struct page_info *pg, unsigned int node,
         }
         else
         {
-            /* Merge with successor block? */
+            /*
+             * Merge with successor block?
+             * Only un-fragmented buddy can be merged forward.
+             */
             buddy = pg + mask;
-            if ( !can_merge(buddy, node, order, need_scrub) )
+            if ( is_frag || !can_merge(buddy, node, order, need_scrub) )
                 break;
 
             buddy->count_info &= ~PGC_need_scrub;
@@ -1069,10 +1073,13 @@ static unsigned int node_to_scrub(bool_t get_node)
     }
 }
 
+#define SCRUB_CHUNK_ORDER  8
 bool_t scrub_free_pages()
 {
     struct page_info *pg;
     unsigned int i, zone;
+    unsigned int num_scrubbed, scrub_order, start, end;
+    bool_t preempt, is_frag;
     int order, cpu = smp_processor_id();
     nodeid_t node;
 
@@ -1093,19 +1100,64 @@ bool_t scrub_free_pages()
                 if ( !test_bit(_PGC_need_scrub, &pg->count_info) )
                     break;
 
-                for ( i = 0; i < (1UL << order); i++)
+                page_list_del(pg, &heap(node, zone, order));
+
+                scrub_order = MIN(order, SCRUB_CHUNK_ORDER);
+                num_scrubbed = 0;
+                is_frag = false;
+                while ( num_scrubbed < (1 << order) )
                 {
-                    scrub_one_page(&pg[i]);
+                    for ( i = 0; i < (1 << scrub_order); i++ )
+                        scrub_one_page(&pg[num_scrubbed + i]);
+
+                    num_scrubbed += (1 << scrub_order);
                     if ( softirq_pending(cpu) )
-                        goto out;
+                    {
+                        preempt = 1;
+                        is_frag = (num_scrubbed < (1 << order));
+                        break;
+                    }
                 }
 
-                pg->count_info &= ~PGC_need_scrub;
+                start = 0;
+                end = num_scrubbed;
 
-                page_list_del(pg, &heap(node, zone, order));
-                (void)merge_chunks(pg, node, zone, order);
+                /* Merge clean pages */
+                pg->count_info &= ~PGC_need_scrub;
+                while ( start < end )
+                {
+                    /*
+                     * Largest power-of-two chunk starting @start,
+                     * not greater than @end
+                     */
+                    unsigned chunk_order = flsl(end - start) - 1;
+                    struct page_info *ppg = &pg[start];
+
+                    node_need_scrub[node] -= (1 << chunk_order);
+
+                    PFN_ORDER(ppg) = chunk_order;
+                    (void)merge_chunks(ppg, node, zone, chunk_order, is_frag);
+                    start += (1 << chunk_order);
+                }
 
-                node_need_scrub[node] -= (1UL << order);
+                /* Merge unscrubbed pages */
+                while ( end < (1 << order) )
+                {
+                    /*
+                     * Largest power-of-two chunk starting @end, not crossing
+                     * next power-of-two boundary
+                     */
+                    unsigned chunk_order = ffsl(end) - 1;
+                    struct page_info *ppg = &pg[end];
+
+                    PFN_ORDER(ppg) = chunk_order;
+                    ppg->count_info |= PGC_need_scrub;
+                    (void)merge_chunks(ppg, node, zone, chunk_order, true);
+                    end += (1 << chunk_order);
+                 }
+
+                if ( preempt )
+                    goto out;
             }
         }
     }
@@ -1174,7 +1226,7 @@ static void free_heap_pages(
         node_need_scrub[node] += (1UL << order);
     }
 
-    pg = merge_chunks(pg, node, zone, order);
+    pg = merge_chunks(pg, node, zone, order, false);
 
     if ( tainted )
         reserve_offlined_page(pg);
