8000 Implemented self-validating global-checksums (gcksums) · littlefs-project/littlefs@1c5adf7 · GitHub
[go: up one dir, main page]
Skip to content
/ littlefs Public

Commit 1c5adf7

Browse files
gekygeky
committed
Implemented self-validating global-checksums (gcksums)
This was quite a puzzle. The problem: How do we detect corrupt mdirs? Seems like a simple question, but we can't just rely on mdir cksums. Our mdirs are independently updateable logs, and logs have this annoying tendency to "rollback" to previously valid states when corrupted. Rollback issues aren't littlefs-specific, but what _is_ littlefs- specific is that when one mdir rolls back, it can disagree with other mdirs, resulting in wildly incorrect filesystem state. To solve this, or at least protect against disagreeable mdirs, we need to somehow include the state of all other mdirs in each mdir commit. --- The first thought: Why not use gstate? We already have a system for storing distributed state. If we add the xor of all of our mdir cksums, we can rebuild it during mount and verify that nothing changed: .--------. .--------. .--------. .--------. .| mdir 0 | .| mdir 1 | .| mdir 2 | .| mdir 3 | || | || | || | || | || gdelta | || gdelta | || gdelta | || gdelta | |'-----|--' |'-----|--' |'-----|--' |'-----|--' '------|-' '------|-' '------|-' '------|-' '--.------' '--.------' '--.------' '--.------' cksum | cksum | cksum | cksum | | | v | v | v | '---------> xor -------> xor -------> xor -------> gcksum | v v v =? '---------> xor -------> xor -------> xor ---> gcksum Unfortunately it's not that easy. Consider what this looks like mathematically (g is our gcksum, c_i is an mdir cksum, d_i is a gcksumdelta, and +/-/sum is xor): g = sum(c_i) = sum(d_i) If we solve for a new gcksumdelta, d_i: d_i = g' - g d_i = g + c_i - g d_i = c_i The gcksum cancels itself out! We're left with an equation that depends only on the current mdir, which doesn't help us at all. Next thought: What if we permute the gcksum with a function t before distributing it over our gcksumdeltas? .--------. .--------. .--------. .--------. .| mdir 0 | .| mdir 1 | .| mdir 2 | .| mdir 3 | || | || | || | || | || gdelta | || gdelta | || gdelta | || gdelta | |'-----|--' |'-----|--' |'-----|--' |'-----|--' '------|-' '------|-' '------|-' '------|-' '--.------' '--.------' '--.------' '--.------' cksum | cksum | cksum | cksum | | | v | v | v | '---------> xor -------> xor -------> xor -------> gcksum | | | | .--t--' | | | | '-> t(gcksum) | v v v =? '---------> xor -------> xor -------> xor ---> t(gcksum) In math terms: t(g) = t(sum(c_i)) = sum(d_i) In order for this to work, t needs to be non-linear. If t is linear, the same thing happens: d_i = t(g') - t(g) d_i = t(g + c_i) - t(g) d_i = t(g) + t(c_i) - t(g) d_i = t(c_i) This was quite funny/frustrating (funnistrating?) during development, because it means a lot of seemingly obvious functions don't work! - t(g) = g - Doesn't work - t(g) = crc32c(g) - Doesn't work because crc32cs are linear - t(g) = g^2 in GF(2^n) - g^2 is linear in GF(2^n)!? Fortunately, powers coprime with 2 finally give us a non-linear function in GF(2^n), so t(g) = g^3 works: d_i = g'^3 - g^3 d_i = (g + c_i)^3 - g^3 d_i = (g^2 + gc_i + gc_i + c_i^2)(g + c_i) - g^3 d_i = (g^2 + c_i^2)(g + c_i) - g^3 d_i = g^3 + gc_i^2 + g^2c_i + c_i^3 - g^3 d_i = gc_i^2 + g^2c_i + c_i^3 --- Bleh, now we need to implement finite-field operations? Well, not entirely! Note that our algorithm never uses division. This means we don't need a full finite-field (+, -, *, /), but can get away with a finite-ring (+, -, *). And conveniently for us, our crc32c polynomial defines a ring epimorphic to a 31-bit finite-field. All we need to do is define crc32c multiplication as polynomial multiplication mod our crc32c polynomial: crc32cmul(a, b) = pmod(pmul(a, b), P) And since crc32c is more-or-less just pmod(x, P), this lets us take advantage of any crc32c hardware/tables that may be available. --- Bunch of notes: - Our 2^n-bit crc-ring maps to a 2^n-1-bit finite-field because our crc polynomial is defined as P(x) = Q(x)(x + 1), where Q(x) is a 2^n-1-bit irreducible polynomial. This is a common crc construction as it provides optimal odd-bit/2-bit error detection, so it shouldn't be too difficult to adapt to other crc sizes. - t(g) = g^3 is not the only function that works, but it turns out to be a pretty good one: - 3 and 2^(2^n-1)-1 are coprime, which means our function t(g) = g^3 provides a one-to-one mapping in the underlying fields of all crc rings of size 2^(2^n). We know 3 and 2^(2^n-1)-1 are coprime because 2^(2^n-1)-1 = 2^(2^n)-1 (a Fermat number) - 2^(2^n-1) (a power-of-2), and 3 divides Fermat numbers >=3 (A023394) and is not 2. - Our delta, when viewed as a polynomial in g: d(g) = gc^2 + g^2c + c^3, has degree 2, which implies there are at most 2 solutions or 1-bit of information loss in the underlying field. This is optimal since the original definition already had 2 solutions before we even chose a function: d(g) = t(g + c) - t(g) d(g) = t(g + c) - t((g + c) - c) d(g) = t((g + c) + c) - t(g + c) d(g) = d(g + c) Though note the mapping of our crc-ring to the underlying field already represents 1-bit of information loss. - If you're using a cryptographic hash or other non-crc, you should probably just use an equal sized finite-field. Though note changing from a 2^n-1-bit field to a 2^n-bit field does change the math a bit, with t(g) = g^7 being a better non-linear function: - 7 is the smallest odd-number coprime with 2^n-1, a Fermat number, which makes t(g) = g^7 a one-to-one mapping. 3 humorously divides all 2^n-1 Fermat numbers. - Expanding delta with t(g) = g^7 gives us a 6 degree polynomial, which implies at most 6 solutions or ~3-bits of information loss. This isn't actually the best you can do, some exhaustive searching over small fields (<=2^16) suggests t(g) = g^(2^(n-1)-1) _might_ be optimal, but that's a heck of a lot more multiplications. - Because our crc32cs preserve parity/are epimorphic to parity bits, addition (xor) and multiplication (crc32cmul) also preserve parity, which can be used to show our entire gcksum system preserves parity. This is quite neat, and means we are guaranteed to detect any odd number of bit-errors across the entire filesystem. - Another idea was to use two different addition operations: xor and overflowing addition (or mod a prime). This probably would have worked, but lacks the rigor of the above solution. - You might think an RS-like construction would help here, where g = sum(c_ia^i), but this suffers from the same problem: d_i = g' - g d_i = g + c_ia^i - g d_i = c_ia^i Nothing here depends on anything outside of the current mdir. - Another question is should we be using an RS-like construction anyways to include location information in our gcksum? Maybe in another system, but I don't think it's necessary in littlefs. While our mdir are independently updateable, they aren't _entirely_ independent. The location of each mdir is stored in either the mtree or a parent mdir, so it always gets mixed into the gcksum somewhere. The only exception being the mrootanchor which is always at the fixed blocks 0x{0,1}. - This does _not_ catch "global-rollback" issues, where the most recent commit in the entire filesystem is corrupted, revealing an older, but still valid, filesystem state. But as far as I am aware this is just a fundamental limitation of powerloss-resilient filesystems, short of doing destructive operations. At the very least, exposing the gcksum would allow the user to store it externally and prevent this issue. --- Implementation details: - Our gcksumdelta depends on the rbyd's cksum, so there's a catch-22 if we include it in the rbyd itself. We can avoid this by including it in the commit tags (actually the separate canonical cksum makes this easier than it would have been earlier), but this does mean LFSR_TAG_GCKSUMDELTA is not an LFSR_TAG_GDELTA subtype. Unfortunate but not a dealbreaker. - Reading/writing the gcksumdelta gets a bit annoying with it not being in the rbyd. For now I've extended the low-level lfsr_rbyd_fetch_/ lfsr_rbyd_appendcksum_ to accept an optional gcksumdelta pointer, which is a bit awkward, but I don't know of a better solution. - Unlike the grm, _every_ mdir commit involves the gcksum, which means we either need to propagate the gcksumdelta up the mroot chain correctly, or somehow keep track of partially flushed gcksumdeltas. To make this work I modified the low-level lfsr_mdir_commit__ functions to accept start_rid=-2 to indicate when gcksumdeltas should be flushed. It's a bit of a hack, but I think it might make sense to extend this to all gdeltas eventually. The gcksum cost both code and RAM, but I think it's well worth it for removing an entire category of filesystem corruption: code stack ctx before: 37796 2608 620 after: 38428 (+1.7%) 2640 (+1.2%) 644 (+3.9%)
1 parent 0eee570 commit 1c5adf7

File tree

11 files changed

+684
-168
lines changed

11 files changed

+684
-168
lines changed

‎lfs.c

Lines changed: 235 additions & 44 deletions
Large diffs are not rendered by default.

‎lfs.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -611,6 +611,7 @@ typedef struct {
611611
typedef struct lfsr_mdir {
612612
lfsr_smid_t mid;
613613
lfsr_rbyd_t rbyd;
614+
uint32_t gcksumdelta;
614615
} lfsr_mdir_t;
615616

616617
typedef struct lfsr_omdir {
@@ -874,6 +875,10 @@ typedef struct lfs {
874875
uint8_t *buffer;
875876
} lookahead;
876877

878+
uint32_t gcksum;
879+
uint32_t gcksum_p;
880+
uint32_t gcksum_d;
881+
877882
lfsr_grm_t grm;
878883
uint8_t grm_p[LFSR_GRM_DSIZE];
879884
uint8_t grm_d[LFSR_GRM_DSIZE];

‎lfs_util.c

Lines changed: 118 additions & 74 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,86 @@ ssize_t lfs_fromleb128(uint32_t *word, const void *buffer, size_t size) {
7676
// return crc;
7777
//}
7878

79+
80+
// crc32c tables (see lfs_crc32c for more info)
81+
#if !defined(LFS_FASTER_CRC32C)
82+
static const uint32_t lfs_crc32c_table[16] = {
83+
0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1,
84+
0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d,
85+
0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9,
86+
0xc38d26c4, 0xd3d3e1ab, 0xe330a81a, 0xf36e6f75,
87+
};
88+
89+
#else
90+
static const uint32_t lfs_crc32c_table[256] = {
91+
0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4,
92+
0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb,
93+
0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b,
94+
0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24,
95+
0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b,
96+
0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
97+
0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54,
98+
0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b,
99+
0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a,
100+
0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35,
101+
0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5,
102+
0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
103+
0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45,
104+
0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a,
105+
0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a,
106+
0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595,
107+
0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48,
108+
0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
109+
0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687,
110+
0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198,
111+
0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927,
112+
0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38,
113+
0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8,
114+
0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
115+
0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096,
116+
0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789,
117+
0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859,
118+
0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46,
119+
0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9,
120+
0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
121+
0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36,
122+
0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829,
123+
0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c,
124+
0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93,
125+
0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043,
126+
0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
127+
0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3,
128+
0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc,
129+
0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c,
130+
0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033,
131+
0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652,
132+
0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
133+
0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d,
134+
0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982,
135+
0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d,
136+
0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622,
137+
0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2,
138+
0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
139+
0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530,
140+
0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f,
141+
0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff,
142+
0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0,
143+
0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f,
144+
0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
145+
0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90,
146+
0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f,
147+
0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee,
148+
0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1,
149+
0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321,
150+
0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
151+
0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81,
152+
0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e,
153+
0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e,
154+
0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351,
155+
};
156+
#endif
157+
158+
79159
// Calculate crc32c incrementally
80160
uint32_t lfs_crc32c(uint32_t crc, const void *buffer, size_t size) {
81161
// init with 0xffffffff so prefixed zeros affect the crc
@@ -107,86 +187,12 @@ uint32_t lfs_crc32c(uint32_t crc, const void *buffer, size_t size) {
107187
}
108188

109189
#elif !defined(LFS_FASTER_CRC32C)
110-
static const uint32_t lfs_crc32c_table[16] = {
111-
0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1,
112-
0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d,
113-
0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9,
114-
0xc38d26c4, 0xd3d3e1ab, 0xe330a81a, 0xf36e6f75,
115-
};
116-
117190
for (size_t i = 0; i < size; i++) {
118191
crc = (crc >> 4) ^ lfs_crc32c_table[0xf & (crc ^ (data[i] >> 0))];
119192
crc = (crc >> 4) ^ lfs_crc32c_table[0xf & (crc ^ (data[i] >> 4))];
120193
}
121194

122195
#else
123-
static const uint32_t lfs_crc32c_table[256] = {
124-
0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4,
125-
0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb,
126-
0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b,
127-
0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24,
128-
0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b,
129-
0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
130-
0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54,
131-
0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b,
132-
0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a,
133-
0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35,
134-
0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5,
135-
0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
136-
0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45,
137-
0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a,
138-
0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a,
139-
0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595,
140-
0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48,
141-
0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
142-
0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687,
143-
0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198,
144-
0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927,
145-
0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38,
146-
0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8,
147-
0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
148-
0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096,
149-
0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789,
150-
0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859,
151-
0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46,
152-
0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9,
153-
0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
154-
0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36,
155-
0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829,
156-
0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c,
157-
0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93,
158-
0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043,
159-
0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
160-
0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3,
161-
0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc,
162-
0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c,
163-
0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033,
164-
0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652,
165-
0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
166-
0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d,
167-
0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982,
168-
0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d,
169-
0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622,
170-
0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2,
171-
0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
172-
0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530,
173-
0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f,
174-
0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff,
175-
0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0,
176-
0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f,
177-
0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
178-
0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90,
179-
0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f,
180-
0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee,
181-
0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1,
182-
0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321,
183-
0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
184-
0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81,
185-
0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e,
186-
0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e,
187-
0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351,
188-
};
189-
190196
for (size_t i = 0; i < size; i++) {
191197
crc = (crc >> 8) ^ lfs_crc32c_table[0xff & (crc ^ data[i])];
192198
}
@@ -197,4 +203,42 @@ uint32_t lfs_crc32c(uint32_t crc, const void *buffer, size_t size) {
197203
return crc;
198204
}
199205

206+
// Multiply two crc32cs in the crc32c ring
207+
uint32_t lfs_crc32c_mul(uint32_t a, uint32_t b) {
208+
// Multiplication in a crc32c ring involves polynomial
209+
// multiplication modulo the crc32c polynomial to keep things
210+
// finite:
211+
//
212+
// r = a * b mod P
213+
//
214+
// Note because our crc32c is not irreducible, this does not give
215+
// us a finite-field, i.e. division is undefined. Still,
216+
// multiplication has useful properties.
217+
218+
// This gets a bit funky because crc32cs are little-endian, but
219+
// fortunately pmul is symmetric. Unfortunately the result is
220+
// 31-bits large, so we need to shift by 1.
221+
uint64_t r = lfs_pmul(a, b) << 1;
222+
223+
// We can accelerate our module with crc32c tables if present, these
224+
// loops may look familiar.
225+
#if defined(LFS_SMALLER_CRC32C)
226+
for (int i = 0; i < 32; i++) {
227+
r = (r >> 1) ^ ((r & 1) ? 0x82f63b78 : 0);
228+
}
229+
230+
#elif !defined(LFS_FASTER_CRC32C)
231+
for (int i = 0; i < 8; i++) {
232+
r = (r >> 4) ^ lfs_crc32c_table[0xf & r];
233+
}
234+
235+
#else
236+
for (int i = 0; i < 4; i++) {
237+
r = (r >> 8) ^ lfs_crc32c_table[0xff & r];
238+
}
239+
#endif
240+
241+
return (uint32_t)r;
242+
}
243+
200244
#endif

‎lfs_util.h

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -281,6 +281,25 @@ static inline int lfs_scmp(uint32_t a, uint32_t b) {
281281
return (int)(unsigned)(a - b);
282282
}
283283

284+
// Perform polynomial/carry-less multiplication
285+
//
286+
// This is a multiply where all adds are replaced with xors. If we view
287+
// a and b as binary polynomials, xor is polynomial addition and pmul is
288+
// polynomial multiplication.
289+
static inline uint64_t lfs_pmul(uint32_t a, uint32_t b) {
290+
uint64_t r = 0;
291+
uint64_t a_ = a;
292+
while (b) {
293+
if (b & 1) {
294+
r ^= a_;
295+
}
296+
a_ <<= 1;
297+
b >>= 1;
298+
}
299+
return r;
300+
}
301+
302+
284303
// Convert between 32-bit little-endian and native order
285304
static inline uint32_t lfs_fromle32(uint32_t a) {
286305
#if !defined(LFS_NO_BUILTINS) && defined(LFS_LITTLE_ENDIAN)
@@ -603,6 +622,9 @@ static inline size_t lfs_strcspn(const char *a, const char *cs) {
603622
//
604623
uint32_t lfs_crc32c(uint32_t crc, const void *buffer, size_t size);
605624

625+
// Multiply two crc32cs in the crc32c ring
626+
uint32_t lfs_crc32c_mul(uint32_t a, uint32_t b);
627+
606628

607629
// Allocate memory, only used if buffers are not provided to littlefs
608630
// Note, memory must be 64-bit aligned

‎scripts/dbgbmap.py

Lines changed: 19 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -50,10 +50,11 @@
5050
TAG_R = 0x2000
5151
TAG_LE = 0x0000
5252
TAG_GT = 0x1000
53-
TAG_CKSUM = 0x3000 ## 0x3c0p v-11 cccc ---- ---p
53+
TAG_CKSUM = 0x3000 ## 0x300p v-11 ---- ---- ---p
5454
TAG_P = 0x0001
55-
TAG_NOTE = 0x3100 # 0x3100 v-11 ---1 ---- ----
56-
TAG_ECKSUM = 0x3200 # 0x3200 v-11 --1- ---- ----
55+
TAG_NOTE = 0x3100 ## 0x3100 v-11 ---1 ---- ----
56+
TAG_ECKSUM = 0x3200 ## 0x3200 v-11 --1- ---- ----
57+
TAG_GCKSUMDELTA = 0x3300 ## 0x3300 v-11 --11 ---- ----
5758

5859

5960
CHARS = 'mbd-'
@@ -594,7 +595,8 @@ def draw(self, row, *,
594595

595596
# our core rbyd type
596597
class Rbyd:
597-
def __init__(self, blocks, data, rev, eoff, trunk, weight, cksum):
598+
def __init__(self, blocks, data, rev, eoff, trunk, weight, cksum,
599+
gcksumdelta):
598600
if isinstance(blocks, int):
599601
blocks = (blocks,)
600602

@@ -605,6 +607,7 @@ def __init__(self, blocks, data, rev, eoff, trunk, weight, cksum):
605607
self.trunk = trunk
606608
self.weight = weight
607609
self.cksum = cksum
610+
self.gcksumdelta = gcksumdelta
608611

609612
@property
610613
def block(self):
@@ -680,6 +683,8 @@ def fetch(cls, f, block_size, block, trunk=None, cksum=None):
680683
weight = 0
681684
weight_ = 0
682685
weight__ = 0
686+
gcksumdelta = None
687+
gcksumdelta_ = None
683688
while j_ < len(data) and (not trunk or eoff <= trunk):
684689
# read next tag
685690
v, tag, w, size, d = fromtag(data[j_:])
@@ -695,6 +700,11 @@ def fetch(cls, f, block_size, block, trunk=None, cksum=None):
695700
if not tag & TAG_ALT:
696701
if (tag & 0xff00) != TAG_CKSUM:
697702
cksum___ = crc32c(data[j_:j_+size], cksum___)
703+
704+
# found a gcksumdelta?
705+
if (tag & 0xff00) == TAG_GCKSUMDELTA:
706+
gcksumdelta_ = (tag, w, j_-d, d, data[j_:j_+size])
707+
698708
# found a cksum?
699709
else:
700710
# check cksum
@@ -706,6 +716,8 @@ def fetch(cls, f, block_size, block, trunk=None, cksum=None):
706716
cksum_ = cksum__
707717
trunk_ = trunk__
708718
weight = weight_
719+
gcksumdelta = gcksumdelta_
720+
gcksumdelta_ = None
709721
# update perturb bit
710722
perturb = tag & TAG_P
711723
# revert to data cksum and perturb
@@ -737,6 +749,7 @@ def fetch(cls, f, block_size, block, trunk=None, cksum=None):
737749
0xfca42daf if perturb else 0)
738750
trunk_ = trunk__
739751
weight = weight_
752+
gcksumdelta = gcksumdelta_
740753
trunk___ = 0
741754

742755
# update canonical checksum, xoring out any perturb state
@@ -747,9 +760,9 @@ def fetch(cls, f, block_size, block, trunk=None, cksum=None):
747760

748761
# cksum mismatch?
749762
if cksum is not None and cksum_ != cksum:
750-
return cls(block, data, rev, 0, 0, 0, cksum_)
763+
return cls(block, data, rev, 0, 0, 0, cksum_, gcksumdelta)
751764

752-
return cls(block, data, rev, eoff, trunk_, weight, cksum_)
765+
return cls(block, data, rev, eoff, trunk_, weight, cksum_, gcksumdelta)
753766

754767
def lookup(self, rid, tag):
755768
if not self:

0 commit comments

Comments
 (0)
0