[PATCH 00/12] Die commit->util, die!

[PATCH 00/12] Die commit->util, die!

[Nguyễn Thái Ngọc Duy]

There's not much to write here. It's basically a copy from 12/12:

This 'util' pointer can be used for many different purposes,
controlled in different ways. Some are not even contained in a command
code, but buried deep in common code with no clue who will use it and
how. For example, if revs.show_source is set, then it's used for
storing path name, but if you happen to call get_merge_parent() then
some 'util' may end up storing another thing.

The move to using commit-slab gives us a much better picture of how
some piece of data is associated with a commit and what for. Since
nobody uses 'util' pointer anymore, we can retire it so that nobody will
abuse it again. commit-slab will be the way forward for associating
data to a commit.

As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
architecture) which should help reduce memory usage for reachability
test a bit. This is also what commit-slab is invented for [1].

[1] 96c4f4a370 (commit: allow associating auxiliary info on-demand -
2013-04-09)

Nguyễn Thái Ngọc Duy (12):
  blame: use commit-slab for blame suspects instead of commit->util
  describe: use commit-slab for commit names instead of commit->util
  shallow.c: use commit-slab for commit depth instead of commit->util
  sequencer.c: use commit-slab to mark seen commits
  sequencer.c: use commit-slab to associate todo items to commits
  revision.c: use commit-slab for show_source
  bisect.c: use commit-slab for commit weight instead of commit->util
  name-rev: use commit-slab for rev-name instead of commit->util
  show-branch: use commit-slab for commit-name instead of commit->util
  log: use commit-slab in prepare_bases() instead of commit->util
  merge: use commit-slab in merge remote desc instead of commit->util
  commit.h: delete 'util' field in struct commit

 bisect.c              | 12 +++++++++---
 blame.c               | 42 +++++++++++++++++++++++++++++++-----------
 blame.h               |  2 ++
 builtin/blame.c       |  2 +-
 builtin/describe.c    | 16 +++++++++++++---
 builtin/fast-export.c | 14 +++++++++-----
 builtin/log.c         | 17 +++++++++++++----
 builtin/merge.c       | 25 +++++++++++++------------
 builtin/name-rev.c    | 23 ++++++++++++++++++++---
 builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
 commit.c              | 12 ++++++++++--
 commit.h              |  8 ++++++--
 log-tree.c            |  8 ++++++--
 merge-recursive.c     |  8 +++++---
 revision.c            | 17 +++++++++++++----
 revision.h            |  5 ++++-
 sequencer.c           | 24 ++++++++++++++++++------
 shallow.c             | 37 +++++++++++++++++++++++++------------
 18 files changed, 225 insertions(+), 86 deletions(-)

-- 
2.17.0.705.g3525833791

[PATCH 01/12] blame: use commit-slab for blame suspects instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 blame.c         | 42 +++++++++++++++++++++++++++++++-----------
 blame.h         |  2 ++
 builtin/blame.c |  2 +-
 3 files changed, 34 insertions(+), 12 deletions(-)

diff --git a/blame.c b/blame.c
index 78c9808bd1..18e8bd996a 100644
--- a/blame.c
+++ b/blame.c
@@ -6,6 +6,24 @@
 #include "diffcore.h"
 #include "tag.h"
 #include "blame.h"
+#include "commit-slab.h"
+
+define_commit_slab(blame_suspects, struct blame_origin *);
+static struct blame_suspects blame_suspects;
+
+struct blame_origin *get_blame_suspects(struct commit *commit)
+{
+	struct blame_origin **result;
+
+	result = blame_suspects_peek(&blame_suspects, commit);
+
+	return result ? *result : NULL;
+}
+
+static void set_blame_suspects(struct commit *commit, struct blame_origin *origin)
+{
+	*blame_suspects_at(&blame_suspects, commit) = origin;
+}
 
 void blame_origin_decref(struct blame_origin *o)
 {
@@ -15,12 +33,12 @@ void blame_origin_decref(struct blame_origin *o)
 			blame_origin_decref(o->previous);
 		free(o->file.ptr);
 		/* Should be present exactly once in commit chain */
-		for (p = o->commit->util; p; l = p, p = p->next) {
+		for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) {
 			if (p == o) {
 				if (l)
 					l->next = p->next;
 				else
-					o->commit->util = p->next;
+					set_blame_suspects(o->commit, p->next);
 				free(o);
 				return;
 			}
@@ -41,8 +59,8 @@ static struct blame_origin *make_origin(struct commit *commit, const char *path)
 	FLEX_ALLOC_STR(o, path, path);
 	o->commit = commit;
 	o->refcnt = 1;
-	o->next = commit->util;
-	commit->util = o;
+	o->next = get_blame_suspects(commit);
+	set_blame_suspects(commit, o);
 	return o;
 }
 
@@ -54,13 +72,13 @@ static struct blame_origin *get_origin(struct commit *commit, const char *path)
 {
 	struct blame_origin *o, *l;
 
-	for (o = commit->util, l = NULL; o; l = o, o = o->next) {
+	for (o = get_blame_suspects(commit), l = NULL; o; l = o, o = o->next) {
 		if (!strcmp(o->path, path)) {
 			/* bump to front */
 			if (l) {
 				l->next = o->next;
-				o->next = commit->util;
-				commit->util = o;
+				o->next = get_blame_suspects(commit);
+				set_blame_suspects(commit, o);
 			}
 			return blame_origin_incref(o);
 		}
@@ -478,7 +496,7 @@ static void queue_blames(struct blame_scoreboard *sb, struct blame_origin *porig
 		porigin->suspects = blame_merge(porigin->suspects, sorted);
 	else {
 		struct blame_origin *o;
-		for (o = porigin->commit->util; o; o = o->next) {
+		for (o = get_blame_suspects(porigin->commit); o; o = o->next) {
 			if (o->suspects) {
 				porigin->suspects = sorted;
 				return;
@@ -525,7 +543,7 @@ static struct blame_origin *find_origin(struct commit *parent,
 	const char *paths[2];
 
 	/* First check any existing origins */
-	for (porigin = parent->util; porigin; porigin = porigin->next)
+	for (porigin = get_blame_suspects(parent); porigin; porigin = porigin->next)
 		if (!strcmp(porigin->path, origin->path)) {
 			/*
 			 * The same path between origin and its parent
@@ -1550,7 +1568,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)
 
 	while (commit) {
 		struct blame_entry *ent;
-		struct blame_origin *suspect = commit->util;
+		struct blame_origin *suspect = get_blame_suspects(commit);
 
 		/* find one suspect to break down */
 		while (suspect && !suspect->suspects)
@@ -1752,6 +1770,8 @@ void setup_scoreboard(struct blame_scoreboard *sb, const char *path, struct blam
 	struct commit *final_commit = NULL;
 	enum object_type type;
 
+	init_blame_suspects(&blame_suspects);
+
 	if (sb->reverse && sb->contents_from)
 		die(_("--contents and --reverse do not blend well."));
 
@@ -1815,7 +1835,7 @@ void setup_scoreboard(struct blame_scoreboard *sb, const char *path, struct blam
 	}
 
 	if (is_null_oid(&sb->final->object.oid)) {
-		o = sb->final->util;
+		o = get_blame_suspects(sb->final);
 		sb->final_buf = xmemdupz(o->file.ptr, o->file.size);
 		sb->final_buf_size = o->file.size;
 	}
diff --git a/blame.h b/blame.h
index a6c915c277..2092f9529c 100644
--- a/blame.h
+++ b/blame.h
@@ -172,4 +172,6 @@ extern void setup_scoreboard(struct blame_scoreboard *sb, const char *path, stru
 
 extern struct blame_entry *blame_entry_prepend(struct blame_entry *head, long start, long end, struct blame_origin *o);
 
+extern struct blame_origin *get_blame_suspects(struct commit *commit);
+
 #endif /* BLAME_H */
diff --git a/builtin/blame.c b/builtin/blame.c
index db38c0b307..969572810d 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -457,7 +457,7 @@ static void output(struct blame_scoreboard *sb, int option)
 			struct commit *commit = ent->suspect->commit;
 			if (commit->object.flags & MORE_THAN_ONE_PATH)
 				continue;
-			for (suspect = commit->util; suspect; suspect = suspect->next) {
+			for (suspect = get_blame_suspects(commit); suspect; suspect = suspect->next) {
 				if (suspect->guilty && count++) {
 					commit->object.flags |= MORE_THAN_ONE_PATH;
 					break;
-- 
2.17.0.705.g3525833791

Re: [PATCH 01/12] blame: use commit-slab for blame suspects instead of commit->util

[Jeff King]

On Sat, May 12, 2018 at 10:00:17AM +0200, Nguyễn Thái Ngọc Duy wrote:

> +define_commit_slab(blame_suspects, struct blame_origin *);
> +static struct blame_suspects blame_suspects;
> +
> +struct blame_origin *get_blame_suspects(struct commit *commit)
> +{
> +	struct blame_origin **result;
> +
> +	result = blame_suspects_peek(&blame_suspects, commit);
> +
> +	return result ? *result : NULL;
> +}

Hmm. You need this helper because you want to be able to peek and get a
NULL. But that's already what _at() would return, with the only
difference that we may extend the slab just to return NULL.

I wonder how much it matters in practice. We'd generally be extending
the slab to hit every commit anyway in this case, I would think.

I suppose it doesn't actually simplify the code that much to do it that
way, though. We could get rid of this helper, but the caller would still
look like:

  for (p = *blame_suspects_at(o->commit); p; p = p->next)

which is actually slightly uglier than get_blame_suspects(), because we
have to do the pointer-dereference ourselves.

-Peff

Re: [PATCH 01/12] blame: use commit-slab for blame suspects instead of commit->util

[Duy Nguyen]

On Sat, May 12, 2018 at 11:22 AM, Jeff King <peff@peff.net> wrote:
> On Sat, May 12, 2018 at 10:00:17AM +0200, Nguyễn Thái Ngọc Duy wrote:
>
>> +define_commit_slab(blame_suspects, struct blame_origin *);
>> +static struct blame_suspects blame_suspects;
>> +
>> +struct blame_origin *get_blame_suspects(struct commit *commit)
>> +{
>> +     struct blame_origin **result;
>> +
>> +     result = blame_suspects_peek(&blame_suspects, commit);
>> +
>> +     return result ? *result : NULL;
>> +}
>
> Hmm. You need this helper because you want to be able to peek and get a
> NULL. But that's already what _at() would return, with the only
> difference that we may extend the slab just to return NULL.
>
> I wonder how much it matters in practice. We'd generally be extending
> the slab to hit every commit anyway in this case, I would think.

I don't know much about blame so I stay very conservative ;-) If it's
safe to just do _at() here, I'll update this patch.

> I suppose it doesn't actually simplify the code that much to do it that
> way, though. We could get rid of this helper, but the caller would still
> look like:
>
>   for (p = *blame_suspects_at(o->commit); p; p = p->next)
>
> which is actually slightly uglier than get_blame_suspects(), because we
> have to do the pointer-dereference ourselves.

And the caller would need to include commit-slab.h too. I added
get_blame_suspects() because I wanted to avoid that.
-- 
Duy

[PATCH 02/12] describe: use commit-slab for commit names instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/describe.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index b5afc45846..1b6ca42553 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -15,9 +15,12 @@
 #include "run-command.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "commit-slab.h"
 
 #define MAX_TAGS	(FLAG_BITS - 1)
 
+define_commit_slab(commit_names, struct commit_name *);
+
 static const char * const describe_usage[] = {
 	N_("git describe [<options>] [<commit-ish>...]"),
 	N_("git describe [<options>] --dirty"),
@@ -37,6 +40,7 @@ static struct string_list patterns = STRING_LIST_INIT_NODUP;
 static struct string_list exclude_patterns = STRING_LIST_INIT_NODUP;
 static int always;
 static const char *suffix, *dirty, *broken;
+static struct commit_names commit_names;
 
 /* diff-index command arguments to check if working tree is dirty. */
 static const char *diff_index_args[] = {
@@ -321,11 +325,14 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	if (!have_util) {
 		struct hashmap_iter iter;
 		struct commit *c;
-		struct commit_name *n = hashmap_iter_first(&names, &iter);
+		struct commit_name *n;
+
+		init_commit_names(&commit_names);
+		n = hashmap_iter_first(&names, &iter);
 		for (; n; n = hashmap_iter_next(&iter)) {
 			c = lookup_commit_reference_gently(&n->peeled, 1);
 			if (c)
-				c->util = n;
+				*commit_names_at(&commit_names, c) = n;
 		}
 		have_util = 1;
 	}
@@ -336,8 +343,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	while (list) {
 		struct commit *c = pop_commit(&list);
 		struct commit_list *parents = c->parents;
+		struct commit_name **slot;
+
 		seen_commits++;
-		n = c->util;
+		slot = commit_names_peek(&commit_names, c);
+		n = slot ? *slot : NULL;
 		if (n) {
 			if (!tags && !all && n->prio < 2) {
 				unannotated_cnt++;
-- 
2.17.0.705.g3525833791

[PATCH 03/12] shallow.c: use commit-slab for commit depth instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

While at there, plug a leak for keeping track of depth in this code.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 shallow.c | 37 +++++++++++++++++++++++++------------
 1 file changed, 25 insertions(+), 12 deletions(-)

diff --git a/shallow.c b/shallow.c
index df4d44ea7a..6ea411b0d2 100644
--- a/shallow.c
+++ b/shallow.c
@@ -12,6 +12,7 @@
 #include "commit-slab.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "commit-slab.h"
 
 static int is_shallow = -1;
 static struct stat_validity shallow_stat;
@@ -74,6 +75,7 @@ int is_repository_shallow(void)
 	return is_shallow;
 }
 
+define_commit_slab(commit_depth, int *);
 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		int shallow_flag, int not_shallow_flag)
 {
@@ -82,25 +84,29 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 	struct object_array stack = OBJECT_ARRAY_INIT;
 	struct commit *commit = NULL;
 	struct commit_graft *graft;
+	struct commit_depth depths;
 
+	init_commit_depth(&depths);
 	while (commit || i < heads->nr || stack.nr) {
 		struct commit_list *p;
 		if (!commit) {
 			if (i < heads->nr) {
+				int **depth_slot;
 				commit = (struct commit *)
 					deref_tag(heads->objects[i++].item, NULL, 0);
 				if (!commit || commit->object.type != OBJ_COMMIT) {
 					commit = NULL;
 					continue;
 				}
-				if (!commit->util)
-					commit->util = xmalloc(sizeof(int));
-				*(int *)commit->util = 0;
+				depth_slot = commit_depth_at(&depths, commit);
+				if (!*depth_slot)
+					*depth_slot = xmalloc(sizeof(int));
+				**depth_slot = 0;
 				cur_depth = 0;
 			} else {
 				commit = (struct commit *)
 					object_array_pop(&stack);
-				cur_depth = *(int *)commit->util;
+				cur_depth = **commit_depth_peek(&depths, commit);
 			}
 		}
 		parse_commit_or_die(commit);
@@ -116,25 +122,32 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		}
 		commit->object.flags |= not_shallow_flag;
 		for (p = commit->parents, commit = NULL; p; p = p->next) {
-			if (!p->item->util) {
-				int *pointer = xmalloc(sizeof(int));
-				p->item->util = pointer;
-				*pointer =  cur_depth;
+			int **depth_slot = commit_depth_at(&depths, p->item);
+			if (!*depth_slot) {
+				*depth_slot = xmalloc(sizeof(int));
+				**depth_slot = cur_depth;
 			} else {
-				int *pointer = p->item->util;
-				if (cur_depth >= *pointer)
+				if (cur_depth >= **depth_slot)
 					continue;
-				*pointer = cur_depth;
+				**depth_slot = cur_depth;
 			}
 			if (p->next)
 				add_object_array(&p->item->object,
 						NULL, &stack);
 			else {
 				commit = p->item;
-				cur_depth = *(int *)commit->util;
+				depth_slot = commit_depth_peek(&depths, commit);
+				cur_depth = **depth_slot;
 			}
 		}
 	}
+	for (i = 0; i < depths.slab_count; i++) {
+		int j;
+
+		for (j = 0; j < depths.slab_size; j++)
+			free(depths.slab[i][j]);
+	}
+	clear_commit_depth(&depths);
 
 	return result;
 }
-- 
2.17.0.705.g3525833791

Re: [PATCH 03/12] shallow.c: use commit-slab for commit depth instead of commit->util

[Jeff King]

On Sat, May 12, 2018 at 10:00:19AM +0200, Nguyễn Thái Ngọc Duy wrote:

> @@ -82,25 +84,29 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
>  	struct object_array stack = OBJECT_ARRAY_INIT;
>  	struct commit *commit = NULL;
>  	struct commit_graft *graft;
> +	struct commit_depth depths;
>  
> +	init_commit_depth(&depths);
>  	while (commit || i < heads->nr || stack.nr) {
>  		struct commit_list *p;
>  		if (!commit) {
>  			if (i < heads->nr) {
> +				int **depth_slot;
>  				commit = (struct commit *)
>  					deref_tag(heads->objects[i++].item, NULL, 0);
>  				if (!commit || commit->object.type != OBJ_COMMIT) {
>  					commit = NULL;
>  					continue;
>  				}
> -				if (!commit->util)
> -					commit->util = xmalloc(sizeof(int));
> -				*(int *)commit->util = 0;
> +				depth_slot = commit_depth_at(&depths, commit);
> +				if (!*depth_slot)
> +					*depth_slot = xmalloc(sizeof(int));
> +				**depth_slot = 0;

It looks like we could save ourselves an extra layer of indirection (and
tiny heap allocations) by just storing an "int" directly in the slab.
Do we ever use the NULL as a sentinel value?

Here we just allocate it if not set. Let's see if we can find some
others...

> @@ -116,25 +122,32 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
>  		}
>  		commit->object.flags |= not_shallow_flag;
>  		for (p = commit->parents, commit = NULL; p; p = p->next) {
> -			if (!p->item->util) {
> -				int *pointer = xmalloc(sizeof(int));
> -				p->item->util = pointer;
> -				*pointer =  cur_depth;
> +			int **depth_slot = commit_depth_at(&depths, p->item);
> +			if (!*depth_slot) {
> +				*depth_slot = xmalloc(sizeof(int));
> +				**depth_slot = cur_depth;
>  			} else {
> -				int *pointer = p->item->util;
> -				if (cur_depth >= *pointer)
> +				if (cur_depth >= **depth_slot)
>  					continue;
> -				*pointer = cur_depth;
> +				**depth_slot = cur_depth;
>  			}

Here we malloc again if it's not set. But we do behave slightly
differently when we see NULL, in that we do not bother to even compare
against cur_depth. So if we were to directly store ints, we'd see "0" as
the sentinel depth here, which would not match our "cur_depth >=
depth_slot" check.

So no, it wouldn't work to directly store depths with the code as
written.  I'm not sure if the depth can ever be 0. If not, then it would
be a suitable sentinel as:

  int *slot = commit_depth_at(&depths, p->item);
  if (!*slot || cur_depth < *slot)
	*slot = cur_depth;

But somebody would have to dig into the possible values of cur_depth
there (which would make sense to do as a separate patch anyway, since
the point of this is to be a direct conversion).

-Peff

Re: [PATCH 03/12] shallow.c: use commit-slab for commit depth instead of commit->util

[Jeff King]

On Sat, May 12, 2018 at 05:07:48AM -0400, Jeff King wrote:

> So no, it wouldn't work to directly store depths with the code as
> written.  I'm not sure if the depth can ever be 0. If not, then it would
> be a suitable sentinel as:
> 
>   int *slot = commit_depth_at(&depths, p->item);
>   if (!*slot || cur_depth < *slot)
> 	*slot = cur_depth;
> 
> But somebody would have to dig into the possible values of cur_depth
> there (which would make sense to do as a separate patch anyway, since
> the point of this is to be a direct conversion).

By the way, one other approach if xcalloc() doesn't produce a good
sentinel is to use a data type that does. ;) E.g., something like this
should work:

  struct depth {
	unsigned valid:1;
	int value;
  };
  define_commit_slab(commit_depth, struct depth);

  ...

  struct depth *slot = commit_depth_at(&depths, p->item);
  if (!slot->valid || cur_depth < slot->value) {
	slot->value = cur_depth;
	slot->valid = 1;
  }

That wastes an extra 4 bytes per slot over storing an int directly, but
it's the same as storing an 8-byte pointer, plus you avoid the storage
and runtime overhead of malloc.

I actually wonder if we could wrap commit_slab with a variant that
stores the sentinel data itself, to make this pattern easier. I.e.,
something like:

  #define define_commit_slab_sentinel(name, type) \
	struct name##_value { \
		unsigned valid:1; \
		type value; \
	}; \
	define_commit_slab(name, struct name##_value)

and some matching "peek" and "at" functions to manipulate value
directly.

I think the end result would be nicer, but it's turning into a little
bit of a rabbit hole. So I don't mind going with your direct conversion
here for now.

-Peff

Re: [PATCH 03/12] shallow.c: use commit-slab for commit depth instead of commit->util

[Duy Nguyen]

On Sat, May 12, 2018 at 11:18 AM, Jeff King <peff@peff.net> wrote:
> On Sat, May 12, 2018 at 05:07:48AM -0400, Jeff King wrote:
>
>> So no, it wouldn't work to directly store depths with the code as
>> written.  I'm not sure if the depth can ever be 0. If not, then it would
>> be a suitable sentinel as:
>>
>>   int *slot = commit_depth_at(&depths, p->item);
>>   if (!*slot || cur_depth < *slot)
>>       *slot = cur_depth;
>>
>> But somebody would have to dig into the possible values of cur_depth
>> there (which would make sense to do as a separate patch anyway, since
>> the point of this is to be a direct conversion).
>
> By the way, one other approach if xcalloc() doesn't produce a good
> sentinel is to use a data type that does. ;) E.g., something like this
> should work:
>
>   struct depth {
>         unsigned valid:1;
>         int value;
>   };
>   define_commit_slab(commit_depth, struct depth);
>
>   ...
>
>   struct depth *slot = commit_depth_at(&depths, p->item);
>   if (!slot->valid || cur_depth < slot->value) {
>         slot->value = cur_depth;
>         slot->valid = 1;
>   }
>
> That wastes an extra 4 bytes per slot over storing an int directly, but
> it's the same as storing an 8-byte pointer, plus you avoid the storage
> and runtime overhead of malloc.

Or we could have a way to let the user decide initial values. If the
initial value here is -1 (which can't possibly be used in the current
code), it could be the sentinel value.

Did you notice the for loop in the end to free "int *"? I don't like
peeking inside a slab that way and would prefer passing a "free"
function pointer to clear_commit_depth(), or just assign a "free"
function to some new field in struct commit_depth and
clear_commit_depth() will call it. If we have a new field for "free"
callback in the struct, it makes sense to have an "init" callback to
do extra initialization on top of xcalloc.

> I actually wonder if we could wrap commit_slab with a variant that
> stores the sentinel data itself, to make this pattern easier. I.e.,
> something like:
>
>   #define define_commit_slab_sentinel(name, type) \
>         struct name##_value { \
>                 unsigned valid:1; \
>                 type value; \
>         }; \
>         define_commit_slab(name, struct name##_value)
>
> and some matching "peek" and "at" functions to manipulate value
> directly.

If you keep this valid bit in a separate slab, you can pack these bits
very tight and not worry about wasting memory. Lookup in commit-slab
is cheap enough that doing double lookups (one for valid field, one
for value) is not a problem, I think.

> I think the end result would be nicer, but it's turning into a little
> bit of a rabbit hole. So I don't mind going with your direct conversion
> here for now.

Yeah I think I will stick with a faithful conversion for now. The
conversion shows room for improvement which could be the next
microproject (I thought of adding this removing 'util' task as a 2019
microproject but it was too tricky for newcomers to do).
-- 
Duy

Re: [PATCH 03/12] shallow.c: use commit-slab for commit depth instead of commit->util

[Jeff King]

On Sat, May 12, 2018 at 02:09:18PM +0200, Duy Nguyen wrote:

> > That wastes an extra 4 bytes per slot over storing an int directly, but
> > it's the same as storing an 8-byte pointer, plus you avoid the storage
> > and runtime overhead of malloc.
> 
> Or we could have a way to let the user decide initial values. If the
> initial value here is -1 (which can't possibly be used in the current
> code), it could be the sentinel value.

That's actually a little tricky. Right now the sentinels are assigned by
xcalloc(), so they're all-bits zero. We _could_ walk any newly allocated
slab and assign a value to each element, but I'd worry that is wasteful
for cases where might only use a small part of the slab (and my
assumption is that the OS can give us zero'd pages pretty cheaply, and
maybe even avoid allocating a page until we touch them, but I don't know
how true that is).

> Did you notice the for loop in the end to free "int *"? I don't like
> peeking inside a slab that way and would prefer passing a "free"
> function pointer to clear_commit_depth(), or just assign a "free"
> function to some new field in struct commit_depth and
> clear_commit_depth() will call it. If we have a new field for "free"
> callback in the struct, it makes sense to have an "init" callback to
> do extra initialization on top of xcalloc.

You might find that a free() is tricky with the type system. This is all
implemented with macros, so you'd end up calling free() on an int (even
if it's a function that nobody ever calls). I suppose the value could be
cast to void to shut up the compiler, but then that function is like a
ticking time bomb. ;)

So I guess you'd need a variant of define_commit_slab() that defines the
clear function and one that doesn't.

> > I actually wonder if we could wrap commit_slab with a variant that
> > stores the sentinel data itself, to make this pattern easier. I.e.,
> > something like:
> >
> >   #define define_commit_slab_sentinel(name, type) \
> >         struct name##_value { \
> >                 unsigned valid:1; \
> >                 type value; \
> >         }; \
> >         define_commit_slab(name, struct name##_value)
> >
> > and some matching "peek" and "at" functions to manipulate value
> > directly.
> 
> If you keep this valid bit in a separate slab, you can pack these bits
> very tight and not worry about wasting memory. Lookup in commit-slab
> is cheap enough that doing double lookups (one for valid field, one
> for value) is not a problem, I think.

True, though your cache behavior gets worse if your have two separate
arrays. I'm not sure pinching bytes matters all that much. linux.git has
~600k commits, so even there a few bytes each is not so bad (although
again, we get into cache issues).

> Yeah I think I will stick with a faithful conversion for now. The
> conversion shows room for improvement which could be the next
> microproject (I thought of adding this removing 'util' task as a 2019
> microproject but it was too tricky for newcomers to do).

Makes sense to me.

-Peff

Re: [PATCH 03/12] shallow.c: use commit-slab for commit depth instead of commit->util

[Duy Nguyen]

On Sat, May 12, 2018 at 11:07 AM, Jeff King <peff@peff.net> wrote:
> On Sat, May 12, 2018 at 10:00:19AM +0200, Nguyễn Thái Ngọc Duy wrote:
>
>> @@ -82,25 +84,29 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
>>       struct object_array stack = OBJECT_ARRAY_INIT;
>>       struct commit *commit = NULL;
>>       struct commit_graft *graft;
>> +     struct commit_depth depths;
>>
>> +     init_commit_depth(&depths);
>>       while (commit || i < heads->nr || stack.nr) {
>>               struct commit_list *p;
>>               if (!commit) {
>>                       if (i < heads->nr) {
>> +                             int **depth_slot;
>>                               commit = (struct commit *)
>>                                       deref_tag(heads->objects[i++].item, NULL, 0);
>>                               if (!commit || commit->object.type != OBJ_COMMIT) {
>>                                       commit = NULL;
>>                                       continue;
>>                               }
>> -                             if (!commit->util)
>> -                                     commit->util = xmalloc(sizeof(int));
>> -                             *(int *)commit->util = 0;
>> +                             depth_slot = commit_depth_at(&depths, commit);
>> +                             if (!*depth_slot)
>> +                                     *depth_slot = xmalloc(sizeof(int));
>> +                             **depth_slot = 0;
>
> It looks like we could save ourselves an extra layer of indirection (and
> tiny heap allocations) by just storing an "int" directly in the slab.
> Do we ever use the NULL as a sentinel value?
>
> Here we just allocate it if not set. Let's see if we can find some
> others...
>
>> @@ -116,25 +122,32 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
>>               }
>>               commit->object.flags |= not_shallow_flag;
>>               for (p = commit->parents, commit = NULL; p; p = p->next) {
>> -                     if (!p->item->util) {
>> -                             int *pointer = xmalloc(sizeof(int));
>> -                             p->item->util = pointer;
>> -                             *pointer =  cur_depth;
>> +                     int **depth_slot = commit_depth_at(&depths, p->item);
>> +                     if (!*depth_slot) {
>> +                             *depth_slot = xmalloc(sizeof(int));
>> +                             **depth_slot = cur_depth;
>>                       } else {
>> -                             int *pointer = p->item->util;
>> -                             if (cur_depth >= *pointer)
>> +                             if (cur_depth >= **depth_slot)
>>                                       continue;
>> -                             *pointer = cur_depth;
>> +                             **depth_slot = cur_depth;
>>                       }
>
> Here we malloc again if it's not set. But we do behave slightly
> differently when we see NULL, in that we do not bother to even compare
> against cur_depth. So if we were to directly store ints, we'd see "0" as
> the sentinel depth here, which would not match our "cur_depth >=
> depth_slot" check.
>
> So no, it wouldn't work to directly store depths with the code as
> written.  I'm not sure if the depth can ever be 0. If not, then it would
> be a suitable sentinel as:
>
>   int *slot = commit_depth_at(&depths, p->item);
>   if (!*slot || cur_depth < *slot)
>         *slot = cur_depth;
>
> But somebody would have to dig into the possible values of cur_depth
> there (which would make sense to do as a separate patch anyway, since
> the point of this is to be a direct conversion).

I actually tried that first, going with storing int directly in the
slab instead of int*. And some shallow tests failed so I didn't bother
(the goal was to get rid of 'util' pointer, not to optimize more)
-- 
Duy

[PATCH 04/12] sequencer.c: use commit-slab to mark seen commits

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 sequencer.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index 4ce5120e77..5993ffe060 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -23,6 +23,7 @@
 #include "hashmap.h"
 #include "notes-utils.h"
 #include "sigchain.h"
+#include "commit-slab.h"
 
 #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
 
@@ -3160,6 +3161,7 @@ static enum check_level get_missing_commit_check_level(void)
 	return CHECK_IGNORE;
 }
 
+define_commit_slab(commit_seen, int);
 /*
  * Check if the user dropped some commits by mistake
  * Behaviour determined by rebase.missingCommitsCheck.
@@ -3173,6 +3175,9 @@ int check_todo_list(void)
 	struct todo_list todo_list = TODO_LIST_INIT;
 	struct strbuf missing = STRBUF_INIT;
 	int advise_to_edit_todo = 0, res = 0, i;
+	struct commit_seen commit_seen;
+
+	init_commit_seen(&commit_seen);
 
 	strbuf_addstr(&todo_file, rebase_path_todo());
 	if (strbuf_read_file_or_whine(&todo_list.buf, todo_file.buf) < 0) {
@@ -3189,7 +3194,7 @@ int check_todo_list(void)
 	for (i = 0; i < todo_list.nr; i++) {
 		struct commit *commit = todo_list.items[i].commit;
 		if (commit)
-			commit->util = (void *)1;
+			*commit_seen_at(&commit_seen, commit) = 1;
 	}
 
 	todo_list_release(&todo_list);
@@ -3205,11 +3210,11 @@ int check_todo_list(void)
 	for (i = todo_list.nr - 1; i >= 0; i--) {
 		struct todo_item *item = todo_list.items + i;
 		struct commit *commit = item->commit;
-		if (commit && !commit->util) {
+		if (commit && !*commit_seen_at(&commit_seen, commit)) {
 			strbuf_addf(&missing, " - %s %.*s\n",
 				    short_commit_name(commit),
 				    item->arg_len, item->arg);
-			commit->util = (void *)1;
+			*commit_seen_at(&commit_seen, commit) = 1;
 		}
 	}
 
@@ -3235,6 +3240,7 @@ int check_todo_list(void)
 		"The possible behaviours are: ignore, warn, error.\n\n"));
 
 leave_check:
+	clear_commit_seen(&commit_seen);
 	strbuf_release(&todo_file);
 	todo_list_release(&todo_list);
 
-- 
2.17.0.705.g3525833791

Re: [PATCH 04/12] sequencer.c: use commit-slab to mark seen commits

[Jeff King]

On Sat, May 12, 2018 at 10:00:20AM +0200, Nguyễn Thái Ngọc Duy wrote:

> +define_commit_slab(commit_seen, int);

Yay, this one is nice and simple. :) This is what I had hoped for all
along with the slab concept.

-Peff

Re: [PATCH 04/12] sequencer.c: use commit-slab to mark seen commits

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Sat, May 12, 2018 at 10:00:20AM +0200, Nguyễn Thái Ngọc Duy wrote:
>
>> +define_commit_slab(commit_seen, int);
>
> Yay, this one is nice and simple. :) This is what I had hoped for all
> along with the slab concept.
>
> -Peff

Does it need to use a full int, not just a byte per commit, though?

Re: [PATCH 04/12] sequencer.c: use commit-slab to mark seen commits

[Duy Nguyen]

On Sat, May 12, 2018 at 3:43 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Jeff King <peff@peff.net> writes:
>
>> On Sat, May 12, 2018 at 10:00:20AM +0200, Nguyễn Thái Ngọc Duy wrote:
>>
>>> +define_commit_slab(commit_seen, int);
>>
>> Yay, this one is nice and simple. :) This is what I had hoped for all
>> along with the slab concept.
>>
>> -Peff
>
> Does it need to use a full int, not just a byte per commit, though?

True. Is it time to introduce 'bool' type? I did not want to put the
'char' type up there (but now that I think about it I could have put
uint8_t too).
-- 
Duy

[PATCH 05/12] sequencer.c: use commit-slab to associate todo items to commits

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 sequencer.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index 5993ffe060..1a0a6916e3 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -3362,6 +3362,8 @@ static int subject2item_cmp(const void *fndata,
 	return key ? strcmp(a->subject, key) : strcmp(a->subject, b->subject);
 }
 
+define_commit_slab(commit_todo_item, struct todo_item *);
+
 /*
  * Rearrange the todo list that has both "pick commit-id msg" and "pick
  * commit-id fixup!/squash! msg" in it so that the latter is put immediately
@@ -3378,6 +3380,7 @@ int rearrange_squash(void)
 	struct hashmap subject2item;
 	int res = 0, rearranged = 0, *next, *tail, i;
 	char **subjects;
+	struct commit_todo_item commit_todo;
 
 	if (strbuf_read_file_or_whine(&todo_list.buf, todo_file) < 0)
 		return -1;
@@ -3386,6 +3389,7 @@ int rearrange_squash(void)
 		return -1;
 	}
 
+	init_commit_todo_item(&commit_todo);
 	/*
 	 * The hashmap maps onelines to the respective todo list index.
 	 *
@@ -3416,10 +3420,11 @@ int rearrange_squash(void)
 
 		if (is_fixup(item->command)) {
 			todo_list_release(&todo_list);
+			clear_commit_todo_item(&commit_todo);
 			return error(_("the script was already rearranged."));
 		}
 
-		item->commit->util = item;
+		*commit_todo_item_at(&commit_todo, item->commit) = item;
 
 		parse_commit(item->commit);
 		commit_buffer = get_commit_buffer(item->commit, NULL);
@@ -3446,9 +3451,9 @@ int rearrange_squash(void)
 			else if (!strchr(p, ' ') &&
 				 (commit2 =
 				  lookup_commit_reference_by_name(p)) &&
-				 commit2->util)
+				 *commit_todo_item_at(&commit_todo, commit2))
 				/* found by commit name */
-				i2 = (struct todo_item *)commit2->util
+				i2 = *commit_todo_item_peek(&commit_todo, commit2)
 					- todo_list.items;
 			else {
 				/* copy can be a prefix of the commit subject */
@@ -3527,5 +3532,6 @@ int rearrange_squash(void)
 	hashmap_free(&subject2item, 1);
 	todo_list_release(&todo_list);
 
+	clear_commit_todo_item(&commit_todo);
 	return res;
 }
-- 
2.17.0.705.g3525833791

Re: [PATCH 05/12] sequencer.c: use commit-slab to associate todo items to commits

[Jeff King]

On Sat, May 12, 2018 at 10:00:21AM +0200, Nguyễn Thái Ngọc Duy wrote:

> @@ -3446,9 +3451,9 @@ int rearrange_squash(void)
>  			else if (!strchr(p, ' ') &&
>  				 (commit2 =
>  				  lookup_commit_reference_by_name(p)) &&
> -				 commit2->util)
> +				 *commit_todo_item_at(&commit_todo, commit2))
>  				/* found by commit name */
> -				i2 = (struct todo_item *)commit2->util
> +				i2 = *commit_todo_item_peek(&commit_todo, commit2)
>  					- todo_list.items;

Directly dereferencing _peek() is an anti-pattern, since it may return
NULL. We know it's OK here because the earlier call to _at() would have
extended the slab. But it probably makes sense to use _at() in both
places then (or even to use _peek() for the earlier one if you want to
avoid extending, but as I said in the other message, I kind of
suspect most of these cases end up allocating slab space for most of the
commits anyway).

-Peff

[PATCH 06/12] revision.c: use commit-slab for show_source

[Nguyễn Thái Ngọc Duy]

Instead of relying on commit->util to store the source string, let the
user provide a commit-slab to store the source strings in.

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/fast-export.c | 14 +++++++++-----
 builtin/log.c         |  7 +++++--
 log-tree.c            |  8 ++++++--
 revision.c            | 17 +++++++++++++----
 revision.h            |  5 ++++-
 5 files changed, 37 insertions(+), 14 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 530df12f05..092e29583e 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -21,6 +21,7 @@
 #include "quote.h"
 #include "remote.h"
 #include "blob.h"
+#include "commit-slab.h"
 
 static const char *fast_export_usage[] = {
 	N_("git fast-export [rev-list-opts]"),
@@ -38,6 +39,7 @@ static struct string_list extra_refs = STRING_LIST_INIT_NODUP;
 static struct refspec *refspecs;
 static int refspecs_nr;
 static int anonymize;
+static struct source_slab source_slab;
 
 static int parse_opt_signed_tag_mode(const struct option *opt,
 				     const char *arg, int unset)
@@ -590,7 +592,7 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,
 		if (!S_ISGITLINK(diff_queued_diff.queue[i]->two->mode))
 			export_blob(&diff_queued_diff.queue[i]->two->oid);
 
-	refname = commit->util;
+	refname = *source_slab_peek(&source_slab, commit);
 	if (anonymize) {
 		refname = anonymize_refname(refname);
 		anonymize_ident_line(&committer, &committer_end);
@@ -862,10 +864,11 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)
 		 * This ref will not be updated through a commit, lets make
 		 * sure it gets properly updated eventually.
 		 */
-		if (commit->util || commit->object.flags & SHOWN)
+		if (*source_slab_at(&source_slab, commit) ||
+		    commit->object.flags & SHOWN)
 			string_list_append(&extra_refs, full_name)->util = commit;
-		if (!commit->util)
-			commit->util = full_name;
+		if (!*source_slab_at(&source_slab, commit))
+			*source_slab_at(&source_slab, commit) = full_name;
 	}
 }
 
@@ -1029,8 +1032,9 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
 	git_config(git_default_config, NULL);
 
 	init_revisions(&revs, prefix);
+	init_source_slab(&source_slab);
 	revs.topo_order = 1;
-	revs.show_source = 1;
+	revs.source_slab = &source_slab;
 	revs.rewrite_parents = 1;
 	argc = parse_options(argc, argv, prefix, options, fast_export_usage,
 			PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN);
diff --git a/builtin/log.c b/builtin/log.c
index 71f68a3e4f..0d199ebd5d 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -148,6 +148,7 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	static struct string_list decorate_refs_include = STRING_LIST_INIT_NODUP;
 	struct decoration_filter decoration_filter = {&decorate_refs_include,
 						      &decorate_refs_exclude};
+	static struct source_slab source_slab;
 
 	const struct option builtin_log_options[] = {
 		OPT__QUIET(&quiet, N_("suppress diff output")),
@@ -194,8 +195,10 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	    rev->diffopt.filter || rev->diffopt.flags.follow_renames)
 		rev->always_show_header = 0;
 
-	if (source)
-		rev->show_source = 1;
+	if (source) {
+		init_source_slab(&source_slab);
+		rev->source_slab = &source_slab;
+	}
 
 	if (mailmap) {
 		rev->mailmap = xcalloc(1, sizeof(struct string_list));
diff --git a/log-tree.c b/log-tree.c
index d1c0bedf24..d36a945fc4 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -295,8 +295,12 @@ void show_decorations(struct rev_info *opt, struct commit *commit)
 {
 	struct strbuf sb = STRBUF_INIT;
 
-	if (opt->show_source && commit->util)
-		fprintf(opt->diffopt.file, "\t%s", (char *) commit->util);
+	if (opt->source_slab) {
+		char **slot = source_slab_peek(opt->source_slab, commit);
+
+		if (slot && *slot)
+			fprintf(opt->diffopt.file, "\t%s", *slot);
+	}
 	if (!opt->show_decorations)
 		return;
 	format_decorations(&sb, commit, opt->diffopt.use_color);
diff --git a/revision.c b/revision.c
index 1cff11833e..41b56f789d 100644
--- a/revision.c
+++ b/revision.c
@@ -255,14 +255,19 @@ static struct commit *handle_commit(struct rev_info *revs,
 	 */
 	if (object->type == OBJ_COMMIT) {
 		struct commit *commit = (struct commit *)object;
+
 		if (parse_commit(commit) < 0)
 			die("unable to parse commit %s", name);
 		if (flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
 			revs->limited = 1;
 		}
-		if (revs->show_source && !commit->util)
-			commit->util = xstrdup(name);
+		if (revs->source_slab) {
+			char **slot = source_slab_at(revs->source_slab, commit);
+
+			if (!*slot)
+				*slot = xstrdup(name);
+		}
 		return commit;
 	}
 
@@ -814,8 +819,12 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			}
 			return -1;
 		}
-		if (revs->show_source && !p->util)
-			p->util = commit->util;
+		if (revs->source_slab) {
+			char **slot = source_slab_at(revs->source_slab, p);
+
+			if (!*slot)
+				*slot = *source_slab_at(revs->source_slab, commit);
+		}
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
 			p->object.flags |= SEEN;
diff --git a/revision.h b/revision.h
index b8c47b98e2..72404e2599 100644
--- a/revision.h
+++ b/revision.h
@@ -6,6 +6,7 @@
 #include "notes.h"
 #include "pretty.h"
 #include "diff.h"
+#include "commit-slab.h"
 
 /* Remember to update object flag allocation in object.h */
 #define SEEN		(1u<<0)
@@ -29,6 +30,7 @@ struct rev_info;
 struct log_info;
 struct string_list;
 struct saved_parents;
+define_commit_slab(source_slab, char *);
 
 struct rev_cmdline_info {
 	unsigned int nr;
@@ -111,7 +113,6 @@ struct rev_info {
 			right_only:1,
 			rewrite_parents:1,
 			print_parents:1,
-			show_source:1,
 			show_decorations:1,
 			reverse:1,
 			reverse_output_stage:1,
@@ -224,6 +225,8 @@ struct rev_info {
 
 	struct commit_list *previous_parents;
 	const char *break_bar;
+
+	struct source_slab *source_slab;
 };
 
 extern int ref_excluded(struct string_list *, const char *path);
-- 
2.17.0.705.g3525833791

Re: [PATCH 06/12] revision.c: use commit-slab for show_source

[Jeff King]

On Sat, May 12, 2018 at 10:00:22AM +0200, Nguyễn Thái Ngọc Duy wrote:

> diff --git a/revision.h b/revision.h
> index b8c47b98e2..72404e2599 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -6,6 +6,7 @@
>  #include "notes.h"
>  #include "pretty.h"
>  #include "diff.h"
> +#include "commit-slab.h"
>  
>  /* Remember to update object flag allocation in object.h */
>  #define SEEN		(1u<<0)
> @@ -29,6 +30,7 @@ struct rev_info;
>  struct log_info;
>  struct string_list;
>  struct saved_parents;
> +define_commit_slab(source_slab, char *);

Since this one is a global, can we give it a name that ties it to the
revision machinery? Like "revision_source_slab" or something?

I wonder if we can even drop the "slab" to make the name shorter (e.g.,
"revision_sources" or something).

It's a little ugly that everybody who includes revision.h gets the full
set of static functions defined. I wonder if we should have separate
declare/define macros to let these exist as real functions. Maybe it
doesn't really matter, though.

-Peff

Re: [PATCH 06/12] revision.c: use commit-slab for show_source

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Sat, May 12, 2018 at 10:00:22AM +0200, Nguyễn Thái Ngọc Duy wrote:
>
>> diff --git a/revision.h b/revision.h
>> index b8c47b98e2..72404e2599 100644
>> --- a/revision.h
>> +++ b/revision.h
>> @@ -6,6 +6,7 @@
>>  #include "notes.h"
>>  #include "pretty.h"
>>  #include "diff.h"
>> +#include "commit-slab.h"
>>  
>>  /* Remember to update object flag allocation in object.h */
>>  #define SEEN		(1u<<0)
>> @@ -29,6 +30,7 @@ struct rev_info;
>>  struct log_info;
>>  struct string_list;
>>  struct saved_parents;
>> +define_commit_slab(source_slab, char *);
>
> Since this one is a global, can we give it a name that ties it to the
> revision machinery? Like "revision_source_slab" or something?

Should this one be global in the first place?  Can we tie it to say
"struct rev_info" or something?  I'd somehow anticipate a far future
where object flag bits used for traversal book-keeping would be moved
out of the objects themselves and multiple simultanous traversal
becomes reality.

Not limited to this particular one, but we'd need to think how the
commit_slab mechanism should interact with the_repository idea
Stefan has been having fun with.  If the object pool is maintained
per in-core repository object, presumably we'd have more than one
in-core instances of the same commit object if we have more than one
repository objects, and decorating one with a slab data may not want
to decorate the other one at the same time.

Re: [PATCH 06/12] revision.c: use commit-slab for show_source

[Duy Nguyen]

On Sat, May 12, 2018 at 3:58 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Jeff King <peff@peff.net> writes:
>
>> On Sat, May 12, 2018 at 10:00:22AM +0200, Nguyễn Thái Ngọc Duy wrote:
>>
>>> diff --git a/revision.h b/revision.h
>>> index b8c47b98e2..72404e2599 100644
>>> --- a/revision.h
>>> +++ b/revision.h
>>> @@ -6,6 +6,7 @@
>>>  #include "notes.h"
>>>  #include "pretty.h"
>>>  #include "diff.h"
>>> +#include "commit-slab.h"
>>>
>>>  /* Remember to update object flag allocation in object.h */
>>>  #define SEEN                (1u<<0)
>>> @@ -29,6 +30,7 @@ struct rev_info;
>>>  struct log_info;
>>>  struct string_list;
>>>  struct saved_parents;
>>> +define_commit_slab(source_slab, char *);
>>
>> Since this one is a global, can we give it a name that ties it to the
>> revision machinery? Like "revision_source_slab" or something?
>
> Should this one be global in the first place?  Can we tie it to say
> "struct rev_info" or something?  I'd somehow anticipate a far future
> where object flag bits used for traversal book-keeping would be moved
> out of the objects themselves and multiple simultanous traversal
> becomes reality.

Yeah I thought about those 27 bits but discarded it because it was not
that much. But now that you brought up the maintainability aspect of
it, it might make sense to move those bits out (if we manage to make
commit-slab (or a specialized version of it) manage bitmaps instead of
primitive types, which is not impossible).

I don't understand the tying to struct rev_info though. This is a
struct definition and cannot really be tied to another struct. The
pointer to struct source_slab _is_ tied to struct rev_info.

> Not limited to this particular one, but we'd need to think how the
> commit_slab mechanism should interact with the_repository idea
> Stefan has been having fun with.  If the object pool is maintained
> per in-core repository object, presumably we'd have more than one
> in-core instances of the same commit object if we have more than one
> repository objects, and decorating one with a slab data may not want
> to decorate the other one at the same time.

It should be ok. The slab is indexed by the "commit index" which is
already per parsed_object_pool. Commit-slab user has to be careful to
use the right slab with the right repo and free it at the right time,
but that I think is outside with struct repository.
-- 
Duy

Re: [PATCH 06/12] revision.c: use commit-slab for show_source

[Jeff King]

On Sat, May 12, 2018 at 04:13:59PM +0200, Duy Nguyen wrote:

> > Should this one be global in the first place?  Can we tie it to say
> > "struct rev_info" or something?  I'd somehow anticipate a far future
> > where object flag bits used for traversal book-keeping would be moved
> > out of the objects themselves and multiple simultanous traversal
> > becomes reality.
> 
> Yeah I thought about those 27 bits but discarded it because it was not
> that much. But now that you brought up the maintainability aspect of
> it, it might make sense to move those bits out (if we manage to make
> commit-slab (or a specialized version of it) manage bitmaps instead of
> primitive types, which is not impossible).
> 
> I don't understand the tying to struct rev_info though. This is a
> struct definition and cannot really be tied to another struct. The
> pointer to struct source_slab _is_ tied to struct rev_info.

Right. We have a global type name and global functions, because this is
C. But the actual variable itself is inside struct rev_info (you used a
pointer to a caller-allocated struct, but I think that's fine, too).

> > Not limited to this particular one, but we'd need to think how the
> > commit_slab mechanism should interact with the_repository idea
> > Stefan has been having fun with.  If the object pool is maintained
> > per in-core repository object, presumably we'd have more than one
> > in-core instances of the same commit object if we have more than one
> > repository objects, and decorating one with a slab data may not want
> > to decorate the other one at the same time.
> 
> It should be ok. The slab is indexed by the "commit index" which is
> already per parsed_object_pool. Commit-slab user has to be careful to
> use the right slab with the right repo and free it at the right time,
> but that I think is outside with struct repository.

In theory somebody could misuse a "struct commit" from the wrong
repository and get nonsense results. I'd like to think that would be
pretty hard, but I guess it could be possible to make a mistake like
that at the interface where we call into a submodule-related function.

You could get around it by making the commit_index global across all
pools, but I don't think that's a good idea. Since it's an array index,
we want it to be compact and low.

-Peff

[PATCH 07/12] bisect.c: use commit-slab for commit weight instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 bisect.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/bisect.c b/bisect.c
index a579b50884..6de1abd407 100644
--- a/bisect.c
+++ b/bisect.c
@@ -12,6 +12,7 @@
 #include "bisect.h"
 #include "sha1-array.h"
 #include "argv-array.h"
+#include "commit-slab.h"
 
 static struct oid_array good_revs;
 static struct oid_array skipped_revs;
@@ -70,16 +71,19 @@ static void clear_distance(struct commit_list *list)
 	}
 }
 
+define_commit_slab(commit_weight, int *);
+static struct commit_weight commit_weight;
+
 #define DEBUG_BISECT 0
 
 static inline int weight(struct commit_list *elem)
 {
-	return *((int*)(elem->item->util));
+	return **commit_weight_at(&commit_weight, elem->item);
 }
 
 static inline void weight_set(struct commit_list *elem, int weight)
 {
-	*((int*)(elem->item->util)) = weight;
+	**commit_weight_at(&commit_weight, elem->item) = weight;
 }
 
 static int count_interesting_parents(struct commit *commit)
@@ -265,7 +269,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
 
-		p->item->util = &weights[n++];
+		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
 		switch (count_interesting_parents(commit)) {
 		case 0:
 			if (!(flags & TREESAME)) {
@@ -372,6 +376,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	int *weights;
 
 	show_list("bisection 2 entry", 0, 0, *commit_list);
+	init_commit_weight(&commit_weight);
 
 	/*
 	 * Count the number of total and tree-changing items on the
@@ -412,6 +417,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	}
 	free(weights);
 	*commit_list = best;
+	clear_commit_weight(&commit_weight);
 }
 
 static int register_ref(const char *refname, const struct object_id *oid,
-- 
2.17.0.705.g3525833791

Re: [PATCH 07/12] bisect.c: use commit-slab for commit weight instead of commit->util

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> It's done so that commit->util can be removed. See more explanation in
> the commit that removes commit->util.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---

Yup, this one is a no-brainer.

>  bisect.c | 12 +++++++++---
>  1 file changed, 9 insertions(+), 3 deletions(-)
>
> diff --git a/bisect.c b/bisect.c
> index a579b50884..6de1abd407 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -12,6 +12,7 @@
>  #include "bisect.h"
>  #include "sha1-array.h"
>  #include "argv-array.h"
> +#include "commit-slab.h"
>  
>  static struct oid_array good_revs;
>  static struct oid_array skipped_revs;
> @@ -70,16 +71,19 @@ static void clear_distance(struct commit_list *list)
>  	}
>  }
>  
> +define_commit_slab(commit_weight, int *);
> +static struct commit_weight commit_weight;
> +
>  #define DEBUG_BISECT 0
>  
>  static inline int weight(struct commit_list *elem)
>  {
> -	return *((int*)(elem->item->util));
> +	return **commit_weight_at(&commit_weight, elem->item);
>  }
>  
>  static inline void weight_set(struct commit_list *elem, int weight)
>  {
> -	*((int*)(elem->item->util)) = weight;
> +	**commit_weight_at(&commit_weight, elem->item) = weight;
>  }
>  
>  static int count_interesting_parents(struct commit *commit)
> @@ -265,7 +269,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  		struct commit *commit = p->item;
>  		unsigned flags = commit->object.flags;
>  
> -		p->item->util = &weights[n++];
> +		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
>  		switch (count_interesting_parents(commit)) {
>  		case 0:
>  			if (!(flags & TREESAME)) {
> @@ -372,6 +376,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
>  	int *weights;
>  
>  	show_list("bisection 2 entry", 0, 0, *commit_list);
> +	init_commit_weight(&commit_weight);
>  
>  	/*
>  	 * Count the number of total and tree-changing items on the
> @@ -412,6 +417,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
>  	}
>  	free(weights);
>  	*commit_list = best;
> +	clear_commit_weight(&commit_weight);
>  }
>  
>  static int register_ref(const char *refname, const struct object_id *oid,

[PATCH 08/12] name-rev: use commit-slab for rev-name instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/name-rev.c | 23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 387ddf85d2..0eb440359d 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -6,6 +6,7 @@
 #include "refs.h"
 #include "parse-options.h"
 #include "sha1-lookup.h"
+#include "commit-slab.h"
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 
@@ -17,11 +18,26 @@ typedef struct rev_name {
 	int from_tag;
 } rev_name;
 
+define_commit_slab(commit_rev_name, struct rev_name *);
+
 static timestamp_t cutoff = TIME_MAX;
+static struct commit_rev_name rev_names;
 
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
+static struct rev_name *get_commit_rev_name(struct commit *commit)
+{
+	struct rev_name **slot = commit_rev_name_peek(&rev_names, commit);
+
+	return slot ? *slot : NULL;
+}
+
+static void set_commit_rev_name(struct commit *commit, struct rev_name *name)
+{
+	*commit_rev_name_at(&rev_names, commit) = name;
+}
+
 static int is_better_name(struct rev_name *name,
 			  const char *tip_name,
 			  timestamp_t taggerdate,
@@ -65,7 +81,7 @@ static void name_rev(struct commit *commit,
 		int generation, int distance, int from_tag,
 		int deref)
 {
-	struct rev_name *name = (struct rev_name *)commit->util;
+	struct rev_name *name = get_commit_rev_name(commit);
 	struct commit_list *parents;
 	int parent_number = 1;
 	char *to_free = NULL;
@@ -84,7 +100,7 @@ static void name_rev(struct commit *commit,
 
 	if (name == NULL) {
 		name = xmalloc(sizeof(rev_name));
-		commit->util = name;
+		set_commit_rev_name(commit, name);
 		goto copy_data;
 	} else if (is_better_name(name, tip_name, taggerdate,
 				  generation, distance, from_tag)) {
@@ -296,7 +312,7 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
 	if (o->type != OBJ_COMMIT)
 		return get_exact_ref_match(o);
 	c = (struct commit *) o;
-	n = c->util;
+	n = get_commit_rev_name(c);
 	if (!n)
 		return NULL;
 
@@ -413,6 +429,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		OPT_END(),
 	};
 
+	init_commit_rev_name(&rev_names);
 	git_config(git_default_config, NULL);
 	argc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);
 	if (all + transform_stdin + !!argc > 1) {
-- 
2.17.0.705.g3525833791

[PATCH 09/12] show-branch: use commit-slab for commit-name instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
 1 file changed, 27 insertions(+), 12 deletions(-)

diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 6c2148b71d..29d15d16d2 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -7,6 +7,7 @@
 #include "argv-array.h"
 #include "parse-options.h"
 #include "dir.h"
+#include "commit-slab.h"
 
 static const char* show_branch_usage[] = {
     N_("git show-branch [-a | --all] [-r | --remotes] [--topo-order | --date-order]\n"
@@ -59,15 +60,27 @@ struct commit_name {
 	int generation; /* how many parents away from head_name */
 };
 
+define_commit_slab(commit_name_slab, struct commit_name *);
+static struct commit_name_slab name_slab;
+
+static struct commit_name *commit_to_name(struct commit *commit)
+{
+	return *commit_name_slab_at(&name_slab, commit);
+}
+
+
 /* Name the commit as nth generation ancestor of head_name;
  * we count only the first-parent relationship for naming purposes.
  */
 static void name_commit(struct commit *commit, const char *head_name, int nth)
 {
 	struct commit_name *name;
-	if (!commit->util)
-		commit->util = xmalloc(sizeof(struct commit_name));
-	name = commit->util;
+
+	name = *commit_name_slab_at(&name_slab, commit);
+	if (!name) {
+		name = xmalloc(sizeof(*name));
+		*commit_name_slab_at(&name_slab, commit) = name;
+	}
 	name->head_name = head_name;
 	name->generation = nth;
 }
@@ -79,8 +92,8 @@ static void name_commit(struct commit *commit, const char *head_name, int nth)
  */
 static void name_parent(struct commit *commit, struct commit *parent)
 {
-	struct commit_name *commit_name = commit->util;
-	struct commit_name *parent_name = parent->util;
+	struct commit_name *commit_name = commit_to_name(commit);
+	struct commit_name *parent_name = commit_to_name(parent);
 	if (!commit_name)
 		return;
 	if (!parent_name ||
@@ -94,12 +107,12 @@ static int name_first_parent_chain(struct commit *c)
 	int i = 0;
 	while (c) {
 		struct commit *p;
-		if (!c->util)
+		if (!commit_to_name(c))
 			break;
 		if (!c->parents)
 			break;
 		p = c->parents->item;
-		if (!p->util) {
+		if (!commit_to_name(p)) {
 			name_parent(c, p);
 			i++;
 		}
@@ -122,7 +135,7 @@ static void name_commits(struct commit_list *list,
 	/* First give names to the given heads */
 	for (cl = list; cl; cl = cl->next) {
 		c = cl->item;
-		if (c->util)
+		if (commit_to_name(c))
 			continue;
 		for (i = 0; i < num_rev; i++) {
 			if (rev[i] == c) {
@@ -148,9 +161,9 @@ static void name_commits(struct commit_list *list,
 			struct commit_name *n;
 			int nth;
 			c = cl->item;
-			if (!c->util)
+			if (!commit_to_name(c))
 				continue;
-			n = c->util;
+			n = commit_to_name(c);
 			parents = c->parents;
 			nth = 0;
 			while (parents) {
@@ -158,7 +171,7 @@ static void name_commits(struct commit_list *list,
 				struct strbuf newname = STRBUF_INIT;
 				parents = parents->next;
 				nth++;
-				if (p->util)
+				if (commit_to_name(p))
 					continue;
 				switch (n->generation) {
 				case 0:
@@ -271,7 +284,7 @@ static void show_one_commit(struct commit *commit, int no_name)
 {
 	struct strbuf pretty = STRBUF_INIT;
 	const char *pretty_str = "(unavailable)";
-	struct commit_name *name = commit->util;
+	struct commit_name *name = commit_to_name(commit);
 
 	if (commit->object.parsed) {
 		pp_commit_easy(CMIT_FMT_ONELINE, commit, &pretty);
@@ -660,6 +673,8 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		OPT_END()
 	};
 
+	init_commit_name_slab(&name_slab);
+
 	git_config(git_show_branch_config, NULL);
 
 	/* If nothing is specified, try the default first */
-- 
2.17.0.705.g3525833791

[PATCH 10/12] log: use commit-slab in prepare_bases() instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/log.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 0d199ebd5d..b771d27164 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -28,6 +28,7 @@
 #include "mailmap.h"
 #include "gpg-interface.h"
 #include "progress.h"
+#include "commit-slab.h"
 
 #define MAIL_DEFAULT_WRAP 72
 
@@ -1340,6 +1341,8 @@ static struct commit *get_base_commit(const char *base_commit,
 	return base;
 }
 
+define_commit_slab(commit_base, int);
+
 static void prepare_bases(struct base_tree_info *bases,
 			  struct commit *base,
 			  struct commit **list,
@@ -1348,11 +1351,13 @@ static void prepare_bases(struct base_tree_info *bases,
 	struct commit *commit;
 	struct rev_info revs;
 	struct diff_options diffopt;
+	struct commit_base commit_base;
 	int i;
 
 	if (!base)
 		return;
 
+	init_commit_base(&commit_base);
 	diff_setup(&diffopt);
 	diffopt.flags.recursive = 1;
 	diff_setup_done(&diffopt);
@@ -1365,7 +1370,7 @@ static void prepare_bases(struct base_tree_info *bases,
 	for (i = 0; i < total; i++) {
 		list[i]->object.flags &= ~UNINTERESTING;
 		add_pending_object(&revs, &list[i]->object, "rev_list");
-		list[i]->util = (void *)1;
+		*commit_base_at(&commit_base, list[i]) = 1;
 	}
 	base->object.flags |= UNINTERESTING;
 	add_pending_object(&revs, &base->object, "base");
@@ -1379,7 +1384,7 @@ static void prepare_bases(struct base_tree_info *bases,
 	while ((commit = get_revision(&revs)) != NULL) {
 		struct object_id oid;
 		struct object_id *patch_id;
-		if (commit->util)
+		if (*commit_base_at(&commit_base, commit))
 			continue;
 		if (commit_patch_id(commit, &diffopt, &oid, 0))
 			die(_("cannot get patch id"));
@@ -1388,6 +1393,7 @@ static void prepare_bases(struct base_tree_info *bases,
 		oidcpy(patch_id, &oid);
 		bases->nr_patch_id++;
 	}
+	clear_commit_base(&commit_base);
 }
 
 static void print_bases(struct base_tree_info *bases, FILE *file)
-- 
2.17.0.705.g3525833791

[PATCH 11/12] merge: use commit-slab in merge remote desc instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/merge.c   | 25 +++++++++++++------------
 commit.c          | 12 ++++++++++--
 commit.h          |  2 +-
 merge-recursive.c |  8 +++++---
 4 files changed, 29 insertions(+), 18 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9db5a2cf16..fc55bc264b 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -443,6 +443,7 @@ static void merge_name(const char *remote, struct strbuf *msg)
 	struct object_id branch_head;
 	struct strbuf buf = STRBUF_INIT;
 	struct strbuf bname = STRBUF_INIT;
+	struct merge_remote_desc *desc;
 	const char *ptr;
 	char *found_ref;
 	int len, early;
@@ -515,16 +516,13 @@ static void merge_name(const char *remote, struct strbuf *msg)
 		strbuf_release(&truname);
 	}
 
-	if (remote_head->util) {
-		struct merge_remote_desc *desc;
-		desc = merge_remote_util(remote_head);
-		if (desc && desc->obj && desc->obj->type == OBJ_TAG) {
-			strbuf_addf(msg, "%s\t\t%s '%s'\n",
-				    oid_to_hex(&desc->obj->oid),
-				    type_name(desc->obj->type),
-				    remote);
-			goto cleanup;
-		}
+	desc = merge_remote_util(remote_head);
+	if (desc && desc->obj && desc->obj->type == OBJ_TAG) {
+		strbuf_addf(msg, "%s\t\t%s '%s'\n",
+			    oid_to_hex(&desc->obj->oid),
+			    type_name(desc->obj->type),
+			    remote);
+		goto cleanup;
 	}
 
 	strbuf_addf(msg, "%s\t\tcommit '%s'\n",
@@ -932,8 +930,11 @@ static void write_merge_heads(struct commit_list *remoteheads)
 	for (j = remoteheads; j; j = j->next) {
 		struct object_id *oid;
 		struct commit *c = j->item;
-		if (c->util && merge_remote_util(c)->obj) {
-			oid = &merge_remote_util(c)->obj->oid;
+		struct merge_remote_desc *desc;
+
+		desc = merge_remote_util(c);
+		if (desc && desc->obj) {
+			oid = &desc->obj->oid;
 		} else {
 			oid = &c->object.oid;
 		}
diff --git a/commit.c b/commit.c
index 57049118a5..8202067cd5 100644
--- a/commit.c
+++ b/commit.c
@@ -1574,13 +1574,21 @@ int commit_tree_extended(const char *msg, size_t msg_len,
 	return result;
 }
 
+define_commit_slab(merge_desc_slab, struct merge_remote_desc *);
+struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);
+
+struct merge_remote_desc *merge_remote_util(struct commit *commit)
+{
+	return *merge_desc_slab_at(&merge_desc_slab, commit);
+}
+
 void set_merge_remote_desc(struct commit *commit,
 			   const char *name, struct object *obj)
 {
 	struct merge_remote_desc *desc;
 	FLEX_ALLOC_STR(desc, name, name);
 	desc->obj = obj;
-	commit->util = desc;
+	*merge_desc_slab_at(&merge_desc_slab, commit) = desc;
 }
 
 struct commit *get_merge_parent(const char *name)
@@ -1592,7 +1600,7 @@ struct commit *get_merge_parent(const char *name)
 		return NULL;
 	obj = parse_object(&oid);
 	commit = (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
-	if (commit && !commit->util)
+	if (commit && !merge_remote_util(commit))
 		set_merge_remote_desc(commit, name, obj);
 	return commit;
 }
diff --git a/commit.h b/commit.h
index e57ae4b583..838f6a6b26 100644
--- a/commit.h
+++ b/commit.h
@@ -303,7 +303,7 @@ struct merge_remote_desc {
 	struct object *obj; /* the named object, could be a tag */
 	char name[FLEX_ARRAY];
 };
-#define merge_remote_util(commit) ((struct merge_remote_desc *)((commit)->util))
+extern struct merge_remote_desc *merge_remote_util(struct commit *);
 extern void set_merge_remote_desc(struct commit *commit,
 				  const char *name, struct object *obj);
 
diff --git a/merge-recursive.c b/merge-recursive.c
index 0c0d48624d..5537f01f8e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -223,10 +223,12 @@ static void output(struct merge_options *o, int v, const char *fmt, ...)
 
 static void output_commit_title(struct merge_options *o, struct commit *commit)
 {
+	struct merge_remote_desc *desc;
+
 	strbuf_addchars(&o->obuf, ' ', o->call_depth * 2);
-	if (commit->util)
-		strbuf_addf(&o->obuf, "virtual %s\n",
-			merge_remote_util(commit)->name);
+	desc = merge_remote_util(commit);
+	if (desc)
+		strbuf_addf(&o->obuf, "virtual %s\n", desc->name);
 	else {
 		strbuf_add_unique_abbrev(&o->obuf, &commit->object.oid,
 					 DEFAULT_ABBREV);
-- 
2.17.0.705.g3525833791

[PATCH 12/12] commit.h: delete 'util' field in struct commit

[Nguyễn Thái Ngọc Duy]

If you have come this far, you probably have seen that this 'util'
pointer is used for many different purposes. Some are not even
contained in a command code, but buried deep in common code with no
clue who will use it and how.

The move to using commit-slab gives us a much better picture of how
some piece of data is associated with a commit and what for. Since
nobody uses 'util' pointer anymore, we can retire so that nobody will
abuse it again. commit-slab will be the way forward for associating
data to a commit.

As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
architecture) which should help reduce memory usage for reachability
test a bit. This is also what commit-slab is invented for [1].

[1] 96c4f4a370 (commit: allow associating auxiliary info on-demand -
2013-04-09)

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit.h | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/commit.h b/commit.h
index 838f6a6b26..70371e111e 100644
--- a/commit.h
+++ b/commit.h
@@ -18,12 +18,16 @@ struct commit_list {
 
 struct commit {
 	struct object object;
-	void *util;
 	unsigned int index;
 	timestamp_t date;
 	struct commit_list *parents;
 	struct tree *tree;
 	uint32_t graph_pos;
+	/*
+	 * Do not add more fields here unless it's _very_ often
+	 * used. Use commit-slab to associate more data with a commit
+	 * instead.
+	 */
 };
 
 extern int save_commit_buffer;
-- 
2.17.0.705.g3525833791

Re: [PATCH 00/12] Die commit->util, die!

[Jeff King]

On Sat, May 12, 2018 at 10:00:16AM +0200, Nguyễn Thái Ngọc Duy wrote:

> There's not much to write here. It's basically a copy from 12/12:
> 
> This 'util' pointer can be used for many different purposes,
> controlled in different ways. Some are not even contained in a command
> code, but buried deep in common code with no clue who will use it and
> how. For example, if revs.show_source is set, then it's used for
> storing path name, but if you happen to call get_merge_parent() then
> some 'util' may end up storing another thing.
> 
> The move to using commit-slab gives us a much better picture of how
> some piece of data is associated with a commit and what for. Since
> nobody uses 'util' pointer anymore, we can retire it so that nobody will
> abuse it again. commit-slab will be the way forward for associating
> data to a commit.
> 
> As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
> architecture) which should help reduce memory usage for reachability
> test a bit. This is also what commit-slab is invented for [1].

I left a few comments, but overall this looks pretty good. A few of the
conversions get tricky with the number of pointer dereferences, but most
of those were pretty tricky to begin with (that weight stuff in
bisect.c...yikes!).

I love the result. More maintainable code, less possibility of conflicts
in the util field, and a memory savings to boot.

-Peff

Re: [PATCH 00/12] Die commit->util, die!

[Jakub Narebski]

Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:

> There's not much to write here. It's basically a copy from 12/12:
>
> This 'util' pointer can be used for many different purposes,
> controlled in different ways. Some are not even contained in a command
> code, but buried deep in common code with no clue who will use it and
> how. For example, if revs.show_source is set, then it's used for
> storing path name, but if you happen to call get_merge_parent() then
> some 'util' may end up storing another thing.
>
> The move to using commit-slab gives us a much better picture of how
> some piece of data is associated with a commit and what for. Since
> nobody uses 'util' pointer anymore, we can retire it so that nobody will
> abuse it again. commit-slab will be the way forward for associating
> data to a commit.
>
> As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
> architecture) which should help reduce memory usage for reachability
> test a bit. This is also what commit-slab is invented for [1].
>
> [1] 96c4f4a370 (commit: allow associating auxiliary info on-demand -
> 2013-04-09)

Good work.  This would reduce the amount of technical debt in Git.

I just wonder if most of those transformation could not be done with
Coccinelle, instead of doing it by hand.

> Nguyễn Thái Ngọc Duy (12):
>   blame: use commit-slab for blame suspects instead of commit->util
>   describe: use commit-slab for commit names instead of commit->util
>   shallow.c: use commit-slab for commit depth instead of commit->util
>   sequencer.c: use commit-slab to mark seen commits
>   sequencer.c: use commit-slab to associate todo items to commits
>   revision.c: use commit-slab for show_source
>   bisect.c: use commit-slab for commit weight instead of commit->util
>   name-rev: use commit-slab for rev-name instead of commit->util
>   show-branch: use commit-slab for commit-name instead of commit->util
>   log: use commit-slab in prepare_bases() instead of commit->util
>   merge: use commit-slab in merge remote desc instead of commit->util
>   commit.h: delete 'util' field in struct commit
>
>  bisect.c              | 12 +++++++++---
>  blame.c               | 42 +++++++++++++++++++++++++++++++-----------
>  blame.h               |  2 ++
>  builtin/blame.c       |  2 +-
>  builtin/describe.c    | 16 +++++++++++++---
>  builtin/fast-export.c | 14 +++++++++-----
>  builtin/log.c         | 17 +++++++++++++----
>  builtin/merge.c       | 25 +++++++++++++------------
>  builtin/name-rev.c    | 23 ++++++++++++++++++++---
>  builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
>  commit.c              | 12 ++++++++++--
>  commit.h              |  8 ++++++--
>  log-tree.c            |  8 ++++++--
>  merge-recursive.c     |  8 +++++---
>  revision.c            | 17 +++++++++++++----
>  revision.h            |  5 ++++-
>  sequencer.c           | 24 ++++++++++++++++++------
>  shallow.c             | 37 +++++++++++++++++++++++++------------
>  18 files changed, 225 insertions(+), 86 deletions(-)

Re: [PATCH 00/12] Die commit->util, die!

[Duy Nguyen]

On Sat, May 12, 2018 at 8:50 PM, Jakub Narebski <jnareb@gmail.com> wrote:
> I just wonder if most of those transformation could not be done with
> Coccinelle, instead of doing it by hand.

I doubt coccinelle is smart enough to figure out the convoluted use of
'util' pointer (but then I'm not a heavy coccinelle user). I actually
got it wrong a couple times and had to rely on the test suite to guide
me.
-- 
Duy

[PATCH v2 00/14] Die commit->util, die!

[Nguyễn Thái Ngọc Duy]

v2 is mostly refinements with a big change: commit-slab.h is
restructured to allow sharing commit slabs. Other changes are

- rename struct source_slab to revision_sources
- keep revision_sources_* functinons (and one static variable) to
  revision.c instead of duplicating them whenver revision.h is
  included.
- reduce elemtype in commit_seen in sequencer.c from 4 bytes to 1.
- avoid dereferencing _peek in sequencer.c

Interdiff

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 092e29583e..b08e5ea0e3 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -39,7 +39,7 @@ static struct string_list extra_refs = STRING_LIST_INIT_NODUP;
 static struct refspec *refspecs;
 static int refspecs_nr;
 static int anonymize;
-static struct source_slab source_slab;
+static struct revision_sources revision_sources;
 
 static int parse_opt_signed_tag_mode(const struct option *opt,
 				     const char *arg, int unset)
@@ -592,7 +592,7 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,
 		if (!S_ISGITLINK(diff_queued_diff.queue[i]->two->mode))
 			export_blob(&diff_queued_diff.queue[i]->two->oid);
 
-	refname = *source_slab_peek(&source_slab, commit);
+	refname = *revision_sources_peek(&revision_sources, commit);
 	if (anonymize) {
 		refname = anonymize_refname(refname);
 		anonymize_ident_line(&committer, &committer_end);
@@ -864,11 +864,11 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)
 		 * This ref will not be updated through a commit, lets make
 		 * sure it gets properly updated eventually.
 		 */
-		if (*source_slab_at(&source_slab, commit) ||
+		if (*revision_sources_at(&revision_sources, commit) ||
 		    commit->object.flags & SHOWN)
 			string_list_append(&extra_refs, full_name)->util = commit;
-		if (!*source_slab_at(&source_slab, commit))
-			*source_slab_at(&source_slab, commit) = full_name;
+		if (!*revision_sources_at(&revision_sources, commit))
+			*revision_sources_at(&revision_sources, commit) = full_name;
 	}
 }
 
@@ -1032,9 +1032,9 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
 	git_config(git_default_config, NULL);
 
 	init_revisions(&revs, prefix);
-	init_source_slab(&source_slab);
+	init_revision_sources(&revision_sources);
 	revs.topo_order = 1;
-	revs.source_slab = &source_slab;
+	revs.sources = &revision_sources;
 	revs.rewrite_parents = 1;
 	argc = parse_options(argc, argv, prefix, options, fast_export_usage,
 			PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN);
diff --git a/builtin/log.c b/builtin/log.c
index b771d27164..967fbc5caa 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -149,7 +149,7 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	static struct string_list decorate_refs_include = STRING_LIST_INIT_NODUP;
 	struct decoration_filter decoration_filter = {&decorate_refs_include,
 						      &decorate_refs_exclude};
-	static struct source_slab source_slab;
+	static struct revision_sources revision_sources;
 
 	const struct option builtin_log_options[] = {
 		OPT__QUIET(&quiet, N_("suppress diff output")),
@@ -197,8 +197,8 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 		rev->always_show_header = 0;
 
 	if (source) {
-		init_source_slab(&source_slab);
-		rev->source_slab = &source_slab;
+		init_revision_sources(&revision_sources);
+		rev->sources = &revision_sources;
 	}
 
 	if (mailmap) {
diff --git a/commit-slab-hdr.h b/commit-slab-hdr.h
new file mode 100644
index 0000000000..adc7b46c83
--- /dev/null
+++ b/commit-slab-hdr.h
@@ -0,0 +1,43 @@
+#ifndef COMMIT_SLAB_HDR_H
+#define COMMIT_SLAB_HDR_H
+
+/* allocate ~512kB at once, allowing for malloc overhead */
+#ifndef COMMIT_SLAB_SIZE
+#define COMMIT_SLAB_SIZE (512*1024-32)
+#endif
+
+#define declare_commit_slab(slabname, elemtype) 			\
+									\
+struct slabname {							\
+	unsigned slab_size;						\
+	unsigned stride;						\
+	unsigned slab_count;						\
+	elemtype **slab;						\
+}
+
+/*
+ * Statically initialize a commit slab named "var". Note that this
+ * evaluates "stride" multiple times! Example:
+ *
+ *   struct indegree indegrees = COMMIT_SLAB_INIT(1, indegrees);
+ *
+ */
+#define COMMIT_SLAB_INIT(stride, var) { \
+	COMMIT_SLAB_SIZE / sizeof(**((var).slab)) / (stride), \
+	(stride), 0, NULL \
+}
+
+#define declare_commit_slab_prototypes(slabname, elemtype)		\
+									\
+void init_ ##slabname## _with_stride(struct slabname *s, unsigned stride); \
+void init_ ##slabname(struct slabname *s);				\
+void clear_ ##slabname(struct slabname *s);				\
+elemtype *slabname## _at_peek(struct slabname *s, const struct commit *c, int add_if_missing); \
+elemtype *slabname## _at(struct slabname *s, const struct commit *c);	\
+elemtype *slabname## _peek(struct slabname *s, const struct commit *c)
+
+#define define_shared_commit_slab(slabname, elemtype) \
+	declare_commit_slab(slabname, elemtype); \
+	declare_commit_slab_prototypes(slabname, elemtype)
+
+#endif /* COMMIT_SLAB_HDR_H */
diff --git a/commit-slab-impl.h b/commit-slab-impl.h
new file mode 100644
index 0000000000..19a88d7d8f
--- /dev/null
+++ b/commit-slab-impl.h
@@ -0,0 +1,97 @@
+#ifndef COMMIT_SLAB_IMPL_H
+#define COMMIT_SLAB_IMPL_H
+
+#define MAYBE_UNUSED __attribute__((__unused__))
+
+#define implement_static_commit_slab(slabname, elemtype) \
+	implement_commit_slab(slabname, elemtype, static MAYBE_UNUSED)
+
+#define implement_shared_commit_slab(slabname, elemtype) \
+	implement_commit_slab(slabname, elemtype, )
+
+#define implement_commit_slab(slabname, elemtype, scope)		\
+									\
+static int stat_ ##slabname## realloc;					\
+									\
+scope void init_ ##slabname## _with_stride(struct slabname *s,		\
+						   unsigned stride)	\
+{									\
+	unsigned int elem_size;						\
+	if (!stride)							\
+		stride = 1;						\
+	s->stride = stride;						\
+	elem_size = sizeof(elemtype) * stride;				\
+	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
+	s->slab_count = 0;						\
+	s->slab = NULL;							\
+}									\
+									\
+scope void init_ ##slabname(struct slabname *s)				\
+{									\
+	init_ ##slabname## _with_stride(s, 1);				\
+}									\
+									\
+scope void clear_ ##slabname(struct slabname *s)			\
+{									\
+	unsigned int i;							\
+	for (i = 0; i < s->slab_count; i++)				\
+		free(s->slab[i]);					\
+	s->slab_count = 0;						\
+	FREE_AND_NULL(s->slab);						\
+}									\
+									\
+scope elemtype *slabname## _at_peek(struct slabname *s,			\
+						  const struct commit *c, \
+						  int add_if_missing)   \
+{									\
+	unsigned int nth_slab, nth_slot;				\
+									\
+	nth_slab = c->index / s->slab_size;				\
+	nth_slot = c->index % s->slab_size;				\
+									\
+	if (s->slab_count <= nth_slab) {				\
+		unsigned int i;						\
+		if (!add_if_missing)					\
+			return NULL;					\
+		REALLOC_ARRAY(s->slab, nth_slab + 1);			\
+		stat_ ##slabname## realloc++;				\
+		for (i = s->slab_count; i <= nth_slab; i++)		\
+			s->slab[i] = NULL;				\
+		s->slab_count = nth_slab + 1;				\
+	}								\
+	if (!s->slab[nth_slab]) {					\
+		if (!add_if_missing)					\
+			return NULL;					\
+		s->slab[nth_slab] = xcalloc(s->slab_size,		\
+					    sizeof(**s->slab) * s->stride);		\
+	}								\
+	return &s->slab[nth_slab][nth_slot * s->stride];		\
+}									\
+									\
+scope elemtype *slabname## _at(struct slabname *s,			\
+					     const struct commit *c)	\
+{									\
+	return slabname##_at_peek(s, c, 1);				\
+}									\
+									\
+scope elemtype *slabname## _peek(struct slabname *s,			\
+					     const struct commit *c)	\
+{									\
+	return slabname##_at_peek(s, c, 0);				\
+}									\
+									\
+struct slabname
+
+/*
+ * Note that this redundant forward declaration is required
+ * to allow a terminating semicolon, which makes instantiations look
+ * like function declarations.  I.e., the expansion of
+ *
+ *    implement_commit_slab(indegree, int);
+ *
+ * ends in 'struct indegree;'.  This would otherwise
+ * be a syntax error according (at least) to ISO C.  It's hard to
+ * catch because GCC silently parses it by default.
+ */
+
+#endif	/* COMMIT_SLAB_IMPL_H */
diff --git a/commit-slab.h b/commit-slab.h
index dcaab8ca04..dc029acc66 100644
--- a/commit-slab.h
+++ b/commit-slab.h
@@ -1,6 +1,9 @@
 #ifndef COMMIT_SLAB_H
 #define COMMIT_SLAB_H
 
+#include "commit-slab-hdr.h"
+#include "commit-slab-impl.h"
+
 /*
  * define_commit_slab(slabname, elemtype) creates boilerplate code to define
  * a new struct (struct slabname) that is used to associate a piece of data
@@ -41,114 +44,8 @@
  *   leaking memory.
  */
 
-/* allocate ~512kB at once, allowing for malloc overhead */
-#ifndef COMMIT_SLAB_SIZE
-#define COMMIT_SLAB_SIZE (512*1024-32)
-#endif
-
-#define MAYBE_UNUSED __attribute__((__unused__))
-
-#define define_commit_slab(slabname, elemtype) 				\
-									\
-struct slabname {							\
-	unsigned slab_size;						\
-	unsigned stride;						\
-	unsigned slab_count;						\
-	elemtype **slab;						\
-};									\
-static int stat_ ##slabname## realloc;					\
-									\
-static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
-						   unsigned stride)	\
-{									\
-	unsigned int elem_size;						\
-	if (!stride)							\
-		stride = 1;						\
-	s->stride = stride;						\
-	elem_size = sizeof(elemtype) * stride;				\
-	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
-	s->slab_count = 0;						\
-	s->slab = NULL;							\
-}									\
-									\
-static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
-{									\
-	init_ ##slabname## _with_stride(s, 1);				\
-}									\
-									\
-static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
-{									\
-	unsigned int i;							\
-	for (i = 0; i < s->slab_count; i++)				\
-		free(s->slab[i]);					\
-	s->slab_count = 0;						\
-	FREE_AND_NULL(s->slab);						\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
-						  const struct commit *c, \
-						  int add_if_missing)   \
-{									\
-	unsigned int nth_slab, nth_slot;				\
-									\
-	nth_slab = c->index / s->slab_size;				\
-	nth_slot = c->index % s->slab_size;				\
-									\
-	if (s->slab_count <= nth_slab) {				\
-		unsigned int i;						\
-		if (!add_if_missing)					\
-			return NULL;					\
-		REALLOC_ARRAY(s->slab, nth_slab + 1);			\
-		stat_ ##slabname## realloc++;				\
-		for (i = s->slab_count; i <= nth_slab; i++)		\
-			s->slab[i] = NULL;				\
-		s->slab_count = nth_slab + 1;				\
-	}								\
-	if (!s->slab[nth_slab]) {					\
-		if (!add_if_missing)					\
-			return NULL;					\
-		s->slab[nth_slab] = xcalloc(s->slab_size,		\
-					    sizeof(**s->slab) * s->stride);		\
-	}								\
-	return &s->slab[nth_slab][nth_slot * s->stride];		\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
-					     const struct commit *c)	\
-{									\
-	return slabname##_at_peek(s, c, 1);				\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
-					     const struct commit *c)	\
-{									\
-	return slabname##_at_peek(s, c, 0);				\
-}									\
-									\
-struct slabname
-
-/*
- * Note that this redundant forward declaration is required
- * to allow a terminating semicolon, which makes instantiations look
- * like function declarations.  I.e., the expansion of
- *
- *    define_commit_slab(indegree, int);
- *
- * ends in 'struct indegree;'.  This would otherwise
- * be a syntax error according (at least) to ISO C.  It's hard to
- * catch because GCC silently parses it by default.
- */
-
-/*
- * Statically initialize a commit slab named "var". Note that this
- * evaluates "stride" multiple times! Example:
- *
- *   struct indegree indegrees = COMMIT_SLAB_INIT(1, indegrees);
- *
- */
-#define COMMIT_SLAB_INIT(stride, var) { \
-	COMMIT_SLAB_SIZE / sizeof(**((var).slab)) / (stride), \
-	(stride), 0, NULL \
-}
+#define define_commit_slab(slabname, elemtype) \
+	declare_commit_slab(slabname, elemtype); \
+	implement_static_commit_slab(slabname, elemtype)
 
 #endif /* COMMIT_SLAB_H */
diff --git a/log-tree.c b/log-tree.c
index d36a945fc4..0b41ee3235 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -295,8 +295,8 @@ void show_decorations(struct rev_info *opt, struct commit *commit)
 {
 	struct strbuf sb = STRBUF_INIT;
 
-	if (opt->source_slab) {
-		char **slot = source_slab_peek(opt->source_slab, commit);
+	if (opt->sources) {
+		char **slot = revision_sources_peek(opt->sources, commit);
 
 		if (slot && *slot)
 			fprintf(opt->diffopt.file, "\t%s", *slot);
diff --git a/revision.c b/revision.c
index 41b56f789d..be8fe7d67b 100644
--- a/revision.c
+++ b/revision.c
@@ -29,6 +29,8 @@ volatile show_early_output_fn_t show_early_output;
 static const char *term_bad;
 static const char *term_good;
 
+implement_shared_commit_slab(revision_sources, char *);
+
 void show_object_with_name(FILE *out, struct object *obj, const char *name)
 {
 	const char *p;
@@ -262,8 +264,8 @@ static struct commit *handle_commit(struct rev_info *revs,
 			mark_parents_uninteresting(commit);
 			revs->limited = 1;
 		}
-		if (revs->source_slab) {
-			char **slot = source_slab_at(revs->source_slab, commit);
+		if (revs->sources) {
+			char **slot = revision_sources_at(revs->sources, commit);
 
 			if (!*slot)
 				*slot = xstrdup(name);
@@ -819,11 +821,11 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			}
 			return -1;
 		}
-		if (revs->source_slab) {
-			char **slot = source_slab_at(revs->source_slab, p);
+		if (revs->sources) {
+			char **slot = revision_sources_at(revs->sources, p);
 
 			if (!*slot)
-				*slot = *source_slab_at(revs->source_slab, commit);
+				*slot = *revision_sources_at(revs->sources, commit);
 		}
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
diff --git a/revision.h b/revision.h
index 72404e2599..f3dc5f9740 100644
--- a/revision.h
+++ b/revision.h
@@ -6,7 +6,7 @@
 #include "notes.h"
 #include "pretty.h"
 #include "diff.h"
-#include "commit-slab.h"
+#include "commit-slab-hdr.h"
 
 /* Remember to update object flag allocation in object.h */
 #define SEEN		(1u<<0)
@@ -30,7 +30,7 @@ struct rev_info;
 struct log_info;
 struct string_list;
 struct saved_parents;
-define_commit_slab(source_slab, char *);
+define_shared_commit_slab(revision_sources, char *);
 
 struct rev_cmdline_info {
 	unsigned int nr;
@@ -226,7 +226,7 @@ struct rev_info {
 	struct commit_list *previous_parents;
 	const char *break_bar;
 
-	struct source_slab *source_slab;
+	struct revision_sources *sources;
 };
 
 extern int ref_excluded(struct string_list *, const char *path);
diff --git a/sequencer.c b/sequencer.c
index 1a0a6916e3..dd4993fd99 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -3161,7 +3161,7 @@ static enum check_level get_missing_commit_check_level(void)
 	return CHECK_IGNORE;
 }
 
-define_commit_slab(commit_seen, int);
+define_commit_slab(commit_seen, uint8_t);
 /*
  * Check if the user dropped some commits by mistake
  * Behaviour determined by rebase.missingCommitsCheck.
@@ -3453,7 +3453,7 @@ int rearrange_squash(void)
 				  lookup_commit_reference_by_name(p)) &&
 				 *commit_todo_item_at(&commit_todo, commit2))
 				/* found by commit name */
-				i2 = *commit_todo_item_peek(&commit_todo, commit2)
+				i2 = *commit_todo_item_at(&commit_todo, commit2)
 					- todo_list.items;
 			else {
 				/* copy can be a prefix of the commit subject */
diff --git a/shallow.c b/shallow.c
index 6ea411b0d2..daf60a9391 100644
--- a/shallow.c
+++ b/shallow.c
@@ -75,6 +75,10 @@ int is_repository_shallow(void)
 	return is_shallow;
 }
 
+/*
+ * TODO: use "int" elemtype instead of "int *" when/if commit-slab
+ * supports a "valid" flag.
+ */
 define_commit_slab(commit_depth, int *);
 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		int shallow_flag, int not_shallow_flag)


Nguyễn Thái Ngọc Duy (14):
  commit-slab.h: code split
  commit-slab: support shared commit-slab
  blame: use commit-slab for blame suspects instead of commit->util
  describe: use commit-slab for commit names instead of commit->util
  shallow.c: use commit-slab for commit depth instead of commit->util
  sequencer.c: use commit-slab to mark seen commits
  sequencer.c: use commit-slab to associate todo items to commits
  revision.c: use commit-slab for show_source
  bisect.c: use commit-slab for commit weight instead of commit->util
  name-rev: use commit-slab for rev-name instead of commit->util
  show-branch: use commit-slab for commit-name instead of commit->util
  log: use commit-slab in prepare_bases() instead of commit->util
  merge: use commit-slab in merge remote desc instead of commit->util
  commit.h: delete 'util' field in struct commit

 bisect.c              |  12 +++--
 blame.c               |  42 +++++++++++----
 blame.h               |   2 +
 builtin/blame.c       |   2 +-
 builtin/describe.c    |  16 ++++--
 builtin/fast-export.c |  14 +++--
 builtin/log.c         |  17 +++++--
 builtin/merge.c       |  25 ++++-----
 builtin/name-rev.c    |  23 +++++++--
 builtin/show-branch.c |  39 +++++++++-----
 commit-slab-hdr.h     |  43 ++++++++++++++++
 commit-slab-impl.h    |  97 +++++++++++++++++++++++++++++++++++
 commit-slab.h         | 115 +++---------------------------------------
 commit.c              |  12 ++++-
 commit.h              |   8 ++-
 log-tree.c            |   8 ++-
 merge-recursive.c     |   8 +--
 revision.c            |  19 +++++--
 revision.h            |   5 +-
 sequencer.c           |  24 ++++++---
 shallow.c             |  41 ++++++++++-----
 21 files changed, 377 insertions(+), 195 deletions(-)
 create mode 100644 commit-slab-hdr.h
 create mode 100644 commit-slab-impl.h

-- 
2.17.0.705.g3525833791

[PATCH v2 01/14] commit-slab.h: code split

[Nguyễn Thái Ngọc Duy]

The struct declaration and implementation macros are moved to
commit-slab-hdr.h and commit-slab-impl.h respectively. This right now
is not needed for current users but if we share a commit-slab for
multiple files, we need something better than the current structure.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit-slab-hdr.h  |  30 ++++++++++++
 commit-slab-impl.h |  91 +++++++++++++++++++++++++++++++++++
 commit-slab.h      | 115 +++------------------------------------------
 3 files changed, 127 insertions(+), 109 deletions(-)
 create mode 100644 commit-slab-hdr.h
 create mode 100644 commit-slab-impl.h

diff --git a/commit-slab-hdr.h b/commit-slab-hdr.h
new file mode 100644
index 0000000000..fb5220fb7d
--- /dev/null
+++ b/commit-slab-hdr.h
@@ -0,0 +1,30 @@
+#ifndef COMMIT_SLAB_HDR_H
+#define COMMIT_SLAB_HDR_H
+
+/* allocate ~512kB at once, allowing for malloc overhead */
+#ifndef COMMIT_SLAB_SIZE
+#define COMMIT_SLAB_SIZE (512*1024-32)
+#endif
+
+#define declare_commit_slab(slabname, elemtype) 			\
+									\
+struct slabname {							\
+	unsigned slab_size;						\
+	unsigned stride;						\
+	unsigned slab_count;						\
+	elemtype **slab;						\
+}
+
+/*
+ * Statically initialize a commit slab named "var". Note that this
+ * evaluates "stride" multiple times! Example:
+ *
+ *   struct indegree indegrees = COMMIT_SLAB_INIT(1, indegrees);
+ *
+ */
+#define COMMIT_SLAB_INIT(stride, var) { \
+	COMMIT_SLAB_SIZE / sizeof(**((var).slab)) / (stride), \
+	(stride), 0, NULL \
+}
+
+#endif /* COMMIT_SLAB_HDR_H */
diff --git a/commit-slab-impl.h b/commit-slab-impl.h
new file mode 100644
index 0000000000..234d9ee5f0
--- /dev/null
+++ b/commit-slab-impl.h
@@ -0,0 +1,91 @@
+#ifndef COMMIT_SLAB_IMPL_H
+#define COMMIT_SLAB_IMPL_H
+
+#define MAYBE_UNUSED __attribute__((__unused__))
+
+#define implement_commit_slab(slabname, elemtype) 			\
+									\
+static int stat_ ##slabname## realloc;					\
+									\
+static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
+						   unsigned stride)	\
+{									\
+	unsigned int elem_size;						\
+	if (!stride)							\
+		stride = 1;						\
+	s->stride = stride;						\
+	elem_size = sizeof(elemtype) * stride;				\
+	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
+	s->slab_count = 0;						\
+	s->slab = NULL;							\
+}									\
+									\
+static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
+{									\
+	init_ ##slabname## _with_stride(s, 1);				\
+}									\
+									\
+static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
+{									\
+	unsigned int i;							\
+	for (i = 0; i < s->slab_count; i++)				\
+		free(s->slab[i]);					\
+	s->slab_count = 0;						\
+	FREE_AND_NULL(s->slab);						\
+}									\
+									\
+static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
+						  const struct commit *c, \
+						  int add_if_missing)   \
+{									\
+	unsigned int nth_slab, nth_slot;				\
+									\
+	nth_slab = c->index / s->slab_size;				\
+	nth_slot = c->index % s->slab_size;				\
+									\
+	if (s->slab_count <= nth_slab) {				\
+		unsigned int i;						\
+		if (!add_if_missing)					\
+			return NULL;					\
+		REALLOC_ARRAY(s->slab, nth_slab + 1);			\
+		stat_ ##slabname## realloc++;				\
+		for (i = s->slab_count; i <= nth_slab; i++)		\
+			s->slab[i] = NULL;				\
+		s->slab_count = nth_slab + 1;				\
+	}								\
+	if (!s->slab[nth_slab]) {					\
+		if (!add_if_missing)					\
+			return NULL;					\
+		s->slab[nth_slab] = xcalloc(s->slab_size,		\
+					    sizeof(**s->slab) * s->stride);		\
+	}								\
+	return &s->slab[nth_slab][nth_slot * s->stride];		\
+}									\
+									\
+static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
+					     const struct commit *c)	\
+{									\
+	return slabname##_at_peek(s, c, 1);				\
+}									\
+									\
+static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
+					     const struct commit *c)	\
+{									\
+	return slabname##_at_peek(s, c, 0);				\
+}									\
+									\
+struct slabname
+
+/*
+ * Note that this redundant forward declaration is required
+ * to allow a terminating semicolon, which makes instantiations look
+ * like function declarations.  I.e., the expansion of
+ *
+ *    implement_commit_slab(indegree, int);
+ *
+ * ends in 'struct indegree;'.  This would otherwise
+ * be a syntax error according (at least) to ISO C.  It's hard to
+ * catch because GCC silently parses it by default.
+ */
+
+#endif	/* COMMIT_SLAB_IMPL_H */
diff --git a/commit-slab.h b/commit-slab.h
index dcaab8ca04..204b928584 100644
--- a/commit-slab.h
+++ b/commit-slab.h
@@ -1,6 +1,9 @@
 #ifndef COMMIT_SLAB_H
 #define COMMIT_SLAB_H
 
+#include "commit-slab-hdr.h"
+#include "commit-slab-impl.h"
+
 /*
  * define_commit_slab(slabname, elemtype) creates boilerplate code to define
  * a new struct (struct slabname) that is used to associate a piece of data
@@ -41,114 +44,8 @@
  *   leaking memory.
  */
 
-/* allocate ~512kB at once, allowing for malloc overhead */
-#ifndef COMMIT_SLAB_SIZE
-#define COMMIT_SLAB_SIZE (512*1024-32)
-#endif
-
-#define MAYBE_UNUSED __attribute__((__unused__))
-
-#define define_commit_slab(slabname, elemtype) 				\
-									\
-struct slabname {							\
-	unsigned slab_size;						\
-	unsigned stride;						\
-	unsigned slab_count;						\
-	elemtype **slab;						\
-};									\
-static int stat_ ##slabname## realloc;					\
-									\
-static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
-						   unsigned stride)	\
-{									\
-	unsigned int elem_size;						\
-	if (!stride)							\
-		stride = 1;						\
-	s->stride = stride;						\
-	elem_size = sizeof(elemtype) * stride;				\
-	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
-	s->slab_count = 0;						\
-	s->slab = NULL;							\
-}									\
-									\
-static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
-{									\
-	init_ ##slabname## _with_stride(s, 1);				\
-}									\
-									\
-static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
-{									\
-	unsigned int i;							\
-	for (i = 0; i < s->slab_count; i++)				\
-		free(s->slab[i]);					\
-	s->slab_count = 0;						\
-	FREE_AND_NULL(s->slab);						\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
-						  const struct commit *c, \
-						  int add_if_missing)   \
-{									\
-	unsigned int nth_slab, nth_slot;				\
-									\
-	nth_slab = c->index / s->slab_size;				\
-	nth_slot = c->index % s->slab_size;				\
-									\
-	if (s->slab_count <= nth_slab) {				\
-		unsigned int i;						\
-		if (!add_if_missing)					\
-			return NULL;					\
-		REALLOC_ARRAY(s->slab, nth_slab + 1);			\
-		stat_ ##slabname## realloc++;				\
-		for (i = s->slab_count; i <= nth_slab; i++)		\
-			s->slab[i] = NULL;				\
-		s->slab_count = nth_slab + 1;				\
-	}								\
-	if (!s->slab[nth_slab]) {					\
-		if (!add_if_missing)					\
-			return NULL;					\
-		s->slab[nth_slab] = xcalloc(s->slab_size,		\
-					    sizeof(**s->slab) * s->stride);		\
-	}								\
-	return &s->slab[nth_slab][nth_slot * s->stride];		\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
-					     const struct commit *c)	\
-{									\
-	return slabname##_at_peek(s, c, 1);				\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
-					     const struct commit *c)	\
-{									\
-	return slabname##_at_peek(s, c, 0);				\
-}									\
-									\
-struct slabname
-
-/*
- * Note that this redundant forward declaration is required
- * to allow a terminating semicolon, which makes instantiations look
- * like function declarations.  I.e., the expansion of
- *
- *    define_commit_slab(indegree, int);
- *
- * ends in 'struct indegree;'.  This would otherwise
- * be a syntax error according (at least) to ISO C.  It's hard to
- * catch because GCC silently parses it by default.
- */
-
-/*
- * Statically initialize a commit slab named "var". Note that this
- * evaluates "stride" multiple times! Example:
- *
- *   struct indegree indegrees = COMMIT_SLAB_INIT(1, indegrees);
- *
- */
-#define COMMIT_SLAB_INIT(stride, var) { \
-	COMMIT_SLAB_SIZE / sizeof(**((var).slab)) / (stride), \
-	(stride), 0, NULL \
-}
+#define define_commit_slab(slabname, elemtype) \
+	declare_commit_slab(slabname, elemtype); \
+	implement_commit_slab(slabname, elemtype)
 
 #endif /* COMMIT_SLAB_H */
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 01/14] commit-slab.h: code split

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> The struct declaration and implementation macros are moved to
> commit-slab-hdr.h and commit-slab-impl.h respectively. This right now
> is not needed for current users but if we share a commit-slab for
> multiple files, we need something better than the current structure.

"something better" needs to be replaced with something better for it
to be worth being there.  In other words, say why you want to avoid
including the part you moved to *-impl.h everywhere.

I also think you want to rename s/-hdr.h/-decl.h/ or something to
avoid sounding silly by repeating "header" twice in the name.

> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  commit-slab-hdr.h  |  30 ++++++++++++
>  commit-slab-impl.h |  91 +++++++++++++++++++++++++++++++++++
>  commit-slab.h      | 115 +++------------------------------------------
>  3 files changed, 127 insertions(+), 109 deletions(-)
>  create mode 100644 commit-slab-hdr.h
>  create mode 100644 commit-slab-impl.h

"git blame" tells me that the new two files consist mostly of the
material from commit-slab.h moved verbatim, which is assuring ;-).

[PATCH v2 02/14] commit-slab: support shared commit-slab

[Nguyễn Thái Ngọc Duy]

define_shared_commit_slab() could be used in a header file to define a
commit-slab. One of these C files must include commit-slab-impl.h and
"call" implement_shared_commit_slab().

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit-slab-hdr.h  | 13 +++++++++++++
 commit-slab-impl.h | 20 +++++++++++++-------
 commit-slab.h      |  2 +-
 3 files changed, 27 insertions(+), 8 deletions(-)

diff --git a/commit-slab-hdr.h b/commit-slab-hdr.h
index fb5220fb7d..adc7b46c83 100644
--- a/commit-slab-hdr.h
+++ b/commit-slab-hdr.h
@@ -27,4 +27,17 @@ struct slabname {							\
 	(stride), 0, NULL \
 }
 
+#define declare_commit_slab_prototypes(slabname, elemtype)		\
+									\
+void init_ ##slabname## _with_stride(struct slabname *s, unsigned stride); \
+void init_ ##slabname(struct slabname *s);				\
+void clear_ ##slabname(struct slabname *s);				\
+elemtype *slabname## _at_peek(struct slabname *s, const struct commit *c, int add_if_missing); \
+elemtype *slabname## _at(struct slabname *s, const struct commit *c);	\
+elemtype *slabname## _peek(struct slabname *s, const struct commit *c)
+
+#define define_shared_commit_slab(slabname, elemtype) \
+	declare_commit_slab(slabname, elemtype); \
+	declare_commit_slab_prototypes(slabname, elemtype)
+
 #endif /* COMMIT_SLAB_HDR_H */
diff --git a/commit-slab-impl.h b/commit-slab-impl.h
index 234d9ee5f0..19a88d7d8f 100644
--- a/commit-slab-impl.h
+++ b/commit-slab-impl.h
@@ -3,11 +3,17 @@
 
 #define MAYBE_UNUSED __attribute__((__unused__))
 
-#define implement_commit_slab(slabname, elemtype) 			\
+#define implement_static_commit_slab(slabname, elemtype) \
+	implement_commit_slab(slabname, elemtype, static MAYBE_UNUSED)
+
+#define implement_shared_commit_slab(slabname, elemtype) \
+	implement_commit_slab(slabname, elemtype, )
+
+#define implement_commit_slab(slabname, elemtype, scope)		\
 									\
 static int stat_ ##slabname## realloc;					\
 									\
-static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
+scope void init_ ##slabname## _with_stride(struct slabname *s,		\
 						   unsigned stride)	\
 {									\
 	unsigned int elem_size;						\
@@ -20,12 +26,12 @@ static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
 	s->slab = NULL;							\
 }									\
 									\
-static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
+scope void init_ ##slabname(struct slabname *s)				\
 {									\
 	init_ ##slabname## _with_stride(s, 1);				\
 }									\
 									\
-static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
+scope void clear_ ##slabname(struct slabname *s)			\
 {									\
 	unsigned int i;							\
 	for (i = 0; i < s->slab_count; i++)				\
@@ -34,7 +40,7 @@ static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
 	FREE_AND_NULL(s->slab);						\
 }									\
 									\
-static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
+scope elemtype *slabname## _at_peek(struct slabname *s,			\
 						  const struct commit *c, \
 						  int add_if_missing)   \
 {									\
@@ -62,13 +68,13 @@ static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
 	return &s->slab[nth_slab][nth_slot * s->stride];		\
 }									\
 									\
-static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
+scope elemtype *slabname## _at(struct slabname *s,			\
 					     const struct commit *c)	\
 {									\
 	return slabname##_at_peek(s, c, 1);				\
 }									\
 									\
-static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
+scope elemtype *slabname## _peek(struct slabname *s,			\
 					     const struct commit *c)	\
 {									\
 	return slabname##_at_peek(s, c, 0);				\
diff --git a/commit-slab.h b/commit-slab.h
index 204b928584..dc029acc66 100644
--- a/commit-slab.h
+++ b/commit-slab.h
@@ -46,6 +46,6 @@
 
 #define define_commit_slab(slabname, elemtype) \
 	declare_commit_slab(slabname, elemtype); \
-	implement_commit_slab(slabname, elemtype)
+	implement_static_commit_slab(slabname, elemtype)
 
 #endif /* COMMIT_SLAB_H */
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 02/14] commit-slab: support shared commit-slab

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> define_shared_commit_slab() could be used in a header file to define a
> commit-slab. One of these C files must include commit-slab-impl.h and
> "call" implement_shared_commit_slab().
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  commit-slab-hdr.h  | 13 +++++++++++++
>  commit-slab-impl.h | 20 +++++++++++++-------
>  commit-slab.h      |  2 +-
>  3 files changed, 27 insertions(+), 8 deletions(-)

This, while it is a reasonable change, makes the big comment at the
end of commit-slab-impl.h out of sync with the reality, doesn't it?
implement_commit_slab() now takes three args, but the comment still
says the caller does not have to give the third one.

[PATCH v2 03/14] blame: use commit-slab for blame suspects instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 blame.c         | 42 +++++++++++++++++++++++++++++++-----------
 blame.h         |  2 ++
 builtin/blame.c |  2 +-
 3 files changed, 34 insertions(+), 12 deletions(-)

diff --git a/blame.c b/blame.c
index 78c9808bd1..18e8bd996a 100644
--- a/blame.c
+++ b/blame.c
@@ -6,6 +6,24 @@
 #include "diffcore.h"
 #include "tag.h"
 #include "blame.h"
+#include "commit-slab.h"
+
+define_commit_slab(blame_suspects, struct blame_origin *);
+static struct blame_suspects blame_suspects;
+
+struct blame_origin *get_blame_suspects(struct commit *commit)
+{
+	struct blame_origin **result;
+
+	result = blame_suspects_peek(&blame_suspects, commit);
+
+	return result ? *result : NULL;
+}
+
+static void set_blame_suspects(struct commit *commit, struct blame_origin *origin)
+{
+	*blame_suspects_at(&blame_suspects, commit) = origin;
+}
 
 void blame_origin_decref(struct blame_origin *o)
 {
@@ -15,12 +33,12 @@ void blame_origin_decref(struct blame_origin *o)
 			blame_origin_decref(o->previous);
 		free(o->file.ptr);
 		/* Should be present exactly once in commit chain */
-		for (p = o->commit->util; p; l = p, p = p->next) {
+		for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) {
 			if (p == o) {
 				if (l)
 					l->next = p->next;
 				else
-					o->commit->util = p->next;
+					set_blame_suspects(o->commit, p->next);
 				free(o);
 				return;
 			}
@@ -41,8 +59,8 @@ static struct blame_origin *make_origin(struct commit *commit, const char *path)
 	FLEX_ALLOC_STR(o, path, path);
 	o->commit = commit;
 	o->refcnt = 1;
-	o->next = commit->util;
-	commit->util = o;
+	o->next = get_blame_suspects(commit);
+	set_blame_suspects(commit, o);
 	return o;
 }
 
@@ -54,13 +72,13 @@ static struct blame_origin *get_origin(struct commit *commit, const char *path)
 {
 	struct blame_origin *o, *l;
 
-	for (o = commit->util, l = NULL; o; l = o, o = o->next) {
+	for (o = get_blame_suspects(commit), l = NULL; o; l = o, o = o->next) {
 		if (!strcmp(o->path, path)) {
 			/* bump to front */
 			if (l) {
 				l->next = o->next;
-				o->next = commit->util;
-				commit->util = o;
+				o->next = get_blame_suspects(commit);
+				set_blame_suspects(commit, o);
 			}
 			return blame_origin_incref(o);
 		}
@@ -478,7 +496,7 @@ static void queue_blames(struct blame_scoreboard *sb, struct blame_origin *porig
 		porigin->suspects = blame_merge(porigin->suspects, sorted);
 	else {
 		struct blame_origin *o;
-		for (o = porigin->commit->util; o; o = o->next) {
+		for (o = get_blame_suspects(porigin->commit); o; o = o->next) {
 			if (o->suspects) {
 				porigin->suspects = sorted;
 				return;
@@ -525,7 +543,7 @@ static struct blame_origin *find_origin(struct commit *parent,
 	const char *paths[2];
 
 	/* First check any existing origins */
-	for (porigin = parent->util; porigin; porigin = porigin->next)
+	for (porigin = get_blame_suspects(parent); porigin; porigin = porigin->next)
 		if (!strcmp(porigin->path, origin->path)) {
 			/*
 			 * The same path between origin and its parent
@@ -1550,7 +1568,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)
 
 	while (commit) {
 		struct blame_entry *ent;
-		struct blame_origin *suspect = commit->util;
+		struct blame_origin *suspect = get_blame_suspects(commit);
 
 		/* find one suspect to break down */
 		while (suspect && !suspect->suspects)
@@ -1752,6 +1770,8 @@ void setup_scoreboard(struct blame_scoreboard *sb, const char *path, struct blam
 	struct commit *final_commit = NULL;
 	enum object_type type;
 
+	init_blame_suspects(&blame_suspects);
+
 	if (sb->reverse && sb->contents_from)
 		die(_("--contents and --reverse do not blend well."));
 
@@ -1815,7 +1835,7 @@ void setup_scoreboard(struct blame_scoreboard *sb, const char *path, struct blam
 	}
 
 	if (is_null_oid(&sb->final->object.oid)) {
-		o = sb->final->util;
+		o = get_blame_suspects(sb->final);
 		sb->final_buf = xmemdupz(o->file.ptr, o->file.size);
 		sb->final_buf_size = o->file.size;
 	}
diff --git a/blame.h b/blame.h
index a6c915c277..2092f9529c 100644
--- a/blame.h
+++ b/blame.h
@@ -172,4 +172,6 @@ extern void setup_scoreboard(struct blame_scoreboard *sb, const char *path, stru
 
 extern struct blame_entry *blame_entry_prepend(struct blame_entry *head, long start, long end, struct blame_origin *o);
 
+extern struct blame_origin *get_blame_suspects(struct commit *commit);
+
 #endif /* BLAME_H */
diff --git a/builtin/blame.c b/builtin/blame.c
index db38c0b307..969572810d 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -457,7 +457,7 @@ static void output(struct blame_scoreboard *sb, int option)
 			struct commit *commit = ent->suspect->commit;
 			if (commit->object.flags & MORE_THAN_ONE_PATH)
 				continue;
-			for (suspect = commit->util; suspect; suspect = suspect->next) {
+			for (suspect = get_blame_suspects(commit); suspect; suspect = suspect->next) {
 				if (suspect->guilty && count++) {
 					commit->object.flags |= MORE_THAN_ONE_PATH;
 					break;
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 03/14] blame: use commit-slab for blame suspects instead of commit->util

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> It's done so that commit->util can be removed. See more explanation in
> the commit that removes commit->util.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  blame.c         | 42 +++++++++++++++++++++++++++++++-----------
>  blame.h         |  2 ++
>  builtin/blame.c |  2 +-
>  3 files changed, 34 insertions(+), 12 deletions(-)
>
> diff --git a/blame.c b/blame.c
> index 78c9808bd1..18e8bd996a 100644
> --- a/blame.c
> +++ b/blame.c
> @@ -6,6 +6,24 @@
>  #include "diffcore.h"
>  #include "tag.h"
>  #include "blame.h"
> +#include "commit-slab.h"
> +
> +define_commit_slab(blame_suspects, struct blame_origin *);
> +static struct blame_suspects blame_suspects;
> +
> +struct blame_origin *get_blame_suspects(struct commit *commit)
> +{
> +	struct blame_origin **result;
> +
> +	result = blame_suspects_peek(&blame_suspects, commit);
> +
> +	return result ? *result : NULL;
> +}
> +
> +static void set_blame_suspects(struct commit *commit, struct blame_origin *origin)
> +{
> +	*blame_suspects_at(&blame_suspects, commit) = origin;
> +}
>  
>  void blame_origin_decref(struct blame_origin *o)
>  {

This makes really a pleasant read.  With these helpers in place, the
remainder of this patch becomes mechanical substitution to call
get_blame_suspects when commit->util appears on the RHS of an
expression and set_blame_suspects when commit->util gets assigned.

> @@ -15,12 +33,12 @@ void blame_origin_decref(struct blame_origin *o)
>  			blame_origin_decref(o->previous);
>  		free(o->file.ptr);
>  		/* Should be present exactly once in commit chain */
> -		for (p = o->commit->util; p; l = p, p = p->next) {
> +		for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) {
>  			if (p == o) {
>  				if (l)
>  					l->next = p->next;
>  				else
> -					o->commit->util = p->next;
> +					set_blame_suspects(o->commit, p->next);
>  				free(o);
>  				return;
>  			}

[PATCH v2 04/14] describe: use commit-slab for commit names instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/describe.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index b5afc45846..1b6ca42553 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -15,9 +15,12 @@
 #include "run-command.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "commit-slab.h"
 
 #define MAX_TAGS	(FLAG_BITS - 1)
 
+define_commit_slab(commit_names, struct commit_name *);
+
 static const char * const describe_usage[] = {
 	N_("git describe [<options>] [<commit-ish>...]"),
 	N_("git describe [<options>] --dirty"),
@@ -37,6 +40,7 @@ static struct string_list patterns = STRING_LIST_INIT_NODUP;
 static struct string_list exclude_patterns = STRING_LIST_INIT_NODUP;
 static int always;
 static const char *suffix, *dirty, *broken;
+static struct commit_names commit_names;
 
 /* diff-index command arguments to check if working tree is dirty. */
 static const char *diff_index_args[] = {
@@ -321,11 +325,14 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	if (!have_util) {
 		struct hashmap_iter iter;
 		struct commit *c;
-		struct commit_name *n = hashmap_iter_first(&names, &iter);
+		struct commit_name *n;
+
+		init_commit_names(&commit_names);
+		n = hashmap_iter_first(&names, &iter);
 		for (; n; n = hashmap_iter_next(&iter)) {
 			c = lookup_commit_reference_gently(&n->peeled, 1);
 			if (c)
-				c->util = n;
+				*commit_names_at(&commit_names, c) = n;
 		}
 		have_util = 1;
 	}
@@ -336,8 +343,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	while (list) {
 		struct commit *c = pop_commit(&list);
 		struct commit_list *parents = c->parents;
+		struct commit_name **slot;
+
 		seen_commits++;
-		n = c->util;
+		slot = commit_names_peek(&commit_names, c);
+		n = slot ? *slot : NULL;
 		if (n) {
 			if (!tags && !all && n->prio < 2) {
 				unannotated_cnt++;
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 04/14] describe: use commit-slab for commit names instead of commit->util

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> +		slot = commit_names_peek(&commit_names, c);
> +		n = slot ? *slot : NULL;

Seeing this and the helper in the previous step makes me wonder if
we also want a "peek-and-then-peel" variant that encapsulates this
pattern.  We'll know when we read the series through.

So far looking good.  Thanks.

>  		if (n) {
>  			if (!tags && !all && n->prio < 2) {
>  				unannotated_cnt++;

[PATCH v2 05/14] shallow.c: use commit-slab for commit depth instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

While at there, plug a leak for keeping track of depth in this code.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 shallow.c | 41 +++++++++++++++++++++++++++++------------
 1 file changed, 29 insertions(+), 12 deletions(-)

diff --git a/shallow.c b/shallow.c
index df4d44ea7a..daf60a9391 100644
--- a/shallow.c
+++ b/shallow.c
@@ -12,6 +12,7 @@
 #include "commit-slab.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "commit-slab.h"
 
 static int is_shallow = -1;
 static struct stat_validity shallow_stat;
@@ -74,6 +75,11 @@ int is_repository_shallow(void)
 	return is_shallow;
 }
 
+/*
+ * TODO: use "int" elemtype instead of "int *" when/if commit-slab
+ * supports a "valid" flag.
+ */
+define_commit_slab(commit_depth, int *);
 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		int shallow_flag, int not_shallow_flag)
 {
@@ -82,25 +88,29 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 	struct object_array stack = OBJECT_ARRAY_INIT;
 	struct commit *commit = NULL;
 	struct commit_graft *graft;
+	struct commit_depth depths;
 
+	init_commit_depth(&depths);
 	while (commit || i < heads->nr || stack.nr) {
 		struct commit_list *p;
 		if (!commit) {
 			if (i < heads->nr) {
+				int **depth_slot;
 				commit = (struct commit *)
 					deref_tag(heads->objects[i++].item, NULL, 0);
 				if (!commit || commit->object.type != OBJ_COMMIT) {
 					commit = NULL;
 					continue;
 				}
-				if (!commit->util)
-					commit->util = xmalloc(sizeof(int));
-				*(int *)commit->util = 0;
+				depth_slot = commit_depth_at(&depths, commit);
+				if (!*depth_slot)
+					*depth_slot = xmalloc(sizeof(int));
+				**depth_slot = 0;
 				cur_depth = 0;
 			} else {
 				commit = (struct commit *)
 					object_array_pop(&stack);
-				cur_depth = *(int *)commit->util;
+				cur_depth = **commit_depth_peek(&depths, commit);
 			}
 		}
 		parse_commit_or_die(commit);
@@ -116,25 +126,32 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		}
 		commit->object.flags |= not_shallow_flag;
 		for (p = commit->parents, commit = NULL; p; p = p->next) {
-			if (!p->item->util) {
-				int *pointer = xmalloc(sizeof(int));
-				p->item->util = pointer;
-				*pointer =  cur_depth;
+			int **depth_slot = commit_depth_at(&depths, p->item);
+			if (!*depth_slot) {
+				*depth_slot = xmalloc(sizeof(int));
+				**depth_slot = cur_depth;
 			} else {
-				int *pointer = p->item->util;
-				if (cur_depth >= *pointer)
+				if (cur_depth >= **depth_slot)
 					continue;
-				*pointer = cur_depth;
+				**depth_slot = cur_depth;
 			}
 			if (p->next)
 				add_object_array(&p->item->object,
 						NULL, &stack);
 			else {
 				commit = p->item;
-				cur_depth = *(int *)commit->util;
+				depth_slot = commit_depth_peek(&depths, commit);
+				cur_depth = **depth_slot;
 			}
 		}
 	}
+	for (i = 0; i < depths.slab_count; i++) {
+		int j;
+
+		for (j = 0; j < depths.slab_size; j++)
+			free(depths.slab[i][j]);
+	}
+	clear_commit_depth(&depths);
 
 	return result;
 }
-- 
2.17.0.705.g3525833791

[PATCH v2 06/14] sequencer.c: use commit-slab to mark seen commits

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 sequencer.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index 4ce5120e77..6b785c6c5f 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -23,6 +23,7 @@
 #include "hashmap.h"
 #include "notes-utils.h"
 #include "sigchain.h"
+#include "commit-slab.h"
 
 #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
 
@@ -3160,6 +3161,7 @@ static enum check_level get_missing_commit_check_level(void)
 	return CHECK_IGNORE;
 }
 
+define_commit_slab(commit_seen, uint8_t);
 /*
  * Check if the user dropped some commits by mistake
  * Behaviour determined by rebase.missingCommitsCheck.
@@ -3173,6 +3175,9 @@ int check_todo_list(void)
 	struct todo_list todo_list = TODO_LIST_INIT;
 	struct strbuf missing = STRBUF_INIT;
 	int advise_to_edit_todo = 0, res = 0, i;
+	struct commit_seen commit_seen;
+
+	init_commit_seen(&commit_seen);
 
 	strbuf_addstr(&todo_file, rebase_path_todo());
 	if (strbuf_read_file_or_whine(&todo_list.buf, todo_file.buf) < 0) {
@@ -3189,7 +3194,7 @@ int check_todo_list(void)
 	for (i = 0; i < todo_list.nr; i++) {
 		struct commit *commit = todo_list.items[i].commit;
 		if (commit)
-			commit->util = (void *)1;
+			*commit_seen_at(&commit_seen, commit) = 1;
 	}
 
 	todo_list_release(&todo_list);
@@ -3205,11 +3210,11 @@ int check_todo_list(void)
 	for (i = todo_list.nr - 1; i >= 0; i--) {
 		struct todo_item *item = todo_list.items + i;
 		struct commit *commit = item->commit;
-		if (commit && !commit->util) {
+		if (commit && !*commit_seen_at(&commit_seen, commit)) {
 			strbuf_addf(&missing, " - %s %.*s\n",
 				    short_commit_name(commit),
 				    item->arg_len, item->arg);
-			commit->util = (void *)1;
+			*commit_seen_at(&commit_seen, commit) = 1;
 		}
 	}
 
@@ -3235,6 +3240,7 @@ int check_todo_list(void)
 		"The possible behaviours are: ignore, warn, error.\n\n"));
 
 leave_check:
+	clear_commit_seen(&commit_seen);
 	strbuf_release(&todo_file);
 	todo_list_release(&todo_list);
 
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 06/14] sequencer.c: use commit-slab to mark seen commits

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> It's done so that commit->util can be removed. See more explanation in
> the commit that removes commit->util.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  sequencer.c | 12 +++++++++---
>  1 file changed, 9 insertions(+), 3 deletions(-)
>
> diff --git a/sequencer.c b/sequencer.c
> index 4ce5120e77..6b785c6c5f 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -23,6 +23,7 @@
>  #include "hashmap.h"
>  #include "notes-utils.h"
>  #include "sigchain.h"
> +#include "commit-slab.h"
>  
>  #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
>  
> @@ -3160,6 +3161,7 @@ static enum check_level get_missing_commit_check_level(void)
>  	return CHECK_IGNORE;
>  }
>  
> +define_commit_slab(commit_seen, uint8_t);

Because it makes no difference on any real platform that matters, it
is purely academic preference, but the user of this code does not
care about ensuring that commit-seen data is at lesat 8-bit wide,
which is where we should use uint8_t.  We know this is a simple
yes/no field, so use of "uint8_t" here is quite misleading to the
readers.  "unsigned char" or "char" would be a lot better.

[PATCH v2 07/14] sequencer.c: use commit-slab to associate todo items to commits

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 sequencer.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index 6b785c6c5f..dd4993fd99 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -3362,6 +3362,8 @@ static int subject2item_cmp(const void *fndata,
 	return key ? strcmp(a->subject, key) : strcmp(a->subject, b->subject);
 }
 
+define_commit_slab(commit_todo_item, struct todo_item *);
+
 /*
  * Rearrange the todo list that has both "pick commit-id msg" and "pick
  * commit-id fixup!/squash! msg" in it so that the latter is put immediately
@@ -3378,6 +3380,7 @@ int rearrange_squash(void)
 	struct hashmap subject2item;
 	int res = 0, rearranged = 0, *next, *tail, i;
 	char **subjects;
+	struct commit_todo_item commit_todo;
 
 	if (strbuf_read_file_or_whine(&todo_list.buf, todo_file) < 0)
 		return -1;
@@ -3386,6 +3389,7 @@ int rearrange_squash(void)
 		return -1;
 	}
 
+	init_commit_todo_item(&commit_todo);
 	/*
 	 * The hashmap maps onelines to the respective todo list index.
 	 *
@@ -3416,10 +3420,11 @@ int rearrange_squash(void)
 
 		if (is_fixup(item->command)) {
 			todo_list_release(&todo_list);
+			clear_commit_todo_item(&commit_todo);
 			return error(_("the script was already rearranged."));
 		}
 
-		item->commit->util = item;
+		*commit_todo_item_at(&commit_todo, item->commit) = item;
 
 		parse_commit(item->commit);
 		commit_buffer = get_commit_buffer(item->commit, NULL);
@@ -3446,9 +3451,9 @@ int rearrange_squash(void)
 			else if (!strchr(p, ' ') &&
 				 (commit2 =
 				  lookup_commit_reference_by_name(p)) &&
-				 commit2->util)
+				 *commit_todo_item_at(&commit_todo, commit2))
 				/* found by commit name */
-				i2 = (struct todo_item *)commit2->util
+				i2 = *commit_todo_item_at(&commit_todo, commit2)
 					- todo_list.items;
 			else {
 				/* copy can be a prefix of the commit subject */
@@ -3527,5 +3532,6 @@ int rearrange_squash(void)
 	hashmap_free(&subject2item, 1);
 	todo_list_release(&todo_list);
 
+	clear_commit_todo_item(&commit_todo);
 	return res;
 }
-- 
2.17.0.705.g3525833791

[PATCH v2 08/14] revision.c: use commit-slab for show_source

[Nguyễn Thái Ngọc Duy]

Instead of relying on commit->util to store the source string, let the
user provide a commit-slab to store the source strings in.

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/fast-export.c | 14 +++++++++-----
 builtin/log.c         |  7 +++++--
 log-tree.c            |  8 ++++++--
 revision.c            | 19 +++++++++++++++----
 revision.h            |  5 ++++-
 5 files changed, 39 insertions(+), 14 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 530df12f05..b08e5ea0e3 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -21,6 +21,7 @@
 #include "quote.h"
 #include "remote.h"
 #include "blob.h"
+#include "commit-slab.h"
 
 static const char *fast_export_usage[] = {
 	N_("git fast-export [rev-list-opts]"),
@@ -38,6 +39,7 @@ static struct string_list extra_refs = STRING_LIST_INIT_NODUP;
 static struct refspec *refspecs;
 static int refspecs_nr;
 static int anonymize;
+static struct revision_sources revision_sources;
 
 static int parse_opt_signed_tag_mode(const struct option *opt,
 				     const char *arg, int unset)
@@ -590,7 +592,7 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,
 		if (!S_ISGITLINK(diff_queued_diff.queue[i]->two->mode))
 			export_blob(&diff_queued_diff.queue[i]->two->oid);
 
-	refname = commit->util;
+	refname = *revision_sources_peek(&revision_sources, commit);
 	if (anonymize) {
 		refname = anonymize_refname(refname);
 		anonymize_ident_line(&committer, &committer_end);
@@ -862,10 +864,11 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)
 		 * This ref will not be updated through a commit, lets make
 		 * sure it gets properly updated eventually.
 		 */
-		if (commit->util || commit->object.flags & SHOWN)
+		if (*revision_sources_at(&revision_sources, commit) ||
+		    commit->object.flags & SHOWN)
 			string_list_append(&extra_refs, full_name)->util = commit;
-		if (!commit->util)
-			commit->util = full_name;
+		if (!*revision_sources_at(&revision_sources, commit))
+			*revision_sources_at(&revision_sources, commit) = full_name;
 	}
 }
 
@@ -1029,8 +1032,9 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
 	git_config(git_default_config, NULL);
 
 	init_revisions(&revs, prefix);
+	init_revision_sources(&revision_sources);
 	revs.topo_order = 1;
-	revs.show_source = 1;
+	revs.sources = &revision_sources;
 	revs.rewrite_parents = 1;
 	argc = parse_options(argc, argv, prefix, options, fast_export_usage,
 			PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN);
diff --git a/builtin/log.c b/builtin/log.c
index 71f68a3e4f..d017e57475 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -148,6 +148,7 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	static struct string_list decorate_refs_include = STRING_LIST_INIT_NODUP;
 	struct decoration_filter decoration_filter = {&decorate_refs_include,
 						      &decorate_refs_exclude};
+	static struct revision_sources revision_sources;
 
 	const struct option builtin_log_options[] = {
 		OPT__QUIET(&quiet, N_("suppress diff output")),
@@ -194,8 +195,10 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	    rev->diffopt.filter || rev->diffopt.flags.follow_renames)
 		rev->always_show_header = 0;
 
-	if (source)
-		rev->show_source = 1;
+	if (source) {
+		init_revision_sources(&revision_sources);
+		rev->sources = &revision_sources;
+	}
 
 	if (mailmap) {
 		rev->mailmap = xcalloc(1, sizeof(struct string_list));
diff --git a/log-tree.c b/log-tree.c
index d1c0bedf24..0b41ee3235 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -295,8 +295,12 @@ void show_decorations(struct rev_info *opt, struct commit *commit)
 {
 	struct strbuf sb = STRBUF_INIT;
 
-	if (opt->show_source && commit->util)
-		fprintf(opt->diffopt.file, "\t%s", (char *) commit->util);
+	if (opt->sources) {
+		char **slot = revision_sources_peek(opt->sources, commit);
+
+		if (slot && *slot)
+			fprintf(opt->diffopt.file, "\t%s", *slot);
+	}
 	if (!opt->show_decorations)
 		return;
 	format_decorations(&sb, commit, opt->diffopt.use_color);
diff --git a/revision.c b/revision.c
index 1cff11833e..be8fe7d67b 100644
--- a/revision.c
+++ b/revision.c
@@ -29,6 +29,8 @@ volatile show_early_output_fn_t show_early_output;
 static const char *term_bad;
 static const char *term_good;
 
+implement_shared_commit_slab(revision_sources, char *);
+
 void show_object_with_name(FILE *out, struct object *obj, const char *name)
 {
 	const char *p;
@@ -255,14 +257,19 @@ static struct commit *handle_commit(struct rev_info *revs,
 	 */
 	if (object->type == OBJ_COMMIT) {
 		struct commit *commit = (struct commit *)object;
+
 		if (parse_commit(commit) < 0)
 			die("unable to parse commit %s", name);
 		if (flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
 			revs->limited = 1;
 		}
-		if (revs->show_source && !commit->util)
-			commit->util = xstrdup(name);
+		if (revs->sources) {
+			char **slot = revision_sources_at(revs->sources, commit);
+
+			if (!*slot)
+				*slot = xstrdup(name);
+		}
 		return commit;
 	}
 
@@ -814,8 +821,12 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			}
 			return -1;
 		}
-		if (revs->show_source && !p->util)
-			p->util = commit->util;
+		if (revs->sources) {
+			char **slot = revision_sources_at(revs->sources, p);
+
+			if (!*slot)
+				*slot = *revision_sources_at(revs->sources, commit);
+		}
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
 			p->object.flags |= SEEN;
diff --git a/revision.h b/revision.h
index b8c47b98e2..f3dc5f9740 100644
--- a/revision.h
+++ b/revision.h
@@ -6,6 +6,7 @@
 #include "notes.h"
 #include "pretty.h"
 #include "diff.h"
+#include "commit-slab-hdr.h"
 
 /* Remember to update object flag allocation in object.h */
 #define SEEN		(1u<<0)
@@ -29,6 +30,7 @@ struct rev_info;
 struct log_info;
 struct string_list;
 struct saved_parents;
+define_shared_commit_slab(revision_sources, char *);
 
 struct rev_cmdline_info {
 	unsigned int nr;
@@ -111,7 +113,6 @@ struct rev_info {
 			right_only:1,
 			rewrite_parents:1,
 			print_parents:1,
-			show_source:1,
 			show_decorations:1,
 			reverse:1,
 			reverse_output_stage:1,
@@ -224,6 +225,8 @@ struct rev_info {
 
 	struct commit_list *previous_parents;
 	const char *break_bar;
+
+	struct revision_sources *sources;
 };
 
 extern int ref_excluded(struct string_list *, const char *path);
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 08/14] revision.c: use commit-slab for show_source

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> -	refname = commit->util;
> +	refname = *revision_sources_peek(&revision_sources, commit);

At first glance, I thought that the reason why this uses _peek() is
because the "sources" is expected to only sparsely be populated,
perhaps because get_tags_and_duplicates() annotates only the tips
mentioned on the command line via rev_cmdline mechanism and this
code does not want to auto-vivify the slot, only to read NULL from
it.

But the code that follows this point liberally uses refname without
checking if it is NULL, so I am not quite sure what is going on. In
any case, wouldn't *slab_peek() an anti-pattern?  You use _peek()
because you expect that a slot is not yet allocated for a commit,
you desire not to vivify all the slots for all the commits, and
instead you are prepared to see a NULL returned from the call.  But
I do not think that is what is happening here, so shouldn't it be
using _at() instead of _peek()?

>  	if (anonymize) {
>  		refname = anonymize_refname(refname);

>  		anonymize_ident_line(&committer, &committer_end);
> @@ -862,10 +864,11 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)
>  		 * This ref will not be updated through a commit, lets make
>  		 * sure it gets properly updated eventually.
>  		 */
> -		if (commit->util || commit->object.flags & SHOWN)
> +		if (*revision_sources_at(&revision_sources, commit) ||
> +		    commit->object.flags & SHOWN)

Here it uses *slab_at() which makes more sense.

Re: [PATCH v2 08/14] revision.c: use commit-slab for show_source

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> -	refname = commit->util;
>> +	refname = *revision_sources_peek(&revision_sources, commit);
>
> At first glance, I thought that the reason why this uses _peek() is
> because the "sources" is expected to only sparsely be populated,
> perhaps because get_tags_and_duplicates() annotates only the tips
> mentioned on the command line via rev_cmdline mechanism and this
> code does not want to auto-vivify the slot, only to read NULL from
> it.
>
> But the code that follows this point liberally uses refname without
> checking if it is NULL, so I am not quite sure what is going on.

Ah, of course, this is about the code that propagates the "source"
(i.e. from which tip given on the command line did we start the
traversal to reach this commit?), so that is what ensures there is
something in commit->util and revision_sources not just has an entry
for the commit but the entry should have a non-NULL string.

So shouldn't *slab_peek() here be *slab_at() instead?

> In
> any case, wouldn't *slab_peek() an anti-pattern?  You use _peek()
> because you expect that a slot is not yet allocated for a commit,
> you desire not to vivify all the slots for all the commits, and
> instead you are prepared to see a NULL returned from the call.  But
> I do not think that is what is happening here, so shouldn't it be
> using _at() instead of _peek()?
>
>>  	if (anonymize) {
>>  		refname = anonymize_refname(refname);
>
>>  		anonymize_ident_line(&committer, &committer_end);
>> @@ -862,10 +864,11 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)
>>  		 * This ref will not be updated through a commit, lets make
>>  		 * sure it gets properly updated eventually.
>>  		 */
>> -		if (commit->util || commit->object.flags & SHOWN)
>> +		if (*revision_sources_at(&revision_sources, commit) ||
>> +		    commit->object.flags & SHOWN)
>
> Here it uses *slab_at() which makes more sense.

[PATCH v2 09/14] bisect.c: use commit-slab for commit weight instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 bisect.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/bisect.c b/bisect.c
index a579b50884..6de1abd407 100644
--- a/bisect.c
+++ b/bisect.c
@@ -12,6 +12,7 @@
 #include "bisect.h"
 #include "sha1-array.h"
 #include "argv-array.h"
+#include "commit-slab.h"
 
 static struct oid_array good_revs;
 static struct oid_array skipped_revs;
@@ -70,16 +71,19 @@ static void clear_distance(struct commit_list *list)
 	}
 }
 
+define_commit_slab(commit_weight, int *);
+static struct commit_weight commit_weight;
+
 #define DEBUG_BISECT 0
 
 static inline int weight(struct commit_list *elem)
 {
-	return *((int*)(elem->item->util));
+	return **commit_weight_at(&commit_weight, elem->item);
 }
 
 static inline void weight_set(struct commit_list *elem, int weight)
 {
-	*((int*)(elem->item->util)) = weight;
+	**commit_weight_at(&commit_weight, elem->item) = weight;
 }
 
 static int count_interesting_parents(struct commit *commit)
@@ -265,7 +269,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
 
-		p->item->util = &weights[n++];
+		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
 		switch (count_interesting_parents(commit)) {
 		case 0:
 			if (!(flags & TREESAME)) {
@@ -372,6 +376,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	int *weights;
 
 	show_list("bisection 2 entry", 0, 0, *commit_list);
+	init_commit_weight(&commit_weight);
 
 	/*
 	 * Count the number of total and tree-changing items on the
@@ -412,6 +417,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	}
 	free(weights);
 	*commit_list = best;
+	clear_commit_weight(&commit_weight);
 }
 
 static int register_ref(const char *refname, const struct object_id *oid,
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 09/14] bisect.c: use commit-slab for commit weight instead of commit->util

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> -		p->item->util = &weights[n++];
> +		*commit_weight_at(&commit_weight, p->item) = &weights[n++];

Interesting to see that this cleverness was inherited from the
original code that used the util field :-).  I was wondering why
the code was using "int*" without on-demand allocation.

[PATCH v2 10/14] name-rev: use commit-slab for rev-name instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/name-rev.c | 23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 387ddf85d2..0eb440359d 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -6,6 +6,7 @@
 #include "refs.h"
 #include "parse-options.h"
 #include "sha1-lookup.h"
+#include "commit-slab.h"
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 
@@ -17,11 +18,26 @@ typedef struct rev_name {
 	int from_tag;
 } rev_name;
 
+define_commit_slab(commit_rev_name, struct rev_name *);
+
 static timestamp_t cutoff = TIME_MAX;
+static struct commit_rev_name rev_names;
 
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
+static struct rev_name *get_commit_rev_name(struct commit *commit)
+{
+	struct rev_name **slot = commit_rev_name_peek(&rev_names, commit);
+
+	return slot ? *slot : NULL;
+}
+
+static void set_commit_rev_name(struct commit *commit, struct rev_name *name)
+{
+	*commit_rev_name_at(&rev_names, commit) = name;
+}
+
 static int is_better_name(struct rev_name *name,
 			  const char *tip_name,
 			  timestamp_t taggerdate,
@@ -65,7 +81,7 @@ static void name_rev(struct commit *commit,
 		int generation, int distance, int from_tag,
 		int deref)
 {
-	struct rev_name *name = (struct rev_name *)commit->util;
+	struct rev_name *name = get_commit_rev_name(commit);
 	struct commit_list *parents;
 	int parent_number = 1;
 	char *to_free = NULL;
@@ -84,7 +100,7 @@ static void name_rev(struct commit *commit,
 
 	if (name == NULL) {
 		name = xmalloc(sizeof(rev_name));
-		commit->util = name;
+		set_commit_rev_name(commit, name);
 		goto copy_data;
 	} else if (is_better_name(name, tip_name, taggerdate,
 				  generation, distance, from_tag)) {
@@ -296,7 +312,7 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
 	if (o->type != OBJ_COMMIT)
 		return get_exact_ref_match(o);
 	c = (struct commit *) o;
-	n = c->util;
+	n = get_commit_rev_name(c);
 	if (!n)
 		return NULL;
 
@@ -413,6 +429,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		OPT_END(),
 	};
 
+	init_commit_rev_name(&rev_names);
 	git_config(git_default_config, NULL);
 	argc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);
 	if (all + transform_stdin + !!argc > 1) {
-- 
2.17.0.705.g3525833791

[PATCH v2 11/14] show-branch: use commit-slab for commit-name instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
 1 file changed, 27 insertions(+), 12 deletions(-)

diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 6c2148b71d..29d15d16d2 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -7,6 +7,7 @@
 #include "argv-array.h"
 #include "parse-options.h"
 #include "dir.h"
+#include "commit-slab.h"
 
 static const char* show_branch_usage[] = {
     N_("git show-branch [-a | --all] [-r | --remotes] [--topo-order | --date-order]\n"
@@ -59,15 +60,27 @@ struct commit_name {
 	int generation; /* how many parents away from head_name */
 };
 
+define_commit_slab(commit_name_slab, struct commit_name *);
+static struct commit_name_slab name_slab;
+
+static struct commit_name *commit_to_name(struct commit *commit)
+{
+	return *commit_name_slab_at(&name_slab, commit);
+}
+
+
 /* Name the commit as nth generation ancestor of head_name;
  * we count only the first-parent relationship for naming purposes.
  */
 static void name_commit(struct commit *commit, const char *head_name, int nth)
 {
 	struct commit_name *name;
-	if (!commit->util)
-		commit->util = xmalloc(sizeof(struct commit_name));
-	name = commit->util;
+
+	name = *commit_name_slab_at(&name_slab, commit);
+	if (!name) {
+		name = xmalloc(sizeof(*name));
+		*commit_name_slab_at(&name_slab, commit) = name;
+	}
 	name->head_name = head_name;
 	name->generation = nth;
 }
@@ -79,8 +92,8 @@ static void name_commit(struct commit *commit, const char *head_name, int nth)
  */
 static void name_parent(struct commit *commit, struct commit *parent)
 {
-	struct commit_name *commit_name = commit->util;
-	struct commit_name *parent_name = parent->util;
+	struct commit_name *commit_name = commit_to_name(commit);
+	struct commit_name *parent_name = commit_to_name(parent);
 	if (!commit_name)
 		return;
 	if (!parent_name ||
@@ -94,12 +107,12 @@ static int name_first_parent_chain(struct commit *c)
 	int i = 0;
 	while (c) {
 		struct commit *p;
-		if (!c->util)
+		if (!commit_to_name(c))
 			break;
 		if (!c->parents)
 			break;
 		p = c->parents->item;
-		if (!p->util) {
+		if (!commit_to_name(p)) {
 			name_parent(c, p);
 			i++;
 		}
@@ -122,7 +135,7 @@ static void name_commits(struct commit_list *list,
 	/* First give names to the given heads */
 	for (cl = list; cl; cl = cl->next) {
 		c = cl->item;
-		if (c->util)
+		if (commit_to_name(c))
 			continue;
 		for (i = 0; i < num_rev; i++) {
 			if (rev[i] == c) {
@@ -148,9 +161,9 @@ static void name_commits(struct commit_list *list,
 			struct commit_name *n;
 			int nth;
 			c = cl->item;
-			if (!c->util)
+			if (!commit_to_name(c))
 				continue;
-			n = c->util;
+			n = commit_to_name(c);
 			parents = c->parents;
 			nth = 0;
 			while (parents) {
@@ -158,7 +171,7 @@ static void name_commits(struct commit_list *list,
 				struct strbuf newname = STRBUF_INIT;
 				parents = parents->next;
 				nth++;
-				if (p->util)
+				if (commit_to_name(p))
 					continue;
 				switch (n->generation) {
 				case 0:
@@ -271,7 +284,7 @@ static void show_one_commit(struct commit *commit, int no_name)
 {
 	struct strbuf pretty = STRBUF_INIT;
 	const char *pretty_str = "(unavailable)";
-	struct commit_name *name = commit->util;
+	struct commit_name *name = commit_to_name(commit);
 
 	if (commit->object.parsed) {
 		pp_commit_easy(CMIT_FMT_ONELINE, commit, &pretty);
@@ -660,6 +673,8 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		OPT_END()
 	};
 
+	init_commit_name_slab(&name_slab);
+
 	git_config(git_show_branch_config, NULL);
 
 	/* If nothing is specified, try the default first */
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 11/14] show-branch: use commit-slab for commit-name instead of commit->util

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> It's done so that commit->util can be removed. See more explanation in
> the commit that removes commit->util.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
>  1 file changed, 27 insertions(+), 12 deletions(-)

Looks obviously correct.  

Another place we could use commit-slab in this program, which I
think is a more interesting application, is to use it to store a
bitmask with runtime-computed width to replace those object->flags
bits, which will allow us to lift the MAX_REVS limitation.

Thanks.

Re: [PATCH v2 11/14] show-branch: use commit-slab for commit-name instead of commit->util

[Duy Nguyen]

On Mon, May 14, 2018 at 8:45 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> It's done so that commit->util can be removed. See more explanation in
>> the commit that removes commit->util.
>>
>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>> ---
>>  builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
>>  1 file changed, 27 insertions(+), 12 deletions(-)
>
> Looks obviously correct.
>
> Another place we could use commit-slab in this program, which I
> think is a more interesting application, is to use it to store a
> bitmask with runtime-computed width to replace those object->flags
> bits, which will allow us to lift the MAX_REVS limitation.

Interesting. I have a feeling paint_down() from shallow.c might be
reusable. Anyway I don't have enough interest in this command to
actually fix this so I'll just make a TODO note in case people need
something to do and grep for them in the code.
-- 
Duy

[PATCH v2 12/14] log: use commit-slab in prepare_bases() instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/log.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index d017e57475..967fbc5caa 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -28,6 +28,7 @@
 #include "mailmap.h"
 #include "gpg-interface.h"
 #include "progress.h"
+#include "commit-slab.h"
 
 #define MAIL_DEFAULT_WRAP 72
 
@@ -1340,6 +1341,8 @@ static struct commit *get_base_commit(const char *base_commit,
 	return base;
 }
 
+define_commit_slab(commit_base, int);
+
 static void prepare_bases(struct base_tree_info *bases,
 			  struct commit *base,
 			  struct commit **list,
@@ -1348,11 +1351,13 @@ static void prepare_bases(struct base_tree_info *bases,
 	struct commit *commit;
 	struct rev_info revs;
 	struct diff_options diffopt;
+	struct commit_base commit_base;
 	int i;
 
 	if (!base)
 		return;
 
+	init_commit_base(&commit_base);
 	diff_setup(&diffopt);
 	diffopt.flags.recursive = 1;
 	diff_setup_done(&diffopt);
@@ -1365,7 +1370,7 @@ static void prepare_bases(struct base_tree_info *bases,
 	for (i = 0; i < total; i++) {
 		list[i]->object.flags &= ~UNINTERESTING;
 		add_pending_object(&revs, &list[i]->object, "rev_list");
-		list[i]->util = (void *)1;
+		*commit_base_at(&commit_base, list[i]) = 1;
 	}
 	base->object.flags |= UNINTERESTING;
 	add_pending_object(&revs, &base->object, "base");
@@ -1379,7 +1384,7 @@ static void prepare_bases(struct base_tree_info *bases,
 	while ((commit = get_revision(&revs)) != NULL) {
 		struct object_id oid;
 		struct object_id *patch_id;
-		if (commit->util)
+		if (*commit_base_at(&commit_base, commit))
 			continue;
 		if (commit_patch_id(commit, &diffopt, &oid, 0))
 			die(_("cannot get patch id"));
@@ -1388,6 +1393,7 @@ static void prepare_bases(struct base_tree_info *bases,
 		oidcpy(patch_id, &oid);
 		bases->nr_patch_id++;
 	}
+	clear_commit_base(&commit_base);
 }
 
 static void print_bases(struct base_tree_info *bases, FILE *file)
-- 
2.17.0.705.g3525833791

[PATCH v2 13/14] merge: use commit-slab in merge remote desc instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/merge.c   | 25 +++++++++++++------------
 commit.c          | 12 ++++++++++--
 commit.h          |  2 +-
 merge-recursive.c |  8 +++++---
 4 files changed, 29 insertions(+), 18 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9db5a2cf16..fc55bc264b 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -443,6 +443,7 @@ static void merge_name(const char *remote, struct strbuf *msg)
 	struct object_id branch_head;
 	struct strbuf buf = STRBUF_INIT;
 	struct strbuf bname = STRBUF_INIT;
+	struct merge_remote_desc *desc;
 	const char *ptr;
 	char *found_ref;
 	int len, early;
@@ -515,16 +516,13 @@ static void merge_name(const char *remote, struct strbuf *msg)
 		strbuf_release(&truname);
 	}
 
-	if (remote_head->util) {
-		struct merge_remote_desc *desc;
-		desc = merge_remote_util(remote_head);
-		if (desc && desc->obj && desc->obj->type == OBJ_TAG) {
-			strbuf_addf(msg, "%s\t\t%s '%s'\n",
-				    oid_to_hex(&desc->obj->oid),
-				    type_name(desc->obj->type),
-				    remote);
-			goto cleanup;
-		}
+	desc = merge_remote_util(remote_head);
+	if (desc && desc->obj && desc->obj->type == OBJ_TAG) {
+		strbuf_addf(msg, "%s\t\t%s '%s'\n",
+			    oid_to_hex(&desc->obj->oid),
+			    type_name(desc->obj->type),
+			    remote);
+		goto cleanup;
 	}
 
 	strbuf_addf(msg, "%s\t\tcommit '%s'\n",
@@ -932,8 +930,11 @@ static void write_merge_heads(struct commit_list *remoteheads)
 	for (j = remoteheads; j; j = j->next) {
 		struct object_id *oid;
 		struct commit *c = j->item;
-		if (c->util && merge_remote_util(c)->obj) {
-			oid = &merge_remote_util(c)->obj->oid;
+		struct merge_remote_desc *desc;
+
+		desc = merge_remote_util(c);
+		if (desc && desc->obj) {
+			oid = &desc->obj->oid;
 		} else {
 			oid = &c->object.oid;
 		}
diff --git a/commit.c b/commit.c
index 57049118a5..8202067cd5 100644
--- a/commit.c
+++ b/commit.c
@@ -1574,13 +1574,21 @@ int commit_tree_extended(const char *msg, size_t msg_len,
 	return result;
 }
 
+define_commit_slab(merge_desc_slab, struct merge_remote_desc *);
+struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);
+
+struct merge_remote_desc *merge_remote_util(struct commit *commit)
+{
+	return *merge_desc_slab_at(&merge_desc_slab, commit);
+}
+
 void set_merge_remote_desc(struct commit *commit,
 			   const char *name, struct object *obj)
 {
 	struct merge_remote_desc *desc;
 	FLEX_ALLOC_STR(desc, name, name);
 	desc->obj = obj;
-	commit->util = desc;
+	*merge_desc_slab_at(&merge_desc_slab, commit) = desc;
 }
 
 struct commit *get_merge_parent(const char *name)
@@ -1592,7 +1600,7 @@ struct commit *get_merge_parent(const char *name)
 		return NULL;
 	obj = parse_object(&oid);
 	commit = (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
-	if (commit && !commit->util)
+	if (commit && !merge_remote_util(commit))
 		set_merge_remote_desc(commit, name, obj);
 	return commit;
 }
diff --git a/commit.h b/commit.h
index e57ae4b583..838f6a6b26 100644
--- a/commit.h
+++ b/commit.h
@@ -303,7 +303,7 @@ struct merge_remote_desc {
 	struct object *obj; /* the named object, could be a tag */
 	char name[FLEX_ARRAY];
 };
-#define merge_remote_util(commit) ((struct merge_remote_desc *)((commit)->util))
+extern struct merge_remote_desc *merge_remote_util(struct commit *);
 extern void set_merge_remote_desc(struct commit *commit,
 				  const char *name, struct object *obj);
 
diff --git a/merge-recursive.c b/merge-recursive.c
index 0c0d48624d..5537f01f8e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -223,10 +223,12 @@ static void output(struct merge_options *o, int v, const char *fmt, ...)
 
 static void output_commit_title(struct merge_options *o, struct commit *commit)
 {
+	struct merge_remote_desc *desc;
+
 	strbuf_addchars(&o->obuf, ' ', o->call_depth * 2);
-	if (commit->util)
-		strbuf_addf(&o->obuf, "virtual %s\n",
-			merge_remote_util(commit)->name);
+	desc = merge_remote_util(commit);
+	if (desc)
+		strbuf_addf(&o->obuf, "virtual %s\n", desc->name);
 	else {
 		strbuf_add_unique_abbrev(&o->obuf, &commit->object.oid,
 					 DEFAULT_ABBREV);
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 13/14] merge: use commit-slab in merge remote desc instead of commit->util

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> diff --git a/commit.c b/commit.c
> index 57049118a5..8202067cd5 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -1574,13 +1574,21 @@ int commit_tree_extended(const char *msg, size_t msg_len,
>  	return result;
>  }
>  
> +define_commit_slab(merge_desc_slab, struct merge_remote_desc *);
> +struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);

s/^/static /; otherwise sparse would complain?

Re: [PATCH v2 13/14] merge: use commit-slab in merge remote desc instead of commit->util

[Ramsay Jones]

On 18/05/18 03:16, Junio C Hamano wrote:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
> 
>> diff --git a/commit.c b/commit.c
>> index 57049118a5..8202067cd5 100644
>> --- a/commit.c
>> +++ b/commit.c
>> @@ -1574,13 +1574,21 @@ int commit_tree_extended(const char *msg, size_t msg_len,
>>  	return result;
>>  }
>>  
>> +define_commit_slab(merge_desc_slab, struct merge_remote_desc *);
>> +struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);
> 
> s/^/static /; otherwise sparse would complain?

Indeed, it already did (see [1]). ;-)

Your fixup, commit dc2172daed, on the 'nd/commit-util-to-slab'
branch has indeed fixed it up.

Thanks!

[1] https://public-inbox.org/git/e2c4276f-bcfd-faaa-f9ee-cb50e99da663@ramsayjones.plus.com/

ATB,
Ramsay Jones

[PATCH v2 14/14] commit.h: delete 'util' field in struct commit

[Nguyễn Thái Ngọc Duy]

If you have come this far, you probably have seen that this 'util'
pointer is used for many different purposes. Some are not even
contained in a command code, but buried deep in common code with no
clue who will use it and how.

The move to using commit-slab gives us a much better picture of how
some piece of data is associated with a commit and what for. Since
nobody uses 'util' pointer anymore, we can retire so that nobody will
abuse it again. commit-slab will be the way forward for associating
data to a commit.

As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
architecture) which should help reduce memory usage for reachability
test a bit. This is also what commit-slab is invented for [1].

[1] 96c4f4a370 (commit: allow associating auxiliary info on-demand -
2013-04-09)

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit.h | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/commit.h b/commit.h
index 838f6a6b26..70371e111e 100644
--- a/commit.h
+++ b/commit.h
@@ -18,12 +18,16 @@ struct commit_list {
 
 struct commit {
 	struct object object;
-	void *util;
 	unsigned int index;
 	timestamp_t date;
 	struct commit_list *parents;
 	struct tree *tree;
 	uint32_t graph_pos;
+	/*
+	 * Do not add more fields here unless it's _very_ often
+	 * used. Use commit-slab to associate more data with a commit
+	 * instead.
+	 */
 };
 
 extern int save_commit_buffer;
-- 
2.17.0.705.g3525833791

Re: [PATCH v2 14/14] commit.h: delete 'util' field in struct commit

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> diff --git a/commit.h b/commit.h
> index 838f6a6b26..70371e111e 100644
> --- a/commit.h
> +++ b/commit.h
> @@ -18,12 +18,16 @@ struct commit_list {
>  
>  struct commit {
>  	struct object object;
> -	void *util;
>  	unsigned int index;
>  	timestamp_t date;
>  	struct commit_list *parents;
>  	struct tree *tree;
>  	uint32_t graph_pos;
> +	/*
> +	 * Do not add more fields here unless it's _very_ often
> +	 * used. Use commit-slab to associate more data with a commit
> +	 * instead.
> +	 */
>  };

That's a logical consequence and a natural endgame of this
pleasent-to-read series.  THanks.

Unfortunately we are gaining more and more stuff in "struct commit"
with recent topics, and we may want to see if we can evict some of
them out to shrink it again.

To make it clear that everything that is less often used is keyed
off of the "index" field, I think it makes sense to move that field
to either end of the struct (I think in today's integration I
resolved a few merges to leave the "index" field at the end).

Re: [PATCH v2 14/14] commit.h: delete 'util' field in struct commit

[Duy Nguyen]

On Mon, May 14, 2018 at 04:52:29PM +0900, Junio C Hamano wrote:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
> 
> > diff --git a/commit.h b/commit.h
> > index 838f6a6b26..70371e111e 100644
> > --- a/commit.h
> > +++ b/commit.h
> > @@ -18,12 +18,16 @@ struct commit_list {
> >  
> >  struct commit {
> >  	struct object object;
> > -	void *util;
> >  	unsigned int index;
> >  	timestamp_t date;
> >  	struct commit_list *parents;
> >  	struct tree *tree;
> >  	uint32_t graph_pos;
> > +	/*
> > +	 * Do not add more fields here unless it's _very_ often
> > +	 * used. Use commit-slab to associate more data with a commit
> > +	 * instead.
> > +	 */
> >  };
> 
> That's a logical consequence and a natural endgame of this
> pleasent-to-read series.  THanks.
> 
> Unfortunately we are gaining more and more stuff in "struct commit"
> with recent topics, and we may want to see if we can evict some of
> them out to shrink it again.

Sigh.. ds/lazy-load-trees already enters 'next' so a fixup patch is
something like this.

Derrick, do you want to finish up this patch? I could do that by
myself, but I guess this could be good for you to get familiar with
commit-slab because ds/generation-numbers on 'pu' also adds a new
field in struct commit.

We should avoid adding more stuff in struct commit to reduce overhead
when these fields are not used (and I'm not sure how often generation
numbers are used to justify its place here). One clean way to do it is
with commit-slab, as demonstrated here for 'maybe_tree' field.

Anyway the patch is like this

-- 8< --
diff --git a/commit-graph.c b/commit-graph.c
index 70fa1b25fd..9d084f6200 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -9,6 +9,7 @@
 #include "revision.h"
 #include "sha1-lookup.h"
 #include "commit-graph.h"
+#include "commit-slab.h"
 
 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
@@ -38,6 +39,26 @@
 #define GRAPH_MIN_SIZE (5 * GRAPH_CHUNKLOOKUP_WIDTH + GRAPH_FANOUT_SIZE + \
 			GRAPH_OID_LEN + 8)
 
+
+/*
+ * If the commit is loaded from the commit-graph file, then this
+ * member may be NULL. Only access it through get_commit_tree()
+ * or get_commit_tree_oid().
+ */
+define_commit_slab(maybe_tree, struct tree *);
+struct maybe_tree maybe_trees = COMMIT_SLAB_INIT(1, maybe_trees);
+
+struct tree *set_maybe_tree(const struct commit *commit, struct tree *tree)
+{
+	*maybe_tree_at(&maybe_trees, commit) = tree;
+	return tree;
+}
+
+struct tree *get_maybe_tree(const struct commit *commit)
+{
+	return *maybe_tree_at(&maybe_trees, commit);
+}
+
 char *get_commit_graph_filename(const char *obj_dir)
 {
 	return xstrfmt("%s/info/commit-graph", obj_dir);
@@ -256,7 +277,7 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin
 	item->object.parsed = 1;
 	item->graph_pos = pos;
 
-	item->maybe_tree = NULL;
+	set_maybe_tree(item, NULL);
 
 	date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
 	date_low = get_be32(commit_data + g->hash_len + 12);
@@ -322,15 +343,15 @@ static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *
 					   GRAPH_DATA_WIDTH * (c->graph_pos);
 
 	hashcpy(oid.hash, commit_data);
-	c->maybe_tree = lookup_tree(&oid);
-
-	return c->maybe_tree;
+	return set_maybe_tree(c, lookup_tree(&oid));
 }
 
 struct tree *get_commit_tree_in_graph(const struct commit *c)
 {
-	if (c->maybe_tree)
-		return c->maybe_tree;
+	struct tree *maybe_tree = get_maybe_tree(c);
+
+	if (maybe_tree)
+		return maybe_tree;
 	if (c->graph_pos == COMMIT_NOT_FROM_GRAPH)
 		BUG("get_commit_tree_in_graph called from non-commit-graph commit");
 
diff --git a/commit-graph.h b/commit-graph.h
index 260a468e73..4a02e4b05e 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -45,4 +45,7 @@ void write_commit_graph(const char *obj_dir,
 			int nr_commits,
 			int append);
 
+struct tree *set_maybe_tree(const struct commit *commit, struct tree *tree);
+struct tree *get_maybe_tree(const struct commit *commit);
+
 #endif
diff --git a/commit.c b/commit.c
index 711f674c18..45521ab2de 100644
--- a/commit.c
+++ b/commit.c
@@ -298,8 +298,10 @@ void free_commit_buffer(struct commit *commit)
 
 struct tree *get_commit_tree(const struct commit *commit)
 {
-	if (commit->maybe_tree || !commit->object.parsed)
-		return commit->maybe_tree;
+	struct tree *maybe_tree = get_maybe_tree(commit);
+
+	if (maybe_tree || !commit->object.parsed)
+		return maybe_tree;
 
 	if (commit->graph_pos == COMMIT_NOT_FROM_GRAPH)
 		BUG("commit has NULL tree, but was not loaded from commit-graph");
@@ -351,7 +353,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 	if (get_sha1_hex(bufptr + 5, parent.hash) < 0)
 		return error("bad tree pointer in commit %s",
 			     oid_to_hex(&item->object.oid));
-	item->maybe_tree = lookup_tree(&parent);
+	set_maybe_tree(item, lookup_tree(&parent));
 	bufptr += tree_entry_len + 1; /* "tree " + "hex sha1" + "\n" */
 	pptr = &item->parents;
 
diff --git a/commit.h b/commit.h
index 23a3f364ed..b7274ca365 100644
--- a/commit.h
+++ b/commit.h
@@ -22,13 +22,6 @@ struct commit {
 	unsigned int index;
 	timestamp_t date;
 	struct commit_list *parents;
-
-	/*
-	 * If the commit is loaded from the commit-graph file, then this
-	 * member may be NULL. Only access it through get_commit_tree()
-	 * or get_commit_tree_oid().
-	 */
-	struct tree *maybe_tree;
 	uint32_t graph_pos;
 };
 
diff --git a/merge-recursive.c b/merge-recursive.c
index 8de6e36527..a8b5f9ca39 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -23,6 +23,7 @@
 #include "merge-recursive.h"
 #include "dir.h"
 #include "submodule.h"
+#include "commit-graph.h"
 
 struct path_hashmap_entry {
 	struct hashmap_entry e;
@@ -101,7 +102,7 @@ static struct commit *make_virtual_commit(struct tree *tree, const char *comment
 	struct commit *commit = alloc_commit_node();
 
 	set_merge_remote_desc(commit, comment, (struct object *)commit);
-	commit->maybe_tree = tree;
+	set_maybe_tree(commit, tree);
 	commit->object.parsed = 1;
 	return commit;
 }
-- 8< --

Re: [PATCH v2 14/14] commit.h: delete 'util' field in struct commit

[Duy Nguyen]

On Mon, May 14, 2018 at 6:07 PM, Duy Nguyen <pclouds@gmail.com> wrote:
> On Mon, May 14, 2018 at 04:52:29PM +0900, Junio C Hamano wrote:
>> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>>
>> > diff --git a/commit.h b/commit.h
>> > index 838f6a6b26..70371e111e 100644
>> > --- a/commit.h
>> > +++ b/commit.h
>> > @@ -18,12 +18,16 @@ struct commit_list {
>> >
>> >  struct commit {
>> >     struct object object;
>> > -   void *util;
>> >     unsigned int index;
>> >     timestamp_t date;
>> >     struct commit_list *parents;
>> >     struct tree *tree;
>> >     uint32_t graph_pos;
>> > +   /*
>> > +    * Do not add more fields here unless it's _very_ often
>> > +    * used. Use commit-slab to associate more data with a commit
>> > +    * instead.
>> > +    */
>> >  };
>>
>> That's a logical consequence and a natural endgame of this
>> pleasent-to-read series.  THanks.
>>
>> Unfortunately we are gaining more and more stuff in "struct commit"
>> with recent topics, and we may want to see if we can evict some of
>> them out to shrink it again.
>
> Sigh.. ds/lazy-load-trees already enters 'next' so a fixup patch is
> something like this.

Sorry I take this patch back. I didn't realize it was a rename and the
old field named 'tree' was already there (I vaguely recalled some
"tree" in this struct but didn't stop to think about it). Moving
graph_pos out is an option, but only 32-bit arch gains from it (64-bit
arch will have 4 bytes padding anyway) so probably not worth the
effort. "generation" field should probably be moved out though.
-- 
Duy

Re: [PATCH v2 14/14] commit.h: delete 'util' field in struct commit

[Derrick Stolee]

On 5/14/2018 1:30 PM, Duy Nguyen wrote:
> On Mon, May 14, 2018 at 6:07 PM, Duy Nguyen <pclouds@gmail.com> wrote:
>> On Mon, May 14, 2018 at 04:52:29PM +0900, Junio C Hamano wrote:
>>> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>>>
>>>> diff --git a/commit.h b/commit.h
>>>> index 838f6a6b26..70371e111e 100644
>>>> --- a/commit.h
>>>> +++ b/commit.h
>>>> @@ -18,12 +18,16 @@ struct commit_list {
>>>>
>>>>   struct commit {
>>>>      struct object object;
>>>> -   void *util;
>>>>      unsigned int index;
>>>>      timestamp_t date;
>>>>      struct commit_list *parents;
>>>>      struct tree *tree;
>>>>      uint32_t graph_pos;
>>>> +   /*
>>>> +    * Do not add more fields here unless it's _very_ often
>>>> +    * used. Use commit-slab to associate more data with a commit
>>>> +    * instead.
>>>> +    */
>>>>   };
>>> That's a logical consequence and a natural endgame of this
>>> pleasent-to-read series.  THanks.
>>>
>>> Unfortunately we are gaining more and more stuff in "struct commit"
>>> with recent topics, and we may want to see if we can evict some of
>>> them out to shrink it again.
>> Sigh.. ds/lazy-load-trees already enters 'next' so a fixup patch is
>> something like this.
> Sorry I take this patch back. I didn't realize it was a rename and the
> old field named 'tree' was already there (I vaguely recalled some
> "tree" in this struct but didn't stop to think about it). Moving
> graph_pos out is an option, but only 32-bit arch gains from it (64-bit
> arch will have 4 bytes padding anyway) so probably not worth the
> effort. "generation" field should probably be moved out though.

I'm happy to take a look at this patch and figure out the best way to 
integrate it with the changes I've been doing.

I disagree with the removal of "generation". My intention is to make the 
commit-graph feature a standard feature that most repos (of reasonable 
size) want to have. In that case, 'graph_pos' and 'generation' will be 
set during every parse and used by every commit walk. This is just my 
gut reaction.

As I investigate these changes, I'll try to see what performance hit is 
caused by converting the graph_pos and/or generation to commit slabs. 
(Again, I'm assuming the slabs will make this slower. I may be wrong here.)

Thanks,
-Stolee

Re: [PATCH v2 14/14] commit.h: delete 'util' field in struct commit

[Duy Nguyen]

On Mon, May 14, 2018 at 8:14 PM, Derrick Stolee <stolee@gmail.com> wrote:
> I disagree with the removal of "generation". My intention is to make the
> commit-graph feature a standard feature that most repos (of reasonable size)
> want to have. In that case, 'graph_pos' and 'generation' will be set during
> every parse and used by every commit walk. This is just my gut reaction.

My 'often used' is a poor choice of words. The problem here is memory
consumption in full-repo walk like 'git clone' or 'git gc', where more
memory use may equal more swapping and that will slow things down.

commit-slab also has a few advantage over packing everything in struct
commit besides the performance argument. It makes it easier to see
what field is used for what. And if an operation only uses a field in
a short time, then it's possible to free data after it's done
(impossible to free these struct commits without a lot more thinking
and checking; whatever you add here will stay until the end of the
process, which could be a long time for things like pack-objects)

> As I investigate these changes, I'll try to see what performance hit is
> caused by converting the graph_pos and/or generation to commit slabs.
> (Again, I'm assuming the slabs will make this slower. I may be wrong here.)

The slab allocation code is very similar to memory-pool, which was
made common code also by Microsoft to make reading cache faster so I
don't think it will slow things down for you (again, guessing, no real
measurement from my side). This does make me think it may be a good
idea to try unify commit-slab and memory-pool, let commit-slab be a
thin layer on top of memory-pool or something like that (the fewer
custom mem allocators we have, the better)
-- 
Duy

[PATCH v3 00/15] Die commit->util, die!

[Nguyễn Thái Ngọc Duy]

v3 fixes Junio's comments on v2:

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index b08e5ea0e3..5aaf5c8e59 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -592,7 +592,7 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,
 		if (!S_ISGITLINK(diff_queued_diff.queue[i]->two->mode))
 			export_blob(&diff_queued_diff.queue[i]->two->oid);
 
-	refname = *revision_sources_peek(&revision_sources, commit);
+	refname = *revision_sources_at(&revision_sources, commit);
 	if (anonymize) {
 		refname = anonymize_refname(refname);
 		anonymize_ident_line(&committer, &committer_end);
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 29d15d16d2..f2e985c00a 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -22,6 +22,11 @@ static int showbranch_use_color = -1;
 
 static struct argv_array default_args = ARGV_ARRAY_INIT;
 
+/*
+ * TODO: convert this use of commit->object.flags to commit-slab
+ * instead to store a pointer to ref name directly. Then use the same
+ * UNINTERESTING definition from revision.h here.
+ */
 #define UNINTERESTING	01
 
 #define REV_SHIFT	 2
diff --git a/commit-slab-hdr.h b/commit-slab-decl.h
similarity index 100%
rename from commit-slab-hdr.h
rename to commit-slab-decl.h
diff --git a/commit-slab-impl.h b/commit-slab-impl.h
index 19a88d7d8f..87a9cadfcc 100644
--- a/commit-slab-impl.h
+++ b/commit-slab-impl.h
@@ -87,7 +87,7 @@ struct slabname
  * to allow a terminating semicolon, which makes instantiations look
  * like function declarations.  I.e., the expansion of
  *
- *    implement_commit_slab(indegree, int);
+ *    implement_commit_slab(indegree, int, static);
  *
  * ends in 'struct indegree;'.  This would otherwise
  * be a syntax error according (at least) to ISO C.  It's hard to
diff --git a/commit-slab.h b/commit-slab.h
index dc029acc66..69bf0c807c 100644
--- a/commit-slab.h
+++ b/commit-slab.h
@@ -1,7 +1,7 @@
 #ifndef COMMIT_SLAB_H
 #define COMMIT_SLAB_H
 
-#include "commit-slab-hdr.h"
+#include "commit-slab-decl.h"
 #include "commit-slab-impl.h"
 
 /*
diff --git a/commit.c b/commit.c
index 8202067cd5..e63a8dfeaa 100644
--- a/commit.c
+++ b/commit.c
@@ -1575,7 +1575,7 @@ int commit_tree_extended(const char *msg, size_t msg_len,
 }
 
 define_commit_slab(merge_desc_slab, struct merge_remote_desc *);
-struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);
+static struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);
 
 struct merge_remote_desc *merge_remote_util(struct commit *commit)
 {
diff --git a/commit.h b/commit.h
index 70371e111e..4432458367 100644
--- a/commit.h
+++ b/commit.h
@@ -16,6 +16,11 @@ struct commit_list {
 	struct commit_list *next;
 };
 
+/*
+ * The size of this struct matters in full repo walk operations like
+ * 'git clone' or 'git gc'. Consider using commit-slab to attach data
+ * to a commit instead of adding new fields here.
+ */
 struct commit {
 	struct object object;
 	unsigned int index;
@@ -23,11 +28,6 @@ struct commit {
 	struct commit_list *parents;
 	struct tree *tree;
 	uint32_t graph_pos;
-	/*
-	 * Do not add more fields here unless it's _very_ often
-	 * used. Use commit-slab to associate more data with a commit
-	 * instead.
-	 */
 };
 
 extern int save_commit_buffer;
diff --git a/object.h b/object.h
index b8e70e5519..caf36529f3 100644
--- a/object.h
+++ b/object.h
@@ -43,6 +43,7 @@ struct object_array {
  * builtin/index-pack.c:                                     2021
  * builtin/pack-objects.c:                                   20
  * builtin/reflog.c:                   10--12
+ * builtin/show-branch.c:    0-------------------------------------------26
  * builtin/unpack-objects.c:                                 2021
  */
 #define FLAG_BITS  27
diff --git a/revision.h b/revision.h
index f3dc5f9740..bf2239f876 100644
--- a/revision.h
+++ b/revision.h
@@ -6,7 +6,7 @@
 #include "notes.h"
 #include "pretty.h"
 #include "diff.h"
-#include "commit-slab-hdr.h"
+#include "commit-slab-decl.h"
 
 /* Remember to update object flag allocation in object.h */
 #define SEEN		(1u<<0)
diff --git a/sequencer.c b/sequencer.c
index dd4993fd99..3b6d56d085 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -3161,7 +3161,7 @@ static enum check_level get_missing_commit_check_level(void)
 	return CHECK_IGNORE;
 }
 
-define_commit_slab(commit_seen, uint8_t);
+define_commit_slab(commit_seen, unsigned char);
 /*
  * Check if the user dropped some commits by mistake
  * Behaviour determined by rebase.missingCommitsCheck.
diff --git a/shallow.c b/shallow.c
index daf60a9391..0301049781 100644
--- a/shallow.c
+++ b/shallow.c
@@ -110,7 +110,7 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 			} else {
 				commit = (struct commit *)
 					object_array_pop(&stack);
-				cur_depth = **commit_depth_peek(&depths, commit);
+				cur_depth = **commit_depth_at(&depths, commit);
 			}
 		}
 		parse_commit_or_die(commit);
@@ -140,8 +140,7 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 						NULL, &stack);
 			else {
 				commit = p->item;
-				depth_slot = commit_depth_peek(&depths, commit);
-				cur_depth = **depth_slot;
+				cur_depth = **commit_depth_at(&depths, commit);
 			}
 		}
 	}


Nguyễn Thái Ngọc Duy (15):
  commit-slab.h: code split
  commit-slab: support shared commit-slab
  blame: use commit-slab for blame suspects instead of commit->util
  describe: use commit-slab for commit names instead of commit->util
  shallow.c: use commit-slab for commit depth instead of commit->util
  sequencer.c: use commit-slab to mark seen commits
  sequencer.c: use commit-slab to associate todo items to commits
  revision.c: use commit-slab for show_source
  bisect.c: use commit-slab for commit weight instead of commit->util
  name-rev: use commit-slab for rev-name instead of commit->util
  show-branch: use commit-slab for commit-name instead of commit->util
  show-branch: note about its object flags usage
  log: use commit-slab in prepare_bases() instead of commit->util
  merge: use commit-slab in merge remote desc instead of commit->util
  commit.h: delete 'util' field in struct commit

 bisect.c              |  12 +++--
 blame.c               |  42 +++++++++++----
 blame.h               |   2 +
 builtin/blame.c       |   2 +-
 builtin/describe.c    |  16 ++++--
 builtin/fast-export.c |  14 +++--
 builtin/log.c         |  17 +++++--
 builtin/merge.c       |  25 ++++-----
 builtin/name-rev.c    |  23 +++++++--
 builtin/show-branch.c |  44 +++++++++++-----
 commit-slab-decl.h    |  43 ++++++++++++++++
 commit-slab-impl.h    |  97 +++++++++++++++++++++++++++++++++++
 commit-slab.h         | 115 +++---------------------------------------
 commit.c              |  12 ++++-
 commit.h              |   8 ++-
 log-tree.c            |   8 ++-
 merge-recursive.c     |   8 +--
 object.h              |   1 +
 revision.c            |  19 +++++--
 revision.h            |   5 +-
 sequencer.c           |  24 ++++++---
 shallow.c             |  40 ++++++++++-----
 22 files changed, 382 insertions(+), 195 deletions(-)
 create mode 100644 commit-slab-decl.h
 create mode 100644 commit-slab-impl.h

-- 
2.17.0.705.g3525833791

[PATCH v3 01/15] commit-slab.h: code split

[Nguyễn Thái Ngọc Duy]

The struct declaration and implementation macros are moved to
commit-slab-hdr.h and commit-slab-impl.h respectively.

This right now is not needed for current users but if we make a public
commit-slab type, we may want to avoid including the slab
implementation in a header file which gets replicated in every c file
that includes it.
---
 commit-slab-decl.h |  30 ++++++++++++
 commit-slab-impl.h |  91 +++++++++++++++++++++++++++++++++++
 commit-slab.h      | 115 +++------------------------------------------
 3 files changed, 127 insertions(+), 109 deletions(-)
 create mode 100644 commit-slab-decl.h
 create mode 100644 commit-slab-impl.h

diff --git a/commit-slab-decl.h b/commit-slab-decl.h
new file mode 100644
index 0000000000..fb5220fb7d
--- /dev/null
+++ b/commit-slab-decl.h
@@ -0,0 +1,30 @@
+#ifndef COMMIT_SLAB_HDR_H
+#define COMMIT_SLAB_HDR_H
+
+/* allocate ~512kB at once, allowing for malloc overhead */
+#ifndef COMMIT_SLAB_SIZE
+#define COMMIT_SLAB_SIZE (512*1024-32)
+#endif
+
+#define declare_commit_slab(slabname, elemtype) 			\
+									\
+struct slabname {							\
+	unsigned slab_size;						\
+	unsigned stride;						\
+	unsigned slab_count;						\
+	elemtype **slab;						\
+}
+
+/*
+ * Statically initialize a commit slab named "var". Note that this
+ * evaluates "stride" multiple times! Example:
+ *
+ *   struct indegree indegrees = COMMIT_SLAB_INIT(1, indegrees);
+ *
+ */
+#define COMMIT_SLAB_INIT(stride, var) { \
+	COMMIT_SLAB_SIZE / sizeof(**((var).slab)) / (stride), \
+	(stride), 0, NULL \
+}
+
+#endif /* COMMIT_SLAB_HDR_H */
diff --git a/commit-slab-impl.h b/commit-slab-impl.h
new file mode 100644
index 0000000000..234d9ee5f0
--- /dev/null
+++ b/commit-slab-impl.h
@@ -0,0 +1,91 @@
+#ifndef COMMIT_SLAB_IMPL_H
+#define COMMIT_SLAB_IMPL_H
+
+#define MAYBE_UNUSED __attribute__((__unused__))
+
+#define implement_commit_slab(slabname, elemtype) 			\
+									\
+static int stat_ ##slabname## realloc;					\
+									\
+static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
+						   unsigned stride)	\
+{									\
+	unsigned int elem_size;						\
+	if (!stride)							\
+		stride = 1;						\
+	s->stride = stride;						\
+	elem_size = sizeof(elemtype) * stride;				\
+	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
+	s->slab_count = 0;						\
+	s->slab = NULL;							\
+}									\
+									\
+static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
+{									\
+	init_ ##slabname## _with_stride(s, 1);				\
+}									\
+									\
+static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
+{									\
+	unsigned int i;							\
+	for (i = 0; i < s->slab_count; i++)				\
+		free(s->slab[i]);					\
+	s->slab_count = 0;						\
+	FREE_AND_NULL(s->slab);						\
+}									\
+									\
+static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
+						  const struct commit *c, \
+						  int add_if_missing)   \
+{									\
+	unsigned int nth_slab, nth_slot;				\
+									\
+	nth_slab = c->index / s->slab_size;				\
+	nth_slot = c->index % s->slab_size;				\
+									\
+	if (s->slab_count <= nth_slab) {				\
+		unsigned int i;						\
+		if (!add_if_missing)					\
+			return NULL;					\
+		REALLOC_ARRAY(s->slab, nth_slab + 1);			\
+		stat_ ##slabname## realloc++;				\
+		for (i = s->slab_count; i <= nth_slab; i++)		\
+			s->slab[i] = NULL;				\
+		s->slab_count = nth_slab + 1;				\
+	}								\
+	if (!s->slab[nth_slab]) {					\
+		if (!add_if_missing)					\
+			return NULL;					\
+		s->slab[nth_slab] = xcalloc(s->slab_size,		\
+					    sizeof(**s->slab) * s->stride);		\
+	}								\
+	return &s->slab[nth_slab][nth_slot * s->stride];		\
+}									\
+									\
+static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
+					     const struct commit *c)	\
+{									\
+	return slabname##_at_peek(s, c, 1);				\
+}									\
+									\
+static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
+					     const struct commit *c)	\
+{									\
+	return slabname##_at_peek(s, c, 0);				\
+}									\
+									\
+struct slabname
+
+/*
+ * Note that this redundant forward declaration is required
+ * to allow a terminating semicolon, which makes instantiations look
+ * like function declarations.  I.e., the expansion of
+ *
+ *    implement_commit_slab(indegree, int);
+ *
+ * ends in 'struct indegree;'.  This would otherwise
+ * be a syntax error according (at least) to ISO C.  It's hard to
+ * catch because GCC silently parses it by default.
+ */
+
+#endif	/* COMMIT_SLAB_IMPL_H */
diff --git a/commit-slab.h b/commit-slab.h
index dcaab8ca04..32aa2c0e46 100644
--- a/commit-slab.h
+++ b/commit-slab.h
@@ -1,6 +1,9 @@
 #ifndef COMMIT_SLAB_H
 #define COMMIT_SLAB_H
 
+#include "commit-slab-decl.h"
+#include "commit-slab-impl.h"
+
 /*
  * define_commit_slab(slabname, elemtype) creates boilerplate code to define
  * a new struct (struct slabname) that is used to associate a piece of data
@@ -41,114 +44,8 @@
  *   leaking memory.
  */
 
-/* allocate ~512kB at once, allowing for malloc overhead */
-#ifndef COMMIT_SLAB_SIZE
-#define COMMIT_SLAB_SIZE (512*1024-32)
-#endif
-
-#define MAYBE_UNUSED __attribute__((__unused__))
-
-#define define_commit_slab(slabname, elemtype) 				\
-									\
-struct slabname {							\
-	unsigned slab_size;						\
-	unsigned stride;						\
-	unsigned slab_count;						\
-	elemtype **slab;						\
-};									\
-static int stat_ ##slabname## realloc;					\
-									\
-static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
-						   unsigned stride)	\
-{									\
-	unsigned int elem_size;						\
-	if (!stride)							\
-		stride = 1;						\
-	s->stride = stride;						\
-	elem_size = sizeof(elemtype) * stride;				\
-	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
-	s->slab_count = 0;						\
-	s->slab = NULL;							\
-}									\
-									\
-static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
-{									\
-	init_ ##slabname## _with_stride(s, 1);				\
-}									\
-									\
-static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
-{									\
-	unsigned int i;							\
-	for (i = 0; i < s->slab_count; i++)				\
-		free(s->slab[i]);					\
-	s->slab_count = 0;						\
-	FREE_AND_NULL(s->slab);						\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
-						  const struct commit *c, \
-						  int add_if_missing)   \
-{									\
-	unsigned int nth_slab, nth_slot;				\
-									\
-	nth_slab = c->index / s->slab_size;				\
-	nth_slot = c->index % s->slab_size;				\
-									\
-	if (s->slab_count <= nth_slab) {				\
-		unsigned int i;						\
-		if (!add_if_missing)					\
-			return NULL;					\
-		REALLOC_ARRAY(s->slab, nth_slab + 1);			\
-		stat_ ##slabname## realloc++;				\
-		for (i = s->slab_count; i <= nth_slab; i++)		\
-			s->slab[i] = NULL;				\
-		s->slab_count = nth_slab + 1;				\
-	}								\
-	if (!s->slab[nth_slab]) {					\
-		if (!add_if_missing)					\
-			return NULL;					\
-		s->slab[nth_slab] = xcalloc(s->slab_size,		\
-					    sizeof(**s->slab) * s->stride);		\
-	}								\
-	return &s->slab[nth_slab][nth_slot * s->stride];		\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
-					     const struct commit *c)	\
-{									\
-	return slabname##_at_peek(s, c, 1);				\
-}									\
-									\
-static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
-					     const struct commit *c)	\
-{									\
-	return slabname##_at_peek(s, c, 0);				\
-}									\
-									\
-struct slabname
-
-/*
- * Note that this redundant forward declaration is required
- * to allow a terminating semicolon, which makes instantiations look
- * like function declarations.  I.e., the expansion of
- *
- *    define_commit_slab(indegree, int);
- *
- * ends in 'struct indegree;'.  This would otherwise
- * be a syntax error according (at least) to ISO C.  It's hard to
- * catch because GCC silently parses it by default.
- */
-
-/*
- * Statically initialize a commit slab named "var". Note that this
- * evaluates "stride" multiple times! Example:
- *
- *   struct indegree indegrees = COMMIT_SLAB_INIT(1, indegrees);
- *
- */
-#define COMMIT_SLAB_INIT(stride, var) { \
-	COMMIT_SLAB_SIZE / sizeof(**((var).slab)) / (stride), \
-	(stride), 0, NULL \
-}
+#define define_commit_slab(slabname, elemtype) \
+	declare_commit_slab(slabname, elemtype); \
+	implement_commit_slab(slabname, elemtype)
 
 #endif /* COMMIT_SLAB_H */
-- 
2.17.0.705.g3525833791

Re: [PATCH v3 01/15] commit-slab.h: code split

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> The struct declaration and implementation macros are moved to
> commit-slab-hdr.h and commit-slab-impl.h respectively.

s/hdr/decl/;

>
> This right now is not needed for current users but if we make a public
> commit-slab type, we may want to avoid including the slab
> implementation in a header file which gets replicated in every c file
> that includes it.

s/c file/C file/; 

Also s/may want to/need to/; after all this is not about avoid
bloating the header and slowing down compilation.  Rather, the
duplicated implementation will cause linkage failures so we want
only a single implementation that is referenced from many places.

> ---

Missing sign off.

>  commit-slab-decl.h |  30 ++++++++++++
>  commit-slab-impl.h |  91 +++++++++++++++++++++++++++++++++++
>  commit-slab.h      | 115 +++------------------------------------------
>  3 files changed, 127 insertions(+), 109 deletions(-)
>  create mode 100644 commit-slab-decl.h
>  create mode 100644 commit-slab-impl.h

Other than that, looking good.

[PATCH v3 02/15] commit-slab: support shared commit-slab

[Nguyễn Thái Ngọc Duy]

define_shared_commit_slab() could be used in a header file to define a
commit-slab. One of these C files must include commit-slab-impl.h and
"call" implement_shared_commit_slab().
---
 commit-slab-decl.h | 13 +++++++++++++
 commit-slab-impl.h | 22 ++++++++++++++--------
 commit-slab.h      |  2 +-
 3 files changed, 28 insertions(+), 9 deletions(-)

diff --git a/commit-slab-decl.h b/commit-slab-decl.h
index fb5220fb7d..adc7b46c83 100644
--- a/commit-slab-decl.h
+++ b/commit-slab-decl.h
@@ -27,4 +27,17 @@ struct slabname {							\
 	(stride), 0, NULL \
 }
 
+#define declare_commit_slab_prototypes(slabname, elemtype)		\
+									\
+void init_ ##slabname## _with_stride(struct slabname *s, unsigned stride); \
+void init_ ##slabname(struct slabname *s);				\
+void clear_ ##slabname(struct slabname *s);				\
+elemtype *slabname## _at_peek(struct slabname *s, const struct commit *c, int add_if_missing); \
+elemtype *slabname## _at(struct slabname *s, const struct commit *c);	\
+elemtype *slabname## _peek(struct slabname *s, const struct commit *c)
+
+#define define_shared_commit_slab(slabname, elemtype) \
+	declare_commit_slab(slabname, elemtype); \
+	declare_commit_slab_prototypes(slabname, elemtype)
+
 #endif /* COMMIT_SLAB_HDR_H */
diff --git a/commit-slab-impl.h b/commit-slab-impl.h
index 234d9ee5f0..87a9cadfcc 100644
--- a/commit-slab-impl.h
+++ b/commit-slab-impl.h
@@ -3,11 +3,17 @@
 
 #define MAYBE_UNUSED __attribute__((__unused__))
 
-#define implement_commit_slab(slabname, elemtype) 			\
+#define implement_static_commit_slab(slabname, elemtype) \
+	implement_commit_slab(slabname, elemtype, static MAYBE_UNUSED)
+
+#define implement_shared_commit_slab(slabname, elemtype) \
+	implement_commit_slab(slabname, elemtype, )
+
+#define implement_commit_slab(slabname, elemtype, scope)		\
 									\
 static int stat_ ##slabname## realloc;					\
 									\
-static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
+scope void init_ ##slabname## _with_stride(struct slabname *s,		\
 						   unsigned stride)	\
 {									\
 	unsigned int elem_size;						\
@@ -20,12 +26,12 @@ static MAYBE_UNUSED void init_ ##slabname## _with_stride(struct slabname *s, \
 	s->slab = NULL;							\
 }									\
 									\
-static MAYBE_UNUSED void init_ ##slabname(struct slabname *s)		\
+scope void init_ ##slabname(struct slabname *s)				\
 {									\
 	init_ ##slabname## _with_stride(s, 1);				\
 }									\
 									\
-static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
+scope void clear_ ##slabname(struct slabname *s)			\
 {									\
 	unsigned int i;							\
 	for (i = 0; i < s->slab_count; i++)				\
@@ -34,7 +40,7 @@ static MAYBE_UNUSED void clear_ ##slabname(struct slabname *s)		\
 	FREE_AND_NULL(s->slab);						\
 }									\
 									\
-static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
+scope elemtype *slabname## _at_peek(struct slabname *s,			\
 						  const struct commit *c, \
 						  int add_if_missing)   \
 {									\
@@ -62,13 +68,13 @@ static MAYBE_UNUSED elemtype *slabname## _at_peek(struct slabname *s,	\
 	return &s->slab[nth_slab][nth_slot * s->stride];		\
 }									\
 									\
-static MAYBE_UNUSED elemtype *slabname## _at(struct slabname *s,	\
+scope elemtype *slabname## _at(struct slabname *s,			\
 					     const struct commit *c)	\
 {									\
 	return slabname##_at_peek(s, c, 1);				\
 }									\
 									\
-static MAYBE_UNUSED elemtype *slabname## _peek(struct slabname *s,	\
+scope elemtype *slabname## _peek(struct slabname *s,			\
 					     const struct commit *c)	\
 {									\
 	return slabname##_at_peek(s, c, 0);				\
@@ -81,7 +87,7 @@ struct slabname
  * to allow a terminating semicolon, which makes instantiations look
  * like function declarations.  I.e., the expansion of
  *
- *    implement_commit_slab(indegree, int);
+ *    implement_commit_slab(indegree, int, static);
  *
  * ends in 'struct indegree;'.  This would otherwise
  * be a syntax error according (at least) to ISO C.  It's hard to
diff --git a/commit-slab.h b/commit-slab.h
index 32aa2c0e46..69bf0c807c 100644
--- a/commit-slab.h
+++ b/commit-slab.h
@@ -46,6 +46,6 @@
 
 #define define_commit_slab(slabname, elemtype) \
 	declare_commit_slab(slabname, elemtype); \
-	implement_commit_slab(slabname, elemtype)
+	implement_static_commit_slab(slabname, elemtype)
 
 #endif /* COMMIT_SLAB_H */
-- 
2.17.0.705.g3525833791

[PATCH v3 03/15] blame: use commit-slab for blame suspects instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 blame.c         | 42 +++++++++++++++++++++++++++++++-----------
 blame.h         |  2 ++
 builtin/blame.c |  2 +-
 3 files changed, 34 insertions(+), 12 deletions(-)

diff --git a/blame.c b/blame.c
index 78c9808bd1..18e8bd996a 100644
--- a/blame.c
+++ b/blame.c
@@ -6,6 +6,24 @@
 #include "diffcore.h"
 #include "tag.h"
 #include "blame.h"
+#include "commit-slab.h"
+
+define_commit_slab(blame_suspects, struct blame_origin *);
+static struct blame_suspects blame_suspects;
+
+struct blame_origin *get_blame_suspects(struct commit *commit)
+{
+	struct blame_origin **result;
+
+	result = blame_suspects_peek(&blame_suspects, commit);
+
+	return result ? *result : NULL;
+}
+
+static void set_blame_suspects(struct commit *commit, struct blame_origin *origin)
+{
+	*blame_suspects_at(&blame_suspects, commit) = origin;
+}
 
 void blame_origin_decref(struct blame_origin *o)
 {
@@ -15,12 +33,12 @@ void blame_origin_decref(struct blame_origin *o)
 			blame_origin_decref(o->previous);
 		free(o->file.ptr);
 		/* Should be present exactly once in commit chain */
-		for (p = o->commit->util; p; l = p, p = p->next) {
+		for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) {
 			if (p == o) {
 				if (l)
 					l->next = p->next;
 				else
-					o->commit->util = p->next;
+					set_blame_suspects(o->commit, p->next);
 				free(o);
 				return;
 			}
@@ -41,8 +59,8 @@ static struct blame_origin *make_origin(struct commit *commit, const char *path)
 	FLEX_ALLOC_STR(o, path, path);
 	o->commit = commit;
 	o->refcnt = 1;
-	o->next = commit->util;
-	commit->util = o;
+	o->next = get_blame_suspects(commit);
+	set_blame_suspects(commit, o);
 	return o;
 }
 
@@ -54,13 +72,13 @@ static struct blame_origin *get_origin(struct commit *commit, const char *path)
 {
 	struct blame_origin *o, *l;
 
-	for (o = commit->util, l = NULL; o; l = o, o = o->next) {
+	for (o = get_blame_suspects(commit), l = NULL; o; l = o, o = o->next) {
 		if (!strcmp(o->path, path)) {
 			/* bump to front */
 			if (l) {
 				l->next = o->next;
-				o->next = commit->util;
-				commit->util = o;
+				o->next = get_blame_suspects(commit);
+				set_blame_suspects(commit, o);
 			}
 			return blame_origin_incref(o);
 		}
@@ -478,7 +496,7 @@ static void queue_blames(struct blame_scoreboard *sb, struct blame_origin *porig
 		porigin->suspects = blame_merge(porigin->suspects, sorted);
 	else {
 		struct blame_origin *o;
-		for (o = porigin->commit->util; o; o = o->next) {
+		for (o = get_blame_suspects(porigin->commit); o; o = o->next) {
 			if (o->suspects) {
 				porigin->suspects = sorted;
 				return;
@@ -525,7 +543,7 @@ static struct blame_origin *find_origin(struct commit *parent,
 	const char *paths[2];
 
 	/* First check any existing origins */
-	for (porigin = parent->util; porigin; porigin = porigin->next)
+	for (porigin = get_blame_suspects(parent); porigin; porigin = porigin->next)
 		if (!strcmp(porigin->path, origin->path)) {
 			/*
 			 * The same path between origin and its parent
@@ -1550,7 +1568,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)
 
 	while (commit) {
 		struct blame_entry *ent;
-		struct blame_origin *suspect = commit->util;
+		struct blame_origin *suspect = get_blame_suspects(commit);
 
 		/* find one suspect to break down */
 		while (suspect && !suspect->suspects)
@@ -1752,6 +1770,8 @@ void setup_scoreboard(struct blame_scoreboard *sb, const char *path, struct blam
 	struct commit *final_commit = NULL;
 	enum object_type type;
 
+	init_blame_suspects(&blame_suspects);
+
 	if (sb->reverse && sb->contents_from)
 		die(_("--contents and --reverse do not blend well."));
 
@@ -1815,7 +1835,7 @@ void setup_scoreboard(struct blame_scoreboard *sb, const char *path, struct blam
 	}
 
 	if (is_null_oid(&sb->final->object.oid)) {
-		o = sb->final->util;
+		o = get_blame_suspects(sb->final);
 		sb->final_buf = xmemdupz(o->file.ptr, o->file.size);
 		sb->final_buf_size = o->file.size;
 	}
diff --git a/blame.h b/blame.h
index a6c915c277..2092f9529c 100644
--- a/blame.h
+++ b/blame.h
@@ -172,4 +172,6 @@ extern void setup_scoreboard(struct blame_scoreboard *sb, const char *path, stru
 
 extern struct blame_entry *blame_entry_prepend(struct blame_entry *head, long start, long end, struct blame_origin *o);
 
+extern struct blame_origin *get_blame_suspects(struct commit *commit);
+
 #endif /* BLAME_H */
diff --git a/builtin/blame.c b/builtin/blame.c
index db38c0b307..969572810d 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -457,7 +457,7 @@ static void output(struct blame_scoreboard *sb, int option)
 			struct commit *commit = ent->suspect->commit;
 			if (commit->object.flags & MORE_THAN_ONE_PATH)
 				continue;
-			for (suspect = commit->util; suspect; suspect = suspect->next) {
+			for (suspect = get_blame_suspects(commit); suspect; suspect = suspect->next) {
 				if (suspect->guilty && count++) {
 					commit->object.flags |= MORE_THAN_ONE_PATH;
 					break;
-- 
2.17.0.705.g3525833791

[PATCH v3 04/15] describe: use commit-slab for commit names instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 builtin/describe.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index b5afc45846..1b6ca42553 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -15,9 +15,12 @@
 #include "run-command.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "commit-slab.h"
 
 #define MAX_TAGS	(FLAG_BITS - 1)
 
+define_commit_slab(commit_names, struct commit_name *);
+
 static const char * const describe_usage[] = {
 	N_("git describe [<options>] [<commit-ish>...]"),
 	N_("git describe [<options>] --dirty"),
@@ -37,6 +40,7 @@ static struct string_list patterns = STRING_LIST_INIT_NODUP;
 static struct string_list exclude_patterns = STRING_LIST_INIT_NODUP;
 static int always;
 static const char *suffix, *dirty, *broken;
+static struct commit_names commit_names;
 
 /* diff-index command arguments to check if working tree is dirty. */
 static const char *diff_index_args[] = {
@@ -321,11 +325,14 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	if (!have_util) {
 		struct hashmap_iter iter;
 		struct commit *c;
-		struct commit_name *n = hashmap_iter_first(&names, &iter);
+		struct commit_name *n;
+
+		init_commit_names(&commit_names);
+		n = hashmap_iter_first(&names, &iter);
 		for (; n; n = hashmap_iter_next(&iter)) {
 			c = lookup_commit_reference_gently(&n->peeled, 1);
 			if (c)
-				c->util = n;
+				*commit_names_at(&commit_names, c) = n;
 		}
 		have_util = 1;
 	}
@@ -336,8 +343,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	while (list) {
 		struct commit *c = pop_commit(&list);
 		struct commit_list *parents = c->parents;
+		struct commit_name **slot;
+
 		seen_commits++;
-		n = c->util;
+		slot = commit_names_peek(&commit_names, c);
+		n = slot ? *slot : NULL;
 		if (n) {
 			if (!tags && !all && n->prio < 2) {
 				unannotated_cnt++;
-- 
2.17.0.705.g3525833791

[PATCH v3 05/15] shallow.c: use commit-slab for commit depth instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.

While at there, plug a leak for keeping track of depth in this code.
---
 shallow.c | 40 ++++++++++++++++++++++++++++------------
 1 file changed, 28 insertions(+), 12 deletions(-)

diff --git a/shallow.c b/shallow.c
index df4d44ea7a..0301049781 100644
--- a/shallow.c
+++ b/shallow.c
@@ -12,6 +12,7 @@
 #include "commit-slab.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "commit-slab.h"
 
 static int is_shallow = -1;
 static struct stat_validity shallow_stat;
@@ -74,6 +75,11 @@ int is_repository_shallow(void)
 	return is_shallow;
 }
 
+/*
+ * TODO: use "int" elemtype instead of "int *" when/if commit-slab
+ * supports a "valid" flag.
+ */
+define_commit_slab(commit_depth, int *);
 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		int shallow_flag, int not_shallow_flag)
 {
@@ -82,25 +88,29 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 	struct object_array stack = OBJECT_ARRAY_INIT;
 	struct commit *commit = NULL;
 	struct commit_graft *graft;
+	struct commit_depth depths;
 
+	init_commit_depth(&depths);
 	while (commit || i < heads->nr || stack.nr) {
 		struct commit_list *p;
 		if (!commit) {
 			if (i < heads->nr) {
+				int **depth_slot;
 				commit = (struct commit *)
 					deref_tag(heads->objects[i++].item, NULL, 0);
 				if (!commit || commit->object.type != OBJ_COMMIT) {
 					commit = NULL;
 					continue;
 				}
-				if (!commit->util)
-					commit->util = xmalloc(sizeof(int));
-				*(int *)commit->util = 0;
+				depth_slot = commit_depth_at(&depths, commit);
+				if (!*depth_slot)
+					*depth_slot = xmalloc(sizeof(int));
+				**depth_slot = 0;
 				cur_depth = 0;
 			} else {
 				commit = (struct commit *)
 					object_array_pop(&stack);
-				cur_depth = *(int *)commit->util;
+				cur_depth = **commit_depth_at(&depths, commit);
 			}
 		}
 		parse_commit_or_die(commit);
@@ -116,25 +126,31 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		}
 		commit->object.flags |= not_shallow_flag;
 		for (p = commit->parents, commit = NULL; p; p = p->next) {
-			if (!p->item->util) {
-				int *pointer = xmalloc(sizeof(int));
-				p->item->util = pointer;
-				*pointer =  cur_depth;
+			int **depth_slot = commit_depth_at(&depths, p->item);
+			if (!*depth_slot) {
+				*depth_slot = xmalloc(sizeof(int));
+				**depth_slot = cur_depth;
 			} else {
-				int *pointer = p->item->util;
-				if (cur_depth >= *pointer)
+				if (cur_depth >= **depth_slot)
 					continue;
-				*pointer = cur_depth;
+				**depth_slot = cur_depth;
 			}
 			if (p->next)
 				add_object_array(&p->item->object,
 						NULL, &stack);
 			else {
 				commit = p->item;
-				cur_depth = *(int *)commit->util;
+				cur_depth = **commit_depth_at(&depths, commit);
 			}
 		}
 	}
+	for (i = 0; i < depths.slab_count; i++) {
+		int j;
+
+		for (j = 0; j < depths.slab_size; j++)
+			free(depths.slab[i][j]);
+	}
+	clear_commit_depth(&depths);
 
 	return result;
 }
-- 
2.17.0.705.g3525833791

[PATCH v3 06/15] sequencer.c: use commit-slab to mark seen commits

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 sequencer.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index 4ce5120e77..3af296db3b 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -23,6 +23,7 @@
 #include "hashmap.h"
 #include "notes-utils.h"
 #include "sigchain.h"
+#include "commit-slab.h"
 
 #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
 
@@ -3160,6 +3161,7 @@ static enum check_level get_missing_commit_check_level(void)
 	return CHECK_IGNORE;
 }
 
+define_commit_slab(commit_seen, unsigned char);
 /*
  * Check if the user dropped some commits by mistake
  * Behaviour determined by rebase.missingCommitsCheck.
@@ -3173,6 +3175,9 @@ int check_todo_list(void)
 	struct todo_list todo_list = TODO_LIST_INIT;
 	struct strbuf missing = STRBUF_INIT;
 	int advise_to_edit_todo = 0, res = 0, i;
+	struct commit_seen commit_seen;
+
+	init_commit_seen(&commit_seen);
 
 	strbuf_addstr(&todo_file, rebase_path_todo());
 	if (strbuf_read_file_or_whine(&todo_list.buf, todo_file.buf) < 0) {
@@ -3189,7 +3194,7 @@ int check_todo_list(void)
 	for (i = 0; i < todo_list.nr; i++) {
 		struct commit *commit = todo_list.items[i].commit;
 		if (commit)
-			commit->util = (void *)1;
+			*commit_seen_at(&commit_seen, commit) = 1;
 	}
 
 	todo_list_release(&todo_list);
@@ -3205,11 +3210,11 @@ int check_todo_list(void)
 	for (i = todo_list.nr - 1; i >= 0; i--) {
 		struct todo_item *item = todo_list.items + i;
 		struct commit *commit = item->commit;
-		if (commit && !commit->util) {
+		if (commit && !*commit_seen_at(&commit_seen, commit)) {
 			strbuf_addf(&missing, " - %s %.*s\n",
 				    short_commit_name(commit),
 				    item->arg_len, item->arg);
-			commit->util = (void *)1;
+			*commit_seen_at(&commit_seen, commit) = 1;
 		}
 	}
 
@@ -3235,6 +3240,7 @@ int check_todo_list(void)
 		"The possible behaviours are: ignore, warn, error.\n\n"));
 
 leave_check:
+	clear_commit_seen(&commit_seen);
 	strbuf_release(&todo_file);
 	todo_list_release(&todo_list);
 
-- 
2.17.0.705.g3525833791

[PATCH v3 07/15] sequencer.c: use commit-slab to associate todo items to commits

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 sequencer.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index 3af296db3b..3b6d56d085 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -3362,6 +3362,8 @@ static int subject2item_cmp(const void *fndata,
 	return key ? strcmp(a->subject, key) : strcmp(a->subject, b->subject);
 }
 
+define_commit_slab(commit_todo_item, struct todo_item *);
+
 /*
  * Rearrange the todo list that has both "pick commit-id msg" and "pick
  * commit-id fixup!/squash! msg" in it so that the latter is put immediately
@@ -3378,6 +3380,7 @@ int rearrange_squash(void)
 	struct hashmap subject2item;
 	int res = 0, rearranged = 0, *next, *tail, i;
 	char **subjects;
+	struct commit_todo_item commit_todo;
 
 	if (strbuf_read_file_or_whine(&todo_list.buf, todo_file) < 0)
 		return -1;
@@ -3386,6 +3389,7 @@ int rearrange_squash(void)
 		return -1;
 	}
 
+	init_commit_todo_item(&commit_todo);
 	/*
 	 * The hashmap maps onelines to the respective todo list index.
 	 *
@@ -3416,10 +3420,11 @@ int rearrange_squash(void)
 
 		if (is_fixup(item->command)) {
 			todo_list_release(&todo_list);
+			clear_commit_todo_item(&commit_todo);
 			return error(_("the script was already rearranged."));
 		}
 
-		item->commit->util = item;
+		*commit_todo_item_at(&commit_todo, item->commit) = item;
 
 		parse_commit(item->commit);
 		commit_buffer = get_commit_buffer(item->commit, NULL);
@@ -3446,9 +3451,9 @@ int rearrange_squash(void)
 			else if (!strchr(p, ' ') &&
 				 (commit2 =
 				  lookup_commit_reference_by_name(p)) &&
-				 commit2->util)
+				 *commit_todo_item_at(&commit_todo, commit2))
 				/* found by commit name */
-				i2 = (struct todo_item *)commit2->util
+				i2 = *commit_todo_item_at(&commit_todo, commit2)
 					- todo_list.items;
 			else {
 				/* copy can be a prefix of the commit subject */
@@ -3527,5 +3532,6 @@ int rearrange_squash(void)
 	hashmap_free(&subject2item, 1);
 	todo_list_release(&todo_list);
 
+	clear_commit_todo_item(&commit_todo);
 	return res;
 }
-- 
2.17.0.705.g3525833791

[PATCH v3 08/15] revision.c: use commit-slab for show_source

[Nguyễn Thái Ngọc Duy]

Instead of relying on commit->util to store the source string, let the
user provide a commit-slab to store the source strings in.

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 builtin/fast-export.c | 14 +++++++++-----
 builtin/log.c         |  7 +++++--
 log-tree.c            |  8 ++++++--
 revision.c            | 19 +++++++++++++++----
 revision.h            |  5 ++++-
 5 files changed, 39 insertions(+), 14 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 530df12f05..5aaf5c8e59 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -21,6 +21,7 @@
 #include "quote.h"
 #include "remote.h"
 #include "blob.h"
+#include "commit-slab.h"
 
 static const char *fast_export_usage[] = {
 	N_("git fast-export [rev-list-opts]"),
@@ -38,6 +39,7 @@ static struct string_list extra_refs = STRING_LIST_INIT_NODUP;
 static struct refspec *refspecs;
 static int refspecs_nr;
 static int anonymize;
+static struct revision_sources revision_sources;
 
 static int parse_opt_signed_tag_mode(const struct option *opt,
 				     const char *arg, int unset)
@@ -590,7 +592,7 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,
 		if (!S_ISGITLINK(diff_queued_diff.queue[i]->two->mode))
 			export_blob(&diff_queued_diff.queue[i]->two->oid);
 
-	refname = commit->util;
+	refname = *revision_sources_at(&revision_sources, commit);
 	if (anonymize) {
 		refname = anonymize_refname(refname);
 		anonymize_ident_line(&committer, &committer_end);
@@ -862,10 +864,11 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)
 		 * This ref will not be updated through a commit, lets make
 		 * sure it gets properly updated eventually.
 		 */
-		if (commit->util || commit->object.flags & SHOWN)
+		if (*revision_sources_at(&revision_sources, commit) ||
+		    commit->object.flags & SHOWN)
 			string_list_append(&extra_refs, full_name)->util = commit;
-		if (!commit->util)
-			commit->util = full_name;
+		if (!*revision_sources_at(&revision_sources, commit))
+			*revision_sources_at(&revision_sources, commit) = full_name;
 	}
 }
 
@@ -1029,8 +1032,9 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
 	git_config(git_default_config, NULL);
 
 	init_revisions(&revs, prefix);
+	init_revision_sources(&revision_sources);
 	revs.topo_order = 1;
-	revs.show_source = 1;
+	revs.sources = &revision_sources;
 	revs.rewrite_parents = 1;
 	argc = parse_options(argc, argv, prefix, options, fast_export_usage,
 			PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN);
diff --git a/builtin/log.c b/builtin/log.c
index 71f68a3e4f..d017e57475 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -148,6 +148,7 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	static struct string_list decorate_refs_include = STRING_LIST_INIT_NODUP;
 	struct decoration_filter decoration_filter = {&decorate_refs_include,
 						      &decorate_refs_exclude};
+	static struct revision_sources revision_sources;
 
 	const struct option builtin_log_options[] = {
 		OPT__QUIET(&quiet, N_("suppress diff output")),
@@ -194,8 +195,10 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 	    rev->diffopt.filter || rev->diffopt.flags.follow_renames)
 		rev->always_show_header = 0;
 
-	if (source)
-		rev->show_source = 1;
+	if (source) {
+		init_revision_sources(&revision_sources);
+		rev->sources = &revision_sources;
+	}
 
 	if (mailmap) {
 		rev->mailmap = xcalloc(1, sizeof(struct string_list));
diff --git a/log-tree.c b/log-tree.c
index d1c0bedf24..0b41ee3235 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -295,8 +295,12 @@ void show_decorations(struct rev_info *opt, struct commit *commit)
 {
 	struct strbuf sb = STRBUF_INIT;
 
-	if (opt->show_source && commit->util)
-		fprintf(opt->diffopt.file, "\t%s", (char *) commit->util);
+	if (opt->sources) {
+		char **slot = revision_sources_peek(opt->sources, commit);
+
+		if (slot && *slot)
+			fprintf(opt->diffopt.file, "\t%s", *slot);
+	}
 	if (!opt->show_decorations)
 		return;
 	format_decorations(&sb, commit, opt->diffopt.use_color);
diff --git a/revision.c b/revision.c
index 1cff11833e..be8fe7d67b 100644
--- a/revision.c
+++ b/revision.c
@@ -29,6 +29,8 @@ volatile show_early_output_fn_t show_early_output;
 static const char *term_bad;
 static const char *term_good;
 
+implement_shared_commit_slab(revision_sources, char *);
+
 void show_object_with_name(FILE *out, struct object *obj, const char *name)
 {
 	const char *p;
@@ -255,14 +257,19 @@ static struct commit *handle_commit(struct rev_info *revs,
 	 */
 	if (object->type == OBJ_COMMIT) {
 		struct commit *commit = (struct commit *)object;
+
 		if (parse_commit(commit) < 0)
 			die("unable to parse commit %s", name);
 		if (flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
 			revs->limited = 1;
 		}
-		if (revs->show_source && !commit->util)
-			commit->util = xstrdup(name);
+		if (revs->sources) {
+			char **slot = revision_sources_at(revs->sources, commit);
+
+			if (!*slot)
+				*slot = xstrdup(name);
+		}
 		return commit;
 	}
 
@@ -814,8 +821,12 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			}
 			return -1;
 		}
-		if (revs->show_source && !p->util)
-			p->util = commit->util;
+		if (revs->sources) {
+			char **slot = revision_sources_at(revs->sources, p);
+
+			if (!*slot)
+				*slot = *revision_sources_at(revs->sources, commit);
+		}
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
 			p->object.flags |= SEEN;
diff --git a/revision.h b/revision.h
index b8c47b98e2..bf2239f876 100644
--- a/revision.h
+++ b/revision.h
@@ -6,6 +6,7 @@
 #include "notes.h"
 #include "pretty.h"
 #include "diff.h"
+#include "commit-slab-decl.h"
 
 /* Remember to update object flag allocation in object.h */
 #define SEEN		(1u<<0)
@@ -29,6 +30,7 @@ struct rev_info;
 struct log_info;
 struct string_list;
 struct saved_parents;
+define_shared_commit_slab(revision_sources, char *);
 
 struct rev_cmdline_info {
 	unsigned int nr;
@@ -111,7 +113,6 @@ struct rev_info {
 			right_only:1,
 			rewrite_parents:1,
 			print_parents:1,
-			show_source:1,
 			show_decorations:1,
 			reverse:1,
 			reverse_output_stage:1,
@@ -224,6 +225,8 @@ struct rev_info {
 
 	struct commit_list *previous_parents;
 	const char *break_bar;
+
+	struct revision_sources *sources;
 };
 
 extern int ref_excluded(struct string_list *, const char *path);
-- 
2.17.0.705.g3525833791

[PATCH v3 09/15] bisect.c: use commit-slab for commit weight instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 bisect.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/bisect.c b/bisect.c
index a579b50884..6de1abd407 100644
--- a/bisect.c
+++ b/bisect.c
@@ -12,6 +12,7 @@
 #include "bisect.h"
 #include "sha1-array.h"
 #include "argv-array.h"
+#include "commit-slab.h"
 
 static struct oid_array good_revs;
 static struct oid_array skipped_revs;
@@ -70,16 +71,19 @@ static void clear_distance(struct commit_list *list)
 	}
 }
 
+define_commit_slab(commit_weight, int *);
+static struct commit_weight commit_weight;
+
 #define DEBUG_BISECT 0
 
 static inline int weight(struct commit_list *elem)
 {
-	return *((int*)(elem->item->util));
+	return **commit_weight_at(&commit_weight, elem->item);
 }
 
 static inline void weight_set(struct commit_list *elem, int weight)
 {
-	*((int*)(elem->item->util)) = weight;
+	**commit_weight_at(&commit_weight, elem->item) = weight;
 }
 
 static int count_interesting_parents(struct commit *commit)
@@ -265,7 +269,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
 
-		p->item->util = &weights[n++];
+		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
 		switch (count_interesting_parents(commit)) {
 		case 0:
 			if (!(flags & TREESAME)) {
@@ -372,6 +376,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	int *weights;
 
 	show_list("bisection 2 entry", 0, 0, *commit_list);
+	init_commit_weight(&commit_weight);
 
 	/*
 	 * Count the number of total and tree-changing items on the
@@ -412,6 +417,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	}
 	free(weights);
 	*commit_list = best;
+	clear_commit_weight(&commit_weight);
 }
 
 static int register_ref(const char *refname, const struct object_id *oid,
-- 
2.17.0.705.g3525833791

[PATCH v3 10/15] name-rev: use commit-slab for rev-name instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 builtin/name-rev.c | 23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 387ddf85d2..0eb440359d 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -6,6 +6,7 @@
 #include "refs.h"
 #include "parse-options.h"
 #include "sha1-lookup.h"
+#include "commit-slab.h"
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 
@@ -17,11 +18,26 @@ typedef struct rev_name {
 	int from_tag;
 } rev_name;
 
+define_commit_slab(commit_rev_name, struct rev_name *);
+
 static timestamp_t cutoff = TIME_MAX;
+static struct commit_rev_name rev_names;
 
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
+static struct rev_name *get_commit_rev_name(struct commit *commit)
+{
+	struct rev_name **slot = commit_rev_name_peek(&rev_names, commit);
+
+	return slot ? *slot : NULL;
+}
+
+static void set_commit_rev_name(struct commit *commit, struct rev_name *name)
+{
+	*commit_rev_name_at(&rev_names, commit) = name;
+}
+
 static int is_better_name(struct rev_name *name,
 			  const char *tip_name,
 			  timestamp_t taggerdate,
@@ -65,7 +81,7 @@ static void name_rev(struct commit *commit,
 		int generation, int distance, int from_tag,
 		int deref)
 {
-	struct rev_name *name = (struct rev_name *)commit->util;
+	struct rev_name *name = get_commit_rev_name(commit);
 	struct commit_list *parents;
 	int parent_number = 1;
 	char *to_free = NULL;
@@ -84,7 +100,7 @@ static void name_rev(struct commit *commit,
 
 	if (name == NULL) {
 		name = xmalloc(sizeof(rev_name));
-		commit->util = name;
+		set_commit_rev_name(commit, name);
 		goto copy_data;
 	} else if (is_better_name(name, tip_name, taggerdate,
 				  generation, distance, from_tag)) {
@@ -296,7 +312,7 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
 	if (o->type != OBJ_COMMIT)
 		return get_exact_ref_match(o);
 	c = (struct commit *) o;
-	n = c->util;
+	n = get_commit_rev_name(c);
 	if (!n)
 		return NULL;
 
@@ -413,6 +429,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		OPT_END(),
 	};
 
+	init_commit_rev_name(&rev_names);
 	git_config(git_default_config, NULL);
 	argc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);
 	if (all + transform_stdin + !!argc > 1) {
-- 
2.17.0.705.g3525833791

[PATCH v3 11/15] show-branch: use commit-slab for commit-name instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 builtin/show-branch.c | 39 +++++++++++++++++++++++++++------------
 1 file changed, 27 insertions(+), 12 deletions(-)

diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 6c2148b71d..29d15d16d2 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -7,6 +7,7 @@
 #include "argv-array.h"
 #include "parse-options.h"
 #include "dir.h"
+#include "commit-slab.h"
 
 static const char* show_branch_usage[] = {
     N_("git show-branch [-a | --all] [-r | --remotes] [--topo-order | --date-order]\n"
@@ -59,15 +60,27 @@ struct commit_name {
 	int generation; /* how many parents away from head_name */
 };
 
+define_commit_slab(commit_name_slab, struct commit_name *);
+static struct commit_name_slab name_slab;
+
+static struct commit_name *commit_to_name(struct commit *commit)
+{
+	return *commit_name_slab_at(&name_slab, commit);
+}
+
+
 /* Name the commit as nth generation ancestor of head_name;
  * we count only the first-parent relationship for naming purposes.
  */
 static void name_commit(struct commit *commit, const char *head_name, int nth)
 {
 	struct commit_name *name;
-	if (!commit->util)
-		commit->util = xmalloc(sizeof(struct commit_name));
-	name = commit->util;
+
+	name = *commit_name_slab_at(&name_slab, commit);
+	if (!name) {
+		name = xmalloc(sizeof(*name));
+		*commit_name_slab_at(&name_slab, commit) = name;
+	}
 	name->head_name = head_name;
 	name->generation = nth;
 }
@@ -79,8 +92,8 @@ static void name_commit(struct commit *commit, const char *head_name, int nth)
  */
 static void name_parent(struct commit *commit, struct commit *parent)
 {
-	struct commit_name *commit_name = commit->util;
-	struct commit_name *parent_name = parent->util;
+	struct commit_name *commit_name = commit_to_name(commit);
+	struct commit_name *parent_name = commit_to_name(parent);
 	if (!commit_name)
 		return;
 	if (!parent_name ||
@@ -94,12 +107,12 @@ static int name_first_parent_chain(struct commit *c)
 	int i = 0;
 	while (c) {
 		struct commit *p;
-		if (!c->util)
+		if (!commit_to_name(c))
 			break;
 		if (!c->parents)
 			break;
 		p = c->parents->item;
-		if (!p->util) {
+		if (!commit_to_name(p)) {
 			name_parent(c, p);
 			i++;
 		}
@@ -122,7 +135,7 @@ static void name_commits(struct commit_list *list,
 	/* First give names to the given heads */
 	for (cl = list; cl; cl = cl->next) {
 		c = cl->item;
-		if (c->util)
+		if (commit_to_name(c))
 			continue;
 		for (i = 0; i < num_rev; i++) {
 			if (rev[i] == c) {
@@ -148,9 +161,9 @@ static void name_commits(struct commit_list *list,
 			struct commit_name *n;
 			int nth;
 			c = cl->item;
-			if (!c->util)
+			if (!commit_to_name(c))
 				continue;
-			n = c->util;
+			n = commit_to_name(c);
 			parents = c->parents;
 			nth = 0;
 			while (parents) {
@@ -158,7 +171,7 @@ static void name_commits(struct commit_list *list,
 				struct strbuf newname = STRBUF_INIT;
 				parents = parents->next;
 				nth++;
-				if (p->util)
+				if (commit_to_name(p))
 					continue;
 				switch (n->generation) {
 				case 0:
@@ -271,7 +284,7 @@ static void show_one_commit(struct commit *commit, int no_name)
 {
 	struct strbuf pretty = STRBUF_INIT;
 	const char *pretty_str = "(unavailable)";
-	struct commit_name *name = commit->util;
+	struct commit_name *name = commit_to_name(commit);
 
 	if (commit->object.parsed) {
 		pp_commit_easy(CMIT_FMT_ONELINE, commit, &pretty);
@@ -660,6 +673,8 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		OPT_END()
 	};
 
+	init_commit_name_slab(&name_slab);
+
 	git_config(git_show_branch_config, NULL);
 
 	/* If nothing is specified, try the default first */
-- 
2.17.0.705.g3525833791

[PATCH v3 12/15] show-branch: note about its object flags usage

[Nguyễn Thái Ngọc Duy]

This is another candidate for commit-slab. Keep Junio's observation in
code so we can search it later on when somebody wants to improve the
code.
---
 builtin/show-branch.c | 5 +++++
 object.h              | 1 +
 2 files changed, 6 insertions(+)

diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 29d15d16d2..f2e985c00a 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -22,6 +22,11 @@ static int showbranch_use_color = -1;
 
 static struct argv_array default_args = ARGV_ARRAY_INIT;
 
+/*
+ * TODO: convert this use of commit->object.flags to commit-slab
+ * instead to store a pointer to ref name directly. Then use the same
+ * UNINTERESTING definition from revision.h here.
+ */
 #define UNINTERESTING	01
 
 #define REV_SHIFT	 2
diff --git a/object.h b/object.h
index b8e70e5519..caf36529f3 100644
--- a/object.h
+++ b/object.h
@@ -43,6 +43,7 @@ struct object_array {
  * builtin/index-pack.c:                                     2021
  * builtin/pack-objects.c:                                   20
  * builtin/reflog.c:                   10--12
+ * builtin/show-branch.c:    0-------------------------------------------26
  * builtin/unpack-objects.c:                                 2021
  */
 #define FLAG_BITS  27
-- 
2.17.0.705.g3525833791

[PATCH v3 13/15] log: use commit-slab in prepare_bases() instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 builtin/log.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index d017e57475..967fbc5caa 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -28,6 +28,7 @@
 #include "mailmap.h"
 #include "gpg-interface.h"
 #include "progress.h"
+#include "commit-slab.h"
 
 #define MAIL_DEFAULT_WRAP 72
 
@@ -1340,6 +1341,8 @@ static struct commit *get_base_commit(const char *base_commit,
 	return base;
 }
 
+define_commit_slab(commit_base, int);
+
 static void prepare_bases(struct base_tree_info *bases,
 			  struct commit *base,
 			  struct commit **list,
@@ -1348,11 +1351,13 @@ static void prepare_bases(struct base_tree_info *bases,
 	struct commit *commit;
 	struct rev_info revs;
 	struct diff_options diffopt;
+	struct commit_base commit_base;
 	int i;
 
 	if (!base)
 		return;
 
+	init_commit_base(&commit_base);
 	diff_setup(&diffopt);
 	diffopt.flags.recursive = 1;
 	diff_setup_done(&diffopt);
@@ -1365,7 +1370,7 @@ static void prepare_bases(struct base_tree_info *bases,
 	for (i = 0; i < total; i++) {
 		list[i]->object.flags &= ~UNINTERESTING;
 		add_pending_object(&revs, &list[i]->object, "rev_list");
-		list[i]->util = (void *)1;
+		*commit_base_at(&commit_base, list[i]) = 1;
 	}
 	base->object.flags |= UNINTERESTING;
 	add_pending_object(&revs, &base->object, "base");
@@ -1379,7 +1384,7 @@ static void prepare_bases(struct base_tree_info *bases,
 	while ((commit = get_revision(&revs)) != NULL) {
 		struct object_id oid;
 		struct object_id *patch_id;
-		if (commit->util)
+		if (*commit_base_at(&commit_base, commit))
 			continue;
 		if (commit_patch_id(commit, &diffopt, &oid, 0))
 			die(_("cannot get patch id"));
@@ -1388,6 +1393,7 @@ static void prepare_bases(struct base_tree_info *bases,
 		oidcpy(patch_id, &oid);
 		bases->nr_patch_id++;
 	}
+	clear_commit_base(&commit_base);
 }
 
 static void print_bases(struct base_tree_info *bases, FILE *file)
-- 
2.17.0.705.g3525833791

[PATCH v3 14/15] merge: use commit-slab in merge remote desc instead of commit->util

[Nguyễn Thái Ngọc Duy]

It's done so that commit->util can be removed. See more explanation in
the commit that removes commit->util.
---
 builtin/merge.c   | 25 +++++++++++++------------
 commit.c          | 12 ++++++++++--
 commit.h          |  2 +-
 merge-recursive.c |  8 +++++---
 4 files changed, 29 insertions(+), 18 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9db5a2cf16..fc55bc264b 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -443,6 +443,7 @@ static void merge_name(const char *remote, struct strbuf *msg)
 	struct object_id branch_head;
 	struct strbuf buf = STRBUF_INIT;
 	struct strbuf bname = STRBUF_INIT;
+	struct merge_remote_desc *desc;
 	const char *ptr;
 	char *found_ref;
 	int len, early;
@@ -515,16 +516,13 @@ static void merge_name(const char *remote, struct strbuf *msg)
 		strbuf_release(&truname);
 	}
 
-	if (remote_head->util) {
-		struct merge_remote_desc *desc;
-		desc = merge_remote_util(remote_head);
-		if (desc && desc->obj && desc->obj->type == OBJ_TAG) {
-			strbuf_addf(msg, "%s\t\t%s '%s'\n",
-				    oid_to_hex(&desc->obj->oid),
-				    type_name(desc->obj->type),
-				    remote);
-			goto cleanup;
-		}
+	desc = merge_remote_util(remote_head);
+	if (desc && desc->obj && desc->obj->type == OBJ_TAG) {
+		strbuf_addf(msg, "%s\t\t%s '%s'\n",
+			    oid_to_hex(&desc->obj->oid),
+			    type_name(desc->obj->type),
+			    remote);
+		goto cleanup;
 	}
 
 	strbuf_addf(msg, "%s\t\tcommit '%s'\n",
@@ -932,8 +930,11 @@ static void write_merge_heads(struct commit_list *remoteheads)
 	for (j = remoteheads; j; j = j->next) {
 		struct object_id *oid;
 		struct commit *c = j->item;
-		if (c->util && merge_remote_util(c)->obj) {
-			oid = &merge_remote_util(c)->obj->oid;
+		struct merge_remote_desc *desc;
+
+		desc = merge_remote_util(c);
+		if (desc && desc->obj) {
+			oid = &desc->obj->oid;
 		} else {
 			oid = &c->object.oid;
 		}
diff --git a/commit.c b/commit.c
index 57049118a5..e63a8dfeaa 100644
--- a/commit.c
+++ b/commit.c
@@ -1574,13 +1574,21 @@ int commit_tree_extended(const char *msg, size_t msg_len,
 	return result;
 }
 
+define_commit_slab(merge_desc_slab, struct merge_remote_desc *);
+static struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab);
+
+struct merge_remote_desc *merge_remote_util(struct commit *commit)
+{
+	return *merge_desc_slab_at(&merge_desc_slab, commit);
+}
+
 void set_merge_remote_desc(struct commit *commit,
 			   const char *name, struct object *obj)
 {
 	struct merge_remote_desc *desc;
 	FLEX_ALLOC_STR(desc, name, name);
 	desc->obj = obj;
-	commit->util = desc;
+	*merge_desc_slab_at(&merge_desc_slab, commit) = desc;
 }
 
 struct commit *get_merge_parent(const char *name)
@@ -1592,7 +1600,7 @@ struct commit *get_merge_parent(const char *name)
 		return NULL;
 	obj = parse_object(&oid);
 	commit = (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
-	if (commit && !commit->util)
+	if (commit && !merge_remote_util(commit))
 		set_merge_remote_desc(commit, name, obj);
 	return commit;
 }
diff --git a/commit.h b/commit.h
index e57ae4b583..838f6a6b26 100644
--- a/commit.h
+++ b/commit.h
@@ -303,7 +303,7 @@ struct merge_remote_desc {
 	struct object *obj; /* the named object, could be a tag */
 	char name[FLEX_ARRAY];
 };
-#define merge_remote_util(commit) ((struct merge_remote_desc *)((commit)->util))
+extern struct merge_remote_desc *merge_remote_util(struct commit *);
 extern void set_merge_remote_desc(struct commit *commit,
 				  const char *name, struct object *obj);
 
diff --git a/merge-recursive.c b/merge-recursive.c
index 0c0d48624d..5537f01f8e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -223,10 +223,12 @@ static void output(struct merge_options *o, int v, const char *fmt, ...)
 
 static void output_commit_title(struct merge_options *o, struct commit *commit)
 {
+	struct merge_remote_desc *desc;
+
 	strbuf_addchars(&o->obuf, ' ', o->call_depth * 2);
-	if (commit->util)
-		strbuf_addf(&o->obuf, "virtual %s\n",
-			merge_remote_util(commit)->name);
+	desc = merge_remote_util(commit);
+	if (desc)
+		strbuf_addf(&o->obuf, "virtual %s\n", desc->name);
 	else {
 		strbuf_add_unique_abbrev(&o->obuf, &commit->object.oid,
 					 DEFAULT_ABBREV);
-- 
2.17.0.705.g3525833791

[PATCH v3 15/15] commit.h: delete 'util' field in struct commit

[Nguyễn Thái Ngọc Duy]

If you have come this far, you probably have seen that this 'util'
pointer is used for many different purposes. Some are not even
contained in a command code, but buried deep in common code with no
clue who will use it and how.

The move to using commit-slab gives us a much better picture of how
some piece of data is associated with a commit and what for. Since
nobody uses 'util' pointer anymore, we can retire so that nobody will
abuse it again. commit-slab will be the way forward for associating
data to a commit.

As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
architecture) which should help reduce memory usage for reachability
test a bit. This is also what commit-slab is invented for [1].

[1] 96c4f4a370 (commit: allow associating auxiliary info on-demand -
2013-04-09)
---
 commit.h | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/commit.h b/commit.h
index 838f6a6b26..4432458367 100644
--- a/commit.h
+++ b/commit.h
@@ -16,9 +16,13 @@ struct commit_list {
 	struct commit_list *next;
 };
 
+/*
+ * The size of this struct matters in full repo walk operations like
+ * 'git clone' or 'git gc'. Consider using commit-slab to attach data
+ * to a commit instead of adding new fields here.
+ */
 struct commit {
 	struct object object;
-	void *util;
 	unsigned int index;
 	timestamp_t date;
 	struct commit_list *parents;
-- 
2.17.0.705.g3525833791

Re: [PATCH 00/12] Die commit->util, die!

[Stefan Beller]

On Sat, May 12, 2018 at 1:00 AM, Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
> There's not much to write here. It's basically a copy from 12/12:
>
> This 'util' pointer can be used for many different purposes,
> controlled in different ways. Some are not even contained in a command
> code, but buried deep in common code with no clue who will use it and
> how. For example, if revs.show_source is set, then it's used for
> storing path name, but if you happen to call get_merge_parent() then
> some 'util' may end up storing another thing.

This is cool! It makes life easy when it comes to clearing up commits
in the object store (as it is unclear what the util pointer is used for
we leaked that memory so far in the object store conversion series).

> The move to using commit-slab gives us a much better picture of how
> some piece of data is associated with a commit and what for. Since
> nobody uses 'util' pointer anymore, we can retire it so that nobody will
> abuse it again. commit-slab will be the way forward for associating
> data to a commit.
>
> As a side benefit, this shrinks struct commit by 8 bytes (on 64-bit
> architecture) which should help reduce memory usage for reachability
> test a bit. This is also what commit-slab is invented for [1].

The object store series (called -lookup-final) is at a point where
I have to move one of the slabs (buffer_slab in commit.c) into
the repository or rather into the parsed_object_pool in object.h.

So I think I'll build a series on top of this one first, which allows
for not just defining the slabs all over the place, but actually allows
them to be embedded into other structs.

Then I merge that series with origin/sb/object-store-graft and build
the -final series on top of that.

Stefan