Twenty Thousand Spaces on the Home Page — JavaScript Bug Hunt

Briefing

Modelled on the Stack Overflow outage of 20 July 2016. A post containing roughly 20,000 consecutive whitespace characters reached the home page, where a regular expression trimmed trailing whitespace from each post. Because the pattern was only anchored at the end, the engine tried every starting position inside the run and scanned forward to the next non-space each time, turning a trim into quadratic work. The web servers pinned their CPUs and the site went down for about half an hour; the fix replaced the regex with a simple backwards scan.

trim.js is a reconstruction of that matcher's behaviour, written out as a loop so every character examined is counted by the renderer's cursor.

Rewrite trimTrailing so it does linear work while returning exactly the same text.

Bug report

BUG-SO-0720 · Priority: Critical (site down) · Reported by: SRE on call

trimTrailing(cursor) returns the post text with trailing whitespace removed.

• whitespace is exactly what whitespace.isWhitespace accepts (space, tab, LF, CR, U+200C); everything before the trailing run is kept byte for byte, including whitespace in the middle of the post
• an empty or all-whitespace post returns ""
• characters may only be examined through cursor.charAt(i), and a call must examine at most text.length + 1 characters, whatever the input

Observed: a post with a long run of spaces followed by one more character makes the call examine millions of characters; the home page times out.

Logs

[web-11] GET / 200 34812ms  cpu=100%
[web-11] render summary post=38189021 cursor.reads=199990000
[lb] health check failed: web-01..web-11 (timeout)

The code as shipped

src/render/trim.js (editable)

var isWhitespace = require("./whitespace").isWhitespace;

// Strips trailing whitespace from a post summary before it is rendered.
exports.trimTrailing = function (cursor) {
  var n = cursor.length;
  for (var start = 0; start < n; start++) {
    if (!isWhitespace(cursor.charAt(start))) continue;
    var j = start;
    while (j < n && isWhitespace(cursor.charAt(j))) j++;
    if (j === n) return cursor.slice(0, start);
  }
  return cursor.slice(0, n);
};

Read-only context: src/render/cursor.js, src/render/whitespace.js.