~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/jfs/jfs_dtree.h

Version: ~ [ linux-5.8-rc5 ] ~ [ linux-5.7.8 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.51 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.132 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.188 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.230 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.230 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 /*
 22  *      jfs_dtree.h: directory B+-tree manager
 23  */
 24 
 25 #include "jfs_btree.h"
 26 
 27 typedef union {
 28         struct {
 29                 tid_t tid;
 30                 struct inode *ip;
 31                 u32 ino;
 32         } leaf;
 33         pxd_t xd;
 34 } ddata_t;
 35 
 36 
 37 /*
 38  *      entry segment/slot
 39  *
 40  * an entry consists of type dependent head/only segment/slot and
 41  * additional segments/slots linked vi next field;
 42  * N.B. last/only segment of entry is terminated by next = -1;
 43  */
 44 /*
 45  *      directory page slot
 46  */
 47 struct dtslot {
 48         s8 next;                /* 1: */
 49         s8 cnt;                 /* 1: */
 50         __le16 name[15];        /* 30: */
 51 };                              /* (32) */
 52 
 53 
 54 #define DATASLOTSIZE    16
 55 #define L2DATASLOTSIZE  4
 56 #define DTSLOTSIZE      32
 57 #define L2DTSLOTSIZE    5
 58 #define DTSLOTHDRSIZE   2
 59 #define DTSLOTDATASIZE  30
 60 #define DTSLOTDATALEN   15
 61 
 62 /*
 63  *       internal node entry head/only segment
 64  */
 65 struct idtentry {
 66         pxd_t xd;               /* 8: child extent descriptor */
 67 
 68         s8 next;                /* 1: */
 69         u8 namlen;              /* 1: */
 70         __le16 name[11];        /* 22: 2-byte aligned */
 71 };                              /* (32) */
 72 
 73 #define DTIHDRSIZE      10
 74 #define DTIHDRDATALEN   11
 75 
 76 /* compute number of slots for entry */
 77 #define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15))
 78 
 79 
 80 /*
 81  *      leaf node entry head/only segment
 82  *
 83  *      For legacy filesystems, name contains 13 wchars -- no index field
 84  */
 85 struct ldtentry {
 86         __le32 inumber;         /* 4: 4-byte aligned */
 87         s8 next;                /* 1: */
 88         u8 namlen;              /* 1: */
 89         __le16 name[11];        /* 22: 2-byte aligned */
 90         __le32 index;           /* 4: index into dir_table */
 91 };                              /* (32) */
 92 
 93 #define DTLHDRSIZE      6
 94 #define DTLHDRDATALEN_LEGACY    13      /* Old (OS/2) format */
 95 #define DTLHDRDATALEN   11
 96 
 97 /*
 98  * dir_table used for directory traversal during readdir
 99  */
100 
101 /*
102  * Keep persistent index for directory entries
103  */
104 #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)
105 
106 /*
107  * Maximum entry in inline directory table
108  */
109 #define MAX_INLINE_DIRTABLE_ENTRY 13
110 
111 struct dir_table_slot {
112         u8 rsrvd;               /* 1: */
113         u8 flag;                /* 1: 0 if free */
114         u8 slot;                /* 1: slot within leaf page of entry */
115         u8 addr1;               /* 1: upper 8 bits of leaf page address */
116         __le32 addr2;           /* 4: lower 32 bits of leaf page address -OR-
117                                    index of next entry when this entry was deleted */
118 };                              /* (8) */
119 
120 /*
121  * flag values
122  */
123 #define DIR_INDEX_VALID 1
124 #define DIR_INDEX_FREE 0
125 
126 #define DTSaddress(dir_table_slot, address64)\
127 {\
128         (dir_table_slot)->addr1 = ((u64)address64) >> 32;\
129         (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
130 }
131 
132 #define addressDTS(dts)\
133         ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )
134 
135 /* compute number of slots for entry */
136 #define NDTLEAF_LEGACY(klen)    (DIV_ROUND_UP((2 + (klen)), 15))
137 #define NDTLEAF NDTINTERNAL
138 
139 
140 /*
141  *      directory root page (in-line in on-disk inode):
142  *
143  * cf. dtpage_t below.
144  */
145 typedef union {
146         struct {
147                 struct dasd DASD; /* 16: DASD limit/usage info */
148 
149                 u8 flag;        /* 1: */
150                 u8 nextindex;   /* 1: next free entry in stbl */
151                 s8 freecnt;     /* 1: free count */
152                 s8 freelist;    /* 1: freelist header */
153 
154                 __le32 idotdot; /* 4: parent inode number */
155 
156                 s8 stbl[8];     /* 8: sorted entry index table */
157         } header;               /* (32) */
158 
159         struct dtslot slot[9];
160 } dtroot_t;
161 
162 #define PARENT(IP) \
163         (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))
164 
165 #define DTROOTMAXSLOT   9
166 
167 #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)
168 
169 
170 /*
171  *      directory regular page:
172  *
173  *      entry slot array of 32 byte slot
174  *
175  * sorted entry slot index table (stbl):
176  * contiguous slots at slot specified by stblindex,
177  * 1-byte per entry
178  *   512 byte block:  16 entry tbl (1 slot)
179  *  1024 byte block:  32 entry tbl (1 slot)
180  *  2048 byte block:  64 entry tbl (2 slot)
181  *  4096 byte block: 128 entry tbl (4 slot)
182  *
183  * data area:
184  *   512 byte block:  16 - 2 =  14 slot
185  *  1024 byte block:  32 - 2 =  30 slot
186  *  2048 byte block:  64 - 3 =  61 slot
187  *  4096 byte block: 128 - 5 = 123 slot
188  *
189  * N.B. index is 0-based; index fields refer to slot index
190  * except nextindex which refers to entry index in stbl;
191  * end of entry stot list or freelist is marked with -1.
192  */
193 typedef union {
194         struct {
195                 __le64 next;    /* 8: next sibling */
196                 __le64 prev;    /* 8: previous sibling */
197 
198                 u8 flag;        /* 1: */
199                 u8 nextindex;   /* 1: next entry index in stbl */
200                 s8 freecnt;     /* 1: */
201                 s8 freelist;    /* 1: slot index of head of freelist */
202 
203                 u8 maxslot;     /* 1: number of slots in page slot[] */
204                 u8 stblindex;   /* 1: slot index of start of stbl */
205                 u8 rsrvd[2];    /* 2: */
206 
207                 pxd_t self;     /* 8: self pxd */
208         } header;               /* (32) */
209 
210         struct dtslot slot[128];
211 } dtpage_t;
212 
213 #define DTPAGEMAXSLOT        128
214 
215 #define DT8THPGNODEBYTES     512
216 #define DT8THPGNODETSLOTS      1
217 #define DT8THPGNODESLOTS      16
218 
219 #define DTQTRPGNODEBYTES    1024
220 #define DTQTRPGNODETSLOTS      1
221 #define DTQTRPGNODESLOTS      32
222 
223 #define DTHALFPGNODEBYTES   2048
224 #define DTHALFPGNODETSLOTS     2
225 #define DTHALFPGNODESLOTS     64
226 
227 #define DTFULLPGNODEBYTES   4096
228 #define DTFULLPGNODETSLOTS     4
229 #define DTFULLPGNODESLOTS    128
230 
231 #define DTENTRYSTART    1
232 
233 /* get sorted entry table of the page */
234 #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
235         ((dtroot_t *)(p))->header.stbl : \
236         (s8 *)&(p)->slot[(p)->header.stblindex] )
237 
238 /*
239  * Flags for dtSearch
240  */
241 #define JFS_CREATE 1
242 #define JFS_LOOKUP 2
243 #define JFS_REMOVE 3
244 #define JFS_RENAME 4
245 
246 /*
247  * Maximum file offset for directories.
248  */
249 #define DIREND  INT_MAX
250 
251 /*
252  *      external declarations
253  */
254 extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
255 
256 extern int dtSearch(struct inode *ip, struct component_name * key,
257                     ino_t * data, struct btstack * btstack, int flag);
258 
259 extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
260                     ino_t * ino, struct btstack * btstack);
261 
262 extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
263                     ino_t * data, int flag);
264 
265 extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
266                     ino_t * orig_ino, ino_t new_ino, int flag);
267 
268 extern int jfs_readdir(struct file *file, struct dir_context *ctx);
269 #endif                          /* !_H_JFS_DTREE */
270 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp