«

On 2012-03-10, Ian Collins <ian-> wrote:
> I don't think so, assuming the behaviour of malloc is well defined. All
> strdup is doing is something along the lines of:
>
> char* pNew = malloc( strlen(in) );

s/strlen(in)/strlen(in)+1/ (one extra byte for the null terminator)

> if( pNew )
> strcpy( pNew, p );
>
> return pNew;

Ian Collins <ian-> writes:

> On 03/11/12 01:00 AM, Ben Bacarisse wrote:
>> Ian Collins<ian-> writes:
>> <snip>
>>> I don't see how a function like malloc is any different (form a unit
>>> testing perspective) than any other.
>>
>> To take a simple well-know case (so I don't have to find a way to write
>> the specification!) what would unit tests for strdup look like? In
>> particular, it would be a bug if strdup returned a pointer to a region
>> of memory that overlapped with one returned by any other allocating
>> function or, indeed, by strdup itself. Now you may rule out testing for
>> the former because this is, after all a *unit* test, but not,
>> presumably, the latter.
>
> Well I guess you could rule out both by asserting strdup calls malloc.

That would be to miss the point! Assume that strdup does not use
malloc -- this is an environment where dynamic allocation is not
permitted but we want to be able to copy some limited number of
strings.

>> I've been "out of the loop" as far as testing goes for some time so I
>> don't know how modern unit test systems deal with cases like this. No
>> doubt they have sophisticated memory region checking tools, but surely
>> strdup unit tests will look far more complex than those for, say,
>> strcpy?
>
> I don't think so, assuming the behaviour of malloc is well defined.
> All strdup is doing is something along the lines of:
>
> char* pNew = malloc( strlen(in) );
>
> if( pNew )
> strcpy( pNew, p );
>
> return pNew;

See above.

--
Ben.

On 03/11/12 11:40 AM, Ben Bacarisse wrote:
> Ian Collins<ian-> writes:
>
>> On 03/11/12 01:00 AM, Ben Bacarisse wrote:
>>> Ian Collins<ian-> writes:
>>> <snip>
>>>> I don't see how a function like malloc is any different (form a unit
>>>> testing perspective) than any other.
>>>
>>> To take a simple well-know case (so I don't have to find a way to write
>>> the specification!) what would unit tests for strdup look like? In
>>> particular, it would be a bug if strdup returned a pointer to a region
>>> of memory that overlapped with one returned by any other allocating
>>> function or, indeed, by strdup itself. Now you may rule out testing for
>>> the former because this is, after all a *unit* test, but not,
>>> presumably, the latter.
>>
>> Well I guess you could rule out both by asserting strdup calls malloc.
>
> That would be to miss the point! Assume that strdup does not use
> malloc -- this is an environment where dynamic allocation is not
> permitted but we want to be able to copy some limited number of
> strings.

Um, OK. I was using the description in the Solaris man page:

The strdup() function returns a pointer to a new string that
is a duplicate of the string pointed to by s. The returned
pointer can be passed to free(). The space for the new
string is obtained using malloc(3C).

Given your caveat, I would first test the function that retuned the
memory and then carry on as before by asserting strdup calls that
function. I would then add tests to ensure the string was correctly
copied. This separates testing the memory management functionality from
the string copying.

See my earlier reply to "Don Y" for an example of how those tests would
be built.

--
Ian Collins

On Mar 9, 11:43*pm, Don Y <t...@isnotme.com> wrote:
>
> I.e., I can't come up with "constant" results against
> which to compare test-time results. *Sticking with the
> traditional malloc/free for example (my routines are
> more heavily parameterized), I can create a malloc.test
> that pushes size_t's to malloc. *But, aside from verifying
> the result is not NULL (or, *is* NULL, in some cases!),
> there's nothing I can do to check that the result is
> actually correct!
>
malloc() should be considered a special case. Really it's an IO
function, but the IO is to the heap. You verify that an IO function
works correctly be seeing that the attached hardware operates as
expected (or a dummy device gets the bits if you're testing nukes or
something). You verify that malloc() works by seeing that the heap
changes as you want it to. But you can't actually see the heap,
because it's a static array in the mymalloc() function.
For instance if malloc() returns two pointers to the same block of
memory, that would be very hard to catch in a black box test.

Ian Collins <ian-> writes:

> On 03/11/12 11:40 AM, Ben Bacarisse wrote:
>> Ian Collins<ian-> writes:
>>
>>> On 03/11/12 01:00 AM, Ben Bacarisse wrote:
>>>> Ian Collins<ian-> writes:
>>>> <snip>
>>>>> I don't see how a function like malloc is any different (form a unit
>>>>> testing perspective) than any other.
>>>>
>>>> To take a simple well-know case (so I don't have to find a way to write
>>>> the specification!) what would unit tests for strdup look like? In
>>>> particular, it would be a bug if strdup returned a pointer to a region
>>>> of memory that overlapped with one returned by any other allocating
>>>> function or, indeed, by strdup itself. Now you may rule out testing for
>>>> the former because this is, after all a *unit* test, but not,
>>>> presumably, the latter.
>>>
>>> Well I guess you could rule out both by asserting strdup calls malloc.
>>
>> That would be to miss the point! Assume that strdup does not use
>> malloc -- this is an environment where dynamic allocation is not
>> permitted but we want to be able to copy some limited number of
>> strings.
>
> Um, OK. I was using the description in the Solaris man page:
>
> The strdup() function returns a pointer to a new string that
> is a duplicate of the string pointed to by s. The returned
> pointer can be passed to free(). The space for the new
> string is obtained using malloc(3C).
>
> Given your caveat, I would first test the function that retuned the
> memory and then carry on as before by asserting strdup calls that
> function. I would then add tests to ensure the string was correctly
> copied. This separates testing the memory management functionality
> from the string copying.
>
> See my earlier reply to "Don Y" for an example of how those tests
> would be built.

Hmm... I'm not seeing it. Can we take a specific case? Your previous
post happened to have a strdup with a bug (storage returned was one byte
too short). What sort of unit test would pick that bug up? I may be
misreading the allocation tests you are referring to but they don't seem
to cover that.

--
Ben.

On 03/11/12 01:42 PM, Ben Bacarisse wrote:
> Ian Collins<ian-> writes:
>
>> On 03/11/12 11:40 AM, Ben Bacarisse wrote:
>>> Ian Collins<ian-> writes:
>>>
>>>> On 03/11/12 01:00 AM, Ben Bacarisse wrote:
>>>>> Ian Collins<ian-> writes:
>>>>> <snip>
>>>>>> I don't see how a function like malloc is any different (form a unit
>>>>>> testing perspective) than any other.
>>>>>
>>>>> To take a simple well-know case (so I don't have to find a way to write
>>>>> the specification!) what would unit tests for strdup look like? In
>>>>> particular, it would be a bug if strdup returned a pointer to a region
>>>>> of memory that overlapped with one returned by any other allocating
>>>>> function or, indeed, by strdup itself. Now you may rule out testing for
>>>>> the former because this is, after all a *unit* test, but not,
>>>>> presumably, the latter.
>>>>
>>>> Well I guess you could rule out both by asserting strdup calls malloc.
>>>
>>> That would be to miss the point! Assume that strdup does not use
>>> malloc -- this is an environment where dynamic allocation is not
>>> permitted but we want to be able to copy some limited number of
>>> strings.
>>
>> Um, OK. I was using the description in the Solaris man page:
>>
>> The strdup() function returns a pointer to a new string that
>> is a duplicate of the string pointed to by s. The returned
>> pointer can be passed to free(). The space for the new
>> string is obtained using malloc(3C).
>>
>> Given your caveat, I would first test the function that retuned the
>> memory and then carry on as before by asserting strdup calls that
>> function. I would then add tests to ensure the string was correctly
>> copied. This separates testing the memory management functionality
>> from the string copying.
>>
>> See my earlier reply to "Don Y" for an example of how those tests
>> would be built.
>
> Hmm... I'm not seeing it. Can we take a specific case? Your previous
> post happened to have a strdup with a bug (storage returned was one byte
> too short). What sort of unit test would pick that bug up? I may be
> misreading the allocation tests you are referring to but they don't seem
> to cover that.

I would probably be testing this a two separate libraries. The memory
allocation functions would have their own set of tests and I would then
mock those functions (let's call them staticMalloc and staticFree) in
the string library tests.

So in my string library tests I would have a test like:

TEST_F( MyStingTest,
requestedBufferSizeOneMoreThanStringLength )
{
const char* string = "hello";

test::staticMalloc::expect( sizeof(string)+1 );

strdup( string );

ASSERT_TRUE( test::staticMalloc::called );
}


--
Ian Collins

Ian Collins <ian-> writes:

> On 03/11/12 01:42 PM, Ben Bacarisse wrote:
>> Ian Collins<ian-> writes:
>>
>>> On 03/11/12 11:40 AM, Ben Bacarisse wrote:
>>>> Ian Collins<ian-> writes:
>>>>
>>>>> On 03/11/12 01:00 AM, Ben Bacarisse wrote:
>>>>>> Ian Collins<ian-> writes:
>>>>>> <snip>
>>>>>>> I don't see how a function like malloc is any different (form a unit
>>>>>>> testing perspective) than any other.
>>>>>>
>>>>>> To take a simple well-know case (so I don't have to find a way to write
>>>>>> the specification!) what would unit tests for strdup look like? In
>>>>>> particular, it would be a bug if strdup returned a pointer to a region
>>>>>> of memory that overlapped with one returned by any other allocating
>>>>>> function or, indeed, by strdup itself. Now you may rule out testing for
>>>>>> the former because this is, after all a *unit* test, but not,
>>>>>> presumably, the latter.
>>>>>
>>>>> Well I guess you could rule out both by asserting strdup calls malloc.
>>>>
>>>> That would be to miss the point! Assume that strdup does not use
>>>> malloc -- this is an environment where dynamic allocation is not
>>>> permitted but we want to be able to copy some limited number of
>>>> strings.
>>>
>>> Um, OK. I was using the description in the Solaris man page:
>>>
>>> The strdup() function returns a pointer to a new string that
>>> is a duplicate of the string pointed to by s. The returned
>>> pointer can be passed to free(). The space for the new
>>> string is obtained using malloc(3C).
>>>
>>> Given your caveat, I would first test the function that retuned the
>>> memory and then carry on as before by asserting strdup calls that
>>> function. I would then add tests to ensure the string was correctly
>>> copied. This separates testing the memory management functionality
>>> from the string copying.
>>>
>>> See my earlier reply to "Don Y" for an example of how those tests
>>> would be built.
>>
>> Hmm... I'm not seeing it. Can we take a specific case? Your previous
>> post happened to have a strdup with a bug (storage returned was one byte
>> too short). What sort of unit test would pick that bug up? I may be
>> misreading the allocation tests you are referring to but they don't seem
>> to cover that.
>
> I would probably be testing this a two separate libraries. The memory
> allocation functions would have their own set of tests and I would
> then mock those functions (let's call them staticMalloc and
> staticFree) in the string library tests.
>
> So in my string library tests I would have a test like:
>
> TEST_F( MyStingTest,
> requestedBufferSizeOneMoreThanStringLength )
> {
> const char* string = "hello";
>
> test::staticMalloc::expect( sizeof(string)+1 );
>
> strdup( string );
>
> ASSERT_TRUE( test::staticMalloc::called );
> }

I see, thank you.

You have a bug in the test that is interesting -- the size is also wrong
here. That was a similar bug to the one in strdup. It seems a shame
that one of the things that needs to be tested (the size expression)
must be written out here as well -- I suppose that's why the code's
author should not write the tests. BTW, I might change the expect
call was to expect_at_least(...) so as to uncouple the test from
the implementation a little more.

If I can prevail on you some more... What about the requirement that
the malloced store be unique and not overlapping any others? Is that
done statistically by setting the memory to some known data pattern?

--
Ben.

On 03/11/12 04:09 PM, Ben Bacarisse wrote:
>>
>> I would probably be testing this a two separate libraries. The memory
>> allocation functions would have their own set of tests and I would
>> then mock those functions (let's call them staticMalloc and
>> staticFree) in the string library tests.
>>
>> So in my string library tests I would have a test like:
>>
>> TEST_F( MyStingTest,
>> requestedBufferSizeOneMoreThanStringLength )
>> {
>> const char* string = "hello";
>>
>> test::staticMalloc::expect( sizeof(string)+1 );
>>
>> strdup( string );
>>
>> ASSERT_TRUE( test::staticMalloc::called );
>> }
>
> I see, thank you.
>
> You have a bug in the test that is interesting -- the size is also wrong
> here. That was a similar bug to the one in strdup.

I would test with more than one string, so the bug would soon come to
light. I also try to use a different expression in the tests (such as
size of rather than strlen) to minimise common errors.

> It seems a shame
> that one of the things that needs to be tested (the size expression)
> must be written out here as well -- I suppose that's why the code's
> author should not write the tests.

The odds on the same bug appearing in two different expression are less
than a single occurrence. If I am working with a pair, we often swap
roles between tests. If I am working on my own, I have to take more care!

> BTW, I might change the expect
> call was to expect_at_least(...) so as to uncouple the test from
> the implementation a little more.

That would be fine for numeric values, but not much use for other types.
My harness' expect function accepts function objects as well as values
(one handy feature of C++), so I could use an at_least functor here.

> If I can prevail on you some more... What about the requirement that
> the malloced store be unique and not overlapping any others? Is that
> done statistically by setting the memory to some known data pattern?

That would be a memory allocator test. I'll ruminate some more on how
to write it!

--
Ian Collins

On Saturday, March 10, 2012 9:05:36 AM UTC, Don Y wrote:
> On 3/9/2012 9:53 PM, Ian Collins wrote:


> >>>> There's rarely a problem generating regression tests for
> >>>> functions/procedures that use concrete *values*:
> >>>>
> >>>> And, it is easy to erect the necessary scaffolding for those
> >>>> sorts of tests without introducing any noticeable uncertainty
> >>>> in the veracity of the results obtained.
> >>>>
> >>>> But, I can't see a way to handle this sort of testing on
> >>>> functions that manipulate *pointers* to objects -- without
> >>>> adding a fair bit of code to the scaffolding that, itself,
> >>>> represents a testing issue! (i.e., does the scaffolding
> >>>> have any bugs that result in false positives or negatives??)
> >>>
> >>> As a general point, it a lot easier and more satisfying for the
> >>> programmer to write the tests before the code under test.
> >>
> >> But that's the whole point -- you can't create test cases
> >> independant of the execution environment!
> >
> > Of course you can. How else would you test embedded code for a device
> > without external communications?
>
> For an embedded device, you *know* the environment you
> are operating in. You *know* where the heap resides
> (actual addresses). You know what the alignment
> restrictions of the processor are. You know that a
> request for 0x61 bytes with the heap starting at 0x40000000
> having a length of 0x100 in a byte alignable environment
> allocating from the *end* of the free list (as opposed to
> the start) trimming the allocation unit to the requested
> size *should* give you a result of 0x61 bytes located
> at 0x4000009F. You *then* know that an attempt to
> allocate 0x9E bytes will FAIL under the same calling
> conditions (because a 1 byte crumb will be left in the
> free list -- which "/* CAN'T HAPPEN */".
>
> I write MyMalloc() and hand it to you WITH A TEST SUITE.
> You run it on <whatever> processor and rely on the test
> suite to prove to you that the code works as advertised.
>
> Repeat the above example with a heap at 0x2000 (!!) of size
> 0x1000 and you get different results.
>
> >> What should "malloc(500)" return? 0x1234? 0x12345678?
> >> NULL?
> >
> > What ever *your test harness'* malloc is told to return.
>
> What "test harness malloc"? There *is* no "test harness
> malloc! Recall, I said "malloc and free *types* of functions"
> not "malloc and free" -- in particular, note the semantics of
> myfree() differ from free(3).
>
> All I can compare against is myself -- and if I have a bug
> then the other instance will faithfully repeat the same
> bug.

if you need to test something as complex as malloc you're going to have to open the box. I'd write validation code for the internal data structures. Code that tested for over-laps in allocated data (probably not possible if the data structures are ok) etc. Then run various test running the validation after each alloc or dealloc.

<snip>

> I'm going to give you some code to implement a MyMalloc
> (-like) function. I'm not going to tell you where
> the heap resides in memory. I'm not going to tell you
> if memory accesses must be byte/word/cache-line aligned.
> Heck, I'm not even going to tell you how *big* the heap
> is!
>
> What are your test cases? How do you know if they have
> succeeded or not? I.e., just because MyMalloc *appears*
> to return a value, are you sure that it is the *correct*
> value?
>
> Are you sure that the allocation strategy actually enacted
> was "smallest fit" and not "last fit" or "largest fit"?
> (my memory management system is highly parameterized)
> How do you know that the allocated block was *intentionally*
> aligned with whatever the processor wants -- instead of
> *coincidentally* happening to be aligned? Are you sure
> that any "crumbs" left behind in the free list as a
> result of that alignment are recoverable? (i.e., if
> you left a single byte behind, then you probably can never
> recover it since its not big enough to contain the list
> overhead necessary to tie it into the free list)

white box rather than black box testing.

On Saturday, March 10, 2012 6:29:53 PM UTC, Kaz Kylheku wrote:
> On 2012-03-10, nick_keighley wrote:
> > On Friday, March 9, 2012 11:56:22 PM UTC, Ian Collins wrote:
> >> On 03/10/12 12:43 PM, Don Y

> >> > But, I can't see a way to handle this sort of testing on
> >> > functions that manipulate *pointers* to objects -- without
> >> > adding a fair bit of code to the scaffolding that, itself,
> >> > represents a testing issue! (i.e., does the scaffolding
> >> > have any bugs that result in false positives or negatives??)
> >
> > I think you have to draw the line somewhere. Testing test code
> > leads you into a infinite regression.
>
> That is moot anyway because the point of a /regression/ test suite isn't to
> find bugs or validate functionality. It's simply to validate that the
> behavior hasn't changed between revisions (including buggy behavior!)

ah. ok. But the first time you run the test it /is/ supposed to be part of your validation.

> Thus an imperfect regression test suite can still find a regression.

<snip>

> >> As a general point, it a lot easier and more satisfying for the
> >> programmer to write the tests before the code under test.
> >
> > I know this is the received wisdom in certain circles but I have trouble
>
> This is just "top down design" under new verbiage.

ah, I thought it was nonsense the first time round! I remember reading a book where a guy constructed an entire program top. Jolly cleaver I thought but how does he know how to write exectly the right procedure at each step. To make no mistakes, no false steps. I suspected then- and more than suspect now! that he didn't actually write the program the way he claimed he'd written it.

> Some programmers like to
> write the low-level functions and then express the higher level ones in terms
> of the language of these lower level functions. Other programmers are able to
> write the top that they want first and fill in the bottom.

I do a bit of both. I like to think of the "outside" of the program. Then go into a tool building phase. These are the sort of things I'll need to getthe outside behaviour. The bolt things together, testing as I go. If its very complex then there may be many layers. Oh and these days OO seems to the natural way to do things even if C is the implementaion language. Functional programs I'm still struggling with.

> > writing the test before I've at least specified the function's
> > prototype. And certain tests aren't writable until you've seen the
> > function's internals. For instance certain floating point
> > calculations may have divide by zero possibilities which you only
> > know about once you've seen the code.
>
> There are obvious limitations to "test first" or "top down".

my favourite example was a stream of bytes to hold messages. This could be read from, usually forwards but occaisonally backwards. Internally the stream was a singly linked list of fixed sized blocks. 32 bytes in size if I remeber correctly. This was hurried into "integration test" (put everyting ina big bag and shake it) without any module testing. In the field it failed.. That's right when it tried to reverse over a block boundary.

> For instance, imagine it is 1969. Let's write a test case for the
> awk language!
> Okay, let's see now: invent C, Unix, Yacc, the Bourne shell, etc.
> Finally, awk arrives, and and we can execute our test case!
>
> Bottom up is the way things really progress; top down is a small-scale, local
> aberration.

I used to design top down but implement bottom up. Writing mock functions so I can implement and test top down just seems tedious.

top down used to lead to some odd programs. One program I saw seemed to follow a rule of three. The top called three functions each in turn called three more. Eventually he got bored and a big lump of code down in the bowels suddenly did all the work.