From c800972bc13ad0c7015b7d44fe9f124b719e792e Mon Sep 17 00:00:00 2001 From: spicyjpeg <88942473+spicyjpeg@users.noreply.github.com> Date: Sun, 17 Jul 2022 11:40:02 +0200 Subject: Change I/O base address to 0xbf80, use size_t in stdlib --- libpsn00b/include/stdlib.h | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) (limited to 'libpsn00b/include/stdlib.h') diff --git a/libpsn00b/include/stdlib.h b/libpsn00b/include/stdlib.h index 4c4fcd3..fd4b36c 100644 --- a/libpsn00b/include/stdlib.h +++ b/libpsn00b/include/stdlib.h @@ -9,6 +9,8 @@ #ifndef _STDLIB_H #define _STDLIB_H +#include + #define RAND_MAX 0x7fff /* Conversion functions (not yet implemented) */ @@ -30,7 +32,7 @@ extern "C" { extern int __argc; extern const char **__argv; -int rand(); +int rand(void); void srand(unsigned long seed); int abs(int j); @@ -44,11 +46,11 @@ double strtod(const char *nptr, char **endptr); float strtof(const char *nptr, char **endptr); // Memory allocation functions -void _mem_init(int ram_size, int stack_max_size); -void InitHeap(unsigned int *addr, int size); -int SetHeapSize(int size); -void *malloc(int size); -void *calloc(int number, int size); +void _mem_init(size_t ram_size, size_t stack_max_size); +void InitHeap(void *addr, size_t size); +int SetHeapSize(size_t size); +void *malloc(size_t size); +void *calloc(size_t number, size_t size); void free(void *ptr); #ifdef __cplusplus -- cgit v1.2.3 From 0e755e9801a2dcf7b9827c90cc38e9f532d06393 Mon Sep 17 00:00:00 2001 From: spicyjpeg Date: Sat, 23 Jul 2022 23:49:00 +0200 Subject: Replace default allocator with psyqo implementation --- libpsn00b/include/stdlib.h | 39 +++---- libpsn00b/libc/c++-support.cxx | 46 -------- libpsn00b/libc/cpp_support.cpp | 55 ++++++++++ libpsn00b/libc/malloc.c | 235 +++++++++++++++++++++++++++++++++++++++ libpsn00b/libc/malloc.s | 242 ----------------------------------------- 5 files changed, 304 insertions(+), 313 deletions(-) delete mode 100644 libpsn00b/libc/c++-support.cxx create mode 100644 libpsn00b/libc/cpp_support.cpp create mode 100644 libpsn00b/libc/malloc.c delete mode 100644 libpsn00b/libc/malloc.s (limited to 'libpsn00b/include/stdlib.h') diff --git a/libpsn00b/include/stdlib.h b/libpsn00b/include/stdlib.h index fd4b36c..1888c69 100644 --- a/libpsn00b/include/stdlib.h +++ b/libpsn00b/include/stdlib.h @@ -1,36 +1,25 @@ /* - * stdlib.h - * - * Standard library functions - * - * Inherited from PSXSDK + * PSn00bSDK standard library + * (C) 2019-2022 PSXSDK authors, Lameguy64, spicyjpeg - MPL licensed */ -#ifndef _STDLIB_H -#define _STDLIB_H +#ifndef __STDLIB_H +#define __STDLIB_H #include -#define RAND_MAX 0x7fff +/* Definitions */ -/* Conversion functions (not yet implemented) */ +#define RAND_MAX 0x7fff -/* -extern int atoi(char *s); -extern long atol(char *s); -extern char atob(char *s); // Is this right? -*/ - -// Quick sort (not yet implemented) - -//void qsort(void *base , int nel , int width , int (*cmp)(const void *,const void *)); +/* API */ #ifdef __cplusplus extern "C" { #endif -extern int __argc; -extern const char **__argv; +extern int __argc; +extern const char **__argv; int rand(void); void srand(unsigned long seed); @@ -41,16 +30,17 @@ long long strtoll(const char *nptr, char **endptr, int base); long strtol(const char *nptr, char **endptr, int base); long double strtold(const char *nptr, char **endptr); -// Note: these use floats internally! double strtod(const char *nptr, char **endptr); float strtof(const char *nptr, char **endptr); -// Memory allocation functions void _mem_init(size_t ram_size, size_t stack_max_size); void InitHeap(void *addr, size_t size); -int SetHeapSize(size_t size); +//int SetHeapSize(size_t size); +void *sbrk(ptrdiff_t incr); + void *malloc(size_t size); -void *calloc(size_t number, size_t size); +void *calloc(size_t num, size_t size); +void *realloc(void *ptr, size_t size); void free(void *ptr); #ifdef __cplusplus @@ -58,4 +48,3 @@ void free(void *ptr); #endif #endif - diff --git a/libpsn00b/libc/c++-support.cxx b/libpsn00b/libc/c++-support.cxx deleted file mode 100644 index 38354dd..0000000 --- a/libpsn00b/libc/c++-support.cxx +++ /dev/null @@ -1,46 +0,0 @@ - -#include -#include -#include - -/* Default new/delete operators */ - -void *operator new(size_t size) noexcept { - return malloc(size); -} - -void *operator new[](size_t size) noexcept { - return malloc(size); -} - -void operator delete(void *ptr) noexcept { - free(ptr); -} - -void operator delete[](void *ptr) noexcept { - free(ptr); -} - -/* - * https://en.cppreference.com/w/cpp/memory/new/operator_delete - * - * Called if a user-defined replacement is provided, except that it's - * unspecified whether other overloads or this overload is called when deleting - * objects of incomplete type and arrays of non-class and trivially - * destructible class types. - * - * A memory allocator can use the given size to be more efficient. - */ -void operator delete(void *ptr, size_t size) noexcept { - free(ptr); -} - -/* Placement new operators */ - -void *operator new(size_t size, void *ptr) noexcept { - return ptr; -} - -void *operator new[](size_t size, void *ptr) noexcept { - return ptr; -} diff --git a/libpsn00b/libc/cpp_support.cpp b/libpsn00b/libc/cpp_support.cpp new file mode 100644 index 0000000..f451044 --- /dev/null +++ b/libpsn00b/libc/cpp_support.cpp @@ -0,0 +1,55 @@ +/* + * PSn00bSDK C++ support library + * (C) 2019-2022 Lameguy64, spicyjpeg - MPL licensed + */ + +#include +#include +#include + +/* GCC builtins */ + +extern "C" void *__builtin_new(size_t size) { + return malloc(size); +} + +extern "C" void __builtin_delete(void *ptr) { + free(ptr); +} + +/* Default new/delete operators */ + +void *operator new(size_t size) noexcept { + return malloc(size); +} + +void *operator new[](size_t size) noexcept { + return malloc(size); +} + +void operator delete(void *ptr) noexcept { + free(ptr); +} + +void operator delete[](void *ptr) noexcept { + free(ptr); +} + +// https://en.cppreference.com/w/cpp/memory/new/operator_delete +void operator delete(void *ptr, size_t size) noexcept { + free(ptr); +} + +void operator delete[](void *ptr, size_t size) noexcept { + free(ptr); +} + +/* Placement new operators */ + +void *operator new(size_t size, void *ptr) noexcept { + return ptr; +} + +void *operator new[](size_t size, void *ptr) noexcept { + return ptr; +} diff --git a/libpsn00b/libc/malloc.c b/libpsn00b/libc/malloc.c new file mode 100644 index 0000000..9d538cd --- /dev/null +++ b/libpsn00b/libc/malloc.c @@ -0,0 +1,235 @@ +/* + * PSn00bSDK default memory allocator + * (C) 2022 Nicolas Noble, spicyjpeg + * + * This code is based on psyqo's malloc implementation, available here: + * https://github.com/grumpycoders/pcsx-redux/blob/main/src/mips/psyqo/src/alloc.c + * + * Heap management and memory allocation are completely separate, with the + * latter being built on top of the former. This makes it possible to override + * only InitHeap() and sbrk() while still using the default allocator, or + * override malloc()/realloc()/free() while using the default heap manager. + */ + +#include +#include +#include + +#define _align(x, n) (((x) + ((n) - 1)) & ~((n) - 1)) + +/* Private types */ + +typedef struct _BlockHeader { + struct _BlockHeader *prev, *next; + void *ptr; + size_t size; +} BlockHeader; + +/* Data */ + +static void *_heap_start, *_heap_end, *_heap_limit; +static void *_alloc_start = 0; +static BlockHeader *_alloc_head = 0, *_alloc_tail = 0; + +/* Heap management API */ + +__attribute__((weak)) void InitHeap(void *addr, size_t size) { + _heap_start = addr; + _heap_end = addr; + _heap_limit = (void *) ((uintptr_t) addr + size); +} + +__attribute__((weak)) void *sbrk(ptrdiff_t incr) { + void *old_end = _heap_end; + void *new_end = (void *) _align((uintptr_t) old_end + incr, 8); + + if (new_end > _heap_limit) + return 0; + + _heap_end = new_end; + return old_end; +} + +/* Memory allocator */ + +static BlockHeader *_find_fit(BlockHeader *head, size_t size) { + BlockHeader *prev = head; + + for (; prev; prev = prev->next) { + if (prev->next) { + uintptr_t next_bot = (uintptr_t) prev->next; + next_bot -= (uintptr_t) prev->ptr + prev->size; + + if (next_bot >= size) + return prev; + } + } + + return prev; +} + +__attribute__((weak)) void *malloc(size_t size) { + size_t _size = _align(size + sizeof(BlockHeader), 8); + + // Nothing's initialized yet? Let's just initialize the bottom of our heap, + // flag it as allocated. + if (!_alloc_head) { + if (!_alloc_start) + _alloc_start = sbrk(0); + + BlockHeader *new = (BlockHeader *) sbrk(_size); + if (!new) + return 0; + + void *ptr = (void *) &new[1]; + new->ptr = ptr; + new->size = _size - sizeof(BlockHeader); + new->prev = 0; + new->next = 0; + + _alloc_head = new; + _alloc_tail = new; + return ptr; + } + + // We *may* have the bottom of our heap that has shifted, because of a free. + // So let's check first if we have free space there, because I'm nervous + // about having an incomplete data structure. + if (((uintptr_t) _alloc_start + _size) < ((uintptr_t) _alloc_head)) { + BlockHeader *new = (BlockHeader *) _alloc_start; + + void *ptr = (void *) &new[1]; + new->ptr = ptr; + new->size = _size - sizeof(BlockHeader); + new->prev = 0; + new->next = _alloc_head; + + _alloc_head->prev = new; + _alloc_head = new; + return ptr; + } + + // No luck at the beginning of the heap, let's walk the heap to find a fit. + BlockHeader *prev = _find_fit(_alloc_head, _size); + if (prev) { + BlockHeader *new = (BlockHeader *) ((uintptr_t) prev->ptr + prev->size); + + void *ptr = (void *)((uintptr_t) new + sizeof(BlockHeader)); + new->ptr = ptr; + new->size = _size - sizeof(BlockHeader); + new->prev = prev; + new->next = prev->next; + + (new->next)->prev = new; + prev->next = new; + return ptr; + } + + // Time to extend the size of the heap. + BlockHeader *new = (BlockHeader *) sbrk(_size); + if (!new) + return 0; + + void *ptr = (void *) &new[1]; + new->ptr = ptr; + new->size = _size - sizeof(BlockHeader); + new->prev = _alloc_tail; + new->next = 0; + + _alloc_tail->next = new; + _alloc_tail = new; + return ptr; +} + +__attribute__((weak)) void *calloc(size_t num, size_t size) { + return malloc(num * size); +} + +__attribute__((weak)) void *realloc(void *ptr, size_t size) { + if (!size) { + free(ptr); + return 0; + } + if (!ptr) + return malloc(size); + + size_t _size = _align(size + sizeof(BlockHeader), 8); + + BlockHeader *prev = (BlockHeader *) ((uintptr_t) ptr - sizeof(BlockHeader)); + + // New memory block shorter? + if (prev->size >= _size) { + prev->size = _size; + if (!prev->next) + sbrk((ptr - sbrk(0)) + _size); + + return ptr; + } + + // New memory block larger; is it the last one? + if (!prev->next) { + void *new = sbrk(_size - prev->size); + if (!new) + return 0; + + prev->size = _size; + return ptr; + } + + // Do we have free memory after it? + if (((prev->next)->ptr - ptr) > _size) { + prev->size = _size; + return ptr; + } + + // No luck. + void *new = malloc(_size); + if (!new) + return 0; + + __builtin_memcpy(new, ptr, prev->size); + free(ptr); + return new; +} + +__attribute__((weak)) void free(void *ptr) { + if (!ptr || !_alloc_head) + return; + + // First block; bumping head ahead. + if (ptr == _alloc_head->ptr) { + size_t size = _alloc_head->size; + size += (uintptr_t) _alloc_head->ptr - (uintptr_t) _alloc_head; + _alloc_head = _alloc_head->next; + + if (_alloc_head) { + _alloc_head->prev = 0; + } else { + _alloc_tail = 0; + sbrk(-size); + } + + return; + } + + // Finding the proper block + BlockHeader *cur = _alloc_head; + for (cur = _alloc_head; ptr != cur->ptr; cur = cur->next) { + if (!cur->next) + return; + } + + if (cur->next) { + // In the middle, just unlink it + cur->next->prev = cur->prev; + } else { + // At the end, shrink heap + _alloc_tail = cur->prev; + + void *top = sbrk(0); + size_t size = (top - (cur->prev)->ptr) - (cur->prev)->size; + sbrk(-size); + } + + (cur->prev)->next = cur->next; +} diff --git a/libpsn00b/libc/malloc.s b/libpsn00b/libc/malloc.s deleted file mode 100644 index e441bbe..0000000 --- a/libpsn00b/libc/malloc.s +++ /dev/null @@ -1,242 +0,0 @@ -# Custom first-fit malloc routines by Lameguy64 -# Part of the PSn00bSDK Project -# -# NOTE: there reportedly is a GCC bug which messes up .weak functions written -# in assembly if LTO is enabled. I haven't tested but, according to the -# internet, this bug has never been fixed. -# https://gcc.gnu.org/legacy-ml/gcc-help/2019-10/msg00092.html - -.set noreorder - -.set ND_PREV, 0 # Address to previous block (NULL if starting block) -.set ND_NEXT, 4 # Address to next block (NULL if end block) -.set ND_SIZE, 8 # Size of block -.set ND_HSIZ, 12 - -.section .text - -# Stupid small function just to get bss end -# due to GCC insisting externs to be gp relative -.global GetBSSend -.type GetBSSend, @function -GetBSSend: - la $v0, _end - jr $ra - nop - - -# Initializes the heap for malloc -# a0 - Starting address of heap -# a1 - Size of memory heap -# -.global InitHeap -.type InitHeap, @function -.weak InitHeap -InitHeap: - la $v0, _malloc_addr - sw $a0, 0($v0) - la $v0, _malloc_size - sw $a1, 0($v0) - - sw $0 , ND_PREV($a0) # Set heap header - sw $0 , ND_NEXT($a0) - jr $ra - sw $0 , ND_SIZE($a0) - - -# Changes the heap size without clearing or relocating the heap -# a0 - Size of memory heap in bytes -.global SetHeapSize -.type SetHeapSize, @function -.weak SetHeapSize -SetHeapSize: - la $v1, _malloc_size - lw $v0, 0($v1) - jr $ra - sw $a1, 0($v1) - - -# Allocates a block of memory in the heap -# a0 - Size of memory block to allocate. -# -.global malloc -.type malloc, @function -.weak malloc -malloc: - addiu $a0, 3 # Round size to a multiple of 4 - srl $a0, 2 - - la $a2, _malloc_addr - lw $a2, 0($a2) - sll $a0, 2 - -.Lfind_next: - - move $a1, $a2 - - lw $a2, ND_NEXT($a1) # Get block header - lw $v1, ND_SIZE($a1) - - subu $v0, $a2, $a1 # Compute space between current and next - - beqz $v1, .Lempty_block # Occupy empty block (if size = 0) - nop - - beqz $a2, .Lnew_block # Allocate a new block (if no next) - nop - - addiu $v0, -(ND_HSIZ*2) # Compute remaining space of block - subu $v0, $v1 - - blt $v0, $a0, .Lfind_next # Search for the next block if space is not big enough - nop - - # Perform a block split using remaining space of current block - - addiu $v0, $a1, ND_HSIZ # Compute address for new header - addu $v0, $v1 - - sw $a1, ND_PREV($v0) # Set the new block header - sw $a2, ND_NEXT($v0) - sw $a0, ND_SIZE($v0) - - sw $v0, ND_NEXT($a1) # Update previous and next blocks - sw $v0, ND_PREV($a2) - - jr $ra - addiu $v0, ND_HSIZ - -.Lempty_block: # Occupy an empty block - - beqz $a2, .Lno_next # Skip size calculation if there's no next - nop - - addiu $v0, -ND_HSIZ - blt $v0, $a0, .Lfind_next - nop - - b .Lskip_space_check - nop - -.Lno_next: - - la $v1, _malloc_addr # Check if there's enough space for a block - lw $v1, 0($v1) - la $v0, _malloc_size - lw $v0, 0($v0) - - subu $v1, $a1, $v1 - addu $v1, $a0 - addiu $v1, ND_HSIZ - - bgt $v1, $v0, .Lno_space - nop - -.Lskip_space_check: - - sw $a0, ND_SIZE($a1) - jr $ra # Return address - addiu $v0, $a1, ND_HSIZ - -.Lnew_block: # Create a new block - - addu $a2, $a1, $v1 # Compute address for new block - addiu $a2, ND_HSIZ - - la $v1, _malloc_addr - lw $v1, 0($v1) - la $v0, _malloc_size - lw $v0, 0($v0) - - subu $v1, $a2, $v1 - addu $v1, $a0 - addiu $v1, ND_HSIZ - - bgt $v1, $v0, .Lno_space # Reject if it exceeds specified size - nop - - sw $a1, ND_PREV($a2) - sw $0 , ND_NEXT($a2) - sw $a0, ND_SIZE($a2) - - sw $a2, ND_NEXT($a1) - - jr $ra # Return address - addiu $v0, $a2, ND_HSIZ - -.Lno_space: # Return a null if no space can be found - - jr $ra - move $v0, $0 - - -# Allocates a block of memory in block units and zero fills the -# allocated block. -# a0 - Block size. -# a1 - Number of blocks to allocate -# -.global calloc -.type calloc, @function -.weak calloc -calloc: - mult $a0, $a1 - addiu $sp, -4 - sw $ra, 0($sp) - - jal malloc - mflo $a0 - - move $a0, $v0 - mflo $a1 - -.Lclear_loop: - - sw $0 , 0($a0) - addi $a1, 4 - bgtz $a1, .Lclear_loop - addiu $a0, 4 - - lw $ra, 0($sp) - addiu $sp, 4 - jr $ra - nop - - -# Deallocates an allocated block -# a0 - An address returned by malloc to deallocate -# -.global free -.type free, @function -.weak free -free: - - addiu $a0, -ND_HSIZ - lw $a1, ND_PREV($a0) - lw $a2, ND_NEXT($a0) - - beqz $a1, .Lis_start # Check if block is a starting block - nop - - beqz $a2, .Lis_end - nop - - # Unlink - - sw $a2, ND_NEXT($a1) - jr $ra - sw $a1, ND_PREV($a2) - -.Lis_end: # Unlinks the ending block - - jr $ra - sw $0 , ND_NEXT($a1) - -.Lis_start: # Simply set size to 0 if starting block - - jr $ra - sw $0 , ND_SIZE($a0) - - -# Internal variables -.comm _malloc_addr, 4, 4 -.comm _malloc_size, 4, 4 -- cgit v1.2.3