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