| blob | b54b6bb04b066b3b1f5e1422abf02fb6f005cfe1 |
1 /*
2 * Copyright (c) 2007-2008 The DragonFly Project. All rights reserved.
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
34 * $DragonFly: src/sys/vfs/hammer/hammer_object.c,v 1.97 2008/09/23 22:28:56 dillon Exp $
35 */
46 hammer_btree_leaf_elm_t leaf);
49 u_int16_t rec_type;
51 };
54 hammer_record_t record;
56 };
58 /*
59 * Red-black tree support. Comparison code for insertion.
60 */
61 static int
63 {
74 /*
75 * For search & insertion purposes records deleted by the
76 * frontend or deleted/committed by the backend are silently
77 * ignored. Otherwise pipelined insertions will get messed
78 * up.
79 *
80 * rec1 is greater then rec2 if rec1 is marked deleted.
81 * rec1 is less then rec2 if rec2 is marked deleted.
82 *
83 * Multiple deleted records may be present, do not return 0
84 * if both are marked deleted.
85 */
87 HAMMER_RECF_COMMITTED)) {
89 }
91 HAMMER_RECF_COMMITTED)) {
93 }
96 }
98 /*
99 * Basic record comparison code similar to hammer_btree_cmp().
100 */
101 static int
103 {
114 /*
115 * Never match against an item deleted by the frontend
116 * or backend, or committed by the backend.
117 *
118 * elm is less then rec if rec is marked deleted.
119 */
121 HAMMER_RECF_COMMITTED)) {
123 }
125 }
127 /*
128 * Ranged scan to locate overlapping record(s). This is used by
129 * hammer_ip_get_bulk() to locate an overlapping record. We have
130 * to use a ranged scan because the keys for data records with the
131 * same file base offset can be different due to differing data_len's.
132 *
133 * NOTE: The base file offset of a data record is (key - data_len), not (key).
134 */
135 static int
137 {
146 /*
147 * Overlap compare
148 */
150 /* rec_beg >= leaf_end */
153 /* rec_end <= leaf_beg */
161 }
163 /*
164 * We have to return 0 at this point, even if DELETED_FE is set,
165 * because returning anything else will cause the scan to ignore
166 * one of the branches when we really want it to check both.
167 */
169 }
171 /*
172 * RB_SCAN comparison code for hammer_mem_first(). The argument order
173 * is reversed so the comparison result has to be negated. key_beg and
174 * key_end are both range-inclusive.
175 *
176 * Localized deletions are not cached in-memory.
177 */
178 static
179 int
181 {
192 }
194 /*
195 * This compare function is used when simply looking up key_beg.
196 */
197 static
198 int
200 {
210 }
212 /*
213 * Locate blocks within the truncation range. Partial blocks do not count.
214 */
215 static
216 int
218 {
228 /*
229 * DB record key is not beyond the truncation point, retain.
230 */
235 /*
236 * DATA record offset start is not beyond the truncation point,
237 * retain.
238 */
244 }
246 /*
247 * The record start is >= the truncation point, return match,
248 * the record should be destroyed.
249 */
251 }
255 /*
256 * Allocate a record for the caller to finish filling in. The record is
257 * returned referenced.
258 */
259 hammer_record_t
261 {
262 hammer_record_t record;
263 hammer_mount_t hmp;
279 }
282 }
284 void
286 {
290 }
291 }
293 /*
294 * Called from the backend, hammer_inode.c, after a record has been
295 * flushed to disk. The record has been exclusively locked by the
296 * caller and interlocked with BE.
297 *
298 * We clean up the state, unlock, and release the record (the record
299 * was referenced by the fact that it was in the HAMMER_FST_FLUSH state).
300 */
301 void
303 {
304 hammer_inode_t target_ip;
309 /*
310 * If an error occured, the backend was unable to sync the
311 * record to its media. Leave the record intact.
312 */
316 }
321 /*
322 * Adjust the flush state and dependancy based on success or
323 * failure.
324 */
328 target_entry);
331 }
340 }
341 }
344 /*
345 * Cleanup
346 */
350 }
352 }
354 /*
355 * Release a memory record. Records marked for deletion are immediately
356 * removed from the RB-Tree but otherwise left intact until the last ref
357 * goes away.
358 */
359 void
361 {
362 hammer_mount_t hmp;
363 hammer_reserve_t resv;
364 hammer_inode_t ip;
365 hammer_inode_t target_ip;
371 /*
372 * Upon release of the last reference wakeup any waiters.
373 * The record structure may get destroyed so callers will
374 * loop up and do a relookup.
375 *
376 * WARNING! Record must be removed from RB-TREE before we
377 * might possibly block. hammer_test_inode() can block!
378 */
382 /*
383 * Upon release of the last reference a record marked deleted
384 * by the front or backend, or committed by the backend,
385 * is destroyed.
386 */
388 HAMMER_RECF_DELETED_BE |
389 HAMMER_RECF_COMMITTED)) {
393 /*
394 * target_ip may have zero refs, we have to ref it
395 * to prevent it from being ripped out from under
396 * us.
397 */
403 }
405 /*
406 * Remove the record from the B-Tree
407 */
411 record);
417 }
419 /*
420 * We must wait for any direct-IO to complete before
421 * we can destroy the record because the bio may
422 * have a reference to it.
423 */
427 }
429 /*
430 * Account for the completion after the direct IO
431 * has completed.
432 */
442 }
445 }
447 /*
448 * Do this test after removing record from the B-Tree.
449 */
453 }
459 }
461 /*
462 * Release the reservation.
463 *
464 * If the record was not committed we can theoretically
465 * undo the reservation. However, doing so might
466 * create weird edge cases with the ordering of
467 * direct writes because the related buffer cache
468 * elements are per-vnode. So we don't try.
469 */
471 /* XXX undo leaf.data_offset,leaf.data_len */
474 }
478 }
479 }
480 }
482 /*
483 * Record visibility depends on whether the record is being accessed by
484 * the backend or the frontend. Backend tests ignore the frontend delete
485 * flag. Frontend tests do NOT ignore the backend delete/commit flags and
486 * must also check for commit races.
487 *
488 * Return non-zero if the record is visible, zero if it isn't or if it is
489 * deleted. Returns 0 if the record has been comitted (unless the special
490 * delete-visibility flag is set). A committed record must be located
491 * via the media B-Tree. Returns non-zero if the record is good.
492 *
493 * If HAMMER_CURSOR_DELETE_VISIBILITY is set we allow deleted memory
494 * records to be returned. This is so pending deletions are detected
495 * when using an iterator to locate an unused hash key, or when we need
496 * to locate historical records on-disk to destroy.
497 */
498 static __inline
499 int
501 {
506 HAMMER_RECF_COMMITTED)) {
508 }
511 HAMMER_RECF_DELETED_BE |
512 HAMMER_RECF_COMMITTED)) {
514 }
515 }
517 }
519 /*
520 * This callback is used as part of the RB_SCAN function for in-memory
521 * records. We terminate it (return -1) as soon as we get a match.
522 *
523 * This routine is used by frontend code.
524 *
525 * The primary compare code does not account for ASOF lookups. This
526 * code handles that case as well as a few others.
527 */
528 static
529 int
531 {
534 /*
535 * We terminate on success, so this should be NULL on entry.
536 */
539 /*
540 * Skip if the record was marked deleted or committed.
541 */
545 /*
546 * Skip if not visible due to our as-of TID
547 */
554 }
555 }
557 /*
558 * ref the record. The record is protected from backend B-Tree
559 * interactions by virtue of the cursor's IP lock.
560 */
563 /*
564 * The record may have been deleted or committed while we
565 * were blocked. XXX remove?
566 */
570 }
572 /*
573 * Set the matching record and stop the scan.
574 */
577 }
580 /*
581 * Lookup an in-memory record given the key specified in the cursor. Works
582 * just like hammer_btree_lookup() but operates on an inode's in-memory
583 * record list.
584 *
585 * The lookup must fail if the record is marked for deferred deletion.
586 *
587 * The API for mem/btree_lookup() does not mess with the ATE/EOF bits.
588 */
589 static
590 int
592 {
597 }
602 }
604 /*
605 * hammer_mem_first() - locate the first in-memory record matching the
606 * cursor within the bounds of the key range.
607 *
608 * WARNING! API is slightly different from btree_first(). hammer_mem_first()
609 * will set ATEMEM the same as MEMEOF, and does not return any error.
610 */
611 static
612 void
614 {
615 hammer_inode_t ip;
623 }
629 else
631 }
633 /************************************************************************
634 * HAMMER IN-MEMORY RECORD FUNCTIONS *
635 ************************************************************************
636 *
637 * These functions manipulate in-memory records. Such records typically
638 * exist prior to being committed to disk or indexed via the on-disk B-Tree.
639 */
641 /*
642 * Add a directory entry (dip,ncp) which references inode (ip).
643 *
644 * Note that the low 32 bits of the namekey are set temporarily to create
645 * a unique in-memory record, and may be modified a second time when the
646 * record is synchronized to disk. In particular, the low 32 bits cannot be
647 * all 0's when synching to disk, which is not handled here.
648 *
649 * NOTE: bytes does not include any terminating \0 on name, and name might
650 * not be terminated.
651 */
652 int
656 {
658 hammer_record_t record;
660 u_int32_t max_iterations;
680 /*
681 * Find an unused namekey. Both the in-memory record tree and
682 * the B-Tree are checked. We do not want historically deleted
683 * names to create a collision as our iteration space may be limited,
684 * and since create_tid wouldn't match anyway an ASOF search
685 * must be used to locate collisions.
686 *
687 * delete-visibility is set so pending deletions do not give us
688 * a false-negative on our ability to use an iterator.
689 *
690 * The iterator must not rollover the key. Directory keys only
691 * use the positive key space.
692 */
707 }
708 }
710 /*
711 * The target inode and the directory entry are bound together.
712 */
717 /*
718 * The inode now has a dependancy and must be taken out of the idle
719 * state. An inode not in an idle state is given an extra reference.
720 *
721 * When transitioning to a SETUP state flag for an automatic reflush
722 * when the dependancies are disposed of if someone is waiting on
723 * the inode.
724 */
730 }
735 }
736 failed:
739 }
741 /*
742 * Delete the directory entry and update the inode link count. The
743 * cursor must be seeked to the directory entry record being deleted.
744 *
745 * The related inode should be share-locked by the caller. The caller is
746 * on the frontend. It could also be NULL indicating that the directory
747 * entry being removed has no related inode.
748 *
749 * This function can return EDEADLK requiring the caller to terminate
750 * the cursor, any locks, wait on the returned record, and retry.
751 */
752 int
756 {
757 hammer_record_t record;
761 /*
762 * In-memory (unsynchronized) records can simply be freed.
763 *
764 * Even though the HAMMER_RECF_DELETED_FE flag is ignored
765 * by the backend, we must still avoid races against the
766 * backend potentially syncing the record to the media.
767 *
768 * We cannot call hammer_ip_delete_record(), that routine may
769 * only be called from the backend.
770 */
773 HAMMER_RECF_DELETED_BE |
774 HAMMER_RECF_COMMITTED)) {
783 }
785 /*
786 * If the record is on-disk we have to queue the deletion by
787 * the record's key. This also causes lookups to skip the
788 * record.
789 */
796 /*
797 * ip may be NULL, indicating the deletion of a directory
798 * entry which has no related inode.
799 */
804 target_entry);
807 }
809 /*
810 * The inode now has a dependancy and must be taken out of
811 * the idle state. An inode not in an idle state is given
812 * an extra reference.
813 *
814 * When transitioning to a SETUP state flag for an automatic
815 * reflush when the dependancies are disposed of if someone
816 * is waiting on the inode.
817 */
823 }
826 }
828 /*
829 * One less link. The file may still be open in the OS even after
830 * all links have gone away.
831 *
832 * We have to terminate the cursor before syncing the inode to
833 * avoid deadlocking against ourselves. XXX this may no longer
834 * be true.
835 *
836 * If nlinks drops to zero and the vnode is inactive (or there is
837 * no vnode), call hammer_inode_unloadable_check() to zonk the
838 * inode. If we don't do this here the inode will not be destroyed
839 * on-media until we unmount.
840 */
845 }
855 }
856 }
858 }
860 }
862 /*
863 * Add a record to an inode.
864 *
865 * The caller must allocate the record with hammer_alloc_mem_record(ip) and
866 * initialize the following additional fields:
867 *
868 * The related inode should be share-locked by the caller. The caller is
869 * on the frontend.
870 *
871 * record->rec.entry.base.base.key
872 * record->rec.entry.base.base.rec_type
873 * record->rec.entry.base.base.data_len
874 * record->data (a copy will be kmalloc'd if it cannot be embedded)
875 */
876 int
878 {
887 }
889 /*
890 * Locate a bulk record in-memory. Bulk records allow disk space to be
891 * reserved so the front-end can flush large data writes without having
892 * to queue the BIO to the flusher. Only the related record gets queued
893 * to the flusher.
894 */
896 static hammer_record_t
898 {
910 HAMMER_LOCALIZE_MISC;
917 }
919 /*
920 * Take records vetted by overlap_cmp. The first non-deleted record
921 * (if any) stops the scan.
922 */
923 static int
925 {
929 HAMMER_RECF_COMMITTED)) {
931 }
935 }
937 /*
938 * Reserve blockmap space placemarked with an in-memory record.
939 *
940 * This routine is called by the frontend in order to be able to directly
941 * flush a buffer cache buffer. The frontend has locked the related buffer
942 * cache buffers and we should be able to manipulate any overlapping
943 * in-memory records.
944 *
945 * The caller is responsible for adding the returned record.
946 */
947 hammer_record_t
950 {
951 hammer_record_t record;
952 hammer_record_t conflict;
955 /*
956 * Deal with conflicting in-memory records. We cannot have multiple
957 * in-memory records for the same base offset without seriously
958 * confusing the backend, including but not limited to the backend
959 * issuing delete-create-delete or create-delete-create sequences
960 * and asserting on the delete_tid being the same as the create_tid.
961 *
962 * If we encounter a record with the backend interlock set we cannot
963 * immediately delete it without confusing the backend.
964 */
971 }
973 }
975 /*
976 * Create a record to cover the direct write. This is called with
977 * the related BIO locked so there should be no possible conflict.
978 *
979 * The backend is responsible for finalizing the space reserved in
980 * this record.
981 *
982 * XXX bytes not aligned, depend on the reservation code to
983 * align the reservation.
984 */
987 HAMMER_ZONE_SMALL_DATA_INDEX;
990 errorp);
995 }
1002 HAMMER_LOCALIZE_MISC;
1007 }
1009 /*
1010 * Frontend truncation code. Scan in-memory records only. On-disk records
1011 * and records in a flushing state are handled by the backend. The vnops
1012 * setattr code will handle the block containing the truncation point.
1013 *
1014 * Partial blocks are not deleted.
1015 */
1016 int
1018 {
1030 }
1035 }
1037 static int
1039 {
1049 }
1051 /*
1052 * Return 1 if the caller must check for and delete existing records
1053 * before writing out a new data record.
1054 *
1055 * Return 0 if the caller can just insert the record into the B-Tree without
1056 * checking.
1057 */
1058 static int
1060 {
1067 else
1076 }
1078 }
1080 /*
1081 * Backend code. Sync a record to the media.
1082 */
1083 int
1085 {
1097 /*
1098 * Any direct-write related to the record must complete before we
1099 * can sync the record to the on-disk media.
1100 */
1104 /*
1105 * If this is a bulk-data record placemarker there may be an existing
1106 * record on-disk, indicating a data overwrite. If there is the
1107 * on-disk record must be deleted before we can insert our new record.
1108 *
1109 * We've synthesized this record and do not know what the create_tid
1110 * on-disk is, nor how much data it represents.
1111 *
1112 * Keep in mind that (key) for data records is (base_offset + len),
1113 * not (base_offset). Also, we only want to get rid of on-disk
1114 * records since we are trying to sync our in-memory record, call
1115 * hammer_ip_delete_range() with truncating set to 1 to make sure
1116 * it skips in-memory records.
1117 *
1118 * It is ok for the lookup to return ENOENT.
1119 *
1120 * NOTE OPTIMIZATION: sync_trunc_off is used to determine if we have
1121 * to call hammer_ip_delete_range() or not. This also means we must
1122 * update sync_trunc_off() as we write.
1123 */
1136 }
1138 /*
1139 * If this is a general record there may be an on-disk version
1140 * that must be deleted before we can insert the new record.
1141 */
1147 }
1149 /*
1150 * Setup the cursor.
1151 */
1158 /*
1159 * Records can wind up on-media before the inode itself is on-media.
1160 * Flag the case.
1161 */
1164 /*
1165 * If we are deleting a directory entry an exact match must be
1166 * found on-disk.
1167 */
1176 HAMMER_RECF_COMMITTED;
1178 }
1179 }
1181 }
1183 /*
1184 * We are inserting.
1185 *
1186 * Issue a lookup to position the cursor and locate the insertion
1187 * point. The target key should not exist. If we are creating a
1188 * directory entry we may have to iterate the low 32 bits of the
1189 * key to find an unused key.
1190 */
1201 }
1202 #if 0
1207 #endif
1212 /*
1213 * Allocate the record and data. The result buffers will be
1214 * marked as being modified and further calls to
1215 * hammer_modify_buffer() will result in unneeded UNDO records.
1216 *
1217 * Support zero-fill records (data == NULL and data_len != 0)
1218 */
1220 /*
1221 * The data portion of a bulk-data record has already been
1222 * committed to disk, we need only adjust the layer2
1223 * statistics in the same transaction as our B-Tree insert.
1224 */
1231 /*
1232 * Wholely cached record, with data. Allocate the data.
1233 */
1246 /*
1247 * Wholely cached record, without data.
1248 */
1251 }
1256 error,
1260 }
1262 /*
1263 * Our record is on-disk and we normally mark the in-memory version
1264 * as having been committed (and not BE-deleted).
1265 *
1266 * If the record represented a directory deletion but we had to
1267 * sync a valid directory entry to disk due to dependancies,
1268 * we must convert the record to a covering delete so the
1269 * frontend does not have visibility on the synced entry.
1270 */
1276 }
1278 /*
1279 * Must convert deleted directory entry add
1280 * to a directory entry delete.
1281 */
1289 /* converted record is not yet committed */
1290 /* hammer_flush_record_done takes care of the rest */
1292 /*
1293 * Everything went fine and we are now done with
1294 * this record.
1295 */
1298 }
1303 }
1304 }
1305 done_unlock:
1307 done:
1309 }
1311 /*
1312 * Add the record to the inode's rec_tree. The low 32 bits of a directory
1313 * entry's key is used to deal with hash collisions in the upper 32 bits.
1314 * A unique 64 bit key is generated in-memory and may be regenerated a
1315 * second time when the directory record is flushed to the on-disk B-Tree.
1316 *
1317 * A referenced record is passed to this function. This function
1318 * eats the reference. If an error occurs the record will be deleted.
1319 *
1320 * A copy of the temporary record->data pointer provided by the caller
1321 * will be made.
1322 */
1323 int
1325 {
1328 /*
1329 * Make a private copy of record->data
1330 */
1334 /*
1335 * Insert into the RB tree. A unique key should have already
1336 * been selected if this is a directory entry.
1337 */
1342 }
1351 }
1353 /************************************************************************
1354 * HAMMER INODE MERGED-RECORD FUNCTIONS *
1355 ************************************************************************
1356 *
1357 * These functions augment the B-Tree scanning functions in hammer_btree.c
1358 * by merging in-memory records with on-disk records.
1359 */
1361 /*
1362 * Locate a particular record either in-memory or on-disk.
1363 *
1364 * NOTE: This is basically a standalone routine, hammer_ip_next() may
1365 * NOT be called to iterate results.
1366 */
1367 int
1369 {
1372 /*
1373 * If the element is in-memory return it without searching the
1374 * on-disk B-Tree
1375 */
1381 }
1385 /*
1386 * If the inode has on-disk components search the on-disk B-Tree.
1387 */
1394 }
1396 /*
1397 * Helper for hammer_ip_first()/hammer_ip_next()
1398 *
1399 * NOTE: Both ATEDISK and DISKEOF will be set the same. This sets up
1400 * hammer_ip_first() for calling hammer_ip_next(), and sets up the re-seek
1401 * state if hammer_ip_next() needs to re-seek.
1402 */
1403 static __inline
1404 int
1406 {
1418 }
1421 }
1424 HAMMER_CURSOR_ATEDISK);
1427 HAMMER_CURSOR_ATEDISK;
1430 }
1434 }
1436 }
1438 /*
1439 * Helper for hammer_ip_next()
1440 *
1441 * The caller has determined that the media cursor is further along than the
1442 * memory cursor and must be reseeked after a generation number change.
1443 */
1444 static
1445 int
1447 {
1449 hammer_btree_elm_t elm;
1454 /*
1455 * Do the re-seek.
1456 */
1465 /*
1466 * If the memory record was previous returned to
1467 * the caller and the media record matches
1468 * (-1/+1: only create_tid differs), then iterate
1469 * the media record to avoid a double result.
1470 */
1482 }
1489 }
1490 }
1491 }
1493 }
1495 /*
1496 * Locate the first record within the cursor's key_beg/key_end range,
1497 * restricted to a particular inode. 0 is returned on success, ENOENT
1498 * if no records matched the requested range, or some other error.
1499 *
1500 * When 0 is returned hammer_ip_next() may be used to iterate additional
1501 * records within the requested range.
1502 *
1503 * This function can return EDEADLK, requiring the caller to terminate
1504 * the cursor and try again.
1505 */
1507 int
1509 {
1515 /*
1516 * Clean up fields and setup for merged scan
1517 */
1520 /*
1521 * Search the in-memory record list (Red-Black tree). Unlike the
1522 * B-Tree search, mem_first checks for records in the range.
1523 *
1524 * This function will setup both ATEMEM and MEMEOF properly for
1525 * the ip iteration. ATEMEM will be set if MEMEOF is set.
1526 */
1529 /*
1530 * Detect generation changes during blockages, including
1531 * blockages which occur on the initial btree search.
1532 */
1535 /*
1536 * Initial search and result
1537 */
1543 }
1545 /*
1546 * Retrieve the next record in a merged iteration within the bounds of the
1547 * cursor. This call may be made multiple times after the cursor has been
1548 * initially searched with hammer_ip_first().
1549 *
1550 * There are numerous special cases in this code to deal with races between
1551 * in-memory records and on-media records.
1552 *
1553 * 0 is returned on success, ENOENT if no further records match the
1554 * requested range, or some other error code is returned.
1555 */
1556 int
1558 {
1559 hammer_btree_elm_t elm;
1560 hammer_record_t rec;
1561 hammer_record_t tmprec;
1565 again:
1566 /*
1567 * Get the next on-disk record
1568 *
1569 * NOTE: If we deleted the last on-disk record we had scanned
1570 * ATEDISK will be clear and RETEST will be set, forcing
1571 * a call to iterate. The fact that ATEDISK is clear causes
1572 * iterate to re-test the 'current' element. If ATEDISK is
1573 * set, iterate will skip the 'current' element.
1574 */
1578 HAMMER_CURSOR_RETEST)) {
1587 HAMMER_CURSOR_ATEDISK;
1589 }
1590 }
1591 }
1593 /*
1594 * If the generation changed the backend has deleted or committed
1595 * one or more memory records since our last check.
1596 *
1597 * When this case occurs if the disk cursor is > current memory record
1598 * or the disk cursor is at EOF, we must re-seek the disk-cursor.
1599 * Since the cursor is ahead it must have not yet been eaten (if
1600 * not at eof anyway). (XXX data offset case?)
1601 *
1602 * NOTE: we are not doing a full check here. That will be handled
1603 * later on.
1604 *
1605 * If we have exhausted all memory records we do not have to do any
1606 * further seeks.
1607 */
1610 ) {
1611 kprintf("HAMMER: Debug: generation changed during scan @ino=%016llx\n", (long long)cursor->ip->obj_id);
1622 }
1624 /*
1625 * Do we re-seek the media cursor?
1626 */
1630 }
1631 }
1633 /*
1634 * We can now safely get the next in-memory record. We cannot
1635 * block here.
1636 *
1637 * hammer_rec_scan_cmp: Is the record still in our general range,
1638 * (non-inclusive of snapshot exclusions)?
1639 * hammer_rec_scan_callback: Is the record in our snapshot?
1640 */
1643 /*
1644 * If the current memory record was eaten then get the next
1645 * one. Stale records are skipped.
1646 */
1657 }
1663 }
1665 }
1666 }
1668 /*
1669 * MEMORY RECORD VALIDITY TEST
1670 *
1671 * (We still can't block, which is why tmprec is being held so
1672 * long).
1673 *
1674 * If the memory record is no longer valid we skip it. It may
1675 * have been deleted by the frontend. If it was deleted or
1676 * committed by the backend the generation change re-seeked the
1677 * disk cursor and the record will be present there.
1678 */
1687 }
1688 }
1692 /*
1693 * Extract either the disk or memory record depending on their
1694 * relative position.
1695 */
1699 /*
1700 * Both entries valid. Compare the entries and nominally
1701 * return the first one in the sort order. Numerous cases
1702 * require special attention, however.
1703 */
1707 /*
1708 * If the two entries differ only by their key (-2/2) or
1709 * create_tid (-1/1), and are DATA records, we may have a
1710 * nominal match. We have to calculate the base file
1711 * offset of the data.
1712 */
1721 }
1725 HAMMER_CURSOR_GET_LEAF);
1729 }
1731 /*
1732 * If the entries match exactly the memory entry is either
1733 * an on-disk directory entry deletion or a bulk data
1734 * overwrite. If it is a directory entry deletion we eat
1735 * both entries.
1736 *
1737 * For the bulk-data overwrite case it is possible to have
1738 * visibility into both, which simply means the syncer
1739 * hasn't gotten around to doing the delete+insert sequence
1740 * on the B-Tree. Use the memory entry and throw away the
1741 * on-disk entry.
1742 *
1743 * If the in-memory record is not either of these we
1744 * probably caught the syncer while it was syncing it to
1745 * the media. Since we hold a shared lock on the cursor,
1746 * the in-memory record had better be marked deleted at
1747 * this point.
1748 */
1755 }
1759 }
1760 /* fall through to memory entry */
1762 panic("hammer_ip_next: duplicate mem/b-tree entry %p %d %08x", cursor->iprec, cursor->iprec->type, cursor->iprec->flags);
1765 }
1766 }
1767 /* fall through to the memory entry */
1769 /*
1770 * Only the memory entry is valid.
1771 */
1776 /*
1777 * If the memory entry is an on-disk deletion we should have
1778 * also had found a B-Tree record. If the backend beat us
1779 * to it it would have interlocked the cursor and we should
1780 * have seen the in-memory record marked DELETED_FE.
1781 */
1784 panic("hammer_ip_next: del-on-disk with no b-tree entry iprec %p flags %08x", cursor->iprec, cursor->iprec->flags);
1785 }
1788 /*
1789 * Only the disk entry is valid
1790 */
1796 /*
1797 * Neither entry is valid
1798 *
1799 * XXX error not set properly
1800 */
1805 }
1807 }
1809 /*
1810 * Resolve the cursor->data pointer for the current cursor position in
1811 * a merged iteration.
1812 */
1813 int
1815 {
1816 hammer_record_t record;
1820 /*
1821 * The data associated with an in-memory record is usually
1822 * kmalloced, but reserve-ahead data records will have an
1823 * on-disk reference.
1824 *
1825 * NOTE: Reserve-ahead data records must be handled in the
1826 * context of the related high level buffer cache buffer
1827 * to interlock against async writes.
1828 */
1834 HAMMER_RECTYPE_DATA);
1840 }
1844 }
1846 }
1848 /*
1849 * Backend truncation / record replacement - delete records in range.
1850 *
1851 * Delete all records within the specified range for inode ip. In-memory
1852 * records still associated with the frontend are ignored.
1853 *
1854 * If truncating is non-zero in-memory records associated with the back-end
1855 * are ignored. If truncating is > 1 we can return EWOULDBLOCK.
1856 *
1857 * NOTES:
1858 *
1859 * * An unaligned range will cause new records to be added to cover
1860 * the edge cases. (XXX not implemented yet).
1861 *
1862 * * Replacement via reservations (see hammer_ip_sync_record_cursor())
1863 * also do not deal with unaligned ranges.
1864 *
1865 * * ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
1866 *
1867 * * Record keys for regular file data have to be special-cased since
1868 * they indicate the end of the range (key = base + bytes).
1869 *
1870 * * This function may be asked to delete ridiculously huge ranges, for
1871 * example if someone truncates or removes a 1TB regular file. We
1872 * must be very careful on restarts and we may have to stop w/
1873 * EWOULDBLOCK to avoid blowing out the buffer cache.
1874 */
1875 int
1878 {
1880 hammer_btree_leaf_elm_t leaf;
1885 #if 0
1887 #endif
1890 retry:
1893 HAMMER_LOCALIZE_MISC;
1903 /*
1904 * The key in the B-Tree is (base+bytes), so the first possible
1905 * matching key is ran_beg + 1.
1906 */
1909 }
1918 else
1920 }
1931 /*
1932 * Iterate through matching records and mark them as deleted.
1933 */
1940 /*
1941 * There may be overlap cases for regular file data. Also
1942 * remember the key for a regular file record is (base + len),
1943 * NOT (base).
1944 *
1945 * Note that do to duplicates (mem & media) allowed by
1946 * DELETE_VISIBILITY, off can wind up less then ran_beg.
1947 */
1950 /*
1951 * Check the left edge case. We currently do not
1952 * split existing records.
1953 */
1958 }
1960 /*
1961 * Check the right edge case. Note that the
1962 * record can be completely out of bounds, which
1963 * terminates the search.
1964 *
1965 * base->key is exclusive of the right edge while
1966 * ran_end is inclusive of the right edge. The
1967 * (key - data_len) left boundary is inclusive.
1968 *
1969 * XXX theory-check this test at some point, are
1970 * we missing a + 1 somewhere? Note that ran_end
1971 * could overflow.
1972 */
1977 }
1980 }
1982 /*
1983 * Delete the record. When truncating we do not delete
1984 * in-memory (data) records because they represent data
1985 * written after the truncation.
1986 *
1987 * This will also physically destroy the B-Tree entry and
1988 * data if the retention policy dictates. The function
1989 * will set HAMMER_CURSOR_RETEST to cause hammer_ip_next()
1990 * to retest the new 'current' element.
1991 */
1994 /*
1995 * If we have built up too many meta-buffers we risk
1996 * deadlocking the kernel and must stop. This can
1997 * occur when deleting ridiculously huge files.
1998 * sync_trunc_off is updated so the next cycle does
1999 * not re-iterate records we have already deleted.
2000 *
2001 * This is only done with formal truncations.
2002 */
2007 }
2008 }
2013 }
2022 }
2026 }
2028 /*
2029 * This backend function deletes the specified record on-disk, similar to
2030 * delete_range but for a specific record. Unlike the exact deletions
2031 * used when deleting a directory entry this function uses an ASOF search
2032 * like delete_range.
2033 *
2034 * This function may be called with ip->obj_asof set for a slave snapshot,
2035 * so don't use it. We always delete non-historical records only.
2036 */
2037 static int
2039 hammer_btree_leaf_elm_t leaf)
2040 {
2045 retry:
2057 }
2063 }
2065 }
2067 /*
2068 * This function deletes remaining auxillary records when an inode is
2069 * being deleted. This function explicitly does not delete the
2070 * inode record, directory entry, data, or db records. Those must be
2071 * properly disposed of prior to this call.
2072 */
2073 int
2075 {
2077 hammer_btree_leaf_elm_t leaf;
2081 retry:
2084 HAMMER_LOCALIZE_MISC;
2104 /*
2105 * Iterate through matching records and mark them as deleted.
2106 */
2112 /*
2113 * Mark the record and B-Tree entry as deleted. This will
2114 * also physically delete the B-Tree entry, record, and
2115 * data if the retention policy dictates. The function
2116 * will set HAMMER_CURSOR_RETEST to cause hammer_ip_next()
2117 * to retest the new 'current' element.
2118 *
2119 * Directory entries (and delete-on-disk directory entries)
2120 * must be synced and cannot be deleted.
2121 */
2127 }
2135 }
2139 }
2141 /*
2142 * Delete the record at the current cursor. On success the cursor will
2143 * be positioned appropriately for an iteration but may no longer be at
2144 * a leaf node.
2145 *
2146 * This routine is only called from the backend.
2147 *
2148 * NOTE: This can return EDEADLK, requiring the caller to terminate the
2149 * cursor and retry.
2150 */
2151 int
2153 hammer_tid_t tid)
2154 {
2155 hammer_record_t iprec;
2156 hammer_mount_t hmp;
2163 /*
2164 * In-memory (unsynchronized) records can simply be freed. This
2165 * only occurs in range iterations since all other records are
2166 * individually synchronized. Thus there should be no confusion with
2167 * the interlock.
2168 *
2169 * An in-memory record may be deleted before being committed to disk,
2170 * but could have been accessed in the mean time. The reservation
2171 * code will deal with the case.
2172 */
2181 }
2183 /*
2184 * On-disk records are marked as deleted by updating their delete_tid.
2185 * This does not effect their position in the B-Tree (which is based
2186 * on their create_tid).
2187 *
2188 * Frontend B-Tree operations track inodes so we tell
2189 * hammer_delete_at_cursor() not to.
2190 */
2195 cursor,
2200 }
2202 }
2204 /*
2205 * Delete the B-Tree element at the current cursor and do any necessary
2206 * mirror propagation.
2207 *
2208 * The cursor must be properly positioned for an iteration on return but
2209 * may be pointing at an internal element.
2210 *
2211 * An element can be un-deleted by passing a delete_tid of 0 with
2212 * HAMMER_DELETE_ADJUST.
2213 */
2214 int
2218 {
2220 hammer_transaction_t trans;
2221 hammer_btree_leaf_elm_t leaf;
2222 hammer_node_t node;
2223 hammer_btree_elm_t elm;
2224 hammer_off_t data_offset;
2226 u_int16_t rec_type;
2245 /*
2246 * Adjust the delete_tid. Update the mirror_tid propagation field
2247 * as well. delete_tid can be 0 (undelete -- used by mirroring).
2248 */
2255 }
2272 }
2273 }
2275 /*
2276 * Adjust for the iteration. We have deleted the current
2277 * element and want to clear ATEDISK so the iteration does
2278 * not skip the element after, which now becomes the current
2279 * element. This element must be re-tested if doing an
2280 * iteration, which is handled by the RETEST flag.
2281 */
2285 }
2287 /*
2288 * An on-disk record cannot have the same delete_tid
2289 * as its create_tid. In a chain of record updates
2290 * this could result in a duplicate record.
2291 */
2294 }
2296 /*
2297 * Destroy the B-Tree element if asked (typically if a nohistory
2298 * file or mount, or when called by the pruning code).
2299 *
2300 * Adjust the ATEDISK flag to properly support iterations.
2301 */
2309 }
2313 }
2317 /*
2318 * The deletion moves the next element (if any) to
2319 * the current element position. We must clear
2320 * ATEDISK so this element is not skipped and we
2321 * must set RETEST to force any iteration to re-test
2322 * the element.
2323 */
2327 }
2328 }
2339 }
2340 }
2341 }
2343 /*
2344 * Track inode count and next_tid. This is used by the mirroring
2345 * and PFS code. icount can be negative, zero, or positive.
2346 */
2350 vol0_stat_inodes);
2353 }
2358 }
2359 }
2361 /*
2362 * mirror_tid propagation occurs if the node's mirror_tid had to be
2363 * updated while adjusting the delete_tid.
2364 *
2365 * This occurs when deleting even in nohistory mode, but does not
2366 * occur when pruning an already-deleted node.
2367 *
2368 * cursor->ip is NULL when called from the pruning, mirroring,
2369 * and pfs code. If non-NULL propagation will be conditionalized
2370 * on whether the PFS is in no-history mode or not.
2371 */
2375 else
2377 }
2380 }
2382 /*
2383 * Determine whether we can remove a directory. This routine checks whether
2384 * a directory is empty or not and enforces flush connectivity.
2385 *
2386 * Flush connectivity requires that we block if the target directory is
2387 * currently flushing, otherwise it may not end up in the same flush group.
2388 *
2389 * Returns 0 on success, ENOTEMPTY or EDEADLK (or other errors) on failure.
2390 */
2391 int
2393 {
2397 /*
2398 * Check directory empty
2399 */
2425 }