Skip to content

nsrepair2: Improve sorting performance and add tests

Nick Huang acpica-devel linux-acpi lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest2 patches 5 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2ACPI: nsrepair2: Replace O(n²) bubble sort with O(n log n) sort_r()drivers/acpi/acpica/nsrepair2.c+62 -252 replies
2/2ACPI: acpica: Add KUnit tests for nsrepair2 repair functionsdrivers/acpi/acpica/nsrepair2_test.c+854 -01 reply

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [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
Signature · 1 line
2.43.0