Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright (c) 1996 Paul Mackerras <paulus@cs.anu.edu.au> |
| 3 | * Changes to accommodate Power Macintoshes. |
| 4 | * Cort Dougan <cort@cs.nmt.edu> |
| 5 | * Rewrites. |
| 6 | * Grant Erickson <grant@lcse.umn.edu> |
| 7 | * General rework and split from mm/init.c. |
| 8 | * |
| 9 | * Module name: mem_pieces.c |
| 10 | * |
| 11 | * Description: |
| 12 | * Routines and data structures for manipulating and representing |
| 13 | * phyiscal memory extents (i.e. address/length pairs). |
| 14 | * |
| 15 | */ |
| 16 | |
| 17 | #include <linux/config.h> |
| 18 | #include <linux/kernel.h> |
| 19 | #include <linux/stddef.h> |
| 20 | #include <linux/init.h> |
| 21 | #include <asm/page.h> |
| 22 | |
| 23 | #include "mem_pieces.h" |
| 24 | |
| 25 | extern struct mem_pieces phys_avail; |
| 26 | |
| 27 | static void mem_pieces_print(struct mem_pieces *); |
| 28 | |
| 29 | /* |
| 30 | * Scan a region for a piece of a given size with the required alignment. |
| 31 | */ |
| 32 | void __init * |
| 33 | mem_pieces_find(unsigned int size, unsigned int align) |
| 34 | { |
| 35 | int i; |
| 36 | unsigned a, e; |
| 37 | struct mem_pieces *mp = &phys_avail; |
| 38 | |
| 39 | for (i = 0; i < mp->n_regions; ++i) { |
| 40 | a = mp->regions[i].address; |
| 41 | e = a + mp->regions[i].size; |
| 42 | a = (a + align - 1) & -align; |
| 43 | if (a + size <= e) { |
| 44 | mem_pieces_remove(mp, a, size, 1); |
| 45 | return (void *) __va(a); |
| 46 | } |
| 47 | } |
| 48 | panic("Couldn't find %u bytes at %u alignment\n", size, align); |
| 49 | |
| 50 | return NULL; |
| 51 | } |
| 52 | |
| 53 | /* |
| 54 | * Remove some memory from an array of pieces |
| 55 | */ |
| 56 | void __init |
| 57 | mem_pieces_remove(struct mem_pieces *mp, unsigned int start, unsigned int size, |
| 58 | int must_exist) |
| 59 | { |
| 60 | int i, j; |
| 61 | unsigned int end, rs, re; |
| 62 | struct reg_property *rp; |
| 63 | |
| 64 | end = start + size; |
| 65 | for (i = 0, rp = mp->regions; i < mp->n_regions; ++i, ++rp) { |
| 66 | if (end > rp->address && start < rp->address + rp->size) |
| 67 | break; |
| 68 | } |
| 69 | if (i >= mp->n_regions) { |
| 70 | if (must_exist) |
| 71 | printk("mem_pieces_remove: [%x,%x) not in any region\n", |
| 72 | start, end); |
| 73 | return; |
| 74 | } |
| 75 | for (; i < mp->n_regions && end > rp->address; ++i, ++rp) { |
| 76 | rs = rp->address; |
| 77 | re = rs + rp->size; |
| 78 | if (must_exist && (start < rs || end > re)) { |
| 79 | printk("mem_pieces_remove: bad overlap [%x,%x) with", |
| 80 | start, end); |
| 81 | mem_pieces_print(mp); |
| 82 | must_exist = 0; |
| 83 | } |
| 84 | if (start > rs) { |
| 85 | rp->size = start - rs; |
| 86 | if (end < re) { |
| 87 | /* need to split this entry */ |
| 88 | if (mp->n_regions >= MEM_PIECES_MAX) |
| 89 | panic("eek... mem_pieces overflow"); |
| 90 | for (j = mp->n_regions; j > i + 1; --j) |
| 91 | mp->regions[j] = mp->regions[j-1]; |
| 92 | ++mp->n_regions; |
| 93 | rp[1].address = end; |
| 94 | rp[1].size = re - end; |
| 95 | } |
| 96 | } else { |
| 97 | if (end < re) { |
| 98 | rp->address = end; |
| 99 | rp->size = re - end; |
| 100 | } else { |
| 101 | /* need to delete this entry */ |
| 102 | for (j = i; j < mp->n_regions - 1; ++j) |
| 103 | mp->regions[j] = mp->regions[j+1]; |
| 104 | --mp->n_regions; |
| 105 | --i; |
| 106 | --rp; |
| 107 | } |
| 108 | } |
| 109 | } |
| 110 | } |
| 111 | |
| 112 | static void __init |
| 113 | mem_pieces_print(struct mem_pieces *mp) |
| 114 | { |
| 115 | int i; |
| 116 | |
| 117 | for (i = 0; i < mp->n_regions; ++i) |
| 118 | printk(" [%x, %x)", mp->regions[i].address, |
| 119 | mp->regions[i].address + mp->regions[i].size); |
| 120 | printk("\n"); |
| 121 | } |
| 122 | |
| 123 | void __init |
| 124 | mem_pieces_sort(struct mem_pieces *mp) |
| 125 | { |
| 126 | unsigned long a, s; |
| 127 | int i, j; |
| 128 | |
| 129 | for (i = 1; i < mp->n_regions; ++i) { |
| 130 | a = mp->regions[i].address; |
| 131 | s = mp->regions[i].size; |
| 132 | for (j = i - 1; j >= 0; --j) { |
| 133 | if (a >= mp->regions[j].address) |
| 134 | break; |
| 135 | mp->regions[j+1] = mp->regions[j]; |
| 136 | } |
| 137 | mp->regions[j+1].address = a; |
| 138 | mp->regions[j+1].size = s; |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | void __init |
| 143 | mem_pieces_coalesce(struct mem_pieces *mp) |
| 144 | { |
| 145 | unsigned long a, s, ns; |
| 146 | int i, j, d; |
| 147 | |
| 148 | d = 0; |
| 149 | for (i = 0; i < mp->n_regions; i = j) { |
| 150 | a = mp->regions[i].address; |
| 151 | s = mp->regions[i].size; |
| 152 | for (j = i + 1; j < mp->n_regions |
| 153 | && mp->regions[j].address - a <= s; ++j) { |
| 154 | ns = mp->regions[j].address + mp->regions[j].size - a; |
| 155 | if (ns > s) |
| 156 | s = ns; |
| 157 | } |
| 158 | mp->regions[d].address = a; |
| 159 | mp->regions[d].size = s; |
| 160 | ++d; |
| 161 | } |
| 162 | mp->n_regions = d; |
| 163 | } |