1eb60ceacSChris Mason #define _XOPEN_SOURCE 500 2eb60ceacSChris Mason #include <stdio.h> 3eb60ceacSChris Mason #include <stdlib.h> 4eb60ceacSChris Mason #include <sys/types.h> 5eb60ceacSChris Mason #include <sys/stat.h> 6eb60ceacSChris Mason #include <fcntl.h> 7eb60ceacSChris Mason #include <unistd.h> 8eb60ceacSChris Mason #include "kerncompat.h" 9eb60ceacSChris Mason #include "radix-tree.h" 10eb60ceacSChris Mason #include "ctree.h" 11eb60ceacSChris Mason #include "disk-io.h" 12eb60ceacSChris Mason 13eb60ceacSChris Mason static int allocated_blocks = 0; 14ed2ff2cbSChris Mason int cache_max = 10000; 15eb60ceacSChris Mason 169a8dd150SChris Mason static int check_tree_block(struct ctree_root *root, struct tree_buffer *buf) 17eb60ceacSChris Mason { 189a8dd150SChris Mason if (buf->blocknr != buf->node.header.blocknr) 199a8dd150SChris Mason BUG(); 209a8dd150SChris Mason if (root->node && buf->node.header.parentid != root->node->node.header.parentid) 219a8dd150SChris Mason BUG(); 229a8dd150SChris Mason return 0; 23eb60ceacSChris Mason } 24eb60ceacSChris Mason 25ed2ff2cbSChris Mason static int free_some_buffers(struct ctree_root *root) 26ed2ff2cbSChris Mason { 27ed2ff2cbSChris Mason struct list_head *node, *next; 28ed2ff2cbSChris Mason struct tree_buffer *b; 29ed2ff2cbSChris Mason if (root->cache_size < cache_max) 30ed2ff2cbSChris Mason return 0; 31ed2ff2cbSChris Mason list_for_each_safe(node, next, &root->cache) { 32ed2ff2cbSChris Mason b = list_entry(node, struct tree_buffer, cache); 33ed2ff2cbSChris Mason if (b->count == 1) { 34ed2ff2cbSChris Mason BUG_ON(!list_empty(&b->dirty)); 35ed2ff2cbSChris Mason list_del_init(&b->cache); 36ed2ff2cbSChris Mason tree_block_release(root, b); 37ed2ff2cbSChris Mason if (root->cache_size < cache_max) 3877ce6846SChris Mason break; 39ed2ff2cbSChris Mason } 40ed2ff2cbSChris Mason } 41ed2ff2cbSChris Mason return 0; 42ed2ff2cbSChris Mason } 43ed2ff2cbSChris Mason 44eb60ceacSChris Mason struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr) 45eb60ceacSChris Mason { 46eb60ceacSChris Mason struct tree_buffer *buf; 47eb60ceacSChris Mason int ret; 48eb60ceacSChris Mason buf = malloc(sizeof(struct tree_buffer)); 49eb60ceacSChris Mason if (!buf) 50eb60ceacSChris Mason return buf; 51eb60ceacSChris Mason allocated_blocks++; 52eb60ceacSChris Mason buf->blocknr = blocknr; 53ed2ff2cbSChris Mason buf->count = 2; 54ed2ff2cbSChris Mason INIT_LIST_HEAD(&buf->dirty); 55ed2ff2cbSChris Mason free_some_buffers(root); 56eb60ceacSChris Mason radix_tree_preload(GFP_KERNEL); 57eb60ceacSChris Mason ret = radix_tree_insert(&root->cache_radix, blocknr, buf); 58eb60ceacSChris Mason radix_tree_preload_end(); 59ed2ff2cbSChris Mason list_add_tail(&buf->cache, &root->cache); 60ed2ff2cbSChris Mason root->cache_size++; 61eb60ceacSChris Mason if (ret) { 62eb60ceacSChris Mason free(buf); 63eb60ceacSChris Mason return NULL; 64eb60ceacSChris Mason } 65eb60ceacSChris Mason return buf; 66eb60ceacSChris Mason } 67eb60ceacSChris Mason 689a8dd150SChris Mason struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr) 69eb60ceacSChris Mason { 70eb60ceacSChris Mason struct tree_buffer *buf; 719a8dd150SChris Mason buf = radix_tree_lookup(&root->cache_radix, blocknr); 729a8dd150SChris Mason if (buf) { 739a8dd150SChris Mason buf->count++; 749a8dd150SChris Mason } else { 759a8dd150SChris Mason buf = alloc_tree_block(root, blocknr); 769a8dd150SChris Mason if (!buf) { 77eb60ceacSChris Mason BUG(); 78eb60ceacSChris Mason return NULL; 79eb60ceacSChris Mason } 809a8dd150SChris Mason } 81eb60ceacSChris Mason return buf; 82eb60ceacSChris Mason } 83eb60ceacSChris Mason 84eb60ceacSChris Mason struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr) 85eb60ceacSChris Mason { 86d97e63b6SChris Mason loff_t offset = blocknr * CTREE_BLOCKSIZE; 87eb60ceacSChris Mason struct tree_buffer *buf; 88eb60ceacSChris Mason int ret; 89eb60ceacSChris Mason 90eb60ceacSChris Mason buf = radix_tree_lookup(&root->cache_radix, blocknr); 91eb60ceacSChris Mason if (buf) { 92eb60ceacSChris Mason buf->count++; 939a8dd150SChris Mason } else { 94eb60ceacSChris Mason buf = alloc_tree_block(root, blocknr); 95eb60ceacSChris Mason if (!buf) 96eb60ceacSChris Mason return NULL; 97eb60ceacSChris Mason ret = pread(root->fp, &buf->node, CTREE_BLOCKSIZE, offset); 98eb60ceacSChris Mason if (ret != CTREE_BLOCKSIZE) { 99eb60ceacSChris Mason free(buf); 100eb60ceacSChris Mason return NULL; 101eb60ceacSChris Mason } 1029a8dd150SChris Mason } 1039a8dd150SChris Mason if (check_tree_block(root, buf)) 104cfaa7295SChris Mason BUG(); 105eb60ceacSChris Mason return buf; 106eb60ceacSChris Mason } 107eb60ceacSChris Mason 108ed2ff2cbSChris Mason int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf) 109ed2ff2cbSChris Mason { 110ed2ff2cbSChris Mason if (!list_empty(&buf->dirty)) 111ed2ff2cbSChris Mason return 0; 112ed2ff2cbSChris Mason list_add_tail(&buf->dirty, &root->trans); 113ed2ff2cbSChris Mason buf->count++; 114ed2ff2cbSChris Mason return 0; 115ed2ff2cbSChris Mason } 116ed2ff2cbSChris Mason 117ed2ff2cbSChris Mason int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf) 118ed2ff2cbSChris Mason { 119ed2ff2cbSChris Mason if (!list_empty(&buf->dirty)) { 120ed2ff2cbSChris Mason list_del_init(&buf->dirty); 121ed2ff2cbSChris Mason tree_block_release(root, buf); 122ed2ff2cbSChris Mason } 123ed2ff2cbSChris Mason return 0; 124ed2ff2cbSChris Mason } 125ed2ff2cbSChris Mason 126eb60ceacSChris Mason int write_tree_block(struct ctree_root *root, struct tree_buffer *buf) 127eb60ceacSChris Mason { 128eb60ceacSChris Mason u64 blocknr = buf->blocknr; 129d97e63b6SChris Mason loff_t offset = blocknr * CTREE_BLOCKSIZE; 130eb60ceacSChris Mason int ret; 131eb60ceacSChris Mason 132eb60ceacSChris Mason if (buf->blocknr != buf->node.header.blocknr) 133eb60ceacSChris Mason BUG(); 134eb60ceacSChris Mason ret = pwrite(root->fp, &buf->node, CTREE_BLOCKSIZE, offset); 135eb60ceacSChris Mason if (ret != CTREE_BLOCKSIZE) 136eb60ceacSChris Mason return ret; 137eb60ceacSChris Mason return 0; 138eb60ceacSChris Mason } 139eb60ceacSChris Mason 140ed2ff2cbSChris Mason static int __commit_transaction(struct ctree_root *root) 141ed2ff2cbSChris Mason { 142ed2ff2cbSChris Mason struct tree_buffer *b; 143ed2ff2cbSChris Mason int ret = 0; 144ed2ff2cbSChris Mason int wret; 145ed2ff2cbSChris Mason while(!list_empty(&root->trans)) { 146ed2ff2cbSChris Mason b = list_entry(root->trans.next, struct tree_buffer, dirty); 147ed2ff2cbSChris Mason list_del_init(&b->dirty); 148ed2ff2cbSChris Mason wret = write_tree_block(root, b); 149ed2ff2cbSChris Mason if (wret) 150ed2ff2cbSChris Mason ret = wret; 151ed2ff2cbSChris Mason tree_block_release(root, b); 152ed2ff2cbSChris Mason } 153ed2ff2cbSChris Mason return ret; 154ed2ff2cbSChris Mason } 155ed2ff2cbSChris Mason 156*a28ec197SChris Mason int commit_transaction(struct ctree_root *root, struct ctree_super_block *s) 157ed2ff2cbSChris Mason { 158*a28ec197SChris Mason int ret = 0; 159*a28ec197SChris Mason 160ed2ff2cbSChris Mason ret = __commit_transaction(root); 161ed2ff2cbSChris Mason if (!ret && root != root->extent_root) 162ed2ff2cbSChris Mason ret = __commit_transaction(root->extent_root); 163ed2ff2cbSChris Mason BUG_ON(ret); 164*a28ec197SChris Mason if (root->commit_root != root->node) { 165*a28ec197SChris Mason struct tree_buffer *snap = root->commit_root; 166*a28ec197SChris Mason root->commit_root = root->node; 167*a28ec197SChris Mason root->node->count++; 168*a28ec197SChris Mason ret = btrfs_drop_snapshot(root, snap); 169*a28ec197SChris Mason BUG_ON(ret); 170*a28ec197SChris Mason tree_block_release(root, snap); 171*a28ec197SChris Mason } 172*a28ec197SChris Mason write_ctree_super(root, s); 173*a28ec197SChris Mason btrfs_finish_extent_commit(root); 174ed2ff2cbSChris Mason return ret; 175ed2ff2cbSChris Mason } 176ed2ff2cbSChris Mason 177d97e63b6SChris Mason static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root, 178d97e63b6SChris Mason struct ctree_root_info *info, int fp) 179d97e63b6SChris Mason { 180ed2ff2cbSChris Mason INIT_LIST_HEAD(&root->trans); 181ed2ff2cbSChris Mason INIT_LIST_HEAD(&root->cache); 182*a28ec197SChris Mason root->cache_size = 0; 183d97e63b6SChris Mason root->fp = fp; 184cfaa7295SChris Mason root->node = NULL; 185d97e63b6SChris Mason root->extent_root = extent_root; 186*a28ec197SChris Mason root->commit_root = NULL; 187*a28ec197SChris Mason root->node = read_tree_block(root, info->tree_root); 188*a28ec197SChris Mason memset(&root->current_insert, 0, sizeof(root->current_insert)); 189d97e63b6SChris Mason return 0; 190d97e63b6SChris Mason } 191d97e63b6SChris Mason 192cfaa7295SChris Mason struct ctree_root *open_ctree(char *filename, struct ctree_super_block *super) 193eb60ceacSChris Mason { 194eb60ceacSChris Mason struct ctree_root *root = malloc(sizeof(struct ctree_root)); 195d97e63b6SChris Mason struct ctree_root *extent_root = malloc(sizeof(struct ctree_root)); 196eb60ceacSChris Mason int fp; 197eb60ceacSChris Mason int ret; 198eb60ceacSChris Mason 199c673024aSChris Mason fp = open(filename, O_CREAT | O_RDWR, 0600); 200eb60ceacSChris Mason if (fp < 0) { 201eb60ceacSChris Mason free(root); 202eb60ceacSChris Mason return NULL; 203eb60ceacSChris Mason } 2049a8dd150SChris Mason INIT_RADIX_TREE(&root->cache_radix, GFP_KERNEL); 205*a28ec197SChris Mason INIT_RADIX_TREE(&root->pinned_radix, GFP_KERNEL); 206*a28ec197SChris Mason INIT_RADIX_TREE(&extent_root->pinned_radix, GFP_KERNEL); 2079a8dd150SChris Mason INIT_RADIX_TREE(&extent_root->cache_radix, GFP_KERNEL); 208cfaa7295SChris Mason ret = pread(fp, super, sizeof(struct ctree_super_block), 209d97e63b6SChris Mason CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 2105c680ed6SChris Mason if (ret == 0 || super->root_info.tree_root == 0) { 2115c680ed6SChris Mason printf("making new FS!\n"); 212d97e63b6SChris Mason ret = mkfs(fp); 213d97e63b6SChris Mason if (ret) 214d97e63b6SChris Mason return NULL; 215cfaa7295SChris Mason ret = pread(fp, super, sizeof(struct ctree_super_block), 216d97e63b6SChris Mason CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 217d97e63b6SChris Mason if (ret != sizeof(struct ctree_super_block)) 218d97e63b6SChris Mason return NULL; 219d97e63b6SChris Mason } 220d97e63b6SChris Mason BUG_ON(ret < 0); 221cfaa7295SChris Mason __setup_root(root, extent_root, &super->root_info, fp); 222cfaa7295SChris Mason __setup_root(extent_root, extent_root, &super->extent_info, fp); 223*a28ec197SChris Mason root->commit_root = root->node; 224*a28ec197SChris Mason root->node->count++; 225eb60ceacSChris Mason return root; 226eb60ceacSChris Mason } 227eb60ceacSChris Mason 228cfaa7295SChris Mason static int __update_root(struct ctree_root *root, struct ctree_root_info *info) 229cfaa7295SChris Mason { 230cfaa7295SChris Mason info->tree_root = root->node->blocknr; 231cfaa7295SChris Mason return 0; 232cfaa7295SChris Mason } 233cfaa7295SChris Mason 234cfaa7295SChris Mason int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s) 235cfaa7295SChris Mason { 236cfaa7295SChris Mason int ret; 237cfaa7295SChris Mason __update_root(root, &s->root_info); 238cfaa7295SChris Mason __update_root(root->extent_root, &s->extent_info); 239cfaa7295SChris Mason ret = pwrite(root->fp, s, sizeof(*s), CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 240cfaa7295SChris Mason if (ret != sizeof(*s)) { 241cfaa7295SChris Mason fprintf(stderr, "failed to write new super block err %d\n", ret); 242cfaa7295SChris Mason return ret; 243cfaa7295SChris Mason } 244cfaa7295SChris Mason return 0; 245cfaa7295SChris Mason } 246cfaa7295SChris Mason 247ed2ff2cbSChris Mason static int drop_cache(struct ctree_root *root) 248ed2ff2cbSChris Mason { 249ed2ff2cbSChris Mason while(!list_empty(&root->cache)) { 250ed2ff2cbSChris Mason struct tree_buffer *b = list_entry(root->cache.next, 251ed2ff2cbSChris Mason struct tree_buffer, cache); 252ed2ff2cbSChris Mason list_del_init(&b->cache); 253ed2ff2cbSChris Mason tree_block_release(root, b); 254ed2ff2cbSChris Mason } 255ed2ff2cbSChris Mason return 0; 256ed2ff2cbSChris Mason } 257*a28ec197SChris Mason int close_ctree(struct ctree_root *root, struct ctree_super_block *s) 258eb60ceacSChris Mason { 259*a28ec197SChris Mason commit_transaction(root, s); 260*a28ec197SChris Mason __commit_transaction(root->extent_root); 261*a28ec197SChris Mason write_ctree_super(root, s); 262ed2ff2cbSChris Mason drop_cache(root->extent_root); 263ed2ff2cbSChris Mason drop_cache(root); 264ed2ff2cbSChris Mason BUG_ON(!list_empty(&root->trans)); 265ed2ff2cbSChris Mason BUG_ON(!list_empty(&root->extent_root->trans)); 266ed2ff2cbSChris Mason 267eb60ceacSChris Mason close(root->fp); 268eb60ceacSChris Mason if (root->node) 269eb60ceacSChris Mason tree_block_release(root, root->node); 270cfaa7295SChris Mason if (root->extent_root->node) 271cfaa7295SChris Mason tree_block_release(root->extent_root, root->extent_root->node); 272*a28ec197SChris Mason tree_block_release(root, root->commit_root); 273eb60ceacSChris Mason free(root); 274eb60ceacSChris Mason printf("on close %d blocks are allocated\n", allocated_blocks); 275eb60ceacSChris Mason return 0; 276eb60ceacSChris Mason } 277eb60ceacSChris Mason 278eb60ceacSChris Mason void tree_block_release(struct ctree_root *root, struct tree_buffer *buf) 279eb60ceacSChris Mason { 280eb60ceacSChris Mason buf->count--; 281cfaa7295SChris Mason if (buf->count < 0) 282cfaa7295SChris Mason BUG(); 283eb60ceacSChris Mason if (buf->count == 0) { 28402217ed2SChris Mason BUG_ON(!list_empty(&buf->cache)); 28502217ed2SChris Mason BUG_ON(!list_empty(&buf->dirty)); 286eb60ceacSChris Mason if (!radix_tree_lookup(&root->cache_radix, buf->blocknr)) 287eb60ceacSChris Mason BUG(); 288eb60ceacSChris Mason radix_tree_delete(&root->cache_radix, buf->blocknr); 289eb60ceacSChris Mason memset(buf, 0, sizeof(*buf)); 290eb60ceacSChris Mason free(buf); 291eb60ceacSChris Mason BUG_ON(allocated_blocks == 0); 292eb60ceacSChris Mason allocated_blocks--; 293ed2ff2cbSChris Mason BUG_ON(root->cache_size == 0); 294ed2ff2cbSChris Mason root->cache_size--; 295eb60ceacSChris Mason } 296eb60ceacSChris Mason } 297eb60ceacSChris Mason 298