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