cp/mm/buddy.c

   1 /*
   2  * (C) Copyright 2007-2010  Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
   3  *
   4  * This file is released under the GPLv2.  See the COPYING file for more
   5  * details.
   6  */
   7
   8 #include <list.h>
   9 #include <page.h>
  10 #include <mm.h>
  11 #include <buddy.h>
  12 #include <spinlock.h>
  13
  14 /*
  15  * Lists of free page ranges
  16  */
  17 static struct list_head orders_normal[64-PAGE_SHIFT];
  18 static struct list_head orders_low[31-PAGE_SHIFT];
  19
  20 static spinlock_t orders_lock = SPIN_LOCK_UNLOCKED;
  21
  22 static void __init_buddy_alloc(u64 base, int pages, int max_order,
  23                                struct list_head *orders)
  24 {
  25         int order;
  26         struct page *p;
  27
  28         for(order=0; order < max_order; order++) {
  29                 INIT_LIST_HEAD(&orders[order]);
  30
  31                 if (pages & (1 << order)) {
  32                         p = addr_to_page((void*) base);
  33
  34                         list_add(&p->buddy, &orders[order]);
  35
  36                         base += (PAGE_SIZE << order);
  37                 }
  38         }
  39 }
  40
  41 /*
  42  * Initialize the buddy allocator. This is rather simple, and the only
  43  * complication is that we must keep track of storage below 2GB separately
  44  * since some IO related structures can address only the first 2GB. *sigh*
  45  */
  46 void init_buddy_alloc(u64 start)
  47 {
  48         u64 normal_pages;
  49         u64 low_pages;
  50
  51         if (memsize > 2UL*1024*1024*1024) {
  52                 /* There are more than 2GB of storage */
  53                 low_pages = (2UL*1024*1024*1024 - start) >> PAGE_SHIFT;
  54                 normal_pages = (memsize - start) >> PAGE_SHIFT;
  55                 normal_pages -= low_pages;
  56         } else {
  57                 /* All the storage is under the 2GB mark */
  58                 low_pages = (memsize - start) >> PAGE_SHIFT;
  59                 normal_pages = 0;
  60         }
  61
  62         /* let's add all the free low storage to the lists */
  63         __init_buddy_alloc(start, low_pages, ZONE_LOW_MAX_ORDER, orders_low);
  64
  65         /* now, let's add all the free storage above 2GB */
  66         __init_buddy_alloc(2UL*1024*1024*1024, normal_pages, ZONE_NORMAL_MAX_ORDER,
  67                            orders_normal);
  68 }
  69
  70 static struct page *__do_alloc_pages(int order, struct list_head *orders)
  71 {
  72         struct page *page;
  73
  74         if (!list_empty(&orders[order])) {
  75                 page = list_first_entry(&orders[order], struct page, buddy);
  76
  77                 list_del(&page->buddy);
  78
  79                 return page;
  80         }
  81
  82         return NULL;
  83 }
  84
  85 static struct page *__alloc_pages(int order, int type)
  86 {
  87         struct page *p;
  88
  89         /* Do we have to use ZONE_LOW? */
  90         if (type == ZONE_LOW)
  91                 goto zone_low;
  92
  93         p = __do_alloc_pages(order, orders_normal);
  94         if (p)
  95                 return p;
  96
  97         /* If there was no ZONE_NORMAL page, let's try ZONE_LOW */
  98
  99 zone_low:
 100         return __do_alloc_pages(order, orders_low);
 101 }
 102
 103 /*
 104  * Split a given (actual) order allocation into an allocation of wanted
 105  * order, and return the rest of pages to the unused lists
 106  *
 107  * E.g.,
 108  *
 109  * pages (base):
 110  *
 111  * +---+---+---+---+---+---+---+---+
 112  * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
 113  * +---+---+---+---+---+---+---+---+
 114  *
 115  * actual = 3
 116  * wanted = 1
 117  *
 118  * return order 2 range back to free pool:
 119  *
 120  *                 +---+---+---+---+
 121  *                 | 4 | 5 | 6 | 7 |
 122  *                 +---+---+---+---+
 123  *
 124  * return order 1 range back to free pool:
 125  *
 126  *         +---+---+
 127  *         | 2 | 3 |
 128  *         +---+---+
 129  *
 130  * The End. Now, pages 2-7 are back in the free pool, and pages 0&1 are an
 131  * order 1 allocation.
 132  *
 133  */
 134 static void __chip_pages(struct page *base, int actual, int wanted)
 135 {
 136         struct page *p;
 137         struct list_head *orders;
 138
 139         orders = (IS_LOW_ZONE(base) ? orders_low : orders_normal);
 140
 141         for(; actual > wanted; actual--) {
 142                 p = &base[1 << (actual-1)];
 143                 list_add(&p->buddy, &orders[actual-1]);
 144         }
 145 }
 146
 147 /**
 148  * alloc_pages - allocate a series of consecutive pages
 149  * @order:      allocate 2^order consecutive pages
 150  * @type:       type of pages (<2GB, or anywhere)
 151  */
 152 struct page *alloc_pages(int order, int type)
 153 {
 154         struct page *page;
 155         int gord;
 156         unsigned long mask;
 157         int max_order;
 158
 159         spin_lock_intsave(&orders_lock, &mask);
 160
 161         /* easy way */
 162         page = __alloc_pages(order, type);
 163         if (page)
 164                 goto out;
 165
 166         /*
 167          * There is no page-range of the given order, let's try to find the
 168          * smallest one larger and split it
 169          */
 170
 171         max_order = (type == ZONE_LOW ?
 172                         ZONE_LOW_MAX_ORDER : ZONE_NORMAL_MAX_ORDER);
 173
 174         for(gord=order+1; gord < max_order; gord++) {
 175                 if (gord >= max_order)
 176                         break;
 177
 178                 page = __alloc_pages(gord, type);
 179                 if (!page)
 180                         continue;
 181
 182                 __chip_pages(page, gord, order);
 183
 184                 goto out;
 185         }
 186
 187         /* alright, totally out of memory */
 188         page = NULL;
 189
 190 out:
 191         spin_unlock_intrestore(&orders_lock, mask);
 192
 193         return page;
 194 }
 195
 196 void free_pages(void *ptr, int order)
 197 {
 198         struct page *base = addr_to_page(ptr);
 199         unsigned long mask;
 200         struct list_head *orders;
 201
 202         orders = IS_LOW_ZONE(base) ? orders_low : orders_normal;
 203
 204         spin_lock_intsave(&orders_lock, &mask);
 205         list_add(&base->buddy, &orders[order]);
 206         spin_unlock_intrestore(&orders_lock, mask);
 207
 208         /*
 209          * TODO: a more complex thing we could try is to coallesce adjecent
 210          * page ranges into one higher order one (defrag)
 211          */
 212 }