{"thread":{"id":"39363","subject":"[PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","startedAt":"2015-05-18T23:24:09Z","lastAt":"2015-05-19T21:19:52Z","messageCount":6,"participants":["René Scharfe","Stefan Beller","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"261524","messageId":"555A7499.7090900@web.de","threadId":"39363","inReplyTo":null,"subject":"[PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2015-05-18T23:24:09Z","receivedAt":"2015-05-18T23:24:09Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use an automatic variable for recent_bitmaps, an array of pointers.\nThis way we don't allocate too much and don't have to free the memory\nat the end. The old code over-allocated because it reserved enough\nmemory to store all of the structs it is only pointing to and never\nfreed it. 160 64-bit pointers take up 1280 bytes, which is not too\nmuch to be placed on the stack.\n\nMAX_XOR_OFFSET is turned into a preprocessor constant to make it\nconstant enough for use in an non-variable array declaration.\n\nNoticed-by: Stefan Beller \nSuggested-by: Jeff King \nSigned-off-by: Rene Scharfe \n---\nThis seems to have fallen through the cracks, or did I just miss it?\n\n pack-bitmap.c | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 62a98cc..e5abb8a 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -209,14 +209,12 @@ static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)\n \treturn buffer[(*pos)++];\n }\n \n+#define MAX_XOR_OFFSET 160\n+\n static int load_bitmap_entries_v1(struct bitmap_index *index)\n {\n-\tstatic const size_t MAX_XOR_OFFSET = 160;\n-\n \tuint32_t i;\n-\tstruct stored_bitmap **recent_bitmaps;\n-\n-\trecent_bitmaps = xcalloc(MAX_XOR_OFFSET, sizeof(struct stored_bitmap));\n+\tstruct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };\n \n \tfor (i = 0; i < index->entry_count; ++i) {\n \t\tint xor_offset, flags;\n-- \n2.4.1\n"},{"id":"261532","messageId":"CAGZ79kZeX_VqcvTt_kgGKyWH0SV2zsV_j1KuxNhwR18zWfp5LA@mail.gmail.com","threadId":"39363","inReplyTo":"555A7499.7090900@web.de","subject":"Re: [PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2015-05-19T00:57:13Z","receivedAt":"2015-05-19T00:57:13Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, May 18, 2015 at 4:24 PM, René Scharfe wrote:\n> Use an automatic variable for recent_bitmaps, an array of pointers.\n> This way we don't allocate too much and don't have to free the memory\n> at the end. The old code over-allocated because it reserved enough\n> memory to store all of the structs it is only pointing to and never\n> freed it. 160 64-bit pointers take up 1280 bytes, which is not too\n> much to be placed on the stack.\n>\n> MAX_XOR_OFFSET is turned into a preprocessor constant to make it\n> constant enough for use in an non-variable array declaration.\n>\n> Noticed-by: Stefan Beller \n> Suggested-by: Jeff King \n> Signed-off-by: Rene Scharfe \n> ---\n> This seems to have fallen through the cracks, or did I just miss it?\n\nI planned on resending it eventually. ;)\nBut with the usual definition of 'eventually',\nit may take a while.\n\nThanks for picking this up!\nStefan\n\n\n\n>\n> pack-bitmap.c | 8 +++-----\n> 1 file changed, 3 insertions(+), 5 deletions(-)\n>\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 62a98cc..e5abb8a 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -209,14 +209,12 @@ static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)\n> return buffer[(*pos)++];\n> }\n>\n> +#define MAX_XOR_OFFSET 160\n> +\n> static int load_bitmap_entries_v1(struct bitmap_index *index)\n> {\n> - static const size_t MAX_XOR_OFFSET = 160;\n\nIs there a reason why we prefer defines over a static const size_t here?\n\n> -\n> uint32_t i;\n> - struct stored_bitmap **recent_bitmaps;\n> -\n> - recent_bitmaps = xcalloc(MAX_XOR_OFFSET, sizeof(struct stored_bitmap));\n> + struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };\n\nThis looks fine to me.\n\n>\n> for (i = 0; i < index->entry_count; ++i) {\n> int xor_offset, flags;\n> --\n> 2.4.1\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"261533","messageId":"20150519022321.GA29026@peff.net","threadId":"39363","inReplyTo":"555A7499.7090900@web.de","subject":"Re: [PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-05-19T02:23:21Z","receivedAt":"2015-05-19T02:23:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 19, 2015 at 01:24:09AM +0200, René Scharfe wrote:\n\n> Use an automatic variable for recent_bitmaps, an array of pointers.\n> This way we don't allocate too much and don't have to free the memory\n> at the end. The old code over-allocated because it reserved enough\n> memory to store all of the structs it is only pointing to and never\n> freed it. 160 64-bit pointers take up 1280 bytes, which is not too\n> much to be placed on the stack.\n> \n> MAX_XOR_OFFSET is turned into a preprocessor constant to make it\n> constant enough for use in an non-variable array declaration.\n> \n> Noticed-by: Stefan Beller \n> Suggested-by: Jeff King \n> Signed-off-by: Rene Scharfe \n> ---\n> This seems to have fallen through the cracks, or did I just miss it?\n\nThanks, this looks good.\n\nI looked over the function one more time to make sure it is the function\nthat is wrong, and not my suggestion. :) The current code seems pretty\nobviously wrong.\n\n-Peff\n"},{"id":"261588","messageId":"xmqqoalg73md.fsf@gitster.dls.corp.google.com","threadId":"39363","inReplyTo":"20150519022321.GA29026@peff.net","subject":"Re: [PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-05-19T19:45:46Z","receivedAt":"2015-05-19T19:45:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, May 19, 2015 at 01:24:09AM +0200, René Scharfe wrote:\n>\n>> Use an automatic variable for recent_bitmaps, an array of pointers.\n>> This way we don't allocate too much and don't have to free the memory\n>> at the end. The old code over-allocated because it reserved enough\n>> memory to store all of the structs it is only pointing to and never\n>> freed it. 160 64-bit pointers take up 1280 bytes, which is not too\n>> much to be placed on the stack.\n>> \n>> MAX_XOR_OFFSET is turned into a preprocessor constant to make it\n>> constant enough for use in an non-variable array declaration.\n>> \n>> Noticed-by: Stefan Beller \n>> Suggested-by: Jeff King \n>> Signed-off-by: Rene Scharfe \n>> ---\n>> This seems to have fallen through the cracks, or did I just miss it?\n>\n> Thanks, this looks good.\n>\n> I looked over the function one more time to make sure it is the function\n> that is wrong, and not my suggestion. :) The current code seems pretty\n> obviously wrong.\n\nI actually cannot guess what the current code is trying to do. Was\nit an attempt to cache that many entries, but instead allocated and\ndiscarded the space it tried to use as a cache every time?\n"},{"id":"261591","messageId":"555B9D1E.2050609@web.de","threadId":"39363","inReplyTo":"CAGZ79kZeX_VqcvTt_kgGKyWH0SV2zsV_j1KuxNhwR18zWfp5LA@mail.gmail.com","subject":"Re: [PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2015-05-19T20:29:18Z","receivedAt":"2015-05-19T20:29:18Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 19.05.2015 um 02:57 schrieb Stefan Beller:\n> On Mon, May 18, 2015 at 4:24 PM, René Scharfe wrote:\n>> diff --git a/pack-bitmap.c b/pack-bitmap.c\n>> index 62a98cc..e5abb8a 100644\n>> --- a/pack-bitmap.c\n>> +++ b/pack-bitmap.c\n>> @@ -209,14 +209,12 @@ static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)\n>> return buffer[(*pos)++];\n>> }\n>>\n>> +#define MAX_XOR_OFFSET 160\n>> +\n>> static int load_bitmap_entries_v1(struct bitmap_index *index)\n>> {\n>> - static const size_t MAX_XOR_OFFSET = 160;\n>\n> Is there a reason why we prefer defines over a static const size_t here?\n\nYes, see below.\n\n>> -\n>> uint32_t i;\n>> - struct stored_bitmap **recent_bitmaps;\n>> -\n>> - recent_bitmaps = xcalloc(MAX_XOR_OFFSET, sizeof(struct stored_bitmap));\n>> + struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };\n\nIf MAX_XOR_OFFSET is a const then C89 does not allow this declaration. \nC99 gives you a variable-length array here. VLAs can't be initialized \nat declaration time, so we'd need to add a memset() call (at least with \nGCC 4.9). Overall it's simpler and shorter to use a macro.\n\nWe could also use an enum, but that's not exactly common.\n\nRené\n"},{"id":"261596","messageId":"20150519211952.GA23904@peff.net","threadId":"39363","inReplyTo":"xmqqoalg73md.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] pack-bitmaps: plug memory leak, fix allocation size for recent_bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-05-19T21:19:52Z","receivedAt":"2015-05-19T21:19:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 19, 2015 at 12:45:46PM -0700, Junio C Hamano wrote:\n\n> > I looked over the function one more time to make sure it is the function\n> > that is wrong, and not my suggestion. :) The current code seems pretty\n> > obviously wrong.\n> \n> I actually cannot guess what the current code is trying to do. Was\n> it an attempt to cache that many entries, but instead allocated and\n> discarded the space it tried to use as a cache every time?\n\nSort of. There are two caches at work.\n\nThe bitmaps on disk may be stored as XORs against nearby bitmaps up to\nMAX_XOR_OFFSET slots away. So our goal is to reconstruct the actual\nbitmaps and put them in our cache for later use. That's actually done by\nstore_bitmap(), which puts them into a hash table indexed by sha1.\n\nBut because we get the XOR base as an offset, we also need to be able to\nquickly say \"what was the bitmap that was N slots ago?\", and the hash\ncannot answer that quickly. So we keep a sliding window of the last\nMAX_XOR_OFFSET bitmaps (pointing to the cached bitmaps stored in the\nhash), and then we can index that directly by offset. And we can reuse\nthe array as a circular buffer (notice we always index it modulo the max\noffset).\n\nSo you can think of the recent_bitmaps as an auxiliary index into the\nbitmaps already cached by store_bitmap(). We don't need it after the xor\nreconstruction (actually I think we don't do the xor reconstruction\nhere, but instead retain a pointer to the xor base and lazily do it, but\nthe point is that we've created that pointer).\n\n-Peff\n"}]}