Replace handrolled hashes with a splay tree, while there plug a memleak

inherited from the original drm driver.

input and ok oga@.

3 files changed, 27 insertions, 46 deletions

diff --git a/sys/dev/pci/drm/drmP.h b/sys/dev/pci/drm/drmP.h
index 0fa1df871c5..07fd6976d4a 100644
--- a/sys/dev/pci/drm/drmP.h
+++ b/sys/dev/pci/drm/drmP.h
@@ -157,7 +157,6 @@ typedef struct drm_file drm_file_t;
 #define DRM_LINUX 0
 #endif
 
-#define DRM_HASH_SIZE	      16 /* Size of key hash table		  */
 #define DRM_KERNEL_CONTEXT    0	 /* Change drm_resctx if changed	  */
 #define DRM_RESERVED_CONTEXTS 1	 /* Change drm_resctx if changed	  */
 
@@ -540,14 +539,12 @@ typedef struct drm_ioctl_desc {
 #define DRM_IOCTL_DEF(ioctl, func, flags) \
 	[DRM_IOCTL_NR(ioctl)] = {ioctl, func, flags}
 
-typedef TAILQ_HEAD(drm_magic_list, drm_magic_entry) drm_magic_head_t;
 struct drm_magic_entry {
 	drm_magic_t	       magic;
 	struct drm_file	       *priv;
-	TAILQ_ENTRY(drm_magic_entry) link;
+	SPLAY_ENTRY(drm_magic_entry) node;
 };
 
-
 typedef struct drm_buf {
 	int		  idx;	       /* Index into master buflist	     */
 	int		  total;       /* Buffer size			     */
@@ -860,7 +857,7 @@ struct drm_device {
 
 				/* Authentication */
 	drm_file_list_t   files;
-	drm_magic_head_t  magiclist[DRM_HASH_SIZE];
+	SPLAY_HEAD(drm_magic_tree, drm_magic_entry)	magiclist;
 
 	/* Linked list of mappable regions. Protected by dev_lock */
 	drm_map_list_t	  maplist;
@@ -1102,6 +1099,8 @@ struct drm_drawable_info	*drm_get_drawable_info(drm_device_t *dev,
 /* Authentication IOCTL support (drm_auth.c) */
 int	drm_getmagic(drm_device_t *dev, void *data, struct drm_file *file_priv);
 int	drm_authmagic(drm_device_t *dev, void *data, struct drm_file *file_priv);
+int	drm_magic_cmp(struct drm_magic_entry *, struct drm_magic_entry *);
+SPLAY_PROTOTYPE(drm_magic_tree, drm_magic_entry, node, drm_magic_cmp);
 
 /* Buffer management support (drm_bufs.c) */
 int	drm_addmap_ioctl(drm_device_t *dev, void *data, struct drm_file *file_priv);
diff --git a/sys/dev/pci/drm/drm_auth.c b/sys/dev/pci/drm/drm_auth.c
index 6e4cd1dddcd..7ee2d00d8d0 100644
--- a/sys/dev/pci/drm/drm_auth.c
+++ b/sys/dev/pci/drm/drm_auth.c
@@ -35,17 +35,10 @@
 
 #include "drmP.h"
 
-int	 drm_hash_magic(drm_magic_t);
 drm_file_t *drm_find_file(drm_device_t *, drm_magic_t);
 int	 drm_add_magic(drm_device_t *, drm_file_t *, drm_magic_t);
 int	 drm_remove_magic(drm_device_t *, drm_magic_t);
 
-int
-drm_hash_magic(drm_magic_t magic)
-{
-	return magic & (DRM_HASH_SIZE-1);
-}
-
 /**
  * Returns the file private associated with the given magic number.
  */
@@ -53,18 +46,13 @@ drm_file_t *
 drm_find_file(drm_device_t *dev, drm_magic_t magic)
 {
 	struct drm_magic_entry *pt;
-	int hash;
-
-	hash = drm_hash_magic(magic);
+	struct drm_magic_entry	key;
 
 	DRM_SPINLOCK_ASSERT(&dev->dev_lock);
 
-	TAILQ_FOREACH(pt, &dev->magiclist[hash], link) {
-		if (pt->magic == magic) {
-			return (pt->priv);
-		}
-	}
-
+	key.magic = magic;
+	if ((pt = SPLAY_FIND(drm_magic_tree, &dev->magiclist, &key)) != NULL)
+		return (pt->priv);
 	return (NULL);
 }
 
@@ -75,19 +63,17 @@ drm_find_file(drm_device_t *dev, drm_magic_t magic)
 int
 drm_add_magic(drm_device_t *dev, drm_file_t *priv, drm_magic_t magic)
 {
-	int hash;
 	struct drm_magic_entry *entry;
 
 	DRM_DEBUG("%d\n", magic);
 
 	DRM_SPINLOCK_ASSERT(&dev->dev_lock);
 
-	hash = drm_hash_magic(magic);
 	entry = malloc(sizeof(*entry), M_DRM, M_ZERO | M_NOWAIT);
 	if (!entry) return ENOMEM;
 	entry->magic = magic;
 	entry->priv  = priv;
-	TAILQ_INSERT_TAIL(&dev->magiclist[hash], entry, link);
+	SPLAY_INSERT(drm_magic_tree, &dev->magiclist, entry);
 
 	return 0;
 }
@@ -99,26 +85,19 @@ drm_add_magic(drm_device_t *dev, drm_file_t *priv, drm_magic_t magic)
 int
 drm_remove_magic(drm_device_t *dev, drm_magic_t magic)
 {
-	struct drm_magic_entry *prev = NULL;
 	struct drm_magic_entry *pt;
-	int hash;
+	struct drm_magic_entry  key;
 
 	DRM_SPINLOCK_ASSERT(&dev->dev_lock);
 
 	DRM_DEBUG("%d\n", magic);
-	hash = drm_hash_magic(magic);
-
-	for (pt = TAILQ_FIRST(&dev->magiclist[hash]);
-	    pt != TAILQ_END(&dev->magiclist[hash]);
-	    prev = pt, pt = TAILQ_NEXT(pt, link)) {
-		if (pt->magic == magic) {
-			TAILQ_REMOVE(&dev->magiclist[hash], pt, link);
-			return 0;
-		}
-	}
 
+	key.magic = magic;
+	if ((pt = SPLAY_FIND(drm_magic_tree, &dev->magiclist, &key)) == NULL)
+		return EINVAL;
+	SPLAY_REMOVE(drm_magic_tree, &dev->magiclist, pt);
 	free(pt, M_DRM);
-	return EINVAL;
+	return (0);
 }
 
 /**
@@ -181,3 +160,11 @@ drm_authmagic(drm_device_t *dev, void *data, struct drm_file *file_priv)
 		return EINVAL;
 	}
 }
+
+int
+drm_magic_cmp(struct drm_magic_entry *dme1, struct drm_magic_entry *dme2)
+{
+	return (dme1->magic - dme2->magic);
+}
+
+SPLAY_GENERATE(drm_magic_tree, drm_magic_entry, node, drm_magic_cmp);
diff --git a/sys/dev/pci/drm/drm_drv.c b/sys/dev/pci/drm/drm_drv.c
index a352d67ccbe..7eaf8358810 100644
--- a/sys/dev/pci/drm/drm_drv.c
+++ b/sys/dev/pci/drm/drm_drv.c
@@ -380,9 +380,7 @@ drm_firstopen(drm_device_t *dev)
 	for ( i = 0 ; i < DRM_ARRAY_SIZE(dev->counts) ; i++ )
 		atomic_set( &dev->counts[i], 0 );
 
-	for ( i = 0 ; i < DRM_HASH_SIZE ; i++ ) {
-		TAILQ_INIT(&dev->magiclist[i]);
-	}
+	SPLAY_INIT(&dev->magiclist);
 
 	dev->lock.lock_queue = 0;
 	dev->irq_enabled = 0;
@@ -409,7 +407,6 @@ drm_lastclose(drm_device_t *dev)
 #ifdef __FreeBSD__
 	drm_local_map_t *mapsave;
 #endif
-	int i;
 
 	DRM_SPINLOCK_ASSERT(&dev->dev_lock);
 
@@ -429,11 +426,9 @@ drm_lastclose(drm_device_t *dev)
 
 	drm_drawable_free_all(dev);
 				/* Clear pid list */
-	for ( i = 0 ; i < DRM_HASH_SIZE ; i++ ) {
-		while ((pt = TAILQ_FIRST(&dev->magiclist[i])) != NULL) {
-			TAILQ_REMOVE(&dev->magiclist[i], pt, link);
-			free(pt, M_DRM);
-		}
+	while ((pt = SPLAY_ROOT(&dev->magiclist)) != NULL) {
+		SPLAY_REMOVE(drm_magic_tree, &dev->magiclist, pt);
+		free(pt, M_DRM);
 	}
 
 				/* Clear AGP information */