diff mbox

Consensus on unit tests?

Message ID 92609f90-7a53-a455-ca72-b9baae224a38@redhat.com
State Not Applicable
Headers show

Commit Message

Carlos O'Donell June 24, 2016, 11:59 p.m. UTC
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.

Comments

Florian Weimer July 1, 2016, 6:43 a.m. UTC | #1
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
Carlos O'Donell July 4, 2016, 2:27 p.m. UTC | #2
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.
Florian Weimer July 4, 2016, 7:06 p.m. UTC | #3
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
Carlos O'Donell July 4, 2016, 8:44 p.m. UTC | #4
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.
Florian Weimer Aug. 15, 2016, 2:23 p.m. UTC | #5
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
Roland McGrath Sept. 3, 2016, 12:32 a.m. UTC | #6
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
diff mbox

Patch

diff --git a/elf/Makefile b/elf/Makefile
index 210dde9..cd8df19 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -23,7 +23,7 @@  include ../Makeconfig
 
 headers		= elf.h bits/elfclass.h link.h bits/link.h
 routines	= $(all-dl-routines) dl-support dl-iteratephdr \
-		  dl-addr enbl-secure dl-profstub \
+		  dl-addr dl-addr-obj enbl-secure dl-profstub \
 		  dl-origin dl-libc dl-sym dl-tsd dl-sysdep
 
 # The core dynamic linking functions are in libc for the static and
@@ -312,6 +312,9 @@  tests-special += $(objpfx)tst-prelink-cmp.out
 endif
 endif
 
+tests += tst-_dl_addr_inside_object
+$(objpfx)tst-_dl_addr_inside_object: $(objpfx)dl-addr-obj.os
+
 include ../Rules
 
 ifeq (yes,$(build-shared))
diff --git a/elf/dl-addr-obj.c b/elf/dl-addr-obj.c
new file mode 100644
index 0000000..2ac97a6
--- /dev/null
+++ b/elf/dl-addr-obj.c
@@ -0,0 +1,72 @@ 
+/* Determine if address is inside object segments.
+   Copyright (C) 1996-2016 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <link.h>
+#include <elf.h>
+
+/* Return non-zero if ADDR lies within one of L's segments.
+   We have three cases we care about and we do not need to avoid overflow.
+
+   Case 1: addr is above a segment.
+   +==================+<- l_map_end
+   |                  |<- addr
+   |------------------|<- l_addr + p_vaddr + p_memsz
+   |                  |
+   |                  |
+   |------------------|<- l_addr + p_vaddr
+   |------------------|<- l_addr
+   |                  |
+   +==================+<- l_map_start
+
+   Case 2: addr is within a segments.
+   +==================+<- l_map_end
+   |                  |
+   |------------------|<- l_addr + p_vaddr + p_memsz
+   |                  |<- addr
+   |                  |
+   |------------------|<- l_addr + p_vaddr
+   |------------------|<- l_addr
+   |                  |
+   +==================+<- l_map_start
+
+   Case 3: addr is below a segments.
+   +==================+<- l_map_end
+   |                  |
+   |------------------|<- l_addr + p_vaddr + p_memsz
+   |                  |
+   |                  |
+   |------------------|<- l_addr + p_vaddr
+   |------------------|<- l_addr
+   |                  |<- addr
+   +==================+<- l_map_start
+
+*/
+int
+internal_function
+_dl_addr_inside_object (struct link_map *l, const ElfW(Addr) addr)
+{
+  int n = l->l_phnum;
+  const ElfW(Addr) reladdr = addr - l->l_addr;
+
+	/*&& reladdr - l->l_phdr[n].p_vaddr >= 0*/
+  while (--n >= 0)
+    if (l->l_phdr[n].p_type == PT_LOAD
+	&& reladdr - l->l_phdr[n].p_vaddr < l->l_phdr[n].p_memsz)
+      return 1;
+  return 0;
+}
diff --git a/elf/dl-addr.c b/elf/dl-addr.c
index 291ff55..5a4ab1e 100644
--- a/elf/dl-addr.c
+++ b/elf/dl-addr.c
@@ -143,19 +143,3 @@  _dl_addr (const void *address, Dl_info *info,
   return result;
 }
 libc_hidden_def (_dl_addr)
-
-/* Return non-zero if ADDR lies within one of L's segments.  */
-int
-internal_function
-_dl_addr_inside_object (struct link_map *l, const ElfW(Addr) addr)
-{
-  int n = l->l_phnum;
-  const ElfW(Addr) reladdr = addr - l->l_addr;
-
-  while (--n >= 0)
-    if (l->l_phdr[n].p_type == PT_LOAD
-	&& reladdr - l->l_phdr[n].p_vaddr >= 0
-	&& reladdr - l->l_phdr[n].p_vaddr < l->l_phdr[n].p_memsz)
-      return 1;
-  return 0;
-}
diff --git a/elf/dl-open.c b/elf/dl-open.c
index 6f178b3..70f3f1e 100644
--- a/elf/dl-open.c
+++ b/elf/dl-open.c
@@ -735,21 +735,3 @@  _dl_show_scope (struct link_map *l, int from)
     _dl_debug_printf (" no scope\n");
   _dl_debug_printf ("\n");
 }
-
-#if IS_IN (rtld)
-/* Return non-zero if ADDR lies within one of L's segments.  */
-int
-internal_function
-_dl_addr_inside_object (struct link_map *l, const ElfW(Addr) addr)
-{
-  int n = l->l_phnum;
-  const ElfW(Addr) reladdr = addr - l->l_addr;
-
-  while (--n >= 0)
-    if (l->l_phdr[n].p_type == PT_LOAD
-	&& reladdr - l->l_phdr[n].p_vaddr >= 0
-	&& reladdr - l->l_phdr[n].p_vaddr < l->l_phdr[n].p_memsz)
-      return 1;
-  return 0;
-}
-#endif
diff --git a/elf/tst-_dl_addr_inside_object.c b/elf/tst-_dl_addr_inside_object.c
new file mode 100644
index 0000000..b268578
--- /dev/null
+++ b/elf/tst-_dl_addr_inside_object.c
@@ -0,0 +1,194 @@ 
+/* Unit test for _dl_addr_inside_object.
+   Copyright (C) 2016 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <link.h>
+#include <elf.h>
+
+extern int _dl_addr_inside_object (struct link_map *l, const ElfW(Addr) addr);
+
+static int
+do_test (void)
+{
+  int ret;
+  ElfW(Addr) addr;
+  struct link_map map;
+  ElfW(Phdr) header;
+  map.l_phdr = &header;
+  map.l_phnum = 1;
+  map.l_addr = 0x0;
+  /* Segment spans 0x2000 -> 0x4000.  */
+  header.p_vaddr = 0x2000;
+  header.p_memsz = 0x2000;
+  header.p_type = PT_LOAD;
+  /* Address is above the segment e.g. > 0x4000.  */
+  addr = 0x5000;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("PASS: Above: Address is detected as outside the segment.\n");
+	break;
+      case 1:
+        printf ("FAIL: Above: Address is detected as inside the segment.\n");
+	exit (1);
+	break;
+      default:
+	printf ("FAIL: Above: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is inside the segment e.g. 0x2000 < addr < 0x4000.  */
+  addr = 0x3000;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("FAIL: Inside: Address is detected as outside the segment.\n");
+	exit (1);
+	break;
+      case 1:
+        printf ("PASS: Inside: Address is detected as inside the segment.\n");
+	break;
+      default:
+	printf ("FAIL: Inside: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is below the segment e.g. < 0x2000.  */
+  addr = 0x1000;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("PASS: Below: Address is detected as outside the segment.\n");
+	break;
+      case 1:
+        printf ("FAIL: Below: Address is detected as inside the segment.\n");
+	exit (1);
+	break;
+      default:
+	printf ("FAIL: Below: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is in the segment and addr == p_vaddr.  */
+  addr = 0x2000;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("FAIL: At p_vaddr: Address is detected as outside the segment.\n");
+	exit (1);
+	break;
+      case 1:
+        printf ("PASS: At p_vaddr: Address is detected as inside the segment.\n");
+	break;
+      default:
+	printf ("FAIL: At p_vaddr: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is in the segment and addr == p_vaddr + p_memsz - 1.  */
+  addr = 0x2000 + 0x2000 - 0x1;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("FAIL: At p_memsz-1: Address is detected as outside the segment.\n");
+	exit (1);
+	break;
+      case 1:
+        printf ("PASS: At p_memsz-1: Address is detected as inside the segment.\n");
+	break;
+      default:
+	printf ("FAIL: At p_memsz-1: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is outside the segment and addr == p_vaddr + p_memsz.  */
+  addr = 0x2000 + 0x2000;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("PASS: At p_memsz: Address is detected as outside the segment.\n");
+	break;
+      case 1:
+        printf ("FAIL: At p_memsz: Address is detected as inside the segment.\n");
+	exit (1);
+	break;
+      default:
+	printf ("FAIL: At p_memsz: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is outside the segment and p_vaddr at maximum address.  */
+  addr = 0x0 - 0x2;
+  header.p_vaddr = 0x0 - 0x1;
+  header.p_memsz = 0x1;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("PASS: At max: Address is detected as outside the segment.\n");
+	break;
+      case 1:
+        printf ("FAIL: At max: Address is detected as inside the segment.\n");
+	exit (1);
+	break;
+      default:
+	printf ("FAIL: At max: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is outside the segment and p_vaddr at minimum address.  */
+  addr = 0x1;
+  header.p_vaddr = 0x0;
+  header.p_memsz = 0x1;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("PASS: At min: Address is detected as outside the segment.\n");
+	break;
+      case 1:
+        printf ("FAIL: At min: Address is detected as inside the segment.\n");
+	exit (1);
+	break;
+      default:
+	printf ("FAIL: At min: Invalid return value.\n");
+	exit (1);
+    }
+  /* Address is always inside the segment with p_memsz at max.  */
+  addr = 0x0;
+  header.p_vaddr = 0x0;
+  header.p_memsz = 0x0 - 0x1;
+  ret = _dl_addr_inside_object (&map, addr);
+  switch (ret)
+    {
+      case 0:
+	printf ("FAIL: At maxmem: Address is detected as outside the segment.\n");
+	exit (1);
+	break;
+      case 1:
+        printf ("PASS: At maxmem: Address is detected as inside the segment.\n");
+	break;
+      default:
+	printf ("FAIL: At maxmem: Invalid return value.\n");
+	exit (1);
+    }
+  return 0;
+}
+
+#define TEST_FUNCTION do_test ()
+#include "../test-skeleton.c"