1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) STRATO AG 2013.  All rights reserved.
4 */
5
6#include <linux/uuid.h>
7#include <asm/unaligned.h>
8#include "messages.h"
9#include "ctree.h"
10#include "transaction.h"
11#include "disk-io.h"
12#include "fs.h"
13#include "accessors.h"
14#include "uuid-tree.h"
15
16static void btrfs_uuid_to_key(u8 *uuid, u8 type, struct btrfs_key *key)
17{
18	key->type = type;
19	key->objectid = get_unaligned_le64(uuid);
20	key->offset = get_unaligned_le64(uuid + sizeof(u64));
21}
22
23/* return -ENOENT for !found, < 0 for errors, or 0 if an item was found */
24static int btrfs_uuid_tree_lookup(struct btrfs_root *uuid_root, u8 *uuid,
25				  u8 type, u64 subid)
26{
27	int ret;
28	struct btrfs_path *path = NULL;
29	struct extent_buffer *eb;
30	int slot;
31	u32 item_size;
32	unsigned long offset;
33	struct btrfs_key key;
34
35	if (WARN_ON_ONCE(!uuid_root)) {
36		ret = -ENOENT;
37		goto out;
38	}
39
40	path = btrfs_alloc_path();
41	if (!path) {
42		ret = -ENOMEM;
43		goto out;
44	}
45
46	btrfs_uuid_to_key(uuid, type, &key);
47	ret = btrfs_search_slot(NULL, uuid_root, &key, path, 0, 0);
48	if (ret < 0) {
49		goto out;
50	} else if (ret > 0) {
51		ret = -ENOENT;
52		goto out;
53	}
54
55	eb = path->nodes[0];
56	slot = path->slots[0];
57	item_size = btrfs_item_size(eb, slot);
58	offset = btrfs_item_ptr_offset(eb, slot);
59	ret = -ENOENT;
60
61	if (!IS_ALIGNED(item_size, sizeof(u64))) {
62		btrfs_warn(uuid_root->fs_info,
63			   "uuid item with illegal size %lu!",
64			   (unsigned long)item_size);
65		goto out;
66	}
67	while (item_size) {
68		__le64 data;
69
70		read_extent_buffer(eb, &data, offset, sizeof(data));
71		if (le64_to_cpu(data) == subid) {
72			ret = 0;
73			break;
74		}
75		offset += sizeof(data);
76		item_size -= sizeof(data);
77	}
78
79out:
80	btrfs_free_path(path);
81	return ret;
82}
83
84int btrfs_uuid_tree_add(struct btrfs_trans_handle *trans, u8 *uuid, u8 type,
85			u64 subid_cpu)
86{
87	struct btrfs_fs_info *fs_info = trans->fs_info;
88	struct btrfs_root *uuid_root = fs_info->uuid_root;
89	int ret;
90	struct btrfs_path *path = NULL;
91	struct btrfs_key key;
92	struct extent_buffer *eb;
93	int slot;
94	unsigned long offset;
95	__le64 subid_le;
96
97	ret = btrfs_uuid_tree_lookup(uuid_root, uuid, type, subid_cpu);
98	if (ret != -ENOENT)
99		return ret;
100
101	if (WARN_ON_ONCE(!uuid_root)) {
102		ret = -EINVAL;
103		goto out;
104	}
105
106	btrfs_uuid_to_key(uuid, type, &key);
107
108	path = btrfs_alloc_path();
109	if (!path) {
110		ret = -ENOMEM;
111		goto out;
112	}
113
114	ret = btrfs_insert_empty_item(trans, uuid_root, path, &key,
115				      sizeof(subid_le));
116	if (ret == 0) {
117		/* Add an item for the type for the first time */
118		eb = path->nodes[0];
119		slot = path->slots[0];
120		offset = btrfs_item_ptr_offset(eb, slot);
121	} else if (ret == -EEXIST) {
122		/*
123		 * An item with that type already exists.
124		 * Extend the item and store the new subid at the end.
125		 */
126		btrfs_extend_item(trans, path, sizeof(subid_le));
127		eb = path->nodes[0];
128		slot = path->slots[0];
129		offset = btrfs_item_ptr_offset(eb, slot);
130		offset += btrfs_item_size(eb, slot) - sizeof(subid_le);
131	} else {
132		btrfs_warn(fs_info,
133			   "insert uuid item failed %d (0x%016llx, 0x%016llx) type %u!",
134			   ret, key.objectid, key.offset, type);
135		goto out;
136	}
137
138	ret = 0;
139	subid_le = cpu_to_le64(subid_cpu);
140	write_extent_buffer(eb, &subid_le, offset, sizeof(subid_le));
141	btrfs_mark_buffer_dirty(trans, eb);
142
143out:
144	btrfs_free_path(path);
145	return ret;
146}
147
148int btrfs_uuid_tree_remove(struct btrfs_trans_handle *trans, u8 *uuid, u8 type,
149			u64 subid)
150{
151	struct btrfs_fs_info *fs_info = trans->fs_info;
152	struct btrfs_root *uuid_root = fs_info->uuid_root;
153	int ret;
154	struct btrfs_path *path = NULL;
155	struct btrfs_key key;
156	struct extent_buffer *eb;
157	int slot;
158	unsigned long offset;
159	u32 item_size;
160	unsigned long move_dst;
161	unsigned long move_src;
162	unsigned long move_len;
163
164	if (WARN_ON_ONCE(!uuid_root)) {
165		ret = -EINVAL;
166		goto out;
167	}
168
169	btrfs_uuid_to_key(uuid, type, &key);
170
171	path = btrfs_alloc_path();
172	if (!path) {
173		ret = -ENOMEM;
174		goto out;
175	}
176
177	ret = btrfs_search_slot(trans, uuid_root, &key, path, -1, 1);
178	if (ret < 0) {
179		btrfs_warn(fs_info, "error %d while searching for uuid item!",
180			   ret);
181		goto out;
182	}
183	if (ret > 0) {
184		ret = -ENOENT;
185		goto out;
186	}
187
188	eb = path->nodes[0];
189	slot = path->slots[0];
190	offset = btrfs_item_ptr_offset(eb, slot);
191	item_size = btrfs_item_size(eb, slot);
192	if (!IS_ALIGNED(item_size, sizeof(u64))) {
193		btrfs_warn(fs_info, "uuid item with illegal size %lu!",
194			   (unsigned long)item_size);
195		ret = -ENOENT;
196		goto out;
197	}
198	while (item_size) {
199		__le64 read_subid;
200
201		read_extent_buffer(eb, &read_subid, offset, sizeof(read_subid));
202		if (le64_to_cpu(read_subid) == subid)
203			break;
204		offset += sizeof(read_subid);
205		item_size -= sizeof(read_subid);
206	}
207
208	if (!item_size) {
209		ret = -ENOENT;
210		goto out;
211	}
212
213	item_size = btrfs_item_size(eb, slot);
214	if (item_size == sizeof(subid)) {
215		ret = btrfs_del_item(trans, uuid_root, path);
216		goto out;
217	}
218
219	move_dst = offset;
220	move_src = offset + sizeof(subid);
221	move_len = item_size - (move_src - btrfs_item_ptr_offset(eb, slot));
222	memmove_extent_buffer(eb, move_dst, move_src, move_len);
223	btrfs_truncate_item(trans, path, item_size - sizeof(subid), 1);
224
225out:
226	btrfs_free_path(path);
227	return ret;
228}
229
230static int btrfs_uuid_iter_rem(struct btrfs_root *uuid_root, u8 *uuid, u8 type,
231			       u64 subid)
232{
233	struct btrfs_trans_handle *trans;
234	int ret;
235
236	/* 1 - for the uuid item */
237	trans = btrfs_start_transaction(uuid_root, 1);
238	if (IS_ERR(trans)) {
239		ret = PTR_ERR(trans);
240		goto out;
241	}
242
243	ret = btrfs_uuid_tree_remove(trans, uuid, type, subid);
244	btrfs_end_transaction(trans);
245
246out:
247	return ret;
248}
249
250/*
251 * Check if there's an matching subvolume for given UUID
252 *
253 * Return:
254 * 0	check succeeded, the entry is not outdated
255 * > 0	if the check failed, the caller should remove the entry
256 * < 0	if an error occurred
257 */
258static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info,
259				       u8 *uuid, u8 type, u64 subvolid)
260{
261	int ret = 0;
262	struct btrfs_root *subvol_root;
263
264	if (type != BTRFS_UUID_KEY_SUBVOL &&
265	    type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
266		goto out;
267
268	subvol_root = btrfs_get_fs_root(fs_info, subvolid, true);
269	if (IS_ERR(subvol_root)) {
270		ret = PTR_ERR(subvol_root);
271		if (ret == -ENOENT)
272			ret = 1;
273		goto out;
274	}
275
276	switch (type) {
277	case BTRFS_UUID_KEY_SUBVOL:
278		if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE))
279			ret = 1;
280		break;
281	case BTRFS_UUID_KEY_RECEIVED_SUBVOL:
282		if (memcmp(uuid, subvol_root->root_item.received_uuid,
283			   BTRFS_UUID_SIZE))
284			ret = 1;
285		break;
286	}
287	btrfs_put_root(subvol_root);
288out:
289	return ret;
290}
291
292int btrfs_uuid_tree_iterate(struct btrfs_fs_info *fs_info)
293{
294	struct btrfs_root *root = fs_info->uuid_root;
295	struct btrfs_key key;
296	struct btrfs_path *path;
297	int ret = 0;
298	struct extent_buffer *leaf;
299	int slot;
300	u32 item_size;
301	unsigned long offset;
302
303	path = btrfs_alloc_path();
304	if (!path) {
305		ret = -ENOMEM;
306		goto out;
307	}
308
309	key.objectid = 0;
310	key.type = 0;
311	key.offset = 0;
312
313again_search_slot:
314	ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION);
315	if (ret) {
316		if (ret > 0)
317			ret = 0;
318		goto out;
319	}
320
321	while (1) {
322		if (btrfs_fs_closing(fs_info)) {
323			ret = -EINTR;
324			goto out;
325		}
326		cond_resched();
327		leaf = path->nodes[0];
328		slot = path->slots[0];
329		btrfs_item_key_to_cpu(leaf, &key, slot);
330
331		if (key.type != BTRFS_UUID_KEY_SUBVOL &&
332		    key.type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
333			goto skip;
334
335		offset = btrfs_item_ptr_offset(leaf, slot);
336		item_size = btrfs_item_size(leaf, slot);
337		if (!IS_ALIGNED(item_size, sizeof(u64))) {
338			btrfs_warn(fs_info,
339				   "uuid item with illegal size %lu!",
340				   (unsigned long)item_size);
341			goto skip;
342		}
343		while (item_size) {
344			u8 uuid[BTRFS_UUID_SIZE];
345			__le64 subid_le;
346			u64 subid_cpu;
347
348			put_unaligned_le64(key.objectid, uuid);
349			put_unaligned_le64(key.offset, uuid + sizeof(u64));
350			read_extent_buffer(leaf, &subid_le, offset,
351					   sizeof(subid_le));
352			subid_cpu = le64_to_cpu(subid_le);
353			ret = btrfs_check_uuid_tree_entry(fs_info, uuid,
354							  key.type, subid_cpu);
355			if (ret < 0)
356				goto out;
357			if (ret > 0) {
358				btrfs_release_path(path);
359				ret = btrfs_uuid_iter_rem(root, uuid, key.type,
360							  subid_cpu);
361				if (ret == 0) {
362					/*
363					 * this might look inefficient, but the
364					 * justification is that it is an
365					 * exception that check_func returns 1,
366					 * and that in the regular case only one
367					 * entry per UUID exists.
368					 */
369					goto again_search_slot;
370				}
371				if (ret < 0 && ret != -ENOENT)
372					goto out;
373				key.offset++;
374				goto again_search_slot;
375			}
376			item_size -= sizeof(subid_le);
377			offset += sizeof(subid_le);
378		}
379
380skip:
381		ret = btrfs_next_item(root, path);
382		if (ret == 0)
383			continue;
384		else if (ret > 0)
385			ret = 0;
386		break;
387	}
388
389out:
390	btrfs_free_path(path);
391	return ret;
392}
393