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
  26 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
  27
  28 struct db_rbt_ctx {
  29         struct rb_root tree;
  30 };
  31
  32 struct db_rbt_rec {
  33         struct db_rbt_node *node;
  34 };
  35
  36 /* The structure that ends up in the tree */
  37
  38 struct db_rbt_node {
  39         struct rb_node rb_node;
  40         size_t keysize, valuesize;
  41 };
  42
  43 /*
  44  * Hide the ugly pointer calculations in a function
  45  */
  46
  47 static struct db_rbt_node *db_rbt2node(struct rb_node *node)
  48 {
  49         return (struct db_rbt_node *)
  50                 ((char *)node - offsetof(struct db_rbt_node, rb_node));
  51 }
  52
  53 /*
  54  * Compare two keys
  55  */
  56
  57 static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
  58 {
  59         int res;
  60
  61         res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
  62
  63         if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
  64                 return -1;
  65         }
  66         if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
  67                 return 1;
  68         }
  69         return 0;
  70 }
  71
  72 /*
  73  * dissect a db_rbt_node into its implicit key and value parts
  74  */
  75
  76 static void db_rbt_parse_node(struct db_rbt_node *node,
  77                               TDB_DATA *key, TDB_DATA *value)
  78 {
  79         size_t key_offset, value_offset;
  80
  81         key_offset = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
  82         key->dptr = ((uint8_t *)node) + key_offset;
  83         key->dsize = node->keysize;
  84
  85         value_offset = DBWRAP_RBT_ALIGN(node->keysize);
  86         value->dptr = key->dptr + value_offset;
  87         value->dsize = node->valuesize;
  88 }
  89
  90 static ssize_t db_rbt_reclen(size_t keylen, size_t valuelen)
  91 {
  92         size_t len, tmp;
  93
  94         len = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
  95
  96         tmp = DBWRAP_RBT_ALIGN(keylen);
  97         if (tmp < keylen) {
  98                 goto overflow;
  99         }
 100
 101         len += tmp;
 102         if (len < tmp) {
 103                 goto overflow;
 104         }
 105
 106         len += valuelen;
 107         if (len < valuelen) {
 108                 goto overflow;
 109         }
 110
 111         return len;
 112 overflow:
 113         return -1;
 114 }
 115
 116 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 117 {
 118         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
 119                 rec->db->private_data, struct db_rbt_ctx);
 120         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 121         struct db_rbt_node *node;
 122
 123         struct rb_node ** p;
 124         struct rb_node * parent;
 125
 126         ssize_t reclen;
 127         TDB_DATA this_key, this_val;
 128
 129         if (rec_priv->node != NULL) {
 130
 131                 /*
 132                  * The record was around previously
 133                  */
 134
 135                 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
 136
 137                 SMB_ASSERT(this_key.dsize == rec->key.dsize);
 138                 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
 139                                   this_key.dsize) == 0);
 140
 141                 if (this_val.dsize >= data.dsize) {
 142                         /*
 143                          * The new value fits into the old space
 144                          */
 145                         memcpy(this_val.dptr, data.dptr, data.dsize);
 146                         rec_priv->node->valuesize = data.dsize;
 147                         return NT_STATUS_OK;
 148                 }
 149         }
 150
 151         reclen = db_rbt_reclen(rec->key.dsize, data.dsize);
 152         if (reclen == -1) {
 153                 return NT_STATUS_INSUFFICIENT_RESOURCES;
 154         }
 155
 156         node = talloc_size(db_ctx, reclen);
 157         if (node == NULL) {
 158                 return NT_STATUS_NO_MEMORY;
 159         }
 160
 161         if (rec_priv->node != NULL) {
 162                 /*
 163                  * We need to delete the key from the tree and start fresh,
 164                  * there's not enough space in the existing record
 165                  */
 166
 167                 rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
 168
 169                 /*
 170                  * Keep the existing node around for a while: If the record
 171                  * existed before, we reference the key data in there.
 172                  */
 173         }
 174
 175         ZERO_STRUCT(node->rb_node);
 176
 177         node->keysize = rec->key.dsize;
 178         node->valuesize = data.dsize;
 179
 180         db_rbt_parse_node(node, &this_key, &this_val);
 181
 182         memcpy(this_key.dptr, rec->key.dptr, node->keysize);
 183         TALLOC_FREE(rec_priv->node);
 184         rec_priv->node = node;
 185
 186         memcpy(this_val.dptr, data.dptr, node->valuesize);
 187
 188         parent = NULL;
 189         p = &db_ctx->tree.rb_node;
 190
 191         while (*p) {
 192                 struct db_rbt_node *r;
 193                 TDB_DATA search_key, search_val;
 194                 int res;
 195
 196                 parent = (*p);
 197
 198                 r = db_rbt2node(*p);
 199
 200                 db_rbt_parse_node(r, &search_key, &search_val);
 201
 202                 res = db_rbt_compare(this_key, search_key);
 203
 204                 if (res == -1) {
 205                         p = &(*p)->rb_left;
 206                 }
 207                 else if (res == 1) {
 208                         p = &(*p)->rb_right;
 209                 }
 210                 else {
 211                         smb_panic("someone messed with the tree");
 212                 }
 213         }
 214
 215         rb_link_node(&node->rb_node, parent, p);
 216         rb_insert_color(&node->rb_node, &db_ctx->tree);
 217
 218         return NT_STATUS_OK;
 219 }
 220
 221 static NTSTATUS db_rbt_delete(struct db_record *rec)
 222 {
 223         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
 224                 rec->db->private_data, struct db_rbt_ctx);
 225         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 226
 227         if (rec_priv->node == NULL) {
 228                 return NT_STATUS_OK;
 229         }
 230
 231         rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
 232         TALLOC_FREE(rec_priv->node);
 233
 234         return NT_STATUS_OK;
 235 }
 236
 237 static NTSTATUS db_rbt_store_deny(struct db_record *rec, TDB_DATA data, int flag)
 238 {
 239         return NT_STATUS_MEDIA_WRITE_PROTECTED;
 240 }
 241
 242 static NTSTATUS db_rbt_delete_deny(struct db_record *rec)
 243 {
 244         return NT_STATUS_MEDIA_WRITE_PROTECTED;
 245 }
 246
 247 struct db_rbt_search_result {
 248         TDB_DATA key;
 249         TDB_DATA val;
 250         struct db_rbt_node* node;
 251 };
 252
 253 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
 254                                    struct db_rbt_search_result *result)
 255 {
 256         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 257                 db->private_data, struct db_rbt_ctx);
 258
 259         struct rb_node *n;
 260         bool found = false;
 261         struct db_rbt_node *r = NULL;
 262         TDB_DATA search_key, search_val;
 263
 264         n = ctx->tree.rb_node;
 265
 266         while (n != NULL) {
 267                 int res;
 268
 269                 r = db_rbt2node(n);
 270
 271                 db_rbt_parse_node(r, &search_key, &search_val);
 272
 273                 res = db_rbt_compare(key, search_key);
 274
 275                 if (res == -1) {
 276                         n = n->rb_left;
 277                 }
 278                 else if (res == 1) {
 279                         n = n->rb_right;
 280                 }
 281                 else {
 282                         found = true;
 283                         break;
 284                 }
 285         }
 286         if (result != NULL) {
 287                 if (found) {
 288                         result->key = search_key;
 289                         result->val = search_val;
 290                         result->node = r;
 291                 } else {
 292                         ZERO_STRUCT(*result);
 293                 }
 294         }
 295         return found;
 296 }
 297
 298 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
 299                                              TALLOC_CTX *mem_ctx,
 300                                              TDB_DATA key)
 301 {
 302         struct db_rbt_rec *rec_priv;
 303         struct db_record *result;
 304         size_t size;
 305         bool found;
 306         struct db_rbt_search_result res;
 307
 308         found = db_rbt_search_internal(db_ctx, key, &res);
 309
 310         /*
 311          * In this low-level routine, play tricks to reduce the number of
 312          * tallocs to one. Not recommened for general use, but here it pays
 313          * off.
 314          */
 315
 316         size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
 317                 + sizeof(struct db_rbt_rec);
 318
 319         if (!found) {
 320                 /*
 321                  * We need to keep the key around for later store
 322                  */
 323                 size += key.dsize;
 324         }
 325
 326         result = (struct db_record *)talloc_size(mem_ctx, size);
 327         if (result == NULL) {
 328                 return NULL;
 329         }
 330
 331         rec_priv = (struct db_rbt_rec *)
 332                 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
 333
 334         result->store = db_rbt_store;
 335         result->delete_rec = db_rbt_delete;
 336         result->private_data = rec_priv;
 337
 338         rec_priv->node = res.node;
 339         result->value  = res.val;
 340
 341         if (found) {
 342                 result->key = res.key;
 343         }
 344         else {
 345                 result->key.dptr = (uint8_t *)
 346                         ((char *)rec_priv + sizeof(*rec_priv));
 347                 result->key.dsize = key.dsize;
 348                 memcpy(result->key.dptr, key.dptr, key.dsize);
 349         }
 350
 351         return result;
 352 }
 353
 354 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
 355 {
 356         return db_rbt_search_internal(db, key, NULL);
 357 }
 358
 359 static int db_rbt_wipe(struct db_context *db)
 360 {
 361         struct db_rbt_ctx *old_ctx = talloc_get_type_abort(
 362                 db->private_data, struct db_rbt_ctx);
 363         struct db_rbt_ctx *new_ctx = talloc_zero(db, struct db_rbt_ctx);
 364         if (new_ctx == NULL) {
 365                 return -1;
 366         }
 367         db->private_data = new_ctx;
 368         talloc_free(old_ctx);
 369         return 0;
 370 }
 371
 372 static NTSTATUS db_rbt_parse_record(struct db_context *db, TDB_DATA key,
 373                                     void (*parser)(TDB_DATA key, TDB_DATA data,
 374                                                    void *private_data),
 375                                     void *private_data)
 376 {
 377         struct db_rbt_search_result res;
 378         bool found = db_rbt_search_internal(db, key, &res);
 379
 380         if (!found) {
 381                 return NT_STATUS_NOT_FOUND;
 382         }
 383         parser(res.key, res.val, private_data);
 384         return NT_STATUS_OK;
 385 }
 386
 387 static int db_rbt_traverse_internal(struct db_context *db,
 388                                     struct rb_node *n,
 389                                     int (*f)(struct db_record *db,
 390                                              void *private_data),
 391                                     void *private_data, uint32_t* count,
 392                                     bool rw)
 393 {
 394         struct rb_node *rb_right;
 395         struct rb_node *rb_left;
 396         struct db_record rec;
 397         struct db_rbt_rec rec_priv;
 398         int ret;
 399
 400         if (n == NULL) {
 401                 return 0;
 402         }
 403
 404         rb_left = n->rb_left;
 405         rb_right = n->rb_right;
 406
 407         ret = db_rbt_traverse_internal(db, rb_left, f, private_data, count, rw);
 408         if (ret != 0) {
 409                 return ret;
 410         }
 411
 412         rec_priv.node = db_rbt2node(n);
 413         /* n might be altered by the callback function */
 414         n = NULL;
 415
 416         ZERO_STRUCT(rec);
 417         rec.db = db;
 418         rec.private_data = &rec_priv;
 419         if (rw) {
 420                 rec.store = db_rbt_store;
 421                 rec.delete_rec = db_rbt_delete;
 422         } else {
 423                 rec.store = db_rbt_store_deny;
 424                 rec.delete_rec = db_rbt_delete_deny;
 425         }
 426         db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
 427
 428         ret = f(&rec, private_data);
 429         (*count) ++;
 430         if (ret != 0) {
 431                 return ret;
 432         }
 433
 434         if (rec_priv.node != NULL) {
 435                 /*
 436                  * If the current record is still there
 437                  * we should take the current rb_right.
 438                  */
 439                 rb_right = rec_priv.node->rb_node.rb_right;
 440         }
 441
 442         return db_rbt_traverse_internal(db, rb_right, f, private_data, count, rw);
 443 }
 444
 445 static int db_rbt_traverse(struct db_context *db,
 446                            int (*f)(struct db_record *db,
 447                                     void *private_data),
 448                            void *private_data)
 449 {
 450         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 451                 db->private_data, struct db_rbt_ctx);
 452         uint32_t count = 0;
 453
 454         int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
 455                                            f, private_data, &count,
 456                                            true /* rw */);
 457         if (ret != 0) {
 458                 return -1;
 459         }
 460         if (count > INT_MAX) {
 461                 return -1;
 462         }
 463         return count;
 464 }
 465
 466 static int db_rbt_traverse_read(struct db_context *db,
 467                                 int (*f)(struct db_record *db,
 468                                          void *private_data),
 469                                 void *private_data)
 470 {
 471         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 472                 db->private_data, struct db_rbt_ctx);
 473         uint32_t count = 0;
 474
 475         int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
 476                                            f, private_data, &count,
 477                                            false /* rw */);
 478         if (ret != 0) {
 479                 return -1;
 480         }
 481         if (count > INT_MAX) {
 482                 return -1;
 483         }
 484         return count;
 485 }
 486
 487 static int db_rbt_get_seqnum(struct db_context *db)
 488 {
 489         return 0;
 490 }
 491
 492 static int db_rbt_trans_dummy(struct db_context *db)
 493 {
 494         /*
 495          * Transactions are pretty pointless in-memory, just return success.
 496          */
 497         return 0;
 498 }
 499
 500 static size_t db_rbt_id(struct db_context *db, uint8_t *id, size_t idlen)
 501 {
 502         if (idlen >= sizeof(struct db_context *)) {
 503                 memcpy(id, &db, sizeof(struct db_context *));
 504         }
 505         return sizeof(struct db_context *);
 506 }
 507
 508 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
 509 {
 510         struct db_context *result;
 511
 512         result = talloc_zero(mem_ctx, struct db_context);
 513
 514         if (result == NULL) {
 515                 return NULL;
 516         }
 517
 518         result->private_data = talloc_zero(result, struct db_rbt_ctx);
 519
 520         if (result->private_data == NULL) {
 521                 TALLOC_FREE(result);
 522                 return NULL;
 523         }
 524
 525         result->fetch_locked = db_rbt_fetch_locked;
 526         result->traverse = db_rbt_traverse;
 527         result->traverse_read = db_rbt_traverse_read;
 528         result->get_seqnum = db_rbt_get_seqnum;
 529         result->transaction_start = db_rbt_trans_dummy;
 530         result->transaction_commit = db_rbt_trans_dummy;
 531         result->transaction_cancel = db_rbt_trans_dummy;
 532         result->exists = db_rbt_exists;
 533         result->wipe = db_rbt_wipe;
 534         result->parse_record = db_rbt_parse_record;
 535         result->id = db_rbt_id;
 536         result->name = "dbwrap rbt";
 537
 538         return result;
 539 }