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