wrt my conservative static region allocator...
Chris M. Thomasson
I was wondering if anybody has been using it, or even finds it useful for
that matter? Do you have any suggestions on how to improve it?
I think I should go ahead and remove all of the `RALLOC_DBG_PRINTF' stuff.
Not sure if it needs to be in there. Its more of a sanity check.
Thank you.
blargg
> Here is the code all wrapped up in a header to make it easier to use:
>
> http://pastebin.com/f37a23918
First off, you should document what the hell this does, and the part of
the header defining the interface. I get the vague idea it allocates space
within a block provided by the user...
For you "align pointer to next multiple of mp_align" macro,
#define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
((void*)( \
(((ralloc_uintptr_type)(mp_ptr)) + ((mp_align) - 1)) \
& ~(((mp_align) - 1)) \
))
why not write this as the following?
#define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
((void*)((char*)(mp_ptr)+(-(ralloc_uintptr_type)(mp_ptr))%(mp_align_)))
That is, calculate the alignment offset and add that to mp_ptr as a char*,
rather than directly manipulating the bits of the pointer. This follows
the principle of using read-only access to low-level details when
possible.
Chris M. Thomasson
news:blargg.ei3-29...@192.168.1.4...
> "Chris M. Thomasson" wrote:
>> Here is the code all wrapped up in a header to make it easier to use:
>>
>> http://pastebin.com/f37a23918
>
> First off, you should document what the hell this does
Yikes! I forgot to post the original thread:
http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195
> , and the part of the header defining the interface.
Okay. Will do.
> I get the vague idea it allocates space within a block provided by the
> user...
Right. It can allocate any C type within a user provided block and maintain
alignment specific to said type. It does not waste any alignment space when
allocating, say a `char'. AFAICT, its great for space constrained
environments.
> For you "align pointer to next multiple of mp_align" macro,
>
> #define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
> ((void*)( \
> (((ralloc_uintptr_type)(mp_ptr)) + ((mp_align) - 1)) \
> & ~(((mp_align) - 1)) \
> ))
>
> why not write this as the following?
>
> #define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
> ((void*)((char*)(mp_ptr)+(-(ralloc_uintptr_type)(mp_ptr))%(mp_align_)))
>
> That is, calculate the alignment offset and add that to mp_ptr as a char*,
> rather than directly manipulating the bits of the pointer. This follows
> the principle of using read-only access to low-level details when
> possible.
Well, I do think that would be better. As for why I did it the first way,
well I don't really know. I guess I thought the modulo operator was too
expensive or something retarded like that. Also, many versions of MSVC barf
up a warning:
"unary minus operator applied to unsigned type, result still unsigned"
I will just turn off the warning. Anyway, here is some updated code that has
VERY crude documentation, and also uses your alignment macro:
Thanks for all your comments blargg! I really do appreciate them.
blargg
> blargg wrote:
> > "Chris M. Thomasson" wrote:
> >> Here is the code all wrapped up in a header to make it easier to use:
> >>
> >> http://pastebin.com/f37a23918
> http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195
[...]
> > why not write this as the following?
> >
> > #define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
> [...] I guess I thought the modulo operator was too
> expensive or something retarded like that.
Modulo by a power of two on an unsigned value should generate a mask
operation on any halfway decent compiler. Modulo isn't necessary anyway;
it just simplifies the expression. Note that this won't align properly for
a non-power-of-two; for that, you'd need something like
((void*)((char*)(mp_ptr)+\
((mp_align_)-(ralloc_uintptr_type)(mp_ptr)%(mp_align))%(mp_align)
))
so that you get an offset of 0 if it's already aligned, or a value up to
mp_align-1 if it's not.
> Also, many versions of MSVC barf
> up a warning:
>
> "unary minus operator applied to unsigned type, result still unsigned"
Interesting. You could always just subtract it from zero; should generate
the same code.
> Anyway, here is some updated code that has
> VERY crude documentation, and also uses your alignment macro:
>
> http://pastebin.com/f1bf99c25
Hmmm, instead of your custom RALLOC_UINTPTR_TYPE type, you could just use
uintptr_t from C99's <stdint.h>. Your use of size_t as a fallback for C89
is a good idea.
Your assertion could cause problems, as you're casting an arbitrary
integer to a void*:
#define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
((void*)((unsigned char*)(mp_ptr)+ \
(-(ralloc_uintptr_type)(mp_ptr))%(mp_align)))
#define RALLOC_ALIGN_ASSERT(mp_ptr, mp_align) \
(((void*)(mp_ptr)) == RALLOC_ALIGN_UP(mp_ptr, mp_align))
[...]
static void*
rallocex(
struct region* const self,
size_t size,
size_t align
) {
[...]
assert(align == 1 || RALLOC_ALIGN_ASSERT(align, 2));
Here you're casting align to a void* within the assertion.
Another issue, inside rallocex(), you align the buffer pointer BEFORE
verifying there's enough space to even align it:
align_buffer = RALLOC_ALIGN_UP(raw_buffer, align);
size += align_buffer - raw_buffer;
if (offset + size > self->size)
return NULL;
Even just incrementing a pointer outside the array/one past the end it
points into is undefined behavior.
It seems a lot of machinery for really simple functionality. I tried
coding up a minimal function to do mostly the same thing:
void* ralloc( size_t size, size_t align, char** pos, char* end )
{
void* result = NULL;
size_t pad = (align - ((uintptr_t)*pos % align)) % align;
size_t padded_size = size + pad;
if ( end - *pos >= padded_size )
{
result = *pos + pad;
*pos += padded_size;
}
return result;
}
/* Example usage with static buffer */
static char buf [100];
static char* pos = buf;
void init_buf( void )
{
pos = buf;
}
void* alloc_from_buf( size_t size, size_t align )
{
return ralloc( size, align, &pos, buf + sizeof buf );
}
The core ralloc() function first finds how much padding is necessary to
align *pos, calculates an adjusted size that includes padding, then
verifies that enough space remains in the buffer. If so, it returns the
aligned beginning and adjusts the buffer pointer to just past the end.
User code then allocates the buffer and keeps a pointer to the next
position in it.
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> blargg wrote:
>> > "Chris M. Thomasson" wrote:
>> >> Here is the code all wrapped up in a header to make it easier to use:
>> >>
>> >> http://pastebin.com/f37a23918
> [...]
>> http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195
> [...]
>> > why not write this as the following?
>> >
>> > #define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
>> >
>> > ((void*)((char*)(mp_ptr)+(-(ralloc_uintptr_type)(mp_ptr))%(mp_align)))
>> [...] I guess I thought the modulo operator was too
>> expensive or something retarded like that.
>
> Modulo by a power of two on an unsigned value should generate a mask
> operation on any halfway decent compiler.
Humm. I really need to disassemble some programs to see what's going on with
most of the compilers I use. Modulo is slow when compared to a simple and
operation.
> Modulo isn't necessary anyway;
> it just simplifies the expression. Note that this won't align properly for
> a non-power-of-two; for that, you'd need something like
>
> ((void*)((char*)(mp_ptr)+\
> ((mp_align_)-(ralloc_uintptr_type)(mp_ptr)%(mp_align))%(mp_align)
> ))
>
> so that you get an offset of 0 if it's already aligned, or a value up to
> mp_align-1 if it's not.
Good point. Perhaps I should allow support for alignments for values that
are not powers of two. Humm... Need to think.
>> Also, many versions of MSVC barf
>> up a warning:
>>
>> "unary minus operator applied to unsigned type, result still unsigned"
>
> Interesting. You could always just subtract it from zero; should generate
> the same code.
:^)
>> Anyway, here is some updated code that has
>> VERY crude documentation, and also uses your alignment macro:
>>
>> http://pastebin.com/f1bf99c25
>
> Hmmm, instead of your custom RALLOC_UINTPTR_TYPE type, you could just use
> uintptr_t from C99's <stdint.h>. Your use of size_t as a fallback for C89
> is a good idea.
I was under the impression that `uintptr_t' was optional in C99 (e.g., only
exists in an XSI conformant system). I guess I could just check to see if
the compilation environment is C99; include <stdint.h> and finally check if
the `UINTPTR_MAX' macro is defined. Probably something along the lines of:
___________________________________________________________
#if (__STDC_VERSION__ >= 199901L)
# include <stdint.h>
# if defined (UINTPTR_MAX)
# undef RALLOC_UINTPTR_TYPE
# define RALLOC_UINTPTR_TYPE uintptr_t
# endif
#endif
#if ! defined (RALLOC_UINTPTR_TYPE)
# define RALLOC_UINTPTR_TYPE size_t
#endif
___________________________________________________________
> Your assertion could cause problems, as you're casting an arbitrary
> integer to a void*:
>
> #define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
> ((void*)((unsigned char*)(mp_ptr)+ \
> (-(ralloc_uintptr_type)(mp_ptr))%(mp_align)))
>
> #define RALLOC_ALIGN_ASSERT(mp_ptr, mp_align) \
> (((void*)(mp_ptr)) == RALLOC_ALIGN_UP(mp_ptr, mp_align))
>
> [...]
>
> static void*
> rallocex(
> struct region* const self,
> size_t size,
> size_t align
> ) {
>
> [...]
> assert(align == 1 || RALLOC_ALIGN_ASSERT(align, 2));
>
> Here you're casting align to a void* within the assertion.
I should just define the `RALLOC_ALIGN_ASSERT()' function macro to something
like:
#define RALLOC_ALIGN_ASSERT(mp_ptr, mp_align) ( \
! (((ralloc_uintptr_type)(mp_ptr)) % (mp_align)) \
)
> Another issue, inside rallocex(), you align the buffer pointer BEFORE
> verifying there's enough space to even align it:
>
> align_buffer = RALLOC_ALIGN_UP(raw_buffer, align);
> size += align_buffer - raw_buffer;
> if (offset + size > self->size)
> return NULL;
>
> Even just incrementing a pointer outside the array/one past the end it
> points into is undefined behavior.
Oh shi%. I thought that it if was okay to increment a pointer to one past
the end, it should be okay to increment some more... So, the following
program could theoretically reboot the machine or launch the nukes:
___________________________________________________________
int main(void) {
char x[1];
char* boom = x;
++boom;
++boom;
++boom;
return 0;
}
___________________________________________________________
> It seems a lot of machinery for really simple functionality. I tried
> coding up a minimal function to do mostly the same thing:
>
> void* ralloc( size_t size, size_t align, char** pos, char* end )
> {
> void* result = NULL;
>
> size_t pad = (align - ((uintptr_t)*pos % align)) % align;
> size_t padded_size = size + pad;
>
> if ( end - *pos >= padded_size )
> {
> result = *pos + pad;
> *pos += padded_size;
> }
> return result;
> }
>
> /* Example usage with static buffer */
> static char buf [100];
> static char* pos = buf;
>
> void init_buf( void )
> {
> pos = buf;
> }
>
> void* alloc_from_buf( size_t size, size_t align )
> {
> return ralloc( size, align, &pos, buf + sizeof buf );
> }
Well, at first glance it should work. I would just have to augment it with
the nifty `RALLOC_ALIGN_OF()' function macro in order to automatically
determine alignments for any type.
> The core ralloc() function first finds how much padding is necessary to
> align *pos, calculates an adjusted size that includes padding, then
> verifies that enough space remains in the buffer. If so, it returns the
> aligned beginning and adjusts the buffer pointer to just past the end.
> User code then allocates the buffer and keeps a pointer to the next
> position in it.
Sounds like a plan.
Thank you. I will try to amend the code and re-post it sometime today or
tomorrow.
Chris M. Thomasson
> [...]
Perhaps something like:
_____________________________________________________________________
#define RALLOC_ALIGN_PAD(mp_ptr, mp_align) \
(((((ralloc_uintptr_type)(mp_ptr)) + \
((mp_align) - 1)) & ~(((mp_align) - 1))) - \
(ralloc_uintptr_type)(mp_ptr))
#define RALLOC_ALIGN_ASSERT(mp_ptr, mp_align) \
(! (((ralloc_uintptr_type)(mp_ptr)) % (mp_align)))
static void*
rallocex(
struct region* const self,
size_t size,
size_t align
) {
size_t pad;
unsigned char* raw_buffer = self->buffer + self->offset;
assert(align == 1 || RALLOC_ALIGN_ASSERT(align, 2));
pad = RALLOC_ALIGN_PAD(raw_buffer, align);
if (self->offset + size + pad <= self->size) {
unsigned char* align_buffer = raw_buffer + pad;
assert(RALLOC_ALIGN_ASSERT(align_buffer, align));
self->offset += size + pad;
return align_buffer;
}
return NULL;
}
_____________________________________________________________________
That gets around the incrementing the pointer beyond array limits issue.
blargg
> blargg wrote:
> > Chris M. Thomasson wrote:
> >> blargg wrote:
> >> > "Chris M. Thomasson" wrote:
> >> >> Here is the code all wrapped up in a header to make it easier to use:
> >> >>
> >> >> http://pastebin.com/f37a23918
> > [...]
> >> http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f201
> >> 95
> > [...]
> >> > why not write this as the following?
> >> >
> >> > #define RALLOC_ALIGN_UP(mp_ptr, mp_align) \
> >> >
> >> > ((void*)((char*)(mp_ptr)+(-(ralloc_uintptr_type)(mp_ptr))%(mp_align)))
> >> [...] I guess I thought the modulo operator was too
> >> expensive or something retarded like that.
> >
> > Modulo by a power of two on an unsigned value should generate a mask
> > operation on any halfway decent compiler.
By a power of two KNOWN AT COMPILE TIME, I mean!
> Humm. I really need to disassemble some programs to see what's going on with
> most of the compilers I use. Modulo is slow when compared to a simple and
> operation.
Argh, I'm an idiot; for some reason I was thinking the alignment value
was a compile-time constant. Of course it's going to use a divide, since
it doesn't know it's a power of two. Sorry for the wild goose chase!
blargg
> "blargg" <blarg...@gishpuppy.com> wrote in message
> news:blargg.ei3-30...@192.168.1.4...
> > [...]
> > ((void*)((unsigned char*)(mp_ptr)+ \
> > (-(ralloc_uintptr_type)(mp_ptr))%(mp_align)))
> > Another issue, inside rallocex(), you align the buffer pointer BEFORE
> > verifying there's enough space to even align it:
> >
> > align_buffer = RALLOC_ALIGN_UP(raw_buffer, align);
> > size += align_buffer - raw_buffer;
> > if (offset + size > self->size)
> > return NULL;
> >
> > Even just incrementing a pointer outside the array/one past the end it
> > points into is undefined behavior.
>
> Perhaps something like:
> That gets around the incrementing the pointer beyond array limits issue.
The 7-line self-contained ralloc() I posted yesterday avoids this as
well. It first calculates the padding needed, then ensures there's
enough free space BEFORE incrementing the pointer.
Chris M. Thomasson
Na, you are REALLY extremely far from that nasty term... Perhaps you
would
die trying to reach that low point... AFAICT, you are a helpful
individual
indeed; bless you Sir, and thank you for your VERY valuable time! And,
well,
modulo all the juvenile trolling, this group is an asset to anybody
who
wants to learn more about C. Indeed, we are both conversing here on
an
intellectual, and helpful level; well, that says a lot about what can
happen... IMVHO at least.
;^)
> ; for some reason I was thinking the alignment value
> was a compile-time constant. Of course it's going to use a divide, since
> it doesn't know it's a power of two. Sorry for the wild goose chase!
No problem in any way, shape or from. In my case, the most useful
macro
function will be `ralloct()' which in turn utilizes the
`RALLOC_ALIGN_OF()'
function macro, which IS indeed rendered into a compile-time
constant.
However, the darn compiler might have to possibly generate more than
one
implementation of the function `rallocex()' in order to compensate for
each
KNOWN power of two. Function pointers might get the short end of the
stick...
;^(
Chris M. Thomasson
Charter... Whose news server is at
`news/nntp.charter.net'
Cuts me off every 2-3 days and was doing its thing...
I live up in the high sierra beautiful South Lake Tahoe and the only land
based service we have up here is Charter. They SUCK wrt USENET!!!! Morons at
best!!!
Their service reps do not even seem to know their news service exists!!!
Punks!
Chris M. Thomasson
Exactly; and thank you for all your information. The only thing I can think
of which makes me "want" to use the AND operator is that is not as expensive
_and_ I seem to have a fetish with it; YIKES!
;^(...
blargg
> blargg wrote:
> > Hmmm, instead of your custom RALLOC_UINTPTR_TYPE type, you could just use
> > uintptr_t from C99's <stdint.h>. Your use of size_t as a fallback for C89
> > is a good idea.
>
> I was under the impression that `uintptr_t' was optional in C99
Ahhh, you are correct, but if an implementation didn't have uintptr_t,
presumably there IS no integral type that can represent a pointer. Of
course, all you need is one that that can represent the low bits of it,
but I've seen compilers (like gcc) reject code which casted a pointer to
an unsigned short, even though such truncation would not be a problem for
the code, thus a compiler might reject all attempts to cast to an integral
type when there is no uintptr_t typedef...
[...]
> something along the lines of:
> ___________________________________________________________
> #if (__STDC_VERSION__ >= 199901L)
> # include <stdint.h>
> # if defined (UINTPTR_MAX)
> # undef RALLOC_UINTPTR_TYPE
> # define RALLOC_UINTPTR_TYPE uintptr_t
> # endif
> #endif
Yeah, that's what I'd do.
[...]
> > Even just incrementing a pointer outside the array/one past the end it
> > points into is undefined behavior.
>
> Oh shi%. I thought that it if was okay to increment a pointer to one past
> the end, it should be okay to increment some more...
Yeah, the only special case is for one-past-the-end, due to its usefulness
when iterating over the elements. As an aside, this property even holds
for individual (non-array) objects:
int i;
int* p = &i;
++p; // legal
assert( p == &i + 1 ); // legal
*p; // undefined behavior
Keith Thompson
> Chris M. Thomasson wrote:
>> blargg wrote:
> [...]
>> > Hmmm, instead of your custom RALLOC_UINTPTR_TYPE type, you could just use
>> > uintptr_t from C99's <stdint.h>. Your use of size_t as a fallback for C89
>> > is a good idea.
>>
>> I was under the impression that `uintptr_t' was optional in C99
>
> Ahhh, you are correct, but if an implementation didn't have uintptr_t,
> presumably there IS no integral type that can represent a pointer. Of
> course, all you need is one that that can represent the low bits of it,
> but I've seen compilers (like gcc) reject code which casted a pointer to
> an unsigned short, even though such truncation would not be a problem for
> the code, thus a compiler might reject all attempts to cast to an integral
> type when there is no uintptr_t typedef...
[...]
Really? Converting a pointer to short doesn't violate any constraint,
so rejecting such a conversion would be non-conforming (unless, I
suppose, the compiler can prove that the behavior is undefined, but
that doesn't seem like gcc's style). And a quick experiment shows
that gcc merely issues a warning for a conversion from void* to
unsigned short.
Do you have an example?
--
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"
blargg
> blarg...@gishpuppy.com (blargg) writes:
[...]
> > all you need is one that that can represent the low bits of [a pointer],
> > but I've seen compilers (like gcc) reject code which casted a pointer to
> > an unsigned short, even though such truncation would not be a problem for
> > the code, thus a compiler might reject all attempts to cast to an integral
> > type when there is no uintptr_t typedef...
> [...]
>
> Really? Converting a pointer to short doesn't violate any constraint,
> so rejecting such a conversion would be non-conforming (unless, I
> suppose, the compiler can prove that the behavior is undefined, but
> that doesn't seem like gcc's style). And a quick experiment shows
> that gcc merely issues a warning for a conversion from void* to
> unsigned short.
Sorry, maybe it was just a warning (and it was instead that users of said
code would demand it compile without warnings on gcc).
Since you say it's not a constraint violation, that gives more support to
my approach for aligning by calculating the UNalignment rather than
manipulating the pointer's representation directly. This means one could
use unsigned short (for example), even though on most machines it can't
hold the entire pointer. It makes it compatible with C89, without any mess
like Chris M. Thomasson was laying out:
size_t unalignment = (size_t) pointer % align;
if ( unalignment > 0 )
pointer = (char*) pointer + (align - unalignment);
James Kuyper
>> an unsigned short, even though such truncation would not be a problem for
>> the code, thus a compiler might reject all attempts to cast to an integral
>> type when there is no uintptr_t typedef...
> [...]
>
> Really? Converting a pointer to short doesn't violate any constraint,
> so rejecting such a conversion would be non-conforming (unless, I
> suppose, the compiler can prove that the behavior is undefined, but
> that doesn't seem like gcc's style). And a quick experiment shows
> that gcc merely issues a warning for a conversion from void* to
> unsigned short.
The standard says that "Except as previously specified, the result is
implementation-defined. If the result cannot be represented in the
integer type, the behavior is undefined. The result need not be in the
range of values of any integer type." (6.3.2.3p6)
I think that gcc would be well within it's rights to declare that the
result is too big to fit in an unsigned short, which permits anything,
including rejecting the code.
Keith Thompson
I've worked on systems where that wouldn't work, though the compiler
wouldn't necessarily complain about it. Converting a pointer to
size_t would simply copy or reinterpret the bits, but the
representation of a pointer to anything smaller than 64 bits was such
that the result wouldn't be directly meaningful. Machine addresses
pointed to 64-bit words; for a byte pointer (CHAR_BIT==8), an offset
within the word was stored in the high-order 3 bits of the pointer.
(The system was the Cray T90.)
blargg
> blargg writes:
[...]
> > size_t unalignment = (size_t) pointer % align;
> > if ( unalignment > 0 )
> > pointer = (char*) pointer + (align - unalignment);
>
> I've worked on systems where that wouldn't work, though the compiler
> wouldn't necessarily complain about it. Converting a pointer to
> size_t would simply copy or reinterpret the bits, but the
> representation of a pointer to anything smaller than 64 bits was such
> that the result wouldn't be directly meaningful. Machine addresses
> pointed to 64-bit words; for a byte pointer (CHAR_BIT==8), an offset
> within the word was stored in the high-order 3 bits of the pointer.
> (The system was the Cray T90.)
Very interesting, and something to keep in mind when one thinks that
the low bits of a pointer always correspond to the byte alignment. So
the hardware ignores the upper 3 bits of the address (perhaps those
lines just aren't connected), and for byte accesses the compiler
inserts instructions to read a 64-bit word and then shift it as
dictated by the upper 3 bits of the address. If one wanted to work
portably even on that, one would need to do something like
typedef double maxalign_t;
void* ralloc( size_t size, size_t align, char** pos, char* buf_end )
{
void* result = NULL;
size_t pad = (buf_end - *pos) % align;
size_t padded_size = size + pad;
if ( buf_end - *pos >= padded_size )
{
result = *pos + pad;
*pos += padded_size;
}
return result;
}
/* Example usage with static buffer */
#define BUF_SIZE 100
maxalign_t buf [BUF_SIZE/sizeof(maxalign_t) + 1];
char* pos = (char*) buf;
void init_buf( void )
{
pos = (char*) buf;
}
void* alloc_from_buf( size_t size, size_t align )
{
return ralloc( size, align, &pos, (char*) buf + sizeof buf );
}
This makes the buffer a type with the maximum alignment so that it
will be aligned, and then calculates the adjustment needed by finding
the distance between the current position and the (also aligned) end.
It's nice because it doesn't involve any casts from pointer to int.