File: /usr/src/linux/fs/hfs/binsert.c
1 /*
2 * linux/fs/hfs/binsert.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 insert records in a B-tree.
8 *
9 * "XXX" in a comment is a note to myself to consider changing something.
10 *
11 * In function preconditions the term "valid" applied to a pointer to
12 * a structure means that the pointer is non-NULL and the structure it
13 * points to has all fields initialized to consistent values.
14 */
15
16 #include "hfs_btree.h"
17
18 /*================ File-local functions ================*/
19
20 /* btree locking functions */
21 static inline void hfs_btree_lock(struct hfs_btree *tree)
22 {
23 while (tree->lock)
24 hfs_sleep_on(&tree->wait);
25 tree->lock = 1;
26 }
27
28 static inline void hfs_btree_unlock(struct hfs_btree *tree)
29 {
30 tree->lock = 0;
31 hfs_wake_up(&tree->wait);
32 }
33
34 /*
35 * binsert_nonfull()
36 *
37 * Description:
38 * Inserts a record in a given bnode known to have sufficient space.
39 * Input Variable(s):
40 * struct hfs_brec* brec: pointer to the brec for the insertion
41 * struct hfs_belem* belem: the element in the search path to insert in
42 * struct hfs_bkey* key: pointer to the key for the record to insert
43 * void* data: pointer to the record to insert
44 * hfs_u16 keysize: size of the key to insert
45 * hfs_u16 datasize: size of the record to insert
46 * Output Variable(s):
47 * NONE
48 * Returns:
49 * NONE
50 * Preconditions:
51 * 'brec' points to a valid (struct hfs_brec).
52 * 'belem' points to a valid (struct hfs_belem) in 'brec', the node
53 * of which has enough free space to insert 'key' and 'data'.
54 * 'key' is a pointer to a valid (struct hfs_bkey) of length 'keysize'
55 * which, in sorted order, belongs at the location indicated by 'brec'.
56 * 'data' is non-NULL an points to appropriate data of length 'datasize'
57 * Postconditions:
58 * The record has been inserted in the position indicated by 'brec'.
59 */
60 static void binsert_nonfull(struct hfs_brec *brec, struct hfs_belem *belem,
61 const struct hfs_bkey *key, const void *data,
62 hfs_u8 keysize, hfs_u16 datasize)
63 {
64 int i, rec, nrecs, size, tomove;
65 hfs_u8 *start;
66 struct hfs_bnode *bnode = belem->bnr.bn;
67
68 rec = ++(belem->record);
69 size = ROUND(keysize+1) + datasize;
70 nrecs = bnode->ndNRecs + 1;
71 tomove = bnode_offset(bnode, nrecs) - bnode_offset(bnode, rec);
72
73 /* adjust the record table */
74 for (i = nrecs; i >= rec; --i) {
75 hfs_put_hs(bnode_offset(bnode,i) + size, RECTBL(bnode,i+1));
76 }
77
78 /* make room */
79 start = bnode_key(bnode, rec);
80 memmove(start + size, start, tomove);
81
82 /* copy in the key and the data*/
83 *start = keysize;
84 keysize = ROUND(keysize+1);
85 memcpy(start + 1, (hfs_u8 *)key + 1, keysize-1);
86 memcpy(start + keysize, data, datasize);
87
88 /* update record count */
89 ++bnode->ndNRecs;
90 }
91
92 /*
93 * add_root()
94 *
95 * Description:
96 * Adds a new root to a B*-tree, increasing its height.
97 * Input Variable(s):
98 * struct hfs_btree *tree: the tree to add a new root to
99 * struct hfs_bnode *left: the new root's first child or NULL
100 * struct hfs_bnode *right: the new root's second child or NULL
101 * Output Variable(s):
102 * NONE
103 * Returns:
104 * void
105 * Preconditions:
106 * 'tree' points to a valid (struct hfs_btree).
107 * 'left' and 'right' point to valid (struct hfs_bnode)s, which
108 * resulted from splitting the old root node, or are both NULL
109 * if there was no root node before.
110 * Postconditions:
111 * Upon success a new root node is added to 'tree' with either
112 * two children ('left' and 'right') or none.
113 */
114 static void add_root(struct hfs_btree *tree,
115 struct hfs_bnode *left,
116 struct hfs_bnode *right)
117 {
118 struct hfs_bnode_ref bnr;
119 struct hfs_bnode *root;
120 struct hfs_bkey *key;
121 int keylen = tree->bthKeyLen;
122
123 if (left && !right) {
124 hfs_warn("add_root: LEFT but no RIGHT\n");
125 return;
126 }
127
128 bnr = hfs_bnode_alloc(tree);
129 if (!(root = bnr.bn)) {
130 return;
131 }
132
133 root->sticky = HFS_STICKY;
134 tree->root = root;
135 tree->bthRoot = root->node;
136 ++tree->bthDepth;
137
138 root->ndNHeight = tree->bthDepth;
139 root->ndFLink = 0;
140 root->ndBLink = 0;
141
142 if (!left) {
143 /* tree was empty */
144 root->ndType = ndLeafNode;
145 root->ndNRecs = 0;
146
147 tree->bthFNode = root->node;
148 tree->bthLNode = root->node;
149 } else {
150 root->ndType = ndIndxNode;
151 root->ndNRecs = 2;
152
153 hfs_put_hs(sizeof(struct NodeDescriptor) + ROUND(1+keylen) +
154 sizeof(hfs_u32), RECTBL(root, 2));
155 key = bnode_key(root, 1);
156 key->KeyLen = keylen;
157 memcpy(key->value,
158 ((struct hfs_bkey *)bnode_key(left, 1))->value, keylen);
159 hfs_put_hl(left->node, bkey_record(key));
160
161 hfs_put_hs(sizeof(struct NodeDescriptor) + 2*ROUND(1+keylen) +
162 2*sizeof(hfs_u32), RECTBL(root, 3));
163 key = bnode_key(root, 2);
164 key->KeyLen = keylen;
165 memcpy(key->value,
166 ((struct hfs_bkey *)bnode_key(right, 1))->value, keylen);
167 hfs_put_hl(right->node, bkey_record(key));
168
169 /* the former root (left) is now just a normal node */
170 left->sticky = HFS_NOT_STICKY;
171 if ((left->next = bhash(tree, left->node))) {
172 left->next->prev = left;
173 }
174 bhash(tree, left->node) = left;
175 }
176 hfs_bnode_relse(&bnr);
177 tree->dirt = 1;
178 }
179
180 /*
181 * insert_empty_bnode()
182 *
183 * Description:
184 * Adds an empty node to the right of 'left'.
185 * Input Variable(s):
186 * struct hfs_btree *tree: the tree to add a node to
187 * struct hfs_bnode *left: the node to add a node after
188 * Output Variable(s):
189 * NONE
190 * Returns:
191 * struct hfs_bnode_ref *: reference to the new bnode.
192 * Preconditions:
193 * 'tree' points to a valid (struct hfs_btree) with at least 1 free node.
194 * 'left' points to a valid (struct hfs_bnode) belonging to 'tree'.
195 * Postconditions:
196 * If NULL is returned then 'tree' and 'left' are unchanged.
197 * Otherwise a node with 0 records is inserted in the tree to the right
198 * of the node 'left'. The 'ndFLink' of 'left' and the 'ndBLink' of
199 * the former right-neighbor of 'left' (if one existed) point to the
200 * new node. If 'left' had no right neighbor and is a leaf node the
201 * the 'bthLNode' of 'tree' points to the new node. The free-count and
202 * bitmap for 'tree' are kept current by hfs_bnode_alloc() which supplies
203 * the required node.
204 */
205 static struct hfs_bnode_ref insert_empty_bnode(struct hfs_btree *tree,
206 struct hfs_bnode *left)
207 {
208 struct hfs_bnode_ref retval;
209 struct hfs_bnode_ref right;
210
211 retval = hfs_bnode_alloc(tree);
212 if (!retval.bn) {
213 hfs_warn("hfs_binsert: out of bnodes?.\n");
214 goto done;
215 }
216 retval.bn->sticky = HFS_NOT_STICKY;
217 if ((retval.bn->next = bhash(tree, retval.bn->node))) {
218 retval.bn->next->prev = retval.bn;
219 }
220 bhash(tree, retval.bn->node) = retval.bn;
221
222 if (left->ndFLink) {
223 right = hfs_bnode_find(tree, left->ndFLink, HFS_LOCK_WRITE);
224 if (!right.bn) {
225 hfs_warn("hfs_binsert: corrupt btree.\n");
226 hfs_bnode_bitop(tree, retval.bn->node, 0);
227 hfs_bnode_relse(&retval);
228 goto done;
229 }
230 right.bn->ndBLink = retval.bn->node;
231 hfs_bnode_relse(&right);
232 } else if (left->ndType == ndLeafNode) {
233 tree->bthLNode = retval.bn->node;
234 tree->dirt = 1;
235 }
236
237 retval.bn->ndFLink = left->ndFLink;
238 retval.bn->ndBLink = left->node;
239 retval.bn->ndType = left->ndType;
240 retval.bn->ndNHeight = left->ndNHeight;
241 retval.bn->ndNRecs = 0;
242
243 left->ndFLink = retval.bn->node;
244
245 done:
246 return retval;
247 }
248
249 /*
250 * split()
251 *
252 * Description:
253 * Splits an over full node during insertion.
254 * Picks the split point that results in the most-nearly equal
255 * space usage in the new and old nodes.
256 * Input Variable(s):
257 * struct hfs_belem *elem: the over full node.
258 * int size: the number of bytes to be used by the new record and its key.
259 * Output Variable(s):
260 * struct hfs_belem *elem: changed to indicate where the new record
261 * should be inserted.
262 * Returns:
263 * struct hfs_bnode_ref: reference to the new bnode.
264 * Preconditions:
265 * 'elem' points to a valid path element corresponding to the over full node.
266 * 'size' is positive.
267 * Postconditions:
268 * The records in the node corresponding to 'elem' are redistributed across
269 * the old and new nodes so that after inserting the new record, the space
270 * usage in these two nodes is as equal as possible.
271 * 'elem' is updated so that a call to binsert_nonfull() will insert the
272 * new record in the correct location.
273 */
274 static inline struct hfs_bnode_ref split(struct hfs_belem *elem, int size)
275 {
276 struct hfs_bnode *bnode = elem->bnr.bn;
277 int nrecs, cutoff, index, tmp, used, in_right;
278 struct hfs_bnode_ref right;
279
280 right = insert_empty_bnode(bnode->tree, bnode);
281 if (right.bn) {
282 nrecs = bnode->ndNRecs;
283 cutoff = (size + bnode_end(bnode) -
284 sizeof(struct NodeDescriptor) +
285 (nrecs+1)*sizeof(hfs_u16))/2;
286 used = 0;
287 in_right = 1;
288 /* note that this only works because records sizes are even */
289 for (index=1; index <= elem->record; ++index) {
290 tmp = (sizeof(hfs_u16) + bnode_rsize(bnode, index))/2;
291 used += tmp;
292 if (used > cutoff) {
293 goto found;
294 }
295 used += tmp;
296 }
297 tmp = (size + sizeof(hfs_u16))/2;
298 used += tmp;
299 if (used > cutoff) {
300 goto found;
301 }
302 in_right = 0;
303 used += tmp;
304 for (; index <= nrecs; ++index) {
305 tmp = (sizeof(hfs_u16) + bnode_rsize(bnode, index))/2;
306 used += tmp;
307 if (used > cutoff) {
308 goto found;
309 }
310 used += tmp;
311 }
312 /* couldn't find the split point! */
313 hfs_bnode_relse(&right);
314 }
315 return right;
316
317 found:
318 if (in_right) {
319 elem->bnr = right;
320 elem->record -= index-1;
321 }
322 hfs_bnode_shift_right(bnode, right.bn, index);
323
324 return right;
325 }
326
327 /*
328 * binsert()
329 *
330 * Description:
331 * Inserts a record in a tree known to have enough room, even if the
332 * insertion requires the splitting of nodes.
333 * Input Variable(s):
334 * struct hfs_brec *brec: partial path to the node to insert in
335 * const struct hfs_bkey *key: key for the new record
336 * const void *data: data for the new record
337 * hfs_u8 keysize: size of the key
338 * hfs_u16 datasize: size of the data
339 * int reserve: number of nodes reserved in case of splits
340 * Output Variable(s):
341 * *brec = NULL
342 * Returns:
343 * int: 0 on success, error code on failure
344 * Preconditions:
345 * 'brec' points to a valid (struct hfs_brec) corresponding to a
346 * record in a leaf node, after which a record is to be inserted,
347 * or to "record 0" of the leaf node if the record is to be inserted
348 * before all existing records in the node. The (struct hfs_brec)
349 * includes all ancestors of the leaf node that are needed to
350 * complete the insertion including the parents of any nodes that
351 * will be split.
352 * 'key' points to a valid (struct hfs_bkey) which is appropriate
353 * to this tree, and which belongs at the insertion point.
354 * 'data' points data appropriate for the indicated node.
355 * 'keysize' gives the size in bytes of the key.
356 * 'datasize' gives the size in bytes of the data.
357 * 'reserve' gives the number of nodes that have been reserved in the
358 * tree to allow for splitting of nodes.
359 * Postconditions:
360 * All 'reserve'd nodes have been either used or released.
361 * *brec = NULL
362 * On success the key and data have been inserted at the indicated
363 * location in the tree, all appropriate fields of the in-core data
364 * structures have been changed and updated versions of the on-disk
365 * data structures have been scheduled for write-back to disk.
366 * On failure the B*-tree is probably invalid both on disk and in-core.
367 *
368 * XXX: Some attempt at repair might be made in the event of failure,
369 * or the fs should be remounted read-only so things don't get worse.
370 */
371 static int binsert(struct hfs_brec *brec, const struct hfs_bkey *key,
372 const void *data, hfs_u8 keysize, hfs_u16 datasize,
373 int reserve)
374 {
375 struct hfs_bnode_ref left, right, other;
376 struct hfs_btree *tree = brec->tree;
377 struct hfs_belem *belem = brec->bottom;
378 int tmpsize = 1 + tree->bthKeyLen;
379 struct hfs_bkey *tmpkey = hfs_malloc(tmpsize);
380 hfs_u32 node;
381
382 while ((belem >= brec->top) && (belem->flags & HFS_BPATH_OVERFLOW)) {
383 left = belem->bnr;
384 if (left.bn->ndFLink &&
385 hfs_bnode_in_brec(left.bn->ndFLink, brec)) {
386 hfs_warn("hfs_binsert: corrupt btree\n");
387 tree->reserved -= reserve;
388 hfs_free(tmpkey, tmpsize);
389 return -EIO;
390 }
391
392 right = split(belem, ROUND(keysize+1) + ROUND(datasize));
393 --reserve;
394 --tree->reserved;
395 if (!right.bn) {
396 hfs_warn("hfs_binsert: unable to split node!\n");
397 tree->reserved -= reserve;
398 hfs_free(tmpkey, tmpsize);
399 return -ENOSPC;
400 }
401 binsert_nonfull(brec, belem, key, data, keysize, datasize);
402
403 if (belem->bnr.bn == left.bn) {
404 other = right;
405 if (belem->record == 1) {
406 hfs_bnode_update_key(brec, belem, left.bn, 0);
407 }
408 } else {
409 other = left;
410 }
411
412 if (left.bn->node == tree->root->node) {
413 add_root(tree, left.bn, right.bn);
414 hfs_bnode_relse(&other);
415 goto done;
416 }
417
418 data = &node;
419 datasize = sizeof(node);
420 node = htonl(right.bn->node);
421 key = tmpkey;
422 keysize = tree->bthKeyLen;
423 memcpy(tmpkey, bnode_key(right.bn, 1), keysize+1);
424 hfs_bnode_relse(&other);
425
426 --belem;
427 }
428
429 if (belem < brec->top) {
430 hfs_warn("hfs_binsert: Missing parent.\n");
431 tree->reserved -= reserve;
432 hfs_free(tmpkey, tmpsize);
433 return -EIO;
434 }
435
436 binsert_nonfull(brec, belem, key, data, keysize, datasize);
437
438 done:
439 tree->reserved -= reserve;
440 hfs_free(tmpkey, tmpsize);
441 return 0;
442 }
443
444 /*================ Global functions ================*/
445
446 /*
447 * hfs_binsert()
448 *
449 * Description:
450 * This function inserts a new record into a b-tree.
451 * Input Variable(s):
452 * struct hfs_btree *tree: pointer to the (struct hfs_btree) to insert in
453 * struct hfs_bkey *key: pointer to the (struct hfs_bkey) to insert
454 * void *data: pointer to the data to associate with 'key' in the b-tree
455 * unsigned int datasize: the size of the data
456 * Output Variable(s):
457 * NONE
458 * Returns:
459 * int: 0 on success, error code on failure
460 * Preconditions:
461 * 'tree' points to a valid (struct hfs_btree)
462 * 'key' points to a valid (struct hfs_bkey)
463 * 'data' points to valid memory of length 'datasize'
464 * Postconditions:
465 * If zero is returned then the record has been inserted in the
466 * indicated location updating all in-core data structures and
467 * scheduling all on-disk data structures for write-back.
468 */
469 int hfs_binsert(struct hfs_btree *tree, const struct hfs_bkey *key,
470 const void *data, hfs_u16 datasize)
471 {
472 struct hfs_brec brec;
473 struct hfs_belem *belem;
474 int err, reserve, retval;
475 hfs_u8 keysize;
476
477 if (!tree || (tree->magic != HFS_BTREE_MAGIC) || !key || !data) {
478 hfs_warn("hfs_binsert: invalid arguments.\n");
479 return -EINVAL;
480 }
481
482 if (key->KeyLen > tree->bthKeyLen) {
483 hfs_warn("hfs_binsert: oversized key\n");
484 return -EINVAL;
485 }
486
487 restart:
488 if (!tree->bthNRecs) {
489 /* create the root bnode */
490 add_root(tree, NULL, NULL);
491 if (!hfs_brec_init(&brec, tree, HFS_BFIND_INSERT)) {
492 hfs_warn("hfs_binsert: failed to create root.\n");
493 return -ENOSPC;
494 }
495 } else {
496 err = hfs_bfind(&brec, tree, key, HFS_BFIND_INSERT);
497 if (err < 0) {
498 hfs_warn("hfs_binsert: hfs_brec_find failed.\n");
499 return err;
500 } else if (err == 0) {
501 hfs_brec_relse(&brec, NULL);
502 return -EEXIST;
503 }
504 }
505
506 keysize = key->KeyLen;
507 datasize = ROUND(datasize);
508 belem = brec.bottom;
509 belem->flags = 0;
510 if (bnode_freespace(belem->bnr.bn) <
511 (sizeof(hfs_u16) + ROUND(keysize+1) + datasize)) {
512 belem->flags |= HFS_BPATH_OVERFLOW;
513 }
514 if (belem->record == 0) {
515 belem->flags |= HFS_BPATH_FIRST;
516 }
517
518 if (!belem->flags) {
519 hfs_brec_lock(&brec, brec.bottom);
520 reserve = 0;
521 } else {
522 reserve = brec.bottom - brec.top;
523 if (brec.top == 0) {
524 ++reserve;
525 }
526 /* make certain we have enough nodes to proceed */
527 if ((tree->bthFree - tree->reserved) < reserve) {
528 hfs_brec_relse(&brec, NULL);
529 hfs_btree_lock(tree);
530 if ((tree->bthFree - tree->reserved) < reserve) {
531 hfs_btree_extend(tree);
532 }
533 hfs_btree_unlock(tree);
534 if ((tree->bthFree - tree->reserved) < reserve) {
535 return -ENOSPC;
536 } else {
537 goto restart;
538 }
539 }
540 tree->reserved += reserve;
541 hfs_brec_lock(&brec, NULL);
542 }
543
544 retval = binsert(&brec, key, data, keysize, datasize, reserve);
545 hfs_brec_relse(&brec, NULL);
546 if (!retval) {
547 ++tree->bthNRecs;
548 tree->dirt = 1;
549 }
550 return retval;
551 }
552