jfs_dtree.h 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270
  1. /*
  2. * Copyright (C) International Business Machines Corp., 2000-2002
  3. *
  4. * This program is free software; you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation; either version 2 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * This program is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
  12. * the GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write to the Free Software
  16. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  17. */
  18. #ifndef _H_JFS_DTREE
  19. #define _H_JFS_DTREE
  20. /*
  21. * jfs_dtree.h: directory B+-tree manager
  22. */
  23. #include "jfs_btree.h"
  24. typedef union {
  25. struct {
  26. tid_t tid;
  27. struct inode *ip;
  28. u32 ino;
  29. } leaf;
  30. pxd_t xd;
  31. } ddata_t;
  32. /*
  33. * entry segment/slot
  34. *
  35. * an entry consists of type dependent head/only segment/slot and
  36. * additional segments/slots linked vi next field;
  37. * N.B. last/only segment of entry is terminated by next = -1;
  38. */
  39. /*
  40. * directory page slot
  41. */
  42. struct dtslot {
  43. s8 next; /* 1: */
  44. s8 cnt; /* 1: */
  45. __le16 name[15]; /* 30: */
  46. }; /* (32) */
  47. #define DATASLOTSIZE 16
  48. #define L2DATASLOTSIZE 4
  49. #define DTSLOTSIZE 32
  50. #define L2DTSLOTSIZE 5
  51. #define DTSLOTHDRSIZE 2
  52. #define DTSLOTDATASIZE 30
  53. #define DTSLOTDATALEN 15
  54. /*
  55. * internal node entry head/only segment
  56. */
  57. struct idtentry {
  58. pxd_t xd; /* 8: child extent descriptor */
  59. s8 next; /* 1: */
  60. u8 namlen; /* 1: */
  61. __le16 name[11]; /* 22: 2-byte aligned */
  62. }; /* (32) */
  63. #define DTIHDRSIZE 10
  64. #define DTIHDRDATALEN 11
  65. /* compute number of slots for entry */
  66. #define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15))
  67. /*
  68. * leaf node entry head/only segment
  69. *
  70. * For legacy filesystems, name contains 13 wchars -- no index field
  71. */
  72. struct ldtentry {
  73. __le32 inumber; /* 4: 4-byte aligned */
  74. s8 next; /* 1: */
  75. u8 namlen; /* 1: */
  76. __le16 name[11]; /* 22: 2-byte aligned */
  77. __le32 index; /* 4: index into dir_table */
  78. }; /* (32) */
  79. #define DTLHDRSIZE 6
  80. #define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */
  81. #define DTLHDRDATALEN 11
  82. /*
  83. * dir_table used for directory traversal during readdir
  84. */
  85. /*
  86. * Keep persistent index for directory entries
  87. */
  88. #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)
  89. /*
  90. * Maximum entry in inline directory table
  91. */
  92. #define MAX_INLINE_DIRTABLE_ENTRY 13
  93. struct dir_table_slot {
  94. u8 rsrvd; /* 1: */
  95. u8 flag; /* 1: 0 if free */
  96. u8 slot; /* 1: slot within leaf page of entry */
  97. u8 addr1; /* 1: upper 8 bits of leaf page address */
  98. __le32 addr2; /* 4: lower 32 bits of leaf page address -OR-
  99. index of next entry when this entry was deleted */
  100. }; /* (8) */
  101. /*
  102. * flag values
  103. */
  104. #define DIR_INDEX_VALID 1
  105. #define DIR_INDEX_FREE 0
  106. #define DTSaddress(dir_table_slot, address64)\
  107. {\
  108. (dir_table_slot)->addr1 = ((u64)address64) >> 32;\
  109. (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
  110. }
  111. #define addressDTS(dts)\
  112. ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )
  113. /* compute number of slots for entry */
  114. #define NDTLEAF_LEGACY(klen) (DIV_ROUND_UP((2 + (klen)), 15))
  115. #define NDTLEAF NDTINTERNAL
  116. /*
  117. * directory root page (in-line in on-disk inode):
  118. *
  119. * cf. dtpage_t below.
  120. */
  121. typedef union {
  122. struct {
  123. struct dasd DASD; /* 16: DASD limit/usage info */
  124. u8 flag; /* 1: */
  125. u8 nextindex; /* 1: next free entry in stbl */
  126. s8 freecnt; /* 1: free count */
  127. s8 freelist; /* 1: freelist header */
  128. __le32 idotdot; /* 4: parent inode number */
  129. s8 stbl[8]; /* 8: sorted entry index table */
  130. } header; /* (32) */
  131. struct dtslot slot[9];
  132. } dtroot_t;
  133. #define PARENT(IP) \
  134. (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))
  135. #define DTROOTMAXSLOT 9
  136. #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)
  137. /*
  138. * directory regular page:
  139. *
  140. * entry slot array of 32 byte slot
  141. *
  142. * sorted entry slot index table (stbl):
  143. * contiguous slots at slot specified by stblindex,
  144. * 1-byte per entry
  145. * 512 byte block: 16 entry tbl (1 slot)
  146. * 1024 byte block: 32 entry tbl (1 slot)
  147. * 2048 byte block: 64 entry tbl (2 slot)
  148. * 4096 byte block: 128 entry tbl (4 slot)
  149. *
  150. * data area:
  151. * 512 byte block: 16 - 2 = 14 slot
  152. * 1024 byte block: 32 - 2 = 30 slot
  153. * 2048 byte block: 64 - 3 = 61 slot
  154. * 4096 byte block: 128 - 5 = 123 slot
  155. *
  156. * N.B. index is 0-based; index fields refer to slot index
  157. * except nextindex which refers to entry index in stbl;
  158. * end of entry stot list or freelist is marked with -1.
  159. */
  160. typedef union {
  161. struct {
  162. __le64 next; /* 8: next sibling */
  163. __le64 prev; /* 8: previous sibling */
  164. u8 flag; /* 1: */
  165. u8 nextindex; /* 1: next entry index in stbl */
  166. s8 freecnt; /* 1: */
  167. s8 freelist; /* 1: slot index of head of freelist */
  168. u8 maxslot; /* 1: number of slots in page slot[] */
  169. u8 stblindex; /* 1: slot index of start of stbl */
  170. u8 rsrvd[2]; /* 2: */
  171. pxd_t self; /* 8: self pxd */
  172. } header; /* (32) */
  173. struct dtslot slot[128];
  174. } dtpage_t;
  175. #define DTPAGEMAXSLOT 128
  176. #define DT8THPGNODEBYTES 512
  177. #define DT8THPGNODETSLOTS 1
  178. #define DT8THPGNODESLOTS 16
  179. #define DTQTRPGNODEBYTES 1024
  180. #define DTQTRPGNODETSLOTS 1
  181. #define DTQTRPGNODESLOTS 32
  182. #define DTHALFPGNODEBYTES 2048
  183. #define DTHALFPGNODETSLOTS 2
  184. #define DTHALFPGNODESLOTS 64
  185. #define DTFULLPGNODEBYTES 4096
  186. #define DTFULLPGNODETSLOTS 4
  187. #define DTFULLPGNODESLOTS 128
  188. #define DTENTRYSTART 1
  189. /* get sorted entry table of the page */
  190. #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
  191. ((dtroot_t *)(p))->header.stbl : \
  192. (s8 *)&(p)->slot[(p)->header.stblindex] )
  193. /*
  194. * Flags for dtSearch
  195. */
  196. #define JFS_CREATE 1
  197. #define JFS_LOOKUP 2
  198. #define JFS_REMOVE 3
  199. #define JFS_RENAME 4
  200. /*
  201. * Maximum file offset for directories.
  202. */
  203. #define DIREND INT_MAX
  204. /*
  205. * external declarations
  206. */
  207. extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
  208. extern int dtSearch(struct inode *ip, struct component_name * key,
  209. ino_t * data, struct btstack * btstack, int flag);
  210. extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
  211. ino_t * ino, struct btstack * btstack);
  212. extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
  213. ino_t * data, int flag);
  214. extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
  215. ino_t * orig_ino, ino_t new_ino, int flag);
  216. extern int jfs_readdir(struct file *file, struct dir_context *ctx);
  217. #endif /* !_H_JFS_DTREE */