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