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_size = 0; 15ed2ff2cbSChris Mason int cache_max = 10000; 16eb60ceacSChris Mason 179a8dd150SChris Mason static int check_tree_block(struct ctree_root *root, struct tree_buffer *buf) 18eb60ceacSChris Mason { 199a8dd150SChris Mason if (buf->blocknr != buf->node.header.blocknr) 209a8dd150SChris Mason BUG(); 219a8dd150SChris Mason if (root->node && buf->node.header.parentid != root->node->node.header.parentid) 229a8dd150SChris Mason BUG(); 239a8dd150SChris Mason return 0; 24eb60ceacSChris Mason } 25eb60ceacSChris Mason 26ed2ff2cbSChris Mason static int free_some_buffers(struct ctree_root *root) 27ed2ff2cbSChris Mason { 28ed2ff2cbSChris Mason struct list_head *node, *next; 29ed2ff2cbSChris Mason struct tree_buffer *b; 30ed2ff2cbSChris Mason if (root->cache_size < cache_max) 31ed2ff2cbSChris Mason return 0; 32ed2ff2cbSChris Mason list_for_each_safe(node, next, &root->cache) { 33ed2ff2cbSChris Mason b = list_entry(node, struct tree_buffer, cache); 34ed2ff2cbSChris Mason if (b->count == 1) { 35ed2ff2cbSChris Mason BUG_ON(!list_empty(&b->dirty)); 36ed2ff2cbSChris Mason list_del_init(&b->cache); 37ed2ff2cbSChris Mason tree_block_release(root, b); 38ed2ff2cbSChris Mason if (root->cache_size < cache_max) 39ed2ff2cbSChris Mason return 0; 40ed2ff2cbSChris Mason } 41ed2ff2cbSChris Mason } 42ed2ff2cbSChris Mason return 0; 43ed2ff2cbSChris Mason } 44ed2ff2cbSChris Mason 45eb60ceacSChris Mason struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr) 46eb60ceacSChris Mason { 47eb60ceacSChris Mason struct tree_buffer *buf; 48eb60ceacSChris Mason int ret; 49eb60ceacSChris Mason buf = malloc(sizeof(struct tree_buffer)); 50eb60ceacSChris Mason if (!buf) 51eb60ceacSChris Mason return buf; 52eb60ceacSChris Mason allocated_blocks++; 53eb60ceacSChris Mason buf->blocknr = blocknr; 54ed2ff2cbSChris Mason buf->count = 2; 55ed2ff2cbSChris Mason INIT_LIST_HEAD(&buf->dirty); 56ed2ff2cbSChris Mason free_some_buffers(root); 57eb60ceacSChris Mason radix_tree_preload(GFP_KERNEL); 58eb60ceacSChris Mason ret = radix_tree_insert(&root->cache_radix, blocknr, buf); 59eb60ceacSChris Mason radix_tree_preload_end(); 60ed2ff2cbSChris Mason list_add_tail(&buf->cache, &root->cache); 61ed2ff2cbSChris Mason root->cache_size++; 62eb60ceacSChris Mason if (ret) { 63eb60ceacSChris Mason free(buf); 64eb60ceacSChris Mason return NULL; 65eb60ceacSChris Mason } 66eb60ceacSChris Mason return buf; 67eb60ceacSChris Mason } 68eb60ceacSChris Mason 699a8dd150SChris Mason struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr) 70eb60ceacSChris Mason { 71eb60ceacSChris Mason struct tree_buffer *buf; 729a8dd150SChris Mason buf = radix_tree_lookup(&root->cache_radix, blocknr); 739a8dd150SChris Mason if (buf) { 749a8dd150SChris Mason buf->count++; 759a8dd150SChris Mason } else { 769a8dd150SChris Mason buf = alloc_tree_block(root, blocknr); 779a8dd150SChris Mason if (!buf) { 78eb60ceacSChris Mason BUG(); 79eb60ceacSChris Mason return NULL; 80eb60ceacSChris Mason } 819a8dd150SChris Mason } 82eb60ceacSChris Mason return buf; 83eb60ceacSChris Mason } 84eb60ceacSChris Mason 85eb60ceacSChris Mason struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr) 86eb60ceacSChris Mason { 87d97e63b6SChris Mason loff_t offset = blocknr * CTREE_BLOCKSIZE; 88eb60ceacSChris Mason struct tree_buffer *buf; 89eb60ceacSChris Mason int ret; 90eb60ceacSChris Mason 91eb60ceacSChris Mason buf = radix_tree_lookup(&root->cache_radix, blocknr); 92eb60ceacSChris Mason if (buf) { 93eb60ceacSChris Mason buf->count++; 949a8dd150SChris Mason } else { 95eb60ceacSChris Mason buf = alloc_tree_block(root, blocknr); 96eb60ceacSChris Mason if (!buf) 97eb60ceacSChris Mason return NULL; 98eb60ceacSChris Mason ret = pread(root->fp, &buf->node, CTREE_BLOCKSIZE, offset); 99eb60ceacSChris Mason if (ret != CTREE_BLOCKSIZE) { 100eb60ceacSChris Mason free(buf); 101eb60ceacSChris Mason return NULL; 102eb60ceacSChris Mason } 1039a8dd150SChris Mason } 1049a8dd150SChris Mason if (check_tree_block(root, buf)) 105cfaa7295SChris Mason BUG(); 106eb60ceacSChris Mason return buf; 107eb60ceacSChris Mason } 108eb60ceacSChris Mason 109ed2ff2cbSChris Mason int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf) 110ed2ff2cbSChris Mason { 111ed2ff2cbSChris Mason if (!list_empty(&buf->dirty)) 112ed2ff2cbSChris Mason return 0; 113ed2ff2cbSChris Mason list_add_tail(&buf->dirty, &root->trans); 114ed2ff2cbSChris Mason buf->count++; 115ed2ff2cbSChris Mason return 0; 116ed2ff2cbSChris Mason } 117ed2ff2cbSChris Mason 118ed2ff2cbSChris Mason int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf) 119ed2ff2cbSChris Mason { 120ed2ff2cbSChris Mason if (!list_empty(&buf->dirty)) { 121ed2ff2cbSChris Mason list_del_init(&buf->dirty); 122ed2ff2cbSChris Mason tree_block_release(root, buf); 123ed2ff2cbSChris Mason } 124ed2ff2cbSChris Mason return 0; 125ed2ff2cbSChris Mason } 126ed2ff2cbSChris Mason 127eb60ceacSChris Mason int write_tree_block(struct ctree_root *root, struct tree_buffer *buf) 128eb60ceacSChris Mason { 129eb60ceacSChris Mason u64 blocknr = buf->blocknr; 130d97e63b6SChris Mason loff_t offset = blocknr * CTREE_BLOCKSIZE; 131eb60ceacSChris Mason int ret; 132eb60ceacSChris Mason 133eb60ceacSChris Mason if (buf->blocknr != buf->node.header.blocknr) 134eb60ceacSChris Mason BUG(); 135eb60ceacSChris Mason ret = pwrite(root->fp, &buf->node, CTREE_BLOCKSIZE, offset); 136eb60ceacSChris Mason if (ret != CTREE_BLOCKSIZE) 137eb60ceacSChris Mason return ret; 138eb60ceacSChris Mason return 0; 139eb60ceacSChris Mason } 140eb60ceacSChris Mason 141ed2ff2cbSChris Mason static int __commit_transaction(struct ctree_root *root) 142ed2ff2cbSChris Mason { 143ed2ff2cbSChris Mason struct tree_buffer *b; 144ed2ff2cbSChris Mason int ret = 0; 145ed2ff2cbSChris Mason int wret; 146ed2ff2cbSChris Mason while(!list_empty(&root->trans)) { 147ed2ff2cbSChris Mason b = list_entry(root->trans.next, struct tree_buffer, dirty); 148ed2ff2cbSChris Mason list_del_init(&b->dirty); 149ed2ff2cbSChris Mason wret = write_tree_block(root, b); 150ed2ff2cbSChris Mason if (wret) 151ed2ff2cbSChris Mason ret = wret; 152ed2ff2cbSChris Mason tree_block_release(root, b); 153ed2ff2cbSChris Mason } 154ed2ff2cbSChris Mason return ret; 155ed2ff2cbSChris Mason } 156ed2ff2cbSChris Mason 157ed2ff2cbSChris Mason int commit_transaction(struct ctree_root *root) 158ed2ff2cbSChris Mason { 159ed2ff2cbSChris Mason int ret; 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); 164ed2ff2cbSChris Mason return ret; 165ed2ff2cbSChris Mason } 166ed2ff2cbSChris Mason 167d97e63b6SChris Mason static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root, 168d97e63b6SChris Mason struct ctree_root_info *info, int fp) 169d97e63b6SChris Mason { 170ed2ff2cbSChris Mason INIT_LIST_HEAD(&root->trans); 171ed2ff2cbSChris Mason INIT_LIST_HEAD(&root->cache); 172d97e63b6SChris Mason root->fp = fp; 173cfaa7295SChris Mason root->node = NULL; 174d97e63b6SChris Mason root->node = read_tree_block(root, info->tree_root); 175d97e63b6SChris Mason root->extent_root = extent_root; 176d97e63b6SChris Mason return 0; 177d97e63b6SChris Mason } 178d97e63b6SChris Mason 179cfaa7295SChris Mason struct ctree_root *open_ctree(char *filename, struct ctree_super_block *super) 180eb60ceacSChris Mason { 181eb60ceacSChris Mason struct ctree_root *root = malloc(sizeof(struct ctree_root)); 182d97e63b6SChris Mason struct ctree_root *extent_root = malloc(sizeof(struct ctree_root)); 183eb60ceacSChris Mason int fp; 184eb60ceacSChris Mason int ret; 185eb60ceacSChris Mason 186c673024aSChris Mason fp = open(filename, O_CREAT | O_RDWR, 0600); 187eb60ceacSChris Mason if (fp < 0) { 188eb60ceacSChris Mason free(root); 189eb60ceacSChris Mason return NULL; 190eb60ceacSChris Mason } 1919a8dd150SChris Mason INIT_RADIX_TREE(&root->cache_radix, GFP_KERNEL); 1929a8dd150SChris Mason INIT_RADIX_TREE(&extent_root->cache_radix, GFP_KERNEL); 193cfaa7295SChris Mason ret = pread(fp, super, sizeof(struct ctree_super_block), 194d97e63b6SChris Mason CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 1955c680ed6SChris Mason if (ret == 0 || super->root_info.tree_root == 0) { 1965c680ed6SChris Mason printf("making new FS!\n"); 197d97e63b6SChris Mason ret = mkfs(fp); 198d97e63b6SChris Mason if (ret) 199d97e63b6SChris Mason return NULL; 200cfaa7295SChris Mason ret = pread(fp, super, sizeof(struct ctree_super_block), 201d97e63b6SChris Mason CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 202d97e63b6SChris Mason if (ret != sizeof(struct ctree_super_block)) 203d97e63b6SChris Mason return NULL; 204d97e63b6SChris Mason } 205d97e63b6SChris Mason BUG_ON(ret < 0); 206cfaa7295SChris Mason __setup_root(root, extent_root, &super->root_info, fp); 207cfaa7295SChris Mason __setup_root(extent_root, extent_root, &super->extent_info, fp); 208eb60ceacSChris Mason return root; 209eb60ceacSChris Mason } 210eb60ceacSChris Mason 211cfaa7295SChris Mason static int __update_root(struct ctree_root *root, struct ctree_root_info *info) 212cfaa7295SChris Mason { 213cfaa7295SChris Mason info->tree_root = root->node->blocknr; 214cfaa7295SChris Mason return 0; 215cfaa7295SChris Mason } 216cfaa7295SChris Mason 217cfaa7295SChris Mason int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s) 218cfaa7295SChris Mason { 219cfaa7295SChris Mason int ret; 220cfaa7295SChris Mason __update_root(root, &s->root_info); 221cfaa7295SChris Mason __update_root(root->extent_root, &s->extent_info); 222cfaa7295SChris Mason ret = pwrite(root->fp, s, sizeof(*s), CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); 223cfaa7295SChris Mason if (ret != sizeof(*s)) { 224cfaa7295SChris Mason fprintf(stderr, "failed to write new super block err %d\n", ret); 225cfaa7295SChris Mason return ret; 226cfaa7295SChris Mason } 227cfaa7295SChris Mason return 0; 228cfaa7295SChris Mason } 229cfaa7295SChris Mason 230ed2ff2cbSChris Mason static int drop_cache(struct ctree_root *root) 231ed2ff2cbSChris Mason { 232ed2ff2cbSChris Mason while(!list_empty(&root->cache)) { 233ed2ff2cbSChris Mason struct tree_buffer *b = list_entry(root->cache.next, 234ed2ff2cbSChris Mason struct tree_buffer, cache); 235ed2ff2cbSChris Mason list_del_init(&b->cache); 236ed2ff2cbSChris Mason tree_block_release(root, b); 237ed2ff2cbSChris Mason } 238ed2ff2cbSChris Mason return 0; 239ed2ff2cbSChris Mason } 240eb60ceacSChris Mason int close_ctree(struct ctree_root *root) 241eb60ceacSChris Mason { 242ed2ff2cbSChris Mason drop_cache(root->extent_root); 243ed2ff2cbSChris Mason drop_cache(root); 244ed2ff2cbSChris Mason BUG_ON(!list_empty(&root->trans)); 245ed2ff2cbSChris Mason BUG_ON(!list_empty(&root->extent_root->trans)); 246ed2ff2cbSChris Mason 247eb60ceacSChris Mason close(root->fp); 248eb60ceacSChris Mason if (root->node) 249eb60ceacSChris Mason tree_block_release(root, root->node); 250cfaa7295SChris Mason if (root->extent_root->node) 251cfaa7295SChris Mason tree_block_release(root->extent_root, root->extent_root->node); 252eb60ceacSChris Mason free(root); 253eb60ceacSChris Mason printf("on close %d blocks are allocated\n", allocated_blocks); 254eb60ceacSChris Mason return 0; 255eb60ceacSChris Mason } 256eb60ceacSChris Mason 257eb60ceacSChris Mason void tree_block_release(struct ctree_root *root, struct tree_buffer *buf) 258eb60ceacSChris Mason { 259eb60ceacSChris Mason buf->count--; 260cfaa7295SChris Mason if (buf->count < 0) 261cfaa7295SChris Mason BUG(); 262eb60ceacSChris Mason if (buf->count == 0) { 263eb60ceacSChris Mason if (!radix_tree_lookup(&root->cache_radix, buf->blocknr)) 264eb60ceacSChris Mason BUG(); 265eb60ceacSChris Mason radix_tree_delete(&root->cache_radix, buf->blocknr); 266eb60ceacSChris Mason memset(buf, 0, sizeof(*buf)); 267eb60ceacSChris Mason free(buf); 268eb60ceacSChris Mason BUG_ON(allocated_blocks == 0); 269eb60ceacSChris Mason allocated_blocks--; 270ed2ff2cbSChris Mason BUG_ON(root->cache_size == 0); 271ed2ff2cbSChris Mason root->cache_size--; 272eb60ceacSChris Mason } 273eb60ceacSChris Mason } 274eb60ceacSChris Mason 275