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 30 struct 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 EndCachedExtent41 uint64 End() const { return offset + length; } 42 bool IsAllocated() const; 43 bool IsData() const; 44 45 void Info() const; 46 47 private: CachedExtentCachedExtent48 CachedExtent() {} 49 CachedExtent(const CachedExtent& other); 50 }; 51 52 53 struct TreeDefinition { 54 typedef uint64 Key; 55 typedef CachedExtent Value; 56 GetAVLTreeNodeTreeDefinition57 AVLTreeNode* GetAVLTreeNode(Value* value) const 58 { 59 return value; 60 } 61 GetValueTreeDefinition62 Value* GetValue(AVLTreeNode* node) const 63 { 64 return static_cast<Value*>(node); 65 } 66 CompareTreeDefinition67 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 CompareTreeDefinition76 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 85 struct CachedExtentTree : AVLTree<TreeDefinition> { 86 public: 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(); 98 private: 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 108 class BlockGroup { 109 public: 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 Flags()118 uint64 Flags() const { return fItem->Flags(); } Start()119 uint64 Start() const { return fKey.ObjectID(); } End()120 uint64 End() const 121 { return fKey.ObjectID() + fKey.Offset(); } 122 123 private: 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 131 private: 132 btrfs_key fKey; 133 btrfs_block_group* fItem; 134 BTree* fCurrentExtentTree; 135 }; 136 137 138 class ExtentAllocator { 139 public: 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); 150 private: 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); 156 private: 157 Volume* fVolume; 158 CachedExtentTree* fTree; 159 uint64 fStart; 160 uint64 fEnd; 161 }; 162 163 164 #endif // EXTENT_ALLOCATOR_H 165