{"thread":{"id":"34551","subject":"[RFC/PATCH] commit-slab.h: Fix memory allocation and addressing","startedAt":"2013-07-27T19:00:07Z","lastAt":"2013-07-29T15:42:55Z","messageCount":2,"participants":["Ramsay Jones","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"224188","messageId":"51F418B7.30507@ramsay1.demon.co.uk","threadId":"34551","inReplyTo":null,"subject":"[RFC/PATCH] commit-slab.h: Fix memory allocation and addressing","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsay1.demon.co.uk","sentAt":"2013-07-27T19:00:07Z","receivedAt":"2013-07-27T19:00:07Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\nThe slab initialization code includes the calculation of the\nslab 'elem_size', which is in turn used to determine the size\n(capacity) of the slab. Each element of the slab represents an\narray, of length 'stride', of 'elemtype'. (Note that it may be\nclearer if the define_commit_slab macro parameter was called\n'basetype' rather than 'elemtype'). However, the 'elem_size'\ncalculation incorrectly uses 'sizeof(struct slabname)' in the\nexpression, rather than 'sizeof(elemtype)'.\n\nWithin the slab access routine, <slabname>_at(), the given commit\n'index' is transformed into an (slab#, slot#) pair used to address\nthe required element (a pointer to the first element of the array\nof 'elemtype' associated with that commit). The current code to\ncalculate these address coordinates multiplies the commit index\nby the 'stride' which, at least for the slab#, produces the wrong\nresult. Using the commit index directly, without scaling by the\n'stride', produces the correct 'logical' address.\n\nAlso, when allocating a new slab, the size of the allocation only\nallows for a slab containing elements of single element arrays of\n'elemtype'. This should allow for elements of an array of length\n'stride' of 'elemtype'. In order to fix this, we need to change\nthe element size parameter to xcalloc() by multiplying the current\nelement size (sizeof(**s->slab)) by the s->stride.\n\nHaving changed the calculation of the slot#, we now need to convert\nthe logical 'nth_slot', by scaling with s->stride, into the correct\nphysical address.\n\nSigned-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk>\n---\n\nHi Junio,\n\nWhile looking into a sparse warning, which involved the use of the\n\"commit-slab.h\" header file, I noticed some problems with that code.\n(at least I _think_ I did! ;-)\n\nI was convinced, just by reading the code in the header, that when\nused with stride > 1, the memory allocated to a slab would not be\nsufficient. (ie it would be too small by:\n    s->slab_size * (sizeof(**s->slab) * (stride - 1))\n). So, I had expected t3202-show-branch-octopus.sh to provoke memory\nerror reports when run under valgrind.\n\nHmm, it didn't ... so much for that theory! :-D\n\nSo, I'm a little puzzled; I must be missing something obvious, which\nis why this is marked RFC.\n\nWhat am I missing?\n\nATB,\nRamsay Jones\n\n\n commit-slab.h | 13 ++++++-------\n 1 file changed, 6 insertions(+), 7 deletions(-)\n\ndiff --git a/commit-slab.h b/commit-slab.h\nindex 7d48163..d4c8286 100644\n--- a/commit-slab.h\n+++ b/commit-slab.h\n@@ -48,7 +48,7 @@ static void init_ ##slabname## _with_stride(struct slabname *s,\t\t\\\n \tif (!stride)\t\t\t\t\t\t\t\\\n \t\tstride = 1;\t\t\t\t\t\t\\\n \ts->stride = stride;\t\t\t\t\t\t\\\n-\telem_size = sizeof(struct slabname) * stride;\t\t\t\\\n+\telem_size = sizeof(elemtype) * stride;\t\t\t\t\\\n \ts->slab_size = COMMIT_SLAB_SIZE / elem_size;\t\t\t\\\n \ts->slab_count = 0;\t\t\t\t\t\t\\\n \ts->slab = NULL;\t\t\t\t\t\t\t\\\n@@ -72,11 +72,10 @@ static void clear_ ##slabname(struct slabname *s)\t\t\t\\\n static elemtype *slabname## _at(struct slabname *s,\t\t\t\\\n \t\t\t\tconst struct commit *c)\t\t\t\\\n {\t\t\t\t\t\t\t\t\t\\\n-\tint nth_slab, nth_slot, ix;\t\t\t\t\t\\\n+\tint nth_slab, nth_slot;\t\t\t\t\t\t\\\n \t\t\t\t\t\t\t\t\t\\\n-\tix = c->index * s->stride;\t\t\t\t\t\\\n-\tnth_slab = ix / s->slab_size;\t\t\t\t\t\\\n-\tnth_slot = ix % s->slab_size;\t\t\t\t\t\\\n+\tnth_slab = c->index / s->slab_size;\t\t\t\t\\\n+\tnth_slot = c->index % s->slab_size;\t\t\t\t\\\n \t\t\t\t\t\t\t\t\t\\\n \tif (s->slab_count <= nth_slab) {\t\t\t\t\\\n \t\tint i;\t\t\t\t\t\t\t\\\n@@ -89,8 +88,8 @@ static elemtype *slabname## _at(struct slabname *s,\t\t\t\\\n \t}\t\t\t\t\t\t\t\t\\\n \tif (!s->slab[nth_slab])\t\t\t\t\t\t\\\n \t\ts->slab[nth_slab] = xcalloc(s->slab_size,\t\t\\\n-\t\t\t\t\t    sizeof(**s->slab));\t\t\\\n-\treturn &s->slab[nth_slab][nth_slot];\t\t\t\t\\\n+\t\t\t\t\t    sizeof(**s->slab) * s->stride);\t\t\\\n+\treturn &s->slab[nth_slab][nth_slot * s->stride];\t\t\t\t\\\n }\t\t\t\t\t\t\t\t\t\\\n \t\t\t\t\t\t\t\t\t\\\n static int stat_ ##slabname## realloc\n-- \n1.8.3\n"},{"id":"224228","messageId":"7vppu11if4.fsf@alter.siamese.dyndns.org","threadId":"34551","inReplyTo":"51F418B7.30507@ramsay1.demon.co.uk","subject":"Re: [RFC/PATCH] commit-slab.h: Fix memory allocation and addressing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-29T15:42:55Z","receivedAt":"2013-07-29T15:42:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ramsay Jones <ramsay@ramsay1.demon.co.uk> writes:\n\n> I was convinced, just by reading the code in the header, that when\n> used with stride > 1, the memory allocated to a slab would not be\n> sufficient. (ie it would be too small by:\n>     s->slab_size * (sizeof(**s->slab) * (stride - 1))\n> ). So, I had expected t3202-show-branch-octopus.sh to provoke memory\n> error reports when run under valgrind.\n>\n> Hmm, it didn't ... so much for that theory! :-D\n>\n> So, I'm a little puzzled; I must be missing something obvious, which\n> is why this is marked RFC.\n>\n> What am I missing?\n\nBecause sizeof(struct reachabe_cslab) is much larger than\nsizeof(unsigned char), and the test does not use that many commits\nto cause us to spill to more than one slab?\n\nYour fix of elem_size in your first hunk is correct; for stride N,\nwe want to allocate N*sizeof(elemtype) consecutive bytes in a single\nslab (we do not want to split the array of N elements across two\nslabs).  So \"elem_size\" is the size of the array for a single commit\n(when stride==1, we are storing an array with a single element).\n\nAnd we can fit arrays for s->slab_size = (COMMIT_SLAB_SIZE /\nelem_size) commits in a single slab.  c->index / s->slab_size gives\nus which slab the array for the commit goes, and modulus gives us\nwhich slot in that slab the array sits.  So the second hunk looks\ncorrect, too.\n\nAnd of course, the slab must be allocated as an array with\ns->slab_size elements, each of which holds s->stride elements of\nelem_type that is sizeof(**s->slab) bytes long.\n\nThanks; the patch looks correct to me.\n\nIt is somewhat embarrassing that nobody caught it X-<.\n\n>  commit-slab.h | 13 ++++++-------\n>  1 file changed, 6 insertions(+), 7 deletions(-)\n>\n> diff --git a/commit-slab.h b/commit-slab.h\n> index 7d48163..d4c8286 100644\n> --- a/commit-slab.h\n> +++ b/commit-slab.h\n> @@ -48,7 +48,7 @@ static void init_ ##slabname## _with_stride(struct slabname *s,\t\t\\\n>  \tif (!stride)\t\t\t\t\t\t\t\\\n>  \t\tstride = 1;\t\t\t\t\t\t\\\n>  \ts->stride = stride;\t\t\t\t\t\t\\\n> -\telem_size = sizeof(struct slabname) * stride;\t\t\t\\\n> +\telem_size = sizeof(elemtype) * stride;\t\t\t\t\\\n>  \ts->slab_size = COMMIT_SLAB_SIZE / elem_size;\t\t\t\\\n>  \ts->slab_count = 0;\t\t\t\t\t\t\\\n>  \ts->slab = NULL;\t\t\t\t\t\t\t\\\n> @@ -72,11 +72,10 @@ static void clear_ ##slabname(struct slabname *s)\t\t\t\\\n>  static elemtype *slabname## _at(struct slabname *s,\t\t\t\\\n>  \t\t\t\tconst struct commit *c)\t\t\t\\\n>  {\t\t\t\t\t\t\t\t\t\\\n> -\tint nth_slab, nth_slot, ix;\t\t\t\t\t\\\n> +\tint nth_slab, nth_slot;\t\t\t\t\t\t\\\n>  \t\t\t\t\t\t\t\t\t\\\n> -\tix = c->index * s->stride;\t\t\t\t\t\\\n> -\tnth_slab = ix / s->slab_size;\t\t\t\t\t\\\n> -\tnth_slot = ix % s->slab_size;\t\t\t\t\t\\\n> +\tnth_slab = c->index / s->slab_size;\t\t\t\t\\\n> +\tnth_slot = c->index % s->slab_size;\t\t\t\t\\\n>  \t\t\t\t\t\t\t\t\t\\\n>  \tif (s->slab_count <= nth_slab) {\t\t\t\t\\\n>  \t\tint i;\t\t\t\t\t\t\t\\\n> @@ -89,8 +88,8 @@ static elemtype *slabname## _at(struct slabname *s,\t\t\t\\\n>  \t}\t\t\t\t\t\t\t\t\\\n>  \tif (!s->slab[nth_slab])\t\t\t\t\t\t\\\n>  \t\ts->slab[nth_slab] = xcalloc(s->slab_size,\t\t\\\n> -\t\t\t\t\t    sizeof(**s->slab));\t\t\\\n> -\treturn &s->slab[nth_slab][nth_slot];\t\t\t\t\\\n> +\t\t\t\t\t    sizeof(**s->slab) * s->stride);\t\t\\\n> +\treturn &s->slab[nth_slab][nth_slot * s->stride];\t\t\t\t\\\n>  }\t\t\t\t\t\t\t\t\t\\\n>  \t\t\t\t\t\t\t\t\t\\\n>  static int stat_ ##slabname## realloc\n"}]}