libndr: Avoid assigning duplicate versions to symbols
[amitay/samba.git] / source4 / dsdb / schema / schema_query.c
1 /* 
2    Unix SMB/CIFS Implementation.
3    DSDB schema header
4    
5    Copyright (C) Stefan Metzmacher <metze@samba.org> 2006-2007
6    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2006-2008
7
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.
12    
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.
17    
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/>.
20    
21 */
22
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"
29
30 #undef strcasecmp
31 #undef strncasecmp
32
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);
37
38 static int uint32_cmp(uint32_t c1, uint32_t c2) 
39 {
40         if (c1 == c2) return 0;
41         return c1 > c2 ? 1 : -1;
42 }
43
44 static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)
45 {
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;
52                         }
53                         return 1;
54                 }
55                 return (target->length - len);
56         }
57         return ret;
58 }
59
60 const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
61                                                               uint32_t id)
62 {
63         struct dsdb_attribute *c;
64
65         /*
66          * 0xFFFFFFFF is used as value when no mapping table is available,
67          * so don't try to match with it
68          */
69         if (id == 0xFFFFFFFF) return NULL;
70
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);
75                 return c;
76         }
77
78         BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,
79                               schema->num_attributes, attributeID_id, id, uint32_cmp, c);
80         return c;
81 }
82
83 const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
84                                                                const char *oid)
85 {
86         struct dsdb_attribute *c;
87
88         if (!oid) return NULL;
89
90         BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_oid,
91                               schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
92         return c;
93 }
94
95 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
96                                                                const char *name)
97 {
98         struct dsdb_attribute *c;
99
100         if (!name) return NULL;
101
102         BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
103                               schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
104         return c;
105 }
106
107 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
108                                                                        const struct ldb_val *name)
109 {
110         struct dsdb_attribute *a;
111
112         if (!name) return NULL;
113
114         BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
115                               schema->num_attributes, lDAPDisplayName, name, strcasecmp_with_ldb_val, a);
116         return a;
117 }
118
119 const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
120                                                       int linkID)
121 {
122         struct dsdb_attribute *c;
123
124         BINARY_ARRAY_SEARCH_P(schema->attributes_by_linkID,
125                               schema->num_attributes, linkID, linkID, uint32_cmp, c);
126         return c;
127 }
128
129 const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
130                                                     uint32_t id)
131 {
132         struct dsdb_class *c;
133
134         /*
135          * 0xFFFFFFFF is used as value when no mapping table is available,
136          * so don't try to match with it
137          */
138         if (id == 0xFFFFFFFF) return NULL;
139
140         BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_id,
141                               schema->num_classes, governsID_id, id, uint32_cmp, c);
142         return c;
143 }
144
145 const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
146                                                      const char *oid)
147 {
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);
152         return c;
153 }
154
155 const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
156                                                        const char *name)
157 {
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);
162         return c;
163 }
164
165 const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
166                                                                const struct ldb_val *name)
167 {
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);
172         return c;
173 }
174
175 const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
176                                                   const struct ldb_val *cn)
177 {
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);
182         return c;
183 }
184
185 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
186                                        uint32_t id)
187 {
188         const struct dsdb_attribute *a;
189         const struct dsdb_class *c;
190
191         a = dsdb_attribute_by_attributeID_id(schema, id);
192         if (a) {
193                 return a->lDAPDisplayName;
194         }
195
196         c = dsdb_class_by_governsID_id(schema, id);
197         if (c) {
198                 return c->lDAPDisplayName;
199         }
200
201         return NULL;
202 }
203
204 /** 
205     Return a list of linked attributes, in lDAPDisplayName format.
206
207     This may be used to determine if a modification would require
208     backlinks to be updated, for example
209 */
210
211 WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)
212 {
213         const char **attr_list = NULL;
214         struct dsdb_attribute *cur;
215         unsigned int i = 0;
216         for (cur = schema->attributes; cur; cur = cur->next) {
217                 if (cur->linkID == 0) continue;
218                 
219                 attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);
220                 if (!attr_list) {
221                         return WERR_NOT_ENOUGH_MEMORY;
222                 }
223                 attr_list[i] = cur->lDAPDisplayName;
224                 i++;
225         }
226         if (attr_list != NULL && attr_list[i] != NULL) {
227                 attr_list[i] = NULL;
228         }
229         *attr_list_ret = attr_list;
230         return WERR_OK;
231 }
232
233 const char **merge_attr_list(TALLOC_CTX *mem_ctx, 
234                        const char **attrs, const char * const*new_attrs) 
235 {
236         const char **ret_attrs;
237         unsigned int i;
238         size_t new_len, new_attr_len, orig_len = str_list_length(attrs);
239         if (new_attrs == NULL || new_attrs[0] == NULL) {
240                 return attrs;
241         }
242         new_attr_len = str_list_length(new_attrs);
243
244         ret_attrs = talloc_realloc(mem_ctx,
245                                    attrs, const char *, orig_len + new_attr_len + 1);
246         if (ret_attrs) {
247                 for (i = 0; i < new_attr_len; i++) {
248                         ret_attrs[orig_len + i] = new_attrs[i];
249                 }
250                 new_len = orig_len + new_attr_len;
251
252                 ret_attrs[new_len] = NULL;
253         }
254
255         return ret_attrs;
256 }
257
258 /*
259   Return a merged list of the attributes of exactly one class (not
260   considering subclasses, auxillary classes etc)
261 */
262
263 const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
264 {
265         const char **attr_list = NULL;
266         switch (query) {
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);
270                 break;
271                 
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);
275                 break;
276                 
277         case DSDB_SCHEMA_SYS_MAY:
278                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
279                 break;
280                 
281         case DSDB_SCHEMA_SYS_MUST:
282                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
283                 break;
284                 
285         case DSDB_SCHEMA_MAY:
286                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
287                 break;
288                 
289         case DSDB_SCHEMA_MUST:
290                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
291                 break;
292                 
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);
298                 break;
299         }
300         return attr_list;
301 }
302
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) 
307 {
308         const char **this_class_list;
309         const char **system_recursive_list;
310         const char **recursive_list;
311         const char **attr_list;
312
313         this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
314         
315         recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema, 
316                                                            sclass->systemAuxiliaryClass,
317                                                            query);
318         
319         system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema, 
320                                                                   sclass->auxiliaryClass,
321                                                                   query);
322         
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);
326         return attr_list;
327 }
328
329 /* Return a full attribute list for a given class list
330
331    Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
332  */
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)
337 {
338         unsigned int i;
339         const char **attr_list = NULL;
340
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]),
345                                                     query);
346
347                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
348         }
349         return attr_list;
350 }
351
352 /* Return a full attribute list for a given class list (as a ldb_message_element)
353
354    Using the ldb_message_element ensures we do length-limited
355    comparisons, rather than casting the possibly-unterminated string
356
357    Via attribute_list_from_class() this calls 
358    dsdb_full_attribute_list_internal() when recursing on auxiliary classes
359  */
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)
364 {
365         unsigned int i;
366         const char **attr_list = NULL;
367
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]),
372                                                     query);
373                 
374                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
375         }
376         return attr_list;
377 }
378
379 static int qsort_string(const char **s1, const char **s2)
380 {
381         return strcasecmp(*s1, *s2);
382 }
383
384 /* Helper function to remove duplicates from the attribute list to be returned */
385 static const char **dedup_attr_list(const char **attr_list) 
386 {
387         size_t new_len = str_list_length(attr_list);
388         /* Remove duplicates */
389         if (new_len > 1) {
390                 size_t i;
391                 TYPESAFE_QSORT(attr_list, new_len, qsort_string);
392                 
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;
399                                 new_len--;
400                                 i--;
401                         }
402                 }
403         }
404         return attr_list;
405 }
406
407 /* Return a full attribute list for a given class list (as a ldb_message_element)
408
409    Using the ldb_message_element ensures we do length-limited
410    comparisons, rather than casting the possibly-unterminated string
411
412    The result contains only unique values
413  */
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)
418 {
419         const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
420         return dedup_attr_list(attr_list);
421 }
422
423 /* Return the schemaIDGUID of a class */
424
425 const struct GUID *class_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
426                                                           const char *name)
427 {
428         const struct dsdb_class *object_class = dsdb_class_by_lDAPDisplayName(schema, name);
429         if (!object_class)
430                 return NULL;
431
432         return &object_class->schemaIDGUID;
433 }
434
435 const struct GUID *attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
436                                                               const char *name)
437 {
438         const struct dsdb_attribute *attr = dsdb_attribute_by_lDAPDisplayName(schema, name);
439         if (!attr)
440                 return NULL;
441
442         return &attr->schemaIDGUID;
443 }
444
445 /*
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".
451  */
452 int dsdb_sort_objectClass_attr(struct ldb_context *ldb,
453                                const struct dsdb_schema *schema,
454                                const struct ldb_message_element *objectclass_element,
455                                TALLOC_CTX *mem_ctx,
456                                struct ldb_message_element *out_objectclass_element)
457 {
458         unsigned int i, lowest;
459         struct class_list {
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;
467
468         tmp_mem_ctx = talloc_new(mem_ctx);
469         if (tmp_mem_ctx == NULL) {
470                 return ldb_oom(ldb);
471         }
472
473         /*
474          * DESIGN:
475          *
476          * We work on 4 different 'bins' (implemented here as linked lists):
477          *
478          * * sorted:       the eventual list, in the order we wish to push
479          *                 into the database.  This is the only ordered list.
480          *
481          * * parent_class: The current parent class 'bin' we are
482          *                 trying to find subclasses for
483          *
484          * * subclass:     The subclasses we have found so far
485          *
486          * * unsorted:     The remaining objectClasses
487          *
488          * The process is a matter of filtering objectClasses up from
489          * unsorted into sorted.  Order is irrelevent in the later 3 'bins'.
490          *
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.
496          *
497          * We then repeat, until we find no more subclasses.  Any left
498          * over classes are added to the end.
499          *
500          */
501
502         /*
503          * Firstly, dump all the "objectClass" values into the unsorted bin,
504          * except for 'top', which is special
505          */
506         for (i=0; i < objectclass_element->num_values; i++) {
507                 current = talloc(tmp_mem_ctx, struct class_list);
508                 if (!current) {
509                         talloc_free(tmp_mem_ctx);
510                         return ldb_oom(ldb);
511                 }
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;
525                 }
526
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);
530                 }
531         }
532
533
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);
538
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) {
543                                 break;
544                         }
545                 }
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)) {
548                         continue;
549                 }
550
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);
554         }
555
556         /* For each object: order by hierarchy */
557         while (unsorted != NULL) {
558                 lowest = UINT_MAX;
559                 current_lowest = current_lowest_struct = NULL;
560                 for (current = unsorted; current != NULL; current = current->next) {
561                         if (current->objectclass->subClass_order <= lowest) {
562                                 /*
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
566                                  */
567                                 if (current->objectclass->objectClassCategory > 1) {
568                                         current_lowest = current;
569                                 } else {
570                                         current_lowest_struct = current;
571                                 }
572                                 lowest = current->objectclass->subClass_order;
573                         }
574                 }
575                 if (current_lowest == NULL) {
576                         current_lowest = current_lowest_struct;
577                 }
578
579                 if (current_lowest != NULL) {
580                         DLIST_REMOVE(unsorted,current_lowest);
581                         DLIST_ADD_END(sorted,current_lowest);
582                 }
583         }
584
585         /* Now rebuild the sorted "objectClass" message element */
586         el = out_objectclass_element;
587
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);
592                 return ldb_oom(ldb);
593         }
594         el->num_values = 0;
595         el->values = NULL;
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);
601                         return ldb_oom(ldb);
602                 }
603                 el->values[el->num_values] = data_blob_string_const(current->objectclass->lDAPDisplayName);
604
605                 ++(el->num_values);
606         }
607
608         talloc_free(tmp_mem_ctx);
609         return LDB_SUCCESS;
610 }