Consensus on unit tests?

  There is a lot of work to be done inside the dynamic
loader, particularly when it comes to accelerating the
symbol lookup and searches. See bugs 17645 and 15310.
It would seem immensely beneficial to me to be able
to split up some of these functions and put them through
unit testing to better define their behaviour and interfaces.

I would like to be able to move in incrementally and split
out some common functions, apply unit tests, and then improve
the functional performance by using the same framework to put
the function into a microbenchmark.

Obviously this is not the end goal. We need far more complete
tests that run the dynamic loader through the full sequence of
operations that a user is going to do, but internally it would
help build confidence in the changes to be able to unit test
them.

For example coverity detected a superfluous "always true"
part of a conditional in _dl_addr_inside_object. The statement
"&& reladdr - l->l_phdr[n].p_vaddr >= 0" is always true because
both reladdr and p_vaddr are unsigned quantities whose difference
is always greater than or equal to zero.

I would like to remove the superfluous condition and add a
unit test for all the cases that define the way the interface
should behave.

Since Florian asked for pretty diagrams, I have included them.

If nobody objects to unit tests within the dynamic loader I would
like to use unit tests, not to find bugs, but to effectively design
and limit the implementation's behaviour. The unit tests could for
example exercise that existing code continues to have some odd
corner case behaviour that must not be removed.

Should we allow unit tests for the dynamic loader?

In general the addition of unit tests looks like this:
- Split the function in question into a distinct C file.
- Add the new C file to the list of objects used to build rtld.
- Add a new unit test that links against the built object
  file that contains the function you want to test and provides
  all the things the function needs to operate (sometimes difficult).
- The test shall setup and exercise the interface to define the
  implementation behaviour.

The patch below is really a toy example, but it serves the purpose
to show my idea.
  

On 06/25/2016 01:59 AM, Carlos O'Donell wrote:

> I would like to remove the superfluous condition and add a
> unit test for all the cases that define the way the interface
> should behave.
>
> Since Florian asked for pretty diagrams, I have included them.

I can't quote your patch due to the way it is included in the message 
(inline text after the signature).

What's unclear based on the documentation if the address has to fall in 
the range covered by the link map (i.e., if there are indeed only three 
cases, or five).  If there is indeed a precondition that the address is 
in some special range, you should add it to the comment.

There is also a stray comment in the function itself.

> Should we allow unit tests for the dynamic loader?

I expect unit tests which look like this to be noncontroversial.

Things are more interesting if you have to add testing hooks to the 
code, or export additional symbols.

Thanks,
Florian
  

On 07/01/2016 02:43 AM, Florian Weimer wrote:
> On 06/25/2016 01:59 AM, Carlos O'Donell wrote:
> 
>> I would like to remove the superfluous condition and add a unit
>> test for all the cases that define the way the interface should
>> behave.
>> 
>> Since Florian asked for pretty diagrams, I have included them.
> 
> I can't quote your patch due to the way it is included in the message
> (inline text after the signature).

I can certainly adjust the way I inline my messages if that helps.
Out of curiosity, what MUA are you using?
 
> What's unclear based on the documentation if the address has to fall
> in the range covered by the link map (i.e., if there are indeed only
> three cases, or five).  If there is indeed a precondition that the
> address is in some special range, you should add it to the comment.

There is no precondition that I am aware of. I have clarified the
new patch to say "loadable segment" where I previously said "segment"
to make it more clear.

There are some "optimizations" going on here, and l_contiguous is used
to avoid calling _dl_addr_inside_object, under the assumption that
for finding the "caller" it is sufficient just to see if the address
was between the start and end of the mappings. This is only possible
if the mappings are right beside each other, because otherwise it's
conceivable you might have two ELF files that actually interleave
as long as their segment alignments allow it and the kernel
assigns addresses to the gaps.

> There is also a stray comment in the function itself.

Fixed.

>> Should we allow unit tests for the dynamic loader?
> 
> I expect unit tests which look like this to be noncontroversial.

Thank you for your input.

> Things are more interesting if you have to add testing hooks to the
> code, or export additional symbols.

Agreed. My goal here was to be as open about my vision for testing.
I think unit testing to define an interface is fine. I think unit testing
to look for bugs is not fine. The unit testing should be simple enough to
describe the way the interface works, but not contain a million regression
tests.
  

On 07/04/2016 04:27 PM, Carlos O'Donell wrote:
> On 07/01/2016 02:43 AM, Florian Weimer wrote:
>> On 06/25/2016 01:59 AM, Carlos O'Donell wrote:
>>
>>> I would like to remove the superfluous condition and add a unit
>>> test for all the cases that define the way the interface should
>>> behave.
>>>
>>> Since Florian asked for pretty diagrams, I have included them.
>>
>> I can't quote your patch due to the way it is included in the message
>> (inline text after the signature).
>
> I can certainly adjust the way I inline my messages if that helps.
> Out of curiosity, what MUA are you using?

Thunderbird.  It usually does not have these problems, but this time, 
the patch was included inline after the signature separator.  Somehow, 
Thunderbird ended up treating it as if format=flowed was specified.

>> What's unclear based on the documentation if the address has to fall
>> in the range covered by the link map (i.e., if there are indeed only
>> three cases, or five).  If there is indeed a precondition that the
>> address is in some special range, you should add it to the comment.
>
> There is no precondition that I am aware of. I have clarified the
> new patch to say "loadable segment" where I previously said "segment"
> to make it more clear.

Not even things like “a segment must not cover more than half of the 
address space” or “a segment must not cross the middle of the address 
space”?  Or addr >= l->l_addr?

Intuitively, I would expect that a straight interval comparison as you 
wrote it, without any additional checks, would need an additional bit 
beyond the word size for it to be correct.

Florian
  

On 07/04/2016 03:06 PM, Florian Weimer wrote:
>> There is no precondition that I am aware of. I have clarified the 
>> new patch to say "loadable segment" where I previously said
>> "segment" to make it more clear.
> 
> Not even things like “a segment must not cover more than half of the
> address space” or “a segment must not cross the middle of the address
> space”?  Or addr >= l->l_addr?

I see no reason why a segment can't cover more than half the address space
or cross the middle of the address space.

Equally there is nothing wrong with addr being greater than l->l_addr,
perhaps you meant less than or equal to, which would result in the reladdr
being wrapped.

> Intuitively, I would expect that a straight interval comparison as
> you wrote it, without any additional checks, would need an additional
> bit beyond the word size for it to be correct.

Could you expand on that?

I think the key here is that this is unsigned arithmetic.
  

On 07/04/2016 10:44 PM, Carlos O'Donell wrote:
> On 07/04/2016 03:06 PM, Florian Weimer wrote:
>>> There is no precondition that I am aware of. I have clarified the
>>> new patch to say "loadable segment" where I previously said
>>> "segment" to make it more clear.
>>
>> Not even things like “a segment must not cover more than half of the
>> address space” or “a segment must not cross the middle of the address
>> space”?  Or addr >= l->l_addr?
>
> I see no reason why a segment can't cover more than half the address space
> or cross the middle of the address space.
>
> Equally there is nothing wrong with addr being greater than l->l_addr,
> perhaps you meant less than or equal to, which would result in the reladdr
> being wrapped.

Right, I meant less than l_addr.

I wrote a simulator with 6-bit addresses to check my theory that the 
checks were incorrect.  It turns out I was wrong.  I'm attaching it 
nevertheless.  It is written in Ada because it is one of the few 
languages which have a suitable built-in arithmetic type.  (Using 8-bit 
addresses (unsigned char) in C would result in arithmetic being promoted 
to int, giving different results.)

I also verified this with Z3 in two different ways.  The first one gives 
a garbage result (false positive) with the Z3 version in Fedora, but 
correctly reports unsatisfiable with the master branch.

(declare-const l_addr (_ BitVec 4))
(declare-const p_vaddr (_ BitVec 4))
(declare-const p_memsz (_ BitVec 4))
(declare-const addr (_ BitVec 4))
(assert (<= (+ (bv2int l_addr) (bv2int p_vaddr) (bv2int p_memsz)) 15))
(assert (not (= (and (<= (+ (bv2int l_addr) (bv2int p_vaddr))
			 (bv2int addr))
		     (< (bv2int addr)
			(+ (bv2int l_addr) (bv2int p_vaddr)
			   (bv2int p_memsz))))
		(bvult (bvsub (bvsub addr l_addr) p_vaddr) p_memsz))))
(check-sat)

This one appears to work with older versions, too:

(declare-const l_addr (_ BitVec 8))
(declare-const p_vaddr (_ BitVec 8))
(declare-const p_memsz (_ BitVec 8))
(declare-const addr (_ BitVec 8))

(define-fun no-overflow ((a (_ BitVec 8)) (b (_ BitVec 8))) bool
   (bvuge (bvadd a b) a))

(assert (no-overflow l_addr p_vaddr))
(assert (no-overflow (bvadd l_addr p_vaddr) p_memsz))

(define-fun widen ((a (_ BitVec 8))) (_ BitVec 12)
   (concat #x0 a))

(assert (not (= (and (bvule (bvadd (widen l_addr) (widen p_vaddr))
			    (widen addr))
		     (bvult (widen addr)
			    (bvadd (bvadd (widen l_addr) (widen p_vaddr))
				   (widen p_memsz))))
		(bvult (bvsub (bvsub addr l_addr) p_vaddr) p_memsz))))
(check-sat)

I suspect that this boils down to exhaustive search for Z3 as well; the 
run times go up pretty quickly if you increase the bit vector size.

In all cases, the lingering question is whether the translation is 
correct.  It is more obvious with the ACSL translation (due to Pascal Cuoq):

/*@
   requires (a + v + m) ≤ 0x100000000;
   ensures \result == 1 <==> a + v ≤ x < a + v + m;
*/
int f(unsigned a, unsigned v, unsigned m, unsigned x) {
   unsigned r = x - a;
   return r - v < m;
}

But none of the ACSL provers we tried could handle this.

Anyway, I now believe your patch is correct.

Florian
  

You asked about the general concept of unit tests, and the following
discussion was only about the technical issues with the specific code in
your example.  

I think the general notion of unit tests is a very good one.  I don't
see any obvious problems in the approach you've taken to building a unit
test.  Of course, any particular refactoring change to enable unit
testing might have issues and "It's for a unit test!" is not any kind of
trump over usual review concerns.

The likely pitfall I would look out for is when breaking some function
out into its own file to make it unit-testable might perturb the
optimization opportunities for the function in the actual build.  We
should be careful about that.  In your first example, the function was
already global, so there is no particular reason to worry about that
issue.


Thanks,
Roland