fs/hfs/bnode.c

   1 /*
   2  * linux/fs/hfs/bnode.c
   3  *
   4  * Copyright (C) 1995-1997  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU Public License.
   6  *
   7  * This file contains the code to access nodes in the B-tree structure.
   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  * The code in this file initializes some structures which contain
  16  * pointers by calling memset(&foo, 0, sizeof(foo)).
  17  * This produces the desired behavior only due to the non-ANSI
  18  * assumption that the machine representation of NULL is all zeros.
  19  */
  20
  21 #include "hfs_btree.h"
  22
  23 /*================ File-local variables ================*/
  24
  25 /* debugging statistics */
  26 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  27 int bnode_count = 0;
  28 #endif
  29
  30 /*================ Global functions ================*/
  31
  32 /*
  33  * hfs_bnode_delete()
  34  *
  35  * Description:
  36  *   This function is called to remove a bnode from the cache and
  37  *   release its resources.
  38  * Input Variable(s):
  39  *   struct hfs_bnode *bn: Pointer to the (struct hfs_bnode) to be
  40  *   removed from the cache.
  41  * Output Variable(s):
  42  *   NONE
  43  * Returns:
  44  *   void
  45  * Preconditions:
  46  *   'bn' points to a "valid" (struct hfs_bnode).
  47  * Postconditions:
  48  *   The node 'bn' is removed from the cache, its memory freed and its
  49  *   buffer (if any) released.
  50  */
  51 void hfs_bnode_delete(struct hfs_bnode *bn)
  52 {
  53 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  54         --bnode_count;
  55 #endif
  56         /* join neighbors */
  57         if (bn->next) {
  58                 bn->next->prev = bn->prev;
  59         }
  60         if (bn->prev) {
  61                 bn->prev->next = bn->next;
  62         }
  63         /* fix cache slot if necessary */
  64         if (bhash(bn->tree, bn->node) == bn) {
  65                 bhash(bn->tree, bn->node) = bn->next;
  66         }
  67         /* release resources */
  68         hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
  69         HFS_DELETE(bn);
  70 }
  71
  72
  73 /*
  74  * hfs_bnode_read()
  75  *
  76  * Description:
  77  *   This function creates a (struct hfs_bnode) and, if appropriate,
  78  *   inserts it in the cache.
  79  * Input Variable(s):
  80  *   struct hfs_bnode *bnode: pointer to the new bnode.
  81  *   struct hfs_btree *tree: pointer to the (struct hfs_btree)
  82  *    containing the desired node
  83  *   hfs_u32 node: the number of the desired node.
  84  *   int sticky: the value to assign to the 'sticky' field.
  85  * Output Variable(s):
  86  *   NONE
  87  * Returns:
  88  *   (struct hfs_bnode *) pointing to the newly created bnode or NULL.
  89  * Preconditions:
  90  *   'bnode' points to a "valid" (struct hfs_bnode).
  91  *   'tree' points to a "valid" (struct hfs_btree).
  92  *   'node' is an existing node number in the B-tree.
  93  * Postconditions:
  94  *   The following are true of 'bnode' upon return:
  95  *    The 'magic' field is set to indicate a valid (struct hfs_bnode).
  96  *    The 'sticky', 'tree' and 'node' fields are initialized to the
  97  *    values of the of the corresponding arguments.
  98  *    If the 'sticky' argument is zero then the fields 'prev' and
  99  *    'next' are initialized by inserting the (struct hfs_bnode) in the
 100  *    linked list of the appropriate cache slot; otherwise they are
 101  *    initialized to NULL.
 102  *    The data is read from disk (or buffer cache) and the 'buf' field
 103  *    points to the buffer for that data.
 104  *    If no other processes tried to access this node while this
 105  *    process was waiting on disk I/O (if necessary) then the
 106  *    remaining fields are zero ('count', 'resrv', 'lock') or NULL
 107  *    ('wqueue', 'rqueue') corresponding to no accesses.
 108  *    If there were access attempts during I/O then they were blocked
 109  *    until the I/O was complete, and the fields 'count', 'resrv',
 110  *    'lock', 'wqueue' and 'rqueue' reflect the results of unblocking
 111  *    those processes when the I/O was completed.
 112  */
 113 void hfs_bnode_read(struct hfs_bnode *bnode, struct hfs_btree *tree,
 114                     hfs_u32 node, int sticky)
 115 {
 116         struct NodeDescriptor *nd;
 117         int block, lcv;
 118         hfs_u16 curr, prev, limit;
 119
 120         /* Initialize the structure */
 121         memset(bnode, 0, sizeof(*bnode));
 122         bnode->magic = HFS_BNODE_MAGIC;
 123         bnode->tree = tree;
 124         bnode->node = node;
 125         bnode->sticky = sticky;
 126
 127         if (sticky == HFS_NOT_STICKY) {
 128                 /* Insert it in the cache if appropriate */
 129                 if ((bnode->next = bhash(tree, node))) {
 130                         bnode->next->prev = bnode;
 131                 }
 132                 bhash(tree, node) = bnode;
 133         }
 134
 135         /* Make the bnode look like it is being
 136            modified so other processes will wait for
 137            the I/O to complete */
 138         bnode->count = bnode->resrv = bnode->lock = 1;
 139
 140         /* Read in the node, possibly causing a schedule()
 141            call.  If the I/O fails then emit a warning.  Each
 142            process that was waiting on the bnode (including
 143            the current one) will notice the failure and
 144            hfs_bnode_relse() the node.  The last hfs_bnode_relse()
 145            will call hfs_bnode_delete() and discard the bnode.  */
 146
 147         block = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
 148         if (!block) {
 149                 hfs_warn("hfs_bnode_read: bad node number 0x%08x\n", node);
 150         } else if (hfs_buffer_ok(bnode->buf =
 151                                  hfs_buffer_get(tree->sys_mdb, block, 1))) {
 152                 /* read in the NodeDescriptor */
 153                 nd = (struct NodeDescriptor *)hfs_buffer_data(bnode->buf);
 154                 bnode->ndFLink    = hfs_get_hl(nd->ndFLink);
 155                 bnode->ndBLink    = hfs_get_hl(nd->ndBLink);
 156                 bnode->ndType     = nd->ndType;
 157                 bnode->ndNHeight  = nd->ndNHeight;
 158                 bnode->ndNRecs    = hfs_get_hs(nd->ndNRecs);
 159
 160                 /* verify the integrity of the node */
 161                 prev = sizeof(struct NodeDescriptor);
 162                 limit = HFS_SECTOR_SIZE - sizeof(hfs_u16)*(bnode->ndNRecs + 1);
 163                 for (lcv=1; lcv <= (bnode->ndNRecs + 1); ++lcv) {
 164                         curr = hfs_get_hs(RECTBL(bnode, lcv));
 165                         if ((curr < prev) || (curr > limit)) {
 166                                 hfs_warn("hfs_bnode_read: corrupt node "
 167                                          "number 0x%08x\n", node);
 168                                 hfs_buffer_put(bnode->buf);
 169                                 bnode->buf = NULL;
 170                                 break;
 171                         }
 172                         prev = curr;
 173                 }
 174         }
 175
 176         /* Undo our fakery with the lock state and
 177            hfs_wake_up() anyone who we managed to trick */
 178         --bnode->count;
 179         bnode->resrv = bnode->lock = 0;
 180         hfs_wake_up(&bnode->rqueue);
 181 }
 182
 183 /*
 184  * hfs_bnode_lock()
 185  *
 186  * Description:
 187  *   This function does the locking of a bnode.
 188  * Input Variable(s):
 189  *   struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to lock
 190  *   int lock_type: the type of lock desired
 191  * Output Variable(s):
 192  *   NONE
 193  * Returns:
 194  *   void
 195  * Preconditions:
 196  *   'bn' points to a "valid" (struct hfs_bnode).
 197  *   'lock_type' is a valid hfs_lock_t
 198  * Postconditions:
 199  *   The 'count' field of 'bn' is incremented by one.  If 'lock_type'
 200  *   is HFS_LOCK_RESRV the 'resrv' field is also incremented.
 201  */
 202 void hfs_bnode_lock(struct hfs_bnode_ref *bnr, int lock_type)
 203 {
 204         struct hfs_bnode *bn = bnr->bn;
 205
 206         if ((lock_type == bnr->lock_type) || !bn) {
 207                 return;
 208         }
 209
 210         if (bnr->lock_type == HFS_LOCK_WRITE) {
 211                 hfs_bnode_commit(bnr->bn);
 212         }
 213
 214         switch (lock_type) {
 215         default:
 216                 goto bail;
 217                 break;
 218
 219         case HFS_LOCK_READ:
 220                 /* We may not obtain read access if any process is
 221                    currently modifying or waiting to modify this node.
 222                    If we can't obtain access we wait on the rqueue
 223                    wait queue to be woken up by the modifying process
 224                    when it relinquishes its lock. */
 225                 switch (bnr->lock_type) {
 226                 default:
 227                         goto bail;
 228                         break;
 229
 230                 case HFS_LOCK_NONE:
 231                         while (bn->lock || bn->wqueue) {
 232                                 hfs_sleep_on(&bn->rqueue);
 233                         }
 234                         ++bn->count;
 235                         break;
 236                 }
 237                 break;
 238
 239         case HFS_LOCK_RESRV:
 240                 /* We may not obtain a reservation (read access with
 241                    an option to write later), if any process currently
 242                    holds a reservation on this node.  That includes
 243                    any process which is currently modifying this node.
 244                    If we can't obtain access, then we wait on the
 245                    rqueue wait queue to e woken up by the
 246                    reservation-holder when it calls hfs_bnode_relse. */
 247                 switch (bnr->lock_type) {
 248                 default:
 249                         goto bail;
 250                         break;
 251
 252                 case HFS_LOCK_NONE:
 253                         while (bn->resrv) {
 254                                 hfs_sleep_on(&bn->rqueue);
 255                         }
 256                         bn->resrv = 1;
 257                         ++bn->count;
 258                         break;
 259
 260                 case HFS_LOCK_WRITE:
 261                         bn->lock = 0;
 262                         hfs_wake_up(&bn->rqueue);
 263                         break;
 264                 }
 265                 break;
 266
 267         case HFS_LOCK_WRITE:
 268                 switch (bnr->lock_type) {
 269                 default:
 270                         goto bail;
 271                         break;
 272
 273                 case HFS_LOCK_NONE:
 274                         while (bn->resrv) {
 275                                 hfs_sleep_on(&bn->rqueue);
 276                         }
 277                         bn->resrv = 1;
 278                         ++bn->count;
 279                 case HFS_LOCK_RESRV:
 280                         while (bn->count > 1) {
 281                                 hfs_sleep_on(&bn->wqueue);
 282                         }
 283                         bn->lock = 1;
 284                         break;
 285                 }
 286                 break;
 287
 288         case HFS_LOCK_NONE:
 289                 switch (bnr->lock_type) {
 290                 default:
 291                         goto bail;
 292                         break;
 293
 294                 case HFS_LOCK_READ:
 295                         /* This process was reading this node.  If
 296                            there is now exactly one other process using
 297                            the node then hfs_wake_up() a (potentially
 298                            nonexistent) waiting process.  Note that I
 299                            refer to "a" process since the reservation
 300                            system ensures that only one process can
 301                            get itself on the wait queue.  */
 302                         if (bn->count == 2) {
 303                                 hfs_wake_up(&bn->wqueue);
 304                         }
 305                         break;
 306
 307                 case HFS_LOCK_WRITE:
 308                         /* This process was modifying this node.
 309                            Unlock the node and fall-through to the
 310                            HFS_LOCK_RESRV case, since a 'reservation'
 311                            is a prerequisite for HFS_LOCK_WRITE.  */
 312                         bn->lock = 0;
 313                 case HFS_LOCK_RESRV:
 314                         /* This process had placed a 'reservation' on
 315                            this node, indicating an intention to
 316                            possibly modify the node.  We can get to
 317                            this spot directly (if the 'reservation'
 318                            not converted to a HFS_LOCK_WRITE), or by
 319                            falling through from the above case if the
 320                            reservation was converted.
 321                            Since HFS_LOCK_RESRV and HFS_LOCK_WRITE
 322                            both block processes that want access
 323                            (HFS_LOCK_RESRV blocks other processes that
 324                            want reservations but allow HFS_LOCK_READ
 325                            accesses, while HFS_LOCK_WRITE must have
 326                            exclusive access and thus blocks both
 327                            types) we hfs_wake_up() any processes that
 328                            might be waiting for access.  If multiple
 329                            processes are waiting for a reservation
 330                            then the magic of process scheduling will
 331                            settle the dispute. */
 332                         bn->resrv = 0;
 333                         hfs_wake_up(&bn->rqueue);
 334                         break;
 335                 }
 336                 --bn->count;
 337                 break;
 338         }
 339         bnr->lock_type = lock_type;
 340         return;
 341
 342 bail:
 343         hfs_warn("hfs_bnode_lock: invalid lock change: %d->%d.\n",
 344                 bnr->lock_type, lock_type);
 345         return;
 346 }
 347
 348 /*
 349  * hfs_bnode_relse()
 350  *
 351  * Description:
 352  *   This function is called when a process is done using a bnode.  If
 353  *   the proper conditions are met then we call hfs_bnode_delete() to remove
 354  *   it from the cache.  If it is not deleted then we update its state
 355  *   to reflect one less process using it.
 356  * Input Variable(s):
 357  *   struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to release.
 358  *   int lock_type: The type of lock held by the process releasing this node.
 359  * Output Variable(s):
 360  *   NONE
 361  * Returns:
 362  *   void
 363  * Preconditions:
 364  *   'bn' is NULL or points to a "valid" (struct hfs_bnode).
 365  * Postconditions:
 366  *   If 'bn' meets the appropriate conditions (see below) then it is
 367  *   kept in the cache and all fields are set to consistent values
 368  *   which reflect one less process using the node than upon entry.
 369  *   If 'bn' does not meet the conditions then it is deleted (see
 370  *   hfs_bnode_delete() for postconditions).
 371  *   In either case, if 'lock_type' is HFS_LOCK_WRITE
 372  *   then the corresponding buffer is dirtied.
 373  */
 374 void hfs_bnode_relse(struct hfs_bnode_ref *bnr)
 375 {
 376         struct hfs_bnode *bn;
 377
 378         if (!bnr || !(bn = bnr->bn)) {
 379                 return;
 380         }
 381
 382         /* We update the lock state of the node if it is still in use
 383            or if it is "sticky" (such as the B-tree head and root).
 384            Otherwise we just delete it.  */
 385         if ((bn->count > 1) || (bn->rqueue) || (bn->sticky != HFS_NOT_STICKY)) {
 386                 hfs_bnode_lock(bnr, HFS_LOCK_NONE);
 387         } else {
 388                 /* dirty buffer if we (might) have modified it */
 389                 if (bnr->lock_type == HFS_LOCK_WRITE) {
 390                         hfs_bnode_commit(bn);
 391                 }
 392                 hfs_bnode_delete(bn);
 393                 bnr->lock_type = HFS_LOCK_NONE;
 394         }
 395         bnr->bn = NULL;
 396 }
 397
 398 /*
 399  * hfs_bnode_find()
 400  *
 401  * Description:
 402  *   This function is called to obtain a bnode.  The cache is
 403  *   searched for the node.  If it not found there it is added to
 404  *   the cache by hfs_bnode_read().  There are two special cases node=0
 405  *   (the header node) and node='tree'->bthRoot (the root node), in
 406  *   which the nodes are obtained from fields of 'tree' without
 407  *   consulting or modifying the cache.
 408  * Input Variable(s):
 409  *   struct hfs_tree *tree: pointer to the (struct hfs_btree) from
 410  *    which to get a node.
 411  *   int node: the node number to get from 'tree'.
 412  *   int lock_type: The kind of access (HFS_LOCK_READ, or
 413  *    HFS_LOCK_RESRV) to obtain to the node
 414  * Output Variable(s):
 415  *   NONE
 416  * Returns:
 417  *   (struct hfs_bnode_ref) Reference to the requested node.
 418  * Preconditions:
 419  *   'tree' points to a "valid" (struct hfs_btree).
 420  * Postconditions:
 421  *   If 'node' refers to a valid node in 'tree' and 'lock_type' has
 422  *   one of the values listed above and no I/O errors occur then the
 423  *   value returned refers to a valid (struct hfs_bnode) corresponding
 424  *   to the requested node with the requested access type.  The node
 425  *   is also added to the cache if not previously present and not the
 426  *   root or header.
 427  *   If the conditions given above are not met, the bnode in the
 428  *   returned reference is NULL.
 429  */
 430 struct hfs_bnode_ref hfs_bnode_find(struct hfs_btree *tree,
 431                                     hfs_u32 node, int lock_type)
 432 {
 433         struct hfs_bnode *bn;
 434         struct hfs_bnode *empty = NULL;
 435         struct hfs_bnode_ref bnr;
 436
 437         bnr.lock_type = HFS_LOCK_NONE;
 438         bnr.bn = NULL;
 439
 440 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 441         hfs_warn("hfs_bnode_find: %c %d:%d\n",
 442                  lock_type==HFS_LOCK_READ?'R':
 443                         (lock_type==HFS_LOCK_RESRV?'V':'W'),
 444                  (int)ntohl(tree->entry.cnid), node);
 445 #endif
 446
 447         /* check special cases */
 448         if (!node) {
 449                 bn = &tree->head;
 450                 goto return_it;
 451         } else if (node == tree->bthRoot) {
 452                 bn = tree->root;
 453                 goto return_it;
 454         }
 455
 456 restart:
 457         /* look for the node in the cache. */
 458         bn = bhash(tree, node);
 459         while (bn && (bn->magic == HFS_BNODE_MAGIC)) {
 460                 if (bn->node == node) {
 461                         goto found_it;
 462                 }
 463                 bn = bn->next;
 464         }
 465
 466         if (!empty) {
 467 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 468                 ++bnode_count;
 469 #endif
 470                 if (HFS_NEW(empty)) {
 471                         goto restart;
 472                 }
 473                 return bnr;
 474         }
 475         bn = empty;
 476         hfs_bnode_read(bn, tree, node, HFS_NOT_STICKY);
 477         goto return_it;
 478
 479 found_it:
 480         /* check validity */
 481         if (bn->magic != HFS_BNODE_MAGIC) {
 482                 /* If we find a corrupt bnode then we return
 483                    NULL.  However, we don't try to remove it
 484                    from the cache or release its resources
 485                    since we have no idea what kind of trouble
 486                    we could get into that way. */
 487                 hfs_warn("hfs_bnode_find: bnode cache is corrupt.\n");
 488                 return bnr;
 489         }
 490         if (empty) {
 491 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 492                 --bnode_count;
 493 #endif
 494                 HFS_DELETE(empty);
 495         }
 496
 497 return_it:
 498         /* Wait our turn */
 499         bnr.bn = bn;
 500         hfs_bnode_lock(&bnr, lock_type);
 501
 502         /* Check for failure to read the node from disk */
 503         if (!hfs_buffer_ok(bn->buf)) {
 504                 hfs_bnode_relse(&bnr);
 505         }
 506
 507 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
 508         if (!bnr.bn) {
 509                 hfs_warn("hfs_bnode_find: failed\n");
 510         } else {
 511                 hfs_warn("hfs_bnode_find: use %d(%d) lvl %d [%d]\n", bn->count,
 512                          bn->buf->b_count, bn->ndNHeight, bnode_count);
 513                 hfs_warn("hfs_bnode_find: blnk %u flnk %u recs %u\n",
 514                          bn->ndBLink, bn->ndFLink, bn->ndNRecs);
 515         }
 516 #endif
 517
 518         return bnr;
 519 }
 520
 521 /*
 522  * hfs_bnode_commit()
 523  *
 524  * Called to write a possibly dirty bnode back to disk.
 525  */
 526 void hfs_bnode_commit(struct hfs_bnode *bn)
 527 {
 528         if (hfs_buffer_ok(bn->buf)) {
 529                 struct NodeDescriptor *nd;
 530                 nd = (struct NodeDescriptor *)hfs_buffer_data(bn->buf);
 531
 532                 hfs_put_hl(bn->ndFLink, nd->ndFLink);
 533                 hfs_put_hl(bn->ndBLink, nd->ndBLink);
 534                 nd->ndType    = bn->ndType;
 535                 nd->ndNHeight = bn->ndNHeight;
 536                 hfs_put_hs(bn->ndNRecs, nd->ndNRecs);
 537                 hfs_buffer_dirty(bn->buf);
 538
 539                 /* increment write count */
 540                 hfs_mdb_dirty(bn->tree->sys_mdb);
 541         }
 542 }