1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * linux/fs/hfsplus/bfind.c |
4 | * |
5 | * Copyright (C) 2001 |
6 | * Brad Boyer (flar@allandria.com) |
7 | * (C) 2003 Ardis Technologies <roman@ardistech.com> |
8 | * |
9 | * Search routines for btrees |
10 | */ |
11 | |
12 | #include <linux/slab.h> |
13 | #include "hfsplus_fs.h" |
14 | |
15 | int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) |
16 | { |
17 | void *ptr; |
18 | |
19 | fd->tree = tree; |
20 | fd->bnode = NULL; |
21 | ptr = kmalloc(size: tree->max_key_len * 2 + 4, GFP_KERNEL); |
22 | if (!ptr) |
23 | return -ENOMEM; |
24 | fd->search_key = ptr; |
25 | fd->key = ptr + tree->max_key_len + 2; |
26 | hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n" , |
27 | tree->cnid, __builtin_return_address(0)); |
28 | switch (tree->cnid) { |
29 | case HFSPLUS_CAT_CNID: |
30 | mutex_lock_nested(lock: &tree->tree_lock, subclass: CATALOG_BTREE_MUTEX); |
31 | break; |
32 | case HFSPLUS_EXT_CNID: |
33 | mutex_lock_nested(lock: &tree->tree_lock, subclass: EXTENTS_BTREE_MUTEX); |
34 | break; |
35 | case HFSPLUS_ATTR_CNID: |
36 | mutex_lock_nested(lock: &tree->tree_lock, subclass: ATTR_BTREE_MUTEX); |
37 | break; |
38 | default: |
39 | BUG(); |
40 | } |
41 | return 0; |
42 | } |
43 | |
44 | void hfs_find_exit(struct hfs_find_data *fd) |
45 | { |
46 | hfs_bnode_put(node: fd->bnode); |
47 | kfree(objp: fd->search_key); |
48 | hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n" , |
49 | fd->tree->cnid, __builtin_return_address(0)); |
50 | mutex_unlock(lock: &fd->tree->tree_lock); |
51 | fd->tree = NULL; |
52 | } |
53 | |
54 | int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode, |
55 | struct hfs_find_data *fd, |
56 | int *begin, |
57 | int *end, |
58 | int *cur_rec) |
59 | { |
60 | __be32 cur_cnid; |
61 | __be32 search_cnid; |
62 | |
63 | if (bnode->tree->cnid == HFSPLUS_EXT_CNID) { |
64 | cur_cnid = fd->key->ext.cnid; |
65 | search_cnid = fd->search_key->ext.cnid; |
66 | } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) { |
67 | cur_cnid = fd->key->cat.parent; |
68 | search_cnid = fd->search_key->cat.parent; |
69 | } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) { |
70 | cur_cnid = fd->key->attr.cnid; |
71 | search_cnid = fd->search_key->attr.cnid; |
72 | } else { |
73 | cur_cnid = 0; /* used-uninitialized warning */ |
74 | search_cnid = 0; |
75 | BUG(); |
76 | } |
77 | |
78 | if (cur_cnid == search_cnid) { |
79 | (*end) = (*cur_rec); |
80 | if ((*begin) == (*end)) |
81 | return 1; |
82 | } else { |
83 | if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid)) |
84 | (*begin) = (*cur_rec) + 1; |
85 | else |
86 | (*end) = (*cur_rec) - 1; |
87 | } |
88 | |
89 | return 0; |
90 | } |
91 | |
92 | int hfs_find_rec_by_key(struct hfs_bnode *bnode, |
93 | struct hfs_find_data *fd, |
94 | int *begin, |
95 | int *end, |
96 | int *cur_rec) |
97 | { |
98 | int cmpval; |
99 | |
100 | cmpval = bnode->tree->keycmp(fd->key, fd->search_key); |
101 | if (!cmpval) { |
102 | (*end) = (*cur_rec); |
103 | return 1; |
104 | } |
105 | if (cmpval < 0) |
106 | (*begin) = (*cur_rec) + 1; |
107 | else |
108 | *(end) = (*cur_rec) - 1; |
109 | |
110 | return 0; |
111 | } |
112 | |
113 | /* Find the record in bnode that best matches key (not greater than...)*/ |
114 | int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, |
115 | search_strategy_t rec_found) |
116 | { |
117 | u16 off, len, keylen; |
118 | int rec; |
119 | int b, e; |
120 | int res; |
121 | |
122 | BUG_ON(!rec_found); |
123 | b = 0; |
124 | e = bnode->num_recs - 1; |
125 | res = -ENOENT; |
126 | do { |
127 | rec = (e + b) / 2; |
128 | len = hfs_brec_lenoff(node: bnode, rec, off: &off); |
129 | keylen = hfs_brec_keylen(node: bnode, rec); |
130 | if (keylen == 0) { |
131 | res = -EINVAL; |
132 | goto fail; |
133 | } |
134 | hfs_bnode_read(node: bnode, buf: fd->key, off, len: keylen); |
135 | if (rec_found(bnode, fd, &b, &e, &rec)) { |
136 | res = 0; |
137 | goto done; |
138 | } |
139 | } while (b <= e); |
140 | |
141 | if (rec != e && e >= 0) { |
142 | len = hfs_brec_lenoff(node: bnode, rec: e, off: &off); |
143 | keylen = hfs_brec_keylen(node: bnode, rec: e); |
144 | if (keylen == 0) { |
145 | res = -EINVAL; |
146 | goto fail; |
147 | } |
148 | hfs_bnode_read(node: bnode, buf: fd->key, off, len: keylen); |
149 | } |
150 | |
151 | done: |
152 | fd->record = e; |
153 | fd->keyoffset = off; |
154 | fd->keylength = keylen; |
155 | fd->entryoffset = off + keylen; |
156 | fd->entrylength = len - keylen; |
157 | |
158 | fail: |
159 | return res; |
160 | } |
161 | |
162 | /* Traverse a B*Tree from the root to a leaf finding best fit to key */ |
163 | /* Return allocated copy of node found, set recnum to best record */ |
164 | int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) |
165 | { |
166 | struct hfs_btree *tree; |
167 | struct hfs_bnode *bnode; |
168 | u32 nidx, parent; |
169 | __be32 data; |
170 | int height, res; |
171 | |
172 | tree = fd->tree; |
173 | if (fd->bnode) |
174 | hfs_bnode_put(node: fd->bnode); |
175 | fd->bnode = NULL; |
176 | nidx = tree->root; |
177 | if (!nidx) |
178 | return -ENOENT; |
179 | height = tree->depth; |
180 | res = 0; |
181 | parent = 0; |
182 | for (;;) { |
183 | bnode = hfs_bnode_find(tree, num: nidx); |
184 | if (IS_ERR(ptr: bnode)) { |
185 | res = PTR_ERR(ptr: bnode); |
186 | bnode = NULL; |
187 | break; |
188 | } |
189 | if (bnode->height != height) |
190 | goto invalid; |
191 | if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) |
192 | goto invalid; |
193 | bnode->parent = parent; |
194 | |
195 | res = __hfs_brec_find(bnode, fd, rec_found: do_key_compare); |
196 | if (!height) |
197 | break; |
198 | if (fd->record < 0) |
199 | goto release; |
200 | |
201 | parent = nidx; |
202 | hfs_bnode_read(node: bnode, buf: &data, off: fd->entryoffset, len: 4); |
203 | nidx = be32_to_cpu(data); |
204 | hfs_bnode_put(node: bnode); |
205 | } |
206 | fd->bnode = bnode; |
207 | return res; |
208 | |
209 | invalid: |
210 | pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n" , |
211 | height, bnode->height, bnode->type, nidx, parent); |
212 | res = -EIO; |
213 | release: |
214 | hfs_bnode_put(node: bnode); |
215 | return res; |
216 | } |
217 | |
218 | int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) |
219 | { |
220 | int res; |
221 | |
222 | res = hfs_brec_find(fd, do_key_compare: hfs_find_rec_by_key); |
223 | if (res) |
224 | return res; |
225 | if (fd->entrylength > rec_len) |
226 | return -EINVAL; |
227 | hfs_bnode_read(node: fd->bnode, buf: rec, off: fd->entryoffset, len: fd->entrylength); |
228 | return 0; |
229 | } |
230 | |
231 | int hfs_brec_goto(struct hfs_find_data *fd, int cnt) |
232 | { |
233 | struct hfs_btree *tree; |
234 | struct hfs_bnode *bnode; |
235 | int idx, res = 0; |
236 | u16 off, len, keylen; |
237 | |
238 | bnode = fd->bnode; |
239 | tree = bnode->tree; |
240 | |
241 | if (cnt < 0) { |
242 | cnt = -cnt; |
243 | while (cnt > fd->record) { |
244 | cnt -= fd->record + 1; |
245 | fd->record = bnode->num_recs - 1; |
246 | idx = bnode->prev; |
247 | if (!idx) { |
248 | res = -ENOENT; |
249 | goto out; |
250 | } |
251 | hfs_bnode_put(node: bnode); |
252 | bnode = hfs_bnode_find(tree, num: idx); |
253 | if (IS_ERR(ptr: bnode)) { |
254 | res = PTR_ERR(ptr: bnode); |
255 | bnode = NULL; |
256 | goto out; |
257 | } |
258 | } |
259 | fd->record -= cnt; |
260 | } else { |
261 | while (cnt >= bnode->num_recs - fd->record) { |
262 | cnt -= bnode->num_recs - fd->record; |
263 | fd->record = 0; |
264 | idx = bnode->next; |
265 | if (!idx) { |
266 | res = -ENOENT; |
267 | goto out; |
268 | } |
269 | hfs_bnode_put(node: bnode); |
270 | bnode = hfs_bnode_find(tree, num: idx); |
271 | if (IS_ERR(ptr: bnode)) { |
272 | res = PTR_ERR(ptr: bnode); |
273 | bnode = NULL; |
274 | goto out; |
275 | } |
276 | } |
277 | fd->record += cnt; |
278 | } |
279 | |
280 | len = hfs_brec_lenoff(node: bnode, rec: fd->record, off: &off); |
281 | keylen = hfs_brec_keylen(node: bnode, rec: fd->record); |
282 | if (keylen == 0) { |
283 | res = -EINVAL; |
284 | goto out; |
285 | } |
286 | fd->keyoffset = off; |
287 | fd->keylength = keylen; |
288 | fd->entryoffset = off + keylen; |
289 | fd->entrylength = len - keylen; |
290 | hfs_bnode_read(node: bnode, buf: fd->key, off, len: keylen); |
291 | out: |
292 | fd->bnode = bnode; |
293 | return res; |
294 | } |
295 | |