Line data Source code
1 : /*
2 : ldb database library
3 :
4 : Copyright (C) Andrew Tridgell 2004
5 :
6 : ** NOTE! The following LGPL license applies to the ldb
7 : ** library. This does NOT imply that all of Samba is released
8 : ** under the LGPL
9 :
10 : This library is free software; you can redistribute it and/or
11 : modify it under the terms of the GNU Lesser General Public
12 : License as published by the Free Software Foundation; either
13 : version 3 of the License, or (at your option) any later version.
14 :
15 : This library is distributed in the hope that it will be useful,
16 : but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 : Lesser General Public License for more details.
19 :
20 : You should have received a copy of the GNU Lesser General Public
21 : License along with this library; if not, see <http://www.gnu.org/licenses/>.
22 : */
23 :
24 : /*
25 : * Name: ldb
26 : *
27 : * Component: ldb pack/unpack
28 : *
29 : * Description: pack/unpack routines for ldb messages as key/value blobs
30 : *
31 : * Author: Andrew Tridgell
32 : */
33 :
34 : #include "ldb_private.h"
35 :
36 : /*
37 : * These macros are from byte_array.h via libssh
38 : * TODO: This will be replaced with use of the byte_array.h header when it
39 : * becomes available.
40 : *
41 : * Macros for handling integer types in byte arrays
42 : *
43 : * This file is originally from the libssh.org project
44 : *
45 : * Copyright (c) 2018 Andreas Schneider <asn@cryptomilk.org>
46 : *
47 : * This library is free software; you can redistribute it and/or
48 : * modify it under the terms of the GNU Lesser General Public
49 : * License as published by the Free Software Foundation; either
50 : * version 2.1 of the License, or (at your option) any later version.
51 : *
52 : * This library is distributed in the hope that it will be useful,
53 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
54 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
55 : * Lesser General Public License for more details.
56 : *
57 : * You should have received a copy of the GNU Lesser General Public
58 : * License along with this library; if not, write to the Free Software
59 : * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
60 : */
61 : #define _DATA_BYTE_CONST(data, pos) \
62 : ((uint8_t)(((const uint8_t *)(data))[(pos)]))
63 : #define PULL_LE_U8(data, pos) \
64 : (_DATA_BYTE_CONST(data, pos))
65 : #define PULL_LE_U16(data, pos) \
66 : ((uint16_t)PULL_LE_U8(data, pos) |\
67 : ((uint16_t)(PULL_LE_U8(data, (pos) + 1))) << 8)
68 : #define PULL_LE_U32(data, pos) \
69 : ((uint32_t)(PULL_LE_U16(data, pos) |\
70 : ((uint32_t)PULL_LE_U16(data, (pos) + 2)) << 16))
71 :
72 : #define _DATA_BYTE(data, pos) \
73 : (((uint8_t *)(data))[(pos)])
74 : #define PUSH_LE_U8(data, pos, val) \
75 : (_DATA_BYTE(data, pos) = ((uint8_t)(val)))
76 : #define PUSH_LE_U16(data, pos, val) \
77 : (PUSH_LE_U8((data), (pos), (uint8_t)((uint16_t)(val) & 0xff)),\
78 : PUSH_LE_U8((data), (pos) + 1,\
79 : (uint8_t)((uint16_t)(val) >> 8)))
80 : #define PUSH_LE_U32(data, pos, val) \
81 : (PUSH_LE_U16((data), (pos), (uint16_t)((uint32_t)(val) & 0xffff)),\
82 : PUSH_LE_U16((data), (pos) + 2, (uint16_t)((uint32_t)(val) >> 16)))
83 :
84 : #define U32_LEN 4
85 : #define U16_LEN 2
86 : #define U8_LEN 1
87 : #define NULL_PAD_BYTE_LEN 1
88 :
89 216263191 : static int attribute_storable_values(const struct ldb_message_element *el)
90 : {
91 235346509 : if (el->num_values == 0) return 0;
92 :
93 235346509 : if (ldb_attr_cmp(el->name, "distinguishedName") == 0) return 0;
94 :
95 216252044 : return el->num_values;
96 : }
97 :
98 6320667 : static int ldb_pack_data_v1(struct ldb_context *ldb,
99 : const struct ldb_message *message,
100 : struct ldb_val *data)
101 : {
102 6320667 : unsigned int i, j, real_elements=0;
103 : size_t size, dn_len, attr_len, value_len;
104 : const char *dn;
105 : uint8_t *p;
106 : size_t len;
107 :
108 6320667 : dn = ldb_dn_get_linearized(message->dn);
109 6320667 : if (dn == NULL) {
110 0 : errno = ENOMEM;
111 0 : return -1;
112 : }
113 :
114 : /* work out how big it needs to be */
115 6320667 : size = U32_LEN * 2 + NULL_PAD_BYTE_LEN;
116 :
117 6320667 : dn_len = strlen(dn);
118 6320667 : if (size + dn_len < size) {
119 0 : errno = ENOMEM;
120 0 : return -1;
121 : }
122 5559190 : size += dn_len;
123 :
124 : /*
125 : * First calcuate the buffer size we need, and check for
126 : * overflows
127 : */
128 35903688 : for (i=0;i<message->num_elements;i++) {
129 30344498 : if (attribute_storable_values(&message->elements[i]) == 0) {
130 3233 : continue;
131 : }
132 :
133 30341265 : real_elements++;
134 :
135 30341265 : if (size + U32_LEN + NULL_PAD_BYTE_LEN < size) {
136 0 : errno = ENOMEM;
137 0 : return -1;
138 : }
139 30341265 : size += U32_LEN + NULL_PAD_BYTE_LEN;
140 :
141 30341265 : attr_len = strlen(message->elements[i].name);
142 30341265 : if (size + attr_len < size) {
143 0 : errno = ENOMEM;
144 0 : return -1;
145 : }
146 26844265 : size += attr_len;
147 :
148 61688687 : for (j=0;j<message->elements[i].num_values;j++) {
149 34844422 : if (size + U32_LEN + NULL_PAD_BYTE_LEN < size) {
150 0 : errno = ENOMEM;
151 0 : return -1;
152 : }
153 34844422 : size += U32_LEN + NULL_PAD_BYTE_LEN;
154 :
155 34844422 : value_len = message->elements[i].values[j].length;
156 34844422 : if (size + value_len < size) {
157 0 : errno = ENOMEM;
158 0 : return -1;
159 : }
160 34844422 : size += value_len;
161 : }
162 : }
163 :
164 : /* allocate it */
165 6320667 : data->data = talloc_array(ldb, uint8_t, size);
166 6320667 : if (!data->data) {
167 0 : errno = ENOMEM;
168 0 : return -1;
169 : }
170 6320667 : data->length = size;
171 :
172 6320667 : p = data->data;
173 6320667 : PUSH_LE_U32(p, 0, LDB_PACKING_FORMAT);
174 6320667 : p += U32_LEN;
175 6320667 : PUSH_LE_U32(p, 0, real_elements);
176 6320667 : p += U32_LEN;
177 :
178 : /* the dn needs to be packed so we can be case preserving
179 : while hashing on a case folded dn */
180 6320667 : len = dn_len;
181 7082144 : memcpy(p, dn, len+NULL_PAD_BYTE_LEN);
182 6320667 : p += len + NULL_PAD_BYTE_LEN;
183 :
184 36665165 : for (i=0;i<message->num_elements;i++) {
185 30344498 : if (attribute_storable_values(&message->elements[i]) == 0) {
186 3233 : continue;
187 : }
188 30341265 : len = strlen(message->elements[i].name);
189 33838265 : memcpy(p, message->elements[i].name, len+NULL_PAD_BYTE_LEN);
190 30341265 : p += len + NULL_PAD_BYTE_LEN;
191 30341265 : PUSH_LE_U32(p, 0, message->elements[i].num_values);
192 30341265 : p += U32_LEN;
193 65185687 : for (j=0;j<message->elements[i].num_values;j++) {
194 34844422 : PUSH_LE_U32(p, 0,
195 : message->elements[i].values[j].length);
196 34844422 : p += U32_LEN;
197 38885010 : memcpy(p, message->elements[i].values[j].data,
198 34844422 : message->elements[i].values[j].length);
199 34844422 : p[message->elements[i].values[j].length] = 0;
200 34844422 : p += message->elements[i].values[j].length +
201 : NULL_PAD_BYTE_LEN;
202 : }
203 : }
204 :
205 5559190 : return 0;
206 : }
207 :
208 : /*
209 : * New pack version designed based on performance profiling of version 1.
210 : * The approach is to separate value data from the rest of the record's data.
211 : * This improves performance because value data is not needed during unpacking
212 : * or filtering of the message's attribute list. During filtering we only copy
213 : * attributes which are present in the attribute list, however at the parse
214 : * stage we need to point to all attributes as they may be referenced in the
215 : * search expression.
216 : * With this new format, we don't lose time loading data (eg via
217 : * talloc_memdup()) that is never needed (for the vast majority of attributes
218 : * are are never found in either the search expression or attribute list).
219 : * Additional changes include adding a canonicalized DN (for later
220 : * optimizations) and variable width length fields for faster unpacking.
221 : * The pack and unpack performance improvement is tested in the torture
222 : * test torture_ldb_pack_format_perf.
223 : *
224 : * Layout:
225 : *
226 : * Version (4 bytes)
227 : * Number of Elements (4 bytes)
228 : * DN length (4 bytes)
229 : * DN with null terminator (DN length + 1 bytes)
230 : * Canonicalized DN length (4 bytes)
231 : * Canonicalized DN with null terminator (Canonicalized DN length + 1 bytes)
232 : * Number of bytes from here to value data section (4 bytes)
233 : * # For each element:
234 : * Element name length (4 bytes)
235 : * Element name with null terminator (Element name length + 1 bytes)
236 : * Number of values (4 bytes)
237 : * Width of value lengths
238 : * # For each value:
239 : * Value data length (#bytes given by width field above)
240 : * # For each element:
241 : * # For each value:
242 : * Value data (#bytes given by corresponding length above)
243 : */
244 12271994 : static int ldb_pack_data_v2(struct ldb_context *ldb,
245 : const struct ldb_message *message,
246 : struct ldb_val *data)
247 : {
248 12271994 : unsigned int i, j, real_elements=0;
249 : size_t size, dn_len, dn_canon_len, attr_len, value_len;
250 : const char *dn, *dn_canon;
251 : uint8_t *p, *q;
252 : size_t len;
253 : size_t max_val_len;
254 : uint8_t val_len_width;
255 :
256 : /*
257 : * First half of this function will calculate required size for
258 : * packed data. Initial size is 20 = 5 * 4. 5 fixed fields are:
259 : * version, num elements, dn len, canon dn len, attr section len
260 : */
261 12271994 : size = U32_LEN * 5;
262 :
263 : /*
264 : * Get linearized and canonicalized form of the DN and add the lengths
265 : * of each to size, plus 1 for null terminator.
266 : */
267 12271994 : dn = ldb_dn_get_linearized(message->dn);
268 12271994 : if (dn == NULL) {
269 0 : errno = ENOMEM;
270 0 : return -1;
271 : }
272 :
273 12271994 : dn_len = strlen(dn) + NULL_PAD_BYTE_LEN;
274 12271994 : if (size + dn_len < size) {
275 0 : errno = ENOMEM;
276 0 : return -1;
277 : }
278 12271994 : size += dn_len;
279 :
280 12271994 : if (ldb_dn_is_special(message->dn)) {
281 9857496 : dn_canon_len = NULL_PAD_BYTE_LEN;
282 9857496 : dn_canon = discard_const_p(char, "\0");
283 : } else {
284 1761708 : dn_canon = ldb_dn_canonical_string(message->dn, message->dn);
285 1761708 : if (dn_canon == NULL) {
286 0 : errno = ENOMEM;
287 0 : return -1;
288 : }
289 :
290 1761708 : dn_canon_len = strlen(dn_canon) + NULL_PAD_BYTE_LEN;
291 1761708 : if (size + dn_canon_len < size) {
292 0 : errno = ENOMEM;
293 0 : return -1;
294 : }
295 : }
296 12271994 : size += dn_canon_len;
297 :
298 : /* Add the size required by each element */
299 70491165 : for (i=0;i<message->num_elements;i++) {
300 58219171 : if (attribute_storable_values(&message->elements[i]) == 0) {
301 1979 : continue;
302 : }
303 :
304 58217192 : real_elements++;
305 :
306 : /*
307 : * Add length of element name + 9 for:
308 : * 1 for null terminator
309 : * 4 for element name length field
310 : * 4 for number of values field
311 : */
312 58217192 : attr_len = strlen(message->elements[i].name);
313 58217192 : if (size + attr_len + U32_LEN * 2 + NULL_PAD_BYTE_LEN < size) {
314 0 : errno = ENOMEM;
315 0 : return -1;
316 : }
317 54187838 : size += attr_len + U32_LEN * 2 + NULL_PAD_BYTE_LEN;
318 :
319 : /*
320 : * Find the max value length, so we can calculate the width
321 : * required for the value length fields.
322 : */
323 54187838 : max_val_len = 0;
324 129508823 : for (j=0;j<message->elements[i].num_values;j++) {
325 75320985 : value_len = message->elements[i].values[j].length;
326 75320985 : if (value_len > max_val_len) {
327 60653030 : max_val_len = value_len;
328 : }
329 :
330 75320985 : if (size + value_len + NULL_PAD_BYTE_LEN < size) {
331 0 : errno = ENOMEM;
332 0 : return -1;
333 : }
334 75320985 : size += value_len + NULL_PAD_BYTE_LEN;
335 : }
336 :
337 58217192 : if (max_val_len <= UCHAR_MAX) {
338 50791082 : val_len_width = U8_LEN;
339 3545293 : } else if (max_val_len <= USHRT_MAX) {
340 3379888 : val_len_width = U16_LEN;
341 16868 : } else if (max_val_len <= UINT_MAX) {
342 16868 : val_len_width = U32_LEN;
343 : } else {
344 0 : errno = EMSGSIZE;
345 0 : return -1;
346 : }
347 :
348 : /* Total size required for val lengths (re-using variable) */
349 58217192 : max_val_len = (val_len_width*message->elements[i].num_values);
350 :
351 : /* Add one for storing the width */
352 58217192 : max_val_len += U8_LEN;
353 58217192 : if (size + max_val_len < size) {
354 0 : errno = ENOMEM;
355 0 : return -1;
356 : }
357 54187838 : size += max_val_len;
358 : }
359 :
360 : /* Allocate */
361 12271994 : data->data = talloc_array(ldb, uint8_t, size);
362 12271994 : if (!data->data) {
363 0 : errno = ENOMEM;
364 0 : return -1;
365 : }
366 12271994 : data->length = size;
367 :
368 : /* Packing format version and number of element */
369 12271994 : p = data->data;
370 12271994 : PUSH_LE_U32(p, 0, LDB_PACKING_FORMAT_V2);
371 12271994 : p += U32_LEN;
372 12271994 : PUSH_LE_U32(p, 0, real_elements);
373 12271994 : p += U32_LEN;
374 :
375 : /* Pack DN and Canonicalized DN */
376 12271994 : PUSH_LE_U32(p, 0, dn_len-NULL_PAD_BYTE_LEN);
377 12271994 : p += U32_LEN;
378 12271994 : memcpy(p, dn, dn_len);
379 12271994 : p += dn_len;
380 :
381 12271994 : PUSH_LE_U32(p, 0, dn_canon_len-NULL_PAD_BYTE_LEN);
382 12271994 : p += U32_LEN;
383 12271994 : memcpy(p, dn_canon, dn_canon_len);
384 12271994 : p += dn_canon_len;
385 :
386 : /*
387 : * Save pointer at this point and leave a U32_LEN gap for
388 : * storing the size of the attribute names and value lengths
389 : * section
390 : */
391 12271994 : q = p;
392 12271994 : p += U32_LEN;
393 :
394 70491165 : for (i=0;i<message->num_elements;i++) {
395 58219171 : if (attribute_storable_values(&message->elements[i]) == 0) {
396 1979 : continue;
397 : }
398 :
399 : /* Length of el name */
400 58217192 : len = strlen(message->elements[i].name);
401 58217192 : PUSH_LE_U32(p, 0, len);
402 58217192 : p += U32_LEN;
403 :
404 : /*
405 : * Even though we have the element name's length, put a null
406 : * terminator at the end so if any code uses the name
407 : * directly, it'll be safe to do things requiring null
408 : * termination like strlen
409 : */
410 62246546 : memcpy(p, message->elements[i].name, len+NULL_PAD_BYTE_LEN);
411 58217192 : p += len + NULL_PAD_BYTE_LEN;
412 : /* Num values */
413 58217192 : PUSH_LE_U32(p, 0, message->elements[i].num_values);
414 58217192 : p += U32_LEN;
415 :
416 : /*
417 : * Calculate value length width again. It's faster to
418 : * calculate it again than do the array management to
419 : * store the result during size calculation.
420 : */
421 58217192 : max_val_len = 0;
422 133538177 : for (j=0;j<message->elements[i].num_values;j++) {
423 75320985 : value_len = message->elements[i].values[j].length;
424 75320985 : if (value_len > max_val_len) {
425 60653030 : max_val_len = value_len;
426 : }
427 : }
428 :
429 58217192 : if (max_val_len <= UCHAR_MAX) {
430 50791082 : val_len_width = U8_LEN;
431 3545293 : } else if (max_val_len <= USHRT_MAX) {
432 3379888 : val_len_width = U16_LEN;
433 16868 : } else if (max_val_len <= UINT_MAX) {
434 16868 : val_len_width = U32_LEN;
435 : } else {
436 0 : errno = EMSGSIZE;
437 0 : return -1;
438 : }
439 :
440 : /* Pack the width */
441 58217192 : *p = val_len_width & 0xFF;
442 58217192 : p += U8_LEN;
443 :
444 : /*
445 : * Pack each value's length using the minimum number of bytes
446 : * required, which we just calculated. We repeat the loop
447 : * for each case here so the compiler can inline code.
448 : */
449 54187838 : if (val_len_width == U8_LEN) {
450 122191279 : for (j=0;j<message->elements[i].num_values;j++) {
451 71400197 : PUSH_LE_U8(p, 0,
452 : message->elements[i].values[j].length);
453 71400197 : p += U8_LEN;
454 : }
455 3545293 : } else if (val_len_width == U16_LEN) {
456 7283808 : for (j=0;j<message->elements[i].num_values;j++) {
457 3903920 : PUSH_LE_U16(p, 0,
458 : message->elements[i].values[j].length);
459 3903920 : p += U16_LEN;
460 : }
461 16868 : } else if (val_len_width == U32_LEN) {
462 33736 : for (j=0;j<message->elements[i].num_values;j++) {
463 16868 : PUSH_LE_U32(p, 0,
464 : message->elements[i].values[j].length);
465 16868 : p += U32_LEN;
466 : }
467 : }
468 : }
469 :
470 : /*
471 : * We've finished packing the attr names and value lengths
472 : * section, so store the size in the U32_LEN gap we left
473 : * earlier
474 : */
475 12271994 : PUSH_LE_U32(q, 0, p-q);
476 :
477 : /* Now pack the values */
478 70491165 : for (i=0;i<message->num_elements;i++) {
479 58219171 : if (attribute_storable_values(&message->elements[i]) == 0) {
480 1979 : continue;
481 : }
482 129508823 : for (j=0;j<message->elements[i].num_values;j++) {
483 90009186 : memcpy(p, message->elements[i].values[j].data,
484 75320985 : message->elements[i].values[j].length);
485 :
486 : /*
487 : * Even though we have the data length, put a null
488 : * terminator at the end of each value's data so if
489 : * any code uses the data directly, it'll be safe to
490 : * do things requiring null termination like strlen.
491 : */
492 75320985 : p[message->elements[i].values[j].length] = 0;
493 75320985 : p += message->elements[i].values[j].length +
494 : NULL_PAD_BYTE_LEN;
495 : }
496 : }
497 :
498 : /*
499 : * If we didn't end up at the end of the data here, something has
500 : * gone very wrong.
501 : */
502 12271994 : if (p != data->data + size) {
503 0 : errno = ENOMEM;
504 0 : return -1;
505 : }
506 :
507 11496016 : return 0;
508 : }
509 :
510 : /*
511 : pack a ldb message into a linear buffer in a ldb_val
512 :
513 : note that this routine avoids saving elements with zero values,
514 : as these are equivalent to having no element
515 :
516 : caller frees the data buffer after use
517 : */
518 18592661 : int ldb_pack_data(struct ldb_context *ldb,
519 : const struct ldb_message *message,
520 : struct ldb_val *data,
521 : uint32_t pack_format_version) {
522 :
523 18592661 : if (pack_format_version == LDB_PACKING_FORMAT) {
524 6320667 : return ldb_pack_data_v1(ldb, message, data);
525 12271994 : } else if (pack_format_version == LDB_PACKING_FORMAT_V2) {
526 12271994 : return ldb_pack_data_v2(ldb, message, data);
527 : } else {
528 0 : errno = EINVAL;
529 0 : return -1;
530 : }
531 : }
532 :
533 : /*
534 : * Unpack a ldb message from a linear buffer in ldb_val
535 : */
536 25249023 : static int ldb_unpack_data_flags_v1(struct ldb_context *ldb,
537 : const struct ldb_val *data,
538 : struct ldb_message *message,
539 : unsigned int flags,
540 : unsigned format)
541 : {
542 : uint8_t *p;
543 : size_t remaining;
544 : size_t dn_len;
545 : unsigned int i, j;
546 25249023 : unsigned int nelem = 0;
547 : size_t len;
548 25249023 : struct ldb_val *ldb_val_single_array = NULL;
549 :
550 25249023 : message->elements = NULL;
551 :
552 25249023 : p = data->data;
553 :
554 : /* Format (U32, already read) + U32 for num_elements */
555 25249023 : if (data->length < U32_LEN * 2) {
556 0 : errno = EIO;
557 0 : goto failed;
558 : }
559 :
560 : /* Skip first 4 bytes, format already read */
561 25249023 : p += U32_LEN;
562 25249023 : message->num_elements = PULL_LE_U32(p, 0);
563 25249023 : p += U32_LEN;
564 :
565 25249023 : remaining = data->length - U32_LEN * 2;
566 :
567 25249023 : switch (format) {
568 0 : case LDB_PACKING_FORMAT_NODN:
569 0 : message->dn = NULL;
570 0 : break;
571 :
572 25249019 : case LDB_PACKING_FORMAT:
573 : /*
574 : * With this check, we know that the DN at p is \0
575 : * terminated.
576 : */
577 25249019 : dn_len = strnlen((char *)p, remaining);
578 25249019 : if (dn_len == remaining) {
579 0 : errno = EIO;
580 0 : goto failed;
581 : }
582 25249019 : if (flags & LDB_UNPACK_DATA_FLAG_NO_DN) {
583 923910 : message->dn = NULL;
584 19759173 : } else {
585 : struct ldb_val blob;
586 24325109 : blob.data = discard_const_p(uint8_t, p);
587 24325109 : blob.length = dn_len;
588 24325109 : message->dn = ldb_dn_from_ldb_val(message, ldb, &blob);
589 24325109 : if (message->dn == NULL) {
590 0 : errno = ENOMEM;
591 0 : goto failed;
592 : }
593 : }
594 : /*
595 : * Redundant: by definition, remaining must be more
596 : * than one less than dn_len, as otherwise it would be
597 : * == dn_len
598 : */
599 25249019 : if (remaining < dn_len + NULL_PAD_BYTE_LEN) {
600 0 : errno = EIO;
601 0 : goto failed;
602 : }
603 25249019 : remaining -= dn_len + NULL_PAD_BYTE_LEN;
604 25249019 : p += dn_len + NULL_PAD_BYTE_LEN;
605 25249019 : break;
606 :
607 4 : default:
608 4 : errno = EIO;
609 4 : goto failed;
610 : }
611 :
612 25249019 : if (flags & LDB_UNPACK_DATA_FLAG_NO_ATTRS) {
613 5239696 : return 0;
614 : }
615 :
616 19945851 : if (message->num_elements == 0) {
617 33 : return 0;
618 : }
619 :
620 19945806 : if (message->num_elements > remaining / 6) {
621 0 : errno = EIO;
622 0 : goto failed;
623 : }
624 :
625 19945806 : message->elements = talloc_zero_array(message, struct ldb_message_element,
626 : message->num_elements);
627 19945806 : if (!message->elements) {
628 0 : errno = ENOMEM;
629 0 : goto failed;
630 : }
631 :
632 : /*
633 : * In typical use, most values are single-valued. This makes
634 : * it quite expensive to allocate an array of ldb_val for each
635 : * of these, just to then hold the pointer to the data buffer
636 : * So with LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC we allocate this
637 : * ahead of time and use it for the single values where possible.
638 : * (This is used the the normal search case, but not in the
639 : * index case because of caller requirements).
640 : */
641 19945806 : if (flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) {
642 9771301 : ldb_val_single_array = talloc_array(message->elements, struct ldb_val,
643 : message->num_elements);
644 9771301 : if (ldb_val_single_array == NULL) {
645 0 : errno = ENOMEM;
646 0 : goto failed;
647 : }
648 : }
649 :
650 218648361 : for (i=0;i<message->num_elements;i++) {
651 198702555 : const char *attr = NULL;
652 : size_t attr_len;
653 198702555 : struct ldb_message_element *element = NULL;
654 :
655 : /*
656 : * Sanity check: Element must be at least the size of empty
657 : * attr name and value and NULL terms for each.
658 : */
659 198702555 : if (remaining < U32_LEN * 2 + NULL_PAD_BYTE_LEN * 2) {
660 0 : errno = EIO;
661 0 : goto failed;
662 : }
663 :
664 : /*
665 : * With this check, we know that the attribute name at
666 : * p is \0 terminated.
667 : */
668 198702555 : attr_len = strnlen((char *)p, remaining-6);
669 198702555 : if (attr_len == remaining-6) {
670 0 : errno = EIO;
671 0 : goto failed;
672 : }
673 198702555 : if (attr_len == 0) {
674 0 : errno = EIO;
675 0 : goto failed;
676 : }
677 198702555 : attr = (char *)p;
678 :
679 198702555 : element = &message->elements[nelem];
680 198702555 : element->name = attr;
681 198702555 : element->flags = 0;
682 :
683 198702555 : if (remaining < (attr_len + NULL_PAD_BYTE_LEN)) {
684 0 : errno = EIO;
685 0 : goto failed;
686 : }
687 198702555 : remaining -= attr_len + NULL_PAD_BYTE_LEN;
688 198702555 : p += attr_len + NULL_PAD_BYTE_LEN;
689 198702555 : element->num_values = PULL_LE_U32(p, 0);
690 198702555 : element->values = NULL;
691 198702555 : if ((flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) && element->num_values == 1) {
692 138751483 : element->values = &ldb_val_single_array[nelem];
693 59951072 : } else if (element->num_values != 0) {
694 59951072 : element->values = talloc_array(message->elements,
695 : struct ldb_val,
696 : element->num_values);
697 59951072 : if (!element->values) {
698 0 : errno = ENOMEM;
699 0 : goto failed;
700 : }
701 : }
702 198702555 : p += U32_LEN;
703 198702555 : if (remaining < U32_LEN) {
704 0 : errno = EIO;
705 0 : goto failed;
706 : }
707 198702555 : remaining -= U32_LEN;
708 437831409 : for (j = 0; j < element->num_values; j++) {
709 : /*
710 : * Sanity check: Value must be at least the size of
711 : * empty val and NULL terminator.
712 : */
713 239128854 : if (remaining < U32_LEN + NULL_PAD_BYTE_LEN) {
714 0 : errno = EIO;
715 0 : goto failed;
716 : }
717 239128854 : remaining -= U32_LEN + NULL_PAD_BYTE_LEN;
718 :
719 239128854 : len = PULL_LE_U32(p, 0);
720 239128854 : if (remaining < len) {
721 0 : errno = EIO;
722 0 : goto failed;
723 : }
724 218813551 : if (len + NULL_PAD_BYTE_LEN < len) {
725 0 : errno = EIO;
726 0 : goto failed;
727 : }
728 :
729 239128854 : element->values[j].length = len;
730 239128854 : element->values[j].data = p + U32_LEN;
731 239128854 : remaining -= len;
732 239128854 : p += len + U32_LEN + NULL_PAD_BYTE_LEN;
733 : }
734 198702555 : nelem++;
735 : }
736 : /*
737 : * Adapt the number of elements to the real number of unpacked elements,
738 : * it means that we overallocated elements array.
739 : */
740 19945806 : message->num_elements = nelem;
741 :
742 : /*
743 : * Shrink the allocated size. On current talloc behaviour
744 : * this will help if we skipped 32 or more attributes.
745 : */
746 19945806 : message->elements = talloc_realloc(message, message->elements,
747 : struct ldb_message_element,
748 : message->num_elements);
749 :
750 19945806 : if (remaining != 0) {
751 0 : ldb_debug(ldb, LDB_DEBUG_ERROR,
752 : "Error: %zu bytes unread in ldb_unpack_data_flags",
753 : remaining);
754 : }
755 :
756 18186110 : return 0;
757 :
758 4 : failed:
759 4 : talloc_free(message->elements);
760 4 : return -1;
761 : }
762 :
763 : /*
764 : * Unpack a ldb message from a linear buffer in ldb_val
765 : */
766 424436850 : static int ldb_unpack_data_flags_v2(struct ldb_context *ldb,
767 : const struct ldb_val *data,
768 : struct ldb_message *message,
769 : unsigned int flags)
770 : {
771 : uint8_t *p, *q, *end_p, *value_section_p;
772 : unsigned int i, j;
773 424436850 : unsigned int nelem = 0;
774 : size_t len;
775 424436850 : struct ldb_val *ldb_val_single_array = NULL;
776 : uint8_t val_len_width;
777 :
778 424436850 : message->elements = NULL;
779 :
780 424436850 : p = data->data;
781 424436850 : end_p = p + data->length;
782 :
783 : /* Skip first 4 bytes, format already read */
784 424436850 : p += U32_LEN;
785 :
786 : /* First fields are fixed: num_elements, DN length */
787 424436850 : if (p + U32_LEN * 2 > end_p) {
788 0 : errno = EIO;
789 0 : goto failed;
790 : }
791 :
792 424436850 : message->num_elements = PULL_LE_U32(p, 0);
793 424436850 : p += U32_LEN;
794 :
795 424436850 : len = PULL_LE_U32(p, 0);
796 424436850 : p += U32_LEN;
797 :
798 424436850 : if (p + len + NULL_PAD_BYTE_LEN > end_p) {
799 3 : errno = EIO;
800 3 : goto failed;
801 : }
802 :
803 424436847 : if (flags & LDB_UNPACK_DATA_FLAG_NO_DN) {
804 91695329 : message->dn = NULL;
805 : } else {
806 : struct ldb_val blob;
807 332741518 : blob.data = discard_const_p(uint8_t, p);
808 332741518 : blob.length = len;
809 332741518 : message->dn = ldb_dn_from_ldb_val(message, ldb, &blob);
810 332741518 : if (message->dn == NULL) {
811 1 : errno = ENOMEM;
812 1 : goto failed;
813 : }
814 : }
815 :
816 424436846 : p += len + NULL_PAD_BYTE_LEN;
817 :
818 424436846 : if (*(p-NULL_PAD_BYTE_LEN) != '\0') {
819 1 : errno = EINVAL;
820 1 : goto failed;
821 : }
822 :
823 : /* Now skip the canonicalized DN and its length */
824 424436845 : len = PULL_LE_U32(p, 0) + NULL_PAD_BYTE_LEN;
825 424436845 : p += U32_LEN;
826 :
827 424436845 : if (p + len > end_p) {
828 3 : errno = EIO;
829 3 : goto failed;
830 : }
831 :
832 424436842 : p += len;
833 :
834 424436842 : if (*(p-NULL_PAD_BYTE_LEN) != '\0') {
835 2 : errno = EINVAL;
836 2 : goto failed;
837 : }
838 :
839 424436840 : if (flags & LDB_UNPACK_DATA_FLAG_NO_ATTRS) {
840 70068169 : return 0;
841 : }
842 :
843 353451928 : if (message->num_elements == 0) {
844 32 : return 0;
845 : }
846 :
847 : /*
848 : * Sanity check (17 bytes is the minimum element size)
849 : */
850 353451896 : if (message->num_elements > (end_p - p) / 17) {
851 4 : errno = EIO;
852 4 : goto failed;
853 : }
854 :
855 353451892 : message->elements = talloc_zero_array(message,
856 : struct ldb_message_element,
857 : message->num_elements);
858 353451892 : if (!message->elements) {
859 0 : errno = ENOMEM;
860 0 : goto failed;
861 : }
862 :
863 : /*
864 : * In typical use, most values are single-valued. This makes
865 : * it quite expensive to allocate an array of ldb_val for each
866 : * of these, just to then hold the pointer to the data buffer.
867 : * So with LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC we allocate this
868 : * ahead of time and use it for the single values where possible.
869 : * (This is used the the normal search case, but not in the
870 : * index case because of caller requirements).
871 : */
872 353451892 : if (flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) {
873 204579938 : ldb_val_single_array = talloc_array(message->elements,
874 : struct ldb_val,
875 : message->num_elements);
876 204579938 : if (ldb_val_single_array == NULL) {
877 0 : errno = ENOMEM;
878 0 : goto failed;
879 : }
880 : }
881 :
882 353451892 : q = p + PULL_LE_U32(p, 0);
883 353451892 : value_section_p = q;
884 353451892 : p += U32_LEN;
885 :
886 5010153369 : for (i=0;i<message->num_elements;i++) {
887 4656701492 : const char *attr = NULL;
888 : size_t attr_len;
889 4656701492 : struct ldb_message_element *element = NULL;
890 :
891 : /* Sanity check: minimum element size */
892 4656701492 : if (p + (U32_LEN * 2) + /* attr name len, num values */
893 4656701492 : (U8_LEN * 2) + /* value length width, one val length */
894 : (NULL_PAD_BYTE_LEN * 2) /* null for attr name + val */
895 : > value_section_p) {
896 0 : errno = EIO;
897 0 : goto failed;
898 : }
899 :
900 4656701492 : attr_len = PULL_LE_U32(p, 0);
901 4656701492 : p += U32_LEN;
902 :
903 4656701492 : if (attr_len == 0) {
904 0 : errno = EIO;
905 0 : goto failed;
906 : }
907 4656701492 : attr = (char *)p;
908 :
909 4656701492 : p += attr_len + NULL_PAD_BYTE_LEN;
910 : /*
911 : * num_values, val_len_width
912 : *
913 : * val_len_width is the width specifier
914 : * for the variable length encoding
915 : */
916 4656701492 : if (p + U32_LEN + U8_LEN > value_section_p) {
917 3 : errno = EIO;
918 3 : goto failed;
919 : }
920 :
921 4656701489 : if (*(p-NULL_PAD_BYTE_LEN) != '\0') {
922 2 : errno = EINVAL;
923 2 : goto failed;
924 : }
925 :
926 4656701487 : element = &message->elements[nelem];
927 4656701487 : element->name = attr;
928 4656701487 : element->flags = 0;
929 :
930 4656701487 : element->num_values = PULL_LE_U32(p, 0);
931 4656701487 : element->values = NULL;
932 7711833018 : if ((flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) &&
933 4241673493 : element->num_values == 1) {
934 4048989998 : element->values = &ldb_val_single_array[nelem];
935 607711489 : } else if (element->num_values != 0) {
936 607711489 : element->values = talloc_array(message->elements,
937 : struct ldb_val,
938 : element->num_values);
939 607711489 : if (!element->values) {
940 1 : errno = ENOMEM;
941 1 : goto failed;
942 : }
943 : }
944 :
945 4656701486 : p += U32_LEN;
946 :
947 : /*
948 : * Here we read how wide the remaining lengths are
949 : * which avoids storing and parsing a lot of leading
950 : * 0s
951 : */
952 4656701486 : val_len_width = *p;
953 4656701486 : p += U8_LEN;
954 :
955 4656701486 : if (p + val_len_width * element->num_values >
956 : value_section_p) {
957 4 : errno = EIO;
958 4 : goto failed;
959 : }
960 :
961 : /*
962 : * This is structured weird for compiler optimization
963 : * purposes, but we need to pull the array of widths
964 : * with different macros depending on how wide the
965 : * biggest one is (specified by val_len_width)
966 : */
967 4656701482 : if (val_len_width == U8_LEN) {
968 9193591650 : for (j = 0; j < element->num_values; j++) {
969 4948682347 : element->values[j].length = PULL_LE_U8(p, 0);
970 4948682347 : p += U8_LEN;
971 : }
972 339249069 : } else if (val_len_width == U16_LEN) {
973 707238668 : for (j = 0; j < element->num_values; j++) {
974 371577733 : element->values[j].length = PULL_LE_U16(p, 0);
975 371577733 : p += U16_LEN;
976 : }
977 40726 : } else if (val_len_width == U32_LEN) {
978 81452 : for (j = 0; j < element->num_values; j++) {
979 40726 : element->values[j].length = PULL_LE_U32(p, 0);
980 40726 : p += U32_LEN;
981 : }
982 : } else {
983 0 : errno = ERANGE;
984 0 : goto failed;
985 : }
986 :
987 9977002283 : for (j = 0; j < element->num_values; j++) {
988 5320300806 : len = element->values[j].length;
989 5320300806 : if (len + NULL_PAD_BYTE_LEN < len) {
990 0 : errno = EIO;
991 0 : goto failed;
992 : }
993 5320300806 : if (q + len + NULL_PAD_BYTE_LEN > end_p) {
994 5 : errno = EIO;
995 5 : goto failed;
996 : }
997 :
998 5320300801 : element->values[j].data = q;
999 5320300801 : q += len + NULL_PAD_BYTE_LEN;
1000 : }
1001 4656701477 : nelem++;
1002 : }
1003 :
1004 : /*
1005 : * If p isn't now pointing at the beginning of the value section,
1006 : * something went very wrong.
1007 : */
1008 353451877 : if (p != value_section_p) {
1009 0 : ldb_debug(ldb, LDB_DEBUG_ERROR,
1010 : "Error: Data corruption in ldb_unpack_data_flags");
1011 0 : errno = EIO;
1012 0 : goto failed;
1013 : }
1014 :
1015 : /*
1016 : * Adapt the number of elements to the real number of unpacked
1017 : * elements it means that we overallocated elements array.
1018 : */
1019 353451877 : message->num_elements = nelem;
1020 :
1021 : /*
1022 : * Shrink the allocated size. On current talloc behaviour
1023 : * this will help if we skipped 32 or more attributes.
1024 : */
1025 353451877 : message->elements = talloc_realloc(message, message->elements,
1026 : struct ldb_message_element,
1027 : message->num_elements);
1028 :
1029 353451877 : if (q != end_p) {
1030 0 : ldb_debug(ldb, LDB_DEBUG_ERROR,
1031 : "Error: %zu bytes unread in ldb_unpack_data_flags",
1032 : end_p - q);
1033 0 : errno = EIO;
1034 0 : goto failed;
1035 : }
1036 :
1037 347466482 : return 0;
1038 :
1039 29 : failed:
1040 29 : talloc_free(message->elements);
1041 29 : return -1;
1042 : }
1043 :
1044 34767583 : int ldb_unpack_get_format(const struct ldb_val *data,
1045 : uint32_t *pack_format_version)
1046 : {
1047 34767583 : if (data->length < U32_LEN) {
1048 0 : return LDB_ERR_OPERATIONS_ERROR;
1049 : }
1050 34767583 : *pack_format_version = PULL_LE_U32(data->data, 0);
1051 34767583 : return LDB_SUCCESS;
1052 : }
1053 :
1054 : /*
1055 : * Unpack a ldb message from a linear buffer in ldb_val
1056 : */
1057 449685873 : int ldb_unpack_data_flags(struct ldb_context *ldb,
1058 : const struct ldb_val *data,
1059 : struct ldb_message *message,
1060 : unsigned int flags)
1061 : {
1062 : unsigned format;
1063 :
1064 449685873 : if (data->length < U32_LEN) {
1065 0 : errno = EIO;
1066 0 : return -1;
1067 : }
1068 :
1069 449685873 : format = PULL_LE_U32(data->data, 0);
1070 449685873 : if (format == LDB_PACKING_FORMAT_V2) {
1071 424436850 : return ldb_unpack_data_flags_v2(ldb, data, message, flags);
1072 : }
1073 :
1074 : /*
1075 : * The v1 function we're about to call takes either LDB_PACKING_FORMAT
1076 : * or LDB_PACKING_FORMAT_NODN packing format versions, and will error
1077 : * if given some other version, so we don't need to do any further
1078 : * checks on 'format'.
1079 : */
1080 25249023 : return ldb_unpack_data_flags_v1(ldb, data, message, flags, format);
1081 : }
1082 :
1083 :
1084 : /*
1085 : * Unpack a ldb message from a linear buffer in ldb_val
1086 : *
1087 : * Free with ldb_unpack_data_free()
1088 : */
1089 7103964 : int ldb_unpack_data(struct ldb_context *ldb,
1090 : const struct ldb_val *data,
1091 : struct ldb_message *message)
1092 : {
1093 7103964 : return ldb_unpack_data_flags(ldb, data, message, 0);
1094 : }
1095 :
1096 : /*
1097 : add the special distinguishedName element
1098 : */
1099 5626733 : static int msg_add_distinguished_name(struct ldb_message *msg)
1100 : {
1101 5626733 : const char *dn_attr = "distinguishedName";
1102 5626733 : char *dn = NULL;
1103 :
1104 5626733 : if (ldb_msg_find_element(msg, dn_attr)) {
1105 : /*
1106 : * This should not happen, but this is
1107 : * existing behaviour...
1108 : */
1109 0 : return LDB_SUCCESS;
1110 : }
1111 :
1112 5626733 : dn = ldb_dn_alloc_linearized(msg, msg->dn);
1113 5626733 : if (dn == NULL) {
1114 0 : return LDB_ERR_OPERATIONS_ERROR;
1115 : }
1116 :
1117 5626733 : return ldb_msg_add_steal_string(msg, dn_attr, dn);
1118 : }
1119 :
1120 : /*
1121 : * filter the specified list of attributes from msg,
1122 : * adding requested attributes, and perhaps all for *,
1123 : * but not the DN to filtered_msg.
1124 : */
1125 130526324 : int ldb_filter_attrs(struct ldb_context *ldb,
1126 : const struct ldb_message *msg,
1127 : const char *const *attrs,
1128 : struct ldb_message *filtered_msg)
1129 : {
1130 : unsigned int i;
1131 130526324 : bool keep_all = false;
1132 130526324 : bool add_dn = false;
1133 : uint32_t num_elements;
1134 : uint32_t elements_size;
1135 :
1136 130526324 : if (attrs) {
1137 : /* check for special attrs */
1138 3704377627 : for (i = 0; attrs[i]; i++) {
1139 3582739420 : int cmp = strcmp(attrs[i], "*");
1140 3582739420 : if (cmp == 0) {
1141 3680824 : keep_all = true;
1142 3680824 : break;
1143 : }
1144 3578901766 : cmp = ldb_attr_cmp(attrs[i], "distinguishedName");
1145 3578901766 : if (cmp == 0) {
1146 678 : add_dn = true;
1147 : }
1148 : }
1149 : } else {
1150 1677068 : keep_all = true;
1151 : }
1152 :
1153 130526324 : if (keep_all) {
1154 5626055 : add_dn = true;
1155 5626055 : elements_size = msg->num_elements + 1;
1156 :
1157 : /* Shortcuts for the simple cases */
1158 124900269 : } else if (add_dn && i == 1) {
1159 193 : if (msg_add_distinguished_name(filtered_msg) != 0) {
1160 0 : goto failed;
1161 : }
1162 173 : return 0;
1163 124900076 : } else if (i == 0) {
1164 10302488 : return 0;
1165 :
1166 : /*
1167 : * Otherwise we are copying at most as many elements as we
1168 : * have attributes
1169 : */
1170 : } else {
1171 111492376 : elements_size = i;
1172 : }
1173 :
1174 120132834 : filtered_msg->elements = talloc_array(filtered_msg,
1175 : struct ldb_message_element,
1176 : elements_size);
1177 120132834 : if (filtered_msg->elements == NULL) goto failed;
1178 :
1179 116850268 : num_elements = 0;
1180 :
1181 2879523567 : for (i = 0; i < msg->num_elements; i++) {
1182 2762673299 : struct ldb_message_element *el = &msg->elements[i];
1183 :
1184 : /*
1185 : * el2 is assigned after the Pigeonhole principle
1186 : * check below for clarity
1187 : */
1188 2762673299 : struct ldb_message_element *el2 = NULL;
1189 : unsigned int j;
1190 :
1191 2762673299 : if (keep_all == false) {
1192 2574178457 : bool found = false;
1193 50137387819 : for (j = 0; attrs[j]; j++) {
1194 48809543102 : int cmp = ldb_attr_cmp(el->name, attrs[j]);
1195 48809543102 : if (cmp == 0) {
1196 1219400609 : found = true;
1197 1219400609 : break;
1198 : }
1199 : }
1200 2639427426 : if (found == false) {
1201 1393093686 : continue;
1202 : }
1203 : }
1204 :
1205 : /*
1206 : * Pigeonhole principle: we can't have more elements
1207 : * than the number of attributes if they are unique in
1208 : * the DB.
1209 : */
1210 1369579613 : if (num_elements >= elements_size) {
1211 0 : goto failed;
1212 : }
1213 :
1214 1369579613 : el2 = &filtered_msg->elements[num_elements];
1215 :
1216 1369579613 : *el2 = *el;
1217 1369579613 : el2->name = talloc_strdup(filtered_msg->elements,
1218 : el->name);
1219 1369579613 : if (el2->name == NULL) {
1220 0 : goto failed;
1221 : }
1222 1369579613 : el2->values = talloc_array(filtered_msg->elements,
1223 : struct ldb_val, el->num_values);
1224 1369579613 : if (el2->values == NULL) {
1225 0 : goto failed;
1226 : }
1227 2910122054 : for (j=0;j<el->num_values;j++) {
1228 1572849689 : el2->values[j] = ldb_val_dup(el2->values, &el->values[j]);
1229 1572849689 : if (el2->values[j].data == NULL && el->values[j].length != 0) {
1230 0 : goto failed;
1231 : }
1232 : }
1233 1369579613 : num_elements++;
1234 : }
1235 :
1236 120132834 : filtered_msg->num_elements = num_elements;
1237 :
1238 120132834 : if (add_dn) {
1239 5626540 : if (msg_add_distinguished_name(filtered_msg) != 0) {
1240 0 : goto failed;
1241 : }
1242 : }
1243 :
1244 120132834 : if (filtered_msg->num_elements > 0) {
1245 : filtered_msg->elements
1246 111203563 : = talloc_realloc(filtered_msg,
1247 : filtered_msg->elements,
1248 : struct ldb_message_element,
1249 : filtered_msg->num_elements);
1250 111203563 : if (filtered_msg->elements == NULL) {
1251 0 : goto failed;
1252 : }
1253 : } else {
1254 8929271 : TALLOC_FREE(filtered_msg->elements);
1255 : }
1256 :
1257 116850268 : return 0;
1258 0 : failed:
1259 0 : TALLOC_FREE(filtered_msg->elements);
1260 0 : return -1;
1261 : }
|