From patchwork Fri Aug 14 22:11:41 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 11715225 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BC85D109B for ; Fri, 14 Aug 2020 22:14:24 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 9847620771 for ; Fri, 14 Aug 2020 22:14:24 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=citrix.com header.i=@citrix.com header.b="ZlKPQRZf" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 9847620771 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwD-000899-W1; Fri, 14 Aug 2020 22:12:37 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwC-000891-1z for xen-devel@lists.xenproject.org; Fri, 14 Aug 2020 22:12:36 +0000 X-Inumbo-ID: ac1994c2-799c-4656-a432-1ce28cd9734c Received: from esa1.hc3370-68.iphmx.com (unknown [216.71.145.142]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id ac1994c2-799c-4656-a432-1ce28cd9734c; Fri, 14 Aug 2020 22:12:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1597443155; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=SMCBsmOzak2flXbv7Zo/YlQyvKHgExmZi0mtL3kNGOc=; b=ZlKPQRZfhRC0Hf0U9ZiW8CyAKhhc5FiGxOZs3ZeNZiiMJqpUkYp/jS2N MQ295C29rc7RGWzvpaB/HrbqqbV9YuNoM0QXn8Or/GenA02gvZi6UyG0h M3/CPz6S1AH7zsmY9ikJT1NAnLKakSnzBt23t7OmBlruYiPGF6UY0MGGx I=; Authentication-Results: esa1.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: 8o2irhUK6ivwW2LwCmgsbAmHRyIZbk6sxuvhZuSNn4hpq4reWoYmwVZjpdYsbegpOvYh31Y/Hj rX+Trj8uYTTx/i4yPQdMJQmtRcBjheyi35nNkQLcHyp+LrpwlApFUKINMzME+WM65kibFpmjpy uaAmcWvvzGt4XDR8wSHZJoI+EKggsKuabmWL1oDzSpbodHTmwPHms1AUncYSEsffTm5ethXrQu wtqJx64k+3PW09sJvNXExBQ54LZNxhjrhDnHpuDVltZR/o77dlitTX8AO3AVrXCC8fbsYL6rCv cgc= X-SBRS: 2.7 X-MesageID: 24917745 X-Ironport-Server: esa1.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.76,313,1592884800"; d="scan'208";a="24917745" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v1 1/6] tools/ocaml/libs/xc: Fix ambiguous documentation comment Date: Fri, 14 Aug 2020 23:11:41 +0100 Message-ID: X-Mailer: git-send-email 2.25.1 In-Reply-To: References: MIME-Version: 1.0 X-ClientProxiedBy: FTLPEX02CAS02.citrite.net (10.13.99.123) To AMSPEX02CL02.citrite.net (10.69.22.126) X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" Signed-off-by: Edwin Török --- tools/ocaml/libs/xc/xenctrl.mli | 2 ++ 1 file changed, 2 insertions(+) diff --git a/tools/ocaml/libs/xc/xenctrl.mli b/tools/ocaml/libs/xc/xenctrl.mli index 26ec7e59b1..f7f6ec570d 100644 --- a/tools/ocaml/libs/xc/xenctrl.mli +++ b/tools/ocaml/libs/xc/xenctrl.mli @@ -132,8 +132,10 @@ external interface_close : handle -> unit = "stub_xc_interface_close" * interface_open and interface_close or with_intf although mixing both * is possible *) val with_intf : (handle -> 'a) -> 'a + (** [get_handle] returns the global handle used by [with_intf] *) val get_handle: unit -> handle option + (** [close handle] closes the handle maintained by [with_intf]. This * should only be closed before process exit. It must not be called from * a function called directly or indirectly by with_intf as this From patchwork Fri Aug 14 22:11:42 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 11715227 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 26CD214F6 for ; Fri, 14 Aug 2020 22:14:25 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 02C5E20771 for ; Fri, 14 Aug 2020 22:14:25 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=citrix.com header.i=@citrix.com header.b="LHLwtQZL" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 02C5E20771 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwH-00089S-8X; Fri, 14 Aug 2020 22:12:41 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwG-000891-Ql for xen-devel@lists.xenproject.org; Fri, 14 Aug 2020 22:12:40 +0000 X-Inumbo-ID: edf2a22b-ff50-4a2b-995d-a1c07ad16467 Received: from esa1.hc3370-68.iphmx.com (unknown [216.71.145.142]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id edf2a22b-ff50-4a2b-995d-a1c07ad16467; Fri, 14 Aug 2020 22:12:35 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1597443157; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=YT4HghR0/mQiuB+0ZHbTT8P7/FFGJ4MPWIY1ryiFPUA=; b=LHLwtQZLD17xQqjSbeBzxiZcSTcuuUWjOegjl7MuxhyjR7awPjWkhsaV fztKWKLoh0vyvZcG3s6uGvCdYQ2k9ci/Ey7uE3CUJlBvRyTYRavf6Bv/5 hZ8g2/MAo8nZcTRPvL3f15x9QyIaBWGj2Z6ODLJScmSZErmhrBgpUGS+h s=; Authentication-Results: esa1.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: VRvqjG0Z9Mii4Qho8718sZXP81D4c5CkfE7hbkOyWgAzlSlmlT1PvrS9bXzuUa3RLdBPVilUmF XqSvTvYm0ejKdlYLNLlttH4vzu+WO/5uBcqARR1edle/G12D4uhks0WxHj0TV9OgZ6atM+7POY f/gufhcM35e8/OcAwkVpOrAaHcyIz9oAdfujTOTw3Rrs/RnG+0F90xRPAcUvKCHiNO9aJpjvhK tAVZXS7YN2nzVLmD6FnrPEIUQPwa7Z0t/OY3x2CVHVrzLkcbEYharJIyhclc5eJOXQPsfrAxE+ Q+k= X-SBRS: 2.7 X-MesageID: 24917746 X-Ironport-Server: esa1.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.76,313,1592884800"; d="scan'208";a="24917746" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v1 2/6] tools/ocaml/xenstored: fix deprecation warning Date: Fri, 14 Aug 2020 23:11:42 +0100 Message-ID: X-Mailer: git-send-email 2.25.1 In-Reply-To: References: MIME-Version: 1.0 X-ClientProxiedBy: FTLPEX02CAS02.citrite.net (10.13.99.123) To AMSPEX02CL02.citrite.net (10.69.22.126) X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" ``` File "xenstored/disk.ml", line 33, characters 9-23: 33 | let c = Char.lowercase c in ^^^^^^^^^^^^^^ (alert deprecated): Stdlib.Char.lowercase Use Char.lowercase_ascii instead. ``` Signed-off-by: Edwin Török --- tools/ocaml/xenstored/disk.ml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tools/ocaml/xenstored/disk.ml b/tools/ocaml/xenstored/disk.ml index 4739967b61..1ca0e2a95e 100644 --- a/tools/ocaml/xenstored/disk.ml +++ b/tools/ocaml/xenstored/disk.ml @@ -30,7 +30,7 @@ let undec c = | _ -> raise (Failure "undecify") let unhex c = - let c = Char.lowercase c in + let c = Char.lowercase_ascii c in match c with | '0' .. '9' -> (Char.code c) - (Char.code '0') | 'a' .. 'f' -> (Char.code c) - (Char.code 'a') + 10 From patchwork Fri Aug 14 22:11:43 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 11715229 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2AB4E13B1 for ; Fri, 14 Aug 2020 22:14:34 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 052F420771 for ; Fri, 14 Aug 2020 22:14:34 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=citrix.com header.i=@citrix.com header.b="NIlWr4qe" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 052F420771 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwM-00089z-HR; Fri, 14 Aug 2020 22:12:46 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwL-000891-Qn for xen-devel@lists.xenproject.org; Fri, 14 Aug 2020 22:12:45 +0000 X-Inumbo-ID: 8f36f27c-12dd-423d-9c95-49a5bcecb5e8 Received: from esa1.hc3370-68.iphmx.com (unknown [216.71.145.142]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id 8f36f27c-12dd-423d-9c95-49a5bcecb5e8; Fri, 14 Aug 2020 22:12:38 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1597443159; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=r8ehkDegyME6bv9QcJZhEj/RknOtin3F+AcEEK7wbxw=; b=NIlWr4qe9rEqzHC7UVjwT3VC1M2tWsvLmrdLTgpN2Enth+4qOr3zWcuP oPFmjLg2dKcwDtoUlrFA1PMcrYjuBylIslAF3SCJkAud5FBg9yjLrP9vf 3gWPwOZ+do9Cx5xHMjdis0gfzzcRNJ4GCKJ470dVl6gxlB61bRY0lpKpM c=; Authentication-Results: esa1.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: 9+CkQgBCMCycE6HAp4+5UhYsxpOdTWeixjXQM9sbdbxbQxLbq7Oxq7PmKGefkOjlGo6c+EfuQK y4V6lhmYpnkxesi7c5a2PkBGW3J+4odhw+9qtlobNyWfAObHf/tihnZWZUeinD010Us7V2E/gv uMqb8CE3BaJU1k+JCwOBVk6U2HqCZjOdb80eBb54WQuHuCKOxBEPLW/SPEiihYvzDT/8JIsGFM lKPlyzno5FdO37pJhd9/1RlW2jUxPEQw1smaEFQRq0pSIUZVhjenfKX5yP5xzaCiPUi/e3t9Wc uzU= X-SBRS: 2.7 X-MesageID: 24917749 X-Ironport-Server: esa1.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.76,313,1592884800"; d="scan'208";a="24917749" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v1 3/6] tools/ocaml/xenstored: replace hand rolled GC with weak GC references Date: Fri, 14 Aug 2020 23:11:43 +0100 Message-ID: <163338eec9bc32a886e8def8f59224c902b1c07b.1597442238.git.edvin.torok@citrix.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: References: MIME-Version: 1.0 X-ClientProxiedBy: FTLPEX02CAS02.citrite.net (10.13.99.123) To AMSPEX02CL02.citrite.net (10.69.22.126) X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" The code here is attempting to reduce memory usage by sharing common substrings in the tree: it replaces strings with ints, and keeps a string->int map that gets manually garbage collected using a hand-rolled mark and sweep algorithm. This is unnecessary: OCaml already has a mark-and-sweep Garbage Collector runtime, and sharing of common strings in tree nodes can be achieved through Weak references: if the string hasn't been seen yet it gets added to the Weak reference table, and if it has we use the entry from the table instead, thus storing a string only once. When the string is no longer referenced OCaml's GC will drop it from the weak table: there is no need to manually do a mark-and-sweep, or to tell OCaml when to drop it. Signed-off-by: Edwin Török --- tools/ocaml/xenstored/connection.ml | 3 -- tools/ocaml/xenstored/history.ml | 14 ------ tools/ocaml/xenstored/store.ml | 11 ++--- tools/ocaml/xenstored/symbol.ml | 68 ++++++----------------------- tools/ocaml/xenstored/symbol.mli | 21 ++------- tools/ocaml/xenstored/xenstored.ml | 16 +------ 6 files changed, 24 insertions(+), 109 deletions(-) diff --git a/tools/ocaml/xenstored/connection.ml b/tools/ocaml/xenstored/connection.ml index 24750ada43..aa6dd95501 100644 --- a/tools/ocaml/xenstored/connection.ml +++ b/tools/ocaml/xenstored/connection.ml @@ -271,9 +271,6 @@ let has_more_work con = let incr_ops con = con.stat_nb_ops <- con.stat_nb_ops + 1 -let mark_symbols con = - Hashtbl.iter (fun _ t -> Store.mark_symbols (Transaction.get_store t)) con.transactions - let stats con = Hashtbl.length con.watches, con.stat_nb_ops diff --git a/tools/ocaml/xenstored/history.ml b/tools/ocaml/xenstored/history.ml index f39565bff5..029802bd15 100644 --- a/tools/ocaml/xenstored/history.ml +++ b/tools/ocaml/xenstored/history.ml @@ -22,20 +22,6 @@ type history_record = { let history : history_record list ref = ref [] -(* Called from periodic_ops to ensure we don't discard symbols that are still needed. *) -(* There is scope for optimisation here, since in consecutive commits one commit's `after` - * is the same thing as the next commit's `before`, but not all commits in history are - * consecutive. *) -let mark_symbols () = - (* There are gaps where dom0's commits are missing. Otherwise we could assume that - * each element's `before` is the same thing as the next element's `after` - * since the next element is the previous commit *) - List.iter (fun hist_rec -> - Store.mark_symbols hist_rec.before; - Store.mark_symbols hist_rec.after; - ) - !history - (* Keep only enough commit-history to protect the running transactions that we are still tracking *) (* There is scope for optimisation here, replacing List.filter with something more efficient, * probably on a different list-like structure. *) diff --git a/tools/ocaml/xenstored/store.ml b/tools/ocaml/xenstored/store.ml index f299ec6461..45659a23ee 100644 --- a/tools/ocaml/xenstored/store.ml +++ b/tools/ocaml/xenstored/store.ml @@ -46,18 +46,18 @@ let add_child node child = let exists node childname = let childname = Symbol.of_string childname in - List.exists (fun n -> n.name = childname) node.children + List.exists (fun n -> Symbol.equal n.name childname) node.children let find node childname = let childname = Symbol.of_string childname in - List.find (fun n -> n.name = childname) node.children + List.find (fun n -> Symbol.equal n.name childname) node.children let replace_child node child nchild = (* this is the on-steroid version of the filter one-replace one *) let rec replace_one_in_list l = match l with | [] -> [] - | h :: tl when h.name = child.name -> nchild :: tl + | h :: tl when Symbol.equal h.name child.name -> nchild :: tl | h :: tl -> h :: replace_one_in_list tl in { node with children = (replace_one_in_list node.children) } @@ -67,7 +67,7 @@ let del_childname node childname = let rec delete_one_in_list l = match l with | [] -> raise Not_found - | h :: tl when h.name = sym -> tl + | h :: tl when Symbol.equal h.name sym -> tl | h :: tl -> h :: delete_one_in_list tl in { node with children = (delete_one_in_list node.children) } @@ -463,9 +463,6 @@ let copy store = { quota = Quota.copy store.quota; } -let mark_symbols store = - Node.recurse (fun node -> Symbol.mark_as_used node.Node.name) store.root - let incr_transaction_coalesce store = store.stat_transaction_coalesce <- store.stat_transaction_coalesce + 1 let incr_transaction_abort store = diff --git a/tools/ocaml/xenstored/symbol.ml b/tools/ocaml/xenstored/symbol.ml index 4420c6a4d7..dac6f9f819 100644 --- a/tools/ocaml/xenstored/symbol.ml +++ b/tools/ocaml/xenstored/symbol.ml @@ -14,63 +14,23 @@ * GNU Lesser General Public License for more details. *) -type t = int +module WeakTable = Weak.Make(struct + type t = string + let equal = String.equal + let hash = Hashtbl.hash +end) -type 'a record = { data: 'a; mutable garbage: bool } -let int_string_tbl : (int,string record) Hashtbl.t = Hashtbl.create 1024 -let string_int_tbl : (string,int) Hashtbl.t = Hashtbl.create 1024 +type t = string -let created_counter = ref 0 -let used_counter = ref 0 +let tbl = WeakTable.create 1024 -let count = ref 0 -let rec fresh () = - if Hashtbl.mem int_string_tbl !count - then begin - incr count; - fresh () - end else - !count +let of_string s = WeakTable.merge tbl s +let to_string s = s -let new_record v = { data=v; garbage=false } - -let of_string name = - if Hashtbl.mem string_int_tbl name - then begin - incr used_counter; - Hashtbl.find string_int_tbl name - end else begin - let i = fresh () in - incr created_counter; - Hashtbl.add string_int_tbl name i; - Hashtbl.add int_string_tbl i (new_record name); - i - end - -let to_string i = - (Hashtbl.find int_string_tbl i).data - -let mark_all_as_unused () = - Hashtbl.iter (fun _ v -> v.garbage <- true) int_string_tbl - -let mark_as_used symb = - let record1 = Hashtbl.find int_string_tbl symb in - record1.garbage <- false - -let garbage () = - let records = Hashtbl.fold (fun symb record accu -> - if record.garbage then (symb, record.data) :: accu else accu - ) int_string_tbl [] in - let remove (int,string) = - Hashtbl.remove int_string_tbl int; - Hashtbl.remove string_int_tbl string - in - created_counter := 0; - used_counter := 0; - List.iter remove records +let equal a b = + (* compare using physical equality, both members have to be part of the above weak table *) + a == b let stats () = - Hashtbl.length string_int_tbl - -let created () = !created_counter -let used () = !used_counter + let len, entries, _, _, _, _ = WeakTable.stats tbl in + len, entries diff --git a/tools/ocaml/xenstored/symbol.mli b/tools/ocaml/xenstored/symbol.mli index c3c9f6e2f8..586ab57507 100644 --- a/tools/ocaml/xenstored/symbol.mli +++ b/tools/ocaml/xenstored/symbol.mli @@ -29,24 +29,11 @@ val of_string : string -> t val to_string : t -> string (** Convert a symbol into a string. *) -(** {6 Garbage Collection} *) - -(** Symbols need to be regulary garbage collected. The following steps should be followed: -- mark all the knowns symbols as unused (with [mark_all_as_unused]); -- mark all the symbols really usefull as used (with [mark_as_used]); and -- finally, call [garbage] *) - -val mark_all_as_unused : unit -> unit -val mark_as_used : t -> unit -val garbage : unit -> unit +val equal: t -> t -> bool +(** Compare two symbols for equality *) (** {6 Statistics } *) -val stats : unit -> int -(** Get the number of used symbols. *) +val stats : unit -> int * int +(** Get the table size and number of entries. *) -val created : unit -> int -(** Returns the number of symbols created since the last GC. *) - -val used : unit -> int -(** Returns the number of existing symbols used since the last GC *) diff --git a/tools/ocaml/xenstored/xenstored.ml b/tools/ocaml/xenstored/xenstored.ml index a4466c5b5c..047e093555 100644 --- a/tools/ocaml/xenstored/xenstored.ml +++ b/tools/ocaml/xenstored/xenstored.ml @@ -378,18 +378,6 @@ let _ = let periodic_ops now = debug "periodic_ops starting"; - (* we garbage collect the string->int dictionary after a sizeable amount of operations, - * there's no need to be really fast even if we got loose - * objects since names are often reuse. - *) - if Symbol.created () > 1000 || Symbol.used () > 20000 - then begin - Symbol.mark_all_as_unused (); - Store.mark_symbols store; - Connections.iter cons Connection.mark_symbols; - History.mark_symbols (); - Symbol.garbage () - end; (* scan all the xs rings as a safenet for ill-behaved clients *) if !ring_scan_interval >= 0 && now > (!last_scan_time +. float !ring_scan_interval) then @@ -407,11 +395,11 @@ let _ = let (lanon, lanon_ops, lanon_watchs, ldom, ldom_ops, ldom_watchs) = Connections.stats cons in let store_nodes, store_abort, store_coalesce = Store.stats store in - let symtbl_len = Symbol.stats () in + let symtbl_len, symtbl_entries = Symbol.stats () in info "store stat: nodes(%d) t-abort(%d) t-coalesce(%d)" store_nodes store_abort store_coalesce; - info "sytbl stat: %d" symtbl_len; + info "sytbl stat: length(%d) entries(%d)" symtbl_len symtbl_entries; info " con stat: anonymous(%d, %d o, %d w) domains(%d, %d o, %d w)" lanon lanon_ops lanon_watchs ldom ldom_ops ldom_watchs; info " mem stat: minor(%.0f) promoted(%.0f) major(%.0f) heap(%d w, %d c) live(%d w, %d b) free(%d w, %d b)" From patchwork Fri Aug 14 22:11:44 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 11715219 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 5FE32109B for ; Fri, 14 Aug 2020 22:13:14 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 2E72520768 for ; Fri, 14 Aug 2020 22:13:14 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=citrix.com header.i=@citrix.com header.b="JACD4tcg" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 2E72520768 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwS-0008CG-0S; Fri, 14 Aug 2020 22:12:52 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hwQ-000891-Qq for xen-devel@lists.xenproject.org; Fri, 14 Aug 2020 22:12:50 +0000 X-Inumbo-ID: 120bce8d-035b-43fc-b322-00fe05df8f38 Received: from esa2.hc3370-68.iphmx.com (unknown [216.71.145.153]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id 120bce8d-035b-43fc-b322-00fe05df8f38; Fri, 14 Aug 2020 22:12:41 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1597443162; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=gS1TrvmCnqSK0AHt92/O0DkyvU/FsC2Pi/fd9rcw+pU=; b=JACD4tcgRPoMZoKQknaOVEJ32qOFy/e5krF2WyddHiwmv+iDg0YfzC2E WK6s00nBViWFYBIa8Runwu207xXE+/7xt+mwWvr294BUzmPCk5RhmHkVJ QZvC2pX7GPIpRnxkmsQ5dcpi2YT4mlQWbZfl9MxS+FV+uJE9gbXHKmXPY U=; Authentication-Results: esa2.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: WRaiui+ufzcDYWZ2PrPCwz7mKR+OKb10oYnx5L0F+N4H6Hv/7xG20Q3vEqE7b+v18XN0zNMZYa a3xYsunPFbgy682QLt+71IzPdbaZW4oSjAiTwN1rjFpyKBMeWOHSTI4jajXfdNSSfVhum7jiFP HprgPigmejnX35lh3BQTB8r2A4+Y4MIN6mg81tic8ThlFblsO6aNdY2g2E0xMkuMtNWNp+J9T4 QNRiQXUGM0d8FT5+UGiBxqSDpCPcqxz84GXoPNqmzwOF97feD+7BjHOLdyM9E4uI9POG4F61+g 9DI= X-SBRS: 2.7 X-MesageID: 24594732 X-Ironport-Server: esa2.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.76,313,1592884800"; d="scan'208";a="24594732" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v1 4/6] tools/ocaml/xenstored: drop select based Date: Fri, 14 Aug 2020 23:11:44 +0100 Message-ID: <1e3b3f1ecb3b0c44a23f8ec5fe0af4b2249c1c7e.1597442238.git.edvin.torok@citrix.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: References: MIME-Version: 1.0 X-ClientProxiedBy: FTLPEX02CAS02.citrite.net (10.13.99.123) To AMSPEX02CL02.citrite.net (10.69.22.126) X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" Poll has been the default since 2014, I think we can safely say by now that poll() works and we don't need to fall back to select(). This will allow fixing up the way we call poll to be more efficient (and pave the way for introducing epoll support): currently poll wraps the select API, which is inefficient. Signed-off-by: Edwin Török --- tools/ocaml/xenstored/Makefile | 12 ++++++------ tools/ocaml/xenstored/parse_arg.ml | 7 ++----- tools/ocaml/xenstored/{select.ml => poll.ml} | 14 ++------------ tools/ocaml/xenstored/{select.mli => poll.mli} | 12 ++---------- tools/ocaml/xenstored/xenstored.ml | 4 +--- 5 files changed, 13 insertions(+), 36 deletions(-) rename tools/ocaml/xenstored/{select.ml => poll.ml} (85%) rename tools/ocaml/xenstored/{select.mli => poll.mli} (58%) diff --git a/tools/ocaml/xenstored/Makefile b/tools/ocaml/xenstored/Makefile index 68d35c483a..692a62584e 100644 --- a/tools/ocaml/xenstored/Makefile +++ b/tools/ocaml/xenstored/Makefile @@ -18,12 +18,12 @@ OCAMLINCLUDE += \ -I $(OCAML_TOPLEVEL)/libs/xc \ -I $(OCAML_TOPLEVEL)/libs/eventchn -LIBS = syslog.cma syslog.cmxa select.cma select.cmxa +LIBS = syslog.cma syslog.cmxa poll.cma poll.cmxa syslog_OBJS = syslog syslog_C_OBJS = syslog_stubs -select_OBJS = select -select_C_OBJS = select_stubs -OCAML_LIBRARY = syslog select +poll_OBJS = poll +poll_C_OBJS = select_stubs +OCAML_LIBRARY = syslog poll LIBS += systemd.cma systemd.cmxa systemd_OBJS = systemd @@ -58,13 +58,13 @@ OBJS = paths \ process \ xenstored -INTF = symbol.cmi trie.cmi syslog.cmi systemd.cmi select.cmi +INTF = symbol.cmi trie.cmi syslog.cmi systemd.cmi poll.cmi XENSTOREDLIBS = \ unix.cmxa \ -ccopt -L -ccopt . syslog.cmxa \ -ccopt -L -ccopt . systemd.cmxa \ - -ccopt -L -ccopt . select.cmxa \ + -ccopt -L -ccopt . poll.cmxa \ -ccopt -L -ccopt $(OCAML_TOPLEVEL)/libs/mmap $(OCAML_TOPLEVEL)/libs/mmap/xenmmap.cmxa \ -ccopt -L -ccopt $(OCAML_TOPLEVEL)/libs/eventchn $(OCAML_TOPLEVEL)/libs/eventchn/xeneventchn.cmxa \ -ccopt -L -ccopt $(OCAML_TOPLEVEL)/libs/xc $(OCAML_TOPLEVEL)/libs/xc/xenctrl.cmxa \ diff --git a/tools/ocaml/xenstored/parse_arg.ml b/tools/ocaml/xenstored/parse_arg.ml index 1803c3eda0..2c4b5a8528 100644 --- a/tools/ocaml/xenstored/parse_arg.ml +++ b/tools/ocaml/xenstored/parse_arg.ml @@ -25,7 +25,6 @@ type config = tracefile: string option; (* old xenstored compatibility *) restart: bool; disable_socket: bool; - use_select: bool; } let do_argv = @@ -37,7 +36,7 @@ let do_argv = and config_file = ref "" and restart = ref false and disable_socket = ref false - and use_select = ref false in + in let speclist = [ ("--no-domain-init", Arg.Unit (fun () -> domain_init := false), @@ -54,9 +53,8 @@ let do_argv = ("-T", Arg.Set_string tracefile, ""); (* for compatibility *) ("--restart", Arg.Set restart, "Read database on starting"); ("--disable-socket", Arg.Unit (fun () -> disable_socket := true), "Disable socket"); - ("--use-select", Arg.Unit (fun () -> use_select := true), "Use select instead of poll"); (* for backward compatibility and testing *) ] in - let usage_msg = "usage : xenstored [--config-file ] [--no-domain-init] [--help] [--no-fork] [--reraise-top-level] [--restart] [--disable-socket] [--use-select]" in + let usage_msg = "usage : xenstored [--config-file ] [--no-domain-init] [--help] [--no-fork] [--reraise-top-level] [--restart] [--disable-socket]" in Arg.parse speclist (fun _ -> ()) usage_msg; { domain_init = !domain_init; @@ -68,5 +66,4 @@ let do_argv = tracefile = if !tracefile <> "" then Some !tracefile else None; restart = !restart; disable_socket = !disable_socket; - use_select = !use_select; } diff --git a/tools/ocaml/xenstored/select.ml b/tools/ocaml/xenstored/poll.ml similarity index 85% rename from tools/ocaml/xenstored/select.ml rename to tools/ocaml/xenstored/poll.ml index 0455e163e3..26f8620dfc 100644 --- a/tools/ocaml/xenstored/select.ml +++ b/tools/ocaml/xenstored/poll.ml @@ -63,15 +63,5 @@ let poll_select in_fds out_fds exc_fds timeout = (if event.except then fd :: x else x)) a r -(* If the use_poll function is not called at all, we default to the original Unix.select behavior *) -let select_fun = ref Unix.select - -let use_poll yes = - let sel_fun, max_fd = - if yes then poll_select, get_sys_fs_nr_open () - else Unix.select, 1024 in - select_fun := sel_fun; - set_fd_limit max_fd - -let select in_fds out_fds exc_fds timeout = - (!select_fun) in_fds out_fds exc_fds timeout +let () = + set_fd_limit (get_sys_fs_nr_open ()) diff --git a/tools/ocaml/xenstored/select.mli b/tools/ocaml/xenstored/poll.mli similarity index 58% rename from tools/ocaml/xenstored/select.mli rename to tools/ocaml/xenstored/poll.mli index 3912779172..f73465b99f 100644 --- a/tools/ocaml/xenstored/select.mli +++ b/tools/ocaml/xenstored/poll.mli @@ -13,15 +13,7 @@ *) -(** Same interface and semantics as [Unix.select] but with an extra alternative - implementation based on poll. Switching implementations is done by calling - the [use_poll] function. *) -val select: +(** Same interface and semantics as [Unix.select], implemented using poll(3). *) +val poll_select: Unix.file_descr list -> Unix.file_descr list -> Unix.file_descr list -> float -> Unix.file_descr list * Unix.file_descr list * Unix.file_descr list - -(** [use_poll true] will use poll based select with max fds number limitation - eliminated; [use_poll false] will use standard [Unix.select] with max fd - number set to 1024; not calling this function at all equals to use the - standard [Unix.select] with max fd number setting untouched. *) -val use_poll: bool -> unit diff --git a/tools/ocaml/xenstored/xenstored.ml b/tools/ocaml/xenstored/xenstored.ml index 047e093555..f3e4697dea 100644 --- a/tools/ocaml/xenstored/xenstored.ml +++ b/tools/ocaml/xenstored/xenstored.ml @@ -308,8 +308,6 @@ let _ = ); ); - Select.use_poll (not cf.use_select); - Sys.set_signal Sys.sighup (Sys.Signal_handle sighup_handler); Sys.set_signal Sys.sigterm (Sys.Signal_handle (fun _ -> quit := true)); Sys.set_signal Sys.sigusr1 (Sys.Signal_handle (fun _ -> sigusr1_handler store)); @@ -441,7 +439,7 @@ let _ = let inset, outset = Connections.select ~only_if:is_peaceful cons in let rset, wset, _ = try - Select.select (spec_fds @ inset) outset [] timeout + Poll.poll_select (spec_fds @ inset) outset [] timeout with Unix.Unix_error(Unix.EINTR, _, _) -> [], [], [] in let sfds, cfds = From patchwork Fri Aug 14 22:14:16 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 11715231 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 77988109B for ; Fri, 14 Aug 2020 22:15:32 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 51BEC2074D for ; Fri, 14 Aug 2020 22:15:32 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=citrix.com header.i=@citrix.com header.b="Ubu10ISK" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 51BEC2074D Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hyF-00009R-DI; Fri, 14 Aug 2020 22:14:43 +0000 Received: from all-amaz-eas1.inumbo.com ([34.197.232.57] helo=us1-amaz-eas2.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hyD-00007n-P3 for xen-devel@lists.xenproject.org; Fri, 14 Aug 2020 22:14:41 +0000 X-Inumbo-ID: 6909c582-9f4e-44d7-bc8b-509c7e7097c7 Received: from esa1.hc3370-68.iphmx.com (unknown [216.71.145.142]) by us1-amaz-eas2.inumbo.com (Halon) with ESMTPS id 6909c582-9f4e-44d7-bc8b-509c7e7097c7; Fri, 14 Aug 2020 22:14:38 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1597443279; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=0Q7mZezmkZDXxgdfVrSnPIVAXJc1OwrHZVcWnmgusxs=; b=Ubu10ISKPvXSxvDbqWooK3wDw9jmlzJkNWwyHPHkDSF9b1vesulhAHIy wYR9ju6rcm8XR0PZ905IEmQ+lmQNHwR1kB/vxYlymFc9CuRVUxzFZ1Xu0 8X1BXjvgec00cVC3VLOirYDV9v56btTD4jS8CLd4cpMvPJp1tjqJVYeak 8=; Authentication-Results: esa1.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: 1LBNtNrPDNlAwaIFp3ww/RJ8dePjBdmQ0essod3qtkvnJPnEVBiqMl1hKXPllR4ZYmiy1lI3F/ Eqplq86CoKTMeW25/bjvz5DHqLiHCmGaUnEM9peONsiFysBH6acXcGbUqbawUMP8PHHXu6tZIp 3WXil2ha5g3nBxtKCRSVsnj8K49F584Wkvt8zqPAe47A9Pn9aBIsgidXVULJre/zoKxoM1staa Vy0LFVOdm79M53gol2JlGpkLmyIh8J9/F4UZb+FSbEY9drbncn5bn3F1Oo/8IixIaOIyil3hjk EoY= X-SBRS: 2.7 X-MesageID: 24917872 X-Ironport-Server: esa1.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.76,313,1592884800"; d="scan'208";a="24917872" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v1 5/6] tools/ocaml/xenstored: use more efficient node trees Date: Fri, 14 Aug 2020 23:14:16 +0100 Message-ID: X-Mailer: git-send-email 2.25.1 In-Reply-To: References: MIME-Version: 1.0 X-ClientProxiedBy: FTLPEX02CAS01.citrite.net (10.13.99.120) To AMSPEX02CL02.citrite.net (10.69.22.126) X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" This changes the output of xenstore-ls to be sorted. Previously the keys were listed in the order in which they were inserted in. docs/misc/xenstore.txt doesn't specify in what order keys are listed. Map.update is used to retain semantics with replace_child: only an existing child is replaced, if it wasn't part of the original map we don't add it. Similarly exception behaviour is retained for del_childname and related functions. Entries are stored in reverse sort order, so that upon Map.fold the constructed list is sorted in ascending order and there is no need for a List.rev. Signed-off-by: Edwin Török --- tools/ocaml/xenstored/store.ml | 46 +++++++++++++++----------------- tools/ocaml/xenstored/symbol.ml | 4 +++ tools/ocaml/xenstored/symbol.mli | 3 +++ 3 files changed, 29 insertions(+), 24 deletions(-) diff --git a/tools/ocaml/xenstored/store.ml b/tools/ocaml/xenstored/store.ml index 45659a23ee..d9dfa36045 100644 --- a/tools/ocaml/xenstored/store.ml +++ b/tools/ocaml/xenstored/store.ml @@ -16,17 +16,19 @@ *) open Stdext +module SymbolMap = Map.Make(Symbol) + module Node = struct type t = { name: Symbol.t; perms: Perms.Node.t; value: string; - children: t list; + children: t SymbolMap.t; } let create _name _perms _value = - { name = Symbol.of_string _name; perms = _perms; value = _value; children = []; } + { name = Symbol.of_string _name; perms = _perms; value = _value; children = SymbolMap.empty; } let get_owner node = Perms.Node.get_owner node.perms let get_children node = node.children @@ -42,38 +44,34 @@ let set_value node nvalue = let set_perms node nperms = { node with perms = nperms } let add_child node child = - { node with children = child :: node.children } + let children = SymbolMap.add child.name child node.children in + { node with children } let exists node childname = let childname = Symbol.of_string childname in - List.exists (fun n -> Symbol.equal n.name childname) node.children + SymbolMap.mem childname node.children let find node childname = let childname = Symbol.of_string childname in - List.find (fun n -> Symbol.equal n.name childname) node.children + SymbolMap.find childname node.children let replace_child node child nchild = - (* this is the on-steroid version of the filter one-replace one *) - let rec replace_one_in_list l = - match l with - | [] -> [] - | h :: tl when Symbol.equal h.name child.name -> nchild :: tl - | h :: tl -> h :: replace_one_in_list tl - in - { node with children = (replace_one_in_list node.children) } + { node with + children = SymbolMap.update child.name + (function None -> None | Some _ -> Some nchild) + node.children + } let del_childname node childname = let sym = Symbol.of_string childname in - let rec delete_one_in_list l = - match l with - | [] -> raise Not_found - | h :: tl when Symbol.equal h.name sym -> tl - | h :: tl -> h :: delete_one_in_list tl - in - { node with children = (delete_one_in_list node.children) } + { node with children = + SymbolMap.update sym + (function None -> raise Not_found | Some _ -> None) + node.children + } let del_all_children node = - { node with children = [] } + { node with children = SymbolMap.empty } (* check if the current node can be accessed by the current connection with rperm permissions *) let check_perm node connection request = @@ -87,7 +85,7 @@ let check_owner node connection = raise Define.Permission_denied; end -let rec recurse fct node = fct node; List.iter (recurse fct) node.children +let rec recurse fct node = fct node; SymbolMap.iter (fun _ -> recurse fct) node.children let unpack node = (Symbol.to_string node.name, node.perms, node.value) @@ -321,7 +319,7 @@ let ls store perm path = Node.check_perm cnode perm Perms.READ; cnode.Node.children in Path.apply store.root path do_ls in - List.rev (List.map (fun n -> Symbol.to_string n.Node.name) children) + SymbolMap.fold (fun k _ accu -> Symbol.to_string k :: accu) children [] let getperms store perm path = if path = [] then @@ -350,7 +348,7 @@ let traversal root_node f = let rec _traversal path node = f path node; let node_path = Path.of_path_and_name path (Symbol.to_string node.Node.name) in - List.iter (_traversal node_path) node.Node.children + SymbolMap.iter (fun _ -> _traversal node_path) node.Node.children in _traversal [] root_node diff --git a/tools/ocaml/xenstored/symbol.ml b/tools/ocaml/xenstored/symbol.ml index dac6f9f819..2697915623 100644 --- a/tools/ocaml/xenstored/symbol.ml +++ b/tools/ocaml/xenstored/symbol.ml @@ -31,6 +31,10 @@ let equal a b = (* compare using physical equality, both members have to be part of the above weak table *) a == b +let compare a b = + if equal a b then 0 + else -(String.compare a b) + let stats () = let len, entries, _, _, _, _ = WeakTable.stats tbl in len, entries diff --git a/tools/ocaml/xenstored/symbol.mli b/tools/ocaml/xenstored/symbol.mli index 586ab57507..dd0f014796 100644 --- a/tools/ocaml/xenstored/symbol.mli +++ b/tools/ocaml/xenstored/symbol.mli @@ -32,6 +32,9 @@ val to_string : t -> string val equal: t -> t -> bool (** Compare two symbols for equality *) +val compare: t -> t -> int +(** Compare two symbols *) + (** {6 Statistics } *) val stats : unit -> int * int From patchwork Fri Aug 14 22:14:17 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 11715233 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id DF126618 for ; Fri, 14 Aug 2020 22:15:47 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id BA8892074D for ; Fri, 14 Aug 2020 22:15:47 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=citrix.com header.i=@citrix.com header.b="JJ/bjhqZ" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org BA8892074D Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hyJ-0000Af-OH; Fri, 14 Aug 2020 22:14:47 +0000 Received: from all-amaz-eas1.inumbo.com ([34.197.232.57] helo=us1-amaz-eas2.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1k6hyI-00007n-P2 for xen-devel@lists.xenproject.org; Fri, 14 Aug 2020 22:14:46 +0000 X-Inumbo-ID: f2dcc7ba-d036-4764-9056-17974c1d5988 Received: from esa2.hc3370-68.iphmx.com (unknown [216.71.145.153]) by us1-amaz-eas2.inumbo.com (Halon) with ESMTPS id f2dcc7ba-d036-4764-9056-17974c1d5988; Fri, 14 Aug 2020 22:14:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1597443280; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=if7OGWtVmhZh72IibrAy1nlT/ZT6plG+SikdsKX2czc=; b=JJ/bjhqZ5QwEu1kcgiUXc+mVKYBIvn/eg0PflKh/8pVrpG/wyvMDCUrb c9oOxANJ60xWuKPbaDwabuLOoIaHbcW+hfMwFdgoZcuX/z6EeWV8IKzso +5MTaHDKFK7PPh/STtYwyspXOwphdhuz+SRRNpbTBxpyAZ/UW3peQGaj1 0=; Authentication-Results: esa2.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: RP0nrB09qZOcsD1mSyafDyVlsizLVkFU4vgSZ9Lyr+IityS70NXuNoiZ1WfjjYwsO0ZqA2cODT HqwV8G4eRG+NsqjFM7M5D7ZALPwLIYtmkOMM3wud0qjAFk20rv28hIMTEo4fdqtAsp6iqEkNnL TAo75Gr1RSxOPPxBskvNOrz7HWoilS+//sNUVfqpPyr2qnVL+s52SSVmKNhD0GPU8KdHNFutRJ yH870z85/1YPlWoePTAqigPsk2gHbZezBuSNjSDMogPke4q10btLjiADD01MXfUyH42C2efK0l AZA= X-SBRS: 2.7 X-MesageID: 24594802 X-Ironport-Server: esa2.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.76,313,1592884800"; d="scan'208";a="24594802" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v1 6/6] tools/ocaml/xenstored: use more efficient tries Date: Fri, 14 Aug 2020 23:14:17 +0100 Message-ID: <9bb3bfc05610728017dbd6321470b5413302d717.1597442238.git.edvin.torok@citrix.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: References: MIME-Version: 1.0 X-ClientProxiedBy: FTLPEX02CAS01.citrite.net (10.13.99.120) To AMSPEX02CL02.citrite.net (10.69.22.126) X-BeenThere: xen-devel@lists.xenproject.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Sender: "Xen-devel" No functional change, just an optimization. Signed-off-by: Edwin Török --- tools/ocaml/xenstored/connections.ml | 2 +- tools/ocaml/xenstored/trie.ml | 61 ++++++++++++---------------- tools/ocaml/xenstored/trie.mli | 26 ++++++------ 3 files changed, 41 insertions(+), 48 deletions(-) diff --git a/tools/ocaml/xenstored/connections.ml b/tools/ocaml/xenstored/connections.ml index f02ef6b526..4983c7370b 100644 --- a/tools/ocaml/xenstored/connections.ml +++ b/tools/ocaml/xenstored/connections.ml @@ -21,7 +21,7 @@ type t = { anonymous: (Unix.file_descr, Connection.t) Hashtbl.t; domains: (int, Connection.t) Hashtbl.t; ports: (Xeneventchn.t, Connection.t) Hashtbl.t; - mutable watches: (string, Connection.watch list) Trie.t; + mutable watches: Connection.watch list Trie.t; } let create () = { diff --git a/tools/ocaml/xenstored/trie.ml b/tools/ocaml/xenstored/trie.ml index dc42535092..f4ef97742f 100644 --- a/tools/ocaml/xenstored/trie.ml +++ b/tools/ocaml/xenstored/trie.ml @@ -13,24 +13,26 @@ * GNU Lesser General Public License for more details. *) +module StringMap = Map.Make(String) + module Node = struct - type ('a,'b) t = { - key: 'a; - value: 'b option; - children: ('a,'b) t list; + type 'a t = { + key: string; + value: 'a option; + children: 'a t StringMap.t; } let _create key value = { key = key; value = Some value; - children = []; + children = StringMap.empty; } let empty key = { key = key; value = None; - children = [] + children = StringMap.empty; } let _get_key node = node.key @@ -47,41 +49,31 @@ struct { node with children = children } let _add_child node child = - { node with children = child :: node.children } + { node with children = StringMap.add child.key child node.children } end -type ('a,'b) t = ('a,'b) Node.t list +type 'a t = 'a Node.t StringMap.t let mem_node nodes key = - List.exists (fun n -> n.Node.key = key) nodes + StringMap.mem key nodes let find_node nodes key = - List.find (fun n -> n.Node.key = key) nodes + StringMap.find key nodes let replace_node nodes key node = - let rec aux = function - | [] -> [] - | h :: tl when h.Node.key = key -> node :: tl - | h :: tl -> h :: aux tl - in - aux nodes + StringMap.update key (function None -> None | Some _ -> Some node) nodes let remove_node nodes key = - let rec aux = function - | [] -> raise Not_found - | h :: tl when h.Node.key = key -> tl - | h :: tl -> h :: aux tl - in - aux nodes + StringMap.update key (function None -> raise Not_found | Some _ -> None) nodes -let create () = [] +let create () = StringMap.empty let rec iter f tree = - let aux node = - f node.Node.key node.Node.value; + let aux key node = + f key node.Node.value; iter f node.Node.children in - List.iter aux tree + StringMap.iter aux tree let rec map f tree = let aux node = @@ -92,13 +84,14 @@ let rec map f tree = in { node with Node.value = value; Node.children = map f node.Node.children } in - List.filter (fun n -> n.Node.value <> None || n.Node.children <> []) (List.map aux tree) + tree |> StringMap.map aux + |> StringMap.filter (fun _ n -> n.Node.value <> None || not (StringMap.is_empty n.Node.children) ) let rec fold f tree acc = - let aux accu node = - fold f node.Node.children (f node.Node.key node.Node.value accu) + let aux key node accu = + fold f node.Node.children (f key node.Node.value accu) in - List.fold_left aux acc tree + StringMap.fold aux tree acc (* return a sub-trie *) let rec sub_node tree = function @@ -115,7 +108,7 @@ let rec sub_node tree = function let sub tree path = try (sub_node tree path).Node.children - with Not_found -> [] + with Not_found -> StringMap.empty let find tree path = Node.get_value (sub_node tree path) @@ -158,8 +151,8 @@ and set tree path value = let node = find_node tree h in replace_node tree h (set_node node t value) end else begin - let node = Node.empty h in - set_node node t value :: tree + let node = Node._create h value in + StringMap.add node.Node.key node tree end let rec unset tree = function @@ -174,7 +167,7 @@ let rec unset tree = function then Node.set_children (Node.empty h) children else Node.set_children node children in - if children = [] && new_node.Node.value = None + if StringMap.is_empty children && new_node.Node.value = None then remove_node tree h else replace_node tree h new_node end else diff --git a/tools/ocaml/xenstored/trie.mli b/tools/ocaml/xenstored/trie.mli index 5dc53c1cb1..27785154f5 100644 --- a/tools/ocaml/xenstored/trie.mli +++ b/tools/ocaml/xenstored/trie.mli @@ -15,46 +15,46 @@ (** Basic Implementation of polymorphic tries (ie. prefix trees) *) -type ('a, 'b) t -(** The type of tries. ['a list] is the type of keys, ['b] the type of values. +type 'a t +(** The type of tries. ['a] the type of values. Internally, a trie is represented as a labeled tree, where node contains values - of type ['a * 'b option]. *) + of type [string * 'a option]. *) -val create : unit -> ('a,'b) t +val create : unit -> 'a t (** Creates an empty trie. *) -val mem : ('a,'b) t -> 'a list -> bool +val mem : 'a t -> string list -> bool (** [mem t k] returns true if a value is associated with the key [k] in the trie [t]. Otherwise, it returns false. *) -val find : ('a, 'b) t -> 'a list -> 'b +val find : 'a t -> string list -> 'a (** [find t k] returns the value associated with the key [k] in the trie [t]. Returns [Not_found] if no values are associated with [k] in [t]. *) -val set : ('a, 'b) t -> 'a list -> 'b -> ('a, 'b) t +val set : 'a t -> string list -> 'a -> 'a t (** [set t k v] associates the value [v] with the key [k] in the trie [t]. *) -val unset : ('a, 'b) t -> 'a list -> ('a, 'b) t +val unset : 'a t -> string list -> 'a t (** [unset k v] removes the association of value [v] with the key [k] in the trie [t]. Moreover, it automatically clean the trie, ie. it removes recursively every nodes of [t] containing no values and having no chil. *) -val iter : ('a -> 'b option -> unit) -> ('a, 'b) t -> unit +val iter : (string -> 'a option -> unit) -> 'a t -> unit (** [iter f t] applies the function [f] to every node of the trie [t]. As nodes of the trie [t] do not necessary contains a value, the second argument of [f] is an option type. *) -val iter_path : ('a -> 'b option -> unit) -> ('a, 'b) t -> 'a list -> unit +val iter_path : (string -> 'a option -> unit) -> 'a t -> string list -> unit (** [iter_path f t p] iterates [f] over nodes associated with the path [p] in the trie [t]. If [p] is not a valid path of [t], it iterates on the longest valid prefix of [p]. *) -val fold : ('a -> 'b option -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c +val fold : (string -> 'a option -> 'c -> 'c) -> 'a t -> 'c -> 'c (** [fold f t x] fold [f] over every nodes of [t], with [x] as initial value. *) -val map : ('b -> 'c option) -> ('a,'b) t -> ('a,'c) t +val map : ('a -> 'b option) -> 'a t -> 'b t (** [map f t] maps [f] over every values stored in [t]. The return value of [f] is of type 'c option as one may wants to remove value associated to a key. This function is not tail-recursive. *) -val sub : ('a, 'b) t -> 'a list -> ('a,'b) t +val sub : 'a t -> string list -> 'a t (** [sub t p] returns the sub-trie associated with the path [p] in the trie [t]. If [p] is not a valid path of [t], it returns an empty trie. *)