Fix ULID bugs when generating randomness for multiple requests coming in at the exact same timestamp #2
Conversation
…e same timestamp * Correct conditional in Nat80.add() to only give an overflow error when incrementing the h value by 1 causes it to overflow * Correct Nat80.toArray() to return the full concatenated array from lower and upper Nat80 thresholds, as Source.new() expects a full 16 elements. Note that this is triggered by #ok(Nat80.toArray(e)) in the monotomicRead() method
|
Great find! @di-wu Can you validate ane merge? |
There was a problem hiding this comment.
-
6vs10
Not sure how this got passed the tests I did back in the day.
80 = 10 * 8 != 6 * 8... -
I'll go over what should happen here...
Since the lower part number is the same bitlength as the given number to add. We know that if we add them together we get either, a number bigger than before, or smaller.
e.g. (nat8, max: 255)
var n = 124;
n +%= 121; // OK
// n == 255
n +%= 1; // Overflow
// n == 0
Which means if the new lower part is smaller than the original, we need to add 1 to the higher number.
Then in turn we can apply the same logic to the higher part of the uint80 number.
I used to following tests to check the PR:
$
$(vessel bin)/moc $(vessel sources) -r test/Nat80.test.mo
import Nat80 "../src/Nat80";
let MAX_NAT16 : Nat16 = 65_535;
let MAX_NAT64 : Nat64 = 18_446_744_073_709_551_615;
var n = Nat80.ZERO;
func add(x : Nat64) = switch (Nat80.add(n, x)) {
case (#ok(m)) n := m;
case (#err(_)) assert(false);
};
assert(Nat80.toArray(n) == [
0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00,
]);
assert(Nat80.isZero(n));
add(MAX_NAT64);
assert(Nat80.toArray(n) == [
0x00, 0x00, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
]);
add(1);
assert(Nat80.toArray(n) == [
0x00, 0x01, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00,
]);
add(MAX_NAT64);
assert(Nat80.toArray(n) == [
0x00, 0x01, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
]);
n := { low = MAX_NAT64; high = MAX_NAT16 };
assert(Nat80.toArray(n) == [
0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
]);
assert(not Nat80.isZero(n));
n := Nat80.addWrap(n, 1);
assert(Nat80.isZero(n));
n := { low = MAX_NAT64; high = MAX_NAT16 };
assert(Nat80.add(n, 1) == #err("overflow"));
public func add(n80 : Nat80, n : Nat64) : Result.Result<Nat80, Text> {
let m = addWrap(n80, n);
if (m.high < n80.high) return #err("overflow");
#ok(m);
};
public func addWrap(n80 : Nat80, n : Nat64) : Nat80 {
var l = n80.low +% n;
var h = n80.high;
if (l < n80.low) h +%= 1;
{ low = l; high = h; };
};
src/Nat80.mo
Outdated
| if (n80.low < l) h +%= 1; | ||
| if (n80.high < h) return #err("overflow"); | ||
| if (n80.high > h) return #err("overflow"); |
There was a problem hiding this comment.
It seems like both brackets need to be inverted.
if (l < n80.low) h +%= 1;
if (h < n80.high) return #err("overflow");
There was a problem hiding this comment.
Ah good point, I will test that out just to make sure and then push up a fix
|
@di-wu I've grouped them together by those with the exact same mtimestamp to show you what I mean Now that the lower part overflow is fixed, I'm seeing much more randomness in the random portion of the ULID Grouping by the timestamp once more I like the monotomic randomness introduced, but I'm wondering if this would lead to reaching the 2^80 conflict overflow sooner? Edit: Ah, I think I understand what is happening now. The I'm fine with this, but do we need the randomness on conflicts? What are some of the benefits/drawbacks? If you're set on keeping the |
|
The reason I used |
|
Ok, pushed up the fix for when the lower part of the ulid overflows. Ready for squash merge |
Tagging the maintainer @di-wu and ICDevs @skilesare for potential impacted library dependencies
Initial Issue
Making at least 2-3 requests that call the Source new() method at roughly the same time hit an overflow error. This was due to a bug in the following conditional statement.
Source of overflow error
Subsequent Issue
Upon fixing this bug, I encountered an uncaught index out of bounds error Where index out of bounds error was throwing
This was due to the fact that the
Array.append()method was removed in a subsequent commit and swapped for tabulate, and the size of the array (6) was less than the 10 elements necessary for the random portion of the ulid generation. Source of index out of bounds error.Fixes Made