What memory address spaces are there?

Question

What forms of memory address spaces have been used?

Today, a large flat virtual address space is common. Historically, more complicated address spaces have been used, such as a pair of a base address and an offset, a pair of a segment number and an offset, a word address plus some index for a byte or other sub-object, and so on.

From time to time, various answers and comments assert that C (or C++) pointers are essentially integers. That is an incorrect model for C (or C++), since the variety of address spaces is undoubtedly the cause of some of the C (or C++) rules about pointer operations. For example, not defining pointer arithmetic beyond an array simplifies support for pointers in a base and offset model. Limits on pointer conversion simplify support for address-plus-extra-data models.

That recurring assertion motivates this question. I am looking for information about the variety of address spaces to illustrate that a C pointer is not necessarily a simple integer and that the C restrictions on pointer operations are sensible given the wide variety of machines to be supported.

Useful information may include:

• Examples of computer architectures with various address spaces and descriptions of those spaces.
• Examples of various address spaces still in use in machines currently being manufactured.
• References to documentation or explanation, especially URLs.
• Elaboration on how address spaces motivate C pointer rules.

This is a broad question, so I am open to suggestions on managing it. I would be happy to see collaborative editing on a single generally inclusive answer. However, that may fail to award reputation as deserved. I suggest up-voting multiple useful contributions.

Answer 1

Just about anything you can imagine has probably been used. The first major division is between byte addressing (all modern architectures) and word addressing (pre-IBM 360/PDP-11, but I think modern Unisys mainframes are still word addressed). In word addressing, char* and void* would often be bigger than an int*; even if they were not bigger, the "byte selector" would be in the high order bits, which were required to be 0, or would be ignored for anything other than bytes. (On a PDP-10, for example, if p was a char*, (int)p < (int)(p+1) would often be false, even though int and char* had the same size.)

Among byte addressed machines, the major variants are segmented and non-segmented architectures. Both are still wide spread today, although in the case of Intel 32bit (a segmented architecture with 48 bit addresses), some of the more widely used OSs (Windows and Linux) artificially restrict user processes to a single segment, simulating a flat addressing.

Although I've no recent experience, I would expect even more variety in embedded processors. In particular, in the past, it was frequent for embedded processors to use a Harvard architecture, where code and data were in independent address spaces (so that a function pointer and a data pointer, cast to a large enough integral type, could compare equal).

Answer 2

I would say you are asking the wrong question, except as historical curiosity.

Even if your system happens to use a flat address space -- indeed, even if every system from now until the end of time uses a flat address space -- you still cannot treat pointers as integers.

The C and C++ standards leave all sorts of pointer arithmetic "undefined". That can impact you right now, on any system, because compilers will assume you avoid undefined behavior and optimize accordingly.

For a concrete example, three months ago a very interesting bug turned up in Valgrind:

https://sourceforge.net/p/valgrind/mailman/message/29730736/

(Click "View entire thread", then search for "undefined behavior".)

Basically, Valgrind was using less-than and greater-than on pointers to try to determine if an automatic variable was within a certain range. Because comparisons between pointers in different aggregates is "undefined", Clang simply optimized away all of the comparisons to return a constant true (or false; I forget).

This bug itself spawned an interesting StackOverflow question.

So while the original pointer arithmetic definitions may have catered to real machines, and that might be interesting for its own sake, it is actually irrelevant to programming today. What is relevant today is that you simply cannot assume that pointers behave like integers, period, regardless of the system you happen to be using. "Undefined behavior" does not mean "something funny happens"; it means the compiler can assume you do not engage in it. When you do, you introduce a contradiction into the compiler's reasoning; and from a contradiction, anything follows... It only depends on how smart your compiler is.

And they get smarter all the time.