bnode.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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 General 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         hfs_init_waitqueue(&bnode->rqueue);
  127         hfs_init_waitqueue(&bnode->wqueue);
  128 
  129         if (sticky == HFS_NOT_STICKY) {
  130                 /* Insert it in the cache if appropriate */
  131                 if ((bnode->next = bhash(tree, node))) {
  132                         bnode->next->prev = bnode;
  133                 }
  134                 bhash(tree, node) = bnode;
  135         }
  136 
  137         /* Make the bnode look like it is being
  138            modified so other processes will wait for
  139            the I/O to complete */
  140         bnode->count = bnode->resrv = bnode->lock = 1;
  141 
  142         /* Read in the node, possibly causing a schedule()
  143            call.  If the I/O fails then emit a warning.  Each
  144            process that was waiting on the bnode (including
  145            the current one) will notice the failure and
  146            hfs_bnode_relse() the node.  The last hfs_bnode_relse()
  147            will call hfs_bnode_delete() and discard the bnode.  */
  148 
  149         block = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
  150         if (!block) {
  151                 hfs_warn("hfs_bnode_read: bad node number 0x%08x\n", node);
  152         } else if (hfs_buffer_ok(bnode->buf =
  153                                  hfs_buffer_get(tree->sys_mdb, block, 1))) {
  154                 /* read in the NodeDescriptor */
  155                 nd = (struct NodeDescriptor *)hfs_buffer_data(bnode->buf);
  156                 bnode->ndFLink    = hfs_get_hl(nd->ndFLink);
  157                 bnode->ndBLink    = hfs_get_hl(nd->ndBLink);
  158                 bnode->ndType     = nd->ndType;
  159                 bnode->ndNHeight  = nd->ndNHeight;
  160                 bnode->ndNRecs    = hfs_get_hs(nd->ndNRecs);
  161 
  162                 /* verify the integrity of the node */
  163                 prev = sizeof(struct NodeDescriptor);
  164                 limit = HFS_SECTOR_SIZE - sizeof(hfs_u16)*(bnode->ndNRecs + 1);
  165                 for (lcv=1; lcv <= (bnode->ndNRecs + 1); ++lcv) {
  166                         curr = hfs_get_hs(RECTBL(bnode, lcv));
  167                         if ((curr < prev) || (curr > limit)) {
  168                                 hfs_warn("hfs_bnode_read: corrupt node "
  169                                          "number 0x%08x\n", node);
  170                                 hfs_buffer_put(bnode->buf);
  171                                 bnode->buf = NULL;
  172                                 break;
  173                         }
  174                         prev = curr;
  175                 }
  176         }
  177 
  178         /* Undo our fakery with the lock state and
  179            hfs_wake_up() anyone who we managed to trick */
  180         --bnode->count;
  181         bnode->resrv = bnode->lock = 0;
  182         hfs_wake_up(&bnode->rqueue);
  183 }
  184 
  185 /*
  186  * hfs_bnode_lock()
  187  *
  188  * Description:
  189  *   This function does the locking of a bnode.
  190  * Input Variable(s):
  191  *   struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to lock
  192  *   int lock_type: the type of lock desired
  193  * Output Variable(s):
  194  *   NONE
  195  * Returns:
  196  *   void
  197  * Preconditions:
  198  *   'bn' points to a "valid" (struct hfs_bnode).
  199  *   'lock_type' is a valid hfs_lock_t
  200  * Postconditions:
  201  *   The 'count' field of 'bn' is incremented by one.  If 'lock_type'
  202  *   is HFS_LOCK_RESRV the 'resrv' field is also incremented.
  203  */
  204 void hfs_bnode_lock(struct hfs_bnode_ref *bnr, int lock_type)
  205 {
  206         struct hfs_bnode *bn = bnr->bn;
  207 
  208         if ((lock_type == bnr->lock_type) || !bn) {
  209                 return;
  210         }
  211 
  212         if (bnr->lock_type == HFS_LOCK_WRITE) {
  213                 hfs_bnode_commit(bnr->bn);
  214         }
  215 
  216         switch (lock_type) {
  217         default:
  218                 goto bail;
  219                 break;
  220 
  221         case HFS_LOCK_READ:
  222                 /* We may not obtain read access if any process is
  223                    currently modifying or waiting to modify this node.
  224                    If we can't obtain access we wait on the rqueue
  225                    wait queue to be woken up by the modifying process
  226                    when it relinquishes its lock. */
  227                 switch (bnr->lock_type) {
  228                 default:
  229                         goto bail;
  230                         break;
  231 
  232                 case HFS_LOCK_NONE:
  233                         while (bn->lock || waitqueue_active(&bn->wqueue)) {
  234                                 hfs_sleep_on(&bn->rqueue);
  235                         }
  236                         ++bn->count;
  237                         break;
  238                 }
  239                 break;
  240                         
  241         case HFS_LOCK_RESRV:
  242                 /* We may not obtain a reservation (read access with
  243                    an option to write later), if any process currently
  244                    holds a reservation on this node.  That includes
  245                    any process which is currently modifying this node.
  246                    If we can't obtain access, then we wait on the
  247                    rqueue wait queue to e woken up by the
  248                    reservation-holder when it calls hfs_bnode_relse. */
  249                 switch (bnr->lock_type) {
  250                 default:
  251                         goto bail;
  252                         break;
  253 
  254                 case HFS_LOCK_NONE:
  255                         while (bn->resrv) {
  256                                 hfs_sleep_on(&bn->rqueue);
  257                         }
  258                         bn->resrv = 1;
  259                         ++bn->count;
  260                         break;
  261 
  262                 case HFS_LOCK_WRITE:
  263                         bn->lock = 0;
  264                         hfs_wake_up(&bn->rqueue);
  265                         break;
  266                 }
  267                 break;
  268                 
  269         case HFS_LOCK_WRITE:
  270                 switch (bnr->lock_type) {
  271                 default:
  272                         goto bail;
  273                         break;
  274 
  275                 case HFS_LOCK_NONE:
  276                         while (bn->resrv) {
  277                                 hfs_sleep_on(&bn->rqueue);
  278                         }
  279                         bn->resrv = 1;
  280                         ++bn->count;
  281                 case HFS_LOCK_RESRV:
  282                         while (bn->count > 1) {
  283                                 hfs_sleep_on(&bn->wqueue);
  284                         }
  285                         bn->lock = 1;
  286                         break;
  287                 }
  288                 break;
  289 
  290         case HFS_LOCK_NONE:
  291                 switch (bnr->lock_type) {
  292                 default:
  293                         goto bail;
  294                         break;
  295 
  296                 case HFS_LOCK_READ:
  297                         /* This process was reading this node.  If
  298                            there is now exactly one other process using
  299                            the node then hfs_wake_up() a (potentially
  300                            nonexistent) waiting process.  Note that I
  301                            refer to "a" process since the reservation
  302                            system ensures that only one process can
  303                            get itself on the wait queue.  */
  304                         if (bn->count == 2) {
  305                                 hfs_wake_up(&bn->wqueue);
  306                         }
  307                         break;
  308 
  309                 case HFS_LOCK_WRITE:
  310                         /* This process was modifying this node.
  311                            Unlock the node and fall-through to the
  312                            HFS_LOCK_RESRV case, since a 'reservation'
  313                            is a prerequisite for HFS_LOCK_WRITE.  */
  314                         bn->lock = 0;
  315                 case HFS_LOCK_RESRV:
  316                         /* This process had placed a 'reservation' on
  317                            this node, indicating an intention to
  318                            possibly modify the node.  We can get to
  319                            this spot directly (if the 'reservation'
  320                            not converted to a HFS_LOCK_WRITE), or by
  321                            falling through from the above case if the
  322                            reservation was converted.
  323                            Since HFS_LOCK_RESRV and HFS_LOCK_WRITE
  324                            both block processes that want access
  325                            (HFS_LOCK_RESRV blocks other processes that
  326                            want reservations but allow HFS_LOCK_READ
  327                            accesses, while HFS_LOCK_WRITE must have
  328                            exclusive access and thus blocks both
  329                            types) we hfs_wake_up() any processes that
  330                            might be waiting for access.  If multiple
  331                            processes are waiting for a reservation
  332                            then the magic of process scheduling will
  333                            settle the dispute. */
  334                         bn->resrv = 0;
  335                         hfs_wake_up(&bn->rqueue);
  336                         break;
  337                 }
  338                 --bn->count;
  339                 break;
  340         }
  341         bnr->lock_type = lock_type;
  342         return;
  343 
  344 bail:
  345         hfs_warn("hfs_bnode_lock: invalid lock change: %d->%d.\n",
  346                 bnr->lock_type, lock_type);
  347         return;
  348 }
  349 
  350 /*
  351  * hfs_bnode_relse()
  352  *
  353  * Description:
  354  *   This function is called when a process is done using a bnode.  If
  355  *   the proper conditions are met then we call hfs_bnode_delete() to remove
  356  *   it from the cache.  If it is not deleted then we update its state
  357  *   to reflect one less process using it.
  358  * Input Variable(s):
  359  *   struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to release.
  360  *   int lock_type: The type of lock held by the process releasing this node.
  361  * Output Variable(s):
  362  *   NONE
  363  * Returns:
  364  *   void
  365  * Preconditions:
  366  *   'bn' is NULL or points to a "valid" (struct hfs_bnode).
  367  * Postconditions:
  368  *   If 'bn' meets the appropriate conditions (see below) then it is
  369  *   kept in the cache and all fields are set to consistent values
  370  *   which reflect one less process using the node than upon entry.
  371  *   If 'bn' does not meet the conditions then it is deleted (see
  372  *   hfs_bnode_delete() for postconditions).
  373  *   In either case, if 'lock_type' is HFS_LOCK_WRITE
  374  *   then the corresponding buffer is dirtied.
  375  */
  376 void hfs_bnode_relse(struct hfs_bnode_ref *bnr)
  377 {
  378         struct hfs_bnode *bn;
  379 
  380         if (!bnr || !(bn = bnr->bn)) {
  381                 return;
  382         }
  383 
  384         /* We update the lock state of the node if it is still in use
  385            or if it is "sticky" (such as the B-tree head and root).
  386            Otherwise we just delete it.  */
  387         if ((bn->count > 1) || (waitqueue_active(&bn->rqueue)) || (bn->sticky != HFS_NOT_STICKY)) {
  388                 hfs_bnode_lock(bnr, HFS_LOCK_NONE);
  389         } else {
  390                 /* dirty buffer if we (might) have modified it */
  391                 if (bnr->lock_type == HFS_LOCK_WRITE) {
  392                         hfs_bnode_commit(bn);
  393                 }
  394                 hfs_bnode_delete(bn);
  395                 bnr->lock_type = HFS_LOCK_NONE;
  396         }
  397         bnr->bn = NULL;
  398 }
  399 
  400 /*
  401  * hfs_bnode_find()
  402  *
  403  * Description:
  404  *   This function is called to obtain a bnode.  The cache is
  405  *   searched for the node.  If it not found there it is added to
  406  *   the cache by hfs_bnode_read().  There are two special cases node=0
  407  *   (the header node) and node='tree'->bthRoot (the root node), in
  408  *   which the nodes are obtained from fields of 'tree' without
  409  *   consulting or modifying the cache.
  410  * Input Variable(s):
  411  *   struct hfs_tree *tree: pointer to the (struct hfs_btree) from
  412  *    which to get a node.
  413  *   int node: the node number to get from 'tree'.
  414  *   int lock_type: The kind of access (HFS_LOCK_READ, or
  415  *    HFS_LOCK_RESRV) to obtain to the node
  416  * Output Variable(s):
  417  *   NONE
  418  * Returns:
  419  *   (struct hfs_bnode_ref) Reference to the requested node.
  420  * Preconditions:
  421  *   'tree' points to a "valid" (struct hfs_btree).
  422  * Postconditions:
  423  *   If 'node' refers to a valid node in 'tree' and 'lock_type' has
  424  *   one of the values listed above and no I/O errors occur then the
  425  *   value returned refers to a valid (struct hfs_bnode) corresponding
  426  *   to the requested node with the requested access type.  The node
  427  *   is also added to the cache if not previously present and not the
  428  *   root or header.
  429  *   If the conditions given above are not met, the bnode in the
  430  *   returned reference is NULL.
  431  */
  432 struct hfs_bnode_ref hfs_bnode_find(struct hfs_btree *tree,
  433                                     hfs_u32 node, int lock_type)
  434 {
  435         struct hfs_bnode *bn;
  436         struct hfs_bnode *empty = NULL;
  437         struct hfs_bnode_ref bnr;
  438 
  439         bnr.lock_type = HFS_LOCK_NONE;
  440         bnr.bn = NULL;
  441 
  442 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  443         hfs_warn("hfs_bnode_find: %c %d:%d\n",
  444                  lock_type==HFS_LOCK_READ?'R':
  445                         (lock_type==HFS_LOCK_RESRV?'V':'W'),
  446                  (int)ntohl(tree->entry.cnid), node);
  447 #endif
  448 
  449         /* check special cases */
  450         if (!node) {
  451                 bn = &tree->head;
  452                 goto return_it;
  453         } else if (node == tree->bthRoot) {
  454                 bn = tree->root;
  455                 goto return_it;
  456         } 
  457 
  458 restart:
  459         /* look for the node in the cache. */
  460         bn = bhash(tree, node);
  461         while (bn && (bn->magic == HFS_BNODE_MAGIC)) {
  462                 if (bn->node == node) {
  463                         goto found_it;
  464                 }
  465                 bn = bn->next;
  466         }
  467 
  468         if (!empty) {
  469 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  470                 ++bnode_count;
  471 #endif
  472                 if (HFS_NEW(empty)) {
  473                         goto restart;
  474                 }
  475                 return bnr;
  476         }
  477         bn = empty;
  478         hfs_bnode_read(bn, tree, node, HFS_NOT_STICKY);
  479         goto return_it;
  480 
  481 found_it:
  482         /* check validity */
  483         if (bn->magic != HFS_BNODE_MAGIC) {
  484                 /* If we find a corrupt bnode then we return
  485                    NULL.  However, we don't try to remove it
  486                    from the cache or release its resources
  487                    since we have no idea what kind of trouble
  488                    we could get into that way. */
  489                 hfs_warn("hfs_bnode_find: bnode cache is corrupt.\n");
  490                 return bnr;
  491         } 
  492         if (empty) {
  493 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  494                 --bnode_count;
  495 #endif
  496                 HFS_DELETE(empty);
  497         }
  498         
  499 return_it:
  500         /* Wait our turn */
  501         bnr.bn = bn;
  502         hfs_bnode_lock(&bnr, lock_type);
  503 
  504         /* Check for failure to read the node from disk */
  505         if (!hfs_buffer_ok(bn->buf)) {
  506                 hfs_bnode_relse(&bnr);
  507         }
  508 
  509 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
  510         if (!bnr.bn) {
  511                 hfs_warn("hfs_bnode_find: failed\n");
  512         } else {
  513                 hfs_warn("hfs_bnode_find: use %d(%d) lvl %d [%d]\n", bn->count,
  514                          bn->buf->b_count, bn->ndNHeight, bnode_count);
  515                 hfs_warn("hfs_bnode_find: blnk %u flnk %u recs %u\n", 
  516                          bn->ndBLink, bn->ndFLink, bn->ndNRecs);
  517         }
  518 #endif
  519 
  520         return bnr;
  521 }
  522 
  523 /*
  524  * hfs_bnode_commit()
  525  *
  526  * Called to write a possibly dirty bnode back to disk.
  527  */
  528 void hfs_bnode_commit(struct hfs_bnode *bn)
  529 {
  530         if (hfs_buffer_ok(bn->buf)) {
  531                 struct NodeDescriptor *nd;
  532                 nd = (struct NodeDescriptor *)hfs_buffer_data(bn->buf);
  533 
  534                 hfs_put_hl(bn->ndFLink, nd->ndFLink);
  535                 hfs_put_hl(bn->ndBLink, nd->ndBLink);
  536                 nd->ndType    = bn->ndType;
  537                 nd->ndNHeight = bn->ndNHeight;
  538                 hfs_put_hs(bn->ndNRecs, nd->ndNRecs);
  539                 hfs_buffer_dirty(bn->buf);
  540 
  541                 /* increment write count */
  542                 hfs_mdb_dirty(bn->tree->sys_mdb);
  543         }
  544 }
Cache object: dff1a2a5902b5c5d6125215909ca55bc
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/fs/hfs/bnode.c

FreeBSD/Linux Kernel Cross Reference
sys/fs/hfs/bnode.c
