[deliverable/linux.git] / arch / powerpc / mm / imalloc.c

/*
 * c 2001 PPC 64 Team, IBM Corp
 * 
 *      This program is free software; you can redistribute it and/or
 *      modify it under the terms of the GNU General Public License
 *      as published by the Free Software Foundation; either version
 *      2 of the License, or (at your option) any later version.
 */

#include <linux/slab.h>
#include <linux/vmalloc.h>

#include <asm/uaccess.h>
#include <asm/pgalloc.h>
#include <asm/pgtable.h>
#include <asm/semaphore.h>
#include <asm/cacheflush.h>

#include "mmu_decl.h"

static DECLARE_MUTEX(imlist_sem);
struct vm_struct * imlist = NULL;

static int get_free_im_addr(unsigned long size, unsigned long *im_addr)
{
	unsigned long addr;
	struct vm_struct **p, *tmp;

	addr = ioremap_bot;
	for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
		if (size + addr < (unsigned long) tmp->addr)
			break;
		if ((unsigned long)tmp->addr >= ioremap_bot)
			addr = tmp->size + (unsigned long) tmp->addr;
		if (addr >= IMALLOC_END-size)
			return 1;
	}
	*im_addr = addr;

	return 0;
}

/* Return whether the region described by v_addr and size is a subset
 * of the region described by parent
 */
static inline int im_region_is_subset(unsigned long v_addr, unsigned long size,
			struct vm_struct *parent)
{
	return (int) (v_addr >= (unsigned long) parent->addr &&
	              v_addr < (unsigned long) parent->addr + parent->size &&
	    	      size < parent->size);
}

/* Return whether the region described by v_addr and size is a superset
 * of the region described by child
 */
static int im_region_is_superset(unsigned long v_addr, unsigned long size,
		struct vm_struct *child)
{
	struct vm_struct parent;

	parent.addr = (void *) v_addr;
	parent.size = size;

	return im_region_is_subset((unsigned long) child->addr, child->size,
			&parent);
}

/* Return whether the region described by v_addr and size overlaps
 * the region described by vm.  Overlapping regions meet the
 * following conditions:
 * 1) The regions share some part of the address space
 * 2) The regions aren't identical
 * 3) Neither region is a subset of the other
 */
static int im_region_overlaps(unsigned long v_addr, unsigned long size,
		     struct vm_struct *vm)
{
	if (im_region_is_superset(v_addr, size, vm))
		return 0;

	return (v_addr + size > (unsigned long) vm->addr + vm->size &&
		v_addr < (unsigned long) vm->addr + vm->size) ||
	       (v_addr < (unsigned long) vm->addr &&
		v_addr + size > (unsigned long) vm->addr);
}

/* Determine imalloc status of region described by v_addr and size.
 * Can return one of the following:
 * IM_REGION_UNUSED   -  Entire region is unallocated in imalloc space.
 * IM_REGION_SUBSET -    Region is a subset of a region that is already
 * 			 allocated in imalloc space.
 * 		         vm will be assigned to a ptr to the parent region.
 * IM_REGION_EXISTS -    Exact region already allocated in imalloc space.
 *                       vm will be assigned to a ptr to the existing imlist
 *                       member.
 * IM_REGION_OVERLAPS -  Region overlaps an allocated region in imalloc space.
 * IM_REGION_SUPERSET -  Region is a superset of a region that is already
 *                       allocated in imalloc space.
 */
static int im_region_status(unsigned long v_addr, unsigned long size,
		    struct vm_struct **vm)
{
	struct vm_struct *tmp;

	for (tmp = imlist; tmp; tmp = tmp->next)
		if (v_addr < (unsigned long) tmp->addr + tmp->size)
			break;

	if (tmp) {
		if (im_region_overlaps(v_addr, size, tmp))
			return IM_REGION_OVERLAP;

		*vm = tmp;
		if (im_region_is_subset(v_addr, size, tmp)) {
			/* Return with tmp pointing to superset */
			return IM_REGION_SUBSET;
		}
		if (im_region_is_superset(v_addr, size, tmp)) {
			/* Return with tmp pointing to first subset */
			return IM_REGION_SUPERSET;
		}
		else if (v_addr == (unsigned long) tmp->addr &&
		 	 size == tmp->size) {
			/* Return with tmp pointing to exact region */
			return IM_REGION_EXISTS;
		}
	}

	*vm = NULL;
	return IM_REGION_UNUSED;
}

static struct vm_struct * split_im_region(unsigned long v_addr, 
		unsigned long size, struct vm_struct *parent)
{
	struct vm_struct *vm1 = NULL;
	struct vm_struct *vm2 = NULL;
	struct vm_struct *new_vm = NULL;
	
	vm1 = (struct vm_struct *) kmalloc(sizeof(*vm1), GFP_KERNEL);
	if (vm1	== NULL) {
		printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
		return NULL;
	}

	if (v_addr == (unsigned long) parent->addr) {
	        /* Use existing parent vm_struct to represent child, allocate
		 * new one for the remainder of parent range
		 */
		vm1->size = parent->size - size;
		vm1->addr = (void *) (v_addr + size);
		vm1->next = parent->next;

		parent->size = size;
		parent->next = vm1;
		new_vm = parent;
	} else if (v_addr + size == (unsigned long) parent->addr + 
			parent->size) {
		/* Allocate new vm_struct to represent child, use existing
		 * parent one for remainder of parent range
		 */
		vm1->size = size;
		vm1->addr = (void *) v_addr;
		vm1->next = parent->next;
		new_vm = vm1;

		parent->size -= size;
		parent->next = vm1;
	} else {
	        /* Allocate two new vm_structs for the new child and 
		 * uppermost remainder, and use existing parent one for the
		 * lower remainder of parent range
		 */
		vm2 = (struct vm_struct *) kmalloc(sizeof(*vm2), GFP_KERNEL);
		if (vm2 == NULL) {
			printk(KERN_ERR "%s() out of memory\n", __FUNCTION__);
			kfree(vm1);
			return NULL;
		}

		vm1->size = size;
		vm1->addr = (void *) v_addr;
		vm1->next = vm2;
		new_vm = vm1;

		vm2->size = ((unsigned long) parent->addr + parent->size) - 
				(v_addr + size);
		vm2->addr = (void *) v_addr + size;
		vm2->next = parent->next;

		parent->size = v_addr - (unsigned long) parent->addr;
		parent->next = vm1;
	}

	return new_vm;
}

static struct vm_struct * __add_new_im_area(unsigned long req_addr, 
					    unsigned long size)
{
	struct vm_struct **p, *tmp, *area;
		
	for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
		if (req_addr + size <= (unsigned long)tmp->addr)
			break;
	}
	
	area = (struct vm_struct *) kmalloc(sizeof(*area), GFP_KERNEL);
	if (!area)
		return NULL;
	area->flags = 0;
	area->addr = (void *)req_addr;
	area->size = size;
	area->next = *p;
	*p = area;

	return area;
}

static struct vm_struct * __im_get_area(unsigned long req_addr, 
					unsigned long size,
					int criteria)
{
	struct vm_struct *tmp;
	int status;

	status = im_region_status(req_addr, size, &tmp);
	if ((criteria & status) == 0) {
		return NULL;
	}
	
	switch (status) {
	case IM_REGION_UNUSED:
		tmp = __add_new_im_area(req_addr, size);
		break;
	case IM_REGION_SUBSET:
		tmp = split_im_region(req_addr, size, tmp);
		break;
	case IM_REGION_EXISTS:
		/* Return requested region */
		break;
	case IM_REGION_SUPERSET:
		/* Return first existing subset of requested region */
		break;
	default:
		printk(KERN_ERR "%s() unexpected imalloc region status\n",
				__FUNCTION__);
		tmp = NULL;
	}

	return tmp;
}

struct vm_struct * im_get_free_area(unsigned long size)
{
	struct vm_struct *area;
	unsigned long addr;
	
	down(&imlist_sem);
	if (get_free_im_addr(size, &addr)) {
		printk(KERN_ERR "%s() cannot obtain addr for size 0x%lx\n",
				__FUNCTION__, size);
		area = NULL;
		goto next_im_done;
	}

	area = __im_get_area(addr, size, IM_REGION_UNUSED);
	if (area == NULL) {
		printk(KERN_ERR 
		       "%s() cannot obtain area for addr 0x%lx size 0x%lx\n",
			__FUNCTION__, addr, size);
	}
next_im_done:
	up(&imlist_sem);
	return area;
}

struct vm_struct * im_get_area(unsigned long v_addr, unsigned long size,
		int criteria)
{
	struct vm_struct *area;

	down(&imlist_sem);
	area = __im_get_area(v_addr, size, criteria);
	up(&imlist_sem);
	return area;
}

void im_free(void * addr)
{
	struct vm_struct **p, *tmp;
  
	if (!addr)
		return;
	if ((unsigned long) addr & ~PAGE_MASK) {
		printk(KERN_ERR "Trying to %s bad address (%p)\n", __FUNCTION__,			addr);
		return;
	}
	down(&imlist_sem);
	for (p = &imlist ; (tmp = *p) ; p = &tmp->next) {
		if (tmp->addr == addr) {
			*p = tmp->next;
			unmap_vm_area(tmp);
			kfree(tmp);
			up(&imlist_sem);
			return;
		}
	}
	up(&imlist_sem);
	printk(KERN_ERR "Trying to %s nonexistent area (%p)\n", __FUNCTION__,
			addr);
}
Commit	Line	Data
1da177e4 LT	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>
20cee16c	17	#include <asm/cacheflush.h>
1da177e4	18
800fc3ee DG	19	#include "mmu_decl.h"
800fc3ee DG	20
1da177e4 LT	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
1f8d419e	29	addr = ioremap_bot;
1da177e4 LT	30	for (p = &imlist; (tmp = *p) ; p = &tmp->next) {
	31	if (size + addr < (unsigned long) tmp->addr)
	32	break;
1f8d419e	33	if ((unsigned long)tmp->addr >= ioremap_bot)
1da177e4	34	addr = tmp->size + (unsigned long) tmp->addr;
e28f7faf	35	if (addr >= IMALLOC_END-size)
1da177e4 LT	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	if (tmp) {
111	if (im_region_overlaps(v_addr, size, tmp))
112	return IM_REGION_OVERLAP;
113
114	*vm = tmp;
115	if (im_region_is_subset(v_addr, size, tmp)) {
116	/* Return with tmp pointing to superset */
117	return IM_REGION_SUBSET;
118	}
119	if (im_region_is_superset(v_addr, size, tmp)) {
120	/* Return with tmp pointing to first subset */
121	return IM_REGION_SUPERSET;
122	}
123	else if (v_addr == (unsigned long) tmp->addr &&
124	size == tmp->size) {
125	/* Return with tmp pointing to exact region */
126	return IM_REGION_EXISTS;
127	}
128	}
129
130	*vm = NULL;
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
20cee16c	290	void im_free(void * addr)
1da177e4 LT	291	{
1da177e4 LT	292	struct vm_struct *p, tmp;
1da177e4 LT	293
1da177e4 LT	294	if (!addr)
20cee16c DG	295	return;
20cee16c DG	296	if ((unsigned long) addr & ~PAGE_MASK) {
1da177e4	297	printk(KERN_ERR "Trying to %s bad address (%p)\n", __FUNCTION__, addr);
20cee16c	298	return;
1da177e4 LT	299	}
	300	down(&imlist_sem);
	301	for (p = &imlist ; (tmp = *p) ; p = &tmp->next) {
	302	if (tmp->addr == addr) {
1da177e4	303	*p = tmp->next;
20cee16c	304	unmap_vm_area(tmp);
1da177e4 LT	305	kfree(tmp);
1da177e4 LT	306	up(&imlist_sem);
20cee16c	307	return;
1da177e4 LT	308	}
	309	}
	310	up(&imlist_sem);
	311	printk(KERN_ERR "Trying to %s nonexistent area (%p)\n", __FUNCTION__,
	312	addr);
1da177e4	313	}