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 = kzalloc(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("cnid %d, caller %ps\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("cnid %d, caller %ps\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 fd->record = -1; 119 fd->keyoffset = -1; 120 fd->keylength = -1; 121 fd->entryoffset = -1; 122 fd->entrylength = -1; 123 124 tree = fd->tree; 125 if (fd->bnode) 126 hfs_bnode_put(fd->bnode); 127 fd->bnode = NULL; 128 nidx = tree->root; 129 if (!nidx) 130 return -ENOENT; 131 height = tree->depth; 132 res = 0; 133 parent = 0; 134 for (;;) { 135 bnode = hfs_bnode_find(tree, nidx); 136 if (IS_ERR(bnode)) { 137 res = PTR_ERR(bnode); 138 bnode = NULL; 139 break; 140 } 141 if (bnode->height != height) 142 goto invalid; 143 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 144 goto invalid; 145 bnode->parent = parent; 146 147 res = __hfs_brec_find(bnode, fd); 148 if (!height) 149 break; 150 if (fd->record < 0) 151 goto release; 152 153 parent = nidx; 154 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 155 nidx = be32_to_cpu(data); 156 hfs_bnode_put(bnode); 157 } 158 fd->bnode = bnode; 159 return res; 160 161 invalid: 162 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 163 height, bnode->height, bnode->type, nidx, parent); 164 res = -EIO; 165 release: 166 hfs_bnode_put(bnode); 167 return res; 168 } 169 170 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) 171 { 172 int res; 173 174 res = hfs_brec_find(fd); 175 if (res) 176 return res; 177 if (fd->entrylength > rec_len) 178 return -EINVAL; 179 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 180 return 0; 181 } 182 183 int hfs_brec_goto(struct hfs_find_data *fd, int cnt) 184 { 185 struct hfs_btree *tree; 186 struct hfs_bnode *bnode; 187 int idx, res = 0; 188 u16 off, len, keylen; 189 190 bnode = fd->bnode; 191 tree = bnode->tree; 192 193 if (cnt < 0) { 194 cnt = -cnt; 195 while (cnt > fd->record) { 196 cnt -= fd->record + 1; 197 fd->record = bnode->num_recs - 1; 198 idx = bnode->prev; 199 if (!idx) { 200 res = -ENOENT; 201 goto out; 202 } 203 hfs_bnode_put(bnode); 204 bnode = hfs_bnode_find(tree, idx); 205 if (IS_ERR(bnode)) { 206 res = PTR_ERR(bnode); 207 bnode = NULL; 208 goto out; 209 } 210 } 211 fd->record -= cnt; 212 } else { 213 while (cnt >= bnode->num_recs - fd->record) { 214 cnt -= bnode->num_recs - fd->record; 215 fd->record = 0; 216 idx = bnode->next; 217 if (!idx) { 218 res = -ENOENT; 219 goto out; 220 } 221 hfs_bnode_put(bnode); 222 bnode = hfs_bnode_find(tree, idx); 223 if (IS_ERR(bnode)) { 224 res = PTR_ERR(bnode); 225 bnode = NULL; 226 goto out; 227 } 228 } 229 fd->record += cnt; 230 } 231 232 len = hfs_brec_lenoff(bnode, fd->record, &off); 233 keylen = hfs_brec_keylen(bnode, fd->record); 234 if (keylen == 0) { 235 res = -EINVAL; 236 goto out; 237 } 238 fd->keyoffset = off; 239 fd->keylength = keylen; 240 fd->entryoffset = off + keylen; 241 fd->entrylength = len - keylen; 242 hfs_bnode_read(bnode, fd->key, off, keylen); 243 out: 244 fd->bnode = bnode; 245 return res; 246 } 247