* [PATCH 1/4] sload.f2fs: fix bugs in f2fs_write_block()
@ 2017-10-31 3:42 Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 2/4] f2fs-tools: f2fs_read() and f2fs_filesize_update() are added Jaegeuk Kim
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: Jaegeuk Kim @ 2017-10-31 3:42 UTC (permalink / raw)
To: linux-f2fs-devel; +Cc: Hyojun Kim, Jaegeuk Kim
From: Hyojun Kim <hyojun@google.com>
Found and fixed following three bugs in f2fs_write_block() function.
- Write (4096 - offset) bytes for the first block even for small count.
- For overwriting, found blkaddr is not used for writing.
- dn.idirty status can be lost by set_new_dnode().
- missing inode_checksum
Signed-off-by: Hyojun Kim <hyojun@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@google.com>
---
fsck/segment.c | 36 +++++++++++++++++++++---------------
1 file changed, 21 insertions(+), 15 deletions(-)
diff --git a/fsck/segment.c b/fsck/segment.c
index d568d61..2ea5bf1 100644
--- a/fsck/segment.c
+++ b/fsck/segment.c
@@ -16,6 +16,14 @@
#include "fsck.h"
#include "node.h"
+static void write_inode(u64 blkaddr, struct f2fs_node *inode)
+{
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_INODE_CHKSUM))
+ inode->i.i_inode_checksum =
+ cpu_to_le32(f2fs_inode_chksum(inode));
+ ASSERT(dev_write_block(inode, blkaddr) >= 0);
+}
+
void reserve_new_block(struct f2fs_sb_info *sbi, block_t *to,
struct f2fs_summary *sum, int type)
{
@@ -71,6 +79,7 @@ static void f2fs_write_block(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
void *data_blk;
struct node_info ni;
struct f2fs_node *inode;
+ int idirty = 0;
int ret = -1;
get_node_info(sbi, ino, &ni);
@@ -86,6 +95,8 @@ static void f2fs_write_block(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
off_in_block = offset & ((1 << F2FS_BLKSIZE_BITS) - 1);
len_in_block = (1 << F2FS_BLKSIZE_BITS) - off_in_block;
+ if (len_in_block > count)
+ len_in_block = count;
len_already = 0;
/*
@@ -115,17 +126,20 @@ static void f2fs_write_block(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
blkaddr = datablock_addr(dn.node_blk, dn.ofs_in_node);
/* A new page from WARM_DATA */
- if (blkaddr == NULL_ADDR)
+ if (blkaddr == NULL_ADDR) {
new_data_block(sbi, data_blk, &dn,
CURSEG_WARM_DATA);
+ blkaddr = dn.data_blkaddr;
+ idirty |= dn.idirty;
+ }
/* Copy data from buffer to file */
- ret = dev_read_block(data_blk, dn.data_blkaddr);
+ ret = dev_read_block(data_blk, blkaddr);
ASSERT(ret >= 0);
memcpy(data_blk + off_in_block, buffer, len_in_block);
- ret = dev_write_block(data_blk, dn.data_blkaddr);
+ ret = dev_write_block(data_blk, blkaddr);
ASSERT(ret >= 0);
off_in_block = 0;
@@ -148,13 +162,12 @@ static void f2fs_write_block(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
/* Update the inode info */
if (le64_to_cpu(inode->i.i_size) < offset + count) {
inode->i.i_size = cpu_to_le64(offset + count);
- dn.idirty = 1;
+ idirty = 1;
}
- if (dn.idirty) {
+ if (idirty) {
ASSERT(inode == dn.inode_blk);
- ret = dev_write_block(inode, ni.blk_addr);
- ASSERT(ret >= 0);
+ write_inode(ni.blk_addr, inode);
}
if (dn.node_blk && dn.node_blk != dn.inode_blk)
@@ -203,15 +216,8 @@ int f2fs_build_file(struct f2fs_sb_info *sbi, struct dentry *de)
n = read(fd, buffer, BLOCK_SZ);
ASSERT(n == de->size);
memcpy(inline_data_addr(node_blk), buffer, de->size);
-
node_blk->i.i_size = cpu_to_le64(de->size);
-
- if (c.feature & cpu_to_le32(F2FS_FEATURE_INODE_CHKSUM))
- node_blk->i.i_inode_checksum =
- cpu_to_le32(f2fs_inode_chksum(node_blk));
-
- ret = dev_write_block(node_blk, ni.blk_addr);
- ASSERT(ret >= 0);
+ write_inode(ni.blk_addr, node_blk);
free(node_blk);
} else {
while ((n = read(fd, buffer, BLOCK_SZ)) > 0) {
--
2.14.0.rc1.383.gd1ce394fe2-goog
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH 2/4] f2fs-tools: f2fs_read() and f2fs_filesize_update() are added
2017-10-31 3:42 [PATCH 1/4] sload.f2fs: fix bugs in f2fs_write_block() Jaegeuk Kim
@ 2017-10-31 3:42 ` Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 3/4] mkfs.f2fs: support quota option in mkfs Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 4/4] fsck.f2fs: support quota Jaegeuk Kim
2 siblings, 0 replies; 4+ messages in thread
From: Jaegeuk Kim @ 2017-10-31 3:42 UTC (permalink / raw)
To: linux-f2fs-devel; +Cc: Hyojun Kim, Jaegeuk Kim
From: Hyojun Kim <hyojun@google.com>
This patch adds f2fs_read() and f2fs_filesize_update(). It also refactors
f2fs_write_block() and renamed as f2fs_write().
Signed-off-by: Hyojun Kim <hyojun@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@google.com>
---
fsck/fsck.h | 6 ++
fsck/segment.c | 248 ++++++++++++++++++++++++++++++++++++++-------------------
2 files changed, 171 insertions(+), 83 deletions(-)
diff --git a/fsck/fsck.h b/fsck/fsck.h
index 1e8ed0b..5628906 100644
--- a/fsck/fsck.h
+++ b/fsck/fsck.h
@@ -219,6 +219,12 @@ void f2fs_alloc_nid(struct f2fs_sb_info *, nid_t *, int);
void set_data_blkaddr(struct dnode_of_data *);
block_t new_node_block(struct f2fs_sb_info *,
struct dnode_of_data *, unsigned int);
+
+/* segment.c */
+u64 f2fs_read(struct f2fs_sb_info *, nid_t, void *, u64, pgoff_t);
+u64 f2fs_write(struct f2fs_sb_info *, nid_t, void *, u64, pgoff_t);
+void f2fs_filesize_update(struct f2fs_sb_info *, nid_t, u64);
+
void get_dnode_of_data(struct f2fs_sb_info *, struct dnode_of_data *,
pgoff_t, int);
void make_dentry_ptr(struct f2fs_dentry_ptr *, struct f2fs_node *, void *, int);
diff --git a/fsck/segment.c b/fsck/segment.c
index 2ea5bf1..e13f147 100644
--- a/fsck/segment.c
+++ b/fsck/segment.c
@@ -68,111 +68,193 @@ void new_data_block(struct f2fs_sb_info *sbi, void *block,
set_data_blkaddr(dn);
}
-static void f2fs_write_block(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
+u64 f2fs_read(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
u64 count, pgoff_t offset)
{
- u64 start = F2FS_BYTES_TO_BLK(offset);
- u64 len = F2FS_BYTES_TO_BLK(count);
- u64 end_offset;
- u64 off_in_block, len_in_block, len_already;
- struct dnode_of_data dn = {0};
- void *data_blk;
+ struct dnode_of_data dn;
struct node_info ni;
struct f2fs_node *inode;
- int idirty = 0;
- int ret = -1;
-
+ char *blk_buffer;
+ u64 filesize;
+ u64 off_in_blk;
+ u64 len_in_blk;
+ u64 read_count;
+ u64 remained_blkentries;
+ block_t blkaddr;
+ void *index_node = NULL;
+
+ memset(&dn, 0, sizeof(dn));
+
+ /* Memory allocation for block buffer and inode. */
+ blk_buffer = calloc(BLOCK_SZ, 2);
+ ASSERT(blk_buffer);
+ inode = (struct f2fs_node*)(blk_buffer + BLOCK_SZ);
+
+ /* Read inode */
get_node_info(sbi, ino, &ni);
- inode = calloc(BLOCK_SZ, 1);
- ASSERT(inode);
-
- ret = dev_read_block(inode, ni.blk_addr);
- ASSERT(ret >= 0);
-
- if (S_ISDIR(le16_to_cpu(inode->i.i_mode)) ||
- S_ISLNK(le16_to_cpu(inode->i.i_mode)))
- ASSERT(0);
-
- off_in_block = offset & ((1 << F2FS_BLKSIZE_BITS) - 1);
- len_in_block = (1 << F2FS_BLKSIZE_BITS) - off_in_block;
- if (len_in_block > count)
- len_in_block = count;
- len_already = 0;
-
- /*
- * When calculate how many blocks this 'count' stride accross,
- * We should take offset in a block in account.
- */
- len = F2FS_BYTES_TO_BLK(count + off_in_block
- + ((1 << F2FS_BLKSIZE_BITS) - 1));
-
- data_blk = calloc(BLOCK_SZ, 1);
- ASSERT(data_blk);
-
- set_new_dnode(&dn, inode, NULL, ino);
+ ASSERT(dev_read_block(inode, ni.blk_addr) >= 0);
+ ASSERT(!S_ISDIR(le16_to_cpu(inode->i.i_mode)));
+ ASSERT(!S_ISLNK(le16_to_cpu(inode->i.i_mode)));
+
+ /* Adjust count with file length. */
+ filesize = le64_to_cpu(inode->i.i_size);
+ if (offset > filesize)
+ count = 0;
+ else if (count + offset > filesize)
+ count = filesize - offset;
+
+ /* Main loop for file blocks */
+ read_count = remained_blkentries = 0;
+ while (count > 0) {
+ if (remained_blkentries == 0) {
+ set_new_dnode(&dn, inode, NULL, ino);
+ get_dnode_of_data(sbi, &dn, F2FS_BYTES_TO_BLK(offset),
+ LOOKUP_NODE);
+ if (index_node)
+ free(index_node);
+ index_node = (dn.node_blk == dn.inode_blk) ?
+ NULL : dn.node_blk;
+ remained_blkentries = ADDRS_PER_PAGE(dn.node_blk);
+ }
+ ASSERT(remained_blkentries > 0);
+
+ blkaddr = datablock_addr(dn.node_blk, dn.ofs_in_node);
+ if (blkaddr == NULL_ADDR || blkaddr == NEW_ADDR)
+ break;
+
+ off_in_blk = offset % BLOCK_SZ;
+ len_in_blk = BLOCK_SZ - off_in_blk;
+ if (len_in_blk > count)
+ len_in_blk = count;
+
+ /* Read data from single block. */
+ if (len_in_blk < BLOCK_SZ) {
+ ASSERT(dev_read_block(blk_buffer, blkaddr) >= 0);
+ memcpy(buffer, blk_buffer + off_in_blk, len_in_blk);
+ } else {
+ /* Direct read */
+ ASSERT(dev_read_block(buffer, blkaddr) >= 0);
+ }
- while (len) {
- if (dn.node_blk != dn.inode_blk)
- free(dn.node_blk);
+ offset += len_in_blk;
+ count -= len_in_blk;
+ buffer += len_in_blk;
+ read_count += len_in_blk;
- set_new_dnode(&dn, inode, NULL, ino);
- get_dnode_of_data(sbi, &dn, start, ALLOC_NODE);
+ dn.ofs_in_node++;
+ remained_blkentries--;
+ }
+ if (index_node)
+ free(index_node);
+ free(blk_buffer);
- end_offset = ADDRS_PER_PAGE(dn.node_blk);
+ return read_count;
+}
- while (dn.ofs_in_node < end_offset && len) {
- block_t blkaddr;
+u64 f2fs_write(struct f2fs_sb_info *sbi, nid_t ino, void *buffer,
+ u64 count, pgoff_t offset)
+{
+ struct dnode_of_data dn;
+ struct node_info ni;
+ struct f2fs_node *inode;
+ char *blk_buffer;
+ u64 off_in_blk;
+ u64 len_in_blk;
+ u64 written_count;
+ u64 remained_blkentries;
+ block_t blkaddr;
+ void* index_node = NULL;
+ int idirty = 0;
- blkaddr = datablock_addr(dn.node_blk, dn.ofs_in_node);
+ /* Memory allocation for block buffer and inode. */
+ blk_buffer = calloc(BLOCK_SZ, 2);
+ ASSERT(blk_buffer);
+ inode = (struct f2fs_node*)(blk_buffer + BLOCK_SZ);
- /* A new page from WARM_DATA */
- if (blkaddr == NULL_ADDR) {
- new_data_block(sbi, data_blk, &dn,
- CURSEG_WARM_DATA);
- blkaddr = dn.data_blkaddr;
- idirty |= dn.idirty;
- }
+ /* Read inode */
+ get_node_info(sbi, ino, &ni);
+ ASSERT(dev_read_block(inode, ni.blk_addr) >= 0);
+ ASSERT(!S_ISDIR(le16_to_cpu(inode->i.i_mode)));
+ ASSERT(!S_ISLNK(le16_to_cpu(inode->i.i_mode)));
+
+ /* Main loop for file blocks */
+ written_count = remained_blkentries = 0;
+ while (count > 0) {
+ if (remained_blkentries == 0) {
+ set_new_dnode(&dn, inode, NULL, ino);
+ get_dnode_of_data(sbi, &dn, F2FS_BYTES_TO_BLK(offset),
+ ALLOC_NODE);
+ idirty |= dn.idirty;
+ if (index_node)
+ free(index_node);
+ index_node = (dn.node_blk == dn.inode_blk) ?
+ NULL : dn.node_blk;
+ remained_blkentries = ADDRS_PER_PAGE(dn.node_blk);
+ }
+ ASSERT(remained_blkentries > 0);
- /* Copy data from buffer to file */
- ret = dev_read_block(data_blk, blkaddr);
- ASSERT(ret >= 0);
+ blkaddr = datablock_addr(dn.node_blk, dn.ofs_in_node);
+ if (blkaddr == NULL_ADDR || blkaddr == NEW_ADDR) {
+ new_data_block(sbi, blk_buffer, &dn, CURSEG_WARM_DATA);
+ blkaddr = dn.data_blkaddr;
+ }
- memcpy(data_blk + off_in_block, buffer, len_in_block);
+ off_in_blk = offset % BLOCK_SZ;
+ len_in_blk = BLOCK_SZ - off_in_blk;
+ if (len_in_blk > count)
+ len_in_blk = count;
+
+ /* Write data to single block. */
+ if (len_in_blk < BLOCK_SZ) {
+ ASSERT(dev_read_block(blk_buffer, blkaddr) >= 0);
+ memcpy(blk_buffer + off_in_blk, buffer, len_in_blk);
+ ASSERT(dev_write_block(blk_buffer, blkaddr) >= 0);
+ } else {
+ /* Direct write */
+ ASSERT(dev_write_block(buffer, blkaddr) >= 0);
+ }
- ret = dev_write_block(data_blk, blkaddr);
- ASSERT(ret >= 0);
+ offset += len_in_blk;
+ count -= len_in_blk;
+ buffer += len_in_blk;
+ written_count += len_in_blk;
- off_in_block = 0;
- len_already += len_in_block;
- if ((count - len_already) > (1 << F2FS_BLKSIZE_BITS))
- len_in_block = 1 << F2FS_BLKSIZE_BITS;
- else
- len_in_block = count - len_already;
- len--;
- start++;
- dn.ofs_in_node++;
- }
- /* Update the direct node */
- if (dn.ndirty) {
- ret = dev_write_block(dn.node_blk, dn.node_blkaddr);
- ASSERT(ret >= 0);
- }
+ dn.ofs_in_node++;
+ if ((--remained_blkentries == 0 || count == 0) && (dn.ndirty))
+ ASSERT(dev_write_block(dn.node_blk, dn.node_blkaddr) >= 0);
}
-
- /* Update the inode info */
- if (le64_to_cpu(inode->i.i_size) < offset + count) {
- inode->i.i_size = cpu_to_le64(offset + count);
+ if (offset > le64_to_cpu(inode->i.i_size)) {
+ inode->i.i_size = cpu_to_le64(offset);
idirty = 1;
}
-
if (idirty) {
ASSERT(inode == dn.inode_blk);
write_inode(ni.blk_addr, inode);
}
+ if (index_node)
+ free(index_node);
+ free(blk_buffer);
+
+ return written_count;
+}
+
+/* This function updates only inode->i.i_size */
+void f2fs_filesize_update(struct f2fs_sb_info *sbi, nid_t ino, u64 filesize)
+{
+ struct node_info ni;
+ struct f2fs_node *inode;
+
+ inode = calloc(BLOCK_SZ, 1);
+ ASSERT(inode);
+ get_node_info(sbi, ino, &ni);
+
+ ASSERT(dev_read_block(inode, ni.blk_addr) >= 0);
+ ASSERT(!S_ISDIR(le16_to_cpu(inode->i.i_mode)));
+ ASSERT(!S_ISLNK(le16_to_cpu(inode->i.i_mode)));
+
+ inode->i.i_size = cpu_to_le64(filesize);
- if (dn.node_blk && dn.node_blk != dn.inode_blk)
- free(dn.node_blk);
- free(data_blk);
+ write_inode(ni.blk_addr, inode);
free(inode);
}
@@ -221,7 +303,7 @@ int f2fs_build_file(struct f2fs_sb_info *sbi, struct dentry *de)
free(node_blk);
} else {
while ((n = read(fd, buffer, BLOCK_SZ)) > 0) {
- f2fs_write_block(sbi, de->ino, buffer, n, off);
+ f2fs_write(sbi, de->ino, buffer, n, off);
off += n;
}
}
--
2.14.0.rc1.383.gd1ce394fe2-goog
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH 3/4] mkfs.f2fs: support quota option in mkfs
2017-10-31 3:42 [PATCH 1/4] sload.f2fs: fix bugs in f2fs_write_block() Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 2/4] f2fs-tools: f2fs_read() and f2fs_filesize_update() are added Jaegeuk Kim
@ 2017-10-31 3:42 ` Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 4/4] fsck.f2fs: support quota Jaegeuk Kim
2 siblings, 0 replies; 4+ messages in thread
From: Jaegeuk Kim @ 2017-10-31 3:42 UTC (permalink / raw)
To: linux-f2fs-devel; +Cc: Hyojun Kim, Jaegeuk Kim
From: Hyojun Kim <hyojun@google.com>
This patch let mkfs to handle quota option and create quota files.
Signed-off-by: Hyojun Kim <hyojun@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@google.com>
---
include/f2fs_fs.h | 21 +++-
include/quota.h | 77 ++++++++++++++
mkfs/f2fs_format.c | 278 +++++++++++++++++++++++++++++++++++++++++++++---
mkfs/f2fs_format_main.c | 2 +
4 files changed, 363 insertions(+), 15 deletions(-)
create mode 100644 include/quota.h
diff --git a/include/f2fs_fs.h b/include/f2fs_fs.h
index 9f56388..d26b7cf 100644
--- a/include/f2fs_fs.h
+++ b/include/f2fs_fs.h
@@ -458,6 +458,13 @@ enum {
#define F2FS_NODE_INO(sbi) (sbi->node_ino_num)
#define F2FS_META_INO(sbi) (sbi->meta_ino_num)
+#define F2FS_QUOTA_INO 3
+#define F2FS_MAX_QUOTAS 3
+#define QUOTA_DATA(i) (2)
+#define QUOTA_INO(sb,t) (le32_to_cpu((sb)->qf_ino[t]))
+
+#define FS_IMMUTABLE_FL 0x00000010 /* Immutable file */
+
/* This flag is used by node and meta inodes, and by recovery */
#define GFP_F2FS_ZERO (GFP_NOFS | __GFP_ZERO)
@@ -478,6 +485,7 @@ enum {
#define F2FS_FEATURE_PRJQUOTA 0x0010
#define F2FS_FEATURE_INODE_CHKSUM 0x0020
#define F2FS_FEATURE_FLEXIBLE_INLINE_XATTR 0x0040
+#define F2FS_FEATURE_QUOTA_INO 0x0080
#define MAX_VOLUME_NAME 512
@@ -528,7 +536,8 @@ struct f2fs_super_block {
__u8 encryption_level; /* versioning level for encryption */
__u8 encrypt_pw_salt[16]; /* Salt used for string2key algorithm */
struct f2fs_device devs[MAX_DEVICES]; /* device list */
- __u8 reserved[327]; /* valid reserved region */
+ __le32 qf_ino[F2FS_MAX_QUOTAS]; /* quota inode numbers */
+ __u8 reserved[315]; /* valid reserved region */
} __attribute__((packed));
/*
@@ -1171,4 +1180,14 @@ static inline __le64 get_cp_crc(struct f2fs_checkpoint *cp)
return cpu_to_le64(cp_ver);
}
+static inline int is_qf_ino(struct f2fs_super_block *sb, nid_t ino)
+{
+ int i;
+
+ for (i = 0; i < F2FS_MAX_QUOTAS; i++)
+ if (sb->qf_ino[i] == ino)
+ return 1;
+ return 0;
+}
+
#endif /*__F2FS_FS_H */
diff --git a/include/quota.h b/include/quota.h
new file mode 100644
index 0000000..4c9f5f4
--- /dev/null
+++ b/include/quota.h
@@ -0,0 +1,77 @@
+/*
+ *
+ * Header file for disk format of new quotafile format
+ *
+ * Copied essential definitions and structures for mkfs.f2fs from quotaio.h
+ *
+ * Aditya Kali <adityakali@google.com>
+ * Jan Kara <jack@suse.cz>
+ * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
+ *
+ */
+#ifndef F2FS_QUOTA_H
+#define F2FS_QUOTA_H
+
+enum quota_type {
+ USRQUOTA = 0,
+ GRPQUOTA = 1,
+ PRJQUOTA = 2,
+ MAXQUOTAS = 3,
+};
+
+#if MAXQUOTAS > 32
+#error "cannot have more than 32 quota types to fit in qtype_bits"
+#endif
+
+#define QUOTA_USR_BIT (1 << USRQUOTA)
+#define QUOTA_GRP_BIT (1 << GRPQUOTA)
+#define QUOTA_PRJ_BIT (1 << PRJQUOTA)
+#define QUOTA_ALL_BIT (QUOTA_USR_BIT | QUOTA_GRP_BIT | QUOTA_PRJ_BIT)
+
+/*
+ * Definitions of magics and versions of current quota files
+ */
+#define INITQMAGICS {\
+ 0xd9c01f11, /* USRQUOTA */\
+ 0xd9c01927, /* GRPQUOTA */\
+ 0xd9c03f14 /* PRJQUOTA */\
+}
+
+#define V2_DQINFOOFF sizeof(struct v2_disk_dqheader) /* Offset of info header in file */
+
+#define MAX_IQ_TIME 604800 /* (7*24*60*60) 1 week */
+#define MAX_DQ_TIME 604800 /* (7*24*60*60) 1 week */
+
+#define QT_TREEOFF 1 /* Offset of tree in file in blocks */
+
+struct v2_disk_dqheader {
+ u_int32_t dqh_magic; /* Magic number identifying file */
+ u_int32_t dqh_version; /* File version */
+} __attribute__ ((packed));
+
+/* Header with type and version specific information */
+struct v2_disk_dqinfo {
+ u_int32_t dqi_bgrace; /* Time before block soft limit becomes hard limit */
+ u_int32_t dqi_igrace; /* Time before inode soft limit becomes hard limit */
+ u_int32_t dqi_flags; /* Flags for quotafile (DQF_*) */
+ u_int32_t dqi_blocks; /* Number of blocks in file */
+ u_int32_t dqi_free_blk; /* Number of first free block in the list */
+ u_int32_t dqi_free_entry; /* Number of block with at least one free entry */
+} __attribute__ ((packed));
+
+struct v2r1_disk_dqblk {
+ __le32 dqb_id; /* id this quota applies to */
+ __le32 dqb_pad;
+ __le64 dqb_ihardlimit; /* absolute limit on allocated inodes */
+ __le64 dqb_isoftlimit; /* preferred inode limit */
+ __le64 dqb_curinodes; /* current # allocated inodes */
+ __le64 dqb_bhardlimit; /* absolute limit on disk space
+ * (in QUOTABLOCK_SIZE) */
+ __le64 dqb_bsoftlimit; /* preferred limit on disk space
+ * (in QUOTABLOCK_SIZE) */
+ __le64 dqb_curspace; /* current space occupied (in bytes) */
+ __le64 dqb_btime; /* time limit for excessive disk use */
+ __le64 dqb_itime; /* time limit for excessive inode use */
+} __attribute__ ((packed));
+
+#endif
diff --git a/mkfs/f2fs_format.c b/mkfs/f2fs_format.c
index 8a821d3..c809225 100644
--- a/mkfs/f2fs_format.c
+++ b/mkfs/f2fs_format.c
@@ -19,6 +19,7 @@
#include <uuid/uuid.h>
#include "f2fs_fs.h"
+#include "quota.h"
#include "f2fs_format_utils.h"
extern struct f2fs_configuration c;
@@ -32,6 +33,8 @@ struct f2fs_checkpoint *cp;
#define last_zone(cur) ((cur - 1) * c.segs_per_zone)
#define last_section(cur) (cur + (c.secs_per_zone - 1) * c.segs_per_sec)
+static unsigned int quotatype_bits = 0;
+
const char *media_ext_lists[] = {
"jpg",
"gif",
@@ -153,6 +156,8 @@ static int f2fs_prepare_super_block(void)
u_int32_t sit_bitmap_size, max_sit_bitmap_size;
u_int32_t max_nat_bitmap_size, max_nat_segments;
u_int32_t total_zones;
+ u_int32_t next_ino;
+ enum quota_type qtype;
int i;
set_sb(magic, F2FS_SUPER_MAGIC);
@@ -382,6 +387,17 @@ static int f2fs_prepare_super_block(void)
set_sb(node_ino, 1);
set_sb(meta_ino, 2);
set_sb(root_ino, 3);
+ next_ino = 4;
+
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_QUOTA_INO)) {
+ quotatype_bits = QUOTA_USR_BIT | QUOTA_GRP_BIT;
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_PRJQUOTA))
+ quotatype_bits |= QUOTA_PRJ_BIT;
+ }
+
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++)
+ sb->qf_ino[qtype] =
+ ((1 << qtype) & quotatype_bits) ? next_ino++ : 0;
if (total_zones <= 6) {
MSG(1, "\tError: %d zones: Need more zones "
@@ -513,6 +529,9 @@ static int f2fs_write_check_point_pack(void)
char *cp_payload = NULL;
char *sum_compact, *sum_compact_p;
struct f2fs_summary *sum_entry;
+ enum quota_type qtype;
+ u_int32_t quota_inum, quota_dnum;
+ int off;
int ret = -1;
cp = calloc(F2FS_BLKSIZE, 1);
@@ -562,9 +581,16 @@ static int f2fs_write_check_point_pack(void)
set_cp(cur_data_segno[i], 0xffffffff);
}
- set_cp(cur_node_blkoff[0], 1);
- set_cp(cur_data_blkoff[0], 1);
- set_cp(valid_block_count, 2);
+ quota_inum = quota_dnum = 0;
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++)
+ if (sb->qf_ino[qtype]) {
+ quota_inum++;
+ quota_dnum += QUOTA_DATA(qtype);
+ }
+
+ set_cp(cur_node_blkoff[0], 1 + quota_inum);
+ set_cp(cur_data_blkoff[0], 1 + quota_dnum);
+ set_cp(valid_block_count, 2 + quota_inum + quota_dnum);
set_cp(rsvd_segment_count, c.reserved_segments);
set_cp(overprov_segment_count, (get_sb(segment_count_main) -
get_cp(rsvd_segment_count)) *
@@ -593,9 +619,9 @@ static int f2fs_write_check_point_pack(void)
set_cp(ckpt_flags, flags);
set_cp(cp_pack_start_sum, 1 + get_sb(cp_payload));
- set_cp(valid_node_count, 1);
- set_cp(valid_inode_count, 1);
- set_cp(next_free_nid, get_sb(root_ino) + 1);
+ set_cp(valid_node_count, 1 + quota_inum);
+ set_cp(valid_inode_count, 1 + quota_inum);
+ set_cp(next_free_nid, get_sb(root_ino) + 1 + quota_inum);
set_cp(sit_ver_bitmap_bytesize, ((get_sb(segment_count_sit) / 2) <<
get_sb(log_blocks_per_seg)) / 8);
@@ -653,7 +679,7 @@ static int f2fs_write_check_point_pack(void)
SET_SUM_TYPE((&sum->footer), SUM_TYPE_DATA);
journal = &sum->journal;
- journal->n_nats = cpu_to_le16(1);
+ journal->n_nats = cpu_to_le16(1 + quota_inum);
journal->nat_j.entries[0].nid = sb->root_ino;
journal->nat_j.entries[0].ne.version = 0;
journal->nat_j.entries[0].ne.ino = sb->root_ino;
@@ -661,6 +687,19 @@ static int f2fs_write_check_point_pack(void)
get_sb(main_blkaddr) +
get_cp(cur_node_segno[0]) * c.blks_per_seg);
+ for (qtype = 0, i = 1; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (sb->qf_ino[qtype] == 0)
+ continue;
+ journal->nat_j.entries[i].nid = sb->qf_ino[qtype];
+ journal->nat_j.entries[i].ne.version = 0;
+ journal->nat_j.entries[i].ne.ino = sb->qf_ino[qtype];
+ journal->nat_j.entries[i].ne.block_addr = cpu_to_le32(
+ get_sb(main_blkaddr) +
+ get_cp(cur_node_segno[0]) *
+ c.blks_per_seg + i);
+ i++;
+ }
+
memcpy(sum_compact_p, &journal->n_nats, SUM_JOURNAL_SIZE);
sum_compact_p += SUM_JOURNAL_SIZE;
@@ -669,8 +708,11 @@ static int f2fs_write_check_point_pack(void)
journal->n_sits = cpu_to_le16(6);
journal->sit_j.entries[0].segno = cp->cur_node_segno[0];
journal->sit_j.entries[0].se.vblocks =
- cpu_to_le16((CURSEG_HOT_NODE << 10) | 1);
+ cpu_to_le16((CURSEG_HOT_NODE << 10) |
+ (1 + quota_inum));
f2fs_set_bit(0, (char *)journal->sit_j.entries[0].se.valid_map);
+ for (i = 1; i <= quota_inum; i++)
+ f2fs_set_bit(i, (char *)journal->sit_j.entries[0].se.valid_map);
journal->sit_j.entries[1].segno = cp->cur_node_segno[1];
journal->sit_j.entries[1].se.vblocks =
cpu_to_le16((CURSEG_WARM_NODE << 10));
@@ -681,8 +723,12 @@ static int f2fs_write_check_point_pack(void)
/* data sit for root */
journal->sit_j.entries[3].segno = cp->cur_data_segno[0];
journal->sit_j.entries[3].se.vblocks =
- cpu_to_le16((CURSEG_HOT_DATA << 10) | 1);
+ cpu_to_le16((CURSEG_HOT_DATA << 10) |
+ (1 + quota_dnum));
f2fs_set_bit(0, (char *)journal->sit_j.entries[3].se.valid_map);
+ for (i = 1; i <= quota_dnum; i++)
+ f2fs_set_bit(i, (char *)journal->sit_j.entries[3].se.valid_map);
+
journal->sit_j.entries[4].segno = cp->cur_data_segno[1];
journal->sit_j.entries[4].se.vblocks =
cpu_to_le16((CURSEG_WARM_DATA << 10));
@@ -697,6 +743,20 @@ static int f2fs_write_check_point_pack(void)
sum_entry = (struct f2fs_summary *)sum_compact_p;
sum_entry->nid = sb->root_ino;
sum_entry->ofs_in_node = 0;
+
+ off = 1;
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (sb->qf_ino[qtype] == 0)
+ continue;
+ int j;
+
+ for (j = 0; j < QUOTA_DATA(qtype); j++) {
+ (sum_entry + off + j)->nid = sb->qf_ino[qtype];
+ (sum_entry + off + j)->ofs_in_node = j;
+ }
+ off += QUOTA_DATA(qtype);
+ }
+
/* warm data summary, nothing to do */
/* cold data summary, nothing to do */
@@ -714,6 +774,13 @@ static int f2fs_write_check_point_pack(void)
sum->entries[0].nid = sb->root_ino;
sum->entries[0].ofs_in_node = 0;
+ for (qtype = i = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (sb->qf_ino[qtype] == 0)
+ continue;
+ sum->entries[1 + i].nid = sb->qf_ino[qtype];
+ sum->entries[1 + i].ofs_in_node = 0;
+ i++;
+ }
cp_seg_blk++;
DBG(1, "\tWriting Segment summary for HOT_NODE, at offset 0x%08"PRIx64"\n",
@@ -855,12 +922,19 @@ static int f2fs_write_super_block(void)
static int discard_obsolete_dnode(struct f2fs_node *raw_node, u_int64_t offset)
{
u_int64_t next_blkaddr = 0;
- u_int64_t root_inode_pos = get_sb(main_blkaddr);
u64 end_blkaddr = (get_sb(segment_count_main) <<
get_sb(log_blocks_per_seg)) + get_sb(main_blkaddr);
+ u_int64_t start_inode_pos = get_sb(main_blkaddr);
+ u_int64_t last_inode_pos;
+ enum quota_type qtype;
+ u_int32_t quota_inum = 0;
+
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++)
+ if (sb->qf_ino[qtype]) quota_inum++;
/* only root inode was written before truncating dnodes */
- root_inode_pos += c.cur_seg[CURSEG_HOT_NODE] * c.blks_per_seg;
+ last_inode_pos = start_inode_pos +
+ c.cur_seg[CURSEG_HOT_NODE] * c.blks_per_seg + quota_inum;
if (c.zoned_mode)
return 0;
@@ -883,7 +957,7 @@ static int discard_obsolete_dnode(struct f2fs_node *raw_node, u_int64_t offset)
}
offset = next_blkaddr;
/* should avoid recursive chain due to stale data */
- if (offset == root_inode_pos)
+ if (offset >= start_inode_pos || offset <= last_inode_pos)
break;
} while (1);
@@ -963,7 +1037,6 @@ static int f2fs_write_root_inode(void)
c.blks_per_seg, main_area_node_seg_blk_offset);
if (dev_write_block(raw_node, main_area_node_seg_blk_offset)) {
MSG(1, "\tError: While writing the raw_node to disk!!!\n");
- free(raw_node);
return -1;
}
@@ -974,10 +1047,161 @@ static int f2fs_write_root_inode(void)
#ifndef WITH_ANDROID
if (discard_obsolete_dnode(raw_node, main_area_node_seg_blk_offset)) {
- free(raw_node);
return -1;
}
#endif
+ return 0;
+}
+
+static int f2fs_write_default_quota(int qtype, unsigned int blkaddr)
+{
+ char *filebuf = calloc(F2FS_BLKSIZE, 2);
+ int file_magics[] = INITQMAGICS;
+ struct v2_disk_dqheader ddqheader;
+ struct v2_disk_dqinfo ddqinfo;
+ struct v2r1_disk_dqblk dqblk;
+
+ if (filebuf == NULL) {
+ MSG(1, "\tError: Calloc Failed for filebuf!!!\n");
+ return -1;
+ }
+
+ /* Write basic quota header */
+ ddqheader.dqh_magic = cpu_to_le32(file_magics[qtype]);
+ /* only support QF_VFSV1 */
+ ddqheader.dqh_version = cpu_to_le32(1);
+
+ memcpy(filebuf, &ddqheader, sizeof(ddqheader));
+
+ /* Fill Initial quota file content */
+ ddqinfo.dqi_bgrace = cpu_to_le32(MAX_DQ_TIME);
+ ddqinfo.dqi_igrace = cpu_to_le32(MAX_IQ_TIME);
+ ddqinfo.dqi_flags = cpu_to_le32(0);
+ ddqinfo.dqi_blocks = cpu_to_le32(QT_TREEOFF + 5);
+ ddqinfo.dqi_free_blk = cpu_to_le32(0);
+ ddqinfo.dqi_free_entry = cpu_to_le32(5);
+
+ memcpy(filebuf + V2_DQINFOOFF, &ddqinfo, sizeof(ddqinfo));
+
+ filebuf[1024] = 2;
+ filebuf[2048] = 3;
+ filebuf[3072] = 4;
+ filebuf[4096] = 5;
+
+ filebuf[5120 + 8] = 1;
+
+ dqblk.dqb_id = cpu_to_le32(0);
+ dqblk.dqb_pad = cpu_to_le32(0);
+ dqblk.dqb_ihardlimit = cpu_to_le64(0);
+ dqblk.dqb_isoftlimit = cpu_to_le64(0);
+ dqblk.dqb_curinodes = cpu_to_le64(1);
+ dqblk.dqb_bhardlimit = cpu_to_le64(0);
+ dqblk.dqb_bsoftlimit = cpu_to_le64(0);
+ dqblk.dqb_curspace = cpu_to_le64(4096);
+ dqblk.dqb_btime = cpu_to_le64(0);
+ dqblk.dqb_itime = cpu_to_le64(0);
+
+ memcpy(filebuf + 5136, &dqblk, sizeof(struct v2r1_disk_dqblk));
+
+ /* Write two blocks */
+ if (dev_write_block(filebuf, blkaddr) ||
+ dev_write_block(filebuf + F2FS_BLKSIZE, blkaddr + 1)) {
+ MSG(1, "\tError: While writing the quota_blk to disk!!!\n");
+ free(filebuf);
+ return -1;
+ }
+
+ free(filebuf);
+ return 0;
+}
+
+static int f2fs_write_qf_inode(int qtype)
+{
+ struct f2fs_node *raw_node = NULL;
+ u_int64_t data_blk_nor;
+ u_int64_t main_area_node_seg_blk_offset = 0;
+ int i;
+
+ raw_node = calloc(F2FS_BLKSIZE, 1);
+ if (raw_node == NULL) {
+ MSG(1, "\tError: Calloc Failed for raw_node!!!\n");
+ return -1;
+ }
+
+ raw_node->footer.nid = sb->qf_ino[qtype];
+ raw_node->footer.ino = sb->qf_ino[qtype];
+ raw_node->footer.cp_ver = cpu_to_le64(1);
+ raw_node->footer.next_blkaddr = cpu_to_le32(
+ get_sb(main_blkaddr) +
+ c.cur_seg[CURSEG_HOT_NODE] *
+ c.blks_per_seg + 1 + qtype + 1);
+
+ raw_node->i.i_mode = cpu_to_le16(0x8180);
+ raw_node->i.i_links = cpu_to_le32(1);
+ raw_node->i.i_uid = cpu_to_le32(getuid());
+ raw_node->i.i_gid = cpu_to_le32(getgid());
+
+ raw_node->i.i_size = cpu_to_le64(1024 * 6); /* Hard coded */
+ raw_node->i.i_blocks = cpu_to_le64(1 + QUOTA_DATA(qtype));
+
+ raw_node->i.i_atime = cpu_to_le32(time(NULL));
+ raw_node->i.i_atime_nsec = 0;
+ raw_node->i.i_ctime = cpu_to_le32(time(NULL));
+ raw_node->i.i_ctime_nsec = 0;
+ raw_node->i.i_mtime = cpu_to_le32(time(NULL));
+ raw_node->i.i_mtime_nsec = 0;
+ raw_node->i.i_generation = 0;
+ raw_node->i.i_xattr_nid = 0;
+ raw_node->i.i_flags = FS_IMMUTABLE_FL;
+ raw_node->i.i_current_depth = cpu_to_le32(1);
+ raw_node->i.i_dir_level = DEF_DIR_LEVEL;
+
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_EXTRA_ATTR)) {
+ raw_node->i.i_inline = F2FS_EXTRA_ATTR;
+ raw_node->i.i_extra_isize =
+ cpu_to_le16(F2FS_TOTAL_EXTRA_ATTR_SIZE);
+ }
+
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_PRJQUOTA))
+ raw_node->i.i_projid = cpu_to_le32(F2FS_DEF_PROJID);
+
+ data_blk_nor = get_sb(main_blkaddr) +
+ c.cur_seg[CURSEG_HOT_DATA] * c.blks_per_seg + 1;
+
+ for (i = 0; i < qtype; i++)
+ if (sb->qf_ino[i])
+ data_blk_nor += QUOTA_DATA(i);
+
+ /* write two blocks */
+ if (f2fs_write_default_quota(qtype, data_blk_nor)) {
+ free(raw_node);
+ return -1;
+ }
+
+ for (i = 0; i < QUOTA_DATA(qtype); i++)
+ raw_node->i.i_addr[get_extra_isize(raw_node) + i] =
+ cpu_to_le32(data_blk_nor + i);
+ raw_node->i.i_ext.fofs = 0;
+ raw_node->i.i_ext.blk_addr = 0;
+ raw_node->i.i_ext.len = 0;
+
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_INODE_CHKSUM))
+ raw_node->i.i_inode_checksum =
+ cpu_to_le32(f2fs_inode_chksum(raw_node));
+
+ main_area_node_seg_blk_offset = get_sb(main_blkaddr);
+ main_area_node_seg_blk_offset += c.cur_seg[CURSEG_HOT_NODE] *
+ c.blks_per_seg + qtype + 1;
+
+ DBG(1, "\tWriting quota inode (hot node), %x %x %x at offset 0x%08"PRIu64"\n",
+ get_sb(main_blkaddr),
+ c.cur_seg[CURSEG_HOT_NODE],
+ c.blks_per_seg, main_area_node_seg_blk_offset);
+ if (dev_write_block(raw_node, main_area_node_seg_blk_offset)) {
+ MSG(1, "\tError: While writing the raw_node to disk!!!\n");
+ free(raw_node);
+ return -1;
+ }
free(raw_node);
return 0;
@@ -987,6 +1211,8 @@ static int f2fs_update_nat_root(void)
{
struct f2fs_nat_block *nat_blk = NULL;
u_int64_t nat_seg_blk_offset = 0;
+ enum quota_type qtype;
+ int i;
nat_blk = calloc(F2FS_BLKSIZE, 1);
if(nat_blk == NULL) {
@@ -994,6 +1220,18 @@ static int f2fs_update_nat_root(void)
return -1;
}
+ /* update quota */
+ for (qtype = i = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (sb->qf_ino[qtype] == 0)
+ continue;
+ nat_blk->entries[sb->qf_ino[qtype]].block_addr =
+ cpu_to_le32(get_sb(main_blkaddr) +
+ c.cur_seg[CURSEG_HOT_NODE] *
+ c.blks_per_seg + i + 1);
+ nat_blk->entries[sb->qf_ino[qtype]].ino = sb->qf_ino[qtype];
+ i++;
+ }
+
/* update root */
nat_blk->entries[get_sb(root_ino)].block_addr = cpu_to_le32(
get_sb(main_blkaddr) +
@@ -1048,6 +1286,7 @@ static int f2fs_add_default_dentry_root(void)
/* bitmap for . and .. */
test_and_set_bit_le(0, dent_blk->dentry_bitmap);
test_and_set_bit_le(1, dent_blk->dentry_bitmap);
+
data_blk_offset = get_sb(main_blkaddr);
data_blk_offset += c.cur_seg[CURSEG_HOT_DATA] *
c.blks_per_seg;
@@ -1066,6 +1305,7 @@ static int f2fs_add_default_dentry_root(void)
static int f2fs_create_root_dir(void)
{
+ enum quota_type qtype;
int err = 0;
err = f2fs_write_root_inode();
@@ -1074,6 +1314,16 @@ static int f2fs_create_root_dir(void)
goto exit;
}
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (sb->qf_ino[qtype] == 0)
+ continue;
+ err = f2fs_write_qf_inode(qtype);
+ if (err < 0) {
+ MSG(1, "\tError: Failed to write quota inode!!!\n");
+ goto exit;
+ }
+ }
+
err = f2fs_update_nat_root();
if (err < 0) {
MSG(1, "\tError: Failed to update NAT for root!!!\n");
diff --git a/mkfs/f2fs_format_main.c b/mkfs/f2fs_format_main.c
index ef62777..50735d3 100644
--- a/mkfs/f2fs_format_main.c
+++ b/mkfs/f2fs_format_main.c
@@ -88,6 +88,8 @@ static void parse_feature(const char *features)
c.feature |= cpu_to_le32(F2FS_FEATURE_INODE_CHKSUM);
} else if (!strcmp(features, "flexible_inline_xattr")) {
c.feature |= cpu_to_le32(F2FS_FEATURE_FLEXIBLE_INLINE_XATTR);
+ } else if (!strcmp(features, "quota")) {
+ c.feature |= cpu_to_le32(F2FS_FEATURE_QUOTA_INO);
} else {
MSG(0, "Error: Wrong features\n");
mkfs_usage();
--
2.14.0.rc1.383.gd1ce394fe2-goog
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH 4/4] fsck.f2fs: support quota
2017-10-31 3:42 [PATCH 1/4] sload.f2fs: fix bugs in f2fs_write_block() Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 2/4] f2fs-tools: f2fs_read() and f2fs_filesize_update() are added Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 3/4] mkfs.f2fs: support quota option in mkfs Jaegeuk Kim
@ 2017-10-31 3:42 ` Jaegeuk Kim
2 siblings, 0 replies; 4+ messages in thread
From: Jaegeuk Kim @ 2017-10-31 3:42 UTC (permalink / raw)
To: linux-f2fs-devel; +Cc: Hyojun Kim, Jaegeuk Kim
From: Hyojun Kim <hyojun@google.com>
This patch let fsck to check and fix quota file contents.
Signed-off-by: Hyojun Kim <hyojun@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@google.com>
---
fsck/Makefile.am | 3 +-
fsck/common.h | 30 +
fsck/dict.c | 1501 +++++++++++++++++++++++++++++++++++++++++++++++++++
fsck/dict.h | 144 +++++
fsck/dqblk_v2.h | 31 ++
fsck/fsck.c | 105 +++-
fsck/fsck.h | 10 +
fsck/main.c | 18 +-
fsck/mkquota.c | 403 ++++++++++++++
fsck/mount.c | 15 +-
fsck/quotaio.c | 221 ++++++++
fsck/quotaio.h | 255 +++++++++
fsck/quotaio_tree.c | 679 +++++++++++++++++++++++
fsck/quotaio_tree.h | 66 +++
fsck/quotaio_v2.c | 284 ++++++++++
fsck/quotaio_v2.h | 54 ++
fsck/segment.c | 22 +-
include/f2fs_fs.h | 19 +
mkfs/f2fs_format.c | 10 +-
19 files changed, 3852 insertions(+), 18 deletions(-)
create mode 100644 fsck/common.h
create mode 100644 fsck/dict.c
create mode 100644 fsck/dict.h
create mode 100644 fsck/dqblk_v2.h
create mode 100644 fsck/mkquota.c
create mode 100644 fsck/quotaio.c
create mode 100644 fsck/quotaio.h
create mode 100644 fsck/quotaio_tree.c
create mode 100644 fsck/quotaio_tree.h
create mode 100644 fsck/quotaio_v2.c
create mode 100644 fsck/quotaio_v2.h
diff --git a/fsck/Makefile.am b/fsck/Makefile.am
index 7abcd00..cf0f7d1 100644
--- a/fsck/Makefile.am
+++ b/fsck/Makefile.am
@@ -5,7 +5,8 @@ AM_CFLAGS = -Wall
sbin_PROGRAMS = fsck.f2fs
fsck_f2fs_SOURCES = main.c fsck.c dump.c mount.c defrag.c f2fs.h fsck.h $(top_srcdir)/include/f2fs_fs.h \
resize.c \
- node.c segment.c dir.c sload.c xattr.c
+ node.c segment.c dir.c sload.c xattr.c \
+ dict.c mkquota.c quotaio.c quotaio_tree.c quotaio_v2.c
fsck_f2fs_LDADD = ${libselinux_LIBS} ${libuuid_LIBS} $(top_builddir)/lib/libf2fs.la
install-data-hook:
diff --git a/fsck/common.h b/fsck/common.h
new file mode 100644
index 0000000..19a6ecc
--- /dev/null
+++ b/fsck/common.h
@@ -0,0 +1,30 @@
+/**
+ *
+ * Various things common for all utilities
+ *
+ */
+
+#ifndef __QUOTA_COMMON_H__
+#define __QUOTA_COMMON_H__
+
+#undef DEBUG_QUOTA
+
+#ifndef __attribute__
+# if !defined __GNUC__ || __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+# define __attribute__(x)
+# endif
+#endif
+
+#define log_err(format, arg ...) \
+ fprintf(stderr, "[ERROR] %s:%d:%s:: " format "\n", \
+ __FILE__, __LINE__, __func__, ## arg)
+
+#ifdef DEBUG_QUOTA
+# define log_debug(format, arg ...) \
+ fprintf(stderr, "[DEBUG] %s:%d:%s:: " format "\n", \
+ __FILE__, __LINE__, __func__, ## arg)
+#else
+# define log_debug(...)
+#endif
+
+#endif /* __QUOTA_COMMON_H__ */
diff --git a/fsck/dict.c b/fsck/dict.c
new file mode 100644
index 0000000..bb7600c
--- /dev/null
+++ b/fsck/dict.c
@@ -0,0 +1,1501 @@
+/*
+ * Dictionary Abstract Data Type
+ * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
+ *
+ * Free Software License:
+ *
+ * All rights are reserved by the author, with the following exceptions:
+ * Permission is granted to freely reproduce and distribute this software,
+ * possibly in exchange for a fee, provided that this copyright notice appears
+ * intact. Permission is also granted to adapt this software to produce
+ * derivative works, as long as the modified versions carry this copyright
+ * notice and additional notices stating that the work has been modified.
+ * This source code may be translated into executable form and incorporated
+ * into proprietary software; there is no requirement for such software to
+ * contain a copyright notice related to this source.
+ *
+ * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $
+ * $Name: kazlib_1_20 $
+ */
+
+#define DICT_NODEBUG
+
+#include "config.h"
+#include <stdlib.h>
+#include <stddef.h>
+#ifdef DICT_NODEBUG
+#define dict_assert(x)
+#else
+#include <assert.h>
+#define dict_assert(x) assert(x)
+#endif
+#define DICT_IMPLEMENTATION
+#include "dict.h"
+#include <f2fs_fs.h>
+
+#ifdef KAZLIB_RCSID
+static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $";
+#endif
+
+/*
+ * These macros provide short convenient names for structure members,
+ * which are embellished with dict_ prefixes so that they are
+ * properly confined to the documented namespace. It's legal for a
+ * program which uses dict to define, for instance, a macro called ``parent''.
+ * Such a macro would interfere with the dnode_t struct definition.
+ * In general, highly portable and reusable C modules which expose their
+ * structures need to confine structure member names to well-defined spaces.
+ * The resulting identifiers aren't necessarily convenient to use, nor
+ * readable, in the implementation, however!
+ */
+
+#define left dict_left
+#define right dict_right
+#define parent dict_parent
+#define color dict_color
+#define key dict_key
+#define data dict_data
+
+#define nilnode dict_nilnode
+#define nodecount dict_nodecount
+#define maxcount dict_maxcount
+#define compare dict_compare
+#define allocnode dict_allocnode
+#define freenode dict_freenode
+#define context dict_context
+#define dupes dict_dupes
+
+#define dictptr dict_dictptr
+
+#define dict_root(D) ((D)->nilnode.left)
+#define dict_nil(D) (&(D)->nilnode)
+#define DICT_DEPTH_MAX 64
+
+static dnode_t *dnode_alloc(void *context);
+static void dnode_free(dnode_t *node, void *context);
+
+/*
+ * Perform a ``left rotation'' adjustment on the tree. The given node P and
+ * its right child C are rearranged so that the P instead becomes the left
+ * child of C. The left subtree of C is inherited as the new right subtree
+ * for P. The ordering of the keys within the tree is thus preserved.
+ */
+static void rotate_left(dnode_t *upper)
+{
+ dnode_t *lower, *lowleft, *upparent;
+
+ lower = upper->right;
+ upper->right = lowleft = lower->left;
+ lowleft->parent = upper;
+
+ lower->parent = upparent = upper->parent;
+
+ /* don't need to check for root node here because root->parent is
+ the sentinel nil node, and root->parent->left points back to root */
+
+ if (upper == upparent->left) {
+ upparent->left = lower;
+ } else {
+ dict_assert(upper == upparent->right);
+ upparent->right = lower;
+ }
+
+ lower->left = upper;
+ upper->parent = lower;
+}
+
+/*
+ * This operation is the ``mirror'' image of rotate_left. It is
+ * the same procedure, but with left and right interchanged.
+ */
+static void rotate_right(dnode_t *upper)
+{
+ dnode_t *lower, *lowright, *upparent;
+
+ lower = upper->left;
+ upper->left = lowright = lower->right;
+ lowright->parent = upper;
+
+ lower->parent = upparent = upper->parent;
+
+ if (upper == upparent->right) {
+ upparent->right = lower;
+ } else {
+ dict_assert(upper == upparent->left);
+ upparent->left = lower;
+ }
+
+ lower->right = upper;
+ upper->parent = lower;
+}
+
+/*
+ * Do a postorder traversal of the tree rooted at the specified
+ * node and free everything under it. Used by dict_free().
+ */
+static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
+{
+ if (node == nil)
+ return;
+ free_nodes(dict, node->left, nil);
+ free_nodes(dict, node->right, nil);
+ dict->freenode(node, dict->context);
+}
+
+/*
+ * This procedure performs a verification that the given subtree is a binary
+ * search tree. It performs an inorder traversal of the tree using the
+ * dict_next() successor function, verifying that the key of each node is
+ * strictly lower than that of its successor, if duplicates are not allowed,
+ * or lower or equal if duplicates are allowed. This function is used for
+ * debugging purposes.
+ */
+#ifndef DICT_NODEBUG
+static int verify_bintree(dict_t *dict)
+{
+ dnode_t *first, *next;
+
+ first = dict_first(dict);
+
+ if (dict->dupes) {
+ while (first && (next = dict_next(dict, first))) {
+ if (dict->compare(first->key, next->key) > 0)
+ return 0;
+ first = next;
+ }
+ } else {
+ while (first && (next = dict_next(dict, first))) {
+ if (dict->compare(first->key, next->key) >= 0)
+ return 0;
+ first = next;
+ }
+ }
+ return 1;
+}
+
+/*
+ * This function recursively verifies that the given binary subtree satisfies
+ * three of the red black properties. It checks that every red node has only
+ * black children. It makes sure that each node is either red or black. And it
+ * checks that every path has the same count of black nodes from root to leaf.
+ * It returns the blackheight of the given subtree; this allows blackheights to
+ * be computed recursively and compared for left and right siblings for
+ * mismatches. It does not check for every nil node being black, because there
+ * is only one sentinel nil node. The return value of this function is the
+ * black height of the subtree rooted at the node ``root'', or zero if the
+ * subtree is not red-black.
+ */
+static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
+{
+ unsigned height_left, height_right;
+
+ if (root != nil) {
+ height_left = verify_redblack(nil, root->left);
+ height_right = verify_redblack(nil, root->right);
+ if (height_left == 0 || height_right == 0)
+ return 0;
+ if (height_left != height_right)
+ return 0;
+ if (root->color == dnode_red) {
+ if (root->left->color != dnode_black)
+ return 0;
+ if (root->right->color != dnode_black)
+ return 0;
+ return height_left;
+ }
+ if (root->color != dnode_black)
+ return 0;
+ return height_left + 1;
+ }
+ return 1;
+}
+
+/*
+ * Compute the actual count of nodes by traversing the tree and
+ * return it. This could be compared against the stored count to
+ * detect a mismatch.
+ */
+static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
+{
+ if (root == nil)
+ return 0;
+ else
+ return 1 + verify_node_count(nil, root->left)
+ + verify_node_count(nil, root->right);
+}
+#endif
+
+/*
+ * Verify that the tree contains the given node. This is done by
+ * traversing all of the nodes and comparing their pointers to the
+ * given pointer. Returns 1 if the node is found, otherwise
+ * returns zero. It is intended for debugging purposes.
+ */
+static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
+{
+ if (root != nil) {
+ return root == node
+ || verify_dict_has_node(nil, root->left, node)
+ || verify_dict_has_node(nil, root->right, node);
+ }
+ return 0;
+}
+
+#ifdef FSCK_NOTUSED
+/*
+ * Dynamically allocate and initialize a dictionary object.
+ */
+dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp)
+{
+ dict_t *new = malloc(sizeof *new);
+
+ if (new) {
+ new->compare = comp;
+ new->allocnode = dnode_alloc;
+ new->freenode = dnode_free;
+ new->context = NULL;
+ new->nodecount = 0;
+ new->maxcount = maxcount;
+ new->nilnode.left = &new->nilnode;
+ new->nilnode.right = &new->nilnode;
+ new->nilnode.parent = &new->nilnode;
+ new->nilnode.color = dnode_black;
+ new->dupes = 0;
+ }
+ return new;
+}
+#endif /* FSCK_NOTUSED */
+
+/*
+ * Select a different set of node allocator routines.
+ */
+void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
+ dnode_free_t fr, void *context)
+{
+ dict_assert(dict_count(dict) == 0);
+ dict_assert((al == NULL && fr == NULL) || (al != NULL && fr != NULL));
+
+ dict->allocnode = al ? al : dnode_alloc;
+ dict->freenode = fr ? fr : dnode_free;
+ dict->context = context;
+}
+
+#ifdef FSCK_NOTUSED
+/*
+ * Free a dynamically allocated dictionary object. Removing the nodes
+ * from the tree before deleting it is required.
+ */
+void dict_destroy(dict_t *dict)
+{
+ dict_assert(dict_isempty(dict));
+ free(dict);
+}
+#endif
+
+/*
+ * Free all the nodes in the dictionary by using the dictionary's
+ * installed free routine. The dictionary is emptied.
+ */
+void dict_free_nodes(dict_t *dict)
+{
+ dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
+ free_nodes(dict, root, nil);
+ dict->nodecount = 0;
+ dict->nilnode.left = &dict->nilnode;
+ dict->nilnode.right = &dict->nilnode;
+}
+
+#ifdef FSCK_NOTUSED
+/*
+ * Obsolescent function, equivalent to dict_free_nodes
+ */
+void dict_free(dict_t *dict)
+{
+#ifdef KAZLIB_OBSOLESCENT_DEBUG
+ dict_assert("call to obsolescent function dict_free()" && 0);
+#endif
+ dict_free_nodes(dict);
+}
+#endif
+
+/*
+ * Initialize a user-supplied dictionary object.
+ */
+dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
+{
+ dict->compare = comp;
+ dict->allocnode = dnode_alloc;
+ dict->freenode = dnode_free;
+ dict->context = NULL;
+ dict->nodecount = 0;
+ dict->maxcount = maxcount;
+ dict->nilnode.left = &dict->nilnode;
+ dict->nilnode.right = &dict->nilnode;
+ dict->nilnode.parent = &dict->nilnode;
+ dict->nilnode.color = dnode_black;
+ dict->dupes = 0;
+ return dict;
+}
+
+#ifdef FSCK_NOTUSED
+/*
+ * Initialize a dictionary in the likeness of another dictionary
+ */
+void dict_init_like(dict_t *dict, const dict_t *template)
+{
+ dict->compare = template->compare;
+ dict->allocnode = template->allocnode;
+ dict->freenode = template->freenode;
+ dict->context = template->context;
+ dict->nodecount = 0;
+ dict->maxcount = template->maxcount;
+ dict->nilnode.left = &dict->nilnode;
+ dict->nilnode.right = &dict->nilnode;
+ dict->nilnode.parent = &dict->nilnode;
+ dict->nilnode.color = dnode_black;
+ dict->dupes = template->dupes;
+
+ dict_assert(dict_similar(dict, template));
+}
+
+/*
+ * Remove all nodes from the dictionary (without freeing them in any way).
+ */
+static void dict_clear(dict_t *dict)
+{
+ dict->nodecount = 0;
+ dict->nilnode.left = &dict->nilnode;
+ dict->nilnode.right = &dict->nilnode;
+ dict->nilnode.parent = &dict->nilnode;
+ dict_assert(dict->nilnode.color == dnode_black);
+}
+#endif /* FSCK_NOTUSED */
+
+/*
+ * Verify the integrity of the dictionary structure. This is provided for
+ * debugging purposes, and should be placed in assert statements. Just because
+ * this function succeeds doesn't mean that the tree is not corrupt. Certain
+ * corruptions in the tree may simply cause undefined behavior.
+ */
+#ifndef DICT_NODEBUG
+int dict_verify(dict_t *dict)
+{
+ dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
+
+ /* check that the sentinel node and root node are black */
+ if (root->color != dnode_black)
+ return 0;
+ if (nil->color != dnode_black)
+ return 0;
+ if (nil->right != nil)
+ return 0;
+ /* nil->left is the root node; check that its parent pointer is nil */
+ if (nil->left->parent != nil)
+ return 0;
+ /* perform a weak test that the tree is a binary search tree */
+ if (!verify_bintree(dict))
+ return 0;
+ /* verify that the tree is a red-black tree */
+ if (!verify_redblack(nil, root))
+ return 0;
+ if (verify_node_count(nil, root) != dict_count(dict))
+ return 0;
+ return 1;
+}
+#endif /* DICT_NODEBUG */
+
+#ifdef FSCK_NOTUSED
+/*
+ * Determine whether two dictionaries are similar: have the same comparison and
+ * allocator functions, and same status as to whether duplicates are allowed.
+ */
+int dict_similar(const dict_t *left, const dict_t *right)
+{
+ if (left->compare != right->compare)
+ return 0;
+
+ if (left->allocnode != right->allocnode)
+ return 0;
+
+ if (left->freenode != right->freenode)
+ return 0;
+
+ if (left->context != right->context)
+ return 0;
+
+ if (left->dupes != right->dupes)
+ return 0;
+
+ return 1;
+}
+#endif /* FSCK_NOTUSED */
+
+/*
+ * Locate a node in the dictionary having the given key.
+ * If the node is not found, a null a pointer is returned (rather than
+ * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
+ * located node is returned.
+ */
+dnode_t *dict_lookup(dict_t *dict, const void *key)
+{
+ dnode_t *root = dict_root(dict);
+ dnode_t *nil = dict_nil(dict);
+ dnode_t *saved;
+ int result;
+
+ /* simple binary search adapted for trees that contain duplicate keys */
+
+ while (root != nil) {
+ result = dict->compare(key, root->key);
+ if (result < 0)
+ root = root->left;
+ else if (result > 0)
+ root = root->right;
+ else {
+ if (!dict->dupes) { /* no duplicates, return match */
+ return root;
+ } else { /* could be dupes, find leftmost one */
+ do {
+ saved = root;
+ root = root->left;
+ while (root != nil && dict->compare(key, root->key))
+ root = root->right;
+ } while (root != nil);
+ return saved;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+#ifdef FSCK_NOTUSED
+/*
+ * Look for the node corresponding to the lowest key that is equal to or
+ * greater than the given key. If there is no such node, return null.
+ */
+dnode_t *dict_lower_bound(dict_t *dict, const void *key)
+{
+ dnode_t *root = dict_root(dict);
+ dnode_t *nil = dict_nil(dict);
+ dnode_t *tentative = 0;
+
+ while (root != nil) {
+ int result = dict->compare(key, root->key);
+
+ if (result > 0) {
+ root = root->right;
+ } else if (result < 0) {
+ tentative = root;
+ root = root->left;
+ } else {
+ if (!dict->dupes) {
+ return root;
+ } else {
+ tentative = root;
+ root = root->left;
+ }
+ }
+ }
+
+ return tentative;
+}
+
+/*
+ * Look for the node corresponding to the greatest key that is equal to or
+ * lower than the given key. If there is no such node, return null.
+ */
+dnode_t *dict_upper_bound(dict_t *dict, const void *key)
+{
+ dnode_t *root = dict_root(dict);
+ dnode_t *nil = dict_nil(dict);
+ dnode_t *tentative = 0;
+
+ while (root != nil) {
+ int result = dict->compare(key, root->key);
+
+ if (result < 0) {
+ root = root->left;
+ } else if (result > 0) {
+ tentative = root;
+ root = root->right;
+ } else {
+ if (!dict->dupes) {
+ return root;
+ } else {
+ tentative = root;
+ root = root->right;
+ }
+ }
+ }
+
+ return tentative;
+}
+#endif
+
+/*
+ * Insert a node into the dictionary. The node should have been
+ * initialized with a data field. All other fields are ignored.
+ * The behavior is undefined if the user attempts to insert into
+ * a dictionary that is already full (for which the dict_isfull()
+ * function returns true).
+ */
+void dict_insert(dict_t *dict, dnode_t *node, const void *key)
+{
+ dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
+ dnode_t *parent = nil, *uncle, *grandpa;
+ int result = -1;
+
+ node->key = key;
+
+ dict_assert(!dict_isfull(dict));
+ dict_assert(!dict_contains(dict, node));
+ dict_assert(!dnode_is_in_a_dict(node));
+
+ /* basic binary tree insert */
+
+ while (where != nil) {
+ parent = where;
+ result = dict->compare(key, where->key);
+ /* trap attempts at duplicate key insertion unless it's explicitly allowed */
+ dict_assert(dict->dupes || result != 0);
+ if (result < 0)
+ where = where->left;
+ else
+ where = where->right;
+ }
+
+ dict_assert(where == nil);
+
+ if (result < 0)
+ parent->left = node;
+ else
+ parent->right = node;
+
+ node->parent = parent;
+ node->left = nil;
+ node->right = nil;
+
+ dict->nodecount++;
+
+ /* red black adjustments */
+
+ node->color = dnode_red;
+
+ while (parent->color == dnode_red) {
+ grandpa = parent->parent;
+ if (parent == grandpa->left) {
+ uncle = grandpa->right;
+ if (uncle->color == dnode_red) { /* red parent, red uncle */
+ parent->color = dnode_black;
+ uncle->color = dnode_black;
+ grandpa->color = dnode_red;
+ node = grandpa;
+ parent = grandpa->parent;
+ } else { /* red parent, black uncle */
+ if (node == parent->right) {
+ rotate_left(parent);
+ parent = node;
+ dict_assert(grandpa == parent->parent);
+ /* rotation between parent and child preserves grandpa */
+ }
+ parent->color = dnode_black;
+ grandpa->color = dnode_red;
+ rotate_right(grandpa);
+ break;
+ }
+ } else { /* symmetric cases: parent == parent->parent->right */
+ uncle = grandpa->left;
+ if (uncle->color == dnode_red) {
+ parent->color = dnode_black;
+ uncle->color = dnode_black;
+ grandpa->color = dnode_red;
+ node = grandpa;
+ parent = grandpa->parent;
+ } else {
+ if (node == parent->left) {
+ rotate_right(parent);
+ parent = node;
+ dict_assert(grandpa == parent->parent);
+ }
+ parent->color = dnode_black;
+ grandpa->color = dnode_red;
+ rotate_left(grandpa);
+ break;
+ }
+ }
+ }
+
+ dict_root(dict)->color = dnode_black;
+
+ dict_assert(dict_verify(dict));
+}
+
+#ifdef FSCK_NOTUSED
+/*
+ * Delete the given node from the dictionary. If the given node does not belong
+ * to the given dictionary, undefined behavior results. A pointer to the
+ * deleted node is returned.
+ */
+dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
+{
+ dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
+
+ /* basic deletion */
+
+ dict_assert(!dict_isempty(dict));
+ dict_assert(dict_contains(dict, delete));
+
+ /*
+ * If the node being deleted has two children, then we replace it with its
+ * successor (i.e. the leftmost node in the right subtree.) By doing this,
+ * we avoid the traditional algorithm under which the successor's key and
+ * value *only* move to the deleted node and the successor is spliced out
+ * from the tree. We cannot use this approach because the user may hold
+ * pointers to the successor, or nodes may be inextricably tied to some
+ * other structures by way of embedding, etc. So we must splice out the
+ * node we are given, not some other node, and must not move contents from
+ * one node to another behind the user's back.
+ */
+
+ if (delete->left != nil && delete->right != nil) {
+ dnode_t *next = dict_next(dict, delete);
+ dnode_t *nextparent = next->parent;
+ dnode_color_t nextcolor = next->color;
+
+ dict_assert(next != nil);
+ dict_assert(next->parent != nil);
+ dict_assert(next->left == nil);
+
+ /*
+ * First, splice out the successor from the tree completely, by
+ * moving up its right child into its place.
+ */
+
+ child = next->right;
+ child->parent = nextparent;
+
+ if (nextparent->left == next) {
+ nextparent->left = child;
+ } else {
+ dict_assert(nextparent->right == next);
+ nextparent->right = child;
+ }
+
+ /*
+ * Now that the successor has been extricated from the tree, install it
+ * in place of the node that we want deleted.
+ */
+
+ next->parent = delparent;
+ next->left = delete->left;
+ next->right = delete->right;
+ next->left->parent = next;
+ next->right->parent = next;
+ next->color = delete->color;
+ delete->color = nextcolor;
+
+ if (delparent->left == delete) {
+ delparent->left = next;
+ } else {
+ dict_assert(delparent->right == delete);
+ delparent->right = next;
+ }
+
+ } else {
+ dict_assert(delete != nil);
+ dict_assert(delete->left == nil || delete->right == nil);
+
+ child = (delete->left != nil) ? delete->left : delete->right;
+
+ child->parent = delparent = delete->parent;
+
+ if (delete == delparent->left) {
+ delparent->left = child;
+ } else {
+ dict_assert(delete == delparent->right);
+ delparent->right = child;
+ }
+ }
+
+ delete->parent = NULL;
+ delete->right = NULL;
+ delete->left = NULL;
+
+ dict->nodecount--;
+
+ dict_assert(verify_bintree(dict));
+
+ /* red-black adjustments */
+
+ if (delete->color == dnode_black) {
+ dnode_t *parent, *sister;
+
+ dict_root(dict)->color = dnode_red;
+
+ while (child->color == dnode_black) {
+ parent = child->parent;
+ if (child == parent->left) {
+ sister = parent->right;
+ dict_assert(sister != nil);
+ if (sister->color == dnode_red) {
+ sister->color = dnode_black;
+ parent->color = dnode_red;
+ rotate_left(parent);
+ sister = parent->right;
+ dict_assert(sister != nil);
+ }
+ if (sister->left->color == dnode_black
+ && sister->right->color == dnode_black) {
+ sister->color = dnode_red;
+ child = parent;
+ } else {
+ if (sister->right->color == dnode_black) {
+ dict_assert(sister->left->color == dnode_red);
+ sister->left->color = dnode_black;
+ sister->color = dnode_red;
+ rotate_right(sister);
+ sister = parent->right;
+ dict_assert(sister != nil);
+ }
+ sister->color = parent->color;
+ sister->right->color = dnode_black;
+ parent->color = dnode_black;
+ rotate_left(parent);
+ break;
+ }
+ } else { /* symmetric case: child == child->parent->right */
+ dict_assert(child == parent->right);
+ sister = parent->left;
+ dict_assert(sister != nil);
+ if (sister->color == dnode_red) {
+ sister->color = dnode_black;
+ parent->color = dnode_red;
+ rotate_right(parent);
+ sister = parent->left;
+ dict_assert(sister != nil);
+ }
+ if (sister->right->color == dnode_black
+ && sister->left->color == dnode_black) {
+ sister->color = dnode_red;
+ child = parent;
+ } else {
+ if (sister->left->color == dnode_black) {
+ dict_assert(sister->right->color == dnode_red);
+ sister->right->color = dnode_black;
+ sister->color = dnode_red;
+ rotate_left(sister);
+ sister = parent->left;
+ dict_assert(sister != nil);
+ }
+ sister->color = parent->color;
+ sister->left->color = dnode_black;
+ parent->color = dnode_black;
+ rotate_right(parent);
+ break;
+ }
+ }
+ }
+
+ child->color = dnode_black;
+ dict_root(dict)->color = dnode_black;
+ }
+
+ dict_assert(dict_verify(dict));
+
+ return delete;
+}
+#endif /* FSCK_NOTUSED */
+
+/*
+ * Allocate a node using the dictionary's allocator routine, give it
+ * the data item.
+ */
+int dict_alloc_insert(dict_t *dict, const void *key, void *data)
+{
+ dnode_t *node = dict->allocnode(dict->context);
+
+ if (node) {
+ dnode_init(node, data);
+ dict_insert(dict, node, key);
+ return 1;
+ }
+ return 0;
+}
+
+#ifdef FSCK_NOTUSED
+void dict_delete_free(dict_t *dict, dnode_t *node)
+{
+ dict_delete(dict, node);
+ dict->freenode(node, dict->context);
+}
+#endif
+
+/*
+ * Return the node with the lowest (leftmost) key. If the dictionary is empty
+ * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
+ */
+dnode_t *dict_first(dict_t *dict)
+{
+ dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
+
+ if (root != nil)
+ while ((left = root->left) != nil)
+ root = left;
+
+ return (root == nil) ? NULL : root;
+}
+
+/*
+ * Return the node with the highest (rightmost) key. If the dictionary is empty
+ * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
+ */
+dnode_t *dict_last(dict_t *dict)
+{
+ dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
+
+ if (root != nil)
+ while ((right = root->right) != nil)
+ root = right;
+
+ return (root == nil) ? NULL : root;
+}
+
+/*
+ * Return the given node's successor node---the node which has the
+ * next key in the the left to right ordering. If the node has
+ * no successor, a null pointer is returned rather than a pointer to
+ * the nil node.
+ */
+dnode_t *dict_next(dict_t *dict, dnode_t *curr)
+{
+ dnode_t *nil = dict_nil(dict), *parent, *left;
+
+ if (curr->right != nil) {
+ curr = curr->right;
+ while ((left = curr->left) != nil)
+ curr = left;
+ return curr;
+ }
+
+ parent = curr->parent;
+
+ while (parent != nil && curr == parent->right) {
+ curr = parent;
+ parent = curr->parent;
+ }
+
+ return (parent == nil) ? NULL : parent;
+}
+
+/*
+ * Return the given node's predecessor, in the key order.
+ * The nil sentinel node is returned if there is no predecessor.
+ */
+dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
+{
+ dnode_t *nil = dict_nil(dict), *parent, *right;
+
+ if (curr->left != nil) {
+ curr = curr->left;
+ while ((right = curr->right) != nil)
+ curr = right;
+ return curr;
+ }
+
+ parent = curr->parent;
+
+ while (parent != nil && curr == parent->left) {
+ curr = parent;
+ parent = curr->parent;
+ }
+
+ return (parent == nil) ? NULL : parent;
+}
+
+void dict_allow_dupes(dict_t *dict)
+{
+ dict->dupes = 1;
+}
+
+#undef dict_count
+#undef dict_isempty
+#undef dict_isfull
+#undef dnode_get
+#undef dnode_put
+#undef dnode_getkey
+
+dictcount_t dict_count(dict_t *dict)
+{
+ return dict->nodecount;
+}
+
+int dict_isempty(dict_t *dict)
+{
+ return dict->nodecount == 0;
+}
+
+int dict_isfull(dict_t *dict)
+{
+ return dict->nodecount == dict->maxcount;
+}
+
+int dict_contains(dict_t *dict, dnode_t *node)
+{
+ return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
+}
+
+static dnode_t *dnode_alloc(void *UNUSED(context))
+{
+ return malloc(sizeof *dnode_alloc(NULL));
+}
+
+static void dnode_free(dnode_t *node, void *UNUSED(context))
+{
+ free(node);
+}
+
+dnode_t *dnode_create(void *data)
+{
+ dnode_t *new = malloc(sizeof *new);
+ if (new) {
+ new->data = data;
+ new->parent = NULL;
+ new->left = NULL;
+ new->right = NULL;
+ }
+ return new;
+}
+
+dnode_t *dnode_init(dnode_t *dnode, void *data)
+{
+ dnode->data = data;
+ dnode->parent = NULL;
+ dnode->left = NULL;
+ dnode->right = NULL;
+ return dnode;
+}
+
+void dnode_destroy(dnode_t *dnode)
+{
+ dict_assert(!dnode_is_in_a_dict(dnode));
+ free(dnode);
+}
+
+void *dnode_get(dnode_t *dnode)
+{
+ return dnode->data;
+}
+
+const void *dnode_getkey(dnode_t *dnode)
+{
+ return dnode->key;
+}
+
+#ifdef FSCK_NOTUSED
+void dnode_put(dnode_t *dnode, void *data)
+{
+ dnode->data = data;
+}
+#endif
+
+#ifndef DICT_NODEBUG
+int dnode_is_in_a_dict(dnode_t *dnode)
+{
+ return (dnode->parent && dnode->left && dnode->right);
+}
+#endif
+
+#ifdef FSCK_NOTUSED
+void dict_process(dict_t *dict, void *context, dnode_process_t function)
+{
+ dnode_t *node = dict_first(dict), *next;
+
+ while (node != NULL) {
+ /* check for callback function deleting */
+ /* the next node from under us */
+ dict_assert(dict_contains(dict, node));
+ next = dict_next(dict, node);
+ function(dict, node, context);
+ node = next;
+ }
+}
+
+static void load_begin_internal(dict_load_t *load, dict_t *dict)
+{
+ load->dictptr = dict;
+ load->nilnode.left = &load->nilnode;
+ load->nilnode.right = &load->nilnode;
+}
+
+void dict_load_begin(dict_load_t *load, dict_t *dict)
+{
+ dict_assert(dict_isempty(dict));
+ load_begin_internal(load, dict);
+}
+
+void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)
+{
+ dict_t *dict = load->dictptr;
+ dnode_t *nil = &load->nilnode;
+
+ dict_assert(!dnode_is_in_a_dict(newnode));
+ dict_assert(dict->nodecount < dict->maxcount);
+
+#ifndef DICT_NODEBUG
+ if (dict->nodecount > 0) {
+ if (dict->dupes)
+ dict_assert(dict->compare(nil->left->key, key) <= 0);
+ else
+ dict_assert(dict->compare(nil->left->key, key) < 0);
+ }
+#endif
+
+ newnode->key = key;
+ nil->right->left = newnode;
+ nil->right = newnode;
+ newnode->left = nil;
+ dict->nodecount++;
+}
+
+void dict_load_end(dict_load_t *load)
+{
+ dict_t *dict = load->dictptr;
+ dnode_t *tree[DICT_DEPTH_MAX] = { 0 };
+ dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
+ dnode_t *complete = 0;
+ dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
+ dictcount_t botrowcount;
+ unsigned baselevel = 0, level = 0, i;
+
+ dict_assert(dnode_red == 0 && dnode_black == 1);
+
+ while (fullcount >= nodecount && fullcount)
+ fullcount >>= 1;
+
+ botrowcount = nodecount - fullcount;
+
+ for (curr = loadnil->left; curr != loadnil; curr = next) {
+ next = curr->left;
+
+ if (complete == NULL && botrowcount-- == 0) {
+ dict_assert(baselevel == 0);
+ dict_assert(level == 0);
+ baselevel = level = 1;
+ complete = tree[0];
+
+ if (complete != 0) {
+ tree[0] = 0;
+ complete->right = dictnil;
+ while (tree[level] != 0) {
+ tree[level]->right = complete;
+ complete->parent = tree[level];
+ complete = tree[level];
+ tree[level++] = 0;
+ }
+ }
+ }
+
+ if (complete == NULL) {
+ curr->left = dictnil;
+ curr->right = dictnil;
+ curr->color = level % 2;
+ complete = curr;
+
+ dict_assert(level == baselevel);
+ while (tree[level] != 0) {
+ tree[level]->right = complete;
+ complete->parent = tree[level];
+ complete = tree[level];
+ tree[level++] = 0;
+ }
+ } else {
+ curr->left = complete;
+ curr->color = (level + 1) % 2;
+ complete->parent = curr;
+ tree[level] = curr;
+ complete = 0;
+ level = baselevel;
+ }
+ }
+
+ if (complete == NULL)
+ complete = dictnil;
+
+ for (i = 0; i < DICT_DEPTH_MAX; i++) {
+ if (tree[i] != 0) {
+ tree[i]->right = complete;
+ complete->parent = tree[i];
+ complete = tree[i];
+ }
+ }
+
+ dictnil->color = dnode_black;
+ dictnil->right = dictnil;
+ complete->parent = dictnil;
+ complete->color = dnode_black;
+ dict_root(dict) = complete;
+
+ dict_assert(dict_verify(dict));
+}
+
+void dict_merge(dict_t *dest, dict_t *source)
+{
+ dict_load_t load;
+ dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);
+
+ dict_assert(dict_similar(dest, source));
+
+ if (source == dest)
+ return;
+
+ dest->nodecount = 0;
+ load_begin_internal(&load, dest);
+
+ for (;;) {
+ if (leftnode != NULL && rightnode != NULL) {
+ if (dest->compare(leftnode->key, rightnode->key) < 0)
+ goto copyleft;
+ else
+ goto copyright;
+ } else if (leftnode != NULL) {
+ goto copyleft;
+ } else if (rightnode != NULL) {
+ goto copyright;
+ } else {
+ dict_assert(leftnode == NULL && rightnode == NULL);
+ break;
+ }
+
+copyleft:
+ {
+ dnode_t *next = dict_next(dest, leftnode);
+#ifndef DICT_NODEBUG
+ leftnode->left = NULL; /* suppress assertion in dict_load_next */
+#endif
+ dict_load_next(&load, leftnode, leftnode->key);
+ leftnode = next;
+ continue;
+ }
+
+copyright:
+ {
+ dnode_t *next = dict_next(source, rightnode);
+#ifndef DICT_NODEBUG
+ rightnode->left = NULL;
+#endif
+ dict_load_next(&load, rightnode, rightnode->key);
+ rightnode = next;
+ continue;
+ }
+ }
+
+ dict_clear(source);
+ dict_load_end(&load);
+}
+#endif /* FSCK_NOTUSED */
+
+#ifdef KAZLIB_TEST_MAIN
+
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <stdarg.h>
+
+typedef char input_t[256];
+
+static int tokenize(char *string, ...)
+{
+ char **tokptr;
+ va_list arglist;
+ int tokcount = 0;
+
+ va_start(arglist, string);
+ tokptr = va_arg(arglist, char **);
+ while (tokptr) {
+ while (*string && isspace((unsigned char) *string))
+ string++;
+ if (!*string)
+ break;
+ *tokptr = string;
+ while (*string && !isspace((unsigned char) *string))
+ string++;
+ tokptr = va_arg(arglist, char **);
+ tokcount++;
+ if (!*string)
+ break;
+ *string++ = 0;
+ }
+ va_end(arglist);
+
+ return tokcount;
+}
+
+static int comparef(const void *key1, const void *key2)
+{
+ return strcmp(key1, key2);
+}
+
+static char *dupstring(char *str)
+{
+ int sz = strlen(str) + 1;
+ char *new = malloc(sz);
+ if (new)
+ memcpy(new, str, sz);
+ return new;
+}
+
+static dnode_t *new_node(void *c)
+{
+ static dnode_t few[5];
+ static int count;
+
+ if (count < 5)
+ return few + count++;
+
+ return NULL;
+}
+
+static void del_node(dnode_t *n, void *c)
+{
+}
+
+static int prompt = 0;
+
+static void construct(dict_t *d)
+{
+ input_t in;
+ int done = 0;
+ dict_load_t dl;
+ dnode_t *dn;
+ char *tok1, *tok2, *val;
+ const char *key;
+ char *help =
+ "p turn prompt on\n"
+ "q finish construction\n"
+ "a <key> <val> add new entry\n";
+
+ if (!dict_isempty(d))
+ puts("warning: dictionary not empty!");
+
+ dict_load_begin(&dl, d);
+
+ while (!done) {
+ if (prompt)
+ putchar('>');
+ fflush(stdout);
+
+ if (!fgets(in, sizeof(input_t), stdin))
+ break;
+
+ switch (in[0]) {
+ case '?':
+ puts(help);
+ break;
+ case 'p':
+ prompt = 1;
+ break;
+ case 'q':
+ done = 1;
+ break;
+ case 'a':
+ if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
+ puts("what?");
+ break;
+ }
+ key = dupstring(tok1);
+ val = dupstring(tok2);
+ dn = dnode_create(val);
+
+ if (!key || !val || !dn) {
+ puts("out of memory");
+ free((void *) key);
+ free(val);
+ if (dn)
+ dnode_destroy(dn);
+ }
+
+ dict_load_next(&dl, dn, key);
+ break;
+ default:
+ putchar('?');
+ putchar('\n');
+ break;
+ }
+ }
+
+ dict_load_end(&dl);
+}
+
+int main(void)
+{
+ input_t in;
+ dict_t darray[10];
+ dict_t *d = &darray[0];
+ dnode_t *dn;
+ int i;
+ char *tok1, *tok2, *val;
+ const char *key;
+
+ char *help =
+ "a <key> <val> add value to dictionary\n"
+ "d <key> delete value from dictionary\n"
+ "l <key> lookup value in dictionary\n"
+ "( <key> lookup lower bound\n"
+ ") <key> lookup upper bound\n"
+ "# <num> switch to alternate dictionary (0-9)\n"
+ "j <num> <num> merge two dictionaries\n"
+ "f free the whole dictionary\n"
+ "k allow duplicate keys\n"
+ "c show number of entries\n"
+ "t dump whole dictionary in sort order\n"
+ "m make dictionary out of sorted items\n"
+ "p turn prompt on\n"
+ "s switch to non-functioning allocator\n"
+ "q quit";
+
+ for (i = 0; i < sizeof darray / sizeof *darray; i++)
+ dict_init(&darray[i], DICTCOUNT_T_MAX, comparef);
+
+ for (;;) {
+ if (prompt)
+ putchar('>');
+ fflush(stdout);
+
+ if (!fgets(in, sizeof(input_t), stdin))
+ break;
+
+ switch(in[0]) {
+ case '?':
+ puts(help);
+ break;
+ case 'a':
+ if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
+ puts("what?");
+ break;
+ }
+ key = dupstring(tok1);
+ val = dupstring(tok2);
+
+ if (!key || !val) {
+ puts("out of memory");
+ free((void *) key);
+ free(val);
+ }
+
+ if (!dict_alloc_insert(d, key, val)) {
+ puts("dict_alloc_insert failed");
+ free((void *) key);
+ free(val);
+ break;
+ }
+ break;
+ case 'd':
+ if (tokenize(in+1, &tok1, (char **) 0) != 1) {
+ puts("what?");
+ break;
+ }
+ dn = dict_lookup(d, tok1);
+ if (!dn) {
+ puts("dict_lookup failed");
+ break;
+ }
+ val = dnode_get(dn);
+ key = dnode_getkey(dn);
+ dict_delete_free(d, dn);
+
+ free(val);
+ free((void *) key);
+ break;
+ case 'f':
+ dict_free(d);
+ break;
+ case 'l':
+ case '(':
+ case ')':
+ if (tokenize(in+1, &tok1, (char **) 0) != 1) {
+ puts("what?");
+ break;
+ }
+ dn = 0;
+ switch (in[0]) {
+ case 'l':
+ dn = dict_lookup(d, tok1);
+ break;
+ case '(':
+ dn = dict_lower_bound(d, tok1);
+ break;
+ case ')':
+ dn = dict_upper_bound(d, tok1);
+ break;
+ }
+ if (!dn) {
+ puts("lookup failed");
+ break;
+ }
+ val = dnode_get(dn);
+ puts(val);
+ break;
+ case 'm':
+ construct(d);
+ break;
+ case 'k':
+ dict_allow_dupes(d);
+ break;
+ case 'c':
+ printf("%lu\n", (unsigned long) dict_count(d));
+ break;
+ case 't':
+ for (dn = dict_first(d); dn; dn = dict_next(d, dn)) {
+ printf("%s\t%s\n", (char *) dnode_getkey(dn),
+ (char *) dnode_get(dn));
+ }
+ break;
+ case 'q':
+ exit(0);
+ break;
+ case '\0':
+ break;
+ case 'p':
+ prompt = 1;
+ break;
+ case 's':
+ dict_set_allocator(d, new_node, del_node, NULL);
+ break;
+ case '#':
+ if (tokenize(in+1, &tok1, (char **) 0) != 1) {
+ puts("what?");
+ break;
+ } else {
+ int dictnum = atoi(tok1);
+ if (dictnum < 0 || dictnum > 9) {
+ puts("invalid number");
+ break;
+ }
+ d = &darray[dictnum];
+ }
+ break;
+ case 'j':
+ if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
+ puts("what?");
+ break;
+ } else {
+ int dict1 = atoi(tok1), dict2 = atoi(tok2);
+ if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) {
+ puts("invalid number");
+ break;
+ }
+ dict_merge(&darray[dict1], &darray[dict2]);
+ }
+ break;
+ default:
+ putchar('?');
+ putchar('\n');
+ break;
+ }
+ }
+
+ return 0;
+}
+
+#endif
diff --git a/fsck/dict.h b/fsck/dict.h
new file mode 100644
index 0000000..c59e1a2
--- /dev/null
+++ b/fsck/dict.h
@@ -0,0 +1,144 @@
+/*
+ * Dictionary Abstract Data Type
+ * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
+ *
+ * Free Software License:
+ *
+ * All rights are reserved by the author, with the following exceptions:
+ * Permission is granted to freely reproduce and distribute this software,
+ * possibly in exchange for a fee, provided that this copyright notice appears
+ * intact. Permission is also granted to adapt this software to produce
+ * derivative works, as long as the modified versions carry this copyright
+ * notice and additional notices stating that the work has been modified.
+ * This source code may be translated into executable form and incorporated
+ * into proprietary software; there is no requirement for such software to
+ * contain a copyright notice related to this source.
+ *
+ * $Id: dict.h,v 1.22.2.6 2000/11/13 01:36:44 kaz Exp $
+ * $Name: kazlib_1_20 $
+ */
+
+#ifndef DICT_H
+#define DICT_H
+
+#include <limits.h>
+#ifdef KAZLIB_SIDEEFFECT_DEBUG
+#include "sfx.h"
+#endif
+
+/*
+ * Blurb for inclusion into C++ translation units
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef unsigned long dictcount_t;
+#define DICTCOUNT_T_MAX ULONG_MAX
+
+/*
+ * The dictionary is implemented as a red-black tree
+ */
+
+typedef enum { dnode_red, dnode_black } dnode_color_t;
+
+typedef struct dnode_t {
+#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
+ struct dnode_t *dict_left;
+ struct dnode_t *dict_right;
+ struct dnode_t *dict_parent;
+ dnode_color_t dict_color;
+ const void *dict_key;
+ void *dict_data;
+#else
+ int dict_dummy;
+#endif
+} dnode_t;
+
+typedef int (*dict_comp_t)(const void *, const void *);
+typedef dnode_t *(*dnode_alloc_t)(void *);
+typedef void (*dnode_free_t)(dnode_t *, void *);
+
+typedef struct dict_t {
+#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
+ dnode_t dict_nilnode;
+ dictcount_t dict_nodecount;
+ dictcount_t dict_maxcount;
+ dict_comp_t dict_compare;
+ dnode_alloc_t dict_allocnode;
+ dnode_free_t dict_freenode;
+ void *dict_context;
+ int dict_dupes;
+#else
+ int dict_dummmy;
+#endif
+} dict_t;
+
+typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
+
+typedef struct dict_load_t {
+#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
+ dict_t *dict_dictptr;
+ dnode_t dict_nilnode;
+#else
+ int dict_dummmy;
+#endif
+} dict_load_t;
+
+extern dict_t *dict_create(dictcount_t, dict_comp_t);
+extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
+extern void dict_destroy(dict_t *);
+extern void dict_free_nodes(dict_t *);
+extern void dict_free(dict_t *);
+extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
+extern void dict_init_like(dict_t *, const dict_t *);
+extern int dict_verify(dict_t *);
+extern int dict_similar(const dict_t *, const dict_t *);
+extern dnode_t *dict_lookup(dict_t *, const void *);
+extern dnode_t *dict_lower_bound(dict_t *, const void *);
+extern dnode_t *dict_upper_bound(dict_t *, const void *);
+extern void dict_insert(dict_t *, dnode_t *, const void *);
+extern dnode_t *dict_delete(dict_t *, dnode_t *);
+extern int dict_alloc_insert(dict_t *, const void *, void *);
+extern void dict_delete_free(dict_t *, dnode_t *);
+extern dnode_t *dict_first(dict_t *);
+extern dnode_t *dict_last(dict_t *);
+extern dnode_t *dict_next(dict_t *, dnode_t *);
+extern dnode_t *dict_prev(dict_t *, dnode_t *);
+extern dictcount_t dict_count(dict_t *);
+extern int dict_isempty(dict_t *);
+extern int dict_isfull(dict_t *);
+extern int dict_contains(dict_t *, dnode_t *);
+extern void dict_allow_dupes(dict_t *);
+extern int dnode_is_in_a_dict(dnode_t *);
+extern dnode_t *dnode_create(void *);
+extern dnode_t *dnode_init(dnode_t *, void *);
+extern void dnode_destroy(dnode_t *);
+extern void *dnode_get(dnode_t *);
+extern const void *dnode_getkey(dnode_t *);
+extern void dnode_put(dnode_t *, void *);
+extern void dict_process(dict_t *, void *, dnode_process_t);
+extern void dict_load_begin(dict_load_t *, dict_t *);
+extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
+extern void dict_load_end(dict_load_t *);
+extern void dict_merge(dict_t *, dict_t *);
+
+#if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
+#ifdef KAZLIB_SIDEEFFECT_DEBUG
+#define dict_isfull(D) (SFX_CHECK(D)->dict_nodecount == (D)->dict_maxcount)
+#else
+#define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
+#endif
+#define dict_count(D) ((D)->dict_nodecount)
+#define dict_isempty(D) ((D)->dict_nodecount == 0)
+#define dnode_get(N) ((N)->dict_data)
+#define dnode_getkey(N) ((N)->dict_key)
+#define dnode_put(N, X) ((N)->dict_data = (X))
+#endif
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/fsck/dqblk_v2.h b/fsck/dqblk_v2.h
new file mode 100644
index 0000000..d12512a
--- /dev/null
+++ b/fsck/dqblk_v2.h
@@ -0,0 +1,31 @@
+/*
+ * Header file for disk format of new quotafile format
+ *
+ * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
+ */
+
+#ifndef __QUOTA_DQBLK_V2_H__
+#define __QUOTA_DQBLK_V2_H__
+
+#include "quotaio_tree.h"
+
+/* Structure for format specific information */
+struct v2_mem_dqinfo {
+ struct qtree_mem_dqinfo dqi_qtree;
+ unsigned int dqi_flags; /* Flags set in quotafile */
+ unsigned int dqi_used_entries; /* Number of entries in file -
+ updated by scan_dquots */
+ unsigned int dqi_data_blocks; /* Number of data blocks in file -
+ updated by scan_dquots */
+};
+
+struct v2_mem_dqblk {
+ long long dqb_off; /* Offset of dquot in file */
+};
+
+struct quotafile_ops; /* Will be defined later in quotaio.h */
+
+/* Operations above this format */
+extern struct quotafile_ops quotafile_ops_2;
+
+#endif /* __QUOTA_DQBLK_V2_H__ */
diff --git a/fsck/fsck.c b/fsck/fsck.c
index 56a47be..35df68c 100644
--- a/fsck/fsck.c
+++ b/fsck/fsck.c
@@ -9,12 +9,12 @@
* published by the Free Software Foundation.
*/
#include "fsck.h"
+#include "quotaio.h"
char *tree_mark;
uint32_t tree_mark_size = 256;
-static inline int f2fs_set_main_bitmap(struct f2fs_sb_info *sbi, u32 blk,
- int type)
+int f2fs_set_main_bitmap(struct f2fs_sb_info *sbi, u32 blk, int type)
{
struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
struct seg_entry *se;
@@ -50,6 +50,13 @@ static inline int f2fs_test_sit_bitmap(struct f2fs_sb_info *sbi, u32 blk)
return f2fs_test_bit(BLKOFF_FROM_MAIN(sbi, blk), fsck->sit_area_bitmap);
}
+int f2fs_set_sit_bitmap(struct f2fs_sb_info *sbi, u32 blk)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+
+ return f2fs_set_bit(BLKOFF_FROM_MAIN(sbi, blk), fsck->sit_area_bitmap);
+}
+
static int add_into_hard_link_list(struct f2fs_sb_info *sbi,
u32 nid, u32 link_cnt)
{
@@ -500,7 +507,9 @@ int fsck_chk_node_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
goto err;
if (ntype == TYPE_INODE) {
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
fsck_chk_inode_blk(sbi, nid, ftype, node_blk, blk_cnt, &ni);
+ quota_add_inode_usage(fsck->qctx, nid, &node_blk->i);
} else {
switch (ntype) {
case TYPE_DIRECT_NODE:
@@ -622,7 +631,8 @@ void fsck_chk_inode_blk(struct f2fs_sb_info *sbi, u32 nid,
if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0) {
f2fs_set_main_bitmap(sbi, ni->blk_addr,
CURSEG_WARM_NODE);
- if (i_links > 1 && ftype != F2FS_FT_ORPHAN) {
+ if (i_links > 1 && ftype != F2FS_FT_ORPHAN &&
+ !is_qf_ino(F2FS_RAW_SUPER(sbi), nid)) {
/* First time. Create new hard link node */
add_into_hard_link_list(sbi, nid, i_links);
fsck->chk.multi_hard_link_files++;
@@ -807,6 +817,11 @@ skip_blkcnt_fix:
le32_to_cpu(node_blk->footer.ino),
en, (u32)i_blocks);
+ if (is_qf_ino(F2FS_RAW_SUPER(sbi), nid))
+ DBG(1, "Quota Inode: 0x%x [%s] i_blocks: %u\n\n",
+ le32_to_cpu(node_blk->footer.ino),
+ en, (u32)i_blocks);
+
if (ftype == F2FS_FT_DIR) {
DBG(1, "Directory Inode: 0x%x [%s] depth: %d has %d files\n\n",
le32_to_cpu(node_blk->footer.ino), en,
@@ -1558,6 +1573,82 @@ int fsck_chk_orphan_node(struct f2fs_sb_info *sbi)
return 0;
}
+int fsck_chk_quota_node(struct f2fs_sb_info *sbi)
+{
+ struct f2fs_super_block *sb = F2FS_RAW_SUPER(sbi);
+ enum quota_type qtype;
+ int ret = 0;
+ u32 blk_cnt = 0;
+
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (sb->qf_ino[qtype] == 0)
+ continue;
+ nid_t ino = QUOTA_INO(sb, qtype);
+ struct node_info ni;
+
+ DBG(1, "[%3d] ino [0x%x]\n", qtype, ino);
+ blk_cnt = 1;
+
+ if (c.preen_mode == PREEN_MODE_1 && !c.fix_on) {
+ get_node_info(sbi, ino, &ni);
+ if (!IS_VALID_NID(sbi, ino) ||
+ !IS_VALID_BLK_ADDR(sbi, ni.blk_addr))
+ return -EINVAL;
+ }
+ ret = fsck_chk_node_blk(sbi, NULL, ino,
+ F2FS_FT_REG_FILE, TYPE_INODE, &blk_cnt, NULL);
+ if (ret)
+ ASSERT_MSG("[0x%x] wrong orphan inode", ino);
+ }
+ return ret;
+}
+
+int fsck_chk_quota_files(struct f2fs_sb_info *sbi)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+ struct f2fs_super_block *sb = F2FS_RAW_SUPER(sbi);
+ enum quota_type qtype;
+ f2fs_ino_t ino;
+ int ret = 0;
+ int needs_writeout;
+
+ /* Return if quota feature is disabled */
+ if (!fsck->qctx)
+ return 0;
+
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ ino = sb->qf_ino[qtype];
+ if (!ino)
+ continue;
+
+ DBG(1, "Checking Quota file ([%3d] ino [0x%x])\n", qtype, ino);
+ needs_writeout = 0;
+ ret = quota_compare_and_update(sbi, qtype, &needs_writeout);
+ if (ret == 0 && needs_writeout == 0) {
+ DBG(1, "OK\n");
+ continue;
+ }
+
+ /* Something is wrong */
+ if (c.fix_on) {
+ DBG(0, "Fixing Quota file ([%3d] ino [0x%x])\n",
+ qtype, ino);
+ f2fs_filesize_update(sbi, ino, 0);
+ ret = quota_write_inode(sbi, qtype);
+ if (!ret) {
+ c.bug_on = 1;
+ DBG(1, "OK\n");
+ } else {
+ ASSERT_MSG("Unable to write quota file");
+ }
+ } else {
+ ASSERT_MSG("Quota file is missing or invalid"
+ " quota file content found.");
+ }
+ }
+ return ret;
+}
+
int fsck_chk_meta(struct f2fs_sb_info *sbi)
{
struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
@@ -1618,6 +1709,10 @@ int fsck_chk_meta(struct f2fs_sb_info *sbi)
if (fsck_chk_orphan_node(sbi))
return -EINVAL;
+ /* 5. check quota inode simply */
+ if (fsck_chk_quota_node(sbi))
+ return -EINVAL;
+
if (fsck->nat_valid_inode_cnt != le32_to_cpu(cp->valid_inode_count)) {
ASSERT_MSG("valid inode does not match: nat_valid_inode_cnt %u,"
" valid_inode_count %u",
@@ -2042,6 +2137,10 @@ int fsck_verify(struct f2fs_sb_info *sbi)
void fsck_free(struct f2fs_sb_info *sbi)
{
struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+
+ if (fsck->qctx)
+ quota_release_context(&fsck->qctx);
+
if (fsck->main_area_bitmap)
free(fsck->main_area_bitmap);
diff --git a/fsck/fsck.h b/fsck/fsck.h
index 5628906..7b6ac2b 100644
--- a/fsck/fsck.h
+++ b/fsck/fsck.h
@@ -13,6 +13,8 @@
#include "f2fs.h"
+struct quota_ctx;
+
#define FSCK_UNMATCHED_EXTENT 0x00000001
enum {
@@ -85,6 +87,8 @@ struct f2fs_fsck {
u32 dentry_depth;
struct f2fs_nat_entry *entries;
u32 nat_valid_inode_cnt;
+
+ struct quota_ctx *qctx;
};
#define BLOCK_SZ 4096
@@ -118,6 +122,8 @@ enum seg_type {
struct selabel_handle;
extern int fsck_chk_orphan_node(struct f2fs_sb_info *);
+extern int fsck_chk_quota_node(struct f2fs_sb_info *);
+extern int fsck_chk_quota_files(struct f2fs_sb_info *);
extern int fsck_chk_node_blk(struct f2fs_sb_info *, struct f2fs_inode *, u32,
enum FILE_TYPE, enum NODE_TYPE, u32 *,
struct child_info *);
@@ -154,6 +160,8 @@ extern void nullify_nat_entry(struct f2fs_sb_info *, u32);
extern void rewrite_sit_area_bitmap(struct f2fs_sb_info *);
extern void build_nat_area_bitmap(struct f2fs_sb_info *);
extern void build_sit_area_bitmap(struct f2fs_sb_info *);
+extern int f2fs_set_main_bitmap(struct f2fs_sb_info *, u32, int);
+extern int f2fs_set_sit_bitmap(struct f2fs_sb_info *, u32);
extern void fsck_init(struct f2fs_sb_info *);
extern int fsck_verify(struct f2fs_sb_info *);
extern void fsck_free(struct f2fs_sb_info *);
@@ -210,6 +218,8 @@ int f2fs_resize(struct f2fs_sb_info *);
/* sload.c */
int f2fs_sload(struct f2fs_sb_info *, const char *, const char *,
const char *, struct selabel_handle *);
+
+/* segment.c */
void reserve_new_block(struct f2fs_sb_info *, block_t *,
struct f2fs_summary *, int);
void new_data_block(struct f2fs_sb_info *, void *,
diff --git a/fsck/main.c b/fsck/main.c
index c9411eb..eab213d 100644
--- a/fsck/main.c
+++ b/fsck/main.c
@@ -18,6 +18,7 @@
#include "fsck.h"
#include <libgen.h>
#include <ctype.h>
+#include "quotaio.h"
struct f2fs_fsck gfsck;
@@ -407,6 +408,7 @@ static void do_fsck(struct f2fs_sb_info *sbi)
struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi);
u32 flag = le32_to_cpu(ckpt->ckpt_flags);
u32 blk_cnt;
+ errcode_t ret;
fsck_init(sbi);
@@ -429,8 +431,7 @@ static void do_fsck(struct f2fs_sb_info *sbi)
c.fix_on = 1;
break;
}
- } else {
- /*
+ } else { /*
* we can hit this in 3 situations:
* 1. fsck -f, fix_on has already been set to 1 when
* parsing options;
@@ -443,12 +444,23 @@ static void do_fsck(struct f2fs_sb_info *sbi)
c.fix_on = 1;
}
- fsck_chk_orphan_node(sbi);
+ fsck_chk_quota_node(sbi);
/* Traverse all block recursively from root inode */
blk_cnt = 1;
+
+ if (c.feature & cpu_to_le32(F2FS_FEATURE_QUOTA_INO)) {
+ ret = quota_init_context(sbi);
+ if (ret) {
+ ASSERT_MSG("quota_init_context failure: %d", ret);
+ return;
+ }
+ }
+ fsck_chk_orphan_node(sbi);
fsck_chk_node_blk(sbi, NULL, sbi->root_ino_num,
F2FS_FT_DIR, TYPE_INODE, &blk_cnt, NULL);
+ fsck_chk_quota_files(sbi);
+
fsck_verify(sbi);
fsck_free(sbi);
}
diff --git a/fsck/mkquota.c b/fsck/mkquota.c
new file mode 100644
index 0000000..aadfae7
--- /dev/null
+++ b/fsck/mkquota.c
@@ -0,0 +1,403 @@
+/*
+ * mkquota.c --- create quota files for a filesystem
+ *
+ * Aditya Kali <adityakali@google.com>
+ * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
+ */
+#include "config.h"
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <errno.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <fcntl.h>
+
+#include "quotaio.h"
+#include "quotaio_v2.h"
+#include "quotaio_tree.h"
+#include "common.h"
+#include "dict.h"
+
+
+/* Needed for architectures where sizeof(int) != sizeof(void *) */
+#define UINT_TO_VOIDPTR(val) ((void *)(intptr_t)(val))
+#define VOIDPTR_TO_UINT(ptr) ((unsigned int)(intptr_t)(ptr))
+
+#if DEBUG_QUOTA
+static void print_dquot(const char *desc, struct dquot *dq)
+{
+ if (desc)
+ fprintf(stderr, "%s: ", desc);
+ fprintf(stderr, "%u %lld:%lld:%lld %lld:%lld:%lld\n",
+ dq->dq_id, (long long) dq->dq_dqb.dqb_curspace,
+ (long long) dq->dq_dqb.dqb_bsoftlimit,
+ (long long) dq->dq_dqb.dqb_bhardlimit,
+ (long long) dq->dq_dqb.dqb_curinodes,
+ (long long) dq->dq_dqb.dqb_isoftlimit,
+ (long long) dq->dq_dqb.dqb_ihardlimit);
+}
+#else
+#define print_dquot(...)
+#endif
+
+static void write_dquots(dict_t *dict, struct quota_handle *qh)
+{
+ dnode_t *n;
+ struct dquot *dq;
+
+ for (n = dict_first(dict); n; n = dict_next(dict, n)) {
+ dq = dnode_get(n);
+ if (dq) {
+ print_dquot("write", dq);
+ dq->dq_h = qh;
+ update_grace_times(dq);
+ qh->qh_ops->commit_dquot(dq);
+ }
+ }
+}
+
+errcode_t quota_write_inode(struct f2fs_sb_info *sbi, enum quota_type qtype)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+ struct f2fs_super_block *sb = F2FS_RAW_SUPER(sbi);
+ quota_ctx_t qctx = fsck->qctx;
+ struct quota_handle *h = NULL;
+ int retval = 0;
+ dict_t *dict;
+
+ if ((!qctx) || (!sb->qf_ino[qtype]))
+ return 0;
+
+ retval = quota_get_mem(sizeof(struct quota_handle), &h);
+ if (retval) {
+ log_debug("Unable to allocate quota handle");
+ goto out;
+ }
+
+ dict = qctx->quota_dict[qtype];
+ if (dict) {
+ retval = quota_file_create(sbi, h, qtype);
+ if (retval) {
+ log_debug("Cannot initialize io on quotafile");
+ } else {
+ write_dquots(dict, h);
+ quota_file_close(sbi, h, 1);
+ }
+ }
+out:
+ if (h)
+ quota_free_mem(&h);
+ return retval;
+}
+
+/******************************************************************/
+/* Helper functions for computing quota in memory. */
+/******************************************************************/
+
+static int dict_uint_cmp(const void *a, const void *b)
+{
+ unsigned int c, d;
+
+ c = VOIDPTR_TO_UINT(a);
+ d = VOIDPTR_TO_UINT(b);
+
+ if (c == d)
+ return 0;
+ else if (c > d)
+ return 1;
+ else
+ return -1;
+}
+
+static inline qid_t get_qid(struct f2fs_inode *inode, enum quota_type qtype)
+{
+ switch (qtype) {
+ case USRQUOTA:
+ return inode->i_uid;
+ case GRPQUOTA:
+ return inode->i_gid;
+ case PRJQUOTA:
+ return inode->i_projid;
+ default:
+ return 0;
+ }
+
+ return 0;
+}
+
+static void quota_dnode_free(dnode_t *node, void *UNUSED(context))
+{
+ void *ptr = node ? dnode_get(node) : 0;
+
+ quota_free_mem(&ptr);
+ free(node);
+}
+
+/*
+ * Set up the quota tracking data structures.
+ */
+errcode_t quota_init_context(struct f2fs_sb_info *sbi)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+ struct f2fs_super_block *sb = F2FS_RAW_SUPER(sbi);
+ errcode_t err;
+ dict_t *dict;
+ quota_ctx_t ctx;
+ enum quota_type qtype;
+
+ err = quota_get_mem(sizeof(struct quota_ctx), &ctx);
+ if (err) {
+ log_debug("Failed to allocate quota context");
+ return err;
+ }
+
+ memset(ctx, 0, sizeof(struct quota_ctx));
+ dict_init(&ctx->linked_inode_dict, DICTCOUNT_T_MAX, dict_uint_cmp);
+ for (qtype = 0; qtype < MAXQUOTAS; qtype++) {
+ ctx->quota_file[qtype] = NULL;
+ if (!sb->qf_ino[qtype])
+ continue;
+ err = quota_get_mem(sizeof(dict_t), &dict);
+ if (err) {
+ log_debug("Failed to allocate dictionary");
+ quota_release_context(&ctx);
+ return err;
+ }
+ ctx->quota_dict[qtype] = dict;
+ dict_init(dict, DICTCOUNT_T_MAX, dict_uint_cmp);
+ dict_set_allocator(dict, NULL, quota_dnode_free, NULL);
+ }
+ ctx->sbi = sbi;
+ fsck->qctx = ctx;
+ return 0;
+}
+
+void quota_release_context(quota_ctx_t *qctx)
+{
+ dict_t *dict;
+ enum quota_type qtype;
+ quota_ctx_t ctx;
+
+ if (!qctx)
+ return;
+
+ ctx = *qctx;
+ for (qtype = 0; qtype < MAXQUOTAS; qtype++) {
+ dict = ctx->quota_dict[qtype];
+ ctx->quota_dict[qtype] = 0;
+ if (dict) {
+ dict_free_nodes(dict);
+ free(dict);
+ }
+ }
+ dict_free_nodes(&ctx->linked_inode_dict);
+ *qctx = NULL;
+ free(ctx);
+}
+
+static struct dquot *get_dq(dict_t *dict, __u32 key)
+{
+ struct dquot *dq;
+ dnode_t *n;
+
+ n = dict_lookup(dict, UINT_TO_VOIDPTR(key));
+ if (n)
+ dq = dnode_get(n);
+ else {
+ if (quota_get_mem(sizeof(struct dquot), &dq)) {
+ log_err("Unable to allocate dquot");
+ return NULL;
+ }
+ memset(dq, 0, sizeof(struct dquot));
+ dict_alloc_insert(dict, UINT_TO_VOIDPTR(key), dq);
+ dq->dq_id = key;
+ }
+ return dq;
+}
+
+/*
+ * Called to update the blocks used by a particular inode
+ */
+void quota_data_add(quota_ctx_t qctx, struct f2fs_inode *inode, qsize_t space)
+{
+ struct dquot *dq;
+ dict_t *dict;
+ enum quota_type qtype;
+
+ if (!qctx)
+ return;
+
+ for (qtype = 0; qtype < MAXQUOTAS; qtype++) {
+ dict = qctx->quota_dict[qtype];
+ if (dict) {
+ dq = get_dq(dict, get_qid(inode, qtype));
+ if (dq)
+ dq->dq_dqb.dqb_curspace += space;
+ }
+ }
+}
+
+/*
+ * Called to remove some blocks used by a particular inode
+ */
+void quota_data_sub(quota_ctx_t qctx, struct f2fs_inode *inode, qsize_t space)
+{
+ struct dquot *dq;
+ dict_t *dict;
+ enum quota_type qtype;
+
+ if (!qctx)
+ return;
+
+ for (qtype = 0; qtype < MAXQUOTAS; qtype++) {
+ dict = qctx->quota_dict[qtype];
+ if (dict) {
+ dq = get_dq(dict, get_qid(inode, qtype));
+ dq->dq_dqb.dqb_curspace -= space;
+ }
+ }
+}
+
+/*
+ * Called to count the files used by an inode's user/group
+ */
+void quota_data_inodes(quota_ctx_t qctx, struct f2fs_inode *inode, int adjust)
+{
+ struct dquot *dq;
+ dict_t *dict; enum quota_type qtype;
+
+ if (!qctx)
+ return;
+
+ for (qtype = 0; qtype < MAXQUOTAS; qtype++) {
+ dict = qctx->quota_dict[qtype];
+ if (dict) {
+ dq = get_dq(dict, get_qid(inode, qtype));
+ dq->dq_dqb.dqb_curinodes += adjust;
+ }
+ }
+}
+
+/*
+ * Called from fsck to count quota.
+ */
+void quota_add_inode_usage(quota_ctx_t qctx, f2fs_ino_t ino,
+ struct f2fs_inode* inode)
+{
+ if (qctx) {
+ /* Handle hard linked inodes */
+ if (inode->i_links > 1) {
+ if (dict_lookup(&qctx->linked_inode_dict,
+ UINT_TO_VOIDPTR(ino))) {
+ return;
+ }
+ dict_alloc_insert(&qctx->linked_inode_dict,
+ UINT_TO_VOIDPTR(ino), NULL);
+ }
+
+ qsize_t space = (inode->i_blocks - 1) * BLOCK_SZ;
+ quota_data_add(qctx, inode, space);
+ quota_data_inodes(qctx, inode, +1);
+ }
+}
+
+struct scan_dquots_data {
+ dict_t *quota_dict;
+ int update_limits; /* update limits from disk */
+ int update_usage;
+ int usage_is_inconsistent;
+};
+
+static int scan_dquots_callback(struct dquot *dquot, void *cb_data)
+{
+ struct scan_dquots_data *scan_data = cb_data;
+ dict_t *quota_dict = scan_data->quota_dict;
+ struct dquot *dq;
+
+ dq = get_dq(quota_dict, dquot->dq_id);
+ dq->dq_id = dquot->dq_id;
+ dq->dq_flags |= DQF_SEEN;
+
+ print_dquot("mem", dq);
+ print_dquot("dsk", dquot);
+ /* Check if there is inconsistency */
+ if (dq->dq_dqb.dqb_curspace != dquot->dq_dqb.dqb_curspace ||
+ dq->dq_dqb.dqb_curinodes != dquot->dq_dqb.dqb_curinodes) {
+ scan_data->usage_is_inconsistent = 1;
+ log_debug("[QUOTA WARNING] Usage inconsistent for ID %u:"
+ "actual (%lld, %lld) != expected (%lld, %lld)\n",
+ dq->dq_id, (long long) dq->dq_dqb.dqb_curspace,
+ (long long) dq->dq_dqb.dqb_curinodes,
+ (long long) dquot->dq_dqb.dqb_curspace,
+ (long long) dquot->dq_dqb.dqb_curinodes);
+ }
+
+ if (scan_data->update_limits) {
+ dq->dq_dqb.dqb_ihardlimit = dquot->dq_dqb.dqb_ihardlimit;
+ dq->dq_dqb.dqb_isoftlimit = dquot->dq_dqb.dqb_isoftlimit;
+ dq->dq_dqb.dqb_bhardlimit = dquot->dq_dqb.dqb_bhardlimit;
+ dq->dq_dqb.dqb_bsoftlimit = dquot->dq_dqb.dqb_bsoftlimit;
+ }
+
+ if (scan_data->update_usage) {
+ dq->dq_dqb.dqb_curspace = dquot->dq_dqb.dqb_curspace;
+ dq->dq_dqb.dqb_curinodes = dquot->dq_dqb.dqb_curinodes;
+ }
+
+ return 0;
+}
+
+/*
+ * Compares the measured quota in qctx->quota_dict with that in the quota inode
+ * on disk and updates the limits in qctx->quota_dict. 'usage_inconsistent' is
+ * set to 1 if the supplied and on-disk quota usage values are not identical.
+ */
+errcode_t quota_compare_and_update(struct f2fs_sb_info *sbi,
+ enum quota_type qtype, int *usage_inconsistent)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+ quota_ctx_t qctx = fsck->qctx;
+ struct quota_handle qh;
+ struct scan_dquots_data scan_data;
+ struct dquot *dq;
+ dnode_t *n;
+ dict_t *dict = qctx->quota_dict[qtype];
+ errcode_t err = 0;
+
+ if (!dict)
+ goto out;
+
+ err = quota_file_open(sbi, &qh, qtype, 0);
+ if (err) {
+ log_debug("Open quota file failed");
+ goto out;
+ }
+
+ scan_data.quota_dict = qctx->quota_dict[qtype];
+ scan_data.update_limits = 1;
+ scan_data.update_usage = 0;
+ scan_data.usage_is_inconsistent = 0;
+ err = qh.qh_ops->scan_dquots(&qh, scan_dquots_callback, &scan_data);
+ if (err) {
+ log_debug("Error scanning dquots");
+ goto out;
+ }
+
+ for (n = dict_first(dict); n; n = dict_next(dict, n)) {
+ dq = dnode_get(n);
+ if (!dq)
+ continue;
+ if ((dq->dq_flags & DQF_SEEN) == 0) {
+ log_debug("[QUOTA WARNING] "
+ "Missing quota entry ID %d\n", dq->dq_id);
+ scan_data.usage_is_inconsistent = 1;
+ }
+ }
+ *usage_inconsistent = scan_data.usage_is_inconsistent;
+
+out:
+ return err;
+}
+
diff --git a/fsck/mount.c b/fsck/mount.c
index 29af3b7..d71e107 100644
--- a/fsck/mount.c
+++ b/fsck/mount.c
@@ -297,6 +297,9 @@ void print_sb_state(struct f2fs_super_block *sb)
if (f & cpu_to_le32(F2FS_FEATURE_FLEXIBLE_INLINE_XATTR)) {
MSG(0, "%s", " flexible inline xattr");
}
+ if (f & cpu_to_le32(F2FS_FEATURE_QUOTA_INO)) {
+ MSG(0, "%s", " quota ino");
+ }
MSG(0, "\n");
MSG(0, "Info: superblock encrypt level = %d, salt = ",
sb->encryption_level);
@@ -739,7 +742,7 @@ static int f2fs_init_nid_bitmap(struct f2fs_sb_info *sbi)
nid_t nid;
int i;
- if (!(c.func == SLOAD))
+ if (!(c.func == SLOAD || c.func == FSCK))
return 0;
nm_i->nid_bitmap = (char *)calloc(nid_bitmap_size, 1);
@@ -2159,10 +2162,14 @@ int f2fs_do_mount(struct f2fs_sb_info *sbi)
if (c.auto_fix || c.preen_mode) {
u32 flag = get_cp(ckpt_flags);
- if (flag & CP_FSCK_FLAG)
+ if (flag & CP_FSCK_FLAG ||
+ (exist_qf_ino(sb) && (!(flag & CP_UMOUNT_FLAG) ||
+ flag & CP_ERROR_FLAG))) {
c.fix_on = 1;
- else if (!c.preen_mode)
+ } else if (!c.preen_mode) {
+ print_cp_state(flag);
return 1;
+ }
}
c.bug_on = 0;
@@ -2224,7 +2231,7 @@ void f2fs_do_umount(struct f2fs_sb_info *sbi)
unsigned int i;
/* free nm_info */
- if (c.func == SLOAD)
+ if (c.func == SLOAD || c.func == FSCK)
free(nm_i->nid_bitmap);
free(nm_i->nat_bitmap);
free(sbi->nm_info);
diff --git a/fsck/quotaio.c b/fsck/quotaio.c
new file mode 100644
index 0000000..afadf56
--- /dev/null
+++ b/fsck/quotaio.c
@@ -0,0 +1,221 @@
+/** quotaio.c
+ *
+ * Generic IO operations on quotafiles
+ * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
+ * Aditya Kali <adityakali@google.com> - Ported to e2fsprogs
+ * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
+ */
+
+#include "config.h"
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <time.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/file.h>
+#include <assert.h>
+
+#include "common.h"
+#include "quotaio.h"
+
+static const char * const extensions[MAXQUOTAS] = {
+ [USRQUOTA] = "user",
+ [GRPQUOTA] = "group",
+ [PRJQUOTA] = "project",
+};
+
+/* Header in all newer quotafiles */
+struct disk_dqheader {
+ __le32 dqh_magic;
+ __le32 dqh_version;
+} __attribute__ ((packed));
+
+/**
+ * Convert type of quota to written representation
+ */
+const char *quota_type2name(enum quota_type qtype)
+{
+ if (qtype >= MAXQUOTAS)
+ return "unknown";
+ return extensions[qtype];
+}
+
+/*
+ * Set grace time if needed
+ */
+void update_grace_times(struct dquot *q)
+{
+ time_t now;
+
+ time(&now);
+ if (q->dq_dqb.dqb_bsoftlimit && toqb(q->dq_dqb.dqb_curspace) >
+ q->dq_dqb.dqb_bsoftlimit) {
+ if (!q->dq_dqb.dqb_btime)
+ q->dq_dqb.dqb_btime =
+ now + q->dq_h->qh_info.dqi_bgrace;
+ } else {
+ q->dq_dqb.dqb_btime = 0;
+ }
+
+ if (q->dq_dqb.dqb_isoftlimit && q->dq_dqb.dqb_curinodes >
+ q->dq_dqb.dqb_isoftlimit) {
+ if (!q->dq_dqb.dqb_itime)
+ q->dq_dqb.dqb_itime =
+ now + q->dq_h->qh_info.dqi_igrace;
+ } else {
+ q->dq_dqb.dqb_itime = 0;
+ }
+}
+
+/* Functions to read/write quota file. */
+static unsigned int quota_write_nomount(struct quota_file *qf,
+ long offset,
+ void *buf, unsigned int size)
+{
+ unsigned int written;
+
+ written = f2fs_write(qf->sbi, qf->ino, buf, size, offset);
+ if (qf->filesize < offset + written)
+ qf->filesize = offset + written;
+
+ return written;
+}
+
+static unsigned int quota_read_nomount(struct quota_file *qf, long offset,
+ void *buf, unsigned int size)
+{
+ return f2fs_read(qf->sbi, qf->ino, buf, size, offset);
+}
+
+/*
+ * Detect quota format and initialize quota IO
+ */
+errcode_t quota_file_open(struct f2fs_sb_info *sbi, struct quota_handle *h,
+ enum quota_type qtype, int flags)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+ struct f2fs_super_block *sb = F2FS_RAW_SUPER(sbi);
+ quota_ctx_t qctx = fsck->qctx;
+ f2fs_ino_t qf_ino;
+ errcode_t err = 0;
+ int allocated_handle = 0;
+
+ if (qtype >= MAXQUOTAS)
+ return EINVAL;
+
+ qf_ino = sb->qf_ino[qtype];
+
+ if (!h) {
+ if (qctx->quota_file[qtype]) {
+ h = qctx->quota_file[qtype];
+ (void) quota_file_close(sbi, h, 0);
+ }
+ err = quota_get_mem(sizeof(struct quota_handle), &h);
+ if (err) {
+ log_err("Unable to allocate quota handle");
+ return err;
+ }
+ allocated_handle = 1;
+ }
+
+ h->qh_qf.sbi = sbi;
+ h->qh_qf.ino = qf_ino;
+ h->write = quota_write_nomount;
+ h->read = quota_read_nomount;
+ h->qh_file_flags = flags;
+ h->qh_io_flags = 0;
+ h->qh_type = qtype;
+ h->qh_fmt = QFMT_VFS_V1;
+ memset(&h->qh_info, 0, sizeof(h->qh_info));
+ h->qh_ops = "afile_ops_2;
+
+ if (h->qh_ops->check_file &&
+ (h->qh_ops->check_file(h, qtype) == 0)) {
+ log_err("qh_ops->check_file failed");
+ err = EIO;
+ goto errout;
+ }
+
+ if (h->qh_ops->init_io && (h->qh_ops->init_io(h) < 0)) {
+ log_err("qh_ops->init_io failed");
+ err = EIO;
+ goto errout;
+ }
+ if (allocated_handle)
+ qctx->quota_file[qtype] = h;
+errout:
+ return err;
+}
+
+/*
+ * Create new quotafile of specified format on given filesystem
+ */
+errcode_t quota_file_create(struct f2fs_sb_info *sbi, struct quota_handle *h,
+ enum quota_type qtype)
+{
+ struct f2fs_super_block *sb = F2FS_RAW_SUPER(sbi);
+ f2fs_ino_t qf_inum = sb->qf_ino[qtype];
+ errcode_t err = 0;
+
+ h->qh_qf.sbi = sbi;
+ h->qh_qf.ino = qf_inum;
+ h->write = quota_write_nomount;
+ h->read = quota_read_nomount;
+
+ log_debug("Creating quota ino=%u, type=%d", qf_inum, qtype);
+ h->qh_io_flags = 0;
+ h->qh_type = qtype;
+ h->qh_fmt = QFMT_VFS_V1;
+ memset(&h->qh_info, 0, sizeof(h->qh_info));
+ h->qh_ops = "afile_ops_2;
+
+ if (h->qh_ops->new_io && (h->qh_ops->new_io(h) < 0)) {
+ log_err("qh_ops->new_io failed");
+ err = EIO;
+ }
+
+ return err;
+}
+
+/*
+ * Close quotafile and release handle
+ */
+errcode_t quota_file_close(struct f2fs_sb_info *sbi, struct quota_handle *h,
+ int update_filesize)
+{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+ quota_ctx_t qctx = fsck->qctx;
+
+ if (h->qh_io_flags & IOFL_INFODIRTY) {
+ if (h->qh_ops->write_info && h->qh_ops->write_info(h) < 0)
+ return EIO;
+ h->qh_io_flags &= ~IOFL_INFODIRTY;
+ }
+ if (h->qh_ops->end_io && h->qh_ops->end_io(h) < 0)
+ return EIO;
+ if (update_filesize) {
+ f2fs_filesize_update(sbi, h->qh_qf.ino, h->qh_qf.filesize);
+ }
+ if (qctx->quota_file[h->qh_type] == h)
+ quota_free_mem(&qctx->quota_file[h->qh_type]);
+ return 0;
+}
+
+/*
+ * Create empty quota structure
+ */
+struct dquot *get_empty_dquot(void)
+{
+ struct dquot *dquot;
+
+ if (quota_get_memzero(sizeof(struct dquot), &dquot)) {
+ log_err("Failed to allocate dquot");
+ return NULL;
+ }
+
+ dquot->dq_id = -1;
+ return dquot;
+}
diff --git a/fsck/quotaio.h b/fsck/quotaio.h
new file mode 100644
index 0000000..e796eb1
--- /dev/null
+++ b/fsck/quotaio.h
@@ -0,0 +1,255 @@
+/** quotaio.h
+ *
+ * Interface to the quota library.
+ *
+ * The quota library provides interface for creating and updating the quota
+ * files and the ext4 superblock fields. It supports the new VFS_V1 quota
+ * format. The quota library also provides support for keeping track of quotas
+ * in memory.
+ *
+ * Aditya Kali <adityakali@google.com>
+ * Header of IO operations for quota utilities
+ *
+ * Jan Kara <jack@suse.cz>
+ *
+ * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
+ */
+
+#ifndef GUARD_QUOTAIO_H
+#define GUARD_QUOTAIO_H
+
+#include <limits.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <arpa/inet.h>
+
+#include "dict.h"
+#include "f2fs_fs.h"
+#include "f2fs.h"
+#include "node.h"
+#include "fsck.h"
+
+#include "dqblk_v2.h"
+
+typedef int64_t qsize_t; /* Type in which we store size limitations */
+typedef int32_t f2fs_ino_t;
+typedef int errcode_t;
+
+enum quota_type {
+ USRQUOTA = 0,
+ GRPQUOTA = 1,
+ PRJQUOTA = 2,
+ MAXQUOTAS = 3,
+};
+
+#if MAXQUOTAS > 32
+#error "cannot have more than 32 quota types to fit in qtype_bits"
+#endif
+
+
+#define QUOTA_USR_BIT (1 << USRQUOTA)
+#define QUOTA_GRP_BIT (1 << GRPQUOTA)
+#define QUOTA_PRJ_BIT (1 << PRJQUOTA)
+#define QUOTA_ALL_BIT (QUOTA_USR_BIT | QUOTA_GRP_BIT | QUOTA_PRJ_BIT)
+
+typedef struct quota_ctx *quota_ctx_t;
+
+struct quota_ctx {
+ struct f2fs_sb_info *sbi;
+ struct dict_t *quota_dict[MAXQUOTAS];
+ struct quota_handle *quota_file[MAXQUOTAS];
+ struct dict_t linked_inode_dict;
+};
+
+/*
+ * Definitions of magics and versions of current quota files
+ */
+#define INITQMAGICS {\
+ 0xd9c01f11, /* USRQUOTA */\
+ 0xd9c01927, /* GRPQUOTA */\
+ 0xd9c03f14 /* PRJQUOTA */\
+}
+
+/* Size of blocks in which are counted size limits in generic utility parts */
+#define QUOTABLOCK_BITS 10
+#define QUOTABLOCK_SIZE (1 << QUOTABLOCK_BITS)
+#define toqb(x) (((x) + QUOTABLOCK_SIZE - 1) >> QUOTABLOCK_BITS)
+
+/* Quota format type IDs */
+#define QFMT_VFS_OLD 1
+#define QFMT_VFS_V0 2
+#define QFMT_VFS_V1 4
+
+/*
+ * The following constants define the default amount of time given a user
+ * before the soft limits are treated as hard limits (usually resulting
+ * in an allocation failure). The timer is started when the user crosses
+ * their soft limit, it is reset when they go below their soft limit.
+ */
+#define MAX_IQ_TIME 604800 /* (7*24*60*60) 1 week */
+#define MAX_DQ_TIME 604800 /* (7*24*60*60) 1 week */
+
+#define IOFL_INFODIRTY 0x01 /* Did info change? */
+
+struct quotafile_ops;
+
+/* Generic information about quotafile */
+struct util_dqinfo {
+ time_t dqi_bgrace; /* Block grace time for given quotafile */
+ time_t dqi_igrace; /* Inode grace time for given quotafile */
+ union {
+ struct v2_mem_dqinfo v2_mdqi;
+ } u; /* Format specific info about quotafile */
+};
+
+struct quota_file {
+ struct f2fs_sb_info *sbi;
+ f2fs_ino_t ino;
+ int64_t filesize;
+};
+
+/* Structure for one opened quota file */
+struct quota_handle {
+ enum quota_type qh_type; /* Type of quotafile */
+ int qh_fmt; /* Quotafile format */
+ int qh_file_flags;
+ int qh_io_flags; /* IO flags for file */
+ struct quota_file qh_qf;
+ unsigned int (*read)(struct quota_file *qf, long offset,
+ void *buf, unsigned int size);
+ unsigned int (*write)(struct quota_file *qf, long offset,
+ void *buf, unsigned int size);
+ struct quotafile_ops *qh_ops; /* Operations on quotafile */
+ struct util_dqinfo qh_info; /* Generic quotafile info */
+};
+
+/* Utility quota block */
+struct util_dqblk {
+ qsize_t dqb_ihardlimit;
+ qsize_t dqb_isoftlimit;
+ qsize_t dqb_curinodes;
+ qsize_t dqb_bhardlimit;
+ qsize_t dqb_bsoftlimit;
+ qsize_t dqb_curspace;
+ time_t dqb_btime;
+ time_t dqb_itime;
+ union {
+ struct v2_mem_dqblk v2_mdqb;
+ } u; /* Format specific dquot information */
+};
+
+/* Structure for one loaded quota */
+struct dquot {
+ struct dquot *dq_next; /* Pointer to next dquot in the list */
+ qid_t dq_id; /* ID dquot belongs to */
+ int dq_flags; /* Some flags for utils */
+ struct quota_handle *dq_h; /* Handle of quotafile for this dquot */
+ struct util_dqblk dq_dqb; /* Parsed data of dquot */
+};
+
+#define DQF_SEEN 0x0001
+
+/* Structure of quotafile operations */
+struct quotafile_ops {
+ /* Check whether quotafile is in our format */
+ int (*check_file) (struct quota_handle *h, int type);
+ /* Open quotafile */
+ int (*init_io) (struct quota_handle *h);
+ /* Create new quotafile */
+ int (*new_io) (struct quota_handle *h);
+ /* Write all changes and close quotafile */
+ int (*end_io) (struct quota_handle *h);
+ /* Write info about quotafile */
+ int (*write_info) (struct quota_handle *h);
+ /* Read dquot into memory */
+ struct dquot *(*read_dquot) (struct quota_handle *h, qid_t id);
+ /* Write given dquot to disk */
+ int (*commit_dquot) (struct dquot *dquot);
+ /* Scan quotafile and call callback on every structure */
+ int (*scan_dquots) (struct quota_handle *h,
+ int (*process_dquot) (struct dquot *dquot,
+ void *data),
+ void *data);
+ /* Function to print format specific file information */
+ int (*report) (struct quota_handle *h, int verbose);
+};
+
+#ifdef __CHECKER__
+# ifndef __bitwise
+# define __bitwise __attribute__((bitwise))
+# endif
+#define __force __attribute__((force))
+#else
+# ifndef __bitwise
+# define __bitwise
+# endif
+#define __force
+#endif
+
+#define be32_to_cpu(n) ntohl(n)
+
+/* Open existing quotafile of given type (and verify its format) on given
+ * filesystem. */
+errcode_t quota_file_open(struct f2fs_sb_info *sbi, struct quota_handle *h,
+ enum quota_type qtype, int flags);
+
+/* Create new quotafile of specified format on given filesystem */
+errcode_t quota_file_create(struct f2fs_sb_info *sbi, struct quota_handle *h,
+ enum quota_type qtype);
+
+/* Close quotafile */
+errcode_t quota_file_close(struct f2fs_sb_info *sbi, struct quota_handle *h,
+ int update_filesize);
+
+/* Get empty quota structure */
+struct dquot *get_empty_dquot(void);
+const char *quota_type2name(enum quota_type qtype);
+void update_grace_times(struct dquot *q);
+
+/* In mkquota.c */
+errcode_t quota_init_context(struct f2fs_sb_info *sbi);
+void quota_data_inodes(quota_ctx_t qctx, struct f2fs_inode *inode, int adjust);
+void quota_data_add(quota_ctx_t qctx, struct f2fs_inode *inode, qsize_t space);
+void quota_data_sub(quota_ctx_t qctx, struct f2fs_inode *inode, qsize_t space);
+errcode_t quota_write_inode(struct f2fs_sb_info *sbi, enum quota_type qtype);
+void quota_add_inode_usage(quota_ctx_t qctx, f2fs_ino_t ino,
+ struct f2fs_inode* inode);
+void quota_release_context(quota_ctx_t *qctx);
+errcode_t quota_compare_and_update(struct f2fs_sb_info *sbi,
+ enum quota_type qtype, int *usage_inconsistent);
+
+static inline errcode_t quota_get_mem(unsigned long size, void *ptr)
+{
+ void *pp;
+
+ pp = malloc(size);
+ if (!pp)
+ return -1;
+ memcpy(ptr, &pp, sizeof (pp));
+ return 0;
+}
+
+static inline errcode_t quota_get_memzero(unsigned long size, void *ptr)
+{
+ void *pp;
+
+ pp = malloc(size);
+ if (!pp)
+ return -1;
+ memset(pp, 0, size);
+ memcpy(ptr, &pp, sizeof(pp));
+ return 0;
+}
+
+static inline errcode_t quota_free_mem(void *ptr)
+{
+ void *p;
+
+ memcpy(&p, ptr, sizeof(p));
+ free(p);
+ p = 0;
+ memcpy(ptr, &p, sizeof(p));
+ return 0;
+}
+
+#endif /* GUARD_QUOTAIO_H */
diff --git a/fsck/quotaio_tree.c b/fsck/quotaio_tree.c
new file mode 100644
index 0000000..5aef228
--- /dev/null
+++ b/fsck/quotaio_tree.c
@@ -0,0 +1,679 @@
+/*
+ * Implementation of new quotafile format
+ *
+ * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
+ * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
+ */
+
+#include "config.h"
+#include <sys/types.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "common.h"
+#include "quotaio_tree.h"
+#include "quotaio.h"
+
+typedef char *dqbuf_t;
+
+#define freedqbuf(buf) quota_free_mem(&buf)
+
+static inline dqbuf_t getdqbuf(void)
+{
+ dqbuf_t buf;
+ if (quota_get_memzero(QT_BLKSIZE, &buf)) {
+ log_err("Failed to allocate dqbuf");
+ return NULL;
+ }
+
+ return buf;
+}
+
+/* Is given dquot empty? */
+int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
+{
+ unsigned int i;
+
+ for (i = 0; i < info->dqi_entry_size; i++)
+ if (disk[i])
+ return 0;
+ return 1;
+}
+
+int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
+{
+ return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) /
+ info->dqi_entry_size;
+}
+
+static int get_index(qid_t id, int depth)
+{
+ return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff;
+}
+
+static inline void mark_quotafile_info_dirty(struct quota_handle *h)
+{
+ h->qh_io_flags |= IOFL_INFODIRTY;
+}
+
+/* Read given block */
+static void read_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
+{
+ int err;
+
+ err = h->read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
+ QT_BLKSIZE);
+ if (err < 0)
+ log_err("Cannot read block %u: %s", blk, strerror(errno));
+ else if (err != QT_BLKSIZE)
+ memset(buf + err, 0, QT_BLKSIZE - err);
+}
+
+/* Write block */
+static int write_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
+{
+ int err;
+
+ err = h->write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
+ QT_BLKSIZE);
+ if (err < 0 && errno != ENOSPC)
+ log_err("Cannot write block (%u): %s", blk, strerror(errno));
+ if (err != QT_BLKSIZE)
+ return -ENOSPC;
+ return 0;
+}
+
+/* Get free block in file (either from free list or create new one) */
+static int get_free_dqblk(struct quota_handle *h)
+{
+ dqbuf_t buf = getdqbuf();
+ struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+ int blk;
+
+ if (!buf)
+ return -ENOMEM;
+
+ if (info->dqi_free_blk) {
+ blk = info->dqi_free_blk;
+ read_blk(h, blk, buf);
+ info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free);
+ } else {
+ memset(buf, 0, QT_BLKSIZE);
+ /* Assure block allocation... */
+ if (write_blk(h, info->dqi_blocks, buf) < 0) {
+ freedqbuf(buf);
+ log_err("Cannot allocate new quota block "
+ "(out of disk space).");
+ return -ENOSPC;
+ }
+ blk = info->dqi_blocks++;
+ }
+ mark_quotafile_info_dirty(h);
+ freedqbuf(buf);
+ return blk;
+}
+
+/* Put given block to free list */
+static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf,
+ unsigned int blk)
+{
+ struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+
+ dh->dqdh_next_free = cpu_to_le32(info->dqi_free_blk);
+ dh->dqdh_prev_free = cpu_to_le32(0);
+ dh->dqdh_entries = cpu_to_le16(0);
+ info->dqi_free_blk = blk;
+ mark_quotafile_info_dirty(h);
+ write_blk(h, blk, buf);
+}
+
+/* Remove given block from the list of blocks with free entries */
+static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf,
+ unsigned int blk)
+{
+ dqbuf_t tmpbuf = getdqbuf();
+ struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
+ unsigned int nextblk = le32_to_cpu(dh->dqdh_next_free), prevblk =
+ le32_to_cpu(dh->dqdh_prev_free);
+
+ if (!tmpbuf)
+ return;
+
+ if (nextblk) {
+ read_blk(h, nextblk, tmpbuf);
+ ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
+ dh->dqdh_prev_free;
+ write_blk(h, nextblk, tmpbuf);
+ }
+ if (prevblk) {
+ read_blk(h, prevblk, tmpbuf);
+ ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free =
+ dh->dqdh_next_free;
+ write_blk(h, prevblk, tmpbuf);
+ } else {
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = nextblk;
+ mark_quotafile_info_dirty(h);
+ }
+ freedqbuf(tmpbuf);
+ dh->dqdh_next_free = dh->dqdh_prev_free = cpu_to_le32(0);
+ write_blk(h, blk, buf); /* No matter whether write succeeds
+ * block is out of list */
+}
+
+/* Insert given block to the beginning of list with free entries */
+static void insert_free_dqentry(struct quota_handle *h, dqbuf_t buf,
+ unsigned int blk)
+{
+ dqbuf_t tmpbuf = getdqbuf();
+ struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+
+ if (!tmpbuf)
+ return;
+
+ dh->dqdh_next_free = cpu_to_le32(info->dqi_free_entry);
+ dh->dqdh_prev_free = cpu_to_le32(0);
+ write_blk(h, blk, buf);
+ if (info->dqi_free_entry) {
+ read_blk(h, info->dqi_free_entry, tmpbuf);
+ ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
+ cpu_to_le32(blk);
+ write_blk(h, info->dqi_free_entry, tmpbuf);
+ }
+ freedqbuf(tmpbuf);
+ info->dqi_free_entry = blk;
+ mark_quotafile_info_dirty(h);
+}
+
+/* Find space for dquot */
+static unsigned int find_free_dqentry(struct quota_handle *h,
+ struct dquot *dquot, int *err)
+{
+ int blk, i;
+ struct qt_disk_dqdbheader *dh;
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+ char *ddquot;
+ dqbuf_t buf;
+
+ *err = 0;
+ buf = getdqbuf();
+ if (!buf) {
+ *err = -ENOMEM;
+ return 0;
+ }
+
+ dh = (struct qt_disk_dqdbheader *)buf;
+ if (info->dqi_free_entry) {
+ blk = info->dqi_free_entry;
+ read_blk(h, blk, buf);
+ } else {
+ blk = get_free_dqblk(h);
+ if (blk < 0) {
+ freedqbuf(buf);
+ *err = blk;
+ return 0;
+ }
+ memset(buf, 0, QT_BLKSIZE);
+ info->dqi_free_entry = blk;
+ mark_quotafile_info_dirty(h);
+ }
+
+ /* Block will be full? */
+ if (le16_to_cpu(dh->dqdh_entries) + 1 >=
+ qtree_dqstr_in_blk(info))
+ remove_free_dqentry(h, buf, blk);
+
+ dh->dqdh_entries =
+ cpu_to_le16(le16_to_cpu(dh->dqdh_entries) + 1);
+ /* Find free structure in block */
+ ddquot = buf + sizeof(struct qt_disk_dqdbheader);
+ for (i = 0;
+ i < qtree_dqstr_in_blk(info) && !qtree_entry_unused(info, ddquot);
+ i++)
+ ddquot += info->dqi_entry_size;
+
+ if (i == qtree_dqstr_in_blk(info))
+ log_err("find_free_dqentry(): Data block full unexpectedly.");
+
+ write_blk(h, blk, buf);
+ dquot->dq_dqb.u.v2_mdqb.dqb_off =
+ (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
+ i * info->dqi_entry_size;
+ freedqbuf(buf);
+ return blk;
+}
+
+/* Insert reference to structure into the trie */
+static int do_insert_tree(struct quota_handle *h, struct dquot *dquot,
+ unsigned int * treeblk, int depth)
+{
+ dqbuf_t buf;
+ int newson = 0, newact = 0;
+ __le32 *ref;
+ unsigned int newblk;
+ int ret = 0;
+
+ log_debug("inserting in tree: treeblk=%u, depth=%d", *treeblk, depth);
+ buf = getdqbuf();
+ if (!buf)
+ return -ENOMEM;
+
+ if (!*treeblk) {
+ ret = get_free_dqblk(h);
+ if (ret < 0)
+ goto out_buf;
+ *treeblk = ret;
+ memset(buf, 0, QT_BLKSIZE);
+ newact = 1;
+ } else {
+ read_blk(h, *treeblk, buf);
+ }
+
+ ref = (__le32 *) buf;
+ newblk = le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
+ if (!newblk)
+ newson = 1;
+ if (depth == QT_TREEDEPTH - 1) {
+ if (newblk)
+ log_err("Inserting already present quota entry "
+ "(block %u).",
+ ref[get_index(dquot->dq_id, depth)]);
+ newblk = find_free_dqentry(h, dquot, &ret);
+ } else {
+ ret = do_insert_tree(h, dquot, &newblk, depth + 1);
+ }
+
+ if (newson && ret >= 0) {
+ ref[get_index(dquot->dq_id, depth)] =
+ cpu_to_le32(newblk);
+ write_blk(h, *treeblk, buf);
+ } else if (newact && ret < 0) {
+ put_free_dqblk(h, buf, *treeblk);
+ }
+
+out_buf:
+ freedqbuf(buf);
+ return ret;
+}
+
+/* Wrapper for inserting quota structure into tree */
+static void dq_insert_tree(struct quota_handle *h, struct dquot *dquot)
+{
+ unsigned int tmp = QT_TREEOFF;
+
+ if (do_insert_tree(h, dquot, &tmp, 0) < 0)
+ log_err("Cannot write quota (id %u): %s",
+ (unsigned int) dquot->dq_id, strerror(errno));
+}
+
+/* Write dquot to file */
+void qtree_write_dquot(struct dquot *dquot)
+{
+ errcode_t retval;
+ unsigned int ret;
+ char *ddquot;
+ struct quota_handle *h = dquot->dq_h;
+ struct qtree_mem_dqinfo *info =
+ &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
+
+
+ log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u",
+ dquot->dq_dqb.u.v2_mdqb.dqb_off,
+ info->dqi_entry_size);
+ retval = quota_get_mem(info->dqi_entry_size, &ddquot);
+ if (retval) {
+ errno = ENOMEM;
+ log_err("Quota write failed (id %u): %s",
+ (unsigned int)dquot->dq_id, strerror(errno));
+ return;
+ }
+ memset(ddquot, 0, info->dqi_entry_size);
+
+ if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) {
+ dq_insert_tree(dquot->dq_h, dquot);
+ }
+ info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
+ log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u",
+ dquot->dq_dqb.u.v2_mdqb.dqb_off,
+ info->dqi_entry_size);
+ ret = h->write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot,
+ info->dqi_entry_size);
+
+ if (ret != info->dqi_entry_size) {
+ if (ret > 0)
+ errno = ENOSPC;
+ log_err("Quota write failed (id %u): %s",
+ (unsigned int)dquot->dq_id, strerror(errno));
+ }
+ quota_free_mem(&ddquot);
+}
+
+/* Free dquot entry in data block */
+static void free_dqentry(struct quota_handle *h, struct dquot *dquot,
+ unsigned int blk)
+{
+ struct qt_disk_dqdbheader *dh;
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+ dqbuf_t buf = getdqbuf();
+
+ if (!buf)
+ return;
+
+ if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk)
+ log_err("Quota structure has offset to other block (%u) "
+ "than it should (%u).", blk,
+ (unsigned int) (dquot->dq_dqb.u.v2_mdqb.dqb_off >>
+ QT_BLKSIZE_BITS));
+
+ read_blk(h, blk, buf);
+ dh = (struct qt_disk_dqdbheader *)buf;
+ dh->dqdh_entries =
+ cpu_to_le16(le16_to_cpu(dh->dqdh_entries) - 1);
+
+ if (!le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */
+ remove_free_dqentry(h, buf, blk);
+ put_free_dqblk(h, buf, blk);
+ } else {
+ memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off &
+ ((1 << QT_BLKSIZE_BITS) - 1)),
+ 0, info->dqi_entry_size);
+
+ /* First free entry? */
+ if (le16_to_cpu(dh->dqdh_entries) ==
+ qtree_dqstr_in_blk(info) - 1)
+ /* This will also write data block */
+ insert_free_dqentry(h, buf, blk);
+ else
+ write_blk(h, blk, buf);
+ }
+ dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
+ freedqbuf(buf);
+}
+
+/* Remove reference to dquot from tree */
+static void remove_tree(struct quota_handle *h, struct dquot *dquot,
+ unsigned int * blk, int depth)
+{
+ dqbuf_t buf = getdqbuf();
+ unsigned int newblk;
+ __le32 *ref = (__le32 *) buf;
+
+ if (!buf)
+ return;
+
+ read_blk(h, *blk, buf);
+ newblk = le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
+ if (depth == QT_TREEDEPTH - 1) {
+ free_dqentry(h, dquot, newblk);
+ newblk = 0;
+ } else {
+ remove_tree(h, dquot, &newblk, depth + 1);
+ }
+
+ if (!newblk) {
+ int i;
+
+ ref[get_index(dquot->dq_id, depth)] = cpu_to_le32(0);
+
+ /* Block got empty? */
+ for (i = 0; i < QT_BLKSIZE && !buf[i]; i++);
+
+ /* Don't put the root block into the free block list */
+ if (i == QT_BLKSIZE && *blk != QT_TREEOFF) {
+ put_free_dqblk(h, buf, *blk);
+ *blk = 0;
+ } else {
+ write_blk(h, *blk, buf);
+ }
+ }
+ freedqbuf(buf);
+}
+
+/* Delete dquot from tree */
+void qtree_delete_dquot(struct dquot *dquot)
+{
+ unsigned int tmp = QT_TREEOFF;
+
+ if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) /* Even not allocated? */
+ return;
+ remove_tree(dquot->dq_h, dquot, &tmp, 0);
+}
+
+/* Find entry in block */
+static long find_block_dqentry(struct quota_handle *h,
+ struct dquot *dquot, unsigned int blk)
+{
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+ dqbuf_t buf = getdqbuf();
+ int i;
+ char *ddquot = buf + sizeof(struct qt_disk_dqdbheader);
+
+ if (!buf)
+ return -ENOMEM;
+
+ read_blk(h, blk, buf);
+ for (i = 0;
+ i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot);
+ i++)
+ ddquot += info->dqi_entry_size;
+
+ if (i == qtree_dqstr_in_blk(info))
+ log_err("Quota for id %u referenced but not present.",
+ dquot->dq_id);
+ freedqbuf(buf);
+ return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
+ i * info->dqi_entry_size;
+}
+
+/* Find entry for given id in the tree */
+static long find_tree_dqentry(struct quota_handle *h,
+ struct dquot *dquot,
+ unsigned int blk, int depth)
+{
+ dqbuf_t buf = getdqbuf();
+ long ret = 0;
+ __le32 *ref = (__le32 *) buf;
+
+ if (!buf)
+ return -ENOMEM;
+
+ read_blk(h, blk, buf);
+ ret = 0;
+ blk = le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
+ if (!blk) /* No reference? */
+ goto out_buf;
+ if (depth < QT_TREEDEPTH - 1)
+ ret = find_tree_dqentry(h, dquot, blk, depth + 1);
+ else
+ ret = find_block_dqentry(h, dquot, blk);
+out_buf:
+ freedqbuf(buf);
+ return ret;
+}
+
+/* Find entry for given id in the tree - wrapper function */
+static inline long find_dqentry(struct quota_handle *h,
+ struct dquot *dquot)
+{
+ return find_tree_dqentry(h, dquot, QT_TREEOFF, 0);
+}
+
+/*
+ * Read dquot from disk.
+ */
+struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id)
+{
+ struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
+ long offset;
+ unsigned int ret;
+ char *ddquot;
+ struct dquot *dquot = get_empty_dquot();
+
+ if (!dquot)
+ return NULL;
+ if (quota_get_mem(info->dqi_entry_size, &ddquot)) {
+ quota_free_mem(&dquot);
+ return NULL;
+ }
+
+ dquot->dq_id = id;
+ dquot->dq_h = h;
+ dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
+ memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk));
+
+ offset = find_dqentry(h, dquot);
+ if (offset > 0) {
+ dquot->dq_dqb.u.v2_mdqb.dqb_off = offset;
+ ret = h->read(&h->qh_qf, offset, ddquot,
+ info->dqi_entry_size);
+ if (ret != info->dqi_entry_size) {
+ if (ret > 0)
+ errno = EIO;
+ log_err("Cannot read quota structure for id %u: %s",
+ dquot->dq_id, strerror(errno));
+ }
+ info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
+ }
+ quota_free_mem(&ddquot);
+ return dquot;
+}
+
+/*
+ * Scan all dquots in file and call callback on each
+ */
+#define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7)))
+#define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7)))
+
+static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap,
+ int (*process_dquot) (struct dquot *, void *),
+ void *data)
+{
+ struct qtree_mem_dqinfo *info =
+ &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
+ dqbuf_t buf = getdqbuf();
+ struct qt_disk_dqdbheader *dh;
+ char *ddata;
+ int entries, i;
+
+ if (!buf)
+ return 0;
+
+ set_bit(bitmap, blk);
+ read_blk(dquot->dq_h, blk, buf);
+ dh = (struct qt_disk_dqdbheader *)buf;
+ ddata = buf + sizeof(struct qt_disk_dqdbheader);
+ entries = le16_to_cpu(dh->dqdh_entries);
+ for (i = 0; i < qtree_dqstr_in_blk(info);
+ i++, ddata += info->dqi_entry_size)
+ if (!qtree_entry_unused(info, ddata)) {
+ dquot->dq_dqb.u.v2_mdqb.dqb_off =
+ (blk << QT_BLKSIZE_BITS) +
+ sizeof(struct qt_disk_dqdbheader) +
+ i * info->dqi_entry_size;
+ info->dqi_ops->disk2mem_dqblk(dquot, ddata);
+ if (process_dquot(dquot, data) < 0)
+ break;
+ }
+ freedqbuf(buf);
+ return entries;
+}
+
+static int check_reference(struct quota_handle *h, unsigned int blk)
+{
+ if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) {
+ log_err("Illegal reference (%u >= %u) in %s quota file. "
+ "Quota file is probably corrupted.\n"
+ "Please run fsck (8) to fix it.",
+ blk,
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks,
+ quota_type2name(h->qh_type));
+ return -1;
+ }
+ return 0;
+}
+
+/* Return 0 for successful run */
+static int report_tree(struct dquot *dquot, unsigned int blk, int depth,
+ char *bitmap, int *entries,
+ int (*process_dquot) (struct dquot *, void *),
+ void *data)
+{
+ int i;
+ dqbuf_t buf = getdqbuf();
+ __le32 *ref = (__le32 *) buf;
+
+ if (!buf)
+ return -1;
+
+ read_blk(dquot->dq_h, blk, buf);
+ for (i = 0; i < QT_BLKSIZE >> 2; i++) {
+ blk = le32_to_cpu(ref[i]);
+ if (blk == 0)
+ continue;
+
+ if (check_reference(dquot->dq_h, blk))
+ break;
+
+ if (depth == QT_TREEDEPTH - 1) {
+ if (!get_bit(bitmap, blk))
+ *entries += report_block(dquot, blk, bitmap,
+ process_dquot, data);
+ } else {
+ if (report_tree(dquot, blk, depth + 1, bitmap, entries,
+ process_dquot, data))
+ break;
+ }
+ }
+ freedqbuf(buf);
+ return (i < QT_BLKSIZE >> 2) ? -1 : 0;
+}
+
+static unsigned int find_set_bits(char *bmp, int blocks)
+{
+ unsigned int used = 0;
+ int i;
+
+ for (i = 0; i < blocks; i++)
+ if (get_bit(bmp, i))
+ used++;
+ return used;
+}
+
+int qtree_scan_dquots(struct quota_handle *h,
+ int (*process_dquot) (struct dquot *, void *),
+ void *data)
+{
+ struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi;
+ struct qtree_mem_dqinfo *info = &v2info->dqi_qtree;
+ struct dquot *dquot = get_empty_dquot();
+ char *bitmap = NULL;
+ int ret = -1;
+ int entries = 0;
+
+ if (!dquot)
+ return -1;
+
+ dquot->dq_h = h;
+ if (quota_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap))
+ goto out;
+ if (report_tree(dquot, QT_TREEOFF, 0, bitmap, &entries, process_dquot,
+ data))
+ goto out;
+
+ v2info->dqi_used_entries = entries;
+ v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks);
+ ret = 0;
+
+out:
+ if (bitmap)
+ quota_free_mem(&bitmap);
+ if (dquot)
+ quota_free_mem(&dquot);
+
+ return ret;
+}
diff --git a/fsck/quotaio_tree.h b/fsck/quotaio_tree.h
new file mode 100644
index 0000000..4ca2d7f
--- /dev/null
+++ b/fsck/quotaio_tree.h
@@ -0,0 +1,66 @@
+/*
+ * Definitions of structures for vfsv0 quota format
+ */
+
+#ifndef _LINUX_QUOTA_TREE_H
+#define _LINUX_QUOTA_TREE_H
+
+#include <inttypes.h>
+#include <linux/types.h>
+#include <sys/types.h>
+
+typedef __u32 qid_t; /* Type in which we store ids in memory */
+
+#define QT_TREEOFF 1 /* Offset of tree in file in blocks */
+#define QT_TREEDEPTH 4 /* Depth of quota tree */
+#define QT_BLKSIZE_BITS 10
+#define QT_BLKSIZE (1 << QT_BLKSIZE_BITS) /* Size of block with quota
+ * structures */
+
+/*
+ * Structure of header of block with quota structures. It is padded to 16 bytes
+ * so there will be space for exactly 21 quota-entries in a block
+ */
+struct qt_disk_dqdbheader {
+ __le32 dqdh_next_free; /* Number of next block with free
+ * entry */
+ __le32 dqdh_prev_free; /* Number of previous block with free
+ * entry */
+ __le16 dqdh_entries; /* Number of valid entries in block */
+ __le16 dqdh_pad1;
+ __le32 dqdh_pad2;
+} __attribute__ ((packed));
+
+struct dquot;
+struct quota_handle;
+
+/* Operations */
+struct qtree_fmt_operations {
+ /* Convert given entry from in memory format to disk one */
+ void (*mem2disk_dqblk)(void *disk, struct dquot *dquot);
+ /* Convert given entry from disk format to in memory one */
+ void (*disk2mem_dqblk)(struct dquot *dquot, void *disk);
+ /* Is this structure for given id? */
+ int (*is_id)(void *disk, struct dquot *dquot);
+};
+
+/* Inmemory copy of version specific information */
+struct qtree_mem_dqinfo {
+ unsigned int dqi_blocks; /* # of blocks in quota file */
+ unsigned int dqi_free_blk; /* First block in list of free blocks */
+ unsigned int dqi_free_entry; /* First block with free entry */
+ unsigned int dqi_entry_size; /* Size of quota entry in quota file */
+ struct qtree_fmt_operations *dqi_ops; /* Operations for entry
+ * manipulation */
+};
+
+void qtree_write_dquot(struct dquot *dquot);
+struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id);
+void qtree_delete_dquot(struct dquot *dquot);
+int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk);
+int qtree_scan_dquots(struct quota_handle *h,
+ int (*process_dquot) (struct dquot *, void *), void *data);
+
+int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info);
+
+#endif /* _LINUX_QUOTAIO_TREE_H */
diff --git a/fsck/quotaio_v2.c b/fsck/quotaio_v2.c
new file mode 100644
index 0000000..478cd17
--- /dev/null
+++ b/fsck/quotaio_v2.c
@@ -0,0 +1,284 @@
+/*
+ * Implementation of new quotafile format
+ *
+ * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
+ * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
+ */
+
+#include "config.h"
+#include <sys/types.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "common.h"
+
+#include "quotaio_v2.h"
+#include "dqblk_v2.h"
+#include "quotaio_tree.h"
+
+static int v2_check_file(struct quota_handle *h, int type);
+static int v2_init_io(struct quota_handle *h);
+static int v2_new_io(struct quota_handle *h);
+static int v2_write_info(struct quota_handle *h);
+static struct dquot *v2_read_dquot(struct quota_handle *h, qid_t id);
+static int v2_commit_dquot(struct dquot *dquot);
+static int v2_scan_dquots(struct quota_handle *h,
+ int (*process_dquot) (struct dquot *dquot,
+ void *data),
+ void *data);
+static int v2_report(struct quota_handle *h, int verbose);
+
+struct quotafile_ops quotafile_ops_2 = {
+ .check_file = v2_check_file,
+ .init_io = v2_init_io,
+ .new_io = v2_new_io,
+ .write_info = v2_write_info,
+ .read_dquot = v2_read_dquot,
+ .commit_dquot = v2_commit_dquot,
+ .scan_dquots = v2_scan_dquots,
+ .report = v2_report,
+};
+
+/*
+ * Copy dquot from disk to memory
+ */
+static void v2r1_disk2memdqblk(struct dquot *dquot, void *dp)
+{
+ struct util_dqblk *m = &dquot->dq_dqb;
+ struct v2r1_disk_dqblk *d = dp, empty;
+
+ dquot->dq_id = le32_to_cpu(d->dqb_id);
+ m->dqb_ihardlimit = le64_to_cpu(d->dqb_ihardlimit);
+ m->dqb_isoftlimit = le64_to_cpu(d->dqb_isoftlimit);
+ m->dqb_bhardlimit = le64_to_cpu(d->dqb_bhardlimit);
+ m->dqb_bsoftlimit = le64_to_cpu(d->dqb_bsoftlimit);
+ m->dqb_curinodes = le64_to_cpu(d->dqb_curinodes);
+ m->dqb_curspace = le64_to_cpu(d->dqb_curspace);
+ m->dqb_itime = le64_to_cpu(d->dqb_itime);
+ m->dqb_btime = le64_to_cpu(d->dqb_btime);
+
+ memset(&empty, 0, sizeof(struct v2r1_disk_dqblk));
+ empty.dqb_itime = cpu_to_le64(1);
+ if (!memcmp(&empty, dp, sizeof(struct v2r1_disk_dqblk)))
+ m->dqb_itime = 0;
+}
+
+/*
+ * Copy dquot from memory to disk
+ */
+static void v2r1_mem2diskdqblk(void *dp, struct dquot *dquot)
+{
+ struct util_dqblk *m = &dquot->dq_dqb;
+ struct v2r1_disk_dqblk *d = dp;
+
+ d->dqb_ihardlimit = cpu_to_le64(m->dqb_ihardlimit);
+ d->dqb_isoftlimit = cpu_to_le64(m->dqb_isoftlimit);
+ d->dqb_bhardlimit = cpu_to_le64(m->dqb_bhardlimit);
+ d->dqb_bsoftlimit = cpu_to_le64(m->dqb_bsoftlimit);
+ d->dqb_curinodes = cpu_to_le64(m->dqb_curinodes);
+ d->dqb_curspace = cpu_to_le64(m->dqb_curspace);
+ d->dqb_itime = cpu_to_le64(m->dqb_itime);
+ d->dqb_btime = cpu_to_le64(m->dqb_btime);
+ d->dqb_id = cpu_to_le32(dquot->dq_id);
+ if (qtree_entry_unused(&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree, dp))
+ d->dqb_itime = cpu_to_le64(1);
+}
+
+static int v2r1_is_id(void *dp, struct dquot *dquot)
+{
+ struct v2r1_disk_dqblk *d = dp;
+ struct qtree_mem_dqinfo *info =
+ &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
+
+ if (qtree_entry_unused(info, dp))
+ return 0;
+ return le32_to_cpu(d->dqb_id) == dquot->dq_id;
+}
+
+static struct qtree_fmt_operations v2r1_fmt_ops = {
+ .mem2disk_dqblk = v2r1_mem2diskdqblk,
+ .disk2mem_dqblk = v2r1_disk2memdqblk,
+ .is_id = v2r1_is_id,
+};
+
+/*
+ * Copy dqinfo from disk to memory
+ */
+static inline void v2_disk2memdqinfo(struct util_dqinfo *m,
+ struct v2_disk_dqinfo *d)
+{
+ m->dqi_bgrace = le32_to_cpu(d->dqi_bgrace);
+ m->dqi_igrace = le32_to_cpu(d->dqi_igrace);
+ m->u.v2_mdqi.dqi_flags = le32_to_cpu(d->dqi_flags) & V2_DQF_MASK;
+ m->u.v2_mdqi.dqi_qtree.dqi_blocks = le32_to_cpu(d->dqi_blocks);
+ m->u.v2_mdqi.dqi_qtree.dqi_free_blk =
+ le32_to_cpu(d->dqi_free_blk);
+ m->u.v2_mdqi.dqi_qtree.dqi_free_entry =
+ le32_to_cpu(d->dqi_free_entry);
+}
+
+/*
+ * Copy dqinfo from memory to disk
+ */
+static inline void v2_mem2diskdqinfo(struct v2_disk_dqinfo *d,
+ struct util_dqinfo *m)
+{
+ d->dqi_bgrace = cpu_to_le32(m->dqi_bgrace);
+ d->dqi_igrace = cpu_to_le32(m->dqi_igrace);
+ d->dqi_flags = cpu_to_le32(m->u.v2_mdqi.dqi_flags & V2_DQF_MASK);
+ d->dqi_blocks = cpu_to_le32(m->u.v2_mdqi.dqi_qtree.dqi_blocks);
+ d->dqi_free_blk =
+ cpu_to_le32(m->u.v2_mdqi.dqi_qtree.dqi_free_blk);
+ d->dqi_free_entry =
+ cpu_to_le32(m->u.v2_mdqi.dqi_qtree.dqi_free_entry);
+}
+
+static int v2_read_header(struct quota_handle *h, struct v2_disk_dqheader *dqh)
+{
+ if (h->read(&h->qh_qf, 0, dqh, sizeof(struct v2_disk_dqheader)) !=
+ sizeof(struct v2_disk_dqheader))
+ return 0;
+
+ return 1;
+}
+
+/*
+ * Check whether given quota file is in our format
+ */
+static int v2_check_file(struct quota_handle *h, int type)
+{
+ struct v2_disk_dqheader dqh;
+ int file_magics[] = INITQMAGICS;
+ int be_magic;
+
+ if (!v2_read_header(h, &dqh))
+ return 0;
+
+ be_magic = be32_to_cpu((__force __be32)dqh.dqh_magic);
+ if (be_magic == file_magics[type]) {
+ log_err("Your quota file is stored in wrong endianity");
+ return 0;
+ }
+ if (V2_VERSION != le32_to_cpu(dqh.dqh_version))
+ return 0;
+ return 1;
+}
+
+/*
+ * Open quotafile
+ */
+static int v2_init_io(struct quota_handle *h)
+{
+ struct v2_disk_dqinfo ddqinfo;
+
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_entry_size =
+ sizeof(struct v2r1_disk_dqblk);
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_ops = &v2r1_fmt_ops;
+
+ /* Read information about quotafile */
+ if (h->read(&h->qh_qf, V2_DQINFOOFF, &ddqinfo,
+ sizeof(ddqinfo)) != sizeof(ddqinfo))
+ return -1;
+ v2_disk2memdqinfo(&h->qh_info, &ddqinfo);
+ return 0;
+}
+
+/*
+ * Initialize new quotafile
+ */
+static int v2_new_io(struct quota_handle *h)
+{
+ int file_magics[] = INITQMAGICS;
+ struct v2_disk_dqheader ddqheader;
+ struct v2_disk_dqinfo ddqinfo;
+
+ if (h->qh_fmt != QFMT_VFS_V1)
+ return -1;
+
+ /* Write basic quota header */
+ ddqheader.dqh_magic = cpu_to_le32(file_magics[h->qh_type]);
+ ddqheader.dqh_version = cpu_to_le32(V2_VERSION);
+ if (h->write(&h->qh_qf, 0, &ddqheader, sizeof(ddqheader)) !=
+ sizeof(ddqheader))
+ return -1;
+
+ /* Write information about quotafile */
+ h->qh_info.dqi_bgrace = MAX_DQ_TIME;
+ h->qh_info.dqi_igrace = MAX_IQ_TIME;
+ h->qh_info.u.v2_mdqi.dqi_flags = 0;
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks = QT_TREEOFF + 1;
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_blk = 0;
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = 0;
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_entry_size =
+ sizeof(struct v2r1_disk_dqblk);
+ h->qh_info.u.v2_mdqi.dqi_qtree.dqi_ops = &v2r1_fmt_ops;
+ v2_mem2diskdqinfo(&ddqinfo, &h->qh_info);
+ if (h->write(&h->qh_qf, V2_DQINFOOFF, &ddqinfo,
+ sizeof(ddqinfo)) !=
+ sizeof(ddqinfo))
+ return -1;
+
+ return 0;
+}
+
+/*
+ * Write information (grace times to file)
+ */
+static int v2_write_info(struct quota_handle *h)
+{
+ struct v2_disk_dqinfo ddqinfo;
+
+ v2_mem2diskdqinfo(&ddqinfo, &h->qh_info);
+ if (h->write(&h->qh_qf, V2_DQINFOOFF, &ddqinfo, sizeof(ddqinfo)) !=
+ sizeof(ddqinfo))
+ return -1;
+
+ return 0;
+}
+
+/*
+ * Read dquot from disk
+ */
+static struct dquot *v2_read_dquot(struct quota_handle *h, qid_t id)
+{
+ return qtree_read_dquot(h, id);
+}
+
+/*
+ * Commit changes of dquot to disk - it might also mean deleting it when quota
+ * became fake one and user has no blocks.
+ * User can process use 'errno' to detect errstr.
+ */
+static int v2_commit_dquot(struct dquot *dquot)
+{
+ struct util_dqblk *b = &dquot->dq_dqb;
+
+ if (!b->dqb_curspace && !b->dqb_curinodes && !b->dqb_bsoftlimit &&
+ !b->dqb_isoftlimit && !b->dqb_bhardlimit && !b->dqb_ihardlimit)
+ {
+ qtree_delete_dquot(dquot);
+ } else {
+ qtree_write_dquot(dquot);
+ }
+ return 0;
+}
+
+static int v2_scan_dquots(struct quota_handle *h,
+ int (*process_dquot) (struct dquot *, void *),
+ void *data)
+{
+ return qtree_scan_dquots(h, process_dquot, data);
+}
+
+/* Report information about quotafile.
+ * TODO: Not used right now, but we should be able to use this when we add
+ * support to debugfs to read quota files.
+ */
+static int v2_report(struct quota_handle *UNUSED(h), int UNUSED(verbose))
+{
+ log_err("Not Implemented.");
+ return -1;
+}
diff --git a/fsck/quotaio_v2.h b/fsck/quotaio_v2.h
new file mode 100644
index 0000000..de2db27
--- /dev/null
+++ b/fsck/quotaio_v2.h
@@ -0,0 +1,54 @@
+/*
+ *
+ * Header file for disk format of new quotafile format
+ *
+ */
+
+#ifndef GUARD_QUOTAIO_V2_H
+#define GUARD_QUOTAIO_V2_H
+
+#include <sys/types.h>
+#include "quotaio.h"
+
+/* Offset of info header in file */
+#define V2_DQINFOOFF sizeof(struct v2_disk_dqheader)
+/* Supported version of quota-tree format */
+#define V2_VERSION 1
+
+struct v2_disk_dqheader {
+ __le32 dqh_magic; /* Magic number identifying file */
+ __le32 dqh_version; /* File version */
+} __attribute__ ((packed));
+
+/* Flags for version specific files */
+#define V2_DQF_MASK 0x0000 /* Mask for all valid ondisk flags */
+
+/* Header with type and version specific information */
+struct v2_disk_dqinfo {
+ __le32 dqi_bgrace; /* Time before block soft limit becomes
+ * hard limit */
+ __le32 dqi_igrace; /* Time before inode soft limit becomes
+ * hard limit */
+ __le32 dqi_flags; /* Flags for quotafile (DQF_*) */
+ __le32 dqi_blocks; /* Number of blocks in file */
+ __le32 dqi_free_blk; /* Number of first free block in the list */
+ __le32 dqi_free_entry; /* Number of block with at least one
+ * free entry */
+} __attribute__ ((packed));
+
+struct v2r1_disk_dqblk {
+ __le32 dqb_id; /* id this quota applies to */
+ __le32 dqb_pad;
+ __le64 dqb_ihardlimit; /* absolute limit on allocated inodes */
+ __le64 dqb_isoftlimit; /* preferred inode limit */
+ __le64 dqb_curinodes; /* current # allocated inodes */
+ __le64 dqb_bhardlimit; /* absolute limit on disk space
+ * (in QUOTABLOCK_SIZE) */
+ __le64 dqb_bsoftlimit; /* preferred limit on disk space
+ * (in QUOTABLOCK_SIZE) */
+ __le64 dqb_curspace; /* current space occupied (in bytes) */
+ __le64 dqb_btime; /* time limit for excessive disk use */
+ __le64 dqb_itime; /* time limit for excessive inode use */
+} __attribute__ ((packed));
+
+#endif
diff --git a/fsck/segment.c b/fsck/segment.c
index e13f147..efbd667 100644
--- a/fsck/segment.c
+++ b/fsck/segment.c
@@ -27,9 +27,10 @@ static void write_inode(u64 blkaddr, struct f2fs_node *inode)
void reserve_new_block(struct f2fs_sb_info *sbi, block_t *to,
struct f2fs_summary *sum, int type)
{
+ struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
struct seg_entry *se;
- u64 blkaddr;
- u64 offset;
+ u64 blkaddr, offset;
+ u64 old_blkaddr = *to;
blkaddr = SM_I(sbi)->main_blkaddr;
@@ -43,7 +44,16 @@ void reserve_new_block(struct f2fs_sb_info *sbi, block_t *to,
se->type = type;
se->valid_blocks++;
f2fs_set_bit(offset, (char *)se->cur_valid_map);
- sbi->total_valid_block_count++;
+ if (c.func == FSCK) {
+ f2fs_set_main_bitmap(sbi, blkaddr, type);
+ f2fs_set_sit_bitmap(sbi, blkaddr);
+ }
+
+ if (old_blkaddr == NULL_ADDR) {
+ sbi->total_valid_block_count++;
+ if (c.func == FSCK)
+ fsck->chk.valid_blk_cnt++;
+ }
se->dirty = 1;
/* read/write SSA */
@@ -56,6 +66,7 @@ void new_data_block(struct f2fs_sb_info *sbi, void *block,
{
struct f2fs_summary sum;
struct node_info ni;
+ int blkaddr = datablock_addr(dn->node_blk, dn->ofs_in_node);
ASSERT(dn->node_blk);
memset(block, 0, BLOCK_SZ);
@@ -64,7 +75,10 @@ void new_data_block(struct f2fs_sb_info *sbi, void *block,
set_summary(&sum, dn->nid, dn->ofs_in_node, ni.version);
reserve_new_block(sbi, &dn->data_blkaddr, &sum, type);
- inc_inode_blocks(dn);
+ if (blkaddr == NULL_ADDR)
+ inc_inode_blocks(dn);
+ else if (blkaddr == NEW_ADDR)
+ dn->idirty = 1;
set_data_blkaddr(dn);
}
diff --git a/include/f2fs_fs.h b/include/f2fs_fs.h
index d26b7cf..c2b2454 100644
--- a/include/f2fs_fs.h
+++ b/include/f2fs_fs.h
@@ -24,6 +24,15 @@
#include <linux/blkzoned.h>
#endif
+#ifdef UNUSED
+#elif defined(__GNUC__)
+# define UNUSED(x) UNUSED_ ## x __attribute__((unused))
+#elif defined(__LCLINT__)
+# define UNUSED(x) x
+#else
+# define UNUSED(x) x
+#endif
+
typedef u_int64_t u64;
typedef u_int32_t u32;
typedef u_int16_t u16;
@@ -1180,6 +1189,16 @@ static inline __le64 get_cp_crc(struct f2fs_checkpoint *cp)
return cpu_to_le64(cp_ver);
}
+static inline int exist_qf_ino(struct f2fs_super_block *sb)
+{
+ int i;
+
+ for (i = 0; i < F2FS_MAX_QUOTAS; i++)
+ if (sb->qf_ino[i])
+ return 1;
+ return 0;
+}
+
static inline int is_qf_ino(struct f2fs_super_block *sb, nid_t ino)
{
int i;
diff --git a/mkfs/f2fs_format.c b/mkfs/f2fs_format.c
index c809225..2103f9d 100644
--- a/mkfs/f2fs_format.c
+++ b/mkfs/f2fs_format.c
@@ -395,9 +395,13 @@ static int f2fs_prepare_super_block(void)
quotatype_bits |= QUOTA_PRJ_BIT;
}
- for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++)
- sb->qf_ino[qtype] =
- ((1 << qtype) & quotatype_bits) ? next_ino++ : 0;
+ for (qtype = 0; qtype < F2FS_MAX_QUOTAS; qtype++) {
+ if (!((1 << qtype) & quotatype_bits))
+ continue;
+ sb->qf_ino[qtype] = cpu_to_le32(next_ino++);
+ MSG(0, "Info: add quota type = %u => %u\n",
+ qtype, next_ino - 1);
+ }
if (total_zones <= 6) {
MSG(1, "\tError: %d zones: Need more zones "
--
2.14.0.rc1.383.gd1ce394fe2-goog
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
^ permalink raw reply related [flat|nested] 4+ messages in thread
end of thread, other threads:[~2017-10-31 3:42 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-10-31 3:42 [PATCH 1/4] sload.f2fs: fix bugs in f2fs_write_block() Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 2/4] f2fs-tools: f2fs_read() and f2fs_filesize_update() are added Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 3/4] mkfs.f2fs: support quota option in mkfs Jaegeuk Kim
2017-10-31 3:42 ` [PATCH 4/4] fsck.f2fs: support quota Jaegeuk Kim
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.