fs/jfs/jfs_dtree.h - kernel/msm-4.9 - Gitiles

 /*
  *   Copyright (c) International Business Machines Corp., 2000-2002
  *
  *   This program is free software;  you can redistribute it and/or modify
  *   it under the terms of the GNU General Public License as published by
  *   the Free Software Foundation; either version 2 of the License, or
  *   (at your option) any later version.
  *
  *   This program is distributed in the hope that it will be useful,
  *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
  *   the GNU General Public License for more details.
  *
  *   You should have received a copy of the GNU General Public License
  *   along with this program;  if not, write to the Free Software
  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  */
 #ifndef _H_JFS_DTREE
 #define	_H_JFS_DTREE

 /*
  *	jfs_dtree.h: directory B+-tree manager
  */

 #include "jfs_btree.h"

 typedef union {
 	struct {
 		tid_t tid;
 		struct inode *ip;
 		u32 ino;
 	} leaf;
 	pxd_t xd;
 } ddata_t;


 /*
  *      entry segment/slot
  *
  * an entry consists of type dependent head/only segment/slot and
  * additional segments/slots linked vi next field;
  * N.B. last/only segment of entry is terminated by next = -1;
  */
 /*
  *	directory page slot
  */
 struct dtslot {
 	s8 next;		/* 1: */
 	s8 cnt;			/* 1: */
 	__le16 name[15];	/* 30: */
 };				/* (32) */


 #define DATASLOTSIZE	16
 #define L2DATASLOTSIZE	4
 #define	DTSLOTSIZE	32
 #define	L2DTSLOTSIZE	5
 #define DTSLOTHDRSIZE	2
 #define DTSLOTDATASIZE	30
 #define DTSLOTDATALEN	15

 /*
  *	 internal node entry head/only segment
  */
 struct idtentry {
 	pxd_t xd;		/* 8: child extent descriptor */

 	s8 next;		/* 1: */
 	u8 namlen;		/* 1: */
 	__le16 name[11];	/* 22: 2-byte aligned */
 };				/* (32) */

 #define DTIHDRSIZE	10
 #define DTIHDRDATALEN	11

 /* compute number of slots for entry */
 #define	NDTINTERNAL(klen) ( ((4 + (klen)) + (15 - 1)) / 15 )


 /*
  *	leaf node entry head/only segment
  *
  * 	For legacy filesystems, name contains 13 wchars -- no index field
  */
 struct ldtentry {
 	__le32 inumber;		/* 4: 4-byte aligned */
 	s8 next;		/* 1: */
 	u8 namlen;		/* 1: */
 	__le16 name[11];	/* 22: 2-byte aligned */
 	__le32 index;		/* 4: index into dir_table */
 };				/* (32) */

 #define DTLHDRSIZE	6
 #define DTLHDRDATALEN_LEGACY	13	/* Old (OS/2) format */
 #define DTLHDRDATALEN	11

 /*
  * dir_table used for directory traversal during readdir
  */

 /*
  * Keep persistent index for directory entries
  */
 #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)

 /*
  * Maximum entry in inline directory table
  */
 #define MAX_INLINE_DIRTABLE_ENTRY 13

 struct dir_table_slot {
 	u8 rsrvd;		/* 1: */
 	u8 flag;		/* 1: 0 if free */
 	u8 slot;		/* 1: slot within leaf page of entry */
 	u8 addr1;		/* 1: upper 8 bits of leaf page address */
 	__le32 addr2;		/* 4: lower 32 bits of leaf page address -OR-
 				   index of next entry when this entry was deleted */
 };				/* (8) */

 /*
  * flag values
  */
 #define DIR_INDEX_VALID 1
 #define DIR_INDEX_FREE 0

 #define DTSaddress(dir_table_slot, address64)\
 {\
 	(dir_table_slot)->addr1 = ((u64)address64) >> 32;\
 	(dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
 }

 #define addressDTS(dts)\
 	( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )

 /* compute number of slots for entry */
 #define	NDTLEAF_LEGACY(klen)	( ((2 + (klen)) + (15 - 1)) / 15 )
 #define	NDTLEAF	NDTINTERNAL


 /*
  *	directory root page (in-line in on-disk inode):
  *
  * cf. dtpage_t below.
  */
 typedef union {
 	struct {
 		struct dasd DASD; /* 16: DASD limit/usage info */

 		u8 flag;	/* 1: */
 		u8 nextindex;	/* 1: next free entry in stbl */
 		s8 freecnt;	/* 1: free count */
 		s8 freelist;	/* 1: freelist header */

 		__le32 idotdot;	/* 4: parent inode number */

 		s8 stbl[8];	/* 8: sorted entry index table */
 	} header;		/* (32) */

 	struct dtslot slot[9];
 } dtroot_t;

 #define PARENT(IP) \
 	(le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))

 #define DTROOTMAXSLOT	9

 #define	dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)


 /*
  *	directory regular page:
  *
  *	entry slot array of 32 byte slot
  *
  * sorted entry slot index table (stbl):
  * contiguous slots at slot specified by stblindex,
  * 1-byte per entry
  *   512 byte block:  16 entry tbl (1 slot)
  *  1024 byte block:  32 entry tbl (1 slot)
  *  2048 byte block:  64 entry tbl (2 slot)
  *  4096 byte block: 128 entry tbl (4 slot)
  *
  * data area:
  *   512 byte block:  16 - 2 =  14 slot
  *  1024 byte block:  32 - 2 =  30 slot
  *  2048 byte block:  64 - 3 =  61 slot
  *  4096 byte block: 128 - 5 = 123 slot
  *
  * N.B. index is 0-based; index fields refer to slot index
  * except nextindex which refers to entry index in stbl;
  * end of entry stot list or freelist is marked with -1.
  */
 typedef union {
 	struct {
 		__le64 next;	/* 8: next sibling */
 		__le64 prev;	/* 8: previous sibling */

 		u8 flag;	/* 1: */
 		u8 nextindex;	/* 1: next entry index in stbl */
 		s8 freecnt;	/* 1: */
 		s8 freelist;	/* 1: slot index of head of freelist */

 		u8 maxslot;	/* 1: number of slots in page slot[] */
 		u8 stblindex;	/* 1: slot index of start of stbl */
 		u8 rsrvd[2];	/* 2: */

 		pxd_t self;	/* 8: self pxd */
 	} header;		/* (32) */

 	struct dtslot slot[128];
 } dtpage_t;

 #define DTPAGEMAXSLOT        128

 #define DT8THPGNODEBYTES     512
 #define DT8THPGNODETSLOTS      1
 #define DT8THPGNODESLOTS      16

 #define DTQTRPGNODEBYTES    1024
 #define DTQTRPGNODETSLOTS      1
 #define DTQTRPGNODESLOTS      32

 #define DTHALFPGNODEBYTES   2048
 #define DTHALFPGNODETSLOTS     2
 #define DTHALFPGNODESLOTS     64

 #define DTFULLPGNODEBYTES   4096
 #define DTFULLPGNODETSLOTS     4
 #define DTFULLPGNODESLOTS    128

 #define DTENTRYSTART	1

 /* get sorted entry table of the page */
 #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
 	((dtroot_t *)(p))->header.stbl : \
 	(s8 *)&(p)->slot[(p)->header.stblindex] )

 /*
  * Flags for dtSearch
  */
 #define JFS_CREATE 1
 #define JFS_LOOKUP 2
 #define JFS_REMOVE 3
 #define JFS_RENAME 4

 #define DIRENTSIZ(namlen) \
     ( (sizeof(struct dirent) - 2*(JFS_NAME_MAX+1) + 2*((namlen)+1) + 3) &~ 3 )

 /*
  * Maximum file offset for directories.
  */
 #define DIREND	INT_MAX

 /*
  *	external declarations
  */
 extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);

 extern int dtSearch(struct inode *ip, struct component_name * key,
 		    ino_t * data, struct btstack * btstack, int flag);

 extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
 		    ino_t * ino, struct btstack * btstack);

 extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
 		    ino_t * data, int flag);

 extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
 		    ino_t * orig_ino, ino_t new_ino, int flag);

 extern int jfs_readdir(struct file *filp, void *dirent, filldir_t filldir);

 #ifdef  _JFS_DEBUG_DTREE
 extern int dtDisplayTree(struct inode *ip);

 extern int dtDisplayPage(struct inode *ip, s64 bn, dtpage_t * p);
 #endif				/* _JFS_DEBUG_DTREE */

 #endif				/* !_H_JFS_DTREE */
	/*
	* Copyright (c) International Business Machines Corp., 2000-2002
	*
	* This program is free software; you can redistribute it and/or modify
	* it under the terms of the GNU General Public License as published by
	* the Free Software Foundation; either version 2 of the License, or
	* (at your option) any later version.
	*
	* This program is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
	* the GNU General Public License for more details.
	*
	* You should have received a copy of the GNU General Public License
	* along with this program; if not, write to the Free Software
	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	*/
	#ifndef _H_JFS_DTREE
	#define _H_JFS_DTREE

	/*
	* jfs_dtree.h: directory B+-tree manager
	*/

	#include "jfs_btree.h"

	typedef union {
	struct {
	tid_t tid;
	struct inode *ip;
	u32 ino;
	} leaf;
	pxd_t xd;
	} ddata_t;


	/*
	* entry segment/slot
	*
	* an entry consists of type dependent head/only segment/slot and
	* additional segments/slots linked vi next field;
	* N.B. last/only segment of entry is terminated by next = -1;
	*/
	/*
	* directory page slot
	*/
	struct dtslot {
	s8 next; /* 1: */
	s8 cnt; /* 1: */
	__le16 name[15]; /* 30: */
	}; /* (32) */


	#define DATASLOTSIZE 16
	#define L2DATASLOTSIZE 4
	#define DTSLOTSIZE 32
	#define L2DTSLOTSIZE 5
	#define DTSLOTHDRSIZE 2
	#define DTSLOTDATASIZE 30
	#define DTSLOTDATALEN 15

	/*
	* internal node entry head/only segment
	*/
	struct idtentry {
	pxd_t xd; /* 8: child extent descriptor */

	s8 next; /* 1: */
	u8 namlen; /* 1: */
	__le16 name[11]; /* 22: 2-byte aligned */
	}; /* (32) */

	#define DTIHDRSIZE 10
	#define DTIHDRDATALEN 11

	/* compute number of slots for entry */
	#define NDTINTERNAL(klen) ( ((4 + (klen)) + (15 - 1)) / 15 )


	/*
	* leaf node entry head/only segment
	*
	* For legacy filesystems, name contains 13 wchars -- no index field
	*/
	struct ldtentry {
	__le32 inumber; /* 4: 4-byte aligned */
	s8 next; /* 1: */
	u8 namlen; /* 1: */
	__le16 name[11]; /* 22: 2-byte aligned */
	__le32 index; /* 4: index into dir_table */
	}; /* (32) */

	#define DTLHDRSIZE 6
	#define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */
	#define DTLHDRDATALEN 11

	/*
	* dir_table used for directory traversal during readdir
	*/

	/*
	* Keep persistent index for directory entries
	*/
	#define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)

	/*
	* Maximum entry in inline directory table
	*/
	#define MAX_INLINE_DIRTABLE_ENTRY 13

	struct dir_table_slot {
	u8 rsrvd; /* 1: */
	u8 flag; /* 1: 0 if free */
	u8 slot; /* 1: slot within leaf page of entry */
	u8 addr1; /* 1: upper 8 bits of leaf page address */
	__le32 addr2; /* 4: lower 32 bits of leaf page address -OR-
	index of next entry when this entry was deleted */
	}; /* (8) */

	/*
	* flag values
	*/
	#define DIR_INDEX_VALID 1
	#define DIR_INDEX_FREE 0

	#define DTSaddress(dir_table_slot, address64)\
	{\
	(dir_table_slot)->addr1 = ((u64)address64) >> 32;\
	(dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
	}

	#define addressDTS(dts)\
	( ((s64)((dts)->addr1)) << 32 \| __le32_to_cpu((dts)->addr2) )

	/* compute number of slots for entry */
	#define NDTLEAF_LEGACY(klen) ( ((2 + (klen)) + (15 - 1)) / 15 )
	#define NDTLEAF NDTINTERNAL


	/*
	* directory root page (in-line in on-disk inode):
	*
	* cf. dtpage_t below.
	*/
	typedef union {
	struct {
	struct dasd DASD; /* 16: DASD limit/usage info */

	u8 flag; /* 1: */
	u8 nextindex; /* 1: next free entry in stbl */
	s8 freecnt; /* 1: free count */
	s8 freelist; /* 1: freelist header */

	__le32 idotdot; /* 4: parent inode number */

	s8 stbl[8]; /* 8: sorted entry index table */
	} header; /* (32) */

	struct dtslot slot[9];
	} dtroot_t;

	#define PARENT(IP) \
	(le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))

	#define DTROOTMAXSLOT 9

	#define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)


	/*
	* directory regular page:
	*
	* entry slot array of 32 byte slot
	*
	* sorted entry slot index table (stbl):
	* contiguous slots at slot specified by stblindex,
	* 1-byte per entry
	* 512 byte block: 16 entry tbl (1 slot)
	* 1024 byte block: 32 entry tbl (1 slot)
	* 2048 byte block: 64 entry tbl (2 slot)
	* 4096 byte block: 128 entry tbl (4 slot)
	*
	* data area:
	* 512 byte block: 16 - 2 = 14 slot
	* 1024 byte block: 32 - 2 = 30 slot
	* 2048 byte block: 64 - 3 = 61 slot
	* 4096 byte block: 128 - 5 = 123 slot
	*
	* N.B. index is 0-based; index fields refer to slot index
	* except nextindex which refers to entry index in stbl;
	* end of entry stot list or freelist is marked with -1.
	*/
	typedef union {
	struct {
	__le64 next; /* 8: next sibling */
	__le64 prev; /* 8: previous sibling */

	u8 flag; /* 1: */
	u8 nextindex; /* 1: next entry index in stbl */
	s8 freecnt; /* 1: */
	s8 freelist; /* 1: slot index of head of freelist */

	u8 maxslot; /* 1: number of slots in page slot[] */
	u8 stblindex; /* 1: slot index of start of stbl */
	u8 rsrvd[2]; /* 2: */

	pxd_t self; /* 8: self pxd */
	} header; /* (32) */

	struct dtslot slot[128];
	} dtpage_t;

	#define DTPAGEMAXSLOT 128

	#define DT8THPGNODEBYTES 512
	#define DT8THPGNODETSLOTS 1
	#define DT8THPGNODESLOTS 16

	#define DTQTRPGNODEBYTES 1024
	#define DTQTRPGNODETSLOTS 1
	#define DTQTRPGNODESLOTS 32

	#define DTHALFPGNODEBYTES 2048
	#define DTHALFPGNODETSLOTS 2
	#define DTHALFPGNODESLOTS 64

	#define DTFULLPGNODEBYTES 4096
	#define DTFULLPGNODETSLOTS 4
	#define DTFULLPGNODESLOTS 128

	#define DTENTRYSTART 1

	/* get sorted entry table of the page */
	#define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
	((dtroot_t *)(p))->header.stbl : \
	(s8 *)&(p)->slot[(p)->header.stblindex] )

	/*
	* Flags for dtSearch
	*/
	#define JFS_CREATE 1
	#define JFS_LOOKUP 2
	#define JFS_REMOVE 3
	#define JFS_RENAME 4

	#define DIRENTSIZ(namlen) \
	( (sizeof(struct dirent) - 2(JFS_NAME_MAX+1) + 2((namlen)+1) + 3) &~ 3 )

	/*
	* Maximum file offset for directories.
	*/
	#define DIREND INT_MAX

	/*
	* external declarations
	*/
	extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);

	extern int dtSearch(struct inode ip, struct component_name key,
	ino_t * data, struct btstack * btstack, int flag);

	extern int dtInsert(tid_t tid, struct inode ip, struct component_name key,
	ino_t * ino, struct btstack * btstack);

	extern int dtDelete(tid_t tid, struct inode ip, struct component_name key,
	ino_t * data, int flag);

	extern int dtModify(tid_t tid, struct inode ip, struct component_name key,
	ino_t * orig_ino, ino_t new_ino, int flag);

	extern int jfs_readdir(struct file filp, void dirent, filldir_t filldir);

	#ifdef _JFS_DEBUG_DTREE
	extern int dtDisplayTree(struct inode *ip);

	extern int dtDisplayPage(struct inode ip, s64 bn, dtpage_t p);
	#endif /* _JFS_DEBUG_DTREE */

	#endif /* !_H_JFS_DTREE */