[PATCH] bisect: save heap memory. allocate only the required amount

Find and allocate the required amount instead of
allocating extra 100 bytes

Signed-off-by: Arjun Sreedharan <redacted>
---
 bisect.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/bisect.c b/bisect.c
index d6e851d..c96aab0 100644
--- a/bisect.c
+++ b/bisect.c

@@ -215,10 +215,13 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 	}
 	qsort(array, cnt, sizeof(*array), compare_commit_dist);
 	for (p = list, i = 0; i < cnt; i++) {
-		struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+		char name[100];
+		sprintf(name, "dist=%d", array[i].distance);
+		int name_len = strlen(name);
+		struct name_decoration *r = xmalloc(sizeof(*r) + name_len);
 		struct object *obj = &(array[i].commit->object);
 
-		sprintf(r->name, "dist=%d", array[i].distance);
+		memcpy(r->name, name, name_len + 1);
 		r->next = add_decoration(&name_decoration, obj, r);
 		p->item = array[i].commit;
 		p = p->next;

-- 
1.7.11.7

On 24.08.2014 16:17, Arjun Sreedharan wrote:

Would it make sense to convert the 'name' into a git strbuf?
Please have a look at Documentation/technical/api-strbuf.txt

+		sprintf(name, "dist=%d", array[i].distance);
+		int name_len = strlen(name);
+		struct name_decoration *r = xmalloc(sizeof(*r) + name_len);
 		struct object *obj = &(array[i].commit->object);
 
-		sprintf(r->name, "dist=%d", array[i].distance);
+		memcpy(r->name, name, name_len + 1);
 		r->next = add_decoration(&name_decoration, obj, r);
 		p->item = array[i].commit;
 		p = p->next;

On 24/08/14 15:17, Arjun Sreedharan wrote:

declaration(s) after statement.

 
-		sprintf(r->name, "dist=%d", array[i].distance);
+		memcpy(r->name, name, name_len + 1);
 		r->next = add_decoration(&name_decoration, obj, r);
 		p->item = array[i].commit;
 		p = p->next;

HTH

ATB,
Ramsay Jones

find and allocate the required amount instead of
allocating extra 100 bytes

Signed-off-by: Arjun Sreedharan <redacted>
---
 bisect.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/bisect.c b/bisect.c
index d6e851d..a52631e 100644
--- a/bisect.c
+++ b/bisect.c

@@ -215,12 +215,16 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 	}
 	qsort(array, cnt, sizeof(*array), compare_commit_dist);
 	for (p = list, i = 0; i < cnt; i++) {
-		struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+		struct strbuf name = STRBUF_INIT;	
+		struct name_decoration *r;
 		struct object *obj = &(array[i].commit->object);
 
-		sprintf(r->name, "dist=%d", array[i].distance);
+		strbuf_addf(&name, "dist=%d", array[i].distance);
+		r = xmalloc(sizeof(*r) + name.len);
+		memcpy(r->name, name.buf, name.len + 1);
 		r->next = add_decoration(&name_decoration, obj, r);
 		p->item = array[i].commit;
+		strbuf_release(&name);
 		p = p->next;
 	}
 	if (p)

-- 
1.7.11.7

On Sun, Aug 24, 2014 at 8:10 AM, Stefan Beller [off-list ref] wrote:

quoted

      for (p = list, i = 0; i < cnt; i++) {
-             struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+             char name[100];

Would it make sense to convert the 'name' into a git strbuf?
Please have a look at Documentation/technical/api-strbuf.txt

Why not go one step further and format it twice, once only
to measure the necessary size to allocate, allocate and
then format into it for real? Then you do not need to print
into a temporary strbuf, copy the result and free the strbuf,
no?

BUT.

The string will always be "dist=" followed by decimal representation of
a count that fits in "int" anyway, so I actually think use of strbuf is way
overkill (and formatting it twice also is); the patch as posted should be
just fine.

Or am I missing some uses that require larger/unbounded buffer outside
the context of the patch?

On Sun, Aug 24, 2014 at 04:39:37PM -0700, Junio C Hamano wrote:

On Sun, Aug 24, 2014 at 8:10 AM, Stefan Beller [off-list ref] wrote:

quoted

quoted

      for (p = list, i = 0; i < cnt; i++) {
-             struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+             char name[100];

Would it make sense to convert the 'name' into a git strbuf?
Please have a look at Documentation/technical/api-strbuf.txt

Why not go one step further and format it twice, once only
to measure the necessary size to allocate, allocate and
then format into it for real? Then you do not need to print
into a temporary strbuf, copy the result and free the strbuf,
no?

BUT.

The string will always be "dist=" followed by decimal representation of
a count that fits in "int" anyway, so I actually think use of strbuf is way
overkill (and formatting it twice also is); the patch as posted should be
just fine.

I think you are right, and the patch is the right direction (assuming we
want to do this; I question whether there are enough elements in the
list for us to care about the size, and if there are, we are probably
better off storing the int and formatting the strings on the fly).

I wonder if there is a way we could get rid of the magic "100" here,
though. Its meaning is "enough to hold 'dist=' and any integer". But you
have to read carefully to see that this call to sprintf is not a buffer
overflow. A strbuf is one way to get rid of it, though it is awkward
because we then have to copy the result into a flex-array structure.

It would be nice if there was some way to abstract the idea of
formatting a buffer directly into a flex-array. That would involve the
double-format you mention, but we could use it in lots of places to make
the code nicer. Maybe like:

  void *fmt_flex_array(size_t base, const char *fmt, ...)
  {
          va_list ap;
	  size_t flex;
	  unsigned char *ret;

	  va_start(ap, fmt);
	  flex = vsnprintf(NULL, 0, fmt, ap);
	  va_end(ap);

	  ret = xmalloc(base + flex + 1);
	  va_start(ap, fmt);
	  /* Eek, see below */
	  vsnprintf(ret + flex, flex + 1, fmt, ap);

	  return ret;
  }

and you'd call it like:

  struct name_decoration *r = fmt_flex_array(sizeof(*r), "dist=%d", x);

Except that I don't think we are guaranteed that offsetof(mystruct,
flex_member) is equal to sizeof(mystruct). If FLEX_ARRAY is 0, it should
be, but some platforms use FLEX_ARRAY=1. So you'd have to pass in the
offset like:

  struct name_decoration *r = fmt_flex_array(sizeof(*r),
                                             offsetof(*r, name),
					     "dist=%d", x);

which is a little less nice. You could make it nicer with a macro, but
we don't assume variadic macros. <sigh>

-Peff

On Sun, Aug 24, 2014 at 07:47:24PM +0530, Arjun Sreedharan wrote:

This allocation should be name_len + 1 for the NUL-terminator, no?

It looks like add_name_decoration in log-tree already handles half of
what you are adding here. Can we just make that available globally (it
is manipulating the already-global "struct decoration name_decoration")?

I also notice that we do not set r->type at all, meaning the decoration
lookup code in log-tree will access uninitialized memory (worse, it will
use it as a pointer offset into the color list; I got a segfault when I
tried to run "git rev-list --bisect-all v1.8.0..v1.9.0").

I think we need this:

diff --git a/bisect.c b/bisect.c
index d6e851d..e2a7682 100644
--- a/bisect.c
+++ b/bisect.c

@@ -219,6 +219,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		struct object *obj = &(array[i].commit->object);
 
 		sprintf(r->name, "dist=%d", array[i].distance);
+		r->type = 0;
 		r->next = add_decoration(&name_decoration, obj, r);
 		p->item = array[i].commit;
 		p = p->next;

at a minimum.

It looks like this was a regression caused by eb3005e (commit.h: add
'type' to struct name_decoration, 2010-06-19). Which makes me wonder if
anybody actually _uses_ --bisect-all (which AFAICT is the only way to
trigger the problem), but since it's public, I guess we should keep it.

I think the sane thing here is to stop advertising name_decoration as a
global, and make all callers use add_name_decoration. That makes it
easier for callers like this one, and would have caught the regression
caused be eb3005e (the compiler would have noticed that we were not
passing a type parameter to the function).

-Peff

On Mon, Aug 25, 2014 at 3:35 PM, Jeff King [off-list ref] wrote:

On Sun, Aug 24, 2014 at 07:47:24PM +0530, Arjun Sreedharan wrote:

quoted

diff --git a/bisect.c b/bisect.c
index d6e851d..c96aab0 100644
--- a/bisect.c
+++ b/bisect.c

@@ -215,10 +215,13 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
      }
      qsort(array, cnt, sizeof(*array), compare_commit_dist);
      for (p = list, i = 0; i < cnt; i++) {
-             struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+             char name[100];
+             sprintf(name, "dist=%d", array[i].distance);
+             int name_len = strlen(name);
+             struct name_decoration *r = xmalloc(sizeof(*r) + name_len);

This allocation should be name_len + 1 for the NUL-terminator, no?

I wondered about that too, but as struct name_decoration is defined like this:

struct name_decoration {
        struct name_decoration *next;
        int type;
        char name[1];
};

the .name field of this struct already has one char, so the allocation
above should be ok.

It looks like add_name_decoration in log-tree already handles half of
what you are adding here. Can we just make that available globally (it
is manipulating the already-global "struct decoration name_decoration")?

Yeah, it looks like it should be better.

Note that add_name_decoration() does:

int nlen = strlen(name);
struct name_decoration *res = xmalloc(sizeof(struct name_decoration) + nlen);

so it also relies on the fact that .name contains one char.

Yeah if we don't use add_name_decoration() we would need that.
Thanks for noticing.

It looks like this was a regression caused by eb3005e (commit.h: add
'type' to struct name_decoration, 2010-06-19). Which makes me wonder if
anybody actually _uses_ --bisect-all (which AFAICT is the only way to
trigger the problem), but since it's public, I guess we should keep it.

Yeah, we should probably keep it.

I think the sane thing here is to stop advertising name_decoration as a
global, and make all callers use add_name_decoration. That makes it
easier for callers like this one, and would have caught the regression
caused be eb3005e (the compiler would have noticed that we were not
passing a type parameter to the function).

I agree.

Thanks,
Christian.

On Mon, Aug 25, 2014 at 04:06:52PM +0200, Christian Couder wrote:

quoted

This allocation should be name_len + 1 for the NUL-terminator, no?

I wondered about that too, but as struct name_decoration is defined like this:

struct name_decoration {
        struct name_decoration *next;
        int type;
        char name[1];
};

the .name field of this struct already has one char, so the allocation
above should be ok.

Yeah, you're right. I would argue it should just be FLEX_ARRAY for
consistency with other spots, though (in which case add_name_decoration
needs to be updated with a +1).

Running "git grep '^	char [^ ]*\[[01]]' -- '*.[ch]'" shows that this
is one of only two spots that don't use FLEX_ARRAY (and the other has a
comment explaining why not).

-Peff