[PATCH v6 07/31] xen/arm: ITS: Add helper functions to manage its_devices

[vijay.kilari@gmail.com]

From: Vijaya Kumar K <Vijaya.Kumar@caviumnetworks.com>

Helper functions to manage its devices using RB-tree
are introduced in physical ITS driver.

This is global list of all the devices.

Signed-off-by: Vijaya Kumar K <Vijaya.Kumar@caviumnetworks.com>
Acked-by: Ian Campbell <ian.campbell@citrix.com>
Reviewed-by: Julien Grall <julien.grall@citrix.com>
---
v5: - Added assert on spinlock
v4: - Remove passing of root node as parameter
    - Declare prototype in header file
    - Rename find_its_device to its_find_device
---
 xen/arch/arm/gic-v3-its.c     |   53 +++++++++++++++++++++++++++++++++++++++++
 xen/include/asm-arm/gic-its.h |    3 +++
 2 files changed, 56 insertions(+)

diff --git a/xen/arch/arm/gic-v3-its.c b/xen/arch/arm/gic-v3-its.c
index 4ad8d8e..88cc89d 100644
--- a/xen/arch/arm/gic-v3-its.c
+++ b/xen/arch/arm/gic-v3-its.c
@@ -93,6 +93,8 @@ struct its_node {
 static LIST_HEAD(its_nodes);
 static DEFINE_SPINLOCK(its_lock);
 static struct rdist_prop  *gic_rdists;
+static struct rb_root rb_its_dev;
+static DEFINE_SPINLOCK(rb_its_dev_lock);
 
 #define gic_data_rdist()    (this_cpu(rdist))
 
@@ -115,6 +117,55 @@ static struct its_collection *dev_event_to_col(struct its_device *dev,
     return its->collections + dev->event_map.col_map[event];
 }
 
+/* RB-tree helpers for its_device */
+static struct its_device *its_find_device(u32 devid)
+{
+    struct rb_node *node = rb_its_dev.rb_node;
+
+    ASSERT(spin_is_locked(&rb_its_dev_lock));
+    while ( node )
+    {
+        struct its_device *dev;
+
+        dev = container_of(node, struct its_device, node);
+        if ( devid < dev->device_id )
+            node = node->rb_left;
+        else if ( devid > dev->device_id )
+            node = node->rb_right;
+        else
+            return dev;
+    }
+
+    return NULL;
+}
+
+static int its_insert_device(struct its_device *dev)
+{
+    struct rb_node **new, *parent;
+
+    ASSERT(spin_is_locked(&rb_its_dev_lock));
+    new = &rb_its_dev.rb_node;
+    parent = NULL;
+    while ( *new )
+    {
+        struct its_device *this;
+
+        this  = container_of(*new, struct its_device, node);
+        parent = *new;
+        if ( dev->device_id < this->device_id )
+            new = &((*new)->rb_left);
+        else if ( dev->device_id > this->device_id )
+            new = &((*new)->rb_right);
+        else
+            return -EEXIST;
+    }
+
+    rb_link_node(&dev->node, parent, new);
+    rb_insert_color(&dev->node, &rb_its_dev);
+
+    return 0;
+}
+
 #define ITS_CMD_QUEUE_SZ            SZ_64K
 #define ITS_CMD_QUEUE_NR_ENTRIES    (ITS_CMD_QUEUE_SZ / sizeof(its_cmd_block))
 
@@ -939,6 +990,8 @@ static int its_probe(struct dt_device_node *node)
     list_add(&its->entry, &its_nodes);
     spin_unlock(&its_lock);
 
+    rb_its_dev = RB_ROOT;
+
     return 0;
 
 out_free_tables:
diff --git a/xen/include/asm-arm/gic-its.h b/xen/include/asm-arm/gic-its.h
index 259b0fe..70e7f54 100644
--- a/xen/include/asm-arm/gic-its.h
+++ b/xen/include/asm-arm/gic-its.h
@@ -19,6 +19,7 @@
 #define __ASM_ARM_GIC_ITS_H__
 
 #include <asm/gic_v3_defs.h>
+#include <xen/rbtree.h>
 
 /*
  * ITS registers, offsets from ITS_base
@@ -266,6 +267,8 @@ struct its_device {
     struct event_lpi_map    event_map;
     /* Physical Device id */
     u32                     device_id;
+    /* RB-tree entry */
+    struct rb_node          node;
 };
 
 int its_init(struct rdist_prop *rdists);
-- 
1.7.9.5