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 58609019 : static struct db_rbt_node *db_rbt2node(struct rb_node *node)
53 : {
54 58609019 : 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 58609019 : static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
63 : {
64 : int res;
65 :
66 58609019 : res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
67 :
68 58609019 : if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
69 24677386 : return -1;
70 : }
71 33931633 : if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
72 25109201 : return 1;
73 : }
74 8822432 : return 0;
75 : }
76 :
77 : /*
78 : * dissect a db_rbt_node into its implicit key and value parts
79 : */
80 :
81 60051043 : 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 60051043 : key_offset = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
87 60051043 : key->dptr = ((uint8_t *)node) + key_offset;
88 60051043 : key->dsize = node->keysize;
89 :
90 60051043 : value_offset = DBWRAP_RBT_ALIGN(node->keysize);
91 60051043 : value->dptr = key->dptr + value_offset;
92 60051043 : value->dsize = node->valuesize;
93 60051043 : }
94 :
95 1433950 : static ssize_t db_rbt_reclen(size_t keylen, size_t valuelen)
96 : {
97 : size_t len, tmp;
98 :
99 1433950 : len = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
100 :
101 1433950 : tmp = DBWRAP_RBT_ALIGN(keylen);
102 1433950 : if (tmp < keylen) {
103 0 : goto overflow;
104 : }
105 :
106 1433950 : len += tmp;
107 1433950 : if (len < tmp) {
108 0 : goto overflow;
109 : }
110 :
111 1433950 : len += valuelen;
112 1433950 : if (len < valuelen) {
113 0 : goto overflow;
114 : }
115 :
116 1433950 : return len;
117 0 : overflow:
118 0 : return -1;
119 : }
120 :
121 1433955 : static NTSTATUS db_rbt_storev(struct db_record *rec,
122 : const TDB_DATA *dbufs, int num_dbufs, int flag)
123 : {
124 1433955 : struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
125 : rec->db->private_data, struct db_rbt_ctx);
126 1433955 : 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 1433955 : struct rb_node *parent = NULL;
131 1433955 : struct db_rbt_node *parent_node = NULL;
132 :
133 : ssize_t reclen;
134 : TDB_DATA data, this_key, this_val;
135 1433955 : void *to_free = NULL;
136 :
137 1433955 : if (db_ctx->traverse_read > 0) {
138 0 : return NT_STATUS_MEDIA_WRITE_PROTECTED;
139 : }
140 :
141 1433955 : if ((flag == TDB_INSERT) && (rec_priv->node != NULL)) {
142 0 : return NT_STATUS_OBJECT_NAME_COLLISION;
143 : }
144 :
145 1433955 : if ((flag == TDB_MODIFY) && (rec_priv->node == NULL)) {
146 0 : return NT_STATUS_OBJECT_NAME_NOT_FOUND;
147 : }
148 :
149 1433955 : if (num_dbufs == 1) {
150 1433955 : 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 1433955 : 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 1433950 : reclen = db_rbt_reclen(rec->key.dsize, data.dsize);
183 1433950 : if (reclen == -1) {
184 0 : TALLOC_FREE(to_free);
185 0 : return NT_STATUS_INSUFFICIENT_RESOURCES;
186 : }
187 :
188 1433950 : node = talloc_zero_size(db_ctx, reclen);
189 1433950 : if (node == NULL) {
190 0 : TALLOC_FREE(to_free);
191 0 : return NT_STATUS_NO_MEMORY;
192 : }
193 :
194 1433950 : 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 1433950 : node->keysize = rec->key.dsize;
216 1433950 : node->valuesize = data.dsize;
217 :
218 1433950 : db_rbt_parse_node(node, &this_key, &this_val);
219 :
220 1433950 : memcpy(this_key.dptr, rec->key.dptr, node->keysize);
221 1433950 : TALLOC_FREE(rec_priv->node);
222 1433950 : rec_priv->node = node;
223 :
224 1433950 : if (node->valuesize > 0) {
225 389962 : memcpy(this_val.dptr, data.dptr, node->valuesize);
226 : }
227 :
228 1433950 : parent = NULL;
229 1433950 : p = &db_ctx->tree.rb_node;
230 :
231 15725758 : while (*p) {
232 : struct db_rbt_node *r;
233 : TDB_DATA search_key, search_val;
234 : int res;
235 :
236 13022508 : r = db_rbt2node(*p);
237 :
238 13022508 : parent = (*p);
239 13022508 : parent_node = r;
240 :
241 13022508 : db_rbt_parse_node(r, &search_key, &search_val);
242 :
243 13022508 : res = db_rbt_compare(this_key, search_key);
244 :
245 13022508 : if (res == -1) {
246 6457505 : p = &(*p)->rb_left;
247 : }
248 6565003 : else if (res == 1) {
249 6565003 : p = &(*p)->rb_right;
250 : }
251 : else {
252 0 : smb_panic("someone messed with the tree");
253 : }
254 : }
255 :
256 1433950 : rb_link_node(&node->rb_node, parent, p);
257 1433950 : DLIST_ADD_AFTER(db_ctx->nodes, node, parent_node);
258 1433950 : rb_insert_color(&node->rb_node, &db_ctx->tree);
259 :
260 1433950 : TALLOC_FREE(to_free);
261 :
262 1433950 : return NT_STATUS_OK;
263 : }
264 :
265 65885 : static NTSTATUS db_rbt_delete(struct db_record *rec)
266 : {
267 65885 : struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
268 : rec->db->private_data, struct db_rbt_ctx);
269 65885 : struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
270 :
271 65885 : if (db_ctx->traverse_read > 0) {
272 0 : return NT_STATUS_MEDIA_WRITE_PROTECTED;
273 : }
274 :
275 65885 : if (rec_priv->node == NULL) {
276 2078 : return NT_STATUS_OK;
277 : }
278 :
279 63807 : if (db_ctx->traverse_nextp != NULL) {
280 7985 : if (*db_ctx->traverse_nextp == rec_priv->node) {
281 0 : *db_ctx->traverse_nextp = rec_priv->node->next;
282 : }
283 : }
284 :
285 63807 : rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
286 63807 : DLIST_REMOVE(db_ctx->nodes, rec_priv->node);
287 63807 : TALLOC_FREE(rec_priv->node);
288 :
289 63807 : 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 12114995 : static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
299 : struct db_rbt_search_result *result)
300 : {
301 12114995 : struct db_rbt_ctx *ctx = talloc_get_type_abort(
302 : db->private_data, struct db_rbt_ctx);
303 :
304 : struct rb_node *n;
305 12114995 : bool found = false;
306 12114995 : struct db_rbt_node *r = NULL;
307 12114995 : TDB_DATA search_key = { 0 };
308 12114995 : TDB_DATA search_val = { 0 };
309 :
310 12114995 : n = ctx->tree.rb_node;
311 :
312 60296239 : while (n != NULL) {
313 : int res;
314 :
315 45586511 : r = db_rbt2node(n);
316 :
317 45586511 : db_rbt_parse_node(r, &search_key, &search_val);
318 :
319 45586511 : res = db_rbt_compare(key, search_key);
320 :
321 45586511 : if (res == -1) {
322 18219881 : n = n->rb_left;
323 : }
324 27366630 : else if (res == 1) {
325 18544198 : n = n->rb_right;
326 : }
327 : else {
328 8822432 : found = true;
329 8822432 : break;
330 : }
331 : }
332 12114995 : if (result != NULL) {
333 11343210 : if (found) {
334 8441552 : result->key = search_key;
335 8441552 : result->val = search_val;
336 8441552 : result->node = r;
337 : } else {
338 2901658 : ZERO_STRUCT(*result);
339 : }
340 : }
341 12114995 : return found;
342 : }
343 :
344 8378623 : 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 8378623 : 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 8378623 : size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
363 : + sizeof(struct db_rbt_rec);
364 :
365 8378623 : if (!found) {
366 : /*
367 : * We need to keep the key around for later store
368 : */
369 1436028 : size += key.dsize;
370 : }
371 :
372 8378623 : result = (struct db_record *)talloc_size(mem_ctx, size);
373 8378623 : if (result == NULL) {
374 0 : return NULL;
375 : }
376 :
377 8378623 : rec_priv = (struct db_rbt_rec *)
378 : ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
379 :
380 8378623 : result->storev = db_rbt_storev;
381 8378623 : result->delete_rec = db_rbt_delete;
382 8378623 : result->private_data = rec_priv;
383 :
384 8378623 : rec_priv->node = res.node;
385 8378623 : result->value = res.val;
386 8378623 : result->value_valid = true;
387 :
388 8378623 : if (found) {
389 6942595 : result->key = res.key;
390 : }
391 : else {
392 1436028 : result->key.dptr = (uint8_t *)
393 : ((char *)rec_priv + sizeof(*rec_priv));
394 1436028 : result->key.dsize = key.dsize;
395 1436028 : memcpy(result->key.dptr, key.dptr, key.dsize);
396 : }
397 :
398 8378623 : return result;
399 : }
400 :
401 771785 : static int db_rbt_exists(struct db_context *db, TDB_DATA key)
402 : {
403 771785 : 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 2964587 : 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 2964587 : bool found = db_rbt_search_internal(db, key, &res);
426 :
427 2964587 : if (!found) {
428 1465630 : return NT_STATUS_NOT_FOUND;
429 : }
430 1498957 : parser(res.key, res.val, private_data);
431 1498957 : return NT_STATUS_OK;
432 : }
433 :
434 15854 : 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 15854 : struct db_rbt_ctx *ctx = talloc_get_type_abort(
441 : db->private_data, struct db_rbt_ctx);
442 15854 : struct db_rbt_node *cur = NULL;
443 15854 : struct db_rbt_node *next = NULL;
444 : int ret;
445 :
446 23923 : for (cur = ctx->nodes; cur != NULL; cur = next) {
447 : struct db_record rec;
448 : struct db_rbt_rec rec_priv;
449 :
450 8069 : rec_priv.node = cur;
451 8069 : next = rec_priv.node->next;
452 :
453 8069 : ZERO_STRUCT(rec);
454 8069 : rec.db = db;
455 8069 : rec.private_data = &rec_priv;
456 8069 : rec.storev = db_rbt_storev;
457 8069 : rec.delete_rec = db_rbt_delete;
458 8069 : db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
459 8069 : rec.value_valid = true;
460 :
461 8069 : if (rw) {
462 8069 : ctx->traverse_nextp = &next;
463 : }
464 8069 : ret = f(&rec, private_data);
465 8069 : (*count) ++;
466 8069 : if (rw) {
467 8069 : ctx->traverse_nextp = NULL;
468 : }
469 8069 : if (ret != 0) {
470 0 : return ret;
471 : }
472 8069 : if (rec_priv.node != NULL) {
473 84 : next = rec_priv.node->next;
474 : }
475 : }
476 :
477 15854 : 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 15854 : 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 15854 : struct db_rbt_ctx *ctx = talloc_get_type_abort(
510 : db->private_data, struct db_rbt_ctx);
511 15854 : uint32_t count = 0;
512 : int ret;
513 :
514 15854 : if (ctx->traverse_nextp != NULL) {
515 0 : return -1;
516 : };
517 :
518 15854 : if (ctx->traverse_read > 0) {
519 0 : return db_rbt_traverse_read(db, f, private_data);
520 : }
521 :
522 15854 : ret = db_rbt_traverse_internal(db,
523 : f, private_data, &count,
524 : true /* rw */);
525 15854 : if (ret != 0) {
526 0 : return -1;
527 : }
528 15854 : if (count > INT_MAX) {
529 0 : return -1;
530 : }
531 15854 : 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 743540 : struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
556 : {
557 : struct db_context *result;
558 :
559 743540 : result = talloc_zero(mem_ctx, struct db_context);
560 :
561 743540 : if (result == NULL) {
562 0 : return NULL;
563 : }
564 :
565 743540 : result->private_data = talloc_zero(result, struct db_rbt_ctx);
566 :
567 743540 : if (result->private_data == NULL) {
568 0 : TALLOC_FREE(result);
569 0 : return NULL;
570 : }
571 :
572 743540 : result->fetch_locked = db_rbt_fetch_locked;
573 743540 : result->traverse = db_rbt_traverse;
574 743540 : result->traverse_read = db_rbt_traverse_read;
575 743540 : result->get_seqnum = db_rbt_get_seqnum;
576 743540 : result->transaction_start = db_rbt_trans_dummy;
577 743540 : result->transaction_commit = db_rbt_trans_dummy;
578 743540 : result->transaction_cancel = db_rbt_trans_dummy;
579 743540 : result->exists = db_rbt_exists;
580 743540 : result->wipe = db_rbt_wipe;
581 743540 : result->parse_record = db_rbt_parse_record;
582 743540 : result->id = db_rbt_id;
583 743540 : result->name = "dbwrap rbt";
584 :
585 743540 : return result;
586 : }
|
