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
);