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