Regression testing for pointers

[Don Y]

Hi,

There's rarely a problem generating regression tests for
functions/procedures that use concrete *values*:

sqrt.test

3 --> 1.732
4 --> 2
5 --> 2.236

(apologies if I have misremembered any of these 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??)

In particular, I am trying to develop a test suite for my
dynamic memory management functions (e.g., malloc and free
types of routines).

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!

[Recall, the location and size of the free store might change
from environment to environment; alignment constraints might
vary, etc.]

E.g., if a test invocation of malloc(100) returns 0x12345678
in one environment, it could just as easily return 0x1234
in *another* (smaller address space). A second, identical test
invocation returning 0x87654321 could likewise be "correct".

About the only thing I can check for is if that second
invocation returned 0x12345699 (which overlaps the previous
allocation at 0x12345678!).

Furthermore, just examining the results from malloc don't
tell me that the freelist is being maintained, properly.

Of course, I can write code to inspect these objects in
greater detail. But, then the test scaffolding starts to
rival the complexity of the functions being tested! (bugs)

I guess the "ideal" I see would be to be able to build a
"memory image" and verify that the functions cause expected
and predicted changes in that "image".

E.g., as the allocation policy is varied, to see the
effects of that reflected in the changes to the free list
before vs. after the invocation.

But, I can't see any way to make this NOT require some sort
of active probing of memory by the test scaffolding (which
means the internals of the functions have to be exposed to
the test suite).

So: how do other folks test for pointer manipulation? etc.

 

[Ian Collins]

Hi,

There's rarely a problem generating regression tests for
functions/procedures that use concrete *values*:

sqrt.test

3 --> 1.732
4 --> 2
5 --> 2.236

(apologies if I have misremembered any of these 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.

In particular, I am trying to develop a test suite for my
dynamic memory management functions (e.g., malloc and free
types of routines).

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!

Mock the functions your code calls.

I have a mocking library that can be used to mock any C function (given
its return and parameter types) for use in unit tests which enables me
to specify expected parameters and returned results. I find this
invaluable for comprehensive uni testing.

 

[Don Y]

Hi Ian,

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!

What should "malloc(500)" return? 0x1234? 0x12345678?
NULL?

Mock the functions your code calls.

I have a mocking library that can be used to mock any C function (given
its return and parameter types) for use in unit tests which enables me
to specify expected parameters and returned results. I find this
invaluable for comprehensive uni testing.

I don't see how that will help me. Malloc doesn't "call* anything.
It massages blocks of memory in ways that vary depending on the
platform involved, etc.

E.g.,

foo = malloc(500);
result = myfree(foo, 451);

can work on some platforms and not on others; and, among
those where it does work, can give different results from
platform to platform.

The problem becomes even more difficult when you start
varying allocation strategies, fragmentation criteria, etc.

 

[Kaz Kylheku]

In particular, I am trying to develop a test suite for my
dynamic memory management functions (e.g., malloc and free
types of routines).

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!

A possible regression test case for malloc routines is a program which beats up
the routines, performs certain validation on the inputs and terminates
successfully.

About the only thing I can check for is if that second
invocation returned 0x12345699 (which overlaps the previous
allocation at 0x12345678!).

You could allocate some random blocks and keep them in an array. All such
blocks should be non-overlapping.

Another thing to test for is that the allocator is not getting confused and
overwriting the data areas of the blocks.

Put data in the blocks and maintain checksums. Check that the allocator
operations do not change anything.

Also, the regression test does not have to use only the public routines. Give
your allocator routines some debugging functions.

The test could check, for instance, that the allocator's data structures have
returned to some proper state after the blocks have been freed.

This could be repeated for different orders of freeing the blocks: in order, in
reverse order, in scrambled order.

You could have some self-check routines in the allocator. For instance if it
keeps counters about how much has been allocated, etc, a function could be
provided which performs a check by walking the data structure to validate that
the meta-data matches the structure.

Furthermore, just examining the results from malloc don't
tell me that the freelist is being maintained, properly.

See above: expose an internal routine that validates the sanity of the
free list, and use it in the regression test case.

Of course, I can write code to inspect these objects in
greater detail. But, then the test scaffolding starts to
rival the complexity of the functions being tested! (bugs)

But that is fine because that scaffolding isn't what is being deployed.

A wind tunnel is going to be larger than the aircraft part being tested.
That's a given.

I guess the "ideal" I see would be to be able to build a
"memory image" and verify that the functions cause expected
and predicted changes in that "image".

That's not a bad idea.

The image will likely contain pointers. Those can be normalized by changing
them to offsets from the base address.

As a substitute for a binary image dump, you could have a
symbolic dump which traverses everything and produces
a printed representation of it.

But, I can't see any way to make this NOT require some sort
of active probing of memory by the test scaffolding (which
means the internals of the functions have to be exposed to
the test suite).

Exposing internals to a regression test: fine idea.

Would you not test electronic hardware with some probes
to check voltage levels and signals?

 

[Ian Collins]

Hi Ian,



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?

What should "malloc(500)" return? 0x1234? 0x12345678?
NULL?

What ever *your test harness'* malloc is told to return.

I don't see how that will help me. Malloc doesn't "call* anything.
It massages blocks of memory in ways that vary depending on the
platform involved, etc.

That's why you want to use a mock - to make your tests platform neutral.

 

[Ian Collins]

What ever *your test harness'* malloc is told to return.

Maybe an example is called for:

Given

typedef struct { int n; } X;

X* makeAnX( int nx; )
{
X* p = malloc( sizeof *p );
p->n = n;
return p;
}

A Googletest test (my library is C++, C simply can't do what it does.
But that doesn't matter as for testing C functions) function using my
mocks may look something like:

void testSomething()
{
X testX;

malloc::willReturn &testX;
malloc::expect( sizeof(X) );

X* p = makeAnX( 42 );

ASSERT_EQ( p, &testX );
ASSERT_EQ( 42, n-> );
}

The above tests that makeAnX passes the expected value to malloc and the
correct value is returned from makeAnX.

 

[Jorgen Grahn]

Hi,

There's rarely a problem generating regression tests for
functions/procedures that use concrete *values*:

sqrt.test

3 --> 1.732
4 --> 2
5 --> 2.236

(apologies if I have misremembered any of these 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??)

In particular, I am trying to develop a test suite for my
dynamic memory management functions (e.g., malloc and free
types of routines).

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!

I don't see the problem. The semantics of malloc() are:

- malloc(N) returns either 0 or a pointer to N usable bytes
- that pointer is aligned in some useful way
- active malloc()ed blocks don't overlap

And that's surely something you can test. The number of possible
inputs is staggering, so picking relevant ones is hard ... but the
pass/fail criteria are rather straightforward.

Mixing free() into this is trickier, but still not in the way that
seems to worry you. For starters, how can you make this implementation
fail the tests?

void free(void *ptr) { ; }

....

Furthermore, just examining the results from malloc don't
tell me that the freelist is being maintained, properly.

Of course, I can write code to inspect these objects in
greater detail. But, then the test scaffolding starts to
rival the complexity of the functions being tested! (bugs)

I think this is just a function of the fact that writing a good
malloc/free is *hard*.

/Jorgen

 

[Don Y]

Hi Ian,

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 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.

That's why you want to use a mock - to make your tests platform neutral.

Sorry, I just don't see this.

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)

 

[Don Y]

Hi Jorgen,

---^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Note the use of "TYPES of routines" (i.e., NOT "malloc")

I don't see the problem. The semantics of malloc() are:

See above. And, the earlier comment regarding "functions
(in general) that manipulate pointers.

- malloc(N) returns either 0 or a pointer to N usable bytes
- that pointer is aligned in some useful way
- active malloc()ed blocks don't overlap

And that's surely something you can test.

No, you can't. You don't know what valid results *are*!
Can I allocate 64K of memory? 4G bytes of memory? How
much memory do I really *have* available? If I allocate
X bytes of memory, where will it end up located (even if
you stick to the conventional malloc, you have no way
of telling if it has actually allocated memory from
a *real* place in memory. You have no way of knowing
how many of those allocations can/will succeed before the
heap is exhausted. Or, do you just keep issuing requests
until malloc fails? Then, examine all of the results
to see if the above conditions hold for all such
allocations? How do you *know* that the pointer is
aligned properly and not just "coincidence".

2+2 == 2*2

The number of possible
inputs is staggering, so picking relevant ones is hard ... but the
pass/fail criteria are rather straightforward.

Mixing free() into this is trickier, but still not in the way that
seems to worry you. For starters, how can you make this implementation
fail the tests?

void free(void *ptr) { ; }

What if ptr references a location that was NEVER in the heap?
What if it references a location that could never have been
*returned* by malloc()? E.g., not properly aligned.

I think this is just a function of the fact that writing a good
malloc/free is *hard*.

Writing the subsystem is fairly easy. But, coming up with
a robust way of testing it so that others can deploy it
on very different hardware is proving difficult.

E.g., I can give you source for sqrt() and you could port it
to <whatever> and then reassure yourself that it is working
properly by running a set of test cases (that I provide
and you potentially augment) through it and verify the results.
sqrt(3) =?= 1.732, etc. "3" doesn't change from one platform
to another. Nor does "1.732".

Since you can't nail down actual addresses a priori (i.e., at
test creation time), the only way to design aggressive tests
(for memory allocators) is to do so algorithmically. But,
then your test suite becomes nontrivial and subject to
bugs (1.732 is ALWAYS 1.732)

 

[Ian Collins]

Hi Ian,



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.

Ah, I see. I though you were testing something that used malloc, rather
than an implementation of malloc.

In the case above, just use conditionally compiled constants for heap
base and size.

I don't see how a function like malloc is any different (form a unit
testing perspective) than any other.

 

[Guest]

On 03/10/12 12:43 PM, Don Y

I think you have to draw the line somewhere. Testing test code leads you into a infinite regression.

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 writing the test before I've at least specified the function's prototype. Andcertain 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.

<snip>

 

[Ben Bacarisse]

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.

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?

 

[BartC]

Writing the subsystem is fairly easy. But, coming up with
a robust way of testing it so that others can deploy it
on very different hardware is proving difficult.

E.g., I can give you source for sqrt() and you could port it
to <whatever> and then reassure yourself that it is working
properly by running a set of test cases (that I provide
and you potentially augment) through it and verify the results.
sqrt(3) =?= 1.732, etc. "3" doesn't change from one platform
to another. Nor does "1.732".

Actually the square root of 3, as returned from such a function, *can*
change between platforms. But is that due to differences in precision, or
because of a bug?

Since you can't nail down actual addresses a priori (i.e., at
test creation time), the only way to design aggressive tests
(for memory allocators) is to do so algorithmically. But,
then your test suite becomes nontrivial and subject to
bugs (1.732 is ALWAYS 1.732)

Maybe you're just trying too hard. Are you trying to produce some software,
which, without benefit of alpha and beta versions, can be released as a
version 1.000 with *no* bugs?

I'm not sure that's possible except for the most trivial examples, and even
then you might just be getting the right answers by luck.

And then there's performance to be considered; it might work properly, but
too slowly. Or it might only slow down after a particular pattern of inputs.
Functions such as allocators are very difficult to test. And it might be
difficult to just think up suitable tests, without feedback from actual
trials.

 

[Don Y]

Hi Nick,

I think you have to draw the line somewhere. Testing test code
leads you into a infinite regression.

Of course! Hence the desire for your test scaffolding to
be "above suspicion". The more "thinking" that it has to
do (to adapt to a test environment and particular test
results), then the more opportunities there are for errors
to creep into it.

This is especially the case where the scaffolding is "special"
for (one?) particular function.

I know this is the received wisdom in certain circles but I have
trouble 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.

I tend to keep a list of the types of things that I *see* as
potentially "going wrong" while I am writing the code. At the
very least, I want my test cases to cover every path *through*
the code. And, test the various boundary conditions that
the code makes obvious.

However, just *thinking* about how you might test something
brings up other cases that you might have to formally
specify in the contract. E.g., what happens if you "free"
a block that has already been free-d? (do you silently
ignore it? or throw an assertion failure??)

I think it important to consider how functions will be used
and ABused in designing your tests. E.g., I build memory
management functions with scads of invariants within that
verify the caller isn't trying to do something "wrong"
(because callers tend to screw up when it comes to using
memory management routines). I'd rather have a routine lock
up during testing (where I can *see* it) than worry about
some latent bug in "production".

 

[Kaz Kylheku]

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!)

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

Some of the output of a regression test case could be due to a bug in the test
case. If that output changes because of a regression in the software being
tested, the test case has done its job anyway.

The test suite shows (within the limitations of its coverage) that the new
revision of the software duplicates the old revision, not only
feature-for-feature, as well as bug-for-bug.

Sometimes when you fix a bug in the program, you have to update the test suite,
because it has test cases which confirm the buggy behavior.

I know this is the received wisdom in certain circles but I have trouble

This is just "top down design" under new verbiage. 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.

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".

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.

 

[Don Y]

Hi Bart,

Actually the square root of 3, as returned from such a function, *can*
change between platforms. But is that due to differences in precision, or
because of a bug?

You can ensure that the routine is good to "N digits"
(where N is related to the minimum conforming "DBL_DIG";
your algorithm could provide more, or less, depending on
its design. OTOH, saying sqrt(3) == 1.7 is probably not
what the contract guarantees! :> )

Maybe you're just trying too hard. Are you trying to produce some software,
which, without benefit of alpha and beta versions, can be released as a
version 1.000 with *no* bugs?

First of all, I consider it sinful to release code that hasn't
been tested. "Well, I ran it a couple of times and it *looked*
like it was working. Play with it and tell me what you think..."
is not a valid attitude, IMO.

Second, testing helps clarify how a function/subsystem is
*intended* to work. It tells users of those functions/subsystems
what they should expect from "real-world examples". E.g.,
tests expected not to succeed are commented in the test suite
as to WHY they won't "work" (e.g., sqrt(-1)).

Third, it often helps *you* think of situations that you might
not have addressed -- or, in which the contract may be deficient.

Fourth, they act as REGRESSION tests to safeguard against
the INTRODUCTION of bugs after release: "This stuff USED TO
WORK, why doesn't it *now*?"

I'm not sure that's possible except for the most trivial examples, and even
then you might just be getting the right answers by luck.

"Luck" has no place in an engineering/science discipline:
"Here, Isaac, drop the apple... maybe it will FALL"

You engineer tests to *verify* expected results. If the test
doesn't turn out the way you *expect*, it should truly be a
surprise to you!

And then there's performance to be considered; it might work properly, but
too slowly. Or it might only slow down after a particular pattern of
inputs.

That, in itself (in this particular case) is actually one of the
things you want to test for! *If* the code is functioning
properly, then I can expect performance to be X in this situation
(based on the deliberate actions I have taken to fragment the
free list).

Part of the rationale for my abandonment of the traditional
malloc/free approach is because it doesn't give the programmer
any control over runtime *performance* -- it's an opaque box!

Functions such as allocators are very difficult to test. And it might be
difficult to just think up suitable tests, without feedback from actual
trials.

How could a "trial" possibly give me more information than I
have available when examining the source? If I know my art,
then I should be able to anticipate damn near every possible
case that the code will encounter -- moreso than an application
is likely to stumble upon in the course of pursuing *its* goal.

 

[Don Y]

Hi Ian,

Ah, I see. I though you were testing something that used malloc, rather
than an implementation of malloc.

Exactly. And, since so much relies on this subsystem, I
want to "beat on it" pretty severely to assure myself (and
others porting to other platforms) that it *does* handle
every potential "situation".

In the case above, just use conditionally compiled constants for heap
base and size.

That assumes you can put the heap where your test suite wants
it. E.g., on a tiny processor, the heap might be at 0xA000;
on a desktop, at 0x40020000; on a 64b machine...

Similarly, the amount of memory *in* the heap might vary.
You could allocate 1MB on a desktop platform but 10KB on
a tiny machine might be "oodles". If you've written with
the tiny machine in mind, perhaps you've a latent bug where
you expected pointers to be 16b instead of 32b (sure, you
can code to deal with this; but, you can also FORGET TO
CODE to deal with this!).

The alignment constraints of the processor might change from
what your test cases "expect".

Etc. You could *code* a "test routine" that examines these
things and *intelligently* invokes the UUT. But, that means
you start migrating complexity into the "tester" that can be
just as tricky (if not trickier!) as the code you are hoping
to "test".

I don't see how a function like malloc is any different (form a unit
testing perspective) than any other.

Because addresses aren't as constrained (in the language) as
*values*. "3" is "3" is "3". But, for a given object, you
can have environments where &object can NEVER be 0x0...3 -- or
0x0...2 (!), etc.

At the same time, that same code can execute in environments
where this assertion doesn't hold.

Yet, BOTH are "correct".

 

[Don Y]

Hi Kaz,

A possible regression test case for malloc routines is a program which beats up
the routines, performs certain validation on the inputs and terminates
successfully.

But that doesn't "prove" that the functions are operating as
*designed*/expected.

E.g., my allocator allows the caller to tell it *how* to select
a chunk of memory from the free list, *where* in the free list
that selection should be made, how the selection should be modified
to fit the specifications of the request, etc.

The allocator can "satisfy" all of the requests that I make
of it (i.e., can return non NULL) yet could have done so
in entirely the wrong "way".

You could allocate some random blocks and keep them in an array. All such
blocks should be non-overlapping.

But that still doesn't tell you that it is returning the *correct*
results. You're testing an *aspect* of the allocator which doesn;t
guarantee that the allocator itself is functioning properly.

E.g., imagine testing sqrt() with (pseudocode):

lastvalue = 0.
lastresult = 0
do {
value = lastvalue + 1.
result = sqrt(value)
if ! (result > lastresult)
break;
lastvalue = value
lastresult = result
} while (FOREVER)

I.e., a functioning sqrt() will comply with this test. But,
a MALfunctioning one will, as well!

Another thing to test for is that the allocator is not getting confused and
overwriting the data areas of the blocks.

Put data in the blocks and maintain checksums. Check that the allocator
operations do not change anything.

Again, that's just poking an *aspect* of the allocation
not testing the allocator's functionality. Before the blocks
are allocated, their contents are indeterminate. You don't
*care* if the allocator screws with them prior to allocation.
All you care is that it doesn't alter the contents of ALLOCATED
blocks.

Also, the regression test does not have to use only the public routines. Give
your allocator routines some debugging functions.

The test could check, for instance, that the allocator's data structures have
returned to some proper state after the blocks have been freed.

The code already is littered with invariants. I am *sure* it
"works". :> The problem is making sure that it continues to
work wen ported to other platforms, when "tweeked" by well
meaning developers, etc.

This could be repeated for different orders of freeing the blocks: in order, in
reverse order, in scrambled order.

In my case, its considerably harder than that. You tell the allocator
(and reclamation function) how you want the free list managed. So,
you can allocate using a set of criteria (call them "A1") and release
with some criteria R1. The *next* allocation would yield M1.

OTOH, allocating with A1 and releasing with R2 could cause the next
allocation to yield M2 (!) -- and be operating exactly as designed!

You could have some self-check routines in the allocator. For instance if it
keeps counters about how much has been allocated, etc, a function could be
provided which performs a check by walking the data structure to validate that
the meta-data matches the structure.

See above (invariants)

See above: expose an internal routine that validates the sanity of the
free list, and use it in the regression test case.


But that is fine because that scaffolding isn't what is being deployed.

A wind tunnel is going to be larger than the aircraft part being tested.
That's a given.

But the effort to VALIDATE the wind tunnel is amortized over
ALL of the aircraft parts being tested in that tunnel. Imagine
building a special wind tunnel for the wing. Of *this* ONE
airframe. And, yet another for the tail section. Another for
the fuselage, etc.

Each needs to be validated in its own right before being relied
upon to vouch for the "correctness" of the items tested within.

That's not a bad idea.

The image will likely contain pointers. Those can be normalized by changing
them to offsets from the base address.

As a substitute for a binary image dump, you could have a
symbolic dump which traverses everything and produces
a printed representation of it.

The problem is building the "template" image. You can't just
put pointers anywhere. E.g., how do you create an "unaligned
pointer" in the language?

Exposing internals to a regression test: fine idea.

Would you not test electronic hardware with some probes
to check voltage levels and signals?

Sure. But I wouldn't grab a length of #12AWG and use it to
probe the front end of a satellite receiver! I'd get a
probe that was VALIDATED AS APPROPRIATE for that sort of
testing.

 

[Ian Collins]

Hi Ian,



That assumes you can put the heap where your test suite wants
it. E.g., on a tiny processor, the heap might be at 0xA000;
on a desktop, at 0x40020000; on a 64b machine...

Similarly, the amount of memory *in* the heap might vary.
You could allocate 1MB on a desktop platform but 10KB on
a tiny machine might be "oodles". If you've written with
the tiny machine in mind, perhaps you've a latent bug where
you expected pointers to be 16b instead of 32b (sure, you
can code to deal with this; but, you can also FORGET TO
CODE to deal with this!).

The alignment constraints of the processor might change from
what your test cases "expect".

Etc. You could *code* a "test routine" that examines these
things and *intelligently* invokes the UUT. But, that means
you start migrating complexity into the "tester" that can be
just as tricky (if not trickier!) as the code you are hoping
to "test".

OK, it's a dull Sunday morning, so I cooked up a quick working example
using Google Test.

The simple function myMalloc() will:

Return NULL for a zero size request.
Return a correctly aligned pointer within the heap for a non-zero request.
Use a fixed heap base of 0xA000 and size of 0x1000 on TARGET_X.

#if defined TARGET_X
const uint8_t* heapBase = 0xA000;
const size_t heapSize = 0x1000;
const size_t minAlign = 8;
#else
uint8_t* heapBase = NULL;
size_t heapSize = 0x1000;
size_t minAlign = 8;
#endif

void* myMalloc( size_t size )
{
size_t offset = 0;

if( size )
{
while( (size_t)(heapBase+offset)%minAlign ) ++offset;

return heapBase+offset;
}
return NULL;
}

TEST_F( MyMallocTest,
returnIsNullForZeroByteRequest )
{
ASSERT_FALSE( myMalloc(0) );
}

TEST_F( MyMallocTest,
returnIsInHeapForOneByteRequest )
{
ASSERT_TRUE( myMalloc(1) >= heapBase );
ASSERT_TRUE( myMalloc(1) < heapBase+heapSize );
}

TEST_F( MyMallocTest,
returnForOneByteRequestCorrectlyAlligned )
{
ASSERT_EQ( 0, (size_t)myMalloc(1)%minAlign );
}

TEST_F( MyMallocTest,
returnForOneByteRequestCorrectlyAllignedFor128Bytes )
{
minAlign = 128;
ASSERT_EQ( 0, (size_t)myMalloc(1)%minAlign );
}

The Google test code is at the end to avoid clutter.

Because addresses aren't as constrained (in the language) as
*values*. "3" is "3" is "3". But, for a given object, you
can have environments where&object can NEVER be 0x0...3 -- or
0x0...2 (!), etc.

At the same time, that same code can execute in environments
where this assertion doesn't hold.

Yet, BOTH are "correct".

Does the exaple above help?

--
Google test bits for the test:

#include <gtest/gtest.h>

struct MyMallocTest : testing::Test
{
uint8_t* heap;

MyMallocTest()
{
heap = new uint8_t[heapSize];
heapBase = heap;
}

~MyMallocTest()
{
heapSize = 0x1000;
delete heap;
}

void SetUp() { memset( heap, '@', heapSize ); }
};

// tests go here

int main( int argc, char **argv )
{
testing::InitGoogleTest(&argc, argv);

return RUN_ALL_TESTS();
}

 

[Ian Collins]

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.

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;