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
   8      ** NOTE! The following LGPL license applies to the ldb
   9      ** library. This does NOT imply that all of Samba is released
  10      ** under the LGPL
  11
  12    This library is free software; you can redistribute it and/or
  13    modify it under the terms of the GNU Lesser General Public
  14    License as published by the Free Software Foundation; either
  15    version 3 of the License, or (at your option) any later version.
  16
  17    This library is distributed in the hope that it will be useful,
  18    but WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20    Lesser General Public License for more details.
  21
  22    You should have received a copy of the GNU Lesser General Public
  23    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  24
  25 */
  26
  27 #include "ldb_includes.h"
  28
  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
 267         /* We handle wildcards in ldb_msg_el_merge_wildcard */
 268         if (ldb_attr_cmp(attr_name, "*") == 0) {
 269                 return LDB_SUCCESS;
 270         }
 271
 272         map = map_attr_find_local(data, attr_name);
 273
 274         /* Unknown attribute in remote message:
 275          * skip, attribute was probably auto-generated */
 276         if (map == NULL) {
 277                 return LDB_SUCCESS;
 278         }
 279
 280         switch (map->type) {
 281         case MAP_IGNORE:
 282                 break;
 283         case MAP_CONVERT:
 284                 remote_name = map->u.convert.remote_name;
 285                 break;
 286         case MAP_KEEP:
 287                 remote_name = attr_name;
 288                 break;
 289         case MAP_RENAME:
 290                 remote_name = map->u.rename.remote_name;
 291                 break;
 292         case MAP_GENERATE:
 293                 break;
 294         }
 295
 296         switch (map->type) {
 297         case MAP_IGNORE:
 298                 return LDB_SUCCESS;
 299
 300         case MAP_CONVERT:
 301                 if (map->u.convert.convert_remote == NULL) {
 302                         ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
 303                                   "Skipping attribute '%s': "
 304                                   "'convert_remote' not set\n",
 305                                   attr_name);
 306                         return LDB_SUCCESS;
 307                 }
 308                 /* fall through */
 309         case MAP_KEEP:
 310         case MAP_RENAME:
 311                 old = ldb_msg_find_element(remote, remote_name);
 312                 if (old) {
 313                         el = ldb_msg_el_map_remote(module, local, map, attr_name, old);
 314                 } else {
 315                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
 316                 }
 317                 break;
 318
 319         case MAP_GENERATE:
 320                 if (map->u.generate.generate_local == NULL) {
 321                         ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
 322                                   "Skipping attribute '%s': "
 323                                   "'generate_local' not set\n",
 324                                   attr_name);
 325                         return LDB_SUCCESS;
 326                 }
 327
 328                 el = map->u.generate.generate_local(module, local, attr_name, remote);
 329                 if (!el) {
 330                         /* Generation failure is probably due to lack of source attributes */
 331                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
 332                 }
 333                 break;
 334         }
 335
 336         if (el == NULL) {
 337                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
 338         }
 339
 340         return ldb_msg_replace(local, el);
 341 }
 342
 343 /* Handle wildcard parts of merging a remote message element into a local message. */
 344 static int ldb_msg_el_merge_wildcard(struct ldb_module *module, struct ldb_message *local,
 345                                      struct ldb_message *remote)
 346 {
 347         const struct ldb_map_context *data = map_get_context(module);
 348         const struct ldb_map_attribute *map = map_attr_find_local(data, "*");
 349         struct ldb_message_element *el=NULL;
 350         int i, ret;
 351
 352         /* Perhaps we have a mapping for "*" */
 353         if (map && map->type == MAP_KEEP) {
 354                 /* We copy everything over, and hope that anything with a
 355                    more specific rule is overwritten */
 356                 for (i = 0; i < remote->num_elements; i++) {
 357                         el = ldb_msg_el_map_remote(module, local, map, remote->elements[i].name,
 358                                                    &remote->elements[i]);
 359                         if (el == NULL) {
 360                                 return LDB_ERR_OPERATIONS_ERROR;
 361                         }
 362
 363                         ret = ldb_msg_replace(local, el);
 364                         if (ret) {
 365                                 return ret;
 366                         }
 367                 }
 368         }
 369
 370         /* Now walk the list of possible mappings, and apply each */
 371         for (i = 0; data->attribute_maps[i].local_name; i++) {
 372                 ret = ldb_msg_el_merge(module, local, remote,
 373                                        data->attribute_maps[i].local_name);
 374                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
 375                         continue;
 376                 } else if (ret) {
 377                         return ret;
 378                 } else {
 379                         continue;
 380                 }
 381         }
 382
 383         return LDB_SUCCESS;
 384 }
 385
 386 /* Mapping messages
 387  * ================ */
 388
 389 /* Merge two local messages into a single one. */
 390 static int ldb_msg_merge_local(struct ldb_module *module, struct ldb_message *msg1, struct ldb_message *msg2)
 391 {
 392         int i, ret;
 393
 394         for (i = 0; i < msg2->num_elements; i++) {
 395                 ret = ldb_msg_replace(msg1, &msg2->elements[i]);
 396                 if (ret) {
 397                         return ret;
 398                 }
 399         }
 400
 401         return LDB_SUCCESS;
 402 }
 403
 404 /* Merge a local and a remote message into a single local one. */
 405 static int ldb_msg_merge_remote(struct map_context *ac, struct ldb_message *local,
 406                                 struct ldb_message *remote)
 407 {
 408         int i, ret;
 409         const char * const *attrs = ac->all_attrs;
 410         if (!attrs) {
 411                 ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
 412                 if (ret) {
 413                         return ret;
 414                 }
 415         }
 416
 417         for (i = 0; attrs && attrs[i]; i++) {
 418                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
 419                         ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
 420                         if (ret) {
 421                                 return ret;
 422                         }
 423                         break;
 424                 }
 425         }
 426
 427         /* Try to map each attribute back;
 428          * Add to local message is possible,
 429          * Overwrite old local attribute if necessary */
 430         for (i = 0; attrs && attrs[i]; i++) {
 431                 ret = ldb_msg_el_merge(ac->module, local, remote,
 432                                        attrs[i]);
 433                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
 434                 } else if (ret) {
 435                         return ret;
 436                 }
 437         }
 438
 439         return LDB_SUCCESS;
 440 }
 441
 442 /* Mapping search results
 443  * ====================== */
 444
 445 /* Map a search result back into the local partition. */
 446 static int map_reply_remote(struct map_context *ac, struct ldb_reply *ares)
 447 {
 448         struct ldb_message *msg;
 449         struct ldb_dn *dn;
 450         int ret;
 451
 452         /* There is no result message, skip */
 453         if (ares->type != LDB_REPLY_ENTRY) {
 454                 return 0;
 455         }
 456
 457         /* Create a new result message */
 458         msg = ldb_msg_new(ares);
 459         if (msg == NULL) {
 460                 map_oom(ac->module);
 461                 return -1;
 462         }
 463
 464         /* Merge remote message into new message */
 465         ret = ldb_msg_merge_remote(ac, msg, ares->message);
 466         if (ret) {
 467                 talloc_free(msg);
 468                 return ret;
 469         }
 470
 471         /* Create corresponding local DN */
 472         dn = ldb_dn_map_rebase_remote(ac->module, msg, ares->message->dn);
 473         if (dn == NULL) {
 474                 talloc_free(msg);
 475                 return -1;
 476         }
 477         msg->dn = dn;
 478
 479         /* Store new message with new DN as the result */
 480         talloc_free(ares->message);
 481         ares->message = msg;
 482
 483         return 0;
 484 }
 485
 486 /* Mapping parse trees
 487  * =================== */
 488
 489 /* Check whether a parse tree can safely be split in two. */
 490 static bool ldb_parse_tree_check_splittable(const struct ldb_parse_tree *tree)
 491 {
 492         const struct ldb_parse_tree *subtree = tree;
 493         bool negate = false;
 494
 495         while (subtree) {
 496                 switch (subtree->operation) {
 497                 case LDB_OP_NOT:
 498                         negate = !negate;
 499                         subtree = subtree->u.isnot.child;
 500                         continue;
 501
 502                 case LDB_OP_AND:
 503                         return !negate; /* if negate: False */
 504
 505                 case LDB_OP_OR:
 506                         return negate;  /* if negate: True */
 507
 508                 default:
 509                         return true;    /* simple parse tree */
 510                 }
 511         }
 512
 513         return true;                    /* no parse tree */
 514 }
 515
 516 /* Collect a list of attributes required to match a given parse tree. */
 517 static int ldb_parse_tree_collect_attrs(struct ldb_module *module, void *mem_ctx, const char ***attrs, const struct ldb_parse_tree *tree)
 518 {
 519         const char **new_attrs;
 520         int i, ret;
 521
 522         if (tree == NULL) {
 523                 return 0;
 524         }
 525
 526         switch (tree->operation) {
 527         case LDB_OP_OR:
 528         case LDB_OP_AND:                /* attributes stored in list of subtrees */
 529                 for (i = 0; i < tree->u.list.num_elements; i++) {
 530                         ret = ldb_parse_tree_collect_attrs(module, mem_ctx,
 531                                                            attrs, tree->u.list.elements[i]);
 532                         if (ret) {
 533                                 return ret;
 534                         }
 535                 }
 536                 return 0;
 537
 538         case LDB_OP_NOT:                /* attributes stored in single subtree */
 539                 return ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.isnot.child);
 540
 541         default:                        /* single attribute in tree */
 542                 new_attrs = ldb_attr_list_copy_add(mem_ctx, *attrs, tree->u.equality.attr);
 543                 talloc_free(*attrs);
 544                 *attrs = new_attrs;
 545                 return 0;
 546         }
 547
 548         return -1;
 549 }
 550
 551 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
 552
 553 /* Select a negated subtree that queries attributes in the local partition */
 554 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)
 555 {
 556         struct ldb_parse_tree *child;
 557         int ret;
 558
 559         /* Prepare new tree */
 560         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 561         if (*new == NULL) {
 562                 map_oom(module);
 563                 return -1;
 564         }
 565
 566         /* Generate new subtree */
 567         ret = map_subtree_select_local(module, *new, &child, tree->u.isnot.child);
 568         if (ret) {
 569                 talloc_free(*new);
 570                 return ret;
 571         }
 572
 573         /* Prune tree without subtree */
 574         if (child == NULL) {
 575                 talloc_free(*new);
 576                 *new = NULL;
 577                 return 0;
 578         }
 579
 580         (*new)->u.isnot.child = child;
 581
 582         return ret;
 583 }
 584
 585 /* Select a list of subtrees that query attributes in the local partition */
 586 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)
 587 {
 588         int i, j, ret=0;
 589
 590         /* Prepare new tree */
 591         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 592         if (*new == NULL) {
 593                 map_oom(module);
 594                 return -1;
 595         }
 596
 597         /* Prepare list of subtrees */
 598         (*new)->u.list.num_elements = 0;
 599         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
 600         if ((*new)->u.list.elements == NULL) {
 601                 map_oom(module);
 602                 talloc_free(*new);
 603                 return -1;
 604         }
 605
 606         /* Generate new list of subtrees */
 607         j = 0;
 608         for (i = 0; i < tree->u.list.num_elements; i++) {
 609                 struct ldb_parse_tree *child;
 610                 ret = map_subtree_select_local(module, *new, &child, tree->u.list.elements[i]);
 611                 if (ret) {
 612                         talloc_free(*new);
 613                         return ret;
 614                 }
 615
 616                 if (child) {
 617                         (*new)->u.list.elements[j] = child;
 618                         j++;
 619                 }
 620         }
 621
 622         /* Prune tree without subtrees */
 623         if (j == 0) {
 624                 talloc_free(*new);
 625                 *new = NULL;
 626                 return 0;
 627         }
 628
 629         /* Fix subtree list size */
 630         (*new)->u.list.num_elements = j;
 631         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
 632
 633         return ret;
 634 }
 635
 636 /* Select a simple subtree that queries attributes in the local partition */
 637 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)
 638 {
 639         /* Prepare new tree */
 640         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 641         if (*new == NULL) {
 642                 map_oom(module);
 643                 return -1;
 644         }
 645
 646         return 0;
 647 }
 648
 649 /* Select subtrees that query attributes in the local partition */
 650 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 651 {
 652         const struct ldb_map_context *data = map_get_context(module);
 653
 654         if (tree == NULL) {
 655                 return 0;
 656         }
 657
 658         if (tree->operation == LDB_OP_NOT) {
 659                 return map_subtree_select_local_not(module, mem_ctx, new, tree);
 660         }
 661
 662         if (tree->operation == LDB_OP_AND || tree->operation == LDB_OP_OR) {
 663                 return map_subtree_select_local_list(module, mem_ctx, new, tree);
 664         }
 665
 666         if (map_attr_check_remote(data, tree->u.equality.attr)) {
 667                 *new = NULL;
 668                 return 0;
 669         }
 670
 671         return map_subtree_select_local_simple(module, mem_ctx, new, tree);
 672 }
 673
 674 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
 675
 676 /* Collect a negated subtree that queries attributes in the remote partition */
 677 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)
 678 {
 679         struct ldb_parse_tree *child;
 680         int ret;
 681
 682         /* Prepare new tree */
 683         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 684         if (*new == NULL) {
 685                 map_oom(module);
 686                 return -1;
 687         }
 688
 689         /* Generate new subtree */
 690         ret = map_subtree_collect_remote(module, *new, &child, tree->u.isnot.child);
 691         if (ret) {
 692                 talloc_free(*new);
 693                 return ret;
 694         }
 695
 696         /* Prune tree without subtree */
 697         if (child == NULL) {
 698                 talloc_free(*new);
 699                 *new = NULL;
 700                 return 0;
 701         }
 702
 703         (*new)->u.isnot.child = child;
 704
 705         return ret;
 706 }
 707
 708 /* Collect a list of subtrees that query attributes in the remote partition */
 709 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)
 710 {
 711         int i, j, ret=0;
 712
 713         /* Prepare new tree */
 714         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 715         if (*new == NULL) {
 716                 map_oom(module);
 717                 return -1;
 718         }
 719
 720         /* Prepare list of subtrees */
 721         (*new)->u.list.num_elements = 0;
 722         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
 723         if ((*new)->u.list.elements == NULL) {
 724                 map_oom(module);
 725                 talloc_free(*new);
 726                 return -1;
 727         }
 728
 729         /* Generate new list of subtrees */
 730         j = 0;
 731         for (i = 0; i < tree->u.list.num_elements; i++) {
 732                 struct ldb_parse_tree *child;
 733                 ret = map_subtree_collect_remote(module, *new, &child, tree->u.list.elements[i]);
 734                 if (ret) {
 735                         talloc_free(*new);
 736                         return ret;
 737                 }
 738
 739                 if (child) {
 740                         (*new)->u.list.elements[j] = child;
 741                         j++;
 742                 }
 743         }
 744
 745         /* Prune tree without subtrees */
 746         if (j == 0) {
 747                 talloc_free(*new);
 748                 *new = NULL;
 749                 return 0;
 750         }
 751
 752         /* Fix subtree list size */
 753         (*new)->u.list.num_elements = j;
 754         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
 755
 756         return ret;
 757 }
 758
 759 /* Collect a simple subtree that queries attributes in the remote partition */
 760 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)
 761 {
 762         const char *attr;
 763
 764         /* Prepare new tree */
 765         *new = talloc(mem_ctx, struct ldb_parse_tree);
 766         if (*new == NULL) {
 767                 map_oom(module);
 768                 return -1;
 769         }
 770         **new = *tree;
 771
 772         if (map->type == MAP_KEEP) {
 773                 /* Nothing to do here */
 774                 return 0;
 775         }
 776
 777         /* Store attribute and value in new tree */
 778         switch (tree->operation) {
 779         case LDB_OP_PRESENT:
 780                 attr = map_attr_map_local(*new, map, tree->u.present.attr);
 781                 (*new)->u.present.attr = attr;
 782                 break;
 783         case LDB_OP_SUBSTRING:
 784         {
 785                 attr = map_attr_map_local(*new, map, tree->u.substring.attr);
 786                 (*new)->u.substring.attr = attr;
 787                 break;
 788         }
 789         case LDB_OP_EQUALITY:
 790                 attr = map_attr_map_local(*new, map, tree->u.equality.attr);
 791                 (*new)->u.equality.attr = attr;
 792                 break;
 793         case LDB_OP_LESS:
 794         case LDB_OP_GREATER:
 795         case LDB_OP_APPROX:
 796                 attr = map_attr_map_local(*new, map, tree->u.comparison.attr);
 797                 (*new)->u.comparison.attr = attr;
 798                 break;
 799         case LDB_OP_EXTENDED:
 800                 attr = map_attr_map_local(*new, map, tree->u.extended.attr);
 801                 (*new)->u.extended.attr = attr;
 802                 break;
 803         default:                        /* unknown kind of simple subtree */
 804                 talloc_free(*new);
 805                 return -1;
 806         }
 807
 808         if (attr == NULL) {
 809                 talloc_free(*new);
 810                 *new = NULL;
 811                 return 0;
 812         }
 813
 814         if (map->type == MAP_RENAME) {
 815                 /* Nothing more to do here, the attribute has been renamed */
 816                 return 0;
 817         }
 818
 819         /* Store attribute and value in new tree */
 820         switch (tree->operation) {
 821         case LDB_OP_PRESENT:
 822                 break;
 823         case LDB_OP_SUBSTRING:
 824         {
 825                 int i;
 826                 /* Map value */
 827                 (*new)->u.substring.chunks = NULL;
 828                 for (i=0; tree->u.substring.chunks[i]; i++) {
 829                         (*new)->u.substring.chunks = talloc_realloc(*new, (*new)->u.substring.chunks, struct ldb_val *, i+2);
 830                         if (!(*new)->u.substring.chunks) {
 831                                 talloc_free(*new);
 832                                 *new = NULL;
 833                                 return 0;
 834                         }
 835                         (*new)->u.substring.chunks[i] = talloc(*new, struct ldb_val);
 836                         if (!(*new)->u.substring.chunks[i]) {
 837                                 talloc_free(*new);
 838                                 *new = NULL;
 839                                 return 0;
 840                         }
 841                         *(*new)->u.substring.chunks[i] = ldb_val_map_local(module, *new, map, tree->u.substring.chunks[i]);
 842                         (*new)->u.substring.chunks[i+1] = NULL;
 843                 }
 844                 break;
 845         }
 846         case LDB_OP_EQUALITY:
 847                 (*new)->u.equality.value = ldb_val_map_local(module, *new, map, &tree->u.equality.value);
 848                 break;
 849         case LDB_OP_LESS:
 850         case LDB_OP_GREATER:
 851         case LDB_OP_APPROX:
 852                 (*new)->u.comparison.value = ldb_val_map_local(module, *new, map, &tree->u.comparison.value);
 853                 break;
 854         case LDB_OP_EXTENDED:
 855                 (*new)->u.extended.value = ldb_val_map_local(module, *new, map, &tree->u.extended.value);
 856                 (*new)->u.extended.rule_id = talloc_strdup(*new, tree->u.extended.rule_id);
 857                 break;
 858         default:                        /* unknown kind of simple subtree */
 859                 talloc_free(*new);
 860                 return -1;
 861         }
 862
 863         return 0;
 864 }
 865
 866 /* Collect subtrees that query attributes in the remote partition */
 867 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 868 {
 869         const struct ldb_map_context *data = map_get_context(module);
 870         const struct ldb_map_attribute *map;
 871
 872         if (tree == NULL) {
 873                 return 0;
 874         }
 875
 876         if (tree->operation == LDB_OP_NOT) {
 877                 return map_subtree_collect_remote_not(module, mem_ctx, new, tree);
 878         }
 879
 880         if ((tree->operation == LDB_OP_AND) || (tree->operation == LDB_OP_OR)) {
 881                 return map_subtree_collect_remote_list(module, mem_ctx, new, tree);
 882         }
 883
 884         if (!map_attr_check_remote(data, tree->u.equality.attr)) {
 885                 *new = NULL;
 886                 return 0;
 887         }
 888
 889         map = map_attr_find_local(data, tree->u.equality.attr);
 890         if (map->convert_operator) {
 891                 return map->convert_operator(module, mem_ctx, new, tree);
 892         }
 893
 894         if (map->type == MAP_GENERATE) {
 895                 ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
 896                           "Skipping attribute '%s': "
 897                           "'convert_operator' not set\n",
 898                           tree->u.equality.attr);
 899                 *new = NULL;
 900                 return 0;
 901         }
 902
 903         return map_subtree_collect_remote_simple(module, mem_ctx, new, tree, map);
 904 }
 905
 906 /* Split subtrees that query attributes in the local partition from
 907  * those that query the remote partition. */
 908 static int ldb_parse_tree_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, struct ldb_parse_tree **local_tree, struct ldb_parse_tree **remote_tree, const struct ldb_parse_tree *tree)
 909 {
 910         int ret;
 911
 912         *local_tree = NULL;
 913         *remote_tree = NULL;
 914
 915         /* No original tree */
 916         if (tree == NULL) {
 917                 return 0;
 918         }
 919
 920         /* Generate local tree */
 921         ret = map_subtree_select_local(module, local_ctx, local_tree, tree);
 922         if (ret) {
 923                 return ret;
 924         }
 925
 926         /* Generate remote tree */
 927         ret = map_subtree_collect_remote(module, remote_ctx, remote_tree, tree);
 928         if (ret) {
 929                 talloc_free(*local_tree);
 930                 return ret;
 931         }
 932
 933         return 0;
 934 }
 935
 936 /* Collect a list of attributes required either explicitly from a
 937  * given list or implicitly  from a given parse tree; split the
 938  * collected list into local and remote parts. */
 939 static int map_attrs_collect_and_partition(struct ldb_module *module, struct map_context *ac,
 940                                            const char * const *search_attrs,
 941                                            const struct ldb_parse_tree *tree)
 942 {
 943         void *tmp_ctx;
 944         const char **tree_attrs;
 945         const char **remote_attrs;
 946         const char **local_attrs;
 947         int ret;
 948
 949         /* There is no tree, just partition the searched attributes */
 950         if (tree == NULL) {
 951                 ret = map_attrs_partition(module, ac,
 952                                           &local_attrs, &remote_attrs, search_attrs);
 953                 if (ret == 0) {
 954                         ac->local_attrs = local_attrs;
 955                         ac->remote_attrs = remote_attrs;
 956                         ac->all_attrs = search_attrs;
 957                 }
 958                 return ret;
 959         }
 960
 961         /* Create context for temporary memory */
 962         tmp_ctx = talloc_new(ac);
 963         if (tmp_ctx == NULL) {
 964                 goto oom;
 965         }
 966
 967         /* Prepare list of attributes from tree */
 968         tree_attrs = talloc_array(tmp_ctx, const char *, 1);
 969         if (tree_attrs == NULL) {
 970                 talloc_free(tmp_ctx);
 971                 goto oom;
 972         }
 973         tree_attrs[0] = NULL;
 974
 975         /* Collect attributes from tree */
 976         ret = ldb_parse_tree_collect_attrs(module, tmp_ctx, &tree_attrs, tree);
 977         if (ret) {
 978                 goto done;
 979         }
 980
 981         /* Merge attributes from search operation */
 982         ret = map_attrs_merge(module, tmp_ctx, &tree_attrs, search_attrs);
 983         if (ret) {
 984                 goto done;
 985         }
 986
 987         /* Split local from remote attributes */
 988         ret = map_attrs_partition(module, ac, &local_attrs,
 989                                   &remote_attrs, tree_attrs);
 990
 991         if (ret == 0) {
 992                 ac->local_attrs = local_attrs;
 993                 ac->remote_attrs = remote_attrs;
 994                 talloc_steal(ac, tree_attrs);
 995                 ac->all_attrs = tree_attrs;
 996         }
 997 done:
 998         /* Free temporary memory */
 999         talloc_free(tmp_ctx);
1000         return ret;
1001
1002 oom:
1003         map_oom(module);
1004         return -1;
1005 }
1006
1007
1008 /* Outbound requests: search
1009  * ========================= */
1010
1011 /* Pass a merged search result up the callback chain. */
1012 int map_up_callback(struct ldb_context *ldb, const struct ldb_request *req, struct ldb_reply *ares)
1013 {
1014         int i;
1015
1016         /* No callback registered, stop */
1017         if (req->callback == NULL) {
1018                 return LDB_SUCCESS;
1019         }
1020
1021         /* Only records need special treatment */
1022         if (ares->type != LDB_REPLY_ENTRY) {
1023                 return req->callback(ldb, req->context, ares);
1024         }
1025
1026         /* Merged result doesn't match original query, skip */
1027         if (!ldb_match_msg(ldb, ares->message, req->op.search.tree, req->op.search.base, req->op.search.scope)) {
1028                 ldb_debug(ldb, LDB_DEBUG_TRACE, "ldb_map: "
1029                           "Skipping record '%s': "
1030                           "doesn't match original search\n",
1031                           ldb_dn_get_linearized(ares->message->dn));
1032                 return LDB_SUCCESS;
1033         }
1034
1035         /* Limit result to requested attrs */
1036         if ((req->op.search.attrs) && (!ldb_attr_in_list(req->op.search.attrs, "*"))) {
1037                 for (i = 0; i < ares->message->num_elements; ) {
1038                         struct ldb_message_element *el = &ares->message->elements[i];
1039                         if (!ldb_attr_in_list(req->op.search.attrs, el->name)) {
1040                                 ldb_msg_remove_element(ares->message, el);
1041                         } else {
1042                                 i++;
1043                         }
1044                 }
1045         }
1046
1047         return req->callback(ldb, req->context, ares);
1048 }
1049
1050 /* Merge the remote and local parts of a search result. */
1051 int map_local_merge_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
1052 {
1053         struct map_search_context *sc;
1054         int ret;
1055
1056         if (context == NULL || ares == NULL) {
1057                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
1058                                                        "NULL Context or Result in `map_local_merge_callback`"));
1059                 return LDB_ERR_OPERATIONS_ERROR;
1060         }
1061
1062         sc = talloc_get_type(context, struct map_search_context);
1063
1064         switch (ares->type) {
1065         case LDB_REPLY_ENTRY:
1066                 /* We have already found a local record */
1067                 if (sc->local_res) {
1068                         ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
1069                                                                "Too many results to base search for local entry"));
1070                         talloc_free(ares);
1071                         return LDB_ERR_OPERATIONS_ERROR;
1072                 }
1073
1074                 /* Store local result */
1075                 sc->local_res = ares;
1076
1077                 /* Merge remote into local message */
1078                 ret = ldb_msg_merge_local(sc->ac->module, ares->message, sc->remote_res->message);
1079                 if (ret) {
1080                         talloc_free(ares);
1081                         return LDB_ERR_OPERATIONS_ERROR;
1082                 }
1083
1084                 return map_up_callback(ldb, sc->ac->orig_req, ares);
1085
1086         case LDB_REPLY_DONE:
1087                 /* No local record found, continue with remote record */
1088                 if (sc->local_res == NULL) {
1089                         return map_up_callback(ldb, sc->ac->orig_req, sc->remote_res);
1090                 }
1091                 return LDB_SUCCESS;
1092
1093         default:
1094                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
1095                                                        "Unexpected result type in base search for local entry"));
1096                 talloc_free(ares);
1097                 return LDB_ERR_OPERATIONS_ERROR;
1098         }
1099 }
1100
1101 /* Search the local part of a remote search result. */
1102 int map_remote_search_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
1103 {
1104         struct map_context *ac;
1105         struct map_search_context *sc;
1106         struct ldb_request *req;
1107         int ret;
1108
1109         if (context == NULL || ares == NULL) {
1110                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
1111                                                        "NULL Context or Result in `map_remote_search_callback`"));
1112                 return LDB_ERR_OPERATIONS_ERROR;
1113         }
1114
1115         ac = talloc_get_type(context, struct map_context);
1116
1117         /* It's not a record, stop searching */
1118         if (ares->type != LDB_REPLY_ENTRY) {
1119                 return map_up_callback(ldb, ac->orig_req, ares);
1120         }
1121
1122         /* Map result record into a local message */
1123         ret = map_reply_remote(ac, ares);
1124         if (ret) {
1125                 talloc_free(ares);
1126                 return LDB_ERR_OPERATIONS_ERROR;
1127         }
1128
1129         /* There is no local db, stop searching */
1130         if (!map_check_local_db(ac->module)) {
1131                 return map_up_callback(ldb, ac->orig_req, ares);
1132         }
1133
1134         /* Prepare local search context */
1135         sc = map_init_search_context(ac, ares);
1136         if (sc == NULL) {
1137                 talloc_free(ares);
1138                 return LDB_ERR_OPERATIONS_ERROR;
1139         }
1140
1141         /* Prepare local search request */
1142         /* TODO: use GUIDs here instead? */
1143
1144         ac->search_reqs = talloc_realloc(ac, ac->search_reqs, struct ldb_request *, ac->num_searches + 2);
1145         if (ac->search_reqs == NULL) {
1146                 talloc_free(ares);
1147                 return LDB_ERR_OPERATIONS_ERROR;
1148         }
1149
1150         ac->search_reqs[ac->num_searches]
1151                 = req = map_search_base_req(ac, ares->message->dn,
1152                                             NULL, NULL, sc, map_local_merge_callback);
1153         if (req == NULL) {
1154                 talloc_free(sc);
1155                 talloc_free(ares);
1156                 return LDB_ERR_OPERATIONS_ERROR;
1157         }
1158         ac->num_searches++;
1159         ac->search_reqs[ac->num_searches] = NULL;
1160
1161         return ldb_next_request(ac->module, req);
1162 }
1163
1164 /* Search a record. */
1165 int map_search(struct ldb_module *module, struct ldb_request *req)
1166 {
1167         struct ldb_handle *h;
1168         struct map_context *ac;
1169         struct ldb_parse_tree *local_tree, *remote_tree;
1170         int ret;
1171
1172         const char *wildcard[] = { "*", NULL };
1173         const char * const *attrs;
1174
1175         if (!module->private_data) /* if we're not yet initialized, go to the next module */
1176                 return ldb_next_request(module, req);
1177
1178         /* Do not manipulate our control entries */
1179         if (ldb_dn_is_special(req->op.search.base))
1180                 return ldb_next_request(module, req);
1181
1182         /* No mapping requested, skip to next module */
1183         if ((req->op.search.base) && (!ldb_dn_check_local(module, req->op.search.base))) {
1184                 return ldb_next_request(module, req);
1185         }
1186
1187         /* TODO: How can we be sure about which partition we are
1188          *       targetting when there is no search base? */
1189
1190         /* Prepare context and handle */
1191         h = map_init_handle(req, module);
1192         if (h == NULL) {
1193                 return LDB_ERR_OPERATIONS_ERROR;
1194         }
1195         ac = talloc_get_type(h->private_data, struct map_context);
1196
1197         ac->search_reqs = talloc_array(ac, struct ldb_request *, 2);
1198         if (ac->search_reqs == NULL) {
1199                 talloc_free(h);
1200                 return LDB_ERR_OPERATIONS_ERROR;
1201         }
1202         ac->num_searches = 1;
1203         ac->search_reqs[1] = NULL;
1204
1205         /* Prepare the remote operation */
1206         ac->search_reqs[0] = talloc(ac, struct ldb_request);
1207         if (ac->search_reqs[0] == NULL) {
1208                 goto oom;
1209         }
1210
1211         *(ac->search_reqs[0]) = *req;   /* copy the request */
1212
1213         ac->search_reqs[0]->handle = h; /* return our own handle to deal with this call */
1214
1215         ac->search_reqs[0]->context = ac;
1216         ac->search_reqs[0]->callback = map_remote_search_callback;
1217
1218         /* It is easier to deal with the two different ways of
1219          * expressing the wildcard in the same codepath */
1220         attrs = req->op.search.attrs;
1221         if (attrs == NULL) {
1222                 attrs = wildcard;
1223         }
1224
1225         /* Split local from remote attrs */
1226         ret = map_attrs_collect_and_partition(module, ac,
1227                                               attrs, req->op.search.tree);
1228         if (ret) {
1229                 goto failed;
1230         }
1231
1232         ac->search_reqs[0]->op.search.attrs = ac->remote_attrs;
1233
1234         /* Split local from remote tree */
1235         ret = ldb_parse_tree_partition(module, ac, ac->search_reqs[0],
1236                                        &local_tree, &remote_tree,
1237                                        req->op.search.tree);
1238         if (ret) {
1239                 goto failed;
1240         }
1241
1242         if (((local_tree != NULL) && (remote_tree != NULL)) &&
1243             (!ldb_parse_tree_check_splittable(req->op.search.tree))) {
1244                 /* The query can't safely be split, enumerate the remote partition */
1245                 local_tree = NULL;
1246                 remote_tree = NULL;
1247         }
1248
1249         if (local_tree == NULL) {
1250                 /* Construct default local parse tree */
1251                 local_tree = talloc_zero(ac, struct ldb_parse_tree);
1252                 if (local_tree == NULL) {
1253                         map_oom(ac->module);
1254                         goto failed;
1255                 }
1256
1257                 local_tree->operation = LDB_OP_PRESENT;
1258                 local_tree->u.present.attr = talloc_strdup(local_tree, IS_MAPPED);
1259         }
1260         if (remote_tree == NULL) {
1261                 /* Construct default remote parse tree */
1262                 remote_tree = ldb_parse_tree(ac->search_reqs[0], NULL);
1263                 if (remote_tree == NULL) {
1264                         goto failed;
1265                 }
1266         }
1267
1268         ac->local_tree = local_tree;
1269         ac->search_reqs[0]->op.search.tree = remote_tree;
1270
1271         ldb_set_timeout_from_prev_req(module->ldb, req, ac->search_reqs[0]);
1272
1273         h->state = LDB_ASYNC_INIT;
1274         h->status = LDB_SUCCESS;
1275
1276         ac->step = MAP_SEARCH_REMOTE;
1277
1278         ret = ldb_next_remote_request(module, ac->search_reqs[0]);
1279         if (ret == LDB_SUCCESS) {
1280                 req->handle = h;
1281         }
1282         return ret;
1283
1284 oom:
1285         map_oom(module);
1286 failed:
1287         talloc_free(h);
1288         return LDB_ERR_OPERATIONS_ERROR;
1289 }