tree: https://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git ftrace/core head: 83dddc0b1e2dd1894186a46acce4dfce75d60c72 commit: 83dddc0b1e2dd1894186a46acce4dfce75d60c72 [46/46] tracing: Rewrite filter logic to be simpler and faster
smatch warnings: kernel/trace/trace_events_filter.c:467 predicate_parse() warn: possible memory leak of 'inverts' # https://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git/commit/?id=83dddc0b1e2dd1894186a46acce4dfce75d60c72 git remote add trace https://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git git remote update trace git checkout 83dddc0b1e2dd1894186a46acce4dfce75d60c72 vim +/inverts +467 kernel/trace/trace_events_filter.c 61e9dea2 Steven Rostedt 2011-01-27 159 83dddc0b Steven Rostedt (VMware 2018-03-09 160) /* 83dddc0b Steven Rostedt (VMware 2018-03-09 161) * Without going into a formal proof, this explains the method that is used in 83dddc0b Steven Rostedt (VMware 2018-03-09 162) * parsing the logical expressions. 83dddc0b Steven Rostedt (VMware 2018-03-09 163) * 83dddc0b Steven Rostedt (VMware 2018-03-09 164) * For example, if we have: "a && !(!b || (c && g)) || d || e && !f" 83dddc0b Steven Rostedt (VMware 2018-03-09 165) * The first pass will convert it into the following program: 83dddc0b Steven Rostedt (VMware 2018-03-09 166) * 83dddc0b Steven Rostedt (VMware 2018-03-09 167) * n1: r=a; l1: if (!r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 168) * n2: r=b; l2: if (!r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 169) * n3: r=c; r=!r; l3: if (r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 170) * n4: r=g; r=!r; l4: if (r) goto l5; 83dddc0b Steven Rostedt (VMware 2018-03-09 171) * n5: r=d; l5: if (r) goto T 83dddc0b Steven Rostedt (VMware 2018-03-09 172) * n6: r=e; l6: if (!r) goto l7; 83dddc0b Steven Rostedt (VMware 2018-03-09 173) * n7: r=f; r=!r; l7: if (!r) goto F 83dddc0b Steven Rostedt (VMware 2018-03-09 174) * T: return TRUE 83dddc0b Steven Rostedt (VMware 2018-03-09 175) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 176) * 83dddc0b Steven Rostedt (VMware 2018-03-09 177) * To do this, we use a data structure to represent each of the above 83dddc0b Steven Rostedt (VMware 2018-03-09 178) * predicate and conditions that has: 83dddc0b Steven Rostedt (VMware 2018-03-09 179) * 83dddc0b Steven Rostedt (VMware 2018-03-09 180) * predicate, when_to_branch, invert, target 83dddc0b Steven Rostedt (VMware 2018-03-09 181) * 83dddc0b Steven Rostedt (VMware 2018-03-09 182) * The "predicate" will hold the function to determine the result "r". 83dddc0b Steven Rostedt (VMware 2018-03-09 183) * The "when_to_branch" denotes what "r" should be if a branch is to be taken 83dddc0b Steven Rostedt (VMware 2018-03-09 184) * "&&" would contain "!r" or (0) and "||" would contain "r" or (1). 83dddc0b Steven Rostedt (VMware 2018-03-09 185) * The "invert" holds whether the value should be reversed before testing. 83dddc0b Steven Rostedt (VMware 2018-03-09 186) * The "target" contains the label "l#" to jump to. 83dddc0b Steven Rostedt (VMware 2018-03-09 187) * 83dddc0b Steven Rostedt (VMware 2018-03-09 188) * A stack is created to hold values when parentheses are used. 83dddc0b Steven Rostedt (VMware 2018-03-09 189) * 83dddc0b Steven Rostedt (VMware 2018-03-09 190) * To simplify the logic, the labels will start at 0 and not 1. 83dddc0b Steven Rostedt (VMware 2018-03-09 191) * 83dddc0b Steven Rostedt (VMware 2018-03-09 192) * The possible invert values are 1 and 0. The number of "!"s that are in scope 83dddc0b Steven Rostedt (VMware 2018-03-09 193) * before the predicate determines the invert value, if the number is odd then 83dddc0b Steven Rostedt (VMware 2018-03-09 194) * the invert value is 1 and 0 otherwise. This means the invert value only 83dddc0b Steven Rostedt (VMware 2018-03-09 195) * needs to be toggled when a new "!" is introduced compared to what is stored 83dddc0b Steven Rostedt (VMware 2018-03-09 196) * on the stack, where parentheses were used. 83dddc0b Steven Rostedt (VMware 2018-03-09 197) * 83dddc0b Steven Rostedt (VMware 2018-03-09 198) * The top of the stack and "invert" are initialized to zero. 83dddc0b Steven Rostedt (VMware 2018-03-09 199) * 83dddc0b Steven Rostedt (VMware 2018-03-09 200) * ** FIRST PASS ** 83dddc0b Steven Rostedt (VMware 2018-03-09 201) * 83dddc0b Steven Rostedt (VMware 2018-03-09 202) * #1 A loop through all the tokens is done: 83dddc0b Steven Rostedt (VMware 2018-03-09 203) * 83dddc0b Steven Rostedt (VMware 2018-03-09 204) * #2 If the token is an "(", the stack is push, and the current stack value 83dddc0b Steven Rostedt (VMware 2018-03-09 205) * gets the current invert value, and the loop continues to the next token. 83dddc0b Steven Rostedt (VMware 2018-03-09 206) * The top of the stack saves the "invert" value to keep track of what 83dddc0b Steven Rostedt (VMware 2018-03-09 207) * the current inversion is. As "!(a && !b || c)" would require all 83dddc0b Steven Rostedt (VMware 2018-03-09 208) * predicates being affected separately by the "!" before the parentheses. 83dddc0b Steven Rostedt (VMware 2018-03-09 209) * And that would end up being equivalent to "(!a || b) && !c" 83dddc0b Steven Rostedt (VMware 2018-03-09 210) * 83dddc0b Steven Rostedt (VMware 2018-03-09 211) * #3 If the token is an "!", the current "invert" value gets inverted, and 83dddc0b Steven Rostedt (VMware 2018-03-09 212) * the loop continues. Note, if the next token is a predicate, then 83dddc0b Steven Rostedt (VMware 2018-03-09 213) * this "invert" value is only valid for the current program entry, 83dddc0b Steven Rostedt (VMware 2018-03-09 214) * and does not affect other predicates later on. 83dddc0b Steven Rostedt (VMware 2018-03-09 215) * 83dddc0b Steven Rostedt (VMware 2018-03-09 216) * The only other acceptable token is the predicate string. 83dddc0b Steven Rostedt (VMware 2018-03-09 217) * 83dddc0b Steven Rostedt (VMware 2018-03-09 218) * #4 A new entry into the program is added saving: the predicate and the 83dddc0b Steven Rostedt (VMware 2018-03-09 219) * current value of "invert". The target is currently assigned to the 83dddc0b Steven Rostedt (VMware 2018-03-09 220) * previous program index (this will not be its final value). 83dddc0b Steven Rostedt (VMware 2018-03-09 221) * 83dddc0b Steven Rostedt (VMware 2018-03-09 222) * #5 We now enter another loop and look at the next token. The only valid 83dddc0b Steven Rostedt (VMware 2018-03-09 223) * tokens are ")", "&&", "||" or end of the input string "\0". 83dddc0b Steven Rostedt (VMware 2018-03-09 224) * 83dddc0b Steven Rostedt (VMware 2018-03-09 225) * #6 The invert variable is reset to the current value saved on the top of 83dddc0b Steven Rostedt (VMware 2018-03-09 226) * the stack. 83dddc0b Steven Rostedt (VMware 2018-03-09 227) * 83dddc0b Steven Rostedt (VMware 2018-03-09 228) * #7 The top of the stack holds not only the current invert value, but also 83dddc0b Steven Rostedt (VMware 2018-03-09 229) * if a "&&" or "||" needs to be processed. Note, the "&&" takes higher 83dddc0b Steven Rostedt (VMware 2018-03-09 230) * precedence than "||". That is "a && b || c && d" is equivalent to 83dddc0b Steven Rostedt (VMware 2018-03-09 231) * "(a && b) || (c && d)". Thus the first thing to do is to see if "&&" needs 83dddc0b Steven Rostedt (VMware 2018-03-09 232) * to be processed. This is the case if an "&&" was the last token. If it was 83dddc0b Steven Rostedt (VMware 2018-03-09 233) * then we call update_preds(). This takes the program, the current index in 83dddc0b Steven Rostedt (VMware 2018-03-09 234) * the program, and the current value of "invert". More will be described 83dddc0b Steven Rostedt (VMware 2018-03-09 235) * below about this function. 83dddc0b Steven Rostedt (VMware 2018-03-09 236) * 83dddc0b Steven Rostedt (VMware 2018-03-09 237) * #8 If the next token is "&&" then we set a flag in the top of the stack 83dddc0b Steven Rostedt (VMware 2018-03-09 238) * that denotes that "&&" needs to be processed, break out of this loop 83dddc0b Steven Rostedt (VMware 2018-03-09 239) * and continue with the outer loop. 83dddc0b Steven Rostedt (VMware 2018-03-09 240) * 83dddc0b Steven Rostedt (VMware 2018-03-09 241) * #9 Otherwise, if a "||" needs to be processed then update_preds() is called. 83dddc0b Steven Rostedt (VMware 2018-03-09 242) * This is called with the program, the current index in the program, but 83dddc0b Steven Rostedt (VMware 2018-03-09 243) * this time with an inverted value of "invert" (that is !invert). This is 83dddc0b Steven Rostedt (VMware 2018-03-09 244) * because the value taken will become the "when_to_branch" value of the 83dddc0b Steven Rostedt (VMware 2018-03-09 245) * program. 83dddc0b Steven Rostedt (VMware 2018-03-09 246) * Note, this is called when the next token is not an "&&". As stated before, 83dddc0b Steven Rostedt (VMware 2018-03-09 247) * "&&" takes higher precedence, and "||" should not be processed yet if the 83dddc0b Steven Rostedt (VMware 2018-03-09 248) * next logical operation is "&&". 83dddc0b Steven Rostedt (VMware 2018-03-09 249) * 83dddc0b Steven Rostedt (VMware 2018-03-09 250) * #10 If the next token is "||" then we set a flag in the top of the stack 83dddc0b Steven Rostedt (VMware 2018-03-09 251) * that denotes that "||" needs to be processed, break out of this loop 83dddc0b Steven Rostedt (VMware 2018-03-09 252) * and continue with the outer loop. 83dddc0b Steven Rostedt (VMware 2018-03-09 253) * 83dddc0b Steven Rostedt (VMware 2018-03-09 254) * #11 If this is the end of the input string "\0" then we break out of both 83dddc0b Steven Rostedt (VMware 2018-03-09 255) * loops. 83dddc0b Steven Rostedt (VMware 2018-03-09 256) * 83dddc0b Steven Rostedt (VMware 2018-03-09 257) * #12 Otherwise, the next token is ")", where we pop the stack and continue 83dddc0b Steven Rostedt (VMware 2018-03-09 258) * this inner loop. 83dddc0b Steven Rostedt (VMware 2018-03-09 259) * 83dddc0b Steven Rostedt (VMware 2018-03-09 260) * Now to discuss the update_pred() function, as that is key to the setting up 83dddc0b Steven Rostedt (VMware 2018-03-09 261) * of the program. Remember the "target" of the program is initialized to the 83dddc0b Steven Rostedt (VMware 2018-03-09 262) * previous index and not the "l" label. The target holds the index into the 83dddc0b Steven Rostedt (VMware 2018-03-09 263) * program that gets affected by the operand. Thus if we have something like 83dddc0b Steven Rostedt (VMware 2018-03-09 264) * "a || b && c", when we process "a" the target will be "-1" (undefined). 83dddc0b Steven Rostedt (VMware 2018-03-09 265) * When we process "b", its target is "0", which is the index of "a", as that's 83dddc0b Steven Rostedt (VMware 2018-03-09 266) * the predicate that is affected by "||". But because the next token after "b" 83dddc0b Steven Rostedt (VMware 2018-03-09 267) * is "&&" we don't call update_preds(). Instead continue to "c". As the 83dddc0b Steven Rostedt (VMware 2018-03-09 268) * next token after "c" is not "&&" but the end of input, we first process the 83dddc0b Steven Rostedt (VMware 2018-03-09 269) * "&&" by calling update_preds() for the "&&" then we process the "||" by 83dddc0b Steven Rostedt (VMware 2018-03-09 270) * callin updates_preds() with the values for processing "||". 83dddc0b Steven Rostedt (VMware 2018-03-09 271) * 83dddc0b Steven Rostedt (VMware 2018-03-09 272) * What does that mean? What update_preds() does is to first save the "target" 83dddc0b Steven Rostedt (VMware 2018-03-09 273) * of the program entry indexed by the current program entry's "target" 83dddc0b Steven Rostedt (VMware 2018-03-09 274) * (remember the "target" is initialized to previous program entry), and then 83dddc0b Steven Rostedt (VMware 2018-03-09 275) * sets that "target" to the current index which represents the label "l#". 83dddc0b Steven Rostedt (VMware 2018-03-09 276) * That entry's "when_to_branch" is set to the value passed in (the "invert" 83dddc0b Steven Rostedt (VMware 2018-03-09 277) * or "!invert"). Then it sets the current program entry's target to the saved 83dddc0b Steven Rostedt (VMware 2018-03-09 278) * "target" value (the old value of the program that had its "target" updated 83dddc0b Steven Rostedt (VMware 2018-03-09 279) * to the label). 83dddc0b Steven Rostedt (VMware 2018-03-09 280) * 83dddc0b Steven Rostedt (VMware 2018-03-09 281) * Looking back at "a || b && c", we have the following steps: 83dddc0b Steven Rostedt (VMware 2018-03-09 282) * "a" - prog[0] = { "a", X, -1 } // pred, when_to_branch, target 83dddc0b Steven Rostedt (VMware 2018-03-09 283) * "||" - flag that we need to process "||"; continue outer loop 83dddc0b Steven Rostedt (VMware 2018-03-09 284) * "b" - prog[1] = { "b", X, 0 } 83dddc0b Steven Rostedt (VMware 2018-03-09 285) * "&&" - flag that we need to process "&&"; continue outer loop 83dddc0b Steven Rostedt (VMware 2018-03-09 286) * (Notice we did not process "||") 83dddc0b Steven Rostedt (VMware 2018-03-09 287) * "c" - prog[2] = { "c", X, 1 } 83dddc0b Steven Rostedt (VMware 2018-03-09 288) * update_preds(prog, 2, 0); // invert = 0 as we are processing "&&" 83dddc0b Steven Rostedt (VMware 2018-03-09 289) * t = prog[2].target; // t = 1 83dddc0b Steven Rostedt (VMware 2018-03-09 290) * s = prog[t].target; // s = 0 83dddc0b Steven Rostedt (VMware 2018-03-09 291) * prog[t].target = 2; // Set target to "l2" 83dddc0b Steven Rostedt (VMware 2018-03-09 292) * prog[t].when_to_branch = 0; 83dddc0b Steven Rostedt (VMware 2018-03-09 293) * prog[2].target = s; 83dddc0b Steven Rostedt (VMware 2018-03-09 294) * update_preds(prog, 2, 1); // invert = 1 as we are now processing "||" 83dddc0b Steven Rostedt (VMware 2018-03-09 295) * t = prog[2].target; // t = 0 83dddc0b Steven Rostedt (VMware 2018-03-09 296) * s = prog[t].target; // s = -1 83dddc0b Steven Rostedt (VMware 2018-03-09 297) * prog[t].target = 2; // Set target to "l2" 83dddc0b Steven Rostedt (VMware 2018-03-09 298) * prog[t].when_to_branch = 1; 83dddc0b Steven Rostedt (VMware 2018-03-09 299) * prog[2].target = s; 83dddc0b Steven Rostedt (VMware 2018-03-09 300) * 83dddc0b Steven Rostedt (VMware 2018-03-09 301) * #13 Which brings us to the final step of the first pass, which is to set 83dddc0b Steven Rostedt (VMware 2018-03-09 302) * the last program entry's when_to_branch and target, which will be 83dddc0b Steven Rostedt (VMware 2018-03-09 303) * when_to_branch = 0; target = N; ( the label after the program entry after 83dddc0b Steven Rostedt (VMware 2018-03-09 304) * the last program entry processed above). 83dddc0b Steven Rostedt (VMware 2018-03-09 305) * 83dddc0b Steven Rostedt (VMware 2018-03-09 306) * If we denote "TRUE" to be the entry after the last program entry processed, 83dddc0b Steven Rostedt (VMware 2018-03-09 307) * and "FALSE" the program entry after that, we are now done with the first 83dddc0b Steven Rostedt (VMware 2018-03-09 308) * pass. 83dddc0b Steven Rostedt (VMware 2018-03-09 309) * 83dddc0b Steven Rostedt (VMware 2018-03-09 310) * Making the above "a || b && c" have a progam of: 83dddc0b Steven Rostedt (VMware 2018-03-09 311) * prog[0] = { "a", 1, 2 } 83dddc0b Steven Rostedt (VMware 2018-03-09 312) * prog[1] = { "b", 0, 2 } 83dddc0b Steven Rostedt (VMware 2018-03-09 313) * prog[2] = { "c", 0, 3 } 83dddc0b Steven Rostedt (VMware 2018-03-09 314) * 83dddc0b Steven Rostedt (VMware 2018-03-09 315) * Which translates into: 83dddc0b Steven Rostedt (VMware 2018-03-09 316) * n0: r = a; l0: if (r) goto l2; 83dddc0b Steven Rostedt (VMware 2018-03-09 317) * n1: r = b; l1: if (!r) goto l2; 83dddc0b Steven Rostedt (VMware 2018-03-09 318) * n2: r = c; l2: if (!r) goto l3; // Which is the same as "goto F;" 83dddc0b Steven Rostedt (VMware 2018-03-09 319) * T: return TRUE; l3: 83dddc0b Steven Rostedt (VMware 2018-03-09 320) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 321) * 83dddc0b Steven Rostedt (VMware 2018-03-09 322) * Although, after the first pass, the program is correct, it is 83dddc0b Steven Rostedt (VMware 2018-03-09 323) * inefficient. The simple sample of "a || b && c" could be easily been 83dddc0b Steven Rostedt (VMware 2018-03-09 324) * converted into: 83dddc0b Steven Rostedt (VMware 2018-03-09 325) * n0: r = a; if (r) goto T 83dddc0b Steven Rostedt (VMware 2018-03-09 326) * n1: r = b; if (!r) goto F 83dddc0b Steven Rostedt (VMware 2018-03-09 327) * n2: r = c; if (!r) goto F 83dddc0b Steven Rostedt (VMware 2018-03-09 328) * T: return TRUE; 83dddc0b Steven Rostedt (VMware 2018-03-09 329) * F: return FALSE; 83dddc0b Steven Rostedt (VMware 2018-03-09 330) * 83dddc0b Steven Rostedt (VMware 2018-03-09 331) * The First Pass is over the input string. The next too passes are over 83dddc0b Steven Rostedt (VMware 2018-03-09 332) * the program itself. 83dddc0b Steven Rostedt (VMware 2018-03-09 333) * 83dddc0b Steven Rostedt (VMware 2018-03-09 334) * ** SECOND PASS ** 83dddc0b Steven Rostedt (VMware 2018-03-09 335) * 83dddc0b Steven Rostedt (VMware 2018-03-09 336) * Which brings us to the second pass. If a jump to a label has the 83dddc0b Steven Rostedt (VMware 2018-03-09 337) * same condition as that label, it can instead jump to its target. 83dddc0b Steven Rostedt (VMware 2018-03-09 338) * The original example of "a && !(!b || (c && g)) || d || e && !f" 83dddc0b Steven Rostedt (VMware 2018-03-09 339) * where the first pass gives us: 83dddc0b Steven Rostedt (VMware 2018-03-09 340) * 83dddc0b Steven Rostedt (VMware 2018-03-09 341) * n1: r=a; l1: if (!r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 342) * n2: r=b; l2: if (!r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 343) * n3: r=c; r=!r; l3: if (r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 344) * n4: r=g; r=!r; l4: if (r) goto l5; 83dddc0b Steven Rostedt (VMware 2018-03-09 345) * n5: r=d; l5: if (r) goto T 83dddc0b Steven Rostedt (VMware 2018-03-09 346) * n6: r=e; l6: if (!r) goto l7; 83dddc0b Steven Rostedt (VMware 2018-03-09 347) * n7: r=f; r=!r; l7: if (!r) goto F: 83dddc0b Steven Rostedt (VMware 2018-03-09 348) * T: return TRUE; 83dddc0b Steven Rostedt (VMware 2018-03-09 349) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 350) * 83dddc0b Steven Rostedt (VMware 2018-03-09 351) * We can see that "l3: if (r) goto l4;" and at l4, we have "if (r) goto l5;". 83dddc0b Steven Rostedt (VMware 2018-03-09 352) * And "l5: if (r) goto T", we could optimize this by converting l3 and l4 83dddc0b Steven Rostedt (VMware 2018-03-09 353) * to go directly to T. To accomplish this, we start from the last 83dddc0b Steven Rostedt (VMware 2018-03-09 354) * entry in the program and work our way back. If the target of the entry 83dddc0b Steven Rostedt (VMware 2018-03-09 355) * has the same "when_to_branch" then we could use that entry's target. 83dddc0b Steven Rostedt (VMware 2018-03-09 356) * Doing this, the above would end up as: 83dddc0b Steven Rostedt (VMware 2018-03-09 357) * 83dddc0b Steven Rostedt (VMware 2018-03-09 358) * n1: r=a; l1: if (!r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 359) * n2: r=b; l2: if (!r) goto l4; 83dddc0b Steven Rostedt (VMware 2018-03-09 360) * n3: r=c; r=!r; l3: if (r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 361) * n4: r=g; r=!r; l4: if (r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 362) * n5: r=d; l5: if (r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 363) * n6: r=e; l6: if (!r) goto F; 83dddc0b Steven Rostedt (VMware 2018-03-09 364) * n7: r=f; r=!r; l7: if (!r) goto F; 83dddc0b Steven Rostedt (VMware 2018-03-09 365) * T: return TRUE 83dddc0b Steven Rostedt (VMware 2018-03-09 366) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 367) * 83dddc0b Steven Rostedt (VMware 2018-03-09 368) * In that same pass, if the "when_to_branch" doesn't match, we can simply 83dddc0b Steven Rostedt (VMware 2018-03-09 369) * go to the program entry after the label. That is, "l2: if (!r) goto l4;" 83dddc0b Steven Rostedt (VMware 2018-03-09 370) * where "l4: if (r) goto T;", then we can convert l2 to be: 83dddc0b Steven Rostedt (VMware 2018-03-09 371) * "l2: if (!r) goto n5;". 83dddc0b Steven Rostedt (VMware 2018-03-09 372) * 83dddc0b Steven Rostedt (VMware 2018-03-09 373) * This will have the second pass give us: 83dddc0b Steven Rostedt (VMware 2018-03-09 374) * n1: r=a; l1: if (!r) goto n5; 83dddc0b Steven Rostedt (VMware 2018-03-09 375) * n2: r=b; l2: if (!r) goto n5; 83dddc0b Steven Rostedt (VMware 2018-03-09 376) * n3: r=c; r=!r; l3: if (r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 377) * n4: r=g; r=!r; l4: if (r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 378) * n5: r=d; l5: if (r) goto T 83dddc0b Steven Rostedt (VMware 2018-03-09 379) * n6: r=e; l6: if (!r) goto F; 83dddc0b Steven Rostedt (VMware 2018-03-09 380) * n7: r=f; r=!r; l7: if (!r) goto F 83dddc0b Steven Rostedt (VMware 2018-03-09 381) * T: return TRUE 83dddc0b Steven Rostedt (VMware 2018-03-09 382) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 383) * 83dddc0b Steven Rostedt (VMware 2018-03-09 384) * Notice, all the "l#" labels are no longer used, and they can now 83dddc0b Steven Rostedt (VMware 2018-03-09 385) * be discarded. 83dddc0b Steven Rostedt (VMware 2018-03-09 386) * 83dddc0b Steven Rostedt (VMware 2018-03-09 387) * ** THIRD PASS ** 83dddc0b Steven Rostedt (VMware 2018-03-09 388) * 83dddc0b Steven Rostedt (VMware 2018-03-09 389) * For the third pass we deal with the inverts. As they simply just 83dddc0b Steven Rostedt (VMware 2018-03-09 390) * make the "when_to_branch" get inverted, a simple loop over the 83dddc0b Steven Rostedt (VMware 2018-03-09 391) * program to that does: "when_to_branch ^= invert;" will do the 83dddc0b Steven Rostedt (VMware 2018-03-09 392) * job, leaving us with: 83dddc0b Steven Rostedt (VMware 2018-03-09 393) * n1: r=a; if (!r) goto n5; 83dddc0b Steven Rostedt (VMware 2018-03-09 394) * n2: r=b; if (!r) goto n5; 83dddc0b Steven Rostedt (VMware 2018-03-09 395) * n3: r=c: if (!r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 396) * n4: r=g; if (!r) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 397) * n5: r=d; if (r) goto T 83dddc0b Steven Rostedt (VMware 2018-03-09 398) * n6: r=e; if (!r) goto F; 83dddc0b Steven Rostedt (VMware 2018-03-09 399) * n7: r=f; if (r) goto F 83dddc0b Steven Rostedt (VMware 2018-03-09 400) * T: return TRUE 83dddc0b Steven Rostedt (VMware 2018-03-09 401) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 402) * 83dddc0b Steven Rostedt (VMware 2018-03-09 403) * As "r = a; if (!r) goto n5;" is obviously the same as 83dddc0b Steven Rostedt (VMware 2018-03-09 404) * "if (!a) goto n5;" without doing anything we can interperate the 83dddc0b Steven Rostedt (VMware 2018-03-09 405) * program as: 83dddc0b Steven Rostedt (VMware 2018-03-09 406) * n1: if (!a) goto n5; 83dddc0b Steven Rostedt (VMware 2018-03-09 407) * n2: if (!b) goto n5; 83dddc0b Steven Rostedt (VMware 2018-03-09 408) * n3: if (!c) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 409) * n4: if (!g) goto T; 83dddc0b Steven Rostedt (VMware 2018-03-09 410) * n5: if (d) goto T 83dddc0b Steven Rostedt (VMware 2018-03-09 411) * n6: if (!e) goto F; 83dddc0b Steven Rostedt (VMware 2018-03-09 412) * n7: if (f) goto F 83dddc0b Steven Rostedt (VMware 2018-03-09 413) * T: return TRUE 83dddc0b Steven Rostedt (VMware 2018-03-09 414) * F: return FALSE 83dddc0b Steven Rostedt (VMware 2018-03-09 415) * 83dddc0b Steven Rostedt (VMware 2018-03-09 416) * Since the inverts are discarded at the end, there's no reason to store 83dddc0b Steven Rostedt (VMware 2018-03-09 417) * them in the program array (and waste memory). A separate array to hold 83dddc0b Steven Rostedt (VMware 2018-03-09 418) * the inverts is used and freed at the end. 83dddc0b Steven Rostedt (VMware 2018-03-09 419) */ 83dddc0b Steven Rostedt (VMware 2018-03-09 420) static struct prog_entry * 83dddc0b Steven Rostedt (VMware 2018-03-09 421) predicate_parse(const char *str, int nr_parens, int nr_preds, 83dddc0b Steven Rostedt (VMware 2018-03-09 422) parse_pred_fn parse_pred, void *data, 83dddc0b Steven Rostedt (VMware 2018-03-09 423) struct filter_parse_error *pe) 83dddc0b Steven Rostedt (VMware 2018-03-09 424) { 83dddc0b Steven Rostedt (VMware 2018-03-09 425) struct prog_entry *prog_stack; 83dddc0b Steven Rostedt (VMware 2018-03-09 426) struct prog_entry *prog; 83dddc0b Steven Rostedt (VMware 2018-03-09 427) const char *ptr = str; 83dddc0b Steven Rostedt (VMware 2018-03-09 428) char *inverts = NULL; 83dddc0b Steven Rostedt (VMware 2018-03-09 429) int *op_stack; 83dddc0b Steven Rostedt (VMware 2018-03-09 430) int *top; 83dddc0b Steven Rostedt (VMware 2018-03-09 431) int invert = 0; 83dddc0b Steven Rostedt (VMware 2018-03-09 432) int ret = -ENOMEM; 83dddc0b Steven Rostedt (VMware 2018-03-09 433) int len; 83dddc0b Steven Rostedt (VMware 2018-03-09 434) int N = 0; 83dddc0b Steven Rostedt (VMware 2018-03-09 435) int i; 83dddc0b Steven Rostedt (VMware 2018-03-09 436) 83dddc0b Steven Rostedt (VMware 2018-03-09 437) nr_preds += 2; /* For TRUE and FALSE */ 83dddc0b Steven Rostedt (VMware 2018-03-09 438) 83dddc0b Steven Rostedt (VMware 2018-03-09 439) op_stack = kmalloc(sizeof(*op_stack) * nr_parens, GFP_KERNEL); 83dddc0b Steven Rostedt (VMware 2018-03-09 440) if (!op_stack) 83dddc0b Steven Rostedt (VMware 2018-03-09 441) return ERR_PTR(-ENOMEM); 83dddc0b Steven Rostedt (VMware 2018-03-09 442) prog_stack = kmalloc(sizeof(*prog_stack) * nr_preds, GFP_KERNEL); 83dddc0b Steven Rostedt (VMware 2018-03-09 443) if (!prog_stack) { 83dddc0b Steven Rostedt (VMware 2018-03-09 444) parse_error(pe, -ENOMEM, 0); 83dddc0b Steven Rostedt (VMware 2018-03-09 445) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 446) } 83dddc0b Steven Rostedt (VMware 2018-03-09 447) inverts = kmalloc(sizeof(*inverts) * nr_preds, GFP_KERNEL); 83dddc0b Steven Rostedt (VMware 2018-03-09 448) if (!inverts) { 83dddc0b Steven Rostedt (VMware 2018-03-09 449) parse_error(pe, -ENOMEM, 0); 83dddc0b Steven Rostedt (VMware 2018-03-09 450) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 451) } 83dddc0b Steven Rostedt (VMware 2018-03-09 452) 83dddc0b Steven Rostedt (VMware 2018-03-09 453) top = op_stack; 83dddc0b Steven Rostedt (VMware 2018-03-09 454) prog = prog_stack; 83dddc0b Steven Rostedt (VMware 2018-03-09 455) *top = 0; 83dddc0b Steven Rostedt (VMware 2018-03-09 456) 83dddc0b Steven Rostedt (VMware 2018-03-09 457) /* First pass */ 83dddc0b Steven Rostedt (VMware 2018-03-09 458) while (*ptr) { /* #1 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 459) const char *next = ptr++; 83dddc0b Steven Rostedt (VMware 2018-03-09 460) 83dddc0b Steven Rostedt (VMware 2018-03-09 461) if (isspace(*next)) 83dddc0b Steven Rostedt (VMware 2018-03-09 462) continue; 83dddc0b Steven Rostedt (VMware 2018-03-09 463) 83dddc0b Steven Rostedt (VMware 2018-03-09 464) switch (*next) { 83dddc0b Steven Rostedt (VMware 2018-03-09 465) case '(': /* #2 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 466) if (top - op_stack > nr_parens) 83dddc0b Steven Rostedt (VMware 2018-03-09 @467) return ERR_PTR(-EINVAL); ^^^^^^^^^^^^^^^^ goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 468) *(++top) = invert; 83dddc0b Steven Rostedt (VMware 2018-03-09 469) continue; 83dddc0b Steven Rostedt (VMware 2018-03-09 470) case '!': /* #3 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 471) if (!is_not(next)) 83dddc0b Steven Rostedt (VMware 2018-03-09 472) break; 83dddc0b Steven Rostedt (VMware 2018-03-09 473) invert = !invert; 83dddc0b Steven Rostedt (VMware 2018-03-09 474) continue; 83dddc0b Steven Rostedt (VMware 2018-03-09 475) } 83dddc0b Steven Rostedt (VMware 2018-03-09 476) 83dddc0b Steven Rostedt (VMware 2018-03-09 477) if (N >= nr_preds) { 83dddc0b Steven Rostedt (VMware 2018-03-09 478) parse_error(pe, FILT_ERR_TOO_MANY_PREDS, next - str); 83dddc0b Steven Rostedt (VMware 2018-03-09 479) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 480) } 83dddc0b Steven Rostedt (VMware 2018-03-09 481) 83dddc0b Steven Rostedt (VMware 2018-03-09 482) inverts[N] = invert; /* #4 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 483) prog[N].target = N-1; 83dddc0b Steven Rostedt (VMware 2018-03-09 484) 83dddc0b Steven Rostedt (VMware 2018-03-09 485) len = parse_pred(next, data, ptr - str, pe, &prog[N].pred); 83dddc0b Steven Rostedt (VMware 2018-03-09 486) if (len < 0) { 83dddc0b Steven Rostedt (VMware 2018-03-09 487) ret = len; 83dddc0b Steven Rostedt (VMware 2018-03-09 488) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 489) } 83dddc0b Steven Rostedt (VMware 2018-03-09 490) ptr = next + len; 83dddc0b Steven Rostedt (VMware 2018-03-09 491) 83dddc0b Steven Rostedt (VMware 2018-03-09 492) N++; 83dddc0b Steven Rostedt (VMware 2018-03-09 493) 83dddc0b Steven Rostedt (VMware 2018-03-09 494) ret = -1; 83dddc0b Steven Rostedt (VMware 2018-03-09 495) while (1) { /* #5 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 496) next = ptr++; 83dddc0b Steven Rostedt (VMware 2018-03-09 497) if (isspace(*next)) 83dddc0b Steven Rostedt (VMware 2018-03-09 498) continue; 83dddc0b Steven Rostedt (VMware 2018-03-09 499) 83dddc0b Steven Rostedt (VMware 2018-03-09 500) switch (*next) { 83dddc0b Steven Rostedt (VMware 2018-03-09 501) case ')': 83dddc0b Steven Rostedt (VMware 2018-03-09 502) case '\0': 83dddc0b Steven Rostedt (VMware 2018-03-09 503) break; 83dddc0b Steven Rostedt (VMware 2018-03-09 504) case '&': 83dddc0b Steven Rostedt (VMware 2018-03-09 505) case '|': 83dddc0b Steven Rostedt (VMware 2018-03-09 506) if (next[1] == next[0]) { 83dddc0b Steven Rostedt (VMware 2018-03-09 507) ptr++; 83dddc0b Steven Rostedt (VMware 2018-03-09 508) break; 83dddc0b Steven Rostedt (VMware 2018-03-09 509) } 83dddc0b Steven Rostedt (VMware 2018-03-09 510) default: 83dddc0b Steven Rostedt (VMware 2018-03-09 511) parse_error(pe, FILT_ERR_TOO_MANY_PREDS, 83dddc0b Steven Rostedt (VMware 2018-03-09 512) next - str); 83dddc0b Steven Rostedt (VMware 2018-03-09 513) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 514) } 83dddc0b Steven Rostedt (VMware 2018-03-09 515) 83dddc0b Steven Rostedt (VMware 2018-03-09 516) invert = *top & INVERT; 83dddc0b Steven Rostedt (VMware 2018-03-09 517) 83dddc0b Steven Rostedt (VMware 2018-03-09 518) if (*top & PROCESS_AND) { /* #7 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 519) update_preds(prog, N - 1, invert); 83dddc0b Steven Rostedt (VMware 2018-03-09 520) *top &= ~PROCESS_AND; 83dddc0b Steven Rostedt (VMware 2018-03-09 521) } 83dddc0b Steven Rostedt (VMware 2018-03-09 522) if (*next == '&') { /* #8 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 523) *top |= PROCESS_AND; 83dddc0b Steven Rostedt (VMware 2018-03-09 524) break; 83dddc0b Steven Rostedt (VMware 2018-03-09 525) } 83dddc0b Steven Rostedt (VMware 2018-03-09 526) if (*top & PROCESS_OR) { /* #9 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 527) update_preds(prog, N - 1, !invert); 83dddc0b Steven Rostedt (VMware 2018-03-09 528) *top &= ~PROCESS_OR; 83dddc0b Steven Rostedt (VMware 2018-03-09 529) } 83dddc0b Steven Rostedt (VMware 2018-03-09 530) if (*next == '|') { /* #10 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 531) *top |= PROCESS_OR; 83dddc0b Steven Rostedt (VMware 2018-03-09 532) break; 83dddc0b Steven Rostedt (VMware 2018-03-09 533) } 83dddc0b Steven Rostedt (VMware 2018-03-09 534) if (!*next) /* #11 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 535) goto out; 83dddc0b Steven Rostedt (VMware 2018-03-09 536) 83dddc0b Steven Rostedt (VMware 2018-03-09 537) if (top == op_stack) { 83dddc0b Steven Rostedt (VMware 2018-03-09 538) ret = -1; 83dddc0b Steven Rostedt (VMware 2018-03-09 539) /* Too few '(' */ 83dddc0b Steven Rostedt (VMware 2018-03-09 540) parse_error(pe, FILT_ERR_TOO_MANY_CLOSE, ptr - str); 83dddc0b Steven Rostedt (VMware 2018-03-09 541) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 542) } 83dddc0b Steven Rostedt (VMware 2018-03-09 543) top--; /* #12 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 544) } 83dddc0b Steven Rostedt (VMware 2018-03-09 545) } 83dddc0b Steven Rostedt (VMware 2018-03-09 546) out: 83dddc0b Steven Rostedt (VMware 2018-03-09 547) if (top != op_stack) { 83dddc0b Steven Rostedt (VMware 2018-03-09 548) /* Too many '(' */ 83dddc0b Steven Rostedt (VMware 2018-03-09 549) parse_error(pe, FILT_ERR_TOO_MANY_OPEN, ptr - str); 83dddc0b Steven Rostedt (VMware 2018-03-09 550) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 551) } 83dddc0b Steven Rostedt (VMware 2018-03-09 552) 83dddc0b Steven Rostedt (VMware 2018-03-09 553) prog[N].pred = NULL; /* #13 */ 83dddc0b Steven Rostedt (VMware 2018-03-09 554) prog[N].target = 1; /* TRUE */ 83dddc0b Steven Rostedt (VMware 2018-03-09 555) prog[N+1].pred = NULL; 83dddc0b Steven Rostedt (VMware 2018-03-09 556) prog[N+1].target = 0; /* FALSE */ 83dddc0b Steven Rostedt (VMware 2018-03-09 557) prog[N-1].target = N; 83dddc0b Steven Rostedt (VMware 2018-03-09 558) prog[N-1].when_to_branch = false; 83dddc0b Steven Rostedt (VMware 2018-03-09 559) 83dddc0b Steven Rostedt (VMware 2018-03-09 560) /* Second Pass */ 83dddc0b Steven Rostedt (VMware 2018-03-09 561) for (i = N-1 ; i--; ) { 83dddc0b Steven Rostedt (VMware 2018-03-09 562) int target = prog[i].target; 83dddc0b Steven Rostedt (VMware 2018-03-09 563) if (prog[i].when_to_branch == prog[target].when_to_branch) 83dddc0b Steven Rostedt (VMware 2018-03-09 564) prog[i].target = prog[target].target; 83dddc0b Steven Rostedt (VMware 2018-03-09 565) } 83dddc0b Steven Rostedt (VMware 2018-03-09 566) 83dddc0b Steven Rostedt (VMware 2018-03-09 567) /* Third Pass */ 83dddc0b Steven Rostedt (VMware 2018-03-09 568) for (i = 0; i < N; i++) { 83dddc0b Steven Rostedt (VMware 2018-03-09 569) invert = inverts[i] ^ prog[i].when_to_branch; 83dddc0b Steven Rostedt (VMware 2018-03-09 570) prog[i].when_to_branch = invert; 83dddc0b Steven Rostedt (VMware 2018-03-09 571) /* Make sure the program always moves forward */ 83dddc0b Steven Rostedt (VMware 2018-03-09 572) if (WARN_ON(prog[i].target <= i)) { 83dddc0b Steven Rostedt (VMware 2018-03-09 573) ret = -EINVAL; 83dddc0b Steven Rostedt (VMware 2018-03-09 574) goto out_free; 83dddc0b Steven Rostedt (VMware 2018-03-09 575) } 83dddc0b Steven Rostedt (VMware 2018-03-09 576) } 83dddc0b Steven Rostedt (VMware 2018-03-09 577) 83dddc0b Steven Rostedt (VMware 2018-03-09 578) return prog; 83dddc0b Steven Rostedt (VMware 2018-03-09 579) out_free: 83dddc0b Steven Rostedt (VMware 2018-03-09 580) kfree(op_stack); 83dddc0b Steven Rostedt (VMware 2018-03-09 581) kfree(prog_stack); 83dddc0b Steven Rostedt (VMware 2018-03-09 582) kfree(inverts); 83dddc0b Steven Rostedt (VMware 2018-03-09 583) return ERR_PTR(ret); 83dddc0b Steven Rostedt (VMware 2018-03-09 584) } 83dddc0b Steven Rostedt (VMware 2018-03-09 585) --- 0-DAY kernel test infrastructure Open Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation _______________________________________________ kbuild mailing list kbuild@lists.01.org https://lists.01.org/mailman/listinfo/kbuild
