s4:dsdb_sort_objectClass_attr - simplify memory context handling
[obnox/samba/samba-obnox.git] / source4 / dsdb / schema / schema_query.c
1 /* 
2    Unix SMB/CIFS mplementation.
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 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);
34
35 static int uint32_cmp(uint32_t c1, uint32_t c2) 
36 {
37         if (c1 == c2) return 0;
38         return c1 > c2 ? 1 : -1;
39 }
40
41 static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)
42 {
43         int ret = strncasecmp((const char *)target->data, str, target->length);
44         if (ret == 0) {
45                 size_t len = strlen(str);
46                 if (target->length > len) {
47                         if (target->data[len] == 0) {
48                                 return 0;
49                         }
50                         return 1;
51                 }
52                 return (target->length - len);
53         }
54         return ret;
55 }
56
57 const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
58                                                               uint32_t id)
59 {
60         struct dsdb_attribute *c;
61
62         /*
63          * 0xFFFFFFFF is used as value when no mapping table is available,
64          * so don't try to match with it
65          */
66         if (id == 0xFFFFFFFF) return NULL;
67
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);
72                 return c;
73         }
74
75         BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,
76                               schema->num_attributes, attributeID_id, id, uint32_cmp, c);
77         return c;
78 }
79
80 const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
81                                                                const char *oid)
82 {
83         struct dsdb_attribute *c;
84
85         if (!oid) return NULL;
86
87         BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_oid,
88                               schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
89         return c;
90 }
91
92 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
93                                                                const char *name)
94 {
95         struct dsdb_attribute *c;
96
97         if (!name) return NULL;
98
99         BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
100                               schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
101         return c;
102 }
103
104 const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
105                                                                        const struct ldb_val *name)
106 {
107         struct dsdb_attribute *a;
108
109         if (!name) return NULL;
110
111         BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,
112                               schema->num_attributes, lDAPDisplayName, name, strcasecmp_with_ldb_val, a);
113         return a;
114 }
115
116 const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
117                                                       int linkID)
118 {
119         struct dsdb_attribute *c;
120
121         BINARY_ARRAY_SEARCH_P(schema->attributes_by_linkID,
122                               schema->num_attributes, linkID, linkID, uint32_cmp, c);
123         return c;
124 }
125
126 const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
127                                                     uint32_t id)
128 {
129         struct dsdb_class *c;
130
131         /*
132          * 0xFFFFFFFF is used as value when no mapping table is available,
133          * so don't try to match with it
134          */
135         if (id == 0xFFFFFFFF) return NULL;
136
137         BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_id,
138                               schema->num_classes, governsID_id, id, uint32_cmp, c);
139         return c;
140 }
141
142 const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
143                                                      const char *oid)
144 {
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);
149         return c;
150 }
151
152 const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
153                                                        const char *name)
154 {
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);
159         return c;
160 }
161
162 const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
163                                                                const struct ldb_val *name)
164 {
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);
169         return c;
170 }
171
172 const struct dsdb_class *dsdb_class_by_cn(const struct dsdb_schema *schema,
173                                           const char *cn)
174 {
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);
179         return c;
180 }
181
182 const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
183                                                   const struct ldb_val *cn)
184 {
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);
189         return c;
190 }
191
192 const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
193                                        uint32_t id)
194 {
195         const struct dsdb_attribute *a;
196         const struct dsdb_class *c;
197
198         a = dsdb_attribute_by_attributeID_id(schema, id);
199         if (a) {
200                 return a->lDAPDisplayName;
201         }
202
203         c = dsdb_class_by_governsID_id(schema, id);
204         if (c) {
205                 return c->lDAPDisplayName;
206         }
207
208         return NULL;
209 }
210
211 /** 
212     Return a list of linked attributes, in lDAPDisplayName format.
213
214     This may be used to determine if a modification would require
215     backlinks to be updated, for example
216 */
217
218 WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)
219 {
220         const char **attr_list = NULL;
221         struct dsdb_attribute *cur;
222         unsigned int i = 0;
223         for (cur = schema->attributes; cur; cur = cur->next) {
224                 if (cur->linkID == 0) continue;
225                 
226                 attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);
227                 if (!attr_list) {
228                         return WERR_NOMEM;
229                 }
230                 attr_list[i] = cur->lDAPDisplayName;
231                 i++;
232         }
233         attr_list[i] = NULL;
234         *attr_list_ret = attr_list;
235         return WERR_OK;
236 }
237
238 const char **merge_attr_list(TALLOC_CTX *mem_ctx, 
239                        const char **attrs, const char * const*new_attrs) 
240 {
241         const char **ret_attrs;
242         unsigned int i;
243         size_t new_len, orig_len = str_list_length(attrs);
244         if (!new_attrs) {
245                 return attrs;
246         }
247
248         ret_attrs = talloc_realloc(mem_ctx, 
249                                    attrs, const char *, orig_len + str_list_length(new_attrs) + 1);
250         if (ret_attrs) {
251                 for (i=0; i < str_list_length(new_attrs); i++) {
252                         ret_attrs[orig_len + i] = new_attrs[i];
253                 }
254                 new_len = orig_len + str_list_length(new_attrs);
255
256                 ret_attrs[new_len] = NULL;
257         }
258
259         return ret_attrs;
260 }
261
262 /*
263   Return a merged list of the attributes of exactly one class (not
264   considering subclasses, auxillary classes etc)
265 */
266
267 const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
268 {
269         const char **attr_list = NULL;
270         switch (query) {
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);
274                 break;
275                 
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);
279                 break;
280                 
281         case DSDB_SCHEMA_SYS_MAY:
282                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
283                 break;
284                 
285         case DSDB_SCHEMA_SYS_MUST:
286                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
287                 break;
288                 
289         case DSDB_SCHEMA_MAY:
290                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
291                 break;
292                 
293         case DSDB_SCHEMA_MUST:
294                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
295                 break;
296                 
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);
302                 break;
303         }
304         return attr_list;
305 }
306
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) 
311 {
312         const char **this_class_list;
313         const char **system_recursive_list;
314         const char **recursive_list;
315         const char **attr_list;
316
317         this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
318         
319         recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema, 
320                                                            sclass->systemAuxiliaryClass,
321                                                            query);
322         
323         system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema, 
324                                                                   sclass->auxiliaryClass,
325                                                                   query);
326         
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);
330         return attr_list;
331 }
332
333 /* Return a full attribute list for a given class list
334
335    Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
336  */
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)
341 {
342         unsigned int i;
343         const char **attr_list = NULL;
344
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]),
349                                                     query);
350
351                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
352         }
353         return attr_list;
354 }
355
356 /* Return a full attribute list for a given class list (as a ldb_message_element)
357
358    Using the ldb_message_element ensures we do length-limited
359    comparisons, rather than casting the possibly-unterminated string
360
361    Via attribute_list_from_class() this calls 
362    dsdb_full_attribute_list_internal() when recursing on auxiliary classes
363  */
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)
368 {
369         unsigned int i;
370         const char **attr_list = NULL;
371
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]),
376                                                     query);
377                 
378                 attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
379         }
380         return attr_list;
381 }
382
383 static int qsort_string(const char **s1, const char **s2)
384 {
385         return strcasecmp(*s1, *s2);
386 }
387
388 /* Helper function to remove duplicates from the attribute list to be returned */
389 static const char **dedup_attr_list(const char **attr_list) 
390 {
391         size_t new_len = str_list_length(attr_list);
392         /* Remove duplicates */
393         if (new_len > 1) {
394                 size_t i;
395                 TYPESAFE_QSORT(attr_list, new_len, qsort_string);
396                 
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;
403                                 new_len--;
404                                 i--;
405                         }
406                 }
407         }
408         return attr_list;
409 }
410
411 /* Return a full attribute list for a given class list (as a ldb_message_element)
412
413    Using the ldb_message_element ensures we do length-limited
414    comparisons, rather than casting the possibly-unterminated string
415
416    The result contains only unique values
417  */
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)
422 {
423         const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
424         return dedup_attr_list(attr_list);
425 }
426
427 /* Return the schemaIDGUID of a class */
428
429 const struct GUID *class_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
430                                                           const char *name)
431 {
432         const struct dsdb_class *object_class = dsdb_class_by_lDAPDisplayName(schema, name);
433         if (!object_class)
434                 return NULL;
435
436         return &object_class->schemaIDGUID;
437 }
438
439 const struct GUID *attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,
440                                                               const char *name)
441 {
442         const struct dsdb_attribute *attr = dsdb_attribute_by_lDAPDisplayName(schema, name);
443         if (!attr)
444                 return NULL;
445
446         return &attr->schemaIDGUID;
447 }
448
449 /*
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 "mem_ctx".
455  */
456 int dsdb_sort_objectClass_attr(struct ldb_context *ldb,
457                                const struct dsdb_schema *schema,
458                                const struct ldb_message_element *objectclass_element,
459                                TALLOC_CTX *mem_ctx,
460                                struct ldb_message_element *out_objectclass_element)
461 {
462         unsigned int i, lowest;
463         struct class_list {
464                 struct class_list *prev, *next;
465                 const struct dsdb_class *objectclass;
466         } *unsorted = NULL, *sorted = NULL, *current = NULL,
467           *poss_parent = NULL, *new_parent = NULL,
468           *current_lowest = NULL, *current_lowest_struct = NULL;
469         struct ldb_message_element *el;
470         TALLOC_CTX *tmp_mem_ctx;
471
472         tmp_mem_ctx = talloc_new(mem_ctx);
473         if (tmp_mem_ctx == NULL) {
474                 return ldb_oom(ldb);
475         }
476
477         /*
478          * DESIGN:
479          *
480          * We work on 4 different 'bins' (implemented here as linked lists):
481          *
482          * * sorted:       the eventual list, in the order we wish to push
483          *                 into the database.  This is the only ordered list.
484          *
485          * * parent_class: The current parent class 'bin' we are
486          *                 trying to find subclasses for
487          *
488          * * subclass:     The subclasses we have found so far
489          *
490          * * unsorted:     The remaining objectClasses
491          *
492          * The process is a matter of filtering objectClasses up from
493          * unsorted into sorted.  Order is irrelevent in the later 3 'bins'.
494          *
495          * We start with 'top' (found and promoted to parent_class
496          * initially).  Then we find (in unsorted) all the direct
497          * subclasses of 'top'.  parent_classes is concatenated onto
498          * the end of 'sorted', and subclass becomes the list in
499          * parent_class.
500          *
501          * We then repeat, until we find no more subclasses.  Any left
502          * over classes are added to the end.
503          *
504          */
505
506         /*
507          * Firstly, dump all the "objectClass" values into the unsorted bin,
508          * except for 'top', which is special
509          */
510         for (i=0; i < objectclass_element->num_values; i++) {
511                 current = talloc(tmp_mem_ctx, struct class_list);
512                 if (!current) {
513                         talloc_free(tmp_mem_ctx);
514                         return ldb_oom(ldb);
515                 }
516                 current->objectclass = dsdb_class_by_lDAPDisplayName_ldb_val(schema, &objectclass_element->values[i]);
517                 if (!current->objectclass) {
518                         ldb_asprintf_errstring(ldb, "objectclass %.*s is not a valid objectClass in schema",
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                         talloc_free(tmp_mem_ctx);
522                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
523                 } else if (current->objectclass->isDefunct) {
524                         ldb_asprintf_errstring(ldb, "objectclass %.*s marked as isDefunct objectClass in schema - not valid for new objects",
525                                                (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);
526                         /* This looks weird, but windows apparently returns this for invalid objectClass values */
527                         talloc_free(tmp_mem_ctx);
528                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
529                 }
530
531                 /* Don't add top to list, we will do that later */
532                 if (ldb_attr_cmp("top", current->objectclass->lDAPDisplayName) != 0) {
533                         DLIST_ADD_END(unsorted, current, struct class_list *);
534                 }
535         }
536
537
538         /* Add top here, to prevent duplicates */
539         current = talloc(tmp_mem_ctx, struct class_list);
540         current->objectclass = dsdb_class_by_lDAPDisplayName(schema, "top");
541         DLIST_ADD_END(sorted, current, struct class_list *);
542
543         /* For each object: find parent chain */
544         for (current = unsorted; current != NULL; current = current->next) {
545                 for (poss_parent = unsorted; poss_parent; poss_parent = poss_parent->next) {
546                         if (ldb_attr_cmp(poss_parent->objectclass->lDAPDisplayName, current->objectclass->subClassOf) == 0) {
547                                 break;
548                         }
549                 }
550                 /* If we didn't get to the end of the list, we need to add this parent */
551                 if (poss_parent || (ldb_attr_cmp("top", current->objectclass->subClassOf) == 0)) {
552                         continue;
553                 }
554
555                 new_parent = talloc(tmp_mem_ctx, struct class_list);
556                 new_parent->objectclass = dsdb_class_by_lDAPDisplayName(schema, current->objectclass->subClassOf);
557                 DLIST_ADD_END(unsorted, new_parent, struct class_list *);
558         }
559
560         /* For each object: order by hierarchy */
561         while (unsorted != NULL) {
562                 lowest = UINT_MAX;
563                 current_lowest = current_lowest_struct = NULL;
564                 for (current = unsorted; current != NULL; current = current->next) {
565                         if (current->objectclass->subClass_order <= lowest) {
566                                 /*
567                                  * According to MS-ADTS 3.1.1.1.4 structural
568                                  * and 88 object classes are always listed after
569                                  * the other class types in a subclass hierarchy
570                                  */
571                                 if (current->objectclass->objectClassCategory > 1) {
572                                         current_lowest = current;
573                                 } else {
574                                         current_lowest_struct = current;
575                                 }
576                                 lowest = current->objectclass->subClass_order;
577                         }
578                 }
579                 if (current_lowest == NULL) {
580                         current_lowest = current_lowest_struct;
581                 }
582
583                 if (current_lowest != NULL) {
584                         DLIST_REMOVE(unsorted,current_lowest);
585                         DLIST_ADD_END(sorted,current_lowest, struct class_list *);
586                 }
587         }
588
589         /* Now rebuild the sorted "objectClass" message element */
590         el = out_objectclass_element;
591
592         el->flags = objectclass_element->flags;
593         el->name = talloc_strdup(mem_ctx, objectclass_element->name);
594         if (el->name == NULL) {
595                 talloc_free(tmp_mem_ctx);
596                 return ldb_oom(ldb);
597         }
598         el->num_values = 0;
599         el->values = NULL;
600         for (current = sorted; current != NULL; current = current->next) {
601                 el->values = talloc_realloc(mem_ctx, el->values,
602                                             struct ldb_val, el->num_values + 1);
603                 if (el->values == NULL) {
604                         talloc_free(tmp_mem_ctx);
605                         return ldb_oom(ldb);
606                 }
607                 el->values[el->num_values] = data_blob_string_const(current->objectclass->lDAPDisplayName);
608
609                 ++(el->num_values);
610         }
611
612         talloc_free(tmp_mem_ctx);
613         return LDB_SUCCESS;
614 }