ldb:utf8: ldb_ascii_toupper() avoids real toupper()

[Samba.git] / lib / ldb / common / ldb_pack.c

/*
   ldb database library

   Copyright (C) Andrew Tridgell  2004

     ** NOTE! The following LGPL license applies to the ldb
     ** library. This does NOT imply that all of Samba is released
     ** under the LGPL

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 3 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, see <http://www.gnu.org/licenses/>.
*/

/*
 *  Name: ldb
 *
 *  Component: ldb pack/unpack
 *
 *  Description: pack/unpack routines for ldb messages as key/value blobs
 *
 *  Author: Andrew Tridgell
 */

#include "ldb_private.h"

/*
 * These macros are from byte_array.h via libssh
 * TODO: This will be replaced with use of the byte_array.h header when it
 * becomes available.
 *
 * Macros for handling integer types in byte arrays
 *
 * This file is originally from the libssh.org project
 *
 * Copyright (c) 2018 Andreas Schneider <asn@cryptomilk.org>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */
#define _DATA_BYTE_CONST(data, pos) \
        ((uint8_t)(((const uint8_t *)(data))[(pos)]))
#define PULL_LE_U8(data, pos) \
        (_DATA_BYTE_CONST(data, pos))
#define PULL_LE_U16(data, pos) \
        ((uint16_t)PULL_LE_U8(data, pos) |\
        ((uint16_t)(PULL_LE_U8(data, (pos) + 1))) << 8)
#define PULL_LE_U32(data, pos) \
        ((uint32_t)(PULL_LE_U16(data, pos) |\
        ((uint32_t)PULL_LE_U16(data, (pos) + 2)) << 16))

#define _DATA_BYTE(data, pos) \
        (((uint8_t *)(data))[(pos)])
#define PUSH_LE_U8(data, pos, val) \
        (_DATA_BYTE(data, pos) = ((uint8_t)(val)))
#define PUSH_LE_U16(data, pos, val) \
        (PUSH_LE_U8((data), (pos), (uint8_t)((uint16_t)(val) & 0xff)),\
                    PUSH_LE_U8((data), (pos) + 1,\
                               (uint8_t)((uint16_t)(val) >> 8)))
#define PUSH_LE_U32(data, pos, val) \
        (PUSH_LE_U16((data), (pos), (uint16_t)((uint32_t)(val) & 0xffff)),\
         PUSH_LE_U16((data), (pos) + 2, (uint16_t)((uint32_t)(val) >> 16)))

#define U32_LEN 4
#define U16_LEN 2
#define U8_LEN 1
#define NULL_PAD_BYTE_LEN 1

static int attribute_storable_values(const struct ldb_message_element *el)
{
        if (el->num_values == 0) return 0;

        if (ldb_attr_cmp(el->name, "distinguishedName") == 0) return 0;

        return el->num_values;
}

static int ldb_pack_data_v1(struct ldb_context *ldb,
                            const struct ldb_message *message,
                            struct ldb_val *data)
{
        unsigned int i, j, real_elements=0;
        size_t size, dn_len, attr_len, value_len;
        const char *dn;
        uint8_t *p;
        size_t len;

        dn = ldb_dn_get_linearized(message->dn);
        if (dn == NULL) {
                errno = ENOMEM;
                return -1;
        }

        /* work out how big it needs to be */
        size = U32_LEN * 2 + NULL_PAD_BYTE_LEN;

        dn_len = strlen(dn);
        if (size + dn_len < size) {
                errno = ENOMEM;
                return -1;
        }
        size += dn_len;

        /*
         * First calculate the buffer size we need, and check for
         * overflows
         */
        for (i=0;i<message->num_elements;i++) {
                if (attribute_storable_values(&message->elements[i]) == 0) {
                        continue;
                }

                real_elements++;

                if (size + U32_LEN + NULL_PAD_BYTE_LEN < size) {
                        errno = ENOMEM;
                        return -1;
                }
                size += U32_LEN + NULL_PAD_BYTE_LEN;

                attr_len = strlen(message->elements[i].name);
                if (size + attr_len < size) {
                        errno = ENOMEM;
                        return -1;
                }
                size += attr_len;

                for (j=0;j<message->elements[i].num_values;j++) {
                        if (size + U32_LEN + NULL_PAD_BYTE_LEN < size) {
                                errno = ENOMEM;
                                return -1;
                        }
                        size += U32_LEN + NULL_PAD_BYTE_LEN;

                        value_len = message->elements[i].values[j].length;
                        if (size + value_len < size) {
                                errno = ENOMEM;
                                return -1;
                        }
                        size += value_len;
                }
        }

        /* allocate it */
        data->data = talloc_array(ldb, uint8_t, size);
        if (!data->data) {
                errno = ENOMEM;
                return -1;
        }
        data->length = size;

        p = data->data;
        PUSH_LE_U32(p, 0, LDB_PACKING_FORMAT);
        p += U32_LEN;
        PUSH_LE_U32(p, 0, real_elements);
        p += U32_LEN;

        /* the dn needs to be packed so we can be case preserving
           while hashing on a case folded dn */
        len = dn_len;
        memcpy(p, dn, len+NULL_PAD_BYTE_LEN);
        p += len + NULL_PAD_BYTE_LEN;

        for (i=0;i<message->num_elements;i++) {
                if (attribute_storable_values(&message->elements[i]) == 0) {
                        continue;
                }
                len = strlen(message->elements[i].name);
                memcpy(p, message->elements[i].name, len+NULL_PAD_BYTE_LEN);
                p += len + NULL_PAD_BYTE_LEN;
                PUSH_LE_U32(p, 0, message->elements[i].num_values);
                p += U32_LEN;
                for (j=0;j<message->elements[i].num_values;j++) {
                        PUSH_LE_U32(p, 0,
                                    message->elements[i].values[j].length);
                        p += U32_LEN;
                        memcpy(p, message->elements[i].values[j].data,
                               message->elements[i].values[j].length);
                        p[message->elements[i].values[j].length] = 0;
                        p += message->elements[i].values[j].length +
                                NULL_PAD_BYTE_LEN;
                }
        }

        return 0;
}

/*
 * New pack version designed based on performance profiling of version 1.
 * The approach is to separate value data from the rest of the record's data.
 * This improves performance because value data is not needed during unpacking
 * or filtering of the message's attribute list. During filtering we only copy
 * attributes which are present in the attribute list, however at the parse
 * stage we need to point to all attributes as they may be referenced in the
 * search expression.
 * With this new format, we don't lose time loading data (eg via
 * talloc_memdup()) that is never needed (for the vast majority of attributes
 * are are never found in either the search expression or attribute list).
 * Additional changes include adding a canonicalized DN (for later
 * optimizations) and variable width length fields for faster unpacking.
 * The pack and unpack performance improvement is tested in the torture
 * test torture_ldb_pack_format_perf.
 *
 * Layout:
 *
 * Version (4 bytes)
 * Number of Elements (4 bytes)
 * DN length (4 bytes)
 * DN with null terminator (DN length + 1 bytes)
 * Canonicalized DN length (4 bytes)
 * Canonicalized DN with null terminator (Canonicalized DN length + 1 bytes)
 * Number of bytes from here to value data section (4 bytes)
 * # For each element:
 *      Element name length (4 bytes)
 *      Element name with null terminator (Element name length + 1 bytes)
 *      Number of values (4 bytes)
 *      Width of value lengths
 *      # For each value:
 *              Value data length (#bytes given by width field above)
 * # For each element:
 *      # For each value:
 *              Value data (#bytes given by corresponding length above)
 */
static int ldb_pack_data_v2(struct ldb_context *ldb,
                            const struct ldb_message *message,
                            struct ldb_val *data)
{
        unsigned int i, j, real_elements=0;
        size_t size, dn_len, dn_canon_len, attr_len, value_len;
        const char *dn, *dn_canon;
        uint8_t *p, *q;
        size_t len;
        size_t max_val_len;
        uint8_t val_len_width;

        /*
         * First half of this function will calculate required size for
         * packed data. Initial size is 20 = 5 * 4.  5 fixed fields are:
         * version, num elements, dn len, canon dn len, attr section len
         */
        size = U32_LEN * 5;

        /*
         * Get linearized and canonicalized form of the DN and add the lengths
         * of each to size, plus 1 for null terminator.
         */
        dn = ldb_dn_get_linearized(message->dn);
        if (dn == NULL) {
                errno = ENOMEM;
                return -1;
        }

        dn_len = strlen(dn) + NULL_PAD_BYTE_LEN;
        if (size + dn_len < size) {
                errno = ENOMEM;
                return -1;
        }
        size += dn_len;

        if (ldb_dn_is_special(message->dn)) {
                dn_canon_len = NULL_PAD_BYTE_LEN;
                dn_canon = discard_const_p(char, "\0");
        } else {
                dn_canon = ldb_dn_canonical_string(message->dn, message->dn);
                if (dn_canon == NULL) {
                        errno = ENOMEM;
                        return -1;
                }

                dn_canon_len = strlen(dn_canon) + NULL_PAD_BYTE_LEN;
                if (size + dn_canon_len < size) {
                        errno = ENOMEM;
                        return -1;
                }
        }
        size += dn_canon_len;

        /* Add the size required by each element */
        for (i=0;i<message->num_elements;i++) {
                if (attribute_storable_values(&message->elements[i]) == 0) {
                        continue;
                }

                real_elements++;

                /*
                 * Add length of element name + 9 for:
                 * 1 for null terminator
                 * 4 for element name length field
                 * 4 for number of values field
                 */
                attr_len = strlen(message->elements[i].name);
                if (size + attr_len + U32_LEN * 2 + NULL_PAD_BYTE_LEN < size) {
                        errno = ENOMEM;
                        return -1;
                }
                size += attr_len + U32_LEN * 2 + NULL_PAD_BYTE_LEN;

                /*
                 * Find the max value length, so we can calculate the width
                 * required for the value length fields.
                 */
                max_val_len = 0;
                for (j=0;j<message->elements[i].num_values;j++) {
                        value_len = message->elements[i].values[j].length;
                        if (value_len > max_val_len) {
                                max_val_len = value_len;
                        }

                        if (size + value_len + NULL_PAD_BYTE_LEN < size) {
                                errno = ENOMEM;
                                return -1;
                        }
                        size += value_len + NULL_PAD_BYTE_LEN;
                }

                if (max_val_len <= UCHAR_MAX) {
                        val_len_width = U8_LEN;
                } else if (max_val_len <= USHRT_MAX) {
                        val_len_width = U16_LEN;
                } else if (max_val_len <= UINT_MAX) {
                        val_len_width = U32_LEN;
                } else {
                        errno = EMSGSIZE;
                        return -1;
                }

                /* Total size required for val lengths (re-using variable) */
                max_val_len = (val_len_width*message->elements[i].num_values);

                /* Add one for storing the width */
                max_val_len += U8_LEN;
                if (size + max_val_len < size) {
                        errno = ENOMEM;
                        return -1;
                }
                size += max_val_len;
        }

        /* Allocate */
        data->data = talloc_array(ldb, uint8_t, size);
        if (!data->data) {
                errno = ENOMEM;
                return -1;
        }
        data->length = size;

        /* Packing format version and number of element */
        p = data->data;
        PUSH_LE_U32(p, 0, LDB_PACKING_FORMAT_V2);
        p += U32_LEN;
        PUSH_LE_U32(p, 0, real_elements);
        p += U32_LEN;

        /* Pack DN and Canonicalized DN */
        PUSH_LE_U32(p, 0, dn_len-NULL_PAD_BYTE_LEN);
        p += U32_LEN;
        memcpy(p, dn, dn_len);
        p += dn_len;

        PUSH_LE_U32(p, 0, dn_canon_len-NULL_PAD_BYTE_LEN);
        p += U32_LEN;
        memcpy(p, dn_canon, dn_canon_len);
        p += dn_canon_len;

        /*
         * Save pointer at this point and leave a U32_LEN gap for
         * storing the size of the attribute names and value lengths
         * section
         */
        q = p;
        p += U32_LEN;

        for (i=0;i<message->num_elements;i++) {
                if (attribute_storable_values(&message->elements[i]) == 0) {
                        continue;
                }

                /* Length of el name */
                len = strlen(message->elements[i].name);
                PUSH_LE_U32(p, 0, len);
                p += U32_LEN;

                /*
                 * Even though we have the element name's length, put a null
                 * terminator at the end so if any code uses the name
                 * directly, it'll be safe to do things requiring null
                 * termination like strlen
                 */
                memcpy(p, message->elements[i].name, len+NULL_PAD_BYTE_LEN);
                p += len + NULL_PAD_BYTE_LEN;
                /* Num values */
                PUSH_LE_U32(p, 0, message->elements[i].num_values);
                p += U32_LEN;

                /*
                 * Calculate value length width again. It's faster to
                 * calculate it again than do the array management to
                 * store the result during size calculation.
                 */
                max_val_len = 0;
                for (j=0;j<message->elements[i].num_values;j++) {
                        value_len = message->elements[i].values[j].length;
                        if (value_len > max_val_len) {
                                max_val_len = value_len;
                        }
                }

                if (max_val_len <= UCHAR_MAX) {
                        val_len_width = U8_LEN;
                } else if (max_val_len <= USHRT_MAX) {
                        val_len_width = U16_LEN;
                } else if (max_val_len <= UINT_MAX) {
                        val_len_width = U32_LEN;
                } else {
                        errno = EMSGSIZE;
                        return -1;
                }

                /* Pack the width */
                *p = val_len_width & 0xFF;
                p += U8_LEN;

                /*
                 * Pack each value's length using the minimum number of bytes
                 * required, which we just calculated. We repeat the loop
                 * for each case here so the compiler can inline code.
                 */
                if (val_len_width == U8_LEN) {
                        for (j=0;j<message->elements[i].num_values;j++) {
                                PUSH_LE_U8(p, 0,
                                        message->elements[i].values[j].length);
                                p += U8_LEN;
                        }
                } else if (val_len_width == U16_LEN) {
                        for (j=0;j<message->elements[i].num_values;j++) {
                                PUSH_LE_U16(p, 0,
                                        message->elements[i].values[j].length);
                                p += U16_LEN;
                        }
                } else if (val_len_width == U32_LEN) {
                        for (j=0;j<message->elements[i].num_values;j++) {
                                PUSH_LE_U32(p, 0,
                                        message->elements[i].values[j].length);
                                p += U32_LEN;
                        }
                }
        }

        /*
         * We've finished packing the attr names and value lengths
         * section, so store the size in the U32_LEN gap we left
         * earlier
         */
        PUSH_LE_U32(q, 0, p-q);

        /* Now pack the values */
        for (i=0;i<message->num_elements;i++) {
                if (attribute_storable_values(&message->elements[i]) == 0) {
                        continue;
                }
                for (j=0;j<message->elements[i].num_values;j++) {
                        memcpy(p, message->elements[i].values[j].data,
                               message->elements[i].values[j].length);

                        /*
                         * Even though we have the data length, put a null
                         * terminator at the end of each value's data so if
                         * any code uses the data directly, it'll  be safe to
                         * do things requiring null termination like strlen.
                         */
                        p[message->elements[i].values[j].length] = 0;
                        p += message->elements[i].values[j].length +
                                NULL_PAD_BYTE_LEN;
                }
        }

        /*
         * If we didn't end up at the end of the data here, something has
         * gone very wrong.
         */
        if (p != data->data + size) {
                errno = ENOMEM;
                return -1;
        }

        return 0;
}

/*
  pack a ldb message into a linear buffer in a ldb_val

  note that this routine avoids saving elements with zero values,
  as these are equivalent to having no element

  caller frees the data buffer after use
*/
int ldb_pack_data(struct ldb_context *ldb,
                  const struct ldb_message *message,
                  struct ldb_val *data,
                  uint32_t pack_format_version) {

        if (pack_format_version == LDB_PACKING_FORMAT) {
                return ldb_pack_data_v1(ldb, message, data);
        } else if (pack_format_version == LDB_PACKING_FORMAT_V2) {
                return ldb_pack_data_v2(ldb, message, data);
        } else {
                errno = EINVAL;
                return -1;
        }
}

/*
 * Unpack a ldb message from a linear buffer in ldb_val
 */
static int ldb_unpack_data_flags_v1(struct ldb_context *ldb,
                                    const struct ldb_val *data,
                                    struct ldb_message *message,
                                    unsigned int flags,
                                    unsigned format)
{
        uint8_t *p;
        size_t remaining;
        size_t dn_len;
        unsigned int i, j;
        unsigned int nelem = 0;
        size_t len;
        struct ldb_val *ldb_val_single_array = NULL;

        message->elements = NULL;

        p = data->data;

        /* Format (U32, already read) + U32 for num_elements */
        if (data->length < U32_LEN * 2) {
                errno = EIO;
                goto failed;
        }

        /* Skip first 4 bytes, format already read */
        p += U32_LEN;
        message->num_elements = PULL_LE_U32(p, 0);
        p += U32_LEN;

        remaining = data->length - U32_LEN * 2;

        switch (format) {
        case LDB_PACKING_FORMAT_NODN:
                message->dn = NULL;
                break;

        case LDB_PACKING_FORMAT:
                /*
                 * With this check, we know that the DN at p is \0
                 * terminated.
                 */
                dn_len = strnlen((char *)p, remaining);
                if (dn_len == remaining) {
                        errno = EIO;
                        goto failed;
                }
                if (flags & LDB_UNPACK_DATA_FLAG_NO_DN) {
                        message->dn = NULL;
                } else {
                        struct ldb_val blob;
                        blob.data = discard_const_p(uint8_t, p);
                        blob.length = dn_len;
                        message->dn = ldb_dn_from_ldb_val(message, ldb, &blob);
                        if (message->dn == NULL) {
                                errno = ENOMEM;
                                goto failed;
                        }
                }
                /*
                 * Redundant: by definition, remaining must be more
                 * than one less than dn_len, as otherwise it would be
                 * == dn_len
                 */
                if (remaining < dn_len + NULL_PAD_BYTE_LEN) {
                        errno = EIO;
                        goto failed;
                }
                remaining -= dn_len + NULL_PAD_BYTE_LEN;
                p += dn_len + NULL_PAD_BYTE_LEN;
                break;

        default:
                errno = EIO;
                goto failed;
        }

        if (flags & LDB_UNPACK_DATA_FLAG_NO_ATTRS) {
                message->num_elements = 0;
                return 0;
        }
        
        if (message->num_elements == 0) {
                return 0;
        }

        if (message->num_elements > remaining / 6) {
                errno = EIO;
                goto failed;
        }

        message->elements = talloc_zero_array(message, struct ldb_message_element,
                                              message->num_elements);
        if (!message->elements) {
                errno = ENOMEM;
                goto failed;
        }

        /*
         * In typical use, most values are single-valued.  This makes
         * it quite expensive to allocate an array of ldb_val for each
         * of these, just to then hold the pointer to the data buffer
         * So with LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC we allocate this
         * ahead of time and use it for the single values where possible.
         * (This is used the the normal search case, but not in the
         * index case because of caller requirements).
         */
        if (flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) {
                ldb_val_single_array = talloc_array(message->elements, struct ldb_val,
                                                    message->num_elements);
                if (ldb_val_single_array == NULL) {
                        errno = ENOMEM;
                        goto failed;
                }
        }

        for (i=0;i<message->num_elements;i++) {
                const char *attr = NULL;
                size_t attr_len;
                struct ldb_message_element *element = NULL;

                /*
                 * Sanity check: Element must be at least the size of empty
                 * attr name and value and NULL terms for each.
                 */
                if (remaining < U32_LEN * 2 + NULL_PAD_BYTE_LEN * 2) {
                        errno = EIO;
                        goto failed;
                }

                /*
                 * With this check, we know that the attribute name at
                 * p is \0 terminated.
                 */
                attr_len = strnlen((char *)p, remaining-6);
                if (attr_len == remaining-6) {
                        errno = EIO;
                        goto failed;
                }
                if (attr_len == 0) {
                        errno = EIO;
                        goto failed;
                }
                attr = (char *)p;

                element = &message->elements[nelem];
                element->name = attr;
                element->flags = 0;

                if (remaining < (attr_len + NULL_PAD_BYTE_LEN)) {
                        errno = EIO;
                        goto failed;
                }
                remaining -= attr_len + NULL_PAD_BYTE_LEN;
                p += attr_len + NULL_PAD_BYTE_LEN;
                element->num_values = PULL_LE_U32(p, 0);
                element->values = NULL;
                if ((flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) && element->num_values == 1) {
                        element->values = &ldb_val_single_array[nelem];
                        element->flags |= LDB_FLAG_INTERNAL_SHARED_VALUES;
                } else if (element->num_values != 0) {
                        element->values = talloc_array(message->elements,
                                                       struct ldb_val,
                                                       element->num_values);
                        if (!element->values) {
                                errno = ENOMEM;
                                goto failed;
                        }
                }
                p += U32_LEN;
                if (remaining < U32_LEN) {
                        errno = EIO;
                        goto failed;
                }
                remaining -= U32_LEN;
                for (j = 0; j < element->num_values; j++) {
                        /*
                         * Sanity check: Value must be at least the size of
                         * empty val and NULL terminator.
                         */
                        if (remaining < U32_LEN + NULL_PAD_BYTE_LEN) {
                                errno = EIO;
                                goto failed;
                        }
                        remaining -= U32_LEN + NULL_PAD_BYTE_LEN;

                        len = PULL_LE_U32(p, 0);
                        if (remaining < len) {
                                errno = EIO;
                                goto failed;
                        }
                        if (len + NULL_PAD_BYTE_LEN < len) {
                                errno = EIO;
                                goto failed;
                        }

                        element->values[j].length = len;
                        element->values[j].data = p + U32_LEN;
                        remaining -= len;
                        p += len + U32_LEN + NULL_PAD_BYTE_LEN;
                }
                nelem++;
        }
        /*
         * Adapt the number of elements to the real number of unpacked elements,
         * it means that we overallocated elements array.
         */
        message->num_elements = nelem;

        /*
         * Shrink the allocated size.  On current talloc behaviour
         * this will help if we skipped 32 or more attributes.
         */
        message->elements = talloc_realloc(message, message->elements,
                                           struct ldb_message_element,
                                           message->num_elements);

        if (remaining != 0) {
                ldb_debug(ldb, LDB_DEBUG_ERROR,
                          "Error: %zu bytes unread in ldb_unpack_data_flags",
                          remaining);
        }

        return 0;

failed:
        talloc_free(message->elements);
        return -1;
}

/*
 * Unpack a ldb message from a linear buffer in ldb_val
 */
static int ldb_unpack_data_flags_v2(struct ldb_context *ldb,
                                    const struct ldb_val *data,
                                    struct ldb_message *message,
                                    unsigned int flags)
{
        uint8_t *p, *q, *end_p, *value_section_p;
        unsigned int i, j;
        unsigned int nelem = 0;
        size_t len;
        struct ldb_val *ldb_val_single_array = NULL;
        uint8_t val_len_width;

        message->elements = NULL;

        p = data->data;
        end_p = p + data->length;

        /* Skip first 4 bytes, format already read */
        p += U32_LEN;

        /* First fields are fixed: num_elements, DN length */
        if (U32_LEN * 2 > end_p - p) {
                errno = EIO;
                goto failed;
        }

        message->num_elements = PULL_LE_U32(p, 0);
        p += U32_LEN;

        len = PULL_LE_U32(p, 0);
        p += U32_LEN;

        if (len + NULL_PAD_BYTE_LEN > end_p - p) {
                errno = EIO;
                goto failed;
        }

        if (flags & LDB_UNPACK_DATA_FLAG_NO_DN) {
                message->dn = NULL;
        } else {
                struct ldb_val blob;
                blob.data = discard_const_p(uint8_t, p);
                blob.length = len;
                message->dn = ldb_dn_from_ldb_val(message, ldb, &blob);
                if (message->dn == NULL) {
                        errno = ENOMEM;
                        goto failed;
                }
        }

        p += len + NULL_PAD_BYTE_LEN;

        if (*(p-NULL_PAD_BYTE_LEN) != '\0') {
                errno = EINVAL;
                goto failed;
        }

        /* Now skip the canonicalized DN and its length */
        len = PULL_LE_U32(p, 0) + NULL_PAD_BYTE_LEN;
        p += U32_LEN;

        if (len > end_p - p) {
                errno = EIO;
                goto failed;
        }

        p += len;

        if (*(p-NULL_PAD_BYTE_LEN) != '\0') {
                errno = EINVAL;
                goto failed;
        }

        if (flags & LDB_UNPACK_DATA_FLAG_NO_ATTRS) {
                message->num_elements = 0;
                return 0;
        }

        if (message->num_elements == 0) {
                return 0;
        }

        /*
         * Sanity check (17 bytes is the minimum element size)
         */
        if (message->num_elements > (end_p - p) / 17) {
                errno = EIO;
                goto failed;
        }

        message->elements = talloc_zero_array(message,
                                              struct ldb_message_element,
                                              message->num_elements);
        if (!message->elements) {
                errno = ENOMEM;
                goto failed;
        }

        /*
         * In typical use, most values are single-valued.  This makes
         * it quite expensive to allocate an array of ldb_val for each
         * of these, just to then hold the pointer to the data buffer.
         * So with LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC we allocate this
         * ahead of time and use it for the single values where possible.
         * (This is used the the normal search case, but not in the
         * index case because of caller requirements).
         */
        if (flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) {
                ldb_val_single_array = talloc_array(message->elements,
                                                    struct ldb_val,
                                                    message->num_elements);
                if (ldb_val_single_array == NULL) {
                        errno = ENOMEM;
                        goto failed;
                }
        }

        q = p + PULL_LE_U32(p, 0);
        value_section_p = q;
        p += U32_LEN;

        for (i=0;i<message->num_elements;i++) {
                const char *attr = NULL;
                size_t attr_len;
                struct ldb_message_element *element = NULL;

                /* Sanity check: minimum element size */
                if ((U32_LEN * 2) + /* attr name len, num values */
                        (U8_LEN * 2) + /* value length width, one val length */
                        (NULL_PAD_BYTE_LEN * 2) /* null for attr name + val */
                        > value_section_p - p) {
                        errno = EIO;
                        goto failed;
                }

                attr_len = PULL_LE_U32(p, 0);
                p += U32_LEN;

                if (attr_len == 0) {
                        errno = EIO;
                        goto failed;
                }
                attr = (char *)p;

                p += attr_len + NULL_PAD_BYTE_LEN;
                /*
                 * num_values, val_len_width
                 *
                 * val_len_width is the width specifier
                 * for the variable length encoding
                 */
                if (U32_LEN + U8_LEN > value_section_p - p) {
                        errno = EIO;
                        goto failed;
                }

                if (*(p-NULL_PAD_BYTE_LEN) != '\0') {
                        errno = EINVAL;
                        goto failed;
                }

                element = &message->elements[nelem];
                element->name = attr;
                element->flags = 0;

                element->num_values = PULL_LE_U32(p, 0);
                element->values = NULL;
                if ((flags & LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC) &&
                    element->num_values == 1) {
                        element->values = &ldb_val_single_array[nelem];
                        element->flags |= LDB_FLAG_INTERNAL_SHARED_VALUES;
                } else if (element->num_values != 0) {
                        element->values = talloc_array(message->elements,
                                                       struct ldb_val,
                                                       element->num_values);
                        if (!element->values) {
                                errno = ENOMEM;
                                goto failed;
                        }
                }

                p += U32_LEN;

                /*
                 * Here we read how wide the remaining lengths are
                 * which avoids storing and parsing a lot of leading
                 * 0s
                 */
                val_len_width = *p;
                p += U8_LEN;

                if (val_len_width * element->num_values >
                    value_section_p - p) {
                        errno = EIO;
                        goto failed;
                }

                /*
                 * This is structured weird for compiler optimization
                 * purposes, but we need to pull the array of widths
                 * with different macros depending on how wide the
                 * biggest one is (specified by val_len_width)
                 */
                if (val_len_width == U8_LEN) {
                        for (j = 0; j < element->num_values; j++) {
                                element->values[j].length = PULL_LE_U8(p, 0);
                                p += U8_LEN;
                        }
                } else if (val_len_width == U16_LEN) {
                        for (j = 0; j < element->num_values; j++) {
                                element->values[j].length = PULL_LE_U16(p, 0);
                                p += U16_LEN;
                        }
                } else if (val_len_width == U32_LEN) {
                        for (j = 0; j < element->num_values; j++) {
                                element->values[j].length = PULL_LE_U32(p, 0);
                                p += U32_LEN;
                        }
                } else {
                        errno = ERANGE;
                        goto failed;
                }

                for (j = 0; j < element->num_values; j++) {
                        len = element->values[j].length;
                        if (len + NULL_PAD_BYTE_LEN < len) {
                                errno = EIO;
                                goto failed;
                        }
                        if (len + NULL_PAD_BYTE_LEN > end_p - q) {
                                errno = EIO;
                                goto failed;
                        }

                        element->values[j].data = q;
                        q += len + NULL_PAD_BYTE_LEN;
                }
                nelem++;
        }

        /*
         * If p isn't now pointing at the beginning of the value section,
         * something went very wrong.
         */
        if (p != value_section_p) {
                ldb_debug(ldb, LDB_DEBUG_ERROR,
                          "Error: Data corruption in ldb_unpack_data_flags");
                errno = EIO;
                goto failed;
        }

        /*
         * Adapt the number of elements to the real number of unpacked
         * elements it means that we overallocated elements array.
         */
        message->num_elements = nelem;

        /*
         * Shrink the allocated size.  On current talloc behaviour
         * this will help if we skipped 32 or more attributes.
         */
        message->elements = talloc_realloc(message, message->elements,
                                           struct ldb_message_element,
                                           message->num_elements);

        if (q != end_p) {
                ldb_debug(ldb, LDB_DEBUG_ERROR,
                          "Error: %zu bytes unread in ldb_unpack_data_flags",
                          end_p - q);
                errno = EIO;
                goto failed;
        }

        return 0;

failed:
        talloc_free(message->elements);
        return -1;
}

int ldb_unpack_get_format(const struct ldb_val *data,
                          uint32_t *pack_format_version)
{
        if (data->length < U32_LEN) {
                return LDB_ERR_OPERATIONS_ERROR;
        }
        *pack_format_version = PULL_LE_U32(data->data, 0);
        return LDB_SUCCESS;
}

/*
 * Unpack a ldb message from a linear buffer in ldb_val
 */
int ldb_unpack_data_flags(struct ldb_context *ldb,
                          const struct ldb_val *data,
                          struct ldb_message *message,
                          unsigned int flags)
{
        unsigned format;

        if (data->length < U32_LEN) {
                errno = EIO;
                return -1;
        }

        format = PULL_LE_U32(data->data, 0);
        if (format == LDB_PACKING_FORMAT_V2) {
                return ldb_unpack_data_flags_v2(ldb, data, message, flags);
        }

        /*
         * The v1 function we're about to call takes either LDB_PACKING_FORMAT
         * or LDB_PACKING_FORMAT_NODN packing format versions, and will error
         * if given some other version, so we don't need to do any further
         * checks on 'format'.
         */
        return ldb_unpack_data_flags_v1(ldb, data, message, flags, format);
}


/*
 * Unpack a ldb message from a linear buffer in ldb_val
 *
 * Free with ldb_unpack_data_free()
 */
int ldb_unpack_data(struct ldb_context *ldb,
                    const struct ldb_val *data,
                    struct ldb_message *message)
{
        return ldb_unpack_data_flags(ldb, data, message, 0);
}

/*
  add the special distinguishedName element
*/
int ldb_msg_add_distinguished_name(struct ldb_message *msg)
{
        const char *dn_attr = "distinguishedName";
        char *dn = NULL;

        if (ldb_msg_find_element(msg, dn_attr)) {
                /*
                 * This should not happen, but this is
                 * existing behaviour...
                 */
                return LDB_SUCCESS;
        }

        dn = ldb_dn_alloc_linearized(msg, msg->dn);
        if (dn == NULL) {
                return LDB_ERR_OPERATIONS_ERROR;
        }

        return ldb_msg_add_steal_string(msg, dn_attr, dn);
}

/*
 * filter the specified list of attributes from msg,
 * adding requested attributes, and perhaps all for *,
 * but not the DN to filtered_msg.
 */
int ldb_filter_attrs(struct ldb_context *ldb,
                     const struct ldb_message *msg,
                     const char *const *attrs,
                     struct ldb_message *filtered_msg)
{
        unsigned int i;
        bool keep_all = false;
        bool add_dn = false;
        uint32_t num_elements;
        uint32_t elements_size;

        if (attrs) {
                /* check for special attrs */
                for (i = 0; attrs[i]; i++) {
                        int cmp = strcmp(attrs[i], "*");
                        if (cmp == 0) {
                                keep_all = true;
                                break;
                        }
                        cmp = ldb_attr_cmp(attrs[i], "distinguishedName");
                        if (cmp == 0) {
                                add_dn = true;
                        }
                }
        } else {
                keep_all = true;
        }

        if (keep_all) {
                add_dn = true;
                elements_size = msg->num_elements + 1;

        /* Shortcuts for the simple cases */
        } else if (add_dn && i == 1) {
                if (ldb_msg_add_distinguished_name(filtered_msg) != 0) {
                        goto failed;
                }
                return 0;
        } else if (i == 0) {
                return 0;

        /*
         * Otherwise we are copying at most as many elements as we
         * have attributes
         */
        } else {
                elements_size = i;
        }

        filtered_msg->elements = talloc_array(filtered_msg,
                                              struct ldb_message_element,
                                              elements_size);
        if (filtered_msg->elements == NULL) goto failed;

        num_elements = 0;

        for (i = 0; i < msg->num_elements; i++) {
                struct ldb_message_element *el = &msg->elements[i];

                /*
                 * el2 is assigned after the Pigeonhole principle
                 * check below for clarity
                 */
                struct ldb_message_element *el2 = NULL;
                unsigned int j;

                if (keep_all == false) {
                        bool found = false;
                        for (j = 0; attrs[j]; j++) {
                                int cmp = ldb_attr_cmp(el->name, attrs[j]);
                                if (cmp == 0) {
                                        found = true;
                                        break;
                                }
                        }
                        if (found == false) {
                                continue;
                        }
                }

                /*
                 * Pigeonhole principle: we can't have more elements
                 * than the number of attributes if they are unique in
                 * the DB.
                 */
                if (num_elements >= elements_size) {
                        goto failed;
                }

                el2 = &filtered_msg->elements[num_elements];

                *el2 = *el;
                el2->name = talloc_strdup(filtered_msg->elements,
                                          el->name);
                if (el2->name == NULL) {
                        goto failed;
                }
                el2->values = talloc_array(filtered_msg->elements,
                                           struct ldb_val, el->num_values);
                if (el2->values == NULL) {
                        goto failed;
                }
                for (j=0;j<el->num_values;j++) {
                        el2->values[j] = ldb_val_dup(el2->values, &el->values[j]);
                        if (el2->values[j].data == NULL && el->values[j].length != 0) {
                                goto failed;
                        }
                }
                num_elements++;
        }

        filtered_msg->num_elements = num_elements;

        if (add_dn) {
                if (ldb_msg_add_distinguished_name(filtered_msg) != 0) {
                        goto failed;
                }
        }

        if (filtered_msg->num_elements > 0) {
                filtered_msg->elements
                        = talloc_realloc(filtered_msg,
                                         filtered_msg->elements,
                                         struct ldb_message_element,
                                         filtered_msg->num_elements);
                if (filtered_msg->elements == NULL) {
                        goto failed;
                }
        } else {
                TALLOC_FREE(filtered_msg->elements);
        }

        return 0;
failed:
        TALLOC_FREE(filtered_msg->elements);
        return -1;
}

/*
 * filter the specified list of attributes from msg,
 * adding requested attributes, and perhaps all for *.
 * Unlike ldb_filter_attrs(), the DN will not be added
 * if it is missing.
 */
int ldb_filter_attrs_in_place(struct ldb_message *msg,
                              const char *const *attrs)
{
        unsigned int i = 0;
        bool keep_all = false;
        unsigned int num_del = 0;

        if (attrs) {
                /* check for special attrs */
                for (i = 0; attrs[i]; i++) {
                        int cmp = strcmp(attrs[i], "*");
                        if (cmp == 0) {
                                keep_all = true;
                                break;
                        }
                }
                if (!keep_all && i == 0) {
                        msg->num_elements = 0;
                        return LDB_SUCCESS;
                }
        } else {
                keep_all = true;
        }

        for (i = 0; i < msg->num_elements; i++) {
                bool found = false;
                unsigned int j;

                if (keep_all) {
                        found = true;
                } else {
                        for (j = 0; attrs[j]; j++) {
                                int cmp = ldb_attr_cmp(msg->elements[i].name, attrs[j]);
                                if (cmp == 0) {
                                        found = true;
                                        break;
                                }
                        }
                }

                if (!found) {
                        ++num_del;
                } else if (num_del != 0) {
                        msg->elements[i - num_del] = msg->elements[i];
                }
        }

        msg->num_elements -= num_del;

        return LDB_SUCCESS;
}

/* Have an unpacked ldb message take talloc ownership of its elements. */
int ldb_msg_elements_take_ownership(struct ldb_message *msg)
{
        unsigned int i = 0;

        for (i = 0; i < msg->num_elements; i++) {
                struct ldb_message_element *el = &msg->elements[i];
                const char *name;
                unsigned int j;

                name = talloc_strdup(msg->elements,
                                     el->name);
                if (name == NULL) {
                        return -1;
                }
                el->name = name;

                if (el->flags & LDB_FLAG_INTERNAL_SHARED_VALUES) {
                        struct ldb_val *values = talloc_memdup(msg->elements, el->values,
                                                               sizeof(struct ldb_val) * el->num_values);
                        if (values == NULL) {
                                return -1;
                        }
                        el->values = values;
                        el->flags &= ~LDB_FLAG_INTERNAL_SHARED_VALUES;
                }

                for (j = 0; j < el->num_values; j++) {
                        struct ldb_val val = ldb_val_dup(el->values, &el->values[j]);
                        if (val.data == NULL && el->values[j].length != 0) {
                                return -1;
                        }
                        el->values[j] = val;
                }
        }

        return LDB_SUCCESS;
}