source4/lib/ldb/ldb_map/ldb_map_outbound.c

   1 /*
   2    ldb database mapping module
   3
   4    Copyright (C) Jelmer Vernooij 2005
   5    Copyright (C) Martin Kuehl <mkhl@samba.org> 2006
   6    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2006
   7    Copyright (C) Simo Sorce <idra@samba.org> 2008
   8
   9      ** NOTE! The following LGPL license applies to the ldb
  10      ** library. This does NOT imply that all of Samba is released
  11      ** under the LGPL
  12
  13    This library is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU Lesser General Public
  15    License as published by the Free Software Foundation; either
  16    version 3 of the License, or (at your option) any later version.
  17
  18    This library is distributed in the hope that it will be useful,
  19    but WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    Lesser General Public License for more details.
  22
  23    You should have received a copy of the GNU Lesser General Public
  24    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  25
  26 */
  27
  28 #include "ldb_module.h"
  29 #include "ldb_private.h"
  30
  31 #include "ldb_map.h"
  32 #include "ldb_map_private.h"
  33
  34
  35 /* Mapping attributes
  36  * ================== */
  37
  38 /* Select attributes that stay in the local partition. */
  39 static const char **map_attrs_select_local(struct ldb_module *module, void *mem_ctx, const char * const *attrs)
  40 {
  41         const struct ldb_map_context *data = map_get_context(module);
  42         const char **result;
  43         int i, last;
  44
  45         if (attrs == NULL)
  46                 return NULL;
  47
  48         last = 0;
  49         result = talloc_array(mem_ctx, const char *, 1);
  50         if (result == NULL) {
  51                 goto failed;
  52         }
  53         result[0] = NULL;
  54
  55         for (i = 0; attrs[i]; i++) {
  56                 /* Wildcards and ignored attributes are kept locally */
  57                 if ((ldb_attr_cmp(attrs[i], "*") == 0) ||
  58                     (!map_attr_check_remote(data, attrs[i]))) {
  59                         result = talloc_realloc(mem_ctx, result, const char *, last+2);
  60                         if (result == NULL) {
  61                                 goto failed;
  62                         }
  63
  64                         result[last] = talloc_strdup(result, attrs[i]);
  65                         result[last+1] = NULL;
  66                         last++;
  67                 }
  68         }
  69
  70         return result;
  71
  72 failed:
  73         talloc_free(result);
  74         map_oom(module);
  75         return NULL;
  76 }
  77
  78 /* Collect attributes that are mapped into the remote partition. */
  79 static const char **map_attrs_collect_remote(struct ldb_module *module, void *mem_ctx,
  80                                              const char * const *attrs)
  81 {
  82         const struct ldb_map_context *data = map_get_context(module);
  83         const char **result;
  84         const struct ldb_map_attribute *map;
  85         const char *name=NULL;
  86         int i, j, last;
  87         int ret;
  88
  89         last = 0;
  90         result = talloc_array(mem_ctx, const char *, 1);
  91         if (result == NULL) {
  92                 goto failed;
  93         }
  94         result[0] = NULL;
  95
  96         for (i = 0; attrs[i]; i++) {
  97                 /* Wildcards are kept remotely, too */
  98                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
  99                         const char **new_attrs = NULL;
 100                         ret = map_attrs_merge(module, mem_ctx, &new_attrs, attrs);
 101                         if (ret != LDB_SUCCESS) {
 102                                 goto failed;
 103                         }
 104                         ret = map_attrs_merge(module, mem_ctx, &new_attrs, data->wildcard_attributes);
 105                         if (ret != LDB_SUCCESS) {
 106                                 goto failed;
 107                         }
 108
 109                         attrs = new_attrs;
 110                         break;
 111                 }
 112         }
 113
 114         for (i = 0; attrs[i]; i++) {
 115                 /* Wildcards are kept remotely, too */
 116                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
 117                         /* Add all 'include in wildcard' attributes */
 118                         name = attrs[i];
 119                         goto named;
 120                 }
 121
 122                 /* Add remote names of mapped attrs */
 123                 map = map_attr_find_local(data, attrs[i]);
 124                 if (map == NULL) {
 125                         continue;
 126                 }
 127
 128                 switch (map->type) {
 129                 case MAP_IGNORE:
 130                         continue;
 131
 132                 case MAP_KEEP:
 133                         name = attrs[i];
 134                         goto named;
 135
 136                 case MAP_RENAME:
 137                 case MAP_CONVERT:
 138                         name = map->u.rename.remote_name;
 139                         goto named;
 140
 141                 case MAP_GENERATE:
 142                         /* Add all remote names of "generate" attrs */
 143                         for (j = 0; map->u.generate.remote_names[j]; j++) {
 144                                 result = talloc_realloc(mem_ctx, result, const char *, last+2);
 145                                 if (result == NULL) {
 146                                         goto failed;
 147                                 }
 148
 149                                 result[last] = talloc_strdup(result, map->u.generate.remote_names[j]);
 150                                 result[last+1] = NULL;
 151                                 last++;
 152                         }
 153                         continue;
 154                 }
 155
 156         named:  /* We found a single remote name, add that */
 157                 result = talloc_realloc(mem_ctx, result, const char *, last+2);
 158                 if (result == NULL) {
 159                         goto failed;
 160                 }
 161
 162                 result[last] = talloc_strdup(result, name);
 163                 result[last+1] = NULL;
 164                 last++;
 165         }
 166
 167         return result;
 168
 169 failed:
 170         talloc_free(result);
 171         map_oom(module);
 172         return NULL;
 173 }
 174
 175 /* Split attributes that stay in the local partition from those that
 176  * are mapped into the remote partition. */
 177 static int map_attrs_partition(struct ldb_module *module, void *mem_ctx, const char ***local_attrs, const char ***remote_attrs, const char * const *attrs)
 178 {
 179         *local_attrs = map_attrs_select_local(module, mem_ctx, attrs);
 180         *remote_attrs = map_attrs_collect_remote(module, mem_ctx, attrs);
 181
 182         return 0;
 183 }
 184
 185 /* Mapping message elements
 186  * ======================== */
 187
 188 /* Add an element to a message, overwriting any old identically named elements. */
 189 static int ldb_msg_replace(struct ldb_message *msg, const struct ldb_message_element *el)
 190 {
 191         struct ldb_message_element *old;
 192
 193         old = ldb_msg_find_element(msg, el->name);
 194
 195         /* no local result, add as new element */
 196         if (old == NULL) {
 197                 if (ldb_msg_add_empty(msg, el->name, 0, &old) != 0) {
 198                         return -1;
 199                 }
 200                 talloc_free(discard_const_p(char, old->name));
 201         }
 202
 203         /* copy new element */
 204         *old = *el;
 205
 206         /* and make sure we reference the contents */
 207         if (!talloc_reference(msg->elements, el->name)) {
 208                 return -1;
 209         }
 210         if (!talloc_reference(msg->elements, el->values)) {
 211                 return -1;
 212         }
 213
 214         return 0;
 215 }
 216
 217 /* Map a message element back into the local partition. */
 218 static struct ldb_message_element *ldb_msg_el_map_remote(struct ldb_module *module,
 219                                                          void *mem_ctx,
 220                                                          const struct ldb_map_attribute *map,
 221                                                          const char *attr_name,
 222                                                          const struct ldb_message_element *old)
 223 {
 224         struct ldb_message_element *el;
 225         int i;
 226
 227         el = talloc_zero(mem_ctx, struct ldb_message_element);
 228         if (el == NULL) {
 229                 map_oom(module);
 230                 return NULL;
 231         }
 232
 233         el->values = talloc_array(el, struct ldb_val, old->num_values);
 234         if (el->values == NULL) {
 235                 talloc_free(el);
 236                 map_oom(module);
 237                 return NULL;
 238         }
 239
 240         el->name = talloc_strdup(el, attr_name);
 241         if (el->name == NULL) {
 242                 talloc_free(el);
 243                 map_oom(module);
 244                 return NULL;
 245         }
 246
 247         for (i = 0; i < old->num_values; i++) {
 248                 el->values[i] = ldb_val_map_remote(module, el->values, map, &old->values[i]);
 249                 /* Conversions might fail, in which case bail */
 250                 if (!el->values[i].data) {
 251                         talloc_free(el);
 252                         return NULL;
 253                 }
 254                 el->num_values++;
 255         }
 256
 257         return el;
 258 }
 259
 260 /* Merge a remote message element into a local message. */
 261 static int ldb_msg_el_merge(struct ldb_module *module, struct ldb_message *local,
 262                             struct ldb_message *remote, const char *attr_name)
 263 {
 264         const struct ldb_map_context *data = map_get_context(module);
 265         const struct ldb_map_attribute *map;
 266         struct ldb_message_element *old, *el=NULL;
 267         const char *remote_name = NULL;
 268         struct ldb_context *ldb;
 269
 270         ldb = ldb_module_get_ctx(module);
 271
 272         /* We handle wildcards in ldb_msg_el_merge_wildcard */
 273         if (ldb_attr_cmp(attr_name, "*") == 0) {
 274                 return LDB_SUCCESS;
 275         }
 276
 277         map = map_attr_find_local(data, attr_name);
 278
 279         /* Unknown attribute in remote message:
 280          * skip, attribute was probably auto-generated */
 281         if (map == NULL) {
 282                 return LDB_SUCCESS;
 283         }
 284
 285         switch (map->type) {
 286         case MAP_IGNORE:
 287                 break;
 288         case MAP_CONVERT:
 289                 remote_name = map->u.convert.remote_name;
 290                 break;
 291         case MAP_KEEP:
 292                 remote_name = attr_name;
 293                 break;
 294         case MAP_RENAME:
 295                 remote_name = map->u.rename.remote_name;
 296                 break;
 297         case MAP_GENERATE:
 298                 break;
 299         }
 300
 301         switch (map->type) {
 302         case MAP_IGNORE:
 303                 return LDB_SUCCESS;
 304
 305         case MAP_CONVERT:
 306                 if (map->u.convert.convert_remote == NULL) {
 307                         ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb_map: "
 308                                   "Skipping attribute '%s': "
 309                                   "'convert_remote' not set\n",
 310                                   attr_name);
 311                         return LDB_SUCCESS;
 312                 }
 313                 /* fall through */
 314         case MAP_KEEP:
 315         case MAP_RENAME:
 316                 old = ldb_msg_find_element(remote, remote_name);
 317                 if (old) {
 318                         el = ldb_msg_el_map_remote(module, local, map, attr_name, old);
 319                 } else {
 320                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
 321                 }
 322                 break;
 323
 324         case MAP_GENERATE:
 325                 if (map->u.generate.generate_local == NULL) {
 326                         ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb_map: "
 327                                   "Skipping attribute '%s': "
 328                                   "'generate_local' not set\n",
 329                                   attr_name);
 330                         return LDB_SUCCESS;
 331                 }
 332
 333                 el = map->u.generate.generate_local(module, local, attr_name, remote);
 334                 if (!el) {
 335                         /* Generation failure is probably due to lack of source attributes */
 336                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
 337                 }
 338                 break;
 339         }
 340
 341         if (el == NULL) {
 342                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
 343         }
 344
 345         return ldb_msg_replace(local, el);
 346 }
 347
 348 /* Handle wildcard parts of merging a remote message element into a local message. */
 349 static int ldb_msg_el_merge_wildcard(struct ldb_module *module, struct ldb_message *local,
 350                                      struct ldb_message *remote)
 351 {
 352         const struct ldb_map_context *data = map_get_context(module);
 353         const struct ldb_map_attribute *map = map_attr_find_local(data, "*");
 354         struct ldb_message_element *el=NULL;
 355         int i, ret;
 356
 357         /* Perhaps we have a mapping for "*" */
 358         if (map && map->type == MAP_KEEP) {
 359                 /* We copy everything over, and hope that anything with a
 360                    more specific rule is overwritten */
 361                 for (i = 0; i < remote->num_elements; i++) {
 362                         el = ldb_msg_el_map_remote(module, local, map, remote->elements[i].name,
 363                                                    &remote->elements[i]);
 364                         if (el == NULL) {
 365                                 return LDB_ERR_OPERATIONS_ERROR;
 366                         }
 367
 368                         ret = ldb_msg_replace(local, el);
 369                         if (ret) {
 370                                 return ret;
 371                         }
 372                 }
 373         }
 374
 375         /* Now walk the list of possible mappings, and apply each */
 376         for (i = 0; data->attribute_maps[i].local_name; i++) {
 377                 ret = ldb_msg_el_merge(module, local, remote,
 378                                        data->attribute_maps[i].local_name);
 379                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
 380                         continue;
 381                 } else if (ret) {
 382                         return ret;
 383                 } else {
 384                         continue;
 385                 }
 386         }
 387
 388         return LDB_SUCCESS;
 389 }
 390
 391 /* Mapping messages
 392  * ================ */
 393
 394 /* Merge two local messages into a single one. */
 395 static int ldb_msg_merge_local(struct ldb_module *module, struct ldb_message *msg1, struct ldb_message *msg2)
 396 {
 397         int i, ret;
 398
 399         for (i = 0; i < msg2->num_elements; i++) {
 400                 ret = ldb_msg_replace(msg1, &msg2->elements[i]);
 401                 if (ret) {
 402                         return ret;
 403                 }
 404         }
 405
 406         return LDB_SUCCESS;
 407 }
 408
 409 /* Merge a local and a remote message into a single local one. */
 410 static int ldb_msg_merge_remote(struct map_context *ac, struct ldb_message *local,
 411                                 struct ldb_message *remote)
 412 {
 413         int i, ret;
 414         const char * const *attrs = ac->all_attrs;
 415         if (!attrs) {
 416                 ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
 417                 if (ret) {
 418                         return ret;
 419                 }
 420         }
 421
 422         for (i = 0; attrs && attrs[i]; i++) {
 423                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
 424                         ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
 425                         if (ret) {
 426                                 return ret;
 427                         }
 428                         break;
 429                 }
 430         }
 431
 432         /* Try to map each attribute back;
 433          * Add to local message is possible,
 434          * Overwrite old local attribute if necessary */
 435         for (i = 0; attrs && attrs[i]; i++) {
 436                 ret = ldb_msg_el_merge(ac->module, local, remote,
 437                                        attrs[i]);
 438                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
 439                 } else if (ret) {
 440                         return ret;
 441                 }
 442         }
 443
 444         return LDB_SUCCESS;
 445 }
 446
 447 /* Mapping search results
 448  * ====================== */
 449
 450 /* Map a search result back into the local partition. */
 451 static int map_reply_remote(struct map_context *ac, struct ldb_reply *ares)
 452 {
 453         struct ldb_message *msg;
 454         struct ldb_dn *dn;
 455         int ret;
 456
 457         /* There is no result message, skip */
 458         if (ares->type != LDB_REPLY_ENTRY) {
 459                 return 0;
 460         }
 461
 462         /* Create a new result message */
 463         msg = ldb_msg_new(ares);
 464         if (msg == NULL) {
 465                 map_oom(ac->module);
 466                 return -1;
 467         }
 468
 469         /* Merge remote message into new message */
 470         ret = ldb_msg_merge_remote(ac, msg, ares->message);
 471         if (ret) {
 472                 talloc_free(msg);
 473                 return ret;
 474         }
 475
 476         /* Create corresponding local DN */
 477         dn = ldb_dn_map_rebase_remote(ac->module, msg, ares->message->dn);
 478         if (dn == NULL) {
 479                 talloc_free(msg);
 480                 return -1;
 481         }
 482         msg->dn = dn;
 483
 484         /* Store new message with new DN as the result */
 485         talloc_free(ares->message);
 486         ares->message = msg;
 487
 488         return 0;
 489 }
 490
 491 /* Mapping parse trees
 492  * =================== */
 493
 494 /* Check whether a parse tree can safely be split in two. */
 495 static bool ldb_parse_tree_check_splittable(const struct ldb_parse_tree *tree)
 496 {
 497         const struct ldb_parse_tree *subtree = tree;
 498         bool negate = false;
 499
 500         while (subtree) {
 501                 switch (subtree->operation) {
 502                 case LDB_OP_NOT:
 503                         negate = !negate;
 504                         subtree = subtree->u.isnot.child;
 505                         continue;
 506
 507                 case LDB_OP_AND:
 508                         return !negate; /* if negate: False */
 509
 510                 case LDB_OP_OR:
 511                         return negate;  /* if negate: True */
 512
 513                 default:
 514                         return true;    /* simple parse tree */
 515                 }
 516         }
 517
 518         return true;                    /* no parse tree */
 519 }
 520
 521 /* Collect a list of attributes required to match a given parse tree. */
 522 static int ldb_parse_tree_collect_attrs(struct ldb_module *module, void *mem_ctx, const char ***attrs, const struct ldb_parse_tree *tree)
 523 {
 524         const char **new_attrs;
 525         int i, ret;
 526
 527         if (tree == NULL) {
 528                 return 0;
 529         }
 530
 531         switch (tree->operation) {
 532         case LDB_OP_OR:
 533         case LDB_OP_AND:                /* attributes stored in list of subtrees */
 534                 for (i = 0; i < tree->u.list.num_elements; i++) {
 535                         ret = ldb_parse_tree_collect_attrs(module, mem_ctx,
 536                                                            attrs, tree->u.list.elements[i]);
 537                         if (ret) {
 538                                 return ret;
 539                         }
 540                 }
 541                 return 0;
 542
 543         case LDB_OP_NOT:                /* attributes stored in single subtree */
 544                 return ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.isnot.child);
 545
 546         default:                        /* single attribute in tree */
 547                 new_attrs = ldb_attr_list_copy_add(mem_ctx, *attrs, tree->u.equality.attr);
 548                 talloc_free(*attrs);
 549                 *attrs = new_attrs;
 550                 return 0;
 551         }
 552
 553         return -1;
 554 }
 555
 556 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
 557
 558 /* Select a negated subtree that queries attributes in the local partition */
 559 static int map_subtree_select_local_not(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 560 {
 561         struct ldb_parse_tree *child;
 562         int ret;
 563
 564         /* Prepare new tree */
 565         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 566         if (*new == NULL) {
 567                 map_oom(module);
 568                 return -1;
 569         }
 570
 571         /* Generate new subtree */
 572         ret = map_subtree_select_local(module, *new, &child, tree->u.isnot.child);
 573         if (ret) {
 574                 talloc_free(*new);
 575                 return ret;
 576         }
 577
 578         /* Prune tree without subtree */
 579         if (child == NULL) {
 580                 talloc_free(*new);
 581                 *new = NULL;
 582                 return 0;
 583         }
 584
 585         (*new)->u.isnot.child = child;
 586
 587         return ret;
 588 }
 589
 590 /* Select a list of subtrees that query attributes in the local partition */
 591 static int map_subtree_select_local_list(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 592 {
 593         int i, j, ret=0;
 594
 595         /* Prepare new tree */
 596         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 597         if (*new == NULL) {
 598                 map_oom(module);
 599                 return -1;
 600         }
 601
 602         /* Prepare list of subtrees */
 603         (*new)->u.list.num_elements = 0;
 604         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
 605         if ((*new)->u.list.elements == NULL) {
 606                 map_oom(module);
 607                 talloc_free(*new);
 608                 return -1;
 609         }
 610
 611         /* Generate new list of subtrees */
 612         j = 0;
 613         for (i = 0; i < tree->u.list.num_elements; i++) {
 614                 struct ldb_parse_tree *child;
 615                 ret = map_subtree_select_local(module, *new, &child, tree->u.list.elements[i]);
 616                 if (ret) {
 617                         talloc_free(*new);
 618                         return ret;
 619                 }
 620
 621                 if (child) {
 622                         (*new)->u.list.elements[j] = child;
 623                         j++;
 624                 }
 625         }
 626
 627         /* Prune tree without subtrees */
 628         if (j == 0) {
 629                 talloc_free(*new);
 630                 *new = NULL;
 631                 return 0;
 632         }
 633
 634         /* Fix subtree list size */
 635         (*new)->u.list.num_elements = j;
 636         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
 637
 638         return ret;
 639 }
 640
 641 /* Select a simple subtree that queries attributes in the local partition */
 642 static int map_subtree_select_local_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 643 {
 644         /* Prepare new tree */
 645         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 646         if (*new == NULL) {
 647                 map_oom(module);
 648                 return -1;
 649         }
 650
 651         return 0;
 652 }
 653
 654 /* Select subtrees that query attributes in the local partition */
 655 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 656 {
 657         const struct ldb_map_context *data = map_get_context(module);
 658
 659         if (tree == NULL) {
 660                 return 0;
 661         }
 662
 663         if (tree->operation == LDB_OP_NOT) {
 664                 return map_subtree_select_local_not(module, mem_ctx, new, tree);
 665         }
 666
 667         if (tree->operation == LDB_OP_AND || tree->operation == LDB_OP_OR) {
 668                 return map_subtree_select_local_list(module, mem_ctx, new, tree);
 669         }
 670
 671         if (map_attr_check_remote(data, tree->u.equality.attr)) {
 672                 *new = NULL;
 673                 return 0;
 674         }
 675
 676         return map_subtree_select_local_simple(module, mem_ctx, new, tree);
 677 }
 678
 679 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
 680
 681 /* Collect a negated subtree that queries attributes in the remote partition */
 682 static int map_subtree_collect_remote_not(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 683 {
 684         struct ldb_parse_tree *child;
 685         int ret;
 686
 687         /* Prepare new tree */
 688         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 689         if (*new == NULL) {
 690                 map_oom(module);
 691                 return -1;
 692         }
 693
 694         /* Generate new subtree */
 695         ret = map_subtree_collect_remote(module, *new, &child, tree->u.isnot.child);
 696         if (ret) {
 697                 talloc_free(*new);
 698                 return ret;
 699         }
 700
 701         /* Prune tree without subtree */
 702         if (child == NULL) {
 703                 talloc_free(*new);
 704                 *new = NULL;
 705                 return 0;
 706         }
 707
 708         (*new)->u.isnot.child = child;
 709
 710         return ret;
 711 }
 712
 713 /* Collect a list of subtrees that query attributes in the remote partition */
 714 static int map_subtree_collect_remote_list(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 715 {
 716         int i, j, ret=0;
 717
 718         /* Prepare new tree */
 719         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 720         if (*new == NULL) {
 721                 map_oom(module);
 722                 return -1;
 723         }
 724
 725         /* Prepare list of subtrees */
 726         (*new)->u.list.num_elements = 0;
 727         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
 728         if ((*new)->u.list.elements == NULL) {
 729                 map_oom(module);
 730                 talloc_free(*new);
 731                 return -1;
 732         }
 733
 734         /* Generate new list of subtrees */
 735         j = 0;
 736         for (i = 0; i < tree->u.list.num_elements; i++) {
 737                 struct ldb_parse_tree *child;
 738                 ret = map_subtree_collect_remote(module, *new, &child, tree->u.list.elements[i]);
 739                 if (ret) {
 740                         talloc_free(*new);
 741                         return ret;
 742                 }
 743
 744                 if (child) {
 745                         (*new)->u.list.elements[j] = child;
 746                         j++;
 747                 }
 748         }
 749
 750         /* Prune tree without subtrees */
 751         if (j == 0) {
 752                 talloc_free(*new);
 753                 *new = NULL;
 754                 return 0;
 755         }
 756
 757         /* Fix subtree list size */
 758         (*new)->u.list.num_elements = j;
 759         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
 760
 761         return ret;
 762 }
 763
 764 /* Collect a simple subtree that queries attributes in the remote partition */
 765 int map_subtree_collect_remote_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree, const struct ldb_map_attribute *map)
 766 {
 767         const char *attr;
 768
 769         /* Prepare new tree */
 770         *new = talloc(mem_ctx, struct ldb_parse_tree);
 771         if (*new == NULL) {
 772                 map_oom(module);
 773                 return -1;
 774         }
 775         **new = *tree;
 776
 777         if (map->type == MAP_KEEP) {
 778                 /* Nothing to do here */
 779                 return 0;
 780         }
 781
 782         /* Store attribute and value in new tree */
 783         switch (tree->operation) {
 784         case LDB_OP_PRESENT:
 785                 attr = map_attr_map_local(*new, map, tree->u.present.attr);
 786                 (*new)->u.present.attr = attr;
 787                 break;
 788         case LDB_OP_SUBSTRING:
 789         {
 790                 attr = map_attr_map_local(*new, map, tree->u.substring.attr);
 791                 (*new)->u.substring.attr = attr;
 792                 break;
 793         }
 794         case LDB_OP_EQUALITY:
 795                 attr = map_attr_map_local(*new, map, tree->u.equality.attr);
 796                 (*new)->u.equality.attr = attr;
 797                 break;
 798         case LDB_OP_LESS:
 799         case LDB_OP_GREATER:
 800         case LDB_OP_APPROX:
 801                 attr = map_attr_map_local(*new, map, tree->u.comparison.attr);
 802                 (*new)->u.comparison.attr = attr;
 803                 break;
 804         case LDB_OP_EXTENDED:
 805                 attr = map_attr_map_local(*new, map, tree->u.extended.attr);
 806                 (*new)->u.extended.attr = attr;
 807                 break;
 808         default:                        /* unknown kind of simple subtree */
 809                 talloc_free(*new);
 810                 return -1;
 811         }
 812
 813         if (attr == NULL) {
 814                 talloc_free(*new);
 815                 *new = NULL;
 816                 return 0;
 817         }
 818
 819         if (map->type == MAP_RENAME) {
 820                 /* Nothing more to do here, the attribute has been renamed */
 821                 return 0;
 822         }
 823
 824         /* Store attribute and value in new tree */
 825         switch (tree->operation) {
 826         case LDB_OP_PRESENT:
 827                 break;
 828         case LDB_OP_SUBSTRING:
 829         {
 830                 int i;
 831                 /* Map value */
 832                 (*new)->u.substring.chunks = NULL;
 833                 for (i=0; tree->u.substring.chunks[i]; i++) {
 834                         (*new)->u.substring.chunks = talloc_realloc(*new, (*new)->u.substring.chunks, struct ldb_val *, i+2);
 835                         if (!(*new)->u.substring.chunks) {
 836                                 talloc_free(*new);
 837                                 *new = NULL;
 838                                 return 0;
 839                         }
 840                         (*new)->u.substring.chunks[i] = talloc(*new, struct ldb_val);
 841                         if (!(*new)->u.substring.chunks[i]) {
 842                                 talloc_free(*new);
 843                                 *new = NULL;
 844                                 return 0;
 845                         }
 846                         *(*new)->u.substring.chunks[i] = ldb_val_map_local(module, *new, map, tree->u.substring.chunks[i]);
 847                         (*new)->u.substring.chunks[i+1] = NULL;
 848                 }
 849                 break;
 850         }
 851         case LDB_OP_EQUALITY:
 852                 (*new)->u.equality.value = ldb_val_map_local(module, *new, map, &tree->u.equality.value);
 853                 break;
 854         case LDB_OP_LESS:
 855         case LDB_OP_GREATER:
 856         case LDB_OP_APPROX:
 857                 (*new)->u.comparison.value = ldb_val_map_local(module, *new, map, &tree->u.comparison.value);
 858                 break;
 859         case LDB_OP_EXTENDED:
 860                 (*new)->u.extended.value = ldb_val_map_local(module, *new, map, &tree->u.extended.value);
 861                 (*new)->u.extended.rule_id = talloc_strdup(*new, tree->u.extended.rule_id);
 862                 break;
 863         default:                        /* unknown kind of simple subtree */
 864                 talloc_free(*new);
 865                 return -1;
 866         }
 867
 868         return 0;
 869 }
 870
 871 /* Collect subtrees that query attributes in the remote partition */
 872 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 873 {
 874         const struct ldb_map_context *data = map_get_context(module);
 875         const struct ldb_map_attribute *map;
 876         struct ldb_context *ldb;
 877
 878         ldb = ldb_module_get_ctx(module);
 879
 880         if (tree == NULL) {
 881                 return 0;
 882         }
 883
 884         if (tree->operation == LDB_OP_NOT) {
 885                 return map_subtree_collect_remote_not(module, mem_ctx, new, tree);
 886         }
 887
 888         if ((tree->operation == LDB_OP_AND) || (tree->operation == LDB_OP_OR)) {
 889                 return map_subtree_collect_remote_list(module, mem_ctx, new, tree);
 890         }
 891
 892         if (!map_attr_check_remote(data, tree->u.equality.attr)) {
 893                 *new = NULL;
 894                 return 0;
 895         }
 896
 897         map = map_attr_find_local(data, tree->u.equality.attr);
 898         if (map->convert_operator) {
 899                 return map->convert_operator(module, mem_ctx, new, tree);
 900         }
 901
 902         if (map->type == MAP_GENERATE) {
 903                 ldb_debug(ldb, LDB_DEBUG_WARNING, "ldb_map: "
 904                           "Skipping attribute '%s': "
 905                           "'convert_operator' not set\n",
 906                           tree->u.equality.attr);
 907                 *new = NULL;
 908                 return 0;
 909         }
 910
 911         return map_subtree_collect_remote_simple(module, mem_ctx, new, tree, map);
 912 }
 913
 914 /* Split subtrees that query attributes in the local partition from
 915  * those that query the remote partition. */
 916 static int ldb_parse_tree_partition(struct ldb_module *module,
 917                                         void *mem_ctx,
 918                                         struct ldb_parse_tree **local_tree,
 919                                         struct ldb_parse_tree **remote_tree,
 920                                         const struct ldb_parse_tree *tree)
 921 {
 922         int ret;
 923
 924         *local_tree = NULL;
 925         *remote_tree = NULL;
 926
 927         /* No original tree */
 928         if (tree == NULL) {
 929                 return 0;
 930         }
 931
 932         /* Generate local tree */
 933         ret = map_subtree_select_local(module, mem_ctx, local_tree, tree);
 934         if (ret) {
 935                 return ret;
 936         }
 937
 938         /* Generate remote tree */
 939         ret = map_subtree_collect_remote(module, mem_ctx, remote_tree, tree);
 940         if (ret) {
 941                 talloc_free(*local_tree);
 942                 return ret;
 943         }
 944
 945         return 0;
 946 }
 947
 948 /* Collect a list of attributes required either explicitly from a
 949  * given list or implicitly  from a given parse tree; split the
 950  * collected list into local and remote parts. */
 951 static int map_attrs_collect_and_partition(struct ldb_module *module, struct map_context *ac,
 952                                            const char * const *search_attrs,
 953                                            const struct ldb_parse_tree *tree)
 954 {
 955         void *tmp_ctx;
 956         const char **tree_attrs;
 957         const char **remote_attrs;
 958         const char **local_attrs;
 959         int ret;
 960
 961         /* There is no tree, just partition the searched attributes */
 962         if (tree == NULL) {
 963                 ret = map_attrs_partition(module, ac,
 964                                           &local_attrs, &remote_attrs, search_attrs);
 965                 if (ret == 0) {
 966                         ac->local_attrs = local_attrs;
 967                         ac->remote_attrs = remote_attrs;
 968                         ac->all_attrs = search_attrs;
 969                 }
 970                 return ret;
 971         }
 972
 973         /* Create context for temporary memory */
 974         tmp_ctx = talloc_new(ac);
 975         if (tmp_ctx == NULL) {
 976                 goto oom;
 977         }
 978
 979         /* Prepare list of attributes from tree */
 980         tree_attrs = talloc_array(tmp_ctx, const char *, 1);
 981         if (tree_attrs == NULL) {
 982                 talloc_free(tmp_ctx);
 983                 goto oom;
 984         }
 985         tree_attrs[0] = NULL;
 986
 987         /* Collect attributes from tree */
 988         ret = ldb_parse_tree_collect_attrs(module, tmp_ctx, &tree_attrs, tree);
 989         if (ret) {
 990                 goto done;
 991         }
 992
 993         /* Merge attributes from search operation */
 994         ret = map_attrs_merge(module, tmp_ctx, &tree_attrs, search_attrs);
 995         if (ret) {
 996                 goto done;
 997         }
 998
 999         /* Split local from remote attributes */
1000         ret = map_attrs_partition(module, ac, &local_attrs,
1001                                   &remote_attrs, tree_attrs);
1002
1003         if (ret == 0) {
1004                 ac->local_attrs = local_attrs;
1005                 ac->remote_attrs = remote_attrs;
1006                 talloc_steal(ac, tree_attrs);
1007                 ac->all_attrs = tree_attrs;
1008         }
1009 done:
1010         /* Free temporary memory */
1011         talloc_free(tmp_ctx);
1012         return ret;
1013
1014 oom:
1015         map_oom(module);
1016         return -1;
1017 }
1018
1019
1020 /* Outbound requests: search
1021  * ========================= */
1022
1023 static int map_remote_search_callback(struct ldb_request *req,
1024                                         struct ldb_reply *ares);
1025 static int map_local_merge_callback(struct ldb_request *req,
1026                                         struct ldb_reply *ares);
1027 static int map_search_local(struct map_context *ac);
1028
1029 static int map_save_entry(struct map_context *ac, struct ldb_reply *ares)
1030 {
1031         struct map_reply *mr;
1032
1033         mr = talloc_zero(ac, struct map_reply);
1034         if (mr == NULL) {
1035                 map_oom(ac->module);
1036                 return LDB_ERR_OPERATIONS_ERROR;
1037         }
1038         mr->remote = talloc_steal(mr, ares);
1039         if (ac->r_current) {
1040                 ac->r_current->next = mr;
1041         } else {
1042                 /* first entry */
1043                 ac->r_list = mr;
1044         }
1045         ac->r_current = mr;
1046
1047         return LDB_SUCCESS;
1048 }
1049
1050 /* Pass a merged search result up the callback chain. */
1051 int map_return_entry(struct map_context *ac, struct ldb_reply *ares)
1052 {
1053         struct ldb_message_element *el;
1054         const char * const *attrs;
1055         struct ldb_context *ldb;
1056         int i;
1057
1058         ldb = ldb_module_get_ctx(ac->module);
1059
1060         /* Merged result doesn't match original query, skip */
1061         if (!ldb_match_msg(ldb, ares->message,
1062                            ac->req->op.search.tree,
1063                            ac->req->op.search.base,
1064                            ac->req->op.search.scope)) {
1065                 ldb_debug(ldb, LDB_DEBUG_TRACE, "ldb_map: "
1066                           "Skipping record '%s': "
1067                           "doesn't match original search\n",
1068                           ldb_dn_get_linearized(ares->message->dn));
1069                 return LDB_SUCCESS;
1070         }
1071
1072         /* Limit result to requested attrs */
1073         if (ac->req->op.search.attrs &&
1074             (! ldb_attr_in_list(ac->req->op.search.attrs, "*"))) {
1075
1076                 attrs = ac->req->op.search.attrs;
1077                 i = 0;
1078
1079                 while (i < ares->message->num_elements) {
1080
1081                         el = &ares->message->elements[i];
1082                         if ( ! ldb_attr_in_list(attrs, el->name)) {
1083                                 ldb_msg_remove_element(ares->message, el);
1084                         } else {
1085                                 i++;
1086                         }
1087                 }
1088         }
1089
1090         return ldb_module_send_entry(ac->req, ares->message, ares->controls);
1091 }
1092
1093 /* Search a record. */
1094 int map_search(struct ldb_module *module, struct ldb_request *req)
1095 {
1096         struct ldb_parse_tree *remote_tree;
1097         struct ldb_parse_tree *local_tree;
1098         struct ldb_request *remote_req;
1099         struct ldb_context *ldb;
1100         struct map_context *ac;
1101         int ret;
1102
1103         const char *wildcard[] = { "*", NULL };
1104         const char * const *attrs;
1105
1106         ldb = ldb_module_get_ctx(module);
1107
1108         /* if we're not yet initialized, go to the next module */
1109         if (!ldb_module_get_private(module))
1110                 return ldb_next_request(module, req);
1111
1112         /* Do not manipulate our control entries */
1113         if (ldb_dn_is_special(req->op.search.base)) {
1114                 return ldb_next_request(module, req);
1115         }
1116
1117         /* No mapping requested, skip to next module */
1118         if ((req->op.search.base) && (!ldb_dn_check_local(module, req->op.search.base))) {
1119                 return ldb_next_request(module, req);
1120         }
1121
1122         /* TODO: How can we be sure about which partition we are
1123          *       targetting when there is no search base? */
1124
1125         /* Prepare context and handle */
1126         ac = map_init_context(module, req);
1127         if (ac == NULL) {
1128                 return LDB_ERR_OPERATIONS_ERROR;
1129         }
1130
1131         /* It is easier to deal with the two different ways of
1132          * expressing the wildcard in the same codepath */
1133         attrs = req->op.search.attrs;
1134         if (attrs == NULL) {
1135                 attrs = wildcard;
1136         }
1137
1138         /* Split local from remote attrs */
1139         ret = map_attrs_collect_and_partition(module, ac,
1140                                               attrs, req->op.search.tree);
1141         if (ret) {
1142                 return LDB_ERR_OPERATIONS_ERROR;
1143         }
1144
1145         /* Split local from remote tree */
1146         ret = ldb_parse_tree_partition(module, ac,
1147                                        &local_tree, &remote_tree,
1148                                        req->op.search.tree);
1149         if (ret) {
1150                 return LDB_ERR_OPERATIONS_ERROR;
1151         }
1152
1153         if (((local_tree != NULL) && (remote_tree != NULL)) &&
1154             (!ldb_parse_tree_check_splittable(req->op.search.tree))) {
1155                 /* The query can't safely be split, enumerate the remote partition */
1156                 local_tree = NULL;
1157                 remote_tree = NULL;
1158         }
1159
1160         if (local_tree == NULL) {
1161                 /* Construct default local parse tree */
1162                 local_tree = talloc_zero(ac, struct ldb_parse_tree);
1163                 if (local_tree == NULL) {
1164                         map_oom(ac->module);
1165                         return LDB_ERR_OPERATIONS_ERROR;
1166                 }
1167
1168                 local_tree->operation = LDB_OP_PRESENT;
1169                 local_tree->u.present.attr = talloc_strdup(local_tree, IS_MAPPED);
1170         }
1171         if (remote_tree == NULL) {
1172                 /* Construct default remote parse tree */
1173                 remote_tree = ldb_parse_tree(ac, NULL);
1174                 if (remote_tree == NULL) {
1175                         return LDB_ERR_OPERATIONS_ERROR;
1176                 }
1177         }
1178
1179         ac->local_tree = local_tree;
1180
1181         /* Prepare the remote operation */
1182         ret = ldb_build_search_req_ex(&remote_req, ldb, ac,
1183                                       req->op.search.base,
1184                                       req->op.search.scope,
1185                                       remote_tree,
1186                                       ac->remote_attrs,
1187                                       req->controls,
1188                                       ac, map_remote_search_callback,
1189                                       req);
1190         if (ret != LDB_SUCCESS) {
1191                 return LDB_ERR_OPERATIONS_ERROR;
1192         }
1193
1194         return ldb_next_remote_request(module, remote_req);
1195 }
1196
1197 /* Now, search the local part of a remote search result. */
1198 static int map_remote_search_callback(struct ldb_request *req,
1199                                         struct ldb_reply *ares)
1200 {
1201         struct map_context *ac;
1202         int ret;
1203
1204         ac = talloc_get_type(req->context, struct map_context);
1205
1206         if (!ares) {
1207                 return ldb_module_done(ac->req, NULL, NULL,
1208                                         LDB_ERR_OPERATIONS_ERROR);
1209         }
1210         if (ares->error != LDB_SUCCESS) {
1211                 return ldb_module_done(ac->req, ares->controls,
1212                                         ares->response, ares->error);
1213         }
1214
1215         switch (ares->type) {
1216         case LDB_REPLY_REFERRAL:
1217
1218                 /* ignore referrals */
1219                 talloc_free(ares);
1220                 return LDB_SUCCESS;
1221
1222         case LDB_REPLY_ENTRY:
1223
1224                 /* Map result record into a local message */
1225                 ret = map_reply_remote(ac, ares);
1226                 if (ret) {
1227                         talloc_free(ares);
1228                         return ldb_module_done(ac->req, NULL, NULL,
1229                                                 LDB_ERR_OPERATIONS_ERROR);
1230                 }
1231
1232                 /* if we have no local db, then we can just return the reply to
1233                  * the upper layer, otherwise we must save it and process it
1234                  * when all replies ahve been gathered */
1235                 if ( ! map_check_local_db(ac->module)) {
1236                         ret = map_return_entry(ac, ares);
1237                 } else {
1238                         ret = map_save_entry(ac,ares);
1239                 }
1240
1241                 if (ret != LDB_SUCCESS) {
1242                         talloc_free(ares);
1243                         return ldb_module_done(ac->req, NULL, NULL,
1244                                                 LDB_ERR_OPERATIONS_ERROR);
1245                 }
1246                 break;
1247
1248         case LDB_REPLY_DONE:
1249
1250                 if ( ! map_check_local_db(ac->module)) {
1251                         return ldb_module_done(ac->req, ares->controls,
1252                                                 ares->response, LDB_SUCCESS);
1253                 }
1254
1255                 talloc_free(ares);
1256
1257                 /* reset the pointer to the start of the list */
1258                 ac->r_current = ac->r_list;
1259
1260                 /* no entry just return */
1261                 if (ac->r_current == NULL) {
1262                         return ldb_module_done(ac->req, ares->controls,
1263                                                 ares->response, LDB_SUCCESS);
1264                 }
1265
1266                 ret = map_search_local(ac);
1267                 if (ret != LDB_SUCCESS) {
1268                         return ldb_module_done(ac->req, NULL, NULL, ret);
1269                 }
1270         }
1271
1272         return LDB_SUCCESS;
1273 }
1274
1275 static int map_search_local(struct map_context *ac)
1276 {
1277         struct ldb_request *search_req;
1278
1279         if (ac->r_current == NULL || ac->r_current->remote == NULL) {
1280                 return LDB_ERR_OPERATIONS_ERROR;
1281         }
1282
1283         /* Prepare local search request */
1284         /* TODO: use GUIDs here instead? */
1285         search_req = map_search_base_req(ac,
1286                                          ac->r_current->remote->message->dn,
1287                                          NULL, NULL,
1288                                          ac, map_local_merge_callback);
1289         if (search_req == NULL) {
1290                 return LDB_ERR_OPERATIONS_ERROR;
1291         }
1292
1293         return ldb_next_request(ac->module, search_req);
1294 }
1295
1296 /* Merge the remote and local parts of a search result. */
1297 int map_local_merge_callback(struct ldb_request *req, struct ldb_reply *ares)
1298 {
1299         struct ldb_context *ldb;
1300         struct map_context *ac;
1301         int ret;
1302
1303         ac = talloc_get_type(req->context, struct map_context);
1304         ldb = ldb_module_get_ctx(ac->module);
1305
1306         if (!ares) {
1307                 return ldb_module_done(ac->req, NULL, NULL,
1308                                         LDB_ERR_OPERATIONS_ERROR);
1309         }
1310         if (ares->error != LDB_SUCCESS) {
1311                 return ldb_module_done(ac->req, ares->controls,
1312                                         ares->response, ares->error);
1313         }
1314
1315         switch (ares->type) {
1316         case LDB_REPLY_ENTRY:
1317                 /* We have already found a local record */
1318                 if (ac->r_current->local) {
1319                         talloc_free(ares);
1320                         ldb_set_errstring(ldb, "ldb_map: Too many results!");
1321                         return ldb_module_done(ac->req, NULL, NULL,
1322                                                 LDB_ERR_OPERATIONS_ERROR);
1323                 }
1324
1325                 /* Store local result */
1326                 ac->r_current->local = talloc_steal(ac->r_current, ares);
1327
1328                 break;
1329
1330         case LDB_REPLY_REFERRAL:
1331                 /* ignore referrals */
1332                 talloc_free(ares);
1333                 break;
1334
1335         case LDB_REPLY_DONE:
1336                 talloc_free(ares);
1337
1338                 /* No local record found, map and send remote record */
1339                 if (ac->r_current->local != NULL) {
1340                         /* Merge remote into local message */
1341                         ret = ldb_msg_merge_local(ac->module,
1342                                                   ac->r_current->local->message,
1343                                                   ac->r_current->remote->message);
1344                         if (ret == LDB_SUCCESS) {
1345                                 ret = map_return_entry(ac, ac->r_current->local);
1346                         }
1347                         if (ret != LDB_SUCCESS) {
1348                                 return ldb_module_done(ac->req, NULL, NULL,
1349                                                         LDB_ERR_OPERATIONS_ERROR);
1350                         }
1351                 } else {
1352                         ret = map_return_entry(ac, ac->r_current->remote);
1353                         if (ret != LDB_SUCCESS) {
1354                                 return ldb_module_done(ac->req,
1355                                                         NULL, NULL, ret);
1356                         }
1357                 }
1358
1359                 if (ac->r_current->next != NULL) {
1360                         ac->r_current = ac->r_current->next;
1361                         if (ac->r_current->remote->type == LDB_REPLY_ENTRY) {
1362                                 ret = map_search_local(ac);
1363                                 if (ret != LDB_SUCCESS) {
1364                                         return ldb_module_done(ac->req,
1365                                                                NULL, NULL, ret);
1366                                 }
1367                                 break;
1368                         }
1369                 }
1370
1371                 /* ok we are done with all search, finally it is time to
1372                  * finish operations for this module */
1373                 return ldb_module_done(ac->req,
1374                                         ac->r_current->remote->controls,
1375                                         ac->r_current->remote->response,
1376                                         ac->r_current->remote->error);
1377         }
1378
1379         return LDB_SUCCESS;
1380 }