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