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