{"thread":{"id":"11692","subject":"pack-objects: Fix segfault when object count is less than thread count","startedAt":"2008-01-21T14:35:45Z","lastAt":"2008-01-21T17:53:59Z","messageCount":6,"participants":["Sergey Vlasov","Johannes Sixt","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"66142","messageId":"1200926145-14625-1-git-send-email-vsu@altlinux.ru","threadId":"11692","inReplyTo":null,"subject":"pack-objects: Fix segfault when object count is less than thread count","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2008-01-21T14:35:45Z","receivedAt":"2008-01-21T14:35:45Z","isPatch":false,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"When partitioning the work amongst threads, dividing the number of\nobjects by the number of threads may return 0 when there are less\nobjects than threads; this will cause the subsequent code to segfault\nwhen accessing list[sub_size-1].  Fix this by ensuring that sub_size\nis not zero if there is at least one object to process.\n\nSigned-off-by: Sergey Vlasov <vsu@altlinux.ru>\n---\n builtin-pack-objects.c |    3 +++\n 1 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex ec10238..cdf8aae 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1665,6 +1665,9 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \tfor (i = 0; i < delta_search_threads; i++) {\n \t\tunsigned sub_size = list_size / (delta_search_threads - i);\n \n+\t\tif (sub_size == 0 && list_size >= 1)\n+\t\t\tsub_size = 1;\n+\n \t\tp[i].window = window;\n \t\tp[i].depth = depth;\n \t\tp[i].processed = processed;\n-- \n1.5.4.rc4.14.gd50a3\n"},{"id":"66143","messageId":"4794B65E.5000502@viscovery.net","threadId":"11692","inReplyTo":"1200926145-14625-1-git-send-email-vsu@altlinux.ru","subject":"Re: pack-objects: Fix segfault when object count is less than thread count","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2008-01-21T15:12:30Z","receivedAt":"2008-01-21T15:12:30Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Sergey Vlasov schrieb:\n> When partitioning the work amongst threads, dividing the number of\n> objects by the number of threads may return 0 when there are less\n> objects than threads; this will cause the subsequent code to segfault\n> when accessing list[sub_size-1].  Fix this by ensuring that sub_size\n> is not zero if there is at least one object to process.\n> \n> Signed-off-by: Sergey Vlasov <vsu@altlinux.ru>\n> ---\n>  builtin-pack-objects.c |    3 +++\n>  1 files changed, 3 insertions(+), 0 deletions(-)\n> \n> diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> index ec10238..cdf8aae 100644\n> --- a/builtin-pack-objects.c\n> +++ b/builtin-pack-objects.c\n> @@ -1665,6 +1665,9 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n>  \tfor (i = 0; i < delta_search_threads; i++) {\n>  \t\tunsigned sub_size = list_size / (delta_search_threads - i);\n>  \n> +\t\tif (sub_size == 0 && list_size >= 1)\n> +\t\t\tsub_size = 1;\n> +\n>  \t\tp[i].window = window;\n>  \t\tp[i].depth = depth;\n>  \t\tp[i].processed = processed;\n\nI think it fits the logic better to include sub_size > 0 in the while loop\nthat follows, like so:\n\n\t\t/* try to split chunks on \"path\" boundaries */\n\t\twhile (0 < sub_size && sub_size < list_size &&\n\t\t       list[sub_size]->hash &&\n\t\t       list[sub_size]->hash == list[sub_size-1]->hash)\n\t\t\tsub_size++;\n\nbecause we explicitly want to allow threads to \"work\" on zero objects\n(i.e. do nothing at all), but if a thread does get assigned some work,\nthen its chunk is extended past the next path boundary. This way you\ncollapse two special cases - \"zero-sized chunk\" and \"path boundary\" - into\none.\n\n-- Hannes\n"},{"id":"66146","messageId":"alpine.LFD.1.00.0801211103480.20753@xanadu.home","threadId":"11692","inReplyTo":"1200926145-14625-1-git-send-email-vsu@altlinux.ru","subject":"Re: pack-objects: Fix segfault when object count is less than thread count","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-01-21T16:07:15Z","receivedAt":"2008-01-21T16:07:15Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Jan 2008, Sergey Vlasov wrote:\n\n> When partitioning the work amongst threads, dividing the number of\n> objects by the number of threads may return 0 when there are less\n> objects than threads; this will cause the subsequent code to segfault\n> when accessing list[sub_size-1].  Fix this by ensuring that sub_size\n> is not zero if there is at least one object to process.\n\nNo.  Forcing one object in a thread is counter productive since it won't \nhave anything to delta against.  Instead, the thread should be allowed \nto have zero objects and let the other threads have more.\n\nThis patch would be a proper fix:\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex ec10238..d3efeff 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1672,7 +1672,8 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \t\tp[i].data_ready = 0;\n \n \t\t/* try to split chunks on \"path\" boundaries */\n-\t\twhile (sub_size < list_size && list[sub_size]->hash &&\n+\t\twhile (sub_size && sub_size < list_size &&\n+\t\t       list[sub_size]->hash &&\n \t\t       list[sub_size]->hash == list[sub_size-1]->hash)\n \t\t\tsub_size++;\n \n"},{"id":"66147","messageId":"alpine.LFD.1.00.0801211107500.20753@xanadu.home","threadId":"11692","inReplyTo":"4794B65E.5000502@viscovery.net","subject":"Re: pack-objects: Fix segfault when object count is less than thread count","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-01-21T16:08:34Z","receivedAt":"2008-01-21T16:08:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Jan 2008, Johannes Sixt wrote:\n\n> Sergey Vlasov schrieb:\n> > When partitioning the work amongst threads, dividing the number of\n> > objects by the number of threads may return 0 when there are less\n> > objects than threads; this will cause the subsequent code to segfault\n> > when accessing list[sub_size-1].  Fix this by ensuring that sub_size\n> > is not zero if there is at least one object to process.\n> > \n> > Signed-off-by: Sergey Vlasov <vsu@altlinux.ru>\n> > ---\n> >  builtin-pack-objects.c |    3 +++\n> >  1 files changed, 3 insertions(+), 0 deletions(-)\n> > \n> > diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> > index ec10238..cdf8aae 100644\n> > --- a/builtin-pack-objects.c\n> > +++ b/builtin-pack-objects.c\n> > @@ -1665,6 +1665,9 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n> >  \tfor (i = 0; i < delta_search_threads; i++) {\n> >  \t\tunsigned sub_size = list_size / (delta_search_threads - i);\n> >  \n> > +\t\tif (sub_size == 0 && list_size >= 1)\n> > +\t\t\tsub_size = 1;\n> > +\n> >  \t\tp[i].window = window;\n> >  \t\tp[i].depth = depth;\n> >  \t\tp[i].processed = processed;\n> \n> I think it fits the logic better to include sub_size > 0 in the while loop\n> that follows, like so:\n> \n> \t\t/* try to split chunks on \"path\" boundaries */\n> \t\twhile (0 < sub_size && sub_size < list_size &&\n> \t\t       list[sub_size]->hash &&\n> \t\t       list[sub_size]->hash == list[sub_size-1]->hash)\n> \t\t\tsub_size++;\n> \n> because we explicitly want to allow threads to \"work\" on zero objects\n> (i.e. do nothing at all), but if a thread does get assigned some work,\n> then its chunk is extended past the next path boundary. This way you\n> collapse two special cases - \"zero-sized chunk\" and \"path boundary\" - into\n> one.\n\nExact.\n\n\nNicolas\n"},{"id":"66156","messageId":"20080121174052.GA4627@atlas.home","threadId":"11692","inReplyTo":"alpine.LFD.1.00.0801211103480.20753@xanadu.home","subject":"Re: pack-objects: Fix segfault when object count is less than thread count","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2008-01-21T17:40:52Z","receivedAt":"2008-01-21T17:40:52Z","isPatch":false,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"On Mon, Jan 21, 2008 at 11:07:15AM -0500, Nicolas Pitre wrote:\n> On Mon, 21 Jan 2008, Sergey Vlasov wrote:\n> \n> > When partitioning the work amongst threads, dividing the number of\n> > objects by the number of threads may return 0 when there are less\n> > objects than threads; this will cause the subsequent code to segfault\n> > when accessing list[sub_size-1].  Fix this by ensuring that sub_size\n> > is not zero if there is at least one object to process.\n> \n> No.  Forcing one object in a thread is counter productive since it won't \n> have anything to delta against.  Instead, the thread should be allowed \n> to have zero objects and let the other threads have more.\n> \n> This patch would be a proper fix:\n> \n> diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> index ec10238..d3efeff 100644\n> --- a/builtin-pack-objects.c\n> +++ b/builtin-pack-objects.c\n> @@ -1672,7 +1672,8 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n>  \t\tp[i].data_ready = 0;\n>  \n>  \t\t/* try to split chunks on \"path\" boundaries */\n> -\t\twhile (sub_size < list_size && list[sub_size]->hash &&\n> +\t\twhile (sub_size && sub_size < list_size &&\n> +\t\t       list[sub_size]->hash &&\n>  \t\t       list[sub_size]->hash == list[sub_size-1]->hash)\n>  \t\t\tsub_size++;\n\nActually there will not be any significant differences - with my patch\nthe object distribution between threads will be 1, 1, ..., 0, 0...,\nand with your patch it would be 0, 0, ..., 1, 1, ... (unless the\nobjects had the same hash, in which case they would be passed to a\nsingle thread in both cases).\n\nWe could even introduce some limit on the number of objects below\nwhich multithreaded packing is not attempted, so that packing a small\nnumber of objects would be more efficient.\n"},{"id":"66157","messageId":"alpine.LFD.1.00.0801211248590.20753@xanadu.home","threadId":"11692","inReplyTo":"20080121174052.GA4627@atlas.home","subject":"Re: pack-objects: Fix segfault when object count is less than thread count","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-01-21T17:53:59Z","receivedAt":"2008-01-21T17:53:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 21 Jan 2008, Sergey Vlasov wrote:\n\n> On Mon, Jan 21, 2008 at 11:07:15AM -0500, Nicolas Pitre wrote:\n> > On Mon, 21 Jan 2008, Sergey Vlasov wrote:\n> > \n> > > When partitioning the work amongst threads, dividing the number of\n> > > objects by the number of threads may return 0 when there are less\n> > > objects than threads; this will cause the subsequent code to segfault\n> > > when accessing list[sub_size-1].  Fix this by ensuring that sub_size\n> > > is not zero if there is at least one object to process.\n> > \n> > No.  Forcing one object in a thread is counter productive since it won't \n> > have anything to delta against.  Instead, the thread should be allowed \n> > to have zero objects and let the other threads have more.\n> > \n> > This patch would be a proper fix:\n> > \n> > diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> > index ec10238..d3efeff 100644\n> > --- a/builtin-pack-objects.c\n> > +++ b/builtin-pack-objects.c\n> > @@ -1672,7 +1672,8 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n> >  \t\tp[i].data_ready = 0;\n> >  \n> >  \t\t/* try to split chunks on \"path\" boundaries */\n> > -\t\twhile (sub_size < list_size && list[sub_size]->hash &&\n> > +\t\twhile (sub_size && sub_size < list_size &&\n> > +\t\t       list[sub_size]->hash &&\n> >  \t\t       list[sub_size]->hash == list[sub_size-1]->hash)\n> >  \t\t\tsub_size++;\n> \n> Actually there will not be any significant differences - with my patch\n> the object distribution between threads will be 1, 1, ..., 0, 0...,\n> and with your patch it would be 0, 0, ..., 1, 1, ...\n\nOr more likely 0, 0, ..., 2.\n\nAnd the code is simpler.\n\n> We could even introduce some limit on the number of objects below\n> which multithreaded packing is not attempted, so that packing a small\n> number of objects would be more efficient.\n\nPossibly.  But that's not a requirement at this moment.\n\n\nNicolas\n"}]}