4 ms·

This is an extremely good question, and I do not have a satisfying answer. Note that `malloc` is special in the C standard as well, and AFAIK it is not possibl

This is an extremely good question, and I do not have a satisfying answer. Note that `malloc` is special in the C standard as well, and AFAIK it is not possible to implement `malloc` in standard C at all. Heck, there are several models of C out there where you cannot implement `memcpy`.

mbel 8y ago
> Note that `malloc` is special in the C standard as well, and AFAIK it is not possible to implement `malloc` in standard C at all. malloc() is usually implemented in C [0] and to be honest I'm not sure why do you think it wouldn't be? Of course you need OS API calls to actually get some memory (unless you want to operate on statically defined memory buffer) but well it's still C. [0] https://github.com/lattera/glibc/blob/master/malloc/malloc.c https://github.com/lattera/glibc/blob/master/malloc/malloc.c
- pjmlp 8y ago
  That linked implementation relies on OS primitives (sysmalloc()), implemented in C, Assembly or whatever was used to write the OS. Try to implement malloc() on bare metal, without using either Assembly or language extensions.
- TheCoelacanth 8y ago
  It's C, but it's not standard C. It uses implementation defined behavior. Every compiler has some implementation defined behavior because they would be much less useful without it.
amluto 8y ago
Hmm. My answer would be “you don’t, unless you are willing to accidentally give stronger guarantees”. I believe that standard C11 permits a function to allocate malloc-style from a big static arena of type array of char. You can even implement free() and reuse the memory. But then all the allocations are really pointers into the arena, and certain operations that should be UB aren’t if you use this type of malloc. But then you throw something like __attribute__((malloc)) on it, and define that as transforming the return value into a new Pointer that is in a different, fresh allocation. And you declare that access to the range of the arena in use is UB until free() gets called. I don’t know how well this fits into the formalism, but I think that a complete formal memory model would need to understand that free() is permitted to treat its argument as a pointer into a large array of char, but that free()’s caller is not.

mbel 8y ago

> Note that `malloc` is special in the C standard as well, and AFAIK it is not possible to implement `malloc` in standard C at all. malloc() is usually implemented in C [0] and to be honest I'm not sure why do you think it wouldn't be? Of course you need OS API calls to actually get some memory (unless you want to operate on statically defined memory buffer) but well it's still C. [0] https://github.com/lattera/glibc/blob/master/malloc/malloc.c https://github.com/lattera/glibc/blob/master/malloc/malloc.c

pjmlp 8y ago
That linked implementation relies on OS primitives (sysmalloc()), implemented in C, Assembly or whatever was used to write the OS. Try to implement malloc() on bare metal, without using either Assembly or language extensions.
TheCoelacanth 8y ago
It's C, but it's not standard C. It uses implementation defined behavior. Every compiler has some implementation defined behavior because they would be much less useful without it.

amluto 8y ago

Hmm. My answer would be “you don’t, unless you are willing to accidentally give stronger guarantees”. I believe that standard C11 permits a function to allocate malloc-style from a big static arena of type array of char. You can even implement free() and reuse the memory. But then all the allocations are really pointers into the arena, and certain operations that should be UB aren’t if you use this type of malloc. But then you throw something like __attribute__((malloc)) on it, and define that as transforming the return value into a new Pointer that is in a different, fresh allocation. And you declare that access to the range of the arena in use is UB until free() gets called. I don’t know how well this fits into the formalism, but I think that a complete formal memory model would need to understand that free() is permitted to treat its argument as a pointer into a large array of char, but that free()’s caller is not.