Re: proposal: some pointer and arithmetic utilities

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

On 24 Mar, 2013, at 14:35 , Mouse <mouse%Rodents-Montreal.ORG@localhost> wrote:

>> [...], 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.
> 
> Not necessarily.  It will point to the same object, but I don't think
> there's any guarantee that two pointers to the same object are always
> bit-for-bit identical.  If nothing else, there may be padding bits.
> (At least, I'm fairly sure that's true of C.  Does POSIX contain such a
> promise?)

I'm no C language lawyer so I'll grant you an argument brownie point if this
is what you are after.  The part of the C draft pointed out earlier in the
thread guarantees that a pointer to a structure can be converted to a
pointer to its first member and vice versa, so knowing either one is as
good as knowing the other.  If you know a platform where two pointers of
the same type to the same object won't have identical bits then good for you.

> This "place it at the top of the sturct" paradigm strikes me as bad
> interface design.  If nothing else, it makes it impossible to have two
> such library structs in the same application struct.  It also makes it
> impossible for the library struct to be opaque to the application code;
> it can be undocumented, but it can't be opaque.  It also means that
> modifying the library struct introduces nontrivial ABI issues.

You misunderstand. The interface design is not a "place it at the
top of any particular structure" paradigm, it is an "application
allocates memory the library needs to use" paradigm.  The library
doesn't care where the memory is located, the application is free to
do what it wants.  If the application wants to separately allocate
the library's overhead it is free to do so; just define a struct
with the library's overhead and a (correctly typed!) pointer to the
application structure, and there you go: separate allocation along with
better type checking.  It is also always possible to have two library
structs in the same application struct; the application can write
its own version of container_of(), or use its own structure definitions
with pointers to the outer struct, or whatever its environment lets
it comfortably do.  If the application struct is important to keep
fixed for an ABI then the application will know that and will allocate
library overhead structs elsewhere.  And if the application doesn't trust
itself not to write to the innards of the overhead (which I personally
think is a much smaller problem than that of accidentally writing
the wrong type to a void *) it can always write its own module to
separately allocate and free the library struct while hiding its
contents from the rest of itself.  All the things you say can't be
done can in fact be done if the application chooses to do them;
the choice of how to use the library is left to the application.
Not having the extra pointer inside the library struct doesn't
prevent the application from having an extra pointer, it just
allows the application the option of not having it.

So the sole interface choice being made by the library is that
it requires the application to do its memory allocations so that
the library doesn't have to.  This isn't always a good (or even
possible) choice, but it sometimes is possible and it is useful to
have library functions which can execute reliably in situations
where memory allocations can't be done, or can't be done reliably
(e.g. in the kernel when you can't sleep), or where the application
has other reasons not to want a library to do them dynamically,
so letting the application choose when and how the required memory
is obtained makes the library more portable and and more widely
useful.  And, of course, it is very often convenient to provide
the application with a complete type so that it can statically
allocate the memory if it wants, or group small, related allocations
like this into a larger structure which can be allocated and freed
all at once, and whose allocation either succeeds or fails all at
once, rather than allocating and freeing each individual chunk by
itself.

> None of these problems arise when the library struct is entirely
> private to the library, with its caller treating it either as void * or
> as a pointer to an incomplete struct type - or, in cases where it can
> be done, not having anything to do with it at all.  (Well, the last one
> potentially arises, but it's a lot easier to deal with.)

None of those problems are really problems except the "entirely
private to the library" part, but if the whole point is to allow the
application to do its own memory allocation then the application must
know what to allocate and denying the application a complete type
prevents it from doing static allocations or grouping related allocations
together in a bigger structure that comes and goes all at once,
instead forcing the application to ask the library to allocate everything
separately. Since the application is not prevented from making
allocations like this separately if it wants to in any case, all this
does is deny the application the other choices.  I think this is a poor
way to write reusable code since, if the application's programmer
doesn't like the constraint, he now has incentive to avoid the library
in favor of writing his own stuff to do the same function without your
constraints being imposed on him.

If you think no library API should work this way, however, then you
don't have to start with fixing mine; POSIX C libraries are full of them
so you can work on those instead.  To pick a random example whose
man page happens to be in a window on my screen, the pthread library
seems to have at least a half a dozen private (or pretend-are-opaque)
types which it takes as arguments but expects the application to
provide space for; it provides _init() functions but no _create()
or _alloc() functions.  My use is not different.

>> 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,
> 
> "Already"?  Only if you insist on the embedded-struct interface design.

As pointed out, I insist on nothing.  The application is free to keep
an extra pointer, the library just doesn't force it to if the application
doesn't need it.  The kernel code example that was the topic is one
which didn't need it and was doing pretty well without it.

>> so you're adding cost to the normal case where there is no need to
>> spend anything in execution.
> 
> No need?  Perhaps...unless you want to be able to use two such library
> structs in the same application struct.  Or unless you want compiler
> help enforcing opacity of the library's private data.  Or unless you
> want a future-ready ABI.

As pointed out above, giving the application the option of not having
the pointer doesn't prevent the application from doing all those things
if the application wants to do them.

>> 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,
> 
> I'd prefer that too.
> 
> I'm not convinced it's possible.  (I'm even less convinced it's
> possible to do without making nonportable assumptions about the way the
> compiler implements certain things.)

I'd be interested in an example of compiler behaviour which would
prevent its implementation without violating some other guarantee
the C standard already provides.  It is my guess that the (surprisingly
generous) things that the standard guarantees about the behaviour of
types which might be members of unions, plus offsetof(), already constrain
compilers to behave in a way permitting a portable implementation.  I'm
no C language lawyer, however, so I won't try to make that argument

>> 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.
> 
> Yes.  C does not have real polymorphism, so it is not possible for
> polymorphic interfaces in C to be type-correct.  Hence, of course, both
> your example interfaces have type-safety risks.

This I agree with, but if there is no type-safety and correct behaviour
depends on the application code not causing an accident then the qualitative
question of which interface is least accident-prone is still quite relevant.
You've avoided addressing that.  I still believe that having some type,
which limits the kinds of confusion which the compiler can't detect, is
qualitatively better than using void * and providing unlimited
opportunities for confusion.

> I don't know what was in the minds of the people who wrote the emails
> you got your impression from.  But I do see reasons - sketched above -
> to prefer the first kind of interface.
> 
>> I hence get what container_of() seems to be good for.
> 
> I like it about as much as I like offsetof - which is to say, I think
> it is a mistake.  I have trouble imagining a use for it that is neither
> premature optimization nor so heavily in need of "every last cycle"
> optimization that it arguably shouldn't be in C at all.

So I guess you like it as much as I like using void * to avoid an
explicit cast documenting the nasty thing one is relying on while
making it not one bit less nasty.  People have opinions.

But preventing "premature optimization" by designing the library interface
to prohibit the application from ever making the optimization is a bit
like jailing people for the things they might do even if they haven't
done them.  Some optimizations are premature and some aren't, some
optimizations are useful and some aren't, but distinguishing those
outside the context of a particular application can often only be
done on the basis of purely subjective opinion.

You clearly have an opinion, and I might even have an opinion, but all
my experience writing code for other people to use tells me that if
you try to enforce your subjective opinions at a library interface then
often the only result of that is that people with other opinions (perhaps
better supported by contextual facts than yours are) won't use it.  I
hence prefer to leave as many of those decisions as possible to the user
of the library.

Dennis Ferguson