{"thread":{"id":"62674","subject":"[PATCH] prio-queue: use size_t rather than int for size","startedAt":"2024-12-20T08:49:50Z","lastAt":"2024-12-27T14:34:42Z","messageCount":6,"participants":["Jeff King","Junio C Hamano","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"509365","messageId":"20241220084949.GA132704@coredump.intra.peff.net","threadId":"62674","inReplyTo":null,"subject":"[PATCH] prio-queue: use size_t rather than int for size","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-20T08:49:49Z","receivedAt":"2024-12-20T08:49:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The alloc and nr fields of a prio-queue tell us how much memory is\nallocated and used in the array. So the natural type for them is size_t,\nwhich prevents overflow on 64-bit systems where \"int\" is still 32 bits.\n\nThis is unlikely to happen in practice, as we typically use it for\nstoring commits, and having 2^31 of those is rather a lot. But it's good\nto keep our generic data structures as flexible as possible. And as we\nstart to enforce -Wsign-compare, it means that callers need to use\n\"int\", too, and the problem proliferates. Let's fix it at the source.\n\nThe changes here can be put into a few groups:\n\n  1. Changing the alloc/nr fields in the struct to size_t. This requires\n     swapping out int for size_t in negotiator/skipping.c, as well as\n     in prio_queue_get(), because those all iterate over the array.\n     Building with -Wsign-compare complains about these.\n\n  2. Other code that assigns or passes around indexes into the array\n     (e.g., the swap() and compare() functions) won't trigger\n     -Wsign-compare because we are simply truncating the values. These\n     are caught by -Wconversion, but I've adjusted them here to\n     future-proof us.\n\n  3. In prio_queue_reverse() we compute \"queue->nr - 1\" without checking\n     if anything is in the queue, which underflows now that nr is\n     unsigned. We can fix that by returning early when the queue is\n     empty (there is nothing to reverse).\n\n  4. The insertion_ctr variable is currently unsigned, but can likewise\n     grow (it is actually worse, because adding and removing an element\n     many times will keep increasing the counter, even though \"nr\" does\n     not). I've bumped that to size_t here, as well.\n\n     But -Wconversion notes that computing the \"cmp\" result by\n     subtracting the counters and assigning to \"int\" is a potential\n     problem. And that's true even before this patch, since we use an\n     unsigned counter (imagine comparing \"2^32-1\" and \"0\", which should\n     be a high positive value, but instead is \"-1\" as a signed int).\n\n     Since we only care about the sign (and not the magnitude) of the\n     result, we could fix this by swapping out the subtraction for a\n     ternary comparison. Probably the performance impact would be\n     negligible, since we just called into a custom compare function and\n     branched on its result anyway. But it's easy enough to do a\n     branchless version by subtracting the comparison results.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nNoticed this because the -Wsign-compare topic hit next, which raised a\nfew warnings with my local branches (but I think prio-queue is in the\nwrong here, hence this patch). It did turn out a little more involved\nthan I had expected, but I think the end result is more future-proof.\n\n negotiator/skipping.c |  5 ++---\n prio-queue.c          | 15 +++++++++------\n prio-queue.h          |  2 +-\n 3 files changed, 12 insertions(+), 10 deletions(-)\n\ndiff --git a/negotiator/skipping.c b/negotiator/skipping.c\nindex abedb70a48..616df6bf3a 100644\n--- a/negotiator/skipping.c\n+++ b/negotiator/skipping.c\n@@ -134,7 +134,6 @@ static int push_parent(struct data *data, struct entry *entry,\n \tstruct entry *parent_entry;\n \n \tif (to_push->object.flags & SEEN) {\n-\t\tint i;\n \t\tif (to_push->object.flags & POPPED)\n \t\t\t/*\n \t\t\t * The entry for this commit has already been popped,\n@@ -145,7 +144,7 @@ static int push_parent(struct data *data, struct entry *entry,\n \t\t/*\n \t\t * Find the existing entry and use it.\n \t\t */\n-\t\tfor (i = 0; i < data->rev_list.nr; i++) {\n+\t\tfor (size_t i = 0; i < data->rev_list.nr; i++) {\n \t\t\tparent_entry = data->rev_list.array[i].data;\n \t\t\tif (parent_entry->commit == to_push)\n \t\t\t\tgoto parent_found;\n@@ -248,7 +247,7 @@ static int ack(struct fetch_negotiator *n, struct commit *c)\n static void release(struct fetch_negotiator *n)\n {\n \tstruct data *data = n->data;\n-\tfor (int i = 0; i < data->rev_list.nr; i++)\n+\tfor (size_t i = 0; i < data->rev_list.nr; i++)\n \t\tfree(data->rev_list.array[i].data);\n \tclear_prio_queue(&data->rev_list);\n \tFREE_AND_NULL(data);\ndiff --git a/prio-queue.c b/prio-queue.c\nindex 450775a374..d0581dcc5c 100644\n--- a/prio-queue.c\n+++ b/prio-queue.c\n@@ -1,26 +1,29 @@\n #include \"git-compat-util.h\"\n #include \"prio-queue.h\"\n \n-static inline int compare(struct prio_queue *queue, int i, int j)\n+static inline int compare(struct prio_queue *queue, size_t i, size_t j)\n {\n \tint cmp = queue->compare(queue->array[i].data, queue->array[j].data,\n \t\t\t\t queue->cb_data);\n \tif (!cmp)\n-\t\tcmp = queue->array[i].ctr - queue->array[j].ctr;\n+\t\tcmp = (queue->array[i].ctr > queue->array[j].ctr) -\n+\t              (queue->array[i].ctr < queue->array[j].ctr);\n \treturn cmp;\n }\n \n-static inline void swap(struct prio_queue *queue, int i, int j)\n+static inline void swap(struct prio_queue *queue, size_t i, size_t j)\n {\n \tSWAP(queue->array[i], queue->array[j]);\n }\n \n void prio_queue_reverse(struct prio_queue *queue)\n {\n-\tint i, j;\n+\tsize_t i, j;\n \n \tif (queue->compare)\n \t\tBUG(\"prio_queue_reverse() on non-LIFO queue\");\n+\tif (!queue->nr)\n+\t\treturn;\n \tfor (i = 0; i < (j = (queue->nr - 1) - i); i++)\n \t\tswap(queue, i, j);\n }\n@@ -35,7 +38,7 @@ void clear_prio_queue(struct prio_queue *queue)\n \n void prio_queue_put(struct prio_queue *queue, void *thing)\n {\n-\tint ix, parent;\n+\tsize_t ix, parent;\n \n \t/* Append at the end */\n \tALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);\n@@ -58,7 +61,7 @@ void prio_queue_put(struct prio_queue *queue, void *thing)\n void *prio_queue_get(struct prio_queue *queue)\n {\n \tvoid *result;\n-\tint ix, child;\n+\tsize_t ix, child;\n \n \tif (!queue->nr)\n \t\treturn NULL;\ndiff --git a/prio-queue.h b/prio-queue.h\nindex 4f9a37e6be..36f370625f 100644\n--- a/prio-queue.h\n+++ b/prio-queue.h\n@@ -30,7 +30,7 @@ struct prio_queue {\n \tprio_queue_compare_fn compare;\n \tunsigned insertion_ctr;\n \tvoid *cb_data;\n-\tint alloc, nr;\n+\tsize_t alloc, nr;\n \tstruct prio_queue_entry *array;\n };\n \n-- \n2.48.0.rc0.406.g65874f98ea\n"},{"id":"509366","messageId":"20241220085337.GA133148@coredump.intra.peff.net","threadId":"62674","inReplyTo":"20241220084949.GA132704@coredump.intra.peff.net","subject":"Re: [PATCH] prio-queue: use size_t rather than int for size","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-20T08:53:37Z","receivedAt":"2024-12-20T08:53:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 20, 2024 at 03:49:49AM -0500, Jeff King wrote:\n\n> -static inline int compare(struct prio_queue *queue, int i, int j)\n> +static inline int compare(struct prio_queue *queue, size_t i, size_t j)\n>  {\n>  \tint cmp = queue->compare(queue->array[i].data, queue->array[j].data,\n>  \t\t\t\t queue->cb_data);\n>  \tif (!cmp)\n> -\t\tcmp = queue->array[i].ctr - queue->array[j].ctr;\n> +\t\tcmp = (queue->array[i].ctr > queue->array[j].ctr) -\n> +\t              (queue->array[i].ctr < queue->array[j].ctr);\n>  \treturn cmp;\n>  }\n\nSorry, just realized that \"diff --check\" (and apply) complains about the\nindentation here. It's a TAB followed by 14 spaces, instead of two TABs\nfollowed by 6 spaces. I guess caused by me lining things up manually.\n\n-Peff\n"},{"id":"509396","messageId":"xmqqh66yfk89.fsf@gitster.g","threadId":"62674","inReplyTo":"20241220085337.GA133148@coredump.intra.peff.net","subject":"Re: [PATCH] prio-queue: use size_t rather than int for size","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-12-20T15:27:18Z","receivedAt":"2024-12-20T15:27:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Dec 20, 2024 at 03:49:49AM -0500, Jeff King wrote:\n>\n>> -static inline int compare(struct prio_queue *queue, int i, int j)\n>> +static inline int compare(struct prio_queue *queue, size_t i, size_t j)\n>>  {\n>>  \tint cmp = queue->compare(queue->array[i].data, queue->array[j].data,\n>>  \t\t\t\t queue->cb_data);\n>>  \tif (!cmp)\n>> -\t\tcmp = queue->array[i].ctr - queue->array[j].ctr;\n>> +\t\tcmp = (queue->array[i].ctr > queue->array[j].ctr) -\n>> +\t              (queue->array[i].ctr < queue->array[j].ctr);\n>>  \treturn cmp;\n>>  }\n>\n> Sorry, just realized that \"diff --check\" (and apply) complains about the\n> indentation here. It's a TAB followed by 14 spaces, instead of two TABs\n> followed by 6 spaces. I guess caused by me lining things up manually.\n\n\"git am --whitespace=fix\" with or without \"-3\" corrects such\nglitches just fine, and \"git am --whitespace=error\" correctly stops\nme from applying such a patch.\n\nWhat is worrysome is \"git am -3 --whitespace=warn\" does not seem to\ncatch it (without \"-3\" it works just fine).  I do not know offhand\nif this is a recent regression or not.\n\n\n"},{"id":"509406","messageId":"20241220160153.GE152570@coredump.intra.peff.net","threadId":"62674","inReplyTo":"xmqqh66yfk89.fsf@gitster.g","subject":"Re: [PATCH] prio-queue: use size_t rather than int for size","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-20T16:01:53Z","receivedAt":"2024-12-20T16:01:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 20, 2024 at 07:27:18AM -0800, Junio C Hamano wrote:\n\n> > Sorry, just realized that \"diff --check\" (and apply) complains about the\n> > indentation here. It's a TAB followed by 14 spaces, instead of two TABs\n> > followed by 6 spaces. I guess caused by me lining things up manually.\n> \n> \"git am --whitespace=fix\" with or without \"-3\" corrects such\n> glitches just fine, and \"git am --whitespace=error\" correctly stops\n> me from applying such a patch.\n> \n> What is worrysome is \"git am -3 --whitespace=warn\" does not seem to\n> catch it (without \"-3\" it works just fine).  I do not know offhand\n> if this is a recent regression or not.\n\nInteresting. I noticed with stock \"git am\" (I sometimes \"reset --hard\"\nand reapply my own patches because I made tweaks to the commit message\nwhile sending).\n\nLooks like it does not warn even going back to v2.0.5 (my stock \"this\nwas a long time ago\" version). Curiously if you accidentally try to\napply the patch a second time, it does notice the problem.\n\nSo I agree it's a bug, but I think it has been around for a while.\n\n-Peff\n"},{"id":"509585","messageId":"Z25-PaOQg7lAeyxx@pks.im","threadId":"62674","inReplyTo":"20241220084949.GA132704@coredump.intra.peff.net","subject":"Re: [PATCH] prio-queue: use size_t rather than int for size","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-12-27T10:15:31Z","receivedAt":"2024-12-27T10:15:54Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Dec 20, 2024 at 03:49:49AM -0500, Jeff King wrote:\n[snip]\n>   4. The insertion_ctr variable is currently unsigned, but can likewise\n>      grow (it is actually worse, because adding and removing an element\n>      many times will keep increasing the counter, even though \"nr\" does\n>      not). I've bumped that to size_t here, as well.\n\nI agree that bumping it to `size_t` would be sensible, but it doesn't\nlook like you actually followed through with that change, as...\n\n> diff --git a/prio-queue.h b/prio-queue.h\n> index 4f9a37e6be..36f370625f 100644\n> --- a/prio-queue.h\n> +++ b/prio-queue.h\n> @@ -30,7 +30,7 @@ struct prio_queue {\n>  \tprio_queue_compare_fn compare;\n>  \tunsigned insertion_ctr;\n\n... it still says `unsigned` here.\n\nI was surprised by how few callers there are required any changes due to\n`.nr` changing. I scanned through the code and found one more instance\nwhere we have to adapt code, in commit-reach.c:queue_has_nonstale(). The\ncompiler does not generate warnings for this case because the file isn't\n-Wsign-compare clean yet.\n\nAnyway, I see that the patch has landed in \"master\" already. Let me send\na follow-up patch series to fix both issues.\n\nPatrick\n"},{"id":"509636","messageId":"20241227143440.GB88306@coredump.intra.peff.net","threadId":"62674","inReplyTo":"Z25-PaOQg7lAeyxx@pks.im","subject":"Re: [PATCH] prio-queue: use size_t rather than int for size","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-27T14:34:40Z","receivedAt":"2024-12-27T14:34:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 27, 2024 at 11:15:31AM +0100, Patrick Steinhardt wrote:\n\n> On Fri, Dec 20, 2024 at 03:49:49AM -0500, Jeff King wrote:\n> [snip]\n> >   4. The insertion_ctr variable is currently unsigned, but can likewise\n> >      grow (it is actually worse, because adding and removing an element\n> >      many times will keep increasing the counter, even though \"nr\" does\n> >      not). I've bumped that to size_t here, as well.\n> \n> I agree that bumping it to `size_t` would be sensible, but it doesn't\n> look like you actually followed through with that change, as...\n\nDoh, good catch. I had backed it out temporarily to confirm that it was\na problem even before the patch, but accidentally ended up with the\nwrong state in the commit.\n\n> I was surprised by how few callers there are required any changes due to\n> `.nr` changing. I scanned through the code and found one more instance\n> where we have to adapt code, in commit-reach.c:queue_has_nonstale(). The\n> compiler does not generate warnings for this case because the file isn't\n> -Wsign-compare clean yet.\n\nMakes sense.\n\n> Anyway, I see that the patch has landed in \"master\" already. Let me send\n> a follow-up patch series to fix both issues.\n\nThanks!\n\n-Peff\n"}]}