1/* 2 * Copyright 2017, Ch��� V�� Gia Hy, cvghy116@gmail.com. 3 * This file may be used under the terms of the MIT License. 4 */ 5#ifndef EXTENT_ALLOCATOR_H 6#define EXTENT_ALLOCATOR_H 7 8 9#include "BTree.h" 10#include "Volume.h" 11 12#include "system_dependencies.h" 13 14 15#ifdef FS_SHELL 16#define ERROR(x...) TRACE(x) 17#else 18#include <DebugSupport.h> 19#endif 20 21 22//#define TRACE_BTRFS 23#ifdef TRACE_BTRFS 24# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x) 25#else 26# define TRACE(x...) ; 27#endif 28 29 30struct CachedExtent : AVLTreeNode { 31 uint64 offset; 32 uint64 length; 33 int refCount; 34 uint64 flags; 35 btrfs_extent* item; 36 37 static CachedExtent* Create(uint64 offset, uint64 length, 38 uint64 flags); 39 void Delete(); 40 41 uint64 End() const { return offset + length; } 42 bool IsAllocated() const; 43 bool IsData() const; 44 45 void Info() const; 46 47private: 48 CachedExtent() {} 49 CachedExtent(const CachedExtent& other); 50}; 51 52 53struct TreeDefinition { 54 typedef uint64 Key; 55 typedef CachedExtent Value; 56 57 AVLTreeNode* GetAVLTreeNode(Value* value) const 58 { 59 return value; 60 } 61 62 Value* GetValue(AVLTreeNode* node) const 63 { 64 return static_cast<Value*>(node); 65 } 66 67 int Compare(const Key& a, const Value* b) const 68 { 69 if (a < b->offset) 70 return -1; 71 if (a >= b->End()) 72 return 1; 73 return 0; 74 } 75 76 int Compare(const Value* a, const Value* b) const 77 { 78 int comp = Compare(a->offset, b); 79 // TODO: check more conditions here if necessary 80 return comp; 81 } 82}; 83 84 85struct CachedExtentTree : AVLTree<TreeDefinition> { 86public: 87 CachedExtentTree( 88 const TreeDefinition& definition); 89 ~CachedExtentTree(); 90 91 status_t FindNext(CachedExtent** chosen, uint64 offset, 92 uint64 size, uint64 type); 93 status_t AddExtent(CachedExtent* extent); 94 status_t FillFreeExtents(uint64 lowerBound, 95 uint64 upperBound); 96 void DumpInOrder() const; 97 void Delete(); 98private: 99 status_t _AddAllocatedExtent(CachedExtent* node); 100 status_t _AddFreeExtent(CachedExtent* node); 101 void _CombineFreeExtent(CachedExtent* node); 102 void _RemoveExtent(CachedExtent* node); 103 void _DumpInOrder(CachedExtent* node) const; 104 void _Delete(CachedExtent* node); 105}; 106 107 108class BlockGroup { 109public: 110 BlockGroup(BTree* extentTree); 111 ~BlockGroup(); 112 113 status_t SetExtentTree(off_t rootAddress); 114 status_t Initialize(uint64 flag); 115 status_t LoadExtent(CachedExtentTree* tree, 116 bool inverse = false); 117 118 uint64 Flags() const { return fItem->Flags(); } 119 uint64 Start() const { return fKey.ObjectID(); } 120 uint64 End() const 121 { return fKey.ObjectID() + fKey.Offset(); } 122 123private: 124 BlockGroup(const BlockGroup&); 125 BlockGroup& operator=(const BlockGroup&); 126 status_t _InsertExtent(CachedExtentTree* tree, 127 uint64 size, uint64 length, uint64 flags); 128 status_t _InsertExtent(CachedExtentTree* tree, 129 CachedExtent* extent); 130 131private: 132 btrfs_key fKey; 133 btrfs_block_group* fItem; 134 BTree* fCurrentExtentTree; 135}; 136 137 138class ExtentAllocator { 139public: 140 ExtentAllocator(Volume* volume); 141 ~ExtentAllocator(); 142 143 status_t Initialize(); 144 status_t AllocateTreeBlock(uint64& found, 145 uint64 start = (uint64)-1, 146 uint64 flags = BTRFS_BLOCKGROUP_FLAG_METADATA); 147 status_t AllocateDataBlock(uint64& found, uint64 size, 148 uint64 start = (uint64)-1, 149 uint64 flags = BTRFS_BLOCKGROUP_FLAG_DATA); 150private: 151 ExtentAllocator(const ExtentAllocator&); 152 ExtentAllocator& operator=(const ExtentAllocator&); 153 status_t _LoadExtentTree(uint64 flags); 154 status_t _Allocate(uint64& found, uint64 start, 155 uint64 size, uint64 type); 156private: 157 Volume* fVolume; 158 CachedExtentTree* fTree; 159 uint64 fStart; 160 uint64 fEnd; 161}; 162 163 164#endif // EXTENT_ALLOCATOR_H 165