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_storev(struct db_record *rec,
 122                               const TDB_DATA *dbufs, int num_dbufs, int flag)
 123 {
 124         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
 125                 rec->db->private_data, struct db_rbt_ctx);
 126         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         struct rb_node *parent = NULL;
 131         struct db_rbt_node *parent_node = NULL;
 132
 133         ssize_t reclen;
 134         TDB_DATA data, this_key, this_val;
 135         void *to_free = NULL;
 136
 137         if (db_ctx->traverse_read > 0) {
 138                 return NT_STATUS_MEDIA_WRITE_PROTECTED;
 139         }
 140
 141         if ((flag == TDB_INSERT) && (rec_priv->node != NULL)) {
 142                 return NT_STATUS_OBJECT_NAME_COLLISION;
 143         }
 144
 145         if ((flag == TDB_MODIFY) && (rec_priv->node == NULL)) {
 146                 return NT_STATUS_OBJECT_NAME_NOT_FOUND;
 147         }
 148
 149         if (num_dbufs == 1) {
 150                 data = dbufs[0];
 151         } else {
 152                 NTSTATUS status;
 153
 154                 data = (TDB_DATA) {0};
 155                 status = dbwrap_merge_dbufs(&data, rec, dbufs, num_dbufs);
 156                 if (!NT_STATUS_IS_OK(status)) {
 157                         return status;
 158                 }
 159                 to_free = data.dptr;
 160         }
 161
 162         if (rec_priv->node != NULL) {
 163
 164                 /*
 165                  * The record was around previously
 166                  */
 167
 168                 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
 169
 170                 SMB_ASSERT(this_key.dsize == rec->key.dsize);
 171                 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
 172                                   this_key.dsize) == 0);
 173
 174                 if (this_val.dsize >= data.dsize) {
 175                         /*
 176                          * The new value fits into the old space
 177                          */
 178                         memcpy(this_val.dptr, data.dptr, data.dsize);
 179                         rec_priv->node->valuesize = data.dsize;
 180                         TALLOC_FREE(to_free);
 181                         return NT_STATUS_OK;
 182                 }
 183         }
 184
 185         reclen = db_rbt_reclen(rec->key.dsize, data.dsize);
 186         if (reclen == -1) {
 187                 TALLOC_FREE(to_free);
 188                 return NT_STATUS_INSUFFICIENT_RESOURCES;
 189         }
 190
 191         node = talloc_zero_size(db_ctx, reclen);
 192         if (node == NULL) {
 193                 TALLOC_FREE(to_free);
 194                 return NT_STATUS_NO_MEMORY;
 195         }
 196
 197         if (rec_priv->node != NULL) {
 198                 if (db_ctx->traverse_nextp != NULL) {
 199                         if (*db_ctx->traverse_nextp == rec_priv->node) {
 200                                 *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                 rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
 210                 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         node->keysize = rec->key.dsize;
 219         node->valuesize = data.dsize;
 220
 221         db_rbt_parse_node(node, &this_key, &this_val);
 222
 223         memcpy(this_key.dptr, rec->key.dptr, node->keysize);
 224         TALLOC_FREE(rec_priv->node);
 225         rec_priv->node = node;
 226
 227         if (node->valuesize > 0) {
 228                 memcpy(this_val.dptr, data.dptr, node->valuesize);
 229         }
 230
 231         parent = NULL;
 232         p = &db_ctx->tree.rb_node;
 233
 234         while (*p) {
 235                 struct db_rbt_node *r;
 236                 TDB_DATA search_key, search_val;
 237                 int res;
 238
 239                 r = db_rbt2node(*p);
 240
 241                 parent = (*p);
 242                 parent_node = r;
 243
 244                 db_rbt_parse_node(r, &search_key, &search_val);
 245
 246                 res = db_rbt_compare(this_key, search_key);
 247
 248                 if (res == -1) {
 249                         p = &(*p)->rb_left;
 250                 }
 251                 else if (res == 1) {
 252                         p = &(*p)->rb_right;
 253                 }
 254                 else {
 255                         smb_panic("someone messed with the tree");
 256                 }
 257         }
 258
 259         rb_link_node(&node->rb_node, parent, p);
 260         DLIST_ADD_AFTER(db_ctx->nodes, node, parent_node);
 261         rb_insert_color(&node->rb_node, &db_ctx->tree);
 262
 263         TALLOC_FREE(to_free);
 264
 265         return NT_STATUS_OK;
 266 }
 267
 268 static NTSTATUS db_rbt_delete(struct db_record *rec)
 269 {
 270         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
 271                 rec->db->private_data, struct db_rbt_ctx);
 272         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 273
 274         if (db_ctx->traverse_read > 0) {
 275                 return NT_STATUS_MEDIA_WRITE_PROTECTED;
 276         }
 277
 278         if (rec_priv->node == NULL) {
 279                 return NT_STATUS_OK;
 280         }
 281
 282         if (db_ctx->traverse_nextp != NULL) {
 283                 if (*db_ctx->traverse_nextp == rec_priv->node) {
 284                         *db_ctx->traverse_nextp = rec_priv->node->next;
 285                 }
 286         }
 287
 288         rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
 289         DLIST_REMOVE(db_ctx->nodes, rec_priv->node);
 290         TALLOC_FREE(rec_priv->node);
 291
 292         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 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
 302                                    struct db_rbt_search_result *result)
 303 {
 304         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 305                 db->private_data, struct db_rbt_ctx);
 306
 307         struct rb_node *n;
 308         bool found = false;
 309         struct db_rbt_node *r = NULL;
 310         TDB_DATA search_key = { 0 };
 311         TDB_DATA search_val = { 0 };
 312
 313         n = ctx->tree.rb_node;
 314
 315         while (n != NULL) {
 316                 int res;
 317
 318                 r = db_rbt2node(n);
 319
 320                 db_rbt_parse_node(r, &search_key, &search_val);
 321
 322                 res = db_rbt_compare(key, search_key);
 323
 324                 if (res == -1) {
 325                         n = n->rb_left;
 326                 }
 327                 else if (res == 1) {
 328                         n = n->rb_right;
 329                 }
 330                 else {
 331                         found = true;
 332                         break;
 333                 }
 334         }
 335         if (result != NULL) {
 336                 if (found) {
 337                         result->key = search_key;
 338                         result->val = search_val;
 339                         result->node = r;
 340                 } else {
 341                         ZERO_STRUCT(*result);
 342                 }
 343         }
 344         return found;
 345 }
 346
 347 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
 348                                              TALLOC_CTX *mem_ctx,
 349                                              TDB_DATA key)
 350 {
 351         struct db_rbt_rec *rec_priv;
 352         struct db_record *result;
 353         size_t size;
 354         bool found;
 355         struct db_rbt_search_result res;
 356
 357         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         size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
 366                 + sizeof(struct db_rbt_rec);
 367
 368         if (!found) {
 369                 /*
 370                  * We need to keep the key around for later store
 371                  */
 372                 size += key.dsize;
 373         }
 374
 375         result = (struct db_record *)talloc_size(mem_ctx, size);
 376         if (result == NULL) {
 377                 return NULL;
 378         }
 379
 380         rec_priv = (struct db_rbt_rec *)
 381                 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
 382
 383         result->storev = db_rbt_storev;
 384         result->delete_rec = db_rbt_delete;
 385         result->private_data = rec_priv;
 386
 387         rec_priv->node = res.node;
 388         result->value  = res.val;
 389         result->value_valid = true;
 390
 391         if (found) {
 392                 result->key = res.key;
 393         }
 394         else {
 395                 result->key.dptr = (uint8_t *)
 396                         ((char *)rec_priv + sizeof(*rec_priv));
 397                 result->key.dsize = key.dsize;
 398                 memcpy(result->key.dptr, key.dptr, key.dsize);
 399         }
 400
 401         return result;
 402 }
 403
 404 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
 405 {
 406         return db_rbt_search_internal(db, key, NULL);
 407 }
 408
 409 static int db_rbt_wipe(struct db_context *db)
 410 {
 411         struct db_rbt_ctx *old_ctx = talloc_get_type_abort(
 412                 db->private_data, struct db_rbt_ctx);
 413         struct db_rbt_ctx *new_ctx = talloc_zero(db, struct db_rbt_ctx);
 414         if (new_ctx == NULL) {
 415                 return -1;
 416         }
 417         db->private_data = new_ctx;
 418         talloc_free(old_ctx);
 419         return 0;
 420 }
 421
 422 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         struct db_rbt_search_result res;
 428         bool found = db_rbt_search_internal(db, key, &res);
 429
 430         if (!found) {
 431                 return NT_STATUS_NOT_FOUND;
 432         }
 433         parser(res.key, res.val, private_data);
 434         return NT_STATUS_OK;
 435 }
 436
 437 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         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 444                 db->private_data, struct db_rbt_ctx);
 445         struct db_rbt_node *cur = NULL;
 446         struct db_rbt_node *next = NULL;
 447         int ret;
 448
 449         for (cur = ctx->nodes; cur != NULL; cur = next) {
 450                 struct db_record rec;
 451                 struct db_rbt_rec rec_priv;
 452
 453                 rec_priv.node = cur;
 454                 next = rec_priv.node->next;
 455
 456                 ZERO_STRUCT(rec);
 457                 rec.db = db;
 458                 rec.private_data = &rec_priv;
 459                 rec.storev = db_rbt_storev;
 460                 rec.delete_rec = db_rbt_delete;
 461                 db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
 462                 rec.value_valid = true;
 463
 464                 if (rw) {
 465                         ctx->traverse_nextp = &next;
 466                 }
 467                 ret = f(&rec, private_data);
 468                 (*count) ++;
 469                 if (rw) {
 470                         ctx->traverse_nextp = NULL;
 471                 }
 472                 if (ret != 0) {
 473                         return ret;
 474                 }
 475                 if (rec_priv.node != NULL) {
 476                         next = rec_priv.node->next;
 477                 }
 478         }
 479
 480         return 0;
 481 }
 482
 483 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         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 489                 db->private_data, struct db_rbt_ctx);
 490         uint32_t count = 0;
 491         int ret;
 492
 493         ctx->traverse_read++;
 494         ret = db_rbt_traverse_internal(db,
 495                                        f, private_data, &count,
 496                                        false /* rw */);
 497         ctx->traverse_read--;
 498         if (ret != 0) {
 499                 return -1;
 500         }
 501         if (count > INT_MAX) {
 502                 return -1;
 503         }
 504         return count;
 505 }
 506
 507 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         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 513                 db->private_data, struct db_rbt_ctx);
 514         uint32_t count = 0;
 515         int ret;
 516
 517         if (ctx->traverse_nextp != NULL) {
 518                 return -1;
 519         };
 520
 521         if (ctx->traverse_read > 0) {
 522                 return db_rbt_traverse_read(db, f, private_data);
 523         }
 524
 525         ret = db_rbt_traverse_internal(db,
 526                                        f, private_data, &count,
 527                                        true /* rw */);
 528         if (ret != 0) {
 529                 return -1;
 530         }
 531         if (count > INT_MAX) {
 532                 return -1;
 533         }
 534         return count;
 535 }
 536
 537 static int db_rbt_get_seqnum(struct db_context *db)
 538 {
 539         return 0;
 540 }
 541
 542 static int db_rbt_trans_dummy(struct db_context *db)
 543 {
 544         /*
 545          * Transactions are pretty pointless in-memory, just return success.
 546          */
 547         return 0;
 548 }
 549
 550 static size_t db_rbt_id(struct db_context *db, uint8_t *id, size_t idlen)
 551 {
 552         if (idlen >= sizeof(struct db_context *)) {
 553                 memcpy(id, &db, sizeof(struct db_context *));
 554         }
 555         return sizeof(struct db_context *);
 556 }
 557
 558 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
 559 {
 560         struct db_context *result;
 561
 562         result = talloc_zero(mem_ctx, struct db_context);
 563
 564         if (result == NULL) {
 565                 return NULL;
 566         }
 567
 568         result->private_data = talloc_zero(result, struct db_rbt_ctx);
 569
 570         if (result->private_data == NULL) {
 571                 TALLOC_FREE(result);
 572                 return NULL;
 573         }
 574
 575         result->fetch_locked = db_rbt_fetch_locked;
 576         result->traverse = db_rbt_traverse;
 577         result->traverse_read = db_rbt_traverse_read;
 578         result->get_seqnum = db_rbt_get_seqnum;
 579         result->transaction_start = db_rbt_trans_dummy;
 580         result->transaction_commit = db_rbt_trans_dummy;
 581         result->transaction_cancel = db_rbt_trans_dummy;
 582         result->exists = db_rbt_exists;
 583         result->wipe = db_rbt_wipe;
 584         result->parse_record = db_rbt_parse_record;
 585         result->id = db_rbt_id;
 586         result->name = "dbwrap rbt";
 587
 588         return result;
 589 }