#2515 data race in multi-threaded word wrap

[Zufu Liu]

My following change from [bugs:#2511] seems introduced or exposed data race for multi-threaded wrap block:

-           cache[pos].reset();
+           cache[pos]->ReSet(lineNumber, maxChars);

The root cause I think is that multiple significant lines may mapped to same cache position, when one thread is using the layout (in view.LayoutLine), another thread may resize it and use it. with old cache[pos].reset() both thread will works on different layout (previous thread's layout is no longer in the cache, but not dangling).

[Zufu Liu]

Following is test program to show multiple significant lines may mapped to same cache position:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <memory>
#include <vector>
#include <map>

struct LineLayout {
    int lineNumber;
    LineLayout(int lineNumber_) noexcept : lineNumber{lineNumber_} {}
    int LineNumber() const noexcept {
        return lineNumber;
    }
    bool CanHold(int lineDoc) const noexcept {
        return lineNumber == lineDoc;
    }
};

constexpr uint32_t AlignUp(uint32_t value, uint32_t alignment) noexcept {
    return ((value - 1) / alignment + 1) * alignment;
}
constexpr uint32_t alignmentLLC = 20;
void TestScintilla() {
    constexpr int lineCaret = 59;
    constexpr int lineTop = 52;
    constexpr int linesOnScreen = 48;
    constexpr int linesInDoc = 928;
    constexpr uint32_t cacheSize = AlignUp(linesOnScreen + 1, alignmentLLC);

    const auto LineMayCache = [=](int line) noexcept {
        return std::abs(line - lineCaret) < linesOnScreen ||
            ((line >= lineTop) && (line <= (lineTop + linesOnScreen)));
    };
    const auto EntryForLine = [=](int line) noexcept {
        return 1 + (line % (cacheSize - 1));
    };

    std::vector<std::shared_ptr<LineLayout>> cache{cacheSize};
    std::map<uint32_t, int> uniquePos;
    for (int lineNumber = 0; lineNumber < linesInDoc; lineNumber++) {
        if (!LineMayCache(lineNumber)) {
            continue;
        }
#if 1
        uint32_t pos = 0;
        if (!(cache[0] && (cache[0]->LineNumber() == lineNumber))) {
            const uint32_t posForLine = EntryForLine(lineNumber);
            if (lineNumber == lineCaret) {
                if (cache[0]) {
                    const uint32_t posNewForEntry0 = EntryForLine(cache[0]->LineNumber());
                    if (posForLine == posNewForEntry0) {
                        std::swap(cache[0], cache[posNewForEntry0]);
                    } else {
                        cache[posNewForEntry0] = std::move(cache[0]);
                    }
                }
                if (cache[posForLine] && (cache[posForLine]->LineNumber() == lineNumber)) {
                    cache[0] = std::move(cache[posForLine]);
                }
            } else {
                pos = posForLine;
            }
        }
        if (!cache[pos] || !cache[pos]->CanHold(lineNumber)) {
            cache[pos] = std::make_shared<LineLayout>(lineNumber);
        }
#else
        const uint32_t pos = EntryForLine(lineNumber);
#endif
        const auto [it, inserted] = uniquePos.try_emplace(pos, lineNumber);
        if (!inserted) {
            printf("error [%d, %d, %d] %u: %d, %d\n", linesOnScreen, lineCaret, lineTop, pos, lineNumber, it->second);
            return;
        }
    }
}

int __cdecl main() {
    TestScintilla();
    return 0;
}

[Zufu Liu]

with following change for Notepad4:

@@ -640,6 +640,10 @@ uint32_t EditView::LayoutLine(const EditModel &model, Surface *surface, const Vi

            const XYPOSITION xBeginSegment = xPosition;
            for (int i = 0; i < ts.length; i++) {

+               if (iByte > static_cast<unsigned>(ll->numCharsInLine)) {
+                   printf("data race: lineNumber=%zd/%zd iByte=%u/%d\n", line, ll->LineNumber(), iByte, ll->numCharsInLine);
+                   throw iByte;
+               }
                xPosition = ll->positions[iByte] + xBeginSegment;
                ll->positions[iByte++] = xPosition;
            }

I can reproduce the race when running (x64 Debug or Release) from Visual Studio 2026 (it's hard to reproduce outside the debugger), open scintilla\win32\SurfaceGDI.cxx, put caret between class and SurfaceGDI, toggle fold for level 2 (collapse all SurfaceGDI methods), then resize editor width multiples, VS will stop at throw iByte. change Notepad4's LineLayoutCache from std::unique_ptr<LineLayout> to std::shared_ptr<LineLayout> does not fix the race, but following fixes it.

-           ret->Reset(lineNumber, maxChars);
+           ret.reset();

check layout use_count() after linesAfterWrap[i] = ll->lines;, it's positive.

I have not yet reproduce the race in Scintilla with similar change:

diff -r b896a2e57652 src/EditView.cxx
--- a/src/EditView.cxx
+++ b/src/EditView.cxx
@@ -520,6 +520,10 @@
            }
            const XYPOSITION xBeginSegment = xPosition;
            for (int i = 0; i < ts.length; i++) {

+               if (iByte > static_cast<unsigned>(numCharsInLine)) {
+                   printf("data race: lineNumber=%zd/%zd iByte=%zu/%d\n", line, ll->LineNumber(), iByte, numCharsInLine);
+                   throw iByte;
+               }
                xPosition = ll->positions[iByte] + xBeginSegment;
                ll->positions[iByte++] = xPosition;
            }
diff -r b896a2e57652 src/Editor.cxx
--- a/src/Editor.cxx
+++ b/src/Editor.cxx
@@ -1603,6 +1603,11 @@
                    }
                    view.LayoutLine(*this, surface, vs, ll.get(), wrapWidth, multiThreaded);
                    linesAfterWrap[i] = ll->lines;
+                   const long use_count = ll.use_count();
+                   if (use_count <= 0) {
+                       printf("dangling: %zd\n", lineNumber);
+                       throw use_count;
+                   }
                }
            }
        });

[Zufu Liu]

but not dangling

here is no need to mannerly reset:

@@ -599,10 +599,7 @@
    }

    if (pos < cache.size()) {

-       if (cache[pos] && !cache[pos]->CanHold(lineNumber, maxChars)) {
-           cache[pos]->ReSet(lineNumber, maxChars);
-       }
-       if (!cache[pos]) {
+       if (!cache[pos] || !cache[pos]->CanHold(lineNumber, maxChars)) {
            cache[pos] = std::make_shared<LineLayout>(lineNumber, maxChars);
        }
 #ifdef CHECK_LLC

[Neil Hodgson]

I should have noticed the problem with the ReSet change.

The above change looks good so has been committed as [e87fc0].

This is probably worth a release since there may be writes outside allocations.

[Zufu Liu]

ReSet can only be called from main thread (the only thread that uses layout cache) or when lineNumber is same (same document line number is only handled by one thread).

Adjust LineMayCache could make significant lines maps to unique cache position (change || to && seems work in Notepad4), but that requires some calculation and proof, and is hard to get right.