[C] Improving performance of my Linux kernel query

[kees]

Hi!

The Linux kernel is in the final stages of converting all its ancient 1-element arrays into flexible arrays. For various reasons we want to only do this on structures that are actually using such array members, so I'm trying to locate them all. The query I have works great for finding array[index] style uses (only takes a couple minutes to run), but when I added logic to find pointer arithmetic (e.g. array + index) the query time jumped to 20 minutes. I don't understand why, given the matches for 1-element arrays should be a very small set of structs. (i.e. there are so few TrailingSizeOneArrayMember instances, I would expect only a doubling of query time: a second usage of an instance.)

import cpp class TrailingSizeOneArrayMember extends Field { TrailingSizeOneArrayMember() { exists(Struct s | this = s.getCanonicalMember(max(int j | s.getCanonicalMember(j) instanceof Field | j)) ) and this.getUnspecifiedType() instanceof ArrayType and ( this.getUnspecifiedType().(ArrayType).getArraySize() = 1 ) } } from Struct s, TrailingSizeOneArrayMember m, Expr access, ArrayExpr array, Expr index, PointerAddExpr add where m = s.getAField() and m.getAnAccess() = access and ( ( /* array[NNN] */ array.getArrayBase() = access and array.getArrayOffset() = index and /* * If it's a dynamic array index, we have to assume we're treating * the array as a flexible array (or at the very least, we can't * make any assumptions about it). * If it's a literal, we can ignore all instances of a "0" index, * which would not be out of bounds for a 1-element array. */ (not index.isConstant() or index.getValue().toInt() != 0) ) or /* This "or" adds 20 minutes to the query. O_o */ ( /* array + NNN */ add.getLeftOperand() = access ) ) select "struct " + s.getName() + "::" + m.getName() as struct, access.getLocation() as location 

If I remove the or add.getLeftOperand() = access portion of the query, this runs quite quickly. What am I doing wrong? (Or, maybe, why is it so much slower?)

Thanks!

[smowton]

This may be because you have variables add, array and index that is only bound on one side of the or. On the other side it would be populated by every array indexing operation / every add operation in the kernel, then ultimately the unused variables are ignored, so depending on optimisation choices you may or may not pay a substantial cost for that.

Suggested rewrite:

import cpp class TrailingSizeOneArrayMember extends Field { TrailingSizeOneArrayMember() { exists(Struct s | this = s.getCanonicalMember(max(int j | s.getCanonicalMember(j) instanceof Field | j)) ) and this.getUnspecifiedType() instanceof ArrayType and this.getUnspecifiedType().(ArrayType).getArraySize() = 1 } } from Struct s, TrailingSizeOneArrayMember m, Expr access where m = s.getAField() and m.getAnAccess() = access and ( exists(ArrayExpr array, Expr index | /* array[NNN] */ array.getArrayBase() = access and array.getArrayOffset() = index and /*  * If it's a dynamic array index, we have to assume we're treating  * the array as a flexible array (or at the very least, we can't  * make any assumptions about it).  * If it's a literal, we can ignore all instances of a "0" index,  * which would not be out of bounds for a 1-element array.  */ (not index.isConstant() or index.getValue().toInt() != 0) ) or /* This "or" adds 20 minutes to the query. O_o */ /* array + NNN */ any(PointerAddExpr add).getLeftOperand() = access ) select "struct " + s.getName() + "::" + m.getName() as struct, access.getLocation() as location

Now the variables are only introduced in the scopes where they are used, using an exists and an any statement respectively.

[kees]

Thank you! That did it: Evaluation completed (55.9s) I thought the scope would be handled automatically, but now I see how to narrow the scope. I appreciate the help! :)