Merge branch 'drm-patches' of git://git.kernel.org/pub/scm/linux/kernel/git/airlied/drm-2.6

* 'drm-patches' of git://git.kernel.org/pub/scm/linux/kernel/git/airlied/drm-2.6: (36 commits)
  drm: Use register writes instead of BITBLT_MULTI packets for buffer swap blits
  drm: use radeon specific names for radeon flags
  drm: add device/vendor id to drm_device_t for compat with FreeBSD drivers
  drm: allow multiple addMaps with the same 32-bit map offsset.
  drm: fd.o Bug #7595: Avoid u32 overflows in radeon_check_and_fixup_offset().
  drm: Fix hashtab implementation leaking illegal error codes to user space.
  drm: domain changes broke ppc r200
  drm: fixup setversion return codes..
  drm: fixup i915 error codes
  drm: realign sosme radeon code with drm git tree
  drm: realign via driver with drm git tree
  drm: remove hash tables on drm exit
  drm: cleanups
  drm: i810_dma.c: fix pointer arithmetic for 64-bit target
  drm: avoid kernel oops in some error paths calling drm_lastclose
  drm: allow detection of new VIA chipsets
  drm: fix i965 build bug
  drm: remove FALSE/TRUE that snuck in with simple memory manager changes.
  drm: Add support for Intel i965G chipsets.
  drm: add better explanation for i830/i915
  ...

42 files changed, 1878 insertions, 1772 deletions

diff --git a/drivers/char/drm/Kconfig b/drivers/char/drm/Kconfig
index 5278c388d3e..ef833a1c27e 100644
--- a/drivers/char/drm/Kconfig
+++ b/drivers/char/drm/Kconfig
@@ -60,7 +60,9 @@ config DRM_I830
 	  Choose this option if you have a system that has Intel 830M, 845G,
 	  852GM, 855GM or 865G integrated graphics.  If M is selected, the
 	  module will be called i830.  AGP support is required for this driver
-	  to work. This driver will eventually be replaced by the i915 one.
+	  to work. This driver is used by the older X releases X.org 6.7 and
+	  XFree86 4.3. If unsure, build this and i915 as modules and the X server
+	  will load the correct one.
 
 config DRM_I915
 	tristate "i915 driver"
@@ -68,8 +70,9 @@ config DRM_I915
 	  Choose this option if you have a system that has Intel 830M, 845G,
 	  852GM, 855GM 865G or 915G integrated graphics.  If M is selected, the
 	  module will be called i915.  AGP support is required for this driver
-	  to work. This driver will eventually replace the I830 driver, when
-	  later release of X start to use the new DDX and DRI.
+	  to work. This driver is used by the Intel driver in X.org 6.8 and
+	  XFree86 4.4 and above. If unsure, build this and i830 as modules and 
+	  the X server will load the correct one.
 	
 endchoice
 
diff --git a/drivers/char/drm/Makefile b/drivers/char/drm/Makefile
index 9d180c42816..3ad0f648c6b 100644
--- a/drivers/char/drm/Makefile
+++ b/drivers/char/drm/Makefile
@@ -6,7 +6,7 @@ drm-objs    :=	drm_auth.o drm_bufs.o drm_context.o drm_dma.o drm_drawable.o \
 		drm_drv.o drm_fops.o drm_ioctl.o drm_irq.o \
 		drm_lock.o drm_memory.o drm_proc.o drm_stub.o drm_vm.o \
 		drm_agpsupport.o drm_scatter.o ati_pcigart.o drm_pci.o \
-		drm_sysfs.o
+		drm_sysfs.o drm_hashtab.o drm_sman.o drm_mm.o
 
 tdfx-objs   := tdfx_drv.o
 r128-objs   := r128_drv.o r128_cce.o r128_state.o r128_irq.o
@@ -16,9 +16,9 @@ i830-objs   := i830_drv.o i830_dma.o i830_irq.o
 i915-objs   := i915_drv.o i915_dma.o i915_irq.o i915_mem.o
 radeon-objs := radeon_drv.o radeon_cp.o radeon_state.o radeon_mem.o radeon_irq.o r300_cmdbuf.o
 ffb-objs    := ffb_drv.o ffb_context.o
-sis-objs    := sis_drv.o sis_ds.o sis_mm.o
+sis-objs    := sis_drv.o sis_mm.o
 savage-objs := savage_drv.o savage_bci.o savage_state.o
-via-objs    := via_irq.o via_drv.o via_ds.o via_map.o via_mm.o via_dma.o via_verifier.o via_video.o via_dmablit.o
+via-objs    := via_irq.o via_drv.o via_map.o via_mm.o via_dma.o via_verifier.o via_video.o via_dmablit.o
 
 ifeq ($(CONFIG_COMPAT),y)
 drm-objs    += drm_ioc32.o
diff --git a/drivers/char/drm/drmP.h b/drivers/char/drm/drmP.h
index d2a56182bc3..7690a59ace0 100644
--- a/drivers/char/drm/drmP.h
+++ b/drivers/char/drm/drmP.h
@@ -79,6 +79,7 @@
 #define __OS_HAS_MTRR (defined(CONFIG_MTRR))
 
 #include "drm_os_linux.h"
+#include "drm_hashtab.h"
 
 /***********************************************************************/
 /** \name DRM template customization defaults */
@@ -104,7 +105,7 @@
 #define DRM_DEBUG_CODE 2	  /**< Include debugging code if > 1, then
 				     also include looping detection. */
 
-#define DRM_HASH_SIZE	      16 /**< Size of key hash table. Must be power of 2. */
+#define DRM_MAGIC_HASH_ORDER  4  /**< Size of key hash table. Must be power of 2. */
 #define DRM_KERNEL_CONTEXT    0	 /**< Change drm_resctx if changed */
 #define DRM_RESERVED_CONTEXTS 1	 /**< Change drm_resctx if changed */
 #define DRM_LOOPING_LIMIT     5000000
@@ -134,19 +135,12 @@
 #define DRM_MEM_CTXBITMAP 18
 #define DRM_MEM_STUB      19
 #define DRM_MEM_SGLISTS   20
-#define DRM_MEM_CTXLIST  21
+#define DRM_MEM_CTXLIST   21
+#define DRM_MEM_MM        22
+#define DRM_MEM_HASHTAB   23
 
 #define DRM_MAX_CTXBITMAP (PAGE_SIZE * 8)
-
-/*@}*/
-
-/***********************************************************************/
-/** \name Backward compatibility section */
-/*@{*/
-
-#define DRM_RPR_ARG(vma) vma,
-
-#define VM_OFFSET(vma) ((vma)->vm_pgoff << PAGE_SHIFT)
+#define DRM_MAP_HASH_OFFSET 0x10000000
 
 /*@}*/
 
@@ -211,8 +205,6 @@
 /*@{*/
 
 #define DRM_ARRAY_SIZE(x) ARRAY_SIZE(x)
-#define DRM_MIN(a,b) min(a,b)
-#define DRM_MAX(a,b) max(a,b)
 
 #define DRM_LEFTCOUNT(x) (((x)->rp + (x)->count - (x)->wp) % ((x)->count + 1))
 #define DRM_BUFCOUNT(x) ((x)->count - DRM_LEFTCOUNT(x))
@@ -286,7 +278,8 @@ typedef struct drm_devstate {
 } drm_devstate_t;
 
 typedef struct drm_magic_entry {
-	drm_magic_t magic;
+	drm_hash_item_t hash_item;
+	struct list_head head;
 	struct drm_file *priv;
 	struct drm_magic_entry *next;
 } drm_magic_entry_t;
@@ -493,6 +486,7 @@ typedef struct drm_sigdata {
  */
 typedef struct drm_map_list {
 	struct list_head head;		/**< list head */
+	drm_hash_item_t hash;
 	drm_map_t *map;			/**< mapping */
 	unsigned int user_token;
 } drm_map_list_t;
@@ -527,6 +521,22 @@ typedef struct ati_pcigart_info {
 	drm_local_map_t mapping;
 } drm_ati_pcigart_info;
 
+/*
+ * Generic memory manager structs
+ */
+typedef struct drm_mm_node {
+	struct list_head fl_entry;
+	struct list_head ml_entry;
+	int free;
+	unsigned long start;
+	unsigned long size;
+	void *private;
+} drm_mm_node_t;
+
+typedef struct drm_mm {
+	drm_mm_node_t root_node;
+} drm_mm_t;
+
 /**
  * DRM driver structure. This structure represent the common code for
  * a family of cards. There will one drm_device for each card present
@@ -646,13 +656,15 @@ typedef struct drm_device {
 	/*@{ */
 	drm_file_t *file_first;		/**< file list head */
 	drm_file_t *file_last;		/**< file list tail */
-	drm_magic_head_t magiclist[DRM_HASH_SIZE];	/**< magic hash table */
+	drm_open_hash_t magiclist;	/**< magic hash table */
+	struct list_head magicfree;
 	/*@} */
 
 	/** \name Memory management */
 	/*@{ */
 	drm_map_list_t *maplist;	/**< Linked list of regions */
 	int map_count;			/**< Number of mappable regions */
+	drm_open_hash_t map_hash;	/**< User token hash table for maps */
 
 	/** \name Context handle management */
 	/*@{ */
@@ -711,10 +723,8 @@ typedef struct drm_device {
 	drm_agp_head_t *agp;	/**< AGP data */
 
 	struct pci_dev *pdev;		/**< PCI device structure */
-	int pci_domain;			/**< PCI bus domain number */
-	int pci_bus;			/**< PCI bus number */
-	int pci_slot;			/**< PCI slot number */
-	int pci_func;			/**< PCI function number */
+	int pci_vendor;			/**< PCI vendor id */
+	int pci_device;			/**< PCI device id */
 #ifdef __alpha__
 	struct pci_controller *hose;
 #endif
@@ -736,6 +746,12 @@ static __inline__ int drm_core_check_feature(struct drm_device *dev,
 	return ((dev->driver->driver_features & feature) ? 1 : 0);
 }
 
+#ifdef __alpha__
+#define drm_get_pci_domain(dev) dev->hose->bus->number
+#else
+#define drm_get_pci_domain(dev) 0
+#endif
+
 #if __OS_HAS_AGP
 static inline int drm_core_has_AGP(struct drm_device *dev)
 {
@@ -1011,6 +1027,18 @@ extern struct class_device *drm_sysfs_device_add(struct class *cs,
 						 drm_head_t *head);
 extern void drm_sysfs_device_remove(struct class_device *class_dev);
 
+/*
+ * Basic memory manager support (drm_mm.c)
+ */
+extern drm_mm_node_t *drm_mm_get_block(drm_mm_node_t * parent,
+				       unsigned long size,
+				       unsigned alignment);
+extern void drm_mm_put_block(drm_mm_t *mm, drm_mm_node_t *cur);
+extern drm_mm_node_t *drm_mm_search_free(const drm_mm_t *mm, unsigned long size,
+					 unsigned alignment, int best_match);
+extern int drm_mm_init(drm_mm_t *mm, unsigned long start, unsigned long size);
+extern void drm_mm_takedown(drm_mm_t *mm);
+
 /* Inline replacements for DRM_IOREMAP macros */
 static __inline__ void drm_core_ioremap(struct drm_map *map,
 					struct drm_device *dev)
diff --git a/drivers/char/drm/drm_auth.c b/drivers/char/drm/drm_auth.c
index 2a37586a7ee..c7b19d35bcd 100644
--- a/drivers/char/drm/drm_auth.c
+++ b/drivers/char/drm/drm_auth.c
@@ -36,20 +36,6 @@
 #include "drmP.h"
 
 /**
- * Generate a hash key from a magic.
- *
- * \param magic magic.
- * \return hash key.
- *
- * The key is the modulus of the hash table size, #DRM_HASH_SIZE, which must be
- * a power of 2.
- */
-static int drm_hash_magic(drm_magic_t magic)
-{
-	return magic & (DRM_HASH_SIZE - 1);
-}
-
-/**
  * Find the file with the given magic number.
  *
  * \param dev DRM device.
@@ -63,14 +49,12 @@ static drm_file_t *drm_find_file(drm_device_t * dev, drm_magic_t magic)
 {
 	drm_file_t *retval = NULL;
 	drm_magic_entry_t *pt;
-	int hash = drm_hash_magic(magic);
+	drm_hash_item_t *hash;
 
 	mutex_lock(&dev->struct_mutex);
-	for (pt = dev->magiclist[hash].head; pt; pt = pt->next) {
-		if (pt->magic == magic) {
-			retval = pt->priv;
-			break;
-		}
+	if (!drm_ht_find_item(&dev->magiclist, (unsigned long)magic, &hash)) {
+		pt = drm_hash_entry(hash, drm_magic_entry_t, hash_item);
+		retval = pt->priv;
 	}
 	mutex_unlock(&dev->struct_mutex);
 	return retval;
@@ -90,28 +74,20 @@ static drm_file_t *drm_find_file(drm_device_t * dev, drm_magic_t magic)
 static int drm_add_magic(drm_device_t * dev, drm_file_t * priv,
 			 drm_magic_t magic)
 {
-	int hash;
 	drm_magic_entry_t *entry;
 
 	DRM_DEBUG("%d\n", magic);
 
-	hash = drm_hash_magic(magic);
 	entry = drm_alloc(sizeof(*entry), DRM_MEM_MAGIC);
 	if (!entry)
 		return -ENOMEM;
 	memset(entry, 0, sizeof(*entry));
-	entry->magic = magic;
 	entry->priv = priv;
-	entry->next = NULL;
 
+	entry->hash_item.key = (unsigned long)magic;
 	mutex_lock(&dev->struct_mutex);
-	if (dev->magiclist[hash].tail) {
-		dev->magiclist[hash].tail->next = entry;
-		dev->magiclist[hash].tail = entry;
-	} else {
-		dev->magiclist[hash].head = entry;
-		dev->magiclist[hash].tail = entry;
-	}
+	drm_ht_insert_item(&dev->magiclist, &entry->hash_item);
+	list_add_tail(&entry->head, &dev->magicfree);
 	mutex_unlock(&dev->struct_mutex);
 
 	return 0;
@@ -128,34 +104,24 @@ static int drm_add_magic(drm_device_t * dev, drm_file_t * priv,
  */
 static int drm_remove_magic(drm_device_t * dev, drm_magic_t magic)
 {
-	drm_magic_entry_t *prev = NULL;
 	drm_magic_entry_t *pt;
-	int hash;
+	drm_hash_item_t *hash;
 
 	DRM_DEBUG("%d\n", magic);
-	hash = drm_hash_magic(magic);
 
 	mutex_lock(&dev->struct_mutex);
-	for (pt = dev->magiclist[hash].head; pt; prev = pt, pt = pt->next) {
-		if (pt->magic == magic) {
-			if (dev->magiclist[hash].head == pt) {
-				dev->magiclist[hash].head = pt->next;
-			}
-			if (dev->magiclist[hash].tail == pt) {
-				dev->magiclist[hash].tail = prev;
-			}
-			if (prev) {
-				prev->next = pt->next;
-			}
-			mutex_unlock(&dev->struct_mutex);
-			return 0;
-		}
+	if (drm_ht_find_item(&dev->magiclist, (unsigned long)magic, &hash)) {
+		mutex_unlock(&dev->struct_mutex);
+		return -EINVAL;
 	}
+	pt = drm_hash_entry(hash, drm_magic_entry_t, hash_item);
+	drm_ht_remove_item(&dev->magiclist, hash);
+	list_del(&pt->head);
 	mutex_unlock(&dev->struct_mutex);
 
 	drm_free(pt, sizeof(*pt), DRM_MEM_MAGIC);
 
-	return -EINVAL;
+	return 0;
 }
 
 /**
diff --git a/drivers/char/drm/drm_bufs.c b/drivers/char/drm/drm_bufs.c
index 006b06d2972..029baea33b6 100644
--- a/drivers/char/drm/drm_bufs.c
+++ b/drivers/char/drm/drm_bufs.c
@@ -65,43 +65,29 @@ static drm_map_list_t *drm_find_matching_map(drm_device_t *dev,
 	return NULL;
 }
 
-/*
- * Used to allocate 32-bit handles for mappings.
- */
-#define START_RANGE 0x10000000
-#define END_RANGE 0x40000000
-
-#ifdef _LP64
-static __inline__ unsigned int HandleID(unsigned long lhandle,
-					drm_device_t *dev)
+static int drm_map_handle(drm_device_t *dev, drm_hash_item_t *hash,
+			  unsigned long user_token, int hashed_handle)
 {
-	static unsigned int map32_handle = START_RANGE;
-	unsigned int hash;
-
-	if (lhandle & 0xffffffff00000000) {
-		hash = map32_handle;
-		map32_handle += PAGE_SIZE;
-		if (map32_handle > END_RANGE)
-			map32_handle = START_RANGE;
-	} else
-		hash = lhandle;
-
-	while (1) {
-		drm_map_list_t *_entry;
-		list_for_each_entry(_entry, &dev->maplist->head, head) {
-			if (_entry->user_token == hash)
-				break;
-		}
-		if (&_entry->head == &dev->maplist->head)
-			return hash;
+	int use_hashed_handle;
+#if (BITS_PER_LONG == 64)
+	use_hashed_handle = ((user_token & 0xFFFFFFFF00000000UL) || hashed_handle);
+#elif (BITS_PER_LONG == 32)
+	use_hashed_handle = hashed_handle;
+#else
+#error Unsupported long size. Neither 64 nor 32 bits.
+#endif
 
-		hash += PAGE_SIZE;
-		map32_handle += PAGE_SIZE;
+	if (!use_hashed_handle) {
+		int ret;
+		hash->key = user_token;
+		ret = drm_ht_insert_item(&dev->map_hash, hash);
+		if (ret != -EINVAL)
+			return ret;
 	}
+	return drm_ht_just_insert_please(&dev->map_hash, hash,
+					 user_token, 32 - PAGE_SHIFT - 3,
+					 PAGE_SHIFT, DRM_MAP_HASH_OFFSET);
 }
-#else
-# define HandleID(x,dev) (unsigned int)(x)
-#endif
 
 /**
  * Ioctl to specify a range of memory that is available for mapping by a non-root process.
@@ -123,6 +109,8 @@ static int drm_addmap_core(drm_device_t * dev, unsigned int offset,
 	drm_map_t *map;
 	drm_map_list_t *list;
 	drm_dma_handle_t *dmah;
+	unsigned long user_token;
+	int ret;
 
 	map = drm_alloc(sizeof(*map), DRM_MEM_MAPS);
 	if (!map)
@@ -257,11 +245,20 @@ static int drm_addmap_core(drm_device_t * dev, unsigned int offset,
 
 	mutex_lock(&dev->struct_mutex);
 	list_add(&list->head, &dev->maplist->head);
+
 	/* Assign a 32-bit handle */
 	/* We do it here so that dev->struct_mutex protects the increment */
-	list->user_token = HandleID(map->type == _DRM_SHM
-				    ? (unsigned long)map->handle
-				    : map->offset, dev);
+	user_token = (map->type == _DRM_SHM) ? (unsigned long)map->handle :
+		map->offset;
+	ret = drm_map_handle(dev, &list->hash, user_token, 0);
+	if (ret) {
+		drm_free(map, sizeof(*map), DRM_MEM_MAPS);
+		drm_free(list, sizeof(*list), DRM_MEM_MAPS);
+		mutex_unlock(&dev->struct_mutex);
+		return ret;
+	}
+
+	list->user_token = list->hash.key;
 	mutex_unlock(&dev->struct_mutex);
 
 	*maplist = list;
@@ -346,6 +343,7 @@ int drm_rmmap_locked(drm_device_t *dev, drm_local_map_t *map)
 
 		if (r_list->map == map) {
 			list_del(list);
+			drm_ht_remove_key(&dev->map_hash, r_list->user_token);
 			drm_free(list, sizeof(*list), DRM_MEM_MAPS);
 			break;
 		}
@@ -441,8 +439,10 @@ int drm_rmmap_ioctl(struct inode *inode, struct file *filp,
 		return -EINVAL;
 	}
 
-	if (!map)
+	if (!map) {
+		mutex_unlock(&dev->struct_mutex);
 		return -EINVAL;
+	}
 
 	/* Register and framebuffer maps are permanent */
 	if ((map->type == _DRM_REGISTERS) || (map->type == _DRM_FRAME_BUFFER)) {
diff --git a/drivers/char/drm/drm_drv.c b/drivers/char/drm/drm_drv.c
index 3c0b882a8e7..b366c5b1bd1 100644
--- a/drivers/char/drm/drm_drv.c
+++ b/drivers/char/drm/drm_drv.c
@@ -118,7 +118,7 @@ static drm_ioctl_desc_t drm_ioctls[] = {
 	[DRM_IOCTL_NR(DRM_IOCTL_WAIT_VBLANK)] = {drm_wait_vblank, 0},
 };
 
-#define DRIVER_IOCTL_COUNT	DRM_ARRAY_SIZE( drm_ioctls )
+#define DRIVER_IOCTL_COUNT	ARRAY_SIZE( drm_ioctls )
 
 /**
  * Take down the DRM device.
@@ -155,12 +155,13 @@ int drm_lastclose(drm_device_t * dev)
 	del_timer(&dev->timer);
 
 	/* Clear pid list */
-	for (i = 0; i < DRM_HASH_SIZE; i++) {
-		for (pt = dev->magiclist[i].head; pt; pt = next) {
-			next = pt->next;
+	if (dev->magicfree.next) {
+		list_for_each_entry_safe(pt, next, &dev->magicfree, head) {
+			list_del(&pt->head);
+			drm_ht_remove_item(&dev->magiclist, &pt->hash_item);
 			drm_free(pt, sizeof(*pt), DRM_MEM_MAGIC);
 		}
-		dev->magiclist[i].head = dev->magiclist[i].tail = NULL;
+		drm_ht_remove(&dev->magiclist);
 	}
 
 	/* Clear AGP information */
@@ -299,6 +300,7 @@ static void drm_cleanup(drm_device_t * dev)
 	if (dev->maplist) {
 		drm_free(dev->maplist, sizeof(*dev->maplist), DRM_MEM_MAPS);
 		dev->maplist = NULL;
+		drm_ht_remove(&dev->map_hash);
 	}
 
 	drm_ctxbitmap_cleanup(dev);
diff --git a/drivers/char/drm/drm_fops.c b/drivers/char/drm/drm_fops.c
index b7f7951c458..898f47dafec 100644
--- a/drivers/char/drm/drm_fops.c
+++ b/drivers/char/drm/drm_fops.c
@@ -53,6 +53,8 @@ static int drm_setup(drm_device_t * dev)
 			return ret;
 	}
 
+	dev->magicfree.next = NULL;
+
 	/* prebuild the SAREA */
 	i = drm_addmap(dev, 0, SAREA_MAX, _DRM_SHM, _DRM_CONTAINS_LOCK, &map);
 	if (i != 0)
@@ -69,13 +71,11 @@ static int drm_setup(drm_device_t * dev)
 			return i;
 	}
 
-	for (i = 0; i < DRM_ARRAY_SIZE(dev->counts); i++)
+	for (i = 0; i < ARRAY_SIZE(dev->counts); i++)
 		atomic_set(&dev->counts[i], 0);
 
-	for (i = 0; i < DRM_HASH_SIZE; i++) {
-		dev->magiclist[i].head = NULL;
-		dev->magiclist[i].tail = NULL;
-	}
+	drm_ht_create(&dev->magiclist, DRM_MAGIC_HASH_ORDER);
+	INIT_LIST_HEAD(&dev->magicfree);
 
 	dev->ctxlist = drm_alloc(sizeof(*dev->ctxlist), DRM_MEM_CTXLIST);
 	if (dev->ctxlist == NULL)
diff --git a/drivers/char/drm/drm_hashtab.c b/drivers/char/drm/drm_hashtab.c
new file mode 100644
index 00000000000..a0b2d6802ae
--- /dev/null
+++ b/drivers/char/drm/drm_hashtab.c
@@ -0,0 +1,190 @@
+/**************************************************************************
+ *
+ * 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.
+ *
+ *
+ **************************************************************************/
+/*
+ * Simple open hash tab implementation.
+ *
+ * Authors:
+ * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
+ */
+
+#include "drmP.h"
+#include "drm_hashtab.h"
+#include <linux/hash.h>
+
+int drm_ht_create(drm_open_hash_t *ht, unsigned int order)
+{
+	unsigned int i;
+
+	ht->size = 1 << order;
+	ht->order = order;
+	ht->fill = 0;
+	ht->table = vmalloc(ht->size*sizeof(*ht->table));
+	if (!ht->table) {
+		DRM_ERROR("Out of memory for hash table\n");
+		return -ENOMEM;
+	}
+	for (i=0; i< ht->size; ++i) {
+		INIT_HLIST_HEAD(&ht->table[i]);
+	}
+	return 0;
+}
+
+void drm_ht_verbose_list(drm_open_hash_t *ht, unsigned long key)
+{
+	drm_hash_item_t *entry;
+	struct hlist_head *h_list;
+	struct hlist_node *list;
+	unsigned int hashed_key;
+	int count = 0;
+
+	hashed_key = hash_long(key, ht->order);
+	DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
+	h_list = &ht->table[hashed_key];
+	hlist_for_each(list, h_list) {
+		entry = hlist_entry(list, drm_hash_item_t, head);
+		DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
+	}
+}
+
+static struct hlist_node *drm_ht_find_key(drm_open_hash_t *ht, 
+					  unsigned long key)
+{
+	drm_hash_item_t *entry;
+	struct hlist_head *h_list;
+	struct hlist_node *list;
+	unsigned int hashed_key;
+
+	hashed_key = hash_long(key, ht->order);
+	h_list = &ht->table[hashed_key];
+	hlist_for_each(list, h_list) {
+		entry = hlist_entry(list, drm_hash_item_t, head);
+		if (entry->key == key)
+			return list;
+		if (entry->key > key)
+			break;
+	}
+	return NULL;
+}
+
+
+int drm_ht_insert_item(drm_open_hash_t *ht, drm_hash_item_t *item)
+{
+	drm_hash_item_t *entry;
+	struct hlist_head *h_list;
+	struct hlist_node *list, *parent;
+	unsigned int hashed_key;
+	unsigned long key = item->key;
+
+	hashed_key = hash_long(key, ht->order);
+	h_list = &ht->table[hashed_key];
+	parent = NULL;
+	hlist_for_each(list, h_list) {
+		entry = hlist_entry(list, drm_hash_item_t, head);
+		if (entry->key == key)
+			return -EINVAL;
+		if (entry->key > key)
+			break;
+		parent = list;
+	}
+	if (parent) {
+		hlist_add_after(parent, &item->head);
+	} else {
+		hlist_add_head(&item->head, h_list);
+	}
+	return 0;
+}
+
+/*
+ * Just insert an item and return any "bits" bit key that hasn't been 
+ * used before.
+ */
+int drm_ht_just_insert_please(drm_open_hash_t *ht, drm_hash_item_t *item,
+			      unsigned long seed, int bits, int shift,
+			      unsigned long add)
+{
+	int ret;
+	unsigned long mask = (1 << bits) - 1;
+	unsigned long first, unshifted_key;
+
+	unshifted_key = hash_long(seed, bits);
+	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(drm_open_hash_t *ht, unsigned long key,
+		     drm_hash_item_t **item)
+{
+	struct hlist_node *list;
+
+	list = drm_ht_find_key(ht, key);
+	if (!list)
+		return -EINVAL;
+
+	*item = hlist_entry(list, drm_hash_item_t, head);
+	return 0;
+}
+
+int drm_ht_remove_key(drm_open_hash_t *ht, unsigned long key)
+{
+	struct hlist_node *list;
+
+	list = drm_ht_find_key(ht, key);
+	if (list) {
+		hlist_del_init(list);
+		ht->fill--;
+		return 0;
+	}
+	return -EINVAL;
+}
+
+int drm_ht_remove_item(drm_open_hash_t *ht, drm_hash_item_t *item)
+{
+	hlist_del_init(&item->head);
+	ht->fill--;
+	return 0;
+}
+
+void drm_ht_remove(drm_open_hash_t *ht)
+{
+	if (ht->table) {
+		vfree(ht->table);
+		ht->table = NULL;
+	}
+}
+
diff --git a/drivers/char/drm/drm_hashtab.h b/drivers/char/drm/drm_hashtab.h
new file mode 100644
index 00000000000..40afec05bff
--- /dev/null
+++ b/drivers/char/drm/drm_hashtab.h
@@ -0,0 +1,67 @@
+/**************************************************************************
+ *
+ * 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:
+ *<