git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 10/20] pack-bitmap.c: ensure that eindex lookups don't overflow

From
Taylor Blau <me@ttaylorr.com>
Date
Jul 12, 2023, 23:37 UTC
Message-ID
<822cb19da4e7dac5b1d4d4c7e115d7e4bcb7c976.1689205042.git.me@ttaylorr.com>
In-Reply-To
<cover.1689205042.git.me@ttaylorr.com>

When a bitmap is used to answer some reachability query, it creates a pseudo-bitmap called the "extended index" on top of any existing bitmaps to store objects that are relevant to the query, but not mentioned in the bitmap.

When looking up the ith object in the extended index in a bitmap, it is common to write something like:

    bitmap_get(result, i + bitmap_num_objects(bitmap_git))

, indicating that we want the ith object following all other objects mentioned in the bitmap_git.

Since the type of `i` and the return type of `bitmap_num_objects()` are both `uint32_t`s, But if there are either a large number of objects in the bitmap, or a large number of objects in the extended index (or both), this addition can overflow when the sum is greater than 2^32-1.

Having that large of a bitmap position is entirely acceptable, but we need to ensure that the computed bitmap position for that object is performed using 64-bits and doesn't overflow.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 7367f62bb6..7ddb465c20 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -1294,7 +1294,7 @@ static void show_extended_objects(struct bitmap_index *bitmap_git,
 	for (i = 0; i < eindex->count; ++i) {
 		struct object *obj;
 
-		if (!bitmap_get(objects, bitmap_num_objects(bitmap_git) + i))
+		if (!bitmap_get(objects, st_add(bitmap_num_objects(bitmap_git), i)))
 			continue;
 
 		obj = eindex->objects[i];
@@ -1473,7 +1473,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
 	 * them individually.
 	 */
 	for (i = 0; i < eindex->count; i++) {
-		uint32_t pos = i + bitmap_num_objects(bitmap_git);
+		size_t pos = st_add(i, bitmap_num_objects(bitmap_git));
 		if (eindex->objects[i]->type == type &&
 		    bitmap_get(to_filter, pos) &&
 		    !bitmap_get(tips, pos))
@@ -1564,7 +1564,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
 	}
 
 	for (i = 0; i < eindex->count; i++) {
-		uint32_t pos = i + bitmap_num_objects(bitmap_git);
+		size_t pos = st_add(i, bitmap_num_objects(bitmap_git));
 		if (eindex->objects[i]->type == OBJ_BLOB &&
 		    bitmap_get(to_filter, pos) &&
 		    !bitmap_get(tips, pos) &&
@@ -2038,7 +2038,8 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git,
 
 	for (i = 0; i < eindex->count; ++i) {
 		if (eindex->objects[i]->type == type &&
-			bitmap_get(objects, bitmap_num_objects(bitmap_git) + i))
+		    bitmap_get(objects,
+			       st_add(bitmap_num_objects(bitmap_git), i)))
 			count++;
 	}
 
@@ -2452,7 +2453,8 @@ static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git)
 	for (i = 0; i < eindex->count; i++) {
 		struct object *obj = eindex->objects[i];
 
-		if (!bitmap_get(result, bitmap_num_objects(bitmap_git) + i))
+		if (!bitmap_get(result,
+				st_add(bitmap_num_objects(bitmap_git), i)))
 			continue;
 
 		if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)

-- 
2.41.0.347.g7b976b8871f
Previous: Taylor BlauNext: Taylor Blau
Message 17 of 28 in “guard object lookups against 32-bit overflow”
  1. 00/20 guard object lookups against 32-bit overflowTaylor Blau, Jul 12, 2023
  2. 01/20 packfile.c: prevent overflow in `nth_packed_object_id()`Taylor Blau, Jul 12, 2023
  3. 02/20 packfile.c: prevent overflow in `load_idx()`Taylor Blau, Jul 12, 2023
  4. Phillip WoodJul 13, 2023
  5. Taylor BlauJul 13, 2023
  6. Taylor BlauJul 14, 2023
  7. Phillip WoodJul 14, 2023
  8. Junio C HamanoJul 14, 2023
  9. Phillip WoodJul 14, 2023
  10. Junio C HamanoJul 13, 2023
  11. 03/20 packfile.c: use checked arithmetic in `nth_packed_object_offset()`Taylor Blau, Jul 12, 2023
  12. 04/20 midx.c: use `size_t`'s for fanout nr and allocTaylor Blau, Jul 12, 2023
  13. 05/20 midx.c: prevent overflow in `nth_midxed_object_oid()`Taylor Blau, Jul 12, 2023
  14. 06/20 midx.c: prevent overflow in `nth_midxed_offset()`Taylor Blau, Jul 12, 2023
  15. 08/20 midx.c: prevent overflow in `write_midx_internal()`Taylor Blau, Jul 12, 2023
  16. 09/20 midx.c: prevent overflow in `fill_included_packs_batch()`Taylor Blau, Jul 12, 2023
  17. 10/20 pack-bitmap.c: ensure that eindex lookups don't overflowTaylor Blau, Jul 12, 2023
  18. 11/20 commit-graph.c: prevent overflow in `write_commit_graph_file()`Taylor Blau, Jul 12, 2023
  19. 12/20 commit-graph.c: prevent overflow in add_graph_to_chain()Taylor Blau, Jul 12, 2023
  20. 13/20 commit-graph.c: prevent overflow in `load_oid_from_graph()`Taylor Blau, Jul 12, 2023
  21. 14/20 commit-graph.c: prevent overflow in `fill_commit_graph_info()`Taylor Blau, Jul 12, 2023
  22. 15/20 commit-graph.c: prevent overflow in `fill_commit_in_graph()`Taylor Blau, Jul 12, 2023
  23. 16/20 commit-graph.c: prevent overflow in `load_tree_for_commit()`Taylor Blau, Jul 12, 2023
  24. 17/20 commit-graph.c: prevent overflow in `split_graph_merge_strategy()`Taylor Blau, Jul 12, 2023
  25. 18/20 commit-graph.c: prevent overflow in `merge_commit_graph()`Taylor Blau, Jul 12, 2023
  26. 19/20 commit-graph.c: prevent overflow in `write_commit_graph()`Taylor Blau, Jul 12, 2023
  27. 20/20 commit-graph.c: prevent overflow in `verify_commit_graph()`Taylor Blau, Jul 12, 2023
  28. 07/20 midx.c: store `nr`, `alloc` variables as `size_t`'sTaylor Blau, Jul 12, 2023

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.