[PATCH for-4.17 v1 1/2] xenctrl.ml: make domain_getinfolist tail recursive

[Edwin Török <edvin.torok@xxxxxxxxxx>]

On a host with ~1000 VMs (the support limit for XAPI) domain_getinfolist
took O(n^2) time (n=number of domains).
This couples with xenopsd making inefficient calls to
domain_getinfolist(1 call/VM) resulted in visibly bad performance of
XAPI.

It was calling the Xen domainfolist hypercall N/2 times.
Optimize this such that it is called at most 2 times during normal use.

Implement a tail recursive `rev_concat` equivalent to `concat |> rev`,
and use it instead of calling `@` multiple times.

The added benefit is that the list of domains should now actually be in
increasing order instead of having pairs of 2 changing direction every time.

Signed-off-by: Edwin Török <edvin.torok@xxxxxxxxxx>
Tested-by: Pau Ruiz Safont <pau.safont@xxxxxxxxxx>
---
 tools/ocaml/libs/xc/xenctrl.ml | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)

diff --git a/tools/ocaml/libs/xc/xenctrl.ml b/tools/ocaml/libs/xc/xenctrl.ml
index 28ed642231..3ebedffdc7 100644
--- a/tools/ocaml/libs/xc/xenctrl.ml
+++ b/tools/ocaml/libs/xc/xenctrl.ml
@@ -226,14 +226,25 @@ external domain_shutdown: handle -> domid -> 
shutdown_reason -> unit
 external _domain_getinfolist: handle -> domid -> int -> domaininfo list
        = "stub_xc_domain_getinfolist"
 
+let rev_append_fold acc e = List.rev_append e acc
+
+(**
+       [rev_concat lst] is equivalent to [lst |> List.concat |> List.rev]
+       except it is tail recursive, whereas [List.concat] isn't.
+       Example:
+       rev_concat [[10;9;8];[7;6];[5]]] = [5; 6; 7; 8; 9; 10]
+*)
+let rev_concat lst = List.fold_left rev_append_fold [] lst
+
 let domain_getinfolist handle first_domain =
        let nb = 2 in
-       let last_domid l = (List.hd l).domid + 1 in
-       let rec __getlist from =
-               let l = _domain_getinfolist handle from nb in
-               (if List.length l = nb then __getlist (last_domid l) else []) @ 
l
-               in
-       List.rev (__getlist first_domain)
+       let rec __getlist lst from =
+               (* _domain_getinfolist returns domains in reverse order, 
largest first *)
+               match _domain_getinfolist handle from nb with
+               | [] -> rev_concat lst
+               | (hd :: _) as l -> __getlist (l :: lst) (hd.domid + 1)
+       in
+       __getlist [] first_domain
 
 external domain_getinfo: handle -> domid -> domaininfo= 
"stub_xc_domain_getinfo"
 
-- 
2.34.1