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