Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #159250 > unrolled thread

container_of macro...

Back to article view | Back to comp.lang.c

Contents

  container_of macro... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-08 17:24 -0800
    Re: container_of macro... Öö Tiib <ootiib@hot.ee> - 2021-03-09 02:06 -0800
      Re: container_of macro... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 17:02 -0800
    Re: container_of macro... Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-09 15:59 +0000
      Re: container_of macro... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-09 17:35 +0000
        Re: container_of macro... Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-09 17:51 +0000
          Re: container_of macro... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 17:13 -0800
      Re: container_of macro... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 17:05 -0800
    Re: container_of macro... William Ahern <william@25thandClement.com> - 2021-03-09 18:56 -0800
      Re: container_of macro... Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-10 03:47 +0000
        Re: container_of macro... William Ahern <william@25thandClement.com> - 2021-03-12 17:01 -0800
          Re: container_of macro... Jim <jim.cromie@gmail.com> - 2021-03-16 22:14 -0700
      Re: container_of macro... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 17:07 -0800

#159250 — container_of macro...

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?

[toc] | [next] | [standalone]

#159253

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. 

[toc] | [prev] | [next] | [standalone]

#159279

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.

>   
>> 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.
> 

[toc] | [prev] | [next] | [standalone]

#159254

On 2021-03-09, Chris M. Thomasson <chris.m.thomasson.1@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

[toc] | [prev] | [next] | [standalone]

#159259

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

> On 2021-03-09, Chris M. Thomasson <chris.m.thomasson.1@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.

[toc] | [prev] | [next] | [standalone]

#159261

On 2021-03-09, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>
>> On 2021-03-09, Chris M. Thomasson <chris.m.thomasson.1@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.

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

[toc] | [prev] | [next] | [standalone]

#159282

On 3/9/2021 9:51 AM, Kaz Kylheku wrote:
> On 2021-03-09, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>
>>> On 2021-03-09, Chris M. Thomasson <chris.m.thomasson.1@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.

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?


> 
> 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.
> 

[toc] | [prev] | [next] | [standalone]

#159280

On 3/9/2021 7:59 AM, Kaz Kylheku wrote:
> On 2021-03-09, Chris M. Thomasson <chris.m.thomasson.1@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.

[toc] | [prev] | [next] | [standalone]

#159267

Chris M. Thomasson <chris.m.thomasson.1@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.

[toc] | [prev] | [next] | [standalone]

#159268

On 2021-03-10, William Ahern <william@25thandClement.com> wrote:
> Chris M. Thomasson <chris.m.thomasson.1@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.


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

[toc] | [prev] | [next] | [standalone]

#159318

Kaz Kylheku <563-365-8930@kylheku.com> wrote:
> On 2021-03-10, William Ahern <william@25thandClement.com> wrote:
>> Chris M. Thomasson <chris.m.thomasson.1@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.

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.)

[toc] | [prev] | [next] | [standalone]

#159389

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-

[toc] | [prev] | [next] | [standalone]

#159281

On 3/9/2021 6:56 PM, William Ahern wrote:
> Chris M. Thomasson <chris.m.thomasson.1@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.


> 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.
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web