diff options
Diffstat (limited to 'fs/jfs/jfs_xtree.c')
| -rw-r--r-- | fs/jfs/jfs_xtree.c | 961 |
1 files changed, 0 insertions, 961 deletions
diff --git a/fs/jfs/jfs_xtree.c b/fs/jfs/jfs_xtree.c index 3148e9b35f3b..2d304cee884c 100644 --- a/fs/jfs/jfs_xtree.c +++ b/fs/jfs/jfs_xtree.c @@ -114,17 +114,6 @@ static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split, static int xtSplitRoot(tid_t tid, struct inode *ip, struct xtsplit * split, struct metapage ** rmpp); -#ifdef _STILL_TO_PORT -static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp, - xtpage_t * fp, struct btstack * btstack); - -static int xtSearchNode(struct inode *ip, - xad_t * xad, - int *cmpp, struct btstack * btstack, int flag); - -static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp); -#endif /* _STILL_TO_PORT */ - /* * xtLookup() * @@ -1493,189 +1482,6 @@ int xtExtend(tid_t tid, /* transaction id */ return rc; } -#ifdef _NOTYET -/* - * xtTailgate() - * - * function: split existing 'tail' extent - * (split offset >= start offset of tail extent), and - * relocate and extend the split tail half; - * - * note: existing extent may or may not have been committed. - * caller is responsible for pager buffer cache update, and - * working block allocation map update; - * update pmap: free old split tail extent, alloc new extent; - */ -int xtTailgate(tid_t tid, /* transaction id */ - struct inode *ip, s64 xoff, /* split/new extent offset */ - s32 xlen, /* new extent length */ - s64 xaddr, /* new extent address */ - int flag) -{ - int rc = 0; - int cmp; - struct metapage *mp; /* meta-page buffer */ - xtpage_t *p; /* base B+-tree index page */ - s64 bn; - int index, nextindex, llen, rlen; - struct btstack btstack; /* traverse stack */ - struct xtsplit split; /* split information */ - xad_t *xad; - struct tlock *tlck; - struct xtlock *xtlck = 0; - struct tlock *mtlck; - struct maplock *pxdlock; - -/* -printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n", - (ulong)xoff, xlen, (ulong)xaddr); -*/ - - /* there must exist extent to be tailgated */ - if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT))) - return rc; - - /* retrieve search result */ - XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); - - if (cmp != 0) { - XT_PUTPAGE(mp); - jfs_error(ip->i_sb, "couldn't find extent\n"); - return -EIO; - } - - /* entry found must be last entry */ - nextindex = le16_to_cpu(p->header.nextindex); - if (index != nextindex - 1) { - XT_PUTPAGE(mp); - jfs_error(ip->i_sb, "the entry found is not the last entry\n"); - return -EIO; - } - - BT_MARK_DIRTY(mp, ip); - /* - * acquire tlock of the leaf page containing original entry - */ - if (!test_cflag(COMMIT_Nolink, ip)) { - tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW); - xtlck = (struct xtlock *) & tlck->lock; - } - - /* completely replace extent ? */ - xad = &p->xad[index]; -/* -printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n", - (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad)); -*/ - if ((llen = xoff - offsetXAD(xad)) == 0) - goto updateOld; - - /* - * partially replace extent: insert entry for new extent - */ -//insertNew: - /* - * if the leaf page is full, insert the new entry and - * propagate up the router entry for the new page from split - * - * The xtSplitUp() will insert the entry and unpin the leaf page. - */ - if (nextindex == le16_to_cpu(p->header.maxentry)) { - /* xtSpliUp() unpins leaf pages */ - split.mp = mp; - split.index = index + 1; - split.flag = XAD_NEW; - split.off = xoff; /* split offset */ - split.len = xlen; - split.addr = xaddr; - split.pxdlist = NULL; - if ((rc = xtSplitUp(tid, ip, &split, &btstack))) - return rc; - - /* get back old page */ - XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); - if (rc) - return rc; - /* - * if leaf root has been split, original root has been - * copied to new child page, i.e., original entry now - * resides on the new child page; - */ - if (p->header.flag & BT_INTERNAL) { - ASSERT(p->header.nextindex == - cpu_to_le16(XTENTRYSTART + 1)); - xad = &p->xad[XTENTRYSTART]; - bn = addressXAD(xad); - XT_PUTPAGE(mp); - - /* get new child page */ - XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); - if (rc) - return rc; - - BT_MARK_DIRTY(mp, ip); - if (!test_cflag(COMMIT_Nolink, ip)) { - tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW); - xtlck = (struct xtlock *) & tlck->lock; - } - } - } - /* - * insert the new entry into the leaf page - */ - else { - /* insert the new entry: mark the entry NEW */ - xad = &p->xad[index + 1]; - XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr); - - /* advance next available entry index */ - le16_add_cpu(&p->header.nextindex, 1); - } - - /* get back old XAD */ - xad = &p->xad[index]; - - /* - * truncate/relocate old extent at split offset - */ - updateOld: - /* update dmap for old/committed/truncated extent */ - rlen = lengthXAD(xad) - llen; - if (!(xad->flag & XAD_NEW)) { - /* free from PWMAP at commit */ - if (!test_cflag(COMMIT_Nolink, ip)) { - mtlck = txMaplock(tid, ip, tlckMAP); - pxdlock = (struct maplock *) & mtlck->lock; - pxdlock->flag = mlckFREEPXD; - PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen); - PXDlength(&pxdlock->pxd, rlen); - pxdlock->index = 1; - } - } else - /* free from WMAP */ - dbFree(ip, addressXAD(xad) + llen, (s64) rlen); - - if (llen) - /* truncate */ - XADlength(xad, llen); - else - /* replace */ - XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr); - - if (!test_cflag(COMMIT_Nolink, ip)) { - xtlck->lwm.offset = (xtlck->lwm.offset) ? - min(index, (int)xtlck->lwm.offset) : index; - xtlck->lwm.length = le16_to_cpu(p->header.nextindex) - - xtlck->lwm.offset; - } - - /* unpin the leaf page */ - XT_PUTPAGE(mp); - - return rc; -} -#endif /* _NOTYET */ - /* * xtUpdate() * @@ -1753,32 +1559,12 @@ int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad) newindex = index + 1; nextindex = le16_to_cpu(p->header.nextindex); -#ifdef _JFS_WIP_NOCOALESCE - if (xoff < nxoff) - goto updateRight; - - /* - * replace XAD with nXAD - */ - replace: /* (nxoff == xoff) */ - if (nxlen == xlen) { - /* replace XAD with nXAD:recorded */ - *xad = *nxad; - xad->flag = xflag & ~XAD_NOTRECORDED; - - goto out; - } else /* (nxlen < xlen) */ - goto updateLeft; -#endif /* _JFS_WIP_NOCOALESCE */ - -/* #ifdef _JFS_WIP_COALESCE */ if (xoff < nxoff) goto coalesceRight; /* * coalesce with left XAD */ -//coalesceLeft: /* (xoff == nxoff) */ /* is XAD first entry of page ? */ if (index == XTENTRYSTART) goto replace; @@ -1897,7 +1683,6 @@ int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad) jfs_error(ip->i_sb, "xoff >= nxoff\n"); return -EIO; } -/* #endif _JFS_WIP_COALESCE */ /* * split XAD into (lXAD, nXAD): @@ -2305,752 +2090,6 @@ int xtAppend(tid_t tid, /* transaction id */ return rc; } -#ifdef _STILL_TO_PORT - -/* - TBD for defragmentaion/reorganization - - * - * xtDelete() - * - * function: - * delete the entry with the specified key. - * - * N.B.: whole extent of the entry is assumed to be deleted. - * - * parameter: - * - * return: - * ENOENT: if the entry is not found. - * - * exception: - */ -int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag) -{ - int rc = 0; - struct btstack btstack; - int cmp; - s64 bn; - struct metapage *mp; - xtpage_t *p; - int index, nextindex; - struct tlock *tlck; - struct xtlock *xtlck; - - /* - * find the matching entry; xtSearch() pins the page - */ - if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0))) - return rc; - - XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); - if (cmp) { - /* unpin the leaf page */ - XT_PUTPAGE(mp); - return -ENOENT; - } - - /* - * delete the entry from the leaf page - */ - nextindex = le16_to_cpu(p->header.nextindex); - le16_add_cpu(&p->header.nextindex, -1); - - /* - * if the leaf page bocome empty, free the page - */ - if (p->header.nextindex == cpu_to_le16(XTENTRYSTART)) - return (xtDeleteUp(tid, ip, mp, p, &btstack)); - - BT_MARK_DIRTY(mp, ip); - /* - * acquire a transaction lock on the leaf page; - * - * action:xad deletion; - */ - tlck = txLock(tid, ip, mp, tlckXTREE); - xtlck = (struct xtlock *) & tlck->lock; - xtlck->lwm.offset = - (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index; - - /* if delete from middle, shift left/compact the remaining entries */ - if (index < nextindex - 1) - memmove(&p->xad[index], &p->xad[index + 1], - (nextindex - index - 1) * sizeof(xad_t)); - - XT_PUTPAGE(mp); - - return 0; -} - - -/* - TBD for defragmentaion/reorganization - - * - * xtDeleteUp() - * - * function: - * free empty pages as propagating deletion up the tree - * - * parameter: - * - * return: - */ -static int -xtDeleteUp(tid_t tid, struct inode *ip, - struct metapage * fmp, xtpage_t * fp, struct btstack * btstack) -{ - int rc = 0; - struct metapage *mp; - xtpage_t *p; - int index, nextindex; - s64 xaddr; - int xlen; - struct btframe *parent; - struct tlock *tlck; - struct xtlock *xtlck; - - /* - * keep root leaf page which has become empty - */ - if (fp->header.flag & BT_ROOT) { - /* keep the root page */ - fp->header.flag &= ~BT_INTERNAL; - fp->header.flag |= BT_LEAF; - fp->header.nextindex = cpu_to_le16(XTENTRYSTART); - - /* XT_PUTPAGE(fmp); */ - - return 0; - } - - /* - * free non-root leaf page - */ - if ((rc = xtRelink(tid, ip, fp))) { - XT_PUTPAGE(fmp); - return rc; - } - - xaddr = addressPXD(&fp->header.self); - xlen = lengthPXD(&fp->header.self); - /* free the page extent */ - dbFree(ip, xaddr, (s64) xlen); - - /* free the buffer page */ - discard_metapage(fmp); - - /* - * propagate page deletion up the index tree - * - * If the delete from the parent page makes it empty, - * continue all the way up the tree. - * stop if the root page is reached (which is never deleted) or - * if the entry deletion does not empty the page. - */ - while ((parent = BT_POP(btstack)) != NULL) { - /* get/pin the parent page <sp> */ - XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc); - if (rc) - return rc; - - index = parent->index; - - /* delete the entry for the freed child page from parent. - */ - nextindex = le16_to_cpu(p->header.nextindex); - - /* - * the parent has the single entry being deleted: - * free the parent page which has become empty. - */ - if (nextindex == 1) { - if (p->header.flag & BT_ROOT) { - /* keep the root page */ - p->header.flag &= ~BT_INTERNAL; - p->header.flag |= BT_LEAF; - p->header.nextindex = - cpu_to_le16(XTENTRYSTART); - - /* XT_PUTPAGE(mp); */ - - break; - } else { - /* free the parent page */ - if ((rc = xtRelink(tid, ip, p))) - return rc; - - xaddr = addressPXD(&p->header.self); - /* free the page extent */ - dbFree(ip, xaddr, - (s64) JFS_SBI(ip->i_sb)->nbperpage); - - /* unpin/free the buffer page */ - discard_metapage(mp); - - /* propagate up */ - continue; - } - } - /* - * the parent has other entries remaining: - * delete the router entry from the parent page. - */ - else { - BT_MARK_DIRTY(mp, ip); - /* - * acquire a transaction lock on the leaf page; - * - * action:xad deletion; - */ - tlck = txLock(tid, ip, mp, tlckXTREE); - xtlck = (struct xtlock *) & tlck->lock; - xtlck->lwm.offset = - (xtlck->lwm.offset) ? min(index, - xtlck->lwm. - offset) : index; - - /* if delete from middle, - * shift left/compact the remaining entries in the page - */ - if (index < nextindex - 1) - memmove(&p->xad[index], &p->xad[index + 1], - (nextindex - index - - 1) << L2XTSLOTSIZE); - - le16_add_cpu(&p->header.nextindex, -1); - jfs_info("xtDeleteUp(entry): 0x%lx[%d]", - (ulong) parent->bn, index); - } - - /* unpin the parent page */ - XT_PUTPAGE(mp); - - /* exit propagation up */ - break; - } - - return 0; -} - - -/* - * NAME: xtRelocate() - * - * FUNCTION: relocate xtpage or data extent of regular file; - * This function is mainly used by defragfs utility. - * - * NOTE: This routine does not have the logic to handle - * uncommitted allocated extent. The caller should call - * txCommit() to commit all the allocation before call - * this routine. - */ -int -xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */ - s64 nxaddr, /* new xaddr */ - int xtype) -{ /* extent type: XTPAGE or DATAEXT */ - int rc = 0; - struct tblock *tblk; - struct tlock *tlck; - struct xtlock *xtlck; - struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */ - xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */ - xad_t *xad; - pxd_t *pxd; - s64 xoff, xsize; - int xlen; - s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn; - cbuf_t *cp; - s64 offset, nbytes, nbrd, pno; - int nb, npages, nblks; - s64 bn; - int cmp; - int index; - struct pxd_lock *pxdlock; - struct btstack btstack; /* traverse stack */ - - xtype = xtype & EXTENT_TYPE; - - xoff = offsetXAD(oxad); - oxaddr = addressXAD(oxad); - xlen = lengthXAD(oxad); - - /* validate extent offset */ - offset = xoff << JFS_SBI(ip->i_sb)->l2bsize; - if (offset >= ip->i_size) - return -ESTALE; /* stale extent */ - - jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx", - xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr); - - /* - * 1. get and validate the parent xtpage/xad entry - * covering the source extent to be relocated; - */ - if (xtype == DATAEXT) { - /* search in leaf entry */ - rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0); - if (rc) - return rc; - - /* retrieve search result */ - XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); - - if (cmp) { - XT_PUTPAGE(pmp); - return -ESTALE; - } - - /* validate for exact match with a single entry */ - xad = &pp->xad[index]; - if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) { - XT_PUTPAGE(pmp); - return -ESTALE; - } - } else { /* (xtype == XTPAGE) */ - - /* search in internal entry */ - rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0); - if (rc) - return rc; - - /* retrieve search result */ - XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); - - if (cmp) { - XT_PUTPAGE(pmp); - return -ESTALE; - } - - /* xtSearchNode() validated for exact match with a single entry - */ - xad = &pp->xad[index]; - } - jfs_info("xtRelocate: parent xad entry validated."); - - /* - * 2. relocate the extent - */ - if (xtype == DATAEXT) { - /* if the extent is allocated-but-not-recorded - * there is no real data to be moved in this extent, - */ - if (xad->flag & XAD_NOTRECORDED) - goto out; - else - /* release xtpage for cmRead()/xtLookup() */ - XT_PUTPAGE(pmp); - - /* - * cmRelocate() - * - * copy target data pages to be relocated; - * - * data extent must start at page boundary and - * multiple of page size (except the last data extent); - * read in each page of the source data extent into cbuf, - * update the cbuf extent descriptor of the page to be - * homeward bound to new dst data extent - * copy the data from the old extent to new extent. - * copy is essential for compressed files to avoid problems - * that can arise if there was a change in compression - * algorithms. - * it is a good strategy because it may disrupt cache - * policy to keep the pages in memory afterwards. - */ - offset = xoff << JFS_SBI(ip->i_sb)->l2bsize; - assert((offset & CM_OFFSET) == 0); - nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize; - pno = offset >> CM_L2BSIZE; - npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE; -/* - npages = ((offset + nbytes - 1) >> CM_L2BSIZE) - - (offset >> CM_L2BSIZE) + 1; -*/ - sxaddr = oxaddr; - dxaddr = nxaddr; - - /* process the request one cache buffer at a time */ - for (nbrd = 0; nbrd < nbytes; nbrd += nb, - offset += nb, pno++, npages--) { - /* compute page size */ - nb = min(nbytes - nbrd, CM_BSIZE); - - /* get the cache buffer of the page */ - if (rc = cmRead(ip, offset, npages, &cp)) - break; - - assert(addressPXD(&cp->cm_pxd) == sxaddr); - assert(!cp->cm_modified); - - /* bind buffer with the new extent address */ - nblks = nb >> JFS_IP(ip->i_sb)->l2bsize; - cmSetXD(ip, cp, pno, dxaddr, nblks); - - /* release the cbuf, mark it as modified */ - cmPut(cp, true); - - dxaddr += nblks; - sxaddr += nblks; - } - - /* get back parent page */ - if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0))) - return rc; - - XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); - jfs_info("xtRelocate: target data extent relocated."); - } else { /* (xtype == XTPAGE) */ - - /* - * read in the target xtpage from the source extent; - */ - XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc); - if (rc) { - XT_PUTPAGE(pmp); - return rc; - } - - /* - * read in sibling pages if any to update sibling pointers; - */ - rmp = NULL; - if (p->header.next) { - nextbn = le64_to_cpu(p->header.next); - XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc); - if (rc) { - XT_PUTPAGE(pmp); - XT_PUTPAGE(mp); - return (rc); - } - } - - lmp = NULL; - if (p->header.prev) { - prevbn = le64_to_cpu(p->header.prev); - XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc); - if (rc) { - XT_PUTPAGE(pmp); - XT_PUTPAGE(mp); - if (rmp) - XT_PUTPAGE(rmp); - return (rc); - } - } - - /* at this point, all xtpages to be updated are in memory */ - - /* - * update sibling pointers of sibling xtpages if any; - */ - if (lmp) { - BT_MARK_DIRTY(lmp, ip); - tlck = txLock(tid, ip, lmp, tlckXTREE | tlckRELINK); - lp->header.next = cpu_to_le64(nxaddr); - XT_PUTPAGE(lmp); - } - - if (rmp) { - BT_MARK_DIRTY(rmp, ip); - tlck = txLock(tid, ip, rmp, tlckXTREE | tlckRELINK); - rp->header.prev = cpu_to_le64(nxaddr); - XT_PUTPAGE(rmp); - } - - /* - * update the target xtpage to be relocated - * - * update the self address of the target page - * and write to destination extent; - * redo image covers the whole xtpage since it is new page - * to the destination extent; - * update of bmap for the free of source extent - * of the target xtpage itself: - * update of bmap for the allocation of destination extent - * of the target xtpage itself: - * update of bmap for the extents covered by xad entries in - * the target xtpage is not necessary since they are not - * updated; - * if not committed before this relocation, - * target page may contain XAD_NEW entries which must - * be scanned for bmap update (logredo() always - * scan xtpage REDOPAGE image for bmap update); - * if committed before this relocation (tlckRELOCATE), - * scan may be skipped by commit() and logredo(); - */ - BT_MARK_DIRTY(mp, ip); - /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */ - tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW); - xtlck = (struct xtlock *) & tlck->lock; - - /* update the self address in the xtpage header */ - pxd = &p->header.self; - PXDaddress(pxd, nxaddr); - - /* linelock for the after image of the whole page */ - xtlck->lwm.length = - le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset; - - /* update the buffer extent descriptor of target xtpage */ - xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize; - bmSetXD(mp, nxaddr, xsize); - - /* unpin the target page to new homeward bound */ - XT_PUTPAGE(mp); - jfs_info("xtRelocate: target xtpage relocated."); - } - - /* - * 3. acquire maplock for the source extent to be freed; - * - * acquire a maplock saving the src relocated extent address; - * to free of the extent at commit time; - */ - out: - /* if DATAEXT relocation, write a LOG_UPDATEMAP record for - * free PXD of the source data extent (logredo() will update - * bmap for free of source data extent), and update bmap for - * free of the source data extent; - */ - if (xtype == DATAEXT) - tlck = txMaplock(tid, ip, tlckMAP); - /* if XTPAGE relocation, write a LOG_NOREDOPAGE record - * for the source xtpage (logredo() will init NoRedoPage - * filter and will also update bmap for free of the source - * xtpage), and update bmap for free of the source xtpage; - * N.B. We use tlckMAP instead of tlkcXTREE because there - * is no buffer associated with this lock since the buffer - * has been redirected to the target location. - */ - else /* (xtype == XTPAGE) */ - tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE); - - pxdlock = (struct pxd_lock *) & tlck->lock; - pxdlock->flag = mlckFREEPXD; - PXDaddress(&pxdlock->pxd, oxaddr); - PXDlength(&pxdlock->pxd, xlen); - pxdlock->index = 1; - - /* - * 4. update the parent xad entry for relocation; - * - * acquire tlck for the parent entry with XAD_NEW as entry - * update which will write LOG_REDOPAGE and update bmap for - * allocation of XAD_NEW destination extent; - */ - jfs_info("xtRelocate: update parent xad entry."); - BT_MARK_DIRTY(pmp, ip); - tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW); - xtlck = (struct xtlock *) & tlck->lock; - - /* update the XAD with the new destination extent; */ - xad = &pp->xad[index]; - xad->flag |= XAD_NEW; - XADaddress(xad, nxaddr); - - xtlck->lwm.offset = min(index, xtlck->lwm.offset); - xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) - - xtlck->lwm.offset; - - /* unpin the parent xtpage */ - XT_PUTPAGE(pmp); - - return rc; -} - - -/* - * xtSearchNode() - * - * function: search for the internal xad entry covering specified extent. - * This function is mainly used by defragfs utility. - * - * parameters: - * ip - file object; - * xad - extent to find; - * cmpp - comparison result: - * btstack - traverse stack; - * flag - search process flag; - * - * returns: - * btstack contains (bn, index) of search path traversed to the entry. - * *cmpp is set to result of comparison with the entry returned. - * the page containing the entry is pinned at exit. - */ -static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */ - int *cmpp, struct btstack * btstack, int flag) -{ - int rc = 0; - s64 xoff, xaddr; - int xlen; - int cmp = 1; /* init for empty page */ - s64 bn; /* block number */ - struct metapage *mp; /* meta-page buffer */ - xtpage_t *p; /* page */ - int base, index, lim; - struct btframe *btsp; - s64 t64; - - BT_CLR(btstack); - - xoff = offsetXAD(xad); - xlen = lengthXAD(xad); - xaddr = addressXAD(xad); - - /* - * search down tree from root: - * - * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of - * internal page, child page Pi contains entry with k, Ki <= K < Kj. - * - * if entry with search key K is not found - * internal page search find the entry with largest key Ki - * less than K which point to the child page to search; - * leaf page search find the entry with smallest key Kj - * greater than K so that the returned index is the position of - * the entry to be shifted right for insertion of new entry. - * for empty tree, search key is greater than any key of the tree. - * - * by convention, root bn = 0. - */ - for (bn = 0;;) { - /* get/pin the page to search */ - XT_GETPAGE(ip, bn, mp, PSIZE, p, rc); - if (rc) - return rc; - if (p->header.flag & BT_LEAF) { - XT_PUTPAGE(mp); - return -ESTALE; - } - - lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART; - - /* - * binary search with search key K on the current page - */ - for (base = XTENTRYSTART; lim; lim >>= 1) { - index = base + (lim >> 1); - - XT_CMP(cmp, xoff, &p->xad[index], t64); - if (cmp == 0) { - /* - * search hit - * - * verify for exact match; - */ - if (xaddr == addressXAD(&p->xad[index]) && - xoff == offsetXAD(&p->xad[index])) { - *cmpp = cmp; - - /* save search result */ - btsp = btstack->top; - btsp->bn = bn; - btsp->index = index; - btsp->mp = mp; - - return 0; - } - - /* descend/search its child page */ - goto next; - } - - if (cmp > 0) { - base = index + 1; - --lim; - } - } - - /* - * search miss - non-leaf page: - * - * base is the smallest index with key (Kj) greater than - * search key (K) and may be zero or maxentry index. - * if base is non-zero, decrement base by one to get the parent - * entry of the child page to search. - */ - index = base ? base - 1 : base; - - /* - * go down to child page - */ - next: - /* get the child page block number */ - bn = addressXAD(&p->xad[index]); - - /* unpin the parent page */ - XT_PUTPAGE(mp); - } -} - - -/* - * xtRelink() - * - * function: - * link around a freed page. - * - * Parameter: - * int tid, - * struct inode *ip, - * xtpage_t *p) - * - * returns: - */ -static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p) -{ - int rc = 0; - struct metapage *mp; - s64 nextbn, prevbn; - struct tlock *tlck; - - nextbn = le64_to_cpu(p->header.next); - prevbn = le64_to_cpu(p->header.prev); - - /* update prev pointer of the next page */ - if (nextbn != 0) { - XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc); - if (rc) - return rc; - - /* - * acquire a transaction lock on the page; - * - * action: update prev pointer; - */ - BT_MARK_DIRTY(mp, ip); - tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK); - - /* the page may already have been tlock'd */ - - p->header.prev = cpu_to_le64(prevbn); - - XT_PUTPAGE(mp); - } - - /* update next pointer of the previous page */ - if (prevbn != 0) { - XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc); - if (rc) - return rc; - - /* - * acquire a transaction lock on the page; - * - * action: update next pointer; - */ - BT_MARK_DIRTY(mp, ip); - tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK); - - /* the page may already have been tlock'd */ - - p->header.next = le64_to_cpu(nextbn); - - XT_PUTPAGE(mp); - } - - return 0; -} -#endif /* _STILL_TO_PORT */ - /* * xtInitRoot() |