Documentation/technical/bitmap-format.txt: add missing position table
PATCH v2 1/2 Documentation/technical/bitmap-format.txt: add missing position table
While investigating a benign Coverity warning on the new pseudo-merge implementation, I was struggling to understand the (paraphrased) below:
ofs = index_end - 24 - (index->pseudo_merges.nr * sizeof(uint64_t));
for (i = 0; i < index->pseudo_merges.nr; i++) {
index->pseudo_merges.v[i].at = get_be64(ofs);
ofs += sizeof(uint64_t);
}, in pack-bitmap.c::load_bitmap_header(). Looking at the documentation, the diagram describing the on-disk format (prior to this patch) suggested that the optional extended lookup table immediately preceded the trailing metadata portion.
If that were the case, that would make the above code from load_bitmap_header() incorrect, as we'd be blindly reading into the extended offset table.
But later on in the documentation there is a description of the pseudo-merge position table as immediately preceding the trailing metadata portion of the extension. And indeed, we do write the position table in pack-bitmap-write.c:
/* write positions for all pseudo merges */
for (i = 0; i < writer->pseudo_merges_nr; i++)
hashwrite_be64(f, pseudo_merge_ofs[i]);
hashwrite_be32(f, writer->pseudo_merges_nr);
hashwrite_be32(f, kh_size(writer->pseudo_merge_commits));
hashwrite_be64(f, table_start - start);
hashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t));So this is purely a case of the diagram being out of sync with the textual description and actual implementation of the format specification.
Add the missing component back to the format diagram to avoid further confusion in this area.
--- Documentation/technical/bitmap-format.txt | 9 +++++++++ 1 file changed, 9 insertions(+)
Documentation/technical/bitmap-format.txt +9 -0
@@ -312,6 +312,15 @@ the end of a `.bitmap` file. The format is as follows: | | +-------------------------------------------+ | | +| Pseudo-merge position table | +| +----+----------+----------+----------+ | +| | N | Offset 1 | .... | Offset N | | +| +----+----------+----------+----------+ | +| | | 8 bytes | .... | 8 bytes | | +| +----+----------+----------+----------+ | +| | ++-------------------------------------------+ +| | | Pseudo-merge Metadata | | +-----------------------------------+ | | | # pseudo-merges (4 bytes) | |
base-commit: 0b7500dc66ffcb6b1ccc3332715936a59c6b5ce4
Signature · 1 line
2.45.0.32.ga71ec05e5dc.dirty
PATCH v2 2/2 pack-bitmap.c: ensure pseudo-merge offset reads are bounded
After reading the pseudo-merge extension's metadata table, we allocate an array to store information about each pseudo-merge, including its byte offset within the .bitmap file itself.
This is done like so:
pseudo_merge_ofs = index_end - 24 -
(index->pseudo_merges.nr * sizeof(uint64_t));
for (i = 0; i < index->pseudo_merges.nr; i++) {
index->pseudo_merges.v[i].at = get_be64(pseudo_merge_ofs);
pseudo_merge_ofs += sizeof(uint64_t);
}But if the pseudo-merge table is corrupt, we'll keep calling get_be64() past the end of the pseudo-merge extension, potentially reading off the end of the mmap'd region.
Prevent this by ensuring that we have at least table_size - 24 many bytes available to read (subtracting 24 as the length of the metadata component).
This is sufficient to prevent us from reading off the end of the pseudo-merge extension, and ensures that all of the get_be64() calls below are in bounds.
--- pack-bitmap.c | 3 +++ 1 file changed, 3 insertions(+)
pack-bitmap.c +3 -0
@@ -238,6 +238,9 @@ static int load_bitmap_header(struct bitmap_index *index) index->pseudo_merges.commits_nr =get_be32 (index_end -20 ); index->pseudo_merges.nr =get_be32 (index_end -24 ); +if (st_mult (index->pseudo_merges.nr,sizeof (uint64_t )) > table_size -24 ) +return error (_ ("corrupted bitmap index file, pseudo-merge table too short" )); +CALLOC_ARRAY (index->pseudo_merges.v, index->pseudo_merges.nr);
Signature · 1 line
2.45.0.32.ga71ec05e5dc.dirty
Re: [PATCH 2/2] pack-bitmap.c: ensure pseudo-merge offset reads are bounded
Quoted 17 lines · Taylor Blau
After reading the pseudo-merge extension's metadata table, we allocate an array to store information about each pseudo-merge, including its byte offset within the .bitmap file itself.
This is done like so:
pseudo_merge_ofs = index_end - 24 - (index->pseudo_merges.nr * sizeof(uint64_t)); for (i = 0; i < index->pseudo_merges.nr; i++) { index->pseudo_merges.v[i].at = get_be64(pseudo_merge_ofs); pseudo_merge_ofs += sizeof(uint64_t); }But if the pseudo-merge table is corrupt, we'll keep calling
get_be64()past the end of the pseudo-merge extension, potentially reading off the end of the mmap'd region.
Quoted 7 lines
Prevent this by ensuring that we have at least
table_size - 24many bytes available to read (subtracting 24 as the length of the metadata component).This is sufficient to prevent us from reading off the end of the pseudo-merge extension, and ensures that all of the
get_be64()calls below are in bounds.
Can table_size at this point be smaller than 24, which will allow (table_size - 24) to be a huge number that st_mult() will comfortably fit?
Quoted 19 lines
Helped-by Jeff King <[email protected]>Signed-off-by Taylor Blau <[email protected]>--- pack-bitmap.c | 3 +++ 1 file changed, 3 insertions(+)pack-bitmap.c +3
-0@@ -238,6 +238,9 @@ static int load_bitmap_header(struct bitmap_index *index) index->pseudo_merges.commits_nr =get_be32 (index_end -20 ); index->pseudo_merges.nr =get_be32 (index_end -24 ); +if (st_mult (index->pseudo_merges.nr,sizeof (uint64_t )) > table_size -24 ) +return error (_ ("corrupted bitmap index file, pseudo-merge table too short" )); +CALLOC_ARRAY (index->pseudo_merges.v, index->pseudo_merges.nr);
Re: [PATCH 2/2] pack-bitmap.c: ensure pseudo-merge offset reads are bounded
Quoted 3 lines · Junio C Hamano
Can
table_sizeat this point be smaller than 24, which will allow (table_size- 24) to be a huge number thatst_mult()will comfortably fit?
It could be smaller than 24, but I think we're at the point of diminishing returns here. The table_size field is read from the .bitmap file itself, and we do some light bounds checking here:
table_size = get_be64(index_end - 8);
if (table_size > index_end - index->map - header_size)
return error(_(...));We could add another check to ensure that table_size is at least 24, but I'm less concerned here for a couple of reasons:
- Since we're reading off of the index_end, we know that all of our reads are within the .bitmap itself, so we're not reading outside of the memory-mapped region.
- Checking that index->pseudo_merges.nr is a reasonable size also bounds reads, but more importantly IMHO prevents a large heap allocation via the CALLOC_ARRAY() below.
So I think we could check the table_size value, but I'm not sure we'd gain very much by doing so.
Thanks,
Taylor
Re: [PATCH 2/2] pack-bitmap.c: ensure pseudo-merge offset reads are bounded
Quoted 7 lines · Taylor Blau
Quoted 3 lines · Junio C Hamano
Can
table_sizeat this point be smaller than 24, which will allow (table_size- 24) to be a huge number thatst_mult()will comfortably fit?It could be smaller than 24, but I think we're at the point of diminishing returns here.
I only meant to say that we could easily rewrite
if (st_mult() > table_size - 24)
condition to
if (st_add(st_mult(), 24) > table_size)
and we do not have to think if we have already checked table_size before we reach this point of the control flow.
Re: [PATCH 2/2] pack-bitmap.c: ensure pseudo-merge offset reads are bounded
Quoted 12 lines · Junio C Hamano
Quoted 7 lines · Taylor Blau
Quoted 3 lines · Junio C Hamano
Can
table_sizeat this point be smaller than 24, which will allow (table_size- 24) to be a huge number thatst_mult()will comfortably fit?It could be smaller than 24, but I think we're at the point of diminishing returns here.
I only meant to say that we could easily rewrite
Quoted 8 lines
if (st_mult() > table_size - 24)condition to
if (st_add(st_mult(), 24) > table_size)and we do not have to think if we have already checked
table_sizebefore we reach this point of the control flow.
Ah. Thanks for the clarification. Yes, I think you could do so; I'm happy to send another version if you like.
Thanks,
Taylor
Re: [PATCH 2/2] pack-bitmap.c: ensure pseudo-merge offset reads are bounded
Quoted 17 lines · Taylor Blau
Quoted 16 lines · Junio C Hamano
Quoted 7 lines · Taylor Blau
Quoted 3 lines · Junio C Hamano
Can
table_sizeat this point be smaller than 24, which will allow (table_size- 24) to be a huge number thatst_mult()will comfortably fit?It could be smaller than 24, but I think we're at the point of diminishing returns here.
I only meant to say that we could easily rewrite
if (st_mult() > table_size - 24)condition to
Quoted 7 lines
Quoted 4 lines
if (st_add(st_mult(), 24) > table_size)and we do not have to think if we have already checked
table_sizebefore we reach this point of the control flow.Ah. Thanks for the clarification. Yes, I think you could do so; I'm happy to send another version if you like.
Let's get this thing unstuck; the other larger topic that this topic builds upon is stuck for too long.
v2 cover pseudo-merge: various small fixes
In reply to Taylor BlauHere is a small reroll of a couple of patches I wrote to fix various small issues with the tb/pseudo-merge-reachability-bitmaps topic.
The only change since last time is replacing:
if (st_mult(index->pseudo_merges.nr, sizeof(uint64_t)) > table_size - 24)
with:
if (st_add(st_mult(index->pseudo_merges.nr, sizeof(uint64_t)), 24) > table_size)
based on helpful review from Junio. For convenience, a range-diff is below. Thanks in advance for any final review on this topic :-).
Taylor Blau (2):
Documentation/technical/bitmap-format.txt: add missing position table pack-bitmap.c: ensure pseudo-merge offset reads are bounded
Documentation/technical/bitmap-format.txt | 9 +++++++++ pack-bitmap.c | 5 +++++ 2 files changed, 14 insertions(+)
Range-diff against v1:
-: ---------- > 1: a71ec05e5d Documentation/technical/bitmap-format.txt: add missing position table 1: 0a16399d14 ! 2: 8abd564e7c pack-bitmap.c: ensure pseudo-merge offset reads are bounded
@@ Commit message
end of the mmap'd region.
Prevent this by ensuring that we have at least table_size - 24 many
- bytes available to read (subtracting 24 as the length of the metadata
- component).
+ bytes available to read (adding 24 to the left-hand side of our
+ inequality to account for the length of the metadata component).
This is sufficient to prevent us from reading off the end of the pseudo-merge extension, and ensures that all of the get_be64() calls
@@ pack-bitmap.c: static int load_bitmap_header(struct bitmap_index *index)
index->pseudo_merges.commits_nr = get_be32(index_end - 20); index->pseudo_merges.nr = get_be32(index_end - 24);
-+ if (st_mult(index->pseudo_merges.nr, sizeof(uint64_t)) > table_size - 24)
++ if (st_add(st_mult(index->pseudo_merges.nr,
++ sizeof(uint64_t)),
++ 24) > table_size)
+ return error(_("corrupted bitmap index file, pseudo-merge table too short"));
+
CALLOC_ARRAY(index->pseudo_merges.v,
base-commit: 0b7500dc66ffcb6b1ccc3332715936a59c6b5ce4 --
2.45.0.33.g0a16399d14.dirty
PATCH v2 1/2 Documentation/technical/bitmap-format.txt: add missing position table
While investigating a benign Coverity warning on the new pseudo-merge implementation, I was struggling to understand the (paraphrased) below:
ofs = index_end - 24 - (index->pseudo_merges.nr * sizeof(uint64_t));
for (i = 0; i < index->pseudo_merges.nr; i++) {
index->pseudo_merges.v[i].at = get_be64(ofs);
ofs += sizeof(uint64_t);
}, in pack-bitmap.c::load_bitmap_header(). Looking at the documentation, the diagram describing the on-disk format (prior to this patch) suggested that the optional extended lookup table immediately preceded the trailing metadata portion.
If that were the case, that would make the above code from load_bitmap_header() incorrect, as we'd be blindly reading into the extended offset table.
But later on in the documentation there is a description of the pseudo-merge position table as immediately preceding the trailing metadata portion of the extension. And indeed, we do write the position table in pack-bitmap-write.c:
/* write positions for all pseudo merges */
for (i = 0; i < writer->pseudo_merges_nr; i++)
hashwrite_be64(f, pseudo_merge_ofs[i]);
hashwrite_be32(f, writer->pseudo_merges_nr);
hashwrite_be32(f, kh_size(writer->pseudo_merge_commits));
hashwrite_be64(f, table_start - start);
hashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t));So this is purely a case of the diagram being out of sync with the textual description and actual implementation of the format specification.
Add the missing component back to the format diagram to avoid further confusion in this area.
--- Documentation/technical/bitmap-format.txt | 9 +++++++++ 1 file changed, 9 insertions(+)
Documentation/technical/bitmap-format.txt +9 -0
@@ -312,6 +312,15 @@ the end of a `.bitmap` file. The format is as follows: | | +-------------------------------------------+ | | +| Pseudo-merge position table | +| +----+----------+----------+----------+ | +| | N | Offset 1 | .... | Offset N | | +| +----+----------+----------+----------+ | +| | | 8 bytes | .... | 8 bytes | | +| +----+----------+----------+----------+ | +| | ++-------------------------------------------+ +| | | Pseudo-merge Metadata | | +-----------------------------------+ | | | # pseudo-merges (4 bytes) | |
Signature · 1 line
2.45.0.33.g0a16399d14.dirty
PATCH v2 2/2 pack-bitmap.c: ensure pseudo-merge offset reads are bounded
In reply to Taylor BlauAfter reading the pseudo-merge extension's metadata table, we allocate an array to store information about each pseudo-merge, including its byte offset within the .bitmap file itself.
This is done like so:
pseudo_merge_ofs = index_end - 24 -
(index->pseudo_merges.nr * sizeof(uint64_t));
for (i = 0; i < index->pseudo_merges.nr; i++) {
index->pseudo_merges.v[i].at = get_be64(pseudo_merge_ofs);
pseudo_merge_ofs += sizeof(uint64_t);
}But if the pseudo-merge table is corrupt, we'll keep calling get_be64() past the end of the pseudo-merge extension, potentially reading off the end of the mmap'd region.
Prevent this by ensuring that we have at least table_size - 24 many bytes available to read (adding 24 to the left-hand side of our inequality to account for the length of the metadata component).
This is sufficient to prevent us from reading off the end of the pseudo-merge extension, and ensures that all of the get_be64() calls below are in bounds.
--- pack-bitmap.c | 5 +++++ 1 file changed, 5 insertions(+)
pack-bitmap.c +5 -0
@@ -238,6 +238,11 @@ static int load_bitmap_header(struct bitmap_index *index) index->pseudo_merges.commits_nr =get_be32 (index_end -20 ); index->pseudo_merges.nr =get_be32 (index_end -24 ); +if (st_add (st_mult (index->pseudo_merges.nr, +sizeof (uint64_t )), +24 ) > table_size) +return error (_ ("corrupted bitmap index file, pseudo-merge table too short" )); +CALLOC_ARRAY (index->pseudo_merges.v, index->pseudo_merges.nr);
Signature · 1 line
2.45.0.33.g0a16399d14.dirty
Re: [PATCH v2 0/2] pseudo-merge: various small fixes
In reply to Taylor BlauQuoted 49 lines · Taylor Blau
Here is a small reroll of a couple of patches I wrote to fix various small issues with the tb/pseudo-merge-reachability-bitmaps topic.
The only change since last time is replacing:
if (st_mult(index->pseudo_merges.nr, sizeof(uint64_t)) > table_size - 24)with:
if (st_add(st_mult(index->pseudo_merges.nr, sizeof(uint64_t)), 24) > table_size)based on helpful review from Junio. For convenience, a range-diff is below. Thanks in advance for any final review on this topic :-).
Taylor Blau (2):
Documentation/technical/bitmap-format.txt: add missing position tablepack-bitmap.c: ensure pseudo-merge offset reads are boundedDocumentation/technical/bitmap-format.txt | 9 +++++++++ pack-bitmap.c | 5 +++++ 2 files changed, 14 insertions(+)Range-diff against v1:
-: ---------- > 1: a71ec05e5d Documentation/technical/bitmap-format.txt: add missing position table 1: 0a16399d14 ! 2: 8abd564e7c pack-bitmap.c: ensure pseudo-merge offset reads are bounded@@ Commit message
end of the mmap'd region.Prevent this by ensuring that we have at least
table_size - 24many
- bytes available to read (subtracting 24 as the length of the metadata
- component).
+ bytes available to read (adding 24 to the left-hand side of our
+ inequality to account for the length of the metadata component).This is sufficient to prevent us from reading off the end of the pseudo-merge extension, and ensures that all of the
get_be64()calls
@@pack-bitmap.c: static intload_bitmap_header(struct bitmap_index *index)
index->pseudo_merges.commits_nr=get_be32(index_end - 20);index->pseudo_merges.nr=get_be32(index_end - 24);-+ if (
st_mult(index->pseudo_merges.nr, sizeof(uint64_t))>table_size- 24)
++ if (st_add(st_mult(index->pseudo_merges.nr,
++sizeof(uint64_t)),
++ 24) >table_size)
+ returnerror(_("corrupted bitmap index file, pseudo-merge table too short"));
+
CALLOC_ARRAY(index->pseudo_merges.v,
Quoted 3 lines
base-commit:
0b7500dc66ffcb6b1ccc3332715936a59c6b5ce4--
2.45.0.33.g0a16399d14.dirty
Series looks good to me.
Re: [PATCH v2 0/2] pseudo-merge: various small fixes
Quoted 7 lines · Elijah Newren
Quoted 4 lines · Taylor Blau
Here is a small reroll of a couple of patches I wrote to fix various small issues with the tb/pseudo-merge-reachability-bitmaps topic.
...
Series looks good to me.
Thanks, it looked good to me, too. Let's roll it into the base topic that has been waiting in 'next'.