Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Shao Miller <sha0.miller@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Reference counting |
| Date | 2011-06-15 02:16 -0500 |
| Organization | A noiseless patient Spider |
| Message-ID | <it9io3$jsv$1@dont-email.me> (permalink) |
| References | (5 earlier) <d6d7b471-ee68-443e-8592-c56e3555bef9@e26g2000vbz.googlegroups.com> <it5kok$m5o$1@dont-email.me> <a290e025-ebf8-48cc-af63-55188e70d090@a10g2000vbz.googlegroups.com> <it5vnd$4qo$1@dont-email.me> <ef5a24b9-9442-456f-b46b-72fb072775f9@hg8g2000vbb.googlegroups.com> |
On 6/14/2011 2:14 PM, ImpalerCore wrote:
> 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:
http://codepad.org/0R6QzND9
-----
/**
* 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;
}
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Reference counting daknok <radekslupik@gmail.com> - 2011-06-05 12:52 +0200
Re: Reference counting Angel <angel+news@spamcop.net> - 2011-06-05 11:17 +0000
Re: Reference counting Gene <gene.ressler@gmail.com> - 2011-06-06 20:07 -0700
Multiple Inheritance (Was Re: Reference counting) Shao Miller <sha0.miller@gmail.com> - 2011-06-11 03:57 -0500
Re: Multiple Inheritance (Was Re: Reference counting) Dr Nick <3-nospam@temporary-address.org.uk> - 2011-06-12 07:22 +0100
Re: Reference counting China Blue Angels <chine.bleu@yahoo.com> - 2011-06-05 05:07 -0700
Re: Reference counting "BartC" <bc@freeuk.com> - 2011-06-05 13:14 +0100
Re: Reference counting daknok <daknok@example.com> - 2011-06-05 14:22 +0200
Re: Reference counting "BartC" <bc@freeuk.com> - 2011-06-05 14:45 +0100
Re: Reference counting daknok <daknok@example.com> - 2011-06-05 17:01 +0200
Re: Reference counting Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-05 18:06 -0400
Re: Reference counting Dr Nick <3-nospam@temporary-address.org.uk> - 2011-06-12 07:25 +0100
Re: Reference counting daknok <daknok@example.com> - 2011-06-05 15:29 +0200
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-05 12:17 -0500
Re: Reference counting cri@tiac.net (Richard Harter) - 2011-06-05 17:11 +0000
Re: Reference counting ImpalerCore <jadill33@gmail.com> - 2011-06-10 11:30 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-10 16:04 -0400
Re: Reference counting James Kuyper <jameskuyper@verizon.net> - 2011-06-10 22:56 -0400
Re: Reference counting ImpalerCore <jadill33@gmail.com> - 2011-06-11 12:36 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-11 17:23 -0500
Re: Reference counting luser- -droog <mijoryx@yahoo.com> - 2011-06-12 15:15 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-12 21:13 -0500
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-13 12:37 -0700
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-13 12:54 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-13 16:40 -0500
Re: Reference counting ImpalerCore <jadill33@gmail.com> - 2011-06-13 07:34 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-13 14:26 -0500
Re: Reference counting ImpalerCore <jadill33@gmail.com> - 2011-06-13 12:47 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-13 17:33 -0500
Re: Reference counting ImpalerCore <jadill33@gmail.com> - 2011-06-14 12:14 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-15 02:16 -0500
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-15 15:34 -0700
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-15 15:42 -0700
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 13:45 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-16 17:02 -0500
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 15:18 -0700
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 16:01 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-16 18:44 -0500
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 17:11 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-16 18:39 -0500
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-11 16:51 -0700
Re: Reference counting "Chris M. Thomasson" <cristom@charter.net> - 2011-06-11 18:28 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-12 16:10 -0500
Re: Reference counting ImpalerCore <jadill33@gmail.com> - 2011-06-13 07:36 -0700
Re: Reference counting Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-14 15:00 -0700
Re: Reference counting luser- -droog <mijoryx@yahoo.com> - 2011-06-13 21:46 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-14 03:19 -0500
Re: Reference counting Angel <angel+news@spamcop.net> - 2011-06-14 07:31 +0000
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-14 05:02 -0500
Re: Reference counting Keith Thompson <kst-u@mib.org> - 2011-06-14 09:03 -0700
Re: Reference counting luser- -droog <mijoryx@yahoo.com> - 2011-06-14 10:23 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-14 13:46 -0500
Re: Reference counting Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-14 15:05 -0700
Re: Reference counting Keith Thompson <kst-u@mib.org> - 2011-06-14 16:44 -0700
Re: Reference counting Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-15 06:54 -0700
Re: Reference counting Keith Thompson <kst-u@mib.org> - 2011-06-15 08:46 -0700
Re: Reference counting pete <pfiland@mindspring.com> - 2011-06-15 22:19 -0400
Re: Reference counting James Kuyper <jameskuyper@verizon.net> - 2011-06-15 23:03 -0400
Re: Reference counting Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-19 14:48 -0700
Re: Reference counting Seebs <usenet-nospam@seebs.net> - 2011-06-14 17:16 +0000
Re: Reference counting luser- -droog <mijoryx@yahoo.com> - 2011-06-14 20:53 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-16 18:49 -0500
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-14 08:30 +0200
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-14 09:15 +0200
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-14 04:21 -0500
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-16 10:35 +0200
Re: Reference counting Ian Collins <ian-news@hotmail.com> - 2011-06-16 20:36 +1200
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-16 11:21 +0200
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-19 17:57 +0200
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-19 20:01 +0200
Re: Reference counting Keith Thompson <kst-u@mib.org> - 2011-06-19 11:07 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-19 23:15 -0500
Re: Reference counting "io_x" <a@b.c.invalid> - 2011-06-20 08:21 +0200
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-16 19:05 -0500
Re: Reference counting Ian Collins <ian-news@hotmail.com> - 2011-06-17 12:09 +1200
Re: Reference counting luser- -droog <mijoryx@yahoo.com> - 2011-06-15 08:40 -0700
Re: Reference counting "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-06-16 11:08 -0700
Re: Reference counting Shao Miller <sha0.miller@gmail.com> - 2011-06-16 14:42 -0400
csiph-web