git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / Atom feed
* [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements
@ 2019-08-26  2:43 Eric Wong
  2019-08-26  2:43 ` [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent Eric Wong
                   ` (10 more replies)
  0 siblings, 11 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This started out as yak-shaving exercise to introduce the
"container_of" macro to make hashmap more flexible and
less error-prone.

So far I've ended up finding and fixing two real bugs in
patches 1/11 and 2/11 which should be fast-tracked.

Patches 3-9 are straightforward safety fixes to prevent future
bugs of the same type.

10-11 are work-in-progress changes to remove the limitation
of hashmap_entry being the first member of a struct.  It's
also part of my ongoing agenda to spread Linux kernel idioms
into userspace and maybe get git.git hackers more comfortable
with kernel hacking (and vice-versa :>)

I'll try to continue the rest within the next few days.


The following changes since commit 745f6812895b31c02b29bdfe4ae8e5498f776c26:

  First batch after Git 2.23 (2019-08-22 12:41:04 -0700)

are available in the Git repository at:

  https://80x24.org/git-svn.git hashmap-wip-v1

for you to fetch changes up to 4d9857917670218cba447caddec15a2734c86e2c:

  hashmap_get_next returns "struct hashmap_entry *" (2019-08-26 02:25:35 +0000)

----------------------------------------------------------------
Eric Wong (11):
      diff: use hashmap_entry_init on moved_entry.ent
      packfile: use hashmap_entry in delta_base_cache_entry
      hashmap_entry_init takes "struct hashmap_entry *"
      hashmap_entry: detect improper initialization
      hashmap_get_next takes "const struct hashmap_entry *"
      hashmap_add takes "struct hashmap_entry *"
      hashmap_get takes "const struct hashmap_entry *"
      hashmap_remove takes "const struct hashmap_entry *"
      hashmap_put takes "struct hashmap_entry *"
      introduce container_of macro
      hashmap_get_next returns "struct hashmap_entry *"

 attr.c                              |  8 +++----
 blame.c                             | 12 +++++-----
 builtin/describe.c                  |  4 ++--
 builtin/difftool.c                  | 17 +++++++-------
 builtin/fast-export.c               |  9 ++++----
 builtin/fetch.c                     |  4 ++--
 config.c                            |  8 +++----
 diff.c                              | 23 ++++++++++++-------
 diffcore-rename.c                   | 15 ++++++++-----
 git-compat-util.h                   | 10 +++++++++
 hashmap.c                           | 30 ++++++++++++++-----------
 hashmap.h                           | 45 +++++++++++++++++++++----------------
 merge-recursive.c                   | 27 +++++++++++-----------
 name-hash.c                         | 41 +++++++++++++++++----------------
 oidmap.c                            |  2 +-
 packfile.c                          |  8 +++----
 patch-ids.c                         |  6 ++---
 range-diff.c                        |  8 +++----
 ref-filter.c                        |  5 +++--
 refs.c                              |  7 ++++--
 remote.c                            |  8 ++++---
 revision.c                          |  9 ++++----
 sequencer.c                         |  9 ++++----
 sub-process.c                       | 10 ++++-----
 submodule-config.c                  | 20 ++++++++---------
 t/helper/test-hashmap.c             | 24 +++++++++++---------
 t/helper/test-lazy-init-name-hash.c |  4 ++--
 27 files changed, 210 insertions(+), 163 deletions(-)

^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-27 13:31   ` Derrick Stolee
  2019-08-26  2:43 ` [PATCH 02/11] packfile: use hashmap_entry in delta_base_cache_entry Eric Wong
                   ` (9 subsequent siblings)
  10 siblings, 1 reply; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

Otherwise, the hashmap_entry.next field appears to remain
uninitialized, which can lead to problems when
add_lines_to_move_detection calls hashmap_add.

I found this through manual inspection when converting
hashmap_add callers to take "struct hashmap_entry *".

Signed-off-by: Eric Wong <e@80x24.org>
---
 diff.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/diff.c b/diff.c
index efe42b341a..02491ee684 100644
--- a/diff.c
+++ b/diff.c
@@ -964,8 +964,9 @@ static struct moved_entry *prepare_entry(struct diff_options *o,
 	struct moved_entry *ret = xmalloc(sizeof(*ret));
 	struct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no];
 	unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS;
+	unsigned int hash = xdiff_hash_string(l->line, l->len, flags);
 
-	ret->ent.hash = xdiff_hash_string(l->line, l->len, flags);
+	hashmap_entry_init(&ret->ent, hash);
 	ret->es = l;
 	ret->next_line = NULL;
 
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 02/11] packfile: use hashmap_entry in delta_base_cache_entry
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
  2019-08-26  2:43 ` [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-26  2:43 ` [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *" Eric Wong
                   ` (8 subsequent siblings)
  10 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This hashmap_entry_init function is intended to take a
hashmap_entry struct pointer, not a hashmap struct pointer.

This was not noticed because hashmap_entry_init takes a "void *"
arg instead of "struct hashmap_entry *", and the hashmap struct
is larger and can be cast into a hashmap_entry struct without
data corruption.

This has the beneficial side effect of reducing the size of
a delta_base_cache_entry from 104 bytes to 72 bytes on 64-bit
systems.

Signed-off-by: Eric Wong <e@80x24.org>
---
 packfile.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/packfile.c b/packfile.c
index fc43a6c52c..37fe0b73a6 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1361,7 +1361,7 @@ struct delta_base_cache_key {
 };
 
 struct delta_base_cache_entry {
-	struct hashmap hash;
+	struct hashmap_entry ent;
 	struct delta_base_cache_key key;
 	struct list_head lru;
 	void *data;
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
  2019-08-26  2:43 ` [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent Eric Wong
  2019-08-26  2:43 ` [PATCH 02/11] packfile: use hashmap_entry in delta_base_cache_entry Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-27 13:35   ` Derrick Stolee
  2019-08-26  2:43 ` [PATCH 04/11] hashmap_entry: detect improper initialization Eric Wong
                   ` (7 subsequent siblings)
  10 siblings, 1 reply; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

C compilers do type checking to make life easier for us.  So
rely on that and update all hashmap_entry_init callers to take
"struct hashmap_entry *" to avoid future bugs while improving
safety and readability.

Signed-off-by: Eric Wong <e@80x24.org>
---
 attr.c                  |  4 ++--
 blame.c                 |  2 +-
 builtin/describe.c      |  2 +-
 builtin/difftool.c      |  6 +++---
 builtin/fast-export.c   |  2 +-
 builtin/fetch.c         |  2 +-
 config.c                |  4 ++--
 diffcore-rename.c       |  2 +-
 hashmap.c               |  4 ++--
 hashmap.h               | 12 ++++++------
 merge-recursive.c       | 13 +++++++------
 name-hash.c             | 10 +++++-----
 packfile.c              |  2 +-
 patch-ids.c             |  2 +-
 range-diff.c            |  4 ++--
 ref-filter.c            |  3 ++-
 refs.c                  |  2 +-
 remote.c                |  2 +-
 revision.c              |  4 ++--
 sequencer.c             |  5 +++--
 sub-process.c           |  4 ++--
 submodule-config.c      | 10 +++++-----
 t/helper/test-hashmap.c |  6 +++---
 23 files changed, 55 insertions(+), 52 deletions(-)

diff --git a/attr.c b/attr.c
index 93dc16b59c..a8be7a7b4f 100644
--- a/attr.c
+++ b/attr.c
@@ -98,7 +98,7 @@ static void *attr_hashmap_get(struct attr_hashmap *map,
 	if (!map->map.tablesize)
 		attr_hashmap_init(map);
 
-	hashmap_entry_init(&k, memhash(key, keylen));
+	hashmap_entry_init(&k.ent, memhash(key, keylen));
 	k.key = key;
 	k.keylen = keylen;
 	e = hashmap_get(&map->map, &k, NULL);
@@ -117,7 +117,7 @@ static void attr_hashmap_add(struct attr_hashmap *map,
 		attr_hashmap_init(map);
 
 	e = xmalloc(sizeof(struct attr_hash_entry));
-	hashmap_entry_init(e, memhash(key, keylen));
+	hashmap_entry_init(&e->ent, memhash(key, keylen));
 	e->key = key;
 	e->keylen = keylen;
 	e->value = value;
diff --git a/blame.c b/blame.c
index 36a2e7ef11..46059410cd 100644
--- a/blame.c
+++ b/blame.c
@@ -417,7 +417,7 @@ static void get_fingerprint(struct fingerprint *result,
 		/* Ignore whitespace pairs */
 		if (hash == 0)
 			continue;
-		hashmap_entry_init(entry, hash);
+		hashmap_entry_init(&entry->entry, hash);
 
 		found_entry = hashmap_get(&result->map, entry, NULL);
 		if (found_entry) {
diff --git a/builtin/describe.c b/builtin/describe.c
index 200154297d..596ddf89a5 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -123,7 +123,7 @@ static void add_to_known_names(const char *path,
 		if (!e) {
 			e = xmalloc(sizeof(struct commit_name));
 			oidcpy(&e->peeled, peeled);
-			hashmap_entry_init(e, oidhash(peeled));
+			hashmap_entry_init(&e->entry, oidhash(peeled));
 			hashmap_add(&names, e);
 			e->path = NULL;
 		}
diff --git a/builtin/difftool.c b/builtin/difftool.c
index 16eb8b70ea..98ffc04c61 100644
--- a/builtin/difftool.c
+++ b/builtin/difftool.c
@@ -161,7 +161,7 @@ static void add_left_or_right(struct hashmap *map, const char *path,
 	struct pair_entry *e, *existing;
 
 	FLEX_ALLOC_STR(e, path, path);
-	hashmap_entry_init(e, strhash(path));
+	hashmap_entry_init(&e->entry, strhash(path));
 	existing = hashmap_get(map, e, NULL);
 	if (existing) {
 		free(e);
@@ -234,7 +234,7 @@ static void changed_files(struct hashmap *result, const char *index_path,
 	while (!strbuf_getline_nul(&buf, fp)) {
 		struct path_entry *entry;
 		FLEX_ALLOC_STR(entry, path, buf.buf);
-		hashmap_entry_init(entry, strhash(buf.buf));
+		hashmap_entry_init(&entry->entry, strhash(buf.buf));
 		hashmap_add(result, entry);
 	}
 	fclose(fp);
@@ -461,7 +461,7 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,
 
 			/* Avoid duplicate working_tree entries */
 			FLEX_ALLOC_STR(entry, path, dst_path);
-			hashmap_entry_init(entry, strhash(dst_path));
+			hashmap_entry_init(&entry->entry, strhash(dst_path));
 			if (hashmap_get(&working_tree_dups, entry, NULL)) {
 				free(entry);
 				continue;
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index f541f55d33..287dbd24a3 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -148,7 +148,7 @@ static const void *anonymize_mem(struct hashmap *map,
 	if (!map->cmpfn)
 		hashmap_init(map, anonymized_entry_cmp, NULL, 0);
 
-	hashmap_entry_init(&key, memhash(orig, *len));
+	hashmap_entry_init(&key.hash, memhash(orig, *len));
 	key.orig = orig;
 	key.orig_len = *len;
 	ret = hashmap_get(map, &key, NULL);
diff --git a/builtin/fetch.c b/builtin/fetch.c
index 717dd14e89..b7d70eee70 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -276,7 +276,7 @@ static struct refname_hash_entry *refname_hash_add(struct hashmap *map,
 	size_t len = strlen(refname);
 
 	FLEX_ALLOC_MEM(ent, refname, refname, len);
-	hashmap_entry_init(ent, strhash(refname));
+	hashmap_entry_init(&ent->ent, strhash(refname));
 	oidcpy(&ent->oid, oid);
 	hashmap_add(map, ent);
 	return ent;
diff --git a/config.c b/config.c
index 3900e4947b..08d866e7de 100644
--- a/config.c
+++ b/config.c
@@ -1861,7 +1861,7 @@ static struct config_set_element *configset_find_element(struct config_set *cs,
 	if (git_config_parse_key(key, &normalized_key, NULL))
 		return NULL;
 
-	hashmap_entry_init(&k, strhash(normalized_key));
+	hashmap_entry_init(&k.ent, strhash(normalized_key));
 	k.key = normalized_key;
 	found_entry = hashmap_get(&cs->config_hash, &k, NULL);
 	free(normalized_key);
@@ -1882,7 +1882,7 @@ static int configset_add_value(struct config_set *cs, const char *key, const cha
 	 */
 	if (!e) {
 		e = xmalloc(sizeof(*e));
-		hashmap_entry_init(e, strhash(key));
+		hashmap_entry_init(&e->ent, strhash(key));
 		e->key = xstrdup(key);
 		string_list_init(&e->value_list, 1);
 		hashmap_add(&cs->config_hash, e);
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 9624864858..44a3ab1e31 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -329,7 +329,7 @@ static void insert_file_table(struct repository *r,
 	entry->index = index;
 	entry->filespec = filespec;
 
-	hashmap_entry_init(entry, hash_filespec(r, filespec));
+	hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
 	hashmap_add(table, entry);
 }
 
diff --git a/hashmap.c b/hashmap.c
index d42f01ff5a..6818c65174 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -293,13 +293,13 @@ const void *memintern(const void *data, size_t len)
 		hashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0);
 
 	/* lookup interned string in pool */
-	hashmap_entry_init(&key, memhash(data, len));
+	hashmap_entry_init(&key.ent, memhash(data, len));
 	key.len = len;
 	e = hashmap_get(&map, &key, data);
 	if (!e) {
 		/* not found: create it */
 		FLEX_ALLOC_MEM(e, data, data, len);
-		hashmap_entry_init(e, key.ent.hash);
+		hashmap_entry_init(&e->ent, key.ent.hash);
 		e->len = len;
 		hashmap_add(&map, e);
 	}
diff --git a/hashmap.h b/hashmap.h
index 8424911566..3d7939c291 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -48,14 +48,14 @@
  *         if (!strcmp("add", action)) {
  *             struct long2string *e;
  *             FLEX_ALLOC_STR(e, value, value);
- *             hashmap_entry_init(e, memhash(&key, sizeof(long)));
+ *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
  *             e->key = key;
  *             hashmap_add(&map, e);
  *         }
  *
  *         if (!strcmp("print_all_by_key", action)) {
  *             struct long2string k, *e;
- *             hashmap_entry_init(&k, memhash(&key, sizeof(long)));
+ *             hashmap_entry_init(&k->ent, memhash(&key, sizeof(long)));
  *             k.key = key;
  *
  *             flags &= ~COMPARE_VALUE;
@@ -70,7 +70,7 @@
  *         if (!strcmp("has_exact_match", action)) {
  *             struct long2string *e;
  *             FLEX_ALLOC_STR(e, value, value);
- *             hashmap_entry_init(e, memhash(&key, sizeof(long)));
+ *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
  *             e->key = key;
  *
  *             flags |= COMPARE_VALUE;
@@ -80,7 +80,7 @@
  *
  *         if (!strcmp("has_exact_match_no_heap_alloc", action)) {
  *             struct long2string k;
- *             hashmap_entry_init(&k, memhash(&key, sizeof(long)));
+ *             hashmap_entry_init(&k->ent, memhash(&key, sizeof(long)));
  *             k.key = key;
  *
  *             flags |= COMPARE_VALUE;
@@ -244,9 +244,9 @@ void hashmap_free(struct hashmap *map, int free_entries);
  * your structure was allocated with xmalloc(), you can just free(3) it,
  * and if it is on stack, you can just let it go out of scope).
  */
-static inline void hashmap_entry_init(void *entry, unsigned int hash)
+static inline void
+hashmap_entry_init(struct hashmap_entry *e, unsigned int hash)
 {
-	struct hashmap_entry *e = entry;
 	e->hash = hash;
 	e->next = NULL;
 }
diff --git a/merge-recursive.c b/merge-recursive.c
index 6b812d67e3..6bc4f14ff4 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -61,7 +61,7 @@ static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap,
 
 	if (dir == NULL)
 		return NULL;
-	hashmap_entry_init(&key, strhash(dir));
+	hashmap_entry_init(&key.ent, strhash(dir));
 	key.dir = dir;
 	return hashmap_get(hashmap, &key, NULL);
 }
@@ -85,7 +85,7 @@ static void dir_rename_init(struct hashmap *map)
 static void dir_rename_entry_init(struct dir_rename_entry *entry,
 				  char *directory)
 {
-	hashmap_entry_init(entry, strhash(directory));
+	hashmap_entry_init(&entry->ent, strhash(directory));
 	entry->dir = directory;
 	entry->non_unique_new_dir = 0;
 	strbuf_init(&entry->new_dir, 0);
@@ -97,7 +97,7 @@ static struct collision_entry *collision_find_entry(struct hashmap *hashmap,
 {
 	struct collision_entry key;
 
-	hashmap_entry_init(&key, strhash(target_file));
+	hashmap_entry_init(&key.ent, strhash(target_file));
 	key.target_file = target_file;
 	return hashmap_get(hashmap, &key, NULL);
 }
@@ -454,7 +454,7 @@ static int save_files_dirs(const struct object_id *oid,
 	strbuf_addstr(base, path);
 
 	FLEX_ALLOC_MEM(entry, path, base->buf, base->len);
-	hashmap_entry_init(entry, path_hash(entry->path));
+	hashmap_entry_init(&entry->e, path_hash(entry->path));
 	hashmap_add(&opt->current_file_dir_set, entry);
 
 	strbuf_setlen(base, baselen);
@@ -731,7 +731,7 @@ static char *unique_path(struct merge_options *opt, const char *path, const char
 	}
 
 	FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);
-	hashmap_entry_init(entry, path_hash(entry->path));
+	hashmap_entry_init(&entry->e, path_hash(entry->path));
 	hashmap_add(&opt->current_file_dir_set, entry);
 	return strbuf_detach(&newpath, NULL);
 }
@@ -2358,7 +2358,8 @@ static void compute_collisions(struct hashmap *collisions,
 		if (!collision_ent) {
 			collision_ent = xcalloc(1,
 						sizeof(struct collision_entry));
-			hashmap_entry_init(collision_ent, strhash(new_path));
+			hashmap_entry_init(&collision_ent->ent,
+						strhash(new_path));
 			hashmap_put(collisions, collision_ent);
 			collision_ent->target_file = new_path;
 		} else {
diff --git a/name-hash.c b/name-hash.c
index 695908609f..1ce1417f7e 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -33,7 +33,7 @@ static struct dir_entry *find_dir_entry__hash(struct index_state *istate,
 		const char *name, unsigned int namelen, unsigned int hash)
 {
 	struct dir_entry key;
-	hashmap_entry_init(&key, hash);
+	hashmap_entry_init(&key.ent, hash);
 	key.namelen = namelen;
 	return hashmap_get(&istate->dir_hash, &key, name);
 }
@@ -68,7 +68,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 	if (!dir) {
 		/* not found, create it and add to hash table */
 		FLEX_ALLOC_MEM(dir, name, ce->name, namelen);
-		hashmap_entry_init(dir, memihash(ce->name, namelen));
+		hashmap_entry_init(&dir->ent, memihash(ce->name, namelen));
 		dir->namelen = namelen;
 		hashmap_add(&istate->dir_hash, dir);
 
@@ -106,7 +106,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 	if (ce->ce_flags & CE_HASHED)
 		return;
 	ce->ce_flags |= CE_HASHED;
-	hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));
+	hashmap_entry_init(&ce->ent, memihash(ce->name, ce_namelen(ce)));
 	hashmap_add(&istate->name_hash, ce);
 
 	if (ignore_case)
@@ -280,7 +280,7 @@ static struct dir_entry *hash_dir_entry_with_parent_and_prefix(
 	dir = find_dir_entry__hash(istate, prefix->buf, prefix->len, hash);
 	if (!dir) {
 		FLEX_ALLOC_MEM(dir, name, prefix->buf, prefix->len);
-		hashmap_entry_init(dir, hash);
+		hashmap_entry_init(&dir->ent, hash);
 		dir->namelen = prefix->len;
 		dir->parent = parent;
 		hashmap_add(&istate->dir_hash, dir);
@@ -472,7 +472,7 @@ static void *lazy_name_thread_proc(void *_data)
 	for (k = 0; k < d->istate->cache_nr; k++) {
 		struct cache_entry *ce_k = d->istate->cache[k];
 		ce_k->ce_flags |= CE_HASHED;
-		hashmap_entry_init(ce_k, d->lazy_entries[k].hash_name);
+		hashmap_entry_init(&ce_k->ent, d->lazy_entries[k].hash_name);
 		hashmap_add(&d->istate->name_hash, ce_k);
 	}
 
diff --git a/packfile.c b/packfile.c
index 37fe0b73a6..96535eb86b 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1487,7 +1487,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 
 	if (!delta_base_cache.cmpfn)
 		hashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);
-	hashmap_entry_init(ent, pack_entry_hash(p, base_offset));
+	hashmap_entry_init(&ent->ent, pack_entry_hash(p, base_offset));
 	hashmap_add(&delta_base_cache, ent);
 }
 
diff --git a/patch-ids.c b/patch-ids.c
index e8c150d0c9..a2da711678 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -83,7 +83,7 @@ static int init_patch_id_entry(struct patch_id *patch,
 	if (commit_patch_id(commit, &ids->diffopts, &header_only_patch_id, 1, 0))
 		return -1;
 
-	hashmap_entry_init(patch, oidhash(&header_only_patch_id));
+	hashmap_entry_init(&patch->ent, oidhash(&header_only_patch_id));
 	return 0;
 }
 
diff --git a/range-diff.c b/range-diff.c
index ba1e9a4265..32b29f9594 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -217,7 +217,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)
 		util->i = i;
 		util->patch = a->items[i].string;
 		util->diff = util->patch + util->diff_offset;
-		hashmap_entry_init(util, strhash(util->diff));
+		hashmap_entry_init(&util->e, strhash(util->diff));
 		hashmap_add(&map, util);
 	}
 
@@ -228,7 +228,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)
 		util->i = i;
 		util->patch = b->items[i].string;
 		util->diff = util->patch + util->diff_offset;
-		hashmap_entry_init(util, strhash(util->diff));
+		hashmap_entry_init(&util->e, strhash(util->diff));
 		other = hashmap_remove(&map, util, NULL);
 		if (other) {
 			if (other->matching >= 0)
diff --git a/ref-filter.c b/ref-filter.c
index f27cfc8c3e..206014c93d 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1565,7 +1565,8 @@ static void populate_worktree_map(struct hashmap *map, struct worktree **worktre
 			struct ref_to_worktree_entry *entry;
 			entry = xmalloc(sizeof(*entry));
 			entry->wt = worktrees[i];
-			hashmap_entry_init(entry, strhash(worktrees[i]->head_ref));
+			hashmap_entry_init(&entry->ent,
+					strhash(worktrees[i]->head_ref));
 
 			hashmap_add(map, entry);
 		}
diff --git a/refs.c b/refs.c
index cd297ee4bd..c43ec59c6e 100644
--- a/refs.c
+++ b/refs.c
@@ -1796,7 +1796,7 @@ static struct ref_store_hash_entry *alloc_ref_store_hash_entry(
 	struct ref_store_hash_entry *entry;
 
 	FLEX_ALLOC_STR(entry, name, name);
-	hashmap_entry_init(entry, strhash(name));
+	hashmap_entry_init(&entry->ent, strhash(name));
 	entry->refs = refs;
 	return entry;
 }
diff --git a/remote.c b/remote.c
index e50f7602ed..bd81cb71bc 100644
--- a/remote.c
+++ b/remote.c
@@ -158,7 +158,7 @@ static struct remote *make_remote(const char *name, int len)
 	ALLOC_GROW(remotes, remotes_nr + 1, remotes_alloc);
 	remotes[remotes_nr++] = ret;
 
-	hashmap_entry_init(ret, lookup_entry.hash);
+	hashmap_entry_init(&ret->ent, lookup_entry.hash);
 	replaced = hashmap_put(&remotes_hash, ret);
 	assert(replaced == NULL);  /* no previous entry overwritten */
 	return ret;
diff --git a/revision.c b/revision.c
index 07412297f0..3461c78883 100644
--- a/revision.c
+++ b/revision.c
@@ -141,7 +141,7 @@ static void paths_and_oids_insert(struct hashmap *map,
 	struct path_and_oids_entry key;
 	struct path_and_oids_entry *entry;
 
-	hashmap_entry_init(&key, hash);
+	hashmap_entry_init(&key.ent, hash);
 
 	/* use a shallow copy for the lookup */
 	key.path = (char *)path;
@@ -149,7 +149,7 @@ static void paths_and_oids_insert(struct hashmap *map,
 
 	if (!(entry = (struct path_and_oids_entry *)hashmap_get(map, &key, NULL))) {
 		entry = xcalloc(1, sizeof(struct path_and_oids_entry));
-		hashmap_entry_init(entry, hash);
+		hashmap_entry_init(&entry->ent, hash);
 		entry->path = xstrdup(key.path);
 		oidset_init(&entry->trees, 16);
 		hashmap_put(map, entry);
diff --git a/sequencer.c b/sequencer.c
index 34ebf8ed94..1140cdf526 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -4538,7 +4538,7 @@ static const char *label_oid(struct object_id *oid, const char *label,
 	}
 
 	FLEX_ALLOC_STR(labels_entry, label, label);
-	hashmap_entry_init(labels_entry, strihash(label));
+	hashmap_entry_init(&labels_entry->entry, strihash(label));
 	hashmap_add(&state->labels, labels_entry);
 
 	FLEX_ALLOC_STR(string_entry, string, label);
@@ -5252,7 +5252,8 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 						strhash(subject), subject)) {
 			FLEX_ALLOC_MEM(entry, subject, subject, subject_len);
 			entry->i = i;
-			hashmap_entry_init(entry, strhash(entry->subject));
+			hashmap_entry_init(&entry->entry,
+					strhash(entry->subject));
 			hashmap_put(&subject2item, entry);
 		}
 	}
diff --git a/sub-process.c b/sub-process.c
index 3f4af93555..9847dad6fc 100644
--- a/sub-process.c
+++ b/sub-process.c
@@ -20,7 +20,7 @@ struct subprocess_entry *subprocess_find_entry(struct hashmap *hashmap, const ch
 {
 	struct subprocess_entry key;
 
-	hashmap_entry_init(&key, strhash(cmd));
+	hashmap_entry_init(&key.ent, strhash(cmd));
 	key.cmd = cmd;
 	return hashmap_get(hashmap, &key, NULL);
 }
@@ -96,7 +96,7 @@ int subprocess_start(struct hashmap *hashmap, struct subprocess_entry *entry, co
 		return err;
 	}
 
-	hashmap_entry_init(entry, strhash(cmd));
+	hashmap_entry_init(&entry->ent, strhash(cmd));
 
 	err = startfn(entry);
 	if (err) {
diff --git a/submodule-config.c b/submodule-config.c
index 4264ee216f..4aa02e280e 100644
--- a/submodule-config.c
+++ b/submodule-config.c
@@ -123,7 +123,7 @@ static void cache_put_path(struct submodule_cache *cache,
 	unsigned int hash = hash_oid_string(&submodule->gitmodules_oid,
 					    submodule->path);
 	struct submodule_entry *e = xmalloc(sizeof(*e));
-	hashmap_entry_init(e, hash);
+	hashmap_entry_init(&e->ent, hash);
 	e->config = submodule;
 	hashmap_put(&cache->for_path, e);
 }
@@ -135,7 +135,7 @@ static void cache_remove_path(struct submodule_cache *cache,
 					    submodule->path);
 	struct submodule_entry e;
 	struct submodule_entry *removed;
-	hashmap_entry_init(&e, hash);
+	hashmap_entry_init(&e.ent, hash);
 	e.config = submodule;
 	removed = hashmap_remove(&cache->for_path, &e, NULL);
 	free(removed);
@@ -147,7 +147,7 @@ static void cache_add(struct submodule_cache *cache,
 	unsigned int hash = hash_oid_string(&submodule->gitmodules_oid,
 					    submodule->name);
 	struct submodule_entry *e = xmalloc(sizeof(*e));
-	hashmap_entry_init(e, hash);
+	hashmap_entry_init(&e->ent, hash);
 	e->config = submodule;
 	hashmap_add(&cache->for_name, e);
 }
@@ -163,7 +163,7 @@ static const struct submodule *cache_lookup_path(struct submodule_cache *cache,
 	oidcpy(&key_config.gitmodules_oid, gitmodules_oid);
 	key_config.path = path;
 
-	hashmap_entry_init(&key, hash);
+	hashmap_entry_init(&key.ent, hash);
 	key.config = &key_config;
 
 	entry = hashmap_get(&cache->for_path, &key, NULL);
@@ -183,7 +183,7 @@ static struct submodule *cache_lookup_name(struct submodule_cache *cache,
 	oidcpy(&key_config.gitmodules_oid, gitmodules_oid);
 	key_config.name = name;
 
-	hashmap_entry_init(&key, hash);
+	hashmap_entry_init(&key.ent, hash);
 	key.config = &key_config;
 
 	entry = hashmap_get(&cache->for_name, &key, NULL);
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index aaf17b0ddf..0c9fd7c996 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -37,7 +37,7 @@ static struct test_entry *alloc_test_entry(unsigned int hash,
 	size_t klen = strlen(key);
 	size_t vlen = strlen(value);
 	struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
-	hashmap_entry_init(entry, hash);
+	hashmap_entry_init(&entry->ent, hash);
 	memcpy(entry->key, key, klen + 1);
 	memcpy(entry->key + klen + 1, value, vlen + 1);
 	return entry;
@@ -103,7 +103,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 
 			/* add entries */
 			for (i = 0; i < TEST_SIZE; i++) {
-				hashmap_entry_init(entries[i], hashes[i]);
+				hashmap_entry_init(&entries[i]->ent, hashes[i]);
 				hashmap_add(&map, entries[i]);
 			}
 
@@ -116,7 +116,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 		/* fill the map (sparsely if specified) */
 		j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;
 		for (i = 0; i < j; i++) {
-			hashmap_entry_init(entries[i], hashes[i]);
+			hashmap_entry_init(&entries[i]->ent, hashes[i]);
 			hashmap_add(&map, entries[i]);
 		}
 
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (2 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *" Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-27  9:10   ` Johannes Schindelin
  2019-09-08  7:49   ` [RFC 04/11] coccicheck: detect hashmap_entry.hash assignment Eric Wong
  2019-08-26  2:43 ` [PATCH 05/11] hashmap_get_next takes "const struct hashmap_entry *" Eric Wong
                   ` (6 subsequent siblings)
  10 siblings, 2 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

By renaming the "hash" field to "_hash", it's easy to spot
improper initialization of hashmap_entry structs which
can leave "hashmap_entry.next" uninitialized.

Signed-off-by: Eric Wong <e@80x24.org>
---
 builtin/fast-export.c               | 5 +++--
 hashmap.c                           | 9 +++++----
 hashmap.h                           | 4 ++--
 name-hash.c                         | 9 +++++----
 remote.c                            | 6 ++++--
 t/helper/test-lazy-init-name-hash.c | 4 ++--
 6 files changed, 21 insertions(+), 16 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 287dbd24a3..f30a92a4d3 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -144,18 +144,19 @@ static const void *anonymize_mem(struct hashmap *map,
 				 const void *orig, size_t *len)
 {
 	struct anonymized_entry key, *ret;
+	unsigned int hash = memhash(orig, *len);
 
 	if (!map->cmpfn)
 		hashmap_init(map, anonymized_entry_cmp, NULL, 0);
 
-	hashmap_entry_init(&key.hash, memhash(orig, *len));
+	hashmap_entry_init(&key.hash, hash);
 	key.orig = orig;
 	key.orig_len = *len;
 	ret = hashmap_get(map, &key, NULL);
 
 	if (!ret) {
 		ret = xmalloc(sizeof(*ret));
-		hashmap_entry_init(&ret->hash, key.hash.hash);
+		hashmap_entry_init(&ret->hash, hash);
 		ret->orig = xstrdup(orig);
 		ret->orig_len = *len;
 		ret->anon = generate(orig, len);
diff --git a/hashmap.c b/hashmap.c
index 6818c65174..777beda347 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -96,14 +96,14 @@ static inline int entry_equals(const struct hashmap *map,
 		const void *keydata)
 {
 	return (e1 == e2) ||
-	       (e1->hash == e2->hash &&
+	       (e1->_hash == e2->_hash &&
 		!map->cmpfn(map->cmpfn_data, e1, e2, keydata));
 }
 
 static inline unsigned int bucket(const struct hashmap *map,
 		const struct hashmap_entry *key)
 {
-	return key->hash & (map->tablesize - 1);
+	return key->_hash & (map->tablesize - 1);
 }
 
 int hashmap_bucket(const struct hashmap *map, unsigned int hash)
@@ -287,19 +287,20 @@ const void *memintern(const void *data, size_t len)
 {
 	static struct hashmap map;
 	struct pool_entry key, *e;
+	unsigned int hash = memhash(data, len);
 
 	/* initialize string pool hashmap */
 	if (!map.tablesize)
 		hashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0);
 
 	/* lookup interned string in pool */
-	hashmap_entry_init(&key.ent, memhash(data, len));
+	hashmap_entry_init(&key.ent, hash);
 	key.len = len;
 	e = hashmap_get(&map, &key, data);
 	if (!e) {
 		/* not found: create it */
 		FLEX_ALLOC_MEM(e, data, data, len);
-		hashmap_entry_init(&e->ent, key.ent.hash);
+		hashmap_entry_init(&e->ent, hash);
 		e->len = len;
 		hashmap_add(&map, e);
 	}
diff --git a/hashmap.h b/hashmap.h
index 3d7939c291..d635e0815a 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -145,7 +145,7 @@ struct hashmap_entry {
 	struct hashmap_entry *next;
 
 	/* entry's hash code */
-	unsigned int hash;
+	unsigned int _hash;
 };
 
 /*
@@ -247,7 +247,7 @@ void hashmap_free(struct hashmap *map, int free_entries);
 static inline void
 hashmap_entry_init(struct hashmap_entry *e, unsigned int hash)
 {
-	e->hash = hash;
+	e->_hash = hash;
 	e->next = NULL;
 }
 
diff --git a/name-hash.c b/name-hash.c
index 1ce1417f7e..8b33c5cb59 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -268,7 +268,7 @@ static struct dir_entry *hash_dir_entry_with_parent_and_prefix(
 	assert((parent != NULL) ^ (strchr(prefix->buf, '/') == NULL));
 
 	if (parent)
-		hash = memihash_cont(parent->ent.hash,
+		hash = memihash_cont(parent->ent._hash,
 			prefix->buf + parent->namelen,
 			prefix->len - parent->namelen);
 	else
@@ -289,7 +289,8 @@ static struct dir_entry *hash_dir_entry_with_parent_and_prefix(
 			unlock_dir_mutex(lock_nr);
 
 			/* All I really need here is an InterlockedIncrement(&(parent->nr)) */
-			lock_nr = compute_dir_lock_nr(&istate->dir_hash, parent->ent.hash);
+			lock_nr = compute_dir_lock_nr(&istate->dir_hash,
+							parent->ent._hash);
 			lock_dir_mutex(lock_nr);
 			parent->nr++;
 		}
@@ -427,10 +428,10 @@ static int handle_range_1(
 		lazy_entries[k].dir = parent;
 		if (parent) {
 			lazy_entries[k].hash_name = memihash_cont(
-				parent->ent.hash,
+				parent->ent._hash,
 				ce_k->name + parent->namelen,
 				ce_namelen(ce_k) - parent->namelen);
-			lazy_entries[k].hash_dir = parent->ent.hash;
+			lazy_entries[k].hash_dir = parent->ent._hash;
 		} else {
 			lazy_entries[k].hash_name = memihash(ce_k->name, ce_namelen(ce_k));
 		}
diff --git a/remote.c b/remote.c
index bd81cb71bc..dc09172e9d 100644
--- a/remote.c
+++ b/remote.c
@@ -136,6 +136,7 @@ static struct remote *make_remote(const char *name, int len)
 	struct remote *ret, *replaced;
 	struct remotes_hash_key lookup;
 	struct hashmap_entry lookup_entry;
+	unsigned int hash;
 
 	if (!len)
 		len = strlen(name);
@@ -143,7 +144,8 @@ static struct remote *make_remote(const char *name, int len)
 	init_remotes_hash();
 	lookup.str = name;
 	lookup.len = len;
-	hashmap_entry_init(&lookup_entry, memhash(name, len));
+	hash = memhash(name, len);
+	hashmap_entry_init(&lookup_entry, hash);
 
 	if ((ret = hashmap_get(&remotes_hash, &lookup_entry, &lookup)) != NULL)
 		return ret;
@@ -158,7 +160,7 @@ static struct remote *make_remote(const char *name, int len)
 	ALLOC_GROW(remotes, remotes_nr + 1, remotes_alloc);
 	remotes[remotes_nr++] = ret;
 
-	hashmap_entry_init(&ret->ent, lookup_entry.hash);
+	hashmap_entry_init(&ret->ent, hash);
 	replaced = hashmap_put(&remotes_hash, ret);
 	assert(replaced == NULL);  /* no previous entry overwritten */
 	return ret;
diff --git a/t/helper/test-lazy-init-name-hash.c b/t/helper/test-lazy-init-name-hash.c
index b99a37080d..d01ea0e526 100644
--- a/t/helper/test-lazy-init-name-hash.c
+++ b/t/helper/test-lazy-init-name-hash.c
@@ -43,13 +43,13 @@ static void dump_run(void)
 
 	dir = hashmap_iter_first(&the_index.dir_hash, &iter_dir);
 	while (dir) {
-		printf("dir %08x %7d %s\n", dir->ent.hash, dir->nr, dir->name);
+		printf("dir %08x %7d %s\n", dir->ent._hash, dir->nr, dir->name);
 		dir = hashmap_iter_next(&iter_dir);
 	}
 
 	ce = hashmap_iter_first(&the_index.name_hash, &iter_cache);
 	while (ce) {
-		printf("name %08x %s\n", ce->ent.hash, ce->name);
+		printf("name %08x %s\n", ce->ent._hash, ce->name);
 		ce = hashmap_iter_next(&iter_cache);
 	}
 
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 05/11] hashmap_get_next takes "const struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (3 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 04/11] hashmap_entry: detect improper initialization Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-26  2:43 ` [PATCH 06/11] hashmap_add takes "struct " Eric Wong
                   ` (5 subsequent siblings)
  10 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This is less error-prone than "const void *" as the compiler
now detects invalid types being passed.

Signed-off-by: Eric Wong <e@80x24.org>
---
 diff.c                  | 5 +++--
 diffcore-rename.c       | 2 +-
 hashmap.c               | 5 +++--
 hashmap.h               | 3 ++-
 name-hash.c             | 2 +-
 t/helper/test-hashmap.c | 2 +-
 6 files changed, 11 insertions(+), 8 deletions(-)

diff --git a/diff.c b/diff.c
index 02491ee684..1168f0cbb9 100644
--- a/diff.c
+++ b/diff.c
@@ -1036,7 +1036,7 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o,
 	int i;
 	char *got_match = xcalloc(1, pmb_nr);
 
-	for (; match; match = hashmap_get_next(hm, match)) {
+	for (; match; match = hashmap_get_next(hm, &match->ent)) {
 		for (i = 0; i < pmb_nr; i++) {
 			struct moved_entry *prev = pmb[i].match;
 			struct moved_entry *cur = (prev && prev->next_line) ?
@@ -1189,7 +1189,8 @@ static void mark_color_as_moved(struct diff_options *o,
 			 * The current line is the start of a new block.
 			 * Setup the set of potential blocks.
 			 */
-			for (; match; match = hashmap_get_next(hm, match)) {
+			for (; match; match = hashmap_get_next(hm,
+								&match->ent)) {
 				ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc);
 				if (o->color_moved_ws_handling &
 				    COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) {
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 44a3ab1e31..2a1449013b 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -285,7 +285,7 @@ static int find_identical_files(struct hashmap *srcs,
 	p = hashmap_get_from_hash(srcs,
 				  hash_filespec(options->repo, target),
 				  NULL);
-	for (; p; p = hashmap_get_next(srcs, p)) {
+	for (; p; p = hashmap_get_next(srcs, &p->entry)) {
 		int score;
 		struct diff_filespec *source = p->filespec;
 
diff --git a/hashmap.c b/hashmap.c
index 777beda347..958a7dfe14 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -191,9 +191,10 @@ void *hashmap_get(const struct hashmap *map, const void *key, const void *keydat
 	return *find_entry_ptr(map, key, keydata);
 }
 
-void *hashmap_get_next(const struct hashmap *map, const void *entry)
+void *hashmap_get_next(const struct hashmap *map,
+			const struct hashmap_entry *entry)
 {
-	struct hashmap_entry *e = ((struct hashmap_entry *) entry)->next;
+	struct hashmap_entry *e = entry->next;
 	for (; e; e = e->next)
 		if (entry_equals(map, entry, e, NULL))
 			return e;
diff --git a/hashmap.h b/hashmap.h
index d635e0815a..8f55782dc9 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -318,7 +318,8 @@ static inline void *hashmap_get_from_hash(const struct hashmap *map,
  * `entry` is the hashmap_entry to start the search from, obtained via a previous
  * call to `hashmap_get` or `hashmap_get_next`.
  */
-void *hashmap_get_next(const struct hashmap *map, const void *entry);
+void *hashmap_get_next(const struct hashmap *map,
+			const struct hashmap_entry *entry);
 
 /*
  * Adds a hashmap entry. This allows to add duplicate entries (i.e.
diff --git a/name-hash.c b/name-hash.c
index 8b33c5cb59..e90660c94f 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -711,7 +711,7 @@ struct cache_entry *index_file_exists(struct index_state *istate, const char *na
 	while (ce) {
 		if (same_name(ce, name, namelen, icase))
 			return ce;
-		ce = hashmap_get_next(&istate->name_hash, ce);
+		ce = hashmap_get_next(&istate->name_hash, &ce->ent);
 	}
 	return NULL;
 }
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 0c9fd7c996..bf063a2521 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -203,7 +203,7 @@ int cmd__hashmap(int argc, const char **argv)
 				puts("NULL");
 			while (entry) {
 				puts(get_value(entry));
-				entry = hashmap_get_next(&map, entry);
+				entry = hashmap_get_next(&map, &entry->ent);
 			}
 
 		} else if (!strcmp("remove", cmd) && p1) {
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 06/11] hashmap_add takes "struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (4 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 05/11] hashmap_get_next takes "const struct hashmap_entry *" Eric Wong
@ 2019-08-26  2:43 ` " Eric Wong
  2019-08-26  2:43 ` [PATCH 07/11] hashmap_get takes "const struct " Eric Wong
                   ` (4 subsequent siblings)
  10 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This is less error-prone than "void *" as the compiler now
detects invalid types being passed.

Signed-off-by: Eric Wong <e@80x24.org>
---
 attr.c                  | 2 +-
 blame.c                 | 2 +-
 builtin/describe.c      | 2 +-
 builtin/difftool.c      | 6 +++---
 builtin/fetch.c         | 2 +-
 config.c                | 2 +-
 diff.c                  | 2 +-
 diffcore-rename.c       | 2 +-
 hashmap.c               | 6 +++---
 hashmap.h               | 4 ++--
 merge-recursive.c       | 4 ++--
 name-hash.c             | 8 ++++----
 packfile.c              | 2 +-
 patch-ids.c             | 2 +-
 range-diff.c            | 2 +-
 ref-filter.c            | 2 +-
 sequencer.c             | 2 +-
 sub-process.c           | 2 +-
 submodule-config.c      | 2 +-
 t/helper/test-hashmap.c | 6 +++---
 20 files changed, 31 insertions(+), 31 deletions(-)

diff --git a/attr.c b/attr.c
index a8be7a7b4f..fa26a3e3cb 100644
--- a/attr.c
+++ b/attr.c
@@ -122,7 +122,7 @@ static void attr_hashmap_add(struct attr_hashmap *map,
 	e->keylen = keylen;
 	e->value = value;
 
-	hashmap_add(&map->map, e);
+	hashmap_add(&map->map, &e->ent);
 }
 
 struct all_attrs_item {
diff --git a/blame.c b/blame.c
index 46059410cd..4d20aee435 100644
--- a/blame.c
+++ b/blame.c
@@ -424,7 +424,7 @@ static void get_fingerprint(struct fingerprint *result,
 			found_entry->count += 1;
 		} else {
 			entry->count = 1;
-			hashmap_add(&result->map, entry);
+			hashmap_add(&result->map, &entry->entry);
 			++entry;
 		}
 	}
diff --git a/builtin/describe.c b/builtin/describe.c
index 596ddf89a5..f5e0a7e033 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -124,7 +124,7 @@ static void add_to_known_names(const char *path,
 			e = xmalloc(sizeof(struct commit_name));
 			oidcpy(&e->peeled, peeled);
 			hashmap_entry_init(&e->entry, oidhash(peeled));
-			hashmap_add(&names, e);
+			hashmap_add(&names, &e->entry);
 			e->path = NULL;
 		}
 		e->tag = tag;
diff --git a/builtin/difftool.c b/builtin/difftool.c
index 98ffc04c61..82c146718d 100644
--- a/builtin/difftool.c
+++ b/builtin/difftool.c
@@ -168,7 +168,7 @@ static void add_left_or_right(struct hashmap *map, const char *path,
 		e = existing;
 	} else {
 		e->left[0] = e->right[0] = '\0';
-		hashmap_add(map, e);
+		hashmap_add(map, &e->entry);
 	}
 	strlcpy(is_right ? e->right : e->left, content, PATH_MAX);
 }
@@ -235,7 +235,7 @@ static void changed_files(struct hashmap *result, const char *index_path,
 		struct path_entry *entry;
 		FLEX_ALLOC_STR(entry, path, buf.buf);
 		hashmap_entry_init(&entry->entry, strhash(buf.buf));
-		hashmap_add(result, entry);
+		hashmap_add(result, &entry->entry);
 	}
 	fclose(fp);
 	if (finish_command(&diff_files))
@@ -466,7 +466,7 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,
 				free(entry);
 				continue;
 			}
-			hashmap_add(&working_tree_dups, entry);
+			hashmap_add(&working_tree_dups, &entry->entry);
 
 			if (!use_wt_file(workdir, dst_path, &roid)) {
 				if (checkout_path(rmode, &roid, dst_path,
diff --git a/builtin/fetch.c b/builtin/fetch.c
index b7d70eee70..909dbde909 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -278,7 +278,7 @@ static struct refname_hash_entry *refname_hash_add(struct hashmap *map,
 	FLEX_ALLOC_MEM(ent, refname, refname, len);
 	hashmap_entry_init(&ent->ent, strhash(refname));
 	oidcpy(&ent->oid, oid);
-	hashmap_add(map, ent);
+	hashmap_add(map, &ent->ent);
 	return ent;
 }
 
diff --git a/config.c b/config.c
index 08d866e7de..2243d7c3d6 100644
--- a/config.c
+++ b/config.c
@@ -1885,7 +1885,7 @@ static int configset_add_value(struct config_set *cs, const char *key, const cha
 		hashmap_entry_init(&e->ent, strhash(key));
 		e->key = xstrdup(key);
 		string_list_init(&e->value_list, 1);
-		hashmap_add(&cs->config_hash, e);
+		hashmap_add(&cs->config_hash, &e->ent);
 	}
 	si = string_list_append_nodup(&e->value_list, xstrdup_or_null(value));
 
diff --git a/diff.c b/diff.c
index 1168f0cbb9..cc7f06d10d 100644
--- a/diff.c
+++ b/diff.c
@@ -1003,7 +1003,7 @@ static void add_lines_to_move_detection(struct diff_options *o,
 		if (prev_line && prev_line->es->s == o->emitted_symbols->buf[n].s)
 			prev_line->next_line = key;
 
-		hashmap_add(hm, key);
+		hashmap_add(hm, &key->ent);
 		prev_line = key;
 	}
 }
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 2a1449013b..4670a40179 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -330,7 +330,7 @@ static void insert_file_table(struct repository *r,
 	entry->filespec = filespec;
 
 	hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
-	hashmap_add(table, entry);
+	hashmap_add(table, &entry->entry);
 }
 
 /*
diff --git a/hashmap.c b/hashmap.c
index 958a7dfe14..1aa1324c3e 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -201,12 +201,12 @@ void *hashmap_get_next(const struct hashmap *map,
 	return NULL;
 }
 
-void hashmap_add(struct hashmap *map, void *entry)
+void hashmap_add(struct hashmap *map, struct hashmap_entry *entry)
 {
 	unsigned int b = bucket(map, entry);
 
 	/* add entry */
-	((struct hashmap_entry *) entry)->next = map->table[b];
+	entry->next = map->table[b];
 	map->table[b] = entry;
 
 	/* fix size and rehash if appropriate */
@@ -303,7 +303,7 @@ const void *memintern(const void *data, size_t len)
 		FLEX_ALLOC_MEM(e, data, data, len);
 		hashmap_entry_init(&e->ent, hash);
 		e->len = len;
-		hashmap_add(&map, e);
+		hashmap_add(&map, &e->ent);
 	}
 	return e->data;
 }
diff --git a/hashmap.h b/hashmap.h
index 8f55782dc9..6a2fdf451b 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -50,7 +50,7 @@
  *             FLEX_ALLOC_STR(e, value, value);
  *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
  *             e->key = key;
- *             hashmap_add(&map, e);
+ *             hashmap_add(&map, &e->ent);
  *         }
  *
  *         if (!strcmp("print_all_by_key", action)) {
@@ -328,7 +328,7 @@ void *hashmap_get_next(const struct hashmap *map,
  * `map` is the hashmap structure.
  * `entry` is the entry to add.
  */
-void hashmap_add(struct hashmap *map, void *entry);
+void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
 
 /*
  * Adds or replaces a hashmap entry. If the hashmap contains duplicate
diff --git a/merge-recursive.c b/merge-recursive.c
index 6bc4f14ff4..db9b247ece 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -455,7 +455,7 @@ static int save_files_dirs(const struct object_id *oid,
 
 	FLEX_ALLOC_MEM(entry, path, base->buf, base->len);
 	hashmap_entry_init(&entry->e, path_hash(entry->path));
-	hashmap_add(&opt->current_file_dir_set, entry);
+	hashmap_add(&opt->current_file_dir_set, &entry->e);
 
 	strbuf_setlen(base, baselen);
 	return (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);
@@ -732,7 +732,7 @@ static char *unique_path(struct merge_options *opt, const char *path, const char
 
 	FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);
 	hashmap_entry_init(&entry->e, path_hash(entry->path));
-	hashmap_add(&opt->current_file_dir_set, entry);
+	hashmap_add(&opt->current_file_dir_set, &entry->e);
 	return strbuf_detach(&newpath, NULL);
 }
 
diff --git a/name-hash.c b/name-hash.c
index e90660c94f..def3576a8b 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -70,7 +70,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 		FLEX_ALLOC_MEM(dir, name, ce->name, namelen);
 		hashmap_entry_init(&dir->ent, memihash(ce->name, namelen));
 		dir->namelen = namelen;
-		hashmap_add(&istate->dir_hash, dir);
+		hashmap_add(&istate->dir_hash, &dir->ent);
 
 		/* recursively add missing parent directories */
 		dir->parent = hash_dir_entry(istate, ce, namelen);
@@ -107,7 +107,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 		return;
 	ce->ce_flags |= CE_HASHED;
 	hashmap_entry_init(&ce->ent, memihash(ce->name, ce_namelen(ce)));
-	hashmap_add(&istate->name_hash, ce);
+	hashmap_add(&istate->name_hash, &ce->ent);
 
 	if (ignore_case)
 		add_dir_entry(istate, ce);
@@ -283,7 +283,7 @@ static struct dir_entry *hash_dir_entry_with_parent_and_prefix(
 		hashmap_entry_init(&dir->ent, hash);
 		dir->namelen = prefix->len;
 		dir->parent = parent;
-		hashmap_add(&istate->dir_hash, dir);
+		hashmap_add(&istate->dir_hash, &dir->ent);
 
 		if (parent) {
 			unlock_dir_mutex(lock_nr);
@@ -474,7 +474,7 @@ static void *lazy_name_thread_proc(void *_data)
 		struct cache_entry *ce_k = d->istate->cache[k];
 		ce_k->ce_flags |= CE_HASHED;
 		hashmap_entry_init(&ce_k->ent, d->lazy_entries[k].hash_name);
-		hashmap_add(&d->istate->name_hash, ce_k);
+		hashmap_add(&d->istate->name_hash, &ce_k->ent);
 	}
 
 	return NULL;
diff --git a/packfile.c b/packfile.c
index 96535eb86b..f7402c470b 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1488,7 +1488,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 	if (!delta_base_cache.cmpfn)
 		hashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);
 	hashmap_entry_init(&ent->ent, pack_entry_hash(p, base_offset));
-	hashmap_add(&delta_base_cache, ent);
+	hashmap_add(&delta_base_cache, &ent->ent);
 }
 
 int packed_object_info(struct repository *r, struct packed_git *p,
diff --git a/patch-ids.c b/patch-ids.c
index a2da711678..f87b62bf58 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -116,6 +116,6 @@ struct patch_id *add_commit_patch_id(struct commit *commit,
 		return NULL;
 	}
 
-	hashmap_add(&ids->patches, key);
+	hashmap_add(&ids->patches, &key->ent);
 	return key;
 }
diff --git a/range-diff.c b/range-diff.c
index 32b29f9594..96f955d84d 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -218,7 +218,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)
 		util->patch = a->items[i].string;
 		util->diff = util->patch + util->diff_offset;
 		hashmap_entry_init(&util->e, strhash(util->diff));
-		hashmap_add(&map, util);
+		hashmap_add(&map, &util->e);
 	}
 
 	/* Now try to find exact matches in b */
diff --git a/ref-filter.c b/ref-filter.c
index 206014c93d..d939ebc6bb 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1568,7 +1568,7 @@ static void populate_worktree_map(struct hashmap *map, struct worktree **worktre
 			hashmap_entry_init(&entry->ent,
 					strhash(worktrees[i]->head_ref));
 
-			hashmap_add(map, entry);
+			hashmap_add(map, &entry->ent);
 		}
 	}
 }
diff --git a/sequencer.c b/sequencer.c
index 1140cdf526..ee11cda7e7 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -4539,7 +4539,7 @@ static const char *label_oid(struct object_id *oid, const char *label,
 
 	FLEX_ALLOC_STR(labels_entry, label, label);
 	hashmap_entry_init(&labels_entry->entry, strihash(label));
-	hashmap_add(&state->labels, labels_entry);
+	hashmap_add(&state->labels, &labels_entry->entry);
 
 	FLEX_ALLOC_STR(string_entry, string, label);
 	oidcpy(&string_entry->entry.oid, oid);
diff --git a/sub-process.c b/sub-process.c
index 9847dad6fc..d58e069855 100644
--- a/sub-process.c
+++ b/sub-process.c
@@ -105,7 +105,7 @@ int subprocess_start(struct hashmap *hashmap, struct subprocess_entry *entry, co
 		return err;
 	}
 
-	hashmap_add(hashmap, entry);
+	hashmap_add(hashmap, &entry->ent);
 	return 0;
 }
 
diff --git a/submodule-config.c b/submodule-config.c
index 4aa02e280e..a3bbd9fd6f 100644
--- a/submodule-config.c
+++ b/submodule-config.c
@@ -149,7 +149,7 @@ static void cache_add(struct submodule_cache *cache,
 	struct submodule_entry *e = xmalloc(sizeof(*e));
 	hashmap_entry_init(&e->ent, hash);
 	e->config = submodule;
-	hashmap_add(&cache->for_name, e);
+	hashmap_add(&cache->for_name, &e->ent);
 }
 
 static const struct submodule *cache_lookup_path(struct submodule_cache *cache,
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index bf063a2521..49e715f1cd 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -104,7 +104,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 			/* add entries */
 			for (i = 0; i < TEST_SIZE; i++) {
 				hashmap_entry_init(&entries[i]->ent, hashes[i]);
-				hashmap_add(&map, entries[i]);
+				hashmap_add(&map, &entries[i]->ent);
 			}
 
 			hashmap_free(&map, 0);
@@ -117,7 +117,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 		j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;
 		for (i = 0; i < j; i++) {
 			hashmap_entry_init(&entries[i]->ent, hashes[i]);
-			hashmap_add(&map, entries[i]);
+			hashmap_add(&map, &entries[i]->ent);
 		}
 
 		for (j = 0; j < rounds; j++) {
@@ -179,7 +179,7 @@ int cmd__hashmap(int argc, const char **argv)
 			entry = alloc_test_entry(hash, p1, p2);
 
 			/* add to hashmap */
-			hashmap_add(&map, entry);
+			hashmap_add(&map, &entry->ent);
 
 		} else if (!strcmp("put", cmd) && p1 && p2) {
 
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 07/11] hashmap_get takes "const struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (5 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 06/11] hashmap_add takes "struct " Eric Wong
@ 2019-08-26  2:43 ` " Eric Wong
  2019-08-26  2:43 ` [PATCH 08/11] hashmap_remove " Eric Wong
                   ` (3 subsequent siblings)
  10 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This is less error-prone than "const void *" as the compiler
now detects invalid types being passed.

Signed-off-by: Eric Wong <e@80x24.org>
---
 attr.c                | 2 +-
 blame.c               | 6 +++---
 builtin/difftool.c    | 5 +++--
 builtin/fast-export.c | 2 +-
 config.c              | 2 +-
 diff.c                | 4 ++--
 hashmap.c             | 5 +++--
 hashmap.h             | 8 +++++---
 merge-recursive.c     | 4 ++--
 name-hash.c           | 2 +-
 patch-ids.c           | 2 +-
 revision.c            | 3 ++-
 sub-process.c         | 2 +-
 submodule-config.c    | 4 ++--
 14 files changed, 28 insertions(+), 23 deletions(-)

diff --git a/attr.c b/attr.c
index fa26a3e3cb..9bdef61cc3 100644
--- a/attr.c
+++ b/attr.c
@@ -101,7 +101,7 @@ static void *attr_hashmap_get(struct attr_hashmap *map,
 	hashmap_entry_init(&k.ent, memhash(key, keylen));
 	k.key = key;
 	k.keylen = keylen;
-	e = hashmap_get(&map->map, &k, NULL);
+	e = hashmap_get(&map->map, &k.ent, NULL);
 
 	return e ? e->value : NULL;
 }
diff --git a/blame.c b/blame.c
index 4d20aee435..73ffb59403 100644
--- a/blame.c
+++ b/blame.c
@@ -419,7 +419,7 @@ static void get_fingerprint(struct fingerprint *result,
 			continue;
 		hashmap_entry_init(&entry->entry, hash);
 
-		found_entry = hashmap_get(&result->map, entry, NULL);
+		found_entry = hashmap_get(&result->map, &entry->entry, NULL);
 		if (found_entry) {
 			found_entry->count += 1;
 		} else {
@@ -452,7 +452,7 @@ static int fingerprint_similarity(struct fingerprint *a, struct fingerprint *b)
 	hashmap_iter_init(&b->map, &iter);
 
 	while ((entry_b = hashmap_iter_next(&iter))) {
-		if ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {
+		if ((entry_a = hashmap_get(&a->map, &entry_b->entry, NULL))) {
 			intersection += entry_a->count < entry_b->count ?
 					entry_a->count : entry_b->count;
 		}
@@ -471,7 +471,7 @@ static void fingerprint_subtract(struct fingerprint *a, struct fingerprint *b)
 	hashmap_iter_init(&b->map, &iter);
 
 	while ((entry_b = hashmap_iter_next(&iter))) {
-		if ((entry_a = hashmap_get(&a->map, entry_b, NULL))) {
+		if ((entry_a = hashmap_get(&a->map, &entry_b->entry, NULL))) {
 			if (entry_a->count <= entry_b->count)
 				hashmap_remove(&a->map, entry_b, NULL);
 			else
diff --git a/builtin/difftool.c b/builtin/difftool.c
index 82c146718d..f41298d199 100644
--- a/builtin/difftool.c
+++ b/builtin/difftool.c
@@ -162,7 +162,7 @@ static void add_left_or_right(struct hashmap *map, const char *path,
 
 	FLEX_ALLOC_STR(e, path, path);
 	hashmap_entry_init(&e->entry, strhash(path));
-	existing = hashmap_get(map, e, NULL);
+	existing = hashmap_get(map, &e->entry, NULL);
 	if (existing) {
 		free(e);
 		e = existing;
@@ -462,7 +462,8 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,
 			/* Avoid duplicate working_tree entries */
 			FLEX_ALLOC_STR(entry, path, dst_path);
 			hashmap_entry_init(&entry->entry, strhash(dst_path));
-			if (hashmap_get(&working_tree_dups, entry, NULL)) {
+			if (hashmap_get(&working_tree_dups, &entry->entry,
+					NULL)) {
 				free(entry);
 				continue;
 			}
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index f30a92a4d3..081cdd70c9 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -152,7 +152,7 @@ static const void *anonymize_mem(struct hashmap *map,
 	hashmap_entry_init(&key.hash, hash);
 	key.orig = orig;
 	key.orig_len = *len;
-	ret = hashmap_get(map, &key, NULL);
+	ret = hashmap_get(map, &key.hash, NULL);
 
 	if (!ret) {
 		ret = xmalloc(sizeof(*ret));
diff --git a/config.c b/config.c
index 2243d7c3d6..1a1b6675fd 100644
--- a/config.c
+++ b/config.c
@@ -1863,7 +1863,7 @@ static struct config_set_element *configset_find_element(struct config_set *cs,
 
 	hashmap_entry_init(&k.ent, strhash(normalized_key));
 	k.key = normalized_key;
-	found_entry = hashmap_get(&cs->config_hash, &k, NULL);
+	found_entry = hashmap_get(&cs->config_hash, &k.ent, NULL);
 	free(normalized_key);
 	return found_entry;
 }
diff --git a/diff.c b/diff.c
index cc7f06d10d..72d3c6aa19 100644
--- a/diff.c
+++ b/diff.c
@@ -1144,13 +1144,13 @@ static void mark_color_as_moved(struct diff_options *o,
 		case DIFF_SYMBOL_PLUS:
 			hm = del_lines;
 			key = prepare_entry(o, n);
-			match = hashmap_get(hm, key, NULL);
+			match = hashmap_get(hm, &key->ent, NULL);
 			free(key);
 			break;
 		case DIFF_SYMBOL_MINUS:
 			hm = add_lines;
 			key = prepare_entry(o, n);
-			match = hashmap_get(hm, key, NULL);
+			match = hashmap_get(hm, &key->ent, NULL);
 			free(key);
 			break;
 		default:
diff --git a/hashmap.c b/hashmap.c
index 1aa1324c3e..f02ac41758 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -186,7 +186,8 @@ void hashmap_free(struct hashmap *map, int free_entries)
 	memset(map, 0, sizeof(*map));
 }
 
-void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)
+void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
+		const void *keydata)
 {
 	return *find_entry_ptr(map, key, keydata);
 }
@@ -297,7 +298,7 @@ const void *memintern(const void *data, size_t len)
 	/* lookup interned string in pool */
 	hashmap_entry_init(&key.ent, hash);
 	key.len = len;
-	e = hashmap_get(&map, &key, data);
+	e = hashmap_get(&map, &key.ent, data);
 	if (!e) {
 		/* not found: create it */
 		FLEX_ALLOC_MEM(e, data, data, len);
diff --git a/hashmap.h b/hashmap.h
index 6a2fdf451b..dea369868d 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -74,7 +74,8 @@
  *             e->key = key;
  *
  *             flags |= COMPARE_VALUE;
- *             printf("%sfound\n", hashmap_get(&map, e, NULL) ? "" : "not ");
+ *             printf("%sfound\n",
+ *                    hashmap_get(&map, &e->ent, NULL) ? "" : "not ");
  *             free(e);
  *         }
  *
@@ -84,7 +85,8 @@
  *             k.key = key;
  *
  *             flags |= COMPARE_VALUE;
- *             printf("%sfound\n", hashmap_get(&map, &k, value) ? "" : "not ");
+ *             printf("%sfound\n",
+ *                    hashmap_get(&map, &k->ent, value) ? "" : "not ");
  *         }
  *
  *         if (!strcmp("end", action)) {
@@ -286,7 +288,7 @@ static inline unsigned int hashmap_get_size(struct hashmap *map)
  * If an entry with matching hash code is found, `key` and `keydata` are passed
  * to `hashmap_cmp_fn` to decide whether the entry matches the key.
  */
-void *hashmap_get(const struct hashmap *map, const void *key,
+void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
 			 const void *keydata);
 
 /*
diff --git a/merge-recursive.c b/merge-recursive.c
index db9b247ece..2d31a3e279 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -63,7 +63,7 @@ static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap,
 		return NULL;
 	hashmap_entry_init(&key.ent, strhash(dir));
 	key.dir = dir;
-	return hashmap_get(hashmap, &key, NULL);
+	return hashmap_get(hashmap, &key.ent, NULL);
 }
 
 static int dir_rename_cmp(const void *unused_cmp_data,
@@ -99,7 +99,7 @@ static struct collision_entry *collision_find_entry(struct hashmap *hashmap,
 
 	hashmap_entry_init(&key.ent, strhash(target_file));
 	key.target_file = target_file;
-	return hashmap_get(hashmap, &key, NULL);
+	return hashmap_get(hashmap, &key.ent, NULL);
 }
 
 static int collision_cmp(void *unused_cmp_data,
diff --git a/name-hash.c b/name-hash.c
index def3576a8b..7368913613 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -35,7 +35,7 @@ static struct dir_entry *find_dir_entry__hash(struct index_state *istate,
 	struct dir_entry key;
 	hashmap_entry_init(&key.ent, hash);
 	key.namelen = namelen;
-	return hashmap_get(&istate->dir_hash, &key, name);
+	return hashmap_get(&istate->dir_hash, &key.ent, name);
 }
 
 static struct dir_entry *find_dir_entry(struct index_state *istate,
diff --git a/patch-ids.c b/patch-ids.c
index f87b62bf58..437f29e42c 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -99,7 +99,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,
 	if (init_patch_id_entry(&patch, commit, ids))
 		return NULL;
 
-	return hashmap_get(&ids->patches, &patch, NULL);
+	return hashmap_get(&ids->patches, &patch.ent, NULL);
 }
 
 struct patch_id *add_commit_patch_id(struct commit *commit,
diff --git a/revision.c b/revision.c
index 3461c78883..4336281286 100644
--- a/revision.c
+++ b/revision.c
@@ -147,7 +147,8 @@ static void paths_and_oids_insert(struct hashmap *map,
 	key.path = (char *)path;
 	oidset_init(&key.trees, 0);
 
-	if (!(entry = (struct path_and_oids_entry *)hashmap_get(map, &key, NULL))) {
+	entry = hashmap_get(map, &key.ent, NULL);
+	if (!entry) {
 		entry = xcalloc(1, sizeof(struct path_and_oids_entry));
 		hashmap_entry_init(&entry->ent, hash);
 		entry->path = xstrdup(key.path);
diff --git a/sub-process.c b/sub-process.c
index d58e069855..debd86bb68 100644
--- a/sub-process.c
+++ b/sub-process.c
@@ -22,7 +22,7 @@ struct subprocess_entry *subprocess_find_entry(struct hashmap *hashmap, const ch
 
 	hashmap_entry_init(&key.ent, strhash(cmd));
 	key.cmd = cmd;
-	return hashmap_get(hashmap, &key, NULL);
+	return hashmap_get(hashmap, &key.ent, NULL);
 }
 
 int subprocess_read_status(int fd, struct strbuf *status)
diff --git a/submodule-config.c b/submodule-config.c
index a3bbd9fd6f..58d585cd7d 100644
--- a/submodule-config.c
+++ b/submodule-config.c
@@ -166,7 +166,7 @@ static const struct submodule *cache_lookup_path(struct submodule_cache *cache,
 	hashmap_entry_init(&key.ent, hash);
 	key.config = &key_config;
 
-	entry = hashmap_get(&cache->for_path, &key, NULL);
+	entry = hashmap_get(&cache->for_path, &key.ent, NULL);
 	if (entry)
 		return entry->config;
 	return NULL;
@@ -186,7 +186,7 @@ static struct submodule *cache_lookup_name(struct submodule_cache *cache,
 	hashmap_entry_init(&key.ent, hash);
 	key.config = &key_config;
 
-	entry = hashmap_get(&cache->for_name, &key, NULL);
+	entry = hashmap_get(&cache->for_name, &key.ent, NULL);
 	if (entry)
 		return entry->config;
 	return NULL;
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 08/11] hashmap_remove takes "const struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (6 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 07/11] hashmap_get takes "const struct " Eric Wong
@ 2019-08-26  2:43 ` " Eric Wong
  2019-08-26  2:43 ` [PATCH 09/11] hashmap_put takes "struct " Eric Wong
                   ` (2 subsequent siblings)
  10 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This is less error-prone than "const void *" as the compiler
now detects invalid types being passed.

Signed-off-by: Eric Wong <e@80x24.org>
---
 blame.c            | 2 +-
 hashmap.c          | 3 ++-
 hashmap.h          | 2 +-
 merge-recursive.c  | 2 +-
 name-hash.c        | 4 ++--
 packfile.c         | 2 +-
 range-diff.c       | 2 +-
 sub-process.c      | 2 +-
 submodule-config.c | 2 +-
 9 files changed, 11 insertions(+), 10 deletions(-)

diff --git a/blame.c b/blame.c
index 73ffb59403..00f8f3fb0a 100644
--- a/blame.c
+++ b/blame.c
@@ -473,7 +473,7 @@ static void fingerprint_subtract(struct fingerprint *a, struct fingerprint *b)
 	while ((entry_b = hashmap_iter_next(&iter))) {
 		if ((entry_a = hashmap_get(&a->map, &entry_b->entry, NULL))) {
 			if (entry_a->count <= entry_b->count)
-				hashmap_remove(&a->map, entry_b, NULL);
+				hashmap_remove(&a->map, &entry_b->entry, NULL);
 			else
 				entry_a->count -= entry_b->count;
 		}
diff --git a/hashmap.c b/hashmap.c
index f02ac41758..efcb6420fc 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -218,7 +218,8 @@ void hashmap_add(struct hashmap *map, struct hashmap_entry *entry)
 	}
 }
 
-void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)
+void *hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
+		const void *keydata)
 {
 	struct hashmap_entry *old;
 	struct hashmap_entry **e = find_entry_ptr(map, key, keydata);
diff --git a/hashmap.h b/hashmap.h
index dea369868d..c8d5314667 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -349,7 +349,7 @@ void *hashmap_put(struct hashmap *map, void *entry);
  *
  * Argument explanation is the same as in `hashmap_get`.
  */
-void *hashmap_remove(struct hashmap *map, const void *key,
+void *hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
 		const void *keydata);
 
 /*
diff --git a/merge-recursive.c b/merge-recursive.c
index 2d31a3e279..f60451d396 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -2001,7 +2001,7 @@ static void remove_hashmap_entries(struct hashmap *dir_renames,
 
 	for (i = 0; i < items_to_remove->nr; i++) {
 		entry = items_to_remove->items[i].util;
-		hashmap_remove(dir_renames, entry, NULL);
+		hashmap_remove(dir_renames, &entry->ent, NULL);
 	}
 	string_list_clear(items_to_remove, 0);
 }
diff --git a/name-hash.c b/name-hash.c
index 7368913613..f64c52bfa2 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -95,7 +95,7 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
 	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
 	while (dir && !(--dir->nr)) {
 		struct dir_entry *parent = dir->parent;
-		hashmap_remove(&istate->dir_hash, dir, NULL);
+		hashmap_remove(&istate->dir_hash, &dir->ent, NULL);
 		free(dir);
 		dir = parent;
 	}
@@ -626,7 +626,7 @@ void remove_name_hash(struct index_state *istate, struct cache_entry *ce)
 	if (!istate->name_hash_initialized || !(ce->ce_flags & CE_HASHED))
 		return;
 	ce->ce_flags &= ~CE_HASHED;
-	hashmap_remove(&istate->name_hash, ce, ce);
+	hashmap_remove(&istate->name_hash, &ce->ent, ce);
 
 	if (ignore_case)
 		remove_dir_entry(istate, ce);
diff --git a/packfile.c b/packfile.c
index f7402c470b..3edd648de0 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1423,7 +1423,7 @@ static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
  */
 static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)
 {
-	hashmap_remove(&delta_base_cache, ent, &ent->key);
+	hashmap_remove(&delta_base_cache, &ent->ent, &ent->key);
 	list_del(&ent->lru);
 	delta_base_cached -= ent->size;
 	free(ent);
diff --git a/range-diff.c b/range-diff.c
index 96f955d84d..c51cfd5556 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -229,7 +229,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)
 		util->patch = b->items[i].string;
 		util->diff = util->patch + util->diff_offset;
 		hashmap_entry_init(&util->e, strhash(util->diff));
-		other = hashmap_remove(&map, util, NULL);
+		other = hashmap_remove(&map, &util->e, NULL);
 		if (other) {
 			if (other->matching >= 0)
 				BUG("already assigned!");
diff --git a/sub-process.c b/sub-process.c
index debd86bb68..99fccef592 100644
--- a/sub-process.c
+++ b/sub-process.c
@@ -58,7 +58,7 @@ void subprocess_stop(struct hashmap *hashmap, struct subprocess_entry *entry)
 	kill(entry->process.pid, SIGTERM);
 	finish_command(&entry->process);
 
-	hashmap_remove(hashmap, entry, NULL);
+	hashmap_remove(hashmap, &entry->ent, NULL);
 }
 
 static void subprocess_exit_handler(struct child_process *process)
diff --git a/submodule-config.c b/submodule-config.c
index 58d585cd7d..7486745a6a 100644
--- a/submodule-config.c
+++ b/submodule-config.c
@@ -137,7 +137,7 @@ static void cache_remove_path(struct submodule_cache *cache,
 	struct submodule_entry *removed;
 	hashmap_entry_init(&e.ent, hash);
 	e.config = submodule;
-	removed = hashmap_remove(&cache->for_path, &e, NULL);
+	removed = hashmap_remove(&cache->for_path, &e.ent, NULL);
 	free(removed);
 }
 
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 09/11] hashmap_put takes "struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (7 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 08/11] hashmap_remove " Eric Wong
@ 2019-08-26  2:43 ` " Eric Wong
  2019-08-26  2:43 ` [PATCH 10/11] introduce container_of macro Eric Wong
  2019-08-26  2:43 ` [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *" Eric Wong
  10 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This is less error-prone than "void *" as the compiler now
detects invalid types being passed.

Signed-off-by: Eric Wong <e@80x24.org>
---
 builtin/fast-export.c   | 2 +-
 hashmap.c               | 2 +-
 hashmap.h               | 2 +-
 merge-recursive.c       | 4 ++--
 oidmap.c                | 2 +-
 refs.c                  | 5 ++++-
 remote.c                | 2 +-
 revision.c              | 2 +-
 sequencer.c             | 2 +-
 submodule-config.c      | 2 +-
 t/helper/test-hashmap.c | 2 +-
 11 files changed, 15 insertions(+), 12 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 081cdd70c9..654bfce8d5 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -161,7 +161,7 @@ static const void *anonymize_mem(struct hashmap *map,
 		ret->orig_len = *len;
 		ret->anon = generate(orig, len);
 		ret->anon_len = *len;
-		hashmap_put(map, ret);
+		hashmap_put(map, &ret->hash);
 	}
 
 	*len = ret->anon_len;
diff --git a/hashmap.c b/hashmap.c
index efcb6420fc..2dd9912e13 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -241,7 +241,7 @@ void *hashmap_remove(struct hashmap *map, const struct hashmap_entry *key,
 	return old;
 }
 
-void *hashmap_put(struct hashmap *map, void *entry)
+void *hashmap_put(struct hashmap *map, struct hashmap_entry *entry)
 {
 	struct hashmap_entry *old = hashmap_remove(map, entry, NULL);
 	hashmap_add(map, entry);
diff --git a/hashmap.h b/hashmap.h
index c8d5314667..b62ee2e7b9 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -340,7 +340,7 @@ void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
  * `entry` is the entry to add or replace.
  * Returns the replaced entry, or NULL if not found (i.e. the entry was added).
  */
-void *hashmap_put(struct hashmap *map, void *entry);
+void *hashmap_put(struct hashmap *map, struct hashmap_entry *entry);
 
 /*
  * Removes a hashmap entry matching the specified key. If the hashmap contains
diff --git a/merge-recursive.c b/merge-recursive.c
index f60451d396..a685b4fb69 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -2229,7 +2229,7 @@ static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs)
 		if (!entry) {
 			entry = xmalloc(sizeof(*entry));
 			dir_rename_entry_init(entry, old_dir);
-			hashmap_put(dir_renames, entry);
+			hashmap_put(dir_renames, &entry->ent);
 		} else {
 			free(old_dir);
 		}
@@ -2360,7 +2360,7 @@ static void compute_collisions(struct hashmap *collisions,
 						sizeof(struct collision_entry));
 			hashmap_entry_init(&collision_ent->ent,
 						strhash(new_path));
-			hashmap_put(collisions, collision_ent);
+			hashmap_put(collisions, &collision_ent->ent);
 			collision_ent->target_file = new_path;
 		} else {
 			free(new_path);
diff --git a/oidmap.c b/oidmap.c
index 6d6e840d03..cd22b3a8bf 100644
--- a/oidmap.c
+++ b/oidmap.c
@@ -51,5 +51,5 @@ void *oidmap_put(struct oidmap *map, void *entry)
 		oidmap_init(map, 0);
 
 	hashmap_entry_init(&to_put->internal_entry, oidhash(&to_put->oid));
-	return hashmap_put(&map->map, to_put);
+	return hashmap_put(&map->map, &to_put->internal_entry);
 }
diff --git a/refs.c b/refs.c
index c43ec59c6e..3e55031256 100644
--- a/refs.c
+++ b/refs.c
@@ -1863,10 +1863,13 @@ static void register_ref_store_map(struct hashmap *map,
 				   struct ref_store *refs,
 				   const char *name)
 {
+	struct ref_store_hash_entry *entry;
+
 	if (!map->tablesize)
 		hashmap_init(map, ref_store_hash_cmp, NULL, 0);
 
-	if (hashmap_put(map, alloc_ref_store_hash_entry(name, refs)))
+	entry = alloc_ref_store_hash_entry(name, refs);
+	if (hashmap_put(map, &entry->ent))
 		BUG("%s ref_store '%s' initialized twice", type, name);
 }
 
diff --git a/remote.c b/remote.c
index dc09172e9d..248d60e0ad 100644
--- a/remote.c
+++ b/remote.c
@@ -161,7 +161,7 @@ static struct remote *make_remote(const char *name, int len)
 	remotes[remotes_nr++] = ret;
 
 	hashmap_entry_init(&ret->ent, hash);
-	replaced = hashmap_put(&remotes_hash, ret);
+	replaced = hashmap_put(&remotes_hash, &ret->ent);
 	assert(replaced == NULL);  /* no previous entry overwritten */
 	return ret;
 }
diff --git a/revision.c b/revision.c
index 4336281286..a7e2339064 100644
--- a/revision.c
+++ b/revision.c
@@ -153,7 +153,7 @@ static void paths_and_oids_insert(struct hashmap *map,
 		hashmap_entry_init(&entry->ent, hash);
 		entry->path = xstrdup(key.path);
 		oidset_init(&entry->trees, 16);
-		hashmap_put(map, entry);
+		hashmap_put(map, &entry->ent);
 	}
 
 	oidset_insert(&entry->trees, oid);
diff --git a/sequencer.c b/sequencer.c
index ee11cda7e7..b4ef70e260 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -5254,7 +5254,7 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 			entry->i = i;
 			hashmap_entry_init(&entry->entry,
 					strhash(entry->subject));
-			hashmap_put(&subject2item, entry);
+			hashmap_put(&subject2item, &entry->entry);
 		}
 	}
 
diff --git a/submodule-config.c b/submodule-config.c
index 7486745a6a..9248c5ea5b 100644
--- a/submodule-config.c
+++ b/submodule-config.c
@@ -125,7 +125,7 @@ static void cache_put_path(struct submodule_cache *cache,
 	struct submodule_entry *e = xmalloc(sizeof(*e));
 	hashmap_entry_init(&e->ent, hash);
 	e->config = submodule;
-	hashmap_put(&cache->for_path, e);
+	hashmap_put(&cache->for_path, &e->ent);
 }
 
 static void cache_remove_path(struct submodule_cache *cache,
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 49e715f1cd..de2bd083b9 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -187,7 +187,7 @@ int cmd__hashmap(int argc, const char **argv)
 			entry = alloc_test_entry(hash, p1, p2);
 
 			/* add / replace entry */
-			entry = hashmap_put(&map, entry);
+			entry = hashmap_put(&map, &entry->ent);
 
 			/* print and free replaced entry, if any */
 			puts(entry ? get_value(entry) : "NULL");
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 10/11] introduce container_of macro
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (8 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 09/11] hashmap_put takes "struct " Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-27 14:49   ` Derrick Stolee
  2019-08-26  2:43 ` [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *" Eric Wong
  10 siblings, 1 reply; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This macro is popular within the Linux kernel for supporting
intrusive data structures such as linked lists, red-black trees,
and chained hash tables while allowing the compiler to do
type checking.

I intend to use this to remove the limitation of "hashmap_entry"
being location-dependent and to allow more compile-time type
checking.

This macro already exists in our source as "list_entry" in
list.h and making "list_entry" an alias to "container_of"
as the Linux kernel has done is a possibility.

Signed-off-by: Eric Wong <e@80x24.org>
---
 git-compat-util.h | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/git-compat-util.h b/git-compat-util.h
index 83be89de0a..4cc2c8283a 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -1312,4 +1312,14 @@ void unleak_memory(const void *ptr, size_t len);
  */
 #include "banned.h"
 
+/*
+ * container_of - Get the address of an object containing a field.
+ *
+ * @ptr: pointer to the field.
+ * @type: type of the object.
+ * @member: name of the field within the object.
+ */
+#define container_of(ptr, type, member) \
+	((type *) ((char *)(ptr) - offsetof(type, member)))
+
 #endif
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *"
  2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
                   ` (9 preceding siblings ...)
  2019-08-26  2:43 ` [PATCH 10/11] introduce container_of macro Eric Wong
@ 2019-08-26  2:43 ` Eric Wong
  2019-08-27 14:53   ` Derrick Stolee
  10 siblings, 1 reply; 30+ messages in thread
From: Eric Wong @ 2019-08-26  2:43 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git

This is a step towards removing the requirement for
hashmap_entry being the first field of a struct.

Signed-off-by: Eric Wong <e@80x24.org>
---
 diff.c                  | 19 ++++++++++++-------
 diffcore-rename.c       | 11 +++++++----
 hashmap.c               |  2 +-
 hashmap.h               | 12 ++++++++----
 name-hash.c             |  8 +++++---
 t/helper/test-hashmap.c | 10 ++++++----
 6 files changed, 39 insertions(+), 23 deletions(-)

diff --git a/diff.c b/diff.c
index 72d3c6aa19..663b5d01f8 100644
--- a/diff.c
+++ b/diff.c
@@ -1035,8 +1035,10 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o,
 {
 	int i;
 	char *got_match = xcalloc(1, pmb_nr);
+	struct hashmap_entry *ent = &match->ent;
 
-	for (; match; match = hashmap_get_next(hm, &match->ent)) {
+	for (; ent; ent = hashmap_get_next(hm, ent)) {
+		match = container_of(ent, struct moved_entry, ent);
 		for (i = 0; i < pmb_nr; i++) {
 			struct moved_entry *prev = pmb[i].match;
 			struct moved_entry *cur = (prev && prev->next_line) ?
@@ -1135,8 +1137,9 @@ static void mark_color_as_moved(struct diff_options *o,
 
 	for (n = 0; n < o->emitted_symbols->nr; n++) {
 		struct hashmap *hm = NULL;
+		struct hashmap_entry *ent = NULL;
 		struct moved_entry *key;
-		struct moved_entry *match = NULL;
+		struct moved_entry *match;
 		struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n];
 		enum diff_symbol last_symbol = 0;
 
@@ -1144,20 +1147,20 @@ static void mark_color_as_moved(struct diff_options *o,
 		case DIFF_SYMBOL_PLUS:
 			hm = del_lines;
 			key = prepare_entry(o, n);
-			match = hashmap_get(hm, &key->ent, NULL);
+			ent = hashmap_get(hm, &key->ent, NULL);
 			free(key);
 			break;
 		case DIFF_SYMBOL_MINUS:
 			hm = add_lines;
 			key = prepare_entry(o, n);
-			match = hashmap_get(hm, &key->ent, NULL);
+			ent = hashmap_get(hm, &key->ent, NULL);
 			free(key);
 			break;
 		default:
 			flipped_block = 0;
 		}
 
-		if (!match) {
+		if (!ent) {
 			int i;
 
 			adjust_last_block(o, n, block_length);
@@ -1169,6 +1172,7 @@ static void mark_color_as_moved(struct diff_options *o,
 			last_symbol = l->s;
 			continue;
 		}
+		match = container_of(ent, struct moved_entry, ent);
 
 		if (o->color_moved == COLOR_MOVED_PLAIN) {
 			last_symbol = l->s;
@@ -1189,8 +1193,9 @@ static void mark_color_as_moved(struct diff_options *o,
 			 * The current line is the start of a new block.
 			 * Setup the set of potential blocks.
 			 */
-			for (; match; match = hashmap_get_next(hm,
-								&match->ent)) {
+			for (; ent; ent = hashmap_get_next(hm, ent)) {
+				match = container_of(ent, struct moved_entry,
+							ent);
 				ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc);
 				if (o->color_moved_ws_handling &
 				    COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) {
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 4670a40179..71aa240a68 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -274,7 +274,7 @@ static int find_identical_files(struct hashmap *srcs,
 				struct diff_options *options)
 {
 	int renames = 0;
-
+	struct hashmap_entry *ent;
 	struct diff_filespec *target = rename_dst[dst_index].two;
 	struct file_similarity *p, *best = NULL;
 	int i = 100, best_score = -1;
@@ -282,12 +282,15 @@ static int find_identical_files(struct hashmap *srcs,
 	/*
 	 * Find the best source match for specified destination.
 	 */
-	p = hashmap_get_from_hash(srcs,
+	ent = hashmap_get_from_hash(srcs,
 				  hash_filespec(options->repo, target),
 				  NULL);
-	for (; p; p = hashmap_get_next(srcs, &p->entry)) {
+	for (; ent; ent = hashmap_get_next(srcs, ent)) {
 		int score;
-		struct diff_filespec *source = p->filespec;
+		struct diff_filespec *source;
+
+		p = container_of(ent, struct file_similarity, entry);
+		source = p->filespec;
 
 		/* False hash collision? */
 		if (!oideq(&source->oid, &target->oid))
diff --git a/hashmap.c b/hashmap.c
index 2dd9912e13..d6434d9ca4 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -192,7 +192,7 @@ void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
 	return *find_entry_ptr(map, key, keydata);
 }
 
-void *hashmap_get_next(const struct hashmap *map,
+struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
 			const struct hashmap_entry *entry)
 {
 	struct hashmap_entry *e = entry->next;
diff --git a/hashmap.h b/hashmap.h
index b62ee2e7b9..25643dcdc4 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -55,15 +55,19 @@
  *
  *         if (!strcmp("print_all_by_key", action)) {
  *             struct long2string k, *e;
+ *             struct hashmap_entry *ent;
  *             hashmap_entry_init(&k->ent, memhash(&key, sizeof(long)));
  *             k.key = key;
  *
  *             flags &= ~COMPARE_VALUE;
- *             e = hashmap_get(&map, &k, NULL);
- *             if (e) {
+ *             ent = hashmap_get(&map, &k, NULL);
+ *             if (ent) {
+ *                 e = container_of(ent, struct long2string, ent);
  *                 printf("first: %ld %s\n", e->key, e->value);
- *                 while ((e = hashmap_get_next(&map, e)))
+ *                 while ((ent = hashmap_get_next(&map, ent))) {
+ *                     e = container_of(ent, struct long2string, ent);
  *                     printf("found more: %ld %s\n", e->key, e->value);
+ *                 }
  *             }
  *         }
  *
@@ -320,7 +324,7 @@ static inline void *hashmap_get_from_hash(const struct hashmap *map,
  * `entry` is the hashmap_entry to start the search from, obtained via a previous
  * call to `hashmap_get` or `hashmap_get_next`.
  */
-void *hashmap_get_next(const struct hashmap *map,
+struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
 			const struct hashmap_entry *entry);
 
 /*
diff --git a/name-hash.c b/name-hash.c
index f64c52bfa2..6f2779934f 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -703,15 +703,17 @@ void adjust_dirname_case(struct index_state *istate, char *name)
 struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)
 {
 	struct cache_entry *ce;
+	struct hashmap_entry *ent;
 
 	lazy_init_name_hash(istate);
 
-	ce = hashmap_get_from_hash(&istate->name_hash,
+	ent = hashmap_get_from_hash(&istate->name_hash,
 				   memihash(name, namelen), NULL);
-	while (ce) {
+	while (ent) {
+		ce = container_of(ent, struct cache_entry, ent);
 		if (same_name(ce, name, namelen, icase))
 			return ce;
-		ce = hashmap_get_next(&istate->name_hash, &ce->ent);
+		ent = hashmap_get_next(&istate->name_hash, ent);
 	}
 	return NULL;
 }
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index de2bd083b9..d85b8dc58e 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -194,16 +194,18 @@ int cmd__hashmap(int argc, const char **argv)
 			free(entry);
 
 		} else if (!strcmp("get", cmd) && p1) {
+			struct hashmap_entry *e;
 
 			/* lookup entry in hashmap */
-			entry = hashmap_get_from_hash(&map, hash, p1);
+			e = hashmap_get_from_hash(&map, hash, p1);
 
 			/* print result */
-			if (!entry)
+			if (!e)
 				puts("NULL");
-			while (entry) {
+			while (e) {
+				entry = container_of(e, struct test_entry, ent);
 				puts(get_value(entry));
-				entry = hashmap_get_next(&map, &entry->ent);
+				e = hashmap_get_next(&map, e);
 			}
 
 		} else if (!strcmp("remove", cmd) && p1) {
-- 
EW


^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-26  2:43 ` [PATCH 04/11] hashmap_entry: detect improper initialization Eric Wong
@ 2019-08-27  9:10   ` Johannes Schindelin
  2019-08-27  9:49     ` Eric Wong
  2019-09-08  7:49   ` [RFC 04/11] coccicheck: detect hashmap_entry.hash assignment Eric Wong
  1 sibling, 1 reply; 30+ messages in thread
From: Johannes Schindelin @ 2019-08-27  9:10 UTC (permalink / raw)
  To: Eric Wong; +Cc: Junio C Hamano, git

Hi Eric,

On Mon, 26 Aug 2019, Eric Wong wrote:

> By renaming the "hash" field to "_hash", it's easy to spot
> improper initialization of hashmap_entry structs which
> can leave "hashmap_entry.next" uninitialized.

Would you mind elaborating a bit? This explanation does not enlighten
me, sadly, all I see is that it makes it (slightly) harder for me to
maintain Git for Windows' patches on top of `pu`, as the FSCache patches
access that field directly (so even if they rebase cleanly, the build
breaks).

Ciao,
Dscho

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-27  9:10   ` Johannes Schindelin
@ 2019-08-27  9:49     ` Eric Wong
  2019-08-27 22:16       ` Junio C Hamano
  2019-08-28  9:03       ` Phillip Wood
  0 siblings, 2 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-27  9:49 UTC (permalink / raw)
  To: Johannes Schindelin; +Cc: Junio C Hamano, git

Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> Hi Eric,
> 
> On Mon, 26 Aug 2019, Eric Wong wrote:
> 
> > By renaming the "hash" field to "_hash", it's easy to spot
> > improper initialization of hashmap_entry structs which
> > can leave "hashmap_entry.next" uninitialized.
> 
> Would you mind elaborating a bit? This explanation does not enlighten
> me, sadly, all I see is that it makes it (slightly) harder for me to
> maintain Git for Windows' patches on top of `pu`, as the FSCache patches
> access that field directly (so even if they rebase cleanly, the build
> breaks).

I renamed it to intentionally break my build.

That way I could easily spot if there were any other improper
initializations of the .hash field.  It's fine to revert,
actually, it could be more of a "showing my work" patch.

(AFAIK, it's a pretty common practice, but maybe not here :x)

I've also pondered adding a
"hashmap_entry_hash(const struct hashmap_entry *)"
accessor method for reading the field value (but not setting
it), but it's a bit verbose...

I'm also wondering where/if hashmap offers a real benefit over
khash nowadays; the latter ought to have better locality.
Would like benchmark at some point in the future;
but safety fixes first :)

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent
  2019-08-26  2:43 ` [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent Eric Wong
@ 2019-08-27 13:31   ` Derrick Stolee
  0 siblings, 0 replies; 30+ messages in thread
From: Derrick Stolee @ 2019-08-27 13:31 UTC (permalink / raw)
  To: Eric Wong, Junio C Hamano; +Cc: git

On 8/25/2019 10:43 PM, Eric Wong wrote:
> Otherwise, the hashmap_entry.next field appears to remain
> uninitialized, which can lead to problems when
> add_lines_to_move_detection calls hashmap_add.
> 
> I found this through manual inspection when converting
> hashmap_add callers to take "struct hashmap_entry *".
> 
> Signed-off-by: Eric Wong <e@80x24.org>
> ---
>  diff.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/diff.c b/diff.c
> index efe42b341a..02491ee684 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -964,8 +964,9 @@ static struct moved_entry *prepare_entry(struct diff_options *o,
>  	struct moved_entry *ret = xmalloc(sizeof(*ret));
>  	struct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no];
>  	unsigned flags = o->color_moved_ws_handling & XDF_WHITESPACE_FLAGS;
> +	unsigned int hash = xdiff_hash_string(l->line, l->len, flags);
>  
> -	ret->ent.hash = xdiff_hash_string(l->line, l->len, flags);
> +	hashmap_entry_init(&ret->ent, hash);

I've typically seen these hashmap_entry_init() calls include the
hash function in-line instead of saving to a variable. But, this
looks fine and is obviously correct.

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *"
  2019-08-26  2:43 ` [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *" Eric Wong
@ 2019-08-27 13:35   ` Derrick Stolee
  2019-08-28 15:01     ` Johannes Schindelin
  0 siblings, 1 reply; 30+ messages in thread
From: Derrick Stolee @ 2019-08-27 13:35 UTC (permalink / raw)
  To: Eric Wong, Junio C Hamano; +Cc: git

On 8/25/2019 10:43 PM, Eric Wong wrote:
> C compilers do type checking to make life easier for us.  So
> rely on that and update all hashmap_entry_init callers to take
> "struct hashmap_entry *" to avoid future bugs while improving
> safety and readability.

Overall I like this change. I'll need to keep it in mind with my
sparse-checkout work that is adding more hashmap types.

One _might_ think that this change is relaxing the condition on
where the hashmap_entry appears within the super-struct, but
the hashmap internals will still use void* and perform a cast
to hashmap_entry for hash comparisons.
 
> Signed-off-by: Eric Wong <e@80x24.org>
> ---
>  attr.c                  |  4 ++--
>  blame.c                 |  2 +-
>  builtin/describe.c      |  2 +-
>  builtin/difftool.c      |  6 +++---
>  builtin/fast-export.c   |  2 +-
>  builtin/fetch.c         |  2 +-
>  config.c                |  4 ++--
>  diffcore-rename.c       |  2 +-
>  hashmap.c               |  4 ++--
>  hashmap.h               | 12 ++++++------
>  merge-recursive.c       | 13 +++++++------
>  name-hash.c             | 10 +++++-----
>  packfile.c              |  2 +-
>  patch-ids.c             |  2 +-
>  range-diff.c            |  4 ++--
>  ref-filter.c            |  3 ++-
>  refs.c                  |  2 +-
>  remote.c                |  2 +-
>  revision.c              |  4 ++--
>  sequencer.c             |  5 +++--
>  sub-process.c           |  4 ++--
>  submodule-config.c      | 10 +++++-----
>  t/helper/test-hashmap.c |  6 +++---
>  23 files changed, 55 insertions(+), 52 deletions(-)
> 
> diff --git a/attr.c b/attr.c
> index 93dc16b59c..a8be7a7b4f 100644
> --- a/attr.c
> +++ b/attr.c
> @@ -98,7 +98,7 @@ static void *attr_hashmap_get(struct attr_hashmap *map,
>  	if (!map->map.tablesize)
>  		attr_hashmap_init(map);
>  
> -	hashmap_entry_init(&k, memhash(key, keylen));
> +	hashmap_entry_init(&k.ent, memhash(key, keylen));
>  	k.key = key;
>  	k.keylen = keylen;
>  	e = hashmap_get(&map->map, &k, NULL);
> @@ -117,7 +117,7 @@ static void attr_hashmap_add(struct attr_hashmap *map,
>  		attr_hashmap_init(map);
>  
>  	e = xmalloc(sizeof(struct attr_hash_entry));
> -	hashmap_entry_init(e, memhash(key, keylen));
> +	hashmap_entry_init(&e->ent, memhash(key, keylen));
>  	e->key = key;
>  	e->keylen = keylen;
>  	e->value = value;
> diff --git a/blame.c b/blame.c
> index 36a2e7ef11..46059410cd 100644
> --- a/blame.c
> +++ b/blame.c
> @@ -417,7 +417,7 @@ static void get_fingerprint(struct fingerprint *result,
>  		/* Ignore whitespace pairs */
>  		if (hash == 0)
>  			continue;
> -		hashmap_entry_init(entry, hash);
> +		hashmap_entry_init(&entry->entry, hash);
>  
>  		found_entry = hashmap_get(&result->map, entry, NULL);
>  		if (found_entry) {
> diff --git a/builtin/describe.c b/builtin/describe.c
> index 200154297d..596ddf89a5 100644
> --- a/builtin/describe.c
> +++ b/builtin/describe.c
> @@ -123,7 +123,7 @@ static void add_to_known_names(const char *path,
>  		if (!e) {
>  			e = xmalloc(sizeof(struct commit_name));
>  			oidcpy(&e->peeled, peeled);
> -			hashmap_entry_init(e, oidhash(peeled));
> +			hashmap_entry_init(&e->entry, oidhash(peeled));
>  			hashmap_add(&names, e);
>  			e->path = NULL;
>  		}
> diff --git a/builtin/difftool.c b/builtin/difftool.c
> index 16eb8b70ea..98ffc04c61 100644
> --- a/builtin/difftool.c
> +++ b/builtin/difftool.c
> @@ -161,7 +161,7 @@ static void add_left_or_right(struct hashmap *map, const char *path,
>  	struct pair_entry *e, *existing;
>  
>  	FLEX_ALLOC_STR(e, path, path);
> -	hashmap_entry_init(e, strhash(path));
> +	hashmap_entry_init(&e->entry, strhash(path));
>  	existing = hashmap_get(map, e, NULL);
>  	if (existing) {
>  		free(e);
> @@ -234,7 +234,7 @@ static void changed_files(struct hashmap *result, const char *index_path,
>  	while (!strbuf_getline_nul(&buf, fp)) {
>  		struct path_entry *entry;
>  		FLEX_ALLOC_STR(entry, path, buf.buf);
> -		hashmap_entry_init(entry, strhash(buf.buf));
> +		hashmap_entry_init(&entry->entry, strhash(buf.buf));
>  		hashmap_add(result, entry);
>  	}
>  	fclose(fp);
> @@ -461,7 +461,7 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix,
>  
>  			/* Avoid duplicate working_tree entries */
>  			FLEX_ALLOC_STR(entry, path, dst_path);
> -			hashmap_entry_init(entry, strhash(dst_path));
> +			hashmap_entry_init(&entry->entry, strhash(dst_path));
>  			if (hashmap_get(&working_tree_dups, entry, NULL)) {
>  				free(entry);
>  				continue;
> diff --git a/builtin/fast-export.c b/builtin/fast-export.c
> index f541f55d33..287dbd24a3 100644
> --- a/builtin/fast-export.c
> +++ b/builtin/fast-export.c
> @@ -148,7 +148,7 @@ static const void *anonymize_mem(struct hashmap *map,
>  	if (!map->cmpfn)
>  		hashmap_init(map, anonymized_entry_cmp, NULL, 0);
>  
> -	hashmap_entry_init(&key, memhash(orig, *len));
> +	hashmap_entry_init(&key.hash, memhash(orig, *len));
>  	key.orig = orig;
>  	key.orig_len = *len;
>  	ret = hashmap_get(map, &key, NULL);
> diff --git a/builtin/fetch.c b/builtin/fetch.c
> index 717dd14e89..b7d70eee70 100644
> --- a/builtin/fetch.c
> +++ b/builtin/fetch.c
> @@ -276,7 +276,7 @@ static struct refname_hash_entry *refname_hash_add(struct hashmap *map,
>  	size_t len = strlen(refname);
>  
>  	FLEX_ALLOC_MEM(ent, refname, refname, len);
> -	hashmap_entry_init(ent, strhash(refname));
> +	hashmap_entry_init(&ent->ent, strhash(refname));
>  	oidcpy(&ent->oid, oid);
>  	hashmap_add(map, ent);
>  	return ent;
> diff --git a/config.c b/config.c
> index 3900e4947b..08d866e7de 100644
> --- a/config.c
> +++ b/config.c
> @@ -1861,7 +1861,7 @@ static struct config_set_element *configset_find_element(struct config_set *cs,
>  	if (git_config_parse_key(key, &normalized_key, NULL))
>  		return NULL;
>  
> -	hashmap_entry_init(&k, strhash(normalized_key));
> +	hashmap_entry_init(&k.ent, strhash(normalized_key));
>  	k.key = normalized_key;
>  	found_entry = hashmap_get(&cs->config_hash, &k, NULL);
>  	free(normalized_key);
> @@ -1882,7 +1882,7 @@ static int configset_add_value(struct config_set *cs, const char *key, const cha
>  	 */
>  	if (!e) {
>  		e = xmalloc(sizeof(*e));
> -		hashmap_entry_init(e, strhash(key));
> +		hashmap_entry_init(&e->ent, strhash(key));
>  		e->key = xstrdup(key);
>  		string_list_init(&e->value_list, 1);
>  		hashmap_add(&cs->config_hash, e);
> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 9624864858..44a3ab1e31 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -329,7 +329,7 @@ static void insert_file_table(struct repository *r,
>  	entry->index = index;
>  	entry->filespec = filespec;
>  
> -	hashmap_entry_init(entry, hash_filespec(r, filespec));
> +	hashmap_entry_init(&entry->entry, hash_filespec(r, filespec));
>  	hashmap_add(table, entry);
>  }
>  
> diff --git a/hashmap.c b/hashmap.c
> index d42f01ff5a..6818c65174 100644
> --- a/hashmap.c
> +++ b/hashmap.c
> @@ -293,13 +293,13 @@ const void *memintern(const void *data, size_t len)
>  		hashmap_init(&map, (hashmap_cmp_fn) pool_entry_cmp, NULL, 0);
>  
>  	/* lookup interned string in pool */
> -	hashmap_entry_init(&key, memhash(data, len));
> +	hashmap_entry_init(&key.ent, memhash(data, len));
>  	key.len = len;
>  	e = hashmap_get(&map, &key, data);
>  	if (!e) {
>  		/* not found: create it */
>  		FLEX_ALLOC_MEM(e, data, data, len);
> -		hashmap_entry_init(e, key.ent.hash);
> +		hashmap_entry_init(&e->ent, key.ent.hash);
>  		e->len = len;
>  		hashmap_add(&map, e);
>  	}
> diff --git a/hashmap.h b/hashmap.h
> index 8424911566..3d7939c291 100644
> --- a/hashmap.h
> +++ b/hashmap.h
> @@ -48,14 +48,14 @@
>   *         if (!strcmp("add", action)) {
>   *             struct long2string *e;
>   *             FLEX_ALLOC_STR(e, value, value);
> - *             hashmap_entry_init(e, memhash(&key, sizeof(long)));
> + *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
>   *             e->key = key;
>   *             hashmap_add(&map, e);
>   *         }
>   *
>   *         if (!strcmp("print_all_by_key", action)) {
>   *             struct long2string k, *e;
> - *             hashmap_entry_init(&k, memhash(&key, sizeof(long)));
> + *             hashmap_entry_init(&k->ent, memhash(&key, sizeof(long)));
>   *             k.key = key;
>   *
>   *             flags &= ~COMPARE_VALUE;
> @@ -70,7 +70,7 @@
>   *         if (!strcmp("has_exact_match", action)) {
>   *             struct long2string *e;
>   *             FLEX_ALLOC_STR(e, value, value);
> - *             hashmap_entry_init(e, memhash(&key, sizeof(long)));
> + *             hashmap_entry_init(&e->ent, memhash(&key, sizeof(long)));
>   *             e->key = key;
>   *
>   *             flags |= COMPARE_VALUE;
> @@ -80,7 +80,7 @@
>   *
>   *         if (!strcmp("has_exact_match_no_heap_alloc", action)) {
>   *             struct long2string k;
> - *             hashmap_entry_init(&k, memhash(&key, sizeof(long)));
> + *             hashmap_entry_init(&k->ent, memhash(&key, sizeof(long)));
>   *             k.key = key;
>   *
>   *             flags |= COMPARE_VALUE;
> @@ -244,9 +244,9 @@ void hashmap_free(struct hashmap *map, int free_entries);
>   * your structure was allocated with xmalloc(), you can just free(3) it,
>   * and if it is on stack, you can just let it go out of scope).
>   */
> -static inline void hashmap_entry_init(void *entry, unsigned int hash)
> +static inline void
> +hashmap_entry_init(struct hashmap_entry *e, unsigned int hash)
>  {
> -	struct hashmap_entry *e = entry;
>  	e->hash = hash;
>  	e->next = NULL;
>  }
> diff --git a/merge-recursive.c b/merge-recursive.c
> index 6b812d67e3..6bc4f14ff4 100644
> --- a/merge-recursive.c
> +++ b/merge-recursive.c
> @@ -61,7 +61,7 @@ static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap,
>  
>  	if (dir == NULL)
>  		return NULL;
> -	hashmap_entry_init(&key, strhash(dir));
> +	hashmap_entry_init(&key.ent, strhash(dir));
>  	key.dir = dir;
>  	return hashmap_get(hashmap, &key, NULL);
>  }
> @@ -85,7 +85,7 @@ static void dir_rename_init(struct hashmap *map)
>  static void dir_rename_entry_init(struct dir_rename_entry *entry,
>  				  char *directory)
>  {
> -	hashmap_entry_init(entry, strhash(directory));
> +	hashmap_entry_init(&entry->ent, strhash(directory));
>  	entry->dir = directory;
>  	entry->non_unique_new_dir = 0;
>  	strbuf_init(&entry->new_dir, 0);
> @@ -97,7 +97,7 @@ static struct collision_entry *collision_find_entry(struct hashmap *hashmap,
>  {
>  	struct collision_entry key;
>  
> -	hashmap_entry_init(&key, strhash(target_file));
> +	hashmap_entry_init(&key.ent, strhash(target_file));
>  	key.target_file = target_file;
>  	return hashmap_get(hashmap, &key, NULL);
>  }
> @@ -454,7 +454,7 @@ static int save_files_dirs(const struct object_id *oid,
>  	strbuf_addstr(base, path);
>  
>  	FLEX_ALLOC_MEM(entry, path, base->buf, base->len);
> -	hashmap_entry_init(entry, path_hash(entry->path));
> +	hashmap_entry_init(&entry->e, path_hash(entry->path));
>  	hashmap_add(&opt->current_file_dir_set, entry);
>  
>  	strbuf_setlen(base, baselen);
> @@ -731,7 +731,7 @@ static char *unique_path(struct merge_options *opt, const char *path, const char
>  	}
>  
>  	FLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);
> -	hashmap_entry_init(entry, path_hash(entry->path));
> +	hashmap_entry_init(&entry->e, path_hash(entry->path));
>  	hashmap_add(&opt->current_file_dir_set, entry);
>  	return strbuf_detach(&newpath, NULL);
>  }
> @@ -2358,7 +2358,8 @@ static void compute_collisions(struct hashmap *collisions,
>  		if (!collision_ent) {
>  			collision_ent = xcalloc(1,
>  						sizeof(struct collision_entry));
> -			hashmap_entry_init(collision_ent, strhash(new_path));
> +			hashmap_entry_init(&collision_ent->ent,
> +						strhash(new_path));
>  			hashmap_put(collisions, collision_ent);
>  			collision_ent->target_file = new_path;
>  		} else {
> diff --git a/name-hash.c b/name-hash.c
> index 695908609f..1ce1417f7e 100644
> --- a/name-hash.c
> +++ b/name-hash.c
> @@ -33,7 +33,7 @@ static struct dir_entry *find_dir_entry__hash(struct index_state *istate,
>  		const char *name, unsigned int namelen, unsigned int hash)
>  {
>  	struct dir_entry key;
> -	hashmap_entry_init(&key, hash);
> +	hashmap_entry_init(&key.ent, hash);
>  	key.namelen = namelen;
>  	return hashmap_get(&istate->dir_hash, &key, name);
>  }
> @@ -68,7 +68,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
>  	if (!dir) {
>  		/* not found, create it and add to hash table */
>  		FLEX_ALLOC_MEM(dir, name, ce->name, namelen);
> -		hashmap_entry_init(dir, memihash(ce->name, namelen));
> +		hashmap_entry_init(&dir->ent, memihash(ce->name, namelen));
>  		dir->namelen = namelen;
>  		hashmap_add(&istate->dir_hash, dir);
>  
> @@ -106,7 +106,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
>  	if (ce->ce_flags & CE_HASHED)
>  		return;
>  	ce->ce_flags |= CE_HASHED;
> -	hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));
> +	hashmap_entry_init(&ce->ent, memihash(ce->name, ce_namelen(ce)));
>  	hashmap_add(&istate->name_hash, ce);
>  
>  	if (ignore_case)
> @@ -280,7 +280,7 @@ static struct dir_entry *hash_dir_entry_with_parent_and_prefix(
>  	dir = find_dir_entry__hash(istate, prefix->buf, prefix->len, hash);
>  	if (!dir) {
>  		FLEX_ALLOC_MEM(dir, name, prefix->buf, prefix->len);
> -		hashmap_entry_init(dir, hash);
> +		hashmap_entry_init(&dir->ent, hash);
>  		dir->namelen = prefix->len;
>  		dir->parent = parent;
>  		hashmap_add(&istate->dir_hash, dir);
> @@ -472,7 +472,7 @@ static void *lazy_name_thread_proc(void *_data)
>  	for (k = 0; k < d->istate->cache_nr; k++) {
>  		struct cache_entry *ce_k = d->istate->cache[k];
>  		ce_k->ce_flags |= CE_HASHED;
> -		hashmap_entry_init(ce_k, d->lazy_entries[k].hash_name);
> +		hashmap_entry_init(&ce_k->ent, d->lazy_entries[k].hash_name);
>  		hashmap_add(&d->istate->name_hash, ce_k);
>  	}
>  
> diff --git a/packfile.c b/packfile.c
> index 37fe0b73a6..96535eb86b 100644
> --- a/packfile.c
> +++ b/packfile.c
> @@ -1487,7 +1487,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
>  
>  	if (!delta_base_cache.cmpfn)
>  		hashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);
> -	hashmap_entry_init(ent, pack_entry_hash(p, base_offset));
> +	hashmap_entry_init(&ent->ent, pack_entry_hash(p, base_offset));
>  	hashmap_add(&delta_base_cache, ent);
>  }
>  
> diff --git a/patch-ids.c b/patch-ids.c
> index e8c150d0c9..a2da711678 100644
> --- a/patch-ids.c
> +++ b/patch-ids.c
> @@ -83,7 +83,7 @@ static int init_patch_id_entry(struct patch_id *patch,
>  	if (commit_patch_id(commit, &ids->diffopts, &header_only_patch_id, 1, 0))
>  		return -1;
>  
> -	hashmap_entry_init(patch, oidhash(&header_only_patch_id));
> +	hashmap_entry_init(&patch->ent, oidhash(&header_only_patch_id));
>  	return 0;
>  }
>  
> diff --git a/range-diff.c b/range-diff.c
> index ba1e9a4265..32b29f9594 100644
> --- a/range-diff.c
> +++ b/range-diff.c
> @@ -217,7 +217,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)
>  		util->i = i;
>  		util->patch = a->items[i].string;
>  		util->diff = util->patch + util->diff_offset;
> -		hashmap_entry_init(util, strhash(util->diff));
> +		hashmap_entry_init(&util->e, strhash(util->diff));
>  		hashmap_add(&map, util);
>  	}
>  
> @@ -228,7 +228,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)
>  		util->i = i;
>  		util->patch = b->items[i].string;
>  		util->diff = util->patch + util->diff_offset;
> -		hashmap_entry_init(util, strhash(util->diff));
> +		hashmap_entry_init(&util->e, strhash(util->diff));
>  		other = hashmap_remove(&map, util, NULL);
>  		if (other) {
>  			if (other->matching >= 0)
> diff --git a/ref-filter.c b/ref-filter.c
> index f27cfc8c3e..206014c93d 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -1565,7 +1565,8 @@ static void populate_worktree_map(struct hashmap *map, struct worktree **worktre
>  			struct ref_to_worktree_entry *entry;
>  			entry = xmalloc(sizeof(*entry));
>  			entry->wt = worktrees[i];
> -			hashmap_entry_init(entry, strhash(worktrees[i]->head_ref));
> +			hashmap_entry_init(&entry->ent,
> +					strhash(worktrees[i]->head_ref));
>  
>  			hashmap_add(map, entry);
>  		}
> diff --git a/refs.c b/refs.c
> index cd297ee4bd..c43ec59c6e 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -1796,7 +1796,7 @@ static struct ref_store_hash_entry *alloc_ref_store_hash_entry(
>  	struct ref_store_hash_entry *entry;
>  
>  	FLEX_ALLOC_STR(entry, name, name);
> -	hashmap_entry_init(entry, strhash(name));
> +	hashmap_entry_init(&entry->ent, strhash(name));
>  	entry->refs = refs;
>  	return entry;
>  }
> diff --git a/remote.c b/remote.c
> index e50f7602ed..bd81cb71bc 100644
> --- a/remote.c
> +++ b/remote.c
> @@ -158,7 +158,7 @@ static struct remote *make_remote(const char *name, int len)
>  	ALLOC_GROW(remotes, remotes_nr + 1, remotes_alloc);
>  	remotes[remotes_nr++] = ret;
>  
> -	hashmap_entry_init(ret, lookup_entry.hash);
> +	hashmap_entry_init(&ret->ent, lookup_entry.hash);
>  	replaced = hashmap_put(&remotes_hash, ret);
>  	assert(replaced == NULL);  /* no previous entry overwritten */
>  	return ret;
> diff --git a/revision.c b/revision.c
> index 07412297f0..3461c78883 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -141,7 +141,7 @@ static void paths_and_oids_insert(struct hashmap *map,
>  	struct path_and_oids_entry key;
>  	struct path_and_oids_entry *entry;
>  
> -	hashmap_entry_init(&key, hash);
> +	hashmap_entry_init(&key.ent, hash);
>  
>  	/* use a shallow copy for the lookup */
>  	key.path = (char *)path;
> @@ -149,7 +149,7 @@ static void paths_and_oids_insert(struct hashmap *map,
>  
>  	if (!(entry = (struct path_and_oids_entry *)hashmap_get(map, &key, NULL))) {
>  		entry = xcalloc(1, sizeof(struct path_and_oids_entry));
> -		hashmap_entry_init(entry, hash);
> +		hashmap_entry_init(&entry->ent, hash);
>  		entry->path = xstrdup(key.path);
>  		oidset_init(&entry->trees, 16);
>  		hashmap_put(map, entry);
> diff --git a/sequencer.c b/sequencer.c
> index 34ebf8ed94..1140cdf526 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -4538,7 +4538,7 @@ static const char *label_oid(struct object_id *oid, const char *label,
>  	}
>  
>  	FLEX_ALLOC_STR(labels_entry, label, label);
> -	hashmap_entry_init(labels_entry, strihash(label));
> +	hashmap_entry_init(&labels_entry->entry, strihash(label));
>  	hashmap_add(&state->labels, labels_entry);
>  
>  	FLEX_ALLOC_STR(string_entry, string, label);
> @@ -5252,7 +5252,8 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
>  						strhash(subject), subject)) {
>  			FLEX_ALLOC_MEM(entry, subject, subject, subject_len);
>  			entry->i = i;
> -			hashmap_entry_init(entry, strhash(entry->subject));
> +			hashmap_entry_init(&entry->entry,
> +					strhash(entry->subject));
>  			hashmap_put(&subject2item, entry);
>  		}
>  	}
> diff --git a/sub-process.c b/sub-process.c
> index 3f4af93555..9847dad6fc 100644
> --- a/sub-process.c
> +++ b/sub-process.c
> @@ -20,7 +20,7 @@ struct subprocess_entry *subprocess_find_entry(struct hashmap *hashmap, const ch
>  {
>  	struct subprocess_entry key;
>  
> -	hashmap_entry_init(&key, strhash(cmd));
> +	hashmap_entry_init(&key.ent, strhash(cmd));
>  	key.cmd = cmd;
>  	return hashmap_get(hashmap, &key, NULL);
>  }
> @@ -96,7 +96,7 @@ int subprocess_start(struct hashmap *hashmap, struct subprocess_entry *entry, co
>  		return err;
>  	}
>  
> -	hashmap_entry_init(entry, strhash(cmd));
> +	hashmap_entry_init(&entry->ent, strhash(cmd));
>  
>  	err = startfn(entry);
>  	if (err) {
> diff --git a/submodule-config.c b/submodule-config.c
> index 4264ee216f..4aa02e280e 100644
> --- a/submodule-config.c
> +++ b/submodule-config.c
> @@ -123,7 +123,7 @@ static void cache_put_path(struct submodule_cache *cache,
>  	unsigned int hash = hash_oid_string(&submodule->gitmodules_oid,
>  					    submodule->path);
>  	struct submodule_entry *e = xmalloc(sizeof(*e));
> -	hashmap_entry_init(e, hash);
> +	hashmap_entry_init(&e->ent, hash);
>  	e->config = submodule;
>  	hashmap_put(&cache->for_path, e);
>  }
> @@ -135,7 +135,7 @@ static void cache_remove_path(struct submodule_cache *cache,
>  					    submodule->path);
>  	struct submodule_entry e;
>  	struct submodule_entry *removed;
> -	hashmap_entry_init(&e, hash);
> +	hashmap_entry_init(&e.ent, hash);
>  	e.config = submodule;
>  	removed = hashmap_remove(&cache->for_path, &e, NULL);
>  	free(removed);
> @@ -147,7 +147,7 @@ static void cache_add(struct submodule_cache *cache,
>  	unsigned int hash = hash_oid_string(&submodule->gitmodules_oid,
>  					    submodule->name);
>  	struct submodule_entry *e = xmalloc(sizeof(*e));
> -	hashmap_entry_init(e, hash);
> +	hashmap_entry_init(&e->ent, hash);
>  	e->config = submodule;
>  	hashmap_add(&cache->for_name, e);
>  }
> @@ -163,7 +163,7 @@ static const struct submodule *cache_lookup_path(struct submodule_cache *cache,
>  	oidcpy(&key_config.gitmodules_oid, gitmodules_oid);
>  	key_config.path = path;
>  
> -	hashmap_entry_init(&key, hash);
> +	hashmap_entry_init(&key.ent, hash);
>  	key.config = &key_config;
>  
>  	entry = hashmap_get(&cache->for_path, &key, NULL);
> @@ -183,7 +183,7 @@ static struct submodule *cache_lookup_name(struct submodule_cache *cache,
>  	oidcpy(&key_config.gitmodules_oid, gitmodules_oid);
>  	key_config.name = name;
>  
> -	hashmap_entry_init(&key, hash);
> +	hashmap_entry_init(&key.ent, hash);
>  	key.config = &key_config;
>  
>  	entry = hashmap_get(&cache->for_name, &key, NULL);
> diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
> index aaf17b0ddf..0c9fd7c996 100644
> --- a/t/helper/test-hashmap.c
> +++ b/t/helper/test-hashmap.c
> @@ -37,7 +37,7 @@ static struct test_entry *alloc_test_entry(unsigned int hash,
>  	size_t klen = strlen(key);
>  	size_t vlen = strlen(value);
>  	struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
> -	hashmap_entry_init(entry, hash);
> +	hashmap_entry_init(&entry->ent, hash);
>  	memcpy(entry->key, key, klen + 1);
>  	memcpy(entry->key + klen + 1, value, vlen + 1);
>  	return entry;
> @@ -103,7 +103,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
>  
>  			/* add entries */
>  			for (i = 0; i < TEST_SIZE; i++) {
> -				hashmap_entry_init(entries[i], hashes[i]);
> +				hashmap_entry_init(&entries[i]->ent, hashes[i]);
>  				hashmap_add(&map, entries[i]);
>  			}
>  
> @@ -116,7 +116,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
>  		/* fill the map (sparsely if specified) */
>  		j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;
>  		for (i = 0; i < j; i++) {
> -			hashmap_entry_init(entries[i], hashes[i]);
> +			hashmap_entry_init(&entries[i]->ent, hashes[i]);
>  			hashmap_add(&map, entries[i]);
>  		}
>  
> 


^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 10/11] introduce container_of macro
  2019-08-26  2:43 ` [PATCH 10/11] introduce container_of macro Eric Wong
@ 2019-08-27 14:49   ` Derrick Stolee
  2019-08-28  9:11     ` Phillip Wood
  2019-08-30 19:43     ` Eric Wong
  0 siblings, 2 replies; 30+ messages in thread
From: Derrick Stolee @ 2019-08-27 14:49 UTC (permalink / raw)
  To: Eric Wong, Junio C Hamano; +Cc: git

On 8/25/2019 10:43 PM, Eric Wong wrote:
> This macro is popular within the Linux kernel for supporting
> intrusive data structures such as linked lists, red-black trees,
> and chained hash tables while allowing the compiler to do
> type checking.
> 
> I intend to use this to remove the limitation of "hashmap_entry"
> being location-dependent and to allow more compile-time type
> checking.
> 
> This macro already exists in our source as "list_entry" in
> list.h and making "list_entry" an alias to "container_of"
> as the Linux kernel has done is a possibility.
[snip]
> +/*
> + * container_of - Get the address of an object containing a field.
> + *
> + * @ptr: pointer to the field.
> + * @type: type of the object.
> + * @member: name of the field within the object.
> + */
> +#define container_of(ptr, type, member) \
> +	((type *) ((char *)(ptr) - offsetof(type, member)))
> +
>  #endif

I think it would be good to include at least one use of this
macro in this patch. As it stands, I need to look at the next
patch to make sense of what this is doing.

It took me a little while to parse what is happening here.
'ptr' is a pointer to the generic struct (in our case,
'struct hashmap_entry *'), while 'type' is the parent type,
and 'member' is the name of the member in 'type' that is
of type typeof(*ptr).

Perhaps this is easier to grok for others than it was for me.

-Stolee

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *"
  2019-08-26  2:43 ` [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *" Eric Wong
@ 2019-08-27 14:53   ` Derrick Stolee
  2019-08-30 19:36     ` Eric Wong
  0 siblings, 1 reply; 30+ messages in thread
From: Derrick Stolee @ 2019-08-27 14:53 UTC (permalink / raw)
  To: Eric Wong, Junio C Hamano; +Cc: git

On 8/25/2019 10:43 PM, Eric Wong wrote:
> This is a step towards removing the requirement for
> hashmap_entry being the first field of a struct.
> 
> Signed-off-by: Eric Wong <e@80x24.org>
> ---
>  diff.c                  | 19 ++++++++++++-------
>  diffcore-rename.c       | 11 +++++++----
>  hashmap.c               |  2 +-
>  hashmap.h               | 12 ++++++++----
>  name-hash.c             |  8 +++++---
>  t/helper/test-hashmap.c | 10 ++++++----
>  6 files changed, 39 insertions(+), 23 deletions(-)
> 
> diff --git a/diff.c b/diff.c
> index 72d3c6aa19..663b5d01f8 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -1035,8 +1035,10 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o,
>  {
>  	int i;
>  	char *got_match = xcalloc(1, pmb_nr);
> +	struct hashmap_entry *ent = &match->ent;
>  
> -	for (; match; match = hashmap_get_next(hm, &match->ent)) {
> +	for (; ent; ent = hashmap_get_next(hm, ent)) {
> +		match = container_of(ent, struct moved_entry, ent);

Lines like this are very difficult to parse. In this
container_of() macro, 'ent' is taking both the 'ptr' and
'member' values.

I would prefer that you make your local member be named
something different, for instance:

	struct hashmap_entry *match_ent = &match->ent;

and

	match = container_of(match_ent, struct moved_entry, ent);

>  		for (i = 0; i < pmb_nr; i++) {
>  			struct moved_entry *prev = pmb[i].match;
>  			struct moved_entry *cur = (prev && prev->next_line) ?
> @@ -1135,8 +1137,9 @@ static void mark_color_as_moved(struct diff_options *o,
>  
>  	for (n = 0; n < o->emitted_symbols->nr; n++) {
>  		struct hashmap *hm = NULL;
> +		struct hashmap_entry *ent = NULL;
>  		struct moved_entry *key;
> -		struct moved_entry *match = NULL;
> +		struct moved_entry *match;
>  		struct emitted_diff_symbol *l = &o->emitted_symbols->buf[n];
>  		enum diff_symbol last_symbol = 0;
>  
> @@ -1144,20 +1147,20 @@ static void mark_color_as_moved(struct diff_options *o,
>  		case DIFF_SYMBOL_PLUS:
>  			hm = del_lines;
>  			key = prepare_entry(o, n);
> -			match = hashmap_get(hm, &key->ent, NULL);
> +			ent = hashmap_get(hm, &key->ent, NULL);
>  			free(key);
>  			break;
>  		case DIFF_SYMBOL_MINUS:
>  			hm = add_lines;
>  			key = prepare_entry(o, n);
> -			match = hashmap_get(hm, &key->ent, NULL);
> +			ent = hashmap_get(hm, &key->ent, NULL);
>  			free(key);
>  			break;
>  		default:
>  			flipped_block = 0;
>  		}
>  
> -		if (!match) {
> +		if (!ent) {
>  			int i;
>  
>  			adjust_last_block(o, n, block_length);
> @@ -1169,6 +1172,7 @@ static void mark_color_as_moved(struct diff_options *o,
>  			last_symbol = l->s;
>  			continue;
>  		}
> +		match = container_of(ent, struct moved_entry, ent);
>  
>  		if (o->color_moved == COLOR_MOVED_PLAIN) {
>  			last_symbol = l->s;
> @@ -1189,8 +1193,9 @@ static void mark_color_as_moved(struct diff_options *o,
>  			 * The current line is the start of a new block.
>  			 * Setup the set of potential blocks.
>  			 */
> -			for (; match; match = hashmap_get_next(hm,
> -								&match->ent)) {
> +			for (; ent; ent = hashmap_get_next(hm, ent)) {
> +				match = container_of(ent, struct moved_entry,
> +							ent);

Same complaint here.

>  				ALLOC_GROW(pmb, pmb_nr + 1, pmb_alloc);
>  				if (o->color_moved_ws_handling &
>  				    COLOR_MOVED_WS_ALLOW_INDENTATION_CHANGE) {
> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 4670a40179..71aa240a68 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -274,7 +274,7 @@ static int find_identical_files(struct hashmap *srcs,
>  				struct diff_options *options)
>  {
>  	int renames = 0;
> -
> +	struct hashmap_entry *ent;
>  	struct diff_filespec *target = rename_dst[dst_index].two;
>  	struct file_similarity *p, *best = NULL;
>  	int i = 100, best_score = -1;
> @@ -282,12 +282,15 @@ static int find_identical_files(struct hashmap *srcs,
>  	/*
>  	 * Find the best source match for specified destination.
>  	 */
> -	p = hashmap_get_from_hash(srcs,
> +	ent = hashmap_get_from_hash(srcs,
>  				  hash_filespec(options->repo, target),
>  				  NULL);
> -	for (; p; p = hashmap_get_next(srcs, &p->entry)) {
> +	for (; ent; ent = hashmap_get_next(srcs, ent)) {
>  		int score;
> -		struct diff_filespec *source = p->filespec;
> +		struct diff_filespec *source;
> +
> +		p = container_of(ent, struct file_similarity, entry);

This is slightly better, but still a bit confusing.

> +		source = p->filespec;
>  
>  		/* False hash collision? */
>  		if (!oideq(&source->oid, &target->oid))
> diff --git a/hashmap.c b/hashmap.c
> index 2dd9912e13..d6434d9ca4 100644
> --- a/hashmap.c
> +++ b/hashmap.c
> @@ -192,7 +192,7 @@ void *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key,
>  	return *find_entry_ptr(map, key, keydata);
>  }
>  
> -void *hashmap_get_next(const struct hashmap *map,
> +struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
>  			const struct hashmap_entry *entry)
>  {
>  	struct hashmap_entry *e = entry->next;
> diff --git a/hashmap.h b/hashmap.h
> index b62ee2e7b9..25643dcdc4 100644
> --- a/hashmap.h
> +++ b/hashmap.h
> @@ -55,15 +55,19 @@
>   *
>   *         if (!strcmp("print_all_by_key", action)) {
>   *             struct long2string k, *e;
> + *             struct hashmap_entry *ent;
>   *             hashmap_entry_init(&k->ent, memhash(&key, sizeof(long)));
>   *             k.key = key;
>   *
>   *             flags &= ~COMPARE_VALUE;
> - *             e = hashmap_get(&map, &k, NULL);
> - *             if (e) {
> + *             ent = hashmap_get(&map, &k, NULL);
> + *             if (ent) {
> + *                 e = container_of(ent, struct long2string, ent);
>   *                 printf("first: %ld %s\n", e->key, e->value);
> - *                 while ((e = hashmap_get_next(&map, e)))
> + *                 while ((ent = hashmap_get_next(&map, ent))) {
> + *                     e = container_of(ent, struct long2string, ent);
>   *                     printf("found more: %ld %s\n", e->key, e->value);
> + *                 }
>   *             }
>   *         }
>   *
> @@ -320,7 +324,7 @@ static inline void *hashmap_get_from_hash(const struct hashmap *map,
>   * `entry` is the hashmap_entry to start the search from, obtained via a previous
>   * call to `hashmap_get` or `hashmap_get_next`.
>   */
> -void *hashmap_get_next(const struct hashmap *map,
> +struct hashmap_entry *hashmap_get_next(const struct hashmap *map,
>  			const struct hashmap_entry *entry);
>  
>  /*
> diff --git a/name-hash.c b/name-hash.c
> index f64c52bfa2..6f2779934f 100644
> --- a/name-hash.c
> +++ b/name-hash.c
> @@ -703,15 +703,17 @@ void adjust_dirname_case(struct index_state *istate, char *name)
>  struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int icase)
>  {
>  	struct cache_entry *ce;
> +	struct hashmap_entry *ent;
>  
>  	lazy_init_name_hash(istate);
>  
> -	ce = hashmap_get_from_hash(&istate->name_hash,
> +	ent = hashmap_get_from_hash(&istate->name_hash,
>  				   memihash(name, namelen), NULL);
> -	while (ce) {
> +	while (ent) {
> +		ce = container_of(ent, struct cache_entry, ent);
>  		if (same_name(ce, name, namelen, icase))
>  			return ce;
> -		ce = hashmap_get_next(&istate->name_hash, &ce->ent);
> +		ent = hashmap_get_next(&istate->name_hash, ent);
>  	}
>  	return NULL;
>  }
> diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
> index de2bd083b9..d85b8dc58e 100644
> --- a/t/helper/test-hashmap.c
> +++ b/t/helper/test-hashmap.c
> @@ -194,16 +194,18 @@ int cmd__hashmap(int argc, const char **argv)
>  			free(entry);
>  
>  		} else if (!strcmp("get", cmd) && p1) {
> +			struct hashmap_entry *e;
>  
>  			/* lookup entry in hashmap */
> -			entry = hashmap_get_from_hash(&map, hash, p1);
> +			e = hashmap_get_from_hash(&map, hash, p1);
>  
>  			/* print result */
> -			if (!entry)
> +			if (!e)
>  				puts("NULL");
> -			while (entry) {
> +			while (e) {
> +				entry = container_of(e, struct test_entry, ent);
>  				puts(get_value(entry));
> -				entry = hashmap_get_next(&map, &entry->ent);
> +				e = hashmap_get_next(&map, e);
>  			}
>  
>  		} else if (!strcmp("remove", cmd) && p1) {

I didn't comment on them all, but essentially every use of
container_of() here is pretty confusing with the names. Perhaps
some pattern of "type_member" could be helpful, so you can use

	type_p = container_of(type_member, struct type, member);

to be really clear about each name.

Thanks,
-Stolee


^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-27  9:49     ` Eric Wong
@ 2019-08-27 22:16       ` Junio C Hamano
  2019-08-28 15:04         ` Johannes Schindelin
  2019-08-28  9:03       ` Phillip Wood
  1 sibling, 1 reply; 30+ messages in thread
From: Junio C Hamano @ 2019-08-27 22:16 UTC (permalink / raw)
  To: Eric Wong; +Cc: Johannes Schindelin, git

Eric Wong <e@80x24.org> writes:

> I renamed it to intentionally break my build.

This cuts both ways.  If you work without any throw-away merges, it
is GOOD to make sure any new use other people added will be spotted
by the compiler by breaking the build.  It will force you to resolve
all such breakages until you can move on to other topics, and it
will also force you to commit to your topic that deliberately breaks
the build by renaming.

If you want to avoid committing to the current iteration of topic,
however, then that would mean you'd need a reliable way to rebuild
evil merges (aka resolution of semantic conflicts) so that you can
keep parts of more recent history more flexible (similar to how 'pu'
is managed).

My plan is to have ew/hashmap topic for a few days while ejecting
the js/add-i topic which semantically conflicts with the changed way
hashmaps ought to be used temporarily, and when I have enough time
and concentration, try to see if I can come up with a good semantic
conflict resolution that I can keep reusing (aka refs/merge-fix/).
If it happens, we'll see both topics, and if it doesn't, I'll then
drop ew/hashmap and queue js/add-i and rinse and repeat from there
;-)

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-27  9:49     ` Eric Wong
  2019-08-27 22:16       ` Junio C Hamano
@ 2019-08-28  9:03       ` Phillip Wood
  2019-08-30 19:52         ` Eric Wong
  1 sibling, 1 reply; 30+ messages in thread
From: Phillip Wood @ 2019-08-28  9:03 UTC (permalink / raw)
  To: Eric Wong, Johannes Schindelin; +Cc: Junio C Hamano, git

Hi Eric

On 27/08/2019 10:49, Eric Wong wrote:
> Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
>> Hi Eric,
>>
>> On Mon, 26 Aug 2019, Eric Wong wrote:
>>
>>> By renaming the "hash" field to "_hash", it's easy to spot
>>> improper initialization of hashmap_entry structs which
>>> can leave "hashmap_entry.next" uninitialized.
>>
>> Would you mind elaborating a bit? This explanation does not enlighten
>> me, sadly, all I see is that it makes it (slightly) harder for me to
>> maintain Git for Windows' patches on top of `pu`, as the FSCache patches
>> access that field directly (so even if they rebase cleanly, the build
>> breaks).
> 
> I renamed it to intentionally break my build.
> 
> That way I could easily spot if there were any other improper
> initializations of the .hash field.  It's fine to revert,
> actually, it could be more of a "showing my work" patch.

I'm still a bit confused as the changed initializations already used 
hashmap_entry_init() and so presumably were already initializing 
hashmap_entry.next correctly. Is there a way to get 'make coccicheck' 
detect incorrect initializations, this renaming wont prevent bad code 
being added in the future.

Best Wishes

Phillip

> (AFAIK, it's a pretty common practice, but maybe not here :x)
> 
> I've also pondered adding a
> "hashmap_entry_hash(const struct hashmap_entry *)"
> accessor method for reading the field value (but not setting
> it), but it's a bit verbose...
> 
> I'm also wondering where/if hashmap offers a real benefit over
> khash nowadays; the latter ought to have better locality.
> Would like benchmark at some point in the future;
> but safety fixes first :)
> 

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 10/11] introduce container_of macro
  2019-08-27 14:49   ` Derrick Stolee
@ 2019-08-28  9:11     ` Phillip Wood
  2019-08-30 19:43     ` Eric Wong
  1 sibling, 0 replies; 30+ messages in thread
From: Phillip Wood @ 2019-08-28  9:11 UTC (permalink / raw)
  To: Derrick Stolee, Eric Wong, Junio C Hamano; +Cc: git

On 27/08/2019 15:49, Derrick Stolee wrote:
> On 8/25/2019 10:43 PM, Eric Wong wrote:
>> This macro is popular within the Linux kernel for supporting
>> intrusive data structures such as linked lists, red-black trees,
>> and chained hash tables while allowing the compiler to do
>> type checking.
>>
>> I intend to use this to remove the limitation of "hashmap_entry"
>> being location-dependent and to allow more compile-time type
>> checking.
>>
>> This macro already exists in our source as "list_entry" in
>> list.h and making "list_entry" an alias to "container_of"
>> as the Linux kernel has done is a possibility.
> [snip]
>> +/*
>> + * container_of - Get the address of an object containing a field.
>> + *
>> + * @ptr: pointer to the field.
>> + * @type: type of the object.
>> + * @member: name of the field within the object.
>> + */
>> +#define container_of(ptr, type, member) \
>> +	((type *) ((char *)(ptr) - offsetof(type, member)))
>> +
>>   #endif
> 
> I think it would be good to include at least one use of this
> macro in this patch. As it stands, I need to look at the next
> patch to make sense of what this is doing.
> 
> It took me a little while to parse what is happening here.
> 'ptr' is a pointer to the generic struct (in our case,
> 'struct hashmap_entry *'), while 'type' is the parent type,
> and 'member' is the name of the member in 'type' that is
> of type typeof(*ptr).

It took me a couple of minutes to figure it out as well. The rest of 
this patch series adds some very welcome type safety changes, at first 
sight this patch threatens to undermine that as there is no check (and 
no compiler independent way to check) that type == typeof(*ptr). It 
would also be helpful if the commit message could explain how this can 
be used to improve type safety.

Best Wishes

Phillip

> Perhaps this is easier to grok for others than it was for me.
> 
> -Stolee
> 

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *"
  2019-08-27 13:35   ` Derrick Stolee
@ 2019-08-28 15:01     ` Johannes Schindelin
  2019-08-30 19:48       ` Eric Wong
  0 siblings, 1 reply; 30+ messages in thread
From: Johannes Schindelin @ 2019-08-28 15:01 UTC (permalink / raw)
  To: Derrick Stolee; +Cc: Eric Wong, Junio C Hamano, git

Hi Stolee,

On Tue, 27 Aug 2019, Derrick Stolee wrote:

> On 8/25/2019 10:43 PM, Eric Wong wrote:
> > C compilers do type checking to make life easier for us.  So
> > rely on that and update all hashmap_entry_init callers to take
> > "struct hashmap_entry *" to avoid future bugs while improving
> > safety and readability.
>
> Overall I like this change. I'll need to keep it in mind with my
> sparse-checkout work that is adding more hashmap types.
>
> One _might_ think that this change is relaxing the condition on
> where the hashmap_entry appears within the super-struct, but
> the hashmap internals will still use void* and perform a cast
> to hashmap_entry for hash comparisons.

I thought precisely the same.

Maybe we can get a Coccinelle rule that verifies that `struct
hashmap_entryh` fields are always the first ones?

Ciao,
Dscho

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-27 22:16       ` Junio C Hamano
@ 2019-08-28 15:04         ` Johannes Schindelin
  0 siblings, 0 replies; 30+ messages in thread
From: Johannes Schindelin @ 2019-08-28 15:04 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: Eric Wong, git

Hi Junio,

On Tue, 27 Aug 2019, Junio C Hamano wrote:

> My plan is to have ew/hashmap topic for a few days while ejecting
> the js/add-i topic which semantically conflicts with the changed way
> hashmaps ought to be used temporarily, and when I have enough time
> and concentration, try to see if I can come up with a good semantic
> conflict resolution that I can keep reusing (aka refs/merge-fix/).
> If it happens, we'll see both topics, and if it doesn't, I'll then
> drop ew/hashmap and queue js/add-i and rinse and repeat from there
> ;-)

FWIW I crafted my latest iteration such that you would only need to do
the `hash` => `_hash` rename in one line to merge `js/builtin-add-i`.

Ciao,
Dscho

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *"
  2019-08-27 14:53   ` Derrick Stolee
@ 2019-08-30 19:36     ` Eric Wong
  0 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-30 19:36 UTC (permalink / raw)
  To: Derrick Stolee; +Cc: Junio C Hamano, git

Derrick Stolee <stolee@gmail.com> wrote:
> On 8/25/2019 10:43 PM, Eric Wong wrote:
> > --- a/diff.c
> > +++ b/diff.c
> > @@ -1035,8 +1035,10 @@ static void pmb_advance_or_null_multi_match(struct diff_options *o,
> >  {
> >  	int i;
> >  	char *got_match = xcalloc(1, pmb_nr);
> > +	struct hashmap_entry *ent = &match->ent;
> >  
> > -	for (; match; match = hashmap_get_next(hm, &match->ent)) {
> > +	for (; ent; ent = hashmap_get_next(hm, ent)) {
> > +		match = container_of(ent, struct moved_entry, ent);
> 
> Lines like this are very difficult to parse. In this
> container_of() macro, 'ent' is taking both the 'ptr' and
> 'member' values.

Agreed, naming is hard :<

In the Linux kernel list.h implementation, there's actually
list_for_each_entry, list_next_entry and a bunch of other
macros which allow the caller to avoid using container_of.
We only have list_first_entry, so far.

We can draw inspiration from those macros by creating
hashmap_get_next_entry and hashmap_for_each_entry macros
which allow callers specify the type once; and there'd
be no need for callers to specify the hashmap_entry
pointer name at all :)

Unlike the kernel, it looks like we can't rely on __typeof__ in
git, but I think we can let the caller specify the type once...



^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 10/11] introduce container_of macro
  2019-08-27 14:49   ` Derrick Stolee
  2019-08-28  9:11     ` Phillip Wood
@ 2019-08-30 19:43     ` Eric Wong
  1 sibling, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-30 19:43 UTC (permalink / raw)
  To: Derrick Stolee; +Cc: Junio C Hamano, git

Derrick Stolee <stolee@gmail.com> wrote:
> On 8/25/2019 10:43 PM, Eric Wong wrote:
> > + * container_of - Get the address of an object containing a field.
> > + *
> > + * @ptr: pointer to the field.
> > + * @type: type of the object.
> > + * @member: name of the field within the object.
> > + */
> > +#define container_of(ptr, type, member) \
> > +	((type *) ((char *)(ptr) - offsetof(type, member)))
> > +
> >  #endif
> 
> I think it would be good to include at least one use of this
> macro in this patch. As it stands, I need to look at the next
> patch to make sense of what this is doing.

Yeah, I considered making list_entry an alias of this.
But I wasn't sure about including git-compat-util.h in
list.h...

> It took me a little while to parse what is happening here.
> 'ptr' is a pointer to the generic struct (in our case,
> 'struct hashmap_entry *'), while 'type' is the parent type,
> and 'member' is the name of the member in 'type' that is
> of type typeof(*ptr).
> 
> Perhaps this is easier to grok for others than it was for me.

*shrug*  I only dabble in C, but I've been using it for a good
while.  I'm probably drawn to it because I'm not a great C
programmer like having it to prevent mistakes.  I also find
open-coded linked lists (even singly-linked ones!)
hard-to-follow, so I always reach for something like urcu/list.h
or ccan/list.h.

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *"
  2019-08-28 15:01     ` Johannes Schindelin
@ 2019-08-30 19:48       ` Eric Wong
  2019-09-02 13:46         ` Johannes Schindelin
  0 siblings, 1 reply; 30+ messages in thread
From: Eric Wong @ 2019-08-30 19:48 UTC (permalink / raw)
  To: Johannes Schindelin; +Cc: Derrick Stolee, Junio C Hamano, git

Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> Hi Stolee,
> 
> On Tue, 27 Aug 2019, Derrick Stolee wrote:
> 
> > On 8/25/2019 10:43 PM, Eric Wong wrote:
> > > C compilers do type checking to make life easier for us.  So
> > > rely on that and update all hashmap_entry_init callers to take
> > > "struct hashmap_entry *" to avoid future bugs while improving
> > > safety and readability.
> >
> > Overall I like this change. I'll need to keep it in mind with my
> > sparse-checkout work that is adding more hashmap types.
> >
> > One _might_ think that this change is relaxing the condition on
> > where the hashmap_entry appears within the super-struct, but
> > the hashmap internals will still use void* and perform a cast
> > to hashmap_entry for hash comparisons.
> 
> I thought precisely the same.

Yes, that's the goal I'm working towards as mentioned in patches
10 and 11 :)

> Maybe we can get a Coccinelle rule that verifies that `struct
> hashmap_entryh` fields are always the first ones?

At this point, why?  Given the goal is to remove that requirement
entirely.

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 04/11] hashmap_entry: detect improper initialization
  2019-08-28  9:03       ` Phillip Wood
@ 2019-08-30 19:52         ` Eric Wong
  0 siblings, 0 replies; 30+ messages in thread
From: Eric Wong @ 2019-08-30 19:52 UTC (permalink / raw)
  To: phillip.wood; +Cc: Johannes Schindelin, Junio C Hamano, git

Phillip Wood <phillip.wood123@gmail.com> wrote:
> Hi Eric
> 
> On 27/08/2019 10:49, Eric Wong wrote:
> > Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > > Hi Eric,
> > > 
> > > On Mon, 26 Aug 2019, Eric Wong wrote:
> > > 
> > > > By renaming the "hash" field to "_hash", it's easy to spot
> > > > improper initialization of hashmap_entry structs which
> > > > can leave "hashmap_entry.next" uninitialized.
> > > 
> > > Would you mind elaborating a bit? This explanation does not enlighten
> > > me, sadly, all I see is that it makes it (slightly) harder for me to
> > > maintain Git for Windows' patches on top of `pu`, as the FSCache patches
> > > access that field directly (so even if they rebase cleanly, the build
> > > breaks).
> > 
> > I renamed it to intentionally break my build.
> > 
> > That way I could easily spot if there were any other improper
> > initializations of the .hash field.  It's fine to revert,
> > actually, it could be more of a "showing my work" patch.
> 
> I'm still a bit confused as the changed initializations already used
> hashmap_entry_init() and so presumably were already initializing
> hashmap_entry.next correctly. Is there a way to get 'make coccicheck' detect
> incorrect initializations, this renaming wont prevent bad code being added
> in the future.

Yeah I forgot we had coccicheck :x

I think this patch to rename the field can be dropped entirely.
I changed some usages of hashmap_entry_init to avoid reading the
.hash field entirely, since the result of memhash() could be
stored locally for multiple uses of hashmap_entry_init.

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *"
  2019-08-30 19:48       ` Eric Wong
@ 2019-09-02 13:46         ` Johannes Schindelin
  0 siblings, 0 replies; 30+ messages in thread
From: Johannes Schindelin @ 2019-09-02 13:46 UTC (permalink / raw)
  To: Eric Wong; +Cc: Derrick Stolee, Junio C Hamano, git

Hi Eric,

On Fri, 30 Aug 2019, Eric Wong wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> >
> > On Tue, 27 Aug 2019, Derrick Stolee wrote:
> >
> > > On 8/25/2019 10:43 PM, Eric Wong wrote:
> > > > C compilers do type checking to make life easier for us.  So
> > > > rely on that and update all hashmap_entry_init callers to take
> > > > "struct hashmap_entry *" to avoid future bugs while improving
> > > > safety and readability.
> > >
> > > Overall I like this change. I'll need to keep it in mind with my
> > > sparse-checkout work that is adding more hashmap types.
> > >
> > > One _might_ think that this change is relaxing the condition on
> > > where the hashmap_entry appears within the super-struct, but
> > > the hashmap internals will still use void* and perform a cast
> > > to hashmap_entry for hash comparisons.
> >
> > I thought precisely the same.
>
> Yes, that's the goal I'm working towards as mentioned in patches
> 10 and 11 :)

Well, it is not exactly clear to me how memory management would work (I
have not read patch 10 or 11 due to lack of time). At the moment,
releasing a hashmap means we can simply `free()` the stored pointers. If
you drop the requirement to make the `hashmap_entry` field the first
field of the enclosing `struct`, that is no longer possible.

Of course, you could add an `offsetof` value to the hashmap that says
what number we have to subtract from the stored pointer before calling
`free()`, but that sounds quite a bit more fragile to me than the
current design.

> > Maybe we can get a Coccinelle rule that verifies that `struct
> > hashmap_entryh` fields are always the first ones?
>
> At this point, why?  Given the goal is to remove that requirement
> entirely.

With a Coccinelle rule, we could maintain a simple design *and* be
certain that no user violates the assumption that the `hashmap_entry`
field is the first one in the enclosing `struct`.

Ciao,
Dscho

^ permalink raw reply	[flat|nested] 30+ messages in thread

* [RFC 04/11] coccicheck: detect hashmap_entry.hash assignment
  2019-08-26  2:43 ` [PATCH 04/11] hashmap_entry: detect improper initialization Eric Wong
  2019-08-27  9:10   ` Johannes Schindelin
@ 2019-09-08  7:49   ` Eric Wong
  2019-09-09 18:15     ` Junio C Hamano
  1 sibling, 1 reply; 30+ messages in thread
From: Eric Wong @ 2019-09-08  7:49 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git, Phillip Wood, Johannes Schindelin

Eric Wong <e@80x24.org> wrote:
> By renaming the "hash" field to "_hash", it's easy to spot
> improper initialization of hashmap_entry structs which
> can leave "hashmap_entry.next" uninitialized.

Junio, I'm planning to reroll this series.
(Sorry for not following up sooner)

Would you prefer I drop 04/11 "hashmap_entry: detect improper initialization"
in favor of the following?  Thanks.

---------8<--------
Subject: [PATCH 4/11] coccicheck: detect hashmap_entry.hash assignment

Assigning hashmap_entry.hash manually leaves hashmap_entry.next
uninitialized, which can be dangerous once the hashmap_entry is
inserted into a hashmap.   Detect those assignments and use
hashmap_entry_init, instead.

Signed-off-by: Eric Wong <e@80x24.org>
---
 contrib/coccinelle/hashmap.cocci | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 contrib/coccinelle/hashmap.cocci

diff --git a/contrib/coccinelle/hashmap.cocci b/contrib/coccinelle/hashmap.cocci
new file mode 100644
index 0000000000..d69e120ccf
--- /dev/null
+++ b/contrib/coccinelle/hashmap.cocci
@@ -0,0 +1,16 @@
+@ hashmap_entry_init_usage @
+expression E;
+struct hashmap_entry HME;
+@@
+- HME.hash = E;
++ hashmap_entry_init(&HME, E);
+
+@@
+identifier f !~ "^hashmap_entry_init$";
+expression E;
+struct hashmap_entry *HMEP;
+@@
+  f(...) {<...
+- HMEP->hash = E;
++ hashmap_entry_init(HMEP, E);
+  ...>}

^ permalink raw reply	[flat|nested] 30+ messages in thread

* Re: [RFC 04/11] coccicheck: detect hashmap_entry.hash assignment
  2019-09-08  7:49   ` [RFC 04/11] coccicheck: detect hashmap_entry.hash assignment Eric Wong
@ 2019-09-09 18:15     ` Junio C Hamano
  0 siblings, 0 replies; 30+ messages in thread
From: Junio C Hamano @ 2019-09-09 18:15 UTC (permalink / raw)
  To: Eric Wong; +Cc: git, Phillip Wood, Johannes Schindelin

Eric Wong <e@80x24.org> writes:

> Eric Wong <e@80x24.org> wrote:
>> By renaming the "hash" field to "_hash", it's easy to spot
>> improper initialization of hashmap_entry structs which
>> can leave "hashmap_entry.next" uninitialized.
>
> Junio, I'm planning to reroll this series.
> (Sorry for not following up sooner)
>
> Would you prefer I drop 04/11 "hashmap_entry: detect improper initialization"
> in favor of the following?  Thanks.

Automation is good ;-)
FWIW, I do not mind the original 04/11 myself too much, though.

Thanks.

> ---------8<--------
> Subject: [PATCH 4/11] coccicheck: detect hashmap_entry.hash assignment
>
> Assigning hashmap_entry.hash manually leaves hashmap_entry.next
> uninitialized, which can be dangerous once the hashmap_entry is
> inserted into a hashmap.   Detect those assignments and use
> hashmap_entry_init, instead.
>
> Signed-off-by: Eric Wong <e@80x24.org>
> ---
>  contrib/coccinelle/hashmap.cocci | 16 ++++++++++++++++
>  1 file changed, 16 insertions(+)
>  create mode 100644 contrib/coccinelle/hashmap.cocci
>
> diff --git a/contrib/coccinelle/hashmap.cocci b/contrib/coccinelle/hashmap.cocci
> new file mode 100644
> index 0000000000..d69e120ccf
> --- /dev/null
> +++ b/contrib/coccinelle/hashmap.cocci
> @@ -0,0 +1,16 @@
> +@ hashmap_entry_init_usage @
> +expression E;
> +struct hashmap_entry HME;
> +@@
> +- HME.hash = E;
> ++ hashmap_entry_init(&HME, E);
> +
> +@@
> +identifier f !~ "^hashmap_entry_init$";
> +expression E;
> +struct hashmap_entry *HMEP;
> +@@
> +  f(...) {<...
> +- HMEP->hash = E;
> ++ hashmap_entry_init(HMEP, E);
> +  ...>}

^ permalink raw reply	[flat|nested] 30+ messages in thread

end of thread, back to index

Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-08-26  2:43 [PATCH 00/11] hashmap: bugfixes, safety fixes, and WIP improvements Eric Wong
2019-08-26  2:43 ` [PATCH 01/11] diff: use hashmap_entry_init on moved_entry.ent Eric Wong
2019-08-27 13:31   ` Derrick Stolee
2019-08-26  2:43 ` [PATCH 02/11] packfile: use hashmap_entry in delta_base_cache_entry Eric Wong
2019-08-26  2:43 ` [PATCH 03/11] hashmap_entry_init takes "struct hashmap_entry *" Eric Wong
2019-08-27 13:35   ` Derrick Stolee
2019-08-28 15:01     ` Johannes Schindelin
2019-08-30 19:48       ` Eric Wong
2019-09-02 13:46         ` Johannes Schindelin
2019-08-26  2:43 ` [PATCH 04/11] hashmap_entry: detect improper initialization Eric Wong
2019-08-27  9:10   ` Johannes Schindelin
2019-08-27  9:49     ` Eric Wong
2019-08-27 22:16       ` Junio C Hamano
2019-08-28 15:04         ` Johannes Schindelin
2019-08-28  9:03       ` Phillip Wood
2019-08-30 19:52         ` Eric Wong
2019-09-08  7:49   ` [RFC 04/11] coccicheck: detect hashmap_entry.hash assignment Eric Wong
2019-09-09 18:15     ` Junio C Hamano
2019-08-26  2:43 ` [PATCH 05/11] hashmap_get_next takes "const struct hashmap_entry *" Eric Wong
2019-08-26  2:43 ` [PATCH 06/11] hashmap_add takes "struct " Eric Wong
2019-08-26  2:43 ` [PATCH 07/11] hashmap_get takes "const struct " Eric Wong
2019-08-26  2:43 ` [PATCH 08/11] hashmap_remove " Eric Wong
2019-08-26  2:43 ` [PATCH 09/11] hashmap_put takes "struct " Eric Wong
2019-08-26  2:43 ` [PATCH 10/11] introduce container_of macro Eric Wong
2019-08-27 14:49   ` Derrick Stolee
2019-08-28  9:11     ` Phillip Wood
2019-08-30 19:43     ` Eric Wong
2019-08-26  2:43 ` [PATCH 11/11] hashmap_get_next returns "struct hashmap_entry *" Eric Wong
2019-08-27 14:53   ` Derrick Stolee
2019-08-30 19:36     ` Eric Wong

git@vger.kernel.org list mirror (unofficial, one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox