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 | 10 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 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2012-03-15 13:10 -0700 |
| Message-ID | <6706525.36.1331842255566.JavaMail.geo-discussion-forums@ynej9> |
| In reply to | #18785 |
בתאריך יום רביעי, 14 במרס 2012 22:57:11 UTC, מאת Kaz Kylheku: > > What crap! Pure functions in pure functional languages allocate memory. E.g. > mapping a list to a different list. The different list has to come from > somewhere. > You need to learn to express yourself in a more cultured manner. Not everyone who disagrees with you is talking crap, and even if they are, often it's better not to say it. We implement median(const double *x, int N) inthe obvious way, by copying to a temporary and sorting. So if we run out of memory, what do we do? Returning nan would seem a reasonable idea. So median will sometimes return the mid point of x, sometimes nan, for identical values of x. So it's not, strictly, a pure function of x. It's a pure function of x and th state of the memory allocator. For indetical x and identical states of the free list, it will always return the same result. However it's not easy to peep into the memory allocator, nor is it usually useful to do so. It does mean that we're treating the memory allocation system as something special. But that's reasonable. It's the infinite tape in our Turing machine. -- MiniBasic - how to write a script interpreter http://www.malcolmmclean.site11.com/www
[toc] | [prev] | [next] | [standalone]
| From | jgk@panix.com (Joe keane) |
|---|---|
| Date | 2012-03-16 22:20 +0000 |
| Message-ID | <jk0ebq$3d0$1@reader1.panix.com> |
| In reply to | #18809 |
In article <6706525.36.1331842255566.JavaMail.geo-discussion-forums@ynej9>, Malcolm McLean <malcolm.mclean5@btinternet.com> wrote: >You need to learn to express yourself in a more cultured manner. Not >everyone who disagrees with you is talking crap, and even if they are, >often it's better not to say it. 'if you don't have anything nice to say' then you're a jerk
[toc] | [prev] | [next] | [standalone]
| From | "io_x" <a@b.c.invalid> |
|---|---|
| Date | 2012-03-18 07:15 +0100 |
| Message-ID | <4f657c63$0$1381$4fafbaef@reader1.news.tin.it> |
| In reply to | #18809 |
"Malcolm McLean" <malcolm.mclean5@btinternet.com> ha scritto nel messaggio news:6706525.36.1331842255566.JavaMail.geo-discussion-forums@ynej9... ?????? ??? ?????, 14 ???? 2012 22:57:11 UTC, ??? Kaz Kylheku: > > What crap! Pure functions in pure functional languages allocate memory. E.g. > mapping a list to a different list. The different list has to come from > somewhere. > You need to learn to express yourself in a more cultured manner. Not everyone who disagrees with you is talking crap, and even if they are, often it's better not to say it. We implement median(const double *x, int N) inthe obvious way, by copying to a temporary and sorting. So if we run out of memory, what do we do? Returning nan would seem a reasonable idea. So median will sometimes return the mid point of x, sometimes nan, for identical values of x. So it's not, strictly, a pure function of x. It's a pure function of x and th state of the memory allocator. #it is not only memory allocator, even the state of all the OS ... #what about if one virus-thread write in the data the function use... #sometime somewhere someone said that a beam change the value of a memory #location: this can produce one not right result ... #so even if all is ok the result could be wrong... #100% secure not exist For indetical x and identical states of the free list, it will always return the same result. However it's not easy to peep into the memory allocator, nor is it usually useful to do so. It does mean that we're treating the memory allocation system as something special. But that's reasonable. It's the infinite tape in our Turing machine. -- MiniBasic - how to write a script interpreter http://www.malcolmmclean.site11.com/www
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-14 23:13 -0700 |
| Message-ID | <jjs1a5$9kv$1@speranza.aioe.org> |
| In reply to | #18784 |
Hi Malcolm, On 3/14/2012 3:15 PM, Malcolm McLean wrote: > בתאריך יום רביעי, 14 במרס 2012 08:45:26 UTC, מאת Don Y: >> Oh, I think I see the distinction you are making. To you, >> a "pure function" can have no side effects. It takes >> inputs using call by value semantics and returns a result >> maintaining no internal state in the process. > > A function is a mapping of input to output. A procedure is is a > sequence of actions. Unfortunately these terms are in use to refer > to void fucntions and those that return values. This distinction > is important for the grammar of the language (if(foo()) is illegal > if foo is a void fucntion, legal if it return a value), but not > from a softwar eengineering perspective (rewrite int foo(void) as > void foo(int *answer) and you're not really changing anything.) Do you consider the alteration of *answer to have changed the nature of foo? > A pure function changes the dta passed to it, but nothing else. In that case, my allocateMemory is a pure function. It only changes the data passed to it: a heap_t (and some constants). > That means that, strictly, it can't call malloc(). Even if it just > allocates a temporary buffer and frees it, that may change the state > of the heap and cause the next call to malloc() to return null when > it otherwise wouldn't have done, so not a pure function. Understood. > But that requirement means that a large number of functions either > have to be declared non-pure, or they have to use fixed buffers and > return buffer exceeded errors. That's not really useful. So it's > better to divide your functions into those that do IO and those > that don't. That's the best palce to do the division. Then, again, does allocateMemory(heap_t theHeap, ...) represent a procedure doing I/O? When the only thing that changes is theHeap? > But it does make malloc() a special function. Because malloc implicitly relies on a "global" object (the heap)?
[toc] | [prev] | [next] | [standalone]
| From | gordonb.b29ri@burditt.org (Gordon Burditt) |
|---|---|
| Date | 2012-03-12 19:37 -0500 |
| Message-ID | <UaOdnXvsapxVC8PSnZ2dnUVZ_t2dnZ2d@posted.internetamerica> |
| In reply to | #18420 |
> 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. 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). > > 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 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. > 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. > 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*. 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.
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-12 19:23 -0700 |
| Message-ID | <jjmb2l$klf$1@speranza.aioe.org> |
| In reply to | #18622 |
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!
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-14 13:12 +1300 |
| Message-ID | <9sa63cF8igU3@mid.individual.net> |
| In reply to | #18420 |
On 03/10/12 12:43 PM, Don Y wrote: > 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.] With the hindsight gained from a few days of posts, one simple and obvious solution is to consider your allocator as a normal function that returns predetermined values. Not pointers to usable memory, just values. You can then writes your tests to test for your expected values. Just don't try and dereference the values! -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-14 01:54 -0700 |
| Message-ID | <jjpmbg$8g3$1@speranza.aioe.org> |
| In reply to | #18737 |
Hi Ian, On 3/13/2012 5:12 PM, Ian Collins wrote: > On 03/10/12 12:43 PM, Don Y wrote: >> [Recall, the location and size of the free store might change >> from environment to environment; alignment constraints might >> vary, etc.] > > With the hindsight gained from a few days of posts, one simple and > obvious solution is to consider your allocator as a normal function that > returns predetermined values. Not pointers to usable memory, just values. Exactly! The allocator just manipulates "funny integers". The relationships between those integers are determined by the initial conditions and the parameters passed to each (successive) function invocation. I don't *care* what's *at* that "address" -- that's *inside* a newly allocated chunk of memory (and not specified by the allocator). > You can then writes your tests to test for your expected values. Just > don't try and dereference the values! But, I am still stuck with dealing with a portable way of testing this. I can *treat* the values returned as just "values". But, the *allocator* gives them additional meaning when it is looking at them. E.g., it *does* dereference pointers to walk the free list, etc. So, 0x27 could be a "number" to a test harness -- but 0x27 is an *address* to the allocator (and must be accessible) <frown> I am beginning to think that a portable test is just not possible. The same sorts of issues come up (in spades!) in the validation of the RTOS, drivers, etc. It might be more prudent to just release the documentation for the API's and tell folks to write their own <whatever> to meet the stated goals. And just concentrate on keeping the "application" layer portable. [After all, if you don't understand the hardware well enough to write these mechanisms, you shouldn't be *porting* it!]
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-14 22:05 +1300 |
| Message-ID | <9sb5b4F8igU6@mid.individual.net> |
| In reply to | #18756 |
On 03/14/12 09:54 PM, Don Y wrote: > Hi Ian, > > On 3/13/2012 5:12 PM, Ian Collins wrote: >> On 03/10/12 12:43 PM, Don Y wrote: > >>> [Recall, the location and size of the free store might change >>> from environment to environment; alignment constraints might >>> vary, etc.] >> >> With the hindsight gained from a few days of posts, one simple and >> obvious solution is to consider your allocator as a normal function that >> returns predetermined values. Not pointers to usable memory, just values. > > Exactly! The allocator just manipulates "funny integers". > The relationships between those integers are determined > by the initial conditions and the parameters passed to > each (successive) function invocation. > > I don't *care* what's *at* that "address" -- that's > *inside* a newly allocated chunk of memory (and not > specified by the allocator). > >> You can then writes your tests to test for your expected values. Just >> don't try and dereference the values! > > But, I am still stuck with dealing with a portable way of > testing this. > > I can *treat* the values returned as just "values". > But, the *allocator* gives them additional meaning > when it is looking at them. E.g., it *does* dereference > pointers to walk the free list, etc. So, 0x27 could > be a "number" to a test harness -- but 0x27 is an > *address* to the allocator (and must be accessible) Do the housekeeping in a different address space than the "heap". For example your free list entries could be static, or in memory allocated and used internally by the allocator. > <frown> I am beginning to think that a portable test is just > not possible. The same sorts of issues come up (in spades!) in > the validation of the RTOS, drivers, etc. It might be more > prudent to just release the documentation for the API's and > tell folks to write their own<whatever> to meet the stated > goals. And just concentrate on keeping the "application" > layer portable. > > [After all, if you don't understand the hardware well enough > to write these mechanisms, you shouldn't be *porting* it!] All it takes is a bit of imagination! Most of what I do is embedded and all the code I write has extensive (hosted) tests because I write test first. If you code test first, your code must be written in a test friendly style. The problems come when you try and bolt the tests on after the fact. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-14 11:54 -0700 |
| Message-ID | <jjqpgp$62n$1@speranza.aioe.org> |
| In reply to | #18759 |
Hi Ian, On 3/14/2012 2:05 AM, Ian Collins wrote: >> But, I am still stuck with dealing with a portable way of >> testing this. >> >> I can *treat* the values returned as just "values". >> But, the *allocator* gives them additional meaning >> when it is looking at them. E.g., it *does* dereference >> pointers to walk the free list, etc. So, 0x27 could >> be a "number" to a test harness -- but 0x27 is an >> *address* to the allocator (and must be accessible) > > Do the housekeeping in a different address space than the "heap". For > example your free list entries could be static, or in memory allocated > and used internally by the allocator. Then I end up having "free" memory sitting idle while also having to set aside *other* memory to track where the free memory is located! You can conceivably have HEAPSIZE/MINFRAGSIZE (note that HEAPSIZE might not be a manifest constant) fragments in your free list. This could require OVERHEADPERFRAG*(HEAPSIZE/MINFRAGSIZE) bytes to track/manage. If, instead, you ensure OVERHEADPERFRAG <= MINFRAGSIZE, then each fragment can contain its own "overhead" and not require additional resources beyond those already set aside *as* "The Heap". (only free fragments need to track their overhead) >> <frown> I am beginning to think that a portable test is just >> not possible. The same sorts of issues come up (in spades!) in >> the validation of the RTOS, drivers, etc. It might be more >> prudent to just release the documentation for the API's and >> tell folks to write their own<whatever> to meet the stated >> goals. And just concentrate on keeping the "application" >> layer portable. >> >> [After all, if you don't understand the hardware well enough >> to write these mechanisms, you shouldn't be *porting* it!] > > All it takes is a bit of imagination! > > Most of what I do is embedded and all the code I write has extensive > (hosted) tests because I write test first. If you code test first, your > code must be written in a test friendly style. The problems come when > you try and bolt the tests on after the fact. I know what the test cases need to be before I write the code (having the specification in hand). I further refine those test cases as I develop the implementation -- because I see specific "conditionals" that I need to make sure the test will exercise for full coverage. The commentary in the code will literally say something like: "guard against fragment claiming a size that would have it extend beyond the end of the address space" (i.e., a >=17 byte fragment at 0xFFFFFFF0) I write the bulk of the code's framework on a PC as that lets me cut and paste from the specification into the code body (the tools I use for the specification don't run anywhere other than Windows). This lets me transfer the spirit of the individual tests required into the code base (i.e., verify a fragment doesn't infer its ending address extends beyond the end of memory -- regardless of where that might be on this particular platform) Then, I make an intial pass at debugging portions of the code using a PC-based IDE (lately, borland's). Here, I'm just trying to get the "cruft" out of the code... typos, consistent declarations, etc. Then, I move to one of the BSD boxes where I am more comfortable "working". By the time I finish, there, the code is, IMO, ready for testing. (note that the compiler here is different as well as the hardware targeted than the borland/pc effort) Then, back to the PC and deployment under an ICE or emulator. I.e., are there any portability issues in the *code* that the target compiler tickles? (the BSD environments are big *and* little endian, different alignment requirements, etc. so I can see how code *really* adapts to those differences) And, ultimately, does it work in the environment for which it is *targeted*? Can I put the heap at 0xFFFF0000 and get it to behave properly? *Will* the code check itself for insane operating conditions as it is supposed to? etc.
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.lang.c
csiph-web