C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  new T[n], when n > (std::numeric_limits<std::size_t>::max()          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Falk Tannhäuser Guest Posted: Sun Aug 21, 2005 9:32 pm    Post subject: new T[n], when n > (std::numeric_limits<std::size_t>::max() According to § 5.3.4/10-12, the expression "new T[n]" results in the call of operator "new[](sizeof(T)*n + epsilon)", where epsilon is some implementation-dependent value representing array allocation overhead; while said operator has the form void* operator new[](std::size_t size) throw(std::bad_alloc); (§ 18.4.1.2). My question is what is supposed to happen when an overflow occurs in the expression "sizeof(T)*n + epsilon", i.e. when the result can't be represented within a std::size_t so that the rules of § 3.9.1/4 and 4.7/2 (reduction modulo 2^n) intervene. In my understanding of the Standard, the truncated result is passed to operator new[], typically yielding in allocation of insufficient space and thus, undefined behaviour when accessing to array elements beyond the actually allocated limit (which could already be done by the constructor of T). While this behaviour seems inconsistent with § 5.3.4/14 "Note: when the allocation function returns a value other than null, it must be a pointer to a block of storage in which space for the object has been reserved. The block of storage is assumed to be appropriately aligned and of the requested size. [...]" it seems what is implemented by GCC 3.4.4 Cygwin, so I get core dumps when trying to allocate too big arrays. Actually I get a warning "integer overflow in expression" when "n" is a compile time constant, but of course nothing in the general case. I can't imagine that I'm the first one to notice this problem. Is this just a bug in GCC or a Hole in the Holy Standard? Am I the only one to believe that it is not acceptable? Maybe I should post this to comp.std.c++ too... By the way, std::vector seems to suffer from an analogous problem. While § 23.2.4.2/4 requires reserve(n) to throw an exception std::length_error if n > max_size(), no such check seems to be required for other std::vector member functions capable of triggering a growth of the vector's capacity beyond its max_size() - was it left out intentionally or has it just been forgotten? std::basic_string doesn't seem to suffer from this problem as one can convince himself by searching the Standard's text for "length_error". Again, my GCC throws length_error only for reserve(), but not i.e. for resize() or when trying to construct a vector with too many elements, so core dumps occur in these cases. Falk [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Florian Weimer Guest Posted: Mon Aug 22, 2005 10:06 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma * Falk Tannhäuser: Quote: My question is what is supposed to happen when an overflow occurs in the expression "sizeof(T)*n + epsilon", i.e. when the result can't be represented within a std::size_t so that the rules of § 3.9.1/4 and 4.7/2 (reduction modulo 2^n) intervene. There's been some discussion on comp.std.c++ recently. It's also PR19351 for GCC. Quote: I can't imagine that I'm the first one to notice this problem. It's been known as a potential security problem for quite some time: <http://cert.uni-stuttgart.de/advisories/calloc.php> Quote: Is this just a bug in GCC or a Hole in the Holy Standard? This is not quite clear. Personally, I believe that GCC should throw std::bad_alloc when the allocated array would be smaller than expected. However, there is a group of people who claim that the standard does not allow throwing an exception in this case. It seems that it was discussed in the WG, and it was decided that this is not something the WG should care about. Quote: Am I the only one to believe that it is not acceptable? No, certainly not. While you shouldn't allocate unbounded amounts of memory, you also run into this problem if you use your own version of operator new (which could enforce a per-client memory limit, for example). The issue forces you to check all allocations manually. Unless this is fixed, I would even outlaw operator new[] completely. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Martin Bonner Guest Posted: Mon Aug 22, 2005 10:10 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Falk Tannhäuser wrote: Quote: According to § 5.3.4/10-12, the expression "new T[n]" results in the call of operator "new[](sizeof(T)*n + epsilon)", where epsilon is some implementation-dependent value representing array allocation overhead; while said operator has the form void* operator new[](std::size_t size) throw(std::bad_alloc); (§ 18.4.1.2). My question is what is supposed to happen when an overflow occurs in the expression "sizeof(T)*n + epsilon", The standard probably doesn't define what is supposed to happen. It seems to me that on any implementation you have invoked undefined behaviour by exceeding the implementation's resource limits (in this case, the maximum possibly size of an array object). [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Falk Tannhäuser Guest Posted: Mon Aug 22, 2005 2:47 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Martin Bonner wrote: Quote: Falk Tannhäuser wrote: My question is what is supposed to happen when an overflow occurs in the expression "sizeof(T)*n + epsilon", The standard probably doesn't define what is supposed to happen. It seems to me that on any implementation you have invoked undefined behaviour by exceeding the implementation's resource limits (in this case, the maximum possibly size of an array object). The problem is that - The average C++ programmer relies on new T[n] to throw std::bad_alloc, and new(std::nothrow) T[n] to return 0 when the implementation's resource limits are exceeded, and popular programming tutorials / guidelines rarely tell him that this is not sufficient and that testing n before allocating is necessary too, - Even for the not-so-average programmer scrupulous about avoiding any UB causing crashes, data corruption or security holes, there is no standard compliant way to know the implementation's maximum possibly size of a dynamically allocated array object, especially it is not specified how big the allocation overhead 'epsilon' may be (I would expect it to be sizeof(std::size_t) to memorize the number of destructors to be called on delete[], or perhaps 0 when said destructors are trivial, but one can't be sure), - Worse: std::vector - which is supposed to be a safer replacement for new[] - is not completely free from the problem neither (see my original posting) Falk [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Martin Bonner Guest Posted: Mon Aug 22, 2005 5:32 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Falk Tannhäuser wrote: Quote: Martin Bonner wrote: Falk Tannhäuser wrote: My question is what is supposed to happen when an overflow occurs in the expression "sizeof(T)*n + epsilon", The standard probably doesn't define what is supposed to happen. It seems to me that on any implementation you have invoked undefined behaviour by exceeding the implementation's resource limits (in this case, the maximum possibly size of an array object). The problem is that - The average C++ programmer relies on new T[n] to throw std::bad_alloc, and new(std::nothrow) T[n] to return 0 when the implementation's resource limits are exceeded, and popular programming tutorials / guidelines rarely tell him that this is not sufficient and that testing n before allocating is necessary too, - Even for the not-so-average programmer scrupulous about avoiding any UB causing crashes, data corruption or security holes, there is no standard compliant way to know the implementation's maximum possibly size of a dynamically allocated array object, especially it is not specified how big the allocation overhead 'epsilon' may be (I would expect it to be sizeof(std::size_t) to memorize the number of destructors to be called on delete[], or perhaps 0 when said destructors are trivial, but one can't be sure), - Worse: std::vector - which is supposed to be a safer replacement for new[] - is not completely free from the problem neither (see my original posting) As things stand, I think this is a "Quality Of Implementation" issue. I don't see how this could be regarded as a Defect that can be fixed with a DR. For C++0X, it would seem reasonable to specify the obvious behaviour. I think this is an issue for comp.std.c++. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Kanze Guest Posted: Mon Aug 22, 2005 5:34 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Falk Tannhäuser wrote: Quote: Martin Bonner wrote: Falk Tannhäuser wrote: My question is what is supposed to happen when an overflow occurs in the expression "sizeof(T)*n + epsilon", The standard probably doesn't define what is supposed to happen. It seems to me that on any implementation you have invoked undefined behaviour by exceeding the implementation's resource limits (in this case, the maximum possibly size of an array object). The only logical answer is that it should throw bad_alloc. I actually brought the point up in some forum some time ago. Since then, however, I've rethought about it, and while the only acceptable behavior I can think of is that the allocation should fail, it's tricky, since the expression is evaluated before the allocation function is called, but it is the allocation function which decides how to handle allocation failure (throw bad_alloc, return NULL, etc.). I can see two more or less good solutions, but both are really extensions: -- Require the compiler to call the allocation function with a special, must fail value (std::numeric_limits<size_t>::max(), for example. Note, however, that this could break working code, if a system could actually allocate std::numeric_limits<size_t>::max() bytes, and the application depended on it. -- Require the compiler to throw bad_alloc unless the allocation function has a throw() exception specifier, and return NULL otherwise. In the meantime, of course, it is impossible to write correct code using array new. Not that that bothers me much; I use std::vector instead, and in the case of std::vector, I don't think that there is any undefined behavior in this case (which puts some burden on the implementor, but since they won't use the new operator anyway, except for placement new, it's not that bad). Quote: The problem is that - The average C++ programmer relies on new T[n] to throw std::bad_alloc, and new(std::nothrow) T[n] to return 0 when the implementation's resource limits are exceeded, and popular programming tutorials / guidelines rarely tell him that this is not sufficient and that testing n before allocating is necessary too, I would hope that the "average" C++ programmer never uses new T[n]; now that we have std::vector, what's the point? (I know, there are a few exceptions. But IMHO, they're few enough that they shouldn't concern the "average" programmer.) Quote: - Even for the not-so-average programmer scrupulous about avoiding any UB causing crashes, data corruption or security holes, there is no standard compliant way to know the implementation's maximum possibly size of a dynamically allocated array object, especially it is not specified how big the allocation overhead 'epsilon' may be (I would expect it to be sizeof(std::size_t) to memorize the number of destructors to be called on delete[], or perhaps 0 when said destructors are trivial, but one can't be sure), Prepare to be disappointed. On most 32 bit machines, sizeof( size_t ) is 4, but any hidden overhead must be a multiple of 8 to ensure proper alignment for doubles. Although not guaranteed at all by the standard, I would expect it to be a constant value, always the same for all array new (for a given compiler). In which case, it is fairly easy to write a small program which will determine it, and add it to a system dependant header, e.g.: #define GB_ARRAY_ALLOCATION_OVERHEAD 8 Quote: - Worse: std::vector - which is supposed to be a safer replacement for new[] - is not completely free from the problem neither (see my original posting) IMHO, that's an error in the implementation. If n >= max_size(), the standard specifies what happens. And max_size() should be such that the problem cannot occur. -- James Kanze mailto: [email]james.kanze (AT) free (DOT) fr[/email] Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Howard Hinnant Guest Posted: Mon Aug 22, 2005 7:12 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma In article <8764tys90o.fsf (AT) mid (DOT) deneb.enyo.de>, Florian Weimer <fw (AT) deneb (DOT) enyo.de> wrote: Quote: It seems that it was discussed in the WG, and it was decided that this is not something the WG should care about. <nod> http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_closed.html#256 -Howard [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Kanze Guest Posted: Tue Aug 23, 2005 6:42 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Howard Hinnant wrote: Quote: In article <8764tys90o.fsf (AT) mid (DOT) deneb.enyo.de>, Florian Weimer <fw (AT) deneb (DOT) enyo.de> wrote: It seems that it was discussed in the WG, and it was decided that this is not something the WG should care about. nod http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_closed.html#256 The problem is that the rationale given in this statement is simply false. There is no way a user can possibly check. (Furthermore, of course, in general, if the user can know that the the check is not needed, so can the compiler.) The problem, of course, is that the compiler doesn't generally know what to do if there is overflow. Even in the case of a non-placement new, the defined behavior if the request cannot be met is to invoke the new_handler, if one is set. And of course, in the case of placement new, who knows how the user intends to report failure. It's not an easy issue, but it does more or less make array new pretty much unusable. -- James Kanze mailto: [email]james.kanze (AT) free (DOT) fr[/email] Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Florian Weimer Guest Posted: Tue Aug 23, 2005 6:46 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma * Falk Tannhäuser: Quote: - Even for the not-so-average programmer scrupulous about avoiding any UB causing crashes, data corruption or security holes, there is no standard compliant way to know the implementation's maximum possibly size of a dynamically allocated array object, especially it is not specified how big the allocation overhead 'epsilon' may be (I would expect it to be sizeof(std::size_t) to memorize the number of destructors to be called on delete[], or perhaps 0 when said destructors are trivial, but one can't be sure), Many implementation use commit-on-use instead of commit-on-alloc. This means that you might run into undefined behavior when you allocate large objects without proper error checking. Even with commit-on-use, you have to be careful to avoid resource exhaustion attacks. That's why I mention user-defined pool allocators in my other message. They can prevent such attacks even if attackers can request arbitrary amounts of memory (but have only access to very few pools), as long as the overflows are caught by the implementation. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Florian Weimer Guest Posted: Tue Aug 23, 2005 6:49 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma * Martin Bonner: Quote: As things stand, I think this is a "Quality Of Implementation" issue. Only if implementations are allowed to throw std::bad_alloc in this case. Since the arithmetic occurs in std::size_t, an unsigned type, you cannot claim undefined behavior thanks to integer overflow. So std::bad_alloc has to be thrown *after* a user-defined operator new has been called, if it can be called at all. This is not just a QoI issue, I fear. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Martin Bonner Guest Posted: Thu Aug 25, 2005 11:06 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Florian Weimer wrote: Quote: * Martin Bonner: As things stand, I think this is a "Quality Of Implementation" issue. Only if implementations are allowed to throw std::bad_alloc in this case. Since the arithmetic occurs in std::size_t, an unsigned type, you cannot claim undefined behavior thanks to integer overflow. I don't. I claim undefined behaviour for exceeding resource limits (section 1.4 paragraph 2, point 1 of the standard. See also Appendix B). Quote: So std::bad_alloc has to be thrown *after* a user-defined operator new has been called, if it can be called at all. This is not just a QoI issue, I fear. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Florian Weimer Guest Posted: Sat Sep 10, 2005 12:40 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma * Martin Bonner: Quote: Florian Weimer wrote: * Martin Bonner: As things stand, I think this is a "Quality Of Implementation" issue. Only if implementations are allowed to throw std::bad_alloc in this case. Since the arithmetic occurs in std::size_t, an unsigned type, you cannot claim undefined behavior thanks to integer overflow. I don't. I claim undefined behaviour for exceeding resource limits (section 1.4 paragraph 2, point 1 of the standard. See also Appendix B). This is a bit unsatisfactory for me. After all, any implementation could claim that the contingent of CPU cycles has been used up at any time during execution, and use it as a excuse to introduce undefined behavior at any point. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Martin Bonner Guest Posted: Tue Sep 13, 2005 12:39 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Florian Weimer wrote: Quote: * Martin Bonner: Florian Weimer wrote: * Martin Bonner: As things stand, I think this is a "Quality Of Implementation" issue. Only if implementations are allowed to throw std::bad_alloc in this case. Since the arithmetic occurs in std::size_t, an unsigned type, you cannot claim undefined behavior thanks to integer overflow. I don't. I claim undefined behaviour for exceeding resource limits (section 1.4 paragraph 2, point 1 of the standard. See also Appendix B). This is a bit unsatisfactory for me. After all, any implementation could claim that the contingent of CPU cycles has been used up at any time during execution, and use it as a excuse to introduce undefined behavior at any point. If you mean that you can get undefined behaviour because the OS terminates your process because it has exceeded it's time allocation, that's entirely correct. If you mean that there is some construct that the compiler doesn't generate correct code for and the implementation claims "whenever you encounter this construct, you will have exceeded your allocation of CPU cycles, and hence we can do what we like", I don't think that's right. On the other hand, resource limits do severly limit what you can rigorously imply about programs. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Allan W Guest Posted: Tue Sep 13, 2005 6:04 pm    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma James Kanze wrote: Quote: The only logical answer is that it should throw bad_alloc. [snip] while the only acceptable behavior I can think of is that the allocation should fail, it's tricky, since the expression is evaluated before the allocation function is called, but it is the allocation function which decides how to handle allocation failure (throw bad_alloc, return NULL, etc.). If the epsilon for a given implementation is fixed (and I imagine that most implementations work this way), then the standard library implementation could just fail for any allocation which is less than epsilon. Of course, this does nothing to help user-defined operator new's. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze Guest Posted: Wed Sep 14, 2005 9:49 am    Post subject: Re: new T[n], when n > (std::numeric_limits<std::size_t>::ma Allan W wrote: Quote: James Kanze wrote: The only logical answer is that it should throw bad_alloc. [snip] while the only acceptable behavior I can think of is that the allocation should fail, it's tricky, since the expression is evaluated before the allocation function is called, but it is the allocation function which decides how to handle allocation failure (throw bad_alloc, return NULL, etc.). If the epsilon for a given implementation is fixed (and I imagine that most implementations work this way), then the standard library implementation could just fail for any allocation which is less than epsilon. Of course, this does nothing to help user-defined operator new's. Any given implementation could easily arrange for some special value to trigger automatic failure when passed to operator new. The problem is, as you point out, user defined operator new's, either overloads or replacement functions. For this, the standard would have to define some sort of special value (e.g. std::numeric_limits< size_t >::max()). -- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.