linux-kernel - [PATCH 0/2] nsrepair2: Improve sorting performance and add tests

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-next>] [day] [month] [year] [list]

Message-ID: <20260201130334.3107-1-sef1548@gmail.com>
Date: Sun,  1 Feb 2026 13:03:32 +0000
From: Nick Huang <sef1548@...il.com>
To: "Rafael J . Wysocki" <rafael@...nel.org>,
	Robert Moore <robert.moore@...el.com>
Cc: Len Brown <lenb@...nel.org>,
	linux-acpi@...r.kernel.org,
	acpica-devel@...ts.linux.dev,
	linux-kernel@...r.kernel.org,
	paladin@...b.edu.tw,
	kusogame68@...il.com,
	ceyanglab@...il.com,
	n1136402@...b.edu.tw,
	Nick Huang <sef1548@...il.com>
Subject: [PATCH 0/2] nsrepair2: Improve sorting performance and add tests 

   This patch series improves the ACPI nsrepair2 sorting implementation
   and adds comprehensive KUnit tests.

   Patch 1 replaces the O(n²) bubble sort algorithm in acpi_ns_sort_list()
   with the kernel's sort_r() function, which uses heapsort to achieve
   O(n log n) time complexity. This improves performance when sorting
   large ACPI package lists (e.g., _PSS, _TSS) while reducing code
   complexity by leveraging the existing kernel sort API.

   Patch 2 adds KUnit tests to verify the repair functions in nsrepair2.c,
   covering:
     - ACPI operand object creation (integer, string, buffer, package)
     - Namespace node creation and NAMESEG comparison
     - Package structures for _PSS, _CST, _ALR, _PRT methods
     - _HID string format verification
     - _FDE buffer expansion
     - Sorting logic with ascending/descending order



Nick Huang (2):
  ACPI: nsrepair2: Replace O(n²) bubble sort with O(n log n) sort_r()
  ACPI: acpica: Add KUnit tests for nsrepair2 repair functions

 drivers/acpi/acpica/nsrepair2.c      |  87 ++-
 drivers/acpi/acpica/nsrepair2_test.c | 854 +++++++++++++++++++++++++++
 2 files changed, 916 insertions(+), 25 deletions(-)
 create mode 100644 drivers/acpi/acpica/nsrepair2_test.c

-- 
2.43.0