jfs_xtree.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 *   Copyright (C) International Business Machines Corp., 2000-2005
 */
/*
 *	jfs_xtree.c: extent allocation descriptor B+-tree manager
 */

#include <linux/fs.h>
#include <linux/module.h>
#include <linux/quotaops.h>
#include <linux/seq_file.h>
#include "jfs_incore.h"
#include "jfs_filsys.h"
#include "jfs_metapage.h"
#include "jfs_dmap.h"
#include "jfs_dinode.h"
#include "jfs_superblock.h"
#include "jfs_debug.h"

/*
 * xtree local flag
 */
#define XT_INSERT …

/*
 *	xtree key/entry comparison: extent offset
 *
 * return:
 *	-1: k < start of extent
 *	 0: start_of_extent <= k <= end_of_extent
 *	 1: k > end_of_extent
 */
#define XT_CMP(CMP, K, X, OFFSET64) …

/* write a xad entry */
#define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR) …

#define XT_PAGE(IP, MP) …

/* get page buffer for specified block address */
/* ToDo: Replace this ugly macro with a function */
#define XT_GETPAGE(IP, BN, MP, SIZE, P, RC) …

/* for consistency */
#define XT_PUTPAGE(MP) …

#define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) …
/* xtree entry parameter descriptor */
struct xtsplit { … };


/*
 *	statistics
 */
#ifdef CONFIG_JFS_STATISTICS
static struct { … } xtStat;
#endif


/*
 * forward references
 */
static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
		    struct btstack * btstack, int flag);

static int xtSplitUp(tid_t tid,
		     struct inode *ip,
		     struct xtsplit * split, struct btstack * btstack);

static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
		       struct metapage ** rmpp, s64 * rbnp);

static int xtSplitRoot(tid_t tid, struct inode *ip,
		       struct xtsplit * split, struct metapage ** rmpp);

/*
 *	xtLookup()
 *
 * function: map a single page into a physical extent;
 */
int xtLookup(struct inode *ip, s64 lstart,
	     s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
{ … }

/*
 *	xtSearch()
 *
 * function:	search for the xad entry covering specified offset.
 *
 * parameters:
 *	ip	- file object;
 *	xoff	- extent offset;
 *	nextp	- address of next extent (if any) for search miss
 *	cmpp	- comparison result:
 *	btstack - traverse stack;
 *	flag	- search process flag (XT_INSERT);
 *
 * 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 xtSearch(struct inode *ip, s64 xoff,	s64 *nextp,
		    int *cmpp, struct btstack * btstack, int flag)
{ … }

/*
 *	xtInsert()
 *
 * function:
 *
 * parameter:
 *	tid	- transaction id;
 *	ip	- file object;
 *	xflag	- extent flag (XAD_NOTRECORDED):
 *	xoff	- extent offset;
 *	xlen	- extent length;
 *	xaddrp	- extent address pointer (in/out):
 *		if (*xaddrp)
 *			caller allocated data extent at *xaddrp;
 *		else
 *			allocate data extent and return its xaddr;
 *	flag	-
 *
 * return:
 */
int xtInsert(tid_t tid,		/* transaction id */
	     struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
	     int flag)
{ … }


/*
 *	xtSplitUp()
 *
 * function:
 *	split full pages as propagating insertion up the tree
 *
 * parameter:
 *	tid	- transaction id;
 *	ip	- file object;
 *	split	- entry parameter descriptor;
 *	btstack - traverse stack from xtSearch()
 *
 * return:
 */
static int
xtSplitUp(tid_t tid,
	  struct inode *ip, struct xtsplit * split, struct btstack * btstack)
{ … }


/*
 *	xtSplitPage()
 *
 * function:
 *	split a full non-root page into
 *	original/split/left page and new right page
 *	i.e., the original/split page remains as left page.
 *
 * parameter:
 *	int		tid,
 *	struct inode	*ip,
 *	struct xtsplit	*split,
 *	struct metapage	**rmpp,
 *	u64		*rbnp,
 *
 * return:
 *	Pointer to page in which to insert or NULL on error.
 */
static int
xtSplitPage(tid_t tid, struct inode *ip,
	    struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
{ … }


/*
 *	xtSplitRoot()
 *
 * function:
 *	split the full root page into original/root/split page and new
 *	right page
 *	i.e., root remains fixed in tree anchor (inode) and the root is
 *	copied to a single new right child page since root page <<
 *	non-root page, and the split root page contains a single entry
 *	for the new right child page.
 *
 * parameter:
 *	int		tid,
 *	struct inode	*ip,
 *	struct xtsplit	*split,
 *	struct metapage	**rmpp)
 *
 * return:
 *	Pointer to page in which to insert or NULL on error.
 */
static int
xtSplitRoot(tid_t tid,
	    struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
{ … }


/*
 *	xtExtend()
 *
 * function: extend in-place;
 *
 * 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: alloc whole extended extent;
 */
int xtExtend(tid_t tid,		/* transaction id */
	     struct inode *ip, s64 xoff,	/* delta extent offset */
	     s32 xlen,		/* delta extent length */
	     int flag)
{ … }

/*
 *	xtUpdate()
 *
 * function: update XAD;
 *
 *	update extent for allocated_but_not_recorded or
 *	compressed extent;
 *
 * parameter:
 *	nxad	- new XAD;
 *		logical extent of the specified XAD must be completely
 *		contained by an existing XAD;
 */
int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
{ … }


/*
 *	xtAppend()
 *
 * function: grow in append mode from contiguous region specified ;
 *
 * parameter:
 *	tid		- transaction id;
 *	ip		- file object;
 *	xflag		- extent flag:
 *	xoff		- extent offset;
 *	maxblocks	- max extent length;
 *	xlen		- extent length (in/out);
 *	xaddrp		- extent address pointer (in/out):
 *	flag		-
 *
 * return:
 */
int xtAppend(tid_t tid,		/* transaction id */
	     struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
	     s32 * xlenp,	/* (in/out) */
	     s64 * xaddrp,	/* (in/out) */
	     int flag)
{ … }

/*
 *	xtInitRoot()
 *
 * initialize file root (inline in inode)
 */
void xtInitRoot(tid_t tid, struct inode *ip)
{ … }


/*
 * We can run into a deadlock truncating a file with a large number of
 * xtree pages (large fragmented file).  A robust fix would entail a
 * reservation system where we would reserve a number of metadata pages
 * and tlocks which we would be guaranteed without a deadlock.  Without
 * this, a partial fix is to limit number of metadata pages we will lock
 * in a single transaction.  Currently we will truncate the file so that
 * no more than 50 leaf pages will be locked.  The caller of xtTruncate
 * will be responsible for ensuring that the current transaction gets
 * committed, and that subsequent transactions are created to truncate
 * the file further if needed.
 */
#define MAX_TRUNCATE_LEAVES …

/*
 *	xtTruncate()
 *
 * function:
 *	traverse for truncation logging backward bottom up;
 *	terminate at the last extent entry at the current subtree
 *	root page covering new down size.
 *	truncation may occur within the last extent entry.
 *
 * parameter:
 *	int		tid,
 *	struct inode	*ip,
 *	s64		newsize,
 *	int		type)	{PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
 *
 * return:
 *
 * note:
 *	PWMAP:
 *	 1. truncate (non-COMMIT_NOLINK file)
 *	    by jfs_truncate() or jfs_open(O_TRUNC):
 *	    xtree is updated;
 *	 2. truncate index table of directory when last entry removed
 *	map update via tlock at commit time;
 *	PMAP:
 *	 Call xtTruncate_pmap instead
 *	WMAP:
 *	 1. remove (free zero link count) on last reference release
 *	    (pmap has been freed at commit zero link count);
 *	 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
 *	    xtree is updated;
 *	 map update directly at truncation time;
 *
 *	if (DELETE)
 *		no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
 *	else if (TRUNCATE)
 *		must write LOG_NOREDOPAGE for deleted index page;
 *
 * pages may already have been tlocked by anonymous transactions
 * during file growth (i.e., write) before truncation;
 *
 * except last truncated entry, deleted entries remains as is
 * in the page (nextindex is updated) for other use
 * (e.g., log/update allocation map): this avoid copying the page
 * info but delay free of pages;
 *
 */
s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
{ … }


/*
 *	xtTruncate_pmap()
 *
 * function:
 *	Perform truncate to zero length for deleted file, leaving the
 *	xtree and working map untouched.  This allows the file to
 *	be accessed via open file handles, while the delete of the file
 *	is committed to disk.
 *
 * parameter:
 *	tid_t		tid,
 *	struct inode	*ip,
 *	s64		committed_size)
 *
 * return: new committed size
 *
 * note:
 *
 *	To avoid deadlock by holding too many transaction locks, the
 *	truncation may be broken up into multiple transactions.
 *	The committed_size keeps track of part of the file has been
 *	freed from the pmaps.
 */
s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
{ … }

#ifdef CONFIG_JFS_STATISTICS
int jfs_xtstat_proc_show(struct seq_file *m, void *v)
{ … }
#endif
linux/fs/jfs/jfs_xtree.c
