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 2 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 explode and utility functions
  29  *
  30  *  Description: - explode a dn into it's own basic elements
  31  *                 and put them in a structure
  32  *               - manipulate ldb_dn structures
  33  *
  34  *  Author: Simo Sorce
  35  */
  36
  37 #include "includes.h"
  38 #include "ldb/include/ldb.h"
  39 #include "ldb/include/ldb_private.h"
  40 #include <ctype.h>
  41
  42 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  43
  44 static int ldb_dn_is_valid_attribute_name(const char *name)
  45 {
  46         while (*name) {
  47                 if (! isascii(*name)) {
  48                         return 0;
  49                 }
  50                 if (! (isalnum((unsigned char)*name) || *name == '-')) {
  51                         return 0;
  52                 }
  53                 name++;
  54         }
  55
  56         return 1;
  57 }
  58
  59 static char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
  60 {
  61         const char *p, *s, *src;
  62         char *d, *dst;
  63         int len;
  64
  65         if (!value.length)
  66                 return NULL;
  67
  68         p = s = src = (const char *)value.data;
  69         len = value.length;
  70
  71         /* allocate destination string, it will be at most 3 times the source */
  72         dst = d = talloc_array(mem_ctx, char, len * 3 + 1);
  73         LDB_DN_NULL_FAILED(dst);
  74
  75         while (p - src < len) {
  76
  77                 p += strcspn(p, ",=\n+<>#;\\\"");
  78
  79                 if (p - src == len) /* found no escapable chars */
  80                         break;
  81
  82                 memcpy(d, s, p - s); /* copy the part of the string before the stop */
  83                 d += (p - s); /* move to current position */
  84
  85                 if (*p) { /* it is a normal escapable character */
  86                         *d++ = '\\';
  87                         *d++ = *p++;
  88                 } else { /* we have a zero byte in the string */
  89                         strncpy(d, "\00", 3); /* escape the zero */
  90                         d = d + 3;
  91                         p++; /* skip the zero */
  92                 }
  93                 s = p; /* move forward */
  94         }
  95
  96         /* copy the last part (with zero) and return */
  97         memcpy(d, s, &src[len] - s + 1);
  98
  99         return dst;
 100
 101 failed:
 102         talloc_free(dst);
 103         return NULL;
 104 }
 105
 106 static struct ldb_val ldb_dn_unescape_value(void *mem_ctx, const char *src)
 107 {
 108         struct ldb_val value;
 109         unsigned x;
 110         char *p, *dst = NULL, *end;
 111
 112         value.length = 0;
 113
 114         LDB_DN_NULL_FAILED(src);
 115
 116         dst = p = talloc_memdup(mem_ctx, src, strlen(src) + 1);
 117         LDB_DN_NULL_FAILED(dst);
 118
 119         end = &dst[strlen(dst)];
 120
 121         while (*p) {
 122                 p += strcspn(p, ",=\n+<>#;\\\"");
 123
 124                 if (*p == '\\') {
 125                         if (strchr(",=\n+<>#;\\\"", p[1])) {
 126                                 memmove(p, p + 1, end - (p + 1) + 1);
 127                                 end--;
 128                                 p++;
 129                                 continue;
 130                         }
 131
 132                         if (sscanf(p + 1, "%02x", &x) == 1) {
 133                                 *p = (unsigned char)x;
 134                                 memmove(p + 1, p + 3, end - (p + 3) + 1);
 135                                 end -= 2;
 136                                 p++;
 137                                 continue;
 138                         }
 139                 }
 140
 141                 /* a string with not escaped specials is invalid (tested) */
 142                 if (*p != '\0') {
 143                         goto failed;
 144                 }
 145         }
 146
 147         value.length = end - dst;
 148         value.data = dst;
 149         return value;
 150
 151 failed:
 152         talloc_free(dst);
 153         return value;
 154 }
 155
 156 /* check if the string contains quotes
 157  * skips leading and trailing spaces
 158  * - returns 0 if no quotes found
 159  * - returns 1 if quotes are found and put their position
 160  *   in *quote_start and *quote_end parameters
 161  * - return -1 if there are open quotes
 162  */
 163
 164 static int get_quotes_position(const char *source, int *quote_start, int *quote_end)
 165 {
 166         const char *p;
 167
 168         p = source;
 169
 170         /* check if there are quotes surrounding the value */
 171         p += strspn(p, " \n"); /* skip white spaces */
 172
 173         if (*p == '\"') {
 174                 *quote_start = p - source;
 175
 176                 p++;
 177                 while (*p != '\"') {
 178                         p = strchr(p, '\"');
 179                         LDB_DN_NULL_FAILED(p);
 180
 181                         if (*(p - 1) == '\\')
 182                                 p++;
 183                 }
 184
 185                 *quote_end = p - source;
 186                 return 1;
 187         }
 188
 189         return 0;
 190
 191 failed:
 192         return -1;
 193 }
 194
 195 static char *seek_to_separator(char *string, const char *separators)
 196 {
 197         char *p;
 198         int ret, qs, qe;
 199
 200         p = strchr(string, '=');
 201         LDB_DN_NULL_FAILED(p);
 202
 203         p++;
 204
 205         /* check if there are quotes surrounding the value */
 206
 207         ret = get_quotes_position(p, &qs, &qe);
 208         if (ret == -1)
 209                 return NULL;
 210
 211         if (ret == 1) { /* quotes found */
 212
 213                 p += qe; /* positioning after quotes */
 214                 p += strspn(p, " \n"); /* skip white spaces after the quote */
 215
 216                 if (strcspn(p, separators) != 0) /* if there are characters between quotes */
 217                         return NULL;        /* and separators, the dn is invalid */
 218
 219                 return p; /* return on the separator */
 220         }
 221
 222         /* no quotes found seek to separators */
 223         ret = strcspn(p, separators);
 224         if (ret == 0) /* no separators ?! bail out */
 225                 return NULL;
 226
 227         return p + ret;
 228
 229 failed:
 230         return NULL;
 231 }
 232
 233 static char *ldb_dn_trim_string(char *string, const char *edge)
 234 {
 235         char *s, *p;
 236
 237         /* seek out edge from start of string */
 238         s = string + strspn(string, edge);
 239
 240         /* backwards skip from end of string */
 241         p = &s[strlen(s) - 1];
 242         while (p > s && strchr(edge, *p)) {
 243                 *p = '\0';
 244                 p--;
 245         }
 246
 247         return s;
 248 }
 249
 250 /* we choosed to not support multpile valued components */
 251 static struct ldb_dn_component ldb_dn_explode_component(void *mem_ctx, char *raw_component)
 252 {
 253         struct ldb_dn_component dc;
 254         char *p;
 255         int ret, qs, qe;
 256
 257         /* find attribute type/value separator */
 258         p = strchr(raw_component, '=');
 259         LDB_DN_NULL_FAILED(p);
 260
 261         *p++ = '\0'; /* terminate name and point to value */
 262
 263         /* copy and trim name in the component */
 264         dc.name = talloc_strdup(mem_ctx, ldb_dn_trim_string(raw_component, " \n"));
 265         if (!dc.name)
 266                 return dc;
 267
 268         if (! ldb_dn_is_valid_attribute_name(dc.name)) {
 269                 goto failed;
 270         }
 271
 272         ret = get_quotes_position(p, &qs, &qe);
 273
 274         switch (ret) {
 275         case 0: /* no quotes trim the string */
 276                 p = ldb_dn_trim_string(p, " \n");
 277                 dc.value = ldb_dn_unescape_value(mem_ctx, p);
 278                 break;
 279
 280         case 1: /* quotes found get the unquoted string */
 281                 p[qe] = '\0';
 282                 p = p + qs + 1;
 283                 dc.value.length = strlen(p);
 284                 dc.value.data = talloc_memdup(mem_ctx, p, dc.value.length + 1);
 285                 break;
 286
 287         default: /* mismatched quotes ot other error, bail out */
 288                 goto failed;
 289         }
 290
 291         if (dc.value.length == 0) {
 292                 goto failed;
 293         }
 294
 295         return dc;
 296
 297 failed:
 298         talloc_free(dc.name);
 299         dc.name = NULL;
 300         return dc;
 301 }
 302
 303 struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
 304 {
 305         struct ldb_dn *edn; /* the exploded dn */
 306         char *pdn, *p;
 307
 308         pdn = NULL;
 309
 310         /* Allocate a structure to hold the exploded DN */
 311         edn = talloc(mem_ctx, struct ldb_dn);
 312         LDB_DN_NULL_FAILED(edn);
 313
 314         /* Initially there are no components */
 315         edn->comp_num = 0;
 316         edn->components = NULL;
 317
 318         /* Special DNs case */
 319         if (dn[0] == '@') {
 320                 edn->comp_num = 1;
 321                 edn->components = talloc(edn, struct ldb_dn_component);
 322                 if (edn->components == NULL) goto failed;
 323                 edn->components[0].name = talloc_strdup(edn->components, "@SPECIAL");
 324                 if (edn->components[0].name == NULL) goto failed;
 325                 edn->components[0].value.data = talloc_strdup(edn->components, dn);
 326                 if (edn->components[0].value.data== NULL) goto failed;
 327                 edn->components[0].value.length = strlen(dn);
 328                 return edn;
 329         }
 330
 331         pdn = p = talloc_strdup(edn, dn);
 332         LDB_DN_NULL_FAILED(pdn);
 333
 334         /* get the components */
 335         do {
 336                 char *t;
 337
 338                 /* terminate the current component and return pointer to the next one */
 339                 t = seek_to_separator(p, ",;");
 340                 LDB_DN_NULL_FAILED(t);
 341
 342                 if (*t) { /* here there is a separator */
 343                         *t = '\0'; /*terminate */
 344                         t++; /* a separtor means another component follows */
 345                 }
 346
 347                 /* allocate space to hold the dn component */
 348                 edn->components = talloc_realloc(edn, edn->components,
 349                                                  struct ldb_dn_component,
 350                                                  edn->comp_num + 1);
 351                 if (edn->components == NULL)
 352                         goto failed;
 353
 354                 /* store the exploded component in the main structure */
 355                 edn->components[edn->comp_num] = ldb_dn_explode_component(edn, p);
 356                 LDB_DN_NULL_FAILED(edn->components[edn->comp_num].name);
 357
 358                 edn->comp_num++;
 359
 360                 /* jump to the next component if any */
 361                 p = t;
 362
 363         } while(*p);
 364
 365         talloc_free(pdn);
 366         return edn;
 367
 368 failed:
 369         talloc_free(pdn);
 370         talloc_free(edn);
 371         return NULL;
 372 }
 373
 374 char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn)
 375 {
 376         char *dn, *value;
 377         int i;
 378
 379         /* Special DNs */
 380         if ((edn->comp_num == 1) && strcmp("@SPECIAL", edn->components[0].name) == 0) {
 381                 dn = talloc_strdup(mem_ctx, edn->components[0].value.data);
 382                 return dn;
 383         }
 384
 385         dn = talloc_strdup(mem_ctx, "");
 386         LDB_DN_NULL_FAILED(dn);
 387
 388         for (i = 0; i < edn->comp_num; i++) {
 389                 value = ldb_dn_escape_value(dn, edn->components[i].value);
 390                 LDB_DN_NULL_FAILED(value);
 391
 392                 if (i == 0) {
 393                         dn = talloc_asprintf_append(dn, "%s=%s", edn->components[i].name, value);
 394                 } else {
 395                         dn = talloc_asprintf_append(dn, ",%s=%s", edn->components[i].name, value);
 396                 }
 397                 LDB_DN_NULL_FAILED(dn);
 398
 399                 talloc_free(value);
 400         }
 401
 402         return dn;
 403
 404 failed:
 405         talloc_free(dn);
 406         return NULL;
 407 }
 408
 409 /* compare DNs using casefolding compare functions */
 410
 411 int ldb_dn_compare_base(struct ldb_context *ldb,
 412                    const struct ldb_dn *base,
 413                    const struct ldb_dn *dn)
 414 {
 415         int ret;
 416         int n0, n1;
 417
 418         if (base->comp_num > dn->comp_num) {
 419                 return (dn->comp_num - base->comp_num);
 420         }
 421
 422         /* if the number of components doesn't match they differ */
 423         n0 = base->comp_num - 1;
 424         n1 = dn->comp_num - 1;
 425         while (n0 >= 0 && n1 >= 0) {
 426                 const struct ldb_attrib_handler *h;
 427
 428                 /* compare names (attribute names are guaranteed to be ASCII only) */
 429                 ret = ldb_caseless_cmp(base->components[n0].name,
 430                                        dn->components[n1].name);
 431                 if (ret) {
 432                         return ret;
 433                 }
 434
 435                 /* names match, compare values */
 436                 h = ldb_attrib_handler(ldb, base->components[n0].name);
 437                 ret = h->comparison_fn(ldb, ldb, &(base->components[n0].value),
 438                                                   &(dn->components[n1].value));
 439                 if (ret) {
 440                         return ret;
 441                 }
 442                 n1--;
 443                 n0--;
 444         }
 445
 446         return 0;
 447 }
 448
 449 int ldb_dn_compare(struct ldb_context *ldb,
 450                    const struct ldb_dn *edn0,
 451                    const struct ldb_dn *edn1)
 452 {
 453         if (edn0->comp_num != edn1->comp_num)
 454                 return (edn1->comp_num - edn0->comp_num);
 455
 456         return ldb_dn_compare_base(ldb, edn0, edn1);
 457 }
 458
 459 int ldb_dn_cmp(struct ldb_context *ldb, const char *dn0, const char *dn1)
 460 {
 461         struct ldb_dn *edn0;
 462         struct ldb_dn *edn1;
 463         int ret;
 464
 465         edn0 = ldb_dn_explode_casefold(ldb, dn0);
 466         if (edn0 == NULL) return 0;
 467
 468         edn1 = ldb_dn_explode_casefold(ldb, dn1);
 469         if (edn1 == NULL) {
 470                 talloc_free(edn0);
 471                 return 0;
 472         }
 473
 474         ret = ldb_dn_compare(ldb, edn0, edn1);
 475
 476         talloc_free(edn0);
 477         talloc_free(edn1);
 478
 479         return ret;
 480 }
 481
 482 /*
 483   casefold a dn. We need to casefold the attribute names, and canonicalize
 484   attribute values of case insensitive attributes.
 485 */
 486 struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, const struct ldb_dn *edn)
 487 {
 488         struct ldb_dn *cedn;
 489         int i;
 490
 491         cedn = talloc(ldb, struct ldb_dn);
 492         LDB_DN_NULL_FAILED(cedn);
 493
 494         cedn->comp_num = edn->comp_num;
 495         cedn->components = talloc_array(cedn, struct ldb_dn_component, edn->comp_num);
 496         LDB_DN_NULL_FAILED(cedn->components);
 497
 498         for (i = 0; i < edn->comp_num; i++) {
 499                 struct ldb_dn_component dc;
 500                 const struct ldb_attrib_handler *h;
 501
 502                 dc.name = ldb_casefold(cedn, edn->components[i].name);
 503                 LDB_DN_NULL_FAILED(dc.name);
 504
 505                 h = ldb_attrib_handler(ldb, dc.name);
 506                 if (h->canonicalise_fn(ldb, cedn, &(edn->components[i].value), &(dc.value)) != 0) {
 507                         goto failed;
 508                 }
 509
 510                 cedn->components[i] = dc;
 511         }
 512
 513         return cedn;
 514
 515 failed:
 516         talloc_free(cedn);
 517         return NULL;
 518 }
 519
 520 struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn)
 521 {
 522         struct ldb_dn *edn, *cdn;
 523
 524         edn = ldb_dn_explode(ldb, dn);
 525         if (edn == NULL) return NULL;
 526
 527         cdn = ldb_dn_casefold(ldb, edn);
 528
 529         talloc_free(edn);
 530         return cdn;
 531 }