On Mon, Jul 14, 2025 at 11:53:19AM -0700, Tiffany Yang wrote:
> Each case tested by the binder allocator test is defined by 3 parameters:
> the end alignment type of each requested buffer allocation, whether those
> buffers share the front or back pages of the allotted address space, and
> the order in which those buffers should be released. The alignment type
> represents how a binder buffer may be laid out within or across page
> boundaries and relative to other buffers, and it's used along with
> whether the buffers cover part (sharing the front pages) of or all
> (sharing the back pages) of the vma to calculate the sizes passed into
> each test.
>
> binder_alloc_test_alloc recursively generates each possible arrangement
> of alignment types and then tests that the binder_alloc code tracks pages
> correctly when those buffers are allocated and then freed in every
> possible order at both ends of the address space. While they provide
> comprehensive coverage, they are poor candidates to be represented as
> KUnit test cases, which must be statically enumerated. For 5 buffers and
> 5 end alignment types, the test case array would have 750,000 entries.
> This change structures the recursive calls into meaningful test cases so
> that failures are easier to interpret.
>
> Signed-off-by: Tiffany Yang <ynaf...@google.com>
> ---
> v2:
> * Fix build warning Reported-by: kernel test robot <l...@intel.com>
> Closes:
> https://lore.kernel.org/oe-kbuild-all/202506281959.hfotiujs-...@intel.com/
> ---
> drivers/android/tests/binder_alloc_kunit.c | 234 ++++++++++++++++-----
> 1 file changed, 181 insertions(+), 53 deletions(-)
>
> diff --git a/drivers/android/tests/binder_alloc_kunit.c
> b/drivers/android/tests/binder_alloc_kunit.c
> index 9e185e2036e5..02aa4a135eb5 100644
> --- a/drivers/android/tests/binder_alloc_kunit.c
> +++ b/drivers/android/tests/binder_alloc_kunit.c
> @@ -24,7 +24,16 @@ MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
> #define BUFFER_NUM 5
> #define BUFFER_MIN_SIZE (PAGE_SIZE / 8)
>
> -static int binder_alloc_test_failures;
> +#define FREESEQ_BUFLEN ((3 * BUFFER_NUM) + 1)
> +
> +#define ALIGN_TYPE_STRLEN (12)
> +
> +#define ALIGNMENTS_BUFLEN (((ALIGN_TYPE_STRLEN + 6) * BUFFER_NUM) + 1)
> +
> +#define PRINT_ALL_CASES (0)
> +
> +/* 5^5 alignment combinations * 2 places to share pages * 5! free sequences
> */
> +#define TOTAL_EXHAUSTIVE_CASES (3125 * 2 * 120)
>
> /**
> * enum buf_end_align_type - Page alignment of a buffer
> @@ -86,18 +95,49 @@ enum buf_end_align_type {
> LOOP_END,
> };
>
> -static void pr_err_size_seq(struct kunit *test, size_t *sizes, int *seq)
> +static const char *const buf_end_align_type_strs[LOOP_END] = {
> + [SAME_PAGE_UNALIGNED] = "SP_UNALIGNED",
> + [SAME_PAGE_ALIGNED] = " SP_ALIGNED ",
> + [NEXT_PAGE_UNALIGNED] = "NP_UNALIGNED",
> + [NEXT_PAGE_ALIGNED] = " NP_ALIGNED ",
> + [NEXT_NEXT_UNALIGNED] = "NN_UNALIGNED",
> +};
> +
> +struct binder_alloc_test_case_info {
> + size_t *buffer_sizes;
> + int *free_sequence;
> + char alignments[ALIGNMENTS_BUFLEN];
> + bool front_pages;
> +};
> +
> +static void stringify_free_seq(struct kunit *test, int *seq, char *buf,
> + size_t buf_len)
> {
> + size_t bytes = 0;
> int i;
>
> - kunit_err(test, "alloc sizes: ");
> - for (i = 0; i < BUFFER_NUM; i++)
> - pr_cont("[%zu]", sizes[i]);
> - pr_cont("\n");
> - kunit_err(test, "free seq: ");
> - for (i = 0; i < BUFFER_NUM; i++)
> - pr_cont("[%d]", seq[i]);
> - pr_cont("\n");
> + for (i = 0; i < BUFFER_NUM; i++) {
> + bytes += snprintf(buf + bytes, buf_len - bytes, "[%d]", seq[i]);
> + if (bytes >= buf_len)
> + break;
> + }
> + KUNIT_EXPECT_LT(test, bytes, buf_len);
> +}
> +
> +static void stringify_alignments(struct kunit *test, int *alignments,
> + char *buf, size_t buf_len)
> +{
> + size_t bytes = 0;
> + int i;
> +
> + for (i = 0; i < BUFFER_NUM; i++) {
> + bytes += snprintf(buf + bytes, buf_len - bytes, "[ %d:%s ]", i,
> + buf_end_align_type_strs[alignments[i]]);
> + if (bytes >= buf_len)
> + break;
> + }
> +
> + KUNIT_EXPECT_LT(test, bytes, buf_len);
> }
For both stringify functions, snprintf is potentially unsafe. In the
spirit of recent string API discussions, please switch to using a
seq_buf:
static void stringify_free_seq(struct kunit *test, int *seq, seq_buf *buf)
{
unsigned int i;
for (i = 0; i < BUFFER_NUM; i++)
seq_buf_printf(buf, "[%d]", seq[i])
KUNIT_EXPECT_FALSE(test, seq_buf_has_overflowed(buf));
}
...
DECLARE_SEQ_BUF(freeseq_buf, FREESEQ_BUFLEN);
...
stringify_free_seq(test, tc->free_sequence, &freeseq_buf);
>
> static bool check_buffer_pages_allocated(struct kunit *test,
> @@ -124,28 +164,30 @@ static bool check_buffer_pages_allocated(struct kunit
> *test,
> return true;
> }
>
> -static void binder_alloc_test_alloc_buf(struct kunit *test,
> - struct binder_alloc *alloc,
> - struct binder_buffer *buffers[],
> - size_t *sizes, int *seq)
> +static unsigned long binder_alloc_test_alloc_buf(struct kunit *test,
> + struct binder_alloc *alloc,
> + struct binder_buffer
> *buffers[],
> + size_t *sizes, int *seq)
> {
> + unsigned long failures = 0;
> int i;
>
> for (i = 0; i < BUFFER_NUM; i++) {
> buffers[i] = binder_alloc_new_buf(alloc, sizes[i], 0, 0, 0);
> if (IS_ERR(buffers[i]) ||
> - !check_buffer_pages_allocated(test, alloc, buffers[i],
> sizes[i])) {
> - pr_err_size_seq(test, sizes, seq);
> - binder_alloc_test_failures++;
> - }
> + !check_buffer_pages_allocated(test, alloc, buffers[i],
> sizes[i]))
> + failures++;
> }
> +
> + return failures;
> }
>
> -static void binder_alloc_test_free_buf(struct kunit *test,
> - struct binder_alloc *alloc,
> - struct binder_buffer *buffers[],
> - size_t *sizes, int *seq, size_t end)
> +static unsigned long binder_alloc_test_free_buf(struct kunit *test,
> + struct binder_alloc *alloc,
> + struct binder_buffer *buffers[],
> + size_t *sizes, int *seq, size_t
> end)
> {
> + unsigned long failures = 0;
> int i;
>
> for (i = 0; i < BUFFER_NUM; i++)
> @@ -153,17 +195,19 @@ static void binder_alloc_test_free_buf(struct kunit
> *test,
>
> for (i = 0; i <= (end - 1) / PAGE_SIZE; i++) {
> if (list_empty(page_to_lru(alloc->pages[i]))) {
> - pr_err_size_seq(test, sizes, seq);
> kunit_err(test, "expect lru but is %s at page index
> %d\n",
> alloc->pages[i] ? "alloc" : "free", i);
> - binder_alloc_test_failures++;
> + failures++;
> }
> }
> +
> + return failures;
> }
>
> -static void binder_alloc_test_free_page(struct kunit *test,
> - struct binder_alloc *alloc)
> +static unsigned long binder_alloc_test_free_page(struct kunit *test,
> + struct binder_alloc *alloc)
> {
> + unsigned long failures = 0;
> unsigned long count;
> int i;
>
> @@ -177,27 +221,70 @@ static void binder_alloc_test_free_page(struct kunit
> *test,
> kunit_err(test, "expect free but is %s at page index
> %d\n",
> list_empty(page_to_lru(alloc->pages[i])) ?
> "alloc" : "lru", i);
> - binder_alloc_test_failures++;
> + failures++;
> }
> }
> +
> + return failures;
> }
>
> -static void binder_alloc_test_alloc_free(struct kunit *test,
> +/* Executes one full test run for the given test case. */
> +static bool binder_alloc_test_alloc_free(struct kunit *test,
> struct binder_alloc *alloc,
> - size_t *sizes, int *seq, size_t end)
> + struct binder_alloc_test_case_info *tc,
> + size_t end)
> {
> + unsigned long pages = PAGE_ALIGN(end) / PAGE_SIZE;
> struct binder_buffer *buffers[BUFFER_NUM];
> -
> - binder_alloc_test_alloc_buf(test, alloc, buffers, sizes, seq);
> - binder_alloc_test_free_buf(test, alloc, buffers, sizes, seq, end);
> + unsigned long failures;
> + bool failed = false;
> +
> + failures = binder_alloc_test_alloc_buf(test, alloc, buffers,
> + tc->buffer_sizes,
> + tc->free_sequence);
> + failed = failed || failures;
> + KUNIT_EXPECT_EQ_MSG(test, failures, 0,
> + "Initial allocation failed: %lu/%u buffers with
> errors",
> + failures, BUFFER_NUM);
> +
> + failures = binder_alloc_test_free_buf(test, alloc, buffers,
> + tc->buffer_sizes,
> + tc->free_sequence, end);
> + failed = failed || failures;
> + KUNIT_EXPECT_EQ_MSG(test, failures, 0,
> + "Initial buffers not freed correctly: %lu/%lu pages
> not on lru list",
> + failures, pages);
>
> /* Allocate from lru. */
> - binder_alloc_test_alloc_buf(test, alloc, buffers, sizes, seq);
> - if (list_lru_count(alloc->freelist))
> - kunit_err(test, "lru list should be empty but is not\n");
> -
> - binder_alloc_test_free_buf(test, alloc, buffers, sizes, seq, end);
> - binder_alloc_test_free_page(test, alloc);
> + failures = binder_alloc_test_alloc_buf(test, alloc, buffers,
> + tc->buffer_sizes,
> + tc->free_sequence);
> + failed = failed || failures;
> + KUNIT_EXPECT_EQ_MSG(test, failures, 0,
> + "Reallocation failed: %lu/%u buffers with errors",
> + failures, BUFFER_NUM);
> +
> + failures = list_lru_count(alloc->freelist);
> + failed = failed || failures;
> + KUNIT_EXPECT_EQ_MSG(test, failures, 0,
> + "lru list should be empty after reallocation but
> still has %lu pages",
> + failures);
> +
> + failures = binder_alloc_test_free_buf(test, alloc, buffers,
> + tc->buffer_sizes,
> + tc->free_sequence, end);
> + failed = failed || failures;
> + KUNIT_EXPECT_EQ_MSG(test, failures, 0,
> + "Reallocated buffers not freed correctly: %lu/%lu
> pages not on lru list",
> + failures, pages);
> +
> + failures = binder_alloc_test_free_page(test, alloc);
> + failed = failed || failures;
> + KUNIT_EXPECT_EQ_MSG(test, failures, 0,
> + "Failed to clean up allocated pages: %lu/%lu pages
> still installed",
> + failures, (alloc->buffer_size / PAGE_SIZE));
> +
> + return failed;
> }
>
> static bool is_dup(int *seq, int index, int val)
> @@ -213,24 +300,44 @@ static bool is_dup(int *seq, int index, int val)
>
> /* Generate BUFFER_NUM factorial free orders. */
> static void permute_frees(struct kunit *test, struct binder_alloc *alloc,
> - size_t *sizes, int *seq, int index, size_t end)
> + struct binder_alloc_test_case_info *tc,
> + unsigned long *runs, unsigned long *failures,
> + int index, size_t end)
> {
> + bool case_failed;
> int i;
>
> if (index == BUFFER_NUM) {
> - binder_alloc_test_alloc_free(test, alloc, sizes, seq, end);
> + char freeseq_buf[FREESEQ_BUFLEN];
> +
> + case_failed = binder_alloc_test_alloc_free(test, alloc, tc,
> end);
> + *runs += 1;
> + *failures += case_failed;
> +
> + if (case_failed || PRINT_ALL_CASES) {
> + stringify_free_seq(test, tc->free_sequence, freeseq_buf,
> + FREESEQ_BUFLEN);
> + kunit_err(test, "case %lu: [%s] | %s - %s - %s", *runs,
> + case_failed ? "FAILED" : "PASSED",
> + tc->front_pages ? "front" : "back ",
> + tc->alignments, freeseq_buf);
> + }
> +
> return;
> }
> for (i = 0; i < BUFFER_NUM; i++) {
> - if (is_dup(seq, index, i))
> + if (is_dup(tc->free_sequence, index, i))
> continue;
> - seq[index] = i;
> - permute_frees(test, alloc, sizes, seq, index + 1, end);
> + tc->free_sequence[index] = i;
> + permute_frees(test, alloc, tc, runs, failures, index + 1, end);
> }
> }
>
> -static void gen_buf_sizes(struct kunit *test, struct binder_alloc *alloc,
> - size_t *end_offset)
> +static void gen_buf_sizes(struct kunit *test,
> + struct binder_alloc *alloc,
> + struct binder_alloc_test_case_info *tc,
> + size_t *end_offset, unsigned long *runs,
> + unsigned long *failures)
> {
> size_t last_offset, offset = 0;
> size_t front_sizes[BUFFER_NUM];
> @@ -238,31 +345,45 @@ static void gen_buf_sizes(struct kunit *test, struct
> binder_alloc *alloc,
> int seq[BUFFER_NUM] = {0};
> int i;
>
> + tc->free_sequence = seq;
> for (i = 0; i < BUFFER_NUM; i++) {
> last_offset = offset;
> offset = end_offset[i];
> front_sizes[i] = offset - last_offset;
> back_sizes[BUFFER_NUM - i - 1] = front_sizes[i];
> }
> + back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1];
> +
> /*
> * Buffers share the first or last few pages.
> * Only BUFFER_NUM - 1 buffer sizes are adjustable since
> * we need one giant buffer before getting to the last page.
> */
> - back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1];
> - permute_frees(test, alloc, front_sizes, seq, 0,
> + tc->front_pages = true;
> + tc->buffer_sizes = front_sizes;
> + permute_frees(test, alloc, tc, runs, failures, 0,
> end_offset[BUFFER_NUM - 1]);
> - permute_frees(test, alloc, back_sizes, seq, 0, alloc->buffer_size);
> +
> + tc->front_pages = false;
> + tc->buffer_sizes = back_sizes;
> + permute_frees(test, alloc, tc, runs, failures, 0, alloc->buffer_size);
> }
>
> static void gen_buf_offsets(struct kunit *test, struct binder_alloc *alloc,
> - size_t *end_offset, int index)
> + size_t *end_offset, int *alignments,
> + unsigned long *runs, unsigned long *failures,
> + int index)
> {
> size_t end, prev;
> int align;
>
> if (index == BUFFER_NUM) {
> - gen_buf_sizes(test, alloc, end_offset);
> + struct binder_alloc_test_case_info tc = {0};
> +
> + stringify_alignments(test, alignments, tc.alignments,
> + ALIGNMENTS_BUFLEN);
> +
> + gen_buf_sizes(test, alloc, &tc, end_offset, runs, failures);
> return;
> }
> prev = index == 0 ? 0 : end_offset[index - 1];
> @@ -276,7 +397,9 @@ static void gen_buf_offsets(struct kunit *test, struct
> binder_alloc *alloc,
> else
> end += BUFFER_MIN_SIZE;
> end_offset[index] = end;
> - gen_buf_offsets(test, alloc, end_offset, index + 1);
> + alignments[index] = align;
> + gen_buf_offsets(test, alloc, end_offset, alignments, runs,
> + failures, index + 1);
> }
> }
>
> @@ -328,10 +451,15 @@ static void binder_alloc_exhaustive_test(struct kunit
> *test)
> {
> struct binder_alloc_test *priv = test->priv;
> size_t end_offset[BUFFER_NUM];
> + int alignments[BUFFER_NUM];
> + unsigned long failures = 0;
> + unsigned long runs = 0;
>
> - gen_buf_offsets(test, &priv->alloc, end_offset, 0);
> + gen_buf_offsets(test, &priv->alloc, end_offset, alignments, &runs,
> + &failures, 0);
>
> - KUNIT_EXPECT_EQ(test, binder_alloc_test_failures, 0);
> + KUNIT_EXPECT_EQ(test, runs, TOTAL_EXHAUSTIVE_CASES);
> + KUNIT_EXPECT_EQ(test, failures, 0);
> }
>
> /* ===== End test cases ===== */
> --
> 2.50.0.727.gbf7dc18ff4-goog
>
Otherwise looks good to me.
--
Kees Cook
