testing and code coverage

Posted May 31, 2006 14:54 UTC (Wed) by mingo (subscriber, #31122)
In reply to: testing and code coverage by jreiser
Parent article: The kernel lock validator

Second, the problem is not only "branches of code [coverage of basic blocks]." The problem is conditional execution paths through multiple basic blocks, including re-convergent fanout (correlated conditions) and partial correctness with "don't care" conditions.

yes - code coverage and testing is alot more than just basic coverage of all existing code.

but coverage that triggers locking is alot simpler than full coverage, because locks are almost always taken in simple ways, without too many branches. So while in theory code like this:


void function1(unsigned long mask)
{
        if (mask & 0x00000001)
                spin_lock(&lock0);
        if (mask & 0x00000002)
                spin_lock(&lock1);
        if (mask & 0x00000004)
                spin_lock(&lock2);
        if (mask & 0x00000008)
                spin_lock(&lock3);
        if (mask & 0x00000010)
                spin_lock(&lock4);
...
        if (mask & 0x80000000)
                spin_lock(&lock31);
}

could exist in the kernel and would require 4 billion values of 'mask' to cycle through all the possible locking scenarios, in practice the kernel is full of much simpler locking constructs:

void function2(unsigned long mask)
{
        spin_lock(&lock);
        ...
        spin_unlock(&lock);
}

where covering the function once is probably enough to map its locking impact. In fact, "tricky", non-straight locking code is being frowned upon from a review and quality POV, which too works in favor of validation quality. To stay with the function1() example, such code will very likely be rejected at a very early review stage.

and finally, even theoretical full code coverage is alot simpler than the possible combinations of codepaths on an multiprocessor system that could trigger deadlocks.

naturally, being a dynamic method, the lock validator can only claim correctness about codepaths it actually observes (any other code doesnt even exist for it), and thus it still depends on how frequently (and with what memory state) those codepaths get triggered.