1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * linux/fs/hfs/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 "btree.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 HFS_CAT_CNID: |
30 | mutex_lock_nested(lock: &tree->tree_lock, subclass: CATALOG_BTREE_MUTEX); |
31 | break; |
32 | case HFS_EXT_CNID: |
33 | mutex_lock_nested(lock: &tree->tree_lock, subclass: EXTENTS_BTREE_MUTEX); |
34 | break; |
35 | case HFS_ATTR_CNID: |
36 | mutex_lock_nested(lock: &tree->tree_lock, subclass: ATTR_BTREE_MUTEX); |
37 | break; |
38 | default: |
39 | return -EINVAL; |
40 | } |
41 | return 0; |
42 | } |
43 | |
44 | void hfs_find_exit(struct hfs_find_data *fd) |
45 | { |
46 | hfs_bnode_put(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 | /* Find the record in bnode that best matches key (not greater than...)*/ |
55 | int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd) |
56 | { |
57 | int cmpval; |
58 | u16 off, len, keylen; |
59 | int rec; |
60 | int b, e; |
61 | int res; |
62 | |
63 | b = 0; |
64 | e = bnode->num_recs - 1; |
65 | res = -ENOENT; |
66 | do { |
67 | rec = (e + b) / 2; |
68 | len = hfs_brec_lenoff(bnode, rec, &off); |
69 | keylen = hfs_brec_keylen(bnode, rec); |
70 | if (keylen == 0) { |
71 | res = -EINVAL; |
72 | goto fail; |
73 | } |
74 | hfs_bnode_read(bnode, fd->key, off, keylen); |
75 | cmpval = bnode->tree->keycmp(fd->key, fd->search_key); |
76 | if (!cmpval) { |
77 | e = rec; |
78 | res = 0; |
79 | goto done; |
80 | } |
81 | if (cmpval < 0) |
82 | b = rec + 1; |
83 | else |
84 | e = rec - 1; |
85 | } while (b <= e); |
86 | if (rec != e && e >= 0) { |
87 | len = hfs_brec_lenoff(bnode, e, &off); |
88 | keylen = hfs_brec_keylen(bnode, e); |
89 | if (keylen == 0) { |
90 | res = -EINVAL; |
91 | goto fail; |
92 | } |
93 | hfs_bnode_read(bnode, fd->key, off, keylen); |
94 | } |
95 | done: |
96 | fd->record = e; |
97 | fd->keyoffset = off; |
98 | fd->keylength = keylen; |
99 | fd->entryoffset = off + keylen; |
100 | fd->entrylength = len - keylen; |
101 | fail: |
102 | return res; |
103 | } |
104 | |
105 | /* Traverse a B*Tree from the root to a leaf finding best fit to key */ |
106 | /* Return allocated copy of node found, set recnum to best record */ |
107 | int hfs_brec_find(struct hfs_find_data *fd) |
108 | { |
109 | struct hfs_btree *tree; |
110 | struct hfs_bnode *bnode; |
111 | u32 nidx, parent; |
112 | __be32 data; |
113 | int height, res; |
114 | |
115 | tree = fd->tree; |
116 | if (fd->bnode) |
117 | hfs_bnode_put(fd->bnode); |
118 | fd->bnode = NULL; |
119 | nidx = tree->root; |
120 | if (!nidx) |
121 | return -ENOENT; |
122 | height = tree->depth; |
123 | res = 0; |
124 | parent = 0; |
125 | for (;;) { |
126 | bnode = hfs_bnode_find(tree, nidx); |
127 | if (IS_ERR(ptr: bnode)) { |
128 | res = PTR_ERR(ptr: bnode); |
129 | bnode = NULL; |
130 | break; |
131 | } |
132 | if (bnode->height != height) |
133 | goto invalid; |
134 | if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) |
135 | goto invalid; |
136 | bnode->parent = parent; |
137 | |
138 | res = __hfs_brec_find(bnode, fd); |
139 | if (!height) |
140 | break; |
141 | if (fd->record < 0) |
142 | goto release; |
143 | |
144 | parent = nidx; |
145 | hfs_bnode_read(bnode, &data, fd->entryoffset, 4); |
146 | nidx = be32_to_cpu(data); |
147 | hfs_bnode_put(bnode); |
148 | } |
149 | fd->bnode = bnode; |
150 | return res; |
151 | |
152 | invalid: |
153 | pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n" , |
154 | height, bnode->height, bnode->type, nidx, parent); |
155 | res = -EIO; |
156 | release: |
157 | hfs_bnode_put(bnode); |
158 | return res; |
159 | } |
160 | |
161 | int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) |
162 | { |
163 | int res; |
164 | |
165 | res = hfs_brec_find(fd); |
166 | if (res) |
167 | return res; |
168 | if (fd->entrylength > rec_len) |
169 | return -EINVAL; |
170 | hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); |
171 | return 0; |
172 | } |
173 | |
174 | int hfs_brec_goto(struct hfs_find_data *fd, int cnt) |
175 | { |
176 | struct hfs_btree *tree; |
177 | struct hfs_bnode *bnode; |
178 | int idx, res = 0; |
179 | u16 off, len, keylen; |
180 | |
181 | bnode = fd->bnode; |
182 | tree = bnode->tree; |
183 | |
184 | if (cnt < 0) { |
185 | cnt = -cnt; |
186 | while (cnt > fd->record) { |
187 | cnt -= fd->record + 1; |
188 | fd->record = bnode->num_recs - 1; |
189 | idx = bnode->prev; |
190 | if (!idx) { |
191 | res = -ENOENT; |
192 | goto out; |
193 | } |
194 | hfs_bnode_put(bnode); |
195 | bnode = hfs_bnode_find(tree, idx); |
196 | if (IS_ERR(ptr: bnode)) { |
197 | res = PTR_ERR(ptr: bnode); |
198 | bnode = NULL; |
199 | goto out; |
200 | } |
201 | } |
202 | fd->record -= cnt; |
203 | } else { |
204 | while (cnt >= bnode->num_recs - fd->record) { |
205 | cnt -= bnode->num_recs - fd->record; |
206 | fd->record = 0; |
207 | idx = bnode->next; |
208 | if (!idx) { |
209 | res = -ENOENT; |
210 | goto out; |
211 | } |
212 | hfs_bnode_put(bnode); |
213 | bnode = hfs_bnode_find(tree, idx); |
214 | if (IS_ERR(ptr: bnode)) { |
215 | res = PTR_ERR(ptr: bnode); |
216 | bnode = NULL; |
217 | goto out; |
218 | } |
219 | } |
220 | fd->record += cnt; |
221 | } |
222 | |
223 | len = hfs_brec_lenoff(bnode, fd->record, &off); |
224 | keylen = hfs_brec_keylen(bnode, fd->record); |
225 | if (keylen == 0) { |
226 | res = -EINVAL; |
227 | goto out; |
228 | } |
229 | fd->keyoffset = off; |
230 | fd->keylength = keylen; |
231 | fd->entryoffset = off + keylen; |
232 | fd->entrylength = len - keylen; |
233 | hfs_bnode_read(bnode, fd->key, off, keylen); |
234 | out: |
235 | fd->bnode = bnode; |
236 | return res; |
237 | } |
238 | |