From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Prior to this patch series, the refs API said nothing about the
lifetime of the refname parameter passed to each_ref_fn callbacks by
the for_each_ref()-style iteration functions. De facto, the refnames
usually had long lives because they were pointers into the ref_cache
data structures, and those are only invalidated under rare
circumstances. And some callers were assuming a long lifetime, for
example storing references to the refname string instead of copying
it.
But it has long been the case that ref caches could be invalidated,
for example when a packed ref is deleted. AFAIK there was never much
clarity about what that might mean for callers.
Recently a number of race conditions related to references have been
discovered. There is likely to be a two-pronged solution to the
races:
* For traditional, filesystem-based references, there will have to be
more checks that the ref caches are still up-to-date at the time of
their use (see, for example, [1]). If not, the ref cache will have
to be invalidated and reloaded. Assuming that the invalidation of
the old cache includes freeing its memory, such an invalidation will
cause lots of refname strings to be freed even though callers might
still hold references to them.
* For server-class installations, filesystem-based references might
not be robust enough for 100% reliable operation, because the
reading of the complete set of references is not an atomic
operation. If another reference storage mechanism is developed,
there is no reason to expect the refnames strings to have long
lifetimes.
A prerequisite for either of these approaches is to harmonize what
callers assume and what the API guarantees.
The purpose of this patch series is to track down callers who assume
that the refnames that they receive via a each_ref_fn callback have
lifetimes beyond the duration of the callback invocation and to
rewrite them to work without that assumption. The final patch
documents explicitly that callers should not retain references to the
refnames.
A word about how I audited the code:
To find callers making unwarranted assumptions, I (temporarily)
changed do_one_ref() to do a xstrdup() of the refname, pass the copy
to the callback function, then free() the copy. This caused
ill-behaved callers to access freed memory, which could be detected by
running the testsuite under valgrind. There were indeed a number of
such errors. All of them are fixed by this patch series, and the test
just described now runs without errors.
I plan to do a second audit by hand to see if the test suite and/or
valgrind missed anything.
The last two patches are RFCs. I would like some input on the second
to last because I am not very familiar with how the object array entry
names are used, how many might be created, etc. The last patch is an
illustration of how I would like to change the API docs, but it will
only be ready when all of the code has been audited and adapted.
Please see especially my comments on these two patches for more
information.
[1] http://thread.gmane.org/gmane.comp.version-control.git/223299
Michael Haggerty (17):
describe: make own copy of refname
fetch: make own copies of refnames
add_rev_cmdline(): make a copy of the name argument
builtin_diff_tree(): make it obvious that function wants two entries
cmd_diff(): use an object_array for holding trees
cmd_diff(): rename local variable "list" -> "entry"
cmd_diff(): make it obvious which cases are exclusive of each other
revision: split some overly-long lines
gc_boundary(): move the check "alloc <= nr" to caller
get_revision_internal(): make check less mysterious
object_array: add function object_array_filter()
object_array_remove_duplicates(): rewrite to reduce copying
fsck: don't put a void*-shaped peg in a char*-shaped hole
find_first_merges(): initialize merges variable using initializer
find_first_merges(): remove unnecessary code
object_array_entry: copy name before storing in name field
refs: document the lifetime of the refname passed to each_ref_fn
builtin/describe.c | 6 +++--
builtin/diff.c | 68 ++++++++++++++++++++++++++----------------------------
builtin/fetch.c | 4 ++--
builtin/fsck.c | 2 +-
object.c | 50 +++++++++++++++++++++++++++++++--------
object.h | 23 ++++++++++++++++--
refs.h | 22 +++++++++++++-----
revision.c | 61 +++++++++++++++++++++++++-----------------------
revision.h | 32 ++++++++++++++++---------
submodule.c | 6 ++---
10 files changed, 172 insertions(+), 102 deletions(-)
--
1.8.2.3
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Do not retain a reference to the refname passed to the each_ref_fn
callback get_name(), because there is no guarantee of the lifetimes of
these names. Instead, make a local copy when needed.
Signed-off-by: Michael Haggerty <redacted>
---
builtin/describe.c | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Do not retain references to refnames passed to the each_ref_fn
callback add_existing(), because their lifetime is not guaranteed.
Signed-off-by: Michael Haggerty <redacted>
---
builtin/fetch.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Instead of assuming that the memory pointed to by the name argument
will live forever, make a local copy of it before storing it in the
ref_cmdline_info.
Signed-off-by: Michael Haggerty <redacted>
---
revision.c | 6 +++++-
1 file changed, 5 insertions(+), 1 deletion(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Change cmd_diff() to use a (struct object_array) for holding the trees
that it accumulates, rather than rolling its own equivalent.
Signed-off-by: Michael Haggerty <redacted>
---
builtin/diff.c | 37 ++++++++++++++++++-------------------
1 file changed, 18 insertions(+), 19 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Add a function that allows unwanted entries in an object_array to be
removed. This encapsulation is a step towards giving object_array
ownership of its entries' name memory.
Use the new function to replace revision.c:gc_boundary().
Signed-off-by: Michael Haggerty <redacted>
---
object.c | 16 ++++++++++++++++
object.h | 11 +++++++++++
revision.c | 28 ++++++++++------------------
3 files changed, 37 insertions(+), 18 deletions(-)
@@ -2575,7 +2567,7 @@ static struct commit *get_revision_internal(struct rev_info *revs)p->flags|=CHILD_SHOWN;if(revs->boundary_commits.nr==revs->boundary_commits.alloc){/* Try to make space and thereby avoid a realloc(): */-gc_boundary(&revs->boundary_commits);+object_array_filter(&revs->boundary_commits,entry_unshown,NULL);}add_object_array(p,NULL,&revs->boundary_commits);}
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
The source of this nonsense was
04d3975937 fsck: reduce stack footprint
, which wedged a pointer to parent into the object_array_entry's name
field. The parent pointer was passed to traverse_one_object(), even
though that function *didn't use it*.
The useless code has been deleted over time. Commit
a1cdc25172 fsck: drop unused parameter from traverse_one_object()
removed the parent pointer from traverse_one_object()'s
signature. Commit
c0aa335c95 Remove unused variables
removed the code that read the parent pointer back out of the name
field.
This commit takes the last step: don't write the parent pointer into
the name field in the first place.
Signed-off-by: Michael Haggerty <redacted>
---
I thought that this misuse of the name field was going to be a
showstopper for changing how the name's memory is managed, but then I
noticed that the value stored here is never used.
builtin/fsck.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
The lifetime of the refname was never documented, but some callers
used to assume that its lifetime was essentially permanent. The
commits leading up to this have disabused such callers of that notion.
The new status quo is that the API explicitly does *not* guarantee
that the refname string lives beyond a single callback invocation.
Document that fact.
Signed-off-by: Michael Haggerty <redacted>
---
This patch is the ultimate goal of the series, and I include it for
illustration, but it obviously shouldn't be committed before the
object_array questions have been answered and the rest of the code has
been audited more carefully.
refs.h | 22 ++++++++++++++++------
1 file changed, 16 insertions(+), 6 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
No names are ever set for the object_array_entries in merges, so there
is no need to pretend to copy them to the result array.
Signed-off-by: Michael Haggerty <redacted>
---
submodule.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Change object_array and object_array_entry to copy the name before
storing it in the name field, and free it when an entry is deleted
from the array. This is useful because some of the name strings
passed to add_object_array() or add_object_array_with_mode() are
refnames whose lifetime is not defined by the refs API (and which we
want to shorten).
Signed-off-by: Michael Haggerty <redacted>
---
This is the culmination of the last few commits. Since some callers
want to store refnames in the name field of object_array elements, but
we don't want those callers to assume that the refnames that they got
from for_each_ref() have infinite lifetime, the easiest thing to do is
have object_array make a copy of the names before writing them in the
entries, and to free the names for entries that are no longer in use.
This change fixes the problem, but has some disadvantages:
* It requires extra copies to be made of strings that are already
copies, for example when the results of path_name(path, name) are
used as a name in revision.c:add_object(). This might be rare
enough that it can be ignored (though the original result of
path_name() would have to be freed, which this patch doesn't do so
there is a memory leak).
* Many callers store the empty string ("") as the name; for example,
most of the entries created during a run of rev-list have "" as
their name. This means that lots of needless copies of "" are being
made. I think that the best solution to this problem would be to
store NULL rather than "" for such entries, but I haven't figured
out all of the places where the name is used.
The alternative would be to have callers make the copies if necessary
*before* passing the names into add_object_array(), and themselves
ensure that those copies get freed sometime. This would be more work:
effectively each object_array would have to have its own memory
ownership policy and we would have to figure out exactly where in the
code entries are added and removed from particular lists.
Since I'm not too clear on what these names are used for, how many
object_array entries are created in different scenarios, etc., I
decided to submit this patch as an RFC to get some feedback before I
work on a final solution.
object.c | 6 +++++-
object.h | 6 +++++-
2 files changed, 10 insertions(+), 2 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
There is no logical reason for this test to be here. At the caller we
might be able to figure out its meaning.
Signed-off-by: Michael Haggerty <redacted>
---
revision.c | 27 ++++++++++++---------------
1 file changed, 12 insertions(+), 15 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
The old version copied one entry to its destination position, then
deleted any matching entries from the tail of the array. This
required the tail of the array to be copied multiple times. It didn't
affect the complexity of the algorithm because the whole tail has to
be searched through anyway. But all the copying was unnecessary.
Instead, check for the existence of an entry with the same name in the
*head* of the list before copying an entry to its final position.
This way each entry has to be copied at most one time.
Extract a helper function contains_name() to do a bit of the work.
Signed-off-by: Michael Haggerty <redacted>
---
object.c | 32 +++++++++++++++++++++-----------
object.h | 6 +++++-
2 files changed, 26 insertions(+), 12 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
The condition under which gc_boundary() is called was previously
if (alloc <= nr)
. But by construction, nr can never exceed alloc, so the check looks
unnecessarily mysterious. In fact, the purpose of the check is to try
to avoid a realloc() call by shrinking the array if possible if it is
at its allocation limit when a new element is about to be added. So
change the check to
if (nr == alloc)
and add a comment to explain what's going on.
Signed-off-by: Michael Haggerty <redacted>
---
Please check that I have properly described the purpose of this check.
The way the code is written, it looks like a bad pattern of growth and
shrinkage of the array (namely, just under the resize limit) could
cause gc_boundary() to be called over and over again with (most of)
the same data. I hope that the author had some reason to believe that
such a pattern is unlikely.
revision.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
@@ -2573,8 +2573,10 @@ static struct commit *get_revision_internal(struct rev_info *revs)if(p->flags&(CHILD_SHOWN|SHOWN))continue;p->flags|=CHILD_SHOWN;-if(revs->boundary_commits.alloc<=revs->boundary_commits.nr)+if(revs->boundary_commits.nr==revs->boundary_commits.alloc){+/* Try to make space and thereby avoid a realloc(): */gc_boundary(&revs->boundary_commits);+}add_object_array(p,NULL,&revs->boundary_commits);}
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
Instead of accepting an array and using exactly two elements from the
array, take two single (struct object_array_entry *) arguments.
Signed-off-by: Michael Haggerty <redacted>
---
builtin/diff.c | 18 +++++++++---------
1 file changed, 9 insertions(+), 9 deletions(-)
@@ -153,7 +153,8 @@ static int builtin_diff_index(struct rev_info *revs,staticintbuiltin_diff_tree(structrev_info*revs,intargc,constchar**argv,-structobject_array_entry*ent)+structobject_array_entry*ent0,+structobject_array_entry*ent1){constunsignedchar*(sha1[2]);intswap=0;
@@ -161,13 +162,13 @@ static int builtin_diff_tree(struct rev_info *revs,if(argc>1)usage(builtin_diff_usage);-/* We saw two trees, ent[0] and ent[1].-*ifent[1]isuninteresting,theyareswapped+/* We saw two trees, ent0 and ent1.+*ifent1isuninteresting,theyareswapped*/-if(ent[1].item->flags&UNINTERESTING)+if(ent1->item->flags&UNINTERESTING)swap=1;-sha1[swap]=ent[0].item->sha1;-sha1[1-swap]=ent[1].item->sha1;+sha1[swap]=ent0->item->sha1;+sha1[1-swap]=ent1->item->sha1;diff_tree_sha1(sha1[0],sha1[1],"",&revs->diffopt);log_tree_diff_flush(revs);return0;
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:19
At first glance the OBJ_COMMIT, OBJ_TREE, and OBJ_BLOB cases look like
they might be mutually exclusive. But the OBJ_COMMIT case doesn't end
the loop iteration with "continue" like the other two cases, but
rather falls through. So use if...else if...else construct to make it
more obvious that only the last two cases are mutually exclusive.
Signed-off-by: Michael Haggerty <redacted>
---
builtin/diff.c | 9 ++++-----
1 file changed, 4 insertions(+), 5 deletions(-)
From: Johan Herland <hidden> Date: 2016-06-15 22:57:20
On Sun, May 19, 2013 at 10:26 PM, Michael Haggerty [off-list ref] wrote:
Recently a number of race conditions related to references have been
discovered. There is likely to be a two-pronged solution to the
races:
* For traditional, filesystem-based references, there will have to be
more checks that the ref caches are still up-to-date at the time of
their use (see, for example, [1]). If not, the ref cache will have
to be invalidated and reloaded. Assuming that the invalidation of
the old cache includes freeing its memory, such an invalidation will
cause lots of refname strings to be freed even though callers might
still hold references to them.
* For server-class installations, filesystem-based references might
not be robust enough for 100% reliable operation, because the
reading of the complete set of references is not an atomic
operation. If another reference storage mechanism is developed,
there is no reason to expect the refnames strings to have long
lifetimes.
(Sorry for going slightly off-topic and returning to the general
discussion on how to resolve the race conditions...)
For server-class installations we need ref storage that can be read
(and updated?) atomically, and the current system of loose + packed
files won't work since reading (and updating) more than a single file
is not an atomic operation. Trivially, one could resolve this by
dropping loose refs, and always using a single packed-refs file, but
that would make it prohibitively expensive to update refs (the entire
packed-refs file must be rewritten for every update).
Now, observe that we don't have these race conditions in the object
database, because it is an add-only immutable data store.
What if we stored the refs as a tree object in the object database,
referenced by a single (loose) ref? There would be a _single_ (albeit
highly contentious) file outside the object database that represent
the current state of the refs, but hopefully we can guarantee
atomicity when reading (and updating?) that one file. Transactions can
be done by:
1. Recording the tree id holding the refs before starting manipulation.
2. Creating a new tree object holding the manipulated state.
3. Re-checking the tree id before replacing the loose ref. If
unchanged: commit, else: rollback/error out.
All readers would trivially have access to a consistent refs view,
since the state of the entire refs hierarchy is held in the tree id
read from that single loose ref.
It seems to me this should be somewhat less prohibitively expensive
than maintaining all refs in a single packed-refs file. That said, we
do end up producing a few new objects for every single ref update,
most of which would be thrown away by a future "gc". This might bog
things down, but I'm not sure how much.
I'm sure someone must have had this idea before (although I don't
remember this alternative being raised at the Git Merge conference),
so please enlighten me as to why this won't work... ;)
...Johan
PS: Keeping reflogs is just a matter of wrapping the ref tree in a
commit object using the previous state of the ref tree as its parent.
--
Johan Herland, [off-list ref]
www.herland.net
From: Johan Herland <hidden> Date: 2016-06-15 22:57:20
On Sun, May 19, 2013 at 10:27 PM, Michael Haggerty [off-list ref] wrote:
This is the culmination of the last few commits. Since some callers
want to store refnames in the name field of object_array elements, but
we don't want those callers to assume that the refnames that they got
from for_each_ref() have infinite lifetime, the easiest thing to do is
have object_array make a copy of the names before writing them in the
entries, and to free the names for entries that are no longer in use.
This change fixes the problem, but has some disadvantages:
* It requires extra copies to be made of strings that are already
copies, for example when the results of path_name(path, name) are
used as a name in revision.c:add_object(). This might be rare
enough that it can be ignored (though the original result of
path_name() would have to be freed, which this patch doesn't do so
there is a memory leak).
* Many callers store the empty string ("") as the name; for example,
most of the entries created during a run of rev-list have "" as
their name. This means that lots of needless copies of "" are being
made. I think that the best solution to this problem would be to
store NULL rather than "" for such entries, but I haven't figured
out all of the places where the name is used.
Use strbufs?
No allocation (except for the strbuf object itself) is needed for
empty strings, and string ownership and be transferred to and from it
to prevent extra copies.
...Johan
--
Johan Herland, [off-list ref]
www.herland.net
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:20
This is a very interesting idea. "It's turtles all the way down."
On 05/20/2013 12:28 PM, Johan Herland wrote:
(Sorry for going slightly off-topic and returning to the general
discussion on how to resolve the race conditions...)
For server-class installations we need ref storage that can be read
(and updated?) atomically, and the current system of loose + packed
files won't work since reading (and updating) more than a single file
is not an atomic operation. Trivially, one could resolve this by
dropping loose refs, and always using a single packed-refs file, but
that would make it prohibitively expensive to update refs (the entire
packed-refs file must be rewritten for every update).
Correct, or the "packed-refs" file would have to be updated in place
using some database-style approach for locking/transactions/whatever.
Now, observe that we don't have these race conditions in the object
database, because it is an add-only immutable data store.
Except for prune, of course, which can cause race conditions WRT to writers.
What if we stored the refs as a tree object in the object database,
referenced by a single (loose) ref? There would be a _single_ (albeit
highly contentious) file outside the object database that represent
the current state of the refs, but hopefully we can guarantee
atomicity when reading (and updating?) that one file. Transactions can
be done by:
1. Recording the tree id holding the refs before starting manipulation.
2. Creating a new tree object holding the manipulated state.
3. Re-checking the tree id before replacing the loose ref. If
unchanged: commit, else: rollback/error out.
There are two closely related possibilities and I'm not sure which one
you mean:
* Effectively treat all of the refs as loose refs, but stored not in the
filesystem but rather in a hierarchical tree structure in the object
database. E.g., all of the refs directly under "refs/heads" would be in
one tree object, those in refs/remotes/foo in a second, those for
refs/remotes/bar in another etc. and all of them linked up together in a
tree object representing "refs".
* Effectively treat all of the refs as packed refs, but store the single
"packed-refs" file as a single object in the object database.
(The first alternative sounds more practical to me. I also guess that's
what you mean, since down below you say that each change would require
producing "a few objects".)
Of course in either case we couldn't use a tree object directly, because
these new "reference tree" objects would refer not only to blobs and
other trees but also to commits and tags.
All readers would trivially have access to a consistent refs view,
since the state of the entire refs hierarchy is held in the tree id
read from that single loose ref.
It seems to me this should be somewhat less prohibitively expensive
than maintaining all refs in a single packed-refs file. That said, we
do end up producing a few new objects for every single ref update,
most of which would be thrown away by a future "gc". This might bog
things down, but I'm not sure how much.
I'm sure someone must have had this idea before (although I don't
remember this alternative being raised at the Git Merge conference),
so please enlighten me as to why this won't work... ;)
[I know this is not what you are suggesting, but I am reminded of
Subversion, which stores trunk, branches, and tags in the same "tree"
space as the contents of the working trees. A Subversion commit
references a gigantic tree encompassing all branches of development and
all files on all of those branches (with cheap copies to reduce the
redundancy):
/
/trunk/
/trunk/Makefile
/trunk/src/
/trunk/src/foo.c
/branches/
/branches/next/
/branches/next/Makefile
/branches/next/src/
/branches/next/src/foo.c
/branches/pu/
/branches/pu/Makefile
/branches/pu/src/
/branches/pu/src/foo.c
/tags/
/tags/v1.8.2/
/tags/v1.8.2/Makefile
/tags/v1.8.2/src/
/tags/v1.8.2/src/foo.c
etc...
A Subversion commit thus describes the state of *every* branch and tag
at that moment in time. The model is conceptually very simple (in fact,
too simple, and I believe the Subversion developers regret not having
distinguished between the branch namespace and the file namespace).]
The main difficulty with this idea will be the extreme contention on
that "last loose reference file" pointing at the root of the reference
tree. Essentially *every* change to the repository will have to create
a new reference tree and point this file at the new version. I doubt
that would be a problem for short-lived operations, but I fear that a
long-lived operation would *never* get done. By the time it had
finished constructing its new reference tree, some other short-lived
operation will have changed it, and the long-lived process will have to
choose between
* Restart from the beginning.
* Die with a kind of "concurrent modification error".
* Resolve the difference between the reference tree at the start of its
operation and the reference tree as it exists when it is done with the
changes that they want to make. In some cases this might be able to be
done automatically as a kind of "reference tree merge" but the logic
might have to vary from case to case.
PS: Keeping reflogs is just a matter of wrapping the ref tree in a
commit object using the previous state of the ref tree as its parent.
Yes, there are a lot of nice aspects to this idea in that it reuses
concepts with which we are already familiar. For example, fetching from
a remote would approximately hook the remote's entire reference tree
into a subtree of the local "refs/remotes" reference subtree. But with
things like reflogs we would have to be careful not to keep obsolete
objects around *forever*--there would have to be some mechanism to prune
the old reference history.
Altogether a very interesting idea.
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:20
On 05/20/2013 12:33 PM, Johan Herland wrote:
On Sun, May 19, 2013 at 10:27 PM, Michael Haggerty [off-list ref] wrote:
quoted
This is the culmination of the last few commits. Since some callers
want to store refnames in the name field of object_array elements, but
we don't want those callers to assume that the refnames that they got
from for_each_ref() have infinite lifetime, the easiest thing to do is
have object_array make a copy of the names before writing them in the
entries, and to free the names for entries that are no longer in use.
This change fixes the problem, but has some disadvantages:
* It requires extra copies to be made of strings that are already
copies, for example when the results of path_name(path, name) are
used as a name in revision.c:add_object(). This might be rare
enough that it can be ignored (though the original result of
path_name() would have to be freed, which this patch doesn't do so
there is a memory leak).
* Many callers store the empty string ("") as the name; for example,
most of the entries created during a run of rev-list have "" as
their name. This means that lots of needless copies of "" are being
made. I think that the best solution to this problem would be to
store NULL rather than "" for such entries, but I haven't figured
out all of the places where the name is used.
Use strbufs?
No allocation (except for the strbuf object itself) is needed for
empty strings, and string ownership and be transferred to and from it
to prevent extra copies.
That would cost two extra size_t per object_array_entry. I have the
feeling that this structure is used often enough that the extra overhead
would be a disadvantage, but I'm not sure.
The obvious alternative would be to teach users to deal with NULL and
either add another constructor alternative that transfers string
ownership or *always* transfer string ownership and change the callers
to call xstrdup() if they don't already own the name string. I think I
will try that approach first.
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
From: Jeff King <hidden> Date: 2016-06-15 22:57:20
On Mon, May 20, 2013 at 04:42:38PM +0200, Michael Haggerty wrote:
quoted
quoted
* Many callers store the empty string ("") as the name; for example,
most of the entries created during a run of rev-list have "" as
their name. This means that lots of needless copies of "" are being
made. I think that the best solution to this problem would be to
store NULL rather than "" for such entries, but I haven't figured
out all of the places where the name is used.
Use strbufs?
No allocation (except for the strbuf object itself) is needed for
empty strings, and string ownership and be transferred to and from it
to prevent extra copies.
That would cost two extra size_t per object_array_entry. I have the
feeling that this structure is used often enough that the extra overhead
would be a disadvantage, but I'm not sure.
The obvious alternative would be to teach users to deal with NULL and
either add another constructor alternative that transfers string
ownership or *always* transfer string ownership and change the callers
to call xstrdup() if they don't already own the name string. I think I
will try that approach first.
You could use the same trick that strbuf does: instead of NULL, point to
a well-known empty string literal. Readers do not have to care about
this optimization at all; only writers need to recognize the well-known
pointer value. And since we do not update in place but only eventually
free, it really is just that anyone calling free() would do "if (name !=
well_known_empty_string)".
-Peff
From: Michael Haggerty <hidden> Date: 2016-06-15 22:57:20
On 05/20/2013 06:44 PM, Jeff King wrote:
On Mon, May 20, 2013 at 04:42:38PM +0200, Michael Haggerty wrote:
quoted
quoted
quoted
* Many callers store the empty string ("") as the name; for example,
most of the entries created during a run of rev-list have "" as
their name. This means that lots of needless copies of "" are being
made. I think that the best solution to this problem would be to
store NULL rather than "" for such entries, but I haven't figured
out all of the places where the name is used.
Use strbufs?
No allocation (except for the strbuf object itself) is needed for
empty strings, and string ownership and be transferred to and from it
to prevent extra copies.
That would cost two extra size_t per object_array_entry. I have the
feeling that this structure is used often enough that the extra overhead
would be a disadvantage, but I'm not sure.
The obvious alternative would be to teach users to deal with NULL and
either add another constructor alternative that transfers string
ownership or *always* transfer string ownership and change the callers
to call xstrdup() if they don't already own the name string. I think I
will try that approach first.
You could use the same trick that strbuf does: instead of NULL, point to
a well-known empty string literal. Readers do not have to care about
this optimization at all; only writers need to recognize the well-known
pointer value. And since we do not update in place but only eventually
free, it really is just that anyone calling free() would do "if (name !=
well_known_empty_string)".
Yes, that sounds like the best solution. Ultimately there is only one
writer, add_object_array_with_mode(), and it can do
if (!name)
entry->name = NULL;
else if (!*name)
entry->name = well_known_empty_string;
else
entry->name = xstrdup(name);
This should be a lot less intrusive than what I was trying: to change
callers who wrote name="" to write name=NULL instead. But it is a
nightmare to find all of the code that reads name and decide whether
they need to do
entry->name ? entry->name : ""
because that in turn depends on whether the code that wrote into the
same object_array always/never/sometimes wrote strings vs. NULL to the
name field. Blech, encapsulation is tough in C.
While I was chasing down callers, I came across other gems like
builtin/checkout.c:
add_pending_object(&revs, object, sha1_to_hex(object->sha1));
revision.c:
add_pending_object(revs, object, sha1_to_hex(object->sha1));
submodule.c:
add_pending_object(rev, &list->item->object,
sha1_to_hex(list->item->object.sha1));
so apparently I wasn't the only one befuddled by the lifetime and
ownership of the name field of object_array_entry.
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/