[xen stable-4.16] tools/ocaml/xenctrl: Make domain_getinfolist tail recursive

[patchbot@xxxxxxx]

commit c6a3d14df051bae0323af539e34cf5a65fba1112
Author:     Edwin Török <edvin.torok@xxxxxxxxxx>
AuthorDate: Tue Nov 1 17:59:16 2022 +0000
Commit:     Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
CommitDate: Thu Feb 9 15:58:51 2023 +0000

    tools/ocaml/xenctrl: Make domain_getinfolist tail recursive
    
    domain_getinfolist() is quadratic with the number of domains, because of the
    behaviour of the underlying hypercall.  xenopsd was further observed to be
    wasting excessive quantites of time manipulating the list of 
already-obtained
    domains.
    
    Implement a tail recursive `rev_concat` equivalent to `concat |> rev`, and 
use
    it instead of calling `@` multiple times.
    
    An incidental benefit is that the list of domains will now be in domid 
order,
    instead of having pairs of 2 domains changing direction every time.
    
    In a scalability testing scenario with ~1000 VMs, a combination of this and
    the subsequent change takes xenopsd's wallclock time in domain_getinfolist()
    down from 88% to 0.02%
    
    Signed-off-by: Edwin Török <edvin.torok@xxxxxxxxxx>
    Tested-by: Pau Ruiz Safont <pau.safont@xxxxxxxxxx>
    Acked-by: Christian Lindig <christian.lindig@xxxxxxxxxx>
    (cherry picked from commit c3b6be714c64aa62b56d0bce96f4b6a10b5c2078)
---
 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 7503031d8f..f10b686215 100644
--- a/tools/ocaml/libs/xc/xenctrl.ml
+++ b/tools/ocaml/libs/xc/xenctrl.ml
@@ -212,14 +212,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"
 
--
generated by git-patchbot for /home/xen/git/xen.git#stable-4.16