Kevin Mullin wrote:
>
> Steve Clamage wrote:
>
>   In article 10B1@oz.net, Kevin Mullin <kmullin@oz.net> writes:
>   >What is the standard operation of the delete operator when it is
>   given
>   >an address NOT provided by the new operator?  According to IBM (we
>   are
>   >using their IBM C/C++ for MVS/ESA product, V3R2M0) it is stated in
>   the
>   >proposed ANSI standard for C++ as undefined.  I think it is a
>   problem
>   >that the reaction of delete to this situation is undefined.
>
...
>   The standard could mandate particular behavior in the presence of an
>
>   invalid delete. That in turn would require that implementations
>   always
>   validate pointer expressions passed to 'delete', something that is
>   very
>   expensive to do. (Some languages do make that requirement, and
>   run-time
>   efficiency suffers.)
>
> For my own education, I'd like to know what this overhead would be.  I
> mean, in my overloaded new and delete operators (which are faster, by
> the way.  I've saved 20% run time expense when running with IBM C/C++ on
> MVS!) I catch bad addresses.  I don't validate the pointer expressions.

What does 'validate the pointer expressions' mean to you, if it doesn't
mean 'catch bad addresses'?

> My delete (and I presume the standard delete) simply gets an address.
> My delete (and I presume the standard delete) knows about that address,
> since it was the partner 'new' operator which handed it out, and I
> presume that new and delete are somehow related.  Anyway, all I do is
> say 'Hmm.  That address is not mine!'.  In that case, on MVS, I call a

How do you determine that the address is not yours? I'm not aware of any
reliable method that doesn't involve a search requiring time at least
proportional to log(N), where 'N' is the number of currently allocated
blocks. A simpler, faster implementation can assume that there are
pointers to the previous and next memory blocks at negative offsets from
the provided address, and therefore needs to examine at most three of
the memory blocks. Obviously, such a scheme could fail catastrophically
if passed an invalid address. The standard does not define the
consequences of deleting an invalid object, precisely to allow such
implementations. The overhead required by address validation may be less
important to you than ease of debugging erroneous programs; however, C++
is used by a wide variety of applications, and some of them need every
possible nanosecond.

If you saved time compared to the IBM 'delete', despite implementing a
search, they (hopefully) are implementing some even more sophisticated
validity checks. Are you sure a mere 20% time savings was worth the
development time required, and abandoning whatever those validity checks
might be?

> system dump routine to see who gave it to me, and then I can debug that
> call.  All I'm asking is for the standard delete to indicate that the
> delete failed, not why it failed.  And I certainly wouldn't expect the
> standard to mandate that a dump must somehow be provided.  I would like
> to be able to test the return code from delete (or some other mechanism
> to test for validity of the delte) and be able to see during code

Just because 'delete' failed doesn't mean that it is easy for 'delete'
to know that it has failed. Unless 'delete' does address validation as
described above, it cannot know that it has attempted to change values
at the wrong locations in memory, so it cannot return an error code to
indicate that fact.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Kevin Mullin <kmullin@oz.net> writes:

>.. in my overloaded new and delete operators ...
>I catch bad addresses.

Fine!  That is all well and good.

>In that case, on MVS, I call a
>system dump routine to see who gave it to me, and then I can debug that
>call.

Seems to me that that is a fine thing to do.
It is also perfectly standard-conforming.

>All I'm asking is for the standard delete to indicate that the
>delete failed, not why it failed.  And I certainly wouldn't expect the
>standard to mandate that a dump must somehow be provided.  I would like
>to be able to test the return code from delete (or some other mechanism
>to test for validity of the delte) and be able to see during code
>development that something is amiss.

If the operator delete function detects that it has been passed a bad
pointer, then it has found a quite serious bug, and under most
circumstances it really ought to terminate the process.  Then you would
definitely be able to see that something is amiss.

Providing a return value from delete would only encourage people
implementing delete to not terminate the process in such a situation,
which in most circumstances would be bad.  It would be particularly bad
if the code that called delete ignored the return value.  Given that
all existing code ignores the return value of delete, this would be
very bad indeed.

A better alternative would be for it to throw an exception.
However, even this may get caught by a `catch(...)' handler,
and might go unnoticed.  In a development environment, it would
be better to terminate the process.

Currently deleting a bad pointer can result in delete throwing an
exception, terminating the process, printing out a nice stack dump,
or whatever.  Whether or not the implementation actually does something
sensible is a quality of implementation issue.  If the implementation
you are using is not good quality, or does something that is not optimal
for your purposes, I sympathize.

Should the C++ standard _require_ an implementation to do something
sensible when delete is called with a bad pointer?  No, because in
general implementations can't always tell, at least not with 100%
certainty, or not efficiently, or both.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Kevin Mullin <kmullin@oz.net> writes:

|>  [Steve Clamage writes:]
|>    The standard could mandate particular behavior in the presence of an
|>    invalid delete. That in turn would require that implementations always
|>    validate pointer expressions passed to 'delete', something that is very
|>    expensive to do. (Some languages do make that requirement, and run-time
|>    efficiency suffers.)
|>
|>  For my own education, I'd like to know what this overhead would be.  I
|>  mean, in my overloaded new and delete operators (which are faster, by
|>  the way.  I've saved 20% run time expense when running with IBM C/C++ on
|>  MVS!) I catch bad addresses.  I don't validate the pointer expressions.
|>  My delete (and I presume the standard delete) simply gets an address.
|>  My delete (and I presume the standard delete) knows about that address,
|>  since it was the partner 'new' operator which handed it out, and I
|>  presume that new and delete are somehow related.  Anyway, all I do is
|>  say 'Hmm.  That address is not mine!'.

That's easier said than done.  So how do you know if the address is
yours?  The only general solution I know is to put it into some sort of
associative container on new, and see if the value passed to delete is
there.  (Note that the standard does require delete to be a no-op on a
null pointer.  But this is a special case for which there is, or should
be, an efficient test.)

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kuyper <kuyper@wizard.net> wrote in article
<333FE04D.167E@wizard.net>...
> Kevin Mullin wrote:
[...]
> >   validate pointer expressions passed to 'delete', something that is
> >   very expensive to do.
[...]
> > For my own education, I'd like to know what this overhead would be.
[...]
> What does 'validate the pointer expressions' mean to you, if it doesn't
> mean 'catch bad addresses'?

> How do you determine that the address is not yours? I'm not aware of any
> reliable method that doesn't involve a search requiring time at least
> proportional to log(N), where 'N' is the number of currently allocated
> blocks.

You can do this in O(1) time, with a small proportionallity constant.

new() and delete() share a vector of pointers to currently allocated
blocks.  Valid blocks are prefixed with their index in the vector.

pseudo code for "normal" new() and delete() without validity checking.
   new(size)
      find an available block containing at least (size+sizeof(size_t))
bytes.
      grab the block.
      store size in the first word.
      return a pointer to the second word.
  delete(ptr)
      size = *((word*)ptr-1);
      restore the block to the available pool

pseudo code for "enhanced" new() and delete().  Extra work marked with '*'

  struct entry
  {
    void* ptr;
    size_t size; // If ptr points at an allocated block, this is its size
    // If flag is ALLOCATED_BLOCK, ptr points at an allocated block, and
size is the size
    // of the allocated block.
    // If flag is AVAILABLE_ENTRY, ptr is junk, and size is used to
maintain a linked list of
    // available entries (by array index).
    enum{ ALLOCATED_BLOCK, AVAILABLE_ENTRY } flag;
  };
  static array<entry> entries;
  int free_list;
  new(size)
     find an available block containing at least (size+sizeof(int)) bytes
     grab the block
     * find an available entry, either in free_list, or by growing entries.
     * Store the pointer to the block, and the block's size in the entry.
     Store the entry's index in the first word of the block.
     Return the the pointer to the second word of the block
  delete(ptr)
      index = *((word*)ptr-1);
      * Make sure index is in range 0...array.Size();
      * Make sure array[index].flag == ALLOCATED_BLOCK;
      * Make sure array[index].ptr == ptr;
      size = array[index].size;
      Put block into the available pool
      * Put array[index] into the free entry list.

You can clearly perform all of the '*' operations except for "growing
entries" at the cost of just several instructions.  There are several
strategies for growing arrays at amoratized constant costs of just several
instructions per element.  In many cases these costs will be significantly
less than the cost to find and grab available blocks, or to return
available blocks to the pool.

Other penalties associated with my scheme are extra storage requirements
(an extra pointer, index, and flag bit per allocated block) and increased
library complexity.

This stuff only tells global delete that the block it has been asked to
delete was really provided by global new.  It doesn't detect type errors.
    void* v = new T1;
    delete (T2*)v;
Also if the 'entries' array gets corrupted by a rogue pointer, all bets are
off.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Bill Wade <bill.wade@stoner.com> wrote in article
<01bc3ec4$a0f193f0$2864370a@janeway>...
> James Kuyper <kuyper@wizard.net> wrote in article
> <333FE04D.167E@wizard.net>...
> > Kevin Mullin wrote:
> [...]
> > >   validate pointer expressions passed to 'delete', something that is
> > >   very expensive to do.
> [...]
> > > For my own education, I'd like to know what this overhead would be.
> [...]
> > What does 'validate the pointer expressions' mean to you, if it doesn't
> > mean 'catch bad addresses'?
>
> > How do you determine that the address is not yours? I'm not aware of
any
> > reliable method that doesn't involve a search requiring time at least
> > proportional to log(N), where 'N' is the number of currently allocated
> > blocks.

One could use a hash-table implementation for the associative
array suggested by Mr. Kanze.  This would also be O(1) and
would avoid the problem I mention below.

> You can do this in O(1) time, with a small proportionallity constant.
>
> new() and delete() share a vector of pointers to currently allocated
> blocks.  Valid blocks are prefixed with their index in the vector.

But what about invalid block pointers?  You cannot even be sure
that the supposed block can be dereferenced without causing an
address fault.  There is no C++ way to avoid or trap address faults
for randomly accessed memory.  (Sorry for the pun!)

> pseudo code for "normal" new() and delete() without validity checking.
[cut for length, along with most of "improved" code]
>   delete(ptr)
>       index = *((word*)ptr-1);
Address fault here for some values of ptr on any modern OS.
The next steps are great, if they actually get executed.
>       * Make sure index is in range 0...array.Size();
>       * Make sure array[index].flag == ALLOCATED_BLOCK;
>       * Make sure array[index].ptr == ptr;
>       size = array[index].size;
>       Put block into the available pool
>       * Put array[index] into the free entry list.
[balance of discussion cut]
--
-- Larry Brasfield
-- The aforementioned views are mine alone and are not
-- to be construed as representing my employer's views.
-- (For an e-mail reply, remove SpamGuard_.)
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

"Larry Brasfield" <SpamGuard_larrybr@microsoft.com> writes:

|>  Bill Wade <bill.wade@stoner.com> wrote in article
|>  <01bc3ec4$a0f193f0$2864370a@janeway>...
|>  > James Kuyper <kuyper@wizard.net> wrote in article
|>  > <333FE04D.167E@wizard.net>...
|>  > > Kevin Mullin wrote:
|>  > [...]
|>  > > >   validate pointer expressions passed to 'delete', something that is
|>  > > >   very expensive to do.
|>  > [...]
|>  > > > For my own education, I'd like to know what this overhead would be.
|>  > [...]
|>  > > What does 'validate the pointer expressions' mean to you, if it doesn't
|>  > > mean 'catch bad addresses'?
|>  >
|>  > > How do you determine that the address is not yours? I'm not aware of
|>  any
|>  > > reliable method that doesn't involve a search requiring time at least
|>  > > proportional to log(N), where 'N' is the number of currently allocated
|>  > > blocks.
|>
|>  One could use a hash-table implementation for the associative
|>  array suggested by Mr. Kanze.  This would also be O(1) and
|>  would avoid the problem I mention below.
|>
|>  > You can do this in O(1) time, with a small proportionallity constant.
|>  >
|>  > new() and delete() share a vector of pointers to currently allocated
|>  > blocks.  Valid blocks are prefixed with their index in the vector.
|>
|>  But what about invalid block pointers?  You cannot even be sure
|>  that the supposed block can be dereferenced without causing an
|>  address fault.  There is no C++ way to avoid or trap address faults
|>  for randomly accessed memory.  (Sorry for the pun!)

If you are writing your own memory management, there is a very great
probability that the code is not "100% guaranteed portable" anyway.
(There is, for example, no guaranteed portable way of hash coding a
pointer, even supposing you can read it.)  In practice, if the pointer
makes it into your operator delete, you can probably count on being able
to read it.  If the implementation were going to trap on accessing an
invalid pointer, it would have done so when the user read the pointer to
pass it to you.

The hash table implementation is doable on most implementations,
although not portably, and the constant factor is probably fairly
important.  (Some care is also necessary to avoid infinite recursion,
since the hash table probably needs dynamic memory itself.)  In my own
debugging operator new, I've contented myself with marking the bytes in
front of the returned pointer with a specific value, and changing the
mark back on free.  In theory, of course, it is quite possible that a
random pointer will have exactly this byte pattern preceding it; in
practice, the case is rare enough for the check to be worthwhile.  (It
probably wouldn't be an acceptable if the check were used for
determining a defined behavior, e.g.: doing nothing and returning an
error code.  As a debugging aid, however, it will catch the error
immediately most of the time.  Which is better than what the standard
operator new does.)

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kanze <james-albert.kanze@vx.cit.alcatel.fr> wrote in article
<rf5zpvgtubr.fsf@vx.cit.alcatel.fr>...
> "Larry Brasfield" <SpamGuard_larrybr@microsoft.com> writes:
. . .
> |>  But what about invalid block pointers?  You cannot even be sure
> |>  that the supposed block can be dereferenced without causing an
> |>  address fault.  There is no C++ way to avoid or trap address faults
> |>  for randomly accessed memory.  (Sorry for the pun!)
>
> If you are writing your own memory management, there is a very great
> probability that the code is not "100% guaranteed portable" anyway.
> (There is, for example, no guaranteed portable way of hash coding a
> pointer, even supposing you can read it.)  In practice, if the pointer
> makes it into your operator delete, you can probably count on being able
> to read it.  If the implementation were going to trap on accessing an
> invalid pointer, it would have done so when the user read the pointer to
> pass it to you.

The point I intended to make remains valid.
Mr. Wade's pseudo-code for a "delete(ptr)" implementation began:
      index = *((word*)ptr-1);
I annotated this with:
   Address fault here for some values of ptr on any modern OS.

I agree with your criticism of my statement "You cannot even be
sure that the supposed block can be dereferenced without causing
an address fault."  I should have written "read", not "dereferenced".
For bogus values of ptr, the "supposed block" may be located in
portions of the address space that are not accessible.

The point stands that the expression
  *((word*)ptr-1)
is likely to fail given arbitrary values of ptr.

[fine hash table discussion cut for brevity]
--
-- Larry Brasfield
-- The aforementioned views are mine alone and are not
-- to be construed as representing my employer's views.
-- (For an e-mail reply, remove SpamGuard_.)
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

"Larry Brasfield" <SpamGuard_larrybr@microsoft.com> wrote:

>The point stands that the expression
>  *((word*)ptr-1)
>is likely to fail given arbitrary values of ptr.

That said, though, I think it's arguable that common delete failures are
often a result of using a dangling pointer, as opposed to a random one.
Also, there are actually many pointer values in operating systems I've
used that don't crash if you try to read them (note that he's not
writing to it, but reading from it). That's why it's often so hard to
find bad pointers -- the program doesn't just crash as a result of a
simple dereference, it crashes later on when it's harder to find the
cause.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Steve Clamage wrote:

  In article 10B1@oz.net, Kevin Mullin <kmullin@oz.net> writes:
  >What is the standard operation of the delete operator when it is
  given
  >an address NOT provided by the new operator?  According to IBM (we
  are
  >using their IBM C/C++ for MVS/ESA product, V3R2M0) it is stated in
  the
  >proposed ANSI standard for C++ as undefined.  I think it is a
  problem
  >that the reaction of delete to this situation is undefined.

  The operand of 'delete' must be a pointer to an object returned from

  a new-expression, and must also meet some other requirements about
  type and whether the single-object or array versions were used.
  Otherwise the results are indeed undefined (5.3.5 "Delete" in the
  draft standard).

  In writing the language standard, there are not very many options
  in this case.

  The standard could mandate particular behavior in the presence of an

  invalid delete. That in turn would require that implementations
  always
  validate pointer expressions passed to 'delete', something that is
  very
  expensive to do. (Some languages do make that requirement, and
  run-time
  efficiency suffers.)

For my own education, I'd like to know what this overhead would be.  I
mean, in my overloaded new and delete operators (which are faster, by
the way.  I've saved 20% run time expense when running with IBM C/C++ on
MVS!) I catch bad addresses.  I don't validate the pointer expressions.
My delete (and I presume the standard delete) simply gets an address.
My delete (and I presume the standard delete) knows about that address,
since it was the partner 'new' operator which handed it out, and I
presume that new and delete are somehow related.  Anyway, all I do is
say 'Hmm.  That address is not mine!'.  In that case, on MVS, I call a
system dump routine to see who gave it to me, and then I can debug that
call.  All I'm asking is for the standard delete to indicate that the
delete failed, not why it failed.  And I certainly wouldn't expect the
standard to mandate that a dump must somehow be provided.  I would like
to be able to test the return code from delete (or some other mechanism
to test for validity of the delte) and be able to see during code
development that something is amiss.  I think there is a precedent for
this kind of reaction in the C and C++=A0standards.  After all, even
printf has a return value.  I doubt if anyone uses it, but the standard
does say that the return value of printf is the number of characters
printed OR=A0A=A0NEGATIVE=A0VALUE=A0IF=A0THE=A0PRINT=A0FAILED (emphasis m=
ine).  Is
this to much to ask?

  C++ has adopted the C premise of allowing memory management to be
  as efficient as possible. If you make a programming error (delete
  twice, try to delete a bogus pointer value, etc), you are totally
  on your own. On the other hand, an implementation is allowed to
  validate all delete operations, and some provide such an option.
  Third-party tools that do the validation are also available. The
  efficiency loss for a program performing the checks is dramatic.

  Could the standard require that the effect of an improper delete-
  expression be implementation-defined? That would mean that the
  implementation would have to tell you what happens in every
  situation. If the implementation chooses to validate all delete-
  expressions, that is not a problem. If it doesn't validate all
  delete-expressions, there is no way it can predict what the result
  of an invalid delete-expression will be. The expression might trash
  some piece of data currently in use, or even part of an active stack

  frame, and all bets are off after that.

  Summary: You can't predict the result of an invalid delete unless
  you
  perform full validation of all delete-expressions, and the decision
  has been not to make that requirement because it is much too
  expensive. Thus, the effect of an invalid delete must remain
  undefined.
  ---
  Steve Clamage, stephen.clamage@eng.sun.com
  ---
  [ comp.std.c++ is moderated.  To submit articles: try just posting
  with      ]
  [ your news-reader.  If that fails, use
  mailto:std-c++@ncar.ucar.edu         ]
  [ FAQ:
  http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
  [ Policy:
  http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
  [ Comments?
  mailto:std-c++-request@ncar.ucar.edu                             ]



--
Kevin Mullin
kmullin@oz.net
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]