Change drm Map handles to be arbitrary 32-bit hash tokens in the range

    0x10000000 to 0x90000000 in PAGE_SIZE increments.
Implement hashed map lookups.
This potentially breaks both 2D and 3D drivers. If so, the corresponding
2D and 3D driver should be fixed, and it's corresponding drm device driver
    should have its major bumped as soon as possible.
Bump sis and via drm device driver majors.
The SiS and Unichrome 3D drivers are fixed in Mesa CVS HEAD and
    mesa_6_4_branch.

5 files changed, 37 insertions, 69 deletions

diff --git a/linux-core/drmP.h b/linux-core/drmP.h
index 6c56b7d4..fb0ba482 100644
--- a/linux-core/drmP.h
+++ b/linux-core/drmP.h
@@ -153,6 +153,7 @@
 #define DRM_MEM_HASHTAB   23
 
 #define DRM_MAX_CTXBITMAP (PAGE_SIZE * 8)
+#define DRM_MAP_HASH_OFFSET 0x10000000
 
 /*@}*/
 
@@ -502,6 +503,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;
@@ -679,6 +681,7 @@ typedef struct drm_device {
 	/*@{ */
 	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 */
 	/*@{ */
diff --git a/linux-core/drm_bufs.c b/linux-core/drm_bufs.c
index eb478ba2..44705259 100644
--- a/linux-core/drm_bufs.c
+++ b/linux-core/drm_bufs.c
@@ -65,44 +65,6 @@ 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 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;
-
-		hash += PAGE_SIZE;
-		map32_handle += PAGE_SIZE;
-	}
-}
-#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.
  *
@@ -300,9 +262,18 @@ static int drm_addmap_core(drm_device_t * dev, unsigned int offset,
 	list_add(&list->head, &dev->maplist->head);
 	/* Assign a 32-bit handle */
 	/* We do it here so that dev->struct_sem protects the increment */
-	list->user_token = HandleID(map->type == _DRM_SHM
-				    ? (unsigned long)map->handle
-				    : map->offset, dev);
+
+        if (drm_ht_just_insert_please(&dev->map_hash, &list->hash, 
+				      ((map->type == _DRM_SHM) ? (unsigned long)map->handle : 
+                                       map->offset) >> PAGE_SHIFT,
+				      32 - PAGE_SHIFT - 1)) {
+                drm_free(map, sizeof(*map), DRM_MEM_MAPS);
+                drm_free(list, sizeof(*list), DRM_MEM_MAPS);
+                up(&dev->struct_sem);
+                return -ENOMEM;
+	}
+
+	list->user_token = (list->hash.key << PAGE_SHIFT) + DRM_MAP_HASH_OFFSET;
 	up(&dev->struct_sem);
 
 	*maplist = list;
@@ -387,6 +358,8 @@ 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_MAP_HASH_OFFSET) >> PAGE_SHIFT);
 			drm_free(list, sizeof(*list), DRM_MEM_MAPS);
 			break;
 		}
diff --git a/linux-core/drm_hashtab.h b/linux-core/drm_hashtab.h
index 580a02ed..d792499e 100644
--- a/linux-core/drm_hashtab.h
+++ b/linux-core/drm_hashtab.h
@@ -35,7 +35,7 @@
 #ifndef DRM_HASHTAB_H
 #define DRM_HASHTAB_H
 
-#define drm_hash_entry(_a1, _a2, _a3) list_entry(_a1, _a2, _a3)
+#define drm_hash_entry(_ptr, _type, _member) container_of(_ptr, _type, _member)
 
 typedef struct drm_hash_item{
         struct hlist_node head;
diff --git a/linux-core/drm_stub.c b/linux-core/drm_stub.c
index 6ba6f6e1..24955634 100644
--- a/linux-core/drm_stub.c
+++ b/linux-core/drm_stub.c
@@ -82,6 +82,10 @@ static int drm_fill_in_dev(drm_device_t * dev, struct pci_dev *pdev,
 	if (dev->maplist == NULL)
 		return -ENOMEM;
 	INIT_LIST_HEAD(&dev->maplist->head);
+        if (drm_ht_create(&dev->map_hash, 12)) {
+                drm_free(dev->maplist, sizeof(*dev->maplist), DRM_MEM_MAPS);
+                return -ENOMEM;
+        }
 
 	/* the DRM has 6 counters */
 	dev->counters = 6;
diff --git a/linux-core/drm_vm.c b/linux-core/drm_vm.c
index b92552e6..93037bda 100644
--- a/linux-core/drm_vm.c
+++ b/linux-core/drm_vm.c
@@ -59,7 +59,7 @@ static __inline__ struct page *drm_do_vm_nopage(struct vm_area_struct *vma,
 	drm_device_t *dev = priv->head->dev;
 	drm_map_t *map = NULL;
 	drm_map_list_t *r_list;
-	struct list_head *list;
+        drm_hash_item_t *hash;
 
 	/*
 	 * Find the right map
@@ -70,14 +70,12 @@ static __inline__ struct page *drm_do_vm_nopage(struct vm_area_struct *vma,
 	if (!dev->agp || !dev->agp->cant_use_aperture)
 		goto vm_nopage_error;
 
-	list_for_each(list, &dev->maplist->head) {
-		r_list = list_entry(list, drm_map_list_t, head);
-		map = r_list->map;
-		if (!map)
-			continue;
-		if (r_list->user_token == VM_OFFSET(vma))
-			break;
-	}
+        if (drm_ht_find_item(&dev->map_hash, (VM_OFFSET(vma) - DRM_MAP_HASH_OFFSET) >> PAGE_SHIFT,  
+                             &hash)) 
+                goto vm_nopage_error;
+
+        r_list = drm_hash_entry(hash, drm_map_list_t, hash);
+	map = r_list->map;
 
 	if (map && map->type == _DRM_AGP) {
 		unsigned long offset = address - vma->vm_start;
@@ -556,9 +554,8 @@ int drm_mmap(struct file *filp, struct vm_area_struct *vma)
 	drm_file_t *priv = filp->private_data;
 	drm_device_t *dev = priv->head->dev;
 	drm_map_t *map = NULL;
-	drm_map_list_t *r_list;
 	unsigned long offset = 0;
-	struct list_head *list;
+        drm_hash_item_t *hash;
 
 	DRM_DEBUG("start = 0x%lx, end = 0x%lx, offset = 0x%lx\n",
 		  vma->vm_start, vma->vm_end, VM_OFFSET(vma));
@@ -578,22 +575,13 @@ int drm_mmap(struct file *filp, struct vm_area_struct *vma)
 	    )
 		return drm_mmap_dma(filp, vma);
 
-	/* A sequential search of a linked list is
-	   fine here because: 1) there will only be
-	   about 5-10 entries in the list and, 2) a
-	   DRI client only has to do this mapping
-	   once, so it doesn't have to be optimized
-	   for performance, even if the list was a
-	   bit longer. */
-	list_for_each(list, &dev->maplist->head) {
-
-		r_list = list_entry(list, drm_map_list_t, head);
-		map = r_list->map;
-		if (!map)
-			continue;
-		if (r_list->user_token == VM_OFFSET(vma))
-			break;
-	}
+        if (drm_ht_find_item(&dev->map_hash, (VM_OFFSET(vma) - DRM_MAP_HASH_OFFSET) >> PAGE_SHIFT,
+                             &hash)) {
+                DRM_ERROR("Could not find map\n");
+		return -EINVAL;
+        }
+        
+	map = drm_hash_entry(hash,drm_map_list_t, hash)->map;
 
 	if (!map || ((map->flags & _DRM_RESTRICTED) && !capable(CAP_SYS_ADMIN)))
 		return -EPERM;