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 struct hfsmount *hfsmp; 157 158 /* Try and reserve the last 5% of the disk space for file blocks. */ 159 hfsmp = VTOVCB(btree->fileRefNum); 160 rsrvblks = ((u_int64_t)hfsmp->allocLimit * 5) / 100; 161 rsrvblks = MIN(rsrvblks, HFS_MAXRESERVE / hfsmp->blockSize); 162 freeblks = hfs_freeblks(hfsmp, 0); 163 if (freeblks <= rsrvblks) { 164 /* When running low, disallow adding new items. */ 165 if ((inserts > 0) && (deletes == 0)) { 166 return (ENOSPC); 167 } 168 freeblks = 0; 169 } else { 170 freeblks -= rsrvblks; 171 } 172 reqblks = clumpsize / hfsmp->blockSize; 173 174 if (reqblks > freeblks) { 175 reqblks = ((rsrvNodes - availNodes) * btree->nodeSize) / hfsmp->blockSize; 176 /* When running low, disallow adding new items. */ 177 if ((reqblks > freeblks) && (inserts > 0) && (deletes == 0)) { 178 return (ENOSPC); 179 } 180 file->ff_clumpsize = freeblks * hfsmp->blockSize; 181 } 182 totalNodes = rsrvNodes + btree->totalNodes - availNodes; 183 184 /* See if we also need a map node */ 185 if (totalNodes > (int)CalcMapBits(btree)) { 186 ++totalNodes; 187 } 188 if ((err = ExtendBTree(btree, totalNodes))) { 189 goto out; 190 } 191 } 192 /* Save this reserve if this is a persistent request. */ 193 if (data) { 194 btree->reservedNodes += rsrvNodes; 195 nr_insert(btree->fileRefNum, (struct nreserve *)data, rsrvNodes); 196 } 197out: 198 /* Put clump size back if it was changed. */ 199 if (file->ff_clumpsize != clumpsize) 200 file->ff_clumpsize = clumpsize; 201 202 return (err); 203} 204 205 206/* 207 * BTReleaseReserve - release the node reserve held by current thread 208 * 209 * Used by the Catalog Layer (hfs_catalog.c) to relinquish reserved space. 210 */ 211__private_extern__ 212int 213BTReleaseReserve(FCB *file, void* data) 214{ 215 BTreeControlBlock *btree; 216 int nodecnt; 217 218 btree = (BTreeControlBlockPtr)file->fcbBTCBPtr; 219 220 REQUIRE_FILE_LOCK(btree->fileRefNum, true); 221 222 nr_delete(btree->fileRefNum, (struct nreserve *)data, &nodecnt); 223 224 if (nodecnt) 225 btree->reservedNodes -= nodecnt; 226 227 return (0); 228} 229 230/* 231 * BTUpdateReserve - update a node reserve for allocations that occurred. 232 */ 233__private_extern__ 234void 235BTUpdateReserve(BTreeControlBlockPtr btreePtr, int nodes) 236{ 237 nr_update(btreePtr->fileRefNum, nodes); 238} 239 240 241/*----------------------------------------------------------------------------*/ 242/* Node Reserve Hash Functions (private) */ 243 244 245int nrinserts = 0; 246int nrdeletes = 0; 247 248/* 249 * Insert a new node reserve. 250 */ 251static void 252nr_insert(struct vnode * btvp, struct nreserve *nrp, int nodecnt) 253{ 254 struct nodereserve *nrhead; 255 struct nreserve *tmp_nrp; 256 void * tag = NR_GET_TAG(); 257 258 /* 259 * Check the cache - there may already be a reserve 260 */ 261 lck_mtx_lock(&nr_mutex); 262 nrhead = NR_HASH(btvp, tag); 263 for (tmp_nrp = nrhead->lh_first; tmp_nrp; 264 tmp_nrp = tmp_nrp->nr_hash.le_next) { 265 if ((tmp_nrp->nr_tag == tag) && (tmp_nrp->nr_btvp == btvp)) { 266 nrp->nr_tag = 0; 267 tmp_nrp->nr_nodecnt += nodecnt; 268 lck_mtx_unlock(&nr_mutex); 269 return; 270 } 271 } 272 273 nrp->nr_nodecnt = nodecnt; 274 nrp->nr_newnodes = 0; 275 nrp->nr_btvp = btvp; 276 nrp->nr_tag = tag; 277 LIST_INSERT_HEAD(nrhead, nrp, nr_hash); 278 ++nrinserts; 279 lck_mtx_unlock(&nr_mutex); 280} 281 282/* 283 * Delete a node reserve. 284 */ 285static void 286nr_delete(struct vnode * btvp, struct nreserve *nrp, int *nodecnt) 287{ 288 void * tag = NR_GET_TAG(); 289 290 lck_mtx_lock(&nr_mutex); 291 if (nrp->nr_tag) { 292 if ((nrp->nr_tag != tag) || (nrp->nr_btvp != btvp)) 293 panic("hfs: nr_delete: invalid NR (%p)", nrp); 294 LIST_REMOVE(nrp, nr_hash); 295 *nodecnt = nrp->nr_nodecnt; 296 bzero(nrp, sizeof(struct nreserve)); 297 ++nrdeletes; 298 } else { 299 *nodecnt = 0; 300 } 301 lck_mtx_unlock(&nr_mutex); 302} 303 304 305/* 306 * Update a node reserve for any allocations that occurred. 307 */ 308static void 309nr_update(struct vnode * btvp, int nodecnt) 310{ 311 struct nodereserve *nrhead; 312 struct nreserve *nrp; 313 void* tag = NR_GET_TAG(); 314 315 lck_mtx_lock(&nr_mutex); 316 317 nrhead = NR_HASH(btvp, tag); 318 for (nrp = nrhead->lh_first; nrp; nrp = nrp->nr_hash.le_next) { 319 if ((nrp->nr_tag == tag) && (nrp->nr_btvp == btvp)) { 320 nrp->nr_newnodes += nodecnt; 321 break; 322 } 323 } 324 lck_mtx_unlock(&nr_mutex); 325} 326