This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Use Quicksearch in strstr
- From: Joseph Myers <joseph at codesourcery dot com>
- To: Rich Felker <dalias at libc dot org>
- Cc: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>, 'GNU C Library' <libc-alpha at sourceware dot org>, nd <nd at arm dot com>, Alexander Monakov <amonakov at ispras dot ru>
- Date: Tue, 6 Nov 2018 17:50:04 +0000
- Subject: Re: [PATCH] Use Quicksearch in strstr
- References: <DB5PR08MB1030E559B3818F52CA48A63583F30@DB5PR08MB1030.eurprd08.prod.outlook.com> <20181029225421.GA21482@domone> <DB5PR08MB1030CE58A51EDD8FE90D80DD83CD0@DB5PR08MB1030.eurprd08.prod.outlook.com> <DB5PR08MB1030428E777D456220B6F09383CB0@DB5PR08MB1030.eurprd08.prod.outlook.com> <20181106153429.GP5150@brightrain.aerifal.cx>
On Tue, 6 Nov 2018, Rich Felker wrote:
> Real world performance includes performance under the control of a
> hostile input source, under which naive algorithms will perform
> hundreds of times slower. This "quicksearch" is incredibly slow on
Indeed. I think strstr failing to be O(m+n) worst case is clearly a
security bug; when you have an upper bound on m for an O(mn) algorithm to
avoid a quadratic worst case, the only question is at what point that
bound gets too high so the worst case performance is excessively bad.
I've just filed bug 23865 for wcsstr using a naive quadratic-time
implementation.
--
Joseph S. Myers
joseph@codesourcery.com