Make libbmm more efficient

libbmm calls into the kernel a lot to perform various functions such as
translating between virtual and physical addresses, finding out the
buffer size, and so forth.  Much of this can be done in userspace,
because we have that information at the point where the buffer is
allocated.

Rather than having to keep fetching it from the kernel, store it in our
own local bmm_buffer structure, and store this in a pair of rb trees -
one indexed by physical address and the other by virtual address.  This
allows us to efficiently look up the bmm_buffer structure by either
address, and retrieve the other buffer attribute(s).

Reference: http://web.eecs.utk.edu/~plank/plank/rbtree/rbtree.html

1 files changed, 210 insertions, 54 deletions

diff --git a/bmm_lib.c b/bmm_lib.c
index 1b3a156..3e4ebd2 100644
--- a/bmm_lib.c
+++ b/bmm_lib.c
@@ -15,11 +15,15 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/mman.h>
+#include <assert.h>
 #include <fcntl.h>
+#include <pthread.h>
+#include <stdlib.h>
 #include <unistd.h>
 
 #include "bmm_lib_priv.h"
 #include "bmm_lib.h"
+#include "rb.h"
 
 #undef DEBUG
 
@@ -38,6 +42,108 @@
 
 static unsigned bmm_api;
 static int bmm_fd = -1;
+static pthread_mutex_t bmm_mutex = PTHREAD_MUTEX_INITIALIZER;
+static Rb_node virt_rb;
+static Rb_node phys_rb;
+
+struct bmm_buffer {
+	void *vaddr;
+	unsigned long paddr;
+	size_t size;
+	int attr;
+};
+
+static int cmp_virt(const void *key, const void *val)
+{
+	const struct bmm_buffer *buf = val;
+	void *k = (void *)key;
+
+	return (k < buf->vaddr) ? -1 :
+	       (k - buf->vaddr < buf->size) ? 0 : 1;
+}
+
+static int cmp_phys(const void *key, const void *val)
+{
+	const struct bmm_buffer *buf = val;
+	unsigned long k = (unsigned long)key;
+
+	return (k < buf->paddr) ? -1 :
+	       (k - buf->paddr < buf->size) ? 0 : 1;
+}
+
+static struct bmm_buffer *bmm_buf_find_virt(void *virt)
+{
+	struct bmm_buffer *buf = NULL;
+	Rb_node node;
+	int found = 0;
+
+	node = rb_find_key_n(virt_rb, virt, cmp_virt, &found);
+	if (found) {
+		buf = rb_val(node);
+
+		pr_debug("rb: %s(%p) phys=0x%08lx virt=%p size=0x%08lx\n",
+			"find_virt", virt, buf->paddr, buf->vaddr, buf->size);
+	} else {
+		pr_debug("rb: %s(%p): not found\n",
+			"find_virt", virt);
+	}
+
+	return buf;
+}
+
+static struct bmm_buffer *bmm_buf_find_phys(unsigned long phys)
+{
+	struct bmm_buffer *buf = NULL;
+	Rb_node node;
+	int found = 0;
+
+	node = rb_find_key_n(phys_rb, (void *)phys, cmp_phys, &found);
+	if (found) {
+		buf = rb_val(node);
+
+		pr_debug("rb: %s(0x%08lx) phys=0x%08lx virt=%p size=0x%08lx\n",
+			"find_phys", (unsigned long)phys, buf->paddr, buf->vaddr, buf->size);
+	} else {
+		pr_debug("rb: %s(0x%08lx): not found\n",
+			"find_phys", (unsigned long)phys);
+	}
+
+	return buf;
+}
+
+static void bmm_buf_remove(struct bmm_buffer *buf)
+{
+	Rb_node node;
+	int found = 0;
+
+	pr_debug("rb: %s phys=0x%08lx virt=%p size=0x%08lx\n",
+		"remove", buf->paddr, buf->vaddr, buf->size);
+
+	node = rb_find_key_n(virt_rb, buf->vaddr, cmp_virt, &found);
+	assert(found);
+	rb_delete_node(node);
+
+	node = rb_find_key_n(phys_rb, (void *)buf->paddr, cmp_phys, &found);
+	assert(found);
+	rb_delete_node(node);
+}
+
+static void bmm_buf_insert(struct bmm_buffer *buf)
+{
+	Rb_node node;
+	int found = 0;
+
+	pr_debug("rb: %s phys=0x%08lx virt=%p size=0x%08lx\n",
+		"insert", buf->paddr, buf->vaddr, buf->size);
+
+	node = rb_find_key_n(virt_rb, buf->vaddr, cmp_virt, &found);
+	assert(found == 0);
+	rb_insert_b(node, buf);
+
+	node = rb_find_key_n(phys_rb, (void *)buf->paddr, cmp_phys, &found);
+	assert(found == 0);
+	rb_insert_b(node, buf);
+}
 
 static int bmm_get_api_version(void)
 {
@@ -64,10 +170,14 @@ static int bmm_get_api_version(void)
 
 int bmm_init()
 {
-        /* attempt to open the BMM driver */
-	if(bmm_fd < 0) {
-		bmm_fd = open(BMM_DEVICE_FILE, O_RDWR | O_CLOEXEC);
+	if (bmm_fd < 0) {
+		virt_rb = make_rb();
+		phys_rb = make_rb();
+		if (!virt_rb || !phys_rb)
+			goto err_rb;
 
+		/* attempt to open the BMM driver */
+		bmm_fd = open(BMM_DEVICE_FILE, O_RDWR | O_CLOEXEC);
 		pr_debug("BMM device fd: %d\n", bmm_fd);
 		if (bmm_fd < 0)
 			goto err_open;
@@ -82,18 +192,29 @@ int bmm_init()
 	close(bmm_fd);
 	bmm_fd = -1;
  err_open:
+ err_rb:
+	if (phys_rb)
+		rb_free_tree(phys_rb);
+	if (virt_rb)
+		rb_free_tree(virt_rb);
+	phys_rb = virt_rb = NULL;
 	return bmm_fd;
 }
 
 void bmm_exit()
 {
-	if(bmm_fd >= 0)
+	if (bmm_fd >= 0) {
 		close(bmm_fd);
+		rb_free_tree(phys_rb);
+		rb_free_tree(virt_rb);
+		phys_rb = virt_rb = NULL;
+	}
 	bmm_fd = -1;
 }
 
 void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align)
 {
+	struct bmm_buffer *buf;
 	int ret;
 	void *vaddr;
 	ioctl_arg_t io;
@@ -104,6 +225,10 @@ void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align)
 	if(bmm_init() < 0)
 		return NULL;
 
+	buf = malloc(sizeof(*buf));
+	if (!buf)
+		return NULL;
+
 	pr_debug("%s(size=%lu,attr=%x,align=%u)\n", __FUNCTION__, size, attr, align);
 
 	/* obsolete, only for back-compatible */
@@ -118,13 +243,31 @@ void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align)
 	io.output = 0;
 	io.arg = attr;
 	ret = ioctl(bmm_fd, BMM_MALLOC_ALIGNED, &io);
-	if(ret < 0 || io.output == 0)
-		return NULL;
+	if (ret < 0 || io.output == 0)
+		goto err_free_buf;
 
 	pr_debug("bmm_malloc return paddr = 0x%08lx\n", io.output);
 
 	vaddr = mmap(0, size, PROT_READ | PROT_WRITE, MAP_SHARED, bmm_fd, io.output);
-	return ((int)vaddr == -1) ? NULL : vaddr;
+	if ((int)vaddr == -1) {
+		/* FIXME: we can't free the bmm buffer without a vaddr! */
+		goto err_free_buf;
+	}
+
+	buf->vaddr = vaddr;
+	buf->paddr = io.output;
+	buf->size = size;
+	buf->attr = attr;
+
+	pthread_mutex_lock(&bmm_mutex);
+	bmm_buf_insert(buf);
+	pthread_mutex_unlock(&bmm_mutex);
+
+	return vaddr;
+
+ err_free_buf:
+	free(buf);
+	return NULL;
 }
 
 void *bmm_malloc(unsigned long size, int attr)
@@ -134,19 +277,27 @@ void *bmm_malloc(unsigned long size, int attr)
 
 void bmm_free(void *vaddr)
 {
-	unsigned long size;
+	struct bmm_buffer *buf;
 	ioctl_arg_t io;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return;
 
-	size = bmm_get_mem_size(vaddr);
-	munmap(vaddr, size);
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		bmm_buf_remove(buf);
+	pthread_mutex_unlock(&bmm_mutex);
 
-	io.input = (unsigned long)vaddr;
+	assert(buf);
+
+	munmap(buf->vaddr, buf->size);
+
+	io.input = (unsigned long)buf->vaddr;
 	io.output = 0;
 	io.arg = 0;
 	ioctl(bmm_fd, BMM_FREE, &io);
+	free(buf);
 }
 
 void *bmm_attach(unsigned long paddr, unsigned long len)
@@ -174,38 +325,36 @@ void bmm_detach(void *vaddr, unsigned long len)
 
 void *bmm_get_vaddr(unsigned long paddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	void *va = NULL;
 
-	if(bmm_init() < 0)
-		return NULL;
+	if (bmm_init() < 0)
+		return 0;
 
-	io.input = paddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd, BMM_GET_VIRT_ADDR, &io);
-	if(ret < 0)
-		return NULL;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_phys(paddr);
+	if (buf)
+		va = buf->vaddr + (paddr - buf->paddr);
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return (void *)io.output;
+	return va;
 }
 
 unsigned long bmm_get_paddr(void *vaddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	unsigned long pa = 0;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return 0;
 
-	io.input = (unsigned long)vaddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd,BMM_GET_PHYS_ADDR, &io);
-	if(ret < 0)
-		return 0;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		pa = buf->paddr + (vaddr - buf->vaddr);
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return io.output;
+	return pa;
 }
 
 int bmm_get_dmabuf_fd(void *vaddr)
@@ -227,42 +376,41 @@ int bmm_get_dmabuf_fd(void *vaddr)
 
 unsigned long bmm_get_mem_size(void *vaddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	unsigned long size = 0;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return 0;
 
-	io.input = (unsigned long)vaddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd,BMM_GET_MEM_SIZE, &io);
-	if(ret < 0)
-		return 0;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		size = buf->size;
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return io.output;
+	return size;
 }
 
 int bmm_get_mem_attr(void *vaddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	int attr = 0;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return 0;
 
-	io.input = (unsigned long)vaddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd, BMM_GET_MEM_ATTR, &io);
-	if(ret < 0)
-		return 0;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		attr = buf->attr;
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return (int)io.output;
+	return attr;
 }
 
 int bmm_set_mem_attr(void *vaddr, int attr)
 {
+	struct bmm_buffer *buf;
 	int ret;
 	ioctl_arg_t io;
 
@@ -276,7 +424,15 @@ int bmm_set_mem_attr(void *vaddr, int attr)
 	if(ret < 0)
 		return 0;
 
-	return (int)io.output;
+	attr = io.output;
+
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		buf->attr = attr;
+	pthread_mutex_unlock(&bmm_mutex);
+
+	return attr;
 }
 
 unsigned long bmm_get_total_space()