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