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 }