Read the auth cookie in linear time

Splitting the header with patterns that backtrack over spaces cost a
quarter of a second per request at the 8 KB line most web servers
allow, and a second at 16 KB, without any login. auth-file's trim had
the same shape and now reads the cookie as well.

3 files changed, 52 insertions, 14 deletions

diff --git a/custom/extensions/auth-file.lua b/custom/extensions/auth-file.luaindex aef7190..90f597b 100644--- a/custom/extensions/auth-file.lua+++ b/custom/extensions/auth-file.lua@@ -98,8 +98,19 @@ local action, http, cgit, post -- The two lookups below, account_hash and repo_userset, are the only part -- of this script that differs from auth-inline.lua. -local function trim(s)-	return (string.gsub(s, "^%s*(.-)%s*$", "%1"))+-- Lua patterns backtrack, so "^%s*(.-)%s*$" costs the square of a run of+-- spaces inside the text. Finding each end directly stays linear, which+-- matters for the Cookie header a visitor writes.+local function trim(text)+	local first = text:find("%S")+	if first == nil then+		return ""+	end+	local last = #text+	while text:find("^%s", last) do+		last = last - 1+	end+	return text:sub(first, last) end  local function add_names(list, set)@@ -210,16 +221,17 @@ function parse_query(query) 	return params end -local function pattern_escape(s)-	return (string.gsub(s, "([%^%$%(%)%%%.%[%]%*%+%-%?])", "%%%1"))-end- -- The token comes back still URL encoded by secure_value. Decoding it here -- would break the signature check for any value carrying a percent escape.--- The name is escaped because it lands in a Lua pattern. function get_cookie(cookies, name)-	cookies = string.gsub(";" .. (cookies or "") .. ";", "%s*;%s*", ";")-	return string.match(cookies, ";" .. pattern_escape(name) .. "=(.-);")+	for raw in string.gmatch(cookies or "", "[^;]+") do+		local pair = trim(raw)+		local equals = pair:find("=", 1, true)+		if equals and pair:sub(1, equals - 1) == name then+			return pair:sub(equals + 1)+		end+	end+	return nil end  function tohex(bytes)
diff --git a/custom/extensions/auth-file.lua b/custom/extensions/auth-file.lua
index aef7190..90f597b 100644
--- a/custom/extensions/auth-file.lua
+++ b/custom/extensions/auth-file.lua
@@ -98,8 +98,19 @@ local action, http, cgit, post
 -- The two lookups below, account_hash and repo_userset, are the only part
 -- of this script that differs from auth-inline.lua.
 
-local function trim(s)
-	return (string.gsub(s, "^%s*(.-)%s*$", "%1"))
+-- Lua patterns backtrack, so "^%s*(.-)%s*$" costs the square of a run of
+-- spaces inside the text. Finding each end directly stays linear, which
+-- matters for the Cookie header a visitor writes.
+local function trim(text)
+	local first = text:find("%S")
+	if first == nil then
+		return ""
+	end
+	local last = #text
+	while text:find("^%s", last) do
+		last = last - 1
+	end
+	return text:sub(first, last)
 end
 
 local function add_names(list, set)
@@ -210,16 +221,17 @@ function parse_query(query)
 	return params
 end
 
-local function pattern_escape(s)
-	return (string.gsub(s, "([%^%$%(%)%%%.%[%]%*%+%-%?])", "%%%1"))
-end
-
 -- The token comes back still URL encoded by secure_value. Decoding it here
 -- would break the signature check for any value carrying a percent escape.
--- The name is escaped because it lands in a Lua pattern.
 function get_cookie(cookies, name)
-	cookies = string.gsub(";" .. (cookies or "") .. ";", "%s*;%s*", ";")
-	return string.match(cookies, ";" .. pattern_escape(name) .. "=(.-);")
+	for raw in string.gmatch(cookies or "", "[^;]+") do
+		local pair = trim(raw)
+		local equals = pair:find("=", 1, true)
+		if equals and pair:sub(1, equals - 1) == name then
+			return pair:sub(equals + 1)
+		end
+	end
+	return nil
 end
 
 function tohex(bytes)
diff --git a/custom/extensions/auth-inline.lua b/custom/extensions/auth-inline.luaindex 5363a38..de91f88 100644--- a/custom/extensions/auth-inline.lua+++ b/custom/extensions/auth-inline.lua@@ -168,16 +168,32 @@ function parse_query(query) 	return params end -local function pattern_escape(s)-	return (string.gsub(s, "([%^%$%(%)%%%.%[%]%*%+%-%?])", "%%%1"))+-- Lua patterns backtrack, so "^%s*(.-)%s*$" costs the square of a run of+-- spaces inside the text. Finding each end directly stays linear, which+-- matters for the Cookie header a visitor writes.+local function trim(text)+	local first = text:find("%S")+	if first == nil then+		return ""+	end+	local last = #text+	while text:find("^%s", last) do+		last = last - 1+	end+	return text:sub(first, last) end  -- The token comes back still URL encoded by secure_value. Decoding it here -- would break the signature check for any value carrying a percent escape.--- The name is escaped because it lands in a Lua pattern. function get_cookie(cookies, name)-	cookies = string.gsub(";" .. (cookies or "") .. ";", "%s*;%s*", ";")-	return string.match(cookies, ";" .. pattern_escape(name) .. "=(.-);")+	for raw in string.gmatch(cookies or "", "[^;]+") do+		local pair = trim(raw)+		local equals = pair:find("=", 1, true)+		if equals and pair:sub(1, equals - 1) == name then+			return pair:sub(equals + 1)+		end+	end+	return nil end  function tohex(bytes)
diff --git a/custom/extensions/auth-inline.lua b/custom/extensions/auth-inline.lua
index 5363a38..de91f88 100644
--- a/custom/extensions/auth-inline.lua
+++ b/custom/extensions/auth-inline.lua
@@ -168,16 +168,32 @@ function parse_query(query)
 	return params
 end
 
-local function pattern_escape(s)
-	return (string.gsub(s, "([%^%$%(%)%%%.%[%]%*%+%-%?])", "%%%1"))
+-- Lua patterns backtrack, so "^%s*(.-)%s*$" costs the square of a run of
+-- spaces inside the text. Finding each end directly stays linear, which
+-- matters for the Cookie header a visitor writes.
+local function trim(text)
+	local first = text:find("%S")
+	if first == nil then
+		return ""
+	end
+	local last = #text
+	while text:find("^%s", last) do
+		last = last - 1
+	end
+	return text:sub(first, last)
 end
 
 -- The token comes back still URL encoded by secure_value. Decoding it here
 -- would break the signature check for any value carrying a percent escape.
--- The name is escaped because it lands in a Lua pattern.
 function get_cookie(cookies, name)
-	cookies = string.gsub(";" .. (cookies or "") .. ";", "%s*;%s*", ";")
-	return string.match(cookies, ";" .. pattern_escape(name) .. "=(.-);")
+	for raw in string.gmatch(cookies or "", "[^;]+") do
+		local pair = trim(raw)
+		local equals = pair:find("=", 1, true)
+		if equals and pair:sub(1, equals - 1) == name then
+			return pair:sub(equals + 1)
+		end
+	end
+	return nil
 end
 
 function tohex(bytes)
diff --git a/tests/extensions/test-auth.lua b/tests/extensions/test-auth.luaindex 0025a81..5d3541c 100644--- a/tests/extensions/test-auth.lua+++ b/tests/extensions/test-auth.lua@@ -121,6 +121,16 @@ h.equals("a lone cookie is found", get_cookie("cgitauth=abc", "cgitauth"), "abc" h.equals("no header yields no cookie", get_cookie(nil, "cgitauth"), nil) h.equals("a longer name does not match", get_cookie("xcgitauth=z", "cgitauth"), nil) h.equals("a magic character in the name is taken literally", get_cookie("a-b=z", "a-b"), "z")+h.equals("spaces around a pair are ignored", get_cookie(" foo=1 ;  cgitauth=abc ", "cgitauth"), "abc")+h.equals("a value keeps its own equals signs", get_cookie("cgitauth=a=b", "cgitauth"), "a=b")++-- The Cookie header is the visitor's to write, so a run of spaces in it+-- must not cost the square of its length.+local started = os.clock()+get_cookie("a=" .. string.rep(" ", 20000) .. "b", "cgitauth")+h.equals("a long run of spaces is read quickly",+	get_cookie(string.rep(" ", 20000) .. "cgitauth=abc", "cgitauth"), "abc")+h.check("and in linear time", os.clock() - started < 0.5)  h.check("equal strings compare equal", constant_equals("abc", "abc")) h.check("differing strings do not", not constant_equals("abc", "abd"))
diff --git a/tests/extensions/test-auth.lua b/tests/extensions/test-auth.lua
index 0025a81..5d3541c 100644
--- a/tests/extensions/test-auth.lua
+++ b/tests/extensions/test-auth.lua
@@ -121,6 +121,16 @@ h.equals("a lone cookie is found", get_cookie("cgitauth=abc", "cgitauth"), "abc"
 h.equals("no header yields no cookie", get_cookie(nil, "cgitauth"), nil)
 h.equals("a longer name does not match", get_cookie("xcgitauth=z", "cgitauth"), nil)
 h.equals("a magic character in the name is taken literally", get_cookie("a-b=z", "a-b"), "z")
+h.equals("spaces around a pair are ignored", get_cookie(" foo=1 ;  cgitauth=abc ", "cgitauth"), "abc")
+h.equals("a value keeps its own equals signs", get_cookie("cgitauth=a=b", "cgitauth"), "a=b")
+
+-- The Cookie header is the visitor's to write, so a run of spaces in it
+-- must not cost the square of its length.
+local started = os.clock()
+get_cookie("a=" .. string.rep(" ", 20000) .. "b", "cgitauth")
+h.equals("a long run of spaces is read quickly",
+	get_cookie(string.rep(" ", 20000) .. "cgitauth=abc", "cgitauth"), "abc")
+h.check("and in linear time", os.clock() - started < 0.5)
 
 h.check("equal strings compare equal", constant_equals("abc", "abc"))
 h.check("differing strings do not", not constant_equals("abc", "abd"))