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, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: ldb dn creation and manipulation utility functions
  29  *
  30  *  Description: - explode a dn into it's own basic elements
  31  *                 and put them in a structure (only if necessary)
  32  *               - manipulate ldb_dn structures
  33  *
  34  *  Author: Simo Sorce
  35  */
  36
  37 #include "ldb_includes.h"
  38 #include <ctype.h>
  39
  40 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  41
  42 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
  43
  44 /**
  45    internal ldb exploded dn structures
  46 */
  47 struct ldb_dn_component {
  48
  49         char *name;
  50         struct ldb_val value;
  51
  52         char *cf_name;
  53         struct ldb_val cf_value;
  54 };
  55
  56 struct ldb_dn {
  57
  58         struct ldb_context *ldb;
  59
  60         /* Special DNs are always linearized */
  61         bool special;
  62         bool invalid;
  63
  64         bool valid_case;
  65
  66         char *linearized;
  67         char *casefold;
  68
  69         unsigned int comp_num;
  70         struct ldb_dn_component *components;
  71
  72 };
  73
  74 /* strdn may be NULL */
  75 struct ldb_dn *ldb_dn_new(void *mem_ctx, struct ldb_context *ldb, const char *strdn)
  76 {
  77         struct ldb_dn *dn;
  78
  79         if ( (! mem_ctx) || (! ldb)) return NULL;
  80
  81         dn = talloc_zero(mem_ctx, struct ldb_dn);
  82         LDB_DN_NULL_FAILED(dn);
  83
  84         dn->ldb = ldb;
  85
  86         if (strdn) {
  87                 if (strdn[0] == '@') {
  88                         dn->special = true;
  89                 }
  90                 if (strncasecmp(strdn, "<GUID=", 6) == 0) {
  91                         /* this is special DN returned when the
  92                          * exploded_dn control is used */
  93                         dn->special = true;
  94                         /* FIXME: add a GUID string to ldb_dn structure */
  95                 } else if (strncasecmp(strdn, "<SID=", 8) == 0) {
  96                         /* this is special DN returned when the
  97                          * exploded_dn control is used */
  98                         dn->special = true;
  99                         /* FIXME: add a SID string to ldb_dn structure */
 100                 } else if (strncasecmp(strdn, "<WKGUID=", 8) == 0) {
 101                         /* this is special DN returned when the
 102                          * exploded_dn control is used */
 103                         dn->special = true;
 104                         /* FIXME: add a WKGUID string to ldb_dn structure */
 105                 }
 106                 dn->linearized = talloc_strdup(dn, strdn);
 107         } else {
 108                 dn->linearized = talloc_strdup(dn, "");
 109         }
 110         LDB_DN_NULL_FAILED(dn->linearized);
 111
 112         return dn;
 113
 114 failed:
 115         talloc_free(dn);
 116         return NULL;
 117 }
 118
 119 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx, struct ldb_context *ldb, const char *new_fmt, ...)
 120 {
 121         struct ldb_dn *dn;
 122         char *strdn;
 123         va_list ap;
 124
 125         if ( (! mem_ctx) || (! ldb)) return NULL;
 126
 127         dn = talloc_zero(mem_ctx, struct ldb_dn);
 128         LDB_DN_NULL_FAILED(dn);
 129
 130         dn->ldb = ldb;
 131
 132         va_start(ap, new_fmt);
 133         strdn = talloc_vasprintf(dn, new_fmt, ap);
 134         va_end(ap);
 135         LDB_DN_NULL_FAILED(strdn);
 136
 137         if (strdn[0] == '@') {
 138                 dn->special = true;
 139         }
 140         if (strncasecmp(strdn, "<GUID=", 6) == 0) {
 141                 /* this is special DN returned when the
 142                  * exploded_dn control is used */
 143                 dn->special = true;
 144                 /* FIXME: add a GUID string to ldb_dn structure */
 145         } else if (strncasecmp(strdn, "<SID=", 8) == 0) {
 146                 /* this is special DN returned when the
 147                  * exploded_dn control is used */
 148                 dn->special = true;
 149                 /* FIXME: add a SID string to ldb_dn structure */
 150         } else if (strncasecmp(strdn, "<WKGUID=", 8) == 0) {
 151                 /* this is special DN returned when the
 152                  * exploded_dn control is used */
 153                 dn->special = true;
 154                 /* FIXME: add a WKGUID string to ldb_dn structure */
 155         }
 156         dn->linearized = strdn;
 157
 158         return dn;
 159
 160 failed:
 161         talloc_free(dn);
 162         return NULL;
 163 }
 164
 165 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 166 {
 167         const char *p, *s;
 168         char *d;
 169         int l;
 170
 171         p = s = src;
 172         d = dst;
 173
 174         while (p - src < len) {
 175
 176                 p += strcspn(p, ",=\n+<>#;\\\"");
 177
 178                 if (p - src == len) /* found no escapable chars */
 179                         break;
 180
 181                 memcpy(d, s, p - s); /* copy the part of the string before the stop */
 182                 d += (p - s); /* move to current position */
 183
 184                 if (*p) { /* it is a normal escapable character */
 185                         *d++ = '\\';
 186                         *d++ = *p++;
 187                 } else { /* we have a zero byte in the string */
 188                         strncpy(d, "\00", 3); /* escape the zero */
 189                         d += 3;
 190                         p++; /* skip the zero */
 191                 }
 192                 s = p; /* move forward */
 193         }
 194
 195         /* copy the last part (with zero) and return */
 196         l = len - (s - src);
 197         memcpy(d, s, l + 1);
 198
 199         /* return the length of the resulting string */
 200         return (l + (d - dst));
 201 }
 202
 203 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 204 {
 205         char *dst;
 206
 207         if (!value.length)
 208                 return NULL;
 209
 210         /* allocate destination string, it will be at most 3 times the source */
 211         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 212         if ( ! dst) {
 213                 talloc_free(dst);
 214                 return NULL;
 215         }
 216
 217         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 218
 219         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
 220
 221         return dst;
 222 }
 223
 224 /*
 225   explode a DN string into a ldb_dn structure
 226   based on RFC4514 except that we don't support multiple valued RDNs
 227 */
 228 static bool ldb_dn_explode(struct ldb_dn *dn)
 229 {
 230         char *p, *data, *d, *dt, *t;
 231         bool trim = false;
 232         bool in_attr = false;
 233         bool in_value = false;
 234         bool in_quote = false;
 235         bool is_oid = false;
 236         bool escape = false;
 237         unsigned x;
 238         int l;
 239
 240         if ( ! dn || dn->invalid) return false;
 241
 242         if (dn->components) {
 243                 return true;
 244         }
 245
 246         if ( ! dn->linearized) {
 247                 return false;
 248         }
 249
 250         /* Empty DNs */
 251         if (dn->linearized[0] == '\0') {
 252                 return true;
 253         }
 254
 255         /* Special DNs case */
 256         if (dn->special) {
 257                 return true;
 258         }
 259
 260         /* make sure we free this if alloced previously before replacing */
 261         talloc_free(dn->components);
 262
 263         /* in the common case we have 3 or more components */
 264         /* make sure all components are zeroed, other functions depend on this */
 265         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 266         if ( ! dn->components) {
 267                 return false;
 268         }
 269         dn->comp_num = 0;
 270
 271         /* Components data space is allocated here once */
 272         data = talloc_array(dn->components, char, strlen(dn->linearized) + 1);
 273         if (!data) {
 274                 return false;
 275         }
 276
 277         p = dn->linearized;
 278         in_attr = true;
 279         trim = true;
 280         t = NULL;
 281         d = dt = data;
 282
 283         while (*p) {
 284
 285                 if (in_attr) {
 286                         if (trim) {
 287                                 if (*p == ' ') {
 288                                         p++;
 289                                         continue;
 290                                 }
 291
 292                                 /* first char */
 293                                 trim = false;
 294
 295                                 if (!isascii(*p)) {
 296                                         /* attr names must be ascii only */
 297                                         dn->invalid = true;
 298                                         goto failed;
 299                                 }
 300
 301                                 if (isdigit(*p)) {
 302                                         is_oid = true;
 303                                 } else
 304                                 if ( ! isalpha(*p)) {
 305                                         /* not a digit nor an alpha, invalid attribute name */
 306                                         dn->invalid = true;
 307                                         goto failed;
 308                                 }
 309
 310                                 *d++ = *p++;
 311                                 continue;
 312                         }
 313
 314                         if (*p == ' ') {
 315                                 p++;
 316                                 /* valid only if we are at the end */
 317                                 trim = true;
 318                                 continue;
 319                         }
 320
 321                         if (trim && (*p != '=')) {
 322                                 /* spaces/tabs are not allowed in attribute names */
 323                                 dn->invalid = true;
 324                                 goto failed;
 325                         }
 326
 327                         if (*p == '=') {
 328                                 /* attribute terminated */
 329                                 in_attr = false;
 330                                 in_value = true;
 331                                 trim = true;
 332                                 l = 0;
 333
 334                                 *d++ = '\0';
 335                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 336                                 if ( ! dn->components[dn->comp_num].name) {
 337                                         /* ouch */
 338                                         goto failed;
 339                                 }
 340
 341                                 dt = d;
 342
 343                                 p++;
 344                                 continue;
 345                         }
 346
 347                         if (!isascii(*p)) {
 348                                 /* attr names must be ascii only */
 349                                 dn->invalid = true;
 350                                 goto failed;
 351                         }
 352
 353                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 354                                 /* not a digit nor a dot, invalid attribute oid */
 355                                 dn->invalid = true;
 356                                 goto failed;
 357                         } else
 358                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 359                                 /* not ALPHA, DIGIT or HYPHEN */
 360                                 dn->invalid = true;
 361                                 goto failed;
 362                         }
 363
 364                         *d++ = *p++;
 365                         continue;
 366                 }
 367
 368                 if (in_value) {
 369                         if (in_quote) {
 370                                 if (*p == '\"') {
 371                                         if (p[-1] != '\\') {
 372                                                 p++;
 373                                                 in_quote = false;
 374                                                 continue;
 375                                         }
 376                                 }
 377                                 *d++ = *p++;
 378                                 l++;
 379                                 continue;
 380                         }
 381
 382                         if (trim) {
 383                                 if (*p == ' ') {
 384                                         p++;
 385                                         continue;
 386                                 }
 387
 388                                 /* first char */
 389                                 trim = false;
 390
 391                                 if (*p == '\"') {
 392                                         in_quote = true;
 393                                         p++;
 394                                         continue;
 395                                 }
 396                         }
 397
 398                         switch (*p) {
 399
 400                         /* TODO: support ber encoded values
 401                         case '#':
 402                         */
 403
 404                         case ',':
 405                                 if (escape) {
 406                                         *d++ = *p++;
 407                                         l++;
 408                                         escape = false;
 409                                         continue;
 410                                 }
 411                                 /* ok found value terminator */
 412
 413                                 if ( t ) {
 414                                         /* trim back */
 415                                         d -= (p - t);
 416                                         l -= (p - t);
 417                                 }
 418
 419                                 in_attr = true;
 420                                 in_value = false;
 421                                 trim = true;
 422
 423                                 p++;
 424                                 *d++ = '\0';
 425                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 426                                 dn->components[dn->comp_num].value.length = l;
 427                                 if ( ! dn->components[dn->comp_num].value.data) {
 428                                         /* ouch ! */
 429                                         goto failed;
 430                                 }
 431
 432                                 dt = d;
 433
 434                                 dn->comp_num++;
 435                                 if (dn->comp_num > 2) {
 436                                         dn->components = talloc_realloc(dn,
 437                                                                         dn->components,
 438                                                                         struct ldb_dn_component,
 439                                                                         dn->comp_num + 1);
 440                                         if ( ! dn->components) {
 441                                                 /* ouch ! */
 442                                                 goto failed;
 443                                         }
 444                                         /* make sure all components are zeroed, other functions depend on this */
 445                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 446                                 }
 447
 448                                 continue;
 449
 450                         case '=':
 451                         case '\n':
 452                         case '+':
 453                         case '<':
 454                         case '>':
 455                         case '#':
 456                         case ';':
 457                         case '\"':
 458                                 /* a string with not escaped specials is invalid (tested) */
 459                                 if ( ! escape) {
 460                                         dn->invalid = true;
 461                                         goto failed;
 462                                 }
 463                                 escape = false;
 464
 465                                 *d++ = *p++;
 466                                 l++;
 467
 468                                 if ( t ) t = NULL;
 469                                 break;
 470
 471                         case '\\':
 472                                 if ( ! escape) {
 473                                         escape = true;
 474                                         p++;
 475                                         continue;
 476                                 }
 477                                 escape = false;
 478
 479                                 *d++ = *p++;
 480                                 l++;
 481
 482                                 if ( t ) t = NULL;
 483                                 break;
 484
 485                         default:
 486                                 if (escape) {
 487                                         if (sscanf(p, "%02x", &x) != 1) {
 488                                                 /* invalid escaping sequence */
 489                                                 dn->invalid = true;
 490                                                 goto failed;
 491                                         }
 492                                         escape = false;
 493
 494                                         p += 2;
 495                                         *d++ = (unsigned char)x;
 496                                         l++;
 497
 498                                         if ( t ) t = NULL;
 499                                         break;
 500                                 }
 501
 502                                 if (*p == ' ') {
 503                                         if ( ! t) t = p;
 504                                 } else {
 505                                         if ( t ) t = NULL;
 506                                 }
 507
 508                                 *d++ = *p++;
 509                                 l++;
 510
 511                                 break;
 512                         }
 513
 514                 }
 515         }
 516
 517         if (in_attr || in_quote) {
 518                 /* invalid dn */
 519                 dn->invalid = true;
 520                 goto failed;
 521         }
 522
 523         /* save last element */
 524         if ( t ) {
 525                 /* trim back */
 526                 d -= (p - t);
 527                 l -= (p - t);
 528         }
 529
 530         *d++ = '\0';
 531         dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 532         dn->components[dn->comp_num].value.length = l;
 533
 534         if ( ! dn->components[dn->comp_num].value.data) {
 535                 /* ouch */
 536                 goto failed;
 537         }
 538
 539         dn->comp_num++;
 540
 541         talloc_free(data);
 542         return true;
 543
 544 failed:
 545         dn->comp_num = 0;
 546         talloc_free(dn->components);
 547         return false;
 548 }
 549
 550 bool ldb_dn_validate(struct ldb_dn *dn)
 551 {
 552         return ldb_dn_explode(dn);
 553 }
 554
 555 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 556 {
 557         int i, len;
 558         char *d, *n;
 559
 560         if ( ! dn || ( dn->invalid)) return NULL;
 561
 562         if (dn->linearized) return dn->linearized;
 563
 564         if ( ! dn->components) {
 565                 dn->invalid = true;
 566                 return NULL;
 567         }
 568
 569         if (dn->comp_num == 0) {
 570                 dn->linearized = talloc_strdup(dn, "");
 571                 if ( ! dn->linearized) return NULL;
 572                 return dn->linearized;
 573         }
 574
 575         /* calculate maximum possible length of DN */
 576         for (len = 0, i = 0; i < dn->comp_num; i++) {
 577                 len += strlen(dn->components[i].name); /* name len */
 578                 len += (dn->components[i].value.length * 3); /* max escaped data len */
 579                 len += 2; /* '=' and ',' */
 580         }
 581         dn->linearized = talloc_array(dn, char, len);
 582         if ( ! dn->linearized) return NULL;
 583
 584         d = dn->linearized;
 585
 586         for (i = 0; i < dn->comp_num; i++) {
 587
 588                 /* copy the name */
 589                 n = dn->components[i].name;
 590                 while (*n) *d++ = *n++;
 591
 592                 *d++ = '=';
 593
 594                 /* and the value */
 595                 d += ldb_dn_escape_internal( d,
 596                                 (char *)dn->components[i].value.data,
 597                                 dn->components[i].value.length);
 598                 *d++ = ',';
 599         }
 600
 601         *(--d) = '\0';
 602
 603         /* don't waste more memory than necessary */
 604         dn->linearized = talloc_realloc(dn, dn->linearized, char, (d - dn->linearized + 1));
 605
 606         return dn->linearized;
 607 }
 608
 609 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
 610 {
 611         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 612 }
 613
 614 /*
 615   casefold a dn. We need to casefold the attribute names, and canonicalize
 616   attribute values of case insensitive attributes.
 617 */
 618
 619 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 620 {
 621         int i, ret;
 622
 623         if ( ! dn || dn->invalid) return false;
 624
 625         if (dn->valid_case) return true;
 626
 627         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
 628                 return false;
 629         }
 630
 631         for (i = 0; i < dn->comp_num; i++) {
 632                 const struct ldb_schema_attribute *a;
 633
 634                 dn->components[i].cf_name = ldb_attr_casefold(dn->components, dn->components[i].name);
 635                 if (!dn->components[i].cf_name) {
 636                         goto failed;
 637                 }
 638
 639                 a = ldb_schema_attribute_by_name(dn->ldb, dn->components[i].cf_name);
 640                 ret = a->syntax->canonicalise_fn(dn->ldb, dn->components,
 641                                                  &(dn->components[i].value),
 642                                                  &(dn->components[i].cf_value));
 643                 if (ret != 0) {
 644                         goto failed;
 645                 }
 646         }
 647
 648         dn->valid_case = true;
 649
 650         return true;
 651
 652 failed:
 653         for (i = 0; i < dn->comp_num; i++) {
 654                 LDB_FREE(dn->components[i].cf_name);
 655                 LDB_FREE(dn->components[i].cf_value.data);
 656         }
 657         return false;
 658 }
 659
 660 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 661 {
 662         int i, len;
 663         char *d, *n;
 664
 665         if (dn->casefold) return dn->casefold;
 666
 667         if (dn->special) {
 668                 dn->casefold = talloc_strdup(dn, dn->linearized);
 669                 if (!dn->casefold) return NULL;
 670                 dn->valid_case = true;
 671                 return dn->casefold;
 672         }
 673
 674         if ( ! ldb_dn_casefold_internal(dn)) {
 675                 return NULL;
 676         }
 677
 678         if (dn->comp_num == 0) {
 679                 if (dn->linearized && dn->linearized[0] == '\0') {
 680                         /* hmm a NULL dn, should we faild casefolding ? */
 681                         dn->casefold = talloc_strdup(dn, "");
 682                         return dn->casefold;
 683                 }
 684                 /* A DN must be NULL, special, or have components */
 685                 dn->invalid = true;
 686                 return NULL;
 687         }
 688
 689         /* calculate maximum possible length of DN */
 690         for (len = 0, i = 0; i < dn->comp_num; i++) {
 691                 len += strlen(dn->components[i].cf_name); /* name len */
 692                 len += (dn->components[i].cf_value.length * 3); /* max escaped data len */
 693                 len += 2; /* '=' and ',' */
 694         }
 695         dn->casefold = talloc_array(dn, char, len);
 696         if ( ! dn->casefold) return NULL;
 697
 698         d = dn->casefold;
 699
 700         for (i = 0; i < dn->comp_num; i++) {
 701
 702                 /* copy the name */
 703                 n = dn->components[i].cf_name;
 704                 while (*n) *d++ = *n++;
 705
 706                 *d++ = '=';
 707
 708                 /* and the value */
 709                 d += ldb_dn_escape_internal( d,
 710                                 (char *)dn->components[i].cf_value.data,
 711                                 dn->components[i].cf_value.length);
 712                 *d++ = ',';
 713         }
 714         *(--d) = '\0';
 715
 716         /* don't waste more memory than necessary */
 717         dn->casefold = talloc_realloc(dn, dn->casefold, char, strlen(dn->casefold) + 1);
 718
 719         return dn->casefold;
 720 }
 721
 722 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
 723 {
 724         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
 725 }
 726
 727 /* Determine if dn is below base, in the ldap tree.  Used for
 728  * evaluating a subtree search.
 729  * 0 if they match, otherwise non-zero
 730  */
 731
 732 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
 733 {
 734         int ret;
 735         int n_base, n_dn;
 736
 737         if ( ! base || base->invalid) return 1;
 738         if ( ! dn || dn->invalid) return -1;
 739
 740         if (( ! base->valid_case) || ( ! dn->valid_case)) {
 741                 if (base->linearized && dn->linearized) {
 742                         /* try with a normal compare first, if we are lucky
 743                          * we will avoid exploding and casfolding */
 744                         int dif;
 745                         dif = strlen(dn->linearized) - strlen(base->linearized);
 746                         if (dif < 0) return dif;
 747                         if (strcmp(base->linearized, &dn->linearized[dif]) == 0) return 0;
 748                 }
 749
 750                 if ( ! ldb_dn_casefold_internal(base)) {
 751                         return 1;
 752                 }
 753
 754                 if ( ! ldb_dn_casefold_internal(dn)) {
 755                         return -1;
 756                 }
 757
 758         }
 759
 760         /* if base has more components,
 761          * they don't have the same base */
 762         if (base->comp_num > dn->comp_num) {
 763                 return (dn->comp_num - base->comp_num);
 764         }
 765
 766         if (dn->comp_num == 0) {
 767                 if (dn->special && base->special) {
 768                         return strcmp(base->linearized, dn->linearized);
 769                 } else if (dn->special) {
 770                         return -1;
 771                 } else if (base->special) {
 772                         return 1;
 773                 } else {
 774                         return 0;
 775                 }
 776         }
 777
 778         n_base = base->comp_num - 1;
 779         n_dn = dn->comp_num - 1;
 780
 781         while (n_base >= 0) {
 782                 /* compare attr names */
 783                 ret = strcmp(base->components[n_base].cf_name, dn->components[n_dn].cf_name);
 784                 if (ret != 0) return ret;
 785
 786                 /* compare attr.cf_value. */
 787                 if (base->components[n_base].cf_value.length != dn->components[n_dn].cf_value.length) {
 788                         return base->components[n_base].cf_value.length - dn->components[n_dn].cf_value.length;
 789                 }
 790                 ret = strcmp((char *)base->components[n_base].cf_value.data, (char *)dn->components[n_dn].cf_value.data);
 791                 if (ret != 0) return ret;
 792
 793                 n_base--;
 794                 n_dn--;
 795         }
 796
 797         return 0;
 798 }
 799
 800 /* compare DNs using casefolding compare functions.
 801
 802    If they match, then return 0
 803  */
 804
 805 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 806 {
 807         int i, ret;
 808
 809         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) return -1;
 810
 811         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
 812                 if (dn0->linearized && dn1->linearized) {
 813                         /* try with a normal compare first, if we are lucky
 814                          * we will avoid exploding and casfolding */
 815                         if (strcmp(dn0->linearized, dn1->linearized) == 0) return 0;
 816                 }
 817
 818                 if ( ! ldb_dn_casefold_internal(dn0)) {
 819                         return 1;
 820                 }
 821
 822                 if ( ! ldb_dn_casefold_internal(dn1)) {
 823                         return -1;
 824                 }
 825
 826         }
 827
 828         if (dn0->comp_num != dn1->comp_num) {
 829                 return (dn1->comp_num - dn0->comp_num);
 830         }
 831
 832         if (dn0->comp_num == 0) {
 833                 if (dn0->special && dn1->special) {
 834                         return strcmp(dn0->linearized, dn1->linearized);
 835                 } else if (dn0->special) {
 836                         return 1;
 837                 } else if (dn1->special) {
 838                         return -1;
 839                 } else {
 840                         return 0;
 841                 }
 842         }
 843
 844         for (i = 0; i < dn0->comp_num; i++) {
 845                 /* compare attr names */
 846                 ret = strcmp(dn0->components[i].cf_name, dn1->components[i].cf_name);
 847                 if (ret != 0) return ret;
 848
 849                 /* compare attr.cf_value. */
 850                 if (dn0->components[i].cf_value.length != dn1->components[i].cf_value.length) {
 851                         return dn0->components[i].cf_value.length - dn1->components[i].cf_value.length;
 852                 }
 853                 ret = strcmp((char *)dn0->components[i].cf_value.data, (char *)dn1->components[i].cf_value.data);
 854                 if (ret != 0) return ret;
 855         }
 856
 857         return 0;
 858 }
 859
 860 static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
 861 {
 862         struct ldb_dn_component dst;
 863
 864         memset(&dst, 0, sizeof(dst));
 865
 866         if (src == NULL) {
 867                 return dst;
 868         }
 869
 870         dst.value = ldb_val_dup(mem_ctx, &(src->value));
 871         if (dst.value.data == NULL) {
 872                 return dst;
 873         }
 874
 875         dst.name = talloc_strdup(mem_ctx, src->name);
 876         if (dst.name == NULL) {
 877                 LDB_FREE(dst.value.data);
 878                 return dst;
 879         }
 880
 881         if (src->cf_value.data) {
 882                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
 883                 if (dst.cf_value.data == NULL) {
 884                         LDB_FREE(dst.value.data);
 885                         LDB_FREE(dst.name);
 886                         return dst;
 887                 }
 888
 889                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
 890                 if (dst.cf_name == NULL) {
 891                         LDB_FREE(dst.cf_name);
 892                         LDB_FREE(dst.value.data);
 893                         LDB_FREE(dst.name);
 894                         return dst;
 895                 }
 896         } else {
 897                 dst.cf_value.data = NULL;
 898                 dst.cf_name = NULL;
 899         }
 900
 901         return dst;
 902 }
 903
 904 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
 905 {
 906         struct ldb_dn *new_dn;
 907
 908         if (!dn || dn->invalid) {
 909                 return NULL;
 910         }
 911
 912         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
 913         if ( !new_dn) {
 914                 return NULL;
 915         }
 916
 917         *new_dn = *dn;
 918
 919         if (dn->components) {
 920                 int i;
 921
 922                 new_dn->components = talloc_zero_array(new_dn, struct ldb_dn_component, dn->comp_num);
 923                 if ( ! new_dn->components) {
 924                         talloc_free(new_dn);
 925                         return NULL;
 926                 }
 927
 928                 for (i = 0; i < dn->comp_num; i++) {
 929                         new_dn->components[i] = ldb_dn_copy_component(new_dn->components, &dn->components[i]);
 930                         if ( ! new_dn->components[i].value.data) {
 931                                 talloc_free(new_dn);
 932                                 return NULL;
 933                         }
 934                 }
 935         }
 936
 937         if (dn->casefold) {
 938                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
 939                 if ( ! new_dn->casefold) {
 940                         talloc_free(new_dn);
 941                         return NULL;
 942                 }
 943         }
 944
 945         if (dn->linearized) {
 946                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
 947                 if ( ! new_dn->linearized) {
 948                         talloc_free(new_dn);
 949                         return NULL;
 950                 }
 951         }
 952
 953         return new_dn;
 954 }
 955
 956 /* modify the given dn by adding a base.
 957  *
 958  * return true if successful and false if not
 959  * if false is returned the dn may be marked invalid
 960  */
 961 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
 962 {
 963         const char *s;
 964         char *t;
 965
 966         if ( !base || base->invalid || !dn || dn->invalid) {
 967                 return false;
 968         }
 969
 970         if (dn->components) {
 971                 int i;
 972
 973                 if ( ! ldb_dn_validate(base)) {
 974                         return false;
 975                 }
 976
 977                 s = NULL;
 978                 if (dn->valid_case) {
 979                         if ( ! (s = ldb_dn_get_casefold(base))) {
 980                                 return false;
 981                         }
 982                 }
 983
 984                 dn->components = talloc_realloc(dn,
 985                                                 dn->components,
 986                                                 struct ldb_dn_component,
 987                                                 dn->comp_num + base->comp_num);
 988                 if ( ! dn->components) {
 989                         dn->invalid = true;
 990                         return false;
 991                 }
 992
 993                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
 994                         dn->components[dn->comp_num] = ldb_dn_copy_component(dn->components, &base->components[i]);
 995                         if (dn->components[dn->comp_num].value.data == NULL) {
 996                                 dn->invalid = true;
 997                                 return false;
 998                         }
 999                 }
1000
1001                 if (dn->casefold && s) {
1002                         if (*dn->casefold) {
1003                                 t = talloc_asprintf(dn, "%s,%s", dn->casefold, s);
1004                         } else {
1005                                 t = talloc_strdup(dn, s);
1006                         }
1007                         LDB_FREE(dn->casefold);
1008                         dn->casefold = t;
1009                 }
1010         }
1011
1012         if (dn->linearized) {
1013
1014                 s = ldb_dn_get_linearized(base);
1015                 if ( ! s) {
1016                         return false;
1017                 }
1018
1019                 if (*dn->linearized) {
1020                         t = talloc_asprintf(dn, "%s,%s", dn->linearized, s);
1021                 } else {
1022                         t = talloc_strdup(dn, s);
1023                 }
1024                 if ( ! t) {
1025                         dn->invalid = true;
1026                         return false;
1027                 }
1028                 LDB_FREE(dn->linearized);
1029                 dn->linearized = t;
1030         }
1031
1032         return true;
1033 }
1034
1035 /* modify the given dn by adding a base.
1036  *
1037  * return true if successful and false if not
1038  * if false is returned the dn may be marked invalid
1039  */
1040 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1041 {
1042         struct ldb_dn *base;
1043         char *base_str;
1044         va_list ap;
1045         bool ret;
1046
1047         if ( !dn || dn->invalid) {
1048                 return false;
1049         }
1050
1051         va_start(ap, base_fmt);
1052         base_str = talloc_vasprintf(dn, base_fmt, ap);
1053         va_end(ap);
1054
1055         if (base_str == NULL) {
1056                 return false;
1057         }
1058
1059         base = ldb_dn_new(base_str, dn->ldb, base_str);
1060
1061         ret = ldb_dn_add_base(dn, base);
1062
1063         talloc_free(base_str);
1064
1065         return ret;
1066 }
1067
1068 /* modify the given dn by adding children elements.
1069  *
1070  * return true if successful and false if not
1071  * if false is returned the dn may be marked invalid
1072  */
1073 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1074 {
1075         const char *s;
1076         char *t;
1077
1078         if ( !child || child->invalid || !dn || dn->invalid) {
1079                 return false;
1080         }
1081
1082         if (dn->components) {
1083                 int n, i, j;
1084
1085                 if ( ! ldb_dn_validate(child)) {
1086                         return false;
1087                 }
1088
1089                 s = NULL;
1090                 if (dn->valid_case) {
1091                         if ( ! (s = ldb_dn_get_casefold(child))) {
1092                                 return false;
1093                         }
1094                 }
1095
1096                 n = dn->comp_num + child->comp_num;
1097
1098                 dn->components = talloc_realloc(dn,
1099                                                 dn->components,
1100                                                 struct ldb_dn_component,
1101                                                 n);
1102                 if ( ! dn->components) {
1103                         dn->invalid = true;
1104                         return false;
1105                 }
1106
1107                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1108                         dn->components[j] = dn->components[i];
1109                 }
1110
1111                 for (i = 0; i < child->comp_num; i++) {
1112                         dn->components[i] = ldb_dn_copy_component(dn->components, &child->components[i]);
1113                         if (dn->components[i].value.data == NULL) {
1114                                 dn->invalid = true;
1115                                 return false;
1116                         }
1117                 }
1118
1119                 dn->comp_num = n;
1120
1121                 if (dn->casefold && s) {
1122                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1123                         LDB_FREE(dn->casefold);
1124                         dn->casefold = t;
1125                 }
1126         }
1127
1128         if (dn->linearized) {
1129
1130                 s = ldb_dn_get_linearized(child);
1131                 if ( ! s) {
1132                         return false;
1133                 }
1134
1135                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1136                 if ( ! t) {
1137                         dn->invalid = true;
1138                         return false;
1139                 }
1140                 LDB_FREE(dn->linearized);
1141                 dn->linearized = t;
1142         }
1143
1144         return true;
1145 }
1146
1147 /* modify the given dn by adding children elements.
1148  *
1149  * return true if successful and false if not
1150  * if false is returned the dn may be marked invalid
1151  */
1152 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1153 {
1154         struct ldb_dn *child;
1155         char *child_str;
1156         va_list ap;
1157         bool ret;
1158
1159         if ( !dn || dn->invalid) {
1160                 return false;
1161         }
1162
1163         va_start(ap, child_fmt);
1164         child_str = talloc_vasprintf(dn, child_fmt, ap);
1165         va_end(ap);
1166
1167         if (child_str == NULL) {
1168                 return false;
1169         }
1170
1171         child = ldb_dn_new(child_str, dn->ldb, child_str);
1172
1173         ret = ldb_dn_add_child(dn, child);
1174
1175         talloc_free(child_str);
1176
1177         return ret;
1178 }
1179
1180 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1181 {
1182         int i;
1183
1184         if ( ! ldb_dn_validate(dn)) {
1185                 return false;
1186         }
1187
1188         if (dn->comp_num < num) {
1189                 return false;
1190         }
1191
1192         /* free components */
1193         for (i = num; i > 0; i--) {
1194                 LDB_FREE(dn->components[dn->comp_num - i].name);
1195                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1196                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1197                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1198         }
1199
1200         dn->comp_num -= num;
1201
1202         if (dn->valid_case) {
1203                 for (i = 0; i < dn->comp_num; i++) {
1204                         LDB_FREE(dn->components[i].cf_name);
1205                         LDB_FREE(dn->components[i].cf_value.data);
1206                 }
1207                 dn->valid_case = false;
1208         }
1209
1210         LDB_FREE(dn->casefold);
1211         LDB_FREE(dn->linearized);
1212
1213         return true;
1214 }
1215
1216 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1217 {
1218         int i, j;
1219
1220         if ( ! ldb_dn_validate(dn)) {
1221                 return false;
1222         }
1223
1224         if (dn->comp_num < num) {
1225                 return false;
1226         }
1227
1228         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1229                 if (i < num) {
1230                         LDB_FREE(dn->components[i].name);
1231                         LDB_FREE(dn->components[i].value.data);
1232                         LDB_FREE(dn->components[i].cf_name);
1233                         LDB_FREE(dn->components[i].cf_value.data);
1234                 }
1235                 dn->components[i] = dn->components[j];
1236         }
1237
1238         dn->comp_num -= num;
1239
1240         if (dn->valid_case) {
1241                 for (i = 0; i < dn->comp_num; i++) {
1242                         LDB_FREE(dn->components[i].cf_name);
1243                         LDB_FREE(dn->components[i].cf_value.data);
1244                 }
1245                 dn->valid_case = false;
1246         }
1247
1248         LDB_FREE(dn->casefold);
1249         LDB_FREE(dn->linearized);
1250
1251         return true;
1252 }
1253
1254 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1255 {
1256         struct ldb_dn *new_dn;
1257
1258         new_dn = ldb_dn_copy(mem_ctx, dn);
1259         if ( !new_dn ) {
1260                 return NULL;
1261         }
1262
1263         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1264                 talloc_free(new_dn);
1265                 return NULL;
1266         }
1267
1268         return new_dn;
1269 }
1270
1271 /* Create a 'canonical name' string from a DN:
1272
1273    ie dc=samba,dc=org -> samba.org/
1274       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1275
1276    There are two formats, the EX format has the last / replaced with a newline (\n).
1277
1278 */
1279 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1280         int i;
1281         TALLOC_CTX *tmpctx;
1282         char *cracked = NULL;
1283
1284         if ( ! ldb_dn_validate(dn)) {
1285                 return NULL;
1286         }
1287
1288         tmpctx = talloc_new(mem_ctx);
1289
1290         /* Walk backwards down the DN, grabbing 'dc' components at first */
1291         for (i = dn->comp_num - 1 ; i >= 0; i--) {
1292                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1293                         break;
1294                 }
1295                 if (cracked) {
1296                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1297                                                   ldb_dn_escape_value(tmpctx, dn->components[i].value),
1298                                                   cracked);
1299                 } else {
1300                         cracked = ldb_dn_escape_value(tmpctx, dn->components[i].value);
1301                 }
1302                 if (!cracked) {
1303                         goto done;
1304                 }
1305         }
1306
1307         /* Only domain components?  Finish here */
1308         if (i < 0) {
1309                 if (ex_format) {
1310                         cracked = talloc_append_string(tmpctx, cracked, "\n");
1311                 } else {
1312                         cracked = talloc_append_string(tmpctx, cracked, "/");
1313                 }
1314                 talloc_steal(mem_ctx, cracked);
1315                 goto done;
1316         }
1317
1318         /* Now walk backwards appending remaining components */
1319         for (; i > 0; i--) {
1320                 cracked = talloc_asprintf_append(cracked, "/%s",
1321                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1322                 if (!cracked) {
1323                         goto done;
1324                 }
1325         }
1326
1327         /* Last one, possibly a newline for the 'ex' format */
1328         if (ex_format) {
1329                 cracked = talloc_asprintf_append(cracked, "\n%s",
1330                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1331         } else {
1332                 cracked = talloc_asprintf_append(cracked, "/%s",
1333                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1334         }
1335
1336         talloc_steal(mem_ctx, cracked);
1337 done:
1338         talloc_free(tmpctx);
1339         return cracked;
1340 }
1341
1342 /* Wrapper functions for the above, for the two different string formats */
1343 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1344         return ldb_dn_canonical(mem_ctx, dn, 0);
1345
1346 }
1347
1348 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1349         return ldb_dn_canonical(mem_ctx, dn, 1);
1350 }
1351
1352 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1353 {
1354         if ( ! ldb_dn_validate(dn)) {
1355                 return -1;
1356         }
1357         return dn->comp_num;
1358 }
1359
1360 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1361 {
1362         if ( ! ldb_dn_validate(dn)) {
1363                 return NULL;
1364         }
1365         if (num >= dn->comp_num) return NULL;
1366         return dn->components[num].name;
1367 }
1368
1369 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn, unsigned int num)
1370 {
1371         if ( ! ldb_dn_validate(dn)) {
1372                 return NULL;
1373         }
1374         if (num >= dn->comp_num) return NULL;
1375         return &dn->components[num].value;
1376 }
1377
1378 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1379 {
1380         if ( ! ldb_dn_validate(dn)) {
1381                 return NULL;
1382         }
1383         if (dn->comp_num == 0) return NULL;
1384         return dn->components[0].name;
1385 }
1386
1387 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1388 {
1389         if ( ! ldb_dn_validate(dn)) {
1390                 return NULL;
1391         }
1392         if (dn->comp_num == 0) return NULL;
1393         return &dn->components[0].value;
1394 }
1395
1396 int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const struct ldb_val val)
1397 {
1398         char *n;
1399         struct ldb_val v;
1400
1401         if ( ! ldb_dn_validate(dn)) {
1402                 return LDB_ERR_OTHER;
1403         }
1404
1405         if (num >= dn->comp_num) {
1406                 return LDB_ERR_OTHER;
1407         }
1408
1409         n = talloc_strdup(dn, name);
1410         if ( ! n) {
1411                 return LDB_ERR_OTHER;
1412         }
1413
1414         v.length = val.length;
1415         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1416         if ( ! v.data) {
1417                 talloc_free(n);
1418                 return LDB_ERR_OTHER;
1419         }
1420
1421         talloc_free(dn->components[num].name);
1422         talloc_free(dn->components[num].value.data);
1423         dn->components[num].name = n;
1424         dn->components[num].value = v;
1425
1426         if (dn->valid_case) {
1427                 int i;
1428                 for (i = 0; i < dn->comp_num; i++) {
1429                         LDB_FREE(dn->components[i].cf_name);
1430                         LDB_FREE(dn->components[i].cf_value.data);
1431                 }
1432                 dn->valid_case = false;
1433         }
1434         LDB_FREE(dn->casefold);
1435         LDB_FREE(dn->linearized);
1436
1437         return LDB_SUCCESS;
1438 }
1439
1440 bool ldb_dn_is_valid(struct ldb_dn *dn)
1441 {
1442         if ( ! dn) return false;
1443         return ! dn->invalid;
1444 }
1445
1446 bool ldb_dn_is_special(struct ldb_dn *dn)
1447 {
1448         if ( ! dn || dn->invalid) return false;
1449         return dn->special;
1450 }
1451
1452 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
1453 {
1454         if ( ! dn || dn->invalid) return false;
1455         return ! strcmp(dn->linearized, check);
1456 }
1457
1458 bool ldb_dn_is_null(struct ldb_dn *dn)
1459 {
1460         if ( ! dn || dn->invalid) return false;
1461         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
1462         return false;
1463 }