OK folks, corrected

Discussion in 'C Programming' started by jacob navia, Mar 7, 2008.

  1. jacob navia

    jacob navia Guest

    After a heated discussion, I decided to fix this problem of VLAs
    It took me almost the whole day to realize that

    1) I am storing the size of ALL VLAs in a hidden local variable
    in case somebody calls sizeof(vla), and I need to return that
    size. This means most of this problem was solved already.

    2) I am executing code anyway when I leave a scope.

    THEN:

    When leaving a scope with level bigger than function, i.e. an inner
    scope, go through all local variables of that scope and see if it
    is a VLA.

    If it is, look where its size is stored. Read that size and add it to
    the stack pointer.

    ----------------------------------------------------------------

    Open questions:
    --------------
    What happens with:

    for (int i = 0; i<100; i++) {
    int tab[i*1024];
    int *pint = alloca(42);
    }

    With the current scheme of freeing the VLAs this
    will crash.

    :-(

    This was NOT crashing before. I do not know what to do with
    this stuff.

    gcc dedicates a register to save the stack position
    in such blocks. When the block exits, the whole stack
    is restored, what means that the alloca's done are
    automatically taken care of correctly.

    This is a hell of expensive, since I have only 3 free registers in
    the x86 32 bit architecture. This means that I would lose 33% of the
    machine dedicated to holding the stack value.

    gcc uses esi, and it can (with its bloated "optimize it all"
    machinery) remark that this is only used in this block and
    can be used elsewhere. I do not do global register allocation,
    since it just would bring me a few percent speed gain at enormous
    cost.

    I would have to dedicate the register within the WHOLE function.

    For the time being I will leave it like this. Note that using
    alloca within a loop is quite suicidal anyway, since all the storage
    can't be reclaimed until the function exit in principle in many
    implementations.

    I can "cheat out" by writing this in the docs...

    "Do not use alloca in blocks using VLAs"

    :)

    So, I see the regulars come and start arguing:

    "Jacob recommended alloca and it crashes. "


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Mar 7, 2008
    #1
    1. Advertising

  2. jacob navia

    santosh Guest

    jacob navia wrote:

    > After a heated discussion, I decided to fix this problem of VLAs
    > It took me almost the whole day to realize that
    >
    > 1) I am storing the size of ALL VLAs in a hidden local variable
    > in case somebody calls sizeof(vla), and I need to return that
    > size. This means most of this problem was solved already.
    >
    > 2) I am executing code anyway when I leave a scope.
    >
    > THEN:
    >
    > When leaving a scope with level bigger than function, i.e. an inner
    > scope, go through all local variables of that scope and see if it
    > is a VLA.
    >
    > If it is, look where its size is stored. Read that size and add it to
    > the stack pointer.
    >
    > ----------------------------------------------------------------
    >
    > Open questions:
    > --------------
    > What happens with:
    >
    > for (int i = 0; i<100; i++) {
    > int tab[i*1024];
    > int *pint = alloca(42);
    > }
    >
    > With the current scheme of freeing the VLAs this
    > will crash.
    >
    > :-(
    >
    > This was NOT crashing before. I do not know what to do with
    > this stuff.
    >
    > gcc dedicates a register to save the stack position
    > in such blocks. When the block exits, the whole stack
    > is restored, what means that the alloca's done are
    > automatically taken care of correctly.
    >
    > This is a hell of expensive, since I have only 3 free registers in
    > the x86 32 bit architecture. This means that I would lose 33% of the
    > machine dedicated to holding the stack value.
    >
    > gcc uses esi, and it can (with its bloated "optimize it all"
    > machinery) remark that this is only used in this block and
    > can be used elsewhere. I do not do global register allocation,
    > since it just would bring me a few percent speed gain at enormous
    > cost.
    >
    > I would have to dedicate the register within the WHOLE function.


    Can't you use a normal variable instead of a register?

    <snip>
     
    santosh, Mar 7, 2008
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    santosh wrote:
    >
    > Can't you use a normal variable instead of a register?
    >
    > <snip>
    >



    Not easily. I know the size of the VLA expression because I store
    it in a variable.

    With alloca however, I would have to modfy the
    signature of alloca to make a new alloca

    void *new_alloca(size_t siz, size_t *pVar);

    and alloca would store in pVar the size of the variable
    it allocates, adding it in case there are two or more
    allocations.

    This would imply that I monitor all calls and see if they
    are a call to "alloca", and if they are, I pass the
    address of that variable (that must be block specific)

    Obviously, I would spare myself all the adds to esp
    and I could do it in a single instruction like
    gcc:
    move %esi,%esp

    BUT

    in the x86 is quite expensive.

    In x86-64 this is the way to go since there are 8 more
    registers, and dedicating one is much less expensive anyway.

    In the power pc lcc-win this is not even a problem with 32 registers!

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Mar 7, 2008
    #3
  4. jacob navia

    CBFalconer Guest

    jacob navia wrote:
    >

    .... snip ...
    >
    > I can "cheat out" by writing this in the docs...
    >
    > "Do not use alloca in blocks using VLAs"
    >
    > :)
    >
    > So, I see the regulars come and start arguing:
    >
    > "Jacob recommended alloca and it crashes. "


    You have a much easier and more accurate solution available.
    Document that:

    "alloca is not provided, because it is not described in
    the C standard, and the requirement is handled by VLAs."

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.


    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Mar 7, 2008
    #4
  5. jacob navia

    Guest

    jacob navia <> wrote:
    >
    > What happens with:
    >
    > for (int i = 0; i<100; i++) {
    > int tab[i*1024];
    > int *pint = alloca(42);
    > }
    >
    > With the current scheme of freeing the VLAs this
    > will crash.


    That's why you shouldn't be recommending that people use alloca(). :)

    > I can "cheat out" by writing this in the docs...
    >
    > "Do not use alloca in blocks using VLAs"


    That would be my suggestion. Another alternative would be to set a flag
    in the compiler when you see alloca() in a block and then revert to the
    previous behavior where you don't adjust the stack pointer at the end of
    the block.

    -Larry Jones

    Years from now when I'm successful and happy, ...and he's in
    prison... I hope I'm not too mature to gloat. -- Calvin
     
    , Mar 7, 2008
    #5
  6. jacob navia

    Willem Guest

    jacob wrote:
    ) Open questions:
    ) --------------
    ) What happens with:
    )
    ) for (int i = 0; i<100; i++) {
    ) int tab[i*1024];
    ) int *pint = alloca(42);
    ) }

    I just tested this on gcc-4.1.3 and it looks like the alloca()'d blocks
    are freed as soon as the block is left. Not what the manpage states.

    #include <stdio.h>
    #include <alloca.h>

    int main(void)
    {
    int i, n;
    int *ptr[10];
    n = 10;
    for (i = 0; i < 10; i++) {
    int tab[n];
    ptr = alloca(1);
    }
    for (i = 0; i < 10; i++) {
    fprintf(stderr, "%d: %p\n", i, (void *)ptr);
    }
    return 0;
    }

    Prints:

    0: 0xbf8799e0
    1: 0xbf8799e0
    2: 0xbf8799e0
    3: 0xbf8799e0
    4: 0xbf8799e0
    5: 0xbf8799e0
    6: 0xbf8799e0
    7: 0xbf8799e0
    8: 0xbf8799e0
    9: 0xbf8799e0


    NB: This only happens in the presence of a VLA.
    If you comment out the VLA, the pointers are different.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Mar 7, 2008
    #6
  7. jacob navia

    Ben Pfaff Guest

    jacob navia <> writes:

    > I can "cheat out" by writing this in the docs...
    >
    > "Do not use alloca in blocks using VLAs"


    How about adding a diagnostic so that people who don't read the
    docs get some help too?
    --
    Ben Pfaff
    http://benpfaff.org
     
    Ben Pfaff, Mar 7, 2008
    #7
  8. jacob navia <> writes:
    > After a heated discussion, I decided to fix this problem of VLAs


    Good for you.

    [big snip]

    > I can "cheat out" by writing this in the docs...
    >
    > "Do not use alloca in blocks using VLAs"
    >
    > :)


    Not an unreasonable solution. If you feel you must support alloca(),
    it's good to emphasize how fragile it is. Anyone using it must read
    the implementation's documentation carefully to see how its use is
    restricted.

    > So, I see the regulars come and start arguing:
    >
    > "Jacob recommended alloca and it crashes. "


    We don't need to make that argument. You've made it for us quite
    effectively.

    Now that this issue is settled, please take a moment to consider that
    we were right, and you were wrong, all along. Everyone is wrong
    sometimes, but consider not responding to all criticism (and all bug
    reports from people you dislike) as personal attacks.

    This post is intended as *constructive* criticism. I'll be pleasantly
    surprised if you take it that way. I truly don't enjoy watching you
    act like a paranoid fool.

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Mar 7, 2008
    #8
  9. "jacob navia" <> schreef in bericht
    news:fqr0qi$s64$...
    > 1) I am storing the size of ALL VLAs in a hidden local variable
    > in case somebody calls sizeof(vla), and I need to return that
    > size. This means most of this problem was solved already.
    >
    > 2) I am executing code anyway when I leave a scope.
    >


    I havent seen the VLA discussion, but why would anyone want to use alloca
    and VLA's at the same time?

    Or does it crash too when you have a VLA and call a function that uses
    alloca?
     
    Serve Laurijssen, Mar 7, 2008
    #9
  10. jacob navia

    user923005 Guest

    On Mar 7, 9:50 am, Keith Thompson <> wrote:
    > jacob navia <> writes:
    > > After a heated discussion, I decided to fix this problem of VLAs

    >
    > Good for you.
    >
    > [big snip]
    >
    > > I can "cheat out" by writing this in the docs...

    >
    > > "Do not use alloca in blocks using VLAs"

    >
    > > :)

    >
    > Not an unreasonable solution.  If you feel you must support alloca(),
    > it's good to emphasize how fragile it is.  Anyone using it must read
    > the implementation's documentation carefully to see how its use is
    > restricted.
    >
    > > So, I see the regulars come and start arguing:

    >
    > > "Jacob recommended alloca and it crashes. "

    >
    > We don't need to make that argument.  You've made it for us quite
    > effectively.
    >
    > Now that this issue is settled, please take a moment to consider that
    > we were right, and you were wrong, all along.  Everyone is wrong
    > sometimes, but consider not responding to all criticism (and all bug
    > reports from people you dislike) as personal attacks.
    >
    > This post is intended as *constructive* criticism.  I'll be pleasantly
    > surprised if you take it that way.  I truly don't enjoy watching you
    > act like a paranoid fool.


    The fact that he recognized a problem, repaired it, and reported the
    correction is certainly encouraging. As long as people show me that
    they are actually listening to dialogue (even if they drag their feet,
    kicking and screaming during the dialog), there is no reason to stop
    reading them. So Jacob will never go into my category for people like
    'Kenny' and 'Twink' who are simply contrary for the sake of being
    contrary.
     
    user923005, Mar 7, 2008
    #10
  11. jacob navia

    Ian Collins Guest

    jacob navia wrote:
    > After a heated discussion, I decided to fix this problem of VLAs
    > It took me almost the whole day to realize that
    >
    > 1) I am storing the size of ALL VLAs in a hidden local variable
    > in case somebody calls sizeof(vla), and I need to return that
    > size. This means most of this problem was solved already.
    >
    > 2) I am executing code anyway when I leave a scope.
    >
    > THEN:
    >
    > When leaving a scope with level bigger than function, i.e. an inner
    > scope, go through all local variables of that scope and see if it
    > is a VLA.
    >
    > If it is, look where its size is stored. Read that size and add it to
    > the stack pointer.
    >

    That's good to hear. It's a pity not all compiler vendors respond so
    quickly.

    > ----------------------------------------------------------------
    >
    > Open questions:
    > --------------
    > What happens with:
    >
    > for (int i = 0; i<100; i++) {
    > int tab[i*1024];
    > int *pint = alloca(42);
    > }
    >
    > With the current scheme of freeing the VLAs this
    > will crash.
    >

    Drop alloca in favour of VLAs. Or implement alloca as a wrapper over a VLA.

    --
    Ian Collins.
     
    Ian Collins, Mar 7, 2008
    #11
  12. jacob navia

    jacob navia Guest

    Serve Laurijssen wrote:
    >
    > "jacob navia" <> schreef in bericht
    > news:fqr0qi$s64$...
    >> 1) I am storing the size of ALL VLAs in a hidden local variable
    >> in case somebody calls sizeof(vla), and I need to return that
    >> size. This means most of this problem was solved already.
    >>
    >> 2) I am executing code anyway when I leave a scope.
    >>

    >
    > I havent seen the VLA discussion, but why would anyone want to use
    > alloca and VLA's at the same time?
    >
    > Or does it crash too when you have a VLA and call a function that uses
    > alloca?
    >


    No, that is not possible anyway since a function when leaving
    will erase any alloca allocations

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Mar 7, 2008
    #12
  13. In article <>,
    user923005 <> wrote:
    ....
    >reading them. So Jacob will never go into my category for people like
    >'Kenny' and 'Twink' who are simply contrary for the sake of being
    >contrary.


    No. We're not!
     
    Kenny McCormack, Mar 7, 2008
    #13
  14. Ian Collins <> writes:
    > jacob navia wrote:

    [...]
    >> Open questions:
    >> --------------
    >> What happens with:
    >>
    >> for (int i = 0; i<100; i++) {
    >> int tab[i*1024];
    >> int *pint = alloca(42);
    >> }
    >>
    >> With the current scheme of freeing the VLAs this
    >> will crash.
    >>

    > Drop alloca in favour of VLAs. Or implement alloca as a wrapper over a VLA.


    The former would break any existing code that uses alloca (which I'm
    not entirely convinced would be a bad thing). The latter doesn't
    satisfy the required semantics of alloca; if you call alloca N times
    in a loop, all N allocated objects continue to exist until the
    function terminates.

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Mar 8, 2008
    #14
  15. jacob navia

    Ian Collins Guest

    Keith Thompson wrote:
    > Ian Collins <> writes:
    >> jacob navia wrote:

    > [...]
    >>> Open questions:
    >>> --------------
    >>> What happens with:
    >>>
    >>> for (int i = 0; i<100; i++) {
    >>> int tab[i*1024];
    >>> int *pint = alloca(42);
    >>> }
    >>>
    >>> With the current scheme of freeing the VLAs this
    >>> will crash.
    >>>

    >> Drop alloca in favour of VLAs. Or implement alloca as a wrapper over a VLA.

    >
    > The former would break any existing code that uses alloca (which I'm
    > not entirely convinced would be a bad thing). The latter doesn't
    > satisfy the required semantics of alloca; if you call alloca N times
    > in a loop, all N allocated objects continue to exist until the
    > function terminates.
    >

    How can a non-standard function have defined semantics?

    --
    Ian Collins.
     
    Ian Collins, Mar 8, 2008
    #15
  16. "jacob navia" <> schreef in bericht
    news:fqsdun$esk$...
    > Serve Laurijssen wrote:
    >>
    >> "jacob navia" <> schreef in bericht
    >> news:fqr0qi$s64$...
    >>> 1) I am storing the size of ALL VLAs in a hidden local variable
    >>> in case somebody calls sizeof(vla), and I need to return that
    >>> size. This means most of this problem was solved already.
    >>>
    >>> 2) I am executing code anyway when I leave a scope.
    >>>

    >>
    >> I havent seen the VLA discussion, but why would anyone want to use alloca
    >> and VLA's at the same time?
    >>
    >> Or does it crash too when you have a VLA and call a function that uses
    >> alloca?
    >>

    >
    > No, that is not possible anyway since a function when leaving
    > will erase any alloca allocations


    Well then the only time I can think of that somebody uses alloca and VLA's
    at the same time is when a macro is used that uses VLA's or alloca and the
    programmer forgot that.
    A reminder by the compiler would be very handy :) It could save loads of
    debugging time
     
    Serve Laurijssen, Mar 8, 2008
    #16
  17. Ian Collins <> writes:
    > Keith Thompson wrote:
    >> Ian Collins <> writes:
    >>> jacob navia wrote:

    >> [...]
    >>>> Open questions:
    >>>> --------------
    >>>> What happens with:
    >>>>
    >>>> for (int i = 0; i<100; i++) {
    >>>> int tab[i*1024];
    >>>> int *pint = alloca(42);
    >>>> }
    >>>>
    >>>> With the current scheme of freeing the VLAs this
    >>>> will crash.
    >>>>
    >>> Drop alloca in favour of VLAs. Or implement alloca as a wrapper
    >>> over a VLA.

    >>
    >> The former would break any existing code that uses alloca (which I'm
    >> not entirely convinced would be a bad thing). The latter doesn't
    >> satisfy the required semantics of alloca; if you call alloca N times
    >> in a loop, all N allocated objects continue to exist until the
    >> function terminates.
    >>

    > How can a non-standard function have defined semantics?


    The same way malloc() had defined semantics before 1989.

    Every alloc() man page I've seen says the allocated memory is freed
    when the calling function returns. If an implementation wants to
    provide a (non-standard) function that doesn't behave that way, it
    shouldn't call it "alloca".

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Mar 8, 2008
    #17
  18. Ian Collins said:

    <snip>

    > How can a non-standard function have defined semantics?


    By making it the fourth argument in a qsort call? :)

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 8, 2008
    #18
  19. jacob navia

    santosh Guest

    Richard Heathfield wrote:

    > Ian Collins said:
    >
    > <snip>
    >
    >> How can a non-standard function have defined semantics?

    >
    > By making it the fourth argument in a qsort call? :)


    Doesn't that constitute as just defining the interface?
     
    santosh, Mar 8, 2008
    #19
  20. On Sat, 08 Mar 2008 15:05:05 +0530, santosh wrote:
    > Richard Heathfield wrote:
    >> Ian Collins said:
    >>> How can a non-standard function have defined semantics?

    >>
    >> By making it the fourth argument in a qsort call? :)

    >
    > Doesn't that constitute as just defining the interface?


    "The function shall return an integer less than, equal to, or greater than
    zero if the first argument is considered to be respectively less than,
    equal to, or greater than the second."

    Unrelated to the actual topic, but a question about qsort: is the
    behaviour defined if compar longjmps out of qsort when the two arguments
    are considered incomparable by the application? It needs some way to exit
    without returning an integer. :)
     
    Harald van Dijk, Mar 8, 2008
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?iso-8859-1?Q?Fran=E7ois?= Pinard

    Re: NEW MAINTAINER for Pymacs [corrected]

    =?iso-8859-1?Q?Fran=E7ois?= Pinard, Sep 24, 2004, in forum: Python
    Replies:
    2
    Views:
    324
    =?iso-8859-1?Q?Fran=E7ois?= Pinard
    Sep 24, 2004
  2. Markus Franz
    Replies:
    2
    Views:
    354
    Denis S. Otkidach
    Dec 28, 2004
  3. Sudheer Gupta

    Using C struct in Python** corrected

    Sudheer Gupta, Jun 7, 2006, in forum: Python
    Replies:
    0
    Views:
    291
    Sudheer Gupta
    Jun 7, 2006
  4. Girish Sahani
    Replies:
    5
    Views:
    286
    Fredrik Lundh
    Jun 12, 2006
  5. Anonymous
    Replies:
    2
    Views:
    339
    Barry
    Aug 29, 2007
Loading...

Share This Page