Ticket #13612: btrfs.patchset

File btrfs.patchset, 164.6 KB (added by pulkomandy, 7 years ago)

Hyche's work as a patchset, for archiving purposes

Line 
1From 760dcbe03220b4dc159c3df35d3466724bddae8c Mon Sep 17 00:00:00 2001
2From: hyche <cvghy116@gmail.com>
3Date: Thu, 18 May 2017 19:52:06 +0700
4Subject: [PATCH 01/36] Fixed: Code style (again) * Pointer/Reference should be
5 next to type * else if -> if * Remove trailing spaces
6
7---
8 .../kernel/file_systems/btrfs/Attribute.cpp | 4 +-
9 src/add-ons/kernel/file_systems/btrfs/CRCTable.cpp | 66 +++++++++++-----------
10 .../kernel/file_systems/btrfs/CachedBlock.h | 2 +-
11 src/add-ons/kernel/file_systems/btrfs/Chunk.cpp | 8 +--
12 .../file_systems/btrfs/DirectoryIterator.cpp | 4 +-
13 src/add-ons/kernel/file_systems/btrfs/Inode.h | 2 +-
14 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 18 +++---
15 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 10 ++--
16 .../kernel/file_systems/btrfs/crc_table.cpp | 2 +-
17 .../kernel/file_systems/btrfs/kernel_interface.cpp | 26 +++++----
18 10 files changed, 72 insertions(+), 70 deletions(-)
19
20diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
21index 3553005..d701a2a 100644
22--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
23+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
24@@ -161,7 +161,7 @@ Attribute::_Lookup(const char* name, size_t nameLength,
25 B_PRIu32 " \"%s\"\n", hash, name);
26 return status;
27 }
28-
29+
30 if (_entries == NULL)
31 free(entries);
32 else
33@@ -186,7 +186,7 @@ Attribute::_FindEntry(btrfs_dir_entry* entries, size_t length,
34 // TODO there could be several entries with the same name hash
35 entry = (btrfs_dir_entry*)((uint8*)entry + entry->Length());
36 }
37-
38+
39 *_entry = entry;
40 return B_OK;
41 }
42diff --git a/src/add-ons/kernel/file_systems/btrfs/CRCTable.cpp b/src/add-ons/kernel/file_systems/btrfs/CRCTable.cpp
43index b621f75..6dca655 100644
44--- a/src/add-ons/kernel/file_systems/btrfs/CRCTable.cpp
45+++ b/src/add-ons/kernel/file_systems/btrfs/CRCTable.cpp
46@@ -11,39 +11,39 @@
47
48
49 //! CRC 03667067501 table, as generated by crc_table.cpp
50-static uint32 kCrcTable[256] = {
51- 0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, 0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb,
52- 0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b, 0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24,
53- 0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b, 0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
54- 0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54, 0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b,
55- 0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a, 0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35,
56- 0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5, 0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
57- 0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45, 0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a,
58- 0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a, 0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595,
59- 0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48, 0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
60- 0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687, 0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198,
61- 0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927, 0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38,
62- 0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8, 0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
63- 0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096, 0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789,
64- 0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859, 0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46,
65- 0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9, 0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
66- 0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36, 0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829,
67- 0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c, 0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93,
68- 0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043, 0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
69- 0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3, 0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc,
70- 0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c, 0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033,
71- 0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652, 0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
72- 0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d, 0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982,
73- 0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d, 0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622,
74- 0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2, 0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
75- 0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530, 0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f,
76- 0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff, 0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0,
77- 0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f, 0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
78- 0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90, 0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f,
79- 0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee, 0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1,
80- 0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321, 0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
81- 0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81, 0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e,
82- 0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e, 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351
83+static uint32 kCrcTable[256] = {
84+ 0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, 0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb,
85+ 0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b, 0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24,
86+ 0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b, 0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
87+ 0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54, 0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b,
88+ 0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a, 0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35,
89+ 0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5, 0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
90+ 0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45, 0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a,
91+ 0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a, 0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595,
92+ 0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48, 0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
93+ 0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687, 0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198,
94+ 0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927, 0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38,
95+ 0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8, 0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
96+ 0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096, 0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789,
97+ 0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859, 0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46,
98+ 0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9, 0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
99+ 0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36, 0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829,
100+ 0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c, 0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93,
101+ 0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043, 0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
102+ 0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3, 0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc,
103+ 0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c, 0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033,
104+ 0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652, 0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
105+ 0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d, 0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982,
106+ 0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d, 0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622,
107+ 0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2, 0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
108+ 0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530, 0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f,
109+ 0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff, 0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0,
110+ 0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f, 0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
111+ 0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90, 0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f,
112+ 0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee, 0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1,
113+ 0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321, 0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
114+ 0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81, 0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e,
115+ 0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e, 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351
116 };
117
118
119diff --git a/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h b/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
120index 59ff119..1071977 100644
121--- a/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
122+++ b/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
123@@ -29,7 +29,7 @@ private:
124 CachedBlock(const CachedBlock&);
125 CachedBlock& operator=(const CachedBlock&);
126 // no implementation
127-
128+
129 protected:
130 Volume* fVolume;
131 off_t fBlockNumber;
132diff --git a/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp b/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp
133index 9ce7003..f730baa 100644
134--- a/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp
135+++ b/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp
136@@ -37,8 +37,8 @@ Chunk::Chunk(struct btrfs_chunk* chunk, fsblock_t offset)
137
138 TRACE("chunk[0] length %" B_PRIu64 " owner %" B_PRIu64 " stripe_length %"
139 B_PRIu64 " type %" B_PRIu64 " stripe_count %u sub_stripes %u "
140- "sector_size %" B_PRIu32 "\n", chunk->Length(), chunk->Owner(),
141- chunk->StripeLength(), chunk->Type(), chunk->StripeCount(),
142+ "sector_size %" B_PRIu32 "\n", chunk->Length(), chunk->Owner(),
143+ chunk->StripeLength(), chunk->Type(), chunk->StripeCount(),
144 chunk->SubStripes(), chunk->SectorSize());
145 for (int32 i = 0; i < chunk->StripeCount(); i++) {
146 TRACE("chunk.stripe[%" B_PRId32 "].physical %" B_PRId64 " deviceid %"
147@@ -57,7 +57,7 @@ Chunk::~Chunk()
148 uint32
149 Chunk::Size() const
150 {
151- return sizeof(struct btrfs_chunk)
152+ return sizeof(struct btrfs_chunk)
153 + fChunk->StripeCount() * sizeof(struct btrfs_stripe);
154 }
155
156@@ -71,7 +71,7 @@ Chunk::FindBlock(off_t logical, off_t& physical)
157 if (logical < (off_t)fChunkOffset
158 || logical > (off_t)(fChunkOffset + fChunk->Length()))
159 return B_BAD_VALUE;
160-
161+
162 // only one stripe
163 physical = logical + fChunk->stripes[0].Offset() - fChunkOffset;
164 return B_OK;
165diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
166index ded0351..e898d25 100644
167--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
168+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
169@@ -109,11 +109,11 @@ status_t
170 DirectoryIterator::Lookup(const char* name, size_t nameLength, ino_t* _id)
171 {
172 if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0) {
173- if (strcmp(name, ".") == 0
174+ if (strcmp(name, ".") == 0
175 || fInode->ID() == BTRFS_OBJECT_ID_CHUNK_TREE) {
176 *_id = fInode->ID();
177 return B_OK;
178- }
179+ }
180 return fInode->FindParent(_id);
181 }
182
183diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.h b/src/add-ons/kernel/file_systems/btrfs/Inode.h
184index 683ae03..4182634 100644
185--- a/src/add-ons/kernel/file_systems/btrfs/Inode.h
186+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.h
187@@ -62,7 +62,7 @@ public:
188
189 void* FileCache() const { return fCache; }
190 void* Map() const { return fMap; }
191-
192+
193 status_t FindParent(ino_t* id);
194 private:
195 Inode(Volume* volume);
196diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
197index 1886041..4a459fa 100644
198--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
199+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
200@@ -193,7 +193,7 @@ btrfs_super_block::IsValid()
201 // TODO: check some more values!
202 if (strncmp(magic, BTRFS_SUPER_BLOCK_MAGIC, sizeof(magic)) != 0)
203 return false;
204-
205+
206 return true;
207 }
208
209@@ -240,7 +240,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
210 {
211 flags |= B_MOUNT_READ_ONLY;
212 // we only support read-only for now
213-
214+
215 if ((flags & B_MOUNT_READ_ONLY) != 0) {
216 TRACE("Volume::Mount(): Read only\n");
217 } else {
218@@ -264,7 +264,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
219 ERROR("Volume::Mount(): Identify() failed\n");
220 return status;
221 }
222-
223+
224 fBlockSize = fSuperBlock.BlockSize();
225 TRACE("block size %" B_PRIu32 "\n", fBlockSize);
226
227@@ -278,7 +278,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
228 if (key->Type() != BTRFS_KEY_TYPE_CHUNK_ITEM) {
229 break;
230 }
231-
232+
233 struct btrfs_chunk* chunk = (struct btrfs_chunk*)(key + 1);
234 fChunk = new(std::nothrow) Chunk(chunk, key->Offset());
235 if (fChunk == NULL)
236@@ -298,7 +298,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
237 FindBlock(fSuperBlock.LogRoot(), physical);
238 TRACE("Volume::Mount() log_root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
239 fSuperBlock.LogRoot(), physical);
240-
241+
242 // check if the device size is large enough to hold the file system
243 off_t diskSize;
244 status = opener.GetSize(&diskSize);
245@@ -311,7 +311,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
246 fBlockSize);
247 if (fBlockCache == NULL)
248 return B_ERROR;
249-
250+
251 TRACE("Volume::Mount(): Initialized block cache: %p\n", fBlockCache);
252
253 fChunkTree = new(std::nothrow) BPlusTree(this, fSuperBlock.ChunkRoot());
254@@ -347,7 +347,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
255 free(root);
256 if (fExtentTree == NULL)
257 return B_NO_MEMORY;
258-
259+
260 search_key.SetOffset(0);
261 search_key.SetObjectID(BTRFS_OBJECT_ID_FS_TREE);
262 if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
263@@ -359,7 +359,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
264 free(root);
265 if (fFSTree == NULL)
266 return B_NO_MEMORY;
267-
268+
269 search_key.SetOffset(0);
270 search_key.SetObjectID(BTRFS_OBJECT_ID_DEV_TREE);
271 if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
272@@ -385,7 +385,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
273 free(root);
274 if (fChecksumTree == NULL)
275 return B_NO_MEMORY;
276-
277+
278 // ready
279 status = get_vnode(fFSVolume, BTRFS_OBJECT_ID_CHUNK_TREE,
280 (void**)&fRootNode);
281diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
282index 2791cf2..056aa0c 100644
283--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
284+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
285@@ -19,7 +19,7 @@ struct btrfs_key {
286 uint64 object_id;
287 uint8 type;
288 uint64 offset;
289-
290+
291 uint64 ObjectID() const { return B_LENDIAN_TO_HOST_INT64(object_id); }
292 uint8 Type() const { return type; }
293 uint64 Offset() const { return B_LENDIAN_TO_HOST_INT64(offset); }
294@@ -223,13 +223,13 @@ struct btrfs_inode {
295 timespec.tv_sec = B_LENDIAN_TO_HOST_INT64(time.seconds);
296 timespec.tv_nsec = B_LENDIAN_TO_HOST_INT32(time.nanoseconds);
297 }
298- void GetAccessTime(struct timespec& timespec) const
299+ void GetAccessTime(struct timespec& timespec) const
300 { _DecodeTime(timespec, access_time); }
301- void GetChangeTime(struct timespec& timespec) const
302+ void GetChangeTime(struct timespec& timespec) const
303 { _DecodeTime(timespec, change_time); }
304- void GetModificationTime(struct timespec& timespec) const
305+ void GetModificationTime(struct timespec& timespec) const
306 { _DecodeTime(timespec, modification_time); }
307- void GetCreationTime(struct timespec& timespec) const
308+ void GetCreationTime(struct timespec& timespec) const
309 { _DecodeTime(timespec, creation_time); }
310 } _PACKED;
311
312diff --git a/src/add-ons/kernel/file_systems/btrfs/crc_table.cpp b/src/add-ons/kernel/file_systems/btrfs/crc_table.cpp
313index e35f217..09ca7c2 100644
314--- a/src/add-ons/kernel/file_systems/btrfs/crc_table.cpp
315+++ b/src/add-ons/kernel/file_systems/btrfs/crc_table.cpp
316@@ -11,7 +11,7 @@
317 UDF tag id CRC values.
318
319 This code based off of crc code in UDF-2.50 specs, as permitted.
320- See UDF-2.50 6.5 for more information.
321+ See UDF-2.50 6.5 for more information.
322
323 Reflected version by Jéme Duval
324 */
325diff --git a/src/add-ons/kernel/file_systems/btrfs/kernel_interface.cpp b/src/add-ons/kernel/file_systems/btrfs/kernel_interface.cpp
326index c405125..8a75c50 100644
327--- a/src/add-ons/kernel/file_systems/btrfs/kernel_interface.cpp
328+++ b/src/add-ons/kernel/file_systems/btrfs/kernel_interface.cpp
329@@ -175,18 +175,18 @@ btrfs_get_vnode(fs_volume* _volume, ino_t id, fs_vnode* _node, int* _type,
330 return B_NO_MEMORY;
331
332 status_t status = inode->InitCheck();
333- if (status != B_OK)
334+ if (status != B_OK) {
335 delete inode;
336-
337- if (status == B_OK) {
338- _node->private_node = inode;
339- _node->ops = &gBtrfsVnodeOps;
340- *_type = inode->Mode();
341- *_flags = 0;
342- } else
343 ERROR("get_vnode: InitCheck() failed. Error: %s\n", strerror(status));
344+ return status;
345+ }
346
347- return status;
348+ _node->private_node = inode;
349+ _node->ops = &gBtrfsVnodeOps;
350+ *_type = inode->Mode();
351+ *_flags = 0;
352+
353+ return B_OK;
354 }
355
356
357@@ -620,11 +620,13 @@ btrfs_read_attr_dir(fs_volume* _volume, fs_vnode* _node,
358
359 size_t length = bufferSize;
360 status_t status = iterator->GetNext(dirent->d_name, &length);
361+ if (status != B_OK)
362+ return status;
363+
364 if (status == B_ENTRY_NOT_FOUND) {
365 *_num = 0;
366 return B_OK;
367- } else if (status != B_OK)
368- return status;
369+ }
370
371 Volume* volume = (Volume*)_volume->private_volume;
372 dirent->d_dev = volume->ID();
373@@ -860,7 +862,7 @@ static file_system_module_info sBtrfsFileSystem = {
374
375 &btrfs_mount,
376
377-
378+
379 /* capability querying operations */
380 NULL,
381
382--
3832.7.0
384
385
386From 1e509413c09cdde8259e8a2b8eb467ffd2a8436a Mon Sep 17 00:00:00 2001
387From: hyche <cvghy116@gmail.com>
388Date: Sun, 4 Jun 2017 23:07:38 +0700
389Subject: [PATCH 02/36] btrfs_shell: Added cat command
390
391---
392 src/tools/btrfs_shell/Jamfile | 5 ++
393 src/tools/btrfs_shell/additional_commands.cpp | 19 ++++++++
394 src/tools/btrfs_shell/command_cat.cpp | 67 +++++++++++++++++++++++++++
395 src/tools/btrfs_shell/command_cat.h | 17 +++++++
396 4 files changed, 108 insertions(+)
397 create mode 100644 src/tools/btrfs_shell/additional_commands.cpp
398 create mode 100644 src/tools/btrfs_shell/command_cat.cpp
399 create mode 100644 src/tools/btrfs_shell/command_cat.h
400
401diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
402index 9f46bb3..842b2b5 100644
403--- a/src/tools/btrfs_shell/Jamfile
404+++ b/src/tools/btrfs_shell/Jamfile
405@@ -26,8 +26,11 @@ if ! $(HOST_PLATFORM_BEOS_COMPATIBLE) {
406 fsShellCommandLibs = $(HOST_NETWORK_LIBS) ;
407 }
408
409+UseHeaders [ FDirName $(HAIKU_TOP) headers build ] : true ;
410+
411 if ! $(HOST_PLATFORM_BEOS_COMPATIBLE) {
412 UseHeaders [ FDirName $(HAIKU_TOP) headers build os ] : true ;
413+ UseHeaders [ FDirName $(HAIKU_TOP) headers build os support ] : true ;
414 }
415
416 UsePrivateHeaders shared storage fs_shell ;
417@@ -50,6 +53,8 @@ BuildPlatformMergeObject <build>btrfs.o : $(btrfsSources) ;
418
419 BuildPlatformMain <build>btrfs_shell
420 :
421+ additional_commands.cpp
422+ command_cat.cpp
423 :
424 <build>btrfs.o
425 <build>fs_shell.a $(libHaikuCompat) $(HOST_LIBSUPC++) $(HOST_LIBSTDC++)
426diff --git a/src/tools/btrfs_shell/additional_commands.cpp b/src/tools/btrfs_shell/additional_commands.cpp
427new file mode 100644
428index 0000000..82a1f12
429--- /dev/null
430+++ b/src/tools/btrfs_shell/additional_commands.cpp
431@@ -0,0 +1,19 @@
432+#include "fssh.h"
433+
434+#include "command_cat.h"
435+
436+
437+namespace FSShell {
438+
439+
440+void
441+register_additional_commands()
442+{
443+ CommandManager::Default()->AddCommands(
444+ command_cat, "cat", "concatenate file(s) to stdout",
445+ NULL
446+ );
447+}
448+
449+
450+} // namespace FSShell
451diff --git a/src/tools/btrfs_shell/command_cat.cpp b/src/tools/btrfs_shell/command_cat.cpp
452new file mode 100644
453index 0000000..6601611
454--- /dev/null
455+++ b/src/tools/btrfs_shell/command_cat.cpp
456@@ -0,0 +1,67 @@
457+#include <stdio.h>
458+#include <stdlib.h>
459+
460+#include "syscalls.h"
461+#include "system_dependencies.h"
462+
463+
464+namespace FSShell {
465+
466+
467+fssh_status_t
468+command_cat(int argc, const char* const* argv)
469+{
470+ long numBytes = 10;
471+ int fileStart = 1;
472+ if (argc == 2 && !strcmp(argv[1], "--help")) {
473+ printf(
474+ "Usage: %s [ -n ] [FILE]...\n"
475+ "\t -n\tNumber of bytes to read\n",
476+ argv[0]
477+ );
478+ return FSSH_B_OK;
479+ }
480+
481+ if (argc < 2) {
482+ //get input from stdin and print to stdout
483+ return FSSH_B_OK;
484+ }
485+
486+ if (argc > 3 && !strcmp(argv[1], "-n")) {
487+ fileStart += 2;
488+ numBytes = strtol(argv[2], NULL, 10);
489+ }
490+
491+
492+ const char* const* files = argv + fileStart;
493+ for (; *files; files++) {
494+ const char* file = *files;
495+ int fd = _kern_open(-1, file, O_RDONLY, O_RDONLY);
496+ if (fd < 0) {
497+ fssh_dprintf("Error: %s\n", fssh_strerror(fd));
498+ return FSSH_B_BAD_VALUE;
499+ }
500+
501+ char buffer[numBytes + 1];
502+ if (buffer == NULL) {
503+ fssh_dprintf("Error: No memory\n");
504+ _kern_close(fd);
505+ return FSSH_B_NO_MEMORY;
506+ }
507+
508+ if (_kern_read(fd, 0, buffer, numBytes) != numBytes) {
509+ fssh_dprintf("Error: fail to read, length: %i\n", numBytes);
510+ _kern_close(fd);
511+ return FSSH_B_BAD_VALUE;
512+ }
513+
514+ _kern_close(fd);
515+ buffer[numBytes] = '\0';
516+ printf("%s\n", buffer);
517+ }
518+
519+ return FSSH_B_OK;
520+}
521+
522+
523+} // namespace FSShell
524diff --git a/src/tools/btrfs_shell/command_cat.h b/src/tools/btrfs_shell/command_cat.h
525new file mode 100644
526index 0000000..a86fd78
527--- /dev/null
528+++ b/src/tools/btrfs_shell/command_cat.h
529@@ -0,0 +1,17 @@
530+#ifndef COMMAND_CAT_H
531+#define COMMAND_CAT_H
532+
533+
534+#include "fssh_types.h"
535+
536+
537+namespace FSShell {
538+
539+
540+fssh_status_t command_cat(int argc, const char* const* argv);
541+
542+
543+} // namespace FSShell
544+
545+
546+#endif // COMMAND_CAT_H
547--
5482.7.0
549
550
551From cbafb7ff38c2d2fc1b2b29280bea97c269af5f76 Mon Sep 17 00:00:00 2001
552From: hyche <cvghy116@gmail.com>
553Date: Fri, 9 Jun 2017 16:09:35 +0700
554Subject: [PATCH 03/36] BTRFS: * Removed struct keyword for declaring variable.
555 * Renamed BPlusTree to BTree because BtrFS use a variant of BTree not B+Tree.
556
557---
558 .../kernel/file_systems/btrfs/Attribute.cpp | 2 +-
559 .../kernel/file_systems/btrfs/AttributeIterator.h | 2 +-
560 .../kernel/file_systems/btrfs/BPlusTree.cpp | 292 ---------------------
561 src/add-ons/kernel/file_systems/btrfs/BPlusTree.h | 134 ----------
562 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 292 +++++++++++++++++++++
563 src/add-ons/kernel/file_systems/btrfs/BTree.h | 134 ++++++++++
564 src/add-ons/kernel/file_systems/btrfs/Chunk.cpp | 14 +-
565 src/add-ons/kernel/file_systems/btrfs/Chunk.h | 4 +-
566 .../file_systems/btrfs/DirectoryIterator.cpp | 6 +-
567 .../kernel/file_systems/btrfs/DirectoryIterator.h | 2 +-
568 src/add-ons/kernel/file_systems/btrfs/Inode.cpp | 14 +-
569 src/add-ons/kernel/file_systems/btrfs/Inode.h | 2 +-
570 src/add-ons/kernel/file_systems/btrfs/Jamfile | 2 +-
571 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 30 +--
572 src/add-ons/kernel/file_systems/btrfs/Volume.h | 18 +-
573 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 14 +-
574 src/tools/btrfs_shell/Jamfile | 2 +-
575 17 files changed, 482 insertions(+), 482 deletions(-)
576 delete mode 100644 src/add-ons/kernel/file_systems/btrfs/BPlusTree.cpp
577 delete mode 100644 src/add-ons/kernel/file_systems/btrfs/BPlusTree.h
578 create mode 100644 src/add-ons/kernel/file_systems/btrfs/BTree.cpp
579 create mode 100644 src/add-ons/kernel/file_systems/btrfs/BTree.h
580
581diff --git a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
582index d701a2a..ecb25ac 100644
583--- a/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
584+++ b/src/add-ons/kernel/file_systems/btrfs/Attribute.cpp
585@@ -9,7 +9,7 @@
586
587
588 #include "Attribute.h"
589-#include "BPlusTree.h"
590+#include "BTree.h"
591 #include "CRCTable.h"
592 #include "Utility.h"
593
594diff --git a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.h b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.h
595index d1f60c5..b9491f4 100644
596--- a/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.h
597+++ b/src/add-ons/kernel/file_systems/btrfs/AttributeIterator.h
598@@ -6,7 +6,7 @@
599 #define ATTRIBUTEITERATOR_H
600
601
602-#include "BPlusTree.h"
603+#include "BTree.h"
604 #include "Inode.h"
605
606
607diff --git a/src/add-ons/kernel/file_systems/btrfs/BPlusTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BPlusTree.cpp
608deleted file mode 100644
609index af8a031..0000000
610--- a/src/add-ons/kernel/file_systems/btrfs/BPlusTree.cpp
611+++ /dev/null
612@@ -1,292 +0,0 @@
613-/*
614- * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
615- * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
616- * This file may be used under the terms of the MIT License.
617- */
618-
619-
620-//! B+Tree implementation
621-
622-
623-#include "BPlusTree.h"
624-#include "CachedBlock.h"
625-
626-
627-//#define TRACE_BTRFS
628-#ifdef TRACE_BTRFS
629-# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
630-#else
631-# define TRACE(x...) ;
632-#endif
633-# define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
634-
635-
636-BPlusTree::BPlusTree(Volume* volume, struct btrfs_stream* stream)
637- :
638- fStream(stream),
639- fRootBlock(0),
640- fVolume(volume)
641-{
642- mutex_init(&fIteratorLock, "btrfs b+tree iterator");
643-}
644-
645-
646-BPlusTree::BPlusTree(Volume* volume, fsblock_t rootBlock)
647- :
648- fStream(NULL),
649- fRootBlock(rootBlock),
650- fVolume(volume)
651-{
652- mutex_init(&fIteratorLock, "btrfs b+tree iterator");
653-}
654-
655-
656-BPlusTree::~BPlusTree()
657-{
658- // if there are any TreeIterators left, we need to stop them
659- // (can happen when the tree's inode gets deleted while
660- // traversing the tree - a TreeIterator doesn't lock the inode)
661- mutex_lock(&fIteratorLock);
662-
663- SinglyLinkedList<TreeIterator>::Iterator iterator
664- = fIterators.GetIterator();
665- while (iterator.HasNext())
666- iterator.Next()->Stop();
667- mutex_destroy(&fIteratorLock);
668-}
669-
670-
671-int32
672-BPlusTree::_CompareKeys(struct btrfs_key& key1, struct btrfs_key& key2)
673-{
674- if (key1.ObjectID() > key2.ObjectID())
675- return 1;
676- if (key1.ObjectID() < key2.ObjectID())
677- return -1;
678- if (key1.Type() > key2.Type())
679- return 1;
680- if (key1.Type() < key2.Type())
681- return -1;
682- if (key1.Offset() > key2.Offset())
683- return 1;
684- if (key1.Offset() < key2.Offset())
685- return -1;
686- return 0;
687-}
688-
689-
690-/*! Searches the key in the tree, and stores the allocated found item in
691- _value, if successful.
692- Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
693- It can also return other errors to indicate that something went wrong.
694-*/
695-status_t
696-BPlusTree::_Find(struct btrfs_key& key, void** _value, size_t* _size,
697- bplustree_traversing type)
698-{
699- TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
700- key.ObjectID(), key.Type(), key.Offset());
701- btrfs_stream* stream = fStream;
702- CachedBlock cached(fVolume);
703- fsblock_t physical;
704- if (stream == NULL) {
705- if (fVolume->FindBlock(fRootBlock, physical) != B_OK) {
706- ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
707- return B_ERROR;
708- }
709- stream = (btrfs_stream*)cached.SetTo(physical);
710- }
711-
712- while (stream->header.Level() != 0) {
713- TRACE("Find() level %d\n", stream->header.Level());
714- uint32 i = 1;
715- for (; i < stream->header.ItemCount(); i++) {
716- int32 comp = _CompareKeys(stream->index[i].key, key);
717- TRACE("Find() found index %" B_PRIu32 " at %" B_PRId64 " comp %"
718- B_PRId32 "\n", i, stream->index[i].BlockNum(), comp);
719- if (comp < 0)
720- continue;
721- if (comp > 0 || type == BPLUSTREE_BACKWARD)
722- break;
723- }
724- TRACE("Find() getting index %" B_PRIu32 " at %" B_PRId64 "\n", i - 1,
725- stream->index[i - 1].BlockNum());
726-
727- if (fVolume->FindBlock(stream->index[i - 1].BlockNum(), physical)
728- != B_OK) {
729- ERROR("Find() unmapped block %" B_PRId64 "\n",
730- stream->index[i - 1].BlockNum());
731- return B_ERROR;
732- }
733- stream = (btrfs_stream*)cached.SetTo(physical);
734- }
735-
736- uint32 i;
737-#ifdef TRACE_BTRFS
738- TRACE("Find() dump count %" B_PRId32 "\n", stream->header.ItemCount());
739- for (i = 0; i < stream->header.ItemCount(); i++) {
740- int32 comp = _CompareKeys(key, stream->entries[i].key);
741- TRACE("Find() dump %" B_PRIu32 " %" B_PRIu32 " offset %" B_PRId64
742- " comp %" B_PRId32 "\n", stream->entries[i].Offset(),
743- stream->entries[i].Size(), stream->entries[i].key.Offset(), comp);
744- }
745-#endif
746-
747- for (i = 0; i < stream->header.ItemCount(); i++) {
748- int32 comp = _CompareKeys(key, stream->entries[i].key);
749- TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 " oid %" B_PRId64
750- " type %d offset %" B_PRId64 " comp %" B_PRId32 "\n",
751- stream->entries[i].Offset(), stream->entries[i].Size(),
752- stream->entries[i].key.ObjectID(), stream->entries[i].key.Type(),
753- stream->entries[i].key.Offset(), comp);
754- if (comp == 0)
755- break;
756- if (comp < 0 && i > 0) {
757- if (type == BPLUSTREE_EXACT)
758- return B_ENTRY_NOT_FOUND;
759- if (type == BPLUSTREE_BACKWARD)
760- i--;
761- break;
762- }
763- }
764-
765- if (i == stream->header.ItemCount()) {
766- if (type == BPLUSTREE_BACKWARD)
767- i--;
768- else
769- return B_ENTRY_NOT_FOUND;
770- }
771-
772- if (i < stream->header.ItemCount()
773- && stream->entries[i].key.Type() == key.Type()) {
774- TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
775- stream->entries[i].Offset(), stream->entries[i].Size());
776-
777- if (_value != NULL) {
778- *_value = malloc(stream->entries[i].Size());
779- uint32 totalOffset = stream->entries[i].Offset() + sizeof(btrfs_header);
780-
781-
782- if ((fVolume->BlockSize() - totalOffset % fVolume->BlockSize())
783- >= stream->entries[i].Size()) {
784- //If there is enough space for *_value
785- memcpy(*_value, ((uint8*)cached.SetTo(physical
786- + totalOffset / fVolume->BlockSize())
787- + totalOffset % fVolume->BlockSize()),
788- stream->entries[i].Size());
789- } else {
790- read_pos(fVolume->Device(), physical
791- * fVolume->BlockSize() + totalOffset,
792- *_value, stream->entries[i].Size());
793- }
794-
795- key.SetOffset(stream->entries[i].key.Offset());
796- if (_size != NULL)
797- *_size = stream->entries[i].Size();
798- }
799- return B_OK;
800- }
801-
802-
803- TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n", key.Offset(),
804- key.ObjectID());
805-
806- return B_ENTRY_NOT_FOUND;
807-}
808-
809-
810-status_t
811-BPlusTree::FindNext(struct btrfs_key& key, void** _value, size_t* _size)
812-{
813- return _Find(key, _value, _size, BPLUSTREE_FORWARD);
814-}
815-
816-
817-status_t
818-BPlusTree::FindPrevious(struct btrfs_key& key, void** _value, size_t* _size)
819-{
820- return _Find(key, _value, _size, BPLUSTREE_BACKWARD);
821-}
822-
823-
824-status_t
825-BPlusTree::FindExact(struct btrfs_key& key, void** _value, size_t* _size)
826-{
827- return _Find(key, _value, _size, BPLUSTREE_EXACT);
828-}
829-
830-
831-void
832-BPlusTree::_AddIterator(TreeIterator* iterator)
833-{
834- MutexLocker _(fIteratorLock);
835- fIterators.Add(iterator);
836-}
837-
838-
839-void
840-BPlusTree::_RemoveIterator(TreeIterator* iterator)
841-{
842- MutexLocker _(fIteratorLock);
843- fIterators.Remove(iterator);
844-}
845-
846-
847-// #pragma mark -
848-
849-
850-TreeIterator::TreeIterator(BPlusTree* tree, struct btrfs_key& key)
851- :
852- fTree(tree),
853- fCurrentKey(key)
854-{
855- Rewind();
856- tree->_AddIterator(this);
857-}
858-
859-
860-TreeIterator::~TreeIterator()
861-{
862- if (fTree)
863- fTree->_RemoveIterator(this);
864-}
865-
866-
867-/*! Iterates through the tree in the specified direction.
868-*/
869-status_t
870-TreeIterator::Traverse(bplustree_traversing direction, struct btrfs_key& key,
871- void** value, size_t* size)
872-{
873- if (fTree == NULL)
874- return B_INTERRUPTED;
875-
876- fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
877- status_t status = fTree->_Find(fCurrentKey, value, size,
878- direction);
879- if (status != B_OK) {
880- TRACE("TreeIterator::Traverse() Find failed\n");
881- return B_ENTRY_NOT_FOUND;
882- }
883-
884- return B_OK;
885-}
886-
887-
888-/*! just sets the current key in the iterator.
889-*/
890-status_t
891-TreeIterator::Find(struct btrfs_key& key)
892-{
893- if (fTree == NULL)
894- return B_INTERRUPTED;
895- fCurrentKey = key;
896- return B_OK;
897-}
898-
899-
900-void
901-TreeIterator::Stop()
902-{
903- fTree = NULL;
904-}
905diff --git a/src/add-ons/kernel/file_systems/btrfs/BPlusTree.h b/src/add-ons/kernel/file_systems/btrfs/BPlusTree.h
906deleted file mode 100644
907index a9e7ee2..0000000
908--- a/src/add-ons/kernel/file_systems/btrfs/BPlusTree.h
909+++ /dev/null
910@@ -1,134 +0,0 @@
911-/*
912- * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
913- * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
914- * This file may be used under the terms of the MIT License.
915- */
916-#ifndef B_PLUS_TREE_H
917-#define B_PLUS_TREE_H
918-
919-
920-#include "btrfs.h"
921-#include "Volume.h"
922-
923-
924-#define BPLUSTREE_NULL -1LL
925-#define BPLUSTREE_FREE -2LL
926-
927-
928-enum bplustree_traversing {
929- BPLUSTREE_FORWARD = 1,
930- BPLUSTREE_EXACT = 0,
931- BPLUSTREE_BACKWARD = -1,
932-
933- BPLUSTREE_BEGIN = 0,
934- BPLUSTREE_END = -1
935-};
936-
937-
938-// #pragma mark - in-memory structures
939-
940-
941-template<class T> class Stack;
942-class TreeIterator;
943-
944-
945-// needed for searching (utilizing a stack)
946-struct node_and_key {
947- off_t nodeOffset;
948- uint16 keyIndex;
949-};
950-
951-
952-class BPlusTree {
953-public:
954- BPlusTree(Volume* volume,
955- struct btrfs_stream* stream);
956- BPlusTree(Volume* volume,
957- fsblock_t rootBlock);
958- ~BPlusTree();
959- status_t FindExact(struct btrfs_key& key, void** value,
960- size_t* size = NULL);
961- status_t FindNext(struct btrfs_key& key, void** value,
962- size_t* size = NULL);
963- status_t FindPrevious(struct btrfs_key& key, void** value,
964- size_t* size = NULL);
965-
966-private:
967- BPlusTree(const BPlusTree& other);
968- BPlusTree& operator=(const BPlusTree& other);
969- // no implementation
970-
971- int32 _CompareKeys(struct btrfs_key& key1,
972- struct btrfs_key& key2);
973- status_t _Find(struct btrfs_key& key, void** value,
974- size_t* size, bplustree_traversing type);
975- void _AddIterator(TreeIterator* iterator);
976- void _RemoveIterator(TreeIterator* iterator);
977-private:
978- friend class TreeIterator;
979-
980- struct btrfs_stream* fStream;
981- fsblock_t fRootBlock;
982- Volume* fVolume;
983- mutex fIteratorLock;
984- SinglyLinkedList<TreeIterator> fIterators;
985-};
986-
987-
988-class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
989-public:
990- TreeIterator(BPlusTree* tree, struct btrfs_key& key);
991- ~TreeIterator();
992-
993- status_t Traverse(bplustree_traversing direction,
994- struct btrfs_key& key, void** value,
995- size_t* size = NULL);
996- status_t Find(struct btrfs_key& key);
997-
998- status_t Rewind();
999- status_t GetNextEntry(struct btrfs_key& key, void** value,
1000- size_t* size = NULL);
1001- status_t GetPreviousEntry(struct btrfs_key& key, void** value,
1002- size_t* size = NULL);
1003-
1004- BPlusTree* Tree() const { return fTree; }
1005-
1006-private:
1007- friend class BPlusTree;
1008-
1009- // called by BPlusTree
1010- void Stop();
1011-
1012-private:
1013- BPlusTree* fTree;
1014- struct btrfs_key fCurrentKey;
1015-};
1016-
1017-
1018-// #pragma mark - TreeIterator inline functions
1019-
1020-
1021-inline status_t
1022-TreeIterator::Rewind()
1023-{
1024- fCurrentKey.SetOffset(BPLUSTREE_BEGIN);
1025- return B_OK;
1026-}
1027-
1028-
1029-inline status_t
1030-TreeIterator::GetNextEntry(struct btrfs_key& key, void** value, size_t* size)
1031-{
1032- return Traverse(BPLUSTREE_FORWARD, key, value, size);
1033-}
1034-
1035-
1036-inline status_t
1037-TreeIterator::GetPreviousEntry(struct btrfs_key& key, void** value,
1038- size_t* size)
1039-{
1040- return Traverse(BPLUSTREE_BACKWARD, key, value, size);
1041-}
1042-
1043-
1044-#endif // B_PLUS_TREE_H
1045diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1046new file mode 100644
1047index 0000000..cdacde3
1048--- /dev/null
1049+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1050@@ -0,0 +1,292 @@
1051+/*
1052+ * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
1053+ * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
1054+ * This file may be used under the terms of the MIT License.
1055+ */
1056+
1057+
1058+//! BTree implementation
1059+
1060+
1061+#include "BTree.h"
1062+#include "CachedBlock.h"
1063+
1064+
1065+//#define TRACE_BTRFS
1066+#ifdef TRACE_BTRFS
1067+# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
1068+#else
1069+# define TRACE(x...) ;
1070+#endif
1071+# define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
1072+
1073+
1074+BTree::BTree(Volume* volume, btrfs_stream* stream)
1075+ :
1076+ fStream(stream),
1077+ fRootBlock(0),
1078+ fVolume(volume)
1079+{
1080+ mutex_init(&fIteratorLock, "btrfs b+tree iterator");
1081+}
1082+
1083+
1084+BTree::BTree(Volume* volume, fsblock_t rootBlock)
1085+ :
1086+ fStream(NULL),
1087+ fRootBlock(rootBlock),
1088+ fVolume(volume)
1089+{
1090+ mutex_init(&fIteratorLock, "btrfs b+tree iterator");
1091+}
1092+
1093+
1094+BTree::~BTree()
1095+{
1096+ // if there are any TreeIterators left, we need to stop them
1097+ // (can happen when the tree's inode gets deleted while
1098+ // traversing the tree - a TreeIterator doesn't lock the inode)
1099+ mutex_lock(&fIteratorLock);
1100+
1101+ SinglyLinkedList<TreeIterator>::Iterator iterator
1102+ = fIterators.GetIterator();
1103+ while (iterator.HasNext())
1104+ iterator.Next()->Stop();
1105+ mutex_destroy(&fIteratorLock);
1106+}
1107+
1108+
1109+int32
1110+BTree::_CompareKeys(btrfs_key& key1, btrfs_key& key2)
1111+{
1112+ if (key1.ObjectID() > key2.ObjectID())
1113+ return 1;
1114+ if (key1.ObjectID() < key2.ObjectID())
1115+ return -1;
1116+ if (key1.Type() > key2.Type())
1117+ return 1;
1118+ if (key1.Type() < key2.Type())
1119+ return -1;
1120+ if (key1.Offset() > key2.Offset())
1121+ return 1;
1122+ if (key1.Offset() < key2.Offset())
1123+ return -1;
1124+ return 0;
1125+}
1126+
1127+
1128+/*! Searches the key in the tree, and stores the allocated found item in
1129+ _value, if successful.
1130+ Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
1131+ It can also return other errors to indicate that something went wrong.
1132+*/
1133+status_t
1134+BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
1135+ btree_traversing type)
1136+{
1137+ TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
1138+ key.ObjectID(), key.Type(), key.Offset());
1139+ btrfs_stream* stream = fStream;
1140+ CachedBlock cached(fVolume);
1141+ fsblock_t physical;
1142+ if (stream == NULL) {
1143+ if (fVolume->FindBlock(fRootBlock, physical) != B_OK) {
1144+ ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
1145+ return B_ERROR;
1146+ }
1147+ stream = (btrfs_stream*)cached.SetTo(physical);
1148+ }
1149+
1150+ while (stream->header.Level() != 0) {
1151+ TRACE("Find() level %d\n", stream->header.Level());
1152+ uint32 i = 1;
1153+ for (; i < stream->header.ItemCount(); i++) {
1154+ int32 comp = _CompareKeys(stream->index[i].key, key);
1155+ TRACE("Find() found index %" B_PRIu32 " at %" B_PRId64 " comp %"
1156+ B_PRId32 "\n", i, stream->index[i].BlockNum(), comp);
1157+ if (comp < 0)
1158+ continue;
1159+ if (comp > 0 || type == BTREE_BACKWARD)
1160+ break;
1161+ }
1162+ TRACE("Find() getting index %" B_PRIu32 " at %" B_PRId64 "\n", i - 1,
1163+ stream->index[i - 1].BlockNum());
1164+
1165+ if (fVolume->FindBlock(stream->index[i - 1].BlockNum(), physical)
1166+ != B_OK) {
1167+ ERROR("Find() unmapped block %" B_PRId64 "\n",
1168+ stream->index[i - 1].BlockNum());
1169+ return B_ERROR;
1170+ }
1171+ stream = (btrfs_stream*)cached.SetTo(physical);
1172+ }
1173+
1174+ uint32 i;
1175+#ifdef TRACE_BTRFS
1176+ TRACE("Find() dump count %" B_PRId32 "\n", stream->header.ItemCount());
1177+ for (i = 0; i < stream->header.ItemCount(); i++) {
1178+ int32 comp = _CompareKeys(key, stream->entries[i].key);
1179+ TRACE("Find() dump %" B_PRIu32 " %" B_PRIu32 " offset %" B_PRId64
1180+ " comp %" B_PRId32 "\n", stream->entries[i].Offset(),
1181+ stream->entries[i].Size(), stream->entries[i].key.Offset(), comp);
1182+ }
1183+#endif
1184+
1185+ for (i = 0; i < stream->header.ItemCount(); i++) {
1186+ int32 comp = _CompareKeys(key, stream->entries[i].key);
1187+ TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 " oid %" B_PRId64
1188+ " type %d offset %" B_PRId64 " comp %" B_PRId32 "\n",
1189+ stream->entries[i].Offset(), stream->entries[i].Size(),
1190+ stream->entries[i].key.ObjectID(), stream->entries[i].key.Type(),
1191+ stream->entries[i].key.Offset(), comp);
1192+ if (comp == 0)
1193+ break;
1194+ if (comp < 0 && i > 0) {
1195+ if (type == BTREE_EXACT)
1196+ return B_ENTRY_NOT_FOUND;
1197+ if (type == BTREE_BACKWARD)
1198+ i--;
1199+ break;
1200+ }
1201+ }
1202+
1203+ if (i == stream->header.ItemCount()) {
1204+ if (type == BTREE_BACKWARD)
1205+ i--;
1206+ else
1207+ return B_ENTRY_NOT_FOUND;
1208+ }
1209+
1210+ if (i < stream->header.ItemCount()
1211+ && stream->entries[i].key.Type() == key.Type()) {
1212+ TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
1213+ stream->entries[i].Offset(), stream->entries[i].Size());
1214+
1215+ if (_value != NULL) {
1216+ *_value = malloc(stream->entries[i].Size());
1217+ uint32 totalOffset = stream->entries[i].Offset() + sizeof(btrfs_header);
1218+
1219+
1220+ if ((fVolume->BlockSize() - totalOffset % fVolume->BlockSize())
1221+ >= stream->entries[i].Size()) {
1222+ //If there is enough space for *_value
1223+ memcpy(*_value, ((uint8*)cached.SetTo(physical
1224+ + totalOffset / fVolume->BlockSize())
1225+ + totalOffset % fVolume->BlockSize()),
1226+ stream->entries[i].Size());
1227+ } else {
1228+ read_pos(fVolume->Device(), physical
1229+ * fVolume->BlockSize() + totalOffset,
1230+ *_value, stream->entries[i].Size());
1231+ }
1232+
1233+ key.SetOffset(stream->entries[i].key.Offset());
1234+ if (_size != NULL)
1235+ *_size = stream->entries[i].Size();
1236+ }
1237+ return B_OK;
1238+ }
1239+
1240+
1241+ TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n", key.Offset(),
1242+ key.ObjectID());
1243+
1244+ return B_ENTRY_NOT_FOUND;
1245+}
1246+
1247+
1248+status_t
1249+BTree::FindNext(btrfs_key& key, void** _value, size_t* _size)
1250+{
1251+ return _Find(key, _value, _size, BTREE_FORWARD);
1252+}
1253+
1254+
1255+status_t
1256+BTree::FindPrevious(btrfs_key& key, void** _value, size_t* _size)
1257+{
1258+ return _Find(key, _value, _size, BTREE_BACKWARD);
1259+}
1260+
1261+
1262+status_t
1263+BTree::FindExact(btrfs_key& key, void** _value, size_t* _size)
1264+{
1265+ return _Find(key, _value, _size, BTREE_EXACT);
1266+}
1267+
1268+
1269+void
1270+BTree::_AddIterator(TreeIterator* iterator)
1271+{
1272+ MutexLocker _(fIteratorLock);
1273+ fIterators.Add(iterator);
1274+}
1275+
1276+
1277+void
1278+BTree::_RemoveIterator(TreeIterator* iterator)
1279+{
1280+ MutexLocker _(fIteratorLock);
1281+ fIterators.Remove(iterator);
1282+}
1283+
1284+
1285+// #pragma mark -
1286+
1287+
1288+TreeIterator::TreeIterator(BTree* tree, btrfs_key& key)
1289+ :
1290+ fTree(tree),
1291+ fCurrentKey(key)
1292+{
1293+ Rewind();
1294+ tree->_AddIterator(this);
1295+}
1296+
1297+
1298+TreeIterator::~TreeIterator()
1299+{
1300+ if (fTree)
1301+ fTree->_RemoveIterator(this);
1302+}
1303+
1304+
1305+/*! Iterates through the tree in the specified direction.
1306+*/
1307+status_t
1308+TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
1309+ void** value, size_t* size)
1310+{
1311+ if (fTree == NULL)
1312+ return B_INTERRUPTED;
1313+
1314+ fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
1315+ status_t status = fTree->_Find(fCurrentKey, value, size,
1316+ direction);
1317+ if (status != B_OK) {
1318+ TRACE("TreeIterator::Traverse() Find failed\n");
1319+ return B_ENTRY_NOT_FOUND;
1320+ }
1321+
1322+ return B_OK;
1323+}
1324+
1325+
1326+/*! just sets the current key in the iterator.
1327+*/
1328+status_t
1329+TreeIterator::Find(btrfs_key& key)
1330+{
1331+ if (fTree == NULL)
1332+ return B_INTERRUPTED;
1333+ fCurrentKey = key;
1334+ return B_OK;
1335+}
1336+
1337+
1338+void
1339+TreeIterator::Stop()
1340+{
1341+ fTree = NULL;
1342+}
1343diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
1344new file mode 100644
1345index 0000000..56a8b6d
1346--- /dev/null
1347+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
1348@@ -0,0 +1,134 @@
1349+/*
1350+ * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
1351+ * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
1352+ * This file may be used under the terms of the MIT License.
1353+ */
1354+#ifndef B_PLUS_TREE_H
1355+#define B_PLUS_TREE_H
1356+
1357+
1358+#include "btrfs.h"
1359+#include "Volume.h"
1360+
1361+
1362+#define BTREE_NULL -1LL
1363+#define BTREE_FREE -2LL
1364+
1365+
1366+enum btree_traversing {
1367+ BTREE_FORWARD = 1,
1368+ BTREE_EXACT = 0,
1369+ BTREE_BACKWARD = -1,
1370+
1371+ BTREE_BEGIN = 0,
1372+ BTREE_END = -1
1373+};
1374+
1375+
1376+// #pragma mark - in-memory structures
1377+
1378+
1379+template<class T> class Stack;
1380+class TreeIterator;
1381+
1382+
1383+// needed for searching (utilizing a stack)
1384+struct node_and_key {
1385+ off_t nodeOffset;
1386+ uint16 keyIndex;
1387+};
1388+
1389+
1390+class BTree {
1391+public:
1392+ BTree(Volume* volume,
1393+ btrfs_stream* stream);
1394+ BTree(Volume* volume,
1395+ fsblock_t rootBlock);
1396+ ~BTree();
1397+ status_t FindExact(btrfs_key& key, void** value,
1398+ size_t* size = NULL);
1399+ status_t FindNext(btrfs_key& key, void** value,
1400+ size_t* size = NULL);
1401+ status_t FindPrevious(btrfs_key& key, void** value,
1402+ size_t* size = NULL);
1403+
1404+private:
1405+ BTree(const BTree& other);
1406+ BTree& operator=(const BTree& other);
1407+ // no implementation
1408+
1409+ int32 _CompareKeys(btrfs_key& key1,
1410+ btrfs_key& key2);
1411+ status_t _Find(btrfs_key& key, void** value,
1412+ size_t* size, btree_traversing type);
1413+ void _AddIterator(TreeIterator* iterator);
1414+ void _RemoveIterator(TreeIterator* iterator);
1415+private:
1416+ friend class TreeIterator;
1417+
1418+ btrfs_stream* fStream;
1419+ fsblock_t fRootBlock;
1420+ Volume* fVolume;
1421+ mutex fIteratorLock;
1422+ SinglyLinkedList<TreeIterator> fIterators;
1423+};
1424+
1425+
1426+class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
1427+public:
1428+ TreeIterator(BTree* tree, btrfs_key& key);
1429+ ~TreeIterator();
1430+
1431+ status_t Traverse(btree_traversing direction,
1432+ btrfs_key& key, void** value,
1433+ size_t* size = NULL);
1434+ status_t Find(btrfs_key& key);
1435+
1436+ status_t Rewind();
1437+ status_t GetNextEntry(btrfs_key& key, void** value,
1438+ size_t* size = NULL);
1439+ status_t GetPreviousEntry(btrfs_key& key, void** value,
1440+ size_t* size = NULL);
1441+
1442+ BTree* Tree() const { return fTree; }
1443+
1444+private:
1445+ friend class BTree;
1446+
1447+ // called by BTree
1448+ void Stop();
1449+
1450+private:
1451+ BTree* fTree;
1452+ btrfs_key fCurrentKey;
1453+};
1454+
1455+
1456+// #pragma mark - TreeIterator inline functions
1457+
1458+
1459+inline status_t
1460+TreeIterator::Rewind()
1461+{
1462+ fCurrentKey.SetOffset(BTREE_BEGIN);
1463+ return B_OK;
1464+}
1465+
1466+
1467+inline status_t
1468+TreeIterator::GetNextEntry(btrfs_key& key, void** value, size_t* size)
1469+{
1470+ return Traverse(BTREE_FORWARD, key, value, size);
1471+}
1472+
1473+
1474+inline status_t
1475+TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
1476+ size_t* size)
1477+{
1478+ return Traverse(BTREE_BACKWARD, key, value, size);
1479+}
1480+
1481+
1482+#endif // B_PLUS_TREE_H
1483diff --git a/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp b/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp
1484index f730baa..cba77ce 100644
1485--- a/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp
1486+++ b/src/add-ons/kernel/file_systems/btrfs/Chunk.cpp
1487@@ -19,21 +19,21 @@
1488 # define FATAL(x...) dprintf("\33[34mbtrfs:\33[0m " x)
1489
1490
1491-Chunk::Chunk(struct btrfs_chunk* chunk, fsblock_t offset)
1492+Chunk::Chunk(btrfs_chunk* chunk, fsblock_t offset)
1493 :
1494 fChunk(NULL),
1495 fInitStatus(B_OK)
1496 {
1497 fChunkOffset = offset;
1498- fChunk = (struct btrfs_chunk*)malloc(sizeof(struct btrfs_chunk)
1499- + chunk->StripeCount() * sizeof(struct btrfs_stripe));
1500+ fChunk = (btrfs_chunk*)malloc(sizeof(btrfs_chunk)
1501+ + chunk->StripeCount() * sizeof(btrfs_stripe));
1502 if (fChunk == NULL) {
1503 fInitStatus = B_NO_MEMORY;
1504 return;
1505 }
1506
1507- memcpy(fChunk, chunk, sizeof(struct btrfs_chunk)
1508- + chunk->StripeCount() * sizeof(struct btrfs_stripe));
1509+ memcpy(fChunk, chunk, sizeof(btrfs_chunk)
1510+ + chunk->StripeCount() * sizeof(btrfs_stripe));
1511
1512 TRACE("chunk[0] length %" B_PRIu64 " owner %" B_PRIu64 " stripe_length %"
1513 B_PRIu64 " type %" B_PRIu64 " stripe_count %u sub_stripes %u "
1514@@ -57,8 +57,8 @@ Chunk::~Chunk()
1515 uint32
1516 Chunk::Size() const
1517 {
1518- return sizeof(struct btrfs_chunk)
1519- + fChunk->StripeCount() * sizeof(struct btrfs_stripe);
1520+ return sizeof(btrfs_chunk)
1521+ + fChunk->StripeCount() * sizeof(btrfs_stripe);
1522 }
1523
1524
1525diff --git a/src/add-ons/kernel/file_systems/btrfs/Chunk.h b/src/add-ons/kernel/file_systems/btrfs/Chunk.h
1526index 4119dec..c1fbe49 100644
1527--- a/src/add-ons/kernel/file_systems/btrfs/Chunk.h
1528+++ b/src/add-ons/kernel/file_systems/btrfs/Chunk.h
1529@@ -14,7 +14,7 @@
1530
1531 class Chunk {
1532 public:
1533- Chunk(struct btrfs_chunk* chunk,
1534+ Chunk(btrfs_chunk* chunk,
1535 fsblock_t offset);
1536 ~Chunk();
1537 uint32 Size() const;
1538@@ -23,7 +23,7 @@ public:
1539 fsblock_t End() const
1540 { return fChunkOffset + fChunk->Length(); }
1541 private:
1542- struct btrfs_chunk* fChunk;
1543+ btrfs_chunk* fChunk;
1544 fsblock_t fChunkOffset;
1545 status_t fInitStatus;
1546 };
1547diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1548index e898d25..b19dabf 100644
1549--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1550+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.cpp
1551@@ -23,7 +23,7 @@ DirectoryIterator::DirectoryIterator(Inode* inode)
1552 fInode(inode),
1553 fIterator(NULL)
1554 {
1555- struct btrfs_key key;
1556+ btrfs_key key;
1557 key.SetType(BTRFS_KEY_TYPE_DIR_INDEX);
1558 key.SetObjectID(inode->ID());
1559 fIterator = new(std::nothrow) TreeIterator(inode->GetVolume()->FSTree(),
1560@@ -118,7 +118,7 @@ DirectoryIterator::Lookup(const char* name, size_t nameLength, ino_t* _id)
1561 }
1562
1563 uint32 hash = calculate_crc((uint32)~1, (uint8*)name, nameLength);
1564- struct btrfs_key key;
1565+ btrfs_key key;
1566 key.SetType(BTRFS_KEY_TYPE_DIR_ITEM);
1567 key.SetObjectID(fInode->ID());
1568 key.SetOffset(hash);
1569@@ -156,7 +156,7 @@ status_t
1570 DirectoryIterator::Rewind()
1571 {
1572 fIterator->Rewind();
1573- fOffset = BPLUSTREE_BEGIN;
1574+ fOffset = BTREE_BEGIN;
1575 return B_OK;
1576 }
1577
1578diff --git a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.h b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.h
1579index 069c9a0..086863d 100644
1580--- a/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.h
1581+++ b/src/add-ons/kernel/file_systems/btrfs/DirectoryIterator.h
1582@@ -6,7 +6,7 @@
1583 #define DIRECTORYITERATOR_H
1584
1585
1586-#include "BPlusTree.h"
1587+#include "BTree.h"
1588 #include "Inode.h"
1589
1590
1591diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
1592index 666000e..ef66d34 100644
1593--- a/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
1594+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.cpp
1595@@ -7,7 +7,7 @@
1596
1597
1598 #include "Inode.h"
1599-#include "BPlusTree.h"
1600+#include "BTree.h"
1601 #include "CachedBlock.h"
1602 #include "Utility.h"
1603
1604@@ -74,19 +74,19 @@ Inode::InitCheck()
1605 status_t
1606 Inode::UpdateNodeFromDisk()
1607 {
1608- struct btrfs_key search_key;
1609+ btrfs_key search_key;
1610 search_key.SetType(BTRFS_KEY_TYPE_INODE_ITEM);
1611 search_key.SetObjectID(fID);
1612 search_key.SetOffset(0);
1613
1614- struct btrfs_inode* node;
1615+ btrfs_inode* node;
1616 if (fVolume->FSTree()->FindExact(search_key, (void**)&node) != B_OK) {
1617 ERROR("Inode::UpdateNodeFromDisk(): Couldn't find inode %"
1618 B_PRIdINO "\n", fID);
1619 return B_ENTRY_NOT_FOUND;
1620 }
1621
1622- memcpy(&fNode, node, sizeof(struct btrfs_inode));
1623+ memcpy(&fNode, node, sizeof(btrfs_inode));
1624 free(node);
1625 return B_OK;
1626 }
1627@@ -107,7 +107,7 @@ Inode::CheckPermissions(int accessMode) const
1628 status_t
1629 Inode::FindBlock(off_t pos, off_t& physical, off_t* _length)
1630 {
1631- struct btrfs_key search_key;
1632+ btrfs_key search_key;
1633 search_key.SetType(BTRFS_KEY_TYPE_EXTENT_DATA);
1634 search_key.SetObjectID(fID);
1635 search_key.SetOffset(pos + 1);
1636@@ -162,7 +162,7 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
1637
1638 // the file cache doesn't seem to like non block aligned file offset
1639 // so we avoid the file cache for inline extents
1640- struct btrfs_key search_key;
1641+ btrfs_key search_key;
1642 search_key.SetType(BTRFS_KEY_TYPE_EXTENT_DATA);
1643 search_key.SetObjectID(fID);
1644 search_key.SetOffset(pos + 1);
1645@@ -288,7 +288,7 @@ Inode::ReadAt(off_t pos, uint8* buffer, size_t* _length)
1646 status_t
1647 Inode::FindParent(ino_t* id)
1648 {
1649- struct btrfs_key search_key;
1650+ btrfs_key search_key;
1651 search_key.SetType(BTRFS_KEY_TYPE_INODE_REF);
1652 search_key.SetObjectID(fID);
1653 search_key.SetOffset(-1);
1654diff --git a/src/add-ons/kernel/file_systems/btrfs/Inode.h b/src/add-ons/kernel/file_systems/btrfs/Inode.h
1655index 4182634..003baf4 100644
1656--- a/src/add-ons/kernel/file_systems/btrfs/Inode.h
1657+++ b/src/add-ons/kernel/file_systems/btrfs/Inode.h
1658@@ -78,7 +78,7 @@ private:
1659 void* fCache;
1660 void* fMap;
1661 status_t fInitStatus;
1662- struct btrfs_inode fNode;
1663+ btrfs_inode fNode;
1664 };
1665
1666
1667diff --git a/src/add-ons/kernel/file_systems/btrfs/Jamfile b/src/add-ons/kernel/file_systems/btrfs/Jamfile
1668index dc246b4..d408e55 100644
1669--- a/src/add-ons/kernel/file_systems/btrfs/Jamfile
1670+++ b/src/add-ons/kernel/file_systems/btrfs/Jamfile
1671@@ -12,7 +12,7 @@ KernelAddon btrfs :
1672 kernel_interface.cpp
1673 Attribute.cpp
1674 AttributeIterator.cpp
1675- BPlusTree.cpp
1676+ BTree.cpp
1677 Chunk.cpp
1678 CRCTable.cpp
1679 DirectoryIterator.cpp
1680diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1681index 4a459fa..ed1bd62 100644
1682--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1683+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1684@@ -9,7 +9,7 @@
1685
1686
1687 #include "Volume.h"
1688-#include "BPlusTree.h"
1689+#include "BTree.h"
1690 #include "CachedBlock.h"
1691 #include "Chunk.h"
1692 #include "Inode.h"
1693@@ -271,19 +271,19 @@ Volume::Mount(const char* deviceName, uint32 flags)
1694 uint8* start = (uint8*)&fSuperBlock.system_chunk_array[0];
1695 uint8* end = (uint8*)&fSuperBlock.system_chunk_array[2048];
1696 while (start < end) {
1697- struct btrfs_key* key = (struct btrfs_key*)start;
1698+ btrfs_key* key = (btrfs_key*)start;
1699 TRACE("system_chunk_array object_id 0x%" B_PRIx64 " offset 0x%"
1700 B_PRIx64 " type 0x%x\n", key->ObjectID(), key->Offset(),
1701 key->Type());
1702 if (key->Type() != BTRFS_KEY_TYPE_CHUNK_ITEM) {
1703 break;
1704 }
1705-
1706- struct btrfs_chunk* chunk = (struct btrfs_chunk*)(key + 1);
1707+
1708+ btrfs_chunk* chunk = (btrfs_chunk*)(key + 1);
1709 fChunk = new(std::nothrow) Chunk(chunk, key->Offset());
1710 if (fChunk == NULL)
1711 return B_ERROR;
1712- start += sizeof(struct btrfs_key) + fChunk->Size();
1713+ start += sizeof(btrfs_key) + fChunk->Size();
1714 }
1715
1716 TRACE("Volume::Mount() generation: %" B_PRIu64 "\n",
1717@@ -314,7 +314,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
1718
1719 TRACE("Volume::Mount(): Initialized block cache: %p\n", fBlockCache);
1720
1721- fChunkTree = new(std::nothrow) BPlusTree(this, fSuperBlock.ChunkRoot());
1722+ fChunkTree = new(std::nothrow) BTree(this, fSuperBlock.ChunkRoot());
1723 if (fChunkTree == NULL)
1724 return B_NO_MEMORY;
1725
1726@@ -328,22 +328,22 @@ Volume::Mount(const char* deviceName, uint32 flags)
1727 TRACE("Volume::Mount() log_root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
1728 fSuperBlock.LogRoot(), physical);
1729
1730- fRootTree = new(std::nothrow) BPlusTree(this, fSuperBlock.Root());
1731+ fRootTree = new(std::nothrow) BTree(this, fSuperBlock.Root());
1732 if (fRootTree == NULL)
1733 return B_NO_MEMORY;
1734 TRACE("Volume::Mount(): Searching extent root\n");
1735- struct btrfs_key search_key;
1736+ btrfs_key search_key;
1737 search_key.SetOffset(0);
1738 search_key.SetType(BTRFS_KEY_TYPE_ROOT_ITEM);
1739 search_key.SetObjectID(BTRFS_OBJECT_ID_EXTENT_TREE);
1740- struct btrfs_root* root;
1741+ btrfs_root* root;
1742 if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
1743 ERROR("Volume::Mount(): Couldn't find extent root\n");
1744 return B_ERROR;
1745 }
1746 TRACE("Volume::Mount(): Found extent root: %" B_PRIu64 "\n",
1747 root->BlockNum());
1748- fExtentTree = new(std::nothrow) BPlusTree(this, root->BlockNum());
1749+ fExtentTree = new(std::nothrow) BTree(this, root->BlockNum());
1750 free(root);
1751 if (fExtentTree == NULL)
1752 return B_NO_MEMORY;
1753@@ -355,7 +355,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
1754 return B_ERROR;
1755 }
1756 TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n", root->BlockNum());
1757- fFSTree = new(std::nothrow) BPlusTree(this, root->BlockNum());
1758+ fFSTree = new(std::nothrow) BTree(this, root->BlockNum());
1759 free(root);
1760 if (fFSTree == NULL)
1761 return B_NO_MEMORY;
1762@@ -368,7 +368,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
1763 }
1764 TRACE("Volume::Mount(): Found dev root: %" B_PRIu64 "\n",
1765 root->BlockNum());
1766- fDevTree = new(std::nothrow) BPlusTree(this, root->BlockNum());
1767+ fDevTree = new(std::nothrow) BTree(this, root->BlockNum());
1768 free(root);
1769 if (fDevTree == NULL)
1770 return B_NO_MEMORY;
1771@@ -381,7 +381,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
1772 }
1773 TRACE("Volume::Mount(): Found checksum root: %" B_PRIu64 "\n",
1774 root->BlockNum());
1775- fChecksumTree = new(std::nothrow) BPlusTree(this, root->BlockNum());
1776+ fChecksumTree = new(std::nothrow) BTree(this, root->BlockNum());
1777 free(root);
1778 if (fChecksumTree == NULL)
1779 return B_NO_MEMORY;
1780@@ -487,11 +487,11 @@ Volume::FindBlock(off_t logical, off_t& physical)
1781 return fChunk->FindBlock(logical, physical);
1782 }
1783
1784- struct btrfs_key search_key;
1785+ btrfs_key search_key;
1786 search_key.SetOffset(logical);
1787 search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
1788 search_key.SetObjectID(BTRFS_OBJECT_ID_CHUNK_TREE);
1789- struct btrfs_chunk* chunk;
1790+ btrfs_chunk* chunk;
1791 size_t chunk_length;
1792 status_t status = fChunkTree->FindPrevious(search_key, (void**)&chunk,
1793 &chunk_length);
1794diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.h b/src/add-ons/kernel/file_systems/btrfs/Volume.h
1795index 1171a25..e5b371f 100644
1796--- a/src/add-ons/kernel/file_systems/btrfs/Volume.h
1797+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.h
1798@@ -14,7 +14,7 @@ enum volume_flags {
1799 VOLUME_READ_ONLY = 0x0001
1800 };
1801
1802-class BPlusTree;
1803+class BTree;
1804 class Chunk;
1805 class Inode;
1806
1807@@ -38,8 +38,8 @@ public:
1808 { return fFSVolume ? fFSVolume->id : -1; }
1809 fs_volume* FSVolume() const { return fFSVolume; }
1810 const char* Name() const;
1811- BPlusTree* FSTree() const { return fFSTree; }
1812- BPlusTree* RootTree() const { return fRootTree; }
1813+ BTree* FSTree() const { return fFSTree; }
1814+ BTree* RootTree() const { return fRootTree; }
1815
1816 uint32 BlockSize() const { return fBlockSize; }
1817 btrfs_super_block& SuperBlock() { return fSuperBlock; }
1818@@ -68,12 +68,12 @@ private:
1819 Inode* fRootNode;
1820
1821 Chunk* fChunk;
1822- BPlusTree* fChunkTree;
1823- BPlusTree* fRootTree;
1824- BPlusTree* fDevTree;
1825- BPlusTree* fExtentTree;
1826- BPlusTree* fFSTree;
1827- BPlusTree* fChecksumTree;
1828+ BTree* fChunkTree;
1829+ BTree* fRootTree;
1830+ BTree* fDevTree;
1831+ BTree* fExtentTree;
1832+ BTree* fFSTree;
1833+ BTree* fChecksumTree;
1834 };
1835
1836
1837diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1838index 056aa0c..a329d47 100644
1839--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1840+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1841@@ -106,7 +106,7 @@ struct btrfs_chunk {
1842 uint32 sector_size;
1843 uint16 stripe_count;
1844 uint16 sub_stripes;
1845- struct btrfs_stripe stripes[0];
1846+ btrfs_stripe stripes[0];
1847 uint64 Length() const { return B_LENDIAN_TO_HOST_INT64(length); }
1848 uint64 Owner() const { return B_LENDIAN_TO_HOST_INT64(owner); }
1849 uint64 StripeLength() const
1850@@ -169,7 +169,7 @@ struct btrfs_super_block {
1851 uint8 root_level;
1852 uint8 chunk_root_level;
1853 uint8 log_root_level;
1854- struct btrfs_device device;
1855+ btrfs_device device;
1856 char label[256];
1857 uint64 reserved[32];
1858 uint8 system_chunk_array[2048];
1859@@ -206,10 +206,10 @@ struct btrfs_inode {
1860 uint64 flags;
1861 uint64 sequence;
1862 uint64 reserved[4];
1863- struct btrfs_timespec access_time;
1864- struct btrfs_timespec change_time;
1865- struct btrfs_timespec modification_time;
1866- struct btrfs_timespec creation_time;
1867+ btrfs_timespec access_time;
1868+ btrfs_timespec change_time;
1869+ btrfs_timespec modification_time;
1870+ btrfs_timespec creation_time;
1871 uint64 Generation() const { return B_LENDIAN_TO_HOST_INT64(generation); }
1872 uint64 Size() const { return B_LENDIAN_TO_HOST_INT64(size); }
1873 uint32 UserID() const { return B_LENDIAN_TO_HOST_INT32(uid); }
1874@@ -218,7 +218,7 @@ struct btrfs_inode {
1875 uint64 Flags() const { return B_LENDIAN_TO_HOST_INT64(flags); }
1876 uint64 Sequence() const { return B_LENDIAN_TO_HOST_INT64(sequence); }
1877 static void _DecodeTime(struct timespec& timespec,
1878- const struct btrfs_timespec& time)
1879+ const btrfs_timespec& time)
1880 {
1881 timespec.tv_sec = B_LENDIAN_TO_HOST_INT64(time.seconds);
1882 timespec.tv_nsec = B_LENDIAN_TO_HOST_INT32(time.nanoseconds);
1883diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
1884index 842b2b5..dcf071e 100644
1885--- a/src/tools/btrfs_shell/Jamfile
1886+++ b/src/tools/btrfs_shell/Jamfile
1887@@ -40,7 +40,7 @@ UseHeaders [ FDirName $(HAIKU_TOP) src tools fs_shell ] ;
1888 local btrfsSources =
1889 Attribute.cpp
1890 AttributeIterator.cpp
1891- BPlusTree.cpp
1892+ BTree.cpp
1893 Chunk.cpp
1894 CRCTable.cpp
1895 DirectoryIterator.cpp
1896--
18972.7.0
1898
1899
1900From 58a53c234cd3a32736256decda73743af235714c Mon Sep 17 00:00:00 2001
1901From: hyche <cvghy116@gmail.com>
1902Date: Fri, 9 Jun 2017 17:47:40 +0700
1903Subject: [PATCH 04/36] BTRFS: Refix ticket #12788 * Change block size to node
1904 size. Block is not always the same as sector.
1905
1906---
1907 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 19 +++----------------
1908 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 2 +-
1909 2 files changed, 4 insertions(+), 17 deletions(-)
1910
1911diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1912index cdacde3..85fda06 100644
1913--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1914+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
1915@@ -164,22 +164,9 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
1916
1917 if (_value != NULL) {
1918 *_value = malloc(stream->entries[i].Size());
1919- uint32 totalOffset = stream->entries[i].Offset() + sizeof(btrfs_header);
1920-
1921-
1922- if ((fVolume->BlockSize() - totalOffset % fVolume->BlockSize())
1923- >= stream->entries[i].Size()) {
1924- //If there is enough space for *_value
1925- memcpy(*_value, ((uint8*)cached.SetTo(physical
1926- + totalOffset / fVolume->BlockSize())
1927- + totalOffset % fVolume->BlockSize()),
1928- stream->entries[i].Size());
1929- } else {
1930- read_pos(fVolume->Device(), physical
1931- * fVolume->BlockSize() + totalOffset,
1932- *_value, stream->entries[i].Size());
1933- }
1934-
1935+ memcpy(*_value, ((uint8 *)&stream->entries[0]
1936+ + stream->entries[i].Offset()),
1937+ stream->entries[i].Size());
1938 key.SetOffset(stream->entries[i].key.Offset());
1939 if (_size != NULL)
1940 *_size = stream->entries[i].Size();
1941diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1942index a329d47..c0cf017 100644
1943--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1944+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
1945@@ -177,7 +177,7 @@ struct btrfs_super_block {
1946 bool IsValid();
1947 // implemented in Volume.cpp
1948 uint64 TotalSize() const { return B_LENDIAN_TO_HOST_INT64(total_size); }
1949- uint32 BlockSize() const { return B_LENDIAN_TO_HOST_INT32(sector_size); }
1950+ uint32 BlockSize() const { return B_LENDIAN_TO_HOST_INT32(node_size); }
1951 uint64 RootDirObjectID() const
1952 { return B_LENDIAN_TO_HOST_INT64(root_dir_object_id); }
1953 uint64 Generation() const
1954--
19552.7.0
1956
1957
1958From 1936f3ff416364fcda5515019e39cdfa7bfc4a83 Mon Sep 17 00:00:00 2001
1959From: hyche <cvghy116@gmail.com>
1960Date: Fri, 9 Jun 2017 17:50:13 +0700
1961Subject: [PATCH 05/36] BTRFS: Added retrieve sector size for later use
1962
1963---
1964 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 2 ++
1965 src/add-ons/kernel/file_systems/btrfs/Volume.h | 3 +++
1966 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 1 +
1967 3 files changed, 6 insertions(+)
1968
1969diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1970index ed1bd62..71e148a 100644
1971--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1972+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
1973@@ -266,7 +266,9 @@ Volume::Mount(const char* deviceName, uint32 flags)
1974 }
1975
1976 fBlockSize = fSuperBlock.BlockSize();
1977+ fSectorSize = fSuperBlock.SectorSize();
1978 TRACE("block size %" B_PRIu32 "\n", fBlockSize);
1979+ TRACE("sector size %" B_PRIu32 "\n", fSectorSize);
1980
1981 uint8* start = (uint8*)&fSuperBlock.system_chunk_array[0];
1982 uint8* end = (uint8*)&fSuperBlock.system_chunk_array[2048];
1983diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.h b/src/add-ons/kernel/file_systems/btrfs/Volume.h
1984index e5b371f..6561087 100644
1985--- a/src/add-ons/kernel/file_systems/btrfs/Volume.h
1986+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.h
1987@@ -41,7 +41,9 @@ public:
1988 BTree* FSTree() const { return fFSTree; }
1989 BTree* RootTree() const { return fRootTree; }
1990
1991+ uint32 SectorSize() const { return fSectorSize; }
1992 uint32 BlockSize() const { return fBlockSize; }
1993+
1994 btrfs_super_block& SuperBlock() { return fSuperBlock; }
1995
1996 status_t LoadSuperBlock();
1997@@ -62,6 +64,7 @@ private:
1998 char fName[32];
1999
2000 uint32 fFlags;
2001+ uint32 fSectorSize;
2002 uint32 fBlockSize;
2003
2004 void* fBlockCache;
2005diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2006index c0cf017..2afe5a9 100644
2007--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2008+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2009@@ -178,6 +178,7 @@ struct btrfs_super_block {
2010 // implemented in Volume.cpp
2011 uint64 TotalSize() const { return B_LENDIAN_TO_HOST_INT64(total_size); }
2012 uint32 BlockSize() const { return B_LENDIAN_TO_HOST_INT32(node_size); }
2013+ uint32 SectorSize() const { return B_LENDIAN_TO_HOST_INT32(sector_size); }
2014 uint64 RootDirObjectID() const
2015 { return B_LENDIAN_TO_HOST_INT64(root_dir_object_id); }
2016 uint64 Generation() const
2017--
20182.7.0
2019
2020
2021From bd3f07977dde23bd2d461a42376bb0edfe87dfd6 Mon Sep 17 00:00:00 2001
2022From: hyche <cvghy116@gmail.com>
2023Date: Fri, 9 Jun 2017 17:52:11 +0700
2024Subject: [PATCH 06/36] BTRFS: Added TRACE macro for debugging
2025
2026---
2027 src/add-ons/kernel/file_systems/btrfs/CachedBlock.h | 8 ++++++++
2028 1 file changed, 8 insertions(+)
2029
2030diff --git a/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h b/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
2031index 1071977..3d2a5cf 100644
2032--- a/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
2033+++ b/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
2034@@ -11,6 +11,14 @@
2035 #include "Volume.h"
2036
2037
2038+//#define TRACE_BTRFS
2039+#ifdef TRACE_BTRFS
2040+# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
2041+#else
2042+# define TRACE(x...) ;
2043+#endif
2044+
2045+
2046 class CachedBlock {
2047 public:
2048 CachedBlock(Volume* volume);
2049--
20502.7.0
2051
2052
2053From 346ef54e8a3202876683fb19ce214d2206c0a5b4 Mon Sep 17 00:00:00 2001
2054From: hyche <cvghy116@gmail.com>
2055Date: Fri, 9 Jun 2017 17:53:21 +0700
2056Subject: [PATCH 07/36] BTRFS: CachedBlock now is writable.
2057
2058---
2059 .../kernel/file_systems/btrfs/CachedBlock.h | 30 +++++++++++++++++++---
2060 1 file changed, 27 insertions(+), 3 deletions(-)
2061
2062diff --git a/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h b/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
2063index 3d2a5cf..769774f 100644
2064--- a/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
2065+++ b/src/add-ons/kernel/file_systems/btrfs/CachedBlock.h
2066@@ -29,9 +29,12 @@ public:
2067 void Unset();
2068
2069 const uint8* SetTo(off_t block);
2070+ uint8* SetToWritable(off_t block, int32 transactionId,
2071+ bool empty);
2072
2073 const uint8* Block() const { return fBlock; }
2074 off_t BlockNumber() const { return fBlockNumber; }
2075+ bool IsWritable() const { return fWritable; }
2076
2077 private:
2078 CachedBlock(const CachedBlock&);
2079@@ -42,6 +45,7 @@ protected:
2080 Volume* fVolume;
2081 off_t fBlockNumber;
2082 uint8* fBlock;
2083+ bool fWritable;
2084 };
2085
2086
2087@@ -53,7 +57,8 @@ CachedBlock::CachedBlock(Volume* volume)
2088 :
2089 fVolume(volume),
2090 fBlockNumber(0),
2091- fBlock(NULL)
2092+ fBlock(NULL),
2093+ fWritable(false)
2094 {
2095 }
2096
2097@@ -63,7 +68,8 @@ CachedBlock::CachedBlock(Volume* volume, off_t block)
2098 :
2099 fVolume(volume),
2100 fBlockNumber(0),
2101- fBlock(NULL)
2102+ fBlock(NULL),
2103+ fWritable(false)
2104 {
2105 SetTo(block);
2106 }
2107@@ -93,7 +99,7 @@ CachedBlock::Unset()
2108 }
2109
2110
2111-inline const uint8 *
2112+inline const uint8*
2113 CachedBlock::SetTo(off_t block)
2114 {
2115 Unset();
2116@@ -102,4 +108,22 @@ CachedBlock::SetTo(off_t block)
2117 }
2118
2119
2120+inline uint8*
2121+CachedBlock::SetToWritable(off_t block, int32 transactionId, bool empty)
2122+{
2123+ Unset();
2124+ fBlockNumber = block;
2125+ fWritable = true;
2126+ if (empty) {
2127+ fBlock = (uint8*)block_cache_get_empty(fVolume->BlockCache(),
2128+ block, transactionId);
2129+ } else {
2130+ fBlock = (uint8*)block_cache_get_writable(fVolume->BlockCache(),
2131+ block, transactionId);
2132+ }
2133+
2134+ return fBlock;
2135+}
2136+
2137+
2138 #endif // CACHED_BLOCK_H
2139--
21402.7.0
2141
2142
2143From be7da51581f706bb84c71a52352fe673f8a43653 Mon Sep 17 00:00:00 2001
2144From: hyche <cvghy116@gmail.com>
2145Date: Thu, 15 Jun 2017 01:16:21 +0700
2146Subject: [PATCH 08/36] BTRFS: Method _Compare from BTree is now in btrfs_key
2147
2148---
2149 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 24 ++++++++++++------------
2150 src/add-ons/kernel/file_systems/btrfs/BTree.h | 2 --
2151 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 2 ++
2152 3 files changed, 14 insertions(+), 14 deletions(-)
2153
2154diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2155index 85fda06..1033b80 100644
2156--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2157+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2158@@ -57,19 +57,19 @@ BTree::~BTree()
2159
2160
2161 int32
2162-BTree::_CompareKeys(btrfs_key& key1, btrfs_key& key2)
2163+btrfs_key::Compare(const btrfs_key& key) const
2164 {
2165- if (key1.ObjectID() > key2.ObjectID())
2166+ if (ObjectID() > key.ObjectID())
2167 return 1;
2168- if (key1.ObjectID() < key2.ObjectID())
2169+ if (ObjectID() < key.ObjectID())
2170 return -1;
2171- if (key1.Type() > key2.Type())
2172+ if (Type() > key.Type())
2173 return 1;
2174- if (key1.Type() < key2.Type())
2175+ if (Type() < key.Type())
2176 return -1;
2177- if (key1.Offset() > key2.Offset())
2178+ if (Offset() > key.Offset())
2179 return 1;
2180- if (key1.Offset() < key2.Offset())
2181+ if (Offset() < key.Offset())
2182 return -1;
2183 return 0;
2184 }
2185@@ -101,12 +101,12 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
2186 TRACE("Find() level %d\n", stream->header.Level());
2187 uint32 i = 1;
2188 for (; i < stream->header.ItemCount(); i++) {
2189- int32 comp = _CompareKeys(stream->index[i].key, key);
2190+ int32 comp = key.Compare(stream->index[i].key);
2191 TRACE("Find() found index %" B_PRIu32 " at %" B_PRId64 " comp %"
2192 B_PRId32 "\n", i, stream->index[i].BlockNum(), comp);
2193- if (comp < 0)
2194+ if (comp > 0)
2195 continue;
2196- if (comp > 0 || type == BTREE_BACKWARD)
2197+ if (comp < 0 || type == BTREE_BACKWARD)
2198 break;
2199 }
2200 TRACE("Find() getting index %" B_PRIu32 " at %" B_PRId64 "\n", i - 1,
2201@@ -125,7 +125,7 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
2202 #ifdef TRACE_BTRFS
2203 TRACE("Find() dump count %" B_PRId32 "\n", stream->header.ItemCount());
2204 for (i = 0; i < stream->header.ItemCount(); i++) {
2205- int32 comp = _CompareKeys(key, stream->entries[i].key);
2206+ int32 comp = key.Compare(stream->entries[i].key);
2207 TRACE("Find() dump %" B_PRIu32 " %" B_PRIu32 " offset %" B_PRId64
2208 " comp %" B_PRId32 "\n", stream->entries[i].Offset(),
2209 stream->entries[i].Size(), stream->entries[i].key.Offset(), comp);
2210@@ -133,7 +133,7 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
2211 #endif
2212
2213 for (i = 0; i < stream->header.ItemCount(); i++) {
2214- int32 comp = _CompareKeys(key, stream->entries[i].key);
2215+ int32 comp = key.Compare(stream->entries[i].key);
2216 TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 " oid %" B_PRId64
2217 " type %d offset %" B_PRId64 " comp %" B_PRId32 "\n",
2218 stream->entries[i].Offset(), stream->entries[i].Size(),
2219diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2220index 56a8b6d..0559343 100644
2221--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
2222+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2223@@ -58,8 +58,6 @@ private:
2224 BTree& operator=(const BTree& other);
2225 // no implementation
2226
2227- int32 _CompareKeys(btrfs_key& key1,
2228- btrfs_key& key2);
2229 status_t _Find(btrfs_key& key, void** value,
2230 size_t* size, btree_traversing type);
2231 void _AddIterator(TreeIterator* iterator);
2232diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2233index 2afe5a9..279c42c 100644
2234--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2235+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2236@@ -26,6 +26,8 @@ struct btrfs_key {
2237 void SetObjectID(uint64 id) { object_id = B_HOST_TO_LENDIAN_INT64(id); }
2238 void SetType(uint8 key_type) { type = key_type; }
2239 void SetOffset(uint64 off) { offset = B_HOST_TO_LENDIAN_INT64(off); }
2240+ int32 Compare(const btrfs_key& key) const;
2241+ //implemented in BTree.cpp
2242 } _PACKED;
2243
2244
2245--
22462.7.0
2247
2248
2249From 4734c677dd6b4beb617b8aaa8d8e892ded3f3f49 Mon Sep 17 00:00:00 2001
2250From: hyche <cvghy116@gmail.com>
2251Date: Thu, 15 Jun 2017 23:32:34 +0700
2252Subject: [PATCH 09/36] BTRFS: Initialize BPath and BNode for tree manipulation
2253
2254---
2255 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 73 +++++++++++++++++++++++++
2256 src/add-ons/kernel/file_systems/btrfs/BTree.h | 58 ++++++++++++++++++++
2257 2 files changed, 131 insertions(+)
2258
2259diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2260index 1033b80..7db8c2d 100644
2261--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2262+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2263@@ -21,6 +21,79 @@
2264 # define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
2265
2266
2267+BNode::BNode(void* cache)
2268+ :
2269+ fNode(NULL),
2270+ fCache(cache),
2271+ fBlockNumber(0),
2272+ fCurrentSlot(0),
2273+ fWritable(false)
2274+{
2275+}
2276+
2277+
2278+BNode::BNode(void* cache, off_t block)
2279+ :
2280+ fNode(NULL),
2281+ fCache(cache),
2282+ fBlockNumber(0),
2283+ fCurrentSlot(0),
2284+ fWritable(false)
2285+{
2286+ SetTo(block);
2287+}
2288+
2289+
2290+BNode::~BNode()
2291+{
2292+ Unset();
2293+}
2294+
2295+
2296+void
2297+BNode::Keep()
2298+{
2299+ fNode = NULL;
2300+}
2301+
2302+void
2303+BNode::Unset()
2304+{
2305+ if (fNode != NULL) {
2306+ block_cache_put(fCache, fBlockNumber);
2307+ fNode = NULL;
2308+ }
2309+}
2310+
2311+
2312+void
2313+BNode::SetTo(off_t block)
2314+{
2315+ Unset();
2316+ fBlockNumber = block;
2317+ fNode = (btrfs_stream*)block_cache_get(fCache, block);
2318+}
2319+
2320+
2321+void
2322+BNode::SetToWritable(off_t block, int32 transactionId, bool empty)
2323+{
2324+ Unset();
2325+ fBlockNumber = block;
2326+ fWritable = true;
2327+ if (empty) {
2328+ fNode = (btrfs_stream*)block_cache_get_empty(fCache, block,
2329+ transactionId);
2330+ } else {
2331+ fNode = (btrfs_stream*)block_cache_get_writable(fCache, block,
2332+ transactionId);
2333+ }
2334+}
2335+
2336+
2337+//-pragma mark
2338+
2339+
2340 BTree::BTree(Volume* volume, btrfs_stream* stream)
2341 :
2342 fStream(stream),
2343diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2344index 0559343..cf9e2cb 100644
2345--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
2346+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2347@@ -14,6 +14,8 @@
2348 #define BTREE_NULL -1LL
2349 #define BTREE_FREE -2LL
2350
2351+#define BTRFS_MAX_TREE_DEPTH 8
2352+
2353
2354 enum btree_traversing {
2355 BTREE_FORWARD = 1,
2356@@ -39,6 +41,62 @@ struct node_and_key {
2357 };
2358
2359
2360+class BNode {
2361+public:
2362+ BNode(void* cache);
2363+ BNode(void* cache, off_t block);
2364+ ~BNode();
2365+
2366+ // just return from Header
2367+ uint64 BlockNum() const
2368+ { return fNode->header.BlockNum(); }
2369+ uint64 Flags() const
2370+ { return fNode->header.Flags(); }
2371+ uint64 Generation() const
2372+ { return fNode->header.Generation(); }
2373+ uint64 Owner() const
2374+ { return fNode->header.Owner(); }
2375+ uint32 ItemCount() const
2376+ { return fNode->header.ItemCount(); }
2377+ uint8 Level() const
2378+ { return fNode->header.Level(); }
2379+
2380+ btrfs_index* Index(uint32 i) const
2381+ { return &fNode->index[i]; }
2382+
2383+ btrfs_entry* Item(uint32 i) const
2384+ { return &fNode->entries[i]; }
2385+ uint8* ItemData(uint32 i) const
2386+ { return (uint8*)Item(0) + Item(i)->Offset(); }
2387+
2388+ void Keep();
2389+ void Unset();
2390+
2391+
2392+ void SetTo(off_t block);
2393+ void SetToWritable(off_t block,
2394+ int32 transactionId, bool empty);
2395+
2396+ off_t BlockNumber() const { return fBlockNumber; }
2397+ bool IsWritable() const { return fWritable; }
2398+private:
2399+ BNode(const BNode&);
2400+ BNode& operator=(const BNode&);
2401+ //no implementation
2402+
2403+ btrfs_stream* fNode;
2404+ void* fCache;
2405+ off_t fBlockNumber;
2406+ uint32 fCurrentSlot;
2407+ bool fWritable;
2408+};
2409+
2410+
2411+class BPath {
2412+ BNode* nodes[BTRFS_MAX_TREE_DEPTH];
2413+};
2414+
2415+
2416 class BTree {
2417 public:
2418 BTree(Volume* volume,
2419--
24202.7.0
2421
2422
2423From a3455177f23d967aaba2db88a05f119d674fc98c Mon Sep 17 00:00:00 2001
2424From: hyche <cvghy116@gmail.com>
2425Date: Fri, 16 Jun 2017 22:52:17 +0700
2426Subject: [PATCH 10/36] BTRFS: Chunk tree objectID is 3, 256 is the objectID of
2427 first created subvolume in fs tree and also of first chunk tree (item in
2428 chunk tree).
2429
2430---
2431 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 4 +-
2432 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 54 ++++++++++++------------
2433 2 files changed, 30 insertions(+), 28 deletions(-)
2434
2435diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2436index 71e148a..372ce09 100644
2437--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2438+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2439@@ -389,7 +389,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
2440 return B_NO_MEMORY;
2441
2442 // ready
2443- status = get_vnode(fFSVolume, BTRFS_OBJECT_ID_CHUNK_TREE,
2444+ status = get_vnode(fFSVolume, BTRFS_FIRST_SUBVOLUME,
2445 (void**)&fRootNode);
2446 if (status != B_OK) {
2447 ERROR("could not create root node: get_vnode() failed!\n");
2448@@ -492,7 +492,7 @@ Volume::FindBlock(off_t logical, off_t& physical)
2449 btrfs_key search_key;
2450 search_key.SetOffset(logical);
2451 search_key.SetType(BTRFS_KEY_TYPE_CHUNK_ITEM);
2452- search_key.SetObjectID(BTRFS_OBJECT_ID_CHUNK_TREE);
2453+ search_key.SetObjectID(BTRFS_OBJECT_ID_FIRST_CHUNK_TREE);
2454 btrfs_chunk* chunk;
2455 size_t chunk_length;
2456 status_t status = fChunkTree->FindPrevious(search_key, (void**)&chunk,
2457diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2458index 279c42c..39ca5b3 100644
2459--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2460+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2461@@ -303,32 +303,34 @@ struct btrfs_extent_data {
2462 } _PACKED;
2463
2464
2465-#define BTRFS_SUPER_BLOCK_MAGIC "_BHRfS_M"
2466-
2467-#define BTRFS_OBJECT_ID_ROOT_TREE 1
2468-#define BTRFS_OBJECT_ID_EXTENT_TREE 2
2469-#define BTRFS_OBJECT_ID_DEV_TREE 4
2470-#define BTRFS_OBJECT_ID_FS_TREE 5
2471-#define BTRFS_OBJECT_ID_ROOT_TREE_DIR 6
2472-#define BTRFS_OBJECT_ID_CHECKSUM_TREE 7
2473-#define BTRFS_OBJECT_ID_CHUNK_TREE 256
2474-
2475-#define BTRFS_KEY_TYPE_CHUNK_ITEM 228
2476-#define BTRFS_KEY_TYPE_DIR_ITEM 84
2477-#define BTRFS_KEY_TYPE_DIR_INDEX 96
2478-#define BTRFS_KEY_TYPE_EXTENT_DATA 108
2479-#define BTRFS_KEY_TYPE_INODE_ITEM 1
2480-#define BTRFS_KEY_TYPE_INODE_REF 12
2481-#define BTRFS_KEY_TYPE_ROOT_ITEM 132
2482-#define BTRFS_KEY_TYPE_XATTR_ITEM 24
2483-
2484-#define BTRFS_EXTENT_COMPRESS_NONE 0
2485-#define BTRFS_EXTENT_COMPRESS_ZLIB 1
2486-#define BTRFS_EXTENT_COMPRESS_LZO 2
2487-
2488-#define BTRFS_EXTENT_DATA_INLINE 0
2489-#define BTRFS_EXTENT_DATA_REGULAR 1
2490-#define BTRFS_EXTENT_DATA_PRE 2
2491+#define BTRFS_SUPER_BLOCK_MAGIC "_BHRfS_M"
2492+#define BTRFS_FIRST_SUBVOLUME 256
2493+
2494+#define BTRFS_OBJECT_ID_ROOT_TREE 1
2495+#define BTRFS_OBJECT_ID_EXTENT_TREE 2
2496+#define BTRFS_OBJECT_ID_CHUNK_TREE 3
2497+#define BTRFS_OBJECT_ID_DEV_TREE 4
2498+#define BTRFS_OBJECT_ID_FS_TREE 5
2499+#define BTRFS_OBJECT_ID_ROOT_TREE_DIR 6
2500+#define BTRFS_OBJECT_ID_CHECKSUM_TREE 7
2501+#define BTRFS_OBJECT_ID_FIRST_CHUNK_TREE 256
2502+
2503+#define BTRFS_KEY_TYPE_CHUNK_ITEM 228
2504+#define BTRFS_KEY_TYPE_DIR_ITEM 84
2505+#define BTRFS_KEY_TYPE_DIR_INDEX 96
2506+#define BTRFS_KEY_TYPE_EXTENT_DATA 108
2507+#define BTRFS_KEY_TYPE_INODE_ITEM 1
2508+#define BTRFS_KEY_TYPE_INODE_REF 12
2509+#define BTRFS_KEY_TYPE_ROOT_ITEM 132
2510+#define BTRFS_KEY_TYPE_XATTR_ITEM 24
2511+
2512+#define BTRFS_EXTENT_COMPRESS_NONE 0
2513+#define BTRFS_EXTENT_COMPRESS_ZLIB 1
2514+#define BTRFS_EXTENT_COMPRESS_LZO 2
2515+
2516+#define BTRFS_EXTENT_DATA_INLINE 0
2517+#define BTRFS_EXTENT_DATA_REGULAR 1
2518+#define BTRFS_EXTENT_DATA_PRE 2
2519
2520
2521 struct file_cookie {
2522--
25232.7.0
2524
2525
2526From a9e74353712da42060556bb4394ec13b9020ad51 Mon Sep 17 00:00:00 2001
2527From: hyche <cvghy116@gmail.com>
2528Date: Sun, 18 Jun 2017 22:44:08 +0700
2529Subject: [PATCH 11/36] BTRFS: Added binary search for item slot
2530
2531---
2532 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 33 +++++++++++++++++++++++++
2533 src/add-ons/kernel/file_systems/btrfs/BTree.h | 2 ++
2534 2 files changed, 35 insertions(+)
2535
2536diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2537index 7db8c2d..fc3a891 100644
2538--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2539+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2540@@ -91,6 +91,39 @@ BNode::SetToWritable(off_t block, int32 transactionId, bool empty)
2541 }
2542
2543
2544+int32
2545+BNode::SearchSlot(const btrfs_key& key, int* slot) const
2546+{
2547+ //binary search for item slot in a node
2548+ int entrySize = sizeof(btrfs_entry);
2549+ if (Level() != 0) {
2550+ // internal node
2551+ entrySize = sizeof(btrfs_index);
2552+ }
2553+
2554+ int low = 0;
2555+ int high = ItemCount();
2556+ int mid;
2557+ int base = sizeof(btrfs_header);
2558+ const btrfs_key* other;
2559+ while (low < high) {
2560+ mid = (low + high) / 2;
2561+ other = (const btrfs_key*)((uint8*)fNode + base + mid * entrySize);
2562+ int comp = key.Compare(*other);
2563+ if (comp < 0)
2564+ high = mid;
2565+ else if (comp > 0)
2566+ low = mid + 1;
2567+ else {
2568+ *slot = mid;
2569+ return B_OK;
2570+ }
2571+ }
2572+ *slot = low;
2573+ return B_ENTRY_NOT_FOUND;
2574+}
2575+
2576+
2577 //-pragma mark
2578
2579
2580diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2581index cf9e2cb..ffddf1d 100644
2582--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
2583+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2584@@ -79,6 +79,8 @@ public:
2585
2586 off_t BlockNumber() const { return fBlockNumber; }
2587 bool IsWritable() const { return fWritable; }
2588+
2589+ int32 SearchSlot(const btrfs_key& key, int* slot) const;
2590 private:
2591 BNode(const BNode&);
2592 BNode& operator=(const BNode&);
2593--
25942.7.0
2595
2596
2597From 8ee5e1382f7cc0bf66bb317e84a7295e8c07b84d Mon Sep 17 00:00:00 2001
2598From: hyche <cvghy116@gmail.com>
2599Date: Thu, 22 Jun 2017 19:59:58 +0700
2600Subject: [PATCH 12/36] BTRFS: BlockNum -> Logical to prevent misunderstanding
2601
2602---
2603 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 8 ++++----
2604 src/add-ons/kernel/file_systems/btrfs/BTree.h | 6 +++---
2605 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 16 ++++++++--------
2606 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 12 ++++++------
2607 4 files changed, 21 insertions(+), 21 deletions(-)
2608
2609diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2610index fc3a891..18106e0 100644
2611--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2612+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2613@@ -209,19 +209,19 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
2614 for (; i < stream->header.ItemCount(); i++) {
2615 int32 comp = key.Compare(stream->index[i].key);
2616 TRACE("Find() found index %" B_PRIu32 " at %" B_PRId64 " comp %"
2617- B_PRId32 "\n", i, stream->index[i].BlockNum(), comp);
2618+ B_PRId32 "\n", i, stream->index[i].Logical(), comp);
2619 if (comp > 0)
2620 continue;
2621 if (comp < 0 || type == BTREE_BACKWARD)
2622 break;
2623 }
2624 TRACE("Find() getting index %" B_PRIu32 " at %" B_PRId64 "\n", i - 1,
2625- stream->index[i - 1].BlockNum());
2626+ stream->index[i - 1].Logical());
2627
2628- if (fVolume->FindBlock(stream->index[i - 1].BlockNum(), physical)
2629+ if (fVolume->FindBlock(stream->index[i - 1].Logical(), physical)
2630 != B_OK) {
2631 ERROR("Find() unmapped block %" B_PRId64 "\n",
2632- stream->index[i - 1].BlockNum());
2633+ stream->index[i - 1].Logical());
2634 return B_ERROR;
2635 }
2636 stream = (btrfs_stream*)cached.SetTo(physical);
2637diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2638index ffddf1d..a121337 100644
2639--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
2640+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2641@@ -48,8 +48,8 @@ public:
2642 ~BNode();
2643
2644 // just return from Header
2645- uint64 BlockNum() const
2646- { return fNode->header.BlockNum(); }
2647+ uint64 Logical() const
2648+ { return fNode->header.Logical(); }
2649 uint64 Flags() const
2650 { return fNode->header.Flags(); }
2651 uint64 Generation() const
2652@@ -77,7 +77,7 @@ public:
2653 void SetToWritable(off_t block,
2654 int32 transactionId, bool empty);
2655
2656- off_t BlockNumber() const { return fBlockNumber; }
2657+ off_t BlockNum() const { return fBlockNumber;}
2658 bool IsWritable() const { return fWritable; }
2659
2660 int32 SearchSlot(const btrfs_key& key, int* slot) const;
2661diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2662index 372ce09..7a378cf 100644
2663--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2664+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2665@@ -344,8 +344,8 @@ Volume::Mount(const char* deviceName, uint32 flags)
2666 return B_ERROR;
2667 }
2668 TRACE("Volume::Mount(): Found extent root: %" B_PRIu64 "\n",
2669- root->BlockNum());
2670- fExtentTree = new(std::nothrow) BTree(this, root->BlockNum());
2671+ root->Logical());
2672+ fExtentTree = new(std::nothrow) BTree(this, root->Logical());
2673 free(root);
2674 if (fExtentTree == NULL)
2675 return B_NO_MEMORY;
2676@@ -356,8 +356,8 @@ Volume::Mount(const char* deviceName, uint32 flags)
2677 ERROR("Volume::Mount(): Couldn't find fs root\n");
2678 return B_ERROR;
2679 }
2680- TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n", root->BlockNum());
2681- fFSTree = new(std::nothrow) BTree(this, root->BlockNum());
2682+ TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n", root->Logical());
2683+ fFSTree = new(std::nothrow) BTree(this, root->Logical());
2684 free(root);
2685 if (fFSTree == NULL)
2686 return B_NO_MEMORY;
2687@@ -369,8 +369,8 @@ Volume::Mount(const char* deviceName, uint32 flags)
2688 return B_ERROR;
2689 }
2690 TRACE("Volume::Mount(): Found dev root: %" B_PRIu64 "\n",
2691- root->BlockNum());
2692- fDevTree = new(std::nothrow) BTree(this, root->BlockNum());
2693+ root->Logical());
2694+ fDevTree = new(std::nothrow) BTree(this, root->Logical());
2695 free(root);
2696 if (fDevTree == NULL)
2697 return B_NO_MEMORY;
2698@@ -382,8 +382,8 @@ Volume::Mount(const char* deviceName, uint32 flags)
2699 return B_ERROR;
2700 }
2701 TRACE("Volume::Mount(): Found checksum root: %" B_PRIu64 "\n",
2702- root->BlockNum());
2703- fChecksumTree = new(std::nothrow) BTree(this, root->BlockNum());
2704+ root->Logical());
2705+ fChecksumTree = new(std::nothrow) BTree(this, root->Logical());
2706 free(root);
2707 if (fChecksumTree == NULL)
2708 return B_NO_MEMORY;
2709diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2710index 39ca5b3..d7b9fef 100644
2711--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2712+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
2713@@ -40,14 +40,14 @@ struct btrfs_timespec {
2714 struct btrfs_header {
2715 uint8 checksum[32];
2716 uint8 fsid[16];
2717- uint64 blocknum;
2718+ uint64 logical_address;
2719 uint64 flags;
2720 uint8 chunk_tree_uuid[16];
2721 uint64 generation;
2722 uint64 owner;
2723 uint32 item_count;
2724 uint8 level;
2725- uint64 BlockNum() const { return B_LENDIAN_TO_HOST_INT64(blocknum); }
2726+ uint64 Logical() const { return B_LENDIAN_TO_HOST_INT64(logical_address); }
2727 uint64 Flags() const { return B_LENDIAN_TO_HOST_INT64(flags); }
2728 uint64 Generation() const
2729 { return B_LENDIAN_TO_HOST_INT64(generation); }
2730@@ -61,9 +61,9 @@ struct btrfs_header {
2731
2732 struct btrfs_index {
2733 btrfs_key key;
2734- uint64 blocknum;
2735+ uint64 logical_address;
2736 uint64 generation;
2737- uint64 BlockNum() const { return B_LENDIAN_TO_HOST_INT64(blocknum); }
2738+ uint64 Logical() const { return B_LENDIAN_TO_HOST_INT64(logical_address); }
2739 uint64 Generation() const
2740 { return B_LENDIAN_TO_HOST_INT64(generation); }
2741 } _PACKED;
2742@@ -241,7 +241,7 @@ struct btrfs_root {
2743 btrfs_inode inode;
2744 uint64 generation;
2745 uint64 root_dirid;
2746- uint64 blocknum;
2747+ uint64 logical_address;
2748 uint64 limit_bytes;
2749 uint64 used_bytes;
2750 uint64 last_snapshot;
2751@@ -252,7 +252,7 @@ struct btrfs_root {
2752 uint8 level;
2753 uint64 Generation() const
2754 { return B_LENDIAN_TO_HOST_INT64(generation); }
2755- uint64 BlockNum() const { return B_LENDIAN_TO_HOST_INT64(blocknum); }
2756+ uint64 Logical() const { return B_LENDIAN_TO_HOST_INT64(logical_address); }
2757 } _PACKED;
2758
2759
2760--
27612.7.0
2762
2763
2764From 58a3a6b040a459a57083b63a29dce6f6bd4943af Mon Sep 17 00:00:00 2001
2765From: hyche <cvghy116@gmail.com>
2766Date: Thu, 22 Jun 2017 21:39:55 +0700
2767Subject: [PATCH 13/36] BTRFS: Added SetRoot for tree. Tree root is initialized
2768 at mount time
2769
2770---
2771 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 31 ++++++++++++++++++++----
2772 src/add-ons/kernel/file_systems/btrfs/BTree.h | 3 +++
2773 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 30 ++++++++++++++---------
2774 3 files changed, 47 insertions(+), 17 deletions(-)
2775
2776diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2777index 18106e0..31714cc 100644
2778--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2779+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2780@@ -127,6 +127,16 @@ BNode::SearchSlot(const btrfs_key& key, int* slot) const
2781 //-pragma mark
2782
2783
2784+BTree::BTree(Volume* volume)
2785+ :
2786+ fStream(NULL),
2787+ fRootBlock(0),
2788+ fVolume(volume)
2789+{
2790+ mutex_init(&fIteratorLock, "btrfs b+tree iterator");
2791+}
2792+
2793+
2794 BTree::BTree(Volume* volume, btrfs_stream* stream)
2795 :
2796 fStream(stream),
2797@@ -196,11 +206,7 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
2798 CachedBlock cached(fVolume);
2799 fsblock_t physical;
2800 if (stream == NULL) {
2801- if (fVolume->FindBlock(fRootBlock, physical) != B_OK) {
2802- ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
2803- return B_ERROR;
2804- }
2805- stream = (btrfs_stream*)cached.SetTo(physical);
2806+ stream = (btrfs_stream*)cached.SetTo(fRootBlock);
2807 }
2808
2809 while (stream->header.Level() != 0) {
2810@@ -309,6 +315,21 @@ BTree::FindExact(btrfs_key& key, void** _value, size_t* _size)
2811 }
2812
2813
2814+status_t
2815+BTree::SetRoot(off_t logical, fsblock_t* block)
2816+{
2817+ if (block != NULL) {
2818+ fRootBlock = *block;
2819+ } else {
2820+ if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
2821+ ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
2822+ return B_ERROR;
2823+ }
2824+ }
2825+ return B_OK;
2826+}
2827+
2828+
2829 void
2830 BTree::_AddIterator(TreeIterator* iterator)
2831 {
2832diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2833index a121337..edd44e1 100644
2834--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
2835+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
2836@@ -101,6 +101,7 @@ class BPath {
2837
2838 class BTree {
2839 public:
2840+ BTree(Volume* volume);
2841 BTree(Volume* volume,
2842 btrfs_stream* stream);
2843 BTree(Volume* volume,
2844@@ -113,6 +114,8 @@ public:
2845 status_t FindPrevious(btrfs_key& key, void** value,
2846 size_t* size = NULL);
2847
2848+ status_t SetRoot(off_t logical, fsblock_t* block);
2849+
2850 private:
2851 BTree(const BTree& other);
2852 BTree& operator=(const BTree& other);
2853diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2854index 7a378cf..234df2c 100644
2855--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2856+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
2857@@ -280,7 +280,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
2858 if (key->Type() != BTRFS_KEY_TYPE_CHUNK_ITEM) {
2859 break;
2860 }
2861-
2862+
2863 btrfs_chunk* chunk = (btrfs_chunk*)(key + 1);
2864 fChunk = new(std::nothrow) Chunk(chunk, key->Offset());
2865 if (fChunk == NULL)
2866@@ -316,10 +316,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
2867
2868 TRACE("Volume::Mount(): Initialized block cache: %p\n", fBlockCache);
2869
2870- fChunkTree = new(std::nothrow) BTree(this, fSuperBlock.ChunkRoot());
2871+ fChunkTree = new(std::nothrow) BTree(this);
2872 if (fChunkTree == NULL)
2873 return B_NO_MEMORY;
2874-
2875+ fChunkTree->SetRoot(fSuperBlock.ChunkRoot(), NULL);
2876 FindBlock(fSuperBlock.Root(), physical);
2877 TRACE("Volume::Mount() root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
2878 fSuperBlock.Root(), physical);
2879@@ -330,9 +330,11 @@ Volume::Mount(const char* deviceName, uint32 flags)
2880 TRACE("Volume::Mount() log_root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
2881 fSuperBlock.LogRoot(), physical);
2882
2883- fRootTree = new(std::nothrow) BTree(this, fSuperBlock.Root());
2884+ fRootTree = new(std::nothrow) BTree(this);
2885 if (fRootTree == NULL)
2886 return B_NO_MEMORY;
2887+ fRootTree->SetRoot(fSuperBlock.Root(), NULL);
2888+
2889 TRACE("Volume::Mount(): Searching extent root\n");
2890 btrfs_key search_key;
2891 search_key.SetOffset(0);
2892@@ -345,10 +347,11 @@ Volume::Mount(const char* deviceName, uint32 flags)
2893 }
2894 TRACE("Volume::Mount(): Found extent root: %" B_PRIu64 "\n",
2895 root->Logical());
2896- fExtentTree = new(std::nothrow) BTree(this, root->Logical());
2897- free(root);
2898+ fExtentTree = new(std::nothrow) BTree(this);
2899 if (fExtentTree == NULL)
2900 return B_NO_MEMORY;
2901+ fExtentTree->SetRoot(root->Logical(), NULL);
2902+ free(root);
2903
2904 search_key.SetOffset(0);
2905 search_key.SetObjectID(BTRFS_OBJECT_ID_FS_TREE);
2906@@ -357,10 +360,11 @@ Volume::Mount(const char* deviceName, uint32 flags)
2907 return B_ERROR;
2908 }
2909 TRACE("Volume::Mount(): Found fs root: %" B_PRIu64 "\n", root->Logical());
2910- fFSTree = new(std::nothrow) BTree(this, root->Logical());
2911- free(root);
2912+ fFSTree = new(std::nothrow) BTree(this);
2913 if (fFSTree == NULL)
2914 return B_NO_MEMORY;
2915+ fFSTree->SetRoot(root->Logical(), NULL);
2916+ free(root);
2917
2918 search_key.SetOffset(0);
2919 search_key.SetObjectID(BTRFS_OBJECT_ID_DEV_TREE);
2920@@ -370,10 +374,11 @@ Volume::Mount(const char* deviceName, uint32 flags)
2921 }
2922 TRACE("Volume::Mount(): Found dev root: %" B_PRIu64 "\n",
2923 root->Logical());
2924- fDevTree = new(std::nothrow) BTree(this, root->Logical());
2925- free(root);
2926+ fDevTree = new(std::nothrow) BTree(this);
2927 if (fDevTree == NULL)
2928 return B_NO_MEMORY;
2929+ fDevTree->SetRoot(root->Logical(), NULL);
2930+ free(root);
2931
2932 search_key.SetOffset(0);
2933 search_key.SetObjectID(BTRFS_OBJECT_ID_CHECKSUM_TREE);
2934@@ -383,10 +388,11 @@ Volume::Mount(const char* deviceName, uint32 flags)
2935 }
2936 TRACE("Volume::Mount(): Found checksum root: %" B_PRIu64 "\n",
2937 root->Logical());
2938- fChecksumTree = new(std::nothrow) BTree(this, root->Logical());
2939- free(root);
2940+ fChecksumTree = new(std::nothrow) BTree(this);
2941 if (fChecksumTree == NULL)
2942 return B_NO_MEMORY;
2943+ fChecksumTree->SetRoot(root->Logical(), NULL);
2944+ free(root);
2945
2946 // ready
2947 status = get_vnode(fFSVolume, BTRFS_FIRST_SUBVOLUME,
2948--
29492.7.0
2950
2951
2952From d44f3731a7ddabfe9bbc39375eecd5cde6a10ce2 Mon Sep 17 00:00:00 2001
2953From: hyche <cvghy116@gmail.com>
2954Date: Fri, 23 Jun 2017 15:34:19 +0700
2955Subject: [PATCH 14/36] BTRFS: Enhanced node search slot to handle
2956 btree_traverse type
2957
2958---
2959 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 21 +++++++++++++++------
2960 src/add-ons/kernel/file_systems/btrfs/BTree.h | 3 ++-
2961 2 files changed, 17 insertions(+), 7 deletions(-)
2962
2963diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2964index 31714cc..678b775 100644
2965--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2966+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
2967@@ -92,7 +92,7 @@ BNode::SetToWritable(off_t block, int32 transactionId, bool empty)
2968
2969
2970 int32
2971-BNode::SearchSlot(const btrfs_key& key, int* slot) const
2972+BNode::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
2973 {
2974 //binary search for item slot in a node
2975 int entrySize = sizeof(btrfs_entry);
2976@@ -103,24 +103,33 @@ BNode::SearchSlot(const btrfs_key& key, int* slot) const
2977
2978 int low = 0;
2979 int high = ItemCount();
2980- int mid;
2981+ int mid, comp;
2982 int base = sizeof(btrfs_header);
2983 const btrfs_key* other;
2984 while (low < high) {
2985 mid = (low + high) / 2;
2986 other = (const btrfs_key*)((uint8*)fNode + base + mid * entrySize);
2987- int comp = key.Compare(*other);
2988+ comp = key.Compare(*other);
2989 if (comp < 0)
2990 high = mid;
2991 else if (comp > 0)
2992 low = mid + 1;
2993 else {
2994 *slot = mid;
2995- return B_OK;
2996+ return B_OK; //if key is in node
2997 }
2998 }
2999- *slot = low;
3000- return B_ENTRY_NOT_FOUND;
3001+
3002+ TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
3003+ *slot, comp);
3004+ if (type == BTREE_BACKWARD)
3005+ *slot = low - 1;
3006+ else if (type == BTREE_FORWARD)
3007+ *slot = low;
3008+
3009+ if (*slot < 0 || type == BTREE_EXACT)
3010+ return B_ENTRY_NOT_FOUND;
3011+ return B_OK;
3012 }
3013
3014
3015diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3016index edd44e1..2a5997f 100644
3017--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3018+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3019@@ -80,7 +80,8 @@ public:
3020 off_t BlockNum() const { return fBlockNumber;}
3021 bool IsWritable() const { return fWritable; }
3022
3023- int32 SearchSlot(const btrfs_key& key, int* slot) const;
3024+ int32 SearchSlot(const btrfs_key& key, int* slot,
3025+ btree_traversing type) const;
3026 private:
3027 BNode(const BNode&);
3028 BNode& operator=(const BNode&);
3029--
30302.7.0
3031
3032
3033From de32356689e772d4c35b1f7cc951244e3ec55345 Mon Sep 17 00:00:00 2001
3034From: hyche <cvghy116@gmail.com>
3035Date: Fri, 23 Jun 2017 17:18:39 +0700
3036Subject: [PATCH 15/36] BTRFS: Added retrieve RootBlock of BTree
3037
3038---
3039 src/add-ons/kernel/file_systems/btrfs/BTree.h | 2 ++
3040 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 4 ++++
3041 2 files changed, 6 insertions(+)
3042
3043diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3044index 2a5997f..4e9e7e5 100644
3045--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3046+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3047@@ -117,6 +117,8 @@ public:
3048
3049 status_t SetRoot(off_t logical, fsblock_t* block);
3050
3051+ fsblock_t RootBlock() const { return fRootBlock; }
3052+
3053 private:
3054 BTree(const BTree& other);
3055 BTree& operator=(const BTree& other);
3056diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
3057index 234df2c..36dac6c 100644
3058--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
3059+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
3060@@ -320,6 +320,8 @@ Volume::Mount(const char* deviceName, uint32 flags)
3061 if (fChunkTree == NULL)
3062 return B_NO_MEMORY;
3063 fChunkTree->SetRoot(fSuperBlock.ChunkRoot(), NULL);
3064+ TRACE("Volume::Mount() chunk_root: %" B_PRIu64 " (physical block %" B_PRIu64
3065+ ")\n", fSuperBlock.ChunkRoot(), fChunkTree->RootBlock());
3066 FindBlock(fSuperBlock.Root(), physical);
3067 TRACE("Volume::Mount() root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
3068 fSuperBlock.Root(), physical);
3069@@ -334,6 +336,8 @@ Volume::Mount(const char* deviceName, uint32 flags)
3070 if (fRootTree == NULL)
3071 return B_NO_MEMORY;
3072 fRootTree->SetRoot(fSuperBlock.Root(), NULL);
3073+ TRACE("Volume::Mount() root: %" B_PRIu64 " (physical block %" B_PRIu64 ")\n",
3074+ fSuperBlock.Root(), fRootTree->RootBlock());
3075
3076 TRACE("Volume::Mount(): Searching extent root\n");
3077 btrfs_key search_key;
3078--
30792.7.0
3080
3081
3082From 1560e2a4b041c9c298754e8f7c1ca025a8f0c5b3 Mon Sep 17 00:00:00 2001
3083From: hyche <cvghy116@gmail.com>
3084Date: Fri, 23 Jun 2017 17:27:53 +0700
3085Subject: [PATCH 16/36] BTRFS: Combine BNode and _Find * Replaced fStream by
3086 BNode, this might fix errors when handling BTree with multiple levels because
3087 fStream remains at leaf after first allocating. * Changed search algorithm
3088 for items (linear search -> binary search)
3089
3090---
3091 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 94 ++++++-------------------
3092 src/add-ons/kernel/file_systems/btrfs/BTree.h | 1 -
3093 2 files changed, 23 insertions(+), 72 deletions(-)
3094
3095diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3096index 678b775..87edf86 100644
3097--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3098+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3099@@ -138,7 +138,6 @@ BNode::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
3100
3101 BTree::BTree(Volume* volume)
3102 :
3103- fStream(NULL),
3104 fRootBlock(0),
3105 fVolume(volume)
3106 {
3107@@ -148,7 +147,6 @@ BTree::BTree(Volume* volume)
3108
3109 BTree::BTree(Volume* volume, btrfs_stream* stream)
3110 :
3111- fStream(stream),
3112 fRootBlock(0),
3113 fVolume(volume)
3114 {
3115@@ -158,7 +156,6 @@ BTree::BTree(Volume* volume, btrfs_stream* stream)
3116
3117 BTree::BTree(Volume* volume, fsblock_t rootBlock)
3118 :
3119- fStream(NULL),
3120 fRootBlock(rootBlock),
3121 fVolume(volume)
3122 {
3123@@ -211,86 +208,41 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
3124 {
3125 TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
3126 key.ObjectID(), key.Type(), key.Offset());
3127- btrfs_stream* stream = fStream;
3128 CachedBlock cached(fVolume);
3129- fsblock_t physical;
3130- if (stream == NULL) {
3131- stream = (btrfs_stream*)cached.SetTo(fRootBlock);
3132- }
3133-
3134- while (stream->header.Level() != 0) {
3135- TRACE("Find() level %d\n", stream->header.Level());
3136- uint32 i = 1;
3137- for (; i < stream->header.ItemCount(); i++) {
3138- int32 comp = key.Compare(stream->index[i].key);
3139- TRACE("Find() found index %" B_PRIu32 " at %" B_PRId64 " comp %"
3140- B_PRId32 "\n", i, stream->index[i].Logical(), comp);
3141- if (comp > 0)
3142- continue;
3143- if (comp < 0 || type == BTREE_BACKWARD)
3144- break;
3145- }
3146- TRACE("Find() getting index %" B_PRIu32 " at %" B_PRId64 "\n", i - 1,
3147- stream->index[i - 1].Logical());
3148-
3149- if (fVolume->FindBlock(stream->index[i - 1].Logical(), physical)
3150+ BNode node(fVolume->BlockCache(), fRootBlock);
3151+ int slot, ret;
3152+ fsblock_t physicalBlock;
3153+
3154+ while (node.Level() != 0) {
3155+ TRACE("Find() level %d\n", node.Level());
3156+ ret = node.SearchSlot(key, &slot, BTREE_BACKWARD);
3157+ if (ret != B_OK)
3158+ return ret;
3159+ TRACE("Find() getting index %" B_PRIu32 "\n", slot);
3160+
3161+ if (fVolume->FindBlock(node.Index(slot)->Logical(), physicalBlock)
3162 != B_OK) {
3163 ERROR("Find() unmapped block %" B_PRId64 "\n",
3164- stream->index[i - 1].Logical());
3165+ node.Index(slot)->Logical());
3166 return B_ERROR;
3167 }
3168- stream = (btrfs_stream*)cached.SetTo(physical);
3169- }
3170-
3171- uint32 i;
3172-#ifdef TRACE_BTRFS
3173- TRACE("Find() dump count %" B_PRId32 "\n", stream->header.ItemCount());
3174- for (i = 0; i < stream->header.ItemCount(); i++) {
3175- int32 comp = key.Compare(stream->entries[i].key);
3176- TRACE("Find() dump %" B_PRIu32 " %" B_PRIu32 " offset %" B_PRId64
3177- " comp %" B_PRId32 "\n", stream->entries[i].Offset(),
3178- stream->entries[i].Size(), stream->entries[i].key.Offset(), comp);
3179- }
3180-#endif
3181-
3182- for (i = 0; i < stream->header.ItemCount(); i++) {
3183- int32 comp = key.Compare(stream->entries[i].key);
3184- TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 " oid %" B_PRId64
3185- " type %d offset %" B_PRId64 " comp %" B_PRId32 "\n",
3186- stream->entries[i].Offset(), stream->entries[i].Size(),
3187- stream->entries[i].key.ObjectID(), stream->entries[i].key.Type(),
3188- stream->entries[i].key.Offset(), comp);
3189- if (comp == 0)
3190- break;
3191- if (comp < 0 && i > 0) {
3192- if (type == BTREE_EXACT)
3193- return B_ENTRY_NOT_FOUND;
3194- if (type == BTREE_BACKWARD)
3195- i--;
3196- break;
3197- }
3198+ node.SetTo(physicalBlock);
3199 }
3200
3201- if (i == stream->header.ItemCount()) {
3202- if (type == BTREE_BACKWARD)
3203- i--;
3204- else
3205- return B_ENTRY_NOT_FOUND;
3206- }
3207+ TRACE("Find() dump count %" B_PRId32 "\n", node.ItemCount());
3208+ ret = node.SearchSlot(key, &slot, type);
3209
3210- if (i < stream->header.ItemCount()
3211- && stream->entries[i].key.Type() == key.Type()) {
3212+ if ( ret == B_OK && node.Item(slot)->key.Type() == key.Type()) {
3213 TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
3214- stream->entries[i].Offset(), stream->entries[i].Size());
3215+ node.Item(slot)->Offset(), node.Item(slot)->Size());
3216
3217 if (_value != NULL) {
3218- *_value = malloc(stream->entries[i].Size());
3219- memcpy(*_value, ((uint8 *)&stream->entries[0]
3220- + stream->entries[i].Offset()),
3221- stream->entries[i].Size());
3222- key.SetOffset(stream->entries[i].key.Offset());
3223+ *_value = malloc(node.Item(slot)->Size());
3224+ memcpy(*_value, node.ItemData(slot),
3225+ node.Item(slot)->Size());
3226+ key.SetOffset(node.Item(slot)->key.Offset());
3227 if (_size != NULL)
3228- *_size = stream->entries[i].Size();
3229+ *_size = node.Item(slot)->Size();
3230 }
3231 return B_OK;
3232 }
3233diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3234index 4e9e7e5..aaaf5a6 100644
3235--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3236+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3237@@ -131,7 +131,6 @@ private:
3238 private:
3239 friend class TreeIterator;
3240
3241- btrfs_stream* fStream;
3242 fsblock_t fRootBlock;
3243 Volume* fVolume;
3244 mutex fIteratorLock;
3245--
32462.7.0
3247
3248
3249From 9b71fad18e6a870e24020221d91488dcba702833 Mon Sep 17 00:00:00 2001
3250From: hyche <cvghy116@gmail.com>
3251Date: Fri, 23 Jun 2017 17:37:55 +0700
3252Subject: [PATCH 17/36] BTRFS: Some modifications for Volume.cpp * Removed
3253 redundant codes when mounting roots * Added TRACE * Finding root should be
3254 "FindExact" to make it more understandable.
3255
3256---
3257 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 33 +++++-------------------
3258 1 file changed, 7 insertions(+), 26 deletions(-)
3259
3260diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
3261index 36dac6c..6c923ee 100644
3262--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
3263+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
3264@@ -288,19 +288,6 @@ Volume::Mount(const char* deviceName, uint32 flags)
3265 start += sizeof(btrfs_key) + fChunk->Size();
3266 }
3267
3268- TRACE("Volume::Mount() generation: %" B_PRIu64 "\n",
3269- fSuperBlock.Generation());
3270- fsblock_t physical = 0;
3271- FindBlock(fSuperBlock.Root(), physical);
3272- TRACE("Volume::Mount() root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
3273- fSuperBlock.Root(), physical);
3274- FindBlock(fSuperBlock.ChunkRoot(), physical);
3275- TRACE("Volume::Mount() chunk_root: %" B_PRIu64 " (physical %" B_PRIu64
3276- ")\n", fSuperBlock.ChunkRoot(), physical);
3277- FindBlock(fSuperBlock.LogRoot(), physical);
3278- TRACE("Volume::Mount() log_root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
3279- fSuperBlock.LogRoot(), physical);
3280-
3281 // check if the device size is large enough to hold the file system
3282 off_t diskSize;
3283 status = opener.GetSize(&diskSize);
3284@@ -322,15 +309,6 @@ Volume::Mount(const char* deviceName, uint32 flags)
3285 fChunkTree->SetRoot(fSuperBlock.ChunkRoot(), NULL);
3286 TRACE("Volume::Mount() chunk_root: %" B_PRIu64 " (physical block %" B_PRIu64
3287 ")\n", fSuperBlock.ChunkRoot(), fChunkTree->RootBlock());
3288- FindBlock(fSuperBlock.Root(), physical);
3289- TRACE("Volume::Mount() root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
3290- fSuperBlock.Root(), physical);
3291- FindBlock(fSuperBlock.ChunkRoot(), physical);
3292- TRACE("Volume::Mount() chunk_root: %" B_PRIu64 " (physical %" B_PRIu64
3293- ")\n", fSuperBlock.ChunkRoot(), physical);
3294- FindBlock(fSuperBlock.LogRoot(), physical);
3295- TRACE("Volume::Mount() log_root: %" B_PRIu64 " (physical %" B_PRIu64 ")\n",
3296- fSuperBlock.LogRoot(), physical);
3297
3298 fRootTree = new(std::nothrow) BTree(this);
3299 if (fRootTree == NULL)
3300@@ -345,7 +323,7 @@ Volume::Mount(const char* deviceName, uint32 flags)
3301 search_key.SetType(BTRFS_KEY_TYPE_ROOT_ITEM);
3302 search_key.SetObjectID(BTRFS_OBJECT_ID_EXTENT_TREE);
3303 btrfs_root* root;
3304- if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
3305+ if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
3306 ERROR("Volume::Mount(): Couldn't find extent root\n");
3307 return B_ERROR;
3308 }
3309@@ -357,9 +335,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
3310 fExtentTree->SetRoot(root->Logical(), NULL);
3311 free(root);
3312
3313+ TRACE("Volume::Mount(): Searching fs root\n");
3314 search_key.SetOffset(0);
3315 search_key.SetObjectID(BTRFS_OBJECT_ID_FS_TREE);
3316- if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
3317+ if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
3318 ERROR("Volume::Mount(): Couldn't find fs root\n");
3319 return B_ERROR;
3320 }
3321@@ -370,9 +349,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
3322 fFSTree->SetRoot(root->Logical(), NULL);
3323 free(root);
3324
3325+ TRACE("Volume::Mount(): Searching dev root\n");
3326 search_key.SetOffset(0);
3327 search_key.SetObjectID(BTRFS_OBJECT_ID_DEV_TREE);
3328- if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
3329+ if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
3330 ERROR("Volume::Mount(): Couldn't find dev root\n");
3331 return B_ERROR;
3332 }
3333@@ -384,9 +364,10 @@ Volume::Mount(const char* deviceName, uint32 flags)
3334 fDevTree->SetRoot(root->Logical(), NULL);
3335 free(root);
3336
3337+ TRACE("Volume::Mount(): Searching checksum root\n");
3338 search_key.SetOffset(0);
3339 search_key.SetObjectID(BTRFS_OBJECT_ID_CHECKSUM_TREE);
3340- if (fRootTree->FindNext(search_key, (void**)&root) != B_OK) {
3341+ if (fRootTree->FindExact(search_key, (void**)&root) != B_OK) {
3342 ERROR("Volume::Mount(): Couldn't find checksum root\n");
3343 return B_ERROR;
3344 }
3345--
33462.7.0
3347
3348
3349From 53b5221a2031c95017047b21a46ce9e155fbae9b Mon Sep 17 00:00:00 2001
3350From: hyche <cvghy116@gmail.com>
3351Date: Mon, 26 Jun 2017 22:26:51 +0700
3352Subject: [PATCH 18/36] BTRFS: Changed name BNode and BPath to BTreeNode and
3353 BTreePath as the original names are already exist in Haiku Storage Kit.
3354
3355---
3356 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 18 +++++++++---------
3357 src/add-ons/kernel/file_systems/btrfs/BTree.h | 21 +++++++++++++--------
3358 2 files changed, 22 insertions(+), 17 deletions(-)
3359
3360diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3361index 87edf86..870fd37 100644
3362--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3363+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3364@@ -21,7 +21,7 @@
3365 # define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
3366
3367
3368-BNode::BNode(void* cache)
3369+BTreeNode::BTreeNode(void* cache)
3370 :
3371 fNode(NULL),
3372 fCache(cache),
3373@@ -32,7 +32,7 @@ BNode::BNode(void* cache)
3374 }
3375
3376
3377-BNode::BNode(void* cache, off_t block)
3378+BTreeNode::BTreeNode(void* cache, off_t block)
3379 :
3380 fNode(NULL),
3381 fCache(cache),
3382@@ -44,20 +44,20 @@ BNode::BNode(void* cache, off_t block)
3383 }
3384
3385
3386-BNode::~BNode()
3387+BTreeNode::~BTreeNode()
3388 {
3389 Unset();
3390 }
3391
3392
3393 void
3394-BNode::Keep()
3395+BTreeNode::Keep()
3396 {
3397 fNode = NULL;
3398 }
3399
3400 void
3401-BNode::Unset()
3402+BTreeNode::Unset()
3403 {
3404 if (fNode != NULL) {
3405 block_cache_put(fCache, fBlockNumber);
3406@@ -67,7 +67,7 @@ BNode::Unset()
3407
3408
3409 void
3410-BNode::SetTo(off_t block)
3411+BTreeNode::SetTo(off_t block)
3412 {
3413 Unset();
3414 fBlockNumber = block;
3415@@ -76,7 +76,7 @@ BNode::SetTo(off_t block)
3416
3417
3418 void
3419-BNode::SetToWritable(off_t block, int32 transactionId, bool empty)
3420+BTreeNode::SetToWritable(off_t block, int32 transactionId, bool empty)
3421 {
3422 Unset();
3423 fBlockNumber = block;
3424@@ -92,7 +92,7 @@ BNode::SetToWritable(off_t block, int32 transactionId, bool empty)
3425
3426
3427 int32
3428-BNode::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
3429+BTreeNode::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
3430 {
3431 //binary search for item slot in a node
3432 int entrySize = sizeof(btrfs_entry);
3433@@ -209,7 +209,7 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
3434 TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
3435 key.ObjectID(), key.Type(), key.Offset());
3436 CachedBlock cached(fVolume);
3437- BNode node(fVolume->BlockCache(), fRootBlock);
3438+ BTreeNode node(fVolume->BlockCache(), fRootBlock);
3439 int slot, ret;
3440 fsblock_t physicalBlock;
3441
3442diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3443index aaaf5a6..da6dee9 100644
3444--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3445+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3446@@ -41,11 +41,11 @@ struct node_and_key {
3447 };
3448
3449
3450-class BNode {
3451+class BTreeNode {
3452 public:
3453- BNode(void* cache);
3454- BNode(void* cache, off_t block);
3455- ~BNode();
3456+ BTreeNode(void* cache);
3457+ BTreeNode(void* cache, off_t block);
3458+ ~BTreeNode();
3459
3460 // just return from Header
3461 uint64 Logical() const
3462@@ -83,8 +83,8 @@ public:
3463 int32 SearchSlot(const btrfs_key& key, int* slot,
3464 btree_traversing type) const;
3465 private:
3466- BNode(const BNode&);
3467- BNode& operator=(const BNode&);
3468+ BTreeNode(const BTreeNode&);
3469+ BTreeNode& operator=(const BTreeNode&);
3470 //no implementation
3471
3472 btrfs_stream* fNode;
3473@@ -95,8 +95,13 @@ private:
3474 };
3475
3476
3477-class BPath {
3478- BNode* nodes[BTRFS_MAX_TREE_DEPTH];
3479+class BTreePath {
3480+public:
3481+ BTreePath();
3482+private:
3483+ BTreePath(const BTreePath&);
3484+ BTreePath operator=(const BTreePath&);
3485+ BTreeNode* nodes[BTRFS_MAX_TREE_DEPTH];
3486 };
3487
3488
3489--
34902.7.0
3491
3492
3493From 756cecd47fa3d42a94178a97d83d61a99c47ce19 Mon Sep 17 00:00:00 2001
3494From: hyche <cvghy116@gmail.com>
3495Date: Mon, 26 Jun 2017 23:04:51 +0700
3496Subject: [PATCH 19/36] Btrfs: Added logical address (root) for BTree
3497
3498---
3499 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 2 ++
3500 src/add-ons/kernel/file_systems/btrfs/BTree.h | 3 ++-
3501 2 files changed, 4 insertions(+), 1 deletion(-)
3502
3503diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3504index 870fd37..45cc3f1 100644
3505--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3506+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
3507@@ -281,7 +281,9 @@ BTree::SetRoot(off_t logical, fsblock_t* block)
3508 {
3509 if (block != NULL) {
3510 fRootBlock = *block;
3511+ //TODO: mapping physical block -> logical address
3512 } else {
3513+ fLogicalRoot = logical;
3514 if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
3515 ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
3516 return B_ERROR;
3517diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3518index da6dee9..3641448 100644
3519--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3520+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3521@@ -121,8 +121,8 @@ public:
3522 size_t* size = NULL);
3523
3524 status_t SetRoot(off_t logical, fsblock_t* block);
3525-
3526 fsblock_t RootBlock() const { return fRootBlock; }
3527+ off_t LogicalRoot() const { return fLogicalRoot; }
3528
3529 private:
3530 BTree(const BTree& other);
3531@@ -137,6 +137,7 @@ private:
3532 friend class TreeIterator;
3533
3534 fsblock_t fRootBlock;
3535+ off_t fLogicalRoot;
3536 Volume* fVolume;
3537 mutex fIteratorLock;
3538 SinglyLinkedList<TreeIterator> fIterators;
3539--
35402.7.0
3541
3542
3543From eab9b738eafbd0243865490f4780446b9b765136 Mon Sep 17 00:00:00 2001
3544From: hyche <cvghy116@gmail.com>
3545Date: Sat, 1 Jul 2017 00:10:27 +0700
3546Subject: [PATCH 20/36] btrfs_shell: Support AVLTree
3547
3548---
3549 headers/private/kernel/util/AVLTreeBase.h | 7 +++++-
3550 .../file_systems/btrfs/system_dependencies.h | 2 ++
3551 src/system/kernel/util/AVLTreeBase.cpp | 28 ++++++++++++----------
3552 src/tools/btrfs_shell/Jamfile | 10 +++++++-
3553 4 files changed, 33 insertions(+), 14 deletions(-)
3554
3555diff --git a/headers/private/kernel/util/AVLTreeBase.h b/headers/private/kernel/util/AVLTreeBase.h
3556index 6c9bd7b..6e5cfac 100644
3557--- a/headers/private/kernel/util/AVLTreeBase.h
3558+++ b/headers/private/kernel/util/AVLTreeBase.h
3559@@ -6,7 +6,12 @@
3560 #define _KERNEL_UTIL_AVL_TREE_BASE_H
3561
3562
3563-#include <SupportDefs.h>
3564+#ifndef FS_SHELL
3565+# include <SupportDefs.h>
3566+#else
3567+# include <algorithm>
3568+# include "fssh_api_wrapper.h"
3569+#endif
3570
3571
3572 class AVLTreeIterator;
3573diff --git a/src/add-ons/kernel/file_systems/btrfs/system_dependencies.h b/src/add-ons/kernel/file_systems/btrfs/system_dependencies.h
3574index dd337be..578e276 100644
3575--- a/src/add-ons/kernel/file_systems/btrfs/system_dependencies.h
3576+++ b/src/add-ons/kernel/file_systems/btrfs/system_dependencies.h
3577@@ -7,6 +7,7 @@
3578 // This needs to be included before the fs_shell wrapper
3579 #include <zlib.h>
3580 #include <new>
3581+#include <util/AVLTree.h>
3582
3583 #include "fssh_api_wrapper.h"
3584 #include "fssh_auto_deleter.h"
3585@@ -18,6 +19,7 @@
3586 #include <util/AutoLock.h>
3587 #include <util/SinglyLinkedList.h>
3588 #include <util/Stack.h>
3589+#include <util/AVLTree.h>
3590 #include <sys/stat.h>
3591 #include <sys/types.h>
3592 #include <ByteOrder.h>
3593diff --git a/src/system/kernel/util/AVLTreeBase.cpp b/src/system/kernel/util/AVLTreeBase.cpp
3594index 91c3ff0..af473e8 100644
3595--- a/src/system/kernel/util/AVLTreeBase.cpp
3596+++ b/src/system/kernel/util/AVLTreeBase.cpp
3597@@ -6,22 +6,26 @@
3598
3599 #include <util/AVLTreeBase.h>
3600
3601-#include <algorithm>
3602-
3603-#include <KernelExport.h>
3604-
3605+#ifndef FS_SHELL
3606+# include <algorithm>
3607+# include <KernelExport.h>
3608+#endif
3609
3610 #ifdef _KERNEL_MODE
3611 # define CHECK_FAILED(message...) panic(message)
3612 #else
3613-# include <stdio.h>
3614-# include <OS.h>
3615-# define CHECK_FAILED(message...) \
3616- do { \
3617- fprintf(stderr, message); \
3618- fprintf(stderr, "\n"); \
3619- debugger("AVLTreeBase check failed"); \
3620- } while (false)
3621+# ifndef FS_SHELL
3622+# include <stdio.h>
3623+# include <OS.h>
3624+# define CHECK_FAILED(message...) \
3625+ do { \
3626+ fprintf(stderr, message); \
3627+ fprintf(stderr, "\n"); \
3628+ debugger("AVLTreeBase check failed"); \
3629+ } while (false)
3630+# else
3631+# define CHECK_FAILED(message...) dprintf(message)
3632+# endif
3633 #endif
3634
3635
3636diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
3637index dcf071e..5502c7e 100644
3638--- a/src/tools/btrfs_shell/Jamfile
3639+++ b/src/tools/btrfs_shell/Jamfile
3640@@ -33,6 +33,7 @@ if ! $(HOST_PLATFORM_BEOS_COMPATIBLE) {
3641 UseHeaders [ FDirName $(HAIKU_TOP) headers build os support ] : true ;
3642 }
3643
3644+UsePrivateKernelHeaders ;
3645 UsePrivateHeaders shared storage fs_shell ;
3646 UseHeaders [ FDirName $(HAIKU_TOP) headers private ] : true ;
3647 UseHeaders [ FDirName $(HAIKU_TOP) src tools fs_shell ] ;
3648@@ -49,7 +50,11 @@ local btrfsSources =
3649 kernel_interface.cpp
3650 ;
3651
3652-BuildPlatformMergeObject <build>btrfs.o : $(btrfsSources) ;
3653+local utilitySources =
3654+ AVLTreeBase.cpp
3655+;
3656+
3657+BuildPlatformMergeObject <build>btrfs.o : $(btrfsSources) $(utilitySources) ;
3658
3659 BuildPlatformMain <build>btrfs_shell
3660 :
3661@@ -60,3 +65,6 @@ BuildPlatformMain <build>btrfs_shell
3662 <build>fs_shell.a $(libHaikuCompat) $(HOST_LIBSUPC++) $(HOST_LIBSTDC++)
3663 $(HOST_LIBROOT) $(fsShellCommandLibs)
3664 ;
3665+
3666+SEARCH on [ FGristFiles $(utilitySources) ]
3667+ += [ FDirName $(HAIKU_TOP) src system kernel util ] ;
3668--
36692.7.0
3670
3671
3672From 2affed2d312b6fb8153e07a18899601b1b6165d7 Mon Sep 17 00:00:00 2001
3673From: hyche <cvghy116@gmail.com>
3674Date: Sun, 2 Jul 2017 23:53:20 +0700
3675Subject: [PATCH 21/36] BtrFS: Added more on-disk data structures
3676
3677---
3678 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 110 +++++++++++++++++++++++++-
3679 1 file changed, 109 insertions(+), 1 deletion(-)
3680
3681diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
3682index d7b9fef..49ea7f3 100644
3683--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
3684+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
3685@@ -12,8 +12,61 @@
3686 typedef uint64 fileblock_t; // file block number
3687 typedef uint64 fsblock_t; // filesystem block number
3688
3689-
3690 #define BTRFS_SUPER_BLOCK_OFFSET 0x10000
3691+#define BTRFS_NUM_ROOT_BACKUPS 4
3692+
3693+
3694+struct btrfs_backup_roots {
3695+ uint64 root;
3696+ uint64 root_generation;
3697+ uint64 chunk_root;
3698+ uint64 chunk_root_generation;
3699+ uint64 extent_root;
3700+ uint64 extent_root_generation;
3701+ uint64 fs_root;
3702+ uint64 fs_root_generation;
3703+ uint64 device_root;
3704+ uint64 device_root_generation;
3705+ uint64 csum_root;
3706+ uint64 csum_root_generation;
3707+ uint64 total_size;
3708+ uint64 used_size;
3709+ uint64 num_devices;
3710+ uint8 unused_1[32];
3711+ uint8 root_level;
3712+ uint8 chunk_root_level;
3713+ uint8 extent_root_level;
3714+ uint8 fs_root_level;
3715+ uint8 device_root_level;
3716+ uint8 csum_root_level;
3717+ uint8 unused_2[10];
3718+
3719+ uint64 Root() const { return B_LENDIAN_TO_HOST_INT64(root); }
3720+ uint64 RootGen() const
3721+ { return B_LENDIAN_TO_HOST_INT64(root_generation); }
3722+ uint64 ChunkRoot() const { return B_LENDIAN_TO_HOST_INT64(chunk_root); }
3723+ uint64 ChunkRootGen() const
3724+ { return B_LENDIAN_TO_HOST_INT64(chunk_root_generation); }
3725+ uint64 ExtentRoot() const { return B_LENDIAN_TO_HOST_INT64(extent_root); }
3726+ uint64 ExtentRootGen() const
3727+ { return B_LENDIAN_TO_HOST_INT64(extent_root_generation); }
3728+ uint64 FSRoot() const { return B_LENDIAN_TO_HOST_INT64(fs_root); }
3729+ uint64 FSRootGen() const
3730+ { return B_LENDIAN_TO_HOST_INT64(fs_root_generation); }
3731+ uint64 DeviceRoot() const { return B_LENDIAN_TO_HOST_INT64(device_root); }
3732+ uint64 DeviceRootGen() const
3733+ { return B_LENDIAN_TO_HOST_INT64(device_root_generation); }
3734+ uint64 CSumRoot() const { return B_LENDIAN_TO_HOST_INT64(csum_root); }
3735+ uint64 CSumRootGen() const
3736+ { return B_LENDIAN_TO_HOST_INT64(csum_root_generation); }
3737+ uint8 RootLevel() const { return root_level; }
3738+ uint8 ChunkRootLevel() const { return chunk_root_level; }
3739+ uint8 ExtentRootLevel() const { return extent_root_level; }
3740+ uint8 FSRootLevel() const { return fs_root_level; }
3741+ uint8 DeviceRootLevel() const { return device_root_level; }
3742+ uint8 CSumRootLevel() const { return csum_root_level; }
3743+} _PACKED;
3744+
3745
3746 struct btrfs_key {
3747 uint64 object_id;
3748@@ -175,6 +228,7 @@ struct btrfs_super_block {
3749 char label[256];
3750 uint64 reserved[32];
3751 uint8 system_chunk_array[2048];
3752+ btrfs_backup_roots backup_roots[BTRFS_NUM_ROOT_BACKUPS];
3753
3754 bool IsValid();
3755 // implemented in Volume.cpp
3756@@ -237,6 +291,16 @@ struct btrfs_inode {
3757 } _PACKED;
3758
3759
3760+struct btrfs_inode_ref {
3761+ uint8 index;
3762+ uint16 name_length;
3763+ uint8 name[];
3764+
3765+ uint8 Index() const { return index; }
3766+ uint16 NameLength() const { return B_LENDIAN_TO_HOST_INT16(name_length); }
3767+} _PACKED;
3768+
3769+
3770 struct btrfs_root {
3771 btrfs_inode inode;
3772 uint64 generation;
3773@@ -303,6 +367,50 @@ struct btrfs_extent_data {
3774 } _PACKED;
3775
3776
3777+struct btrfs_block_group {
3778+ uint64 used_space;
3779+ uint64 chunk_object_id;
3780+ uint64 flags;
3781+
3782+ uint64 UsedSpace() const { return used_space; }
3783+ uint64 ChunkObjectID() const { return chunk_object_id; }
3784+ uint64 Flags() const { return flags; }
3785+} _PACKED;
3786+
3787+
3788+struct btrfs_extent {
3789+ uint64 refs;
3790+ uint64 generation;
3791+ uint64 flags;
3792+
3793+ uint64 RefCount() const { return B_LENDIAN_TO_HOST_INT64(refs); }
3794+ uint64 Generation() const { return B_LENDIAN_TO_HOST_INT64(generation); }
3795+ uint64 Flags() const { return B_LENDIAN_TO_HOST_INT64(flags); }
3796+} _PACKED;
3797+
3798+
3799+struct btrfs_extent_inline_ref {
3800+ uint8 type;
3801+ uint64 offset;
3802+
3803+ uint8 Type() const { return type; }
3804+ uint64 Offset() const { return B_LENDIAN_TO_HOST_INT64(offset); }
3805+} _PACKED;
3806+
3807+
3808+struct btrfs_extent_data_ref {
3809+ uint64 root_id;
3810+ uint64 inode_id;
3811+ uint64 offset;
3812+ uint32 ref_count;
3813+
3814+ uint64 RootID() const { return B_LENDIAN_TO_HOST_INT64(root_id); }
3815+ uint64 InodeID() const { return B_LENDIAN_TO_HOST_INT64(inode_id); }
3816+ uint64 Offset() const { return B_LENDIAN_TO_HOST_INT64(offset);}
3817+ uint32 RefCount() const { return B_LENDIAN_TO_HOST_INT32(ref_count); }
3818+} _PACKED;
3819+
3820+
3821 #define BTRFS_SUPER_BLOCK_MAGIC "_BHRfS_M"
3822 #define BTRFS_FIRST_SUBVOLUME 256
3823
3824--
38252.7.0
3826
3827
3828From 66850de665bf9c208d246b3515474993ae72cbda Mon Sep 17 00:00:00 2001
3829From: hyche <cvghy116@gmail.com>
3830Date: Sun, 2 Jul 2017 23:55:42 +0700
3831Subject: [PATCH 22/36] BtrFS: Added flags and key types
3832
3833---
3834 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 26 +++++++++++++++++++++-----
3835 1 file changed, 21 insertions(+), 5 deletions(-)
3836
3837diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
3838index 49ea7f3..5549258 100644
3839--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
3840+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
3841@@ -423,22 +423,38 @@ struct btrfs_extent_data_ref {
3842 #define BTRFS_OBJECT_ID_CHECKSUM_TREE 7
3843 #define BTRFS_OBJECT_ID_FIRST_CHUNK_TREE 256
3844
3845-#define BTRFS_KEY_TYPE_CHUNK_ITEM 228
3846+#define BTRFS_KEY_TYPE_INODE_ITEM 1
3847+#define BTRFS_KEY_TYPE_INODE_REF 12
3848+#define BTRFS_KEY_TYPE_XATTR_ITEM 24
3849 #define BTRFS_KEY_TYPE_DIR_ITEM 84
3850 #define BTRFS_KEY_TYPE_DIR_INDEX 96
3851 #define BTRFS_KEY_TYPE_EXTENT_DATA 108
3852-#define BTRFS_KEY_TYPE_INODE_ITEM 1
3853-#define BTRFS_KEY_TYPE_INODE_REF 12
3854 #define BTRFS_KEY_TYPE_ROOT_ITEM 132
3855-#define BTRFS_KEY_TYPE_XATTR_ITEM 24
3856+#define BTRFS_KEY_TYPE_EXTENT_ITEM 168
3857+#define BTRFS_KEY_TYPE_METADATA_ITEM 169
3858+#define BTRFS_KEY_TYPE_EXTENT_DATA_REF 178
3859+#define BTRFS_KEY_TYPE_BLOCKGROUP_ITEM 192
3860+#define BTRFS_KEY_TYPE_CHUNK_ITEM 228
3861
3862 #define BTRFS_EXTENT_COMPRESS_NONE 0
3863 #define BTRFS_EXTENT_COMPRESS_ZLIB 1
3864 #define BTRFS_EXTENT_COMPRESS_LZO 2
3865-
3866 #define BTRFS_EXTENT_DATA_INLINE 0
3867 #define BTRFS_EXTENT_DATA_REGULAR 1
3868 #define BTRFS_EXTENT_DATA_PRE 2
3869+#define BTRFS_EXTENT_FLAG_DATA 1
3870+#define BTRFS_EXTENT_FLAG_TREE_BLOCK 2
3871+
3872+#define BTRFS_BLOCKGROUP_FLAG_DATA 1
3873+#define BTRFS_BLOCKGROUP_FLAG_SYSTEM 2
3874+#define BTRFS_BLOCKGROUP_FLAG_METADA 4
3875+#define BTRFS_BLOCKGROUP_FLAG_RAID0 8
3876+#define BTRFS_BLOCKGROUP_FLAG_RAID1 16
3877+#define BTRFS_BLOCKGROUP_FLAG_DUP 32
3878+#define BTRFS_BLOCKGROUP_FLAG_RAID10 64
3879+#define BTRFS_BLOCKGROUP_FLAG_RAID5 128
3880+#define BTRFS_BLOCKGROUP_FLAG_RAID6 256
3881+#define BTRFS_BLOCKGROUP_FLAG_MASK 512
3882
3883
3884 struct file_cookie {
3885--
38862.7.0
3887
3888
3889From 5314db1c524a05839ab3c3ff30ee0ed686f42b15 Mon Sep 17 00:00:00 2001
3890From: hyche <cvghy116@gmail.com>
3891Date: Tue, 4 Jul 2017 23:51:02 +0700
3892Subject: [PATCH 23/36] Volume: Fixex coding style and added retrieve more
3893 fields
3894
3895---
3896 src/add-ons/kernel/file_systems/btrfs/Volume.h | 14 ++++++++------
3897 1 file changed, 8 insertions(+), 6 deletions(-)
3898
3899diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.h b/src/add-ons/kernel/file_systems/btrfs/Volume.h
3900index 6561087..7889336 100644
3901--- a/src/add-ons/kernel/file_systems/btrfs/Volume.h
3902+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.h
3903@@ -39,10 +39,12 @@ public:
3904 fs_volume* FSVolume() const { return fFSVolume; }
3905 const char* Name() const;
3906 BTree* FSTree() const { return fFSTree; }
3907+ BTree* ExtentTree() const { return fExtentTree; }
3908 BTree* RootTree() const { return fRootTree; }
3909
3910 uint32 SectorSize() const { return fSectorSize; }
3911 uint32 BlockSize() const { return fBlockSize; }
3912+ Chunk* SystemChunk() const { return fChunk; }
3913
3914 btrfs_super_block& SuperBlock() { return fSuperBlock; }
3915
3916@@ -71,12 +73,12 @@ private:
3917 Inode* fRootNode;
3918
3919 Chunk* fChunk;
3920- BTree* fChunkTree;
3921- BTree* fRootTree;
3922- BTree* fDevTree;
3923- BTree* fExtentTree;
3924- BTree* fFSTree;
3925- BTree* fChecksumTree;
3926+ BTree* fChunkTree;
3927+ BTree* fRootTree;
3928+ BTree* fDevTree;
3929+ BTree* fExtentTree;
3930+ BTree* fFSTree;
3931+ BTree* fChecksumTree;
3932 };
3933
3934
3935--
39362.7.0
3937
3938
3939From 4e041a19888709680dd144f930503ee70e2d5aee Mon Sep 17 00:00:00 2001
3940From: hyche <cvghy116@gmail.com>
3941Date: Wed, 5 Jul 2017 00:00:49 +0700
3942Subject: [PATCH 24/36] Btrfs: LogicalRoot -> Logical (BTree) and added
3943 retrieve Volume
3944
3945---
3946 src/add-ons/kernel/file_systems/btrfs/BTree.h | 4 +++-
3947 1 file changed, 3 insertions(+), 1 deletion(-)
3948
3949diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3950index 3641448..3ded002 100644
3951--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3952+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3953@@ -120,9 +120,11 @@ public:
3954 status_t FindPrevious(btrfs_key& key, void** value,
3955 size_t* size = NULL);
3956
3957+ Volume* SystemVolume() const { return fVolume; }
3958+
3959 status_t SetRoot(off_t logical, fsblock_t* block);
3960 fsblock_t RootBlock() const { return fRootBlock; }
3961- off_t LogicalRoot() const { return fLogicalRoot; }
3962+ off_t Logical() const { return fLogicalRoot; }
3963
3964 private:
3965 BTree(const BTree& other);
3966--
39672.7.0
3968
3969
3970From af909636d2fc546e5ef56deca623a241844fb45f Mon Sep 17 00:00:00 2001
3971From: hyche <cvghy116@gmail.com>
3972Date: Wed, 5 Jul 2017 00:04:54 +0700
3973Subject: [PATCH 25/36] Btrfs: Fixed coding style (BTree)
3974
3975---
3976 src/add-ons/kernel/file_systems/btrfs/BTree.h | 50 +++++++++++++--------------
3977 1 file changed, 25 insertions(+), 25 deletions(-)
3978
3979diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3980index 3ded002..3dcbe82 100644
3981--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
3982+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
3983@@ -47,38 +47,38 @@ public:
3984 BTreeNode(void* cache, off_t block);
3985 ~BTreeNode();
3986
3987- // just return from Header
3988- uint64 Logical() const
3989- { return fNode->header.Logical(); }
3990- uint64 Flags() const
3991- { return fNode->header.Flags(); }
3992- uint64 Generation() const
3993- { return fNode->header.Generation(); }
3994- uint64 Owner() const
3995- { return fNode->header.Owner(); }
3996- uint32 ItemCount() const
3997- { return fNode->header.ItemCount(); }
3998- uint8 Level() const
3999- { return fNode->header.Level(); }
4000-
4001- btrfs_index* Index(uint32 i) const
4002+ // just return from Header
4003+ uint64 Logical() const
4004+ { return fNode->header.Logical(); }
4005+ uint64 Flags() const
4006+ { return fNode->header.Flags(); }
4007+ uint64 Generation() const
4008+ { return fNode->header.Generation(); }
4009+ uint64 Owner() const
4010+ { return fNode->header.Owner(); }
4011+ uint32 ItemCount() const
4012+ { return fNode->header.ItemCount(); }
4013+ uint8 Level() const
4014+ { return fNode->header.Level(); }
4015+
4016+ btrfs_index* Index(uint32 i) const
4017 { return &fNode->index[i]; }
4018
4019- btrfs_entry* Item(uint32 i) const
4020- { return &fNode->entries[i]; }
4021- uint8* ItemData(uint32 i) const
4022- { return (uint8*)Item(0) + Item(i)->Offset(); }
4023+ btrfs_entry* Item(uint32 i) const
4024+ { return &fNode->entries[i]; }
4025+ uint8* ItemData(uint32 i) const
4026+ { return (uint8*)Item(0) + Item(i)->Offset(); }
4027
4028- void Keep();
4029- void Unset();
4030+ void Keep();
4031+ void Unset();
4032
4033
4034- void SetTo(off_t block);
4035- void SetToWritable(off_t block,
4036+ void SetTo(off_t block);
4037+ void SetToWritable(off_t block,
4038 int32 transactionId, bool empty);
4039
4040- off_t BlockNum() const { return fBlockNumber;}
4041- bool IsWritable() const { return fWritable; }
4042+ off_t BlockNum() const { return fBlockNumber;}
4043+ bool IsWritable() const { return fWritable; }
4044
4045 int32 SearchSlot(const btrfs_key& key, int* slot,
4046 btree_traversing type) const;
4047--
40482.7.0
4049
4050
4051From 40d013209a754df08702b02a651cb1d87191e395 Mon Sep 17 00:00:00 2001
4052From: hyche <cvghy116@gmail.com>
4053Date: Wed, 5 Jul 2017 00:08:54 +0700
4054Subject: [PATCH 26/36] Btrfs: Some modifications of BTree _Find * Added "read"
4055 argument, may change variable type in the future instead of just bool
4056 variable. * Now search key's objectId is changed to found key's objectId.
4057
4058---
4059 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 36 ++++++++++++++-----------
4060 src/add-ons/kernel/file_systems/btrfs/BTree.h | 14 +++++-----
4061 2 files changed, 27 insertions(+), 23 deletions(-)
4062
4063diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4064index 45cc3f1..f661aec 100644
4065--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4066+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4067@@ -204,7 +204,7 @@ btrfs_key::Compare(const btrfs_key& key) const
4068 */
4069 status_t
4070 BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
4071- btree_traversing type)
4072+ bool read, btree_traversing type)
4073 {
4074 TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
4075 key.ObjectID(), key.Type(), key.Offset());
4076@@ -231,8 +231,15 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
4077
4078 TRACE("Find() dump count %" B_PRId32 "\n", node.ItemCount());
4079 ret = node.SearchSlot(key, &slot, type);
4080+ if ((slot >= node.ItemCount() || node.Item(slot)->key.Type() != key.Type())
4081+ && read == true
4082+ || ret != B_OK) {
4083+ TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n", key.Offset(),
4084+ key.ObjectID());
4085+ return B_ENTRY_NOT_FOUND;
4086+ }
4087
4088- if ( ret == B_OK && node.Item(slot)->key.Type() == key.Type()) {
4089+ if (read == true) {
4090 TRACE("Find() found %" B_PRIu32 " %" B_PRIu32 "\n",
4091 node.Item(slot)->Offset(), node.Item(slot)->Size());
4092
4093@@ -241,38 +248,35 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
4094 memcpy(*_value, node.ItemData(slot),
4095 node.Item(slot)->Size());
4096 key.SetOffset(node.Item(slot)->key.Offset());
4097+ key.SetObjectID(node.Item(slot)->key.ObjectID());
4098 if (_size != NULL)
4099 *_size = node.Item(slot)->Size();
4100 }
4101- return B_OK;
4102+ } else {
4103+ *_value = (void*)&slot;
4104 }
4105-
4106-
4107- TRACE("Find() not found %" B_PRId64 " %" B_PRId64 "\n", key.Offset(),
4108- key.ObjectID());
4109-
4110- return B_ENTRY_NOT_FOUND;
4111+ return B_OK;
4112 }
4113
4114
4115 status_t
4116-BTree::FindNext(btrfs_key& key, void** _value, size_t* _size)
4117+BTree::FindNext(btrfs_key& key, void** _value, size_t* _size, bool read)
4118 {
4119- return _Find(key, _value, _size, BTREE_FORWARD);
4120+ return _Find(key, _value, _size, read, BTREE_FORWARD);
4121 }
4122
4123
4124 status_t
4125-BTree::FindPrevious(btrfs_key& key, void** _value, size_t* _size)
4126+BTree::FindPrevious(btrfs_key& key, void** _value, size_t* _size, bool read)
4127 {
4128- return _Find(key, _value, _size, BTREE_BACKWARD);
4129+ return _Find(key, _value, _size, read, BTREE_BACKWARD);
4130 }
4131
4132
4133 status_t
4134-BTree::FindExact(btrfs_key& key, void** _value, size_t* _size)
4135+BTree::FindExact(btrfs_key& key, void** _value, size_t* _size, bool read)
4136 {
4137- return _Find(key, _value, _size, BTREE_EXACT);
4138+ return _Find(key, _value, _size, read, BTREE_EXACT);
4139 }
4140
4141
4142@@ -340,7 +344,7 @@ TreeIterator::Traverse(btree_traversing direction, btrfs_key& key,
4143
4144 fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
4145 status_t status = fTree->_Find(fCurrentKey, value, size,
4146- direction);
4147+ true, direction);
4148 if (status != B_OK) {
4149 TRACE("TreeIterator::Traverse() Find failed\n");
4150 return B_ENTRY_NOT_FOUND;
4151diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4152index 3dcbe82..d82d671 100644
4153--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
4154+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4155@@ -80,8 +80,8 @@ public:
4156 off_t BlockNum() const { return fBlockNumber;}
4157 bool IsWritable() const { return fWritable; }
4158
4159- int32 SearchSlot(const btrfs_key& key, int* slot,
4160- btree_traversing type) const;
4161+ int32 SearchSlot(const btrfs_key& key, int* slot,
4162+ btree_traversing type) const;
4163 private:
4164 BTreeNode(const BTreeNode&);
4165 BTreeNode& operator=(const BTreeNode&);
4166@@ -114,11 +114,11 @@ public:
4167 fsblock_t rootBlock);
4168 ~BTree();
4169 status_t FindExact(btrfs_key& key, void** value,
4170- size_t* size = NULL);
4171+ size_t* size = NULL, bool read = true);
4172 status_t FindNext(btrfs_key& key, void** value,
4173- size_t* size = NULL);
4174+ size_t* size = NULL, bool read = true);
4175 status_t FindPrevious(btrfs_key& key, void** value,
4176- size_t* size = NULL);
4177+ size_t* size = NULL, bool read = true);
4178
4179 Volume* SystemVolume() const { return fVolume; }
4180
4181@@ -131,8 +131,8 @@ private:
4182 BTree& operator=(const BTree& other);
4183 // no implementation
4184
4185- status_t _Find(btrfs_key& key, void** value,
4186- size_t* size, btree_traversing type);
4187+ status_t _Find(btrfs_key& key, void** value, size_t* size,
4188+ bool read, btree_traversing type);
4189 void _AddIterator(TreeIterator* iterator);
4190 void _RemoveIterator(TreeIterator* iterator);
4191 private:
4192--
41932.7.0
4194
4195
4196From 8e72d23cf0a020b1753b1b6a99ec497f7a6e065c Mon Sep 17 00:00:00 2001
4197From: hyche <cvghy116@gmail.com>
4198Date: Wed, 5 Jul 2017 00:18:23 +0700
4199Subject: [PATCH 27/36] btrfs_shell: remove BEOS_COMPATIBLE as Haiku doesn't
4200 support anymore
4201
4202---
4203 src/tools/btrfs_shell/Jamfile | 7 ++-----
4204 1 file changed, 2 insertions(+), 5 deletions(-)
4205
4206diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
4207index 5502c7e..5029613 100644
4208--- a/src/tools/btrfs_shell/Jamfile
4209+++ b/src/tools/btrfs_shell/Jamfile
4210@@ -27,11 +27,8 @@ if ! $(HOST_PLATFORM_BEOS_COMPATIBLE) {
4211 }
4212
4213 UseHeaders [ FDirName $(HAIKU_TOP) headers build ] : true ;
4214-
4215-if ! $(HOST_PLATFORM_BEOS_COMPATIBLE) {
4216- UseHeaders [ FDirName $(HAIKU_TOP) headers build os ] : true ;
4217- UseHeaders [ FDirName $(HAIKU_TOP) headers build os support ] : true ;
4218-}
4219+UseHeaders [ FDirName $(HAIKU_TOP) headers build os ] : true ;
4220+UseHeaders [ FDirName $(HAIKU_TOP) headers build os support ] : true ;
4221
4222 UsePrivateKernelHeaders ;
4223 UsePrivateHeaders shared storage fs_shell ;
4224--
42252.7.0
4226
4227
4228From 1656daf120c6f10ca0559604c19e43c3b8599f23 Mon Sep 17 00:00:00 2001
4229From: hyche <cvghy116@gmail.com>
4230Date: Wed, 5 Jul 2017 00:23:38 +0700
4231Subject: [PATCH 28/36] Btrfs: Added new file ExtentAllocator * New class
4232 BlockGroup: This holds block_group item, it handles free extents and extents,
4233 now its only dump it out. * New class ExtentAllocator: This will know how to
4234 allocate blocks or extents, currently no ideas how to implement it. * New
4235 class FreeExtentTree: An AVLTree that tracks free extents. * Jamfile: Added
4236 more fields.
4237
4238---
4239 .../kernel/file_systems/btrfs/ExtentAllocator.cpp | 246 +++++++++++++++++++++
4240 .../kernel/file_systems/btrfs/ExtentAllocator.h | 62 ++++++
4241 src/add-ons/kernel/file_systems/btrfs/Jamfile | 1 +
4242 src/tools/btrfs_shell/Jamfile | 1 +
4243 4 files changed, 310 insertions(+)
4244 create mode 100644 src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
4245 create mode 100644 src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
4246
4247diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
4248new file mode 100644
4249index 0000000..363acec
4250--- /dev/null
4251+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
4252@@ -0,0 +1,246 @@
4253+#include "ExtentAllocator.h"
4254+#include "Chunk.h"
4255+
4256+
4257+struct FreeExtent : AVLTreeNode {
4258+ uint64 offset;
4259+ uint64 length;
4260+ uint64 flags;
4261+
4262+ FreeExtent(uint64 offset, uint64 length, uint64 flags)
4263+ {
4264+ this->offset = offset;
4265+ this->length = length;
4266+ this->flags = flags;
4267+ }
4268+
4269+ uint64 End() const
4270+ {
4271+ return offset + length;
4272+ }
4273+
4274+ bool Intersect(const FreeExtent* other)
4275+ {
4276+ if (offset >= other->End() || End() <= other->offset) {
4277+ return false;
4278+ }
4279+ if (offset >= other->offset) {
4280+ length = std::min(length, other->End() - offset);
4281+ } else {
4282+ offset = other->offset;
4283+ length = std::min(other->length, End() - other->offset);
4284+ }
4285+ return true;
4286+ }
4287+
4288+ void info() const
4289+ {
4290+ TRACE("free extent at %" B_PRIu64 "( %" B_PRIu64 " ) length %" B_PRIu64
4291+ " flags %" B_PRIu64 "\n", offset, offset/16384, length/16384, flags);
4292+ }
4293+};
4294+
4295+
4296+struct TreeDefinition {
4297+ typedef uint64 Key;
4298+ typedef FreeExtent Value;
4299+
4300+ AVLTreeNode* GetAVLTreeNode(Value* value) const
4301+ {
4302+ return value;
4303+ }
4304+
4305+ Value* GetValue(AVLTreeNode* node) const
4306+ {
4307+ return static_cast<Value*>(node);
4308+ }
4309+
4310+ int Compare(const Key& a, const Value* b) const
4311+ {
4312+ if (a < b->offset)
4313+ return -1;
4314+ if (a >= b->End())
4315+ return 1;
4316+ return 0;
4317+ }
4318+
4319+ int Compare(const Value* a, const Value* b) const
4320+ {
4321+ int comp = Compare(a->offset, b);
4322+ //TODO: check more conditions here for inserting
4323+ return comp;
4324+ }
4325+};
4326+
4327+
4328+struct FreeExtentTree : public AVLTree<TreeDefinition> {
4329+ FreeExtentTree(const TreeDefinition& definition)
4330+ :
4331+ AVLTree<TreeDefinition>(definition)
4332+ {
4333+ }
4334+
4335+ void DumpInOrder() const
4336+ {
4337+ _DumpInOrder(RootNode());
4338+ }
4339+
4340+private:
4341+ void _DumpInOrder(FreeExtent* node) const
4342+ {
4343+ if (node == NULL)
4344+ return;
4345+ _DumpInOrder(fDefinition.GetValue(node->left));
4346+ node->info();
4347+ _DumpInOrder(fDefinition.GetValue(node->right));
4348+ }
4349+};
4350+
4351+
4352+//BlockGroup
4353+
4354+
4355+BlockGroup::BlockGroup(BTree* extentTree)
4356+ :
4357+ fBlockGroup(NULL),
4358+ fExtentTree(extentTree)
4359+{
4360+ if (Allocate(BTRFS_BLOCKGROUP_FLAG_METADA) != B_OK) {
4361+ panic("Fail to initliaze BlockGroup\n");
4362+ }
4363+}
4364+
4365+
4366+BlockGroup::BlockGroup(BTree* extentTree, uint64 flag)
4367+ :
4368+ fBlockGroup(NULL),
4369+ fExtentTree(extentTree)
4370+{
4371+ if (Allocate(flag) != B_OK) {
4372+ panic("Fail to initliaze BlockGroup\n");
4373+ }
4374+}
4375+
4376+
4377+BlockGroup::~BlockGroup()
4378+{
4379+ if (fBlockGroup != NULL)
4380+ free(fBlockGroup);
4381+}
4382+
4383+
4384+// Allocate BlockGroup that has flag
4385+status_t
4386+BlockGroup::Allocate(uint64 flag)
4387+{
4388+ Chunk* chunk = fExtentTree->SystemVolume()->SystemChunk();
4389+ fKey.SetObjectID(chunk->Offset());
4390+ fKey.SetType(BTRFS_KEY_TYPE_BLOCKGROUP_ITEM);
4391+ fKey.SetOffset(0);
4392+ status_t status;
4393+
4394+ while(true) {
4395+ status = fExtentTree->FindNext(fKey, (void**)&fBlockGroup);
4396+ if ((fBlockGroup->Flags() & flag) == flag || status != B_OK)
4397+ break;
4398+ fKey.SetObjectID(End());
4399+ fKey.SetOffset(0);
4400+ }
4401+
4402+ if (status != B_OK) {
4403+ TRACE("BlockGroup::Allocate() cannot find block group has flag: %"
4404+ B_PRIu64 "\n", flag);
4405+ }
4406+
4407+ return status;
4408+}
4409+
4410+
4411+status_t
4412+BlockGroup::LoadExtent(FreeExtentTree* tree, bool inverse)
4413+{
4414+ btrfs_key searchKey;
4415+ void* data;
4416+ status_t status;
4417+ uint64 flags = fBlockGroup->flags;
4418+ uint64 start = Start();
4419+
4420+ searchKey.SetType(BTRFS_KEY_TYPE_METADATA_ITEM);
4421+ uint64 extentSize = fExtentTree->SystemVolume()->BlockSize();
4422+ if ((flags & BTRFS_BLOCKGROUP_FLAG_MASK) == BTRFS_BLOCKGROUP_FLAG_DATA)
4423+ searchKey.SetType(BTRFS_KEY_TYPE_EXTENT_ITEM);
4424+ searchKey.SetObjectID(start);
4425+ searchKey.SetOffset(0);
4426+
4427+ while(true) {
4428+ status = fExtentTree->FindNext(searchKey, &data);
4429+ if (status != B_OK) {
4430+ if (searchKey.ObjectID() == Start()) {
4431+ //handle special case when key has objectid == BlockGroup's objectid
4432+ searchKey.SetObjectID(Start() + 1);
4433+ searchKey.SetOffset(0);
4434+ continue;
4435+ }
4436+ break;
4437+ }
4438+ if ((flags & BTRFS_BLOCKGROUP_FLAG_MASK) == BTRFS_BLOCKGROUP_FLAG_DATA) {
4439+ extentSize = searchKey.Offset();
4440+ }
4441+
4442+ if (inverse == false) {
4443+ } else {
4444+ _InsertFreeExtent(tree, start, searchKey.ObjectID() - start, flags);
4445+ }
4446+ start = searchKey.ObjectID() + extentSize;
4447+ searchKey.SetObjectID(start);
4448+ searchKey.SetOffset(0);
4449+ }
4450+ if (inverse == true) {
4451+ _InsertFreeExtent(tree, start, End() - start, flags);
4452+ }
4453+
4454+ return B_OK;
4455+}
4456+
4457+
4458+status_t
4459+BlockGroup::_InsertFreeExtent(FreeExtentTree* tree, uint64 start, uint64 length,
4460+ uint64 flags)
4461+{
4462+ if (length <= 0)
4463+ return B_BAD_DATA;
4464+ FreeExtent* freeExtent = new FreeExtent(start, length, flags);
4465+ tree->Insert(freeExtent);
4466+ return B_OK;
4467+}
4468+
4469+
4470+// ExtentAllocator
4471+
4472+
4473+ExtentAllocator::ExtentAllocator(Volume* volume)
4474+ :
4475+ fTree(NULL),
4476+ fBlockGroup(NULL),
4477+ fVolume(volume)
4478+{
4479+ fTree = new FreeExtentTree(TreeDefinition());
4480+ fBlockGroup = new BlockGroup(volume->ExtentTree());
4481+}
4482+
4483+
4484+ExtentAllocator::~ExtentAllocator()
4485+{
4486+ delete fTree;
4487+ delete fBlockGroup;
4488+}
4489+
4490+
4491+void
4492+ExtentAllocator::AllocateFreeExtent()
4493+{
4494+ BTree* extentTree = new BTree(fVolume);
4495+ fBlockGroup->LoadExtent(fTree, true);
4496+ fTree->DumpInOrder();
4497+ delete extentTree;
4498+}
4499diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
4500new file mode 100644
4501index 0000000..a11306e
4502--- /dev/null
4503+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
4504@@ -0,0 +1,62 @@
4505+#ifndef EXTENT_ALLOCATOR_H
4506+#define EXTENT_ALLOCATOR_H
4507+
4508+
4509+#include "Volume.h"
4510+#include "BTree.h"
4511+
4512+
4513+//#define TRACE_BTRFS
4514+#ifdef TRACE_BTRFS
4515+# define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
4516+#else
4517+# define TRACE(x...) ;
4518+#endif
4519+
4520+
4521+struct FreeExtent;
4522+struct FreeExtentTree;
4523+
4524+
4525+class BlockGroup {
4526+public:
4527+ BlockGroup(BTree* extentTree);
4528+ BlockGroup(BTree* extentTree, uint64 flag);
4529+ ~BlockGroup();
4530+
4531+ status_t Allocate(uint64 flag);
4532+ status_t LoadExtent(FreeExtentTree* tree,
4533+ bool inverse=false);
4534+ uint64 Start() const { return fKey.ObjectID(); }
4535+ uint64 End() const
4536+ { return fKey.ObjectID() + fKey.Offset(); }
4537+
4538+private:
4539+ BlockGroup(const BlockGroup&);
4540+ BlockGroup& operator=(const BlockGroup&);
4541+ status_t _InsertFreeExtent(FreeExtentTree* tree,
4542+ uint64 size, uint64 length, uint64 flags);
4543+
4544+ btrfs_key fKey;
4545+ btrfs_block_group* fBlockGroup;
4546+ BTree* fExtentTree;
4547+};
4548+
4549+
4550+class ExtentAllocator {
4551+public:
4552+ ExtentAllocator(Volume* volume);
4553+ ~ExtentAllocator();
4554+
4555+ void AllocateFreeExtent();
4556+private:
4557+ ExtentAllocator(const ExtentAllocator&);
4558+ ExtentAllocator& operator=(const ExtentAllocator&);
4559+private:
4560+ Volume* fVolume;
4561+ BlockGroup* fBlockGroup;
4562+ FreeExtentTree* fTree;
4563+};
4564+
4565+
4566+#endif // EXTENT_ALLOCATOR_H
4567diff --git a/src/add-ons/kernel/file_systems/btrfs/Jamfile b/src/add-ons/kernel/file_systems/btrfs/Jamfile
4568index d408e55..78ba20c 100644
4569--- a/src/add-ons/kernel/file_systems/btrfs/Jamfile
4570+++ b/src/add-ons/kernel/file_systems/btrfs/Jamfile
4571@@ -16,6 +16,7 @@ KernelAddon btrfs :
4572 Chunk.cpp
4573 CRCTable.cpp
4574 DirectoryIterator.cpp
4575+ ExtentAllocator.cpp
4576 Inode.cpp
4577 Volume.cpp
4578 : kernel_libz.a
4579diff --git a/src/tools/btrfs_shell/Jamfile b/src/tools/btrfs_shell/Jamfile
4580index 5029613..99231c8 100644
4581--- a/src/tools/btrfs_shell/Jamfile
4582+++ b/src/tools/btrfs_shell/Jamfile
4583@@ -42,6 +42,7 @@ local btrfsSources =
4584 Chunk.cpp
4585 CRCTable.cpp
4586 DirectoryIterator.cpp
4587+ ExtentAllocator.cpp
4588 Inode.cpp
4589 Volume.cpp
4590 kernel_interface.cpp
4591--
45922.7.0
4593
4594
4595From 78c1f35ed8fb8caa3701c6a058edd1c178a971da Mon Sep 17 00:00:00 2001
4596From: hyche <cvghy116@gmail.com>
4597Date: Thu, 6 Jul 2017 17:34:49 +0700
4598Subject: [PATCH 29/36] Btrfs: BTreeNode now holding Volume instead of cache in
4599 order to retrieve more values.
4600
4601---
4602 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 18 +++++++++---------
4603 src/add-ons/kernel/file_systems/btrfs/BTree.h | 6 +++---
4604 .../kernel/file_systems/btrfs/ExtentAllocator.cpp | 4 ++--
4605 3 files changed, 14 insertions(+), 14 deletions(-)
4606
4607diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4608index f661aec..14c693b 100644
4609--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4610+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4611@@ -21,10 +21,10 @@
4612 # define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
4613
4614
4615-BTreeNode::BTreeNode(void* cache)
4616+BTreeNode::BTreeNode(Volume* volume)
4617 :
4618 fNode(NULL),
4619- fCache(cache),
4620+ fVolume(volume),
4621 fBlockNumber(0),
4622 fCurrentSlot(0),
4623 fWritable(false)
4624@@ -32,10 +32,10 @@ BTreeNode::BTreeNode(void* cache)
4625 }
4626
4627
4628-BTreeNode::BTreeNode(void* cache, off_t block)
4629+BTreeNode::BTreeNode(Volume* volume, off_t block)
4630 :
4631 fNode(NULL),
4632- fCache(cache),
4633+ fVolume(volume),
4634 fBlockNumber(0),
4635 fCurrentSlot(0),
4636 fWritable(false)
4637@@ -60,7 +60,7 @@ void
4638 BTreeNode::Unset()
4639 {
4640 if (fNode != NULL) {
4641- block_cache_put(fCache, fBlockNumber);
4642+ block_cache_put(fVolume->BlockCache(), fBlockNumber);
4643 fNode = NULL;
4644 }
4645 }
4646@@ -71,7 +71,7 @@ BTreeNode::SetTo(off_t block)
4647 {
4648 Unset();
4649 fBlockNumber = block;
4650- fNode = (btrfs_stream*)block_cache_get(fCache, block);
4651+ fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
4652 }
4653
4654
4655@@ -82,10 +82,10 @@ BTreeNode::SetToWritable(off_t block, int32 transactionId, bool empty)
4656 fBlockNumber = block;
4657 fWritable = true;
4658 if (empty) {
4659- fNode = (btrfs_stream*)block_cache_get_empty(fCache, block,
4660+ fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(), block,
4661 transactionId);
4662 } else {
4663- fNode = (btrfs_stream*)block_cache_get_writable(fCache, block,
4664+ fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(), block,
4665 transactionId);
4666 }
4667 }
4668@@ -209,7 +209,7 @@ BTree::_Find(btrfs_key& key, void** _value, size_t* _size,
4669 TRACE("Find() objectid %" B_PRId64 " type %d offset %" B_PRId64 " \n",
4670 key.ObjectID(), key.Type(), key.Offset());
4671 CachedBlock cached(fVolume);
4672- BTreeNode node(fVolume->BlockCache(), fRootBlock);
4673+ BTreeNode node(fVolume, fRootBlock);
4674 int slot, ret;
4675 fsblock_t physicalBlock;
4676
4677diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4678index d82d671..c092973 100644
4679--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
4680+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4681@@ -43,8 +43,8 @@ struct node_and_key {
4682
4683 class BTreeNode {
4684 public:
4685- BTreeNode(void* cache);
4686- BTreeNode(void* cache, off_t block);
4687+ BTreeNode(Volume* volume);
4688+ BTreeNode(Volume* volume, off_t block);
4689 ~BTreeNode();
4690
4691 // just return from Header
4692@@ -88,7 +88,7 @@ private:
4693 //no implementation
4694
4695 btrfs_stream* fNode;
4696- void* fCache;
4697+ Volume* fVolume;
4698 off_t fBlockNumber;
4699 uint32 fCurrentSlot;
4700 bool fWritable;
4701diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
4702index 363acec..d8b2d5b 100644
4703--- a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
4704+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
4705@@ -220,9 +220,9 @@ BlockGroup::_InsertFreeExtent(FreeExtentTree* tree, uint64 start, uint64 length,
4706
4707 ExtentAllocator::ExtentAllocator(Volume* volume)
4708 :
4709- fTree(NULL),
4710+ fVolume(volume),
4711 fBlockGroup(NULL),
4712- fVolume(volume)
4713+ fTree(NULL)
4714 {
4715 fTree = new FreeExtentTree(TreeDefinition());
4716 fBlockGroup = new BlockGroup(volume->ExtentTree());
4717--
47182.7.0
4719
4720
4721From 3747ac863541cf82033ba562dfae2b5fc03ee3b1 Mon Sep 17 00:00:00 2001
4722From: hyche <cvghy116@gmail.com>
4723Date: Thu, 6 Jul 2017 23:33:06 +0700
4724Subject: [PATCH 30/36] Btrfs: Fixed mask value of block_group flag
4725
4726---
4727 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 2 +-
4728 1 file changed, 1 insertion(+), 1 deletion(-)
4729
4730diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
4731index 5549258..993ac88 100644
4732--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
4733+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
4734@@ -454,7 +454,7 @@ struct btrfs_extent_data_ref {
4735 #define BTRFS_BLOCKGROUP_FLAG_RAID10 64
4736 #define BTRFS_BLOCKGROUP_FLAG_RAID5 128
4737 #define BTRFS_BLOCKGROUP_FLAG_RAID6 256
4738-#define BTRFS_BLOCKGROUP_FLAG_MASK 512
4739+#define BTRFS_BLOCKGROUP_FLAG_MASK 511
4740
4741
4742 struct file_cookie {
4743--
47442.7.0
4745
4746
4747From 88dff02cf80e1a0e60d7dc68a8f1aee9893c717d Mon Sep 17 00:00:00 2001
4748From: hyche <cvghy116@gmail.com>
4749Date: Fri, 7 Jul 2017 23:01:16 +0700
4750Subject: [PATCH 31/36] Btrfs: Initialized space calculating helpers
4751
4752---
4753 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 42 +++++++++++++++++++++++++
4754 src/add-ons/kernel/file_systems/btrfs/BTree.h | 6 ++++
4755 2 files changed, 48 insertions(+)
4756
4757diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4758index 14c693b..d4206b7 100644
4759--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4760+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4761@@ -91,6 +91,48 @@ BTreeNode::SetToWritable(off_t block, int32 transactionId, bool empty)
4762 }
4763
4764
4765+//calculate used space, 0 is for internal node, from 1 -> 3 is for leaf
4766+//type 0: calculate for internal nodes
4767+//type 1: only item space
4768+//type 2: only item data space
4769+//type 3: both type 1 and 2
4770+uint32
4771+BTreeNode::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
4772+{
4773+ if (to < from || from < 0 || to >= ItemCount() || ItemCount() == 0)
4774+ return 0;
4775+
4776+ uint32 result = 0;
4777+ if (type == 0) {
4778+ result = sizeof(btrfs_index) * (to - from + 1);
4779+ }
4780+ if ((type & 1) == 1) {
4781+ result += sizeof(btrfs_entry) * (to - from + 1);
4782+ }
4783+ if ((type & 2) == 2) {
4784+ result += Item(from)->Offset() + Item(from)->Size()
4785+ - Item(to)->Offset();
4786+ }
4787+ return result + sizeof(btrfs_header);
4788+}
4789+
4790+
4791+uint32
4792+BTreeNode::SpaceUsed() const
4793+{
4794+ if (Level() == 0)
4795+ return _CalculateSpace(0, ItemCount() - 1, 3);
4796+ return _CalculateSpace(0, ItemCount() - 1, 0);
4797+}
4798+
4799+
4800+uint32
4801+BTreeNode::SpaceLeft() const
4802+{
4803+ return fVolume->BlockSize() - SpaceUsed();
4804+}
4805+
4806+
4807 int32
4808 BTreeNode::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
4809 {
4810diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4811index c092973..7b11d94 100644
4812--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
4813+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4814@@ -80,6 +80,9 @@ public:
4815 off_t BlockNum() const { return fBlockNumber;}
4816 bool IsWritable() const { return fWritable; }
4817
4818+ uint32 SpaceUsed() const;
4819+ uint32 SpaceLeft() const;
4820+
4821 int32 SearchSlot(const btrfs_key& key, int* slot,
4822 btree_traversing type) const;
4823 private:
4824@@ -87,6 +90,9 @@ private:
4825 BTreeNode& operator=(const BTreeNode&);
4826 //no implementation
4827
4828+ uint32 _CalculateSpace(uint32 from, uint32 to,
4829+ uint8 type) const;
4830+
4831 btrfs_stream* fNode;
4832 Volume* fVolume;
4833 off_t fBlockNumber;
4834--
48352.7.0
4836
4837
4838From 5ff5bee54ae635cc87090f795138a740bd9e809b Mon Sep 17 00:00:00 2001
4839From: hyche <cvghy116@gmail.com>
4840Date: Fri, 7 Jul 2017 23:02:26 +0700
4841Subject: [PATCH 32/36] Btrfs: Initialized node copy helpers
4842
4843---
4844 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 58 ++++++++++++++++++++++---
4845 src/add-ons/kernel/file_systems/btrfs/BTree.h | 4 ++
4846 2 files changed, 57 insertions(+), 5 deletions(-)
4847
4848diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4849index d4206b7..e8980fb 100644
4850--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4851+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4852@@ -91,11 +91,13 @@ BTreeNode::SetToWritable(off_t block, int32 transactionId, bool empty)
4853 }
4854
4855
4856-//calculate used space, 0 is for internal node, from 1 -> 3 is for leaf
4857-//type 0: calculate for internal nodes
4858-//type 1: only item space
4859-//type 2: only item data space
4860-//type 3: both type 1 and 2
4861+/*
4862+ * calculate used space, 0 is for internal node, from 1 -> 3 is for leaf
4863+ * type 0: calculate for internal nodes
4864+ * type 1: only item space
4865+ * type 2: only item data space
4866+ * type 3: both type 1 and 2
4867+ */
4868 uint32
4869 BTreeNode::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
4870 {
4871@@ -133,6 +135,52 @@ BTreeNode::SpaceLeft() const
4872 }
4873
4874
4875+void
4876+BTreeNode::_Copy(const BTreeNode* origin, uint32 at, uint32 from,
4877+ uint32 to) const
4878+{
4879+ if (Level() == 0) {
4880+ memcpy(Item(at), origin->Item(from),
4881+ origin->_CalculateSpace(from, to, 1));
4882+ memcpy(ItemData(at), origin->ItemData(from),
4883+ origin->_CalculateSpace(from, to, 2));
4884+ } else {
4885+ memcpy(Index(at), origin->Index(from),
4886+ origin->_CalculateSpace(from, to, 0));
4887+ }
4888+}
4889+
4890+
4891+/*
4892+ * copy item and item data except its header
4893+ * length < 0: removing
4894+ * length > 0: inserting
4895+ */
4896+status_t
4897+BTreeNode::Copy(const BTreeNode* origin, uint32 start, uint32 end,
4898+ int length) const
4899+{
4900+ if (length < 0 && std::abs(length) >= SpaceUsed() - sizeof(btrfs_header)
4901+ || (length > 0 && length >= SpaceLeft()))
4902+ return B_BAD_VALUE;
4903+
4904+ if (length == 0) {
4905+ //copy all
4906+ _Copy(origin, 0, 0, ItemCount() - 1);
4907+ } else if (length < 0) {
4908+ //removing all items in [start, end]
4909+ _Copy(origin, 0, 0, start - 1); // <-- [start,...
4910+ _Copy(origin, start, end + 1, ItemCount() - 1); // ..., end] -->
4911+ } else {
4912+ //inserting in [start, end] - make a hole for later
4913+ _Copy(origin, 0, 0, start - 1);
4914+ _Copy(origin, end + 1, start, ItemCount() - 1);
4915+ }
4916+
4917+ return B_OK;
4918+}
4919+
4920+
4921 int32
4922 BTreeNode::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type) const
4923 {
4924diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4925index 7b11d94..7416f05 100644
4926--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
4927+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
4928@@ -83,6 +83,8 @@ public:
4929 uint32 SpaceUsed() const;
4930 uint32 SpaceLeft() const;
4931
4932+ status_t Copy(const BTreeNode* origin, uint32 start,
4933+ uint32 end, int length) const;
4934 int32 SearchSlot(const btrfs_key& key, int* slot,
4935 btree_traversing type) const;
4936 private:
4937@@ -90,6 +92,8 @@ private:
4938 BTreeNode& operator=(const BTreeNode&);
4939 //no implementation
4940
4941+ void _Copy(const BTreeNode* origin, uint32 at, uint32 from,
4942+ uint32 to) const;
4943 uint32 _CalculateSpace(uint32 from, uint32 to,
4944 uint8 type) const;
4945
4946--
49472.7.0
4948
4949
4950From 09fb2627b6c97988d6122903478beab0e3ed34a2 Mon Sep 17 00:00:00 2001
4951From: hyche <cvghy116@gmail.com>
4952Date: Fri, 7 Jul 2017 23:04:23 +0700
4953Subject: [PATCH 33/36] Btrfs: Added setters for btrfs_header
4954
4955---
4956 src/add-ons/kernel/file_systems/btrfs/btrfs.h | 7 +++++++
4957 1 file changed, 7 insertions(+)
4958
4959diff --git a/src/add-ons/kernel/file_systems/btrfs/btrfs.h b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
4960index 993ac88..3afad57 100644
4961--- a/src/add-ons/kernel/file_systems/btrfs/btrfs.h
4962+++ b/src/add-ons/kernel/file_systems/btrfs/btrfs.h
4963@@ -109,6 +109,13 @@ struct btrfs_header {
4964 uint32 ItemCount() const
4965 { return B_LENDIAN_TO_HOST_INT32(item_count); }
4966 uint8 Level() const { return level; }
4967+ void SetLogical(uint64 logical)
4968+ { logical_address = B_HOST_TO_LENDIAN_INT64(logical); }
4969+ void SetFlags(uint64 flags) { flags = B_HOST_TO_LENDIAN_INT64(flags); }
4970+ void SetGeneration(uint64 gen) { generation = B_HOST_TO_LENDIAN_INT64(gen);}
4971+ void SetOwner(uint64) { owner = B_HOST_TO_LENDIAN_INT64(owner); }
4972+ void SetItemCount(uint32 itemCount)
4973+ { item_count = B_HOST_TO_LENDIAN_INT32(itemCount); }
4974 } _PACKED;
4975
4976
4977--
49782.7.0
4979
4980
4981From 0f7464782c9e5d8efc8381d2b207baed2893a440 Mon Sep 17 00:00:00 2001
4982From: hyche <cvghy116@gmail.com>
4983Date: Sat, 15 Jul 2017 20:05:36 +0700
4984Subject: [PATCH 34/36] Btrfs: * Fix code style (again) * Rename method:
4985 AllocateFreeExtent -> _LoadFreeExtent * etc
4986
4987---
4988 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 1 +
4989 src/add-ons/kernel/file_systems/btrfs/BTree.h | 30 +++++++++++-----------
4990 src/add-ons/kernel/file_systems/btrfs/Chunk.h | 1 +
4991 .../kernel/file_systems/btrfs/ExtentAllocator.cpp | 2 +-
4992 .../kernel/file_systems/btrfs/ExtentAllocator.h | 7 ++---
4993 src/add-ons/kernel/file_systems/btrfs/Volume.cpp | 1 -
4994 src/add-ons/kernel/file_systems/btrfs/Volume.h | 6 ++---
4995 7 files changed, 25 insertions(+), 23 deletions(-)
4996
4997diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
4998index e8980fb..cc8ab3e 100644
4999--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5000+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5001@@ -56,6 +56,7 @@ BTreeNode::Keep()
5002 fNode = NULL;
5003 }
5004
5005+
5006 void
5007 BTreeNode::Unset()
5008 {
5009diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
5010index 7416f05..23aaf08 100644
5011--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
5012+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
5013@@ -3,8 +3,8 @@
5014 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
5015 * This file may be used under the terms of the MIT License.
5016 */
5017-#ifndef B_PLUS_TREE_H
5018-#define B_PLUS_TREE_H
5019+#ifndef B_TREE_H
5020+#define B_TREE_H
5021
5022
5023 #include "btrfs.h"
5024@@ -49,30 +49,29 @@ public:
5025
5026 // just return from Header
5027 uint64 Logical() const
5028- { return fNode->header.Logical(); }
5029+ { return fNode->header.Logical(); }
5030 uint64 Flags() const
5031- { return fNode->header.Flags(); }
5032+ { return fNode->header.Flags(); }
5033 uint64 Generation() const
5034- { return fNode->header.Generation(); }
5035+ { return fNode->header.Generation(); }
5036 uint64 Owner() const
5037- { return fNode->header.Owner(); }
5038+ { return fNode->header.Owner(); }
5039 uint32 ItemCount() const
5040- { return fNode->header.ItemCount(); }
5041+ { return fNode->header.ItemCount(); }
5042 uint8 Level() const
5043- { return fNode->header.Level(); }
5044+ { return fNode->header.Level(); }
5045
5046 btrfs_index* Index(uint32 i) const
5047- { return &fNode->index[i]; }
5048+ { return &fNode->index[i]; }
5049
5050 btrfs_entry* Item(uint32 i) const
5051- { return &fNode->entries[i]; }
5052+ { return &fNode->entries[i]; }
5053 uint8* ItemData(uint32 i) const
5054- { return (uint8*)Item(0) + Item(i)->Offset(); }
5055+ { return (uint8*)Item(0) + Item(i)->Offset(); }
5056
5057 void Keep();
5058 void Unset();
5059
5060-
5061 void SetTo(off_t block);
5062 void SetToWritable(off_t block,
5063 int32 transactionId, bool empty);
5064@@ -86,7 +85,7 @@ public:
5065 status_t Copy(const BTreeNode* origin, uint32 start,
5066 uint32 end, int length) const;
5067 int32 SearchSlot(const btrfs_key& key, int* slot,
5068- btree_traversing type) const;
5069+ btree_traversing type) const;
5070 private:
5071 BTreeNode(const BTreeNode&);
5072 BTreeNode& operator=(const BTreeNode&);
5073@@ -97,7 +96,8 @@ private:
5074 uint32 _CalculateSpace(uint32 from, uint32 to,
5075 uint8 type) const;
5076
5077- btrfs_stream* fNode;
5078+private:
5079+ btrfs_stream* fNode;
5080 Volume* fVolume;
5081 off_t fBlockNumber;
5082 uint32 fCurrentSlot;
5083@@ -212,4 +212,4 @@ TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
5084 }
5085
5086
5087-#endif // B_PLUS_TREE_H
5088+#endif // B_TREE_H
5089diff --git a/src/add-ons/kernel/file_systems/btrfs/Chunk.h b/src/add-ons/kernel/file_systems/btrfs/Chunk.h
5090index c1fbe49..9766c37 100644
5091--- a/src/add-ons/kernel/file_systems/btrfs/Chunk.h
5092+++ b/src/add-ons/kernel/file_systems/btrfs/Chunk.h
5093@@ -28,4 +28,5 @@ private:
5094 status_t fInitStatus;
5095 };
5096
5097+
5098 #endif // CHUNK_H
5099diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
5100index d8b2d5b..e033a95 100644
5101--- a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
5102+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.cpp
5103@@ -237,7 +237,7 @@ ExtentAllocator::~ExtentAllocator()
5104
5105
5106 void
5107-ExtentAllocator::AllocateFreeExtent()
5108+ExtentAllocator::_LoadFreeExtent()
5109 {
5110 BTree* extentTree = new BTree(fVolume);
5111 fBlockGroup->LoadExtent(fTree, true);
5112diff --git a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
5113index a11306e..3c8763d 100644
5114--- a/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
5115+++ b/src/add-ons/kernel/file_systems/btrfs/ExtentAllocator.h
5116@@ -29,7 +29,7 @@ public:
5117 bool inverse=false);
5118 uint64 Start() const { return fKey.ObjectID(); }
5119 uint64 End() const
5120- { return fKey.ObjectID() + fKey.Offset(); }
5121+ { return fKey.ObjectID() + fKey.Offset(); }
5122
5123 private:
5124 BlockGroup(const BlockGroup&);
5125@@ -37,8 +37,9 @@ private:
5126 status_t _InsertFreeExtent(FreeExtentTree* tree,
5127 uint64 size, uint64 length, uint64 flags);
5128
5129+private:
5130 btrfs_key fKey;
5131- btrfs_block_group* fBlockGroup;
5132+ btrfs_block_group* fBlockGroup;
5133 BTree* fExtentTree;
5134 };
5135
5136@@ -48,10 +49,10 @@ public:
5137 ExtentAllocator(Volume* volume);
5138 ~ExtentAllocator();
5139
5140- void AllocateFreeExtent();
5141 private:
5142 ExtentAllocator(const ExtentAllocator&);
5143 ExtentAllocator& operator=(const ExtentAllocator&);
5144+ void _LoadFreeExtent();
5145 private:
5146 Volume* fVolume;
5147 BlockGroup* fBlockGroup;
5148diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
5149index 6c923ee..3ceb713 100644
5150--- a/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
5151+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.cpp
5152@@ -519,4 +519,3 @@ Volume::Identify(int fd, btrfs_super_block* superBlock)
5153
5154 return B_OK;
5155 }
5156-
5157diff --git a/src/add-ons/kernel/file_systems/btrfs/Volume.h b/src/add-ons/kernel/file_systems/btrfs/Volume.h
5158index 7889336..d839dc0 100644
5159--- a/src/add-ons/kernel/file_systems/btrfs/Volume.h
5160+++ b/src/add-ons/kernel/file_systems/btrfs/Volume.h
5161@@ -38,9 +38,9 @@ public:
5162 { return fFSVolume ? fFSVolume->id : -1; }
5163 fs_volume* FSVolume() const { return fFSVolume; }
5164 const char* Name() const;
5165- BTree* FSTree() const { return fFSTree; }
5166- BTree* ExtentTree() const { return fExtentTree; }
5167- BTree* RootTree() const { return fRootTree; }
5168+ BTree* FSTree() const { return fFSTree; }
5169+ BTree* ExtentTree() const { return fExtentTree; }
5170+ BTree* RootTree() const { return fRootTree; }
5171
5172 uint32 SectorSize() const { return fSectorSize; }
5173 uint32 BlockSize() const { return fBlockSize; }
5174--
51752.7.0
5176
5177
5178From 05c45c421da0b51007b37e8450dbd8172f1edc97 Mon Sep 17 00:00:00 2001
5179From: hyche <cvghy116@gmail.com>
5180Date: Sun, 16 Jul 2017 23:16:52 +0700
5181Subject: [PATCH 35/36] Btrfs: Changed _CalculateSpace function, now it doesn't
5182 take btrfs_header into account, also it won't return error for checking
5183 inputs as because 0 is a valid result.
5184
5185---
5186 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 12 +++++-------
5187 1 file changed, 5 insertions(+), 7 deletions(-)
5188
5189diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5190index cc8ab3e..619221f 100644
5191--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5192+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5193@@ -93,7 +93,8 @@ BTreeNode::SetToWritable(off_t block, int32 transactionId, bool empty)
5194
5195
5196 /*
5197- * calculate used space, 0 is for internal node, from 1 -> 3 is for leaf
5198+ * calculate used space except the header,
5199+ * 0 is for internal node, from 1 -> 3 is for leaf
5200 * type 0: calculate for internal nodes
5201 * type 1: only item space
5202 * type 2: only item data space
5203@@ -102,9 +103,6 @@ BTreeNode::SetToWritable(off_t block, int32 transactionId, bool empty)
5204 uint32
5205 BTreeNode::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
5206 {
5207- if (to < from || from < 0 || to >= ItemCount() || ItemCount() == 0)
5208- return 0;
5209-
5210 uint32 result = 0;
5211 if (type == 0) {
5212 result = sizeof(btrfs_index) * (to - from + 1);
5213@@ -116,7 +114,7 @@ BTreeNode::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
5214 result += Item(from)->Offset() + Item(from)->Size()
5215 - Item(to)->Offset();
5216 }
5217- return result + sizeof(btrfs_header);
5218+ return result;
5219 }
5220
5221
5222@@ -124,8 +122,8 @@ uint32
5223 BTreeNode::SpaceUsed() const
5224 {
5225 if (Level() == 0)
5226- return _CalculateSpace(0, ItemCount() - 1, 3);
5227- return _CalculateSpace(0, ItemCount() - 1, 0);
5228+ return _CalculateSpace(0, ItemCount() - 1, 3) + sizeof(btrfs_header);
5229+ return _CalculateSpace(0, ItemCount() - 1, 0) + sizeof(btrfs_header);
5230 }
5231
5232
5233--
52342.7.0
5235
5236
5237From fb1352eb04099ca2e5618af699fb4bc4ab783f3f Mon Sep 17 00:00:00 2001
5238From: hyche <cvghy116@gmail.com>
5239Date: Sun, 16 Jul 2017 23:21:18 +0700
5240Subject: [PATCH 36/36] Btrfs: Fix copy helpers * Fix not handle memory
5241 correctly. * Fix misused methods of copy and original node. * Fix
5242 insert/remove items when in corner cases (e.g removing/inserting items at the
5243 beginning or ending).
5244
5245---
5246 src/add-ons/kernel/file_systems/btrfs/BTree.cpp | 43 +++++++++++++++++++------
5247 src/add-ons/kernel/file_systems/btrfs/BTree.h | 4 +--
5248 2 files changed, 35 insertions(+), 12 deletions(-)
5249
5250diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5251index 619221f..769dd83 100644
5252--- a/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5253+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.cpp
5254@@ -136,12 +136,22 @@ BTreeNode::SpaceLeft() const
5255
5256 void
5257 BTreeNode::_Copy(const BTreeNode* origin, uint32 at, uint32 from,
5258- uint32 to) const
5259+ uint32 to, int length) const
5260 {
5261+ TRACE("BTreeNode::_Copy() at: %d from: %d to: %d length: %d\n",
5262+ at, from, to, length);
5263 if (Level() == 0) {
5264 memcpy(Item(at), origin->Item(from),
5265 origin->_CalculateSpace(from, to, 1));
5266- memcpy(ItemData(at), origin->ItemData(from),
5267+
5268+ // Item offset of copied node must be changed to get the
5269+ // item data offset correctly. length can be zero
5270+ // but let it there doesn't harm anything.
5271+ for (int i = at; i - at <= to - from; ++i) {
5272+ Item(i)->SetOffset(Item(i)->Offset() - length);
5273+ TRACE("BTreeNode::_Copy() i: %d offset %d\n", i, Item(i)->Offset());
5274+ }
5275+ memcpy(ItemData(at + to - from), origin->ItemData(to),
5276 origin->_CalculateSpace(from, to, 2));
5277 } else {
5278 memcpy(Index(at), origin->Index(from),
5279@@ -159,21 +169,34 @@ status_t
5280 BTreeNode::Copy(const BTreeNode* origin, uint32 start, uint32 end,
5281 int length) const
5282 {
5283- if (length < 0 && std::abs(length) >= SpaceUsed() - sizeof(btrfs_header)
5284- || (length > 0 && length >= SpaceLeft()))
5285+ if (length < 0
5286+ && std::abs(length) >= origin->SpaceUsed() - sizeof(btrfs_header)
5287+ || (length > 0 && length >= origin->SpaceLeft()))
5288 return B_BAD_VALUE;
5289
5290+ TRACE("BTreeNode::Copy() start %d end %d length %d\n", start,
5291+ end, length);
5292 if (length == 0) {
5293- //copy all
5294- _Copy(origin, 0, 0, ItemCount() - 1);
5295+ _Copy(origin, 0, 0, origin->ItemCount() - 1, 0);
5296 } else if (length < 0) {
5297 //removing all items in [start, end]
5298- _Copy(origin, 0, 0, start - 1); // <-- [start,...
5299- _Copy(origin, start, end + 1, ItemCount() - 1); // ..., end] -->
5300+ if (start > 0)
5301+ _Copy(origin, 0, 0, start - 1, 0); // <-- [start,...
5302+ if (end + 1 < origin->ItemCount()) {
5303+ // we only care data size
5304+ length += sizeof(btrfs_entry) * (end - start + 1);
5305+ // ..., end] -->
5306+ _Copy(origin, start, end + 1, origin->ItemCount() - 1, length);
5307+ }
5308 } else {
5309 //inserting in [start, end] - make a hole for later
5310- _Copy(origin, 0, 0, start - 1);
5311- _Copy(origin, end + 1, start, ItemCount() - 1);
5312+ if (start > 0)
5313+ _Copy(origin, 0, 0, start - 1, 0);
5314+ if (start < origin->ItemCount()) {
5315+ // again we care data size only
5316+ length -= sizeof(btrfs_entry) * (end - start + 1);
5317+ _Copy(origin, end + 1, start, origin->ItemCount() - 1, length);
5318+ }
5319 }
5320
5321 return B_OK;
5322diff --git a/src/add-ons/kernel/file_systems/btrfs/BTree.h b/src/add-ons/kernel/file_systems/btrfs/BTree.h
5323index 23aaf08..f9804bc 100644
5324--- a/src/add-ons/kernel/file_systems/btrfs/BTree.h
5325+++ b/src/add-ons/kernel/file_systems/btrfs/BTree.h
5326@@ -91,8 +91,8 @@ private:
5327 BTreeNode& operator=(const BTreeNode&);
5328 //no implementation
5329
5330- void _Copy(const BTreeNode* origin, uint32 at, uint32 from,
5331- uint32 to) const;
5332+ void _Copy(const BTreeNode* origin, uint32 at,
5333+ uint32 from, uint32 to, int length) const;
5334 uint32 _CalculateSpace(uint32 from, uint32 to,
5335 uint8 type) const;
5336
5337--
53382.7.0
5339