msm: kgsl: Store process mem entries in a rbtree
The list of memory objects attached to a process gets searched quite
a lot during normal operation of the driver. For processes with a
lot of memory allocations, the linear search through the list is O(N)
and uses a lot more CPU during critical loops than it should. Change
the mem entry list to a rbtree for faster search speeds.
Change-Id: Ic0dedbad1b25d9d77f56f93696b2fe933fbad333
Signed-off-by: Jordan Crouse <jcrouse@codeaurora.org>
diff --git a/drivers/gpu/msm/kgsl.c b/drivers/gpu/msm/kgsl.c
index 1b0a7bc..d6c78bc 100644
--- a/drivers/gpu/msm/kgsl.c
+++ b/drivers/gpu/msm/kgsl.c
@@ -21,7 +21,7 @@
#include <linux/vmalloc.h>
#include <linux/pm_runtime.h>
#include <linux/genlock.h>
-
+#include <linux/rbtree.h>
#include <linux/ashmem.h>
#include <linux/major.h>
#include <linux/ion.h>
@@ -224,8 +224,28 @@
void kgsl_mem_entry_attach_process(struct kgsl_mem_entry *entry,
struct kgsl_process_private *process)
{
+ struct rb_node **node;
+ struct rb_node *parent = NULL;
+
spin_lock(&process->mem_lock);
- list_add(&entry->list, &process->mem_list);
+
+ node = &process->mem_rb.rb_node;
+
+ while (*node) {
+ struct kgsl_mem_entry *cur;
+
+ parent = *node;
+ cur = rb_entry(parent, struct kgsl_mem_entry, node);
+
+ if (entry->memdesc.gpuaddr < cur->memdesc.gpuaddr)
+ node = &parent->rb_left;
+ else
+ node = &parent->rb_right;
+ }
+
+ rb_link_node(&entry->node, parent, node);
+ rb_insert_color(&entry->node, &process->mem_rb);
+
spin_unlock(&process->mem_lock);
entry->priv = process;
@@ -593,8 +613,7 @@
spin_lock_init(&private->mem_lock);
private->refcnt = 1;
private->pid = task_tgid_nr(current);
-
- INIT_LIST_HEAD(&private->mem_list);
+ private->mem_rb = RB_ROOT;
if (kgsl_mmu_enabled())
{
@@ -623,7 +642,7 @@
struct kgsl_process_private *private)
{
struct kgsl_mem_entry *entry = NULL;
- struct kgsl_mem_entry *entry_tmp = NULL;
+ struct rb_node *node;
if (!private)
return;
@@ -637,11 +656,13 @@
list_del(&private->list);
- list_for_each_entry_safe(entry, entry_tmp, &private->mem_list, list) {
- list_del(&entry->list);
+ for (node = rb_first(&private->mem_rb); node; ) {
+ entry = rb_entry(node, struct kgsl_mem_entry, node);
+ node = rb_next(&entry->node);
+
+ rb_erase(&entry->node, &private->mem_rb);
kgsl_mem_entry_detach_process(entry);
}
-
kgsl_mmu_putpagetable(private->pagetable);
kfree(private);
unlock:
@@ -767,47 +788,43 @@
return result;
}
-
-/*call with private->mem_lock locked */
-static struct kgsl_mem_entry *
-kgsl_sharedmem_find(struct kgsl_process_private *private, unsigned int gpuaddr)
-{
- struct kgsl_mem_entry *entry = NULL, *result = NULL;
-
- BUG_ON(private == NULL);
-
- gpuaddr &= PAGE_MASK;
-
- list_for_each_entry(entry, &private->mem_list, list) {
- if (entry->memdesc.gpuaddr == gpuaddr) {
- result = entry;
- break;
- }
- }
- return result;
-}
-
/*call with private->mem_lock locked */
struct kgsl_mem_entry *
kgsl_sharedmem_find_region(struct kgsl_process_private *private,
- unsigned int gpuaddr,
- size_t size)
+ unsigned int gpuaddr, size_t size)
{
- struct kgsl_mem_entry *entry = NULL, *result = NULL;
+ struct rb_node *node = private->mem_rb.rb_node;
- BUG_ON(private == NULL);
+ while (node != NULL) {
+ struct kgsl_mem_entry *entry;
- list_for_each_entry(entry, &private->mem_list, list) {
- if (kgsl_gpuaddr_in_memdesc(&entry->memdesc, gpuaddr, size)) {
- result = entry;
- break;
+ entry = rb_entry(node, struct kgsl_mem_entry, node);
+
+
+ if (kgsl_gpuaddr_in_memdesc(&entry->memdesc, gpuaddr, size))
+ return entry;
+
+ if (gpuaddr < entry->memdesc.gpuaddr)
+ node = node->rb_left;
+ else if (gpuaddr >=
+ (entry->memdesc.gpuaddr + entry->memdesc.size))
+ node = node->rb_right;
+ else {
+ return NULL;
}
}
- return result;
+ return NULL;
}
EXPORT_SYMBOL(kgsl_sharedmem_find_region);
+/*call with private->mem_lock locked */
+static inline struct kgsl_mem_entry *
+kgsl_sharedmem_find(struct kgsl_process_private *private, unsigned int gpuaddr)
+{
+ return kgsl_sharedmem_find_region(private, gpuaddr, 1);
+}
+
/*call all ioctl sub functions with driver locked*/
static long kgsl_ioctl_device_getproperty(struct kgsl_device_private *dev_priv,
unsigned int cmd, void *data)
@@ -1059,7 +1076,7 @@
{
struct kgsl_mem_entry *entry = priv;
spin_lock(&entry->priv->mem_lock);
- list_del(&entry->list);
+ rb_erase(&entry->node, &entry->priv->mem_rb);
spin_unlock(&entry->priv->mem_lock);
trace_kgsl_mem_timestamp_free(entry, timestamp);
kgsl_mem_entry_detach_process(entry);
@@ -1158,7 +1175,8 @@
spin_lock(&private->mem_lock);
entry = kgsl_sharedmem_find(private, param->gpuaddr);
if (entry)
- list_del(&entry->list);
+ rb_erase(&entry->node, &private->mem_rb);
+
spin_unlock(&private->mem_lock);
if (entry) {
@@ -2115,7 +2133,7 @@
unsigned long vma_offset = vma->vm_pgoff << PAGE_SHIFT;
struct kgsl_device_private *dev_priv = file->private_data;
struct kgsl_process_private *private = dev_priv->process_priv;
- struct kgsl_mem_entry *tmp, *entry = NULL;
+ struct kgsl_mem_entry *entry = NULL;
struct kgsl_device *device = dev_priv->device;
/* Handle leagacy behavior for memstore */
@@ -2126,13 +2144,11 @@
/* Find a chunk of GPU memory */
spin_lock(&private->mem_lock);
- list_for_each_entry(tmp, &private->mem_list, list) {
- if (vma_offset == tmp->memdesc.gpuaddr) {
- kgsl_mem_entry_get(tmp);
- entry = tmp;
- break;
- }
- }
+ entry = kgsl_sharedmem_find(private, vma_offset);
+
+ if (entry)
+ kgsl_mem_entry_get(entry);
+
spin_unlock(&private->mem_lock);
if (entry == NULL)
diff --git a/drivers/gpu/msm/kgsl.h b/drivers/gpu/msm/kgsl.h
index 20ed808..3dafbb9 100644
--- a/drivers/gpu/msm/kgsl.h
+++ b/drivers/gpu/msm/kgsl.h
@@ -132,7 +132,7 @@
int memtype;
int flags;
void *priv_data;
- struct list_head list;
+ struct rb_node node;
uint32_t free_timestamp;
/* back pointer to private structure under whose context this
* allocation is made */
diff --git a/drivers/gpu/msm/kgsl_device.h b/drivers/gpu/msm/kgsl_device.h
index 2eacf22..69964e3 100644
--- a/drivers/gpu/msm/kgsl_device.h
+++ b/drivers/gpu/msm/kgsl_device.h
@@ -216,7 +216,7 @@
unsigned int refcnt;
pid_t pid;
spinlock_t mem_lock;
- struct list_head mem_list;
+ struct rb_root mem_rb;
struct kgsl_pagetable *pagetable;
struct list_head list;
struct kobject kobj;