/* * linux/mm/page_alloc.c * * Manages the free list, the system allocates free pages here. * Note that kmalloc() lives in slab.c * * Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds * Swap reorganised 29.12.95, Stephen Tweedie * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999 * Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999 * Zone balancing, Kanoj Sarcar, SGI, Jan 2000 * Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002 * (lots of bits borrowed from Ingo Molnar & Andrew Morton) */ #include <linux/config.h>#include <linux/stddef.h>#include <linux/mm.h>#include <linux/swap.h>#include <linux/interrupt.h>#include <linux/pagemap.h>#include <linux/bootmem.h>#include <linux/compiler.h>#include <linux/module.h>#include <linux/suspend.h>#include <linux/pagevec.h>#include <linux/blkdev.h>#include <linux/slab.h>#include <linux/notifier.h>#include <linux/topology.h>#include <linux/sysctl.h>#include <linux/cpu.h>#include <linux/cpuset.h>#include <linux/nodemask.h>#include <linux/vmalloc.h> #include <asm/tlbflush.h>#include "internal.h" /* * MCD - HACK: Find somewhere to initialize this EARLY, or make this * initializer cleaner */nodemask_t node_online_map = { { [0] = 1UL } };EXPORT_SYMBOL(node_online_map);nodemask_t node_possible_map = NODE_MASK_ALL;EXPORT_SYMBOL(node_possible_map);struct pglist_data *pgdat_list;unsigned long totalram_pages;unsigned long totalhigh_pages;long nr_swap_pages; /* * results with 256, 32 in the lowmem_reserve sysctl: * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high) * 1G machine -> (16M dma, 784M normal, 224M high) * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA */int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 256, 32 }; EXPORT_SYMBOL(totalram_pages);EXPORT_SYMBOL(nr_swap_pages); /* * Used by page_zone() to look up the address of the struct zone whose * id is encoded in the upper bits of page->flags */struct zone *zone_table[1 << ZONETABLE_SHIFT];EXPORT_SYMBOL(zone_table); static char *zone_names[MAX_NR_ZONES] = { "DMA", "Normal", "HighMem" };int min_free_kbytes = 1024; unsigned long __initdata nr_kernel_pages;unsigned long __initdata nr_all_pages; /* * Temporary debugging check for pages not lying within a given zone. */static int bad_range(struct zone *zone, struct page *page){ if (page_to_pfn(page) >= zone->zone_start_pfn + zone->spanned_pages) return 1; if (page_to_pfn(page) < zone->zone_start_pfn) return 1;#ifdef CONFIG_HOLES_IN_ZONE if (!pfn_valid(page_to_pfn(page))) return 1;#endif if (zone != page_zone(page)) return 1; return 0;} static void bad_page(const char *function, struct page *page){ printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n", function, current->comm, page); printk(KERN_EMERG "flags:0x%0*lx mapping:%p mapcount:%d count:%d\n", (int)(2*sizeof(page_flags_t)), (unsigned long)page->flags, page->mapping, page_mapcount(page), page_count(page)); printk(KERN_EMERG "Backtrace:\n"); dump_stack(); printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n"); page->flags &= ~(1 << PG_lru | 1 << PG_private | 1 << PG_locked | 1 << PG_active | 1 << PG_dirty | 1 << PG_reclaim | 1 << PG_slab | 1 << PG_swapcache | 1 << PG_writeback); set_page_count(page, 0); reset_page_mapcount(page); page->mapping = NULL; tainted |= TAINT_BAD_PAGE;} #ifndef CONFIG_HUGETLB_PAGE#define prep_compound_page(page, order) do { } while (0)#define destroy_compound_page(page, order) do { } while (0)#else/* * Higher-order pages are called "compound pages". They are structured thusly: * * The first PAGE_SIZE page is called the "head page". * * The remaining PAGE_SIZE pages are called "tail pages". * * All pages have PG_compound set. All pages have their ->private pointing at * the head page (even the head page has this). * * The first tail page's ->mapping, if non-zero, holds the address of the * compound page's put_page() function. * * The order of the allocation is stored in the first tail page's ->index * This is only for debug at present. This usage means that zero-order pages * may not be compound. */static void prep_compound_page(struct page *page, unsigned long order){ int i; int nr_pages = 1 << order; page[1].mapping = NULL; page[1].index = order; for (i = 0; i < nr_pages; i++) { struct page *p = page + i; SetPageCompound(p); p->private = (unsigned long)page; }} static void destroy_compound_page(struct page *page, unsigned long order){ int i; int nr_pages = 1 << order; if (!PageCompound(page)) return; if (page[1].index != order) bad_page(__FUNCTION__, page); for (i = 0; i < nr_pages; i++) { struct page *p = page + i; if (!PageCompound(p)) bad_page(__FUNCTION__, page); if (p->private != (unsigned long)page) bad_page(__FUNCTION__, page); ClearPageCompound(p); }}#endif /* CONFIG_HUGETLB_PAGE */ /* * function for dealing with page's order in buddy system. * zone->lock is already acquired when we use these. * So, we don't need atomic page->flags operations here. */static inline unsigned long page_order(struct page *page) { return page->private;} static inline void set_page_order(struct page *page, int order) { page->private = order; __SetPagePrivate(page);} static inline void rmv_page_order(struct page *page){ __ClearPagePrivate(page); page->private = 0;} /* * Locate the struct page for both the matching buddy in our * pair (buddy1) and the combined O(n+1) page they form (page). * * 1) Any buddy B1 will have an order O twin B2 which satisfies * the following equation: * B2 = B1 ^ (1 << O) * For example, if the starting buddy (buddy2) is #8 its order * 1 buddy is #10: * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10 * * 2) Any buddy B will have an order O+1 parent P which * satisfies the following equation: * P = B & ~(1 << O) * * Assumption: *_mem_map is contigious at least up to MAX_ORDER */static inline struct page *__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order){ unsigned long buddy_idx = page_idx ^ (1 << order); return page + (buddy_idx - page_idx);} static inline unsigned long__find_combined_index(unsigned long page_idx, unsigned int order){ return (page_idx & ~(1 << order));} /* * This function checks whether a page is free && is the buddy * we can do coalesce a page and its buddy if * (a) the buddy is free && * (b) the buddy is on the buddy system && * (c) a page and its buddy have the same order. * for recording page's order, we use page->private and PG_private. * */static inline int page_is_buddy(struct page *page, int order){ if (PagePrivate(page) && (page_order(page) == order) && !PageReserved(page) && page_count(page) == 0) return 1; return 0;} /* * Freeing function for a buddy system allocator. * * The concept of a buddy system is to maintain direct-mapped table * (containing bit values) for memory blocks of various "orders". * The bottom level table contains the map for the smallest allocatable * units of memory (here, pages), and each level above it describes * pairs of units from the levels below, hence, "buddies". * At a high level, all that happens here is marking the table entry * at the bottom level available, and propagating the changes upward * as necessary, plus some accounting needed to play nicely with other * parts of the VM system. * At each level, we keep a list of pages, which are heads of continuous * free pages of length of (1 << order) and marked with PG_Private.Page's * order is recorded in page->private field. * So when we are allocating or freeing one, we can derive the state of the * other. That is, if we allocate a small block, and both were * free, the remainder of the region must be split into blocks. * If a block is freed, and its buddy is also free, then this * triggers coalescing into a block of larger size. * * -- wli */ static inline void __free_pages_bulk (struct page *page, struct zone *zone, unsigned int order){ unsigned long page_idx; int order_size = 1 << order; if (unlikely(order)) destroy_compound_page(page, order); page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); BUG_ON(page_idx & (order_size - 1)); BUG_ON(bad_range(zone, page)); zone->free_pages += order_size; while (order < MAX_ORDER-1) { unsigned long combined_idx; struct free_area *area; struct page *buddy; combined_idx = __find_combined_index(page_idx, order); buddy = __page_find_buddy(page, page_idx, order); if (bad_range(zone, buddy)) break; if (!page_is_buddy(buddy, order)) break; /* Move the buddy up one level. */ list_del(&buddy->lru); area = zone->free_area + order; area->nr_free--; rmv_page_order(buddy); page = page + (combined_idx - page_idx); page_idx = combined_idx; order++; } set_page_order(page, order); list_add(&page->lru, &zone->free_area[order].free_list); zone->free_area[order].nr_free++;} static inline void free_pages_check(const char *function, struct page *page){ if ( page_mapcount(page) || page->mapping != NULL || page_count(page) != 0 || (page->flags & ( 1 << PG_lru | 1 << PG_private | 1 << PG_locked | 1 << PG_active | 1 << PG_reclaim | 1 << PG_slab | 1 << PG_swapcache | 1 << PG_writeback ))) bad_page(function, page); if (PageDirty(page)) ClearPageDirty(page);} /* * Frees a list of pages. * Assumes all pages on list are in same zone, and of same order. * count is the number of pages to free, or 0 for all on the list. * * If the zone was previously in an "all pages pinned" state then look to * see if this freeing clears that state. * * And clear the zone's pages_scanned counter, to hold off the "all pages are * pinned" detection logic. */static intfree_pages_bulk(struct zone *zone, int count, struct list_head *list, unsigned int order){ unsigned long flags; struct page *page = NULL; int ret = 0; spin_lock_irqsave(&zone->lock, flags); zone->all_unreclaimable = 0; zone->pages_scanned = 0; while (!list_empty(list) && count--) { page = list_entry(list->prev, struct page, lru); /* have to delete it as __free_pages_bulk list manipulates */ list_del(&page->lru); __free_pages_bulk(page, zone, order); ret++; } spin_unlock_irqrestore(&zone->lock, flags); return ret;} void __free_pages_ok(struct page *page, unsigned int order){ LIST_HEAD(list); int i; arch_free_page(page, order); mod_page_state(pgfree, 1 << order); #ifndef CONFIG_MMU if (order > 0) for (i = 1 ; i < (1 << order) ; ++i) __put_page(page + i);#endif for (i = 0 ; i < (1 << order) ; ++i) free_pages_check(__FUNCTION__, page + i); list_add(&page->lru, &list); kernel_map_pages(page, 1<<order, 0); free_pages_bulk(page_zone(page), 1, &list, order);} /* * The order of subdivision here is critical for the IO subsystem. * Please do not alter this order without good reasons and regression * testing. Specifically, as large blocks of memory are subdivided, * the order in which smaller blocks are delivered depends on the order * they're subdivided in this function. This is the primary factor * influencing the order in which pages are delivered to the IO * subsystem according to empirical testing, and this is also justified * by considering the behavior of a buddy system containing a single * large block of memory acted on by a series of small allocations. * This behavior is a critical factor in sglist merging's success. * * -- wli */static inline struct page *expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area){ unsigned long size = 1 << high; while (high > low) { area--; high--; size >>= 1; BUG_ON(bad_range(zone, &page[size])); list_add(&page[size].lru, &area->free_list); area->nr_free++; set_page_order(&page[size], high); } return page;} void set_page_refs(struct page *page, int order){#ifdef CONFIG_MMU set_page_count(page, 1);#else int i; /* * We need to reference all the pages for this order, otherwise if * anyone accesses one of the pages with (get/put) it will be freed. * - eg: access_process_vm() */ for (i = 0; i < (1 << order); i++) set_page_count(page + i, 1);#endif /* CONFIG_MMU */} /* * This page is about to be returned from the page allocator */static void prep_new_page(struct page *page, int order){ if ( page_mapcount(page) || page->mapping != NULL || page_count(page) != 0 || (page->flags & ( 1 << PG_lru | 1 << PG_private | 1 << PG_locked | 1 << PG_active | 1 << PG_dirty | 1 << PG_reclaim | 1 << PG_slab | 1 << PG_swapcache | 1 << PG_writeback ))) bad_page(__FUNCTION__, page); page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 1 << PG_referenced | 1 << PG_arch_1 | 1 << PG_checked | 1 << PG_mappedtodisk); page->private = 0; set_page_refs(page, order); kernel_map_pages(page, 1 << order, 1);} /* * Do the hard work of removing an element from the buddy allocator. * Call me with the zone->lock already held. */static struct page *__rmqueue(struct zone *zone, unsigned int order){ struct free_area * area; unsigned int current_order; struct page *page; for (current_order = order; current_order < MAX_ORDER; ++current_order) { area = zone->free_area + current_order; if (list_empty(&area->free_list)) continue; page = list_entry(area->free_list.next, struct page, lru); list_del(&page->lru); rmv_page_order(page); area->nr_free--; zone->free_pages -= 1UL << order; return expand(zone, page, order, current_order, area); } return NULL;} /* * Obtain a specified number of elements from the buddy allocator, all under * a single hold of the lock, for efficiency. Add them to the supplied list. * Returns the number of new pages which were placed at *list. */static int rmqueue_bulk(struct zone *zone, unsigned int order, unsigned long count, struct list_head *list)Lines 1–500 of 2549. Load more
/* * linux/mm/page_alloc.c * * Manages the free list, the system allocates free pages here. * Note that kmalloc() lives in slab.c * * Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds * Swap reorganised 29.12.95, Stephen Tweedie * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999 * Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999 * Zone balancing, Kanoj Sarcar, SGI, Jan 2000 * Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002 * (lots of bits borrowed from Ingo Molnar & Andrew Morton) */ #include <linux/config.h> #include <linux/stddef.h> #include <linux/mm.h> #include <linux/swap.h> #include <linux/interrupt.h> #include <linux/pagemap.h> #include <linux/bootmem.h> #include <linux/compiler.h> #include <linux/module.h> #include <linux/suspend.h> #include <linux/pagevec.h> #include <linux/blkdev.h> #include <linux/slab.h> #include <linux/notifier.h> #include <linux/topology.h> #include <linux/sysctl.h> #include <linux/cpu.h> #include <linux/cpuset.h> #include <linux/nodemask.h> #include <linux/vmalloc.h> #include <asm/tlbflush.h> #include "internal.h" /* * MCD - HACK: Find somewhere to initialize this EARLY, or make this * initializer cleaner */ nodemask_t node_online_map = { { [0] = 1UL } }; EXPORT_SYMBOL(node_online_map); nodemask_t node_possible_map = NODE_MASK_ALL; EXPORT_SYMBOL(node_possible_map); struct pglist_data *pgdat_list; unsigned long totalram_pages; unsigned long totalhigh_pages; long nr_swap_pages; /* * results with 256, 32 in the lowmem_reserve sysctl: * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high) * 1G machine -> (16M dma, 784M normal, 224M high) * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA */ int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 256, 32 }; EXPORT_SYMBOL(totalram_pages); EXPORT_SYMBOL(nr_swap_pages); /* * Used by page_zone() to look up the address of the struct zone whose * id is encoded in the upper bits of page->flags */ struct zone *zone_table[1 << ZONETABLE_SHIFT]; EXPORT_SYMBOL(zone_table); static char *zone_names[MAX_NR_ZONES] = { "DMA", "Normal", "HighMem" }; int min_free_kbytes = 1024; unsigned long __initdata nr_kernel_pages; unsigned long __initdata nr_all_pages; /* * Temporary debugging check for pages not lying within a given zone. */ static int bad_range(struct zone *zone, struct page *page) { if (page_to_pfn(page) >= zone->zone_start_pfn + zone->spanned_pages) return 1; if (page_to_pfn(page) < zone->zone_start_pfn) return 1; #ifdef CONFIG_HOLES_IN_ZONE if (!pfn_valid(page_to_pfn(page))) return 1; #endif if (zone != page_zone(page)) return 1; return 0; } static void bad_page(const char *function, struct page *page) { printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n", function, current->comm, page); printk(KERN_EMERG "flags:0x%0*lx mapping:%p mapcount:%d count:%d\n", (int)(2*sizeof(page_flags_t)), (unsigned long)page->flags, page->mapping, page_mapcount(page), page_count(page)); printk(KERN_EMERG "Backtrace:\n"); dump_stack(); printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n"); page->flags &= ~(1 << PG_lru | 1 << PG_private | 1 << PG_locked | 1 << PG_active | 1 << PG_dirty | 1 << PG_reclaim | 1 << PG_slab | 1 << PG_swapcache | 1 << PG_writeback); set_page_count(page, 0); reset_page_mapcount(page); page->mapping = NULL; tainted |= TAINT_BAD_PAGE; } #ifndef CONFIG_HUGETLB_PAGE #define prep_compound_page(page, order) do { } while (0) #define destroy_compound_page(page, order) do { } while (0) #else /* * Higher-order pages are called "compound pages". They are structured thusly: * * The first PAGE_SIZE page is called the "head page". * * The remaining PAGE_SIZE pages are called "tail pages". * * All pages have PG_compound set. All pages have their ->private pointing at * the head page (even the head page has this). * * The first tail page's ->mapping, if non-zero, holds the address of the * compound page's put_page() function. * * The order of the allocation is stored in the first tail page's ->index * This is only for debug at present. This usage means that zero-order pages * may not be compound. */ static void prep_compound_page(struct page *page, unsigned long order) { int i; int nr_pages = 1 << order; page[1].mapping = NULL; page[1].index = order; for (i = 0; i < nr_pages; i++) { struct page *p = page + i; SetPageCompound(p); p->private = (unsigned long)page; } } static void destroy_compound_page(struct page *page, unsigned long order) { int i; int nr_pages = 1 << order; if (!PageCompound(page)) return; if (page[1].index != order) bad_page(__FUNCTION__, page); for (i = 0; i < nr_pages; i++) { struct page *p = page + i; if (!PageCompound(p)) bad_page(__FUNCTION__, page); if (p->private != (unsigned long)page) bad_page(__FUNCTION__, page); ClearPageCompound(p); } } #endif /* CONFIG_HUGETLB_PAGE */ /* * function for dealing with page's order in buddy system. * zone->lock is already acquired when we use these. * So, we don't need atomic page->flags operations here. */ static inline unsigned long page_order(struct page *page) { return page->private; } static inline void set_page_order(struct page *page, int order) { page->private = order; __SetPagePrivate(page); } static inline void rmv_page_order(struct page *page) { __ClearPagePrivate(page); page->private = 0; } /* * Locate the struct page for both the matching buddy in our * pair (buddy1) and the combined O(n+1) page they form (page). * * 1) Any buddy B1 will have an order O twin B2 which satisfies * the following equation: * B2 = B1 ^ (1 << O) * For example, if the starting buddy (buddy2) is #8 its order * 1 buddy is #10: * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10 * * 2) Any buddy B will have an order O+1 parent P which * satisfies the following equation: * P = B & ~(1 << O) * * Assumption: *_mem_map is contigious at least up to MAX_ORDER */ static inline struct page * __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order) { unsigned long buddy_idx = page_idx ^ (1 << order); return page + (buddy_idx - page_idx); } static inline unsigned long __find_combined_index(unsigned long page_idx, unsigned int order) { return (page_idx & ~(1 << order)); } /* * This function checks whether a page is free && is the buddy * we can do coalesce a page and its buddy if * (a) the buddy is free && * (b) the buddy is on the buddy system && * (c) a page and its buddy have the same order. * for recording page's order, we use page->private and PG_private. * */ static inline int page_is_buddy(struct page *page, int order) { if (PagePrivate(page) && (page_order(page) == order) && !PageReserved(page) && page_count(page) == 0) return 1; return 0; } /* * Freeing function for a buddy system allocator. * * The concept of a buddy system is to maintain direct-mapped table * (containing bit values) for memory blocks of various "orders". * The bottom level table contains the map for the smallest allocatable * units of memory (here, pages), and each level above it describes * pairs of units from the levels below, hence, "buddies". * At a high level, all that happens here is marking the table entry * at the bottom level available, and propagating the changes upward * as necessary, plus some accounting needed to play nicely with other * parts of the VM system. * At each level, we keep a list of pages, which are heads of continuous * free pages of length of (1 << order) and marked with PG_Private.Page's * order is recorded in page->private field. * So when we are allocating or freeing one, we can derive the state of the * other. That is, if we allocate a small block, and both were * free, the remainder of the region must be split into blocks. * If a block is freed, and its buddy is also free, then this * triggers coalescing into a block of larger size. * * -- wli */ static inline void __free_pages_bulk (struct page *page, struct zone *zone, unsigned int order) { unsigned long page_idx; int order_size = 1 << order; if (unlikely(order)) destroy_compound_page(page, order); page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); BUG_ON(page_idx & (order_size - 1)); BUG_ON(bad_range(zone, page)); zone->free_pages += order_size; while (order < MAX_ORDER-1) { unsigned long combined_idx; struct free_area *area; struct page *buddy; combined_idx = __find_combined_index(page_idx, order); buddy = __page_find_buddy(page, page_idx, order); if (bad_range(zone, buddy)) break; if (!page_is_buddy(buddy, order)) break; /* Move the buddy up one level. */ list_del(&buddy->lru); area = zone->free_area + order; area->nr_free--; rmv_page_order(buddy); page = page + (combined_idx - page_idx); page_idx = combined_idx; order++; } set_page_order(page, order); list_add(&page->lru, &zone->free_area[order].free_list); zone->free_area[order].nr_free++; } static inline void free_pages_check(const char *function, struct page *page) { if ( page_mapcount(page) || page->mapping != NULL || page_count(page) != 0 || (page->flags & ( 1 << PG_lru | 1 << PG_private | 1 << PG_locked | 1 << PG_active | 1 << PG_reclaim | 1 << PG_slab | 1 << PG_swapcache | 1 << PG_writeback ))) bad_page(function, page); if (PageDirty(page)) ClearPageDirty(page); } /* * Frees a list of pages. * Assumes all pages on list are in same zone, and of same order. * count is the number of pages to free, or 0 for all on the list. * * If the zone was previously in an "all pages pinned" state then look to * see if this freeing clears that state. * * And clear the zone's pages_scanned counter, to hold off the "all pages are * pinned" detection logic. */ static int free_pages_bulk(struct zone *zone, int count, struct list_head *list, unsigned int order) { unsigned long flags; struct page *page = NULL; int ret = 0; spin_lock_irqsave(&zone->lock, flags); zone->all_unreclaimable = 0; zone->pages_scanned = 0; while (!list_empty(list) && count--) { page = list_entry(list->prev, struct page, lru); /* have to delete it as __free_pages_bulk list manipulates */ list_del(&page->lru); __free_pages_bulk(page, zone, order); ret++; } spin_unlock_irqrestore(&zone->lock, flags); return ret; } void __free_pages_ok(struct page *page, unsigned int order) { LIST_HEAD(list); int i; arch_free_page(page, order); mod_page_state(pgfree, 1 << order); #ifndef CONFIG_MMU if (order > 0) for (i = 1 ; i < (1 << order) ; ++i) __put_page(page + i); #endif for (i = 0 ; i < (1 << order) ; ++i) free_pages_check(__FUNCTION__, page + i); list_add(&page->lru, &list); kernel_map_pages(page, 1<<order, 0); free_pages_bulk(page_zone(page), 1, &list, order); } /* * The order of subdivision here is critical for the IO subsystem. * Please do not alter this order without good reasons and regression * testing. Specifically, as large blocks of memory are subdivided, * the order in which smaller blocks are delivered depends on the order * they're subdivided in this function. This is the primary factor * influencing the order in which pages are delivered to the IO * subsystem according to empirical testing, and this is also justified * by considering the behavior of a buddy system containing a single * large block of memory acted on by a series of small allocations. * This behavior is a critical factor in sglist merging's success. * * -- wli */ static inline struct page * expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area) { unsigned long size = 1 << high; while (high > low) { area--; high--; size >>= 1; BUG_ON(bad_range(zone, &page[size])); list_add(&page[size].lru, &area->free_list); area->nr_free++; set_page_order(&page[size], high); } return page; } void set_page_refs(struct page *page, int order) { #ifdef CONFIG_MMU set_page_count(page, 1); #else int i; /* * We need to reference all the pages for this order, otherwise if * anyone accesses one of the pages with (get/put) it will be freed. * - eg: access_process_vm() */ for (i = 0; i < (1 << order); i++) set_page_count(page + i, 1); #endif /* CONFIG_MMU */ } /* * This page is about to be returned from the page allocator */ static void prep_new_page(struct page *page, int order) { if ( page_mapcount(page) || page->mapping != NULL || page_count(page) != 0 || (page->flags & ( 1 << PG_lru | 1 << PG_private | 1 << PG_locked | 1 << PG_active | 1 << PG_dirty | 1 << PG_reclaim | 1 << PG_slab | 1 << PG_swapcache | 1 << PG_writeback ))) bad_page(__FUNCTION__, page); page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 1 << PG_referenced | 1 << PG_arch_1 | 1 << PG_checked | 1 << PG_mappedtodisk); page->private = 0; set_page_refs(page, order); kernel_map_pages(page, 1 << order, 1); } /* * Do the hard work of removing an element from the buddy allocator. * Call me with the zone->lock already held. */ static struct page *__rmqueue(struct zone *zone, unsigned int order) { struct free_area * area; unsigned int current_order; struct page *page; for (current_order = order; current_order < MAX_ORDER; ++current_order) { area = zone->free_area + current_order; if (list_empty(&area->free_list)) continue; page = list_entry(area->free_list.next, struct page, lru); list_del(&page->lru); rmv_page_order(page); area->nr_free--; zone->free_pages -= 1UL << order; return expand(zone, page, order, current_order, area); } return NULL; } /* * Obtain a specified number of elements from the buddy allocator, all under * a single hold of the lock, for efficiency. Add them to the supplied list. * Returns the number of new pages which were placed at *list. */ static int rmqueue_bulk(struct zone *zone, unsigned int order, unsigned long count, struct list_head *list)