Convert some more files to GPLv3.
[jra/samba/.git] / source4 / dsdb / samdb / ldb_modules / schema.c
1 /* 
2    ldb database library
3
4    Copyright (C) Simo Sorce  2004-2006
5
6    This program is free software; you can redistribute it and/or modify
7    it under the terms of the GNU General Public License as published by
8    the Free Software Foundation; either version 3 of the License, or
9    (at your option) any later version.
10    
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15    
16    You should have received a copy of the GNU General Public License
17    along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 /*
21  *  Name: ldb
22  *
23  *  Component: ldb schema module
24  *
25  *  Description: add schema check functionality
26  *
27  *  Author: Simo Sorce
28  */
29
30 #include "includes.h"
31 #include "libcli/ldap/ldap.h"
32 #include "ldb/include/ldb_errors.h"
33 #include "ldb/include/ldb_private.h"
34 #include "lib/util/dlinklist.h"
35 #include "schema_syntax.h"
36
37 /* Syntax-Table
38
39    see ldap_server/devdocs/AD-syntaxes.txt
40 */
41
42 enum schema_class_type {
43         SCHEMA_CT_88            = 0,
44         SCHEMA_CT_STRUCTURAL    = 1,
45         SCHEMA_CT_ABSTRACT      = 2,
46         SCHEMA_CT_AUXILIARY     = 3
47 };
48
49 struct schema_attribute {
50         char *OID;                              /* attributeID     */
51         char *name;                             /* lDAPDisplayName */
52         enum schema_internal_syntax syntax;     /* generated from attributeSyntax, oMSyntax, oMObjectClass */
53         bool single;                            /* isSingleValued  */
54         int min;                                /* rangeLower      */
55         int max;                                /* rangeUpper      */
56         int systemflag;                         /* systemFlag      */
57         int searchflag;                         /* searchFlag      */
58         bool isdefunct;                         /* isDefunct       */
59 };
60
61 struct schema_class {
62         char *OID;                              /* governsID             */
63         char *name;                             /* lDAPDisplayName       */
64         enum schema_class_type type;            /* objectClassCategory   */
65         bool systemOnly;                        /* systemOnly            */
66         bool isdefunct;                         /* isDefunct             */
67         int systemflag;                         /* systemFlag            */
68         char *defobjcat;                        /* defaultObjectCategory */
69         struct schema_class *parent;            /* subClassOf            */
70         struct schema_class **sysaux;           /* systemAuxiliaryClass  */
71         struct schema_class **aux;              /* auxiliaryClass        */
72         struct schema_class **sysposssup;       /* systemPossSuperiors   */
73         struct schema_class **posssup;          /* possSuperiors         */
74         struct schema_class **possinf;          /* possibleInferiors     */
75         struct schema_attribute **sysmust;      /* systemMustContain     */
76         struct schema_attribute **must;         /* MustContain           */
77         struct schema_attribute **sysmay;       /* systemMayContain      */
78         struct schema_attribute **may;          /* MayContain            */
79 };
80
81 /* TODO: ditcontentrules */
82
83 struct schema_private_data {
84         struct ldb_dn *schema_dn;
85         struct schema_attribute **attrs;
86         struct schema_store *attrs_store;
87         int num_attributes;
88         struct schema_class **class;
89         struct schema_store *class_store;
90         int num_classes;
91 };
92
93 struct schema_class_dlist {
94         struct schema_class *class;
95         struct schema_class_dlist *prev;
96         struct schema_class_dlist *next;
97         enum schema_class_type role;
98 };
99
100 struct schema_context {
101
102         enum sc_op { SC_ADD, SC_MOD, SC_DEL, SC_RENAME } op;
103         enum sc_step { SC_INIT, SC_ADD_CHECK_PARENT, SC_ADD_TEMP, SC_DEL_CHECK_CHILDREN } step;
104
105         struct schema_private_data *data;
106
107         struct ldb_module *module;
108         struct ldb_request *orig_req;
109         struct ldb_request *down_req;
110
111         struct ldb_request *parent_req;
112         struct ldb_reply *parent_res;
113
114         struct schema_class_dlist *class_list;
115         struct schema_class **sup_list;
116         struct schema_class **aux_list;
117 };
118
119 /* FIXME: I'd really like to use an hash table here */
120 struct schema_link {
121         const char *name;
122         void *object;
123 };
124
125 struct schema_store {
126         struct schema_link *store;
127         int num_links;
128 };
129
130 static struct schema_store *schema_store_new(TALLOC_CTX *mem_ctx)
131 {
132         struct schema_store *ht;
133         
134         ht = talloc(mem_ctx, struct schema_store);
135         if (!ht) return NULL;
136
137         ht->store = NULL;
138         ht->num_links = 0;
139
140         return ht;
141 }
142         
143 static int schema_store_add(struct schema_store *ht, const char *key, void *object)
144 {
145         ht->store = talloc_realloc(ht, ht->store, struct schema_link, ht->num_links + 1);
146         if (!ht->store) return LDB_ERR_OPERATIONS_ERROR;
147
148         ht->store[ht->num_links].name = key;
149         ht->store[ht->num_links].object = object;
150
151         ht->num_links++;
152
153         return LDB_SUCCESS;
154 }
155
156 static void *schema_store_find(struct schema_store *ht, const char *key)
157 {
158         int i;
159
160         for (i = 0; i < ht->num_links; i++) {
161                 if (strcasecmp(ht->store[i].name, key) == 0) {
162                         return ht->store[i].object;
163                 }
164         }
165
166         return NULL;
167 }
168
169 #define SCHEMA_CHECK_VALUE(mem, val, mod) \
170                 do { if (mem == val) { \
171                         ret = LDB_ERR_OPERATIONS_ERROR; \
172                         ldb_asprintf_errstring(mod->ldb, \
173                                 "schema module: Memory allocation or attribute error on %s", #mem); \
174                         goto done; } } while(0)
175
176 struct schema_class **schema_get_class_list(struct ldb_module *module,
177                                             struct schema_private_data *data,
178                                             struct ldb_message_element *el)
179 {
180         struct schema_class **list;
181         int i;
182         
183         list = talloc_array(data, struct schema_class *, el->num_values + 1);
184         if (!list) {
185                 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Out of Memory");
186                 return NULL;
187         }
188         
189         for (i = 0; i < el->num_values; i++) {
190                 list[i] = (struct schema_class *)schema_store_find(data->class_store,
191                                                                   (char *)el->values[i].data);
192                 if (!list[i]) {
193                         ldb_debug_set(module->ldb,
194                                         LDB_DEBUG_ERROR,
195                                         "Class %s referenced but not found in schema\n",
196                                         (char *)el->values[i].data);
197                         return NULL;
198                 }
199         }
200         list[i] = NULL;
201
202         return list;
203 }
204
205 struct schema_attribute **schema_get_attrs_list(struct ldb_module *module,
206                                                 struct schema_private_data *data,
207                                                 struct ldb_message_element *el)
208 {
209         struct schema_attribute **list;
210         int i;
211
212         list = talloc_array(data, struct schema_attribute *, el->num_values + 1);
213         if (!list) {
214                 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Out of Memory");
215                 return NULL;
216         }
217         
218         for (i = 0; i < el->num_values; i++) {
219                 list[i] = (struct schema_attribute *)schema_store_find(data->attrs_store,
220                                                                       (char *)el->values[i].data);
221                 if (!list[i]) {
222                         ldb_debug_set(module->ldb,
223                                         LDB_DEBUG_ERROR,
224                                         "Attriobute %s referenced but not found in schema\n",
225                                         (char *)el->values[i].data);
226                         return NULL;
227                 }
228         }
229         list[i] = NULL;
230
231         return list;
232 }
233
234 static int schema_init_attrs(struct ldb_module *module, struct schema_private_data *data)
235 {
236         static const char *schema_attrs[] = {   "attributeID",
237                                                 "lDAPDisplayName",
238                                                 "attributeSyntax",
239                                                 "oMSyntax",
240                                                 "oMObjectClass",
241                                                 "isSingleValued",
242                                                 "rangeLower",
243                                                 "rangeUpper",
244                                                 "searchFlag",
245                                                 "systemFlag",
246                                                 "isDefunct",
247                                                 NULL };
248         struct ldb_result *res;
249         int ret, i;
250
251         ret = ldb_search(module->ldb,
252                          data->schema_dn,
253                          LDB_SCOPE_SUBTREE,
254                          "(objectClass=attributeSchema)",
255                          schema_attrs,
256                          &res);
257
258         if (ret != LDB_SUCCESS) {
259                 goto done;
260         }
261
262         data->num_attributes = res->count;
263         data->attrs = talloc_array(data, struct schema_attribute *, res->count);
264         SCHEMA_CHECK_VALUE(data->attrs, NULL, module);
265
266         data->attrs_store = schema_store_new(data);
267         SCHEMA_CHECK_VALUE(data->attrs_store, NULL, module);
268         
269         for (i = 0; i < res->count; i++) {
270                 const char *tmp_single;
271                 const char *attr_syntax;
272                 uint32_t om_syntax;
273                 const struct ldb_val *om_class;
274
275                 data->attrs[i] = talloc(data->attrs, struct schema_attribute);
276                 SCHEMA_CHECK_VALUE(data->attrs[i], NULL, module);
277
278                 data->attrs[i]->OID = talloc_strdup(data->attrs[i],
279                                                 ldb_msg_find_attr_as_string(res->msgs[i], "attributeID", NULL));
280                 SCHEMA_CHECK_VALUE(data->attrs[i]->OID, NULL, module);
281                 
282                 data->attrs[i]->name = talloc_strdup(data->attrs[i],
283                                                 ldb_msg_find_attr_as_string(res->msgs[i], "lDAPDisplayName", NULL));
284                 SCHEMA_CHECK_VALUE(data->attrs[i]->name, NULL, module);
285
286                 /* once we have both the OID and the attribute name, add the pointer to the store */
287                 schema_store_add(data->attrs_store, data->attrs[i]->OID, data->attrs[i]);
288                 schema_store_add(data->attrs_store, data->attrs[i]->name, data->attrs[i]);
289
290                 attr_syntax = ldb_msg_find_attr_as_string(res->msgs[i], "attributeSyntax", NULL);
291                 SCHEMA_CHECK_VALUE(attr_syntax, NULL, module);
292                 
293                 om_syntax = ldb_msg_find_attr_as_uint(res->msgs[i], "oMSyntax", 0);
294                 /* 0 is not a valid oMSyntax */
295                 SCHEMA_CHECK_VALUE(om_syntax, 0, module);
296
297                 om_class = ldb_msg_find_ldb_val(res->msgs[i], "oMObjectClass");
298
299                 ret = map_schema_syntax(om_syntax, attr_syntax, om_class, &data->attrs[i]->syntax);
300                 if (ret != LDB_SUCCESS) {
301                         ldb_asprintf_errstring(module->ldb,
302                                 "schema module: invalid om syntax value on %s",
303                                 data->attrs[i]->name);
304                         goto done;
305                 }
306                 
307                 tmp_single = ldb_msg_find_attr_as_string(res->msgs[i], "isSingleValued", NULL);
308                 SCHEMA_CHECK_VALUE(tmp_single, NULL, module);
309                 if (strcmp(tmp_single, "TRUE") == 0) {
310                         data->attrs[i]->single = 1;
311                 } else {
312                         data->attrs[i]->single = 0;
313                 }
314
315                 /* the following are optional */
316                 data->attrs[i]->min = ldb_msg_find_attr_as_int(res->msgs[i], "rangeLower", INT_MIN);
317                 data->attrs[i]->max = ldb_msg_find_attr_as_int(res->msgs[i], "rangeUpper", INT_MAX);
318                 data->attrs[i]->systemflag = ldb_msg_find_attr_as_int(res->msgs[i], "systemFlag", 0);
319                 data->attrs[i]->searchflag = ldb_msg_find_attr_as_int(res->msgs[i], "searchFlag", 0);
320                 data->attrs[i]->isdefunct = ldb_msg_find_attr_as_bool(res->msgs[i], "isDefunct", false);
321         }
322
323 done:
324         talloc_free(res);
325         return ret;
326 }
327
328 static int schema_init_classes(struct ldb_module *module, struct schema_private_data *data)
329 {
330         const char *schema_attrs[] = {  "governsID",
331                                                 "lDAPDisplayName",
332                                                 "objectClassCategory",
333                                                 "defaultObjectCategory",
334                                                 "systemOnly",
335                                                 "systemFlag",
336                                                 "isDefunct",
337                                                 "subClassOf",
338                                                 "systemAuxiliaryClass",
339                                                 "auxiliaryClass",
340                                                 "systemPossSuperiors",
341                                                 "possSuperiors",
342                                                 "possibleInferiors",
343                                                 "systemMustContain",
344                                                 "MustContain", 
345                                                 "systemMayContain",
346                                                 "MayContain",
347                                                 NULL };
348         struct ldb_result *res;
349         int ret, i;
350
351         ret = ldb_search(module->ldb,
352                          data->schema_dn,
353                          LDB_SCOPE_SUBTREE,
354                          "(objectClass=classSchema)",
355                          schema_attrs,
356                          &res);
357
358         if (ret != LDB_SUCCESS) {
359                 goto done;
360         }
361
362         data->num_classes = res->count;
363         data->class = talloc_array(data, struct schema_class *, res->count);
364         SCHEMA_CHECK_VALUE(data->class, NULL, module);
365
366         data->class_store = schema_store_new(data);
367         SCHEMA_CHECK_VALUE(data->class_store, NULL, module);
368
369         for (i = 0; i < res->count; i++) {
370                 struct ldb_message_element *el;
371
372                 data->class[i] = talloc(data->class, struct schema_class);
373                 SCHEMA_CHECK_VALUE(data->class[i], NULL, module);
374
375                 data->class[i]->OID = talloc_strdup(data->class[i],
376                                                 ldb_msg_find_attr_as_string(res->msgs[i], "governsID", NULL));
377                 SCHEMA_CHECK_VALUE(data->class[i]->OID, NULL, module);
378
379                 data->class[i]->name = talloc_strdup(data->class[i],
380                                                 ldb_msg_find_attr_as_string(res->msgs[i], "lDAPDisplayName", NULL));
381                 SCHEMA_CHECK_VALUE(data->class[i]->name, NULL, module);
382
383                 /* once we have both the OID and the class name, add the pointer to the store */
384                 schema_store_add(data->class_store, data->class[i]->OID, data->class[i]);
385                 schema_store_add(data->class_store, data->class[i]->name, data->class[i]);
386
387                 data->class[i]->type = ldb_msg_find_attr_as_int(res->msgs[i], "objectClassCategory", -1);
388                 /* 0 should not be a valid value, but turn out it is so test with -1 */
389                 SCHEMA_CHECK_VALUE(data->class[i]->type, -1, module);
390
391                 data->class[i]->defobjcat = talloc_strdup(data->class[i],
392                                                 ldb_msg_find_attr_as_string(res->msgs[i],
393                                                                         "defaultObjectCategory", NULL));
394 /*              SCHEMA_CHECK_VALUE(data->class[i]->defobjcat, NULL, module);
395 */
396                 /* the following attributes are all optional */
397
398                 data->class[i]->systemOnly = ldb_msg_find_attr_as_bool(res->msgs[i], "systemOnly", false);
399                 data->class[i]->systemflag = ldb_msg_find_attr_as_int(res->msgs[i], "systemFlag", 0);
400                 data->class[i]->isdefunct = ldb_msg_find_attr_as_bool(res->msgs[i], "isDefunct", false);
401
402                 /* attributes are loaded first, so we can just go an query the attributes repo */
403                 
404                 el = ldb_msg_find_element(res->msgs[i], "systemMustContain");
405                 if (el) {
406                         data->class[i]->sysmust = schema_get_attrs_list(module, data, el);
407                         SCHEMA_CHECK_VALUE(data->class[i]->sysmust, NULL, module);
408                 }
409
410                 el = ldb_msg_find_element(res->msgs[i], "MustContain");
411                 if (el) {
412                         data->class[i]->must = schema_get_attrs_list(module, data, el);
413                         SCHEMA_CHECK_VALUE(data->class[i]->must, NULL, module);
414                 }
415
416                 el = ldb_msg_find_element(res->msgs[i], "systemMayContain");
417                 if (el) {
418                         data->class[i]->sysmay = schema_get_attrs_list(module, data, el);
419                         SCHEMA_CHECK_VALUE(data->class[i]->sysmay, NULL, module);
420                 }
421
422                 el = ldb_msg_find_element(res->msgs[i], "MayContain");
423                 if (el) {
424                         data->class[i]->may = schema_get_attrs_list(module, data, el);
425                         SCHEMA_CHECK_VALUE(data->class[i]->may, NULL, module);
426                 }
427
428         }
429
430         /* subClassOf, systemAuxiliaryClass, auxiliaryClass, systemPossSuperiors
431          * must be filled in a second loop, when all class objects are allocated
432          * or we may not find a class that has not yet been parsed */
433         for (i = 0; i < res->count; i++) {
434                 struct ldb_message_element *el;
435                 const char *attr;
436
437                 /* this is single valued anyway */
438                 attr = ldb_msg_find_attr_as_string(res->msgs[i], "subClassOf", NULL);
439                 SCHEMA_CHECK_VALUE(attr, NULL, module);
440                 data->class[i]->parent = schema_store_find(data->class_store, attr);
441                 SCHEMA_CHECK_VALUE(data->class[i]->parent, NULL, module);
442
443                 /* the following attributes are all optional */
444
445                 data->class[i]->sysaux = NULL;
446                 el = ldb_msg_find_element(res->msgs[i], "systemAuxiliaryClass");
447                 if (el) {
448                         data->class[i]->sysaux = schema_get_class_list(module, data, el); 
449                         SCHEMA_CHECK_VALUE(data->class[i]->sysaux, NULL, module);
450                 }
451
452                 data->class[i]->aux = NULL;
453                 el = ldb_msg_find_element(res->msgs[i], "auxiliaryClass");
454                 if (el) {
455                         data->class[i]->aux = schema_get_class_list(module, data, el); 
456                         SCHEMA_CHECK_VALUE(data->class[i]->aux, NULL, module);
457                 }
458
459                 data->class[i]->sysposssup = NULL;
460                 el = ldb_msg_find_element(res->msgs[i], "systemPossSuperiors");
461                 if (el) {
462                         data->class[i]->sysposssup = schema_get_class_list(module, data, el); 
463                         SCHEMA_CHECK_VALUE(data->class[i]->sysposssup, NULL, module);
464                 }
465
466                 data->class[i]->posssup = NULL;
467                 el = ldb_msg_find_element(res->msgs[i], "possSuperiors");
468                 if (el) {
469                         data->class[i]->posssup = schema_get_class_list(module, data, el); 
470                         SCHEMA_CHECK_VALUE(data->class[i]->posssup, NULL, module);
471                 }
472
473                 data->class[i]->possinf = NULL;
474                 el = ldb_msg_find_element(res->msgs[i], "possibleInferiors");
475                 if (el) {
476                         data->class[i]->possinf = schema_get_class_list(module, data, el); 
477                         SCHEMA_CHECK_VALUE(data->class[i]->possinf, NULL, module);
478                 }
479         }
480
481 done:
482         talloc_free(res);
483         return ret;
484 }
485
486 static struct ldb_handle *schema_init_handle(struct ldb_request *req, struct ldb_module *module, enum sc_op op)
487 {
488         struct schema_context *sctx;
489         struct ldb_handle *h;
490
491         h = talloc_zero(req, struct ldb_handle);
492         if (h == NULL) {
493                 ldb_set_errstring(module->ldb, "Out of Memory");
494                 return NULL;
495         }
496
497         h->module = module;
498
499         sctx = talloc_zero(h, struct schema_context);
500         if (sctx == NULL) {
501                 ldb_set_errstring(module->ldb, "Out of Memory");
502                 talloc_free(h);
503                 return NULL;
504         }
505
506         h->private_data = (void *)sctx;
507
508         h->state = LDB_ASYNC_INIT;
509         h->status = LDB_SUCCESS;
510
511         sctx->op = op;
512         sctx->step = SC_INIT;
513         sctx->data = module->private_data;
514         sctx->module = module;
515         sctx->orig_req = req;
516
517         return h;
518 }
519
520 static int schema_add_check_parent(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
521 {
522         struct schema_context *sctx;
523
524         sctx = talloc_get_type(context, struct schema_context);
525
526         /* we are interested only in the single reply (base search) we receive here */
527         if (ares->type == LDB_REPLY_ENTRY) {
528                 if (sctx->parent_res != NULL) {
529                         ldb_set_errstring(ldb, "Too many results");
530                         talloc_free(ares);
531                         return LDB_ERR_OPERATIONS_ERROR;
532                 }
533                 sctx->parent_res = talloc_steal(sctx, ares);
534         } else {
535                 talloc_free(ares);
536         }
537
538         return LDB_SUCCESS;
539 }
540
541 static int schema_add_build_parent_req(struct schema_context *sctx)
542 {
543         const char * const parent_attrs[] = { "objectClass", NULL };
544         int ret;
545
546         sctx->parent_req = talloc_zero(sctx, struct ldb_request);
547         if (sctx->parent_req == NULL) {
548                 ldb_debug(sctx->module->ldb, LDB_DEBUG_ERROR, "Out of Memory!\n");
549                 return LDB_ERR_OPERATIONS_ERROR;
550         }
551
552         sctx->parent_req->operation = LDB_SEARCH;
553         sctx->parent_req->op.search.scope = LDB_SCOPE_BASE;
554         sctx->parent_req->op.search.base = ldb_dn_get_parent(sctx->parent_req, sctx->orig_req->op.add.message->dn);
555         sctx->parent_req->op.search.tree = ldb_parse_tree(sctx->parent_req, "(objectClass=*)");
556         sctx->parent_req->op.search.attrs = parent_attrs;
557         sctx->parent_req->controls = NULL;
558         sctx->parent_req->context = sctx;
559         sctx->parent_req->callback = schema_add_check_parent;
560         ret = ldb_set_timeout_from_prev_req(sctx->module->ldb, sctx->orig_req, sctx->parent_req);
561
562         return ret;
563 }
564
565 static struct schema_class_dlist *schema_add_get_dlist_entry_with_class(struct schema_class_dlist *list, struct schema_class *class)
566 {
567         struct schema_class_dlist *temp;
568
569         for (temp = list; temp && (temp->class != class); temp = temp->next) /* noop */ ;
570         return temp;
571 }
572
573 static int schema_add_class_to_dlist(struct schema_class_dlist *list, struct schema_class *class, enum schema_class_type role)
574 {
575         struct schema_class_dlist *entry;
576         struct schema_class_dlist *temp;
577         int ret;
578
579         /* see if this class is usable */
580         if (class->isdefunct) {
581                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
582         }
583
584         /* see if this class already exist in the class list */
585         if (schema_add_get_dlist_entry_with_class(list, class)) {
586                 return LDB_SUCCESS;
587         }
588
589         /* this is a new class go on and add to the list */
590         entry = talloc_zero(list, struct schema_class_dlist);
591         if (!entry) return LDB_ERR_OPERATIONS_ERROR;
592         entry->class = class;
593         entry->role = class->type;
594
595         /* If parent is top (list is guaranteed to start always with top) */
596         if (class->parent == list->class) {
597                 /* if the hierarchy role is structural try to add it just after top */
598                 if (role == SCHEMA_CT_STRUCTURAL) {
599                         /* but check no other class at after top has a structural role */
600                         if (list->next && (list->next->role == SCHEMA_CT_STRUCTURAL)) {
601                                 return LDB_ERR_OBJECT_CLASS_VIOLATION;
602                         }
603                         DLIST_ADD_AFTER(list, entry, list);
604                 } else {
605                         DLIST_ADD_END(list, entry, struct schema_class_dlist *);
606                 }
607                 return LDB_SUCCESS;
608         }
609
610         /* search if parent has already been added */
611         temp = schema_add_get_dlist_entry_with_class(list->next, class->parent);
612         if (temp == NULL) {
613                 ret = schema_add_class_to_dlist(list, class->parent, role);
614                 if (ret != LDB_SUCCESS) {
615                         return ret;
616                 }
617                 temp = schema_add_get_dlist_entry_with_class(list->next, class->parent);
618         }
619         if (!temp) { /* parent not found !? */
620                 return LDB_ERR_OPERATIONS_ERROR;
621         }
622
623         DLIST_ADD_AFTER(list, entry, temp);
624         if (role == SCHEMA_CT_STRUCTURAL || role == SCHEMA_CT_AUXILIARY) {
625                 temp = entry;
626                 do {
627                         temp->role = role;
628                         temp = temp->prev;
629                         /* stop when hierarchy base is met or when base class parent is top */
630                 } while (temp->class == temp->next->class->parent &&
631                          temp->next->class->parent != list->class);
632
633                 /* if we have not reached the head of the list
634                  * and role is structural */
635                 if (temp != list && role == SCHEMA_CT_STRUCTURAL) {
636                         struct schema_class_dlist *hfirst, *hlast;
637
638                         /* check if the list second entry is structural */
639                         if (list->next->role == SCHEMA_CT_STRUCTURAL) {
640                                 /* we have a confilict here */
641                                 return LDB_ERR_OBJECT_CLASS_VIOLATION;
642                         }
643                         /* we have to move this hierarchy of classes
644                          * so that the base of the structural hierarchy is right after top */
645                          
646                         hfirst = temp->next;
647                         hlast = entry;
648                         /* now hfirst - hlast are the boundaries of the structural hierarchy */
649                         
650                         /* extract the structural hierachy from the list */
651                         hfirst->prev->next = hlast->next;
652                         if (hlast->next) hlast->next->prev = hfirst->prev;
653                         
654                         /* insert the structural hierarchy just after top */
655                         list->next->prev = hlast;
656                         hlast->next = list->next;
657                         list->next = hfirst;
658                         hfirst->prev = list;
659                 }       
660         }
661
662         return LDB_SUCCESS;
663 }
664
665 /* merge source list into dest list and remove duplicates */
666 static int schema_merge_class_list(TALLOC_CTX *mem_ctx, struct schema_class ***dest, struct schema_class **source)
667 {
668         struct schema_class **list = *dest;
669         int i, j, n, f;
670
671         n = 0;  
672         if (list) for (n = 0; list[n]; n++) /* noop */ ;
673         f = n;
674
675         for (i = 0; source[i]; i++) {
676                 for (j = 0; j < f; j++) {
677                         if (list[j] == source[i]) {
678                                 break;
679                         }
680                 }
681                 if (j < f) { /* duplicate found */
682                         continue;
683                 }
684
685                 list = talloc_realloc(mem_ctx, list, struct schema_class *, n + 2);
686                 if (!list) {
687                         return LDB_ERR_OPERATIONS_ERROR;
688                 }
689                 list[n] = source[i];
690                 n++;
691                 list[n] = NULL;
692         }
693
694         *dest = list;
695
696         return LDB_SUCCESS;
697 }
698
699 /* validate and modify the objectclass attribute to sort and add parents */
700 static int schema_add_build_objectclass_list(struct schema_context *sctx)
701 {
702         struct schema_class_dlist *temp;
703         struct ldb_message_element * el;
704         struct schema_class *class;
705         int ret, i, an;
706
707         /* First of all initialize list, it must start with class top */
708         sctx->class_list = talloc_zero(sctx, struct schema_class_dlist);
709         if (!sctx->class_list) return LDB_ERR_OPERATIONS_ERROR;
710
711         sctx->class_list->class = schema_store_find(sctx->data->class_store, "top");
712         if (!sctx->class_list->class) return LDB_ERR_OPERATIONS_ERROR;
713
714         el = ldb_msg_find_element(sctx->orig_req->op.add.message, "objectClass");
715         if (!el) {
716                 return LDB_ERR_OBJECT_CLASS_VIOLATION;
717         }
718
719         for (i = 0; i < el->num_values; i++) {
720
721                 class = schema_store_find(sctx->data->class_store, (char *)el->values[i].data);
722                 if (!class) {
723                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
724                 }
725                 
726                 ret = schema_add_class_to_dlist(sctx->class_list, class, class->type);
727                 if (ret != LDB_SUCCESS) {
728                         return ret;
729                 }
730         }
731
732         /* now check if there is any class role that is still not STRUCTURAL or AUXILIARY */
733         /* build also the auxiliary class list and the possible superiors list */ 
734         temp = sctx->class_list->next; /* top is special, skip it */
735         an = 0;
736
737         while (temp) {
738                 if (temp->role == SCHEMA_CT_ABSTRACT || temp->role == SCHEMA_CT_88) {
739                         return LDB_ERR_OBJECT_CLASS_VIOLATION;
740                 }
741                 if (temp->class->sysaux) {
742                         ret = schema_merge_class_list(sctx, &sctx->aux_list, temp->class->sysaux);
743                         if (ret != LDB_SUCCESS) {
744                                 return LDB_ERR_OPERATIONS_ERROR;
745                         }
746                 }
747                 if (temp->class->aux) {
748                         ret = schema_merge_class_list(sctx, &sctx->aux_list, temp->class->aux);
749                         if (ret != LDB_SUCCESS) {
750                                 return LDB_ERR_OPERATIONS_ERROR;
751                         }
752                 }
753                 if (temp->class->sysposssup) {
754                         ret = schema_merge_class_list(sctx, &sctx->sup_list, temp->class->sysposssup);
755                         if (ret != LDB_SUCCESS) {
756                                 return LDB_ERR_OPERATIONS_ERROR;
757                         }
758                 }
759                 if (temp->class->posssup) {
760                         ret = schema_merge_class_list(sctx, &sctx->sup_list, temp->class->posssup);
761                         if (ret != LDB_SUCCESS) {
762                                 return LDB_ERR_OPERATIONS_ERROR;
763                         }
764                 }
765                 temp = temp->next;
766         }
767
768         /* complete sup_list with material from the aux classes */
769         for (i = 0; sctx->aux_list && sctx->aux_list[i]; i++) {
770                 if (sctx->aux_list[i]->sysposssup) {
771                         ret = schema_merge_class_list(sctx, &sctx->sup_list, sctx->aux_list[i]->sysposssup);
772                         if (ret != LDB_SUCCESS) {
773                                 return LDB_ERR_OPERATIONS_ERROR;
774                         }
775                 }
776                 if (sctx->aux_list[i]->posssup) {
777                         ret = schema_merge_class_list(sctx, &sctx->sup_list, sctx->aux_list[i]->posssup);
778                         if (ret != LDB_SUCCESS) {
779                                 return LDB_ERR_OPERATIONS_ERROR;
780                         }
781                 }
782         }
783
784         if (!sctx->sup_list) return LDB_ERR_NAMING_VIOLATION;
785
786         return LDB_SUCCESS;
787 }
788
789 static int schema_add_check_container_constraints(struct schema_context *sctx)
790 {
791         struct schema_class **parent_possinf = NULL;
792         struct schema_class **parent_classes;
793         struct schema_class_dlist *temp;
794         struct ldb_message_element *el;
795         int i, j, ret;
796
797         el = ldb_msg_find_element(sctx->parent_res->message, "objectClass");
798         if (!el) {
799                 /* what the .. */
800                 return LDB_ERR_OPERATIONS_ERROR;
801         }
802
803         parent_classes = talloc_array(sctx, struct schema_class *, el->num_values + 1);
804
805         for (i = 0; i < el->num_values; i++) {
806
807                 parent_classes[i] = schema_store_find(sctx->data->class_store, (const char *)el->values[i].data);
808                 if (!parent_classes[i]) { /* should not be possible */
809                         return LDB_ERR_OPERATIONS_ERROR;
810                 }
811
812                 if (parent_classes[i]->possinf) {
813                         ret = schema_merge_class_list(sctx, &parent_possinf, parent_classes[i]->possinf);
814                         if (ret != LDB_SUCCESS) {
815                                 return LDB_ERR_OPERATIONS_ERROR;
816                         }
817                 }
818
819                 /* check also embedded auxiliary classes possinf */
820                 for (j = 0; parent_classes[i]->sysaux && parent_classes[i]->sysaux[j]; j++) {
821                         if (parent_classes[i]->sysaux[j]->possinf) {
822                                 ret = schema_merge_class_list(sctx, &parent_possinf, parent_classes[i]->sysaux[j]->possinf);
823                                 if (ret != LDB_SUCCESS) {
824                                         return LDB_ERR_OPERATIONS_ERROR;
825                                 }
826                         }
827                 }
828                 for (j = 0; parent_classes[i]->aux && parent_classes[i]->aux[j]; j++) {
829                         if (parent_classes[i]->aux[j]->possinf) {
830                                 ret = schema_merge_class_list(sctx, &parent_possinf, parent_classes[i]->aux[j]->possinf);
831                                 if (ret != LDB_SUCCESS) {
832                                         return LDB_ERR_OPERATIONS_ERROR;
833                                 }
834                         }
835                 }
836         }
837
838         /* foreach parent objectclass,
839          *   check parent possible inferiors match all of the child objectclasses
840          *    and that
841          *   poss Superiors of the child objectclasses mathes one of the parent classes
842          */
843
844         temp = sctx->class_list->next; /* skip top it is special */
845         while (temp) {
846
847                 for (i = 0; parent_possinf[i]; i++) {
848                         if (temp->class == parent_possinf[i]) {
849                                 break;
850                         }
851                 }
852                 if (parent_possinf[i] == NULL) {
853                         /* class not found in possible inferiors */
854                         return LDB_ERR_NAMING_VIOLATION;
855                 }
856
857                 temp = temp->next;
858         }
859
860         for (i = 0; parent_classes[i]; i++) {
861                 for (j = 0; sctx->sup_list[j]; j++) {
862                         if (sctx->sup_list[j] == parent_classes[i]) {
863                                 break;
864                         }
865                 }
866                 if (sctx->sup_list[j]) { /* possible Superiors match one of the parent classes */
867                         return LDB_SUCCESS;
868                 }
869         }
870
871         /* no parent classes matched superiors */
872         return LDB_ERR_NAMING_VIOLATION;
873 }
874
875 static int schema_add_build_down_req(struct schema_context *sctx)
876 {
877         struct schema_class_dlist *temp;
878         struct ldb_message *msg;
879         int ret;
880
881         sctx->down_req = talloc(sctx, struct ldb_request);
882         if (!sctx->down_req) {
883                 ldb_set_errstring(sctx->module->ldb, "Out of memory!");
884                 return LDB_ERR_OPERATIONS_ERROR;
885         }
886
887         *(sctx->down_req) = *(sctx->orig_req); /* copy the request */
888         msg = ldb_msg_copy_shallow(sctx->down_req, sctx->orig_req->op.add.message);
889         if (!msg) {
890                 ldb_set_errstring(sctx->module->ldb, "Out of memory!");
891                 return LDB_ERR_OPERATIONS_ERROR;
892         }
893
894         /* rebuild the objectclass list */
895         ldb_msg_remove_attr(msg, "objectClass");
896         ret = ldb_msg_add_empty(msg, "objectClass", 0, NULL);
897         if (ret != LDB_SUCCESS) {
898                 return ret;
899         }
900
901         /* Add the complete list of classes back to the message */
902         for (temp = sctx->class_list; temp; temp = temp->next) {
903                 ret = ldb_msg_add_string(msg, "objectClass", temp->class->name);
904                 if (ret != LDB_SUCCESS) {
905                         return ret;
906                 }
907         }
908
909         /* objectCategory can be set only by the system */
910         if (ldb_msg_find_element(msg, "objectCategory")) {
911                 return LDB_ERR_CONSTRAINT_VIOLATION;
912         }
913
914         /* the OC is mandatory, every class defines it */
915         /* use the one defined in the structural class that defines the object */
916         for (temp = sctx->class_list->next; temp; temp = temp->next) {
917                 if (!temp->next) break;
918                 if (temp->next->role != SCHEMA_CT_STRUCTURAL) break;
919         }
920 /*      oc = talloc_strdup(msg, temp->class->defobjcat);
921         ret = ldb_msg_add_string(msg, "objectCategory", oc);
922 */
923         sctx->down_req->op.add.message = msg;
924
925         return LDB_SUCCESS;
926 }
927
928 static int schema_check_attributes_syntax(struct schema_context *sctx)
929 {
930         struct ldb_message *msg;
931         struct schema_attribute *attr;
932         int i, ret;
933
934         msg = sctx->orig_req->op.add.message;
935         for (i = 0; i < msg->num_elements; i++) {
936                 attr = schema_store_find(sctx->data->attrs_store, msg->elements[i].name);
937                 if (attr == NULL) {
938                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
939                 }
940                 ret = schema_validate(sctx->module->ldb, &msg->elements[i], attr->syntax, attr->single, attr->min, attr->max);
941                 if (ret != LDB_SUCCESS) {
942                         return ret;
943                 }
944         }
945
946         return LDB_SUCCESS;
947 }
948
949 static int schema_add_continue(struct ldb_handle *h)
950 {
951         struct schema_context *sctx;
952         int ret;
953
954         sctx = talloc_get_type(h->private_data, struct schema_context);
955
956         switch (sctx->step) {
957         case SC_INIT:
958
959                 /* First of all check that a parent exists for this entry */
960                 ret = schema_add_build_parent_req(sctx);
961                 if (ret != LDB_SUCCESS) {
962                         break;
963                 }
964
965                 sctx->step = SC_ADD_CHECK_PARENT;
966                 return ldb_next_request(sctx->module, sctx->parent_req);
967
968         case SC_ADD_CHECK_PARENT:
969
970                 /* parent search done, check result and go on */
971                 if (sctx->parent_res == NULL) {
972                         /* we must have a parent */
973                         ret = LDB_ERR_NO_SUCH_OBJECT;
974                         break;
975                 }
976
977                 /* Check objectclasses are ok */
978                 ret = schema_add_build_objectclass_list(sctx);
979                 if (ret != LDB_SUCCESS) {
980                         break;
981                 }
982
983                 /* check the parent is of the right type for this object */
984                 ret = schema_add_check_container_constraints(sctx);
985                 if (ret != LDB_SUCCESS) {
986                         break;
987                 }
988
989                 /* check attributes syntax */
990                 
991                 ret = schema_check_attributes_syntax(sctx);
992                 if (ret != LDB_SUCCESS) {
993                         break;
994                 }
995
996                 ret = schema_add_build_down_req(sctx);
997                 if (ret != LDB_SUCCESS) {
998                         break;
999                 }
1000                 sctx->step = SC_ADD_TEMP;
1001
1002                 return ldb_next_request(sctx->module, sctx->down_req);
1003
1004         default:
1005                 ret = LDB_ERR_OPERATIONS_ERROR;
1006                 break;
1007         }
1008
1009         /* this is reached only in case of error */
1010         /* FIXME: fire an async reply ? */
1011         h->status = ret;
1012         h->state = LDB_ASYNC_DONE;
1013         return ret;
1014 }
1015
1016 static int schema_add(struct ldb_module *module, struct ldb_request *req)
1017 {
1018         struct schema_context *sctx;
1019         struct ldb_handle *h;
1020
1021         if (ldb_dn_is_special(req->op.add.message->dn)) { /* do not manipulate our control entries */
1022                 return ldb_next_request(module, req);
1023         }
1024
1025         h = schema_init_handle(req, module, SC_ADD);
1026         if (!h) {
1027                 return LDB_ERR_OPERATIONS_ERROR;
1028         }
1029
1030         sctx = talloc_get_type(h->private_data, struct schema_context);
1031         sctx->orig_req->handle = h;
1032         return schema_add_continue(h);
1033 }
1034
1035
1036 static int schema_modify(struct ldb_module *module, struct ldb_request *req)
1037 {
1038         if (ldb_dn_is_special(req->op.mod.message->dn)) { /* do not manipulate our control entries */
1039                 return ldb_next_request(module, req);
1040         }
1041
1042         return ldb_next_request(module, req);   
1043 }
1044
1045 static int schema_delete(struct ldb_module *module, struct ldb_request *req)
1046 {
1047         if (ldb_dn_is_special(req->op.del.dn)) { /* do not manipulate our control entries */
1048                 return ldb_next_request(module, req);
1049         }
1050         
1051         /* First of all check no children exists for this entry */
1052
1053         return ldb_next_request(module, req);
1054 }
1055
1056 static int schema_rename(struct ldb_module *module, struct ldb_request *req)
1057 {
1058         if (ldb_dn_is_special(req->op.rename.olddn) &&
1059             ldb_dn_is_special(req->op.rename.newdn)) { /* do not manipulate our control entries */
1060                 return ldb_next_request(module, req);
1061         }
1062
1063         return ldb_next_request(module, req);
1064 }
1065
1066 static int schema_wait_loop(struct ldb_handle *handle) {
1067         struct schema_context *sctx;
1068         int ret;
1069     
1070         if (!handle || !handle->private_data) {
1071                 return LDB_ERR_OPERATIONS_ERROR;
1072         }
1073
1074         if (handle->state == LDB_ASYNC_DONE) {
1075                 return handle->status;
1076         }
1077
1078         handle->state = LDB_ASYNC_PENDING;
1079         handle->status = LDB_SUCCESS;
1080
1081         sctx = talloc_get_type(handle->private_data, struct schema_context);
1082
1083         switch (sctx->step) {
1084         case SC_ADD_CHECK_PARENT:
1085                 ret = ldb_wait(sctx->parent_req->handle, LDB_WAIT_NONE);
1086
1087                 if (ret != LDB_SUCCESS) {
1088                         handle->status = ret;
1089                         goto done;
1090                 }
1091                 if (sctx->parent_req->handle->status != LDB_SUCCESS) {
1092                         handle->status = sctx->parent_req->handle->status;
1093                         goto done;
1094                 }
1095
1096                 if (sctx->parent_req->handle->state != LDB_ASYNC_DONE) {
1097                         return LDB_SUCCESS;
1098                 }
1099
1100                 return schema_add_continue(handle);
1101
1102         case SC_ADD_TEMP:
1103                 ret = ldb_wait(sctx->down_req->handle, LDB_WAIT_NONE);
1104
1105                 if (ret != LDB_SUCCESS) {
1106                         handle->status = ret;
1107                         goto done;
1108                 }
1109                 if (sctx->down_req->handle->status != LDB_SUCCESS) {
1110                         handle->status = sctx->down_req->handle->status;
1111                         goto done;
1112                 }
1113
1114                 if (sctx->down_req->handle->state != LDB_ASYNC_DONE) {
1115                         return LDB_SUCCESS;
1116                 }
1117
1118                 break;
1119
1120         default:
1121                 ret = LDB_ERR_OPERATIONS_ERROR;
1122                 goto done;
1123         }
1124
1125         ret = LDB_SUCCESS;
1126
1127 done:
1128         handle->state = LDB_ASYNC_DONE;
1129         return ret;
1130 }
1131
1132 static int schema_wait_all(struct ldb_handle *handle) {
1133
1134         int ret;
1135
1136         while (handle->state != LDB_ASYNC_DONE) {
1137                 ret = schema_wait_loop(handle);
1138                 if (ret != LDB_SUCCESS) {
1139                         return ret;
1140                 }
1141         }
1142
1143         return handle->status;
1144 }
1145
1146 static int schema_wait(struct ldb_handle *handle, enum ldb_wait_type type)
1147 {
1148         if (type == LDB_WAIT_ALL) {
1149                 return schema_wait_all(handle);
1150         } else {
1151                 return schema_wait_loop(handle);
1152         }
1153 }
1154
1155 static int schema_init(struct ldb_module *module)
1156 {
1157         static const char *schema_attrs[] = { "schemaNamingContext", NULL };
1158         struct schema_private_data *data;
1159         struct ldb_result *res;
1160         int ret;
1161
1162         /* need to let the partition module to register first */
1163         ret = ldb_next_init(module);
1164         if (ret != LDB_SUCCESS) {
1165                 return ret;
1166         }
1167
1168         data = ldb_get_opaque(module->ldb, "schema_instance");
1169         if (data) {
1170                 module->private_data = data;
1171                 return LDB_SUCCESS;
1172         }
1173
1174         data = talloc_zero(module->ldb, struct schema_private_data);
1175         if (data == NULL) {
1176                 return LDB_ERR_OPERATIONS_ERROR;
1177         }
1178
1179         /* find the schema partition */
1180         ret = ldb_search(module->ldb,
1181                          ldb_dn_new(module, module->ldb, NULL),
1182                          LDB_SCOPE_BASE,
1183                          "(objectClass=*)",
1184                          schema_attrs,
1185                          &res);
1186
1187         if (res->count != 1) {
1188                 /* FIXME: return a clear error string */
1189                 talloc_free(data);
1190                 talloc_free(res);
1191                 return LDB_ERR_OPERATIONS_ERROR;
1192         }
1193
1194         data->schema_dn = ldb_msg_find_attr_as_dn(module->ldb, data, res->msgs[0], "schemaNamingContext");
1195         if (data->schema_dn == NULL) {
1196                 /* FIXME: return a clear error string */
1197                 talloc_free(data);
1198                 talloc_free(res);
1199                 return LDB_ERR_OPERATIONS_ERROR;
1200         }
1201
1202         talloc_free(res);
1203
1204         ret = schema_init_attrs(module, data);
1205         if (ret != LDB_SUCCESS) {
1206                 talloc_free(data);
1207                 return ret;
1208         }
1209
1210         ret = schema_init_classes(module, data);
1211         if (ret != LDB_SUCCESS) {
1212                 talloc_free(data);
1213                 return ret;
1214         }
1215
1216         module->private_data = data;
1217         ldb_set_opaque(module->ldb, "schema_instance", data);
1218
1219         return LDB_SUCCESS;
1220 }
1221
1222 _PUBLIC_ const struct ldb_module_ops ldb_schema_module_ops = {
1223         .name          = "schema",
1224         .init_context  = schema_init,
1225         .add           = schema_add,
1226         .modify        = schema_modify,
1227         .del           = schema_delete,
1228         .rename        = schema_rename,
1229         .wait          = schema_wait
1230 };