lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <536D6780.2050007@oracle.com> Date: Fri, 09 May 2014 16:40:48 -0700 From: mingming cao <mingming.cao@...cle.com> To: linux-ext4@...r.kernel.org, Ted Tso <tytso@....edu> Subject: proposed draft for ext4 reflink Hello, I have been thinking about adding reflink support to ext4 filesystem. File reflink supports multiple files share the same data blocks. This is very useful to take snapshots and doing backups. When reflink command is called, a new file/inode is created, but the new file points to the same data blocks from the original file. When there is need to change the new file data, copy on write is triggered. Currently there are other filesystem like btrfs and OCFS has reflink support. And it seems interesting to add this feature to ext4 as well. Here is the first draft of ext reflink design text. I am sending out in hope I could get more feedbacks and suggestions. Thanks! Mingming ext4 reflink overview ===================== In current ext4 filesystem, one data block could only be used to one inode at a time. After reflink, we break this rule, same data block could be shared by multiple files. The key issue here is how to avoid freeing up blocks still used by other inode (reflinked files). We need to keep track of the usage of data blocks using counters. Using the refcount to track block usage is pretty straightforward. When reflink is called, shared data block refcount are increased. Upon read, there is no action needed, but if one inode start to write to the shared data block, copy on write will happen first. The refcount of the original data block will be decreased correspondingly and a new data block is allocated to for the modified data. refcount will be decreased whenever one of the inode free its data, and and only when the refcount drop to zero could the filesystem safely claim this data block back. The key question is where to store the refcount for each shared data blocks. Current ext4 block bitmaps only used for if the block is free or not. We need to store the refcount somewhere else. There are multiple options. I started to think about option 1) at the beginning then option 2) came out when data checksumming feature is planned. Option 2) sounds more straignt forward and I will list both so we could have some discussions about which would be better solution. Option 1) Dynamic per-reflinked files refcount =================================== Based on reflink file groups, we could have a dynamically allocated shared refcount tree. This tree is hanging out from the inodes that sharing the same set of blocks. The tree is indexed by physical block numbers. The files sharing blocks will to use this tree as reference to look up the reference counter to determine if the block is safe to free, or need a copy-on-write. COW (Copy On Write) and refcount tree ------------------------------------- We would need an extent like structure to store the {physical block number, len, refcount} refcount record in refcount tree. When reflink is called, a new inode is created, and the extent tree is copied from the original inode to the new inode. If the original inode already have a refcount tree, then the refcount for the extent will be increased. If not, then refcount tree is created and the two inodes all point to the same refcount tree. Every extent will have a refcount record and will be inserted into the refcount tree. At that very beginning time, the refcount record is 1:1 map to the extent structure. This will change as inode starts to write. When inode wants to overwrite to a shared block, copy on write happens -- new block be allocated before the write and the original extent data are remain untouched. The original refcount record need to be updated accordingly after COW. If the inode only overwrite part of extent, the refcount record need to split and decrease refcount for the portion of the change extent. The refcount for the portion that still shared by the inodes remain the same. In worse case refcount tree becomes very fragmented if inode keep rewriting after reflink. Imagining one inode rewrite every 4k after being reflinked by other inode. At certain point, we may need to allow larger chunk of COW, or even a whole file data copy would be triggered if fragmentation getting worse. The refcount tree could be a btree that easy to insert, search etc operate. Since this tree is shared by reflinked files, we would need a lock to guard access this tree operations. Since this is important metadata, we would want to add checksums for refcount index and leaf blocks where the refcount records are stored. Link refcount tree to inodes ----------------------------------- The root of refcount tree are pointed from inodes that are reflinked. At the time of the reflink, the address of root refcount tree would be linked from inodes. To store the location of the refcount tree, one way is to use extended attributes. Extended attributes have to be copied to the new reflinked file first. The location of the reflink root block is stored as two extended attributes (32 bits). We also could store the address of refcount tree into inode size extra_isize. Liu zheng's proposal of project quota also looks for space in ext4 inode to store project id. Expanding inode size extra_isize impact all files so this is not optimal. I haven’t thought much about what we need to do in the e2fsprogs side, but that would require teach fsck to understand refcount tree. Option 2 ) Static filesystem-wide per-block refcount ======================================== The most straightforward way is to create refcount record for every data block in the filesystem. Similar to data checksumming feature proposed earlier, along with other blockgroup metadata, we could have a per-block metadata record, to store refcounts, back reference, data checksumming. The per for the blocks in that blockgroup. This works well if the data checksumming feature plans to go this direction (adding per data block metadata), and we could just add two bytes for block refcount. Getting the block refcount will only take O(1) time if the per-data metadata are allocated statically, and there is basically very little impact to performance. The downside is the extra space cost for the blocks not shared. Unlike data checksumming feature, refcount only matters to those blocks being shared in the reflinked inodes. And secondly, it would not as efficient as per-extent refcount as we would need to track per-block refcount instead of larger extent granularity. Overall, this is just a draft to show the thoughts about implement reflink for ext4 filesystem. I am sure there are lots of other things that I might missed or havent thought through. I am looking for many suggestions, critics and discussion, and hopefully this could be a good start. Mingming -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists