Skip site navigation (1)Skip section navigation (2)
Date:      Sun, 31 Jan 2010 14:25:29 +0000 (UTC)
From:      Robert Noland <rnoland@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r203287 - in head/sys: conf dev/drm modules/drm/drm
Message-ID:  <201001311425.o0VEPTEo049344@svn.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: rnoland
Date: Sun Jan 31 14:25:29 2010
New Revision: 203287
URL: http://svn.freebsd.org/changeset/base/203287

Log:
  Import simple drm memory manager.
  
  This is required for the VIA driver and at least some parts are needed
  for GEM.
  
  MFC after:	2 weeks

Added:
  head/sys/dev/drm/drm_hashtab.c   (contents, props changed)
  head/sys/dev/drm/drm_hashtab.h   (contents, props changed)
  head/sys/dev/drm/drm_mm.c   (contents, props changed)
  head/sys/dev/drm/drm_mm.h   (contents, props changed)
  head/sys/dev/drm/drm_sman.c   (contents, props changed)
  head/sys/dev/drm/drm_sman.h   (contents, props changed)
Modified:
  head/sys/conf/files
  head/sys/dev/drm/drmP.h
  head/sys/dev/drm/drm_linux_list.h
  head/sys/dev/drm/drm_memory.c
  head/sys/dev/drm/i915_drv.c
  head/sys/dev/drm/i915_drv.h
  head/sys/modules/drm/drm/Makefile

Modified: head/sys/conf/files
==============================================================================
--- head/sys/conf/files	Sun Jan 31 14:25:09 2010	(r203286)
+++ head/sys/conf/files	Sun Jan 31 14:25:29 2010	(r203287)
@@ -839,12 +839,15 @@ dev/drm/drm_dma.c		optional drm
 dev/drm/drm_drawable.c		optional drm
 dev/drm/drm_drv.c		optional drm
 dev/drm/drm_fops.c		optional drm
+dev/drm/drm_hashtab.c		optional drm
 dev/drm/drm_ioctl.c		optional drm
 dev/drm/drm_irq.c		optional drm
 dev/drm/drm_lock.c		optional drm
 dev/drm/drm_memory.c		optional drm
+dev/drm/drm_mm.c		optional drm
 dev/drm/drm_pci.c		optional drm
 dev/drm/drm_scatter.c		optional drm
+dev/drm/drm_sman.c		optional drm
 dev/drm/drm_sysctl.c		optional drm
 dev/drm/drm_vm.c		optional drm
 dev/drm/i915_dma.c		optional i915drm

Modified: head/sys/dev/drm/drmP.h
==============================================================================
--- head/sys/dev/drm/drmP.h	Sun Jan 31 14:25:09 2010	(r203286)
+++ head/sys/dev/drm/drmP.h	Sun Jan 31 14:25:29 2010	(r203287)
@@ -91,9 +91,9 @@ struct drm_file;
 #include <sys/bus.h>
 
 #include "dev/drm/drm.h"
-#include "dev/drm/drm_linux_list.h"
 #include "dev/drm/drm_atomic.h"
 #include "dev/drm/drm_internal.h"
+#include "dev/drm/drm_linux_list.h"
 
 #include <opt_drm.h>
 #ifdef DRM_DEBUG
@@ -147,6 +147,8 @@ MALLOC_DECLARE(DRM_MEM_AGPLISTS);
 MALLOC_DECLARE(DRM_MEM_CTXBITMAP);
 MALLOC_DECLARE(DRM_MEM_SGLISTS);
 MALLOC_DECLARE(DRM_MEM_DRAWABLE);
+MALLOC_DECLARE(DRM_MEM_MM);
+MALLOC_DECLARE(DRM_MEM_HASHTAB);
 
 SYSCTL_DECL(_hw_drm);
 
@@ -193,6 +195,11 @@ typedef void			irqreturn_t;
 #define IRQ_HANDLED		/* nothing */
 #define IRQ_NONE		/* nothing */
 
+#define unlikely(x)            __builtin_expect(!!(x), 0)
+#define container_of(ptr, type, member) ({			\
+	__typeof( ((type *)0)->member ) *__mptr = (ptr);	\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+
 enum {
 	DRM_IS_NOT_AGP,
 	DRM_IS_AGP,

Added: head/sys/dev/drm/drm_hashtab.c
==============================================================================
--- /dev/null	00:00:00 1970	(empty, because file is newly added)
+++ head/sys/dev/drm/drm_hashtab.c	Sun Jan 31 14:25:29 2010	(r203287)
@@ -0,0 +1,180 @@
+/**************************************************************************
+ *
+ * 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.
+ *
+ *
+ **************************************************************************/
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+/*
+ * Simple open hash tab implementation.
+ *
+ * Authors:
+ * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
+ */
+
+#include "dev/drm/drmP.h"
+#include "dev/drm/drm_hashtab.h"
+
+#include <sys/hash.h>
+
+int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
+{
+	ht->size = 1 << order;
+	ht->order = order;
+	ht->table = NULL;
+	ht->table = hashinit(ht->size, DRM_MEM_HASHTAB, &ht->mask);
+	if (!ht->table) {
+		DRM_ERROR("Out of memory for hash table\n");
+		return -ENOMEM;
+	}
+	return 0;
+}
+
+void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
+{
+	struct drm_hash_item *entry;
+	struct drm_hash_item_list *h_list;
+	unsigned int hashed_key;
+	int count = 0;
+
+	hashed_key = hash32_buf(&key, sizeof(key), ht->order);
+	DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
+	h_list = &ht->table[hashed_key & ht->mask];
+	LIST_FOREACH(entry, h_list, head)
+		DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
+}
+
+static struct drm_hash_item *
+drm_ht_find_key(struct drm_open_hash *ht, unsigned long key)
+{
+	struct drm_hash_item *entry;
+	struct drm_hash_item_list *h_list;
+	unsigned int hashed_key;
+
+	hashed_key = hash32_buf(&key, sizeof(key), ht->order);
+	h_list = &ht->table[hashed_key & ht->mask];
+	LIST_FOREACH(entry, h_list, head) {
+		if (entry->key == key)
+			return entry;
+		if (entry->key > key)
+			break;
+	}
+	return NULL;
+}
+
+
+int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
+{
+	struct drm_hash_item *entry, *parent;
+	struct drm_hash_item_list *h_list;
+	unsigned int hashed_key;
+	unsigned long key = item->key;
+
+	hashed_key = hash32_buf(&key, sizeof(key), ht->order);
+	h_list = &ht->table[hashed_key & ht->mask];
+	parent = NULL;
+	LIST_FOREACH(entry, h_list, head) {
+		if (entry->key == key)
+			return -EINVAL;
+		if (entry->key > key)
+			break;
+		parent = entry;
+	}
+	if (parent) {
+		LIST_INSERT_AFTER(parent, item, head);
+	} else {
+		LIST_INSERT_HEAD(h_list, item, head);
+	}
+	return 0;
+}
+
+/*
+ * Just insert an item and return any "bits" bit key that hasn't been
+ * used before.
+ */
+int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
+			      unsigned long seed, int bits, int shift,
+			      unsigned long add)
+{
+	int ret;
+	unsigned long mask = (1 << bits) - 1;
+	unsigned long first, unshifted_key = 0;
+
+	unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key);
+	first = unshifted_key;
+	do {
+		item->key = (unshifted_key << shift) + add;
+		ret = drm_ht_insert_item(ht, item);
+		if (ret)
+			unshifted_key = (unshifted_key + 1) & mask;
+	} while(ret && (unshifted_key != first));
+
+	if (ret) {
+		DRM_ERROR("Available key bit space exhausted\n");
+		return -EINVAL;
+	}
+	return 0;
+}
+
+int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
+		     struct drm_hash_item **item)
+{
+	struct drm_hash_item *entry;
+
+	entry = drm_ht_find_key(ht, key);
+	if (!entry)
+		return -EINVAL;
+
+	*item = entry;
+	return 0;
+}
+
+int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
+{
+	struct drm_hash_item *entry;
+
+	entry = drm_ht_find_key(ht, key);
+	if (entry) {
+		LIST_REMOVE(entry, head);
+		return 0;
+	}
+	return -EINVAL;
+}
+
+int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
+{
+	LIST_REMOVE(item, head);
+	return 0;
+}
+
+void drm_ht_remove(struct drm_open_hash *ht)
+{
+	if (ht->table) {
+		hashdestroy(ht->table, DRM_MEM_HASHTAB, ht->mask);
+		ht->table = NULL;
+	}
+}

Added: head/sys/dev/drm/drm_hashtab.h
==============================================================================
--- /dev/null	00:00:00 1970	(empty, because file is newly added)
+++ head/sys/dev/drm/drm_hashtab.h	Sun Jan 31 14:25:29 2010	(r203287)
@@ -0,0 +1,68 @@
+/**************************************************************************
+ *
+ * Copyright 2006 Tungsten Graphics, Inc., Bismack, 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.
+ *
+ *
+ **************************************************************************/
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+/*
+ * Simple open hash tab implementation.
+ *
+ * Authors:
+ * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
+ */
+
+#ifndef DRM_HASHTAB_H
+#define DRM_HASHTAB_H
+
+#define drm_hash_entry(_ptr, _type, _member) container_of(_ptr, _type, _member)
+
+struct drm_hash_item {
+	LIST_ENTRY(drm_hash_item) head;
+	unsigned long key;
+};
+
+struct drm_open_hash {
+	LIST_HEAD(drm_hash_item_list, drm_hash_item) *table;
+	unsigned int  size;
+	unsigned int order;
+	unsigned long mask;
+};
+
+extern int drm_ht_create(struct drm_open_hash *ht, unsigned int order);
+extern int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item);
+extern int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
+				     unsigned long seed, int bits, int shift,
+				     unsigned long add);
+extern int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key, struct drm_hash_item **item);
+
+extern void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key);
+extern int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key);
+extern int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item);
+extern void drm_ht_remove(struct drm_open_hash *ht);
+
+#endif

Modified: head/sys/dev/drm/drm_linux_list.h
==============================================================================
--- head/sys/dev/drm/drm_linux_list.h	Sun Jan 31 14:25:09 2010	(r203286)
+++ head/sys/dev/drm/drm_linux_list.h	Sun Jan 31 14:25:29 2010	(r203287)
@@ -32,12 +32,15 @@
 #include <sys/cdefs.h>
 __FBSDID("$FreeBSD$");
 
+#ifndef _DRM_LINUX_LIST_H_
+#define _DRM_LINUX_LIST_H_
+
 struct list_head {
 	struct list_head *next, *prev;
 };
 
-/* Cheat, assume the list_head is at the start of the struct */
-#define list_entry(entry, type, member)	(type *)(entry)
+#define list_entry(ptr, type, member) container_of(ptr,type,member)
+#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 
 static __inline__ void
 INIT_LIST_HEAD(struct list_head *head) {
@@ -51,6 +54,14 @@ list_empty(struct list_head *head) {
 }
 
 static __inline__ void
+list_add(struct list_head *new, struct list_head *head) {
+        (head)->next->prev = new;
+        (new)->next = (head)->next;
+        (new)->prev = head;
+        (head)->next = new;
+}
+
+static __inline__ void
 list_add_tail(struct list_head *entry, struct list_head *head) {
 	(entry)->prev = (head)->prev;
 	(entry)->next = head;
@@ -64,6 +75,13 @@ list_del(struct list_head *entry) {
 	(entry)->prev->next = (entry)->next;
 }
 
+static __inline__ void
+list_del_init(struct list_head *entry) {
+	(entry)->next->prev = (entry)->prev;
+	(entry)->prev->next = (entry)->next;
+	INIT_LIST_HEAD(entry);
+}
+
 #define list_for_each(entry, head)				\
     for (entry = (head)->next; entry != head; entry = (entry)->next)
 
@@ -76,3 +94,17 @@ list_del(struct list_head *entry) {
 	entry != head; 						\
 	entry = temp, temp = entry->next)
 
+/**
+ * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @pos:        the type * to use as a loop cursor.
+ * @n:          another type * to use as temporary storage
+ * @head:       the head for your list.
+ * @member:     the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = list_entry((head)->next, __typeof(*pos), member),	\
+	    n = list_entry(pos->member.next, __typeof(*pos), member);	\
+	    &pos->member != (head);					\
+	    pos = n, n = list_entry(n->member.next, __typeof(*n), member))
+
+#endif /* _DRM_LINUX_LIST_H_ */

Modified: head/sys/dev/drm/drm_memory.c
==============================================================================
--- head/sys/dev/drm/drm_memory.c	Sun Jan 31 14:25:09 2010	(r203286)
+++ head/sys/dev/drm/drm_memory.c	Sun Jan 31 14:25:29 2010	(r203287)
@@ -60,6 +60,8 @@ MALLOC_DEFINE(DRM_MEM_CTXBITMAP, "drm_ct
     "DRM CTXBITMAP Data Structures");
 MALLOC_DEFINE(DRM_MEM_SGLISTS, "drm_sglists", "DRM SGLISTS Data Structures");
 MALLOC_DEFINE(DRM_MEM_DRAWABLE, "drm_drawable", "DRM DRAWABLE Data Structures");
+MALLOC_DEFINE(DRM_MEM_MM, "drm_sman", "DRM MEMORY MANAGER Data Structures");
+MALLOC_DEFINE(DRM_MEM_HASHTAB, "drm_hashtab", "DRM HASHTABLE Data Structures");
 
 void drm_mem_init(void)
 {

Added: head/sys/dev/drm/drm_mm.c
==============================================================================
--- /dev/null	00:00:00 1970	(empty, because file is newly added)
+++ head/sys/dev/drm/drm_mm.c	Sun Jan 31 14:25:29 2010	(r203287)
@@ -0,0 +1,368 @@
+/**************************************************************************
+ *
+ * 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.
+ *
+ *
+ **************************************************************************/
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+/*
+ * 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 "dev/drm/drmP.h"
+#include "dev/drm/drm_mm.h"
+
+#define MM_UNUSED_TARGET 4
+
+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 struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
+{
+	struct drm_mm_node *child;
+
+	if (atomic)
+		child = malloc(sizeof(*child), DRM_MEM_MM, M_NOWAIT);
+	else
+		child = malloc(sizeof(*child), DRM_MEM_MM, M_WAITOK);
+
+	if (unlikely(child == NULL)) {
+		mtx_lock(&mm->unused_lock);
+		if (list_empty(&mm->unused_nodes))
+			child = NULL;
+		else {
+			child =
+			    list_entry(mm->unused_nodes.next,
+				       struct drm_mm_node, fl_entry);
+			list_del(&child->fl_entry);
+			--mm->num_unused;
+		}
+		mtx_unlock(&mm->unused_lock);
+	}
+	return child;
+}
+
+int drm_mm_pre_get(struct drm_mm *mm)
+{
+	struct drm_mm_node *node;
+
+	mtx_lock(&mm->unused_lock);
+	while (mm->num_unused < MM_UNUSED_TARGET) {
+		mtx_unlock(&mm->unused_lock);
+		node = malloc(sizeof(*node), DRM_MEM_MM, M_WAITOK);
+		mtx_lock(&mm->unused_lock);
+
+		if (unlikely(node == NULL)) {
+			int ret = (mm->num_unused < 2) ? -ENOMEM : 0;
+			mtx_unlock(&mm->unused_lock);
+			return ret;
+		}
+		++mm->num_unused;
+		list_add_tail(&node->fl_entry, &mm->unused_nodes);
+	}
+	mtx_unlock(&mm->unused_lock);
+	return 0;
+}
+
+static int drm_mm_create_tail_node(struct drm_mm *mm,
+				   unsigned long start,
+				   unsigned long size, int atomic)
+{
+	struct drm_mm_node *child;
+
+	child = drm_mm_kmalloc(mm, atomic);
+	if (unlikely(child == NULL))
+		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, int atomic)
+{
+	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, atomic);
+	}
+	entry->size += size;
+	return 0;
+}
+
+static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent,
+						 unsigned long size,
+						 int atomic)
+{
+	struct drm_mm_node *child;
+
+	child = drm_mm_kmalloc(parent->mm, atomic);
+	if (unlikely(child == NULL))
+		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_generic(struct drm_mm_node *node,
+					     unsigned long size,
+					     unsigned alignment,
+					     int atomic)
+{
+
+	struct drm_mm_node *align_splitoff = NULL;
+	unsigned tmp = 0;
+
+	if (alignment)
+		tmp = node->start % alignment;
+
+	if (tmp) {
+		align_splitoff =
+		    drm_mm_split_at_start(node, alignment - tmp, atomic);
+		if (unlikely(align_splitoff == NULL))
+			return NULL;
+	}
+
+	if (node->size == size) {
+		list_del_init(&node->fl_entry);
+		node->free = 0;
+	} else {
+		node = drm_mm_split_at_start(node, size, atomic);
+	}
+
+	if (align_splitoff)
+		drm_mm_put_block(align_splitoff);
+
+	return node;
+}
+
+/*
+ * 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);
+				if (mm->num_unused < MM_UNUSED_TARGET) {
+					list_add(&next_node->fl_entry,
+						 &mm->unused_nodes);
+					++mm->num_unused;
+				} else
+					free(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);
+		if (mm->num_unused < MM_UNUSED_TARGET) {
+			list_add(&cur->fl_entry, &mm->unused_nodes);
+			++mm->num_unused;
+		} else
+			free(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);
+	INIT_LIST_HEAD(&mm->unused_nodes);
+	mm->num_unused = 0;
+	mtx_init(&mm->unused_lock, "drm_unused", NULL, MTX_DEF);
+
+	return drm_mm_create_tail_node(mm, start, size, 0);
+}
+
+void drm_mm_takedown(struct drm_mm * mm)
+{
+	struct list_head *bnode = mm->fl_entry.next;
+	struct drm_mm_node *entry;
+	struct drm_mm_node *next;
+
+	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);
+	free(entry, DRM_MEM_MM);
+
+	mtx_lock(&mm->unused_lock);
+	list_for_each_entry_safe(entry, next, &mm->unused_nodes, fl_entry) {
+		list_del(&entry->fl_entry);
+		free(entry, DRM_MEM_MM);
+		--mm->num_unused;
+	}
+	mtx_unlock(&mm->unused_lock);
+
+	mtx_destroy(&mm->unused_lock);
+
+	KASSERT(mm->num_unused == 0, ("num_unused != 0"));
+}

Added: head/sys/dev/drm/drm_mm.h
==============================================================================
--- /dev/null	00:00:00 1970	(empty, because file is newly added)
+++ head/sys/dev/drm/drm_mm.h	Sun Jan 31 14:25:29 2010	(r203287)
@@ -0,0 +1,100 @@
+/**************************************************************************
+ *
+ * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. 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.
+ *
+ *
+ **************************************************************************/
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+/*
+ * Authors:
+ * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
+ */
+
+#ifndef _DRM_MM_H_
+#define _DRM_MM_H_
+
+#include "dev/drm/drm_linux_list.h"
+
+struct drm_mm_node {
+	struct list_head fl_entry;
+	struct list_head ml_entry;
+	int free;
+	unsigned long start;
+	unsigned long size;
+	struct drm_mm *mm;
+	void *private;
+};
+
+struct drm_mm {
+	struct list_head fl_entry;
+	struct list_head ml_entry;
+	struct list_head unused_nodes;
+	int num_unused;
+	struct mtx unused_lock;
+};
+
+/*
+ * Basic range manager support (drm_mm.c)
+ */
+extern struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *node,
+						    unsigned long size,
+						    unsigned alignment,
+						    int atomic);
+static inline struct drm_mm_node *drm_mm_get_block(struct drm_mm_node *parent,
+						   unsigned long size,
+						   unsigned alignment)
+{
+	return drm_mm_get_block_generic(parent, size, alignment, 0);
+}
+static inline struct drm_mm_node *drm_mm_get_block_atomic(struct drm_mm_node *parent,
+							  unsigned long size,
+							  unsigned alignment)
+{
+	return drm_mm_get_block_generic(parent, size, alignment, 1);
+}
+extern void drm_mm_put_block(struct drm_mm_node *cur);
+extern struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
+					      unsigned long size,
+					      unsigned alignment,
+					      int best_match);
+extern int drm_mm_init(struct drm_mm *mm, unsigned long start,
+		       unsigned long size);
+extern void drm_mm_takedown(struct drm_mm *mm);
+extern int drm_mm_clean(struct drm_mm *mm);
+extern unsigned long drm_mm_tail_space(struct drm_mm *mm);
+extern int drm_mm_remove_space_from_tail(struct drm_mm *mm,
+					 unsigned long size);
+extern int drm_mm_add_space_to_tail(struct drm_mm *mm,
+				    unsigned long size, int atomic);
+extern int drm_mm_pre_get(struct drm_mm *mm);
+
+static inline struct drm_mm *drm_get_mm(struct drm_mm_node *block)
+{
+	return block->mm;
+}
+
+#endif

Added: head/sys/dev/drm/drm_sman.c
==============================================================================
--- /dev/null	00:00:00 1970	(empty, because file is newly added)
+++ head/sys/dev/drm/drm_sman.c	Sun Jan 31 14:25:29 2010	(r203287)
@@ -0,0 +1,352 @@
+/**************************************************************************
+ *
+ * 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 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.
+ *
+ * The above copyright notice and this permission notice (including the
+ * next paragraph) shall be included in all copies or substantial portions
+ * of the Software.
+ *
+ *
+ **************************************************************************/
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+/*
+ * Simple memory manager interface that keeps track on allocate regions on a
+ * per "owner" basis. All regions associated with an "owner" can be released
+ * with a simple call. Typically if the "owner" exists. The owner is any
+ * "unsigned long" identifier. Can typically be a pointer to a file private
+ * struct or a context identifier.
+ *
+ * Authors:
+ * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
+ */
+
+#include "dev/drm/drmP.h"
+#include "dev/drm/drm_sman.h"
+
+struct drm_owner_item {
+	struct drm_hash_item owner_hash;
+	struct list_head sman_list;
+	struct list_head mem_blocks;
+};
+
+void drm_sman_takedown(struct drm_sman * sman)
+{
+	drm_ht_remove(&sman->user_hash_tab);
+	drm_ht_remove(&sman->owner_hash_tab);
+	if (sman->mm)
+		drm_free(sman->mm, sman->num_managers * sizeof(*sman->mm),
+		    DRM_MEM_MM);
+}
+
+int
+drm_sman_init(struct drm_sman * sman, unsigned int num_managers,
+	      unsigned int user_order, unsigned int owner_order)
+{
+	int ret = 0;
+
+	sman->mm = (struct drm_sman_mm *) drm_calloc(num_managers,
+	    sizeof(*sman->mm), DRM_MEM_MM);
+	if (!sman->mm) {
+		ret = -ENOMEM;
+		goto out;
+	}
+	sman->num_managers = num_managers;
+	INIT_LIST_HEAD(&sman->owner_items);
+	ret = drm_ht_create(&sman->owner_hash_tab, owner_order);
+	if (ret)
+		goto out1;
+	ret = drm_ht_create(&sman->user_hash_tab, user_order);
+	if (!ret)
+		goto out;
+
+	drm_ht_remove(&sman->owner_hash_tab);
+out1:
+	drm_free(sman->mm, num_managers * sizeof(*sman->mm), DRM_MEM_MM);
+out:
+	return ret;
+}
+
+static void *drm_sman_mm_allocate(void *private, unsigned long size,
+				  unsigned alignment)
+{
+	struct drm_mm *mm = (struct drm_mm *) private;
+	struct drm_mm_node *tmp;
+
+	tmp = drm_mm_search_free(mm, size, alignment, 1);
+	if (!tmp) {
+		return NULL;
+	}
+	tmp = drm_mm_get_block(tmp, size, alignment);
+	return tmp;
+}
+
+static void drm_sman_mm_free(void *private, void *ref)
+{
+	struct drm_mm_node *node = (struct drm_mm_node *) ref;
+
+	drm_mm_put_block(node);
+}
+
+static void drm_sman_mm_destroy(void *private)
+{
+	struct drm_mm *mm = (struct drm_mm *) private;
+	drm_mm_takedown(mm);
+	drm_free(mm, sizeof(*mm), DRM_MEM_MM);
+}
+
+static unsigned long drm_sman_mm_offset(void *private, void *ref)
+{
+	struct drm_mm_node *node = (struct drm_mm_node *) ref;
+	return node->start;
+}
+
+int
+drm_sman_set_range(struct drm_sman * sman, unsigned int manager,
+		   unsigned long start, unsigned long size)
+{
+	struct drm_sman_mm *sman_mm;
+	struct drm_mm *mm;
+	int ret;
+
+	KASSERT(manager < sman->num_managers, ("Invalid manager"));
+
+	sman_mm = &sman->mm[manager];
+	mm = malloc(sizeof(*mm), DRM_MEM_MM, M_WAITOK | M_ZERO);
+	if (!mm) {
+		return -ENOMEM;
+	}
+	sman_mm->private = mm;
+	ret = drm_mm_init(mm, start, size);

*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001311425.o0VEPTEo049344>