source4/dsdb/samdb/ldb_modules/count_attrs.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2019
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 /*
  21  * Count how often different attributes are searched for, for performance
  22  * analysis. The counts are stored in tdb files in the 'debug' subdirectory of
  23  * Samba installation's private directory, and can be read using
  24  * script/attr_count_read.
  25  */
  26
  27 #include "includes.h"
  28 #include "ldb_module.h"
  29 #include "param/param.h"
  30 #include "lib/tdb_wrap/tdb_wrap.h"
  31 #include "system/filesys.h"
  32
  33 #define NULL_ATTRS "__null_attrs__"
  34 #define EMPTY_ATTRS "__empty_attrs__"
  35 #define UNKNOWN_ATTR "__unknown_attribute__"
  36 #define STAR_ATTR "*"
  37
  38 #define NULL_REQ_PSEUDO_N -2LL;
  39 #define STAR_REQ_PSEUDO_N -4LL;
  40
  41 #undef strcasecmp
  42
  43 struct count_attrs_private {
  44         struct tdb_wrap *requested;
  45         struct tdb_wrap *duplicates;
  46         struct tdb_wrap *found;
  47         struct tdb_wrap *not_found;
  48         struct tdb_wrap *unwanted;
  49         struct tdb_wrap *star_match;
  50         struct tdb_wrap *null_req;
  51         struct tdb_wrap *empty_req;
  52         struct tdb_wrap *req_vs_found;
  53 };
  54
  55
  56 struct count_attrs_context {
  57         struct ldb_module *module;
  58         struct ldb_request *req;
  59         bool has_star;
  60         bool is_null;
  61         const char **requested_attrs;
  62         size_t n_attrs;
  63 };
  64
  65
  66 static int add_key(struct tdb_context *tdb,
  67                    struct TDB_DATA key)
  68 {
  69         int ret;
  70         uint32_t one = 1;
  71         struct TDB_DATA value = {
  72                 .dptr = (uint8_t *)&one,
  73                 .dsize = sizeof(one)
  74         };
  75         ret = tdb_store(tdb,
  76                         key,
  77                         value,
  78                         0);
  79         return ret;
  80 }
  81
  82 static int increment_attr_count(struct tdb_context *tdb,
  83                                 const char *attr)
  84 {
  85         /*
  86          * Note that as we don't lock the database, there is a small window
  87          * between the fetch and store in which identical updates from
  88          * separate processes can race to clobber each other. If this happens
  89          * the stored count will be one less than it should be.
  90          *
  91          * We don't worry about that because it should be quite rare and
  92          * agnostic as to which counts are affected, meaning the overall
  93          * statistical truth is preserved.
  94          */
  95         int ret;
  96         uint32_t *val;
  97         TDB_DATA key = {
  98                 .dptr = discard_const(attr),
  99                 .dsize = strlen(attr)
 100         };
 101
 102         TDB_DATA data = tdb_fetch(tdb, key);
 103         if (data.dptr == NULL) {
 104                 ret = tdb_error(tdb);
 105                 if (ret != TDB_ERR_NOEXIST) {
 106                         const char *errstr = tdb_errorstr(tdb);
 107                         DBG_ERR("tdb fetch error: %s\n", errstr);
 108                         return LDB_ERR_OPERATIONS_ERROR;
 109                 }
 110                 /* this key is unknown. We'll add it and get out of here. */
 111                 ret = add_key(tdb, key);
 112                 if (ret != 0) {
 113                         DBG_ERR("could not add %s: %d\n", attr, ret);
 114                 }
 115                 return ret;
 116         }
 117
 118         val = (uint32_t *)data.dptr;
 119         (*val)++;
 120
 121         ret = tdb_store(tdb,
 122                         key,
 123                         data,
 124                         0);
 125
 126         if (ret != 0) {
 127                 const char *errstr = tdb_errorstr(tdb);
 128                 DBG_ERR("tdb store error: %s\n", errstr);
 129                 free(data.dptr);
 130                 return LDB_ERR_OPERATIONS_ERROR;
 131         }
 132         free(data.dptr);
 133         return LDB_SUCCESS;
 134 }
 135
 136
 137 static int increment_req_vs_found(struct tdb_context *tdb,
 138                                   struct count_attrs_context *ac,
 139                                   size_t n_found)
 140 {
 141         /*
 142          * Here we record the number of elements in each reply along with the
 143          * number of attributes in the corresponding request. Requests for
 144          * NULL and "*" are arbitrarily given the attribute counts -2 and -4
 145          * respectively. This leads them to be plotted as two stacks on the
 146          * left hand side of the scatter plot.
 147          */
 148         int ret;
 149         ssize_t k[2];
 150         uint32_t *val = NULL;
 151         TDB_DATA key = {
 152                 .dptr = (unsigned char *)k,
 153                 .dsize = sizeof(k)
 154         };
 155         TDB_DATA data = {0};
 156         ssize_t n_req = ac->n_attrs;
 157         if (ac->is_null) {
 158                 n_req = NULL_REQ_PSEUDO_N;
 159         } else if (ac->has_star) {
 160                 n_req = STAR_REQ_PSEUDO_N;
 161         }
 162         k[0] = n_req;
 163         k[1] = n_found;
 164
 165         data = tdb_fetch(tdb, key);
 166         if (data.dptr == NULL) {
 167                 ret = tdb_error(tdb);
 168                 if (ret != TDB_ERR_NOEXIST) {
 169                         const char *errstr = tdb_errorstr(tdb);
 170                         DBG_ERR("req vs found fetch error: %s\n", errstr);
 171                         return LDB_ERR_OPERATIONS_ERROR;
 172                 }
 173                 /* unknown key */
 174                 ret = add_key(tdb, key);
 175                 if (ret != 0) {
 176                         DBG_ERR("could not add req vs found %zu:%zu: %d\n",
 177                                 n_req, n_found, ret);
 178                 }
 179                 return ret;
 180         }
 181
 182         val = (uint32_t *)data.dptr;
 183         (*val)++;
 184
 185         ret = tdb_store(tdb, key, data, 0);
 186         if (ret != 0) {
 187                 const char *errstr = tdb_errorstr(tdb);
 188                 DBG_ERR("req vs found store error: %s\n", errstr);
 189                 free(data.dptr);
 190                 return LDB_ERR_OPERATIONS_ERROR;
 191         }
 192         free(data.dptr);
 193         return LDB_SUCCESS;
 194 }
 195
 196
 197 static int strcasecmp_ptr(const char **a, const char **b)
 198 {
 199         return strcasecmp(*a, *b);
 200 }
 201
 202
 203 static const char **get_sorted_attrs(TALLOC_CTX *mem_ctx,
 204                                      const char * const *unsorted_attrs,
 205                                      size_t n_attrs)
 206 {
 207         size_t i;
 208         const char **attrs = talloc_array(mem_ctx,
 209                                           const char *,
 210                                           n_attrs);
 211
 212         if (attrs == NULL) {
 213                 return NULL;
 214         }
 215         for (i = 0; i < n_attrs; i++) {
 216                 const char *a = unsorted_attrs[i];
 217                 if (a == NULL) {
 218                         DBG_ERR("attrs have disappeared! "
 219                                 "wanted %zu; got %zu\n",
 220                                 n_attrs, i);
 221                         talloc_free(attrs);
 222                         return NULL;
 223                 }
 224                 attrs[i] = a;
 225         }
 226
 227         qsort(attrs, n_attrs, sizeof(char *), QSORT_CAST strcasecmp_ptr);
 228         return attrs;
 229 }
 230
 231
 232
 233 static int count_attrs_search_callback(struct ldb_request *req,
 234                                        struct ldb_reply *ares)
 235 {
 236         struct count_attrs_private *priv = NULL;
 237         struct ldb_message *msg = NULL;
 238         size_t i, j;
 239         int ret;
 240
 241         struct count_attrs_context *ac = \
 242                 talloc_get_type(req->context,
 243                                 struct count_attrs_context);
 244
 245         struct ldb_context *ldb = ldb_module_get_ctx(ac->module);
 246
 247         priv = talloc_get_type_abort(ldb_module_get_private(ac->module),
 248                                      struct count_attrs_private);
 249
 250         if (ares == NULL) {
 251                 DBG_ERR("ares is NULL\n");
 252                 return ldb_module_done(ac->req, NULL, NULL,
 253                                        LDB_ERR_OPERATIONS_ERROR);
 254         }
 255         if (ares->error != LDB_SUCCESS) {
 256                 DBG_INFO("ares error %d\n", ares->error);
 257                 return ldb_module_done(ac->req, ares->controls,
 258                                         ares->response, ares->error);
 259         }
 260
 261         switch (ares->type) {
 262         case LDB_REPLY_REFERRAL:
 263                 return ldb_module_send_referral(ac->req, ares->referral);
 264
 265         case LDB_REPLY_DONE:
 266                 return ldb_module_done(ac->req, ares->controls,
 267                                        ares->response, LDB_SUCCESS);
 268
 269         case LDB_REPLY_ENTRY:
 270                 msg = ares->message;
 271                 if (ac->is_null || ac->n_attrs == 0) {
 272                         struct tdb_context *tdb = NULL;
 273                         /*
 274                          * Note when attributes are found when the requested
 275                          * list was empty or NULL
 276                          */
 277                         if (ac->is_null) {
 278                                 tdb = priv->null_req->tdb;
 279                         } else {
 280                                 tdb = priv->empty_req->tdb;
 281                         }
 282                         for (i = 0; i < msg->num_elements; i++) {
 283                                 const char *name = msg->elements[i].name;
 284                                 ret = increment_attr_count(tdb, name);
 285                                 if (ret != LDB_SUCCESS) {
 286                                         talloc_free(ares);
 287                                         DBG_ERR("inc failed\n");
 288                                         return ret;
 289                                 }
 290                         }
 291                 } else {
 292                         /*
 293                          * We make sorted lists of the requested and found
 294                          * elements, which makes it easy to find missing or
 295                          * intruding values.
 296                          */
 297                         struct tdb_context *found_tdb = priv->found->tdb;
 298                         struct tdb_context *unwanted_tdb = \
 299                                 priv->unwanted->tdb;
 300                         struct tdb_context *star_match_tdb = \
 301                                 priv->star_match->tdb;
 302                         struct tdb_context *not_found_tdb = \
 303                                 priv->not_found->tdb;
 304
 305                         const char **requested_attrs = ac->requested_attrs;
 306                         const char **found_attrs = \
 307                                 talloc_array(ac, const char *,
 308                                              msg->num_elements);
 309                         if (found_attrs == NULL) {
 310                                 return ldb_oom(ldb);
 311                         }
 312
 313                         for (i = 0; i < msg->num_elements; i++) {
 314                                 found_attrs[i] = msg->elements[i].name;
 315                         }
 316
 317                         qsort(found_attrs, msg->num_elements, sizeof(char *),
 318                               QSORT_CAST strcasecmp_ptr);
 319
 320
 321                         /* find and report duplicates */
 322                         for (i = 1; i < msg->num_elements; i++) {
 323                                 if (strcasecmp(found_attrs[i],
 324                                                found_attrs[i - 1]) == 0) {
 325                                         DBG_ERR("duplicate element: %s!\n",
 326                                                 found_attrs[i]);
 327                                         /*
 328                                          * If this happens it will muck up our
 329                                          * counts, but probably have worse
 330                                          * effects on the rest of the module
 331                                          * stack. */
 332                                 }
 333                         }
 334
 335                         /*
 336                          * This next bit is like the merge stage of a
 337                          * mergesort, but instead of merging we only detect
 338                          * absense or presence.
 339                          */
 340                         i = 0;
 341                         j = 0;
 342                         while (i < ac->n_attrs ||
 343                                j < msg->num_elements) {
 344                                 int cmp;
 345                                 if (i >= ac->n_attrs) {
 346                                         cmp = 1;
 347                                 } else if (j >= msg->num_elements) {
 348                                         cmp = -1;
 349                                 } else {
 350                                         cmp = strcasecmp(requested_attrs[i],
 351                                                          found_attrs[j]
 352                                                 );
 353                                 }
 354
 355                                 if (cmp < 0) {
 356                                         /* We did not find the element */
 357                                         ret = increment_attr_count(
 358                                                 not_found_tdb,
 359                                                 requested_attrs[i]);
 360                                         i++;
 361                                 } else if (cmp > 0) {
 362                                         /*
 363                                          * We found the element, but didn't
 364                                          * specifically ask for it.
 365                                          */
 366                                         if (ac->has_star) {
 367                                                 ret = increment_attr_count(
 368                                                         star_match_tdb,
 369                                                         found_attrs[j]);
 370                                         } else {
 371                                                 ret = increment_attr_count(
 372                                                         unwanted_tdb,
 373                                                         found_attrs[j]);
 374                                         }
 375                                         j++;
 376                                 } else {
 377                                         /* We got what we asked for. */
 378                                         ret = increment_attr_count(
 379                                                 found_tdb,
 380                                                 found_attrs[j]);
 381                                         i++;
 382                                         j++;
 383                                 }
 384                                 if (ret != LDB_SUCCESS) {
 385                                         talloc_free(ares);
 386                                         DBG_ERR("inc failed\n");
 387                                         return ret;
 388                                 }
 389                         }
 390                 }
 391                 ret = increment_req_vs_found(priv->req_vs_found->tdb,
 392                                              ac,
 393                                              msg->num_elements);
 394
 395                 if (ret != LDB_SUCCESS) {
 396                         talloc_free(ares);
 397                         DBG_ERR("inc of req vs found failed\n");
 398                         return ret;
 399                 }
 400
 401                 return ldb_module_send_entry(
 402                         ac->req,
 403                         ares->message,
 404                         ares->controls);
 405         }
 406
 407         talloc_free(ares);
 408         return LDB_SUCCESS;
 409 }
 410
 411
 412 static int count_attrs_search(struct ldb_module *module,
 413                               struct ldb_request *req)
 414 {
 415         int ret;
 416         const char * const *attrs = req->op.search.attrs;
 417         struct count_attrs_private *count_attrs_private = NULL;
 418         struct tdb_context *tdb = NULL;
 419         struct ldb_request *down_req = NULL;
 420         struct count_attrs_context *ac = NULL;
 421         bool has_star = false;
 422         bool is_null = false;
 423         size_t n_attrs = 0;
 424         const char **sorted_attrs = NULL;
 425         struct ldb_context *ldb = ldb_module_get_ctx(module);
 426
 427
 428         void *untyped_private = ldb_module_get_private(module);
 429         if (untyped_private == NULL) {
 430                 /*
 431                  * There are some cases (in early start up, and during a
 432                  * backup restore) in which we get a NULL private object, in
 433                  * which case all we can do is ignore it and pass the request
 434                  * on unexamined.
 435                  */
 436                 return ldb_next_request(module, req);
 437         }
 438
 439         count_attrs_private = talloc_get_type_abort(untyped_private,
 440                                                     struct count_attrs_private);
 441         tdb = count_attrs_private->requested->tdb;
 442
 443         ac = talloc_zero(req, struct count_attrs_context);
 444         if (ac == NULL) {
 445                 return ldb_oom(ldb);
 446         }
 447
 448         if (attrs == NULL) {
 449                 ret = increment_attr_count(tdb, NULL_ATTRS);
 450                 if (ret != LDB_SUCCESS) {
 451                         talloc_free(ac);
 452                         return ret;
 453                 }
 454                 is_null = true;
 455         } else if (attrs[0] == NULL) {
 456                 ret = increment_attr_count(tdb, EMPTY_ATTRS);
 457                 if (ret != LDB_SUCCESS) {
 458                         talloc_free(ac);
 459                         return ret;
 460                 }
 461         } else {
 462                 size_t i, j;
 463                 for (i = 0; attrs[i] != NULL; i++) {
 464                         ret = increment_attr_count(tdb, attrs[i]);
 465                         if (ret != LDB_SUCCESS) {
 466                                 talloc_free(ac);
 467                                 return ret;
 468                         }
 469                         if (strcmp("*", attrs[i]) == 0) {
 470                                 has_star = true;
 471                         }
 472                 }
 473                 n_attrs = i;
 474                 sorted_attrs = get_sorted_attrs(req,
 475                                                 attrs,
 476                                                 n_attrs);
 477                 /*
 478                  * Find, report, and remove duplicates. Duplicate attrs in
 479                  * requests are allowed, but don't work well with our
 480                  * merge-count algorithm.
 481                  */
 482                 j = 0;
 483                 for (i = 1; i < n_attrs; i++) {
 484                         if (strcasecmp(sorted_attrs[i],
 485                                        sorted_attrs[j]) == 0) {
 486                                 ret = increment_attr_count(
 487                                         count_attrs_private->duplicates->tdb,
 488                                         sorted_attrs[i]);
 489                                 if (ret != LDB_SUCCESS) {
 490                                         talloc_free(ac);
 491                                         return ret;
 492                                 }
 493                         } else {
 494                                 j++;
 495                                 if (j != i) {
 496                                         sorted_attrs[j] = sorted_attrs[i];
 497                                 }
 498                         }
 499                 }
 500                 n_attrs = j;
 501         }
 502
 503         ac->module = module;
 504         ac->req = req;
 505         ac->has_star = has_star;
 506         ac->is_null = is_null;
 507         ac->n_attrs = n_attrs;
 508         ac->requested_attrs = sorted_attrs;
 509
 510         ret = ldb_build_search_req_ex(&down_req,
 511                                       ldb,
 512                                       ac,
 513                                       req->op.search.base,
 514                                       req->op.search.scope,
 515                                       req->op.search.tree,
 516                                       req->op.search.attrs,
 517                                       req->controls,
 518                                       ac,
 519                                       count_attrs_search_callback,
 520                                       req);
 521         if (ret != LDB_SUCCESS) {
 522                 return ldb_operr(ldb);
 523         }
 524
 525         return ldb_next_request(module, down_req);
 526 }
 527
 528
 529 static struct tdb_wrap * open_private_tdb(TALLOC_CTX *mem_ctx,
 530                                           struct loadparm_context *lp_ctx,
 531                                           const char *name)
 532 {
 533         struct tdb_wrap *store = NULL;
 534         char *filename = lpcfg_private_path(mem_ctx, lp_ctx, name);
 535
 536         if (filename == NULL) {
 537                 return NULL;
 538         }
 539
 540         store = tdb_wrap_open(mem_ctx, filename, 1000,
 541                               TDB_CLEAR_IF_FIRST,
 542                               O_RDWR | O_CREAT,
 543                               0660);
 544         if (store == NULL) {
 545                 DBG_ERR("failed to open tdb at %s\n", filename);
 546         }
 547         TALLOC_FREE(filename);
 548         return store;
 549 }
 550
 551 static int make_private_dir(TALLOC_CTX *mem_ctx,
 552                             struct loadparm_context *lp_ctx,
 553                             const char *name)
 554 {
 555         int ret;
 556         char *dirname = lpcfg_private_path(mem_ctx, lp_ctx, name);
 557         if (dirname == NULL) {
 558                 return -1;
 559         }
 560         ret = mkdir(dirname, 0755);
 561         TALLOC_FREE(dirname);
 562         return ret;
 563 }
 564
 565
 566 static int count_attrs_init(struct ldb_module *module)
 567 {
 568         struct ldb_context *ldb = NULL;
 569         struct count_attrs_private *data = NULL;
 570         struct loadparm_context *lp_ctx = NULL;
 571         int ret;
 572
 573         ldb = ldb_module_get_ctx(module);
 574
 575         data = talloc_zero(module, struct count_attrs_private);
 576         if (data == NULL) {
 577                 return ldb_oom(ldb);
 578         }
 579
 580         lp_ctx = talloc_get_type(ldb_get_opaque(ldb, "loadparm"),
 581                                  struct loadparm_context);
 582
 583         ret = make_private_dir(data, lp_ctx, "debug");
 584         if (ret != 0) {
 585                 goto no_private_dir;
 586         }
 587         data->requested = open_private_tdb(data, lp_ctx,
 588                                            "debug/attr_counts_requested.tdb");
 589         data->duplicates =                      \
 590                 open_private_tdb(data, lp_ctx,
 591                                  "debug/attr_counts_duplicates.tdb");
 592         data->found = open_private_tdb(data, lp_ctx,
 593                                        "debug/attr_counts_found.tdb");
 594         data->not_found = open_private_tdb(data, lp_ctx,
 595                                            "debug/attr_counts_not_found.tdb");
 596         data->unwanted = open_private_tdb(data, lp_ctx,
 597                                           "debug/attr_counts_unwanted.tdb");
 598         data->star_match = open_private_tdb(data, lp_ctx,
 599                                             "debug/attr_counts_star_match.tdb");
 600         data->null_req = open_private_tdb(data, lp_ctx,
 601                                           "debug/attr_counts_null_req.tdb");
 602         data->empty_req = open_private_tdb(data, lp_ctx,
 603                                            "debug/attr_counts_empty_req.tdb");
 604         data->req_vs_found =                    \
 605                 open_private_tdb(data, lp_ctx,
 606                                  "debug/attr_counts_req_vs_found.tdb");
 607         if (data->requested == NULL ||
 608             data->duplicates == NULL ||
 609             data->found == NULL ||
 610             data->not_found == NULL ||
 611             data->unwanted == NULL ||
 612             data->star_match == NULL ||
 613             data->null_req == NULL ||
 614             data->empty_req == NULL ||
 615             data->req_vs_found == NULL) {
 616                 goto no_private_dir;
 617         }
 618
 619         ldb_module_set_private(module, data);
 620         return ldb_next_init(module);
 621
 622   no_private_dir:
 623         /*
 624          * If we leave the private data NULL, the search function knows not to
 625          * do anything.
 626          */
 627         DBG_WARNING("the count_attrs module could not open its databases\n");
 628         DBG_WARNING("attributes will not be counted.\n");
 629         TALLOC_FREE(data);
 630         ldb_module_set_private(module, NULL);
 631         return ldb_next_init(module);
 632 }
 633
 634 static const struct ldb_module_ops ldb_count_attrs_module_ops = {
 635         .name              = "count_attrs",
 636         .search            = count_attrs_search,
 637         .init_context      = count_attrs_init
 638 };
 639
 640 int ldb_count_attrs_init(const char *version)
 641 {
 642         LDB_MODULE_CHECK_VERSION(version);
 643         return ldb_register_module(&ldb_count_attrs_module_ops);
 644 }