linux-kernel - Re: [PATCH] hwmon: coretemp: use list instead of fixed size array for temp data

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: <55A93365.4000702@roeck-us.net>
Date:	Fri, 17 Jul 2015 09:55:01 -0700
From:	Guenter Roeck <linux@...ck-us.net>
To:	"Odzioba, Lukasz" <lukasz.odzioba@...el.com>,
	Jean Delvare <jdelvare@...e.de>
CC:	"Yu, Fenghua" <fenghua.yu@...el.com>,
	"lm-sensors@...sensors.org" <lm-sensors@...sensors.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] hwmon: coretemp: use list instead of fixed size array
 for temp data

On 07/16/2015 06:17 AM, Odzioba, Lukasz wrote:
> On  Wednesday, July 15, 2015 11:08 PM Jean Delvare wrote:
>> I see the benefit of removing the arbitrary limit, but why use a list
>> instead of a dynamically allocated array? This is turning a O(1)
>> algorithm into a O(n) algorithm. I know n isn't too large in this case
>> but I still consider it bad practice if it can be avoided.
>
> This patch tries to solve two problems which are present on current hardware:
> -cpus with more than 32 cores
> -core id is greater than NUM_REAL_CORES
>
> In both cases it ends up with the following error in dmesg:
> coretemp coretemp.0: Adding Core XXX failed
>
> We could just bump NUM_REAL_CORES to 128 like we did in 2012 and call it
> solved, but the problem will come back eventually and it is waste of
> memory for cpus with handful of cores.
>
> If there is way to obtain maximum core id during module initialization,
> then we can allocate array and keep O(1) access. If we can't figure out
> maximum core id then we can increase size of the array when new cores are
> added. The problem with this is that core id enumeration can be sparse so
> again we have waste of memory.
>
>> Do you expect core IDs to become arbitrarily large?
>> Significantly larger than the core count?
>
> The question is what does significantly mean.
> According to Documentation/cputopology.txt:
> ---
> 2) /sys/devices/system/cpu/cpuX/topology/core_id:
>
> 	the CPU core ID of cpuX. Typically it is the hardware platform's
> 	identifier (rather than the kernel's).  The actual value is
> 	architecture and platform dependent.
> ---
>
> Even now we can have one core present with id like 60 (think of Xeon Phi).
> I haven't seen in the wild insane core ids like thousands, but I don't see
> a reason why we shouldn't handle it in a proper manner.
>
> Current patch does not use more memory than it is needed, but the pitfall is
> that it increased access complexity from O(1) to O(n). We could slide another
> patch on top of this one to reduce access complexity from O(n) to O(logn)
> by using i.e. radix tree. I preferred to send functional fix in the first
> place, and then work on optimization if there is a concern about it.
> Forgive me if it is not appropriate.
>

You don't really explain why your approach would be better than allocating
an array of pointers to struct temp_data and increasing its size using
krealloc if needed.

Guenter

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/