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