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/kernel.h> 18#include <linux/stddef.h> 19#include <linux/init.h> 20#include <asm/page.h> 21 22#include "mem_pieces.h" 23 24extern struct mem_pieces phys_avail; 25 26static void mem_pieces_print(struct mem_pieces *); 27 28/* 29 * Scan a region for a piece of a given size with the required alignment. 30 */ 31void __init * 32mem_pieces_find(unsigned int size, unsigned int align) 33{ 34 int i; 35 unsigned a, e; 36 struct mem_pieces *mp = &phys_avail; 37 38 for (i = 0; i < mp->n_regions; ++i) { 39 a = mp->regions[i].address; 40 e = a + mp->regions[i].size; 41 a = (a + align - 1) & -align; 42 if (a + size <= e) { 43 mem_pieces_remove(mp, a, size, 1); 44 return (void *) __va(a); 45 } 46 } 47 panic("Couldn't find %u bytes at %u alignment\n", size, align); 48 49 return NULL; 50} 51 52/* 53 * Remove some memory from an array of pieces 54 */ 55void __init 56mem_pieces_remove(struct mem_pieces *mp, unsigned int start, unsigned int size, 57 int must_exist) 58{ 59 int i, j; 60 unsigned int end, rs, re; 61 struct reg_property *rp; 62 63 end = start + size; 64 for (i = 0, rp = mp->regions; i < mp->n_regions; ++i, ++rp) { 65 if (end > rp->address && start < rp->address + rp->size) 66 break; 67 } 68 if (i >= mp->n_regions) { 69 if (must_exist) 70 printk("mem_pieces_remove: [%x,%x) not in any region\n", 71 start, end); 72 return; 73 } 74 for (; i < mp->n_regions && end > rp->address; ++i, ++rp) { 75 rs = rp->address; 76 re = rs + rp->size; 77 if (must_exist && (start < rs || end > re)) { 78 printk("mem_pieces_remove: bad overlap [%x,%x) with", 79 start, end); 80 mem_pieces_print(mp); 81 must_exist = 0; 82 } 83 if (start > rs) { 84 rp->size = start - rs; 85 if (end < re) { 86 /* need to split this entry */ 87 if (mp->n_regions >= MEM_PIECES_MAX) 88 panic("eek... mem_pieces overflow"); 89 for (j = mp->n_regions; j > i + 1; --j) 90 mp->regions[j] = mp->regions[j-1]; 91 ++mp->n_regions; 92 rp[1].address = end; 93 rp[1].size = re - end; 94 } 95 } else { 96 if (end < re) { 97 rp->address = end; 98 rp->size = re - end; 99 } else { 100 /* need to delete this entry */ 101 for (j = i; j < mp->n_regions - 1; ++j) 102 mp->regions[j] = mp->regions[j+1]; 103 --mp->n_regions; 104 --i; 105 --rp; 106 } 107 } 108 } 109} 110 111static void __init 112mem_pieces_print(struct mem_pieces *mp) 113{ 114 int i; 115 116 for (i = 0; i < mp->n_regions; ++i) 117 printk(" [%x, %x)", mp->regions[i].address, 118 mp->regions[i].address + mp->regions[i].size); 119 printk("\n"); 120} 121 122void __init 123mem_pieces_sort(struct mem_pieces *mp) 124{ 125 unsigned long a, s; 126 int i, j; 127 128 for (i = 1; i < mp->n_regions; ++i) { 129 a = mp->regions[i].address; 130 s = mp->regions[i].size; 131 for (j = i - 1; j >= 0; --j) { 132 if (a >= mp->regions[j].address) 133 break; 134 mp->regions[j+1] = mp->regions[j]; 135 } 136 mp->regions[j+1].address = a; 137 mp->regions[j+1].size = s; 138 } 139} 140 141void __init 142mem_pieces_coalesce(struct mem_pieces *mp) 143{ 144 unsigned long a, s, ns; 145 int i, j, d; 146 147 d = 0; 148 for (i = 0; i < mp->n_regions; i = j) { 149 a = mp->regions[i].address; 150 s = mp->regions[i].size; 151 for (j = i + 1; j < mp->n_regions 152 && mp->regions[j].address - a <= s; ++j) { 153 ns = mp->regions[j].address + mp->regions[j].size - a; 154 if (ns > s) 155 s = ns; 156 } 157 mp->regions[d].address = a; 158 mp->regions[d].size = s; 159 ++d; 160 } 161 mp->n_regions = d; 162} 163