2

When I write code, among the more common classes of bug I create is off-by-one errors (OBO). In "real" code I most often run into this issue while doing complicated pointer/iterator arithmetic in C or C++, but I've also at times had issues with it in job interview and homework (e.g. implementing mergesort) questions where I used other programming languages.

My typical debugging strategy consists of randomly swapping < and <=, ++var and var++ and appending + 1 or - 1 to variables until the code appears to work. I would be interested to know what better strategies or tools (e.g. static analysis, debugger/IDE features, etc.) exist to spot OBO.

I'm not particularly interested in pat answers like "avoid C-style loops," "avoid pointer arithmetic," "code in a functional style" or "use a different programming language." Yes, these things can mitigate the issue, but it's not always possible to do them and they don't eliminate the OBO danger entirely.

As an example, I believe the following code, a C (or it's also valid C++) implementation of strcpy(3), is free of OBO. But as you can see there are dozens of potential problem areas where OBO could crop up. Is there some way to easily confirm that it is in fact free of OBO?

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

#if !defined(__GNUC__) && !defined(__attribute__)
#define __attribute__(X)
#endif

#ifdef __cplusplus
extern "C" {
#if defined(__GNUC__) || defined(_MSC_VER) || defined(__restrict)
#define restrict __restrict
#elif !defined(restrict)
#define restrict
#endif
#endif

static inline bool aligned8(const void *ptr) {return !((uintptr_t)ptr & 7);}
static inline bool aligned4(const void *ptr) {return !((uintptr_t)ptr & 3);}
static inline bool aligned2(const void *ptr) {return !((uintptr_t)ptr & 1);}

/* Positive return value is the greatest common alignment (≤8) of the pointers.
 * Negative return value is the byte offset that when added to both pointers
 * yields a pair of pointers with alignment ≥8.
 */
static inline int common_alignment(const void *p1, const void *p2) {
    if (aligned8(p1)) {
        if (aligned8(p2))
            return 8;
        else if (aligned4(p2))
            return 4;
        else if (aligned2(p2))
            return 2;
    } else if (aligned4(p1)) {
        if (aligned8(p2))
            return 4;
        else if (aligned4(p2))
            return -4;
        else if (aligned2(p2))
            return 2;
    } else if (aligned2(p1)) {
        if (aligned4(p2))
            return 2;
        else if (aligned2(p2))
            return -6;
    } else if (!aligned2(p2)) {
        return -7;
    }
    return 1;
}

/* strcpy implementation
 */
__attribute__((nonnull))
size_t string_copy(char *restrict dst, const char *restrict src) {
    size_t i = 0;
    int align = common_alignment(dst, src);

    if (align < 0) {
        for (; i < (size_t)-align; ++i)
            if (!(*dst++ = *src++))
                return i;
        align = 8;
    }

    const size_t mask = (size_t)align - 1;

#define ALIGNED_STRING_COPY_IMPL_(BITS) do {\
    uint##BITS##_t *restrict dst##BITS = (uint##BITS##_t*)dst;\
    while (*src++)\
        if (!(++i & mask))\
            *dst##BITS++ = *(const uint##BITS##_t *restrict)(src - align);\
    dst = (char*)dst##BITS;\
} while (0)

    if (align & 8) {
        ALIGNED_STRING_COPY_IMPL_(64);
    } else if (align & 4) {
        ALIGNED_STRING_COPY_IMPL_(32);
    } else if (align & 2) {
        ALIGNED_STRING_COPY_IMPL_(16);
    } else { // byte-aligned
        while ((*dst++ = *src++))
            ++i;
        return i;
    }

    const size_t offset = (i & mask) + 1;

    memcpy(dst, src - offset, offset);

    return i;
}

#ifdef __cplusplus
}
#endif
Ray Hamel
  • 1,289
  • 6
  • 16
  • You may want to run a *static analysis* tool. – Thomas Matthews Apr 26 '21 at 17:25
  • 1
    I am not aware of any "formal" or automated method for it (unless it is causing some illegal accesses that can be discovered by analysis tools). It is just each time you encounter a potential for OBO you need to think carefully, maybe draw some diagrams on paper. – Eugene Sh. Apr 26 '21 at 17:25
  • Use a checklist when you inspect your code. Add "off by one" as one of the items in the checklist. – Thomas Matthews Apr 26 '21 at 17:26
  • 2
    *My typical debugging strategy consists of randomly swapping < and <=, ++var and var++ and appending + 1 or - 1 to variables until the code appears to work* - this is most definitely not the right approach. When you discover an off-by-one error, you need to get to its root, and fix it there, otherwise you will fix it in one place, and it will reappear in another . – Eugene Sh. Apr 26 '21 at 17:31
  • 2
    Write and run test cases that hit the boundary conditions. – Pete Becker Apr 26 '21 at 17:32
  • @EugeneSh. That's my debugging strategy, not my "my work is done here" criterion. – Ray Hamel Apr 26 '21 at 17:37
  • Stop guessing. Write proofs. Formal proofs for whole programs or large functions is hard, but writing proofs for straightforward cases is not. Given a function passed an array of some length n, write some documentation (in comments is fine) demonstrating the maximum index used to access the array is less than n. Take at least one class in formal mathematics of program semantics. – Eric Postpischil Apr 26 '21 at 17:41
  • @RayHamel Ok, sure, if your environment lets you afford this. Not every one does. For example if you have a system reproducing the failure in another time zone and you need an actual person to help you in the other side - then you can only afford a very limited number of trials per unit of time. – Eugene Sh. Apr 26 '21 at 17:43
  • Instead of randomly changing the code, analyze the program and the algorithm and try to understand why it uses `<` or `<=` etc. Running the program in a debugger step-by-step might help to get this understanding. – Bodo Apr 26 '21 at 17:45
  • BTW, `!((uintptr_t)ptr & 7)` is not a specified way to find alignment as it assumes integer characteristics about the encoding of a pointer. Commonly this "works". – chux - Reinstate Monica Apr 26 '21 at 17:45
  • @chux-ReinstateMonica If we are on it, how would you do it in a conforming way? – Eugene Sh. Apr 26 '21 at 17:47
  • @EugeneSh.AFAIK, there is not a conforming way. Some things C can't do. – chux - Reinstate Monica Apr 26 '21 at 17:50
  • @EugeneSh.: It is a conforming way. It is not a strictly conforming way. – Eric Postpischil Apr 26 '21 at 17:57

0 Answers0