git/shallow.c, branch v2.13.2

shallow: avoid memory leak

2017-05-08T03:18:20Z

Reported by Coverity. Signed-off-by: Johannes Schindelin Signed-off-by: Junio C Hamano

Rename sha1_array to oid_array

2017-03-31T15:33:56Z

Since this structure handles an array of object IDs, rename it to struct oid_array. Also rename the accessor functions and the initialization constant. This commit was produced mechanically by providing non-Documentation files to the following Perl one-liners: perl -pi -E 's/struct sha1_array/struct oid_array/g' perl -pi -E 's/\bsha1_array_/oid_array_/g' perl -pi -E 's/SHA1_ARRAY_INIT/OID_ARRAY_INIT/g' Signed-off-by: brian m. carlson Signed-off-by: Junio C Hamano

sha1-array: convert internal storage for struct sha1_array to object_id

2017-03-28T16:59:34Z

Make the internal storage for struct sha1_array use an array of struct object_id internally. Update the users of this struct which inspect its internals. Signed-off-by: brian m. carlson Signed-off-by: Junio C Hamano

Merge branch 'nd/shallow-fixup'

2016-12-21T22:55:02Z

Code cleanup in shallow boundary computation. * nd/shallow-fixup: shallow.c: remove useless code shallow.c: bit manipulation tweaks shallow.c: avoid theoretical pointer wrap-around shallow.c: make paint_alloc slightly more robust shallow.c: stop abusing COMMIT_SLAB_SIZE for paint_info's memory pools shallow.c: rename fields in paint_info to better express their purposes

shallow.c: remove useless code

2016-12-07T23:44:31Z

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: bit manipulation tweaks

2016-12-07T23:44:31Z

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: avoid theoretical pointer wrap-around

2016-12-07T23:44:31Z

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: make paint_alloc slightly more robust

2016-12-07T23:44:31Z

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: stop abusing COMMIT_SLAB_SIZE for paint_info's memory pools

2016-12-07T23:44:31Z

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: rename fields in paint_info to better express their purposes

2016-12-07T23:44:31Z

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