The AXFS header.
Signed-off-by: Jared Hulbert <[email protected]>
---
diff --git a/include/linux/axfs.h b/include/linux/axfs.h
new file mode 100644
index 0000000..87af84a
--- /dev/null
+++ b/include/linux/axfs.h
@@ -0,0 +1,360 @@
+/*
+ * Advanced XIP File System for Linux - AXFS
+ * Readonly, compressed, and XIP filesystem for Linux systems big and small
+ *
+ * Copyright(c) 2008 Numonyx
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * Authors:
+ * Eric Anderson
+ * Jared Hulbert <[email protected]>
+ * Sujaya Srinivasan
+ * Justin Treon
+ *
+ * Project url: http://axfs.sourceforge.net
+ */
+
+#ifndef __AXFS_H
+#define __AXFS_H
+
+
+#ifdef __KERNEL__
+#include <linux/rwsem.h>
+#endif
+#include <linux/errno.h>
+#include <linux/time.h>
+
+#define AXFS_MAGIC 0x48A0E4CD /* some random number */
+#define AXFS_SIGNATURE "Advanced XIP FS"
+#define AXFS_MAXPATHLEN 255
+
+/* Uncompression interfaces to the underlying zlib */
+int axfs_uncompress_block(void *, int, void *, int);
+int axfs_uncompress_init(void);
+int axfs_uncompress_exit(void);
+
+struct axfs_profiling_data {
+ u64 inode_number;
+ unsigned long count;
+};
+
+enum axfs_node_types {
+ XIP = 0,
+ Compressed,
+ Byte_Aligned,
+};
+
+enum axfs_compression_types {
+ ZLIB = 0
+};
+
+/*
+ * on media struct describing a data region
+ */
+struct axfs_region_desc_onmedia {
+ u64 fsoffset;
+ u64 size;
+ u64 compressed_size;
+ u64 max_index;
+ u8 table_byte_depth;
+ u8 incore;
+};
+
+struct axfs_region_desc {
+ u64 fsoffset;
+ u64 size;
+ u64 compressed_size;
+ u64 max_index;
+ void *virt_addr;
+ u8 table_byte_depth;
+ u8 incore;
+};
+
+/*
+ * axfs_super is the on media format for the super block it must be big endian
+ */
+struct axfs_super_onmedia {
+ u32 magic; /* 0x48A0E4CD - random number */
+ u8 signature[16]; /* "Advanced XIP FS" */
+ u8 digest[40]; /* sha1 digest for checking data integrity */
+ u32 cblock_size; /* maximum size of the block being compressed */
+ u64 files; /* number of inodes/files in fs */
+ u64 size; /* total image size */
+ u64 blocks; /* number of nodes in fs */
+ u64 mmap_size; /* size of the memory mapped part of image */
+ u64 strings; /* offset to strings region descriptor */
+ u64 xip; /* offset to xip region descriptor */
+ u64 byte_aligned; /* offset to the byte aligned region desc */
+ u64 compressed; /* offset to the compressed region desc */
+ u64 node_type; /* offset to node type region desc */
+ u64 node_index; /* offset to node index region desc */
+ u64 cnode_offset; /* offset to cnode offset region desc */
+ u64 cnode_index; /* offset to cnode index region desc */
+ u64 banode_offset; /* offset to banode offset region desc */
+ u64 cblock_offset; /* offset to cblock offset region desc */
+ u64 inode_file_size; /* offset to inode file size desc*/
+ u64 inode_name_offset; /* offset to inode num_entries region desc */
+ u64 inode_num_entries; /* offset to inode num_entries region desc */
+ u64 inode_mode_index; /* offset to inode mode index region desc */
+ u64 inode_array_index; /* offset to inode node index region desc */
+ u64 modes; /* offset to mode mode region desc */
+ u64 uids; /* offset to mode uid index region desc */
+ u64 gids; /* offset to mode gid index region desc */
+ u8 version_major;
+ u8 version_minor;
+ u8 version_sub;
+ u8 compression_type; /* Identifies type of compression used on FS */
+ u64 timestamp; /* UNIX time_t of filesystem build time */
+};
+
+/*
+ * axfs super-block data in core
+ */
+struct axfs_super {
+ u32 magic;
+ u8 version_major;
+ u8 version_minor;
+ u8 version_sub;
+ u8 padding;
+ u64 files;
+ u64 size;
+ u64 blocks;
+ u64 mmap_size;
+ struct axfs_region_desc strings;
+ struct axfs_region_desc xip;
+ struct axfs_region_desc compressed;
+ struct axfs_region_desc byte_aligned;
+ struct axfs_region_desc node_type;
+ struct axfs_region_desc node_index;
+ struct axfs_region_desc cnode_offset;
+ struct axfs_region_desc cnode_index;
+ struct axfs_region_desc banode_offset;
+ struct axfs_region_desc cblock_offset;
+ struct axfs_region_desc inode_file_size;
+ struct axfs_region_desc inode_name_offset;
+ struct axfs_region_desc inode_num_entries;
+ struct axfs_region_desc inode_mode_index;
+ struct axfs_region_desc inode_array_index;
+ struct axfs_region_desc modes;
+ struct axfs_region_desc uids;
+ struct axfs_region_desc gids;
+ unsigned long phys_start_addr;
+ unsigned long virt_start_addr;
+ char *second_dev;
+ unsigned long iomem_size;
+ void *mtd0; /* primary device */
+ void *mtd1; /* secondary device */
+ u32 cblock_size;
+ u64 current_cnode_index;
+ void *cblock_buffer[2];
+ struct rw_semaphore lock;
+ struct axfs_profiling_data *profile_data_ptr;
+ u8 profiling_on; /* Determines if profiling is on or off */
+ u8 mtd_pointed;
+ u8 compression_type;
+ struct timespec timestamp;
+};
+
+#define AXFS_PAGE_SIZE 4096
+
+#define AXFS_SB(sb) (struct axfs_super *)((sb)->s_fs_info)
+#define AXFS_MTD(sb) (void *)((sb)->s_mtd)
+#define AXFS_MTD0(sb) (((AXFS_SB(sb))->mtd0) ? \
+ ((AXFS_SB(sb))->mtd0) : (AXFS_MTD(sb)))
+#define AXFS_MTD1(sb) ((AXFS_SB(sb))->mtd1)
+
+#define AXFS_BDEV(sb) ((sb)->s_bdev)
+
+#define AXFS_HAS_BDEV(sb) \
+ ((AXFS_BDEV(sb) != NULL) ? TRUE : FALSE)
+#define AXFS_HAS_MTD(sb) \
+ (((AXFS_MTD0(sb) != NULL) || \
+ (AXFS_MTD1(sb) != NULL) || \
+ (AXFS_MTD(sb) != NULL)) ? TRUE : FALSE)
+
+#define AXFS_NODEV(sb) \
+ ((!AXFS_HAS_MTD(sb) && !AXFS_HAS_BDEV(sb)) ? TRUE : FALSE)
+
+static inline u64 axfs_bytetable_stitch(u8 depth, u8 *table, u64 index)
+{
+ u64 i;
+ u64 output = 0;
+ u64 byte = 0;
+ u64 j;
+ u64 bits;
+
+ for (i = 0; i < depth; i++) {
+ j = index * depth + i;
+ bits = 8 * (depth - i - 1);
+ byte = table[j];
+ output += byte << bits;
+ }
+ return output;
+}
+
+#define AXFS_GET_BYTETABLE_VAL(desc,index) \
+ axfs_bytetable_stitch(((struct axfs_region_desc)(desc)).table_byte_depth,\
+ (u8 *)((struct axfs_region_desc)(desc)).virt_addr, index)
+
+#define AXFS_GET_NODE_TYPE(sbi,node_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->node_type,\
+ (node_index))
+
+#define AXFS_GET_NODE_INDEX(sbi,node__index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->node_index,\
+ (node__index))
+
+#define AXFS_IS_NODE_XIP(sbi,node_index) \
+ (AXFS_GET_NODE_TYPE(sbi, (node_index)) == XIP)
+
+#define AXFS_GET_CNODE_INDEX(sbi,node_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->cnode_index,\
+ (node_index))
+
+#define AXFS_GET_CNODE_OFFSET(desc,node_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->cnode_offset,\
+ (node_index))
+
+#define AXFS_GET_BANODE_OFFSET(desc,node_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->banode_offset,\
+ (node_index))
+
+#define AXFS_GET_CBLOCK_OFFSET(desc,node_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->cblock_offset,\
+ (node_index))
+
+#define AXFS_GET_INODE_FILE_SIZE(sbi,inode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_file_size,\
+ (inode_index))
+
+#define AXFS_GET_INODE_NAME_OFFSET(sbi,inode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_name_offset,\
+ (inode_index))
+
+#define AXFS_GET_INODE_NUM_ENTRIES(sbi,inode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_num_entries,\
+ (inode_index))
+
+#define AXFS_GET_INODE_MODE_INDEX(sbi,inode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_mode_index,\
+ (inode_index))
+
+#define AXFS_GET_INODE_ARRAY_INDEX(sbi,inode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_array_index,\
+ (inode_index))
+
+#define AXFS_GET_MODE(sbi,mode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->modes,\
+ (AXFS_GET_INODE_MODE_INDEX(sbi, (mode_index))))
+
+#define AXFS_GET_UID(sbi,mode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->uids,\
+ (AXFS_GET_INODE_MODE_INDEX(sbi, (mode_index))))
+
+#define AXFS_GET_GID(sbi,mode_index) \
+ AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->gids,\
+ (AXFS_GET_INODE_MODE_INDEX(sbi, (mode_index))))
+
+#define AXFS_IS_REGION_COMPRESSED(_region) \
+ (( \
+ ((struct axfs_region_desc *)(_region))->compressed_size > \
+ 0 \
+ ) ? TRUE : FALSE)
+
+#define AXFS_PHYSADDR_IS_VALID(sbi) \
+ (((((struct axfs_super *)(sbi))->phys_start_addr) > 0 \
+ ) ? TRUE : FALSE)
+
+#define AXFS_VIRTADDR_IS_VALID(sbi) \
+ (((((struct axfs_super *)(sbi))->virt_start_addr) > 0 \
+ ) ? TRUE : FALSE)
+
+#define AXFS_IS_IOMEM(sbi) \
+ (((((struct axfs_super *)(sbi))->iomem_size) > 0) ? TRUE : FALSE)
+
+#define AXFS_IS_POINTED(sbi) \
+ (((((struct axfs_super *)(sbi))->mtd_pointed) > 0) ? TRUE : FALSE)
+
+#define AXFS_IS_PHYSMEM(sbi) \
+ (( \
+ AXFS_PHYSADDR_IS_VALID(sbi) \
+ && !AXFS_IS_IOMEM(sbi) \
+ && !AXFS_IS_POINTED(sbi) \
+ ) ? TRUE : FALSE)
+
+#define AXFS_IS_MMAPABLE(sbi,offset) \
+ ((\
+ (((struct axfs_super *)(sbi))->mmap_size) > (offset) \
+ ) ? TRUE : FALSE)
+
+#define AXFS_IS_OFFSET_MMAPABLE(sbi,offset) \
+ (( \
+ AXFS_IS_MMAPABLE(sbi, offset) && AXFS_VIRTADDR_IS_VALID(sbi) \
+ ) ? TRUE : FALSE)
+
+#define AXFS_IS_REGION_MMAPABLE(sbi,_region) \
+ (( \
+ AXFS_IS_MMAPABLE(sbi, ((struct axfs_region_desc *)(_region))->fsoffset) \
+ && AXFS_VIRTADDR_IS_VALID(sbi) \
+ ) ? TRUE : FALSE)
+
+#define AXFS_IS_REGION_INCORE(_region) \
+ (((_region)->incore > 0) ? TRUE : FALSE)
+
+#define AXFS_IS_REGION_XIP(sbi,_region) \
+ (( \
+ !AXFS_IS_REGION_COMPRESSED(_region) && \
+ !AXFS_IS_REGION_INCORE(_region) && \
+ AXFS_IS_REGION_MMAPABLE(sbi,_region) \
+ ) ? TRUE : FALSE)
+
+#define AXFS_GET_XIP_REGION_PHYSADDR(sbi) \
+ (unsigned long)((sbi)->phys_start_addr + (sbi)->xip.fsoffset)
+
+#define AXFS_GET_INODE_NAME(sbi,inode_index) \
+ (char *)( \
+ (sbi)->strings.virt_addr \
+ + AXFS_GET_INODE_NAME_OFFSET(sbi,inode_index) \
+ )
+
+#define AXFS_GET_CBLOCK_ADDRESS(sbi, cnode_index)\
+ (unsigned long)( \
+ (sbi)->compressed.virt_addr \
+ + AXFS_GET_CBLOCK_OFFSET(sbi, cnode_index) \
+ )
+
+#define AXFS_GET_NODE_ADDRESS(sbi,node__index) \
+ (unsigned long)( \
+ (sbi)->node_index.virt_addr \
+ + AXFS_GET_NODE_INDEX(sbi, node__index) \
+ )
+
+#define AXFS_GET_BANODE_ADDRESS(sbi,banode_index) \
+ (unsigned long)( \
+ (sbi)->byte_aligned.virt_addr \
+ + AXFS_GET_BANODE_OFFSET(sbi, banode_index) \
+ )
+
+#define AXFS_FSOFFSET_2_DEVOFFSET(sbi,fsoffset) \
+ (( \
+ ((sbi)->phys_start_addr == 0) && ((sbi)->virt_start_addr == 0) \
+ ) ? (fsoffset) : (fsoffset - (sbi)->mmap_size) \
+ )
+
+#define AXFS_GET_CBLOCK_LENGTH(sbi,cblock_index) \
+ (u64)( \
+ (u64)AXFS_GET_CBLOCK_OFFSET(sbi, ((u64)(cblock_index)+(u64)1)) \
+ - (u64)AXFS_GET_CBLOCK_OFFSET(sbi, (cblock_index)) \
+ )
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+#endif
Jared Hulbert wrote:
> +#define AXFS_GET_BYTETABLE_VAL(desc,index) \
> + axfs_bytetable_stitch(((struct axfs_region_desc)(desc)).table_byte_depth,\
> + (u8 *)((struct axfs_region_desc)(desc)).virt_addr, index)
> +
> +#define AXFS_GET_NODE_TYPE(sbi,node_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->node_type,\
> + (node_index))
> +
> +#define AXFS_GET_NODE_INDEX(sbi,node__index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->node_index,\
> + (node__index))
> +
> +#define AXFS_IS_NODE_XIP(sbi,node_index) \
> + (AXFS_GET_NODE_TYPE(sbi, (node_index)) == XIP)
> +
> +#define AXFS_GET_CNODE_INDEX(sbi,node_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->cnode_index,\
> + (node_index))
> +
> +#define AXFS_GET_CNODE_OFFSET(desc,node_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->cnode_offset,\
> + (node_index))
> +
> +#define AXFS_GET_BANODE_OFFSET(desc,node_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->banode_offset,\
> + (node_index))
> +
> +#define AXFS_GET_CBLOCK_OFFSET(desc,node_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->cblock_offset,\
> + (node_index))
> +
> +#define AXFS_GET_INODE_FILE_SIZE(sbi,inode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_file_size,\
> + (inode_index))
> +
> +#define AXFS_GET_INODE_NAME_OFFSET(sbi,inode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_name_offset,\
> + (inode_index))
> +
> +#define AXFS_GET_INODE_NUM_ENTRIES(sbi,inode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_num_entries,\
> + (inode_index))
> +
> +#define AXFS_GET_INODE_MODE_INDEX(sbi,inode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_mode_index,\
> + (inode_index))
> +
> +#define AXFS_GET_INODE_ARRAY_INDEX(sbi,inode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->inode_array_index,\
> + (inode_index))
> +
> +#define AXFS_GET_MODE(sbi,mode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->modes,\
> + (AXFS_GET_INODE_MODE_INDEX(sbi, (mode_index))))
> +
> +#define AXFS_GET_UID(sbi,mode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->uids,\
> + (AXFS_GET_INODE_MODE_INDEX(sbi, (mode_index))))
> +
> +#define AXFS_GET_GID(sbi,mode_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->gids,\
> + (AXFS_GET_INODE_MODE_INDEX(sbi, (mode_index))))
> +
> +#define AXFS_IS_REGION_COMPRESSED(_region) \
> + (( \
> + ((struct axfs_region_desc *)(_region))->compressed_size > \
> + 0 \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_PHYSADDR_IS_VALID(sbi) \
> + (((((struct axfs_super *)(sbi))->phys_start_addr) > 0 \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_VIRTADDR_IS_VALID(sbi) \
> + (((((struct axfs_super *)(sbi))->virt_start_addr) > 0 \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_IS_IOMEM(sbi) \
> + (((((struct axfs_super *)(sbi))->iomem_size) > 0) ? TRUE : FALSE)
> +
> +#define AXFS_IS_POINTED(sbi) \
> + (((((struct axfs_super *)(sbi))->mtd_pointed) > 0) ? TRUE : FALSE)
> +
> +#define AXFS_IS_PHYSMEM(sbi) \
> + (( \
> + AXFS_PHYSADDR_IS_VALID(sbi) \
> + && !AXFS_IS_IOMEM(sbi) \
> + && !AXFS_IS_POINTED(sbi) \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_IS_MMAPABLE(sbi,offset) \
> + ((\
> + (((struct axfs_super *)(sbi))->mmap_size) > (offset) \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_IS_OFFSET_MMAPABLE(sbi,offset) \
> + (( \
> + AXFS_IS_MMAPABLE(sbi, offset) && AXFS_VIRTADDR_IS_VALID(sbi) \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_IS_REGION_MMAPABLE(sbi,_region) \
> + (( \
> + AXFS_IS_MMAPABLE(sbi, ((struct axfs_region_desc *)(_region))->fsoffset) \
> + && AXFS_VIRTADDR_IS_VALID(sbi) \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_IS_REGION_INCORE(_region) \
> + (((_region)->incore > 0) ? TRUE : FALSE)
> +
> +#define AXFS_IS_REGION_XIP(sbi,_region) \
> + (( \
> + !AXFS_IS_REGION_COMPRESSED(_region) && \
> + !AXFS_IS_REGION_INCORE(_region) && \
> + AXFS_IS_REGION_MMAPABLE(sbi,_region) \
> + ) ? TRUE : FALSE)
> +
> +#define AXFS_GET_XIP_REGION_PHYSADDR(sbi) \
> + (unsigned long)((sbi)->phys_start_addr + (sbi)->xip.fsoffset)
> +
> +#define AXFS_GET_INODE_NAME(sbi,inode_index) \
> + (char *)( \
> + (sbi)->strings.virt_addr \
> + + AXFS_GET_INODE_NAME_OFFSET(sbi,inode_index) \
> + )
> +
> +#define AXFS_GET_CBLOCK_ADDRESS(sbi, cnode_index)\
> + (unsigned long)( \
> + (sbi)->compressed.virt_addr \
> + + AXFS_GET_CBLOCK_OFFSET(sbi, cnode_index) \
> + )
> +
> +#define AXFS_GET_NODE_ADDRESS(sbi,node__index) \
> + (unsigned long)( \
> + (sbi)->node_index.virt_addr \
> + + AXFS_GET_NODE_INDEX(sbi, node__index) \
> + )
> +
> +#define AXFS_GET_BANODE_ADDRESS(sbi,banode_index) \
> + (unsigned long)( \
> + (sbi)->byte_aligned.virt_addr \
> + + AXFS_GET_BANODE_OFFSET(sbi, banode_index) \
> + )
> +
> +#define AXFS_FSOFFSET_2_DEVOFFSET(sbi,fsoffset) \
> + (( \
> + ((sbi)->phys_start_addr == 0) && ((sbi)->virt_start_addr == 0) \
> + ) ? (fsoffset) : (fsoffset - (sbi)->mmap_size) \
> + )
> +
> +#define AXFS_GET_CBLOCK_LENGTH(sbi,cblock_index) \
> + (u64)( \
> + (u64)AXFS_GET_CBLOCK_OFFSET(sbi, ((u64)(cblock_index)+(u64)1)) \
> + - (u64)AXFS_GET_CBLOCK_OFFSET(sbi, (cblock_index)) \
> + )
> +
> +#ifndef TRUE
> +#define TRUE 1
> +#endif
> +#ifndef FALSE
> +#define FALSE 0
> +#endif
*Shrug*. That part reads scary. Are all those casts and macros really
needed? Maybe it is worth considering to clean this up a little.
On Thursday 21 August 2008, Jared Hulbert wrote:
>
> +#ifndef __AXFS_H
> +#define __AXFS_H
> +
> +
> +#ifdef __KERNEL__
> +#include <linux/rwsem.h>
> +#endif
> +#include <linux/errno.h>
> +#include <linux/time.h>
> +
> +#define AXFS_MAGIC 0x48A0E4CD /* some random number */
> +#define AXFS_SIGNATURE "Advanced XIP FS"
> +#define AXFS_MAXPATHLEN 255
> +
> +/* Uncompression interfaces to the underlying zlib */
> +int axfs_uncompress_block(void *, int, void *, int);
> +int axfs_uncompress_init(void);
> +int axfs_uncompress_exit(void);
You already have both __KERNEL__ and user space parts in your header.
Function declarations clearly don't belong in the user visible parts.
I suggest you only leave on-disk data structure definitions and user
interfaces in the user-visible include/linux/axfs.h file, and move
all internal interfaces to fs/axfs/axfs.h.
> +/*
> + * on media struct describing a data region
> + */
> +struct axfs_region_desc_onmedia {
> + u64 fsoffset;
> + u64 size;
> + u64 compressed_size;
> + u64 max_index;
> + u8 table_byte_depth;
> + u8 incore;
> +};
For on-disk data structures, I would use __be64 or __le64 types,
preferrably the opposite of your native CPU byte order on the system
you are developing most code on, to make sure that you get endianess
right.
> +#define AXFS_PAGE_SIZE 4096
What happens on systems where AXFS_PAGE_SIZE != PAGE_SIZE?
> +#ifndef TRUE
> +#define TRUE 1
> +#endif
> +#ifndef FALSE
> +#define FALSE 0
> +#endif
> +
These are already defined in <linux/kernel.h>, so please use the
existing definitions.
Arnd <><
On Thursday 21 August 2008, Jared Hulbert wrote:
> +static inline u64 axfs_bytetable_stitch(u8 depth, u8 *table, u64 index)
> +{
> +???????u64 i;
> +???????u64 output = 0;
> +???????u64 byte = 0;
> +???????u64 j;
> +???????u64 bits;
> +
> +???????for (i = 0; i < depth; i++) {
> +???????????????j = index * depth + i;
> +???????????????bits = 8 * (depth - i - 1);
> +???????????????byte = table[j];
> +???????????????output += byte << bits;
> +???????}
> +???????return output;
> +}
> +
> +#define AXFS_GET_BYTETABLE_VAL(desc,index) \
> + ?axfs_bytetable_stitch(((struct axfs_region_desc)(desc)).table_byte_depth,\
> + ?(u8 *)((struct axfs_region_desc)(desc)).virt_addr, index)
> +
This bytetable stuff looks overly complicated, both the data structure and
the access method. It seems like you are implementing your own custom Huffman
compression with this.
Is the reasonn for the bytetable just to pack numbers efficiently, or do you
have a different intention?
Did you see a significant size benefit over simply storing all metadata as
uncompressed data structures like in cramfs?
Have you considered storing simple dentry/inode data in node_type==Compressed
nodes?
Arnd <><
On Wed, 2008-08-20 at 22:45 -0700, Jared Hulbert wrote:
> +#define AXFS_GET_BYTETABLE_VAL(desc,index) \
> + axfs_bytetable_stitch(((struct
> axfs_region_desc)(desc)).table_byte_depth,\
> + (u8 *)((struct axfs_region_desc)(desc)).virt_addr, index)
> +
> +#define AXFS_GET_NODE_TYPE(sbi,node_index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->node_type,\
> + (node_index))
> +
> +#define AXFS_GET_NODE_INDEX(sbi,node__index) \
> + AXFS_GET_BYTETABLE_VAL(((struct axfs_super *)(sbi))->node_index,\
> + (node__index))
> +
I think it would be much cleaner to do all these similar macro's as
static inline functions.
Daniel
>> +#define AXFS_PAGE_SIZE 4096
>
> What happens on systems where AXFS_PAGE_SIZE != PAGE_SIZE?
Right now, bad things I imagine. I meant to revisit this, there was
some reason during development for this, I don't remember. No reason
for AXFS_PAGE_SIZE I think.
> I think it would be much cleaner to do all these similar macro's as
> static inline functions.
Yeah. Been thinking about that.
> This bytetable stuff looks overly complicated, both the data structure and
> the access method. It seems like you are implementing your own custom Huffman
> compression with this.
>
> Is the reasonn for the bytetable just to pack numbers efficiently, or do you
> have a different intention?
It looks more complicated than it is. I need a data structure that is
64bit capable, easily read-in-place (remember this is designed to be
an XIP fs), and highly space efficient. Because it's XIP I didn't
want something that required a lot of calculation nor something that
made you incur a lot of cache misses. So yes I just want to pack
numbers in an easily read-in-place fashion.
If I have an array of u64 numbers tracking small numbers (a[0] = 1;
a[1] = 2;) just throwing that onmedia is a big waste.
(0x0000000000000001; 0x0000000000000002) Having different array types
for different images such as arrays of u8,u16,u32,u64 becomes less
efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
interesting size for me.
All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
Take an array of u64 like this :
0x0000000000000005
0x0000000000001001
0x00000000000a0000
I strip off the unneeded leading zeros:
0x000005
0x001001
0x0a0000
Then pack them to byte alignment:
0x0000050010010a0000
Sure it could be encoded more but that would make it harder to extract
the data. This way I can read the data in one, maybe two, cache
misses. A couple of shifts to deal with the alignment and endianness
and we are done.
> Did you see a significant size benefit over simply storing all metadata as
> uncompressed data structures like in cramfs?
Yes. For some modest values of significant. In terms of the amount of
space required to track the metadata it is more dramatic. For a small
rootfs I can fit many of the data structures in an u8 array, while
maintaining u64 compatibility. Compared to dumping u64 arrays onmedia
that's an 8X savings. But it's an 8X savings of a smallish percentage
of the image size. The difference is more pronounced on a smaller
(2MB) filesystem I tested but it was only ~5% if memory serves me
correct.
> Have you considered storing simple dentry/inode data in node_type==Compressed
> nodes?
Yes, I thought a lot about that. But I choose against it because I
wanted read-in-place data structures for minimum RAM usage in the XIP
case and I figure the way I do it would stat() faster.
On Friday 22 August 2008, Jared Hulbert wrote:
> > This bytetable stuff looks overly complicated, both the data structure and
> > the access method. It seems like you are implementing your own custom Huffman
> > compression with this.
> >
> > Is the reasonn for the bytetable just to pack numbers efficiently, or do you
> > have a different intention?
>
> It looks more complicated than it is. I need a data structure that is
> 64bit capable, easily read-in-place (remember this is designed to be
> an XIP fs), and highly space efficient. Because it's XIP I didn't
> want something that required a lot of calculation nor something that
> made you incur a lot of cache misses. So yes I just want to pack
> numbers in an easily read-in-place fashion.
ok, that makes sense.
> If I have an array of u64 numbers tracking small numbers (a[0] = 1;
> a[1] = 2;) just throwing that onmedia is a big waste.
> (0x0000000000000001; 0x0000000000000002) Having different array types
> for different images such as arrays of u8,u16,u32,u64 becomes less
> efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
> interesting size for me.
>
> All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
> Take an array of u64 like this :
> 0x0000000000000005
> 0x0000000000001001
> 0x00000000000a0000
>
> I strip off the unneeded leading zeros:
> 0x000005
> 0x001001
> 0x0a0000
>
> Then pack them to byte alignment:
> 0x0000050010010a0000
>
> Sure it could be encoded more but that would make it harder to extract
> the data. This way I can read the data in one, maybe two, cache
> misses. A couple of shifts to deal with the alignment and endianness
> and we are done.
So do I understand right that 3 bytes is your minimum size, and going
smaller than that would not be helpful? Otherwise I would assume that
storing a '5' should only take one byte instead of three.
I don't unsterstand yet why you store the length of each word separate
from the word. Most variable-length codes store that implicitly in
the data itself, e.g. in the upper three bits, so that for storing
0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
which is shorter than what you have, but not harder to decode.
> > Did you see a significant size benefit over simply storing all metadata as
> > uncompressed data structures like in cramfs?
>
> Yes. For some modest values of significant. In terms of the amount of
> space required to track the metadata it is more dramatic. For a small
> rootfs I can fit many of the data structures in an u8 array, while
> maintaining u64 compatibility. Compared to dumping u64 arrays onmedia
> that's an 8X savings. But it's an 8X savings of a smallish percentage
> of the image size. The difference is more pronounced on a smaller
> (2MB) filesystem I tested but it was only ~5% if memory serves me
> correct.
If you can save 5% on a real-world file system, you have convinced me.
> > Have you considered storing simple dentry/inode data in node_type==Compressed
> > nodes?
>
> Yes, I thought a lot about that. But I choose against it because I
> wanted read-in-place data structures for minimum RAM usage in the XIP
> case and I figure the way I do it would stat() faster.
ok.
Arnd <><
On Fri, 22 Aug 2008, Arnd Bergmann wrote:
> On Friday 22 August 2008, Jared Hulbert wrote:
> > If I have an array of u64 numbers tracking small numbers (a[0] = 1;
> > a[1] = 2;) just throwing that onmedia is a big waste.
> > (0x0000000000000001; 0x0000000000000002) Having different array types
> > for different images such as arrays of u8,u16,u32,u64 becomes less
> > efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
> > interesting size for me.
> >
> > All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
> > Take an array of u64 like this :
> > 0x0000000000000005
> > 0x0000000000001001
> > 0x00000000000a0000
> >
> > I strip off the unneeded leading zeros:
> > 0x000005
> > 0x001001
> > 0x0a0000
> >
> > Then pack them to byte alignment:
> > 0x0000050010010a0000
> >
> > Sure it could be encoded more but that would make it harder to extract
> > the data. This way I can read the data in one, maybe two, cache
> > misses. A couple of shifts to deal with the alignment and endianness
> > and we are done.
>
> So do I understand right that 3 bytes is your minimum size, and going
> smaller than that would not be helpful? Otherwise I would assume that
> storing a '5' should only take one byte instead of three.
>From the paper, the minimum size (called `depth') is 1.
> I don't unsterstand yet why you store the length of each word separate
> from the word. Most variable-length codes store that implicitly in
> the data itself, e.g. in the upper three bits, so that for storing
> 0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
> which is shorter than what you have, but not harder to decode.
AFAIU, the length (`depth') of each word is not stored separate, as the
depth is the same for all values in the same table.
With kind regards,
Geert Uytterhoeven
Software Architect
Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium
Phone: +32 (0)2 700 8453
Fax: +32 (0)2 700 8622
E-mail: [email protected]
Internet: http://www.sony-europe.com/
A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010
>> So do I understand right that 3 bytes is your minimum size, and going
>> smaller than that would not be helpful? Otherwise I would assume that
>> storing a '5' should only take one byte instead of three.
Right. But you need 3 bytes to store the maximum value 0x0a0000
If we had:
0x0000000000000003
0x00000000000000FF
0x000000000000000A
You would only need a 1 byte depth.
> From the paper, the minimum size (called `depth') is 1.
Correct the depth can be from 1 to 8 bytes. The depth is determined
by the maximum value in the array.
>> I don't unsterstand yet why you store the length of each word separate
>> from the word. Most variable-length codes store that implicitly in
>> the data itself, e.g. in the upper three bits, so that for storing
>> 0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
>> which is shorter than what you have, but not harder to decode.
>
> AFAIU, the length (`depth') of each word is not stored separate, as the
> depth is the same for all values in the same table.
That is correct. Each table has a single depth stored in the region descriptor.