Reference counting
daknok
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?
Angel
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
BartC
"daknok" <radek...@gmail.com> wrote in message
news:4deb6008$0$28457$703f...@textnews.kpn.nl...
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
daknok
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
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;
};
BartC
news:4deb74f0$0$28443$703f...@textnews.kpn.nl...
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
daknok
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.
Shao Miller
> 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.
Richard Harter
wrote:
There are many ways to skin this particular cat. A simple way is to
pass in the addresses of the components. In the case of retain you
have one argument, the address of the reference counter. Thus you
call Retain thusly:
Retain(&(str->references));
By the by, you don't need to return the pointer to str in the Retain
functions.
The Release functions are a potential problem because different things
might require different numbers of calls to free. However it looks
like they would each have two - the data array and the struct itself.
Here I will commend to you a little trick. In your struct you have a
little struct that looks like this:
struct releasables {
void * first;
void * second;
};
When you init the struct you set first to the payload and second to
the struct itself. Thus the Release code looks like this.
Release(&(str->references),str->releasables);
The Release code then looks something like this:
void Release(unsigned *references, struct releasables releasables)
{
(*references)--;
if (*references == 0) {
free(releasables->first);
free(releasable->second);
}
}
Incidentally I don't think much of making your Release functions void.
You should return something that indicates whether the struct still
exists or whether it has been freed. Checking the validity of
pointers has a way of preventing unpleasant surprises.
I am sure that you can come up with something slicker and less
cumbersome that the above, which is an off the top of my head sort of
thing. The important thing is this: If you can make all of the
release/retain functions somehow smell the same then you can handle
them all the same.
Eric Sosman
> [...]
> 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
eso...@ieee-dot-org.invalid
Gene
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.
}
ImpalerCore
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.
Shao Miller
> 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[i]);
printf(
"footer_at: [%d] ",
(int)footer_at(sizes[i]) * sizeof (footer_t)
);
printf(
"size_with_footer: [%d] ",
(int)size_with_footer(sizes[i])
);
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.
James Kuyper
...
> 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
Shao Miller
> On Jun 5, 7:17 am, Angel<angel+n...@spamcop.net> wrote:
>> On 2011-06-05, daknok<radekslu...@gmail.com> wrote:
>>
>>> If I want to do simple reference counting for different structures I
>>> would go like 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? :)
ImpalerCore
Granted that kind of C1X feature would be superior. I suppose one
must weigh the utility of the concept against its portability risk.
In the absence of C1X features, I suppose that one could still manage
to make it work by discovering the value corresponding to the concept
of 'alignof(max_align_t)', and configure it for each environment
manually a la '#define ALIGN_MAX N'. 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.
\code snippet
void* rc_malloc( size_t size )
{
void* mem = NULL;
void* p = NULL;
p = malloc( size + ALIGN_MAX );
if ( p )
{
/* Set the reference count to 1. */
*((int*)p) = 1;
mem = (unsigned char*)p + ALIGN_MAX;
}
return mem;
}
\endcode
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.
Best regards,
John D.
Shao Miller
>
> 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*
Chris M. Thomasson
news:52c902de-0f66-4bb0...@hg8g2000vbb.googlegroups.com...
[...]
> 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
news:8cTIp.4134$SG4....@newsfe03.iad...
> "ImpalerCore" <jadi...@gmail.com> wrote in message
> news:52c902de-0f66-4bb0...@hg8g2000vbb.googlegroups.com...
>
> [...]
>
>> 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:
lol...
Dr Nick
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
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.
Shao Miller
> "Chris M. Thomasson"<cri...@charter.net> wrote in message
> news:8cTIp.4134$SG4....@newsfe03.iad...
>> "ImpalerCore"<jadi...@gmail.com> wrote in message
>> news:52c902de-0f66-4bb0...@hg8g2000vbb.googlegroups.com...
>>
>> [...]
>>
>>> 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. ;)
luser- -droog
With a suitable convention established for finding the end, sure.
But the simplest way to find the end is to put a size field or
pointer at the beginning, and we're back to the same alignment
question. So it's hard to explore that option without making the
entire issue more complicated.
Shao Miller
I agree that a disadvantage to accounting at the end is the convention
for finding the end.
The example code offered elsethread has a function that takes a 'size_t'
which must match what was passed to the allocator, and passing this
around is certainly overhead.
For a simple string-accounting struct which keeps track of the size, one
can pass 'sizeof *my_string + my_string->max_length' (or whatever), but
you're right; that seems like an awkward thing to pass to a
reference-releasing function.
For statically-sized objects, a macro makes things a bit easier (note
that 'ptr' is only evaluated once, for whatever that's worth):
#define release(ptr) (release_((ptr), sizeof *(ptr)))
Here's a code example, below. It ought to compile as one file. If
anyone has time to review it, what're some advantages and disadvantages
for the approach?:
#define ALL_IN_ONE 1
/**** ref_cnt.h */
/* For 'size_t' */
#include <stddef.h>
/*** Macros */
#define GetRefForFixedSizeObj(obj) \
(GetRefFromPtrAndSize((obj), sizeof *(obj)))
/*** Object types */
typedef void ** ref_counted_obj;
/*** Function types */
typedef void f_ref_cnt_free(ref_counted_obj);
/*** Functions */
extern ref_counted_obj GetRefFromPtrAndSize(void *, size_t);
extern ref_counted_obj NewRefCountedObj(size_t, f_ref_cnt_free *);
extern ref_counted_obj GetRef(ref_counted_obj);
extern void PutRef(ref_counted_obj);
/**** ref_cnt.c */
#include <stdlib.h>
#if !ALL_IN_ONE
#include <stddef.h>
#include "ref_cnt.h"
#endif
/*** Types */
struct ref_counted_obj_ {
void * obj;
unsigned int ref_count;
f_ref_cnt_free * dealloc;
};
/*** Functions */
static ptrdiff_t ref_at(size_t size) {
size_t result;
result = size;
result += sizeof (struct ref_counted_obj_);
/* Check for wrap-around */
if (result < size)
return 0;
--result;
result /= sizeof (struct ref_counted_obj_);
return (ptrdiff_t) result;
}
ref_counted_obj GetRefFromPtrAndSize(
void * ptr,
size_t size
) {
ptrdiff_t ref_index;
struct ref_counted_obj_ * ref;
ref_index = ref_at(size);
if (!ptr || !ref_index)
return NULL;
/* Point to the accounting info */
ref = ptr;
ref += ref_index;
/* Increment ref count and check for wrap-around */
if (!++ref->ref_count) {
--ref->ref_count;
return NULL;
}
return &ref->obj;
}
ref_counted_obj NewRefCountedObj(
size_t size,
f_ref_cnt_free * dealloc
) {
ptrdiff_t ref_index;
size_t new_size;
struct ref_counted_obj_ * ref;
ref_index = ref_at(size);
if (!ref_index)
return NULL;
/* Calculate required size */
new_size = (ref_index + 1) * sizeof *ref;
/* Check for wrap-around */
if (new_size < size)
return NULL;
/* Allocate and check for failure */
ref = malloc(new_size);
if (!ref)
return NULL;
/* Populate accounting info */
ref[ref_index].obj = ref;
ref += ref_index;
ref->ref_count = 1;
ref->dealloc = dealloc;
return &ref->obj;
}
ref_counted_obj GetRef(ref_counted_obj ref) {
struct ref_counted_obj_ * ref_;
if (!ref)
return NULL;
ref_ = (void *) ref;
/* Increment ref count and check for wrap-around */
if (++ref_->ref_count) {
--ref_->ref_count;
return NULL;
}
return ref;
}
void PutRef(ref_counted_obj ref) {
struct ref_counted_obj_ * ref_;
if (!ref)
return;
ref_ = (void *) ref;
/* Decrement ref count and check for zero */
if (!--ref_->ref_count) {
ref_->dealloc(ref);
free(ref_->obj);
}
return;
}
/**** Test program */
#include <stdio.h>
#include <string.h>
#if !ALL_IN_ONE
#include <stdlib.h>
#include "ref_cnt.h"
#endif
/*** Macros */
#define GetFooRef(foo) \
(GetRefFromPtrAndSize((foo), sizeof *(foo) + (foo)->len))
/*** Types */
struct foo {
double bobble;
size_t len;
char bear[1];
};
/*** Functions */
f_ref_cnt_free foo_dealloc;
void foo_dealloc(ref_counted_obj ptr) {
struct foo * bar;
bar = *ptr;
printf(
"foo_dealloc(%p): {%f, %d, \"%s\"}\n",
*ptr,
bar->bobble,
(int)bar->len,
bar->bear
);
return;
}
int main(void) {
ref_counted_obj bar_ref;
struct foo * bar;
char laughsalot[] = "Laughs-a-lot";
bar_ref = NewRefCountedObj(
sizeof *bar + sizeof laughsalot,
foo_dealloc
);
if (!bar_ref) {
puts("NewRefCountedObj() failed!");
return EXIT_FAILURE;
}
bar = *bar_ref;
bar->bobble = 3.14159;
bar->len = sizeof laughsalot;
memcpy(bar->bear, laughsalot, sizeof laughsalot);
/* Test re-getting the accounting info */
bar_ref = NULL;
bar_ref = GetFooRef(bar);
if (!bar_ref) {
puts("GetRefFromPtrAndSize() failed!");
free(bar); /* Yeah */
return EXIT_FAILURE;
}
/* We have two references */
PutRef(bar_ref);
PutRef(bar_ref);
return EXIT_SUCCESS;
}
ImpalerCore
I just find the interface with your footer method to be more verbose
without any tangible benefit. You add these four functions, yet you
haven't tried to use them to come up with the reference counted
allocation, copy, and release functions.
size_t footer_at(size_t size);
size_t size_with_footer(size_t size);
footer_t * get_footer(void * mem, size_t size);
void * malloc_with_footer(size_t size);
My opinion is that the interface is cluttered, and doesn't even do
what was asked, to reference count. When you come to the release
step, are you going to require everyone to pass in the size of the
allocated object?
void rc_release( void* p, size_t
I_need_to_know_the_object_size_to_find_the_footer );
Raw pointers don't carry the size of the allocated memory with them.
I don't have access to what malloc uses internally. If you have a
malloced character string, are you going to require the user to pass
in the original allocated size of each allocated string so you can
find the footer when you go to decrement its reference count? Placing
the bookkeeping before the object pointer allows one to know where the
bookkeeping object is without knowing the size or contents of the
allocated object.
Write your version of rc_malloc, rc_copy, and rc_release in terms of
your footer interface and make a pros vs cons list. I just see more
cons to this technique without any perceived pros.
Best regards,
John D.
ImpalerCore
> "Chris M. Thomasson" <cris...@charter.net> wrote in messagenews:8cTIp.4134$SG4....@newsfe03.iad...> "ImpalerCore" <jadil...@gmail.com> wrote in message
> >news:52c902de-0f66-4bb0...@hg8g2000vbb.googlegroups.com...
>
> > [...]
>
> >> 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...
Thanks for the sample and thread references, I will give it some study
in my free time.
Best regards,
John D.
Shao Miller
Thanks. I posted more code and thoughts about half a day before your
response. Perhaps your news-reader has filtered it? :)
Is keeping the accounting info before the object and working out some
way to get the alignment right really much more common than keeping it
after the object? (Obviously this is only a poll of anyone here who
responds.)
Have a pleasant day.
Chris M. Thomasson
news:it3roq$ear$1...@dont-email.me...
[...]
>
> /*** Macros */
> #define GetFooRef(foo) \
> (GetRefFromPtrAndSize((foo), sizeof *(foo) + (foo)->len))
[...]
Using macros... Humm, well how about something simple like this:
_____________________________________________________
typedef void (ref_count_func_dtor) (void*);
struct ref_count
{
unsigned count;
ref_count_func_dtor* fp_dtor;
};
#define REF_COUNT_STRUCT(mp_type) \
struct \
{ \
struct ref_count rcount; \
mp_type type; \
}
void* ref_count_sys_create(
size_t size,
ref_count_func_dtor* fp_dtor
){
struct ref_count* const self = malloc(size);
if (! self) return NULL;
self->count = 1;
self->fp_dtor = fp_dtor;
return self + 1;
}
#define REF_COUNT_CREATE(mp_type, mp_fp_dtor) \
ref_count_sys_create( \
sizeof(REF_COUNT_STRUCT(mp_type)), \
(mp_fp_dtor) \
)
#define ref_count_get(mp_state) \
((mp_state) \
? (((struct ref_count*)(mp_state)) - 1) \
: (NULL))
void*
ref_count_acquire(
void* state
){
struct ref_count* const self = ref_count_get(state);
if (! self) return NULL;
++self->count;
return state;
}
void
ref_count_release(
void* state
){
struct ref_count* const self = ref_count_get(state);
if (! self) return;
if (--self->count) return;
if (self->fp_dtor) self->fp_dtor(state);
free(self);
}
_____________________________________________________
ImpalerCore
It depends, if you're a debugging allocator, you'll likely want to put
markers at each end to detect buffer overruns and the like. The
dmalloc and SQLite allocators are examples that place information at
both sides.
The dmalloc allocator simply guesses the alignment by defining
'#define ALLOCATION_ALIGNMENT N' in a conf.h file that just guesses
the alignment from 'ac_cv_sizeof_long'. I haven't investigated how
SQLite goes about it.
For myself, I've never implemented a reference counted pointer scheme,
so what you saw is just conjecture about how I'd attempt it.
> Have a pleasant day.
Same to you.
John D.
Chris M. Thomasson
> "Shao Miller" <sha0....@gmail.com> wrote in message
> news:it3roq$ear$1...@dont-email.me...
> [...]
>
>>
>> /*** Macros */
>> #define GetFooRef(foo) \
>> (GetRefFromPtrAndSize((foo), sizeof *(foo) + (foo)->len))
>
> [...]
>
> Using macros... Humm, well how about something simple like this:
>
> http://codepad.org/CzUX4xDB
[...]
Umm, I don't think that is going to work!
;^o
Shao Miller
> "Shao Miller"<sha0....@gmail.com> wrote in message
> news:it3roq$ear$1...@dont-email.me...
> [...]
>
>>
>> /*** Macros */
>> #define GetFooRef(foo) \
>> (GetRefFromPtrAndSize((foo), sizeof *(foo) + (foo)->len))
>
> [...]
>
> Using macros... Humm, well how about something simple like this:
>
> http://codepad.org/CzUX4xDB
>
Cool. :)
> _____________________________________________________
> typedef void (ref_count_func_dtor) (void*);
>
>
> struct ref_count
> {
> unsigned count;
> ref_count_func_dtor* fp_dtor;
> };
>
>
> #define REF_COUNT_STRUCT(mp_type) \
> struct \
> { \
> struct ref_count rcount; \
> mp_type type; \
> }
>
>
> void* ref_count_sys_create(
> size_t size,
> ref_count_func_dtor* fp_dtor
> ){
> struct ref_count* const self = malloc(size);
> if (! self) return NULL;
> self->count = 1;
> self->fp_dtor = fp_dtor;
> return self + 1;
> }
>
How do you know that '(self + 1) == ((char *) self +
offsetof(REF_COUNT_STRUCT(mp_type), type))'? It might be unlikely that
there is padding there, but is no padding guaranteed?
>
> #define REF_COUNT_CREATE(mp_type, mp_fp_dtor) \
> ref_count_sys_create( \
> sizeof(REF_COUNT_STRUCT(mp_type)), \
> (mp_fp_dtor) \
> )
>
This interface appears to restrict callers to types whose sizes are
known and are integer constant expressions... Not that there's anything
wrong with that. :)
Shao Miller
Well, two people in another C-devoted forum suggested another concern
with keeping the accounting information at/near the end of the allocated
storage: Someone sloppy can overwrite it. By accounting near the
beginning, that might be less likely.
I'm just not sure how one gets the alignment at the beginning to be
guaranteed as correct without making an extra burden to callers, for C
implementations conforming to < C1X.
Given an adaptation of Mr. Chris M. Thomasson's macro:
#define ALIGNOF(type) (offsetof(struct{char c; type t;}, t))
(which, by the way, I just noticed doesn't appear to be guaranteed as
giving the same result every time due to a lack of tag, though that
might be highly unlikely)
We could have a 'malloc' wrapper:
void * malloc_aligned(size_t size, size_t alignment);
But then callers would need to:
some * p = malloc_aligned(
sizeof *p + optional_variable_length,
ALIGNOF(some)
);
where we'd forfeit the convenience of having 'some' appear just once.
Any pad-to-nice-alignment-at-the-beginning strategy for < C1X is just
guessing, isn't it? And the more conservative we are, the greater the
risk of wasted space?
If one only requires a 'ptrdiff_t' or 'size_t' at the beginning, this
might be minimal and could specify where additional accounting info at
the end is, but that does seem complicated.
But even with the overhead of tracking the size of the allocated data
and of requiring that paired with the pointer in order to find the
accounting info, are there scenarios where a caller _shouldn't_ know the
apparent size of the allocated data? Isn't that asking for trouble?
Sentinels are great for unknown lengths, but a call to 'malloc' requires
a known length... Shouldn't this be tracked somewhere as a good
programming practice in order to avoid out-of-bounds accesses?
luser- -droog
I'm too lazy to finish coding this, but what about a simple open-
addressed
hash-table?
#define MAX 100
typedef struct ref_ {
void *ptr;
int count;
void (*final)(void *ptr);
} ref_;
ref_ ref_tab_[2*MAX+1];
void *ref_malloc(size_t sz) { }
void ref_inc(void *ptr) { }
void ref_dec(void *ptr) { }
void ref_set_final(void *ptr, void (*final)(void *ptr)) { }
io_x
"daknok" <radek...@gmail.com> ha scritto nel messaggio
news:4deb6008$0$28457$703f...@textnews.kpn.nl...
> Hi,
>
> If I want to do simple reference counting for different structures I would go
> like this:
>
> 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;
> }
if i would write something as that:
1) i not would write a wrapper to malloc
2) i not would write the referenece counter in the
struct because it waste space
3) for each struct has need referece counter i would write
one global vaiable as in:
int StringCont;
struct String {
char *cString;
size_t length;
};
int vvvCont;
struct vvv{
char *cg;
int le;
};
struct String* CostruttoreString(char* what)
{struct String *a;
char *b;
unsigned c, i;
a=malloc(sizeof(String));
if(a==0) return 0;
c=(what==0? 0: strlen(what));
if((int)c<0) {m: free(a); return 0;}
b=malloc(c+2);
if(b==0) goto m;
for(i=0; i<c; ++i)
b[i]=what[i];
b[i]=0;
a.cString=b;
++StringCont;
if(StringCont<=0)
{printf("overflow string conter\n");
exit(0);
}
a.lenght=c+2;
return a;
}
void DistruttoreString(struct String* what)
{char *b;
if(what==0) return;
free(what.cString);
free(what);
--StringCont;
if(StringCont<0)
{printf("overflow string conter\n");
exit(0);
}
}
there is some problem in multi thread program
for access to the varible counter, so in that case use some
Os sincronizzation
io_x
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
news:4df6ff99$0$2687$4faf...@reader1.news.tin.it...
> struct String* CostruttoreString(char* what)
> {struct String *a;
> char *b;
> unsigned c, i;
>
> a=malloc(sizeof(String));
> if(a==0) return 0;
> c=(what==0? 0: strlen(what));
> if((int)c<0) {m: free(a); return 0;}
> b=malloc(c+2);
> if(b==0) goto m;
> for(i=0; i<c; ++i)
> b[i]=what[i];
if(what!=0)
{for(i=0; i<c; ++i)
b[i]=what[i];
}
else b[0]=0;
Shao Miller
For hashing, is the object representation of a 'void *' guaranteed to be
the same any time a 'void *' points to the same object? Is it likely?
(I think so.) :)
Angel
>
> For hashing, is the object representation of a 'void *' guaranteed to be
> the same any time a 'void *' points to the same object? Is it likely?
> (I think so.) :)
The standard only says pointers are represented in an
implementation-defined manner. But as long as the pointer value doesn't
change, I doubt the representation will. On most implementations, a
pointer is really just a 32- or 64-bit unsigned number, indicating a
certain spot in virtual memory.
--
"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
Shao Miller
> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
> news:4df6ff99$0$2687$4faf...@reader1.news.tin.it...
>> struct String* CostruttoreString(char* what)
>> {struct String *a;
>> char *b;
>> unsigned c, i;
>>
>> a=malloc(sizeof(String));
I think you meant 'sizeof (struct String)' there. :)
I don't completely understand how your code accomplishes reference
counting. Your code appears to keep track of how many strings have been
allocated. But I think that the "reference counting" subject of this
thread is more along the lines of:
- You allocate an object and assume that there is one user of that object.
- Another user can subscribe for use of the object (increment the
reference count of that object).
- A user can unsubscribe ("release") from use of the object (decrement
the reference count of the object).
- When there are no more users of the object, the object can be freed.
Shao Miller
> On 2011-06-14, Shao Miller<sha0....@gmail.com> wrote:
>>
>> For hashing, is the object representation of a 'void *' guaranteed to be
>> the same any time a 'void *' points to the same object? Is it likely?
>> (I think so.) :)
>
> The standard only says pointers are represented in an
> implementation-defined manner. But as long as the pointer value doesn't
> change, I doubt the representation will. On most implementations, a
> pointer is really just a 32- or 64-bit unsigned number, indicating a
> certain spot in virtual memory.
>
The strategy would then seem to be hopefully portable just as
alignment-guessing is also hopefully portable.
What are the odds that a given pointer to a reference-counted object
would have the same, simple XOR "hash" of all of its bytes in common
with another such pointer?
unsigned char ptr_hash(void * ptr) {
unsigned char
* pos = &ptr,
* end = pos + sizeof ptr,
result = 0;
while (pos < end)
result ^= *pos++;
return result;
}
/* pete says UB when 'sizeof (int) == 1' */
static xxx ptr_hash_table[1 << CHAR_BIT];
Maybe 'xxx' is a pointer type to a hopefully short list of pointers
which can be tested with '=='. Such a short list could be 'realloc'd.
But then 'ptr_hash_table' is 'sizeof (xxx) * (1 << CHAR_BIT)' bytes large.
Maybe 'xxx' is an integer type for an index into another array which is
itself 'realloc'd.
(Insert more hashing strategies here.)
Interesting. :)
Keith Thompson
> On 2011-06-14, Shao Miller <sha0....@gmail.com> wrote:
>> For hashing, is the object representation of a 'void *' guaranteed to be
>> the same any time a 'void *' points to the same object? Is it likely?
>> (I think so.) :)
>
> The standard only says pointers are represented in an
> implementation-defined manner. But as long as the pointer value doesn't
> change, I doubt the representation will. On most implementations, a
> pointer is really just a 32- or 64-bit unsigned number, indicating a
> certain spot in virtual memory.
Quibble: Pointer representation is unspecified, not
implementation-defined. The difference is that an implementation
aren't required to document its pointer representation(s).
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
luser- -droog
> Angel <angel+n...@spamcop.net> writes:
> > On 2011-06-14, Shao Miller <sha0.mil...@gmail.com> wrote:
> >> For hashing, is the object representation of a 'void *' guaranteed to be
> >> the same any time a 'void *' points to the same object? Is it likely?
> >> (I think so.) :)
>
> > The standard only says pointers are represented in an
> > implementation-defined manner. But as long as the pointer value doesn't
> > change, I doubt the representation will. On most implementations, a
> > pointer is really just a 32- or 64-bit unsigned number, indicating a
> > certain spot in virtual memory.
>
> Quibble: Pointer representation is unspecified, not
> implementation-defined. The difference is that an implementation
> aren't required to document its pointer representation(s).
>
Does that make it even more seat-of-the-pants than guessing alignment?
Seebs
> On 2011-06-14, Shao Miller <sha0....@gmail.com> wrote:
>> For hashing, is the object representation of a 'void *' guaranteed to be
>> the same any time a 'void *' points to the same object? Is it likely?
>> (I think so.) :)
> The standard only says pointers are represented in an
> implementation-defined manner. But as long as the pointer value doesn't
> change, I doubt the representation will. On most implementations, a
> pointer is really just a 32- or 64-bit unsigned number, indicating a
> certain spot in virtual memory.
On segmented architectures, it is possible for segments to overlap, meaning
that there are multiple pointer representations for the same address; on
such implementations, comparisons have to take that into account.
-s
--
Copyright 2011, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
Shao Miller
Well alignment-guessing seems straight-forward, at least. N1570
has[6.2.8p4] that "... Every valid alignment value shall be a
nonnegative integral power of two." Which 4 KiB satisfies, for
example... Plenty of room for a reference count, a 'size_t' for the
object, a pointer to a handler function for OO "messages," a signature
for the original allocator, a UUID, a doubly-linked-list entry, a
'jmp_buf', some opcode bytes, a checksum of the header...
ImpalerCore
Seems reasonable. For example, how much do you trust users of
sprintf?
> I'm just not sure how one gets the alignment at the beginning to be
> guaranteed as correct without making an extra burden to callers, for C
> implementations conforming to < C1X.
>
> Given an adaptation of Mr. Chris M. Thomasson's macro:
>
> #define ALIGNOF(type) (offsetof(struct{char c; type t;}, t))
>
> (which, by the way, I just noticed doesn't appear to be guaranteed as
> giving the same result every time due to a lack of tag, though that
> might be highly unlikely)
Can you elaborate?
> We could have a 'malloc' wrapper:
>
> void * malloc_aligned(size_t size, size_t alignment);
>
> But then callers would need to:
>
> some * p = malloc_aligned(
> sizeof *p + optional_variable_length,
> ALIGNOF(some)
> );
>
> where we'd forfeit the convenience of having 'some' appear just once.
>
> Any pad-to-nice-alignment-at-the-beginning strategy for < C1X is just
> guessing, isn't it? And the more conservative we are, the greater the
> risk of wasted space?
It's a cost benefit analysis. We're not necessarily limited to using
one single method. A simpler interface can use a conservative
alignment valid for any type to make it easier for the user (assuming
one can determine ALIGN_MAX with enough confidence through platform
and compiler documentation, autoconf, or some C offsetof
incantation). If more performance needs to be squeaked out, a more
complex interface may be used. Personally, I just haven't been in a
situation that's motivated me to think of using reference counting.
> If one only requires a 'ptrdiff_t' or 'size_t' at the beginning, this
> might be minimal and could specify where additional accounting info at
> the end is, but that does seem complicated.
>
> But even with the overhead of tracking the size of the allocated data
> and of requiring that paired with the pointer in order to find the
> accounting info, are there scenarios where a caller _shouldn't_ know the
> apparent size of the allocated data?
The design of malloc is predicated on the user not needing to track
the size of the allocation. Otherwise C would be designed with
'free( void* p, size_t sz )'. Of course, malloc is responsible to
track allocation size internally, but it's in the implementation
space, not user space. For better or worse, there is no standard
method to take a raw pointer and obtain its allocation size. There
are times when knowing the allocation space is desirable: designing a
custom allocator, managing an auto-resizing container like a string or
array, when its the destination buffer of a snprintf function, etc,
but certainly not universal.
> Isn't that asking for trouble?
> Sentinels are great for unknown lengths, but a call to 'malloc' requires
> a known length... Shouldn't this be tracked somewhere as a good
> programming practice in order to avoid out-of-bounds accesses?
That is in the realm of debugging allocators, which is good practice
to use. Delegating this responsibility directly to users is in my
opinion a bad idea.
Most debugging allocators use the preprocessor to replace instances of
'malloc' with their own special call to allocator. By providing your
own malloc wrapper, one can create an interface to allocate a
reference counted pointer through something like 'rc_malloc', but
still tap into dmalloc or valgrind to verify that your implementation
doesn't trash the address space, i.e.
---dmalloc.h---
#define malloc(size) \
dmalloc_malloc(__FILE__, __LINE__, (size), DMALLOC_FUNC_MALLOC, 0,
0)
Again, this is just one path from several viable methods to implement
reference counting. I'm not arguing for superiority of one method
over another simply because I have no real-use experience with
reference counting, just curiosity.
Best regards,
John D.
Tim Rentsch
> 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'. [snip]
Unless one considers the type 'unsigned int' to be a type
different from that of 'int'.
Tim Rentsch
> Angel <angel...@spamcop.net> writes:
>> On 2011-06-14, Shao Miller <sha0....@gmail.com> wrote:
>>> For hashing, is the object representation of a 'void *' guaranteed to be
>>> the same any time a 'void *' points to the same object? Is it likely?
>>> (I think so.) :)
>>
>> The standard only says pointers are represented in an
>> implementation-defined manner. But as long as the pointer value doesn't
>> change, I doubt the representation will. On most implementations, a
>> pointer is really just a 32- or 64-bit unsigned number, indicating a
>> certain spot in virtual memory.
>
> Quibble: Pointer representation is unspecified, not
> implementation-defined. [snip]
How do you reconcile this assertion with 6.2.6.1p2? Certainly
it looks like the representation of any pointer value stored in
an object would be (at least) implementation-defined.
Keith Thompson
Quite easily: by failing to read it carefully enough. 8-)}
But now that I have, I'm confused. Here's what it says:
1 The representations of all types are unspecified except as
stated in this subclause.
2 Except for bit-fields, objects are composed of contiguous
sequences of one or more bytes, the number, order, and
encoding of which are either explicitly specified or
implementation-defined.
3 Values stored in unsigned bit-fields and objects of type unsigned
char shall be represented using a pure binary notation.
As far as I can tell, *all* types have implementation-defined
representations; the section says so for non bit-fields and for
unsigned bit-fields, and I don't think there's enough wiggle room
to say that signed bit-fields have unspecified representations.
So why does paragraph 1 say "unspecified" rather than
"implementation-defined"? "(Unspecified" is a subset of
"implementation-defined", so it's not wrong, but it seems needlessly
unspecific.
luser- -droog
> An external table would avoid all the alignment-guessing for pre-C1X.
> I'm too lazy to finish coding this, but what about a simple open-
> addressed
> hash-table?
Laziness overcome!
517(0)10:47 PM:~ 0> cat rfct.c
#define TEST
enum { MAX = 100, TABSZ = 2*MAX+1 };
#include <stdlib.h>
struct ref_ {
void *ptr;
int count;
void (*final)(void *ptr);
} typedef ref_;
ref_ ref_tab_[TABSZ];
void ref_init(void) {
int i;
for (i=0; i < TABSZ; i++) {
ref_tab_[i] = (ref_){ .ptr = NULL, .count = 0, .final =
NULL };
}
}
/* courtesy of Shao Miller */
unsigned char ptr_hash(void * ptr) {
unsigned char
* pos = (void *)&ptr,
* end = pos + sizeof ptr,
result = 0;
while (pos < end)
result ^= *pos++;
return result;
}
/* pete says UB when 'sizeof (int) == 1' */
/* static xxx ptr_hash_table[1 << CHAR_BIT]; */
ref_ *ref_find(void *ptr) {
int
h = ptr_hash(ptr) % TABSZ,
i = h;
if (ptr == ref_tab_[i].ptr || ref_tab_[i].ptr == NULL)
return &ref_tab_[i];
for (++i; i < TABSZ; i++) {
if (ptr == ref_tab_[i].ptr || ref_tab_[i].ptr == NULL)
return &ref_tab_[i];
}
for (i = 0; i < h; i++) {
if (ptr == ref_tab_[i].ptr || ref_tab_[i].ptr == NULL)
return &ref_tab_[i];
}
return NULL;
}
void ref_new(void *ptr) {
ref_ *ref = ref_find(ptr);
if (ref) {
ref->ptr = ptr;
ref->count = 1;
ref->final = free;
}
}
ref_ *ref_get(void *ptr) {
ref_ *ref = ref_find(ptr);
if (ref)
if (ref->ptr == NULL)
return NULL;
return ref;
}
void *ref_malloc(size_t sz) {
void *ptr = malloc(sz);
if (ptr)
ref_new(ptr);
return ptr;
}
void ref_inc(void *ptr) {
ref_ *ref = ref_get(ptr);
if (ref) ref->count++;
}
void ref_dec(void *ptr) {
ref_ *ref = ref_get(ptr);
if (ref)
if (--ref->count == 0) {
ref->final(ptr);
ref->ptr = 0;
ref->final = NULL;
}
}
void ref_set_final(void *ptr, void (*final)(void *ptr)) {
ref_ *ref = ref_get(ptr);
if (ref)
ref->final = final;
}
#ifdef TEST
#include <string.h>
#include <stdio.h>
#define strdup(s) strcpy(ref_malloc(sizeof(s)),s)
void print(char *s) {
ref_inc(s);
if (ref_get(s)) printf("%s\n", s);
ref_dec(s);
}
int main(void) {
ref_init();
char *s = strdup("apple");
char *t = strdup("banana");
print(s); /* apple */
print(t); /* banana */
ref_dec(s);
print(s); /* */
print(t); /* banana */
ref_dec(t);
print(s); /* */
print(t); /* */
return 0;
}
#endif
518(0)10:47 PM:~ 0> make rfct && rfct
cc -g -Wall -c -o rfct.o rfct.c
cc rfct.o -o rfct
apple
banana
banana
519(0)10:47 PM:~ 0>
Shao Miller
> On Jun 13, 6:33 pm, Shao Miller<sha0.mil...@gmail.com> wrote:
>>
>> Well, two people in another C-devoted forum suggested another concern
>> with keeping the accounting information at/near the end of the allocated
>> storage: Someone sloppy can overwrite it. By accounting near the
>> beginning, that might be less likely.
>
> Seems reasonable. For example, how much do you trust users of
> sprintf?
>
Indeed.
>> I'm just not sure how one gets the alignment at the beginning to be
>> guaranteed as correct without making an extra burden to callers, for C
>> implementations conforming to< C1X.
>>
>> Given an adaptation of Mr. Chris M. Thomasson's macro:
>>
>> #define ALIGNOF(type) (offsetof(struct{char c; type t;}, t))
>>
>> (which, by the way, I just noticed doesn't appear to be guaranteed as
>> giving the same result every time due to a lack of tag, though that
>> might be highly unlikely)
>
> Can you elaborate?
>
If you have:
struct {
int x;
} foo;
struct {
int x;
} bar;
I believe that you are not guaranteed that 'sizeof foo == sizeof bar',
as they have different types... Though I find it highly unlikely.
Similarly, the 'ALIGNOF' macro above could yield different results upon
invocations with the same 'type' because the implementation could have
generated different padding for the different types of "helper" structs.
>> We could have a 'malloc' wrapper:
>>
>> void * malloc_aligned(size_t size, size_t alignment);
>>
>> But then callers would need to:
>>
>> some * p = malloc_aligned(
>> sizeof *p + optional_variable_length,
>> ALIGNOF(some)
>> );
>>
>> where we'd forfeit the convenience of having 'some' appear just once.
>>
>> Any pad-to-nice-alignment-at-the-beginning strategy for< C1X is just
>> guessing, isn't it? And the more conservative we are, the greater the
>> risk of wasted space?
>
> It's a cost benefit analysis. We're not necessarily limited to using
> one single method. A simpler interface can use a conservative
> alignment valid for any type to make it easier for the user (assuming
> one can determine ALIGN_MAX with enough confidence through platform
> and compiler documentation, autoconf, or some C offsetof
> incantation). If more performance needs to be squeaked out, a more
> complex interface may be used. Personally, I just haven't been in a
> situation that's motivated me to think of using reference counting.
>
Well, assuming the 'ALIGNOF' above is a pretty good alignment guess, the
code example below makes use of it to allocate an object with a
reference-counting prefix object. It doesn't have:
- 'sprintf' user concerns ;)
- the overhead of tracking an object's originally-allocated size
I'm not sure what disadvantages there are to the approach in the code
below. Any ideas? (Or anyone else?)
>> If one only requires a 'ptrdiff_t' or 'size_t' at the beginning, this
>> might be minimal and could specify where additional accounting info at
>> the end is, but that does seem complicated.
>>
>> But even with the overhead of tracking the size of the allocated data
>> and of requiring that paired with the pointer in order to find the
>> accounting info, are there scenarios where a caller _shouldn't_ know the
>> apparent size of the allocated data?
>
> The design of malloc is predicated on the user not needing to track
> the size of the allocation. Otherwise C would be designed with
> 'free( void* p, size_t sz )'. Of course, malloc is responsible to
> track allocation size internally, but it's in the implementation
> space, not user space. For better or worse, there is no standard
> method to take a raw pointer and obtain its allocation size. There
> are times when knowing the allocation space is desirable: designing a
> custom allocator, managing an auto-resizing container like a string or
> array, when its the destination buffer of a snprintf function, etc,
> but certainly not universal.
>
I agree that it's a burden to pass around a size, but was just
commenting on the sanity of having it handy.
>> Isn't that asking for trouble?
>> Sentinels are great for unknown lengths, but a call to 'malloc' requires
>> a known length... Shouldn't this be tracked somewhere as a good
>> programming practice in order to avoid out-of-bounds accesses?
>
> That is in the realm of debugging allocators, which is good practice
> to use. Delegating this responsibility directly to users is in my
> opinion a bad idea.
>
Hmmm... Yes I guess it's automation and burden-relief versus
encouraging awareness of every detail.
> Most debugging allocators use the preprocessor to replace instances of
> 'malloc' with their own special call to allocator. By providing your
> own malloc wrapper, one can create an interface to allocate a
> reference counted pointer through something like 'rc_malloc', but
> still tap into dmalloc or valgrind to verify that your implementation
> doesn't trash the address space, i.e.
>
> ---dmalloc.h---
>
> #define malloc(size) \
> dmalloc_malloc(__FILE__, __LINE__, (size), DMALLOC_FUNC_MALLOC, 0,
> 0)
>
> Again, this is just one path from several viable methods to implement
> reference counting. I'm not arguing for superiority of one method
> over another simply because I have no real-use experience with
> reference counting, just curiosity.
Well unfortunately, the 'pfxalloc' function below is not a drop-in
replacement for 'malloc', but a wrapper function or macro or both could
potentially produce a drop-in replacement.
Here's the code, which ought to compile as a single file, or one can
split it up into multiple files. Also available, with nice colours, at:
-----
/**
* Delete all lines containing
* 'ALL_IN_ONE' if you split this example
* into separate files.
*/
#define ALL_IN_ONE 1
/****
* pfxalloc.h
*
* Shao Miller, 2011
* It took several minutes to find
* a free *alloc. (No pun intended.)
*/
#ifndef PFXALLOC_H_
/* For 'offsetof' and 'size_t' */
#include <stddef.h>
/*** Macros */
#define PFXALLOC_H_
#ifndef alignof
/* Derived from Mr. Chris M. Thomasson */
#define alignof(type) \
(offsetof(struct {char c; type t;}, t))
#ifdef __alignof_is_defined
#undef __alignof_is_defined
#endif /* __alignof_is_defined */
#define __alignof_is_defined 1
#endif /* alignof */
/*** Functions */
/**
* Allocate memory for an object and an
* associated "prefix" object.
*
* @v pfx_size The "prefix" size.
* @v obj_alignment The object's alignment
* requirement.
* @v obj_size The object's size.
* @ret void * Points to the object,
* or is NULL for failure.
*/
extern void * pfxalloc(size_t, size_t, size_t);
/**
* Get an object's associated "prefix" object.
*
* @v obj The object to fetch the
* associated "prefix" for.
* @ret void * Points to the "prefix",
* or is NULL for failure.
*/
extern void * pfxget(void *);
#endif /* PFXALLOC_H_ */
/**** pfxalloc.c */
/* Shao Miller, 2011 */
/* For 'malloc' */
#include <stdlib.h>
#if !ALL_IN_ONE
/* For 'size_t', 'ptrdiff_t' and 'NULL' */
#include <stddef.h>
/* For 'alignof' */
#include "pfxalloc.h"
#endif /* !ALL_IN_ONE */
/*** Constants */
enum cv {
cv_ptrdiff_alignment =
alignof(ptrdiff_t),
cv_zero = 0
};
/*** Functions */
/**
* The layout looks like:
* +-----+-------------+--------+--------+
* | pfx | opt_padding | offset | |
* +- -+- -+- -+ object |
* | header | |
* +----------------------------+--------+
*/
void * pfxalloc(
size_t pfx_size,
size_t obj_alignment,
size_t obj_size
) {
size_t offset_at;
ptrdiff_t * offset;
size_t header_size;
size_t total_size;
unsigned char * mem;
unsigned char * obj;
/* Sanity-check alignment value */
if (obj_alignment & (obj_alignment - 1))
return NULL;
/* Calculate the offset position */
offset_at = pfx_size;
offset_at += sizeof *offset;
/* Check for wrap-around */
if (offset_at < pfx_size)
return NULL;
--offset_at;
offset_at /= sizeof *offset;
/* Calculate the header size */
header_size = (offset_at + 1) * sizeof *offset;
/* Check for wrap-around */
if (header_size < pfx_size)
return NULL;
/* Calculate padding */
if (obj_alignment > cv_ptrdiff_alignment) {
size_t new_hdr_size = header_size;
new_hdr_size += obj_alignment;
/* Check for wrap-around */
if (new_hdr_size < header_size)
return NULL;
--new_hdr_size;
new_hdr_size /= obj_alignment;
new_hdr_size *= obj_alignment;
header_size = new_hdr_size;
}
/* Allocate storage */
total_size = header_size + obj_size;
/* Check for wrap-around */
if (total_size < pfx_size || total_size < obj_size)
return NULL;
mem = malloc(total_size);
if (!mem)
return mem;
/* Point to the object */
obj = mem + header_size;
/* Note the offset to the prefix */
offset = (ptrdiff_t *) obj - 1;
*offset = obj - mem;
return obj;
}
/* Fetch an asociated prefix for an object */
void * pfxget(void * obj) {
ptrdiff_t * offset;
unsigned char * prefix;
if (!obj)
return obj;
offset = obj;
--offset;
prefix = obj;
prefix -= *offset;
return prefix;
}
/**** ref_cnt.h */
/* Shao Miller, 2011 */
#ifndef REF_CNT_H_
#if !ALL_IN_ONE
/* For 'size_t' */
#include <stddef.h>
#include "align.h"
#endif /* !ALL_IN_ONE */
/*** Macros */
#define REF_CNT_H_
/*** Function types */
typedef void f_ref_cnt_free(void *);
/*** Functions */
/**
* Create a new, reference-counted object
*
* @v size The size of the object
* to allocate, in bytes.
* @v alignment The alignment requirement
* for the object.
* @v dealloc The de-allocation function
* to call, when refs == 0.
* @ret void * Points to the newly-
* allocated object, or is
* NULL, upon failure.
*/
extern void * NewRefCountedObj(
size_t,
size_t,
f_ref_cnt_free *
);
/**
* Increment the reference count for an object.
*
* @v obj The object to reference.
* @ret void * Points to the object, or is
* NULL if too many references.
*/
extern void * GetRef(void *);
/**
* Decrement the reference count for an object.
*
* @v obj The object to dereference.
*/
extern void PutRef(void *);
#endif /* REF_CNT_H_ */
/**** ref_cnt.c */
/* Shao Miller, 2011 */
#if !ALL_IN_ONE
/* For 'size_t' */
#include <stddef.h>
#include "pfxalloc.h"
#include "ref_cnt.h"
#endif /* !ALL_IN_ONE */
/*** Types */
struct ref_counted_obj {
unsigned int ref_count;
f_ref_cnt_free * dealloc;
};
/*** Functions */
void * NewRefCountedObj(
size_t size,
size_t alignment,
f_ref_cnt_free * dealloc
) {
void * result;
struct ref_counted_obj * ref;
/* Allocate the object */
result = pfxalloc(
sizeof *ref,
alignment,
size
);
if (!result)
return result;
ref = pfxget(result);
if (!ref) {
/* Uh oh; this is unexpected! */
return ref;
}
/* Populate accounting info */
ref->ref_count = 1;
ref->dealloc = dealloc;
return result;
}
void * GetRef(void * obj) {
struct ref_counted_obj * ref;
ref = pfxget(obj);
if (!ref)
return ref;
/* Increment ref count and check for wrap-around */
if (!++ref->ref_count) {
--ref->ref_count;
return NULL;
}
return obj;
}
void PutRef(void * obj) {
struct ref_counted_obj * ref;
ref = pfxget(obj);
if (!ref)
return;
/* Decrement ref count and check for zero */
if (!--ref->ref_count) {
ref->dealloc(obj);
free(ref);
}
return;
}
/**** Test program */
/* Shao Miller, 2011 */
#include <stdio.h>
#include <string.h>
#if !ALL_IN_ONE
#include <stdlib.h>
#include "pfxalloc.h"
#include "ref_cnt.h"
#endif /* !ALL_IN_ONE */
/*** Types */
struct foo {
double bobble;
size_t len;
char bear[1];
};
/*** Functions */
f_ref_cnt_free foo_dealloc;
void foo_dealloc(void * ptr) {
struct foo * bar;
bar = ptr;
printf(
"foo_dealloc(%p): {%f, %d, \"%s\"}\n",
ptr,
bar->bobble,
(int)bar->len,
bar->bear
);
return;
}
int main(void) {
struct foo * bar;
char laughsalot[] = "Laughs-a-lot";
bar = NewRefCountedObj(
sizeof *bar + sizeof laughsalot,
alignof (struct foo),
foo_dealloc
);
if (!bar) {
puts("NewRefCountedObj() failed!");
return EXIT_FAILURE;
}
bar->bobble = 3.14159;
bar->len = sizeof laughsalot;
memcpy(bar->bear, laughsalot, sizeof laughsalot);
/* Test getting a reference */
bar = GetRef(bar);
if (!bar) {
puts("GetRef() failed!");
PutRef(bar);
return EXIT_FAILURE;
}
/* We have two references */
PutRef(bar);
PutRef(bar);
return EXIT_SUCCESS;
}
Tim Rentsch
> "implementation-defined"? [snip]
Here's a possible idea: maybe paragraph 1 is talking about
representations generally (including, eg, registers), but
paragraph 2 is talking about representations specifically
only in objects. So values of a type can be represented
outside of being stored in an object, but what those
representations might be is all "under the hood", with no
documentation required. What do you think? Does that make
sense?
luser- -droog
> Hi,
>
> 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?
+1 for an excellent question leading to a very interesting thread!
Keith Thompson
My impression is that the idea of representation applies only to
objects. The representation of a value not stored in an object is
irrelevant until and unless it's stored in an object.
I think your idea makes some sense, but I don't think it's what
6.2.6.1 is referring to.
I have no particular support for this.
jameskuyper
> James Kuyper <james...@verizon.net> writes:
>
> > On 06/10/2011 02:30 PM, ImpalerCore wrote:
...
> >>
> >> 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'. [snip]
>
> Unless one considers the type 'unsigned int' to be a type
> different from that of 'int'.
I was talking about types "with a size ... that is different from that of 'int'". 'unsigned int' is a type with a size that is guaranteed to be the same as that of 'int', so that type is just as safe as 'int' itself.
Ian Collins
Please don't use the sociopathic "new" google interface, it ruins threading!
--
Ian Collins
Chris M. Thomasson
[...]
> Given an adaptation of Mr. Chris M. Thomasson's macro:
>
> #define ALIGNOF(type) (offsetof(struct{char c; type t;}, t))
>
> (which, by the way, I just noticed doesn't appear to be guaranteed as
> giving the same result every time due to a lack of tag, though that might
> be highly unlikely)
>
> We could have a 'malloc' wrapper:
>
> void * malloc_aligned(size_t size, size_t alignment);
>
> But then callers would need to:
>
> some * p = malloc_aligned(
> sizeof *p + optional_variable_length,
> ALIGNOF(some)
> );
>
> where we'd forfeit the convenience of having 'some' appear just once.
You mean something like this crazy shi%:
? ;^o
[...]
Chris M. Thomasson
news:BraKp.8802$F25....@newsfe04.iad...
>>
>> void * malloc_aligned(size_t size, size_t alignment);
>> where we'd forfeit the convenience of having 'some' appear just once.
>
> You mean something like this crazy shi%:
>
> http://codepad.org/Ot7HL6Te
I was allocating too much space in the code above. Here is an "improved"
version:
Sorry about that.
pete
Do you think that the value of (-1 & 3)
corresponds to the way that an implementation
represents negative integers?
Constants have object types.
In C89, the standard talks about the representation
of object types.
There's no mention of "object representation" in C89.
I think it was better that way.
--
pete
James Kuyper
> On 06/16/11 09:42 AM, jameskuyper wrote:
>
> Please don't use the sociopathic "new" google interface, it ruins threading!
Sorry about that. I normally post from my home machine, and use Google
only for tracking the newsgroups when not at home. I should have been
more careful about responding.
--
James Kuyper
James Kuyper
> Keith Thompson wrote:
...
>> My impression is that the idea of representation applies only to
>> objects. The representation of a value not stored in an object is
>> irrelevant until and unless it's stored in an object.
>>
>> I think your idea makes some sense, but I don't think it's what
>> 6.2.6.1 is referring to.
>>
>> I have no particular support for this.
>
> Do you think that the value of (-1 & 3)
> corresponds to the way that an implementation
> represents negative integers?
The way that the bit-wise operators behave is defined in terms of the
bits, even though C operators only operate on values, and bits are a
feature of the corresponding representation. This is less than ideal, IMO.
The only exception is the bit-wise shift operators; but interestingly
enough, the result is at best implementation-defined, and at worst,
undefined, whenever a shift would otherwise seem to involve a sign bit
that is non-zero.
--
James Kuyper
io_x
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
what about my try?
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
// macro for types
#define u64 uint64_t
#define u32 uint32_t
#define u16 uint16_t
#define u8 uint8_t
#define uns unsigned
#define dbl double
// macro for function
#define P printf
// macro for keyWords
#define G goto
#define R return
#define W while
#define F for
union tipidiarray{
double a;
size_t v;
u8* m;
};
/* suppone che gli array di double, size_t
u8* si mantengano allineati */
u32 elemento=sizeof(union tipidiarray);
u8* IniMem(u32 s)
{u8 *p;
u32 *pu;
u32 c;
if(s==0) R 0;
c=s; c+=elemento;
if(c<s) R 0;
p=malloc(c);
if(p==0) R 0;
pu=(u32*)p; p+=elemento;
pu[0]=1; pu[1]=(u32)p;
return p;
}
u8* GetRef(u8* v)
{u8 *p;
u32 *pu;
if(v==0) R 0;
p=v-elemento; pu=(u32*)p;
if(pu[0]==0||pu[1]!=(u32)v) R 0;
++pu[0];
if(pu[0]==0){--pu[0]; R 0;}
R v;
}
u32 GetRefCounter(u8* v)
{u8 *p;
u32 *pu;
if(v==0) R 0;
p=v-elemento; pu=(u32*)p;
if(pu[1]!=(u32)v) R (u32)-1;
R pu[0];
}
u8* PutRef(u32* ris, u8* v)
{u8 *p;
u32 *pu;
if(ris==0||v==0) R 0;
*ris=0;
p=v-elemento; pu=(u32*)p;
if(pu[0]==0||pu[1]!=(u32)v)
{*ris=-1; R 0;}
--pu[0];
if(pu[0]==0)
{ pu[1]=0; free(p); }
R 0;
}
int main(void)
{double *arrd, *pad;
u32 *arru, *elm, ris;
if(2*sizeof(u32)>elemento )
{P("Errore di inizializzazione\n"); R 0;}
arrd=(double*)IniMem(10*sizeof(double));
arrd[0]=1.111;
pad=(dbl*)GetRef((u8*)arrd);
if(pad==0) {P("Errore della funzione GetRef()\n");
P("o memoria insufficiente\n");
exit(0);
}
P("val=%f nref=%u\n", pad[0], (uns)GetRefCounter((u8*)arrd));
pad=(dbl*)PutRef(&ris, (u8*)pad);
P("val=%f nref=%u pad=%p ris=%u\n",
arrd[0], (uns)GetRefCounter((u8*)arrd), (u8*)pad, (uns) ris);
arrd=(dbl*)PutRef(&ris, (u8*)pad);
P("nref=%u ris=%u\n", (uns)GetRefCounter((u8*)arrd), (uns) ris);
R 0;
}
Ian Collins
> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
> news:4df70a29$0$2690$4faf...@reader1.news.tin.it...
>
> what about my try?
>
> #include<stdio.h>
> #include<stdlib.h>
> #include<stdint.h>
>
> // macro for types
> #define u64 uint64_t
> #define u32 uint32_t
> #define u16 uint16_t
> #define u8 uint8_t
> #define uns unsigned
> #define dbl double
>
> // macro for function
> #define P printf
Sane readers will have given up by here.
--
Ian Collins
io_x
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
>
> "io_x" <a...@b.c.invalid> ha scritto nel messaggio
> news:4df70a29$0$2690$4faf...@reader1.news.tin.it...
>
> what about my try?
someone think there are too many cast?
what about consider for align
union tipidiarray{
double a;
size_t v;
u8* m;
};
and think are possible array of each element of that union?
so if "a" is aligned to double, size_t, u8*
"a"+sizeof(double), "a"+sizeof(size_t)
"a"+sizeof(u8*) has to be aligned to each rispettive type
and so if "a" is a return address of malloc
"a"+sizeof(tipidiarray)
is ok for double, size_t, u8*
[if "a" point to sufficient memory]
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
// macro for types
#define u64 uint64_t
#define u32 uint32_t
#define u16 uint16_t
#define u8 uint8_t
#define uns unsigned
#define dbl double
// macro for function
#define P printf
// macro for keyWords
#define G goto
#define R return
#define W while
#define F for
union tipidiarray{
double a;
size_t v;
u8* m;
};
u32 elemento=sizeof(union tipidiarray);
u8* IniMem(u32 s)
{u8 *p;
u32 *pu;
u32 c;
if(s==0) R 0;
c=s; c+=elemento;
if(c<=s) R 0;
p=malloc(c);
if(p==0) R 0;
pu=(u32*)p; p+=elemento;
pu[0]=1; pu[1]=(u32)p;
R p;
}
u8* GetRef(u8* v)
{u8 *p;
u32 *pu;
if(v==0) R 0;
p=v-elemento; pu=(u32*)p;
if(pu[0]==0||pu[1]!=(u32)v) R 0;
++pu[0];
if(pu[0]==0){--pu[0]; R 0;}
R v;
}
u32 GetRefCounter(u8* v)
{u8 *p;
u32 *pu;
if(v==0) R 0;
p=v-elemento; pu=(u32*)p;
if(pu[1]!=(u32)v) R (u32)-1;
R pu[0];
}
u8* PutRef(u32* ris, u8* v)
{u8 *p;
u32 *pu;
if(ris==0) R 0;
*ris=0;
if(v==0) R 0;
p=v-elemento; pu=(u32*)p;
if(pu[0]==0||pu[1]!=(u32)v)
{*ris=-1; R 0;}
--pu[0];
if(pu[0]==0)
{ pu[1]=0; free(p); }
R 0;
}
int main(void)
{double *arrd, *pad;
u32 *arru, *elm, ris;
if(2*sizeof(u32)>elemento )
{P("Errore di inizializzazione\n"); R 0;}
arrd=(double*)IniMem(10*sizeof(double));
arrd[0]=1.111;
pad=(double*)GetRef((u8*)arrd);
if(pad==0) {P("Errore della funzione GetRef()\n");
P("o memoria insufficiente\n");
exit(0);
}
P("val=%f nref=%u\n", pad[0], (uns)GetRefCounter((u8*)arrd));
pad=(dbl*)PutRef(&ris, (u8*)pad);
P("val=%f nref=%u pad=%p ris=%u\n",
arrd[0], (uns)GetRefCounter((u8*)arrd), (u8*)pad, (uns) ris);
arrd=(double*)PutRef(&ris, (u8*)pad);
christian.bau
> 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?
Go to the apple website, look around for the Core Foundation source
code, and look at the source code for CFRetain / CFRelease.
Shao Miller
To save people some time, here it is (I think):
http://www.opensource.apple.com/source/CF/CF-550.42/CFRuntime.c
Chris M. Thomasson
I think there is an error in `xmalloc_aligned()' because I subtract
`sizeof(void*)' from the aligned user object base address! This might not be
correct because `sizeof(void*)' could be `4' and `ALIGN_OF(void*)' (assume
100% correct result for a moment) just might be 128!
Therefore, I need to use something like:
___________________________________________
#define ALIGN_PTR_SZ \
(ALIGN_OF(void*) > sizeof(void*) \
? ALIGN_OF(void*) \
: sizeof(void*))
___________________________________________
as an offset wrt the aligned "user object" portion of the allocated
memory...
;^/
Shao Miller
> "Chris M. Thomasson"<cri...@charter.net> wrote in message
> news:rzaKp.360$lv6...@newsfe12.iad...
>> "Chris M. Thomasson"<cri...@charter.net> wrote in message
>> news:BraKp.8802$F25....@newsfe04.iad...
>>> "Shao Miller"<sha0....@gmail.com> wrote in message
>>> news:it5vnd$4qo$1...@dont-email.me...
>> [...]
>>>> We could have a 'malloc' wrapper:
>>>>
>>>> void * malloc_aligned(size_t size, size_t alignment);
>> [...]
>>>> where we'd forfeit the convenience of having 'some' appear just once.
>>>
>>> You mean something like this crazy shi%:
>>>
>>> http://codepad.org/Ot7HL6Te
>>
>> I was allocating too much space in the code above. Here is an "improved"
>> version:
>>
>> http://codepad.org/fOAFnYCZ
>>
>> Sorry about that.
>
> I think there is an error in `xmalloc_aligned()' because I subtract
> `sizeof(void*)' from the aligned user object base address! This might not be
> correct because `sizeof(void*)' could be `4' and `ALIGN_OF(void*)' (assume
> 100% correct result for a moment) just might be 128!
>
I think you mean "assume 100% incorrect result for a moment," right? If
it was a correct result, the alignment couldn't be greater than the
'sizeof'... The 'sizeof' must be an integer multiple of the alignment
requirement, else arrays wouldn't work. I might have misunderstood you. :)
>
> Therefore, I need to use something like:
> ___________________________________________
> #define ALIGN_PTR_SZ \
> (ALIGN_OF(void*)> sizeof(void*) \
> ? ALIGN_OF(void*) \
> : sizeof(void*))
> ___________________________________________
>
>
> as an offset wrt the aligned "user object" portion of the allocated
> memory...
>
> ;^/
>
Interesting code, by the way.
Chris M. Thomasson
Sorry; I was _really_ decoupling `ALIGN_OF()' with `sizeof()'!
Chris M. Thomasson
>>> I think there is an error in `xmalloc_aligned()' because I subtract
>>> `sizeof(void*)' from the aligned user object base address! This might
>>> not be
>>> correct because `sizeof(void*)' could be `4' and `ALIGN_OF(void*)'
>>> (assume
>>> 100% correct result for a moment) just might be 128!
>>>
>>
>> I think you mean "assume 100% incorrect result for a moment," right? If
>> it was a correct result, the alignment couldn't be greater than the
>> 'sizeof'... The 'sizeof' must be an integer multiple of the alignment
>> requirement, else arrays wouldn't work. I might have misunderstood you.
>> :)
>
> Sorry; I was _really_ decoupling `ALIGN_OF()' with `sizeof()'!
think in terms of `sizeof(data-structure-A)' is less than alignment for said
`(data-structure-A)'. This can be fairly common.
sizeof(foo) can be 4
alignof(foo) might be 1024
Who knows right?
Shao Miller
Over a couple of days, Chris M. Thomasson wrote:
> #include <stdio.h>
> #include <stdlib.h>
> #include <stddef.h>
> #include <assert.h>
>
> #if ! defined (ALIGN_UINTPTR_TYPE)
> # define ALIGN_UINTPTR_TYPE size_t
> #endif
>
So it seems you allow for an override, above. Whatever the choice, the
result of casting a pointer to an integer type is
implementation-defined[6.3.2.3p6]. The result needn't be particularly
meaningful, though it'd probably be pretty sensible to convert to an
integer representing a linear address for an environment with such an
addressing model. An implementation needn't support 'intptr_t' nor
'uintptr_t', for example[7.18.1.4p1].
>
> typedef char ALIGN_STATIC_ASSERT
> [
> sizeof(ALIGN_UINTPTR_TYPE) == sizeof(void*)
> ? 1 : -1
> ];
>
Ok so whatever the choice of this special type, its size must be equal
to 'sizeof (void *)'. I guess the idea is that a 'void *' is an
integer-in-disguise and casting to this integer type with the same size
ought not to "involve much"?
>
> #define ALIGN_OF(mp_type) \
> offsetof( \
> struct \
> { \
> char pad; \
> mp_type type; \
> }, \
> type \
> )
>
'mp' for "macro parameter"? :)
>
> #define ALIGN_UP(mp_ptr, mp_align) \
> ((void*)( \
> (((ALIGN_UINTPTR_TYPE)(mp_ptr)) + \
> ((mp_align) - 1)) & ~(((mp_align) - 1)) \
> ))
>
Above, you cast a pointer to an integer type (presumably). This assumes
that the result can be manipulated arithmetically, then cast back to a
pointer type[6.3.2.3p5], then the resulting pointer used. That's
probably true for several implementations, but a trap representation is
also a possible result.
You might "statically" assert the presence of 'uintptr_t' and use it,
since it has a few guarantees associated with it. It's still not
guaranteed (as far as I know) that manipulating the integer value
arithmetically has any relationship to alignment or what the
cast-to-pointer will point [in]to.
The bitwise operations are nice.
>
> void*
> xmalloc_aligned(
> size_t header_size,
> size_t object_size,
> size_t align_size
> ){
> size_t total_size;
> unsigned char* tmp;
> unsigned char* header;
> unsigned char* header_ptr;
> unsigned char* object;
>
> align_size = align_size
> ? (size_t)ALIGN_UP(align_size, ALIGN_OF(void*))
> : ALIGN_OF(void*);
>
Aha. Here you use 'ALIGN_UP' with an integer value as 'mp_ptr', so
'ALIGN_UP' is designed for both pointer and integers.
If I read correctly, the 'ALIGN_UP' will yield a 'void *', which you
cast to a 'size_t', above. But earlier on you allowed for a user to
specify a type other than the default 'size_t' as a preferred integer
type for pointer conversion. I see you have no choice here, since
'align_size' is a 'size_t'.
If only this computation didn't have to invoke pointer conversions,
since the macro arguments are integers and the result is an integer. Oh
well.
Each time you use 'ALIGN_OF', you have a "helper" struct without a tag.
Although it's probably pretty unlikely, it seems that an
implementation could choose different padding each time, despite the
same struct definition with the 'char' and the same 'mp_type' member.
> total_size = (size_t)
> ALIGN_UP(
> header_size + sizeof(void*) +
> object_size + ALIGN_OF(void*) + align_size,
> ALIGN_OF(void*)
> );
>
Hopefully the additions of these 'size_t' values don't wrap around. The
caller can always take the blame.
> if (! (header = malloc(total_size))) return NULL;
> tmp = ALIGN_UP(header + header_size, ALIGN_OF(void*));
> object = ALIGN_UP(tmp + sizeof(void*), align_size);
> header_ptr = object - sizeof(void*);
> *((void**)header_ptr) = header;
>
> return object;
> }
>
Does the resulting layout look like this?:
[header_size] | padding | header_ptr | [object_size]
>
> #define xmalloc_aligned_get(mp_object) \
> ((mp_object) \
> ? (*((void**)(((unsigned char*)mp_object) \
> - sizeof(void*)))) \
> : NULL)
>
So one takes a pointer, back-tracks to an immediately preceding 'void
*', then that pointer points to a header. Aha.
>
> #define XMALLOC_ALIGNED(mp_header, mp_object) \
> xmalloc_aligned( \
> sizeof(mp_header), \
> sizeof(mp_object), \
> ALIGN_OF(mp_object) \
> )
>
So the macro user needs to understand that this convenience macro takes
type-names.
>
> void
> xfree_aligned(
> void* object
> ){
> if (! object) return;
> free(xmalloc_aligned_get(object));
> }
>
> typedef void (ref_count_func_dtor) (void*);
>
I'm not sure why function pointer 'typedef's are so popular when one can
'typedef' functions, as you have above. This 'typedef' can serve as a
"safety measure" in that if you declare:
ref_count_func_dtor some_func;
somewhere, the definition had better agree with the declared type. I'm
a bit confused by one of Microsoft's analysis tools which _appears_ (I
could be wrong) to require functions to be declared with function
pointer types prior to their definitions. *boggle*
I believe that parentheses are required in the 'typedef' for function
_pointer_ types, of course. (Heh.)
>
> struct ref_count
> {
> unsigned count;
> ref_count_func_dtor* fp_dtor;
> };
>
> void* ref_count_sys_create(
> size_t object_size,
> size_t align_size,
> ref_count_func_dtor* fp_dtor
> ){
> struct ref_count* self;
> void* const object =
> xmalloc_aligned(sizeof(*self), object_size, align_size);
> if (! object) return NULL;
> self = xmalloc_aligned_get(object);
> self->count = 1;
> self->fp_dtor = fp_dtor;
> return object;
> }
>
Nice and simple.
>
> #define REF_COUNT_CREATE(mp_type, mp_fp_dtor) \
> ref_count_sys_create( \
> sizeof(mp_type), \
> ALIGN_OF(mp_type), \
> (mp_fp_dtor) \
> )
>
>
> #define ref_count_get(mp_object) \
> xmalloc_aligned_get(mp_object)
>
>
> void*
> ref_count_acquire(
> void* state
> ){
> struct ref_count* const self = ref_count_get(state);
> if (! self) return NULL;
> ++self->count;
> return state;
> }
>
Hopefully the reference count doesn't wrap around.
>
> void
> ref_count_release(
> void* state
> ){
> struct ref_count* const self = ref_count_get(state);
> if (! self) return;
> if (--self->count) return;
> if (self->fp_dtor) self->fp_dtor(state);
> free(self);
> }
>
So simple, so nice.
>
> struct foo
> {
> /*__declspec(align(128))*/ double state;
> };
>
>
> void
> foo_ref_count_dtor(
> void* state
> ){
> struct foo* const self = state;
>
> printf("foo_ref_count_dtor::%p - %f\n",
> (void*)self, self->state);
> }
>
Why not use 'state' instead of '(void*)self'? (Not that it matters.)
>
> int main(void)
> {
> struct foo* foo1 =
> REF_COUNT_CREATE(struct foo, foo_ref_count_dtor);
>
> struct foo* foo2;
>
> if (! foo1) return EXIT_FAILURE;
>
> foo1->state = -665;
>
> foo2 = ref_count_acquire(foo1);
>
> foo2->state -= 1;
>
> ref_count_release(foo1);
> ref_count_release(foo2);
>
> return EXIT_SUCCESS;
> }
Pretty nifty. :)
Shao Miller
Nope; you've lost me.
If we take your 'foo' example and do:
foo array[2];
The first element will presumably be properly aligned at some multiple
of 1024, then the next element will start 4 bytes later, which will be
improperly aligned at ((some multiple of 1024) plus 4).
Shao Miller
> luser- -droog wrote:
>> An external table would avoid all the alignment-guessing for pre-C1X.
>> I'm too lazy to finish coding this, but what about a simple open-
>> addressed
>> hash-table?
>
> Laziness overcome!
>
>
> int main(void) {
> ref_init();
> char *s = strdup("apple");
> char *t = strdup("banana");
>
> print(s); /* apple */
> print(t); /* banana */
>
> ref_dec(s);
> print(s); /* */
> print(t); /* banana */
>
> ref_dec(t);
> print(s); /* */
> print(t); /* */
>
> return 0;
> }
>
> #endif
> cc -g -Wall -c -o rfct.o rfct.c
> cc rfct.o -o rfct
> apple
> banana
> banana
> 519(0)10:47 PM:~ 0>
How interesting! You impose no special requirements on the programmers
to use overriding macros or wrapper functions for allocation functions,
you do not touch nor examine the state of the pointed-to objects, yet
your 'ref_dec' invocations behave differently! Pretty nifty.
Shao Miller
> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
> news:4df70a29$0$2690$4faf...@reader1.news.tin.it...
>
> what about my try?
>
I find it a bit crammed and difficult to read, so here's an adaptation
of the code by performing preprocessor expansion, followed by an
'indent' invocation:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
union tipidiarray {
double a;
size_t v;
uint8_t *m;
};
uint32_t elemento = sizeof(union tipidiarray);
uint8_t *IniMem(uint32_t s)
{
uint8_t *p;
uint32_t *pu;
uint32_t c;
if (s == 0)
return 0;
c = s;
c += elemento;
if (c < s)
return 0;
p = malloc(c);
if (p == 0)
return 0;
pu = (uint32_t *) p;
p += elemento;
pu[0] = 1;
pu[1] = (uint32_t) p;
return p;
}
uint8_t *GetRef(uint8_t * v)
{
uint8_t *p;
uint32_t *pu;
if (v == 0)
return 0;
p = v - elemento;
pu = (uint32_t *) p;
if (pu[0] == 0 || pu[1] != (uint32_t) v)
return 0;
++pu[0];
if (pu[0] == 0) {
--pu[0];
return 0;
}
return v;
}
uint32_t GetRefCounter(uint8_t * v)
{
uint8_t *p;
uint32_t *pu;
if (v == 0)
return 0;
p = v - elemento;
pu = (uint32_t *) p;
if (pu[1] != (uint32_t) v)
return (uint32_t) - 1;
return pu[0];
}
uint8_t *PutRef(uint32_t * ris, uint8_t * v)
{
uint8_t *p;
uint32_t *pu;
if (ris == 0 || v == 0)
return 0;
*ris = 0;
p = v - elemento;
pu = (uint32_t *) p;
if (pu[0] == 0 || pu[1] != (uint32_t) v) {
*ris = -1;
return 0;
}
--pu[0];
if (pu[0] == 0) {
pu[1] = 0;
free(p);
}
return 0;
}
int main(void)
{
double *arrd, *pad;
uint32_t *arru, *elm, ris;
if (2 * sizeof(uint32_t) > elemento) {
printf("Errore di inizializzazione\n");
return 0;
}
arrd = (double *)IniMem(10 * sizeof(double));
arrd[0] = 1.111;
pad = (double *)GetRef((uint8_t *) arrd);
if (pad == 0) {
printf("Errore della funzione GetRef()\n");
printf("o memoria insufficiente\n");
exit(0);
}
printf("val=%f nref=%u\n", pad[0],
(unsigned)GetRefCounter((uint8_t *) arrd));
pad = (double *)PutRef(&ris, (uint8_t *) pad);
printf("val=%f nref=%u pad=%p ris=%u\n",
arrd[0], (unsigned)GetRefCounter((uint8_t *) arrd),
(uint8_t *) pad, (unsigned)ris);
arrd = (double *)PutRef(&ris, (uint8_t *) pad);
printf("nref=%u ris=%u\n", (unsigned)GetRefCounter((uint8_t *)
arrd),
(unsigned)ris);
return 0;
}
Ian Collins
> On 6/16/2011 3:35 AM, io_x wrote:
>> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
>> news:4df70a29$0$2690$4faf...@reader1.news.tin.it...
>>
>> what about my try?
>>
>> [...code...]
>
> I find it a bit crammed and difficult to read, so here's an adaptation
> of the code by performing preprocessor expansion, followed by an
> 'indent' invocation:
That's one way to get rid of those stupid macros!
--
Ian Collins
Chris M. Thomasson
[...]
Yikes! Let me try to clarify: I was thinking in terms of an array of `struct
object' in which the beginning of said array is aligned on a boundary that
is greater than `sizeof(struct object)'. Imagine an array of N 128-byte
objects that simply has to be aligned on a 4096-byte boundary. Please excuse
any confusions I have caused!
;^(...
io_x
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
u32 ele(void)
{double dbt[2];
size_t szt[2];
u8* art[2], *a, *b;
long unsigned lut[2];
u32 r, v;
a=&dbt[0]; b=&dbt[1];
r=b-a;
a=&szt[0]; b=&szt[1];
if(b-a>r) r=b-a;
a=&art[0]; b=&art[1];
if(b-a>r) r=b-a;
a=&lut[0]; b=&lut[1];
if(b-a>r) r=b-a;
R r;
}
union tipidiarray{
double a;
size_t v;
u8* m;
};
u32 elemento;
elemento=ele();
P("Elemento=%u\n", elemento);
io_x
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
/*
??????????????
serve per trovare il prossimo elemento
allocato da malloc con allineamento
buono per tutti i tipi possibili nella
macchina in cui gira ma tale che l'allineamento
sia del tipo: + (0, 1, 2, 4, 8, 16, 32, 64..)
*/
u32 ele(void)
{long double ldbt[2];
double dbt[2];
size_t szt[2];
u8* art[2], *a, *b;
long unsigned lut[2];
u32 r, v;
r=0;
a=&ldbt[0]; b=&ldbt[1];
v=b-a;
// 100b-1b=11
if(((v-1)&v)==0 && v>r) r=v;
a=&dbt[0]; b=&dbt[1];
v=b-a;
// 100b-1b=11
if(((v-1)&v)==0 && v>r) r=v;
a=&szt[0]; b=&szt[1];
v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
a=&art[0]; b=&art[1];
v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
a=&lut[0]; b=&lut[1];
v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
R r;
}
union tipidiarray{
double a;
size_t v;
u8* m;
};
u32 elemento;
elemento=ele();
P("Elemento=%u\n", elemento);
Keith Thompson
[...]
> // macro for types
> #define u64 uint64_t
> #define u32 uint32_t
> #define u16 uint16_t
> #define u8 uint8_t
> #define uns unsigned
> #define dbl double
>
> // macro for function
> #define P printf
>
> // macro for keyWords
> #define G goto
> #define R return
> #define W while
> #define F for
No.
Tim Rentsch
> My impression is that the idea of representation applies only to
> objects. The representation of a value not stored in an object is
> irrelevant until and unless it's stored in an object.
Let me offer a counter-example, which is floating-point values.
In several places the Standard talks about floating-point operands
being represented with a greater range or precision than that of
the type (of the expression that would produce the operand value).
Certainly these operand values exist and have some representation
in an actual computer, but those representations aren't the same as
the operand's expression's type's object representation -- indeed,
the representation of a floating-point operand value may be different
than the object representation of any C floating-point type.
A similar description could hold for a (hypothetical) machine that
had only one kind of signed integer register, let's say 128 bits,
with all signed arithmetic being done using these big registers
(and with some way of storing part of a big register into a narrower
non-register memory location). The register representation could
easily be different than the object representation of any C
signed integer type. The representation of signed integer values
would be unspecified, only the representations of signed integers
stored in objects would be implementation-defined.
> I think your idea makes some sense, but I don't think it's what
> 6.2.6.1 is referring to.
I don't mean to advocate that it is, only that it might be (and
that I can't yet think of any better possibility).
> I have no particular support for this.
The word representation (in various forms) is used in quite
a few places in the Standard, applying to lots of different
circumstances. If 6.2.6.1p1 isn't referring to things like
floating-point operands (ie, representations other than those
in objects), what is it talking about?
Tim Rentsch
> On Tuesday, June 14, 2011 6:00:21 PM UTC-4, Tim Rentsch wrote:
>> James Kuyper <james...@verizon.net> writes:
>>
>> > On 06/10/2011 02:30 PM, ImpalerCore wrote:
> ...
>> >> #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'. [snip]
>>
>> Unless one considers the type 'unsigned int' to be a type
>> different from that of 'int'.
>
> I was talking about types "with a size ... that is different from that
> of 'int'". 'unsigned int' is a type with a size that is guaranteed to
> be the same as that of 'int', so that type is just as safe as 'int'
> itself.
I see - the unspecified referent of the final "that" allowed
the earlier statement to be read ambiguously.
But the assertion about size isn't right either. The pointer
value in 'mem' is suitably aligned for any type whose size
evenly divides 'sizeof (int)', or for that matter any type
whose alignment evenly divides 'sizeof (int)'. The second
condition is conservatively testable (no false positives,
only potentially false negatives), and the first is exactly
testable, using completely portable code.
Shao Miller
> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
> news:4df9caab$0$40251$4faf...@reader1.news.tin.it...
>>
>> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
>> news:4df9c004$0$40246$4faf...@reader1.news.tin.it...
>>>
>>> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
>>> news:4df70a29$0$2690$4faf...@reader1.news.tin.it...
>>>
>>> what about my try?
>>
>> someone think there are too many cast?
>> what about consider for align
>> union tipidiarray{
>> double a;
>> size_t v;
>> u8* m;
>> };
>> and think are possible array of each element of that union?
>> so if "a" is aligned to double, size_t, u8*
>> "a"+sizeof(double), "a"+sizeof(size_t)
>> "a"+sizeof(u8*) has to be aligned to each rispettive type
>> and so if "a" is a return address of malloc
>> "a"+sizeof(tipidiarray)
>> is ok for double, size_t, u8*
>> [if "a" point to sufficient memory]
>
On 6/19/2011 1:01 PM, io_x could have written:
> #include <stdio.h>
> #include <stdlib.h>
> #include <stdint.h>
>
> uint32_t ele(void)
> {
> long double ldbt[2];
> double dbt[2];
> size_t szt[2];
> uint8_t *art[2], *a, *b;
> long unsigned lut[2];
> uint32_t r, v;
>
> r = 0;
> a = &ldbt[0];
> b = &ldbt[1];
> v = b - a;
> #if 0
> 100b-1b=11
> #endif
> if (((v - 1) & v) == 0 && v > r)
> r = v;
>
> a = &dbt[0];
> b = &dbt[1];
> v = b - a;
> #if 0
> 100b-1b=11
> #endif
> if (((v - 1) & v) == 0 && v > r)
> r = v;
>
> a = &szt[0];
> b = &szt[1];
> v = b - a;
> if (((v - 1) & v) == 0 && v > r)
> r = v;
>
> a = &art[0];
> b = &art[1];
> v = b - a;
> if (((v - 1) & v) == 0 && v > r)
> r = v;
>
> a = &lut[0];
> b = &lut[1];
> v = b - a;
> if (((v - 1) & v) == 0 && v > r)
> r = v;
>
> return r;
> }
>
> union tipidiarray {
> double a;
> size_t v;
> uint8_t *m;
> };
>
> uint32_t elemento;
>
> uint8_t *IniMem(uint32_t s)
> {
> uint8_t *p;
> uint32_t *pu;
> uint32_t c;
>
> if (s == 0)
> return 0;
> c = s;
> c += elemento;
> if (c <= s)
> if (ris == 0)
> return 0;
> *ris = 0;
> if (v == 0)
> return 0;
> p = v - elemento;
> pu = (uint32_t *) p;
> if (pu[0] == 0 || pu[1] != (uint32_t) v) {
> *ris = -1;
> return 0;
> }
> --pu[0];
> if (pu[0] == 0) {
> pu[1] = 0;
> free(p);
> }
> return 0;
> }
>
> int main(void)
> {
> double *arrd, *pad;
> uint32_t *arru, *elm, ris;
>
> elemento = ele();
> printf("Elemento=%u\n", elemento);
> if (2 * sizeof(uint32_t) > elemento) {
> printf("Errore di inizializzazione\n");
> return 0;
> }
> arrd = (double *)IniMem(10 * sizeof(double));
> arrd[0] = 1.111;
> pad = (double *)GetRef((uint8_t *) arrd);
> if (pad == 0) {
> printf("Errore della funzione GetRef()\n");
> printf("o memoria insufficiente\n");
> exit(0);
> }
> printf("val=%f nref=%u\n", pad[0],
> (unsigned)GetRefCounter((uint8_t *) arrd));
> pad = (double *)PutRef(&ris, (uint8_t *) pad);
> printf("val=%f nref=%u pad=%p ris=%u\n",
> arrd[0], (unsigned)GetRefCounter((uint8_t *) arrd),
> (uint8_t *) pad, (unsigned)ris);
>
> arrd = (double *)PutRef(&ris, (uint8_t *) pad);
> printf("nref=%u ris=%u\n", (unsigned)GetRefCounter((uint8_t *) arrd),
> (unsigned)ris);
> return 0;
> }
GCC gave:
io_x2.c: In function 'ele':
io_x2.c:15: warning: assignment from incompatible pointer type
io_x2.c:16: warning: assignment from incompatible pointer type
io_x2.c:24: warning: assignment from incompatible pointer type
io_x2.c:25: warning: assignment from incompatible pointer type
io_x2.c:33: warning: assignment from incompatible pointer type
io_x2.c:34: warning: assignment from incompatible pointer type
io_x2.c:39: warning: assignment from incompatible pointer type
io_x2.c:40: warning: assignment from incompatible pointer type
io_x2.c:45: warning: assignment from incompatible pointer type
io_x2.c:46: warning: assignment from incompatible pointer type
io_x
"Shao Miller" <sha0....@gmail.com> ha scritto nel messaggio
news:itme0r$h0m$1...@dont-email.me...
> On 6/19/2011 1:01 PM, io_x wrote:
>> "io_x"<a...@b.c.invalid> ha scritto nel messaggio
>> news:4df9caab$0$40251$4faf...@reader1.news.tin.it...
all these below warning should be for the function ele();
where is the problem in access data
using unsigned char pointers?
the only problem that came in mind is if
uint8_t!=unsigned char
and uint8_t* has incompatible reppresentation
with unsigned char
what about the use of cast?
uint32_t ele(void)
{long double ldbt[2];
double dbt[2];
size_t szt[2];
uint8_t art[2], *a, *b;
long unsigned lut[2];
uint32_t r, v;
r=0;
a=(uint8_t*)ldbt; b=(uint8_t*)(ldbt+1); v=b-a;
/* 100b-1b=11 */
if(((v-1)&v)==0 && v>r) r=v;
a=(uint8_t*)dbt; b=(uint8_t*)(dbt +1); v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
a=(uint8_t*)szt; b=(uint8_t*)(szt +1); v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
a=(uint8_t*)art; b=(uint8_t*)(art +1); v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
a=(uint8_t*)lut; b=(uint8_t*)(lut +1); v=b-a;
if(((v-1)&v)==0 && v>r) r=v;
return r;