QL Heap

[bwinkel67]

That assumes the C runtimes would ever hand back memory it once allocated to the OS. Almost no C compiler, at least none contemporary to the QL does that. Memory footage on nearly any C compiler I know can only grow, never shrink. C runtimes will obviously hand back any free()d memory to its own "unallocated" pool for re-use by the same job, but never hand back heap fragments to the OS. That is to keep heap memory allocated in per-program chunks rather than have applications spread their allocated memory all over the place (which is way worse).

If you take C68, for example, any heap management function will allocate memory in chunks of 8kBytes per default, any future memory allocation is satisfied from these large chunks, if this first chunk is depleted, C68 will allocate more in 4kBytes granularity. (all of these are adjustable)

Ah, perhaps that's what's going on and hopefully, Digital 'C' SE does some form of it. Now 8k byte chunks sounds a little better and that would explain why it works for me. I don't have Digital Precision's source but I do have the Hendrix text on Small 'C' and it comes with the original source code, so perhaps I need to crack that open to see how its allocator works. If things get really bad I may just go the route of specifying a maximum size for programs (say 16K) and reduce my reliance of constantly allocating and freeing memory. Setting by internal block size to 64 bytes for the BASIC program area is probably not an ideal size :-/ This was initially a prototype that got ported to a different platform so I didn't bother much with memory model design.

[mk79]

I'd be surprised if Digital 'C' SE is that complex. They are a pretty small and rudimentary compiler and linker and I would have thought left most of this to the OS.

Actually you are right, malloc maps to the common heap on that compiler. I found that the sources are available after all (malloc maps to mlalloc):

Code: Select all

* Memory allocation routines
*
* mlalloc(size) long size; Gets size bytes from QDOS common heap.
*       Ensures size is even, rounding up if necessary.
*       Returns address (bse relative) of space allocated or NULL
*
                function <'mlalloc'>
                copy_to mlalloc_end
                move.l  (dsp),d1        No. of bytes
                addq.l  #1,d1           Ensure even
                bclr    #0,d1
                moveq   #-1,d2
                moveq   #mt.alchp,d0
                trap    #1
                move.l  a0,prim
                sub.l   bse,prim
                tst.l   d0
                beq.s   mlalloc_exit
                move.l  #null,prim
mlalloc_exit    rts
mlalloc_end

Here's a basic program I use to debug heap problems, it dumps the heap structure into a file. Maybe it can help you:

Code: Select all

100 INPUT#0,'File> ';File$
110 OPEN_NEW#3,File$
120 PRINT#3,"Freemem :"; FREE_MEM/1024; "kb"
130 PRINT#3\\"Common heap"\
140 common -1
150 PRINT#3\\"TPA"\
160 TPA -1
170 CLOSE#3
990 :
1000 DEFine PROCedure common(jobID)
1010 adr = PEEK_L(HEX('28004'))
1020 chpfr = HEX('28004') + PEEK_L(HEX('28008'))
1030 endHeap = PEEK_L(HEX('2800C'))
1040 heap(jobID)
1050 END DEFine common
1060 :
1070 DEFine PROCedure TPA(jobID)
1080 adr = PEEK_L(HEX('28014'))
1090 chpfr = HEX('28014') + PEEK_L(HEX('28018'))
1100 endHeap = PEEK_L(HEX('28020'))
1110 heap(jobID)
1120 END DEFine TPA
1130 :
1140 DEFine PROCedure heap(jobID)
1150 :
1160 ch% = 3
1170 flag = 0
1180 PRINT#ch%,CHR$(10)&'address  '!'length'!'driver'!'ownr'!'rflag    '!'name'
1190 :
1200 REPeat heaploop
1210   IF adr >= endHeap: EXIT heaploop
1220   CHP_LEN = PEEK_L(adr)
1230   CHP_JOB = PEEK_W(adr + 10)
1240   IF jobID >= 0 AND jobID <> CHP_JOB: GO TO 1350
1250   CHP_DRIVR = PEEK_L(adr + 4)
1260   CHP_OWNER = PEEK_L(adr + 8)
1270   CHP_RFLAG = PEEK_L(adr + 12)
1280   PRINT#ch%,HEX$(adr,32)&' '!HEX$(CHP_LEN,24)!HEX$(CHP_DRIVR,24)!HEX$(CHP_JOB,16)!HEX$(CHP_RFLAG,32);
1290   IF chpfr = adr THEN
1300     PRINT#ch%,'  free': chpfr = chpfr + CHP_DRIVR
1310   ELSE
1320     PRINT#ch%,'  '&JOB$(CHP_OWNER)
1330   END IF
1340   flag = 1
1350   adr = adr + CHP_LEN
1360 END REPeat heaploop
1370 :
1380 IF NOT flag: PRINT#ch%,'Nothing found': ELSE PRINT#ch%,'Finished'
1390 END DEFine heap
1400 :

[tofro]

Ah, perhaps that's what's going on and hopefully, Digital 'C' SE does some form of it. Now 8k byte chunks sounds a little better and that would explain why it works for me. I don't have Digital Precision's source but I do have the Hendrix text on Small 'C' and it comes with the original source code, so perhaps I need to crack that open to see how its allocator works. If things get really bad I may just go the route of specifying a maximum size for programs (say 16K) and reduce my reliance of constantly allocating and freeing memory. Setting by internal block size to 64 bytes for the BASIC program area is probably not an ideal size :-/ This was initially a prototype that got ported to a different platform so I didn't bother much with memory model design.

Well, QDOS is actually pretty unique in that respect: It does have an API that supports allocation of "private heaps" in "larger chunks":

• Allocate a large chunk from the OS using MT.ALCHP
• Hand that chunk over to the OS "private heap" management using MT.LNKFR
• Allocate bits of memory from that private heap into your application using MT.ALLOC traps until the chunk is depleted
• Add new chunks to the private heap using MT.ALCHP+MT.LNKFR, or free allocated bits back to the private heap using MT.LNKFR

That mechanism is actually intended for device drivers to be able to allocate heap memory (that it already owns) from atomic code, but can just as well be used from applications.
I don't know any other OS that would support such stuff.

Tobias

[bwinkel67]

One other question...it seems the QL allocate function (which Martin noted is what Digital 'C' SE seems to be using directly) seems to be destructive when it is asked to allocate more memory than it has. On a few occasions, even though internally I end gracefully when trying to load a program that is too big (i.e. I check for NULL and stop), I crash horribly.

Digital 'C' SE does have an avail() function that returns how much memory is left but it is unclear to me what that means. Does it return the top of the heap (binary-tree is hopefully how QDOS implements it) where the top contains the biggest contiguous size, or does it give the entire free memory. If it's the former then it would be useful and perhaps to avoid crashes if mlalloc is destructive, I could call it first:

Code: Select all

   if (needed_memory < avail(0))
      ptr = malloc(needed_memory);
   else
      syserr(NOHEAP);    /* my internal ZXSimulator function */

Here is what the Digital 'C' SE documentation says avail() does. It's confusing because it speaks of holes that free() leaves. I'd rather it just say "returns biggest block available" as that would make the function useful.

Code: Select all

long avail(code) int code;
                   Returns the number of bytes of free memory in the
                   QDOS common heap. This number does not include
                   holes left by previous use of free(). If there is
                   no  free memory, the action taken depends on the
                   value of code:  if code = 0, avail() returns 0; if
                   code != 0, the task is aborted.

Edit: I found Tony Tebby and Kavid Karlin's Software Developer Guide which adds some clarity. It talks about the heap being relocatable which I'm not sure how that would work: "The use of relative pointers ensures that heaps may be moved." So when you get a pointer to a memory blob, not sure how the heap could be moved if a program is working with a specific memory address"

[tofro]

One other question...it seems the QL allocate function (which Martin noted is what Digital 'C' SE seems to be using directly) seems to be destructive when it is asked to allocate more memory than it has. On a few occasions, even though internally I end gracefully when trying to load a program that is too big (i.e. I check for NULL and stop), I crash horribly.

Digital 'C' SE does have an avail() function that returns how much memory is left but it is unclear to me what that means. Does it return the top of the heap (binary-tree is hopefully how QDOS implements it) where the top contains the biggest contiguous size, or does it give the entire free memory. If it's the former then it would be useful and perhaps to avoid crashes if mlalloc is destructive, I could call it first:

Code: Select all

   if (needed_memory < avail(0))
      ptr = malloc(needed_memory);
   else
      syserr(NOHEAP);    /* my internal ZXSimulator function */

Here is what the Digital 'C' SE documentation says avail() does. It's confusing because it speaks of holes that free() leaves. I'd rather it just say "returns biggest block available" as that would make the function useful.

Code: Select all

long avail(code) int code;
                   Returns the number of bytes of free memory in the
                   QDOS common heap. This number does not include
                   holes left by previous use of free(). If there is
                   no  free memory, the action taken depends on the
                   value of code:  if code = 0, avail() returns 0; if
                   code != 0, the task is aborted.

Edit: I found Tony Tebby and Kavid Karlin's Software Developer Guide which adds some clarity. It talks about the heap being relocatable which I'm not sure how that would work: "The use of relative pointers ensures that heaps may be moved." So when you get a pointer to a memory blob, not sure how the heap could be moved if a program is working with a specific memory address"

It talks about "heaps" being reloctable. Not the "common heap being reloctable". SuperBasic moves its heaps about quite a lot on memory-limited machines.

QDOS memory management can be rather complex as there two allocation mechanisms as described above that are layered inside-out like a Russian doll.
The Common Heap (i.e. that memory area that is shared between all jobs) never moves. You get chunks of memory from there and return it.
The innermost doll is the heap management code that builds a job-private heap out of those big chunks (A mechanism apparently not used by Digital C). That heap management code does allow you to manage small bits inside your big chunks - That's what Tony calls the "heaps" (note the plural - There's only one common heap but many heaps within there...)

The MT.ALLOC/MT.LNKFR code indeed uses only relative pointers for its inner heap management - Which would allow you to allocate other "chunks", copy all of the old chunk's contents to the new one and only adjust the base pointer to the heap within there, and it would still work - This obviously doesn't work with a C program, as that expects pointers returned from malloc() to be immutable and absolute. But if your code doesn't move the chunks, nobody else will - That's simply an option.

Digital C does seem to use (like most compilers) the outer layer of heap management code (MT.ALCHP/RECHP) - allocating and returning chunks directly to and from the common heap. As it does that in program-allocation-sized chunks, that's actually not very multi-tasking-friendly as it spreads the job's allocations all over the place, with a high likelyhood to fragment the common heap so much that it will waste system memory big time.

[bwinkel67]

I seem to be running into that problem; i.e. interaction with other elements, esp the OS. When I do the following within the ZXSimulator command prompt, things work as expected (assuming 30,000 bytes free in common heap).

DIM A(2000)
DIM B(1000)
DIM C(6500)

Note that each does a malloc of twice that size in bytes so I have allocated 17,000 bytes. However, if I instead do the following (note that I reboot/reset everything to have same start):

DIM A(2000)
DIM B(1000)
LOAD "MDV2_TEST_BAS"

Where test_bas is 13,000 bytes in length, I get a MAX HEAP ERROR. Note that 13000 bytes is the same as DIM A(6500) so overall memory should again be 17,000 bytes.

The only internal difference that I can deduce is that there is a while loop using fseek() to figure out the size of a file (doing so in 64 byte blocks) before it does the malloc (and it fails on the malloc before it actually reads in the file). So I speculate that QDOS has read in part of the file while fseeking through it and is using part of the heap leaving the file in cache. This makes reading the file, I assume, somewhat faster since it can now do less I/O, but I lose some memory (or at least it gets fragmented).

Once I replace the fseek() technique with the actual Trap 3 call to get file size I won't have that problem, but still, it's a side effect. Haven't tried to clear the cache using rewind() as I presently just re-seek to 0 (rewind is supposed to clear input so I'm not sure if that means the entire cache gets abandoned).

However, all in all, I love the complexity of the QDOS operating system (even the original BBQL versions -- I use JSU). Thankfully it's not a simple program loader like many of the other personal computers of the era (except the Amiga of course). Pretty cool they developed that level of complexity for such a small platform in the early 80's.

[NormanDunbar]

George Gwilt wrote a couple of pages on my QDOSMSQ Internals web site about heaps, with examples and links to all the traps and vectors involved in using the common and user heaps. It might be useful - http://www.qdosmsq.dunbar-it.co.uk/doku ... mory:heaps.


Cheers,
Norm.

[mk79]

One other question...it seems the QL allocate function (which Martin

Marcel

Digital 'C' SE does have an avail() function that returns how much memory is left but it is unclear to me what that means.

It returns the gap between the topmost heap entry and the base of Basic. Not the biggest hole in the heap

Does it return the top of the heap (binary-tree is hopefully how QDOS implements it)

You think a home system from 1984 where the whole of the OS fits into 48kb uses a binary tree for heap managemt? I think your expectations are a tad too high.

[bwinkel67]

One other question...it seems the QL allocate function (which Martin

Marcel

I'm really sorry about that...don't know why Martin stuck in my head...

Digital 'C' SE does have an avail() function that returns how much memory is left but it is unclear to me what that means.

It returns the gap between the topmost heap entry and the base of Basic. Not the biggest hole in the heap

I'm not sure what use I would have for that as I would care more about the largest chunk available. I need to figure out why a failed malloc sometimes causes havoc as you'd think the call would realize there wasn't enough memory and just return NULL. I don't see my code doing anything destructive as it just gives up and returns to the prompt.

Does it return the top of the heap (binary-tree is hopefully how QDOS implements it)

You think a home system from 1984 where the whole of the OS fits into 48kb uses a binary tree for heap managemt? I think your expectations are a tad too high.

It seems to be a simple linked list that it keeps track of free space and I don't think it's ordered.

You can implement a binary tree heap structure as a static linear array pretty simply -- just have to do some basic child and parent index math: index * 2 & index * 2+1 for children and index / 2 (integer division) for parent -- and you get the last node (which is the hard part usually) as just the length of the filled array. So that's why didn't think it was a huge hit. Doing it with dynamic memory is more complex as just keeping track of the last node in the tree is not a pretty algorithm (though interesting to walk through). Now you have to store two values in each array element (size and start address) so it can't be just a simple integer array.

[tofro]

I think you're missing a point here - namely what the task of an OS is on the one hand, and how "well-behaving applications" should use that services OTOH.

QDOS has been written under the assumption that jobs would try and use the memory services of the OS in the most cooperative way possible: That is, the way C68 does it. What Digital C seems to do is not very cooperative: The system used (allocating lots of tiny chunks all over the place) there is bound to cause memory fragmentation big time on a multi-tasking system. And, as the unexpanded QL is severely memory-limited, that leads to exhausted heap space very early.