Allow overriding malloc and free at compile time #1917

Addresses the suggestion by real_or_random here: #1789 (comment)

Allows to override the default malloc and free at compile time using -DSECP256K1_MALLOC=my_malloc -DSECP256K1_FREE=my_free. With helps users that can not link against malloc, such as the rust-secp256k1 wasm build.

Afaict, this is complementary to #1095 and #1461: with the macros defined, the library needs nothing from <stdlib.h> besides abort in the default callbacks. But #1461 would need to keep the allocating functions enabled when SECP256K1_MALLOC is defined.

There are a few things to note here:

Do We Want to Provide More Guarantees than malloc/free?

The docs added in the current version of the PR say that the semantics should be the same as malloc/free. This can be quite demanding if you don't have a full version of malloc available.

We could provide more guarantees for specific use cases. For example, have a SECP256K1_SIMPLE_MALLOC and guarantee that all frees will be in a row (so a simple bump allocator can be used). SECP256K1_SIMPLE_MALLOC could just be defined as SECP256K1_MALLOC. I wonder if this is overkill, but providing such guarantees for SECP256K1_MALLOC in general may bite us in the future.

Another subtle detail is that free(NULL) is guaranteed to be a noop, but this is exactly the kind of thing that a caller may get wrong, so maybe we should simply avoid calling free on NULL pointers.

New Approach for Overrides

One thing to note here is that diverges from our previous approach of overriding functions that we used for external error callbacks: requiring the user to set a flag macro such as USE_EXTERNAL_DEFAULT_CALLBACKS and provide some symbols at link time (https://github.com/bitcoin-core/secp256k1/pull/595/)

When I worked on #595, the approach in this PR (namely simply using macro for the function call) didn't occur to me. I only saw this later in another crypto library (I can't remember which one).

I think the two approaches functionally equivalent but I believe this one here is more straight-forward and a bit more convenient to use (in particular if you can pass -include to the compiler). So if others agree with this assessment, we could use this one here also for the external callbacks and deprecate USE_EXTERNAL_DEFAULT_CALLBACKS. Or we stick with the USE_ approach if we find that nicer (or simply good enough not to bother with changing approaches).

We want more overrides in the futures, e.g., a compile-time override for SHA256, and potentially overrides for fprintf and abort that are more fine-grained than overriding the entire external callback. So it's probably good to pick a good "design" now.

What If You Really Don't Have malloc?

We also need to deal with this situation (probably in a separate PR). There should probably be a macro SECP256K1_HAS_MALLOC or SECP256K1_NO_MALLOC. Now that I write this, I realize it's actually almost exactly #1095, so we should pick up the work on that again.

Thanks for the helpful feedback @real-or-random , per your comment in #1789 I made the change to SECP256K1_FREE so it now also receives the size of the allocation.

This can be quite demanding if you don't have a full version of malloc available.

Makes sense. I documented only minimal guarantees instead. So SECP256K1_MALLOC is called with size > 0, SECP256K1_FREE is called exactly once per allocation and no ordering guarantees. free is also never called on NULL. I left out the SECP256K1_SIMPLE_MALLOC idea for now. I looked into implementing a simple bump allocator but would like to leave that for a follow-up.

So if others agree with this assessment, we could use this one here also for the external callbacks and deprecate USE_EXTERNAL_DEFAULT_CALLBACKS.

I personally prefer this. The second commit adds SECP256K1_ILLEGAL_CALLBACK_FN and SECP256K1_ERROR_CALLBACK_FN and reimplements USE_EXTERNAL_DEFAULT_CALLBACKS on top of them and marks it as deprecated. Let me know if you think that is the right approach.

There should probably be a macro SECP256K1_HAS_MALLOC or SECP256K1_NO_MALLOC.

Added SECP256K1_NO_MALLOC here now. It removes all uses of malloc and free. I can pull it out into a separate PR if you like I didn't want to open yet another PR without some high level feedback if this is looking good overall. There is also a CI job to test it.

I will take a deeper look at #1461 for the includes part. Could you rebase it maybe? Let me know if you think these changes should be coordinated in some special way.

Concept ACK

I think the two approaches functionally equivalent but I believe this one here is more straight-forward and a bit more convenient to use (in particular if you can pass -include to the compiler). So if others agree with this assessment, we could use this one here also for the external callbacks and deprecate USE_EXTERNAL_DEFAULT_CALLBACKS. Or we stick with the USE_ approach if we find that nicer (or simply good enough not to bother with changing approaches).

+1 on preferring the approach in this PR. From my past I'm personally more familiar with the current way on master (i.e. provide symbols at link time), but using macros for function calls seems indeed a bit nicer and more convenient to use, and seem to have no drawbacks.

The CI job where I had added the coverage for NO_MALLOC failed because the precompute tools use checked_malloc. There are a number of ways to fix this but I followed the way USE_EXTERNAL_CALLBACKS is ignored in tests.c since that seemed to be pretty comparable.

Every size passed to SECP256K1_FREE matches its allocation, and I suggest this PR's CI allocator check that too.

I wanted to know whether the new size argument is right everywhere, since a Rust deallocator relies on it. Across tests, noverify_tests, exhaustive_tests, the examples and a short run of the benchmarks, about 58,700 allocations were all freed exactly once, each with the size it was allocated with. None was freed as NULL. A build with ASan and UBSan gave the same result. The library calls no malloc or free directly.

secp256k1_ci_free in ci/malloc_override.h checks that the size is nonzero, not that it matches the allocation, so a wrong size would pass CI. When I passed 8 bytes too few in secp256k1_context_destroy, my allocator caught it. A CI allocator that keeps the size in a small header in front of each block, and asserts it on free, would catch that too. I measured f933871 on macOS arm64 with Apple clang, all modules on, through an allocator that records each allocation's size and compares it on free; I can share the allocator and the logs.

f933871a79a09c1eb408960d7274d96dd67bd91b needs rebase

BTW this PR works perfectly for the rust-bindings. I believe it lets us remove every single patch we've applied libsecp256k1 and just vendor the code directly. (Well, we still have to #define out printf and still need to do a sed pass to inject version numbers into all the exported symbols.)

Rebased

secp256k1_ci_free in ci/malloc_override.h checks that the size is nonzero, not that it matches the allocation, so a wrong size would pass CI.

Thanks, seemed fine to add a check for this. The CI allocator now stores the size in a header in front of each block and asserts on free that it matches.

The size check works: with the new ci/malloc_override.h, a wrong size passed to SECP256K1_FREE aborts the tests.

I checked it on 55cce7845d, with clang on macOS arm64, by making secp256k1_context_destroy pass sizeof(secp256k1_context) + 1 to checked_free. With the new header, tests, noverify_tests and exhaustive_tests all stop on assert(alloc_size == size). With the header from the previous push and the same change, all three pass.

Thanks for adding it.

ACK 55cce7845d9d71680a55212ee1f5b336756fc96b; successfully ran local tests, and tried integrating into rust-secp successfully