[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [xen stable-4.16] tools/ocaml/xenctrl: Make domain_getinfolist tail recursive
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
|
![]() |
Lists.xenproject.org is hosted with RackSpace, monitoring our |