27

In C/C++, addition or subtraction on pointer is defined only if the resulting pointer lies within the original pointed complete object. Moreover, comparison of two pointers can only be performed if the two pointed objects are subobjects of a unique complete object.

What are the reasons of such limitations?

I supposed that segmented memory model (see here §1.2.1) could be one of the reasons but since compilers can actually define a total order on all pointers as demonstrated by this answer, I am doubting this.

Oliv
  • 17,610
  • 1
  • 29
  • 72
  • AFAIK, pointer addition and substraction is portably defined for arrays only ... – Massimiliano Janes Dec 03 '17 at 08:12
  • regarding the linked answer, I don't see why he calls the existence of std::less a "giant loophole"; it just means that the *implementation* knows how to compute a total order (that's not surprising). The same thing applies to float's for example. – Massimiliano Janes Dec 03 '17 at 08:16
  • @MassimilianoJanes Its a giant loophole because there is no reason the builtin operators shouldn't behave like `std::less`. In the cases where it differs, it's because there is unspecified behaviour, and that is in no way useful. – Passer By Dec 03 '17 at 08:20
  • @MassimilianoJanes I have done a huge circumvolution around this fact (pointer arithmetic on array) to include the ininteresting case were we add 1 to a pointer to a non array element (because a single object is for pointer arithmetic considered an array of size 1). But I don't know how to rephrase it concisely. – Oliv Dec 03 '17 at 08:20
  • @PasserBy yes, but that "there is no reason the builtin operators shouldn't behave like std::less" is not implied by the mere existence of std::less as it seems that answer's doing. Consider, less, there *are* reasons for it to differ from "operator<(float)"... – Massimiliano Janes Dec 03 '17 at 08:25
  • @MassimilianoJanes Um... I meant for object pointers. – Passer By Dec 03 '17 at 08:25
  • @PasserBy This is exactly what is intriguing me. Maybe the reason is for compatibilty with antic pneumatic computers or maybe abacus ;) – Oliv Dec 03 '17 at 08:45
  • 2
    @oliv a reason could be that more UB enables more optimizations; consider *"int x[10];int\* py = x + j;"*, here the compiler could legally make assumptions on the range of *j* – Massimiliano Janes Dec 03 '17 at 08:48
  • 2
    @MassimilianoJanes Given the history of C and the usage of UB for optimization, I think it is very unlikely that optimization potential was the reason for any UB in C. – Sebastian Redl Dec 03 '17 at 08:54
  • @SebastianRedl ah I see (BTW, is the question more about *historical* reasons or *ex-post* ones ?); moreover, UB allows more optimizations on the compiler side, but may force programmers to write unportable code to write their owns. I'd still bet on the compiler, but who knows ... :) – Massimiliano Janes Dec 03 '17 at 09:42
  • @MassimilianoJanes The question is why we have this rules now? So from my point of you, your comment and the one of Sebastian Redl are complementaries: your comment gives one reason why we keep this limitation for pointer arithmetic; the comment of Sebastian Redls suggest that this may not be the original reason, and that there are still other(s) reason(s). – Oliv Dec 03 '17 at 10:13
  • @MassimilianoJanes on general case we hate the "optimizations" done around some baseless "undefined behavior" that should not be there – Öö Tiib Dec 03 '17 at 10:49
  • 3
    In a segmented architecture `pa - pb` will have more than one correct answer if the address architecture allows the segment address scheme to overlap. – Richard Critten Dec 03 '17 at 11:43
  • @RichardCritten, Reading your comment, I have thought that it would just require to convert a relative address to an absolute one. But may be it is impossible on some platefroms. Do you know plateforms on which an unprivilegied application could not retrieve the base address of a segment? – Oliv Dec 03 '17 at 13:34
  • 1
    It gives the runtime library authors a break. The more critical thing that a memory allocator needs to do is avoid the detrimental effects of heap fragmentation. One standard technique is to group allocations by object size, thus making it very likely that a hole left by a destroyed object can easily be reused. So the memory model is no longer a flat chunk of memory, it is a list of sub-heaps. Comparing pointers to objects that live in different sub-heaps is not meaningful. That access plays a role is a wonky rule from C++98, a cheap way to improve locality of reference. – Hans Passant Dec 03 '17 at 13:35
  • @Oliv Think about where the physical architecture is the segmented architecture and a location in memory may have more than one segment-offset address (due to segments being able to overlap) the 8086, 80286 have this memory architecture. Have a read of https://blogs.msdn.microsoft.com/oldnewthing/20171113-00/?p=97386 and other related info and be thankful we have moved on. – Richard Critten Dec 03 '17 at 13:56
  • 1
    @RichardCritten: that segment:offset pair can be converted to an absolute address, so pointer arithmetic and comparison can be easily defined. – geza Dec 03 '17 at 14:01
  • 4
    @oliv it would help if you(or anybody) could produce a *genuine* use-case where such relaxed requirements would turn out useful; imho, in order to be fair, such use-case should 1) apply to latest standard, 2) should *not* have an equivalent, portable solution, and 3) should *not* rely on any further undefined behavior. Only then, such use-cases could be meaningfully compared against the loss of generality that such decision would entail. – Massimiliano Janes Dec 03 '17 at 16:17
  • @MassimilianoJanes There the famous c++ big trouble: std::vectors can't be implemented using the language, surprise!! We do not have the right to perform pointer arithmetic on allocated memory! Take all implementations of std::vector, they all use UB! I am not going to talk about that, if I did it, nobody would focus any more on my question. Or just consider `std::vector::iterator`, it is just a wrapper around a pointer to the value type, when one makes a comparison of to iterators, one compares pointers to objects that do not belong to any array, so this is UB according to the standard. – Oliv Dec 03 '17 at 16:23
  • @oliv I know, that's why I added 3); in order to write vector<> you need **more** undefined behaviour ! see for example [p0532r0](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0532r0.pdf); so, it's not a fair example imho – Massimiliano Janes Dec 03 '17 at 16:37
  • @MassimilianoJanes From my point of view, this is more a mistake in the design of allocators, `allocator::construct` should return the pointer to the constructed object. And this UB only applies when elements have a const or ref member no? But there are lot of UB here. – Oliv Dec 03 '17 at 16:50
  • @MassimilianoJanes If pointer arithmetic and pointer comparison where not that limited, and without this UB which originate in a design mistake of (misnamed) allocators, I know vectors and many other usefull containers, can be implemented without any UB. We can even do system (kernel) programming in c++ ;) – Oliv Dec 03 '17 at 16:58
  • 4
    @PasserBy Regarding std::less and the builtin operators, there are very good reasons for them to behave differently. For effieciency the builtin comparison operators should be allowed to use the architectures natural comparison instructions and because of things segmented addressing or multiple address spaces it may not be possible to implement a total order of pointers this way. For std::less, a total order is more important than efficiency and it is ok to do extra work to handle memory segments and address spaces. – Johan Dec 04 '17 at 20:51
  • @Johan That would be a valid argument only if it were _implementation defined_ behaviour, like integer sizes and such. – Passer By Dec 05 '17 at 01:00
  • Giving a historically accurate answer might involve looking through the records, archives, etc of the C standards committee. – Krazy Glew Dec 06 '17 at 06:17
  • 1
    I do know that optimization was relevant to the standards body almost as soon as standardization began. The optimization impediments were introduced earlier. – Krazy Glew Dec 06 '17 at 06:19
  • 1
    If you can compare 2 pointers and remember the result, it constrains thongs like garbage collection. Yes, C/C++ is not garbage collected. But C/C++ can be GC’ed - witness the Boehm conservative GC. BTW Hans Boehm has been quite influential in C and C++, esp in memory model. – Krazy Glew Dec 06 '17 at 06:25
  • @KrazyGlew: One of the great tragedies of C (which in turn impacted C++) is that the authors of the Standard failed to distinguish between actions for which quality implementations should seek to define and uphold the same behavior (or at least a predictable range of behaviors) when practical, versus those where no implementations should be particularly expected to behave predictably. I think the authors wanted to avoid branding some implementations as "inferior", and expected that programmers and compiler writers would find it obvious which actions should fall into which category, – supercat Dec 08 '17 at 20:47
  • @Oliv • note that `p + i` is valid for `0 ≤ i ≤ n`. Even though p[n] cannot be accessed, it is a valid pointer (not UB). – Eljay Dec 11 '17 at 15:34
  • @KrazyGlew: It is not possible for a single language to guarantee that all the features needed for all purposes will be available, without guaranteeing things some otherwise-useful execution platforms would be unable to support. The Standard would be much more useful if it could recognize categories of implementations that make (or do not make) various guarantees, rather than ignoring any features that shouldn't be mandated on all implementations. – supercat Dec 12 '17 at 19:38
  • @supercat: so, what capabilities does outside-of-object pointing get you? that you don’t get from putting your objects all inside a struct, and using pointer to member? – Krazy Glew Dec 13 '17 at 03:56
  • @KrazyGlew: For starters, how about the ability to use things that aren't of static or automatic duration on a freestanding implementation that doesn't include `malloc()`? I'd say that's pretty important. Further, C has never had a special syntax for "pointer to an object within an array of `T`" (as opposed to "pointer to a standalone object of type `T`"), and so the ability to use a `T*` as the former has always been fundamental. Another thing to consider is that in C89, given `struct s {int x[4],y[4];}; int test(struct s*p, int idx) { if (!p->y[0]) p->x[idx]++; return p->y[0]); }`, ... – supercat Dec 13 '17 at 16:16
  • ...if such a function was called from code that did e.g. `int hey(void) union { struct s ss; int arr[8];} u={0}; return test(&u.ss,4);}` and `sizeof u == u.ss`, behavior would have been defined since `p->x` within `test` would be a pointer to hey's `u->arr`. If one presumes that a compiler will generate code for `test` should work correctly with all callers, that would imply how `test` must behave in the case where `idx` is 4. Being able to have a function that can e.g. treat a struct such as the above as a sequence of eight integers (rather than having to handle `x` and `y` separately)... – supercat Dec 13 '17 at 16:27
  • ...can be useful, but C never specified a syntax for such purpose [IMHO, an easy way of doing so would be to say that applying `[]` to an array type was limited to accessing items within the array, but applying `+` to a decomposed pointer would not be thus limited]. – supercat Dec 13 '17 at 16:28

7 Answers7

13

The reason is to keep the possibility to generate reasonable code. This applies to systems with a flat memory model as well as to systems with more complex memory models. If you forbid the (not very useful) corner cases like adding or subtracting out of arrays and demanding a total order on pointers between objects you can skip a lot of overhead in the generated code.

The limitations imposed by the standard allows the compiler to make assumptions on pointer arithmetic and use this to improve quality of the code. It covers both computing things statically in the compiler instead of at runtime and choosing which instrutions and addressing modes to use. As an example, consider a program with two pointers p1 and p2. If the compiler can derive that they point to different data objects it can safely assume that any no operation based on following p1 will ever affect the object pointed to by p2. This allows the compiler to reorder loads and stores based on p1 without consider loads and stores based on p2 and the other way around.

Johan
  • 3,667
  • 6
  • 20
  • 25
  • With flat memory model, I believe there are just no overhead. On segmented memory model, because compilers know to which segment belongs each pointer at compile time, they can generate the optimal code for pointers on the same segment and less optimal for pointers not belonging to the same segment. Could you develop on the "a lot of overhead"? – Oliv Dec 08 '17 at 11:30
  • @oliv This is not true in general, even with a flat memory model the ub-rules allows the compiler to make assumptions on pointer arithmetic and by that improve the quality of the code. It relates both to computing things statically in the compiler instead of at runtime and to which instructions to choose. – Johan Dec 08 '17 at 12:05
  • 1
    @Johan: can you give an example? – geza Dec 08 '17 at 12:32
  • 1
    @geza: As a simple example, consider `int foo[10],bar[10],x; ... if (bar[0]) foo[x]++; return bar[0];`. Should a compiler have to reload `bar[0]` after incrementing `foo[x]` to allow for the possibility that `foo+x == bar`? – supercat Dec 08 '17 at 20:56
  • @supercat, modulo arithmetic only applies to unsigned, it is supecified specificaly in the standard, while non signed does not use modulo arithmetic. There are no reason to specify that pointer arithmetic should follow modulo arithmetic. So the compiler will never take into incount this case whatsoever. – Oliv Dec 12 '17 at 09:49
  • @Oliv: No need for modular artithmetic. If the distance between `foo` and `bar` happened to equal `x`, then `foo+x` and `bar` would identify the same storage. In some kinds of system programming, it may be important for compilers to recognize such possibilities [especially with objects declared `extern`, which might e.g. have been forced by the linker to be placed at the beginning and end of unused (and available) storage.] – supercat Dec 12 '17 at 15:54
  • Indeed I did not read well your comment! So the trouble is pointer / array conversion ! – Oliv Dec 12 '17 at 20:12
  • @oliv No, the problem is increased pointer aliasing. If arbitrary pointer arithmetic is allowed the compiler can not assume that the operation `*(foo + x)++` will not affect `*bar`. With the current rules this is a valid assumption since if `foo + x` contains the same address as `bar` then the program is undefined and anything goes. – Johan Dec 12 '17 at 20:59
  • 1
    But the compilers are going to assume that these two expressions may alias in almost all cases. Think about a function that take as argument two pointer to the same type, if you do not want the compiler to alias the expression above, you need to declare one "restrict". The only situation where compilers can infer that these two expressions are not aliading is when the compiler can deduce the original array of these pointers, that is when the arrays are declared in the direct context of these expressions. So this rule just do not help! – Oliv Dec 12 '17 at 22:38
  • @Oliv: I think the main situation the rule is intended to help could best be supported by recognizing the use of `someArrayLvalue[x]` or `&(someArrayLvalue[x])` as having a more limited meaning than `*(someArrayLvalue+x)` or `(someArrayLvalue+x)`, with the former only having defined behavior of `x` is non-negative and is less than the number of elements in `someArrayLvalue`, and the latter also being defined if `someArrayLvalue` is contained within a larger object and the resulting address would be part of *that*. – supercat Jul 11 '18 at 21:55
  • @Oliv: Both operations are useful, and I think it's crazy that rather than recognize ways of specifying each, the Standard simply ignores the latter despite the fact that it is indispensible in many kinds of low-level or systems programming. – supercat Jul 11 '18 at 21:56
10

You only prove that the restriction could be removed - but miss that it would come with a cost (in terms of memory and code) - which was contrary to the goals of C.

Specifically the difference needs to have a type, which is ptrdiff_t, and one would assume it is similar to size_t.

In a segmented memory model you (normally) indirectly have a limitation on the sizes of objects - assuming that the answers in: What's the real size of `size_t`, `uintptr_t`, `intptr_t` and `ptrdiff_t` type on 16-bit systems using segmented addressing mode? are correct.

Thus at least for differences removing that restriction would not only add extra instructions to ensure a total order - for an unimportant corner case (as in other answer), but also spend double the amount of memory for differences etc.

C was designed to be more minimalistic and not to force compiler to spend memory and code on such cases. (In those days memory limitations mattered more.)

Obviously there are also other benefits - like the possibility to detect errors when mixing pointers from different arrays. Similarly as mixing iterators for two different containers is undefined in C++ (with some minor exceptions) - and some debug-implementations detect such errors.

Hans Olsson
  • 11,123
  • 15
  • 38
  • So there is a limitation due to the difference type. But why limiting to the size of the complete object in which is originaly pointing the pointer? – Oliv Dec 08 '17 at 18:32
  • @Oliv Because there are systems that can have different kinds or segments of memory, where pointers into one kind of memory looks entirely different from the other kinds of memory, and there does not exist an good way to compare pointers to different kinds of memory - at least not without adding huge cost to every kind of pointer comparison (i.e. each comparison would need to first figure out what kind of memory it is and then carry that information alongside all pointers). So, not all systems provide a flat address space where the memory address is a simple unique number. – nos Dec 08 '17 at 18:42
  • @nos The information is carried somehow because without it, it would be impossible to dereference a pointer. For example, a function declared `void f(int* p)` should in any case be able to derefence `p`. So a `int*` must hold all the information (address space, segment, relative address). Or maybe, far and huge pointer had different types? – Oliv Dec 08 '17 at 19:00
  • Don't forget banked memory (https://en.wikipedia.org/wiki/Bank_switching)... banked architectures were popular back when C was being invented. Pointers in different banks simply can not be compared with each other in any sane manner. I've seen bank pages as small as 512 (two-byte) words (C would never work on such) and as large as 8K (two byte) words which did support compilers. Likely larger banks were out there but I never used them. – Gilbert Dec 09 '17 at 13:32
  • @Oliv, far and huge pointers were different types (or different type-prefixes or...). Comparing them would for me be similar to comparing map::iterator and vector::iterator (and not only between iterators from different vectors). Defining a total order would be possible for such cases, but in more than 99.99% of cases it is a mistake and detecting that is more helpful. – Hans Olsson Dec 12 '17 at 10:57
  • @HansOlsson My question was not about segmented memory model, but why arithmetic is limited to fall within an object. In the country I am living, I have taken the habit to ask a question and then propose something wrong because Frenches love contradictive debate. So the best way to get an answer is to stimulate a contradictive answer. Unfortunatly that has not work here, poeple have forgotten the answer, and have told about what they knew about segmented memory model. Unfortunate inter-cultural misunderstanding. – Oliv Dec 12 '17 at 11:10
  • As I see it there are two parts to why arithmetic is limited within to within one object: performance and diagnostics. They go together, and without convincing use-cases it is then a matter of paying extra to be able to be able to shoot yourself in the foot. That's why we still have the restriction - even with linear address space. – Hans Olsson Dec 12 '17 at 11:23
10

There are architectures where program and data spaces are separated, and it's simply impossible to subtract two arbitrary pointers. A pointer to a function or to const static data will be in a completely different address space than a normal variable.

Even if you arbitrarily supplied a ranking between different address spaces, there's a possibility that the diff_t type would need to be a larger size. And the process of comparing or subtracting two pointers would be greatly complicated. That's a bad idea in a language that is designed for speed.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • I understand thanks to you, that the pointer could not go out of its address space. But why the arithmetic is allowed only within the boundary of an array, why not allowing arithmetic on all the address space? – Oliv Dec 08 '17 at 18:38
  • 1
    @Oliv the standard doesn't have any concept of address spaces. It doesn't even assume the existence of a stack and a heap, even though everybody has them. The only way to specify the limitation in a way that makes sense is to do it in terms of an object or array. – Mark Ransom Dec 08 '17 at 19:14
  • Thank you this is exactly what I expected after I read your answer :). – Oliv Dec 08 '17 at 19:16
  • 1
    Note: program and data spaces are separated example: [Harvard architecture](https://en.wikipedia.org/wiki/Harvard_architecture). – chux - Reinstate Monica Dec 08 '17 at 20:14
3

The rationale is that some architectures have segmented memory, and pointers to different objects may point at different memory segments. The difference between the two pointers would then not necessarily be something meaningful.

This goes back all the way to pre-standard C. The C rationale doesn't mention this explicitly, but it hints at this being the reason, if we look where it explains the rationale why using a negative array index is undefined behavior (C99 rationale 5.10 6.5.6, emphasis mine):

In the case of p-1, on the other hand, an entire object would have to be allocated prior to the array of objects that p traverses, so decrement loops that run off the bottom of an array can fail. This restriction allows segmented architectures, for instance, to place objects at the start of a range of addressable memory.

Lundin
  • 195,001
  • 40
  • 254
  • 396
  • Almost, so why if they had allowed `p-1` (without allowing its deferencement) segmented architecture would not habe been allowed to place an object at the start of a range of addressable memory? – Oliv Dec 08 '17 at 17:58
  • @Oliv • I'm speculating, but maybe because decrementing C008:0000 becomes C008:FFF0 (for an array of something that takes 16-bytes per something), and that wrap-around would be tricky to handle (i.e., necessitating extra code, slower speed). Are segmented architectures still around? – Eljay Dec 11 '17 at 20:58
  • 1
    @Eljay: On an 8086 real mode compiler, subtracting one from 0xC008:0 would yield 0xC008:0xFFFF. Bizarrely enough, this behavior is actually very useful, since it means that objects larger than 32K can be handled using 16-bit arithmetic. A pointer to a 50,000-byte object will have a segment part that is less than 15536. If one tries to add 40,000 to it, that value will get converted to -25536 by integer wraparound, but adding -25536 to a pointer whose segment part is less than 15536 will add 40000 to the segment part. – supercat Jul 11 '18 at 21:48
2

Since the C standard intends to cover the majority of processor architectures, it should also cover this one: Imagine an architecture (I know one, but wouldn't name it) where pointers are not just plain numbers, but are like structures or "descriptors". Such a structure contains information about the object it points into (its virtual address and size) and the offset within it. Adding or subtracting a pointer produces a new structure with only the offset field adjusted; producing a structure with the offset greater than the size of the object is hardware prohibited. There are other restrictions (such as how the initial descriptor is produced or what are the other ways to modify it), but they are not relevant to the topic.

Sergey Barannikov
  • 328
  • 1
  • 6
2

In most cases where the Stanadrd classifies an action as invoking Undefined Behavior, it has done so because:

  1. There might be platforms where defining the behavior would be expensive. Segmented architectures could behave weirdly if code tries to do pointer arithmetic that extends beyond object boundaries, and some compilers may evaluate p > q by testing the sign of q-p.

  2. There are some kinds of programming where defining the behavior would be useless. Many kinds of code can get by just fine without relying upon forms of pointer addition, subtraction, or relational comparison beyond those given by the Standard.

  3. People writing compilers for various purposes should be capable of recognizing cases where quality compilers intended for such purposes should behave predictably, and handling such cases when appropriate, whether or not the Standard compels them to do so.

Both #1 and #2 are very low bars, and #3 was thought to be a "gimme". Although it has become fashionable for compiler writers to show off their cleverness by finding ways of breaking code whose behavior was defined by quality implementations intended for low-level programming, I don't think the authors of the Standard expected compiler writers to perceive a huge difference between actions which were required to behave predictably, versus those where nearly all quality implementations were expected to behave identically, but where there it might conceivably be useful to let some arcane implementations do something else.

supercat
  • 77,689
  • 9
  • 166
  • 211
1

I would like to answer this by inverting the question. Instead of asking why pointer addition and most of the arithmetic operations are not allowed, why do pointers allow only adding or subtracting an integer, post and pre increment and decrement and comparison (or subtraction) of pointers pointing to the same array? It is to do with the logical consequence of the arithmetic operation. Adding/subtracting an integer n to a pointer p gives me the address of nth element from the currently pointed element either in the forward or reverse direction. Similarly, subtracting p1 and p2 pointing to the same array gives me the count of elements between the two pointers. The fact (or design) that the pointer arithmetic operations are defined consistent with the type of variable it is pointing to is a real stroke of genius. Any operation other than the permitted ones defies programming or philosophically logical reasoning and therefore is not allowed.

Seshadri R
  • 1,192
  • 14
  • 24
  • Actualy, my question originate on the fact that these rules does not allow to implement an efficient vector, or a colony without UB. Unfortunatly, we use pointer to identify memory location too. – Oliv Dec 10 '17 at 21:21
  • @oliv What do you mean by "colony" in this context? – zwol Dec 11 '17 at 15:46
  • @zwol like the one of boost or plf. – Oliv Dec 11 '17 at 16:17
  • @oliv I don't know what that is, and searches do not bring it up. Do you have a specific URL for the thing you're talking about? – zwol Dec 11 '17 at 16:25
  • @zwol indeed google need these 3 words to find related results (boost cpp colony), it need to understand that you are making a search in the "coder" context. – Oliv Dec 12 '17 at 09:46
  • @Oliv When I do that search I get a lot of stuff about ant-colony optimization algorithms. I doubt this is what you are getting; you seem to be talking about a data structure. Please provide a *specific URL* for the thing you are talking about. – zwol Dec 12 '17 at 13:03
  • Are you kidding me, I have just done the search with different google regio's, it just works fine! duckduck go, the 17'th link! – Oliv Dec 12 '17 at 13:48
  • @Oliv No I was not kidding, and I don't understand why you don't want to give actual links to the things you are talking about. Links are reliable. Search keywords are not reliable. – zwol Dec 13 '17 at 12:56