Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18;
MIME-Version: 1.0
References: <CAHk-=wiacQM76xec=Hr7cLchVZ8Mo9VDHmXRJzJ_EX4sOsApEA@mail.gmail.com>
 <YiqPmIdZ/RGiaOei@qmqm.qmqm.pl>
In-Reply-To: <YiqPmIdZ/RGiaOei@qmqm.qmqm.pl>
From:   Linus Torvalds <torvalds@linux-foundation.org>
Date:   Thu, 10 Mar 2022 16:46:33 -0800
Message-ID: <CAADWXX-Pr-D3wSr5wsqTEOBSJzB9k7bSH+7hnCAj0AeL0=U4mg@mail.gmail.com>
Subject: Re: [PATCH 2/6] list: add new MACROs to make iterator invisiable
To:     =?UTF-8?B?TWljaGHFgiBNaXJvc8WCYXc=?= <mirq-linux@rere.qmqm.pl>
Cc:     Xiaomeng Tong <xiam0nd.tong@gmail.com>,
        Arnd Bergmann <arnd@arndb.de>,
        Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
        Jakob Koschel <jakobkoschel@gmail.com>,
        Jann Horn <jannh@google.com>,
        Kees Cook <keescook@chromium.org>,
        Linux Kbuild mailing list <linux-kbuild@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        Linux-MM <linux-mm@kvack.org>, Netdev <netdev@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Thu, Mar 10, 2022 at 3:54 PM Micha=C5=82 Miros=C5=82aw <mirq-linux@rere.=
qmqm.pl> wrote:
>
> If the macro implementation doesn't have to be pretty, maybe it could go
> a step further and remember the list_head's offset? That would look
> something like following (expanding on your patch; not compile tested):

Oh, I thought of it.

It gets complicated.

For example, a type that refers to a list of itself (and 'struct
task_struct' is one such example) cannot actually refer to that other
member name while declaring the head entry.

That's true even if the target member was declared before the head
that points to it - because the type just hasn't been fully
instantiated yet, so you can't refer to it AT ALL.

And even if that wasn't the case - and we could refer to previous
members during the initialization of subsequent ones - you'd still end
up with circular issues when one type has a list of another type,
which has a list of the first type.

Which I'm also fairly certain does happen.

With regular "circular pointers", the trick is to just pre-declare the type=
, ie

   struct second;

  struct first {
     .. define here, can use 'struct second *'
  };

  struct second {
    .. define here, can use 'struct first *'
  };

but that only works as long as you only use a pointer to that type.
You can't actually use 'offsetof()' of the members that haven't been
described yet.

Now, you can combine that "pre-declare the type" model with the "do
the offsetof later", but it gets nasty.

So I actually think it *can* be made to work, but not using your
"pointer to an array of the right size". I think you have to

 - pre-declare another type (the name needs to be a mix of both the
base type and the target type) with one macro

 - use a pointer to that as-yet undefined but declared type it in that
union defined by list_traversal_head() type

 - then, later on, when that target type has been fully defined, have
a *different* macro that then creates the actual type, which can now
have the right size, because the target has been declared

But that means that you can't really describe that thing inside just
the list_traversal_head() thing, you need *another* place that firsat
declares that type, and then a *third* place that defines that final
the type once all the pieces are in hand.

So it gets a lot uglier. But yes, I do believe it it's doable with
those extra steps.

The extra steps can at least be sanity-checked by that name, so
there's some "cross-verification" that you get all the pieces right,
but it ends up being pretty nasty.

It's extra nasty because that type-name ends up having to contain both
the source and destination types, and the member name. We could avoid
that before, because the 'name##_traversal_type' thing was entirely
internal to the source structure that contains the head, so we didn't
need to name that source structure - it was all very naturally
encapsulated.

So you'd have to do something like

  #define list_traversal_declare(src, head, dst, member) \
        struct src##_##head##_##dst##_##member##_offset_type

  #define list_traversal_defile(src, head, dst, member) \
        list_traversal_declare(src,head,dst,member) { \
                char[offsetof(struct dst, member); \
        }

   #define list_traversal_head(src, name, dst, member) \
    union {
        struct list_head name; \
        struct dst *name##_traversal_type; \
        list_traversal_declare(src,head,dst,member) *name##_target_type_off=
set;
    }

and then you'd have to do

    list_traversal_declare(task_struct, children, task_struct, sibling);

    struct task_struct {
        ...
        list_traversal_entry(task_struct, children, task_struct, sibling);
        ..
    };

    list_traversal_define(task_struct, children, task_struct, sibling);

and now list_traversal() itself can use
'sizeof(*name##_target_type_offset)' to get that offset.

NOTE! All of the above was written in my MUA with absolutely no
testing, just "I think something like this will work". And note how
really ugly it gets.

So. Doable? Yes. But at a pretty horrid cost - not just inside the
"list_traverse()" macro, but in that now the places declaring how the
list works get much much nastier.

                 Linus