Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Don Y <this@isnotme.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Regression testing for pointers |
| Date | 2012-03-14 11:32 -0700 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <jjqo7o$2na$1@speranza.aioe.org> (permalink) |
| References | (15 earlier) <9s8ee6FhvvU6@mid.individual.net> <jjnvii$e7d$1@speranza.aioe.org> <9s9hpbF8igU1@mid.individual.net> <jjpmn4$9j0$1@speranza.aioe.org> <9sb634F8igU7@mid.individual.net> |
Hi Ian, On 3/14/2012 2:18 AM, Ian Collins wrote: > On 03/14/12 10:00 PM, Don Y wrote: >> On 3/13/2012 11:25 AM, Ian Collins wrote: >>> On 03/14/12 06:19 AM, Don Y wrote: >>>>>>> Your typical memory allocator is a little more complex and less >>>>>>> deterministic than strchr(). >>>>>> >>>>>> But it still produces *a* result. It is a deterministic >>>>>> algorithm (even if the specification -- like malloc -- doesn't >>>>>> make that determinism explicit). With a given set of operating >>>>>> conditions and inputs, you **KNOW** what the result will be. >>>>>> TEST FOR THAT RESULT! >>>>> >>>>> It may produce a result, but more often than not, the exact value >>>>> is of >>>>> little on no consequence. >>>> >>>> Is the exact value of sqrt()'s result of no consequence? >>> >>> Now I think you are being deliberately obtuse. You were talking about >>> malloc, not sqrt. >> >> My point was, "What makes malloc's result 'of little or no >> consequence' while sqrt's *is* consequential?" > > Because of the way the function is specified. You pass 4 to sqrt, it > must return 2. You ask malloc for 4 bytes, it can give return a pointer > to any correctly aligned bit of memory. That's malloc(3)'s contract; not allocateMemory()'s! :> >>>>> If you start to test for specific values based >>>>> on knowledge of the internals, you end up with a very fragile test >>>> >>>> No! I am *not* looking at test internals. I am looking at >>>> the SPECIFIED, CONTRACTUAL BEHAVIOR of the function. >>> >>> Then I guess the root cause of this debate is that your function is over >>> specified. >> >> No. It specifies exactly as much as is needed to allow the >> developer to direct and predict its operation. I can >> wrap it in a macro and turn it into any number of different >> "malloc(3)" implementations -- by *removing* that flexibility >> from the developer. > > Isn't the point of the specification of a function like malloc to give > the implementer the freedom to design the internals to meet a specific The specification just ensures that implementor and "user" agree on what functionality will be provided and the semantics for invocation, etc. Within those constraints, the implementor is free to do as he chooses. And, to *change* that "on a whim" (to meet some arbitrary criteria that <someone> deems appropriate). You can't get deterministic (predictable -- esp temporally) behavior from something that is free to produce resuts however it chooses! E.g., (some implementation of) malloc(3) could satisfy all requests with (increments of) 4KB blocks of memory and still conform to the interface specification. If your heap is only 8K, you might not be real happy with that! :> The application knows more about how it will be *using* memory than the memory management system does. And, if it knows it can influence *how* memory is allocated, then it can *really* think about how it wants to use memory as it realizes that this knowledge can improve performance. E.g., if I need 100 bytes of memory and then want 200 more (for some other reason), it would be smarter for that second allocation request to be satisfied "close to" (in terms of actual memory addresses) that first one -- if I am operating in a VM environment! Otherwise, the first allocation requires a physical memory page to be faulted in to "back" those 100 bytes (even though the rest of the page is "unused") while another, *different* page might be faulted in to satisfy that second allocation request. If the application can influence *how* the free space is chosen to satisfy a request, it can direct the allocator in that way. On bigger systems, you would embed this knowledge of the underlying VM in the allocator and not the application -- for the exact opposite reason (i.e., to take advantage of knowledge of the underlying VM that the application might not have or want to be concerned with). But, on bigger systems you often have more resources to play with and are less concerned about how "well" the application fits with those resources. > need? Any of the malloc/free implementations I have written over the > years could be swapped out for another (with the except of one that used > 386 page registers). They would work to specification, but not give the > best performance in each other's applications. --^^^^^^^^^^^^^^^^^ Exactly! When you are trimming the hardware down to the barest minimum necessary for a task, you want the software to be "frugal" in how it handles *its* responsibilities. [You aren't designing a general purpose solution that will handle an UNCONSTRAINED range of applications but, rather, a solution for a *particular* application.] >>>>> I still think you are testing at too high a level, test the functions >>>>> that manipulate your internal independently. >>>> >>>> There *is* nothing else. the allocator and the deallocator >>>> are the *only* things that massage the internal state of the >>>> heap! >>> >>> The you should extract some of the internal functionality and test it. >> >> I can essentially do this by examining the results of >> successive invocations designed to expose aspects of that >> state. (see other post to Malcolm, this date) > > But you can't directly do it. The contents of the free list aren't specified by the function's specification. The only thing that is specified is *how* it goes about providing a pointer to a block of memory per the parameters passed. Testing anything other than that (peeking under the hood) ties the test implementation to the function implementation. Do you peek inside sqrt() while testing it to verify that the individual CORDIC iterations are proceeding in the right order? Or, do you wait to examine the result? And, all you really care about *is* the result. If you craft your test cases to put the function in a situation where you effectively EXPOSE an internal decision E.g., I know there are two fragments in the free list at this point -- based on the results I have verified from my previous allocation requests. And, I know *where* those fragments must be -- again, because I know what memory has already been granted to me and where *it* is located in the address space. So, I can now issue a request that could be handled by *either* of those fragments (i.e., both are big enough) but specify a selection criteria that SHOULD cause the allocator to pick fragment A instead of fragment B. Let's see if it does... I can stack these test cases back to back forcing the allocator to pick one, then the other, based solely on the parameters that I pass to it (since the function is just a state machine and must respond to its inputs -- which include its current "state" -- in a predictable manner) > You could easily extract and test the > functions the manipulate the free list for example. I guess the > difference in approach is I would have written and tested those lower > level functions before combining them. Each of the "criteria" is essentially a (*ftn)() -- with a suitable parameter list. This makes it easy for me to add other options/criteria without having to redesign the entire algorithm. I.e., it imposes a framework *inside* the function. So, for example, a (*selector)() takes a pointer to a heap_t (which contains information about the free list for that heap as well as constraints on that heap) and a size_t (for the desired chunk) as well as caller-specified alignment (in addition tot he alignment constraints imposed by the platform). The (*selector)() is responsible for examining the free list for the heap and picking a suitable fragment for the request based on the strategy that it embodies. A (*trimmer)() takes a fragment_t and a size_t and returns a fragment_t that has been "trimmed" to the correct size (noting alignment constraints in the process) along with a fragment_t that is "scrap" (returned to the free list). Etc. Below this lies another level of functions that actually "do the work". This allows code to be shared between "selectors", etc. (e.g., a selector might examine the free list differently based on knowledge of how the free list is *currently* ordered) The problem is that most of the implementation relies on storing data *in* the free *fragments* to eliminate the need for supplemental data structures. E.g., the fragments are maintained in a doubly linked list with that "overhead" residing *in* the fragments themselves. So, the data for the fragment at 0x12345678 is stored *in* the fragment at 0x12345678. The allocator must dereference 0x12345678 in order to find the size of that fragment, the next fragment preceding/following it in the free list, etc. As such, testing that the code properly handles the case of a 17 byte fragment existing AT 0xFFFFFFF0 (which clearly can't be the case since the 17th byte would be past the end of memory!) requires *accessing* the data at 0xFFFFFFF0 (i.e., I don't even *know* that the "size" stored in that fragment is INCORRECT until I can do that!) By contrast, a 17 byte fragment at 0xFFFFFF00 wouldn't be an error (at least not for *that* reason!)
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-09 16:43 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 12:56 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-09 19:40 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 17:53 +1300
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 18:12 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 02:05 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-10 23:17 +1300
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-10 12:00 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 11:00 +1300
Re: Regression testing for pointers Ike Naar <ike@iceland.freeshell.org> - 2012-03-10 22:23 +0000
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-10 22:40 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 12:12 +1300
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-11 00:42 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 14:26 +1300
Re: Regression testing for pointers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-11 03:09 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 18:16 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 12:01 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-11 10:35 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 09:19 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 07:23 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:23 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:25 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 00:19 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 20:34 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 01:00 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:22 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 10:19 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 07:25 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 02:00 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 22:18 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 11:32 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-15 05:58 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-15 05:55 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-15 11:32 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-16 18:14 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-20 01:43 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-20 21:59 +1300
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-16 03:05 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-20 02:33 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-24 11:49 +1300
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 05:01 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 09:44 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-12 09:56 +1300
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-10 02:28 -0800
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 11:09 -0700
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-10 18:29 +0000
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 05:22 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 09:50 -0700
Re: Regression testing for pointers "io_x" <a@b.c.invalid> - 2012-03-13 13:09 +0100
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-10 03:14 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 12:42 -0700
Re: Regression testing for pointers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-10 08:42 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 02:19 -0700
Re: Regression testing for pointers "BartC" <bc@freeuk.com> - 2012-03-10 15:54 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-10 11:49 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-11 06:09 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 12:33 -0700
Re: Regression testing for pointers nick_keighley_nospam@hotmail.com - 2012-03-12 03:29 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 10:01 -0700
Re: Regression testing for pointers "BartC" <bc@freeuk.com> - 2012-03-13 18:56 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 16:31 -0700
Re: Regression testing for pointers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-12 00:30 +0000
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:41 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-12 13:39 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 09:36 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 07:25 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 16:28 -0700
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 04:20 +0000
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:34 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 00:29 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 17:31 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 01:05 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:30 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-13 10:43 -0700
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-10 15:41 -0800
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-11 11:23 -0700
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-13 13:43 -0700
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 01:45 -0700
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-14 15:15 -0700
Re: Regression testing for pointers Kaz Kylheku <kaz@kylheku.com> - 2012-03-14 22:57 +0000
Re: Regression testing for pointers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-03-15 13:10 -0700
Re: Regression testing for pointers jgk@panix.com (Joe keane) - 2012-03-16 22:20 +0000
Re: Regression testing for pointers "io_x" <a@b.c.invalid> - 2012-03-18 07:15 +0100
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 23:13 -0700
Re: Regression testing for pointers gordonb.b29ri@burditt.org (Gordon Burditt) - 2012-03-12 19:37 -0500
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-12 19:23 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 13:12 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 01:54 -0700
Re: Regression testing for pointers Ian Collins <ian-news@hotmail.com> - 2012-03-14 22:05 +1300
Re: Regression testing for pointers Don Y <this@isnotme.com> - 2012-03-14 11:54 -0700
csiph-web