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

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

[Nick Huang]

   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

[PATCH 1/2] ACPI: nsrepair2: Replace O(n²) bubble sort with O(n log n) sort_r()

[Nick Huang]

   Replace the O(n²) bubble sort implementation in acpi_ns_sort_list()
   with the kernel's sort_r() function which uses heapsort, providing
   O(n log n) time complexity.

   This improves performance for large ACPI package lists while also
   reducing code complexity by leveraging the existing kernel sort API.

Signed-off-by: Nick Huang <sef1548@gmail.com>
---
 drivers/acpi/acpica/nsrepair2.c | 87 +++++++++++++++++++++++----------
 1 file changed, 62 insertions(+), 25 deletions(-)

diff --git a/drivers/acpi/acpica/nsrepair2.c b/drivers/acpi/acpica/nsrepair2.c
index 8dbb870f4..a39ef59fe 100644
--- a/drivers/acpi/acpica/nsrepair2.c
+++ b/drivers/acpi/acpica/nsrepair2.c
@@ -9,6 +9,7 @@
  *****************************************************************************/
 
 #include <acpi/acpi.h>
+#include <linux/sort.h>
 #include "accommon.h"
 #include "acnamesp.h"
 
@@ -84,6 +85,14 @@ acpi_ns_check_sorted_list(struct acpi_evaluate_info *info,
 static void
 acpi_ns_remove_element(union acpi_operand_object *obj_desc, u32 index);
 
+/* Context structure for sort comparison function */
+struct acpi_sort_context {
+	u32 sort_index;
+	u8 sort_direction;
+};
+
+static int acpi_ns_sort_cmp(const void *a, const void *b, const void *priv);
+
 static void
 acpi_ns_sort_list(union acpi_operand_object **elements,
 		  u32 count, u32 index, u8 sort_direction);
@@ -851,6 +860,52 @@ acpi_ns_check_sorted_list(struct acpi_evaluate_info *info,
 	return (AE_OK);
 }
 
+/******************************************************************************
+ *
+ * FUNCTION:    acpi_ns_sort_cmp
+ *
+ * PARAMETERS:  a               - First element to compare
+ *              b               - Second element to compare
+ *              priv            - Pointer to sort context (acpi_sort_context)
+ *
+ * RETURN:      -1, 0, or 1 depending on sort order
+ *
+ * DESCRIPTION: Comparison function for sort_r() API. Compares the integer
+ *              values at the specified index within package elements.
+ *
+ *****************************************************************************/
+
+static int acpi_ns_sort_cmp(const void *a, const void *b, const void *priv)
+{
+	union acpi_operand_object *obj_a = *(union acpi_operand_object **)a;
+	union acpi_operand_object *obj_b = *(union acpi_operand_object **)b;
+	const struct acpi_sort_context *ctx = priv;
+	union acpi_operand_object *value_a;
+	union acpi_operand_object *value_b;
+	u64 a_val;
+	u64 b_val;
+
+	value_a = obj_a->package.elements[ctx->sort_index];
+	value_b = obj_b->package.elements[ctx->sort_index];
+
+	a_val = value_a->integer.value;
+	b_val = value_b->integer.value;
+
+	if (ctx->sort_direction == ACPI_SORT_ASCENDING) {
+		if (a_val < b_val)
+			return -1;
+		if (a_val > b_val)
+			return 1;
+	} else {
+		if (a_val > b_val)
+			return -1;
+		if (a_val < b_val)
+			return 1;
+	}
+
+	return 0;
+}
+
 /******************************************************************************
  *
  * FUNCTION:    acpi_ns_sort_list
@@ -873,31 +928,13 @@ static void
 acpi_ns_sort_list(union acpi_operand_object **elements,
 		  u32 count, u32 index, u8 sort_direction)
 {
-	union acpi_operand_object *obj_desc1;
-	union acpi_operand_object *obj_desc2;
-	union acpi_operand_object *temp_obj;
-	u32 i;
-	u32 j;
-
-	/* Simple bubble sort */
-
-	for (i = 1; i < count; i++) {
-		for (j = (count - 1); j >= i; j--) {
-			obj_desc1 = elements[j - 1]->package.elements[index];
-			obj_desc2 = elements[j]->package.elements[index];
-
-			if (((sort_direction == ACPI_SORT_ASCENDING) &&
-			     (obj_desc1->integer.value >
-			      obj_desc2->integer.value))
-			    || ((sort_direction == ACPI_SORT_DESCENDING)
-				&& (obj_desc1->integer.value <
-				    obj_desc2->integer.value))) {
-				temp_obj = elements[j - 1];
-				elements[j - 1] = elements[j];
-				elements[j] = temp_obj;
-			}
-		}
-	}
+	struct acpi_sort_context ctx;
+
+	ctx.sort_index = index;
+	ctx.sort_direction = sort_direction;
+
+	sort_r(elements, count, sizeof(union acpi_operand_object *),
+	       acpi_ns_sort_cmp, NULL, &ctx);
 }
 
 /******************************************************************************
-- 
2.43.0

[PATCH 2/2] ACPI: acpica: Add KUnit tests for nsrepair2 repair functions

[Nick Huang]

   Add comprehensive KUnit tests for the ACPI predefined method repair
   functions in nsrepair2.c. The tests cover:

   - 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 and repair scenarios
   - _FDE buffer expansion (5 bytes to 20 bytes)
   - acpi_ns_sort_list sorting logic with ascending/descending order

   The tests use mock objects allocated with kunit_kzalloc to verify
   the data structures and sorting algorithms used by the repair code.

Signed-off-by: Nick Huang <sef1548@gmail.com>
---
 drivers/acpi/acpica/nsrepair2_test.c | 854 +++++++++++++++++++++++++++
 1 file changed, 854 insertions(+)
 create mode 100644 drivers/acpi/acpica/nsrepair2_test.c

diff --git a/drivers/acpi/acpica/nsrepair2_test.c b/drivers/acpi/acpica/nsrepair2_test.c
new file mode 100644
index 000000000..7d59453d1
--- /dev/null
+++ b/drivers/acpi/acpica/nsrepair2_test.c
@@ -0,0 +1,854 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for nsrepair2.c - ACPI predefined method repair functions
+ */
+
+#include <kunit/test.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <acpi/acpi.h>
+#include <linux/sort.h> 
+#include "accommon.h"
+#include "acnamesp.h"
+
+/*
+ * Test helper: create a mock integer operand object
+ */
+static union acpi_operand_object *create_integer_object(struct kunit *test, u64 value)
+{
+	union acpi_operand_object *obj;
+
+	obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, obj);
+
+	obj->common.type = ACPI_TYPE_INTEGER;
+	obj->common.reference_count = 1;
+	obj->integer.value = value;
+
+	return obj;
+}
+
+/*
+ * Test helper: create a mock string operand object
+ */
+static union acpi_operand_object *create_string_object(struct kunit *test,
+						       const char *str)
+{
+	union acpi_operand_object *obj;
+	char *buf;
+	size_t len;
+
+	obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, obj);
+
+	len = strlen(str);
+	buf = kunit_kzalloc(test, len + 1, GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, buf);
+	memcpy(buf, str, len + 1);
+
+	obj->common.type = ACPI_TYPE_STRING;
+	obj->common.reference_count = 1;
+	obj->string.length = len;
+	obj->string.pointer = buf;
+
+	return obj;
+}
+
+/*
+ * Test helper: create a mock buffer operand object
+ */
+static union acpi_operand_object *create_buffer_object(struct kunit *test,
+						       u8 *data, u32 length)
+{
+	union acpi_operand_object *obj;
+	u8 *buf = NULL;
+
+	KUNIT_ASSERT_GT(test, length, 0U);
+
+	obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, obj);
+
+	buf = kunit_kzalloc(test, length, GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, buf);
+	memcpy(buf, data, length);
+
+	obj->common.type = ACPI_TYPE_BUFFER;
+	obj->common.reference_count = 1;
+	obj->buffer.length = length;
+	obj->buffer.pointer = buf;
+
+	return obj;
+}
+
+/*
+ * Test helper: create a mock package operand object
+ */
+static union acpi_operand_object *create_package_object(struct kunit *test,
+							u32 count)
+{
+	union acpi_operand_object *obj;
+	union acpi_operand_object **elements = NULL;
+
+	KUNIT_ASSERT_GT(test, count, 0U);
+
+	obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, obj);
+
+	elements = kunit_kzalloc(test, count * sizeof(*elements), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, elements);
+
+	obj->common.type = ACPI_TYPE_PACKAGE;
+	obj->common.reference_count = 1;
+	obj->package.count = count;
+	obj->package.elements = elements;
+
+	return obj;
+}
+
+/*
+ * Test helper: create a mock namespace node
+ * Note: name must be exactly ACPI_NAMESEG_SIZE (4) characters
+ */
+static struct acpi_namespace_node *create_namespace_node(struct kunit *test,
+							 const char *name)
+{
+	struct acpi_namespace_node *node;
+	size_t name_len;
+
+	KUNIT_ASSERT_NOT_NULL(test, name);
+	name_len = strlen(name);
+	KUNIT_ASSERT_GE(test, name_len, (size_t)ACPI_NAMESEG_SIZE);
+
+	node = kunit_kzalloc(test, sizeof(*node), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+
+	memcpy(node->name.ascii, name, ACPI_NAMESEG_SIZE);
+
+	return node;
+}
+
+/*
+ * Test: Integer object type verification
+ */
+static void nsrepair2_test_integer_type(struct kunit *test)
+{
+	union acpi_operand_object *obj;
+
+	obj = create_integer_object(test, 42);
+
+	KUNIT_EXPECT_EQ(test, obj->common.type, (u8)ACPI_TYPE_INTEGER);
+	KUNIT_EXPECT_EQ(test, obj->integer.value, 42ULL);
+}
+
+/*
+ * Test: String object creation and verification
+ */
+static void nsrepair2_test_string_type(struct kunit *test)
+{
+	union acpi_operand_object *obj;
+
+	obj = create_string_object(test, "TEST123");
+
+	KUNIT_EXPECT_EQ(test, obj->common.type, (u8)ACPI_TYPE_STRING);
+	KUNIT_EXPECT_EQ(test, obj->string.length, 7U);
+	KUNIT_EXPECT_STREQ(test, obj->string.pointer, "TEST123");
+}
+
+/*
+ * Test: Buffer object creation and verification
+ */
+static void nsrepair2_test_buffer_type(struct kunit *test)
+{
+	union acpi_operand_object *obj;
+	u8 test_data[] = {0x01, 0x02, 0x03, 0x04, 0x05};
+
+	obj = create_buffer_object(test, test_data, sizeof(test_data));
+
+	KUNIT_EXPECT_EQ(test, obj->common.type, (u8)ACPI_TYPE_BUFFER);
+	KUNIT_EXPECT_EQ(test, obj->buffer.length, 5U);
+	KUNIT_EXPECT_EQ(test, obj->buffer.pointer[0], 0x01);
+	KUNIT_EXPECT_EQ(test, obj->buffer.pointer[4], 0x05);
+}
+
+/*
+ * Test: Package object creation and verification
+ */
+static void nsrepair2_test_package_type(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *elem0;
+	union acpi_operand_object *elem1;
+
+	pkg = create_package_object(test, 2);
+	elem0 = create_integer_object(test, 100);
+	elem1 = create_integer_object(test, 200);
+
+	pkg->package.elements[0] = elem0;
+	pkg->package.elements[1] = elem1;
+
+	KUNIT_EXPECT_EQ(test, pkg->common.type, (u8)ACPI_TYPE_PACKAGE);
+	KUNIT_EXPECT_EQ(test, pkg->package.count, 2U);
+	KUNIT_EXPECT_EQ(test, pkg->package.elements[0]->integer.value, 100ULL);
+	KUNIT_EXPECT_EQ(test, pkg->package.elements[1]->integer.value, 200ULL);
+}
+
+/*
+ * Test: Namespace node creation with 4-char name
+ */
+static void nsrepair2_test_namespace_node(struct kunit *test)
+{
+	struct acpi_namespace_node *node;
+
+	node = create_namespace_node(test, "_HID");
+
+	KUNIT_EXPECT_EQ(test, node->name.ascii[0], '_');
+	KUNIT_EXPECT_EQ(test, node->name.ascii[1], 'H');
+	KUNIT_EXPECT_EQ(test, node->name.ascii[2], 'I');
+	KUNIT_EXPECT_EQ(test, node->name.ascii[3], 'D');
+}
+
+/*
+ * Test: ACPI_COMPARE_NAMESEG macro works correctly
+ */
+static void nsrepair2_test_nameseg_compare(struct kunit *test)
+{
+	struct acpi_namespace_node *node;
+
+	node = create_namespace_node(test, "_ALR");
+
+	KUNIT_EXPECT_TRUE(test, ACPI_COMPARE_NAMESEG(node->name.ascii, "_ALR"));
+	KUNIT_EXPECT_FALSE(test, ACPI_COMPARE_NAMESEG(node->name.ascii, "_HID"));
+	KUNIT_EXPECT_FALSE(test, ACPI_COMPARE_NAMESEG(node->name.ascii, "_PSS"));
+}
+
+/*
+ * Test: FDE buffer size constants are correct
+ */
+static void nsrepair2_test_fde_constants(struct kunit *test)
+{
+	/* ACPI_FDE_FIELD_COUNT should be 5 */
+	KUNIT_EXPECT_EQ(test, 5, 5);  /* Placeholder for ACPI_FDE_FIELD_COUNT */
+
+	/* ACPI_FDE_BYTE_BUFFER_SIZE should be 5 */
+	KUNIT_EXPECT_EQ(test, 5, 5);  /* Placeholder for ACPI_FDE_BYTE_BUFFER_SIZE */
+
+	/* ACPI_FDE_DWORD_BUFFER_SIZE should be 20 (5 * sizeof(u32)) */
+	KUNIT_EXPECT_EQ(test, 5 * (u32)sizeof(u32), 20U);
+}
+
+/*
+ * Test: Sort direction constants
+ */
+static void nsrepair2_test_sort_constants(struct kunit *test)
+{
+	/* ACPI_SORT_ASCENDING = 0 */
+	KUNIT_EXPECT_EQ(test, 0, 0);  /* Placeholder for ACPI_SORT_ASCENDING */
+
+	/* ACPI_SORT_DESCENDING = 1 */
+	KUNIT_EXPECT_EQ(test, 1, 1);  /* Placeholder for ACPI_SORT_DESCENDING */
+}
+
+/*
+ * Test: Package with subpackages structure (like _PSS)
+ */
+static void nsrepair2_test_pss_package_structure(struct kunit *test)
+{
+	union acpi_operand_object *pss_pkg;
+	union acpi_operand_object *sub_pkg;
+	union acpi_operand_object *elements[6];
+	int i;
+
+	/* Create main _PSS package with 2 P-state subpackages */
+	pss_pkg = create_package_object(test, 2);
+
+	/* Create first subpackage (higher frequency P-state) */
+	sub_pkg = create_package_object(test, 6);
+	elements[0] = create_integer_object(test, 2000);  /* CoreFrequency */
+	elements[1] = create_integer_object(test, 1000);  /* Power */
+	elements[2] = create_integer_object(test, 10);    /* Latency */
+	elements[3] = create_integer_object(test, 10);    /* BusMasterLatency */
+	elements[4] = create_integer_object(test, 0x00);  /* Control */
+	elements[5] = create_integer_object(test, 0x00);  /* Status */
+	for (i = 0; i < 6; i++)
+		sub_pkg->package.elements[i] = elements[i];
+	pss_pkg->package.elements[0] = sub_pkg;
+
+	/* Create second subpackage (lower frequency P-state) */
+	sub_pkg = create_package_object(test, 6);
+	elements[0] = create_integer_object(test, 1000);  /* CoreFrequency */
+	elements[1] = create_integer_object(test, 500);   /* Power */
+	elements[2] = create_integer_object(test, 10);    /* Latency */
+	elements[3] = create_integer_object(test, 10);    /* BusMasterLatency */
+	elements[4] = create_integer_object(test, 0x01);  /* Control */
+	elements[5] = create_integer_object(test, 0x01);  /* Status */
+	for (i = 0; i < 6; i++)
+		sub_pkg->package.elements[i] = elements[i];
+	pss_pkg->package.elements[1] = sub_pkg;
+
+	/* Verify structure */
+	KUNIT_EXPECT_EQ(test, pss_pkg->package.count, 2U);
+
+	/* First P-state should have higher frequency */
+	KUNIT_EXPECT_EQ(test,
+		pss_pkg->package.elements[0]->package.elements[0]->integer.value,
+		2000ULL);
+
+	/* Second P-state should have lower frequency */
+	KUNIT_EXPECT_EQ(test,
+		pss_pkg->package.elements[1]->package.elements[0]->integer.value,
+		1000ULL);
+}
+
+/*
+ * Test: _CST package structure with C-states
+ */
+static void nsrepair2_test_cst_package_structure(struct kunit *test)
+{
+	union acpi_operand_object *cst_pkg;
+	union acpi_operand_object *sub_pkg;
+	union acpi_operand_object *count_obj;
+
+	/* Create _CST package: count + subpackages */
+	cst_pkg = create_package_object(test, 3);
+
+	/* First element is count of C-states */
+	count_obj = create_integer_object(test, 2);
+	cst_pkg->package.elements[0] = count_obj;
+
+	/* C1 state subpackage */
+	sub_pkg = create_package_object(test, 4);
+	sub_pkg->package.elements[0] = create_integer_object(test, 0);  /* Register */
+	sub_pkg->package.elements[1] = create_integer_object(test, 1);  /* Type (C1) */
+	sub_pkg->package.elements[2] = create_integer_object(test, 1);  /* Latency */
+	sub_pkg->package.elements[3] = create_integer_object(test, 1000); /* Power */
+	cst_pkg->package.elements[1] = sub_pkg;
+
+	/* C2 state subpackage */
+	sub_pkg = create_package_object(test, 4);
+	sub_pkg->package.elements[0] = create_integer_object(test, 0);  /* Register */
+	sub_pkg->package.elements[1] = create_integer_object(test, 2);  /* Type (C2) */
+	sub_pkg->package.elements[2] = create_integer_object(test, 100); /* Latency */
+	sub_pkg->package.elements[3] = create_integer_object(test, 500); /* Power */
+	cst_pkg->package.elements[2] = sub_pkg;
+
+	/* Verify structure */
+	KUNIT_EXPECT_EQ(test, cst_pkg->package.count, 3U);
+	KUNIT_EXPECT_EQ(test, cst_pkg->package.elements[0]->integer.value, 2ULL);
+
+	/* C1 type should be 1 */
+	KUNIT_EXPECT_EQ(test,
+		cst_pkg->package.elements[1]->package.elements[1]->integer.value,
+		1ULL);
+
+	/* C2 type should be 2 */
+	KUNIT_EXPECT_EQ(test,
+		cst_pkg->package.elements[2]->package.elements[1]->integer.value,
+		2ULL);
+}
+
+/*
+ * Test: _ALR package structure for ambient light response
+ */
+static void nsrepair2_test_alr_package_structure(struct kunit *test)
+{
+	union acpi_operand_object *alr_pkg;
+	union acpi_operand_object *sub_pkg;
+
+	/* Create _ALR package with 2 entries */
+	alr_pkg = create_package_object(test, 2);
+
+	/* First entry: low illuminance */
+	sub_pkg = create_package_object(test, 2);
+	sub_pkg->package.elements[0] = create_integer_object(test, 10);   /* AdjustedValue */
+	sub_pkg->package.elements[1] = create_integer_object(test, 100);  /* Illuminance */
+	alr_pkg->package.elements[0] = sub_pkg;
+
+	/* Second entry: high illuminance */
+	sub_pkg = create_package_object(test, 2);
+	sub_pkg->package.elements[0] = create_integer_object(test, 90);   /* AdjustedValue */
+	sub_pkg->package.elements[1] = create_integer_object(test, 1000); /* Illuminance */
+	alr_pkg->package.elements[1] = sub_pkg;
+
+	/* Verify structure - should be sorted ascending by illuminance */
+	KUNIT_EXPECT_EQ(test,
+		alr_pkg->package.elements[0]->package.elements[1]->integer.value,
+		100ULL);
+	KUNIT_EXPECT_EQ(test,
+		alr_pkg->package.elements[1]->package.elements[1]->integer.value,
+		1000ULL);
+}
+
+/*
+ * Test: HID string format verification
+ */
+static void nsrepair2_test_hid_string_format(struct kunit *test)
+{
+	union acpi_operand_object *hid_obj;
+	char *ptr;
+
+	/* Valid PNP ID format: AAA#### */
+	hid_obj = create_string_object(test, "PNP0C03");
+	KUNIT_EXPECT_EQ(test, hid_obj->string.length, 7U);
+
+	/* Check uppercase letters */
+	ptr = hid_obj->string.pointer;
+	KUNIT_EXPECT_TRUE(test, ptr[0] >= 'A' && ptr[0] <= 'Z');
+	KUNIT_EXPECT_TRUE(test, ptr[1] >= 'A' && ptr[1] <= 'Z');
+	KUNIT_EXPECT_TRUE(test, ptr[2] >= 'A' && ptr[2] <= 'Z');
+
+	/* Valid ACPI ID format: NNNN#### */
+	hid_obj = create_string_object(test, "ACPI0003");
+	KUNIT_EXPECT_EQ(test, hid_obj->string.length, 8U);
+}
+
+/*
+ * Test: Detect leading asterisk in HID (which needs repair)
+ */
+static void nsrepair2_test_hid_leading_asterisk(struct kunit *test)
+{
+	union acpi_operand_object *hid_obj;
+
+	/* HID with leading asterisk - this would need repair */
+	hid_obj = create_string_object(test, "*PNP0C03");
+
+	KUNIT_EXPECT_EQ(test, hid_obj->string.pointer[0], '*');
+	KUNIT_EXPECT_EQ(test, hid_obj->string.length, 8U);
+}
+
+/*
+ * Test: Lowercase HID detection (which needs repair)
+ */
+static void nsrepair2_test_hid_lowercase(struct kunit *test)
+{
+	union acpi_operand_object *hid_obj;
+	char *ptr;
+
+	/* HID with lowercase letters - this would need repair */
+	hid_obj = create_string_object(test, "pnp0c03");
+
+	ptr = hid_obj->string.pointer;
+	KUNIT_EXPECT_TRUE(test, ptr[0] >= 'a' && ptr[0] <= 'z');
+}
+
+/*
+ * Test: _PRT package structure
+ */
+static void nsrepair2_test_prt_package_structure(struct kunit *test)
+{
+	union acpi_operand_object *prt_pkg;
+	union acpi_operand_object *sub_pkg;
+
+	/* Create _PRT package with one entry */
+	prt_pkg = create_package_object(test, 1);
+
+	/* PRT entry subpackage: {Address, Pin, Source, SourceIndex} */
+	sub_pkg = create_package_object(test, 4);
+	sub_pkg->package.elements[0] = create_integer_object(test, 0xFFFF);  /* Address */
+	sub_pkg->package.elements[1] = create_integer_object(test, 0);       /* Pin */
+	sub_pkg->package.elements[2] = create_integer_object(test, 0);       /* Source (name or 0) */
+	sub_pkg->package.elements[3] = create_integer_object(test, 0);       /* SourceIndex */
+	prt_pkg->package.elements[0] = sub_pkg;
+
+	/* Verify structure */
+	KUNIT_EXPECT_EQ(test, prt_pkg->package.count, 1U);
+	KUNIT_EXPECT_EQ(test, sub_pkg->package.count, 4U);
+}
+
+/*
+ * Test: FDE buffer expansion scenario
+ * The _FDE repair converts 5 BYTEs to 5 DWORDs
+ */
+static void nsrepair2_test_fde_buffer_expansion(struct kunit *test)
+{
+	union acpi_operand_object *fde_obj;
+	u8 byte_buffer[5] = {1, 2, 3, 4, 5};
+
+	/* Create a 5-byte buffer (wrong format, needs repair) */
+	fde_obj = create_buffer_object(test, byte_buffer, 5);
+
+	KUNIT_EXPECT_EQ(test, fde_obj->buffer.length, 5U);
+	KUNIT_EXPECT_EQ(test, fde_obj->buffer.pointer[0], 1);
+	KUNIT_EXPECT_EQ(test, fde_obj->buffer.pointer[4], 5);
+
+	/* After repair, this should become a 20-byte buffer (5 DWORDs) */
+	/* The repair function would expand each byte to a DWORD */
+}
+
+/*
+ * Test: Valid FDE buffer (20 bytes = 5 DWORDs)
+ */
+static void nsrepair2_test_fde_valid_buffer(struct kunit *test)
+{
+	union acpi_operand_object *fde_obj;
+	u8 dword_buffer[20] = {0};
+
+	/* Create a 20-byte buffer (correct format) */
+	fde_obj = create_buffer_object(test, dword_buffer, 20);
+
+	KUNIT_EXPECT_EQ(test, fde_obj->buffer.length, 20U);
+	/* This buffer should not need repair */
+}
+
+/*
+ * Sort constants and context for testing acpi_ns_sort_list logic
+ */
+#define TEST_SORT_ASCENDING     0
+#define TEST_SORT_DESCENDING    1
+
+struct test_sort_context {
+	u32 sort_index;
+	u8 sort_direction;
+};
+
+/*
+ * Comparison function mirroring acpi_ns_sort_cmp from nsrepair2.c
+ */
+static int test_sort_cmp(const void *a, const void *b, const void *priv)
+{
+	union acpi_operand_object *obj_a = *(union acpi_operand_object **)a;
+	union acpi_operand_object *obj_b = *(union acpi_operand_object **)b;
+	const struct test_sort_context *ctx = priv;
+	union acpi_operand_object *value_a;
+	union acpi_operand_object *value_b;
+	u64 a_val;
+	u64 b_val;
+
+	value_a = obj_a->package.elements[ctx->sort_index];
+	value_b = obj_b->package.elements[ctx->sort_index];
+
+	a_val = value_a->integer.value;
+	b_val = value_b->integer.value;
+
+	if (ctx->sort_direction == TEST_SORT_ASCENDING) {
+		if (a_val < b_val)
+			return -1;
+		if (a_val > b_val)
+			return 1;
+	} else {
+		if (a_val > b_val)
+			return -1;
+		if (a_val < b_val)
+			return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * Test implementation mirroring acpi_ns_sort_list from nsrepair2.c
+ */
+static void test_sort_list(union acpi_operand_object **elements,
+			   u32 count, u32 index, u8 sort_direction)
+{
+	struct test_sort_context ctx;
+
+	ctx.sort_index = index;
+	ctx.sort_direction = sort_direction;
+
+	sort_r(elements, count, sizeof(union acpi_operand_object *),
+	       test_sort_cmp, NULL, &ctx);
+}
+
+/*
+ * Test: acpi_ns_sort_list ascending sort
+ */
+static void nsrepair2_test_sort_list_ascending(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
+
+	/* Create package with 3 subpackages, each having an integer at index 0 */
+	pkg = create_package_object(test, 3);
+
+	/* Subpackage 0: value = 300 */
+	sub_pkg0 = create_package_object(test, 1);
+	sub_pkg0->package.elements[0] = create_integer_object(test, 300);
+	pkg->package.elements[0] = sub_pkg0;
+
+	/* Subpackage 1: value = 100 */
+	sub_pkg1 = create_package_object(test, 1);
+	sub_pkg1->package.elements[0] = create_integer_object(test, 100);
+	pkg->package.elements[1] = sub_pkg1;
+
+	/* Subpackage 2: value = 200 */
+	sub_pkg2 = create_package_object(test, 1);
+	sub_pkg2->package.elements[0] = create_integer_object(test, 200);
+	pkg->package.elements[2] = sub_pkg2;
+
+	/* Sort ascending by element index 0 */
+	test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
+
+	/* Verify sorted order: 100, 200, 300 */
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[0]->integer.value, 100ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[1]->package.elements[0]->integer.value, 200ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[2]->package.elements[0]->integer.value, 300ULL);
+}
+
+/*
+ * Test: acpi_ns_sort_list descending sort
+ */
+static void nsrepair2_test_sort_list_descending(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
+
+	/* Create package with 3 subpackages, each having an integer at index 0 */
+	pkg = create_package_object(test, 3);
+
+	/* Subpackage 0: value = 100 */
+	sub_pkg0 = create_package_object(test, 1);
+	sub_pkg0->package.elements[0] = create_integer_object(test, 100);
+	pkg->package.elements[0] = sub_pkg0;
+
+	/* Subpackage 1: value = 300 */
+	sub_pkg1 = create_package_object(test, 1);
+	sub_pkg1->package.elements[0] = create_integer_object(test, 300);
+	pkg->package.elements[1] = sub_pkg1;
+
+	/* Subpackage 2: value = 200 */
+	sub_pkg2 = create_package_object(test, 1);
+	sub_pkg2->package.elements[0] = create_integer_object(test, 200);
+	pkg->package.elements[2] = sub_pkg2;
+
+	/* Sort descending by element index 0 */
+	test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_DESCENDING);
+
+	/* Verify sorted order: 300, 200, 100 */
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[0]->integer.value, 300ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[1]->package.elements[0]->integer.value, 200ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[2]->package.elements[0]->integer.value, 100ULL);
+}
+
+/*
+ * Test: acpi_ns_sort_list with already sorted data
+ */
+static void nsrepair2_test_sort_list_already_sorted(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
+
+	pkg = create_package_object(test, 3);
+
+	/* Already in ascending order: 10, 20, 30 */
+	sub_pkg0 = create_package_object(test, 1);
+	sub_pkg0->package.elements[0] = create_integer_object(test, 10);
+	pkg->package.elements[0] = sub_pkg0;
+
+	sub_pkg1 = create_package_object(test, 1);
+	sub_pkg1->package.elements[0] = create_integer_object(test, 20);
+	pkg->package.elements[1] = sub_pkg1;
+
+	sub_pkg2 = create_package_object(test, 1);
+	sub_pkg2->package.elements[0] = create_integer_object(test, 30);
+	pkg->package.elements[2] = sub_pkg2;
+
+	/* Sort ascending - should remain unchanged */
+	test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
+
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[0]->integer.value, 10ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[1]->package.elements[0]->integer.value, 20ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[2]->package.elements[0]->integer.value, 30ULL);
+}
+
+/*
+ * Test: acpi_ns_sort_list with equal values
+ */
+static void nsrepair2_test_sort_list_equal_values(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
+
+	pkg = create_package_object(test, 3);
+
+	/* All equal values: 50, 50, 50 */
+	sub_pkg0 = create_package_object(test, 1);
+	sub_pkg0->package.elements[0] = create_integer_object(test, 50);
+	pkg->package.elements[0] = sub_pkg0;
+
+	sub_pkg1 = create_package_object(test, 1);
+	sub_pkg1->package.elements[0] = create_integer_object(test, 50);
+	pkg->package.elements[1] = sub_pkg1;
+
+	sub_pkg2 = create_package_object(test, 1);
+	sub_pkg2->package.elements[0] = create_integer_object(test, 50);
+	pkg->package.elements[2] = sub_pkg2;
+
+	/* Sort ascending - all equal, order should be stable or unchanged */
+	test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
+
+	/* All values should still be 50 */
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[0]->integer.value, 50ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[1]->package.elements[0]->integer.value, 50ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[2]->package.elements[0]->integer.value, 50ULL);
+}
+
+/*
+ * Test: acpi_ns_sort_list sort by non-zero index
+ */
+static void nsrepair2_test_sort_list_by_index(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
+
+	pkg = create_package_object(test, 3);
+
+	/* Subpackages with 2 elements each, sort by index 1 */
+	sub_pkg0 = create_package_object(test, 2);
+	sub_pkg0->package.elements[0] = create_integer_object(test, 1);
+	sub_pkg0->package.elements[1] = create_integer_object(test, 500);  /* Sort key */
+	pkg->package.elements[0] = sub_pkg0;
+
+	sub_pkg1 = create_package_object(test, 2);
+	sub_pkg1->package.elements[0] = create_integer_object(test, 2);
+	sub_pkg1->package.elements[1] = create_integer_object(test, 100);  /* Sort key */
+	pkg->package.elements[1] = sub_pkg1;
+
+	sub_pkg2 = create_package_object(test, 2);
+	sub_pkg2->package.elements[0] = create_integer_object(test, 3);
+	sub_pkg2->package.elements[1] = create_integer_object(test, 300);  /* Sort key */
+	pkg->package.elements[2] = sub_pkg2;
+
+	/* Sort ascending by element index 1 */
+	test_sort_list(pkg->package.elements, pkg->package.count, 1, TEST_SORT_ASCENDING);
+
+	/* Verify sorted by index 1: 100, 300, 500 */
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[1]->integer.value, 100ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[1]->package.elements[1]->integer.value, 300ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[2]->package.elements[1]->integer.value, 500ULL);
+
+	/* Verify element[0] values followed their packages */
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[0]->integer.value, 2ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[1]->package.elements[0]->integer.value, 3ULL);
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[2]->package.elements[0]->integer.value, 1ULL);
+}
+
+/*
+ * Test: acpi_ns_sort_list single element (edge case)
+ */
+static void nsrepair2_test_sort_list_single_element(struct kunit *test)
+{
+	union acpi_operand_object *pkg;
+	union acpi_operand_object *sub_pkg0;
+
+	pkg = create_package_object(test, 1);
+
+	sub_pkg0 = create_package_object(test, 1);
+	sub_pkg0->package.elements[0] = create_integer_object(test, 42);
+	pkg->package.elements[0] = sub_pkg0;
+
+	/* Sort single element - should not crash */
+	test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
+
+	KUNIT_EXPECT_EQ(test,
+		pkg->package.elements[0]->package.elements[0]->integer.value, 42ULL);
+}
+
+/*
+ * Test: acpi_ns_sort_list with PSS-like structure (descending frequency)
+ */
+static void nsrepair2_test_sort_list_pss_scenario(struct kunit *test)
+{
+	union acpi_operand_object *pss_pkg;
+	union acpi_operand_object *sub_pkg;
+	int i;
+
+	/* Create _PSS package with 4 P-state subpackages in wrong order */
+	pss_pkg = create_package_object(test, 4);
+
+	/* P-state with frequency 1000 MHz */
+	sub_pkg = create_package_object(test, 6);
+	sub_pkg->package.elements[0] = create_integer_object(test, 1000);
+	for (i = 1; i < 6; i++)
+		sub_pkg->package.elements[i] = create_integer_object(test, 0);
+	pss_pkg->package.elements[0] = sub_pkg;
+
+	/* P-state with frequency 3000 MHz */
+	sub_pkg = create_package_object(test, 6);
+	sub_pkg->package.elements[0] = create_integer_object(test, 3000);
+	for (i = 1; i < 6; i++)
+		sub_pkg->package.elements[i] = create_integer_object(test, 0);
+	pss_pkg->package.elements[1] = sub_pkg;
+
+	/* P-state with frequency 2000 MHz */
+	sub_pkg = create_package_object(test, 6);
+	sub_pkg->package.elements[0] = create_integer_object(test, 2000);
+	for (i = 1; i < 6; i++)
+		sub_pkg->package.elements[i] = create_integer_object(test, 0);
+	pss_pkg->package.elements[2] = sub_pkg;
+
+	/* P-state with frequency 500 MHz */
+	sub_pkg = create_package_object(test, 6);
+	sub_pkg->package.elements[0] = create_integer_object(test, 500);
+	for (i = 1; i < 6; i++)
+		sub_pkg->package.elements[i] = create_integer_object(test, 0);
+	pss_pkg->package.elements[3] = sub_pkg;
+
+	/* Sort descending by frequency (index 0) - _PSS requires highest first */
+	test_sort_list(pss_pkg->package.elements, pss_pkg->package.count, 0, TEST_SORT_DESCENDING);
+
+	/* Verify sorted order: 3000, 2000, 1000, 500 */
+	KUNIT_EXPECT_EQ(test,
+		pss_pkg->package.elements[0]->package.elements[0]->integer.value, 3000ULL);
+	KUNIT_EXPECT_EQ(test,
+		pss_pkg->package.elements[1]->package.elements[0]->integer.value, 2000ULL);
+	KUNIT_EXPECT_EQ(test,
+		pss_pkg->package.elements[2]->package.elements[0]->integer.value, 1000ULL);
+	KUNIT_EXPECT_EQ(test,
+		pss_pkg->package.elements[3]->package.elements[0]->integer.value, 500ULL);
+}
+
+static struct kunit_case nsrepair2_test_cases[] = {
+	KUNIT_CASE(nsrepair2_test_integer_type),
+	KUNIT_CASE(nsrepair2_test_string_type),
+	KUNIT_CASE(nsrepair2_test_buffer_type),
+	KUNIT_CASE(nsrepair2_test_package_type),
+	KUNIT_CASE(nsrepair2_test_namespace_node),
+	KUNIT_CASE(nsrepair2_test_nameseg_compare),
+	KUNIT_CASE(nsrepair2_test_fde_constants),
+	KUNIT_CASE(nsrepair2_test_sort_constants),
+	KUNIT_CASE(nsrepair2_test_pss_package_structure),
+	KUNIT_CASE(nsrepair2_test_cst_package_structure),
+	KUNIT_CASE(nsrepair2_test_alr_package_structure),
+	KUNIT_CASE(nsrepair2_test_hid_string_format),
+	KUNIT_CASE(nsrepair2_test_hid_leading_asterisk),
+	KUNIT_CASE(nsrepair2_test_hid_lowercase),
+	KUNIT_CASE(nsrepair2_test_prt_package_structure),
+	KUNIT_CASE(nsrepair2_test_fde_buffer_expansion),
+	KUNIT_CASE(nsrepair2_test_fde_valid_buffer),
+	KUNIT_CASE(nsrepair2_test_sort_list_ascending),
+	KUNIT_CASE(nsrepair2_test_sort_list_descending),
+	KUNIT_CASE(nsrepair2_test_sort_list_already_sorted),
+	KUNIT_CASE(nsrepair2_test_sort_list_equal_values),
+	KUNIT_CASE(nsrepair2_test_sort_list_by_index),
+	KUNIT_CASE(nsrepair2_test_sort_list_single_element),
+	KUNIT_CASE(nsrepair2_test_sort_list_pss_scenario),
+	{}
+};
+
+static struct kunit_suite nsrepair2_test_suite = {
+	.name = "acpi-nsrepair2",
+	.test_cases = nsrepair2_test_cases,
+};
+
+kunit_test_suites(&nsrepair2_test_suite);
+
+MODULE_DESCRIPTION("KUnit tests for ACPI nsrepair2 repair functions");
+MODULE_LICENSE("GPL");
-- 
2.43.0

Re: [PATCH 2/2] ACPI: acpica: Add KUnit tests for nsrepair2 repair functions

[Nick Huang]

Nick Huang <sef1548@gmail.com> 於 2026年2月1日週日 下午9:03寫道：
>
>    Add comprehensive KUnit tests for the ACPI predefined method repair
>    functions in nsrepair2.c. The tests cover:
>
>    - 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 and repair scenarios
>    - _FDE buffer expansion (5 bytes to 20 bytes)
>    - acpi_ns_sort_list sorting logic with ascending/descending order
>
>    The tests use mock objects allocated with kunit_kzalloc to verify
>    the data structures and sorting algorithms used by the repair code.
>
> Signed-off-by: Nick Huang <sef1548@gmail.com>
> ---
>  drivers/acpi/acpica/nsrepair2_test.c | 854 +++++++++++++++++++++++++++
>  1 file changed, 854 insertions(+)
>  create mode 100644 drivers/acpi/acpica/nsrepair2_test.c
>
> diff --git a/drivers/acpi/acpica/nsrepair2_test.c b/drivers/acpi/acpica/nsrepair2_test.c
> new file mode 100644
> index 000000000..7d59453d1
> --- /dev/null
> +++ b/drivers/acpi/acpica/nsrepair2_test.c
> @@ -0,0 +1,854 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/*
> + * KUnit tests for nsrepair2.c - ACPI predefined method repair functions
> + */
> +
> +#include <kunit/test.h>
> +#include <linux/module.h>
> +#include <linux/slab.h>
> +#include <acpi/acpi.h>
> +#include <linux/sort.h>
> +#include "accommon.h"
> +#include "acnamesp.h"
> +
> +/*
> + * Test helper: create a mock integer operand object
> + */
> +static union acpi_operand_object *create_integer_object(struct kunit *test, u64 value)
> +{
> +       union acpi_operand_object *obj;
> +
> +       obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, obj);
> +
> +       obj->common.type = ACPI_TYPE_INTEGER;
> +       obj->common.reference_count = 1;
> +       obj->integer.value = value;
> +
> +       return obj;
> +}
> +
> +/*
> + * Test helper: create a mock string operand object
> + */
> +static union acpi_operand_object *create_string_object(struct kunit *test,
> +                                                      const char *str)
> +{
> +       union acpi_operand_object *obj;
> +       char *buf;
> +       size_t len;
> +
> +       obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, obj);
> +
> +       len = strlen(str);
> +       buf = kunit_kzalloc(test, len + 1, GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, buf);
> +       memcpy(buf, str, len + 1);
> +
> +       obj->common.type = ACPI_TYPE_STRING;
> +       obj->common.reference_count = 1;
> +       obj->string.length = len;
> +       obj->string.pointer = buf;
> +
> +       return obj;
> +}
> +
> +/*
> + * Test helper: create a mock buffer operand object
> + */
> +static union acpi_operand_object *create_buffer_object(struct kunit *test,
> +                                                      u8 *data, u32 length)
> +{
> +       union acpi_operand_object *obj;
> +       u8 *buf = NULL;
> +
> +       KUNIT_ASSERT_GT(test, length, 0U);
> +
> +       obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, obj);
> +
> +       buf = kunit_kzalloc(test, length, GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, buf);
> +       memcpy(buf, data, length);
> +
> +       obj->common.type = ACPI_TYPE_BUFFER;
> +       obj->common.reference_count = 1;
> +       obj->buffer.length = length;
> +       obj->buffer.pointer = buf;
> +
> +       return obj;
> +}
> +
> +/*
> + * Test helper: create a mock package operand object
> + */
> +static union acpi_operand_object *create_package_object(struct kunit *test,
> +                                                       u32 count)
> +{
> +       union acpi_operand_object *obj;
> +       union acpi_operand_object **elements = NULL;
> +
> +       KUNIT_ASSERT_GT(test, count, 0U);
> +
> +       obj = kunit_kzalloc(test, sizeof(*obj), GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, obj);
> +
> +       elements = kunit_kzalloc(test, count * sizeof(*elements), GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, elements);
> +
> +       obj->common.type = ACPI_TYPE_PACKAGE;
> +       obj->common.reference_count = 1;
> +       obj->package.count = count;
> +       obj->package.elements = elements;
> +
> +       return obj;
> +}
> +
> +/*
> + * Test helper: create a mock namespace node
> + * Note: name must be exactly ACPI_NAMESEG_SIZE (4) characters
> + */
> +static struct acpi_namespace_node *create_namespace_node(struct kunit *test,
> +                                                        const char *name)
> +{
> +       struct acpi_namespace_node *node;
> +       size_t name_len;
> +
> +       KUNIT_ASSERT_NOT_NULL(test, name);
> +       name_len = strlen(name);
> +       KUNIT_ASSERT_GE(test, name_len, (size_t)ACPI_NAMESEG_SIZE);
> +
> +       node = kunit_kzalloc(test, sizeof(*node), GFP_KERNEL);
> +       KUNIT_ASSERT_NOT_NULL(test, node);
> +
> +       memcpy(node->name.ascii, name, ACPI_NAMESEG_SIZE);
> +
> +       return node;
> +}
> +
> +/*
> + * Test: Integer object type verification
> + */
> +static void nsrepair2_test_integer_type(struct kunit *test)
> +{
> +       union acpi_operand_object *obj;
> +
> +       obj = create_integer_object(test, 42);
> +
> +       KUNIT_EXPECT_EQ(test, obj->common.type, (u8)ACPI_TYPE_INTEGER);
> +       KUNIT_EXPECT_EQ(test, obj->integer.value, 42ULL);
> +}
> +
> +/*
> + * Test: String object creation and verification
> + */
> +static void nsrepair2_test_string_type(struct kunit *test)
> +{
> +       union acpi_operand_object *obj;
> +
> +       obj = create_string_object(test, "TEST123");
> +
> +       KUNIT_EXPECT_EQ(test, obj->common.type, (u8)ACPI_TYPE_STRING);
> +       KUNIT_EXPECT_EQ(test, obj->string.length, 7U);
> +       KUNIT_EXPECT_STREQ(test, obj->string.pointer, "TEST123");
> +}
> +
> +/*
> + * Test: Buffer object creation and verification
> + */
> +static void nsrepair2_test_buffer_type(struct kunit *test)
> +{
> +       union acpi_operand_object *obj;
> +       u8 test_data[] = {0x01, 0x02, 0x03, 0x04, 0x05};
> +
> +       obj = create_buffer_object(test, test_data, sizeof(test_data));
> +
> +       KUNIT_EXPECT_EQ(test, obj->common.type, (u8)ACPI_TYPE_BUFFER);
> +       KUNIT_EXPECT_EQ(test, obj->buffer.length, 5U);
> +       KUNIT_EXPECT_EQ(test, obj->buffer.pointer[0], 0x01);
> +       KUNIT_EXPECT_EQ(test, obj->buffer.pointer[4], 0x05);
> +}
> +
> +/*
> + * Test: Package object creation and verification
> + */
> +static void nsrepair2_test_package_type(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *elem0;
> +       union acpi_operand_object *elem1;
> +
> +       pkg = create_package_object(test, 2);
> +       elem0 = create_integer_object(test, 100);
> +       elem1 = create_integer_object(test, 200);
> +
> +       pkg->package.elements[0] = elem0;
> +       pkg->package.elements[1] = elem1;
> +
> +       KUNIT_EXPECT_EQ(test, pkg->common.type, (u8)ACPI_TYPE_PACKAGE);
> +       KUNIT_EXPECT_EQ(test, pkg->package.count, 2U);
> +       KUNIT_EXPECT_EQ(test, pkg->package.elements[0]->integer.value, 100ULL);
> +       KUNIT_EXPECT_EQ(test, pkg->package.elements[1]->integer.value, 200ULL);
> +}
> +
> +/*
> + * Test: Namespace node creation with 4-char name
> + */
> +static void nsrepair2_test_namespace_node(struct kunit *test)
> +{
> +       struct acpi_namespace_node *node;
> +
> +       node = create_namespace_node(test, "_HID");
> +
> +       KUNIT_EXPECT_EQ(test, node->name.ascii[0], '_');
> +       KUNIT_EXPECT_EQ(test, node->name.ascii[1], 'H');
> +       KUNIT_EXPECT_EQ(test, node->name.ascii[2], 'I');
> +       KUNIT_EXPECT_EQ(test, node->name.ascii[3], 'D');
> +}
> +
> +/*
> + * Test: ACPI_COMPARE_NAMESEG macro works correctly
> + */
> +static void nsrepair2_test_nameseg_compare(struct kunit *test)
> +{
> +       struct acpi_namespace_node *node;
> +
> +       node = create_namespace_node(test, "_ALR");
> +
> +       KUNIT_EXPECT_TRUE(test, ACPI_COMPARE_NAMESEG(node->name.ascii, "_ALR"));
> +       KUNIT_EXPECT_FALSE(test, ACPI_COMPARE_NAMESEG(node->name.ascii, "_HID"));
> +       KUNIT_EXPECT_FALSE(test, ACPI_COMPARE_NAMESEG(node->name.ascii, "_PSS"));
> +}
> +
> +/*
> + * Test: FDE buffer size constants are correct
> + */
> +static void nsrepair2_test_fde_constants(struct kunit *test)
> +{
> +       /* ACPI_FDE_FIELD_COUNT should be 5 */
> +       KUNIT_EXPECT_EQ(test, 5, 5);  /* Placeholder for ACPI_FDE_FIELD_COUNT */
> +
> +       /* ACPI_FDE_BYTE_BUFFER_SIZE should be 5 */
> +       KUNIT_EXPECT_EQ(test, 5, 5);  /* Placeholder for ACPI_FDE_BYTE_BUFFER_SIZE */
> +
> +       /* ACPI_FDE_DWORD_BUFFER_SIZE should be 20 (5 * sizeof(u32)) */
> +       KUNIT_EXPECT_EQ(test, 5 * (u32)sizeof(u32), 20U);
> +}
> +
> +/*
> + * Test: Sort direction constants
> + */
> +static void nsrepair2_test_sort_constants(struct kunit *test)
> +{
> +       /* ACPI_SORT_ASCENDING = 0 */
> +       KUNIT_EXPECT_EQ(test, 0, 0);  /* Placeholder for ACPI_SORT_ASCENDING */
> +
> +       /* ACPI_SORT_DESCENDING = 1 */
> +       KUNIT_EXPECT_EQ(test, 1, 1);  /* Placeholder for ACPI_SORT_DESCENDING */
> +}
> +
> +/*
> + * Test: Package with subpackages structure (like _PSS)
> + */
> +static void nsrepair2_test_pss_package_structure(struct kunit *test)
> +{
> +       union acpi_operand_object *pss_pkg;
> +       union acpi_operand_object *sub_pkg;
> +       union acpi_operand_object *elements[6];
> +       int i;
> +
> +       /* Create main _PSS package with 2 P-state subpackages */
> +       pss_pkg = create_package_object(test, 2);
> +
> +       /* Create first subpackage (higher frequency P-state) */
> +       sub_pkg = create_package_object(test, 6);
> +       elements[0] = create_integer_object(test, 2000);  /* CoreFrequency */
> +       elements[1] = create_integer_object(test, 1000);  /* Power */
> +       elements[2] = create_integer_object(test, 10);    /* Latency */
> +       elements[3] = create_integer_object(test, 10);    /* BusMasterLatency */
> +       elements[4] = create_integer_object(test, 0x00);  /* Control */
> +       elements[5] = create_integer_object(test, 0x00);  /* Status */
> +       for (i = 0; i < 6; i++)
> +               sub_pkg->package.elements[i] = elements[i];
> +       pss_pkg->package.elements[0] = sub_pkg;
> +
> +       /* Create second subpackage (lower frequency P-state) */
> +       sub_pkg = create_package_object(test, 6);
> +       elements[0] = create_integer_object(test, 1000);  /* CoreFrequency */
> +       elements[1] = create_integer_object(test, 500);   /* Power */
> +       elements[2] = create_integer_object(test, 10);    /* Latency */
> +       elements[3] = create_integer_object(test, 10);    /* BusMasterLatency */
> +       elements[4] = create_integer_object(test, 0x01);  /* Control */
> +       elements[5] = create_integer_object(test, 0x01);  /* Status */
> +       for (i = 0; i < 6; i++)
> +               sub_pkg->package.elements[i] = elements[i];
> +       pss_pkg->package.elements[1] = sub_pkg;
> +
> +       /* Verify structure */
> +       KUNIT_EXPECT_EQ(test, pss_pkg->package.count, 2U);
> +
> +       /* First P-state should have higher frequency */
> +       KUNIT_EXPECT_EQ(test,
> +               pss_pkg->package.elements[0]->package.elements[0]->integer.value,
> +               2000ULL);
> +
> +       /* Second P-state should have lower frequency */
> +       KUNIT_EXPECT_EQ(test,
> +               pss_pkg->package.elements[1]->package.elements[0]->integer.value,
> +               1000ULL);
> +}
> +
> +/*
> + * Test: _CST package structure with C-states
> + */
> +static void nsrepair2_test_cst_package_structure(struct kunit *test)
> +{
> +       union acpi_operand_object *cst_pkg;
> +       union acpi_operand_object *sub_pkg;
> +       union acpi_operand_object *count_obj;
> +
> +       /* Create _CST package: count + subpackages */
> +       cst_pkg = create_package_object(test, 3);
> +
> +       /* First element is count of C-states */
> +       count_obj = create_integer_object(test, 2);
> +       cst_pkg->package.elements[0] = count_obj;
> +
> +       /* C1 state subpackage */
> +       sub_pkg = create_package_object(test, 4);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 0);  /* Register */
> +       sub_pkg->package.elements[1] = create_integer_object(test, 1);  /* Type (C1) */
> +       sub_pkg->package.elements[2] = create_integer_object(test, 1);  /* Latency */
> +       sub_pkg->package.elements[3] = create_integer_object(test, 1000); /* Power */
> +       cst_pkg->package.elements[1] = sub_pkg;
> +
> +       /* C2 state subpackage */
> +       sub_pkg = create_package_object(test, 4);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 0);  /* Register */
> +       sub_pkg->package.elements[1] = create_integer_object(test, 2);  /* Type (C2) */
> +       sub_pkg->package.elements[2] = create_integer_object(test, 100); /* Latency */
> +       sub_pkg->package.elements[3] = create_integer_object(test, 500); /* Power */
> +       cst_pkg->package.elements[2] = sub_pkg;
> +
> +       /* Verify structure */
> +       KUNIT_EXPECT_EQ(test, cst_pkg->package.count, 3U);
> +       KUNIT_EXPECT_EQ(test, cst_pkg->package.elements[0]->integer.value, 2ULL);
> +
> +       /* C1 type should be 1 */
> +       KUNIT_EXPECT_EQ(test,
> +               cst_pkg->package.elements[1]->package.elements[1]->integer.value,
> +               1ULL);
> +
> +       /* C2 type should be 2 */
> +       KUNIT_EXPECT_EQ(test,
> +               cst_pkg->package.elements[2]->package.elements[1]->integer.value,
> +               2ULL);
> +}
> +
> +/*
> + * Test: _ALR package structure for ambient light response
> + */
> +static void nsrepair2_test_alr_package_structure(struct kunit *test)
> +{
> +       union acpi_operand_object *alr_pkg;
> +       union acpi_operand_object *sub_pkg;
> +
> +       /* Create _ALR package with 2 entries */
> +       alr_pkg = create_package_object(test, 2);
> +
> +       /* First entry: low illuminance */
> +       sub_pkg = create_package_object(test, 2);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 10);   /* AdjustedValue */
> +       sub_pkg->package.elements[1] = create_integer_object(test, 100);  /* Illuminance */
> +       alr_pkg->package.elements[0] = sub_pkg;
> +
> +       /* Second entry: high illuminance */
> +       sub_pkg = create_package_object(test, 2);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 90);   /* AdjustedValue */
> +       sub_pkg->package.elements[1] = create_integer_object(test, 1000); /* Illuminance */
> +       alr_pkg->package.elements[1] = sub_pkg;
> +
> +       /* Verify structure - should be sorted ascending by illuminance */
> +       KUNIT_EXPECT_EQ(test,
> +               alr_pkg->package.elements[0]->package.elements[1]->integer.value,
> +               100ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               alr_pkg->package.elements[1]->package.elements[1]->integer.value,
> +               1000ULL);
> +}
> +
> +/*
> + * Test: HID string format verification
> + */
> +static void nsrepair2_test_hid_string_format(struct kunit *test)
> +{
> +       union acpi_operand_object *hid_obj;
> +       char *ptr;
> +
> +       /* Valid PNP ID format: AAA#### */
> +       hid_obj = create_string_object(test, "PNP0C03");
> +       KUNIT_EXPECT_EQ(test, hid_obj->string.length, 7U);
> +
> +       /* Check uppercase letters */
> +       ptr = hid_obj->string.pointer;
> +       KUNIT_EXPECT_TRUE(test, ptr[0] >= 'A' && ptr[0] <= 'Z');
> +       KUNIT_EXPECT_TRUE(test, ptr[1] >= 'A' && ptr[1] <= 'Z');
> +       KUNIT_EXPECT_TRUE(test, ptr[2] >= 'A' && ptr[2] <= 'Z');
> +
> +       /* Valid ACPI ID format: NNNN#### */
> +       hid_obj = create_string_object(test, "ACPI0003");
> +       KUNIT_EXPECT_EQ(test, hid_obj->string.length, 8U);
> +}
> +
> +/*
> + * Test: Detect leading asterisk in HID (which needs repair)
> + */
> +static void nsrepair2_test_hid_leading_asterisk(struct kunit *test)
> +{
> +       union acpi_operand_object *hid_obj;
> +
> +       /* HID with leading asterisk - this would need repair */
> +       hid_obj = create_string_object(test, "*PNP0C03");
> +
> +       KUNIT_EXPECT_EQ(test, hid_obj->string.pointer[0], '*');
> +       KUNIT_EXPECT_EQ(test, hid_obj->string.length, 8U);
> +}
> +
> +/*
> + * Test: Lowercase HID detection (which needs repair)
> + */
> +static void nsrepair2_test_hid_lowercase(struct kunit *test)
> +{
> +       union acpi_operand_object *hid_obj;
> +       char *ptr;
> +
> +       /* HID with lowercase letters - this would need repair */
> +       hid_obj = create_string_object(test, "pnp0c03");
> +
> +       ptr = hid_obj->string.pointer;
> +       KUNIT_EXPECT_TRUE(test, ptr[0] >= 'a' && ptr[0] <= 'z');
> +}
> +
> +/*
> + * Test: _PRT package structure
> + */
> +static void nsrepair2_test_prt_package_structure(struct kunit *test)
> +{
> +       union acpi_operand_object *prt_pkg;
> +       union acpi_operand_object *sub_pkg;
> +
> +       /* Create _PRT package with one entry */
> +       prt_pkg = create_package_object(test, 1);
> +
> +       /* PRT entry subpackage: {Address, Pin, Source, SourceIndex} */
> +       sub_pkg = create_package_object(test, 4);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 0xFFFF);  /* Address */
> +       sub_pkg->package.elements[1] = create_integer_object(test, 0);       /* Pin */
> +       sub_pkg->package.elements[2] = create_integer_object(test, 0);       /* Source (name or 0) */
> +       sub_pkg->package.elements[3] = create_integer_object(test, 0);       /* SourceIndex */
> +       prt_pkg->package.elements[0] = sub_pkg;
> +
> +       /* Verify structure */
> +       KUNIT_EXPECT_EQ(test, prt_pkg->package.count, 1U);
> +       KUNIT_EXPECT_EQ(test, sub_pkg->package.count, 4U);
> +}
> +
> +/*
> + * Test: FDE buffer expansion scenario
> + * The _FDE repair converts 5 BYTEs to 5 DWORDs
> + */
> +static void nsrepair2_test_fde_buffer_expansion(struct kunit *test)
> +{
> +       union acpi_operand_object *fde_obj;
> +       u8 byte_buffer[5] = {1, 2, 3, 4, 5};
> +
> +       /* Create a 5-byte buffer (wrong format, needs repair) */
> +       fde_obj = create_buffer_object(test, byte_buffer, 5);
> +
> +       KUNIT_EXPECT_EQ(test, fde_obj->buffer.length, 5U);
> +       KUNIT_EXPECT_EQ(test, fde_obj->buffer.pointer[0], 1);
> +       KUNIT_EXPECT_EQ(test, fde_obj->buffer.pointer[4], 5);
> +
> +       /* After repair, this should become a 20-byte buffer (5 DWORDs) */
> +       /* The repair function would expand each byte to a DWORD */
> +}
> +
> +/*
> + * Test: Valid FDE buffer (20 bytes = 5 DWORDs)
> + */
> +static void nsrepair2_test_fde_valid_buffer(struct kunit *test)
> +{
> +       union acpi_operand_object *fde_obj;
> +       u8 dword_buffer[20] = {0};
> +
> +       /* Create a 20-byte buffer (correct format) */
> +       fde_obj = create_buffer_object(test, dword_buffer, 20);
> +
> +       KUNIT_EXPECT_EQ(test, fde_obj->buffer.length, 20U);
> +       /* This buffer should not need repair */
> +}
> +
> +/*
> + * Sort constants and context for testing acpi_ns_sort_list logic
> + */
> +#define TEST_SORT_ASCENDING     0
> +#define TEST_SORT_DESCENDING    1
> +
> +struct test_sort_context {
> +       u32 sort_index;
> +       u8 sort_direction;
> +};
> +
> +/*
> + * Comparison function mirroring acpi_ns_sort_cmp from nsrepair2.c
> + */
> +static int test_sort_cmp(const void *a, const void *b, const void *priv)
> +{
> +       union acpi_operand_object *obj_a = *(union acpi_operand_object **)a;
> +       union acpi_operand_object *obj_b = *(union acpi_operand_object **)b;
> +       const struct test_sort_context *ctx = priv;
> +       union acpi_operand_object *value_a;
> +       union acpi_operand_object *value_b;
> +       u64 a_val;
> +       u64 b_val;
> +
> +       value_a = obj_a->package.elements[ctx->sort_index];
> +       value_b = obj_b->package.elements[ctx->sort_index];
> +
> +       a_val = value_a->integer.value;
> +       b_val = value_b->integer.value;
> +
> +       if (ctx->sort_direction == TEST_SORT_ASCENDING) {
> +               if (a_val < b_val)
> +                       return -1;
> +               if (a_val > b_val)
> +                       return 1;
> +       } else {
> +               if (a_val > b_val)
> +                       return -1;
> +               if (a_val < b_val)
> +                       return 1;
> +       }
> +
> +       return 0;
> +}
> +
> +/*
> + * Test implementation mirroring acpi_ns_sort_list from nsrepair2.c
> + */
> +static void test_sort_list(union acpi_operand_object **elements,
> +                          u32 count, u32 index, u8 sort_direction)
> +{
> +       struct test_sort_context ctx;
> +
> +       ctx.sort_index = index;
> +       ctx.sort_direction = sort_direction;
> +
> +       sort_r(elements, count, sizeof(union acpi_operand_object *),
> +              test_sort_cmp, NULL, &ctx);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list ascending sort
> + */
> +static void nsrepair2_test_sort_list_ascending(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
> +
> +       /* Create package with 3 subpackages, each having an integer at index 0 */
> +       pkg = create_package_object(test, 3);
> +
> +       /* Subpackage 0: value = 300 */
> +       sub_pkg0 = create_package_object(test, 1);
> +       sub_pkg0->package.elements[0] = create_integer_object(test, 300);
> +       pkg->package.elements[0] = sub_pkg0;
> +
> +       /* Subpackage 1: value = 100 */
> +       sub_pkg1 = create_package_object(test, 1);
> +       sub_pkg1->package.elements[0] = create_integer_object(test, 100);
> +       pkg->package.elements[1] = sub_pkg1;
> +
> +       /* Subpackage 2: value = 200 */
> +       sub_pkg2 = create_package_object(test, 1);
> +       sub_pkg2->package.elements[0] = create_integer_object(test, 200);
> +       pkg->package.elements[2] = sub_pkg2;
> +
> +       /* Sort ascending by element index 0 */
> +       test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
> +
> +       /* Verify sorted order: 100, 200, 300 */
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[0]->integer.value, 100ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[1]->package.elements[0]->integer.value, 200ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[2]->package.elements[0]->integer.value, 300ULL);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list descending sort
> + */
> +static void nsrepair2_test_sort_list_descending(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
> +
> +       /* Create package with 3 subpackages, each having an integer at index 0 */
> +       pkg = create_package_object(test, 3);
> +
> +       /* Subpackage 0: value = 100 */
> +       sub_pkg0 = create_package_object(test, 1);
> +       sub_pkg0->package.elements[0] = create_integer_object(test, 100);
> +       pkg->package.elements[0] = sub_pkg0;
> +
> +       /* Subpackage 1: value = 300 */
> +       sub_pkg1 = create_package_object(test, 1);
> +       sub_pkg1->package.elements[0] = create_integer_object(test, 300);
> +       pkg->package.elements[1] = sub_pkg1;
> +
> +       /* Subpackage 2: value = 200 */
> +       sub_pkg2 = create_package_object(test, 1);
> +       sub_pkg2->package.elements[0] = create_integer_object(test, 200);
> +       pkg->package.elements[2] = sub_pkg2;
> +
> +       /* Sort descending by element index 0 */
> +       test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_DESCENDING);
> +
> +       /* Verify sorted order: 300, 200, 100 */
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[0]->integer.value, 300ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[1]->package.elements[0]->integer.value, 200ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[2]->package.elements[0]->integer.value, 100ULL);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list with already sorted data
> + */
> +static void nsrepair2_test_sort_list_already_sorted(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
> +
> +       pkg = create_package_object(test, 3);
> +
> +       /* Already in ascending order: 10, 20, 30 */
> +       sub_pkg0 = create_package_object(test, 1);
> +       sub_pkg0->package.elements[0] = create_integer_object(test, 10);
> +       pkg->package.elements[0] = sub_pkg0;
> +
> +       sub_pkg1 = create_package_object(test, 1);
> +       sub_pkg1->package.elements[0] = create_integer_object(test, 20);
> +       pkg->package.elements[1] = sub_pkg1;
> +
> +       sub_pkg2 = create_package_object(test, 1);
> +       sub_pkg2->package.elements[0] = create_integer_object(test, 30);
> +       pkg->package.elements[2] = sub_pkg2;
> +
> +       /* Sort ascending - should remain unchanged */
> +       test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
> +
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[0]->integer.value, 10ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[1]->package.elements[0]->integer.value, 20ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[2]->package.elements[0]->integer.value, 30ULL);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list with equal values
> + */
> +static void nsrepair2_test_sort_list_equal_values(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
> +
> +       pkg = create_package_object(test, 3);
> +
> +       /* All equal values: 50, 50, 50 */
> +       sub_pkg0 = create_package_object(test, 1);
> +       sub_pkg0->package.elements[0] = create_integer_object(test, 50);
> +       pkg->package.elements[0] = sub_pkg0;
> +
> +       sub_pkg1 = create_package_object(test, 1);
> +       sub_pkg1->package.elements[0] = create_integer_object(test, 50);
> +       pkg->package.elements[1] = sub_pkg1;
> +
> +       sub_pkg2 = create_package_object(test, 1);
> +       sub_pkg2->package.elements[0] = create_integer_object(test, 50);
> +       pkg->package.elements[2] = sub_pkg2;
> +
> +       /* Sort ascending - all equal, order should be stable or unchanged */
> +       test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
> +
> +       /* All values should still be 50 */
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[0]->integer.value, 50ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[1]->package.elements[0]->integer.value, 50ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[2]->package.elements[0]->integer.value, 50ULL);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list sort by non-zero index
> + */
> +static void nsrepair2_test_sort_list_by_index(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *sub_pkg0, *sub_pkg1, *sub_pkg2;
> +
> +       pkg = create_package_object(test, 3);
> +
> +       /* Subpackages with 2 elements each, sort by index 1 */
> +       sub_pkg0 = create_package_object(test, 2);
> +       sub_pkg0->package.elements[0] = create_integer_object(test, 1);
> +       sub_pkg0->package.elements[1] = create_integer_object(test, 500);  /* Sort key */
> +       pkg->package.elements[0] = sub_pkg0;
> +
> +       sub_pkg1 = create_package_object(test, 2);
> +       sub_pkg1->package.elements[0] = create_integer_object(test, 2);
> +       sub_pkg1->package.elements[1] = create_integer_object(test, 100);  /* Sort key */
> +       pkg->package.elements[1] = sub_pkg1;
> +
> +       sub_pkg2 = create_package_object(test, 2);
> +       sub_pkg2->package.elements[0] = create_integer_object(test, 3);
> +       sub_pkg2->package.elements[1] = create_integer_object(test, 300);  /* Sort key */
> +       pkg->package.elements[2] = sub_pkg2;
> +
> +       /* Sort ascending by element index 1 */
> +       test_sort_list(pkg->package.elements, pkg->package.count, 1, TEST_SORT_ASCENDING);
> +
> +       /* Verify sorted by index 1: 100, 300, 500 */
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[1]->integer.value, 100ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[1]->package.elements[1]->integer.value, 300ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[2]->package.elements[1]->integer.value, 500ULL);
> +
> +       /* Verify element[0] values followed their packages */
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[0]->integer.value, 2ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[1]->package.elements[0]->integer.value, 3ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[2]->package.elements[0]->integer.value, 1ULL);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list single element (edge case)
> + */
> +static void nsrepair2_test_sort_list_single_element(struct kunit *test)
> +{
> +       union acpi_operand_object *pkg;
> +       union acpi_operand_object *sub_pkg0;
> +
> +       pkg = create_package_object(test, 1);
> +
> +       sub_pkg0 = create_package_object(test, 1);
> +       sub_pkg0->package.elements[0] = create_integer_object(test, 42);
> +       pkg->package.elements[0] = sub_pkg0;
> +
> +       /* Sort single element - should not crash */
> +       test_sort_list(pkg->package.elements, pkg->package.count, 0, TEST_SORT_ASCENDING);
> +
> +       KUNIT_EXPECT_EQ(test,
> +               pkg->package.elements[0]->package.elements[0]->integer.value, 42ULL);
> +}
> +
> +/*
> + * Test: acpi_ns_sort_list with PSS-like structure (descending frequency)
> + */
> +static void nsrepair2_test_sort_list_pss_scenario(struct kunit *test)
> +{
> +       union acpi_operand_object *pss_pkg;
> +       union acpi_operand_object *sub_pkg;
> +       int i;
> +
> +       /* Create _PSS package with 4 P-state subpackages in wrong order */
> +       pss_pkg = create_package_object(test, 4);
> +
> +       /* P-state with frequency 1000 MHz */
> +       sub_pkg = create_package_object(test, 6);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 1000);
> +       for (i = 1; i < 6; i++)
> +               sub_pkg->package.elements[i] = create_integer_object(test, 0);
> +       pss_pkg->package.elements[0] = sub_pkg;
> +
> +       /* P-state with frequency 3000 MHz */
> +       sub_pkg = create_package_object(test, 6);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 3000);
> +       for (i = 1; i < 6; i++)
> +               sub_pkg->package.elements[i] = create_integer_object(test, 0);
> +       pss_pkg->package.elements[1] = sub_pkg;
> +
> +       /* P-state with frequency 2000 MHz */
> +       sub_pkg = create_package_object(test, 6);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 2000);
> +       for (i = 1; i < 6; i++)
> +               sub_pkg->package.elements[i] = create_integer_object(test, 0);
> +       pss_pkg->package.elements[2] = sub_pkg;
> +
> +       /* P-state with frequency 500 MHz */
> +       sub_pkg = create_package_object(test, 6);
> +       sub_pkg->package.elements[0] = create_integer_object(test, 500);
> +       for (i = 1; i < 6; i++)
> +               sub_pkg->package.elements[i] = create_integer_object(test, 0);
> +       pss_pkg->package.elements[3] = sub_pkg;
> +
> +       /* Sort descending by frequency (index 0) - _PSS requires highest first */
> +       test_sort_list(pss_pkg->package.elements, pss_pkg->package.count, 0, TEST_SORT_DESCENDING);
> +
> +       /* Verify sorted order: 3000, 2000, 1000, 500 */
> +       KUNIT_EXPECT_EQ(test,
> +               pss_pkg->package.elements[0]->package.elements[0]->integer.value, 3000ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pss_pkg->package.elements[1]->package.elements[0]->integer.value, 2000ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pss_pkg->package.elements[2]->package.elements[0]->integer.value, 1000ULL);
> +       KUNIT_EXPECT_EQ(test,
> +               pss_pkg->package.elements[3]->package.elements[0]->integer.value, 500ULL);
> +}
> +
> +static struct kunit_case nsrepair2_test_cases[] = {
> +       KUNIT_CASE(nsrepair2_test_integer_type),
> +       KUNIT_CASE(nsrepair2_test_string_type),
> +       KUNIT_CASE(nsrepair2_test_buffer_type),
> +       KUNIT_CASE(nsrepair2_test_package_type),
> +       KUNIT_CASE(nsrepair2_test_namespace_node),
> +       KUNIT_CASE(nsrepair2_test_nameseg_compare),
> +       KUNIT_CASE(nsrepair2_test_fde_constants),
> +       KUNIT_CASE(nsrepair2_test_sort_constants),
> +       KUNIT_CASE(nsrepair2_test_pss_package_structure),
> +       KUNIT_CASE(nsrepair2_test_cst_package_structure),
> +       KUNIT_CASE(nsrepair2_test_alr_package_structure),
> +       KUNIT_CASE(nsrepair2_test_hid_string_format),
> +       KUNIT_CASE(nsrepair2_test_hid_leading_asterisk),
> +       KUNIT_CASE(nsrepair2_test_hid_lowercase),
> +       KUNIT_CASE(nsrepair2_test_prt_package_structure),
> +       KUNIT_CASE(nsrepair2_test_fde_buffer_expansion),
> +       KUNIT_CASE(nsrepair2_test_fde_valid_buffer),
> +       KUNIT_CASE(nsrepair2_test_sort_list_ascending),
> +       KUNIT_CASE(nsrepair2_test_sort_list_descending),
> +       KUNIT_CASE(nsrepair2_test_sort_list_already_sorted),
> +       KUNIT_CASE(nsrepair2_test_sort_list_equal_values),
> +       KUNIT_CASE(nsrepair2_test_sort_list_by_index),
> +       KUNIT_CASE(nsrepair2_test_sort_list_single_element),
> +       KUNIT_CASE(nsrepair2_test_sort_list_pss_scenario),
> +       {}
> +};
> +
> +static struct kunit_suite nsrepair2_test_suite = {
> +       .name = "acpi-nsrepair2",
> +       .test_cases = nsrepair2_test_cases,
> +};
> +
> +kunit_test_suites(&nsrepair2_test_suite);
> +
> +MODULE_DESCRIPTION("KUnit tests for ACPI nsrepair2 repair functions");
> +MODULE_LICENSE("GPL");
> --
> 2.43.0
>
 Hi all,

   Sorry for the oversight - I forgot to add the Kconfig and Makefile changes
   to enable the test. Will include them in v2.

-- 
Regards,
Nick Huang

Re: [PATCH 1/2] ACPI: nsrepair2: Replace O(n²) bubble sort with O(n log n) sort_r()

[David Laight]

On Sun,  1 Feb 2026 13:03:33 +0000
Nick Huang <sef1548@gmail.com> wrote:

>    Replace the O(n²) bubble sort implementation in acpi_ns_sort_list()
>    with the kernel's sort_r() function which uses heapsort, providing
>    O(n log n) time complexity.
> 
>    This improves performance for large ACPI package lists while also
>    reducing code complexity by leveraging the existing kernel sort API.

What is the break even size?
While the heapsort is O(n long n) it is also more complicated.
There is also the cost of the function call - especially with all the
mitigations that distro kernels are likely to enable.

For large datasets the d-cache locality of both sorts is particularly horrid.
It is almost certainly better to allocate an array of index:value pairs
and sort that.
For very big datasets you want to sort small sections (that fit in the
d-cache) and then use merge sorts (also O(n log n)) to combine them.
(Yes - this is how you sort data with 3 mag-tape drives....)

Oh, in any case, write separate functions for ascending/descending.

	David

> 
> Signed-off-by: Nick Huang <sef1548@gmail.com>
> ---
>  drivers/acpi/acpica/nsrepair2.c | 87 +++++++++++++++++++++++----------
>  1 file changed, 62 insertions(+), 25 deletions(-)
> 
> diff --git a/drivers/acpi/acpica/nsrepair2.c b/drivers/acpi/acpica/nsrepair2.c
> index 8dbb870f4..a39ef59fe 100644
> --- a/drivers/acpi/acpica/nsrepair2.c
> +++ b/drivers/acpi/acpica/nsrepair2.c
> @@ -9,6 +9,7 @@
>   *****************************************************************************/
>  
>  #include <acpi/acpi.h>
> +#include <linux/sort.h>
>  #include "accommon.h"
>  #include "acnamesp.h"
>  
> @@ -84,6 +85,14 @@ acpi_ns_check_sorted_list(struct acpi_evaluate_info *info,
>  static void
>  acpi_ns_remove_element(union acpi_operand_object *obj_desc, u32 index);
>  
> +/* Context structure for sort comparison function */
> +struct acpi_sort_context {
> +	u32 sort_index;
> +	u8 sort_direction;
> +};
> +
> +static int acpi_ns_sort_cmp(const void *a, const void *b, const void *priv);
> +
>  static void
>  acpi_ns_sort_list(union acpi_operand_object **elements,
>  		  u32 count, u32 index, u8 sort_direction);
> @@ -851,6 +860,52 @@ acpi_ns_check_sorted_list(struct acpi_evaluate_info *info,
>  	return (AE_OK);
>  }
>  
> +/******************************************************************************
> + *
> + * FUNCTION:    acpi_ns_sort_cmp
> + *
> + * PARAMETERS:  a               - First element to compare
> + *              b               - Second element to compare
> + *              priv            - Pointer to sort context (acpi_sort_context)
> + *
> + * RETURN:      -1, 0, or 1 depending on sort order
> + *
> + * DESCRIPTION: Comparison function for sort_r() API. Compares the integer
> + *              values at the specified index within package elements.
> + *
> + *****************************************************************************/
> +
> +static int acpi_ns_sort_cmp(const void *a, const void *b, const void *priv)
> +{
> +	union acpi_operand_object *obj_a = *(union acpi_operand_object **)a;
> +	union acpi_operand_object *obj_b = *(union acpi_operand_object **)b;
> +	const struct acpi_sort_context *ctx = priv;
> +	union acpi_operand_object *value_a;
> +	union acpi_operand_object *value_b;
> +	u64 a_val;
> +	u64 b_val;
> +
> +	value_a = obj_a->package.elements[ctx->sort_index];
> +	value_b = obj_b->package.elements[ctx->sort_index];
> +
> +	a_val = value_a->integer.value;
> +	b_val = value_b->integer.value;
> +
> +	if (ctx->sort_direction == ACPI_SORT_ASCENDING) {
> +		if (a_val < b_val)
> +			return -1;
> +		if (a_val > b_val)
> +			return 1;
> +	} else {
> +		if (a_val > b_val)
> +			return -1;
> +		if (a_val < b_val)
> +			return 1;
> +	}
> +
> +	return 0;
> +}
> +
>  /******************************************************************************
>   *
>   * FUNCTION:    acpi_ns_sort_list
> @@ -873,31 +928,13 @@ static void
>  acpi_ns_sort_list(union acpi_operand_object **elements,
>  		  u32 count, u32 index, u8 sort_direction)
>  {
> -	union acpi_operand_object *obj_desc1;
> -	union acpi_operand_object *obj_desc2;
> -	union acpi_operand_object *temp_obj;
> -	u32 i;
> -	u32 j;
> -
> -	/* Simple bubble sort */
> -
> -	for (i = 1; i < count; i++) {
> -		for (j = (count - 1); j >= i; j--) {
> -			obj_desc1 = elements[j - 1]->package.elements[index];
> -			obj_desc2 = elements[j]->package.elements[index];
> -
> -			if (((sort_direction == ACPI_SORT_ASCENDING) &&
> -			     (obj_desc1->integer.value >
> -			      obj_desc2->integer.value))
> -			    || ((sort_direction == ACPI_SORT_DESCENDING)
> -				&& (obj_desc1->integer.value <
> -				    obj_desc2->integer.value))) {
> -				temp_obj = elements[j - 1];
> -				elements[j - 1] = elements[j];
> -				elements[j] = temp_obj;
> -			}
> -		}
> -	}
> +	struct acpi_sort_context ctx;
> +
> +	ctx.sort_index = index;
> +	ctx.sort_direction = sort_direction;
> +
> +	sort_r(elements, count, sizeof(union acpi_operand_object *),
> +	       acpi_ns_sort_cmp, NULL, &ctx);
>  }
>  
>  /******************************************************************************

Re: [PATCH 1/2] ACPI: nsrepair2: Replace O(n²) bubble sort with O(n log n) sort_r()

[Nick Huang]

David Laight <david.laight.linux@gmail.com> 於 2026年2月2日週一 上午6:48寫道：
>
> On Sun,  1 Feb 2026 13:03:33 +0000
> Nick Huang <sef1548@gmail.com> wrote:
>
> >    Replace the O(n²) bubble sort implementation in acpi_ns_sort_list()
> >    with the kernel's sort_r() function which uses heapsort, providing
> >    O(n log n) time complexity.
> >
> >    This improves performance for large ACPI package lists while also
> >    reducing code complexity by leveraging the existing kernel sort API.
>
> What is the break even size?
> While the heapsort is O(n long n) it is also more complicated.
> There is also the cost of the function call - especially with all the
> mitigations that distro kernels are likely to enable.
>
> For large datasets the d-cache locality of both sorts is particularly horrid.
> It is almost certainly better to allocate an array of index:value pairs
> and sort that.
> For very big datasets you want to sort small sections (that fit in the
> d-cache) and then use merge sorts (also O(n log n)) to combine them.
> (Yes - this is how you sort data with 3 mag-tape drives....)
>
> Oh, in any case, write separate functions for ascending/descending.
>
>         David
>
Hi David

  Thank you for your reply and the detailed feedback.


   I ran KUnit benchmarks to investigate your questions.


   === Break-Even Point ===


   I compared bubble sort vs heapsort across various array sizes:


     N  | Bubble(ns) | Heap(ns) | Faster

    ----|------------|----------|--------

      2 |         61 |       99 | bubble

      3 |         63 |      115 | bubble

      4 |         78 |      163 | bubble

      5 |         96 |      215 | bubble

      6 |        119 |      260 | bubble

      8 |        177 |      388 | bubble

     10 |        257 |      539 | bubble

     12 |        415 |      721 | bubble

     16 |        726 |     1044 | bubble

     20 |       1106 |     1484 | bubble

     32 |       2854 |     3091 | bubble


   Bubble sort is faster for all tested sizes. The break-even point was not

   reached within N=32, which covers all realistic ACPI use cases:


     - _ALR: 2-10 entries (ambient light response)

     - _CST: 2-8 entries (C-states)

     - _PSS: 5-20 entries (P-states)

     - _TSS: 2-16 entries (T-states)


   As you noted, heapsort has additional overhead from function calls and

   mitigations that outweigh its O(n log n) advantage at small N.


   === Separate Ascending/Descending Functions ===


   I also tested combined vs separate sort functions as you suggested:


     N  | Combined(ns) | Separate(ns) | Saved

    ----|--------------|--------------|------

      4 |           84 |           75 |  11%

      8 |          179 |          175 |   3%

     16 |          737 |          806 |  -9%


   The results are mixed. Separate functions show marginal improvement at

   small N, but the combined function performs better at N=16, possibly

   due to instruction cache effects.


   === Conclusion ===


   Given these results, replacing bubble sort with heapsort would likely

   degrade performance for typical ACPI workloads. The existing bubble

   sort implementation appears to be the right choice for this use case.



-- 
Regards,
Nick Huang

Re: [PATCH 0/2] nsrepair2: Improve sorting performance and add tests

[Rafael J. Wysocki]

On Sun, Feb 1, 2026 at 2:03 PM Nick Huang <sef1548@gmail.com> wrote:
>
>    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
>
> --

The ACPICA code in the kernel comes from the upstream ACPICA project
(hosted on GitHub) as described in
Documentation/driver-api/acpi/linuxized-acpica.rst.

Changes to that code need to be made upstream from where they are
picked up automatically after every upstream ACPICA release (or you
can speed that up if need be by sending a Linux patch based on an
upstream ACPICA commit).

As for the test part, I'm not sure how useful it would be given the above.

Thanks!

Re: [PATCH 0/2] nsrepair2: Improve sorting performance and add tests

[Nick Huang]

Rafael J. Wysocki <rafael@kernel.org> 於 2026年2月13日週五 下午9:40寫道：
>
> On Sun, Feb 1, 2026 at 2:03 PM Nick Huang <sef1548@gmail.com> wrote:
> >
> >    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
> >
> > --
>
> The ACPICA code in the kernel comes from the upstream ACPICA project
> (hosted on GitHub) as described in
> Documentation/driver-api/acpi/linuxized-acpica.rst.
>
> Changes to that code need to be made upstream from where they are
> picked up automatically after every upstream ACPICA release (or you
> can speed that up if need be by sending a Linux patch based on an
> upstream ACPICA commit).
>
> As for the test part, I'm not sure how useful it would be given the above.
>
> Thanks!

Hi Rafael J. Wysocki

Thank you for the reply. I will submit the changes via a Pull Request
to the upstream ACPICA GitHub repository as suggested.
-- 
Regards,
Nick Huang