s4-dsdb: Explain better what records are written during schema set
[Samba.git] / source4 / dsdb / schema / schema_query.c
blobd16711ad19b019299c9014b4a34c0b67617840f5
1 /*
2 Unix SMB/CIFS mplementation.
3 DSDB schema header
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/>.
23 #include "includes.h"
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"
30 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
31 const struct dsdb_schema *schema,
32 const char **class_list,
33 enum dsdb_attr_list_query query);
35 static int uint32_cmp(uint32_t c1, uint32_t c2)
37 if (c1 == c2) return 0;
38 return c1 > c2 ? 1 : -1;
41 static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)
43 int ret = strncasecmp((const char *)target->data, str, target->length);
44 if (ret == 0) {
45 size_t len = strlen(str);
46 if (target->length > len) {
47 if (target->data[len] == 0) {
48 return 0;
50 return 1;
52 return (target->length - len);
54 return ret;
57 const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
58 uint32_t id)
60 struct dsdb_attribute *c;
63 * 0xFFFFFFFF is used as value when no mapping table is available,
64 * so don't try to match with it
66 if (id == 0xFFFFFFFF) return NULL;
68 /* check for msDS-IntId type attribute */
69 if (dsdb_pfm_get_attid_type(id) == DSDB_ATTID_TYPE_INTID) {
70 BINARY_ARRAY_SEARCH_P(schema->attributes_by_msDS_IntId,
71 schema->num_int_id_attr, msDS_IntId, id, uint32_cmp, c);
72 return c;
75 BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,
76 schema->num_attributes, attributeID_id, id, uint32_cmp, c);
77 return c;
80 const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
81 const char *oid)
83 struct dsdb_attribute *c;
85 if (!oid) return NULL;
87 BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_oid,
88 schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
89 return c;
92 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
93 const char *name)
95 struct dsdb_attribute *c;
97 if (!name) return NULL;
99 BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
100 schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
101 return c;
104 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
105 const struct ldb_val *name)
107 struct dsdb_attribute *a;
109 if (!name) return NULL;
111 BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
112 schema->num_attributes, lDAPDisplayName, name, strcasecmp_with_ldb_val, a);
113 return a;
116 const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
117 int linkID)
119 struct dsdb_attribute *c;
121 BINARY_ARRAY_SEARCH_P(schema->attributes_by_linkID,
122 schema->num_attributes, linkID, linkID, uint32_cmp, c);
123 return c;
126 const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
127 uint32_t id)
129 struct dsdb_class *c;
132 * 0xFFFFFFFF is used as value when no mapping table is available,
133 * so don't try to match with it
135 if (id == 0xFFFFFFFF) return NULL;
137 BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_id,
138 schema->num_classes, governsID_id, id, uint32_cmp, c);
139 return c;
142 const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
143 const char *oid)
145 struct dsdb_class *c;
146 if (!oid) return NULL;
147 BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_oid,
148 schema->num_classes, governsID_oid, oid, strcasecmp, c);
149 return c;
152 const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
153 const char *name)
155 struct dsdb_class *c;
156 if (!name) return NULL;
157 BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,
158 schema->num_classes, lDAPDisplayName, name, strcasecmp, c);
159 return c;
162 const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
163 const struct ldb_val *name)
165 struct dsdb_class *c;
166 if (!name) return NULL;
167 BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,
168 schema->num_classes, lDAPDisplayName, name, strcasecmp_with_ldb_val, c);
169 return c;
172 const struct dsdb_class *dsdb_class_by_cn(const struct dsdb_schema *schema,
173 const char *cn)
175 struct dsdb_class *c;
176 if (!cn) return NULL;
177 BINARY_ARRAY_SEARCH_P(schema->classes_by_cn,
178 schema->num_classes, cn, cn, strcasecmp, c);
179 return c;
182 const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
183 const struct ldb_val *cn)
185 struct dsdb_class *c;
186 if (!cn) return NULL;
187 BINARY_ARRAY_SEARCH_P(schema->classes_by_cn,
188 schema->num_classes, cn, cn, strcasecmp_with_ldb_val, c);
189 return c;
192 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
193 uint32_t id)
195 const struct dsdb_attribute *a;
196 const struct dsdb_class *c;
198 a = dsdb_attribute_by_attributeID_id(schema, id);
199 if (a) {
200 return a->lDAPDisplayName;
203 c = dsdb_class_by_governsID_id(schema, id);
204 if (c) {
205 return c->lDAPDisplayName;
208 return NULL;
211 /**
212 Return a list of linked attributes, in lDAPDisplayName format.
214 This may be used to determine if a modification would require
215 backlinks to be updated, for example
218 WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)
220 const char **attr_list = NULL;
221 struct dsdb_attribute *cur;
222 unsigned int i = 0;
223 for (cur = schema->attributes; cur; cur = cur->next) {
224 if (cur->linkID == 0) continue;
226 attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);
227 if (!attr_list) {
228 return WERR_NOMEM;
230 attr_list[i] = cur->lDAPDisplayName;
231 i++;
233 attr_list[i] = NULL;
234 *attr_list_ret = attr_list;
235 return WERR_OK;
238 const char **merge_attr_list(TALLOC_CTX *mem_ctx,
239 const char **attrs, const char * const*new_attrs)
241 const char **ret_attrs;
242 unsigned int i;
243 size_t new_len, orig_len = str_list_length(attrs);
244 if (!new_attrs) {
245 return attrs;
248 ret_attrs = talloc_realloc(mem_ctx,
249 attrs, const char *, orig_len + str_list_length(new_attrs) + 1);
250 if (ret_attrs) {
251 for (i=0; i < str_list_length(new_attrs); i++) {
252 ret_attrs[orig_len + i] = new_attrs[i];
254 new_len = orig_len + str_list_length(new_attrs);
256 ret_attrs[new_len] = NULL;
259 return ret_attrs;
263 Return a merged list of the attributes of exactly one class (not
264 considering subclasses, auxillary classes etc)
267 const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
269 const char **attr_list = NULL;
270 switch (query) {
271 case DSDB_SCHEMA_ALL_MAY:
272 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
273 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
274 break;
276 case DSDB_SCHEMA_ALL_MUST:
277 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
278 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
279 break;
281 case DSDB_SCHEMA_SYS_MAY:
282 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
283 break;
285 case DSDB_SCHEMA_SYS_MUST:
286 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
287 break;
289 case DSDB_SCHEMA_MAY:
290 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
291 break;
293 case DSDB_SCHEMA_MUST:
294 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
295 break;
297 case DSDB_SCHEMA_ALL:
298 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
299 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
300 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
301 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
302 break;
304 return attr_list;
307 static const char **attribute_list_from_class(TALLOC_CTX *mem_ctx,
308 const struct dsdb_schema *schema,
309 const struct dsdb_class *sclass,
310 enum dsdb_attr_list_query query)
312 const char **this_class_list;
313 const char **system_recursive_list;
314 const char **recursive_list;
315 const char **attr_list;
317 this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
319 recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
320 sclass->systemAuxiliaryClass,
321 query);
323 system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
324 sclass->auxiliaryClass,
325 query);
327 attr_list = this_class_list;
328 attr_list = merge_attr_list(mem_ctx, attr_list, recursive_list);
329 attr_list = merge_attr_list(mem_ctx, attr_list, system_recursive_list);
330 return attr_list;
333 /* Return a full attribute list for a given class list
335 Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
337 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
338 const struct dsdb_schema *schema,
339 const char **class_list,
340 enum dsdb_attr_list_query query)
342 unsigned int i;
343 const char **attr_list = NULL;
345 for (i=0; class_list && class_list[i]; i++) {
346 const char **sclass_list
347 = attribute_list_from_class(mem_ctx, schema,
348 dsdb_class_by_lDAPDisplayName(schema, class_list[i]),
349 query);
351 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
353 return attr_list;
356 /* Return a full attribute list for a given class list (as a ldb_message_element)
358 Using the ldb_message_element ensures we do length-limited
359 comparisons, rather than casting the possibly-unterminated string
361 Via attribute_list_from_class() this calls
362 dsdb_full_attribute_list_internal() when recursing on auxiliary classes
364 static const char **dsdb_full_attribute_list_internal_el(TALLOC_CTX *mem_ctx,
365 const struct dsdb_schema *schema,
366 const struct ldb_message_element *el,
367 enum dsdb_attr_list_query query)
369 unsigned int i;
370 const char **attr_list = NULL;
372 for (i=0; i < el->num_values; i++) {
373 const char **sclass_list
374 = attribute_list_from_class(mem_ctx, schema,
375 dsdb_class_by_lDAPDisplayName_ldb_val(schema, &el->values[i]),
376 query);
378 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
380 return attr_list;
383 static int qsort_string(const char **s1, const char **s2)
385 return strcasecmp(*s1, *s2);
388 /* Helper function to remove duplicates from the attribute list to be returned */
389 static const char **dedup_attr_list(const char **attr_list)
391 size_t new_len = str_list_length(attr_list);
392 /* Remove duplicates */
393 if (new_len > 1) {
394 size_t i;
395 TYPESAFE_QSORT(attr_list, new_len, qsort_string);
397 for (i=1; i < new_len; i++) {
398 const char **val1 = &attr_list[i-1];
399 const char **val2 = &attr_list[i];
400 if (ldb_attr_cmp(*val1, *val2) == 0) {
401 memmove(val1, val2, (new_len - i) * sizeof( *attr_list));
402 attr_list[new_len-1] = NULL;
403 new_len--;
404 i--;
408 return attr_list;
411 /* Return a full attribute list for a given class list (as a ldb_message_element)
413 Using the ldb_message_element ensures we do length-limited
414 comparisons, rather than casting the possibly-unterminated string
416 The result contains only unique values
418 const char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,
419 const struct dsdb_schema *schema,
420 const struct ldb_message_element *class_list,
421 enum dsdb_attr_list_query query)
423 const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
424 return dedup_attr_list(attr_list);
427 /* Return the schemaIDGUID of a class */
429 const struct GUID *class_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
430 const char *name)
432 const struct dsdb_class *object_class = dsdb_class_by_lDAPDisplayName(schema, name);
433 if (!object_class)
434 return NULL;
436 return &object_class->schemaIDGUID;
439 const struct GUID *attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
440 const char *name)
442 const struct dsdb_attribute *attr = dsdb_attribute_by_lDAPDisplayName(schema, name);
443 if (!attr)
444 return NULL;
446 return &attr->schemaIDGUID;
450 * Sort a "objectClass" attribute (LDB message element "objectclass_element")
451 * into correct order and validate that all object classes specified actually
452 * exist in the schema.
453 * The output is written in an existing LDB message element
454 * "out_objectclass_element" where the values will be allocated on
455 * "out_mem_ctx".
457 int dsdb_sort_objectClass_attr(struct ldb_context *ldb,
458 const struct dsdb_schema *schema,
459 TALLOC_CTX *mem_ctx,
460 const struct ldb_message_element *objectclass_element,
461 TALLOC_CTX *out_mem_ctx,
462 struct ldb_message_element *out_objectclass_element)
464 unsigned int i, lowest;
465 struct class_list {
466 struct class_list *prev, *next;
467 const struct dsdb_class *objectclass;
468 } *unsorted = NULL, *sorted = NULL, *current = NULL,
469 *poss_parent = NULL, *new_parent = NULL,
470 *current_lowest = NULL, *current_lowest_struct = NULL;
471 struct ldb_message_element *el;
474 * DESIGN:
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
495 * parent_class.
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(mem_ctx, struct class_list);
508 if (!current) {
509 return ldb_oom(ldb);
511 current->objectclass = dsdb_class_by_lDAPDisplayName_ldb_val(schema, &objectclass_element->values[i]);
512 if (!current->objectclass) {
513 ldb_asprintf_errstring(ldb, "objectclass %.*s is not a valid objectClass in schema",
514 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
515 /* This looks weird, but windows apparently returns this for invalid objectClass values */
516 return LDB_ERR_NO_SUCH_ATTRIBUTE;
517 } else if (current->objectclass->isDefunct) {
518 ldb_asprintf_errstring(ldb, "objectclass %.*s marked as isDefunct objectClass in schema - not valid for new objects",
519 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
520 /* This looks weird, but windows apparently returns this for invalid objectClass values */
521 return LDB_ERR_NO_SUCH_ATTRIBUTE;
524 /* Don't add top to list, we will do that later */
525 if (ldb_attr_cmp("top", current->objectclass->lDAPDisplayName) != 0) {
526 DLIST_ADD_END(unsorted, current, struct class_list *);
531 /* Add top here, to prevent duplicates */
532 current = talloc(mem_ctx, struct class_list);
533 current->objectclass = dsdb_class_by_lDAPDisplayName(schema, "top");
534 DLIST_ADD_END(sorted, current, struct class_list *);
536 /* For each object: find parent chain */
537 for (current = unsorted; current != NULL; current = current->next) {
538 for (poss_parent = unsorted; poss_parent; poss_parent = poss_parent->next) {
539 if (ldb_attr_cmp(poss_parent->objectclass->lDAPDisplayName, current->objectclass->subClassOf) == 0) {
540 break;
543 /* If we didn't get to the end of the list, we need to add this parent */
544 if (poss_parent || (ldb_attr_cmp("top", current->objectclass->subClassOf) == 0)) {
545 continue;
548 new_parent = talloc(mem_ctx, struct class_list);
549 new_parent->objectclass = dsdb_class_by_lDAPDisplayName(schema, current->objectclass->subClassOf);
550 DLIST_ADD_END(unsorted, new_parent, struct class_list *);
553 /* For each object: order by hierarchy */
554 while (unsorted != NULL) {
555 lowest = UINT_MAX;
556 current_lowest = current_lowest_struct = NULL;
557 for (current = unsorted; current != NULL; current = current->next) {
558 if (current->objectclass->subClass_order <= lowest) {
560 * According to MS-ADTS 3.1.1.1.4 structural
561 * and 88 object classes are always listed after
562 * the other class types in a subclass hierarchy
564 if (current->objectclass->objectClassCategory > 1) {
565 current_lowest = current;
566 } else {
567 current_lowest_struct = current;
569 lowest = current->objectclass->subClass_order;
572 if (current_lowest == NULL) {
573 current_lowest = current_lowest_struct;
576 if (current_lowest != NULL) {
577 DLIST_REMOVE(unsorted,current_lowest);
578 DLIST_ADD_END(sorted,current_lowest, struct class_list *);
582 /* Now rebuild the sorted "objectClass" message element */
583 el = out_objectclass_element;
585 el->flags = objectclass_element->flags;
586 el->name = talloc_strdup(out_mem_ctx, objectclass_element->name);
587 if (el->name == NULL) {
588 return ldb_oom(ldb);
590 el->num_values = 0;
591 el->values = NULL;
592 for (current = sorted; current != NULL; current = current->next) {
593 el->values = talloc_realloc(out_mem_ctx, el->values,
594 struct ldb_val, el->num_values + 1);
595 if (el->values == NULL) {
596 return ldb_oom(ldb);
598 el->values[el->num_values].data = (uint8_t *)talloc_strdup(out_mem_ctx,
599 current->objectclass->lDAPDisplayName);
600 if (el->values[el->num_values].data == NULL) {
601 return ldb_oom(ldb);
603 el->values[el->num_values].length = strlen(current->objectclass->lDAPDisplayName);
605 ++(el->num_values);
608 return LDB_SUCCESS;