Re: proposal: some pointer and arithmetic utilities

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 22 Mar, 2013, at 15:08 , Alan Barrett <apb%cequrux.com@localhost> wrote:
> I also don't see the point of container_of -- why not redesign the code so 
> that the the inner struct has a pointer to the outer struct?

I'm not sure I understand the point of adding a pointer to the
inner struct's allocation, and I'd like to understand this, but
I'm having a hard time framing my question succinctly.  I
have a number of data structure implementations which work
with an "inner struct", and I've designed APIs for reusable C library
functions like that for a long time.  The inner struct is a library type
which is taken as an argument and returned as a result of whatever
operations the library provides, and contains the data structure overhead
the function requires to avoid a separate memory allocation: say,
a link pointer for a queue implementation, or a couple of pointers
and some bookkeeping for a tree.  Passing pointers to the overhead
struct allows the library to make use of the overhead allocated
for it in the application structure, with compiler type checking,
without otherwise having to know anything about how the application
is using the library; the application and the data it is storing in
the library structure are opaque to the library to the full extent
possible, and the library functions are free to do what they must
do for the application without being burdened with anything the
application could do (or opt not to do) for itself.  I also believe
it is a better design if the overhead struct is treated as opaque
by the application; if the application never writes or reads
anything in the overhead structure (on purpose) it minimizes the
risk of the application writing or reading something in there at a
point where it is concurrently being examined or modified.  If there's
an extra pointer in the library overhead structure then it needs to
be passed in and out as an additional argument to the library
functional API and the library needs to fill it in, so the library
code can manage when the pointer is made available to the application.

What bothers me, however, is that I don't get what it is that paying
this cost in the library is buying.  Note that in the normal case
(which isn't what you necessarily should write the source code for
but is what you normally end up executing), if the application structure
you are designing needs one of these overhead structures you'll just
make life simple by placing it at the very top of the application
structure.  This means the extra pointer you are asking the library
to make additional space to store will, if cast to the overhead
structure type, be bit-for-bit identical to the pointer to the
overhead structure.  You are asking the library to spend space and
instructions to store an exact copy of the thing the library is
going to be storing already, so you're adding cost to the normal
case where there is no need to spend anything in execution.  If
there's something that needs to be fixed here I'd prefer it not to
add execution cost, in either space or instructions, to the normal
case, so if one must pay this cost I'd like to be clear about
what it is fixing.

So I'm getting the impression that the cost is supposed to buy "safety",
but I don't see how.  The fundamental problem is that, for certain
types of functions written in C, the goals of producing reusable code,
so one implementation can be shared by every application which needs
that service, and type safety, so that the compiler helps identify
misuses, seem to be mutually exclusive.  For a concrete example, I
have two queue implementations, one of which doesn't require an overhead
struct in the object being stored and one of which does.  The
former has an API approximately like

        void qfss_enqueue(qfss_t *q, void *ptr);
        void *qfss_dequeue(qfss_t *q);

where the values of ptr added to the queue `q' are returned to guys
dequeuing something from it.  The former requires overhead in the
application structure, maybe like

        struct foo {
                qmpsc_node_t q_node;
                ...
        };

and has an API sort of like

        void qmpsc_enqueue(qmpsc_t *q, qmpsc_node_t *node);
        qmpsc_node_t *qmpsc_dequeue(qmpsc_t *q);

What I would assert is that neither of these provides any type safety
at all.  Correct code in either case requires that all threads enqueuing
stuff on a particular instance of the queue only add the types of things
that the dequeuing threads operating on that instance of the queue expect
to get, and neither the compiler nor the library can do anything to help
with that.  The latter case does have to do some explicit type coercion
that the former doesn't (the void * does it implicitly) but this changes
the problem not at all; if the object queued is the type the dequeuer
expects the pointer type coercion (and the void *) will do the right thing,
otherwise it won't.

Given that in either case you are depending on writing the code correctly
without compiler help, I guess the only remaining question to ask is which
of these interfaces are you more likely to write mistaken code with?  I
don't know a quantitative way to measure that, but I do know that the only
one I have managed to screw up is the first.  The second at least tends
to limit the confusion to those structs having the right type of overhead
as a member while it is way too easy for anything, including a typo (my
mistake), to be accepted as the void * argument without complaint.  I guess
the issue might be that for the second the type coercion only needs to done
by the dequeuer, while with the first both the dequeuer and the enqueuer does
a type coercion (via the void *).  The type coercion in either case eliminates
any possibility of type safety, but the fact that the former does it twice
may provide you with more ways to screw it up in practice.

Given this, what I read you as advocating is that the API for the second
be changed to something more like the first, maybe like

        void qmpsc_enqueue(qmpsc_t *q, qmpsc_node_t *node, void *ptr);
        void *qmpsc_dequeue(qmpsc_t *q);

To me the extra void * argument helps nothing at all; the function is no more
type safe than it was, it still depends on the code being written correctly
without help from the compiler or library.  If anything at all, the extra
void * argument just seems to give you an extra way to screw up.  And the fact
that it has a cost in space and instructions executed while not addressing
the fundamental problem (which I suspect is an unavoidable consequence of
using the C language to write these functions) makes me wonder what is good
about this.

I hence get what container_of() seems to be good for.  It documents the
evil thing you need to do to reuse the functions (the use of void * doesn't
make the operation any less evil but does make the evil less obvious; I'm not
sure that is better), it leaves the normal case as efficient in execution as it
can be, but it doesn't assume the case is "normal" and adds the execution
cost you need to spend (but still not the extra space) when it isn't.  And
there are occasional reasons to not put the overhead struct at the top of
the application structure.  Sometimes you want to be able to store the
application structure in both a queue and a tree at the same time, if both
require a an overhead member they can't both be first, or occasionally you
might figure out that it is better to move the overhead struct down in the
application structure to sit beside (and maybe on the same cache line as)
the data the dequeuer is going to want to look at.  If a container_of() macro
can be implemented for every platform with a C compiler (which is a slightly
different question than the issue of whether it can be implemented portably) I
would prefer to have it available rather than paying for extra pointers which
don't fix the problem.  If I had any issue at all it is only that it is 
offsetof()
and not offset_of(), so maybe the name could lose the underscore unless someone
else has chosen the underscore name already.

Dennis Ferguson