Hello Tim, Let me quote from stringobject.c the "heartbreaking code such as string_repeat's": nbytes = size * sizeof(char); if (nbytes / sizeof(char) != (size_t)size || nbytes + sizeof(PyStringObject) <= nbytes) <OverflowError> op = (PyStringObject *) PyObject_MALLOC(sizeof(PyStringObject) + nbytes); if (op == NULL) <MemoryError> With the proper macro, the whole code above can be written as: nbytes = Py_MUL_ADD(size, sizeof(char), sizeof(PyStringObject)); op = (PyStringObject *) PyObject_MALLOC(nbytes); if (op == NULL) <MemoryError> which seems much cleaner to me. For this reason I do not believe it is a good idea here to define a macro a la Zope C: DO_MULADD_OR(nbytes, size, sizeof(char), sizeof(PyStringObject), goto Overflow); for two reasons: there is no real need for a special "Overflow" case, as long as the returned 'nbytes' is guaranteed to be un-malloc-able; besides, no existing macro (e.g. _PyObject_VAR_SIZE) can support an extra "goto Overflow" case without breaking C code that depends on it. There is however a difference between the two above code fragments, in that the former will raise an OverflowError for "really too large values" and a MemoryError for "reasonable value but still too large for me to allocate right now". Whether this is a correct behavior is debatable. I would argue that raising MemoryError in both cases is fine: after all, "123"*9999999999999999 could be perfectly fine in another Python implementation with lazy strings. It is thus only a memory limit that makes this fail in the current implementation. Note that if we define MAX_SIZE to ((size_t)-1), the overflow check in the present stringobject.c could be more efficiently written down as: if (size > (MAX_SIZE - sizeof(PyStringObject)) / sizeof(char)) <OverflowError> where everything at the right of '>' reduces to a compile-time constant. The Py_MUL_ADD macro can be implemented with this idea in mind, which works best if the 2nd and 3rd arguments are constants.

note that anything/non_constant can be incredibly expensive!

Yes. Couldn't a better overflow-checking algorithm be designed for these cases? For example, to multiply the non-constants 'a' and 'b', we can be sure that there is no overflow if both 'a' and 'b' are small enough (which is the common case anyway). I believe I can even think about a single Py_MUL_ADD macro that is as efficient as above with constant arguments, and otherwise uses this trick. About using 64-bit computations everywhere (as suggested by Christian): if the length of objects (e.g. lists) is still constrained to 31 bits, then it's fine; otherwise, the problem is the same. Do all supported 64-bit platforms have a 32-bit 'int', and thus a 31-bit limit on object lengths? By the way, this makes me think of a good efficient overflow-detection method for platforms with a "long long" type longer than size_t: unsigned long long bytes = ((unsigned long long)a)*((unsigned long long)b)+c; if (bytes > ((size_t)-1)) <overflow>; This compiles to very good assembly code on x86. Mmmh, in summary I would recommend that we define a common "multiply-and-add" macro, returning a size_t or OVERFLOW_VALUE in case of overflow, which is implemented in several different ways on different platforms, as selected by #if's. The same macro is used for just "multiply" or just "add" by relying on the compiler's strengh reduction. Armin

[Armin Rigo]

Let me quote from stringobject.c the "heartbreaking code such as string_repeat's":

nbytes = size * sizeof(char); if (nbytes / sizeof(char) != (size_t)size || nbytes + sizeof(PyStringObject) <= nbytes) <OverflowError> op = (PyStringObject *) PyObject_MALLOC(sizeof(PyStringObject) + nbytes); if (op == NULL) <MemoryError>

With the proper macro, the whole code above can be written as:

nbytes = Py_MUL_ADD(size, sizeof(char), sizeof(PyStringObject)); op = (PyStringObject *) PyObject_MALLOC(nbytes); if (op == NULL) <MemoryError>

which seems much cleaner to me.

It's not the appearance of the code that breaks my heart (although it doesn't cheer it either <wink>), it's that when we "fix" one of these things that pops up in real life, we add a pile of expensive tests and branches to code that's been known to fall over only once in 10 years. So Python gets bigger and slower for everyone, and half the time there's no real cause beyond that some wiener is playing "let's try to break it!".

For this reason I do not believe it is a good idea here to define a macro a la Zope C:

DO_MULADD_OR(nbytes, size, sizeof(char), sizeof(PyStringObject), goto Overflow);

for two reasons: there is no real need for a special "Overflow" case,

I don't know. It depends on context, such as how many times a potential overflow can occur within a single routine. Probably not often on average.

as long as the returned 'nbytes' is guaranteed to be un-malloc-able;

There is no nbytes that's guaranteed to bu un-malloc-able, unless you're going to impose artificial restrictions on malloc. It's not a happy thing to burden our malloc wrappers with another layer of test-and-branch either.

besides, no existing macro (e.g. _PyObject_VAR_SIZE) can support an extra "goto Overflow" case without breaking C code that depends on it.

Cool: yet another reason to leave things alone <wink>.

There is however a difference between the two above code fragments, in that the former will raise an OverflowError for "really too large values" and a MemoryError for "reasonable value but still too large for me to allocate right now". Whether this is a correct behavior is debatable.

Some things aren't worth debating, though -- it doesn't matter to me which exception we raise.

I would argue that raising MemoryError in both cases is fine:

Fine by me too.

after all, "123"*9999999999999999 could be perfectly fine in another Python implementation with lazy strings. It is thus only a memory limit that makes this fail in the current implementation.

Note that if we define MAX_SIZE to ((size_t)-1), the overflow check in the present stringobject.c could be more efficiently written down as:

(size_t)~0UL is safer, although there's really no wholly safe way to spell the intent in C89.

if (size > (MAX_SIZE - sizeof(PyStringObject)) / sizeof(char)) <OverflowError>

where everything at the right of '>' reduces to a compile-time constant. The Py_MUL_ADD macro can be implemented with this idea in mind, which works best if the 2nd and 3rd arguments are constants.

...

note that anything/non_constant can be incredibly expensive!

Yes. Couldn't a better overflow-checking algorithm be designed for these cases? For example, to multiply the non-constants 'a' and 'b', we can be sure that there is no overflow if both 'a' and 'b' are small enough (which is the common case anyway). I believe I can even think about a single Py_MUL_ADD macro that is as efficient as above with constant arguments, and otherwise uses this trick.

And more tests, and more branches. Life will be much easier if we can limit it to size_t thingies (which have the same size, and are unsigned0.

About using 64-bit computations everywhere (as suggested by Christian): if the length of objects (e.g. lists) is still constrained to 31 bits, then it's fine; otherwise, the problem is the same. Do all supported 64-bit platforms have a 32-bit 'int', and thus a 31-bit limit on object lengths?

No. For example, some now-rare models of Cray boxes have no 32-bit types. If 64-bit machines really are the wave of the future (I started using them in the late 1970's, and am still waiting for the revolution <0.9 wink>), it's no cure anyway, as Python in a truly 64-bit world will have to lose its 2GB-bounded of the world (as it's already painfully doing for files, and maybe for mmaps). Then the "detect overflow" problem returns with a vengeance.

By the way, this makes me think of a good efficient overflow-detection method for platforms with a "long long" type longer than size_t:

unsigned long long bytes = ((unsigned long long)a)*((unsigned long long)b)+c; if (bytes > ((size_t)-1)) <overflow>;

This also implicitly assumes that: 1. size_t is no wider than an int; that's the kind of thing the "(size_t)~0UL would be safer" comment above was getting at. 2. long long is at least twice as wide as size_t.

This compiles to very good assembly code on x86.

Mmmh, in summary I would recommend that we define a common "multiply-and-add" macro, returning a size_t or OVERFLOW_VALUE in case of overflow, which is implemented in several different ways on different platforms, as selected by #if's. The same macro is used for just "multiply" or just "add" by relying on the compiler's strengh reduction.

What a PITA. Is it worth it? If I don't have to do it, maybe <wink>. BTW, when we allocate an object that participates in cyclic GC, there's Yet Another little integer that gets added to the total size (to reflect the "extra header" bytes unique to GC'ed objects), and so there's Yet Another place potential overflow may go uncaught now.

[Guido]

... I currently use something like this as the overflow test in a few places:

if (src1 && destination / src1 != src2)

but as Tim points out the division can kill us unless src1 is a constant... How would you spell this without doing a division?

Armin answered that in the case there's an efficient "unsigned long long" type at least twice the width of the inputs. Then you just do the product in the fat precision and see whether any of the upper-half bits are set. As a pragmatic matter, 2/5ths of that trick can work "most of the time": #define YOWZA (sizeof(size_t) * 4U) if ((src1 | src2} >> YOWZA) hard to tell else overflow is impossible would get out quick in *most* non-overflow cases. The fast path there succeeds if and only if both inputs are at most "half full". For example, in string * int it's rare that len(string) >= 64K or int >= 64K. For what to do in the other half, see the history of subtly buggy attempts to detect overflow quickly in Python's int * int code. Without a double-width type to fall back on, I think it's impossible to do this both correctly and quickly. BTW, if we know we're not interested in anything other than 32-bit products, double _prod = (double)src1 * (double)src2; if (_prod < 4294967296.0) /* 2**32 */ result = (size_t)_prod; else overflow; does the trick reliably on all platforms I know of -- although not all Python platforms support floating-point efficiently! It's a good puzzle <wink>.

[Scott Gilbert]

The following is really ugly (until you put it in a macro), but would work:

#define HALF_BITS (sizeof(size_t) * 4U) #define LO_MASK ((((size_t)1) << HALF_BITS)-1) #define HI_MASK (LO_MASK<

if ( /* Tim's fast path */ ((src1 | src2) & HI_MASK) && ( /* Ugly slower path */ (((src1&LO_MASK) * (src2>>HALF_BITS)) & HI_MASK) | (((src1>>HALF_BITS) * (src2&LO_MASK)) & HI_MASK) | (src1>>HALF_BITS) * (src2>>HALF_BITS)) ) { goto overflow; }

I'll repeat that it's hard to do this correctly and quickly (c.f. earlier comments about the history of Python's subtly buggy attempts). This kind of approach is viewing src1 and src2 as 2-digit numbers in base X = 2**HALF_BITS: src1 = A*X + B src2 = C*X + D then viewing their product as highpart: A*C*X**2 + xxxxxxxx middlepart1: A*D*X + xxxxxxxx middlepart2: B*C*X + xxxxxxxx lowpart: B*D xxxxxxxx ---------------- xxxxxxxxxxxxxxxx <danger>< safe > Your second line checks whether the high half of middlepart2 is 0; your third line whether the high half of middlepart1 is 0; your last line whether highpart is 0. But they can all be 0 and *still* have overflow: the sum low half of middlepart1 + low half of middlepart2 + high half of lowpart can carry over into the <danger> zone. Supposing we were looking at 16-bit products, here's an example: 0x01ff * 0x00ff ------ 0000 00ff 0000 fe01 -------- 0001fd01 ^ oops Hint: before posting something like this, prototype it in Python, and do an exhaustive check of all possible pairs of multiplicands in an artificially small base. Very few buggy algorithms survive that, even for very small artificial bases.

Tim Peters :

I'll repeat that it's hard to do this correctly and quickly (c.f. earlier comments about the history of Python's subtly buggy attempts).

The really tragic thing about all this is that most machines have perfectly good facilities for detecting overflow at the machine level, but no commonly used HLL that I know of provides access to them, for some unfathomable reason. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

if we know we're not interested in anything other than 32-bit products,

double _prod = (double)src1 * (double)src2; if (_prod < 4294967296.0) /* 2**32 */ result = (size_t)_prod; else overflow;

does the trick reliably on all platforms I know of -- although not all Python platforms support floating-point efficiently!

I like this one, as well as the one using 64-bit precision. I wonder if we could collect a bunch of different macros and make them tunable for different platforms? (Including a "don't check for overflow" version for people who wanna play fast and loose. :-) The trick will to ensure that the macro arguments are used exactly once in all versions (otherwise switching macros might unveal a new class of bugs). Apart from *how* to check, there's a variety of cases depending on the types of the input and output variables. There's the ob_size calculation for sequence repeat, which takes a C int and a C long and should return something that fits in a C int; and there's the malloc size calculation for various ones, which should take an int and a (small constant) size_t and return a size_t. So maybe we need two macros: one for int*long->int, and one for int*size_t->size_t? With several different implementations, chosen by configure. But first we'd have to see of there are enough places to benefit from such elaborate machinery. There are also additions, usually of small constants, which generally operate on the size_t. These are easier to test: if you add a small positive constant to a size_t, and the result is smaller than the original size_t, an overflow occurred. Similar for plain ints. So I'm not sure we need much help with these. --Guido van Rossum (home page: http://www.python.org/~guido/)

Hello Guido, On Tue, 15 Oct 2002, Guido van Rossum wrote:

I like this one, as well as the one using 64-bit precision. I wonder if we could collect a bunch of different macros and make them tunable for different platforms?

Doable. I experimented with some macros that do (unsigned int)*(unsigned int)->size_t, where the macro to use is selected according to #if's based on the relative size of int, long and long long.

(...) The trick will to ensure that the macro arguments are used exactly once in all versions (otherwise switching macros might unveal a new class of bugs).

Harder...

Apart from *how* to check, there's a variety of cases depending on the types of the input and output variables.

True as well... Why are C macros so limited?...

There are also additions, usually of small constants, which generally operate on the size_t.

If we are sure these are small, we can just add without any check if we reserve a whole range of values for "overflow", e.g. ((size_t)~0x7fff) to ((size_t)~0). Not too clean however. Armin

On Tue, Oct 15, 2002 at 01:29:36AM -0400, Tim Peters wrote:

BTW, if we know we're not interested in anything other than 32-bit products,

double _prod = (double)src1 * (double)src2; if (_prod < 4294967296.0) /* 2**32 */ result = (size_t)_prod; else overflow;

s/_prod;/src1 * src2;/ Re-calculating the product with integer multiplication is probably faster than converting a double to integer on any sane CPU. I wonder if the old SPARCs that don't have an integer multiply instruction actually have a floating point to integer conversion that is faster than integer mul. Wasting "expensive" multiplications this way still feels blasphemous :) Oren

Re-calculating the product with integer multiplication is probably faster than converting a double to integer on any sane CPU.

Um... what would be "sane" about that? I don't know much about the Pentium. I do know that the PowerPC doesn't have any way of moving a value from a float to an integer register without going through memory... but I regard that as a decidedly INsane feature! Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+