Devil's den

Committing a journal transaction in jbd

2011-07-02T02:38:00.000-07:00

Journal's transaction commit consists of 8 phases, with the journal's state transitions mentioned as below in each of the phase.

The main function which does the journal commit is journal_commit_transaction(). When we decide to commit the transaction, journal is in running state. (T_RUNNING)

Lock the transaction for new updates. ===> T_LOCKED
---> Wait for any existing handles in the transaction to complete the updates.
---> Discard buffers from reserved list. (t_reserved_list).

If any buffer is part of next transaction, it is transferred to appropriate list of next transanction, otherwise dropped from journal's list.
---> Drop write-back buffers from checkpoint list.(t_checkpoint_list). Unless the buffers belong to the running or commiting transaction, the corresponding transaction will also be freed up.

Phase 1 start

---> Change transaction state to T_FLUSH
---> Switch the revoke tables.
---> At this point there is no running transaction, it is changed to a commiting
transaction.

Phase 2 start

/* Flushing starts now */
---> Data buffers are flushed first. (t_sync_datalist)
---> Write out revoke records from the revoke hash list and flush to the descriptor blocks in journal.
---> Change transaction state to T_COMMIT

Phase 3 start

---> Flush metadata buffers (present on t_buffers list). See journal_write_metadata_buffer()

Phase 4 start

---> Wait for all the IO submitted buffers above. Wait for metadata buffers which are present on t_iobuf_list. The dummy buffer heads created for metadata buffers are released. The original metadata buffer which was put on shadow list is released, but put into t_forget list.

Phase 5 start

---> Wait for the submitted revoke record and descriptor buffers to complete and written out. This is done by waiting for buffers on t_log_list.

Phase 6 start

---> Change transaction state to T_COMMIT_RECORD
---> IO for data is complete now. Write the commit record in journal.

Phase 7 start

---> Walk the journal's t_forget list to get rid of buffers till there are no more buffers on it. As each buffer is examined, we check if it was on the checkpoint io list of previous transaction. If it is, its removed and if required (in case its dirty) its transferred to the checkpoint list of the committing transaction. See __journal_insert_checkpoint()

Phase 8 start

--> We are done committing the transaction now.
---> Change transaction state to T_FINISHED
---> Set committing transaction = NULL.
---> Calculate average commit time for future use.
---> Setup the checkpointing transaction.

Journalling layer in ext3 (jbd)

2011-07-02T01:58:00.000-07:00

Terminology
Journal handle - A handle pointer each of which represents a single atomic filesystem operation. It tracks all the modifications done as part of one atomic operation.
Transaction - A single atomic sequence of events which guarantees filesytem consistency. It can consist of a single handle or multiple handles for batching efficiency.
Transaction commit - Flushing the in-memory contents of journal to appropriate blocks in journal along with writing a commit record on disk in journal.
Transaction checkpoint - Flushing the contents from journal to their actual location on disk. This is done periodically to make journal space reusable.

Typically journalling a filesystem operation consists of following three steps :-

a) Starting a handle - journal_start(). We need to specify how many fs blocks this op can potentially modify. This is required to ensure that there would be enough space in the journal to completely write contents of this operation.
The number of blocks required is the total number of blocks, including the data which is going to change, metadata blocks, quota blocks if any etc. As an example see EXT3_DATA_TRANS_BLOCKS. These are called buffer credits for the handle.

b) After getting a handle, next step is to associate the modified blocks with the journal handle, so that journal knows that it has to write these blocks in journal. This is done via following APIs journal_get_write_access(handle, bh) which tells the journal that this buffer is going to be modified. A buffer which is of interest to journalling layer has BH_JBD set on it and has a non-zero b_count. At this point a "journal_head" is attached to the buffer. A journal_head can only be part of 1 transaction.

journal_get_write_access(handle, bh) {
    journal_add_journal_head(bh);
    do_get_write_access(handle, jh, 0);
    journal_put_journal_head(bh);
}

journal_add_journal_head(bh) {
     jh = journal_alloc_journal_head();
         set_buffer_jbd(bh);
         bh->b_private = jh;
         jh->b_bh = bh;
     jh->b_jcount++;
}

PS: A buffer is already part of a transaction if its journal_head's b_transaction or b_next_transaction is set. Most of the times, only b_transaction is set. b_next_transaction will be set incase the buffer is getting committed from previous transaction and we are changing it for the current transaction. The b_next_transaction tells journal that this buffer is going in next transaction. In this case a copy on write is performed and the frozen copy is stored in jh->b_frozen_data.
NB : Buffer's b_transaction will only be set if its part of running or committing transaction and not if it resides on some other list like checkpoint list etc.

c) Stop the handle - journal_stop() : As the name suggests, journal stop marks the completion of an op wrt to journal. It returns any left over unused buffer credits to the transaction, drops appropriate references and frees the handle pointer.
If the filesystem requested this op in sync mode, we also need to start committing the transaction to the journal on completion of handle. However in the current code there are some optimizations built around it to figure it out whether it is beneficial to start writing to disk immediately, or based on the op rate wait for sometime and let other op do it.

See the following code as example.

int journal_stop(handle_t *handle)
{
    ...............
    if (trans_time < commit_time) {
        ktime_t expires = ktime_add_ns(ktime_get(),
                commit_time);
        set_current_state(TASK_UNINTERRUPTIBLE);
        schedule_hrtimeout(&expires, HRTIMER_MODE_ABS);
    }    
    ...............
}

Each journal_start/stop pair ie...each handle consists of one atomic filesystem operation. Some fs operations may be atomic in itself but still may not be sufficient enough to have the filesystem in a consistent state. An example of such an op is write which requires a quota update. Nested journal handles will be required to have such atomic op.

Typical sequence would be
a) Start journal handle for write
b) Start journal handle for quota update
c) Stop journal handle for quota update
d) Stop journal handle for write.

Its only after step (d) that the op can be committed to disk.

NB : A buffer is a "journalled" buffer, only if it has a journal head attached to it.

A journal transaction consists of various lists where buffers of interest can reside. Buffers end up on one of the list depending on what flag/state it has. Below is the buffer state to list mapping. See the function __journal_file_buffer() to see how buffers are moved across lists.

List type => buffer state flag
transaction->t_sync_datalist => BJ_SyncData
transaction->t_buffers => BJ_Metadata
transaction->t_forget => BJ_Forget
transaction->t_iobuf_list => BJ_IO
transaction->t_shadow_list => BJ_Shadow
transaction->t_log_list => BJ_LogCtl
transaction->t_reserved_list => BJ_Reserved
transaction->t_locked_list => BJ_Locked

checkpointing transactions in journal (jbd)

2011-07-02T01:41:00.000-07:00

Journal checkpointing : jbd/checkpoint.c
----------------------
The main functions involved in doing journal checkpointing are :-
a) log_do_checkpoint
b) __process_buffer
c) __flush_batch
d) __wait_cp_io

log_do_checkpoint picks up the first transaction on the checkpoint list and then iterates over all the buffers present in the transaction by calling __process_buffer on each of them. As it traverses, it keeps accumulating them in a local array for batching of disk writes. As part of processing it also moves the buffer from checkpoint_list to checkpoint_io_list to indicate that io is pending on these buffers.
Once the array is full or we have no more buffers to process __flush_batch is called to send those buffers to disk for writing.

After the buffers are submitted to disk, __wait_cp_io() is called to wait on each of the buffers for write to complete. After they get cleaned they are removed from the checkpoint_io_list. After all the buffers are freed, transaction itself is freed.

* Helper functions to clear all the clean buffers from the checkpoint list.
__journal_clean_checkpoint_list : Traverses the transactions in checkpoint transactions list (j_checkpoint_transactions) and frees memory by walking each list (j_checkpoint_list) at a time.

Journal (jbd) revoke mechanism

2011-07-01T20:18:00.000-07:00

Journal revoke :- jbd/revoke.c
------------------

Revoke is a method of preventing journal from corrupting filesystem by not replaying ops and overwriting the contents of a deleted block on a newer block. For example consider the following sequence of steps when the filesystem is mounted in metadata only journalling mode.

a) A metadata block 'B' is journalled and contents are copied to journal.
b) Later 'B' gets freed
c) 'B' is now used to write contents of user data, this is not journalled.

Now if we crash and replay, we need to avoid replaying the contents of block 'B' in journal over the user contents.

Revoke mechanism:- During commits of a transaction all the blocks which are revoked are stored in journal. This record of revoked blocks is used during journal recovery and journal is scanned for the revoked blocks before any ops is replayed. If there are transactions for the block after the last revoke record of a block, these ops are safe to replay. Any transactions which appear before the revoke record aren't replayed. The basic idea is that you don't want to replay ops corresponding to a block which may have been freed. Also note that if there are multiple revoke records corresponding to a block in a journal, we only need to worry about the latest record ie...one with highest transaction id.

From file jbd/revoke.c.

 * We can get interactions between revokes and new log data within a
 * single transaction:
 *
 * Block is revoked and then journaled:
 *   The desired end result is the journaling of the new block, so we
 *   cancel the revoke before the transaction commits.
 *
 * Block is journaled and then revoked:
 *   The revoke must take precedence over the write of the block, so we
 *   need either to cancel the journal entry or to write the revoke
 *   later in the log than the log block.  In this case, we choose the
 *   latter: journaling a block cancels any revoke record for that block
 *   in the current transaction, so any revoke for that block in the
 *   transaction must have happened after the block was journaled and so
 *   the revoke must take precedence.
 *
 * Block is revoked and then written as data:
 *   The data write is allowed to succeed, but the revoke is _not_
 *   cancelled.  We still need to prevent old log records from
 *   overwriting the new data.  We don't even need to clear the revoke
 *   bit here.

There are two hash tables to store the revoked entries. These two tables are required one for the running transaction and one for the committing transaction (if any). As you can guess new entries are always logged into the revoke table pointed by current journal->j_revoke pointer which points to the one corresponding to running transaction. You can think of it as a double buffering mechanism. These tables are switched alternately during the commit from kjounald. Access to these hash table entries is protected by the j_revoke_lock.

Important functions:-
Initialize revoke hash : journal_init_revoke()
Inserts in hash : insert_revoke_hash()
Find in hash : find_revoke_record()
Transfer the in-memory revoke table to ondisk journal : journal_write_revoke_records()

NB: Note that you need to revoke a block before freeing it in bitmap and not the viceversa to prevent races.

The buffer heads maintains two set of flags to indicate the revoke status of a buffer.
a) RevokeValid : The revoke status of this buffer is known and can be trusted. If this is not set we can't say much about the buffer and need to search for it in hash.
b) Revoke{set/clear} : These flags make sense when above is set. They tell whether the block is revoked or not.

Journal recovery in jbd

2011-06-26T23:05:00.000-07:00

Journal recovery :- jbd/recovery.c
------------------

Journal recovery is quite simple. It basically consists of below steps.

a) Readahead journal blocks in memory.

b) Do first pass (PASS_SCAN) to see if we need a recovery. If yes what all transactions do we need to replay, if the journal is valid etc other sanity checks. After the first scan pass, an incore data structure about the journal (struct recovery_info) is populated which contains the required information about the recovery.

c) Do second pass (PASS_REVOKE). This traverses all the revoke block types and builds the incore hash of block numbers which are revoked. This ensures that we don't replay ops corresponding to these blocks when we do the actual replay.

d) Do the third/final pass (PASS_REPLAY) which actually does the job of replaying the journal and copies the data from journal to the real filesystem. Replaying a op simply consists of reading the corresponding block number from filesystem, copying the contents from journal to buffer and then marking the buffer dirty which would be written back to the actual location in filesystem.

NB: Steps (b), (c) and (d) are done through a common function do_one_pass().
e) Once the replay is complete, throw away the in-memory revoke hash.

f) Sync the blockdevice.

g) Once the recovery is done, journal_reset() is called to setup the inmemory fields of journal, and journal is ready for business again.

journal_recover()
|
--> do_one_pass(PASS_SCAN)
|
--> do_one_pass(PASS_REVOKE)
|
--> do_one_pass(PASS_REPLAY)
|
--> journal_clear_revoke()
|
--> sync_blockdev() and journal_reset()

mcopy support in fsdb for ufsutils

2010-08-23T22:52:00.000-07:00

I have been looking for something like mcopy support in ufsutils so that I could just copy any files from userspace to the UFS filesystem. This is primarily important because by default kernel is not configured/compiled to have readwrite support for UFS. Either you need to have your own custom compiled kernel or something else so that you can mount the UFS filesystem and then do a copy.

Below is a patch (quick, ugly and dirty) which I wrote for myself which might be useful to you too. It is definitely not the best written but it does its job. Inorder to keep things simple even though I wanted to add a new command "addfile" (or something similar) to fsdb, I have removed other commands from this fsdb and just made it to work like mcopy because I needed it to be integrated with my shell scripts.

Copy the file fsdb.c in the folder ufsutils-7.0/fsdb.ufs/ and then recompile fsdb. If you have a newer version you will want to copy the contents from the original file. Just grep for "MANISH" in the file. Recompile and njoy !!!

Typical invocation would be something like

$./fsdb myufs_file_system local_file_to_copy destination_path_in_FS
eg..

$./fsdb myfs testfile.c /boot/dummyfile.c

Download fsdb.c here

Always verify your FS with fsck after running this :-). I'm not responsible if you lose your data.

* I think it has a small bug while doing truncation of files which are less than size 48K.

Compatibility flags in ext filesystems

2009-05-15T03:11:00.000-07:00

Ever wondered how do ext filesystems are compatible with each other in a way that most of the times they can be mounted seamlessly even though they have ondisk different structures, or in other words how does ext ensures that the ondisk changes are compatible across different releases ?
This is possible due to three important fields present in ext superblock collectively known as compatibilty bitmaps. We will discuss each of them with anexample.

Usually when a new feature is added in ext, a bit is assigned in superblock to indicate whether the filesystem has that feature or not. The decision of putting this bit in which compatibility bitmap is of utmost importance and depends on the nature of the enhancement done.

Compatible features :(s_features_compat) (EXT3_FEATURE_COMPAT_HAS_JOURNAL - Journal support is valid)

Readonly compatible features :(s_feature_ro_compat) (EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER - Filesystem has sparse superblocks ie.. there are backups of superblock in block numbers multiple of 3,5 & 7). - These are the features which are only supported if the file system is mounted in read only mode.

Incompatible features :(s_feature_incompat) EXT4_FEATURE_INCOMPAT_EXTENTS These are the features which older kernel won't be able to interpret and understand and in such cases they should refuse to mount if an incompat bit is set. One such example is the extent map changes, since it changes the way block pointers are stored on disk, older kernels who know only direct/indirect block formats will not be able to read this properly and thus can't serve data when requested.

Inorder to specify a new feature, its compatibility has to be decided and then it is added to the compatibility flags appropriately. See the macro EXT3_FEATURE_RO_COMPAT_SUPP and others to get an idea.

There have been talks and suggestions about adding these compatibility flags on per inode basis rather than the filesystem to achieve maximum backwards compatibility, so that only fewer files are non-compatible.

ext3 write call stack

2009-03-05T22:03:00.000-08:00

Easy way to convert negative integers to hexadecimal

2008-09-18T23:13:00.001-07:00

If you came here looking for some magic......sorry .... I had some issues representing negative integers in hex. Every time I had to convert them to binary, do a 2's complement and then reconvert to hex :-( so was looking for a way which I could use to quickly do my job. I got this trick from net and thought it is pretty easy. You just need to keep the following mapping in mind (or paper :-) though it is pretty simple).

0 1 2 3 4 5 6 7
F E D C B A 9 8

that's all. The above table is just numbers 1-15 in clockwise direction, or more technically the upper number is inverse of the below one.

Now to convert any number say -7218, follow below steps :-

a) Convert 7218 to hex = 0x1C32
b) Interchange each digit with its corresponding counter bit from mapping = 0xE3CD
c) Shift the last digit to left by 1 place...so D becomes E = 0xE3CE = -7218 = 0xFFFFE3CE (don't forget to fill it with 'F's on left. If you don't fill it with 'F' it becomes 65536-7218 = 58318)

NOTE : If the last digit is 'F' and you shift left, you go to '0' and then shift the next digit to left. (Much like carry over).

ext filesystem online resizing.

2008-09-12T23:03:00.000-07:00

Below notes are based on my understanding of code and most of the stuff is copied directly from the paper presented by Andreas Dilger in OLS-2002 "Online ext2 and ext3 Filesystem Resizing". So if you find any errors below they are due to me, and you may want to read the full paper for proper detailed explaination.

Primary operations involved in resizing :-
a) Increase the total number of blocks in primary and backup superblock.
b) Increase the count of free blocks in primary superblock and group descriptor for that group.
c) Increase the number of reserved filesystem blocks.
d) Remount with "-o remount,resize=<newsize>" option.

NOTE: You cannot shrink the filesystem. Shrinking is in general discouraged by filesystems and most of them don't support it, because this might lead to stale/invalid nfs file handles if the client has a file opened and you shrunk the filesystem.

Case 1: Adding blocks to the end of the last partially filled block group.

In order to increase the free blocks count and update block bitmaps, a fake inode is created which spans the newly added blocks at the end of last block group. Since the blocks are already being used by this fake inode we don't have risk of getting it used by anyone else. Now to make these blocks available to filesystem all that needs to be done is to delete this inode by ext2_free_blocks(). During freeing of this inode, appropriate counts and block bitmaps will be updated. This inode is only in memory and has enough fields as required by ext2_free_blocks().
Next is to update the superblock in backup superblocks. Since the backup superblocks are not accessed by kernel they can be directly modified by userspace. If the resize operations is done via mount then since backup superblocks are not updated, but they will be updated to proper values when e2fsck is run next time.

Case 2: Adding new block groups at the end of full block group.

Main steps required to handle this case are :-
a) Create new block bitmaps and inode bitmaps for each added block group and updated them appropriately to reflect the available block and inodes within the group.
b) Add the new entry to group descriptor table. Increase the number of groups in the filesystem so that the inode/block allocation routines know that there are new groups available with free resources.

Inorder to avoid doing all this stuff from kernel, increasing the resources is done from userspace before the kernel becomes aware of new groups. Since as long as the kernel is unaware of new groups, it cannot allocate anything from there and moreover since we are adding at the last, it is safe to do these operations from userspace.

Case 3 : Adding a new block group in new group descriptor block.

This is a bit complex situation because backup superblocks and group descriptors are situated at the start of a block group (so as to be easily identifiable by e2fsck in case of corrruptions), followed by inode and block bitmap. Adding a new block group would mean overwriting these bitmaps and thus they need to be shifted to accomodate the new block. This relocation is not of a serious problem since gdt stores the location of bitmaps. So all we need to do is shift the blocks and then update the new information in the gdt. But this movement of blocks cannot be done while the filesystem is mounted, to avoid any mess within kernel.
Such cases need an unmount of the filesystem (commonly known as filesystem preparation) and they have the advantage that the changes made are compatible with older kernels. However there is another alternative without offlining the filesystem if the user is ready to break this compatibility.

Andreas nicely explains this case in his paper, and I would suggest to read section 3.4 for those who are interested.

Above strategy is for ext2, however resizing in ext3 using the above poses certain problems like :-

a) Writing directly to the device is unsafe since, there is a journalling layer whose job is to make sure that everything is consistent. Thus if you bypass it, it might lead to ondisk corruptions in the filesystem.
b) Unlike ext2, there may be copies of data in ext3 made by journalling and thus there may be differences in what was read and what actually is there if you try to do it from userspace. (See paper)
c) Since ext3 resizing is done through journal, in case if the resize has made to journal and then system crashed. In such cases during reboot journal will be replayed, however since superblock is read first the new size will not be updated. This case is detected by comparing filesystem size before and after journal replay and then update the appropriate datastructures.

ioctls - An easy interface to talk to kernel

2008-09-07T23:18:00.001-07:00

There are many *good* resources available on net if you want to know about ioctls. One of them is "man ioctl"
If you want to know about the list of ioctls, one quick way is "man ioctl_list". What follows below is a layman explaination and may not be liked by "strict" technical persons.

a) What are ioctls ?
ioctls are like swiss knife, one interface to do lot of things. A simple way for userspace to talk to kernel.
Among other available options (syscalls, procfs, sysfs, debugfs .. etc.), probably ioctls are the easiest one if you want to talk to kernel space as well as get that into mainline kernel. One of the reasons is because they are easy to implement and everyone follows its own convention (though it is discouraged) due to lack of no single standard.

To implement an ioctl, all you need to do is tell kernel that I will be sending some *codenumber* from userspace and depending on the codenumber you have to do something (execute a function). Much like switch-case or RPC.

b) How to implement ioctls ?
Depending on the way you want to talk to kernel, you can have an in, out, none or both arguments and you need to tell kernel accordingly so that it can take the appropriate action. Remember that you have to send a *codenumber* to kernel, so you must embed this information in it along with the functionality that you desire.

ioctls are declared using the standard macros defined in asm/ioctl.h. Macros are of type _IO(type,nr) and {_IOR,_IOW,_IOWR}(type,nr,size). Note that R and W are from user perspective (same as read & write). The last parameter 'size' is actually the datatype that needs to be transferred.

An example of ioctl by which you need to change the version of a file in kernel is :-
#define EXMPL_IOC_CHANGE_VERSION _IOW('f',7,long)

This gets expanded into a *codenumber* due to below defined macros :-
#define _IOW(type,nr,size) _IOC(_IOC_WRITE,(type),(nr),(_IOC_TYPECHECK(size)))
#define _IOC(dir,type,nr,size) \
(((dir) << _IOC_DIRSHIFT) | \ /* DIRSHIFT == 30 */
((type) << _IOC_TYPESHIFT) | \ /* TYPESHIFT == 8 */
((nr) << _IOC_NRSHIFT) | \ /* NRSHIFT == 0 */
((size) << _IOC_SIZESHIFT)) /* SIZESHIFT == 16 */
# define _IOC_WRITE 1U

Based on the arguments passed this will create a unique *codenumber* which your module needs to understand. _IOC_TYPECHECK is just a macro for compiler to check for invalid uses of size argument. The ioctl number 'nr' should be chosen such that it doesn't conflict with others (that is one reason why ppl hate ioctls). Some devices use their major number for this.

Once I have defined my ioctl, I need to make kernel understand it. This is done by installing your ioctl handler in the kernel as below :-


struct file_operations my_file_operations = {
              .read = my_read_func,
              .write = my_write_func,
              ........
              .ioctl = my_ioctl_handler,
              ........
              ........
}

and then define my_ioctl_handler() which performs the actual action.


long my_ioctl_handler(struct file *filp, unsigned int cmd, unsigned long arg) {
       struct inode *inode = filp->f_dentry->d_inode;
       unsigned int version;
       switch(cmd) {
        ...........
       case EXMPL_IOC_CHANGE_VERSION : 
                        if (get_user(version, (int __user *) arg)) {
            err = -EFAULT;
           goto err_out;
          }
                        inode->i_version = version;
                        return 0;
       ............
}

And then in userspace, you need to invoke your ioctl as :-


main() {
  int fd;
  fd = open("myfile",O_RDWR);
  if(fd<0)
    exit(1);
  if(ioctl(fd,EXMPL_IOC_CHANGE_VERSION,123)))
      fprintf(stderr,"Some error in ioctl ...\n")
  ........
}

As you can see from the example above, ioctls are very easy interface to notify kernel to do something and are largely used in device drivers. Read Documentation/ioctl-numbers.txt for more on them.