Reference counting

Discussion in 'C Programming' started by daknok, Jun 5, 2011.

  1. daknok

    daknok Guest

    Hi,

    If I want to do simple reference counting for different structures I
    would go like this:

    struct String {
    unsigned references;
    char *cString;
    size_t length;
    };

    void StringRelease(struct String *str) {
    str->references--;
    if (str->references == 0) {
    free(str->cString);
    free(str);
    }
    }

    struct String *StringRetain(struct String *str) {
    str->references++;
    return str;
    }

    Though if I have about ten structs, I have ten different functions to
    increase and decrease the reference count. Is it, in some way, possible
    to just provide one function for increasing and one function for
    decreasing the reference count which can be used for all structs with a
    reference count?
     
    daknok, Jun 5, 2011
    #1
    1. Advertising

  2. daknok

    Angel Guest

    On 2011-06-05, daknok <> wrote:
    > Hi,
    >
    > If I want to do simple reference counting for different structures I
    > would go like this:
    >
    > struct String {
    > unsigned references;
    > char *cString;
    > size_t length;
    > };
    >
    > void StringRelease(struct String *str) {
    > str->references--;
    > if (str->references == 0) {
    > free(str->cString);
    > free(str);
    > }
    > }
    >
    > struct String *StringRetain(struct String *str) {
    > str->references++;
    > return str;
    > }
    >
    > Though if I have about ten structs, I have ten different functions to
    > increase and decrease the reference count. Is it, in some way, possible
    > to just provide one function for increasing and one function for
    > decreasing the reference count which can be used for all structs with a
    > reference count?


    There are number of ways to do this. One of the easiest (but least
    flexible) is to start all your structures with the same reference
    variable, of the same type, like this:

    struct a
    {
    int ref_count;
    char *data;
    char *more_data;
    };

    struct b
    {
    int ref_count;
    int number;
    int another_number;
    };

    Now you can safely read the ref_count from any of these structures, for
    example like this:

    struct ref_count
    {
    int ref_count;
    };

    void increase_refcount(void *data)
    {
    ((struct refcount *) data)->refcount++;
    }

    You can safely pass either pointers to struct a or struct b to this
    function, and it will work as expected. The standard guarantees that
    shared fields at the beginning of structures are compatible. In a way,
    this is a primitive C implementation of inheritance.

    The other way I used this same principle to create a generic linked
    list. Similar tricks are also used in the Linux kernel, and in the
    network parts of glibc.


    --
    "C provides a programmer with more than enough rope to hang himself.
    C++ provides a firing squad, blindfold and last cigarette."
    - seen in comp.lang.c
     
    Angel, Jun 5, 2011
    #2
    1. Advertising

  3. daknok

    BartC Guest

    "daknok" <> wrote in message
    news:4deb6008$0$28457$...
    > Hi,
    >
    > If I want to do simple reference counting for different structures I would
    > go like this:
    >
    > struct String {
    > unsigned references;
    > char *cString;
    > size_t length;
    > };
    >
    > void StringRelease(struct String *str) {
    > str->references--;
    > if (str->references == 0) {
    > free(str->cString);
    > free(str);
    > }
    > }
    >
    > struct String *StringRetain(struct String *str) {
    > str->references++;
    > return str;
    > }
    >
    > Though if I have about ten structs, I have ten different functions to
    > increase and decrease the reference count. Is it, in some way, possible to
    > just provide one function for increasing and one function for decreasing
    > the reference count which can be used for all structs with a reference
    > count?


    How different are these structs? It looks like each struct needs other
    things doing to it apart from the reference count.

    I might go for a single, more elaborate struct that does everything, with
    perhaps a tag in it saying what kind of struct it is. Then you need one set
    of functions, although they will be more complex (and might still delegate
    the work to multiple functions).

    > str->references--;
    > if (str->references == 0) {
    > free(str->cString);
    > free(str);


    Could this be called when ->references is already zero? I might check for
    this.

    --
    Bartc
     
    BartC, Jun 5, 2011
    #3
  4. daknok

    daknok Guest

    On 2011-06-05 14:14:25 +0200, BartC said:

    > "daknok" <> wrote in message
    > news:4deb6008$0$28457$...
    >> Hi,
    >>
    >> If I want to do simple reference counting for different structures I
    >> would go like this:
    >>
    >> struct String {
    >> unsigned references;
    >> char *cString;
    >> size_t length;
    >> };
    >>
    >> void StringRelease(struct String *str) {
    >> str->references--;
    >> if (str->references == 0) {
    >> free(str->cString);
    >> free(str);
    >> }
    >> }
    >>
    >> struct String *StringRetain(struct String *str) {
    >> str->references++;
    >> return str;
    >> }
    >>
    >> Though if I have about ten structs, I have ten different functions to
    >> increase and decrease the reference count. Is it, in some way, possible
    >> to just provide one function for increasing and one function for
    >> decreasing the reference count which can be used for all structs with a
    >> reference count?

    >
    > How different are these structs? It looks like each struct needs other
    > things doing to it apart from the reference count.


    Well I have structs for strings, dates, files, data and URLs basically.
    They all use reference counting.

    >
    > I might go for a single, more elaborate struct that does everything,
    > with perhaps a tag in it saying what kind of struct it is. Then you
    > need one set of functions, although they will be more complex (and
    > might still delegate the work to multiple functions).
    >
    >> str->references--;
    >> if (str->references == 0) {
    >> free(str->cString);
    >> free(str);

    >
    > Could this be called when ->references is already zero? I might check for this.


    This should indeed always be called when the number of references
    reaches zero, because in that case it isn't anymore in use.
     
    daknok, Jun 5, 2011
    #4
  5. daknok

    daknok Guest

    Of course this will only be for strings. I need a deallocator for each
    struct, though I could do this with a type field:

    typedef enum {
    ReferenceCountTypeString,
    ReferenceCountTypeDate,
    ReferenceCountTypeData,
    ReferenceCountTypeURL,
    } ReferenceCountType;

    struct ReferenceCount {
    unsigned references;
    ReferenceCountType type;
    };

    struct String {
    struct ReferenceCount refCount;
    char *cString;
    size_t length;
    };
     
    daknok, Jun 5, 2011
    #5
  6. daknok

    BartC Guest

    "daknok" <> wrote in message
    news:4deb74f0$0$28443$...
    > On 2011-06-05 14:14:25 +0200, BartC said:


    >>> str->references--;
    >>> if (str->references == 0) {
    >>> free(str->cString);
    >>> free(str);

    >>
    >> Could this be called when ->references is already zero? I might check for
    >> this.

    >
    > This should indeed always be called when the number of references reaches
    > zero, because in that case it isn't anymore in use.


    I meant the str->references-- bit.

    If StringRelease() is called on something that already has a reference count
    of 0, then it might go wrong.

    And because such a function is likely to be called from many places where
    the caller does not know/care how many active references remain, then that
    might be an issue.

    --
    bartc
     
    BartC, Jun 5, 2011
    #6
  7. daknok

    daknok Guest

    On 2011-06-05 15:45:41 +0200, BartC said:

    > "daknok" <> wrote in message
    > news:4deb74f0$0$28443$...
    >> On 2011-06-05 14:14:25 +0200, BartC said:

    >
    >>>> str->references--;
    >>>> if (str->references == 0) {
    >>>> free(str->cString);
    >>>> free(str);
    >>>
    >>> Could this be called when ->references is already zero? I might check for
    >>> this.

    >>
    >> This should indeed always be called when the number of references reaches
    >> zero, because in that case it isn't anymore in use.

    >
    > I meant the str->references-- bit.
    >
    > If StringRelease() is called on something that already has a reference count
    > of 0, then it might go wrong.
    >
    > And because such a function is likely to be called from many places where
    > the caller does not know/care how many active references remain, then that
    > might be an issue.


    If the code is written well, this won't be a problem. Even better could
    I write a macro:

    SafeStringRelease(s) if (s != NULL) { StringRelease(s); } s = NULL

    and use that.
     
    daknok, Jun 5, 2011
    #7
  8. daknok

    Shao Miller Guest

    On 6/5/2011 5:52 AM, daknok wrote:
    > Hi,
    >
    > If I want to do simple reference counting for different structures I
    > would go like this:
    >
    > struct String {
    > unsigned references;
    > char *cString;
    > size_t length;
    > };
    >
    > void StringRelease(struct String *str) {
    > str->references--;
    > if (str->references == 0) {
    > free(str->cString);
    > free(str);
    > }
    > }
    >
    > struct String *StringRetain(struct String *str) {
    > str->references++;
    > return str;
    > }
    >
    > Though if I have about ten structs, I have ten different functions to
    > increase and decrease the reference count.


    Your 'struct String' contains a 'cString' pointer, which implies that
    someone has to set that member somehow. If you offer an allocator which
    allocates both a 'struct String' as well as the data that 'cString' will
    point to, a reference-counting de-allocator that has knowledge of the
    resource pointed-to by 'cString' seems nicely symmetrical.

    Does one 'struct String' "own" the string that its 'cString' member
    points to? Or are users allowed to modify the 'cString' member
    themselves and point to, let's say, a string literal? You wouldn't want
    them to free a string literal, most likely. :)

    If the string is "owned" by the associated 'struct String', then of
    course, a nice thing about having an array of some element type is that
    you can allocate 'struct String' and the 'char[]' together.

    typedef struct String_ String;
    struct string_ {
    unsigned int references;
    size_t current_length;
    size_t maximum_length;
    char * cString;
    char data_[1];
    };

    Now you can have an allocator that does something like:

    String * new_string(size_t maximum_length) {
    String * result;
    result = malloc(sizeof *result + maximum_length);
    if (!result)
    return result; /* pass the null pointer value on */
    init_string(result, maximum_length, result->data_);
    return result;
    }

    where 'init_string' is something like:

    void init_string(String * string, size_t maximum_length, char * cString);

    and sets the relevant members (and 'references' to 1, other stuff,
    perhaps). Now when your reference-counting de-allocator is ready to
    free the 'struct String', its call to 'free' will include deallocating
    the trailing 'char[]' that was allocated by the above call to 'malloc'.
    This way, the de-allocator doesn't need to free 2 ranges of memory.

    > Is it, in some way, possible
    > to just provide one function for increasing and one function for
    > decreasing the reference count which can be used for all structs with a
    > reference count?
    >


    I think that depends. If your structs contain references to other
    objects (which might contain references to other objects, etc.), it
    seems that the knowledge for "collapsing" has to go somewhere. If the
    struct "owns" all of the resources associated with it, you could:
    - Explicitly 'free' each resource when the struct is being de-allocated.
    (Knowledge in the struct-specific function.)
    - Track all resources with a linked list and walk the list, freeing
    items, when the struct is being de-allocated. (Knowledge in the
    resource list.)

    If a struct doesn't "own" all of the resources associated with it, then
    perhaps you extend your reference-counting approach to such resources,
    also. But still, the knowledge for what might be referenced by your
    struct needs to go somewhere. Perhaps you have a struct-specific,
    reference-counting de-allocator which decrements the references for all
    of the resources it is referencing. This is a nicely-collapsible chain
    of events.

    As already suggested by others, if your structures all begin with the
    same type of member, you can have a single reference-counting release
    function that takes a pointer to it. While this means not having to use
    'StringRelease', 'FileRelease', 'UrlRelease', etc. all over the place,
    the knowledge of any "sub-resources" still needs to be somewhere;
    possibly in a struct-specific function which can be found via a function
    pointer.
     
    Shao Miller, Jun 5, 2011
    #8
  9. daknok

    Eric Sosman Guest

    On 6/5/2011 11:01 AM, daknok wrote:
    > [...]
    > If the code is written well, this won't be a problem. Even better could
    > I write a macro:
    >
    > SafeStringRelease(s) if (s != NULL) { StringRelease(s); } s = NULL
    >
    > and use that.


    Danger, Will Robinson!

    if (x == 42)
    SafeStringRelease(string);

    Note carefully what happens when `x' is *not* forty-two. (What
    you need is known as "the `do { } while(0)' trick.")

    Then, too, there's the matter of side-effects:

    String *array[42];
    ...
    int i = ...;
    // Release all Strings from the i'th onward:
    while (i < 42)
    SafeStringRelease(array[i++]);

    With SafeStringRelease as it stands you'll free only about half
    of the strings; a corrected version would free only about a third
    and leak another third. Both versions would be likely to do
    something weird on or just after the final trip through the loop.

    I'm not a big believer in the efficacy of the `s = NULL' part,
    for the same reason I don't use a similar construct with free():
    You can NULL out one particular pointer to a released thing, but
    there's not much hope of finding and NULLing all of them. For
    example, what if `s' expands to the name of a function parameter?
    You can NULL out the parameter -- the function's local variable --
    but you can't get at the argument the caller provided.

    --
    Eric Sosman
    d
     
    Eric Sosman, Jun 5, 2011
    #9
  10. daknok

    Gene Guest

    On Jun 5, 7:17 am, Angel <> wrote:
    > On 2011-06-05, daknok <> wrote:
    >
    >
    >
    >
    >
    > > Hi,

    >
    > > If I want to do simple reference counting for different structures I
    > > would go like this:

    >
    > > struct String {
    > >     unsigned references;
    > >     char *cString;
    > >     size_t length;
    > > };

    >
    > > void StringRelease(struct String *str) {
    > >     str->references--;
    > >     if (str->references == 0) {
    > >         free(str->cString);
    > >         free(str);
    > >     }
    > > }

    >
    > > struct String *StringRetain(struct String *str) {
    > >     str->references++;
    > >     return str;
    > > }

    >
    > > Though if I have about ten structs, I have ten different functions to
    > > increase and decrease the reference count. Is it, in some way, possible
    > > to just provide one function for increasing and one function for
    > > decreasing the reference count which can be used for all structs with a
    > > reference count?

    >
    > There are number of ways to do this. One of the easiest (but least
    > flexible) is to start all your structures with the same reference
    > variable, of the same type, like this:
    >
    > struct a
    > {
    >         int ref_count;
    >         char *data;
    >         char *more_data;
    >
    > };
    >
    > struct b
    > {
    >         int ref_count;
    >         int number;
    >         int another_number;
    >
    > };
    >
    > Now you can safely read the ref_count from any of these structures, for
    > example like this:
    >
    > struct ref_count
    > {
    >         int ref_count;
    >
    > };
    >
    > void increase_refcount(void *data)
    > {
    >         ((struct refcount *) data)->refcount++;
    >
    > }
    >
    > You can safely pass either pointers to struct a or struct b to this
    > function, and it will work as expected. The standard guarantees that
    > shared fields at the beginning of structures are compatible. In a way,
    > this is a primitive C implementation of inheritance.


    I asked about this here some time back. The folks who know the
    Standard well denied that this is portable. The standard gives you
    now way to rely on common prefixes of fields to be laid out the same
    way in memory. But you _can_ rely on casts between the first field
    and an enclosing struct type to work correctly. So the fully portable
    way is this:

    typedef enum { StringTag, URLTag, ... } TAG;
    typedef unsigned REF_COUNT;

    typedef struct {
    TAG tag;
    REF_COUNT ref_count;
    } HEADER, *REF_COUNTED_OBJECT_PTR;

    // every kind object needs the same initial header field.
    typedef struct string_s {
    HEADER hdr[1];
    char *text;
    unsigned length;
    } STRING;

    REF_COUNTED_OBJECT_PTR make_string(void)
    {
    STRING *s = safe_malloc(sizeof(STRING));
    s->hdr->tag = StringTag;
    s->hdr->ref_count = 0;
    s->text = NULL;
    s->length = 0;
    return (REF_COUNTED_OJBECT_PTR)s;
    }

    REF_COUNTED_OBJECT_PTR ref (REF_COUNTED_OBJECT_PTR p)
    {
    p->ref_count++;
    return p;
    }

    void deref (REF_COUNTED_OBJECT_PTR p)
    {
    if (--p->ref_count == 0)
    switch (p->tag) {
    case StringTag:
    safe_free((STRING*)p);
    break;
    case ...
    }
    return p;
    }

    .... now for example
    {
    REF_COUNTED_OJBECT_PTR x, s = ref(make_string());
    ... use s
    x = ref(s);
    ... use x
    deref(s);
    ... yada yada
    deref(x); // causes deallocation.
    }
     
    Gene, Jun 7, 2011
    #10
  11. daknok

    ImpalerCore Guest

    On Jun 5, 6:52 am, daknok <> wrote:
    > Hi,
    >
    > If I want to do simple reference counting for different structures I
    > would go like this:
    >
    > struct String {
    >     unsigned references;
    >     char *cString;
    >     size_t length;
    >
    > };
    >
    > void StringRelease(struct String *str) {
    >     str->references--;
    >     if (str->references == 0) {
    >         free(str->cString);
    >         free(str);
    >     }
    >
    > }
    >
    > struct String *StringRetain(struct String *str) {
    >     str->references++;
    >     return str;
    >
    > }
    >
    > Though if I have about ten structs, I have ten different functions to
    > increase and decrease the reference count. Is it, in some way, possible
    > to just provide one function for increasing and one function for
    > decreasing the reference count which can be used for all structs with a
    > reference count?


    One option is to abstract the reference count out of the structure and
    piggyback it onto a raw allocated pointer. The same trick used to
    make debugging allocators could apply to a reference counted pointer.
    I've never done it before, but it's something to ponder. Here's my
    first pass.

    \code snippet
    #define PTR_HEADER_SIZE (sizeof (int))

    void* rc_malloc( size_t size )
    {
    void* mem = NULL;
    void* p = NULL;

    p = malloc( size + PTR_HEADER_SIZE );

    if ( p )
    {
    /* Set the reference count to 1. */
    *((int*)p) = 1;

    mem = (unsigned char*)p + PTR_HEADER_SIZE;
    }

    return mem;
    }

    void* rc_copy( void* p )
    {
    void* actual_p = NULL;

    if ( p )
    {
    actual_p = (unsigned char*)p - PTR_HEADER_SIZE;

    /* Increment the reference count. */
    *((int*)actual_p) += 1;
    }

    return p;
    }

    void rc_release( void* p )
    {
    void* actual_p = NULL;

    if ( p )
    {
    actual_p = (unsigned char*)p - PTR_HEADER_SIZE;

    /* Decrement the reference count. */
    *((int*)actual_p) -= 1;

    /* If reference count down to zero, release the memory. */
    if ( *((int*)actual_p) == 0 ) {
    free( actual_p );
    }
    }
    }
    \endcode

    You prefix every allocation's pointer with an integer reference
    count. On access, it dereferences just like a regular pointer to the
    object. With a slight change in function interface, you should be
    able to use the refcount interface to interact with a reference
    counted pointer. Just don't mix refcount pointers with malloc and
    friends.

    Not tested, don't know how kosher or brittle the technique is, and I
    have no practical experience with reference counting so YMMV.

    Best regards,
    John D.
     
    ImpalerCore, Jun 10, 2011
    #11
  12. daknok

    Shao Miller Guest

    On 6/10/2011 14:30, ImpalerCore wrote:
    > One option is to abstract the reference count out of the structure and
    > piggyback it onto a raw allocated pointer. The same trick used to
    > make debugging allocators could apply to a reference counted pointer.
    > I've never done it before, but it's something to ponder. Here's my
    > first pass.
    >
    > \code snippet
    > #define PTR_HEADER_SIZE (sizeof (int))
    >
    > void* rc_malloc( size_t size )
    > {
    > void* mem = NULL;
    > void* p = NULL;
    >
    > p = malloc( size + PTR_HEADER_SIZE );
    >
    > if ( p )
    > {
    > /* Set the reference count to 1. */
    > *((int*)p) = 1;
    >
    > mem = (unsigned char*)p + PTR_HEADER_SIZE;
    > }
    >
    > return mem;
    > }


    'mem' isn't necessarily suitably aligned for any object; a promise that
    the Standard makes of 'malloc'. Since the 'sizeof (int)' must be an
    integer multiple of the alignment requirement of 'int', you can put the
    'int' at the _end_ of the allocated memory and compute where it needs to
    go so that it doesn't overlap the memory before it and is suitably aligned.

    Maybe something like (disclaimer: quickly coded):

    #include <stddef.h>
    #include <stdlib.h>
    #include <stdio.h>

    typedef int footer_t;

    size_t footer_at(size_t size) {
    size_t x = size;
    x += sizeof (footer_t);
    /* Check for wrap-around */
    if (x < size)
    return 0;
    return (x - 1) / sizeof (footer_t);
    }

    size_t size_with_footer(size_t size) {
    size_t x = footer_at(size);
    if (!x)
    return 0;
    x = (x + 1) * sizeof (footer_t);
    /* Check for wrap-around */
    if (x < size)
    return 0;
    return x;
    }

    footer_t * get_footer(void * mem, size_t size) {
    size_t footer_pos = footer_at(size);
    if (!mem || !footer_pos)
    return NULL;
    return (footer_t *) mem + footer_pos;
    }

    void * malloc_with_footer(size_t size) {
    void * mem;
    footer_t * footer;
    mem = malloc(size_with_footer(size));
    if (!mem)
    return mem;
    footer = get_footer(mem, size);
    if (!footer)
    return footer;
    /* Initialize footer */
    /* ... */
    return mem;
    }

    int main(void) {
    size_t sizes[] = {0, 2, 6, 8, 12, 15};
    enum cv {tests = sizeof sizes / sizeof *sizes};
    int i;

    for (i = 0; i < tests; ++i) {
    printf("size: [%d] ", (int)sizes);
    printf(
    "footer_at: [%d] ",
    (int)footer_at(sizes) * sizeof (footer_t)
    );
    printf(
    "size_with_footer: [%d] ",
    (int)size_with_footer(sizes)
    );
    puts("");
    }
    return 0;
    }

    But then whenever you want to work with the footer, you'd have to use
    'get_footer', instead of a simple cast.
     
    Shao Miller, Jun 10, 2011
    #12
  13. daknok

    James Kuyper Guest

    On 06/10/2011 02:30 PM, ImpalerCore wrote:
    ....
    > One option is to abstract the reference count out of the structure and
    > piggyback it onto a raw allocated pointer. The same trick used to
    > make debugging allocators could apply to a reference counted pointer.
    > I've never done it before, but it's something to ponder. Here's my
    > first pass.
    >
    > \code snippet
    > #define PTR_HEADER_SIZE (sizeof (int))
    >
    > void* rc_malloc( size_t size )
    > {
    > void* mem = NULL;
    > void* p = NULL;
    >
    > p = malloc( size + PTR_HEADER_SIZE );
    >
    > if ( p )
    > {
    > /* Set the reference count to 1. */
    > *((int*)p) = 1;
    >
    > mem = (unsigned char*)p + PTR_HEADER_SIZE;
    > }
    >
    > return mem;
    > }


    The value stored in 'p' is guaranteed to be correctly aligned for all
    types. However, the only thing portably guaranteed about alignment off
    the value stored in 'mem' is that it is suitable for 'int', it need not
    be suitably aligned for any type with a size greater than 1 that is
    different from that of 'int'.

    The draft of the next version of the C standard includes new
    alignment-related features that will help with this kind of thing. The
    C1X version of your code should probably use alignof(max_align_t), where
    max_align_t is declared in <stddef.h>.
    --
    James Kuyper
     
    James Kuyper, Jun 11, 2011
    #13
  14. daknok

    Shao Miller Guest

    Multiple Inheritance (Was Re: Reference counting)

    On 6/6/2011 10:07 PM, Gene wrote:
    > On Jun 5, 7:17 am, Angel<> wrote:
    >> On 2011-06-05, daknok<> wrote:
    >>
    >>> ...
    >>> If I want to do simple reference counting for different structures I
    >>> would go like this:
    >>> ...
    >>> Though if I have about ten structs, I have ten different functions to
    >>> increase and decrease the reference count. Is it, in some way, possible
    >>> to just provide one function for increasing and one function for
    >>> decreasing the reference count which can be used for all structs with a
    >>> reference count?

    >>
    >> There are number of ways to do this. One of the easiest (but least
    >> flexible) is to start all your structures with the same reference
    >> variable, of the same type, like this:
    >>
    >> struct a
    >> {
    >> int ref_count;
    >> char *data;
    >> char *more_data;
    >>
    >> };
    >>
    >> struct b
    >> {
    >> int ref_count;
    >> int number;
    >> int another_number;
    >>
    >> };
    >>
    >> Now you can safely read the ref_count from any of these structures, for
    >> example like this:
    >>
    >> struct ref_count
    >> {
    >> int ref_count;
    >>
    >> };
    >>
    >> void increase_refcount(void *data)
    >> {
    >> ((struct refcount *) data)->refcount++;
    >>
    >> }
    >>
    >> You can safely pass either pointers to struct a or struct b to this
    >> function, and it will work as expected. The standard guarantees that
    >> shared fields at the beginning of structures are compatible. In a way,
    >> this is a primitive C implementation of inheritance.

    >
    > I asked about this here some time back. The folks who know the
    > Standard well denied that this is portable. The standard gives you
    > now way to rely on common prefixes of fields to be laid out the same
    > way in memory. But you _can_ rely on casts between the first field
    > and an enclosing struct type to work correctly. So the fully portable
    > way is this:
    >


    Does anyone recall which thread this was asked about in? I'm curious as
    to whether or not "the folks who know the Standard well" had offered
    concerns beyond alignment.

    If 'struct refcount' (above) has an alignment requirement that is not
    met by where 'data' in 'increase_refcount' (above) points to, then the
    behaviour appears to be undefined[6.3.2.3p7]. But as alluded to above,
    my impressions is that the alignment requirement of a struct or union
    must satisfy the alignment requirement(s) of its member(s), so a pointer
    to the first member (or element) can be cast to a pointer to the
    surrounding struct or union (or array).

    > typedef enum { StringTag, URLTag, ... } TAG;
    > typedef unsigned REF_COUNT;
    >
    > typedef struct {
    > TAG tag;
    > REF_COUNT ref_count;
    > } HEADER, *REF_COUNTED_OBJECT_PTR;
    >
    > // every kind object needs the same initial header field.
    > typedef struct string_s {
    > HEADER hdr[1];
    > char *text;
    > unsigned length;
    > } STRING;
    >
    > REF_COUNTED_OBJECT_PTR make_string(void)
    > {
    > STRING *s = safe_malloc(sizeof(STRING));
    > s->hdr->tag = StringTag;
    > s->hdr->ref_count = 0;
    > s->text = NULL;
    > s->length = 0;
    > return (REF_COUNTED_OJBECT_PTR)s;
    > }
    >


    Which you suggested might've been better as:

    return s->hdr;

    (I hope you don't mind my including that from our brief, private
    discussion.)

    > REF_COUNTED_OBJECT_PTR ref (REF_COUNTED_OBJECT_PTR p)
    > {
    > p->ref_count++;
    > return p;
    > }
    >
    > void deref (REF_COUNTED_OBJECT_PTR p)
    > {
    > if (--p->ref_count == 0)
    > switch (p->tag) {
    > case StringTag:
    > safe_free((STRING*)p);
    > break;
    > case ...
    > }
    > return p;
    > }
    >
    > ... now for example
    > {
    > REF_COUNTED_OJBECT_PTR x, s = ref(make_string());
    > ... use s
    > x = ref(s);
    > ... use x
    > deref(s);
    > ... yada yada
    > deref(x); // causes deallocation.
    > }


    The only "problem" I have with the "first member" strategy
    ('container_of', 'CONTAINING_RECORD', etc.) is in regards to
    extensibility...

    So all of the structs that you define 'HEADER' as the first member for
    are all effectively reference-countable using the above strategy.
    That's fine.

    Then perhaps a day comes when you might like to actually track some
    reference-countable objects in linked lists, but maybe not others. So
    maybe you do:

    struct ref_countable_and_linked_list_trackable {
    HEADER hdr[1];
    LIST_ENTRY link[1];
    };

    And then you revisit the code and change, let's say, 'struct string_s' to:

    typedef struct string_s {
    struct ref_countable_and_linked_list_trackable hdr[1];
    char *text;
    unsigned length;
    } STRING;

    There might be several struct definitions to change, too.

    Then perhaps a day comes when you might like to actually allow for some
    object types to include an "extension" pointer because you'd like to use
    an interface where these objects might optionally be associated with
    additional data. Do you put the extension pointer inside the definition
    of 'HEADER'? Could it go unused and waste space? Do you put it inside
    'struct ref_countable_and_linked_list_trackable'? Could it go unused
    and waste space? Does it apply to all reference-countable object types?
    Does it apply to all linked-list-trackable object types? Does it
    apply to object types which are not reference-countable? It's
    essentially a "multiple-inheritance" challenge, if I understand it
    correctly.

    One strategy might be to have object type "operations:"

    typedef void f_deref(void *);
    typedef void f_unlink(void *);
    typedef void f_free_extension(void *);

    struct object_operations {
    f_deref * deref;
    f_unlink * unlink;
    f_free_extension * free_extension;
    };

    then for a particular object type, you could have (at file scope):

    struct object_operations string_operations = {
    string_deref,
    0,
    0,
    };
    struct object_operations node_operations = {
    node_deref,
    node_unlink,
    0,
    };

    etc. Then your "header" might simply be like 'ops' below:

    struct foo {
    struct object_operations * ops;
    /* Other members */
    };

    and every object would need to have this header initialized to point to
    the operations appropriate for its type. This strategy can also
    eliminate the 'tag' requirement, since an object's supported operations
    define the use of the object.

    void deref(void * object) {
    /* ...Maybe check for null pointer... */
    /* ...Maybe yield debug messages... */
    /* ...Maybe adjust debugging counters... */
    ((struct object_operations *) object)->deref(object);
    return;
    }

    However, this strategy trades the size of objects for the speed required
    to initialize the 'ops' member and to call the functions instead of
    making the simpler casts and offset computations for the inherited
    properties (like 'ref_count').

    Also, there is still wasted space for any object types with unsupported
    operations, in such a type's 'xxx_operations' instance. So if one had
    hundreds of operations, one might further wish to squeeze space and
    forfeit time by using a single "operations function" that returns the
    supported operations:

    enum object_operation_type {
    obj_op_deref,
    obj_op_unlink,
    obj_op_free_extension,
    obj_ops
    };

    union object_operations {
    f_deref * deref;
    f_unlink * unlink;
    f_free_extension * free_extension;
    };

    typedef union object_operations f_object_operations(
    enum object_operation_type
    );

    Then your header might simply be like 'ops' below:

    struct foo {
    f_object_operations * ops;
    /* Other members */
    };

    And each object type would have a handler:

    f_object_operations string_operations;
    union object_operations string_operations(
    enum object_operation_type type
    ) {
    union object_operations result;
    switch (type) {
    case obj_op_deref:
    result.deref = string_deref;
    return result;
    }
    /* Problem */
    }

    And the general interface would call the specific one:

    void deref(void * object) {
    f_object_operations ** ops;
    /* ...Maybe check for null pointer... */
    /* ...Maybe yield debug messages... */
    /* ...Maybe adjust debugging counters... */
    ops = object;
    (*ops)(obj_op_deref).deref(object);
    return;
    }

    Then perhaps a day comes when you'd like to be able to support
    additional operations at execution-time. One could "hook" an object's
    "handler" with a new handler that optionally invokes the old handler, if
    needed. That's pretty easy; just set the 'ops' member.

    Then perhaps a day comes when your additional operations need some kind
    of context whose storage is not accomodated by the object being hooked.
    One could have a "stack" of handlers and context, but then it seems to
    me that the minimal size for a meaningful "header" would be:

    struct header {
    f_object_operations * ops;
    void * context;
    };

    where both of these header members could be hooked for any object, and
    where the 'context' member could point to context which itself includes
    the same header for the previous[ly hooked] context, etc.

    What approach(es) to a "multiple inheritance" challenge do you other
    folks in comp.lang.c enjoy? :)
     
    Shao Miller, Jun 11, 2011
    #14
  15. daknok

    Shao Miller Guest

    On 6/11/2011 2:36 PM, ImpalerCore wrote:
    >
    > If I understand correctly, malloc should always return an aligned
    > pointer, so by knowing ALIGN_MAX, the pointer at offset ALIGN_MAX
    > should also be suitably aligned for any other object. I think this
    > might work, but I hesitate as the nuances of alignment issues continue
    > to elude my understanding.


    Or you can put your accounting object at/near the end of the allocated
    memory, as mentioned else-thread. Would anyone else mind mentioning
    this or does nobody really do that? I thought it was fairly common
    practice for some I/O buffers. Filtering... *sigh*
     
    Shao Miller, Jun 11, 2011
    #15
  16. "ImpalerCore" <> wrote in message
    news:...

    [...]

    > Unfortunately I do not know how
    > to manually find a platform's ALIGN_MAX. I've seen some incantations
    > with unions and offsetof, and autoconf has their AC_CHECK_ALIGNOF, but
    > I don't know how to use it.


    read all of these:


    http://groups.google.com/group/comp.lang.c.moderated/msg/eab267b936d91c7e

    http://groups.google.com/group/comp.lang.c.moderated/msg/0bf610f1573455c1

    http://groups.google.com/group/comp.lang.c.moderated/msg/9f34b8ed765cb32b


    the `ALIGN_OF()' function macro should always give you a "sufficient"
    alignment for a given type.
     
    Chris M. Thomasson, Jun 12, 2011
    #16
  17. "Chris M. Thomasson" <> wrote in message
    news:8cTIp.4134$...
    > "ImpalerCore" <> wrote in message
    > news:...
    >
    > [...]
    >
    >> Unfortunately I do not know how
    >> to manually find a platform's ALIGN_MAX. I've seen some incantations
    >> with unions and offsetof, and autoconf has their AC_CHECK_ALIGNOF, but
    >> I don't know how to use it.

    >
    > read all of these:

    [...]

    >
    > the `ALIGN_OF()' function macro should always give you a "sufficient"
    > alignment for a given type.


    What about some crazy hacked shi% like this crap:

    http://codepad.org/A65Noc37

    lol...
     
    Chris M. Thomasson, Jun 12, 2011
    #17
  18. daknok

    Dr Nick Guest

    Re: Multiple Inheritance (Was Re: Reference counting)

    Shao Miller <> writes:

    > On 6/6/2011 10:07 PM, Gene wrote:
    >> On Jun 5, 7:17 am, Angel<> wrote:
    >>> On 2011-06-05, daknok<> wrote:
    >>>
    >>>> ...
    >>>> If I want to do simple reference counting for different structures I
    >>>> would go like this:
    >>>> ...
    >>>> Though if I have about ten structs, I have ten different functions to
    >>>> increase and decrease the reference count. Is it, in some way, possible
    >>>> to just provide one function for increasing and one function for
    >>>> decreasing the reference count which can be used for all structs with a
    >>>> reference count?
    >>>
    >>> There are number of ways to do this. One of the easiest (but least
    >>> flexible) is to start all your structures with the same reference
    >>> variable, of the same type, like this:
    >>>
    >>> struct a
    >>> {
    >>> int ref_count;
    >>> char *data;
    >>> char *more_data;
    >>>
    >>> };
    >>>
    >>> struct b
    >>> {
    >>> int ref_count;
    >>> int number;
    >>> int another_number;
    >>>
    >>> };
    >>>
    >>> Now you can safely read the ref_count from any of these structures, for
    >>> example like this:
    >>>
    >>> struct ref_count
    >>> {
    >>> int ref_count;
    >>>
    >>> };
    >>>
    >>> void increase_refcount(void *data)
    >>> {
    >>> ((struct refcount *) data)->refcount++;
    >>>
    >>> }
    >>>
    >>> You can safely pass either pointers to struct a or struct b to this
    >>> function, and it will work as expected. The standard guarantees that
    >>> shared fields at the beginning of structures are compatible. In a way,
    >>> this is a primitive C implementation of inheritance.

    >>
    >> I asked about this here some time back. The folks who know the
    >> Standard well denied that this is portable. The standard gives you
    >> now way to rely on common prefixes of fields to be laid out the same
    >> way in memory. But you _can_ rely on casts between the first field
    >> and an enclosing struct type to work correctly. So the fully portable
    >> way is this:
    >>

    >
    > Does anyone recall which thread this was asked about in? I'm curious
    > as to whether or not "the folks who know the Standard well" had
    > offered concerns beyond alignment.


    I asked about it as well when discussing a generic merge-sort that
    relied on each structure starting with it's "struct this *next" pointer
    (rather than ending as is traditional). My sort function had a generic
    struct of that sort that it cast all incoming structures to.

    The consensus was not concerns about alignment - indeed, everybody felt
    it would be almost impossible to find a system that it broke on - but
    that it was *not* guaranteed by the standard.

    IIRC (and I may well not do), if all of them went into a union somewhere
    then it would have to work, and if you have multiple compilation units
    nothing is going to know that there isn't such a union somewhere, but
    nevertheless...
    --
    Online waterways route planner | http://canalplan.eu
    Plan trips, see photos, check facilities | http://canalplan.org.uk
     
    Dr Nick, Jun 12, 2011
    #18
  19. daknok

    Dr Nick Guest

    daknok <> writes:

    > On 2011-06-05 15:45:41 +0200, BartC said:
    >
    >> I meant the str->references-- bit.
    >>
    >> If StringRelease() is called on something that already has a reference count
    >> of 0, then it might go wrong.
    >>
    >> And because such a function is likely to be called from many places where
    >> the caller does not know/care how many active references remain, then that
    >> might be an issue.

    >
    > If the code is written well, this won't be a problem. Even better
    > could I write a macro:
    >
    > SafeStringRelease(s) if (s != NULL) { StringRelease(s); } s = NULL
    >
    > and use that.


    I'd throw as assert in myself (or a custom error routine - cue standard
    discussion about whether assert is wonderful or evil). This is the sort
    of thing that should never happen, so rather than ignoring it silently
    (passing by the macro issues) it indicates a programming error elsewhere
    in your code so I'd want to fail as noisily as possible - certainly when
    developing and testing.
    --
    Online waterways route planner | http://canalplan.eu
    Plan trips, see photos, check facilities | http://canalplan.org.uk
     
    Dr Nick, Jun 12, 2011
    #19
  20. daknok

    Shao Miller Guest

    On 6/11/2011 8:28 PM, Chris M. Thomasson wrote:
    > "Chris M. Thomasson"<> wrote in message
    > news:8cTIp.4134$...
    >> "ImpalerCore"<> wrote in message
    >> news:...
    >>
    >> [...]
    >>
    >>> Unfortunately I do not know how
    >>> to manually find a platform's ALIGN_MAX. I've seen some incantations
    >>> with unions and offsetof, and autoconf has their AC_CHECK_ALIGNOF, but
    >>> I don't know how to use it.

    >>
    >> read all of these:

    > [...]
    >
    >>
    >> the `ALIGN_OF()' function macro should always give you a "sufficient"
    >> alignment for a given type.

    >


    To pull it into this thread, your macro is:

    #define ALIGN_OF(mp_type) \
    offsetof( \
    struct \
    { \
    char pad_ALIGN_OF; \
    mp_type type_ALIGN_OF; \
    }, \
    type_ALIGN_OF \
    )

    Your macro is quite nice for C89 & C99 in that:
    - it expands to a meaningful alignment suggestion
    - it should be an integer constant expression

    One possible disadvantage for C99 is that you cannot use it with a
    variably-modified type.

    > What about [...]
    >
    > http://codepad.org/A65Noc37
    >
    > lol...
    >


    In my opinion, the "union of many types" approach:
    - can waste space
    - is not a guaranteed maximum alignment requirement because it mightn't
    include all types
    - requires that any types used for members be in scope (some might need
    to be #included)
    - is likely to work anyway

    'ref_count_acquire', 'ref_count_release' and 'main' might benefit from
    checking for null pointers, but I doubt you were asking for that kind of
    criticism. ;)
     
    Shao Miller, Jun 12, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ash
    Replies:
    1
    Views:
    436
    SenderX
    Oct 24, 2003
  2. Kalle Rutanen

    Reference counting in C++

    Kalle Rutanen, May 7, 2005, in forum: C++
    Replies:
    0
    Views:
    577
    Kalle Rutanen
    May 7, 2005
  3. Tony Johansson

    reference counting

    Tony Johansson, May 22, 2005, in forum: C++
    Replies:
    4
    Views:
    379
    Andrew Koenig
    May 23, 2005
  4. mathieu
    Replies:
    8
    Views:
    523
    Juha Nieminen
    Aug 31, 2008
  5. edwardfredriks

    counting up instead of counting down

    edwardfredriks, Sep 6, 2005, in forum: Javascript
    Replies:
    6
    Views:
    223
    Dr John Stockton
    Sep 7, 2005
Loading...

Share This Page