source3/lib/ldb_compat.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Tridgell  2004
   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 #include "includes.h"
  25
  26 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s);
  27
  28 static int ldb_parse_hex2char(const char *x)
  29 {
  30         if (isxdigit(x[0]) && isxdigit(x[1])) {
  31                 const char h1 = x[0], h2 = x[1];
  32                 int c;
  33
  34                 if (h1 >= 'a') c = h1 - (int)'a' + 10;
  35                 else if (h1 >= 'A') c = h1 - (int)'A' + 10;
  36                 else if (h1 >= '0') c = h1 - (int)'0';
  37                 c = c << 4;
  38                 if (h2 >= 'a') c += h2 - (int)'a' + 10;
  39                 else if (h2 >= 'A') c += h2 - (int)'A' + 10;
  40                 else if (h2 >= '0') c += h2 - (int)'0';
  41
  42                 return c;
  43         }
  44
  45         return -1;
  46 }
  47
  48
  49
  50 /*
  51    structures for ldb_parse_tree handling code
  52 */
  53 enum ldb_parse_op { LDB_OP_AND=1, LDB_OP_OR=2, LDB_OP_NOT=3,
  54                     LDB_OP_EQUALITY=4, LDB_OP_SUBSTRING=5,
  55                     LDB_OP_GREATER=6, LDB_OP_LESS=7, LDB_OP_PRESENT=8,
  56                     LDB_OP_APPROX=9, LDB_OP_EXTENDED=10 };
  57
  58 struct ldb_parse_tree {
  59         enum ldb_parse_op operation;
  60         union {
  61                 struct {
  62                         struct ldb_parse_tree *child;
  63                 } isnot;
  64                 struct {
  65                         const char *attr;
  66                         struct ldb_val value;
  67                 } equality;
  68                 struct {
  69                         const char *attr;
  70                         int start_with_wildcard;
  71                         int end_with_wildcard;
  72                         struct ldb_val **chunks;
  73                 } substring;
  74                 struct {
  75                         const char *attr;
  76                 } present;
  77                 struct {
  78                         const char *attr;
  79                         struct ldb_val value;
  80                 } comparison;
  81                 struct {
  82                         const char *attr;
  83                         int dnAttributes;
  84                         char *rule_id;
  85                         struct ldb_val value;
  86                 } extended;
  87                 struct {
  88                         unsigned int num_elements;
  89                         struct ldb_parse_tree **elements;
  90                 } list;
  91         } u;
  92 };
  93
  94 /*
  95    decode a RFC2254 binary string representation of a buffer.
  96    Used in LDAP filters.
  97 */
  98 static struct ldb_val ldb_binary_decode(void *mem_ctx, const char *str)
  99 {
 100         size_t i, j;
 101         struct ldb_val ret;
 102         size_t slen = str?strlen(str):0;
 103
 104         ret.data = (uint8_t *)talloc_size(mem_ctx, slen+1);
 105         ret.length = 0;
 106         if (ret.data == NULL) return ret;
 107
 108         for (i=j=0;i<slen;i++) {
 109                 if (str[i] == '\\') {
 110                         int c;
 111
 112                         c = ldb_parse_hex2char(&str[i+1]);
 113                         if (c == -1) {
 114                                 talloc_free(ret.data);
 115                                 memset(&ret, 0, sizeof(ret));
 116                                 return ret;
 117                         }
 118                         ((uint8_t *)ret.data)[j++] = c;
 119                         i += 2;
 120                 } else {
 121                         ((uint8_t *)ret.data)[j++] = str[i];
 122                 }
 123         }
 124         ret.length = j;
 125         ((uint8_t *)ret.data)[j] = 0;
 126
 127         return ret;
 128 }
 129
 130
 131
 132
 133 /*
 134    encode a blob as a RFC2254 binary string, escaping any
 135    non-printable or '\' characters
 136 */
 137 char *ldb_binary_encode(void *mem_ctx, struct ldb_val val)
 138 {
 139         size_t i;
 140         char *ret;
 141         size_t len = val.length;
 142         unsigned char *buf = val.data;
 143
 144         for (i=0;i<val.length;i++) {
 145                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 146                         len += 2;
 147                 }
 148         }
 149         ret = talloc_array(mem_ctx, char, len+1);
 150         if (ret == NULL) return NULL;
 151
 152         len = 0;
 153         for (i=0;i<val.length;i++) {
 154                 if (!isprint(buf[i]) || strchr(" *()\\&|!\"", buf[i])) {
 155                         snprintf(ret+len, 4, "\\%02X", buf[i]);
 156                         len += 3;
 157                 } else {
 158                         ret[len++] = buf[i];
 159                 }
 160         }
 161
 162         ret[len] = 0;
 163
 164         return ret;
 165 }
 166
 167
 168
 169 static enum ldb_parse_op ldb_parse_filtertype(void *mem_ctx, char **type, char **value, const char **s)
 170 {
 171         enum ldb_parse_op filter = 0;
 172         char *name, *val, *k;
 173         const char *p = *s;
 174         const char *t, *t1;
 175
 176         /* retrieve attributetype name */
 177         t = p;
 178
 179         if (*p == '@') { /* for internal attributes the first char can be @ */
 180                 p++;
 181         }
 182
 183         while ((isascii(*p) && isalnum((unsigned char)*p)) || (*p == '-') || (*p == '.')) {
 184                 /* attribute names can only be alphanums */
 185                 p++;
 186         }
 187
 188         if (*p == ':') { /* but extended searches have : and . chars too */
 189                 p = strstr(p, ":=");
 190                 if (p == NULL) { /* malformed attribute name */
 191                         return 0;
 192                 }
 193         }
 194
 195         t1 = p;
 196
 197         while (isspace((unsigned char)*p)) p++;
 198
 199         if (!strchr("=<>~:", *p)) {
 200                 return 0;
 201         }
 202
 203         /* save name */
 204         name = (char *)talloc_memdup(mem_ctx, t, t1 - t + 1);
 205         if (name == NULL) return 0;
 206         name[t1 - t] = '\0';
 207
 208         /* retrieve filtertype */
 209
 210         if (*p == '=') {
 211                 filter = LDB_OP_EQUALITY;
 212         } else if (*(p + 1) == '=') {
 213                 switch (*p) {
 214                 case '<':
 215                         filter = LDB_OP_LESS;
 216                         p++;
 217                         break;
 218                 case '>':
 219                         filter = LDB_OP_GREATER;
 220                         p++;
 221                         break;
 222                 case '~':
 223                         filter = LDB_OP_APPROX;
 224                         p++;
 225                         break;
 226                 case ':':
 227                         filter = LDB_OP_EXTENDED;
 228                         p++;
 229                         break;
 230                 }
 231         }
 232         if (!filter) {
 233                 talloc_free(name);
 234                 return filter;
 235         }
 236         p++;
 237
 238         while (isspace((unsigned char)*p)) p++;
 239
 240         /* retrieve value */
 241         t = p;
 242
 243         while (*p && ((*p != ')') || ((*p == ')') && (*(p - 1) == '\\')))) p++;
 244
 245         val = (char *)talloc_memdup(mem_ctx, t, p - t + 1);
 246         if (val == NULL) {
 247                 talloc_free(name);
 248                 return 0;
 249         }
 250         val[p - t] = '\0';
 251
 252         k = &(val[p - t]);
 253
 254         /* remove trailing spaces from value */
 255         while ((k > val) && (isspace((unsigned char)*(k - 1)))) k--;
 256         *k = '\0';
 257
 258         *type = name;
 259         *value = val;
 260         *s = p;
 261         return filter;
 262 }
 263
 264 /* find the first matching wildcard */
 265 static char *ldb_parse_find_wildcard(char *value)
 266 {
 267         while (*value) {
 268                 value = strpbrk(value, "\\*");
 269                 if (value == NULL) return NULL;
 270
 271                 if (value[0] == '\\') {
 272                         if (value[1] == '\0') return NULL;
 273                         value += 2;
 274                         continue;
 275                 }
 276
 277                 if (value[0] == '*') return value;
 278         }
 279
 280         return NULL;
 281 }
 282
 283 /* return a NULL terminated list of binary strings representing the value
 284    chunks separated by wildcards that makes the value portion of the filter
 285 */
 286 static struct ldb_val **ldb_wildcard_decode(void *mem_ctx, const char *string)
 287 {
 288         struct ldb_val **ret = NULL;
 289         unsigned int val = 0;
 290         char *wc, *str;
 291
 292         wc = talloc_strdup(mem_ctx, string);
 293         if (wc == NULL) return NULL;
 294
 295         while (wc && *wc) {
 296                 str = wc;
 297                 wc = ldb_parse_find_wildcard(str);
 298                 if (wc && *wc) {
 299                         if (wc == str) {
 300                                 wc++;
 301                                 continue;
 302                         }
 303                         *wc = 0;
 304                         wc++;
 305                 }
 306
 307                 ret = talloc_realloc(mem_ctx, ret, struct ldb_val *, val + 2);
 308                 if (ret == NULL) return NULL;
 309
 310                 ret[val] = talloc(mem_ctx, struct ldb_val);
 311                 if (ret[val] == NULL) return NULL;
 312
 313                 *(ret[val]) = ldb_binary_decode(mem_ctx, str);
 314                 if ((ret[val])->data == NULL) return NULL;
 315
 316                 val++;
 317         }
 318
 319         if (ret != NULL) {
 320                 ret[val] = NULL;
 321         }
 322
 323         return ret;
 324 }
 325
 326 /*
 327   parse an extended match
 328
 329   possible forms:
 330         (attr:oid:=value)
 331         (attr:dn:oid:=value)
 332         (attr:dn:=value)
 333         (:dn:oid:=value)
 334
 335   the ':dn' part sets the dnAttributes boolean if present
 336   the oid sets the rule_id string
 337
 338 */
 339 static struct ldb_parse_tree *ldb_parse_extended(struct ldb_parse_tree *ret,
 340                                                  char *attr, char *value)
 341 {
 342         char *p1, *p2;
 343
 344         ret->operation = LDB_OP_EXTENDED;
 345         ret->u.extended.value = ldb_binary_decode(ret, value);
 346         if (ret->u.extended.value.data == NULL) goto failed;
 347
 348         p1 = strchr(attr, ':');
 349         if (p1 == NULL) goto failed;
 350         p2 = strchr(p1+1, ':');
 351
 352         *p1 = 0;
 353         if (p2) *p2 = 0;
 354
 355         ret->u.extended.attr = attr;
 356         if (strcmp(p1+1, "dn") == 0) {
 357                 ret->u.extended.dnAttributes = 1;
 358                 if (p2) {
 359                         ret->u.extended.rule_id = talloc_strdup(ret, p2+1);
 360                         if (ret->u.extended.rule_id == NULL) goto failed;
 361                 } else {
 362                         ret->u.extended.rule_id = NULL;
 363                 }
 364         } else {
 365                 ret->u.extended.dnAttributes = 0;
 366                 ret->u.extended.rule_id = talloc_strdup(ret, p1+1);
 367                 if (ret->u.extended.rule_id == NULL) goto failed;
 368         }
 369
 370         return ret;
 371
 372 failed:
 373         talloc_free(ret);
 374         return NULL;
 375 }
 376
 377
 378 /*
 379   <simple> ::= <attributetype> <filtertype> <attributevalue>
 380 */
 381 static struct ldb_parse_tree *ldb_parse_simple(void *mem_ctx, const char **s)
 382 {
 383         char *attr, *value;
 384         struct ldb_parse_tree *ret;
 385         enum ldb_parse_op filtertype;
 386
 387         ret = talloc(mem_ctx, struct ldb_parse_tree);
 388         if (!ret) {
 389                 errno = ENOMEM;
 390                 return NULL;
 391         }
 392
 393         filtertype = ldb_parse_filtertype(ret, &attr, &value, s);
 394         if (!filtertype) {
 395                 talloc_free(ret);
 396                 return NULL;
 397         }
 398
 399         switch (filtertype) {
 400
 401                 case LDB_OP_PRESENT:
 402                         ret->operation = LDB_OP_PRESENT;
 403                         ret->u.present.attr = attr;
 404                         break;
 405
 406                 case LDB_OP_EQUALITY:
 407
 408                         if (strcmp(value, "*") == 0) {
 409                                 ret->operation = LDB_OP_PRESENT;
 410                                 ret->u.present.attr = attr;
 411                                 break;
 412                         }
 413
 414                         if (ldb_parse_find_wildcard(value) != NULL) {
 415                                 ret->operation = LDB_OP_SUBSTRING;
 416                                 ret->u.substring.attr = attr;
 417                                 ret->u.substring.start_with_wildcard = 0;
 418                                 ret->u.substring.end_with_wildcard = 0;
 419                                 ret->u.substring.chunks = ldb_wildcard_decode(ret, value);
 420                                 if (ret->u.substring.chunks == NULL){
 421                                         talloc_free(ret);
 422                                         return NULL;
 423                                 }
 424                                 if (value[0] == '*')
 425                                         ret->u.substring.start_with_wildcard = 1;
 426                                 if (value[strlen(value) - 1] == '*')
 427                                         ret->u.substring.end_with_wildcard = 1;
 428                                 talloc_free(value);
 429
 430                                 break;
 431                         }
 432
 433                         ret->operation = LDB_OP_EQUALITY;
 434                         ret->u.equality.attr = attr;
 435                         ret->u.equality.value = ldb_binary_decode(ret, value);
 436                         if (ret->u.equality.value.data == NULL) {
 437                                 talloc_free(ret);
 438                                 return NULL;
 439                         }
 440                         talloc_free(value);
 441                         break;
 442
 443                 case LDB_OP_GREATER:
 444                         ret->operation = LDB_OP_GREATER;
 445                         ret->u.comparison.attr = attr;
 446                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 447                         if (ret->u.comparison.value.data == NULL) {
 448                                 talloc_free(ret);
 449                                 return NULL;
 450                         }
 451                         talloc_free(value);
 452                         break;
 453
 454                 case LDB_OP_LESS:
 455                         ret->operation = LDB_OP_LESS;
 456                         ret->u.comparison.attr = attr;
 457                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 458                         if (ret->u.comparison.value.data == NULL) {
 459                                 talloc_free(ret);
 460                                 return NULL;
 461                         }
 462                         talloc_free(value);
 463                         break;
 464
 465                 case LDB_OP_APPROX:
 466                         ret->operation = LDB_OP_APPROX;
 467                         ret->u.comparison.attr = attr;
 468                         ret->u.comparison.value = ldb_binary_decode(ret, value);
 469                         if (ret->u.comparison.value.data == NULL) {
 470                                 talloc_free(ret);
 471                                 return NULL;
 472                         }
 473                         talloc_free(value);
 474                         break;
 475
 476                 case LDB_OP_EXTENDED:
 477
 478                         ret = ldb_parse_extended(ret, attr, value);
 479                         break;
 480
 481                 default:
 482                         talloc_free(ret);
 483                         return NULL;
 484         }
 485
 486         return ret;
 487 }
 488
 489 /*
 490   parse a filterlist
 491   <and> ::= '&' <filterlist>
 492   <or> ::= '|' <filterlist>
 493   <filterlist> ::= <filter> | <filter> <filterlist>
 494 */
 495 static struct ldb_parse_tree *ldb_parse_filterlist(void *mem_ctx, const char **s)
 496 {
 497         struct ldb_parse_tree *ret, *next;
 498         enum ldb_parse_op op;
 499         const char *p = *s;
 500
 501         switch (*p) {
 502                 case '&':
 503                         op = LDB_OP_AND;
 504                         break;
 505                 case '|':
 506                         op = LDB_OP_OR;
 507                         break;
 508                 default:
 509                         return NULL;
 510         }
 511         p++;
 512
 513         while (isspace((unsigned char)*p)) p++;
 514
 515         ret = talloc(mem_ctx, struct ldb_parse_tree);
 516         if (!ret) {
 517                 errno = ENOMEM;
 518                 return NULL;
 519         }
 520
 521         ret->operation = op;
 522         ret->u.list.num_elements = 1;
 523         ret->u.list.elements = talloc(ret, struct ldb_parse_tree *);
 524         if (!ret->u.list.elements) {
 525                 errno = ENOMEM;
 526                 talloc_free(ret);
 527                 return NULL;
 528         }
 529
 530         ret->u.list.elements[0] = ldb_parse_filter(ret->u.list.elements, &p);
 531         if (!ret->u.list.elements[0]) {
 532                 talloc_free(ret);
 533                 return NULL;
 534         }
 535
 536         while (isspace((unsigned char)*p)) p++;
 537
 538         while (*p && (next = ldb_parse_filter(ret->u.list.elements, &p))) {
 539                 struct ldb_parse_tree **e;
 540                 e = talloc_realloc(ret, ret->u.list.elements,
 541                                      struct ldb_parse_tree *,
 542                                      ret->u.list.num_elements + 1);
 543                 if (!e) {
 544                         errno = ENOMEM;
 545                         talloc_free(ret);
 546                         return NULL;
 547                 }
 548                 ret->u.list.elements = e;
 549                 ret->u.list.elements[ret->u.list.num_elements] = next;
 550                 ret->u.list.num_elements++;
 551                 while (isspace((unsigned char)*p)) p++;
 552         }
 553
 554         *s = p;
 555
 556         return ret;
 557 }
 558
 559 /*
 560   <not> ::= '!' <filter>
 561 */
 562 static struct ldb_parse_tree *ldb_parse_not(void *mem_ctx, const char **s)
 563 {
 564         struct ldb_parse_tree *ret;
 565         const char *p = *s;
 566
 567         if (*p != '!') {
 568                 return NULL;
 569         }
 570         p++;
 571
 572         ret = talloc(mem_ctx, struct ldb_parse_tree);
 573         if (!ret) {
 574                 errno = ENOMEM;
 575                 return NULL;
 576         }
 577
 578         ret->operation = LDB_OP_NOT;
 579         ret->u.isnot.child = ldb_parse_filter(ret, &p);
 580         if (!ret->u.isnot.child) {
 581                 talloc_free(ret);
 582                 return NULL;
 583         }
 584
 585         *s = p;
 586
 587         return ret;
 588 }
 589
 590
 591
 592 /*
 593   parse a filtercomp
 594   <filtercomp> ::= <and> | <or> | <not> | <simple>
 595 */
 596 static struct ldb_parse_tree *ldb_parse_filtercomp(void *mem_ctx, const char **s)
 597 {
 598         struct ldb_parse_tree *ret;
 599         const char *p = *s;
 600
 601         while (isspace((unsigned char)*p)) p++;
 602
 603         switch (*p) {
 604         case '&':
 605                 ret = ldb_parse_filterlist(mem_ctx, &p);
 606                 break;
 607
 608         case '|':
 609                 ret = ldb_parse_filterlist(mem_ctx, &p);
 610                 break;
 611
 612         case '!':
 613                 ret = ldb_parse_not(mem_ctx, &p);
 614                 break;
 615
 616         case '(':
 617         case ')':
 618                 return NULL;
 619
 620         default:
 621                 ret = ldb_parse_simple(mem_ctx, &p);
 622
 623         }
 624
 625         *s = p;
 626         return ret;
 627 }
 628
 629
 630
 631 /*
 632   <filter> ::= '(' <filtercomp> ')'
 633 */
 634 static struct ldb_parse_tree *ldb_parse_filter(void *mem_ctx, const char **s)
 635 {
 636         struct ldb_parse_tree *ret;
 637         const char *p = *s;
 638
 639         if (*p != '(') {
 640                 return NULL;
 641         }
 642         p++;
 643
 644         ret = ldb_parse_filtercomp(mem_ctx, &p);
 645
 646         if (*p != ')') {
 647                 return NULL;
 648         }
 649         p++;
 650
 651         while (isspace((unsigned char)*p)) {
 652                 p++;
 653         }
 654
 655         *s = p;
 656
 657         return ret;
 658 }
 659
 660
 661
 662 /*
 663   main parser entry point. Takes a search string and returns a parse tree
 664
 665   expression ::= <simple> | <filter>
 666 */
 667 struct ldb_parse_tree *ldb_parse_tree(void *mem_ctx, const char *s)
 668 {
 669         if (s == NULL || *s == 0) {
 670                 s = "(|(objectClass=*)(distinguishedName=*))";
 671         }
 672
 673         while (isspace((unsigned char)*s)) s++;
 674
 675         if (*s == '(') {
 676                 return ldb_parse_filter(mem_ctx, &s);
 677         }
 678
 679         return ldb_parse_simple(mem_ctx, &s);
 680 }
 681
 682