1/* 2 * Copyright (c) 2004-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28#include "../headers/BTreesPrivate.h" 29#include "sys/malloc.h" 30#include <kern/locks.h> 31 32 33/* 34 * B-tree Node Reserve 35 * 36 * BTReserveSpace 37 * BTReleaseReserve 38 * BTUpdateReserve 39 * 40 * Each kernel thread can have it's own reserve of b-tree 41 * nodes. This reserve info is kept in a hash table. 42 * 43 * Don't forget to call BTReleaseReserve when you're finished 44 * or you will leave stale node reserves in the hash. 45 */ 46 47 48/* 49 * BE CAREFUL WHEN INCREASING THE SIZE OF THIS STRUCT! 50 * 51 * It must remain equal in size to the opaque cat_cookie_t 52 * struct (in hfs_catalog.h). 53 */ 54struct nreserve { 55 LIST_ENTRY(nreserve) nr_hash; /* hash chain */ 56 int nr_nodecnt; /* count of nodes held in reserve */ 57 int nr_newnodes; /* nodes that were allocated */ 58 struct vnode *nr_btvp; /* b-tree file vnode */ 59 void *nr_tag; /* unique tag (per thread) */ 60}; 61 62#define NR_GET_TAG() (current_thread()) 63 64#define NR_CACHE 17 65 66#define NR_HASH(btvp, tag) \ 67 (&nr_hashtbl[((((intptr_t)(btvp)) >> 8) ^ ((intptr_t)(tag) >> 4)) & nr_hashmask]) 68 69LIST_HEAD(nodereserve, nreserve) *nr_hashtbl; 70 71u_long nr_hashmask; 72 73lck_grp_t * nr_lck_grp; 74lck_grp_attr_t * nr_lck_grp_attr; 75lck_attr_t * nr_lck_attr; 76 77lck_mtx_t nr_mutex; 78 79/* Internal Node Reserve Hash Routines (private) */ 80static void nr_insert (struct vnode *, struct nreserve *nrp, int); 81static void nr_delete (struct vnode *, struct nreserve *nrp, int *); 82static void nr_update (struct vnode *, int); 83 84 85/* 86 * BTReserveSetup - initialize the node reserve hash table 87 */ 88__private_extern__ 89void 90BTReserveSetup() 91{ 92 if (sizeof(struct nreserve) != sizeof(cat_cookie_t)) 93 panic("hfs: BTReserveSetup: nreserve size != opaque struct size"); 94 95 nr_hashtbl = hashinit(NR_CACHE, M_HFSMNT, &nr_hashmask); 96 97 nr_lck_grp_attr= lck_grp_attr_alloc_init(); 98 nr_lck_grp = lck_grp_alloc_init("btree_node_reserve", nr_lck_grp_attr); 99 100 nr_lck_attr = lck_attr_alloc_init(); 101 102 lck_mtx_init(&nr_mutex, nr_lck_grp, nr_lck_attr); 103} 104 105 106/* 107 * BTReserveSpace - obtain a node reserve (for current thread) 108 * 109 * Used by the Catalog Layer (hfs_catalog.c) to reserve space. 110 * 111 * When data is NULL, we only insure that there's enough space 112 * but it is not reserved (assumes you keep the b-tree lock). 113 */ 114__private_extern__ 115int 116BTReserveSpace(FCB *file, int operations, void* data) 117{ 118 BTreeControlBlock *btree; 119 int rsrvNodes, availNodes, totalNodes; 120 int height; 121 int inserts, deletes; 122 u_int32_t clumpsize; 123 int err = 0; 124 125 btree = (BTreeControlBlockPtr)file->fcbBTCBPtr; 126 clumpsize = file->ff_clumpsize; 127 128 REQUIRE_FILE_LOCK(btree->fileRefNum, true); 129 130 /* 131 * The node reserve is based on the number of b-tree 132 * operations (insert/deletes) and the height of the 133 * tree. 134 */ 135 height = btree->treeDepth; 136 if (height < 2) 137 height = 2; /* prevent underflow in rsrvNodes calculation */ 138 inserts = operations & 0xffff; 139 deletes = operations >> 16; 140 141 /* 142 * Allow for at least one root split. 143 * 144 * Each delete operation can propogate a big key up the 145 * index. This can cause a split at each level up. 146 * 147 * Each insert operation can cause a local split and a 148 * split at each level up. 149 */ 150 rsrvNodes = 1 + (deletes * (height - 2)) + (inserts * (height - 1)); 151 152 availNodes = btree->freeNodes - btree->reservedNodes; 153 154 if (rsrvNodes > availNodes) { 155 u_int32_t reqblks, freeblks, rsrvblks; 156 uint32_t bt_rsrv; 157 struct hfsmount *hfsmp; 158 159 /* 160 * For UNIX conformance, we try and reserve the MIN of either 5% of 161 * total file blocks or 10MB worth of blocks, for growing existing 162 * files. On non-HFS filesystems, creating a new directory entry may 163 * not cause additional disk space to be allocated, but on HFS, creating 164 * a new entry could cause the b-tree to grow. As a result, we take 165 * some precautions here to prevent that on configurations that try to 166 * satisfy conformance. 167 */ 168 hfsmp = VTOVCB(btree->fileRefNum); 169 rsrvblks = ((u_int64_t)hfsmp->allocLimit * 5) / 100; 170 if (hfsmp->blockSize > HFS_BT_MAXRESERVE) { 171 bt_rsrv = 1; 172 } 173 else { 174 bt_rsrv = (HFS_BT_MAXRESERVE / hfsmp->blockSize); 175 } 176 rsrvblks = MIN(rsrvblks, bt_rsrv); 177 178 freeblks = hfs_freeblks(hfsmp, 0); 179 if (freeblks <= rsrvblks) { 180 /* When running low, disallow adding new items. */ 181 if ((inserts > 0) && (deletes == 0)) { 182 return (ENOSPC); 183 } 184 freeblks = 0; 185 } else { 186 freeblks -= rsrvblks; 187 } 188 reqblks = clumpsize / hfsmp->blockSize; 189 190 if (reqblks > freeblks) { 191 reqblks = ((rsrvNodes - availNodes) * btree->nodeSize) / hfsmp->blockSize; 192 /* When running low, disallow adding new items. */ 193 if ((reqblks > freeblks) && (inserts > 0) && (deletes == 0)) { 194 return (ENOSPC); 195 } 196 file->ff_clumpsize = freeblks * hfsmp->blockSize; 197 } 198 totalNodes = rsrvNodes + btree->totalNodes - availNodes; 199 200 /* See if we also need a map node */ 201 if (totalNodes > (int)CalcMapBits(btree)) { 202 ++totalNodes; 203 } 204 if ((err = ExtendBTree(btree, totalNodes))) { 205 goto out; 206 } 207 } 208 /* Save this reserve if this is a persistent request. */ 209 if (data) { 210 btree->reservedNodes += rsrvNodes; 211 nr_insert(btree->fileRefNum, (struct nreserve *)data, rsrvNodes); 212 } 213out: 214 /* Put clump size back if it was changed. */ 215 if (file->ff_clumpsize != clumpsize) 216 file->ff_clumpsize = clumpsize; 217 218 return (err); 219} 220 221 222/* 223 * BTReleaseReserve - release the node reserve held by current thread 224 * 225 * Used by the Catalog Layer (hfs_catalog.c) to relinquish reserved space. 226 */ 227__private_extern__ 228int 229BTReleaseReserve(FCB *file, void* data) 230{ 231 BTreeControlBlock *btree; 232 int nodecnt; 233 234 btree = (BTreeControlBlockPtr)file->fcbBTCBPtr; 235 236 REQUIRE_FILE_LOCK(btree->fileRefNum, true); 237 238 nr_delete(btree->fileRefNum, (struct nreserve *)data, &nodecnt); 239 240 if (nodecnt) 241 btree->reservedNodes -= nodecnt; 242 243 return (0); 244} 245 246/* 247 * BTUpdateReserve - update a node reserve for allocations that occurred. 248 */ 249__private_extern__ 250void 251BTUpdateReserve(BTreeControlBlockPtr btreePtr, int nodes) 252{ 253 nr_update(btreePtr->fileRefNum, nodes); 254} 255 256 257/*----------------------------------------------------------------------------*/ 258/* Node Reserve Hash Functions (private) */ 259 260 261int nrinserts = 0; 262int nrdeletes = 0; 263 264/* 265 * Insert a new node reserve. 266 */ 267static void 268nr_insert(struct vnode * btvp, struct nreserve *nrp, int nodecnt) 269{ 270 struct nodereserve *nrhead; 271 struct nreserve *tmp_nrp; 272 void * tag = NR_GET_TAG(); 273 274 /* 275 * Check the cache - there may already be a reserve 276 */ 277 lck_mtx_lock(&nr_mutex); 278 nrhead = NR_HASH(btvp, tag); 279 for (tmp_nrp = nrhead->lh_first; tmp_nrp; 280 tmp_nrp = tmp_nrp->nr_hash.le_next) { 281 if ((tmp_nrp->nr_tag == tag) && (tmp_nrp->nr_btvp == btvp)) { 282 nrp->nr_tag = 0; 283 tmp_nrp->nr_nodecnt += nodecnt; 284 lck_mtx_unlock(&nr_mutex); 285 return; 286 } 287 } 288 289 nrp->nr_nodecnt = nodecnt; 290 nrp->nr_newnodes = 0; 291 nrp->nr_btvp = btvp; 292 nrp->nr_tag = tag; 293 LIST_INSERT_HEAD(nrhead, nrp, nr_hash); 294 ++nrinserts; 295 lck_mtx_unlock(&nr_mutex); 296} 297 298/* 299 * Delete a node reserve. 300 */ 301static void 302nr_delete(struct vnode * btvp, struct nreserve *nrp, int *nodecnt) 303{ 304 void * tag = NR_GET_TAG(); 305 306 lck_mtx_lock(&nr_mutex); 307 if (nrp->nr_tag) { 308 if ((nrp->nr_tag != tag) || (nrp->nr_btvp != btvp)) 309 panic("hfs: nr_delete: invalid NR (%p)", nrp); 310 LIST_REMOVE(nrp, nr_hash); 311 *nodecnt = nrp->nr_nodecnt; 312 bzero(nrp, sizeof(struct nreserve)); 313 ++nrdeletes; 314 } else { 315 *nodecnt = 0; 316 } 317 lck_mtx_unlock(&nr_mutex); 318} 319 320 321/* 322 * Update a node reserve for any allocations that occurred. 323 */ 324static void 325nr_update(struct vnode * btvp, int nodecnt) 326{ 327 struct nodereserve *nrhead; 328 struct nreserve *nrp; 329 void* tag = NR_GET_TAG(); 330 331 lck_mtx_lock(&nr_mutex); 332 333 nrhead = NR_HASH(btvp, tag); 334 for (nrp = nrhead->lh_first; nrp; nrp = nrp->nr_hash.le_next) { 335 if ((nrp->nr_tag == tag) && (nrp->nr_btvp == btvp)) { 336 nrp->nr_newnodes += nodecnt; 337 break; 338 } 339 } 340 lck_mtx_unlock(&nr_mutex); 341} 342