source4/dsdb/schema/schema_query.c

   1 /*
   2    Unix SMB/CIFS mplementation.
   3    DSDB schema header
   4
   5    Copyright (C) Stefan Metzmacher <metze@samba.org> 2006-2007
   6    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2006-2008
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20
  21 */
  22
  23 #include "includes.h"
  24 #include "dsdb/samdb/samdb.h"
  25
  26 /* a binary array search, where the array is an array of pointers to structures,
  27    and we want to find a match for 'target' on 'field' in those structures.
  28
  29    Inputs:
  30       array:          base pointer to an array of structures
  31       arrray_size:    number of elements in the array
  32       field:          the name of the field in the structure we are keying off
  33       target:         the field value we are looking for
  34       comparison_fn:  the comparison function
  35       result:         where the result of the search is put
  36
  37    if the element is found, then 'result' is set to point to the found array element. If not,
  38    then 'result' is set to NULL.
  39
  40    The array is assumed to be sorted by the same comparison_fn as the
  41    search (with, for example, qsort)
  42  */
  43 #define BINARY_ARRAY_SEARCH(array, array_size, field, target, comparison_fn, result) do { \
  44         int32_t _b, _e; \
  45         (result) = NULL; \
  46         for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
  47                 int32_t _i = (_b+_e)/2; \
  48                 int _r = comparison_fn(target, array[_i]->field); \
  49                 if (_r == 0) { (result) = array[_i]; break; } \
  50                 if (_r < 0) _e = _i - 1; else _b = _i + 1; \
  51         } } while (0)
  52
  53
  54 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
  55                                                       const struct dsdb_schema *schema,
  56                                                       const char **class_list,
  57                                                       enum dsdb_attr_list_query query);
  58
  59 static int uint32_cmp(uint32_t c1, uint32_t c2)
  60 {
  61         return c1 - c2;
  62 }
  63
  64 static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)
  65 {
  66         int ret = strncasecmp((const char *)target->data, str, target->length);
  67         if (ret == 0) {
  68                 return (target->length - strlen(str));
  69         }
  70         return ret;
  71 }
  72
  73 const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
  74                                                               uint32_t id)
  75 {
  76         struct dsdb_attribute *c;
  77
  78         /*
  79          * 0xFFFFFFFF is used as value when no mapping table is available,
  80          * so don't try to match with it
  81          */
  82         if (id == 0xFFFFFFFF) return NULL;
  83
  84         BINARY_ARRAY_SEARCH(schema->attributes_by_attributeID_id,
  85                             schema->num_attributes, attributeID_id, id, uint32_cmp, c);
  86         return c;
  87 }
  88
  89 const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
  90                                                                const char *oid)
  91 {
  92         struct dsdb_attribute *c;
  93
  94         if (!oid) return NULL;
  95
  96         BINARY_ARRAY_SEARCH(schema->attributes_by_attributeID_oid,
  97                             schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
  98         return c;
  99 }
 100
 101 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
 102                                                                const char *name)
 103 {
 104         struct dsdb_attribute *c;
 105
 106         if (!name) return NULL;
 107
 108         BINARY_ARRAY_SEARCH(schema->attributes_by_lDAPDisplayName,
 109                             schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
 110         return c;
 111 }
 112
 113 const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
 114                                                       int linkID)
 115 {
 116         struct dsdb_attribute *c;
 117
 118         BINARY_ARRAY_SEARCH(schema->attributes_by_linkID,
 119                             schema->num_attributes, linkID, linkID, uint32_cmp, c);
 120         return c;
 121 }
 122
 123 const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
 124                                                     uint32_t id)
 125 {
 126         struct dsdb_class *c;
 127
 128         /*
 129          * 0xFFFFFFFF is used as value when no mapping table is available,
 130          * so don't try to match with it
 131          */
 132         if (id == 0xFFFFFFFF) return NULL;
 133
 134         BINARY_ARRAY_SEARCH(schema->classes_by_governsID_id,
 135                             schema->num_classes, governsID_id, id, uint32_cmp, c);
 136         return c;
 137 }
 138
 139 const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
 140                                                      const char *oid)
 141 {
 142         struct dsdb_class *c;
 143         if (!oid) return NULL;
 144         BINARY_ARRAY_SEARCH(schema->classes_by_governsID_oid,
 145                             schema->num_classes, governsID_oid, oid, strcasecmp, c);
 146         return c;
 147 }
 148
 149 const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
 150                                                        const char *name)
 151 {
 152         struct dsdb_class *c;
 153         if (!name) return NULL;
 154         BINARY_ARRAY_SEARCH(schema->classes_by_lDAPDisplayName,
 155                             schema->num_classes, lDAPDisplayName, name, strcasecmp, c);
 156         return c;
 157 }
 158
 159 const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
 160                                                                struct ldb_val *name)
 161 {
 162         struct dsdb_class *c;
 163         if (!name) return NULL;
 164         BINARY_ARRAY_SEARCH(schema->classes_by_lDAPDisplayName,
 165                             schema->num_classes, lDAPDisplayName, name, strcasecmp_with_ldb_val, c);
 166         return c;
 167 }
 168
 169 const struct dsdb_class *dsdb_class_by_cn(const struct dsdb_schema *schema,
 170                                           const char *cn)
 171 {
 172         struct dsdb_class *c;
 173         if (!cn) return NULL;
 174         BINARY_ARRAY_SEARCH(schema->classes_by_cn,
 175                             schema->num_classes, cn, cn, strcasecmp, c);
 176         return c;
 177 }
 178
 179 const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
 180                                                   struct ldb_val *cn)
 181 {
 182         struct dsdb_class *c;
 183         if (!cn) return NULL;
 184         BINARY_ARRAY_SEARCH(schema->classes_by_cn,
 185                             schema->num_classes, cn, cn, strcasecmp_with_ldb_val, c);
 186         return c;
 187 }
 188
 189 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
 190                                        uint32_t id)
 191 {
 192         const struct dsdb_attribute *a;
 193         const struct dsdb_class *c;
 194
 195         a = dsdb_attribute_by_attributeID_id(schema, id);
 196         if (a) {
 197                 return a->lDAPDisplayName;
 198         }
 199
 200         c = dsdb_class_by_governsID_id(schema, id);
 201         if (c) {
 202                 return c->lDAPDisplayName;
 203         }
 204
 205         return NULL;
 206 }
 207
 208 /**
 209     Return a list of linked attributes, in lDAPDisplayName format.
 210
 211     This may be used to determine if a modification would require
 212     backlinks to be updated, for example
 213 */
 214
 215 WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)
 216 {
 217         const char **attr_list = NULL;
 218         struct dsdb_attribute *cur;
 219         int i = 0;
 220         for (cur = schema->attributes; cur; cur = cur->next) {
 221                 if (cur->linkID == 0) continue;
 222
 223                 attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);
 224                 if (!attr_list) {
 225                         return WERR_NOMEM;
 226                 }
 227                 attr_list[i] = cur->lDAPDisplayName;
 228                 i++;
 229         }
 230         attr_list[i] = NULL;
 231         *attr_list_ret = attr_list;
 232         return WERR_OK;
 233 }
 234
 235 const char **merge_attr_list(TALLOC_CTX *mem_ctx,
 236                        const char **attrs, const char * const*new_attrs)
 237 {
 238         const char **ret_attrs;
 239         int i;
 240         size_t new_len, orig_len = str_list_length(attrs);
 241         if (!new_attrs) {
 242                 return attrs;
 243         }
 244
 245         ret_attrs = talloc_realloc(mem_ctx,
 246                                    attrs, const char *, orig_len + str_list_length(new_attrs) + 1);
 247         if (ret_attrs) {
 248                 for (i=0; i < str_list_length(new_attrs); i++) {
 249                         ret_attrs[orig_len + i] = new_attrs[i];
 250                 }
 251                 new_len = orig_len + str_list_length(new_attrs);
 252
 253                 ret_attrs[new_len] = NULL;
 254         }
 255
 256         return ret_attrs;
 257 }
 258
 259 /*
 260   Return a merged list of the attributes of exactly one class (not
 261   considering subclasses, auxillary classes etc)
 262 */
 263
 264 const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
 265 {
 266         const char **attr_list = NULL;
 267         switch (query) {
 268         case DSDB_SCHEMA_ALL_MAY:
 269                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
 270                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
 271                 break;
 272
 273         case DSDB_SCHEMA_ALL_MUST:
 274                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
 275                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
 276                 break;
 277
 278         case DSDB_SCHEMA_SYS_MAY:
 279                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
 280                 break;
 281
 282         case DSDB_SCHEMA_SYS_MUST:
 283                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
 284                 break;
 285
 286         case DSDB_SCHEMA_MAY:
 287                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
 288                 break;
 289
 290         case DSDB_SCHEMA_MUST:
 291                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
 292                 break;
 293
 294         case DSDB_SCHEMA_ALL:
 295                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
 296                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
 297                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
 298                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
 299                 break;
 300         }
 301         return attr_list;
 302 }
 303
 304 static const char **attribute_list_from_class(TALLOC_CTX *mem_ctx,
 305                                               const struct dsdb_schema *schema,
 306                                               const struct dsdb_class *sclass,
 307                                               enum dsdb_attr_list_query query)
 308 {
 309         const char **this_class_list;
 310         const char **system_recursive_list;
 311         const char **recursive_list;
 312         const char **attr_list;
 313
 314         this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
 315
 316         recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
 317                                                            sclass->systemAuxiliaryClass,
 318                                                            query);
 319
 320         system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
 321                                                                   sclass->auxiliaryClass,
 322                                                                   query);
 323
 324         attr_list = this_class_list;
 325         attr_list = merge_attr_list(mem_ctx, attr_list, recursive_list);
 326         attr_list = merge_attr_list(mem_ctx, attr_list, system_recursive_list);
 327         return attr_list;
 328 }
 329
 330 /* Return a full attribute list for a given class list (as a ldb_message_element)
 331
 332    Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
 333  */
 334 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
 335                                                       const struct dsdb_schema *schema,
 336                                                       const char **class_list,
 337                                                       enum dsdb_attr_list_query query)
 338 {
 339         int i;
 340         const char **attr_list = NULL;
 341
 342         for (i=0; class_list && class_list[i]; i++) {
 343                 const char **sclass_list
 344                         = attribute_list_from_class(mem_ctx, schema,
 345                                                     dsdb_class_by_lDAPDisplayName(schema, class_list[i]),
 346                                                     query);
 347
 348                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
 349         }
 350         return attr_list;
 351 }
 352
 353 /* Return a full attribute list for a given class list (as a ldb_message_element)
 354
 355    Using the ldb_message_element ensures we do length-limited
 356    comparisons, rather than casting the possibly-unterminated string
 357
 358    Via attribute_list_from_class() this calls
 359    dsdb_full_attribute_list_internal() when recursing on auxiliary classes
 360  */
 361 static const char **dsdb_full_attribute_list_internal_el(TALLOC_CTX *mem_ctx,
 362                                                          const struct dsdb_schema *schema,
 363                                                          const struct ldb_message_element *el,
 364                                                          enum dsdb_attr_list_query query)
 365 {
 366         int i;
 367         const char **attr_list = NULL;
 368
 369         for (i=0; i < el->num_values; i++) {
 370                 const char **sclass_list
 371                         = attribute_list_from_class(mem_ctx, schema,
 372                                                     dsdb_class_by_lDAPDisplayName_ldb_val(schema, &el->values[i]),
 373                                                     query);
 374
 375                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
 376         }
 377         return attr_list;
 378 }
 379
 380 /* Helper function to remove duplicates from the attribute list to be returned */
 381 static const char **dedup_attr_list(const char **attr_list)
 382 {
 383         size_t new_len = str_list_length(attr_list);
 384         /* Remove duplicates */
 385         if (new_len > 1) {
 386                 int i;
 387                 qsort(attr_list, new_len,
 388                       sizeof(*attr_list),
 389                       (comparison_fn_t)strcasecmp);
 390
 391                 for (i=1 ; i < new_len; i++) {
 392                         const char **val1 = &attr_list[i-1];
 393                         const char **val2 = &attr_list[i];
 394                         if (ldb_attr_cmp(*val1, *val2) == 0) {
 395                                 memmove(val1, val2, (new_len - i) * sizeof( *attr_list));
 396                                 new_len--;
 397                                 i--;
 398                         }
 399                 }
 400         }
 401         return attr_list;
 402 }
 403
 404 /* Return a full attribute list for a given class list (as a ldb_message_element)
 405
 406    Using the ldb_message_element ensures we do length-limited
 407    comparisons, rather than casting the possibly-unterminated string
 408
 409    The result contains only unique values
 410  */
 411 const char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,
 412                                       const struct dsdb_schema *schema,
 413                                       const struct ldb_message_element *class_list,
 414                                       enum dsdb_attr_list_query query)
 415 {
 416         const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
 417         return dedup_attr_list(attr_list);
 418 }