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 if (target
->length
< len
) {
62 const struct dsdb_attribute
*dsdb_attribute_by_attributeID_id(const struct dsdb_schema
*schema
,
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
);
80 BINARY_ARRAY_SEARCH_P(schema
->attributes_by_attributeID_id
,
81 schema
->num_attributes
, attributeID_id
, id
, uint32_cmp
, c
);
85 const struct dsdb_attribute
*dsdb_attribute_by_attributeID_oid(const struct dsdb_schema
*schema
,
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
);
97 const struct dsdb_attribute
*dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema
*schema
,
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
);
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
);
121 const struct dsdb_attribute
*dsdb_attribute_by_linkID(const struct dsdb_schema
*schema
,
124 struct dsdb_attribute
*c
;
126 BINARY_ARRAY_SEARCH_P(schema
->attributes_by_linkID
,
127 schema
->num_attributes
, linkID
, linkID
, uint32_cmp
, 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
);
141 const struct dsdb_class
*dsdb_class_by_governsID_id(const struct dsdb_schema
*schema
,
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
);
157 const struct dsdb_class
*dsdb_class_by_governsID_oid(const struct dsdb_schema
*schema
,
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
);
167 const struct dsdb_class
*dsdb_class_by_lDAPDisplayName(const struct dsdb_schema
*schema
,
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
);
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
);
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
);
197 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema
*schema
,
200 const struct dsdb_attribute
*a
;
201 const struct dsdb_class
*c
;
203 a
= dsdb_attribute_by_attributeID_id(schema
, id
);
205 return a
->lDAPDisplayName
;
208 c
= dsdb_class_by_governsID_id(schema
, id
);
210 return c
->lDAPDisplayName
;
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
;
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);
233 return WERR_NOT_ENOUGH_MEMORY
;
235 attr_list
[i
] = cur
->lDAPDisplayName
;
238 if (attr_list
!= NULL
&& attr_list
[i
] != NULL
) {
241 *attr_list_ret
= attr_list
;
245 const char **merge_attr_list(TALLOC_CTX
*mem_ctx
,
246 const char **attrs
, const char * const*new_attrs
)
248 const char **ret_attrs
;
250 size_t new_len
, new_attr_len
, orig_len
= str_list_length(attrs
);
251 if (new_attrs
== NULL
|| new_attrs
[0] == NULL
) {
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);
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
;
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
;
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
);
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
);
289 case DSDB_SCHEMA_SYS_MAY
:
290 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->systemMayContain
);
293 case DSDB_SCHEMA_SYS_MUST
:
294 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->systemMustContain
);
297 case DSDB_SCHEMA_MAY
:
298 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->mayContain
);
301 case DSDB_SCHEMA_MUST
:
302 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->mustContain
);
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
);
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
,
331 system_recursive_list
= dsdb_full_attribute_list_internal(mem_ctx
, schema
,
332 sclass
->auxiliaryClass
,
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
);
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
)
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
]),
359 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass_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
)
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
]),
386 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass_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 */
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
;
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
,
440 const struct dsdb_class
*object_class
= dsdb_class_by_lDAPDisplayName(schema
, name
);
444 return &object_class
->schemaIDGUID
;
447 const struct GUID
*attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema
*schema
,
450 const struct dsdb_attribute
*attr
= dsdb_attribute_by_lDAPDisplayName(schema
, name
);
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
,
468 struct ldb_message_element
*out_objectclass_element
)
470 unsigned int i
, lowest
;
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
) {
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
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
);
521 talloc_free(tmp_mem_ctx
);
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) {
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)) {
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
) {
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
;
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
);
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
);
615 el
->values
[el
->num_values
] = data_blob_string_const(current
->objectclass
->lDAPDisplayName
);
620 talloc_free(tmp_mem_ctx
);