]>
git.ipfire.org Git - thirdparty/u-boot.git/blob - fs/btrfs/ctree.c
1 // SPDX-License-Identifier: GPL-2.0+
3 * BTRFS filesystem implementation for U-Boot
5 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
12 int btrfs_comp_keys(struct btrfs_key
*a
, struct btrfs_key
*b
)
14 if (a
->objectid
> b
->objectid
)
16 if (a
->objectid
< b
->objectid
)
18 if (a
->type
> b
->type
)
20 if (a
->type
< b
->type
)
22 if (a
->offset
> b
->offset
)
24 if (a
->offset
< b
->offset
)
29 int btrfs_comp_keys_type(struct btrfs_key
*a
, struct btrfs_key
*b
)
31 if (a
->objectid
> b
->objectid
)
33 if (a
->objectid
< b
->objectid
)
35 if (a
->type
> b
->type
)
37 if (a
->type
< b
->type
)
42 static int generic_bin_search(void *addr
, int item_size
, struct btrfs_key
*key
,
45 int low
= 0, high
= max
, mid
, ret
;
46 struct btrfs_key
*tmp
;
49 mid
= (low
+ high
) / 2;
51 tmp
= (struct btrfs_key
*) ((u8
*) addr
+ mid
*item_size
);
52 ret
= btrfs_comp_keys(tmp
, key
);
68 int btrfs_bin_search(union btrfs_tree_node
*p
, struct btrfs_key
*key
,
74 if (p
->header
.level
) {
76 size
= sizeof(struct btrfs_key_ptr
);
79 size
= sizeof(struct btrfs_item
);
82 return generic_bin_search(addr
, size
, key
, p
->header
.nritems
, slot
);
85 static void clear_path(struct btrfs_path
*p
)
89 for (i
= 0; i
< BTRFS_MAX_LEVEL
; ++i
) {
95 void btrfs_free_path(struct btrfs_path
*p
)
99 for (i
= 0; i
< BTRFS_MAX_LEVEL
; ++i
) {
107 static int read_tree_node(u64 physical
, union btrfs_tree_node
**buf
)
109 ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header
, hdr
,
110 sizeof(struct btrfs_header
));
111 unsigned long size
, offset
= sizeof(*hdr
);
112 union btrfs_tree_node
*res
;
115 if (!btrfs_devread(physical
, sizeof(*hdr
), hdr
))
118 btrfs_header_to_cpu(hdr
);
121 size
= sizeof(struct btrfs_node
)
122 + hdr
->nritems
* sizeof(struct btrfs_key_ptr
);
124 size
= btrfs_info
.sb
.nodesize
;
126 res
= malloc_cache_aligned(size
);
128 debug("%s: malloc failed\n", __func__
);
132 if (!btrfs_devread(physical
+ offset
, size
- offset
,
133 ((u8
*) res
) + offset
)) {
138 memcpy(&res
->header
, hdr
, sizeof(*hdr
));
140 for (i
= 0; i
< hdr
->nritems
; ++i
)
141 btrfs_key_ptr_to_cpu(&res
->node
.ptrs
[i
]);
143 for (i
= 0; i
< hdr
->nritems
; ++i
)
144 btrfs_item_to_cpu(&res
->leaf
.items
[i
]);
151 int btrfs_search_tree(const struct btrfs_root
*root
, struct btrfs_key
*key
,
152 struct btrfs_path
*p
)
156 u64 logical
, physical
;
157 union btrfs_tree_node
*buf
;
161 logical
= root
->bytenr
;
163 for (i
= 0; i
< BTRFS_MAX_LEVEL
; ++i
) {
164 physical
= btrfs_map_logical_to_physical(logical
);
165 if (physical
== -1ULL)
168 if (read_tree_node(physical
, &buf
))
171 lvl
= buf
->header
.level
;
172 if (i
&& prev_lvl
!= lvl
+ 1) {
173 printf("%s: invalid level in header at %llu\n",
179 ret
= btrfs_bin_search(buf
, key
, &slot
);
182 if (ret
&& slot
> 0 && lvl
)
185 p
->slots
[lvl
] = slot
;
189 logical
= buf
->node
.ptrs
[slot
].blockptr
;
200 static int jump_leaf(struct btrfs_path
*path
, int dir
)
204 int level
= 1, from_level
, i
;
206 dir
= dir
>= 0 ? 1 : -1;
210 while (level
< BTRFS_MAX_LEVEL
) {
214 slot
= p
.slots
[level
];
215 if ((dir
> 0 && slot
+ dir
>= p
.nodes
[level
]->header
.nritems
)
216 || (dir
< 0 && !slot
))
222 if (level
== BTRFS_MAX_LEVEL
)
225 p
.slots
[level
] = slot
+ dir
;
230 u64 logical
, physical
;
232 slot
= p
.slots
[level
+ 1];
233 logical
= p
.nodes
[level
+ 1]->node
.ptrs
[slot
].blockptr
;
234 physical
= btrfs_map_logical_to_physical(logical
);
235 if (physical
== -1ULL)
238 if (read_tree_node(physical
, &p
.nodes
[level
]))
244 p
.slots
[level
] = p
.nodes
[level
]->header
.nritems
- 1;
248 /* Free rewritten nodes in path */
249 for (i
= 0; i
<= from_level
; ++i
)
250 free(path
->nodes
[i
]);
256 /* Free rewritten nodes in p */
257 for (i
= level
+ 1; i
<= from_level
; ++i
)
262 int btrfs_prev_slot(struct btrfs_path
*p
)
265 return jump_leaf(p
, -1);
271 int btrfs_next_slot(struct btrfs_path
*p
)
273 struct btrfs_leaf
*leaf
= &p
->nodes
[0]->leaf
;
275 if (p
->slots
[0] >= leaf
->header
.nritems
)
276 return jump_leaf(p
, 1);