[net-next-2.6.git] / drivers / char / drm / drm_mm.c

/**************************************************************************
 *
 * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA.
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sub license, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice (including the
 * next paragraph) shall be included in all copies or substantial portions
 * of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
 * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
 * USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 *
 **************************************************************************/

/*
 * Generic simple memory manager implementation. Intended to be used as a base
 * class implementation for more advanced memory managers.
 *
 * Note that the algorithm used is quite simple and there might be substantial
 * performance gains if a smarter free list is implemented. Currently it is just an
 * unordered stack of free regions. This could easily be improved if an RB-tree
 * is used instead. At least if we expect heavy fragmentation.
 *
 * Aligned allocations can also see improvement.
 *
 * Authors:
 * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
 */

#include "drmP.h"
#include <linux/slab.h>

unsigned long drm_mm_tail_space(struct drm_mm *mm)
{
	struct list_head *tail_node;
	struct drm_mm_node *entry;

	tail_node = mm->ml_entry.prev;
	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
	if (!entry->free)
		return 0;

	return entry->size;
}

int drm_mm_remove_space_from_tail(struct drm_mm *mm, unsigned long size)
{
	struct list_head *tail_node;
	struct drm_mm_node *entry;

	tail_node = mm->ml_entry.prev;
	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
	if (!entry->free)
		return -ENOMEM;

	if (entry->size <= size)
		return -ENOMEM;

	entry->size -= size;
	return 0;
}


static int drm_mm_create_tail_node(struct drm_mm *mm,
			    unsigned long start,
			    unsigned long size)
{
	struct drm_mm_node *child;

	child = (struct drm_mm_node *)
		drm_alloc(sizeof(*child), DRM_MEM_MM);
	if (!child)
		return -ENOMEM;

	child->free = 1;
	child->size = size;
	child->start = start;
	child->mm = mm;

	list_add_tail(&child->ml_entry, &mm->ml_entry);
	list_add_tail(&child->fl_entry, &mm->fl_entry);

	return 0;
}


int drm_mm_add_space_to_tail(struct drm_mm *mm, unsigned long size)
{
	struct list_head *tail_node;
	struct drm_mm_node *entry;

	tail_node = mm->ml_entry.prev;
	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
	if (!entry->free) {
		return drm_mm_create_tail_node(mm, entry->start + entry->size, size);
	}
	entry->size += size;
	return 0;
}

static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent,
					    unsigned long size)
{
	struct drm_mm_node *child;

	child = (struct drm_mm_node *)
		drm_alloc(sizeof(*child), DRM_MEM_MM);
	if (!child)
		return NULL;

	INIT_LIST_HEAD(&child->fl_entry);

	child->free = 0;
	child->size = size;
	child->start = parent->start;
	child->mm = parent->mm;

	list_add_tail(&child->ml_entry, &parent->ml_entry);
	INIT_LIST_HEAD(&child->fl_entry);

	parent->size -= size;
	parent->start += size;
	return child;
}


struct drm_mm_node *drm_mm_get_block(struct drm_mm_node * parent,
				unsigned long size, unsigned alignment)
{

	struct drm_mm_node *align_splitoff = NULL;
	struct drm_mm_node *child;
	unsigned tmp = 0;

	if (alignment)
		tmp = parent->start % alignment;

	if (tmp) {
		align_splitoff = drm_mm_split_at_start(parent, alignment - tmp);
		if (!align_splitoff)
			return NULL;
	}

	if (parent->size == size) {
		list_del_init(&parent->fl_entry);
		parent->free = 0;
		return parent;
	} else {
		child = drm_mm_split_at_start(parent, size);
	}

	if (align_splitoff)
		drm_mm_put_block(align_splitoff);

	return child;
}

/*
 * Put a block. Merge with the previous and / or next block if they are free.
 * Otherwise add to the free stack.
 */

void drm_mm_put_block(struct drm_mm_node * cur)
{

	struct drm_mm *mm = cur->mm;
	struct list_head *cur_head = &cur->ml_entry;
	struct list_head *root_head = &mm->ml_entry;
	struct drm_mm_node *prev_node = NULL;
	struct drm_mm_node *next_node;

	int merged = 0;

	if (cur_head->prev != root_head) {
		prev_node = list_entry(cur_head->prev, struct drm_mm_node, ml_entry);
		if (prev_node->free) {
			prev_node->size += cur->size;
			merged = 1;
		}
	}
	if (cur_head->next != root_head) {
		next_node = list_entry(cur_head->next, struct drm_mm_node, ml_entry);
		if (next_node->free) {
			if (merged) {
				prev_node->size += next_node->size;
				list_del(&next_node->ml_entry);
				list_del(&next_node->fl_entry);
				drm_free(next_node, sizeof(*next_node),
					 DRM_MEM_MM);
			} else {
				next_node->size += cur->size;
				next_node->start = cur->start;
				merged = 1;
			}
		}
	}
	if (!merged) {
		cur->free = 1;
		list_add(&cur->fl_entry, &mm->fl_entry);
	} else {
		list_del(&cur->ml_entry);
		drm_free(cur, sizeof(*cur), DRM_MEM_MM);
	}
}

struct drm_mm_node *drm_mm_search_free(const struct drm_mm * mm,
				  unsigned long size,
				  unsigned alignment, int best_match)
{
	struct list_head *list;
	const struct list_head *free_stack = &mm->fl_entry;
	struct drm_mm_node *entry;
	struct drm_mm_node *best;
	unsigned long best_size;
	unsigned wasted;

	best = NULL;
	best_size = ~0UL;

	list_for_each(list, free_stack) {
		entry = list_entry(list, struct drm_mm_node, fl_entry);
		wasted = 0;

		if (entry->size < size)
			continue;

		if (alignment) {
			register unsigned tmp = entry->start % alignment;
			if (tmp)
				wasted += alignment - tmp;
		}


		if (entry->size >= size + wasted) {
			if (!best_match)
				return entry;
			if (size < best_size) {
				best = entry;
				best_size = entry->size;
			}
		}
	}

	return best;
}

int drm_mm_clean(struct drm_mm * mm)
{
	struct list_head *head = &mm->ml_entry;

	return (head->next->next == head);
}

int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
{
	INIT_LIST_HEAD(&mm->ml_entry);
	INIT_LIST_HEAD(&mm->fl_entry);

	return drm_mm_create_tail_node(mm, start, size);
}


void drm_mm_takedown(struct drm_mm * mm)
{
	struct list_head *bnode = mm->fl_entry.next;
	struct drm_mm_node *entry;

	entry = list_entry(bnode, struct drm_mm_node, fl_entry);

	if (entry->ml_entry.next != &mm->ml_entry ||
	    entry->fl_entry.next != &mm->fl_entry) {
		DRM_ERROR("Memory manager not clean. Delaying takedown\n");
		return;
	}

	list_del(&entry->fl_entry);
	list_del(&entry->ml_entry);

	drm_free(entry, sizeof(*entry), DRM_MEM_MM);
}
Commit	Line	Data
3a1bd924 TH	1	/**************************************************************************
	2	*
	3	* Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA.
	4	* All Rights Reserved.
	5	*
	6	* Permission is hereby granted, free of charge, to any person obtaining a
	7	* copy of this software and associated documentation files (the
	8	* "Software"), to deal in the Software without restriction, including
	9	* without limitation the rights to use, copy, modify, merge, publish,
	10	* distribute, sub license, and/or sell copies of the Software, and to
	11	* permit persons to whom the Software is furnished to do so, subject to
	12	* the following conditions:
	13	*
	14	* The above copyright notice and this permission notice (including the
	15	* next paragraph) shall be included in all copies or substantial portions
	16	* of the Software.
	17	*
	18	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	19	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	20	* FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
	21	* THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
	22	* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
	23	* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
	24	* USE OR OTHER DEALINGS IN THE SOFTWARE.
	25	*
	26	*
	27	**************************************************************************/
	28
	29	/*
	30	* Generic simple memory manager implementation. Intended to be used as a base
	31	* class implementation for more advanced memory managers.
	32	*
	33	* Note that the algorithm used is quite simple and there might be substantial
	34	* performance gains if a smarter free list is implemented. Currently it is just an
	35	* unordered stack of free regions. This could easily be improved if an RB-tree
	36	* is used instead. At least if we expect heavy fragmentation.
	37	*
	38	* Aligned allocations can also see improvement.
	39	*
	40	* Authors:
96de0e25	41	* Thomas Hellström <thomas-at-tungstengraphics-dot-com>
3a1bd924 TH	42	*/
	43
	44	#include "drmP.h"
1d58420b TH	45	#include <linux/slab.h>
1d58420b TH	46
55910517	47	unsigned long drm_mm_tail_space(struct drm_mm *mm)
1d58420b TH	48	{
1d58420b TH	49	struct list_head *tail_node;
55910517	50	struct drm_mm_node *entry;
1d58420b TH	51
1d58420b TH	52	tail_node = mm->ml_entry.prev;
55910517	53	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
1d58420b TH	54	if (!entry->free)
	55	return 0;
	56
	57	return entry->size;
	58	}
	59
55910517	60	int drm_mm_remove_space_from_tail(struct drm_mm *mm, unsigned long size)
1d58420b TH	61	{
1d58420b TH	62	struct list_head *tail_node;
55910517	63	struct drm_mm_node *entry;
1d58420b TH	64
1d58420b TH	65	tail_node = mm->ml_entry.prev;
55910517	66	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
1d58420b TH	67	if (!entry->free)
	68	return -ENOMEM;
	69
	70	if (entry->size <= size)
	71	return -ENOMEM;
	72
	73	entry->size -= size;
	74	return 0;
	75	}
	76
	77
55910517	78	static int drm_mm_create_tail_node(struct drm_mm *mm,
1d58420b TH	79	unsigned long start,
	80	unsigned long size)
	81	{
55910517	82	struct drm_mm_node *child;
1d58420b	83
55910517	84	child = (struct drm_mm_node *)
1d58420b TH	85	drm_alloc(sizeof(*child), DRM_MEM_MM);
	86	if (!child)
	87	return -ENOMEM;
	88
	89	child->free = 1;
	90	child->size = size;
	91	child->start = start;
	92	child->mm = mm;
	93
	94	list_add_tail(&child->ml_entry, &mm->ml_entry);
	95	list_add_tail(&child->fl_entry, &mm->fl_entry);
	96
	97	return 0;
	98	}
	99
	100
55910517	101	int drm_mm_add_space_to_tail(struct drm_mm *mm, unsigned long size)
1d58420b TH	102	{
1d58420b TH	103	struct list_head *tail_node;
55910517	104	struct drm_mm_node *entry;
1d58420b TH	105
1d58420b TH	106	tail_node = mm->ml_entry.prev;
55910517	107	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
1d58420b TH	108	if (!entry->free) {
	109	return drm_mm_create_tail_node(mm, entry->start + entry->size, size);
	110	}
	111	entry->size += size;
	112	return 0;
	113	}
	114
55910517	115	static struct drm_mm_node drm_mm_split_at_start(struct drm_mm_node parent,
1d58420b TH	116	unsigned long size)
1d58420b TH	117	{
55910517	118	struct drm_mm_node *child;
1d58420b	119
55910517	120	child = (struct drm_mm_node *)
1d58420b TH	121	drm_alloc(sizeof(*child), DRM_MEM_MM);
	122	if (!child)
	123	return NULL;
	124
	125	INIT_LIST_HEAD(&child->fl_entry);
	126
	127	child->free = 0;
	128	child->size = size;
	129	child->start = parent->start;
	130	child->mm = parent->mm;
	131
	132	list_add_tail(&child->ml_entry, &parent->ml_entry);
	133	INIT_LIST_HEAD(&child->fl_entry);
	134
	135	parent->size -= size;
	136	parent->start += size;
	137	return child;
	138	}
	139
	140
3a1bd924	141
55910517	142	struct drm_mm_node drm_mm_get_block(struct drm_mm_node parent,
3a1bd924 TH	143	unsigned long size, unsigned alignment)
	144	{
	145
55910517 DA	146	struct drm_mm_node *align_splitoff = NULL;
55910517 DA	147	struct drm_mm_node *child;
1d58420b	148	unsigned tmp = 0;
3a1bd924 TH	149
3a1bd924 TH	150	if (alignment)
1d58420b TH	151	tmp = parent->start % alignment;
	152
	153	if (tmp) {
	154	align_splitoff = drm_mm_split_at_start(parent, alignment - tmp);
	155	if (!align_splitoff)
	156	return NULL;
	157	}
3a1bd924 TH	158
	159	if (parent->size == size) {
	160	list_del_init(&parent->fl_entry);
a1d0fcf5	161	parent->free = 0;
3a1bd924 TH	162	return parent;
3a1bd924 TH	163	} else {
1d58420b TH	164	child = drm_mm_split_at_start(parent, size);
1d58420b TH	165	}
3a1bd924	166
1d58420b TH	167	if (align_splitoff)
1d58420b TH	168	drm_mm_put_block(align_splitoff);
3a1bd924	169
3a1bd924 TH	170	return child;
	171	}
	172
	173	/*
	174	* Put a block. Merge with the previous and / or next block if they are free.
	175	* Otherwise add to the free stack.
	176	*/
	177
55910517	178	void drm_mm_put_block(struct drm_mm_node * cur)
3a1bd924 TH	179	{
3a1bd924 TH	180
55910517	181	struct drm_mm *mm = cur->mm;
3a1bd924	182	struct list_head *cur_head = &cur->ml_entry;
1d58420b	183	struct list_head *root_head = &mm->ml_entry;
55910517 DA	184	struct drm_mm_node *prev_node = NULL;
55910517 DA	185	struct drm_mm_node *next_node;
3a1bd924	186
a1d0fcf5	187	int merged = 0;
3a1bd924 TH	188
3a1bd924 TH	189	if (cur_head->prev != root_head) {
55910517	190	prev_node = list_entry(cur_head->prev, struct drm_mm_node, ml_entry);
3a1bd924 TH	191	if (prev_node->free) {
3a1bd924 TH	192	prev_node->size += cur->size;
a1d0fcf5	193	merged = 1;
3a1bd924 TH	194	}
	195	}
	196	if (cur_head->next != root_head) {
55910517	197	next_node = list_entry(cur_head->next, struct drm_mm_node, ml_entry);
3a1bd924 TH	198	if (next_node->free) {
	199	if (merged) {
	200	prev_node->size += next_node->size;
	201	list_del(&next_node->ml_entry);
	202	list_del(&next_node->fl_entry);
	203	drm_free(next_node, sizeof(*next_node),
	204	DRM_MEM_MM);
	205	} else {
	206	next_node->size += cur->size;
	207	next_node->start = cur->start;
a1d0fcf5	208	merged = 1;
3a1bd924 TH	209	}
	210	}
	211	}
	212	if (!merged) {
a1d0fcf5	213	cur->free = 1;
1d58420b	214	list_add(&cur->fl_entry, &mm->fl_entry);
3a1bd924 TH	215	} else {
	216	list_del(&cur->ml_entry);
	217	drm_free(cur, sizeof(*cur), DRM_MEM_MM);
	218	}
	219	}
	220
55910517	221	struct drm_mm_node drm_mm_search_free(const struct drm_mm mm,
3a1bd924 TH	222	unsigned long size,
	223	unsigned alignment, int best_match)
	224	{
	225	struct list_head *list;
1d58420b	226	const struct list_head *free_stack = &mm->fl_entry;
55910517 DA	227	struct drm_mm_node *entry;
55910517 DA	228	struct drm_mm_node *best;
3a1bd924	229	unsigned long best_size;
1d58420b	230	unsigned wasted;
3a1bd924 TH	231
	232	best = NULL;
	233	best_size = ~0UL;
	234
3a1bd924	235	list_for_each(list, free_stack) {
55910517	236	entry = list_entry(list, struct drm_mm_node, fl_entry);
1d58420b TH	237	wasted = 0;
	238
	239	if (entry->size < size)
	240	continue;
	241
	242	if (alignment) {
	243	register unsigned tmp = entry->start % alignment;
	244	if (tmp)
	245	wasted += alignment - tmp;
	246	}
	247
	248
	249	if (entry->size >= size + wasted) {
3a1bd924 TH	250	if (!best_match)
	251	return entry;
	252	if (size < best_size) {
	253	best = entry;
	254	best_size = entry->size;
	255	}
	256	}
	257	}
	258
	259	return best;
	260	}
	261
55910517	262	int drm_mm_clean(struct drm_mm * mm)
3a1bd924	263	{
1d58420b	264	struct list_head *head = &mm->ml_entry;
3a1bd924	265
1d58420b TH	266	return (head->next->next == head);
1d58420b TH	267	}
3a1bd924	268
55910517	269	int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
1d58420b TH	270	{
	271	INIT_LIST_HEAD(&mm->ml_entry);
	272	INIT_LIST_HEAD(&mm->fl_entry);
3a1bd924	273
1d58420b	274	return drm_mm_create_tail_node(mm, start, size);
3a1bd924 TH	275	}
3a1bd924 TH	276
3a1bd924	277
55910517	278	void drm_mm_takedown(struct drm_mm * mm)
3a1bd924	279	{
1d58420b	280	struct list_head *bnode = mm->fl_entry.next;
55910517	281	struct drm_mm_node *entry;
3a1bd924	282
55910517	283	entry = list_entry(bnode, struct drm_mm_node, fl_entry);
3a1bd924	284
1d58420b TH	285	if (entry->ml_entry.next != &mm->ml_entry \|\|
1d58420b TH	286	entry->fl_entry.next != &mm->fl_entry) {
3a1bd924 TH	287	DRM_ERROR("Memory manager not clean. Delaying takedown\n");
	288	return;
	289	}
	290
	291	list_del(&entry->fl_entry);
	292	list_del(&entry->ml_entry);
	293
	294	drm_free(entry, sizeof(*entry), DRM_MEM_MM);
	295	}
	296