[Support] unsafe pointer arithmetic in llvm_regcomp()

[brad]

Summary

llvm/lib/Support/regcomp.c is borrowed from OpenBSD, to which the following issue has been reported and fixed. (report and patch in https://marc.info/?l=openbsd-tech&m=160923823113340&w=2 )

regcomp.c uses the "start + count < end" idiom to check that there are "count" bytes available in an array of char "start" and "end" both point to.

This is fine, unless "start + count" goes beyond the last element of the array. In this case, pedantic interpretation of the C standard makes the comparison of such a pointer against "end" undefined, and optimizers from hell will happily remove as much code as possible because of this.

An example of this occurs in regcomp.c's bothcases(), which defines bracket[3], sets "next" to "bracket" and "end" to "bracket + 2". Then it invokes p_bracket(), which starts with "if (p->next + 5 < p->end)"...

Because bothcases() and p_bracket() are static functions in regcomp.c, there is a real risk of miscompilation if aggressive inlining happens. The following diff rewrites the "start + count < end" constructs into "end - start > count". Assuming "end" and "start" are always pointing in the array (such as "bracket[3]" above), "end - start" is well-defined and can be compared without trouble.

As a bonus, MORE2() implies MORE() therefore SEETWO() can be simplified a bit.

From bug report: https://bugs.llvm.org/show_bug.cgi?id=48649

[brad]

ping.

[brad]

ping ping.

[vitalybuka]

Can you please clang format according to premerge checks?

llvm/lib/Support/regcomp.c

252

I understand all but this line. I guess it had no UB there.

[MaskRay]

Thanks for porting the fix.

The clang-format diagnostic is because of TAB. The OpenBSD version (https://github.com/openbsd/src/blob/master/lib/libc/regex/regcomp.c) uses TAB and our copy probably should just match.

I verified that this does port the OpenBSD change, but please make sure @vitalybuka is happy as well.

llvm/lib/Support/regcomp.c

252

I think this clause applies
https://www.iso-9899.info/n1570.html#6.5.6p8 "... If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."

There was a UB.

[MaskRay]

Context not available.

In the future please include full context in the patch. See https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

[brad]

Updated with full context.

[vitalybuka]

llvm/lib/Support/regcomp.c

252

I am aware of this rule, but I assume that end and next always "point to elements of the same array object, or one past the last element"
So old MORE2 violates the rule, but MORE does not.

[vitalybuka]

llvm/lib/Support/regcomp.c

252

I am fine if it 's done just for consistency. But I would appreciate explanation if there is UB in MORE() as well.

[brad]

@MaskRay ?

[MaskRay]

In D97129#3289390, @brad wrote:

@MaskRay ?

I already LGTMed. What did you want me to do ? :)

[brad]

In D97129#3289437, @MaskRay wrote:

In D97129#3289390, @brad wrote:

@MaskRay ?

I already LGTMed. What did you want me to do ? :)

@vitalybuka asked a question. Just wondering if there should be further discussion or should I go ahead?

llvm/lib/Support/regcomp.c

 static char nuls[10];   /* place to point scanner in event of error */
 
 /*
  * macros for use with parse structure
  * BEWARE:  these know that the parse structure is named `p' !!!
  */
 #define PEEK()  (*p->next)
 #define PEEK2() (*(p->next+1))
-#define MORE()  (p->next < p->end)
-#define MORE2() (p->next+1 < p->end)
+#define MORE()  (p->end - p->next > 0)
+#define MORE2() (p->end - p->next > 1)
 #define SEE(c)  (MORE() && PEEK() == (c))
-#define SEETWO(a, b)  (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
+#define SEETWO(a, b)  (MORE2() && PEEK() == (a) && PEEK2() == (b))
 #define EAT(c)  ((SEE(c)) ? (NEXT(), 1) : 0)
 #define EATTWO(a, b)  ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
 #define NEXT()  (p->next++)
 #define NEXT2() (p->next += 2)
 #define NEXTn(n)  (p->next += (n))
 #define GETNEXT() (*p->next++)
 #define SETERROR(e) seterr(p, (e))
 #define REQUIRE(co, e)  (void)((co) || SETERROR(e))

  */
 static void
 p_bracket(struct parse *p)
 {
   cset *cs;
   int invert = 0;
 
   /* Dept of Truly Sickening Special-Case Kludges */
-  if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
+  if (p->end - p->next > 5) {
+    if (strncmp(p->next, "[:<:]]", 6) == 0) {
       EMIT(OBOW, 0);
       NEXTn(6);
       return;
     }
-  if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
+    if (strncmp(p->next, "[:>:]]", 6) == 0) {
       EMIT(OEOW, 0);
       NEXTn(6);
       return;
     }
+  }
 
   if ((cs = allocset(p)) == NULL) {
     /* allocset did set error status in p */
     return;
   }
 
   if (EAT('^'))
     invert++; /* make note to invert set at end */