linux-kernel - Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ga4sohvmxgu4hr5o2l5uylb3ryjfqbn7z4nlqb7gryw5lk5rdo@lgqh5rndrfln>
Date: Thu, 4 Jul 2024 14:12:29 +0200
From: Michal Koutný <mkoutny@...e.com>
To: Xavier <xavier_qy@....com>
Cc: tj@...nel.org, longman@...hat.com, akpm@...ux-foundation.org, 
	lizefan.x@...edance.com, hannes@...xchg.org, cgroups@...r.kernel.org, 
	linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org
Subject: Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel
 library

On Wed, Jul 03, 2024 at 07:20:09PM GMT, Xavier <xavier_qy@....com> wrote:
> >Xavier, not sure if you responded to my suggestion of considered zeroed
> >object a valid initialized one. That could save some init work (and
> >move it to alternative uf_find, see below).
> >
> >With uf_find body checking for NULL:
> >
> >	while (node->parent != node) {
> >		parent = node->parent;
> >		node->parent = parent ? parent->parent : node;
> >		node = node->parent;
> >	}
> 
> Yes, I noticed your suggestion. In patch v4, I implemented it by
> initializing to 0 and adding a check for whether the parent is 0 in
> uf_find.

Ah, I didn't read all versions. (You may consider adding a short
changelog when sending a new version of patches where main evolution
points are summed up. ;-))

> However, later, when I was reviewing the algorithm's documentation, I
> noticed it requires initialization to itself.

Well, that's not a hard requirement.

> Moreover, uf_find is a high-frequency operation, if we add a parent
> check within it, the efficiency impact each time would be more
> significant than initializing once. Therefore, I adhered to the
> initialization to itself approach.

I see, thanks for the clarifications,
Michal

Download attachment "signature.asc" of type "application/pgp-signature" (229 bytes)