| 1 |
// SPDX-License-Identifier: GPL-2.0 |
| 2 |
/* |
| 3 |
* linux/fs/hfsplus/bfind.c |
| 4 |
* |
| 5 |
* Copyright (C) 2001 |
| 6 |
* Brad Boyer ([email protected]) |
| 7 |
* (C) 2003 Ardis Technologies <[email protected]> |
| 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 = kzalloc(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("cnid %d, caller %ps\n", |
| 27 |
tree->cnid, __builtin_return_address(0)); |
| 28 |
mutex_lock_nested(&tree->tree_lock, |
| 29 |
hfsplus_btree_lock_class(tree)); |
| 30 |
return 0; |
| 31 |
} |
| 32 |
|
| 33 |
void hfs_find_exit(struct hfs_find_data *fd) |
| 34 |
{ |
| 35 |
hfs_bnode_put(fd->bnode); |
| 36 |
kfree(fd->search_key); |
| 37 |
hfs_dbg("cnid %d, caller %ps\n", |
| 38 |
fd->tree->cnid, __builtin_return_address(0)); |
| 39 |
mutex_unlock(&fd->tree->tree_lock); |
| 40 |
fd->tree = NULL; |
| 41 |
} |
| 42 |
|
| 43 |
int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode, |
| 44 |
struct hfs_find_data *fd, |
| 45 |
int *begin, |
| 46 |
int *end, |
| 47 |
int *cur_rec) |
| 48 |
{ |
| 49 |
__be32 cur_cnid; |
| 50 |
__be32 search_cnid; |
| 51 |
|
| 52 |
if (bnode->tree->cnid == HFSPLUS_EXT_CNID) { |
| 53 |
cur_cnid = fd->key->ext.cnid; |
| 54 |
search_cnid = fd->search_key->ext.cnid; |
| 55 |
} else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) { |
| 56 |
cur_cnid = fd->key->cat.parent; |
| 57 |
search_cnid = fd->search_key->cat.parent; |
| 58 |
} else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) { |
| 59 |
cur_cnid = fd->key->attr.cnid; |
| 60 |
search_cnid = fd->search_key->attr.cnid; |
| 61 |
} else { |
| 62 |
cur_cnid = 0; /* used-uninitialized warning */ |
| 63 |
search_cnid = 0; |
| 64 |
BUG(); |
| 65 |
} |
| 66 |
|
| 67 |
if (cur_cnid == search_cnid) { |
| 68 |
(*end) = (*cur_rec); |
| 69 |
if ((*begin) == (*end)) |
| 70 |
return 1; |
| 71 |
} else { |
| 72 |
if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid)) |
| 73 |
(*begin) = (*cur_rec) + 1; |
| 74 |
else |
| 75 |
(*end) = (*cur_rec) - 1; |
| 76 |
} |
| 77 |
|
| 78 |
return 0; |
| 79 |
} |
| 80 |
|
| 81 |
int hfs_find_rec_by_key(struct hfs_bnode *bnode, |
| 82 |
struct hfs_find_data *fd, |
| 83 |
int *begin, |
| 84 |
int *end, |
| 85 |
int *cur_rec) |
| 86 |
{ |
| 87 |
int cmpval; |
| 88 |
|
| 89 |
cmpval = bnode->tree->keycmp(fd->key, fd->search_key); |
| 90 |
if (!cmpval) { |
| 91 |
(*end) = (*cur_rec); |
| 92 |
return 1; |
| 93 |
} |
| 94 |
if (cmpval < 0) |
| 95 |
(*begin) = (*cur_rec) + 1; |
| 96 |
else |
| 97 |
*(end) = (*cur_rec) - 1; |
| 98 |
|
| 99 |
return 0; |
| 100 |
} |
| 101 |
|
| 102 |
/* Find the record in bnode that best matches key (not greater than...)*/ |
| 103 |
int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, |
| 104 |
search_strategy_t rec_found) |
| 105 |
{ |
| 106 |
u16 off, len, keylen; |
| 107 |
int rec; |
| 108 |
int b, e; |
| 109 |
int res; |
| 110 |
|
| 111 |
BUG_ON(!rec_found); |
| 112 |
b = 0; |
| 113 |
e = bnode->num_recs - 1; |
| 114 |
res = -ENOENT; |
| 115 |
do { |
| 116 |
rec = (e + b) / 2; |
| 117 |
len = hfs_brec_lenoff(bnode, rec, &off); |
| 118 |
keylen = hfs_brec_keylen(bnode, rec); |
| 119 |
if (keylen == 0) { |
| 120 |
res = -EINVAL; |
| 121 |
goto fail; |
| 122 |
} |
| 123 |
hfs_bnode_read(bnode, fd->key, off, keylen); |
| 124 |
if (rec_found(bnode, fd, &b, &e, &rec)) { |
| 125 |
res = 0; |
| 126 |
goto done; |
| 127 |
} |
| 128 |
} while (b <= e); |
| 129 |
|
| 130 |
if (rec != e && e >= 0) { |
| 131 |
len = hfs_brec_lenoff(bnode, e, &off); |
| 132 |
keylen = hfs_brec_keylen(bnode, e); |
| 133 |
if (keylen == 0) { |
| 134 |
res = -EINVAL; |
| 135 |
goto fail; |
| 136 |
} |
| 137 |
hfs_bnode_read(bnode, fd->key, off, keylen); |
| 138 |
} |
| 139 |
|
| 140 |
done: |
| 141 |
fd->record = e; |
| 142 |
fd->keyoffset = off; |
| 143 |
fd->keylength = keylen; |
| 144 |
fd->entryoffset = off + keylen; |
| 145 |
fd->entrylength = len - keylen; |
| 146 |
|
| 147 |
fail: |
| 148 |
return res; |
| 149 |
} |
| 150 |
|
| 151 |
/* Traverse a B*Tree from the root to a leaf finding best fit to key */ |
| 152 |
/* Return allocated copy of node found, set recnum to best record */ |
| 153 |
int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) |
| 154 |
{ |
| 155 |
struct hfs_btree *tree; |
| 156 |
struct hfs_bnode *bnode; |
| 157 |
u32 nidx, parent; |
| 158 |
__be32 data; |
| 159 |
int height, res; |
| 160 |
|
| 161 |
fd->record = -1; |
| 162 |
fd->keyoffset = -1; |
| 163 |
fd->keylength = -1; |
| 164 |
fd->entryoffset = -1; |
| 165 |
fd->entrylength = -1; |
| 166 |
|
| 167 |
tree = fd->tree; |
| 168 |
if (fd->bnode) |
| 169 |
hfs_bnode_put(fd->bnode); |
| 170 |
fd->bnode = NULL; |
| 171 |
nidx = tree->root; |
| 172 |
if (!nidx) |
| 173 |
return -ENOENT; |
| 174 |
height = tree->depth; |
| 175 |
res = 0; |
| 176 |
parent = 0; |
| 177 |
for (;;) { |
| 178 |
bnode = hfs_bnode_find(tree, nidx); |
| 179 |
if (IS_ERR(bnode)) { |
| 180 |
res = PTR_ERR(bnode); |
| 181 |
bnode = NULL; |
| 182 |
break; |
| 183 |
} |
| 184 |
if (bnode->height != height) |
| 185 |
goto invalid; |
| 186 |
if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) |
| 187 |
goto invalid; |
| 188 |
bnode->parent = parent; |
| 189 |
|
| 190 |
res = __hfs_brec_find(bnode, fd, do_key_compare); |
| 191 |
if (!height) |
| 192 |
break; |
| 193 |
if (fd->record < 0) |
| 194 |
goto release; |
| 195 |
|
| 196 |
parent = nidx; |
| 197 |
hfs_bnode_read(bnode, &data, fd->entryoffset, 4); |
| 198 |
nidx = be32_to_cpu(data); |
| 199 |
hfs_bnode_put(bnode); |
| 200 |
} |
| 201 |
fd->bnode = bnode; |
| 202 |
return res; |
| 203 |
|
| 204 |
invalid: |
| 205 |
pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", |
| 206 |
height, bnode->height, bnode->type, nidx, parent); |
| 207 |
res = -EIO; |
| 208 |
release: |
| 209 |
hfs_bnode_put(bnode); |
| 210 |
return res; |
| 211 |
} |
| 212 |
|
| 213 |
int hfs_brec_read(struct hfs_find_data *fd, void *rec, u32 rec_len) |
| 214 |
{ |
| 215 |
int res; |
| 216 |
|
| 217 |
res = hfs_brec_find(fd, hfs_find_rec_by_key); |
| 218 |
if (res) |
| 219 |
return res; |
| 220 |
if (fd->entrylength > rec_len) |
| 221 |
return -EINVAL; |
| 222 |
hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); |
| 223 |
return 0; |
| 224 |
} |
| 225 |
|
| 226 |
int hfs_brec_goto(struct hfs_find_data *fd, int cnt) |
| 227 |
{ |
| 228 |
struct hfs_btree *tree; |
| 229 |
struct hfs_bnode *bnode; |
| 230 |
int idx, res = 0; |
| 231 |
u16 off, len, keylen; |
| 232 |
|
| 233 |
bnode = fd->bnode; |
| 234 |
tree = bnode->tree; |
| 235 |
|
| 236 |
if (cnt < 0) { |
| 237 |
cnt = -cnt; |
| 238 |
while (cnt > fd->record) { |
| 239 |
cnt -= fd->record + 1; |
| 240 |
fd->record = bnode->num_recs - 1; |
| 241 |
idx = bnode->prev; |
| 242 |
if (!idx) { |
| 243 |
res = -ENOENT; |
| 244 |
goto out; |
| 245 |
} |
| 246 |
hfs_bnode_put(bnode); |
| 247 |
bnode = hfs_bnode_find(tree, idx); |
| 248 |
if (IS_ERR(bnode)) { |
| 249 |
res = PTR_ERR(bnode); |
| 250 |
bnode = NULL; |
| 251 |
goto out; |
| 252 |
} |
| 253 |
} |
| 254 |
fd->record -= cnt; |
| 255 |
} else { |
| 256 |
while (cnt >= bnode->num_recs - fd->record) { |
| 257 |
cnt -= bnode->num_recs - fd->record; |
| 258 |
fd->record = 0; |
| 259 |
idx = bnode->next; |
| 260 |
if (!idx) { |
| 261 |
res = -ENOENT; |
| 262 |
goto out; |
| 263 |
} |
| 264 |
hfs_bnode_put(bnode); |
| 265 |
bnode = hfs_bnode_find(tree, idx); |
| 266 |
if (IS_ERR(bnode)) { |
| 267 |
res = PTR_ERR(bnode); |
| 268 |
bnode = NULL; |
| 269 |
goto out; |
| 270 |
} |
| 271 |
} |
| 272 |
fd->record += cnt; |
| 273 |
} |
| 274 |
|
| 275 |
len = hfs_brec_lenoff(bnode, fd->record, &off); |
| 276 |
keylen = hfs_brec_keylen(bnode, fd->record); |
| 277 |
if (keylen == 0) { |
| 278 |
res = -EINVAL; |
| 279 |
goto out; |
| 280 |
} |
| 281 |
fd->keyoffset = off; |
| 282 |
fd->keylength = keylen; |
| 283 |
fd->entryoffset = off + keylen; |
| 284 |
fd->entrylength = len - keylen; |
| 285 |
hfs_bnode_read(bnode, fd->key, off, keylen); |
| 286 |
out: |
| 287 |
fd->bnode = bnode; |
| 288 |
return res; |
| 289 |
} |
| 290 |
|
| 291 |
/** |
| 292 |
* hfsplus_brec_read_cat - read and validate a catalog record |
| 293 |
* @fd: find data structure |
| 294 |
* @entry: pointer to catalog entry to read into |
| 295 |
* |
| 296 |
* Reads a catalog record and validates its size matches the expected |
| 297 |
* size based on the record type. |
| 298 |
* |
| 299 |
* Returns 0 on success, or negative error code on failure. |
| 300 |
*/ |
| 301 |
int hfsplus_brec_read_cat(struct hfs_find_data *fd, hfsplus_cat_entry *entry) |
| 302 |
{ |
| 303 |
int res; |
| 304 |
u32 expected_size; |
| 305 |
|
| 306 |
res = hfs_brec_read(fd, entry, sizeof(hfsplus_cat_entry)); |
| 307 |
if (res) |
| 308 |
return res; |
| 309 |
|
| 310 |
/* Validate catalog record size based on type */ |
| 311 |
switch (be16_to_cpu(entry->type)) { |
| 312 |
case HFSPLUS_FOLDER: |
| 313 |
expected_size = sizeof(struct hfsplus_cat_folder); |
| 314 |
break; |
| 315 |
case HFSPLUS_FILE: |
| 316 |
expected_size = sizeof(struct hfsplus_cat_file); |
| 317 |
break; |
| 318 |
case HFSPLUS_FOLDER_THREAD: |
| 319 |
case HFSPLUS_FILE_THREAD: |
| 320 |
/* Ensure we have at least the fixed fields before reading nodeName.length */ |
| 321 |
if (fd->entrylength < HFSPLUS_MIN_THREAD_SZ) { |
| 322 |
pr_err("thread record too short (got %u)\n", fd->entrylength); |
| 323 |
return -EIO; |
| 324 |
} |
| 325 |
expected_size = hfsplus_cat_thread_size(&entry->thread); |
| 326 |
break; |
| 327 |
default: |
| 328 |
pr_err("unknown catalog record type %d\n", |
| 329 |
be16_to_cpu(entry->type)); |
| 330 |
return -EIO; |
| 331 |
} |
| 332 |
|
| 333 |
if (fd->entrylength != expected_size) { |
| 334 |
pr_err("catalog record size mismatch (type %d, got %u, expected %u)\n", |
| 335 |
be16_to_cpu(entry->type), fd->entrylength, expected_size); |
| 336 |
return -EIO; |
| 337 |
} |
| 338 |
|
| 339 |
return 0; |
| 340 |
} |