sys/vfs/hammer/hammer_object.c

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