scratch space: use single allocation

apoelstra commented at 10:20 pm on March 13, 2019: contributor

in src/scratch_impl.h:32 in d5df0210bf outdated

28@@ -28,6 +29,9 @@ static secp256k1_scratch* secp256k1_scratch_create(const secp256k1_callback* err
29 static void secp256k1_scratch_destroy(secp256k1_scratch* scratch) {
30     if (scratch != NULL) {
31         VERIFY_CHECK(scratch->frame == 0);
32+        if (memcmp(scratch->magic, "scratch", 8) != 0) {
33+            return;
34+        }

jonasnick commented at 10:35 am on March 14, 2019:

how about setting the magic here back to 0s?

in src/scratch_impl.h:73 in d5df0210bf outdated

87@@ -72,6 +88,10 @@ static void *secp256k1_scratch_alloc(secp256k1_scratch* scratch, size_t size) {
88     size_t frame = scratch->frame - 1;
89     size = ((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT;
90 
91+    if (memcmp(scratch->magic, "scratch", 8) != 0) {

jonasnick commented at 10:39 am on March 14, 2019:

Perhaps this should happen before accessing scratch->frame?

in src/tests.c:390 in 548205ec54 outdated

305     /* cleanup */
306-    secp256k1_scratch_space_destroy(scratch);
307+    secp256k1_scratch_space_destroy(none, scratch);
308+    CHECK(ecount == 0);
309+
310+    /* try to use badly initialized scratch space */

jonasnick commented at 10:56 am on March 14, 2019:

should be done for the other functions as well not just scratch_max_allocation or we reduce fraction of lines covered by tests.

in src/scratch.h:14 in 548205ec54 outdated

11@@ -12,28 +12,29 @@
12 /* The typedef is used internally; the struct name is used in the public API
13  * (where it is exposed as a different typedef) */
14 typedef struct secp256k1_scratch_space_struct {
15-    void *data[SECP256K1_SCRATCH_MAX_FRAMES];
16+    unsigned char magic[8];

real-or-random commented at 1:11 pm on March 14, 2019:

Probably not this PR but what do people think about randomizing this? Then it could protect not only against accidental misuse but also against stack smashing etc. This is just a random thought, I haven’t really thought about whether it makes sense or not.

apoelstra commented at 1:16 pm on May 25, 2019:

Not this PR :)

in src/scratch_impl.h:19 in 548205ec54 outdated

18@@ -19,22 +19,32 @@ static secp256k1_scratch* secp256k1_scratch_create(const secp256k1_callback* err
19     secp256k1_scratch* ret = (secp256k1_scratch*)checked_malloc(error_callback, sizeof(*ret));

real-or-random commented at 1:27 pm on March 14, 2019:

Can we unify this malloc with the other one too? Also, scratch_crate kind of promises to allocate at most max_size bytes but we allocate more.

apoelstra commented at 2:32 pm on March 14, 2019:

I guess we should rename max_size … the question is whether it will be more annoying to the user if (a) the function allocates more than they tell it to; (b) the function allocates exactly what they say, but gives them less scratch space than they intended.

My guess is that (a) is the better way to go here, but we should document this.

As for unifying the malloc calls, yeah, sure, I can do that.

real-or-random commented at 1:36 pm on March 14, 2019: contributor

Wouldn’t all of that be easier if we just checked the canary only at top-level, i.e., in exposed API functions (like we use ARG_CHECK only in exposed functions?)

in src/scratch_impl.h:66 in 548205ec54 outdated

63+        secp256k1_callback_call(error_callback, "invalid scratch space");
64+        return 0;
65+    }
66+
67+    if (n <= secp256k1_scratch_max_allocation(error_callback, scratch, objects)) {
68         n += objects * ALIGNMENT;

real-or-random commented at 1:50 pm on March 14, 2019:

Isn’t that too much? To store an array of objects things of type t, we need objects * sizeof(t) bytes of contiguous aligned memory. But there’s no need to care about alignment here, because the stack frames are aligned already, no?

apoelstra commented at 2:42 pm on March 14, 2019:

We allocate multiple objects within one frame.

real-or-random commented at 9:24 pm on March 14, 2019:

Ah nevermind, I just understood the API…

I guess objects * (ALIGNMENT - 1) is still enough but that’s not much of a difference.

apoelstra commented at 11:29 pm on March 14, 2019:

(objects - 1) * ALIGNMENT you mean :). I’m going to leave this be, because otherwise we get into thorny issues thinking about what happens when objects == 0 and also we’d have to change it in a bunch of places. And it’s only 16 bytes.

real-or-random commented at 11:44 pm on March 14, 2019:

I really meant objects * (ALIGNMENT - 1). We’re rounding up to a multiple of ALIGNMENT, so at most by ALIGNMENT - 1… But yes, just leave it, it’s not worth the hassle.

apoelstra commented at 3:36 pm on March 15, 2019:

Oh! Yeah, I see. But did you further mean (objects - 1) * (ALIGNMENT - 1) since the first object does not require alignment (as the frame will already be aligned)?

I’ll add a commit to do ALIGNMENT-1 since that’s quick and easy and doesn’t create any new edge cases.

real-or-random commented at 4:18 pm on March 15, 2019:

Oh! Yeah, I see. But did you further mean (objects - 1) * (ALIGNMENT - 1) since the first object does not require alignment (as the frame will already be aligned)?

Well, if the frame will already be aligned, then (objects - 1) * (ALIGNMENT - 1) is fine and I think objects == 0 should just be rejected. The problem is that now that we just have one malloc call, it’s not guaranteed that the frame is aligned. (edit: The first frame yes but not the second one, etc).

apoelstra commented at 5:05 pm on March 15, 2019:

Oh, shit, yes, I think that’s actually a bug in the current code. I need to add alignment when “allocating” frames as well.

apoelstra commented at 2:16 pm on May 25, 2019:

Fixed by eliminating frames.

apoelstra commented at 2:33 pm on March 14, 2019: contributor

Addressed jonas’ nits.

apoelstra commented at 2:43 pm on March 14, 2019: contributor

Addressed Tim’s nits

apoelstra commented at 8:29 pm on March 14, 2019: contributor

Tim, regarding doing these checks only at the endpoints, the problem is that the user-level “endpoints” are everything that might use a scratch space, including everything that might use ecmult_multi. So this set is unbounded and it’s something we’d have to maintain going forward.

This isn’t a big deal; we already have this situation for e.g. context objects where every new function needs to ARG_CHECK that the appropriate precomp tables are initialized. But it’s annoying and I think this situation is simpler/more maintainable.

real-or-random commented at 8:52 pm on March 14, 2019: contributor

Uh, I haven’t looked at it from that point of view. Agreed, checking it deep in the call tree needs less duplicated code. It’s is less consistent with what we do now for ARG_CHECKs though. But as you say, that’s maybe because it was not the best design choice.

apoelstra commented at 8:55 pm on March 14, 2019: contributor

My view is that for the context stuff it’s necessary to have so much duplication because different functions have different precomp requirements. In this case this is sanity checking that really shouldn’t concern any code outside of the scratch space module.

real-or-random commented at 0:19 am on March 15, 2019: contributor

It should be noted that this PR fixes the following bug (for which I had the description text in some open editor windows already but Andrew fixed it faster than I managed to report it. :+1: )

Create context ctx with default_error_callback
Create scratch space s with ctx.
Change error_callback of ctx to cb
Trigger a call to secp256k1_ecmult_multi_var(ctx,..., which will call scratch_space_allocate_frame. Assume checked_malloc fails.

Expected: cb is called as error callback

Actual: default_error_callback is called as error callback

in src/tests.c:361 in c9f56cc9de outdated

286-    CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 500); /* 500 - ALIGNMENT */
287-    CHECK(secp256k1_scratch_alloc(scratch, 500) != NULL);
288-    CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL);
289+    CHECK(secp256k1_scratch_allocate_frame(&none->error_callback, scratch, 500, 1) == 1);
290+    CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) < 500); /* 500 - ALIGNMENT */
291+    CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) != NULL);

jonasnick commented at 2:07 pm on March 18, 2019:

How about checking here that the result % ALIGNMENT = 0?

jonasnick commented at 2:32 pm on March 18, 2019:

Could also be checked after secp256k1_scratch_space_create

apoelstra commented at 1:21 pm on May 25, 2019:

Am I allowed to use % on a pointer? That seems unlikely to be meaningful.

apoelstra commented at 2:16 pm on May 25, 2019:

Fixed - check scratch->alloc_size

real-or-random commented at 2:20 pm on March 18, 2019: contributor

I discussed this with @jonasnick: We’re not sure what the point of the frames still is when there is only a single malloc now. Maybe there is one but it seems that everything that can be done with frames can be done with similar programming ergonomics without frames.

If we keep frames, then I think the internal API should be documented a little more because it’s not immediately clear how to use it. In particular the wording is somewhat confusing: we “allocate” frames and “alloc(cate)” objects but then e.g., what does the “allocation” in “max_allocation” then give you? All of this is well-defined in the end but one needs to read the code to figure it out.

in src/tests.c:282 in c9f56cc9de outdated

285-    CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1 == 1));
286-    CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 500); /* 500 - ALIGNMENT */
287-    CHECK(secp256k1_scratch_alloc(scratch, 500) != NULL);
288-    CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL);
289+    CHECK(secp256k1_scratch_allocate_frame(&none->error_callback, scratch, 500, 1) == 1);
290+    CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) < 500); /* 500 - ALIGNMENT */

real-or-random commented at 2:27 pm on March 18, 2019:

500 - (ALIGNMENT - 1)?

in src/tests.c:284 in c9f56cc9de outdated

287-    CHECK(secp256k1_scratch_alloc(scratch, 500) != NULL);
288-    CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL);
289+    CHECK(secp256k1_scratch_allocate_frame(&none->error_callback, scratch, 500, 1) == 1);
290+    CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) < 500); /* 500 - ALIGNMENT */
291+    CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) != NULL);
292+    CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) == NULL);

real-or-random commented at 2:30 pm on March 18, 2019:

Is this supposed to fail because 500 is too large or because that’s the second alloc? (Or both?)

apoelstra commented at 1:21 pm on May 25, 2019:

Because 500 is too large.

in src/tests.c:288 in c9f56cc9de outdated

292+    CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) == NULL);
293 
294-    CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1) == 0);
295+    CHECK(secp256k1_scratch_allocate_frame(&none->error_callback, scratch, 500, 1) == 0);
296 
297     /* ...and this effect is undone by popping the frame */

jonasnick commented at 2:31 pm on March 18, 2019:

Perhaps check that effect is undone by comparing the resulting scratch space fields with original fields (frame and data)

apoelstra commented at 2:20 pm on May 25, 2019:

Probably overkill now that only alloc_size ever actually changes. Added checks that alloc_size is 0 and nonzero when we expect it.

in src/tests.c:281 in c9f56cc9de outdated

284     /* ...but pushing a new stack frame does affect the max allocation */
285-    CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1 == 1));
286-    CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 500); /* 500 - ALIGNMENT */
287-    CHECK(secp256k1_scratch_alloc(scratch, 500) != NULL);
288-    CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL);
289+    CHECK(secp256k1_scratch_allocate_frame(&none->error_callback, scratch, 500, 1) == 1);

real-or-random commented at 2:33 pm on March 18, 2019:

Fun that the old code was (basically) equivalent… :D

in src/scratch_impl.h:104 in c9f56cc9de outdated

104+    }
105+
106+    frame = scratch->frame - 1;
107     size = ((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT;
108 
109     if (scratch->frame == 0 || size + scratch->offset[frame] > scratch->frame_size[frame]) {

jonasnick commented at 2:43 pm on March 18, 2019:

fwiw, this size check can be circumvented by setting size such that size + scratch->offset[frame] overflows

apoelstra commented at 2:16 pm on May 25, 2019:

Fixed with checkpointing

jonasnick commented at 2:46 pm on April 1, 2019: contributor

Needs rebase

apoelstra force-pushed on Apr 7, 2019

apoelstra commented at 5:12 pm on April 7, 2019: contributor

Rebased; squashed fixups

apoelstra commented at 5:13 pm on April 7, 2019: contributor

Will revisit to remove the idea of “frames” entirely.

jonasnick commented at 7:01 pm on April 15, 2019: contributor

it seems that everything that can be done with frames can be done with similar programming ergonomics without frames.

It has the small advantage that you can deallocate the whole frame and not have to deallocate all objects one by one. However, that could be done without the api requiring to give the frame size in advance when allocating it. This seems to be unnecessary right now. But I don’t recall the reason for “frames” either.

gmaxwell cross-referenced this on May 10, 2019 from issue Use a static constant table for small ecmult WINDOW_G sizes. by gmaxwell

apoelstra force-pushed on May 25, 2019

apoelstra commented at 2:17 pm on May 25, 2019: contributor

Rebased and replaced frames with “checkpoints” which don’t require pre-registering an allocation size and don’t have a limit to how many are usable.

apoelstra force-pushed on May 25, 2019

in src/scratch.h:17 in 71d5816c91 outdated

18     void *data;
19-    void *current_frame;
20-    size_t offset[SECP256K1_SCRATCH_MAX_FRAMES];
21-    size_t frame_size[SECP256K1_SCRATCH_MAX_FRAMES];
22-    size_t frame;
23+    /** amount that has been allocated (i.e. `date + offset` is the next

real-or-random commented at 3:41 pm on May 25, 2019:

s/date/data

apoelstra commented at 11:04 pm on May 25, 2019:

fixe

in src/scratch_impl.h:82 in 71d5816c91 outdated

114+    if (memcmp(scratch->magic, "scratch", 8) != 0) {
115+        secp256k1_callback_call(error_callback, "invalid scratch space");
116+        return NULL;
117+    }
118+
119+    size = ((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT;

real-or-random commented at 3:51 pm on May 25, 2019:

once #566 is merged (probably today), this can be replaced by ROUND_TO_ALIGN, see https://github.com/bitcoin-core/secp256k1/blob/0522caac8f28e9eaa19bfebc88e463fc8d409b7c/src/util.h#L96

apoelstra commented at 11:04 pm on May 25, 2019:

done

in src/scratch_impl.h:82 in 71d5816c91 outdated

120+    if (size > scratch->max_size - scratch->alloc_size) {
121         return NULL;
122     }
123-    ret = (void *) ((unsigned char *) scratch->data[frame] + scratch->offset[frame]);
124+    ret = (void *) ((char *) scratch->data + scratch->alloc_size);
125     memset(ret, 0, size);

real-or-random commented at 3:54 pm on May 25, 2019:

Maybe we want to memset the entire scratch space when creating it. Seems simpler and also sets the padding bytes (that are there due to rounding to alignment)

apoelstra commented at 11:02 pm on May 25, 2019:

I’m not sure if it’d be simpler - we’d also have to memset on dealloc, so it’d probably be just as much code and accounting.

real-or-random commented at 3:58 pm on May 25, 2019: contributor

LGTM

scratch space: use single allocation 92a48a764d

scratch: add magic bytes to beginning of structure 0be1a4ae62

scratch space: thread `error_callback` into all scratch space functions

Use it when checking magic bytes

c2b028a281

scratch: unify allocations 5a4bc0bb95

scratch: rename `max_size` to `size`, document that extra will actually be allocated a7a164f2c6

scratch: save a couple bytes of unnecessarily-allocated memory 7623cf2b97

apoelstra force-pushed on May 25, 2019

apoelstra commented at 11:05 pm on May 25, 2019: contributor

Rebased, fixed date/data typo, used ROUND_TO_ALIGN in place of manual alignment calculations.

scratch: replace frames with "checkpoint" system 98836b11f0

apoelstra force-pushed on May 26, 2019

gmaxwell commented at 10:09 am on May 26, 2019: contributor

ACK

gmaxwell merged this on May 26, 2019

gmaxwell closed this on May 26, 2019

gmaxwell referenced this in commit 6c36de7a33 on May 26, 2019

sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa

fanquake referenced this in commit 8c97780db8 on Jun 13, 2020

sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020

ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020

real-or-random cross-referenced this on Oct 26, 2020 from issue Prevent arithmetic on NULL pointer if the scratch space is too small by Fabcien

UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021

5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021

gades referenced this in commit d855cc511d on May 8, 2022

scratch space: use single allocation #600