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