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