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

[PATCH v8 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 v8: 
Use a clearer API name to map/unmap the write-protected memory in
ioreq server.

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 v8 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

Re: [PATCH v8 1/3] Remove identical relationship between ioreq type and rangeset type.

[Jan Beulich]

>>> On 23.08.15 at 11:33, <yu.c.zhang@linux.intel.com> wrote:
> --- 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;

Hard tabs.

With that fixed
Acked-by: Jan Beulich <jbeulich@suse.com>

[PATCH v8 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..2313223 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_wp_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_wp_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..253a200 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_wp_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_wp_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 v8 2/3] Differentiate IO/mem resources tracked by ioreq server

[Wei Liu]

On Sun, Aug 23, 2015 at 05:33:17PM +0800, Yu Zhang wrote:
> 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 ++++++++++++++++++++++++++++++++++++++++

For tools bits:

Acked-by: Wei Liu <wei.liu2@citrix.com>

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

[Yu, Zhang]

On 8/25/2015 5:40 PM, Wei Liu wrote:
> On Sun, Aug 23, 2015 at 05:33:17PM +0800, Yu Zhang wrote:
>> 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 ++++++++++++++++++++++++++++++++++++++++
>
> For tools bits:
>
> Acked-by: Wei Liu <wei.liu2@citrix.com>

Thank you, Wei.
To other maintainers, do you have any question or suggestion?
Any advices would be appreciated! Thanks! :)

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

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

[Jan Beulich]

>>> On 28.08.15 at 05:11, <yu.c.zhang@linux.intel.com> wrote:
> To other maintainers, do you have any question or suggestion?

I certainly intend to get to reviewing these patches, but my originally
huge backlog hasn't shrunk enough yet.

Jan

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

[Yu, Zhang]

On 8/28/2015 4:38 PM, Jan Beulich wrote:
>>>> On 28.08.15 at 05:11, <yu.c.zhang@linux.intel.com> wrote:
>> To other maintainers, do you have any question or suggestion?
>
> I certainly intend to get to reviewing these patches, but my originally
> huge backlog hasn't shrunk enough yet.
>
> Jan
>

Thanks for your reply, Jan. And I fully understand. Take your time. :)

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

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

[Ian Campbell]

On Tue, 2015-08-25 at 10:40 +0100, Wei Liu wrote:
> On Sun, Aug 23, 2015 at 05:33:17PM +0800, Yu Zhang wrote:
> > 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 
> > ++++++++++++++++++++++++++++++++++++++++
> 
> For tools bits:
> 
> Acked-by: Wei Liu <wei.liu2@citrix.com>

I looked at it before I saw this and as a binding for the hypercall it LGTM
as well:

Acked-by: Ian Campbell <ian.campbell@citrix.com>

There appear to be no callers of these new interfaces, are those to come
later?

Given the trivial nature of the tools side here I'm likely not going to pay
much attention to this series from now on, please drop me an explicit ping
if something changes which requires my attention.

Ian.

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

[Jan Beulich]

>>> On 23.08.15 at 11:33, <yu.c.zhang@linux.intel.com> wrote:
> --- 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" :
>                        "");

This is becoming unwieldy - please use a static array to get at the
strings.

> @@ -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);
> +        }

I doubt you really want to alter the type when !ram_page. Plus
this altering of the type - if really needed / intended - should be
explained in a comment (after all you have an explicit type for the
caller to pass).

> @@ -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) )

PFN_DOWN() or paddr_to_pfn() please.

> --- 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

If you want this to be done in this patch, then this and patch 3
need to change their order.

> --- 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 */

"memory" is too vague, considering that you mean RAM here and
"MEMORY" above stands for MMIO.

Jan

[PATCH v8 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

Re: [PATCH v8 3/3] Refactor rangeset structure for better performance.

[Jan Beulich]

>>> On 23.08.15 at 11:33, <yu.c.zhang@linux.intel.com> wrote:
>  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 )

Please be consistent throughout the patch: Either always compare
with NULL (like done earlier on) or (preferred) never spell this out
(like done here).

> @@ -410,7 +448,7 @@ void rangeset_domain_destroy(
>  
>  void rangeset_swap(struct rangeset *a, struct rangeset *b)
>  {
> -    LIST_HEAD(tmp);
> +    struct rb_node* tmp;

* and blank want to be swapped.

Jan