Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Don Y <this@isnotme.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Regression testing for pointers |
| Date | 2012-03-12 19:23 -0700 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <jjmb2l$klf$1@speranza.aioe.org> (permalink) |
| References | <jje4jg$l8k$1@speranza.aioe.org> <UaOdnXvsapxVC8PSnZ2dnUVZ_t2dnZ2d@posted.internetamerica> |
Hi Gordon,
On 3/12/2012 5:37 PM, Gordon Burditt wrote:
>> 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??)
>
> Most functions that manipulate pointers can be tested by what it
> puts *IN* the memory pointed at by pointers. For example, one test
> of the non-standard function strdup() can be done by comparing the
> string and the copy. A test of fgets() could test that the buffer
> contents reflects the contents of the test file being read, and
> that fgets() doesn't write too far. A test of a parser that builds
> a complicated tree of nodes out of source code input can look at
> the contents of the parse tree and perhaps check if all nodes
> allocated are either freed or still reachable. The exact position
> of the nodes is not important, as long as they don't overlap.
Correct. But when the "product" in question *is* the pointer,
the issue changes!
> malloc() and free() are exceptions to this. You could check that
> newly-allocated memory is filled with 0xdeadbeef and freed memory
> is filled with 0xfreebee1 (and in the process, perhaps figure out
> if it is rounding up your request size properly) if your malloc()
> has that debug feature.
>
>> In particular, I am trying to develop a test suite for my
>> dynamic memory management functions (e.g., malloc and free
>> types of routines).
---^^^^^^^^^^^^^^^^^
Note I am not debugging "malloc(3)" but, rather, allocateMemory()
(there is no malloc in the system -- because malloc has poor
semantics)
>> 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!
>
> Do you want to open the black box or not?
>
> If so, you can write things like a malloc() arena consistency checker
> (if it doesn't come with one already) to ensure that the arena is
> consistent, and call it before and after every call to malloc().
> (You can verify *that* by scribbling beyond the end of memory you
> allocated and determining that the consistency check fails, or
> deliberately introducing errors into malloc() or free().) You
> may also be able to take snapshots of the free list before and after
> and determine that it is obeying any policy options in effect for
> where to allocate memory.
If I *know* the execution environment, I can get all of this
information just from looking at the returned pointers from
the allocator. No need to peek inside at the free list, etc.
My allocator gives the developer precise control over how it
operates. How it selects the "right" fragment from the free
list, how it decides which *part* of that fragment to use
for the request, what it does with the balance of the
fragment, etc.
So, starting with a full heap (as a single "fragment"), I
can predict exactly what the return value of each allocation
request will be (as long as you let me *see* each such request
and releaseMemory() invocations). Furthermore, I can predict
how "expensive" (time) each such request will be.
E.g., (pseudocode -- ignore errors)
#if BUFSIZE < MINFRAGSIZE
# error ...
#endif
#if BUFFERS < 1
# error ...
#endif
...
createHeap(&theHeap, &memory[], BUFFERS * BUFSIZE)
// create the individual buffers
lastptr = NULL
do {
ptr = (list*) allocateMemory(theHeap, BUFSIZE, FIRSTFIT, TRIMTOSIZE)
ptr->next = lastptr
lastptr = ptr
} while (ptr != NULL)
// place the buffers back into the heap while retaining their sizes
while (ptr != NULL) {
lastptr = ptr->next // can't peek inside the heap once released!
releaseMemory(ptr, RETAINSIZE, ATHEAD)
ptr = lastptr
}
At this point, I have built a pool of fixed size buffers.
Hereafter,
allocateMemory(theHeap, BUFSIZE, FIRSTFIT, EXACTFIT)
will give me a result in constant time -- regardless of the
number of buffers in the pool (because it just grabs the first
fragment off the free list -- which we KNOW is the exact size
that we want!). Similarly,
releaseMemory(ptr, RETAINSIZE, ATHEAD)
will "free" that buffer (for reuse) also in constant time
(because it never has to traverse the free list to append
the "fragment/buffer" -- nor does it have to try to combine
the fragment with adjoining/contiguous fragments in an attempt
to make larger "free fragments")
Furthermore, I can take a single heap and use it to implement
two different types of memory -- a set of fixed size buffers
on one end and variable size buffers on the other. Or, a set
of buffers of a different fixed size.
It's important that the results of each such invocation be
predictable -- not "ad hoc" like malloc(3) would like you
to believe.
> If not, you can check that no two allocations still in force overlap
> each other. You can also check that the pointers returned are
> properly aligned.
>
> I haven't checked, but if you free() a block of memory of size N
> previously allocated, then repeatedly allocate memory blocks of
> size N, you should allocate a block that at least partially
> overlaps the one you free()d before running out of memory.
>
>> [Recall, the location and size of the free store might change
>> from environment to environment;
>
> The location of the free store might change from run to run of the
> *same* executable with the same modification time, due to code that
> tries to prevent buffer overflows from being exploitable by randomizing
> load locations. There is nothing to prohibit this. On a 64-bit
> machine, the OS might try to never re-use any address from one
> program run to any other address in another program run, for the
> lifetime of that CPU.
I'm *below*/alongside the OS. (*I* provide the memory that
the OS uses internally!) Any of these sorts of features *I*
would have to implement -- or, something layered on top of me.
(I write for bare iron)
>> 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.
>
> Not getting back overlapping allocations is a fairly good indication.
For *malloc*, perhaps.
But, if I tell the allocator to select the LAST_FITTING fragment
from the free list, I would expect the pointer returned to be
significantly different than the pointer returned from the
allocation that preceded it using a FIRST_FITTING criteria.
I.e., the allocator's role isn't just to "provide memory"
but to provide the memory per criteria that the caller
supplies.
>> 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)
>
> Some functions are like that. Try writing a test suite for a SQL
> server sometime. Especially if you aren't allowed to examine any
> of the stuff it has stored on disk. Or try testing a C compiler
> as a black box when all the results you get are:
>
> - Compilation failed (with a list of error message).
> - Run failed (with a shell error message like "segmentation
> violation" along with output produced up to that point)
> - Run succeeded (with program output)
>
>> 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".
>
> As far as I know, there is no rule that says that, given 3
> exact-size-match blocks that could satisfy a request, malloc()
> cannot choose one *randomly*.
Again, what malloc(3) does and what *my* allocator does are two
different issues, entirely. What they share is the fact that
they "effectively" return void *'s -- i.e., there's nothing
"there".
> There are some good security reasons
> to do that intentionally, although there are tradeoffs with speed
> which prefers to quit looking after you find one match.
>
>> 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.
>
> Most cases of "pointer manipulation" are not a test of a memory
> allocator.
Sure. But that doesn't mean you can't test them!
The problem lies in trying to do so portably -- without
writing a piece of code of comparable complexity to the
allocator itself!
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web