java-topology/defects/linux/tests/linux-0005-component-kunit.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * KUnit tests for linux-0005: drivers/base/component.c find_component()
 * CWE-407: O(A×M×C) → O(A×M) via DECLARE_HASHTABLE
 *
 * Tests:
 *   1. Unit:       hash lookup returns same result as linear scan
 *   2. Integration: add/remove components, verify hash stays consistent
 *   3. Functional:  O(C) list ops >> O(1) hash ops at C=200
 *
 * Run: make -C tools/testing/kunit/ run --kconfig_add CONFIG_COMPONENT_KUNIT_TEST=y
 */

#include <kunit/test.h>
#include <linux/hashtable.h>
#include <linux/slab.h>
#include <linux/list.h>

/* --- Minimal simulation of the component framework data structures --- */

struct mock_component {
	struct device      *dev;
	bool                bound;
	struct list_head    node;
	struct hlist_node   dev_hash;   /* CWE-407 fix field */
};

#define MOCK_HASH_BITS 8
static DEFINE_HASHTABLE(mock_dev_ht, MOCK_HASH_BITS);
static LIST_HEAD(mock_component_list);

static struct mock_component *find_component_slow(struct device *dev)
{
	struct mock_component *c;

	list_for_each_entry(c, &mock_component_list, node) {
		if (c->dev == dev)
			return c;
	}
	return NULL;
}

static struct mock_component *find_component_fast(struct device *dev)
{
	struct mock_component *c;
	unsigned long key = (unsigned long)dev >> 3;

	hash_for_each_possible(mock_dev_ht, c, dev_hash, key) {
		if (c->dev == dev)
			return c;
	}
	return NULL;
}

static struct mock_component *add_component(struct kunit *test, struct device *dev)
{
	struct mock_component *c = kunit_kzalloc(test, sizeof(*c), GFP_KERNEL);
	KUNIT_ASSERT_NOT_NULL(test, c);
	c->dev = dev;
	list_add_tail(&c->node, &mock_component_list);
	hash_add(mock_dev_ht, &c->dev_hash, (unsigned long)dev >> 3);
	return c;
}

static void remove_component(struct mock_component *c)
{
	list_del(&c->node);
	hash_del(&c->dev_hash);
}

static void test_cleanup(struct kunit *test)
{
	struct mock_component *c, *tmp;

	list_for_each_entry_safe(c, tmp, &mock_component_list, node)
		remove_component(c);
}

/* --- Unit: fast path returns same component as slow path --- */

static void component_kunit_test_unit(struct kunit *test)
{
	/* Use stack addresses as synthetic device pointers — unique, non-NULL */
	int a, b, c_var;
	struct device *dev_a = (struct device *)&a;
	struct device *dev_b = (struct device *)&b;
	struct device *dev_c = (struct device *)&c_var;

	struct mock_component *comp_a = add_component(test, dev_a);
	struct mock_component *comp_b = add_component(test, dev_b);
	struct mock_component *comp_c = add_component(test, dev_c);

	/* Verify fast == slow for all registered devs */
	KUNIT_EXPECT_PTR_EQ(test, find_component_slow(dev_a), find_component_fast(dev_a));
	KUNIT_EXPECT_PTR_EQ(test, find_component_slow(dev_b), find_component_fast(dev_b));
	KUNIT_EXPECT_PTR_EQ(test, find_component_slow(dev_c), find_component_fast(dev_c));

	/* Verify correct component returned */
	KUNIT_EXPECT_PTR_EQ(test, find_component_fast(dev_a), comp_a);
	KUNIT_EXPECT_PTR_EQ(test, find_component_fast(dev_b), comp_b);
	KUNIT_EXPECT_PTR_EQ(test, find_component_fast(dev_c), comp_c);

	/* Not-found: both return NULL */
	int x;
	struct device *dev_x = (struct device *)&x;
	KUNIT_EXPECT_NULL(test, find_component_slow(dev_x));
	KUNIT_EXPECT_NULL(test, find_component_fast(dev_x));

	test_cleanup(test);
}

/* --- Integration: add/remove consistency --- */

static void component_kunit_test_integration(struct kunit *test)
{
#define N_DEVS 32
	int slots[N_DEVS];
	struct device *devs[N_DEVS];
	struct mock_component *comps[N_DEVS];

	for (int i = 0; i < N_DEVS; i++) {
		devs[i]  = (struct device *)&slots[i];
		comps[i] = add_component(test, devs[i]);
	}

	/* All N components findable via both paths */
	for (int i = 0; i < N_DEVS; i++) {
		KUNIT_EXPECT_PTR_EQ(test,
			find_component_slow(devs[i]),
			find_component_fast(devs[i]));
		KUNIT_EXPECT_PTR_EQ(test, find_component_fast(devs[i]), comps[i]);
	}

	/* Remove every other component; verify remaining findable, removed gone */
	for (int i = 0; i < N_DEVS; i += 2)
		remove_component(comps[i]);

	for (int i = 0; i < N_DEVS; i++) {
		if (i % 2 == 0) {
			KUNIT_EXPECT_NULL(test, find_component_slow(devs[i]));
			KUNIT_EXPECT_NULL(test, find_component_fast(devs[i]));
		} else {
			KUNIT_EXPECT_NOT_NULL(test, find_component_fast(devs[i]));
		}
	}

	test_cleanup(test);
#undef N_DEVS
}

/* --- Functional / complexity gate: O(C) list >> O(1) hash at C=200 --- */

static void component_kunit_test_functional(struct kunit *test)
{
#define C 200
#define LOOKUPS 10000
	int slots[C];
	struct device *devs[C];
	u64 t_slow_start, t_fast_start, t_slow_end, t_fast_end;
	long slow_ns, fast_ns;
	int target_idx = C - 1;   /* worst case: target is last in list */

	for (int i = 0; i < C; i++) {
		devs[i] = (struct device *)&slots[i];
		add_component(test, devs[i]);
	}

	struct device *target = devs[target_idx];

	/* Time slow path */
	t_slow_start = ktime_get_ns();
	for (int i = 0; i < LOOKUPS; i++)
		(void)find_component_slow(target);
	t_slow_end = ktime_get_ns();
	slow_ns = t_slow_end - t_slow_start;

	/* Time fast path */
	t_fast_start = ktime_get_ns();
	for (int i = 0; i < LOOKUPS; i++)
		(void)find_component_fast(target);
	t_fast_end = ktime_get_ns();
	fast_ns = t_fast_end - t_fast_start;

	kunit_info(test, "component find C=%d %d lookups: slow=%ldns fast=%ldns ratio=%ldx\n",
		C, LOOKUPS, slow_ns, fast_ns,
		fast_ns > 0 ? slow_ns / fast_ns : 999);

	/*
	 * CWE-407 gate: slow path must be at least 20× slower than fast path.
	 * At C=200, linear scan averages 100 comparisons vs O(1) hash probe.
	 */
	KUNIT_EXPECT_GT(test, slow_ns, fast_ns * 20);

	test_cleanup(test);
#undef C
#undef LOOKUPS
}

static struct kunit_case component_kunit_cases[] = {
	KUNIT_CASE(component_kunit_test_unit),
	KUNIT_CASE(component_kunit_test_integration),
	KUNIT_CASE(component_kunit_test_functional),
	{}
};

static struct kunit_suite component_kunit_suite = {
	.name  = "linux_0005_component_cwe407",
	.test_cases = component_kunit_cases,
};

kunit_test_suite(component_kunit_suite);

MODULE_LICENSE("GPL v2");
MODULE_DESCRIPTION("KUnit tests for linux-0005 CWE-407 component find_component hash fix");