The pervasive effects of C's malloc() and free() on C APIs
utcc.utoronto.ca
utcc.utoronto.ca
Naturally there was a dependency on the exact behavior of the allocator, specifically, that it had to leave a freed block of memory untouched sufficiently long for the caller to be able to use the results. I seem to recall the stipulation was that freed memory was left untouched until the next memory allocation operation. The caller also had to be careful about using or copying the results immediately, before doing too much work.
I have dim memories of people talking about this sort in thing at university in the early 1980s; we were a 4.2 BSD shop. I also recall debugging some old C source code (srogue, which also has BSD heritage) decades later, and encountering use-after-free crashes. There were several instances of this. There were too many to be accidental; it seemed deliberate to me.
I suspect the reason for this "technique" was to relieve the caller of the burden of freeing the memory. It allowed the caller to return variable-length data easily, which couldn't be done if the pointer was to a static data area. And finally it relieved the callee of defining an explicit "free" API.
Frankly I think this is a terrible API style. However, code that used it properly and that was sufficiently careful would actually function properly. But it seems like an incredibly fragile and sloppy way to design a system.
Ex:
struct someStruct* badfunc(){
struct someStruct toReturn;
toReturn.a = foo();
toReturn.b = bar();
return &toReturn;
}
struct someStruct a = *badfunc();
func2(); // This will overwrite the "toReturn"
// from the last call, but as long as the
// struct was copied before any other function
// call, you're probably fine though in
// undefined-behavior land
Either that, or you're talking about strtok (and other non-reentrant functions).
The best version of this is where you allocate a block on your stack then pass that as a pointer up to the next function to use. The one who owns the memory is the one who allocates it (Rust style?). Or, have the linker allocate global blocks works too.
Or do you mean something else by "probably work"? (like, in the sense that it will output "something").
"Source" functions return a malloc'd pointer. You have to manually call free on it, or pass it to a "sink" function (which internally calls free). In C, this is seen in strdup.
C++ took this pattern and formalized it into auto_ptr<>, and later unique_ptr<> when RValue references became a thing in C++11.
Not a good way of doing things. I mean, have fun using Valgrind. Or switching out libc, etc. And what about key material? There you would still have to do a second step of zeroing or junking the memory when done with it anyway.
This was at least a decade before multithreading in C and Unix. But yes this "technique" would have failed miserably in a multithreaded environment.
The problems for the GC languages tend to be fewer but if the wrapper is out of scope but someone grabbed and maintains a hold on the foreign memory directly, they're playing with fire as for when the GC will execute the finalizer hook and make that memory invalid. It's also a frustrating technique when foreign APIs -- particularly in certain graphics contexts -- require allocation threads to be the same as freeing threads, and of course depending on the implementation of free and the GC it might be an expensive operation to have a bunch of them suddenly happen at once when all you were expecting was a new native object and not a bunch of GC work behind the scenes.
For scenarios like you're describing, .NET has SafeHandles for example.
That's more than a bad API design, that's undefined behavior -- squarely in nasal-demons territory. Depending on the compiler, the callee, the caller, or the entire observable universe can be optimized away into a no-op.
But consider the time frame, early 1980s K&R C on 4bsd Unix on a VAX. This predates ANSI/ISO C and Posix. It even predates “nasal demons.” There was no specification; or perhaps the implementation was the specification. The fact was that at some point the bsd allocator did leave freed memory untouched until the next memory allocation operation, and so people wrote programs that relied on this.
Again, I’m not defending this, but this seemed to be the way that some people thought about things. I even remember questioning some code that used memory after having freed it. It was explained to me that this was “safe” because the memory wouldn’t be modified until the next malloc!
Also, remember that BSD was the system where if you did
printf("%s", NULL);
One more common technique from the BSD era (srogue again, but other programs did this too). To save the state of a program, write to a file everything between the base of the data segment to the “break” at the top of the data segment. To restore, just sbrk() to the right size and read it all back in, overwriting everything starting at the base of the data segment. I always found it surprising that this worked, but it worked often enough that people did sh!t like this.
Otherwise I prefer libraries that allow setting the allocation function at least.
That's why even people knew, many C APIs still return dynamic allocated objects or simply let you inject malloc / free if you want more control.
This is a roundabout way to say: if you aspired to provide APIs with zero dynamic allocation, go ahead. But if you find yourself struggling with more complicated code as a result, think about just letting a little bit dynamic allocations may help.
Caller provides memory and function fails if there is to little memory, but writes the the required (variable) amount of memory to an `out length` pointer.
Effectively leading to a common pattern of:
1. call function with empty buffer (or buffer or arbitrary size)
2. allocate buffer
3. call function again with properly sized buffer
4. add a loop if between 1 & 3 the required buffer size can change
its fascinating how well it works for some of it's common use cases and how subtle but badly broken it can be for other use cases :=)
https://docs.microsoft.com/en-us/windows/win32/seccrypto/exa...
They managed to mix both patterns into a ghastly 9 function call!
The example above speaks for itself but I kind of see the "we provide you with memory you need to call 'FreeX' on" and the "call the function twice, once to find out how much memory you need to allocate" patterns to be equally annoying to use.
Callers allocate the right size no matter what OS version, and can only see the fields exposed on the version they were built for.
Anyway, the whole "caller allocates" concept doesn’t work too well in the particular case of `gethostbyname`, which as the author mentions, is a complex struct containing several pointers and double pointers, with a potentially unlimited number of different-length allocations one would have to make!
> If this structure is dynamically allocated by gethostbyname() and returned to the caller, either you need an additional API function to free it or you have to commit to what fields in the structure have to be freed separately, and how
With your approach, wouldn't you need to free all the fields in the structure separately as well? Because, what's the difference between the library allocating the memory -with the problems the article points out- and allocating it yourself?
GCC still supports this with -fpcc-struct-return[1] (though, the modern man page doesn't seem to mention the static return buffer).
Also just because there were no threads back in the day doesn't mean static return buffers were okay. In some cases, invoked signal handlers could still call something and corrupt your statically allocated return buffer. So making any system call after receiving your static return pointer was a footgun to watch out for:
struct foo *bar = some_lib_func();
time(0); /* potential breakage */
void type_init(type *t, [...]);
void type_clear(type *t, [...]);
However, if we are constrained to a C API, it does have one important practical quality in my experience: Because it is always the same, it eases the mental load on both the API's user and the API's implementer, especially if there are many such types involved.
[1] See e.g. https://gmplib.org/manual/Initializing-Integers
Clunky and verbose, yes, error-prone no. The APIs that do that are generally much more clear about ownership, and thus much easier, IMO, to write correct code for. Much worse is the API that returns you a pointer with no obvious mechanism to free it. Is it tied to the lifetime of an input to the function that returned it? Is it a global and this API is completely thread-unsafe? Am I leaking memory?
Exactly, and that’s the right way to do it. In a language without implicit destructors/finalizers, you need a way for callers to say “okay, I’m done with this thing.” And even with GC, you need finalizers to take care of non-memory resources. This may be clunky in C, but that’s what you get in a language that makes you be explicit.
And it goes even further than the article claims: even functions that allocate a flat structure on behalf of the caller and return it should provide a companion function to free it. Reason is that the caller and the called function might have a different idea about what the memory allocator is. That’s rare on unixes, but was reasonably common on Windows with cross-DLL calls (https://codereview.stackexchange.com/questions/153559/safely...)
Also, say a DLL function returns a char pointer containing a string. How would you know whether to call free or delete on it? Or, maybe, the equivalent of free in Frob, the language that DLL happens to be written in?
Not necessarily. The Zig[1] standard library forces callers to provide at runtime an allocator to each data structure or function that allocates. Freeing is then handled either by calling .deinit()—a member function of the datastructure returned (a standard convention)—or, if the function returns a pointer, using the same allocator you passed in to free the returned buffer. C's problem here is it doesn't have namespaces or member functions, so there's a mix of conventions for what the freeing function should be called.
C++ allows this as well for standard library containers, although I've rarely seen it used.
> Also, say a DLL function returns a char pointer containing a string. How would you know whether to call free or delete on it? Or, maybe, the equivalent of free in Frob, the language that DLL happens to be written in?
I have to concede this one. I can't see a way out of this other than documentation.
[1]: https://ziglang.org/
EDIT: assuming we're talking about C++, if not please don't hesitate to corrrect me.
By making ownership part of the API (and ABI).
Sadly C is unable to express this, and thus so are FFI layers.
While multiple statically linked C libs normally use the same allocator, the moment you link in any other language in any way (static,.so) the guarantee is gone.
So you `dart:ffi.allocate` `C-malloc` and rust `std::alloc::alloc` might in the end all use different allocators or might happen to use the same allocator, but as long as you don't carefully control all parts involved the all bets are off.
And it can make a lot of sense to use different allocators in FFI-libraries in some use cases (mainly as a form of optimization).
Which ones? HeapAlloc/HeapFree? LocalAlloc/LocalFree? GlobalAlloc/GlobalFree? CoTaskMemAlloc/CoTaskMemFree? VirtualAlloc/VirtualFree? Something else? If the answer is HeapAlloc/HeapFree, which heap? Should you enable the low-fragmentation heap or not?
The DLL authors should better know what APIs to call internally on their own code.
Nitpick: they're provided by the C runtime library.
For example:
const char* getenv(const char* name);
In Sciter API (https://sciter.com) I am solving this by callback functions:
typedef void string_receiver(const char* s, size_t slen, void* tag);
const char* getenv(const char* name, string_receiver* r, void* tag);
This is a bit ugly on pure C side but it plays quite well with C++ where you can define receiver for std::string for example and define pure C++ version:
std::string getenv(const char* name);
The most comfortable way to do a C API is to make the caller allocate space for return values (that aren't something simply copiable like int), and take a pointer to it as a parameter. The few standard library functions that malloc things are annoying, because you might not want to do that.
> The most comfortable way to do a C API is to make the caller allocate space for return values
That's even worse. How will caller know size of the buffer upfront?
With the callback approach that is trivial - you get the size on call - no need to call the API function twice - for size of the buffer and then for real copy.
But there are performance, security and other issues.
What if it is significantly more performant for getenv() (or whatever) to fetch needed data using alloca (on stack, with fallback to heap/malloc)?
Returning naked pointer is far from being flexible really.
I'm not convinced it's "serious" --- thread-local-storage easily solves that.
Since this structure contains embedded pointers (including two that point to arrays of pointers), there could be quite a lot of things for the caller to call free() on (and in the right order).
Again the solution is simple: Allocate everything at once, so that free() need be called only once on the returned block.
In some ways I think the relative difficulty of using dynamic allocation in C compared to other languages is a good thing --- it forces you to think whether it's really necessary before doing so, and in many cases, it turns out not to be. That way encourages simpler, more efficient code. In contrast, other languages which make it very easy to dynamically allocate (or even do it by default) tend to cause the default efficiency of code written in them to be lower, because it's full of unnecessary dynamic allocations.
What about other cases of exceptional control flow? What happens if a signal arrives while that static area is being used, and the signal handler also needs to use the static area?
There are several options. They all suck.
- Pass in a buffer to be filled by the API. The API can't check the buffer size you gave it. Be mentioned in a CERT security advisory for creating a buffer overflow vulnerability.
- Have the API give you a buffer. Reboot your system regularly to recover the memory leaks.
- Free the buffer before returning it, so the caller is using the buffer after free. Debug memory corruption bugs when someone uses an allocator which overwrites freed buffers.
This is what move semantics are for. You call something, it gives you a thing, and now it's yours to use and release. Needs language support to work well, but is the right answer.
Move semantics is "just" an optimization that makes passing data-owning classes around more efficient. Pre C++11 you'd just return the class by reference to avoid the inefficiency of return by value, but with move semantics you can treat complex types the same as simple ones, and not worry about the efficiency of how you pass them around.
Isn't this literally Rust?
The answer is that Rust has affine types, which is a fancy way of saying that variables are owned exactly once. The borrow checker enforces this property, essentially by making temporary reference copies of the owned object and proving that they never outlive their backing value.
Move semantics are an implementation detail of affine typing, but can also be used (and are successfully applied) outside of purely affine languages like Rust. C++ is probably the most famous example of that, where `std::move` essentially means "extend the lifetime of this value by moving its contents to the lvalue."
As in real life, one of the best ways to cut down on waste (gc load) is to recycle.
For example, when marshaling an object before writing it to a file, makes sense to write it to a scratch buffer before writing it to the file. It's generally on the order of trivial to keep said buffer encapsulated to prevent any caller from dealing with potential pitfalls.
Having clear ownership of the buffer is a big benefit to help reduce any potential issues. You're correct that as a GC approaches perfect, there ceases to be a need for it.
Functions that need to return dynamically sized things take a *PointerScope parameter, which is a struct with two function pointers: malloc() and close().
The api function uses the provided malloc, the caller calls close when they’re done with the returned data.
This can then be used with a bunch of calls (and by the caller itself), and then at the end all the allocations get freed with one simple call.
Obviously the PointerScope would internally need to keep track of what was allocated, so it’s a far from simple struct&code combo, but should provide decent user ergonomics?
Add a create() function too, to create a new PointerScope and you have an entire malloc/free replacing resource management paradigm! ;)
The need to have an opposite function to constructing a new object isn't coming from malloc; it's a resource management problem. fclose(f) doesn't just free FILE *f; it releases some operating system file handle/descriptor, and also removes the object from some global list. (There is one because fflusn(NULL) or process termination is somehow able to flush all streams.)
After a point, it is just personal preference, but in my opinion good C++ code is much much better than good C code. The former actually has tools to express many things about the code.
I usually define my own version of `free()` to check whether the pointer is NULL, free the memory if not, and then set the pointer to NULL. That way if your pointer isn't NULL, it should be pointing somewhere. I believe there are some caveats though, specifically around OOM allocations as memory isn't truly allocated until you go to access it.
C memory is generally quite cool to work with, but those tripping points really will trip you up. It's exceptionally easy to have stuff lingering around indefinitely, even worse when it happens in a loop.
is_alloc: If you have to call is_alloc because you don't know and you get `true` back, you still don't know anything, it could be your memory is live or it could be something else was allocated over your stale pointer.
free_all: This is just ridiculous. Now the heap is completely unusable because your memory could be freed from under you at any time by a concurrent free_all.
The answer I want is a simple one - is _this_ pointer currently pointing to somewhere with allocated memory? The goal would be to avoid double free, or double allocating (and therefore memory leaks).
> free_all: This is just ridiculous. Now the heap is completely unusable because your memory could be freed from under you at any time by a concurrent free_all.
I think you misunderstand. You could have a (contrived) structure like:
typedef struct{ char* a, char** b } s;
s* data = (s*)malloc(sizeof(s));
data->a = (char*)malloc(n * sizeof(char));
data->b = (char**)malloc(l * sizeof(char*));
for(int x = 0; x < l; x++) data->b[x] = (char*)malloc(n * sizeof(char));
I would then imagine a common pattern would be:
s* data = NULL; // Indicate we point to nothing
/* Allocate */
free_all(data); // Free associated memory
data = NULL; // Indicate no memory allocated
s* data = (s*)malloc(sizeof(s));
data->a = y;
data->b = z;
free_all(data);
This doesn't work because you don't know who allocated that memory.
Thread A: free(p)
Thread B: malloc(...) -> p (happens to get the same address)
Thread A: is_alloc(p) -> true
Thread A: free(p) thinking it's not a double free because is_alloc returned true
This scenario is possible because if it wasn't, you wouldn't need is_alloc in the first place. You only "need" it if you've lost track of your memory and have no clue what is allocated and what isn't and you're trying to solve the problem (the wrong way) with these runtime checks.
> I think you misunderstand. You could have a (contrived) structure like: [...]
> Rather than free each of these allocations individually, you would instead have `free_all(data)` (might not be a great name). At compile time the compiler would look at the structure and expand out to be all the free operations as required. Of course you would need the `is_alloc` to test if somebody actually did allocate memory.
If you're going to change the language anyway (changing what the compiler does), just use C++ with unique_ptrs and they do precisely that without is_alloc.
If pointer cycles are a concern (since we're only doing this to avoid proper pointer hygiene in the first place), you could allocate everything within `s` from a private arena and just free the arena.
I obviously haven't fully fleshed it out (I'm not writing an RFC here), but address re-use would be a consideration as you mention.
> You only "need" it if you've lost track of your memory and have no clue what is allocated and what isn't and you're trying to solve the problem (the wrong way) with these runtime checks.
No, you can do:
char* a = (char*)malloc(/**/);
if(a == NULL) printf("error"); // Never runs
/* Any other checks you want to perform */
/* Some processing later */
a[0] = 'a'; // Crash here
> If you're going to change the language anyway (changing what the compiler does), just use C++ with unique_ptrs and they do precisely that without is_alloc.
You don't have to change the way in which the compiler works. You can likely do this with some macros. You would need some way to probe memory allocations though.
Whatever you don't state explicitly is assumed to be like the status quo. You've completely moved the goalposts with each reply.
> No, you can do [...]
Which a simple is_alloc doesn't help with because the allocator doesn't know if the kernel has actually mapped the memory to a physical page.
This requires help from the kernel, which wasn't stated anywhere, nor was this goal stated anywhere.
> You don't have to change the way in which the compiler works. You can likely do this with some macros.
You can't reflect over a struct in C with macros. You can maybe build something that works with some macro hacks that require you to declare each auto-cleaned field with a special macro.
This again is completely different from your previously stated idea that you just declare a struct with raw pointers and the compiler generates the appropriate free() calls.