sys/vfs/hammer/hammer_object.c

   1 /*
   2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  * $DragonFly: src/sys/vfs/hammer/hammer_object.c,v 1.10 2007/12/29 09:01:27 dillon Exp $
  35  */
  36
  37 #include "hammer.h"
  38
  39 static int hammer_mem_add(hammer_transaction_t trans,
  40                              hammer_record_t record);
  41 static int hammer_mem_lookup(hammer_cursor_t cursor, hammer_inode_t ip);
  42 static int hammer_mem_first(hammer_cursor_t cursor, hammer_inode_t ip);
  43 static void hammer_free_mem_record(hammer_record_t record);
  44
  45 /*
  46  * Red-black tree support.
  47  */
  48 static int
  49 hammer_rec_rb_compare(hammer_record_t rec1, hammer_record_t rec2)
  50 {
  51         if (rec1->rec.base.base.rec_type < rec2->rec.base.base.rec_type)
  52                 return(-1);
  53         if (rec1->rec.base.base.rec_type > rec2->rec.base.base.rec_type)
  54                 return(1);
  55
  56         if (rec1->rec.base.base.key < rec2->rec.base.base.key)
  57                 return(-1);
  58         if (rec1->rec.base.base.key > rec2->rec.base.base.key)
  59                 return(1);
  60
  61         if (rec1->rec.base.base.create_tid < rec2->rec.base.base.create_tid)
  62                 return(-1);
  63         if (rec1->rec.base.base.create_tid > rec2->rec.base.base.create_tid)
  64                 return(1);
  65         return(0);
  66 }
  67
  68 static int
  69 hammer_rec_compare(hammer_base_elm_t info, hammer_record_t rec)
  70 {
  71         if (info->rec_type < rec->rec.base.base.rec_type)
  72                 return(-3);
  73         if (info->rec_type > rec->rec.base.base.rec_type)
  74                 return(3);
  75
  76         if (info->key < rec->rec.base.base.key)
  77                 return(-2);
  78         if (info->key > rec->rec.base.base.key)
  79                 return(2);
  80
  81         /*
  82          * This test has a number of special cases.  create_tid in key1 is
  83          * the as-of transction id, and delete_tid in key1 is NOT USED.
  84          *
  85          * A key1->create_tid of 0 matches any record regardles of when
  86          * it was created or destroyed.  0xFFFFFFFFFFFFFFFFULL should be
  87          * used to search for the most current state of the object.
  88          *
  89          * key2->create_tid is a HAMMER record and will never be
  90          * 0.   key2->delete_tid is the deletion transaction id or 0 if
  91          * the record has not yet been deleted.
  92          */
  93         if (info->create_tid) {
  94                 if (info->create_tid < rec->rec.base.base.create_tid)
  95                         return(-1);
  96                 if (rec->rec.base.base.delete_tid &&
  97                     info->create_tid >= rec->rec.base.base.delete_tid) {
  98                         return(1);
  99                 }
 100         }
 101         return(0);
 102 }
 103
 104 /*
 105  * RB_SCAN comparison code for hammer_mem_first().  The argument order
 106  * is reversed so the comparison result has to be negated.  key_beg and
 107  * key_end are both range-inclusive.
 108  *
 109  * The creation timestamp can cause hammer_rec_compare() to return -1 or +1.
 110  * These do not stop the scan.
 111  *
 112  * Localized deletions are not cached in-memory.
 113  */
 114 static
 115 int
 116 hammer_rec_scan_cmp(hammer_record_t rec, void *data)
 117 {
 118         hammer_cursor_t cursor = data;
 119         int r;
 120
 121         r = hammer_rec_compare(&cursor->key_beg, rec);
 122         if (r > 1)
 123                 return(-1);
 124         if (r == 0)
 125                 return(0);
 126         r = hammer_rec_compare(&cursor->key_end, rec);
 127         if (r < -1)
 128                 return(1);
 129         return(0);
 130 }
 131
 132 RB_GENERATE(hammer_rec_rb_tree, hammer_record, rb_node, hammer_rec_rb_compare);
 133 RB_GENERATE_XLOOKUP(hammer_rec_rb_tree, INFO, hammer_record, rb_node,
 134                     hammer_rec_compare, hammer_base_elm_t);
 135
 136 /*
 137  * Allocate a record for the caller to finish filling in.  The record is
 138  * returned referenced and locked.
 139  */
 140 hammer_record_t
 141 hammer_alloc_mem_record(hammer_inode_t ip)
 142 {
 143         hammer_record_t record;
 144
 145         record = kmalloc(sizeof(*record), M_HAMMER, M_WAITOK|M_ZERO);
 146         record->ip = ip;
 147         hammer_ref(&record->lock);
 148         hammer_lock_ex(&record->lock);
 149         return (record);
 150 }
 151
 152 /*
 153  * Release a memory record.  If the record was marked for defered deletion,
 154  * and no references remain, the record is physically destroyed.
 155  */
 156 void
 157 hammer_rel_mem_record(struct hammer_record **recordp)
 158 {
 159         hammer_record_t rec;
 160
 161         if ((rec = *recordp) != NULL) {
 162                 hammer_unref(&rec->lock);
 163                 if (rec->lock.refs == 0) {
 164                         if (rec->flags & HAMMER_RECF_DELETED)
 165                                 hammer_free_mem_record(rec);
 166                 }
 167                 *recordp = NULL;
 168         }
 169 }
 170
 171 /*
 172  * Drop a locked hammer in-memory record.  This function unlocks and
 173  * dereferences the record.  If delete != 0 the record is marked for
 174  * deletion.  Physical deletion only occurs when the last reference goes
 175  * away.
 176  */
 177 void
 178 hammer_drop_mem_record(hammer_record_t rec, int delete)
 179 {
 180         if (delete)
 181                 rec->flags |= HAMMER_RECF_DELETED;
 182         hammer_unlock(&rec->lock);
 183         hammer_rel_mem_record(&rec);
 184 }
 185
 186 /*
 187  * Free a record.  Clean the structure up even though we are throwing it
 188  * away as a sanity check.  The actual free operation is delayed while
 189  * the record is referenced.  However, the record is removed from the RB
 190  * tree immediately.
 191  */
 192 static void
 193 hammer_free_mem_record(hammer_record_t record)
 194 {
 195         if (record->flags & HAMMER_RECF_ONRBTREE) {
 196                 RB_REMOVE(hammer_rec_rb_tree, &record->ip->rec_tree, record);
 197                 record->flags &= ~HAMMER_RECF_ONRBTREE;
 198         }
 199         if (record->lock.refs) {
 200                 record->flags |= HAMMER_RECF_DELETED;
 201                 return;
 202         }
 203         if (record->flags & HAMMER_RECF_ALLOCDATA) {
 204                 kfree(record->data, M_HAMMER);
 205                 record->flags &= ~HAMMER_RECF_ALLOCDATA;
 206         }
 207         record->data = NULL;
 208         kfree(record, M_HAMMER);
 209 }
 210
 211 /*
 212  * Lookup an in-memory record given the key specified in the cursor.  Works
 213  * just like hammer_btree_lookup() but operates on an inode's in-memory
 214  * record list.
 215  *
 216  * The lookup must fail if the record is marked for deferred deletion.
 217  */
 218 static
 219 int
 220 hammer_mem_lookup(hammer_cursor_t cursor, hammer_inode_t ip)
 221 {
 222         int error;
 223
 224         if (cursor->iprec)
 225                 hammer_rel_mem_record(&cursor->iprec);
 226         if (cursor->ip) {
 227                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
 228                                                   &cursor->ip->rec_tree);
 229         }
 230         cursor->ip = ip;
 231         hammer_rec_rb_tree_scan_info_link(&cursor->scan, &ip->rec_tree);
 232         cursor->scan.node = NULL;
 233         cursor->iprec = hammer_rec_rb_tree_RB_LOOKUP_INFO(
 234                                 &ip->rec_tree, &cursor->key_beg);
 235         if (cursor->iprec == NULL) {
 236                 error = ENOENT;
 237         } else {
 238                 hammer_ref(&cursor->iprec->lock);
 239                 error = 0;
 240         }
 241         return(error);
 242 }
 243
 244 /*
 245  * hammer_mem_first() - locate the first in-memory record matching the
 246  * cursor.
 247  *
 248  * The RB_SCAN function we use is designed as a callback.  We terminate it
 249  * (return -1) as soon as we get a match.
 250  */
 251 static
 252 int
 253 hammer_rec_scan_callback(hammer_record_t rec, void *data)
 254 {
 255         hammer_cursor_t cursor = data;
 256
 257         /*
 258          * Skip if not visible due to our as-of TID
 259          */
 260         if (cursor->key_beg.create_tid) {
 261                 if (cursor->key_beg.create_tid < rec->rec.base.base.create_tid)
 262                         return(0);
 263                 if (rec->rec.base.base.delete_tid &&
 264                     cursor->key_beg.create_tid >=
 265                      rec->rec.base.base.delete_tid) {
 266                         return(0);
 267                 }
 268         }
 269
 270         /*
 271          * Return the first matching record and stop the scan
 272          */
 273         if (cursor->iprec == NULL) {
 274                 cursor->iprec = rec;
 275                 hammer_ref(&rec->lock);
 276                 return(-1);
 277         }
 278         return(0);
 279 }
 280
 281 static
 282 int
 283 hammer_mem_first(hammer_cursor_t cursor, hammer_inode_t ip)
 284 {
 285         if (cursor->iprec)
 286                 hammer_rel_mem_record(&cursor->iprec);
 287         if (cursor->ip) {
 288                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
 289                                                   &cursor->ip->rec_tree);
 290         }
 291         cursor->ip = ip;
 292         hammer_rec_rb_tree_scan_info_link(&cursor->scan, &ip->rec_tree);
 293         cursor->scan.node = NULL;
 294         hammer_rec_rb_tree_RB_SCAN(&ip->rec_tree, hammer_rec_scan_cmp,
 295                                    hammer_rec_scan_callback, cursor);
 296
 297         /*
 298          * Adjust scan.node and keep it linked into the RB-tree so we can
 299          * hold the cursor through third party modifications of the RB-tree.
 300          */
 301         if (cursor->iprec) {
 302                 cursor->scan.node = hammer_rec_rb_tree_RB_NEXT(cursor->iprec);
 303                 return(0);
 304         }
 305         return(ENOENT);
 306 }
 307
 308 void
 309 hammer_mem_done(hammer_cursor_t cursor)
 310 {
 311         if (cursor->ip) {
 312                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
 313                                                   &cursor->ip->rec_tree);
 314                 cursor->ip = NULL;
 315         }
 316         if (cursor->iprec)
 317                 hammer_rel_mem_record(&cursor->iprec);
 318 }
 319
 320 /************************************************************************
 321  *                   HAMMER IN-MEMORY RECORD FUNCTIONS                  *
 322  ************************************************************************
 323  *
 324  * These functions manipulate in-memory records.  Such records typically
 325  * exist prior to being committed to disk or indexed via the on-disk B-Tree.
 326  */
 327
 328 /*
 329  * Add a directory entry (dip,ncp) which references inode (ip).
 330  *
 331  * Note that the low 32 bits of the namekey are set temporarily to create
 332  * a unique in-memory record, and may be modified a second time when the
 333  * record is synchronized to disk.  In particular, the low 32 bits cannot be
 334  * all 0's when synching to disk, which is not handled here.
 335  */
 336 int
 337 hammer_ip_add_directory(struct hammer_transaction *trans,
 338                      struct hammer_inode *dip, struct namecache *ncp,
 339                      struct hammer_inode *ip)
 340 {
 341         hammer_record_t record;
 342         int error;
 343         int bytes;
 344
 345         record = hammer_alloc_mem_record(dip);
 346
 347         bytes = ncp->nc_nlen;   /* NOTE: terminating \0 is NOT included */
 348         if (++trans->hmp->namekey_iterator == 0)
 349                 ++trans->hmp->namekey_iterator;
 350
 351         record->rec.entry.base.base.obj_id = dip->obj_id;
 352         record->rec.entry.base.base.key =
 353                 hammer_directory_namekey(ncp->nc_name, bytes);
 354         record->rec.entry.base.base.key += trans->hmp->namekey_iterator;
 355         record->rec.entry.base.base.create_tid = trans->tid;
 356         record->rec.entry.base.base.rec_type = HAMMER_RECTYPE_DIRENTRY;
 357         record->rec.entry.base.base.obj_type = ip->ino_rec.base.base.obj_type;
 358         record->rec.entry.obj_id = ip->obj_id;
 359         if (bytes <= sizeof(record->rec.entry.den_name)) {
 360                 record->data = (void *)record->rec.entry.den_name;
 361                 record->flags |= HAMMER_RECF_EMBEDDED_DATA;
 362         } else {
 363                 record->data = kmalloc(bytes, M_HAMMER, M_WAITOK);
 364                 record->flags |= HAMMER_RECF_ALLOCDATA;
 365         }
 366         bcopy(ncp->nc_name, record->data, bytes);
 367         record->rec.entry.base.data_len = bytes;
 368         ++ip->ino_rec.ino_nlinks;
 369         hammer_modify_inode(trans, ip,
 370                             HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
 371         error = hammer_mem_add(trans, record);
 372         return(error);
 373 }
 374
 375 /*
 376  * Delete the directory entry and update the inode link count.  The
 377  * cursor must be seeked to the directory entry record being deleted.
 378  *
 379  * NOTE: HAMMER_CURSOR_DELETE may not have been set.  XXX remove flag.
 380  */
 381 int
 382 hammer_ip_del_directory(struct hammer_transaction *trans,
 383                      hammer_cursor_t cursor, struct hammer_inode *dip,
 384                      struct hammer_inode *ip)
 385 {
 386         int error;
 387
 388         error = hammer_ip_delete_record(cursor, trans->tid);
 389
 390         /*
 391          * One less link.  The file may still be open in the OS even after
 392          * all links have gone away so we don't destroy the inode's data
 393          * here.
 394          */
 395         if (error == 0) {
 396                 --ip->ino_rec.ino_nlinks;
 397                 hammer_modify_inode(trans, ip,
 398                                     HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
 399                 if (ip->vp == NULL || (ip->vp->v_flag & VINACTIVE))
 400                         hammer_sync_inode(ip, MNT_NOWAIT, 1);
 401
 402         }
 403         return(error);
 404 }
 405
 406 /*
 407  * Sync data from a buffer cache buffer (typically) to the filesystem.  This
 408  * is called via the strategy called from a cached data source.  This code
 409  * is responsible for actually writing a data record out to the disk.
 410  */
 411 int
 412 hammer_ip_sync_data(hammer_transaction_t trans, hammer_inode_t ip,
 413                        int64_t offset, void *data, int bytes,
 414                        struct hammer_cursor **spike)
 415 {
 416         struct hammer_cursor cursor;
 417         hammer_record_ondisk_t rec;
 418         union hammer_btree_elm elm;
 419         void *bdata;
 420         int error;
 421
 422         error = hammer_init_cursor_ip(&cursor, ip);
 423         if (error)
 424                 return(error);
 425         cursor.key_beg.obj_id = ip->obj_id;
 426         cursor.key_beg.key = offset + bytes;
 427         cursor.key_beg.create_tid = trans->tid;
 428         cursor.key_beg.delete_tid = 0;
 429         cursor.key_beg.rec_type = HAMMER_RECTYPE_DATA;
 430         cursor.flags = HAMMER_CURSOR_INSERT;
 431
 432         /*
 433          * Issue a lookup to position the cursor and locate the cluster
 434          */
 435         error = hammer_btree_lookup(&cursor);
 436         if (error == 0) {
 437                 kprintf("hammer_ip_sync_data: duplicate data at (%lld,%d)\n",
 438                         offset, bytes);
 439                 hammer_print_btree_elm(&cursor.node->ondisk->elms[cursor.index],
 440                                        HAMMER_BTREE_TYPE_LEAF, cursor.index);
 441                 error = EIO;
 442         }
 443         if (error != ENOENT)
 444                 goto done;
 445
 446         /*
 447          * Allocate record and data space now that we know which cluster
 448          * the B-Tree node ended up in.
 449          */
 450         bdata = hammer_alloc_data(cursor.node->cluster, bytes, &error,
 451                                   &cursor.data_buffer);
 452         if (bdata == NULL)
 453                 goto done;
 454         rec = hammer_alloc_record(cursor.node->cluster, &error,
 455                                   &cursor.record_buffer);
 456         if (rec == NULL)
 457                 goto fail1;
 458
 459         /*
 460          * Fill everything in and insert our B-Tree node.
 461          */
 462         rec->base.base = cursor.key_beg;
 463         rec->base.data_crc = crc32(data, bytes);
 464         rec->base.rec_id = 0;   /* XXX */
 465         rec->base.data_offset = hammer_bclu_offset(cursor.data_buffer, bdata);
 466         rec->base.data_len = bytes;
 467         hammer_modify_buffer(cursor.record_buffer);
 468
 469         bcopy(data, bdata, bytes);
 470         hammer_modify_buffer(cursor.data_buffer);
 471
 472         elm.leaf.base = cursor.key_beg;
 473         elm.leaf.rec_offset = hammer_bclu_offset(cursor.record_buffer, rec);
 474         elm.leaf.data_offset = rec->base.data_offset;
 475         elm.leaf.data_len = bytes;
 476         elm.leaf.data_crc = rec->base.data_crc;
 477
 478         error = hammer_btree_insert(&cursor, &elm);
 479         if (error == 0)
 480                 goto done;
 481
 482         hammer_free_record_ptr(cursor.record_buffer, rec);
 483 fail1:
 484         hammer_free_data_ptr(cursor.data_buffer, bdata, bytes);
 485 done:
 486         /*
 487          * If ENOSPC in cluster fill in the spike structure and return
 488          * ENOSPC.
 489          */
 490         if (error == ENOSPC)
 491                 hammer_load_spike(&cursor, spike);
 492         hammer_done_cursor(&cursor);
 493         return(error);
 494 }
 495
 496 /*
 497  * Sync an in-memory record to the disk.  this is typically called via fsync
 498  * from a cached record source.  This code is responsible for actually
 499  * writing a record out to the disk.
 500  */
 501 int
 502 hammer_ip_sync_record(hammer_record_t record, struct hammer_cursor **spike)
 503 {
 504         struct hammer_cursor cursor;
 505         hammer_record_ondisk_t rec;
 506         union hammer_btree_elm elm;
 507         void *bdata;
 508         int error;
 509
 510         error = hammer_init_cursor_ip(&cursor, record->ip);
 511         if (error)
 512                 return(error);
 513         cursor.key_beg = record->rec.base.base;
 514         cursor.flags = HAMMER_CURSOR_INSERT;
 515
 516         /*
 517          * Issue a lookup to position the cursor and locate the cluster.  The
 518          * target key should not exist.
 519          *
 520          * If we run out of space trying to adjust the B-Tree for the
 521          * insert, re-lookup without the insert flag so the cursor
 522          * is properly positioned for the spike.
 523          */
 524         error = hammer_btree_lookup(&cursor);
 525         if (error == 0) {
 526                 kprintf("hammer_ip_sync_record: duplicate rec at (%016llx)\n",
 527                         record->rec.base.base.key);
 528                 error = EIO;
 529         }
 530         if (error != ENOENT)
 531                 goto done;
 532
 533         /*
 534          * Allocate record and data space now that we know which cluster
 535          * the B-Tree node ended up in.
 536          */
 537         if (record->data == NULL ||
 538             (record->flags & HAMMER_RECF_EMBEDDED_DATA)) {
 539                 bdata = record->data;
 540         } else {
 541                 bdata = hammer_alloc_data(cursor.node->cluster,
 542                                           record->rec.base.data_len, &error,
 543                                           &cursor.data_buffer);
 544                 if (bdata == NULL)
 545                         goto done;
 546         }
 547         rec = hammer_alloc_record(cursor.node->cluster, &error,
 548                                   &cursor.record_buffer);
 549         if (rec == NULL)
 550                 goto fail1;
 551
 552         /*
 553          * Fill everything in and insert our B-Tree node.
 554          *
 555          * XXX assign rec_id here
 556          */
 557         *rec = record->rec;
 558         if (bdata) {
 559                 rec->base.data_crc = crc32(record->data,
 560                                            record->rec.base.data_len);
 561                 if (record->flags & HAMMER_RECF_EMBEDDED_DATA) {
 562                         /*
 563                          * Data embedded in record
 564                          */
 565                         rec->base.data_offset = ((char *)bdata -
 566                                                  (char *)&record->rec);
 567                         KKASSERT(rec->base.data_offset >= 0 &&
 568                                  rec->base.data_offset + rec->base.data_len <
 569                                   sizeof(*rec));
 570                         rec->base.data_offset += hammer_bclu_offset(cursor.record_buffer, rec);
 571                 } else {
 572                         /*
 573                          * Data separate from record
 574                          */
 575                         rec->base.data_offset = hammer_bclu_offset(cursor.data_buffer,bdata);
 576                         bcopy(record->data, bdata, rec->base.data_len);
 577                         hammer_modify_buffer(cursor.data_buffer);
 578                 }
 579         }
 580         rec->base.rec_id = 0;   /* XXX */
 581
 582         hammer_modify_buffer(cursor.record_buffer);
 583
 584         elm.leaf.base = cursor.key_beg;
 585         elm.leaf.rec_offset = hammer_bclu_offset(cursor.record_buffer, rec);
 586         elm.leaf.data_offset = rec->base.data_offset;
 587         elm.leaf.data_len = rec->base.data_len;
 588         elm.leaf.data_crc = rec->base.data_crc;
 589
 590         error = hammer_btree_insert(&cursor, &elm);
 591         if (error == 0)
 592                 goto done;
 593
 594         hammer_free_record_ptr(cursor.record_buffer, rec);
 595 fail1:
 596         if (record->data && (record->flags & HAMMER_RECF_EMBEDDED_DATA) == 0) {
 597                 hammer_free_data_ptr(cursor.data_buffer, bdata,
 598                                      record->rec.base.data_len);
 599         }
 600 done:
 601         /*
 602          * If ENOSPC in cluster fill in the spike structure and return
 603          * ENOSPC.
 604          */
 605         if (error == ENOSPC)
 606                 hammer_load_spike(&cursor, spike);
 607         hammer_done_cursor(&cursor);
 608         return(error);
 609 }
 610
 611 /*
 612  * Write out a record using the specified cursor.  The caller does not have
 613  * to seek the cursor.  The flags are used to determine whether the data
 614  * (if any) is embedded in the record or not.
 615  *
 616  * The target cursor will be modified by this call.  Note in particular
 617  * that HAMMER_CURSOR_INSERT is set.
 618  */
 619 int
 620 hammer_write_record(hammer_cursor_t cursor, hammer_record_ondisk_t orec,
 621                     void *data, int cursor_flags)
 622 {
 623         union hammer_btree_elm elm;
 624         hammer_record_ondisk_t nrec;
 625         void *bdata;
 626         int error;
 627
 628         cursor->key_beg = orec->base.base;
 629         cursor->flags |= HAMMER_CURSOR_INSERT;
 630
 631         /*
 632          * Issue a lookup to position the cursor and locate the cluster.  The
 633          * target key should not exist.
 634          *
 635          * If we run out of space trying to adjust the B-Tree for the
 636          * insert, re-lookup without the insert flag so the cursor
 637          * is properly positioned for the spike.
 638          */
 639         error = hammer_btree_lookup(cursor);
 640         if (error == 0) {
 641                 kprintf("hammer_ip_sync_record: duplicate rec at (%016llx)\n",
 642                         orec->base.base.key);
 643                 error = EIO;
 644         }
 645         if (error != ENOENT)
 646                 goto done;
 647
 648         /*
 649          * Allocate record and data space now that we know which cluster
 650          * the B-Tree node ended up in.
 651          */
 652         if (data == NULL ||
 653             (cursor_flags & HAMMER_RECF_EMBEDDED_DATA)) {
 654                 bdata = data;
 655         } else {
 656                 bdata = hammer_alloc_data(cursor->node->cluster,
 657                                           orec->base.data_len, &error,
 658                                           &cursor->data_buffer);
 659                 if (bdata == NULL)
 660                         goto done;
 661         }
 662         nrec = hammer_alloc_record(cursor->node->cluster, &error,
 663                                   &cursor->record_buffer);
 664         if (nrec == NULL)
 665                 goto fail1;
 666
 667         /*
 668          * Fill everything in and insert our B-Tree node.
 669          *
 670          * XXX assign rec_id here
 671          */
 672         *nrec = *orec;
 673         nrec->base.data_offset = 0;
 674         if (bdata) {
 675                 nrec->base.data_crc = crc32(bdata, nrec->base.data_len);
 676                 if (cursor_flags & HAMMER_RECF_EMBEDDED_DATA) {
 677                         /*
 678                          * Data embedded in record
 679                          */
 680                         nrec->base.data_offset = ((char *)bdata - (char *)orec);
 681                         KKASSERT(nrec->base.data_offset >= 0 &&
 682                                  nrec->base.data_offset + nrec->base.data_len <
 683                                   sizeof(*nrec));
 684                         nrec->base.data_offset += hammer_bclu_offset(cursor->record_buffer, nrec);
 685                 } else {
 686                         /*
 687                          * Data separate from record
 688                          */
 689                         nrec->base.data_offset = hammer_bclu_offset(cursor->data_buffer, bdata);
 690                         bcopy(data, bdata, nrec->base.data_len);
 691                         hammer_modify_buffer(cursor->data_buffer);
 692                 }
 693         }
 694         nrec->base.rec_id = 0;  /* XXX */
 695
 696         hammer_modify_buffer(cursor->record_buffer);
 697
 698         elm.leaf.base = nrec->base.base;
 699         elm.leaf.rec_offset = hammer_bclu_offset(cursor->record_buffer, nrec);
 700         elm.leaf.data_offset = nrec->base.data_offset;
 701         elm.leaf.data_len = nrec->base.data_len;
 702         elm.leaf.data_crc = nrec->base.data_crc;
 703
 704         error = hammer_btree_insert(cursor, &elm);
 705         if (error == 0)
 706                 goto done;
 707
 708         hammer_free_record_ptr(cursor->record_buffer, nrec);
 709 fail1:
 710         if (data && (cursor_flags & HAMMER_RECF_EMBEDDED_DATA) == 0) {
 711                 hammer_free_data_ptr(cursor->data_buffer, bdata,
 712                                      orec->base.data_len);
 713         }
 714 done:
 715         /* leave cursor intact */
 716         return(error);
 717 }
 718
 719 /*
 720  * Add the record to the inode's rec_tree.  The low 32 bits of a directory
 721  * entry's key is used to deal with hash collisions in the upper 32 bits.
 722  * A unique 64 bit key is generated in-memory and may be regenerated a
 723  * second time when the directory record is flushed to the on-disk B-Tree.
 724  *
 725  * A locked and referenced record is passed to this function.  This function
 726  * eats the lock and reference.
 727  */
 728 static
 729 int
 730 hammer_mem_add(struct hammer_transaction *trans, hammer_record_t record)
 731 {
 732         while (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) {
 733                 if (record->rec.base.base.rec_type != HAMMER_RECTYPE_DIRENTRY){
 734                         hammer_drop_mem_record(record, 1);
 735                         return (EEXIST);
 736                 }
 737                 if (++trans->hmp->namekey_iterator == 0)
 738                         ++trans->hmp->namekey_iterator;
 739                 record->rec.base.base.key &= ~(0xFFFFFFFFLL);
 740                 record->rec.base.base.key |= trans->hmp->namekey_iterator;
 741         }
 742         record->flags |= HAMMER_RECF_ONRBTREE;
 743         hammer_drop_mem_record(record, 0);
 744         return(0);
 745 }
 746
 747 /************************************************************************
 748  *                   HAMMER INODE MERGED-RECORD FUNCTIONS               *
 749  ************************************************************************
 750  *
 751  * These functions augment the B-Tree scanning functions in hammer_btree.c
 752  * by merging in-memory records with on-disk records.
 753  */
 754
 755 /*
 756  * Locate a particular record either in-memory or on-disk.
 757  *
 758  * NOTE: This is basically a standalone routine, hammer_ip_next() may
 759  * NOT be called to iterate results.
 760  */
 761 int
 762 hammer_ip_lookup(hammer_cursor_t cursor, struct hammer_inode *ip)
 763 {
 764         int error;
 765
 766         /*
 767          * If the element is in-memory return it without searching the
 768          * on-disk B-Tree
 769          */
 770         error = hammer_mem_lookup(cursor, ip);
 771         if (error == 0) {
 772                 cursor->record = &cursor->iprec->rec;
 773                 return(error);
 774         }
 775         if (error != ENOENT)
 776                 return(error);
 777
 778         /*
 779          * If the inode has on-disk components search the on-disk B-Tree.
 780          */
 781         if ((ip->flags & HAMMER_INODE_ONDISK) == 0)
 782                 return(error);
 783         error = hammer_btree_lookup(cursor);
 784         if (error == 0)
 785                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
 786         return(error);
 787 }
 788
 789 /*
 790  * Locate the first record within the cursor's key_beg/key_end range,
 791  * restricted to a particular inode.  0 is returned on success, ENOENT
 792  * if no records matched the requested range, or some other error.
 793  *
 794  * When 0 is returned hammer_ip_next() may be used to iterate additional
 795  * records within the requested range.
 796  */
 797 int
 798 hammer_ip_first(hammer_cursor_t cursor, struct hammer_inode *ip)
 799 {
 800         int error;
 801
 802         /*
 803          * Clean up fields and setup for merged scan
 804          */
 805         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
 806         cursor->flags |= HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM;
 807         cursor->flags |= HAMMER_CURSOR_DISKEOF | HAMMER_CURSOR_MEMEOF;
 808         if (cursor->iprec)
 809                 hammer_rel_mem_record(&cursor->iprec);
 810
 811         /*
 812          * Search the on-disk B-Tree.  hammer_btree_lookup() only does an
 813          * exact lookup so if we get ENOENT we have to call the iterate
 814          * function to validate the first record after the begin key.
 815          *
 816          * The ATEDISK flag is used by hammer_btree_iterate to determine
 817          * whether it must index forwards or not.  It is also used here
 818          * to select the next record from in-memory or on-disk.
 819          */
 820         if (ip->flags & HAMMER_INODE_ONDISK) {
 821                 error = hammer_btree_lookup(cursor);
 822                 if (error == ENOENT) {
 823                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
 824                         error = hammer_btree_iterate(cursor);
 825                 }
 826                 if (error && error != ENOENT)
 827                         return(error);
 828                 if (error == 0) {
 829                         cursor->flags &= ~HAMMER_CURSOR_DISKEOF;
 830                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
 831                 } else {
 832                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
 833                 }
 834         }
 835
 836         /*
 837          * Search the in-memory record list (Red-Black tree).  Unlike the
 838          * B-Tree search, mem_first checks for records in the range.
 839          */
 840         error = hammer_mem_first(cursor, ip);
 841         if (error && error != ENOENT)
 842                 return(error);
 843         if (error == 0) {
 844                 cursor->flags &= ~HAMMER_CURSOR_MEMEOF;
 845                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
 846         }
 847
 848         /*
 849          * This will return the first matching record.
 850          */
 851         return(hammer_ip_next(cursor));
 852 }
 853
 854 /*
 855  * Retrieve the next record in a merged iteration within the bounds of the
 856  * cursor.  This call may be made multiple times after the cursor has been
 857  * initially searched with hammer_ip_first().
 858  *
 859  * 0 is returned on success, ENOENT if no further records match the
 860  * requested range, or some other error code is returned.
 861  */
 862 int
 863 hammer_ip_next(hammer_cursor_t cursor)
 864 {
 865         hammer_btree_elm_t elm;
 866         hammer_record_t rec;
 867         int error;
 868         int r;
 869
 870         /*
 871          * Load the current on-disk and in-memory record.  If we ate any
 872          * records we have to get the next one.
 873          *
 874          * If we deleted the last on-disk record we had scanned ATEDISK will
 875          * be clear and DELBTREE will be set, forcing a call to iterate. The
 876          * fact that ATEDISK is clear causes iterate to re-test the 'current'
 877          * element.  If ATEDISK is set, iterate will skip the 'current'
 878          * element.
 879          *
 880          * Get the next on-disk record
 881          */
 882         if (cursor->flags & (HAMMER_CURSOR_ATEDISK|HAMMER_CURSOR_DELBTREE)) {
 883                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
 884                         error = hammer_btree_iterate(cursor);
 885                         if (error == 0)
 886                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
 887                         else
 888                                 cursor->flags |= HAMMER_CURSOR_DISKEOF |
 889                                                  HAMMER_CURSOR_ATEDISK;
 890                 }
 891         }
 892
 893         /*
 894          * Get the next in-memory record.  The record can be ripped out
 895          * of the RB tree so we maintain a scan_info structure to track
 896          * the next node.
 897          *
 898          * hammer_rec_scan_cmp:  Is the record still in our general range,
 899          *                       (non-inclusive of snapshot exclusions)?
 900          * hammer_rec_scan_callback: Is the record in our snapshot?
 901          */
 902         if (cursor->flags & HAMMER_CURSOR_ATEMEM) {
 903                 if ((cursor->flags & HAMMER_CURSOR_MEMEOF) == 0) {
 904                         hammer_rel_mem_record(&cursor->iprec);
 905                         rec = cursor->scan.node;        /* next node */
 906                         while (rec) {
 907                                 if (hammer_rec_scan_cmp(rec, cursor) != 0)
 908                                         break;
 909                                 if (hammer_rec_scan_callback(rec, cursor) != 0)
 910                                         break;
 911                                 rec = hammer_rec_rb_tree_RB_NEXT(rec);
 912                         }
 913                         if (cursor->iprec) {
 914                                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
 915                                 hammer_ref(&cursor->iprec->lock);
 916                                 cursor->scan.node =
 917                                         hammer_rec_rb_tree_RB_NEXT(rec);
 918                         } else {
 919                                 cursor->flags |= HAMMER_CURSOR_MEMEOF;
 920                         }
 921                 }
 922         }
 923
 924         /*
 925          * Extract either the disk or memory record depending on their
 926          * relative position.
 927          */
 928         error = 0;
 929         switch(cursor->flags & (HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM)) {
 930         case 0:
 931                 /*
 932                  * Both entries valid
 933                  */
 934                 elm = &cursor->node->ondisk->elms[cursor->index];
 935                 r = hammer_btree_cmp(&elm->base, &cursor->iprec->rec.base.base);
 936                 if (r < 0) {
 937                         error = hammer_btree_extract(cursor,
 938                                                      HAMMER_CURSOR_GET_RECORD);
 939                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
 940                         break;
 941                 }
 942                 /* fall through to the memory entry */
 943         case HAMMER_CURSOR_ATEDISK:
 944                 /*
 945                  * Only the memory entry is valid
 946                  */
 947                 cursor->record = &cursor->iprec->rec;
 948                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
 949                 break;
 950         case HAMMER_CURSOR_ATEMEM:
 951                 /*
 952                  * Only the disk entry is valid
 953                  */
 954                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
 955                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
 956                 break;
 957         default:
 958                 /*
 959                  * Neither entry is valid
 960                  *
 961                  * XXX error not set properly
 962                  */
 963                 cursor->record = NULL;
 964                 error = ENOENT;
 965                 break;
 966         }
 967         return(error);
 968 }
 969
 970 /*
 971  * Resolve the cursor->data pointer for the current cursor position in
 972  * a merged iteration.
 973  */
 974 int
 975 hammer_ip_resolve_data(hammer_cursor_t cursor)
 976 {
 977         int error;
 978
 979         if (cursor->iprec && cursor->record == &cursor->iprec->rec) {
 980                 cursor->data = cursor->iprec->data;
 981                 error = 0;
 982         } else {
 983                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA);
 984         }
 985         return(error);
 986 }
 987
 988 /*
 989  * Delete all records within the specified range for inode ip.
 990  *
 991  * NOTE: An unaligned range will cause new records to be added to cover
 992  * the edge cases. (XXX not implemented yet).
 993  *
 994  * NOTE: ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
 995  *
 996  * NOTE: Record keys for regular file data have to be special-cased since
 997  * they indicate the end of the range (key = base + bytes).
 998  *
 999  * NOTE: The spike structure must be filled in if we return ENOSPC.
1000  */
1001 int
1002 hammer_ip_delete_range(hammer_transaction_t trans, hammer_inode_t ip,
1003                        int64_t ran_beg, int64_t ran_end,
1004                        struct hammer_cursor **spike)
1005 {
1006         struct hammer_cursor cursor;
1007         hammer_record_ondisk_t rec;
1008         hammer_base_elm_t base;
1009         int error;
1010         int isregfile;
1011         int64_t off;
1012
1013         hammer_init_cursor_ip(&cursor, ip);
1014
1015         cursor.key_beg.obj_id = ip->obj_id;
1016         cursor.key_beg.create_tid = ip->obj_asof;
1017         cursor.key_beg.delete_tid = 0;
1018         cursor.key_beg.obj_type = 0;
1019
1020         cursor.key_end = cursor.key_beg;
1021         if (ip->ino_rec.base.base.obj_type == HAMMER_OBJTYPE_DBFILE) {
1022                 cursor.key_beg.key = ran_beg;
1023                 cursor.key_beg.rec_type = HAMMER_RECTYPE_DB;
1024                 cursor.key_end.rec_type = HAMMER_RECTYPE_DB;
1025                 cursor.key_end.key = ran_end;
1026                 isregfile = 0;
1027         } else {
1028                 /*
1029                  * The key in the B-Tree is (base+bytes), so the first possible
1030                  * matching key is ran_beg + 1.
1031                  */
1032                 int64_t tmp64;
1033
1034                 cursor.key_beg.key = ran_beg + 1;
1035                 cursor.key_beg.rec_type = HAMMER_RECTYPE_DATA;
1036                 cursor.key_end.rec_type = HAMMER_RECTYPE_DATA;
1037
1038                 tmp64 = ran_end + MAXPHYS + 1;  /* work around GCC-4 bug */
1039                 if (tmp64 < ran_end)
1040                         cursor.key_end.key = 0x7FFFFFFFFFFFFFFFLL;
1041                 else
1042                         cursor.key_end.key = ran_end + MAXPHYS + 1;
1043                 isregfile = 1;
1044         }
1045         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
1046
1047         error = hammer_ip_first(&cursor, ip);
1048
1049         /*
1050          * Iterate through matching records and mark them as deleted.
1051          */
1052         while (error == 0) {
1053                 rec = cursor.record;
1054                 base = &rec->base.base;
1055
1056                 KKASSERT(base->delete_tid == 0);
1057
1058                 /*
1059                  * There may be overlap cases for regular file data.  Also
1060                  * remember the key for a regular file record is the offset
1061                  * of the last byte of the record (base + len - 1), NOT the
1062                  * base offset.
1063                  */
1064 #if 0
1065                 kprintf("delete_range rec_type %02x\n", base->rec_type);
1066 #endif
1067                 if (base->rec_type == HAMMER_RECTYPE_DATA) {
1068 #if 0
1069                         kprintf("delete_range loop key %016llx\n",
1070                                 base->key - rec->base.data_len);
1071 #endif
1072                         off = base->key - rec->base.data_len;
1073                         /*
1074                          * Check the left edge case.  We currently do not
1075                          * split existing records.
1076                          */
1077                         if (off < ran_beg) {
1078                                 panic("hammer left edge case %016llx %d\n",
1079                                         base->key, rec->base.data_len);
1080                         }
1081
1082                         /*
1083                          * Check the right edge case.  Note that the
1084                          * record can be completely out of bounds, which
1085                          * terminates the search.
1086                          *
1087                          * base->key is exclusive of the right edge while
1088                          * ran_end is inclusive of the right edge.  The
1089                          * (key - data_len) left boundary is inclusive.
1090                          *
1091                          * XXX theory-check this test at some point, are
1092                          * we missing a + 1 somewhere?  Note that ran_end
1093                          * could overflow.
1094                          */
1095                         if (base->key > ran_end) {
1096                                 if (base->key - rec->base.data_len > ran_end) {
1097                                         kprintf("right edge OOB\n");
1098                                         break;
1099                                 }
1100                                 panic("hammer right edge case\n");
1101                         }
1102                 }
1103
1104                 /*
1105                  * Mark the record and B-Tree entry as deleted.  This will
1106                  * also physically delete the B-Tree entry, record, and
1107                  * data if the retention policy dictates.  The function
1108                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1109                  * uses to perform a fixup.
1110                  */
1111                 error = hammer_ip_delete_record(&cursor, trans->tid);
1112                 if (error)
1113                         break;
1114                 error = hammer_ip_next(&cursor);
1115         }
1116         hammer_done_cursor(&cursor);
1117         if (error == ENOENT)
1118                 error = 0;
1119         return(error);
1120 }
1121
1122 /*
1123  * Delete the record at the current cursor
1124  */
1125 int
1126 hammer_ip_delete_record(hammer_cursor_t cursor, hammer_tid_t tid)
1127 {
1128         hammer_btree_elm_t elm;
1129         hammer_mount_t hmp;
1130         int error;
1131
1132         /*
1133          * In-memory (unsynchronized) records can simply be freed.
1134          */
1135         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1136         if (cursor->record == &cursor->iprec->rec) {
1137                 hammer_free_mem_record(cursor->iprec); /* XXX */
1138                 return(0);
1139         }
1140
1141         /*
1142          * On-disk records are marked as deleted by updating their delete_tid.
1143          */
1144         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
1145         elm = NULL;
1146         hmp = cursor->node->cluster->volume->hmp;
1147
1148         if (error == 0) {
1149                 elm = &cursor->node->ondisk->elms[cursor->index];
1150                 cursor->record->base.base.delete_tid = tid;
1151                 elm->leaf.base.delete_tid = tid;
1152                 hammer_modify_buffer(cursor->record_buffer);
1153                 hammer_modify_node(cursor->node);
1154         }
1155
1156         /*
1157          * If we were mounted with the nohistory option, we physically
1158          * delete the record.
1159          */
1160         if (error == 0 && (hmp->hflags & HMNT_NOHISTORY)) {
1161                 int32_t rec_offset;
1162                 int32_t data_offset;
1163                 int32_t data_len;
1164                 hammer_cluster_t cluster;
1165
1166                 rec_offset = elm->leaf.rec_offset;
1167                 data_offset = elm->leaf.data_offset;
1168                 data_len = elm->leaf.data_len;
1169 #if 0
1170                 kprintf("hammer_ip_delete_record: %08x %08x/%d\n",
1171                         rec_offset, data_offset, data_len);
1172 #endif
1173                 cluster = cursor->node->cluster;
1174                 hammer_ref_cluster(cluster);
1175
1176                 error = hammer_btree_delete(cursor);
1177                 if (error == 0) {
1178                         /*
1179                          * This forces a fixup for the iteration because
1180                          * the cursor is now either sitting at the 'next'
1181                          * element or sitting at the end of a leaf.
1182                          */
1183                         if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1184                                 cursor->flags |= HAMMER_CURSOR_DELBTREE;
1185                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1186                         }
1187                         hammer_free_record(cluster, rec_offset);
1188                         if (data_offset && (data_offset - rec_offset < 0 ||
1189                             data_offset - rec_offset >= HAMMER_RECORD_SIZE)) {
1190                                 hammer_free_data(cluster, data_offset,data_len);
1191                         }
1192                 }
1193                 hammer_rel_cluster(cluster, 0);
1194                 if (error) {
1195                         kprintf("hammer_ip_delete_record: unable to physically delete the record!\n");
1196                         error = 0;
1197                 }
1198         }
1199         return(error);
1200 }
1201