From 8bd8cac9ef1d24899aba952b178602da56cede3d Mon Sep 17 00:00:00 2001 From: Bryce Kwon Date: Sat, 7 Nov 2026 11:06:29 -1000 Subject: Time the other filters at two lengths as well The avatar checks held a 40000 byte address to half a second, twenty times tighter than the readme budget that already failed on a slow host, and in stub mode nearly all of that time went on the fake digest. Link-commits and link-trailers had no check on a long input at all. The readme checks' method moves into the harness so all four share it. A single timing of each length let a busy host that took the CPU away during the longer one make a linear pass look quadratic. The lengths now take turns and the fastest timing of each counts, since a busy host can slow one timing but rarely all five. A ratio under six ends the turns at once, so only one near the bound of ten waits for all five. --- tests/extensions/harness.lua | 33 +++++++++++++++++++++++++++++++++ tests/extensions/test-about-render.lua | 23 +++++------------------ tests/extensions/test-email-avatar.lua | 16 ++++++++-------- tests/extensions/test-link-commits.lua | 7 +++++++ tests/extensions/test-link-trailers.lua | 6 ++++++ 5 files changed, 59 insertions(+), 26 deletions(-) (limited to 'tests/extensions') diff --git a/tests/extensions/harness.lua b/tests/extensions/harness.lua index 5084ab4..188d90f 100644 --- a/tests/extensions/harness.lua +++ b/tests/extensions/harness.lua @@ -301,6 +301,39 @@ function harness.excludes(name, haystack, needle) end end +-- Checks that a text four times as long costs about four times as much to +-- run, as a linear pass does, where a quadratic one costs sixteen times as +-- much. Timing one length against the other cancels out how fast the host +-- is. Each timing repeats the run for at least 50 ms, and the two lengths +-- take turns, keeping the fastest timing of each. A busy host can charge +-- the process for time its CPU was taken away, which slows a timing but +-- never speeds one up. A ratio under six is plainly linear and ends the +-- turns, so only one near the bound takes all five before it can fail. +-- Returns what the longer run gave back. +function harness.stays_linear(name, run, make, length) + local texts = { make(length), make(4 * length) } + local fastest = { math.huge, math.huge } + local out + for _ = 1, 5 do + for i = 1, 2 do + local runs, started = 0, os.clock() + repeat + out = run(texts[i]) + runs = runs + 1 + until os.clock() - started >= 0.05 + fastest[i] = math.min(fastest[i], (os.clock() - started) / runs) + end + if fastest[2] < 6 * fastest[1] then + break + end + end + local short, long = fastest[1], fastest[2] + harness.check(name, long < 10 * short, + string.format("%.4f s at length %d, then %.4f s at four times that", + short, length, long)) + return out +end + -- A run that made no check proves nothing, so it fails as well. function harness.finish() if failures > 0 then diff --git a/tests/extensions/test-about-render.lua b/tests/extensions/test-about-render.lua index a08de66..cdba28a 100644 --- a/tests/extensions/test-about-render.lua +++ b/tests/extensions/test-about-render.lua @@ -266,25 +266,12 @@ out = render("README.md", "**__*_x_*__**") h.contains("every kind of emphasis nests in the others", out, "

x

") --- A hostile readme must cost about four times as much at four times the --- length, as a linear pass does, where a quadratic one costs sixteen times --- as much and holds a request for minutes near the size cap. Timing one --- length against the other cancels out how fast the host is, and each --- render repeats until it is long enough to time. -local function seconds(filename, text) - local runs, started, out = 0, os.clock(), nil - repeat - out = render(filename, text) - runs = runs + 1 - until os.clock() - started >= 0.02 - return (os.clock() - started) / runs, out -end - +-- A hostile readme that renders in more than linear time holds a request +-- for minutes near the size cap. local function stays_linear(name, filename, make, length) - local short = seconds(filename, make(length)) - local long, out = seconds(filename, make(4 * length)) - h.check(name, long < 10 * short, - string.format("%.4f s at length %d, then %.4f s at four times that", short, length, long)) + local out = h.stays_linear(name, function(text) + return render(filename, text) + end, make, length) h.equals(name .. " and still renders as markup", out:sub(1, 22), "
") end diff --git a/tests/extensions/test-email-avatar.lua b/tests/extensions/test-email-avatar.lua index 5929634..c9a9ec0 100644 --- a/tests/extensions/test-email-avatar.lua +++ b/tests/extensions/test-email-avatar.lua @@ -101,14 +101,14 @@ h.contains("a name keeps the escaping cgit gave it", out, "> A & B") h.excludes("and is not escaped again", out, "&amp;") -- A commit can carry any bytes in its address, and a log page runs the --- filter once per row, so the trim has to stay linear in a run of spaces. -local started = os.clock() -render("", "x") -h.check("a long run of inner spaces is trimmed quickly", os.clock() - started < 0.5) - -started = os.clock() -render(string.rep("<", 40000), "x") -h.check("a long run of open brackets is unwrapped quickly", os.clock() - started < 0.5) +-- filter once per row, so trimming and unwrapping have to stay linear. +local function address_only(text) + return (render(text, "x")) +end +h.stays_linear("a long run of inner spaces is trimmed in linear time", address_only, + function(count) return "" end, 10000) +h.stays_linear("an address of open brackets is scanned in linear time", address_only, + function(count) return string.rep("<", count) end, 10000) h.check("text around the brackets is dropped", hash_of(render("x y", "x")) == plain) diff --git a/tests/extensions/test-link-commits.lua b/tests/extensions/test-link-commits.lua index fa3a040..dca16d4 100644 --- a/tests/extensions/test-link-commits.lua +++ b/tests/extensions/test-link-commits.lua @@ -126,4 +126,11 @@ h.equals("the shipped examples link what they describe", out, "!42 and " .. "RFC 9110") +-- A message near cgit's size limit with a match every few bytes still has +-- to come out in linear time. +h.load_with(script, { { "-- { pattern = \"#(%d+)\"", "{ pattern = \"#(%d+)\"" } }) +h.stays_linear("a long message full of matches is linked in linear time", function(text) + return (render(text)) +end, function(count) return string.rep("deadbeef #1 ", count) end, 10000) + h.finish() diff --git a/tests/extensions/test-link-trailers.lua b/tests/extensions/test-link-trailers.lua index c4dfdf5..7912d3e 100644 --- a/tests/extensions/test-link-trailers.lua +++ b/tests/extensions/test-link-trailers.lua @@ -106,4 +106,10 @@ out = render("CVE", "CVE-2024-12345") h.equals("the shipped CVE example links to its record", out, "CVE-2024-12345") +-- A long value of url starts is checked against the url pattern once, from +-- its start, so it costs no more than its length. +h.stays_linear("a long value is checked in linear time", function(text) + return (render("Link", text)) +end, function(count) return string.rep("http://", count) .. " " end, 10000) + h.finish() -- cgit 2.12.1