1/*
2 * Copyright (c) 2002-2013 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28#ifndef __HFS_CATALOG__
29#define __HFS_CATALOG__
30
31#include <sys/appleapiopts.h>
32
33#ifdef KERNEL
34#ifdef __APPLE_API_PRIVATE
35#include <sys/vnode.h>
36
37#include <hfs/hfs_format.h>
38
39/* HFS Catalog */
40
41
42/*
43 * Catalog ADTs
44 *
45 * The cat_desc, cat_attr, and cat_fork structures are
46 * use to import/export data to/from the Catalog file.
47 * The fields in these structures are always in BSD
48 * runtime format (e.g. dates and names).
49 */
50
51typedef u_int32_t	cnid_t;
52
53/*
54 * Catalog Node Descriptor (runtime)
55 */
56struct cat_desc {
57	u_int8_t  cd_flags;       /* see below (8 bits) */
58	u_int8_t  cd_encoding;    /* name encoding */
59	int16_t   cd_namelen;     /* length of cnode name */
60	cnid_t    cd_parentcnid;  /* parent directory CNID */
61	u_int32_t    cd_hint;        /* catalog file hint */
62	cnid_t    cd_cnid;        /* cnode id (for getattrlist) */
63	const u_int8_t * cd_nameptr; /* pointer to cnode name */
64};
65
66/* cd_flags
67 *
68 * CD_EOF is used by hfs_vnop_readdir / cat_getdirentries to indicate EOF was
69 * encountered during a directory enumeration.  When this flag is observed
70 * on the next call to hfs_vnop_readdir it tells the caller that there's no
71 * need to descend into the catalog as EOF was encountered during the last call.
72 * This flag should only be set on the descriptor embedded in the directoryhint.
73 */
74
75#define	CD_HASBUF	0x01	/* allocated filename buffer */
76#define CD_DECOMPOSED	0x02	/* name is fully decomposed */
77#define CD_EOF		0x04	/* see above */
78#define	CD_ISMETA	0x40	/* describes a metadata file */
79#define	CD_ISDIR	0x80	/* describes a directory */
80
81/*
82 * Catalog Node Attributes (runtime)
83 */
84struct cat_attr {
85	cnid_t		ca_fileid;	/* inode number (for stat) normally == cnid */
86	mode_t		ca_mode;	/* file access mode and type (16 bits) */
87	u_int16_t	ca_recflags;	/* catalog record flags (16 bit integer) */
88	u_int32_t	ca_linkcount;	/* real hard link count */
89	uid_t		ca_uid;		/* file owner */
90	gid_t		ca_gid;		/* file group */
91	union {
92	    dev_t	cau_rdev;	/* special file device (VBLK or VCHAR only) */
93	    u_int32_t	cau_linkref;	/* hardlink reference number */
94	} ca_union1;
95	time_t		ca_atime;	/* last access time */
96	time_t		ca_atimeondisk;	/* access time value on disk */
97	time_t		ca_mtime;	/* last data modification time */
98	time_t		ca_ctime;	/* last file status change */
99	time_t		ca_itime;	/* file initialization time */
100	time_t		ca_btime;	/* last backup time */
101	u_int32_t	ca_flags;	/* status flags (chflags) */
102	union {
103	    u_int32_t	cau_blocks;	/* total file blocks used (rsrc + data) */
104	    u_int32_t	cau_entries;	/* total directory entries (valence) */
105	} ca_union2;
106	union {
107	    u_int32_t	cau_dircount;	/* count of sub dirs (for posix nlink) */
108	    u_int32_t	cau_firstlink;	/* first hardlink link (files only) */
109	} ca_union3;
110	u_int8_t 	ca_finderinfo[32]; /* Opaque Finder information */
111};
112
113/* Aliases for common fields */
114#define	ca_rdev		ca_union1.cau_rdev
115#define	ca_linkref	ca_union1.cau_linkref
116#define	ca_blocks	ca_union2.cau_blocks
117#define	ca_entries	ca_union2.cau_entries
118#define	ca_dircount	ca_union3.cau_dircount
119#define	ca_firstlink	ca_union3.cau_firstlink
120
121/*
122 * Catalog Node Fork (runtime)
123 *
124 * NOTE: this is not the same as a struct HFSPlusForkData
125 *
126 * NOTE: if cf_new_size > cf_size, then a write is in progress and is extending
127 * the EOF; the new EOF will be cf_new_size.  Writes and pageouts may validly
128 * write up to cf_new_size, but reads should only read up to cf_size.  When
129 * an extending write is not in progress, cf_new_size is zero.
130 */
131struct cat_fork {
132	off_t          cf_size;        /* fork's logical size in bytes */
133	off_t          cf_new_size;    /* fork's logical size after write completes */
134	union {
135	    u_int32_t  cfu_clump;      /* fork's clump size in bytes (sys files only) */
136	    u_int64_t  cfu_bytesread;  /* bytes read from this fork */
137	} cf_union;
138	u_int32_t      cf_vblocks;     /* virtual (unalloated) blocks */
139	u_int32_t      cf_blocks;      /* total blocks used by this fork */
140	struct HFSPlusExtentDescriptor  cf_extents[8];  /* initial set of extents */
141};
142
143#define cf_clump	cf_union.cfu_clump
144#define cf_bytesread	cf_union.cfu_bytesread
145
146
147/*
148 * Directory Hint
149 * Used to hold state across directory enumerations.
150 *
151 */
152struct directoryhint {
153	TAILQ_ENTRY(directoryhint) dh_link; /* chain */
154	int     dh_index;                   /* index into directory (zero relative) */
155	u_int32_t  dh_threadhint;           /* node hint of a directory's thread record */
156	u_int32_t  dh_time;
157	struct  cat_desc  dh_desc;          /* entry's descriptor */
158};
159typedef struct directoryhint directoryhint_t;
160
161/*
162 * HFS_MAXDIRHINTS cannot be larger than 63 without reducing
163 * HFS_INDEX_BITS, because given the 6-bit tag, at most 63 different
164 * tags can exist.  When HFS_MAXDIRHINTS is larger than 63, the same
165 * list may contain dirhints of the same tag, and a staled dirhint may
166 * be returned.
167 */
168#define HFS_MAXDIRHINTS 32
169#define HFS_DIRHINT_TTL 45
170
171#define HFS_INDEX_MASK  0x03ffffff
172#define HFS_INDEX_BITS  26
173
174
175/*
176 * Catalog Node Entry
177 *
178 * A cat_entry is used for bulk enumerations (hfs_readdirattr).
179 */
180struct cat_entry {
181	struct cat_desc	ce_desc;
182	struct cat_attr	ce_attr;
183	off_t		ce_datasize;
184	off_t		ce_rsrcsize;
185	u_int32_t		ce_datablks;
186	u_int32_t		ce_rsrcblks;
187};
188
189/*
190 * Starting in 10.5, hfs_vnop_readdirattr() only makes one
191 * call to cat_getentriesattr(). So we increased MAXCATENTRIES
192 * while keeping the total size of the CE LIST buffer <= 8K
193 * (which works out to be 60 entries per call).  The 8K limit
194 * keeps the memory coming from a kalloc zone instead of
195 * valuable/fragment-able kernel map space.
196 */
197#define MAXCATENTRIES	\
198	(1 + (8192 - sizeof (struct cat_entrylist)) / sizeof (struct cat_entry))
199
200/*
201 * Catalog Node Entry List
202 *
203 * A cat_entrylist is a list of Catalog Node Entries.
204 */
205struct cat_entrylist {
206	u_int32_t  maxentries;    /* number of entries requested */
207	u_int32_t  realentries;   /* number of valid entries returned */
208	u_int32_t  skipentries;   /* number of entries skipped (reserved HFS+ files) */
209	struct cat_entry  entry[1];   /* array of entries */
210};
211
212#define CE_LIST_SIZE(entries)	\
213	sizeof (*ce_list) + (((entries) - 1) * sizeof (struct cat_entry))
214
215struct hfsmount;
216
217/*
218 * Catalog FileID/CNID Acquisition / Lookup
219 *
220 * Some use-cases require that we find a valid CNID
221 * before we may be ready to enter the item into the namespace.
222 * In order to resolve this, we support a hashtable attached to
223 * the mount that is secured by the catalog lock.
224 *
225 * Finding the next valid CNID is easy if the wraparound bit is
226 * not set -- you just pull from the hfsmp next pointer.
227 * If it is set then you must find a free entry in the catalog
228 * and also query the hashtable to see if the item is free or not.
229 *
230 * If you want to request a CNID before there is a backing item
231 * in the catalog, you must find one that is valid, then insert
232 * it into the hash table until such time that the item is
233 * inserted into the catalog.  After successful catalog insertion,
234 * you must remove the item from the hashtable.
235 */
236
237typedef struct cat_preflightid {
238	cnid_t fileid;
239	LIST_ENTRY(cat_preflightid) id_hash;
240} cat_preflightid_t;
241
242extern int cat_remove_idhash (cat_preflightid_t *preflight);
243extern int cat_insert_idhash (struct hfsmount *hfsmp, cat_preflightid_t *preflight);
244extern int cat_check_idhash (struct hfsmount *hfsmp, cnid_t test_fileid);
245
246/* initialize the id look up hashtable during mount */
247extern void hfs_idhash_init (struct hfsmount *hfsmp);
248
249/* release the id lookup hashtable during unmount */
250extern void hfs_idhash_destroy (struct hfsmount *hfsmp);
251
252/* Get a new CNID for use */
253extern int cat_acquire_cnid (struct hfsmount *hfsmp, cnid_t *new_cnid);
254
255
256/* default size of ID hash is 64 entries */
257#define HFS_IDHASH_DEFAULT 64
258
259
260/*
261 * Catalog Operations Hint
262 *
263 * lower 16 bits: count of B-tree insert operations
264 * upper 16 bits: count of B-tree delete operations
265 *
266 */
267#define CAT_DELETE	0x00010000
268#define CAT_CREATE	0x00000002
269#define CAT_RENAME	0x00010002
270#define CAT_EXCHANGE	0x00010002
271
272typedef u_int32_t	catops_t;
273
274/*
275 * The size of cat_cookie_t much match the size of
276 * the nreserve struct (in BTreeNodeReserve.c).
277 */
278typedef	struct cat_cookie_t {
279#if defined(__LP64__)
280	char	opaque[40];
281#else
282	char	opaque[24];
283#endif
284} cat_cookie_t;
285
286/* Universal catalog key */
287union CatalogKey {
288	HFSCatalogKey      hfs;
289	HFSPlusCatalogKey  hfsPlus;
290};
291typedef union CatalogKey  CatalogKey;
292
293/* Universal catalog data record */
294union CatalogRecord {
295	int16_t               recordType;
296	HFSCatalogFolder      hfsFolder;
297	HFSCatalogFile        hfsFile;
298	HFSCatalogThread      hfsThread;
299	HFSPlusCatalogFolder  hfsPlusFolder;
300	HFSPlusCatalogFile    hfsPlusFile;
301	HFSPlusCatalogThread  hfsPlusThread;
302};
303typedef union CatalogRecord  CatalogRecord;
304
305/* Constants for HFS fork types */
306enum {
307	kHFSDataForkType = 0x0, 	/* data fork */
308	kHFSResourceForkType = 0xff	/* resource fork */
309};
310
311/*
312 * Catalog Interface
313 *
314 * These functions perform a catalog transactions. The
315 * catalog b-tree is abstracted through this interface.
316 * (please don't go around it)
317 */
318
319
320extern void cat_releasedesc(struct cat_desc *descp);
321
322extern int cat_create (	struct hfsmount *hfsmp,
323			cnid_t new_fileid,
324			struct cat_desc *descp,
325			struct cat_attr *attrp,
326			struct cat_desc *out_descp);
327
328extern int cat_delete (	struct hfsmount *hfsmp,
329			struct cat_desc *descp,
330			struct cat_attr *attrp);
331
332extern int cat_lookup (	struct hfsmount *hfsmp,
333			struct cat_desc *descp,
334			int wantrsrc,
335			int force_casesensitive_lookup,
336			struct cat_desc *outdescp,
337			struct cat_attr *attrp,
338			struct cat_fork *forkp,
339    			cnid_t          *desc_cnid);
340
341extern int cat_idlookup (struct hfsmount *hfsmp,
342			cnid_t cnid,
343			int allow_system_files,
344			int wantrsrc,
345			struct cat_desc *outdescp,
346			struct cat_attr *attrp,
347			struct cat_fork *forkp);
348
349extern int cat_findname (struct hfsmount *hfsmp,
350                         cnid_t cnid,
351                         struct cat_desc *outdescp);
352
353extern int cat_getentriesattr(
354			struct hfsmount *hfsmp,
355			directoryhint_t *dirhint,
356			struct cat_entrylist *ce_list);
357
358extern int cat_rename (	struct hfsmount * hfsmp,
359			struct cat_desc * from_cdp,
360			struct cat_desc * todir_cdp,
361			struct cat_desc * to_cdp,
362			struct cat_desc * cdp);
363
364extern int cat_update (	struct hfsmount *hfsmp,
365			struct cat_desc *descp,
366			struct cat_attr *attrp,
367			struct cat_fork *dataforkp,
368			struct cat_fork *rsrcforkp);
369
370extern int cat_getdirentries(
371			struct hfsmount *hfsmp,
372			u_int32_t entrycnt,
373			directoryhint_t *dirhint,
374			uio_t uio,
375			int extended,
376			int * items,
377			int * eofflag);
378
379extern int cat_insertfilethread (
380			struct hfsmount *hfsmp,
381			struct cat_desc *descp);
382
383extern int cat_preflight(
384			struct hfsmount *hfsmp,
385			catops_t ops,
386			cat_cookie_t *cookie,
387			struct proc *p);
388
389extern void cat_postflight(
390			struct hfsmount *hfsmp,
391			cat_cookie_t *cookie,
392			struct proc *p);
393
394extern int cat_binarykeycompare(
395			HFSPlusCatalogKey *searchKey,
396			HFSPlusCatalogKey *trialKey);
397
398extern int CompareCatalogKeys(
399			HFSCatalogKey *searchKey,
400			HFSCatalogKey *trialKey);
401
402extern int CompareExtendedCatalogKeys(
403			HFSPlusCatalogKey *searchKey,
404			HFSPlusCatalogKey *trialKey);
405
406extern void cat_convertattr(
407			struct hfsmount *hfsmp,
408			CatalogRecord * recp,
409			struct cat_attr *attrp,
410			struct cat_fork *datafp,
411			struct cat_fork *rsrcfp);
412
413extern int cat_convertkey(
414			struct hfsmount *hfsmp,
415			CatalogKey *key,
416			CatalogRecord * recp,
417			struct cat_desc *descp);
418
419extern int cat_getkeyplusattr(
420			struct hfsmount *hfsmp,
421			cnid_t cnid,
422			CatalogKey *key,
423			struct cat_attr *attrp);
424
425/* Hard link functions. */
426
427extern int cat_check_link_ancestry(
428			struct hfsmount *hfsmp,
429			cnid_t parentid,
430			cnid_t pointed_at_cnid);
431
432extern int cat_set_childlinkbit(
433			struct hfsmount *hfsmp,
434			cnid_t cnid);
435
436#define HFS_IGNORABLE_LINK  0x00000001
437
438extern int cat_resolvelink( struct hfsmount *hfsmp,
439                            u_int32_t linkref,
440                            int isdirlink,
441                            struct HFSPlusCatalogFile *recp);
442
443extern int cat_createlink( struct hfsmount *hfsmp,
444                           struct cat_desc *descp,
445                           struct cat_attr *attr,
446                           cnid_t nextlinkid,
447                           cnid_t *linkfileid);
448
449/* Finder Info's file type and creator for directory hard link alias */
450enum {
451	kHFSAliasType    = 0x66647270,  /* 'fdrp' */
452	kHFSAliasCreator = 0x4D414353   /* 'MACS' */
453};
454
455extern int cat_deletelink( struct hfsmount *hfsmp,
456                           struct cat_desc *descp);
457
458extern int cat_update_siblinglinks( struct hfsmount *hfsmp,
459                           cnid_t linkfileid,
460                           cnid_t prevlinkid,
461                           cnid_t nextlinkid);
462
463extern int cat_lookuplink( struct hfsmount *hfsmp,
464                           struct cat_desc *descp,
465                           cnid_t *linkfileid,
466                           cnid_t *prevlinkid,
467                           cnid_t *nextlinkid);
468
469extern int cat_lookup_siblinglinks( struct hfsmount *hfsmp,
470                               cnid_t linkfileid,
471                               cnid_t *prevlinkid,
472                               cnid_t *nextlinkid);
473
474extern int cat_lookup_lastlink( struct hfsmount *hfsmp,
475                               cnid_t startid,
476                               cnid_t *nextlinkid,
477							   struct cat_desc *cdesc);
478
479extern int cat_lookup_dirlink(struct hfsmount *hfsmp,
480			     cnid_t dirlink_id,
481			     u_int8_t forktype,
482			     struct cat_desc *outdescp,
483			     struct cat_attr *attrp,
484			     struct cat_fork *forkp);
485
486extern int cat_update_dirlink(struct hfsmount *hfsmp,
487			      u_int8_t forktype,
488			      struct cat_desc *descp,
489			      struct cat_attr *attrp,
490			      struct cat_fork *rsrcforkp);
491
492#endif /* __APPLE_API_PRIVATE */
493#endif /* KERNEL */
494#endif /* __HFS_CATALOG__ */
495