• Eduard Zingerman's avatar
    selftests/bpf: test if state loops are detected in a tricky case · 64870fee
    Eduard Zingerman authored
    A convoluted test case for iterators convergence logic that
    demonstrates that states with branch count equal to 0 might still be
    a part of not completely explored loop.
    
    E.g. consider the following state diagram:
    
                   initial     Here state 'succ' was processed first,
                     |         it was eventually tracked to produce a
                     V         state identical to 'hdr'.
        .---------> hdr        All branches from 'succ' had been explored
        |            |         and thus 'succ' has its .branches == 0.
        |            V
        |    .------...        Suppose states 'cur' and 'succ' correspond
        |    |       |         to the same instruction + callsites.
        |    V       V         In such case it is necessary to check
        |   ...     ...        whether 'succ' and 'cur' are identical.
        |    |       |         If 'succ' and 'cur' are a part of the same loop
        |    V       V         they have to be compared exactly.
        |   succ <- cur
        |    |
        |    V
        |   ...
        |    |
        '----'
    Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
    Link: https://lore.kernel.org/r/20231024000917.12153-7-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    64870fee
iters.c 29 KB