[Bug libc/5514] memmem is O(n^2), but should be O(n)

["ebb9 at byu dot net" <sourceware-bugzilla at sourceware dot org>]

------- Additional Comments From ebb9 at byu dot net  2008-01-04 23:04 -------
I agree with the analysis that memmem (and strstr) can either be async-safe, or
have linear time complexity, but not both (there is no way around the fact that
string searches are inherently quadratic in space-time; you can either have
O(n^2) time and O(1) space, as is currently the case, or you can have O(n) time
and O(n) space, as in KMP or Boyer-Moore, but you cannot have O(n) time and O(1)
space, and O(n) space is not async-safe).

However, POSIX does not require any of the standardized str* or mem* functions
to be async-safe.  I plan on asking the Austin Group if this is an inadvertent
oversight for some of the obvious functions, like strlen.  But while Jakub is
correct in comment #3 that async-safety is nice, I see nothing that requires us
to preserve async-safety in strstr (and by extrapolation, memmem).  This means
that without feedback from the Austin Group, we are now faced with the
engineering decision of whether the default of async-safety or better time
complexity is more desirable in the default case - after all, poor time
complexity can be used as a denial of service attack.  Whichever default is
chosen, someone will come up with a counter program that is penalized.

It almost makes me wonder if there should be two alternate interfaces, strstr_r
that guarantees async-safety but with potentially poor performance, and
strstr_fast that guarantees linear performance but with potential locking.  Or
is there a way to detect whether we are in the middle of a signal handler, and
make a decision between speed and async-safety accordingly?



-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=5514

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.