Merge master.kernel.org:/pub/scm/linux/kernel/git/davej/x86
[linux-2.6] / arch / powerpc / mm / imalloc.c
1 /*
2  * c 2001 PPC 64 Team, IBM Corp
3  * 
4  *      This program is free software; you can redistribute it and/or
5  *      modify it under the terms of the GNU General Public License
6  *      as published by the Free Software Foundation; either version
7  *      2 of the License, or (at your option) any later version.
8  */
9
10 #include <linux/slab.h>
11 #include <linux/vmalloc.h>
12
13 #include <asm/uaccess.h>
14 #include <asm/pgalloc.h>
15 #include <asm/pgtable.h>
16 #include <asm/semaphore.h>
17 #include <asm/cacheflush.h>
18
19 #include "mmu_decl.h"
20
21 static DECLARE_MUTEX(imlist_sem);
22 struct vm_struct * imlist = NULL;
23
24 static int get_free_im_addr(unsigned long size, unsigned long *im_addr)
25 {
26         unsigned long addr;
27         struct vm_struct **p, *tmp;
28
29         addr = ioremap_bot;
30         for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
31                 if (size + addr < (unsigned long) tmp->addr)
32                         break;
33                 if ((unsigned long)tmp->addr >= ioremap_bot)
34                         addr = tmp->size + (unsigned long) tmp->addr;
35                 if (addr >= IMALLOC_END-size)
36                         return 1;
37         }
38         *im_addr = addr;
39
40         return 0;
41 }
42
43 /* Return whether the region described by v_addr and size is a subset
44  * of the region described by parent
45  */
46 static inline int im_region_is_subset(unsigned long v_addr, unsigned long size,
47                         struct vm_struct *parent)
48 {
49         return (int) (v_addr >= (unsigned long) parent->addr &&
50                       v_addr < (unsigned long) parent->addr + parent->size &&
51                       size < parent->size);
52 }
53
54 /* Return whether the region described by v_addr and size is a superset
55  * of the region described by child
56  */
57 static int im_region_is_superset(unsigned long v_addr, unsigned long size,
58                 struct vm_struct *child)
59 {
60         struct vm_struct parent;
61
62         parent.addr = (void *) v_addr;
63         parent.size = size;
64
65         return im_region_is_subset((unsigned long) child->addr, child->size,
66                         &parent);
67 }
68
69 /* Return whether the region described by v_addr and size overlaps
70  * the region described by vm.  Overlapping regions meet the
71  * following conditions:
72  * 1) The regions share some part of the address space
73  * 2) The regions aren't identical
74  * 3) Neither region is a subset of the other
75  */
76 static int im_region_overlaps(unsigned long v_addr, unsigned long size,
77                      struct vm_struct *vm)
78 {
79         if (im_region_is_superset(v_addr, size, vm))
80                 return 0;
81
82         return (v_addr + size > (unsigned long) vm->addr + vm->size &&
83                 v_addr < (unsigned long) vm->addr + vm->size) ||
84                (v_addr < (unsigned long) vm->addr &&
85                 v_addr + size > (unsigned long) vm->addr);
86 }
87
88 /* Determine imalloc status of region described by v_addr and size.
89  * Can return one of the following:
90  * IM_REGION_UNUSED   -  Entire region is unallocated in imalloc space.
91  * IM_REGION_SUBSET -    Region is a subset of a region that is already
92  *                       allocated in imalloc space.
93  *                       vm will be assigned to a ptr to the parent region.
94  * IM_REGION_EXISTS -    Exact region already allocated in imalloc space.
95  *                       vm will be assigned to a ptr to the existing imlist
96  *                       member.
97  * IM_REGION_OVERLAPS -  Region overlaps an allocated region in imalloc space.
98  * IM_REGION_SUPERSET -  Region is a superset of a region that is already
99  *                       allocated in imalloc space.
100  */
101 static int im_region_status(unsigned long v_addr, unsigned long size,
102                     struct vm_struct **vm)
103 {
104         struct vm_struct *tmp;
105
106         for (tmp = imlist; tmp; tmp = tmp->next)
107                 if (v_addr < (unsigned long) tmp->addr + tmp->size)
108                         break;
109
110         *vm = NULL;
111         if (tmp) {
112                 if (im_region_overlaps(v_addr, size, tmp))
113                         return IM_REGION_OVERLAP;
114
115                 *vm = tmp;
116                 if (im_region_is_subset(v_addr, size, tmp)) {
117                         /* Return with tmp pointing to superset */
118                         return IM_REGION_SUBSET;
119                 }
120                 if (im_region_is_superset(v_addr, size, tmp)) {
121                         /* Return with tmp pointing to first subset */
122                         return IM_REGION_SUPERSET;
123                 }
124                 else if (v_addr == (unsigned long) tmp->addr &&
125                          size == tmp->size) {
126                         /* Return with tmp pointing to exact region */
127                         return IM_REGION_EXISTS;
128                 }
129         }
130
131         return IM_REGION_UNUSED;
132 }
133
134 static struct vm_struct * split_im_region(unsigned long v_addr, 
135                 unsigned long size, struct vm_struct *parent)
136 {
137         struct vm_struct *vm1 = NULL;
138         struct vm_struct *vm2 = NULL;
139         struct vm_struct *new_vm = NULL;
140         
141         vm1 = (struct vm_struct *) kmalloc(sizeof(*vm1), GFP_KERNEL);
142         if (vm1 == NULL) {
143                 printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
144                 return NULL;
145         }
146
147         if (v_addr == (unsigned long) parent->addr) {
148                 /* Use existing parent vm_struct to represent child, allocate
149                  * new one for the remainder of parent range
150                  */
151                 vm1->size = parent->size - size;
152                 vm1->addr = (void *) (v_addr + size);
153                 vm1->next = parent->next;
154
155                 parent->size = size;
156                 parent->next = vm1;
157                 new_vm = parent;
158         } else if (v_addr + size == (unsigned long) parent->addr + 
159                         parent->size) {
160                 /* Allocate new vm_struct to represent child, use existing
161                  * parent one for remainder of parent range
162                  */
163                 vm1->size = size;
164                 vm1->addr = (void *) v_addr;
165                 vm1->next = parent->next;
166                 new_vm = vm1;
167
168                 parent->size -= size;
169                 parent->next = vm1;
170         } else {
171                 /* Allocate two new vm_structs for the new child and 
172                  * uppermost remainder, and use existing parent one for the
173                  * lower remainder of parent range
174                  */
175                 vm2 = (struct vm_struct *) kmalloc(sizeof(*vm2), GFP_KERNEL);
176                 if (vm2 == NULL) {
177                         printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
178                         kfree(vm1);
179                         return NULL;
180                 }
181
182                 vm1->size = size;
183                 vm1->addr = (void *) v_addr;
184                 vm1->next = vm2;
185                 new_vm = vm1;
186
187                 vm2->size = ((unsigned long) parent->addr + parent->size) - 
188                                 (v_addr + size);
189                 vm2->addr = (void *) v_addr + size;
190                 vm2->next = parent->next;
191
192                 parent->size = v_addr - (unsigned long) parent->addr;
193                 parent->next = vm1;
194         }
195
196         return new_vm;
197 }
198
199 static struct vm_struct * __add_new_im_area(unsigned long req_addr, 
200                                             unsigned long size)
201 {
202         struct vm_struct **p, *tmp, *area;
203                 
204         for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
205                 if (req_addr + size <= (unsigned long)tmp->addr)
206                         break;
207         }
208         
209         area = (struct vm_struct *) kmalloc(sizeof(*area), GFP_KERNEL);
210         if (!area)
211                 return NULL;
212         area->flags = 0;
213         area->addr = (void *)req_addr;
214         area->size = size;
215         area->next = *p;
216         *p = area;
217
218         return area;
219 }
220
221 static struct vm_struct * __im_get_area(unsigned long req_addr, 
222                                         unsigned long size,
223                                         int criteria)
224 {
225         struct vm_struct *tmp;
226         int status;
227
228         status = im_region_status(req_addr, size, &tmp);
229         if ((criteria & status) == 0) {
230                 return NULL;
231         }
232         
233         switch (status) {
234         case IM_REGION_UNUSED:
235                 tmp = __add_new_im_area(req_addr, size);
236                 break;
237         case IM_REGION_SUBSET:
238                 tmp = split_im_region(req_addr, size, tmp);
239                 break;
240         case IM_REGION_EXISTS:
241                 /* Return requested region */
242                 break;
243         case IM_REGION_SUPERSET:
244                 /* Return first existing subset of requested region */
245                 break;
246         default:
247                 printk(KERN_ERR "%s() unexpected imalloc region status\n",
248                                 __FUNCTION__);
249                 tmp = NULL;
250         }
251
252         return tmp;
253 }
254
255 struct vm_struct * im_get_free_area(unsigned long size)
256 {
257         struct vm_struct *area;
258         unsigned long addr;
259         
260         down(&imlist_sem);
261         if (get_free_im_addr(size, &addr)) {
262                 printk(KERN_ERR "%s() cannot obtain addr for size 0x%lx\n",
263                                 __FUNCTION__, size);
264                 area = NULL;
265                 goto next_im_done;
266         }
267
268         area = __im_get_area(addr, size, IM_REGION_UNUSED);
269         if (area == NULL) {
270                 printk(KERN_ERR 
271                        "%s() cannot obtain area for addr 0x%lx size 0x%lx\n",
272                         __FUNCTION__, addr, size);
273         }
274 next_im_done:
275         up(&imlist_sem);
276         return area;
277 }
278
279 struct vm_struct * im_get_area(unsigned long v_addr, unsigned long size,
280                 int criteria)
281 {
282         struct vm_struct *area;
283
284         down(&imlist_sem);
285         area = __im_get_area(v_addr, size, criteria);
286         up(&imlist_sem);
287         return area;
288 }
289
290 void im_free(void * addr)
291 {
292         struct vm_struct **p, *tmp;
293   
294         if (!addr)
295                 return;
296         if ((unsigned long) addr & ~PAGE_MASK) {
297                 printk(KERN_ERR "Trying to %s bad address (%p)\n", __FUNCTION__,                        addr);
298                 return;
299         }
300         down(&imlist_sem);
301         for (p = &imlist ; (tmp = *p) ; p = &tmp->next) {
302                 if (tmp->addr == addr) {
303                         *p = tmp->next;
304                         unmap_vm_area(tmp);
305                         kfree(tmp);
306                         up(&imlist_sem);
307                         return;
308                 }
309         }
310         up(&imlist_sem);
311         printk(KERN_ERR "Trying to %s nonexistent area (%p)\n", __FUNCTION__,
312                         addr);
313 }