Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Junio C Hamano]

Junio C Hamano  writes:

> Johannes Schindelin  writes:
>
>> Oh, we are already safely in Unrelated Tangent Land for a while, I would
>> think. Nothing of what we are discussing in this thread has anything to do
>> with Kevin's patch series,...
>
> Oh, no question about that.  Go back to my review, to which your
> message I am responding to is a reply to.  What you wrote are all
> about things after "This is a tangent, but this made me wonder if it
> is safe to simply free(3) the result...", which pointed out rough
> points in the hashmap API from the API user's point of view and
> suggested a few possible improvement opportunities.

In other words, I'd be happy with a patch like this, outside the
scope of and independent from this series.

When the hashmap_entry structure does acquire references to external
resources (which I wouldn't judge the likelihood of), this paragraph
will become stale, but that is exactly the point at which _clear()
function needs to be added to the API and described here, replacing
this paragraph.

I do not mind having an empty _clear() before that happens, but I do
not think it adds much safety.  A disciplined user of the API may
call that empty _clear() to make her code future-proof, but we know
there are undisciplined developers and reviewers and there will be
codepaths that call _init() without calling the empty _clear(), and
we won't notice it.  Whoever is adding the real need for _clear()
must audit the codebase at that point _anyway_, and that is why I
think having an empty _clear() before would not buy us much.

 Documentation/technical/api-hashmap.txt | 5 +
 1 file changed, 5 insertions(+)

diff --git a/Documentation/technical/api-hashmap.txt 
b/Documentation/technical/api-hashmap.txt
index ad7a5bd..1dcec3d 100644
--- a/Documentation/technical/api-hashmap.txt
+++ b/Documentation/technical/api-hashmap.txt
@@ -104,6 +104,11 @@ If `free_entries` is true, each hashmap_entry in the map 
is freed as well
 `entry` points to the entry to initialize.
 +
 `hash` is the hash code of the entry.
++
+The hashmap_entry structure does not hold references to external resources,
+and it is safe to just discard it once you are done with it (i.e. if
+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).
 
 `void *hashmap_get(const struct hashmap *map, const void *key, const void 
*keydata)`::
 
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Junio C Hamano]

Johannes Schindelin  writes:

> Hi Junio,
>
> On Mon, 1 Aug 2016, Junio C Hamano wrote:
>
>> Johannes Schindelin  writes:
>> 
>> > It would be a serious bug if hashmap_entry_init() played games with
>> > references, given its signature (that this function does not have any
>> > access to the hashmap structure, only to the entry itself):
>> >
>> >void hashmap_entry_init(void *entry, unsigned int hash)
>> 
>> I do not think we are on the same page.  The "reference to other
>> resource" I wondered was inside the hashmap_entry structure, IOW,
>> "the entry itself".
>
> Oh, I see now.
>
>> Which is declared to be opaque to the API users,
>
> Actually, not really. We cannot do that in C: we need to define the struct
> in hashmap.h so that its size is known to the users.

What I meant was what Documentation/technical/api-hashmap.txt said.
I know that we cannot embed a true "opaque" structure in C just as
you do.

> That is the reason, I guess, why we have the documentation in
> Documentation/technical/api-hashmap.txt: it would have to talk about your
> hypothetical hashmap_entry_clear() (which would better be named
> *_release() BTW, unless I misunderstood what you want a hypothetical
> future version of that function to do).

I think there is no misunderstanding on your part.  I am following
the conclusion (as I recall) of a discussion on the list not in so
distant past about X_free(x) that frees the resource an instance of
"struct X" holds and also the instance itself, and X_clear(x) that
only frees the resources without freeing the instance (the latter of
which allows x to be on stack, you do X_init() and conclude with
X_clear()).  The name X_clear() is more in line with existing API
functions like string_list_clear(), argv_array_clear().  An oddball
is strbuf_release(), which I think made you make the above comment.

>> I have a slight preference to avoid the lazy "void *", but that is
>> an unrelated tangent.
>
> Oh, we are already safely in Unrelated Tangent Land for a while, I would
> think. Nothing of what we are discussing in this thread has anything to do
> with Kevin's patch series,...

Oh, no question about that.  Go back to my review, to which your
message I am responding to is a reply to.  What you wrote are all
about things after "This is a tangent, but this made me wonder if it
is safe to simply free(3) the result...", which pointed out rough
points in the hashmap API from the API user's point of view and
suggested a few possible improvement opportunities.

>> I am saying that an uneven over-enginnering is bad.
>
> Hmm. I guess that the _init() function could be replaced by an _INIT macro
> a la STRBUF_INIT. Not sure it is really worth the effort, though.

I do not think so, as X_init() and X_INIT() from the point of view
of the API user would not make much difference; as long as the
documentation does not say it is safe to make it go out of scope
without "deinitialize" it, the reader will be left wondering.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Johannes Schindelin]

Hi Junio,

On Mon, 1 Aug 2016, Junio C Hamano wrote:

> Johannes Schindelin  writes:
> 
> > It would be a serious bug if hashmap_entry_init() played games with
> > references, given its signature (that this function does not have any
> > access to the hashmap structure, only to the entry itself):
> >
> > void hashmap_entry_init(void *entry, unsigned int hash)
> 
> I do not think we are on the same page.  The "reference to other
> resource" I wondered was inside the hashmap_entry structure, IOW,
> "the entry itself".

Oh, I see now.

> Which is declared to be opaque to the API users,

Actually, not really. We cannot do that in C: we need to define the struct
in hashmap.h so that its size is known to the users.

> so whoever defined that API cannot blame me for not checking its
> definition to see that it only has "unsigned int hash" and no allocated
> memory or open file descriptor in it that needs freeing.

That is the reason, I guess, why we have the documentation in
Documentation/technical/api-hashmap.txt: it would have to talk about your
hypothetical hashmap_entry_clear() (which would better be named
*_release() BTW, unless I misunderstood what you want a hypothetical
future version of that function to do).

And quite frankly, unless we *have* to, I would rather try to avoid
introducing that function as much as possible, as it would make using the
hashmap API even more finicky than it already is.

> By the way, the first parameter of the function being "void *" is
> merely to help lazy API users, who have their own structure that
> embeds the hashmap_entry as its first element, as API documentation
> tells them to do, e.g.
> 
>   struct foo {
>   struct hashmap_entry e;
> ... other "foo" specific fields come here ...
>   } foo;
> 
> and because of the lazy "void *", they do not have to do this:
> 
>   hashmap_entry_init(>e, ...);
> 
> which would be required if the first parameter were "struct
> hashmap_entry *", but they can just do this:
> 
>   hashmap_entry_init(, ...);

Yes, I know that. It is the common way to simulate subclassing in C, for
lack of a more compile-safe construct.

> I have a slight preference to avoid the lazy "void *", but that is
> an unrelated tangent.

Oh, we are already safely in Unrelated Tangent Land for a while, I would
think. Nothing of what we are discussing in this thread has anything to do
with Kevin's patch series, which is about trying to use resources more
sensibly when using the revision machinery's --cherry-pick option.

And since we are already there, I'll offer an opinion in favor of `void
*`: doing the >e dance could quite possibly suggest that `e` is a
field just like any other field (and does not necessarily *need* to be the
first).

But again, this has nothing to do with the patch series we are discussing
here.

> >> The fact that hashmap_entry_init() is there but there is no
> >> corresponding hashmap_entry_clear() hints that there is nothing to be
> >> worried about and I can see from the implementation of
> >> hashmap_entry_init() that no extra resource is held inside, but an
> >> API user should not have to guess.  We may want to do one of the two
> >> things:
> >> 
> >>  * document that an embedded hashmap_entry does not hold any
> >>resource that need to be released and it is safe to free the user
> >>structure that embeds one; or
> >> 
> >>  * implement hashmap_entry_clear() that currently is a no-op.
> >
> > Urgh. The only reason we have hashmap_entry_init() is that we *may* want
> > to extend `struct hashmap_entry` at some point. That is *already*
> > over-engineered because that point in time seems quite unlikely to arrive,
> > like, ever.
> 
> I am saying that an uneven over-enginnering is bad.

Hmm. I guess that the _init() function could be replaced by an _INIT macro
a la STRBUF_INIT. Not sure it is really worth the effort, though.

Ciao,
Dscho
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Eric Wong]

Junio C Hamano  wrote:
> Johannes Schindelin  writes:
> 
> > It would be a serious bug if hashmap_entry_init() played games with
> > references, given its signature (that this function does not have any
> > access to the hashmap structure, only to the entry itself):
> >
> > void hashmap_entry_init(void *entry, unsigned int hash)



> I have a slight preference to avoid the lazy "void *", but that is
> an unrelated tangent.

Me too.  I noticed this while working on the http-walker
speedups and my self-rejected last patch:

  https://public-inbox.org/git/20160711210243.GA1604%40whir/

Extracting list_entry from list.h (currently in next[1]) and
exposing that generically as "container_of" for use with
hashmap_* would make it safer-to-use and allow structs to belong
to multiple hashmaps.

list_entry is also an alias for container_of in the Linux
kernel, but we don't have enough code using list_* to
warrant two names for the same macro.

[1] https://public-inbox.org/git/20160711205131.1291-4-e%4080x24.org/
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Junio C Hamano]

Johannes Schindelin  writes:

> It would be a serious bug if hashmap_entry_init() played games with
> references, given its signature (that this function does not have any
> access to the hashmap structure, only to the entry itself):
>
>   void hashmap_entry_init(void *entry, unsigned int hash)

I do not think we are on the same page.  The "reference to other
resource" I wondered was inside the hashmap_entry structure, IOW,
"the entry itself".

Which is declared to be opaque to the API users, so whoever defined
that API cannot blame me for not checking its definition to see that
it only has "unsigned int hash" and no allocated memory or open file
descriptor in it that needs freeing.

By the way, the first parameter of the function being "void *" is
merely to help lazy API users, who have their own structure that
embeds the hashmap_entry as its first element, as API documentation
tells them to do, e.g.

struct foo {
struct hashmap_entry e;
... other "foo" specific fields come here ...
} foo;

and because of the lazy "void *", they do not have to do this:

hashmap_entry_init(>e, ...);

which would be required if the first parameter were "struct
hashmap_entry *", but they can just do this:

hashmap_entry_init(, ...);

I have a slight preference to avoid the lazy "void *", but that is
an unrelated tangent.

>> The fact that hashmap_entry_init() is there but there is no
>> corresponding hashmap_entry_clear() hints that there is nothing to
>> be worried about and I can see from the implementation of
>> hashmap_entry_init() that no extra resource is held inside, but an
>> API user should not have to guess.  We may want to do one of the two
>> things:
>> 
>>  * document that an embedded hashmap_entry does not hold any
>>resource that need to be released and it is safe to free the user
>>structure that embeds one; or
>> 
>>  * implement hashmap_entry_clear() that currently is a no-op.
>
> Urgh. The only reason we have hashmap_entry_init() is that we *may* want
> to extend `struct hashmap_entry` at some point. That is *already*
> over-engineered because that point in time seems quite unlikely to arrive,
> like, ever.

I am saying that an uneven over-enginnering is bad.

To be consistent with having _init() and declaring the entry
structure to be opaque, you would either need _clear() or document
you would never need to worry about the lack of _clear().
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Johannes Schindelin]

Hi Junio,

first of all: Kevin & I are colleagues and I helped prepare this patch
series. I had the idea to have a two-level patch ID to help e.g. when an
alternate object store is hosted on a (slow) network drive.

On Fri, 29 Jul 2016, Junio C Hamano wrote:

> Kevin Willford  writes:
> 
> >  struct patch_id *add_commit_patch_id(struct commit *commit,
> >  struct patch_ids *ids)
> >  {
> > -   return add_commit(commit, ids, 0);
> > +   struct patch_id *key = xcalloc(1, sizeof(*key));
> > +
> > +   if (init_patch_id_entry(key, commit, ids)) {
> > +   free(key);
> > +   return NULL;
> > +   }
> 
> This is a tangent, but this made me wonder if it is safe to simply
> free(3) the result of calling hashmap_entry_init() which is called
> in init_patch_id_entry().  It would obviously become a resource
> leak, if a hashmap_entry (which the api documentation says is "an
> opaque structure") holds any allocated resource.

It would be a serious bug if hashmap_entry_init() played games with
references, given its signature (that this function does not have any
access to the hashmap structure, only to the entry itself):

void hashmap_entry_init(void *entry, unsigned int hash)

Please note that the `void *entry` really needs to point to a struct whose
first field is of type `struct hashmap_entry`. This is not type-safe, of
course, but C does not allow a strong sub-typing of the kind we want to
use here.

> The fact that hashmap_entry_init() is there but there is no
> corresponding hashmap_entry_clear() hints that there is nothing to
> be worried about and I can see from the implementation of
> hashmap_entry_init() that no extra resource is held inside, but an
> API user should not have to guess.  We may want to do one of the two
> things:
> 
>  * document that an embedded hashmap_entry does not hold any
>resource that need to be released and it is safe to free the user
>structure that embeds one; or
> 
>  * implement hashmap_entry_clear() that currently is a no-op.

Urgh. The only reason we have hashmap_entry_init() is that we *may* want
to extend `struct hashmap_entry` at some point. That is *already*
over-engineered because that point in time seems quite unlikely to arrive,
like, ever.

In that light, as you said, why would we overengineer things even further
by introducing a hashmap_entry_clear(), especially given that we won't
catch any forgotten _clear() calls, given that it is a no-op anyway?

Let's just not.

Ciao,
Dscho
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Junio C Hamano]

Kevin Willford  writes:

> +static int patch_id_cmp(struct patch_id *a,
> + struct patch_id *b,
> + void *keydata)
>  {
> + return hashcmp(a->patch_id, b->patch_id);
>  }
>  
>  int init_patch_ids(struct patch_ids *ids)
>  {
>   memset(ids, 0, sizeof(*ids));
>   diff_setup(>diffopts);
>   DIFF_OPT_SET(>diffopts, RECURSIVE);
>   diff_setup_done(>diffopts);
> + hashmap_init(>patches, (hashmap_cmp_fn)patch_id_cmp, 256);
>   return 0;
>  }

This is a tangent, and I do not suggest to change patch 1/4 to flip
the style, but I am not sure if this is a good style, or casting it
the other way around is better from the type-checking point of view,
i.e.

static int cmp_fn(const void *a_, const void *b_, const void *keydata)
{
struct patch_id *a = a_;
struct patch_id *b = b_;
return hashcmp(a->patch_id, b->patch_id);
}

...
hashmap_init(..., cmp_fn, ...);
...

I see many existing calls to hashmap_init() follow this pattern, so
as I said, patch 1/4 is fine as-is.

Thanks.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Junio C Hamano]

Kevin Willford  writes:

> From: Kevin Willford 
>
> This change will use the hashmap from the hashmap.h to keep track of the
> patch_ids that have been encountered instead of using an internal
> implementation.  This simplifies the implementation of the patch ids.
>
> Signed-off-by: Kevin Willford 
> ---
>  patch-ids.c | 86 
> +
>  patch-ids.h |  7 +++--
>  2 files changed, 32 insertions(+), 61 deletions(-)

The patch text itself is almost unreadble because of a lot of
verbose code it had to carry before this change, and the removal of
that unreadable code of course is the point of this very welcome
clean-up ;-).  The resulting code is very readable.

>  struct patch_id *has_commit_patch_id(struct commit *commit,
>struct patch_ids *ids)
>  {
> - return add_commit(commit, ids, 1);
> + struct patch_id patch;
> +
> + memset(, 0, sizeof(patch));
> + if (init_patch_id_entry(, commit, ids))
> + return NULL;
> + return hashmap_get(>patches, , NULL);
>  }
>  
>  struct patch_id *add_commit_patch_id(struct commit *commit,
>struct patch_ids *ids)
>  {
> - return add_commit(commit, ids, 0);
> + struct patch_id *key = xcalloc(1, sizeof(*key));
> +
> + if (init_patch_id_entry(key, commit, ids)) {
> + free(key);
> + return NULL;
> + }

This is a tangent, but this made me wonder if it is safe to simply
free(3) the result of calling hashmap_entry_init() which is called
in init_patch_id_entry().  It would obviously become a resource
leak, if a hashmap_entry (which the api documentation says is "an
opaque structure") holds any allocated resource.

The fact that hashmap_entry_init() is there but there is no
corresponding hashmap_entry_clear() hints that there is nothing to
be worried about and I can see from the implementation of
hashmap_entry_init() that no extra resource is held inside, but an
API user should not have to guess.  We may want to do one of the two
things:

 * document that an embedded hashmap_entry does not hold any
   resource that need to be released and it is safe to free the user
   structure that embeds one; or

 * implement hashmap_entry_clear() that currently is a no-op.

If we anticipate that the hashmap implementation may gain more
fields in this "opaque" structure, the latter might be a more
future-proof approach, as all the callers of hashmap_entry_init()
would already be calling hashmap_entry_clear() to clean it up when
such a change to the hashmap implementation happens.  On the other
hand, a caller that does not call hashmap_entry_clear() would not be
noticed by anybody as leaking resources until such a change happens,
so the future-proofing may not have much practical value (iow, the
existing callers of _init() would need to be audited anyway to make
sure they also call _clear()).
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation

[Kevin Willford]

From: Kevin Willford 

This change will use the hashmap from the hashmap.h to keep track of the
patch_ids that have been encountered instead of using an internal
implementation.  This simplifies the implementation of the patch ids.

Signed-off-by: Kevin Willford 
---
 patch-ids.c | 86 +
 patch-ids.h |  7 +++--
 2 files changed, 32 insertions(+), 61 deletions(-)

diff --git a/patch-ids.c b/patch-ids.c
index a4d0016..db31fa6 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -16,90 +16,62 @@ int commit_patch_id(struct commit *commit, struct 
diff_options *options,
return diff_flush_patch_id(options, sha1);
 }
 
-static const unsigned char *patch_id_access(size_t index, void *table)
+static int patch_id_cmp(struct patch_id *a,
+   struct patch_id *b,
+   void *keydata)
 {
-   struct patch_id **id_table = table;
-   return id_table[index]->patch_id;
+   return hashcmp(a->patch_id, b->patch_id);
 }
 
-static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)
-{
-   return sha1_pos(id, table, nr, patch_id_access);
-}
-
-#define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */
-struct patch_id_bucket {
-   struct patch_id_bucket *next;
-   int nr;
-   struct patch_id bucket[BUCKET_SIZE];
-};
-
 int init_patch_ids(struct patch_ids *ids)
 {
memset(ids, 0, sizeof(*ids));
diff_setup(>diffopts);
DIFF_OPT_SET(>diffopts, RECURSIVE);
diff_setup_done(>diffopts);
+   hashmap_init(>patches, (hashmap_cmp_fn)patch_id_cmp, 256);
return 0;
 }
 
 int free_patch_ids(struct patch_ids *ids)
 {
-   struct patch_id_bucket *next, *patches;
-
-   free(ids->table);
-   for (patches = ids->patches; patches; patches = next) {
-   next = patches->next;
-   free(patches);
-   }
+   hashmap_free(>patches, 1);
return 0;
 }
 
-static struct patch_id *add_commit(struct commit *commit,
-  struct patch_ids *ids,
-  int no_add)
+static int init_patch_id_entry(struct patch_id *patch,
+  struct commit *commit,
+  struct patch_ids *ids)
 {
-   struct patch_id_bucket *bucket;
-   struct patch_id *ent;
-   unsigned char sha1[20];
-   int pos;
-
-   if (commit_patch_id(commit, >diffopts, sha1))
-   return NULL;
-   pos = patch_pos(ids->table, ids->nr, sha1);
-   if (0 <= pos)
-   return ids->table[pos];
-   if (no_add)
-   return NULL;
-
-   pos = -1 - pos;
+   if (commit_patch_id(commit, >diffopts, patch->patch_id))
+   return -1;
 
-   bucket = ids->patches;
-   if (!bucket || (BUCKET_SIZE <= bucket->nr)) {
-   bucket = xcalloc(1, sizeof(*bucket));
-   bucket->next = ids->patches;
-   ids->patches = bucket;
-   }
-   ent = >bucket[bucket->nr++];
-   hashcpy(ent->patch_id, sha1);
-
-   ALLOC_GROW(ids->table, ids->nr + 1, ids->alloc);
-   if (pos < ids->nr)
-   memmove(ids->table + pos + 1, ids->table + pos,
-   sizeof(ent) * (ids->nr - pos));
-   ids->nr++;
-   ids->table[pos] = ent;
-   return ids->table[pos];
+   hashmap_entry_init(patch, sha1hash(patch->patch_id));
+   return 0;
 }
 
 struct patch_id *has_commit_patch_id(struct commit *commit,
 struct patch_ids *ids)
 {
-   return add_commit(commit, ids, 1);
+   struct patch_id patch;
+
+   memset(, 0, sizeof(patch));
+   if (init_patch_id_entry(, commit, ids))
+   return NULL;
+
+   return hashmap_get(>patches, , NULL);
 }
 
 struct patch_id *add_commit_patch_id(struct commit *commit,
 struct patch_ids *ids)
 {
-   return add_commit(commit, ids, 0);
+   struct patch_id *key = xcalloc(1, sizeof(*key));
+
+   if (init_patch_id_entry(key, commit, ids)) {
+   free(key);
+   return NULL;
+   }
+
+   hashmap_add(>patches, key);
+   return key;
 }
diff --git a/patch-ids.h b/patch-ids.h
index eeb56b3..9569ee0 100644
--- a/patch-ids.h
+++ b/patch-ids.h
@@ -2,15 +2,14 @@
 #define PATCH_IDS_H
 
 struct patch_id {
-   unsigned char patch_id[20];
+   struct hashmap_entry ent;
+   unsigned char patch_id[GIT_SHA1_RAWSZ];
char seen;
 };
 
 struct patch_ids {
+   struct hashmap patches;
struct diff_options diffopts;
-   int nr, alloc;
-   struct patch_id **table;
-   struct patch_id_bucket *patches;
 };
 
 int commit_patch_id(struct commit *commit, struct diff_options *options,
-- 
2.9.2.gvfs.2.42.gb7633a3

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message