BTreeNodeReserve.c [plain text]
#include "../headers/BTreesPrivate.h"
#include "sys/malloc.h"
#include <kern/locks.h>
struct nreserve {
LIST_ENTRY(nreserve) nr_hash;
int nr_nodecnt;
int nr_newnodes;
struct vnode *nr_btvp;
void *nr_tag;
};
#define NR_GET_TAG() (current_thread())
#define NR_CACHE 17
#define NR_HASH(btvp, tag) \
(&nr_hashtbl[((((intptr_t)(btvp)) >> 8) ^ ((intptr_t)(tag) >> 4)) & nr_hashmask])
LIST_HEAD(nodereserve, nreserve) *nr_hashtbl;
u_long nr_hashmask;
lck_grp_t * nr_lck_grp;
lck_grp_attr_t * nr_lck_grp_attr;
lck_attr_t * nr_lck_attr;
lck_mtx_t nr_mutex;
static void nr_insert (struct vnode *, struct nreserve *nrp, int);
static void nr_delete (struct vnode *, struct nreserve *nrp, int *);
static void nr_update (struct vnode *, int);
__private_extern__
void
BTReserveSetup()
{
if (sizeof(struct nreserve) != sizeof(cat_cookie_t))
panic("hfs: BTReserveSetup: nreserve size != opaque struct size");
nr_hashtbl = hashinit(NR_CACHE, M_HFSMNT, &nr_hashmask);
nr_lck_grp_attr= lck_grp_attr_alloc_init();
nr_lck_grp = lck_grp_alloc_init("btree_node_reserve", nr_lck_grp_attr);
nr_lck_attr = lck_attr_alloc_init();
lck_mtx_init(&nr_mutex, nr_lck_grp, nr_lck_attr);
}
__private_extern__
int
BTReserveSpace(FCB *file, int operations, void* data)
{
BTreeControlBlock *btree;
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);
height = btree->treeDepth;
if (height < 2)
height = 2;
inserts = operations & 0xffff;
deletes = operations >> 16;
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;
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) {
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;
if ((reqblks > freeblks) && (inserts > 0) && (deletes == 0)) {
return (ENOSPC);
}
file->ff_clumpsize = freeblks * hfsmp->blockSize;
}
totalNodes = rsrvNodes + btree->totalNodes - availNodes;
if (totalNodes > (int)CalcMapBits(btree)) {
++totalNodes;
}
if ((err = ExtendBTree(btree, totalNodes))) {
goto out;
}
}
if (data) {
btree->reservedNodes += rsrvNodes;
nr_insert(btree->fileRefNum, (struct nreserve *)data, rsrvNodes);
}
out:
if (file->ff_clumpsize != clumpsize)
file->ff_clumpsize = clumpsize;
return (err);
}
__private_extern__
int
BTReleaseReserve(FCB *file, void* data)
{
BTreeControlBlock *btree;
int nodecnt;
btree = (BTreeControlBlockPtr)file->fcbBTCBPtr;
REQUIRE_FILE_LOCK(btree->fileRefNum, true);
nr_delete(btree->fileRefNum, (struct nreserve *)data, &nodecnt);
if (nodecnt)
btree->reservedNodes -= nodecnt;
return (0);
}
__private_extern__
void
BTUpdateReserve(BTreeControlBlockPtr btreePtr, int nodes)
{
nr_update(btreePtr->fileRefNum, nodes);
}
int nrinserts = 0;
int nrdeletes = 0;
static void
nr_insert(struct vnode * btvp, struct nreserve *nrp, int nodecnt)
{
struct nodereserve *nrhead;
struct nreserve *tmp_nrp;
void * tag = NR_GET_TAG();
lck_mtx_lock(&nr_mutex);
nrhead = NR_HASH(btvp, tag);
for (tmp_nrp = nrhead->lh_first; tmp_nrp;
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;
}
}
nrp->nr_nodecnt = nodecnt;
nrp->nr_newnodes = 0;
nrp->nr_btvp = btvp;
nrp->nr_tag = tag;
LIST_INSERT_HEAD(nrhead, nrp, nr_hash);
++nrinserts;
lck_mtx_unlock(&nr_mutex);
}
static void
nr_delete(struct vnode * btvp, struct nreserve *nrp, int *nodecnt)
{
void * tag = NR_GET_TAG();
lck_mtx_lock(&nr_mutex);
if (nrp->nr_tag) {
if ((nrp->nr_tag != tag) || (nrp->nr_btvp != btvp))
panic("hfs: nr_delete: invalid NR (%p)", nrp);
LIST_REMOVE(nrp, nr_hash);
*nodecnt = nrp->nr_nodecnt;
bzero(nrp, sizeof(struct nreserve));
++nrdeletes;
} else {
*nodecnt = 0;
}
lck_mtx_unlock(&nr_mutex);
}
static void
nr_update(struct vnode * btvp, int nodecnt)
{
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)) {
nrp->nr_newnodes += nodecnt;
break;
}
}
lck_mtx_unlock(&nr_mutex);
}