1 /*
2 * from cmocka.c:
3 * These headers or their equivalents should be included prior to
4 * including
5 * this header file.
6 *
7 * #include <stdarg.h>
8 * #include <stddef.h>
9 * #include <setjmp.h>
10 *
11 * This allows test applications to use custom definitions of C standard
12 * library functions and types.
13 */
14 #include <stdarg.h>
15 #include <stddef.h>
16 #include <stdint.h>
17 #include <setjmp.h>
18 #include <cmocka.h>
19
20 #include <errno.h>
21 #include <unistd.h>
22 #include <talloc.h>
23
24 #include <ldb.h>
25 #include <ldb_private.h>
26 #include <string.h>
27 #include <ctype.h>
28
29 struct test_ctx {
30 struct ldb_message *msg;
31 };
32
ldb_msg_setup(void ** state)33 static int ldb_msg_setup(void **state)
34 {
35 struct test_ctx *test_ctx;
36
37 test_ctx = talloc_zero(NULL, struct test_ctx);
38 assert_non_null(test_ctx);
39
40 test_ctx->msg = ldb_msg_new(test_ctx);
41
42 *state = test_ctx;
43 return 0;
44 }
45
ldb_msg_teardown(void ** state)46 static int ldb_msg_teardown(void **state)
47 {
48 struct test_ctx *test_ctx = talloc_get_type_abort(*state,
49 struct test_ctx);
50
51 talloc_free(test_ctx);
52 return 0;
53 }
54
55
add_uint_value(struct test_ctx * test_ctx,struct ldb_message * msg,const char * attr,unsigned int x)56 static void add_uint_value(struct test_ctx *test_ctx,
57 struct ldb_message *msg,
58 const char *attr,
59 unsigned int x)
60 {
61 int ret;
62 struct ldb_val v, v_dup;
63 char s[5];
64 snprintf(s, sizeof(s), "%04x", x);
65 v.data = (uint8_t *)s;
66 v.length = 4;
67 v_dup = ldb_val_dup(test_ctx, &v);
68 assert_non_null(v_dup.data);
69 assert_ptr_not_equal(v_dup.data, v.data);
70 assert_int_equal(v_dup.length, 4);
71
72 ret = ldb_msg_add_value(msg, attr, &v_dup, NULL);
73 assert_int_equal(ret, LDB_SUCCESS);
74 }
75
76
test_ldb_msg_find_duplicate_val(void ** state)77 static void test_ldb_msg_find_duplicate_val(void **state)
78 {
79 int ret;
80 unsigned int i;
81 struct test_ctx *test_ctx = talloc_get_type_abort(*state,
82 struct test_ctx);
83 struct ldb_message *msg = test_ctx->msg;
84 struct ldb_message_element *el;
85 struct ldb_val dummy;
86 struct ldb_val *dupe = &dummy; /* so we can tell it was modified to NULL, not left as NULL */
87
88 ret = ldb_msg_add_empty(msg, "el1", 0, &el);
89 assert_int_equal(ret, LDB_SUCCESS);
90
91 /* An empty message contains no duplicates */
92 ret = ldb_msg_find_duplicate_val(NULL, test_ctx, el, &dupe, 0);
93 assert_int_equal(ret, LDB_SUCCESS);
94 assert_null(dupe);
95
96 for (i = 0; i < 5; i++) {
97 add_uint_value(test_ctx, msg, "el1", i);
98 }
99 /* at this point there are no duplicates, and the check uses the naive
100 quadratic path */
101 ret = ldb_msg_find_duplicate_val(NULL, test_ctx, el, &dupe, 0);
102 assert_int_equal(ret, LDB_SUCCESS);
103 assert_null(dupe);
104
105 /* add a duplicate, still using quadratric path */
106 add_uint_value(test_ctx, msg, "el1", 3);
107 ret = ldb_msg_find_duplicate_val(NULL, test_ctx, el, &dupe, 0);
108 assert_int_equal(ret, LDB_SUCCESS);
109 assert_non_null(dupe);
110 assert_int_equal(dupe->length, 4);
111 assert_memory_equal(dupe->data, "0003", 4);
112
113 /* add some more, triggering algorithmic jump */
114 for (i = 2; i < 11; i++) {
115 add_uint_value(test_ctx, msg, "el1", i);
116 }
117 ret = ldb_msg_find_duplicate_val(NULL, test_ctx, el, &dupe, 0);
118 assert_int_equal(ret, LDB_SUCCESS);
119 assert_non_null(dupe);
120 assert_int_equal(dupe->length, 4);
121 /*XXX not really guaranteed by the API */
122 assert_memory_equal(dupe->data, "0002", 4);
123
124 /* start a new element without duplicates, for the clever algorithm */
125 ldb_msg_add_empty(msg, "el2", 0, &el);
126 for (i = 0; i < 12; i++) {
127 add_uint_value(test_ctx, msg, "el2", i);
128 }
129 ret = ldb_msg_find_duplicate_val(NULL, test_ctx, el, &dupe, 0);
130 assert_int_equal(ret, LDB_SUCCESS);
131 assert_null(dupe);
132 }
133
134
new_msg_element(TALLOC_CTX * mem_ctx,const char * name,unsigned int value_offset,unsigned int num_values)135 static struct ldb_message_element *new_msg_element(TALLOC_CTX *mem_ctx,
136 const char *name,
137 unsigned int value_offset,
138 unsigned int num_values)
139 {
140 unsigned int i, x;
141 struct ldb_message_element *el = talloc_zero(mem_ctx,
142 struct ldb_message_element);
143
144 el->values = talloc_array(el, struct ldb_val, num_values);
145 for (i = 0; i < num_values; i++) {
146 struct ldb_val v;
147 char s[50];
148 v.data = (uint8_t *)s;
149 /* % 3 is to ensure the values list is unsorted */
150 x = i + value_offset;
151 v.length = snprintf(s, sizeof(s), "%u %u", x % 3, x);
152 el->values[i] = ldb_val_dup(mem_ctx, &v);
153 }
154 el->name = name;
155 el->num_values = num_values;
156 return el;
157 }
158
_assert_element_equal(struct ldb_message_element * a,struct ldb_message_element * b,const char * const file,const int line)159 static void _assert_element_equal(struct ldb_message_element *a,
160 struct ldb_message_element *b,
161 const char * const file,
162 const int line)
163 {
164 unsigned int i;
165 _assert_int_equal(a->num_values, b->num_values, file, line);
166 _assert_int_equal(a->flags, b->flags, file, line);
167 _assert_string_equal(a->name, b->name, file, line);
168 for (i = 0; i < a->num_values; i++) {
169 struct ldb_val *v1 = &a->values[i];
170 struct ldb_val *v2 = &b->values[i];
171 _assert_int_equal(v1->length, v2->length, file, line);
172 _assert_memory_equal(v1->data, v2->data, v1->length,
173 file, line);
174 }
175 }
176
177 #define assert_element_equal(a, b) \
178 _assert_element_equal((a), (b), \
179 __FILE__, __LINE__)
180
181
test_ldb_msg_find_common_values(void ** state)182 static void test_ldb_msg_find_common_values(void **state)
183 {
184 /* we only use the state as a talloc context */
185 struct ldb_message_element *el, *el2, *el3, *el4, *el2b, *empty;
186 struct ldb_message_element *orig, *orig2, *orig3, *orig4;
187 int ret;
188 const uint32_t remove_dupes = LDB_MSG_FIND_COMMON_REMOVE_DUPLICATES;
189 el = new_msg_element(*state, "test", 0, 4);
190 el2 = new_msg_element(*state, "test", 4, 4);
191 el3 = new_msg_element(*state, "test", 6, 4);
192 empty = new_msg_element(*state, "test", 0, 0);
193 orig = new_msg_element(*state, "test", 0, 4);
194 orig2 = new_msg_element(*state, "test", 4, 4);
195 orig3 = new_msg_element(*state, "test", 6, 4);
196
197 /* first round is with short value arrays, using quadratic method */
198 /* we expect no collisions here */
199 ret = ldb_msg_find_common_values(NULL, *state, el, el2, 0);
200 assert_int_equal(ret, LDB_SUCCESS);
201
202 /*or here */
203 ret = ldb_msg_find_common_values(NULL, *state, el, el3, 0);
204 assert_int_equal(ret, LDB_SUCCESS);
205
206 /* the same elements in reverse order */
207 ret = ldb_msg_find_common_values(NULL, *state, el2, el, 0);
208 assert_int_equal(ret, LDB_SUCCESS);
209
210 ret = ldb_msg_find_common_values(NULL, *state, el3, el, 0);
211 assert_int_equal(ret, LDB_SUCCESS);
212
213 /* 6, 7 collide */
214 ret = ldb_msg_find_common_values(NULL, *state, el2, el3, 0);
215 assert_int_equal(ret, LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS);
216
217 /* and again */
218 ret = ldb_msg_find_common_values(NULL, *state, el3, el2, 0);
219 assert_int_equal(ret, LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS);
220
221 /* make sure the arrays haven't changed */
222 assert_element_equal(el, orig);
223 assert_element_equal(el2, orig2);
224 assert_element_equal(el3, orig3);
225
226 /* now with the control permisive flag, the first element should be
227 modified to remove the overlap.*/
228
229 /* 6, 7 collide, so el2 will only have 4 and 5 */
230 ret = ldb_msg_find_common_values(NULL, *state, el2, el3, remove_dupes);
231 assert_int_equal(ret, LDB_SUCCESS);
232
233 assert_element_equal(el3, orig3);
234 assert_int_not_equal(el2->num_values, orig2->num_values);
235 assert_int_equal(el2->num_values, 2);
236 el2b = new_msg_element(*state, "test", 4, 2);
237 assert_element_equal(el2, el2b);
238
239 /* now try the same things with a long and a short value list.
240 this should still trigger the quadratic path.
241 */
242 el2 = new_msg_element(*state, "test", 4, 10);
243 orig2 = new_msg_element(*state, "test", 4, 10);
244
245 /* no collisions */
246 ret = ldb_msg_find_common_values(NULL, *state, el, el2, 0);
247 assert_int_equal(ret, LDB_SUCCESS);
248 ret = ldb_msg_find_common_values(NULL, *state, el2, el, 0);
249 assert_int_equal(ret, LDB_SUCCESS);
250
251 /*collisions */
252 ret = ldb_msg_find_common_values(NULL, *state, el3, el2, 0);
253 assert_int_equal(ret, LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS);
254
255 assert_element_equal(el, orig);
256 assert_element_equal(el2, orig2);
257 assert_element_equal(el3, orig3);
258
259 /*collisions with permissive flag*/
260 ret = ldb_msg_find_common_values(NULL, *state, el3, el2, remove_dupes);
261 assert_int_equal(ret, LDB_SUCCESS);
262 assert_element_equal(el2, orig2);
263 assert_int_equal(el3->num_values, 0);
264
265 /* permutations involving empty elements.
266 everything should succeed. */
267 ret = ldb_msg_find_common_values(NULL, *state, el3, el2, 0);
268 assert_int_equal(ret, LDB_SUCCESS);
269 ret = ldb_msg_find_common_values(NULL, *state, el3, el, 0);
270 assert_int_equal(ret, LDB_SUCCESS);
271 ret = ldb_msg_find_common_values(NULL, *state, el2, el3, 0);
272 assert_int_equal(ret, LDB_SUCCESS);
273 assert_int_equal(el2->num_values, orig2->num_values);
274 ret = ldb_msg_find_common_values(NULL, *state, el3, el2, remove_dupes);
275 assert_int_equal(ret, LDB_SUCCESS);
276 assert_int_equal(el2->num_values, orig2->num_values);
277 assert_int_equal(el3->num_values, 0); /* el3 is now empty */
278 ret = ldb_msg_find_common_values(NULL, *state, el2, el3, remove_dupes);
279 assert_int_equal(ret, LDB_SUCCESS);
280 ret = ldb_msg_find_common_values(NULL, *state, el3, empty, 0);
281 assert_int_equal(ret, LDB_SUCCESS);
282 ret = ldb_msg_find_common_values(NULL, *state, empty, empty, 0);
283 assert_int_equal(ret, LDB_SUCCESS);
284 ret = ldb_msg_find_common_values(NULL, *state, empty, el3, 0);
285 assert_int_equal(ret, LDB_SUCCESS);
286
287 assert_element_equal(el2, orig2);
288 assert_element_equal(el, orig);
289 assert_int_equal(el3->num_values, 0);
290
291 /* now with two large value lists */
292 el = new_msg_element(*state, "test", 0, 12);
293 orig = new_msg_element(*state, "test", 0, 12);
294 el4 = new_msg_element(*state, "test", 12, 12);
295 orig4 = new_msg_element(*state, "test", 12, 12);
296
297 /* no collisions */
298 ret = ldb_msg_find_common_values(NULL, *state, el, el4, 0);
299 assert_int_equal(ret, LDB_SUCCESS);
300
301 ret = ldb_msg_find_common_values(NULL, *state, el4, el, 0);
302 assert_int_equal(ret, LDB_SUCCESS);
303
304 /* collisions */
305 ret = ldb_msg_find_common_values(NULL, *state, el4, el2, 0);
306 assert_int_equal(ret, LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS);
307 ret = ldb_msg_find_common_values(NULL, *state, el2, el4, 0);
308 assert_int_equal(ret, LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS);
309 ret = ldb_msg_find_common_values(NULL, *state, el2, el, 0);
310 assert_int_equal(ret, LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS);
311
312 assert_element_equal(el, orig);
313 assert_element_equal(el2, orig2);
314 assert_element_equal(el4, orig4);
315
316 /* with permissive control, but no collisions */
317 ret = ldb_msg_find_common_values(NULL, *state, el, el4, remove_dupes);
318 assert_int_equal(ret, LDB_SUCCESS);
319 ret = ldb_msg_find_common_values(NULL, *state, el4, el, remove_dupes);
320 assert_int_equal(ret, LDB_SUCCESS);
321
322 assert_element_equal(el, orig);
323 assert_element_equal(el4, orig4);
324
325 /* now with collisions, thus modifications.
326 At this stage:
327 el is 0-11 (inclusive)
328 e2 is 4-13
329 el3 is empty
330 el4 is 12-23
331 */
332 ret = ldb_msg_find_common_values(NULL, *state, el4, el2, remove_dupes);
333 assert_int_equal(ret, LDB_SUCCESS);
334 assert_element_equal(el2, orig2);
335 assert_int_not_equal(el4->num_values, orig4->num_values);
336 /* 4 should start at 14 */
337 orig4 = new_msg_element(*state, "test", 14, 10);
338 assert_element_equal(el4, orig4);
339
340 ret = ldb_msg_find_common_values(NULL, *state, el2, el, remove_dupes);
341 assert_int_equal(ret, LDB_SUCCESS);
342 assert_element_equal(el, orig);
343 assert_int_not_equal(el2->num_values, orig2->num_values);
344 orig2 = new_msg_element(*state, "test", 12, 2);
345 assert_element_equal(el2, orig2);
346
347 /* test the empty el against the full elements */
348 ret = ldb_msg_find_common_values(NULL, *state, el, empty, 0);
349 assert_int_equal(ret, LDB_SUCCESS);
350 ret = ldb_msg_find_common_values(NULL, *state, empty, el, 0);
351 assert_int_equal(ret, LDB_SUCCESS);
352 ret = ldb_msg_find_common_values(NULL, *state, el, empty, remove_dupes);
353 assert_int_equal(ret, LDB_SUCCESS);
354 ret = ldb_msg_find_common_values(NULL, *state, empty, el, remove_dupes);
355 assert_int_equal(ret, LDB_SUCCESS);
356 assert_element_equal(el, orig);
357 assert_element_equal(empty, el3);
358
359 /* make sure an identical element with a different name is rejected */
360 el2 = new_msg_element(*state, "fish", 12, 2);
361 ret = ldb_msg_find_common_values(NULL, *state, el2, el, remove_dupes);
362 assert_int_equal(ret, LDB_ERR_INAPPROPRIATE_MATCHING);
363 }
364
365
366
main(int argc,const char ** argv)367 int main(int argc, const char **argv)
368 {
369 const struct CMUnitTest tests[] = {
370 cmocka_unit_test_setup_teardown(test_ldb_msg_find_duplicate_val,
371 ldb_msg_setup,
372 ldb_msg_teardown),
373 cmocka_unit_test_setup_teardown(
374 test_ldb_msg_find_common_values,
375 ldb_msg_setup,
376 ldb_msg_teardown),
377 };
378
379 return cmocka_run_group_tests(tests, NULL, NULL);
380 }
381