328152 |
18-Jan-2018 |
kevans |
MFC r322288: regex(3): Refactor fast/slow stepping bits in matching engine
Adding features for matching is fairly straightforward, but this requires some duplication because of this fast/slow setup. They can be fairly trivially combined into a single walk(), so do it to make future additions less error prone. |
328151 |
18-Jan-2018 |
kevans |
MFC r320742, r320750, r320796: Refactor regex(3) for maintainability
MFC r320742: The impending libregex will implement GNU extensions to bring BREs and EREs closer together. Prepare for this and reduce the diff of libregex changes by refactoring and combining the top-level parsers for EREs/BREs ahead of time.
Branching functionality has been split out to make it easier to follow the combined version of the top-level parser. It may also be enabled in the parsing context to make it easier when libregex enables branching for BREs.
A branching context was also added for the various branching functions and so that BREs, for instance, can determine if they're the first expression in a chain of expressions within the current branch and treat '*' as ordinary if so.
This should have no functional impact and negligible performance impact.
MFC r320750: Fix sparc64 libc build after r320742.
p_branch_empty was declared but never used due to an oversight. Use it as designed, further comment on its return value.
MFC r320796: Correctly ignore branch operators in the top-level parser when applicable.
An oversight in r320742 caused BREs to become sensitive to the branching operator prematurely, which caused breakage in some limited situations -- namely, those that tried to use branching in a BRE. Most of these scenarios had already been corrected beforehand to properly use gsed or grep for GNU extensions, so the damage is slightly mitigated. |
325393 |
04-Nov-2017 |
pfg |
MFC r325066: Fix out-of-bounds read in libc/regex.
The bug is an out-of-bounds read detected with address sanitizer that happens when 'sp' in p_b_coll_elems() includes NUL byte[s], e.g. if it's equal to "GS\x00". In that case len will be equal to 4, and the strncmp(cp->name, sp, len) call will succeed when cp->name is "GS" but the cp->name[len] == '\0' comparison will cause the read to go out-of-bounds.
Checking the length using strlen() instead eliminates the issue.
The bug was found in LLVM with oss-fuzz: https://reviews.llvm.org/D39380
Obtained from: Vlad Tsyrklevich through posting on openbsd-tech |
318029 |
09-May-2017 |
brooks |
MFC r317707:
Correct an out-of-bounds read in regcomp when the RE is bad.
When passed the invalid regular expression "a**", the error is eventually detected and seterr() is called. It sets p->error appropriatly and p->next and p->end to nuls which is a never used char nuls[10] which is zeros due to .bss initialization. Unfortunatly, p_ere_exp() and p_simp_re() both have fall through cases where they set the error, decrement p->next and access it which means a read from whatever .bss variable comes before nuls.
Found with regex_test:repet_multi and CHERI bounds checking.
Reviewed by: ngie, pfg, emaste Obtained from: CheriBSD Sponsored by: DARPA, AFRL Differential Revision: https://reviews.freebsd.org/D10541 |
313240 |
04-Feb-2017 |
ngie |
MFC r312332,r312446,r312451:
r312332:
Use SRCTOP where possible and use :H to manipulate .CURDIR to get rid of unnecessarily long relative path .PATH values with make
r312446 (by emaste):
libc: remove reference to nonexistent lib/locale directory
As far as I can tell this was introduced in r72406 and updated in several subsequent revisions, but the lib/locale directory it referenced never existed.
r312451:
Replace dot-dot relative pathing with SRCTOP-relative paths where possible
This reduces build output, need for recalculating paths, and makes it clearer which paths are relative to what areas in the source tree. The change in performance over a locally mounted UFS filesystem was negligible in my testing, but this may more positively impact other filesystems like NFS.
LIBC_SRCTOP was left alone so Juniper (and other users) can continue to manipulate lib/libc/Makefile (and other Makefile.inc's under lib/libc) as include Makefiles with custom options.
Discussed with: marcel, sjg |
301461 |
05-Jun-2016 |
pfg |
libc/locale: Fix type breakage in __collate_range_cmp().
When collation support was brought in, the second and third arguments in __collate_range_cmp() were changed from int to wchar_t, breaking the ABI. Change them to a "char" type which makes more sense and keeps the ABI compatible.
Also introduce __wcollate_range_cmp() which does work with wide characters. This function is used only internally in libc so we don't export it. Use the new function in glob(3), fnmatch(3), and regexec(3).
PR: 179721 Suggested by: ache. jilles MFC after: 3 weeks (perhaps partial only)
|
300683 |
25-May-2016 |
pfg |
libc: regexec(3) adjustment.
Change the behavior of when REG_STARTEND is combined with REG_NOTBOL.
From the original posting[1]:
"Enable the assumption that pmatch[0].rm_so is a continuation offset to a string and allows us to do a proper assessment of the character in regards to it's word position ('^' or '\<'), without risking going into unallocated memory."
This change makes us similar to how glibc handles REG_STARTEND | REG_NOTBOL, and is closely related to a soon-to-land fix to sed.
Special thanks to Martijn van Duren and Ingo Schwarze for working out some consistent behaviour.
Differential Revision: https://reviews.freebsd.org/D6257 Taken from: openbsd-tech 2016-05-24 [1] (Martijn van Duren) Relnotes: yes MFC after: 1 month
|
227753 |
20-Nov-2011 |
theraven |
Implement xlocale APIs from Darwin, mainly for use by libc++. This adds a load of _l suffixed versions of various standard library functions that use the global locale, making them take an explicit locale parameter. Also adds support for per-thread locales. This work was funded by the FreeBSD Foundation.
Please test any code you have that uses the C standard locale functions!
Reviewed by: das (gdtoa changes) Approved by: dim (mentor)
|
134802 |
05-Sep-2004 |
tjr |
Fix two problems with REG_ICASE that were introduced with the addition of multibyte character support: - In CHadd(), avoid writing past the end of the character set bitmap when the opposite-case counterpart of wide characters with values less than NC have values greater than or equal to NC. - In CHaddtype(), fix a braino that caused alphabetic characters to be added to all character classes! (but only with REG_ICASE)
PR: 71367
|
132019 |
12-Jul-2004 |
tjr |
Make regular expression matching aware of multibyte characters. The general idea is that we perform multibyte->wide character conversion while parsing and compiling, then convert byte sequences to wide characters when they're needed for comparison and stepping through the string during execution.
As with tr(1), the main complication is to efficiently represent sets of characters in bracket expressions. The old bitmap representation is replaced by a bitmap for the first 256 characters combined with a vector of individual wide characters, a vector of character ranges (for [A-Z] etc.), and a vector of character classes (for [[:alpha:]] etc.).
One other point of interest is that although the Boyer-Moore algorithm had to be disabled in the general multibyte case, it is still enabled for UTF-8 because of its self-synchronizing nature. This greatly speeds up matching by reducing the number of multibyte conversions that need to be done.
|
86208 |
09-Nov-2001 |
dcs |
The algorithm that computes the tables used in the BM search algorithm sometimes access an array beyond it's length. This only happens in the last iteration of a loop, and the value fetched is not used then, so the bug is a relatively innocent one. Fix this by not fetching any value on the last iteration of said loop.
Submitted by: MKI <mki@mozone.net> MFC after: 1 week
|
62855 |
09-Jul-2000 |
dcs |
altoffset() always returned whenever it recursed, because at the end of the processing of the recursion, "scan" would be pointing to O_CH (or O_QUEST), which would then be interpreted as being the end character for altoffset().
We avoid this by properly increasing scan before leaving the switch.
Without this, something like (a?b?)?cc would result in a g->moffset of 1 instead of 2.
I added a case to the soon-to-be-imported regex(3) test code to catch this error.
|
62854 |
09-Jul-2000 |
dcs |
Since g->moffset points to the _maximum_ offset at which the must string may be found (from the beginning of the pattern), the point at which must is found minus that offset may actually point to some place before the start of the text.
In that case, make start = start.
Alternatively, this could be tested for in the preceding if, but it did not occur to me. :-)
Caught by: regex(3) test code
|
62754 |
07-Jul-2000 |
dcs |
Deal with the signed/unsigned chars issue in a more proper manner. We use a CHAR_MIN-based array, like elsewhere in the code.
Remove a number of unused variables (some due to the above change, one that was left after a number of optimizing steps through the source).
Brucified by: bde
|
62391 |
02-Jul-2000 |
dcs |
Enhance the optimization provided by pre-matching. Fix style bugs with previous commits.
At the time we search the pattern for the "must" string, we now compute the longest offset from the beginning of the pattern at which the must string might be found. If that offset is found to be infinite (through use of "+" or "*"), we set it to -1 to disable the heuristics applied later.
After we are done with pre-matching, we use that offset and the point in the text at which the must string was found to compute the earliest point at which the pattern might be found.
Special care should be taken here. The variable "start" is passed to the automata-processing functions fast() and slow() to indicate the point in the text at which they should start working from. The real beginning of the text is passed in a struct match variable m, which is used to check for anchors. That variable, though, is initialized with "start", so we must not adjust "start" before "m" is properly initialized.
Simple tests showed a speed increase from 100% to 400%, but they were biased in that regexec() was called for the whole file instead of line by line, and parenthized subexpressions were not searched for.
This change adds a single integer to the size of the "guts" structure, and does not change the ABI.
Further improvements possible:
Since the speed increase observed here is so huge, one intuitive optimization would be to introduce a bias in the function that computes the "must" string so as to prefer a smaller string with a finite offset over a larger one with an infinite offset. Tests have shown this to be a bad idea, though, as the cost of false pre-matches far outweights the benefits of a must offset, even in biased situations.
A number of other improvements suggest themselves, though:
* identify the cases where the pattern is identical to the must string, and avoid entering fast() and slow() in these cases.
* compute the maximum offset from the must string to the end of the pattern, and use that to set the point at which fast() and slow() should give up trying to find a match, and return then return to pre-matching.
* return all the way to pre-matching if a "match" was found and later invalidated by back reference processing. Since back references are evil and should be avoided anyway, this is of little use.
|
62232 |
29-Jun-2000 |
dcs |
Add Boyler-Moore algorithm to pre-matching test.
The BM algorithm works by scanning the pattern from right to left, and jumping as many characters as viable based on the text's mismatched character and the pattern's already matched suffix.
This typically enable us to test only a fraction of the text's characters, but has a worse performance than the straight-forward method for small patterns. Because of this, the BM algorithm will only be used if the pattern size is at least 4 characters.
Notice that this pre-matching is done on the largest substring of the regular expression that _must_ be present on the text for a succesful match to be possible at all.
For instance, "(xyzzy|grues)" will yield a null "must" substring, and, therefore, not benefit from the BM algorithm at all. Because of the lack of intelligence of the algorithm that finds the "must" string, things like "charjump|matchjump" will also yield a null string. To optimize that, "(char|match)jump" should be used.
The setup time (at regcomp()) for the BM algorithm will most likely outweight any benefits for one-time matches. Given the slow regex(3) we have, this is unlikely to be even perceptible, though.
The size of a regex_t structure is increased by 2*sizeof(char*) + 256*sizeof(int) + strlen(must)*sizeof(int). This is all inside the regex_t's "guts", which is allocated dynamically by regcomp(). If allocation of either of the two tables fail, the other one is freed. In this case, the straight-forward algorithm is used for pre-matching.
Tests exercising the code path affected have shown a speed increase of 50% for "must" strings of length four or five.
API and ABI remain unchanged by this commit.
The patch submitted on the PR was not used, as it was non-functional.
PR: 14342
|
48794 |
12-Jul-1999 |
nik |
Add $Id$, to make it simpler for members of the translation teams to track.
The $Id$ line is normally at the bottom of the main comment block in the man page, separated from the rest of the manpage by an empty comment, like so;
.\" $Id$ .\"
If the immediately preceding comment is a @(#) format ID marker than the the $Id$ will line up underneath it with no intervening blank lines. Otherwise, an additional blank line is inserted.
Approved by: bde
|
39327 |
16-Sep-1998 |
imp |
Replace memory leaking instances of realloc with non-leaking reallocf. In some cases replace if (a == null) a = malloc(x); else a = realloc(a, x); with simple reallocf(a, x). Per ANSI-C, this is guaranteed to be the same thing.
I've been running these on my system here w/o ill effects for some time. However, the CTM-express is at part 6 of 34 for the CAM changes, so I've not been able to do a build world with the CAM in the tree with these changes. Shouldn't impact anything, but...
|