X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/0c530ab8987f0ae6a1a3d9284f40182b88852816..39236c6e673c41db228275375ab7fdb0f837b292:/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c diff --git a/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c b/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c index 00874f229..94577758a 100644 --- a/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c +++ b/bsd/hfs/hfscommon/BTree/BTreeNodeReserve.c @@ -1,23 +1,29 @@ /* - * Copyright (c) 2004 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2004-2008 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. + * + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. * - * @APPLE_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ #include "../headers/BTreesPrivate.h" #include "sys/malloc.h" @@ -30,7 +36,6 @@ * 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. @@ -59,7 +64,7 @@ struct nreserve { #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; @@ -74,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 *); -static int nr_lookup (struct vnode *); static void nr_update (struct vnode *, int); @@ -86,7 +90,7 @@ void 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); @@ -99,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. + * + * 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 @@ -128,9 +119,11 @@ BTReserveSpace(FCB *file, int operations, void* data) int rsrvNodes, availNodes, totalNodes; int height; int inserts, deletes; + u_int32_t clumpsize; int err = 0; btree = (BTreeControlBlockPtr)file->fcbBTCBPtr; + clumpsize = file->ff_clumpsize; REQUIRE_FILE_LOCK(btree->fileRefNum, true); @@ -140,30 +133,89 @@ BTReserveSpace(FCB *file, int operations, void* data) * tree. */ height = btree->treeDepth; + if (height < 2) + height = 2; /* prevent underflow in rsrvNodes calculation */ 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) { + 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 */ - if (totalNodes > (int)CalcMapBits(btree)) + if (totalNodes > (int)CalcMapBits(btree)) { ++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); } @@ -228,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->nr_nodecnt += nodecnt; lck_mtx_unlock(&nr_mutex); return; } @@ -253,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)) - 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)); @@ -264,28 +317,6 @@ nr_delete(struct vnode * btvp, struct nreserve *nrp, int *nodecnt) 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.