NEWLIB: page fault (malloc always return NULL)

[Haoud]

Hello,
I ported newlib 2.5.0 thanks to the tutorial of this site. No error at complation but at execution, newlib crashes (page fault around 0x00000000 like 0x0000000e, 0x0000001e...) on functions like close_r, malloc_r, or sfvwrite_r. All these functions are reentrant and I think that's where the problem comes from.
My ELF charger well intializes the BSS segment to 0.

my crt0.c

Code: Select all

#include <fcntl.h>

extern void exit(int code);
extern int main(int argc, char *argv[], char *env);
extern char __bss_start;
extern char _end;
extern char **environ;

void _start(int argc, char *argv[], char *env[])
{
	environ = env;
	exit(main(argc, argv, env))
}

my brk code

Code: Select all

#include <sys/stat.h>
#include <sys/types.h>
#include <sys/fcntl.h>
#include <sys/times.h>
#include <sys/errno.h>
#include <sys/time.h>
#include <stdio.h>
#include <errno.h>
#undef errno

#define SYSCALL_RESERVED		0
#define SYSCALL_EXIT			1
#define SYSCALL_OPEN			2
#define SYSCALL_CLOSE			3
#define SYSCALL_MOUNT			4
#define SYSCALL_UMOUNT			5
#define SYSCALL_READ			6
#define SYSCALL_WRITE			7
#define SYSCALL_SEEK			8
#define SYSCALL_READDIR			9
#define SYSCALL_FORK			10
#define SYSCALL_FORKEXEC		11			// Mélange entre fork et exec (mais en plus optimisé), pas encore supporté
#define SYSCALL_MKDIR			12
#define SYSCALL_RMDIR			13
#define SYSCALL_UNLINK			14
#define SYSCALL_EXEC			15
#define SYSCALL_MKNOD			16
#define SYSCALL_IOCTL			17
#define SYSCALL_BRK				18
#define SYSCALL_CHDIR			19
#define SYSCALL_GETCWD			20
#define SYSCALL_DUP				21
#define SYSCALL_DUP2			22
#define SYSCALL_GETPID          23
#define SYSCALL_ISATTY          24
#define SYSCALL_TIME            25
#define SYSCALL_WAITPID         26
#define SYSCALL_KILL            27
#define SYSCALL_SIGACTION       28
#define SYSCALL_SIGRETURN       29

static unsigned int brk_end = 0;

int syscall3(int id, unsigned int arg0, unsigned int arg1, unsigned int arg2)
{
	int retval;
	asm volatile("mov %1, %%eax				\n\
				  mov %2, %%ebx				\n\
				  mov %3, %%ecx				\n\
				  mov %4, %%edx				\n\
				  int $0x80					\n\
				  mov %%eax, %0" : "=m"(retval) : "m"(id), "m"(arg0), "m"(arg1), "m"(arg2));

	return retval;
}

int syscall0(int id)
{
	return syscall3(id, 0, 0, 0);
}

int syscall1(int id, unsigned int arg0)
{
	return syscall3(id, arg0, 0, 0);
}

int syscall2(int id, unsigned int arg0, unsigned int arg1)
{
	return syscall3(id, arg0, arg1, 0);
}
int haoudos_brk(void *addr)
{
	unsigned int result = syscall1(SYSCALL_BRK, (unsigned int)addr);

	if (result == 0)
		return -1;		

	brk_end = (unsigned int)result;
	return 0;
}

caddr_t sbrk(int incr)
{
	if(brk_end == 0)
		haoudos_brk(NULL);			// Initialise le heap

	unsigned int old_brk_end = brk_end;

	int result = haoudos_brk((void *)(brk_end + incr));

	if (result == -1)
		return 0;

	return old_brk_end;
}

My test code (also crash with binutils)

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
	printf("Test de printf\n");
	exit(0);
	
	return 0;
}

When executing:


I have a null pointer dereference, probably.
If you need more information, don't hesitate to ask me.
Thank you for you help.

EDIT: I'v found a problem: malloc always return NULL, but sbrk return correct value and the kernel alloctatif this correctly. Why ?

EDIT2: Found the fautif code in stdlib/mallocr.c:

Code: Select all

2577	    if (chunksize(top) < nb || remainder_size < (long)MINSIZE)
2579	      MALLOC_UNLOCK;
2580	      return 0; /* propagate failure */

But i don't now why i have this error.

PS: Sorry for my English but i'm French

[Haoud]

OK, after a long debugging days, I concluded that the newlib's malloc_extend heap function was bugged because of the optimization. I had add before the function

Code: Select all

#pragma GCC push_options
#pragma GCC optimize ("O0")

and that at the end of it

Code: Select all

#pragma GCC pop_options)

And since then everything works perfectly.

[mallard]

Honestly, I would (and have in my OS) dump newlib's "malloc" implementation completely.

It's based on the archaic "sbrk" mechanism that's near impossible to integrate nicely with things like dynamically-loaded libraries or anything else that needs to allocate memory at a "lower level" than the C library. POSIX only gets away with it by defining that the dynamic program loader is the C library itself, not a good design IMHO.

Note that the current POSIX standard contains this line in the documentation of brk/sbrk:

The behaviour of brk() and sbrk() is unspecified if an application also uses any other memory functions (such as malloc(), mmap(), free()). Other functions may use these other memory functions silently.

That basically means it's pretty much impossible for brk/sbrk to be used in a safe and portable manner by applications, so it's probably best not to have it at all in a reasonably modern OS, unless you're slavishly devoted to POSIX compliance.

Newlib has a "MALLOC_PROVIDED" option to disable its implementation and it's pretty easy to add an alternative implementation alongside your other OS-specific functions.

[Solar]

Note that the current POSIX standard contains this line in the documentation of brk/sbrk:

The behaviour of brk() and sbrk() is unspecified if an application also uses any other memory functions (such as malloc(), mmap(), free()). Other functions may use these other memory functions silently.

That basically means it's pretty much impossible for brk/sbrk to be used in a safe and portable manner by applications, so it's probably best not to have it at all in a reasonably modern OS, unless you're slavishly devoted to POSIX compliance.

I think you are misinterpreting this, significantly.

What POSIX says here, basically, is that there should be only one authority handling brk() / sbrk() -- you either use brk() / sbrk() directly (and stay away from the higher-level C library functions for memory handling, as those might be using brk() / sbrk() internally in a conflicting way); or you use the C-Lib-provided memory functions only and don't touch the lower level of brk() / sbrk().

The idea is that application and C library should not get into each other's territory.

That does not, in any way, disqualify brk() / sbrk() from being used by a C library implementation, which would provide aforementioned functions (malloc(), ...) based on that lower level.

[mallard]

What POSIX says here, basically, is that there should be only one authority handling brk() / sbrk() -- you either use brk() / sbrk() directly (and stay away from the higher-level C library functions for memory handling, as those might be using brk() / sbrk() internally in a conflicting way); or you use the C-Lib-provided memory functions only and don't touch the lower level of brk() / sbrk().

The idea is that application and C library should not get into each other's territory.

That does not, in any way, disqualify brk() / sbrk() from being used by a C library implementation, which would provide aforementioned functions (malloc(), ...) based on that lower level.

The problem is the sentence "Other functions may use these other memory functions silently." That means that if you've called brk/sbrk you can no longer safely and portably use any C/POSIX functions. You could probably get away with using a few functions that should never allocate/free memory (most of math.h is probably safe), but whether any particular function allocates or frees memory is an implementation detail that should not be relied upon.

Even the lowest-standard-level "system call" I/O routines (open, read, write, close) are permitted to allocate/free memory (hence why ENOMEM is a valid return code), so a program that uses brk/sbrk cannot safely and portably do any I/O.

On common UNIX-like platforms brk/sbrk is usually, for compatibility with older code, implemented in a way that won't cause problems with code that uses it carefully; such as by giving it its own "data segment" (obviously not a real hardware segment, although that was of course what brk/sbrk were designed for) separate from the main heap used by malloc/free (the "emulation" approach used by macOS/iOS). If you do choose to implement it in a new OS, I'd do it this way. Currently my OS has no such function and I've not encountered any code that uses it.

The biggest problems with an sbrk-based implementation of "malloc" is that it's inefficient; you can never release application memory that's not at the top of the heap. So, for example, a program that loads a 100MB dataset, calculates some statistics from it and stores that in a 2KB array (in that order; assuming no pre-existing "gaps" in memory) cannot then release the 100MB until it's finished with the 2KB array. Sure, it can internally "free" that memory for reuse within the application, but if another application needs it you're going to be writing a bunch of redundant data to the swap file.

[Solar]

I am completely with you on sbrk()-based malloc() being inefficient.

But the point of the POSIX verbiage, in one line, is:

"The only one using sbrk() / brk() should be the one who's implementing malloc()."

I.e., the C library. Which is quite obviously aware of how sbrk() / brk() is being used by itself, and can keep usage consistent across all its memory-handling functions as long as no application uses sbrk() / brk() as well.

Which is the other angle of the POSIX verbiage:

"If you ain't the one implementing malloc(), stay clear of sbrk() / brk() cause here be dragons."

[Brendan]

Hi,

The biggest problems with an sbrk-based implementation of "malloc" is that it's inefficient; you can never release application memory that's not at the top of the heap. So, for example, a program that loads a 100MB dataset, calculates some statistics from it and stores that in a 2KB array (in that order; assuming no pre-existing "gaps" in memory) cannot then release the 100MB until it's finished with the 2KB array. Sure, it can internally "free" that memory for reuse within the application, but if another application needs it you're going to be writing a bunch of redundant data to the swap file.

It can internally "free" that virtual memory for reuse within the application, and then it can tell the kernel to make that area "allocate on demand" or "unused" so that the kernel frees the underlying physical pages of RAM. The only thing that is really consumed is space, and (especially for 64-bit) space isn't something that's likely to matter.


Cheers,

Brendan

[mallard]

It can internally "free" that virtual memory for reuse within the application, and then it can tell the kernel to make that area "allocate on demand" or "unused" so that the kernel frees the underlying physical pages of RAM. The only thing that is really consumed is space, and (especially for 64-bit) space isn't something that's likely to matter.

If it has a way (presumably another system call) to tell the kernel that the free'd area is "unused", then it's no longer the "classic" sbrk-based implementation, but something more advanced and better. Newlib's implementation does no such thing and has no particularly easy way to add such a thing (except by "forking" the entire allocator).

Certainly, this "enhanced" implementation solves to an extent the efficiency/wasted memory problem, but it still has the other difficulties (i.e. the entire concept of a "program break", which dates back to segmented memory architectures and is difficult to use with things like dynamic libraries, ASLR, etc.). Supporting brk/sbrk in a "real" way (as opposed to the emulation approach) pretty much forces a particular memory layout on userspace applications (heap at the bottom of memory, everything else at the top). The "mmap style"(*) of implementing malloc-and-friends allows you to completely forget about the idea of a "program break" and simply manage memory as a collection of pages, allowing code and data pages to be anywhere in address space (you'd obviously use the relevant page-based mechanisms to prevent data execution).

* Briefly, the "mmap style" implementation has a system call that requests a number of pages from the OS, which returns the address at which they are mapped and a second call that releases a number of pages at a specified address. Traditionally, these calls are "mmap" and "munmap".