2 * Copyright (c) 1996 Paul Mackerras <paulus@cs.anu.edu.au>
3 * Changes to accommodate Power Macintoshes.
4 * Cort Dougan <cort@cs.nmt.edu>
6 * Grant Erickson <grant@lcse.umn.edu>
7 * General rework and split from mm/init.c.
9 * Module name: mem_pieces.c
12 * Routines and data structures for manipulating and representing
13 * phyiscal memory extents (i.e. address/length pairs).
17 #include <linux/kernel.h>
18 #include <linux/stddef.h>
19 #include <linux/init.h>
22 #include "mem_pieces.h"
24 extern struct mem_pieces phys_avail;
26 static void mem_pieces_print(struct mem_pieces *);
29 * Scan a region for a piece of a given size with the required alignment.
32 mem_pieces_find(unsigned int size, unsigned int align)
36 struct mem_pieces *mp = &phys_avail;
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;
43 mem_pieces_remove(mp, a, size, 1);
44 return (void *) __va(a);
47 panic("Couldn't find %u bytes at %u alignment\n", size, align);
53 * Remove some memory from an array of pieces
56 mem_pieces_remove(struct mem_pieces *mp, unsigned int start, unsigned int size,
60 unsigned int end, rs, re;
61 struct reg_property *rp;
64 for (i = 0, rp = mp->regions; i < mp->n_regions; ++i, ++rp) {
65 if (end > rp->address && start < rp->address + rp->size)
68 if (i >= mp->n_regions) {
70 printk("mem_pieces_remove: [%x,%x) not in any region\n",
74 for (; i < mp->n_regions && end > rp->address; ++i, ++rp) {
77 if (must_exist && (start < rs || end > re)) {
78 printk("mem_pieces_remove: bad overlap [%x,%x) with",
84 rp->size = start - rs;
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];
93 rp[1].size = re - end;
100 /* need to delete this entry */
101 for (j = i; j < mp->n_regions - 1; ++j)
102 mp->regions[j] = mp->regions[j+1];
112 mem_pieces_print(struct mem_pieces *mp)
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);
123 mem_pieces_sort(struct mem_pieces *mp)
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)
134 mp->regions[j+1] = mp->regions[j];
136 mp->regions[j+1].address = a;
137 mp->regions[j+1].size = s;
142 mem_pieces_coalesce(struct mem_pieces *mp)
144 unsigned long a, s, ns;
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;
157 mp->regions[d].address = a;
158 mp->regions[d].size = s;