Re: generic strncpy - off-by-one error
From: Timothy Miller
Date: Fri Aug 15 2003 - 12:32:38 EST
Peter Kjellerstedt wrote:
While I can understand that certain architectures may benefit
from that alteration, I am curious as to what SPECIFICALLY it
is doing that is different. How do they differ?
I do not know if this will give you anything, but here is
the disassembled CRIS version of your first while loop
(note that the branch instructions have one delay slot,
and that dest, src and count are in $r10, $r11 and $r12):
while (count && *src)
805d8: 6cc6 test.d $r12
805da: 1830 beq 805f4
> 805dc: 6a96 move.d $r10,$r9
Ok, test count and exit if count is zero.
I take it that this move is the copy of the dst to a temporary variable?
805de: 8b0b test.b [$r11]
805e0: 1230 beq 805f4
805e2: 0f05 nop
Test *s and exit if zero.
{
count--;
805e4: 81c2 subq 1,$r12
*tmp++ = *src++;
805e6: 4bde move.b [$r11+],$r13
Fetch *s and increment. This is redundant. Why didn't it know to fetch
*s above and keep it in a register?
805e8: 6cc6 test.d $r12
805ea: 0830 beq 805f4
805ec: c9df move.b $r13,[$r9+]
Test count and exit if count is zero. Why is it doing this again? Why
not jump back to the top? Oh, wait... in that case, for the loop to
exit, it would jump to the top and then jump back to past the end,
rather than just failing one branch.
I see that the delay slot was filled with the store to *dst. But is
there also some pipeline latency that makes this worth while?
805ee: 8b0b test.b [$r11]
805f0: f320 bne 805e4
805f2: 0f05 nop
Test *src AGAIN and loop if nonzero. Redundant.
}
And here is my first while loop:
while (count)
8062c: 6cc6 test.d $r12
8062e: 1030 beq 80640
80630: 6a96 move.d $r10,$r9
Test count and bypass if zero. Also, copy dst.
{
count--;
if (!(*tmp++ = *src++))
80632: 4bde move.b [$r11+],$r13
80634: c9db move.b $r13,[$r9]
Move data
80636: 890f test.b [$r9+]
Interesting how (a) it moved the increment to the test, and (b) it makes
a redundant read of the dest.
Does this arch not get condition codes from things other than test and
compare?
And why didn't it test $r13 instead? Wouldn't that have been a lot more
efficient?
80638: 0630 beq 80640
8063a: 81c2 subq 1,$r12
Exit on zero and decrement count.
break;
8063c: f520 bne 80632
8063e: 0f05 nop
Loop.
}
Also note that your version
of the second loop needs an explicit comparison with -1,
whereas mine uses an implicit comparison with 0.
I don't understand why you say I need an explicit comparison
with -1. My first loop exits either with the number of bytes
remaining in the buffer or with zero if it's copied count
number of bytes.
I was talking about the second loop. The object code the compiler
produces for your version actually tests the count variable after
it decreases it, which is why it tests for -1.
Why does it do that? Is that somehow more optimal? Why doesn't it test
BEFORE it decrements? Isn't that more straightforward?
In any event, couldn't that be fixed by moving the decrement into the loop?
The second loop WOULD require a comparison with -1 IF the
"count--" were not inside of the loop body. As it IS in the
loop body, there is no need for that. My second loop has an
implicit comparison against zero.
Hmm, your second loop from above looks like:
while (n--) {
*s++ = 0;
}
whereas mine looks like:
while (count) {
*tmp++ = '\0';
count--;
}
You seem to be referring to my version, where what you say is true.
And what I was saying was that since what the while should test is the
value before the decrement, I assumed that the test would be before the
decrement.
I agree that this is definately a more elegant look to the
code, and I would prefer what you have done here. But what
puzzles me is that this is functionally and logically
equivalent to my code.
So, this code:
for (A; B; C) {}
is the same as this:
A;
while (B) {
...
C;
}
So why is it that this mere syntactic difference causes the
compiler to produce a better result?
I wish I new. Actually in the CRIS case, it seems to be an
optimizer thing. If I change your first loop from
while (n && *s2) {
n--;
*s++ = *s2++;
}
to
while (n && *s2) {
*s++ = *s2++;
n--;
}
it gives the expected object code, i.e., the same as my
first for loop. So here is a modified version of your
code that gives exactly the same object code (for CRIS)
as my version with the for loops:
A decent optimizer should know that the "n--" and the "*s++ = *s2++" are
independent and migrate them to optimal positions.
Furthermore, I put the "n--" first because I assumed that the compiler
might be stupid about it. The idea is to order the statements so that
the results of a given instruction are being computed while the next one
is being decoded.
My assumption was that the code would branch back to the loop test
(rather than make a second one) at the end of the loop and then test n.
Therefore, decrementing n earlier would be a win in terms of having
the result earlier for the test, reducing pipline stall.
char *strncpy(char * s1, const char * s2, size_t n)
{
register char *s = s1;
while (n && *s2) {
*s++ = *s2++;
n--;
}
while (n) {
*s++ = 0;
n--;
}
return s1;
}
//Peter
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/