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.58 2008/05/12 23:15:46 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.obj_id = dip->obj_id;
 480         record->leaf.base.key = hammer_directory_namekey(ncp->nc_name, bytes);
 481         record->leaf.base.key += trans->hmp->namekey_iterator;
 482         record->leaf.base.rec_type = HAMMER_RECTYPE_DIRENTRY;
 483         record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
 484         record->data->entry.obj_id = ip->obj_id;
 485         bcopy(ncp->nc_name, record->data->entry.name, bytes);
 486
 487         ++ip->ino_data.nlinks;
 488         hammer_modify_inode(trans, ip, HAMMER_INODE_DDIRTY);
 489
 490         /*
 491          * The target inode and the directory entry are bound together.
 492          */
 493         record->target_ip = ip;
 494         record->flush_state = HAMMER_FST_SETUP;
 495         TAILQ_INSERT_TAIL(&ip->target_list, record, target_entry);
 496
 497         /*
 498          * The inode now has a dependancy and must be taken out of the idle
 499          * state.  An inode not in an idle state is given an extra reference.
 500          */
 501         if (ip->flush_state == HAMMER_FST_IDLE) {
 502                 hammer_ref(&ip->lock);
 503                 ip->flush_state = HAMMER_FST_SETUP;
 504         }
 505
 506         /* NOTE: copies record->data */
 507         error = hammer_mem_add(trans, record);
 508         return(error);
 509 }
 510
 511 /*
 512  * Delete the directory entry and update the inode link count.  The
 513  * cursor must be seeked to the directory entry record being deleted.
 514  *
 515  * The related inode should be share-locked by the caller.  The caller is
 516  * on the frontend.
 517  *
 518  * This function can return EDEADLK requiring the caller to terminate
 519  * the cursor, any locks, wait on the returned record, and retry.
 520  */
 521 int
 522 hammer_ip_del_directory(struct hammer_transaction *trans,
 523                      hammer_cursor_t cursor, struct hammer_inode *dip,
 524                      struct hammer_inode *ip)
 525 {
 526         hammer_record_t record;
 527         int error;
 528
 529         if (cursor->leaf == &cursor->iprec->leaf) {
 530                 /*
 531                  * In-memory (unsynchronized) records can simply be freed.
 532                  * Even though the HAMMER_RECF_DELETED_FE flag is ignored
 533                  * by the backend, we must still avoid races against the
 534                  * backend potentially syncing the record to the media.
 535                  *
 536                  * We cannot call hammer_ip_delete_record(), that routine may
 537                  * only be called from the backend.
 538                  */
 539                 record = cursor->iprec;
 540                 if (record->flags & HAMMER_RECF_INTERLOCK_BE) {
 541                         KKASSERT(cursor->deadlk_rec == NULL);
 542                         hammer_ref(&record->lock);
 543                         cursor->deadlk_rec = record;
 544                         error = EDEADLK;
 545                 } else {
 546                         KKASSERT(record->type == HAMMER_MEM_RECORD_ADD);
 547                         record->flags |= HAMMER_RECF_DELETED_FE;
 548                         error = 0;
 549                 }
 550         } else {
 551                 /*
 552                  * If the record is on-disk we have to queue the deletion by
 553                  * the record's key.  This also causes lookups to skip the
 554                  * record.
 555                  */
 556                 KKASSERT(dip->flags &
 557                          (HAMMER_INODE_ONDISK | HAMMER_INODE_DONDISK));
 558                 record = hammer_alloc_mem_record(dip, 0);
 559                 record->type = HAMMER_MEM_RECORD_DEL;
 560                 record->leaf.base = cursor->leaf->base;
 561
 562                 record->target_ip = ip;
 563                 record->flush_state = HAMMER_FST_SETUP;
 564                 TAILQ_INSERT_TAIL(&ip->target_list, record, target_entry);
 565
 566                 /*
 567                  * The inode now has a dependancy and must be taken out of
 568                  * the idle state.  An inode not in an idle state is given
 569                  * an extra reference.
 570                  */
 571                 if (ip->flush_state == HAMMER_FST_IDLE) {
 572                         hammer_ref(&ip->lock);
 573                         ip->flush_state = HAMMER_FST_SETUP;
 574                 }
 575
 576                 error = hammer_mem_add(trans, record);
 577         }
 578
 579         /*
 580          * One less link.  The file may still be open in the OS even after
 581          * all links have gone away.
 582          *
 583          * We have to terminate the cursor before syncing the inode to
 584          * avoid deadlocking against ourselves.  XXX this may no longer
 585          * be true.
 586          *
 587          * If nlinks drops to zero and the vnode is inactive (or there is
 588          * no vnode), call hammer_inode_unloadable_check() to zonk the
 589          * inode.  If we don't do this here the inode will not be destroyed
 590          * on-media until we unmount.
 591          */
 592         if (error == 0) {
 593                 --ip->ino_data.nlinks;
 594                 hammer_modify_inode(trans, ip, HAMMER_INODE_DDIRTY);
 595                 if (ip->ino_data.nlinks == 0 &&
 596                     (ip->vp == NULL || (ip->vp->v_flag & VINACTIVE))) {
 597                         hammer_done_cursor(cursor);
 598                         hammer_inode_unloadable_check(ip, 1);
 599                         hammer_flush_inode(ip, 0);
 600                 }
 601
 602         }
 603         return(error);
 604 }
 605
 606 /*
 607  * Add a record to an inode.
 608  *
 609  * The caller must allocate the record with hammer_alloc_mem_record(ip) and
 610  * initialize the following additional fields:
 611  *
 612  * The related inode should be share-locked by the caller.  The caller is
 613  * on the frontend.
 614  *
 615  * record->rec.entry.base.base.key
 616  * record->rec.entry.base.base.rec_type
 617  * record->rec.entry.base.base.data_len
 618  * record->data         (a copy will be kmalloc'd if it cannot be embedded)
 619  */
 620 int
 621 hammer_ip_add_record(struct hammer_transaction *trans, hammer_record_t record)
 622 {
 623         hammer_inode_t ip = record->ip;
 624         int error;
 625
 626         record->leaf.base.obj_id = ip->obj_id;
 627         record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
 628         error = hammer_mem_add(trans, record);
 629         return(error);
 630 }
 631
 632 /*
 633  * Sync data from a buffer cache buffer (typically) to the filesystem.  This
 634  * is called via the strategy called from a cached data source.  This code
 635  * is responsible for actually writing a data record out to the disk.
 636  *
 637  * This can only occur non-historically (i.e. 'current' data only).
 638  *
 639  * The file offset must be HAMMER_BUFSIZE aligned but the data length
 640  * can be truncated.  The record (currently) always represents a BUFSIZE
 641  * swath of space whether the data is truncated or not.
 642  */
 643 int
 644 hammer_ip_sync_data(hammer_cursor_t cursor, hammer_inode_t ip,
 645                        int64_t offset, void *data, int bytes)
 646 {
 647         hammer_transaction_t trans = cursor->trans;
 648         struct hammer_btree_leaf_elm elm;
 649         hammer_off_t data_offset;
 650         void *bdata;
 651         int error;
 652
 653         KKASSERT((offset & HAMMER_BUFMASK) == 0);
 654         KKASSERT(trans->type == HAMMER_TRANS_FLS);
 655         KKASSERT(bytes != 0);
 656 retry:
 657         hammer_normalize_cursor(cursor);
 658         cursor->key_beg.obj_id = ip->obj_id;
 659         cursor->key_beg.key = offset + bytes;
 660         cursor->key_beg.create_tid = trans->tid;
 661         cursor->key_beg.delete_tid = 0;
 662         cursor->key_beg.rec_type = HAMMER_RECTYPE_DATA;
 663         cursor->asof = trans->tid;
 664         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
 665         cursor->flags |= HAMMER_CURSOR_INSERT;
 666         cursor->flags |= HAMMER_CURSOR_BACKEND;
 667
 668         /*
 669          * Issue a lookup to position the cursor.
 670          */
 671         error = hammer_btree_lookup(cursor);
 672         if (error == 0) {
 673                 kprintf("hammer_ip_sync_data: duplicate data at "
 674                         "(%lld,%d) tid %016llx\n",
 675                         offset, bytes, trans->tid);
 676                 hammer_print_btree_elm(&cursor->node->ondisk->
 677                                         elms[cursor->index],
 678                                        HAMMER_BTREE_TYPE_LEAF, cursor->index);
 679                 panic("Duplicate data");
 680                 error = EIO;
 681         }
 682         if (error != ENOENT)
 683                 goto done;
 684
 685         /*
 686          * Allocate our data.  The data buffer is not marked modified (yet)
 687          */
 688         bdata = hammer_alloc_data(trans, bytes, &data_offset,
 689                                   &cursor->data_buffer, &error);
 690
 691         if (bdata == NULL)
 692                 goto done;
 693
 694         /*
 695          * Fill everything in and insert our B-Tree node.
 696          *
 697          * NOTE: hammer_alloc_data() has already marked the data buffer
 698          * as modified.  If we do it again we will generate unnecessary
 699          * undo elements.
 700          */
 701         elm.base.btype = HAMMER_BTREE_TYPE_RECORD;
 702         elm.base.obj_id = ip->obj_id;
 703         elm.base.key = offset + bytes;
 704         elm.base.create_tid = trans->tid;
 705         elm.base.delete_tid = 0;
 706         elm.base.rec_type = HAMMER_RECTYPE_DATA;
 707         elm.atime = 0;
 708         elm.data_offset = data_offset;
 709         elm.data_len = bytes;
 710         elm.data_crc = crc32(data, bytes);
 711
 712         hammer_modify_buffer(trans, cursor->data_buffer, NULL, 0);
 713         bcopy(data, bdata, bytes);
 714         hammer_modify_buffer_done(cursor->data_buffer);
 715
 716         /*
 717          * Data records can wind up on-disk before the inode itself is
 718          * on-disk.  One must assume data records may be on-disk if either
 719          * HAMMER_INODE_DONDISK or HAMMER_INODE_ONDISK is set
 720          */
 721         ip->flags |= HAMMER_INODE_DONDISK;
 722
 723         error = hammer_btree_insert(cursor, &elm);
 724         if (error == 0)
 725                 goto done;
 726
 727         hammer_blockmap_free(trans, data_offset, bytes);
 728 done:
 729         if (error == EDEADLK) {
 730                 hammer_done_cursor(cursor);
 731                 error = hammer_init_cursor(trans, cursor, &ip->cache[0], ip);
 732                 if (error == 0)
 733                         goto retry;
 734         }
 735         return(error);
 736 }
 737
 738 #if 0
 739 /*
 740  * Sync an in-memory record to the disk.  This is called by the backend.
 741  * This code is responsible for actually writing a record out to the disk.
 742  *
 743  * This routine can only be called by the backend and the record
 744  * must have been interlocked with BE.  It will remain interlocked on
 745  * return.  If no error occurs the record will be marked deleted but
 746  * the caller is responsible for its final disposition.
 747  *
 748  * Multiple calls may be aggregated with the same cursor using
 749  * hammer_ip_sync_record_cursor().  The caller must handle EDEADLK
 750  * in that case.
 751  */
 752 int
 753 hammer_ip_sync_record(hammer_transaction_t trans, hammer_record_t record)
 754 {
 755         struct hammer_cursor cursor;
 756         int error;
 757
 758         do {
 759                 error = hammer_init_cursor(trans, &cursor,
 760                                            &record->ip->cache[0], record->ip);
 761                 if (error) {
 762                         KKASSERT(0);
 763                         hammer_done_cursor(&cursor);
 764                         return(error);
 765                 }
 766                 error = hammer_ip_sync_record_cursor(&cursor, record);
 767                 hammer_done_cursor(&cursor);
 768         } while (error == EDEADLK);
 769         return (error);
 770 }
 771
 772 #endif
 773
 774 int
 775 hammer_ip_sync_record_cursor(hammer_cursor_t cursor, hammer_record_t record)
 776 {
 777         hammer_transaction_t trans = cursor->trans;
 778         void *bdata;
 779         int error;
 780
 781         KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
 782         KKASSERT(record->flags & HAMMER_RECF_INTERLOCK_BE);
 783
 784         hammer_normalize_cursor(cursor);
 785         cursor->key_beg = record->leaf.base;
 786         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
 787         cursor->flags |= HAMMER_CURSOR_BACKEND;
 788         cursor->flags &= ~HAMMER_CURSOR_INSERT;
 789
 790         /*
 791          * Records can wind up on-media before the inode itself is on-media.
 792          * Flag the case.
 793          */
 794         record->ip->flags |= HAMMER_INODE_DONDISK;
 795
 796         /*
 797          * If we are deleting an exact match must be found on-disk.
 798          */
 799         if (record->type == HAMMER_MEM_RECORD_DEL) {
 800                 error = hammer_btree_lookup(cursor);
 801                 if (error == 0) {
 802                         error = hammer_ip_delete_record(cursor, trans->tid);
 803                         if (error == 0) {
 804                                 record->flags |= HAMMER_RECF_DELETED_FE;
 805                                 record->flags |= HAMMER_RECF_DELETED_BE;
 806                         }
 807                 }
 808                 goto done;
 809         }
 810
 811         /*
 812          * We are inserting.
 813          *
 814          * Issue a lookup to position the cursor and locate the cluster.  The
 815          * target key should not exist.  If we are creating a directory entry
 816          * we may have to iterate the low 32 bits of the key to find an unused
 817          * key.
 818          */
 819         cursor->flags |= HAMMER_CURSOR_INSERT;
 820
 821         for (;;) {
 822                 error = hammer_btree_lookup(cursor);
 823                 if (hammer_debug_inode)
 824                         kprintf("DOINSERT LOOKUP %d\n", error);
 825                 if (error)
 826                         break;
 827                 if (record->leaf.base.rec_type != HAMMER_RECTYPE_DIRENTRY) {
 828                         kprintf("hammer_ip_sync_record: duplicate rec "
 829                                 "at (%016llx)\n", record->leaf.base.key);
 830                         Debugger("duplicate record1");
 831                         error = EIO;
 832                         break;
 833                 }
 834                 if (++trans->hmp->namekey_iterator == 0)
 835                         ++trans->hmp->namekey_iterator;
 836                 record->leaf.base.key &= ~(0xFFFFFFFFLL);
 837                 record->leaf.base.key |= trans->hmp->namekey_iterator;
 838                 cursor->key_beg.key = record->leaf.base.key;
 839         }
 840         if (error != ENOENT)
 841                 goto done;
 842
 843         /*
 844          * Allocate the record and data.  The result buffers will be
 845          * marked as being modified and further calls to
 846          * hammer_modify_buffer() will result in unneeded UNDO records.
 847          *
 848          * Support zero-fill records (data == NULL and data_len != 0)
 849          */
 850         if (record->data && record->leaf.data_len) {
 851                 bdata = hammer_alloc_data(trans, record->leaf.data_len,
 852                                           &record->leaf.data_offset,
 853                                           &cursor->data_buffer, &error);
 854                 if (bdata == NULL)
 855                         goto done;
 856                 record->leaf.data_crc = crc32(record->data,
 857                                               record->leaf.data_len);
 858                 hammer_modify_buffer(trans, cursor->data_buffer, NULL, 0);
 859                 bcopy(record->data, bdata, record->leaf.data_len);
 860                 hammer_modify_buffer_done(cursor->data_buffer);
 861         } else {
 862                 /* record->leaf.data_len can be non-zero for future zero-fill */
 863                 record->leaf.data_offset = 0;
 864                 record->leaf.data_crc = 0;
 865         }
 866
 867         error = hammer_btree_insert(cursor, &record->leaf);
 868         if (hammer_debug_inode)
 869                 kprintf("BTREE INSERT error %d @ %016llx:%d\n", error, cursor->node->node_offset, cursor->index);
 870
 871         /*
 872          * This occurs when the frontend creates a record and queues it to
 873          * the backend, then tries to delete the record.  The backend must
 874          * still sync the record to the media as if it were not deleted,
 875          * but must interlock with the frontend to ensure that the
 876          * synchronized record is not visible to the frontend, which means
 877          * converting it from an ADD record to a DEL record.
 878          *
 879          * The DEL record then masks the record synced to disk until another
 880          * round can delete it for real.
 881          */
 882         if (error == 0) {
 883                 if (record->flags & HAMMER_RECF_CONVERT_DELETE) {
 884                         KKASSERT(record->type == HAMMER_MEM_RECORD_ADD);
 885                         record->flags &= ~HAMMER_RECF_DELETED_FE;
 886                         record->type = HAMMER_MEM_RECORD_DEL;
 887                         KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
 888                         record->flags &= ~HAMMER_RECF_CONVERT_DELETE;
 889                         /* hammer_flush_record_done takes care of the rest */
 890                 } else {
 891                         record->flags |= HAMMER_RECF_DELETED_FE;
 892                         record->flags |= HAMMER_RECF_DELETED_BE;
 893                 }
 894         } else {
 895                 if (record->leaf.data_offset) {
 896                         hammer_blockmap_free(trans, record->leaf.data_offset,
 897                                              record->leaf.data_len);
 898                 }
 899         }
 900
 901 done:
 902         return(error);
 903 }
 904
 905 /*
 906  * Add the record to the inode's rec_tree.  The low 32 bits of a directory
 907  * entry's key is used to deal with hash collisions in the upper 32 bits.
 908  * A unique 64 bit key is generated in-memory and may be regenerated a
 909  * second time when the directory record is flushed to the on-disk B-Tree.
 910  *
 911  * A referenced record is passed to this function.  This function
 912  * eats the reference.  If an error occurs the record will be deleted.
 913  *
 914  * A copy of the temporary record->data pointer provided by the caller
 915  * will be made.
 916  */
 917 static
 918 int
 919 hammer_mem_add(struct hammer_transaction *trans, hammer_record_t record)
 920 {
 921         /*
 922          * Make a private copy of record->data
 923          */
 924         if (record->data)
 925                 KKASSERT(record->flags & HAMMER_RECF_ALLOCDATA);
 926
 927         /*
 928          * Insert into the RB tree, find an unused iterator if this is
 929          * a directory entry.
 930          */
 931         while (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) {
 932                 if (record->leaf.base.rec_type != HAMMER_RECTYPE_DIRENTRY){
 933                         record->flags |= HAMMER_RECF_DELETED_FE;
 934                         hammer_rel_mem_record(record);
 935                         return (EEXIST);
 936                 }
 937                 if (++trans->hmp->namekey_iterator == 0)
 938                         ++trans->hmp->namekey_iterator;
 939                 record->leaf.base.key &= ~(0xFFFFFFFFLL);
 940                 record->leaf.base.key |= trans->hmp->namekey_iterator;
 941         }
 942         record->flags |= HAMMER_RECF_ONRBTREE;
 943         hammer_modify_inode(trans, record->ip, HAMMER_INODE_XDIRTY);
 944         hammer_rel_mem_record(record);
 945         return(0);
 946 }
 947
 948 /************************************************************************
 949  *                   HAMMER INODE MERGED-RECORD FUNCTIONS               *
 950  ************************************************************************
 951  *
 952  * These functions augment the B-Tree scanning functions in hammer_btree.c
 953  * by merging in-memory records with on-disk records.
 954  */
 955
 956 /*
 957  * Locate a particular record either in-memory or on-disk.
 958  *
 959  * NOTE: This is basically a standalone routine, hammer_ip_next() may
 960  * NOT be called to iterate results.
 961  */
 962 int
 963 hammer_ip_lookup(hammer_cursor_t cursor)
 964 {
 965         int error;
 966
 967         /*
 968          * If the element is in-memory return it without searching the
 969          * on-disk B-Tree
 970          */
 971         KKASSERT(cursor->ip);
 972         error = hammer_mem_lookup(cursor);
 973         if (error == 0) {
 974                 cursor->leaf = &cursor->iprec->leaf;
 975                 return(error);
 976         }
 977         if (error != ENOENT)
 978                 return(error);
 979
 980         /*
 981          * If the inode has on-disk components search the on-disk B-Tree.
 982          */
 983         if ((cursor->ip->flags & (HAMMER_INODE_ONDISK|HAMMER_INODE_DONDISK)) == 0)
 984                 return(error);
 985         error = hammer_btree_lookup(cursor);
 986         if (error == 0)
 987                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
 988         return(error);
 989 }
 990
 991 /*
 992  * Locate the first record within the cursor's key_beg/key_end range,
 993  * restricted to a particular inode.  0 is returned on success, ENOENT
 994  * if no records matched the requested range, or some other error.
 995  *
 996  * When 0 is returned hammer_ip_next() may be used to iterate additional
 997  * records within the requested range.
 998  *
 999  * This function can return EDEADLK, requiring the caller to terminate
1000  * the cursor and try again.
1001  */
1002 int
1003 hammer_ip_first(hammer_cursor_t cursor)
1004 {
1005         hammer_inode_t ip = cursor->ip;
1006         int error;
1007
1008         KKASSERT(ip != NULL);
1009
1010         /*
1011          * Clean up fields and setup for merged scan
1012          */
1013         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1014         cursor->flags |= HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM;
1015         cursor->flags |= HAMMER_CURSOR_DISKEOF | HAMMER_CURSOR_MEMEOF;
1016         if (cursor->iprec) {
1017                 hammer_rel_mem_record(cursor->iprec);
1018                 cursor->iprec = NULL;
1019         }
1020
1021         /*
1022          * Search the on-disk B-Tree.  hammer_btree_lookup() only does an
1023          * exact lookup so if we get ENOENT we have to call the iterate
1024          * function to validate the first record after the begin key.
1025          *
1026          * The ATEDISK flag is used by hammer_btree_iterate to determine
1027          * whether it must index forwards or not.  It is also used here
1028          * to select the next record from in-memory or on-disk.
1029          *
1030          * EDEADLK can only occur if the lookup hit an empty internal
1031          * element and couldn't delete it.  Since this could only occur
1032          * in-range, we can just iterate from the failure point.
1033          */
1034         if (ip->flags & (HAMMER_INODE_ONDISK|HAMMER_INODE_DONDISK)) {
1035                 error = hammer_btree_lookup(cursor);
1036                 if (error == ENOENT || error == EDEADLK) {
1037                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1038                         if (hammer_debug_general & 0x2000)
1039                                 kprintf("error %d node %p %016llx index %d\n", error, cursor->node, cursor->node->node_offset, cursor->index);
1040                         error = hammer_btree_iterate(cursor);
1041                 }
1042                 if (error && error != ENOENT)
1043                         return(error);
1044                 if (error == 0) {
1045                         cursor->flags &= ~HAMMER_CURSOR_DISKEOF;
1046                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1047                 } else {
1048                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
1049                 }
1050         }
1051
1052         /*
1053          * Search the in-memory record list (Red-Black tree).  Unlike the
1054          * B-Tree search, mem_first checks for records in the range.
1055          */
1056         error = hammer_mem_first(cursor);
1057         if (error && error != ENOENT)
1058                 return(error);
1059         if (error == 0) {
1060                 cursor->flags &= ~HAMMER_CURSOR_MEMEOF;
1061                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
1062                 if (hammer_ip_iterate_mem_good(cursor, cursor->iprec) == 0)
1063                         cursor->flags |= HAMMER_CURSOR_ATEMEM;
1064         }
1065
1066         /*
1067          * This will return the first matching record.
1068          */
1069         return(hammer_ip_next(cursor));
1070 }
1071
1072 /*
1073  * Retrieve the next record in a merged iteration within the bounds of the
1074  * cursor.  This call may be made multiple times after the cursor has been
1075  * initially searched with hammer_ip_first().
1076  *
1077  * 0 is returned on success, ENOENT if no further records match the
1078  * requested range, or some other error code is returned.
1079  */
1080 int
1081 hammer_ip_next(hammer_cursor_t cursor)
1082 {
1083         hammer_btree_elm_t elm;
1084         hammer_record_t rec, save;
1085         int error;
1086         int r;
1087
1088 next_btree:
1089         /*
1090          * Load the current on-disk and in-memory record.  If we ate any
1091          * records we have to get the next one.
1092          *
1093          * If we deleted the last on-disk record we had scanned ATEDISK will
1094          * be clear and DELBTREE will be set, forcing a call to iterate. The
1095          * fact that ATEDISK is clear causes iterate to re-test the 'current'
1096          * element.  If ATEDISK is set, iterate will skip the 'current'
1097          * element.
1098          *
1099          * Get the next on-disk record
1100          */
1101         if (cursor->flags & (HAMMER_CURSOR_ATEDISK|HAMMER_CURSOR_DELBTREE)) {
1102                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1103                         error = hammer_btree_iterate(cursor);
1104                         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1105                         if (error == 0)
1106                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1107                         else
1108                                 cursor->flags |= HAMMER_CURSOR_DISKEOF |
1109                                                  HAMMER_CURSOR_ATEDISK;
1110                 }
1111         }
1112
1113 next_memory:
1114         /*
1115          * Get the next in-memory record.  The record can be ripped out
1116          * of the RB tree so we maintain a scan_info structure to track
1117          * the next node.
1118          *
1119          * hammer_rec_scan_cmp:  Is the record still in our general range,
1120          *                       (non-inclusive of snapshot exclusions)?
1121          * hammer_rec_scan_callback: Is the record in our snapshot?
1122          */
1123         if (cursor->flags & HAMMER_CURSOR_ATEMEM) {
1124                 if ((cursor->flags & HAMMER_CURSOR_MEMEOF) == 0) {
1125                         save = cursor->iprec;
1126                         cursor->iprec = NULL;
1127                         rec = save ? hammer_rec_rb_tree_RB_NEXT(save) : NULL;
1128                         while (rec) {
1129                                 if (hammer_rec_scan_cmp(rec, cursor) != 0)
1130                                         break;
1131                                 if (hammer_rec_scan_callback(rec, cursor) != 0)
1132                                         break;
1133                                 rec = hammer_rec_rb_tree_RB_NEXT(rec);
1134                         }
1135                         if (save)
1136                                 hammer_rel_mem_record(save);
1137                         if (cursor->iprec) {
1138                                 KKASSERT(cursor->iprec == rec);
1139                                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
1140                         } else {
1141                                 cursor->flags |= HAMMER_CURSOR_MEMEOF;
1142                         }
1143                 }
1144         }
1145
1146         /*
1147          * The memory record may have become stale while being held in
1148          * cursor->iprec.  We are interlocked against the backend on
1149          * with regards to B-Tree entries.
1150          */
1151         if ((cursor->flags & HAMMER_CURSOR_ATEMEM) == 0) {
1152                 if (hammer_ip_iterate_mem_good(cursor, cursor->iprec) == 0) {
1153                         cursor->flags |= HAMMER_CURSOR_ATEMEM;
1154                         goto next_memory;
1155                 }
1156         }
1157
1158         /*
1159          * Extract either the disk or memory record depending on their
1160          * relative position.
1161          */
1162         error = 0;
1163         switch(cursor->flags & (HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM)) {
1164         case 0:
1165                 /*
1166                  * Both entries valid.   Return the btree entry if it is
1167                  * in front of the memory entry.
1168                  */
1169                 elm = &cursor->node->ondisk->elms[cursor->index];
1170                 r = hammer_btree_cmp(&elm->base, &cursor->iprec->leaf.base);
1171                 if (r < 0) {
1172                         error = hammer_btree_extract(cursor,
1173                                                      HAMMER_CURSOR_GET_LEAF);
1174                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
1175                         break;
1176                 }
1177
1178                 /*
1179                  * If the entries match exactly the memory entry typically
1180                  * specifies an on-disk deletion and we eat both entries.
1181                  *
1182                  * If the in-memory record is not an on-disk deletion we
1183                  * probably caught the syncer while it was syncing it to
1184                  * the media.  Since we hold a shared lock on the cursor,
1185                  * the in-memory record had better be marked deleted at
1186                  * this point.
1187                  */
1188                 if (r == 0) {
1189                         if (cursor->iprec->type == HAMMER_MEM_RECORD_DEL) {
1190                                 if ((cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1191                                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
1192                                         cursor->flags |= HAMMER_CURSOR_ATEMEM;
1193                                         goto next_btree;
1194                                 }
1195                         } else {
1196                                 panic("hammer_ip_next: duplicate mem/b-tree entry");
1197                                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1198                                 goto next_memory;
1199                         }
1200                 }
1201                 /* fall through to the memory entry */
1202         case HAMMER_CURSOR_ATEDISK:
1203                 /*
1204                  * Only the memory entry is valid.
1205                  */
1206                 cursor->leaf = &cursor->iprec->leaf;
1207                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1208
1209                 /*
1210                  * If the memory entry is an on-disk deletion we should have
1211                  * also had found a B-Tree record.  If the backend beat us
1212                  * to it it would have interlocked the cursor and we should
1213                  * have seen the in-memory record marked DELETED_FE.
1214                  */
1215                 if (cursor->iprec->type == HAMMER_MEM_RECORD_DEL &&
1216                     (cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1217                         panic("hammer_ip_next: del-on-disk with no b-tree entry");
1218                 }
1219                 break;
1220         case HAMMER_CURSOR_ATEMEM:
1221                 /*
1222                  * Only the disk entry is valid
1223                  */
1224                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1225                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1226                 break;
1227         default:
1228                 /*
1229                  * Neither entry is valid
1230                  *
1231                  * XXX error not set properly
1232                  */
1233                 cursor->leaf = NULL;
1234                 error = ENOENT;
1235                 break;
1236         }
1237         return(error);
1238 }
1239
1240 /*
1241  * Resolve the cursor->data pointer for the current cursor position in
1242  * a merged iteration.
1243  */
1244 int
1245 hammer_ip_resolve_data(hammer_cursor_t cursor)
1246 {
1247         int error;
1248
1249         if (cursor->iprec && cursor->leaf == &cursor->iprec->leaf) {
1250                 cursor->data = cursor->iprec->data;
1251                 error = 0;
1252         } else {
1253                 cursor->leaf = &cursor->node->ondisk->elms[cursor->index].leaf;
1254                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA);
1255         }
1256         return(error);
1257 }
1258
1259 /*
1260  * Delete all records within the specified range for inode ip.
1261  *
1262  * NOTE: An unaligned range will cause new records to be added to cover
1263  * the edge cases. (XXX not implemented yet).
1264  *
1265  * NOTE: ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
1266  *
1267  * NOTE: Record keys for regular file data have to be special-cased since
1268  * they indicate the end of the range (key = base + bytes).
1269  */
1270 int
1271 hammer_ip_delete_range(hammer_cursor_t cursor, hammer_inode_t ip,
1272                        int64_t ran_beg, int64_t ran_end)
1273 {
1274         hammer_transaction_t trans = cursor->trans;
1275         hammer_btree_leaf_elm_t leaf;
1276         int error;
1277         int64_t off;
1278
1279 #if 0
1280         kprintf("delete_range %p %016llx-%016llx\n", ip, ran_beg, ran_end);
1281 #endif
1282
1283         KKASSERT(trans->type == HAMMER_TRANS_FLS);
1284 retry:
1285         hammer_normalize_cursor(cursor);
1286         cursor->key_beg.obj_id = ip->obj_id;
1287         cursor->key_beg.create_tid = 0;
1288         cursor->key_beg.delete_tid = 0;
1289         cursor->key_beg.obj_type = 0;
1290         cursor->asof = ip->obj_asof;
1291         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1292         cursor->flags |= HAMMER_CURSOR_ASOF;
1293         cursor->flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
1294         cursor->flags |= HAMMER_CURSOR_BACKEND;
1295
1296         cursor->key_end = cursor->key_beg;
1297         if (ip->ino_data.obj_type == HAMMER_OBJTYPE_DBFILE) {
1298                 cursor->key_beg.key = ran_beg;
1299                 cursor->key_beg.rec_type = HAMMER_RECTYPE_DB;
1300                 cursor->key_end.rec_type = HAMMER_RECTYPE_DB;
1301                 cursor->key_end.key = ran_end;
1302         } else {
1303                 /*
1304                  * The key in the B-Tree is (base+bytes), so the first possible
1305                  * matching key is ran_beg + 1.
1306                  */
1307                 int64_t tmp64;
1308
1309                 cursor->key_beg.key = ran_beg + 1;
1310                 cursor->key_beg.rec_type = HAMMER_RECTYPE_DATA;
1311                 cursor->key_end.rec_type = HAMMER_RECTYPE_DATA;
1312
1313                 tmp64 = ran_end + MAXPHYS + 1;  /* work around GCC-4 bug */
1314                 if (tmp64 < ran_end)
1315                         cursor->key_end.key = 0x7FFFFFFFFFFFFFFFLL;
1316                 else
1317                         cursor->key_end.key = ran_end + MAXPHYS + 1;
1318         }
1319         cursor->flags |= HAMMER_CURSOR_END_INCLUSIVE;
1320
1321         error = hammer_ip_first(cursor);
1322
1323         /*
1324          * Iterate through matching records and mark them as deleted.
1325          */
1326         while (error == 0) {
1327                 leaf = cursor->leaf;
1328
1329                 KKASSERT(leaf->base.delete_tid == 0);
1330
1331                 /*
1332                  * There may be overlap cases for regular file data.  Also
1333                  * remember the key for a regular file record is the offset
1334                  * of the last byte of the record (base + len - 1), NOT the
1335                  * base offset.
1336                  */
1337 #if 0
1338                 kprintf("delete_range rec_type %02x\n", leaf->base.rec_type);
1339 #endif
1340                 if (leaf->base.rec_type == HAMMER_RECTYPE_DATA) {
1341 #if 0
1342                         kprintf("delete_range loop key %016llx,%d\n",
1343                                 leaf->base.key - leaf->data_len,
1344                                 leaf->data_len);
1345 #endif
1346                         off = leaf->base.key - leaf->data_len;
1347                         /*
1348                          * Check the left edge case.  We currently do not
1349                          * split existing records.
1350                          */
1351                         if (off < ran_beg) {
1352                                 panic("hammer left edge case %016llx %d\n",
1353                                         leaf->base.key, leaf->data_len);
1354                         }
1355
1356                         /*
1357                          * Check the right edge case.  Note that the
1358                          * record can be completely out of bounds, which
1359                          * terminates the search.
1360                          *
1361                          * base->key is exclusive of the right edge while
1362                          * ran_end is inclusive of the right edge.  The
1363                          * (key - data_len) left boundary is inclusive.
1364                          *
1365                          * XXX theory-check this test at some point, are
1366                          * we missing a + 1 somewhere?  Note that ran_end
1367                          * could overflow.
1368                          */
1369                         if (leaf->base.key - 1 > ran_end) {
1370                                 if (leaf->base.key - leaf->data_len > ran_end)
1371                                         break;
1372                                 panic("hammer right edge case\n");
1373                         }
1374                 }
1375
1376                 /*
1377                  * Mark the record and B-Tree entry as deleted.  This will
1378                  * also physically delete the B-Tree entry, record, and
1379                  * data if the retention policy dictates.  The function
1380                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1381                  * uses to perform a fixup.
1382                  */
1383                 error = hammer_ip_delete_record(cursor, trans->tid);
1384                 if (error)
1385                         break;
1386                 error = hammer_ip_next(cursor);
1387         }
1388         if (error == EDEADLK) {
1389                 hammer_done_cursor(cursor);
1390                 error = hammer_init_cursor(trans, cursor, &ip->cache[0], ip);
1391                 if (error == 0)
1392                         goto retry;
1393         }
1394         if (error == ENOENT)
1395                 error = 0;
1396         return(error);
1397 }
1398
1399 /*
1400  * Delete all user records associated with an inode except the inode record
1401  * itself.  Directory entries are not deleted (they must be properly disposed
1402  * of or nlinks would get upset).
1403  */
1404 int
1405 hammer_ip_delete_range_all(hammer_cursor_t cursor, hammer_inode_t ip,
1406                            int *countp)
1407 {
1408         hammer_transaction_t trans = cursor->trans;
1409         hammer_btree_leaf_elm_t leaf;
1410         int error;
1411
1412         KKASSERT(trans->type == HAMMER_TRANS_FLS);
1413 retry:
1414         hammer_normalize_cursor(cursor);
1415         cursor->key_beg.obj_id = ip->obj_id;
1416         cursor->key_beg.create_tid = 0;
1417         cursor->key_beg.delete_tid = 0;
1418         cursor->key_beg.obj_type = 0;
1419         cursor->key_beg.rec_type = HAMMER_RECTYPE_INODE + 1;
1420         cursor->key_beg.key = HAMMER_MIN_KEY;
1421
1422         cursor->key_end = cursor->key_beg;
1423         cursor->key_end.rec_type = 0xFFFF;
1424         cursor->key_end.key = HAMMER_MAX_KEY;
1425
1426         cursor->asof = ip->obj_asof;
1427         cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1428         cursor->flags |= HAMMER_CURSOR_END_INCLUSIVE | HAMMER_CURSOR_ASOF;
1429         cursor->flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
1430         cursor->flags |= HAMMER_CURSOR_BACKEND;
1431
1432         error = hammer_ip_first(cursor);
1433
1434         /*
1435          * Iterate through matching records and mark them as deleted.
1436          */
1437         while (error == 0) {
1438                 leaf = cursor->leaf;
1439
1440                 KKASSERT(leaf->base.delete_tid == 0);
1441
1442                 /*
1443                  * Mark the record and B-Tree entry as deleted.  This will
1444                  * also physically delete the B-Tree entry, record, and
1445                  * data if the retention policy dictates.  The function
1446                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1447                  * uses to perform a fixup.
1448                  *
1449                  * Directory entries (and delete-on-disk directory entries)
1450                  * must be synced and cannot be deleted.
1451                  */
1452                 if (leaf->base.rec_type != HAMMER_RECTYPE_DIRENTRY) {
1453                         error = hammer_ip_delete_record(cursor, trans->tid);
1454                         ++*countp;
1455                 }
1456                 if (error)
1457                         break;
1458                 error = hammer_ip_next(cursor);
1459         }
1460         if (error == EDEADLK) {
1461                 hammer_done_cursor(cursor);
1462                 error = hammer_init_cursor(trans, cursor, &ip->cache[0], ip);
1463                 if (error == 0)
1464                         goto retry;
1465         }
1466         if (error == ENOENT)
1467                 error = 0;
1468         return(error);
1469 }
1470
1471 /*
1472  * Delete the record at the current cursor.  On success the cursor will
1473  * be positioned appropriately for an iteration but may no longer be at
1474  * a leaf node.
1475  *
1476  * This routine is only called from the backend.
1477  *
1478  * NOTE: This can return EDEADLK, requiring the caller to terminate the
1479  * cursor and retry.
1480  */
1481 int
1482 hammer_ip_delete_record(hammer_cursor_t cursor, hammer_tid_t tid)
1483 {
1484         hammer_btree_elm_t elm;
1485         hammer_mount_t hmp;
1486         int error;
1487         int dodelete;
1488
1489         KKASSERT(cursor->flags & HAMMER_CURSOR_BACKEND);
1490
1491         /*
1492          * In-memory (unsynchronized) records can simply be freed.  This
1493          * only occurs in range iterations since all other records are
1494          * individually synchronized.  Thus there should be no confusion with
1495          * the interlock.
1496          */
1497         if (cursor->leaf == &cursor->iprec->leaf) {
1498                 KKASSERT((cursor->iprec->flags & HAMMER_RECF_INTERLOCK_BE) ==0);
1499                 cursor->iprec->flags |= HAMMER_RECF_DELETED_FE;
1500                 cursor->iprec->flags |= HAMMER_RECF_DELETED_BE;
1501                 return(0);
1502         }
1503
1504         /*
1505          * On-disk records are marked as deleted by updating their delete_tid.
1506          * This does not effect their position in the B-Tree (which is based
1507          * on their create_tid).
1508          */
1509         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1510         elm = NULL;
1511         hmp = cursor->node->hmp;
1512
1513         /*
1514          * If we were mounted with the nohistory option, we physically
1515          * delete the record.
1516          */
1517         if (hmp->hflags & HMNT_NOHISTORY)
1518                 dodelete = 1;
1519         else
1520                 dodelete = 0;
1521
1522         if (error == 0) {
1523                 error = hammer_cursor_upgrade(cursor);
1524                 if (error == 0) {
1525                         elm = &cursor->node->ondisk->elms[cursor->index];
1526                         hammer_modify_node(cursor->trans, cursor->node,
1527                                            &elm->leaf.base.delete_tid,
1528                                            sizeof(elm->leaf.base.delete_tid));
1529                         elm->leaf.base.delete_tid = tid;
1530                         hammer_modify_node_done(cursor->node);
1531
1532                         /*
1533                          * An on-disk record cannot have the same delete_tid
1534                          * as its create_tid.  In a chain of record updates
1535                          * this could result in a duplicate record.
1536                          */
1537                         KKASSERT(elm->leaf.base.delete_tid != elm->leaf.base.create_tid);
1538                 }
1539         }
1540
1541         if (error == 0 && dodelete) {
1542                 error = hammer_delete_at_cursor(cursor, NULL);
1543                 if (error) {
1544                         panic("hammer_ip_delete_record: unable to physically delete the record!\n");
1545                         error = 0;
1546                 }
1547         }
1548         return(error);
1549 }
1550
1551 int
1552 hammer_delete_at_cursor(hammer_cursor_t cursor, int64_t *stat_bytes)
1553 {
1554         hammer_btree_elm_t elm;
1555         hammer_off_t data_offset;
1556         int32_t data_len;
1557         u_int16_t rec_type;
1558         int error;
1559
1560         elm = &cursor->node->ondisk->elms[cursor->index];
1561         KKASSERT(elm->base.btype == HAMMER_BTREE_TYPE_RECORD);
1562
1563         data_offset = elm->leaf.data_offset;
1564         data_len = elm->leaf.data_len;
1565         rec_type = elm->leaf.base.rec_type;
1566
1567         error = hammer_btree_delete(cursor);
1568         if (error == 0) {
1569                 /*
1570                  * This forces a fixup for the iteration because
1571                  * the cursor is now either sitting at the 'next'
1572                  * element or sitting at the end of a leaf.
1573                  */
1574                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1575                         cursor->flags |= HAMMER_CURSOR_DELBTREE;
1576                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1577                 }
1578         }
1579         if (error == 0) {
1580                 switch(data_offset & HAMMER_OFF_ZONE_MASK) {
1581                 case HAMMER_ZONE_LARGE_DATA:
1582                 case HAMMER_ZONE_SMALL_DATA:
1583                         hammer_blockmap_free(cursor->trans,
1584                                              data_offset, data_len);
1585                         break;
1586                 default:
1587                         break;
1588                 }
1589         }
1590         return (error);
1591 }
1592
1593 /*
1594  * Determine whether we can remove a directory.  This routine checks whether
1595  * a directory is empty or not and enforces flush connectivity.
1596  *
1597  * Flush connectivity requires that we block if the target directory is
1598  * currently flushing, otherwise it may not end up in the same flush group.
1599  *
1600  * Returns 0 on success, ENOTEMPTY or EDEADLK (or other errors) on failure.
1601  */
1602 int
1603 hammer_ip_check_directory_empty(hammer_transaction_t trans, hammer_inode_t ip)
1604 {
1605         struct hammer_cursor cursor;
1606         int error;
1607
1608         /*
1609          * Check directory empty
1610          */
1611         hammer_init_cursor(trans, &cursor, &ip->cache[0], ip);
1612
1613         cursor.key_beg.obj_id = ip->obj_id;
1614         cursor.key_beg.create_tid = 0;
1615         cursor.key_beg.delete_tid = 0;
1616         cursor.key_beg.obj_type = 0;
1617         cursor.key_beg.rec_type = HAMMER_RECTYPE_INODE + 1;
1618         cursor.key_beg.key = HAMMER_MIN_KEY;
1619
1620         cursor.key_end = cursor.key_beg;
1621         cursor.key_end.rec_type = 0xFFFF;
1622         cursor.key_end.key = HAMMER_MAX_KEY;
1623
1624         cursor.asof = ip->obj_asof;
1625         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE | HAMMER_CURSOR_ASOF;
1626
1627         error = hammer_ip_first(&cursor);
1628         if (error == ENOENT)
1629                 error = 0;
1630         else if (error == 0)
1631                 error = ENOTEMPTY;
1632         hammer_done_cursor(&cursor);
1633         return(error);
1634 }
1635