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