From 0afd307ab403404f7cf775fc5042f527e8289980 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Tue, 6 Dec 2016 19:53:34 +0700 Subject: shallow.c: rename fields in paint_info to better express their purposes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit paint_alloc() is basically malloc(), tuned for allocating a fixed number of bits on every call without worrying about freeing any individual allocation since all will be freed at the end. It does it by allocating a big block of memory every time it runs out of "free memory". "slab" is a poor choice of name, at least poorer than "pool". Signed-off-by: Nguyễn Thái Ngọc Duy Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- shallow.c | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'shallow.c') diff --git a/shallow.c b/shallow.c index 4d554caf8..57b5fc7b9 100644 --- a/shallow.c +++ b/shallow.c @@ -356,9 +356,9 @@ define_commit_slab(ref_bitmap, uint32_t *); struct paint_info { struct ref_bitmap ref_bitmap; unsigned nr_bits; - char **slab; + char **pools; char *free, *end; - unsigned slab_count; + unsigned pool_count; }; static uint32_t *paint_alloc(struct paint_info *info) @@ -366,11 +366,11 @@ static uint32_t *paint_alloc(struct paint_info *info) unsigned nr = (info->nr_bits + 31) / 32; unsigned size = nr * sizeof(uint32_t); void *p; - if (!info->slab_count || info->free + size > info->end) { - info->slab_count++; - REALLOC_ARRAY(info->slab, info->slab_count); + if (!info->pool_count || info->free + size > info->end) { + info->pool_count++; + REALLOC_ARRAY(info->pools, info->pool_count); info->free = xmalloc(COMMIT_SLAB_SIZE); - info->slab[info->slab_count - 1] = info->free; + info->pools[info->pool_count - 1] = info->free; info->end = info->free + COMMIT_SLAB_SIZE; } p = info->free; @@ -546,9 +546,9 @@ void assign_shallow_commits_to_refs(struct shallow_info *info, post_assign_shallow(info, &pi.ref_bitmap, ref_status); clear_ref_bitmap(&pi.ref_bitmap); - for (i = 0; i < pi.slab_count; i++) - free(pi.slab[i]); - free(pi.slab); + for (i = 0; i < pi.pool_count; i++) + free(pi.pools[i]); + free(pi.pools); free(shallow); } -- cgit v1.2.1 From 6bc3d8c5ec04cdfaa7dc14aed1993f3bb376d9ae Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Tue, 6 Dec 2016 19:53:35 +0700 Subject: shallow.c: stop abusing COMMIT_SLAB_SIZE for paint_info's memory pools MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit We need to allocate a "big" block of memory in paint_alloc(). The exact size does not really matter. But the pool size has no relation with commit-slab. Stop using that macro here. Signed-off-by: Nguyễn Thái Ngọc Duy Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- shallow.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'shallow.c') diff --git a/shallow.c b/shallow.c index 57b5fc7b9..91aa59d4b 100644 --- a/shallow.c +++ b/shallow.c @@ -353,6 +353,8 @@ void remove_nonexistent_theirs_shallow(struct shallow_info *info) define_commit_slab(ref_bitmap, uint32_t *); +#define POOL_SIZE (512 * 1024) + struct paint_info { struct ref_bitmap ref_bitmap; unsigned nr_bits; @@ -369,9 +371,9 @@ static uint32_t *paint_alloc(struct paint_info *info) if (!info->pool_count || info->free + size > info->end) { info->pool_count++; REALLOC_ARRAY(info->pools, info->pool_count); - info->free = xmalloc(COMMIT_SLAB_SIZE); + info->free = xmalloc(POOL_SIZE); info->pools[info->pool_count - 1] = info->free; - info->end = info->free + COMMIT_SLAB_SIZE; + info->end = info->free + POOL_SIZE; } p = info->free; info->free += size; -- cgit v1.2.1 From f2386c6b77e236fc104d3a024e5d314c23a941eb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Tue, 6 Dec 2016 19:53:36 +0700 Subject: shallow.c: make paint_alloc slightly more robust MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit paint_alloc() allocates a big block of memory and splits it into smaller, fixed size, chunks of memory whenever it's called. Each chunk contains enough bits to present all "new refs" [1] in a fetch from a shallow repository. We do not check if the new "big block" is smaller than the requested memory chunk though. If it happens, we'll happily pass back a memory region smaller than expected. Which will lead to problems eventually. A normal fetch may add/update a dozen new refs. Let's stay on the "reasonably extreme" side and say we need 16k refs (or bits from paint_alloc's perspective). Each chunk of memory would be 2k, much smaller than the memory pool (512k). So, normally, the under-allocation situation should never happen. A bad guy, however, could make a fetch that adds more than 4m new/updated refs to this code which results in a memory chunk larger than pool size. Check this case and abort. Noticed-by: Rasmus Villemoes Reviewed-by: Jeff King [1] Details are in commit message of 58babff (shallow.c: the 8 steps to select new commits for .git/shallow - 2013-12-05), step 6. Signed-off-by: Nguyễn Thái Ngọc Duy Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- shallow.c | 3 +++ 1 file changed, 3 insertions(+) (limited to 'shallow.c') diff --git a/shallow.c b/shallow.c index 91aa59d4b..7d5ea0cd3 100644 --- a/shallow.c +++ b/shallow.c @@ -369,6 +369,9 @@ static uint32_t *paint_alloc(struct paint_info *info) unsigned size = nr * sizeof(uint32_t); void *p; if (!info->pool_count || info->free + size > info->end) { + if (size > POOL_SIZE) + die("BUG: pool size too small for %d in paint_alloc()", + size); info->pool_count++; REALLOC_ARRAY(info->pools, info->pool_count); info->free = xmalloc(POOL_SIZE); -- cgit v1.2.1 From 381aa8e73070646933520e1133a81ab4ba383891 Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Tue, 6 Dec 2016 19:53:37 +0700 Subject: shallow.c: avoid theoretical pointer wrap-around MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The expression info->free+size is technically undefined behaviour in exactly the case we want to test for. Moreover, the compiler is likely to translate the expression to (unsigned long)info->free + size > (unsigned long)info->end where there's at least a theoretical chance that the LHS could wrap around 0, giving a false negative. This might as well be written using pointer subtraction avoiding these issues. Signed-off-by: Rasmus Villemoes Signed-off-by: Nguyễn Thái Ngọc Duy Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- shallow.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'shallow.c') diff --git a/shallow.c b/shallow.c index 7d5ea0cd3..4c4486ad6 100644 --- a/shallow.c +++ b/shallow.c @@ -368,7 +368,7 @@ static uint32_t *paint_alloc(struct paint_info *info) unsigned nr = (info->nr_bits + 31) / 32; unsigned size = nr * sizeof(uint32_t); void *p; - if (!info->pool_count || info->free + size > info->end) { + if (!info->pool_count || size > info->end - info->free) { if (size > POOL_SIZE) die("BUG: pool size too small for %d in paint_alloc()", size); -- cgit v1.2.1 From 1127b3ced55b97229c55ff0c7585b284e3551a9e Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Tue, 6 Dec 2016 19:53:38 +0700 Subject: shallow.c: bit manipulation tweaks MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit First of all, 1 << 31 is technically undefined behaviour, so let's just use an unsigned literal. If i is 'signed int' and gcc doesn't know that i is positive, gcc generates code to compute the C99-mandated values of "i / 32" and "i % 32", which is a lot more complicated than simple a simple shifts/mask. The only caller of paint_down actually passes an "unsigned int" value, but the prototype of paint_down causes (completely well-defined) conversion to signed int, and gcc has no way of knowing that the converted value is non-negative. Just make the id parameter unsigned. In update_refstatus, the change in generated code is much smaller, presumably because gcc is smart enough to see that i starts as 0 and is only incremented, so it is allowed (per the UD of signed overflow) to assume that i is always non-negative. But let's just help less smart compilers generate good code anyway. Signed-off-by: Rasmus Villemoes Signed-off-by: Nguyễn Thái Ngọc Duy Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- shallow.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'shallow.c') diff --git a/shallow.c b/shallow.c index 4c4486ad6..2bf25552f 100644 --- a/shallow.c +++ b/shallow.c @@ -389,7 +389,7 @@ static uint32_t *paint_alloc(struct paint_info *info) * all walked commits. */ static void paint_down(struct paint_info *info, const unsigned char *sha1, - int id) + unsigned int id) { unsigned int i, nr; struct commit_list *head = NULL; @@ -401,7 +401,7 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1, if (!c) return; memset(bitmap, 0, bitmap_size); - bitmap[id / 32] |= (1 << (id % 32)); + bitmap[id / 32] |= (1U << (id % 32)); commit_list_insert(c, &head); while (head) { struct commit_list *p; @@ -575,11 +575,11 @@ static int add_ref(const char *refname, const struct object_id *oid, static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap) { - int i; + unsigned int i; if (!ref_status) return; for (i = 0; i < nr; i++) - if (bitmap[i / 32] & (1 << (i % 32))) + if (bitmap[i / 32] & (1U << (i % 32))) ref_status[i]++; } -- cgit v1.2.1 From 649b0c316a65466f43ea748abf468202467fd516 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Tue, 6 Dec 2016 19:53:39 +0700 Subject: shallow.c: remove useless code MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Some context before we talk about the removed code. This paint_down() is part of step 6 of 58babff (shallow.c: the 8 steps to select new commits for .git/shallow - 2013-12-05). When we fetch from a shallow repository, we need to know if one of the new/updated refs needs new "shallow commits" in .git/shallow (because we don't have enough history of those refs) and which one. The question at step 6 is, what (new) shallow commits are required in other to maintain reachability throughout the repository _without_ cutting our history short? To answer, we mark all commits reachable from existing refs with UNINTERESTING ("rev-list --not --all"), mark shallow commits with BOTTOM, then for each new/updated refs, walk through the commit graph until we either hit UNINTERESTING or BOTTOM, marking the ref on the commit as we walk. After all the walking is done, we check the new shallow commits. If we have not seen any new ref marked on a new shallow commit, we know all new/updated refs are reachable using just our history and .git/shallow. The shallow commit in question is not needed and can be thrown away. So, the code. The loop here (to walk through commits) is basically 1. get one commit from the queue 2. ignore if it's SEEN or UNINTERESTING 3. mark it 4. go through all the parents and.. 5a. mark it if it's never marked before 5b. put it back in the queue What we do in this patch is drop step 5a because it is not necessary. The commit being marked at 5a is put back on the queue, and will be marked at step 3 at the next iteration. The only case it will not be marked is when the commit is already marked UNINTERESTING (5a does not check this), which will be ignored at step 2. But we don't care about refs marking on UNINTERESTING. We care about the marking on _shallow commits_ that are not reachable from our current history (and having UNINTERESTING on it means it's reachable). So it's ok for an UNINTERESTING not to be ref-marked. Reported-by: Rasmus Villemoes Signed-off-by: Nguyễn Thái Ngọc Duy Signed-off-by: Junio C Hamano --- shallow.c | 4 ---- 1 file changed, 4 deletions(-) (limited to 'shallow.c') diff --git a/shallow.c b/shallow.c index 2bf25552f..37622523d 100644 --- a/shallow.c +++ b/shallow.c @@ -434,12 +434,8 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1, oid_to_hex(&c->object.oid)); for (p = c->parents; p; p = p->next) { - uint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap, - p->item); if (p->item->object.flags & SEEN) continue; - if (*p_refs == NULL || *p_refs == *refs) - *p_refs = *refs; commit_list_insert(p->item, &head); } } -- cgit v1.2.1