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 switch (tree->cnid) { 29 case HFSPLUS_CAT_CNID: 30 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); 31 break; 32 case HFSPLUS_EXT_CNID: 33 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); 34 break; 35 case HFSPLUS_ATTR_CNID: 36 mutex_lock_nested(&tree->tree_lock, 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(fd->bnode); 47 kfree(fd->search_key); 48 hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n", 49 fd->tree->cnid, __builtin_return_address(0)); 50 mutex_unlock(&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(bnode, rec, &off); 129 keylen = hfs_brec_keylen(bnode, rec); 130 if (keylen == 0) { 131 res = -EINVAL; 132 goto fail; 133 } 134 hfs_bnode_read(bnode, fd->key, off, 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(bnode, e, &off); 143 keylen = hfs_brec_keylen(bnode, e); 144 if (keylen == 0) { 145 res = -EINVAL; 146 goto fail; 147 } 148 hfs_bnode_read(bnode, fd->key, off, 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(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, nidx); 184 if (IS_ERR(bnode)) { 185 res = PTR_ERR(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, do_key_compare); 196 if (!height) 197 break; 198 if (fd->record < 0) 199 goto release; 200 201 parent = nidx; 202 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 203 nidx = be32_to_cpu(data); 204 hfs_bnode_put(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(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, hfs_find_rec_by_key); 223 if (res) 224 return res; 225 if (fd->entrylength > rec_len) 226 return -EINVAL; 227 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, 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(bnode); 252 bnode = hfs_bnode_find(tree, idx); 253 if (IS_ERR(bnode)) { 254 res = PTR_ERR(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(bnode); 270 bnode = hfs_bnode_find(tree, idx); 271 if (IS_ERR(bnode)) { 272 res = PTR_ERR(bnode); 273 bnode = NULL; 274 goto out; 275 } 276 } 277 fd->record += cnt; 278 } 279 280 len = hfs_brec_lenoff(bnode, fd->record, &off); 281 keylen = hfs_brec_keylen(bnode, 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(bnode, fd->key, off, keylen); 291 out: 292 fd->bnode = bnode; 293 return res; 294 } 295