r4281: fixed an ldb indexing bug in ldb found by volker.
[jelmer/samba4-debian.git] / source / lib / ldb / ldb_tdb / ldb_tdb.c
1 /* 
2    ldb database library
3
4    Copyright (C) Andrew Tridgell  2004
5    Copyright (C) Stefan Metzmacher  2004
6    
7
8      ** NOTE! The following LGPL license applies to the ldb
9      ** library. This does NOT imply that all of Samba is released
10      ** under the LGPL
11    
12    This library is free software; you can redistribute it and/or
13    modify it under the terms of the GNU Lesser General Public
14    License as published by the Free Software Foundation; either
15    version 2 of the License, or (at your option) any later version.
16
17    This library is distributed in the hope that it will be useful,
18    but WITHOUT ANY WARRANTY; without even the implied warranty of
19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
20    Lesser General Public License for more details.
21
22    You should have received a copy of the GNU Lesser General Public
23    License along with this library; if not, write to the Free Software
24    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
25 */
26
27 /*
28  *  Name: ldb
29  *
30  *  Component: ldb tdb backend
31  *
32  *  Description: core functions for tdb backend
33  *
34  *  Author: Andrew Tridgell
35  *  Author: Stefan Metzmacher
36  */
37
38 #include "includes.h"
39 #include "ldb/include/ldb.h"
40 #include "ldb/include/ldb_private.h"
41 #include "ldb/ldb_tdb/ldb_tdb.h"
42
43 #define LDBLOCK "INT_LDBLOCK"
44
45 /*
46   form a TDB_DATA for a record key
47   caller frees
48
49   note that the key for a record can depend on whether the 
50   dn refers to a case sensitive index record or not
51 */
52 struct TDB_DATA ltdb_key(struct ldb_module *module, const char *dn)
53 {
54         struct ldb_context *ldb = module->ldb;
55         TDB_DATA key;
56         char *key_str = NULL;
57         char *dn_folded = NULL;
58         const char *prefix = LTDB_INDEX ":";
59         const char *s;
60         int flags;
61
62         /*
63           most DNs are case insensitive. The exception is index DNs for
64           case sensitive attributes
65
66           there are 3 cases dealt with in this code:
67
68           1) if the dn doesn't start with @INDEX: then uppercase whole dn
69           2) if the dn starts with @INDEX:attr and 'attr' is a case insensitive
70              attribute then uppercase whole dn
71           3) if the dn starts with @INDEX:attr and 'attr' is a case sensitive
72              attribute then uppercase up to the value of the attribute, but 
73              not the value itself
74         */
75         if (strncmp(dn, prefix, strlen(prefix)) == 0 &&
76             (s = strchr(dn+strlen(prefix), ':'))) {
77                 char *attr_name, *attr_name_folded;
78                 attr_name = ldb_strndup(ldb, dn+strlen(prefix), (s-(dn+strlen(prefix))));
79                 if (!attr_name) {
80                         goto failed;
81                 }
82                 flags = ltdb_attribute_flags(module, attr_name);
83                 
84                 if (flags & LTDB_FLAG_CASE_INSENSITIVE) {
85                         dn_folded = ldb_casefold(ldb, dn);
86                 } else {
87                         attr_name_folded = ldb_casefold(ldb, attr_name);
88                         if (!attr_name_folded) {
89                                 goto failed;
90                         }
91                         ldb_asprintf(ldb, &dn_folded, "%s:%s:%s",
92                                  prefix, attr_name_folded,
93                                  s+1);
94                         ldb_free(ldb, attr_name_folded);
95                 }
96                 ldb_free(ldb, attr_name);
97         } else {
98                 dn_folded = ldb_casefold(ldb, dn);
99         }
100
101         if (!dn_folded) {
102                 goto failed;
103         }
104
105         ldb_asprintf(ldb, &key_str, "DN=%s", dn_folded);
106         ldb_free(ldb, dn_folded);
107
108         if (!key_str) {
109                 goto failed;
110         }
111
112         key.dptr = key_str;
113         key.dsize = strlen(key_str)+1;
114
115         return key;
116
117 failed:
118         errno = ENOMEM;
119         key.dptr = NULL;
120         key.dsize = 0;
121         return key;
122 }
123
124 /*
125   lock the database for write - currently a single lock is used
126 */
127 static int ltdb_lock(struct ldb_module *module, const char *lockname)
128 {
129         struct ldb_context *ldb = module->ldb;
130         struct ltdb_private *ltdb = module->private_data;
131         TDB_DATA key;
132         int ret;
133
134         if (lockname == NULL) {
135                 return -1;
136         }
137
138         key = ltdb_key(module, lockname);
139         if (!key.dptr) {
140                 return -1;
141         }
142
143         ret = tdb_chainlock(ltdb->tdb, key);
144
145         ldb_free(ldb, key.dptr);
146
147         return ret;
148 }
149
150 /*
151   unlock the database after a ltdb_lock()
152 */
153 static int ltdb_unlock(struct ldb_module *module, const char *lockname)
154 {
155         struct ldb_context *ldb = module->ldb;
156         struct ltdb_private *ltdb = module->private_data;
157         TDB_DATA key;
158
159         if (lockname == NULL) {
160                 return -1;
161         }
162
163         key = ltdb_key(module, lockname);
164         if (!key.dptr) {
165                 return -1;
166         }
167
168         tdb_chainunlock(ltdb->tdb, key);
169
170         ldb_free(ldb, key.dptr);
171
172         return 0;
173 }
174
175
176 /*
177   we've made a modification to a dn - possibly reindex and 
178   update sequence number
179 */
180 static int ltdb_modified(struct ldb_module *module, const char *dn)
181 {
182         int ret = 0;
183
184         if (strcmp(dn, LTDB_INDEXLIST) == 0 ||
185             strcmp(dn, LTDB_ATTRIBUTES) == 0) {
186                 ret = ltdb_reindex(module);
187         }
188
189         if (ret == 0 &&
190             strcmp(dn, LTDB_BASEINFO) != 0) {
191                 ret = ltdb_increase_sequence_number(module);
192         }
193
194         return ret;
195 }
196
197 /*
198   store a record into the db
199 */
200 int ltdb_store(struct ldb_module *module, const struct ldb_message *msg, int flgs)
201 {
202         struct ldb_context *ldb = module->ldb;
203         struct ltdb_private *ltdb = module->private_data;
204         TDB_DATA tdb_key, tdb_data;
205         int ret;
206
207         tdb_key = ltdb_key(module, msg->dn);
208         if (!tdb_key.dptr) {
209                 return -1;
210         }
211
212         ret = ltdb_pack_data(module, msg, &tdb_data);
213         if (ret == -1) {
214                 ldb_free(ldb, tdb_key.dptr);
215                 return -1;
216         }
217
218         ret = tdb_store(ltdb->tdb, tdb_key, tdb_data, flgs);
219         if (ret == -1) {
220                 goto done;
221         }
222         
223         ret = ltdb_index_add(module, msg);
224         if (ret == -1) {
225                 tdb_delete(ltdb->tdb, tdb_key);
226         }
227
228 done:
229         ldb_free(ldb, tdb_key.dptr);
230         ldb_free(ldb, tdb_data.dptr);
231
232         return ret;
233 }
234
235
236 /*
237   add a record to the database
238 */
239 static int ltdb_add(struct ldb_module *module, const struct ldb_message *msg)
240 {
241         struct ltdb_private *ltdb = module->private_data;
242         int ret;
243
244         ltdb->last_err_string = NULL;
245
246         if (ltdb_lock(module, LDBLOCK) != 0) {
247                 return -1;
248         }
249
250         if (ltdb_cache_load(module) != 0) {
251                 ltdb_unlock(module, LDBLOCK);
252                 return -1;
253         }
254         
255         ret = ltdb_store(module, msg, TDB_INSERT);
256
257         if (ret == 0) {
258                 ltdb_modified(module, msg->dn);
259         }
260
261         ltdb_unlock(module, LDBLOCK);
262         return ret;
263 }
264
265
266 /*
267   delete a record from the database, not updating indexes (used for deleting
268   index records)
269 */
270 int ltdb_delete_noindex(struct ldb_module *module, const char *dn)
271 {
272         struct ldb_context *ldb = module->ldb;
273         struct ltdb_private *ltdb = module->private_data;
274         TDB_DATA tdb_key;
275         int ret;
276
277         tdb_key = ltdb_key(module, dn);
278         if (!tdb_key.dptr) {
279                 return -1;
280         }
281
282         ret = tdb_delete(ltdb->tdb, tdb_key);
283         ldb_free(ldb, tdb_key.dptr);
284
285         return ret;
286 }
287
288 /*
289   delete a record from the database
290 */
291 static int ltdb_delete(struct ldb_module *module, const char *dn)
292 {
293         struct ltdb_private *ltdb = module->private_data;
294         int ret;
295         struct ldb_message msg;
296
297         ltdb->last_err_string = NULL;
298
299         if (ltdb_lock(module, LDBLOCK) != 0) {
300                 return -1;
301         }
302
303         if (ltdb_cache_load(module) != 0) {
304                 ltdb_unlock(module, LDBLOCK);
305                 return -1;
306         }
307
308         /* in case any attribute of the message was indexed, we need
309            to fetch the old record */
310         ret = ltdb_search_dn1(module, dn, &msg);
311         if (ret != 1) {
312                 /* not finding the old record is an error */
313                 goto failed;
314         }
315
316         ret = ltdb_delete_noindex(module, dn);
317         if (ret == -1) {
318                 ltdb_search_dn1_free(module, &msg);
319                 goto failed;
320         }
321
322         /* remove any indexed attributes */
323         ret = ltdb_index_del(module, &msg);
324
325         ltdb_search_dn1_free(module, &msg);
326
327         if (ret == 0) {
328                 ltdb_modified(module, dn);
329         }
330
331         ltdb_unlock(module, LDBLOCK);
332         return ret;
333
334 failed:
335         ltdb_unlock(module, LDBLOCK);
336         return -1;
337 }
338
339
340 /*
341   find an element by attribute name. At the moment this does a linear search, it should
342   be re-coded to use a binary search once all places that modify records guarantee
343   sorted order
344
345   return the index of the first matching element if found, otherwise -1
346 */
347 static int find_element(const struct ldb_message *msg, const char *name)
348 {
349         unsigned int i;
350         for (i=0;i<msg->num_elements;i++) {
351                 if (ldb_attr_cmp(msg->elements[i].name, name) == 0) {
352                         return i;
353                 }
354         }
355         return -1;
356 }
357
358
359 /*
360   add an element to an existing record. Assumes a elements array that we
361   can call re-alloc on, and assumed that we can re-use the data pointers from the 
362   passed in additional values. Use with care!
363
364   returns 0 on success, -1 on failure (and sets errno)
365 */
366 static int msg_add_element(struct ldb_context *ldb,
367                            struct ldb_message *msg, struct ldb_message_element *el)
368 {
369         struct ldb_message_element *e2;
370         unsigned int i;
371
372         e2 = ldb_realloc_p(ldb, msg->elements, struct ldb_message_element, 
373                        msg->num_elements+1);
374         if (!e2) {
375                 errno = ENOMEM;
376                 return -1;
377         }
378
379         msg->elements = e2;
380
381         e2 = &msg->elements[msg->num_elements];
382
383         e2->name = el->name;
384         e2->flags = el->flags;
385         e2->values = NULL;
386         if (el->num_values != 0) {
387                 e2->values = ldb_malloc_array_p(ldb, struct ldb_val, el->num_values);
388                 if (!e2->values) {
389                         errno = ENOMEM;
390                         return -1;
391                 }
392         }
393         for (i=0;i<el->num_values;i++) {
394                 e2->values[i] = el->values[i];
395         }
396         e2->num_values = el->num_values;
397
398         msg->num_elements++;
399
400         return 0;
401 }
402
403 /*
404   delete all elements having a specified attribute name
405 */
406 static int msg_delete_attribute(struct ldb_module *module,
407                                 struct ldb_context *ldb,
408                                 struct ldb_message *msg, const char *name)
409 {
410         unsigned int i, j, count=0;
411         struct ldb_message_element *el2;
412
413         el2 = ldb_malloc_array_p(ldb, struct ldb_message_element, msg->num_elements);
414         if (!el2) {
415                 errno = ENOMEM;
416                 return -1;
417         }
418
419         for (i=0;i<msg->num_elements;i++) {
420                 if (ldb_attr_cmp(msg->elements[i].name, name) != 0) {
421                         el2[count++] = msg->elements[i];
422                 } else {
423                         for (j=0;j<msg->elements[i].num_values;j++) {
424                                 ltdb_index_del_value(module, msg->dn, &msg->elements[i], j);
425                         }
426                         ldb_free(ldb, msg->elements[i].values);
427                 }
428         }
429
430         msg->num_elements = count;
431         ldb_free(ldb, msg->elements);
432         msg->elements = el2;
433
434         return 0;
435 }
436
437 /*
438   delete all elements matching an attribute name/value 
439
440   return 0 on success, -1 on failure
441 */
442 static int msg_delete_element(struct ldb_module *module,
443                               struct ldb_message *msg, 
444                               const char *name,
445                               const struct ldb_val *val)
446 {
447         struct ldb_context *ldb = module->ldb;
448         unsigned int i;
449         int found;
450         struct ldb_message_element *el;
451
452         found = find_element(msg, name);
453         if (found == -1) {
454                 return -1;
455         }
456
457         el = &msg->elements[found];
458
459         for (i=0;i<el->num_values;i++) {
460                 if (ltdb_val_equal(module, msg->elements[i].name, &el->values[i], val)) {
461                         if (i<el->num_values-1) {
462                                 memmove(&el->values[i], &el->values[i+1],
463                                         sizeof(el->values[i])*(el->num_values-(i+1)));
464                         }
465                         el->num_values--;
466                         if (el->num_values == 0) {
467                                 return msg_delete_attribute(module, ldb, msg, name);
468                         }
469                         return 0;
470                 }
471         }
472
473         return -1;
474 }
475
476
477 /*
478   modify a record - internal interface
479
480   yuck - this is O(n^2). Luckily n is usually small so we probably
481   get away with it, but if we ever have really large attribute lists 
482   then we'll need to look at this again
483 */
484 int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *msg)
485 {
486         struct ldb_context *ldb = module->ldb;
487         struct ltdb_private *ltdb = module->private_data;
488         TDB_DATA tdb_key, tdb_data;
489         struct ldb_message msg2;
490         unsigned i, j;
491         int ret;
492
493         tdb_key = ltdb_key(module, msg->dn);
494         if (!tdb_key.dptr) {
495                 return -1;
496         }
497
498         tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
499         if (!tdb_data.dptr) {
500                 ldb_free(ldb, tdb_key.dptr);
501                 return -1;
502         }
503
504         ret = ltdb_unpack_data(module, &tdb_data, &msg2);
505         if (ret == -1) {
506                 ldb_free(ldb, tdb_key.dptr);
507                 free(tdb_data.dptr);
508                 return -1;
509         }
510
511         if (!msg2.dn) {
512                 msg2.dn = msg->dn;
513         }
514
515         for (i=0;i<msg->num_elements;i++) {
516                 switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
517
518                 case LDB_FLAG_MOD_ADD:
519                         /* add this element to the message. fail if it
520                            already exists */
521                         ret = find_element(&msg2, msg->elements[i].name);
522                         if (ret != -1) {
523                                 for (j=0;j<msg->elements[i].num_values;j++) {
524                                         if (ldb_msg_find_val(&msg2.elements[ret], 
525                                                              &msg->elements[i].values[j])) {
526                                                 ltdb->last_err_string = "Type or value exists";
527                                                 goto failed;
528                                         }
529                                 }
530                         }
531                         if (msg_add_element(ldb, &msg2, &msg->elements[i]) != 0) {
532                                 goto failed;
533                         }
534                         break;
535
536                 case LDB_FLAG_MOD_REPLACE:
537                         /* replace all elements of this attribute name with the elements
538                            listed. The attribute not existing is not an error */
539                         msg_delete_attribute(module, ldb, &msg2, msg->elements[i].name);
540
541                         /* add the replacement element, if not empty */
542                         if (msg->elements[i].num_values != 0 &&
543                             msg_add_element(ldb, &msg2, &msg->elements[i]) != 0) {
544                                 goto failed;
545                         }
546                         break;
547
548                 case LDB_FLAG_MOD_DELETE:
549                         /* we could be being asked to delete all
550                            values or just some values */
551                         if (msg->elements[i].num_values == 0) {
552                                 if (msg_delete_attribute(module, ldb, &msg2, 
553                                                          msg->elements[i].name) != 0) {
554                                         ltdb->last_err_string = "No such attribute";
555                                         goto failed;
556                                 }
557                                 break;
558                         }
559                         for (j=0;j<msg->elements[i].num_values;j++) {
560                                 if (msg_delete_element(module,
561                                                        &msg2, 
562                                                        msg->elements[i].name,
563                                                        &msg->elements[i].values[j]) != 0) {
564                                         ltdb->last_err_string = "No such attribute";
565                                         goto failed;
566                                 }
567                                 if (ltdb_index_del_value(module, msg->dn, &msg->elements[i], j) != 0) {
568                                         goto failed;
569                                 }
570                         }
571                         break;
572                 }
573         }
574
575         /* we've made all the mods - save the modified record back into the database */
576         ret = ltdb_store(module, &msg2, TDB_MODIFY);
577
578         ldb_free(ldb, tdb_key.dptr);
579         free(tdb_data.dptr);
580         ltdb_unpack_data_free(module, &msg2);
581         return ret;
582
583 failed:
584         ldb_free(ldb, tdb_key.dptr);
585         free(tdb_data.dptr);
586         ltdb_unpack_data_free(module, &msg2);
587         return -1;
588 }
589
590 /*
591   modify a record
592 */
593 static int ltdb_modify(struct ldb_module *module, const struct ldb_message *msg)
594 {
595         struct ltdb_private *ltdb = module->private_data;
596         int ret;
597
598         ltdb->last_err_string = NULL;
599
600         if (ltdb_lock(module, LDBLOCK) != 0) {
601                 return -1;
602         }
603
604         if (ltdb_cache_load(module) != 0) {
605                 ltdb_unlock(module, LDBLOCK);
606                 return -1;
607         }
608
609         ret = ltdb_modify_internal(module, msg);
610
611         if (ret == 0) {
612                 ltdb_modified(module, msg->dn);
613         }
614
615         ltdb_unlock(module, LDBLOCK);
616
617         return ret;
618 }
619
620 /*
621   rename a record
622 */
623 static int ltdb_rename(struct ldb_module *module, const char *olddn, const char *newdn)
624 {
625         struct ldb_context *ldb = module->ldb;
626         struct ltdb_private *ltdb = module->private_data;
627         int ret;
628         struct ldb_message msg;
629         const char *error_str;
630
631         ltdb->last_err_string = NULL;
632
633         if (ltdb_lock(module, LDBLOCK) != 0) {
634                 return -1;
635         }
636
637         /* in case any attribute of the message was indexed, we need
638            to fetch the old record */
639         ret = ltdb_search_dn1(module, olddn, &msg);
640         if (ret != 1) {
641                 /* not finding the old record is an error */
642                 goto failed;
643         }
644
645         msg.dn = ldb_strdup(ldb,newdn);
646         if (!msg.dn) {
647                 ltdb_search_dn1_free(module, &msg);
648                 goto failed;
649         }
650
651         ret = ltdb_add(module, &msg);
652         if (ret == -1) {
653                 ldb_free(ldb, msg.dn);
654                 ltdb_search_dn1_free(module, &msg);
655                 goto failed;
656         }
657         ldb_free(ldb, msg.dn);
658         ltdb_search_dn1_free(module, &msg);
659
660         ret = ltdb_delete(module, olddn);
661         error_str = ltdb->last_err_string;
662         if (ret == -1) {
663                 ltdb_delete(module, newdn);
664         }
665
666         ltdb->last_err_string = error_str;
667
668         ltdb_unlock(module, LDBLOCK);
669
670         return ret;
671 failed:
672         ltdb_unlock(module, LDBLOCK);
673         return -1;
674 }
675
676 /*
677   close database
678 */
679 static int ltdb_close(struct ldb_module *module)
680 {
681         struct ldb_context *ldb = module->ldb;
682         struct ltdb_private *ltdb = module->private_data;
683         int ret;
684
685         ltdb->last_err_string = NULL;
686
687         ltdb_cache_free(module);
688         ldb_set_alloc(ldb, NULL, NULL);
689
690         ret = tdb_close(ltdb->tdb);
691         ldb_free(ldb, ltdb);
692         free(ldb);
693         return ret;
694 }
695                       
696
697 /*
698   return extended error information
699 */
700 static const char *ltdb_errstring(struct ldb_module *module)
701 {
702         struct ltdb_private *ltdb = module->private_data;
703         if (ltdb->last_err_string) {
704                 return ltdb->last_err_string;
705         }
706         return tdb_errorstr(ltdb->tdb);
707 }
708
709
710 static const struct ldb_module_ops ltdb_ops = {
711         "tdb",
712         ltdb_close, 
713         ltdb_search,
714         ltdb_search_free,
715         ltdb_add,
716         ltdb_modify,
717         ltdb_delete,
718         ltdb_rename,
719         ltdb_lock,
720         ltdb_unlock,
721         ltdb_errstring,
722         ltdb_cache_free
723 };
724
725
726 /*
727   connect to the database
728 */
729 struct ldb_context *ltdb_connect(const char *url, 
730                                  unsigned int flags, 
731                                  const char *options[])
732 {
733         const char *path;
734         int tdb_flags, open_flags;
735         struct ltdb_private *ltdb;
736         TDB_CONTEXT *tdb;
737         struct ldb_context *ldb;
738
739         ldb = calloc(1, sizeof(struct ldb_context));
740         if (!ldb) {
741                 errno = ENOMEM;
742                 return NULL;
743         }
744
745         /* parse the url */
746         if (strchr(url, ':')) {
747                 if (strncmp(url, "tdb://", 6) != 0) {
748                         errno = EINVAL;
749                         return NULL;
750                 }
751                 path = url+6;
752         } else {
753                 path = url;
754         }
755
756         tdb_flags = TDB_DEFAULT;
757
758         if (flags & LDB_FLG_RDONLY) {
759                 open_flags = O_RDONLY;
760         } else {
761                 open_flags = O_CREAT | O_RDWR;
762         }
763
764         /* note that we use quite a large default hash size */
765         tdb = tdb_open(path, 10000, tdb_flags, open_flags, 0666);
766         if (!tdb) {
767                 free(ldb);
768                 return NULL;
769         }
770
771         ltdb = ldb_malloc_p(ldb, struct ltdb_private);
772         if (!ltdb) {
773                 tdb_close(tdb);
774                 free(ldb);
775                 errno = ENOMEM;
776                 return NULL;
777         }
778
779         ltdb->tdb = tdb;
780         ltdb->sequence_number = 0;
781
782         memset(&ltdb->cache, 0, sizeof(ltdb->cache));
783
784         ldb->modules = ldb_malloc_p(ldb, struct ldb_module);
785         if (!ldb->modules) {
786                 tdb_close(tdb);
787                 free(ldb);
788                 errno = ENOMEM;
789                 return NULL;
790         }
791         ldb->modules->ldb = ldb;
792         ldb->modules->prev = ldb->modules->next = NULL;
793         ldb->modules->private_data = ltdb;
794         ldb->modules->ops = &ltdb_ops;
795
796         return ldb;
797 }