[PATCH] ldb: Fix index out of bound in ldb_msg_find_common_values

[Lukas Slebodnik]

On (06/07/17 16:38), Douglas Bagnall via samba-technical wrote:
>On 06/07/17 10:05, Douglas Bagnall via samba-technical wrote:
>> On 06/07/17 01:33, Lukas Slebodnik wrote:
>>> -	while (i != n_values) {
>>> +	while (i != n_values && j < el2->num_values) {
>>>  		int ret = ldb_val_cmp(&values[i], &values2[j]);
>>>  		if (ret < 0) {
>>>  			i++;
>>>  		} else if (ret > 0) {
>>>  			j++;
>>> -			if (j == el2->num_values) {
>> 
>> The problem was when el2 has no values, right? In which case we really
>> don't want to be here to start with. Which I obviously failed to check
>> and to test.
>> 
>> We also need something like the attached patch. And a test or two, which
>> I'll get onto.
>> 
>
>Well, here I've added tests of zero length elements that exercises this
>path, but they don't usually fail without the fix because out-of-bounds
>reads are like that.
>
>Can we get another reviewer?
>
>cheers,
>Douglas

>From 2fbf68379f0f6e7b917f91a6eb99fa8fd6b31800 Mon Sep 17 00:00:00 2001
>From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>Date: Thu, 6 Jul 2017 10:01:24 +1200
>Subject: [PATCH 2/3] ldb: avoid searching empty lists in
> ldb_msg_find_common_values
>
>Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>---
> lib/ldb/common/ldb_msg.c | 3 +++
> 1 file changed, 3 insertions(+)
>
>diff --git a/lib/ldb/common/ldb_msg.c b/lib/ldb/common/ldb_msg.c
>index 8e4047b..c2782db 100644
>--- a/lib/ldb/common/ldb_msg.c
>+++ b/lib/ldb/common/ldb_msg.c
>@@ -207,6 +207,9 @@ int ldb_msg_find_common_values(struct ldb_context *ldb,
> 	if (strcmp(el->name, el2->name) != 0) {
> 		return LDB_ERR_INAPPROPRIATE_MATCHING;
> 	}
>+	if (el->num_values == 0 || el2->num_values == 0) {
>+		return LDB_SUCCESS;
>+	}
> 	/*
> 	   With few values, it is better to do the brute-force search than the
> 	   clever search involving tallocs, memcpys, sorts, etc.
>-- 
>2.7.4
>

I think it is reasonable performance optimisation :-)

>
>From c1d0ce9f010525e80ecb1dbcbae105da33edc902 Mon Sep 17 00:00:00 2001
>From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>Date: Thu, 6 Jul 2017 12:41:07 +1200
>Subject: [PATCH 3/3] ldb/tests: more thoroughly test empty ldb_msg elements
>
>Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>---
> lib/ldb/tests/ldb_msg.c | 29 ++++++++++++++++++++++++++---
> 1 file changed, 26 insertions(+), 3 deletions(-)
>
>diff --git a/lib/ldb/tests/ldb_msg.c b/lib/ldb/tests/ldb_msg.c
>index e665d55..b3361dc 100644
>--- a/lib/ldb/tests/ldb_msg.c
>+++ b/lib/ldb/tests/ldb_msg.c
>@@ -87,6 +87,11 @@ static void test_ldb_msg_find_duplicate_val(void **state)
> 	ret = ldb_msg_add_empty(msg, "el1", 0, &el);
> 	assert_int_equal(ret, LDB_SUCCESS);
> 
>+	/* An empty message contains no duplicates */
>+	ret = ldb_msg_find_duplicate_val(NULL, test_ctx, el, &dupe, 0);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	assert_null(dupe);
>+
> 	for (i = 0; i < 5; i++) {
> 		add_uint_value(test_ctx, msg, "el1", i);
> 	}
>@@ -176,19 +181,19 @@ static void _assert_element_equal(struct ldb_message_element *a,
> static void test_ldb_msg_find_common_values(void **state)
> {
> 	/* we only use the state as a talloc context */
>-	struct ldb_message_element *el, *el2, *el3, *el4, *el2b;
>+	struct ldb_message_element *el, *el2, *el3, *el4, *el2b, *empty;
> 	struct ldb_message_element *orig, *orig2, *orig3, *orig4;
> 	int ret;
> 	const uint32_t remove_dupes = LDB_MSG_FIND_COMMON_REMOVE_DUPLICATES;
> 	el = new_msg_element(*state, "test", 0, 4);
> 	el2 = new_msg_element(*state, "test", 4, 4);
> 	el3 = new_msg_element(*state, "test", 6, 4);
>+	empty = new_msg_element(*state, "test", 0, 0);
> 	orig = new_msg_element(*state, "test", 0, 4);
> 	orig2 = new_msg_element(*state, "test", 4, 4);
> 	orig3 = new_msg_element(*state, "test", 6, 4);
> 
> 	/* first round is with short value arrays, using quadratic method */
>-
> 	/* we expect no collisions here */
> 	ret = ldb_msg_find_common_values(NULL, *state, el, el2, 0);
> 	assert_int_equal(ret, LDB_SUCCESS);
>@@ -256,7 +261,7 @@ static void test_ldb_msg_find_common_values(void **state)
> 	assert_element_equal(el2, orig2);
> 	assert_int_equal(el3->num_values, 0);
> 
>-	/* seeing as we have an empty element, try permutations therewith.
>+	/* permutations involving empty elements.
> 	   everything should succeed. */
> 	ret = ldb_msg_find_common_values(NULL, *state, el3, el2, 0);
> 	assert_int_equal(ret, LDB_SUCCESS);
>@@ -268,6 +273,12 @@ static void test_ldb_msg_find_common_values(void **state)
> 	assert_int_equal(ret, LDB_SUCCESS);
> 	ret = ldb_msg_find_common_values(NULL, *state, el2, el3, remove_dupes);
> 	assert_int_equal(ret, LDB_SUCCESS);
>+	ret = ldb_msg_find_common_values(NULL, *state, el3, empty, 0);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	ret = ldb_msg_find_common_values(NULL, *state, empty, empty, 0);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	ret = ldb_msg_find_common_values(NULL, *state, empty, el3, 0);
>+	assert_int_equal(ret, LDB_SUCCESS);
> 
> 	assert_element_equal(el2, orig2);
> 	assert_element_equal(el, orig);
>@@ -329,6 +340,18 @@ static void test_ldb_msg_find_common_values(void **state)
> 	orig2 = new_msg_element(*state, "test", 12, 2);
> 	assert_element_equal(el2, orig2);
> 
>+	/* test the empty el against the full elements */
>+	ret = ldb_msg_find_common_values(NULL, *state, el, empty, 0);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	ret = ldb_msg_find_common_values(NULL, *state, empty, el, 0);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	ret = ldb_msg_find_common_values(NULL, *state, el, empty, remove_dupes);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	ret = ldb_msg_find_common_values(NULL, *state, empty, el, remove_dupes);
>+	assert_int_equal(ret, LDB_SUCCESS);
>+	assert_element_equal(el, orig);
>+	assert_element_equal(empty, el3);
>+
> 	/* make sure an identical element with a different name is rejected */
> 	el2 = new_msg_element(*state, "fish", 12, 2);
> 	ret = ldb_msg_find_common_values(NULL, *state, el2, el, remove_dupes);
>-- 
>2.7.4
>

Have you tried to run unit test with valgrind / ore some address/memory
sanitizer?

Otherwise looks good to me. But it would be good to fix also comment from
different mail in this thread about remove_dupes.

Thank you very much for unit tests. They helped us to find bug :-)
I really appreciate it.

LS