2 * c 2001 PPC 64 Team, IBM Corp
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.
10 #include <linux/slab.h>
11 #include <linux/vmalloc.h>
13 #include <asm/uaccess.h>
14 #include <asm/pgalloc.h>
15 #include <asm/pgtable.h>
16 #include <asm/semaphore.h>
17 #include <asm/imalloc.h>
19 static DECLARE_MUTEX(imlist_sem);
20 struct vm_struct * imlist = NULL;
22 static int get_free_im_addr(unsigned long size, unsigned long *im_addr)
25 struct vm_struct **p, *tmp;
28 for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
29 if (size + addr < (unsigned long) tmp->addr)
31 if ((unsigned long)tmp->addr >= ioremap_bot)
32 addr = tmp->size + (unsigned long) tmp->addr;
33 if (addr > IMALLOC_END-size)
41 /* Return whether the region described by v_addr and size is a subset
42 * of the region described by parent
44 static inline int im_region_is_subset(unsigned long v_addr, unsigned long size,
45 struct vm_struct *parent)
47 return (int) (v_addr >= (unsigned long) parent->addr &&
48 v_addr < (unsigned long) parent->addr + parent->size &&
52 /* Return whether the region described by v_addr and size is a superset
53 * of the region described by child
55 static int im_region_is_superset(unsigned long v_addr, unsigned long size,
56 struct vm_struct *child)
58 struct vm_struct parent;
60 parent.addr = (void *) v_addr;
63 return im_region_is_subset((unsigned long) child->addr, child->size,
67 /* Return whether the region described by v_addr and size overlaps
68 * the region described by vm. Overlapping regions meet the
69 * following conditions:
70 * 1) The regions share some part of the address space
71 * 2) The regions aren't identical
72 * 3) Neither region is a subset of the other
74 static int im_region_overlaps(unsigned long v_addr, unsigned long size,
77 if (im_region_is_superset(v_addr, size, vm))
80 return (v_addr + size > (unsigned long) vm->addr + vm->size &&
81 v_addr < (unsigned long) vm->addr + vm->size) ||
82 (v_addr < (unsigned long) vm->addr &&
83 v_addr + size > (unsigned long) vm->addr);
86 /* Determine imalloc status of region described by v_addr and size.
87 * Can return one of the following:
88 * IM_REGION_UNUSED - Entire region is unallocated in imalloc space.
89 * IM_REGION_SUBSET - Region is a subset of a region that is already
90 * allocated in imalloc space.
91 * vm will be assigned to a ptr to the parent region.
92 * IM_REGION_EXISTS - Exact region already allocated in imalloc space.
93 * vm will be assigned to a ptr to the existing imlist
95 * IM_REGION_OVERLAPS - Region overlaps an allocated region in imalloc space.
96 * IM_REGION_SUPERSET - Region is a superset of a region that is already
97 * allocated in imalloc space.
99 static int im_region_status(unsigned long v_addr, unsigned long size,
100 struct vm_struct **vm)
102 struct vm_struct *tmp;
104 for (tmp = imlist; tmp; tmp = tmp->next)
105 if (v_addr < (unsigned long) tmp->addr + tmp->size)
109 if (im_region_overlaps(v_addr, size, tmp))
110 return IM_REGION_OVERLAP;
113 if (im_region_is_subset(v_addr, size, tmp)) {
114 /* Return with tmp pointing to superset */
115 return IM_REGION_SUBSET;
117 if (im_region_is_superset(v_addr, size, tmp)) {
118 /* Return with tmp pointing to first subset */
119 return IM_REGION_SUPERSET;
121 else if (v_addr == (unsigned long) tmp->addr &&
123 /* Return with tmp pointing to exact region */
124 return IM_REGION_EXISTS;
129 return IM_REGION_UNUSED;
132 static struct vm_struct * split_im_region(unsigned long v_addr,
133 unsigned long size, struct vm_struct *parent)
135 struct vm_struct *vm1 = NULL;
136 struct vm_struct *vm2 = NULL;
137 struct vm_struct *new_vm = NULL;
139 vm1 = (struct vm_struct *) kmalloc(sizeof(*vm1), GFP_KERNEL);
141 printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
145 if (v_addr == (unsigned long) parent->addr) {
146 /* Use existing parent vm_struct to represent child, allocate
147 * new one for the remainder of parent range
149 vm1->size = parent->size - size;
150 vm1->addr = (void *) (v_addr + size);
151 vm1->next = parent->next;
156 } else if (v_addr + size == (unsigned long) parent->addr +
158 /* Allocate new vm_struct to represent child, use existing
159 * parent one for remainder of parent range
162 vm1->addr = (void *) v_addr;
163 vm1->next = parent->next;
166 parent->size -= size;
169 /* Allocate two new vm_structs for the new child and
170 * uppermost remainder, and use existing parent one for the
171 * lower remainder of parent range
173 vm2 = (struct vm_struct *) kmalloc(sizeof(*vm2), GFP_KERNEL);
175 printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
181 vm1->addr = (void *) v_addr;
185 vm2->size = ((unsigned long) parent->addr + parent->size) -
187 vm2->addr = (void *) v_addr + size;
188 vm2->next = parent->next;
190 parent->size = v_addr - (unsigned long) parent->addr;
197 static struct vm_struct * __add_new_im_area(unsigned long req_addr,
200 struct vm_struct **p, *tmp, *area;
202 for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
203 if (req_addr + size <= (unsigned long)tmp->addr)
207 area = (struct vm_struct *) kmalloc(sizeof(*area), GFP_KERNEL);
211 area->addr = (void *)req_addr;
219 static struct vm_struct * __im_get_area(unsigned long req_addr,
223 struct vm_struct *tmp;
226 status = im_region_status(req_addr, size, &tmp);
227 if ((criteria & status) == 0) {
232 case IM_REGION_UNUSED:
233 tmp = __add_new_im_area(req_addr, size);
235 case IM_REGION_SUBSET:
236 tmp = split_im_region(req_addr, size, tmp);
238 case IM_REGION_EXISTS:
239 /* Return requested region */
241 case IM_REGION_SUPERSET:
242 /* Return first existing subset of requested region */
245 printk(KERN_ERR "%s() unexpected imalloc region status\n",
253 struct vm_struct * im_get_free_area(unsigned long size)
255 struct vm_struct *area;
259 if (get_free_im_addr(size, &addr)) {
260 printk(KERN_ERR "%s() cannot obtain addr for size 0x%lx\n",
266 area = __im_get_area(addr, size, IM_REGION_UNUSED);
269 "%s() cannot obtain area for addr 0x%lx size 0x%lx\n",
270 __FUNCTION__, addr, size);
277 struct vm_struct * im_get_area(unsigned long v_addr, unsigned long size,
280 struct vm_struct *area;
283 area = __im_get_area(v_addr, size, criteria);
288 unsigned long im_free(void * addr)
290 struct vm_struct **p, *tmp;
291 unsigned long ret_size = 0;
295 if ((PAGE_SIZE-1) & (unsigned long) addr) {
296 printk(KERN_ERR "Trying to %s bad address (%p)\n", __FUNCTION__, addr);
300 for (p = &imlist ; (tmp = *p) ; p = &tmp->next) {
301 if (tmp->addr == addr) {
302 ret_size = tmp->size;
310 printk(KERN_ERR "Trying to %s nonexistent area (%p)\n", __FUNCTION__,