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(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 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(BNODE_REFS, "find_exit: %d (%p)\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 tree = fd->tree; 162 if (fd->bnode) 163 hfs_bnode_put(fd->bnode); 164 fd->bnode = NULL; 165 nidx = tree->root; 166 if (!nidx) 167 return -ENOENT; 168 height = tree->depth; 169 res = 0; 170 parent = 0; 171 for (;;) { 172 bnode = hfs_bnode_find(tree, nidx); 173 if (IS_ERR(bnode)) { 174 res = PTR_ERR(bnode); 175 bnode = NULL; 176 break; 177 } 178 if (bnode->height != height) 179 goto invalid; 180 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 181 goto invalid; 182 bnode->parent = parent; 183 184 res = __hfs_brec_find(bnode, fd, do_key_compare); 185 if (!height) 186 break; 187 if (fd->record < 0) 188 goto release; 189 190 parent = nidx; 191 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 192 nidx = be32_to_cpu(data); 193 hfs_bnode_put(bnode); 194 } 195 fd->bnode = bnode; 196 return res; 197 198 invalid: 199 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 200 height, bnode->height, bnode->type, nidx, parent); 201 res = -EIO; 202 release: 203 hfs_bnode_put(bnode); 204 return res; 205 } 206 207 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) 208 { 209 int res; 210 211 res = hfs_brec_find(fd, hfs_find_rec_by_key); 212 if (res) 213 return res; 214 if (fd->entrylength > rec_len) 215 return -EINVAL; 216 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 217 return 0; 218 } 219 220 int hfs_brec_goto(struct hfs_find_data *fd, int cnt) 221 { 222 struct hfs_btree *tree; 223 struct hfs_bnode *bnode; 224 int idx, res = 0; 225 u16 off, len, keylen; 226 227 bnode = fd->bnode; 228 tree = bnode->tree; 229 230 if (cnt < 0) { 231 cnt = -cnt; 232 while (cnt > fd->record) { 233 cnt -= fd->record + 1; 234 fd->record = bnode->num_recs - 1; 235 idx = bnode->prev; 236 if (!idx) { 237 res = -ENOENT; 238 goto out; 239 } 240 hfs_bnode_put(bnode); 241 bnode = hfs_bnode_find(tree, idx); 242 if (IS_ERR(bnode)) { 243 res = PTR_ERR(bnode); 244 bnode = NULL; 245 goto out; 246 } 247 } 248 fd->record -= cnt; 249 } else { 250 while (cnt >= bnode->num_recs - fd->record) { 251 cnt -= bnode->num_recs - fd->record; 252 fd->record = 0; 253 idx = bnode->next; 254 if (!idx) { 255 res = -ENOENT; 256 goto out; 257 } 258 hfs_bnode_put(bnode); 259 bnode = hfs_bnode_find(tree, idx); 260 if (IS_ERR(bnode)) { 261 res = PTR_ERR(bnode); 262 bnode = NULL; 263 goto out; 264 } 265 } 266 fd->record += cnt; 267 } 268 269 len = hfs_brec_lenoff(bnode, fd->record, &off); 270 keylen = hfs_brec_keylen(bnode, fd->record); 271 if (keylen == 0) { 272 res = -EINVAL; 273 goto out; 274 } 275 fd->keyoffset = off; 276 fd->keylength = keylen; 277 fd->entryoffset = off + keylen; 278 fd->entrylength = len - keylen; 279 hfs_bnode_read(bnode, fd->key, off, keylen); 280 out: 281 fd->bnode = bnode; 282 return res; 283 } 284