[PATCH v7 0/3] Refactor ioreq server for better performance.

[PATCH v7 0/3] Refactor ioreq server for better performance.

[Yu Zhang]

XenGT leverages ioreq server to track and forward the accesses to
GPU I/O resources, e.g. the PPGTT(per-process graphic translation
tables). Currently, ioreq server uses rangeset to track the BDF/
PIO/MMIO ranges to be emulated. To select an ioreq server, the 
rangeset is searched to see if the I/O range is recorded. However,
traversing the link list inside rangeset could be time consuming
when number of ranges is too high. On HSW platform, number of PPGTTs
for each vGPU could be several hundred. On BDW, this value could
be several thousand.  This patch series refactored rangeset to base
it on red-back tree, so that the searching would be more efficient. 

Besides, this patchset also splits the tracking of MMIO and guest
ram ranges into different rangesets. And to accommodate more ranges,
limitation of the number of ranges in an ioreq server, MAX_NR_IO_RANGES
is changed - future patches might be provided to tune this with other
approaches.

Changes in v7: 
1> Coding style changes;
2> Fix a typo in hvm_select_ioreq_server().

Changes in v6: 
Break the identical relationship between ioreq type and rangeset
index inside ioreq server.

Changes in v5:
1> Use gpfn, instead of gpa to track guest write-protected pages;
2> Remove redundant conditional statement in routine find_range().

Changes in v4:
Keep the name HVMOP_IO_RANGE_MEMORY for MMIO resources, and add
a new one, HVMOP_IO_RANGE_WP_MEM, for write-protected memory.

Changes in v3:
1> Use a seperate rangeset for guest ram pages in ioreq server;
2> Refactor rangeset, instead of introduce a new data structure.

Changes in v2:
1> Split the original patch into 2;
2> Take Paul Durrant's comments:
  a> Add a name member in the struct rb_rangeset, and use the 'q'
debug key to dump the ranges in ioreq server;
  b> Keep original routine names for hvm ioreq server;
  c> Commit message changes - mention that a future patch to change
the maximum ranges inside ioreq server.

Yu Zhang (3):
  Remove identical relationship between ioreq type and rangeset type.
  Differentiate IO/mem resources tracked by ioreq server
  Refactor rangeset structure for better performance.

 tools/libxc/include/xenctrl.h    | 31 +++++++++++++++
 tools/libxc/xc_domain.c          | 61 ++++++++++++++++++++++++++++++
 xen/arch/x86/hvm/hvm.c           | 39 ++++++++++++++-----
 xen/common/rangeset.c            | 82 +++++++++++++++++++++++++++++-----------
 xen/include/asm-x86/hvm/domain.h |  4 +-
 xen/include/public/hvm/hvm_op.h  |  1 +
 6 files changed, 184 insertions(+), 34 deletions(-)

-- 
1.9.1

[PATCH v7 1/3] Remove identical relationship between ioreq type and rangeset type.

[Yu Zhang]

This patch uses HVMOP_IO_RANGE_XXX values rather than the raw ioreq
type to select the ioreq server, therefore the identical relationship
between ioreq type and rangeset type is no longer necessary.

Signed-off-by: Yu Zhang <yu.c.zhang@linux.intel.com>
Reviewed-by: Paul Durrant <paul.durrant@citrix.com>
---
 xen/arch/x86/hvm/hvm.c | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/xen/arch/x86/hvm/hvm.c b/xen/arch/x86/hvm/hvm.c
index c957610..abf9266 100644
--- a/xen/arch/x86/hvm/hvm.c
+++ b/xen/arch/x86/hvm/hvm.c
@@ -2545,7 +2545,7 @@ struct hvm_ioreq_server *hvm_select_ioreq_server(struct domain *d,
                               PCI_SLOT(CF8_BDF(cf8)),
                               PCI_FUNC(CF8_BDF(cf8)));
 
-        type = IOREQ_TYPE_PCI_CONFIG;
+        type = HVMOP_IO_RANGE_PCI;
         addr = ((uint64_t)sbdf << 32) |
                CF8_ADDR_LO(cf8) |
                (p->addr & 3);
@@ -2563,7 +2563,8 @@ struct hvm_ioreq_server *hvm_select_ioreq_server(struct domain *d,
     }
     else
     {
-        type = p->type;
+        type = (p->type == IOREQ_TYPE_PIO) ?
+		HVMOP_IO_RANGE_PORT : HVMOP_IO_RANGE_MEMORY;
         addr = p->addr;
     }
 
@@ -2579,31 +2580,28 @@ struct hvm_ioreq_server *hvm_select_ioreq_server(struct domain *d,
         if ( !s->enabled )
             continue;
 
-        BUILD_BUG_ON(IOREQ_TYPE_PIO != HVMOP_IO_RANGE_PORT);
-        BUILD_BUG_ON(IOREQ_TYPE_COPY != HVMOP_IO_RANGE_MEMORY);
-        BUILD_BUG_ON(IOREQ_TYPE_PCI_CONFIG != HVMOP_IO_RANGE_PCI);
         r = s->range[type];
 
         switch ( type )
         {
             unsigned long end;
 
-        case IOREQ_TYPE_PIO:
+        case HVMOP_IO_RANGE_PORT:
             end = addr + p->size - 1;
             if ( rangeset_contains_range(r, addr, end) )
                 return s;
 
             break;
-        case IOREQ_TYPE_COPY:
+        case HVMOP_IO_RANGE_MEMORY:
             end = addr + (p->size * p->count) - 1;
             if ( rangeset_contains_range(r, addr, end) )
                 return s;
 
             break;
-        case IOREQ_TYPE_PCI_CONFIG:
+        case HVMOP_IO_RANGE_PCI:
             if ( rangeset_contains_singleton(r, addr >> 32) )
             {
-                p->type = type;
+                p->type = IOREQ_TYPE_PCI_CONFIG;
                 p->addr = addr;
                 return s;
             }
-- 
1.9.1

[PATCH v7 2/3] Differentiate IO/mem resources tracked by ioreq server

[Yu Zhang]

Currently in ioreq server, guest write-protected ram pages are
tracked in the same rangeset with device mmio resources. Yet
unlike device mmio, which can be in big chunks, the guest write-
protected pages may be discrete ranges with 4K bytes each. This
patch uses a seperate rangeset for the guest ram pages.

Note: Previously, a new hypercall or subop was suggested to map
write-protected pages into ioreq server. However, it turned out
handler of this new hypercall would be almost the same with the
existing pair - HVMOP_[un]map_io_range_to_ioreq_server, and there's
already a type parameter in this hypercall. So no new hypercall
defined, only a new type is introduced.

Signed-off-by: Yu Zhang <yu.c.zhang@linux.intel.com>
---
 tools/libxc/include/xenctrl.h    | 31 ++++++++++++++++++++
 tools/libxc/xc_domain.c          | 61 ++++++++++++++++++++++++++++++++++++++++
 xen/arch/x86/hvm/hvm.c           | 23 ++++++++++++++-
 xen/include/asm-x86/hvm/domain.h |  4 +--
 xen/include/public/hvm/hvm_op.h  |  1 +
 5 files changed, 117 insertions(+), 3 deletions(-)

diff --git a/tools/libxc/include/xenctrl.h b/tools/libxc/include/xenctrl.h
index de3c0ad..eb1a526 100644
--- a/tools/libxc/include/xenctrl.h
+++ b/tools/libxc/include/xenctrl.h
@@ -2010,6 +2010,37 @@ int xc_hvm_unmap_io_range_from_ioreq_server(xc_interface *xch,
                                             int is_mmio,
                                             uint64_t start,
                                             uint64_t end);
+/**
+ * This function registers a range of write-protected memory for emulation.
+ *
+ * @parm xch a handle to an open hypervisor interface.
+ * @parm domid the domain id to be serviced
+ * @parm id the IOREQ Server id.
+ * @parm start start of range
+ * @parm end end of range (inclusive).
+ * @return 0 on success, -1 on failure.
+ */
+int xc_hvm_map_mem_range_to_ioreq_server(xc_interface *xch,
+                                         domid_t domid,
+                                         ioservid_t id,
+                                         xen_pfn_t start,
+                                         xen_pfn_t end);
+
+/**
+ * This function deregisters a range of write-protected memory for emulation.
+ *
+ * @parm xch a handle to an open hypervisor interface.
+ * @parm domid the domain id to be serviced
+ * @parm id the IOREQ Server id.
+ * @parm start start of range
+ * @parm end end of range (inclusive).
+ * @return 0 on success, -1 on failure.
+ */
+int xc_hvm_unmap_mem_range_from_ioreq_server(xc_interface *xch,
+                                             domid_t domid,
+                                             ioservid_t id,
+                                             xen_pfn_t start,
+                                             xen_pfn_t end);
 
 /**
  * This function registers a PCI device for config space emulation.
diff --git a/tools/libxc/xc_domain.c b/tools/libxc/xc_domain.c
index 2ee26fb..34f138d 100644
--- a/tools/libxc/xc_domain.c
+++ b/tools/libxc/xc_domain.c
@@ -1552,6 +1552,67 @@ int xc_hvm_unmap_io_range_from_ioreq_server(xc_interface *xch, domid_t domid,
     return rc;
 }
 
+int xc_hvm_map_mem_range_to_ioreq_server(xc_interface *xch,
+                                         domid_t domid,
+                                         ioservid_t id,
+                                         xen_pfn_t start,
+                                         xen_pfn_t end)
+{
+    DECLARE_HYPERCALL;
+    DECLARE_HYPERCALL_BUFFER(xen_hvm_io_range_t, arg);
+    int rc;
+
+    arg = xc_hypercall_buffer_alloc(xch, arg, sizeof(*arg));
+    if ( arg == NULL )
+        return -1;
+
+    hypercall.op     = __HYPERVISOR_hvm_op;
+    hypercall.arg[0] = HVMOP_map_io_range_to_ioreq_server;
+    hypercall.arg[1] = HYPERCALL_BUFFER_AS_ARG(arg);
+
+    arg->domid = domid;
+    arg->id = id;
+    arg->type = HVMOP_IO_RANGE_WP_MEM;
+    arg->start = start;
+    arg->end = end;
+
+    rc = do_xen_hypercall(xch, &hypercall);
+
+    xc_hypercall_buffer_free(xch, arg);
+    return rc;
+}
+
+int xc_hvm_unmap_mem_range_from_ioreq_server(xc_interface *xch,
+                                             domid_t domid,
+                                             ioservid_t id,
+                                             xen_pfn_t start,
+                                             xen_pfn_t end)
+{
+    DECLARE_HYPERCALL;
+    DECLARE_HYPERCALL_BUFFER(xen_hvm_io_range_t, arg);
+    int rc;
+
+    arg = xc_hypercall_buffer_alloc(xch, arg, sizeof(*arg));
+    if ( arg == NULL )
+        return -1;
+
+    hypercall.op     = __HYPERVISOR_hvm_op;
+    hypercall.arg[0] = HVMOP_unmap_io_range_from_ioreq_server;
+    hypercall.arg[1] = HYPERCALL_BUFFER_AS_ARG(arg);
+
+    arg->domid = domid;
+    arg->id = id;
+    arg->type = HVMOP_IO_RANGE_WP_MEM;
+    arg->start = start;
+    arg->end = end;
+
+    rc = do_xen_hypercall(xch, &hypercall);
+
+    xc_hypercall_buffer_free(xch, arg);
+    return rc;
+
+}
+
 int xc_hvm_map_pcidev_to_ioreq_server(xc_interface *xch, domid_t domid,
                                       ioservid_t id, uint16_t segment,
                                       uint8_t bus, uint8_t device,
diff --git a/xen/arch/x86/hvm/hvm.c b/xen/arch/x86/hvm/hvm.c
index abf9266..bfe5383 100644
--- a/xen/arch/x86/hvm/hvm.c
+++ b/xen/arch/x86/hvm/hvm.c
@@ -938,8 +938,9 @@ static int hvm_ioreq_server_alloc_rangesets(struct hvm_ioreq_server *s,
 
         rc = asprintf(&name, "ioreq_server %d %s", s->id,
                       (i == HVMOP_IO_RANGE_PORT) ? "port" :
-                      (i == HVMOP_IO_RANGE_MEMORY) ? "memory" :
+                      (i == HVMOP_IO_RANGE_MEMORY) ? "mmio" :
                       (i == HVMOP_IO_RANGE_PCI) ? "pci" :
+                      (i == HVMOP_IO_RANGE_WP_MEM) ? "wp-ed memory" :
                       "");
         if ( rc )
             goto fail;
@@ -1258,6 +1259,7 @@ static int hvm_map_io_range_to_ioreq_server(struct domain *d, ioservid_t id,
             case HVMOP_IO_RANGE_PORT:
             case HVMOP_IO_RANGE_MEMORY:
             case HVMOP_IO_RANGE_PCI:
+            case HVMOP_IO_RANGE_WP_MEM:
                 r = s->range[type];
                 break;
 
@@ -1309,6 +1311,7 @@ static int hvm_unmap_io_range_from_ioreq_server(struct domain *d, ioservid_t id,
             case HVMOP_IO_RANGE_PORT:
             case HVMOP_IO_RANGE_MEMORY:
             case HVMOP_IO_RANGE_PCI:
+            case HVMOP_IO_RANGE_WP_MEM:
                 r = s->range[type];
                 break;
 
@@ -2523,6 +2526,8 @@ struct hvm_ioreq_server *hvm_select_ioreq_server(struct domain *d,
     uint32_t cf8;
     uint8_t type;
     uint64_t addr;
+    p2m_type_t p2mt;
+    struct page_info *ram_page;
 
     if ( list_empty(&d->arch.hvm_domain.ioreq_server.list) )
         return NULL;
@@ -2566,6 +2571,17 @@ struct hvm_ioreq_server *hvm_select_ioreq_server(struct domain *d,
         type = (p->type == IOREQ_TYPE_PIO) ?
 		HVMOP_IO_RANGE_PORT : HVMOP_IO_RANGE_MEMORY;
         addr = p->addr;
+
+        if ( type == HVMOP_IO_RANGE_MEMORY )
+        {
+            ram_page = get_page_from_gfn(d, p->addr >> PAGE_SHIFT,
+                                         &p2mt, P2M_UNSHARE);
+            if ( p2mt == p2m_mmio_write_dm )
+                type = HVMOP_IO_RANGE_WP_MEM;
+
+            if ( ram_page )
+                put_page(ram_page);
+        }
     }
 
     list_for_each_entry ( s,
@@ -2607,6 +2623,11 @@ struct hvm_ioreq_server *hvm_select_ioreq_server(struct domain *d,
             }
 
             break;
+        case HVMOP_IO_RANGE_WP_MEM:
+            if ( rangeset_contains_singleton(r, addr >> PAGE_SHIFT) )
+                return s;
+
+            break;
         }
     }
 
diff --git a/xen/include/asm-x86/hvm/domain.h b/xen/include/asm-x86/hvm/domain.h
index 992d5d1..b2e4234 100644
--- a/xen/include/asm-x86/hvm/domain.h
+++ b/xen/include/asm-x86/hvm/domain.h
@@ -48,8 +48,8 @@ struct hvm_ioreq_vcpu {
     bool_t           pending;
 };
 
-#define NR_IO_RANGE_TYPES (HVMOP_IO_RANGE_PCI + 1)
-#define MAX_NR_IO_RANGES  256
+#define NR_IO_RANGE_TYPES (HVMOP_IO_RANGE_WP_MEM + 1)
+#define MAX_NR_IO_RANGES  8192
 
 struct hvm_ioreq_server {
     struct list_head       list_entry;
diff --git a/xen/include/public/hvm/hvm_op.h b/xen/include/public/hvm/hvm_op.h
index 014546a..c02c91a 100644
--- a/xen/include/public/hvm/hvm_op.h
+++ b/xen/include/public/hvm/hvm_op.h
@@ -331,6 +331,7 @@ struct xen_hvm_io_range {
 # define HVMOP_IO_RANGE_PORT   0 /* I/O port range */
 # define HVMOP_IO_RANGE_MEMORY 1 /* MMIO range */
 # define HVMOP_IO_RANGE_PCI    2 /* PCI segment/bus/dev/func range */
+# define HVMOP_IO_RANGE_WP_MEM 3 /* Write-protected memory range */
     uint64_aligned_t start, end; /* IN - inclusive start and end of range */
 };
 typedef struct xen_hvm_io_range xen_hvm_io_range_t;
-- 
1.9.1

Re: [PATCH v7 2/3] Differentiate IO/mem resources tracked by ioreq server

[Tian, Kevin]

> From: Yu Zhang [mailto:yu.c.zhang@linux.intel.com]
> Sent: Friday, August 21, 2015 11:31 AM
> 
> Currently in ioreq server, guest write-protected ram pages are
> tracked in the same rangeset with device mmio resources. Yet
> unlike device mmio, which can be in big chunks, the guest write-
> protected pages may be discrete ranges with 4K bytes each. This
> patch uses a seperate rangeset for the guest ram pages.
> 
> Note: Previously, a new hypercall or subop was suggested to map
> write-protected pages into ioreq server. However, it turned out
> handler of this new hypercall would be almost the same with the
> existing pair - HVMOP_[un]map_io_range_to_ioreq_server, and there's
> already a type parameter in this hypercall. So no new hypercall
> defined, only a new type is introduced.
> 
> Signed-off-by: Yu Zhang <yu.c.zhang@linux.intel.com>
> ---
>  tools/libxc/include/xenctrl.h    | 31 ++++++++++++++++++++
>  tools/libxc/xc_domain.c          | 61
> ++++++++++++++++++++++++++++++++++++++++
>  xen/arch/x86/hvm/hvm.c           | 23 ++++++++++++++-
>  xen/include/asm-x86/hvm/domain.h |  4 +--
>  xen/include/public/hvm/hvm_op.h  |  1 +
>  5 files changed, 117 insertions(+), 3 deletions(-)
> 
> diff --git a/tools/libxc/include/xenctrl.h b/tools/libxc/include/xenctrl.h
> index de3c0ad..eb1a526 100644
> --- a/tools/libxc/include/xenctrl.h
> +++ b/tools/libxc/include/xenctrl.h
> @@ -2010,6 +2010,37 @@ int
> xc_hvm_unmap_io_range_from_ioreq_server(xc_interface *xch,
>                                              int is_mmio,
>                                              uint64_t start,
>                                              uint64_t end);
> +/**
> + * This function registers a range of write-protected memory for emulation.
> + *
> + * @parm xch a handle to an open hypervisor interface.
> + * @parm domid the domain id to be serviced
> + * @parm id the IOREQ Server id.
> + * @parm start start of range
> + * @parm end end of range (inclusive).
> + * @return 0 on success, -1 on failure.
> + */
> +int xc_hvm_map_mem_range_to_ioreq_server(xc_interface *xch,
> +                                         domid_t domid,
> +                                         ioservid_t id,
> +                                         xen_pfn_t start,
> +                                         xen_pfn_t end);
> +
> +/**
> + * This function deregisters a range of write-protected memory for emulation.
> + *
> + * @parm xch a handle to an open hypervisor interface.
> + * @parm domid the domain id to be serviced
> + * @parm id the IOREQ Server id.
> + * @parm start start of range
> + * @parm end end of range (inclusive).
> + * @return 0 on success, -1 on failure.
> + */
> +int xc_hvm_unmap_mem_range_from_ioreq_server(xc_interface *xch,
> +                                             domid_t domid,
> +                                             ioservid_t id,
> +                                             xen_pfn_t start,
> +                                             xen_pfn_t end);
> 
>  /**
>   * This function registers a PCI device for config space emulation.
> diff --git a/tools/libxc/xc_domain.c b/tools/libxc/xc_domain.c
> index 2ee26fb..34f138d 100644
> --- a/tools/libxc/xc_domain.c
> +++ b/tools/libxc/xc_domain.c
> @@ -1552,6 +1552,67 @@ int
> xc_hvm_unmap_io_range_from_ioreq_server(xc_interface *xch, domid_t domid,
>      return rc;
>  }
> 
> +int xc_hvm_map_mem_range_to_ioreq_server(xc_interface *xch,
> +                                         domid_t domid,
> +                                         ioservid_t id,
> +                                         xen_pfn_t start,
> +                                         xen_pfn_t end)
> +{

Given that this memory range is write-protected, it might be clearer
to have wp in function name. Otherwise it's easy to mistake the
interface as both r/w covered for the range. Or if you want this
interface to be more generic, then a flag parameter would be required
to further specify wp attribute.

Thanks
Kevin

Re: [PATCH v7 2/3] Differentiate IO/mem resources tracked by ioreq server

[Yu, Zhang]

On 8/21/2015 2:35 PM, Tian, Kevin wrote:
>> From: Yu Zhang [mailto:yu.c.zhang@linux.intel.com]
>> Sent: Friday, August 21, 2015 11:31 AM
>>
>> Currently in ioreq server, guest write-protected ram pages are
>> tracked in the same rangeset with device mmio resources. Yet
>> unlike device mmio, which can be in big chunks, the guest write-
>> protected pages may be discrete ranges with 4K bytes each. This
>> patch uses a seperate rangeset for the guest ram pages.
>>
>> Note: Previously, a new hypercall or subop was suggested to map
>> write-protected pages into ioreq server. However, it turned out
>> handler of this new hypercall would be almost the same with the
>> existing pair - HVMOP_[un]map_io_range_to_ioreq_server, and there's
>> already a type parameter in this hypercall. So no new hypercall
>> defined, only a new type is introduced.
>>
>> Signed-off-by: Yu Zhang <yu.c.zhang@linux.intel.com>
>> ---
>>   tools/libxc/include/xenctrl.h    | 31 ++++++++++++++++++++
>>   tools/libxc/xc_domain.c          | 61
>> ++++++++++++++++++++++++++++++++++++++++
>>   xen/arch/x86/hvm/hvm.c           | 23 ++++++++++++++-
>>   xen/include/asm-x86/hvm/domain.h |  4 +--
>>   xen/include/public/hvm/hvm_op.h  |  1 +
>>   5 files changed, 117 insertions(+), 3 deletions(-)
>>
>> diff --git a/tools/libxc/include/xenctrl.h b/tools/libxc/include/xenctrl.h
>> index de3c0ad..eb1a526 100644
>> --- a/tools/libxc/include/xenctrl.h
>> +++ b/tools/libxc/include/xenctrl.h
>> @@ -2010,6 +2010,37 @@ int
>> xc_hvm_unmap_io_range_from_ioreq_server(xc_interface *xch,
>>                                               int is_mmio,
>>                                               uint64_t start,
>>                                               uint64_t end);
>> +/**
>> + * This function registers a range of write-protected memory for emulation.
>> + *
>> + * @parm xch a handle to an open hypervisor interface.
>> + * @parm domid the domain id to be serviced
>> + * @parm id the IOREQ Server id.
>> + * @parm start start of range
>> + * @parm end end of range (inclusive).
>> + * @return 0 on success, -1 on failure.
>> + */
>> +int xc_hvm_map_mem_range_to_ioreq_server(xc_interface *xch,
>> +                                         domid_t domid,
>> +                                         ioservid_t id,
>> +                                         xen_pfn_t start,
>> +                                         xen_pfn_t end);
>> +
>> +/**
>> + * This function deregisters a range of write-protected memory for emulation.
>> + *
s>> + * @parm xch a handle to an open hypervisor interface.
>> + * @parm domid the domain id to be serviced
>> + * @parm id the IOREQ Server id.
>> + * @parm start start of range
>> + * @parm end end of range (inclusive).
>> + * @return 0 on success, -1 on failure.
>> + */
>> +int xc_hvm_unmap_mem_range_from_ioreq_server(xc_interface *xch,
>> +                                             domid_t domid,
>> +                                             ioservid_t id,
>> +                                             xen_pfn_t start,
>> +                                             xen_pfn_t end);
>>
>>   /**
>>    * This function registers a PCI device for config space emulation.
>> diff --git a/tools/libxc/xc_domain.c b/tools/libxc/xc_domain.c
>> index 2ee26fb..34f138d 100644
>> --- a/tools/libxc/xc_domain.c
>> +++ b/tools/libxc/xc_domain.c
>> @@ -1552,6 +1552,67 @@ int
>> xc_hvm_unmap_io_range_from_ioreq_server(xc_interface *xch, domid_t domid,
>>       return rc;
>>   }
>>
>> +int xc_hvm_map_mem_range_to_ioreq_server(xc_interface *xch,
>> +                                         domid_t domid,
>> +                                         ioservid_t id,
>> +                                         xen_pfn_t start,
>> +                                         xen_pfn_t end)
>> +{
>
> Given that this memory range is write-protected, it might be clearer
> to have wp in function name. Otherwise it's easy to mistake the
> interface as both r/w covered for the range. Or if you want this
> interface to be more generic, then a flag parameter would be required
> to further specify wp attribute.
>
> Thanks
> Kevin
>
Thanks, Kevin. Maybe xc_hvm_[un]map_wp_mem_range_to_ioreq_server
is clearer.

Yu
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xen.org
> http://lists.xen.org/xen-devel
>
>

[PATCH v7 3/3] Refactor rangeset structure for better performance.

[Yu Zhang]

This patch refactors struct rangeset to base it on the red-black
tree structure, instead of on the current doubly linked list. By
now, ioreq leverages rangeset to keep track of the IO/memory
resources to be emulated. Yet when number of ranges inside one
ioreq server is very high, traversing a doubly linked list could
be time consuming. With this patch, the time complexity for
searching a rangeset can be improved from O(n) to O(log(n)).
Interfaces of rangeset still remain the same, and no new APIs
introduced.

Signed-off-by: Yu Zhang <yu.c.zhang@linux.intel.com>
Reviewed-by: Paul Durrant <paul.durrant@citrix.com>
---
 xen/common/rangeset.c | 82 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 60 insertions(+), 22 deletions(-)

diff --git a/xen/common/rangeset.c b/xen/common/rangeset.c
index 6c6293c..cde0d06 100644
--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -10,11 +10,12 @@
 #include <xen/sched.h>
 #include <xen/errno.h>
 #include <xen/rangeset.h>
+#include <xen/rbtree.h>
 #include <xsm/xsm.h>
 
 /* An inclusive range [s,e] and pointer to next range in ascending order. */
 struct range {
-    struct list_head list;
+    struct rb_node node;
     unsigned long s, e;
 };
 
@@ -24,7 +25,7 @@ struct rangeset {
     struct domain   *domain;
 
     /* Ordered list of ranges contained in this set, and protecting lock. */
-    struct list_head range_list;
+    struct rb_root   range_tree;
 
     /* Number of ranges that can be allocated */
     long             nr_ranges;
@@ -45,41 +46,78 @@ struct rangeset {
 static struct range *find_range(
     struct rangeset *r, unsigned long s)
 {
-    struct range *x = NULL, *y;
+    struct rb_node *node;
+    struct range   *x;
+    struct range   *prev = NULL;
 
-    list_for_each_entry ( y, &r->range_list, list )
+    node = r->range_tree.rb_node;
+    while ( node )
     {
-        if ( y->s > s )
-            break;
-        x = y;
+        x = container_of(node, struct range, node);
+        if ( (s >= x->s) && (s <= x->e) )
+            return x;
+        if ( s < x->s )
+            node = node->rb_left;
+        else
+        {
+            prev = x;
+            node = node->rb_right;
+        }
     }
 
-    return x;
+    return prev;
 }
 
 /* Return the lowest range in the set r, or NULL if r is empty. */
 static struct range *first_range(
     struct rangeset *r)
 {
-    if ( list_empty(&r->range_list) )
-        return NULL;
-    return list_entry(r->range_list.next, struct range, list);
+    struct rb_node *node;
+
+    node = rb_first(&r->range_tree);
+    if ( node != NULL )
+        return container_of(node, struct range, node);
+
+    return NULL;
 }
 
 /* Return range following x in ascending order, or NULL if x is the highest. */
 static struct range *next_range(
     struct rangeset *r, struct range *x)
 {
-    if ( x->list.next == &r->range_list )
-        return NULL;
-    return list_entry(x->list.next, struct range, list);
+    struct rb_node *node;
+
+    node = rb_next(&x->node);
+    if ( node )
+        return container_of(node, struct range, node);
+
+    return NULL;
 }
 
 /* Insert range y after range x in r. Insert as first range if x is NULL. */
 static void insert_range(
     struct rangeset *r, struct range *x, struct range *y)
 {
-    list_add(&y->list, (x != NULL) ? &x->list : &r->range_list);
+    struct rb_node **node;
+    struct rb_node *parent = NULL;
+
+    if ( x == NULL )
+        node = &r->range_tree.rb_node;
+    else
+    {
+        node = &x->node.rb_right;
+        parent = &x->node;
+    }
+
+    while ( *node )
+    {
+        parent = *node;
+        node = &parent->rb_left;
+    }
+
+    /* Add new node and rebalance the red-black tree. */
+    rb_link_node(&y->node, parent, node);
+    rb_insert_color(&y->node, &r->range_tree);
 }
 
 /* Remove a range from its list and free it. */
@@ -88,7 +126,7 @@ static void destroy_range(
 {
     r->nr_ranges++;
 
-    list_del(&x->list);
+    rb_erase(&x->node, &r->range_tree);
     xfree(x);
 }
 
@@ -319,7 +357,7 @@ bool_t rangeset_contains_singleton(
 bool_t rangeset_is_empty(
     const struct rangeset *r)
 {
-    return ((r == NULL) || list_empty(&r->range_list));
+    return ((r == NULL) || RB_EMPTY_ROOT(&r->range_tree));
 }
 
 struct rangeset *rangeset_new(
@@ -332,7 +370,7 @@ struct rangeset *rangeset_new(
         return NULL;
 
     rwlock_init(&r->lock);
-    INIT_LIST_HEAD(&r->range_list);
+    r->range_tree = RB_ROOT;
     r->nr_ranges = -1;
 
     BUG_ON(flags & ~RANGESETF_prettyprint_hex);
@@ -410,7 +448,7 @@ void rangeset_domain_destroy(
 
 void rangeset_swap(struct rangeset *a, struct rangeset *b)
 {
-    LIST_HEAD(tmp);
+    struct rb_node* tmp;
 
     if ( a < b )
     {
@@ -423,9 +461,9 @@ void rangeset_swap(struct rangeset *a, struct rangeset *b)
         write_lock(&a->lock);
     }
 
-    list_splice_init(&a->range_list, &tmp);
-    list_splice_init(&b->range_list, &a->range_list);
-    list_splice(&tmp, &b->range_list);
+    tmp = a->range_tree.rb_node;
+    a->range_tree.rb_node = b->range_tree.rb_node;
+    b->range_tree.rb_node = tmp;
 
     write_unlock(&a->lock);
     write_unlock(&b->lock);
-- 
1.9.1