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