Implement brk and sbrk

[simonsouth]

This patch adds brk and (a real implementation of) sbrk, functions that change the amount of memory allocated to a process by adjusting its program break (the first memory location past the end of its data segment).

As part of this the patch also changes getrlimit to recognize two additional resource limits, RLIMIT_AS and RLIMIT_DATA, that represent limits on the size of a process' virtual-memory address space and of its data segment, respectively. As far as I can tell Haiku places no artificial restriction on these so I have set them to "unlimited"---if anyone knows differently, I will update the patch.

I've also included a simple unit test that demonstrates the behaviour of sbrk (and of brk, indirectly). Compare with the behaviour specified in ​the man page: On success, the function returns the previous program break; on error, it returns -1 and sets errno to ENOMEM (and leaves the program break unchanged).

[simonsouth]

Add brk and sbrk (and remove sbrk_hook)

[simonsouth]

I've updated the patch to also remove sbrk_hook, which is no longer necessary now that libroot contains its own implementation of sbrk.

[simonsouth]

Hold off on applying this: My code ought to be checking the extent of the data segment before assuming any adjacent areas belong to it.

I'll post another updated patch soon.

[pulkomandy]

Hi,

What is it useful for? (just curious)

It would be nice if the test could use the cppunit based framework, instead of the "SimpleTest" system, because SimpleTest does not give a clear pass/fail output. This would be useful if we ever get our buildbots to automatically run the tests on each build...

[simonsouth]

GNU Emacs needs a working sbrk, as will other UNIX software that handles its own memory management.

I agree about the unit test; I was just following what already existed. I'll take a second look at this as well.

[pulkomandy]

An example of the CPP-Unit based framework is the libnetapi tests: ​http://cgit.haiku-os.org/haiku/tree/src/tests/kits/net/libnetapi

This is preferred over the "SimpleTest" ones, unfortunately we haven't converted much of the tests to this framework, yet.

[korli]

Applied in hrev49872. A CPP unit test is nice to have, but no reason to hold the patch.

[oco]

The new implementation of sbrk severely limit the amount of memory sbrk can allocate. 512 Mo is impossible to allocate (see attached test). And often 2 or three time less, depending on the position of the binary in the address space due to ASLR.

This broke Freepascal that still use this function to allocate memory (since BeOS era). While i can switch to mmap in a future version of Freepascal under Haiku, i think it is a clear BeOS incompatibility.

I think the heap should be include to determine brk address (see ​http://stackoverflow.com/questions/6988487/what-does-brk-system-call-do).

[oco]

Unit test that show that 512 Mo is impossible to allocate using the new sbrk implementation

[korli]

What are FreePascal free memory expectations?

I tested a bit, and the situation with ASLR enabled is chaotic, ie there isn't a contiguous data segment, the new sbrk implementation chooses the latest area, which can be libgcc_s data segment (which is weird BTW). But this isn't OK with ASLR disabled too on x86, the heap is hardcoded to 384MB, which then limits the potential size for sbrk calls. It should be possible to simply reserve a higher address for the heap (here 1GB)

diff --git a/src/system/libroot/posix/malloc/arch-specific.cpp b/src/system/libroot/posix/malloc/arch-specific.cpp
index 4167f04..bd00e12 100644
--- a/src/system/libroot/posix/malloc/arch-specific.cpp
+++ b/src/system/libroot/posix/malloc/arch-specific.cpp
@@ -55,8 +55,8 @@ static const size_t kHeapIncrement = 16 * B_PAGE_SIZE;
 static const addr_t kHeapReservationBase = 0x1000000000;
 static const addr_t kHeapReservationSize = 0x1000000000;
 #else
-static const addr_t kHeapReservationBase = 0x18000000;
-static const addr_t kHeapReservationSize = 0x48000000;
+static const addr_t kHeapReservationBase = 0x40000000;
+static const addr_t kHeapReservationSize = 0x20000000;
 #endif
 
 static area_id sHeapArea;
 

There shouldn't be much impact: with ASLR enabled, the reservation base isn't taken into account anyway (the heap can be located before the program segment for instance...). With ASLR disabled, hoard should be able to allocate in the free range when it exhausts the reserved one, which would be limited to 512MB. Opinions?

Another possibility is to check for an environment variable (like DISABLE_ASLR) to eventually place the initial heap area at the end of the address space.

BTW does FreePascal load any libraries aside from libroot.so? That would also lead to problems (new impl of sbrk would pick these libraries data segments).

[oco]

Freepascal memory allocation strategy is describe here : ​http://www.freepascal.org/docs-html/prog/progsu174.html#x220-2330008.4.2. The OS memory allocation function should be able to allocate as much memory as possible on the system (like mmap can do).

Freepascal itself does not require much more libraries than libroot.so. But programs compiled with Freepascal could potentially load any libraries available on the system (libnet.so for sockets functions for example).

It would be interesting to know exactly what was broken in the previous implementation with GNU Emacs that lead to the new one (maybe the allocated space was not contiguous to the data segment of the main binary). I doubt GNU Emacs never use more than 384 MB. Maybe, it is related to the build process as hinted by this mail : ​http://www.openwall.com/lists/musl/2015/02/03/1.

Excerpt of listarea (with ASLR, in a "favorable" case where the main binary is just before the heap, it is not always the case)

...
 9163                        tt_seg0ro  0x1347000     1000        0     0     0     0
 9164                        tt_seg1rw  0x1348000     1000     1000     0     0     0
 9168                             heap  0x189a7000    40000     9000     0     0     0
...

For this to work, if i understand things correctly (i will not bet on this;-), the main binary should be always the upper one in memory (with ASLR, the starting point can still be different between loads, but less random than the current scheme) and the heap/sbrk area should start just after that (to avoid the gap in the above excerpt). Some additional provisions might be required to reserve space for shared objects that could be dynamically loaded.

[korli]

I'm proposing this patch for review. Feedback welcome.

To help the actual sbrk() implementation, we try to free the space after the program segments. For this to happen:

• the runtime_loader now loads the program first segment with its own segment as a base address: this avoids the situation when the program is loaded at a location before the runtime loader.
• the runtime loader now loads dependencies at a farer location (1GB on 32 bits), this avoids having libroot.so loaded near the program.
• the heap area isn't created on init any more: sbrk is first used to provide the first allocations (until 64 pages), then only the heap area is created: this avoids having an heap area to be created when the program doesn't actually use malloc() (libgcc, libroot might still do though).
• tested on x86 and x86_64, sbrk() allocated 640M successfully.

diff --git a/src/system/libroot/posix/malloc/arch-specific.cpp b/src/system/libroot/posix/malloc/arch-specific.cpp
index 4167f04..2831213 100644
--- a/src/system/libroot/posix/malloc/arch-specific.cpp
+++ b/src/system/libroot/posix/malloc/arch-specific.cpp
@@ -65,6 +65,7 @@ static void *sHeapBase;
 static addr_t sFreeHeapBase;
 static size_t sFreeHeapSize, sHeapAreaSize;
 static free_chunk *sFreeChunks;
+static size_t sSbrkFreeSize;
 
 
 static void
@@ -72,7 +73,7 @@ init_after_fork(void)
 {
 	// find the heap area
 	sHeapArea = area_for((void*)sFreeHeapBase);
-	if (sHeapArea < 0) {
+	if (sHeapArea < 0 && sSbrkFreeSize == 0) {
 		// Where is it gone?
 		debug_printf("hoard: init_after_fork(): thread %" B_PRId32 ", Heap "
 			"area not found! Base address: %p\n", find_thread(NULL),
@@ -96,17 +97,10 @@ __init_heap(void)
 	if (status != B_OK)
 		sHeapBase = NULL;
 
-	uint32 protection = B_READ_AREA | B_WRITE_AREA;
-	if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
-		protection |= B_EXECUTE_AREA;
-	sHeapArea = create_area("heap", (void **)&sHeapBase,
-		status == B_OK ? B_EXACT_ADDRESS : B_RANDOMIZED_BASE_ADDRESS,
-		kInitialHeapSize, B_NO_LOCK, protection);
-	if (sHeapArea < B_OK)
-		return sHeapArea;
-
-	sFreeHeapBase = (addr_t)sHeapBase;
-	sHeapAreaSize = kInitialHeapSize;
+	sSbrkFreeSize = 64 * B_PAGE_SIZE;
+	sHeapArea = B_NO_INIT;
+	sFreeHeapBase = 0;
+	sHeapAreaSize = 0;
 
 	hoardLockInit(sHeapLock, "heap");
 
@@ -157,6 +151,16 @@ hoardSbrk(long size)
 	assert(size > 0);
 	CTRACE(("sbrk: size = %ld\n", size));
 
+	if (sSbrkFreeSize > 0 && size > 0) {
+		if ((size_t)size < sSbrkFreeSize) {
+			sSbrkFreeSize -= min_c((size_t)size, sSbrkFreeSize);
+			void* ptr = sbrk(size);
+			if (ptr != (void*)-1)
+				return ptr;
+		}
+		sSbrkFreeSize = 0;
+	}
+
 	// align size request
 	size = (size + hoardHeap::ALIGNMENT - 1) & ~(hoardHeap::ALIGNMENT - 1);
 
@@ -167,6 +171,19 @@ hoardSbrk(long size)
 
 	hoardLock(sHeapLock);
 
+	if (sFreeHeapBase == 0) {
+		sHeapArea = create_area("heap", (void **)&sHeapBase,
+			sHeapBase != NULL ? B_EXACT_ADDRESS : B_RANDOMIZED_BASE_ADDRESS,
+			kInitialHeapSize, B_NO_LOCK, protection);
+		if (sHeapArea < B_OK) {
+			hoardUnlock(sHeapLock);
+			return NULL;
+		}
+
+		sFreeHeapBase = (addr_t)sHeapBase;
+		sHeapAreaSize = kInitialHeapSize;
+	}
+
 	// find chunk in free list
 	free_chunk *chunk = sFreeChunks, *last = NULL;
 	for (; chunk != NULL; chunk = chunk->next) {
diff --git a/src/system/runtime_loader/elf_load_image.cpp b/src/system/runtime_loader/elf_load_image.cpp
index c6bcbbf..3f67675 100644
--- a/src/system/runtime_loader/elf_load_image.cpp
+++ b/src/system/runtime_loader/elf_load_image.cpp
@@ -527,7 +527,8 @@ load_image(char const* name, image_type type, const char* rpath,
 		goto err2;
 	}
 
-	status = map_image(fd, path, image, eheader.e_type == ET_EXEC);
+	status = map_image(fd, path, image, eheader.e_type == ET_EXEC,
+		type == B_APP_IMAGE);
 	if (status < B_OK) {
 		FATAL("%s: Could not map image: %s\n", image->path, strerror(status));
 		status = B_ERROR;
diff --git a/src/system/runtime_loader/images.cpp b/src/system/runtime_loader/images.cpp
index f2678a3..a291ffd 100644
--- a/src/system/runtime_loader/images.cpp
+++ b/src/system/runtime_loader/images.cpp
@@ -33,9 +33,11 @@
 	// page segment alignment.
 #	define RLD_PROGRAM_BASE	0x600000
 #	define MAX_PAGE_SIZE	0x200000
+#	define RLD_NON_PROGRAM_BASE	0x100000000
 #else
 #	define RLD_PROGRAM_BASE	0x200000
 #	define MAX_PAGE_SIZE	B_PAGE_SIZE
+#	define RLD_NON_PROGRAM_BASE	0x40000000
 #endif
 
 
@@ -170,13 +172,20 @@ topological_sort(image_t* image, uint32 slot, image_t** initList,
 */
 static void
 get_image_region_load_address(image_t* image, uint32 index, long lastDelta,
-	bool fixed, addr_t& loadAddress, uint32& addressSpecifier)
+	bool fixed, bool executable, addr_t& loadAddress, uint32& addressSpecifier)
 {
 	if (!fixed) {
 		// relocatable image... we can afford to place wherever
 		if (index == 0) {
 			// but only the first segment gets a free ride
-			loadAddress = RLD_PROGRAM_BASE;
+			if (!executable)
+				// push libs farer in the address space
+				loadAddress = RLD_NON_PROGRAM_BASE;
+			else {
+				// check the provided address against the program base
+				if (loadAddress < RLD_PROGRAM_BASE)
+					loadAddress = RLD_PROGRAM_BASE;
+			}
 			addressSpecifier = B_RANDOMIZED_BASE_ADDRESS;
 		} else {
 			loadAddress = image->regions[index].vmstart + lastDelta;
@@ -287,7 +296,7 @@ put_image(image_t* image)
 
 
 status_t
-map_image(int fd, char const* path, image_t* image, bool fixed)
+map_image(int fd, char const* path, image_t* image, bool fixed, bool executable)
 {
 	// cut the file name from the path as base name for the created areas
 	const char* baseName = strrchr(path, '/');
@@ -304,6 +313,14 @@ map_image(int fd, char const* path, image_t* image, bool fixed)
 	size_t length = 0;
 	uint32 addressSpecifier = B_RANDOMIZED_ANY_ADDRESS;
 
+	// find out our end of segment to be used as a base
+	area_id ourArea = _kern_area_for((void*)map_image);
+	if (ourArea > B_OK) {
+		area_info ourAreaInfo;
+		if (_kern_get_area_info(ourArea, &ourAreaInfo) == B_OK)
+			loadAddress = (addr_t)ourAreaInfo.address + ourAreaInfo.size;
+	}
+
 	for (uint32 i = 0; i < image->num_regions; i++) {
 		// for BeOS compatibility: if we load an old BeOS executable, we
 		// have to relocate it, if possible - we recognize it because the
@@ -314,7 +331,7 @@ map_image(int fd, char const* path, image_t* image, bool fixed)
 		uint32 regionAddressSpecifier;
 		get_image_region_load_address(image, i,
 			i > 0 ? loadAddress - image->regions[i - 1].vmstart : 0,
-			fixed, loadAddress, regionAddressSpecifier);
+			fixed, executable, loadAddress, regionAddressSpecifier);
 		if (i == 0) {
 			reservedAddress = loadAddress;
 			addressSpecifier = regionAddressSpecifier;
@@ -346,8 +363,8 @@ map_image(int fd, char const* path, image_t* image, bool fixed)
 			baseName, i, (image->regions[i].flags & RFLAG_RW) ? "rw" : "ro");
 
 		get_image_region_load_address(image, i,
-			i > 0 ? image->regions[i - 1].delta : 0, fixed, loadAddress,
-			addressSpecifier);
+			i > 0 ? image->regions[i - 1].delta : 0, fixed, executable,
+			loadAddress, addressSpecifier);
 
 		// If the image position is arbitrary, we must let it point to the start
 		// of the reserved address range.
diff --git a/src/system/runtime_loader/images.h b/src/system/runtime_loader/images.h
index a929040..fa47f0c 100644
--- a/src/system/runtime_loader/images.h
+++ b/src/system/runtime_loader/images.h
@@ -50,7 +50,8 @@ void		delete_image_struct(image_t* image);
 void		delete_image(image_t* image);
 void		put_image(image_t* image);
 
-status_t	map_image(int fd, char const* path, image_t* image, bool fixed);
+status_t	map_image(int fd, char const* path, image_t* image, bool fixed,
+				bool executable);
 void		unmap_image(image_t* image);
 void		remap_images();

[axeld]

I'm basically okay with the patch, but I have two questions: 1) If only libroot/libgcc will use malloc(), but the app uses sbrk(), what exactly will happen with your patch? It does look like the two will interfere now more than before in that use case. Can't we just allocate the heap as before to avoid this? 2) I would actually move the non program base even further down, ie. like 1.5 GB in order to make more space for the heap (or sbrk). If that 512 MB isn't enough, it will be placed somewhere else, anyway, right? We could also add some affinity flag, ie. if an area should rather be created at the start or the end of virtual memory to keep the space for the heap as large as possible.

[korli]

Thanks for the review.

Replying to axeld:

I'm basically okay with the patch, but I have two questions: 1) If only libroot/libgcc will use malloc(), but the app uses sbrk(), what exactly will happen with your patch? It does look like the two will interfere now more than before in that use case. Can't we just allocate the heap as before to avoid this?

libroot/libgcc will use malloc() to init things on library load, but not after. sbrk() will deliver some memory to hoard and to the app, in this order, which means interference shouldn't happen (the app can deallocate up to its allocation with sbrk(), hoard cannot deallocate). Linux does about the same, doing small allocations first with sbrk(), bigger allocations though memory areas, which isn't so different on Haiku with this patch. I think it's the only usecase we should support, any sane application should move out of sbrk() anyway.

2) I would actually move the non program base even further down, ie. like 1.5 GB in order to make more space for the heap (or sbrk). If that 512 MB isn't enough, it will be placed somewhere else, anyway, right? We could also add some affinity flag, ie. if an area should rather be created at the start or the end of virtual memory to keep the space for the heap as large as possible.

Sure I'll check that, though it makes less room for randomizing, this space will be fragmented anyway.