On Thu, Mar 10, 2022 at 3:54 PM Michał Mirosław <[email protected]> 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_offset;
}
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
On Thu, Mar 10, 2022 at 04:46:33PM -0800, Linus Torvalds wrote:
> On Thu, Mar 10, 2022 at 3:54 PM Micha? Miros?aw <[email protected]> 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.
[...]
It seems that it's not that bad if we don't require checking whether
a list_head of an entry is only ever used with a single list parent. The
source type is not needed for the macros, and it turns out that pre-declaring
the offset type is also not needed.
I compile-tested the code below on godbolt.org with -std=c11:
struct list_head {
struct list_head *prev, *next;
};
#define offsetof __builtin_offsetof
#define typeof __typeof
#define list_traversal_head(name,type,target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
char (*name##_list_head_offset)[offsetof(type, target_member)]; \
}
#define self_list_ref_offset_type(type,target_member) \
type##__##target_member##__offset__
#define define_self_list_ref_offset(type,target_member) \
self_list_ref_offset_type(type,target_member) \
{ char ignoreme__[offsetof(type, target_member)]; }
#define self_list_traversal_head(name,type,target_member) \
union { \
struct list_head name; \
type *name##_traversal_type; \
self_list_ref_offset_type(type,target_member) *name##_list_head_offset; \
}
#define list_traversal_entry(ptr, head) \
(typeof(*head##_traversal_type))((void *)ptr - sizeof(**head##_list_head_offset))
#define list_traversal_entry_head(ptr, head) \
((struct list_head *)((void *)ptr + sizeof(**head##_list_head_offset)))
#define list_traversal_entry_is_head(ptr, head) \
(list_traversal_entry_head(ptr, head) == (head))
#define list_traversal_next_entry(ptr, head) \
list_traversal_entry(list_traversal_entry_head(ptr, head)->next, head)
#define list_traverse(pos, head) \
for (typeof(*head##_traversal_type) pos = list_traversal_entry((head)->next, head); \
!list_traversal_entry_is_head(pos, head); \
pos = list_traversal_next_entry(pos,head))
struct entry {
self_list_traversal_head(self_list, struct entry, child_head);
struct list_head child_head;
};
define_self_list_ref_offset(struct entry, child_head);
void bar(struct entry *b);
void foo(struct entry *a)
{
list_traverse(pos, &a->self_list) {
bar(pos);
}
}
--
Micha? Miros?aw
On Sat, Mar 12, 2022 at 2:24 AM Michał Mirosław <[email protected]> wrote:
>
> The source type is not needed for the macros [..]
Ahh. Yeah, as long as we don't do typedefs, it looks like we don't
need to pre-declare the member access types.
I expected that to be required, because function declarations taking
arguments need it, but that's because they create their own scope.
Just doing it in a regular struct (or in this case union) declaration
is fine.
So we would only need that post-declaration.
That said, your naming is wrong. It's not just about "self". It's any
case where the type we iterate over is declared after the type that
has the head.
So I suspect it would be a lot better to just always do it, and not do
that "self vs non-self" distinction.
Linus