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