ctdb-build: Add missing ctdb-tcp dependency
[Samba.git] / source4 / dsdb / schema / schema_query.c
blobaa906d03d4bbbbd4a2b130d7f5c7ceeb336b6ddf
1 /*
2 Unix SMB/CIFS Implementation.
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 #undef strcasecmp
31 #undef strncasecmp
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);
47 if (ret == 0) {
48 size_t len = strlen(str);
49 if (target->length > len) {
50 if (target->data[len] == 0) {
51 return 0;
53 return 1;
55 if (target->length < len) {
56 return -1;
59 return ret;
62 const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
63 uint32_t id)
65 struct dsdb_attribute *c;
68 * 0xFFFFFFFF is used as value when no mapping table is available,
69 * so don't try to match with it
71 if (id == 0xFFFFFFFF) return NULL;
73 /* check for msDS-IntId type attribute */
74 if (dsdb_pfm_get_attid_type(id) == DSDB_ATTID_TYPE_INTID) {
75 BINARY_ARRAY_SEARCH_P(schema->attributes_by_msDS_IntId,
76 schema->num_int_id_attr, msDS_IntId, id, uint32_cmp, c);
77 return c;
80 BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,
81 schema->num_attributes, attributeID_id, id, uint32_cmp, c);
82 return c;
85 const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
86 const char *oid)
88 struct dsdb_attribute *c;
90 if (!oid) return NULL;
92 BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_oid,
93 schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
94 return c;
97 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
98 const char *name)
100 struct dsdb_attribute *c;
102 if (!name) return NULL;
104 BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
105 schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
106 return c;
109 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
110 const struct ldb_val *name)
112 struct dsdb_attribute *a;
114 if (!name) return NULL;
116 BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
117 schema->num_attributes, lDAPDisplayName, name, strcasecmp_with_ldb_val, a);
118 return a;
121 const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
122 int linkID)
124 struct dsdb_attribute *c;
126 BINARY_ARRAY_SEARCH_P(schema->attributes_by_linkID,
127 schema->num_attributes, linkID, linkID, uint32_cmp, c);
128 return c;
131 const struct dsdb_attribute *dsdb_attribute_by_cn_ldb_val(const struct dsdb_schema *schema,
132 const struct ldb_val *cn)
134 struct dsdb_attribute *c;
136 BINARY_ARRAY_SEARCH_P(schema->attributes_by_cn,
137 schema->num_attributes, cn, cn, strcasecmp_with_ldb_val, c);
138 return c;
141 const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
142 uint32_t id)
144 struct dsdb_class *c;
147 * 0xFFFFFFFF is used as value when no mapping table is available,
148 * so don't try to match with it
150 if (id == 0xFFFFFFFF) return NULL;
152 BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_id,
153 schema->num_classes, governsID_id, id, uint32_cmp, c);
154 return c;
157 const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
158 const char *oid)
160 struct dsdb_class *c;
161 if (!oid) return NULL;
162 BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_oid,
163 schema->num_classes, governsID_oid, oid, strcasecmp, c);
164 return c;
167 const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
168 const char *name)
170 struct dsdb_class *c;
171 if (!name) return NULL;
172 BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,
173 schema->num_classes, lDAPDisplayName, name, strcasecmp, c);
174 return c;
177 const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
178 const struct ldb_val *name)
180 struct dsdb_class *c;
181 if (!name) return NULL;
182 BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,
183 schema->num_classes, lDAPDisplayName, name, strcasecmp_with_ldb_val, c);
184 return c;
187 const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
188 const struct ldb_val *cn)
190 struct dsdb_class *c;
191 if (!cn) return NULL;
192 BINARY_ARRAY_SEARCH_P(schema->classes_by_cn,
193 schema->num_classes, cn, cn, strcasecmp_with_ldb_val, c);
194 return c;
197 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
198 uint32_t id)
200 const struct dsdb_attribute *a;
201 const struct dsdb_class *c;
203 a = dsdb_attribute_by_attributeID_id(schema, id);
204 if (a) {
205 return a->lDAPDisplayName;
208 c = dsdb_class_by_governsID_id(schema, id);
209 if (c) {
210 return c->lDAPDisplayName;
213 return NULL;
217 Return a list of linked attributes, in lDAPDisplayName format.
219 This may be used to determine if a modification would require
220 backlinks to be updated, for example
223 WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)
225 const char **attr_list = NULL;
226 struct dsdb_attribute *cur;
227 unsigned int i = 0;
228 for (cur = schema->attributes; cur; cur = cur->next) {
229 if (cur->linkID == 0) continue;
231 attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);
232 if (!attr_list) {
233 return WERR_NOT_ENOUGH_MEMORY;
235 attr_list[i] = cur->lDAPDisplayName;
236 i++;
238 if (attr_list != NULL && attr_list[i] != NULL) {
239 attr_list[i] = NULL;
241 *attr_list_ret = attr_list;
242 return WERR_OK;
245 const char **merge_attr_list(TALLOC_CTX *mem_ctx,
246 const char **attrs, const char * const*new_attrs)
248 const char **ret_attrs;
249 unsigned int i;
250 size_t new_len, new_attr_len, orig_len = str_list_length(attrs);
251 if (new_attrs == NULL || new_attrs[0] == NULL) {
252 return attrs;
254 new_attr_len = str_list_length(new_attrs);
256 ret_attrs = talloc_realloc(mem_ctx,
257 attrs, const char *, orig_len + new_attr_len + 1);
258 if (ret_attrs) {
259 for (i = 0; i < new_attr_len; i++) {
260 ret_attrs[orig_len + i] = new_attrs[i];
262 new_len = orig_len + new_attr_len;
264 ret_attrs[new_len] = NULL;
267 return ret_attrs;
271 Return a merged list of the attributes of exactly one class (not
272 considering subclasses, auxiliary classes etc)
275 const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
277 const char **attr_list = NULL;
278 switch (query) {
279 case DSDB_SCHEMA_ALL_MAY:
280 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
281 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
282 break;
284 case DSDB_SCHEMA_ALL_MUST:
285 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
286 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
287 break;
289 case DSDB_SCHEMA_SYS_MAY:
290 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
291 break;
293 case DSDB_SCHEMA_SYS_MUST:
294 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
295 break;
297 case DSDB_SCHEMA_MAY:
298 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
299 break;
301 case DSDB_SCHEMA_MUST:
302 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
303 break;
305 case DSDB_SCHEMA_ALL:
306 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
307 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
308 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
309 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
310 break;
312 return attr_list;
315 static const char **attribute_list_from_class(TALLOC_CTX *mem_ctx,
316 const struct dsdb_schema *schema,
317 const struct dsdb_class *sclass,
318 enum dsdb_attr_list_query query)
320 const char **this_class_list;
321 const char **system_recursive_list;
322 const char **recursive_list;
323 const char **attr_list;
325 this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
327 recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
328 sclass->systemAuxiliaryClass,
329 query);
331 system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
332 sclass->auxiliaryClass,
333 query);
335 attr_list = this_class_list;
336 attr_list = merge_attr_list(mem_ctx, attr_list, recursive_list);
337 attr_list = merge_attr_list(mem_ctx, attr_list, system_recursive_list);
338 return attr_list;
341 /* Return a full attribute list for a given class list
343 Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
345 static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
346 const struct dsdb_schema *schema,
347 const char **class_list,
348 enum dsdb_attr_list_query query)
350 unsigned int i;
351 const char **attr_list = NULL;
353 for (i=0; class_list && class_list[i]; i++) {
354 const char **sclass_list
355 = attribute_list_from_class(mem_ctx, schema,
356 dsdb_class_by_lDAPDisplayName(schema, class_list[i]),
357 query);
359 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
361 return attr_list;
364 /* Return a full attribute list for a given class list (as a ldb_message_element)
366 Using the ldb_message_element ensures we do length-limited
367 comparisons, rather than casting the possibly-unterminated string
369 Via attribute_list_from_class() this calls
370 dsdb_full_attribute_list_internal() when recursing on auxiliary classes
372 static const char **dsdb_full_attribute_list_internal_el(TALLOC_CTX *mem_ctx,
373 const struct dsdb_schema *schema,
374 const struct ldb_message_element *el,
375 enum dsdb_attr_list_query query)
377 unsigned int i;
378 const char **attr_list = NULL;
380 for (i=0; i < el->num_values; i++) {
381 const char **sclass_list
382 = attribute_list_from_class(mem_ctx, schema,
383 dsdb_class_by_lDAPDisplayName_ldb_val(schema, &el->values[i]),
384 query);
386 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
388 return attr_list;
391 static int qsort_string(const char **s1, const char **s2)
393 return strcasecmp(*s1, *s2);
396 /* Helper function to remove duplicates from the attribute list to be returned */
397 static const char **dedup_attr_list(const char **attr_list)
399 size_t new_len = str_list_length(attr_list);
400 /* Remove duplicates */
401 if (new_len > 1) {
402 size_t i;
403 TYPESAFE_QSORT(attr_list, new_len, qsort_string);
405 for (i=1; new_len > 0 && i < new_len; i++) {
406 const char **val1 = &attr_list[i-1];
407 const char **val2 = &attr_list[i];
408 if (ldb_attr_cmp(*val1, *val2) == 0) {
409 memmove(val1, val2, (new_len - i) * sizeof( *attr_list));
410 attr_list[new_len-1] = NULL;
411 new_len--;
412 i--;
416 return attr_list;
419 /* Return a full attribute list for a given class list (as a ldb_message_element)
421 Using the ldb_message_element ensures we do length-limited
422 comparisons, rather than casting the possibly-unterminated string
424 The result contains only unique values
426 const char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,
427 const struct dsdb_schema *schema,
428 const struct ldb_message_element *class_list,
429 enum dsdb_attr_list_query query)
431 const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
432 return dedup_attr_list(attr_list);
435 /* Return the schemaIDGUID of a class */
437 const struct GUID *class_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
438 const char *name)
440 const struct dsdb_class *object_class = dsdb_class_by_lDAPDisplayName(schema, name);
441 if (!object_class)
442 return NULL;
444 return &object_class->schemaIDGUID;
447 const struct GUID *attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
448 const char *name)
450 const struct dsdb_attribute *attr = dsdb_attribute_by_lDAPDisplayName(schema, name);
451 if (!attr)
452 return NULL;
454 return &attr->schemaIDGUID;
458 * Sort a "objectClass" attribute (LDB message element "objectclass_element")
459 * into correct order and validate that all object classes specified actually
460 * exist in the schema.
461 * The output is written in an existing LDB message element
462 * "out_objectclass_element" where the values will be allocated on "mem_ctx".
464 int dsdb_sort_objectClass_attr(struct ldb_context *ldb,
465 const struct dsdb_schema *schema,
466 const struct ldb_message_element *objectclass_element,
467 TALLOC_CTX *mem_ctx,
468 struct ldb_message_element *out_objectclass_element)
470 unsigned int i, lowest;
471 struct class_list {
472 struct class_list *prev, *next;
473 const struct dsdb_class *objectclass;
474 } *unsorted = NULL, *sorted = NULL, *current = NULL,
475 *poss_parent = NULL, *new_parent = NULL,
476 *current_lowest = NULL, *current_lowest_struct = NULL;
477 struct ldb_message_element *el;
478 TALLOC_CTX *tmp_mem_ctx;
480 tmp_mem_ctx = talloc_new(mem_ctx);
481 if (tmp_mem_ctx == NULL) {
482 return ldb_oom(ldb);
486 * DESIGN:
488 * We work on 4 different 'bins' (implemented here as linked lists):
490 * * sorted: the eventual list, in the order we wish to push
491 * into the database. This is the only ordered list.
493 * * parent_class: The current parent class 'bin' we are
494 * trying to find subclasses for
496 * * subclass: The subclasses we have found so far
498 * * unsorted: The remaining objectClasses
500 * The process is a matter of filtering objectClasses up from
501 * unsorted into sorted. Order is irrelevant in the later 3 'bins'.
503 * We start with 'top' (found and promoted to parent_class
504 * initially). Then we find (in unsorted) all the direct
505 * subclasses of 'top'. parent_classes is concatenated onto
506 * the end of 'sorted', and subclass becomes the list in
507 * parent_class.
509 * We then repeat, until we find no more subclasses. Any left
510 * over classes are added to the end.
515 * Firstly, dump all the "objectClass" values into the unsorted bin,
516 * except for 'top', which is special
518 for (i=0; i < objectclass_element->num_values; i++) {
519 current = talloc(tmp_mem_ctx, struct class_list);
520 if (!current) {
521 talloc_free(tmp_mem_ctx);
522 return ldb_oom(ldb);
524 current->objectclass = dsdb_class_by_lDAPDisplayName_ldb_val(schema, &objectclass_element->values[i]);
525 if (!current->objectclass) {
526 ldb_asprintf_errstring(ldb, "objectclass %.*s is not a valid objectClass in schema",
527 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
528 /* This looks weird, but windows apparently returns this for invalid objectClass values */
529 talloc_free(tmp_mem_ctx);
530 return LDB_ERR_NO_SUCH_ATTRIBUTE;
531 } else if (current->objectclass->isDefunct) {
532 ldb_asprintf_errstring(ldb, "objectclass %.*s marked as isDefunct objectClass in schema - not valid for new objects",
533 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
534 /* This looks weird, but windows apparently returns this for invalid objectClass values */
535 talloc_free(tmp_mem_ctx);
536 return LDB_ERR_NO_SUCH_ATTRIBUTE;
539 /* Don't add top to list, we will do that later */
540 if (ldb_attr_cmp("top", current->objectclass->lDAPDisplayName) != 0) {
541 DLIST_ADD_END(unsorted, current);
546 /* Add top here, to prevent duplicates */
547 current = talloc(tmp_mem_ctx, struct class_list);
548 current->objectclass = dsdb_class_by_lDAPDisplayName(schema, "top");
549 DLIST_ADD_END(sorted, current);
551 /* For each object: find parent chain */
552 for (current = unsorted; current != NULL; current = current->next) {
553 for (poss_parent = unsorted; poss_parent; poss_parent = poss_parent->next) {
554 if (ldb_attr_cmp(poss_parent->objectclass->lDAPDisplayName, current->objectclass->subClassOf) == 0) {
555 break;
558 /* If we didn't get to the end of the list, we need to add this parent */
559 if (poss_parent || (ldb_attr_cmp("top", current->objectclass->subClassOf) == 0)) {
560 continue;
563 new_parent = talloc(tmp_mem_ctx, struct class_list);
564 new_parent->objectclass = dsdb_class_by_lDAPDisplayName(schema, current->objectclass->subClassOf);
565 DLIST_ADD_END(unsorted, new_parent);
568 /* For each object: order by hierarchy */
569 while (unsorted != NULL) {
570 lowest = UINT_MAX;
571 current_lowest = current_lowest_struct = NULL;
572 for (current = unsorted; current != NULL; current = current->next) {
573 if (current->objectclass->subClass_order <= lowest) {
575 * According to MS-ADTS 3.1.1.1.4 structural
576 * and 88 object classes are always listed after
577 * the other class types in a subclass hierarchy
579 if (current->objectclass->objectClassCategory > 1) {
580 current_lowest = current;
581 } else {
582 current_lowest_struct = current;
584 lowest = current->objectclass->subClass_order;
587 if (current_lowest == NULL) {
588 current_lowest = current_lowest_struct;
591 if (current_lowest != NULL) {
592 DLIST_REMOVE(unsorted,current_lowest);
593 DLIST_ADD_END(sorted,current_lowest);
597 /* Now rebuild the sorted "objectClass" message element */
598 el = out_objectclass_element;
600 el->flags = objectclass_element->flags;
601 el->name = talloc_strdup(mem_ctx, objectclass_element->name);
602 if (el->name == NULL) {
603 talloc_free(tmp_mem_ctx);
604 return ldb_oom(ldb);
606 el->num_values = 0;
607 el->values = NULL;
608 for (current = sorted; current != NULL; current = current->next) {
609 el->values = talloc_realloc(mem_ctx, el->values,
610 struct ldb_val, el->num_values + 1);
611 if (el->values == NULL) {
612 talloc_free(tmp_mem_ctx);
613 return ldb_oom(ldb);
615 el->values[el->num_values] = data_blob_string_const(current->objectclass->lDAPDisplayName);
617 ++(el->num_values);
620 talloc_free(tmp_mem_ctx);
621 return LDB_SUCCESS;