(2020/08)
The current implementation of malloc aims at being tiny. Verly low memory overhead (4Bytes per malloc), no usage of sycalls, no mmap or setbrk.(!)
It uses a preallocated buffer, which has to be defined at compile time. The buffer can be located in either the bss section, so it is allocated by the kernel, along with other globals. Since in most cases there is a page allocated for this section, the space is preallocated in each case, and can be used by the "minibuf".
Or the buffer can be located on the stack as well, via the option "globals_on_stack"). Sparse (allocated and free'd) areas are not reused. Instead, when all areas below, say, X, are freed, they are freed in a whole. The intention here is on tiny tools, which only allocate a few variables, where the sizes are more or less known, and ovrall below, say, a maximum of 64kB. It is not the right malloc for other applications.
There are two "mallocs" witin minilib now, which use dynamic allocations:
-
map_protected map_protected maps one (or serveral) page(s)(here 4kB per page) in memory, and guards the page(s) with a protected (PROT_NONE_ page before and after.
The intention is having a memory area for user input, where an over- or underflow won't e.g. overwrite return adresses at the stack.
-
malloc_brk malloc_brk allocates space via moving the program’s break. malloc_brk, however, doesn’t keep track of free’d areas. Here the intention is to 1. Be able to free several allocated areas in one call, by setting the brk back again. And 2., when a malloc’ed area is reallocated, it is possible to simply enlarge the area, without copying.
This is used in 'scandir', where the contents of a directory are read directly into a mallocated area, and when the allocated buffer shows up to be too small, the allocated area is simply enlarged, until the directory is read in. Since the function sorts the entries (if requested) after the read in, all names have to be kept in memory.
There is only one copy of the data done, from kernel to userspace. (When no filter is used). And it is not neccessary to free every direntry, instead, a free of the whole list of dirents can be done with one call. However, again, this obviously will only work, when the whole area can be freed at once. (Subsequent calls to malloc_brk don't allow freeing the areas before).
Atm I'm working at a 'usual' malloc. (Pooled, free lists, and so on). When I'm going to finish this, I cannot say now. I simply do have other obligations as well.
However, it is possible to use any malloc implementation, you can find. (Or to simply use mmap.)
-
The only funcion, which uses a malloc within minilib at all, is 'scandir'. (Which uses malloc_brk.) All other functions use the predefined "mini_buf". (e.g. printf, conversions, andsoon)
-
Furthermore, the curent malloc implementation of minilib does use the fixed buffer "mini_buf", and no calls to mmap or brk are done at all.
Therefore, you can plug in any existing malloc implementation you wish, without having to fear, this will interfere in any way. (If you do not use 'scandir') (E.g. jemalloc, demalloc, and so on. Just do a search at github, there are countless implementations, many very mature).
Finally, somehow I'd say malloc is not really a system function at all. There have to be done too many assumptions on the usecases. (How many calls to malloc, which average of the sizes, how many free's and reallocations, andsoon) If the usecase would be known, it would be possible to write a optimized version. However, the usage isn't known in advance. Not for a system library. (Would look different, when writing a system layer for e.g. a database..)
So - for now, just have a look at one of the other malloc implementations, (Or use mmap for yourself).
As I said, usage of a existing malloc will not interfere with minilib, so long you don't use malloc_brk, map_protected, mmap, brk, or scandir.
- brk
-
int brk( const void* addr )
Defines: sys_brk
change data segment size
set the brk to addr return 0 on success. conformant brk, when mini_errno is defined return -1 and set errno. if errno isn't available, returns the negative errno value on error
Size: ~66B ../src/memory/brk.c l.8 manpage: brk
- free
-
void free(void p)
*Defines: getbrk sys_brk
free allocated memory Size: ~32B ../src/memory/malloc.c l.168 manpage: free
- free_brk
-
int free_brk()
free all memory, which has been allocated with malloc_brk. Returns 0, if memory has been freed; 1, when there hasn't been any memory allocations with malloc_brk before. Then brk() gives an error, return the return value of brk
- getbrk
-
long getbrk()
get the current brk does either a syscall to brk, or returns the globally saved var
- malloc
-
void* malloc(int size)
a memory allocator
0
switch mini_malloc_minibuf
(Use the global minibuf for "allocations".
Advantage: tiny code, fast, located either in the bss or data segment,
or past the stack(might be fastest).
Disadvantage: Possible to overwrite environmental vsariables when located
at the stack via overflow.
No dynamic allocations, the minibuf has a fixed size.
Here we go.. with the .. well.
Fastes and smallest malloc/free combi ever.
Not the smartest.
Since it isn't exactly a memory allocation,
instead it uses the minilib buf.
Which is allocated by the kernel, and located
either in the bss section, or is allocated on the stack.
(option "globals_on_stack")
When allocated at the stack, the stack is first expanded
within startup_c.c, and the return address of startup_c
discarded. (Jump to exit)
Therefore an overflow of the globals would result in a segfault.
For debugging and analization of mallocs and free's, there's
the option analyzemalloc; which dumps all malloc's and free's to stderr.
Format: Address - size)
This is basically a linked list,
optimized for fast access, allocation of new elements,
and small memory overhead.
Albite the list structure might be hard to recognize.
It is not the right malloc, if you expect
many de- or reallocations.
And it obviously is not the right choose, when
expecting medium to big sized allocations. (> 1 page, here 4kB, as medium sized)
Here we use mbuf from top to bottom as stack.
64 Bytes are left at the bottom as reserve.
Possibly we'd like to complain
about the lack of memory, before we exit.
ATM, the 'free' is really lazy.
It free's memory, but a real 'free' is only commited,
when all memory below a freed area is also freed.
Since the target of minilib atm are tiny tools,
this might be ok.
;) but, as I told before -
probably you should look out for a proper malloc implementation.
It depends on your needs.
I'm not sure yet,
whether another implementation of free would be useful at all.
Overall, I'd really prefer keeping minilib tiny.
Reusing sparse freed memory areas also leads
to a whole bunch of complications.
cache misses, searching complexity,
storage overhead, potentially page faults,
just to name a few.
I'm not sure whether it's worth it.
And the existing malloc implementations
out there are countless.
;) It's sometimes smarter to stay special,
albite in this case this means the opposite.
/misc
The memory layout looks like this:
mlgl->ibuf and mlgl->mbuf do point to the same address range.
mlgl->ibuf is provided for alignment and faster access to the int values.
flag prev free is the first bit in size. (0x8000, eq 1000 0000 0000 0000 binary when free),
(mbufsize)
```
size data size mini_buf size
8008dataxxxx0004data8000
Size: ~173B ../src/memory/malloc.c l.142 manpage: malloc
- malloc_brk
-
void* malloc_brk(int size)
Defines: sys_brk getbrk
allocate via setting the brk free and realloc can be used normally. The intention of malloc_brk is for subsequent calls to realloc. The saved data has not to be copied, instead realloc just writes the new size and sets the brk accordingly. if the break is saved before one or more calls to malloc_brk, the allocated memory can also be free'd by setting the brk to the saved value with brk(saved_brk) free_brk() free's all memory, which has been allocated with malloc_brk
- map_protected
-
void* map_protected(int len)
Defines: mprotect mmap
allocate a buffer, which is surrounded by protected pages. mprotect(PROT_NONE) When there is a buffer overflow, neither the stack, nor other structures can be overwritten. Instead the overflow (or underflow) touches the next protected page, what results in a segfault. Most probably you'd like to catch the segfault signal. (By installing a segfault signal handler) The size is always a multiple of the system's pagesize, 4kB here. The len of the mapped memory area is rounded up to the next pagesize. The mapped area can only be free'd by call(s) to unmap_protected, neither realloc nor free are allowed. There is one page before, and one page after the mapped area protected with PROT_NONE, and len rounded up to the next pagebreak. So this is the overhead. If an error occures, errno is set (when defined by the switch mini_errno), and -1 returned, or the negative errno value, when errno isn't defined.
- memcmp
-
int memcmp(const void* c1,const void* c2,int len)
compare bytes in memory Size: ~44B ../src/memory/memcmp.c l.3 manpage: memcmp
- memcpy
-
void* memcpy( void*d, const void s, int n )
*copy bytes in memory Size: ~84B ../src/memory/memcpy.c l.4 manpage: memcpy
- memfd_create
-
int memfd_create( const char uname_ptr, unsigned int flags)
*create an anonymous file Size: ~59B ../include/syscall_stubs.h l.191
- memfrob
-
void* memfrob(void* s, unsigned int len)
frobnicate (encrypt) a memory area
frob string; xor every char with 42
Size: ~78B ../src/memory/memfrob.c l.4
- memmove
-
void* memmove(void dest, const void *src, int n)
*copy bytes in memory with overlapping areas Size: ~88B ../src/memory/memmove.c l.3 manpage: memmove
- memset
-
void memset( void *s, int c, int n)
*set bytes in memory Size: ~90B ../src/memory/memset.c l.3 manpage: memset
- mmap
-
void* ATTR_OPT("O0") mmap(void* addr, size_t len, int prot, int flags, int fd, off_t off)
map pages of memory
mmap wrapper address length is rounded up to a multiple of pagesize (4096 Bytes here) for the description, please look up the according manpage errno is only set, when mini_errno is defined if not, on error the negative errno value is returned. (e.g. -22 for "invalid argument")
Size: ~197B ../src/memory/mmap.c l.8 manpage: mmap
- mprotect
-
int mprotect( POINTER a1, POINTER a2, int a3 )
*set protection of memory mapping Size: ~146B ../include/syscall_stubs.h l.254 manpage: mprotect
- mremap
-
void* volatile ATTR_OPT("O0") mremap(void* addr, size_t old_len, size_t new_len, int flags, void* new_addr)
remap a virtual memory address Size: ~162B ../include/mremap.h l.4
- munmap
-
int munmap( void* addr, size_t len)
unmap pages of memory ../include/syscall_stubs.h l.261 manpage: munmap
- realloc
-
void* realloc(void p, int size)
*Defines: 0 getbrk sys_brk
memory reallocator Size: ~636B ../src/memory/malloc.c l.240 manpage: realloc
- sbrk
-
void* sbrk(long incr)
Defines: sys_brk
change data segment size
Set the new brk, increment/decrement by incr bytes. return the old brk on success. conformant sbrk, when mini_errno is defined if no errno is available, returns the negative errno value on error
Size: ~108B ../src/memory/sbrk.c l.9 manpage: sbrk
- splice
-
int splice( int fd_in, loff_t off_in, int fd_out, loff_t *off_out, size_t len, unsigned int flags)
*splice data to/from a pipe Size: ~178B ../include/syscall_stubs.h l.196
- swap
-
void swap(void* a, void* b,int size)
swap a with b, with 'size' bytes swaps integers and longs at once, when size eq sizeof(int/long)
- unmap_protected
-
int unmap_protected(void p, int len)
*Defines: munmap mprotect
free an area, allocated before with map_protected (len must be the same, when at the invocation of map_protected) returns the value of munmap, when an error occures. errno is set, when defined. return 0 on success.