[cocci] [PATCH 0/3] coccinelle: improve performance of mini_lock, double_lock and minmax

[cocci] [PATCH 0/3] coccinelle: improve performance of mini_lock, double_lock and minmax

[Sang-Heon Jeon]

mini_lock, double_lock and minmax spend most of their time
searching files that have nothing to report. This series collects
the candidates first and runs the expensive rules only when one
exists.

For mini_lock and double_lock this also restores lost coverage.
For example, kernel/bpf/verifier.c exceeded the 200 second timeout
set by .cocciconfig, and coccicheck silently skipped the file.

The benchmark environment and command are as follows.
- AMD Ryzen 7 8845HS, 16 threads, 32 GiB RAM
- Ubuntu 24.04, spatch 1.1.1
- spatch -D report --very-quiet --no-includes --include-headers --cocci-file <script> <file>
  - timeout 200 is added for the whole tree runs

              kernel/bpf/verifier.c    whole tree
  mini_lock   812s -> 2.6s             1.5h -> 1.4h
  double_lock 12.2s -> 0.9s            2.0h -> 1.6h
  minmax      9.0s -> 1.7s             10.2h -> 5.5h

A report-mode run over every .c file in the tree produces
identical output for each script.

No functional change.

Sang-Heon Jeon (3):
  coccinelle: mini_lock: improve performance when searching loops
  coccinelle: double_lock: improve performance when no double lock
    exists
  coccinelle: misc: minmax: improve performance when no candidate exists

 scripts/coccinelle/locks/double_lock.cocci | 15 +++++++++++++-
 scripts/coccinelle/locks/mini_lock.cocci   | 24 ++++++++++++++++++++--
 scripts/coccinelle/misc/minmax.cocci       | 24 +++++++++++++++++-----
 3 files changed, 55 insertions(+), 8 deletions(-)

-- 
2.43.0

[PATCH 0/3] coccinelle: improve performance of mini_lock, double_lock and minmax

[Sang-Heon Jeon]

mini_lock, double_lock and minmax spend most of their time
searching files that have nothing to report. This series collects
the candidates first and runs the expensive rules only when one
exists.

For mini_lock and double_lock this also restores lost coverage.
For example, kernel/bpf/verifier.c exceeded the 200 second timeout
set by .cocciconfig, and coccicheck silently skipped the file.

The benchmark environment and command are as follows.
- AMD Ryzen 7 8845HS, 16 threads, 32 GiB RAM
- Ubuntu 24.04, spatch 1.1.1
- spatch -D report --very-quiet --no-includes --include-headers --cocci-file <script> <file>
  - timeout 200 is added for the whole tree runs

              kernel/bpf/verifier.c    whole tree
  mini_lock   812s -> 2.6s             1.5h -> 1.4h
  double_lock 12.2s -> 0.9s            2.0h -> 1.6h
  minmax      9.0s -> 1.7s             10.2h -> 5.5h

A report-mode run over every .c file in the tree produces
identical output for each script.

No functional change.

Sang-Heon Jeon (3):
  coccinelle: mini_lock: improve performance when searching loops
  coccinelle: double_lock: improve performance when no double lock
    exists
  coccinelle: misc: minmax: improve performance when no candidate exists

 scripts/coccinelle/locks/double_lock.cocci | 15 +++++++++++++-
 scripts/coccinelle/locks/mini_lock.cocci   | 24 ++++++++++++++++++++--
 scripts/coccinelle/misc/minmax.cocci       | 24 +++++++++++++++++-----
 3 files changed, 55 insertions(+), 8 deletions(-)

-- 
2.43.0

[cocci] [PATCH 1/3] coccinelle: mini_lock: improve performance when searching loops

[Sang-Heon Jeon]

The 'looped' rule collects the returns inside a for loop to
prevent 'err' from reporting them. It searches every for loop in
the file, and on files with large loop bodies the search explodes.

For example, kernel/bpf/verifier.c runs for over 200 seconds,
almost entirely in 'looped' according to --profile. Since the
kernel .cocciconfig sets a 200 second timeout, coccicheck silently
skips the file.

To avoid this, collect the candidate returns first, so that
'looped' checks only those positions. 'err' then excludes what
'looped' found.

Every return that 'err' can report is also a candidate, so the
same returns are excluded as before and the output does not change.
A report-mode run over every .c file in the tree produces identical
output.

So verifier.c now finishes well within the timeout, in a few
seconds.

Signed-off-by: Sang-Heon Jeon <ekffu200098@gmail.com>
---
 scripts/coccinelle/locks/mini_lock.cocci | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

diff --git a/scripts/coccinelle/locks/mini_lock.cocci b/scripts/coccinelle/locks/mini_lock.cocci
index 71065d8a5d54..54e06cced63b 100644
--- a/scripts/coccinelle/locks/mini_lock.cocci
+++ b/scripts/coccinelle/locks/mini_lock.cocci
@@ -53,11 +53,31 @@ spin_lock_irq@p1
 spin_lock_irqsave@p1
 ) (E1@p,...);
 
-@looped@
+@err_candidate exists@
+expression E1;
+position prelocked.p;
+position up != prelocked.p1;
+position rc;
+identifier lock,unlock;
+@@
+
+lock(E1@p,...);
+... when != E1
+    when any
+if (...) {
+  ... when != E1
+  return@rc ...;
+}
+... when != E1
+    when any
+unlock@up(E1,...);
+
+@looped depends on err_candidate@
+position err_candidate.rc;
 position r;
 @@
 
-for(...;...;...) { <+... return@r ...; ...+> }
+for(...;...;...) { <+... return@rc@r ...; ...+> }
 
 @err exists@
 expression E1;
-- 
2.43.0

[PATCH 1/3] coccinelle: mini_lock: improve performance when searching loops

[Sang-Heon Jeon]

The 'looped' rule collects the returns inside a for loop to
prevent 'err' from reporting them. It searches every for loop in
the file, and on files with large loop bodies the search explodes.

For example, kernel/bpf/verifier.c runs for over 200 seconds,
almost entirely in 'looped' according to --profile. Since the
kernel .cocciconfig sets a 200 second timeout, coccicheck silently
skips the file.

To avoid this, collect the candidate returns first, so that
'looped' checks only those positions. 'err' then excludes what
'looped' found.

Every return that 'err' can report is also a candidate, so the
same returns are excluded as before and the output does not change.
A report-mode run over every .c file in the tree produces identical
output.

So verifier.c now finishes well within the timeout, in a few
seconds.

Signed-off-by: Sang-Heon Jeon <ekffu200098@gmail.com>
---
 scripts/coccinelle/locks/mini_lock.cocci | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

diff --git a/scripts/coccinelle/locks/mini_lock.cocci b/scripts/coccinelle/locks/mini_lock.cocci
index 71065d8a5d54..54e06cced63b 100644
--- a/scripts/coccinelle/locks/mini_lock.cocci
+++ b/scripts/coccinelle/locks/mini_lock.cocci
@@ -53,11 +53,31 @@ spin_lock_irq@p1
 spin_lock_irqsave@p1
 ) (E1@p,...);
 
-@looped@
+@err_candidate exists@
+expression E1;
+position prelocked.p;
+position up != prelocked.p1;
+position rc;
+identifier lock,unlock;
+@@
+
+lock(E1@p,...);
+... when != E1
+    when any
+if (...) {
+  ... when != E1
+  return@rc ...;
+}
+... when != E1
+    when any
+unlock@up(E1,...);
+
+@looped depends on err_candidate@
+position err_candidate.rc;
 position r;
 @@
 
-for(...;...;...) { <+... return@r ...; ...+> }
+for(...;...;...) { <+... return@rc@r ...; ...+> }
 
 @err exists@
 expression E1;
-- 
2.43.0

[cocci] [PATCH 2/3] coccinelle: double_lock: improve performance when no double lock exists

[Sang-Heon Jeon]

The 'balanced' rule collects the locks that are taken and released
under the same condition, to prevent them from being reported as a
double lock. It runs on every file that contains a lock call.

To avoid this, collect the double-lock candidates first, so that
'balanced' runs only when one exists. The report then excludes what
'balanced' found.

Every double lock that can be reported is also a candidate, so the
same reports are made as before and the output does not change. A
report-mode run over every .c file in the tree produces identical
output.

Signed-off-by: Sang-Heon Jeon <ekffu200098@gmail.com>
---
 scripts/coccinelle/locks/double_lock.cocci | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

diff --git a/scripts/coccinelle/locks/double_lock.cocci b/scripts/coccinelle/locks/double_lock.cocci
index 619cfc714409..381060849a7b 100644
--- a/scripts/coccinelle/locks/double_lock.cocci
+++ b/scripts/coccinelle/locks/double_lock.cocci
@@ -38,7 +38,20 @@ write_lock@p1
 write_trylock@p1
 ) (E1@p,...);
 
-@balanced@
+@r_candidate exists@
+expression x <= locked.E1;
+expression locked.E1;
+expression E2;
+identifier lock;
+position locked.p,p1,p2;
+@@
+
+lock@p1 (E1@p,...);
+... when != E1
+    when != \(x = E2\|&x\)
+lock@p2 (E1,...);
+
+@balanced depends on r_candidate@
 position p1 != locked.p1;
 position locked.p;
 identifier lock,unlock;
-- 
2.43.0

[PATCH 2/3] coccinelle: double_lock: improve performance when no double lock exists

[Sang-Heon Jeon]

The 'balanced' rule collects the locks that are taken and released
under the same condition, to prevent them from being reported as a
double lock. It runs on every file that contains a lock call.

To avoid this, collect the double-lock candidates first, so that
'balanced' runs only when one exists. The report then excludes what
'balanced' found.

Every double lock that can be reported is also a candidate, so the
same reports are made as before and the output does not change. A
report-mode run over every .c file in the tree produces identical
output.

Signed-off-by: Sang-Heon Jeon <ekffu200098@gmail.com>
---
 scripts/coccinelle/locks/double_lock.cocci | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

diff --git a/scripts/coccinelle/locks/double_lock.cocci b/scripts/coccinelle/locks/double_lock.cocci
index 619cfc714409..381060849a7b 100644
--- a/scripts/coccinelle/locks/double_lock.cocci
+++ b/scripts/coccinelle/locks/double_lock.cocci
@@ -38,7 +38,20 @@ write_lock@p1
 write_trylock@p1
 ) (E1@p,...);
 
-@balanced@
+@r_candidate exists@
+expression x <= locked.E1;
+expression locked.E1;
+expression E2;
+identifier lock;
+position locked.p,p1,p2;
+@@
+
+lock@p1 (E1@p,...);
+... when != E1
+    when != \(x = E2\|&x\)
+lock@p2 (E1,...);
+
+@balanced depends on r_candidate@
 position p1 != locked.p1;
 position locked.p;
 identifier lock,unlock;
-- 
2.43.0

[cocci] [PATCH 3/3] coccinelle: misc: minmax: improve performance when no candidate exists

[Sang-Heon Jeon]

The rules that report an opencoded min() or max() search every
function body, even when the file contains nothing to find.

To avoid this, collect the candidates first and run the search only
when one exists. A candidate is any conditional expression whose
condition is a comparison.

Every opencoded min() or max() is also a candidate, so the same
opportunities are reported as before and the output does not
change. A report-mode run over every .c file in the tree produces
identical output.

Signed-off-by: Sang-Heon Jeon <ekffu200098@gmail.com>
---
 scripts/coccinelle/misc/minmax.cocci | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

diff --git a/scripts/coccinelle/misc/minmax.cocci b/scripts/coccinelle/misc/minmax.cocci
index ca4830ae3042..93c074b9439f 100644
--- a/scripts/coccinelle/misc/minmax.cocci
+++ b/scripts/coccinelle/misc/minmax.cocci
@@ -17,7 +17,21 @@ virtual org
 virtual context
 virtual patch
 
-@rmax depends on !patch@
+@max_candidate@
+expression E1, E2, E3, E4;
+binary operator cmp = {>, >=};
+@@
+
+	(E1 cmp E2 ? E3 : E4)
+
+@min_candidate@
+expression E1, E2, E3, E4;
+binary operator cmp = {<, <=};
+@@
+
+	(E1 cmp E2 ? E3 : E4)
+
+@rmax depends on !patch && max_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {>, >=};
@@ -51,7 +65,7 @@ func(...)
 }
 
 // Ignore errcode returns.
-@errcode@
+@errcode depends on min_candidate@
 position p;
 identifier func;
 expression x;
@@ -65,7 +79,7 @@ func(...)
 	...>
 }
 
-@rmin depends on !patch@
+@rmin depends on !patch && min_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {<, <=};
@@ -98,7 +112,7 @@ func(...)
 	...>
 }
 
-@pmax depends on patch@
+@pmax depends on patch && max_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {>=, >};
@@ -131,7 +145,7 @@ func(...)
 	...>
 }
 
-@pmin depends on patch@
+@pmin depends on patch && min_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {<=, <};
-- 
2.43.0

[PATCH 3/3] coccinelle: misc: minmax: improve performance when no candidate exists

[Sang-Heon Jeon]

The rules that report an opencoded min() or max() search every
function body, even when the file contains nothing to find.

To avoid this, collect the candidates first and run the search only
when one exists. A candidate is any conditional expression whose
condition is a comparison.

Every opencoded min() or max() is also a candidate, so the same
opportunities are reported as before and the output does not
change. A report-mode run over every .c file in the tree produces
identical output.

Signed-off-by: Sang-Heon Jeon <ekffu200098@gmail.com>
---
 scripts/coccinelle/misc/minmax.cocci | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

diff --git a/scripts/coccinelle/misc/minmax.cocci b/scripts/coccinelle/misc/minmax.cocci
index ca4830ae3042..93c074b9439f 100644
--- a/scripts/coccinelle/misc/minmax.cocci
+++ b/scripts/coccinelle/misc/minmax.cocci
@@ -17,7 +17,21 @@ virtual org
 virtual context
 virtual patch
 
-@rmax depends on !patch@
+@max_candidate@
+expression E1, E2, E3, E4;
+binary operator cmp = {>, >=};
+@@
+
+	(E1 cmp E2 ? E3 : E4)
+
+@min_candidate@
+expression E1, E2, E3, E4;
+binary operator cmp = {<, <=};
+@@
+
+	(E1 cmp E2 ? E3 : E4)
+
+@rmax depends on !patch && max_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {>, >=};
@@ -51,7 +65,7 @@ func(...)
 }
 
 // Ignore errcode returns.
-@errcode@
+@errcode depends on min_candidate@
 position p;
 identifier func;
 expression x;
@@ -65,7 +79,7 @@ func(...)
 	...>
 }
 
-@rmin depends on !patch@
+@rmin depends on !patch && min_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {<, <=};
@@ -98,7 +112,7 @@ func(...)
 	...>
 }
 
-@pmax depends on patch@
+@pmax depends on patch && max_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {>=, >};
@@ -131,7 +145,7 @@ func(...)
 	...>
 }
 
-@pmin depends on patch@
+@pmin depends on patch && min_candidate@
 identifier func;
 expression x, y;
 binary operator cmp = {<=, <};
-- 
2.43.0