Custom memory allocator - alignment

Discussion in 'C Programming' started by Romeo Colacitti, Mar 4, 2005.

  1. I have a need to make a custom quasi-memory allocator, and I remembered
    a simple ons in K&R2. Looking at the code for it now, I think I notice
    a "fault" in the design, and I was wondering if people would back me up
    on this.

    The design basically uses a pool of memory, allocated as a character
    array. Pointers into the array are retured by the allocated function.
    Isn't this very dangerous, as a char has very lenient memory alignment
    requirements, which would allow the compiler to allocate the array
    starting at a location that might not be a multiple of an address
    required for other type. Also, pointers in the middle of the arrat
    (after the first allocation) will certainly be unaligned for some
    types.

    My fix, is to use an array of ints (as they match the natural size for
    my syste), and then use a pointer into this array of ints. When
    returning the pointer value, I could cast it to (void *).

    Isn't this much safer than the char array versoin?

    Can someone correct me on this, or verify my line of thoughts? thx
     
    Romeo Colacitti, Mar 4, 2005
    #1
    1. Advertising

  2. Romeo Colacitti

    Chris Torek Guest

    In article <>
    Romeo Colacitti <> wrote:
    >I have a need to make a custom quasi-memory allocator, and I remembered
    >a simple ons in K&R2. Looking at the code for it now, I think I notice
    >a "fault" in the design, and I was wondering if people would back me up
    >on this.
    >
    >The design basically uses a pool of memory, allocated as a character
    >array. Pointers into the array are retured by the allocated function.
    >Isn't this very dangerous, as a char has very lenient memory alignment
    >requirements ...


    It is indeed unsuitable as a general-purpose allocator. (As a
    char-array allocator it works fine, of course.)

    >My fix, is to use an array of ints (as they match the natural size for
    >my syste), and then use a pointer into this array of ints. When
    >returning the pointer value, I could cast it to (void *).
    >
    >Isn't this much safer than the char array versoin?


    Well, how much is "much"? Safe*r*, yes, but perhaps not so much.
    In particular it will not fix the problem on machines with 4-byte
    "int"s and 8-byte alignment requirements, such as SPARC and MIPS
    processors.

    ANSI/ISO C, for whatever reasons, does not give one the tools
    required to write malloc() in pure ANSI/ISO C. I find this somewhat
    unfortunate, but for those who want to press on regardless, it
    usually suffices to have the two macros we put into <machine/param.h>
    on 4.xBSD systems: ALIGN(p) takes an arbitrary pointer-or-"intptr_t"
    value p, and returns an aligned variant of it (as an intptr_t),
    which has possibly been increased by some number of bytes ("char"s);
    and ALIGNBYTES is the maximum such increase.

    In other words, on a BSD system, you can write a malloc() clone
    using ALIGNBYTES (to know how many extra bytes to allocate for
    rounding) and ALIGN() (to align pointers). You can also use these
    for other sneaky allocation tricks involving malloc() itself.
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Mar 4, 2005
    #2
    1. Advertising

  3. Chris Torek wrote:
    > In article <>
    > Romeo Colacitti <> wrote:
    > >
    > >The design basically uses a pool of memory, allocated as a character
    > >array. Pointers into the array are retured by the allocated

    function.
    > >Isn't this very dangerous, as a char has very lenient memory

    alignment
    > >requirements ...

    >
    > It is indeed unsuitable as a general-purpose allocator. (As a
    > char-array allocator it works fine, of course.)
    >


    Thank you for clearing that up. The lack of a warning in K&R got me
    confused.

    >
    > >My fix, is to use an array of ints (as they match the natural size

    for
    > >my syste), and then use a pointer into this array of ints. When
    > >returning the pointer value, I could cast it to (void *).
    > >
    > >Isn't this much safer than the char array versoin?

    >
    > Well, how much is "much"? Safe*r*, yes, but perhaps not so much.
    > In particular it will not fix the problem on machines with 4-byte
    > "int"s and 8-byte alignment requirements, such as SPARC and MIPS
    > processors.
    >


    Oh. I would have thought that most implementations (like mine) would
    make sizeof "int" equal to the alignment requirement.

    >
    > ANSI/ISO C, for whatever reasons, does not give one the tools
    > required to write malloc() in pure ANSI/ISO C.


    Is malloc usually coded in assembly?

    > I find this somewhat
    > unfortunate, but for those who want to press on regardless, it
    > usually suffices to have the two macros we put into <machine/param.h>
    > on 4.xBSD systems: ALIGN(p) takes an arbitrary pointer-or-"intptr_t"
    > value p, and returns an aligned variant of it (as an intptr_t),
    > which has possibly been increased by some number of bytes ("char"s);
    > and ALIGNBYTES is the maximum such increase.
    >


    When it returns the aligned variant, does it copy over the contents of
    the object too?

    >
    > In other words, on a BSD system, you can write a malloc() clone
    > using ALIGNBYTES (to know how many extra bytes to allocate for
    > rounding) and ALIGN() (to align pointers). You can also use these
    > for other sneaky allocation tricks involving malloc() itself.


    Well beyond my comprehension, but thank you for clearing up my massive
    confusion. I will use an array of ints in my case.
     
    Romeo Colacitti, Mar 4, 2005
    #3
  4. On 3 Mar 2005 22:26:25 -0800, "Romeo Colacitti" <>
    wrote:
    >Chris Torek wrote:
    >> In article <>
    >> Romeo Colacitti <> wrote:
    >> >
    >> >The design basically uses a pool of memory, allocated as a character
    >> >array. Pointers into the array are retured by the allocated

    >function.
    >> >Isn't this very dangerous, as a char has very lenient memory

    >alignment
    >> >requirements ...

    >>
    >> It is indeed unsuitable as a general-purpose allocator. (As a
    >> char-array allocator it works fine, of course.)
    >>

    >
    >Thank you for clearing that up. The lack of a warning in K&R got me
    >confused.


    have you read K&R2 malloc implementation?
    no and NO, K&R2 malloc returns arrays of units aligned to 8 bytes in
    my x86>=386 Pc and borland C compiler this seems good; sizeof(long)=4;
    but this not fits the other restriction sizeof(long double)=10. it
    seems I remember that if an array of long double 10bytes are aligned
    to 8bytes => x86 cpu can perform operations but 2x more slow: is it
    true?

    How about change *here in my pc&cpu* "Align long" with
    "Align long double"?
    (so there is not problems with long double arrays)
    Thank you very much
     
    RoSsIaCrIiLoIA, Mar 4, 2005
    #4
  5. Romeo Colacitti

    Chris Torek Guest

    [snippage throughout]

    >Chris Torek wrote:
    >> Well, how much is "much"? Safe*r*, yes, but perhaps not so much.
    >> In particular it will not fix the problem on machines with 4-byte
    >> "int"s and 8-byte alignment requirements, such as SPARC and MIPS
    >> processors.


    In article <>
    Romeo Colacitti <> wrote:
    >Oh. I would have thought that most implementations (like mine) would
    >make sizeof "int" equal to the alignment requirement.


    Well, when "maximum alignment" is 128 bytes, do you really want
    128-byte "int"s? Even if maximum alignment is a mere 8 or 16 bytes,
    as is the case on many modern CPUs, are you sure you want to commit
    to having at-least-8-byte "int"s (so that INT_MAX is 9223372036854775807)
    on modern 64-bit CPUs? If so, what will you use for a four-byte
    type, if "char" is to be one 8-bit byte and "short" is to be two?

    >> ANSI/ISO C, for whatever reasons, does not give one the tools
    >> required to write malloc() in pure ANSI/ISO C.


    >Is malloc usually coded in assembly?


    I would imagine not. But one need not resort to assembly code,
    when non-portable C will suffice. The problem then lies in the
    fact that the code is non-portable, so that moving it from machine
    A to machine B causes it to break.

    >> ... for those who want to press on regardless, it
    >> usually suffices to have the two macros we put into <machine/param.h>
    >> on 4.xBSD systems: ALIGN(p) takes an arbitrary pointer-or-"intptr_t"
    >> value p, and returns an aligned variant of it (as an intptr_t),
    >> which has possibly been increased by some number of bytes ("char"s);
    >> and ALIGNBYTES is the maximum such increase.


    >When it returns the aligned variant, does it copy over the contents of
    >the object too?


    I fear you misunderstand: the ALIGN macro does no copying whatsoever.
    In fact, three actual implementations, for three different machines,
    are:

    /* Intel, before SSE */
    #define ALIGNBYTES 3
    #define ALIGN(p) (((intptr_t)(p) + 3) & ~3)

    and:

    /* SPARC and MIPS */
    #define ALIGNBYTES 7
    #define ALIGN(p) (((intptr_t)(p) + 7) & ~7)

    and:

    /* Intel, when using SSE */
    #define ALIGNBYTES 15
    #define ALIGN(p) (((intptr_t)(p) + 15) & ~15)

    It makes little sense to apply ALIGN() to a pointer after storing
    value(s) into the memory to which it points, because the whole
    point of applying the ALIGN() macro is to come up with a "well-aligned"
    pointer, so that *(type)ptr = value works regardless of the given
    pointer-type (char *, int *, double *, long double *, float (**)[5],
    short *(**)(int), whatever).

    Note that the definition on a Data General Eclipse might perhaps
    be:

    #define ALIGNBYTES 3
    #define ALIGN(p) (((intptr_t)(p) + 1) & ~1)

    (depending on the rules for conversion of arbitrary pointers to
    type "intptr_t" -- this assumes the conversion produces a word
    pointer in all cases), so it is not necessarily the case that
    the "number of bytes" (chars) needed is the same as the constant
    added-and-masked-out. (If the conversion from pointer-to-integer
    and back does not account for byte pointers vs word pointers,
    these macros will not suffice, at least not without additional
    rules not present in the BSD implementations.)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Mar 7, 2005
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brian Genisio
    Replies:
    12
    Views:
    8,090
    tom_usenet
    Jan 15, 2004
  2. Alex Vinokur
    Replies:
    16
    Views:
    12,338
    Alex Vinokur
    Aug 16, 2004
  3. Chris Thomasson

    allocator alignment issues...

    Chris Thomasson, Aug 22, 2007, in forum: C++
    Replies:
    1
    Views:
    369
    Chris Thomasson
    Aug 22, 2007
  4. Spiros Bousbouras

    Re: standard memory allocator alignment issue...

    Spiros Bousbouras, May 13, 2008, in forum: C Programming
    Replies:
    9
    Views:
    315
    Spiros Bousbouras
    May 13, 2008
  5. FtM
    Replies:
    64
    Views:
    1,342
    88888 Dihedral
    Jan 7, 2012
Loading...

Share This Page