Author: pburba Date: Fri Oct 7 19:00:40 2011 New Revision: 1180154 URL: http://svn.apache.org/viewvc?rev=1180154&view=rev Log: Tweak the svn_rangelist_merge2 API so it allocates new svn_merge_range_t elements only when absolutely necessary.
This addresses a serious inefficiency in memory usage when svn_mergeinfo_catalog_merge, svn_mergeinfo_merge2, or svn_rangelist_merge2 are called in a loop. Prior to this change svn_rangelist_merge2 could potentially reallocate *every* range in both rangelists. For example, the peak working set memory for the reintegrate merge described here http://svn.haxx.se/dev/archive-2011-09/0254.shtml was 1,324,664 KB with trunk@1179545. With this commit that drops to 26,880 KB. * subversion/include/svn_sorts.h (svn_sort__array_delete): New. * subversion/libsvn_subr/sorts.c (svn_sort__array_delete): New, moved here from subversion/libsvn_client/merge.c:remove_element_from_array. * subversion/libsvn_client/merge.c (remove_element_from_array): Remove -- replacing it with svn_sort__array_delete. (remove_absent_children, remove_children_with_deleted_mergeinfo): Replace remove_element_from_array with svn_sort__array_delete. * subversion/libsvn_subr/mergeinfo.c (adjust_remaining_ranges): New. (svn_rangelist_merge2): We are not creating a new rangelist, so modify the output rangelist in-place as much as possible. Previously we used combine_with_lastrange, which happily reallocated most of the ranges in both rangelists. This is fine for the other callers (i.e. svn_rangelist_intersect, svn_rangelist_remove, and svn_mergeinfo__filter_mergeinfo_by_ranges) which are allocating a new output argument, but not for svn_rangelist_merge2 which is *not* allocating a new rangelist. * subversion/tests/libsvn_subr/mergeinfo-test.c (test_rangelist_merge): Add some new test cases to exercise all the code paths in svn_rangelist_merge2 and adjust_remaining_ranges. Modified: subversion/trunk/subversion/include/svn_sorts.h subversion/trunk/subversion/libsvn_client/merge.c subversion/trunk/subversion/libsvn_subr/mergeinfo.c subversion/trunk/subversion/libsvn_subr/sorts.c subversion/trunk/subversion/tests/libsvn_subr/mergeinfo-test.c Modified: subversion/trunk/subversion/include/svn_sorts.h URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/include/svn_sorts.h?rev=1180154&r1=1180153&r2=1180154&view=diff ============================================================================== --- subversion/trunk/subversion/include/svn_sorts.h (original) +++ subversion/trunk/subversion/include/svn_sorts.h Fri Oct 7 19:00:40 2011 @@ -182,6 +182,12 @@ svn_sort__array_insert(const void *new_e int insert_index); +/* Remove the element at DELETE_INDEX from the array ARR. + If DELETE_INDEX is not a valid element of ARR do nothing. */ +void +svn_sort__array_delete(apr_array_header_t *arr, + int delete_index); + #ifdef __cplusplus } #endif /* __cplusplus */ Modified: subversion/trunk/subversion/libsvn_client/merge.c URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_client/merge.c?rev=1180154&r1=1180153&r2=1180154&view=diff ============================================================================== --- subversion/trunk/subversion/libsvn_client/merge.c (original) +++ subversion/trunk/subversion/libsvn_client/merge.c Fri Oct 7 19:00:40 2011 @@ -4770,30 +4770,6 @@ make_merge_conflict_error(const char *ta r->start, r->end, svn_dirent_local_style(target_wcpath, scratch_pool)); } -/* Remove the element at IDX from the array ARR. - If IDX is not a valid element of ARR do nothing. */ -static void -remove_element_from_array(apr_array_header_t *arr, - int idx) -{ - /* Do we have a valid index? */ - if (idx >= 0 && idx < arr->nelts) - { - if (idx == (arr->nelts - 1)) - { - /* Deleting the last or only element in an array is easy. */ - apr_array_pop(arr); - } - else - { - memmove(arr->elts + arr->elt_size * idx, - arr->elts + arr->elt_size * (idx + 1), - arr->elt_size * (arr->nelts - 1 - idx)); - --(arr->nelts); - } - } -} - /* Helper for do_directory_merge(). TARGET_WCPATH is a directory and CHILDREN_WITH_MERGEINFO is filled @@ -4819,7 +4795,7 @@ remove_absent_children(const char *targe if ((child->absent || child->scheduled_for_deletion) && svn_dirent_is_ancestor(target_wcpath, child->abspath)) { - remove_element_from_array(children_with_mergeinfo, i--); + svn_sort__array_delete(children_with_mergeinfo, i--); } } } @@ -4855,8 +4831,7 @@ remove_children_with_deleted_mergeinfo(m child->abspath, APR_HASH_KEY_STRING)) { - remove_element_from_array(notify_b->children_with_mergeinfo, - i--); + svn_sort__array_delete(notify_b->children_with_mergeinfo, i--); } } } Modified: subversion/trunk/subversion/libsvn_subr/mergeinfo.c URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/mergeinfo.c?rev=1180154&r1=1180153&r2=1180154&view=diff ============================================================================== --- subversion/trunk/subversion/libsvn_subr/mergeinfo.c (original) +++ subversion/trunk/subversion/libsvn_subr/mergeinfo.c Fri Oct 7 19:00:40 2011 @@ -742,68 +742,401 @@ svn_mergeinfo_parse(svn_mergeinfo_t *mer return err; } +/* Cleanup after svn_rangelist_merge2 when it modifies the ending range of + a single rangelist element in-place. + + If *INDEX is not a valid element in RANGELIST do nothing. Otherwise ensure + that RANGELIST[*INDEX]->END does not adjoin or overlap any subsequent + ranges in RANGELIST. + + If overlap is found, then remove, modify, and/or add elements to RANGELIST + as per the invariants for rangelists documented in svn_mergeinfo.h. If + RANGELIST[*INDEX]->END adjoins a subsequent element then combine the + elements if their inheritability permits -- The inheritance of intersecting + and adjoining ranges is handled as per svn_mergeinfo_merge2. Upon return + set *INDEX to the index of the youngest element modified, added, or + adjoined to RANGELIST[*INDEX]. + + Note: Adjoining rangelist elements are those where the end rev of the older + element is equal to the start rev of the younger element. + + Any new elements inserted into RANGELIST are allocated in RESULT_POOL.*/ +static void +adjust_remaining_ranges(apr_array_header_t *rangelist, + int *index, + apr_pool_t *result_pool) +{ + int i; + int starting_index; + int elements_to_delete = 0; + svn_merge_range_t *modified_range; + + if (*index >= rangelist->nelts) + return; + + starting_index = *index + 1; + modified_range = APR_ARRAY_IDX(rangelist, *index, svn_merge_range_t *); + + for (i = *index + 1; i < rangelist->nelts; i++) + { + svn_merge_range_t *next_range = APR_ARRAY_IDX(rangelist, i, + svn_merge_range_t *); + + /* If MODIFIED_RANGE doesn't adjoin or overlap the next range in + RANGELIST then we are finished. */ + if (modified_range->end < next_range->start) + break; + + /* Does MODIFIED_RANGE adjoin NEXT_RANGE? */ + if (modified_range->end == next_range->start) + { + if (modified_range->inheritable == next_range->inheritable) + { + /* Combine adjoining ranges with the same inheritability. */ + modified_range->end = next_range->end; + elements_to_delete++; + } + else + { + /* Cannot join because inheritance differs. */ + (*index)++; + } + break; + } + + /* Alright, we know MODIFIED_RANGE overlaps NEXT_RANGE, but how? */ + if (modified_range->end > next_range->end) + { + /* NEXT_RANGE is a proper subset of MODIFIED_RANGE and the two + don't share the same end range. */ + if (modified_range->inheritable + || (modified_range->inheritable == next_range->inheritable)) + { + /* MODIFIED_RANGE absorbs NEXT_RANGE. */ + elements_to_delete++; + } + else + { + /* NEXT_RANGE is a proper subset MODIFIED_RANGE but + MODIFIED_RANGE is non-inheritable and NEXT_RANGE is + inheritable. This means MODIFIED_RANGE is truncated, + NEXT_RANGE remains, and the portion of MODIFIED_RANGE + younger than NEXT_RANGE is added as a separate range: + ______________________________________________ + | | + M MODIFIED_RANGE N + | (!inhertiable) | + |______________________________________________| + | | + O NEXT_RANGE P + | (inheritable)| + |______________| + | + V + _______________________________________________ + | | | | + M MODIFIED_RANGE O NEXT_RANGE P NEW_RANGE N + | (!inhertiable) | (inheritable)| (!inheritable)| + |________________|______________|_______________| + */ + svn_merge_range_t *new_modified_range = + apr_palloc(result_pool, sizeof(*new_modified_range)); + new_modified_range->start = next_range->end; + new_modified_range->end = modified_range->end; + new_modified_range->inheritable = FALSE; + modified_range->end = next_range->start; + (*index)+=2; + svn_sort__array_insert(&new_modified_range, rangelist, *index); + /* Recurse with the new range. */ + adjust_remaining_ranges(rangelist, index, result_pool); + break; + } + } + else if (modified_range->end == next_range->end) + { + /* NEXT_RANGE is a proper subset MODIFIED_RANGE and share + the same end range. */ + if (modified_range->inheritable + || (modified_range->inheritable == next_range->inheritable)) + { + /* MODIFIED_RANGE absorbs NEXT_RANGE. */ + elements_to_delete++; + } + else + { + /* The intersection between MODIFIED_RANGE and NEXT_RANGE is + absorbed by the latter. */ + modified_range->end = next_range->start; + (*index)++; + } + break; + } + else + { + /* NEXT_RANGE and MODIFIED_RANGE intersect but NEXT_RANGE is not + a proper subset of MODIFIED_RANGE, nor do the two share the + same end revision, i.e. they overlap. */ + if (modified_range->inheritable == next_range->inheritable) + { + /* Combine overlapping ranges with the same inheritability. */ + modified_range->end = next_range->end; + elements_to_delete++; + } + else if (modified_range->inheritable) + { + /* MODIFIED_RANGE absorbs the portion of NEXT_RANGE it overlaps + and NEXT_RANGE is truncated. */ + next_range->start = modified_range->end; + (*index)++; + } + else + { + /* NEXT_RANGE absorbs the portion of MODIFIED_RANGE it overlaps + and MODIFIED_RANGE is truncated. */ + modified_range->end = next_range->start; + (*index)++; + } + break; + } + } + + if (elements_to_delete) + for (i = starting_index; i < (elements_to_delete + starting_index); i++) + svn_sort__array_delete(rangelist, starting_index); +} + svn_error_t * svn_rangelist_merge2(apr_array_header_t *rangelist, const apr_array_header_t *changes, apr_pool_t *result_pool, apr_pool_t *scratch_pool) { - int i, j; - apr_array_header_t *original_rangelist; - - original_rangelist = apr_array_copy(scratch_pool, rangelist); - apr_array_clear(rangelist); + int i = 0; + int j = 0; - i = 0; - j = 0; - while (i < (original_rangelist)->nelts && j < changes->nelts) - { - svn_merge_range_t *elt1, *elt2; - int res; + /* We may modify CHANGES, so make a copy in SCRATCH_POOL. */ + changes = svn_rangelist_dup(changes, scratch_pool); - elt1 = APR_ARRAY_IDX(original_rangelist, i, svn_merge_range_t *); - elt2 = APR_ARRAY_IDX(changes, j, svn_merge_range_t *); + while (i < rangelist->nelts && j < changes->nelts) + { + svn_merge_range_t *range = + APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *); + svn_merge_range_t *change = + APR_ARRAY_IDX(changes, j, svn_merge_range_t *); + int res = svn_sort_compare_ranges(&range, &change); - res = svn_sort_compare_ranges(&elt1, &elt2); if (res == 0) { /* Only when merging two non-inheritable ranges is the result also non-inheritable. In all other cases ensure an inheritiable result. */ - if (elt1->inheritable || elt2->inheritable) - elt1->inheritable = TRUE; - SVN_ERR(combine_with_lastrange(elt1, rangelist, TRUE, result_pool)); + if (range->inheritable || change->inheritable) + range->inheritable = TRUE; i++; j++; } - else if (res < 0) + else if (res < 0) /* CHANGE is younger than RANGE */ { - SVN_ERR(combine_with_lastrange(elt1, rangelist, TRUE, result_pool)); - i++; + if (range->end < change->start) + { + /* RANGE is older than CHANGE and the two do not + adjoin or overlap */ + i++; + } + else if (range->end == change->start) + { + /* RANGE and CHANGE adjoin */ + if (range->inheritable == change->inheritable) + { + /* RANGE and CHANGE have the same inheritability so + RANGE expands to absord CHANGE. */ + range->end = change->end; + adjust_remaining_ranges(rangelist, &i, result_pool); + j++; + } + else + { + /* RANGE and CHANGE adjoin, but have different + inheritability. Since RANGE is older, just + move on to the next RANGE. */ + i++; + } + } + else + { + /* RANGE and CHANGE overlap, but how? */ + if ((range->inheritable == change->inheritable) + || range->inheritable) + { + /* If CHANGE is a proper subset of RANGE, it absorbs RANGE + with no adjustment otherwise only the intersection is + absorbed and CHANGE is truncated. */ + if (range->end >= change->end) + j++; + else + change->start = range->end; + } + else + { + /* RANGE is non-inheritable and CHANGE is inheritable. */ + if (range->start < change->start) + { + /* CHANGE absorbs intersection with RANGE and RANGE + is truncated. */ + svn_merge_range_t *range_copy = + svn_merge_range_dup(range, result_pool); + range_copy->end = change->start; + range->start = change->start; + svn_sort__array_insert(&range_copy, rangelist, i++); + } + else + { + /* CHANGE and RANGE share the same start rev, but + RANGE is considered older because its end rev + is older. */ + range->inheritable = TRUE; + change->start = range->end; + } + } + } } - else + else /* res > 0, CHANGE is older than RANGE */ { - SVN_ERR(combine_with_lastrange(elt2, rangelist, TRUE, result_pool)); - j++; + if (change->end < range->start) + { + /* CHANGE is older than RANGE and the two do not + adjoin or overlap, so insert a copy of CHANGE + into RANGELIST. */ + svn_merge_range_t *change_copy = + svn_merge_range_dup(change, result_pool); + svn_sort__array_insert(&change_copy, rangelist, i++); + j++; + } + else if (change->end == range->start) + { + /* RANGE and CHANGE adjoin */ + if (range->inheritable == change->inheritable) + { + /* RANGE and CHANGE have the same inheritability so we + can simply combine the two in place. */ + range->start = change->start; + j++; + } + else + { + /* RANGE and CHANGE have different inheritability so insert + a copy of CHANGE into RANGELIST. */ + svn_merge_range_t *change_copy = + svn_merge_range_dup(change, result_pool); + svn_sort__array_insert(&change_copy, rangelist, i); + j++; + } + } + else + { + /* RANGE and CHANGE overlap. */ + if (range->inheritable == change->inheritable) + { + /* RANGE and CHANGE have the same inheritability so we + can simply combine the two in place... */ + range->start = change->start; + if (range->end < change->end) + { + /* ...but if RANGE is expanded ensure that we don't + violate any rangelist invariants. */ + range->end = change->end; + adjust_remaining_ranges(rangelist, &i, result_pool); + } + j++; + } + else if (range->inheritable) + { + if (change->start < range->start) + { + /* RANGE is inheritable so absorbs any part of CHANGE + it overlaps. CHANGE is truncated and the remainder + inserted into RANGELIST. */ + svn_merge_range_t *change_copy = + svn_merge_range_dup(change, result_pool); + change_copy->end = range->start; + change->start = range->start; + svn_sort__array_insert(&change_copy, rangelist, i++); + } + else + { + /* CHANGE and RANGE share the same start rev, but + CHANGE is considered older because CHANGE->END is + older than RANGE->END. */ + j++; + } + } + else + { + /* RANGE is non-inheritable and CHANGE is inheritable. */ + if (change->start < range->start) + { + if (change->end == range->end) + { + /* RANGE is a proper subset of CHANGE and share the + same end revision, so set RANGE equal to CHANGE. */ + range->start = change->start; + range->inheritable = TRUE; + j++; + } + else if (change->end > range->end) + { + /* RANGE is a proper subset of CHANGE and CHANGE has + a younger end revision, so set RANGE equal to its + intersection with CHANGE and truncate CHANGE. */ + range->start = change->start; + range->inheritable = TRUE; + change->start = range->end; + } + else + { + /* CHANGE and RANGE overlap. Set RANGE equal to its + intersection with CHANGE and take the remainder + of RANGE and insert it into RANGELIST. */ + svn_merge_range_t *range_copy = + svn_merge_range_dup(range, result_pool); + range_copy->start = change->end; + range->start = change->start; + range->end = change->end; + range->inheritable = TRUE; + svn_sort__array_insert(&range_copy, rangelist, ++i); + j++; + } + } + else + { + /* CHANGE and RANGE share the same start rev, but + CHANGE is considered older because its end rev + is older. + + Insert the intersection of RANGE and CHANGE into + RANGELIST and then set RANGE to the non-intersecting + portion of RANGE. */ + svn_merge_range_t *range_copy = + svn_merge_range_dup(range, result_pool); + range_copy->end = change->end; + range_copy->inheritable = TRUE; + range->start = change->end; + svn_sort__array_insert(&range_copy, rangelist, i++); + j++; + } + } + } } } - /* Copy back any remaining elements. - Only one of these loops should end up running, if anything. */ - - SVN_ERR_ASSERT(!(i < (original_rangelist)->nelts && j < changes->nelts)); - - for (; i < (original_rangelist)->nelts; i++) - { - svn_merge_range_t *elt = APR_ARRAY_IDX(original_rangelist, i, - svn_merge_range_t *); - SVN_ERR(combine_with_lastrange(elt, rangelist, TRUE, result_pool)); - } - - for (; j < changes->nelts; j++) + /* Copy any remaining elements in CHANGES into RANGELIST. */ + for (; j < (changes)->nelts; j++) { - svn_merge_range_t *elt = APR_ARRAY_IDX(changes, j, svn_merge_range_t *); - SVN_ERR(combine_with_lastrange(elt, rangelist, TRUE, result_pool)); + svn_merge_range_t *change = + APR_ARRAY_IDX(changes, j, svn_merge_range_t *); + svn_merge_range_t *change_copy = svn_merge_range_dup(change, + result_pool); + svn_sort__array_insert(&change_copy, rangelist, rangelist->nelts); } return SVN_NO_ERROR; Modified: subversion/trunk/subversion/libsvn_subr/sorts.c URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/sorts.c?rev=1180154&r1=1180153&r2=1180154&view=diff ============================================================================== --- subversion/trunk/subversion/libsvn_subr/sorts.c (original) +++ subversion/trunk/subversion/libsvn_subr/sorts.c Fri Oct 7 19:00:40 2011 @@ -245,3 +245,25 @@ svn_sort__array_insert(const void *new_e /* Copy in the new element */ memcpy(new_position, new_element, array->elt_size); } + +void +svn_sort__array_delete(apr_array_header_t *arr, + int delete_index) +{ + /* Do we have a valid index? */ + if (delete_index >= 0 && delete_index < arr->nelts) + { + if (delete_index == (arr->nelts - 1)) + { + /* Deleting the last or only element in an array is easy. */ + apr_array_pop(arr); + } + else + { + memmove(arr->elts + arr->elt_size * delete_index, + arr->elts + arr->elt_size * (delete_index + 1), + arr->elt_size * (arr->nelts - 1 - delete_index)); + --(arr->nelts); + } + } +} Modified: subversion/trunk/subversion/tests/libsvn_subr/mergeinfo-test.c URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/tests/libsvn_subr/mergeinfo-test.c?rev=1180154&r1=1180153&r2=1180154&view=diff ============================================================================== --- subversion/trunk/subversion/tests/libsvn_subr/mergeinfo-test.c (original) +++ subversion/trunk/subversion/tests/libsvn_subr/mergeinfo-test.c Fri Oct 7 19:00:40 2011 @@ -1181,7 +1181,7 @@ test_rangelist_merge(apr_pool_t *pool) svn_merge_range_t expected_merge[6]; }; - #define SIZE_OF_RANGE_MERGE_TEST_ARRAY 59 + #define SIZE_OF_RANGE_MERGE_TEST_ARRAY 67 /* The actual test data. */ struct rangelist_merge_test_data test_data[SIZE_OF_RANGE_MERGE_TEST_ARRAY] = { @@ -1266,6 +1266,26 @@ test_rangelist_merge(apr_pool_t *pool) {"/A: 2-17", "/A: 1-5*,7*,12-13*", 2, {{0, 1, FALSE}, {1, 17, TRUE}}}, + {"/A: 3-4*,10-15,20", "/A: 5-60*", 5, + {{2, 9, FALSE}, {9, 15, TRUE}, {15, 19, FALSE},{19, 20, TRUE}, + {20, 60, FALSE}}}, + + {"/A: 5-60*", "/A: 3-4*,10-15,20", 5, + {{2, 9, FALSE}, {9, 15, TRUE}, {15, 19, FALSE},{19, 20, TRUE}, + {20, 60, FALSE}}}, + + {"/A: 3-4*,50-100*", "/A: 5-60*", 1, {{2, 100, FALSE}}}, + + {"/A: 5-60*", "/A: 3-4*,50-100*", 1, {{2, 100, FALSE}}}, + + {"/A: 3-4*,50-100", "/A: 5-60*", 2, {{2, 49, FALSE}, {49, 100, TRUE}}}, + + {"/A: 5-60*", "/A: 3-4*,50-100", 2, {{2, 49, FALSE}, {49, 100, TRUE}}}, + + {"/A: 3-4,50-100*", "/A: 5-60", 2, {{2, 60, TRUE}, {60, 100, FALSE}}}, + + {"/A: 5-60", "/A: 3-4,50-100*", 2, {{2, 60, TRUE}, {60, 100, FALSE}}}, + /* A rangelist merged with an empty rangelist should equal the non-empty rangelist but in compacted form. */ {"/A: 1-44,45,46,47-50", "", 1, {{ 0, 50, TRUE }}},
