/* * 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/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/kernel.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/memory_hotplug.h>#include <linux/nodemask.h>#include <linux/vmalloc.h>#include <linux/mempolicy.h>#include <linux/stop_machine.h>#include <linux/sort.h>#include <linux/pfn.h>#include <linux/backing-dev.h>#include <linux/fault-inject.h> #include <asm/tlbflush.h>#include <asm/div64.h>#include "internal.h" /* * MCD - HACK: Find somewhere to initialize this EARLY, or make this * initializer cleaner */nodemask_t node_online_map __read_mostly = { { [0] = 1UL } };EXPORT_SYMBOL(node_online_map);nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL;EXPORT_SYMBOL(node_possible_map);unsigned long totalram_pages __read_mostly;unsigned long totalreserve_pages __read_mostly;long nr_swap_pages;int percpu_pagelist_fraction; static void __free_pages_ok(struct page *page, unsigned int order); /* * 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 * * TBD: should special case ZONE_DMA32 machines here - in those we normally * don't need any ZONE_NORMAL reservation */int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {#ifdef CONFIG_ZONE_DMA 256,#endif#ifdef CONFIG_ZONE_DMA32 256,#endif#ifdef CONFIG_HIGHMEM 32#endif}; EXPORT_SYMBOL(totalram_pages); static char * const zone_names[MAX_NR_ZONES] = {#ifdef CONFIG_ZONE_DMA "DMA",#endif#ifdef CONFIG_ZONE_DMA32 "DMA32",#endif "Normal",#ifdef CONFIG_HIGHMEM "HighMem"#endif}; int min_free_kbytes = 1024; unsigned long __meminitdata nr_kernel_pages;unsigned long __meminitdata nr_all_pages;static unsigned long __initdata dma_reserve; #ifdef CONFIG_ARCH_POPULATES_NODE_MAP /* * MAX_ACTIVE_REGIONS determines the maxmimum number of distinct * ranges of memory (RAM) that may be registered with add_active_range(). * Ranges passed to add_active_range() will be merged if possible * so the number of times add_active_range() can be called is * related to the number of nodes and the number of holes */ #ifdef CONFIG_MAX_ACTIVE_REGIONS /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */ #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS #else #if MAX_NUMNODES >= 32 /* If there can be many nodes, allow up to 50 holes per node */ #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50) #else /* By default, allow up to 256 distinct regions */ #define MAX_ACTIVE_REGIONS 256 #endif #endif struct node_active_region __initdata early_node_map[MAX_ACTIVE_REGIONS]; int __initdata nr_nodemap_entries; unsigned long __initdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES]; unsigned long __initdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];#ifdef CONFIG_MEMORY_HOTPLUG_RESERVE unsigned long __initdata node_boundary_start_pfn[MAX_NUMNODES]; unsigned long __initdata node_boundary_end_pfn[MAX_NUMNODES];#endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */#endif /* CONFIG_ARCH_POPULATES_NODE_MAP */ #ifdef CONFIG_DEBUG_VMstatic int page_outside_zone_boundaries(struct zone *zone, struct page *page){ int ret = 0; unsigned seq; unsigned long pfn = page_to_pfn(page); do { seq = zone_span_seqbegin(zone); if (pfn >= zone->zone_start_pfn + zone->spanned_pages) ret = 1; else if (pfn < zone->zone_start_pfn) ret = 1; } while (zone_span_seqretry(zone, seq)); return ret;} static int page_is_consistent(struct zone *zone, struct page *page){#ifdef CONFIG_HOLES_IN_ZONE if (!pfn_valid(page_to_pfn(page))) return 0;#endif if (zone != page_zone(page)) return 0; return 1;}/* * Temporary debugging check for pages not lying within a given zone. */static int bad_range(struct zone *zone, struct page *page){ if (page_outside_zone_boundaries(zone, page)) return 1; if (!page_is_consistent(zone, page)) return 1; return 0;}#elsestatic inline int bad_range(struct zone *zone, struct page *page){ return 0;}#endif static void bad_page(struct page *page){ printk(KERN_EMERG "Bad page state in process '%s'\n" KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n" KERN_EMERG "Trying to fix it up, but a reboot is needed\n" KERN_EMERG "Backtrace:\n", current->comm, page, (int)(2*sizeof(unsigned long)), (unsigned long)page->flags, page->mapping, page_mapcount(page), page_count(page)); dump_stack(); 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 | 1 << PG_buddy ); set_page_count(page, 0); reset_page_mapcount(page); page->mapping = NULL; add_taint(TAINT_BAD_PAGE);} /* * 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 ->lru.next holds the address of the compound page's * put_page() function. Its ->lru.prev holds the order of allocation. * This usage means that zero-order pages may not be compound. */ static void free_compound_page(struct page *page){ __free_pages_ok(page, (unsigned long)page[1].lru.prev);} static void prep_compound_page(struct page *page, unsigned long order){ int i; int nr_pages = 1 << order; set_compound_page_dtor(page, free_compound_page); page[1].lru.prev = (void *)order; for (i = 0; i < nr_pages; i++) { struct page *p = page + i; __SetPageCompound(p); set_page_private(p, (unsigned long)page); }} static void destroy_compound_page(struct page *page, unsigned long order){ int i; int nr_pages = 1 << order; if (unlikely((unsigned long)page[1].lru.prev != order)) bad_page(page); for (i = 0; i < nr_pages; i++) { struct page *p = page + i; if (unlikely(!PageCompound(p) | (page_private(p) != (unsigned long)page))) bad_page(page); __ClearPageCompound(p); }} static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags){ int i; VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM); /* * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO * and __GFP_HIGHMEM from hard or soft interrupt context. */ VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt()); for (i = 0; i < (1 << order); i++) clear_highpage(page + i);} /* * 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(page);} static inline void set_page_order(struct page *page, int order){ set_page_private(page, order); __SetPageBuddy(page);} static inline void rmv_page_order(struct page *page){ __ClearPageBuddy(page); set_page_private(page, 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 contiguous 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 not in a hole && * (b) the buddy is in the buddy system && * (c) a page and its buddy have the same order && * (d) a page and its buddy are in the same zone. * * For recording whether a page is in the buddy system, we use PG_buddy. * Setting, clearing, and testing PG_buddy is serialized by zone->lock. * * For recording page's order, we use page_private(page). */static inline int page_is_buddy(struct page *page, struct page *buddy, int order){#ifdef CONFIG_HOLES_IN_ZONE if (!pfn_valid(page_to_pfn(buddy))) return 0;#endif if (page_zone_id(page) != page_zone_id(buddy)) return 0; if (PageBuddy(buddy) && page_order(buddy) == order) { BUG_ON(page_count(buddy) != 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_buddy. Page's * order is recorded in page_private(page) 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_one_page(struct page *page, struct zone *zone, unsigned int order){ unsigned long page_idx; int order_size = 1 << order; if (unlikely(PageCompound(page))) destroy_compound_page(page, order); page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); VM_BUG_ON(page_idx & (order_size - 1)); VM_BUG_ON(bad_range(zone, page)); __mod_zone_page_state(zone, NR_FREE_PAGES, order_size); while (order < MAX_ORDER-1) { unsigned long combined_idx; struct free_area *area; struct page *buddy; buddy = __page_find_buddy(page, page_idx, order); if (!page_is_buddy(page, 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); combined_idx = __find_combined_index(page_idx, order); 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 int free_pages_check(struct page *page){ if (unlikely(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 | 1 << PG_reserved | 1 << PG_buddy )))) bad_page(page); if (PageDirty(page)) __ClearPageDirty(page); /* * For now, we report if PG_reserved was found set, but do not * clear it, and do not free the page. But we shall soon need * to do more, for when the ZERO_PAGE count wraps negative. */ return PageReserved(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. * * 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 void free_pages_bulk(struct zone *zone, int count, struct list_head *list, int order){ spin_lock(&zone->lock); zone->all_unreclaimable = 0; zone->pages_scanned = 0; while (count--) { struct page *page; VM_BUG_ON(list_empty(list)); page = list_entry(list->prev, struct page, lru); /* have to delete it as __free_one_page list manipulates */ list_del(&page->lru); __free_one_page(page, zone, order); } spin_unlock(&zone->lock);} static void free_one_page(struct zone *zone, struct page *page, int order){ spin_lock(&zone->lock); zone->all_unreclaimable = 0; zone->pages_scanned = 0; __free_one_page(page, zone, order); spin_unlock(&zone->lock);} static void __free_pages_ok(struct page *page, unsigned int order){ unsigned long flags; int i; int reserved = 0; for (i = 0 ; i < (1 << order) ; ++i) reserved += free_pages_check(page + i); if (reserved) return;Lines 1–500 of 3394. 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/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/kernel.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/memory_hotplug.h> #include <linux/nodemask.h> #include <linux/vmalloc.h> #include <linux/mempolicy.h> #include <linux/stop_machine.h> #include <linux/sort.h> #include <linux/pfn.h> #include <linux/backing-dev.h> #include <linux/fault-inject.h> #include <asm/tlbflush.h> #include <asm/div64.h> #include "internal.h" /* * MCD - HACK: Find somewhere to initialize this EARLY, or make this * initializer cleaner */ nodemask_t node_online_map __read_mostly = { { [0] = 1UL } }; EXPORT_SYMBOL(node_online_map); nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL; EXPORT_SYMBOL(node_possible_map); unsigned long totalram_pages __read_mostly; unsigned long totalreserve_pages __read_mostly; long nr_swap_pages; int percpu_pagelist_fraction; static void __free_pages_ok(struct page *page, unsigned int order); /* * 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 * * TBD: should special case ZONE_DMA32 machines here - in those we normally * don't need any ZONE_NORMAL reservation */ int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { #ifdef CONFIG_ZONE_DMA 256, #endif #ifdef CONFIG_ZONE_DMA32 256, #endif #ifdef CONFIG_HIGHMEM 32 #endif }; EXPORT_SYMBOL(totalram_pages); static char * const zone_names[MAX_NR_ZONES] = { #ifdef CONFIG_ZONE_DMA "DMA", #endif #ifdef CONFIG_ZONE_DMA32 "DMA32", #endif "Normal", #ifdef CONFIG_HIGHMEM "HighMem" #endif }; int min_free_kbytes = 1024; unsigned long __meminitdata nr_kernel_pages; unsigned long __meminitdata nr_all_pages; static unsigned long __initdata dma_reserve; #ifdef CONFIG_ARCH_POPULATES_NODE_MAP /* * MAX_ACTIVE_REGIONS determines the maxmimum number of distinct * ranges of memory (RAM) that may be registered with add_active_range(). * Ranges passed to add_active_range() will be merged if possible * so the number of times add_active_range() can be called is * related to the number of nodes and the number of holes */ #ifdef CONFIG_MAX_ACTIVE_REGIONS /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */ #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS #else #if MAX_NUMNODES >= 32 /* If there can be many nodes, allow up to 50 holes per node */ #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50) #else /* By default, allow up to 256 distinct regions */ #define MAX_ACTIVE_REGIONS 256 #endif #endif struct node_active_region __initdata early_node_map[MAX_ACTIVE_REGIONS]; int __initdata nr_nodemap_entries; unsigned long __initdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES]; unsigned long __initdata arch_zone_highest_possible_pfn[MAX_NR_ZONES]; #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE unsigned long __initdata node_boundary_start_pfn[MAX_NUMNODES]; unsigned long __initdata node_boundary_end_pfn[MAX_NUMNODES]; #endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */ #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */ #ifdef CONFIG_DEBUG_VM static int page_outside_zone_boundaries(struct zone *zone, struct page *page) { int ret = 0; unsigned seq; unsigned long pfn = page_to_pfn(page); do { seq = zone_span_seqbegin(zone); if (pfn >= zone->zone_start_pfn + zone->spanned_pages) ret = 1; else if (pfn < zone->zone_start_pfn) ret = 1; } while (zone_span_seqretry(zone, seq)); return ret; } static int page_is_consistent(struct zone *zone, struct page *page) { #ifdef CONFIG_HOLES_IN_ZONE if (!pfn_valid(page_to_pfn(page))) return 0; #endif if (zone != page_zone(page)) return 0; return 1; } /* * Temporary debugging check for pages not lying within a given zone. */ static int bad_range(struct zone *zone, struct page *page) { if (page_outside_zone_boundaries(zone, page)) return 1; if (!page_is_consistent(zone, page)) return 1; return 0; } #else static inline int bad_range(struct zone *zone, struct page *page) { return 0; } #endif static void bad_page(struct page *page) { printk(KERN_EMERG "Bad page state in process '%s'\n" KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n" KERN_EMERG "Trying to fix it up, but a reboot is needed\n" KERN_EMERG "Backtrace:\n", current->comm, page, (int)(2*sizeof(unsigned long)), (unsigned long)page->flags, page->mapping, page_mapcount(page), page_count(page)); dump_stack(); 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 | 1 << PG_buddy ); set_page_count(page, 0); reset_page_mapcount(page); page->mapping = NULL; add_taint(TAINT_BAD_PAGE); } /* * 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 ->lru.next holds the address of the compound page's * put_page() function. Its ->lru.prev holds the order of allocation. * This usage means that zero-order pages may not be compound. */ static void free_compound_page(struct page *page) { __free_pages_ok(page, (unsigned long)page[1].lru.prev); } static void prep_compound_page(struct page *page, unsigned long order) { int i; int nr_pages = 1 << order; set_compound_page_dtor(page, free_compound_page); page[1].lru.prev = (void *)order; for (i = 0; i < nr_pages; i++) { struct page *p = page + i; __SetPageCompound(p); set_page_private(p, (unsigned long)page); } } static void destroy_compound_page(struct page *page, unsigned long order) { int i; int nr_pages = 1 << order; if (unlikely((unsigned long)page[1].lru.prev != order)) bad_page(page); for (i = 0; i < nr_pages; i++) { struct page *p = page + i; if (unlikely(!PageCompound(p) | (page_private(p) != (unsigned long)page))) bad_page(page); __ClearPageCompound(p); } } static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags) { int i; VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM); /* * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO * and __GFP_HIGHMEM from hard or soft interrupt context. */ VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt()); for (i = 0; i < (1 << order); i++) clear_highpage(page + i); } /* * 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(page); } static inline void set_page_order(struct page *page, int order) { set_page_private(page, order); __SetPageBuddy(page); } static inline void rmv_page_order(struct page *page) { __ClearPageBuddy(page); set_page_private(page, 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 contiguous 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 not in a hole && * (b) the buddy is in the buddy system && * (c) a page and its buddy have the same order && * (d) a page and its buddy are in the same zone. * * For recording whether a page is in the buddy system, we use PG_buddy. * Setting, clearing, and testing PG_buddy is serialized by zone->lock. * * For recording page's order, we use page_private(page). */ static inline int page_is_buddy(struct page *page, struct page *buddy, int order) { #ifdef CONFIG_HOLES_IN_ZONE if (!pfn_valid(page_to_pfn(buddy))) return 0; #endif if (page_zone_id(page) != page_zone_id(buddy)) return 0; if (PageBuddy(buddy) && page_order(buddy) == order) { BUG_ON(page_count(buddy) != 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_buddy. Page's * order is recorded in page_private(page) 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_one_page(struct page *page, struct zone *zone, unsigned int order) { unsigned long page_idx; int order_size = 1 << order; if (unlikely(PageCompound(page))) destroy_compound_page(page, order); page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1); VM_BUG_ON(page_idx & (order_size - 1)); VM_BUG_ON(bad_range(zone, page)); __mod_zone_page_state(zone, NR_FREE_PAGES, order_size); while (order < MAX_ORDER-1) { unsigned long combined_idx; struct free_area *area; struct page *buddy; buddy = __page_find_buddy(page, page_idx, order); if (!page_is_buddy(page, 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); combined_idx = __find_combined_index(page_idx, order); 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 int free_pages_check(struct page *page) { if (unlikely(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 | 1 << PG_reserved | 1 << PG_buddy )))) bad_page(page); if (PageDirty(page)) __ClearPageDirty(page); /* * For now, we report if PG_reserved was found set, but do not * clear it, and do not free the page. But we shall soon need * to do more, for when the ZERO_PAGE count wraps negative. */ return PageReserved(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. * * 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 void free_pages_bulk(struct zone *zone, int count, struct list_head *list, int order) { spin_lock(&zone->lock); zone->all_unreclaimable = 0; zone->pages_scanned = 0; while (count--) { struct page *page; VM_BUG_ON(list_empty(list)); page = list_entry(list->prev, struct page, lru); /* have to delete it as __free_one_page list manipulates */ list_del(&page->lru); __free_one_page(page, zone, order); } spin_unlock(&zone->lock); } static void free_one_page(struct zone *zone, struct page *page, int order) { spin_lock(&zone->lock); zone->all_unreclaimable = 0; zone->pages_scanned = 0; __free_one_page(page, zone, order); spin_unlock(&zone->lock); } static void __free_pages_ok(struct page *page, unsigned int order) { unsigned long flags; int i; int reserved = 0; for (i = 0 ; i < (1 << order) ; ++i) reserved += free_pages_check(page + i); if (reserved) return;