Relax the rw_verify_area() error checking.
[linux-2.6] / fs / hfs / bfind.c
1 /*
2  *  linux/fs/hfs/bfind.c
3  *
4  * Copyright (C) 2001
5  * Brad Boyer (flar@allandria.com)
6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
7  *
8  * Search routines for btrees
9  */
10
11 #include <linux/slab.h>
12 #include "btree.h"
13
14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
15 {
16         void *ptr;
17
18         fd->tree = tree;
19         fd->bnode = NULL;
20         ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
21         if (!ptr)
22                 return -ENOMEM;
23         fd->search_key = ptr;
24         fd->key = ptr + tree->max_key_len + 2;
25         dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0));
26         down(&tree->tree_lock);
27         return 0;
28 }
29
30 void hfs_find_exit(struct hfs_find_data *fd)
31 {
32         hfs_bnode_put(fd->bnode);
33         kfree(fd->search_key);
34         dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0));
35         up(&fd->tree->tree_lock);
36         fd->tree = NULL;
37 }
38
39 /* Find the record in bnode that best matches key (not greater than...)*/
40 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
41 {
42         int cmpval;
43         u16 off, len, keylen;
44         int rec;
45         int b, e;
46         int res;
47
48         b = 0;
49         e = bnode->num_recs - 1;
50         res = -ENOENT;
51         do {
52                 rec = (e + b) / 2;
53                 len = hfs_brec_lenoff(bnode, rec, &off);
54                 keylen = hfs_brec_keylen(bnode, rec);
55                 hfs_bnode_read(bnode, fd->key, off, keylen);
56                 cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
57                 if (!cmpval) {
58                         e = rec;
59                         res = 0;
60                         goto done;
61                 }
62                 if (cmpval < 0)
63                         b = rec + 1;
64                 else
65                         e = rec - 1;
66         } while (b <= e);
67         //printk("%d: %d,%d,%d\n", bnode->this, b, e, rec);
68         if (rec != e && e >= 0) {
69                 len = hfs_brec_lenoff(bnode, e, &off);
70                 keylen = hfs_brec_keylen(bnode, e);
71                 hfs_bnode_read(bnode, fd->key, off, keylen);
72         }
73 done:
74         fd->record = e;
75         fd->keyoffset = off;
76         fd->keylength = keylen;
77         fd->entryoffset = off + keylen;
78         fd->entrylength = len - keylen;
79         return res;
80 }
81
82 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
83 /* Return allocated copy of node found, set recnum to best record */
84 int hfs_brec_find(struct hfs_find_data *fd)
85 {
86         struct hfs_btree *tree;
87         struct hfs_bnode *bnode;
88         u32 nidx, parent;
89         __be32 data;
90         int height, res;
91
92         tree = fd->tree;
93         if (fd->bnode)
94                 hfs_bnode_put(fd->bnode);
95         fd->bnode = NULL;
96         nidx = tree->root;
97         if (!nidx)
98                 return -ENOENT;
99         height = tree->depth;
100         res = 0;
101         parent = 0;
102         for (;;) {
103                 bnode = hfs_bnode_find(tree, nidx);
104                 if (IS_ERR(bnode)) {
105                         res = PTR_ERR(bnode);
106                         bnode = NULL;
107                         break;
108                 }
109                 if (bnode->height != height)
110                         goto invalid;
111                 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
112                         goto invalid;
113                 bnode->parent = parent;
114
115                 res = __hfs_brec_find(bnode, fd);
116                 if (!height)
117                         break;
118                 if (fd->record < 0)
119                         goto release;
120
121                 parent = nidx;
122                 hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
123                 nidx = be32_to_cpu(data);
124                 hfs_bnode_put(bnode);
125         }
126         fd->bnode = bnode;
127         return res;
128
129 invalid:
130         printk("HFS: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
131                 height, bnode->height, bnode->type, nidx, parent);
132         res = -EIO;
133 release:
134         hfs_bnode_put(bnode);
135         return res;
136 }
137
138 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
139 {
140         int res;
141
142         res = hfs_brec_find(fd);
143         if (res)
144                 return res;
145         if (fd->entrylength > rec_len)
146                 return -EINVAL;
147         hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
148         return 0;
149 }
150
151 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
152 {
153         struct hfs_btree *tree;
154         struct hfs_bnode *bnode;
155         int idx, res = 0;
156         u16 off, len, keylen;
157
158         bnode = fd->bnode;
159         tree = bnode->tree;
160
161         if (cnt < 0) {
162                 cnt = -cnt;
163                 while (cnt > fd->record) {
164                         cnt -= fd->record + 1;
165                         fd->record = bnode->num_recs - 1;
166                         idx = bnode->prev;
167                         if (!idx) {
168                                 res = -ENOENT;
169                                 goto out;
170                         }
171                         hfs_bnode_put(bnode);
172                         bnode = hfs_bnode_find(tree, idx);
173                         if (IS_ERR(bnode)) {
174                                 res = PTR_ERR(bnode);
175                                 bnode = NULL;
176                                 goto out;
177                         }
178                 }
179                 fd->record -= cnt;
180         } else {
181                 while (cnt >= bnode->num_recs - fd->record) {
182                         cnt -= bnode->num_recs - fd->record;
183                         fd->record = 0;
184                         idx = bnode->next;
185                         if (!idx) {
186                                 res = -ENOENT;
187                                 goto out;
188                         }
189                         hfs_bnode_put(bnode);
190                         bnode = hfs_bnode_find(tree, idx);
191                         if (IS_ERR(bnode)) {
192                                 res = PTR_ERR(bnode);
193                                 bnode = NULL;
194                                 goto out;
195                         }
196                 }
197                 fd->record += cnt;
198         }
199
200         len = hfs_brec_lenoff(bnode, fd->record, &off);
201         keylen = hfs_brec_keylen(bnode, fd->record);
202         fd->keyoffset = off;
203         fd->keylength = keylen;
204         fd->entryoffset = off + keylen;
205         fd->entrylength = len - keylen;
206         hfs_bnode_read(bnode, fd->key, off, keylen);
207 out:
208         fd->bnode = bnode;
209         return res;
210 }