Message ID | 92609f90-7a53-a455-ca72-b9baae224a38@redhat.com |
---|---|
State | New |
Headers | show |
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
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"