2 Unix SMB/CIFS mplementation.
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"
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
);
45 size_t len
= strlen(str
);
46 if (target
->length
> len
) {
47 if (target
->data
[len
] == 0) {
52 return (target
->length
- len
);
57 const struct dsdb_attribute
*dsdb_attribute_by_attributeID_id(const struct dsdb_schema
*schema
,
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
);
75 BINARY_ARRAY_SEARCH_P(schema
->attributes_by_attributeID_id
,
76 schema
->num_attributes
, attributeID_id
, id
, uint32_cmp
, c
);
80 const struct dsdb_attribute
*dsdb_attribute_by_attributeID_oid(const struct dsdb_schema
*schema
,
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
);
92 const struct dsdb_attribute
*dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema
*schema
,
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
);
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
);
116 const struct dsdb_attribute
*dsdb_attribute_by_linkID(const struct dsdb_schema
*schema
,
119 struct dsdb_attribute
*c
;
121 BINARY_ARRAY_SEARCH_P(schema
->attributes_by_linkID
,
122 schema
->num_attributes
, linkID
, linkID
, uint32_cmp
, c
);
126 const struct dsdb_class
*dsdb_class_by_governsID_id(const struct dsdb_schema
*schema
,
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
);
142 const struct dsdb_class
*dsdb_class_by_governsID_oid(const struct dsdb_schema
*schema
,
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
);
152 const struct dsdb_class
*dsdb_class_by_lDAPDisplayName(const struct dsdb_schema
*schema
,
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
);
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
);
172 const struct dsdb_class
*dsdb_class_by_cn(const struct dsdb_schema
*schema
,
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
);
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
);
192 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema
*schema
,
195 const struct dsdb_attribute
*a
;
196 const struct dsdb_class
*c
;
198 a
= dsdb_attribute_by_attributeID_id(schema
, id
);
200 return a
->lDAPDisplayName
;
203 c
= dsdb_class_by_governsID_id(schema
, id
);
205 return c
->lDAPDisplayName
;
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
;
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);
230 attr_list
[i
] = cur
->lDAPDisplayName
;
234 *attr_list_ret
= attr_list
;
238 const char **merge_attr_list(TALLOC_CTX
*mem_ctx
,
239 const char **attrs
, const char * const*new_attrs
)
241 const char **ret_attrs
;
243 size_t new_len
, orig_len
= str_list_length(attrs
);
248 ret_attrs
= talloc_realloc(mem_ctx
,
249 attrs
, const char *, orig_len
+ str_list_length(new_attrs
) + 1);
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
;
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
;
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
);
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
);
281 case DSDB_SCHEMA_SYS_MAY
:
282 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->systemMayContain
);
285 case DSDB_SCHEMA_SYS_MUST
:
286 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->systemMustContain
);
289 case DSDB_SCHEMA_MAY
:
290 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->mayContain
);
293 case DSDB_SCHEMA_MUST
:
294 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass
->mustContain
);
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
);
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
,
323 system_recursive_list
= dsdb_full_attribute_list_internal(mem_ctx
, schema
,
324 sclass
->auxiliaryClass
,
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
);
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
)
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
]),
351 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass_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
)
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
]),
378 attr_list
= merge_attr_list(mem_ctx
, attr_list
, sclass_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 */
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
;
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
,
432 const struct dsdb_class
*object_class
= dsdb_class_by_lDAPDisplayName(schema
, name
);
436 return &object_class
->schemaIDGUID
;
439 const struct GUID
*attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema
*schema
,
442 const struct dsdb_attribute
*attr
= dsdb_attribute_by_lDAPDisplayName(schema
, name
);
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
457 int dsdb_sort_objectClass_attr(struct ldb_context
*ldb
,
458 const struct dsdb_schema
*schema
,
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
;
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
;
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(mem_ctx
, struct class_list
);
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) {
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)) {
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
) {
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
;
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
) {
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
) {
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
) {
603 el
->values
[el
->num_values
].length
= strlen(current
->objectclass
->lDAPDisplayName
);