DarkElvenAngel
Posts: 2275
Joined: Tue Mar 20, 2018 9:53 pm

Need help understanding sbrk

Wed Aug 03, 2022 6:20 pm

Hello everyone.

I'm working on a memory allocator it's going to run in a VM so I need it to replicate the sbrk function so that it can work with a static block of memory.

I've read the man entry
DESCRIPTION
brk() and sbrk() change the location of the program break, which defines the end of the process's data segment (i.e., the program break is
the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to
the process; decreasing the break deallocates memory.

brk() sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the
process does not exceed its maximum data size (see setrlimit(2)).

sbrk() increments the program's data space by increment bytes. Calling sbrk() with an increment of 0 can be used to find the current loca‐
tion of the program break.
My problem is how does this translate to a stack piece of memory? For example if the memory block is at 0x0f000 and the heap is empty I would assume the sblk(0) would return 0x0f000 and then if I call sblk(size) it will return 0x0f000 + size or -1 for out of memory? Is this basically correct? I'm also thinking I need a way to track the end point of my memory block so I don't exceed it.

Hopefully someone can confirm or point me in the right direction

DarkElvenAngel
Posts: 2275
Joined: Tue Mar 20, 2018 9:53 pm

Re: Need help understanding sbrk

Wed Aug 03, 2022 7:20 pm

pointer math is giving me a head ache...

I've come up with this function however the compiler doesn't like it

Code: Select all

typedef long intptr_t;
#define HEAP_SIZE 1024*10
char HEAP[HEAP_SIZE] = { 0 }; 

void *sbrk(intptr_t increment)
{
	void* start = &HEAP;
	static void* index = &HEAP;
	if (increment == 0) return index;
	if (increment > 0)
	{
		if ((index + increment) > &HEAP[HEAP_SIZE]) return (void*) -1;
	} else {
		if ((index + increment) < &HEAP[0]) return (void*) -1;
	}
	index += increment;
	return (void *)index;
}

User avatar
jahboater
Posts: 8216
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: Need help understanding sbrk

Wed Aug 03, 2022 8:01 pm

I don't think you can do arithmetic on a void* pointer because the compiler doesn't know what size of object it is pointing to.

Also you don't need the & before HEAP in the start and index initialization (the value of an array symbol when used in an expression is the address of the first element).

There is a standard C intptr_t type, so I think its best not to create your own.

DarkElvenAngel
Posts: 2275
Joined: Tue Mar 20, 2018 9:53 pm

Re: Need help understanding sbrk

Wed Aug 03, 2022 8:16 pm

jahboater wrote:
Wed Aug 03, 2022 8:01 pm
I don't think you can do arithmetic on a void* pointer because the compiler doesn't know what size of object it is pointing to.

Also you don't need the & before HEAP in the start and index initialization (the value of an array symbol when used in an expression is the address of the first element).

There is a standard C intptr_t type, so I think its best not to create your own.
I'll try using char* pointer instead and see if that helps. That's a handy tip. [ This cleaned up all the errors ]

I'm not sure about intptr_t I'm compiling without standard headers

DarkElvenAngel
Posts: 2275
Joined: Tue Mar 20, 2018 9:53 pm

Re: Need help understanding sbrk

Wed Aug 03, 2022 9:12 pm

Looking at the memory allocator and the results I think they are suitable however the alignment is set at 16 bytes this is fine for a Pi with more memory however the Pico is also a target for this would alignment to 4 bytes be suitable.

User avatar
jahboater
Posts: 8216
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: Need help understanding sbrk

Wed Aug 03, 2022 9:20 pm

GCC defines __BIGGEST_ALIGNMENT__ which may be of interest.
C++ has a more formal ...
https://en.cppreference.com/w/cpp/types/max_align_t

Doesn't ARMv6 have some things that require 8 byte alignment such as LDD ?
__BIGGEST_ALIGNMENT__ is 8 on ARMv6.
8 is needed for double of course but the Pico doesn't need that.

DarkElvenAngel
Posts: 2275
Joined: Tue Mar 20, 2018 9:53 pm

Re: Need help understanding sbrk

Thu Aug 04, 2022 2:43 am

I finally understand what I'm doing and how it works. I figured out one reason it wasn't working was I was working from a flawed example. I've read many other articles and I see why they didn't make sense.

As for the alignment I'm not sure what use, I'm thinking 4 bytes make sense? Since int is the most popular and I won't be using double. This is meant to run inside a VM that will have limited memory so I don't want to waste to much with alignment bytes. At least now I can acquire memory from the system within the VM when doing system calls.

My final working function is this

Code: Select all

void *sbrk(intptr_t increment)
{
	static char* index = HEAP;
	if (increment == 0) return (void*)index;
	if (increment > 0)
	{
		if ((index + increment) > &HEAP[HEAP_SIZE]) return (void*) -1;
	} else {
		if ((index + increment) < &HEAP[0]) return (void*) -1;
	}
	index += increment;
	return (void *)index;
}
Thanks for the help

trejan
Posts: 4742
Joined: Tue Jul 02, 2019 2:28 pm

Re: Need help understanding sbrk

Thu Aug 04, 2022 4:09 am

DarkElvenAngel wrote:
Thu Aug 04, 2022 2:43 am

Code: Select all

	index += increment;
	return (void *)index;
You're returning the wrong value. sbrk() returns the old break address i.e. index before adding increment.
On success, sbrk() returns the previous program break. (If the break was increased, then this value is a pointer to the start of the newly allocated memory). On error, (void *) -1 is returned, and errno is set to ENOMEM.

User avatar
jahboater
Posts: 8216
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: Need help understanding sbrk

Thu Aug 04, 2022 7:44 am

DarkElvenAngel wrote:
Thu Aug 04, 2022 2:43 am
As for the alignment I'm not sure what use, I'm thinking 4 bytes make sense? Since int is the most popular and I won't be using double. This is meant to run inside a VM that will have limited memory so I don't want to waste to much with alignment bytes.
The alignment of blocks returned by malloc has to be suitable for the worst case, not the most popular case.

If you get it wrong, programs usually fail with "bus error". However the more modern ARM CPU's usually don't care about alignment apart from a small performance penalty perhaps. You can tell if alignment is required by seeing if __ARM_FEATURE_UNALIGNED is set by the compiler.
ARM 64-bit happily loads 16-byte vectors from any address.

I looked it up and the ARM LDD instruction requires even word alignment which is 8-byte alignment. LDD loads two consecutive words from storage.
There may be others I don't know of, even if you are not using double-precision floats.

I suppose in a VM you don't have to worry about cache lines.

The glibc malloc aligns to 32 bytes on Intel 64-bit, 16 bytes on ARM 64-bit, and 8 bytes on ARM 32-bit.

For interest, the C library malloc uses mmap() to get blocks above 128K.

DarkElvenAngel
Posts: 2275
Joined: Tue Mar 20, 2018 9:53 pm

Re: Need help understanding sbrk

Thu Aug 04, 2022 12:50 pm

trejan wrote:
Thu Aug 04, 2022 4:09 am
DarkElvenAngel wrote:
Thu Aug 04, 2022 2:43 am

Code: Select all

	index += increment;
	return (void *)index;
You're returning the wrong value. sbrk() returns the old break address i.e. index before adding increment.
On success, sbrk() returns the previous program break. (If the break was increased, then this value is a pointer to the start of the newly allocated memory). On error, (void *) -1 is returned, and errno is set to ENOMEM.
This explains what I was seeing with memory in the wrong spot so I used a call to get the position first and that solves it. I didn't see I implemented the sbrk() function incorrectly

This seems to work correctly now

Code: Select all

void *sbrk(intptr_t increment)
{
	static char* index = HEAP;
	char* start = index;
	if (increment == 0) return (void*)index;
	if (increment > 0)
	{
		if ((index + increment) > &HEAP[HEAP_SIZE]) return (void*) -1;
	} else {
		if ((index + increment) < &HEAP[0]) return (void*) -1;
	}
	index += increment;
	return (void *)start;
}

Return to “C/C++”