sys/vfs/hammer/hammer_object.c

   1 /*
   2  * Copyright (c) 2007-2008 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.59 2008/05/18 01:48:50 dillon Exp $
  35  */
  36
  37 #include "hammer.h"
  38
  39 static int hammer_mem_add(hammer_transaction_t trans, hammer_record_t record);
  40 static int hammer_mem_lookup(hammer_cursor_t cursor);
  41 static int hammer_mem_first(hammer_cursor_t cursor);
  42
  43 /*
  44  * Red-black tree support.
  45  */
  46 static int
  47 hammer_rec_rb_compare(hammer_record_t rec1, hammer_record_t rec2)
  48 {
  49         if (rec1->leaf.base.rec_type < rec2->leaf.base.rec_type)
  50                 return(-1);
  51         if (rec1->leaf.base.rec_type > rec2->leaf.base.rec_type)
  52                 return(1);
  53
  54         if (rec1->leaf.base.key < rec2->leaf.base.key)
  55                 return(-1);
  56         if (rec1->leaf.base.key > rec2->leaf.base.key)
  57                 return(1);
  58
  59         if (rec1->leaf.base.create_tid == 0) {
  60                 if (rec2->leaf.base.create_tid == 0)
  61                         return(0);
  62                 return(1);
  63         }
  64         if (rec2->leaf.base.create_tid == 0)
  65                 return(-1);
  66
  67         if (rec1->leaf.base.create_tid < rec2->leaf.base.create_tid)
  68                 return(-1);
  69         if (rec1->leaf.base.create_tid > rec2->leaf.base.create_tid)
  70                 return(1);
  71
  72         /*
  73          * Never match against an item deleted by the front-end.
  74          */
  75         if (rec1->flags & HAMMER_RECF_DELETED_FE)
  76                 return(1);
  77         if (rec2->flags & HAMMER_RECF_DELETED_FE)
  78                 return(-1);
  79
  80         return(0);
  81 }
  82
  83 static int
  84 hammer_rec_compare(hammer_base_elm_t info, hammer_record_t rec)
  85 {
  86         if (info->rec_type < rec->leaf.base.rec_type)
  87                 return(-3);
  88         if (info->rec_type > rec->leaf.base.rec_type)
  89                 return(3);
  90
  91         if (info->key < rec->leaf.base.key)
  92                 return(-2);
  93         if (info->key > rec->leaf.base.key)
  94                 return(2);
  95
  96         if (info->create_tid == 0) {
  97                 if (rec->leaf.base.create_tid == 0)
  98                         return(0);
  99                 return(1);
 100         }
 101         if (rec->leaf.base.create_tid == 0)
 102                 return(-1);
 103         if (info->create_tid < rec->leaf.base.create_tid)
 104                 return(-1);
 105         if (info->create_tid > rec->leaf.base.create_tid)
 106                 return(1);
 107         return(0);
 108 }
 109
 110 /*
 111  * RB_SCAN comparison code for hammer_mem_first().  The argument order
 112  * is reversed so the comparison result has to be negated.  key_beg and
 113  * key_end are both range-inclusive.
 114  *
 115  * The creation timestamp can cause hammer_rec_compare() to return -1 or +1.
 116  * These do not stop the scan.
 117  *
 118  * Localized deletions are not cached in-memory.
 119  */
 120 static
 121 int
 122 hammer_rec_scan_cmp(hammer_record_t rec, void *data)
 123 {
 124         hammer_cursor_t cursor = data;
 125         int r;
 126
 127         r = hammer_rec_compare(&cursor->key_beg, rec);
 128         if (r > 1)
 129                 return(-1);
 130         r = hammer_rec_compare(&cursor->key_end, rec);
 131         if (r < -1)
 132                 return(1);
 133         return(0);
 134 }
 135
 136 /*
 137  * This compare function is used when simply looking up key_beg.
 138  */
 139 static
 140 int
 141 hammer_rec_find_cmp(hammer_record_t rec, void *data)
 142 {
 143         hammer_cursor_t cursor = data;
 144         int r;
 145
 146         r = hammer_rec_compare(&cursor->key_beg, rec);
 147         if (r > 1)
 148                 return(-1);
 149         if (r < -1)
 150                 return(1);
 151         return(0);
 152 }
 153
 154 RB_GENERATE(hammer_rec_rb_tree, hammer_record, rb_node, hammer_rec_rb_compare);
 155 RB_GENERATE_XLOOKUP(hammer_rec_rb_tree, INFO, hammer_record, rb_node,
 156                     hammer_rec_compare, hammer_base_elm_t);
 157
 158 /*
 159  * Allocate a record for the caller to finish filling in.  The record is
 160  * returned referenced.
 161  */
 162 hammer_record_t
 163 hammer_alloc_mem_record(hammer_inode_t ip, int data_len)
 164 {
 165         hammer_record_t record;
 166
 167         ++hammer_count_records;
 168         record = kmalloc(sizeof(*record), M_HAMMER, M_WAITOK | M_ZERO);
 169         record->flush_state = HAMMER_FST_IDLE;
 170         record->ip = ip;
 171         record->leaf.base.btype = HAMMER_BTREE_TYPE_RECORD;
 172         record->leaf.data_len = data_len;
 173         hammer_ref(&record->lock);
 174
 175         if (data_len) {
 176                 record->data = kmalloc(data_len, M_HAMMER, M_WAITOK | M_ZERO);
 177                 record->flags |= HAMMER_RECF_ALLOCDATA;
 178                 ++hammer_count_record_datas;
 179         }
 180
 181         return (record);
 182 }
 183
 184 void
 185 hammer_wait_mem_record(hammer_record_t record)
 186 {
 187         while (record->flush_state == HAMMER_FST_FLUSH) {
 188                 record->flags |= HAMMER_RECF_WANTED;
 189                 tsleep(record, 0, "hmrrc2", 0);
 190         }
 191 }
 192
 193 /*
 194  * Called from the backend, hammer_inode.c, after a record has been
 195  * flushed to disk.  The record has been exclusively locked by the
 196  * caller and interlocked with BE.
 197  *
 198  * We clean up the state, unlock, and release the record (the record
 199  * was referenced by the fact that it was in the HAMMER_FST_FLUSH state).
 200  */
 201 void
 202 hammer_flush_record_done(hammer_record_t record, int error)
 203 {
 204         hammer_inode_t target_ip;
 205
 206         KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
 207         KKASSERT(record->flags & HAMMER_RECF_INTERLOCK_BE);
 208
 209         if (error) {
 210                 /*
 211                  * An error occured, the backend was unable to sync the
 212                  * record to its media.  Leave the record intact.
 213                  */
 214                 Debugger("flush_record_done error");
 215         }
 216
 217         if (record->flags & HAMMER_RECF_DELETED_BE) {
 218                 if ((target_ip = record->target_ip) != NULL) {
 219                         TAILQ_REMOVE(&target_ip->target_list, record,
 220                                      target_entry);
 221                         record->target_ip = NULL;
 222                         hammer_test_inode(target_ip);
 223                 }
 224                 record->flush_state = HAMMER_FST_IDLE;
 225         } else {
 226                 if (record->target_ip) {
 227                         record->flush_state = HAMMER_FST_SETUP;
 228                         hammer_test_inode(record->ip);
 229                         hammer_test_inode(record->target_ip);
 230                 } else {
 231                         record->flush_state = HAMMER_FST_IDLE;
 232                 }
 233         }
 234         record->flags &= ~HAMMER_RECF_INTERLOCK_BE;
 235         if (record->flags & HAMMER_RECF_WANTED) {
 236                 record->flags &= ~HAMMER_RECF_WANTED;
 237                 wakeup(record);
 238         }
 239         hammer_rel_mem_record(record);
 240 }
 241
 242 /*
 243  * Release a memory record.  Records marked for deletion are immediately
 244  * removed from the RB-Tree but otherwise left intact until the last ref
 245  * goes away.
 246  */
 247 void
 248 hammer_rel_mem_record(struct hammer_record *record)
 249 {
 250         hammer_inode_t ip, target_ip;
 251
 252         hammer_unref(&record->lock);
 253
 254         if (record->flags & HAMMER_RECF_DELETED_FE) {
 255                 if (record->lock.refs == 0) {
 256                         KKASSERT(record->flush_state != HAMMER_FST_FLUSH);
 257
 258                         ip = record->ip;
 259                         if ((target_ip = record->target_ip) != NULL) {
 260                                 TAILQ_REMOVE(&target_ip->target_list,
 261                                              record, target_entry);
 262                                 record->target_ip = NULL;
 263                                 hammer_test_inode(target_ip);
 264                         }
 265
 266                         if (record->flags & HAMMER_RECF_ONRBTREE) {
 267                                 RB_REMOVE(hammer_rec_rb_tree,
 268                                           &record->ip->rec_tree,
 269                                           record);
 270                                 record->flags &= ~HAMMER_RECF_ONRBTREE;
 271                                 if (RB_EMPTY(&record->ip->rec_tree)) {
 272                                         record->ip->flags &= ~HAMMER_INODE_XDIRTY;
 273                                         hammer_test_inode(record->ip);
 274                                 }
 275                         }
 276                         if (record->flags & HAMMER_RECF_ALLOCDATA) {
 277                                 --hammer_count_record_datas;
 278                                 kfree(record->data, M_HAMMER);
 279                                 record->flags &= ~HAMMER_RECF_ALLOCDATA;
 280                         }
 281                         record->data = NULL;
 282                         --hammer_count_records;
 283                         kfree(record, M_HAMMER);
 284                         return;
 285                 }
 286         }
 287 }
 288
 289 /*
 290  * Record visibility depends on whether the record is being accessed by
 291  * the backend or the frontend.
 292  *
 293  * Return non-zero if the record is visible, zero if it isn't or if it is
 294  * deleted.
 295  */
 296 static __inline
 297 int
 298 hammer_ip_iterate_mem_good(hammer_cursor_t cursor, hammer_record_t record)
 299 {
 300         if (cursor->flags & HAMMER_CURSOR_BACKEND) {
 301                 if (record->flags & HAMMER_RECF_DELETED_BE)
 302                         return(0);
 303 #if 0
 304                 if ((record->flags & HAMMER_RECF_INTERLOCK_BE) == 0)
 305                         return(0);
 306 #endif
 307         } else {
 308                 if (record->flags & HAMMER_RECF_DELETED_FE)
 309                         return(0);
 310         }
 311         return(1);
 312 }
 313
 314 /*
 315  * This callback is used as part of the RB_SCAN function for in-memory
 316  * records.  We terminate it (return -1) as soon as we get a match.
 317  *
 318  * This routine is used by frontend code.
 319  *
 320  * The primary compare code does not account for ASOF lookups.  This
 321  * code handles that case as well as a few others.
 322  */
 323 static
 324 int
 325 hammer_rec_scan_callback(hammer_record_t rec, void *data)
 326 {
 327         hammer_cursor_t cursor = data;
 328
 329         /*
 330          * We terminate on success, so this should be NULL on entry.
 331          */
 332         KKASSERT(cursor->iprec == NULL);
 333
 334         /*
 335          * Skip if the record was marked deleted.
 336          */
 337         if (hammer_ip_iterate_mem_good(cursor, rec) == 0)
 338                 return(0);
 339
 340         /*
 341          * Skip if not visible due to our as-of TID
 342          */
 343         if (cursor->flags & HAMMER_CURSOR_ASOF) {
 344                 if (cursor->asof < rec->leaf.base.create_tid)
 345                         return(0);
 346                 if (rec->leaf.base.delete_tid &&
 347                     cursor->asof >= rec->leaf.base.delete_tid) {
 348                         return(0);
 349                 }
 350         }
 351
 352         /*
 353          * If the record is queued to the flusher we have to block until
 354          * it isn't.  Otherwise we may see duplication between our memory
 355          * cache and the media.
 356          */
 357         hammer_ref(&rec->lock);
 358
 359 #warning "This deadlocks"
 360 #if 0
 361         if (rec->flush_state == HAMMER_FST_FLUSH)
 362                 hammer_wait_mem_record(rec);
 363 #endif
 364
 365         /*
 366          * The record may have been deleted while we were blocked.
 367          */
 368         if (hammer_ip_iterate_mem_good(cursor, rec) == 0) {
 369                 hammer_rel_mem_record(rec);
 370                 return(0);
 371         }
 372
 373         /*
 374          * Set the matching record and stop the scan.
 375          */
 376         cursor->iprec = rec;
 377         return(-1);
 378 }
 379
 380
 381 /*
 382  * Lookup an in-memory record given the key specified in the cursor.  Works
 383  * just like hammer_btree_lookup() but operates on an inode's in-memory
 384  * record list.
 385  *
 386  * The lookup must fail if the record is marked for deferred deletion.
 387  */
 388 static
 389 int
 390 hammer_mem_lookup(hammer_cursor_t cursor)
 391 {
 392         int error;
 393
 394         KKASSERT(cursor->ip);
 395         if (cursor->iprec) {
 396                 hammer_rel_mem_record(cursor->iprec);
 397                 cursor->iprec = NULL;
 398         }
 399         hammer_rec_rb_tree_RB_SCAN(&cursor->ip->rec_tree, hammer_rec_find_cmp,
 400                                    hammer_rec_scan_callback, cursor);
 401
 402         if (cursor->iprec == NULL)
 403                 error = ENOENT;
 404         else
 405                 error = 0;
 406         return(error);
 407 }
 408
 409 /*
 410  * hammer_mem_first() - locate the first in-memory record matching the
 411  * cursor within the bounds of the key range.
 412  */
 413 static
 414 int
 415 hammer_mem_first(hammer_cursor_t cursor)
 416 {
 417         hammer_inode_t ip;
 418
 419         ip = cursor->ip;
 420         KKASSERT(ip != NULL);
 421
 422         if (cursor->iprec) {
 423                 hammer_rel_mem_record(cursor->iprec);
 424                 cursor->iprec = NULL;
 425         }
 426
 427         hammer_rec_rb_tree_RB_SCAN(&ip->rec_tree, hammer_rec_scan_cmp,
 428                                    hammer_rec_scan_callback, cursor);
 429
 430         /*
 431          * Adjust scan.node and keep it linked into the RB-tree so we can
 432          * hold the cursor through third party modifications of the RB-tree.
 433          */
 434         if (cursor->iprec)
 435                 return(0);
 436         return(ENOENT);
 437 }
 438
 439 void
 440 hammer_mem_done(hammer_cursor_t cursor)
 441 {
 442         if (cursor->iprec) {
 443                 hammer_rel_mem_record(cursor->iprec);
 444                 cursor->iprec = NULL;
 445         }
 446 }
 447
 448 /************************************************************************
 449  *                   HAMMER IN-MEMORY RECORD FUNCTIONS                  *
 450  ************************************************************************
 451  *
 452  * These functions manipulate in-memory records.  Such records typically
 453  * exist prior to being committed to disk or indexed via the on-disk B-Tree.
 454  */
 455
 456 /*
 457  * Add a directory entry (dip,ncp) which references inode (ip).
 458  *
 459  * Note that the low 32 bits of the namekey are set temporarily to create
 460  * a unique in-memory record, and may be modified a second time when the
 461  * record is synchronized to disk.  In particular, the low 32 bits cannot be
 462  * all 0's when synching to disk, which is not handled here.
 463  */
 464 int
 465 hammer_ip_add_directory(struct hammer_transaction *trans,
 466                      struct hammer_inode *dip, struct namecache *ncp,
 467                      struct hammer_inode *ip)
 468 {
 469         hammer_record_t record;
 470         int error;
 471         int bytes;
 472
 473         bytes = ncp->nc_nlen;   /* NOTE: terminating \0 is NOT included */
 474         record = hammer_alloc_mem_record(dip, HAMMER_ENTRY_SIZE(bytes));
 475         if (++trans->hmp->namekey_iterator == 0)
 476                 ++trans->hmp->namekey_iterator;
 477
 478         record->type = HAMMER_MEM_RECORD_ADD;
 479         record->leaf.base.localization = HAMMER_LOCALIZE_MISC;
 480         record->leaf.base.obj_id = dip->obj_id;
 481         record->leaf.base.key = hammer_directory_namekey(ncp->nc_name, bytes);
 482         record->leaf.base.key += trans->hmp->namekey_iterator;
 483         record->leaf.base.rec_type = HAMMER_RECTYPE_DIRENTRY;
 484         record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
 485         record->data->entry.obj_id = ip->obj_id;
 486         bcopy(ncp->nc_name, record->data->entry.name, bytes);
 487
 488         ++ip->ino_data.nlinks;
 489         hammer_modify_inode(trans, ip, HAMMER_INODE_DDIRTY);
 490
 491         /*
 492          * The target inode and the directory entry are bound together.
 493          */
 494         record->target_ip = ip;
 495         record->flush_state = HAMMER_FST_SETUP;
 496         TAILQ_INSERT_TAIL(&ip->target_list, record, target_entry);
 497
 498         /*
 499          * The inode now has a dependancy and must be taken out of the idle
 500          * state.  An inode not in an idle state is given an extra reference.
 501          */
 502         if (ip->flush_state == HAMMER_FST_IDLE) {
 503                 hammer_ref(&ip->lock);
 504                 ip->flush_state = HAMMER_FST_SETUP;
 505         }
 506
 507         /* NOTE: copies record->data */
 508         error = hammer_mem_add(trans, record);
 509         return(error);
 510 }
 511
 512 /*
 513  * Delete the directory entry and update the inode link count.  The
 514  * cursor must be seeked to the directory entry record being deleted.
 515  *
 516  * The related inode should be share-locked by the caller.  The caller is
 517  * on the frontend.
 518  *
 519  * This function can return EDEADLK requiring the caller to terminate
 520  * the cursor, any locks, wait on the returned record, and retry.
 521  */
 522 int
 523 hammer_ip_del_directory(struct hammer_transaction *trans,
 524                      hammer_cursor_t cursor, struct hammer_inode *dip,
 525                      struct hammer_inode *ip)
 526 {
 527         hammer_record_t record;
 528         int error;
 529
 530         if (cursor->leaf == &cursor->iprec->leaf) {
 531                 /*
 532                  * In-memory (unsynchronized) records can simply be freed.
 533                  * Even though the HAMMER_RECF_DELETED_FE flag is ignored
 534                  * by the backend, we must still avoid races against the
 535                  * backend potentially syncing the record to the media.
 536                  *
 537                  * We cannot call hammer_ip_delete_record(), that routine may
 538                  * only be called from the backend.
 539                  */
 540                 record = cursor->iprec;
 541                 if (record->flags & HAMMER_RECF_INTERLOCK_BE) {
 542                         KKASSERT(cursor->deadlk_rec == NULL);
 543                         hammer_ref(&record->lock);
 544                         cursor->deadlk_rec = record;
 545                         error = EDEADLK;
 546                 } else {
 547                         KKASSERT(record->type == HAMMER_MEM_RECORD_ADD);
 548                         record->flags |= HAMMER_RECF_DELETED_FE;
 549                         error = 0;
 550                 }
 551         } else {
 552                 /*
 553                  * If the record is on-disk we have to queue the deletion by
 554                  * the record's key.  This also causes lookups to skip the
 555                  * record.
 556                  */
 557                 KKASSERT(dip->flags &
 558                          (HAMMER_INODE_ONDISK | HAMMER_INODE_DONDISK));
 559                 record = hammer_alloc_mem_record(dip, 0);
 560                 record->type = HAMMER_MEM_RECORD_DEL;
 561                 record->leaf.base = cursor->leaf->base;
 562
 563                 record->target_ip = ip;
 564                 record->flush_state = HAMMER_FST_SETUP;
 565                 TAILQ_INSERT_TAIL(&ip->target_list, record, target_entry);
 566
 567                 /*
 568                  * The inode now has a dependancy and must be taken out of
 569                  * the idle state.  An inode not in an idle state is given
 570                  * an extra reference.
 571                  */
 572                 if (ip->flush_state == HAMMER_FST_IDLE) {
 573                         hammer_ref(&ip->lock);
 574                         ip->flush_state = HAMMER_FST_SETUP;
 575                 }
 576
 577                 error = hammer_mem_add(trans, record);
 578         }
 579
 580         /*
 581          * One less link.  The file may still be open in the OS even after
 582          * all links have gone away.
 583          *
 584          * We have to terminate the cursor before syncing the inode to
 585          * avoid deadlocking against ourselves.  XXX this may no longer
 586          * be true.
 587          *
 588          * If nlinks drops to zero and the vnode is inactive (or there is
 589          * no vnode), call hammer_inode_unloadable_check() to zonk the
 590          * inode.  If we don't do this here the inode will not be destroyed
 591          * on-media until we unmount.
 592          */
 593         if (error == 0) {
 594                 --ip->ino_data.nlinks;
 595                 hammer_modify_inode(trans, ip, HAMMER_INODE_DDIRTY);
 596                 if (ip->ino_data.nlinks == 0 &&
 597                     (ip->vp == NULL || (ip->vp->v_flag & VINACTIVE))) {
 598                         hammer_done_cursor(cursor);
 599                         hammer_inode_unloadable_check(ip, 1);
 600                         hammer_flush_inode(ip, 0);
 601                 }
 602
 603         }
 604         return(error);
 605 }
 606
 607 /*
 608  * Add a record to an inode.
 609  *
 610  * The caller must allocate the record with hammer_alloc_mem_record(ip) and
 611  * initialize the following additional fields:
 612  *
 613  * The related inode should be share-locked by the caller.  The caller is
 614  * on the frontend.
 615  *
 616  * record->rec.entry.base.base.key
 617  * record->rec.entry.base.base.rec_type
 618  * record->rec.entry.base.base.data_len
 619  * record->data         (a copy will be kmalloc'd if it cannot be embedded)
 620  */
 621 int
 622 hammer_ip_add_record(struct hammer_transaction *trans, hammer_record_t record)
 623 {
 624         hammer_inode_t ip = record->ip;
 625         int error;
 626
 627         KKASSERT(record->leaf.base.localization != 0);
 628         record->leaf.base.obj_id = ip->obj_id;
 629         record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
 630         error = hammer_mem_add(trans, record);
 631         return(error);
 632 }
 633
 634 /*
 635  * Sync data from a buffer cache buffer (typically) to the filesystem.  This
 636  * is called via the strategy called from a cached data source.  This code
 637  * is responsible for actually writing a data record out to the disk.
 638  *
 639  * This can only occur non-historically (i.e. 'current' data only).
 640  *
 641  * The file offset must be HAMMER_BUFSIZE aligned but the data length
 642  * can be truncated.  The record (currently) always represents a BUFSIZE
 643  * swath of space whether the data is truncated or not.
 644  */
 645 int
 646 hammer_ip_sync_data(hammer_cursor_t cursor, hammer_inode_t ip,
 647                        int64_t offset, void *data, int bytes)
 648 {
 649         hammer_transaction_t trans = cursor->trans;
 650         struct hammer_btree_leaf_elm elm;
 651         hammer_off_t data_offset;
 652         void *bdata;
 653         int error;
 654
 655         KKASSERT((offset & HAMMER_BUFMASK) == 0);
 656         KKASSERT(trans->type == HAMMER_TRANS_FLS);
 657         KKASSERT(bytes != 0);
 658 retry:
 659         hammer_normalize_cursor(cursor);
 660         cursor->key_beg.localization = HAMMER_LOCALIZE_MISC;
 661         cursor->key_beg.obj_id = ip->obj_id;
 662         cursor->key_beg.key = offset + bytes;
 663         cursor->key_beg.create_tid = trans->tid;
 664         cursor->key_beg.delete_tid = 0;
 665         cursor->key_beg.rec_type = HAMMER_RECTYPE_DATA;
 666         cursor->asof = trans->tid;
 667         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
 668         cursor->flags |= HAMMER_CURSOR_INSERT;
 669         cursor->flags |= HAMMER_CURSOR_BACKEND;
 670
 671         /*
 672          * Issue a lookup to position the cursor.
 673          */
 674         error = hammer_btree_lookup(cursor);
 675         if (error == 0) {
 676                 kprintf("hammer_ip_sync_data: duplicate data at "
 677                         "(%lld,%d) tid %016llx\n",
 678                         offset, bytes, trans->tid);
 679                 hammer_print_btree_elm(&cursor->node->ondisk->
 680                                         elms[cursor->index],
 681                                        HAMMER_BTREE_TYPE_LEAF, cursor->index);
 682                 panic("Duplicate data");
 683                 error = EIO;
 684         }
 685         if (error != ENOENT)
 686                 goto done;
 687
 688         /*
 689          * Allocate our data.  The data buffer is not marked modified (yet)
 690          */
 691         bdata = hammer_alloc_data(trans, bytes, &data_offset,
 692                                   &cursor->data_buffer, &error);
 693
 694         if (bdata == NULL)
 695                 goto done;
 696
 697         /*
 698          * Fill everything in and insert our B-Tree node.
 699          *
 700          * NOTE: hammer_alloc_data() has already marked the data buffer
 701          * as modified.  If we do it again we will generate unnecessary
 702          * undo elements.
 703          */
 704         elm.base.btype = HAMMER_BTREE_TYPE_RECORD;
 705         elm.base.localization = HAMMER_LOCALIZE_MISC;
 706         elm.base.obj_id = ip->obj_id;
 707         elm.base.key = offset + bytes;
 708         elm.base.create_tid = trans->tid;
 709         elm.base.delete_tid = 0;
 710         elm.base.rec_type = HAMMER_RECTYPE_DATA;
 711         elm.atime = 0;
 712         elm.data_offset = data_offset;
 713         elm.data_len = bytes;
 714         elm.data_crc = crc32(data, bytes);
 715
 716         hammer_modify_buffer(trans, cursor->data_buffer, NULL, 0);
 717         bcopy(data, bdata, bytes);
 718         hammer_modify_buffer_done(cursor->data_buffer);
 719
 720         /*
 721          * Data records can wind up on-disk before the inode itself is
 722          * on-disk.  One must assume data records may be on-disk if either
 723          * HAMMER_INODE_DONDISK or HAMMER_INODE_ONDISK is set
 724          */
 725         ip->flags |= HAMMER_INODE_DONDISK;
 726
 727         error = hammer_btree_insert(cursor, &elm);
 728         if (error == 0)
 729                 goto done;
 730
 731         hammer_blockmap_free(trans, data_offset, bytes);
 732 done:
 733         if (error == EDEADLK) {
 734                 hammer_done_cursor(cursor);
 735                 error = hammer_init_cursor(trans, cursor, &ip->cache[0], ip);
 736                 if (error == 0)
 737                         goto retry;
 738         }
 739         return(error);
 740 }
 741
 742 #if 0
 743 /*
 744  * Sync an in-memory record to the disk.  This is called by the backend.
 745  * This code is responsible for actually writing a record out to the disk.
 746  *
 747  * This routine can only be called by the backend and the record
 748  * must have been interlocked with BE.  It will remain interlocked on
 749  * return.  If no error occurs the record will be marked deleted but
 750  * the caller is responsible for its final disposition.
 751  *
 752  * Multiple calls may be aggregated with the same cursor using
 753  * hammer_ip_sync_record_cursor().  The caller must handle EDEADLK
 754  * in that case.
 755  */
 756 int
 757 hammer_ip_sync_record(hammer_transaction_t trans, hammer_record_t record)
 758 {
 759         struct hammer_cursor cursor;
 760         int error;
 761
 762         do {
 763                 error = hammer_init_cursor(trans, &cursor,
 764                                            &record->ip->cache[0], record->ip);
 765                 if (error) {
 766                         KKASSERT(0);
 767                         hammer_done_cursor(&cursor);
 768                         return(error);
 769                 }
 770                 error = hammer_ip_sync_record_cursor(&cursor, record);
 771                 hammer_done_cursor(&cursor);
 772         } while (error == EDEADLK);
 773         return (error);
 774 }
 775
 776 #endif
 777
 778 int
 779 hammer_ip_sync_record_cursor(hammer_cursor_t cursor, hammer_record_t record)
 780 {
 781         hammer_transaction_t trans = cursor->trans;
 782         void *bdata;
 783         int error;
 784
 785         KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
 786         KKASSERT(record->flags & HAMMER_RECF_INTERLOCK_BE);
 787         KKASSERT(record->leaf.base.localization != 0);
 788
 789         hammer_normalize_cursor(cursor);
 790         cursor->key_beg = record->leaf.base;
 791         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
 792         cursor->flags |= HAMMER_CURSOR_BACKEND;
 793         cursor->flags &= ~HAMMER_CURSOR_INSERT;
 794
 795         /*
 796          * Records can wind up on-media before the inode itself is on-media.
 797          * Flag the case.
 798          */
 799         record->ip->flags |= HAMMER_INODE_DONDISK;
 800
 801         /*
 802          * If we are deleting an exact match must be found on-disk.
 803          */
 804         if (record->type == HAMMER_MEM_RECORD_DEL) {
 805                 error = hammer_btree_lookup(cursor);
 806                 if (error == 0) {
 807                         error = hammer_ip_delete_record(cursor, trans->tid);
 808                         if (error == 0) {
 809                                 record->flags |= HAMMER_RECF_DELETED_FE;
 810                                 record->flags |= HAMMER_RECF_DELETED_BE;
 811                         }
 812                 }
 813                 goto done;
 814         }
 815
 816         /*
 817          * We are inserting.
 818          *
 819          * Issue a lookup to position the cursor and locate the cluster.  The
 820          * target key should not exist.  If we are creating a directory entry
 821          * we may have to iterate the low 32 bits of the key to find an unused
 822          * key.
 823          */
 824         cursor->flags |= HAMMER_CURSOR_INSERT;
 825
 826         for (;;) {
 827                 error = hammer_btree_lookup(cursor);
 828                 if (hammer_debug_inode)
 829                         kprintf("DOINSERT LOOKUP %d\n", error);
 830                 if (error)
 831                         break;
 832                 if (record->leaf.base.rec_type != HAMMER_RECTYPE_DIRENTRY) {
 833                         kprintf("hammer_ip_sync_record: duplicate rec "
 834                                 "at (%016llx)\n", record->leaf.base.key);
 835                         Debugger("duplicate record1");
 836                         error = EIO;
 837                         break;
 838                 }
 839                 if (++trans->hmp->namekey_iterator == 0)
 840                         ++trans->hmp->namekey_iterator;
 841                 record->leaf.base.key &= ~(0xFFFFFFFFLL);
 842                 record->leaf.base.key |= trans->hmp->namekey_iterator;
 843                 cursor->key_beg.key = record->leaf.base.key;
 844         }
 845         if (error != ENOENT)
 846                 goto done;
 847
 848         /*
 849          * Allocate the record and data.  The result buffers will be
 850          * marked as being modified and further calls to
 851          * hammer_modify_buffer() will result in unneeded UNDO records.
 852          *
 853          * Support zero-fill records (data == NULL and data_len != 0)
 854          */
 855         if (record->data && record->leaf.data_len) {
 856                 bdata = hammer_alloc_data(trans, record->leaf.data_len,
 857                                           &record->leaf.data_offset,
 858                                           &cursor->data_buffer, &error);
 859                 if (bdata == NULL)
 860                         goto done;
 861                 record->leaf.data_crc = crc32(record->data,
 862                                               record->leaf.data_len);
 863                 hammer_modify_buffer(trans, cursor->data_buffer, NULL, 0);
 864                 bcopy(record->data, bdata, record->leaf.data_len);
 865                 hammer_modify_buffer_done(cursor->data_buffer);
 866         } else {
 867                 /* record->leaf.data_len can be non-zero for future zero-fill */
 868                 record->leaf.data_offset = 0;
 869                 record->leaf.data_crc = 0;
 870         }
 871
 872         error = hammer_btree_insert(cursor, &record->leaf);
 873         if (hammer_debug_inode)
 874                 kprintf("BTREE INSERT error %d @ %016llx:%d\n", error, cursor->node->node_offset, cursor->index);
 875
 876         /*
 877          * This occurs when the frontend creates a record and queues it to
 878          * the backend, then tries to delete the record.  The backend must
 879          * still sync the record to the media as if it were not deleted,
 880          * but must interlock with the frontend to ensure that the
 881          * synchronized record is not visible to the frontend, which means
 882          * converting it from an ADD record to a DEL record.
 883          *
 884          * The DEL record then masks the record synced to disk until another
 885          * round can delete it for real.
 886          */
 887         if (error == 0) {
 888                 if (record->flags & HAMMER_RECF_CONVERT_DELETE) {
 889                         KKASSERT(record->type == HAMMER_MEM_RECORD_ADD);
 890                         record->flags &= ~HAMMER_RECF_DELETED_FE;
 891                         record->type = HAMMER_MEM_RECORD_DEL;
 892                         KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
 893                         record->flags &= ~HAMMER_RECF_CONVERT_DELETE;
 894                         /* hammer_flush_record_done takes care of the rest */
 895                 } else {
 896                         record->flags |= HAMMER_RECF_DELETED_FE;
 897                         record->flags |= HAMMER_RECF_DELETED_BE;
 898                 }
 899         } else {
 900                 if (record->leaf.data_offset) {
 901                         hammer_blockmap_free(trans, record->leaf.data_offset,
 902                                              record->leaf.data_len);
 903                 }
 904         }
 905
 906 done:
 907         return(error);
 908 }
 909
 910 /*
 911  * Add the record to the inode's rec_tree.  The low 32 bits of a directory
 912  * entry's key is used to deal with hash collisions in the upper 32 bits.
 913  * A unique 64 bit key is generated in-memory and may be regenerated a
 914  * second time when the directory record is flushed to the on-disk B-Tree.
 915  *
 916  * A referenced record is passed to this function.  This function
 917  * eats the reference.  If an error occurs the record will be deleted.
 918  *
 919  * A copy of the temporary record->data pointer provided by the caller
 920  * will be made.
 921  */
 922 static
 923 int
 924 hammer_mem_add(struct hammer_transaction *trans, hammer_record_t record)
 925 {
 926         /*
 927          * Make a private copy of record->data
 928          */
 929         if (record->data)
 930                 KKASSERT(record->flags & HAMMER_RECF_ALLOCDATA);
 931
 932         /*
 933          * Insert into the RB tree, find an unused iterator if this is
 934          * a directory entry.
 935          */
 936         while (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) {
 937                 if (record->leaf.base.rec_type != HAMMER_RECTYPE_DIRENTRY){
 938                         record->flags |= HAMMER_RECF_DELETED_FE;
 939                         hammer_rel_mem_record(record);
 940                         return (EEXIST);
 941                 }
 942                 if (++trans->hmp->namekey_iterator == 0)
 943                         ++trans->hmp->namekey_iterator;
 944                 record->leaf.base.key &= ~(0xFFFFFFFFLL);
 945                 record->leaf.base.key |= trans->hmp->namekey_iterator;
 946         }
 947         record->flags |= HAMMER_RECF_ONRBTREE;
 948         hammer_modify_inode(trans, record->ip, HAMMER_INODE_XDIRTY);
 949         hammer_rel_mem_record(record);
 950         return(0);
 951 }
 952
 953 /************************************************************************
 954  *                   HAMMER INODE MERGED-RECORD FUNCTIONS               *
 955  ************************************************************************
 956  *
 957  * These functions augment the B-Tree scanning functions in hammer_btree.c
 958  * by merging in-memory records with on-disk records.
 959  */
 960
 961 /*
 962  * Locate a particular record either in-memory or on-disk.
 963  *
 964  * NOTE: This is basically a standalone routine, hammer_ip_next() may
 965  * NOT be called to iterate results.
 966  */
 967 int
 968 hammer_ip_lookup(hammer_cursor_t cursor)
 969 {
 970         int error;
 971
 972         /*
 973          * If the element is in-memory return it without searching the
 974          * on-disk B-Tree
 975          */
 976         KKASSERT(cursor->ip);
 977         error = hammer_mem_lookup(cursor);
 978         if (error == 0) {
 979                 cursor->leaf = &cursor->iprec->leaf;
 980                 return(error);
 981         }
 982         if (error != ENOENT)
 983                 return(error);
 984
 985         /*
 986          * If the inode has on-disk components search the on-disk B-Tree.
 987          */
 988         if ((cursor->ip->flags & (HAMMER_INODE_ONDISK|HAMMER_INODE_DONDISK)) == 0)
 989                 return(error);
 990         error = hammer_btree_lookup(cursor);
 991         if (error == 0)
 992                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
 993         return(error);
 994 }
 995
 996 /*
 997  * Locate the first record within the cursor's key_beg/key_end range,
 998  * restricted to a particular inode.  0 is returned on success, ENOENT
 999  * if no records matched the requested range, or some other error.
1000  *
1001  * When 0 is returned hammer_ip_next() may be used to iterate additional
1002  * records within the requested range.
1003  *
1004  * This function can return EDEADLK, requiring the caller to terminate
1005  * the cursor and try again.
1006  */
1007 int
1008 hammer_ip_first(hammer_cursor_t cursor)
1009 {
1010         hammer_inode_t ip = cursor->ip;
1011         int error;
1012
1013         KKASSERT(ip != NULL);
1014
1015         /*
1016          * Clean up fields and setup for merged scan
1017          */
1018         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1019         cursor->flags |= HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM;
1020         cursor->flags |= HAMMER_CURSOR_DISKEOF | HAMMER_CURSOR_MEMEOF;
1021         if (cursor->iprec) {
1022                 hammer_rel_mem_record(cursor->iprec);
1023                 cursor->iprec = NULL;
1024         }
1025
1026         /*
1027          * Search the on-disk B-Tree.  hammer_btree_lookup() only does an
1028          * exact lookup so if we get ENOENT we have to call the iterate
1029          * function to validate the first record after the begin key.
1030          *
1031          * The ATEDISK flag is used by hammer_btree_iterate to determine
1032          * whether it must index forwards or not.  It is also used here
1033          * to select the next record from in-memory or on-disk.
1034          *
1035          * EDEADLK can only occur if the lookup hit an empty internal
1036          * element and couldn't delete it.  Since this could only occur
1037          * in-range, we can just iterate from the failure point.
1038          */
1039         if (ip->flags & (HAMMER_INODE_ONDISK|HAMMER_INODE_DONDISK)) {
1040                 error = hammer_btree_lookup(cursor);
1041                 if (error == ENOENT || error == EDEADLK) {
1042                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1043                         if (hammer_debug_general & 0x2000)
1044                                 kprintf("error %d node %p %016llx index %d\n", error, cursor->node, cursor->node->node_offset, cursor->index);
1045                         error = hammer_btree_iterate(cursor);
1046                 }
1047                 if (error && error != ENOENT)
1048                         return(error);
1049                 if (error == 0) {
1050                         cursor->flags &= ~HAMMER_CURSOR_DISKEOF;
1051                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1052                 } else {
1053                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
1054                 }
1055         }
1056
1057         /*
1058          * Search the in-memory record list (Red-Black tree).  Unlike the
1059          * B-Tree search, mem_first checks for records in the range.
1060          */
1061         error = hammer_mem_first(cursor);
1062         if (error && error != ENOENT)
1063                 return(error);
1064         if (error == 0) {
1065                 cursor->flags &= ~HAMMER_CURSOR_MEMEOF;
1066                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
1067                 if (hammer_ip_iterate_mem_good(cursor, cursor->iprec) == 0)
1068                         cursor->flags |= HAMMER_CURSOR_ATEMEM;
1069         }
1070
1071         /*
1072          * This will return the first matching record.
1073          */
1074         return(hammer_ip_next(cursor));
1075 }
1076
1077 /*
1078  * Retrieve the next record in a merged iteration within the bounds of the
1079  * cursor.  This call may be made multiple times after the cursor has been
1080  * initially searched with hammer_ip_first().
1081  *
1082  * 0 is returned on success, ENOENT if no further records match the
1083  * requested range, or some other error code is returned.
1084  */
1085 int
1086 hammer_ip_next(hammer_cursor_t cursor)
1087 {
1088         hammer_btree_elm_t elm;
1089         hammer_record_t rec, save;
1090         int error;
1091         int r;
1092
1093 next_btree:
1094         /*
1095          * Load the current on-disk and in-memory record.  If we ate any
1096          * records we have to get the next one.
1097          *
1098          * If we deleted the last on-disk record we had scanned ATEDISK will
1099          * be clear and DELBTREE will be set, forcing a call to iterate. The
1100          * fact that ATEDISK is clear causes iterate to re-test the 'current'
1101          * element.  If ATEDISK is set, iterate will skip the 'current'
1102          * element.
1103          *
1104          * Get the next on-disk record
1105          */
1106         if (cursor->flags & (HAMMER_CURSOR_ATEDISK|HAMMER_CURSOR_DELBTREE)) {
1107                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1108                         error = hammer_btree_iterate(cursor);
1109                         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1110                         if (error == 0)
1111                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1112                         else
1113                                 cursor->flags |= HAMMER_CURSOR_DISKEOF |
1114                                                  HAMMER_CURSOR_ATEDISK;
1115                 }
1116         }
1117
1118 next_memory:
1119         /*
1120          * Get the next in-memory record.  The record can be ripped out
1121          * of the RB tree so we maintain a scan_info structure to track
1122          * the next node.
1123          *
1124          * hammer_rec_scan_cmp:  Is the record still in our general range,
1125          *                       (non-inclusive of snapshot exclusions)?
1126          * hammer_rec_scan_callback: Is the record in our snapshot?
1127          */
1128         if (cursor->flags & HAMMER_CURSOR_ATEMEM) {
1129                 if ((cursor->flags & HAMMER_CURSOR_MEMEOF) == 0) {
1130                         save = cursor->iprec;
1131                         cursor->iprec = NULL;
1132                         rec = save ? hammer_rec_rb_tree_RB_NEXT(save) : NULL;
1133                         while (rec) {
1134                                 if (hammer_rec_scan_cmp(rec, cursor) != 0)
1135                                         break;
1136                                 if (hammer_rec_scan_callback(rec, cursor) != 0)
1137                                         break;
1138                                 rec = hammer_rec_rb_tree_RB_NEXT(rec);
1139                         }
1140                         if (save)
1141                                 hammer_rel_mem_record(save);
1142                         if (cursor->iprec) {
1143                                 KKASSERT(cursor->iprec == rec);
1144                                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
1145                         } else {
1146                                 cursor->flags |= HAMMER_CURSOR_MEMEOF;
1147                         }
1148                 }
1149         }
1150
1151         /*
1152          * The memory record may have become stale while being held in
1153          * cursor->iprec.  We are interlocked against the backend on
1154          * with regards to B-Tree entries.
1155          */
1156         if ((cursor->flags & HAMMER_CURSOR_ATEMEM) == 0) {
1157                 if (hammer_ip_iterate_mem_good(cursor, cursor->iprec) == 0) {
1158                         cursor->flags |= HAMMER_CURSOR_ATEMEM;
1159                         goto next_memory;
1160                 }
1161         }
1162
1163         /*
1164          * Extract either the disk or memory record depending on their
1165          * relative position.
1166          */
1167         error = 0;
1168         switch(cursor->flags & (HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM)) {
1169         case 0:
1170                 /*
1171                  * Both entries valid.   Return the btree entry if it is
1172                  * in front of the memory entry.
1173                  */
1174                 elm = &cursor->node->ondisk->elms[cursor->index];
1175                 r = hammer_btree_cmp(&elm->base, &cursor->iprec->leaf.base);
1176                 if (r < 0) {
1177                         error = hammer_btree_extract(cursor,
1178                                                      HAMMER_CURSOR_GET_LEAF);
1179                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
1180                         break;
1181                 }
1182
1183                 /*
1184                  * If the entries match exactly the memory entry typically
1185                  * specifies an on-disk deletion and we eat both entries.
1186                  *
1187                  * If the in-memory record is not an on-disk deletion we
1188                  * probably caught the syncer while it was syncing it to
1189                  * the media.  Since we hold a shared lock on the cursor,
1190                  * the in-memory record had better be marked deleted at
1191                  * this point.
1192                  */
1193                 if (r == 0) {
1194                         if (cursor->iprec->type == HAMMER_MEM_RECORD_DEL) {
1195                                 if ((cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1196                                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
1197                                         cursor->flags |= HAMMER_CURSOR_ATEMEM;
1198                                         goto next_btree;
1199                                 }
1200                         } else {
1201                                 panic("hammer_ip_next: duplicate mem/b-tree entry");
1202                                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1203                                 goto next_memory;
1204                         }
1205                 }
1206                 /* fall through to the memory entry */
1207         case HAMMER_CURSOR_ATEDISK:
1208                 /*
1209                  * Only the memory entry is valid.
1210                  */
1211                 cursor->leaf = &cursor->iprec->leaf;
1212                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1213
1214                 /*
1215                  * If the memory entry is an on-disk deletion we should have
1216                  * also had found a B-Tree record.  If the backend beat us
1217                  * to it it would have interlocked the cursor and we should
1218                  * have seen the in-memory record marked DELETED_FE.
1219                  */
1220                 if (cursor->iprec->type == HAMMER_MEM_RECORD_DEL &&
1221                     (cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1222                         panic("hammer_ip_next: del-on-disk with no b-tree entry");
1223                 }
1224                 break;
1225         case HAMMER_CURSOR_ATEMEM:
1226                 /*
1227                  * Only the disk entry is valid
1228                  */
1229                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1230                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1231                 break;
1232         default:
1233                 /*
1234                  * Neither entry is valid
1235                  *
1236                  * XXX error not set properly
1237                  */
1238                 cursor->leaf = NULL;
1239                 error = ENOENT;
1240                 break;
1241         }
1242         return(error);
1243 }
1244
1245 /*
1246  * Resolve the cursor->data pointer for the current cursor position in
1247  * a merged iteration.
1248  */
1249 int
1250 hammer_ip_resolve_data(hammer_cursor_t cursor)
1251 {
1252         int error;
1253
1254         if (cursor->iprec && cursor->leaf == &cursor->iprec->leaf) {
1255                 cursor->data = cursor->iprec->data;
1256                 error = 0;
1257         } else {
1258                 cursor->leaf = &cursor->node->ondisk->elms[cursor->index].leaf;
1259                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA);
1260         }
1261         return(error);
1262 }
1263
1264 /*
1265  * Delete all records within the specified range for inode ip.
1266  *
1267  * NOTE: An unaligned range will cause new records to be added to cover
1268  * the edge cases. (XXX not implemented yet).
1269  *
1270  * NOTE: ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
1271  *
1272  * NOTE: Record keys for regular file data have to be special-cased since
1273  * they indicate the end of the range (key = base + bytes).
1274  */
1275 int
1276 hammer_ip_delete_range(hammer_cursor_t cursor, hammer_inode_t ip,
1277                        int64_t ran_beg, int64_t ran_end)
1278 {
1279         hammer_transaction_t trans = cursor->trans;
1280         hammer_btree_leaf_elm_t leaf;
1281         int error;
1282         int64_t off;
1283
1284 #if 0
1285         kprintf("delete_range %p %016llx-%016llx\n", ip, ran_beg, ran_end);
1286 #endif
1287
1288         KKASSERT(trans->type == HAMMER_TRANS_FLS);
1289 retry:
1290         hammer_normalize_cursor(cursor);
1291         cursor->key_beg.localization = HAMMER_LOCALIZE_MISC;
1292         cursor->key_beg.obj_id = ip->obj_id;
1293         cursor->key_beg.create_tid = 0;
1294         cursor->key_beg.delete_tid = 0;
1295         cursor->key_beg.obj_type = 0;
1296         cursor->asof = ip->obj_asof;
1297         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1298         cursor->flags |= HAMMER_CURSOR_ASOF;
1299         cursor->flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
1300         cursor->flags |= HAMMER_CURSOR_BACKEND;
1301
1302         cursor->key_end = cursor->key_beg;
1303         if (ip->ino_data.obj_type == HAMMER_OBJTYPE_DBFILE) {
1304                 cursor->key_beg.key = ran_beg;
1305                 cursor->key_beg.rec_type = HAMMER_RECTYPE_DB;
1306                 cursor->key_end.rec_type = HAMMER_RECTYPE_DB;
1307                 cursor->key_end.key = ran_end;
1308         } else {
1309                 /*
1310                  * The key in the B-Tree is (base+bytes), so the first possible
1311                  * matching key is ran_beg + 1.
1312                  */
1313                 int64_t tmp64;
1314
1315                 cursor->key_beg.key = ran_beg + 1;
1316                 cursor->key_beg.rec_type = HAMMER_RECTYPE_DATA;
1317                 cursor->key_end.rec_type = HAMMER_RECTYPE_DATA;
1318
1319                 tmp64 = ran_end + MAXPHYS + 1;  /* work around GCC-4 bug */
1320                 if (tmp64 < ran_end)
1321                         cursor->key_end.key = 0x7FFFFFFFFFFFFFFFLL;
1322                 else
1323                         cursor->key_end.key = ran_end + MAXPHYS + 1;
1324         }
1325         cursor->flags |= HAMMER_CURSOR_END_INCLUSIVE;
1326
1327         error = hammer_ip_first(cursor);
1328
1329         /*
1330          * Iterate through matching records and mark them as deleted.
1331          */
1332         while (error == 0) {
1333                 leaf = cursor->leaf;
1334
1335                 KKASSERT(leaf->base.delete_tid == 0);
1336
1337                 /*
1338                  * There may be overlap cases for regular file data.  Also
1339                  * remember the key for a regular file record is the offset
1340                  * of the last byte of the record (base + len - 1), NOT the
1341                  * base offset.
1342                  */
1343 #if 0
1344                 kprintf("delete_range rec_type %02x\n", leaf->base.rec_type);
1345 #endif
1346                 if (leaf->base.rec_type == HAMMER_RECTYPE_DATA) {
1347 #if 0
1348                         kprintf("delete_range loop key %016llx,%d\n",
1349                                 leaf->base.key - leaf->data_len,
1350                                 leaf->data_len);
1351 #endif
1352                         off = leaf->base.key - leaf->data_len;
1353                         /*
1354                          * Check the left edge case.  We currently do not
1355                          * split existing records.
1356                          */
1357                         if (off < ran_beg) {
1358                                 panic("hammer left edge case %016llx %d\n",
1359                                         leaf->base.key, leaf->data_len);
1360                         }
1361
1362                         /*
1363                          * Check the right edge case.  Note that the
1364                          * record can be completely out of bounds, which
1365                          * terminates the search.
1366                          *
1367                          * base->key is exclusive of the right edge while
1368                          * ran_end is inclusive of the right edge.  The
1369                          * (key - data_len) left boundary is inclusive.
1370                          *
1371                          * XXX theory-check this test at some point, are
1372                          * we missing a + 1 somewhere?  Note that ran_end
1373                          * could overflow.
1374                          */
1375                         if (leaf->base.key - 1 > ran_end) {
1376                                 if (leaf->base.key - leaf->data_len > ran_end)
1377                                         break;
1378                                 panic("hammer right edge case\n");
1379                         }
1380                 }
1381
1382                 /*
1383                  * Mark the record and B-Tree entry as deleted.  This will
1384                  * also physically delete the B-Tree entry, record, and
1385                  * data if the retention policy dictates.  The function
1386                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1387                  * uses to perform a fixup.
1388                  */
1389                 error = hammer_ip_delete_record(cursor, trans->tid);
1390                 if (error)
1391                         break;
1392                 error = hammer_ip_next(cursor);
1393         }
1394         if (error == EDEADLK) {
1395                 hammer_done_cursor(cursor);
1396                 error = hammer_init_cursor(trans, cursor, &ip->cache[0], ip);
1397                 if (error == 0)
1398                         goto retry;
1399         }
1400         if (error == ENOENT)
1401                 error = 0;
1402         return(error);
1403 }
1404
1405 /*
1406  * Delete all user records associated with an inode except the inode record
1407  * itself.  Directory entries are not deleted (they must be properly disposed
1408  * of or nlinks would get upset).
1409  */
1410 int
1411 hammer_ip_delete_range_all(hammer_cursor_t cursor, hammer_inode_t ip,
1412                            int *countp)
1413 {
1414         hammer_transaction_t trans = cursor->trans;
1415         hammer_btree_leaf_elm_t leaf;
1416         int error;
1417
1418         KKASSERT(trans->type == HAMMER_TRANS_FLS);
1419 retry:
1420         hammer_normalize_cursor(cursor);
1421         cursor->key_beg.localization = HAMMER_LOCALIZE_MISC;
1422         cursor->key_beg.obj_id = ip->obj_id;
1423         cursor->key_beg.create_tid = 0;
1424         cursor->key_beg.delete_tid = 0;
1425         cursor->key_beg.obj_type = 0;
1426         cursor->key_beg.rec_type = HAMMER_RECTYPE_INODE + 1;
1427         cursor->key_beg.key = HAMMER_MIN_KEY;
1428
1429         cursor->key_end = cursor->key_beg;
1430         cursor->key_end.rec_type = 0xFFFF;
1431         cursor->key_end.key = HAMMER_MAX_KEY;
1432
1433         cursor->asof = ip->obj_asof;
1434         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1435         cursor->flags |= HAMMER_CURSOR_END_INCLUSIVE | HAMMER_CURSOR_ASOF;
1436         cursor->flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
1437         cursor->flags |= HAMMER_CURSOR_BACKEND;
1438
1439         error = hammer_ip_first(cursor);
1440
1441         /*
1442          * Iterate through matching records and mark them as deleted.
1443          */
1444         while (error == 0) {
1445                 leaf = cursor->leaf;
1446
1447                 KKASSERT(leaf->base.delete_tid == 0);
1448
1449                 /*
1450                  * Mark the record and B-Tree entry as deleted.  This will
1451                  * also physically delete the B-Tree entry, record, and
1452                  * data if the retention policy dictates.  The function
1453                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1454                  * uses to perform a fixup.
1455                  *
1456                  * Directory entries (and delete-on-disk directory entries)
1457                  * must be synced and cannot be deleted.
1458                  */
1459                 if (leaf->base.rec_type != HAMMER_RECTYPE_DIRENTRY) {
1460                         error = hammer_ip_delete_record(cursor, trans->tid);
1461                         ++*countp;
1462                 }
1463                 if (error)
1464                         break;
1465                 error = hammer_ip_next(cursor);
1466         }
1467         if (error == EDEADLK) {
1468                 hammer_done_cursor(cursor);
1469                 error = hammer_init_cursor(trans, cursor, &ip->cache[0], ip);
1470                 if (error == 0)
1471                         goto retry;
1472         }
1473         if (error == ENOENT)
1474                 error = 0;
1475         return(error);
1476 }
1477
1478 /*
1479  * Delete the record at the current cursor.  On success the cursor will
1480  * be positioned appropriately for an iteration but may no longer be at
1481  * a leaf node.
1482  *
1483  * This routine is only called from the backend.
1484  *
1485  * NOTE: This can return EDEADLK, requiring the caller to terminate the
1486  * cursor and retry.
1487  */
1488 int
1489 hammer_ip_delete_record(hammer_cursor_t cursor, hammer_tid_t tid)
1490 {
1491         hammer_btree_elm_t elm;
1492         hammer_mount_t hmp;
1493         int error;
1494         int dodelete;
1495
1496         KKASSERT(cursor->flags & HAMMER_CURSOR_BACKEND);
1497
1498         /*
1499          * In-memory (unsynchronized) records can simply be freed.  This
1500          * only occurs in range iterations since all other records are
1501          * individually synchronized.  Thus there should be no confusion with
1502          * the interlock.
1503          */
1504         if (cursor->leaf == &cursor->iprec->leaf) {
1505                 KKASSERT((cursor->iprec->flags & HAMMER_RECF_INTERLOCK_BE) ==0);
1506                 cursor->iprec->flags |= HAMMER_RECF_DELETED_FE;
1507                 cursor->iprec->flags |= HAMMER_RECF_DELETED_BE;
1508                 return(0);
1509         }
1510
1511         /*
1512          * On-disk records are marked as deleted by updating their delete_tid.
1513          * This does not effect their position in the B-Tree (which is based
1514          * on their create_tid).
1515          */
1516         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1517         elm = NULL;
1518         hmp = cursor->node->hmp;
1519
1520         /*
1521          * If we were mounted with the nohistory option, we physically
1522          * delete the record.
1523          */
1524         if (hmp->hflags & HMNT_NOHISTORY)
1525                 dodelete = 1;
1526         else
1527                 dodelete = 0;
1528
1529         if (error == 0) {
1530                 error = hammer_cursor_upgrade(cursor);
1531                 if (error == 0) {
1532                         elm = &cursor->node->ondisk->elms[cursor->index];
1533                         hammer_modify_node(cursor->trans, cursor->node,
1534                                            &elm->leaf.base.delete_tid,
1535                                            sizeof(elm->leaf.base.delete_tid));
1536                         elm->leaf.base.delete_tid = tid;
1537                         hammer_modify_node_done(cursor->node);
1538
1539                         /*
1540                          * An on-disk record cannot have the same delete_tid
1541                          * as its create_tid.  In a chain of record updates
1542                          * this could result in a duplicate record.
1543                          */
1544                         KKASSERT(elm->leaf.base.delete_tid != elm->leaf.base.create_tid);
1545                 }
1546         }
1547
1548         if (error == 0 && dodelete) {
1549                 error = hammer_delete_at_cursor(cursor, NULL);
1550                 if (error) {
1551                         panic("hammer_ip_delete_record: unable to physically delete the record!\n");
1552                         error = 0;
1553                 }
1554         }
1555         return(error);
1556 }
1557
1558 int
1559 hammer_delete_at_cursor(hammer_cursor_t cursor, int64_t *stat_bytes)
1560 {
1561         hammer_btree_elm_t elm;
1562         hammer_off_t data_offset;
1563         int32_t data_len;
1564         u_int16_t rec_type;
1565         int error;
1566
1567         elm = &cursor->node->ondisk->elms[cursor->index];
1568         KKASSERT(elm->base.btype == HAMMER_BTREE_TYPE_RECORD);
1569
1570         data_offset = elm->leaf.data_offset;
1571         data_len = elm->leaf.data_len;
1572         rec_type = elm->leaf.base.rec_type;
1573
1574         error = hammer_btree_delete(cursor);
1575         if (error == 0) {
1576                 /*
1577                  * This forces a fixup for the iteration because
1578                  * the cursor is now either sitting at the 'next'
1579                  * element or sitting at the end of a leaf.
1580                  */
1581                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1582                         cursor->flags |= HAMMER_CURSOR_DELBTREE;
1583                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1584                 }
1585         }
1586         if (error == 0) {
1587                 switch(data_offset & HAMMER_OFF_ZONE_MASK) {
1588                 case HAMMER_ZONE_LARGE_DATA:
1589                 case HAMMER_ZONE_SMALL_DATA:
1590                         hammer_blockmap_free(cursor->trans,
1591                                              data_offset, data_len);
1592                         break;
1593                 default:
1594                         break;
1595                 }
1596         }
1597         return (error);
1598 }
1599
1600 /*
1601  * Determine whether we can remove a directory.  This routine checks whether
1602  * a directory is empty or not and enforces flush connectivity.
1603  *
1604  * Flush connectivity requires that we block if the target directory is
1605  * currently flushing, otherwise it may not end up in the same flush group.
1606  *
1607  * Returns 0 on success, ENOTEMPTY or EDEADLK (or other errors) on failure.
1608  */
1609 int
1610 hammer_ip_check_directory_empty(hammer_transaction_t trans, hammer_inode_t ip)
1611 {
1612         struct hammer_cursor cursor;
1613         int error;
1614
1615         /*
1616          * Check directory empty
1617          */
1618         hammer_init_cursor(trans, &cursor, &ip->cache[0], ip);
1619
1620         cursor.key_beg.localization = HAMMER_LOCALIZE_MISC;
1621         cursor.key_beg.obj_id = ip->obj_id;
1622         cursor.key_beg.create_tid = 0;
1623         cursor.key_beg.delete_tid = 0;
1624         cursor.key_beg.obj_type = 0;
1625         cursor.key_beg.rec_type = HAMMER_RECTYPE_INODE + 1;
1626         cursor.key_beg.key = HAMMER_MIN_KEY;
1627
1628         cursor.key_end = cursor.key_beg;
1629         cursor.key_end.rec_type = 0xFFFF;
1630         cursor.key_end.key = HAMMER_MAX_KEY;
1631
1632         cursor.asof = ip->obj_asof;
1633         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE | HAMMER_CURSOR_ASOF;
1634
1635         error = hammer_ip_first(&cursor);
1636         if (error == ENOENT)
1637                 error = 0;
1638         else if (error == 0)
1639                 error = ENOTEMPTY;
1640         hammer_done_cursor(&cursor);
1641         return(error);
1642 }
1643