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.