fs/hfs/bdelete.c

   1 /*
   2  * linux/fs/hfs/bdelete.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 delete 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 /*================ Variable-like macros ================*/
  19
  20 #define FULL (HFS_SECTOR_SIZE - sizeof(struct NodeDescriptor))
  21 #define NO_SPACE (HFS_SECTOR_SIZE+1)
  22
  23 /*================ File-local functions ================*/
  24
  25 /*
  26  * bdelete_nonempty()
  27  *
  28  * Description:
  29  *   Deletes a record from a given bnode without regard to it becoming empty.
  30  * Input Variable(s):
  31  *   struct hfs_brec* brec: pointer to the brec for the deletion
  32  *   struct hfs_belem* belem: which node in 'brec' to delete from
  33  * Output Variable(s):
  34  *   NONE
  35  * Returns:
  36  *   void
  37  * Preconditions:
  38  *   'brec' points to a valid (struct hfs_brec).
  39  *   'belem' points to a valid (struct hfs_belem) in 'brec'.
  40  * Postconditions:
  41  *   The record has been inserted in the position indicated by 'brec'.
  42  */
  43 static void bdelete_nonempty(struct hfs_brec *brec, struct hfs_belem *belem)
  44 {
  45         int i, rec, nrecs, tomove;
  46         hfs_u16 size;
  47         hfs_u8 *start;
  48         struct hfs_bnode *bnode = belem->bnr.bn;
  49
  50         rec = belem->record;
  51         nrecs = bnode->ndNRecs;
  52         size = bnode_rsize(bnode, rec);
  53         tomove = bnode_offset(bnode, nrecs+1) - bnode_offset(bnode, rec+1);
  54
  55         /* adjust the record table */
  56         for (i = rec+1; i <= nrecs; ++i) {
  57                 hfs_put_hs(bnode_offset(bnode,i+1) - size, RECTBL(bnode,i));
  58         }
  59
  60         /* move it down */
  61         start = bnode_key(bnode, rec);
  62         memmove(start, start + size, tomove);
  63
  64         /* update record count */
  65         --bnode->ndNRecs;
  66 }
  67
  68 /*
  69  * del_root()
  70  *
  71  * Description:
  72  *   Delete the current root bnode.
  73  * Input Variable(s):
  74  *   struct hfs_bnode_ref *root: reference to the root bnode
  75  * Output Variable(s):
  76  *   NONE
  77  * Returns:
  78  *   int: 0 on success, error code on failure
  79  * Preconditions:
  80  *   'root' refers to the root bnode with HFS_LOCK_WRITE access.
  81  *   None of 'root's children are held with HFS_LOCK_WRITE access.
  82  * Postconditions:
  83  *   The current 'root' node is removed from the tree and the depth
  84  *    of the tree is reduced by one.
  85  *   If 'root' is an index node with exactly one child, then that
  86  *    child becomes the new root of the tree.
  87  *   If 'root' is an empty leaf node the tree becomes empty.
  88  *   Upon return access to 'root' is relinquished.
  89  */
  90 static int del_root(struct hfs_bnode_ref *root)
  91 {
  92         struct hfs_btree *tree = root->bn->tree;
  93         struct hfs_bnode_ref child;
  94         hfs_u32 node;
  95
  96         if (root->bn->ndNRecs > 1) {
  97                 return 0;
  98         } else if (root->bn->ndNRecs == 0) {
  99                 /* tree is empty */
 100                 tree->bthRoot = 0;
 101                 tree->root = NULL;
 102                 tree->bthRoot = 0;
 103                 tree->bthFNode = 0;
 104                 tree->bthLNode = 0;
 105                 --tree->bthDepth;
 106                 tree->dirt = 1;
 107                 if (tree->bthDepth) {
 108                         hfs_warn("hfs_bdelete: empty tree with bthDepth=%d\n",
 109                                  tree->bthDepth);
 110                         goto bail;
 111                 }
 112                 return hfs_bnode_free(root);
 113         } else if (root->bn->ndType == ndIndxNode) {
 114                 /* tree is non-empty */
 115                 node = hfs_get_hl(bkey_record(bnode_datastart(root->bn)));
 116
 117                 child = hfs_bnode_find(tree, node, HFS_LOCK_READ);
 118                 if (!child.bn) {
 119                         hfs_warn("hfs_bdelete: can't read child node.\n");
 120                         goto bail;
 121                 }
 122
 123                 child.bn->sticky = HFS_STICKY;
 124                 if (child.bn->next) {
 125                         child.bn->next->prev = child.bn->prev;
 126                 }
 127                 if (child.bn->prev) {
 128                         child.bn->prev->next = child.bn->next;
 129                 }
 130                 if (bhash(tree, child.bn->node) == child.bn) {
 131                         bhash(tree, child.bn->node) = child.bn->next;
 132                 }
 133                 child.bn->next = NULL;
 134                 child.bn->prev = NULL;
 135
 136                 tree->bthRoot = child.bn->node;
 137                 tree->root = child.bn;
 138
 139                 /* re-assign bthFNode and bthLNode if the new root is
 140                    a leaf node. */
 141                 if (child.bn->ndType == ndLeafNode) {
 142                         tree->bthFNode = node;
 143                         tree->bthLNode = node;
 144                 }
 145                 hfs_bnode_relse(&child);
 146
 147                 tree->bthRoot = node;
 148                 --tree->bthDepth;
 149                 tree->dirt = 1;
 150                 if (!tree->bthDepth) {
 151                         hfs_warn("hfs_bdelete: non-empty tree with "
 152                                  "bthDepth == 0\n");
 153                         goto bail;
 154                 }
 155                 return hfs_bnode_free(root);    /* marks tree dirty */
 156         }
 157         hfs_bnode_relse(root);
 158         return 0;
 159
 160 bail:
 161         hfs_bnode_relse(root);
 162         return -EIO;
 163 }
 164
 165
 166 /*
 167  * delete_empty_bnode()
 168  *
 169  * Description:
 170  *   Removes an empty non-root bnode from between 'left' and 'right'
 171  * Input Variable(s):
 172  *   hfs_u32 left_node: node number of 'left' or zero if 'left' is invalid
 173  *   struct hfs_bnode_ref *left: reference to the left neighbor of the
 174  *    bnode to remove, or invalid if no such neighbor exists.
 175  *   struct hfs_bnode_ref *center: reference to the bnode to remove
 176  *   hfs_u32 right_node: node number of 'right' or zero if 'right' is invalid
 177  *   struct hfs_bnode_ref *right: reference to the right neighbor of the
 178  *    bnode to remove, or invalid if no such neighbor exists.
 179  * Output Variable(s):
 180  *   NONE
 181  * Returns:
 182  *   void
 183  * Preconditions:
 184  *   'left_node' is as described above.
 185  *   'left' points to a valid (struct hfs_bnode_ref) having HFS_LOCK_WRITE
 186  *    access and referring to the left neighbor of 'center' if such a
 187  *    neighbor exists, or invalid if no such neighbor exists.
 188  *   'center' points to a valid (struct hfs_bnode_ref) having HFS_LOCK_WRITE
 189  *    access and referring to the bnode to delete.
 190  *   'right_node' is as described above.
 191  *   'right' points to a valid (struct hfs_bnode_ref) having HFS_LOCK_WRITE
 192  *    access and referring to the right neighbor of 'center' if such a
 193  *    neighbor exists, or invalid if no such neighbor exists.
 194  * Postconditions:
 195  *   If 'left' is valid its 'ndFLink' field becomes 'right_node'.
 196  *   If 'right' is valid its 'ndBLink' field becomes 'left_node'.
 197  *   If 'center' was the first leaf node then the tree's 'bthFNode'
 198  *    field becomes 'right_node'
 199  *   If 'center' was the last leaf node then the tree's 'bthLNode'
 200  *    field becomes 'left_node'
 201  *   'center' is NOT freed and access to the nodes is NOT relinquished.
 202  */
 203 static void delete_empty_bnode(hfs_u32 left_node, struct hfs_bnode_ref *left,
 204                                struct hfs_bnode_ref *center,
 205                                hfs_u32 right_node, struct hfs_bnode_ref *right)
 206 {
 207         struct hfs_bnode *bnode = center->bn;
 208
 209         if (left_node) {
 210                 left->bn->ndFLink = right_node;
 211         } else if (bnode->ndType == ndLeafNode) {
 212                 bnode->tree->bthFNode = right_node;
 213                 bnode->tree->dirt = 1;
 214         }
 215
 216         if (right_node) {
 217                 right->bn->ndBLink = left_node;
 218         } else if (bnode->ndType == ndLeafNode) {
 219                 bnode->tree->bthLNode = left_node;
 220                 bnode->tree->dirt = 1;
 221         }
 222 }
 223
 224 /*
 225  * balance()
 226  *
 227  * Description:
 228  *   Attempt to equalize space usage in neighboring bnodes.
 229  * Input Variable(s):
 230  *   struct hfs_bnode *left: the left bnode.
 231  *   struct hfs_bnode *right: the right bnode.
 232  * Output Variable(s):
 233  *   NONE
 234  * Returns:
 235  *   void
 236  * Preconditions:
 237  *   'left' and 'right' point to valid (struct hfs_bnode)s obtained
 238  *    with HFS_LOCK_WRITE access, and are neighbors.
 239  * Postconditions:
 240  *   Records are shifted either left or right to make the space usage
 241  *   nearly equal.  When exact equality is not possible the break
 242  *   point is chosen to reduce data movement.
 243  *   The key corresponding to 'right' in its parent is NOT updated.
 244  */
 245 static void balance(struct hfs_bnode *left, struct hfs_bnode *right)
 246 {
 247         int index, left_free, right_free, half;
 248
 249         left_free = bnode_freespace(left);
 250         right_free = bnode_freespace(right);
 251         half = (left_free + right_free)/2;
 252
 253         if (left_free < right_free) {
 254                 /* shift right to balance */
 255                 index = left->ndNRecs + 1;
 256                 while (right_free >= half) {
 257                         --index;
 258                         right_free -= bnode_rsize(left,index)+sizeof(hfs_u16);
 259                 }
 260                 if (index < left->ndNRecs) {
 261 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
 262                         hfs_warn("shifting %d of %d recs right to balance: ",
 263                                left->ndNRecs - index, left->ndNRecs);
 264 #endif
 265                         hfs_bnode_shift_right(left, right, index+1);
 266 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
 267                         hfs_warn("%d,%d\n", left->ndNRecs, right->ndNRecs);
 268 #endif
 269                 }
 270         } else {
 271                 /* shift left to balance */
 272                 index = 0;
 273                 while (left_free >= half) {
 274                         ++index;
 275                         left_free -= bnode_rsize(right,index)+sizeof(hfs_u16);
 276                 }
 277                 if (index > 1) {
 278 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
 279                         hfs_warn("shifting %d of %d recs left to balance: ",
 280                                index-1, right->ndNRecs);
 281 #endif
 282                         hfs_bnode_shift_left(left, right, index-1);
 283 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
 284                         hfs_warn("%d,%d\n", left->ndNRecs, right->ndNRecs);
 285 #endif
 286                 }
 287         }
 288 }
 289
 290 /*
 291  * bdelete()
 292  *
 293  * Delete the given record from a B-tree.
 294  */
 295 static int bdelete(struct hfs_brec *brec)
 296 {
 297         struct hfs_btree *tree = brec->tree;
 298         struct hfs_belem *belem = brec->bottom;
 299         struct hfs_belem *parent = (belem-1);
 300         struct hfs_bnode *bnode;
 301         hfs_u32 left_node, right_node;
 302         struct hfs_bnode_ref left, right;
 303         int left_space, right_space, min_space;
 304         int fix_right_key;
 305         int fix_key;
 306
 307         while ((belem > brec->top) &&
 308                (belem->flags & (HFS_BPATH_UNDERFLOW | HFS_BPATH_FIRST))) {
 309                 bnode = belem->bnr.bn;
 310                 fix_key = belem->flags & HFS_BPATH_FIRST;
 311                 fix_right_key = 0;
 312
 313                 bdelete_nonempty(brec, belem);
 314
 315                 if (bnode->node == tree->root->node) {
 316                         del_root(&belem->bnr);
 317                         --brec->bottom;
 318                         goto done;
 319                 }
 320
 321                 /* check for btree corruption which could lead to deadlock */
 322                 left_node = bnode->ndBLink;
 323                 right_node = bnode->ndFLink;
 324                 if ((left_node && hfs_bnode_in_brec(left_node, brec)) ||
 325                     (right_node && hfs_bnode_in_brec(right_node, brec)) ||
 326                     (left_node == right_node)) {
 327                         hfs_warn("hfs_bdelete: corrupt btree\n");
 328                         hfs_brec_relse(brec, NULL);
 329                         return -EIO;
 330                 }
 331
 332                 /* grab the left neighbor if it exists */
 333                 if (left_node) {
 334                         hfs_bnode_lock(&belem->bnr, HFS_LOCK_RESRV);
 335                         left = hfs_bnode_find(tree,left_node,HFS_LOCK_WRITE);
 336                         if (!left.bn) {
 337                                 hfs_warn("hfs_bdelete: unable to read left "
 338                                          "neighbor.\n");
 339                                 hfs_brec_relse(brec, NULL);
 340                                 return -EIO;
 341                         }
 342                         hfs_bnode_lock(&belem->bnr, HFS_LOCK_WRITE);
 343                         if (parent->record != 1) {
 344                                 left_space = bnode_freespace(left.bn);
 345                         } else {
 346                                 left_space = NO_SPACE;
 347                         }
 348                 } else {
 349                         left.bn = NULL;
 350                         left_space = NO_SPACE;
 351                 }
 352
 353                 /* grab the right neighbor if it exists */
 354                 if (right_node) {
 355                         right = hfs_bnode_find(tree,right_node,HFS_LOCK_WRITE);
 356                         if (!right.bn) {
 357                                 hfs_warn("hfs_bdelete: unable to read right "
 358                                          "neighbor.\n");
 359                                 hfs_bnode_relse(&left);
 360                                 hfs_brec_relse(brec, NULL);
 361                                 return -EIO;
 362                         }
 363                         if (parent->record < parent->bnr.bn->ndNRecs) {
 364                                 right_space = bnode_freespace(right.bn);
 365                         } else {
 366                                 right_space = NO_SPACE;
 367                         }
 368                 } else {
 369                         right.bn = NULL;
 370                         right_space = NO_SPACE;
 371                 }
 372
 373                 if (left_space < right_space) {
 374                         min_space = left_space;
 375                 } else {
 376                         min_space = right_space;
 377                 }
 378
 379                 if (min_space == NO_SPACE) {
 380                         hfs_warn("hfs_bdelete: no siblings?\n");
 381                         hfs_brec_relse(brec, NULL);
 382                         return -EIO;
 383                 }
 384
 385                 if (bnode->ndNRecs == 0) {
 386                         delete_empty_bnode(left_node, &left, &belem->bnr,
 387                                            right_node, &right);
 388                 } else if (min_space + bnode_freespace(bnode) >= FULL) {
 389                         if ((right_space == NO_SPACE) ||
 390                             ((right_space == min_space) &&
 391                              (left_space != NO_SPACE))) {
 392                                 hfs_bnode_shift_left(left.bn, bnode,
 393                                                      bnode->ndNRecs);
 394                         } else {
 395                                 hfs_bnode_shift_right(bnode, right.bn, 1);
 396                                 fix_right_key = 1;
 397                         }
 398                         delete_empty_bnode(left_node, &left, &belem->bnr,
 399                                            right_node, &right);
 400                 } else if (min_space == right_space) {
 401                         balance(bnode, right.bn);
 402                         fix_right_key = 1;
 403                 } else {
 404                         balance(left.bn, bnode);
 405                         fix_key = 1;
 406                 }
 407
 408                 if (fix_right_key) {
 409                         hfs_bnode_update_key(brec, belem, right.bn, 1);
 410                 }
 411
 412                 hfs_bnode_relse(&left);
 413                 hfs_bnode_relse(&right);
 414
 415                 if (bnode->ndNRecs) {
 416                         if (fix_key) {
 417                                 hfs_bnode_update_key(brec, belem, bnode, 0);
 418                         }
 419                         goto done;
 420                 }
 421
 422                 hfs_bnode_free(&belem->bnr);
 423                 --brec->bottom;
 424                 belem = parent;
 425                 --parent;
 426         }
 427
 428         if (belem < brec->top) {
 429                 hfs_warn("hfs_bdelete: Missing parent.\n");
 430                 hfs_brec_relse(brec, NULL);
 431                 return -EIO;
 432         }
 433
 434         bdelete_nonempty(brec, belem);
 435
 436 done:
 437         hfs_brec_relse(brec, NULL);
 438         return 0;
 439 }
 440
 441 /*================ Global functions ================*/
 442
 443 /*
 444  * hfs_bdelete()
 445  *
 446  * Delete the requested record from a B-tree.
 447  */
 448 int hfs_bdelete(struct hfs_btree *tree, const struct hfs_bkey *key)
 449 {
 450         struct hfs_belem *belem;
 451         struct hfs_bnode *bnode;
 452         struct hfs_brec brec;
 453         int retval;
 454
 455         if (!tree || (tree->magic != HFS_BTREE_MAGIC) || !key) {
 456                 hfs_warn("hfs_bdelete: invalid arguments.\n");
 457                 return -EINVAL;
 458         }
 459
 460         retval = hfs_bfind(&brec, tree, key, HFS_BFIND_DELETE);
 461         if (!retval) {
 462                 belem = brec.bottom;
 463                 bnode = belem->bnr.bn;
 464
 465                 belem->flags = 0;
 466                 if ((bnode->ndNRecs * sizeof(hfs_u16) + bnode_end(bnode) -
 467                      bnode_rsize(bnode, belem->record)) < FULL/2) {
 468                         belem->flags |= HFS_BPATH_UNDERFLOW;
 469                 }
 470                 if (belem->record == 1) {
 471                         belem->flags |= HFS_BPATH_FIRST;
 472                 }
 473
 474                 if (!belem->flags) {
 475                         hfs_brec_lock(&brec, brec.bottom);
 476                 } else {
 477                         hfs_brec_lock(&brec, NULL);
 478                 }
 479
 480                 retval = bdelete(&brec);
 481                 if (!retval) {
 482                         --brec.tree->bthNRecs;
 483                         brec.tree->dirt = 1;
 484                 }
 485                 hfs_brec_relse(&brec, NULL);
 486         }
 487         return retval;
 488 }