overlapping buffers and memccpy()

[krader1961]

The change I authored, commit de00119, which was recently merged to fix building on BSD based systems like macOS only works when using gcc to do the compilation. If you instead use the clang compiler provided by Apple it fails because the BSD preprocessor symbol isn't defined. You also need to blacklist __APPLE__.

But here's the thing, the code before my change began with this preprocessor directive:

#if _lib_memccpy && !__ia64 /* these guys may never get it right */

The problem is that assertion is wrong. It implies that the libc implementation of memccpy() on IA64 is broken. Which is incorrect. The problem is the AST sfputr() function is depending on what is explicitly undefined behavior in the face of overlapping source and destination buffers. Every implementation is free to optimize the operation by assuming the buffers do not overlap but in so doing produce incorrect results, including aborting the program, if the buffers do overlap.

I was too timid with my previous change. I should not have added another blacklisted architecture. Instead the use of memccpy() should simply be removed. If you look at the two alternatives using memccpy() simply complicates the code and is unlikely to be measurably, let alone noticeably, faster.

[krader1961]

I instrumented the code to write a diagnostic message when sfputr() is called with overlapping buffers. Many, but not all, show that the buffers have the same initial address:

WTF ps = 0x1e00a85e23b0, s = 0x1e00a85e23b0, p = 1024

Many others overlap somewhat:

WTF ps = 0x1e00a85e2432, s = 0x1e00a85e21df, p = 894

Note the p = value is decimal rather than hex. So those two buffers do overlap since 0x2432 + 894 is greater than 0x21df.

I have no idea why that function is being called with overlapping buffers. But it obviously broken by relying on memccpy() working correctly with overlapping buffers. How is it that this was not noticed long ago?

[krader1961]

I did a more fine grained analysis. First, note that 97.2% of the calls to memccpy() in sfputr() move fewer than 100 bytes while building the entire AST project. And 99.6% move fewer than 500 bytes. So we really don't need the optimized implementation provided by memccpy(). The explicit loop that is already used if memccpy() doesn't handle overlapping buffers is plenty fast given typical inputs. Just for grins I bucketed the calls by the number of bytes copied using a bucket size of 1000:

17788687 1000
  20009 2000
   4508 3000
    354 4000
   1585 5000
   6840 6000
   2322 7000
   1453 8000
    224 9000
    112 10000
     16 11000
      1 12000
      3 13000
      1 15000
     29 17000
     71 18000
     40 19000
      2 21000
      2 24000
      1 25000
     98 33000
     98 34000
      2 41000
      1 47000
      2 135000

Also, when the source and destination buffers aren't the same (i.e., have different starting addrs) it appears they never actually overlap. It only appears they might because a large length (typically 1024) is being passed in. But because the copy terminates when a null byte is seen, and that almost always happens within the first 100 bytes, there isn't any overlap when the starting addr of each buffer differs. Of the invocations that theoretically have overlapping buffers only 27.4% actually overlap. And those are suspicious given that the source and destination addrs are the same and thus should be a nop. Meaning it should be okay to elide the copy.

[krader1961]

Note that ksh cannot be built with the clang toolchain on macOS even after blacklisting defined(__APPLE__) from the systems which can use memccpy(). Not because of a run-time problem but because AST is still trying to support the C standard from circa 1980.

There are a significant number of problems with the code. Most notably with respect to functions which have more than one declaration which do not agree with each other. Something gcc is willing to ignore (apparently for compatibility with ancient C compilers) but clang is not willing to ignore. This does not surprise me very much given the uses of __STD_C in the code to determine whether function declarations have to conform to the original K&R C syntax or anything more modern.

[krader1961]

I just noticed issue #4 for which this issue is essentially a duplicate. My commit de00119 that was recently merged fixes both of the problems identified in issue #4 but in a slightly different manner than was proposed there. So issue #4 can be closed.

However, as noted in my previous comments on this issue sfputr() shouldn't be using memccpy() even on systems where it apparently works because doing so relies on undefined behavior which, theoretically, could change on those systems. The only reason I haven't proposed another change to eliminate that use of memccpy() is that doing so still doesn't yield a working ksh command when building with clang on macOS. I'm still debugging what else is broken but got side tracked by trying to figure out how to not build all the stuff in the AST project that is not needed to build ksh.

[krader1961]

Closing since my change to remove the unsafe use of memccpy() has been merged.