15db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 25db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * fs/logfs/gc.c - garbage collection code 35db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 45db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * As should be obvious for Linux kernel code, license is GPLv2 55db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 65db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Copyright (c) 2005-2008 Joern Engel <joern@logfs.org> 75db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 85db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include "logfs.h" 95db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#include <linux/sched.h> 105a0e3ad6af8660be21ca98a971cd00f331318c05Tejun Heo#include <linux/slab.h> 115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Wear leveling needs to kick in when the difference between low erase 145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * counts and high erase counts gets too big. A good value for "too big" 155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * may be somewhat below 10% of maximum erase count for the device. 165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Why not 397, to pick a nice round number with no specific meaning? :) 175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * WL_RATELIMIT is the minimum time between two wear level events. A huge 195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * number of segments may fulfil the requirements for wear leveling at the 205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * same time. If that happens we don't want to cause a latency from hell, 215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * but just gently pick one segment every so often and minimize overhead. 225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define WL_DELTA 397 245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define WL_RATELIMIT 100 255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define MAX_OBJ_ALIASES 2600 265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define SCAN_RATIO 512 /* number of scanned segments per gc'd segment */ 275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define LIST_SIZE 64 /* base size of candidate lists */ 285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define SCAN_ROUNDS 128 /* maximum number of complete medium scans */ 295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel#define SCAN_ROUNDS_HIGH 4 /* maximum number of higher-level scans */ 305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int no_free_segments(struct super_block *sb) 325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return super->s_free_list.count; 365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* journal has distance -1, top-most ifile layer distance 0 */ 395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic u8 root_distance(struct super_block *sb, gc_level_t __gc_level) 405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u8 gc_level = (__force u8)__gc_level; 435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel switch (gc_level) { 455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 0: /* fall through */ 465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 1: /* fall through */ 475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 2: /* fall through */ 485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 3: 495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* file data or indirect blocks */ 505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return super->s_ifile_levels + super->s_iblock_levels - gc_level; 515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 6: /* fall through */ 525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 7: /* fall through */ 535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 8: /* fall through */ 545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel case 9: 555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* inode file data or indirect blocks */ 565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return super->s_ifile_levels - (gc_level - 6); 575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel default: 585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel printk(KERN_ERR"LOGFS: segment of unknown level %x found\n", 595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel gc_level); 605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel WARN_ON(1); 615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return super->s_ifile_levels + super->s_iblock_levels; 625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int segment_is_reserved(struct super_block *sb, u32 segno) 665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_area *area; 695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel void *reserved; 705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i; 715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Some segments are reserved. Just pretend they were all valid */ 735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel reserved = btree_lookup32(&super->s_reserved_segments, segno); 745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (reserved) 755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 1; 765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Currently open segments */ 785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for_each_area(i) { 795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel area = super->s_area[i]; 805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (area->a_is_open && area->a_segno == segno) 815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 1; 825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void logfs_mark_segment_bad(struct super_block *sb, u32 segno) 885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG(); 905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Returns the bytes consumed by valid objects in this segment. Object headers 945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * are counted, the segment header is not. 955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic u32 logfs_valid_bytes(struct super_block *sb, u32 segno, u32 *ec, 975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel gc_level_t *gc_level) 985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_segment_entry se; 1005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 ec_level; 1015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_get_segment_entry(sb, segno, &se); 1035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (se.ec_level == cpu_to_be32(BADSEG) || 1045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel se.valid == cpu_to_be32(RESERVED)) 1055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return RESERVED; 1065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel ec_level = be32_to_cpu(se.ec_level); 1085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel *ec = ec_level >> 4; 1095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel *gc_level = GC_LEVEL(ec_level & 0xf); 1105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return be32_to_cpu(se.valid); 1115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 1125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void logfs_cleanse_block(struct super_block *sb, u64 ofs, u64 ino, 1145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u64 bix, gc_level_t gc_level) 1155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 1165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct inode *inode; 1175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int err, cookie; 1185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel inode = logfs_safe_iget(sb, ino, &cookie); 1205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel err = logfs_rewrite_block(inode, bix, ofs, gc_level, 0); 1215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG_ON(err); 1225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_safe_iput(inode, cookie); 1235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 1245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1256f485b41875dbf5160c1990322469c1f65f77b28Joern Engelstatic u32 logfs_gc_segment(struct super_block *sb, u32 segno) 1265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 1275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 1285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_segment_header sh; 1295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_object_header oh; 1305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u64 ofs, ino, bix; 1315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 seg_ofs, logical_segno, cleaned = 0; 1325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int err, len, valid; 1335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel gc_level_t gc_level; 1345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel LOGFS_BUG_ON(segment_is_reserved(sb, segno), sb); 1365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel btree_insert32(&super->s_reserved_segments, segno, (void *)1, GFP_NOFS); 1385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel err = wbuf_read(sb, dev_ofs(sb, segno, 0), sizeof(sh), &sh); 1395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG_ON(err); 1405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel gc_level = GC_LEVEL(sh.level); 1415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logical_segno = be32_to_cpu(sh.segno); 1425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (sh.crc != logfs_crc32(&sh, sizeof(sh), 4)) { 1435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_mark_segment_bad(sb, segno); 1445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cleaned = -1; 1455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel goto out; 1465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 1475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (seg_ofs = LOGFS_SEGMENT_HEADERSIZE; 1495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel seg_ofs + sizeof(oh) < super->s_segsize; ) { 1505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel ofs = dev_ofs(sb, logical_segno, seg_ofs); 1515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel err = wbuf_read(sb, dev_ofs(sb, segno, seg_ofs), sizeof(oh), 1525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel &oh); 1535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG_ON(err); 1545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!memchr_inv(&oh, 0xff, sizeof(oh))) 1565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel break; 1575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (oh.crc != logfs_crc32(&oh, sizeof(oh) - 4, 4)) { 1595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_mark_segment_bad(sb, segno); 1605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cleaned = super->s_segsize - 1; 1615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel goto out; 1625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 1635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel ino = be64_to_cpu(oh.ino); 1655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel bix = be64_to_cpu(oh.bix); 1665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel len = sizeof(oh) + be16_to_cpu(oh.len); 1675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel valid = logfs_is_valid_block(sb, ofs, ino, bix, gc_level); 1685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (valid == 1) { 1695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_cleanse_block(sb, ofs, ino, bix, gc_level); 1705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cleaned += len; 1715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } else if (valid == 2) { 1725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Will be invalid upon journal commit */ 1735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cleaned += len; 1745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 1755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel seg_ofs += len; 1765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 1775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelout: 1785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel btree_remove32(&super->s_reserved_segments, segno); 1795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return cleaned; 1805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 1815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic struct gc_candidate *add_list(struct gc_candidate *cand, 1835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct candidate_list *list) 1845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 1855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct rb_node **p = &list->rb_tree.rb_node; 1865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct rb_node *parent = NULL; 1875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cur; 1885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int comp; 1895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->list = list; 1915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel while (*p) { 1925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel parent = *p; 1935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cur = rb_entry(parent, struct gc_candidate, rb_node); 1945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 1955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (list->sort_by_ec) 1965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel comp = cand->erase_count < cur->erase_count; 1975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel else 1985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel comp = cand->valid < cur->valid; 1995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (comp) 2015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel p = &parent->rb_left; 2025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel else 2035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel p = &parent->rb_right; 2045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 2055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel rb_link_node(&cand->rb_node, parent, p); 2065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel rb_insert_color(&cand->rb_node, &list->rb_tree); 2075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (list->count <= list->maxcount) { 2095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel list->count++; 2105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return NULL; 2115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 2125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = rb_entry(rb_last(&list->rb_tree), struct gc_candidate, rb_node); 2135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel rb_erase(&cand->rb_node, &list->rb_tree); 2145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->list = NULL; 2155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return cand; 2165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 2175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void remove_from_list(struct gc_candidate *cand) 2195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 2205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct candidate_list *list = cand->list; 2215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel rb_erase(&cand->rb_node, &list->rb_tree); 2235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel list->count--; 2245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 2255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void free_candidate(struct super_block *sb, struct gc_candidate *cand) 2275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 2285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 2295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel btree_remove32(&super->s_cand_tree, cand->segno); 2315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel kfree(cand); 2325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 2335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelu32 get_best_cand(struct super_block *sb, struct candidate_list *list, u32 *ec) 2355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 2365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand; 2375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 segno; 2385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG_ON(list->count == 0); 2405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = rb_entry(rb_first(&list->rb_tree), struct gc_candidate, rb_node); 2425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel remove_from_list(cand); 2435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel segno = cand->segno; 2445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (ec) 2455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel *ec = cand->erase_count; 2465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel free_candidate(sb, cand); 2475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return segno; 2485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 2495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 2515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * We have several lists to manage segments with. The reserve_list is used to 2525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * deal with bad blocks. We try to keep the best (lowest ec) segments on this 2535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * list. 2545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * The free_list contains free segments for normal usage. It usually gets the 2555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * second pick after the reserve_list. But when the free_list is running short 2565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * it is more important to keep the free_list full than to keep a reserve. 2575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 2585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Segments that are not free are put onto a per-level low_list. If we have 2595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * to run garbage collection, we pick a candidate from there. All segments on 2605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * those lists should have at least some free space so GC will make progress. 2615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 2625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * And last we have the ec_list, which is used to pick segments for wear 2635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * leveling. 2645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 2655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * If all appropriate lists are full, we simply free the candidate and forget 2665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * about that segment for a while. We have better candidates for each purpose. 2675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 2685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void __add_candidate(struct super_block *sb, struct gc_candidate *cand) 2695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 2705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 2715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 full = super->s_segsize - LOGFS_SEGMENT_RESERVE; 2725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand->valid == 0) { 2745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* 100% free segments */ 2755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc_noisy("add reserve segment %x (ec %x) at %llx\n", 2765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->segno, cand->erase_count, 2775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel dev_ofs(sb, cand->segno, 0)); 2785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = add_list(cand, &super->s_reserve_list); 2795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand) { 2805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc_noisy("add free segment %x (ec %x) at %llx\n", 2815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->segno, cand->erase_count, 2825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel dev_ofs(sb, cand->segno, 0)); 2835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = add_list(cand, &super->s_free_list); 2845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 2855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } else { 2865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* good candidates for Garbage Collection */ 2875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand->valid < full) 2885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = add_list(cand, &super->s_low_list[cand->dist]); 2895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* good candidates for wear leveling, 2905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * segments that were recently written get ignored */ 2915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand) 2925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = add_list(cand, &super->s_ec_list); 2935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 2945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand) 2955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel free_candidate(sb, cand); 2965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 2975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 2985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int add_candidate(struct super_block *sb, u32 segno, u32 valid, u32 ec, 2995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u8 dist) 3005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 3015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 3025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand; 3035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = kmalloc(sizeof(*cand), GFP_NOFS); 3055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!cand) 3065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return -ENOMEM; 3075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->segno = segno; 3095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->valid = valid; 3105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->erase_count = ec; 3115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand->dist = dist; 3125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel btree_insert32(&super->s_cand_tree, segno, cand, GFP_NOFS); 3145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel __add_candidate(sb, cand); 3155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 3165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 3175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void remove_segment_from_lists(struct super_block *sb, u32 segno) 3195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 3205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 3215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand; 3225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = btree_lookup32(&super->s_cand_tree, segno); 3245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand) { 3255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel remove_from_list(cand); 3265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel free_candidate(sb, cand); 3275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 3285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 3295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void scan_segment(struct super_block *sb, u32 segno) 3315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 3325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 valid, ec = 0; 3335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel gc_level_t gc_level = 0; 3345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u8 dist; 3355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (segment_is_reserved(sb, segno)) 3375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 3385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel remove_segment_from_lists(sb, segno); 3405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel valid = logfs_valid_bytes(sb, segno, &ec, &gc_level); 3415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (valid == RESERVED) 3425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 3435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel dist = root_distance(sb, gc_level); 3455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel add_candidate(sb, segno, valid, ec, dist); 3465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 3475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic struct gc_candidate *first_in_list(struct candidate_list *list) 3495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 3505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (list->count == 0) 3515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return NULL; 3525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return rb_entry(rb_first(&list->rb_tree), struct gc_candidate, rb_node); 3535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 3545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 3565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Find the best segment for garbage collection. Main criterion is 3575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * the segment requiring the least effort to clean. Secondary 3585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * criterion is to GC on the lowest level available. 3595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 3605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * So we search the least effort segment on the lowest level first, 3615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * then move up and pick another segment iff is requires significantly 3625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * less effort. Hence the LOGFS_MAX_OBJECTSIZE in the comparison. 3635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 3645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic struct gc_candidate *get_candidate(struct super_block *sb) 3655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 3665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 3675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i, max_dist; 3685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand = NULL, *this; 3695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 370934eed395d201bf0901ca0c0cc3703b18729d0ceJoern Engel max_dist = min(no_free_segments(sb), LOGFS_NO_AREAS - 1); 3715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (i = max_dist; i >= 0; i--) { 3735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel this = first_in_list(&super->s_low_list[i]); 3745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!this) 3755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel continue; 3765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!cand) 3775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = this; 3785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (this->valid + LOGFS_MAX_OBJECTSIZE <= cand->valid) 3795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = this; 3805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 3815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return cand; 3825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 3835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int __logfs_gc_once(struct super_block *sb, struct gc_candidate *cand) 3855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 3865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 3875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel gc_level_t gc_level; 3885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 cleaned, valid, segno, ec; 3895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u8 dist; 3905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!cand) { 3925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc("GC attempted, but no candidate found\n"); 3935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 3945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 3955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 3965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel segno = cand->segno; 3975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel dist = cand->dist; 3985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel valid = logfs_valid_bytes(sb, segno, &ec, &gc_level); 3995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel free_candidate(sb, cand); 4005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc("GC segment #%02x at %llx, %x required, %x free, %x valid, %llx free\n", 4015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel segno, (u64)segno << super->s_segshift, 4025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel dist, no_free_segments(sb), valid, 4035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel super->s_free_bytes); 4046f485b41875dbf5160c1990322469c1f65f77b28Joern Engel cleaned = logfs_gc_segment(sb, segno); 4055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc("GC segment #%02x complete - now %x valid\n", segno, 4065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel valid - cleaned); 4075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG_ON(cleaned != valid); 4085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 1; 4095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 4105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int logfs_gc_once(struct super_block *sb) 4125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 4135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand; 4145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = get_candidate(sb); 4165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (cand) 4175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel remove_from_list(cand); 4185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return __logfs_gc_once(sb, cand); 4195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 4205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* returns 1 if a wrap occurs, 0 otherwise */ 4225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int logfs_scan_some(struct super_block *sb) 4235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 4245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 4255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 segno; 4265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i, ret = 0; 4275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel segno = super->s_sweeper; 4295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (i = SCAN_RATIO; i > 0; i--) { 4305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel segno++; 4315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (segno >= super->s_no_segs) { 4325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel segno = 0; 4335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel ret = 1; 4345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Break out of the loop. We want to read a single 4355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * block from the segment size on next invocation if 4365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * SCAN_RATIO is set to match block size 4375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 4385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel break; 4395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 4405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel scan_segment(sb, segno); 4425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 4435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel super->s_sweeper = segno; 4445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return ret; 4455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 4465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 4485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * In principle, this function should loop forever, looking for GC candidates 4495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * and moving data. LogFS is designed in such a way that this loop is 4505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * guaranteed to terminate. 4515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 4525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Limiting the loop to some iterations serves purely to catch cases when 4535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * these guarantees have failed. An actual endless loop is an obvious bug 4545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * and should be reported as such. 4555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 4565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void __logfs_gc_pass(struct super_block *sb, int target) 4575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 4585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 4595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_block *block; 4605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int round, progress, last_progress = 0; 4615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 462032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel /* 463032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel * Doing too many changes to the segfile at once would result 464032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel * in a large number of aliases. Write the journal before 465032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel * things get out of hand. 466032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel */ 467032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel if (super->s_shadow_tree.no_shadowed_segments >= MAX_OBJ_ALIASES) 468032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel logfs_write_anchor(sb); 469032d8f7268444a0f5d4ee02d9513d682d5b8edfcJoern Engel 4705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (no_free_segments(sb) >= target && 4715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel super->s_no_object_aliases < MAX_OBJ_ALIASES) 4725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 4735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc("__logfs_gc_pass(%x)\n", target); 4755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (round = 0; round < SCAN_ROUNDS; ) { 4765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (no_free_segments(sb) >= target) 4775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel goto write_alias; 4785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Sync in-memory state with on-medium state in case they 4805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * diverged */ 481c6d3830140f1d56b07d8ab56a6e14ca3c492a39aJoern Engel logfs_write_anchor(sb); 4825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel round += logfs_scan_some(sb); 4835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (no_free_segments(sb) >= target) 4845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel goto write_alias; 4855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel progress = logfs_gc_once(sb); 4865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (progress) 4875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel last_progress = round; 4885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel else if (round - last_progress > 2) 4895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel break; 4905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel continue; 4915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 4925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* 4935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * The goto logic is nasty, I just don't know a better way to 4945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * code it. GC is supposed to ensure two things: 4955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 1. Enough free segments are available. 4965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 2. The number of aliases is bounded. 4975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * When 1. is achieved, we take a look at 2. and write back 4985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * some alias-containing blocks, if necessary. However, after 4995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * each such write we need to go back to 1., as writes can 5005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * consume free segments. 5015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 5025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelwrite_alias: 5035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (super->s_no_object_aliases < MAX_OBJ_ALIASES) 5045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (list_empty(&super->s_object_alias)) { 5065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* All aliases are still in btree */ 5075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 5095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel log_gc("Write back one alias\n"); 5105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel block = list_entry(super->s_object_alias.next, 5115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_block, alias_list); 5125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel block->ops->write_block(block); 5135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* 5145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * To round off the nasty goto logic, we reset round here. It 5155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * is a safety-net for GC not making any progress and limited 5165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * to something reasonably small. If incremented it for every 5175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * single alias, the loop could terminate rather quickly. 5185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 5195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel round = 0; 5205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 5215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel LOGFS_BUG(sb); 5225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 5235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int wl_ratelimit(struct super_block *sb, u64 *next_event) 5255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 5265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 5275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (*next_event < super->s_gec) { 5295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel *next_event = super->s_gec + WL_RATELIMIT; 5305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 5315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 5325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 1; 5335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 5345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5355db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void logfs_wl_pass(struct super_block *sb) 5365db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 5375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 5385db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *wl_cand, *free_cand; 5395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (wl_ratelimit(sb, &super->s_wl_gec_ostore)) 5415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5435db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel wl_cand = first_in_list(&super->s_ec_list); 5445db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!wl_cand) 5455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5465db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel free_cand = first_in_list(&super->s_free_list); 5475db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!free_cand) 5485db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5495db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5505db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (wl_cand->erase_count < free_cand->erase_count + WL_DELTA) { 5515db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel remove_from_list(wl_cand); 5525db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel __logfs_gc_once(sb, wl_cand); 5535db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 5545db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 5555db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5565db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel/* 5575db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * The journal needs wear leveling as well. But moving the journal is an 5585db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * expensive operation so we try to avoid it as much as possible. And if we 5595db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * have to do it, we move the whole journal, not individual segments. 5605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 5615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Ratelimiting is not strictly necessary here, it mainly serves to avoid the 5625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * calculations. First we check whether moving the journal would be a 5635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * significant improvement. That means that a) the current journal segments 5645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * have more wear than the future journal segments and b) the current journal 5655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * segments have more wear than normal ostore segments. 5665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Rationale for b) is that we don't have to move the journal if it is aging 5675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * less than the ostore, even if the reserve segments age even less (they are 5685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * excluded from wear leveling, after all). 5695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Next we check that the superblocks have less wear than the journal. Since 5705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * moving the journal requires writing the superblocks, we have to protect the 5715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * superblocks even more than the journal. 5725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * 5735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * Also we double the acceptable wear difference, compared to ostore wear 5745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * leveling. Journal data is read and rewritten rapidly, comparatively. So 5755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * soft errors have much less time to accumulate and we allow the journal to 5765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * be a bit worse than the ostore. 5775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 5785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void logfs_journal_wl_pass(struct super_block *sb) 5795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 5805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 5815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand; 5825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 min_journal_ec = -1, max_reserve_ec = 0; 5835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i; 5845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (wl_ratelimit(sb, &super->s_wl_gec_journal)) 5865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (super->s_reserve_list.count < super->s_no_journal_segs) { 5895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Reserve is not full enough to move complete journal */ 5905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 5915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 5925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 5935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel journal_for_each(i) 5945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (super->s_journal_seg[i]) 5955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel min_journal_ec = min(min_journal_ec, 5965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel super->s_journal_ec[i]); 5975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = rb_entry(rb_first(&super->s_free_list.rb_tree), 5985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate, rb_node); 5995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel max_reserve_ec = cand->erase_count; 6005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for (i = 0; i < 2; i++) { 6015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_segment_entry se; 6025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 segno = seg_no(sb, super->s_sb_ofs[i]); 6035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 ec; 6045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_get_segment_entry(sb, segno, &se); 6065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel ec = be32_to_cpu(se.ec_level) >> 4; 6075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel max_reserve_ec = max(max_reserve_ec, ec); 6085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 6095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (min_journal_ec > max_reserve_ec + 2 * WL_DELTA) { 6115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel do_logfs_journal_wl_pass(sb); 6125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 6135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 6145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid logfs_gc_pass(struct super_block *sb) 6165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 6175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 6185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel //BUG_ON(mutex_trylock(&logfs_super(sb)->s_w_mutex)); 6205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* Write journal before free space is getting saturated with dirty 6215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * objects. 6225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 6235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (super->s_dirty_used_bytes + super->s_dirty_free_bytes 6245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel + LOGFS_MAX_OBJECTSIZE >= super->s_free_bytes) 625c6d3830140f1d56b07d8ab56a6e14ca3c492a39aJoern Engel logfs_write_anchor(sb); 626c6d3830140f1d56b07d8ab56a6e14ca3c492a39aJoern Engel __logfs_gc_pass(sb, super->s_total_levels); 6275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_wl_pass(sb); 6285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_journal_wl_pass(sb); 6295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 6305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic int check_area(struct super_block *sb, int i) 6325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 6335db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 6345db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_area *area = super->s_area[i]; 6356f485b41875dbf5160c1990322469c1f65f77b28Joern Engel gc_level_t gc_level; 6366f485b41875dbf5160c1990322469c1f65f77b28Joern Engel u32 cleaned, valid, ec; 6375db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel u32 segno = area->a_segno; 6386f485b41875dbf5160c1990322469c1f65f77b28Joern Engel u64 ofs = dev_ofs(sb, area->a_segno, area->a_written_bytes); 6395db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6405db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!area->a_is_open) 6415db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 6425db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6436f485b41875dbf5160c1990322469c1f65f77b28Joern Engel if (super->s_devops->can_write_buf(sb, ofs) == 0) 6446f485b41875dbf5160c1990322469c1f65f77b28Joern Engel return 0; 6455db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6466f485b41875dbf5160c1990322469c1f65f77b28Joern Engel printk(KERN_INFO"LogFS: Possibly incomplete write at %llx\n", ofs); 6476f485b41875dbf5160c1990322469c1f65f77b28Joern Engel /* 6486f485b41875dbf5160c1990322469c1f65f77b28Joern Engel * The device cannot write back the write buffer. Most likely the 6496f485b41875dbf5160c1990322469c1f65f77b28Joern Engel * wbuf was already written out and the system crashed at some point 6506f485b41875dbf5160c1990322469c1f65f77b28Joern Engel * before the journal commit happened. In that case we wouldn't have 6516f485b41875dbf5160c1990322469c1f65f77b28Joern Engel * to do anything. But if the crash happened before the wbuf was 6526f485b41875dbf5160c1990322469c1f65f77b28Joern Engel * written out correctly, we must GC this segment. So assume the 6536f485b41875dbf5160c1990322469c1f65f77b28Joern Engel * worst and always do the GC run. 6546f485b41875dbf5160c1990322469c1f65f77b28Joern Engel */ 6556f485b41875dbf5160c1990322469c1f65f77b28Joern Engel area->a_is_open = 0; 6566f485b41875dbf5160c1990322469c1f65f77b28Joern Engel valid = logfs_valid_bytes(sb, segno, &ec, &gc_level); 6576f485b41875dbf5160c1990322469c1f65f77b28Joern Engel cleaned = logfs_gc_segment(sb, segno); 6586f485b41875dbf5160c1990322469c1f65f77b28Joern Engel if (cleaned != valid) 6596f485b41875dbf5160c1990322469c1f65f77b28Joern Engel return -EIO; 6605db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 6615db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 6625db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6635db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelint logfs_check_areas(struct super_block *sb) 6645db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 6655db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i, err; 6665db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6675db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for_each_area(i) { 6685db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel err = check_area(sb, i); 6695db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (err) 6705db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return err; 6715db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 6725db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 6735db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 6745db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6755db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void logfs_init_candlist(struct candidate_list *list, int maxcount, 6765db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int sort_by_ec) 6775db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 6785db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel list->count = 0; 6795db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel list->maxcount = maxcount; 6805db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel list->sort_by_ec = sort_by_ec; 6815db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel list->rb_tree = RB_ROOT; 6825db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 6835db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6845db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelint logfs_init_gc(struct super_block *sb) 6855db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 6865db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 6875db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i; 6885db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6895db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel btree_init_mempool32(&super->s_cand_tree, super->s_btree_pool); 6905db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_init_candlist(&super->s_free_list, LIST_SIZE + SCAN_RATIO, 1); 6915db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_init_candlist(&super->s_reserve_list, 6925db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel super->s_bad_seg_reserve, 1); 6935db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for_each_area(i) 6945db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_init_candlist(&super->s_low_list[i], LIST_SIZE, 0); 6955db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_init_candlist(&super->s_ec_list, LIST_SIZE, 1); 6965db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return 0; 6975db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 6985db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 6995db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelstatic void logfs_cleanup_list(struct super_block *sb, 7005db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct candidate_list *list) 7015db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 7025db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct gc_candidate *cand; 7035db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 7045db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel while (list->count) { 7055db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel cand = rb_entry(list->rb_tree.rb_node, struct gc_candidate, 7065db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel rb_node); 7075db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel remove_from_list(cand); 7085db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel free_candidate(sb, cand); 7095db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel } 7105db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel BUG_ON(list->rb_tree.rb_node); 7115db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 7125db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 7135db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engelvoid logfs_cleanup_gc(struct super_block *sb) 7145db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel{ 7155db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel struct logfs_super *super = logfs_super(sb); 7165db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel int i; 7175db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 7185db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel if (!super->s_free_list.count) 7195db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel return; 7205db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel 7215db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel /* 7225db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * FIXME: The btree may still contain a single empty node. So we 7235db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * call the grim visitor to clean up that mess. Btree code should 7245db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel * do it for us, really. 7255db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel */ 7265db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel btree_grim_visitor32(&super->s_cand_tree, 0, NULL); 7275db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_cleanup_list(sb, &super->s_free_list); 7285db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_cleanup_list(sb, &super->s_reserve_list); 7295db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel for_each_area(i) 7305db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_cleanup_list(sb, &super->s_low_list[i]); 7315db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel logfs_cleanup_list(sb, &super->s_ec_list); 7325db53f3e80dee2d9dff5e534f9e9fe1db17c9936Joern Engel} 733