Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #18420 > unrolled thread
| Started by | Don Y <this@isnotme.com> |
|---|---|
| First post | 2012-03-09 16:43 -0700 |
| Last post | 2012-03-14 11:54 -0700 |
| Articles | 20 on this page of 90 — 12 participants |
Back to article view | Back to comp.lang.c
Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-09 16:43 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 12:56 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-09 19:40 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 17:53 +1300
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 18:12 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 02:05 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 23:17 +1300
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-10 12:00 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 11:00 +1300
Re: Regression testing for pointers Ike Naar <ike@iceland.freeshell.org> - 2012-03-10 22:23 +0000
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-10 22:40 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 12:12 +1300
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-11 00:42 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 14:26 +1300
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-11 03:09 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 18:16 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 12:01 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 10:35 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 09:19 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 07:23 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:23 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:25 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 00:19 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 20:34 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 01:00 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:22 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 10:19 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 07:25 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 02:00 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 22:18 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 11:32 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-15 05:58 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-15 05:55 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-15 11:32 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-16 18:14 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-20 01:43 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-20 21:59 +1300
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-16 03:05 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-20 02:33 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-24 11:49 +1300
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 05:01 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 09:44 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-12 09:56 +1300
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-10 02:28 -0800
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 11:09 -0700
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-10 18:29 +0000
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 05:22 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 09:50 -0700
Re: Regression testing for pointers "io_x" <a@b.c.invalid> - 2012-03-13 13:09 +0100
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-10 03:14 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 12:42 -0700
Re: Regression testing for pointers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-10 08:42 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 02:19 -0700
Re: Regression testing for pointers "BartC" <bc@freeuk.com> - 2012-03-10 15:54 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 11:49 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 06:09 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 12:33 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-12 03:29 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 10:01 -0700
Re: Regression testing for pointers "BartC" <bc@freeuk.com> - 2012-03-13 18:56 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 16:31 -0700
Re: Regression testing for pointers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-12 00:30 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:41 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-12 13:39 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 09:36 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 07:25 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:28 -0700
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 04:20 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:34 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 00:29 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:31 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 01:05 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:30 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 10:43 -0700
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-10 15:41 -0800
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 11:23 -0700
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-13 13:43 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 01:45 -0700
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-14 15:15 -0700
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-14 22:57 +0000
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-15 13:10 -0700
Re: Regression testing for pointers jgk@panix.com (Joe keane) - 2012-03-16 22:20 +0000
Re: Regression testing for pointers "io_x" <a@b.c.invalid> - 2012-03-18 07:15 +0100
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 23:13 -0700
Re: Regression testing for pointers gordonb.b29ri@burditt.org (Gordon Burditt) - 2012-03-12 19:37 -0500
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 19:23 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 13:12 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 01:54 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 22:05 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 11:54 -0700
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-12 16:23 -0700 |
| Message-ID | <jjm0hj$vtl$1@speranza.aioe.org> |
| In reply to | #18600 |
Hi Ian,
On 3/12/2012 11:23 AM, Ian Collins wrote:
> So add a test.
> So add a test.
> So add a test.
> So add a test.
> So add a test.
So I -- and anyone modifying the test suite -- should be diligent
enough to verify all of these issues INSTEAD OF something like:
ASSERT(result == 0x80032440)
which performs *all* of these "additional tests". If result is
*not* 0x80032440 then one of the other enumerated issues was
not satisfied!
If you were testing strchr(3), would you do:
template = "ABCDEABCFF
sought = 'C'
result = strchr(template, sought)
ASSERT(result >= &template[0])
ASSERT(result < &template[strlen(template)])
ASSERT(*result == sought)
ASSERT(result[1] == sought+1)
Or, would you do:
ASSERT(result == &template[2])
>> This embodies *all* of the above tests and gives the
>> function far less "wiggle room".
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-13 17:25 +1300 |
| Message-ID | <9s80hcFhvvU1@mid.individual.net> |
| In reply to | #18615 |
On 03/13/12 12:23 PM, Don Y wrote: > Hi Ian, > > On 3/12/2012 11:23 AM, Ian Collins wrote: > >> So add a test. > >> So add a test. > >> So add a test. > >> So add a test. > >> So add a test. > > So I -- and anyone modifying the test suite -- should be diligent > enough to verify all of these issues INSTEAD OF something like: > ASSERT(result == 0x80032440) > which performs *all* of these "additional tests". If result is > *not* 0x80032440 then one of the other enumerated issues was > not satisfied! If you have a condition you want to test, test it. > If you were testing strchr(3), would you do: > template = "ABCDEABCFF > sought = 'C' > result = strchr(template, sought) > ASSERT(result>=&template[0]) > ASSERT(result< &template[strlen(template)]) > ASSERT(*result == sought) > ASSERT(result[1] == sought+1) > > Or, would you do: > ASSERT(result ==&template[2]) > >>> This embodies *all* of the above tests and gives the >>> function far less "wiggle room". That doesn't make any sense and bears no resemblance to the questions you asked and subsequently snipped. You added additional requirements, I suggested you add tests for them. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-13 00:19 -0700 |
| Message-ID | <jjmser$jnv$1@speranza.aioe.org> |
| In reply to | #18629 |
On 3/12/2012 9:25 PM, Ian Collins wrote: > On 03/13/12 12:23 PM, Don Y wrote: >> Hi Ian, >> >> On 3/12/2012 11:23 AM, Ian Collins wrote: >> >>> So add a test. >> >>> So add a test. >> >>> So add a test. >> >>> So add a test. >> >>> So add a test. >> >> So I -- and anyone modifying the test suite -- should be diligent >> enough to verify all of these issues INSTEAD OF something like: >> ASSERT(result == 0x80032440) >> which performs *all* of these "additional tests". If result is >> *not* 0x80032440 then one of the other enumerated issues was >> not satisfied! > > If you have a condition you want to test, test it. > >> If you were testing strchr(3), would you do: >> template = "ABCDEABCFF >> sought = 'C' >> result = strchr(template, sought) >> ASSERT(result>=&template[0]) >> ASSERT(result< &template[strlen(template)]) >> ASSERT(*result == sought) >> ASSERT(result[1] == sought+1) >> >> Or, would you do: >> ASSERT(result ==&template[2]) >> >>>> This embodies *all* of the above tests and gives the >>>> function far less "wiggle room". > > That doesn't make any sense and bears no resemblance to the questions > you asked and subsequently snipped. If your comment applies to the strchr example, that is intended to show that you can present lots of tests/criteria to *infer* that the result is correct. *OR*, you could just CHECK THE RESULT! You *know* what the conditions are when the test is executed (i.e., you know what the resolution of your math library is, you know the value(s) of the inputs to the routines under test) so all you have to do is verify that the *result* is EXACTLY what you expect it to be. No need to look at indirect evidence when you have a concrete result that you can test! > You added additional requirements, I > suggested you add tests for them. ASSERT(result == 0x80032440) exactly and unequivocally proves ALL CONDITIONS are met. Specifically, it states (knowing the conditions in which the test suite executed) that: - the request was satisfied (i.e., the heap's condition at the time was such that the criteria associated with the request could be met) - the *correct* fragment in the free list was selected (because I *knew* what the free list should have contained) - the correct *portion* of the selected fragment was chosen to be returned to the caller - the correct *alignment* was enforced - the correct size chunk was returned to the caller - the internal state of the free list remains consistent (as will be evidenced in subsequent requests) All of those facts are expressed in that single assertion. Change any digit in the constant shown and one or more of these facts are no longer true. I don't have to, separately, test: - did the function return non-NULL? OK, then the request was satisfied - did the function select the LASTFIT fragment as directed (how do you know without peeking inside the free list?) - did the function pick the right *part* of that fragment to use in satisfying the request (how do you know if you can't see the actual bounds of the fragment BEFORE it was selected/manipulated?) - did the request get properly aligned per the requirements of the processor and compiler (again, without seeing the pre-selected fragment, how do you know that any "work" was done on that selection?) - did the right amount of "excess" get trimmed off the fragment prior to being returned - what are the chances that the new state of the free list is as it should be? how many more of these questions do I need to answer in the next N example invocations to assure myself of that? *And*, any other criteria embedded in the function now or in the future are also proven by this. Change a digit in ASSERT(sqrt(3.0) == 1.732) and you KNOW the sqrt code isn't working properly.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-13 20:34 +1300 |
| Message-ID | <9s8bjmFhvvU5@mid.individual.net> |
| In reply to | #18643 |
On 03/13/12 08:19 PM, Don Y wrote: > On 3/12/2012 9:25 PM, Ian Collins wrote: >> On 03/13/12 12:23 PM, Don Y wrote: >>> Hi Ian, >>> >>> On 3/12/2012 11:23 AM, Ian Collins wrote: >>> >>>> So add a test. >>> >>>> So add a test. >>> >>>> So add a test. >>> >>>> So add a test. >>> >>>> So add a test. >>> >>> So I -- and anyone modifying the test suite -- should be diligent >>> enough to verify all of these issues INSTEAD OF something like: >>> ASSERT(result == 0x80032440) >>> which performs *all* of these "additional tests". If result is >>> *not* 0x80032440 then one of the other enumerated issues was >>> not satisfied! >> >> If you have a condition you want to test, test it. >> >>> If you were testing strchr(3), would you do: >>> template = "ABCDEABCFF >>> sought = 'C' >>> result = strchr(template, sought) >>> ASSERT(result>=&template[0]) >>> ASSERT(result< &template[strlen(template)]) >>> ASSERT(*result == sought) >>> ASSERT(result[1] == sought+1) >>> >>> Or, would you do: >>> ASSERT(result ==&template[2]) >>> >>>>> This embodies *all* of the above tests and gives the >>>>> function far less "wiggle room". >> >> That doesn't make any sense and bears no resemblance to the questions >> you asked and subsequently snipped. > > If your comment applies to the strchr example, that is intended > to show that you can present lots of tests/criteria to *infer* > that the result is correct. *OR*, you could just CHECK THE > RESULT! You *know* what the conditions are when the test > is executed (i.e., you know what the resolution of your math > library is, you know the value(s) of the inputs to the routines > under test) so all you have to do is verify that the *result* > is EXACTLY what you expect it to be. No need to look at > indirect evidence when you have a concrete result that you > can test! Your typical memory allocator is a little more complex and less deterministic than strchr(). >> You added additional requirements, I >> suggested you add tests for them. > > ASSERT(result == 0x80032440) > > exactly and unequivocally proves ALL CONDITIONS are met. > Specifically, it states (knowing the conditions in which > the test suite executed) that: > - the request was satisfied (i.e., the heap's condition > at the time was such that the criteria associated with > the request could be met) > - the *correct* fragment in the free list was selected > (because I *knew* what the free list should have contained) > - the correct *portion* of the selected fragment was chosen > to be returned to the caller > - the correct *alignment* was enforced > - the correct size chunk was returned to the caller > - the internal state of the free list remains consistent > (as will be evidenced in subsequent requests) > > All of those facts are expressed in that single assertion. > Change any digit in the constant shown and one or more of > these facts are no longer true. Nowhere in your earlier descriptions was that requirement mentioned. I thought you were test a general purpose allocator. If your requirements are that specific, what's wrong with ASSERT(result == heapBase+0x32440)? The base address can still be flexible. > I don't have to, separately, test: > - did the function return non-NULL? OK, then the request > was satisfied > - did the function select the LASTFIT fragment as directed > (how do you know without peeking inside the free list?) > - did the function pick the right *part* of that fragment > to use in satisfying the request (how do you know if > you can't see the actual bounds of the fragment BEFORE > it was selected/manipulated?) > - did the request get properly aligned per the requirements > of the processor and compiler (again, without seeing the > pre-selected fragment, how do you know that any "work" > was done on that selection?) > - did the right amount of "excess" get trimmed off the > fragment prior to being returned > - what are the chances that the new state of the free list > is as it should be? how many more of these questions do > I need to answer in the next N example invocations to > assure myself of that? > > *And*, any other criteria embedded in the function now > or in the future are also proven by this. I would probably test the competent functions individually (those working with slabs) and mock them in the allocator tests. If you were to build your allocator test first, the design would end up with wouldn't require tests that poke around in the internal structures. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-13 01:00 -0700 |
| Message-ID | <jjmurk$ohs$1@speranza.aioe.org> |
| In reply to | #18645 |
On 3/13/2012 12:34 AM, Ian Collins wrote: >>>> So I -- and anyone modifying the test suite -- should be diligent >>>> enough to verify all of these issues INSTEAD OF something like: >>>> ASSERT(result == 0x80032440) >>>> which performs *all* of these "additional tests". If result is >>>> *not* 0x80032440 then one of the other enumerated issues was >>>> not satisfied! >>> >>> If you have a condition you want to test, test it. >>> >>>> If you were testing strchr(3), would you do: >>>> template = "ABCDEABCFF >>>> sought = 'C' >>>> result = strchr(template, sought) >>>> ASSERT(result>=&template[0]) >>>> ASSERT(result< &template[strlen(template)]) >>>> ASSERT(*result == sought) >>>> ASSERT(result[1] == sought+1) >>>> >>>> Or, would you do: >>>> ASSERT(result ==&template[2]) >>>> >>>>>> This embodies *all* of the above tests and gives the >>>>>> function far less "wiggle room". >>> >>> That doesn't make any sense and bears no resemblance to the questions >>> you asked and subsequently snipped. >> >> If your comment applies to the strchr example, that is intended >> to show that you can present lots of tests/criteria to *infer* >> that the result is correct. *OR*, you could just CHECK THE >> RESULT! You *know* what the conditions are when the test >> is executed (i.e., you know what the resolution of your math >> library is, you know the value(s) of the inputs to the routines >> under test) so all you have to do is verify that the *result* >> is EXACTLY what you expect it to be. No need to look at >> indirect evidence when you have a concrete result that you >> can test! > > Your typical memory allocator is a little more complex and less > deterministic than strchr(). But it still produces *a* result. It is a deterministic algorithm (even if the specification -- like malloc -- doesn't make that determinism explicit). With a given set of operating conditions and inputs, you **KNOW** what the result will be. TEST FOR THAT RESULT! >>> You added additional requirements, I >>> suggested you add tests for them. >> >> ASSERT(result == 0x80032440) >> >> exactly and unequivocally proves ALL CONDITIONS are met. >> Specifically, it states (knowing the conditions in which >> the test suite executed) that: >> - the request was satisfied (i.e., the heap's condition >> at the time was such that the criteria associated with >> the request could be met) >> - the *correct* fragment in the free list was selected >> (because I *knew* what the free list should have contained) >> - the correct *portion* of the selected fragment was chosen >> to be returned to the caller >> - the correct *alignment* was enforced >> - the correct size chunk was returned to the caller >> - the internal state of the free list remains consistent >> (as will be evidenced in subsequent requests) >> >> All of those facts are expressed in that single assertion. >> Change any digit in the constant shown and one or more of >> these facts are no longer true. > > Nowhere in your earlier descriptions was that requirement mentioned. Because I didn't consider it germane to the concept of "testing pointer values". The specification is 15 pages. > I thought you were test a general purpose allocator. > > If your requirements are that specific, what's wrong with > > ASSERT(result == heapBase+0x32440)? What happens if heapBase is effectively (char *) -32400? What happens if the processor only has a 16b address space? What happens if that +32440 was a consequence of pointer alignment requirements on THIS PLATFORM? What happens if there isn't physical memory present at that location? > The base address can still be flexible. > >> I don't have to, separately, test: >> - did the function return non-NULL? OK, then the request >> was satisfied >> - did the function select the LASTFIT fragment as directed >> (how do you know without peeking inside the free list?) >> - did the function pick the right *part* of that fragment >> to use in satisfying the request (how do you know if >> you can't see the actual bounds of the fragment BEFORE >> it was selected/manipulated?) >> - did the request get properly aligned per the requirements >> of the processor and compiler (again, without seeing the >> pre-selected fragment, how do you know that any "work" >> was done on that selection?) >> - did the right amount of "excess" get trimmed off the >> fragment prior to being returned >> - what are the chances that the new state of the free list >> is as it should be? how many more of these questions do >> I need to answer in the next N example invocations to >> assure myself of that? >> >> *And*, any other criteria embedded in the function now >> or in the future are also proven by this. > > I would probably test the competent functions individually (those > working with slabs) and mock them in the allocator tests. If you were to > build your allocator test first, the design would end up with wouldn't > require tests that poke around in the internal structures. The approach I have taken (to testing on *one particular* platform) eliminates the need for "peeking inside". If I know where (on this particular platform) the heap is located and how large it is and alignment constraints, etc. AND have just initialized the heap... THEN: - I know what the internal free list looks like, "conceptually" (I might not know specific bit patterns but I know what the free list *reflects* -- a heap that is completely FULL! - given that free list, I know how any particular allocation request WILL be handled. - given how that request is handled, I now know what the NEW state of the free list will be. - lather, rinse, repeat And, all I need to do to convince myself that my idea of what's happening "under the covers" agrees with what is *really* under the covers is to repeat this process a sufficient number of times and in an appropriately clever order to remove any doubt.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-13 21:22 +1300 |
| Message-ID | <9s8ee6FhvvU6@mid.individual.net> |
| In reply to | #18646 |
On 03/13/12 09:00 PM, Don Y wrote: > On 3/13/2012 12:34 AM, Ian Collins wrote: > >>>>> So I -- and anyone modifying the test suite -- should be diligent >>>>> enough to verify all of these issues INSTEAD OF something like: >>>>> ASSERT(result == 0x80032440) >>>>> which performs *all* of these "additional tests". If result is >>>>> *not* 0x80032440 then one of the other enumerated issues was >>>>> not satisfied! >>>> >>>> If you have a condition you want to test, test it. >>>> >>>>> If you were testing strchr(3), would you do: >>>>> template = "ABCDEABCFF >>>>> sought = 'C' >>>>> result = strchr(template, sought) >>>>> ASSERT(result>=&template[0]) >>>>> ASSERT(result< &template[strlen(template)]) >>>>> ASSERT(*result == sought) >>>>> ASSERT(result[1] == sought+1) >>>>> >>>>> Or, would you do: >>>>> ASSERT(result ==&template[2]) >>>>> >>>>>>> This embodies *all* of the above tests and gives the >>>>>>> function far less "wiggle room". >>>> >>>> That doesn't make any sense and bears no resemblance to the questions >>>> you asked and subsequently snipped. >>> >>> If your comment applies to the strchr example, that is intended >>> to show that you can present lots of tests/criteria to *infer* >>> that the result is correct. *OR*, you could just CHECK THE >>> RESULT! You *know* what the conditions are when the test >>> is executed (i.e., you know what the resolution of your math >>> library is, you know the value(s) of the inputs to the routines >>> under test) so all you have to do is verify that the *result* >>> is EXACTLY what you expect it to be. No need to look at >>> indirect evidence when you have a concrete result that you >>> can test! >> >> Your typical memory allocator is a little more complex and less >> deterministic than strchr(). > > But it still produces *a* result. It is a deterministic > algorithm (even if the specification -- like malloc -- doesn't > make that determinism explicit). With a given set of operating > conditions and inputs, you **KNOW** what the result will be. > TEST FOR THAT RESULT! It may produce a result, but more often than not, the exact value is of little on no consequence. If you start to test for specific values based on knowledge of the internals, you end up with a very fragile test harness. I think this may have been what you were saying elsewhere. If your tests become bonded to single implementation, you are stuck with it. If your tests don't assume specific values, you are free to change the internals of the function as long as you don't break its published behaviour. Obviously if your internal implementation is specified you are stuck. Memory allocators are definitely one of those cases where one size does not fit all, just look at the range of malloc libraries available for a typical non-embedded environment. They would all pass the same test suite assuming the tests didn't make assumptions about the implementation. >> I thought you were test a general purpose allocator. >> >> If your requirements are that specific, what's wrong with >> >> ASSERT(result == heapBase+0x32440)? > > What happens if heapBase is effectively (char *) -32400? > What happens if the processor only has a 16b address space? > What happens if that +32440 was a consequence of pointer > alignment requirements on THIS PLATFORM? > What happens if there isn't physical memory present at > that location? You break 0x32440 down into platform independent variables. >> The base address can still be flexible. >> >>> I don't have to, separately, test: >>> - did the function return non-NULL? OK, then the request >>> was satisfied >>> - did the function select the LASTFIT fragment as directed >>> (how do you know without peeking inside the free list?) >>> - did the function pick the right *part* of that fragment >>> to use in satisfying the request (how do you know if >>> you can't see the actual bounds of the fragment BEFORE >>> it was selected/manipulated?) >>> - did the request get properly aligned per the requirements >>> of the processor and compiler (again, without seeing the >>> pre-selected fragment, how do you know that any "work" >>> was done on that selection?) >>> - did the right amount of "excess" get trimmed off the >>> fragment prior to being returned >>> - what are the chances that the new state of the free list >>> is as it should be? how many more of these questions do >>> I need to answer in the next N example invocations to >>> assure myself of that? >>> >>> *And*, any other criteria embedded in the function now >>> or in the future are also proven by this. >> >> I would probably test the competent functions individually (those >> working with slabs) and mock them in the allocator tests. If you were to >> build your allocator test first, the design would end up with wouldn't >> require tests that poke around in the internal structures. > > The approach I have taken (to testing on *one particular* platform) > eliminates the need for "peeking inside". > > If I know where (on this particular platform) the heap is located > and how large it is and alignment constraints, etc. AND have just > initialized the heap... THEN: > - I know what the internal free list looks like, "conceptually" > (I might not know specific bit patterns but I know what the > free list *reflects* -- a heap that is completely FULL! > - given that free list, I know how any particular allocation > request WILL be handled. > - given how that request is handled, I now know what the NEW > state of the free list will be. > - lather, rinse, repeat Until someone introduces a critical optimisation that changes the layout... I still think you are testing at too high a level, test the functions that manipulate your internal independently. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-13 10:19 -0700 |
| Message-ID | <jjnvii$e7d$1@speranza.aioe.org> |
| In reply to | #18651 |
Hi Ian, >>> Your typical memory allocator is a little more complex and less >>> deterministic than strchr(). >> >> But it still produces *a* result. It is a deterministic >> algorithm (even if the specification -- like malloc -- doesn't >> make that determinism explicit). With a given set of operating >> conditions and inputs, you **KNOW** what the result will be. >> TEST FOR THAT RESULT! > > It may produce a result, but more often than not, the exact value is of > little on no consequence. Is the exact value of sqrt()'s result of no consequence? > If you start to test for specific values based > on knowledge of the internals, you end up with a very fragile test No! I am *not* looking at test internals. I am looking at the SPECIFIED, CONTRACTUAL BEHAVIOR of the function. Are you "looking at internals" when you test the return value of sqrt(5)? The sqrt function returns a positive value for all non negative arguments such that the value, when multiplied by itself, yields the original argument. THAT is what you test for! A *good* test picks values that are likely to cause problems in an implementation and.or *this* implementation. A memory allocator is no different. Pretend the "addresses" returned were integers and the specification was written in terms of *integers*. You wouldn't throw an arbitrary input value at it and not *carefully* examine the result to see that it complies with EXACTLY what you would expect, given its contract. And, if your goal was to ensure that the function behaved well in the wide variety of cases that it might be subjected to once deployed, you would think very carefully about *which* conditions you put it in and how you exercised them. If you developed a general purpose (4 function) calculator, would you use 1+1, 8-5, 3*4, etc. as your test cases? Or, would you think: "Hmmm... I wonder if it handles negative arguments properly? And negative *results*? And, what happens if I give it something too big -- 99999999+1? Or, something 'undefined' -- 345/0?" "Settling" for what the linker gives you as the location for the heap (as well as its *size*!) means you will *never* test the code with any degree of confidence GIVEN THAT IT WILL BE DEPLOYED IN ENVIRONMENTS OTHER THAN YOURS! How do you test sqrt? Don't *you* pick the values that are of interest to you in proving correct operation of the function? Don't *you* verify that the results are "as expected"? Granted, for an invertible function you could potentially do a monte carlo simulation having the test suite check the results (i.e., if result*result =~ argument, then pass). How would you apply that "random" approach to testing a non-invertible function? Or, one who's inverse function is of a complexity greater than or equal to the original function (e.g., a secure hash)? > harness. I think this may have been what you were saying elsewhere. If > your tests become bonded to single implementation, you are stuck with > it. If your tests don't assume specific values, you are free to change If your tests don't assume specific values, then you can't guarantee where in the function's *domain* you are testing. > the internals of the function as long as you don't break its published > behaviour. Obviously if your internal implementation is specified you > are stuck. The internal implementation need not be "fixed". You are still free to implement the function however you want -- as long as the external interface and the guarantees that it affords the developer are ALWAYS met. > Memory allocators are definitely one of those cases where one size does > not fit all, just look at the range of malloc libraries available for a > typical non-embedded environment. They would all pass the same test > suite assuming the tests didn't make assumptions about the implementation. No. It would be easier for *your* "implementation agnostic" approach to test *all* of those allocators with a given test suite. Because you don't *know/care* how they are making their choices! "Did I get a result? OK. Does it overlap any other results I have had? No. Does the chunk returned fit entirely in the *stated* (by the linker!) area of the heap? Yes. Lather, rinse, repeat." >>> I thought you were test a general purpose allocator. >>> >>> If your requirements are that specific, what's wrong with >>> >>> ASSERT(result == heapBase+0x32440)? >> >> What happens if heapBase is effectively (char *) -32400? >> What happens if the processor only has a 16b address space? >> What happens if that +32440 was a consequence of pointer >> alignment requirements on THIS PLATFORM? >> What happens if there isn't physical memory present at >> that location? > > You break 0x32440 down into platform independent variables. And how is that any different from platform *dependent* variables? You still need to "tune" the values to fit the *particular* (test) deployment. And, you have no guarantee that you are poking around all the right "dark corners" for the routine -- since you are not in control of the conditions that your function is being subjected to! >> If I know where (on this particular platform) the heap is located >> and how large it is and alignment constraints, etc. AND have just >> initialized the heap... THEN: >> - I know what the internal free list looks like, "conceptually" >> (I might not know specific bit patterns but I know what the >> free list *reflects* -- a heap that is completely FULL! >> - given that free list, I know how any particular allocation >> request WILL be handled. >> - given how that request is handled, I now know what the NEW >> state of the free list will be. >> - lather, rinse, repeat > > Until someone introduces a critical optimisation that changes the layout... Until someone changes what "sqrt" means! I *only* -- though THOROUGHLY -- test *published*, contractual guarantees that the function *must* honor. What goes on under the hood is never examined, directly. You can implement sqrt with Newton-Rhapson, large lookup tables, CORDIC, etc. Your test suite DOESN'T CARE! As long as sqrt(foo) truly produces the square root of foo! I can change the internals of the memory allocator any way I choose AS LONG AS the results returned for a given set of operating conditions and input variables REMAIN UNCHANGED. E.g., the allocator makes no claims about the *content* of the blocks of memory allocated. I could add some code to zero them out, fill them with pseudo-random numbers -- or just leave their previous contents "as is". The test suite can't *test* any of those conditions because none are guaranteed in the contract. If I find it more efficient to leave assorted crap *in* the chunks, the test suite can't complain! (If K&R's malloc wants to do a "first fit" selection strategy, there's nothing preventing it! Nor anything preventing it from changing that, in a later edition, to a "last fit". The test suite for *their* malloc would have to accept both sets of results as equally valid.) > I still think you are testing at too high a level, test the functions > that manipulate your internal independently. There *is* nothing else. the allocator and the deallocator are the *only* things that massage the internal state of the heap!
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-14 07:25 +1300 |
| Message-ID | <9s9hpbF8igU1@mid.individual.net> |
| In reply to | #18682 |
On 03/14/12 06:19 AM, Don Y wrote: > Hi Ian, > >>>> Your typical memory allocator is a little more complex and less >>>> deterministic than strchr(). >>> >>> But it still produces *a* result. It is a deterministic >>> algorithm (even if the specification -- like malloc -- doesn't >>> make that determinism explicit). With a given set of operating >>> conditions and inputs, you **KNOW** what the result will be. >>> TEST FOR THAT RESULT! >> >> It may produce a result, but more often than not, the exact value is of >> little on no consequence. > > Is the exact value of sqrt()'s result of no consequence? Now I think you are being deliberately obtuse. You were talking about malloc, not sqrt. >> If you start to test for specific values based >> on knowledge of the internals, you end up with a very fragile test > > No! I am *not* looking at test internals. I am looking at > the SPECIFIED, CONTRACTUAL BEHAVIOR of the function. Then I guess the root cause of this debate is that your function is over specified. > Are > you "looking at internals" when you test the return value > of sqrt(5)? The sqrt function returns a positive value > for all non negative arguments such that the value, when > multiplied by itself, yields the original argument. THAT > is what you test for! I'm not aware a of a malloc specification that states the value returned for a given request. It sounds like yours does, which is unusual. > A *good* test picks values that are likely to cause problems > in an implementation and.or *this* implementation. > > A memory allocator is no different. Pretend the "addresses" > returned were integers and the specification was written in > terms of *integers*. You wouldn't throw an arbitrary input > value at it and not *carefully* examine the result to see that > it complies with EXACTLY what you would expect, given its > contract. But is isn't usually specified that way. >> I still think you are testing at too high a level, test the functions >> that manipulate your internal independently. > > There *is* nothing else. the allocator and the deallocator > are the *only* things that massage the internal state of the > heap! The you should extract some of the internal functionality and test it. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-14 02:00 -0700 |
| Message-ID | <jjpmn4$9j0$1@speranza.aioe.org> |
| In reply to | #18688 |
Hi Ian, On 3/13/2012 11:25 AM, Ian Collins wrote: > On 03/14/12 06:19 AM, Don Y wrote: >>>>> Your typical memory allocator is a little more complex and less >>>>> deterministic than strchr(). >>>> >>>> But it still produces *a* result. It is a deterministic >>>> algorithm (even if the specification -- like malloc -- doesn't >>>> make that determinism explicit). With a given set of operating >>>> conditions and inputs, you **KNOW** what the result will be. >>>> TEST FOR THAT RESULT! >>> >>> It may produce a result, but more often than not, the exact value is of >>> little on no consequence. >> >> Is the exact value of sqrt()'s result of no consequence? > > Now I think you are being deliberately obtuse. You were talking about > malloc, not sqrt. My point was, "What makes malloc's result 'of little or no consequence' while sqrt's *is* consequential?" >>> If you start to test for specific values based >>> on knowledge of the internals, you end up with a very fragile test >> >> No! I am *not* looking at test internals. I am looking at >> the SPECIFIED, CONTRACTUAL BEHAVIOR of the function. > > Then I guess the root cause of this debate is that your function is over > specified. No. It specifies exactly as much as is needed to allow the developer to direct and predict its operation. I can wrap it in a macro and turn it into any number of different "malloc(3)" implementations -- by *removing* that flexibility from the developer. >> Are >> you "looking at internals" when you test the return value >> of sqrt(5)? The sqrt function returns a positive value >> for all non negative arguments such that the value, when >> multiplied by itself, yields the original argument. THAT >> is what you test for! > > I'm not aware a of a malloc specification that states the value returned > for a given request. It sounds like yours does, which is unusual. Yes. It's not "malloc" but, rather, a "memory allocator". Unless you can control how the function does its work, you can't control the resources (time and space) that it uses. >> A *good* test picks values that are likely to cause problems >> in an implementation and.or *this* implementation. >> >> A memory allocator is no different. Pretend the "addresses" >> returned were integers and the specification was written in >> terms of *integers*. You wouldn't throw an arbitrary input >> value at it and not *carefully* examine the result to see that >> it complies with EXACTLY what you would expect, given its >> contract. > > But is isn't usually specified that way. > >>> I still think you are testing at too high a level, test the functions >>> that manipulate your internal independently. >> >> There *is* nothing else. the allocator and the deallocator >> are the *only* things that massage the internal state of the >> heap! > > The you should extract some of the internal functionality and test it. I can essentially do this by examining the results of successive invocations designed to expose aspects of that state. (see other post to Malcolm, this date)
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-14 22:18 +1300 |
| Message-ID | <9sb634F8igU7@mid.individual.net> |
| In reply to | #18757 |
On 03/14/12 10:00 PM, Don Y wrote: > Hi Ian, > > On 3/13/2012 11:25 AM, Ian Collins wrote: >> On 03/14/12 06:19 AM, Don Y wrote: >>>>>> Your typical memory allocator is a little more complex and less >>>>>> deterministic than strchr(). >>>>> >>>>> But it still produces *a* result. It is a deterministic >>>>> algorithm (even if the specification -- like malloc -- doesn't >>>>> make that determinism explicit). With a given set of operating >>>>> conditions and inputs, you **KNOW** what the result will be. >>>>> TEST FOR THAT RESULT! >>>> >>>> It may produce a result, but more often than not, the exact value is of >>>> little on no consequence. >>> >>> Is the exact value of sqrt()'s result of no consequence? >> >> Now I think you are being deliberately obtuse. You were talking about >> malloc, not sqrt. > > My point was, "What makes malloc's result 'of little or no > consequence' while sqrt's *is* consequential?" Because of the way the function is specified. You pass 4 to sqrt, it must return 2. You ask malloc for 4 bytes, it can give return a pointer to any correctly aligned bit of memory. >>>> If you start to test for specific values based >>>> on knowledge of the internals, you end up with a very fragile test >>> >>> No! I am *not* looking at test internals. I am looking at >>> the SPECIFIED, CONTRACTUAL BEHAVIOR of the function. >> >> Then I guess the root cause of this debate is that your function is over >> specified. > > No. It specifies exactly as much as is needed to allow the > developer to direct and predict its operation. I can > wrap it in a macro and turn it into any number of different > "malloc(3)" implementations -- by *removing* that flexibility > from the developer. Isn't the point of the specification of a function like malloc to give the implementer the freedom to design the internals to meet a specific need? Any of the malloc/free implementations I have written over the years could be swapped out for another (with the except of one that used 386 page registers). They would work to specification, but not give the best performance in each other's applications. >>>> I still think you are testing at too high a level, test the functions >>>> that manipulate your internal independently. >>> >>> There *is* nothing else. the allocator and the deallocator >>> are the *only* things that massage the internal state of the >>> heap! >> >> The you should extract some of the internal functionality and test it. > > I can essentially do this by examining the results of > successive invocations designed to expose aspects of that > state. (see other post to Malcolm, this date) But you can't directly do it. You could easily extract and test the functions the manipulate the free list for example. I guess the difference in approach is I would have written and tested those lower level functions before combining them. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-14 11:32 -0700 |
| Message-ID | <jjqo7o$2na$1@speranza.aioe.org> |
| In reply to | #18760 |
Hi Ian, On 3/14/2012 2:18 AM, Ian Collins wrote: > On 03/14/12 10:00 PM, Don Y wrote: >> On 3/13/2012 11:25 AM, Ian Collins wrote: >>> On 03/14/12 06:19 AM, Don Y wrote: >>>>>>> Your typical memory allocator is a little more complex and less >>>>>>> deterministic than strchr(). >>>>>> >>>>>> But it still produces *a* result. It is a deterministic >>>>>> algorithm (even if the specification -- like malloc -- doesn't >>>>>> make that determinism explicit). With a given set of operating >>>>>> conditions and inputs, you **KNOW** what the result will be. >>>>>> TEST FOR THAT RESULT! >>>>> >>>>> It may produce a result, but more often than not, the exact value >>>>> is of >>>>> little on no consequence. >>>> >>>> Is the exact value of sqrt()'s result of no consequence? >>> >>> Now I think you are being deliberately obtuse. You were talking about >>> malloc, not sqrt. >> >> My point was, "What makes malloc's result 'of little or no >> consequence' while sqrt's *is* consequential?" > > Because of the way the function is specified. You pass 4 to sqrt, it > must return 2. You ask malloc for 4 bytes, it can give return a pointer > to any correctly aligned bit of memory. That's malloc(3)'s contract; not allocateMemory()'s! :> >>>>> If you start to test for specific values based >>>>> on knowledge of the internals, you end up with a very fragile test >>>> >>>> No! I am *not* looking at test internals. I am looking at >>>> the SPECIFIED, CONTRACTUAL BEHAVIOR of the function. >>> >>> Then I guess the root cause of this debate is that your function is over >>> specified. >> >> No. It specifies exactly as much as is needed to allow the >> developer to direct and predict its operation. I can >> wrap it in a macro and turn it into any number of different >> "malloc(3)" implementations -- by *removing* that flexibility >> from the developer. > > Isn't the point of the specification of a function like malloc to give > the implementer the freedom to design the internals to meet a specific The specification just ensures that implementor and "user" agree on what functionality will be provided and the semantics for invocation, etc. Within those constraints, the implementor is free to do as he chooses. And, to *change* that "on a whim" (to meet some arbitrary criteria that <someone> deems appropriate). You can't get deterministic (predictable -- esp temporally) behavior from something that is free to produce resuts however it chooses! E.g., (some implementation of) malloc(3) could satisfy all requests with (increments of) 4KB blocks of memory and still conform to the interface specification. If your heap is only 8K, you might not be real happy with that! :> The application knows more about how it will be *using* memory than the memory management system does. And, if it knows it can influence *how* memory is allocated, then it can *really* think about how it wants to use memory as it realizes that this knowledge can improve performance. E.g., if I need 100 bytes of memory and then want 200 more (for some other reason), it would be smarter for that second allocation request to be satisfied "close to" (in terms of actual memory addresses) that first one -- if I am operating in a VM environment! Otherwise, the first allocation requires a physical memory page to be faulted in to "back" those 100 bytes (even though the rest of the page is "unused") while another, *different* page might be faulted in to satisfy that second allocation request. If the application can influence *how* the free space is chosen to satisfy a request, it can direct the allocator in that way. On bigger systems, you would embed this knowledge of the underlying VM in the allocator and not the application -- for the exact opposite reason (i.e., to take advantage of knowledge of the underlying VM that the application might not have or want to be concerned with). But, on bigger systems you often have more resources to play with and are less concerned about how "well" the application fits with those resources. > need? Any of the malloc/free implementations I have written over the > years could be swapped out for another (with the except of one that used > 386 page registers). They would work to specification, but not give the > best performance in each other's applications. --^^^^^^^^^^^^^^^^^ Exactly! When you are trimming the hardware down to the barest minimum necessary for a task, you want the software to be "frugal" in how it handles *its* responsibilities. [You aren't designing a general purpose solution that will handle an UNCONSTRAINED range of applications but, rather, a solution for a *particular* application.] >>>>> I still think you are testing at too high a level, test the functions >>>>> that manipulate your internal independently. >>>> >>>> There *is* nothing else. the allocator and the deallocator >>>> are the *only* things that massage the internal state of the >>>> heap! >>> >>> The you should extract some of the internal functionality and test it. >> >> I can essentially do this by examining the results of >> successive invocations designed to expose aspects of that >> state. (see other post to Malcolm, this date) > > But you can't directly do it. The contents of the free list aren't specified by the function's specification. The only thing that is specified is *how* it goes about providing a pointer to a block of memory per the parameters passed. Testing anything other than that (peeking under the hood) ties the test implementation to the function implementation. Do you peek inside sqrt() while testing it to verify that the individual CORDIC iterations are proceeding in the right order? Or, do you wait to examine the result? And, all you really care about *is* the result. If you craft your test cases to put the function in a situation where you effectively EXPOSE an internal decision E.g., I know there are two fragments in the free list at this point -- based on the results I have verified from my previous allocation requests. And, I know *where* those fragments must be -- again, because I know what memory has already been granted to me and where *it* is located in the address space. So, I can now issue a request that could be handled by *either* of those fragments (i.e., both are big enough) but specify a selection criteria that SHOULD cause the allocator to pick fragment A instead of fragment B. Let's see if it does... I can stack these test cases back to back forcing the allocator to pick one, then the other, based solely on the parameters that I pass to it (since the function is just a state machine and must respond to its inputs -- which include its current "state" -- in a predictable manner) > You could easily extract and test the > functions the manipulate the free list for example. I guess the > difference in approach is I would have written and tested those lower > level functions before combining them. Each of the "criteria" is essentially a (*ftn)() -- with a suitable parameter list. This makes it easy for me to add other options/criteria without having to redesign the entire algorithm. I.e., it imposes a framework *inside* the function. So, for example, a (*selector)() takes a pointer to a heap_t (which contains information about the free list for that heap as well as constraints on that heap) and a size_t (for the desired chunk) as well as caller-specified alignment (in addition tot he alignment constraints imposed by the platform). The (*selector)() is responsible for examining the free list for the heap and picking a suitable fragment for the request based on the strategy that it embodies. A (*trimmer)() takes a fragment_t and a size_t and returns a fragment_t that has been "trimmed" to the correct size (noting alignment constraints in the process) along with a fragment_t that is "scrap" (returned to the free list). Etc. Below this lies another level of functions that actually "do the work". This allows code to be shared between "selectors", etc. (e.g., a selector might examine the free list differently based on knowledge of how the free list is *currently* ordered) The problem is that most of the implementation relies on storing data *in* the free *fragments* to eliminate the need for supplemental data structures. E.g., the fragments are maintained in a doubly linked list with that "overhead" residing *in* the fragments themselves. So, the data for the fragment at 0x12345678 is stored *in* the fragment at 0x12345678. The allocator must dereference 0x12345678 in order to find the size of that fragment, the next fragment preceding/following it in the free list, etc. As such, testing that the code properly handles the case of a 17 byte fragment existing AT 0xFFFFFFF0 (which clearly can't be the case since the 17th byte would be past the end of memory!) requires *accessing* the data at 0xFFFFFFF0 (i.e., I don't even *know* that the "size" stored in that fragment is INCORRECT until I can do that!) By contrast, a 17 byte fragment at 0xFFFFFF00 wouldn't be an error (at least not for *that* reason!)
[toc] | [prev] | [next] | [standalone]
| From | nick_keighley_nospam@hotmail.com |
|---|---|
| Date | 2012-03-15 05:58 -0700 |
| Message-ID | <14651976.3284.1331816295797.JavaMail.geo-discussion-forums@vbhv6> |
| In reply to | #18760 |
On Wednesday, March 14, 2012 9:18:28 AM UTC, Ian Collins wrote: > On 03/14/12 10:00 PM, Don Y wrote: <snip> > > I can essentially do this by examining the results of > > successive invocations designed to expose aspects of that > > state. (see other post to Malcolm, this date) > > But you can't directly do it. You could easily extract and test the > functions the manipulate the free list for example. I guess the > difference in approach is I would have written and tested those lower > level functions before combining them. me too. High level testing has failed me too often. And debugging is /much/ harder.
[toc] | [prev] | [next] | [standalone]
| From | nick_keighley_nospam@hotmail.com |
|---|---|
| Date | 2012-03-15 05:55 -0700 |
| Message-ID | <20559117.329.1331816158025.JavaMail.geo-discussion-forums@vbhy1> |
| In reply to | #18757 |
On Wednesday, March 14, 2012 9:00:18 AM UTC, Don Y wrote: > Hi Ian, > On 3/13/2012 11:25 AM, Ian Collins wrote: > > On 03/14/12 06:19 AM, Don Y wrote: <snip> [testing memory allocators] > >>> I still think you are testing at too high a level, test the functions > >>> that manipulate your internal independently. > >> > >> There *is* nothing else. the allocator and the deallocator > >> are the *only* things that massage the internal state of the > >> heap! > > > > The you should extract some of the internal functionality and test it. > > I can essentially do this by examining the results of > successive invocations designed to expose aspects of that > state. (see other post to Malcolm, this date) seems like doing things the hard way. *And* it's error prone. You need white-box knowledge to test your function thoughourly- so why not make it explicit in your test harness? Only-testing-the-public-interface can be taken to ridiculous extremes. Do they deduce the internal behaviour of air-traffic control systems by flying planes at them at different angles? To use the over-stretched Civil Engineering analogy. People who build bridges build them out of known good components which they assemble into known good sub-systems that they in turn assemble into complete bridges or whatever. Somwething complex like a memory allocator needs to be broken into chunks and/or expose much of its internals to facilitate testing.
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-15 11:32 -0700 |
| Message-ID | <jjtcje$t89$1@speranza.aioe.org> |
| In reply to | #18800 |
Hi Nick, On 3/15/2012 5:55 AM, nick_keighley_nospam@hotmail.com wrote: > On Wednesday, March 14, 2012 9:00:18 AM UTC, Don Y wrote: >>>>> I still think you are testing at too high a level, test the functions >>>>> that manipulate your internal independently. >>>> >>>> There *is* nothing else. the allocator and the deallocator >>>> are the *only* things that massage the internal state of the >>>> heap! >>> >>> The you should extract some of the internal functionality and test it. >> >> I can essentially do this by examining the results of >> successive invocations designed to expose aspects of that >> state. (see other post to Malcolm, this date) > > seems like doing things the hard way. *And* it's error prone. You > need white-box knowledge to test your function thoughourly- so why > not make it explicit in your test harness? Doing so means you have now determined the *implementation* as well as the functionality. If you want to split out "sub-functions", do so. Then, formally specify how they must work. And, formally specify a test suite for them. Thereafter, the implementation of the allocator must preserve all of these interfaces. The whole point of regression testing is to formalize the test cases and ensure changes to a function preserve its interface semantics and functionality. I write a CORDIC sqrt. I peek inside and notice that iteration X for an input of FOO yields -- and *should* yield -- an approximation having the value BAZ. You rewrite the sqrt using Newton-Rhapson. Suddenly your test fails because it converges on the result differently. Or, maybe my peek-inside test looks at some parameter of the CORDIC implementation that simply doesn't EXIST in the Newton-Rhapson version. You can *test* your code by single stepping through its execution or "whatever". But *formalizing* that portion of the test process is folly. > Only-testing-the-public-interface can be taken to ridiculous > extremes. Do they deduce the internal behaviour of air-traffic > control systems by flying planes at them at different angles? An air traffic control system will have *numerous* layers of FORMAL SPECIFICATION below "system test/specification". All of those lower "interfaces" are tested. But, they are also points of inflexibility. Any change to any of them can result in changes to the entire *system* above and below it in the abstraction hierarchy. "Let's make malloc(3) return a pointer to a struct that contains a pointer to the allocated memory and the size of that memory". Suddenly, everything that uses malloc changes. (let's make sqrt rely on successive iterations of a CORDIC algorithm; you are free to change the implementation of the CORDIC algorithm -- but, you have to ensure that the results it produces agree with those that are being tested for) If you FORMALIZE test suites then you formalize interfaces. If that's what you want or need, then do so FORMALLY. Make sure there is a formal document that contractually specifies how the interface is expected to function so that: - implementors know how to implement the function described - consumers know how to *use* that function - validation suites know how to exercise that function If, OTOH, you don't want to go to all this trouble and tie your future hands, implement whatever ad hoc testing YOU want and keep it on a scrap of paper in your desk drawer since it is not a formal part of the specification for the function/module you are testing! > To use the over-stretched Civil Engineering analogy. People who > build bridges build them out of known good components which they > assemble into known good sub-systems that they in turn assemble > into complete bridges or whatever. And each of those *components* is formally specified, tested and "vouched for" (by the manufacturer). So a *lawyer* and set of "expert witnesses" can testify that the reason the bridge failed was because ACME Asphalt sold defective road coating to the builder which didn't meet the specifications that the supplier FORMALLY AND LEGALLY AGREED TO in his CONTRACT withe the builder. You can't go and complain that ACME used *pink* asphalt (while you EXPECTED black) -- unless it fails to meet some specified criteria in that contract. Or, that ACME heated the raw material using a wood fire instead of a gas oven in preparing the road covering (unless the specification says "shall be heated in a natural gas fired oven") ACME has liberties as to how it approaches each specification to which it has *contractually* agreed to be bound. > Somwething complex like a memory allocator needs to be broken > into chunks and/or expose much of its internals to facilitate testing. As I said, *you* can look at individual BITS in the CPU, memory, etc. while *you* are testing it. But, the function formally only has ONE interface that it must contractually satisfy.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-16 18:14 +1300 |
| Message-ID | <9sg0iaFgvgU1@mid.individual.net> |
| In reply to | #18806 |
On 03/16/12 07:32 AM, Don Y wrote: > Hi Nick, > > On 3/15/2012 5:55 AM, nick_keighley_nospam@hotmail.com wrote: >> On Wednesday, March 14, 2012 9:00:18 AM UTC, Don Y wrote: > >>>>>> I still think you are testing at too high a level, test the functions >>>>>> that manipulate your internal independently. >>>>> >>>>> There *is* nothing else. the allocator and the deallocator >>>>> are the *only* things that massage the internal state of the >>>>> heap! >>>> >>>> The you should extract some of the internal functionality and test it. >>> >>> I can essentially do this by examining the results of >>> successive invocations designed to expose aspects of that >>> state. (see other post to Malcolm, this date) >> >> seems like doing things the hard way. *And* it's error prone. You >> need white-box knowledge to test your function thoughourly- so why >> not make it explicit in your test harness? > > Doing so means you have now determined the *implementation* > as well as the functionality. > > If you want to split out "sub-functions", do so. Then, > formally specify how they must work. And, formally > specify a test suite for them. Thereafter, the implementation > of the allocator must preserve all of these interfaces. No, you do not. The interface of the allocator is formally specified, not its internals. > The whole point of regression testing is to formalize the > test cases and ensure changes to a function preserve its > interface semantics and functionality. Quite. If you make a change to the internals that breaks the published interface, the published interface test will fail. You could have several stets of internals for different environments and be free to substitute one for another without breaking the published interface. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-20 01:43 -0700 |
| Message-ID | <jk9fuo$puo$1@speranza.aioe.org> |
| In reply to | #18825 |
Hi Ian, On 3/15/2012 10:14 PM, Ian Collins wrote: >>>>>>> I still think you are testing at too high a level, test the >>>>>>> functions >>>>>>> that manipulate your internal independently. >>>>>> >>>>>> There *is* nothing else. the allocator and the deallocator >>>>>> are the *only* things that massage the internal state of the >>>>>> heap! >>>>> >>>>> The you should extract some of the internal functionality and test it. >>>> >>>> I can essentially do this by examining the results of >>>> successive invocations designed to expose aspects of that >>>> state. (see other post to Malcolm, this date) >>> >>> seems like doing things the hard way. *And* it's error prone. You >>> need white-box knowledge to test your function thoughourly- so why >>> not make it explicit in your test harness? >> >> Doing so means you have now determined the *implementation* >> as well as the functionality. >> >> If you want to split out "sub-functions", do so. Then, >> formally specify how they must work. And, formally >> specify a test suite for them. Thereafter, the implementation >> of the allocator must preserve all of these interfaces. > > No, you do not. The interface of the allocator is formally specified, > not its internals. Great! What is your internal test SUPPOSED TO DO when given ___________? How do you *know* what it is supposed to do in that case? What happens when your boss wants to throw some manpower at your task to improve your chances of meeting a deadline and he decides splitting of the development of the test suite for <whatever> should be a nice, easily compartmentalized task. The guy who is writing the test suite for you wants to know what he should *expect* your code to do given ___________. Once you *have* specified this *internal* interface, any changes you make to *that* interface require the rewriting and revalidation of the layers *above* and *below*. I.e., the parts of your <top_level_function> that rely on that <lower_level_implementation> now have to change. And, that <lower_level_implementation> also has to change to agree with the new interface definition. >> The whole point of regression testing is to formalize the >> test cases and ensure changes to a function preserve its >> interface semantics and functionality. > > Quite. If you make a change to the internals that breaks the published > interface, the published interface test will fail. You could have > several stets of internals for different environments and be free to > substitute one for another without breaking the published interface. While you are away at lunch, I replace the code for function() with a new implementation. It adheres to the PUBLISHED interface for function(). But, fails ALL of your "internal tests" because it is implemented in an entirely different manner (that is NOT mandated by the published specification). I haven't done anything wrong. But, my code fails your tests -- because your tests are looking at undocumented aspects of *an* implementation. I rewrite sqrt(): the new RUN-TIME version causes a packet to be sent across the internet to an accountant sitting in a smoke-filled office. The value for which you are seeking the sqrt appears on his display. He takes out his pencil and a clean ream of paper and gets to work on the problem. When he is done, some time later, he types the answer in on his keyboard and a packet is returned to the WAITING application. The sqrt() code then converts this ASCII decimal string into a suitable "double" and returns the value to the caller. There is *nothing* about this implementation that violates the letter of the sqrt() interface specification. Granted, it's dog slow and only works on machines with internet connectivity. But, it still *works*. It passes the regression tests for sqrt(). But, *doesn't* pass any of your undocumented internal tests -- because you probably wouldn't have conceived of such an approach. [If this is too far-fetched, it shouldn't be hard for you to imagine two or three *radically* incompatible means for computing a sqrt that would satisfy the sqrt()'s published interface yet share no "internals" in common with each other. So, any FORMALIZATION of any internal interface (as required to document the expected behavior for a test suite that exercises that internal interface) will dictate which of those implementations are "acceptable" to you.]
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-20 21:59 +1300 |
| Message-ID | <9sqv87Fc6rU2@mid.individual.net> |
| In reply to | #18894 |
On 03/20/12 09:43 PM, Don Y wrote: > Hi Ian, > > On 3/15/2012 10:14 PM, Ian Collins wrote: > >>>>>>>> I still think you are testing at too high a level, test the >>>>>>>> functions >>>>>>>> that manipulate your internal independently. >>>>>>> >>>>>>> There *is* nothing else. the allocator and the deallocator >>>>>>> are the *only* things that massage the internal state of the >>>>>>> heap! >>>>>> >>>>>> The you should extract some of the internal functionality and test it. >>>>> >>>>> I can essentially do this by examining the results of >>>>> successive invocations designed to expose aspects of that >>>>> state. (see other post to Malcolm, this date) >>>> >>>> seems like doing things the hard way. *And* it's error prone. You >>>> need white-box knowledge to test your function thoughourly- so why >>>> not make it explicit in your test harness? >>> >>> Doing so means you have now determined the *implementation* >>> as well as the functionality. >>> >>> If you want to split out "sub-functions", do so. Then, >>> formally specify how they must work. And, formally >>> specify a test suite for them. Thereafter, the implementation >>> of the allocator must preserve all of these interfaces. >> >> No, you do not. The interface of the allocator is formally specified, >> not its internals. > > Great! What is your internal test SUPPOSED TO DO when > given ___________? How do you *know* what it is supposed to > do in that case? As I said a while back, most platforms have a number of interchangeable allocators optimised for various applications. Their internals may be completely different, but they still conform to the the standard allocator requirements. > What happens when your boss wants to > throw some manpower at your task to improve your chances of > meeting a deadline and he decides splitting of the development > of the test suite for<whatever> should be a nice, easily > compartmentalized task. The guy who is writing the test suite > for you wants to know what he should *expect* your code to do > given ___________. We don't work that way. In the TDD world, the bloke (or pair) writing the tests is the bloke (or pair) writing the code. > Once you *have* specified this *internal* interface, any > changes you make to *that* interface require the rewriting > and revalidation of the layers *above* and *below*. I.e., > the parts of your<top_level_function> that rely on that > <lower_level_implementation> now have to change. And, that > <lower_level_implementation> also has to change to agree > with the new interface definition. That argument could go round in circles for ever. >>> The whole point of regression testing is to formalize the >>> test cases and ensure changes to a function preserve its >>> interface semantics and functionality. >> >> Quite. If you make a change to the internals that breaks the published >> interface, the published interface test will fail. You could have >> several stets of internals for different environments and be free to >> substitute one for another without breaking the published interface. > > While you are away at lunch, I replace the code for function() > with a new implementation. It adheres to the PUBLISHED interface > for function(). But, fails ALL of your "internal tests" because > it is implemented in an entirely different manner (that is NOT > mandated by the published specification). It couldn't. You didn't change the internal code, you replaced it with some new code, presumably with its own tests. In other words, you produced another alternative implementation. > I haven't done anything wrong. But, my code fails your > tests -- because your tests are looking at undocumented > aspects of *an* implementation. Nope. > I rewrite sqrt(): the new RUN-TIME version causes a > packet to be sent across the internet to an accountant > sitting in a smoke-filled office. The value for which > you are seeking the sqrt appears on his display. He > takes out his pencil and a clean ream of paper and > gets to work on the problem. When he is done, some > time later, he types the answer in on his keyboard and > a packet is returned to the WAITING application. The > sqrt() code then converts this ASCII decimal string > into a suitable "double" and returns the value to the > caller. > > There is *nothing* about this implementation that > violates the letter of the sqrt() interface specification. > Granted, it's dog slow and only works on machines with > internet connectivity. But, it still *works*. It > passes the regression tests for sqrt(). > > But, *doesn't* pass any of your undocumented internal > tests -- because you probably wouldn't have conceived of > such an approach. While sightly exaggerated, that isn't an uncommon situation. For example an application may happily be working away processing data from a local store. At some point that data is moved to another system and is accessed through a web service. So the persistence layer gets replaced. The application still passes all its regression tests because they don't care how the application outputs 2 when 4 is input, They just care that it does. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | nick_keighley_nospam@hotmail.com |
|---|---|
| Date | 2012-03-16 03:05 -0700 |
| Message-ID | <16697131.758.1331892337093.JavaMail.geo-discussion-forums@ynbq18> |
| In reply to | #18806 |
On Thursday, March 15, 2012 6:32:16 PM UTC, Don Y wrote:
> On 3/15/2012 5:55 AM, nick_keighley_nospam@hotmail.com wrote:
> > On Wednesday, March 14, 2012 9:00:18 AM UTC, Don Y wrote:
> >>>>> I still think you are testing at too high a level, test the functions
> >>>>> that manipulate your internal independently.
> >>>>
> >>>> There *is* nothing else. the allocator and the deallocator
> >>>> are the *only* things that massage the internal state of the
> >>>> heap!
> >>>
> >>> The you should extract some of the internal functionality and test it.
> >>
> >> I can essentially do this by examining the results of
> >> successive invocations designed to expose aspects of that
> >> state. (see other post to Malcolm, this date)
> >
> > seems like doing things the hard way. *And* it's error prone. You
> > need white-box knowledge to test your function thoughourly- so why
> > not make it explicit in your test harness?
>
> Doing so means you have now determined the *implementation*
> as well as the functionality.
no. You've tested the implementation as well as the functionality.
> If you want to split out "sub-functions", do so. Then,
> formally specify how they must work. And, formally
> specify a test suite for them. Thereafter, the implementation
> of the allocator must preserve all of these interfaces.
no. A particular implementation has particualar internal tests.
Perhaps you provide a call internalDataValid() the high level test
need never know what the internal details of that are.
> The whole point of regression testing is to formalize the
> test cases and ensure changes to a function preserve its
> interface semantics and functionality.
that's your definition. To me regression tests are to test you
haven't broken something with your change. A purely functional
test might not check all the boundaries and special cases.
> I write a CORDIC sqrt. I peek inside and notice that iteration
> X for an input of FOO yields -- and *should* yield -- an
> approximation having the value BAZ.
>
> You rewrite the sqrt using Newton-Rhapson. Suddenly your test
> fails because it converges on the result differently.
so testing floating point is difficult.
> Or, maybe my peek-inside test looks at some parameter of
> the CORDIC implementation that simply doesn't EXIST in
> the Newton-Rhapson version.
>
> You can *test* your code by single stepping through its
> execution or "whatever". But *formalizing* that portion
> of the test process is folly.
I'm not sure sqrt() is a really good example. I never suggested
stepping-through-the-code was a sensible validation step.
> > Only-testing-the-public-interface can be taken to ridiculous
> > extremes. Do they deduce the internal behaviour of air-traffic
> > control systems by flying planes at them at different angles?
>
> An air traffic control system will have *numerous* layers
> of FORMAL SPECIFICATION below "system test/specification".
> All of those lower "interfaces" are tested. But, they
> are also points of inflexibility. Any change to any of them
> can result in changes to the entire *system* above and below
> it in the abstraction hierarchy.
>
> "Let's make malloc(3) return a pointer to a struct that contains
> a pointer to the allocated memory and the size of that memory".
>
> Suddenly, everything that uses malloc changes.
quite. You've changed the public interface.
> (let's make
> sqrt rely on successive iterations of a CORDIC algorithm;
> you are free to change the implementation of the CORDIC
> algorithm -- but, you have to ensure that the results it
> produces agree with those that are being tested for)
why?
> If you FORMALIZE test suites then you formalize interfaces.
why? Why can't you write internal tests? You can call them "formal" if you like. Ok.
Step 1 "run internalTest() verify that it returns true"
Step 2 "run first functional test..."
> If that's what you want or need, then do so FORMALLY. Make
> sure there is a formal document that contractually specifies
> how the interface is expected to function so that:
> - implementors know how to implement the function described
> - consumers know how to *use* that function
> - validation suites know how to exercise that function
by why does that preclude any other form of testing?
> If, OTOH, you don't want to go to all this trouble and tie
> your future hands, implement whatever ad hoc testing YOU
> want and keep it on a scrap of paper in your desk drawer
> since it is not a formal part of the specification for the
> function/module you are testing!
I find this very strange. Why can't I run internal tests that
verify correct internal behaviour? These test are not "ad hoc",
they are not kept in the bottom left hand drawer. They can be reviewed,
configuration controlled, and results can be recorded.
It vastly increases confidence in the product over "just run the SAT" .
I've *seen* systems taht passed their SAT and then exhibited field bugs
that good module testing would have detected. It also makes debugging
easier...
> > To use the over-stretched Civil Engineering analogy. People who
> > build bridges build them out of known good components which they
> > assemble into known good sub-systems that they in turn assemble
> > into complete bridges or whatever.
>
> And each of those *components* is formally specified, tested
> and "vouched for" (by the manufacturer).
yes, but not by the customer of the bridge. He probably writes in the
contract "shall be constructed in accordance with best industry
practice" or some such boiler plate. The contract will then specify
its load capacity and how many days a year it will close due to high
winds. etc. They don't actually care what grade of steel is used as
long as someone ensures that the right one was used.
> So a *lawyer* and
> set of "expert witnesses" can testify that the reason the
> bridge failed was because ACME Asphalt sold defective road
> coating to the builder which didn't meet the specifications
> that the supplier FORMALLY AND LEGALLY AGREED TO in his
> CONTRACT withe the builder.
>
> You can't go and complain that ACME used *pink* asphalt (while
> you EXPECTED black) -- unless it fails to meet some specified
> criteria in that contract. Or, that ACME heated the raw material
> using a wood fire instead of a gas oven in preparing the road
> covering (unless the specification says "shall be heated in
> a natural gas fired oven")
>
> ACME has liberties as to how it approaches each specification
> to which it has *contractually* agreed to be bound.
>
> > Somwething complex like a memory allocator needs to be broken
> > into chunks and/or expose much of its internals to facilitate testing.
>
> As I said, *you* can look at individual BITS in the CPU, memory,
> etc. while *you* are testing it. But, the function formally
> only has ONE interface that it must contractually satisfy.
we seem to have acheived stalemate by repetition. Though "sanity is not statistical" Iwill point out there seem to be two of us that don't agree with you.
Happy programming!
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-20 02:33 -0700 |
| Message-ID | <jk9isd$227$1@speranza.aioe.org> |
| In reply to | #18826 |
Hi Nick,
>>>>>>> I still think you are testing at too high a level, test the functions
>>>>>>> that manipulate your internal independently.
>>>>>>
>>>>>> There *is* nothing else. the allocator and the deallocator
>>>>>> are the *only* things that massage the internal state of the
>>>>>> heap!
>>>>>
>>>>> The you should extract some of the internal functionality and test it.
>>>>
>>>> I can essentially do this by examining the results of
>>>> successive invocations designed to expose aspects of that
>>>> state. (see other post to Malcolm, this date)
>>>
>>> seems like doing things the hard way. *And* it's error prone. You
>>> need white-box knowledge to test your function thoughourly- so why
>>> not make it explicit in your test harness?
>>
>> Doing so means you have now determined the *implementation*
>> as well as the functionality.
>
> no. You've tested the implementation as well as the functionality.
If you peek inside AN IMPLEMENTATION and test expecting
some internal aspect of the implementation to comply with
some expectations under <some_set> of conditions, then
you have defined a new interface.
You have to formalize that interface -- otherwise, you can't
KNOW what to expect in any given situation. You can't *know* what
constitutes "correct" results at that internal level.
>> If you want to split out "sub-functions", do so. Then,
>> formally specify how they must work. And, formally
>> specify a test suite for them. Thereafter, the implementation
>> of the allocator must preserve all of these interfaces.
>
> no. A particular implementation has particualar internal tests.
> Perhaps you provide a call internalDataValid() the high level test
> need never know what the internal details of that are.
How is internalDataValid() defined? You have now exposed
another interface. How do I know what that is supposed to
do? How does SOMEONE ELSE looking at the test suite
assure themselves that "internalDataValid()" is being
tested properly?
>> The whole point of regression testing is to formalize the
>> test cases and ensure changes to a function preserve its
>> interface semantics and functionality.
>
> that's your definition. To me regression tests are to test you
> haven't broken something with your change. A purely functional
> test might not check all the boundaries and special cases.
Then your functional test sucks!
What happens when your test suite reports:
test string is located at: 0xFFFFFFFC
the first 4 locations of the string are: 'A' 'B' 'C' 'D'
the FUT (strlen()) returns a result of: ______
Do you *know* what the strlen() that you probably use *often*
will do in this case? Will the above test suite SIGSEGV before
it reports any of this??
Or, is your test suite "lame":
Please type a string, followed by CRLF: ABCDEFG
According to strlen(), you typed 7 characters.
Please type a string, followed by CRLF:
Do you have any faith in how it handles strings with, for example,
32767 characters? 32769??
>> I write a CORDIC sqrt. I peek inside and notice that iteration
>> X for an input of FOO yields -- and *should* yield -- an
>> approximation having the value BAZ.
>>
>> You rewrite the sqrt using Newton-Rhapson. Suddenly your test
>> fails because it converges on the result differently.
>
> so testing floating point is difficult.
No. CORDIC converges on the result differently than a FP
N-R approximation.
Imagine I have an infinitely large table in which all of the values
of sqrt() have been precomputed so sqrt just does a "lookup"
operation. Obviously, testing it's internals would be very
different from testing one that performs a successive approximation.
>> Or, maybe my peek-inside test looks at some parameter of
>> the CORDIC implementation that simply doesn't EXIST in
>> the Newton-Rhapson version.
>>
>> You can *test* your code by single stepping through its
>> execution or "whatever". But *formalizing* that portion
>> of the test process is folly.
>
> I'm not sure sqrt() is a really good example. I never suggested
> stepping-through-the-code was a sensible validation step.
>
>>> Only-testing-the-public-interface can be taken to ridiculous
>>> extremes. Do they deduce the internal behaviour of air-traffic
>>> control systems by flying planes at them at different angles?
>>
>> An air traffic control system will have *numerous* layers
>> of FORMAL SPECIFICATION below "system test/specification".
>> All of those lower "interfaces" are tested. But, they
>> are also points of inflexibility. Any change to any of them
>> can result in changes to the entire *system* above and below
>> it in the abstraction hierarchy.
>>
>> "Let's make malloc(3) return a pointer to a struct that contains
>> a pointer to the allocated memory and the size of that memory".
>>
>> Suddenly, everything that uses malloc changes.
>
> quite. You've changed the public interface.
Exactly. Now, imagine changing some *internal* interface of
malloc that is not visible to the user. YOUR test suite examines
this internal interface. But, its changed. Suddenly, your
tests don't work -- even though the rest of the malloc
implementation has been "fixed" so that it still satisfies
IT'S public interface.
>> (let's make
>> sqrt rely on successive iterations of a CORDIC algorithm;
>> you are free to change the implementation of the CORDIC
>> algorithm -- but, you have to ensure that the results it
>> produces agree with those that are being tested for)
>
> why?
Because YOU want to test this internal interface. You've
documented it so that you can convince a validation
engineer that your test suite for that INTERNAL interface
functions properly. Even though I have just changed
the implementation of the function itself (while preserving
*its* public interface SO IT STILL PASSES *IT'S* TEST SUITE)
>> If you FORMALIZE test suites then you formalize interfaces.
>
> why? Why can't you write internal tests? You can call them "formal" if you like. Ok.
>
> Step 1 "run internalTest() verify that it returns true"
> Step 2 "run first functional test..."
What is "internalTest()" for strlen()? for malloc()? for sqrt()?
A function with *two* entry points??
>> If that's what you want or need, then do so FORMALLY. Make
>> sure there is a formal document that contractually specifies
>> how the interface is expected to function so that:
>> - implementors know how to implement the function described
>> - consumers know how to *use* that function
>> - validation suites know how to exercise that function
>
> by why does that preclude any other form of testing?
Testing is the process of ensuring an implementation meets
its published goals/criteria. Anything you want to test
has to be formally specified -- else how do we agree that
your test really *does* validate proper operation?
>> If, OTOH, you don't want to go to all this trouble and tie
>> your future hands, implement whatever ad hoc testing YOU
>> want and keep it on a scrap of paper in your desk drawer
>> since it is not a formal part of the specification for the
>> function/module you are testing!
>
> I find this very strange. Why can't I run internal tests that
> verify correct internal behaviour? These test are not "ad hoc",
> they are not kept in the bottom left hand drawer. They can be reviewed,
> configuration controlled, and results can be recorded.
Are you REQUIRING the function to pass those tests?
If YOU quit and I am assigned the job of finishing your
work, do *I* have to use the same implementation that
you have chosen? Does the code I implement have to pass
those *internal* tests that you settled on? How do I
know what they should yield? *Why* should they yield those
results? What makes your implementation better than mine?
If I pass a *thorough* set of tests for the published
formal interface, why should I also have to pass your
particular set of internal tests?
I saw an implementation of production software that determined
the size of a file by reading the file and *counting* the
individual bytes. Sure, the result was correct. But a foolish
implementation.
How would you test this function's internals -- look at the
count at random points in time and verify that they were
constantly increasing? Have the loop emit the current
value of the counter periodically (e.g., every 1000 bytes)?
What happens if I rewrite the function and just use fstat()
and return the st_size member of the result? Your test
(for a 4567 byte file) would expect to see:
1000
2000
3000
4000
4567
for example. *My* implementation would simply produce the
final "4567" result. It has *failed* your "internal test"
because the implementation didn't rely on an iterative
counter approach.
Yet, it *passes* the test for the function itself!
> It vastly increases confidence in the product over "just run the SAT" .
> I've *seen* systems taht passed their SAT and then exhibited field bugs
> that good module testing would have detected. It also makes debugging
> easier...
If you passed a formal test and failed in the field, then your
formal test sucks. You clearly aren't testing all of the
conditions that your code is *supposed* to be able to tolerate.
Debugging and testing DURING DEVELOPMENT are different issues.
That's the "desk drawer" comment I made. You can't *force*
someone else (i.e., The Organization) to embrace your
particular implementation without formally nailing down a
contract for that interface that you are exposing.
>>> To use the over-stretched Civil Engineering analogy. People who
>>> build bridges build them out of known good components which they
>>> assemble into known good sub-systems that they in turn assemble
>>> into complete bridges or whatever.
>>
>> And each of those *components* is formally specified, tested
>> and "vouched for" (by the manufacturer).
>
> yes, but not by the customer of the bridge. He probably writes in the
> contract "shall be constructed in accordance with best industry
> practice" or some such boiler plate. The contract will then specify
> its load capacity and how many days a year it will close due to high
> winds. etc. They don't actually care what grade of steel is used as
> long as someone ensures that the right one was used.
----------^^^^^^^^^^^^^^^^^^^^^^^^^AAAAAAAAA^^^^^^^^^^
A contract, *somewhere* specifies what that "right one" is
and who that "someone" will be. When the bridge fails,
you can bet these items will be readily identifiable (as
the lawyers sort out who to go after for the losses).
You can create whatever sorts of contracts you (and your
organization) want. You can hide whatever you want, too.
But, everything that you expose *for* testing ties down
another corner of HOW you implement something -- as well
as how you can reimplement it in the future.
E.g., the is___() character functions are often implemented
as table lookups. The argument to the function is used
to access a const table whose contents represent the
"classifications" for the "character" corresponding to the
argument.
So, table['c'] encodes information that tells me that 'c'
is alphabetic, NOT numeric, NOT whitespace, NOT punctuation,
graphic, NOT a control character, etc.
*BUT*, table[] and its contents are not formally exposed
in the specifications for any of these functions! E.g.,
I can reimplement isdigit() to NOT use that table[] but,
instead, examine the argument directly, algebraically.
OTOH, if you expose table[] and try to test it as an
"internal test", you now have to formally define it
*and* mandate its role in the is___() functions.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-24 11:49 +1300 |
| Message-ID | <9t4cvuF3fiU3@mid.individual.net> |
| In reply to | #18898 |
On 03/20/12 10:33 PM, Don Y wrote: > Hi Nick, > >>>>>>>> I still think you are testing at too high a level, test the functions >>>>>>>> that manipulate your internal independently. >>>>>>> >>>>>>> There *is* nothing else. the allocator and the deallocator >>>>>>> are the *only* things that massage the internal state of the >>>>>>> heap! >>>>>> >>>>>> The you should extract some of the internal functionality and test it. >>>>> >>>>> I can essentially do this by examining the results of >>>>> successive invocations designed to expose aspects of that >>>>> state. (see other post to Malcolm, this date) >>>> >>>> seems like doing things the hard way. *And* it's error prone. You >>>> need white-box knowledge to test your function thoughourly- so why >>>> not make it explicit in your test harness? >>> >>> Doing so means you have now determined the *implementation* >>> as well as the functionality. >> >> no. You've tested the implementation as well as the functionality. > > If you peek inside AN IMPLEMENTATION and test expecting > some internal aspect of the implementation to comply with > some expectations under<some_set> of conditions, then > you have defined a new interface. > > You have to formalize that interface -- otherwise, you can't > KNOW what to expect in any given situation. You can't *know* what > constitutes "correct" results at that internal level. The tests formalise the interface. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
Back to top | Article view | comp.lang.c
csiph-web