Range-check array index before access

If we want to check the range of an array index, it makes much more sense to do it before accessing the corresponding array element, not afterwards.

There are two more instances of this in the clar code, fixes for which I offer in https://github.com/clar-test/clar/pull/115.

Johannes Schindelin (2):
diff: check range before dereferencing an array element
read-cache: check range before dereferencing an array element

 diff.c       | 2 +-
 read-cache.c | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

base-commit: 683c54c999c301c2cd6f715c411407c413b1d84e
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1887%2Fdscho%2Frange-check-array-index-before-access-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1887/dscho/range-check-array-index-before-access-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1887

gitgitgadget

From: Johannes Schindelin <[email protected]>

Before accessing an array element at a given index, we should make sure that the index is within the desired bounds, not afterwards, otherwise it may not make sense to even access the array element in the first place.

Pointed out by CodeQL's cpp/offset-use-before-range-check rule.

---
 diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index c89c15d98e0..18ba3060460 100644
@@ -892,7 +892,7 @@ static void fill_es_indent_data(struct emitted_diff_symbol *es)
 
 	/* skip any \v \f \r at start of indentation */
 	while (s[off] == '\f' || s[off] == '\v' ||
-	       (s[off] == '\r' && off < len - 1))
+	       (off < len - 1 && s[off] == '\r'))
 		off++;
 
 	/* calculate the visual width of indentation */

gitgitgadget

From: Johannes Schindelin <[email protected]>

Before accessing an array element at a given index, we should make sure that the index is within the desired bounds, not afterwards, otherwise it may not make sense to even access the array element in the first place.

Pointed out by CodeQL's cpp/offset-use-before-range-check rule.

---
 read-cache.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index e678c13e8f1..08ae66ad609 100644
@@ -2686,8 +2686,8 @@ static int ce_write_entry(struct hashfile *f, struct cache_entry *ce,
 		int common, to_remove, prefix_size;
 		unsigned char to_remove_vi[16];
 		for (common = 0;
-		     (ce->name[common] &&
-		      common < previous_name->len &&
+		     (common < previous_name->len &&
+		      ce->name[common] &&
 		      ce->name[common] == previous_name->buf[common]);
 		     common++)
 			; /* still matching */

gitgitgadget

Certainly we should, but...

  for (common = 0;
       ce->name[common] &&
       ce->name[common] == previous_name->buf[common];
       common++)

"Johannes Schindelin via GitGitGadget" <[email protected]>

If we want to check the range of an array index, it makes much more sense to do it before accessing the corresponding array element, not afterwards.

There are two more instances of this in the clar code, fixes for which I offer in https://github.com/clar-test/clar/pull/115.

Changes since v1:

* Clarified in the commit message of the second patch that this range-check technically was already right before the array access it wants to guard, but that it still makes sense to move that range-check to the beginning of the loop condition.

Johannes Schindelin (2):
diff: check range before dereferencing an array element
read-cache: check range before dereferencing an array element

 diff.c       | 2 +-
 read-cache.c | 4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

base-commit: 683c54c999c301c2cd6f715c411407c413b1d84e
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1887%2Fdscho%2Frange-check-array-index-before-access-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1887/dscho/range-check-array-index-before-access-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1887

Range-diff vs v1:

 1:  ddfb44ed924 = 1:  ddfb44ed924 diff: check range before dereferencing an array element
 2:  d4e94a243b0 ! 2:  73cae301293 read-cache: check range before dereferencing an array element

@@ Commit message
read-cache: check range before dereferencing an array element

Before accessing an array element at a given index, we should make sure
- that the index is within the desired bounds, not afterwards, otherwise
- it may not make sense to even access the array element in the first
- place.
+ that the index is within the desired bounds, otherwise it makes little
+ sense to access the array element in the first place.

- Pointed out by CodeQL's cpp/offset-use-before-range-check rule.
+ In this instance, testing whether ce->name[common] is the trailing NUL
+ byte is technically different from testing whether common is within
+ the bounds of previous_name. It is also redundant, as the range-check
+ guarantees that previous_name->buf[common] cannot be NUL and therefore
+ the condition ce->name[common] == previous_name->buf[common] would not
+ be met if ce->name[common] evaluated to NUL.
+
+ However, in the interest of reducing the cognitive load to reason about
+ the correctness of this loop (so that I can focus on interesting
+ projects again), I'll simply move the range-check to the beginning of
+ the loop condition and keep the redundant NUL check.
+
+ This acquiesces CodeQL's cpp/offset-use-before-range-check rule.

gitgitgadget

From: Johannes Schindelin <[email protected]>

Before accessing an array element at a given index, we should make sure that the index is within the desired bounds, not afterwards, otherwise it may not make sense to even access the array element in the first place.

Pointed out by CodeQL's cpp/offset-use-before-range-check rule.

---
 diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index c89c15d98e0..18ba3060460 100644
@@ -892,7 +892,7 @@ static void fill_es_indent_data(struct emitted_diff_symbol *es)
 
 	/* skip any \v \f \r at start of indentation */
 	while (s[off] == '\f' || s[off] == '\v' ||
-	       (s[off] == '\r' && off < len - 1))
+	       (off < len - 1 && s[off] == '\r'))
 		off++;
 
 	/* calculate the visual width of indentation */

gitgitgadget

From: Johannes Schindelin <[email protected]>

Before accessing an array element at a given index, we should make sure that the index is within the desired bounds, otherwise it makes little sense to access the array element in the first place.

In this instance, testing whether ce->name[common] is the trailing NUL byte is technically different from testing whether common is within the bounds of previous_name. It is also redundant, as the range-check guarantees that previous_name->buf[common] cannot be NUL and therefore the condition ce->name[common] == previous_name->buf[common] would not be met if ce->name[common] evaluated to NUL.

However, in the interest of reducing the cognitive load to reason about the correctness of this loop (so that I can focus on interesting projects again), I'll simply move the range-check to the beginning of the loop condition and keep the redundant NUL check.

This acquiesces CodeQL's cpp/offset-use-before-range-check rule.

---
 read-cache.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index e678c13e8f1..08ae66ad609 100644
@@ -2686,8 +2686,8 @@ static int ce_write_entry(struct hashfile *f, struct cache_entry *ce,
 		int common, to_remove, prefix_size;
 		unsigned char to_remove_vi[16];
 		for (common = 0;
-		     (ce->name[common] &&
-		      common < previous_name->len &&
+		     (common < previous_name->len &&
+		      ce->name[common] &&
 		      ce->name[common] == previous_name->buf[common]);
 		     common++)
 			; /* still matching */

gitgitgadget

Exactly - we do not want to count CR as being part of the indentation if it is followed by LF. It has been a while since I wrote this code but my recollection is that each string ends with "\n\0". From what I remember to detect moved lines we have to buffer the output from xdl_diff() and so copy each line with xmemdupz() and somewhere the xdiff machinery adds '\n' to incomplete lines when it generates the diff.

Best Wishes

Phillip

"Johannes Schindelin via GitGitGadget" <[email protected]>

At least this part should say this is a false positive, forcing us to make an unnecessary change to help future developers who are running "git blame" and "git log -p" to find out why only s[off] checked against CR needs this check _before_ it, while checking against other values needs _no_ check.

In other words, the first paragraph of the proposed log message is a total red herring. We are accessing an array element at a given index 'off' in the original, we are still accessing the same element in the updated code, and we know the index is within the array bounds. If the condition were "We want to skip CR only at odd places", we would have written

	|| (s[off] == '\r' && (off & 01))

or

	|| ((off & 01) || s[off] == '\r')

and both are equally valid. (off < len -1) should be no different.

Thanks, I think this explanation works, and the patch looks fine. (I didn't dig deeply into patch 1, but I agree with Junio's analysis that it is also a false positive).

-Peff

I think (1) working around a rare false positive to help us use an otherwise mostly useful tool is a worthy thing to do, and (2) when we need to make a workaround for a false positive, we should mark a change to do so as such. And I agree with you that this step in the updated form, both the change in the patch and the proposed log message do their job.

Thanks, both. Will mark this one for 'next'.

Note that I think [1/2] needs similar updates relative to the initial iteration, but since these two patches do not depend on each other, I'll fast track this step without waiting updates to the other one.

From: Johannes Schindelin <[email protected]>

Before accessing an array element at a given index, it should be verified that the index is within the desired bounds, not afterwards, otherwise it may not make sense to even access the array element in the first place. This is the point of CodeQL's cpp/offset-use-before-range-check rule.

This CodeQL rule unfortunately is also triggered by the fill_es_indent_data() code, even though the condition off < len - 1 does not even need to guarantee that the offset is in bounds (s points to a NUL-terminated string, for which s[off] == '\r' would fail before running out of bounds).

Let's work around this rare false positive to help us use an otherwise mostly useful tool is a worthy thing to do.

---
Range-check array index before access

If we want to check the range of an array index, it makes much more sense to do it before accessing the corresponding array element, not afterwards.

There are two more instances of this in the clar code, fixes for which I offer in https://github.com/clar-test/clar/pull/115.

Changes since v2:

* Rebased on top of js/range-check-codeql-workaround.
* Rephrased the commit message.

Changes since v1:

* Clarified in the commit message of the second patch that this range-check technically was already right before the array access it wants to guard, but that it still makes sense to move that range-check to the beginning of the loop condition.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1887%2Fdscho%2Frange-check-array-index-before-access-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1887/dscho/range-check-array-index-before-access-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/1887

Range-diff vs v2:

1: ddfb44ed924 ! 1: 3c6e2647863 diff: check range before dereferencing an array element
@@ Metadata
## Commit message ##
diff: check range before dereferencing an array element

- Before accessing an array element at a given index, we should make sure
- that the index is within the desired bounds, not afterwards, otherwise
- it may not make sense to even access the array element in the first
- place.
+ Before accessing an array element at a given index, it should be
+ verified that the index is within the desired bounds, not afterwards,
+ otherwise it may not make sense to even access the array element in the
+ first place. This is the point of CodeQL's
+ cpp/offset-use-before-range-check rule.

- Pointed out by CodeQL's cpp/offset-use-before-range-check rule.
+ This CodeQL rule unfortunately is also triggered by the
+ fill_es_indent_data() code, even though the condition off < len - 1
+ does not even need to guarantee that the offset is in bounds (s points
+ to a NUL-terminated string, for which s[off] == '\r' would fail before
+ running out of bounds).
+
+ Let's work around this rare false positive to help us use an otherwise
+ mostly useful tool is a worthy thing to do.

2: 73cae301293 < -: ----------- read-cache: check range before dereferencing an array element

 diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index c89c15d98e0..18ba3060460 100644
@@ -892,7 +892,7 @@ static void fill_es_indent_data(struct emitted_diff_symbol *es)
 
 	/* skip any \v \f \r at start of indentation */
 	while (s[off] == '\f' || s[off] == '\v' ||
-	       (s[off] == '\r' && off < len - 1))
+	       (off < len - 1 && s[off] == '\r'))
 		off++;
 
 	/* calculate the visual width of indentation */

base-commit: 0f558141ed3b93b393151367b9569446cd24caab

gitgitgadget

"Johannes Schindelin via GitGitGadget" <[email protected]>

Thanks. I have almost forgotten about this one. The above explanation works very well.

Since this is marked as fixing a false positive, and since it presumably _does_ fix the false positive in practice, this is OK with me.

But...

  while (off < len - 1 &&
         (s[off] == '\f' || s[off] == '\v' || s[off] == '\r')

But doesn't it change the semantics?

s[off] == '\f', even if off is at the end of the string, i.e. (off == len - 1), must trigger the off++ increment.

On the other hand, CR that is the part of CRLF at the end of line is *not* treated like other funny whitespace control characters. This "is off not at the end of line, if so check CR" comparison is about that.

Ah, you're right. I was reading the offset check as "are we past the end of string" (guided by CodeQL's complaint), and if that were the case the logic would apply equally to all values we are checking.

But that is not what is going on at all. The offset check is for "len - 1", and so is "do not do this one CR match for the final character of the string". And thus applying it elsewhere is wrong.

And CodeQL's false positive is doubly wrong. We do not even need to say "the string is NUL-terminated, so it is OK in this case to look past the end-of-string". The check is not even a string bounds check at all.

-Peff

Exactly.

That is what makes it hard to give a reasonable explanation in the log message, which I thought that Dscho did a much better job in this iteration.

Thanks.