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 "ldb/include/ldb_dn.h"
  41
  42
  43 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  44
  45 static char *escape_string(void *mem_ctx, const char *src)
  46 {
  47         const char *p, *s;
  48         char *d, *dst=NULL;
  49
  50         LDB_DN_NULL_FAILED(src);
  51
  52         /* allocate destination string, it will be at most 3 times the source */
  53         dst = d = talloc_array(mem_ctx, char, strlen(src) * 3 + 1);
  54         LDB_DN_NULL_FAILED(dst);
  55
  56         p = s = src;
  57
  58         while (*p) {
  59                 p += strcspn(p, ",=\n+<>#;\\\"");
  60                 if (*p == '\0') /* no special s found, all ok */
  61                         break;
  62
  63                 if (*p) { /* copy part of the string and escape */
  64                         memcpy(d, s, p - s);
  65                         d += (p - s);
  66                         *d++ = '\\';
  67                         *d++ = *p++;
  68                         s = p;
  69                 }
  70         }
  71
  72         /* copy the last part (with zero) and return */
  73         memcpy(d, s, &src[strlen(src)] - s + 1);
  74
  75         return dst;
  76 failed:
  77         talloc_free(dst);
  78         return NULL;
  79 }
  80
  81 static char *unescape_string(void *mem_ctx, const char *src)
  82 {
  83         unsigned x;
  84         char *p, *dst=NULL, *end;
  85
  86         LDB_DN_NULL_FAILED(src);
  87
  88         dst = p = talloc_strdup(mem_ctx, src);
  89         LDB_DN_NULL_FAILED(dst);
  90
  91         end = &dst[strlen(dst)];
  92
  93         while (*p) {
  94                 p += strcspn(p, ",=\n+<>#;\\\"");
  95                 if (*p == '\0') /* no escapes or specials found, all ok */
  96                         return dst;
  97
  98                 if (*p == '\\') {
  99                         if (strchr(",=\n+<>#;\\\"", p[1])) {
 100                                 memmove(p, p + 1, end - (p + 1) + 1);
 101                                 end--;
 102                                 p++;
 103                                 continue;
 104                         }
 105
 106                         if (sscanf(p + 1, "%02x", &x) == 1) {
 107                                 *p = (unsigned char)x;
 108                                 memmove(p + 1, p + 3, end - (p + 3) + 1);
 109                                 end -= 2;
 110                                 p++;
 111                                 continue;
 112                         }
 113                 }
 114
 115                 /* a string with not escaped specials is invalid */
 116
 117                 return NULL;
 118         }
 119
 120         return dst;
 121 failed:
 122         talloc_free(dst);
 123         return NULL;
 124 }
 125
 126 static char *seek_to_separator(char *string, const char *separator)
 127 {
 128         char *p;
 129
 130         p = strchr(string, '=');
 131
 132         LDB_DN_NULL_FAILED(p);
 133
 134         p++;
 135
 136         /* check if there are quotes surrounding the value */
 137         p += strspn(p, " \n"); /* skip white spaces after '=' */
 138
 139         if (*p == '\"') {
 140                 p++;
 141                 while (*p != '\"') {
 142                         p = strchr(p, '\"');
 143                         LDB_DN_NULL_FAILED(p);
 144
 145                         if (*(p - 1) == '\\')
 146                                 p++;
 147                 }
 148         }
 149
 150         p += strcspn(p, separator);
 151
 152         return p;
 153
 154 failed:
 155         return NULL;
 156 }
 157
 158 static char *ldb_dn_trim_string(char *string, const char *edge)
 159 {
 160         char *s, *p;
 161
 162         /* seek out edge from start of string */
 163         s = string + strspn(string, edge);
 164
 165         /* backwards skip from end of string */
 166         p = &s[strlen(s) - 1];
 167         while (p > s && strchr(edge, *p)) {
 168                 *p = '\0';
 169                 p--;
 170         }
 171
 172         return s;
 173 }
 174
 175 static struct ldb_dn_attribute *ldb_dn_explode_attribute(void *mem_ctx, char *raw_attribute)
 176 {
 177         struct ldb_dn_attribute *at;
 178         char *p;
 179
 180         at = talloc(mem_ctx, struct ldb_dn_attribute);
 181         LDB_DN_NULL_FAILED(at);
 182
 183         p = strchr(raw_attribute, '=');
 184
 185         LDB_DN_NULL_FAILED(p);
 186
 187         *p = '\0';
 188
 189         at->name = talloc_strdup(at, ldb_dn_trim_string(raw_attribute, " \n"));
 190         LDB_DN_NULL_FAILED(at->name);
 191
 192         p++;
 193
 194         p = ldb_dn_trim_string(p, " \n");
 195
 196         if (*p == '\"') { /* quotes at start means there must be quotes at the end */
 197                 if (p[strlen(p) - 1] != '\"') /* malformed value */
 198                         return NULL;
 199
 200                 p++;
 201                 p[strlen(p) - 1] = '\0';
 202                 at->value = talloc_strdup(at, p);
 203
 204                 return at;
 205         }
 206         /* no quotes means we must unescape the string */
 207         at->value = unescape_string(at, p);
 208         LDB_DN_NULL_FAILED(at->value);
 209
 210         return at;
 211
 212 failed:
 213         talloc_free(at);
 214         return NULL;
 215 }
 216
 217 static struct ldb_dn_component *explode_component(void *mem_ctx, char *raw_component)
 218 {
 219         struct ldb_dn_component *dc;
 220         char *p;
 221
 222         dc = talloc(mem_ctx, struct ldb_dn_component);
 223         LDB_DN_NULL_FAILED(dc);
 224
 225         dc->attr_num = 0;
 226         dc->attributes = NULL;
 227
 228         p = raw_component;
 229
 230         /* get the components */
 231         do {
 232                 char *t;
 233
 234                 /* terminate the current attribute and return pointer to the next one */
 235                 t = seek_to_separator(p, "+");
 236                 LDB_DN_NULL_FAILED(t);
 237
 238                 if (*t) { /* here there is a separator */
 239                         *t = '\0'; /*terminate */
 240                         t++; /* a separtor means there's another attribute that follows */
 241                 }
 242
 243                 /* allocate attributes pointer */
 244                 dc->attributes = talloc_realloc(dc, dc->attributes,
 245                                                 struct ldb_dn_attribute *,
 246                                                 dc->attr_num + 1);
 247                 LDB_DN_NULL_FAILED(dc->attributes);
 248
 249                 /* store the exploded attirbute in the main structure */
 250                 dc->attributes[dc->attr_num] = ldb_dn_explode_attribute(dc->attributes, p);
 251                 LDB_DN_NULL_FAILED(dc->attributes[dc->attr_num]);
 252
 253                 dc->attr_num++;
 254
 255                 /* jump to the next attribute if any */
 256                 p = t;
 257
 258         } while(*p);
 259
 260         return dc;
 261 failed:
 262         talloc_free(dc);
 263         return NULL;
 264 }
 265
 266 /* FIXME: currently consider a dn composed of only case insensitive attributes
 267           this is not correct and need to be fixed soon */
 268 static void ldb_dn_sort_attributes(struct ldb_dn *edn)
 269 {
 270         struct ldb_dn_attribute *at0, *at1;
 271         int i, j, k, l;
 272
 273         for (i = 0; i < edn->comp_num; i++) {
 274                 if (edn->components[i]->attr_num > 1) {
 275
 276                         /* it is very unlikely that there is a multivalued RDN. In that
 277                            unlikely case it is very unlikely you will find more than 2
 278                            values. So the use of bubble sort here seem to be acceptable */
 279                         for (j = 0; (j + 1) < edn->components[i]->attr_num; j++) {
 280                                 for (k = j; k >= 0; k--) {
 281                                         at0 = edn->components[i]->attributes[k];
 282                                         at1 = edn->components[i]->attributes[k + 1];
 283                                         l = ldb_caseless_cmp(at0->name, at1->name);
 284                                         if (l > 0) {
 285                                                 /* already sorted, so no bubbles to move exit inner loop */
 286                                                 break;
 287                                         }
 288                                         if (l == 0) {
 289                                                 if (ldb_caseless_cmp(at0->value, at1->value) >= 0) {
 290                                                         /* already sorted, so no bubbles to move exit inner loop */
 291                                                         break;
 292                                                 }
 293                                         }
 294
 295                                         edn->components[i]->attributes[k] = at1;
 296                                         edn->components[i]->attributes[k + 1] = at0;
 297                                 }
 298                         }
 299                 }
 300         }
 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         /* Allocate a structure to hold the exploded DN */
 309         edn = talloc(mem_ctx, struct ldb_dn);
 310         LDB_DN_NULL_FAILED(edn);
 311
 312         /* Initially there are no components */
 313         edn->comp_num = 0;
 314         edn->components = NULL;
 315
 316         pdn = p = talloc_strdup(edn, dn);
 317         if (!pdn)
 318                 goto failed;
 319
 320         /* get the components */
 321         do {
 322                 char *t;
 323
 324                 /* terminate the current component and return pointer to the next one */
 325                 t = seek_to_separator(p, ",;");
 326                 if (t == NULL)
 327                         goto failed;
 328
 329                 if (*t) { /* here there is a separator */
 330                         *t = '\0'; /*terminate */
 331                         t++; /* a separtor means there's another component that follows */
 332                 }
 333
 334                 /* allocate space to hold the dn component */
 335                 edn->components = talloc_realloc(edn, edn->components,
 336                                                  struct ldb_dn_component *,
 337                                                  edn->comp_num + 1);
 338                 if (edn->components == NULL)
 339                         goto failed;
 340
 341                 /* store the exploded component in the main structure */
 342                 edn->components[edn->comp_num] = explode_component(edn->components, p);
 343                 if (edn->components[edn->comp_num] == NULL)
 344                         goto failed;
 345
 346                 edn->comp_num++;
 347
 348                 /* jump to the next component if any */
 349                 p = t;
 350
 351         } while(*p);
 352
 353         /* sort attributes if there's any multivalued component */
 354         ldb_dn_sort_attributes(edn);
 355
 356         talloc_free(pdn);
 357         return edn;
 358
 359 failed:
 360         talloc_free(edn);
 361         return NULL;
 362 }
 363
 364 char *ldb_dn_linearize(void *mem_ctx, struct ldb_dn *edn)
 365 {
 366         char *dn, *ename, *evalue;
 367         const char *format;
 368         int i, j;
 369
 370         dn = talloc_strdup(mem_ctx, "");
 371         LDB_DN_NULL_FAILED(dn);
 372
 373         for (i = 0; i < edn->comp_num; i++) {
 374                 if (i != 0) {
 375                         dn = talloc_append_string(mem_ctx, dn, ",");
 376                 }
 377                 for (j = 0; j < edn->components[i]->attr_num; j++) {
 378                         if (j == 0) {
 379                                 format = "%s=%s";
 380                         } else {
 381                                 format = "+%s=%s";
 382                         }
 383
 384                         ename = escape_string(dn, edn->components[i]->attributes[j]->name);
 385                         LDB_DN_NULL_FAILED(ename);
 386
 387                         evalue = escape_string(dn, edn->components[i]->attributes[j]->value);
 388                         LDB_DN_NULL_FAILED(evalue);
 389
 390                         dn = talloc_asprintf_append(dn, format, ename, evalue);
 391                         LDB_DN_NULL_FAILED(dn);
 392
 393                         talloc_free(ename);
 394                         talloc_free(evalue);
 395                 }
 396         }
 397
 398         return dn;
 399 failed:
 400         talloc_free(dn);
 401         return NULL;
 402 }
 403
 404 /* FIXME: currently consider a dn composed of only case insensitive attributes
 405           this is not correct and need to be fixed soon */
 406 int ldb_dn_compare(struct ldb_dn *edn0, struct ldb_dn *edn1)
 407 {
 408         struct ldb_dn_attribute *at0, *at1;
 409         int i, j, k;
 410
 411         /* if the number of components doesn't match they differ */
 412         if (edn0->comp_num != edn1->comp_num)
 413                 return (edn1->comp_num - edn0->comp_num);
 414
 415         for (i = 0; i < edn0->comp_num; i++) {
 416
 417                 /* if the number of attributes per component doesn't match they differ */
 418                 if (edn0->components[i]->attr_num != edn1->components[i]->attr_num)
 419                         return (edn1->components[i]->attr_num - edn0->components[i]->attr_num);
 420
 421                 for (j = 0; j < edn0->components[i]->attr_num; j++) {
 422                         at0 = edn0->components[i]->attributes[j];
 423                         at1 = edn1->components[i]->attributes[j];
 424
 425                         /* compare names */
 426                         k = ldb_caseless_cmp(at0->name, at1->name);
 427                         if (k)
 428                                 return k;
 429
 430                         /* names match, compare values */
 431                         k = ldb_caseless_cmp(at0->value, at1->value);
 432                         if (k)
 433                                 return k;
 434                 }
 435         }
 436
 437         return 0;
 438 }
 439
 440 /*
 441   casefold a dn. We need to uppercase the attribute names, and the
 442   attribute values of case insensitive attributes. We also need to remove
 443   extraneous spaces between elements
 444 */
 445 struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, struct ldb_dn *edn)
 446 {
 447         struct ldb_dn *cedn;
 448         int i, j;
 449
 450         cedn = talloc(ldb, struct ldb_dn);
 451         LDB_DN_NULL_FAILED(cedn);
 452
 453         cedn->comp_num = edn->comp_num;
 454         cedn->components = talloc_array(cedn, struct ldb_dn_component *, edn->comp_num);
 455         LDB_DN_NULL_FAILED(cedn->components);
 456
 457         for (i = 0; i < edn->comp_num; i++) {
 458                 struct ldb_dn_component *dc;
 459
 460                 dc = talloc(cedn->components, struct ldb_dn_component);
 461                 LDB_DN_NULL_FAILED(dc);
 462
 463                 dc->attr_num = edn->components[i]->attr_num;
 464                 dc->attributes = edn->components[i]->attributes;
 465                 LDB_DN_NULL_FAILED(dc->attributes);
 466
 467                 for (j = 0; j < edn->components[i]->attr_num; j++) {
 468                         struct ldb_dn_attribute *at;
 469                         struct ldb_val v0, v;
 470                         const struct ldb_attrib_handler *h;
 471
 472                         at = talloc(dc->attributes, struct ldb_dn_attribute);
 473                         LDB_DN_NULL_FAILED(at);
 474
 475                         at->name = ldb_casefold(at, edn->components[i]->attributes[j]->name);
 476                         LDB_DN_NULL_FAILED(at->name);
 477
 478                         h = ldb_attrib_handler(ldb, at->name);
 479                         /* at->value should be a ldb_val, work around
 480                            this for now .... */
 481                         v0.data = edn->components[i]->attributes[j]->value;
 482                         v0.length = strlen(v0.data);
 483                         if (h->canonicalise_fn(ldb, &v0, &v) != 0) {
 484                                 return NULL;
 485                         }
 486
 487                         talloc_steal(at, v.data);
 488                         at->value = v.data;
 489                         dc->attributes[j] = at;
 490                 }
 491
 492                 cedn->components[i] = dc;
 493         }
 494
 495         return cedn;
 496
 497 failed:
 498         talloc_free(cedn);
 499         return NULL;
 500 }
 501