MSX Malloc on memory > 64KB

bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

MSX Malloc on memory > 64KB

Post by bradstallion »

Hi All,
I'm interested in the More Than 64k stuff. I'm developing a MSXDOS2 application and I'm testing the limits of application size and heap size for mallocs.

I organized my application in 3 banks using the __banked function calls. Moreover, I'd like to use all the RAM installed on the system and managed by the MSXDOS2 memory mapper.

To do so, I played with far memory, implementing a very simple far memory malloc (so far, just an incrementing pointer in the allocated segments, with no realloc nor free) following the guidelines of the section "Implementing Far memory".

It works (!) but the application (that uses malloc a lot) is slow (well, I implementend the malloc stuff mostly in C...), I was forced to change declarations to add the __far decorator, the size of the application grew due to the 3bytes pointers, etc.

Now I'd like to experiment with named address space, probably pre-allocating big arrays in spaces and then implement malloc on them.

Do you have some suggestion on this? And, in general, on malloc-ing on memory beyond 64KB?

Thanks a lot
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

Wow, congrats on doing that. I honestly never expected anyone else to implement __far pointers!

I've not got any concrete answers, but take a look at the "named heap" stuff here: https://github.com/z88dk/z88dk/wiki/Cla ... ry-malloch - the library supports multiple heaps, so you could have one correspond to each segment.

It's obviously not as smooth as treating it as a linearised heap with __far since you'll end up with decorators on variables and you'll have to know the memory layout ahead of time to do that.

The other approach which was used on the ti83+ is to modularise the app so that each segment is independent and just exposes the entry points at a known address. The PR that added that feature is here: https://github.com/z88dk/z88dk/pull/2433 so you can see how it works.
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Sat Apr 13, 2024 2:11 pm Wow, congrats on doing that. I honestly never expected anyone else to implement __far pointers!
Thanks :)
The hardest part was to convert the code already written.

Speaking of, if a have a char *__far string, how can I (s)printf it? Should I copy it to a near address and then print it?
I've not got any concrete answers, but take a look at the "named heap" stuff here: https://github.com/z88dk/z88dk/wiki/Cla ... ry-malloch - the library supports multiple heaps, so you could have one correspond to each segment.
So, if I understand correctly, something like:

__addressmod setb0 spaceb0;
spaceb0 void ∗ myheap[16k];

HeapCreate(myheap);

MyStuff * ptr = HeapAlloc(myheap, sizeof(MyStuff));

is it correct?
It's obviously not as smooth as treating it as a linearised heap with __far since you'll end up with decorators on variables and you'll have to know the memory layout ahead of time to do that.
why decorators on variables?
The other approach which was used on the ti83+ is to modularise the app so that each segment is independent and just exposes the entry points at a known address. The PR that added that feature is here: https://github.com/z88dk/z88dk/pull/2433 so you can see how it works.
Interesting, but I think this doesn't match my code structure.
Thanks a lot for your suggestions!
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

bradstallion wrote: Sun Apr 14, 2024 11:25 am Speaking of, if a have a char *__far string, how can I (s)printf it? Should I copy it to a near address and then print it?
Unfortunately so.
[snip]

is it correct?
It's not quite right, but I've not got it to work either yet, let me get back to you. I've got something that looks right, but it's error-prone so I think I can do better than that.
why decorators on variables?
The pointers returned using a malloc in a bank need to be namespaced, so "spaceb0 void *ptr" for example
Interesting, but I think this doesn't match my code structure.
No worries, just throwing out some more possibilities.
pjshumphreys
Member
Posts: 83
Joined: Sat Feb 06, 2021 2:32 pm

Re: MSX Malloc on memory > 64KB

Post by pjshumphreys »

Speaking of, if a have a char *__far string, how can I (s)printf it? Should I copy it to a near address and then print it?
I've found that storing code and static variables in paged memory is easier to work with than the stack or heap, because of this kind of need to copy data between pages takes extra time. Although having named heaps in paged ram is a nice idea I didn't think of.
...modularise the app so that each segment is independent and just exposes the entry points at a known address
I've had success with a table of JMP instructions and a trampoline function that are always kept paged in, because it simplifies usage of far code.

The trampoline function can look on the stack to see what its return address is then use that to calculate which page to switch to and what the address of the real function to jump to should be. ret instructions will then return to another trampoline function to set the paging back to the way it was.

This also means no matter how much code your program has, you'll always have around 32kb of stack and heap space available. Due to the nature of this approach, your static variables data wouldn't be limited to 64kb either. Because the z80 isn't great at stack relative memory addressing anyway you would also get a bit of a speed boost as well by declaring any variables that can be as static.

This could probably be combined with named heaps in paged ram as well.
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

I have something that looks right. Because the Heap* functions aren't address space aware, we have to wrap the calls to them, so that they work on the right bank.

I've only wrapped Alloc here, but you'll need to do the same for HeapFree etc.

For each bank you want to use you'll have to create the set of functions - since the pointer is still 16 bit there's no way to have a bank reference in them.

Coming back to __far. If you don't mind donating your __far routines, I'd love to have them included in z88dk - even without a working heap, there's still a benefit of being able to access data linearly since the MSX is one of the targets with banking support.

Code: Select all

#include <malloc.h>
#include <stdint.h>

extern void setb0(void);
__addressmod setb0 spaceb0;



extern spaceb0 long heap_b0;
extern spaceb0 uint8_t pool[16000];

void HeapCreate_b0(void)
{
    heap_b0 = 0L;
}

void HeapSbrk_b0(spaceb0 void *ptr, size_t len)
{
   setb0();
   HeapSbrk((void *)&heap_b0, (void *)ptr, len);
}

spaceb0 void *HeapAlloc_b0(size_t len)
{
   setb0();
   HeapAlloc((void *)&heap_b0, len);
}

extern spaceb0 void *alloc_b0(size_t len);

int func(void)
{
   // Create the heap in spaceb0
   HeapCreate_b0();
   // Add some memory to the heap in spaceb0
   HeapSbrk_b0(pool, sizeof(pool));

   // Allocate a pointer from spaceb0
   spaceb0 char *ptr = HeapAlloc_b0(1024);

   return ptr[0];
}
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

pjshumphreys wrote: Sun Apr 14, 2024 2:43 pm I've had success with a table of JMP instructions and a trampoline function that are always kept paged in, because it simplifies usage of far code.

The trampoline function can look on the stack to see what its return address is then use that to calculate which page to switch to and what the address of the real function to jump to should be. ret instructions will then return to another trampoline function to set the paging back to the way it was.
So this is effectively the method used by TI83 apps (though it's got an extra level of indirection regarding function address). __z88dk_shortcall() and __z88dk_shortcall_hl() are similar ideas that uses a rst and what could be an index into a table - fairly similar to how the Z88 handles its system calls.

The __banked calls available for +gb, +msx, +zx and +cpc use an always available trampoline with a 32 bit address following. There's a secondary stack to keep track of the originating page. It's pretty seamless which is nice, though does depend on the common and library routines fitting within the "home" page.

Regardless, there's a lot of ways to implement >64k support, and I'm really happy to see people picking up on the various ways of doing things. I'm not sure we'll end up with a "one size fits all", but hearing what people have done will I'm sure provide guidance to others.
pjshumphreys
Member
Posts: 83
Joined: Sat Feb 06, 2021 2:32 pm

Re: MSX Malloc on memory > 64KB

Post by pjshumphreys »

The __banked calls available for +gb, +msx, +zx and +cpc use an always available trampoline with a 32 bit address following. There's a secondary stack to keep track of the originating page. It's pretty seamless which is nice, though does depend on the common and library routines fitting within the "home" page.
Very cool. Does the pragma for banking transparently take care of static variables as well? Like in this pseudocode:

Code: Select all

int test(void) {
    static char text[80] = "initial value";

    printf("%s\n", text);
}
This stuff was added in 2020 after I'd already rolled my own custom solution so I've not looked into it too closely before.
Regardless, there's a lot of ways to implement >64k support, and I'm really happy to see people picking up on the various ways of doing things. I'm not sure we'll end up with a "one size fits all", but hearing what people have done will I'm sure provide guidance to others.
Agreed. Different types of programs will need different data access patterns so it's good to have many options available. Early PC compilers had memory models (tiny, small, medium, compact, large, huge) for similar reasons.
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

pjshumphreys wrote: Sun Apr 14, 2024 8:18 pmVery cool. Does the pragma for banking transparently take care of static variables as well? Like in this pseudocode:

Code: Select all

int test(void) {
    static char text[80] = "initial value";

    printf("%s\n", text);
}
It can do, all the compilers do is switch the code and rodata sections when #pragma bank is encountered. You can manually switch BSS and DATA to the bank for RAM targets (certainly on +zx) - initially it was written with ROM targets in mind so it's not automatic.
This stuff was added in 2020 after I'd already rolled my own custom solution so I've not looked into it too closely before.
Is that available anywhere for me to have a look at?
pjshumphreys
Member
Posts: 83
Joined: Sat Feb 06, 2021 2:32 pm

Re: MSX Malloc on memory > 64KB

Post by pjshumphreys »

Code: Select all

Is that available anywhere for me to have a look at?
Sure. I've probably linked to this project before but I've migrated my stuff to sourceforge now. Ignore the silly function names. When I was coming up with names for them they were the first thing that came to mind and they made me chuckle.

https://sourceforge.net/p/querycsv/code ... /pager.asm

The spectrum and c64 targets have similar ones:

https://sourceforge.net/p/querycsv/code ... c64/crt0.s
https://sourceforge.net/p/querycsv/code ... /pager.asm

Here's the main project page (Such as it is. I haven't replaced the all the references to github yet):
https://sourceforge.net/p/querycsv/code/ci/master/tree/
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Sun Apr 14, 2024 7:23 pm I have something that looks right. Because the Heap* functions aren't address space aware, we have to wrap the calls to them, so that they work on the right bank.

I've only wrapped Alloc here, but you'll need to do the same for HeapFree etc.
Great, thanks! I'll try it as soon as I can (Monday morning, RL is calling...)
Coming back to __far. If you don't mind donating your __far routines, I'd love to have them included in z88dk - even without a working heap, there's still a benefit of being able to access data linearly since the MSX is one of the targets with banking support.
Sure, no problem. Do you want a zip or a pull request on github? In that case, just tell me where to put the files.
Thanks
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Sun Apr 14, 2024 7:23 pm

Code: Select all



extern spaceb0 void *alloc_b0(size_t len);

BTW, what is the alloc_b0 above?
Thanks
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

bradstallion wrote: Mon Apr 15, 2024 11:18 amBTW, what is the alloc_b0 above?
Thanks
A remnant from an experiment - apologies.
Sure, no problem. Do you want a zip or a pull request on github? In that case, just tell me where to put the files.
A PR would be great - just add the files and I'll tidy up etc - put them in libsrc/target/msx/far - thanks!
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Mon Apr 15, 2024 7:30 pm A PR would be great - just add the files and I'll tidy up etc - put them in libsrc/target/msx/far - thanks!
PR done!

Feel free to correct, improve, throw it away ;)
pjshumphreys
Member
Posts: 83
Joined: Sat Feb 06, 2021 2:32 pm

Re: MSX Malloc on memory > 64KB

Post by pjshumphreys »

Before making calls to the extended bios I recommend you first check it's available. I can't remember for definite but I think it's not always present even on msx2 machines.

My mapper initialisation routine starting at line 240 of https://sourceforge.net/p/querycsv/code ... /pager.asm does this.

My code for this is written in assembly, but the same thing could also be done in C.

Firstly my code checks that the version of cp/m is 2.2 using the CPM_VERS bdos call as all versions of msxdos report this version so if it's anything else you know the code is actually running on real cp/m. The bdos function is in the cpm.h header

Next it makes a msxdos call to check the version of msxdos in use. Real cp/m version 2.2 won't return a value here as bdos calls on cp/m 2.2 don't go up to 0x6f. Unfortunately msxdos calls don't follow the same calling convention as cp/m so you'd need to use the asmcall function to do this.

If the version number returned is 2 the code is really running on msxdos 2. msxdos 1 will return 1 instead.

Then checking the value at address HOKVLD will tell you if an extended bios is present or not.

Finally, the extended bios call to GET_VARTAB can also fail if an msxdos2 mapper isn't available.

Hope this helps
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

Thanks a lot, you are absolutely right. This is a personal project, so it's not very polite, yet. But I put your suggestion on my TODO list.
pjshumphreys
Member
Posts: 83
Joined: Sat Feb 06, 2021 2:32 pm

Re: MSX Malloc on memory > 64KB

Post by pjshumphreys »

It would be very cool to be able to use paged ram in this way on other CP/M like machines as well. You can get apple 2 applicards with 512Kb (https://www.tindie.com/products/gglabs/ ... -iie-iigs/) and the Amstrad PCW 8512 also has 512kb of ram and can run CP/M.
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

pjshumphreys wrote: Wed Apr 17, 2024 1:40 pm It would be very cool to be able to use paged ram in this way on other CP/M like machines as well. You can get apple 2 applicards with 512Kb (https://www.tindie.com/products/gglabs/ ... -iie-iigs/) and the Amstrad PCW 8512 also has 512kb of ram and can run CP/M.
Thanks to the kick from @bradstallion I'm getting there and it should be a doddle to add support for new machines. Hopefully I'll be able to merge within the next couple of weeks.

Effectively for a new target you'll need to supply 3 assembler functions (I've yet to decide on proper names):

Code: Select all

; Get the initial banking setting
; Exit: a = current bank (or entry value for __far_reset)
; Uses; none
__far_init:

; Reset the banking
; Entry: a = bank to page in (or reference to paging config to do so)
; Uses: none
__far_reset

; Maps and pages in the physical bank for the logical address
; Entry: ebc = logical address
;         a' = local memory page
; Exit:   hl = physical address to access (bank paged in)
;        ebc = logical address
;
; Corrupts: d,a
__far_page:
You'll be able to malloc() a block up to a size of 64k which I hope is enough.

Of course I've found a few bugs en-route, not too much of a surprise since this stuff hasn't been heavily used.
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

You'll be able to malloc() a block up to a size of 64k which I hope is enough.
That's great, @dom !
Of course I've found a few bugs en-route, not too much of a surprise since this stuff hasn't been heavily used.
Speaking of, I had a problem with this:

Code: Select all

#define FAR_VOID2 void *__far *__far 

typedef struct {
    FAR_VOID2 items;  // Array of pointers to void
    int size;     // Current number of elements in the vector
} Vector;
In a function, the following code gave problems (wrong pointers, basically):

Code: Select all

vector->items[vector->size++] = item;
while this worked:

Code: Select all

vector->items[vector->size] = item;
vector->size++;
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

I think I may have fixed that one on my adventures.

I've just pushed a change that gives -subtype=msxdos access to a far heap. The size of the heap is defined by -pragma-define:CLIB_FARHEAP_BANKS=nn where nn is the number of 16k pages to grab from the mapper.

The code, apart from 4 routines (and 1 of those should be) is generic, which means you should also get a few string and memory functions as well. You also get a malloc/calloc/free and a noddy realloc implementation.

In theory the maximum allocatable size is a few bytes less than 64k.

Assuming it all builds, it should be in the next nightly.

I'm sure they'll be issues, doing this sort of thing always finds new ways to crash, so bear with me whilst we drive them out.
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Mon Apr 22, 2024 8:59 pm I think I may have fixed that one on my adventures.

I've just pushed a change that gives -subtype=msxdos access to a far heap. The size of the heap is defined by -pragma-define:CLIB_FARHEAP_BANKS=nn where nn is the number of 16k pages to grab from the mapper.
@dom, this is GREAT! Thanks!
In theory the maximum allocatable size is a few bytes less than 64k.
Do you mean the total heap space? Or the maximum single block size?
I'm sure they'll be issues, doing this sort of thing always finds new ways to crash, so bear with me whilst we drive them out.
This is a simple test/benchmark I'm trying:

Code: Select all

#include <stdio.h>
#include <time.h>

void main() {
  int nrep = 200;
  char tmp;
  clock_t t1, t2, t3,t4;

  // test ptr
  int *__far*__far ii;
  ii = (int*__far*__far)malloc_far(sizeof(int*__far));
  *ii = (int*__far)malloc_far(sizeof(int));
  **ii = 123;
  printf("pointer val %d\n", **ii);

  // malloc benchmark
  char * ma;
  t1 = clock();
  for (int i = 0; i<nrep; i++) ma = malloc(sizeof(char));
  t2 = clock();
  for (int i = 0; i<nrep; i++) *ma = 'Z';
  t3 = clock();
  for (int i = 0; i<nrep; i++) tmp = *ma; //printf("---- val: %c\n", *ma);
  t4 = clock();
  printf("%d malloc: %.3f\n", nrep, (float)(t2-t1)/CLOCKS_PER_SEC);
  printf("%d write: %.3f\n", nrep, (float)(t3-t2)/CLOCKS_PER_SEC);
  printf("%d read: %.3f\n", nrep, (float)(t4-t3)/CLOCKS_PER_SEC);
  printf("written val: %c\n", tmp);


  printf("\n");
  
  // malloc far benchmark
  char *__far maf;
  t1 = clock();
  for (int i = 0; i<nrep; i++) maf = malloc_far(sizeof(char));
  t2 = clock();
  for (int i = 0; i<nrep; i++) *maf = 'Z';
  t3 = clock();
  for (int i = 0; i<nrep; i++) tmp = *maf;
  t4 = clock();

  printf("%d malloc far: %.3f\n", nrep, (float)(t2-t1)/CLOCKS_PER_SEC);
  printf("%d write far: %.3f\n", nrep, (float)(t3-t2)/CLOCKS_PER_SEC);
  printf("%d read far: %.3f\n", nrep, (float)(t4-t3)/CLOCKS_PER_SEC);

  printf("written val: %c\n", tmp);

}
I compile it with:

Code: Select all

zcc +msx -subtype=msxdos -o testfar.com testfar.c -DAMALLOC  -pragma-define:CRT_MAX_HEAP_ADDRESS=0x7fff -lm -pragma-define:CLIB_FARHEAP_BANKS=4
The final char 'Z' is not printed.

Thanks again for your work!
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

bradstallion wrote: Tue Apr 23, 2024 9:28 am
dom wrote: Mon Apr 22, 2024 8:59 pm In theory the maximum allocatable size is a few bytes less than 64k.
Do you mean the total heap space? Or the maximum single block size?
Maximum size in a single block - I've been testing with a 128k heap on +test and +msx.
This is a simple test/benchmark I'm trying:
That one is sorted, caused by a confusion around which register to use for sign extension. Use an unsigned char and it's not an issue.
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Tue Apr 23, 2024 5:14 pm That one is sorted, caused by a confusion around which register to use for sign extension. Use an unsigned char and it's not an issue.
Thanks, I'll try the new nightly snapshot tomorrow.
User avatar
dom
Well known member
Posts: 2140
Joined: Sun Jul 15, 2007 10:01 pm

Re: MSX Malloc on memory > 64KB

Post by dom »

It's in the wrong forum, but I've also added support for +zx as well. However, it's noticeable slower than +msx due to the bank switching overhead.
bradstallion
Member
Posts: 30
Joined: Wed Mar 13, 2024 12:52 pm

Re: MSX Malloc on memory > 64KB

Post by bradstallion »

dom wrote: Tue Apr 23, 2024 7:36 pm It's in the wrong forum, but I've also added support for +zx as well. However, it's noticeable slower than +msx due to the bank switching overhead.
That's a great news, because I'd like to compile my application for both platforms.
Anyway, your MSX implementation is waaaaaay faster than mine!!! No surprise! Thank you! =D
Post Reply