1#define _LARGEFILE64_SOURCE
2
3#define LOG_TAG "f2fs_sparseblock"
4
5#include <errno.h>
6#include <f2fs_fs.h>
7#include <fcntl.h>
8#include <linux/types.h>
9#include <malloc.h>
10#include <string.h>
11#include <sys/stat.h>
12#include <sys/types.h>
13#include <unistd.h>
14
15#include <log/log.h>
16
17#include "f2fs_sparseblock.h"
18
19#define D_DISP_u32(ptr, member)           \
20  do {                \
21    SLOGD("%-30s" "\t\t[0x%#08x : %u]\n",    \
22      #member, le32_to_cpu((ptr)->member), le32_to_cpu((ptr)->member) );  \
23  } while (0);
24
25#define D_DISP_u64(ptr, member)           \
26  do {                \
27    SLOGD("%-30s" "\t\t[0x%#016llx : %llu]\n",    \
28      #member, le64_to_cpu((ptr)->member), le64_to_cpu((ptr)->member) );  \
29  } while (0);
30
31#define segno_in_journal(sum, i)    ((sum)->sit_j.entries[i].segno)
32
33#define sit_in_journal(sum, i)      ((sum)->sit_j.entries[i].se)
34
35static void dbg_print_raw_sb_info(struct f2fs_super_block *sb)
36{
37    SLOGD("\n");
38    SLOGD("+--------------------------------------------------------+\n");
39    SLOGD("| Super block                                            |\n");
40    SLOGD("+--------------------------------------------------------+\n");
41
42    D_DISP_u32(sb, magic);
43    D_DISP_u32(sb, major_ver);
44    D_DISP_u32(sb, minor_ver);
45    D_DISP_u32(sb, log_sectorsize);
46    D_DISP_u32(sb, log_sectors_per_block);
47
48    D_DISP_u32(sb, log_blocksize);
49    D_DISP_u32(sb, log_blocks_per_seg);
50    D_DISP_u32(sb, segs_per_sec);
51    D_DISP_u32(sb, secs_per_zone);
52    D_DISP_u32(sb, checksum_offset);
53    D_DISP_u64(sb, block_count);
54
55    D_DISP_u32(sb, section_count);
56    D_DISP_u32(sb, segment_count);
57    D_DISP_u32(sb, segment_count_ckpt);
58    D_DISP_u32(sb, segment_count_sit);
59    D_DISP_u32(sb, segment_count_nat);
60
61    D_DISP_u32(sb, segment_count_ssa);
62    D_DISP_u32(sb, segment_count_main);
63    D_DISP_u32(sb, segment0_blkaddr);
64
65    D_DISP_u32(sb, cp_blkaddr);
66    D_DISP_u32(sb, sit_blkaddr);
67    D_DISP_u32(sb, nat_blkaddr);
68    D_DISP_u32(sb, ssa_blkaddr);
69    D_DISP_u32(sb, main_blkaddr);
70
71    D_DISP_u32(sb, root_ino);
72    D_DISP_u32(sb, node_ino);
73    D_DISP_u32(sb, meta_ino);
74    D_DISP_u32(sb, cp_payload);
75    SLOGD("\n");
76}
77static void dbg_print_raw_ckpt_struct(struct f2fs_checkpoint *cp)
78{
79    SLOGD("\n");
80    SLOGD("+--------------------------------------------------------+\n");
81    SLOGD("| Checkpoint                                             |\n");
82    SLOGD("+--------------------------------------------------------+\n");
83
84    D_DISP_u64(cp, checkpoint_ver);
85    D_DISP_u64(cp, user_block_count);
86    D_DISP_u64(cp, valid_block_count);
87    D_DISP_u32(cp, rsvd_segment_count);
88    D_DISP_u32(cp, overprov_segment_count);
89    D_DISP_u32(cp, free_segment_count);
90
91    D_DISP_u32(cp, alloc_type[CURSEG_HOT_NODE]);
92    D_DISP_u32(cp, alloc_type[CURSEG_WARM_NODE]);
93    D_DISP_u32(cp, alloc_type[CURSEG_COLD_NODE]);
94    D_DISP_u32(cp, cur_node_segno[0]);
95    D_DISP_u32(cp, cur_node_segno[1]);
96    D_DISP_u32(cp, cur_node_segno[2]);
97
98    D_DISP_u32(cp, cur_node_blkoff[0]);
99    D_DISP_u32(cp, cur_node_blkoff[1]);
100    D_DISP_u32(cp, cur_node_blkoff[2]);
101
102
103    D_DISP_u32(cp, alloc_type[CURSEG_HOT_DATA]);
104    D_DISP_u32(cp, alloc_type[CURSEG_WARM_DATA]);
105    D_DISP_u32(cp, alloc_type[CURSEG_COLD_DATA]);
106    D_DISP_u32(cp, cur_data_segno[0]);
107    D_DISP_u32(cp, cur_data_segno[1]);
108    D_DISP_u32(cp, cur_data_segno[2]);
109
110    D_DISP_u32(cp, cur_data_blkoff[0]);
111    D_DISP_u32(cp, cur_data_blkoff[1]);
112    D_DISP_u32(cp, cur_data_blkoff[2]);
113
114    D_DISP_u32(cp, ckpt_flags);
115    D_DISP_u32(cp, cp_pack_total_block_count);
116    D_DISP_u32(cp, cp_pack_start_sum);
117    D_DISP_u32(cp, valid_node_count);
118    D_DISP_u32(cp, valid_inode_count);
119    D_DISP_u32(cp, next_free_nid);
120    D_DISP_u32(cp, sit_ver_bitmap_bytesize);
121    D_DISP_u32(cp, nat_ver_bitmap_bytesize);
122    D_DISP_u32(cp, checksum_offset);
123    D_DISP_u64(cp, elapsed_time);
124
125    D_DISP_u32(cp, sit_nat_version_bitmap[0]);
126    SLOGD("\n\n");
127}
128
129static void dbg_print_info_struct(struct f2fs_info *info)
130{
131    SLOGD("\n");
132    SLOGD("+--------------------------------------------------------+\n");
133    SLOGD("| F2FS_INFO                                              |\n");
134    SLOGD("+--------------------------------------------------------+\n");
135    SLOGD("blocks_per_segment: %"PRIu64, info->blocks_per_segment);
136    SLOGD("block_size: %d", info->block_size);
137    SLOGD("sit_bmp loc: %p", info->sit_bmp);
138    SLOGD("sit_bmp_size: %d", info->sit_bmp_size);
139    SLOGD("blocks_per_sit: %"PRIu64, info->blocks_per_sit);
140    SLOGD("sit_blocks loc: %p", info->sit_blocks);
141    SLOGD("sit_sums loc: %p", info->sit_sums);
142    SLOGD("sit_sums num: %d", le16_to_cpu(info->sit_sums->n_sits));
143    unsigned int i;
144    for(i = 0; i < (le16_to_cpu(info->sit_sums->n_sits)); i++) {
145        SLOGD("entry %d in journal entries is for segment %d",i, le32_to_cpu(segno_in_journal(info->sit_sums, i)));
146    }
147
148    SLOGD("cp_blkaddr: %"PRIu64, info->cp_blkaddr);
149    SLOGD("cp_valid_cp_blkaddr: %"PRIu64, info->cp_valid_cp_blkaddr);
150    SLOGD("sit_blkaddr: %"PRIu64, info->sit_blkaddr);
151    SLOGD("nat_blkaddr: %"PRIu64, info->nat_blkaddr);
152    SLOGD("ssa_blkaddr: %"PRIu64, info->ssa_blkaddr);
153    SLOGD("main_blkaddr: %"PRIu64, info->main_blkaddr);
154    SLOGD("total_user_used: %"PRIu64, info->total_user_used);
155    SLOGD("total_blocks: %"PRIu64, info->total_blocks);
156    SLOGD("\n\n");
157}
158
159
160/* read blocks */
161static int read_structure(int fd, unsigned long long start, void *buf, ssize_t len)
162{
163    off64_t ret;
164
165    ret = lseek64(fd, start, SEEK_SET);
166    if (ret < 0) {
167        SLOGE("failed to seek\n");
168        return ret;
169    }
170
171    ret = read(fd, buf, len);
172    if (ret < 0) {
173        SLOGE("failed to read\n");
174        return ret;
175    }
176    if (ret != len) {
177        SLOGE("failed to read all\n");
178        return -1;
179    }
180    return 0;
181}
182
183static int read_structure_blk(int fd, unsigned long long start_blk, void *buf, size_t len)
184{
185    return read_structure(fd, F2FS_BLKSIZE*start_blk, buf, F2FS_BLKSIZE * len);
186}
187
188static int read_f2fs_sb(int fd, struct f2fs_super_block *sb)
189{
190    int rc;
191    rc = read_structure(fd, F2FS_SUPER_OFFSET, sb, sizeof(*sb));
192    if (le32_to_cpu(sb->magic) != F2FS_SUPER_MAGIC) {
193        SLOGE("Not a valid F2FS super block. Magic:%#08x != %#08x",
194                                  le32_to_cpu(sb->magic), F2FS_SUPER_MAGIC);
195        return -1;
196    }
197    return 0;
198}
199
200unsigned int get_f2fs_filesystem_size_sec(char *dev)
201{
202    int fd;
203    if ((fd = open(dev, O_RDONLY)) < 0) {
204        SLOGE("Cannot open device to get filesystem size ");
205        return 0;
206    }
207    struct f2fs_super_block sb;
208    if(read_f2fs_sb(fd, &sb))
209        return 0;
210    return (unsigned int)(le64_to_cpu(sb.block_count)*F2FS_BLKSIZE/DEFAULT_SECTOR_SIZE);
211}
212
213static struct f2fs_checkpoint *validate_checkpoint(block_t cp_addr,
214                                                   unsigned long long *version, int fd)
215{
216    unsigned char *cp_block_1, *cp_block_2;
217    struct f2fs_checkpoint *cp_block, *cp_ret;
218    u64 cp1_version = 0, cp2_version = 0;
219
220    cp_block_1 = malloc(F2FS_BLKSIZE);
221    if (!cp_block_1)
222        return NULL;
223
224    /* Read the 1st cp block in this CP pack */
225    if (read_structure_blk(fd, cp_addr, cp_block_1, 1))
226        goto invalid_cp1;
227
228    /* get the version number */
229    cp_block = (struct f2fs_checkpoint *)cp_block_1;
230
231    cp1_version = le64_to_cpu(cp_block->checkpoint_ver);
232
233    cp_block_2 = malloc(F2FS_BLKSIZE);
234    if (!cp_block_2) {
235        goto invalid_cp1;
236    }
237    /* Read the 2nd cp block in this CP pack */
238    cp_addr += le32_to_cpu(cp_block->cp_pack_total_block_count) - 1;
239    if (read_structure_blk(fd, cp_addr, cp_block_2, 1)) {
240        goto invalid_cp2;
241    }
242
243    cp_block = (struct f2fs_checkpoint *)cp_block_2;
244
245    cp2_version = le64_to_cpu(cp_block->checkpoint_ver);
246
247    if (cp2_version == cp1_version) {
248        *version = cp2_version;
249        free(cp_block_2);
250        return (struct f2fs_checkpoint *)cp_block_1;
251    }
252
253    /* There must be something wrong with this checkpoint */
254invalid_cp2:
255    free(cp_block_2);
256invalid_cp1:
257    free(cp_block_1);
258    return NULL;
259}
260
261int get_valid_checkpoint_info(int fd, struct f2fs_super_block *sb, struct f2fs_checkpoint **cp,  struct f2fs_info *info)
262{
263    struct f2fs_checkpoint *cp_block;
264
265    struct f2fs_checkpoint *cp1, *cp2, *cur_cp;
266    int cur_cp_no;
267    unsigned long blk_size;
268    unsigned long long cp1_version = 0, cp2_version = 0;
269    unsigned long long cp1_start_blk_no;
270    unsigned long long cp2_start_blk_no;
271    u32 bmp_size;
272
273    blk_size = 1U << le32_to_cpu(sb->log_blocksize);
274
275    /*
276     * Find valid cp by reading both packs and finding most recent one.
277     */
278    cp1_start_blk_no = le32_to_cpu(sb->cp_blkaddr);
279    cp1 = validate_checkpoint(cp1_start_blk_no, &cp1_version, fd);
280
281    /* The second checkpoint pack should start at the next segment */
282    cp2_start_blk_no = cp1_start_blk_no + (1 << le32_to_cpu(sb->log_blocks_per_seg));
283    cp2 = validate_checkpoint(cp2_start_blk_no, &cp2_version, fd);
284
285    if (cp1 && cp2) {
286        if (ver_after(cp2_version, cp1_version)) {
287            cur_cp = cp2;
288            info->cp_valid_cp_blkaddr = cp2_start_blk_no;
289            free(cp1);
290        } else {
291            cur_cp = cp1;
292            info->cp_valid_cp_blkaddr = cp1_start_blk_no;
293            free(cp2);
294        }
295    } else if (cp1) {
296        cur_cp = cp1;
297        info->cp_valid_cp_blkaddr = cp1_start_blk_no;
298    } else if (cp2) {
299        cur_cp = cp2;
300        info->cp_valid_cp_blkaddr = cp2_start_blk_no;
301    } else {
302        goto fail_no_cp;
303    }
304
305    *cp = cur_cp;
306
307    return 0;
308
309fail_no_cp:
310    SLOGE("Valid Checkpoint not found!!");
311    return -EINVAL;
312}
313
314static int gather_sit_info(int fd, struct f2fs_info *info)
315{
316    u64 num_segments = (info->total_blocks - info->main_blkaddr
317            + info->blocks_per_segment - 1) / info->blocks_per_segment;
318    u64 num_sit_blocks = (num_segments + SIT_ENTRY_PER_BLOCK - 1) / SIT_ENTRY_PER_BLOCK;
319    u64 sit_block;
320
321    info->sit_blocks = malloc(num_sit_blocks * sizeof(struct f2fs_sit_block));
322    if (!info->sit_blocks)
323        return -1;
324
325    for(sit_block = 0; sit_block<num_sit_blocks; sit_block++) {
326        off64_t address = info->sit_blkaddr + sit_block;
327
328        if (f2fs_test_bit(sit_block, info->sit_bmp))
329            address += info->blocks_per_sit;
330
331        SLOGD("Reading cache block starting at block %"PRIu64, address);
332        if (read_structure(fd, address * F2FS_BLKSIZE, &info->sit_blocks[sit_block], sizeof(struct f2fs_sit_block))) {
333            SLOGE("Could not read sit block at block %"PRIu64, address);
334            free(info->sit_blocks);
335            return -1;
336        }
337    }
338    return 0;
339}
340
341static inline int is_set_ckpt_flags(struct f2fs_checkpoint *cp, unsigned int f)
342{
343    unsigned int ckpt_flags = le32_to_cpu(cp->ckpt_flags);
344    return !!(ckpt_flags & f);
345}
346
347static inline u64 sum_blk_addr(struct f2fs_checkpoint *cp, struct f2fs_info *info, int base, int type)
348{
349    return info->cp_valid_cp_blkaddr + le32_to_cpu(cp->cp_pack_total_block_count)
350                - (base + 1) + type;
351}
352
353static int get_sit_summary(int fd, struct f2fs_info *info, struct f2fs_checkpoint *cp)
354{
355    char buffer[F2FS_BLKSIZE];
356
357    info->sit_sums = calloc(1, sizeof(struct f2fs_summary_block));
358    if (!info->sit_sums)
359        return -1;
360
361    /* CURSEG_COLD_DATA where the journaled SIT entries are. */
362    if (is_set_ckpt_flags(cp, CP_COMPACT_SUM_FLAG)) {
363        if (read_structure_blk(fd, info->cp_valid_cp_blkaddr + le32_to_cpu(cp->cp_pack_start_sum), buffer, 1))
364            return -1;
365        memcpy(&info->sit_sums->n_sits, &buffer[SUM_JOURNAL_SIZE], SUM_JOURNAL_SIZE);
366    } else {
367        u64 blk_addr;
368        if (is_set_ckpt_flags(cp, CP_UMOUNT_FLAG))
369            blk_addr = sum_blk_addr(cp, info, NR_CURSEG_TYPE, CURSEG_COLD_DATA);
370        else
371            blk_addr = sum_blk_addr(cp, info, NR_CURSEG_DATA_TYPE, CURSEG_COLD_DATA);
372
373        if (read_structure_blk(fd, blk_addr, buffer, 1))
374            return -1;
375
376        memcpy(info->sit_sums, buffer, sizeof(struct f2fs_summary_block));
377    }
378    return 0;
379}
380
381struct f2fs_info *generate_f2fs_info(int fd)
382{
383    struct f2fs_super_block *sb = NULL;
384    struct f2fs_checkpoint *cp = NULL;
385    struct f2fs_info *info;
386
387    info = calloc(1, sizeof(*info));
388    if (!info) {
389        SLOGE("Out of memory!");
390        return NULL;
391    }
392
393    sb = malloc(sizeof(*sb));
394    if(!sb) {
395        SLOGE("Out of memory!");
396        free(info);
397        return NULL;
398    }
399    if (read_f2fs_sb(fd, sb)) {
400        SLOGE("Failed to read superblock");
401        free(info);
402        free(sb);
403        return NULL;
404    }
405    dbg_print_raw_sb_info(sb);
406
407    info->cp_blkaddr = le32_to_cpu(sb->cp_blkaddr);
408    info->sit_blkaddr = le32_to_cpu(sb->sit_blkaddr);
409    info->nat_blkaddr = le32_to_cpu(sb->nat_blkaddr);
410    info->ssa_blkaddr = le32_to_cpu(sb->ssa_blkaddr);
411    info->main_blkaddr = le32_to_cpu(sb->main_blkaddr);
412    info->block_size = F2FS_BLKSIZE;
413    info->total_blocks = sb->block_count;
414    info->blocks_per_sit = (le32_to_cpu(sb->segment_count_sit) >> 1) << le32_to_cpu(sb->log_blocks_per_seg);
415    info->blocks_per_segment = 1U << le32_to_cpu(sb->log_blocks_per_seg);
416
417    if (get_valid_checkpoint_info(fd, sb, &cp, info))
418        goto error;
419    dbg_print_raw_ckpt_struct(cp);
420
421    info->total_user_used = le32_to_cpu(cp->valid_block_count);
422
423    u32 bmp_size = le32_to_cpu(cp->sit_ver_bitmap_bytesize);
424
425    /* get sit validity bitmap */
426    info->sit_bmp = malloc(bmp_size);
427    if(!info->sit_bmp) {
428        SLOGE("Out of memory!");
429        goto error;
430    }
431
432    info->sit_bmp_size = bmp_size;
433    if (read_structure(fd, info->cp_valid_cp_blkaddr * F2FS_BLKSIZE
434                   + offsetof(struct f2fs_checkpoint, sit_nat_version_bitmap),
435                   info->sit_bmp, bmp_size)) {
436        SLOGE("Error getting SIT validity bitmap");
437        goto error;
438    }
439
440    if (gather_sit_info(fd , info)) {
441        SLOGE("Error getting SIT information");
442        goto error;
443    }
444    if (get_sit_summary(fd, info, cp)) {
445        SLOGE("Error getting SIT entries in summary area");
446        goto error;
447    }
448    dbg_print_info_struct(info);
449    return info;
450error:
451    free(sb);
452    free(cp);
453    free_f2fs_info(info);
454    return NULL;
455}
456
457void free_f2fs_info(struct f2fs_info *info)
458{
459    if (info) {
460        free(info->sit_blocks);
461        info->sit_blocks = NULL;
462
463        free(info->sit_bmp);
464        info->sit_bmp = NULL;
465
466        free(info->sit_sums);
467        info->sit_sums = NULL;
468    }
469    free(info);
470}
471
472u64 get_num_blocks_used(struct f2fs_info *info)
473{
474    return info->main_blkaddr + info->total_user_used;
475}
476
477int f2fs_test_bit(unsigned int nr, const char *p)
478{
479    int mask;
480    char *addr = (char *)p;
481
482    addr += (nr >> 3);
483    mask = 1 << (7 - (nr & 0x07));
484    return (mask & *addr) != 0;
485}
486
487int run_on_used_blocks(u64 startblock, struct f2fs_info *info, int (*func)(u64 pos, void *data), void *data) {
488    struct f2fs_sit_block sit_block_cache;
489    struct f2fs_sit_entry * sit_entry;
490    u64 sit_block_num_cur = 0, segnum = 0, block_offset;
491    u64 block;
492    unsigned int used, found, started = 0, i;
493
494    block = startblock;
495    while (block < info->total_blocks) {
496        /* TODO: Save only relevant portions of metadata */
497        if (block < info->main_blkaddr) {
498            if (func(block, data)) {
499                SLOGI("func error");
500                return -1;
501            }
502        } else {
503            /* Main Section */
504            segnum = (block - info->main_blkaddr)/info->blocks_per_segment;
505
506            /* check the SIT entries in the journal */
507            found = 0;
508            for(i = 0; i < le16_to_cpu(info->sit_sums->n_sits); i++) {
509                if (le32_to_cpu(segno_in_journal(info->sit_sums, i)) == segnum) {
510                    sit_entry = &sit_in_journal(info->sit_sums, i);
511                    found = 1;
512                    break;
513                }
514            }
515
516            /* get SIT entry from SIT section */
517            if (!found) {
518                sit_block_num_cur = segnum / SIT_ENTRY_PER_BLOCK;
519                sit_entry = &info->sit_blocks[sit_block_num_cur].entries[segnum % SIT_ENTRY_PER_BLOCK];
520            }
521
522            block_offset = (block - info->main_blkaddr) % info->blocks_per_segment;
523
524            if (block_offset == 0 && GET_SIT_VBLOCKS(sit_entry) == 0) {
525                block += info->blocks_per_segment;
526                continue;
527            }
528
529            used = f2fs_test_bit(block_offset, (char *)sit_entry->valid_map);
530            if(used)
531                if (func(block, data))
532                    return -1;
533        }
534
535        block++;
536    }
537    return 0;
538}
539
540struct privdata
541{
542    int count;
543    int infd;
544    int outfd;
545    char* buf;
546    char *zbuf;
547    int done;
548    struct f2fs_info *info;
549};
550
551
552/*
553 * This is a simple test program. It performs a block to block copy of a
554 * filesystem, replacing blocks identified as unused with 0's.
555 */
556
557int copy_used(u64 pos, void *data)
558{
559    struct privdata *d = data;
560    char *buf;
561    int pdone = (pos * 100) / d->info->total_blocks;
562    if (pdone > d->done) {
563        d->done = pdone;
564        printf("Done with %d percent\n", d->done);
565    }
566
567    d->count++;
568    buf = d->buf;
569    if(read_structure_blk(d->infd, (unsigned long long)pos, d->buf, 1)) {
570        printf("Error reading!!!\n");
571        return -1;
572    }
573
574    off64_t ret;
575    ret = lseek64(d->outfd, pos * F2FS_BLKSIZE, SEEK_SET);
576    if (ret < 0) {
577        SLOGE("failed to seek\n");
578        return ret;
579    }
580
581    ret = write(d->outfd, d->buf, F2FS_BLKSIZE);
582    if (ret < 0) {
583        SLOGE("failed to write\n");
584        return ret;
585    }
586    if (ret != F2FS_BLKSIZE) {
587        SLOGE("failed to read all\n");
588        return -1;
589    }
590    return 0;
591}
592
593int main(int argc, char **argv)
594{
595    if (argc != 3)
596        printf("Usage: %s fs_file_in fs_file_out\n", argv[0]);
597    char *in = argv[1];
598    char *out = argv[2];
599    int infd, outfd;
600
601    if ((infd = open(in, O_RDONLY)) < 0) {
602        SLOGE("Cannot open device");
603        return 0;
604    }
605    if ((outfd = open(out, O_WRONLY|O_CREAT, S_IRUSR | S_IWUSR)) < 0) {
606        SLOGE("Cannot open output");
607        return 0;
608    }
609
610    struct privdata d;
611    d.infd = infd;
612    d.outfd = outfd;
613    d.count = 0;
614    struct f2fs_info *info = generate_f2fs_info(infd);
615    if (!info) {
616        printf("Failed to generate info!");
617        return -1;
618    }
619    char *buf = malloc(F2FS_BLKSIZE);
620    char *zbuf = calloc(1, F2FS_BLKSIZE);
621    d.buf = buf;
622    d.zbuf = zbuf;
623    d.done = 0;
624    d.info = info;
625    int expected_count = get_num_blocks_used(info);
626    run_on_used_blocks(0, info, &copy_used, &d);
627    printf("Copied %d blocks. Expected to copy %d\n", d.count, expected_count);
628    ftruncate64(outfd, info->total_blocks * F2FS_BLKSIZE);
629    free_f2fs_info(info);
630    free(buf);
631    free(zbuf);
632    close(infd);
633    close(outfd);
634    return 0;
635}
636