4 Copyright (C) Simo Sorce 2005-2008
5 Copyright (C) Andrew Bartlett <abartlet@samba.org> 2018
7 ** NOTE! The following LGPL license applies to the ldb
8 ** library. This does NOT imply that all of Samba is released
11 This library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU Lesser General Public
13 License as published by the Free Software Foundation; either
14 version 3 of the License, or (at your option) any later version.
16 This library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 Lesser General Public License for more details.
21 You should have received a copy of the GNU Lesser General Public
22 License along with this library; if not, see <http://www.gnu.org/licenses/>.
28 * Component: ldb paged results control module
30 * Description: this module caches a complete search and sends back
31 * results in chunks as asked by the client
33 * Author: Garming Sam and Aaron Haslett
35 * Note: Based on the original paged_results.c by Simo Sorce and
36 * vlv_pagination.c by Douglas Bagnall and Garming Sam.
40 #include "auth/auth.h"
42 #include "dsdb/samdb/samdb.h"
43 #include "libcli/security/security.h"
44 #include "libcli/ldap/ldap_errors.h"
46 #include "system/filesys.h"
47 #include "system/time.h"
48 #include "ldb_module.h"
49 #include "dsdb/samdb/samdb.h"
51 #include "dsdb/common/util.h"
52 #include "lib/util/dlinklist.h"
54 /* Referrals are temporarily stored in a linked list */
55 struct referral_store {
57 struct referral_store *next;
62 struct results_store {
63 struct results_store *prev, *next;
65 struct private_data *priv;
70 struct referral_store *first_ref;
71 struct referral_store *last_ref;
73 struct ldb_control **controls;
78 size_t result_array_size;
80 struct ldb_control **down_controls;
81 const char * const *attrs;
84 struct ldb_parse_tree *expr;
89 uint32_t next_free_id;
91 struct results_store *store;
94 static int store_destructor(struct results_store *del)
96 struct private_data *priv = del->priv;
97 DLIST_REMOVE(priv->store, del);
99 priv->num_stores -= 1;
104 static struct results_store *new_store(struct private_data *priv)
106 struct results_store *newr;
107 uint32_t new_id = priv->next_free_id++;
109 /* TODO: we should have a limit on the number of
110 * outstanding paged searches
113 newr = talloc_zero(priv, struct results_store);
114 if (!newr) return NULL;
118 newr->cookie = talloc_asprintf(newr, "%d", new_id);
124 newr->timestamp = time(NULL);
126 DLIST_ADD(priv->store, newr);
128 priv->num_stores += 1;
130 talloc_set_destructor(newr, store_destructor);
132 if (priv->num_stores > 10) {
133 struct results_store *last;
135 * 10 is the default for MaxResultSetsPerConn --
136 * possibly need to parameterize it.
138 last = DLIST_TAIL(priv->store);
145 struct paged_context {
146 struct ldb_module *module;
147 struct ldb_request *req;
149 struct results_store *store;
151 struct ldb_control **controls;
154 static int send_referrals(struct results_store *store,
155 struct ldb_request *req)
158 struct referral_store *node;
159 while (store->first_ref != NULL) {
160 node = store->first_ref;
161 ret = ldb_module_send_referral(req, node->ref);
162 if (ret != LDB_SUCCESS) {
165 store->first_ref = node->next;
171 /* Start an ldb request for a single object by GUID */
172 static int paged_search_by_dn_guid(struct ldb_module *module,
173 struct paged_context *ac,
174 struct ldb_result **result,
175 const struct GUID *guid,
176 const char * const *attrs,
177 struct ldb_parse_tree *expr)
180 struct ldb_request *req;
181 struct ldb_result *res;
183 struct GUID_txt_buf guid_str;
185 /* Use controls passed in on the downreq */
186 struct ldb_control **controls = ac->store->down_controls;
188 struct ldb_context *ldb = ldb_module_get_ctx(module);
190 dn = ldb_dn_new_fmt(ac, ldb, "<GUID=%s>",
191 GUID_buf_string(guid, &guid_str));
196 res = talloc_zero(ac, struct ldb_result);
202 ret = ldb_build_search_req_ex(&req, ldb, ac,
209 ldb_search_default_callback,
211 if (ret != LDB_SUCCESS) {
218 * Ensure the dn lasts only as long as the request,
219 * as we will have a lot of these (one per object
223 talloc_steal(req, dn);
225 ret = ldb_request(ldb, req);
226 if (ret == LDB_SUCCESS) {
227 ret = ldb_wait(req->handle, LDB_WAIT_ALL);
231 if (ret != LDB_SUCCESS) {
240 static int paged_results(struct paged_context *ac)
242 struct ldb_paged_control *paged;
243 unsigned int i, num_ctrls;
246 if (ac->store == NULL) {
247 return LDB_ERR_OPERATIONS_ERROR;
250 while (ac->store->last_i < ac->store->num_entries && ac->size > 0) {
251 struct GUID *guid = &ac->store->results[ac->store->last_i++];
252 struct ldb_result *result = NULL;
257 * Note: In the case that an object has been moved to a
258 * different place in the LDAP tree, we might expect the object
259 * to disappear from paged results. If we were going to
260 * implement that behaviour, we would do it here by passing
261 * down the original container DN to the search.
262 * However, testing shows that, on Windows, the moved object
263 * remains in the paged results. So, we are matching Windows
264 * behaviour here by leaving out the scope.
266 ret = paged_search_by_dn_guid(ac->module, ac, &result, guid,
267 ac->req->op.search.attrs,
269 if (ret == LDAP_NO_SUCH_OBJECT /* TODO or no result */) {
270 /* The thing isn't there TODO, which we quietly
271 ignore and go on to send an extra one
274 } else if (ret != LDB_SUCCESS) {
278 ret = ldb_module_send_entry(ac->req, result->msgs[0],
280 if (ret != LDB_SUCCESS) {
285 if (ac->store->first_ref) {
286 /* There is no right place to put references in the sorted
287 results, so we send them as soon as possible.
289 ret = send_referrals(ac->store, ac->req);
290 if (ret != LDB_SUCCESS) {
295 /* return result done */
299 if (ac->store->controls != NULL) {
300 while (ac->store->controls[i]) i++; /* counting */
305 ac->controls = talloc_array(ac, struct ldb_control *, num_ctrls +1);
306 if (ac->controls == NULL) {
307 return LDB_ERR_OPERATIONS_ERROR;
309 ac->controls[num_ctrls] = NULL;
311 for (i = 0; i < (num_ctrls -1); i++) {
312 ac->controls[i] = talloc_reference(ac->controls,
313 ac->store->controls[i]);
316 ac->controls[i] = talloc(ac->controls, struct ldb_control);
317 if (ac->controls[i] == NULL) {
318 return LDB_ERR_OPERATIONS_ERROR;
321 ac->controls[i]->oid = talloc_strdup(ac->controls[i],
322 LDB_CONTROL_PAGED_RESULTS_OID);
323 if (ac->controls[i]->oid == NULL) {
324 return LDB_ERR_OPERATIONS_ERROR;
327 ac->controls[i]->critical = 0;
329 paged = talloc(ac->controls[i], struct ldb_paged_control);
331 return LDB_ERR_OPERATIONS_ERROR;
334 ac->controls[i]->data = paged;
338 paged->cookie = NULL;
339 paged->cookie_len = 0;
341 paged->size = ac->store->num_entries;
342 paged->cookie = talloc_strdup(paged, ac->store->cookie);
343 paged->cookie_len = strlen(paged->cookie) + 1;
349 static int save_referral(struct results_store *store, char *ref)
351 struct referral_store *node = talloc(store,
352 struct referral_store);
354 return LDB_ERR_OPERATIONS_ERROR;
357 node->ref = talloc_steal(node, ref);
359 if (store->first_ref == NULL) {
360 store->first_ref = node;
362 store->last_ref->next = node;
364 store->last_ref = node;
368 static int paged_search_callback(struct ldb_request *req,
369 struct ldb_reply *ares)
371 struct paged_context *ac;
372 struct results_store *store;
374 const struct ldb_val *guid_blob;
378 ac = talloc_get_type(req->context, struct paged_context);
382 return ldb_module_done(ac->req, NULL, NULL,
383 LDB_ERR_OPERATIONS_ERROR);
385 if (ares->error != LDB_SUCCESS) {
386 return ldb_module_done(ac->req, ares->controls,
387 ares->response, ares->error);
390 switch (ares->type) {
391 case LDB_REPLY_ENTRY:
392 if (store->results == NULL) {
393 store->num_entries = 0;
394 store->result_array_size = 16;
395 store->results = talloc_array(store, struct GUID,
396 store->result_array_size);
397 if (store->results == NULL) {
398 return ldb_module_done(ac->req, NULL, NULL,
399 LDB_ERR_OPERATIONS_ERROR);
401 } else if (store->num_entries == store->result_array_size) {
402 if (store->result_array_size > INT_MAX/2) {
403 return ldb_module_done(ac->req, NULL, NULL,
404 LDB_ERR_OPERATIONS_ERROR);
406 store->result_array_size *= 2;
407 store->results = talloc_realloc(store, store->results,
409 store->result_array_size);
410 if (store->results == NULL) {
411 return ldb_module_done(ac->req, NULL, NULL,
412 LDB_ERR_OPERATIONS_ERROR);
416 guid_blob = ldb_dn_get_extended_component(ares->message->dn,
418 status = GUID_from_ndr_blob(guid_blob, &guid);
419 if (!NT_STATUS_IS_OK(status)) {
420 return ldb_module_done(ac->req, NULL, NULL,
421 LDB_ERR_OPERATIONS_ERROR);
424 /* Redundant paranoid check */
425 if (store->num_entries > store->result_array_size) {
426 return ldb_module_done(ac->req, NULL, NULL,
427 LDB_ERR_OPERATIONS_ERROR);
430 store->results[store->num_entries] = guid;
431 store->num_entries++;
434 case LDB_REPLY_REFERRAL:
435 ret = save_referral(store, ares->referral);
436 if (ret != LDB_SUCCESS) {
437 return ldb_module_done(ac->req, NULL, NULL, ret);
442 if (store->num_entries != 0) {
443 store->results = talloc_realloc(store, store->results,
446 if (store->results == NULL) {
447 return ldb_module_done(ac->req, NULL, NULL,
448 LDB_ERR_OPERATIONS_ERROR);
451 store->result_array_size = store->num_entries;
453 ac->store->controls = talloc_move(ac->store, &ares->controls);
454 ret = paged_results(ac);
455 return ldb_module_done(ac->req, ac->controls,
456 ares->response, ret);
462 static struct ldb_control **
463 paged_results_copy_down_controls(TALLOC_CTX *mem_ctx,
464 struct ldb_control **controls)
467 struct ldb_control **new_controls;
468 unsigned int i, j, num_ctrls;
469 if (controls == NULL) {
473 for (num_ctrls = 0; controls[num_ctrls]; num_ctrls++);
475 new_controls = talloc_array(mem_ctx, struct ldb_control *, num_ctrls);
476 if (new_controls == NULL) {
480 for (j = 0, i = 0; i < (num_ctrls); i++) {
481 struct ldb_control *control = controls[i];
482 if (control->oid == NULL) {
485 if (strncmp(control->oid, LDB_CONTROL_PAGED_RESULTS_OID,
486 sizeof(LDB_CONTROL_PAGED_RESULTS_OID)) == 0) {
489 new_controls[j] = talloc_steal(new_controls, control);
492 new_controls[j] = NULL;
496 static const char * const *paged_copy_attrs(TALLOC_CTX *mem_ctx,
497 const char * const *attrs) {
499 const char **new_attrs;
503 new_attrs = ldb_attr_list_copy(mem_ctx, attrs);
505 for (i=0; attrs[i] != NULL; i++) {
506 new_attrs[i] = talloc_strdup(mem_ctx, attrs[i]);
513 * Check if two sets of controls are the same except for the paged results
514 * control in the request controls. This function is messy because request
515 * control lists can contain controls that were NULL'd by the rootdse. We
516 * must ignore those entries. This function is not portable.
518 static bool paged_controls_same(struct ldb_request *req,
519 struct ldb_control **down_controls) {
521 unsigned int num_down_controls, num_non_null_req_controls;
522 struct ldb_control *ctrl;
524 num_down_controls = 0;
525 for (i=0; down_controls[i] != NULL; i++) {
528 ctrl = ldb_request_get_control(req, down_controls[i]->oid);
534 num_non_null_req_controls = 0;
535 for (i=0; req->controls[i] != NULL; i++) {
536 if (req->controls[i]->oid != NULL) {
537 num_non_null_req_controls++;
541 /* At this point we have the number of non-null entries for both
542 * control lists and we know that:
543 * 1. down_controls does not contain the paged control
544 * (because paged_results_copy_down_controls excludes it)
545 * 2. req->controls does contain the paged control
546 * (because this function is only called if this is true)
547 * 3. down_controls is a subset of non-null controls in req->controls
549 * So to confirm that the two lists are identical except for the paged
550 * control, all we need to check is: */
551 if (num_non_null_req_controls == num_down_controls + 1) {
557 static bool paged_attrs_same(const char * const *attrs_1,
558 const char * const *attrs_2) {
560 if (attrs_1 == NULL || attrs_2 == NULL) {
561 if (attrs_1 == NULL && attrs_2 == NULL) {
567 for (i=0; attrs_1[i] != NULL; i++) {
568 if (!ldb_attr_in_list(attrs_2, attrs_1[i])) {
575 static int paged_search(struct ldb_module *module, struct ldb_request *req)
577 struct ldb_context *ldb;
578 struct ldb_control *control;
579 struct private_data *private_data;
580 struct ldb_paged_control *paged_ctrl;
581 struct ldb_request *search_req;
582 struct paged_context *ac;
585 ldb = ldb_module_get_ctx(module);
587 /* check if there's a paged request control */
588 control = ldb_request_get_control(req, LDB_CONTROL_PAGED_RESULTS_OID);
589 if (control == NULL) {
590 /* not found go on */
591 return ldb_next_request(module, req);
594 paged_ctrl = talloc_get_type(control->data, struct ldb_paged_control);
596 return LDB_ERR_PROTOCOL_ERROR;
599 private_data = talloc_get_type(ldb_module_get_private(module),
600 struct private_data);
602 ac = talloc_zero(req, struct paged_context);
604 ldb_set_errstring(ldb, "Out of Memory");
605 return LDB_ERR_OPERATIONS_ERROR;
610 ac->size = paged_ctrl->size;
613 * Apparently some clients send more than 2^31. This
614 * violates the ldap standard, but we need to cope.
615 * In the future, if maximum result sizes are implemented in
616 * Samba, we should also clamp the page size to the maximum
619 ac->size = 0x7FFFFFFF;
622 /* check if it is a continuation search the store */
623 if (paged_ctrl->cookie_len == 0) {
624 struct ldb_control *ext_ctrl;
625 struct ldb_control **controls;
626 static const char * const attrs[1] = { NULL };
628 if (paged_ctrl->size == 0) {
629 return LDB_ERR_OPERATIONS_ERROR;
632 ac->store = new_store(private_data);
633 if (ac->store == NULL) {
634 return LDB_ERR_OPERATIONS_ERROR;
637 controls = req->controls;
638 ext_ctrl = ldb_request_get_control(req,
639 LDB_CONTROL_EXTENDED_DN_OID);
640 if (ext_ctrl == NULL) {
642 * Add extended_dn control to the request if there
643 * isn't already one. We'll get the GUID out of it in
644 * the callback. This is a workaround for the case
645 * where ntsecuritydescriptor forbids fetching GUIDs
646 * for the current user.
648 struct ldb_request *req_extended_dn;
649 struct ldb_extended_dn_control *ext_ctrl_data;
650 req_extended_dn = talloc_zero(req, struct ldb_request);
651 req_extended_dn->controls = req->controls;
652 ext_ctrl_data = talloc_zero(req,
653 struct ldb_extended_dn_control);
654 ext_ctrl_data->type = 1;
656 ret = ldb_request_add_control(req_extended_dn,
657 LDB_CONTROL_EXTENDED_DN_OID,
660 if (ret != LDB_SUCCESS) {
663 controls = req_extended_dn->controls;
666 ret = ldb_build_search_req_ex(&search_req, ldb, ac,
668 req->op.search.scope,
671 //TODO req->op.search.attrs,
674 paged_search_callback,
676 if (ret != LDB_SUCCESS) {
680 ac->store->expr = talloc_steal(ac->store, req->op.search.tree);
681 ac->store->expr_str = ldb_filter_from_tree(ac->store,
682 req->op.search.tree);
683 ac->store->attrs = paged_copy_attrs(ac->store,
684 req->op.search.attrs);
686 /* save it locally and remove it from the list */
687 /* we do not need to replace them later as we
688 * are keeping the original req intact */
689 if (!ldb_save_controls(control, search_req, NULL)) {
690 return LDB_ERR_OPERATIONS_ERROR;
692 ac->store->down_controls =
693 paged_results_copy_down_controls(ac->store, req->controls);
694 if (ac->store->down_controls == NULL) {
695 return LDB_ERR_OPERATIONS_ERROR;
698 return ldb_next_request(module, search_req);
701 struct results_store *current = NULL;
705 /* TODO: age out old outstanding requests */
706 for (current = private_data->store; current != NULL;
707 current = current->next) {
708 if (strcmp(current->cookie, paged_ctrl->cookie) == 0) {
709 current->timestamp = time(NULL);
713 if (current == NULL) {
714 return LDB_ERR_UNWILLING_TO_PERFORM;
717 /* Get the expression string and make sure it didn't change */
718 expr_str = ldb_filter_from_tree(ac, req->op.search.tree);
719 if (expr_str == NULL) {
720 return LDB_ERR_OPERATIONS_ERROR;
723 ret = strcmp(current->expr_str, expr_str);
725 return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
728 bool_ret = paged_controls_same(req, current->down_controls);
729 if (bool_ret == false) {
730 return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
733 bool_ret = paged_attrs_same(req->op.search.attrs,
735 if (bool_ret == false) {
736 return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
739 DLIST_PROMOTE(private_data->store, current);
743 /* check if it is an abandon */
745 return ldb_module_done(req, NULL, NULL,
749 ret = paged_results(ac);
750 if (ret != LDB_SUCCESS) {
751 return ldb_module_done(req, NULL, NULL, ret);
753 return ldb_module_done(req, ac->controls, NULL, LDB_SUCCESS);
757 static int paged_request_init(struct ldb_module *module)
759 struct ldb_context *ldb;
760 struct private_data *data;
763 ldb = ldb_module_get_ctx(module);
765 data = talloc(module, struct private_data);
767 return LDB_ERR_OTHER;
770 data->next_free_id = 1;
771 data->num_stores = 0;
773 ldb_module_set_private(module, data);
775 ret = ldb_mod_register_control(module, LDB_CONTROL_PAGED_RESULTS_OID);
776 if (ret != LDB_SUCCESS) {
777 ldb_debug(ldb, LDB_DEBUG_WARNING,
779 "Unable to register control with rootdse!");
782 return ldb_next_init(module);
785 static const struct ldb_module_ops ldb_paged_results_module_ops = {
786 .name = "dsdb_paged_results",
787 .search = paged_search,
788 .init_context = paged_request_init
791 int ldb_dsdb_paged_results_init(const char *version)
793 LDB_MODULE_CHECK_VERSION(version);
794 return ldb_register_module(&ldb_paged_results_module_ops);