Patch, f2fs headers ready to build with busybox
--- /dev/null +++ b/f2fs/f2fs.h @@ -0,0 +1,374 @@ +/** + * f2fs.h + * + * Copyright (c) 2013 Samsung Electronics Co., Ltd. + * http://www.samsung.com/ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ +#ifndef _F2FS_H_ +#define _F2FS_H_ + +#include <stdlib.h> +#include <unistd.h> +#include <stdio.h> +#include <errno.h> +#include <fcntl.h> +#include <string.h> +#include <errno.h> +#include <mntent.h> +#include <linux/types.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <sys/ioctl.h> +#include <sys/mount.h> +#include <assert.h> + +#include "f2fs_fs.h" + +#define EXIT_ERR_CODE (-1) +#define ver_after(a, b) (typecheck(unsigned long long, a) && \ + typecheck(unsigned long long, b) && \ + ((long long)((a) - (b)) > 0)) + +struct list_head { + struct list_head *next, *prev; +}; + +enum { + NAT_BITMAP, + SIT_BITMAP +}; + +struct node_info { + nid_t nid; + nid_t ino; + u32 blk_addr; + unsigned char version; +}; + +struct f2fs_nm_info { + block_t nat_blkaddr; + nid_t max_nid; + nid_t init_scan_nid; + nid_t next_scan_nid; + + unsigned int nat_cnt; + unsigned int fcnt; + + char *nat_bitmap; + int bitmap_size; +}; + +struct seg_entry { + unsigned short valid_blocks; /* # of valid blocks */ + unsigned char *cur_valid_map; /* validity bitmap of blocks */ + /* + * # of valid blocks and the validity bitmap stored in the the last + * checkpoint pack. This information is used by the SSR mode. + */ + unsigned short ckpt_valid_blocks; + unsigned char *ckpt_valid_map; + unsigned char type; /* segment type like CURSEG_XXX_TYPE */ + unsigned long long mtime; /* modification time of the segment */ +}; + +struct sec_entry { + unsigned int valid_blocks; /* # of valid blocks in a section */ +}; + +struct sit_info { + + block_t sit_base_addr; /* start block address of SIT area */ + block_t sit_blocks; /* # of blocks used by SIT area */ + block_t written_valid_blocks; /* # of valid blocks in main area */ + char *sit_bitmap; /* SIT bitmap pointer */ + unsigned int bitmap_size; /* SIT bitmap size */ + + unsigned long *dirty_sentries_bitmap; /* bitmap for dirty sentries */ + unsigned int dirty_sentries; /* # of dirty sentries */ + unsigned int sents_per_block; /* # of SIT entries per block */ + struct seg_entry *sentries; /* SIT segment-level cache */ + struct sec_entry *sec_entries; /* SIT section-level cache */ + + unsigned long long elapsed_time; /* elapsed time after mount */ + unsigned long long mounted_time; /* mount time */ + unsigned long long min_mtime; /* min. modification time */ + unsigned long long max_mtime; /* max. modification time */ +}; + +struct curseg_info { + struct f2fs_summary_block *sum_blk; /* cached summary block */ + unsigned char alloc_type; /* current allocation type */ + unsigned int segno; /* current segment number */ + unsigned short next_blkoff; /* next block offset to write */ + unsigned int zone; /* current zone number */ + unsigned int next_segno; /* preallocated segment */ +}; + +struct f2fs_sm_info { + struct sit_info *sit_info; + struct curseg_info *curseg_array; + + block_t seg0_blkaddr; + block_t main_blkaddr; + block_t ssa_blkaddr; + + unsigned int segment_count; + unsigned int main_segments; + unsigned int reserved_segments; + unsigned int ovp_segments; +}; + +struct f2fs_sb_info { + struct f2fs_fsck *fsck; + + struct f2fs_super_block *raw_super; + struct f2fs_nm_info *nm_info; + struct f2fs_sm_info *sm_info; + struct f2fs_checkpoint *ckpt; + int cur_cp; + + struct list_head orphan_inode_list; + unsigned int n_orphans; + + /* basic file system units */ + unsigned int log_sectors_per_block; /* log2 sectors per block */ + unsigned int log_blocksize; /* log2 block size */ + unsigned int blocksize; /* block size */ + unsigned int root_ino_num; /* root inode number*/ + unsigned int node_ino_num; /* node inode number*/ + unsigned int meta_ino_num; /* meta inode number*/ + unsigned int log_blocks_per_seg; /* log2 blocks per segment */ + unsigned int blocks_per_seg; /* blocks per segment */ + unsigned int segs_per_sec; /* segments per section */ + unsigned int secs_per_zone; /* sections per zone */ + unsigned int total_sections; /* total section count */ + unsigned int total_node_count; /* total node block count */ + unsigned int total_valid_node_count; /* valid node block count */ + unsigned int total_valid_inode_count; /* valid inode count */ + int active_logs; /* # of active logs */ + + block_t user_block_count; /* # of user blocks */ + block_t total_valid_block_count; /* # of valid blocks */ + block_t alloc_valid_block_count; /* # of allocated blocks */ + block_t last_valid_block_count; /* for recovery */ + u32 s_next_generation; /* for NFS support */ + + unsigned int cur_victim_sec; /* current victim section num */ + +}; + +static inline struct f2fs_super_block *F2FS_RAW_SUPER(struct f2fs_sb_info *sbi) +{ + return (struct f2fs_super_block *)(sbi->raw_super); +} + +static inline struct f2fs_checkpoint *F2FS_CKPT(struct f2fs_sb_info *sbi) +{ + return (struct f2fs_checkpoint *)(sbi->ckpt); +} + +static inline struct f2fs_fsck *F2FS_FSCK(struct f2fs_sb_info *sbi) +{ + return (struct f2fs_fsck *)(sbi->fsck); +} + +static inline struct f2fs_nm_info *NM_I(struct f2fs_sb_info *sbi) +{ + return (struct f2fs_nm_info *)(sbi->nm_info); +} + +static inline struct f2fs_sm_info *SM_I(struct f2fs_sb_info *sbi) +{ + return (struct f2fs_sm_info *)(sbi->sm_info); +} + +static inline struct sit_info *SIT_I(struct f2fs_sb_info *sbi) +{ + return (struct sit_info *)(SM_I(sbi)->sit_info); +} + +static inline void *inline_data_addr(struct f2fs_node *node_blk) +{ + return (void *)&(node_blk->i.i_addr[1]); +} + +static inline unsigned long __bitmap_size(struct f2fs_sb_info *sbi, int flag) +{ + struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi); + + /* return NAT or SIT bitmap */ + if (flag == NAT_BITMAP) + return le32_to_cpu(ckpt->nat_ver_bitmap_bytesize); + else if (flag == SIT_BITMAP) + return le32_to_cpu(ckpt->sit_ver_bitmap_bytesize); + + return 0; +} + +static inline void *__bitmap_ptr(struct f2fs_sb_info *sbi, int flag) +{ + struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi); + int offset; + if (le32_to_cpu(F2FS_RAW_SUPER(sbi)->cp_payload) > 0) { + if (flag == NAT_BITMAP) + return &ckpt->sit_nat_version_bitmap; + else + return ((char *)ckpt + F2FS_BLKSIZE); + } else { + offset = (flag == NAT_BITMAP) ? + le32_to_cpu(ckpt->sit_ver_bitmap_bytesize) : 0; + return &ckpt->sit_nat_version_bitmap + offset; + } +} + +static inline u8 is_set_ckpt_flags(struct f2fs_checkpoint *cp, unsigned int f) +{ + unsigned int ckpt_flags = le32_to_cpu(cp->ckpt_flags); + return ckpt_flags & f; +} + +static inline block_t __start_cp_addr(struct f2fs_sb_info *sbi) +{ + block_t start_addr; + struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi); + unsigned long long ckpt_version = le64_to_cpu(ckpt->checkpoint_ver); + + start_addr = le32_to_cpu(F2FS_RAW_SUPER(sbi)->cp_blkaddr); + + /* + * odd numbered checkpoint should at cp segment 0 + * and even segent must be at cp segment 1 + */ + if (!(ckpt_version & 1)) + start_addr += sbi->blocks_per_seg; + + return start_addr; +} + +static inline block_t __start_sum_addr(struct f2fs_sb_info *sbi) +{ + return le32_to_cpu(F2FS_CKPT(sbi)->cp_pack_start_sum); +} + +#define GET_ZONENO_FROM_SEGNO(sbi, segno) \ + ((segno / sbi->segs_per_sec) / sbi->secs_per_zone) + +#define IS_DATASEG(t) \ + ((t == CURSEG_HOT_DATA) || (t == CURSEG_COLD_DATA) || \ + (t == CURSEG_WARM_DATA)) + +#define IS_NODESEG(t) \ + ((t == CURSEG_HOT_NODE) || (t == CURSEG_COLD_NODE) || \ + (t == CURSEG_WARM_NODE)) + +#define GET_SUM_BLKADDR(sbi, segno) \ + ((sbi->sm_info->ssa_blkaddr) + segno) + +#define GET_SEGOFF_FROM_SEG0(sbi, blk_addr) \ + ((blk_addr) - SM_I(sbi)->seg0_blkaddr) + +#define GET_SEGNO_FROM_SEG0(sbi, blk_addr) \ + (GET_SEGOFF_FROM_SEG0(sbi, blk_addr) >> sbi->log_blocks_per_seg) + +#define GET_BLKOFF_FROM_SEG0(sbi, blk_addr) \ + (GET_SEGOFF_FROM_SEG0(sbi, blk_addr) & (sbi->blocks_per_seg - 1)) + +#define FREE_I_START_SEGNO(sbi) \ + GET_SEGNO_FROM_SEG0(sbi, SM_I(sbi)->main_blkaddr) +#define GET_R2L_SEGNO(sbi, segno) (segno + FREE_I_START_SEGNO(sbi)) + +#define START_BLOCK(sbi, segno) (SM_I(sbi)->main_blkaddr + \ + (segno << sbi->log_blocks_per_seg)) + +static inline struct curseg_info *CURSEG_I(struct f2fs_sb_info *sbi, int type) +{ + return (struct curseg_info *)(SM_I(sbi)->curseg_array + type); +} + +static inline block_t start_sum_block(struct f2fs_sb_info *sbi) +{ + return __start_cp_addr(sbi) + le32_to_cpu(F2FS_CKPT(sbi)->cp_pack_start_sum); +} + +static inline block_t sum_blk_addr(struct f2fs_sb_info *sbi, int base, int type) +{ + return __start_cp_addr(sbi) + le32_to_cpu(F2FS_CKPT(sbi)->cp_pack_total_block_count) + - (base + 1) + type; +} + + +#define nats_in_cursum(sum) (le16_to_cpu(sum->n_nats)) +#define sits_in_cursum(sum) (le16_to_cpu(sum->n_sits)) + +#define nat_in_journal(sum, i) (sum->nat_j.entries[i].ne) +#define nid_in_journal(sum, i) (sum->nat_j.entries[i].nid) +#define sit_in_journal(sum, i) (sum->sit_j.entries[i].se) +#define segno_in_journal(sum, i) (sum->sit_j.entries[i].segno) + +#define SIT_ENTRY_OFFSET(sit_i, segno) \ + (segno % sit_i->sents_per_block) +#define SIT_BLOCK_OFFSET(sit_i, segno) \ + (segno / SIT_ENTRY_PER_BLOCK) +#define TOTAL_SEGS(sbi) (SM_I(sbi)->main_segments) + +static inline u8 IS_VALID_NID(struct f2fs_sb_info *sbi, u32 nid) +{ + return (nid <= (NAT_ENTRY_PER_BLOCK * + F2FS_RAW_SUPER(sbi)->segment_count_nat + << (sbi->log_blocks_per_seg - 1))); +} + +static inline u8 IS_VALID_BLK_ADDR(struct f2fs_sb_info *sbi, u32 addr) +{ + int i; + + if (addr >= F2FS_RAW_SUPER(sbi)->block_count || + addr < SM_I(sbi)->main_blkaddr) { + ASSERT_MSG("block addr [0x%x]\n", addr); + return 0; + } + + for (i = 0; i < NO_CHECK_TYPE; i++) { + struct curseg_info *curseg = CURSEG_I(sbi, i); + + if (START_BLOCK(sbi, curseg->segno) + + curseg->next_blkoff == addr) + return 0; + } + return 1; +} + +static inline u64 BLKOFF_FROM_MAIN(struct f2fs_sb_info *sbi, u64 blk_addr) +{ + ASSERT(blk_addr >= SM_I(sbi)->main_blkaddr); + return blk_addr - SM_I(sbi)->main_blkaddr; +} + +static inline u32 GET_SEGNO(struct f2fs_sb_info *sbi, u64 blk_addr) +{ + return (u32)(BLKOFF_FROM_MAIN(sbi, blk_addr) + >> sbi->log_blocks_per_seg); +} + +static inline u32 OFFSET_IN_SEG(struct f2fs_sb_info *sbi, u64 blk_addr) +{ + return (u32)(BLKOFF_FROM_MAIN(sbi, blk_addr) + % (1 << sbi->log_blocks_per_seg)); +} + +static inline void node_info_from_raw_nat(struct node_info *ni, + struct f2fs_nat_entry *raw_nat) +{ + ni->ino = le32_to_cpu(raw_nat->ino); + ni->blk_addr = le32_to_cpu(raw_nat->block_addr); + ni->version = raw_nat->version; +} + +extern int lookup_nat_in_journal(struct f2fs_sb_info *sbi, u32 nid, struct f2fs_nat_entry *ne); +#define IS_SUM_NODE_SEG(footer) (footer.entry_type == SUM_TYPE_NODE) + +#endif /* _F2FS_H_ */ diff --git a/f2fs/f2fs_format_utils.h b/f2fs/f2fs_format_utils.h new file mode 100644 index 0000000..aa3b062 --- /dev/null +++ b/f2fs/f2fs_format_utils.h @@ -0,0 +1,18 @@ +/** + * f2fs_format_utils.c + * + * Copyright (c) 2014 Samsung Electronics Co., Ltd. + * http://www.samsung.com/ + * + * Dual licensed under the GPL or LGPL version 2 licenses. + */ +#ifndef _LARGEFILE64_SOURCE +#define _LARGEFILE64_SOURCE +#endif + +#include "f2fs_fs.h" + +extern struct f2fs_configuration config; + +int f2fs_trim_device(void); +int f2fs_format_device(void); diff --git a/f2fs/f2fs_fs.h b/f2fs/f2fs_fs.h new file mode 100644 index 0000000..134ae65 --- /dev/null +++ b/f2fs/f2fs_fs.h @@ -0,0 +1,727 @@ +/** + * f2fs_fs.h + * + * Copyright (c) 2012 Samsung Electronics Co., Ltd. + * http://www.samsung.com/ + * + * Dual licensed under the GPL or LGPL version 2 licenses. + * + * The byteswap codes are copied from: + * samba_3_master/lib/ccan/endian/endian.h under LGPL 2.1 + */ +#ifndef __F2FS_FS_H__ +#define __F2FS_FS_H__ + +#define F2FS_MAJOR_VERSION 1 +#define F2FS_MINOR_VERSION 4 + +#include <inttypes.h> +#include <linux/types.h> +#include <sys/types.h> + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +typedef u_int64_t u64; +typedef u_int32_t u32; +typedef u_int16_t u16; +typedef u_int8_t u8; +typedef u32 block_t; +typedef u32 nid_t; +// typedef u8 bool; +typedef unsigned long pgoff_t; + +#include <byteswap.h> + +#if __BYTE_ORDER == __LITTLE_ENDIAN +#define le16_to_cpu(x) ((__u16)(x)) +#define le32_to_cpu(x) ((__u32)(x)) +#define le64_to_cpu(x) ((__u64)(x)) +#define cpu_to_le16(x) ((__u16)(x)) +#define cpu_to_le32(x) ((__u32)(x)) +#define cpu_to_le64(x) ((__u64)(x)) +#elif __BYTE_ORDER == __BIG_ENDIAN +#define le16_to_cpu(x) bswap_16(x) +#define le32_to_cpu(x) bswap_32(x) +#define le64_to_cpu(x) bswap_64(x) +#define cpu_to_le16(x) bswap_16(x) +#define cpu_to_le32(x) bswap_32(x) +#define cpu_to_le64(x) bswap_64(x) +#endif + +#define typecheck(type,x) \ + ({ type __dummy; \ + typeof(x) __dummy2; \ + (void)(&__dummy == &__dummy2); \ + 1; \ + }) + +#define NULL_SEGNO ((unsigned int)~0) + +/* + * Debugging interfaces + */ +#define FIX_MSG(fmt, ...) \ + do { \ + printf("[FIX] (%s:%4d) ", __func__, __LINE__); \ + printf(" --> "fmt"\n", ##__VA_ARGS__); \ + } while (0) + +#define ASSERT_MSG(fmt, ...) \ + do { \ + printf("[ASSERT] (%s:%4d) ", __func__, __LINE__); \ + printf(" --> "fmt"\n", ##__VA_ARGS__); \ + config.bug_on = 1; \ + } while (0) + +#define ASSERT(exp) \ + do { \ + if (!(exp)) { \ + printf("[ASSERT] (%s:%4d) " #exp"\n", \ + __func__, __LINE__); \ + exit(-1); \ + } \ + } while (0) + +#define ERR_MSG(fmt, ...) \ + do { \ + printf("[%s:%d] " fmt, __func__, __LINE__, ##__VA_ARGS__); \ + } while (0) + +#define MSG(n, fmt, ...) \ + do { \ + if (config.dbg_lv >= n) { \ + printf(fmt, ##__VA_ARGS__); \ + } \ + } while (0) + +#define DBG(n, fmt, ...) \ + do { \ + if (config.dbg_lv >= n) { \ + printf("[%s:%4d] " fmt, \ + __func__, __LINE__, ##__VA_ARGS__); \ + } \ + } while (0) + +/* Display on console */ +#define DISP(fmt, ptr, member) \ + do { \ + printf("%-30s" fmt, #member, ((ptr)->member)); \ + } while (0) + +#define DISP_u32(ptr, member) \ + do { \ + assert(sizeof((ptr)->member) <= 4); \ + printf("%-30s" "\t\t[0x%8x : %u]\n", \ + #member, ((ptr)->member), ((ptr)->member)); \ + } while (0) + +#define DISP_u64(ptr, member) \ + do { \ + assert(sizeof((ptr)->member) == 8); \ + printf("%-30s" "\t\t[0x%8llx : %llu]\n", \ + #member, ((ptr)->member), ((ptr)->member)); \ + } while (0) + +#define DISP_utf(ptr, member) \ + do { \ + printf("%-30s" "\t\t[%s]\n", #member, ((ptr)->member)); \ + } while (0) + +/* Display to buffer */ +#define BUF_DISP_u32(buf, data, len, ptr, member) \ + do { \ + assert(sizeof((ptr)->member) <= 4); \ + snprintf(buf, len, #member); \ + snprintf(data, len, "0x%x : %u", ((ptr)->member), \ + ((ptr)->member)); \ + } while (0) + +#define BUF_DISP_u64(buf, data, len, ptr, member) \ + do { \ + assert(sizeof((ptr)->member) == 8); \ + snprintf(buf, len, #member); \ + snprintf(data, len, "0x%llx : %llu", ((ptr)->member), \ + ((ptr)->member)); \ + } while (0) + +#define BUF_DISP_utf(buf, data, len, ptr, member) \ + snprintf(buf, len, #member) + +/* these are defined in kernel */ +#define PAGE_SIZE 4096 +#define PAGE_CACHE_SIZE 4096 +#define BITS_PER_BYTE 8 +#define F2FS_SUPER_MAGIC 0xF2F52010 /* F2FS Magic Number */ +#define CHECKSUM_OFFSET 4092 + +/* for mkfs */ +#define F2FS_MIN_VOLUME_SIZE 104857600 +#define F2FS_NUMBER_OF_CHECKPOINT_PACK 2 +#define DEFAULT_SECTOR_SIZE 512 +#define DEFAULT_SECTORS_PER_BLOCK 8 +#define DEFAULT_BLOCKS_PER_SEGMENT 512 +#define DEFAULT_SEGMENTS_PER_SECTION 1 + +enum f2fs_config_func { + FSCK, + DUMP, +}; + +struct f2fs_configuration { + u_int32_t sector_size; + u_int32_t reserved_segments; + u_int32_t overprovision; + u_int32_t cur_seg[6]; + u_int32_t segs_per_sec; + u_int32_t secs_per_zone; + u_int32_t start_sector; + u_int64_t total_sectors; + u_int32_t sectors_per_blk; + u_int32_t blks_per_seg; + char *vol_label; + int heap; + int32_t fd; + int32_t dump_fd; + char *device_name; + char *extension_list; + int dbg_lv; + int trim; + int func; + void *private; + int fix_on; + int bug_on; + int auto_fix; +} __attribute__((packed)); + +#ifdef CONFIG_64BIT +#define BITS_PER_LONG 64 +#else +#define BITS_PER_LONG 32 +#endif + +#define BIT_MASK(nr) (1 << (nr % BITS_PER_LONG)) +#define BIT_WORD(nr) (nr / BITS_PER_LONG) + +/* + * Copied from fs/f2fs/f2fs.h + */ +#define NR_CURSEG_DATA_TYPE (3) +#define NR_CURSEG_NODE_TYPE (3) +#define NR_CURSEG_TYPE (NR_CURSEG_DATA_TYPE + NR_CURSEG_NODE_TYPE) + +enum { + CURSEG_HOT_DATA = 0, /* directory entry blocks */ + CURSEG_WARM_DATA, /* data blocks */ + CURSEG_COLD_DATA, /* multimedia or GCed data blocks */ + CURSEG_HOT_NODE, /* direct node blocks of directory files */ + CURSEG_WARM_NODE, /* direct node blocks of normal files */ + CURSEG_COLD_NODE, /* indirect node blocks */ + NO_CHECK_TYPE +}; + +/* + * Copied from fs/f2fs/segment.h + */ +#define GET_SUM_TYPE(footer) ((footer)->entry_type) +#define SET_SUM_TYPE(footer, type) ((footer)->entry_type = type) + +/* + * Copied from include/linux/f2fs_sb.h + */ +#define F2FS_SUPER_OFFSET 1024 /* byte-size offset */ +#define F2FS_LOG_SECTOR_SIZE 9 /* 9 bits for 512 byte */ +#define F2FS_LOG_SECTORS_PER_BLOCK 3 /* 4KB: F2FS_BLKSIZE */ +#define F2FS_BLKSIZE 4096 /* support only 4KB block */ +#define F2FS_MAX_EXTENSION 64 /* # of extension entries */ +#define F2FS_BLK_ALIGN(x) (((x) + F2FS_BLKSIZE - 1) / F2FS_BLKSIZE) + +#define NULL_ADDR 0x0U +#define NEW_ADDR -1U + +#define F2FS_ROOT_INO(sbi) (sbi->root_ino_num) +#define F2FS_NODE_INO(sbi) (sbi->node_ino_num) +#define F2FS_META_INO(sbi) (sbi->meta_ino_num) + +/* This flag is used by node and meta inodes, and by recovery */ +#define GFP_F2FS_ZERO (GFP_NOFS | __GFP_ZERO) + +/* + * For further optimization on multi-head logs, on-disk layout supports maximum + * 16 logs by default. The number, 16, is expected to cover all the cases + * enoughly. The implementaion currently uses no more than 6 logs. + * Half the logs are used for nodes, and the other half are used for data. + */ +#define MAX_ACTIVE_LOGS 16 +#define MAX_ACTIVE_NODE_LOGS 8 +#define MAX_ACTIVE_DATA_LOGS 8 + +/* + * For superblock + */ +struct f2fs_super_block { + __le32 magic; /* Magic Number */ + __le16 major_ver; /* Major Version */ + __le16 minor_ver; /* Minor Version */ + __le32 log_sectorsize; /* log2 sector size in bytes */ + __le32 log_sectors_per_block; /* log2 # of sectors per block */ + __le32 log_blocksize; /* log2 block size in bytes */ + __le32 log_blocks_per_seg; /* log2 # of blocks per segment */ + __le32 segs_per_sec; /* # of segments per section */ + __le32 secs_per_zone; /* # of sections per zone */ + __le32 checksum_offset; /* checksum offset inside super block */ + __le64 block_count; /* total # of user blocks */ + __le32 section_count; /* total # of sections */ + __le32 segment_count; /* total # of segments */ + __le32 segment_count_ckpt; /* # of segments for checkpoint */ + __le32 segment_count_sit; /* # of segments for SIT */ + __le32 segment_count_nat; /* # of segments for NAT */ + __le32 segment_count_ssa; /* # of segments for SSA */ + __le32 segment_count_main; /* # of segments for main area */ + __le32 segment0_blkaddr; /* start block address of segment 0 */ + __le32 cp_blkaddr; /* start block address of checkpoint */ + __le32 sit_blkaddr; /* start block address of SIT */ + __le32 nat_blkaddr; /* start block address of NAT */ + __le32 ssa_blkaddr; /* start block address of SSA */ + __le32 main_blkaddr; /* start block address of main area */ + __le32 root_ino; /* root inode number */ + __le32 node_ino; /* node inode number */ + __le32 meta_ino; /* meta inode number */ + __u8 uuid[16]; /* 128-bit uuid for volume */ + __le16 volume_name[512]; /* volume name */ + __le32 extension_count; /* # of extensions below */ + __u8 extension_list[F2FS_MAX_EXTENSION][8]; /* extension array */ + __le32 cp_payload; +} __attribute__((packed)); + +/* + * For checkpoint + */ +#define CP_FSCK_FLAG 0x00000010 +#define CP_ERROR_FLAG 0x00000008 +#define CP_COMPACT_SUM_FLAG 0x00000004 +#define CP_ORPHAN_PRESENT_FLAG 0x00000002 +#define CP_UMOUNT_FLAG 0x00000001 + +struct f2fs_checkpoint { + __le64 checkpoint_ver; /* checkpoint block version number */ + __le64 user_block_count; /* # of user blocks */ + __le64 valid_block_count; /* # of valid blocks in main area */ + __le32 rsvd_segment_count; /* # of reserved segments for gc */ + __le32 overprov_segment_count; /* # of overprovision segments */ + __le32 free_segment_count; /* # of free segments in main area */ + + /* information of current node segments */ + __le32 cur_node_segno[MAX_ACTIVE_NODE_LOGS]; + __le16 cur_node_blkoff[MAX_ACTIVE_NODE_LOGS]; + /* information of current data segments */ + __le32 cur_data_segno[MAX_ACTIVE_DATA_LOGS]; + __le16 cur_data_blkoff[MAX_ACTIVE_DATA_LOGS]; + __le32 ckpt_flags; /* Flags : umount and journal_present */ + __le32 cp_pack_total_block_count; /* total # of one cp pack */ + __le32 cp_pack_start_sum; /* start block number of data summary */ + __le32 valid_node_count; /* Total number of valid nodes */ + __le32 valid_inode_count; /* Total number of valid inodes */ + __le32 next_free_nid; /* Next free node number */ + __le32 sit_ver_bitmap_bytesize; /* Default value 64 */ + __le32 nat_ver_bitmap_bytesize; /* Default value 256 */ + __le32 checksum_offset; /* checksum offset inside cp block */ + __le64 elapsed_time; /* mounted time */ + /* allocation type of current segment */ + unsigned char alloc_type[MAX_ACTIVE_LOGS]; + + /* SIT and NAT version bitmap */ + unsigned char sit_nat_version_bitmap[1]; +} __attribute__((packed)); + +/* + * For orphan inode management + */ +#define F2FS_ORPHANS_PER_BLOCK 1020 + +struct f2fs_orphan_block { + __le32 ino[F2FS_ORPHANS_PER_BLOCK]; /* inode numbers */ + __le32 reserved; /* reserved */ + __le16 blk_addr; /* block index in current CP */ + __le16 blk_count; /* Number of orphan inode blocks in CP */ + __le32 entry_count; /* Total number of orphan nodes in current CP */ + __le32 check_sum; /* CRC32 for orphan inode block */ +} __attribute__((packed)); + +/* + * For NODE structure + */ +struct f2fs_extent { + __le32 fofs; /* start file offset of the extent */ + __le32 blk_addr; /* start block address of the extent */ + __le32 len; /* lengh of the extent */ +} __attribute__((packed)); + +#define F2FS_NAME_LEN 255 +#define F2FS_INLINE_XATTR_ADDRS 50 /* 200 bytes for inline xattrs */ +#define DEF_ADDRS_PER_INODE 923 /* Address Pointers in an Inode */ +#define ADDRS_PER_INODE(fi) addrs_per_inode(fi) +#define ADDRS_PER_BLOCK 1018 /* Address Pointers in a Direct Block */ +#define NIDS_PER_BLOCK 1018 /* Node IDs in an Indirect Block */ + +#define NODE_DIR1_BLOCK (DEF_ADDRS_PER_INODE + 1) +#define NODE_DIR2_BLOCK (DEF_ADDRS_PER_INODE + 2) +#define NODE_IND1_BLOCK (DEF_ADDRS_PER_INODE + 3) +#define NODE_IND2_BLOCK (DEF_ADDRS_PER_INODE + 4) +#define NODE_DIND_BLOCK (DEF_ADDRS_PER_INODE + 5) + +#define F2FS_INLINE_XATTR 0x01 /* file inline xattr flag */ +#define F2FS_INLINE_DATA 0x02 /* file inline data flag */ +#define F2FS_INLINE_DENTRY 0x04 /* file inline dentry flag */ + +#define MAX_INLINE_DATA (sizeof(__le32) * (DEF_ADDRS_PER_INODE - \ + F2FS_INLINE_XATTR_ADDRS - 1)) + +#define INLINE_DATA_OFFSET (PAGE_CACHE_SIZE - sizeof(struct node_footer) \ + - sizeof(__le32)*(DEF_ADDRS_PER_INODE + 5 - 1)) + +#define DEF_DIR_LEVEL 0 + +struct f2fs_inode { + __le16 i_mode; /* file mode */ + __u8 i_advise; /* file hints */ + __u8 i_inline; /* file inline flags */ + __le32 i_uid; /* user ID */ + __le32 i_gid; /* group ID */ + __le32 i_links; /* links count */ + __le64 i_size; /* file size in bytes */ + __le64 i_blocks; /* file size in blocks */ + __le64 i_atime; /* access time */ + __le64 i_ctime; /* change time */ + __le64 i_mtime; /* modification time */ + __le32 i_atime_nsec; /* access time in nano scale */ + __le32 i_ctime_nsec; /* change time in nano scale */ + __le32 i_mtime_nsec; /* modification time in nano scale */ + __le32 i_generation; /* file version (for NFS) */ + __le32 i_current_depth; /* only for directory depth */ + __le32 i_xattr_nid; /* nid to save xattr */ + __le32 i_flags; /* file attributes */ + __le32 i_pino; /* parent inode number */ + __le32 i_namelen; /* file name length */ + __u8 i_name[F2FS_NAME_LEN]; /* file name for SPOR */ + __u8 i_dir_level; /* dentry_level for large dir */ + + struct f2fs_extent i_ext; /* caching a largest extent */ + + __le32 i_addr[DEF_ADDRS_PER_INODE]; /* Pointers to data blocks */ + + __le32 i_nid[5]; /* direct(2), indirect(2), + double_indirect(1) node id */ +} __attribute__((packed)); + +struct direct_node { + __le32 addr[ADDRS_PER_BLOCK]; /* array of data block address */ +} __attribute__((packed)); + +struct indirect_node { + __le32 nid[NIDS_PER_BLOCK]; /* array of data block address */ +} __attribute__((packed)); + +enum { + COLD_BIT_SHIFT = 0, + FSYNC_BIT_SHIFT, + DENT_BIT_SHIFT, + OFFSET_BIT_SHIFT +}; + +#define XATTR_NODE_OFFSET ((((unsigned int)-1) << OFFSET_BIT_SHIFT) \ + >> OFFSET_BIT_SHIFT) + +struct node_footer { + __le32 nid; /* node id */ + __le32 ino; /* inode nunmber */ + __le32 flag; /* include cold/fsync/dentry marks and offset */ + __le64 cp_ver; /* checkpoint version */ + __le32 next_blkaddr; /* next node page block address */ +} __attribute__((packed)); + +struct f2fs_node { + /* can be one of three types: inode, direct, and indirect types */ + union { + struct f2fs_inode i; + struct direct_node dn; + struct indirect_node in; + }; + struct node_footer footer; +} __attribute__((packed)); + +/* + * For NAT entries + */ +#define NAT_ENTRY_PER_BLOCK (PAGE_CACHE_SIZE / sizeof(struct f2fs_nat_entry)) + +struct f2fs_nat_entry { + __u8 version; /* latest version of cached nat entry */ + __le32 ino; /* inode number */ + __le32 block_addr; /* block address */ +} __attribute__((packed)); + +struct f2fs_nat_block { + struct f2fs_nat_entry entries[NAT_ENTRY_PER_BLOCK]; +} __attribute__((packed)); + +/* + * For SIT entries + * + * Each segment is 2MB in size by default so that a bitmap for validity of + * there-in blocks should occupy 64 bytes, 512 bits. + * Not allow to change this. + */ +#define SIT_VBLOCK_MAP_SIZE 64 +#define SIT_ENTRY_PER_BLOCK (PAGE_CACHE_SIZE / sizeof(struct f2fs_sit_entry)) + +/* + * F2FS uses 4 bytes to represent block address. As a result, supported size of + * disk is 16 TB and it equals to 16 * 1024 * 1024 / 2 segments. + */ +#define F2FS_MAX_SEGMENT ((16 * 1024 * 1024) / 2) +#define MAX_SIT_BITMAP_SIZE ((F2FS_MAX_SEGMENT / SIT_ENTRY_PER_BLOCK) / 8) + +/* + * Note that f2fs_sit_entry->vblocks has the following bit-field information. + * [15:10] : allocation type such as CURSEG_XXXX_TYPE + * [9:0] : valid block count + */ +#define SIT_VBLOCKS_SHIFT 10 +#define SIT_VBLOCKS_MASK ((1 << SIT_VBLOCKS_SHIFT) - 1) +#define GET_SIT_VBLOCKS(raw_sit) \ + (le16_to_cpu((raw_sit)->vblocks) & SIT_VBLOCKS_MASK) +#define GET_SIT_TYPE(raw_sit) \ + ((le16_to_cpu((raw_sit)->vblocks) & ~SIT_VBLOCKS_MASK) \ + >> SIT_VBLOCKS_SHIFT) + +struct f2fs_sit_entry { + __le16 vblocks; /* reference above */ + __u8 valid_map[SIT_VBLOCK_MAP_SIZE]; /* bitmap for valid blocks */ + __le64 mtime; /* segment age for cleaning */ +} __attribute__((packed)); + +struct f2fs_sit_block { + struct f2fs_sit_entry entries[SIT_ENTRY_PER_BLOCK]; +} __attribute__((packed)); + +/* + * For segment summary + * + * One summary block contains exactly 512 summary entries, which represents + * exactly 2MB segment by default. Not allow to change the basic units. + * + * NOTE: For initializing fields, you must use set_summary + * + * - If data page, nid represents dnode's nid + * - If node page, nid represents the node page's nid. + * + * The ofs_in_node is used by only data page. It represents offset + * from node's page's beginning to get a data block address. + * ex) data_blkaddr = (block_t)(nodepage_start_address + ofs_in_node) + */ +#define ENTRIES_IN_SUM 512 +#define SUMMARY_SIZE (7) /* sizeof(struct summary) */ +#define SUM_FOOTER_SIZE (5) /* sizeof(struct summary_footer) */ +#define SUM_ENTRIES_SIZE (SUMMARY_SIZE * ENTRIES_IN_SUM) + +/* a summary entry for a 4KB-sized block in a segment */ +struct f2fs_summary { + __le32 nid; /* parent node id */ + union { + __u8 reserved[3]; + struct { + __u8 version; /* node version number */ + __le16 ofs_in_node; /* block index in parent node */ + } __attribute__((packed)); + }; +} __attribute__((packed)); + +/* summary block type, node or data, is stored to the summary_footer */ +#define SUM_TYPE_NODE (1) +#define SUM_TYPE_DATA (0) + +struct summary_footer { + unsigned char entry_type; /* SUM_TYPE_XXX */ + __u32 check_sum; /* summary checksum */ +} __attribute__((packed)); + +#define SUM_JOURNAL_SIZE (F2FS_BLKSIZE - SUM_FOOTER_SIZE -\ + SUM_ENTRIES_SIZE) +#define NAT_JOURNAL_ENTRIES ((SUM_JOURNAL_SIZE - 2) /\ + sizeof(struct nat_journal_entry)) +#define NAT_JOURNAL_RESERVED ((SUM_JOURNAL_SIZE - 2) %\ + sizeof(struct nat_journal_entry)) +#define SIT_JOURNAL_ENTRIES ((SUM_JOURNAL_SIZE - 2) /\ + sizeof(struct sit_journal_entry)) +#define SIT_JOURNAL_RESERVED ((SUM_JOURNAL_SIZE - 2) %\ + sizeof(struct sit_journal_entry)) +/* + * frequently updated NAT/SIT entries can be stored in the spare area in + * summary blocks + */ +enum { + NAT_JOURNAL = 0, + SIT_JOURNAL +}; + +struct nat_journal_entry { + __le32 nid; + struct f2fs_nat_entry ne; +} __attribute__((packed)); + +struct nat_journal { + struct nat_journal_entry entries[NAT_JOURNAL_ENTRIES]; + __u8 reserved[NAT_JOURNAL_RESERVED]; +} __attribute__((packed)); + +struct sit_journal_entry { + __le32 segno; + struct f2fs_sit_entry se; +} __attribute__((packed)); + +struct sit_journal { + struct sit_journal_entry entries[SIT_JOURNAL_ENTRIES]; + __u8 reserved[SIT_JOURNAL_RESERVED]; +} __attribute__((packed)); + +/* 4KB-sized summary block structure */ +struct f2fs_summary_block { + struct f2fs_summary entries[ENTRIES_IN_SUM]; + union { + __le16 n_nats; + __le16 n_sits; + }; + /* spare area is used by NAT or SIT journals */ + union { + struct nat_journal nat_j; + struct sit_journal sit_j; + }; + struct summary_footer footer; +} __attribute__((packed)); + +/* + * For directory operations + */ +#define F2FS_DOT_HASH 0 +#define F2FS_DDOT_HASH F2FS_DOT_HASH +#define F2FS_MAX_HASH (~((0x3ULL) << 62)) +#define F2FS_HASH_COL_BIT ((0x1ULL) << 63) + +typedef __le32 f2fs_hash_t; + +/* One directory entry slot covers 8bytes-long file name */ +#define F2FS_SLOT_LEN 8 +#define F2FS_SLOT_LEN_BITS 3 + +#define GET_DENTRY_SLOTS(x) ((x + F2FS_SLOT_LEN - 1) >> F2FS_SLOT_LEN_BITS) + +/* the number of dentry in a block */ +#define NR_DENTRY_IN_BLOCK 214 + +/* MAX level for dir lookup */ +#define MAX_DIR_HASH_DEPTH 63 + +#define SIZE_OF_DIR_ENTRY 11 /* by byte */ +#define SIZE_OF_DENTRY_BITMAP ((NR_DENTRY_IN_BLOCK + BITS_PER_BYTE - 1) / \ + BITS_PER_BYTE) +#define SIZE_OF_RESERVED (PAGE_SIZE - ((SIZE_OF_DIR_ENTRY + \ + F2FS_SLOT_LEN) * \ + NR_DENTRY_IN_BLOCK + SIZE_OF_DENTRY_BITMAP)) + +/* One directory entry slot representing F2FS_SLOT_LEN-sized file name */ +struct f2fs_dir_entry { + __le32 hash_code; /* hash code of file name */ + __le32 ino; /* inode number */ + __le16 name_len; /* lengh of file name */ + __u8 file_type; /* file type */ +} __attribute__((packed)); + +/* 4KB-sized directory entry block */ +struct f2fs_dentry_block { + /* validity bitmap for directory entries in each block */ + __u8 dentry_bitmap[SIZE_OF_DENTRY_BITMAP]; + __u8 reserved[SIZE_OF_RESERVED]; + struct f2fs_dir_entry dentry[NR_DENTRY_IN_BLOCK]; + __u8 filename[NR_DENTRY_IN_BLOCK][F2FS_SLOT_LEN]; +} __attribute__((packed)); + +/* for inline dir */ +#define NR_INLINE_DENTRY (MAX_INLINE_DATA * BITS_PER_BYTE / \ + ((SIZE_OF_DIR_ENTRY + F2FS_SLOT_LEN) * \ + BITS_PER_BYTE + 1)) +#define INLINE_DENTRY_BITMAP_SIZE ((NR_INLINE_DENTRY + \ + BITS_PER_BYTE - 1) / BITS_PER_BYTE) +#define INLINE_RESERVED_SIZE (MAX_INLINE_DATA - \ + ((SIZE_OF_DIR_ENTRY + F2FS_SLOT_LEN) * \ + NR_INLINE_DENTRY + INLINE_DENTRY_BITMAP_SIZE)) + +/* inline directory entry structure */ +struct f2fs_inline_dentry { + __u8 dentry_bitmap[INLINE_DENTRY_BITMAP_SIZE]; + __u8 reserved[INLINE_RESERVED_SIZE]; + struct f2fs_dir_entry dentry[NR_INLINE_DENTRY]; + __u8 filename[NR_INLINE_DENTRY][F2FS_SLOT_LEN]; +} __packed; + +/* file types used in inode_info->flags */ +enum FILE_TYPE { + F2FS_FT_UNKNOWN, + F2FS_FT_REG_FILE, + F2FS_FT_DIR, + F2FS_FT_CHRDEV, + F2FS_FT_BLKDEV, + F2FS_FT_FIFO, + F2FS_FT_SOCK, + F2FS_FT_SYMLINK, + F2FS_FT_MAX, + /* added for fsck */ + F2FS_FT_ORPHAN, + F2FS_FT_XATTR, + F2FS_FT_LAST_FILE_TYPE = F2FS_FT_XATTR, +}; + +/* from f2fs/segment.h */ +enum { + LFS = 0, + SSR +}; + +extern void ASCIIToUNICODE(u_int16_t *, u_int8_t *); +extern int log_base_2(u_int32_t); +extern unsigned int addrs_per_inode(struct f2fs_inode *); + +extern int get_bits_in_byte(unsigned char n); +extern int set_bit(unsigned int nr,void * addr); +extern int clear_bit(unsigned int nr, void * addr); +extern int test_bit(unsigned int nr, const void * addr); +extern int f2fs_test_bit(unsigned int, const char *); +extern int f2fs_set_bit(unsigned int, char *); +extern int f2fs_clear_bit(unsigned int, char *); +extern unsigned long find_next_bit(const unsigned long *, + unsigned long, unsigned long); + +extern u_int32_t f2fs_cal_crc32(u_int32_t, void *, int); +extern int f2fs_crc_valid(u_int32_t blk_crc, void *buf, int len); + +extern void f2fs_init_configuration(struct f2fs_configuration *); +extern int f2fs_dev_is_umounted(struct f2fs_configuration *); +extern int f2fs_get_device_info(struct f2fs_configuration *); +extern void f2fs_finalize_device(struct f2fs_configuration *); + +extern int dev_read(void *, __u64, size_t); +extern int dev_write(void *, __u64, size_t); +extern int dev_write_block(void *, __u64); +extern int dev_write_dump(void *, __u64, size_t); +/* All bytes in the buffer must be 0 use dev_fill(). */ +extern int dev_fill(void *, __u64, size_t); + +extern int dev_read_block(void *, __u64); +extern int dev_read_blocks(void *, __u64, __u32 ); + +f2fs_hash_t f2fs_dentry_hash(const unsigned char *, int); + +extern struct f2fs_configuration config; + +#endif /*__F2FS_FS_H */ diff --git a/f2fs/fsck.h b/f2fs/fsck.h new file mode 100644 index 0000000..49d6d1d --- /dev/null +++ b/f2fs/fsck.h @@ -0,0 +1,131 @@ +/** + * fsck.h + * + * Copyright (c) 2013 Samsung Electronics Co., Ltd. + * http://www.samsung.com/ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ +#ifndef _FSCK_H_ +#define _FSCK_H_ + +#include "f2fs.h" + +/* fsck.c */ +struct orphan_info { + u32 nr_inodes; + u32 *ino_list; +}; + +struct f2fs_fsck { + struct f2fs_sb_info sbi; + + struct orphan_info orphani; + struct chk_result { + u64 valid_blk_cnt; + u32 valid_nat_entry_cnt; + u32 valid_node_cnt; + u32 valid_inode_cnt; + u32 multi_hard_link_files; + u64 sit_valid_blocks; + u32 sit_free_segs; + u32 free_segs; + } chk; + + struct hard_link_node *hard_link_list_head; + + char *main_seg_usage; + char *main_area_bitmap; + char *nat_area_bitmap; + char *sit_area_bitmap; + + u64 main_area_bitmap_sz; + u32 nat_area_bitmap_sz; + u32 sit_area_bitmap_sz; + + u64 nr_main_blks; + u32 nr_nat_entries; + + u32 dentry_depth; +}; + +#define BLOCK_SZ 4096 +struct block { + unsigned char buf[BLOCK_SZ]; +}; + +enum NODE_TYPE { + TYPE_INODE = 37, + TYPE_DIRECT_NODE = 43, + TYPE_INDIRECT_NODE = 53, + TYPE_DOUBLE_INDIRECT_NODE = 67, + TYPE_XATTR = 77 +}; + +struct hard_link_node { + u32 nid; + u32 links; + struct hard_link_node *next; +}; + +enum seg_type { + SEG_TYPE_DATA, + SEG_TYPE_CUR_DATA, + SEG_TYPE_NODE, + SEG_TYPE_CUR_NODE, + SEG_TYPE_MAX, +}; + +extern void fsck_chk_orphan_node(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 *); +extern void fsck_chk_inode_blk(struct f2fs_sb_info *, u32, enum FILE_TYPE, + struct f2fs_node *, u32 *, struct node_info *); +extern int fsck_chk_dnode_blk(struct f2fs_sb_info *, struct f2fs_inode *, + u32, enum FILE_TYPE, struct f2fs_node *, u32 *, + struct node_info *); +extern int fsck_chk_idnode_blk(struct f2fs_sb_info *, struct f2fs_inode *, + enum FILE_TYPE, struct f2fs_node *, u32 *); +extern int fsck_chk_didnode_blk(struct f2fs_sb_info *, struct f2fs_inode *, + enum FILE_TYPE, struct f2fs_node *, u32 *); +extern int fsck_chk_data_blk(struct f2fs_sb_info *sbi, u32, u32 *, u32 *, + int, enum FILE_TYPE, u32, u16, u8); +extern int fsck_chk_dentry_blk(struct f2fs_sb_info *, u32, u32 *, u32 *, int); +int fsck_chk_inline_dentries(struct f2fs_sb_info *, struct f2fs_node *, + u32 *, u32 *); + +extern void print_node_info(struct f2fs_node *); +extern void print_inode_info(struct f2fs_inode *); +extern struct seg_entry *get_seg_entry(struct f2fs_sb_info *, unsigned int); +extern int get_sum_block(struct f2fs_sb_info *, unsigned int, + struct f2fs_summary_block *); +extern int get_sum_entry(struct f2fs_sb_info *, u32, struct f2fs_summary *); +extern void get_node_info(struct f2fs_sb_info *, nid_t, struct node_info *); +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 void fsck_init(struct f2fs_sb_info *); +extern int fsck_verify(struct f2fs_sb_info *); +extern void fsck_free(struct f2fs_sb_info *); +extern int f2fs_do_mount(struct f2fs_sb_info *); +extern void f2fs_do_umount(struct f2fs_sb_info *); + +/* dump.c */ +struct dump_option { + nid_t nid; + int start_sit; + int end_sit; + int start_ssa; + int end_ssa; + int32_t blk_addr; +}; + +extern void sit_dump(struct f2fs_sb_info *, int, int); +extern void ssa_dump(struct f2fs_sb_info *, int, int); +extern void dump_node(struct f2fs_sb_info *, nid_t); +extern int dump_inode_from_blkaddr(struct f2fs_sb_info *, u32); + +#endif /* _FSCK_H_ */ diff --git a/f2fs/list.h b/f2fs/list.h new file mode 100644 index 0000000..571cd5c --- /dev/null +++ b/f2fs/list.h @@ -0,0 +1,88 @@ + +#define POISON_POINTER_DELTA 0 +#define LIST_POISON1 ((void *) (0x00100100 + POISON_POINTER_DELTA)) +#define LIST_POISON2 ((void *) (0x00200200 + POISON_POINTER_DELTA)) + +#if !defined(offsetof) +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) +#endif +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +struct list_head { + struct list_head *next, *prev; +}; + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +static inline void INIT_LIST_HEAD(struct list_head *list) +{ + list->next = list; + list->prev = list; +} + +static inline void __list_add(struct list_head *new, + struct list_head *prev, + struct list_head *next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +static inline void list_add(struct list_head *new, struct list_head *head) +{ + __list_add(new, head, head->next); +} + +static inline void list_add_tail(struct list_head *new, struct list_head *head) +{ + __list_add(new, head->prev, head); +} + +static inline void __list_del(struct list_head * prev, struct list_head * next) +{ + next->prev = prev; + prev->next = next; +} + +static inline void __list_del_entry(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); +} + +static inline void list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + entry->next = LIST_POISON1; + entry->prev = LIST_POISON2; +} + +static inline int list_empty(const struct list_head *head) +{ + return head->next == head; +} + +#define list_entry(ptr, type, member) \ + container_of(ptr, type, member) + +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member))
_______________________________________________ busybox mailing list [email protected] http://lists.busybox.net/mailman/listinfo/busybox
