[PATCH] powerpc: Merge asm-ppc*/dma.h
[linux-2.6] / arch / ppc / mm / mem_pieces.c
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 }