Is it possible in C (not invoking UB) to check if two objects overlap?

Question

When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object or incomplete types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.

If we have two pointers referencing the same type arrays and we have lengths of those arrays can we find if those arrays do not overlap without invoking a UB?

Remark: I am not interested in examples showing me that in the real life (implementation etc) it can be done. So please do not show the code (unless you can prove [standardwise] that is UB free).

Answer 1

It is possible in standard C, though not as efficient as a non-standard approach.

The above quoted passage from section 6.5.8p5 of the C11 standard applies to relational operators, i.e. <, >, <=, and >=. The equality operators == and != do not have this restriction. They can be used to compare any two object pointers for equality.

Specifically, section 6.5.9p6 regarding the equality operators state:

Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.

So you can check for overlap in a standard-compliant way by using == along with a pair of unsigned char * to iterate through the bytes of each object and compare their addresses for equality.

For example:

int overlap = 0;
unsigned char *o1 = (unsigned char *)&obj1;
unsigned char *o2 = (unsigned char *)&obj2;
for (int i=0; !overlap && i < sizeof obj1; i++) {
    for (int j=0; !overlap && j < sizeof obj2; j++) {
        if (o1 + i == o2 + j) {
            overlap = 1;
        }
    }
}

---

A more efficient approach would be to check the addresses of only the first byte of one object against the addresses of each byte in the other object, since if there is an overlap then the start of one object must be within the other:

int overlap(const void *p1, size_t size1, const void *p2, size_t size2)
{
    const unsigned char *o1 = p1;
    const unsigned char *o2 = p2;
    for (int i=0; i < size1; i++) {
        if (o1 + i == o2) {
            return 1;
        }
    }
    for (int i=0; i < size2; i++) {
        if (o2 + i == o1) {
            return 1;
        }
    }
    return 0;
}

Answer 2

The accepted answer is addressing OP's question by referring the appropriate section of language standard. But the second snippet of code posted in accepted answer will fail, in case, when the first object (array) is subset of second object (array) in such a way that first object is completely overlapped by second object but excluding the start and end element of second object i.e. overlapping like this -

                             object 2
                                |
    +-----------------------------------------------------------+
    |                                                           |
    |                                                           |

    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

        |                                                   |
        |                                                   |
        +---------------------------------------------------+
                                |
                             object 1 (any subset of this region)

This post is just a couple of modifications to address the problem in @dbush post second code snippet as well as making it a little more efficient by considering the size of element type of array in question.

/*
 * Parameters:
 * obj1    : Pointer to array1
 * obj1_sz : Size of array1
 * obj2    : Pointer to array2
 * obj2_sz : Size of array2
 * type_sz : Size of type of elements of array
 *
 * Return:
 * 0 - No overlap
 * 1 - Overlap
 *
 * [Assumption: Both array1 and array2 are of same type]
 */

int check_overlap (const void *obj1, size_t obj1_sz, const void *obj2, size_t obj2_sz, size_t type_sz) {
    const unsigned char *pobj1 = obj1;
    const unsigned char *pobj2 = obj2;
    size_t sz1 = obj1_sz;
    size_t sz2 = obj2_sz;

    if (obj1_sz < obj2_sz) {
            pobj1 = obj2;
            pobj2 = obj1;
            sz1 = obj2_sz;
            sz2 = obj1_sz;
    }

    for (size_t i = 0; i < sz1; ++i) {
            if ((pobj1 + (i * type_sz) == pobj2) ||
                (pobj1 + (i * type_sz) == pobj2 + ((sz2 - 1) * type_sz))) {
                    return 1;
            }
    }
    return 0;
}

Answer 3

Not in a portable way. There are several false negatives.

Counterexample #1: Memory aliasing

It is unusual for a device (e.g. RAM, ROM, or memory-mapped I/O) to use all of the address pins coming out of the processor. Typically, whatever number of address lines are needed by the device are connected to the lowest-order address lines of the processor, the highest address lines are used to select the device, and the address lines in between are not connected:

MSB -------- Address bus -------- LSB
| | ... | |  x x ... x x  | | ... | |
chip select  unconnected   to device

Such a device can be addressed as a block in the address space. However, the device also appears as several other blocks in the address space; each of these blocks physically point to the same locations on the device! The effect is called memory aliasing, and is much more common than you may realize.

For example, imagine a system with 16-bit addresses. Perhaps the top 4 address lines are used to select which chip is being addressed. Suppose we have a device assigned to A15:A12 == 0xE. Furthermore, this device only has 8 address lines coming out of it, so we connect those to A7:A0.

This device appears as addresses 0xE000 through 0xE0FF. However, it also appears at 0xE100 through 0xE1FF. Indeed, it appears 16 times in the address space, at any block 0xEz00 through 0xEzFF. Worse, each of these blocks physically point to the same thing. An access to 0xE123 is the same as an access to 0xE223, 0xE323, 0xE423, and so on.

So you can have two objects in memory that seem to point to different areas of memory, but in fact actually point to the same thing:

char *x = (char *)0xE000;
char *y = (char *)0xE300;
if (overlap(x, y, 16)) { ... }

A naive implementation of overlap() would report these as two different objects. But they are the same object; writing to x[] changes y[]. Therefore, in this case you will get a false negative. A correct implementation of overlap() would require and depend upon full knowledge of the system's memory map, making such a function completely non-portable.

Counterexample #2: Shared memory

Suppose x and y are overlapping objects in process A. We then use the operating system to create shared memory between process A and process B. Specifically, xx is a shared memory pointer in process B that points to x, and yy is a shared memory pointer in process B that points to y.

Back in process A, it's not hard to write a function that determines that x and y indeed overlap.

But depending on the operating system, pointers xx and yy in process B may look nothing like overlapping objects. But in reality, they do indeed point to overlapping objects. So you will get a false negative.

Is it theoretically possible to write a function that checks across processes for overlap? Probably, but keep in mind that I can make the problem even more difficult. I can create subsets of xx and yy that still overlap; I can share memory from process B to a third process; and so on. In any case, any such solution is not portable.

Counterexample #3: 8086 far pointers

The 8086 architecture on the original IBM PC used a type of memory mapping called "segmentation". A 16-bit register called the "segment" was multiplied by 16 and then added to another 16-bit register with the "base address" to obtain the 20-bit physical address.

Programs needing less than 64k of memory could get away with just the 16-bit base addresses, called "near pointers". But programs that needed more than 64k of memory had to maintain 32-bit "far pointers" which contained both the segment and the base address.

Because of the pointer arithmetic of segmentation, it is quite easy to make two far pointers that seem to be quite different, yet point to the same object:

far char *x = (far char *)0x12340005L;
far char *y = (far char *)0x10002345L;

In this case, x and y both point to the same physical address 0x12345, even though they are very different bit patterns.

Some compilers would treat x == y as false because they have different bit patterns. Other compilers would do the math (with a performance penalty) and return true. Yet other compilers let you choose either behavior with a command-line switch or #pragma.

---

The OP complains that these examples represent compilers that are not "standard-conforming". The argument is that if two pointers actually do point to the same object, then the standard says they must compare ==.

If you're going to be such a language-lawyer, then no compiler has even conformed to the standard. Not gcc, not Microsoft C (two compilers proud of their conformance). Basically every system that has had a C compiler has had some degree of memory aliasing (counterexample #1). So every C compiler is guilty of allowing two != pointers point to the same thing.

On the other hand, if you interpret the standard by its intended meaning instead of its literal meaning, then those compilers do conform to the standard.

Sure, these are edge cases. Most programs are in user space, where #1 is hidden away. Few programs use shared memory (#2). And no one likes programming in a segmented memory model (#3). But exceptions like these are why the standard has so many instances of undefined behavior; many things which work in one case cannot be made to work that way on other cases.

Answer 4

Well, if we're going to be language-lawyering, I raise you this:

// SPDX-License-Identifier: CC0-1.0

#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>

bool overlap(const void *p1, size_t s1, const void *p2, size_t s2)
{
    const uintptr_t p1b = (uintptr_t) p1;
    const uintptr_t p2b = (uintptr_t) p2;
    const uintptr_t p1e = (uintptr_t) ((char*) p1 + (s1 - 1));
    const uintptr_t p2e = (uintptr_t) ((char*) p2 + (s2 - 1));
    return (p1b <= p2b && p2b <= p1e)
        || (p2b <= p1b && p1b <= p2e);
}

This code invokes implementation-defined behavior, not undefined behavior.[1] Obviously, this is by no means portable, but in most cases this should work.

---

[1]: ISO/IEC 9899:2018, § 6.3.2.3, par. 6 ("Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined.").

Answer 5

Well, since you didn't say anything about preserving data:

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

bool overlaps(void* p1, void* p2, size_t sz1, size_t sz2) {
    if (!p1 || !p2 || !sz1 || !sz2) return false; /* empty ranges ignored */

    memset(p1, 0, sz1);
    memset(p2, 1, sz2);

    return !!memchr(p1, 1, sz1);
}

This is completely well defined.

Answer 6

In the language the Standard was written to describe, it would be possible to use the equality comparison operator to check the starting address of each object with every possible address within the other. If the objects overlap, one such comparison should report a match.

In the language processed by clang and gcc, however, the equality comparison operator may only be used with two pointers that each identify a byte in some object, or with two pointers that each point just past the last byte of some object, or with a null pointer and a pointer of either of the above categories. Using it with one pointer from each of the first two categories is not allowed.

The inability of clang and gcc to reliably handle corner cases involving comparisons between pointers of the first two categories has been entered on both compilers' bug reporting systems years ago; the fact that both compilers continue to make "optimizations" that break in such cases implies that their maintainers believe the language forbids such comparisons and imposes no requirements whatsoever on the behavior of any program that performs them.

Answer 7

You can check in linear time whether &obj1[i] == &obj2[0] for some i, or &obj1[0] == &obj2[i] for some i and determine this way if there is overlap or not.

Before you do that, you cast obj1 and obj2 to uintptr_t, assume (without evidence) that pointers cast to uintptr_t behave similar to char*, and calculate i, j so that &obj1[i] should equal &obj2[j] according to your assumptions, and both indices are valid. Since comparing unrelated pointers for equality or inequality doesn't invoke UB you might be able to prove that the arrays are overlapping this way. If your implementation is weird then this doesn't help, but also won't give you wrong results. And if the arrays don't overlap, it doesn't work either. In those case you go back to the first method.

Answer 8

The problem maybe more complex, when these objects have other (and different) objects as members (subobjects) which also may overlap. Like an array of strings.

Your overlap problem is more a program logic problem, because every object should have its own memory or some shared data from a data store, which than no one own. Depending on the problem, you can also use an additional memory struct array which is maintaining all start and end addresses of the components and than you only are comparing addresses.