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