Backported 4840 ddi_dma_mem_alloc()/ddi_dma_mem_free() are O(n**2)

3 files changed, 175 insertions, 0 deletions

diff --git a/uts/debian/changelog b/uts/debian/changelog
index 8fa666f..933e7b5 100644
--- a/uts/debian/changelog
+++ b/uts/debian/changelog
@@ -5,6 +5,8 @@ uts (4.3+4) UNRELEASED; urgency=medium
     (updated sys_ioctl_h-bsd-comp.patch). This fixes FTBFS of the shadow
     package, caused by the previous version of that patch. sys/tt*.h
     shadow some macros from sys/termios.h
+  * Backported 4840 ddi_dma_mem_alloc()/ddi_dma_mem_free() are O(n**2)
+    [illumos-4840-ddi_dma_mem_alloc.patch]
 
  -- Igor Pashev <pashev.igor@gmail.com>  Mon, 05 May 2014 16:38:33 +0400
 
diff --git a/uts/debian/patches/illumos-4840-ddi_dma_mem_alloc.patch b/uts/debian/patches/illumos-4840-ddi_dma_mem_alloc.patch
new file mode 100644
index 0000000..e6c9a2d
--- /dev/null
+++ b/uts/debian/patches/illumos-4840-ddi_dma_mem_alloc.patch
@@ -0,0 +1,172 @@
+From a7175e2030b8105e954880bdc63bf0e3dba62d2c Mon Sep 17 00:00:00 2001
+From: Garrett D'Amore <garrett@damore.org>
+Date: Fri, 2 May 2014 21:36:57 -0700
+Subject: [PATCH] 4840 ddi_dma_mem_alloc()/ddi_dma_mem_free() are O(n**2)
+ Reviewed by: Michael Speer <michael.speer@pluribusnetworks.com> Reviewed by:
+ Tycho Nightingale <tycho.nightingale@pluribusnetworks.com> Reviewed by:
+ Rafael Vanoni <rafael.vanoni@pluribusnetworks.com> Reviewed by: Josef 'Jeff'
+ Sipek <jeffpc@josefsipek.net> Reviewed by: Robert Mustacchi <rm@joyent.com>
+ Approved by: Dan McDonald <danmcd@omniti.com>
+
+---
+ usr/src/uts/i86pc/os/ddi_impl.c | 96 +++++++++++++++++++++--------------------
+ 1 file changed, 49 insertions(+), 47 deletions(-)
+
+diff --git a/usr/src/uts/i86pc/os/ddi_impl.c b/usr/src/uts/i86pc/os/ddi_impl.c
+index 60347c6..f743336 100644
+--- a/usr/src/uts/i86pc/os/ddi_impl.c
++++ b/usr/src/uts/i86pc/os/ddi_impl.c
+@@ -21,7 +21,8 @@
+ 
+ /*
+  * Copyright (c) 1992, 2010, Oracle and/or its affiliates. All rights reserved.
+- * Copyright 2012 Garrett D'Amore <garrett@damore.org>.  All rights reserved.
++ * Copyright 2012 Garrett D'Amore <garrett@damore.org>
++ * Copyright 2014 Pluribus Networks, Inc.
+  */
+ 
+ /*
+@@ -65,6 +66,7 @@
+ #include <sys/mach_intr.h>
+ #include <vm/hat_i86.h>
+ #include <sys/x86_archext.h>
++#include <sys/avl.h>
+ 
+ /*
+  * DDI Boot Configuration
+@@ -105,14 +107,20 @@ static int kmem_override_cache_attrs(caddr_t, size_t, uint_t);
+ extern void immu_init(void);
+ #endif
+ 
+-#define	CTGENTRIES	15
++/*
++ * We use an AVL tree to store contiguous address allocations made with the
++ * kalloca() routine, so that we can return the size to free with kfreea().
++ * Note that in the future it would be vastly faster if we could eliminate
++ * this lookup by insisting that all callers keep track of their own sizes,
++ * just as for kmem_alloc().
++ */
++struct ctgas {
++	avl_node_t ctg_link;
++	void *ctg_addr;
++	size_t ctg_size;
++};
+ 
+-static struct ctgas {
+-	struct ctgas	*ctg_next;
+-	int		ctg_index;
+-	void		*ctg_addr[CTGENTRIES];
+-	size_t		ctg_size[CTGENTRIES];
+-} ctglist;
++static avl_tree_t ctgtree;
+ 
+ static kmutex_t		ctgmutex;
+ #define	CTGLOCK()	mutex_enter(&ctgmutex)
+@@ -1198,6 +1206,15 @@ kmem_override_cache_attrs(caddr_t kva, size_t size, uint_t order)
+ 	return (0);
+ }
+ 
++static int
++ctgcompare(const void *a1, const void *a2)
++{
++	/* we just want to compare virtual addresses */
++	a1 = ((struct ctgas *)a1)->ctg_addr;
++	a2 = ((struct ctgas *)a2)->ctg_addr;
++	return (a1 == a2 ? 0 : (a1 < a2 ? -1 : 1));
++}
++
+ void
+ ka_init(void)
+ {
+@@ -1237,6 +1254,10 @@ ka_init(void)
+ 		if (io_arena_params[a].io_initial || a == kmem_io_idx)
+ 			kmem_io_init(a);
+ 	}
++
++	/* initialize ctgtree */
++	avl_create(&ctgtree, ctgcompare, sizeof (struct ctgas),
++	    offsetof(struct ctgas, ctg_link));
+ }
+ 
+ /*
+@@ -1245,24 +1266,14 @@ ka_init(void)
+ static void *
+ putctgas(void *addr, size_t size)
+ {
+-	struct ctgas	*ctgp = &ctglist;
+-	int		i;
+-
+-	CTGLOCK();
+-	do {
+-		if ((i = ctgp->ctg_index) < CTGENTRIES) {
+-			ctgp->ctg_addr[i] = addr;
+-			ctgp->ctg_size[i] = size;
+-			ctgp->ctg_index++;
+-			break;
+-		}
+-		if (!ctgp->ctg_next)
+-			ctgp->ctg_next = kmem_zalloc(sizeof (struct ctgas),
+-			    KM_NOSLEEP);
+-		ctgp = ctgp->ctg_next;
+-	} while (ctgp);
+-
+-	CTGUNLOCK();
++	struct ctgas    *ctgp;
++	if ((ctgp = kmem_zalloc(sizeof (*ctgp), KM_NOSLEEP)) != NULL) {
++		ctgp->ctg_addr = addr;
++		ctgp->ctg_size = size;
++		CTGLOCK();
++		avl_add(&ctgtree, ctgp);
++		CTGUNLOCK();
++	}
+ 	return (ctgp);
+ }
+ 
+@@ -1272,32 +1283,23 @@ putctgas(void *addr, size_t size)
+ static size_t
+ getctgsz(void *addr)
+ {
+-	struct ctgas	*ctgp = &ctglist;
+-	int		i, j;
+-	size_t		sz;
++	struct ctgas    *ctgp;
++	struct ctgas    find;
++	size_t		sz = 0;
+ 
+-	ASSERT(addr);
++	find.ctg_addr = addr;
+ 	CTGLOCK();
++	if ((ctgp = avl_find(&ctgtree, &find, NULL)) != NULL) {
++		avl_remove(&ctgtree, ctgp);
++	}
++	CTGUNLOCK();
+ 
+-	while (ctgp) {
+-		for (i = 0; i < ctgp->ctg_index; i++) {
+-			if (addr != ctgp->ctg_addr[i])
+-				continue;
+-
+-			sz = ctgp->ctg_size[i];
+-			j = --ctgp->ctg_index;
+-			if (i != j) {
+-				ctgp->ctg_size[i] = ctgp->ctg_size[j];
+-				ctgp->ctg_addr[i] = ctgp->ctg_addr[j];
+-			}
+-			CTGUNLOCK();
+-			return (sz);
+-		}
+-		ctgp = ctgp->ctg_next;
++	if (ctgp != NULL) {
++		sz = ctgp->ctg_size;
++		kmem_free(ctgp, sizeof (*ctgp));
+ 	}
+ 
+-	CTGUNLOCK();
+-	return (0);
++	return (sz);
+ }
+ 
+ /*
+-- 
+1.9.1
+
diff --git a/uts/debian/patches/series b/uts/debian/patches/series
index 9542875..3439a6b 100644
--- a/uts/debian/patches/series
+++ b/uts/debian/patches/series
@@ -61,3 +61,4 @@ illumos-4679-intel-erratum-BT81.patch
 illumos-4682.patch
 sys_ioctl_h-bsd-comp.patch
 uts-gcc48-warnings.patch
+illumos-4840-ddi_dma_mem_alloc.patch