Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #18420 > unrolled thread

Regression testing for pointers

Back to article view | Back to comp.lang.c

Contents

  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 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#18735

Hi Bart,

On 3/13/2012 11:56 AM, BartC wrote:

>> When you're moving a few tons of material and "fail to stop"
> ...
>> OTOH, The fact that your dialog box didn't get redrawn on an
> ...
>> E.g., if I am driving a motorized mechanism "to the left",
> ...
>> But, it takes a perverse sort of mind to think about these
>> sorts of things. And, teaching others to think the same
>> way is difficult. I resort to having folks sit down and
>> list the ASSUMPTIONS they are making in any aspect of
>> design. Then, ask yourself which of those are *truly*
>> safe!
>
> If these sorts of things are typical of what you're testing, then perhaps
> you're not using the right language. C is not the safest language in the
> world. Perhaps you should be building a domain-specific language on top.

No, C is NOT the safest language in the world!  But, it
can do "almost anything" and is "widely known".  Imagine
having to craft a DSL for medical instrumentation.  Then,
a year later, another for gaming devices, or process control
equipment, or...

And, consider the folks who follow in your footsteps who
look at this "crazy language" that you've saddled them with.
(not to mention the cost of developing/maintaining tools, etc.)

DSL's tend to work best in domains where there *is* a "standard"
(i.e., you can find other souls that will know the language)
*and* that map closely to the constructs of the application
domain.

E.g., SQL works well for RDBMS's because the constructs that
it is designed to manipulate are directly visible in the
platform on which it executes (i.e., the DBMS!).  Writing
C to manipulate DBMS "tables" is clumsy -- because none
of the machinery that you need is readily available in the
language (though you can obviously *implement* it!)

>> E.g., if I have a "string" located at 0xFF...F8 that has
>> 8 non-NUL characters in it, what should strlen() return?
>
> If you pass strlen() a pointer to any random set of bytes, or any random
> pointer, or even just zero, then anything could happen. You don't even need
> to think up any tricky corner cases!

I trap on a NULL to strlen().  Chances are, this represents an
error in the caller's code.  Catching it *here* (where I know
it doesn't make any sense to be used) helps isolate errors
early, before they can propagate.

The case I illustrated, though, will choke most strlen's.
They will gladly keep incrementing the pointer and examining
sequential memory addresses *AS* the pointer wraps around
the end of memory.  Clearly (?) this is not what the developer
intends so it should trap instead of wandering around until it
stumbles on something that looks like a NUL.

> (And passing 0 to string functions tends to crash them. You might try
> writing a strlen() that is more robust, but the problem will still be
> having
> such low-level functions scattered through your code (plus now having a
> set of string functions that are super-slow because of all the extra
> checks.)

If you implement the tests *smartly*, there is just a constant
penalty (instead of a multiplier).  E.g.,

   ASSERT(ptr != NULL);

   start = ptr;
   while (*ptr != '\0')
      ptr++;

   ASSERT(ptr >= start);
   return ptr-start;

I.e., you don't have to check ptr each time you increment it.

You can also remove these sanity checks in production code.

[toc] | [prev] | [next] | [standalone]

#18563

On Sat, 2012-03-10, Don Y wrote:
> Hi Jorgen,
>
> On 3/10/2012 1:42 AM, Jorgen Grahn 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??)
>>>
>>> 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 the use of "TYPES of routines" (i.e., NOT "malloc")
>
>>> 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:
>
> See above.  And, the earlier comment regarding "functions
> (in general) that manipulate pointers.

I just went with your assumption that a malloc()/free() example would
be useful. (I have to admit I didn't understand the part about
manipulating 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*!

I just gave some rules for valid and invalid results above. Not *all*
rules, of course! You surely realize that it's not possible to prove
the correctness of a malloc() implementation this way.

Note that I'm not saying I would be satisfied with a test which only
uses the three rules above. It just seemed to me you believed there
was nothing you could do to test such a function, without a sort of
debugging interface into its internals.

...
>> 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 don't see the relation between what you write and what I wrote ...
but in the case of free() the specification allows anything to happen,
so in some sense you don't need to test this.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#18617

Hi Jorgen,

>>> - 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*!
>
> I just gave some rules for valid and invalid results above. Not *all*
> rules, of course! You surely realize that it's not possible to prove
> the correctness of a malloc() implementation this way.
>
> Note that I'm not saying I would be satisfied with a test which only
> uses the three rules above. It just seemed to me you believed there
> was nothing you could do to test such a function, without a sort of
> debugging interface into its internals.

Understood.  The point I was making was that it's not the same
sort of validation exercise as testing, e.g., sqrt() might be.

In a given/fixed/known environment, it is relatively easy to
implement lots of tests "safely".  The problem I am facing
here is wanting to make a "portable" test suite -- something
that is easily done with other types of functions but not
so readily with things that fiddle this close to the iron.

>>> 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 don't see the relation between what you write and what I wrote ...
> but in the case of free() the specification allows anything to happen,
> so in some sense you don't need to test this.

You don't need to test it for the "free()" in the standard
libraries.  Just let the OS throw a SIGSEGV when you do
something improper.  :>  (not my style!)

In my case, I need to ensure that myFree() catches conditions
that are indicative of errors in its implementation *or* in
its *use*.  Does this refer to memory managed in *this* heap?
Is the referenced piece of memory known (by the memory
management system) to be "in use" -- and thus a legitimate
target of free()?  Can the pointer legitimately reference a
real block of memory?  (imagine passing 0xFFFFFFFF to free())
etc.

E.g., if a free-d pointer already *appears* to be contained
in the free list (possibly *within* a free memory fragment),
is that an indication of an error on the programmer's part?
(free-ing something that was already free-d?)  Or, is it a
bug in the free() implementation (thinking something is free
that really *isn't*!)

[toc] | [prev] | [next] | [standalone]

#18565

On 03/10/12 10:19 PM, Don Y wrote:
>
> 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)

This appears to be the flaw in your understanding of unit tests.  You 
can nail down actual addresses.  Memory for malloc has to come from 
somewhere and in the tests, that somewhere is the test harness.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#18592

Hi Ian,

On 3/11/2012 5:39 PM, Ian Collins wrote:
> On 03/10/12 10:19 PM, Don Y wrote:
>>
>> 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)
>
> This appears to be the flaw in your understanding of unit tests. You can
> nail down actual addresses.

No.  You can only nail them down in specific environments.
I code on bare iron.  For me, I can put heap *anywhere*.
Indeed, I have to be able to do this else the operating
system won't be able to use memory as and where it wants to!

But, someone else operating on a different platform finds
my tests don't fit that platform.  E.g., I put the heap at
0x00001000 and that happens to be right in the middle
of your interrupt vector table.  Or, there is a bit of
hardware located there.  Or your device only has a 16b
address space.  Or...

Now *you* have to understand the intricacies of my routine
just to create (modify) a test suite that is equally
thorough.  You have to understand the alignment constraints
that your compiler imposes.  You have to know that the
portion of my test suite that addresses with very fine
grained (e.g., single byte) alignment won't port to your
environment (yet, I shouldn't omit it since there are
environments where this *is* permissible and it should
be verified).

I just don't see how this can be done, reliably -- short
of me writing code that actively reconfigures the tests
that it applies based on *its* observations of the
execution environment.

> Memory for malloc has to come from somewhere
> and in the tests, that somewhere is the test harness.

[toc] | [prev] | [next] | [standalone]

#18601

On 03/13/12 05:36 AM, Don Y wrote:
> Hi Ian,
>
> On 3/11/2012 5:39 PM, Ian Collins wrote:
>> On 03/10/12 10:19 PM, Don Y wrote:
>>>
>>> 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)
>>
>> This appears to be the flaw in your understanding of unit tests. You can
>> nail down actual addresses.
>
> No.  You can only nail them down in specific environments.
> I code on bare iron.  For me, I can put heap *anywhere*.
> Indeed, I have to be able to do this else the operating
> system won't be able to use memory as and where it wants to!
>
> But, someone else operating on a different platform finds
> my tests don't fit that platform.  E.g., I put the heap at
> 0x00001000 and that happens to be right in the middle
> of your interrupt vector table.  Or, there is a bit of
> hardware located there.  Or your device only has a 16b
> address space.  Or...

So you write your code to be position independent.  It isn't rocket science.

> Now *you* have to understand the intricacies of my routine
> just to create (modify) a test suite that is equally
> thorough.  You have to understand the alignment constraints
> that your compiler imposes.  You have to know that the
> portion of my test suite that addresses with very fine
> grained (e.g., single byte) alignment won't port to your
> environment (yet, I shouldn't omit it since there are
> environments where this *is* permissible and it should
> be verified).

Again, your code to be alignment independent.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#18616

Hi Ian,

On 3/12/2012 11:25 AM, Ian Collins wrote:

>>>> 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)
>>>
>>> This appears to be the flaw in your understanding of unit tests. You can
>>> nail down actual addresses.
>>
>> No. You can only nail them down in specific environments.
>> I code on bare iron. For me, I can put heap *anywhere*.
>> Indeed, I have to be able to do this else the operating
>> system won't be able to use memory as and where it wants to!
>>
>> But, someone else operating on a different platform finds
>> my tests don't fit that platform. E.g., I put the heap at
>> 0x00001000 and that happens to be right in the middle
>> of your interrupt vector table. Or, there is a bit of
>> hardware located there. Or your device only has a 16b
>> address space. Or...
>
> So you write your code to be position independent. It isn't rocket science.

We're talking about the TEST SUITE!  The code already *is* PIC!

I write the test suite.  It picks an address for "heap".
Works fine in *my* environment -- because I know I have RAM
there, etc.

*You* want to run the code on a different processor in
a different environment.  Gee, you *can't* put the heap
in that place because it's not "general purpose memory".

Now *you* have to modify the test suite and hopefully
not *break* it in the process!

You move the heap to 0xFFFFF000 -- since you have memory
there - and suddenly discover that the test suite's attempt
to allocate a 4K block of memory fails -- when it *shouldn't*
(there's nothing wrong with the code... the BUG is in your
test suite modification!)

>> Now *you* have to understand the intricacies of my routine
>> just to create (modify) a test suite that is equally
>> thorough. You have to understand the alignment constraints
>> that your compiler imposes. You have to know that the
>> portion of my test suite that addresses with very fine
>> grained (e.g., single byte) alignment won't port to your
>> environment (yet, I shouldn't omit it since there are
>> environments where this *is* permissible and it should
>> be verified).
>
> Again, your code to be alignment independent.

[toc] | [prev] | [next] | [standalone]

#18628

On 2012-03-12, Don Y <this@isnotme.com> wrote:
> *You* want to run the code on a different processor in
> a different environment.  Gee, you *can't* put the heap
> in that place because it's not "general purpose memory".
>
> Now *you* have to modify the test suite and hopefully
> not *break* it in the process!
>
> You move the heap to 0xFFFFF000 -- since you have memory
> there - and suddenly discover that the test suite's attempt
> to allocate a 4K block of memory fails -- when it *shouldn't*
> (there's nothing wrong with the code... the BUG is in your
> test suite modification!)

Yes. A regression test suite doesn't catch bugs in the code;
it catches changes of behavior in the test-suite-code combo.

If you fix a bug in the main code, that can cause tests to fail, tests
sometimes confirm that the bugs that were there yesterday are still
there today.

[toc] | [prev] | [next] | [standalone]

#18634

On 03/13/12 05:20 PM, Kaz Kylheku wrote:
> On 2012-03-12, Don Y<this@isnotme.com>  wrote:
>> *You* want to run the code on a different processor in
>> a different environment.  Gee, you *can't* put the heap
>> in that place because it's not "general purpose memory".
>>
>> Now *you* have to modify the test suite and hopefully
>> not *break* it in the process!
>>
>> You move the heap to 0xFFFFF000 -- since you have memory
>> there - and suddenly discover that the test suite's attempt
>> to allocate a 4K block of memory fails -- when it *shouldn't*
>> (there's nothing wrong with the code... the BUG is in your
>> test suite modification!)
>
> Yes. A regression test suite doesn't catch bugs in the code;
> it catches changes of behavior in the test-suite-code combo.
>
> If you fix a bug in the main code, that can cause tests to fail, tests
> sometimes confirm that the bugs that were there yesterday are still
> there today.

Very true.  The first step in fixing a bug should be to add a new 
failing test to show the bug is there.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#18644

On 3/12/2012 9:20 PM, Kaz Kylheku wrote:
> On 2012-03-12, Don Y<this@isnotme.com>  wrote:
>> *You* want to run the code on a different processor in
>> a different environment.  Gee, you *can't* put the heap
>> in that place because it's not "general purpose memory".
>>
>> Now *you* have to modify the test suite and hopefully
>> not *break* it in the process!
>>
>> You move the heap to 0xFFFFF000 -- since you have memory
>> there - and suddenly discover that the test suite's attempt
>> to allocate a 4K block of memory fails -- when it *shouldn't*
>> (there's nothing wrong with the code... the BUG is in your
>> test suite modification!)
>
> Yes. A regression test suite doesn't catch bugs in the code;
> it catches changes of behavior in the test-suite-code combo.

Yes.  Hence the reason you want the test suite to be "of
impeccable quality".  If your test suite becomes to complex,
then you risk introducing apparent -- *or* masking actual --
errors in the code.

If you require others to *modify* your test suite to make *it*
work ("operate") in their environment, then you've added another
potential source of error/unreliability.

> If you fix a bug in the main code, that can cause tests to fail, tests
> sometimes confirm that the bugs that were there yesterday are still
> there today.

Sure!  But, more often than not, it tells you that you had
a problem in your test suite.  Something that you *thought*
you were testing for but actually weren't.

The beauty of a formal test suite is that you can "easily"
reapply the new test suite to the *old* code base and
determine if the test suite was defective, the code base
or *both*.

[toc] | [prev] | [next] | [standalone]

#18632

On 03/13/12 12:28 PM, Don Y wrote:
> Hi Ian,
>
> On 3/12/2012 11:25 AM, Ian Collins wrote:
>
>>>>> 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)
>>>>
>>>> This appears to be the flaw in your understanding of unit tests. You can
>>>> nail down actual addresses.
>>>
>>> No. You can only nail them down in specific environments.
>>> I code on bare iron. For me, I can put heap *anywhere*.
>>> Indeed, I have to be able to do this else the operating
>>> system won't be able to use memory as and where it wants to!
>>>
>>> But, someone else operating on a different platform finds
>>> my tests don't fit that platform. E.g., I put the heap at
>>> 0x00001000 and that happens to be right in the middle
>>> of your interrupt vector table. Or, there is a bit of
>>> hardware located there. Or your device only has a 16b
>>> address space. Or...
>>
>> So you write your code to be position independent. It isn't rocket science.
>
> We're talking about the TEST SUITE!  The code already *is* PIC!

As was the example test suite I posted.

> I write the test suite.  It picks an address for "heap".
> Works fine in *my* environment -- because I know I have RAM
> there, etc.

No *you* don, the compiler/linker does.  The test suite does not make 
any assumptions about the memory heap location.

> *You* want to run the code on a different processor in
> a different environment.  Gee, you *can't* put the heap
> in that place because it's not "general purpose memory".

Good, because I didn't try.  The compiler/linker on the new system will 
do that for me.

> Now *you* have to modify the test suite and hopefully
> not *break* it in the process!

No, I don't.

> You move the heap to 0xFFFFF000 -- since you have memory
> there - and suddenly discover that the test suite's attempt
> to allocate a 4K block of memory fails -- when it *shouldn't*
> (there's nothing wrong with the code... the BUG is in your
> test suite modification!)

Nope, show me where I specified the location of the heap (other than 
heap = new uint8_t[heapSize]; heapBase = heap;).

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#18648

On 3/12/2012 9:31 PM, Ian Collins wrote:
> On 03/13/12 12:28 PM, Don Y wrote:
>> Hi Ian,
>>
>> On 3/12/2012 11:25 AM, Ian Collins wrote:
>>
>>>>>> 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)
>>>>>
>>>>> This appears to be the flaw in your understanding of unit tests.
>>>>> You can
>>>>> nail down actual addresses.
>>>>
>>>> No. You can only nail them down in specific environments.
>>>> I code on bare iron. For me, I can put heap *anywhere*.
>>>> Indeed, I have to be able to do this else the operating
>>>> system won't be able to use memory as and where it wants to!
>>>>
>>>> But, someone else operating on a different platform finds
>>>> my tests don't fit that platform. E.g., I put the heap at
>>>> 0x00001000 and that happens to be right in the middle
>>>> of your interrupt vector table. Or, there is a bit of
>>>> hardware located there. Or your device only has a 16b
>>>> address space. Or...
>>>
>>> So you write your code to be position independent. It isn't rocket
>>> science.
>>
>> We're talking about the TEST SUITE! The code already *is* PIC!
>
> As was the example test suite I posted.
>
>> I write the test suite. It picks an address for "heap".
>> Works fine in *my* environment -- because I know I have RAM
>> there, etc.
>
> No *you* don, the compiler/linker does. The test suite does not make any
> assumptions about the memory heap location.

And, because of that, *you* can't run the entire test suite.

*Pick* a number.  Pretend you are the compiler.  Write it on
a little slip of paper.  Don't show it to me.

Is it 0x27000010?  Is it 0xF9880400?  Is it something ELSE??
For *any* two of those cases, it's *wrong*.  The code doesn't
expect to deal with a heap in a certain place in memory.
It doesn't expect the heaps size to be artificially constrained.
It has to address all possible deployments... different
size pointers, size_t's, etc.

Do you have 4GB of VM in the machine?  Can you allocate a
4GB chunk of memory?  What will your 32b system do when you
try?  Is there a bug in the code that treats allocation sizes
as *signed* (so 2G is the max)?  What if you're operating
on a 64b platform?

Do you only test conditions that you *use*?
   "All of my strings are 30 characters or less so I only need
   to test strlen for results of [0..30]"
   "I never use numbers larger than 999999 so as long as sqrt
   works for that range of values..."
   "Because the linker located my heap at 0xC000, I can never
   allocate a chunk larger than 16KB so..."

>> *You* want to run the code on a different processor in
>> a different environment. Gee, you *can't* put the heap
>> in that place because it's not "general purpose memory".
>
> Good, because I didn't try. The compiler/linker on the new system will
> do that for me.

So, you live with whatever conditions the linker wants to
impose on the code?  Examine any parts of the test suite that
throw errors and rationalize which ones "need not pass"
based on the choice the linkage editor made for you?

A test suite should address the operation of the function(s)
that it purports to test -- over the entire expected range of
operation.  I.e., sqrt should "work" for all doubles -- even
the ones that you don't use in your application.

>> Now *you* have to modify the test suite and hopefully
>> not *break* it in the process!
>
> No, I don't.
>
>> You move the heap to 0xFFFFF000 -- since you have memory
>> there - and suddenly discover that the test suite's attempt
>> to allocate a 4K block of memory fails -- when it *shouldn't*
>> (there's nothing wrong with the code... the BUG is in your
>> test suite modification!)
>
> Nope, show me where I specified the location of the heap (other than
> heap = new uint8_t[heapSize]; heapBase = heap;).

[toc] | [prev] | [next] | [standalone]

#18653

On 03/13/12 09:05 PM, Don Y wrote:
> On 3/12/2012 9:31 PM, Ian Collins wrote:
>> On 03/13/12 12:28 PM, Don Y wrote:
>>> Hi Ian,
>>>
>>> On 3/12/2012 11:25 AM, Ian Collins wrote:
>>>>
>>>> So you write your code to be position independent. It isn't rocket
>>>> science.
>>>
>>> We're talking about the TEST SUITE! The code already *is* PIC!
>>
>> As was the example test suite I posted.
>>
>>> I write the test suite. It picks an address for "heap".
>>> Works fine in *my* environment -- because I know I have RAM
>>> there, etc.
>>
>> No *you* don, the compiler/linker does. The test suite does not make any
>> assumptions about the memory heap location.
>
> And, because of that, *you* can't run the entire test suite.

It hasn't stopped me in the past and I have quite a few (embedded) 
allocators and (hosted) test suites.

>>> *You* want to run the code on a different processor in
>>> a different environment. Gee, you *can't* put the heap
>>> in that place because it's not "general purpose memory".
>>
>> Good, because I didn't try. The compiler/linker on the new system will
>> do that for me.
>
> So, you live with whatever conditions the linker wants to
> impose on the code?  Examine any parts of the test suite that
> throw errors and rationalize which ones "need not pass"
> based on the choice the linkage editor made for you?

No.  I don't make assumptions about values.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#18683

Hi Ian,

On 3/13/2012 1:30 AM, Ian Collins wrote:

>>>> I write the test suite. It picks an address for "heap".
>>>> Works fine in *my* environment -- because I know I have RAM
>>>> there, etc.
>>>
>>> No *you* don, the compiler/linker does. The test suite does not make any
>>> assumptions about the memory heap location.
>>
>> And, because of that, *you* can't run the entire test suite.
>
> It hasn't stopped me in the past and I have quite a few (embedded)
> allocators and (hosted) test suites.

And apparently have never considered someone else deploying
it in an UNCONSTRAINED manner (i.e., observing ONLY the
constraints that you have PUBLISHED for it).

Or, operated in a vanilla, "UMA-esque" environment.

>>>> *You* want to run the code on a different processor in
>>>> a different environment. Gee, you *can't* put the heap
>>>> in that place because it's not "general purpose memory".
>>>
>>> Good, because I didn't try. The compiler/linker on the new system will
>>> do that for me.
>>
>> So, you live with whatever conditions the linker wants to
>> impose on the code? Examine any parts of the test suite that
>> throw errors and rationalize which ones "need not pass"
>> based on the choice the linkage editor made for you?
>
> No. I don't make assumptions about values.

And you quite obviously don't test in all the dark corners!
(since you can't *force* the function to operate in those
places without exercising control over the input conditions!)

*When* your heap ends up at 0xFFFFFFFF, *will* the code
work?  Will it *know* that the address space "ends" at
that single byte?  Will your pointer arithmetic just
silently wrap around and start treating "low memory"
(i.e., at 0x00000000) as the *real* part of the heap?

How will you know how your code behaves in that case?
How will you PROVE it to others?

Or, will you just wait until "fate" causes your heap
to move into some "risky place" that you hadn't
anticipated or accurately protected against in your
implementation?

Will your defense, in that situation, be "Well, you're
not supposed to put the heap *there*!"?  Vaguely
reminiscent of folks complaining when users do things
they "aren't supposed to do"...?

I've watched all sorts of "portable" code fail because
of assumptions that the developers never made explicit.
Move the heap to 0x80000000 and suddenly nothing works!
("Ah, 0x80000000 looks like a 'negative' long and your
pointer math thinks of everything as unsigned...")
Pointers wrapping around the end (or *start*) of
memory, etc.

If you want to make assumptions, fine.  But then you have
to put them in the contract so everyone else knows what
the rules are:  "Don't try to use this allocator on a
64 bit machine because it can't handle chunks larger
than 4G (2G?)"  "Don't use this allocator with heaps
that abut the end of memory because the pointer arithmetic
doesn't check for overflow/wraparound".

I prefer handling all cases -- and being able to *validate*
that compliance.

[toc] | [prev] | [next] | [standalone]

#18498

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

[toc] | [prev] | [next] | [standalone]

#18542

Hi Malcolm,

On 3/10/2012 4:41 PM, Malcolm McLean wrote:
> On Mar 9, 11:43 pm, Don Y<t...@isnotme.com>  wrote:
>>
>> I.e., I can't come up with "constant" results against
>> which to compare test-time results.  Sticking with the
>> traditional malloc/free for example (my routines are
>> more heavily parameterized), I can create a malloc.test
>> that pushes size_t's to malloc.  But, aside from verifying
>> the result is not NULL (or, *is* NULL, in some cases!),
>> there's nothing I can do to check that the result is
>> actually correct!
>
> malloc() should be considered a special case. Really it's an IO
> function, but the IO is to the heap.

Why would you consider this different than a function that
manipulates a doubly linked list?  (a pure function in your
lexicon)

> You verify that an IO function
> works correctly be seeing that the attached hardware operates as
> expected (or a dummy device gets the bits if you're testing nukes or
> something). You verify that malloc() works by seeing that the heap
> changes as you want it to. But you can't actually see the heap,
> because it's a static array in the mymalloc() function.

But you really only care that the results malloc() returns to
you are consistent with its design specifications.

E.g., how would this testing differ from enqueue()/dequeue()
functions?  You don't go poking around ALL of memory verifying
that enqueue and dequeue haven't, accidentally, twiddled
something that they shouldn't have...?

> For instance if malloc() returns two pointers to the same block of
> memory, that would be very hard to catch in a black box test.

Actually, that sort of thing is easy to check for.
In theory, you not only want to test that the pointers
never coincide but that a pointer doesn't reference a
location *inside* another (previously allocated) block
*or* outside the configured range of the heap.  E.g.,
my "releaseMemory()" verifies that the "chunk" that
is passed to it resides *in* the heap that is selected,
is not present in the free list *and* "makes sense"
in the context of those constraints.

*If* you know the details of the execution environment,
then you can easily create a test scenario where every
option of the allocator is observable -- much the
same way that you *know* 2+3==5.

E.g., if the heap resides at 0x80000000 and has a size of
0x1000, is initially "full" (i.e., I just created it!)
then a request for 0x20 bytes chosen from the *tail*
of the free list using a "best fit" strategy, trimming
the allocation to the specified size with an alignment
granularity of 0x80 will yield the value 0x80000F80.
A subsequent allocation request without the alignment
constraint will yield 0x800000E0 while one addition
request for 0x100 bytes with no alignment constraints
would yield 0x80000E80.  These can be determined from the
specification of the function's operation.

These are predictable and invariant -- in *this* test
environment.  The problem is the "constants" will
vary when the platform, heap location, etc. vary.

[toc] | [prev] | [next] | [standalone]

#18696

בתאריך יום ראשון, 11 במרס 2012 18:23:39 UTC, מאת Don Y:
> > > malloc() should be considered a special case. Really it's an IO
> > function, but the IO is to the heap.
> 
> Why would you consider this different than a function that
> manipulates a doubly linked list?  (a pure function in your
> lexicon)
> 
Because we construct the linked list it manipulates outside the function, then we get it back. So we can pass an empty list, a single node, a double node, a triple node, and a 4 node list. We can then, usually, easily verify whether the linked list has been correctly manipulated. We know the addresses of the nodes, what data they contain, etc. We might also want to try with a very long list to test out performance constraints. If the linked list routine passes all of those cases, it's very likely that it passes all case, unless there's a error in memory allocation (memory not being freed, less usually nodes not properly allocated). That's why malloc() is a special case.

[toc] | [prev] | [next] | [standalone]

#18755

Hi Malcolm,

On 3/13/2012 1:43 PM, Malcolm McLean wrote:
> בתאריך יום ראשון, 11 במרס 2012 18:23:39 UTC, מאת Don Y:
>>>> malloc() should be considered a special case. Really it's an IO
>>> function, but the IO is to the heap.
>>
>> Why would you consider this different than a function that
>> manipulates a doubly linked list?  (a pure function in your
>> lexicon)
>>
> Because we construct the linked list it manipulates outside the
> function, then we get it back.

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.

(?)

So, in your case, strlen() is a pure function but memset()
and any math.h functions that modify errno would NOT be?

With this distinction, pure functions are easy to test
because you just look at the return value...

> So we can pass an empty list, a single node, a double node, a
> triple node, and a 4 node list. We can then, usually, easily
> verify whether the linked list has been correctly manipulated.

I am intentionally avoiding that.  I believe that I can
*deduce* what the hidden state (i.e., free list) must be
just by throwing carefully selected examples at the
functions and watching their results (assuming I know
or can control the initial conditions/state)

For example, if the heap occupies [7000.,8000.], is currently
"full" and supports byte alignment (one less issue to address
in this example), then a request for:
    allocate(100., FIRSTFIT, PICKBACK, TRIMTOFIT)
*will* return a pointer to 7900. (decimal, for example) and a
chunk that is 100 bytes long.

[find the FIRST fragment in the free list that is big enough
to handle the request; use the "end" (highest address) of that
fragment to satisfy the request; trim the fragment to the
requested size, returning the excess to the free list]

At this point, we *know* the free list (should) contain a single
fragment located at 7000. having a size of 900.

A subsequent request for:
    allocate(50., FIRSTFIT, PICKFRONT, TRIMTOFIT)
*will* return a pointer to 7000. and a chunk that is 50 bytes
long.

[same explanation as above EXCEPT use the "start" of the selected
fragment to supply the memory to the caller]

The free list should have a single fragment at 7050. of size 850.

We can then choose to release the first chunk with:
     release(ptr, ATHEAD, NOCOALESCE)

At this point, we *know* there are two fragments in the
free list -- one at 7900. of size 100. and the *second*
at 7050. of size 850.

A request for <= 100 bytes "ATHEAD" should yield some
portion of that first fragment (at 7900 -- depending on
whether you PICKFRONT or PICKBACK)

A request for > 100 bytes (but <= 850) "ATHEAD" should
yield some portion of that *second* fragment.

A request for <= 850 bytes "ATTAIL" would yield some
portion of the second fragment.

A request for 99 bytes "EXACTFIT" would skip over that
first fragment (because it can't be trimmed to the
exact size specified -- the single remaining byte would
be too small for MINFRAGSIZE) and select the second
fragment, instead.

If the release had been
     release(ptr, INORDER, COALESCE)
then the chunk would have been inserted into the free list
based on its starting address wrt the starting addresses
of the other fragments in the free list.  I.e., this
would have caused it to be placed *after* the 850 byte
fragment at 7050 (through 7899).  The system would
then merge (COALESCE) the two adjacent free fragments into
a single 950 byte fragment at 7050.

I.e., unlike malloc that gives you what *it* wants (and
about all you can count on is that it is at least as big
as requested!), this allocator lets you *predict* how it
will satisfy your request.

Since you (the developer) know how you are going to *use*
that particular heap, you can select policies that give
you the best overall performance.  E.g., if you are
allocating memory for a layered menu system (each new
layer displayed atop the previous), then you would
want to treat the heap as a LIFO buffer (no "fragmentation"
possible!  You get to use ALL of the heap without
worrying that some combination of allocates and releases
has turned the heap into swiss cheese!)

> We know the addresses of the nodes, what data they contain,
> etc. We might also want to try with a very long list to test
> out performance constraints. If the linked list routine passes
> all of those cases, it's very likely that it passes all case,
> unless there's a error in memory allocation (memory not being
> freed, less usually nodes not properly allocated).

I believe I am doing just that -- though indirectly
and more economically.  By looking at the returned
pointers and knowing how (unlike malloc!) the memory
subsystem operates, I can assure myself that the
algorithms hidden within are acting as expected.
*Just* by checking one pointer for each test invocation!

> That's why malloc() is a special case.

[toc] | [prev] | [next] | [standalone]

#18784

בתאריך יום רביעי, 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.) 

A pure function changes the dta passed to it, but nothing else. 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.
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. But it does make malloc() a special function.

-- 
Basic Algorithms - fast allocators, and how to implement your own malloc()
http://www.malcolmmclean.site11.com/www

[toc] | [prev] | [next] | [standalone]

#18785

On 2012-03-14, Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:
> A pure function changes the dta passed to it, but nothing else. That means
> that, strictly, it can't call malloc(). 

Yeah, sure, and strictly, it can't move the instruction pointer, either,
because that is imperative.

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.

Implementations of anything pure depend on the acceptance of certain impurities
which are managed and hidden away so that they don't interact with the
implementation of the pure formalism.

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web