2 Unix SMB/CIFS Implementation.
5 Copyright (C) Stefan Metzmacher <metze@samba.org> 2006-2007
6 Copyright (C) Andrew Bartlett <abartlet@samba.org> 2006-2008
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.
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.
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/>.
24 #include "dsdb/samdb/samdb.h"
25 #include <ldb_module.h>
26 #include "lib/util/binsearch.h"
27 #include "lib/util/tsort.h"
28 #include "util/dlinklist.h"
33 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
34 const struct dsdb_schema *schema,
35 const char **class_list,
36 enum dsdb_attr_list_query query);
38 static int uint32_cmp(uint32_t c1, uint32_t c2)
40 if (c1 == c2) return 0;
41 return c1 > c2 ? 1 : -1;
44 static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)
46 int ret = strncasecmp((const char *)target->data, str, target->length);
48 size_t len = strlen(str);
49 if (target->length > len) {
50 if (target->data[len] == 0) {
55 return (target->length - len);
60 const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
63 struct dsdb_attribute *c;
66 * 0xFFFFFFFF is used as value when no mapping table is available,
67 * so don't try to match with it
69 if (id == 0xFFFFFFFF) return NULL;
71 /* check for msDS-IntId type attribute */
72 if (dsdb_pfm_get_attid_type(id) == DSDB_ATTID_TYPE_INTID) {
73 BINARY_ARRAY_SEARCH_P(schema->attributes_by_msDS_IntId,
74 schema->num_int_id_attr, msDS_IntId, id, uint32_cmp, c);
78 BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,
79 schema->num_attributes, attributeID_id, id, uint32_cmp, c);
83 const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
86 struct dsdb_attribute *c;
88 if (!oid) return NULL;
90 BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_oid,
91 schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
95 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
98 struct dsdb_attribute *c;
100 if (!name) return NULL;
102 BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
103 schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
107 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
108 const struct ldb_val *name)
110 struct dsdb_attribute *a;
112 if (!name) return NULL;
114 BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
115 schema->num_attributes, lDAPDisplayName, name, strcasecmp_with_ldb_val, a);
119 const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
122 struct dsdb_attribute *c;
124 BINARY_ARRAY_SEARCH_P(schema->attributes_by_linkID,
125 schema->num_attributes, linkID, linkID, uint32_cmp, c);
129 const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
132 struct dsdb_class *c;
135 * 0xFFFFFFFF is used as value when no mapping table is available,
136 * so don't try to match with it
138 if (id == 0xFFFFFFFF) return NULL;
140 BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_id,
141 schema->num_classes, governsID_id, id, uint32_cmp, c);
145 const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
148 struct dsdb_class *c;
149 if (!oid) return NULL;
150 BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_oid,
151 schema->num_classes, governsID_oid, oid, strcasecmp, c);
155 const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
158 struct dsdb_class *c;
159 if (!name) return NULL;
160 BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,
161 schema->num_classes, lDAPDisplayName, name, strcasecmp, c);
165 const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
166 const struct ldb_val *name)
168 struct dsdb_class *c;
169 if (!name) return NULL;
170 BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,
171 schema->num_classes, lDAPDisplayName, name, strcasecmp_with_ldb_val, c);
175 const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
176 const struct ldb_val *cn)
178 struct dsdb_class *c;
179 if (!cn) return NULL;
180 BINARY_ARRAY_SEARCH_P(schema->classes_by_cn,
181 schema->num_classes, cn, cn, strcasecmp_with_ldb_val, c);
185 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
188 const struct dsdb_attribute *a;
189 const struct dsdb_class *c;
191 a = dsdb_attribute_by_attributeID_id(schema, id);
193 return a->lDAPDisplayName;
196 c = dsdb_class_by_governsID_id(schema, id);
198 return c->lDAPDisplayName;
205 Return a list of linked attributes, in lDAPDisplayName format.
207 This may be used to determine if a modification would require
208 backlinks to be updated, for example
211 WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)
213 const char **attr_list = NULL;
214 struct dsdb_attribute *cur;
216 for (cur = schema->attributes; cur; cur = cur->next) {
217 if (cur->linkID == 0) continue;
219 attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);
221 return WERR_NOT_ENOUGH_MEMORY;
223 attr_list[i] = cur->lDAPDisplayName;
226 if (attr_list != NULL && attr_list[i] != NULL) {
229 *attr_list_ret = attr_list;
233 const char **merge_attr_list(TALLOC_CTX *mem_ctx,
234 const char **attrs, const char * const*new_attrs)
236 const char **ret_attrs;
238 size_t new_len, new_attr_len, orig_len = str_list_length(attrs);
239 if (new_attrs == NULL || new_attrs[0] == NULL) {
242 new_attr_len = str_list_length(new_attrs);
244 ret_attrs = talloc_realloc(mem_ctx,
245 attrs, const char *, orig_len + new_attr_len + 1);
247 for (i = 0; i < new_attr_len; i++) {
248 ret_attrs[orig_len + i] = new_attrs[i];
250 new_len = orig_len + new_attr_len;
252 ret_attrs[new_len] = NULL;
259 Return a merged list of the attributes of exactly one class (not
260 considering subclasses, auxillary classes etc)
263 const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
265 const char **attr_list = NULL;
267 case DSDB_SCHEMA_ALL_MAY:
268 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
269 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
272 case DSDB_SCHEMA_ALL_MUST:
273 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
274 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
277 case DSDB_SCHEMA_SYS_MAY:
278 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
281 case DSDB_SCHEMA_SYS_MUST:
282 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
285 case DSDB_SCHEMA_MAY:
286 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
289 case DSDB_SCHEMA_MUST:
290 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
293 case DSDB_SCHEMA_ALL:
294 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
295 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
296 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
297 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
303 static const char **attribute_list_from_class(TALLOC_CTX *mem_ctx,
304 const struct dsdb_schema *schema,
305 const struct dsdb_class *sclass,
306 enum dsdb_attr_list_query query)
308 const char **this_class_list;
309 const char **system_recursive_list;
310 const char **recursive_list;
311 const char **attr_list;
313 this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
315 recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
316 sclass->systemAuxiliaryClass,
319 system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
320 sclass->auxiliaryClass,
323 attr_list = this_class_list;
324 attr_list = merge_attr_list(mem_ctx, attr_list, recursive_list);
325 attr_list = merge_attr_list(mem_ctx, attr_list, system_recursive_list);
329 /* Return a full attribute list for a given class list
331 Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
333 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
334 const struct dsdb_schema *schema,
335 const char **class_list,
336 enum dsdb_attr_list_query query)
339 const char **attr_list = NULL;
341 for (i=0; class_list && class_list[i]; i++) {
342 const char **sclass_list
343 = attribute_list_from_class(mem_ctx, schema,
344 dsdb_class_by_lDAPDisplayName(schema, class_list[i]),
347 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
352 /* Return a full attribute list for a given class list (as a ldb_message_element)
354 Using the ldb_message_element ensures we do length-limited
355 comparisons, rather than casting the possibly-unterminated string
357 Via attribute_list_from_class() this calls
358 dsdb_full_attribute_list_internal() when recursing on auxiliary classes
360 static const char **dsdb_full_attribute_list_internal_el(TALLOC_CTX *mem_ctx,
361 const struct dsdb_schema *schema,
362 const struct ldb_message_element *el,
363 enum dsdb_attr_list_query query)
366 const char **attr_list = NULL;
368 for (i=0; i < el->num_values; i++) {
369 const char **sclass_list
370 = attribute_list_from_class(mem_ctx, schema,
371 dsdb_class_by_lDAPDisplayName_ldb_val(schema, &el->values[i]),
374 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
379 static int qsort_string(const char **s1, const char **s2)
381 return strcasecmp(*s1, *s2);
384 /* Helper function to remove duplicates from the attribute list to be returned */
385 static const char **dedup_attr_list(const char **attr_list)
387 size_t new_len = str_list_length(attr_list);
388 /* Remove duplicates */
391 TYPESAFE_QSORT(attr_list, new_len, qsort_string);
393 for (i=1; i < new_len; i++) {
394 const char **val1 = &attr_list[i-1];
395 const char **val2 = &attr_list[i];
396 if (ldb_attr_cmp(*val1, *val2) == 0) {
397 memmove(val1, val2, (new_len - i) * sizeof( *attr_list));
398 attr_list[new_len-1] = NULL;
407 /* Return a full attribute list for a given class list (as a ldb_message_element)
409 Using the ldb_message_element ensures we do length-limited
410 comparisons, rather than casting the possibly-unterminated string
412 The result contains only unique values
414 const char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,
415 const struct dsdb_schema *schema,
416 const struct ldb_message_element *class_list,
417 enum dsdb_attr_list_query query)
419 const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
420 return dedup_attr_list(attr_list);
423 /* Return the schemaIDGUID of a class */
425 const struct GUID *class_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
428 const struct dsdb_class *object_class = dsdb_class_by_lDAPDisplayName(schema, name);
432 return &object_class->schemaIDGUID;
435 const struct GUID *attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
438 const struct dsdb_attribute *attr = dsdb_attribute_by_lDAPDisplayName(schema, name);
442 return &attr->schemaIDGUID;
446 * Sort a "objectClass" attribute (LDB message element "objectclass_element")
447 * into correct order and validate that all object classes specified actually
448 * exist in the schema.
449 * The output is written in an existing LDB message element
450 * "out_objectclass_element" where the values will be allocated on "mem_ctx".
452 int dsdb_sort_objectClass_attr(struct ldb_context *ldb,
453 const struct dsdb_schema *schema,
454 const struct ldb_message_element *objectclass_element,
456 struct ldb_message_element *out_objectclass_element)
458 unsigned int i, lowest;
460 struct class_list *prev, *next;
461 const struct dsdb_class *objectclass;
462 } *unsorted = NULL, *sorted = NULL, *current = NULL,
463 *poss_parent = NULL, *new_parent = NULL,
464 *current_lowest = NULL, *current_lowest_struct = NULL;
465 struct ldb_message_element *el;
466 TALLOC_CTX *tmp_mem_ctx;
468 tmp_mem_ctx = talloc_new(mem_ctx);
469 if (tmp_mem_ctx == NULL) {
476 * We work on 4 different 'bins' (implemented here as linked lists):
478 * * sorted: the eventual list, in the order we wish to push
479 * into the database. This is the only ordered list.
481 * * parent_class: The current parent class 'bin' we are
482 * trying to find subclasses for
484 * * subclass: The subclasses we have found so far
486 * * unsorted: The remaining objectClasses
488 * The process is a matter of filtering objectClasses up from
489 * unsorted into sorted. Order is irrelevent in the later 3 'bins'.
491 * We start with 'top' (found and promoted to parent_class
492 * initially). Then we find (in unsorted) all the direct
493 * subclasses of 'top'. parent_classes is concatenated onto
494 * the end of 'sorted', and subclass becomes the list in
497 * We then repeat, until we find no more subclasses. Any left
498 * over classes are added to the end.
503 * Firstly, dump all the "objectClass" values into the unsorted bin,
504 * except for 'top', which is special
506 for (i=0; i < objectclass_element->num_values; i++) {
507 current = talloc(tmp_mem_ctx, struct class_list);
509 talloc_free(tmp_mem_ctx);
512 current->objectclass = dsdb_class_by_lDAPDisplayName_ldb_val(schema, &objectclass_element->values[i]);
513 if (!current->objectclass) {
514 ldb_asprintf_errstring(ldb, "objectclass %.*s is not a valid objectClass in schema",
515 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
516 /* This looks weird, but windows apparently returns this for invalid objectClass values */
517 talloc_free(tmp_mem_ctx);
518 return LDB_ERR_NO_SUCH_ATTRIBUTE;
519 } else if (current->objectclass->isDefunct) {
520 ldb_asprintf_errstring(ldb, "objectclass %.*s marked as isDefunct objectClass in schema - not valid for new objects",
521 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
522 /* This looks weird, but windows apparently returns this for invalid objectClass values */
523 talloc_free(tmp_mem_ctx);
524 return LDB_ERR_NO_SUCH_ATTRIBUTE;
527 /* Don't add top to list, we will do that later */
528 if (ldb_attr_cmp("top", current->objectclass->lDAPDisplayName) != 0) {
529 DLIST_ADD_END(unsorted, current);
534 /* Add top here, to prevent duplicates */
535 current = talloc(tmp_mem_ctx, struct class_list);
536 current->objectclass = dsdb_class_by_lDAPDisplayName(schema, "top");
537 DLIST_ADD_END(sorted, current);
539 /* For each object: find parent chain */
540 for (current = unsorted; current != NULL; current = current->next) {
541 for (poss_parent = unsorted; poss_parent; poss_parent = poss_parent->next) {
542 if (ldb_attr_cmp(poss_parent->objectclass->lDAPDisplayName, current->objectclass->subClassOf) == 0) {
546 /* If we didn't get to the end of the list, we need to add this parent */
547 if (poss_parent || (ldb_attr_cmp("top", current->objectclass->subClassOf) == 0)) {
551 new_parent = talloc(tmp_mem_ctx, struct class_list);
552 new_parent->objectclass = dsdb_class_by_lDAPDisplayName(schema, current->objectclass->subClassOf);
553 DLIST_ADD_END(unsorted, new_parent);
556 /* For each object: order by hierarchy */
557 while (unsorted != NULL) {
559 current_lowest = current_lowest_struct = NULL;
560 for (current = unsorted; current != NULL; current = current->next) {
561 if (current->objectclass->subClass_order <= lowest) {
563 * According to MS-ADTS 3.1.1.1.4 structural
564 * and 88 object classes are always listed after
565 * the other class types in a subclass hierarchy
567 if (current->objectclass->objectClassCategory > 1) {
568 current_lowest = current;
570 current_lowest_struct = current;
572 lowest = current->objectclass->subClass_order;
575 if (current_lowest == NULL) {
576 current_lowest = current_lowest_struct;
579 if (current_lowest != NULL) {
580 DLIST_REMOVE(unsorted,current_lowest);
581 DLIST_ADD_END(sorted,current_lowest);
585 /* Now rebuild the sorted "objectClass" message element */
586 el = out_objectclass_element;
588 el->flags = objectclass_element->flags;
589 el->name = talloc_strdup(mem_ctx, objectclass_element->name);
590 if (el->name == NULL) {
591 talloc_free(tmp_mem_ctx);
596 for (current = sorted; current != NULL; current = current->next) {
597 el->values = talloc_realloc(mem_ctx, el->values,
598 struct ldb_val, el->num_values + 1);
599 if (el->values == NULL) {
600 talloc_free(tmp_mem_ctx);
603 el->values[el->num_values] = data_blob_string_const(current->objectclass->lDAPDisplayName);
608 talloc_free(tmp_mem_ctx);