[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! :)