File: /usr/src/linux/fs/hfs/btree.c
1 /*
2 * linux/fs/hfs/btree.c
3 *
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
6 *
7 * This file contains the code to manipulate the B-tree structure.
8 * The catalog and extents files are both B-trees.
9 *
10 * "XXX" in a comment is a note to myself to consider changing something.
11 *
12 * In function preconditions the term "valid" applied to a pointer to
13 * a structure means that the pointer is non-NULL and the structure it
14 * points to has all fields initialized to consistent values.
15 *
16 * The code in this file initializes some structures which contain
17 * pointers by calling memset(&foo, 0, sizeof(foo)).
18 * This produces the desired behavior only due to the non-ANSI
19 * assumption that the machine representation of NULL is all zeros.
20 */
21
22 #include "hfs_btree.h"
23
24 /*================ File-local functions ================*/
25
26 /*
27 * hfs_bnode_ditch()
28 *
29 * Description:
30 * This function deletes an entire linked list of bnodes, so it
31 * does not need to keep the linked list consistent as
32 * hfs_bnode_delete() does.
33 * Called by hfs_btree_init() for error cleanup and by hfs_btree_free().
34 * Input Variable(s):
35 * struct hfs_bnode *bn: pointer to the first (struct hfs_bnode) in
36 * the linked list to be deleted.
37 * Output Variable(s):
38 * NONE
39 * Returns:
40 * void
41 * Preconditions:
42 * 'bn' is NULL or points to a "valid" (struct hfs_bnode) with a 'prev'
43 * field of NULL.
44 * Postconditions:
45 * 'bn' and all (struct hfs_bnode)s in the chain of 'next' pointers
46 * are deleted, freeing the associated memory and hfs_buffer_put()ing
47 * the associated buffer.
48 */
49 static void hfs_bnode_ditch(struct hfs_bnode *bn) {
50 struct hfs_bnode *tmp;
51 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
52 extern int bnode_count;
53 #endif
54
55 while (bn != NULL) {
56 tmp = bn->next;
57 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
58 hfs_warn("deleting node %d from tree %d with count %d\n",
59 bn->node, (int)ntohl(bn->tree->entry.cnid), bn->count);
60 --bnode_count;
61 #endif
62 hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
63
64 /* free all but the header */
65 if (bn->node) {
66 HFS_DELETE(bn);
67 }
68 bn = tmp;
69 }
70 }
71
72 /*================ Global functions ================*/
73
74 /*
75 * hfs_btree_free()
76 *
77 * Description:
78 * This function frees a (struct hfs_btree) obtained from hfs_btree_init().
79 * Called by hfs_put_super().
80 * Input Variable(s):
81 * struct hfs_btree *bt: pointer to the (struct hfs_btree) to free
82 * Output Variable(s):
83 * NONE
84 * Returns:
85 * void
86 * Preconditions:
87 * 'bt' is NULL or points to a "valid" (struct hfs_btree)
88 * Postconditions:
89 * If 'bt' points to a "valid" (struct hfs_btree) then all (struct
90 * hfs_bnode)s associated with 'bt' are freed by calling
91 * hfs_bnode_ditch() and the memory associated with the (struct
92 * hfs_btree) is freed.
93 * If 'bt' is NULL or not "valid" an error is printed and nothing
94 * is changed.
95 */
96 void hfs_btree_free(struct hfs_btree *bt)
97 {
98 int lcv;
99
100 if (bt && (bt->magic == HFS_BTREE_MAGIC)) {
101 hfs_extent_free(&bt->entry.u.file.data_fork);
102
103 for (lcv=0; lcv<HFS_CACHELEN; ++lcv) {
104 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
105 hfs_warn("deleting nodes from bucket %d:\n", lcv);
106 #endif
107 hfs_bnode_ditch(bt->cache[lcv]);
108 }
109
110 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
111 hfs_warn("deleting header and bitmap nodes\n");
112 #endif
113 hfs_bnode_ditch(&bt->head);
114
115 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
116 hfs_warn("deleting root node\n");
117 #endif
118 hfs_bnode_ditch(bt->root);
119
120 HFS_DELETE(bt);
121 } else if (bt) {
122 hfs_warn("hfs_btree_free: corrupted hfs_btree.\n");
123 }
124 }
125
126 /*
127 * hfs_btree_init()
128 *
129 * Description:
130 * Given some vital information from the MDB (HFS superblock),
131 * initializes the fields of a (struct hfs_btree).
132 * Input Variable(s):
133 * struct hfs_mdb *mdb: pointer to the MDB
134 * ino_t cnid: the CNID (HFS_CAT_CNID or HFS_EXT_CNID) of the B-tree
135 * hfs_u32 tsize: the size, in bytes, of the B-tree
136 * hfs_u32 csize: the size, in bytes, of the clump size for the B-tree
137 * Output Variable(s):
138 * NONE
139 * Returns:
140 * (struct hfs_btree *): pointer to the initialized hfs_btree on success,
141 * or NULL on failure
142 * Preconditions:
143 * 'mdb' points to a "valid" (struct hfs_mdb)
144 * Postconditions:
145 * Assuming the inputs are what they claim to be, no errors occur
146 * reading from disk, and no inconsistencies are noticed in the data
147 * read from disk, the return value is a pointer to a "valid"
148 * (struct hfs_btree). If there are errors reading from disk or
149 * inconsistencies are noticed in the data read from disk, then and
150 * all resources that were allocated are released and NULL is
151 * returned. If the inputs are not what they claim to be or if they
152 * are unnoticed inconsistencies in the data read from disk then the
153 * returned hfs_btree is probably going to lead to errors when it is
154 * used in a non-trivial way.
155 */
156 struct hfs_btree * hfs_btree_init(struct hfs_mdb *mdb, ino_t cnid,
157 hfs_byte_t ext[12],
158 hfs_u32 tsize, hfs_u32 csize)
159 {
160 struct hfs_btree * bt;
161 struct BTHdrRec * th;
162 struct hfs_bnode * tmp;
163 unsigned int next;
164 #if defined(DEBUG_HEADER) || defined(DEBUG_ALL)
165 unsigned char *p, *q;
166 #endif
167
168 if (!mdb || !ext || !HFS_NEW(bt)) {
169 goto bail3;
170 }
171
172 bt->magic = HFS_BTREE_MAGIC;
173 bt->sys_mdb = mdb->sys_mdb;
174 bt->reserved = 0;
175 bt->lock = 0;
176 hfs_init_waitqueue(&bt->wait);
177 bt->dirt = 0;
178 memset(bt->cache, 0, sizeof(bt->cache));
179
180 #if 0 /* this is a fake entry. so we don't need to initialize it. */
181 memset(&bt->entry, 0, sizeof(bt->entry));
182 hfs_init_waitqueue(&bt->entry.wait);
183 INIT_LIST_HEAD(&bt->entry.hash);
184 INIT_LIST_HEAD(&bt->entry.list);
185 #endif
186
187 bt->entry.mdb = mdb;
188 bt->entry.cnid = cnid;
189 bt->entry.type = HFS_CDR_FIL;
190 bt->entry.u.file.magic = HFS_FILE_MAGIC;
191 bt->entry.u.file.clumpablks = (csize / mdb->alloc_blksz)
192 >> HFS_SECTOR_SIZE_BITS;
193 bt->entry.u.file.data_fork.entry = &bt->entry;
194 bt->entry.u.file.data_fork.lsize = tsize;
195 bt->entry.u.file.data_fork.psize = tsize >> HFS_SECTOR_SIZE_BITS;
196 bt->entry.u.file.data_fork.fork = HFS_FK_DATA;
197 hfs_extent_in(&bt->entry.u.file.data_fork, ext);
198
199 hfs_bnode_read(&bt->head, bt, 0, HFS_STICKY);
200 if (!hfs_buffer_ok(bt->head.buf)) {
201 goto bail2;
202 }
203 th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) +
204 sizeof(struct NodeDescriptor));
205
206 /* read in the bitmap nodes (if any) */
207 tmp = &bt->head;
208 while ((next = tmp->ndFLink)) {
209 if (!HFS_NEW(tmp->next)) {
210 goto bail2;
211 }
212 hfs_bnode_read(tmp->next, bt, next, HFS_STICKY);
213 if (!hfs_buffer_ok(tmp->next->buf)) {
214 goto bail2;
215 }
216 tmp->next->prev = tmp;
217 tmp = tmp->next;
218 }
219
220 if (hfs_get_ns(th->bthNodeSize) != htons(HFS_SECTOR_SIZE)) {
221 hfs_warn("hfs_btree_init: bthNodeSize!=512 not supported\n");
222 goto bail2;
223 }
224
225 if (cnid == htonl(HFS_CAT_CNID)) {
226 bt->compare = (hfs_cmpfn)hfs_cat_compare;
227 } else if (cnid == htonl(HFS_EXT_CNID)) {
228 bt->compare = (hfs_cmpfn)hfs_ext_compare;
229 } else {
230 goto bail2;
231 }
232 bt->bthDepth = hfs_get_hs(th->bthDepth);
233 bt->bthRoot = hfs_get_hl(th->bthRoot);
234 bt->bthNRecs = hfs_get_hl(th->bthNRecs);
235 bt->bthFNode = hfs_get_hl(th->bthFNode);
236 bt->bthLNode = hfs_get_hl(th->bthLNode);
237 bt->bthNNodes = hfs_get_hl(th->bthNNodes);
238 bt->bthFree = hfs_get_hl(th->bthFree);
239 bt->bthKeyLen = hfs_get_hs(th->bthKeyLen);
240
241 #if defined(DEBUG_HEADER) || defined(DEBUG_ALL)
242 hfs_warn("bthDepth %d\n", bt->bthDepth);
243 hfs_warn("bthRoot %d\n", bt->bthRoot);
244 hfs_warn("bthNRecs %d\n", bt->bthNRecs);
245 hfs_warn("bthFNode %d\n", bt->bthFNode);
246 hfs_warn("bthLNode %d\n", bt->bthLNode);
247 hfs_warn("bthKeyLen %d\n", bt->bthKeyLen);
248 hfs_warn("bthNNodes %d\n", bt->bthNNodes);
249 hfs_warn("bthFree %d\n", bt->bthFree);
250 p = (unsigned char *)hfs_buffer_data(bt->head.buf);
251 q = p + HFS_SECTOR_SIZE;
252 while (p < q) {
253 hfs_warn("%02x %02x %02x %02x %02x %02x %02x %02x "
254 "%02x %02x %02x %02x %02x %02x %02x %02x\n",
255 *p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++,
256 *p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++);
257 }
258 #endif
259
260 /* Read in the root if it exists.
261 The header always exists, but the root exists only if the
262 tree is non-empty */
263 if (bt->bthDepth && bt->bthRoot) {
264 if (!HFS_NEW(bt->root)) {
265 goto bail2;
266 }
267 hfs_bnode_read(bt->root, bt, bt->bthRoot, HFS_STICKY);
268 if (!hfs_buffer_ok(bt->root->buf)) {
269 goto bail1;
270 }
271 } else {
272 bt->root = NULL;
273 }
274
275 return bt;
276
277 bail1:
278 hfs_bnode_ditch(bt->root);
279 bail2:
280 hfs_bnode_ditch(&bt->head);
281 HFS_DELETE(bt);
282 bail3:
283 return NULL;
284 }
285
286 /*
287 * hfs_btree_commit()
288 *
289 * Called to write a possibly dirty btree back to disk.
290 */
291 void hfs_btree_commit(struct hfs_btree *bt, hfs_byte_t ext[12], hfs_lword_t size)
292 {
293 if (bt->dirt) {
294 struct BTHdrRec *th;
295 th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) +
296 sizeof(struct NodeDescriptor));
297
298 hfs_put_hs(bt->bthDepth, th->bthDepth);
299 hfs_put_hl(bt->bthRoot, th->bthRoot);
300 hfs_put_hl(bt->bthNRecs, th->bthNRecs);
301 hfs_put_hl(bt->bthFNode, th->bthFNode);
302 hfs_put_hl(bt->bthLNode, th->bthLNode);
303 hfs_put_hl(bt->bthNNodes, th->bthNNodes);
304 hfs_put_hl(bt->bthFree, th->bthFree);
305 hfs_buffer_dirty(bt->head.buf);
306
307 /*
308 * Commit the bnodes which are not cached.
309 * The map nodes don't need to be committed here because
310 * they are committed every time they are changed.
311 */
312 hfs_bnode_commit(&bt->head);
313 if (bt->root) {
314 hfs_bnode_commit(bt->root);
315 }
316
317
318 hfs_put_hl(bt->bthNNodes << HFS_SECTOR_SIZE_BITS, size);
319 hfs_extent_out(&bt->entry.u.file.data_fork, ext);
320 /* hfs_buffer_dirty(mdb->buf); (Done by caller) */
321
322 bt->dirt = 0;
323 }
324 }
325