* Re: [RFC] adding support for md5
From: Linus Torvalds @ 2006-08-19 20:50 UTC (permalink / raw)
To: David Rientjes; +Cc: git
In-Reply-To: <Pine.LNX.4.63.0608172259280.25827@chino.corp.google.com>
On Thu, 17 Aug 2006, David Rientjes wrote:
>
> I'd like to solicit some comments about implementing support for md5 as a
> hash function that could be determined at runtime by the user during a
> project init-db.
I would _strongly_ suggest against this. At least not md5.
I can see the point of configurable hashes, but it would be for a stronger
hash than sha1, not for a (much) weaker one.
md5 is not only shorter, it's known to be broken, and there are attacks
out there that generate documents with the same md5 checksum quickly and
undetectably (ie depending on what the "document format" is, you might
actually not _see_ the corruption).
There's a real-life example of this (just google for "same md5") with a
postscript file, which when printed out still looks "valid".
In contrast, sha1 is still considered "hard", in that while you can
obviously always brute-force _any_ hash, the sha1 brute-forcing attack is
considered to be impractical and nobody has at least shown any realistic
version of the above postscript kind of hack.
In my fairly limited performance analysis, I've actually been surprised by
the fact that the hashing has never really shown up as a major issue in
any of my profiles. All the _real_ performance issues have been related to
memory usage, and things like the hash lookup (ie "memcmp()" was pretty
high on the list - just from comparing object names during lookup).
We've also had compression issues (initial check-in) and obviously the
delta selection used to be a _huge_ time-waster until the pack info reuse
code went in. But I don't think we've ever had a load that was really
hashing-limited.
So considering that md5 isn't _that_ much faster to compute (let's say
that it's ~30% slower), the biggest advantage of md5 would likely be just
the fact that 16 bytes is smaller than 20 bytes, and thus commit objects
and tree objects in particular could be smaller. But you'd be better off
just using the first 16 bytes of the sha1 than the md5 hash, if that was
the main goal.
So yes, maybe we'll want to make the hash choice a setup-time option, but
if we ever do, I don't think we should make md5 even a choice. It's just
not a very good hash, and no new program should start using it.
Linus
^ permalink raw reply
* Re: [PATCH] gitweb: use common parameter parsing and generation for "o", too.
From: Jakub Narebski @ 2006-08-19 21:44 UTC (permalink / raw)
To: git
In-Reply-To: <20060819183303.GC30022@admingilde.org>
Martin Waitz wrote:
> hoi :)
>
> On Sat, Aug 19, 2006 at 12:55:57PM +0200, Jakub Narebski wrote:
>>> Perhaps introduce a new function which is used to access the parameters?
>>> This new function could check the URL or CGI->param or whatever and then
>>> return the requested value.
>>
>> CGI->param. There is no reason to duplicate CGI module.
>
> yes there is.
> using CGI->param it is not possible to use nice URLs ala
> http://git.site.org/projectpath.git
>
> I would really appreciate to be able to use nice URLs in gitweb that
> correspond to the repository URL.
As far as I know it is now possible (of course if your web server is
configured to redirect / to gitweb.cgi, e.g. for Apache using ScriptAlias
directive) via PATH_INFO support. At least it is what is intended.
Gitweb doesn't generate links in such a way, yet, but this should be fairly
easy now, changing only href() subroutine.
But apart from this one parameter the rest have to be passed as CGI
parameters,
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* Re: [PATCH] gitweb: Support for snapshot
From: Junio C Hamano @ 2006-08-19 21:49 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git
In-Reply-To: <ec76rd$8qf$1@sea.gmane.org>
Jakub Narebski <jnareb@gmail.com> writes:
> Below comments to the patch.
>...
> Wouldn't it make it easier to understand code to put %feature hash
> and gitweb_check_feature subroutine _before_ subroutines for specific
> features?
>
> It would be enough to put:
> $feature{'snapshot'} = [\&feature_snapshot, 0, undef];
Yes; although actually even 'undef' is not needed, I think it
makes sense to have at least one there ;-).
> By the way, wouldn't it be better to use _hash_ for mixed meaning
> than _array_? I.e.
>
> our %feature =
> (
> # feature => {'sub' => feature-sub, 'override' => allow-override, 'default' => default options...]
>
> 'blame' => {'sub' => \&feature_blame, 'override' => 0, 'default' => 0},
> #or 'blame' => {'sub' => \&feature_blame, 'override' => 0, 'default' => [ 0 ]},
> 'snapshot' => {'sub' => \&feature_snapshot, 'override' => 0, 'default => [ 'x-gzip', 'gz', 'gzip' ]},
> );
I like it better except that you made it wider than my terminal
again making it a lot harder to read.
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Jakub Narebski @ 2006-08-19 21:47 UTC (permalink / raw)
To: git
In-Reply-To: <20060819202558.GE30022@admingilde.org>
Martin Waitz wrote:
> now that gitweb.cgi is autogenerated, git refuses to switch to old
> branches unless force is applied:
>
> fatal: Untracked working tree file 'gitweb/gitweb.cgi' would
> be overwritten by merge.
>
> This safety measure is quite useful normally, but for files that are
> explicitly marked as to-be-ignored it should not be neccessary.
>
> But all the code that handles .gitignore is only used by ls-files now.
> Does it make sense to add exclude handling to unpack-trees.c, too?
I think it is "better to be annoying but safe" idea of git. You can always
do "git checkout <branch> gitweb/gitweb.cgi" and "git checkout <branch>",
and not use -f.
Or add gitweb.cgi to .gitignore in the old branch.
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* Re: [RFC] adding support for md5
From: Petr Baudis @ 2006-08-19 22:30 UTC (permalink / raw)
To: linux; +Cc: rientjes, git
In-Reply-To: <20060819031931.486.qmail@science.horizon.com>
Pre Scriptum: I do not advocate supporting many hashing functions just
for the heck of it, but I don't like the "full sweep" approach _when_
(not "in case") we _need_ to change the hash function. After all,
currently we have to operate with the fact that the next one will likely
fall victim of attacks in time as well and this is going to be
periodical operation.
Dear diary, on Sat, Aug 19, 2006 at 05:19:31AM CEST, I got a letter
where linux@horizon.com said that...
> So you can get silly things like the need for a merge commit to
> record the merge of trees that are actually identical.
You can create an ordering of hashes based on their strength and then
rehash your objects to max() of hash types used in the operation. So, if
you're about to merge md5(x) and sha1(y), you first recompute the first
id as sha1(x). Of course "recomputing" needs to be a wee bit more
complex: you need to first substitute tree id for a common hash as well
(and recursively do the same in the trees); slow, yes, but you can
cache it.
It gets worse when you are about to recompute ancestry, so you need to
set up the hash usage transition so that you don't ever have to
- such an event is sufficiently rare that each branch keeper can declare
a flag day "before now I merged only md5 commits and from now on I
will merge only sha1 commits". The tool can help to enforce this.
This strategy will not help in 100% of the cases (md5git-based tool
takes sha1git-created commit and re-creates it based on a snapshot and
the precise same metadata) but I guess it's good enough.
It's good that this is just theory so far, though. I'd say let it be for
now (at least from the "emergency hash switch" standpoint) and do it
when it's needed; you will have to have people upgrade their Git at that
point anyway and the code would bitrot just sitting there and adding
so-far unnecessary complexity. We have worse problems at our hands right
now anyway.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Snow falling on Perl. White noise covering line noise.
Hides all the bugs too. -- J. Putnam
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Junio C Hamano @ 2006-08-19 22:39 UTC (permalink / raw)
To: Martin Waitz; +Cc: git
In-Reply-To: <20060819202558.GE30022@admingilde.org>
Martin Waitz <tali@admingilde.org> writes:
> This safety measure is quite useful normally, but for files that are
> explicitly marked as to-be-ignored it should not be neccessary.
>
> But all the code that handles .gitignore is only used by ls-files now.
> Does it make sense to add exclude handling to unpack-trees.c, too?
In principle, I am not opposed to the idea of making read-tree
take the ignore information into consideration.
But I would suggest you to be _extremely_ careful if you want to
try this. I do not have an example offhand, but I would not be
surprised at all if there is a valid use case where it is useful
to have a pattern that matches a tracked file in .gitignore
file.
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Junio C Hamano @ 2006-08-19 22:41 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git, Martin Waitz
In-Reply-To: <ec80sl$i25$2@sea.gmane.org>
Jakub Narebski <jnareb@gmail.com> writes:
> Martin Waitz wrote:
>
>> now that gitweb.cgi is autogenerated, git refuses to switch to old
>> branches unless force is applied:
>>
>> fatal: Untracked working tree file 'gitweb/gitweb.cgi' would
>> be overwritten by merge.
>>
>> This safety measure is quite useful normally, but for files that are
>> explicitly marked as to-be-ignored it should not be neccessary.
>>
>> But all the code that handles .gitignore is only used by ls-files now.
>> Does it make sense to add exclude handling to unpack-trees.c, too?
>
> I think it is "better to be annoying but safe" idea of git. You can always
> do "git checkout <branch> gitweb/gitweb.cgi" and "git checkout <branch>",
> and not use -f.
I think you are talking backwards. Newer branch have .cgi
generated and older branch has it tracked. After you have built
in a newer branch, checking out an older branch without -f
option would play it safe not to clobber .cgi which is
annoying. So workaround you would want to suggest is TO USE -f.
> Or add gitweb.cgi to .gitignore in the old branch.
And this "adding something to old one" is nonsense ;-).
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Petr Baudis @ 2006-08-19 22:44 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Martin Waitz, git
In-Reply-To: <7vac601hbb.fsf@assigned-by-dhcp.cox.net>
Dear diary, on Sun, Aug 20, 2006 at 12:39:20AM CEST, I got a letter
where Junio C Hamano <junkio@cox.net> said that...
> But I would suggest you to be _extremely_ careful if you want to
> try this. I do not have an example offhand, but I would not be
> surprised at all if there is a valid use case where it is useful
> to have a pattern that matches a tracked file in .gitignore
> file.
*.o and binary blobs of closed-source software.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
Snow falling on Perl. White noise covering line noise.
Hides all the bugs too. -- J. Putnam
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Jakub Narebski @ 2006-08-19 22:48 UTC (permalink / raw)
To: git
In-Reply-To: <7v3bbs1h8c.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano wrote:
> Jakub Narebski <jnareb@gmail.com> writes:
>
>> Martin Waitz wrote:
>>
>>> now that gitweb.cgi is autogenerated, git refuses to switch to old
>>> branches unless force is applied:
>>>
>>> fatal: Untracked working tree file 'gitweb/gitweb.cgi' would
>>> be overwritten by merge.
>>>
>>> This safety measure is quite useful normally, but for files that are
>>> explicitly marked as to-be-ignored it should not be neccessary.
>>>
>>> But all the code that handles .gitignore is only used by ls-files now.
>>> Does it make sense to add exclude handling to unpack-trees.c, too?
>>
>> I think it is "better to be annoying but safe" idea of git. You can always
>> do "git checkout <branch> gitweb/gitweb.cgi" and "git checkout <branch>",
>> and not use -f.
>
> I think you are talking backwards. Newer branch have .cgi
> generated and older branch has it tracked. After you have built
> in a newer branch, checking out an older branch without -f
> option would play it safe not to clobber .cgi which is
> annoying. So workaround you would want to suggest is TO USE -f.
If I remember correctly that is what I did when "master" (and I had switch
to master to do "git pull origin") didn't contain gitweb.cgi -> gitweb.perl
rename. My proposed solution first overwrites generated gitweb.cgi by
tracked file (i'm not sure if this is feature or bug that git-checkout
with file specified (path limit specified?) doesn't need -f, and then
you can do git-checkout full branch without -f.
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Junio C Hamano @ 2006-08-20 1:34 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git
In-Reply-To: <ec84gg$p2l$1@sea.gmane.org>
Jakub Narebski <jnareb@gmail.com> writes:
> ... I'm not sure if this is feature or bug that git-checkout
> with file specified (path limit specified?) doesn't need -f
This is definitely a feature we deliberately added long after
git-checkout was initially written, in reponse to specific
requests from users. Back then the only way to revert to index
or HEAD was to "checkout-index -f -q -u -a" or "reset --hard"
and it was cumbersome to revert only a single path.
I have been wondering if we wanted to be able to say:
git checkout HEAD gitweb/
to revert everything under named hierarchy, but we haven't heard
user requests for this. This is way more dangerous than my
liking so personally I am happy that we do not have it.
^ permalink raw reply
* [PATCH] Helper function to shell quote all arg values at once.
From: Christian Couder @ 2006-08-20 6:07 UTC (permalink / raw)
To: Junio Hamano; +Cc: git
The new sq_quote_argv function is used to refactor the
tracing code in "git.c" and "exec_cmd.c".
This function allocates memory and fills it with a string
containing the quoted argument values. Then it returns a
pointer to this memory that must be freed afterwards.
---
exec_cmd.c | 11 +++--------
git.c | 22 +++++++---------------
quote.c | 33 +++++++++++++++++++++++++++++++++
quote.h | 1 +
4 files changed, 44 insertions(+), 23 deletions(-)
diff --git a/exec_cmd.c b/exec_cmd.c
index e30936d..6d215d8 100644
--- a/exec_cmd.c
+++ b/exec_cmd.c
@@ -98,15 +98,10 @@ int execv_git_cmd(const char **argv)
argv[0] = git_command;
if (getenv("GIT_TRACE")) {
- const char **p = argv;
- fputs("trace: exec:", stderr);
- while (*p) {
- fputc(' ', stderr);
- sq_quote_print(stderr, *p);
- ++p;
- }
- putc('\n', stderr);
+ char *arg_str = sq_quote_argv(argv, -1);
+ fprintf(stderr, "trace: exec: %s\n", arg_str);
fflush(stderr);
+ free(arg_str);
}
/* execve() can only ever return if it fails */
diff --git a/git.c b/git.c
index 930998b..ff4ba66 100644
--- a/git.c
+++ b/git.c
@@ -180,15 +180,11 @@ static int handle_alias(int *argcp, cons
die("recursive alias: %s", alias_command);
if (getenv("GIT_TRACE")) {
- int i;
- fprintf(stderr, "trace: alias expansion: %s =>",
- alias_command);
- for (i = 0; i < count; ++i) {
- fputc(' ', stderr);
- sq_quote_print(stderr, new_argv[i]);
- }
- fputc('\n', stderr);
+ char *arg_str = sq_quote_argv(new_argv, count);
+ fprintf(stderr, "trace: alias expansion: %s => %s\n",
+ alias_command, arg_str);
fflush(stderr);
+ free(arg_str);
}
new_argv = realloc(new_argv, sizeof(char*) *
@@ -292,14 +288,10 @@ static void handle_internal_command(int
if (p->option & USE_PAGER)
setup_pager();
if (getenv("GIT_TRACE")) {
- int i;
- fprintf(stderr, "trace: built-in: git");
- for (i = 0; i < argc; ++i) {
- fputc(' ', stderr);
- sq_quote_print(stderr, argv[i]);
- }
- putc('\n', stderr);
+ char *arg_str = sq_quote_argv(argv, argc);
+ fprintf(stderr, "trace: built-in: git %s\n", arg_str);
fflush(stderr);
+ free(arg_str);
}
exit(p->fn(argc, argv, prefix));
diff --git a/quote.c b/quote.c
index e220dcc..2e6289b 100644
--- a/quote.c
+++ b/quote.c
@@ -74,6 +74,39 @@ char *sq_quote(const char *src)
return buf;
}
+char *sq_quote_argv(const char** argv, int count)
+{
+ char *buf, *to;
+ int i;
+ size_t len;
+
+ /* Count argv if needed. */
+ if (count < 0) {
+ char **p = (char **)argv;
+ count = 0;
+ while (*p++) count++;
+ }
+
+ /* Get destination buffer length. */
+ len = count ? count : 1;
+ for (i = 0; i < count; ++i)
+ len += sq_quote_buf(NULL, 0, argv[i]);
+
+ /* Alloc destination buffer. */
+ to = buf = xmalloc(len);
+
+ /* Copy into destination buffer. */
+ for (i = 0; i < count; ++i) {
+ if (i) *to++ = ' ';
+ to += sq_quote_buf(to, len, argv[i]);
+ }
+
+ if (!count)
+ *buf = 0;
+
+ return buf;
+}
+
char *sq_dequote(char *arg)
{
char *dst = arg;
diff --git a/quote.h b/quote.h
index fc5481e..a6c4611 100644
--- a/quote.h
+++ b/quote.h
@@ -31,6 +31,7 @@ #include <stdio.h>
extern char *sq_quote(const char *src);
extern void sq_quote_print(FILE *stream, const char *src);
extern size_t sq_quote_buf(char *dst, size_t n, const char *src);
+extern char *sq_quote_argv(const char** argv, int count);
/* This unwraps what sq_quote() produces in place, but returns
* NULL if the input does not look like what sq_quote would have
--
1.4.2.g44496-dirty
^ permalink raw reply related
* Re: git refuses to switch to older branches
From: Alex Riesen @ 2006-08-20 7:26 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Martin Waitz, git
In-Reply-To: <7vac601hbb.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano, Sun, Aug 20, 2006 00:39:20 +0200:
> Martin Waitz <tali@admingilde.org> writes:
>
> > This safety measure is quite useful normally, but for files that are
> > explicitly marked as to-be-ignored it should not be neccessary.
> >
> > But all the code that handles .gitignore is only used by ls-files now.
> > Does it make sense to add exclude handling to unpack-trees.c, too?
>
> In principle, I am not opposed to the idea of making read-tree
> take the ignore information into consideration.
>
> But I would suggest you to be _extremely_ careful if you want to
It should be optional. And off by default, people already have got
scripts depending on this behaviour (well, I have).
> try this. I do not have an example offhand, but I would not be
> surprised at all if there is a valid use case where it is useful
> to have a pattern that matches a tracked file in .gitignore
> file.
>
Ignored directory and but some files/subdirectories in it are tracked,
because this is temporary or externally changed data (I have both
examples).
^ permalink raw reply
* Re: [PATCH 2/2] Look for a commit's parents in the standard way.
From: Catalin Marinas @ 2006-08-20 10:43 UTC (permalink / raw)
To: Yann Dirson; +Cc: git
In-Reply-To: <20060814165544.20350.41590.stgit@gandelf.nowhere.earth>
On 14/08/06, Yann Dirson <ydirson@altern.org> wrote:
> This has the direct effect of taking info/grafts into account, since
> ignoring it only causes confusion.
I don't know the difference but is there any between parsing the
commit file and using git-rev-list --parents?
> + self.__parents = split(_output_lines('git-rev-list --parents --max-count=1 %s' % id_hash)[0])[1:]
Instead of using the split() method, you could call
_output_lines('git-rev-list --parents --max-count=1 %s' %
id_hash)[0].split()[1:]. Maybe that's why they might deprecate the
global split method.
Setting self.__parents by calling get-rev-list would have a
performance impact on the push operation. I think we could remove the
__parents variable and only call git-rev-parse in get_parents() or
get_parent().
--
Catalin
^ permalink raw reply
* [ANNOUNCE] git-rev-size: calculate sizes of repository
From: Rutger Nijlunsing @ 2006-08-20 10:54 UTC (permalink / raw)
To: git
[-- Attachment #1: Type: text/plain, Size: 1519 bytes --]
Hi,
Just created as answer to a request on IRC: a script to get the sizes
of a repository and various stages. It caches all sizes it finds, so
is quite fast once it has ramped up.
Example on git repo:
$ git-rev-size.rb HEAD~10..HEAD
ef75951ecabd53b5ed816eb596992f8d222d0fe3 21 694 3343495
a625daccb1750c56768481ec9a5dfd4f9053774e 21 694 3343492
55c3eb434ab6d489c632263239be15a1054df7f2 21 694 3343481
a89fccd28197fa179828c8596791ff16e2268d20 21 694 3343523
d4baf9eaf47ea1ba204f1ab5ecd22326913dd081 21 694 3343498
409d1d2053657f73a3222651111740606122aa80 21 694 3343423
076a10c7282a08f783a28c1b64d0e114a3fe3d39 21 694 3342501
8e3abd4c97b8e7e1128ad0cc44dcc267f478659a 21 694 3342485
500a99935dc157a6625b4decae0b97e896061c2c 21 692 3334754
6493cc09c2aa626ffbe6024dd705e1495c2d87e4 21 692 3334511
d78b0f3d6aa04510dd0c22c3853d3954c5f5b531 21 688 3322774
0fc82cff12a887c1e0e7e69937dbd8a82843c081 21 694 3343352
42f774063db1442fc3815f596d263f90dcd8380b 21 694 3344828
520cd3eca5743bebd217423e1fd0721f32613bb1 21 693 3344115
789a09b4874ae2616987794e0e739b8227957175 21 692 3335517
c35f4c371ac12f4d29b08e46c519ddc0a6494f6e 21 691 3330286
Numbers are SHA1 hash, number of trees, number of blobs and total
number of bytes in those blobs.
You can also find it on http://www.wingding.demon.nl/git-rev-size.rb
--
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------
[-- Attachment #2: git-rev-size.rb --]
[-- Type: text/plain, Size: 2075 bytes --]
#!/usr/bin/env ruby
# Calculates sizes of repository at different commits in git
#
# 20060819 Initial release
# 20060820 Pass arguments to git-rev-list
#
# (c)2006 R. Nijlunsing <git@tux.tmfweb.nl>
# License: LGPLv2
require 'set'
require 'enumerator'
if ARGV.empty?
puts "Calculates sizes of repository at different commits"
puts
puts "Usage: #{$0} <arguments for git-rev-list>"
puts "Example: #{$0} HEAD"
exit 1
end
class Sizes
attr_reader :trees, :blobs, :bytes
def initialize(trees, blobs, bytes); @trees = trees; @blobs = blobs; @bytes = bytes; end
def add(o); @trees += o.trees; @blobs += o.blobs; @bytes += o.bytes; end
end
def tree_size(tree)
return $sha2size[tree] if $sha2size.include?(tree)
size = Sizes.new(1, 0, 0)
blobs = [] # Blobs with unknown sizes
File.popen("git cat-file -p #{tree}", "r") { |io|
while line = io.gets
line =~ %r{^[0-9]{6} ([a-z]+) ([0-9a-f]+)}
type, sha1 = $1, $2
if $sha2size.include?(sha1)
size.add($sha2size[sha1])
elsif type == "tree"
size.add(tree_size(sha1))
elsif type == "blob"
blobs << sha1
else
raise type
end
end
}
if blobs.size > 0
# Do all _blobs_ at once. For this to help, git-cat-file should accept
# more than one filename a time.
blobs.each_slice(1) { |blobs_slice|
File.popen("git cat-file -s #{blobs_slice.join(' ')}", "r") { |io|
blobs_slice.each { |blob|
blob_size = $sha2size[blob] = Sizes.new(0, 1, io.gets.to_i)
size.add(blob_size)
}
}
}
end
$sha2size[tree] = size
end
$sha2size = {} # SHA1 -> Sizes
File.popen("git rev-list #{ARGV.join(' ')}", "r") do |cio|
while commit = cio.gets
tree = nil # Root tree of this commit
commit = commit.chomp
File.popen("git cat-file -p #{commit}", "r") do |io|
while (line = io.gets) && !tree
tree = $1 if line =~ %r{^tree ([a-f0-9]+)}
end
end
if tree
sizes = tree_size(tree)
puts "#{commit} #{sizes.trees} #{sizes.blobs} #{sizes.bytes}"
end
end
end
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Martin Waitz @ 2006-08-20 12:19 UTC (permalink / raw)
To: Alex Riesen; +Cc: Junio C Hamano, git
In-Reply-To: <20060820072612.GA6003@steel.home>
[-- Attachment #1: Type: text/plain, Size: 1616 bytes --]
hoi :)
On Sun, Aug 20, 2006 at 09:26:12AM +0200, Alex Riesen wrote:
> Junio C Hamano, Sun, Aug 20, 2006 00:39:20 +0200:
> > Martin Waitz <tali@admingilde.org> writes:
> >
> > > This safety measure is quite useful normally, but for files that are
> > > explicitly marked as to-be-ignored it should not be neccessary.
> > >
> > > But all the code that handles .gitignore is only used by ls-files now.
> > > Does it make sense to add exclude handling to unpack-trees.c, too?
> >
> > In principle, I am not opposed to the idea of making read-tree
> > take the ignore information into consideration.
> >
> > But I would suggest you to be _extremely_ careful if you want to
>
> It should be optional. And off by default, people already have got
> scripts depending on this behaviour (well, I have).
but having this sort of behaviour optional is bad, I think.
Some people will depend on one semantic and others on the other.
And then get bite if they want to share their scripts.
We have to find _one_ semantic that always works.
> > try this. I do not have an example offhand, but I would not be
> > surprised at all if there is a valid use case where it is useful
> > to have a pattern that matches a tracked file in .gitignore
> > file.
>
> Ignored directory and but some files/subdirectories in it are tracked,
> because this is temporary or externally changed data (I have both
> examples).
but do you have non-tracked files in the ignored directory that you
really care about, i.e. which must not be overridden by a tracked file
with the same name?
--
Martin Waitz
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Martin Waitz @ 2006-08-20 12:21 UTC (permalink / raw)
To: Petr Baudis; +Cc: Junio C Hamano, git
In-Reply-To: <20060819224457.GB23891@pasky.or.cz>
[-- Attachment #1: Type: text/plain, Size: 814 bytes --]
hoi :)
On Sun, Aug 20, 2006 at 12:44:57AM +0200, Petr Baudis wrote:
> Dear diary, on Sun, Aug 20, 2006 at 12:39:20AM CEST, I got a letter
> where Junio C Hamano <junkio@cox.net> said that...
> > But I would suggest you to be _extremely_ careful if you want to
> > try this. I do not have an example offhand, but I would not be
> > surprised at all if there is a valid use case where it is useful
> > to have a pattern that matches a tracked file in .gitignore
> > file.
>
> *.o and binary blobs of closed-source software.
but if you want to switch from one branch which has the .o file
built from source to another branch which has the .o file tracked
in binary form, wouldn't you want to remove the generated file
in order to store the tracked one from the new branch?
--
Martin Waitz
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: git refuses to switch to older branches
From: Johannes Schindelin @ 2006-08-20 12:48 UTC (permalink / raw)
To: Martin Waitz; +Cc: Petr Baudis, Junio C Hamano, git
In-Reply-To: <20060820122128.GG30022@admingilde.org>
Hi,
On Sun, 20 Aug 2006, Martin Waitz wrote:
> On Sun, Aug 20, 2006 at 12:44:57AM +0200, Petr Baudis wrote:
> > Dear diary, on Sun, Aug 20, 2006 at 12:39:20AM CEST, I got a letter
> > where Junio C Hamano <junkio@cox.net> said that...
> > > But I would suggest you to be _extremely_ careful if you want to
> > > try this. I do not have an example offhand, but I would not be
> > > surprised at all if there is a valid use case where it is useful
> > > to have a pattern that matches a tracked file in .gitignore
> > > file.
> >
> > *.o and binary blobs of closed-source software.
>
> but if you want to switch from one branch which has the .o file
> built from source to another branch which has the .o file tracked
> in binary form, wouldn't you want to remove the generated file
> in order to store the tracked one from the new branch?
Not necessarily. Sometimes you have files in your working directory, which
are not in your repository, you know?
Ciao,
Dscho
^ permalink raw reply
* [PATCH] Added support for dropping privileges to git-daemon.
From: Tilman Sauerbeck @ 2006-08-19 12:27 UTC (permalink / raw)
To: git
In-Reply-To: <20060819172533.GB64962@gaz.sfgoth.com>
Signed-off-by: Tilman Sauerbeck <tilman@code-monkey.de>
---
My idea was to keep the code simple :)
Anyway, this patch has the code you proposed.
Documentation/git-daemon.txt | 11 +++++++++-
daemon.c | 45 +++++++++++++++++++++++++++++++++++++++++-
2 files changed, 54 insertions(+), 2 deletions(-)
diff --git a/Documentation/git-daemon.txt b/Documentation/git-daemon.txt
index 0f7d274..3c1bc85 100644
--- a/Documentation/git-daemon.txt
+++ b/Documentation/git-daemon.txt
@@ -11,7 +11,8 @@ SYNOPSIS
'git-daemon' [--verbose] [--syslog] [--inetd | --port=n] [--export-all]
[--timeout=n] [--init-timeout=n] [--strict-paths]
[--base-path=path] [--user-path | --user-path=path]
- [--reuseaddr] [--detach] [--pid-file=file] [directory...]
+ [--reuseaddr] [--detach] [--pid-file=file]
+ [--user=u [--group=g]] [directory...]
DESCRIPTION
-----------
@@ -93,6 +94,14 @@ OPTIONS
--pid-file=file::
Save the process id in 'file'.
+--user=u::
+--group=g::
+ These two options may be used to make `git-daemon` change its uid and
+ gid before entering the server loop.
+ The uid that's used is the one of 'u'. If `group` is specified,
+ the gid is set to the one of 'g', otherwise, the default gid
+ of 'u' is used.
+
<directory>::
A directory to add to the whitelist of allowed directories. Unless
--strict-paths is specified this will also include subdirectories
diff --git a/daemon.c b/daemon.c
index 012936f..70be10f 100644
--- a/daemon.c
+++ b/daemon.c
@@ -7,6 +7,8 @@ #include <netdb.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <syslog.h>
+#include <pwd.h>
+#include <grp.h>
#include "pkt-line.h"
#include "cache.h"
#include "exec_cmd.h"
@@ -14,12 +16,15 @@ #include "exec_cmd.h"
static int log_syslog;
static int verbose;
static int reuseaddr;
+static const char *user;
+static const char *group;
static const char daemon_usage[] =
"git-daemon [--verbose] [--syslog] [--inetd | --port=n] [--export-all]\n"
" [--timeout=n] [--init-timeout=n] [--strict-paths]\n"
" [--base-path=path] [--user-path | --user-path=path]\n"
-" [--reuseaddr] [--detach] [--pid-file=file] [directory...]";
+" [--reuseaddr] [--detach] [--pid-file=file]\n"
+" [--user=u] [--group=g] [directory...]";
/* List of acceptable pathname prefixes */
static char **ok_paths;
@@ -701,6 +706,30 @@ static void store_pid(const char *path)
fclose(f);
}
+static void drop_privileges()
+{
+ struct passwd *p;
+ struct group *g;
+ gid_t gid;
+
+ p = getpwnam (user);
+ if (!p)
+ die("user not found - %s", user);
+
+ if (!group)
+ gid = p->pw_gid;
+ else {
+ g = getgrnam (group);
+ if (!g)
+ die("group not found - %s", group);
+
+ gid = g->gr_gid;
+ }
+
+ if (initgroups (p->pw_name, gid) || setgid (gid) || setuid (p->pw_uid))
+ die("cannot drop privileges");
+}
+
static int serve(int port)
{
int socknum, *socklist;
@@ -709,6 +738,9 @@ static int serve(int port)
if (socknum == 0)
die("unable to allocate any listen sockets on port %u", port);
+ if (user)
+ drop_privileges();
+
return service_loop(socknum, socklist);
}
@@ -791,6 +823,14 @@ int main(int argc, char **argv)
log_syslog = 1;
continue;
}
+ if (!strncmp(arg, "--user=", 7)) {
+ user = arg + 7;
+ continue;
+ }
+ if (!strncmp(arg, "--group=", 8)) {
+ group = arg + 8;
+ continue;
+ }
if (!strcmp(arg, "--")) {
ok_paths = &argv[i+1];
break;
@@ -802,6 +842,9 @@ int main(int argc, char **argv)
usage(daemon_usage);
}
+ if (group && !user)
+ die("--group supplied without --user");
+
if (log_syslog) {
openlog("git-daemon", 0, LOG_DAEMON);
set_die_routine(daemon_die);
--
1.4.2
^ permalink raw reply related
* Re: [ANNOUNCE] git-rev-size: calculate sizes of repository
From: Johannes Schindelin @ 2006-08-20 13:20 UTC (permalink / raw)
To: git; +Cc: git
In-Reply-To: <20060820105452.GA19630@nospam.com>
Hi,
On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:
> You can also find it on http://www.wingding.demon.nl/git-rev-size.rb
Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?
Ciao,
Dscho
^ permalink raw reply
* Re: [ANNOUNCE] git-rev-size: calculate sizes of repository
From: Rutger Nijlunsing @ 2006-08-20 15:24 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: git
In-Reply-To: <Pine.LNX.4.63.0608201519360.28360@wbgn013.biozentrum.uni-wuerzburg.de>
On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:
> Hi,
>
> On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:
>
> > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb
>
> Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?
I _knew_ it... Please go bug someone else. The only thing I did was
help someone, and for that I choose my own tools since I do it for
fun. I don't ask for inclusion in the git archive. I don't ask you to
review it, download it, read it nor use it. Just ignore this post if
Ruby offends you and this problem wasn't your itch.
Please.
--
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------
^ permalink raw reply
* Re: [ANNOUNCE] git-rev-size: calculate sizes of repository
From: Johannes Schindelin @ 2006-08-20 16:09 UTC (permalink / raw)
To: Rutger Nijlunsing; +Cc: git
In-Reply-To: <20060820152404.GA5679@nospam.com>
Hi,
On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:
> On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:
> > Hi,
> >
> > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:
> >
> > > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb
> >
> > Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?
>
> I _knew_ it... Please go bug someone else. The only thing I did was
> help someone, and for that I choose my own tools since I do it for
> fun.
Fair enough.
-- 8< --
[PATCH] Add git-rev-size
This tool spits out the number of trees, the number of blobs, and the total
bytes of the blobs for a given rev range.
Most notably, it adds an object hash map structure to the library.
Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
---
Makefile | 4 ++
builtin-rev-size.c | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++
builtin.h | 1 +
git.c | 1 +
hash.c | 50 ++++++++++++++++++++++++++++
hash.h | 12 +++++++
6 files changed, 159 insertions(+), 1 deletions(-)
diff --git a/Makefile b/Makefile
index a86f289..06c8dd9 100644
--- a/Makefile
+++ b/Makefile
@@ -264,7 +264,8 @@ LIB_OBJS = \
server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
- alloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)
+ alloc.o merge-file.o path-list.o unpack-trees.o help.o \
+ hash.o $(DIFF_OBJS)
BUILTIN_OBJS = \
builtin-add.o \
@@ -297,6 +298,7 @@ BUILTIN_OBJS = \
builtin-repo-config.o \
builtin-rev-list.o \
builtin-rev-parse.o \
+ builtin-rev-size.o \
builtin-rm.o \
builtin-show-branch.o \
builtin-stripspace.o \
diff --git a/builtin-rev-size.c b/builtin-rev-size.c
new file mode 100644
index 0000000..ad88e48
--- /dev/null
+++ b/builtin-rev-size.c
@@ -0,0 +1,92 @@
+/*
+ * "git rev-size" builtin command
+ *
+ * Copyright (C) 2006 Johannes Schindelin
+ */
+
+#include "cache.h"
+#include "builtin.h"
+#include "object.h"
+#include "tree.h"
+#include "tree-walk.h"
+#include "commit.h"
+#include "diff.h"
+#include "revision.h"
+#include "hash.h"
+
+static const char builtin_rev_size_usage[] =
+"git-rev-size <commit-id>...";
+
+struct rev_size {
+ struct object object;
+ size_t trees, blobs, bytes;
+};
+
+struct hash_map rev_size_hash = { 0, 0, NULL };
+
+static struct rev_size *get_rev_size(const char *sha1)
+{
+ struct rev_size *rev_size =
+ (struct rev_size *)hash_get(&rev_size_hash, sha1);
+
+ if (rev_size == NULL) {
+ char type[64];
+ unsigned long size;
+
+ rev_size = xcalloc(1, sizeof(struct rev_size));
+
+ if (sha1_object_info(sha1, type, &size))
+ die("Cannot get info for %s", sha1_to_hex(sha1));
+
+ if (!strcmp(type, "blob")) {
+ rev_size->blobs = 1;
+ rev_size->bytes = size;
+ } else if (!strcmp(type, "tree")) {
+ struct tree *tree = (struct tree *)parse_object(sha1);
+ struct tree_desc desc;
+ struct name_entry entry;
+
+ desc.buf = tree->buffer;
+ desc.size = tree->size;
+
+ while (tree_entry(&desc, &entry)) {
+ struct rev_size *r = get_rev_size(entry.sha1);
+
+ rev_size->trees += r->trees;
+ rev_size->blobs += r->blobs;
+ rev_size->bytes += r->bytes;
+ }
+
+ rev_size->trees++;
+ } else
+ die("Cannot calculate size for type %s", type);
+
+ memcpy(rev_size->object.sha1, sha1, 20);
+ hash_put(&rev_size_hash, &rev_size->object);
+ }
+
+ return rev_size;
+}
+
+int cmd_rev_size(int argc, const char **argv, const char *prefix)
+{
+ struct rev_info revs;
+ struct commit *commit;
+
+ init_revisions(&revs, prefix);
+ revs.abbrev = 0;
+ revs.commit_format = CMIT_FMT_UNSPECIFIED;
+ argc = setup_revisions(argc, argv, &revs, NULL);
+
+ prepare_revision_walk(&revs);
+
+ while ((commit = get_revision(&revs))) {
+ struct rev_size *rev_size =
+ get_rev_size(commit->tree->object.sha1);
+
+ printf("%s %d %d %d\n", sha1_to_hex(commit->object.sha1),
+ rev_size->trees, rev_size->blobs, rev_size->bytes);
+ }
+
+ return 0;
+}
diff --git a/builtin.h b/builtin.h
index ade58c4..9848a5e 100644
--- a/builtin.h
+++ b/builtin.h
@@ -46,6 +46,7 @@ extern int cmd_read_tree(int argc, const
extern int cmd_repo_config(int argc, const char **argv, const char *prefix);
extern int cmd_rev_list(int argc, const char **argv, const char *prefix);
extern int cmd_rev_parse(int argc, const char **argv, const char *prefix);
+extern int cmd_rev_size(int argc, const char **argv, const char *prefix);
extern int cmd_rm(int argc, const char **argv, const char *prefix);
extern int cmd_show_branch(int argc, const char **argv, const char *prefix);
extern int cmd_show(int argc, const char **argv, const char *prefix);
diff --git a/git.c b/git.c
index bf0fe0e..4cfa6cf 100644
--- a/git.c
+++ b/git.c
@@ -262,6 +262,7 @@ static void handle_internal_command(int
{ "repo-config", cmd_repo_config },
{ "rev-list", cmd_rev_list, RUN_SETUP },
{ "rev-parse", cmd_rev_parse, RUN_SETUP },
+ { "rev-size", cmd_rev_size, RUN_SETUP },
{ "rm", cmd_rm, RUN_SETUP },
{ "show-branch", cmd_show_branch, RUN_SETUP },
{ "show", cmd_show, RUN_SETUP | USE_PAGER },
diff --git a/hash.c b/hash.c
new file mode 100644
index 0000000..12d1e65
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,50 @@
+#include "cache.h"
+#include "object.h"
+#include "hash.h"
+
+static unsigned int hash_index(struct hash_map *hash, const char *sha1)
+{
+ unsigned int index = *(unsigned int *)sha1;
+ while (1) {
+ if (index >= hash->alloc)
+ index = index % hash->alloc;
+ if (hash->map[index] == NULL ||
+ !hashcmp(sha1, hash->map[index]->sha1))
+ return index;
+ index++;
+ }
+}
+
+static void grow_hash(struct hash_map *hash)
+{
+ int i;
+ int old_alloc = hash->alloc;
+ struct object **old_map = hash->map;
+
+ hash->alloc = hash->alloc < 32 ? 32 : 2 * hash->alloc;
+ hash->map = xcalloc(hash->alloc, sizeof(struct object *));
+ hash->nr = 0;
+
+ for (i = 0; i < old_alloc; i++) {
+ struct object *obj = old_map[i];
+ if (!obj)
+ continue;
+ hash_put(hash, obj);
+ }
+ free(old_map);
+}
+
+void hash_put(struct hash_map *hash, struct object *obj)
+{
+ if (++hash->nr > hash->alloc / 2)
+ grow_hash(hash);
+
+ hash->map[hash_index(hash, obj->sha1)] = obj;
+}
+
+struct object *hash_get(struct hash_map *hash, const char *sha1)
+{
+ if (hash->alloc == 0)
+ return NULL;
+ return hash->map[hash_index(hash, sha1)];
+}
diff --git a/hash.h b/hash.h
new file mode 100644
index 0000000..0e2b67c
--- /dev/null
+++ b/hash.h
@@ -0,0 +1,12 @@
+#ifndef HASH_H
+#define HASH_H
+
+struct hash_map {
+ unsigned long nr, alloc;
+ struct object **map;
+};
+
+extern struct object *hash_get(struct hash_map *hash, const char *sha1);
+extern void hash_put(struct hash_map *hash, struct object *obj);
+
+#endif
--
1.4.2.ga5e8f-dirty
^ permalink raw reply related
* Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)
From: Josef Weidendorfer @ 2006-08-20 16:37 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: Rutger Nijlunsing, git
In-Reply-To: <Pine.LNX.4.63.0608201805070.28360@wbgn013.biozentrum.uni-wuerzburg.de>
On Sunday 20 August 2006 18:09, Johannes Schindelin wrote:
Hi,
> Most notably, it adds an object hash map structure to the library.
Aside from the given command of this thread, this is interesting
(even more interesting would be a persistent cache for arbitrary object data).
As this could be used in other contexts, some general comments:
> +static unsigned int hash_index(struct hash_map *hash, const char *sha1)
> +{
> + unsigned int index = *(unsigned int *)sha1;
If you have the same SHA1, stored at different addresses, you get different
indexes for the same SHA1. Index probably should be calculated from the
SHA1 string.
> +void hash_put(struct hash_map *hash, struct object *obj)
> +{
> + if (++hash->nr > hash->alloc / 2)
> + grow_hash(hash);
If you insert the same object multiple times, hash->nr will get too big.
Josef
^ permalink raw reply
* Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)
From: Johannes Schindelin @ 2006-08-20 16:51 UTC (permalink / raw)
To: Josef Weidendorfer; +Cc: Rutger Nijlunsing, git
In-Reply-To: <200608201837.33577.Josef.Weidendorfer@gmx.de>
Hi,
On Sun, 20 Aug 2006, Josef Weidendorfer wrote:
> On Sunday 20 August 2006 18:09, Johannes Schindelin wrote:
>
> > +static unsigned int hash_index(struct hash_map *hash, const char *sha1)
> > +{
> > + unsigned int index = *(unsigned int *)sha1;
>
> If you have the same SHA1, stored at different addresses, you get different
> indexes for the same SHA1. Index probably should be calculated from the
> SHA1 string.
Actually, it does! "*(unsigned int *)sha1" means that the first 4 bytes
of the sha1 are interpreted as a number.
> > +void hash_put(struct hash_map *hash, struct object *obj)
> > +{
> > + if (++hash->nr > hash->alloc / 2)
> > + grow_hash(hash);
>
> If you insert the same object multiple times, hash->nr will get too big.
First, you cannot put the same object multiple times. That is not what a
hash does (at least in this case): it stores unique objects (identified by
their sha1 in this case). If you put another object with the same sha1,
the first will be replaced.
Second, since you call hash_put() once per object, hash->nr cannot grow
too big, because grow_hash() doubles hash->alloc. And I call grow_hash()
once the hash map is half-full; Somebody once told me that would be the
optimal growing strategy.
Ciao,
Dscho
^ permalink raw reply
* Re: [ANNOUNCE] git-rev-size: calculate sizes of repository
From: Rutger Nijlunsing @ 2006-08-20 17:24 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: Rutger Nijlunsing, git
In-Reply-To: <Pine.LNX.4.63.0608201805070.28360@wbgn013.biozentrum.uni-wuerzburg.de>
On Sun, Aug 20, 2006 at 06:09:34PM +0200, Johannes Schindelin wrote:
> Hi,
>
> On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:
>
> > On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:
> > > Hi,
> > >
> > > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:
> > >
> > > > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb
> > >
> > > Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?
> >
> > I _knew_ it... Please go bug someone else. The only thing I did was
> > help someone, and for that I choose my own tools since I do it for
> > fun.
>
> Fair enough.
>
> -- 8< --
> [PATCH] Add git-rev-size
>
> This tool spits out the number of trees, the number of blobs, and the total
> bytes of the blobs for a given rev range.
>
> Most notably, it adds an object hash map structure to the library.
>
> Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
[Hm, the itch seems to be contagious. Better watch out...]
Small comments:
The 'git-rev-size' name was chosen because originally it understood
the same arguments as git-rev-list. You might want to add this popen()
back, or have some other way to share those (might be simple in C). Or
is setup_revisions() enough to have the power of git-rev-list?
If seperate commits have to be given on the command line instead of a
range, the command line limit is hit quite quickly (~780 commits). And
if you'll be using xargs, the hash / cache will be less of an advantage.
The original request was 'for each commit' to get an idea of the size
growth during a project.
'builtin_rev_size_usage' is not referred to in the patch, only defined.
Signed-off-by: Rutger Nijlunsing <git@tux.tmfweb.nl>
> ---
> Makefile | 4 ++
> builtin-rev-size.c | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> builtin.h | 1 +
> git.c | 1 +
> hash.c | 50 ++++++++++++++++++++++++++++
> hash.h | 12 +++++++
> 6 files changed, 159 insertions(+), 1 deletions(-)
[snip patch]
--
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------
^ permalink raw reply
* Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)
From: Rutger Nijlunsing @ 2006-08-20 17:40 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: Josef Weidendorfer, Rutger Nijlunsing, git
In-Reply-To: <Pine.LNX.4.63.0608201846110.28360@wbgn013.biozentrum.uni-wuerzburg.de>
> Second, since you call hash_put() once per object, hash->nr cannot grow
> too big, because grow_hash() doubles hash->alloc. And I call grow_hash()
> once the hash map is half-full; Somebody once told me that would be the
> optimal growing strategy.
Optimal growing mainly means to be O(n) (amortized) after n
inserts. That translates to at least _doubling_ (factor 2 or more) the
capacity once you're too full.
Assume doubling at a percentage full. Assume realloc(s) takes O(s)
(where s = number of bytes). Assume we start with 1 element.
We realloc() then when we've got 1 element, then at 2, 4, 8 etc. The
size of the realloc() at each point will also be 1, 2, 4, 8
etc. However, this cost of O(s) can be amortized over the number of
elements. So the work done _per insert_ is still a constant (amortized
again).
Ascilly:
x x x x x x x x x x ... (each insert)
R R R ... (each realloc)
1 2 0 4 0 0 0 8 0 0 ... (cost of those realloc())
This has also to do with the infinite series of the sum(k>0) of 2^-k
being a constant.
--
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox