2 * Copyright (c) 2007-2008 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/sys/vfs/hammer/hammer_object.c,v 1.89 2008/07/13 09:32:48 dillon Exp $
39 static int hammer_mem_add(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 static int hammer_frontend_trunc_callback(hammer_record_t record,
44 static int hammer_record_needs_overwrite_delete(hammer_record_t record);
45 static int hammer_delete_general(hammer_cursor_t cursor, hammer_inode_t ip,
46 hammer_btree_leaf_elm_t leaf);
48 struct rec_trunc_info {
54 * Red-black tree support. Comparison code for insertion.
57 hammer_rec_rb_compare(hammer_record_t rec1, hammer_record_t rec2)
59 if (rec1->leaf.base.rec_type < rec2->leaf.base.rec_type)
61 if (rec1->leaf.base.rec_type > rec2->leaf.base.rec_type)
64 if (rec1->leaf.base.key < rec2->leaf.base.key)
66 if (rec1->leaf.base.key > rec2->leaf.base.key)
70 * Never match against an item deleted by the front-end.
72 * rec1 is greater then rec2 if rec1 is marked deleted.
73 * rec1 is less then rec2 if rec2 is marked deleted.
75 * Multiple deleted records may be present, do not return 0
76 * if both are marked deleted.
78 if (rec1->flags & HAMMER_RECF_DELETED_FE)
80 if (rec2->flags & HAMMER_RECF_DELETED_FE)
87 * Basic record comparison code similar to hammer_btree_cmp().
90 hammer_rec_cmp(hammer_base_elm_t elm, hammer_record_t rec)
92 if (elm->rec_type < rec->leaf.base.rec_type)
94 if (elm->rec_type > rec->leaf.base.rec_type)
97 if (elm->key < rec->leaf.base.key)
99 if (elm->key > rec->leaf.base.key)
103 * Never match against an item deleted by the front-end.
104 * elm is less then rec if rec is marked deleted.
106 if (rec->flags & HAMMER_RECF_DELETED_FE)
112 * Special LOOKUP_INFO to locate an overlapping record. This used by
113 * the reservation code to implement small-block records (whos keys will
114 * be different depending on data_len, when representing the same base
117 * NOTE: The base file offset of a data record is (key - data_len), not (key).
120 hammer_rec_overlap_compare(hammer_btree_leaf_elm_t leaf, hammer_record_t rec)
122 if (leaf->base.rec_type < rec->leaf.base.rec_type)
124 if (leaf->base.rec_type > rec->leaf.base.rec_type)
130 if (leaf->base.rec_type == HAMMER_RECTYPE_DATA) {
131 /* leaf_end <= rec_beg */
132 if (leaf->base.key <= rec->leaf.base.key - rec->leaf.data_len)
134 /* leaf_beg >= rec_end */
135 if (leaf->base.key - leaf->data_len >= rec->leaf.base.key)
138 if (leaf->base.key < rec->leaf.base.key)
140 if (leaf->base.key > rec->leaf.base.key)
145 * Never match against an item deleted by the front-end.
146 * leaf is less then rec if rec is marked deleted.
148 * We must still return the proper code for the scan to continue
149 * along the correct branches.
151 if (rec->flags & HAMMER_RECF_DELETED_FE) {
152 if (leaf->base.key < rec->leaf.base.key)
154 if (leaf->base.key > rec->leaf.base.key)
162 * RB_SCAN comparison code for hammer_mem_first(). The argument order
163 * is reversed so the comparison result has to be negated. key_beg and
164 * key_end are both range-inclusive.
166 * Localized deletions are not cached in-memory.
170 hammer_rec_scan_cmp(hammer_record_t rec, void *data)
172 hammer_cursor_t cursor = data;
175 r = hammer_rec_cmp(&cursor->key_beg, rec);
178 r = hammer_rec_cmp(&cursor->key_end, rec);
185 * This compare function is used when simply looking up key_beg.
189 hammer_rec_find_cmp(hammer_record_t rec, void *data)
191 hammer_cursor_t cursor = data;
194 r = hammer_rec_cmp(&cursor->key_beg, rec);
203 * Locate blocks within the truncation range. Partial blocks do not count.
207 hammer_rec_trunc_cmp(hammer_record_t rec, void *data)
209 struct rec_trunc_info *info = data;
211 if (rec->leaf.base.rec_type < info->rec_type)
213 if (rec->leaf.base.rec_type > info->rec_type)
216 switch(rec->leaf.base.rec_type) {
217 case HAMMER_RECTYPE_DB:
219 * DB record key is not beyond the truncation point, retain.
221 if (rec->leaf.base.key < info->trunc_off)
224 case HAMMER_RECTYPE_DATA:
226 * DATA record offset start is not beyond the truncation point,
229 if (rec->leaf.base.key - rec->leaf.data_len < info->trunc_off)
233 panic("hammer_rec_trunc_cmp: unexpected record type");
237 * The record start is >= the truncation point, return match,
238 * the record should be destroyed.
243 RB_GENERATE(hammer_rec_rb_tree, hammer_record, rb_node, hammer_rec_rb_compare);
244 RB_GENERATE_XLOOKUP(hammer_rec_rb_tree, INFO, hammer_record, rb_node,
245 hammer_rec_overlap_compare, hammer_btree_leaf_elm_t);
248 * Allocate a record for the caller to finish filling in. The record is
249 * returned referenced.
252 hammer_alloc_mem_record(hammer_inode_t ip, int data_len)
254 hammer_record_t record;
256 ++hammer_count_records;
257 record = kmalloc(sizeof(*record), M_HAMMER,
258 M_WAITOK | M_ZERO | M_USE_RESERVE);
259 record->flush_state = HAMMER_FST_IDLE;
261 record->leaf.base.btype = HAMMER_BTREE_TYPE_RECORD;
262 record->leaf.data_len = data_len;
263 hammer_ref(&record->lock);
266 record->data = kmalloc(data_len, M_HAMMER, M_WAITOK | M_ZERO);
267 record->flags |= HAMMER_RECF_ALLOCDATA;
268 ++hammer_count_record_datas;
275 hammer_wait_mem_record_ident(hammer_record_t record, const char *ident)
277 while (record->flush_state == HAMMER_FST_FLUSH) {
278 record->flags |= HAMMER_RECF_WANTED;
279 tsleep(record, 0, ident, 0);
284 * Called from the backend, hammer_inode.c, after a record has been
285 * flushed to disk. The record has been exclusively locked by the
286 * caller and interlocked with BE.
288 * We clean up the state, unlock, and release the record (the record
289 * was referenced by the fact that it was in the HAMMER_FST_FLUSH state).
292 hammer_flush_record_done(hammer_record_t record, int error)
294 hammer_inode_t target_ip;
296 KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
297 KKASSERT(record->flags & HAMMER_RECF_INTERLOCK_BE);
301 * An error occured, the backend was unable to sync the
302 * record to its media. Leave the record intact.
304 Debugger("flush_record_done error");
307 --record->flush_group->refs;
308 record->flush_group = NULL;
310 if (record->flags & HAMMER_RECF_DELETED_BE) {
311 if ((target_ip = record->target_ip) != NULL) {
312 TAILQ_REMOVE(&target_ip->target_list, record,
314 record->target_ip = NULL;
315 hammer_test_inode(target_ip);
317 record->flush_state = HAMMER_FST_IDLE;
319 if (record->target_ip) {
320 record->flush_state = HAMMER_FST_SETUP;
321 hammer_test_inode(record->ip);
322 hammer_test_inode(record->target_ip);
324 record->flush_state = HAMMER_FST_IDLE;
327 record->flags &= ~HAMMER_RECF_INTERLOCK_BE;
328 if (record->flags & HAMMER_RECF_WANTED) {
329 record->flags &= ~HAMMER_RECF_WANTED;
332 hammer_rel_mem_record(record);
336 * Release a memory record. Records marked for deletion are immediately
337 * removed from the RB-Tree but otherwise left intact until the last ref
341 hammer_rel_mem_record(struct hammer_record *record)
343 hammer_inode_t ip, target_ip;
345 hammer_unref(&record->lock);
347 if (record->lock.refs == 0) {
349 * Upon release of the last reference wakeup any waiters.
350 * The record structure may get destroyed so callers will
351 * loop up and do a relookup.
353 * WARNING! Record must be removed from RB-TREE before we
354 * might possibly block. hammer_test_inode() can block!
359 * Upon release of the last reference a record marked deleted
362 if (record->flags & HAMMER_RECF_DELETED_FE) {
363 KKASSERT(ip->lock.refs > 0);
364 KKASSERT(record->flush_state != HAMMER_FST_FLUSH);
367 * target_ip may have zero refs, we have to ref it
368 * to prevent it from being ripped out from under
371 if ((target_ip = record->target_ip) != NULL) {
372 TAILQ_REMOVE(&target_ip->target_list,
373 record, target_entry);
374 record->target_ip = NULL;
375 hammer_ref(&target_ip->lock);
378 if (record->flags & HAMMER_RECF_ONRBTREE) {
379 RB_REMOVE(hammer_rec_rb_tree,
380 &record->ip->rec_tree,
382 KKASSERT(ip->rsv_recs > 0);
385 ip->hmp->rsv_databytes -= record->leaf.data_len;
386 record->flags &= ~HAMMER_RECF_ONRBTREE;
388 if (RB_EMPTY(&record->ip->rec_tree)) {
389 record->ip->flags &= ~HAMMER_INODE_XDIRTY;
390 record->ip->sync_flags &= ~HAMMER_INODE_XDIRTY;
391 hammer_test_inode(record->ip);
396 * Do this test after removing record from the B-Tree.
399 hammer_test_inode(target_ip);
400 hammer_rel_inode(target_ip, 0);
403 if (record->flags & HAMMER_RECF_ALLOCDATA) {
404 --hammer_count_record_datas;
405 kfree(record->data, M_HAMMER);
406 record->flags &= ~HAMMER_RECF_ALLOCDATA;
409 hammer_blockmap_reserve_complete(ip->hmp,
414 --hammer_count_records;
415 kfree(record, M_HAMMER);
421 * Record visibility depends on whether the record is being accessed by
422 * the backend or the frontend.
424 * Return non-zero if the record is visible, zero if it isn't or if it is
429 hammer_ip_iterate_mem_good(hammer_cursor_t cursor, hammer_record_t record)
431 if (cursor->flags & HAMMER_CURSOR_BACKEND) {
432 if (record->flags & HAMMER_RECF_DELETED_BE)
435 if (record->flags & HAMMER_RECF_DELETED_FE)
442 * This callback is used as part of the RB_SCAN function for in-memory
443 * records. We terminate it (return -1) as soon as we get a match.
445 * This routine is used by frontend code.
447 * The primary compare code does not account for ASOF lookups. This
448 * code handles that case as well as a few others.
452 hammer_rec_scan_callback(hammer_record_t rec, void *data)
454 hammer_cursor_t cursor = data;
457 * We terminate on success, so this should be NULL on entry.
459 KKASSERT(cursor->iprec == NULL);
462 * Skip if the record was marked deleted.
464 if (hammer_ip_iterate_mem_good(cursor, rec) == 0)
468 * Skip if not visible due to our as-of TID
470 if (cursor->flags & HAMMER_CURSOR_ASOF) {
471 if (cursor->asof < rec->leaf.base.create_tid)
473 if (rec->leaf.base.delete_tid &&
474 cursor->asof >= rec->leaf.base.delete_tid) {
480 * ref the record. The record is protected from backend B-Tree
481 * interactions by virtue of the cursor's IP lock.
483 hammer_ref(&rec->lock);
486 * The record may have been deleted while we were blocked.
488 if (hammer_ip_iterate_mem_good(cursor, rec) == 0) {
489 hammer_rel_mem_record(rec);
494 * Set the matching record and stop the scan.
502 * Lookup an in-memory record given the key specified in the cursor. Works
503 * just like hammer_btree_lookup() but operates on an inode's in-memory
506 * The lookup must fail if the record is marked for deferred deletion.
510 hammer_mem_lookup(hammer_cursor_t cursor)
514 KKASSERT(cursor->ip);
516 hammer_rel_mem_record(cursor->iprec);
517 cursor->iprec = NULL;
519 hammer_rec_rb_tree_RB_SCAN(&cursor->ip->rec_tree, hammer_rec_find_cmp,
520 hammer_rec_scan_callback, cursor);
522 if (cursor->iprec == NULL)
530 * hammer_mem_first() - locate the first in-memory record matching the
531 * cursor within the bounds of the key range.
535 hammer_mem_first(hammer_cursor_t cursor)
540 KKASSERT(ip != NULL);
543 hammer_rel_mem_record(cursor->iprec);
544 cursor->iprec = NULL;
547 hammer_rec_rb_tree_RB_SCAN(&ip->rec_tree, hammer_rec_scan_cmp,
548 hammer_rec_scan_callback, cursor);
551 * Adjust scan.node and keep it linked into the RB-tree so we can
552 * hold the cursor through third party modifications of the RB-tree.
559 /************************************************************************
560 * HAMMER IN-MEMORY RECORD FUNCTIONS *
561 ************************************************************************
563 * These functions manipulate in-memory records. Such records typically
564 * exist prior to being committed to disk or indexed via the on-disk B-Tree.
568 * Add a directory entry (dip,ncp) which references inode (ip).
570 * Note that the low 32 bits of the namekey are set temporarily to create
571 * a unique in-memory record, and may be modified a second time when the
572 * record is synchronized to disk. In particular, the low 32 bits cannot be
573 * all 0's when synching to disk, which is not handled here.
575 * NOTE: bytes does not include any terminating \0 on name, and name might
579 hammer_ip_add_directory(struct hammer_transaction *trans,
580 struct hammer_inode *dip, const char *name, int bytes,
581 struct hammer_inode *ip)
583 struct hammer_cursor cursor;
584 hammer_record_t record;
589 record = hammer_alloc_mem_record(dip, HAMMER_ENTRY_SIZE(bytes));
590 if (++trans->hmp->namekey_iterator == 0)
591 ++trans->hmp->namekey_iterator;
593 record->type = HAMMER_MEM_RECORD_ADD;
594 record->leaf.base.localization = dip->obj_localization +
595 HAMMER_LOCALIZE_MISC;
596 record->leaf.base.obj_id = dip->obj_id;
597 record->leaf.base.key = hammer_directory_namekey(name, bytes);
598 record->leaf.base.key += trans->hmp->namekey_iterator;
599 record->leaf.base.rec_type = HAMMER_RECTYPE_DIRENTRY;
600 record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
601 record->data->entry.obj_id = ip->obj_id;
602 record->data->entry.localization = ip->obj_localization;
603 bcopy(name, record->data->entry.name, bytes);
605 ++ip->ino_data.nlinks;
606 hammer_modify_inode(ip, HAMMER_INODE_DDIRTY);
609 * Find an unused namekey. Both the in-memory record tree and
610 * the B-Tree are checked. Exact matches also match create_tid
611 * so use an ASOF search to (mostly) ignore it.
613 * delete-visibility is set so pending deletions do not give us
614 * a false-negative on our ability to use an iterator.
616 hammer_init_cursor(trans, &cursor, &dip->cache[1], dip);
617 cursor.key_beg = record->leaf.base;
618 cursor.flags |= HAMMER_CURSOR_ASOF;
619 cursor.flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
620 cursor.asof = ip->obj_asof;
623 while (hammer_ip_lookup(&cursor) == 0) {
624 iterator = (u_int32_t)record->leaf.base.key + 1;
627 record->leaf.base.key &= ~0xFFFFFFFFLL;
628 record->leaf.base.key |= iterator;
629 cursor.key_beg.key = record->leaf.base.key;
630 if (++count == 1000000000) {
631 hammer_rel_mem_record(record);
638 * The target inode and the directory entry are bound together.
640 record->target_ip = ip;
641 record->flush_state = HAMMER_FST_SETUP;
642 TAILQ_INSERT_TAIL(&ip->target_list, record, target_entry);
645 * The inode now has a dependancy and must be taken out of the idle
646 * state. An inode not in an idle state is given an extra reference.
648 if (ip->flush_state == HAMMER_FST_IDLE) {
649 hammer_ref(&ip->lock);
650 ip->flush_state = HAMMER_FST_SETUP;
652 error = hammer_mem_add(record);
654 hammer_done_cursor(&cursor);
659 * Delete the directory entry and update the inode link count. The
660 * cursor must be seeked to the directory entry record being deleted.
662 * The related inode should be share-locked by the caller. The caller is
665 * This function can return EDEADLK requiring the caller to terminate
666 * the cursor, any locks, wait on the returned record, and retry.
669 hammer_ip_del_directory(struct hammer_transaction *trans,
670 hammer_cursor_t cursor, struct hammer_inode *dip,
671 struct hammer_inode *ip)
673 hammer_record_t record;
676 if (hammer_cursor_inmem(cursor)) {
678 * In-memory (unsynchronized) records can simply be freed.
679 * Even though the HAMMER_RECF_DELETED_FE flag is ignored
680 * by the backend, we must still avoid races against the
681 * backend potentially syncing the record to the media.
683 * We cannot call hammer_ip_delete_record(), that routine may
684 * only be called from the backend.
686 record = cursor->iprec;
687 if (record->flags & HAMMER_RECF_INTERLOCK_BE) {
688 KKASSERT(cursor->deadlk_rec == NULL);
689 hammer_ref(&record->lock);
690 cursor->deadlk_rec = record;
693 KKASSERT(record->type == HAMMER_MEM_RECORD_ADD);
694 record->flags |= HAMMER_RECF_DELETED_FE;
699 * If the record is on-disk we have to queue the deletion by
700 * the record's key. This also causes lookups to skip the
703 KKASSERT(dip->flags &
704 (HAMMER_INODE_ONDISK | HAMMER_INODE_DONDISK));
705 record = hammer_alloc_mem_record(dip, 0);
706 record->type = HAMMER_MEM_RECORD_DEL;
707 record->leaf.base = cursor->leaf->base;
709 record->target_ip = ip;
710 record->flush_state = HAMMER_FST_SETUP;
711 TAILQ_INSERT_TAIL(&ip->target_list, record, target_entry);
714 * The inode now has a dependancy and must be taken out of
715 * the idle state. An inode not in an idle state is given
716 * an extra reference.
718 if (ip->flush_state == HAMMER_FST_IDLE) {
719 hammer_ref(&ip->lock);
720 ip->flush_state = HAMMER_FST_SETUP;
723 error = hammer_mem_add(record);
727 * One less link. The file may still be open in the OS even after
728 * all links have gone away.
730 * We have to terminate the cursor before syncing the inode to
731 * avoid deadlocking against ourselves. XXX this may no longer
734 * If nlinks drops to zero and the vnode is inactive (or there is
735 * no vnode), call hammer_inode_unloadable_check() to zonk the
736 * inode. If we don't do this here the inode will not be destroyed
737 * on-media until we unmount.
740 --ip->ino_data.nlinks;
741 hammer_modify_inode(ip, HAMMER_INODE_DDIRTY);
742 if (ip->ino_data.nlinks == 0 &&
743 (ip->vp == NULL || (ip->vp->v_flag & VINACTIVE))) {
744 hammer_done_cursor(cursor);
745 hammer_inode_unloadable_check(ip, 1);
746 hammer_flush_inode(ip, 0);
754 * Add a record to an inode.
756 * The caller must allocate the record with hammer_alloc_mem_record(ip) and
757 * initialize the following additional fields:
759 * The related inode should be share-locked by the caller. The caller is
762 * record->rec.entry.base.base.key
763 * record->rec.entry.base.base.rec_type
764 * record->rec.entry.base.base.data_len
765 * record->data (a copy will be kmalloc'd if it cannot be embedded)
768 hammer_ip_add_record(struct hammer_transaction *trans, hammer_record_t record)
770 hammer_inode_t ip = record->ip;
773 KKASSERT(record->leaf.base.localization != 0);
774 record->leaf.base.obj_id = ip->obj_id;
775 record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
776 error = hammer_mem_add(record);
781 * Locate a bulk record in-memory. Bulk records allow disk space to be
782 * reserved so the front-end can flush large data writes without having
783 * to queue the BIO to the flusher. Only the related record gets queued
786 static hammer_record_t
787 hammer_ip_get_bulk(hammer_inode_t ip, off_t file_offset, int bytes)
789 hammer_record_t record;
790 struct hammer_btree_leaf_elm leaf;
792 bzero(&leaf, sizeof(leaf));
793 leaf.base.obj_id = ip->obj_id;
794 leaf.base.key = file_offset + bytes;
795 leaf.base.create_tid = 0;
796 leaf.base.delete_tid = 0;
797 leaf.base.rec_type = HAMMER_RECTYPE_DATA;
798 leaf.base.obj_type = 0; /* unused */
799 leaf.base.btype = HAMMER_BTREE_TYPE_RECORD; /* unused */
800 leaf.base.localization = ip->obj_localization + HAMMER_LOCALIZE_MISC;
801 leaf.data_len = bytes;
803 record = hammer_rec_rb_tree_RB_LOOKUP_INFO(&ip->rec_tree, &leaf);
805 hammer_ref(&record->lock);
810 * Reserve blockmap space placemarked with an in-memory record.
812 * This routine is called by the frontend in order to be able to directly
813 * flush a buffer cache buffer. The frontend has locked the related buffer
814 * cache buffers and we should be able to manipulate any overlapping
818 hammer_ip_add_bulk(hammer_inode_t ip, off_t file_offset, void *data, int bytes,
821 hammer_record_t record;
822 hammer_record_t conflict;
827 * Deal with conflicting in-memory records. We cannot have multiple
828 * in-memory records for the same offset without seriously confusing
829 * the backend, including but not limited to the backend issuing
830 * delete-create-delete sequences and asserting on the delete_tid
831 * being the same as the create_tid.
833 * If we encounter a record with the backend interlock set we cannot
834 * immediately delete it without confusing the backend.
836 while ((conflict = hammer_ip_get_bulk(ip, file_offset, bytes)) !=NULL) {
837 if (conflict->flags & HAMMER_RECF_INTERLOCK_BE) {
838 conflict->flags |= HAMMER_RECF_WANTED;
839 tsleep(conflict, 0, "hmrrc3", 0);
841 conflict->flags |= HAMMER_RECF_DELETED_FE;
843 hammer_rel_mem_record(conflict);
847 * Create a record to cover the direct write. This is called with
848 * the related BIO locked so there should be no possible conflict.
850 * The backend is responsible for finalizing the space reserved in
853 * XXX bytes not aligned, depend on the reservation code to
854 * align the reservation.
856 record = hammer_alloc_mem_record(ip, 0);
857 zone = (bytes >= HAMMER_BUFSIZE) ? HAMMER_ZONE_LARGE_DATA_INDEX :
858 HAMMER_ZONE_SMALL_DATA_INDEX;
859 record->resv = hammer_blockmap_reserve(ip->hmp, zone, bytes,
860 &record->leaf.data_offset,
862 if (record->resv == NULL) {
863 kprintf("hammer_ip_add_bulk: reservation failed\n");
864 hammer_rel_mem_record(record);
867 record->type = HAMMER_MEM_RECORD_DATA;
868 record->leaf.base.rec_type = HAMMER_RECTYPE_DATA;
869 record->leaf.base.obj_type = ip->ino_leaf.base.obj_type;
870 record->leaf.base.obj_id = ip->obj_id;
871 record->leaf.base.key = file_offset + bytes;
872 record->leaf.base.localization = ip->obj_localization +
873 HAMMER_LOCALIZE_MISC;
874 record->leaf.data_len = bytes;
875 hammer_crc_set_leaf(data, &record->leaf);
876 flags = record->flags;
878 hammer_ref(&record->lock); /* mem_add eats a reference */
879 *errorp = hammer_mem_add(record);
881 conflict = hammer_ip_get_bulk(ip, file_offset, bytes);
882 kprintf("hammer_ip_add_bulk: error %d conflict %p file_offset %lld bytes %d\n",
883 *errorp, conflict, file_offset, bytes);
885 kprintf("conflict %lld %d\n", conflict->leaf.base.key, conflict->leaf.data_len);
887 hammer_rel_mem_record(conflict);
889 KKASSERT(*errorp == 0);
890 conflict = hammer_ip_get_bulk(ip, file_offset, bytes);
891 if (conflict != record) {
892 kprintf("conflict mismatch %p %p %08x\n", conflict, record, record->flags);
894 kprintf("conflict mismatch %lld/%d %lld/%d\n", conflict->leaf.base.key, conflict->leaf.data_len, record->leaf.base.key, record->leaf.data_len);
896 KKASSERT(conflict == record);
897 hammer_rel_mem_record(conflict);
903 * Frontend truncation code. Scan in-memory records only. On-disk records
904 * and records in a flushing state are handled by the backend. The vnops
905 * setattr code will handle the block containing the truncation point.
907 * Partial blocks are not deleted.
910 hammer_ip_frontend_trunc(struct hammer_inode *ip, off_t file_size)
912 struct rec_trunc_info info;
914 switch(ip->ino_data.obj_type) {
915 case HAMMER_OBJTYPE_REGFILE:
916 info.rec_type = HAMMER_RECTYPE_DATA;
918 case HAMMER_OBJTYPE_DBFILE:
919 info.rec_type = HAMMER_RECTYPE_DB;
924 info.trunc_off = file_size;
925 hammer_rec_rb_tree_RB_SCAN(&ip->rec_tree, hammer_rec_trunc_cmp,
926 hammer_frontend_trunc_callback, &info);
931 hammer_frontend_trunc_callback(hammer_record_t record, void *data __unused)
933 if (record->flags & HAMMER_RECF_DELETED_FE)
935 if (record->flush_state == HAMMER_FST_FLUSH)
937 KKASSERT((record->flags & HAMMER_RECF_INTERLOCK_BE) == 0);
938 hammer_ref(&record->lock);
939 record->flags |= HAMMER_RECF_DELETED_FE;
940 hammer_rel_mem_record(record);
945 * Return 1 if the caller must check for and delete existing records
946 * before writing out a new data record.
948 * Return 0 if the caller can just insert the record into the B-Tree without
952 hammer_record_needs_overwrite_delete(hammer_record_t record)
954 hammer_inode_t ip = record->ip;
958 if (ip->ino_data.obj_type == HAMMER_OBJTYPE_DBFILE)
959 file_offset = record->leaf.base.key;
961 file_offset = record->leaf.base.key - record->leaf.data_len;
962 r = (file_offset < ip->save_trunc_off);
963 if (ip->ino_data.obj_type == HAMMER_OBJTYPE_DBFILE) {
964 if (ip->save_trunc_off <= record->leaf.base.key)
965 ip->save_trunc_off = record->leaf.base.key + 1;
967 if (ip->save_trunc_off < record->leaf.base.key)
968 ip->save_trunc_off = record->leaf.base.key;
974 * Backend code. Sync a record to the media.
977 hammer_ip_sync_record_cursor(hammer_cursor_t cursor, hammer_record_t record)
979 hammer_transaction_t trans = cursor->trans;
986 KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
987 KKASSERT(record->flags & HAMMER_RECF_INTERLOCK_BE);
988 KKASSERT(record->leaf.base.localization != 0);
991 * If this is a bulk-data record placemarker there may be an existing
992 * record on-disk, indicating a data overwrite. If there is the
993 * on-disk record must be deleted before we can insert our new record.
995 * We've synthesized this record and do not know what the create_tid
996 * on-disk is, nor how much data it represents.
998 * Keep in mind that (key) for data records is (base_offset + len),
999 * not (base_offset). Also, we only want to get rid of on-disk
1000 * records since we are trying to sync our in-memory record, call
1001 * hammer_ip_delete_range() with truncating set to 1 to make sure
1002 * it skips in-memory records.
1004 * It is ok for the lookup to return ENOENT.
1006 * NOTE OPTIMIZATION: sync_trunc_off is used to determine if we have
1007 * to call hammer_ip_delete_range() or not. This also means we must
1008 * update sync_trunc_off() as we write.
1010 if (record->type == HAMMER_MEM_RECORD_DATA &&
1011 hammer_record_needs_overwrite_delete(record)) {
1012 file_offset = record->leaf.base.key - record->leaf.data_len;
1013 bytes = (record->leaf.data_len + HAMMER_BUFMASK) &
1015 KKASSERT((file_offset & HAMMER_BUFMASK) == 0);
1016 error = hammer_ip_delete_range(
1018 file_offset, file_offset + bytes - 1,
1020 if (error && error != ENOENT)
1025 * If this is a general record there may be an on-disk version
1026 * that must be deleted before we can insert the new record.
1028 if (record->type == HAMMER_MEM_RECORD_GENERAL) {
1029 error = hammer_delete_general(cursor, record->ip,
1031 if (error && error != ENOENT)
1038 hammer_normalize_cursor(cursor);
1039 cursor->key_beg = record->leaf.base;
1040 cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1041 cursor->flags |= HAMMER_CURSOR_BACKEND;
1042 cursor->flags &= ~HAMMER_CURSOR_INSERT;
1045 * Records can wind up on-media before the inode itself is on-media.
1048 record->ip->flags |= HAMMER_INODE_DONDISK;
1051 * If we are deleting a directory entry an exact match must be
1054 if (record->type == HAMMER_MEM_RECORD_DEL) {
1055 error = hammer_btree_lookup(cursor);
1058 error = hammer_ip_delete_record(cursor, record->ip,
1061 record->flags |= HAMMER_RECF_DELETED_FE;
1062 record->flags |= HAMMER_RECF_DELETED_BE;
1071 * Issue a lookup to position the cursor and locate the cluster. The
1072 * target key should not exist. If we are creating a directory entry
1073 * we may have to iterate the low 32 bits of the key to find an unused
1076 hammer_sync_lock_sh(trans);
1077 cursor->flags |= HAMMER_CURSOR_INSERT;
1078 error = hammer_btree_lookup(cursor);
1079 if (hammer_debug_inode)
1080 kprintf("DOINSERT LOOKUP %d\n", error);
1082 kprintf("hammer_ip_sync_record: duplicate rec "
1083 "at (%016llx)\n", record->leaf.base.key);
1084 Debugger("duplicate record1");
1088 if (record->type == HAMMER_MEM_RECORD_DATA)
1089 kprintf("sync_record %016llx ---------------- %016llx %d\n",
1090 record->leaf.base.key - record->leaf.data_len,
1091 record->leaf.data_offset, error);
1094 if (error != ENOENT)
1098 * Allocate the record and data. The result buffers will be
1099 * marked as being modified and further calls to
1100 * hammer_modify_buffer() will result in unneeded UNDO records.
1102 * Support zero-fill records (data == NULL and data_len != 0)
1104 if (record->type == HAMMER_MEM_RECORD_DATA) {
1106 * The data portion of a bulk-data record has already been
1107 * committed to disk, we need only adjust the layer2
1108 * statistics in the same transaction as our B-Tree insert.
1110 KKASSERT(record->leaf.data_offset != 0);
1111 hammer_blockmap_finalize(trans, record->leaf.data_offset,
1112 record->leaf.data_len);
1114 } else if (record->data && record->leaf.data_len) {
1116 * Wholely cached record, with data. Allocate the data.
1118 bdata = hammer_alloc_data(trans, record->leaf.data_len,
1119 record->leaf.base.rec_type,
1120 &record->leaf.data_offset,
1121 &cursor->data_buffer, &error);
1124 hammer_crc_set_leaf(record->data, &record->leaf);
1125 hammer_modify_buffer(trans, cursor->data_buffer, NULL, 0);
1126 bcopy(record->data, bdata, record->leaf.data_len);
1127 hammer_modify_buffer_done(cursor->data_buffer);
1130 * Wholely cached record, without data.
1132 record->leaf.data_offset = 0;
1133 record->leaf.data_crc = 0;
1136 error = hammer_btree_insert(cursor, &record->leaf, &doprop);
1137 if (hammer_debug_inode && error)
1138 kprintf("BTREE INSERT error %d @ %016llx:%d key %016llx\n", error, cursor->node->node_offset, cursor->index, record->leaf.base.key);
1141 * Our record is on-disk, normally mark the in-memory version as
1142 * deleted. If the record represented a directory deletion but
1143 * we had to sync a valid directory entry to disk we must convert
1144 * the record to a covering delete so the frontend does not have
1145 * visibility on the synced entry.
1149 hammer_btree_do_propagation(cursor,
1153 if (record->flags & HAMMER_RECF_CONVERT_DELETE) {
1154 KKASSERT(record->type == HAMMER_MEM_RECORD_ADD);
1155 record->flags &= ~HAMMER_RECF_DELETED_FE;
1156 record->type = HAMMER_MEM_RECORD_DEL;
1157 KKASSERT(record->flush_state == HAMMER_FST_FLUSH);
1158 record->flags &= ~HAMMER_RECF_CONVERT_DELETE;
1159 /* hammer_flush_record_done takes care of the rest */
1161 record->flags |= HAMMER_RECF_DELETED_FE;
1162 record->flags |= HAMMER_RECF_DELETED_BE;
1165 if (record->leaf.data_offset) {
1166 hammer_blockmap_free(trans, record->leaf.data_offset,
1167 record->leaf.data_len);
1171 hammer_sync_unlock(trans);
1177 * Add the record to the inode's rec_tree. The low 32 bits of a directory
1178 * entry's key is used to deal with hash collisions in the upper 32 bits.
1179 * A unique 64 bit key is generated in-memory and may be regenerated a
1180 * second time when the directory record is flushed to the on-disk B-Tree.
1182 * A referenced record is passed to this function. This function
1183 * eats the reference. If an error occurs the record will be deleted.
1185 * A copy of the temporary record->data pointer provided by the caller
1190 hammer_mem_add(hammer_record_t record)
1192 hammer_mount_t hmp = record->ip->hmp;
1195 * Make a private copy of record->data
1198 KKASSERT(record->flags & HAMMER_RECF_ALLOCDATA);
1201 * Insert into the RB tree. A unique key should have already
1202 * been selected if this is a directory entry.
1204 if (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) {
1205 record->flags |= HAMMER_RECF_DELETED_FE;
1206 hammer_rel_mem_record(record);
1209 ++hmp->count_newrecords;
1211 ++record->ip->rsv_recs;
1212 record->ip->hmp->rsv_databytes += record->leaf.data_len;
1213 record->flags |= HAMMER_RECF_ONRBTREE;
1214 hammer_modify_inode(record->ip, HAMMER_INODE_XDIRTY);
1215 hammer_rel_mem_record(record);
1219 /************************************************************************
1220 * HAMMER INODE MERGED-RECORD FUNCTIONS *
1221 ************************************************************************
1223 * These functions augment the B-Tree scanning functions in hammer_btree.c
1224 * by merging in-memory records with on-disk records.
1228 * Locate a particular record either in-memory or on-disk.
1230 * NOTE: This is basically a standalone routine, hammer_ip_next() may
1231 * NOT be called to iterate results.
1234 hammer_ip_lookup(hammer_cursor_t cursor)
1239 * If the element is in-memory return it without searching the
1242 KKASSERT(cursor->ip);
1243 error = hammer_mem_lookup(cursor);
1245 cursor->leaf = &cursor->iprec->leaf;
1248 if (error != ENOENT)
1252 * If the inode has on-disk components search the on-disk B-Tree.
1254 if ((cursor->ip->flags & (HAMMER_INODE_ONDISK|HAMMER_INODE_DONDISK)) == 0)
1256 error = hammer_btree_lookup(cursor);
1258 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1263 * Locate the first record within the cursor's key_beg/key_end range,
1264 * restricted to a particular inode. 0 is returned on success, ENOENT
1265 * if no records matched the requested range, or some other error.
1267 * When 0 is returned hammer_ip_next() may be used to iterate additional
1268 * records within the requested range.
1270 * This function can return EDEADLK, requiring the caller to terminate
1271 * the cursor and try again.
1274 hammer_ip_first(hammer_cursor_t cursor)
1276 hammer_inode_t ip = cursor->ip;
1279 KKASSERT(ip != NULL);
1282 * Clean up fields and setup for merged scan
1284 cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1285 cursor->flags |= HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM;
1286 cursor->flags |= HAMMER_CURSOR_DISKEOF | HAMMER_CURSOR_MEMEOF;
1287 if (cursor->iprec) {
1288 hammer_rel_mem_record(cursor->iprec);
1289 cursor->iprec = NULL;
1293 * Search the on-disk B-Tree. hammer_btree_lookup() only does an
1294 * exact lookup so if we get ENOENT we have to call the iterate
1295 * function to validate the first record after the begin key.
1297 * The ATEDISK flag is used by hammer_btree_iterate to determine
1298 * whether it must index forwards or not. It is also used here
1299 * to select the next record from in-memory or on-disk.
1301 * EDEADLK can only occur if the lookup hit an empty internal
1302 * element and couldn't delete it. Since this could only occur
1303 * in-range, we can just iterate from the failure point.
1305 if (ip->flags & (HAMMER_INODE_ONDISK|HAMMER_INODE_DONDISK)) {
1306 error = hammer_btree_lookup(cursor);
1307 if (error == ENOENT || error == EDEADLK) {
1308 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1309 if (hammer_debug_general & 0x2000)
1310 kprintf("error %d node %p %016llx index %d\n", error, cursor->node, cursor->node->node_offset, cursor->index);
1311 error = hammer_btree_iterate(cursor);
1313 if (error && error != ENOENT)
1316 cursor->flags &= ~HAMMER_CURSOR_DISKEOF;
1317 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1319 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1324 * Search the in-memory record list (Red-Black tree). Unlike the
1325 * B-Tree search, mem_first checks for records in the range.
1327 error = hammer_mem_first(cursor);
1328 if (error && error != ENOENT)
1331 cursor->flags &= ~HAMMER_CURSOR_MEMEOF;
1332 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
1333 if (hammer_ip_iterate_mem_good(cursor, cursor->iprec) == 0)
1334 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1338 * This will return the first matching record.
1340 return(hammer_ip_next(cursor));
1344 * Retrieve the next record in a merged iteration within the bounds of the
1345 * cursor. This call may be made multiple times after the cursor has been
1346 * initially searched with hammer_ip_first().
1348 * 0 is returned on success, ENOENT if no further records match the
1349 * requested range, or some other error code is returned.
1352 hammer_ip_next(hammer_cursor_t cursor)
1354 hammer_btree_elm_t elm;
1355 hammer_record_t rec, save;
1361 * Load the current on-disk and in-memory record. If we ate any
1362 * records we have to get the next one.
1364 * If we deleted the last on-disk record we had scanned ATEDISK will
1365 * be clear and DELBTREE will be set, forcing a call to iterate. The
1366 * fact that ATEDISK is clear causes iterate to re-test the 'current'
1367 * element. If ATEDISK is set, iterate will skip the 'current'
1370 * Get the next on-disk record
1372 if (cursor->flags & (HAMMER_CURSOR_ATEDISK|HAMMER_CURSOR_DELBTREE)) {
1373 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1374 error = hammer_btree_iterate(cursor);
1375 cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1377 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1378 hammer_cache_node(&cursor->ip->cache[1],
1381 cursor->flags |= HAMMER_CURSOR_DISKEOF |
1382 HAMMER_CURSOR_ATEDISK;
1389 * Get the next in-memory record.
1391 * hammer_rec_scan_cmp: Is the record still in our general range,
1392 * (non-inclusive of snapshot exclusions)?
1393 * hammer_rec_scan_callback: Is the record in our snapshot?
1395 if (cursor->flags & HAMMER_CURSOR_ATEMEM) {
1396 if ((cursor->flags & HAMMER_CURSOR_MEMEOF) == 0) {
1397 save = cursor->iprec;
1398 cursor->iprec = NULL;
1399 rec = save ? hammer_rec_rb_tree_RB_NEXT(save) : NULL;
1401 if (hammer_rec_scan_cmp(rec, cursor) != 0)
1403 if (hammer_rec_scan_callback(rec, cursor) != 0)
1405 rec = hammer_rec_rb_tree_RB_NEXT(rec);
1408 hammer_rel_mem_record(save);
1409 if (cursor->iprec) {
1410 KKASSERT(cursor->iprec == rec);
1411 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
1413 cursor->flags |= HAMMER_CURSOR_MEMEOF;
1419 * The memory record may have become stale while being held in
1420 * cursor->iprec. We are interlocked against the backend on
1421 * with regards to B-Tree entries.
1423 if ((cursor->flags & HAMMER_CURSOR_ATEMEM) == 0) {
1424 if (hammer_ip_iterate_mem_good(cursor, cursor->iprec) == 0) {
1425 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1431 * Extract either the disk or memory record depending on their
1432 * relative position.
1435 switch(cursor->flags & (HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM)) {
1438 * Both entries valid. Compare the entries and nominally
1439 * return the first one in the sort order. Numerous cases
1440 * require special attention, however.
1442 elm = &cursor->node->ondisk->elms[cursor->index];
1443 r = hammer_btree_cmp(&elm->base, &cursor->iprec->leaf.base);
1446 * If the two entries differ only by their key (-2/2) or
1447 * create_tid (-1/1), and are DATA records, we may have a
1448 * nominal match. We have to calculate the base file
1449 * offset of the data.
1451 if (r <= 2 && r >= -2 && r != 0 &&
1452 cursor->ip->ino_data.obj_type == HAMMER_OBJTYPE_REGFILE &&
1453 cursor->iprec->type == HAMMER_MEM_RECORD_DATA) {
1454 int64_t base1 = elm->leaf.base.key - elm->leaf.data_len;
1455 int64_t base2 = cursor->iprec->leaf.base.key -
1456 cursor->iprec->leaf.data_len;
1462 error = hammer_btree_extract(cursor,
1463 HAMMER_CURSOR_GET_LEAF);
1464 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1469 * If the entries match exactly the memory entry is either
1470 * an on-disk directory entry deletion or a bulk data
1471 * overwrite. If it is a directory entry deletion we eat
1474 * For the bulk-data overwrite case it is possible to have
1475 * visibility into both, which simply means the syncer
1476 * hasn't gotten around to doing the delete+insert sequence
1477 * on the B-Tree. Use the memory entry and throw away the
1480 * If the in-memory record is not either of these we
1481 * probably caught the syncer while it was syncing it to
1482 * the media. Since we hold a shared lock on the cursor,
1483 * the in-memory record had better be marked deleted at
1487 if (cursor->iprec->type == HAMMER_MEM_RECORD_DEL) {
1488 if ((cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1489 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1490 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1493 } else if (cursor->iprec->type == HAMMER_MEM_RECORD_DATA) {
1494 if ((cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1495 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1497 /* fall through to memory entry */
1499 panic("hammer_ip_next: duplicate mem/b-tree entry %p %d %08x", cursor->iprec, cursor->iprec->type, cursor->iprec->flags);
1500 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1504 /* fall through to the memory entry */
1505 case HAMMER_CURSOR_ATEDISK:
1507 * Only the memory entry is valid.
1509 cursor->leaf = &cursor->iprec->leaf;
1510 cursor->flags |= HAMMER_CURSOR_ATEMEM;
1513 * If the memory entry is an on-disk deletion we should have
1514 * also had found a B-Tree record. If the backend beat us
1515 * to it it would have interlocked the cursor and we should
1516 * have seen the in-memory record marked DELETED_FE.
1518 if (cursor->iprec->type == HAMMER_MEM_RECORD_DEL &&
1519 (cursor->flags & HAMMER_CURSOR_DELETE_VISIBILITY) == 0) {
1520 panic("hammer_ip_next: del-on-disk with no b-tree entry iprec %p flags %08x", cursor->iprec, cursor->iprec->flags);
1523 case HAMMER_CURSOR_ATEMEM:
1525 * Only the disk entry is valid
1527 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1528 cursor->flags |= HAMMER_CURSOR_ATEDISK;
1532 * Neither entry is valid
1534 * XXX error not set properly
1536 cursor->leaf = NULL;
1544 * Resolve the cursor->data pointer for the current cursor position in
1545 * a merged iteration.
1548 hammer_ip_resolve_data(hammer_cursor_t cursor)
1550 hammer_record_t record;
1553 if (hammer_cursor_inmem(cursor)) {
1555 * The data associated with an in-memory record is usually
1556 * kmalloced, but reserve-ahead data records will have an
1557 * on-disk reference.
1559 * NOTE: Reserve-ahead data records must be handled in the
1560 * context of the related high level buffer cache buffer
1561 * to interlock against async writes.
1563 record = cursor->iprec;
1564 cursor->data = record->data;
1566 if (cursor->data == NULL) {
1567 KKASSERT(record->leaf.base.rec_type ==
1568 HAMMER_RECTYPE_DATA);
1569 cursor->data = hammer_bread_ext(cursor->trans->hmp,
1570 record->leaf.data_offset,
1571 record->leaf.data_len,
1573 &cursor->data_buffer);
1576 cursor->leaf = &cursor->node->ondisk->elms[cursor->index].leaf;
1577 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA);
1583 * Backend truncation / record replacement - delete records in range.
1585 * Delete all records within the specified range for inode ip. In-memory
1586 * records still associated with the frontend are ignored.
1588 * If truncating is non-zero in-memory records associated with the back-end
1589 * are ignored. If truncating is > 1 we can return EWOULDBLOCK.
1593 * * An unaligned range will cause new records to be added to cover
1594 * the edge cases. (XXX not implemented yet).
1596 * * Replacement via reservations (see hammer_ip_sync_record_cursor())
1597 * also do not deal with unaligned ranges.
1599 * * ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
1601 * * Record keys for regular file data have to be special-cased since
1602 * they indicate the end of the range (key = base + bytes).
1604 * * This function may be asked to delete ridiculously huge ranges, for
1605 * example if someone truncates or removes a 1TB regular file. We
1606 * must be very careful on restarts and we may have to stop w/
1607 * EWOULDBLOCK to avoid blowing out the buffer cache.
1610 hammer_ip_delete_range(hammer_cursor_t cursor, hammer_inode_t ip,
1611 int64_t ran_beg, int64_t ran_end, int truncating)
1613 hammer_transaction_t trans = cursor->trans;
1614 hammer_btree_leaf_elm_t leaf;
1620 kprintf("delete_range %p %016llx-%016llx\n", ip, ran_beg, ran_end);
1623 KKASSERT(trans->type == HAMMER_TRANS_FLS);
1625 hammer_normalize_cursor(cursor);
1626 cursor->key_beg.localization = ip->obj_localization +
1627 HAMMER_LOCALIZE_MISC;
1628 cursor->key_beg.obj_id = ip->obj_id;
1629 cursor->key_beg.create_tid = 0;
1630 cursor->key_beg.delete_tid = 0;
1631 cursor->key_beg.obj_type = 0;
1633 if (ip->ino_data.obj_type == HAMMER_OBJTYPE_DBFILE) {
1634 cursor->key_beg.key = ran_beg;
1635 cursor->key_beg.rec_type = HAMMER_RECTYPE_DB;
1638 * The key in the B-Tree is (base+bytes), so the first possible
1639 * matching key is ran_beg + 1.
1641 cursor->key_beg.key = ran_beg + 1;
1642 cursor->key_beg.rec_type = HAMMER_RECTYPE_DATA;
1645 cursor->key_end = cursor->key_beg;
1646 if (ip->ino_data.obj_type == HAMMER_OBJTYPE_DBFILE) {
1647 cursor->key_end.key = ran_end;
1649 tmp64 = ran_end + MAXPHYS + 1; /* work around GCC-4 bug */
1650 if (tmp64 < ran_end)
1651 cursor->key_end.key = 0x7FFFFFFFFFFFFFFFLL;
1653 cursor->key_end.key = ran_end + MAXPHYS + 1;
1656 cursor->asof = ip->obj_asof;
1657 cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1658 cursor->flags |= HAMMER_CURSOR_ASOF;
1659 cursor->flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
1660 cursor->flags |= HAMMER_CURSOR_BACKEND;
1661 cursor->flags |= HAMMER_CURSOR_END_INCLUSIVE;
1663 error = hammer_ip_first(cursor);
1666 * Iterate through matching records and mark them as deleted.
1668 while (error == 0) {
1669 leaf = cursor->leaf;
1671 KKASSERT(leaf->base.delete_tid == 0);
1672 KKASSERT(leaf->base.obj_id == ip->obj_id);
1675 * There may be overlap cases for regular file data. Also
1676 * remember the key for a regular file record is (base + len),
1679 * Note that do to duplicates (mem & media) allowed by
1680 * DELETE_VISIBILITY, off can wind up less then ran_beg.
1682 if (leaf->base.rec_type == HAMMER_RECTYPE_DATA) {
1683 off = leaf->base.key - leaf->data_len;
1685 * Check the left edge case. We currently do not
1686 * split existing records.
1688 if (off < ran_beg && leaf->base.key > ran_beg) {
1689 panic("hammer left edge case %016llx %d\n",
1690 leaf->base.key, leaf->data_len);
1694 * Check the right edge case. Note that the
1695 * record can be completely out of bounds, which
1696 * terminates the search.
1698 * base->key is exclusive of the right edge while
1699 * ran_end is inclusive of the right edge. The
1700 * (key - data_len) left boundary is inclusive.
1702 * XXX theory-check this test at some point, are
1703 * we missing a + 1 somewhere? Note that ran_end
1706 if (leaf->base.key - 1 > ran_end) {
1707 if (leaf->base.key - leaf->data_len > ran_end)
1709 panic("hammer right edge case\n");
1712 off = leaf->base.key;
1716 * Delete the record. When truncating we do not delete
1717 * in-memory (data) records because they represent data
1718 * written after the truncation.
1720 * This will also physically destroy the B-Tree entry and
1721 * data if the retention policy dictates. The function
1722 * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1723 * uses to perform a fixup.
1725 if (truncating == 0 || hammer_cursor_ondisk(cursor)) {
1726 error = hammer_ip_delete_record(cursor, ip, trans->tid);
1728 * If we have built up too many meta-buffers we risk
1729 * deadlocking the kernel and must stop. This can
1730 * occur when deleting ridiculously huge files.
1731 * sync_trunc_off is updated so the next cycle does
1732 * not re-iterate records we have already deleted.
1734 * This is only done with formal truncations.
1736 if (truncating > 1 && error == 0 &&
1737 hammer_flusher_meta_limit(ip->hmp)) {
1738 ip->sync_trunc_off = off;
1739 error = EWOULDBLOCK;
1744 ran_beg = off; /* for restart */
1745 error = hammer_ip_next(cursor);
1748 hammer_cache_node(&ip->cache[1], cursor->node);
1750 if (error == EDEADLK) {
1751 hammer_done_cursor(cursor);
1752 error = hammer_init_cursor(trans, cursor, &ip->cache[1], ip);
1756 if (error == ENOENT)
1762 * This backend function deletes the specified record on-disk, similar to
1763 * delete_range but for a specific record. Unlike the exact deletions
1764 * used when deleting a directory entry this function uses an ASOF search
1765 * like delete_range.
1767 * This function may be called with ip->obj_asof set for a slave snapshot,
1768 * so don't use it. We always delete non-historical records only.
1771 hammer_delete_general(hammer_cursor_t cursor, hammer_inode_t ip,
1772 hammer_btree_leaf_elm_t leaf)
1774 hammer_transaction_t trans = cursor->trans;
1777 KKASSERT(trans->type == HAMMER_TRANS_FLS);
1779 hammer_normalize_cursor(cursor);
1780 cursor->key_beg = leaf->base;
1781 cursor->asof = HAMMER_MAX_TID;
1782 cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1783 cursor->flags |= HAMMER_CURSOR_ASOF;
1784 cursor->flags |= HAMMER_CURSOR_BACKEND;
1785 cursor->flags &= ~HAMMER_CURSOR_INSERT;
1787 error = hammer_btree_lookup(cursor);
1789 error = hammer_ip_delete_record(cursor, ip, trans->tid);
1791 if (error == EDEADLK) {
1792 hammer_done_cursor(cursor);
1793 error = hammer_init_cursor(trans, cursor, &ip->cache[1], ip);
1801 * This function deletes remaining auxillary records when an inode is
1802 * being deleted. This function explicitly does not delete the
1803 * inode record, directory entry, data, or db records. Those must be
1804 * properly disposed of prior to this call.
1807 hammer_ip_delete_clean(hammer_cursor_t cursor, hammer_inode_t ip, int *countp)
1809 hammer_transaction_t trans = cursor->trans;
1810 hammer_btree_leaf_elm_t leaf;
1813 KKASSERT(trans->type == HAMMER_TRANS_FLS);
1815 hammer_normalize_cursor(cursor);
1816 cursor->key_beg.localization = ip->obj_localization +
1817 HAMMER_LOCALIZE_MISC;
1818 cursor->key_beg.obj_id = ip->obj_id;
1819 cursor->key_beg.create_tid = 0;
1820 cursor->key_beg.delete_tid = 0;
1821 cursor->key_beg.obj_type = 0;
1822 cursor->key_beg.rec_type = HAMMER_RECTYPE_CLEAN_START;
1823 cursor->key_beg.key = HAMMER_MIN_KEY;
1825 cursor->key_end = cursor->key_beg;
1826 cursor->key_end.rec_type = HAMMER_RECTYPE_MAX;
1827 cursor->key_end.key = HAMMER_MAX_KEY;
1829 cursor->asof = ip->obj_asof;
1830 cursor->flags &= ~HAMMER_CURSOR_INITMASK;
1831 cursor->flags |= HAMMER_CURSOR_END_INCLUSIVE | HAMMER_CURSOR_ASOF;
1832 cursor->flags |= HAMMER_CURSOR_DELETE_VISIBILITY;
1833 cursor->flags |= HAMMER_CURSOR_BACKEND;
1835 error = hammer_ip_first(cursor);
1838 * Iterate through matching records and mark them as deleted.
1840 while (error == 0) {
1841 leaf = cursor->leaf;
1843 KKASSERT(leaf->base.delete_tid == 0);
1846 * Mark the record and B-Tree entry as deleted. This will
1847 * also physically delete the B-Tree entry, record, and
1848 * data if the retention policy dictates. The function
1849 * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1850 * uses to perform a fixup.
1852 * Directory entries (and delete-on-disk directory entries)
1853 * must be synced and cannot be deleted.
1855 error = hammer_ip_delete_record(cursor, ip, trans->tid);
1859 error = hammer_ip_next(cursor);
1862 hammer_cache_node(&ip->cache[1], cursor->node);
1863 if (error == EDEADLK) {
1864 hammer_done_cursor(cursor);
1865 error = hammer_init_cursor(trans, cursor, &ip->cache[1], ip);
1869 if (error == ENOENT)
1875 * Delete the record at the current cursor. On success the cursor will
1876 * be positioned appropriately for an iteration but may no longer be at
1879 * This routine is only called from the backend.
1881 * NOTE: This can return EDEADLK, requiring the caller to terminate the
1885 hammer_ip_delete_record(hammer_cursor_t cursor, hammer_inode_t ip,
1888 hammer_off_t zone2_offset;
1889 hammer_record_t iprec;
1890 hammer_btree_elm_t elm;
1894 KKASSERT(cursor->flags & HAMMER_CURSOR_BACKEND);
1896 hmp = cursor->node->hmp;
1899 * In-memory (unsynchronized) records can simply be freed. This
1900 * only occurs in range iterations since all other records are
1901 * individually synchronized. Thus there should be no confusion with
1904 * An in-memory record may be deleted before being committed to disk,
1905 * but could have been accessed in the mean time. The backing store
1906 * may never been marked allocated and so hammer_blockmap_free() may
1907 * never get called on it. Because of this we have to make sure that
1908 * we've gotten rid of any related hammer_buffer or buffer cache
1911 if (hammer_cursor_inmem(cursor)) {
1912 iprec = cursor->iprec;
1913 KKASSERT((iprec->flags & HAMMER_RECF_INTERLOCK_BE) ==0);
1914 iprec->flags |= HAMMER_RECF_DELETED_FE;
1915 iprec->flags |= HAMMER_RECF_DELETED_BE;
1917 if (iprec->leaf.data_offset && iprec->leaf.data_len) {
1918 zone2_offset = hammer_blockmap_lookup(hmp, iprec->leaf.data_offset, &error);
1919 KKASSERT(error == 0);
1920 hammer_del_buffers(hmp,
1921 iprec->leaf.data_offset,
1923 iprec->leaf.data_len);
1929 * On-disk records are marked as deleted by updating their delete_tid.
1930 * This does not effect their position in the B-Tree (which is based
1931 * on their create_tid).
1933 * Frontend B-Tree operations track inodes so we tell
1934 * hammer_delete_at_cursor() not to.
1936 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_LEAF);
1940 error = hammer_delete_at_cursor(
1942 HAMMER_DELETE_ADJUST | hammer_nohistory(ip),
1944 cursor->trans->time32,
1951 * Delete the B-Tree element at the current cursor and do any necessary
1952 * mirror propagation.
1954 * The cursor must be properly positioned for an iteration on return but
1955 * may be pointing at an internal element.
1957 * An element can be un-deleted by passing a delete_tid of 0 with
1958 * HAMMER_DELETE_ADJUST.
1961 hammer_delete_at_cursor(hammer_cursor_t cursor, int delete_flags,
1962 hammer_tid_t delete_tid, u_int32_t delete_ts,
1963 int track, int64_t *stat_bytes)
1965 struct hammer_btree_leaf_elm save_leaf;
1966 hammer_transaction_t trans;
1967 hammer_btree_leaf_elm_t leaf;
1969 hammer_btree_elm_t elm;
1970 hammer_off_t data_offset;
1977 error = hammer_cursor_upgrade(cursor);
1981 trans = cursor->trans;
1982 node = cursor->node;
1983 elm = &node->ondisk->elms[cursor->index];
1985 KKASSERT(elm->base.btype == HAMMER_BTREE_TYPE_RECORD);
1987 hammer_sync_lock_sh(trans);
1992 * Adjust the delete_tid. Update the mirror_tid propagation field
1993 * as well. delete_tid can be 0 (undelete -- used by mirroring).
1995 if (delete_flags & HAMMER_DELETE_ADJUST) {
1996 if (elm->base.rec_type == HAMMER_RECTYPE_INODE) {
1997 if (elm->leaf.base.delete_tid == 0 && delete_tid)
1999 if (elm->leaf.base.delete_tid && delete_tid == 0)
2003 hammer_modify_node(trans, node, elm, sizeof(*elm));
2004 elm->leaf.base.delete_tid = delete_tid;
2005 elm->leaf.delete_ts = delete_ts;
2006 hammer_modify_node_done(node);
2008 if (elm->leaf.base.delete_tid > node->ondisk->mirror_tid) {
2009 hammer_modify_node_field(trans, node, mirror_tid);
2010 node->ondisk->mirror_tid = elm->leaf.base.delete_tid;
2011 hammer_modify_node_done(node);
2013 if (hammer_debug_general & 0x0002) {
2014 kprintf("delete_at_cursor: propagate %016llx"
2016 elm->leaf.base.delete_tid,
2022 * Adjust for the iteration. We have deleted the current
2023 * element and want to clear ATEDISK so the iteration does
2024 * not skip the element after, which now becomes the current
2027 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
2028 cursor->flags |= HAMMER_CURSOR_DELBTREE;
2029 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
2033 * An on-disk record cannot have the same delete_tid
2034 * as its create_tid. In a chain of record updates
2035 * this could result in a duplicate record.
2037 KKASSERT(elm->leaf.base.delete_tid !=
2038 elm->leaf.base.create_tid);
2042 * Destroy the B-Tree element if asked (typically if a nohistory
2043 * file or mount, or when called by the pruning code).
2045 * Adjust the ATEDISK flag to properly support iterations.
2047 if (delete_flags & HAMMER_DELETE_DESTROY) {
2048 data_offset = elm->leaf.data_offset;
2049 data_len = elm->leaf.data_len;
2050 rec_type = elm->leaf.base.rec_type;
2052 save_leaf = elm->leaf;
2055 if (elm->base.rec_type == HAMMER_RECTYPE_INODE &&
2056 elm->leaf.base.delete_tid == 0) {
2060 error = hammer_btree_delete(cursor);
2063 * This forces a fixup for the iteration because
2064 * the cursor is now either sitting at the 'next'
2065 * element or sitting at the end of a leaf.
2067 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
2068 cursor->flags |= HAMMER_CURSOR_DELBTREE;
2069 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
2073 switch(data_offset & HAMMER_OFF_ZONE_MASK) {
2074 case HAMMER_ZONE_LARGE_DATA:
2075 case HAMMER_ZONE_SMALL_DATA:
2076 case HAMMER_ZONE_META:
2077 hammer_blockmap_free(trans,
2078 data_offset, data_len);
2087 * Track inode count and next_tid. This is used by the mirroring
2088 * and PFS code. icount can be negative, zero, or positive.
2090 if (error == 0 && track) {
2092 hammer_modify_volume_field(trans, trans->rootvol,
2094 trans->rootvol->ondisk->vol0_stat_inodes += icount;
2095 hammer_modify_volume_done(trans->rootvol);
2097 if (trans->rootvol->ondisk->vol0_next_tid < delete_tid) {
2098 hammer_modify_volume(trans, trans->rootvol, NULL, 0);
2099 trans->rootvol->ondisk->vol0_next_tid = delete_tid;
2100 hammer_modify_volume_done(trans->rootvol);
2105 * mirror_tid propagation occurs if the node's mirror_tid had to be
2106 * updated while adjusting the delete_tid.
2108 * This occurs when deleting even in nohistory mode, but does not
2109 * occur when pruning an already-deleted node.
2111 * cursor->ip is NULL when called from the pruning, mirroring,
2112 * and pfs code. If non-NULL propagation will be conditionalized
2113 * on whether the PFS is in no-history mode or not.
2117 hammer_btree_do_propagation(cursor, cursor->ip->pfsm, leaf);
2119 hammer_btree_do_propagation(cursor, NULL, leaf);
2121 hammer_sync_unlock(trans);
2126 * Determine whether we can remove a directory. This routine checks whether
2127 * a directory is empty or not and enforces flush connectivity.
2129 * Flush connectivity requires that we block if the target directory is
2130 * currently flushing, otherwise it may not end up in the same flush group.
2132 * Returns 0 on success, ENOTEMPTY or EDEADLK (or other errors) on failure.
2135 hammer_ip_check_directory_empty(hammer_transaction_t trans, hammer_inode_t ip)
2137 struct hammer_cursor cursor;
2141 * Check directory empty
2143 hammer_init_cursor(trans, &cursor, &ip->cache[1], ip);
2145 cursor.key_beg.localization = ip->obj_localization +
2146 HAMMER_LOCALIZE_MISC;
2147 cursor.key_beg.obj_id = ip->obj_id;
2148 cursor.key_beg.create_tid = 0;
2149 cursor.key_beg.delete_tid = 0;
2150 cursor.key_beg.obj_type = 0;
2151 cursor.key_beg.rec_type = HAMMER_RECTYPE_INODE + 1;
2152 cursor.key_beg.key = HAMMER_MIN_KEY;
2154 cursor.key_end = cursor.key_beg;
2155 cursor.key_end.rec_type = 0xFFFF;
2156 cursor.key_end.key = HAMMER_MAX_KEY;
2158 cursor.asof = ip->obj_asof;
2159 cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE | HAMMER_CURSOR_ASOF;
2161 error = hammer_ip_first(&cursor);
2162 if (error == ENOENT)
2164 else if (error == 0)
2166 hammer_done_cursor(&cursor);