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>
18 #include <asm/cacheflush.h>
20 static DECLARE_MUTEX(imlist_sem
);
21 struct vm_struct
* imlist
= NULL
;
23 static int get_free_im_addr(unsigned long size
, unsigned long *im_addr
)
26 struct vm_struct
**p
, *tmp
;
29 for (p
= &imlist
; (tmp
= *p
) ; p
= &tmp
->next
) {
30 if (size
+ addr
< (unsigned long) tmp
->addr
)
32 if ((unsigned long)tmp
->addr
>= ioremap_bot
)
33 addr
= tmp
->size
+ (unsigned long) tmp
->addr
;
34 if (addr
>= IMALLOC_END
-size
)
42 /* Return whether the region described by v_addr and size is a subset
43 * of the region described by parent
45 static inline int im_region_is_subset(unsigned long v_addr
, unsigned long size
,
46 struct vm_struct
*parent
)
48 return (int) (v_addr
>= (unsigned long) parent
->addr
&&
49 v_addr
< (unsigned long) parent
->addr
+ parent
->size
&&
53 /* Return whether the region described by v_addr and size is a superset
54 * of the region described by child
56 static int im_region_is_superset(unsigned long v_addr
, unsigned long size
,
57 struct vm_struct
*child
)
59 struct vm_struct parent
;
61 parent
.addr
= (void *) v_addr
;
64 return im_region_is_subset((unsigned long) child
->addr
, child
->size
,
68 /* Return whether the region described by v_addr and size overlaps
69 * the region described by vm. Overlapping regions meet the
70 * following conditions:
71 * 1) The regions share some part of the address space
72 * 2) The regions aren't identical
73 * 3) Neither region is a subset of the other
75 static int im_region_overlaps(unsigned long v_addr
, unsigned long size
,
78 if (im_region_is_superset(v_addr
, size
, vm
))
81 return (v_addr
+ size
> (unsigned long) vm
->addr
+ vm
->size
&&
82 v_addr
< (unsigned long) vm
->addr
+ vm
->size
) ||
83 (v_addr
< (unsigned long) vm
->addr
&&
84 v_addr
+ size
> (unsigned long) vm
->addr
);
87 /* Determine imalloc status of region described by v_addr and size.
88 * Can return one of the following:
89 * IM_REGION_UNUSED - Entire region is unallocated in imalloc space.
90 * IM_REGION_SUBSET - Region is a subset of a region that is already
91 * allocated in imalloc space.
92 * vm will be assigned to a ptr to the parent region.
93 * IM_REGION_EXISTS - Exact region already allocated in imalloc space.
94 * vm will be assigned to a ptr to the existing imlist
96 * IM_REGION_OVERLAPS - Region overlaps an allocated region in imalloc space.
97 * IM_REGION_SUPERSET - Region is a superset of a region that is already
98 * allocated in imalloc space.
100 static int im_region_status(unsigned long v_addr
, unsigned long size
,
101 struct vm_struct
**vm
)
103 struct vm_struct
*tmp
;
105 for (tmp
= imlist
; tmp
; tmp
= tmp
->next
)
106 if (v_addr
< (unsigned long) tmp
->addr
+ tmp
->size
)
110 if (im_region_overlaps(v_addr
, size
, tmp
))
111 return IM_REGION_OVERLAP
;
114 if (im_region_is_subset(v_addr
, size
, tmp
)) {
115 /* Return with tmp pointing to superset */
116 return IM_REGION_SUBSET
;
118 if (im_region_is_superset(v_addr
, size
, tmp
)) {
119 /* Return with tmp pointing to first subset */
120 return IM_REGION_SUPERSET
;
122 else if (v_addr
== (unsigned long) tmp
->addr
&&
124 /* Return with tmp pointing to exact region */
125 return IM_REGION_EXISTS
;
130 return IM_REGION_UNUSED
;
133 static struct vm_struct
* split_im_region(unsigned long v_addr
,
134 unsigned long size
, struct vm_struct
*parent
)
136 struct vm_struct
*vm1
= NULL
;
137 struct vm_struct
*vm2
= NULL
;
138 struct vm_struct
*new_vm
= NULL
;
140 vm1
= (struct vm_struct
*) kmalloc(sizeof(*vm1
), GFP_KERNEL
);
142 printk(KERN_ERR
"%s() out of memory\n", __FUNCTION__
);
146 if (v_addr
== (unsigned long) parent
->addr
) {
147 /* Use existing parent vm_struct to represent child, allocate
148 * new one for the remainder of parent range
150 vm1
->size
= parent
->size
- size
;
151 vm1
->addr
= (void *) (v_addr
+ size
);
152 vm1
->next
= parent
->next
;
157 } else if (v_addr
+ size
== (unsigned long) parent
->addr
+
159 /* Allocate new vm_struct to represent child, use existing
160 * parent one for remainder of parent range
163 vm1
->addr
= (void *) v_addr
;
164 vm1
->next
= parent
->next
;
167 parent
->size
-= size
;
170 /* Allocate two new vm_structs for the new child and
171 * uppermost remainder, and use existing parent one for the
172 * lower remainder of parent range
174 vm2
= (struct vm_struct
*) kmalloc(sizeof(*vm2
), GFP_KERNEL
);
176 printk(KERN_ERR
"%s() out of memory\n", __FUNCTION__
);
182 vm1
->addr
= (void *) v_addr
;
186 vm2
->size
= ((unsigned long) parent
->addr
+ parent
->size
) -
188 vm2
->addr
= (void *) v_addr
+ size
;
189 vm2
->next
= parent
->next
;
191 parent
->size
= v_addr
- (unsigned long) parent
->addr
;
198 static struct vm_struct
* __add_new_im_area(unsigned long req_addr
,
201 struct vm_struct
**p
, *tmp
, *area
;
203 for (p
= &imlist
; (tmp
= *p
) ; p
= &tmp
->next
) {
204 if (req_addr
+ size
<= (unsigned long)tmp
->addr
)
208 area
= (struct vm_struct
*) kmalloc(sizeof(*area
), GFP_KERNEL
);
212 area
->addr
= (void *)req_addr
;
220 static struct vm_struct
* __im_get_area(unsigned long req_addr
,
224 struct vm_struct
*tmp
;
227 status
= im_region_status(req_addr
, size
, &tmp
);
228 if ((criteria
& status
) == 0) {
233 case IM_REGION_UNUSED
:
234 tmp
= __add_new_im_area(req_addr
, size
);
236 case IM_REGION_SUBSET
:
237 tmp
= split_im_region(req_addr
, size
, tmp
);
239 case IM_REGION_EXISTS
:
240 /* Return requested region */
242 case IM_REGION_SUPERSET
:
243 /* Return first existing subset of requested region */
246 printk(KERN_ERR
"%s() unexpected imalloc region status\n",
254 struct vm_struct
* im_get_free_area(unsigned long size
)
256 struct vm_struct
*area
;
260 if (get_free_im_addr(size
, &addr
)) {
261 printk(KERN_ERR
"%s() cannot obtain addr for size 0x%lx\n",
267 area
= __im_get_area(addr
, size
, IM_REGION_UNUSED
);
270 "%s() cannot obtain area for addr 0x%lx size 0x%lx\n",
271 __FUNCTION__
, addr
, size
);
278 struct vm_struct
* im_get_area(unsigned long v_addr
, unsigned long size
,
281 struct vm_struct
*area
;
284 area
= __im_get_area(v_addr
, size
, criteria
);
289 void im_free(void * addr
)
291 struct vm_struct
**p
, *tmp
;
295 if ((unsigned long) addr
& ~PAGE_MASK
) {
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
) {
310 printk(KERN_ERR
"Trying to %s nonexistent area (%p)\n", __FUNCTION__
,