From nobody Fri May 17 05:26:37 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1667325631; cv=none; d=zohomail.com; s=zohoarc; b=Q99C9v0oGDOMpOGEti2vIph3H/8cfbYUJgU8/QmvPSxF3BStVpKWjr9nAVs3HMYsGDBDbxYBdE00d9+NrNW7ubvPPYqhuCxA1I0AkkP87rsM9aY5Fn/ACStcw5+xVKqppIGXgV9bN3M0KvYSLRqJryWzpMs+cFKtTenZS46xv7E= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1667325631; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=NibbleQ6qVs4xQcEKphov4U2mitBRSmFzM5yECYLMZs=; b=AqoAssbqyL+G2EhFp8CUh91uLpVM+y6Ku2c3Dv0u1IbiDY2Iu5/9VN/8jwmWIGG5HwxDt/9PTpZQYI8s+GaOZe4WkKBvQ3uyWwT5AuCcHhoZDKpL3Bk7V2oYWo7dn1EYJAlCVI5b7DArBhw7upgg3cu9K8PY+8rxfunBf06WaTE= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1667325631029416.81765074754776; Tue, 1 Nov 2022 11:00:31 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.435179.688306 (Exim 4.92) (envelope-from ) id 1opvYG-00074g-Mi; Tue, 01 Nov 2022 17:59:52 +0000 Received: by outflank-mailman (output) from mailman id 435179.688306; Tue, 01 Nov 2022 17:59:52 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1opvYG-00074Z-Jl; Tue, 01 Nov 2022 17:59:52 +0000 Received: by outflank-mailman (input) for mailman id 435179; Tue, 01 Nov 2022 17:59:51 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1opvYF-0006ou-3H for xen-devel@lists.xenproject.org; Tue, 01 Nov 2022 17:59:51 +0000 Received: from esa4.hc3370-68.iphmx.com (esa4.hc3370-68.iphmx.com [216.71.155.144]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id f987485f-5a0e-11ed-8fd0-01056ac49cbb; Tue, 01 Nov 2022 18:59:49 +0100 (CET) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: f987485f-5a0e-11ed-8fd0-01056ac49cbb DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1667325589; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=GczOI6dOgGkSiOucAzErsvhWg4FDt4sWmOiy0PcUCiw=; b=eHIMTdmh2hTYoHE/V+EdBpAfArYXaERD995BdvnQJsVlpWP81GrpbUpf IXDZjrgp9yQBOKTv6mRJuBllf3qCdR8vl1gzugCnJmQ5YlfLTZW9I8Ftf zTCh9rgZ8UsUGaCna9w5Ue8+YFdsKKnizsw9mceYDU/l1qQ5xalq2HXWx s=; Authentication-Results: esa4.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none X-SBRS: 2.7 X-MesageID: 86481058 X-Ironport-Server: esa4.hc3370-68.iphmx.com X-Remote-IP: 162.221.156.83 X-Policy: $RELAYED IronPort-Data: A9a23:CqrAvK6HpKl6A7m5+udmkQxRtDrHchMFZxGqfqrLsTDasY5as4F+v jcZWmmCaKqCMTH1LYpyOoi0pxkFuMSEmtVmQQRlqHtmHi5G8cbLO4+Ufxz6V8+wwm8vb2o8t plDNYOQRCwQZiWBzvt4GuG59RGQ7YnRGvynTraBYnoqLeNdYH9JoQp5nOIkiZJfj9G8Agec0 fv/uMSaM1K+s9JOGjt8B5mr9VU+4ZwehBtC5gZkPKkT5QeE/5UoJMl3yZ+ZfiOQrrZ8RoZWd 86bpJml82XQ+QsaC9/Nut4XpWVTH9Y+lSDX4pZnc/DKbipq/0Te4Y5iXBYoUm9Fii3hojxE4 I4lWapc6+seFvakdOw1C3G0GszlVEFM0OevzXOX6aR/w6BaGpdFLjoH4EweZOUlFuhL7W5m9 c0hcRs3QFO4xKGU253kSLNFpsgcBZy+VG8fkikIITDxCP8nRdbIQrnQ5M8e1zA17ixMNa+AP YxDM2MpNUmeJU0UUrsUIMtWcOOAi3XhcjsetFWPoqkf6GnP1g1hlrPqNbI5f/TaG5kFxx7F9 goq+UynX0kXMdyV2wCDrGuHl8PvnCXdSZ4dQejQGvlC3wTImz175ActfUS/iem0jAi5Qd03A 0Ad5CcGt6U5802vCN7nUHWQsHOC+xIRRddUO+k78x2WjLrZ5R6DAWoJRSIHb8Yp3PLaXhRzi AXPxYmwQ2Uy7vvFEhpx64t4sxuyCBFMBlUsJhRHDikezIbh+qgTgi3mG4ML/LGOsvX5HjT5w javpSc4hqkOgcNj65hX7WwrkBr3+MGXE1ddChH/Gzv8s1gnPNLNi5mAswCz0BpWEGqOorBtV lAgktPW0u0BBIrleMelELRUR+HBCxpo3VThbb9T83sJrWrFF52LJ9o4DNRCyKBBa59sRNMRS BWP0T69HbcKVJdQUYd5YpiqF+MhxrX6GNLuW5j8N4QQPcItLVTdp3AzOCZ8OlwBd2B1z8kC1 WqzK57wXR7294w6pNZJewvt+eBynX1vrY8ibZv60w6mwdKjiI29EN843K+1RrlgtMu5TPD9q Yk32z2il0oCC4UTo0D/reYuELz9BSNgXs2q9JcHL7Drz8gPMDhJNsI9CIgJI+RN95m5XM+Sl p1hcie0EGbCuEA= IronPort-HdrOrdr: A9a23:TUFdLqG+5LsUrrVgpLqEGMeALOsnbusQ8zAXPiBKJCC9E/bo8P xG+c5w6faaslkssR0b9+xofZPwIk80lqQFhbX5X43DYOCOggLBQL2Kr7GSoQEIcxeUygc379 YET0ERMrzN5VgRt7eH3OG7eexQv+VuJsqT9JnjJ3QGd3AaV0l5hT0JbDpyiidNNXN77ZxSLu vk2uN34wCOVF4wdcqBCnwMT4H41qD2fMKPW29/O/Y/gjP+9g+V1A== X-IronPort-AV: E=Sophos;i="5.95,231,1661832000"; d="scan'208";a="86481058" From: =?UTF-8?q?Edwin=20T=C3=B6r=C3=B6k?= To: CC: , =?UTF-8?q?Edwin=20T=C3=B6r=C3=B6k?= , Christian Lindig , David Scott , Wei Liu , Anthony PERARD Subject: [PATCH for-4.17 v1 1/2] xenctrl.ml: make domain_getinfolist tail recursive Date: Tue, 1 Nov 2022 17:59:16 +0000 Message-ID: <6e9ee150c5f393f2d403a71ac540ff0d621100ab.1667324874.git.edvin.torok@citrix.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1667325632251100005 On a host with ~1000 VMs (the support limit for XAPI) domain_getinfolist took O(n^2) time (n=3Dnumber 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=C3=B6r=C3=B6k Tested-by: Pau Ruiz Safont Acked-by: Christian Lindig --- 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 =3D "stub_xc_domain_getinfolist" =20 +let rev_append_fold acc e =3D 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]]] =3D [5; 6; 7; 8; 9; 10] +*) +let rev_concat lst =3D List.fold_left rev_append_fold [] lst + let domain_getinfolist handle first_domain =3D let nb =3D 2 in - let last_domid l =3D (List.hd l).domid + 1 in - let rec __getlist from =3D - let l =3D _domain_getinfolist handle from nb in - (if List.length l =3D nb then __getlist (last_domid l) else []) @ l - in - List.rev (__getlist first_domain) + let rec __getlist lst from =3D + (* _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 =20 external domain_getinfo: handle -> domid -> domaininfo=3D "stub_xc_domain_= getinfo" =20 --=20 2.34.1 From nobody Fri May 17 05:26:37 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1667325628; cv=none; d=zohomail.com; s=zohoarc; b=EPTFdqB2x9fyG4x0YXX4gN388ht18GCLKH1emmP7gEW5rAPOkmFv9REkx/OkbMlLRPOYc/rRuwmR3QzXDtoQ446jo1Z3RG1TIdfjORfGaXXjKnFXzAX4plPDUbCy7QI5pRdDfaW13RY2TA6d9QlAlCuf2TiciOHcJGHYH4sUL0o= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1667325628; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=4sXjxoLRZIGx3NFESvuoRl8vhEkiLX5ccubjAA4w7Vs=; b=M5bczdjOdobjKc2m+S7BiWRoEetvy43AV5m/zQrY65yRPj6x9uw/Fr24UzAI/8c1CVHbW3vPBskSvgZzMFMV50rpFYf2wuWH/ZpKG0yyOc4G2owTgNv7cjavczOqWLxKz0IhFWjHzcu0PQDRHUPVaPj6Gsydnw6GO2p8dCLCXr0= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1667325628213121.94059895554358; Tue, 1 Nov 2022 11:00:28 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.435180.688317 (Exim 4.92) (envelope-from ) id 1opvYK-0007Lx-VM; Tue, 01 Nov 2022 17:59:56 +0000 Received: by outflank-mailman (output) from mailman id 435180.688317; Tue, 01 Nov 2022 17:59:56 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1opvYK-0007Lq-SI; Tue, 01 Nov 2022 17:59:56 +0000 Received: by outflank-mailman (input) for mailman id 435180; Tue, 01 Nov 2022 17:59:55 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1opvYJ-0007Ki-Nm for xen-devel@lists.xenproject.org; Tue, 01 Nov 2022 17:59:55 +0000 Received: from esa6.hc3370-68.iphmx.com (esa6.hc3370-68.iphmx.com [216.71.155.175]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id fbff9131-5a0e-11ed-91b5-6bf2151ebd3b; Tue, 01 Nov 2022 18:59:54 +0100 (CET) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: fbff9131-5a0e-11ed-91b5-6bf2151ebd3b DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1667325593; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=1BFJHHFskkYwrDc+C5nugZc7KAKVNuo0AeEB6cAz2Ac=; b=AKxvz6YnDCOszHd+cJLKs3kTgFtCgnathi9qor3hj+O0VGmjqyrpJq/o 0Onwfr92DqqYBOmIEl08UAbNT56pe4dE2gjeXqILJjfhtw1/M0zQYH033 tUdSNauPsNiCrzJQG+dq1ibShfQKlagj6rSF74jQq+7PMy8Gz/9rUuFyq s=; Authentication-Results: esa6.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none X-SBRS: 2.7 X-MesageID: 83555985 X-Ironport-Server: esa6.hc3370-68.iphmx.com X-Remote-IP: 162.221.156.83 X-Policy: $RELAYED IronPort-Data: A9a23:W9spzqqhDI3c791hhctDyL4LHM1eBmIaZRIvgKrLsJaIsI4StFCzt garIBnVPqmCZmT8fd4jOYjj9ksHvZXTmoNrSwA5/i82QXkR8JuZCYyVIHmrMnLJJKUvbq7FA +Y2MYCccZ9uHhcwgj/3b9ANeFEljfngqoLUUbKCYWYpAFc+E0/NsDo788YhmIlknNOlNA2Ev NL2sqX3NUSsnjV5KQr40YrawP9UlKm06W5wUmAWP6gR5gaHzyBNVvrzGInqR5fGatgMdgKFb 76rIIGRpgvx4xorA9W5pbf3GmVirmn6ZFXmZtJ+AsBOszAazsAA+v9T2Mk0MC+7vw6hjdFpo OihgLTrIesf0g8gr8xGO/VQO3kW0aSrY9YrK1Dn2SCY5xWun3cBX5yCpaz5VGEV0r8fPI1Ay RAXAC5VagyTnOOI/KOQa7ZQjM5yL5DPGqpK7xmMzRmBZRonaZXKQqGM7t5ExjYgwMtJGJ4yZ eJAN2ApNk6ZJUQSZBFHU/rSn8/x7pX7WzBUtlOT47Yw+W/Q5AdwzKLsIJzefdniqcB9zh3F+ z+XrzmR7hcyM/qdy2CcyG6Wv8jipn76VIwONYaq+as/6LGU7jNKU0BHPbehmtGph0j7V99BJ kg8/is1sbN05EGtVsP6XRCzvDiDpBF0c9ZZDeAS8gyGzavQpQGDCQAsUTppeNEg8sgsSlQXO kShxo2zQ2Y16fvMFCzbpuz8QS6O1TY9MzcGeT8fTDU58vLC/705hEPMF/JFOfvg5jHqIg3Yz zePpSk4orwci88Xyqm2lWz6byKQSovhFVBsuFiONo6xxkYgPdP+OdT0gbTOxawYRLt1WGVtq 5TtdyK2yOkVRa+AmyWWKAnmNOH4vq3VWNEwbLMGInXAy9hP0yT9FWyzyGskTKuMDirjUWawC HI/QSsLuPdu0IKCNMebmb6ZBcUw1rTHHt/4TP3SZdcmSsEvKlDdoHg1PxXBgj2FfK0QfUYXY MnzTCpRJSxCVfQPIMSeGo/xLoPHNghhnDiOFPgXPjys0KaEZW79dFv2GALmUwzN14vd+V29z jqqH5HVo/mpeLGhP3K/HE96BQxiEEXX8rit8JcKKrHYclM4cIzjYteIqY4cl0Vet/w9vo/1E ruVAye0FHKXaaX7FDi3 IronPort-HdrOrdr: A9a23:hiF3n62h8t59zmxs1GuCIAqjBIokLtp133Aq2lEZdPRUGvb3qy nIpoVj6faUskd2ZJhOo7C90cW7LU80sKQFhLX5Xo3SOzUO2lHYT72KhLGKq1aLdhEWtNQtsZ uIG5IOcOEYZmIasS+V2maF+q4bsbu6zJw= X-IronPort-AV: E=Sophos;i="5.95,231,1661832000"; d="scan'208";a="83555985" From: =?UTF-8?q?Edwin=20T=C3=B6r=C3=B6k?= To: CC: , =?UTF-8?q?Edwin=20T=C3=B6r=C3=B6k?= , Christian Lindig , David Scott , Wei Liu , Anthony PERARD Subject: [PATCH for-4.17 v1 2/2] xenctrl: use larger chunksize in domain_getinfolist Date: Tue, 1 Nov 2022 17:59:17 +0000 Message-ID: X-Mailer: git-send-email 2.34.1 In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1667325630555100003 The support limit of XAPI is 1000, so using 1024 will very likely get everything in one go. Other code in Xen also uses chunk sizes of 256 or 1024, and would be much better than 2, especially now that list construction is more efficient. Xenopsd should also use `domain_getinfo` instead of `domain_getinfolist` in a lot of places where info list is used, but that is another optimization. Signed-off-by: Edwin T=C3=B6r=C3=B6k Tested-by: Pau Ruiz Safont Acked-by: Christian Lindig --- tools/ocaml/libs/xc/xenctrl.ml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tools/ocaml/libs/xc/xenctrl.ml b/tools/ocaml/libs/xc/xenctrl.ml index 3ebedffdc7..a56539ff2c 100644 --- a/tools/ocaml/libs/xc/xenctrl.ml +++ b/tools/ocaml/libs/xc/xenctrl.ml @@ -237,7 +237,7 @@ let rev_append_fold acc e =3D List.rev_append e acc let rev_concat lst =3D List.fold_left rev_append_fold [] lst =20 let domain_getinfolist handle first_domain =3D - let nb =3D 2 in + let nb =3D 1024 in let rec __getlist lst from =3D (* _domain_getinfolist returns domains in reverse order, largest first *) match _domain_getinfolist handle from nb with --=20 2.34.1