core/hfs_catalog.h

   1 /*
   2  * Copyright (c) 2002-2015 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_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
  51 typedef u_int32_t       cnid_t;
  52
  53 /*
  54  * Catalog Node Descriptor (runtime)
  55  */
  56 struct 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  */
  84 struct 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         union {
 111                 u_int8_t        ca_finderinfo[32]; /* Opaque Finder information */
 112                 struct {
 113                         FndrFileInfo                                    ca_finderfileinfo;
 114                         struct FndrExtendedFileInfo     ca_finderextendedfileinfo;
 115                 };
 116                 struct {
 117                         FndrDirInfo                                     ca_finderdirinfo;
 118                         struct FndrExtendedDirInfo              ca_finderextendeddirinfo;
 119                 };
 120         };
 121 };
 122
 123 /* Aliases for common fields */
 124 #define ca_rdev         ca_union1.cau_rdev
 125 #define ca_linkref      ca_union1.cau_linkref
 126 #define ca_blocks       ca_union2.cau_blocks
 127 #define ca_entries      ca_union2.cau_entries
 128 #define ca_dircount     ca_union3.cau_dircount
 129 #define ca_firstlink    ca_union3.cau_firstlink
 130
 131 /*
 132  * Catalog Node Fork (runtime)
 133  *
 134  * NOTE: this is not the same as a struct HFSPlusForkData
 135  *
 136  * NOTE: if cf_new_size > cf_size, then a write is in progress and is extending
 137  * the EOF; the new EOF will be cf_new_size.  Writes and pageouts may validly
 138  * write up to cf_new_size, but reads should only read up to cf_size.  When
 139  * an extending write is not in progress, cf_new_size is zero.
 140  */
 141 struct cat_fork {
 142         off_t          cf_size;        /* fork's logical size in bytes */
 143         off_t          cf_new_size;    /* fork's logical size after write completes */
 144         union {
 145             u_int32_t  cfu_clump;      /* fork's clump size in bytes (sys files only) */
 146             u_int64_t  cfu_bytesread;  /* bytes read from this fork */
 147         } cf_union;
 148         u_int32_t      cf_vblocks;     /* virtual (unalloated) blocks */
 149         u_int32_t      cf_blocks;      /* total blocks used by this fork */
 150         struct HFSPlusExtentDescriptor  cf_extents[8];  /* initial set of extents */
 151
 152         /*
 153          * NOTE: If you change this structure, make sure you change you change
 154          * hfs_fork_copy.
 155          */
 156 };
 157
 158 #define cf_clump        cf_union.cfu_clump
 159 #define cf_bytesread    cf_union.cfu_bytesread
 160
 161 void hfs_fork_copy(struct cat_fork *dst, const struct cat_fork *src,
 162                                    HFSPlusExtentDescriptor *extents);
 163
 164 /*
 165  * Directory Hint
 166  * Used to hold state across directory enumerations.
 167  *
 168  */
 169 struct directoryhint {
 170         TAILQ_ENTRY(directoryhint) dh_link; /* chain */
 171         int     dh_index;                   /* index into directory (zero relative) */
 172         u_int32_t  dh_threadhint;           /* node hint of a directory's thread record */
 173         u_int32_t  dh_time;
 174         struct  cat_desc  dh_desc;          /* entry's descriptor */
 175 };
 176 typedef struct directoryhint directoryhint_t;
 177
 178 /*
 179  * HFS_MAXDIRHINTS cannot be larger than 63 without reducing
 180  * HFS_INDEX_BITS, because given the 6-bit tag, at most 63 different
 181  * tags can exist.  When HFS_MAXDIRHINTS is larger than 63, the same
 182  * list may contain dirhints of the same tag, and a staled dirhint may
 183  * be returned.
 184  */
 185 #define HFS_MAXDIRHINTS 32
 186 #define HFS_DIRHINT_TTL 45
 187
 188 #define HFS_INDEX_MASK  0x03ffffff
 189 #define HFS_INDEX_BITS  26
 190
 191
 192 /*
 193  * Catalog Node Entry
 194  *
 195  * A cat_entry is used for bulk enumerations (hfs_readdirattr).
 196  */
 197 struct cat_entry {
 198         struct cat_desc ce_desc;
 199         struct cat_attr ce_attr;
 200         off_t           ce_datasize;
 201         off_t           ce_rsrcsize;
 202         u_int32_t               ce_datablks;
 203         u_int32_t               ce_rsrcblks;
 204 };
 205
 206 /*
 207  * Starting in 10.5, hfs_vnop_readdirattr() only makes one
 208  * call to cat_getentriesattr(). So we increased MAXCATENTRIES
 209  * while keeping the total size of the CE LIST buffer <= 8K
 210  * (which works out to be 60 entries per call).  The 8K limit
 211  * keeps the memory coming from a kalloc zone instead of
 212  * valuable/fragment-able kernel map space.
 213  */
 214 #define MAXCATENTRIES   \
 215         (1 + (8192 - sizeof (struct cat_entrylist)) / sizeof (struct cat_entry))
 216
 217 /*
 218  * Catalog Node Entry List
 219  *
 220  * A cat_entrylist is a list of Catalog Node Entries.
 221  */
 222 struct cat_entrylist {
 223         u_int32_t  maxentries;    /* number of entries requested */
 224         u_int32_t  realentries;   /* number of valid entries returned */
 225         u_int32_t  skipentries;   /* number of entries skipped (reserved HFS+ files) */
 226         struct cat_entry  entry[1];   /* array of entries */
 227 };
 228
 229 #define CE_LIST_SIZE(entries)   \
 230         sizeof (*ce_list) + (((entries) - 1) * sizeof (struct cat_entry))
 231
 232 struct hfsmount;
 233
 234 /*
 235  * Catalog FileID/CNID Acquisition / Lookup
 236  *
 237  * Some use-cases require that we find a valid CNID
 238  * before we may be ready to enter the item into the namespace.
 239  * In order to resolve this, we support a hashtable attached to
 240  * the mount that is secured by the catalog lock.
 241  *
 242  * Finding the next valid CNID is easy if the wraparound bit is
 243  * not set -- you just pull from the hfsmp next pointer.
 244  * If it is set then you must find a free entry in the catalog
 245  * and also query the hashtable to see if the item is free or not.
 246  *
 247  * If you want to request a CNID before there is a backing item
 248  * in the catalog, you must find one that is valid, then insert
 249  * it into the hash table until such time that the item is
 250  * inserted into the catalog.  After successful catalog insertion,
 251  * you must remove the item from the hashtable.
 252  */
 253
 254 typedef struct cat_preflightid {
 255         cnid_t fileid;
 256         LIST_ENTRY(cat_preflightid) id_hash;
 257 } cat_preflightid_t;
 258
 259 extern int cat_remove_idhash (cat_preflightid_t *preflight);
 260 extern int cat_insert_idhash (struct hfsmount *hfsmp, cat_preflightid_t *preflight);
 261 extern int cat_check_idhash (struct hfsmount *hfsmp, cnid_t test_fileid);
 262
 263 /* initialize the id look up hashtable during mount */
 264 extern void hfs_idhash_init (struct hfsmount *hfsmp);
 265
 266 /* release the id lookup hashtable during unmount */
 267 extern void hfs_idhash_destroy (struct hfsmount *hfsmp);
 268
 269 /* Get a new CNID for use */
 270 extern int cat_acquire_cnid (struct hfsmount *hfsmp, cnid_t *new_cnid);
 271
 272
 273 /* default size of ID hash is 64 entries */
 274 #define HFS_IDHASH_DEFAULT 64
 275
 276
 277 /*
 278  * Catalog Operations Hint
 279  *
 280  * lower 16 bits: count of B-tree insert operations
 281  * upper 16 bits: count of B-tree delete operations
 282  *
 283  */
 284 #define CAT_DELETE      0x00010000
 285 #define CAT_CREATE      0x00000002
 286 #define CAT_RENAME      0x00010002
 287 #define CAT_EXCHANGE    0x00010002
 288
 289 typedef u_int32_t       catops_t;
 290
 291 /*
 292  * The size of cat_cookie_t much match the size of
 293  * the nreserve struct (in BTreeNodeReserve.c).
 294  */
 295 typedef struct cat_cookie_t {
 296 #if defined(__LP64__)
 297         char    opaque[40];
 298 #else
 299         char    opaque[24];
 300 #endif
 301 } cat_cookie_t;
 302
 303 /* Universal catalog key */
 304 union CatalogKey {
 305         HFSCatalogKey      hfs;
 306         HFSPlusCatalogKey  hfsPlus;
 307 };
 308 typedef union CatalogKey  CatalogKey;
 309
 310 /* Universal catalog data record */
 311 union CatalogRecord {
 312         int16_t               recordType;
 313         HFSCatalogFolder      hfsFolder;
 314         HFSCatalogFile        hfsFile;
 315         HFSCatalogThread      hfsThread;
 316         HFSPlusCatalogFolder  hfsPlusFolder;
 317         HFSPlusCatalogFile    hfsPlusFile;
 318         HFSPlusCatalogThread  hfsPlusThread;
 319 };
 320 typedef union CatalogRecord  CatalogRecord;
 321
 322 /* Constants for HFS fork types */
 323 enum {
 324         kHFSDataForkType = 0x0,         /* data fork */
 325         kHFSResourceForkType = 0xff     /* resource fork */
 326 };
 327
 328 /*
 329  * Catalog Interface
 330  *
 331  * These functions perform a catalog transactions. The
 332  * catalog b-tree is abstracted through this interface.
 333  * (please don't go around it)
 334  */
 335
 336
 337 extern void cat_releasedesc(struct cat_desc *descp);
 338
 339 extern int cat_create ( struct hfsmount *hfsmp,
 340                         cnid_t new_fileid,
 341                         struct cat_desc *descp,
 342                         struct cat_attr *attrp,
 343                         struct cat_desc *out_descp);
 344
 345 extern int cat_delete ( struct hfsmount *hfsmp,
 346                         struct cat_desc *descp,
 347                         struct cat_attr *attrp);
 348
 349 extern int cat_lookup ( struct hfsmount *hfsmp,
 350                         struct cat_desc *descp,
 351                         int wantrsrc,
 352                         int force_casesensitive_lookup,
 353                         struct cat_desc *outdescp,
 354                         struct cat_attr *attrp,
 355                         struct cat_fork *forkp,
 356                         cnid_t          *desc_cnid);
 357
 358 extern int cat_idlookup (struct hfsmount *hfsmp,
 359                         cnid_t cnid,
 360                         int allow_system_files,
 361                         int wantrsrc,
 362                         struct cat_desc *outdescp,
 363                         struct cat_attr *attrp,
 364                         struct cat_fork *forkp);
 365
 366 extern int cat_findname (struct hfsmount *hfsmp,
 367                          cnid_t cnid,
 368                          struct cat_desc *outdescp);
 369
 370 extern int cat_getentriesattr(
 371                         struct hfsmount *hfsmp,
 372                         directoryhint_t *dirhint,
 373                         struct cat_entrylist *ce_list,
 374                         int *reachedeof);
 375
 376 extern int cat_rename ( struct hfsmount * hfsmp,
 377                         struct cat_desc * from_cdp,
 378                         struct cat_desc * todir_cdp,
 379                         struct cat_desc * to_cdp,
 380                         struct cat_desc * cdp);
 381
 382 extern int cat_update ( struct hfsmount *hfsmp,
 383                         struct cat_desc *descp,
 384                         struct cat_attr *attrp,
 385                         const struct cat_fork *dataforkp,
 386                         const struct cat_fork *rsrcforkp);
 387
 388 extern int cat_getdirentries(
 389                         struct hfsmount *hfsmp,
 390                         u_int32_t entrycnt,
 391                         directoryhint_t *dirhint,
 392                         uio_t uio,
 393                         int extended,
 394                         int * items,
 395                         int * eofflag);
 396
 397 extern int cat_insertfilethread (
 398                         struct hfsmount *hfsmp,
 399                         struct cat_desc *descp);
 400
 401 extern int cat_preflight(
 402                         struct hfsmount *hfsmp,
 403                         catops_t ops,
 404                         cat_cookie_t *cookie,
 405                         struct proc *p);
 406
 407 extern void cat_postflight(
 408                         struct hfsmount *hfsmp,
 409                         cat_cookie_t *cookie,
 410                         struct proc *p);
 411
 412 extern int cat_binarykeycompare(
 413                         HFSPlusCatalogKey *searchKey,
 414                         HFSPlusCatalogKey *trialKey);
 415
 416 extern int CompareCatalogKeys(
 417                         HFSCatalogKey *searchKey,
 418                         HFSCatalogKey *trialKey);
 419
 420 extern int CompareExtendedCatalogKeys(
 421                         HFSPlusCatalogKey *searchKey,
 422                         HFSPlusCatalogKey *trialKey);
 423
 424 extern void cat_convertattr(
 425                         struct hfsmount *hfsmp,
 426                         CatalogRecord * recp,
 427                         struct cat_attr *attrp,
 428                         struct cat_fork *datafp,
 429                         struct cat_fork *rsrcfp);
 430
 431 extern int cat_convertkey(
 432                         struct hfsmount *hfsmp,
 433                         CatalogKey *key,
 434                         CatalogRecord * recp,
 435                         struct cat_desc *descp);
 436
 437 extern int cat_getkeyplusattr(
 438                         struct hfsmount *hfsmp,
 439                         cnid_t cnid,
 440                         CatalogKey *key,
 441                         struct cat_attr *attrp);
 442
 443 /* Hard link functions. */
 444
 445 extern int cat_check_link_ancestry(
 446                         struct hfsmount *hfsmp,
 447                         cnid_t parentid,
 448                         cnid_t pointed_at_cnid);
 449
 450 extern int cat_set_childlinkbit(
 451                         struct hfsmount *hfsmp,
 452                         cnid_t cnid);
 453
 454 #define HFS_IGNORABLE_LINK  0x00000001
 455
 456 extern int cat_resolvelink( struct hfsmount *hfsmp,
 457                             u_int32_t linkref,
 458                             int isdirlink,
 459                             struct HFSPlusCatalogFile *recp);
 460
 461 extern int cat_createlink( struct hfsmount *hfsmp,
 462                            struct cat_desc *descp,
 463                            struct cat_attr *attr,
 464                            cnid_t nextlinkid,
 465                            cnid_t *linkfileid);
 466
 467 /* Finder Info's file type and creator for directory hard link alias */
 468 enum {
 469         kHFSAliasType    = 0x66647270,  /* 'fdrp' */
 470         kHFSAliasCreator = 0x4D414353   /* 'MACS' */
 471 };
 472
 473 extern int cat_deletelink( struct hfsmount *hfsmp,
 474                            struct cat_desc *descp);
 475
 476 extern int cat_update_siblinglinks( struct hfsmount *hfsmp,
 477                            cnid_t linkfileid,
 478                            cnid_t prevlinkid,
 479                            cnid_t nextlinkid);
 480
 481 extern int cat_lookuplink( struct hfsmount *hfsmp,
 482                            struct cat_desc *descp,
 483                            cnid_t *linkfileid,
 484                            cnid_t *prevlinkid,
 485                            cnid_t *nextlinkid);
 486
 487 extern int cat_lookup_siblinglinks( struct hfsmount *hfsmp,
 488                                cnid_t linkfileid,
 489                                cnid_t *prevlinkid,
 490                                cnid_t *nextlinkid);
 491
 492 extern int cat_lookup_lastlink( struct hfsmount *hfsmp,
 493                                cnid_t startid,
 494                                cnid_t *nextlinkid,
 495                                                            struct cat_desc *cdesc);
 496
 497 extern int cat_lookup_dirlink(struct hfsmount *hfsmp,
 498                              cnid_t dirlink_id,
 499                              u_int8_t forktype,
 500                              struct cat_desc *outdescp,
 501                              struct cat_attr *attrp,
 502                              struct cat_fork *forkp);
 503
 504 extern int cat_update_dirlink(struct hfsmount *hfsmp,
 505                               u_int8_t forktype,
 506                               struct cat_desc *descp,
 507                               struct cat_attr *attrp,
 508                               struct cat_fork *rsrcforkp);
 509
 510 #endif /* __APPLE_API_PRIVATE */
 511 #endif /* KERNEL */
 512 #endif /* __HFS_CATALOG__ */