container_of macro...

[Chris M. Thomasson]

Its been a while since I used the container_of macro, however, it can
come in handy wrt creating linked data-structures. Here is an example I
coded up, just to see if I could do it from scratch, after all these years:
________________________________
#include <stdio.h>
#include <stddef.h>
#include <assert.h>


struct ct_slist_node
{
struct ct_slist_node* next;
};

struct ct_slist
{
struct ct_slist_node* head;
};

#define ct_container_of(m_ptr, m_type, m_member) \
((void*)((unsigned char*)(m_ptr) - offsetof(m_type, m_member)))


void
ct_slist_push(
struct ct_slist* self,
struct ct_slist_node* node
) {
node->next = self->head;
self->head = node;
}

struct ct_slist_node*
ct_slist_pop(
struct ct_slist* self
) {
struct ct_slist_node* node = self->head;
if (node) self->head = node->next;
return node;
}



struct foo
{
int a;
struct ct_slist_node next;
char b;
long c;
};



int main(void)
{
struct foo foo;
struct foo* pfoo = ct_container_of(&foo.next, struct foo, next);

printf("&foo.next = %p\n", &foo.next);
printf("&foo = %p\n", &foo);
printf("pfoo = %p\n", pfoo);

assert(&foo == pfoo);

{
#define N 42

struct foo foo[N];
struct ct_slist slist = { NULL };

printf("\npush...\n");
for (unsigned int i = 0; i < N; ++i)
{
printf("&foo[%u] = %p\n", i, foo + i);
ct_slist_push(&slist, &foo[i].next);
}

printf("\npop...\n");
for (unsigned int i = 0; i < N; ++i)
{
struct ct_slist_node* node = ct_slist_pop(&slist);
struct foo* pfoo = ct_container_of(node, struct foo, next);
printf("pfoo = %p = &foo[%u - %u - 1] = %p\n", pfoo, N, i,
&foo[N - i - 1]);
assert(pfoo == &foo[N - i - 1]);
}
}

return 0;
}
________________________________

How many people here use it?

[Öö Tiib]

On Tuesday, 9 March 2021 at 03:24:29 UTC+2, Chris M. Thomasson wrote:
> Its been a while since I used the container_of macro, however, it can
> come in handy wrt creating linked data-structures.

...

> #define ct_container_of(m_ptr, m_type, m_member) \
> ((void*)((unsigned char*)(m_ptr) - offsetof(m_type, m_member)))

Why not ...

#define ct_container_of(m_ptr, m_type, m_member) \
((m_type*)((unsigned char*)(m_ptr) - offsetof(m_type, m_member)))

... ? Rest of your code seems to expect m_type* out of that macro.

> How many people here use it?

I prefer just to copy-paste such code in C. Too clever macros tend
to pointlessly hinder next maintainers. They may need to add some new
function. Say foo_slist_erase_if_magenta() that erases all magenta foos
from list. This is usually trivial inline to write with copy-paste "foo slist"
accessories. The generic slist macros (used maximally once per project)
however may just confuse how to do it and so waste time.

[Kaz Kylheku]

On 2021-03-09, Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
> How many people here use it?

If you put the contained structure as the first member, you don't need
this; just a straight cast.

That takes care of probably more than the proverbial 95% of the
situations.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[Ben Bacarisse]

Kaz Kylheku <563-36...@kylheku.com> writes:

> On 2021-03-09, Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>> How many people here use it?
>
> If you put the contained structure as the first member, you don't need
> this; just a straight cast.

But you then can't write generic list algorithms, no?

> That takes care of probably more than the proverbial 95% of the
> situations.

Maybe such generic code is all in the 5%. I would argue percentages if
that's what you are saying.

--
Ben.

[Kaz Kylheku]

On 2021-03-09, Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
> Kaz Kylheku <563-36...@kylheku.com> writes:
>
>> On 2021-03-09, Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>>> How many people here use it?
>>
>> If you put the contained structure as the first member, you don't need
>> this; just a straight cast.
>
> But you then can't write generic list algorithms, no?

The intrusive container approach for generic containers, though it has
some nice characteristics with regard to memory allocation, is very
limited.

Firstly, by its very nature, it is incompatible with functional
programming. Objects must be mutated in order to put them into a list.

Secondly, once an object is on a list, it cannot be simultaneously put
into another list. (Unless, of course, it has more list nodes, which
is where we run into container_of).

The "object on one list at a time" has basically one text book use case:
the OS scheduler. A process in some state, one state at a time. States
have queues associated with them, and so a process moves between
different queues. For that, it can have links built into it, and so
no allocation takes place.

This is not a "generic container" situation though.

>> That takes care of probably more than the proverbial 95% of the
>> situations.
>
> Maybe such generic code is all in the 5%. I would argue percentages if
> that's what you are saying.

If I needed a generic container with multiple intrusive node links
today, I would spend the bytes and put the numeric offset into the link
node structure.

The offsetof macro is error prone. If a structure has several list
nodes:

struct foo {
lnode_t anode;
lnode_t bnode;
lnode_t cnode;
}

If we have a pointer ptr, to say, the cnode, but we accidentally do
this:

container_of(ptr, struct foo, bnode)

we have a critical error: the returned pointer is wrong; it points
somewhere before the structure.

If node has an offset to the parent structure, we can have a different
inline function or macro for that, just:

container_of(ptr, struct foo)

this retrieves ptr->offset, subtracts it from the char * version of ptr,
and casts it to struct foo *.

That also allows us to write generic code (which we should be concerned
with if our motivation is "generic containers"). We can write a single
common function which takes a pointer to any list node, whether it be
the object's anode, bnode or cathode (EE joke, sorry) and easily
converts it to the struct foo *, to then operate on that object.

We correctly initialize ptr->offset in one place.

We could have a ptr->parent poiner instead, but ptr->offset has
the virtue of being relative. If we assign one initialized structure
to another, the offsets work correctly in the copied structure,
whereas back-pointers will not:

*pfooa = *pfoob;

Offsets can be packed into smaller fields though. E.g. on 64 bit,
we burn 8 bytes for a parent pointer, but there could be situations
in which a smaller type could be used for an offset to some
advantage, alignment of surroundings permitting.

[William Ahern]

Chris M. Thomasson <chris.m.t...@gmail.com> wrote:

> Its been a while since I used the container_of macro, however, it can
> come in handy wrt creating linked data-structures. Here is an example I
> coded up, just to see if I could do it from scratch, after all these years:

The biggest problem with container_of is that it's not typesafe. I never
understood why the GNU and Linux ecosystem adopted that approach instead of
the classic BSD macros:

https://cvsweb.openbsd.org/cgi-bin/cvsweb/~checkout~/src/sys/sys/queue.h

But today even glibc and musl libc provide <sys/queue.h>. As do AIX,
Solaris, and QNX, though AIX only provides LIST and TAILQ. I'm not sure when
these environments added <sys/queue.h>, but they're there now, so I can't
complain. Perhaps Windows will finally add them, making them de facto
standard interfaces[1], though being of BSD heritage neither WG14 nor POSIX
are likely to give them serious consideration. Too practical.

[1] No accounting for all the other proprietary embedded environments,
though importing queue.h from one of the BSDs is hardly burdensome. It's
recognizing the need that's apparently burdensome, given the history of NIH
reinvention.

[Kaz Kylheku]

On 2021-03-10, William Ahern <wil...@25thandClement.com> wrote:
> Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>> Its been a while since I used the container_of macro, however, it can
>> come in handy wrt creating linked data-structures. Here is an example I
>> coded up, just to see if I could do it from scratch, after all these years:
>
> The biggest problem with container_of is that it's not typesafe. I never
> understood why the GNU and Linux ecosystem adopted that approach instead of
> the classic BSD macros:
>
> https://cvsweb.openbsd.org/cgi-bin/cvsweb/~checkout~/src/sys/sys/queue.h

There is virtually no difference; that approach is exactly the
container_of approach.

Like container_of, there are macros which are given the name of a
structure member and calcluate offsets.

For instance:

SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);

looks to me exactly like doing:

for_each_node(N, HEAD) {
TYPE *var = container_of(TYPE, N, NAME);

}

we walk over a list, and then map each node back to a containing
object by assuming it is embedded as a member called NAME.

[Chris M. Thomasson]

On 3/9/2021 2:06 AM, Öö Tiib wrote:
> On Tuesday, 9 March 2021 at 03:24:29 UTC+2, Chris M. Thomasson wrote:
>> Its been a while since I used the container_of macro, however, it can
>> come in handy wrt creating linked data-structures.
>
> ...
>
>> #define ct_container_of(m_ptr, m_type, m_member) \
>> ((void*)((unsigned char*)(m_ptr) - offsetof(m_type, m_member)))
>
> Why not ...
>
> #define ct_container_of(m_ptr, m_type, m_member) \
> ((m_type*)((unsigned char*)(m_ptr) - offsetof(m_type, m_member)))
>
> ... ?

Well, I have no excuse. Typed out this code rather quickly. Using
(m_type*) would help.

> Rest of your code seems to expect m_type* out of that macro.

Yes it does. Fwiw, Microsoft has it in their CONTAINING_RECORD macro.

[Chris M. Thomasson]

On 3/9/2021 7:59 AM, Kaz Kylheku wrote:
> On 2021-03-09, Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>> How many people here use it?
>
> If you put the contained structure as the first member, you don't need
> this; just a straight cast.

Indeed!

>
> That takes care of probably more than the proverbial 95% of the
> situations.
>

Well, the macro gives one the flexibility to add a node to an existing
structure that might not like replacing its existing first member.

[Chris M. Thomasson]

On 3/9/2021 6:56 PM, William Ahern wrote:
> Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>> Its been a while since I used the container_of macro, however, it can
>> come in handy wrt creating linked data-structures. Here is an example I
>> coded up, just to see if I could do it from scratch, after all these years:
>
> The biggest problem with container_of is that it's not typesafe.

Agreed. But then again anything that returns void* is not typesafe.

[Chris M. Thomasson]

Big time! The programmer needs to be very careful, indeed. But then
again, this is C.

>
> If node has an offset to the parent structure, we can have a different
> inline function or macro for that, just:
>
> container_of(ptr, struct foo)
>
> this retrieves ptr->offset, subtracts it from the char * version of ptr,
> and casts it to struct foo *.

Well, please excuse my ignorance here, but are you suggesting that a
node store its offset to its containing structure? Humm... That might
not be okay on space constrained systems?

[William Ahern]

The difference is that container_of takes an explicit type name and casts
the pointer in a way that almost completely subverts type checking. Your
pseudocode above obscures that critical difference.

In general in <sys/queue.h> only *LIST_HEAD and *LIST_ENTRY take explicit
type names. They generate struct definitions which the rest of the API is
carefully designed to avoid casting into oblivion. Almost everywhere else
you only pass object pointers and a field name. Any type mismatches are
caught by the compiler.

The exception is TAILQ, where TAILQ_LAST, TAILQ_PREV, and
TAILQ_FOREACH_REVERSE takes the type name of head. I used to prefer CIRCLEQ
as it offered all the same interfaces without requiring a type name, but the
BSDs removed CIRCLEQ some years ago when it was realized that the
implementation required violating aliasing rules. Fortunately it's rare that
I ever need reverse iteration.

container_of could be made more type safe by dropping the type name argument
and relying on __typeof__ instead. I never understood why it didn't
considering its provenance--Linux kernel hackerdom, where GCC extensions are
commonly relied upon. Most major compilers have supported GCC's __typeof__
extension for decades, including MSVC, SunPro, and xlC. (CIRCLEQ also could
have been rehabilitated using __typeof__, but the BSDs decided to just drop
it entirely.)

[Jim]

to nobody in particular,

the 2 arg version of this macro is junk. it cannot do any type checks.
linux's version has 3 args,
lines 20,21 force compiler type checks.
type is usually 'struct foo' of some flavor,
member must be in it, and thus has some offset from it.
no code is generated for the enforcement, and thats cool.


scripts/kconfig/list.h
19:#define container_of(ptr, type, member) ({ \
20- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
21- (type *)( (char *)__mptr - offsetof(type,member) );})
22-
23-

[tylo]

The problem with this approach is that ({ ... }) is not standard C, and typeof becomes standard in C23.
Here is how to write it type safely, even in C89:

#define container_of(ptr, type, member) \
((type*)((char*)(ptr) + 0*sizeof((ptr) == &((type*)0)->member) - offsetof(type, member)))

[James Kuyper]

On 10/31/22 06:27, tylo wrote:
..

> #define container_of(ptr, type, member) \
> ((type*)((char*)(ptr) + 0*sizeof((ptr) == &((type*)0)->member) -
offsetof(type, member)))

(type*)0->member dereferences a null pointer. As a result, such code has
undefined behavior. On many systems it will do precisely what you
expect, but it is not required to do that.

[Ben Bacarisse]

James Kuyper <james...@alumni.caltech.edu> writes:

> On 10/31/22 06:27, tylo wrote:
> ..
>> #define container_of(ptr, type, member) \
>> ((type*)((char*)(ptr) + 0*sizeof((ptr) == &((type*)0)->member) -
> offsetof(type, member)))
>
> (type*)0->member dereferences a null pointer. As a result, such code has
> undefined behavior.

It's in the unevaluated operand of the sizeof operator. The comparison
is there just to provoke type-checking (the main thrust of this
subthread) and I imagine the sizeof is there to avoid the implied UB.

--
Ben.

[tylo]

tirsdag 1. november 2022 kl. 12:06:17 UTC+1 skrev Ben Bacarisse:
> > (type*)0->member dereferences a null pointer. As a result, such code has
> > undefined behavior.
> It's in the unevaluated operand of the sizeof operator. The comparison
> is there just to provoke type-checking (the main thrust of this
> subthread) and I imagine the sizeof is there to avoid the implied UB.
>
> --
> Ben.

Yes, sizeof is also there to avoid ptr being evaluated twice.

Although not relevant here as sizeof() doesn't evaluate its argument, the expression &((Type*)0)->member evaluates to a compile time constant even by non-optimizing compilers, as they always do basic constant folding optimizations.

[Ben Bacarisse]

tylo <tylo...@gmail.com> writes:

> tirsdag 1. november 2022 kl. 12:06:17 UTC+1 skrev Ben Bacarisse:
>> > (type*)0->member dereferences a null pointer. As a result, such code has
>> > undefined behavior.
>> It's in the unevaluated operand of the sizeof operator. The comparison
>> is there just to provoke type-checking (the main thrust of this
>> subthread) and I imagine the sizeof is there to avoid the implied UB.
>>
>

> Yes, sizeof is also there to avoid ptr being evaluated twice.
>
> Although not relevant here as sizeof() doesn't evaluate its argument,
> the expression &((Type*)0)->member evaluates to a compile time
> constant even by non-optimizing compilers, as they always do basic
> constant folding optimizations.

Compilers are permitted to do what they like with that expression (if it
is in a context where it is evaluated) because it the behaviour is
formally undefined. You can's assume anything about the value.

--
Ben.

[David Brown]

That is a big assumption - not one you should rely on.

You can't assume non-optimising compilers (or optimising compilers where
optimisation is not enabled) do any kind of optimisation at all, even
the simplest ones. Equally, you can't assume that they will /not/ do
any given optimisations. I've seen compilers that will do "x = 0 + 1;"
at run-time when optimisations are disabled, and I've seen compilers
that will eliminate unreachable code on the assumption that signed
integer arithmetic never overflows even when optimisations are disabled.

Always write code in a way that will be correct and safe (including no
undefined behaviour) regardless of any optimisations.

[Andrey Tarasevich]

On 11/2/2022 7:15 AM, tylo wrote:
> tirsdag 1. november 2022 kl. 12:06:17 UTC+1 skrev Ben Bacarisse:
>>> (type*)0->member dereferences a null pointer. As a result, such code has
>>> undefined behavior.
>> It's in the unevaluated operand of the sizeof operator. The comparison
>> is there just to provoke type-checking (the main thrust of this
>> subthread) and I imagine the sizeof is there to avoid the implied UB.
>>
>> --
>> Ben.
>
> Yes, sizeof is also there to avoid ptr being evaluated twice.

No. It is there to inject a dummy comparison into an expression.

> Although not relevant here as sizeof() doesn't evaluate its argument, the expression &((Type*)0)->member evaluates to a compile time constant even by non-optimizing compilers, as they always do basic constant folding optimizations.

No, no, and no.

Firstly, what is a constant expression and what isn't is defined by the
language spec. It does not depend on any compiler optimizations.

Secondly, the above expression does not evaluate to a "compile time
constant". It doesn't need to and it doesn't really matter what it
evaluates to. It is not evaluated at all. It is there for the sole
purpose of producing an invalid comparison

(ptr) == &((type*)0)->member

and therefore a compiler diagnostic in case of type mismatch.

--
Best regards,
Andrey

[Richard Damon]

The arguement of sizeof is NOT evaluated, (except to compute the
type/size of an array, which isn't done here) and that is NOT an
"optimization, so it can't cause undefined behavior.

The type algerbra still happens, and that is all that matters for
determining of the == will create an error.

[Ben Bacarisse]

Richard Damon <Ric...@Damon-Family.org> writes:

> On 11/2/22 12:00 PM, Ben Bacarisse wrote:
>> tylo <tylo...@gmail.com> writes:
>>
>>> tirsdag 1. november 2022 kl. 12:06:17 UTC+1 skrev Ben Bacarisse:
>>>>> (type*)0->member dereferences a null pointer. As a result, such code has
>>>>> undefined behavior.
>>>> It's in the unevaluated operand of the sizeof operator. The comparison
>>>> is there just to provoke type-checking (the main thrust of this
>>>> subthread) and I imagine the sizeof is there to avoid the implied UB.
>>>>
>>>
>>> Yes, sizeof is also there to avoid ptr being evaluated twice.
>>>
>>> Although not relevant here as sizeof() doesn't evaluate its argument,
>>> the expression &((Type*)0)->member evaluates to a compile time
>>> constant even by non-optimizing compilers, as they always do basic
>>> constant folding optimizations.
>>
>> Compilers are permitted to do what they like with that expression (if it
>> is in a context where it is evaluated) because it the behaviour is
>> formally undefined. You can's assume anything about the value.
>
> The arguement of sizeof is NOT evaluated,

I never said it was. In fact I made this same point earlier. Also (as
far as I can tell) tylo also knows this. I was addressing a claim tylo
make about what a particular expression evaluates to.

--
Ben.

[Richard Damon]

But sizeof returns the size of the type, so sizeof in that expression
will ALWAYS return sizeof(int), as that is the ONLY type that the ==
operator returns in C. If the two parametes of the == operator have
incompatible type, we also get a mandatory diagnostic (which might make
the value mute).

Since the value of sizeof was then multiplied by 0, that part of the
expression will always be 0.

This says the express has the value of:

((type*)((char*)(ptr) - offsetof(type, member)))

(There may be an ineffectual subtraction of a 0 value in the calculation)

Which, if "ptr" is actuall a pointer to the member "member" in a struct
"type", will give you a pointer to the "type" object.

[James Kuyper]

I hadn't figured out what the macro was actually supposed to do, and
there was enough distance between the expression and the sizeof, and
enough parenthesis, to confuse me on that point. Sorry for the noise.

[James Kuyper]

On 11/2/22 21:00, Richard Damon wrote:
> On 11/2/22 12:00 PM, Ben Bacarisse wrote:
>> tylo <tylo...@gmail.com> writes:

..

>>> Although not relevant here as sizeof() doesn't evaluate its argument,
>>> the expression &((Type*)0)->member evaluates to a compile time
>>> constant even by non-optimizing compilers, as they always do basic
>>> constant folding optimizations.
>>
>> Compilers are permitted to do what they like with that expression (if it
>> is in a context where it is evaluated) because it the behaviour is
>> formally undefined. You can's assume anything about the value.
>>
>
> The arguement of sizeof is NOT evaluated, (except to compute the
> type/size of an array, which isn't done here) and that is NOT an
> "optimization, so it can't cause undefined behavior.

Ben was responding to an incorrect claim about what that expression
would evaluate to if it had not occurred inside a sizeof expression.

[Chris M. Thomasson]

It's used a lot in the Linux Kernel. Microsoft has one:

https://learn.microsoft.com/en-us/windows/win32/api/ntdef/nf-ntdef-containing_record

[Chris M. Thomasson]

Iirc, mainly used in intrusive data-structures.

[Ben Bacarisse]

Yes, the value of the '0*sizeof ...' sub-expression in not the point. Its
purpose is to provoke a diagnostic if 'ptr' is of the wrong type.

I think we have our wires crossed because you seem to be disagreeing
with something, but I can't tell what.

I thought that tylo was making a claim about how &((Type*)0)->member
will be evaluated, and since he or she seems to know that it's not
evaluated in the given context I took the remark to be a general one
about the evaluation of that expression when it is, indeed, evaluated.

My point about /that/ expression is that you can't assume what tylo
seemed to be assuming about its evaluation.

> This says the express has the value of:
>
> ((type*)((char*)(ptr) - offsetof(type, member)))
>
> (There may be an ineffectual subtraction of a 0 value in the calculation)
>
> Which, if "ptr" is actuall a pointer to the member "member" in a
> struct "type", will give you a pointer to the "type" object.

Yes. That version had already been posted (I think). The new post was
to add a type check, hence the zero-valued extra expression.

--
Ben.

[tylo]

I wrote:
> Although not relevant here as sizeof() doesn't evaluate its argument, the expression &((Type*)0)->member evaluates to a compile time constant even by non-optimizing compilers, as they always do basic constant folding optimizations.

Sorry about the fuzz I made with this comment, which is was incorrect and pointed out by a few of you.

Just to add, there is an alternative way to write this macro, although I think it is equivalent in the end. Although the 0-dereference is not "protected" by sizeof, it is guaranteed never to be executed and therefore not UB:

#define container_of(ptr, type, member) \
((type*)((char*)(1 ? (ptr) : &((type*)0)->member) - offsetof(type, member)))

[Tim Rentsch]

Forgive me for making an obvious point here: _shouldn't_ assume
anything about the value. People can make unwarranted assumptions
about the value, and some people do, even though they shouldn't,
and that's the problem.

[Tim Rentsch]

Andrey Tarasevich <andreyta...@hotmail.com> writes:

> On 11/2/2022 7:15 AM, tylo wrote:
>
>> tirsdag 1. november 2022 kl. 12:06:17 UTC+1 skrev Ben Bacarisse:
>>
>>>> (type*)0->member dereferences a null pointer. As a result, such
>>>> code has undefined behavior.
>>>
>>> It's in the unevaluated operand of the sizeof operator. The
>>> comparison is there just to provoke type-checking (the main thrust
>>> of this subthread) and I imagine the sizeof is there to avoid the
>>> implied UB.
>>>
>>> -- >> Ben.
>>
>> Yes, sizeof is also there to avoid ptr being evaluated twice.
>
> No. It is there to inject a dummy comparison into an expression.
>
>> Although not relevant here as sizeof() doesn't evaluate its
>> argument, the expression &((Type*)0)->member evaluates to a
>> compile time constant even by non-optimizing compilers, as they
>> always do basic constant folding optimizations.
>
> No, no, and no.
>
> Firstly, what is a constant expression and what isn't is defined by

> the language spec. [...]

>
> Secondly, the above expression does not evaluate to a "compile time

> constant". [...]

This response isn't exactly right. Both gcc and clang accept an
expression of the form &((Type*)0)->member as a constant expression.
In particular, a source file

typedef struct { int member; } Type;

const int *x = & ((Type*)0)->member;

is accepted, in a conforming mode, including -pedantic-errors, and
without causing any diagnostics (and indeed the value given to x is
a compile-time constant). Such expressions don't /have/ to be
constant expressions but they /can/ be constant expressions - the C
standard explicitly allows additional forms of constant expressions,
beyond those described in the standard, to be accepted by a
conforming implementation. Similarly, the value of the expression
doesn't /have/ to have any particular value but it /can/ be given
the value most people would expect. Certainly it is true that the
previously quoted expression /might not/ evaluate to a compile time
constant, but saying it /does not/ evaluate to a compile time
constant is wrong: sometimes it does, even if under different
circumstances it would not.