GNU Linux-libre 5.10.219-gnu1
[releases.git] / fs / hfs / bfind.c
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 }