xnu-2422.1.72.tar.gz

[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeNodeReserve.c

diff --git a/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c b/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c
index 6310ef09ab229faa3e58bae2346f71e90308a016..94577758a1d7da705c82287ad81e34ee460c6e99 100644 (file)
--- a/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c
+++ b/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (c) 2004 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2004-2008 Apple Inc. All rights reserved.

  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 


@@ -36,7 +36,6 @@
  * BTReserveSpace
  * BTReleaseReserve
  * BTUpdateReserve
  * BTReserveSpace
  * BTReleaseReserve
  * BTUpdateReserve

- * BTAvailableNodes

  *
  * Each kernel thread can have it's own reserve of b-tree
  * nodes. This reserve info is kept in a hash table.
  *
  * Each kernel thread can have it's own reserve of b-tree
  * nodes. This reserve info is kept in a hash table.


@@ -65,7 +64,7 @@ struct nreserve {
 #define        NR_CACHE 17
 
 #define NR_HASH(btvp, tag) \
 #define        NR_CACHE 17
 
 #define NR_HASH(btvp, tag) \

-       (&nr_hashtbl[((((int)(btvp)) >> 8) ^ ((int)(tag) >> 4)) & nr_hashmask])
+       (&nr_hashtbl[((((intptr_t)(btvp)) >> 8) ^ ((intptr_t)(tag) >> 4)) & nr_hashmask])

 
 LIST_HEAD(nodereserve, nreserve) *nr_hashtbl;
 
 
 LIST_HEAD(nodereserve, nreserve) *nr_hashtbl;
 


@@ -80,7 +79,6 @@ lck_mtx_t  nr_mutex;
 /* Internal Node Reserve Hash Routines (private) */
 static void nr_insert (struct vnode *, struct nreserve *nrp, int);
 static void nr_delete (struct vnode *, struct nreserve *nrp, int *);
 /* Internal Node Reserve Hash Routines (private) */
 static void nr_insert (struct vnode *, struct nreserve *nrp, int);
 static void nr_delete (struct vnode *, struct nreserve *nrp, int *);

-static int  nr_lookup (struct vnode *);

 static void nr_update (struct vnode *, int);
 
 
 static void nr_update (struct vnode *, int);
 
 


@@ -92,7 +90,7 @@ void
 BTReserveSetup()
 {
        if (sizeof(struct nreserve) != sizeof(cat_cookie_t))
 BTReserveSetup()
 {
        if (sizeof(struct nreserve) != sizeof(cat_cookie_t))

-               panic("BTReserveSetup: nreserve size != opaque struct size");
+               panic("hfs: BTReserveSetup: nreserve size != opaque struct size");

 
        nr_hashtbl = hashinit(NR_CACHE, M_HFSMNT, &nr_hashmask);
 
 
        nr_hashtbl = hashinit(NR_CACHE, M_HFSMNT, &nr_hashmask);
 


@@ -105,26 +103,13 @@ BTReserveSetup()
 }
 
 
 }
 
 

-/*
- * BTAvailNodes - obtain the actual available nodes (for current thread)
- *
- */
-__private_extern__
-SInt32
-BTAvailableNodes(BTreeControlBlock *btree)
-{
-       SInt32 availNodes;
-
-       availNodes = (SInt32)btree->freeNodes - (SInt32)btree->reservedNodes;
-
-       return (availNodes + nr_lookup(btree->fileRefNum));
-}
-
-

 /*
  * BTReserveSpace - obtain a node reserve (for current thread)
  *
  * Used by the Catalog Layer (hfs_catalog.c) to reserve space.
 /*
  * BTReserveSpace - obtain a node reserve (for current thread)
  *
  * Used by the Catalog Layer (hfs_catalog.c) to reserve space.

+ *
+ * When data is NULL, we only insure that there's enough space
+ * but it is not reserved (assumes you keep the b-tree lock).

  */
 __private_extern__
 int
  */
 __private_extern__
 int


@@ -134,9 +119,11 @@ BTReserveSpace(FCB *file, int operations, void* data)
        int rsrvNodes, availNodes, totalNodes;
        int height;
        int inserts, deletes;
        int rsrvNodes, availNodes, totalNodes;
        int height;
        int inserts, deletes;

+       u_int32_t clumpsize;

        int err = 0;
 
        btree = (BTreeControlBlockPtr)file->fcbBTCBPtr;
        int err = 0;
 
        btree = (BTreeControlBlockPtr)file->fcbBTCBPtr;

+       clumpsize = file->ff_clumpsize;

 
        REQUIRE_FILE_LOCK(btree->fileRefNum, true);
 
 
        REQUIRE_FILE_LOCK(btree->fileRefNum, true);
 


@@ -146,30 +133,89 @@ BTReserveSpace(FCB *file, int operations, void* data)
         * tree.
         */
        height = btree->treeDepth;
         * tree.
         */
        height = btree->treeDepth;

+       if (height < 2)
+               height = 2;  /* prevent underflow in rsrvNodes calculation */

        inserts = operations & 0xffff;
        deletes = operations >> 16;
        
        inserts = operations & 0xffff;
        deletes = operations >> 16;
        

-       rsrvNodes = 1; /* allow for at least one root split */
-       if (deletes)
-               rsrvNodes += (deletes * (height - 1)) - 1;
-       if (inserts)
-               rsrvNodes += (inserts * height) + 1;
+       /*
+        * Allow for at least one root split.
+        *
+        * Each delete operation can propogate a big key up the
+        * index. This can cause a split at each level up.
+        *
+        * Each insert operation can cause a local split and a
+        * split at each level up.
+        */
+       rsrvNodes = 1 + (deletes * (height - 2)) + (inserts * (height - 1));

 
        availNodes = btree->freeNodes - btree->reservedNodes;
        
        if (rsrvNodes > availNodes) {
 
        availNodes = btree->freeNodes - btree->reservedNodes;
        
        if (rsrvNodes > availNodes) {

+               u_int32_t reqblks, freeblks, rsrvblks;
+               uint32_t bt_rsrv;
+               struct hfsmount *hfsmp;
+
+               /* 
+                * For UNIX conformance, we try and reserve the MIN of either 5% of 
+                * total file blocks or 10MB worth of blocks, for growing existing 
+                * files.  On non-HFS filesystems, creating a new directory entry may
+                * not cause additional disk space to be allocated, but on HFS, creating
+                * a new entry could cause the b-tree to grow.  As a result, we take 
+                * some precautions here to prevent that on configurations that try to 
+                * satisfy conformance.
+                */
+               hfsmp = VTOVCB(btree->fileRefNum);
+               rsrvblks = ((u_int64_t)hfsmp->allocLimit * 5) / 100;
+               if (hfsmp->blockSize > HFS_BT_MAXRESERVE) {
+                       bt_rsrv = 1;    
+               }
+               else {
+                       bt_rsrv = (HFS_BT_MAXRESERVE / hfsmp->blockSize);
+               }
+               rsrvblks = MIN(rsrvblks, bt_rsrv);      
+               
+               freeblks = hfs_freeblks(hfsmp, 0);
+               if (freeblks <= rsrvblks) {
+                       /* When running low, disallow adding new items. */
+                       if ((inserts > 0) && (deletes == 0)) {
+                               return (ENOSPC);
+                       }
+                       freeblks = 0;
+               } else {
+                       freeblks -= rsrvblks;
+               }
+               reqblks = clumpsize / hfsmp->blockSize;
+
+               if (reqblks > freeblks) {
+                       reqblks = ((rsrvNodes - availNodes) * btree->nodeSize) / hfsmp->blockSize;
+                       /* When running low, disallow adding new items. */
+                       if ((reqblks > freeblks) && (inserts > 0) && (deletes == 0)) {
+                               return (ENOSPC);
+                       }
+                       file->ff_clumpsize = freeblks * hfsmp->blockSize;
+               }

                totalNodes = rsrvNodes + btree->totalNodes - availNodes;
                
                /* See if we also need a map node */
                totalNodes = rsrvNodes + btree->totalNodes - availNodes;
                
                /* See if we also need a map node */

-               if (totalNodes > (int)CalcMapBits(btree))
+               if (totalNodes > (int)CalcMapBits(btree)) {

                        ++totalNodes;
                        ++totalNodes;

-               if ((err = ExtendBTree(btree, totalNodes)))
-                       return (err);
-       }       
+               }
+               if ((err = ExtendBTree(btree, totalNodes))) {
+                       goto out;
+               }
+       }
+       /* Save this reserve if this is a persistent request. */
+       if (data) {
+               btree->reservedNodes += rsrvNodes;
+               nr_insert(btree->fileRefNum, (struct nreserve *)data, rsrvNodes);
+       }
+out:
+       /* Put clump size back if it was changed. */
+       if (file->ff_clumpsize != clumpsize)
+               file->ff_clumpsize = clumpsize;

 
 

-       btree->reservedNodes += rsrvNodes;
-       nr_insert(btree->fileRefNum, (struct nreserve *)data, rsrvNodes);
-       return (0);
+       return (err);

 }
 
 
 }
 
 


@@ -234,6 +280,7 @@ nr_insert(struct vnode * btvp, struct nreserve *nrp, int nodecnt)
             tmp_nrp = tmp_nrp->nr_hash.le_next) {
                if ((tmp_nrp->nr_tag == tag) && (tmp_nrp->nr_btvp == btvp)) {
                        nrp->nr_tag = 0;
             tmp_nrp = tmp_nrp->nr_hash.le_next) {
                if ((tmp_nrp->nr_tag == tag) && (tmp_nrp->nr_btvp == btvp)) {
                        nrp->nr_tag = 0;

+                       tmp_nrp->nr_nodecnt += nodecnt;

                        lck_mtx_unlock(&nr_mutex);
                        return;
                }
                        lck_mtx_unlock(&nr_mutex);
                        return;
                }


@@ -259,7 +306,7 @@ nr_delete(struct vnode * btvp, struct nreserve *nrp, int *nodecnt)
        lck_mtx_lock(&nr_mutex);
        if (nrp->nr_tag) {
                if ((nrp->nr_tag != tag) || (nrp->nr_btvp != btvp))
        lck_mtx_lock(&nr_mutex);
        if (nrp->nr_tag) {
                if ((nrp->nr_tag != tag) || (nrp->nr_btvp != btvp))

-                       panic("nr_delete: invalid NR (%08x)", nrp);
+                       panic("hfs: nr_delete: invalid NR (%p)", nrp);

                LIST_REMOVE(nrp, nr_hash);
                *nodecnt = nrp->nr_nodecnt;
                bzero(nrp, sizeof(struct nreserve));
                LIST_REMOVE(nrp, nr_hash);
                *nodecnt = nrp->nr_nodecnt;
                bzero(nrp, sizeof(struct nreserve));


@@ -270,28 +317,6 @@ nr_delete(struct vnode * btvp, struct nreserve *nrp, int *nodecnt)
        lck_mtx_unlock(&nr_mutex);
 }
 
        lck_mtx_unlock(&nr_mutex);
 }
 

-/*
- * Lookup a node reserve.
- */
-static int
-nr_lookup(struct vnode * btvp)
-{
-       struct nodereserve *nrhead;
-       struct nreserve *nrp;
-       void* tag = NR_GET_TAG();
-
-       lck_mtx_lock(&nr_mutex);
-
-       nrhead = NR_HASH(btvp, tag);
-       for (nrp = nrhead->lh_first; nrp; nrp = nrp->nr_hash.le_next) {
-               if ((nrp->nr_tag == tag) && (nrp->nr_btvp == btvp)) {
-                       lck_mtx_unlock(&nr_mutex);
-                       return (nrp->nr_nodecnt - nrp->nr_newnodes);
-               }
-       }
-       lck_mtx_unlock(&nr_mutex);
-       return (0);
-}

 
 /*
  * Update a node reserve for any allocations that occurred.
 
 /*
  * Update a node reserve for any allocations that occurred.