source4/lib/ldb/common/ldb_dn.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce 2005
   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 dn creation and manipulation utility functions
  28  *
  29  *  Description: - explode a dn into it's own basic elements
  30  *                 and put them in a structure (only if necessary)
  31  *               - manipulate ldb_dn structures
  32  *
  33  *  Author: Simo Sorce
  34  */
  35
  36 #include "ldb_private.h"
  37 #include <ctype.h>
  38
  39 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  40
  41 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
  42
  43 /**
  44    internal ldb exploded dn structures
  45 */
  46 struct ldb_dn_component {
  47
  48         char *name;
  49         struct ldb_val value;
  50
  51         char *cf_name;
  52         struct ldb_val cf_value;
  53 };
  54
  55 struct ldb_dn_ext_component {
  56
  57         char *name;
  58         struct ldb_val value;
  59 };
  60
  61 struct ldb_dn {
  62
  63         struct ldb_context *ldb;
  64
  65         /* Special DNs are always linearized */
  66         bool special;
  67         bool invalid;
  68
  69         bool valid_case;
  70
  71         char *linearized;
  72         char *ext_linearized;
  73         char *casefold;
  74
  75         unsigned int comp_num;
  76         struct ldb_dn_component *components;
  77
  78         unsigned int ext_comp_num;
  79         struct ldb_dn_ext_component *ext_components;
  80
  81         char extra_type;
  82         struct ldb_val extra_val;
  83 };
  84
  85 /* it is helpful to be able to break on this in gdb */
  86 static void ldb_dn_mark_invalid(struct ldb_dn *dn)
  87 {
  88         dn->invalid = true;
  89 }
  90
  91 /* strdn may be NULL */
  92 struct ldb_dn *ldb_dn_from_ldb_val(void *mem_ctx,
  93                                    struct ldb_context *ldb,
  94                                    const struct ldb_val *strdn)
  95 {
  96         struct ldb_dn *dn;
  97
  98         if (! ldb) return NULL;
  99
 100         if (strdn && strdn->data
 101             && (strnlen((const char*)strdn->data, strdn->length) != strdn->length)) {
 102                 /* The RDN must not contain a character with value 0x0 */
 103                 return NULL;
 104         }
 105
 106         /* if the DN starts with B: then it has a binary blob
 107          * attached. Called the binary dn parser, which will call back
 108          * here for the rest of the DN */
 109         if (strdn->data && strncmp((char *)strdn->data, "B:", 2) == 0) {
 110                 return ldb_dn_binary_from_ldb_val(mem_ctx, ldb, strdn);
 111         }
 112
 113         dn = talloc_zero(mem_ctx, struct ldb_dn);
 114         LDB_DN_NULL_FAILED(dn);
 115
 116         dn->ldb = ldb;
 117
 118         if (strdn->data && strdn->length) {
 119                 const char *data = (const char *)strdn->data;
 120                 size_t length = strdn->length;
 121
 122                 if (data[0] == '@') {
 123                         dn->special = true;
 124                 }
 125                 dn->ext_linearized = talloc_strndup(dn, data, length);
 126                 LDB_DN_NULL_FAILED(dn->ext_linearized);
 127
 128                 if (data[0] == '<') {
 129                         const char *p_save, *p = dn->ext_linearized;
 130                         do {
 131                                 p_save = p;
 132                                 p = strstr(p, ">;");
 133                                 if (p) {
 134                                         p = p + 2;
 135                                 }
 136                         } while (p);
 137
 138                         if (p_save == dn->ext_linearized) {
 139                                 dn->linearized = talloc_strdup(dn, "");
 140                         } else {
 141                                 dn->linearized = talloc_strdup(dn, p_save);
 142                         }
 143                         LDB_DN_NULL_FAILED(dn->linearized);
 144                 } else {
 145                         dn->linearized = dn->ext_linearized;
 146                         dn->ext_linearized = NULL;
 147                 }
 148         } else {
 149                 dn->linearized = talloc_strdup(dn, "");
 150                 LDB_DN_NULL_FAILED(dn->linearized);
 151         }
 152
 153         return dn;
 154
 155 failed:
 156         talloc_free(dn);
 157         return NULL;
 158 }
 159
 160 /*
 161   a version of strhex_to_str internal to ldb, for use by the binary
 162   ldb code
 163  */
 164 static size_t ldb_strhex_to_str(char *p, size_t p_len, const char *strhex,
 165                                 size_t strhex_len)
 166 {
 167         size_t i;
 168         size_t num_chars = 0;
 169         uint8_t   lonybble, hinybble;
 170         const char     *hexchars = "0123456789ABCDEF";
 171         char           *p1 = NULL, *p2 = NULL;
 172
 173         for (i = 0; i < strhex_len && strhex[i] != 0; i++) {
 174                 if (!(p1 = strchr(hexchars, toupper((unsigned char)strhex[i]))))
 175                         break;
 176
 177                 i++; /* next hex digit */
 178
 179                 if (!(p2 = strchr(hexchars, toupper((unsigned char)strhex[i]))))
 180                         break;
 181
 182                 /* get the two nybbles */
 183                 hinybble = PTR_DIFF(p1, hexchars);
 184                 lonybble = PTR_DIFF(p2, hexchars);
 185
 186                 if (num_chars >= p_len) {
 187                         break;
 188                 }
 189
 190                 p[num_chars] = (hinybble << 4) | lonybble;
 191                 num_chars++;
 192
 193                 p1 = NULL;
 194                 p2 = NULL;
 195         }
 196         return num_chars;
 197 }
 198
 199 /* strdn may be NULL */
 200 struct ldb_dn *ldb_dn_binary_from_ldb_val(void *mem_ctx,
 201                                           struct ldb_context *ldb,
 202                                           const struct ldb_val *strdn)
 203 {
 204         struct ldb_dn *dn;
 205         const char *data;
 206         size_t len;
 207         char *linearized;
 208         TALLOC_CTX *tmp_ctx;
 209         char *p1;
 210         char *p2;
 211         uint32_t blen;
 212         struct ldb_val bval;
 213         struct ldb_val dval;
 214         char *dn_str;
 215         char *old;
 216
 217         if (strdn && strdn->data
 218             && (strlen((const char*)strdn->data) != strdn->length)) {
 219                 /* The RDN must not contain a character with value 0x0 */
 220                 return NULL;
 221         }
 222
 223         if (!strdn->data || strdn->length == 0) {
 224                 return NULL;
 225
 226         }
 227
 228         tmp_ctx = talloc_new(mem_ctx);
 229         if (tmp_ctx == NULL) {
 230                 return NULL;
 231         }
 232
 233         data = (const char *)strdn->data;
 234
 235         if (data[0] != 'B') {
 236                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": no prefix?\n");
 237                 return NULL;
 238         }
 239
 240         len = strdn->length;
 241         linearized = talloc_strndup(tmp_ctx, data, len);
 242         if (linearized == NULL) {
 243                 goto failed;
 244         }
 245
 246         ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": processing DN '%s'\n", linearized);
 247
 248         p1 = linearized;
 249
 250         p1++; len--;
 251
 252         if (p1[0] != ':') {
 253                 goto failed;
 254         }
 255         p1++;
 256         len--;
 257
 258         errno = 0;
 259         blen = strtoul(p1, &p2, 10);
 260         if (errno != 0) {
 261                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": failed\n");
 262                 goto failed;
 263         }
 264         if (p2 == NULL) {
 265                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": failed\n");
 266                 goto failed;
 267         }
 268         if (p2[0] != ':') {
 269                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": failed\n");
 270                 goto failed;
 271         }
 272         len -= PTR_DIFF(p2,p1);//???
 273         p1 = p2+1;
 274         len--;
 275
 276         if (blen >= len) {
 277                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": blen=%u len=%u\n", (unsigned)blen, (unsigned)len);
 278                 goto failed;
 279         }
 280
 281         p2 = p1 + blen;
 282         if (p2[0] != ':') {
 283                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": %s", p2);
 284                 goto failed;
 285         }
 286         dn_str = p2+1;
 287
 288         bval.length = (blen/2)+1;
 289         bval.data = talloc_size(tmp_ctx, bval.length);
 290         if (bval.data == NULL) {
 291                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": err\n");
 292                 goto failed;
 293         }
 294         bval.data[bval.length-1] = 0;
 295
 296         bval.length = ldb_strhex_to_str((char *)bval.data, bval.length,
 297                                         p1, blen);
 298
 299         dval.data = (uint8_t *)dn_str;
 300         dval.length = strlen(dn_str);
 301
 302         dn = ldb_dn_from_ldb_val(mem_ctx, ldb, &dval);
 303         if (dn == NULL) {
 304                 ldb_debug(ldb, LDB_DEBUG_TRACE, __location__ ": err\n");
 305                 goto failed;
 306         }
 307         dn->extra_type = data[0];
 308         dn->extra_val = bval;
 309         talloc_steal(dn, bval.data);
 310
 311         *dn_str = '\0';
 312         old = dn->linearized;
 313         dn->linearized = talloc_asprintf(dn, "%s%s", linearized, dn->linearized);
 314         talloc_free(old);
 315         if (dn->ext_linearized) {
 316                 old = dn->ext_linearized;
 317                 dn->ext_linearized = talloc_asprintf(dn, "%s%s", linearized, dn->ext_linearized);
 318                 talloc_free(old);
 319         }
 320
 321         return dn;
 322 failed:
 323         talloc_free(tmp_ctx);
 324         return NULL;
 325 }
 326
 327 /* strdn may be NULL */
 328 struct ldb_dn *ldb_dn_new(void *mem_ctx,
 329                           struct ldb_context *ldb,
 330                           const char *strdn)
 331 {
 332         struct ldb_val blob;
 333         blob.data = discard_const_p(uint8_t, strdn);
 334         blob.length = strdn ? strlen(strdn) : 0;
 335         return ldb_dn_from_ldb_val(mem_ctx, ldb, &blob);
 336 }
 337
 338 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx,
 339                               struct ldb_context *ldb,
 340                               const char *new_fmt, ...)
 341 {
 342         char *strdn;
 343         va_list ap;
 344
 345         if ( (! mem_ctx) || (! ldb)) return NULL;
 346
 347         va_start(ap, new_fmt);
 348         strdn = talloc_vasprintf(mem_ctx, new_fmt, ap);
 349         va_end(ap);
 350
 351         if (strdn) {
 352                 struct ldb_dn *dn = ldb_dn_new(mem_ctx, ldb, strdn);
 353                 talloc_free(strdn);
 354                 return dn;
 355         }
 356
 357         return NULL;
 358 }
 359
 360 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 361 {
 362         const char *p, *s;
 363         char *d;
 364         int l;
 365
 366         p = s = src;
 367         d = dst;
 368
 369         while (p - src < len) {
 370
 371                 p += strcspn(p, ",=\n+<>#;\\\"");
 372
 373                 if (p - src == len) /* found no escapable chars */
 374                         break;
 375
 376                 /* copy the part of the string before the stop */
 377                 memcpy(d, s, p - s);
 378                 d += (p - s); /* move to current position */
 379
 380                 if (*p) { /* it is a normal escapable character */
 381                         *d++ = '\\';
 382                         *d++ = *p++;
 383                 } else { /* we have a zero byte in the string */
 384                         strncpy(d, "\00", 3); /* escape the zero */
 385                         d += 3;
 386                         p++; /* skip the zero */
 387                 }
 388                 s = p; /* move forward */
 389         }
 390
 391         /* copy the last part (with zero) and return */
 392         l = len - (s - src);
 393         memcpy(d, s, l + 1);
 394
 395         /* return the length of the resulting string */
 396         return (l + (d - dst));
 397 }
 398
 399 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 400 {
 401         char *dst;
 402
 403         if (!value.length)
 404                 return NULL;
 405
 406         /* allocate destination string, it will be at most 3 times the source */
 407         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 408         if ( ! dst) {
 409                 talloc_free(dst);
 410                 return NULL;
 411         }
 412
 413         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 414
 415         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
 416
 417         return dst;
 418 }
 419
 420 /*
 421   explode a DN string into a ldb_dn structure
 422   based on RFC4514 except that we don't support multiple valued RDNs
 423
 424   TODO: according to MS-ADTS:3.1.1.5.2 Naming Constraints
 425   DN must be compliant with RFC2253
 426 */
 427 static bool ldb_dn_explode(struct ldb_dn *dn)
 428 {
 429         char *p, *ex_name, *ex_value, *data, *d, *dt, *t;
 430         bool trim = false;
 431         bool in_extended = false;
 432         bool in_ex_name = false;
 433         bool in_ex_value = false;
 434         bool in_attr = false;
 435         bool in_value = false;
 436         bool in_quote = false;
 437         bool is_oid = false;
 438         bool escape = false;
 439         unsigned x;
 440         int l, ret;
 441         char *parse_dn;
 442
 443         if ( ! dn || dn->invalid) return false;
 444
 445         if (dn->components) {
 446                 return true;
 447         }
 448
 449         if (dn->ext_linearized) {
 450                 parse_dn = dn->ext_linearized;
 451         } else {
 452                 parse_dn = dn->linearized;
 453         }
 454
 455         if ( ! parse_dn ) {
 456                 return false;
 457         }
 458
 459
 460         if (strncmp(parse_dn, "B:", 2) == 0) {
 461                 parse_dn = strchr(parse_dn, ':');
 462                 parse_dn = strchr(parse_dn+1, ':');
 463                 parse_dn = strchr(parse_dn+1, ':');
 464                 parse_dn++;
 465         }
 466
 467         /* Empty DNs */
 468         if (parse_dn[0] == '\0') {
 469                 return true;
 470         }
 471
 472         /* Special DNs case */
 473         if (dn->special) {
 474                 return true;
 475         }
 476
 477         /* make sure we free this if alloced previously before replacing */
 478         talloc_free(dn->components);
 479
 480         talloc_free(dn->ext_components);
 481         dn->ext_components = NULL;
 482
 483         /* in the common case we have 3 or more components */
 484         /* make sure all components are zeroed, other functions depend on it */
 485         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 486         if ( ! dn->components) {
 487                 return false;
 488         }
 489         dn->comp_num = 0;
 490
 491         /* Components data space is allocated here once */
 492         data = talloc_array(dn->components, char, strlen(parse_dn) + 1);
 493         if (!data) {
 494                 return false;
 495         }
 496
 497         p = parse_dn;
 498         in_extended = true;
 499         in_ex_name = false;
 500         in_ex_value = false;
 501         trim = true;
 502         t = NULL;
 503         d = dt = data;
 504
 505         while (*p) {
 506                 if (in_extended) {
 507
 508                         if (!in_ex_name && !in_ex_value) {
 509
 510                                 if (p[0] == '<') {
 511                                         p++;
 512                                         ex_name = d;
 513                                         in_ex_name = true;
 514                                         continue;
 515                                 } else if (p[0] == '\0') {
 516                                         p++;
 517                                         continue;
 518                                 } else {
 519                                         in_extended = false;
 520                                         in_attr = true;
 521                                         dt = d;
 522
 523                                         continue;
 524                                 }
 525                         }
 526
 527                         if (in_ex_name && *p == '=') {
 528                                 *d++ = '\0';
 529                                 p++;
 530                                 ex_value = d;
 531                                 in_ex_name = false;
 532                                 in_ex_value = true;
 533                                 continue;
 534                         }
 535
 536                         if (in_ex_value && *p == '>') {
 537                                 const struct ldb_dn_extended_syntax *ext_syntax;
 538                                 struct ldb_val ex_val = {
 539                                         .data = (uint8_t *)ex_value,
 540                                         .length = d - ex_value
 541                                 };
 542
 543                                 *d++ = '\0';
 544                                 p++;
 545                                 in_ex_value = false;
 546
 547                                 /* Process name and ex_value */
 548
 549                                 dn->ext_components = talloc_realloc(dn,
 550                                                                     dn->ext_components,
 551                                                                     struct ldb_dn_ext_component,
 552                                                                     dn->ext_comp_num + 1);
 553                                 if ( ! dn->ext_components) {
 554                                         /* ouch ! */
 555                                         goto failed;
 556                                 }
 557
 558                                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, ex_name);
 559                                 if (!ext_syntax) {
 560                                         /* We don't know about this type of extended DN */
 561                                         goto failed;
 562                                 }
 563
 564                                 dn->ext_components[dn->ext_comp_num].name = talloc_strdup(dn->ext_components, ex_name);
 565                                 if (!dn->ext_components[dn->ext_comp_num].name) {
 566                                         /* ouch */
 567                                         goto failed;
 568                                 }
 569                                 ret = ext_syntax->read_fn(dn->ldb, dn->ext_components,
 570                                                           &ex_val, &dn->ext_components[dn->ext_comp_num].value);
 571                                 if (ret != LDB_SUCCESS) {
 572                                         ldb_dn_mark_invalid(dn);
 573                                         goto failed;
 574                                 }
 575
 576                                 dn->ext_comp_num++;
 577
 578                                 if (*p == '\0') {
 579                                         /* We have reached the end (extended component only)! */
 580                                         talloc_free(data);
 581                                         return true;
 582
 583                                 } else if (*p == ';') {
 584                                         p++;
 585                                         continue;
 586                                 } else {
 587                                         ldb_dn_mark_invalid(dn);
 588                                         goto failed;
 589                                 }
 590                         }
 591
 592                         *d++ = *p++;
 593                         continue;
 594                 }
 595                 if (in_attr) {
 596                         if (trim) {
 597                                 if (*p == ' ') {
 598                                         p++;
 599                                         continue;
 600                                 }
 601
 602                                 /* first char */
 603                                 trim = false;
 604
 605                                 if (!isascii(*p)) {
 606                                         /* attr names must be ascii only */
 607                                         ldb_dn_mark_invalid(dn);
 608                                         goto failed;
 609                                 }
 610
 611                                 if (isdigit(*p)) {
 612                                         is_oid = true;
 613                                 } else
 614                                 if ( ! isalpha(*p)) {
 615                                         /* not a digit nor an alpha,
 616                                          * invalid attribute name */
 617                                         ldb_dn_mark_invalid(dn);
 618                                         goto failed;
 619                                 }
 620
 621                                 /* Copy this character across from parse_dn,
 622                                  * now we have trimmed out spaces */
 623                                 *d++ = *p++;
 624                                 continue;
 625                         }
 626
 627                         if (*p == ' ') {
 628                                 p++;
 629                                 /* valid only if we are at the end */
 630                                 trim = true;
 631                                 continue;
 632                         }
 633
 634                         if (trim && (*p != '=')) {
 635                                 /* spaces/tabs are not allowed */
 636                                 ldb_dn_mark_invalid(dn);
 637                                 goto failed;
 638                         }
 639
 640                         if (*p == '=') {
 641                                 /* attribute terminated */
 642                                 in_attr = false;
 643                                 in_value = true;
 644                                 trim = true;
 645                                 l = 0;
 646
 647                                 /* Terminate this string in d
 648                                  * (which is a copy of parse_dn
 649                                  *  with spaces trimmed) */
 650                                 *d++ = '\0';
 651                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 652                                 if ( ! dn->components[dn->comp_num].name) {
 653                                         /* ouch */
 654                                         goto failed;
 655                                 }
 656
 657                                 dt = d;
 658
 659                                 p++;
 660                                 continue;
 661                         }
 662
 663                         if (!isascii(*p)) {
 664                                 /* attr names must be ascii only */
 665                                 ldb_dn_mark_invalid(dn);
 666                                 goto failed;
 667                         }
 668
 669                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 670                                 /* not a digit nor a dot,
 671                                  * invalid attribute oid */
 672                                 ldb_dn_mark_invalid(dn);
 673                                 goto failed;
 674                         } else
 675                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 676                                 /* not ALPHA, DIGIT or HYPHEN */
 677                                 ldb_dn_mark_invalid(dn);
 678                                 goto failed;
 679                         }
 680
 681                         *d++ = *p++;
 682                         continue;
 683                 }
 684
 685                 if (in_value) {
 686                         if (in_quote) {
 687                                 if (*p == '\"') {
 688                                         if (p[-1] != '\\') {
 689                                                 p++;
 690                                                 in_quote = false;
 691                                                 continue;
 692                                         }
 693                                 }
 694                                 *d++ = *p++;
 695                                 l++;
 696                                 continue;
 697                         }
 698
 699                         if (trim) {
 700                                 if (*p == ' ') {
 701                                         p++;
 702                                         continue;
 703                                 }
 704
 705                                 /* first char */
 706                                 trim = false;
 707
 708                                 if (*p == '\"') {
 709                                         in_quote = true;
 710                                         p++;
 711                                         continue;
 712                                 }
 713                         }
 714
 715                         switch (*p) {
 716
 717                         /* TODO: support ber encoded values
 718                         case '#':
 719                         */
 720
 721                         case ',':
 722                                 if (escape) {
 723                                         *d++ = *p++;
 724                                         l++;
 725                                         escape = false;
 726                                         continue;
 727                                 }
 728                                 /* ok found value terminator */
 729
 730                                 if ( t ) {
 731                                         /* trim back */
 732                                         d -= (p - t);
 733                                         l -= (p - t);
 734                                 }
 735
 736                                 in_attr = true;
 737                                 in_value = false;
 738                                 trim = true;
 739
 740                                 p++;
 741                                 *d++ = '\0';
 742                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 743                                 dn->components[dn->comp_num].value.length = l;
 744                                 if ( ! dn->components[dn->comp_num].value.data) {
 745                                         /* ouch ! */
 746                                         goto failed;
 747                                 }
 748
 749                                 dt = d;
 750
 751                                 dn->comp_num++;
 752                                 if (dn->comp_num > 2) {
 753                                         dn->components = talloc_realloc(dn,
 754                                                                         dn->components,
 755                                                                         struct ldb_dn_component,
 756                                                                         dn->comp_num + 1);
 757                                         if ( ! dn->components) {
 758                                                 /* ouch ! */
 759                                                 goto failed;
 760                                         }
 761                                         /* make sure all components are zeroed, other functions depend on this */
 762                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 763                                 }
 764
 765                                 continue;
 766
 767                         case '=':
 768                         case '\n':
 769                         case '+':
 770                         case '<':
 771                         case '>':
 772                         case '#':
 773                         case ';':
 774                         case '\"':
 775                                 /* a string with not escaped specials is invalid (tested) */
 776                                 if ( ! escape) {
 777                                         ldb_dn_mark_invalid(dn);
 778                                         goto failed;
 779                                 }
 780                                 escape = false;
 781
 782                                 *d++ = *p++;
 783                                 l++;
 784
 785                                 if ( t ) t = NULL;
 786                                 break;
 787
 788                         case '\\':
 789                                 if ( ! escape) {
 790                                         escape = true;
 791                                         p++;
 792                                         continue;
 793                                 }
 794                                 escape = false;
 795
 796                                 *d++ = *p++;
 797                                 l++;
 798
 799                                 if ( t ) t = NULL;
 800                                 break;
 801
 802                         default:
 803                                 if (escape) {
 804                                         if (sscanf(p, "%02x", &x) != 1) {
 805                                                 /* invalid escaping sequence */
 806                                                 ldb_dn_mark_invalid(dn);
 807                                                 goto failed;
 808                                         }
 809                                         escape = false;
 810
 811                                         p += 2;
 812                                         *d++ = (unsigned char)x;
 813                                         l++;
 814
 815                                         if ( t ) t = NULL;
 816                                         break;
 817                                 }
 818
 819                                 if (*p == ' ') {
 820                                         if ( ! t) t = p;
 821                                 } else {
 822                                         if ( t ) t = NULL;
 823                                 }
 824
 825                                 *d++ = *p++;
 826                                 l++;
 827
 828                                 break;
 829                         }
 830
 831                 }
 832         }
 833
 834         if (in_attr || in_quote) {
 835                 /* invalid dn */
 836                 ldb_dn_mark_invalid(dn);
 837                 goto failed;
 838         }
 839
 840         /* save last element */
 841         if ( t ) {
 842                 /* trim back */
 843                 d -= (p - t);
 844                 l -= (p - t);
 845         }
 846
 847         *d++ = '\0';
 848         dn->components[dn->comp_num].value.length = l;
 849         dn->components[dn->comp_num].value.data =
 850                                 (uint8_t *)talloc_strdup(dn->components, dt);
 851         if ( ! dn->components[dn->comp_num].value.data) {
 852                 /* ouch */
 853                 goto failed;
 854         }
 855
 856         dn->comp_num++;
 857
 858         talloc_free(data);
 859         return true;
 860
 861 failed:
 862         dn->comp_num = 0;
 863         talloc_free(dn->components);
 864         return false;
 865 }
 866
 867 bool ldb_dn_validate(struct ldb_dn *dn)
 868 {
 869         return ldb_dn_explode(dn);
 870 }
 871
 872 static char *data_blob_hex_string_upper(TALLOC_CTX *mem_ctx, const struct ldb_val *blob)
 873 {
 874         int i;
 875         char *hex_string;
 876
 877         hex_string = talloc_array(mem_ctx, char, (blob->length*2)+1);
 878         if (!hex_string) {
 879                 return NULL;
 880         }
 881
 882         for (i = 0; i < blob->length; i++)
 883                 slprintf(&hex_string[i*2], 3, "%02X", blob->data[i]);
 884
 885         hex_string[(blob->length*2)] = '\0';
 886         return hex_string;
 887 }
 888
 889
 890 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 891 {
 892         int i, len;
 893         char *d, *n;
 894         char *extra_prefix = NULL;
 895
 896         if ( ! dn || ( dn->invalid)) return NULL;
 897
 898         if (dn->linearized) return dn->linearized;
 899
 900         if ( ! dn->components) {
 901                 ldb_dn_mark_invalid(dn);
 902                 return NULL;
 903         }
 904
 905         if (dn->extra_type == 'B') {
 906                 char *hexstr = data_blob_hex_string_upper(dn, &dn->extra_val);
 907                 extra_prefix = talloc_asprintf(dn, "B:%u:%s:", (unsigned)(dn->extra_val.length*2), hexstr);
 908                 talloc_free(hexstr);
 909         }
 910
 911         if (dn->comp_num == 0) {
 912                 dn->linearized = talloc_strdup(dn, "");
 913                 if ( ! dn->linearized) return NULL;
 914                 return dn->linearized;
 915         }
 916
 917         /* calculate maximum possible length of DN */
 918         for (len = 0, i = 0; i < dn->comp_num; i++) {
 919                 /* name len */
 920                 len += strlen(dn->components[i].name);
 921                 /* max escaped data len */
 922                 len += (dn->components[i].value.length * 3);
 923                 len += 2; /* '=' and ',' */
 924         }
 925         dn->linearized = talloc_array(dn, char, len);
 926         if ( ! dn->linearized) return NULL;
 927
 928         d = dn->linearized;
 929
 930         for (i = 0; i < dn->comp_num; i++) {
 931
 932                 /* copy the name */
 933                 n = dn->components[i].name;
 934                 while (*n) *d++ = *n++;
 935
 936                 *d++ = '=';
 937
 938                 /* and the value */
 939                 d += ldb_dn_escape_internal( d,
 940                                 (char *)dn->components[i].value.data,
 941                                 dn->components[i].value.length);
 942                 *d++ = ',';
 943         }
 944
 945         *(--d) = '\0';
 946
 947         /* don't waste more memory than necessary */
 948         dn->linearized = talloc_realloc(dn, dn->linearized,
 949                                         char, (d - dn->linearized + 1));
 950
 951         if (extra_prefix) {
 952                 char *old = dn->linearized;
 953                 dn->linearized = talloc_asprintf(dn, "%s%s", extra_prefix, old);
 954                 talloc_free(old);
 955                 talloc_free(extra_prefix);
 956         }
 957
 958         return dn->linearized;
 959 }
 960
 961 char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
 962 {
 963         const char *linearized = ldb_dn_get_linearized(dn);
 964         char *p = NULL;
 965         int i;
 966
 967         if (!linearized) {
 968                 return NULL;
 969         }
 970
 971         if (!ldb_dn_has_extended(dn)) {
 972                 return talloc_strdup(mem_ctx, linearized);
 973         }
 974
 975         if (!ldb_dn_validate(dn)) {
 976                 return NULL;
 977         }
 978
 979         if (dn->extra_type == 'B') {
 980                 char *hexstr = data_blob_hex_string_upper(mem_ctx, &dn->extra_val);
 981                 p = talloc_asprintf(mem_ctx, "B:%u:%s:", (unsigned)(dn->extra_val.length*2), hexstr);
 982                 talloc_free(hexstr);
 983         } else {
 984                 p = talloc_strdup(mem_ctx, "");
 985         }
 986
 987         for (i = 0; i < dn->ext_comp_num; i++) {
 988                 const struct ldb_dn_extended_syntax *ext_syntax;
 989                 const char *name = dn->ext_components[i].name;
 990                 struct ldb_val ec_val = dn->ext_components[i].value;
 991                 struct ldb_val val;
 992                 int ret;
 993
 994                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, name);
 995
 996                 if (mode == 1) {
 997                         ret = ext_syntax->write_clear_fn(dn->ldb, mem_ctx,
 998                                                         &ec_val, &val);
 999                 } else if (mode == 0) {
1000                         ret = ext_syntax->write_hex_fn(dn->ldb, mem_ctx,
1001                                                         &ec_val, &val);
1002                 } else {
1003                         ret = -1;
1004                 }
1005
1006                 if (ret != LDB_SUCCESS) {
1007                         return NULL;
1008                 }
1009
1010                 if (i == 0) {
1011                         p = talloc_asprintf_append_buffer(p, "<%s=%s>", name, val.data);
1012                 } else {
1013                         p = talloc_asprintf_append_buffer(p, ";<%s=%s>",name, val.data);
1014                 }
1015
1016                 talloc_free(val.data);
1017
1018                 if (!p) {
1019                         return NULL;
1020                 }
1021         }
1022
1023         if (dn->ext_comp_num && *linearized) {
1024                 if (strncmp(linearized, "B:", 2) == 0) {
1025                         linearized = strchr(linearized, ':');
1026                         linearized = strchr(linearized+1, ':');
1027                         linearized = strchr(linearized+1, ':');
1028                         linearized++;
1029                 }
1030                 p = talloc_asprintf_append_buffer(p, ";%s", linearized);
1031         }
1032
1033         if (!p) {
1034                 return NULL;
1035         }
1036
1037         return p;
1038 }
1039
1040
1041
1042 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
1043 {
1044         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
1045 }
1046
1047 /*
1048   casefold a dn. We need to casefold the attribute names, and canonicalize
1049   attribute values of case insensitive attributes.
1050 */
1051
1052 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
1053 {
1054         int i, ret;
1055
1056         if ( ! dn || dn->invalid) return false;
1057
1058         if (dn->valid_case) return true;
1059
1060         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
1061                 return false;
1062         }
1063
1064         for (i = 0; i < dn->comp_num; i++) {
1065                 const struct ldb_schema_attribute *a;
1066
1067                 dn->components[i].cf_name =
1068                         ldb_attr_casefold(dn->components,
1069                                           dn->components[i].name);
1070                 if (!dn->components[i].cf_name) {
1071                         goto failed;
1072                 }
1073
1074                 a = ldb_schema_attribute_by_name(dn->ldb,
1075                                                  dn->components[i].cf_name);
1076
1077                 ret = a->syntax->canonicalise_fn(dn->ldb, dn->components,
1078                                                  &(dn->components[i].value),
1079                                                  &(dn->components[i].cf_value));
1080                 if (ret != 0) {
1081                         goto failed;
1082                 }
1083         }
1084
1085         dn->valid_case = true;
1086
1087         return true;
1088
1089 failed:
1090         for (i = 0; i < dn->comp_num; i++) {
1091                 LDB_FREE(dn->components[i].cf_name);
1092                 LDB_FREE(dn->components[i].cf_value.data);
1093         }
1094         return false;
1095 }
1096
1097 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
1098 {
1099         int i, len;
1100         char *d, *n;
1101
1102         if (dn->casefold) return dn->casefold;
1103
1104         if (dn->special) {
1105                 dn->casefold = talloc_strdup(dn, dn->linearized);
1106                 if (!dn->casefold) return NULL;
1107                 dn->valid_case = true;
1108                 return dn->casefold;
1109         }
1110
1111         if ( ! ldb_dn_casefold_internal(dn)) {
1112                 return NULL;
1113         }
1114
1115         if (dn->comp_num == 0) {
1116                 dn->casefold = talloc_strdup(dn, "");
1117                 return dn->casefold;
1118         }
1119
1120         /* calculate maximum possible length of DN */
1121         for (len = 0, i = 0; i < dn->comp_num; i++) {
1122                 /* name len */
1123                 len += strlen(dn->components[i].cf_name);
1124                 /* max escaped data len */
1125                 len += (dn->components[i].cf_value.length * 3);
1126                 len += 2; /* '=' and ',' */
1127         }
1128         dn->casefold = talloc_array(dn, char, len);
1129         if ( ! dn->casefold) return NULL;
1130
1131         d = dn->casefold;
1132
1133         for (i = 0; i < dn->comp_num; i++) {
1134
1135                 /* copy the name */
1136                 n = dn->components[i].cf_name;
1137                 while (*n) *d++ = *n++;
1138
1139                 *d++ = '=';
1140
1141                 /* and the value */
1142                 d += ldb_dn_escape_internal( d,
1143                                 (char *)dn->components[i].cf_value.data,
1144                                 dn->components[i].cf_value.length);
1145                 *d++ = ',';
1146         }
1147         *(--d) = '\0';
1148
1149         /* don't waste more memory than necessary */
1150         dn->casefold = talloc_realloc(dn, dn->casefold,
1151                                       char, strlen(dn->casefold) + 1);
1152
1153         return dn->casefold;
1154 }
1155
1156 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
1157 {
1158         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
1159 }
1160
1161 /* Determine if dn is below base, in the ldap tree.  Used for
1162  * evaluating a subtree search.
1163  * 0 if they match, otherwise non-zero
1164  */
1165
1166 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
1167 {
1168         int ret;
1169         int n_base, n_dn;
1170
1171         if ( ! base || base->invalid) return 1;
1172         if ( ! dn || dn->invalid) return -1;
1173
1174         if (( ! base->valid_case) || ( ! dn->valid_case)) {
1175                 if (base->linearized && dn->linearized) {
1176                         /* try with a normal compare first, if we are lucky
1177                          * we will avoid exploding and casfolding */
1178                         int dif;
1179                         dif = strlen(dn->linearized) - strlen(base->linearized);
1180                         if (dif < 0) {
1181                                 return dif;
1182                         }
1183                         if (strcmp(base->linearized,
1184                                    &dn->linearized[dif]) == 0) {
1185                                 return 0;
1186                         }
1187                 }
1188
1189                 if ( ! ldb_dn_casefold_internal(base)) {
1190                         return 1;
1191                 }
1192
1193                 if ( ! ldb_dn_casefold_internal(dn)) {
1194                         return -1;
1195                 }
1196
1197         }
1198
1199         /* if base has more components,
1200          * they don't have the same base */
1201         if (base->comp_num > dn->comp_num) {
1202                 return (dn->comp_num - base->comp_num);
1203         }
1204
1205         if (dn->comp_num == 0) {
1206                 if (dn->special && base->special) {
1207                         return strcmp(base->linearized, dn->linearized);
1208                 } else if (dn->special) {
1209                         return -1;
1210                 } else if (base->special) {
1211                         return 1;
1212                 } else {
1213                         return 0;
1214                 }
1215         }
1216
1217         n_base = base->comp_num - 1;
1218         n_dn = dn->comp_num - 1;
1219
1220         while (n_base >= 0) {
1221                 char *b_name = base->components[n_base].cf_name;
1222                 char *dn_name = dn->components[n_dn].cf_name;
1223
1224                 char *b_vdata = (char *)base->components[n_base].cf_value.data;
1225                 char *dn_vdata = (char *)dn->components[n_dn].cf_value.data;
1226
1227                 size_t b_vlen = base->components[n_base].cf_value.length;
1228                 size_t dn_vlen = dn->components[n_dn].cf_value.length;
1229
1230                 /* compare attr names */
1231                 ret = strcmp(b_name, dn_name);
1232                 if (ret != 0) return ret;
1233
1234                 /* compare attr.cf_value. */
1235                 if (b_vlen != dn_vlen) {
1236                         return b_vlen - dn_vlen;
1237                 }
1238                 ret = strcmp(b_vdata, dn_vdata);
1239                 if (ret != 0) return ret;
1240
1241                 n_base--;
1242                 n_dn--;
1243         }
1244
1245         return 0;
1246 }
1247
1248 /* compare DNs using casefolding compare functions.
1249
1250    If they match, then return 0
1251  */
1252
1253 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
1254 {
1255         int i, ret;
1256
1257         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) {
1258                 return -1;
1259         }
1260
1261         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
1262                 if (dn0->linearized && dn1->linearized) {
1263                         /* try with a normal compare first, if we are lucky
1264                          * we will avoid exploding and casfolding */
1265                         if (strcmp(dn0->linearized, dn1->linearized) == 0) {
1266                                 return 0;
1267                         }
1268                 }
1269
1270                 if ( ! ldb_dn_casefold_internal(dn0)) {
1271                         return 1;
1272                 }
1273
1274                 if ( ! ldb_dn_casefold_internal(dn1)) {
1275                         return -1;
1276                 }
1277
1278         }
1279
1280         if (dn0->comp_num != dn1->comp_num) {
1281                 return (dn1->comp_num - dn0->comp_num);
1282         }
1283
1284         if (dn0->comp_num == 0) {
1285                 if (dn0->special && dn1->special) {
1286                         return strcmp(dn0->linearized, dn1->linearized);
1287                 } else if (dn0->special) {
1288                         return 1;
1289                 } else if (dn1->special) {
1290                         return -1;
1291                 } else {
1292                         return 0;
1293                 }
1294         }
1295
1296         for (i = 0; i < dn0->comp_num; i++) {
1297                 char *dn0_name = dn0->components[i].cf_name;
1298                 char *dn1_name = dn1->components[i].cf_name;
1299
1300                 char *dn0_vdata = (char *)dn0->components[i].cf_value.data;
1301                 char *dn1_vdata = (char *)dn1->components[i].cf_value.data;
1302
1303                 size_t dn0_vlen = dn0->components[i].cf_value.length;
1304                 size_t dn1_vlen = dn1->components[i].cf_value.length;
1305
1306                 /* compare attr names */
1307                 ret = strcmp(dn0_name, dn1_name);
1308                 if (ret != 0) {
1309                         return ret;
1310                 }
1311
1312                 /* compare attr.cf_value. */
1313                 if (dn0_vlen != dn1_vlen) {
1314                         return dn0_vlen - dn1_vlen;
1315                 }
1316                 ret = strcmp(dn0_vdata, dn1_vdata);
1317                 if (ret != 0) {
1318                         return ret;
1319                 }
1320         }
1321
1322         return 0;
1323 }
1324
1325 static struct ldb_dn_component ldb_dn_copy_component(
1326                                                 void *mem_ctx,
1327                                                 struct ldb_dn_component *src)
1328 {
1329         struct ldb_dn_component dst;
1330
1331         memset(&dst, 0, sizeof(dst));
1332
1333         if (src == NULL) {
1334                 return dst;
1335         }
1336
1337         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1338         if (dst.value.data == NULL) {
1339                 return dst;
1340         }
1341
1342         dst.name = talloc_strdup(mem_ctx, src->name);
1343         if (dst.name == NULL) {
1344                 LDB_FREE(dst.value.data);
1345                 return dst;
1346         }
1347
1348         if (src->cf_value.data) {
1349                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
1350                 if (dst.cf_value.data == NULL) {
1351                         LDB_FREE(dst.value.data);
1352                         LDB_FREE(dst.name);
1353                         return dst;
1354                 }
1355
1356                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
1357                 if (dst.cf_name == NULL) {
1358                         LDB_FREE(dst.cf_name);
1359                         LDB_FREE(dst.value.data);
1360                         LDB_FREE(dst.name);
1361                         return dst;
1362                 }
1363         } else {
1364                 dst.cf_value.data = NULL;
1365                 dst.cf_name = NULL;
1366         }
1367
1368         return dst;
1369 }
1370
1371 static struct ldb_dn_ext_component ldb_dn_ext_copy_component(
1372                                                 void *mem_ctx,
1373                                                 struct ldb_dn_ext_component *src)
1374 {
1375         struct ldb_dn_ext_component dst;
1376
1377         memset(&dst, 0, sizeof(dst));
1378
1379         if (src == NULL) {
1380                 return dst;
1381         }
1382
1383         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1384         if (dst.value.data == NULL) {
1385                 return dst;
1386         }
1387
1388         dst.name = talloc_strdup(mem_ctx, src->name);
1389         if (dst.name == NULL) {
1390                 LDB_FREE(dst.value.data);
1391                 return dst;
1392         }
1393
1394         return dst;
1395 }
1396
1397 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
1398 {
1399         struct ldb_dn *new_dn;
1400
1401         if (!dn || dn->invalid) {
1402                 return NULL;
1403         }
1404
1405         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
1406         if ( !new_dn) {
1407                 return NULL;
1408         }
1409
1410         *new_dn = *dn;
1411
1412         if (dn->components) {
1413                 int i;
1414
1415                 new_dn->components =
1416                         talloc_zero_array(new_dn,
1417                                           struct ldb_dn_component,
1418                                           dn->comp_num);
1419                 if ( ! new_dn->components) {
1420                         talloc_free(new_dn);
1421                         return NULL;
1422                 }
1423
1424                 for (i = 0; i < dn->comp_num; i++) {
1425                         new_dn->components[i] =
1426                                 ldb_dn_copy_component(new_dn->components,
1427                                                       &dn->components[i]);
1428                         if ( ! new_dn->components[i].value.data) {
1429                                 talloc_free(new_dn);
1430                                 return NULL;
1431                         }
1432                 }
1433         }
1434
1435         if (dn->ext_components) {
1436                 int i;
1437
1438                 new_dn->ext_components =
1439                         talloc_zero_array(new_dn,
1440                                           struct ldb_dn_ext_component,
1441                                           dn->ext_comp_num);
1442                 if ( ! new_dn->ext_components) {
1443                         talloc_free(new_dn);
1444                         return NULL;
1445                 }
1446
1447                 for (i = 0; i < dn->ext_comp_num; i++) {
1448                         new_dn->ext_components[i] =
1449                                  ldb_dn_ext_copy_component(
1450                                                 new_dn->ext_components,
1451                                                 &dn->ext_components[i]);
1452                         if ( ! new_dn->ext_components[i].value.data) {
1453                                 talloc_free(new_dn);
1454                                 return NULL;
1455                         }
1456                 }
1457         }
1458
1459         if (dn->casefold) {
1460                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
1461                 if ( ! new_dn->casefold) {
1462                         talloc_free(new_dn);
1463                         return NULL;
1464                 }
1465         }
1466
1467         if (dn->linearized) {
1468                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
1469                 if ( ! new_dn->linearized) {
1470                         talloc_free(new_dn);
1471                         return NULL;
1472                 }
1473         }
1474
1475         if (dn->ext_linearized) {
1476                 new_dn->ext_linearized = talloc_strdup(new_dn,
1477                                                         dn->ext_linearized);
1478                 if ( ! new_dn->ext_linearized) {
1479                         talloc_free(new_dn);
1480                         return NULL;
1481                 }
1482         }
1483
1484         return new_dn;
1485 }
1486
1487 /* modify the given dn by adding a base.
1488  *
1489  * return true if successful and false if not
1490  * if false is returned the dn may be marked invalid
1491  */
1492 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
1493 {
1494         const char *s;
1495         char *t;
1496
1497         if ( !base || base->invalid || !dn || dn->invalid) {
1498                 return false;
1499         }
1500
1501         if (dn->components) {
1502                 int i;
1503
1504                 if ( ! ldb_dn_validate(base)) {
1505                         return false;
1506                 }
1507
1508                 s = NULL;
1509                 if (dn->valid_case) {
1510                         if ( ! (s = ldb_dn_get_casefold(base))) {
1511                                 return false;
1512                         }
1513                 }
1514
1515                 dn->components = talloc_realloc(dn,
1516                                                 dn->components,
1517                                                 struct ldb_dn_component,
1518                                                 dn->comp_num + base->comp_num);
1519                 if ( ! dn->components) {
1520                         ldb_dn_mark_invalid(dn);
1521                         return false;
1522                 }
1523
1524                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
1525                         dn->components[dn->comp_num] =
1526                                 ldb_dn_copy_component(dn->components,
1527                                                         &base->components[i]);
1528                         if (dn->components[dn->comp_num].value.data == NULL) {
1529                                 ldb_dn_mark_invalid(dn);
1530                                 return false;
1531                         }
1532                 }
1533
1534                 if (dn->casefold && s) {
1535                         if (*dn->casefold) {
1536                                 t = talloc_asprintf(dn, "%s,%s",
1537                                                     dn->casefold, s);
1538                         } else {
1539                                 t = talloc_strdup(dn, s);
1540                         }
1541                         LDB_FREE(dn->casefold);
1542                         dn->casefold = t;
1543                 }
1544         }
1545
1546         if (dn->linearized) {
1547
1548                 s = ldb_dn_get_linearized(base);
1549                 if ( ! s) {
1550                         return false;
1551                 }
1552
1553                 if (*dn->linearized) {
1554                         t = talloc_asprintf(dn, "%s,%s",
1555                                             dn->linearized, s);
1556                 } else {
1557                         t = talloc_strdup(dn, s);
1558                 }
1559                 if ( ! t) {
1560                         ldb_dn_mark_invalid(dn);
1561                         return false;
1562                 }
1563                 LDB_FREE(dn->linearized);
1564                 dn->linearized = t;
1565         }
1566
1567         /* Wipe the ext_linearized DN,
1568          * the GUID and SID are almost certainly no longer valid */
1569         if (dn->ext_linearized) {
1570                 LDB_FREE(dn->ext_linearized);
1571         }
1572
1573         LDB_FREE(dn->ext_components);
1574         dn->ext_comp_num = 0;
1575         return true;
1576 }
1577
1578 /* modify the given dn by adding a base.
1579  *
1580  * return true if successful and false if not
1581  * if false is returned the dn may be marked invalid
1582  */
1583 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1584 {
1585         struct ldb_dn *base;
1586         char *base_str;
1587         va_list ap;
1588         bool ret;
1589
1590         if ( !dn || dn->invalid) {
1591                 return false;
1592         }
1593
1594         va_start(ap, base_fmt);
1595         base_str = talloc_vasprintf(dn, base_fmt, ap);
1596         va_end(ap);
1597
1598         if (base_str == NULL) {
1599                 return false;
1600         }
1601
1602         base = ldb_dn_new(base_str, dn->ldb, base_str);
1603
1604         ret = ldb_dn_add_base(dn, base);
1605
1606         talloc_free(base_str);
1607
1608         return ret;
1609 }
1610
1611 /* modify the given dn by adding children elements.
1612  *
1613  * return true if successful and false if not
1614  * if false is returned the dn may be marked invalid
1615  */
1616 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1617 {
1618         const char *s;
1619         char *t;
1620
1621         if ( !child || child->invalid || !dn || dn->invalid) {
1622                 return false;
1623         }
1624
1625         if (dn->components) {
1626                 int n, i, j;
1627
1628                 if ( ! ldb_dn_validate(child)) {
1629                         return false;
1630                 }
1631
1632                 s = NULL;
1633                 if (dn->valid_case) {
1634                         if ( ! (s = ldb_dn_get_casefold(child))) {
1635                                 return false;
1636                         }
1637                 }
1638
1639                 n = dn->comp_num + child->comp_num;
1640
1641                 dn->components = talloc_realloc(dn,
1642                                                 dn->components,
1643                                                 struct ldb_dn_component,
1644                                                 n);
1645                 if ( ! dn->components) {
1646                         ldb_dn_mark_invalid(dn);
1647                         return false;
1648                 }
1649
1650                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1651                         dn->components[j] = dn->components[i];
1652                 }
1653
1654                 for (i = 0; i < child->comp_num; i++) {
1655                         dn->components[i] =
1656                                 ldb_dn_copy_component(dn->components,
1657                                                         &child->components[i]);
1658                         if (dn->components[i].value.data == NULL) {
1659                                 ldb_dn_mark_invalid(dn);
1660                                 return false;
1661                         }
1662                 }
1663
1664                 dn->comp_num = n;
1665
1666                 if (dn->casefold && s) {
1667                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1668                         LDB_FREE(dn->casefold);
1669                         dn->casefold = t;
1670                 }
1671         }
1672
1673         if (dn->linearized) {
1674
1675                 s = ldb_dn_get_linearized(child);
1676                 if ( ! s) {
1677                         return false;
1678                 }
1679
1680                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1681                 if ( ! t) {
1682                         ldb_dn_mark_invalid(dn);
1683                         return false;
1684                 }
1685                 LDB_FREE(dn->linearized);
1686                 dn->linearized = t;
1687         }
1688
1689         /* Wipe the ext_linearized DN,
1690          * the GUID and SID are almost certainly no longer valid */
1691         LDB_FREE(dn->ext_linearized);
1692
1693         LDB_FREE(dn->ext_components);
1694         dn->ext_comp_num = 0;
1695
1696         return true;
1697 }
1698
1699 /* modify the given dn by adding children elements.
1700  *
1701  * return true if successful and false if not
1702  * if false is returned the dn may be marked invalid
1703  */
1704 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1705 {
1706         struct ldb_dn *child;
1707         char *child_str;
1708         va_list ap;
1709         bool ret;
1710
1711         if ( !dn || dn->invalid) {
1712                 return false;
1713         }
1714
1715         va_start(ap, child_fmt);
1716         child_str = talloc_vasprintf(dn, child_fmt, ap);
1717         va_end(ap);
1718
1719         if (child_str == NULL) {
1720                 return false;
1721         }
1722
1723         child = ldb_dn_new(child_str, dn->ldb, child_str);
1724
1725         ret = ldb_dn_add_child(dn, child);
1726
1727         talloc_free(child_str);
1728
1729         return ret;
1730 }
1731
1732 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1733 {
1734         int i;
1735
1736         if ( ! ldb_dn_validate(dn)) {
1737                 return false;
1738         }
1739
1740         if (dn->comp_num < num) {
1741                 return false;
1742         }
1743
1744         /* free components */
1745         for (i = num; i > 0; i--) {
1746                 LDB_FREE(dn->components[dn->comp_num - i].name);
1747                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1748                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1749                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1750         }
1751
1752         dn->comp_num -= num;
1753
1754         if (dn->valid_case) {
1755                 for (i = 0; i < dn->comp_num; i++) {
1756                         LDB_FREE(dn->components[i].cf_name);
1757                         LDB_FREE(dn->components[i].cf_value.data);
1758                 }
1759                 dn->valid_case = false;
1760         }
1761
1762         LDB_FREE(dn->casefold);
1763         LDB_FREE(dn->linearized);
1764
1765         /* Wipe the ext_linearized DN,
1766          * the GUID and SID are almost certainly no longer valid */
1767         LDB_FREE(dn->ext_linearized);
1768
1769         LDB_FREE(dn->ext_components);
1770         dn->ext_comp_num = 0;
1771
1772         return true;
1773 }
1774
1775 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1776 {
1777         int i, j;
1778
1779         if ( ! ldb_dn_validate(dn)) {
1780                 return false;
1781         }
1782
1783         if (dn->comp_num < num) {
1784                 return false;
1785         }
1786
1787         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1788                 if (i < num) {
1789                         LDB_FREE(dn->components[i].name);
1790                         LDB_FREE(dn->components[i].value.data);
1791                         LDB_FREE(dn->components[i].cf_name);
1792                         LDB_FREE(dn->components[i].cf_value.data);
1793                 }
1794                 dn->components[i] = dn->components[j];
1795         }
1796
1797         dn->comp_num -= num;
1798
1799         if (dn->valid_case) {
1800                 for (i = 0; i < dn->comp_num; i++) {
1801                         LDB_FREE(dn->components[i].cf_name);
1802                         LDB_FREE(dn->components[i].cf_value.data);
1803                 }
1804                 dn->valid_case = false;
1805         }
1806
1807         LDB_FREE(dn->casefold);
1808         LDB_FREE(dn->linearized);
1809
1810         /* Wipe the ext_linearized DN,
1811          * the GUID and SID are almost certainly no longer valid */
1812         LDB_FREE(dn->ext_linearized);
1813
1814         LDB_FREE(dn->ext_components);
1815         dn->ext_comp_num = 0;
1816         return true;
1817 }
1818
1819 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1820 {
1821         struct ldb_dn *new_dn;
1822
1823         new_dn = ldb_dn_copy(mem_ctx, dn);
1824         if ( !new_dn ) {
1825                 return NULL;
1826         }
1827
1828         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1829                 talloc_free(new_dn);
1830                 return NULL;
1831         }
1832
1833         /* Wipe the ext_linearized DN,
1834          * the GUID and SID are almost certainly no longer valid */
1835         LDB_FREE(dn->ext_linearized);
1836
1837         LDB_FREE(dn->ext_components);
1838         dn->ext_comp_num = 0;
1839         return new_dn;
1840 }
1841
1842 /* Create a 'canonical name' string from a DN:
1843
1844    ie dc=samba,dc=org -> samba.org/
1845       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1846
1847    There are two formats,
1848    the EX format has the last '/' replaced with a newline (\n).
1849
1850 */
1851 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1852         int i;
1853         TALLOC_CTX *tmpctx;
1854         char *cracked = NULL;
1855         const char *format = (ex_format ? "\n" : "/" );
1856
1857         if ( ! ldb_dn_validate(dn)) {
1858                 return NULL;
1859         }
1860
1861         tmpctx = talloc_new(mem_ctx);
1862
1863         /* Walk backwards down the DN, grabbing 'dc' components at first */
1864         for (i = dn->comp_num - 1 ; i >= 0; i--) {
1865                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1866                         break;
1867                 }
1868                 if (cracked) {
1869                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1870                                                   ldb_dn_escape_value(tmpctx,
1871                                                         dn->components[i].value),
1872                                                   cracked);
1873                 } else {
1874                         cracked = ldb_dn_escape_value(tmpctx,
1875                                                         dn->components[i].value);
1876                 }
1877                 if (!cracked) {
1878                         goto done;
1879                 }
1880         }
1881
1882         /* Only domain components?  Finish here */
1883         if (i < 0) {
1884                 cracked = talloc_strdup_append_buffer(cracked, format);
1885                 talloc_steal(mem_ctx, cracked);
1886                 goto done;
1887         }
1888
1889         /* Now walk backwards appending remaining components */
1890         for (; i > 0; i--) {
1891                 cracked = talloc_asprintf_append_buffer(cracked, "/%s",
1892                                                         ldb_dn_escape_value(tmpctx,
1893                                                         dn->components[i].value));
1894                 if (!cracked) {
1895                         goto done;
1896                 }
1897         }
1898
1899         /* Last one, possibly a newline for the 'ex' format */
1900         cracked = talloc_asprintf_append_buffer(cracked, "%s%s", format,
1901                                                 ldb_dn_escape_value(tmpctx,
1902                                                         dn->components[i].value));
1903
1904         talloc_steal(mem_ctx, cracked);
1905 done:
1906         talloc_free(tmpctx);
1907         return cracked;
1908 }
1909
1910 /* Wrapper functions for the above, for the two different string formats */
1911 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1912         return ldb_dn_canonical(mem_ctx, dn, 0);
1913
1914 }
1915
1916 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1917         return ldb_dn_canonical(mem_ctx, dn, 1);
1918 }
1919
1920 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1921 {
1922         if ( ! ldb_dn_validate(dn)) {
1923                 return -1;
1924         }
1925         return dn->comp_num;
1926 }
1927
1928 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1929 {
1930         if ( ! ldb_dn_validate(dn)) {
1931                 return NULL;
1932         }
1933         if (num >= dn->comp_num) return NULL;
1934         return dn->components[num].name;
1935 }
1936
1937 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn,
1938                                                 unsigned int num)
1939 {
1940         if ( ! ldb_dn_validate(dn)) {
1941                 return NULL;
1942         }
1943         if (num >= dn->comp_num) return NULL;
1944         return &dn->components[num].value;
1945 }
1946
1947 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1948 {
1949         if ( ! ldb_dn_validate(dn)) {
1950                 return NULL;
1951         }
1952         if (dn->comp_num == 0) return NULL;
1953         return dn->components[0].name;
1954 }
1955
1956 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1957 {
1958         if ( ! ldb_dn_validate(dn)) {
1959                 return NULL;
1960         }
1961         if (dn->comp_num == 0) return NULL;
1962         return &dn->components[0].value;
1963 }
1964
1965 int ldb_dn_set_component(struct ldb_dn *dn, int num,
1966                          const char *name, const struct ldb_val val)
1967 {
1968         char *n;
1969         struct ldb_val v;
1970
1971         if ( ! ldb_dn_validate(dn)) {
1972                 return LDB_ERR_OTHER;
1973         }
1974
1975         if (num >= dn->comp_num) {
1976                 return LDB_ERR_OTHER;
1977         }
1978
1979         n = talloc_strdup(dn, name);
1980         if ( ! n) {
1981                 return LDB_ERR_OTHER;
1982         }
1983
1984         v.length = val.length;
1985         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1986         if ( ! v.data) {
1987                 talloc_free(n);
1988                 return LDB_ERR_OTHER;
1989         }
1990
1991         talloc_free(dn->components[num].name);
1992         talloc_free(dn->components[num].value.data);
1993         dn->components[num].name = n;
1994         dn->components[num].value = v;
1995
1996         if (dn->valid_case) {
1997                 int i;
1998                 for (i = 0; i < dn->comp_num; i++) {
1999                         LDB_FREE(dn->components[i].cf_name);
2000                         LDB_FREE(dn->components[i].cf_value.data);
2001                 }
2002                 dn->valid_case = false;
2003         }
2004         LDB_FREE(dn->casefold);
2005         LDB_FREE(dn->linearized);
2006
2007         /* Wipe the ext_linearized DN,
2008          * the GUID and SID are almost certainly no longer valid */
2009         LDB_FREE(dn->ext_linearized);
2010
2011         dn->ext_comp_num = 0;
2012         LDB_FREE(dn->ext_components);
2013         return LDB_SUCCESS;
2014 }
2015
2016 const struct ldb_val *ldb_dn_get_extended_component(struct ldb_dn *dn,
2017                                                     const char *name)
2018 {
2019         int i;
2020         if ( ! ldb_dn_validate(dn)) {
2021                 return NULL;
2022         }
2023         for (i=0; i < dn->ext_comp_num; i++) {
2024                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
2025                         return &dn->ext_components[i].value;
2026                 }
2027         }
2028         return NULL;
2029 }
2030
2031 int ldb_dn_set_extended_component(struct ldb_dn *dn,
2032                                   const char *name, const struct ldb_val *val)
2033 {
2034         struct ldb_dn_ext_component *p;
2035         int i;
2036
2037         if ( ! ldb_dn_validate(dn)) {
2038                 return LDB_ERR_OTHER;
2039         }
2040
2041         for (i=0; i < dn->ext_comp_num; i++) {
2042                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
2043                         if (val) {
2044                                 dn->ext_components[i].value =
2045                                         ldb_val_dup(dn->ext_components, val);
2046
2047                                 dn->ext_components[i].name =
2048                                         talloc_strdup(dn->ext_components, name);
2049                                 if (!dn->ext_components[i].name ||
2050                                     !dn->ext_components[i].value.data) {
2051                                         ldb_dn_mark_invalid(dn);
2052                                         return LDB_ERR_OPERATIONS_ERROR;
2053                                 }
2054
2055                         } else {
2056                                 if (i != (dn->ext_comp_num - 1)) {
2057                                         memmove(&dn->ext_components[i],
2058                                                 &dn->ext_components[i+1],
2059                                                 ((dn->ext_comp_num-1) - i) *
2060                                                   sizeof(*dn->ext_components));
2061                                 }
2062                                 dn->ext_comp_num--;
2063
2064                                 dn->ext_components = talloc_realloc(dn,
2065                                                    dn->ext_components,
2066                                                    struct ldb_dn_ext_component,
2067                                                    dn->ext_comp_num);
2068                                 if (!dn->ext_components) {
2069                                         ldb_dn_mark_invalid(dn);
2070                                         return LDB_ERR_OPERATIONS_ERROR;
2071                                 }
2072                                 return LDB_SUCCESS;
2073                         }
2074                 }
2075         }
2076
2077         p = dn->ext_components
2078                 = talloc_realloc(dn,
2079                                  dn->ext_components,
2080                                  struct ldb_dn_ext_component,
2081                                  dn->ext_comp_num + 1);
2082         if (!dn->ext_components) {
2083                 ldb_dn_mark_invalid(dn);
2084                 return LDB_ERR_OPERATIONS_ERROR;
2085         }
2086
2087         p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, val);
2088         p[dn->ext_comp_num].name = talloc_strdup(p, name);
2089
2090         if (!dn->ext_components[i].name || !dn->ext_components[i].value.data) {
2091                 ldb_dn_mark_invalid(dn);
2092                 return LDB_ERR_OPERATIONS_ERROR;
2093         }
2094         dn->ext_components = p;
2095         dn->ext_comp_num++;
2096
2097         return LDB_SUCCESS;
2098 }
2099
2100 void ldb_dn_remove_extended_components(struct ldb_dn *dn)
2101 {
2102         dn->ext_comp_num = 0;
2103         LDB_FREE(dn->ext_components);
2104 }
2105
2106 bool ldb_dn_is_valid(struct ldb_dn *dn)
2107 {
2108         if ( ! dn) return false;
2109         return ! dn->invalid;
2110 }
2111
2112 bool ldb_dn_is_special(struct ldb_dn *dn)
2113 {
2114         if ( ! dn || dn->invalid) return false;
2115         return dn->special;
2116 }
2117
2118 bool ldb_dn_has_extended(struct ldb_dn *dn)
2119 {
2120         if ( ! dn || dn->invalid) return false;
2121         if (dn->ext_linearized && strchr(dn->ext_linearized,'<')) return true;
2122         return dn->ext_comp_num != 0;
2123 }
2124
2125 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
2126 {
2127         if ( ! dn || dn->invalid) return false;
2128         return ! strcmp(dn->linearized, check);
2129 }
2130
2131 bool ldb_dn_is_null(struct ldb_dn *dn)
2132 {
2133         if ( ! dn || dn->invalid) return false;
2134         if (ldb_dn_has_extended(dn)) return false;
2135         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
2136         return false;
2137 }
2138
2139 int ldb_dn_get_binary(struct ldb_dn *dn, struct ldb_val *val)
2140 {
2141         ZERO_STRUCTP(val);
2142         if (dn->extra_type != 'B') {
2143                 return LDB_SUCCESS;
2144         }
2145         *val = dn->extra_val;
2146         return LDB_SUCCESS;
2147 }
2148
2149 int ldb_dn_set_binary(struct ldb_dn *dn, struct ldb_val *val)
2150 {
2151         dn->extra_type = 'B';
2152         dn->extra_val.data = talloc_memdup(dn, val->data, val->length);
2153         dn->extra_val.length = val->length;
2154
2155         talloc_free(dn->linearized);
2156         talloc_free(dn->ext_linearized);
2157         dn->linearized = NULL;
2158         dn->ext_linearized = NULL;
2159         return LDB_SUCCESS;
2160 }