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