Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list

[David Gow]

On Mon, Oct 7, 2019 at 6:03 PM Kees Cook <keescook@xxxxxxxxxxxx> wrote:
(...)
> > +
> > +static void list_init_test(struct kunit *test)
> > +{
> > +     /* Test the different ways of initialising a list. */
> > +     struct list_head list1 = LIST_HEAD_INIT(list1);
> > +     struct list_head list2;
> > +     LIST_HEAD(list3);
> > +
> > +     INIT_LIST_HEAD(&list2);
>
> Can you also add different storage locations and initial contents tests?
> For example:
>
>         struct list_head *list4;
>         struct list_head *list5;
>
>         list4 = kzalloc(sizeof(*list4));
>         INIT_LIST_HEAD(list4);
>
>         list5 = kmalloc(sizeof(*list5));
>         memset(list4, 0xff, sizeof(*list5));
>         INIT_LIST_HEAD(list5);
>
>
>         KUNIT_EXPECT_TRUE(test, list_empty_careful(&list4));
>         KUNIT_EXPECT_TRUE(test, list_empty_careful(&list5));
>
>         kfree(list4);
>         kfree(list5);
>
> Then we know it's not an accident that INIT_LIST_HEAD() works when both
> all-zeros and all-0xFF initial contents are there. :)

Will do.

> > +static void list_entry_test(struct kunit *test)
> > +{
> > +     struct list_test_struct test_struct;
>
> I guess this is not a missing initialization here because this is just
> testing the container_of() wrapper macro?
>

Yeah: we shouldn't be doing any memory accesses here, just the pointer
manipulation, so it shouldn't matter.
I can add a comment pointing this out, or just initialise it anyway.

> > +
> > +     KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), struct list_test_struct, list));
> > +}
> > +
> > +static void list_first_entry_test(struct kunit *test)
> > +{
> > +     struct list_test_struct test_struct1, test_struct2;
> > +     static LIST_HEAD(list);
>
> This is this static?
>

Oops, this doesn't need to be static. I'll fix this (and the others)
for the next version.

> > +static void list_for_each_test(struct kunit *test)
> > +{
> > +     struct list_head entries[3], *cur;
> > +     LIST_HEAD(list);
> > +     int i = 0;
> > +
> > +     list_add_tail(&entries[0], &list);
> > +     list_add_tail(&entries[1], &list);
> > +     list_add_tail(&entries[2], &list);
> > +
> > +     list_for_each(cur, &list) {
> > +             KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
> > +             i++;
> > +     }
> > +
> > +     KUNIT_EXPECT_EQ(test, i, 3);
> > +}
> > +
> > +static void list_for_each_prev_test(struct kunit *test)
> > +{
> > +     struct list_head entries[3], *cur;
> > +     LIST_HEAD(list);
> > +     int i = 2;
> > +
> > +     list_add_tail(&entries[0], &list);
> > +     list_add_tail(&entries[1], &list);
> > +     list_add_tail(&entries[2], &list);
> > +
> > +     list_for_each_prev(cur, &list) {
> > +             KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
> > +             i--;
> > +     }
> > +
> > +     KUNIT_EXPECT_EQ(test, i, -1);
>
> Both of these tests test that the list contained the correct number of
> entries, not that anything about ordering was established. I would load
> values into these with the list_test_struct and test that the counting
> matches the expected ordering.
>

These tests do check the order of the entries (the order of the list
should match the order of the entries array, and KUNIT_EXPECT_PTR_EQ()
is verifying that the entries[i] is correct).
It would be possible to actually use list_test_struct like with the
list_for_each_entry tests, but since list_for_each just returns the
list_head, it didn't seem useful, so long as the list_head pointers
match.

> > +}
> > +
> > +static void list_for_each_safe_test(struct kunit *test)
> > +{
> > +     struct list_head entries[3], *cur, *n;
> > +     LIST_HEAD(list);
> > +     int i = 0;
> > +
> > +
> > +     list_add_tail(&entries[0], &list);
> > +     list_add_tail(&entries[1], &list);
> > +     list_add_tail(&entries[2], &list);
> > +
> > +     list_for_each_safe(cur, n, &list) {
> > +             KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
> > +             list_del(&entries[i]);
> > +             i++;
> > +     }
> > +
> > +     KUNIT_EXPECT_EQ(test, i, 3);
>
> I would expect an is_empty() test here too.
>

Will do.

> > +}
> > +
> > +static void list_for_each_prev_safe_test(struct kunit *test)
> > +{
> > +     struct list_head entries[3], *cur, *n;
> > +     LIST_HEAD(list);
> > +     int i = 2;
> > +
> > +     list_add_tail(&entries[0], &list);
> > +     list_add_tail(&entries[1], &list);
> > +     list_add_tail(&entries[2], &list);
> > +
> > +     list_for_each_prev_safe(cur, n, &list) {
> > +             KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
> > +             list_del(&entries[i]);
> > +             i--;
> > +     }
>
> Same thing here.
>

Will do.

> > +static void list_for_each_entry_test(struct kunit *test)
> > +{
> > +     struct list_test_struct entries[5], *cur;
> > +     static LIST_HEAD(list);
> > +     int i = 0;
> > +
> > +     for (i = 0; i < 5; ++i) {
> > +             entries[i].data = i;
> > +             list_add_tail(&entries[i].list, &list);
> > +     }
> > +
> > +     i = 0;
> > +
> > +     list_for_each_entry(cur, &list, list) {
> > +             KUNIT_EXPECT_EQ(test, cur->data, i);
> > +             i++;
> > +     }
> > +}
> > +
> > +static void list_for_each_entry_reverse_test(struct kunit *test)
> > +{
> > +     struct list_test_struct entries[5], *cur;
> > +     static LIST_HEAD(list);
> > +     int i = 0;
> > +
> > +     for (i = 0; i < 5; ++i) {
> > +             entries[i].data = i;
> > +             list_add_tail(&entries[i].list, &list);
> > +     }
> > +
> > +     i = 4;
> > +
> > +     list_for_each_entry_reverse(cur, &list, list) {
> > +             KUNIT_EXPECT_EQ(test, cur->data, i);
> > +             i--;
> > +     }
>
> Oh! Here is the data test. Why keep these separate? You could combine
> the counting tests with these?
>
> One thing to consider adding is a short comment above each test to
> clarify the test intention. While these are relatively simple tests, it
> could clarify things like "only testing counts here" or "similar to
> test_foo(), this adds in ordering verification", etc.
>

The idea here was to have a separate test for each function/macro
being tested. This hopefully should make it easier to narrow down
where test failures are. In this case, the tests using
list_test_struct are here because list_for_each_entry() does the
implicit container_of(), so testing it properly requires the test
struct. As above, the list_for_each() tests do actually check the
order, so it's probably worth adding a check for the count to these
tests, too.

There are definitely a few places where extra comments make sense. In
general, for these tests at least, the purpose of each test is to test
the function/macro it's named after, ideally reasonably thoroughly. My
feeling is that, given that, it's more useful to call out explicitly
if something obvious isn't tested (such as the
list_empty_careful_test(), perhaps, which doesn't verify concurrent
access from multiple threads).

Cheers,
-- David