]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/btrfs/ctree.c
2 * BTRFS filesystem implementation for U-Boot
4 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
6 * SPDX-License-Identifier: GPL-2.0+
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
;
50 printf("\tsearching %llu %i\n", key
->objectid
, key
->type
);
51 for (i
= 0; i
< max
; ++i
) {
52 tmp
= (struct btrfs_key
*) ((u8
*) addr
+ i
*item_size
);
53 printf("\t\t%llu %i\n", tmp
->objectid
, tmp
->type
);
59 mid
= (low
+ high
) / 2;
61 tmp
= (struct btrfs_key
*) ((u8
*) addr
+ mid
*item_size
);
62 ret
= btrfs_comp_keys(tmp
, key
);
78 int btrfs_bin_search(union btrfs_tree_node
*p
, struct btrfs_key
*key
,
84 if (p
->header
.level
) {
86 size
= sizeof(struct btrfs_key_ptr
);
89 size
= sizeof(struct btrfs_item
);
92 return generic_bin_search(addr
, size
, key
, p
->header
.nritems
, slot
);
95 static void clear_path(struct btrfs_path
*p
)
99 for (i
= 0; i
< BTRFS_MAX_LEVEL
; ++i
) {
105 void btrfs_free_path(struct btrfs_path
*p
)
109 for (i
= 0; i
< BTRFS_MAX_LEVEL
; ++i
) {
117 static int read_tree_node(u64 physical
, union btrfs_tree_node
**buf
)
119 struct btrfs_header hdr
;
120 unsigned long size
, offset
= sizeof(hdr
);
121 union btrfs_tree_node
*res
;
124 if (!btrfs_devread(physical
, sizeof(hdr
), &hdr
))
127 btrfs_header_to_cpu(&hdr
);
130 size
= sizeof(struct btrfs_node
)
131 + hdr
.nritems
* sizeof(struct btrfs_key_ptr
);
133 size
= btrfs_info
.sb
.nodesize
;
137 debug("%s: malloc failed\n", __func__
);
141 if (!btrfs_devread(physical
+ offset
, size
- offset
,
142 ((u8
*) res
) + offset
)) {
149 for (i
= 0; i
< hdr
.nritems
; ++i
)
150 btrfs_key_ptr_to_cpu(&res
->node
.ptrs
[i
]);
152 for (i
= 0; i
< hdr
.nritems
; ++i
)
153 btrfs_item_to_cpu(&res
->leaf
.items
[i
]);
160 int btrfs_search_tree(const struct btrfs_root
*root
, struct btrfs_key
*key
,
161 struct btrfs_path
*p
)
165 u64 logical
, physical
;
166 union btrfs_tree_node
*buf
;
170 logical
= root
->bytenr
;
172 for (i
= 0; i
< BTRFS_MAX_LEVEL
; ++i
) {
173 physical
= btrfs_map_logical_to_physical(logical
);
174 if (physical
== -1ULL)
177 if (read_tree_node(physical
, &buf
))
180 lvl
= buf
->header
.level
;
181 if (i
&& prev_lvl
!= lvl
+ 1) {
182 printf("%s: invalid level in header at %llu\n",
188 ret
= btrfs_bin_search(buf
, key
, &slot
);
191 if (ret
&& slot
> 0 && lvl
)
194 p
->slots
[lvl
] = slot
;
198 logical
= buf
->node
.ptrs
[slot
].blockptr
;
209 static int jump_leaf(struct btrfs_path
*path
, int dir
)
213 int level
= 1, from_level
, i
;
215 dir
= dir
>= 0 ? 1 : -1;
219 while (level
< BTRFS_MAX_LEVEL
) {
223 slot
= p
.slots
[level
];
224 if ((dir
> 0 && slot
+ dir
>= p
.nodes
[level
]->header
.nritems
)
225 || (dir
< 0 && !slot
))
231 if (level
== BTRFS_MAX_LEVEL
)
234 p
.slots
[level
] = slot
+ dir
;
239 u64 logical
, physical
;
241 slot
= p
.slots
[level
+ 1];
242 logical
= p
.nodes
[level
+ 1]->node
.ptrs
[slot
].blockptr
;
243 physical
= btrfs_map_logical_to_physical(logical
);
244 if (physical
== -1ULL)
247 if (read_tree_node(physical
, &p
.nodes
[level
]))
253 p
.slots
[level
] = p
.nodes
[level
]->header
.nritems
- 1;
257 /* Free rewritten nodes in path */
258 for (i
= 0; i
<= from_level
; ++i
)
259 free(path
->nodes
[i
]);
265 /* Free rewritten nodes in p */
266 for (i
= level
+ 1; i
<= from_level
; ++i
)
271 int btrfs_prev_slot(struct btrfs_path
*p
)
274 return jump_leaf(p
, -1);
280 int btrfs_next_slot(struct btrfs_path
*p
)
282 struct btrfs_leaf
*leaf
= &p
->nodes
[0]->leaf
;
284 if (p
->slots
[0] >= leaf
->header
.nritems
)
285 return jump_leaf(p
, 1);