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