From patchwork Wed Jan 31 10:52:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Edwin Torok X-Patchwork-Id: 13539165 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 13D64C47DDF for ; Wed, 31 Jan 2024 10:53:19 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.673901.1048460 (Exim 4.92) (envelope-from ) id 1rV8DL-0005aC-UV; Wed, 31 Jan 2024 10:53:07 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 673901.1048460; Wed, 31 Jan 2024 10:53:07 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1rV8DL-0005a5-Ph; Wed, 31 Jan 2024 10:53:07 +0000 Received: by outflank-mailman (input) for mailman id 673901; Wed, 31 Jan 2024 10:53:06 +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 1rV8DK-0005ZD-0X for xen-devel@lists.xenproject.org; Wed, 31 Jan 2024 10:53:06 +0000 Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [2a00:1450:4864:20::42f]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id e7d22e4e-c026-11ee-98f5-efadbce2ee36; Wed, 31 Jan 2024 11:53:02 +0100 (CET) Received: by mail-wr1-x42f.google.com with SMTP id ffacd0b85a97d-33ae3cc8a6aso2914616f8f.2 for ; Wed, 31 Jan 2024 02:53:02 -0800 (PST) Received: from fedora39.edvint-x-u ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id o1-20020a5d4081000000b0033ae50e2c6asm10585757wrp.83.2024.01.31.02.53.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 31 Jan 2024 02:53:01 -0800 (PST) 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: e7d22e4e-c026-11ee-98f5-efadbce2ee36 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloud.com; s=cloud; t=1706698381; x=1707303181; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Sa9A5+QxE9tVCCZct9IISsR+fFT6zN3g0plaGL+J3O8=; b=OMcTVKm0LZorrgC2o8RBZfd2GFfPGjVE+7YKvqAif0jRnaA2JdsIM8sMTOqFRMfiDQ 70sZQQdcLeOJa8bW8wUQK3x2Pt+56Oa3QeytVTrIH1x57T5UbBiAEWi7n+S4wi6ZEj1/ ySgcOzyToAcxLT+9b2uzMIVO6TDWmXuAfJwUA= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1706698381; x=1707303181; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Sa9A5+QxE9tVCCZct9IISsR+fFT6zN3g0plaGL+J3O8=; b=dcUt1vQ73H7FGd+nz93zMAJEy10vnxbweiDUzD7aki2UPbVnu+/qLi0y/pR69+GKWS rfJTync64vzDZXwwH+XW0b0w0TQs2REiuana3Bd92IAVHTHLeTV7VtMwURovKKSvOxXz UyUpUOEkEIQNAt7XbQANY8SjexaJgR5EHph0+8wGCfG3tbAiR+tPqdUVfnMUYWGUVs0X TN00d9aw6I9bkK6R4mzrZ+9wiCfZLiUPaEPPP6+v+rVYYvFXHjnlxGkv0I+bm1qF11/c SNrNojlytFYjeezIbddKHUPkP7EFeE9YMwduUyak6JLUUR32Q1qgqZ4Jt7Ynm5/YhdXS I1fQ== X-Gm-Message-State: AOJu0Yx6cl1bsrHrg0D4podKEMU+03eE2WXiNmTaF6myYkSTvf22qOKz YtuiVYlrdKqXpEWvpAa0vVfHiaEz2jz3jaW2zl2VOzE707u3dxFQfxUskaT9YXq45dUcOMoKCC3 hPOf4HA== X-Google-Smtp-Source: AGHT+IHj2ZpYl1siq/JnQdl8XUH43iMpNaE3SW4WBMxK/9aEO8opZUdsBx1VkvGgbtOsUpBOLM0Zgg== X-Received: by 2002:a5d:498d:0:b0:33a:ec23:1a22 with SMTP id r13-20020a5d498d000000b0033aec231a22mr895144wrq.32.1706698381427; Wed, 31 Jan 2024 02:53:01 -0800 (PST) From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: xen-devel@lists.xenproject.org Cc: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , Christian Lindig , David Scott , Wei Liu , Anthony PERARD Subject: [PATCH v1 1/2] oxenstored: use Map instead of Hashtbl for quotas Date: Wed, 31 Jan 2024 10:52:55 +0000 Message-ID: <513931c932fa8d088acefdfc2d3b73d4c3070002.1706697858.git.edwin.torok@cloud.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: References: MIME-Version: 1.0 On a stress test running 1000 VMs flamegraphs have shown that `oxenstored` spends a large amount of time in `Hashtbl.copy` and the GC. Hashtable complexity: * read/write: O(1) average * copy: O(domains) -- copying the entire table Map complexity: * read/write: O(log n) worst case * copy: O(1) -- a word copy We always perform at least one 'copy' when processing each xenstore packet (regardless whether it is a readonly operation or inside a transaction or not), so the actual complexity per packet is: * Hashtbl: O(domains) * Map: O(log domains) Maps are the clear winner, and a better fit for the immutable xenstore tree. Signed-off-by: Edwin Török --- tools/ocaml/xenstored/quota.ml | 65 ++++++++++++++++++---------------- 1 file changed, 34 insertions(+), 31 deletions(-) diff --git a/tools/ocaml/xenstored/quota.ml b/tools/ocaml/xenstored/quota.ml index 300d78a50b..f6e28ecc6a 100644 --- a/tools/ocaml/xenstored/quota.ml +++ b/tools/ocaml/xenstored/quota.ml @@ -23,66 +23,69 @@ let activate = ref true let maxent = ref (1000) let maxsize = ref (2048) +module Domid = struct + type t = Xenctrl.domid + let compare (a:t) (b:t) = compare a b +end + +module DomidMap = Map.Make(Domid) + type t = { maxent: int; (* max entities per domU *) maxsize: int; (* max size of data store in one node *) - cur: (Xenctrl.domid, int) Hashtbl.t; (* current domains quota *) + mutable cur: int DomidMap.t; (* current domains quota *) } let to_string quota domid = - if Hashtbl.mem quota.cur domid - then Printf.sprintf "dom%i quota: %i/%i" domid (Hashtbl.find quota.cur domid) quota.maxent - else Printf.sprintf "dom%i quota: not set" domid + try + Printf.sprintf "dom%i quota: %i/%i" domid (DomidMap.find domid quota.cur) quota.maxent + with Not_found -> + Printf.sprintf "dom%i quota: not set" domid let create () = - { maxent = !maxent; maxsize = !maxsize; cur = Hashtbl.create 100; } + { maxent = !maxent; maxsize = !maxsize; cur = DomidMap.empty; } -let copy quota = { quota with cur = (Hashtbl.copy quota.cur) } +let copy quota = { quota with cur = quota.cur } -let del quota id = Hashtbl.remove quota.cur id +let del quota id = { quota with cur = DomidMap.remove id quota.cur } let _check quota id size = if size > quota.maxsize then ( warn "domain %u err create entry: data too big %d" id size; raise Data_too_big ); - if id > 0 && Hashtbl.mem quota.cur id then - let entry = Hashtbl.find quota.cur id in + if id > 0 then + try + let entry = DomidMap.find id quota.cur in if entry >= quota.maxent then ( warn "domain %u cannot create entry: quota reached" id; raise Limit_reached ) + with Not_found -> () let check quota id size = if !activate then _check quota id size -let get_entry quota id = Hashtbl.find quota.cur id +let find_or_zero quota_cur id = + try DomidMap.find id quota_cur with Not_found -> 0 -let set_entry quota id nb = - if nb = 0 - then Hashtbl.remove quota.cur id - else begin - if Hashtbl.mem quota.cur id then - Hashtbl.replace quota.cur id nb - else - Hashtbl.add quota.cur id nb - end +let update_entry quota_cur id diff = + let nb = diff + find_or_zero quota_cur id in + if nb = 0 then DomidMap.remove id quota_cur + else DomidMap.add id nb quota_cur let del_entry quota id = - try - let nb = get_entry quota id in - set_entry quota id (nb - 1) - with Not_found -> () + quota.cur <- update_entry quota.cur id (-1) let add_entry quota id = - let nb = try get_entry quota id with Not_found -> 0 in - set_entry quota id (nb + 1) - -let add quota diff = - Hashtbl.iter (fun id nb -> set_entry quota id (get_entry quota id + nb)) diff.cur + quota.cur <- update_entry quota.cur id (+1) let merge orig_quota mod_quota dest_quota = - Hashtbl.iter (fun id nb -> let diff = nb - (try get_entry orig_quota id with Not_found -> 0) in - if diff <> 0 then - set_entry dest_quota id ((try get_entry dest_quota id with Not_found -> 0) + diff)) mod_quota.cur + let fold_merge id nb dest = + match nb - find_or_zero orig_quota.cur id with + | 0 -> dest (* not modified *) + | diff -> update_entry dest id diff (* update with [x=x+diff] *) + in + dest_quota.cur <- DomidMap.fold fold_merge mod_quota.cur dest_quota.cur + (* dest_quota = dest_quota + (mod_quota - orig_quota) *) From patchwork Wed Jan 31 10:52:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Edwin Torok X-Patchwork-Id: 13539166 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 06D8AC47258 for ; Wed, 31 Jan 2024 10:53:19 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.673902.1048463 (Exim 4.92) (envelope-from ) id 1rV8DM-0005cr-5X; Wed, 31 Jan 2024 10:53:08 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 673902.1048463; Wed, 31 Jan 2024 10:53:08 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1rV8DM-0005bg-0I; Wed, 31 Jan 2024 10:53:08 +0000 Received: by outflank-mailman (input) for mailman id 673902; Wed, 31 Jan 2024 10:53:06 +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 1rV8DK-0005ZD-M6 for xen-devel@lists.xenproject.org; Wed, 31 Jan 2024 10:53:06 +0000 Received: from mail-wr1-x431.google.com (mail-wr1-x431.google.com [2a00:1450:4864:20::431]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id e87c9b25-c026-11ee-98f5-efadbce2ee36; Wed, 31 Jan 2024 11:53:03 +0100 (CET) Received: by mail-wr1-x431.google.com with SMTP id ffacd0b85a97d-337d05b8942so3977363f8f.3 for ; Wed, 31 Jan 2024 02:53:03 -0800 (PST) Received: from fedora39.edvint-x-u ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id o1-20020a5d4081000000b0033ae50e2c6asm10585757wrp.83.2024.01.31.02.53.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 31 Jan 2024 02:53:02 -0800 (PST) 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: e87c9b25-c026-11ee-98f5-efadbce2ee36 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloud.com; s=cloud; t=1706698382; x=1707303182; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=pEOJ3dKfDa3jEbqZ0msr8PUUdDA4TmMKdDalOhPmKw4=; b=bUydjSuXSmCol8BThYnEUKsS+x8gOHcyovnHC4oZ6urjMt49XLhzNp2IkklEwL2zfo DELrWWuhLdX13YdZdmmcnTZJ3wQozt92+PUvlUSjzqmg8UTJzkW6MB6HtPxyX84Bbm2M DG9+xlLCx38Jdj3qtIW64VFdbM5d/GHpxGGxQ= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1706698382; x=1707303182; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=pEOJ3dKfDa3jEbqZ0msr8PUUdDA4TmMKdDalOhPmKw4=; b=NFgwotV3CmXICNzuM9KRzOGfJ93HiC1RAzGCnhQ5mX7zzkYnFvKKXV5juNEh9NqU7H Yfj0EyUhsf9ddiaDjQZZ1rQdUtXp/SQV1aeuRHv22gLt64FOOHZ6silgN7IBuhezHoxb oTvFkyoGNzTK+X7oWMYq5grAPPNQOrm3GWbGFMxf/8goLlaGZmEtp7dguilVXKyjnthh v5aQtfU+a9BebikcuWJJrz9svjRXKXxzBTnAtkxJxZA77R4qXKWghUz3QdwHpFUI0uBO paNBm+c6GpMg41XRT9D0kl7m8Z6lwa2w7PsX6NXPv1YEWpyE90qLwhWV9IYwpNZ1XTMI WP3w== X-Gm-Message-State: AOJu0Yw5h8f8q3jkNaoO0g7NB94D/jVuDaEOH5q9j6OkvEPjzw9aTT+n shaCOCfQJsnyU/K5l2Y7tQy/zavHkuOq3PzuQP+/DsmzLm799c6m+Y4cE89kNUi4OZy1VKg1DUD ttc87ew== X-Google-Smtp-Source: AGHT+IErnvggzIIJIqkmJKISVmMAepy9lUitEB9v6/O/w4NFnemd6oGnJwTS6QTKsDxkkGRS0NjoYA== X-Received: by 2002:a5d:630f:0:b0:33a:eb24:8383 with SMTP id i15-20020a5d630f000000b0033aeb248383mr891032wru.13.1706698382705; Wed, 31 Jan 2024 02:53:02 -0800 (PST) From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: xen-devel@lists.xenproject.org Cc: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , Christian Lindig , David Scott , Wei Liu , Anthony PERARD Subject: [PATCH v1 2/2] oxenstored: make Quota.t pure Date: Wed, 31 Jan 2024 10:52:56 +0000 Message-ID: X-Mailer: git-send-email 2.43.0 In-Reply-To: References: MIME-Version: 1.0 Now that we no longer have a hashtable inside we can make Quota.t pure, and push the mutable update to its callers. Store.t already had a mutable Quota.t field. No functional change. Signed-off-by: Edwin Török Acked-by: Christian Lindig --- tools/ocaml/xenstored/quota.ml | 8 ++++---- tools/ocaml/xenstored/store.ml | 17 ++++++++++------- 2 files changed, 14 insertions(+), 11 deletions(-) diff --git a/tools/ocaml/xenstored/quota.ml b/tools/ocaml/xenstored/quota.ml index f6e28ecc6a..1f652040d8 100644 --- a/tools/ocaml/xenstored/quota.ml +++ b/tools/ocaml/xenstored/quota.ml @@ -33,7 +33,7 @@ module DomidMap = Map.Make(Domid) type t = { maxent: int; (* max entities per domU *) maxsize: int; (* max size of data store in one node *) - mutable cur: int DomidMap.t; (* current domains quota *) + cur: int DomidMap.t; (* current domains quota *) } let to_string quota domid = @@ -76,10 +76,10 @@ let update_entry quota_cur id diff = else DomidMap.add id nb quota_cur let del_entry quota id = - quota.cur <- update_entry quota.cur id (-1) + {quota with cur = update_entry quota.cur id (-1)} let add_entry quota id = - quota.cur <- update_entry quota.cur id (+1) + {quota with cur = update_entry quota.cur id (+1)} let merge orig_quota mod_quota dest_quota = let fold_merge id nb dest = @@ -87,5 +87,5 @@ let merge orig_quota mod_quota dest_quota = | 0 -> dest (* not modified *) | diff -> update_entry dest id diff (* update with [x=x+diff] *) in - dest_quota.cur <- DomidMap.fold fold_merge mod_quota.cur dest_quota.cur + {dest_quota with cur = DomidMap.fold fold_merge mod_quota.cur dest_quota.cur} (* dest_quota = dest_quota + (mod_quota - orig_quota) *) diff --git a/tools/ocaml/xenstored/store.ml b/tools/ocaml/xenstored/store.ml index 38a4945372..9b8dd2812d 100644 --- a/tools/ocaml/xenstored/store.ml +++ b/tools/ocaml/xenstored/store.ml @@ -85,7 +85,9 @@ module Node = struct raise Define.Permission_denied; end - let rec recurse fct node = fct node; SymbolMap.iter (fun _ -> recurse fct) node.children + let rec recurse fct node acc = + let acc = fct node acc in + SymbolMap.fold (fun _ -> recurse fct) node.children acc (** [recurse_filter_map f tree] applies [f] on each node in the tree recursively, possibly removing some nodes. @@ -408,7 +410,7 @@ let dump_buffer store = dump_store_buf store.root let set_node store path node orig_quota mod_quota = let root = Path.set_node store.root path node in store.root <- root; - Quota.merge orig_quota mod_quota store.quota + store.quota <- Quota.merge orig_quota mod_quota store.quota let write store perm path value = let node, existing = get_deepest_existing_node store path in @@ -422,7 +424,7 @@ let write store perm path value = let root, node_created = path_write store perm path value in store.root <- root; if node_created - then Quota.add_entry store.quota owner + then store.quota <- Quota.add_entry store.quota owner let mkdir store perm path = let node, existing = get_deepest_existing_node store path in @@ -431,7 +433,7 @@ let mkdir store perm path = if not (existing || (Perms.Connection.is_dom0 perm)) then Quota.check store.quota owner 0; store.root <- path_mkdir store perm path; if not existing then - Quota.add_entry store.quota owner + store.quota <- Quota.add_entry store.quota owner let rm store perm path = let rmed_node = Path.get_node store.root path in @@ -439,7 +441,7 @@ let rm store perm path = | None -> raise Define.Doesnt_exist | Some rmed_node -> store.root <- path_rm store perm path; - Node.recurse (fun node -> Quota.del_entry store.quota (Node.get_owner node)) rmed_node + store.quota <- Node.recurse (fun node quota -> Quota.del_entry quota (Node.get_owner node)) rmed_node store.quota let setperms store perm path nperms = match Path.get_node store.root path with @@ -450,8 +452,9 @@ let setperms store perm path nperms = if not ((old_owner = new_owner) || (Perms.Connection.is_dom0 perm)) then raise Define.Permission_denied; store.root <- path_setperms store perm path nperms; - Quota.del_entry store.quota old_owner; - Quota.add_entry store.quota new_owner + store.quota <- + let quota = Quota.del_entry store.quota old_owner in + Quota.add_entry quota new_owner let reset_permissions store domid = Logging.info "store|node" "Cleaning up xenstore ACLs for domid %d" domid;