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