From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f48.google.com (mail-wr1-f48.google.com [209.85.221.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 87F9C3A4AD5 for ; Wed, 14 Jan 2026 16:41:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.48 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768408914; cv=none; b=LYqigR9zdEKTjg1krOWSL8aWXN42oo8ua7wKrWbudjJ5fW1/TQFwtY5y/3FDXiWu98VFoOp5w0exUyI7UlBlv+8Hl/OUiUSkNP/zts9KpaXatokFYDn5lBT1vUsTaNt9Sx5YQ/cGL0PhflOHk5f0GCF66tGiAffRvlrChScF93c= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768408914; c=relaxed/simple; bh=Cx7kvRIX8Qrq0TT1Ah/lwLqz6bmyUkl+ja3kUOilRek=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=qqwZXEVghddtElxYHH6HvlxbzkHHiL3ndF55lla6tEC6xbw7rt17jwpvnzcV1aqVRdku1+ZPBxw44miAgchPUCEjQG90hfC+yqy5nV4FQOcj3JQmzx/2WD2m5+6uYCKCV0TMsEqarLZQgOmGqSDP0UAZWUSaYoN+4rvh5oMBfYA= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=suse.com; spf=pass smtp.mailfrom=suse.com; dkim=pass (2048-bit key) header.d=suse.com header.i=@suse.com header.b=U9wSIwSo; arc=none smtp.client-ip=209.85.221.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=suse.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=suse.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=suse.com header.i=@suse.com header.b="U9wSIwSo" Received: by mail-wr1-f48.google.com with SMTP id ffacd0b85a97d-42fbad1fa90so52174f8f.0 for ; Wed, 14 Jan 2026 08:41:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=google; t=1768408911; x=1769013711; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=a5XsqmTd3Wuf5i5kP7cIwbfY5FVmF/Do+b5WJ9+iLQY=; b=U9wSIwSodCs06wB7tdkolYgmsgzIFQLUpE1w4ZxkVPJkx7mJxb0rvve4y+SKNsTsrs pb1DhXcIRwZmGPHt5pUfhwQ6mZTs+GwzNZ4GQHXnTVCAVBDXOL6xhifiPJSQ27rA9xpr yG826RjZRslf9YZGiihDwHwNnKJRTE7Tav0CrK9MZhE5gEjHLADjjOU8WGSEoAusX4+n xnH9pWqhEWh4U8rb0tMVQzLE7kHkxFfMgXfWDkBkrAuKjPSfHBhahrH8sW5V+5QlrKaN WV81egIsfqrVyDoPEGsNyCHaez3fyzws95CuvxYFOFL1hwSdiQkG19CUwWs/BoGeZhbA Nisw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768408911; x=1769013711; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-gg:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=a5XsqmTd3Wuf5i5kP7cIwbfY5FVmF/Do+b5WJ9+iLQY=; b=TcuWu+vEcAv3cCWpIsm800QHqZF9beS/pgMMqOt+v/dqWmJ6/Huzwk/DuF0DiNeVif x6V9D0inIB/tKb53LWPvy3DjKMmLGjXkUnA6YXw/g6bzKuQPfI3zngZLNrgEb3LwAbah Ku1xzqUpw1j8gRZDZYvFQ9WcFogFFWUSHdE6Y+QZtY1VVGH/wG7vxC6yTl/YZhP1t8/x VS2XNV5w8tR7uMYFNNd5QRUBMG/I9GOX7+Is2F1xYKIey5JO9103QKjJrRXKE9S33h7h 6+lDDtTEpClGue/83YA1mipmXEemCiw3K52gSRm+vgIFmoDRsn8EiC72PG98zt7m+sZy ht4g== X-Forwarded-Encrypted: i=1; AJvYcCWp1GH+/+I+sBCD0OmyxR+sxKQHC88Fhdw+Q8w4VtvJMD3fV9xN0QaKp7J3UHxqPqD+zrFQ+n/d9abYv9U=@vger.kernel.org X-Gm-Message-State: AOJu0YzQJ2hf8ZHNPObqImRQI7QV+EjZGpwHX/yXyZqW3mZJnbNgCbTf CtI76x5VxELzCIVCDo2XAloHuA909Zf/AkL4RhB7QHjdE83wBgwE4ApczsJdo9ay5zc= X-Gm-Gg: AY/fxX6BlXBlbzuZrHMTxytAuvwMpgbY4Cmcy6Y40z41k7ZnnKwNtm33fKpJwOyIVHn NwOQAGOfDDJsoSN5TX3WVb/nwmsfR93QdFe3+ULnx7GSeo6eyjvgcYpPi3xhRZDyDVZVJtkoRnn VDd0nX/WP530+cWbUD35e2I9LR75r4v3Dkm+WCrgG2eVE60W5txq72ourk38beqSYZVVkglbA2m 13M7ZtiLrgsOIg8h1YttDqwIsxtPuS57qw3K89RyikkSQiFKk1o2UnVqnuzTJ4B3u6KwGuAhSGU xGt5HtuqwCcFHFCxxROLt6LwVsTRs0WJOMDzSh/08C4Dhyk1cHMvsGJXnYvoiK5LKz1bjLtcXLY 3VWIW6W080qndODItyp6aLWCNC7BDBkWhuqNOLrdNZguWW0+JkaQzC2ov/InYzGpeq1yjcFDRV+ lYFSiWEh8sgZCwQz3trFV7pxZqSc+IfM4kZmk= X-Received: by 2002:a05:6000:4387:b0:432:c092:ee3b with SMTP id ffacd0b85a97d-4342d5dd58cmr4121853f8f.62.1768408910801; Wed, 14 Jan 2026 08:41:50 -0800 (PST) Received: from localhost (109-81-19-111.rct.o2.cz. [109.81.19.111]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-434af64a643sm284591f8f.1.2026.01.14.08.41.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Jan 2026 08:41:50 -0800 (PST) Date: Wed, 14 Jan 2026 17:41:48 +0100 From: Michal Hocko To: Mathieu Desnoyers Cc: Andrew Morton , linux-kernel@vger.kernel.org, "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , linux-mm@kvack.org, linux-trace-kernel@vger.kernel.org, Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan Subject: Re: [PATCH v16 1/3] lib: Introduce hierarchical per-cpu counters Message-ID: References: <20260114145915.49926-1-mathieu.desnoyers@efficios.com> <20260114145915.49926-2-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260114145915.49926-2-mathieu.desnoyers@efficios.com> On Wed 14-01-26 09:59:13, Mathieu Desnoyers wrote: > * Motivation > > The purpose of this hierarchical split-counter scheme is to: > > - Minimize contention when incrementing and decrementing counters, > - Provide fast access to a sum approximation, > - Provide a sum approximation with an acceptable accuracy level when > scaling to many-core systems. > - Provide approximate and precise comparison of two counters, and > between a counter and a value. > - Provide possible precise sum ranges for a given sum approximation. > > Its goals are twofold: > > - Improve the accuracy of the approximated RSS counter values returned > by proc interfaces [1], > - Reduce the latency of the OOM killer on large many-core systems. > > * Design > > The hierarchical per-CPU counters propagate a sum approximation through > a N-way tree. When reaching the batch size, the carry is propagated > through a binary tree which consists of logN(nr_cpu_ids) levels. The > batch size for each level is twice the batch size of the prior level. > > Example propagation diagram with 8 cpus through a binary tree: > > Level 0: 0 1 2 3 4 5 6 7 > | / | / | / | / > | / | / | / | / > | / | / | / | / > Level 1: 0 1 2 3 > | / | / > | / | / > | / | / > Level 2: 0 1 > | / > | / > | / > Level 3: 0 > > For a binary tree, the maximum inaccuracy is bound by: > batch_size * log2(nr_cpus) * nr_cpus > which evolves with O(n*log(n)) as the number of CPUs increases. > > For a N-way tree, the maximum inaccuracy can be pre-calculated > based on the the N-arity of each level and the batch size. One thing you should probably mention here is the memory consumption of the structure. I have briefly looked at the implementation and concluded that I do not have enough time to make a thorough review. Sorry about that. As I've said in previous version the overall idea is sound. Especially if the additional memory consumption is not a factor. I will let others judge implementation details. Thanks! -- Michal Hocko SUSE Labs