dbwrap: add enum dbwrap_req_state
[kai/samba-autobuild/.git] / lib / dbwrap / dbwrap_rbt.c
1 /*
2    Unix SMB/CIFS implementation.
3    Database interface wrapper around red-black trees
4    Copyright (C) Volker Lendecke 2007, 2008
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 #include "includes.h"
21 #include "dbwrap/dbwrap.h"
22 #include "dbwrap/dbwrap_private.h"
23 #include "dbwrap/dbwrap_rbt.h"
24 #include "../lib/util/rbtree.h"
25 #include "../lib/util/dlinklist.h"
26
27 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
28
29 struct db_rbt_ctx {
30         struct rb_root tree;
31         struct db_rbt_node *nodes;
32         size_t traverse_read;
33         struct db_rbt_node **traverse_nextp;
34 };
35
36 struct db_rbt_rec {
37         struct db_rbt_node *node;
38 };
39
40 /* The structure that ends up in the tree */
41
42 struct db_rbt_node {
43         struct rb_node rb_node;
44         size_t keysize, valuesize;
45         struct db_rbt_node *prev, *next;
46 };
47
48 /*
49  * Hide the ugly pointer calculations in a function
50  */
51
52 static struct db_rbt_node *db_rbt2node(struct rb_node *node)
53 {
54         return (struct db_rbt_node *)
55                 ((char *)node - offsetof(struct db_rbt_node, rb_node));
56 }
57
58 /*
59  * Compare two keys
60  */
61
62 static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
63 {
64         int res;
65
66         res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
67
68         if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
69                 return -1;
70         }
71         if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
72                 return 1;
73         }
74         return 0;
75 }
76
77 /*
78  * dissect a db_rbt_node into its implicit key and value parts
79  */
80
81 static void db_rbt_parse_node(struct db_rbt_node *node,
82                               TDB_DATA *key, TDB_DATA *value)
83 {
84         size_t key_offset, value_offset;
85
86         key_offset = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
87         key->dptr = ((uint8_t *)node) + key_offset;
88         key->dsize = node->keysize;
89
90         value_offset = DBWRAP_RBT_ALIGN(node->keysize);
91         value->dptr = key->dptr + value_offset;
92         value->dsize = node->valuesize;
93 }
94
95 static ssize_t db_rbt_reclen(size_t keylen, size_t valuelen)
96 {
97         size_t len, tmp;
98
99         len = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
100
101         tmp = DBWRAP_RBT_ALIGN(keylen);
102         if (tmp < keylen) {
103                 goto overflow;
104         }
105
106         len += tmp;
107         if (len < tmp) {
108                 goto overflow;
109         }
110
111         len += valuelen;
112         if (len < valuelen) {
113                 goto overflow;
114         }
115
116         return len;
117 overflow:
118         return -1;
119 }
120
121 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
122 {
123         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
124                 rec->db->private_data, struct db_rbt_ctx);
125         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
126         struct db_rbt_node *node;
127
128         struct rb_node ** p;
129         struct rb_node *parent = NULL;
130         struct db_rbt_node *parent_node = NULL;
131
132         ssize_t reclen;
133         TDB_DATA this_key, this_val;
134
135         if (db_ctx->traverse_read > 0) {
136                 return NT_STATUS_MEDIA_WRITE_PROTECTED;
137         }
138
139         if (rec_priv->node != NULL) {
140
141                 /*
142                  * The record was around previously
143                  */
144
145                 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
146
147                 SMB_ASSERT(this_key.dsize == rec->key.dsize);
148                 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
149                                   this_key.dsize) == 0);
150
151                 if (this_val.dsize >= data.dsize) {
152                         /*
153                          * The new value fits into the old space
154                          */
155                         memcpy(this_val.dptr, data.dptr, data.dsize);
156                         rec_priv->node->valuesize = data.dsize;
157                         return NT_STATUS_OK;
158                 }
159         }
160
161         reclen = db_rbt_reclen(rec->key.dsize, data.dsize);
162         if (reclen == -1) {
163                 return NT_STATUS_INSUFFICIENT_RESOURCES;
164         }
165
166         node = talloc_zero_size(db_ctx, reclen);
167         if (node == NULL) {
168                 return NT_STATUS_NO_MEMORY;
169         }
170
171         if (rec_priv->node != NULL) {
172                 if (db_ctx->traverse_nextp != NULL) {
173                         if (*db_ctx->traverse_nextp == rec_priv->node) {
174                                 *db_ctx->traverse_nextp = node;
175                         }
176                 }
177
178                 /*
179                  * We need to delete the key from the tree and start fresh,
180                  * there's not enough space in the existing record
181                  */
182
183                 rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
184                 DLIST_REMOVE(db_ctx->nodes, rec_priv->node);
185
186                 /*
187                  * Keep the existing node around for a while: If the record
188                  * existed before, we reference the key data in there.
189                  */
190         }
191
192         node->keysize = rec->key.dsize;
193         node->valuesize = data.dsize;
194
195         db_rbt_parse_node(node, &this_key, &this_val);
196
197         memcpy(this_key.dptr, rec->key.dptr, node->keysize);
198         TALLOC_FREE(rec_priv->node);
199         rec_priv->node = node;
200
201         memcpy(this_val.dptr, data.dptr, node->valuesize);
202
203         parent = NULL;
204         p = &db_ctx->tree.rb_node;
205
206         while (*p) {
207                 struct db_rbt_node *r;
208                 TDB_DATA search_key, search_val;
209                 int res;
210
211                 r = db_rbt2node(*p);
212
213                 parent = (*p);
214                 parent_node = r;
215
216                 db_rbt_parse_node(r, &search_key, &search_val);
217
218                 res = db_rbt_compare(this_key, search_key);
219
220                 if (res == -1) {
221                         p = &(*p)->rb_left;
222                 }
223                 else if (res == 1) {
224                         p = &(*p)->rb_right;
225                 }
226                 else {
227                         smb_panic("someone messed with the tree");
228                 }
229         }
230
231         rb_link_node(&node->rb_node, parent, p);
232         DLIST_ADD_AFTER(db_ctx->nodes, node, parent_node);
233         rb_insert_color(&node->rb_node, &db_ctx->tree);
234
235         return NT_STATUS_OK;
236 }
237
238 static NTSTATUS db_rbt_delete(struct db_record *rec)
239 {
240         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
241                 rec->db->private_data, struct db_rbt_ctx);
242         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
243
244         if (db_ctx->traverse_read > 0) {
245                 return NT_STATUS_MEDIA_WRITE_PROTECTED;
246         }
247
248         if (rec_priv->node == NULL) {
249                 return NT_STATUS_OK;
250         }
251
252         if (db_ctx->traverse_nextp != NULL) {
253                 if (*db_ctx->traverse_nextp == rec_priv->node) {
254                         *db_ctx->traverse_nextp = rec_priv->node->next;
255                 }
256         }
257
258         rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
259         DLIST_REMOVE(db_ctx->nodes, rec_priv->node);
260         TALLOC_FREE(rec_priv->node);
261
262         return NT_STATUS_OK;
263 }
264
265 struct db_rbt_search_result {
266         TDB_DATA key;
267         TDB_DATA val;
268         struct db_rbt_node* node;
269 };
270
271 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
272                                    struct db_rbt_search_result *result)
273 {
274         struct db_rbt_ctx *ctx = talloc_get_type_abort(
275                 db->private_data, struct db_rbt_ctx);
276
277         struct rb_node *n;
278         bool found = false;
279         struct db_rbt_node *r = NULL;
280         TDB_DATA search_key = { 0 };
281         TDB_DATA search_val = { 0 };
282
283         n = ctx->tree.rb_node;
284
285         while (n != NULL) {
286                 int res;
287
288                 r = db_rbt2node(n);
289
290                 db_rbt_parse_node(r, &search_key, &search_val);
291
292                 res = db_rbt_compare(key, search_key);
293
294                 if (res == -1) {
295                         n = n->rb_left;
296                 }
297                 else if (res == 1) {
298                         n = n->rb_right;
299                 }
300                 else {
301                         found = true;
302                         break;
303                 }
304         }
305         if (result != NULL) {
306                 if (found) {
307                         result->key = search_key;
308                         result->val = search_val;
309                         result->node = r;
310                 } else {
311                         ZERO_STRUCT(*result);
312                 }
313         }
314         return found;
315 }
316
317 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
318                                              TALLOC_CTX *mem_ctx,
319                                              TDB_DATA key)
320 {
321         struct db_rbt_rec *rec_priv;
322         struct db_record *result;
323         size_t size;
324         bool found;
325         struct db_rbt_search_result res;
326
327         found = db_rbt_search_internal(db_ctx, key, &res);
328
329         /*
330          * In this low-level routine, play tricks to reduce the number of
331          * tallocs to one. Not recommened for general use, but here it pays
332          * off.
333          */
334
335         size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
336                 + sizeof(struct db_rbt_rec);
337
338         if (!found) {
339                 /*
340                  * We need to keep the key around for later store
341                  */
342                 size += key.dsize;
343         }
344
345         result = (struct db_record *)talloc_size(mem_ctx, size);
346         if (result == NULL) {
347                 return NULL;
348         }
349
350         rec_priv = (struct db_rbt_rec *)
351                 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
352
353         result->store = db_rbt_store;
354         result->delete_rec = db_rbt_delete;
355         result->private_data = rec_priv;
356
357         rec_priv->node = res.node;
358         result->value  = res.val;
359
360         if (found) {
361                 result->key = res.key;
362         }
363         else {
364                 result->key.dptr = (uint8_t *)
365                         ((char *)rec_priv + sizeof(*rec_priv));
366                 result->key.dsize = key.dsize;
367                 memcpy(result->key.dptr, key.dptr, key.dsize);
368         }
369
370         return result;
371 }
372
373 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
374 {
375         return db_rbt_search_internal(db, key, NULL);
376 }
377
378 static int db_rbt_wipe(struct db_context *db)
379 {
380         struct db_rbt_ctx *old_ctx = talloc_get_type_abort(
381                 db->private_data, struct db_rbt_ctx);
382         struct db_rbt_ctx *new_ctx = talloc_zero(db, struct db_rbt_ctx);
383         if (new_ctx == NULL) {
384                 return -1;
385         }
386         db->private_data = new_ctx;
387         talloc_free(old_ctx);
388         return 0;
389 }
390
391 static NTSTATUS db_rbt_parse_record(struct db_context *db, TDB_DATA key,
392                                     void (*parser)(TDB_DATA key, TDB_DATA data,
393                                                    void *private_data),
394                                     void *private_data)
395 {
396         struct db_rbt_search_result res;
397         bool found = db_rbt_search_internal(db, key, &res);
398
399         if (!found) {
400                 return NT_STATUS_NOT_FOUND;
401         }
402         parser(res.key, res.val, private_data);
403         return NT_STATUS_OK;
404 }
405
406 static int db_rbt_traverse_internal(struct db_context *db,
407                                     int (*f)(struct db_record *db,
408                                              void *private_data),
409                                     void *private_data, uint32_t* count,
410                                     bool rw)
411 {
412         struct db_rbt_ctx *ctx = talloc_get_type_abort(
413                 db->private_data, struct db_rbt_ctx);
414         struct db_rbt_node *cur = NULL;
415         struct db_rbt_node *next = NULL;
416         int ret;
417
418         for (cur = ctx->nodes; cur != NULL; cur = next) {
419                 struct db_record rec;
420                 struct db_rbt_rec rec_priv;
421
422                 rec_priv.node = cur;
423                 next = rec_priv.node->next;
424
425                 ZERO_STRUCT(rec);
426                 rec.db = db;
427                 rec.private_data = &rec_priv;
428                 rec.store = db_rbt_store;
429                 rec.delete_rec = db_rbt_delete;
430                 db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
431
432                 if (rw) {
433                         ctx->traverse_nextp = &next;
434                 }
435                 ret = f(&rec, private_data);
436                 (*count) ++;
437                 if (rw) {
438                         ctx->traverse_nextp = NULL;
439                 }
440                 if (ret != 0) {
441                         return ret;
442                 }
443                 if (rec_priv.node != NULL) {
444                         next = rec_priv.node->next;
445                 }
446         }
447
448         return 0;
449 }
450
451 static int db_rbt_traverse_read(struct db_context *db,
452                                 int (*f)(struct db_record *db,
453                                          void *private_data),
454                                 void *private_data)
455 {
456         struct db_rbt_ctx *ctx = talloc_get_type_abort(
457                 db->private_data, struct db_rbt_ctx);
458         uint32_t count = 0;
459         int ret;
460
461         ctx->traverse_read++;
462         ret = db_rbt_traverse_internal(db,
463                                        f, private_data, &count,
464                                        false /* rw */);
465         ctx->traverse_read--;
466         if (ret != 0) {
467                 return -1;
468         }
469         if (count > INT_MAX) {
470                 return -1;
471         }
472         return count;
473 }
474
475 static int db_rbt_traverse(struct db_context *db,
476                            int (*f)(struct db_record *db,
477                                     void *private_data),
478                            void *private_data)
479 {
480         struct db_rbt_ctx *ctx = talloc_get_type_abort(
481                 db->private_data, struct db_rbt_ctx);
482         uint32_t count = 0;
483         int ret;
484
485         if (ctx->traverse_nextp != NULL) {
486                 return -1;
487         };
488
489         if (ctx->traverse_read > 0) {
490                 return db_rbt_traverse_read(db, f, private_data);
491         }
492
493         ret = db_rbt_traverse_internal(db,
494                                        f, private_data, &count,
495                                        true /* rw */);
496         if (ret != 0) {
497                 return -1;
498         }
499         if (count > INT_MAX) {
500                 return -1;
501         }
502         return count;
503 }
504
505 static int db_rbt_get_seqnum(struct db_context *db)
506 {
507         return 0;
508 }
509
510 static int db_rbt_trans_dummy(struct db_context *db)
511 {
512         /*
513          * Transactions are pretty pointless in-memory, just return success.
514          */
515         return 0;
516 }
517
518 static size_t db_rbt_id(struct db_context *db, uint8_t *id, size_t idlen)
519 {
520         if (idlen >= sizeof(struct db_context *)) {
521                 memcpy(id, &db, sizeof(struct db_context *));
522         }
523         return sizeof(struct db_context *);
524 }
525
526 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
527 {
528         struct db_context *result;
529
530         result = talloc_zero(mem_ctx, struct db_context);
531
532         if (result == NULL) {
533                 return NULL;
534         }
535
536         result->private_data = talloc_zero(result, struct db_rbt_ctx);
537
538         if (result->private_data == NULL) {
539                 TALLOC_FREE(result);
540                 return NULL;
541         }
542
543         result->fetch_locked = db_rbt_fetch_locked;
544         result->traverse = db_rbt_traverse;
545         result->traverse_read = db_rbt_traverse_read;
546         result->get_seqnum = db_rbt_get_seqnum;
547         result->transaction_start = db_rbt_trans_dummy;
548         result->transaction_commit = db_rbt_trans_dummy;
549         result->transaction_cancel = db_rbt_trans_dummy;
550         result->exists = db_rbt_exists;
551         result->wipe = db_rbt_wipe;
552         result->parse_record = db_rbt_parse_record;
553         result->id = db_rbt_id;
554         result->name = "dbwrap rbt";
555
556         return result;
557 }