Diff for "roelkluin/gres_examples" - Linux Kernel Newbies

Differences between revisions 1 and 7 (spanning 6 versions)

To search for an erroneous pattern like this:

for (i = 0; i < n; i++) {}
...
if (i > n) ...

This is wrong because at the end of the loop i equals n and cannot be greater than n. To match this:

gres -A40 "^ for \(" \
"for \( (@V) = @d ; \1 < @d ; \1 \+\+ \)
    \{.8.\}
@n
if \( \1 > \3 \)" | less

The first string is used to get the git grep query. To see what is queried for execute

bli2 "^ for \("

It will print the extended regexp used in the query.

@V is translated to [[:alpha:]_]+[[:alnum:]_]*, which matches a local variable. @d matches any number in several formats, therefore it contains parentheses, that's why to match the second @d we use \3 as a back-reference. \{.8.\} matches anything between curly brackets, up to 8 nested curly brackets.

This results after about 10 seconds in a match:

---[ vi drivers/mmc/host/s3cmci.c +1209 ]---
        /* Set clock */
        for (mci_psc = 0; mci_psc < 255; mci_psc++) {
                ...
        }

        if (mci_psc > 255)
                mci_psc = 255;
        ...

Quite harmless so I left it.

I left this simple for explanatory reasons. A more advanced query to catch these errors, and others, can be found here gres_tests/loops.

-  ⇤ ← Revision 1 as of 2009-12-30 11:24:56 → 
  Size: 3837
  Editor: d133062
  Comment:
+   ← Revision 7 as of 2017-12-30 01:30:26 → ⇥
  Size: 1245
  Editor: localhost
  Comment: converted to 1.6 markup
-Deletions are marked like this.
+Additions are marked like this.
 Line 7:
-This is wrong because at the end of the loop i equals n and cannot be greater than n. The most simple way to match this is:
+This is wrong because at the end of the loop i equals n and cannot be greater than n. To match this:
 Line 10:
-"for \( (@V) = @d ;
         \1 < @d ;
         \1 \+\+ \)
+"for \( (@V) = @d ; \1 < @d ; \1 \+\+ \)
-Line 15:
+Line 13:
-if \( \1 > \3 \)"
+if \( \1 > \3 \)" | less
-Line 17:
+Line 15:
-Also, @d has parentheses, that's why we have to use \3, not \2 for back-reference to match the second @d.
+The first string is used to get the git grep query. To see what is queried for execute
{{{
bli2 "^ for \("
}}}
It will print the extended regexp used in the query.
-Line 19:
+Line 21:
-For me - I currently have kernel version 2.6.33-rc2 - this results after about 10 seconds in a match (simplified here):
+@V is translated to {{{[[:alpha:]_]+[[:alnum:]_]*}}}, which matches a local variable. @d matches any number in several formats, therefore it contains parentheses, that's why to match the second @d we use \3 as a back-reference. {{{\{.8.\}}}} matches anything between curly brackets, up to 8 nested curly brackets.

This results after about 10 seconds in a match:
-Line 31:
+Line 35:
-Quite harmless so I left it. Let's extend the example, similar errors will occur with:
{{{
for (i = 0; i != MAX; i++) {}
...
if (i <= MAX) ...
}}}
+Quite harmless so I left it.
-Line 38:
+Line 37:
-To catch such errors we could use a pattern like this:
{{{
gres -A40 "^ for \(" \
"for \( (@V) = (@d|@K) ;
         \1 (<|\!=) (@d|@K) ;
         (\+\+ \1|\1 \+\+|\1 = \1 \+ 1|\1 = 1 \+ \1) \)
    \{.8.\}
@n
if \( \1 (>|<=) \5 \)"
}}}
The @K matches definitions. This did not result in more errors in this kernel version, so lets extend it even more. Similar problems may occur when we have a pattern like:
{{{
while (foo() && ++i < MAX && bar()) {}
...
if (baz() || i > MAX) ...
}}}

This can be matched by:
{{{
gres -A40 "^ (for|while) \(" \
"(for \([^;]*;|while \() (\(-..\)[&|])*
         \+* (@V) (<|\!=) (@d|@w) ([&|]\(-..\))*
         (; (\+\+ \6|\6 \+\+|\6 = \6 \+ 1|\6 = 1 \+ \6))? \)
    \{.8.\}
@n
if \( (\(-..\)[&|])* \6 (>|<=) \8 ([&|]\(-..\))* \)"
}}}

This results (after about half a minute on my computer) in the additional matches:
{{{
---[ vi arch/sparc/mm/init_64.c +786 ]---
        ...
        start += PAGE_SIZE;
        while (start < end) {
                ...
                if (...)
                        break;
                start += PAGE_SIZE;
        }

        if (start > end)
                start = end;
        ...
---[ vi drivers/atm/horizon.c +626 ]---
        while (...) ...
        ...
        if (...) ...
        ...
        while (div < CR_MAXD) {
                div++;
                if (...) {
                        ...
                        goto got_it;
                }
        }
got_it:
        if (div > CR_MAXD || ...) ...
}}}
The second one was difficult to see in the output due to a prior while loop. The first one, in contrast, is a false positive: the addition of PAGE_SIZE can cause {{{`}}}start' to be bigger than {{{`}}}end'. In the case of a while loop the chosen pattern with {{{`}}}\+*' allows a postfix increment, but 
does not ensure that an increment occurs, an addition can occur just as well. We can exclude the false positive by adding an exclusion pattern:
{{{
gres -A40 "^ (for|while) \(" \
"while \( (\(-..\)[&|])* (@V) (<|\!=) (@d|@w) ([&|]\(-..\))* \) (\{\{-..\} \n)? \5 ([+*|]=|= \5 \+)@n
if \( (\(-..\)[&|])* \5 (>|<=) \7 ([&|]\(-..\))* \)" \
"(for \([^;]*;|while \() (\(-..\)[&|])*
         \+* (@V) (<|\!=) (@d|@w) ([&|]\(-..\))*
         (; (\+\+ \6|\6 \+\+|\6 = \6 \+ 1|\6 = 1 \+ \6))? \)
    \{.8.\}
@n
if \( (\(-..\)[&|])* \6 (>|<=) \8 ([&|]\(-..\))* \)"
}}}

Similarly one can define an erroneous pattern for decrementing loops:
{{{
gres -A40 "^ (for|while) \(" \
"while \( (\(-..\)[&|])* (@V) (>|\!=) (@d|@w) ([&|]\(-..\))* \) (\{\{-..\} \n)? \5 (-=|= \5 -)@n
if \( (\(-..\)[&|])* \5 (<|>=) \7 ([&|]\(-..\))* \)" \
"(for \([^;]*;|while \() (\(-..\)[&|])*
         -* (@V) (>|\!=) (@d|@w) ([&|]\(-..\))*
         (; (-- \6|\6 --|\6 = \6 - 1|\6 = 1 - \6))? \)
    \{.8.\}
@n
if \( (\(-..\)[&|])* \6 (<|>=) \8 ([&|]\(-..\))* \)"
}}}
+I left this simple for explanatory reasons. A more advanced query to catch these errors, and others, can be found here [[roelkluin/gres_tests/loops|gres_tests/loops]].