Lines Matching +full:as +full:- +full:is
1 .. SPDX-License-Identifier: GPL-2.0
11 subsystem is based on. This document describes the design and algorithms that
12 the XFS journalling subsystem is based on so that readers may familiarize
19 the basic concepts covered, the design of the delayed logging mechanism is
32 Some objects, such as inodes and dquots, are logged in logical format where the
33 details logged are made up of the changes to in-core structures rather than
34 on-disk structures. Other objects - typically buffers - have their physical
40 The reason for these differences is to keep the amount of log space and CPU time
41 required to process objects being modified as small as possible and hence the
42 logging overhead as low as possible. Some items are very frequently modified,
44 the overhead of metadata logging low is of prime importance.
58 reservation they take. These are known as "one shot" and "permanent"
64 place. This means that permanent transactions can be used for one-shot
65 modifications, but one-shot reservations cannot be used for permanent
68 In the code, a one-shot transaction pattern looks somewhat like this::
76 As items are modified in the transaction, the dirty regions in those items are
77 tracked via the transaction handle. Once the transaction is committed, all
81 In contrast, a permanent transaction is made up of multiple linked individual
97 While this might look similar to a one-shot transaction, there is an important
105 This results in a series of "rolling transactions" where the inode is locked
107 transactions is running, nothing else can read from or write to the inode and
111 It is important to note that a series of rolling transactions in a permanent
113 individual modification is atomic, the chain is *not atomic*. If we crash half
117 This affects long running permanent transactions in that it is not possible to
119 there is no guarantee of how much of the operation reached stale storage. Hence
122 recovery can complete the operation once the first transactions is persisted in
123 the on-disk journal.
135 that if a specific change is seen after recovery, all metadata modifications
139 ensuring that a long running permanent transaction is fully committed once it is
140 complete, we can explicitly tag a transaction as synchronous. This will trigger
156 journal. This is achieved by the transaction reservations that are made when
157 a transaction is first allocated. For permanent transactions, these reservations
158 are maintained as part of the transaction rolling mechanism.
160 A transaction reservation provides a guarantee that there is physical log space
162 modifications to objects and items. As such, the reservation needs to be large
165 transaction, we have to reserve enough space to record a full leaf-to-root split
166 of the btree. As such, the reservations are quite complex because we have to
178 for the transaction that is calculated at mount time. We must guarantee that the
179 log has this much space available before the transaction is allowed to proceed
183 For one-shot transactions, a single unit space reservation is all that is
185 also have a "log count" that affects the size of the reservation that is to be
189 reservation, it is somewhat inefficient to do this as it requires the
190 transaction rolling mechanism to re-reserve space on every transaction roll. We
194 For example, an inode allocation is typically two transactions - one to
202 Hence when the permanent transaction is first allocated, the log space
203 reservation is increased from a single unit reservation to multiple unit
204 reservations. That multiple is defined by the reservation log count, and this
205 means we can roll the transaction multiple times before we have to re-reserve
210 re-reserve physical space in the log. This is somewhat complex, and requires
217 The position in the log is typically referred to as a Log Sequence Number (LSN).
218 The log is circular, so the positions in the log are defined by the combination
219 of a cycle number - the number of times the log has been overwritten - and the
221 offset in the lower 32 bits. The offset is in units of "basic blocks" (512
225 Log space accounting is done via a pair of constructs called "grant heads". The
226 position of the grant heads is an absolute value, so the amount of space
227 available in the log is defined by the distance between the position of the
228 grant head and the current log tail. That is, how much space can be
232 The first grant head is the "reserve" head. This tracks the byte count of the
233 reservations currently held by active transactions. It is a purely in-memory
234 accounting of the space reservation and, as such, actually tracks byte offsets
236 represent the log position, but it is still treated like a split {cycle,offset}
239 The reserve grant head is used to accurately account for exact transaction
241 and need to write into the log. The reserve head is used to prevent new
243 tail. It will block new reservations in a FIFO queue and as the log tail moves
244 forward it will wake them in order once sufficient space is available. This FIFO
245 mechanism ensures no transaction is starved of resources when log space
248 The other grant head is the "write" head. Unlike the reserve head, this grant
250 this might sound like it is accounting the same state as the reserve grant head
251 - and it mostly does track exactly the same location as the reserve grant head -
255 These differences when a permanent transaction is rolled and the internal "log
260 available, as we may end up on the end of the FIFO queue and the items we have
261 locked while we sleep could end up pinning the tail of the log before there is
266 reservation even if there is no reservation space currently available. That is,
267 we need to be able to *overcommit* the log reservation space. As has already
269 grant head does not track physical space - it only accounts for the amount of
271 over the tail of the log all it means is that new reservations will be throttled
272 immediately and remain throttled until the log tail is moved forward far enough
277 As a result, permanent transactions only "regrant" reservation space during
278 xfs_trans_commit() calls, while the physical log space reservation - tracked by
279 the write head - is then reserved separately by a call to xfs_log_reserve()
287 "Re-logging" the locked items on every transaction roll ensures that the items
291 deadlock the log as we cannot take the locks needed to write back that item and
292 move the tail of the log forwards to free up write grant space. Re-logging the
294 making cannot self-deadlock.
298 tail moving forwards and hence ensuring that write grant space is always
303 Re-logging Explained
309 method called "re-logging". Conceptually, this is quite simple - all it requires
310 is that any new change to the object is recorded with a *new copy* of all the
311 existing changes in the new transaction that is written to the log.
313 That is, if we have a sequence of changes A through to F, and the object was
327 In other words, each time an object is relogged, the new transaction contains
334 implement long-running, multiple-commit permanent transactions.
336 A typical example of a rolling transaction is the removal of extents from an
339 keeps relogging the inode and btree buffers as they get modified in each
340 removal operation. This keeps them moving forward in the log as the operation
344 Hence it can be seen that the relogging operation is fundamental to the correct
347 the log - repeated operations to the same objects write the same changes to
348 the log over and over again. Worse is the fact that objects tend to get
349 dirtier as they get relogged, so each subsequent transaction is writing more
353 hand in hand. That is, transactions don't get written to the physical journal
354 until either a log buffer is filled (a log buffer can hold multiple
356 transactions to disk. This means that XFS is doing aggregation of transactions
357 in memory - batching them, if you like - to minimise the impact of the log IO on
360 The limitation on asynchronous transaction throughput is the number and size of
362 buffers available and the size of each is 32kB - the size can be increased up
366 that can be made to the filesystem at any point in time - if all the log
368 the current batch completes. It is now common for a single current CPU core to
377 relogging technique XFS uses is that we can be relogging changed objects
379 return to the previous relogging example, it is entirely possible that
382 That is, a single log buffer may contain multiple copies of the same object,
383 but only one of those copies needs to be there - the last one "D", as it
388 buffers. It is clear that reducing the number of stale objects written to the
390 is the fundamental goal of delayed logging.
392 From a conceptual point of view, XFS is already doing relogging in memory (where
393 memory == log buffer), only it is doing it extremely inefficiently. It is using
394 logical to physical formatting to do the relogging because there is no
399 Delayed logging is the name we've given to keeping and tracking transactional
401 the relogging concept fundamental to the XFS journalling subsystem, this is
402 actually relatively easy to do - all the changes to logged items are already
403 tracked in the current infrastructure. The big problem is how to accumulate
405 Describing the problems and how they have been solved is the focus of this
409 journalling subsystem is that it disassociates the amount of outstanding
414 crash is much greater than for the existing logging mechanism.
417 will result in a consistent filesystem. What it does mean is that as far as the
418 recovered filesystem is concerned, there may be many thousands of transactions
419 that simply did not occur as a result of the crash. This makes it even more
421 need to ensure application level data integrity is maintained.
423 It should be noted that delayed logging is not an innovative new concept that
424 warrants rigorous proofs to determine whether it is correct or not. The method
426 log is used effectively in many filesystems including ext3 and ext4. Hence
427 no time is spent in this document trying to convince the reader that the
428 concept is sound. Instead it is simply considered a "solved problem" and as
429 such implementing it in XFS is purely an exercise in software engineering.
438 4. No on-disk format change (metadata or log format).
446 ---------------
449 existing log item dirty region tracking) is that when it comes to writing the
451 is not changing while we do this. This requires locking the object to prevent
458 flushing thread has the delayed logging tracking lock already held, and is
463 The solution is relatively simple - it just took a long time to recognise it.
467 transaction commit while the item is locked in the transaction. Instead of
468 using the log buffer as the destination of the formatting code, we can use an
473 the changes in a format that is compatible with the log buffer writing code.
475 rewriting can all be done while the object is locked during transaction commit,
476 resulting in a vector that is transactionally consistent and can be accessed
486 Object +---------------------------------------------+
487 Vector 1 +----+
488 Vector 2 +----+
489 Vector 3 +----------+
493 Log Buffer +-V1-+-V2-+----V3----+
497 Object +---------------------------------------------+
498 Vector 1 +----+
499 Vector 2 +----+
500 Vector 3 +----------+
504 Memory Buffer +-V1-+-V2-+----V3----+
505 Vector 1 +----+
506 Vector 2 +----+
507 Vector 3 +----------+
509 The memory buffer and associated vector need to be passed as a single object,
510 but still need to be associated with the parent object so if the object is
515 buffer is to support splitting vectors across log buffer boundaries correctly.
518 buffer writing (i.e. double encapsulation). This would be an on-disk format
519 change and as such is not desirable. It also means we'd have to write the log
520 region headers in the formatting stage, which is problematic as there is per
525 self-describing object that can be passed to the log buffer write code to be
526 handled in exactly the same manner as the existing log vectors are handled.
527 Hence we avoid needing a new on-disk format to handle items that have been
532 ----------------
537 log item is the natural place to store this vector and buffer, and also makes sense
538 to be the object that is used to track committed objects as it will always
541 The log item is already used to track the log items that have been written to
543 and as such are stored in the Active Item List (AIL) which is a LSN-ordered
546 that is in the AIL can be relogged, which causes the object to be pinned again
550 Essentially, this shows that an item that is in the AIL can still be modified
551 and relogged, so any tracking must be separate to the AIL infrastructure. As
553 can we store state in any field that is protected by the AIL lock. Hence the
557 Similar to the AIL, tracking of committed items is done through a new list
560 in transaction commit order, so when an object is relogged it is removed from
561 its place in the list and re-inserted at the tail. This is entirely arbitrary
562 and done to make it easy for debugging - the last items in the list are the
563 ones that are most recently modified. Ordering of the CIL is not necessary for
564 transactional integrity (as discussed in the next section) so the ordering is
569 ----------------------------
571 When we have a log synchronisation event, commonly known as a "log force",
574 need to be written as an atomic transaction. The need for all the objects to be
575 written as an atomic transaction comes from the requirements of relogging and
576 log replay - all the changes in all the objects in a given transaction must
578 a transaction is not replayed because it is not complete in the log, then
583 transaction, nor does the log replay code. The only fundamental limit is that
585 reason for this limit is that to find the head and tail of the log, there must
587 transaction is larger than half the log, then there is the possibility that a
594 to any other transaction - it contains a transaction header, a series of
596 perspective, the checkpoint transaction is also no different - just a lot
597 bigger with a lot more items in it. The worst case effect of this is that we
600 Because the checkpoint is just another transaction and all the changes to log
601 items are stored as log vectors, we can use the existing log buffer writing
607 per-checkpoint context that travels through the log write process through to
611 checkpoint from initiation to checkpoint completion. A new context is initiated
612 at the same time a checkpoint transaction is started. That is, when we remove
623 checkpoint sequence order is maintained during log replay.
630 detached from the log items. That is, when the CIL is flushed the memory
638 Log Item <-> log vector 1 -> memory buffer
639 | -> vector array
641 Log Item <-> log vector 2 -> memory buffer
642 | -> vector array
647 Log Item <-> log vector N-1 -> memory buffer
648 | -> vector array
650 Log Item <-> log vector N -> memory buffer
651 -> vector array
653 And after the flush the CIL head is empty, and the checkpoint context log
659 log vector 1 -> memory buffer
660 | -> vector array
661 | -> Log Item
663 log vector 2 -> memory buffer
664 | -> vector array
665 | -> Log Item
670 log vector N-1 -> memory buffer
671 | -> vector array
672 | -> Log Item
674 log vector N -> memory buffer
675 -> vector array
676 -> Log Item
678 Once this transfer is done, the CIL can be unlocked and new transactions can
682 Once the checkpoint is written into the log buffers, the checkpoint context is
689 Discussion Point: I am uncertain as to whether the log item is the most
698 vectors in one checkpoint transaction. I'd guess this is a "measure and
700 is in the dev tree....
703 --------------------------------------
705 One of the key aspects of the XFS transaction subsystem is that it tags
708 future operations that cannot be completed until that transaction is fully
710 re-using a freed metadata extent for a data extent), a special, optimised log
714 transaction. This LSN comes directly from the log buffer the transaction is
718 transactions is required.
720 As discussed in the checkpoint section, delayed logging uses per-checkpoint
721 contexts, and as such it is simple to assign a sequence number to each
723 atomically, it is simple to ensure that each new context has a monotonically
725 atomic counter - we can just take the current context sequence number and add
731 checkpoint sequence needs to be committed before they can continue. As a
738 checkpoint commit completes, it is removed from the committing list. Because
747 current design is needed before making any decisions here.
749 The main concern with log forces is to ensure that all the previous checkpoints
754 else for such serialisation - it only matters when we do a log force.
756 The only remaining complexity is that a log force now also has to handle the
757 case where the forcing sequence number is the same as the current context. That
758 is, we need to flush the CIL and potentially wait for it to complete. This is a
764 behaves the same regardless of whether delayed logging is being used or not.
767 ------------------------------------------------
769 The big issue for a checkpoint transaction is the log space reservation for the
770 transaction. We don't know how big a checkpoint transaction is going to be
773 amount of log space required as we add items to the commit item list, but we
779 etc. as well as the actual space for all the changed metadata in the
780 transaction. While some of this is fixed overhead, much of it is dependent on
785 inode changes. If you modify lots of inode cores (e.g. ``chmod -R g+w *``), then
787 format structure. That is, two vectors totaling roughly 150 bytes. If we modify
789 vector is 12 bytes, so the total to be logged is approximately 1.75MB. In
792 buffer format structure for each buffer - roughly 800 vectors or 1.51MB total
793 space. From this, it should be obvious that a static log space reservation is
794 not particularly flexible and is difficult to select the "optimal value" for
800 then calculating the increase or decrease in space used as the object is
802 log buffer metadata used such as log header records.
804 However, even using a static reservation for just the log metadata is
808 reservation needs to be made before the checkpoint is started, and we need to
810 reservation of around 150KB, which is a non-trivial amount of space.
812 A static reservation needs to manipulate the log grant counters - we can take a
815 every checkpoint transaction completion. Unfortunately, if this space is not
818 The problem with this is that it can lead to deadlocks as we may need to commit
821 space available in the log if we are to use static reservations, and that is
822 very difficult and complex to arrange. It is possible to do, but there is a
825 The simpler way of doing this is tracking the entire log space used by the
827 space required by the log metadata. If this log metadata space changes as a
829 the difference in space required is removed from the transaction that causes
831 available in their reservation for this as they have already reserved the
835 Hence we can grow the checkpoint transaction reservation dynamically as items
840 As mentioned early, transactions can't grow to more than half the size of the
841 log. Hence as part of the reservation growing, we need to also check the size
843 the maximum threshold, we need to push the CIL to the log. This is effectively
844 a "background flush" and is done on demand. This is identical to
845 a CIL push triggered by a log force, only that there is no waiting for the
846 checkpoint commit to complete. This background push is checked and executed by
853 manner that is done for the existing logging method. A discussion point is
855 which is once every 30s.
859 ---------------------------------
863 be done any time before the items are unlocked. The result of this mechanism is
864 that items get pinned once for every transaction that is committed to the log
867 transactions is completed, they will unpin the item once. As a result, the item
869 pending transactions. Thus the pinning and unpinning of a log item is symmetric
870 as there is a 1:1 relationship with transaction commit and log item completion.
873 completion relationship. Every time an object is relogged in the CIL it goes
875 That is, we now have a many-to-one relationship between transaction commit and
876 log item completion. The result of this is that pinning and unpinning of the
883 pin the object the first time it is inserted into the CIL - if it is already in
886 counts, but as each checkpoint completes the pin count will retain the correct
892 guarantee which context the pin count is associated with. This is because of
893 the fact pinning the item is dependent on whether the item is present in the
896 (or not pinning, as the case may be). Hence we must hold the CIL flush/commit
900 ---------------------------------------
902 A fundamental requirement for the CIL is that accesses through transaction
908 As a result, the delayed logging transaction commit code needs to be designed
909 for concurrency from the ground up. It is obvious that there are serialisation
910 points in the design - the three important ones are:
916 Looking at the transaction commit and CIL flushing interactions, it is clear
917 that we have a many-to-one interaction here. That is, the only restriction on
918 the number of concurrent transactions that can be trying to commit at once is
920 limit here is in the order of several hundred concurrent transactions for a
921 128MB log, which means that it is generally one per CPU in a machine.
923 The amount of time a transaction commit needs to hold out a flush is a
924 relatively long period of time - the pinning of log items needs to be done
925 while we are holding out a CIL flush, so at the moment that means it is held
927 are in progress). Ultimately a two pass algorithm where the formatting is done
932 really needs to be a sleeping lock - if the CIL flush takes the lock, we do not
935 items, it will get held for a significant time and so spin contention is a
936 significant concern. Preventing lots of CPUs spinning doing nothing is the
940 It should also be noted that CIL flushing is also a relatively rare operation
941 compared to transaction commit for asynchronous transaction workloads - only
942 time will tell if using a read-write semaphore for exclusion will limit
946 The second serialisation point is on the transaction commit side where items
949 commit/flush exclusion. It also needs to be an exclusive lock but it is only
950 held for a very short time and so a spin lock is appropriate here. It is
952 hold time once per transaction I think that contention is unlikely.
954 The final serialisation point is the checkpoint commit record ordering code
955 that is run as part of the checkpoint commit and log force sequencing. The code
960 record write. As a result it needs a lock and a wait variable. Log force
971 serialisation queues. They use the same lock as the CIL, too. If we see too
972 much contention on the CIL lock, or too many context switches as a result of
979 -----------------
981 The existing log item life cycle is as follows::
1019 Essentially, steps 1-6 operate independently from step 7, which is also
1020 independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9
1021 at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur
1022 at the same time. If the log item is in the AIL or between steps 6 and 7
1023 and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9
1024 are entered and completed is the object considered clean.
1075 logging methods are in the middle of the life cycle - they still have the same
1081 As a result of this zero-impact "insertion" of delayed logging infrastructure
1084 mount option. Fundamentally, there is no reason why the log manager would not
1086 characteristics, but this should not be necessary if delayed logging works as