{"thread":{"id":"18511","subject":"[PATCH] avoid possible overflow in delta size filtering computation","startedAt":"2009-03-24T19:56:12Z","lastAt":"2009-03-27T02:23:35Z","messageCount":10,"participants":["Nicolas Pitre","Brandon Casey","Kjetil Barvik"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"109238","messageId":"alpine.LFD.2.00.0903241535010.26337@xanadu.home","threadId":"18511","inReplyTo":null,"subject":"[PATCH] avoid possible overflow in delta size filtering computation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-24T19:56:12Z","receivedAt":"2009-03-24T19:56:12Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On a 32-bit system, the maximum possible size for an object is less than \n4GB, while 64-bit systems may cope with larger objects. Due to this \nlimitation, variables holding object sizes are using an unsigned long \ntype (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n\nWhen large objects are encountered, and/or people play with large delta \ndepth values, it is possible for the maximum allowed delta size \ncomputation to overflow, especially on a 32-bit system. When this \noccurs, surviving result bits may represent a value much smaller than \nwhat it is supposed to be, or even zero. This prevents some objects \nfrom being deltified although they do get deltified when a smaller depth \nlimit is used. Fix this by always performing a 64-bit multiplication.\n\nSigned-off-by: Nicolas Pitre \n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 3a4bdbb..9fc3b35 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1293,7 +1293,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\tmax_size = trg_entry->delta_size;\n \t\tref_depth = trg->depth;\n \t}\n-\tmax_size = max_size * (max_depth - src->depth) /\n+\tmax_size = (uint64_t)max_size * (max_depth - src->depth) /\n \t\t\t\t\t\t(max_depth - ref_depth + 1);\n \tif (max_size == 0)\n \t\treturn 0;\n"},{"id":"109239","messageId":"IJd5MMCs9G_oJF_jS9hZAHkoKM0IvDNHuvHhhQ3MnKbPbSQlMYjOAg@cipher.nrlssc.navy.mil","threadId":"18511","inReplyTo":"alpine.LFD.2.00.0903241535010.26337@xanadu.home","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Brandon Casey","fromEmail":"casey@nrlssc.navy.mil","sentAt":"2009-03-24T20:20:08Z","receivedAt":"2009-03-24T20:20:08Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"Nicolas Pitre wrote:\n> On a 32-bit system, the maximum possible size for an object is less than \n> 4GB, while 64-bit systems may cope with larger objects. Due to this \n> limitation, variables holding object sizes are using an unsigned long \n> type (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n\nFYI: except on windows 64-bit where long is still 32 bits AFAIK\n\n-brandon\n"},{"id":"109241","messageId":"alpine.LFD.2.00.0903241652080.26337@xanadu.home","threadId":"18511","inReplyTo":"IJd5MMCs9G_oJF_jS9hZAHkoKM0IvDNHuvHhhQ3MnKbPbSQlMYjOAg@cipher.nrlssc.navy.mil","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-24T20:52:16Z","receivedAt":"2009-03-24T20:52:16Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 24 Mar 2009, Brandon Casey wrote:\n\n> Nicolas Pitre wrote:\n> > On a 32-bit system, the maximum possible size for an object is less than \n> > 4GB, while 64-bit systems may cope with larger objects. Due to this \n> > limitation, variables holding object sizes are using an unsigned long \n> > type (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n> \n> FYI: except on windows 64-bit where long is still 32 bits AFAIK\n\nWhatever. Same issue.\n\n\nNicolas\n"},{"id":"109280","messageId":"alpine.LFD.2.00.0903241653430.26337@xanadu.home","threadId":"18511","inReplyTo":"IJd5MMCs9G_oJF_jS9hZAHkoKM0IvDNHuvHhhQ3MnKbPbSQlMYjOAg@cipher.nrlssc.navy.mil","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-25T00:39:17Z","receivedAt":"2009-03-25T00:39:17Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 24 Mar 2009, Brandon Casey wrote:\n\n> Nicolas Pitre wrote:\n> > On a 32-bit system, the maximum possible size for an object is less than \n> > 4GB, while 64-bit systems may cope with larger objects. Due to this \n> > limitation, variables holding object sizes are using an unsigned long \n> > type (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n> \n> FYI: except on windows 64-bit where long is still 32 bits AFAIK\n\nWhatever. Same issue.\n\n\nNicolas\n"},{"id":"109347","messageId":"86hc1hdcj1.fsf@broadpark.no","threadId":"18511","inReplyTo":"alpine.LFD.2.00.0903241535010.26337@xanadu.home","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-03-25T12:15:14Z","receivedAt":"2009-03-25T12:15:14Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Nicolas Pitre writes:\n\n> On a 32-bit system, the maximum possible size for an object is less than \n> 4GB, while 64-bit systems may cope with larger objects. Due to this \n> limitation, variables holding object sizes are using an unsigned long \n> type (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n>\n> When large objects are encountered, and/or people play with large delta \n> depth values, it is possible for the maximum allowed delta size \n> computation to overflow, especially on a 32-bit system. When this \n> occurs, surviving result bits may represent a value much smaller than \n> what it is supposed to be, or even zero. This prevents some objects \n> from being deltified although they do get deltified when a smaller depth \n> limit is used. Fix this by always performing a 64-bit multiplication.\n>\n> Signed-off-by: Nicolas Pitre \n\n I added this patch and rerun the 2 test cases form the table where\n --depth is 20000 and 95000, and got the following result:\n\n --depth=20000 => file size: 19126077 delta: 73814\n --depth=95000 => file size: 19126087 delta: 73814\n\n So, it seems that this patch almost fixed the issue. But notice that\n the pack file was 10 bytes larger for the --depth=95000 case.\n\n I made a small perl script to compare the output from 'git verify-pack\n -v' of the 2 idx/pack files, and found the following difference(1)\n (first line from --depth=20000 case, second from --depth=95000):\n\n fe0a6f3e971373590714dbafd087b235ea60ac00 tree 9 19 18921247 731 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d\n fe0a6f3e971373590714dbafd087b235ea60ac00 tree 20 29 18921247 730 12e560f7fb28558b15e3a2008fba860f9a4b2222\n\n 'git show fe0a6f3e971373590714dbafd087b235ea60ac00' =>\n\ntree fe0a6f3e971373590714dbafd087b235ea60ac00\n\nMakefile\nt0000-basic.sh\ntest-lib.sh\n\n 'git show 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d' =>\n\ntree 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d\n\nMakefile\nt0000-basic.sh\nt0100-environment-names.sh\nt0200-update-cache.sh\nt0400-ls-files.sh\nt0500-ls-files.sh\nt1000-checkout-cache.sh\nt1001-checkout-cache.sh\ntest-lib.sh\n\n 'git show 12e560f7fb28558b15e3a2008fba860f9a4b2222' =>\n\ntree 12e560f7fb28558b15e3a2008fba860f9a4b2222\n\nMakefile\nt0000-basic.sh\nt0100-environment-names.sh\nt0200-update-cache.sh\nt0400-ls-files.sh\nt0500-ls-files.sh\nt1000-checkout-cache.sh\nt1001-checkout-cache.sh\ntest-lib.sh\n\n -- kjetil\n\n 1) there was lots of lines with different offsets, all of which was 10\n larger in the --depth=95000 case.\n"},{"id":"109366","messageId":"alpine.LFD.2.00.0903250936100.26337@xanadu.home","threadId":"18511","inReplyTo":"86hc1hdcj1.fsf@broadpark.no","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-25T16:18:00Z","receivedAt":"2009-03-25T16:18:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 25 Mar 2009, Kjetil Barvik wrote:\n\n> Nicolas Pitre writes:\n> \n> > On a 32-bit system, the maximum possible size for an object is less than \n> > 4GB, while 64-bit systems may cope with larger objects. Due to this \n> > limitation, variables holding object sizes are using an unsigned long \n> > type (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n> >\n> > When large objects are encountered, and/or people play with large delta \n> > depth values, it is possible for the maximum allowed delta size \n> > computation to overflow, especially on a 32-bit system. When this \n> > occurs, surviving result bits may represent a value much smaller than \n> > what it is supposed to be, or even zero. This prevents some objects \n> > from being deltified although they do get deltified when a smaller depth \n> > limit is used. Fix this by always performing a 64-bit multiplication.\n> >\n> > Signed-off-by: Nicolas Pitre \n> \n> I added this patch and rerun the 2 test cases form the table where\n> --depth is 20000 and 95000, and got the following result:\n> \n> --depth=20000 => file size: 19126077 delta: 73814\n> --depth=95000 => file size: 19126087 delta: 73814\n> \n> So, it seems that this patch almost fixed the issue. But notice that\n> the pack file was 10 bytes larger for the --depth=95000 case.\n> \n> I made a small perl script to compare the output from 'git verify-pack\n> -v' of the 2 idx/pack files, and found the following difference(1)\n> (first line from --depth=20000 case, second from --depth=95000):\n> \n> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 9 19 18921247 731 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d\n> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 20 29 18921247 730 12e560f7fb28558b15e3a2008fba860f9a4b2222\n\nOK. Apparently, a different base object for that one delta was chosen \nbetween those two runs.\n\nIs your machine SMP?\n\n\nNicolas\n"},{"id":"109373","messageId":"86bprptvcx.fsf@broadpark.no","threadId":"18511","inReplyTo":"alpine.LFD.2.00.0903250936100.26337@xanadu.home","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-03-25T16:34:06Z","receivedAt":"2009-03-25T16:34:06Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Nicolas Pitre writes:\n\n> On Wed, 25 Mar 2009, Kjetil Barvik wrote:\n>\n>> Nicolas Pitre writes:\n>> \n>> > On a 32-bit system, the maximum possible size for an object is less than \n>> > 4GB, while 64-bit systems may cope with larger objects. Due to this \n>> > limitation, variables holding object sizes are using an unsigned long \n>> > type (32 bits on 32-bit systems, or 64 bits on 64-bit systems).\n>> >\n>> > When large objects are encountered, and/or people play with large delta \n>> > depth values, it is possible for the maximum allowed delta size \n>> > computation to overflow, especially on a 32-bit system. When this \n>> > occurs, surviving result bits may represent a value much smaller than \n>> > what it is supposed to be, or even zero. This prevents some objects \n>> > from being deltified although they do get deltified when a smaller depth \n>> > limit is used. Fix this by always performing a 64-bit multiplication.\n>> >\n>> > Signed-off-by: Nicolas Pitre \n>> \n>> I added this patch and rerun the 2 test cases form the table where\n>> --depth is 20000 and 95000, and got the following result:\n>> \n>> --depth=20000 => file size: 19126077 delta: 73814\n>> --depth=95000 => file size: 19126087 delta: 73814\n>> \n>> So, it seems that this patch almost fixed the issue. But notice that\n>> the pack file was 10 bytes larger for the --depth=95000 case.\n>> \n>> I made a small perl script to compare the output from 'git verify-pack\n>> -v' of the 2 idx/pack files, and found the following difference(1)\n>> (first line from --depth=20000 case, second from --depth=95000):\n>> \n>> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 9 19 18921247 731 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d\n>> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 20 29 18921247 730 12e560f7fb28558b15e3a2008fba860f9a4b2222\n>\n> OK. Apparently, a different base object for that one delta was chosen \n> between those two runs.\n>\n> Is your machine SMP?\n\n kjetil ~$ uname -a\n Linux localhost 2.6.28.4 #26 SMP PREEMPT Tue Feb 10 17:07:14 CET 2009\n i686 Intel(R) Core(TM)2 CPU T7200 @ 2.00GHz GenuineIntel GNU/Linux\n\n -- kjetil\n"},{"id":"109402","messageId":"alpine.LFD.2.00.0903251514360.26337@xanadu.home","threadId":"18511","inReplyTo":"86bprptvcx.fsf@broadpark.no","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-25T19:17:31Z","receivedAt":"2009-03-25T19:17:31Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 25 Mar 2009, Kjetil Barvik wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Wed, 25 Mar 2009, Kjetil Barvik wrote:\n> >\n> >> So, it seems that this patch almost fixed the issue. But notice that\n> >> the pack file was 10 bytes larger for the --depth=95000 case.\n> >> \n> >> I made a small perl script to compare the output from 'git verify-pack\n> >> -v' of the 2 idx/pack files, and found the following difference(1)\n> >> (first line from --depth=20000 case, second from --depth=95000):\n> >> \n> >> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 9 19 18921247 731 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d\n> >> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 20 29 18921247 730 12e560f7fb28558b15e3a2008fba860f9a4b2222\n> >\n> > OK. Apparently, a different base object for that one delta was chosen \n> > between those two runs.\n> >\n> > Is your machine SMP?\n> \n> kjetil ~$ uname -a\n> Linux localhost 2.6.28.4 #26 SMP PREEMPT Tue Feb 10 17:07:14 CET 2009\n> i686 Intel(R) Core(TM)2 CPU T7200 @ 2.00GHz GenuineIntel GNU/Linux\n\nHere you go. If you want a perfectly deterministic repacking, you'll \nhave to force the pack.threads config option to 1.\n\n\nNicolas\n"},{"id":"109496","messageId":"86y6usah1p.fsf@broadpark.no","threadId":"18511","inReplyTo":"alpine.LFD.2.00.0903251514360.26337@xanadu.home","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-03-26T07:18:10Z","receivedAt":"2009-03-26T07:18:10Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Nicolas Pitre writes:\n\n> On Wed, 25 Mar 2009, Kjetil Barvik wrote:\n>\n>> Nicolas Pitre writes:\n>> \n>> > On Wed, 25 Mar 2009, Kjetil Barvik wrote:\n>> >\n>> >> So, it seems that this patch almost fixed the issue. But notice that\n>> >> the pack file was 10 bytes larger for the --depth=95000 case.\n>> >> \n>> >> I made a small perl script to compare the output from 'git verify-pack\n>> >> -v' of the 2 idx/pack files, and found the following difference(1)\n>> >> (first line from --depth=20000 case, second from --depth=95000):\n>> >> \n>> >> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 9 19 18921247 731 96a3ec5789504e6d0f90c99fb1937af1ebd58e2d\n>> >> fe0a6f3e971373590714dbafd087b235ea60ac00 tree 20 29 18921247 730 12e560f7fb28558b15e3a2008fba860f9a4b2222\n>> >\n>> > OK. Apparently, a different base object for that one delta was chosen \n>> > between those two runs.\n>> >\n>> > Is your machine SMP?\n>> \n>> kjetil ~$ uname -a\n>> Linux localhost 2.6.28.4 #26 SMP PREEMPT Tue Feb 10 17:07:14 CET 2009\n>> i686 Intel(R) Core(TM)2 CPU T7200 @ 2.00GHz GenuineIntel GNU/Linux\n>\n> Here you go. If you want a perfectly deterministic repacking, you'll \n> have to force the pack.threads config option to 1.\n\n OK, have rerun the test again with pack.config set to 1, and got the\n exact same result(1) as above this time also! :-)\n\n And I think I can explain the reason for the same result: When the\n --window and/or --depth value(s) is larger than (half?) the value of\n possible number of objects (98438 in this time), I think that the\n thread logic finds out that it can only run one thread (there is not\n room/objects enough for 2 or more threads).\n\n This also explains what I see when I run the repack command (without\n the pack.config option), only 1 git process is running on 1 of the\n CPU's from the start, and the other is idle.\n\n ~~\n\n Give me a hint if you want some debug info from the 2 pack/idx files.\n\n -- kjetil\n\n 1) The output from the 2 'git repack' commands did not show the\n \"running delta with 2 threads\" (or something similar) this time.\n I guess this is the sign that \"pack.threads = 1\" is working.\n"},{"id":"109594","messageId":"alpine.LFD.2.00.0903262218470.18797@xanadu.home","threadId":"18511","inReplyTo":"86y6usah1p.fsf@broadpark.no","subject":"Re: [PATCH] avoid possible overflow in delta size filtering computation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-03-27T02:23:35Z","receivedAt":"2009-03-27T02:23:35Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 26 Mar 2009, Kjetil Barvik wrote:\n\n> Nicolas Pitre writes:\n> \n> > Here you go. If you want a perfectly deterministic repacking, you'll \n> > have to force the pack.threads config option to 1.\n> \n> OK, have rerun the test again with pack.config set to 1, and got the\n> exact same result(1) as above this time also! :-)\n\nGood.\n\n> Give me a hint if you want some debug info from the 2 pack/idx files.\n\nI think there is nothing else to debug. Having some differences between \nsuccessive threaded repacks is expected.\n\n\nNicolas\n"}]}