Coccinelle archive on lore.kernel.org
 help / Atom feed
* [Cocci] =~ runtime improvements?
@ 2018-09-27 18:51 keescook
  2018-09-27 21:09 ` julia.lawall
  2018-09-30 15:06 ` lars
  0 siblings, 2 replies; 6+ messages in thread
From: keescook @ 2018-09-27 18:51 UTC (permalink / raw)
  To: cocci

Hi,

This .cocci takes a VERY long time to run against the kernel, and I'd
love to know what I could do to improve it. I assume it's related to
the use of the "=~" operand:

// Replace multi-factor out-of-line products with array_size() usage.
@@
identifier alloc =~ ".*alloc.*";
constant C1, C2, C3;
identifier ISTRIDE, ISIZE, ICOUNT;
expression ESTRIDE, ESIZE, ECOUNT;
expression PRODUCT, OTHER;
@@

(
  PRODUCT = ((C1)) * ((C2)) * ((C3))
|
  PRODUCT = ((C1)) * ((C2))
|
- PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ISIZE))
+ PRODUCT = array3_size(ICOUNT, ISTRIDE, ISIZE)
|
- PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ESIZE))
+ PRODUCT = array3_size(ICOUNT, ISTRIDE, ESIZE)
|
- PRODUCT = ((ICOUNT)) * ((ESTRIDE)) * ((ESIZE))
+ PRODUCT = array3_size(ICOUNT, ESTRIDE, ESIZE)
|
- PRODUCT = ((ECOUNT)) * ((ESTRIDE)) * ((ESIZE))
+ PRODUCT = array3_size(ECOUNT, ESTRIDE, ESIZE)
|
- PRODUCT = ((ICOUNT)) * ((ISIZE))
+ PRODUCT = array_size(ICOUNT, ISTRIDE, ISIZE)
|
- PRODUCT = ((ICOUNT)) * ((ESIZE))
+ PRODUCT = array_size(ICOUNT, ESIZE)
|
- PRODUCT = ((ECOUNT)) * ((ESIZE))
+ PRODUCT = array_size(ECOUNT, ESIZE)
)
  ... when != PRODUCT = OTHER
  alloc(..., PRODUCT, ...)

Thanks!

-Kees

-- 
Kees Cook
Pixel Security

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Cocci] =~ runtime improvements?
  2018-09-27 18:51 [Cocci] =~ runtime improvements? keescook
@ 2018-09-27 21:09 ` julia.lawall
  2018-09-30 15:06 ` lars
  1 sibling, 0 replies; 6+ messages in thread
From: julia.lawall @ 2018-09-27 21:09 UTC (permalink / raw)
  To: cocci



On Thu, 27 Sep 2018, Kees Cook wrote:

> Hi,
>
> This .cocci takes a VERY long time to run against the kernel, and I'd
> love to know what I could do to improve it. I assume it's related to
> the use of the "=~" operand:
>
> // Replace multi-factor out-of-line products with array_size() usage.
> @@
> identifier alloc =~ ".*alloc.*";
> constant C1, C2, C3;
> identifier ISTRIDE, ISIZE, ICOUNT;
> expression ESTRIDE, ESIZE, ECOUNT;
> expression PRODUCT, OTHER;
> @@
>
> (
>   PRODUCT = ((C1)) * ((C2)) * ((C3))
> |
>   PRODUCT = ((C1)) * ((C2))
> |
> - PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ISIZE))
> + PRODUCT = array3_size(ICOUNT, ISTRIDE, ISIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ESIZE))
> + PRODUCT = array3_size(ICOUNT, ISTRIDE, ESIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ESTRIDE)) * ((ESIZE))
> + PRODUCT = array3_size(ICOUNT, ESTRIDE, ESIZE)
> |
> - PRODUCT = ((ECOUNT)) * ((ESTRIDE)) * ((ESIZE))
> + PRODUCT = array3_size(ECOUNT, ESTRIDE, ESIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ISIZE))
> + PRODUCT = array_size(ICOUNT, ISTRIDE, ISIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ESIZE))
> + PRODUCT = array_size(ICOUNT, ESIZE)
> |
> - PRODUCT = ((ECOUNT)) * ((ESIZE))
> + PRODUCT = array_size(ECOUNT, ESIZE)
> )
>   ... when != PRODUCT = OTHER
>   alloc(..., PRODUCT, ...)

The rule contains ... and it doesn't contain anything much concrete.
Regular expressions aren't used to select files, so you consider all
files.  Big disjunctions are also costly.  You could consider making a
series of 9 rules.  Do you need the double parentheses?  That adds more
disjunctions.

julia


>
> Thanks!
>
> -Kees
>
> --
> Kees Cook
> Pixel Security
> _______________________________________________
> Cocci mailing list
> Cocci at systeme.lip6.fr
> https://systeme.lip6.fr/mailman/listinfo/cocci
>

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Cocci] =~ runtime improvements?
  2018-09-27 18:51 [Cocci] =~ runtime improvements? keescook
  2018-09-27 21:09 ` julia.lawall
@ 2018-09-30 15:06 ` lars
  2018-09-30 15:40   ` julia.lawall
  1 sibling, 1 reply; 6+ messages in thread
From: lars @ 2018-09-30 15:06 UTC (permalink / raw)
  To: cocci

On 09/27/2018 08:51 PM, Kees Cook wrote:
> Hi,
> 
> This .cocci takes a VERY long time to run against the kernel, and I'd
> love to know what I could do to improve it. I assume it's related to
> the use of the "=~" operand:
> 

Maybe I'm missing something, but do you need all of those variations? An
expression should match an identifier. I'd expect ((ECOUNT)) *
((ESTRIDE)) * ((ESIZE)) matches the superset of all the other statements
with ICOUNT, ISIZE and ISTRIDE in them. So you only need two rules one
for array_size and one for array3_size.

> // Replace multi-factor out-of-line products with array_size() usage.
> @@
> identifier alloc =~ ".*alloc.*";
> constant C1, C2, C3;
> identifier ISTRIDE, ISIZE, ICOUNT;
> expression ESTRIDE, ESIZE, ECOUNT;
> expression PRODUCT, OTHER;
> @@
> 
> (
>   PRODUCT = ((C1)) * ((C2)) * ((C3))
> |
>   PRODUCT = ((C1)) * ((C2))
> |
> - PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ISIZE))
> + PRODUCT = array3_size(ICOUNT, ISTRIDE, ISIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ESIZE))
> + PRODUCT = array3_size(ICOUNT, ISTRIDE, ESIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ESTRIDE)) * ((ESIZE))
> + PRODUCT = array3_size(ICOUNT, ESTRIDE, ESIZE)
> |
> - PRODUCT = ((ECOUNT)) * ((ESTRIDE)) * ((ESIZE))
> + PRODUCT = array3_size(ECOUNT, ESTRIDE, ESIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ISIZE))
> + PRODUCT = array_size(ICOUNT, ISTRIDE, ISIZE)
> |
> - PRODUCT = ((ICOUNT)) * ((ESIZE))
> + PRODUCT = array_size(ICOUNT, ESIZE)
> |
> - PRODUCT = ((ECOUNT)) * ((ESIZE))
> + PRODUCT = array_size(ECOUNT, ESIZE)
> )
>   ... when != PRODUCT = OTHER
>   alloc(..., PRODUCT, ...)
> 
> Thanks!
> 
> -Kees
> 

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Cocci] =~ runtime improvements?
  2018-09-30 15:06 ` lars
@ 2018-09-30 15:40   ` julia.lawall
  2018-09-30 16:54     ` keescook
  0 siblings, 1 reply; 6+ messages in thread
From: julia.lawall @ 2018-09-30 15:40 UTC (permalink / raw)
  To: cocci



On Sun, 30 Sep 2018, Lars-Peter Clausen wrote:

> On 09/27/2018 08:51 PM, Kees Cook wrote:
> > Hi,
> >
> > This .cocci takes a VERY long time to run against the kernel, and I'd
> > love to know what I could do to improve it. I assume it's related to
> > the use of the "=~" operand:
> >
>
> Maybe I'm missing something, but do you need all of those variations? An
> expression should match an identifier. I'd expect ((ECOUNT)) *
> ((ESTRIDE)) * ((ESIZE)) matches the superset of all the other statements
> with ICOUNT, ISIZE and ISTRIDE in them. So you only need two rules one
> for array_size and one for array3_size.

I agree about the indentifiers and expressions, although he also needs
some rules for the constant case.

thanks,
julia

>
> > // Replace multi-factor out-of-line products with array_size() usage.
> > @@
> > identifier alloc =~ ".*alloc.*";
> > constant C1, C2, C3;
> > identifier ISTRIDE, ISIZE, ICOUNT;
> > expression ESTRIDE, ESIZE, ECOUNT;
> > expression PRODUCT, OTHER;
> > @@
> >
> > (
> >   PRODUCT = ((C1)) * ((C2)) * ((C3))
> > |
> >   PRODUCT = ((C1)) * ((C2))
> > |
> > - PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ISIZE))
> > + PRODUCT = array3_size(ICOUNT, ISTRIDE, ISIZE)
> > |
> > - PRODUCT = ((ICOUNT)) * ((ISTRIDE)) * ((ESIZE))
> > + PRODUCT = array3_size(ICOUNT, ISTRIDE, ESIZE)
> > |
> > - PRODUCT = ((ICOUNT)) * ((ESTRIDE)) * ((ESIZE))
> > + PRODUCT = array3_size(ICOUNT, ESTRIDE, ESIZE)
> > |
> > - PRODUCT = ((ECOUNT)) * ((ESTRIDE)) * ((ESIZE))
> > + PRODUCT = array3_size(ECOUNT, ESTRIDE, ESIZE)
> > |
> > - PRODUCT = ((ICOUNT)) * ((ISIZE))
> > + PRODUCT = array_size(ICOUNT, ISTRIDE, ISIZE)
> > |
> > - PRODUCT = ((ICOUNT)) * ((ESIZE))
> > + PRODUCT = array_size(ICOUNT, ESIZE)
> > |
> > - PRODUCT = ((ECOUNT)) * ((ESIZE))
> > + PRODUCT = array_size(ECOUNT, ESIZE)
> > )
> >   ... when != PRODUCT = OTHER
> >   alloc(..., PRODUCT, ...)
> >
> > Thanks!
> >
> > -Kees
> >
>
> _______________________________________________
> Cocci mailing list
> Cocci at systeme.lip6.fr
> https://systeme.lip6.fr/mailman/listinfo/cocci
>

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Cocci] =~ runtime improvements?
  2018-09-30 15:40   ` julia.lawall
@ 2018-09-30 16:54     ` keescook
  2018-09-30 17:11       ` julia.lawall
  0 siblings, 1 reply; 6+ messages in thread
From: keescook @ 2018-09-30 16:54 UTC (permalink / raw)
  To: cocci

On Sun, Sep 30, 2018 at 8:40 AM, Julia Lawall <julia.lawall@lip6.fr> wrote:
>
>
> On Sun, 30 Sep 2018, Lars-Peter Clausen wrote:
>
>> On 09/27/2018 08:51 PM, Kees Cook wrote:
>> > Hi,
>> >
>> > This .cocci takes a VERY long time to run against the kernel, and I'd
>> > love to know what I could do to improve it. I assume it's related to
>> > the use of the "=~" operand:
>> >
>>
>> Maybe I'm missing something, but do you need all of those variations? An
>> expression should match an identifier. I'd expect ((ECOUNT)) *
>> ((ESTRIDE)) * ((ESIZE)) matches the superset of all the other statements
>> with ICOUNT, ISIZE and ISTRIDE in them. So you only need two rules one
>> for array_size and one for array3_size.
>
> I agree about the indentifiers and expressions, although he also needs
> some rules for the constant case.

I had to go progressively to exclude cases in an attempt to isolate
individual factors. For example:

E1 * E2

will match:

var1 * var2 * var3

In order to make a best-effort at extracting the multiplication
factors, I need to go in order from constants (ignore) to identifiers
(explicitly correct) to expressions (may overly match)

But yes, it seems the problem is mainly the "..." part, which is unavoidable.

-Kees

-- 
Kees Cook
Pixel Security

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Cocci] =~ runtime improvements?
  2018-09-30 16:54     ` keescook
@ 2018-09-30 17:11       ` julia.lawall
  0 siblings, 0 replies; 6+ messages in thread
From: julia.lawall @ 2018-09-30 17:11 UTC (permalink / raw)
  To: cocci



On Sun, 30 Sep 2018, Kees Cook wrote:

> On Sun, Sep 30, 2018 at 8:40 AM, Julia Lawall <julia.lawall@lip6.fr> wrote:
> >
> >
> > On Sun, 30 Sep 2018, Lars-Peter Clausen wrote:
> >
> >> On 09/27/2018 08:51 PM, Kees Cook wrote:
> >> > Hi,
> >> >
> >> > This .cocci takes a VERY long time to run against the kernel, and I'd
> >> > love to know what I could do to improve it. I assume it's related to
> >> > the use of the "=~" operand:
> >> >
> >>
> >> Maybe I'm missing something, but do you need all of those variations? An
> >> expression should match an identifier. I'd expect ((ECOUNT)) *
> >> ((ESTRIDE)) * ((ESIZE)) matches the superset of all the other statements
> >> with ICOUNT, ISIZE and ISTRIDE in them. So you only need two rules one
> >> for array_size and one for array3_size.
> >
> > I agree about the indentifiers and expressions, although he also needs
> > some rules for the constant case.
>
> I had to go progressively to exclude cases in an attempt to isolate
> individual factors. For example:
>
> E1 * E2
>
> will match:
>
> var1 * var2 * var3

I think you could just do E1 * E2 * E3 before E1 * E2?

>
> In order to make a best-effort at extracting the multiplication
> factors, I need to go in order from constants (ignore) to identifiers
> (explicitly correct) to expressions (may overly match)
>
> But yes, it seems the problem is mainly the "..." part, which is unavoidable.

Maybe it would be good to have some special cases?  Are the
multiplications often right next to the allocation?  Or if there is
something that is often between them, then it could be useful to make a
special case for that.

julia

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, back to index

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-09-27 18:51 [Cocci] =~ runtime improvements? keescook
2018-09-27 21:09 ` julia.lawall
2018-09-30 15:06 ` lars
2018-09-30 15:40   ` julia.lawall
2018-09-30 16:54     ` keescook
2018-09-30 17:11       ` julia.lawall

Coccinelle archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/cocci/0 cocci/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 cocci cocci/ https://lore.kernel.org/cocci \
		cocci@systeme.lip6.fr cocci@archiver.kernel.org
	public-inbox-index cocci


Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/fr.lip6.systeme.cocci


AGPL code for this site: git clone https://public-inbox.org/ public-inbox