Psy-Q lib.c issues

General help for the PSY-Q SDK, such as setting the SDK up, compiling correctly, linking and debugging
Post Reply
jman
Rookie Programmer
Rookie Programmer
Posts: 110
Joined: Aug 13, 2013

Psy-Q lib.c issues

Post by jman » October 20th, 2013, 1:14 am

I've found in the official SCEE Playstation Developer's guide (v2.9) a note about memory management functions:
Dynamic Memory Allocation and the Heap

(...cut...)
In C, memory allocation is achieved using the malloc and free functions. Unfortunately there have been several problems with these functions on PlayStation.
The standard malloc/free combination supplied as part of libc fragments memory due to a bug in the free function. This means that large chunks on the machine memory become inaccessible even though they are not holding any valid data.
There is a patch for this bug which is used by linking with a file called mmgm.obj (available from the SCEE WEB SITE). This supplies a new function for initialising the heap and replaces the buggy malloc and free with more reliable functions. In this scheme the heap base is unconventionally located at the address ramsize minus the stacksize and the heap “grows” toward the base of memory.
Whilst these functions are better than the originals, they are still comparatively untested. Also they are rather generic. You are strongly recommended to consider developing a memory allocation scheme that is tailored to your specific application, rather than relying on those supplied in the libraries.
An example showing how to implement a simple malloc/free scheme is presented in the Kernighan & Ritchie book The C Programming Language. This text notes that the optimal memory allocation scheme depends on the nature of the application.
Just out of curiosity, how much this impacts PSX programming? I guess for small applications this may be unnoticeable.
Does anyone have more info/experience about this?
Does this issue has ever been solved (to our knowledge) by Sony over time?

Thanks

User avatar
t0rxe
C Programming Expert
C Programming Expert
Posts: 139
Joined: Dec 19, 2012
Motto: /\OX[]
PlayStation Model: SCPH-5502
Location: Australia

Post by t0rxe » October 20th, 2013, 3:27 pm

Sony solved it by updating Malloc to Malloc3. So just use Malloc3. It's an updated version of Malloc :D
As for how Malloc works, I'll dig up my drawings of the memory management so you can see how Malloc uses the memory. It's extremely useful, and makes working with the 2MB of RAM a lot easier and faster :)

Here is one without the malloc() routine implemented. I will make the malloc version tomorrow ;)
http://www.psxdev.net/forum/viewtopic.php?f=47&t=463
"Nostalgia isn't a big enough word to describe the PlayStation from my eyes"

jman
Rookie Programmer
Rookie Programmer
Posts: 110
Joined: Aug 13, 2013

Post by jman » October 21st, 2013, 12:12 am

Thank you for providing the right keyword ("malloc3"), I've found the reference in the libref46.pdf document.
I'm also interested in this specific implementation of the malloc()/free(). Some low-level knowledge never harms, even if just doing simple things.

User avatar
nocash
PSX Aficionado
PSX Aficionado
Posts: 541
Joined: Nov 12, 2012
Contact:

Post by nocash » October 28th, 2022, 12:52 am

I am just trying to make sense of that issue.

I have tried to reproduce the "bug" where "large chunks" are becoming inaccessible, but I couldn't reproduce that effect. What I've tried is:

Code: Select all

InitHeap
Allocate 1Kbyte blocks (until malloc returns 0 or -1), display number of blocks, free them
Allocate 16Kbyte blocks (until malloc returns 0 or -1), display number of blocks, free them
Allocate 1Kbyte blocks (until malloc returns 0 or -1), display number of blocks, free them
That did all work fine. There is no bug. Or did anybody ever manage to reproduce that bug???

Looking into the "bugged" free function: free(buf) does just set a flag:

Code: Select all

[buf-4]=[buf-4] or 1
It's impossible to get that wrong. There is no bug in the free function.

Looking into the malloc function. That is a mess. It seems to be using a 2-pass try/retry mechanism to find free blocks. And, as free doesn't automatically merge free blocks, the malloc function is somehow taking care of merging them during those passes. It's hard to grasp what it's doing there, but it's apparently working (my above test did include several free 1K blocks, that were successfully merged into 16K blocks).

The closest thing that might be wrong is using an imperfect memory allocation strategy. That isn't exactly a bug, and there is no perfect way to deal with memory fragmentation. But some strategies might be more imperfect than others. In DOS, one can select between three strategies (plus some more for DOS high memory):

Code: Select all

first fit
last fit
best fit
As far as I understand, the PSX malloc function seems to use this strategy:

Code: Select all

middle fit (the first free block, starting after the most recently allocated block)
           (with wrapping to begin of heap space when reaching end of heap)
That seems to be really suboptimal, especially if the surrounding memory is free: It could place the newly allocated block in the middle of three free memory area.
In general, using "first fit" should work better. And, for people who understand how to deal with memory fragmentation:
It would be even better to allow to select "first fit, last fit, best fit" for purposes like allocating resident or temporaty buffers.

User avatar
nocash
PSX Aficionado
PSX Aficionado
Posts: 541
Joined: Nov 12, 2012
Contact:

Post by nocash » October 28th, 2022, 12:18 pm

I've done some more tests to confirm the "middle fit" effect. The tests were done with BIOS versions 1.0J and 4.5E and with my own kernel clone (all of them with identical results).

The "middle fit" strategy is actually happening, it's placing new blocks somewhere near the most recently allocated block (even if all memory was free'ed in meantime). That's bad enough to call it a bug, not just a mere imperfection.

Worse, below does also include a situation where trying to allocate a large block does simply fail (even when all memory was free'ed). That's really a major bug.

And a more generic bug: The Psy-Q malloc description claims that "If allocation fails, NULL is returned", but it's actually returning "either 0 or -1" when failed (both can happen; there's is some weird pseudo-random-logic that decides which of those error values is being returned).

Test 1
This does allocate six blocks, then free the 3rd block, and then does some more allocations and deallocations...

Code: Select all

INIT HEAP(A0070000,00040000)
MALLOC(00001000)=A0070004
MALLOC(00001000)=A0071008
MALLOC(00001000)=A007200C
MALLOC(00001000)=A0073010
MALLOC(00001000)=A0074014
MALLOC(00001000)=A0075018
FREE(A007200C)
MALLOC(00001000)=A007200C   ;-good (though not what I had expected)
FREE(A0070004)
FREE(A0071008)
FREE(A007200C)
FREE(A0073010)
FREE(A0074014)
FREE(A0075018)
MALLOC(00001000)=A007200C   ;-bad (all memory is free, but it's placed there)
FREE(A007200C)
MALLOC(0003FC00)=00000000   ;-very bad (all memory is free, but fails)
MALLOC(0003FC00)=00000000   ;-retry    (still fails)
MALLOC(00000010)=A0070004
FREE(A0070004)
MALLOC(0003FC00)=00000000   ;-retry    (still fails)
Test 2
Same as above, but additionally allocating+freeing a large memory block at the begin of the function. That addition shouldn't affect the following allocations - but somehow it does change the behaviour.

Code: Select all

INIT HEAP(A0070000,00040000)
MALLOC(0003FC00)=A0070004   ;\alloc/free large block, affect behaviour below
FREE(A0070004)              ;/
MALLOC(00001000)=A0070004
MALLOC(00001000)=A0071008
MALLOC(00001000)=A007200C
MALLOC(00001000)=A0073010
MALLOC(00001000)=A0074014
MALLOC(00001000)=A0075018
FREE(A007200C)
MALLOC(00001000)=A007601C   ;-not so good (it's now more what I had expected)
FREE(A0070004)
FREE(A0071008)
FREE(A007601C)
FREE(A0073010)
FREE(A0074014)
FREE(A0075018)
MALLOC(00001000)=A007601C   ;-bad (all memory is free, but it's placed there)
FREE(A007601C)
MALLOC(0003FC00)=A0070004   ;-good (mysteriously, it's working now)
MALLOC(0003FC00)=FFFFFFFF   ;-good (not enough memory) (dunno why -1 instead 0)
MALLOC(00000010)=A00AFC08
FREE(A00AFC08)
MALLOC(0003FC00)=00000000   ;-good (not enough memory) (dunno why 0 instead -1)
I guess Test 2 starts to search after the initially allocated+free'ed large block, ie. near end of heap (and then wraps to begin of heap as there's not enough memory at end of heap, and that wrapping appears to affect some corner cases).

User avatar
nocash
PSX Aficionado
PSX Aficionado
Posts: 541
Joined: Nov 12, 2012
Contact:

Post by nocash » October 28th, 2022, 1:51 pm

Now it would be interesting how they could have tried to fix that with "mmgm.obj" and "malloc2" and "malloc3".
There are some problems:

Internal variables
The kernel stores things like the "most recently allocated address" in internal kernal RAM. Patches can't easily access those internal RAM locations (unless they contain a list of possibly different RAM address(es) for all existing kernel versions).
Generic extra problem: The kernel doesn't disable IRQs when updating the allocation state, so terrible things may happen if a IRQ handler & main program are simultaneously trying to allocate or free memory. Hmmm, I don't know how other OSes are solving that, or if it's generally prohibited to allocate memory inside of IRQ handlers? (memory allocation can be slow, and it would be quite harsh to disable IRQs throughout the whole allocation process).

qsort function
The kernel's "qsort" function is using the standard malloc/free functions (that's done in ROM, with direct function calls, without using the function vectors in RAM). I would rather doubt that Sony was even aware of that issue when trying to fix malloc issues.
But it could be solved by (trying to) make malloc2/malloc3 compatible with the old malloc system. Or (more realistic) simply using two separate heaps (a small qsort heap, and a bigger user heap), to support different qsort sizes, the qsort heap could be temporarily allocated with the new malloc2/3 functions:

Code: Select all

repaired_qsort(base,nel,width,callback):
  virtual_heap=malloc2(width+10h)                ;-alloc virtual heap with malloc2
  InitHeap(virtual_heap,width+10h)               ;-init virtual heap
  result=original_qsort(base,nel,width,callback) ;-execute qsort
  free2(virtual_heap)                            ;-free virtual heap with free2
  return result
can somebody compile malloc2/malloc3 test cases?
I am doing my stuff in ASM and I don't even have a compiler. If somebody wants to help, it would be nice if you could compile some small EXE files. It doesn't need to display any test results, it just needs to contain the allocation functions (for disassembling the EXE code). That is, something like this would be fine:

Code: Select all

main_function:
 InitHeap(80100000h,40000h)
 buf=malloc(100h)
 buf=realloc(buf,200h)
 free(buf)
 buf=calloc(10h,20h)
 free(buf)
 qsort(dummy_array, 10, 4, callback)
dummy_array(0,1,2,3,4,5,6,7,8,9)  ;ten 32bit values (aka entry width=4 byte)
callback(p1,p2): return word[p1]-word[p2]  ;or so, don't care for testing
Make an EXE with function names as shown above.
Make another EXE with function names renamed to InitHeap2,malloc2,realloc2,free2,calloc2.
Make another EXE with function names renamed to InitHeap3,malloc3,realloc3,free3,calloc3.
Make another EXE with mmgm.obj (if you can figure out how that's done, I've no idea).
Having the EXE files in CPE format with SYM file debug info would be nice.

Ah, and what might be easier: Does the PsyQ library contain source code for the malloc2/malloc3 functions?

User avatar
Shadow
Admin / PSXDEV
Admin / PSXDEV
Posts: 2670
Joined: Dec 31, 2012
PlayStation Model: H2000/5502
Discord: Shadow^PSXDEV

Post by Shadow » November 2nd, 2022, 7:55 am

Very nice research! So it's not exactly bugged for small segments. It's only when trying to free large blocks it fails to then re-allocate them when it then returns 0 and -1 as failure flags.

I can't remember which library (maybe LIBETC.LIB) has malloc2 and malloc3 in it, but here is library 4.7 for you: http://psxdev.net/downloads/Psy-Q_47.zip

Also attached for you the older MMGMNEW stuff as Sony's (SN Systems') quick fix.
You do not have the required permissions to view the files attached to this post.
Development Console: SCPH-5502 with 8MB RAM, MM3 Modchip, PAL 60 Colour Modification (for NTSC), PSIO Switch Board, DB-9 breakout headers for both RGB and Serial output and an Xplorer with CAETLA 0.34.

PlayStation Development PC: Windows 98 SE, Pentium 3 at 400MHz, 128MB SDRAM, DTL-H2000, DTL-H2010, DTL-H201A, DTL-S2020 (with 4GB SCSI-2 HDD), 21" Sony G420, CD-R burner, 3.25" and 5.25" Floppy Diskette Drives, ZIP 100 Diskette Drive and an IBM Model M keyboard.

User avatar
nocash
PSX Aficionado
PSX Aficionado
Posts: 541
Joined: Nov 12, 2012
Contact:

Post by nocash » November 2nd, 2022, 1:00 pm

That OBJ and LIB files are all binary in I don't know what format. It would be million times easier if somebody could compile them into a known file format (EXE or CPE).
Shadow wrote: November 2nd, 2022, 7:55 am I can't remember which library (maybe LIBETC.LIB) has malloc2 and malloc3
The LibRef47.pdf file says that malloc2 and malloc3 are in libapi.lib - I hope that info will help somebody to get it compiled : )

As far as I understand, MMGM.OBJ is equivalent to malloc2 and MMGMNEW.OBJ equivalent to malloc3 (?) or when looking at MMGMNEW.TXT, that seems to be an unfinished beta version of the malloc3/calloc3/etc function family.
Shadow wrote: November 2nd, 2022, 7:55 am Very nice research! So it's not exactly bugged for small segments. It's only when trying to free large blocks it fails to...
Allocating large blocks can fail. When allocation is starting somewhere in middle of memory, I think it will only see "60% free from middle to end", and then wrap to begin and see "40% free from begin to middle", and then give up.
By that logic it's impossible to allocate large blocks like 80% of memory, even when 100% of memory is free.

Post Reply

Who is online

Users browsing this forum: No registered users and 2 guests