Commit:     835c134ec4dd755e5c4470af566db226d1e96742
Parent:     954ffcb35f5aca428661d29b96c4eee82b3c19cd
Author:     Mel Gorman <[EMAIL PROTECTED]>
AuthorDate: Tue Oct 16 01:25:47 2007 -0700
Committer:  Linus Torvalds <[EMAIL PROTECTED]>
CommitDate: Tue Oct 16 09:42:59 2007 -0700

    Add a bitmap that is used to track flags affecting a block of pages
    Here is the latest revision of the anti-fragmentation patches.  Of 
    note in this version is special treatment of high-order atomic allocations.
    Care is taken to group them together and avoid grouping pages of other types
    near them.  Artifical tests imply that it works.  I'm trying to get the
    hardware together that would allow setting up of a "real" test.  If anyone
    already has a setup and test that can trigger the atomic-allocation problem,
    I'd appreciate a test of these patches and a report.  The second major 
    is that these patches will apply cleanly with patches that implement
    anti-fragmentation through zones.
    kernbench shows effectively no performance difference varying between -0.2%
    and +2% on a variety of test machines.  Success rates for huge page 
    are dramatically increased.  For example, on a ppc64 machine, the vanilla
    kernel was only able to allocate 1% of memory as a hugepage and this was due
    to a single hugepage reserved as min_free_kbytes.  With these patches 
    17% was allocatable as superpages.  With reclaim-related fixes from Andy
    Whitcroft, it was 40% and further reclaim-related improvements should 
    this further.
    Changelog Since V28
    o Group high-order atomic allocations together
    o It is no longer required to set min_free_kbytes to 10% of memory. A value
      of 16384 in most cases will be sufficient
    o Now applied with zone-based anti-fragmentation
    o Fix incorrect VM_BUG_ON within buffered_rmqueue()
    o Reorder the stack so later patches do not back out work from earlier 
    o Fix bug were journal pages were being treated as movable
    o Bias placement of non-movable pages to lower PFNs
    o More agressive clustering of reclaimable pages in reactions to workloads
      like updatedb that flood the size of inode caches
    Changelog Since V27
    o Renamed anti-fragmentation to Page Clustering. Anti-fragmentation was 
      the mistaken impression that it was the 100% solution for high order
      allocations. Instead, it greatly increases the chances high-order
      allocations will succeed and lays the foundation for defragmentation and
      memory hot-remove to work properly
    o Redefine page groupings based on ability to migrate or reclaim instead of
      basing on reclaimability alone
    o Get rid of spurious inits
    o Per-cpu lists are no longer split up per-type. Instead the per-cpu list is
      searched for a page of the appropriate type
    o Added more explanation commentary
    o Fix up bug in pageblock code where bitmap was used before being initalised
    Changelog Since V26
    o Fix double init of lists in setup_pageset
    Changelog Since V25
    o Fix loop order of for_each_rclmtype_order so that order of loop matches 
    o gfpflags_to_rclmtype uses gfp_t instead of unsigned long
    o Rename get_pageblock_type() to get_page_rclmtype()
    o Fix alignment problem in move_freepages()
    o Add mechanism for assigning flags to blocks of pages instead of 
    o On fallback, do not examine the preferred list of free pages a second time
    The purpose of these patches is to reduce external fragmentation by grouping
    pages of related types together.  When pages are migrated (or reclaimed 
    memory pressure), large contiguous pages will be freed.
    This patch works by categorising allocations by their ability to migrate;
    Movable - The pages may be moved with the page migration mechanism. These 
        generally userspace pages.
    Reclaimable - These are allocations for some kernel caches that are
        reclaimable or allocations that are known to be very short-lived.
    Unmovable - These are pages that are allocated by the kernel that
        are not trivially reclaimed. For example, the memory allocated for a
        loaded module would be in this category. By default, allocations are
        considered to be of this type
    HighAtomic - These are high-order allocations belonging to callers that
        cannot sleep or perform any IO. In practice, this is restricted to
        jumbo frame allocation for network receive. It is assumed that the
        allocations are short-lived
    Instead of having one MAX_ORDER-sized array of free lists in struct 
    there is one for each type of reclaimability.  Once a 2^MAX_ORDER block of
    pages is split for a type of allocation, it is added to the free-lists for
    that type, in effect reserving it.  Hence, over time, pages of the different
    types can be clustered together.
    When the preferred freelists are expired, the largest possible block is 
    from an alternative list.  Buddies that are split from that large block are
    placed on the preferred allocation-type freelists to mitigate fragmentation.
    This implementation gives best-effort for low fragmentation in all zones.
    Ideally, min_free_kbytes needs to be set to a value equal to 4 * (1 <<
    (MAX_ORDER-1)) pages in most cases.  This would be 16384 on x86 and x86_64 
    Our tests show that about 60-70% of physical memory can be allocated on a
    desktop after a few days uptime.  In benchmarks and stress tests, we are
    finding that 80% of memory is available as contiguous blocks at the end of 
    test.  To compare, a standard kernel was getting < 1% of memory as large 
    on a desktop and about 8-12% of memory as large pages at the end of stress
    Following this email are 12 patches that implement thie page grouping 
     The first patch introduces a mechanism for storing flags related to a whole
    block of pages.  Then allocations are split between movable and all other
    allocations.  Following that are patches to deal with per-cpu pages and make
    the mechanism configurable.  The next patch moves free pages between lists
    when partially allocated blocks are used for pages of another migrate type.
    The second last patch groups reclaimable kernel allocations such as inode
    caches together.  The final patch related to groupings keeps high-order 
    The last two patches are more concerned with control of fragmentation.  The
    second last patch biases placement of non-movable allocations towards the
    start of memory.  This is with a view of supporting memory hot-remove of 
    with higher PFNs in the future.  The biasing could be enforced a lot heavier
    but it would cost.  The last patch agressively clusters reclaimable pages 
    inode caches together.
    The fragmentation reduction strategy needs to track if pages within a block
    can be moved or reclaimed so that pages are freed to the appropriate list.
    This patch adds a bitmap for flags affecting a whole a MAX_ORDER block of
    In non-SPARSEMEM configurations, the bitmap is stored in the struct zone and
    allocated during initialisation.  SPARSEMEM statically allocates the bitmap 
    a struct mem_section so that bitmaps do not have to be resized during memory
    hotadd.  This wastes a small amount of memory per unused section (usually
    sizeof(unsigned long)) but the complexity of dynamically allocating the 
    is quite high.
    Additional credit to Andy Whitcroft who reviewed up an earlier 
    of the mechanism an suggested how to make it a *lot* cleaner.
    Signed-off-by: Mel Gorman <[EMAIL PROTECTED]>
    Cc: Andy Whitcroft <[EMAIL PROTECTED]>
    Signed-off-by: Andrew Morton <[EMAIL PROTECTED]>
    Signed-off-by: Linus Torvalds <[EMAIL PROTECTED]>
 include/linux/mmzone.h          |   13 +++++
 include/linux/pageblock-flags.h |   51 ++++++++++++++++++
 mm/page_alloc.c                 |  111 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 175 insertions(+), 0 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index f6167f2..322e804 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -13,6 +13,7 @@
 #include <linux/init.h>
 #include <linux/seqlock.h>
 #include <linux/nodemask.h>
+#include <linux/pageblock-flags.h>
 #include <asm/atomic.h>
 #include <asm/page.h>
@@ -222,6 +223,14 @@ struct zone {
        struct free_area        free_area[MAX_ORDER];
+       /*
+        * Flags for a MAX_ORDER_NR_PAGES block. See pageblock-flags.h.
+        * In SPARSEMEM, this map is stored in struct mem_section
+        */
+       unsigned long           *pageblock_flags;
+#endif /* CONFIG_SPARSEMEM */
@@ -720,6 +729,9 @@ extern struct zone *next_zone(struct zone *zone);
 #error Allocator MAX_ORDER exceeds SECTION_SIZE
@@ -739,6 +751,7 @@ struct mem_section {
         * before using it wrong.
        unsigned long section_mem_map;
diff --git a/include/linux/pageblock-flags.h b/include/linux/pageblock-flags.h
new file mode 100644
index 0000000..96b623f
--- /dev/null
+++ b/include/linux/pageblock-flags.h
@@ -0,0 +1,51 @@
+ * Macros for manipulating and testing flags related to a
+ * MAX_ORDER_NR_PAGES block of pages.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation version 2 of the License
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright (C) IBM Corporation, 2006
+ *
+ * Original author, Mel Gorman
+ * Major cleanups and reduction of bit operations, Andy Whitcroft
+ */
+#include <linux/types.h>
+/* Macro to aid the definition of ranges of bits */
+#define PB_range(name, required_bits) \
+       name, name ## _end = (name + required_bits) - 1
+/* Bit indices that affect a whole block of pages */
+enum pageblock_bits {
+/* Forward declaration */
+struct page;
+/* Declarations for getting and setting flags. See mm/page_alloc.c */
+unsigned long get_pageblock_flags_group(struct page *page,
+                                       int start_bitidx, int end_bitidx);
+void set_pageblock_flags_group(struct page *page, unsigned long flags,
+                                       int start_bitidx, int end_bitidx);
+#define get_pageblock_flags(page) \
+                       get_pageblock_flags_group(page, 0, NR_PAGEBLOCK_BITS-1)
+#define set_pageblock_flags(page) \
+                       set_pageblock_flags_group(page, 0, NR_PAGEBLOCK_BITS-1)
+#endif /* PAGEBLOCK_FLAGS_H */
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index e69f19e..332f46d 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -2931,6 +2931,41 @@ static void __meminit calculate_node_totalpages(struct 
pglist_data *pgdat,
+ * Calculate the size of the zone->blockflags rounded to an unsigned long
+ * Start by making sure zonesize is a multiple of MAX_ORDER-1 by rounding up
+ * Then figure 1 NR_PAGEBLOCK_BITS worth of bits per MAX_ORDER-1, finally
+ * round what is now in bits to nearest long in bits, then return it in
+ * bytes.
+ */
+static unsigned long __init usemap_size(unsigned long zonesize)
+       unsigned long usemapsize;
+       usemapsize = roundup(zonesize, MAX_ORDER_NR_PAGES);
+       usemapsize = usemapsize >> (MAX_ORDER-1);
+       usemapsize *= NR_PAGEBLOCK_BITS;
+       usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));
+       return usemapsize / 8;
+static void __init setup_usemap(struct pglist_data *pgdat,
+                               struct zone *zone, unsigned long zonesize)
+       unsigned long usemapsize = usemap_size(zonesize);
+       zone->pageblock_flags = NULL;
+       if (usemapsize) {
+               zone->pageblock_flags = alloc_bootmem_node(pgdat, usemapsize);
+               memset(zone->pageblock_flags, 0, usemapsize);
+       }
+static void inline setup_usemap(struct pglist_data *pgdat,
+                               struct zone *zone, unsigned long zonesize) {}
+#endif /* CONFIG_SPARSEMEM */
  * Set up the zone data structures:
  *   - mark all pages reserved
@@ -3011,6 +3046,7 @@ static void __meminit free_area_init_core(struct 
pglist_data *pgdat,
                if (!size)
+               setup_usemap(pgdat, zone, size);
                ret = init_currently_empty_zone(zone, zone_start_pfn,
                                                size, MEMMAP_EARLY);
@@ -3991,4 +4027,79 @@ EXPORT_SYMBOL(pfn_to_page);
+/* Return a pointer to the bitmap storing bits affecting a block of pages */
+static inline unsigned long *get_pageblock_bitmap(struct zone *zone,
+                                                       unsigned long pfn)
+       return __pfn_to_section(pfn)->pageblock_flags;
+       return zone->pageblock_flags;
+#endif /* CONFIG_SPARSEMEM */
+static inline int pfn_to_bitidx(struct zone *zone, unsigned long pfn)
+       pfn &= (PAGES_PER_SECTION-1);
+       return (pfn >> (MAX_ORDER-1)) * NR_PAGEBLOCK_BITS;
+       pfn = pfn - zone->zone_start_pfn;
+       return (pfn >> (MAX_ORDER-1)) * NR_PAGEBLOCK_BITS;
+#endif /* CONFIG_SPARSEMEM */
+ * get_pageblock_flags_group - Return the requested group of flags for the 
MAX_ORDER_NR_PAGES block of pages
+ * @page: The page within the block of interest
+ * @start_bitidx: The first bit of interest to retrieve
+ * @end_bitidx: The last bit of interest
+ * returns pageblock_bits flags
+ */
+unsigned long get_pageblock_flags_group(struct page *page,
+                                       int start_bitidx, int end_bitidx)
+       struct zone *zone;
+       unsigned long *bitmap;
+       unsigned long pfn, bitidx;
+       unsigned long flags = 0;
+       unsigned long value = 1;
+       zone = page_zone(page);
+       pfn = page_to_pfn(page);
+       bitmap = get_pageblock_bitmap(zone, pfn);
+       bitidx = pfn_to_bitidx(zone, pfn);
+       for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
+               if (test_bit(bitidx + start_bitidx, bitmap))
+                       flags |= value;
+       return flags;
+ * set_pageblock_flags_group - Set the requested group of flags for a 
MAX_ORDER_NR_PAGES block of pages
+ * @page: The page within the block of interest
+ * @start_bitidx: The first bit of interest
+ * @end_bitidx: The last bit of interest
+ * @flags: The flags to set
+ */
+void set_pageblock_flags_group(struct page *page, unsigned long flags,
+                                       int start_bitidx, int end_bitidx)
+       struct zone *zone;
+       unsigned long *bitmap;
+       unsigned long pfn, bitidx;
+       unsigned long value = 1;
+       zone = page_zone(page);
+       pfn = page_to_pfn(page);
+       bitmap = get_pageblock_bitmap(zone, pfn);
+       bitidx = pfn_to_bitidx(zone, pfn);
+       for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
+               if (flags & value)
+                       __set_bit(bitidx + start_bitidx, bitmap);
+               else
+                       __clear_bit(bitidx + start_bitidx, bitmap);
To unsubscribe from this list: send the line "unsubscribe git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at

Reply via email to