pilgrimk@lafcol.UUCP (Kenwyn A. Pilgrim) (08/17/89)
For those of you who have TP50, please try this:
var
P1,P2: pointer;
begin
GetMem(P1, 50); {1}
GetMem(P2, 20); {2}
FreeMem(P2,20); {3}
FreeMem(P1,50); {4}
end.
While in the DEBUG mode keep an eye on the MemAvail function
(Crtl-F7 then MemAvail to put it in watch window);
This is how my TP5 session went
After Line 1: MemAvail - 50;
After Line 2: MemAvail - 20;
After Line 3: MemAvail + 20;
After Line 4: MemAvail + 50;
So far so good.
Now, switch line {3} with line {4} and run again
The next TP5 session went like this:
After Line 1: MemAvail - 50;
After Line 2: MemAvail - 20;
After New Line 3: MemAvail + 42;
After New Line 4: MemAvail + 28;
In both cases the available memory was restored to its
value before the program was run, but in the latter case the
memory is not replaced as expected.
I am in the process of writing a GetMem and FreeMem functions
which would allow me to save memory segments larger than
64K-$F (using a list of pointers).
I can MyGetMem(P, AnySize) fine, but on occasions MyFreeMem(P)
would say:
Error 204: Invalid pointer operation
esp. when the size allocated is close to the MemAvail (plus or minus
100, for instance). All other tests outside of this range
seem fine (and there were many, but that may not prove much).
I would like to think that the problem here is not my logic
but the way in which TP50 handles memory allocation/deallocation :-(
For those of you who are curious the list is like
ListPtr = ^PtrRec;
PtrRec = record
SavePtr: pointer;
Size : word; {never more than 64K - $F - SizeOf(PtrRec)}
Next: ListPtr
end;
and my routines are
procedure MyGetMem(P: pointer; Size: longint);
procedure MyFreeMem(P: pointer);
(I don't need the size of the memory allocated because
it's already stored in the variable Size)
And yes! I do take into consideration the memory used for each element of
the actual list (i.e. SizeOf(PtrRec) for each 64K-$F or less stored)
Also, because of the way MyGetMem routine allocates memory,
the MyFreeMem routine deallocates the memory FIFO - so maybe
this is where the problem lies. Maybe if I deallocate it LIFO...
Hmmm. Bye for now with that thought.
Thanks in advance for any helpful hints, thought, pointers, etc.
-Kenwyn
P.S.
I would expect the same fragmentation problems inherent with the way in
which TP5 manages memory, but nothing like this!filbo@gorn.santa-cruz.ca.us (Bela Lubkin) (08/17/89)
In article <1392@lafcol.UUCP>, Kenwyn A. Pilgrim writes: [paraphrase: In Turbo Pascal 5.0, if two heap blocks are allocated and then released in the opposite order, MemAvail acts as expected. If they are released in the same order as they were allocated, the first FreeMem increases MemAvail by less than expected; the second by more than expected; but after both are released, MemAvail is as expected.] This is an artifact of how Turbo 5's memory manager works. I'll describe why it happens; I leave it up to you to determine whether this has any bearing on your problem. Without going into a great deal of detail, the memory manager keeps track of free memory by maintaining a list of free blocks. When the heap is empty, there are no free blocks in the list -- the large block at the free end of the heap does not appear in the list and is tracked by other pointers. The size of the free-blocks-list floats according to how many free blocks there are. In the example you gave, there are no free blocks at any time in the sequence [allocate(first); allocate(second); free(second); free(first)]. On the other hand, in the sequence [allocate(first); allocate(second); free(first); free(second)], a free block is created when you free(first). Memory usage looks something like this [not to any scale]: initially: ------------- allocate(first): *------------ allocate(second): **----------- free(first): -*----------* free(second): ------------- To keep track of the free block created by free(first), a free-block pointer is allocated at the end of the heap. This accounts for the missing memory as reported by MemAvail. free(second) allows that free block to coalesce with the rest of the heap, so the free-block pointer goes away, its memory becomes available again, and MemAvail once again reports the expected value. The key point here is that MemAvail may not exactly track the amounts allocated and freed because of this automatic allocation for the free list. > I would like to think that the problem here is not my logic > but the way in which TP50 handles memory allocation/deallocation :-( From what you describe (which I will not attempt to quote), I don't >think< the memory manager is causing your problem. You did indeed find something that seemed anomalous, but it's part of the normal operation of the heap. (BTW, the heap manager does make sure that the memory it's allocating for the free list is available...) One thing was not clear from your posting: when the problem occurs, is the heap very nearly full (or has it been so earlier in the program, and has the highest allocated block not been freed)? The free list is constrained to the end of the heap; if the heap's nearly full, or was, and there is still a block allocated near the end, even if others below it have been freed, you can get an error on a deallocation because the free list is unable to expand. Bela Lubkin * * filbo@gorn.santa-cruz.ca.us CIS: 73047,1112 @ * * ...ucbvax!ucscc!gorn!filbo ^^^ REALLY slow [months?] R Pentomino * Filbo @ Pyrzqxgl (408) 476-4633 & XBBS (408) 476-4945
mccaugh@s.cs.uiuc.edu (08/22/89)
filbo@gorn.santa-cruz.ca.us in s.cs.uiuc.edu:comp.lang.pascal writes: > size of the free-blocks-list floats according to how many free blocks there > are. In the example you gave, there are no free blocks at any time in the > sequence [allocate(first); allocate(second); free(second); free(first)]. On > the other hand, in the sequence [allocate(first); allocate(second); > free(first); free(second)], a free block is created when you free(first). No, this is not quite what happens. First of all, by 'size' of the free- blocks-list do you mean the number of such blocks? If that is all that's given, it seems safe to assume they're all of the same size. Now, I believe the problem lies in your confusion as to what is a free block: when you say that "there are no free blocks at any time", well - if that were literally true - why didn't the user complain of a crash? With only 70 (50+20) bytes allocated, that seems unlikely. What actually happens is that in both of the sequences, a free block gets added ('second' in the first sequence and 'first' in the second), not just in the second sequence of actions. So the only discrepancy here lies in the size of blocks freed. > Memory usage looks something like this [not to any scale]: initially: ------------- allocate(first): *------------ allocate(second): **----------- free(first): -*----------* should be: -*------------ free(second): ------------- > To keep track of the free block created by free(first), a free-block pointer > is allocated at the end of the heap. This accounts for the missing memory > as reported by MemAvail. free(second) allows that free block to coalesce > with the rest of the heap, so the free-block pointer goes away, its memory > becomes available again, and MemAvail once again reports the expected value. It sounds like you are saying that the first block freed is not coalesced into the heap but remains on some free-block list (otherwise why allocate a free-block pointer to it?) but then the second block freed is coalesced: this sounds like memory-mismanagement in that the destiny of freed blocks is left in question: do they go into the free-block-list or back into the heap? If the former, are they all the same size? (This is why I raised the question of equal-sized blocks earlier.) Was there a free-block-list from the beginning or did the compiler generate one on demand? And does MemAvail refer to that list or to the heap? My point is that if MemAvail refers to the free-list only, then it shouldn't have been affected by allocation of the free-block pointer off the heap.
mccaugh@s.cs.uiuc.edu (08/23/89)
Upon reflection, I now realize that I spoke too soon: there is much more to my predecessor's point than I at first realized: if (as I strongly suspect, knowing Borland Int'l as I do) they support only a naive memory-manager, then when blocks become available whose addresses are not contiguous (this is what I mean by NAIVE), they cannot coalesce the block with existing heap so they (naievely) plant a pointer to it and charge the user for 8 bytes of space: 4 bytes for the pointer (address) and 4 for the block-size, which would explain the discrepancy. This does indeed constitute a very valid indictment of the Borland approach!
mccaugh@s.cs.uiuc.edu (08/24/89)
I tried to edit the preceding but it was already networked. Anyway, I apologize for the flame about Borland (only in that this is not the proper place for it). Responding to: filbo@gorn.santa-cruz.ca.us, who writes: > In article <1392@lafcol.UUCP>, Kenwyn A. Pilgrim writes: > [paraphrase: In Turbo Pascal 5.0, if two heap blocks are allocated and then > released in the opposite order, MemAvail acts as expected. If they are > released in the same order as they were allocated, the first FreeMem > increases MemAvail by less than expected; the second by more than expected; > but after both are released, MemAvail is as expected.] ..... > Without going into a great deal of detail, the memory manager keeps track of > free memory by maintaining a list of free blocks. Now what is unclear here is: does the memory manager start out with the free-block list or are the free blocks really just those that were freed up by the user but cannot yet be coalesced into the heap owing to non- contiguous addresses? It sounds as though the latter situation is the case, but I just would like to know for sure. > When the heap is empty, there are no free blocks in the list -- the large > block at the free end of the heap does not appear in the list and is tracked > by other pointers. Again, could the heap not also be empty with some free blocks present but all with non-contiguous addresses preventing re-formation of the heap? Perhaps we need clarification on the definition of "heap", which I do not consider the same as the free-block list. Also, if the heap is empty, what is the status of "the large block at the 'free end' of the heap"? > The size of the free-blocks-list floats according to how many free blocks > there are. In the example you gave, there are no free blocks at any time in > the sequence [allocate(first); allocate(second); free(second); free(first)]. Yes, this is what led me to surmise above that there don't seem to be free blocks to start with, but rather become free'd by the user and tracked by the memory manager when they can't be absorbed into the heap. To say that "there are no free blocks at any time" in the first sequence does then make sense: the memory manager didn't start out with any, and whateve memory got free'd up by the user could get immediately coalesced into the heap. So I apologize for my earlier misunderstanding. > On the other hand, in the sequence [allocate(first); allocate(second); > free(first); free(second)], a free block is created when you free(first). Right: because memory was not de-allocated in LIFO order, the first block freed is not contiguous with the heap and so must be designated a "free block" and tracked until it can be coalesced. >To keep track of the free block created by free(first), a free-block pointer >is allocated at the end of the heap. This accounts for the missing memory >as reported by MemAvail. free(second) allows that free block to coalesce >with the rest of the heap, so the free-block pointer goes away, its memory >becomes available again, and MemAvail once again reports the expected value. Yes, now this makes sense to me - except that I recall MemAvail being off by 8 (rather than 4 bytes, which is all a pointer alone would account for), so I suspect the other 4 bytes refers to the size of the block, also taking up memory. > The key point here is that MemAvail may not exactly track the amounts > allocated and freed because of this automatic allocation for the free list.
filbo@gorn.santa-cruz.ca.us (Bela Lubkin) (08/24/89)
In <208300013@s.cs.uiuc.edu>, mccaugh@s.cs.uiuc.edu writes: > if (as I strongly suspect, > knowing Borland Int'l as I do) they support only a naive memory-manager, > then when blocks become available whose addresses are not contiguous (this > is what I mean by NAIVE), they cannot coalesce the block with existing heap Yes, exactly. Within the constraints of the hardware and software (specifically: 8086-compatible processors; a "pointer" rather than "handle" heap), just what method did you have in mind of coalescing non-contiguous memory blocks? > so they (naievely) plant a pointer to it and charge the user for 8 bytes of > space: 4 bytes for the pointer (address) and 4 for the block-size, which > would explain the discrepancy. What is "naive" about this? The user gets "charged" for free list storage only when it's needed. If a program allocates memory but never frees any, or frees it in strict reverse order, the entire heap is available for user storage. I'd rather have that than be >required< to set aside memory for the free list. A different concern is: is it really beneficial to store the free list separately, rather than >within< the free blocks? Borland's main rationale is that their method allows arbitrarily small heap blocks. I think it's more important that the free list is (somewhat) more protected from being trashed by bad accesses to heap blocks (e.g. accesses to a deallocated pointer). The main disadvantage, of course, is the memory taken up by the free list. More subtly: their old heap manager (in Turbo 3.0 and earlier) had 8-byte granularity and did in fact store the free list within the free blocks. Having worked with both, I think 8-byte granularity is much better for minimizing heap fragmentation. Of course this could be maintained by shelling around the heap functions... Bela Lubkin * * filbo@gorn.santa-cruz.ca.us CIS: 73047,1112 @ * * ...ucbvax!ucscc!gorn!filbo ^^^ REALLY slow [months] R Pentomino * Filbo @ Pyrzqxgl (408) 476-4633 & XBBS (408) 476-4945 ** gorn's MX record is currently broken; you MUST use UUCP routing ** via ...ucbvax!ucscc!gorn!filbo or gorn!filbo@ucscc.ucsc.edu