usr/src/uts/common/sys/dnlc.h

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
  23  */
  24
  25 /*      Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T     */
  26 /*        All Rights Reserved   */
  27
  28 /*
  29  * University Copyright- Copyright (c) 1982, 1986, 1988
  30  * The Regents of the University of California
  31  * All Rights Reserved
  32  *
  33  * University Acknowledgment- Portions of this document are derived from
  34  * software developed by the University of California, Berkeley, and its
  35  * contributors.
  36  */
  37
  38 #ifndef _SYS_DNLC_H
  39 #define _SYS_DNLC_H
  40
  41 #ifdef  __cplusplus
  42 extern "C" {
  43 #endif
  44
  45 #include <sys/kstat.h>
  46
  47 /*
  48  * DNLC - Directory name lookup cache.
  49  * There are now two sorts of name caching:
  50  *
  51  * Standard dnlc: This original cache holds recent mappings
  52  *                of <directory vnode, name> to vnode mappings.
  53  *
  54  * Directory caches: Entire large directories can be cached, subject to
  55  *                   memory availability and tunables. A directory cache
  56  *                   anchor point must be provided in the xxnode for
  57  *                   a directory.
  58  */
  59
  60
  61 /*
  62  * Standard dnlc
  63  * =============
  64  */
  65
  66 /*
  67  * This structure describes the elements in the cache of recent
  68  * names looked up.
  69  *
  70  * Note namlen is a uchar_t to conserve space
  71  * and alignment padding. The max length of any
  72  * pathname component is defined as MAXNAMELEN
  73  * which is 256 (including the terminating null).
  74  * So provided this doesn't change, we don't include the null,
  75  * we always use bcmp to compare strings, and we don't start
  76  * storing full names, then we are ok. The space savings are worth it.
  77  */
  78 typedef struct ncache {
  79         struct ncache *hash_next;       /* hash chain, MUST BE FIRST */
  80         struct ncache *hash_prev;
  81         struct vnode *vp;               /* vnode the name refers to */
  82         struct vnode *dp;               /* vnode of parent of name */
  83         int hash;                       /* hash signature */
  84         uchar_t namlen;                 /* length of name */
  85         char name[1];                   /* segment name - null terminated */
  86 } ncache_t;
  87
  88 /*
  89  * Hash table bucket structure of name cache entries for fast lookup.
  90  */
  91 typedef struct nc_hash  {
  92         ncache_t *hash_next;
  93         ncache_t *hash_prev;
  94         kmutex_t hash_lock;
  95 } nc_hash_t;
  96
  97 /*
  98  * Statistics on name cache
  99  * Not protected by locks
 100  */
 101 /*
 102  * ncstats has been deprecated, due to the integer size of the counters
 103  * which can easily overflow in the dnlc.
 104  * It is maintained (at some expense) for compatability.
 105  * The preferred interface is the kstat accessible nc_stats below, ehich
 106  * is actually shared with directory caching.
 107  */
 108 struct ncstats {
 109         int     hits;           /* hits that we can really use */
 110         int     misses;         /* cache misses */
 111         int     enters;         /* number of enters done */
 112         int     dbl_enters;     /* number of enters tried when already cached */
 113         int     long_enter;     /* deprecated, no longer accounted */
 114         int     long_look;      /* deprecated, no longer accounted */
 115         int     move_to_front;  /* entry moved to front of hash chain */
 116         int     purges;         /* number of purges of cache */
 117 };
 118
 119 struct nc_stats {
 120         kstat_named_t ncs_hits;         /* cache hits */
 121         kstat_named_t ncs_misses;       /* cache misses */
 122         kstat_named_t ncs_neg_hits;     /* negative cache hits */
 123         kstat_named_t ncs_enters;       /* enters */
 124         kstat_named_t ncs_dbl_enters;   /* enters when entry already cached */
 125         kstat_named_t ncs_purge_total;  /* total entries prurged */
 126         kstat_named_t ncs_purge_all;    /* dnlc_purge() calls */
 127         kstat_named_t ncs_purge_vp;     /* dnlc_purge_vp() calls */
 128         kstat_named_t ncs_purge_vfs;    /* dnlc_purge_vfs() calls */
 129         kstat_named_t ncs_purge_fs1;    /* dnlc_purge_fs1() calls */
 130         kstat_named_t ncs_pick_free;    /* found a free ncache */
 131         kstat_named_t ncs_pick_heur;    /* found ncache w/ NULL vpages */
 132         kstat_named_t ncs_pick_last;    /* found last ncache on chain */
 133
 134         /* directory caching stats */
 135
 136         kstat_named_t ncs_dir_hits;     /* dir cache hits */
 137         kstat_named_t ncs_dir_misses;   /* dir cache misses */
 138         kstat_named_t ncs_cur_dirs;     /* current # directories cached */
 139         kstat_named_t ncs_dir_num_ents; /* current # entries cached */
 140         kstat_named_t ncs_dirs_cached;  /* total # directories cached */
 141         kstat_named_t ncs_dir_start_nm; /* dir start no memory */
 142         kstat_named_t ncs_dir_add_nm;   /* add entry/space - no memory */
 143         kstat_named_t ncs_dir_addabort; /* add entry/space - abort */
 144         kstat_named_t ncs_dir_add_max;  /* add entry/space - max exceeded */
 145         kstat_named_t ncs_dir_reme_fai; /* remove entry fail */
 146         kstat_named_t ncs_dir_rems_fai; /* remove space fail */
 147         kstat_named_t ncs_dir_upd_fail; /* update space fail */
 148         kstat_named_t ncs_dir_finipurg; /* fini purges */
 149         kstat_named_t ncs_dir_rec_last; /* reclaim last */
 150         kstat_named_t ncs_dir_recl_any; /* reclaim any */
 151 };
 152
 153 /*
 154  * The dnlc hashing function.
 155  * Although really a kernel macro we export it to allow validation
 156  * of ncache_t entries by mdb. Note, mdb can handle the ASSERT.
 157  *
 158  * 'hash' and 'namlen' must be l-values. A check is made to ensure
 159  * the name length fits into an unsigned char (see ncache_t).
 160  */
 161 #define DNLCHASH(name, dvp, hash, namlen)                       \
 162         {                                                       \
 163                 char Xc;                                        \
 164                 const char *Xcp;                                \
 165                 hash = (int)((uintptr_t)(dvp)) >> 8;            \
 166                 for (Xcp = (name); (Xc = *Xcp) != 0; Xcp++)     \
 167                         (hash) = ((hash) << 4) + (hash) + Xc;   \
 168                 ASSERT((Xcp - (name)) <= ((1 << NBBY) - 1));    \
 169                 (namlen) = Xcp - (name);                        \
 170         }
 171
 172 #if defined(_KERNEL)
 173
 174 #include <sys/vfs.h>
 175 #include <sys/vnode.h>
 176
 177 extern int ncsize;              /* set in param_init() # of dnlc entries */
 178 extern vnode_t negative_cache_vnode;
 179 #define DNLC_NO_VNODE &negative_cache_vnode
 180
 181 void    dnlc_init(void);
 182 void    dnlc_enter(vnode_t *, const char *, vnode_t *);
 183 void    dnlc_update(vnode_t *, const char *, vnode_t *);
 184 vnode_t *dnlc_lookup(vnode_t *, const char *);
 185 void    dnlc_purge(void);
 186 void    dnlc_purge_vp(vnode_t *);
 187 int     dnlc_purge_vfsp(vfs_t *, int);
 188 void    dnlc_remove(vnode_t *, const char *);
 189 int     dnlc_fs_purge1(struct vnodeops *);
 190 void    dnlc_reduce_cache(void *);
 191
 192 #endif  /* defined(_KERNEL) */
 193
 194
 195 /*
 196  * Directory caching interfaces
 197  * ============================
 198  */
 199
 200 /*
 201  * Typically for large directories, the file names will be the same or
 202  * at least similar lengths. So there's no point in anything more elaborate
 203  * than a simple unordered linked list of free space entries.
 204  * For small directories the name length distribution doesn't really matter.
 205  */
 206 typedef struct dcfree {
 207         uint64_t df_handle;             /* fs supplied handle */
 208         struct dcfree *df_next;         /* link to next free entry in bucket */
 209         uint_t df_len;                  /* length of free entry */
 210 } dcfree_t;
 211
 212 typedef struct dcentry {
 213         uint64_t de_handle;             /* fs supplied and returned data */
 214         struct dcentry *de_next;        /* link to next name entry in bucket */
 215         int de_hash;                    /* hash signature */
 216         uchar_t de_namelen;             /* length of name excluding null */
 217         char de_name[1];                /* null terminated name */
 218 } dcentry_t;
 219
 220 typedef struct dircache {
 221         struct dircache *dc_next;       /* chain - for purge purposes */
 222         struct dircache *dc_prev;       /* chain - for purge purposes */
 223         int64_t dc_actime;              /* dir access time, from lbolt64 */
 224         dcentry_t **dc_namehash;        /* entry hash table pointer */
 225         dcfree_t **dc_freehash;         /* free entry hash table pointer */
 226         uint_t dc_num_entries;          /* no of named entries */
 227         uint_t dc_num_free;             /* no of free space entries */
 228         uint_t dc_nhash_mask;           /* name hash table size - 1 */
 229         uint_t dc_fhash_mask;           /* free space hash table size - 1 */
 230         struct dcanchor *dc_anchor;     /* back ptr to anchor */
 231         boolean_t dc_complete;          /* cache complete boolean */
 232 } dircache_t;
 233
 234 typedef struct dcanchor {
 235         void *dca_dircache;     /* pointer to directory cache */
 236         kmutex_t dca_lock;              /* protects the directory cache */
 237 } dcanchor_t;
 238
 239 /*
 240  * Head struct for doubly linked chain of dircache_t
 241  * The next and prev fields must match those of a dircache_t
 242  */
 243 typedef struct {
 244         dircache_t *dch_next;           /* next in chain */
 245         dircache_t *dch_prev;           /* prev in chain */
 246         kmutex_t dch_lock;              /* lock for the chain */
 247 } dchead_t;
 248
 249
 250 #if defined(_KERNEL)
 251
 252 /*
 253  * Status returns from the directory cache interfaces
 254  */
 255 typedef enum {
 256         DOK,            /* operation sucessful */
 257         DNOCACHE,       /* there is no cache */
 258         DFOUND,         /* entry found */
 259         DNOENT,         /* no entry found */
 260         DTOOBIG,        /* exceeds tunable dnlc_max_dir_cache */
 261         DNOMEM          /* no memory */
 262 } dcret_t;
 263
 264 /*
 265  * dnlc_dir_start() requests that a directory be cached.
 266  * This must be called initially to enable caching on a directory.
 267  * After a successful call, directory entries and free space can be
 268  * added (see below) until the directory is marked complete.
 269  * "num_entries" is an estimate of the current number of
 270  * directory entries. The request is rejected with DNOCACHE
 271  * if num_entries falls below the tunable dnlc_dir_min_size (see
 272  * below), and rejected with DTOOBIG if it's above dnlc_dir_max_size.
 273  * Returns DOK, DNOCACHE, DTOOBIG, DNOMEM.
 274  *
 275  * Due to memory shortages, directory caches can be purged at
 276  * any time. If the last directory cache is purged due to memory
 277  * shortage, then the directory cache is marked internally
 278  * as "no memory". Future returns will all be DNOCACHE until
 279  * the next dnlc_start_dir() which will return DNOMEM once.
 280  * This memory shortage may only be transient. It's up to the
 281  * file system as to what to do about this condition, but an
 282  * attempt to immediately re-build the cache will very likely
 283  * lead to the same shortage of memory and a thrashing situation.
 284  *
 285  * It's file system policy as to when and what size directories to cache.
 286  */
 287 dcret_t dnlc_dir_start(dcanchor_t *dcap, uint_t num_entries);
 288
 289 /*
 290  * dnlc_dir_add_entry() adds an entry (name and handle) into a
 291  * partial or complete cache. "handle" is a file system specific
 292  * quantity that is returned on calls to dnlc_dir_lookup() - see below.
 293  * For example, "handle" for ufs holds the inumber and a directory
 294  * entry offset. Returns DOK, DNOCACHE, DTOOBIG.
 295  */
 296 dcret_t dnlc_dir_add_entry(dcanchor_t *dcap, const char *name, uint64_t handle);
 297
 298 /*
 299  * dnlc_dir_add_space adds free space (length and file system specific
 300  * handle) into a partial or complete cache. "handle" is a file
 301  * system specific quantity that is returned on calls to
 302  * dnlc_dir_rem_space_by_len(). For example, "handle" for ufs holds
 303  * the directory entry offset.  Returns DOK, DNOCACHE, DTOOBIG.
 304  */
 305 dcret_t dnlc_dir_add_space(dcanchor_t *dcap, uint_t len, uint64_t handle);
 306
 307 /*
 308  * dnlc_dir_complete() indicates the previously partial cache is now complete.
 309  */
 310 void dnlc_dir_complete(dcanchor_t *dcap);
 311
 312 /*
 313  * dnlc_dir_purge() deletes a partial or complete directory cache
 314  */
 315 void dnlc_dir_purge(dcanchor_t *dcap);
 316
 317 /*
 318  * dnlc_dir_lookup() lookups a file name in a directory cache
 319  * and returns the file system handle specified on dnlc_dir_add_entry()
 320  * in "handlep". Returns DFOUND, DNOENT, DNOCACHE.
 321  */
 322 dcret_t dnlc_dir_lookup(dcanchor_t *dcap, const char *name, uint64_t *handlep);
 323
 324 /*
 325  * dnlc_dir_update() amends the handle for an entry in a directory cache
 326  * "handle" is the new file system specific handle for the file "name".
 327  * Returns DFOUND, DNOENT, DNOCACHE.
 328  */
 329 dcret_t dnlc_dir_update(dcanchor_t *dcap, const char *name, uint64_t handle);
 330
 331 /*
 332  * dnlc_dir_rem_entry() removes an entry form a directory cache.
 333  * Returns the handle if "handlep" non null.
 334  * Returns DFOUND, DNOENT, DNOCACHE.
 335  */
 336 dcret_t dnlc_dir_rem_entry(dcanchor_t *dcap, const char *name,
 337     uint64_t *handlep);
 338
 339 /*
 340  * dnlc_dir_rem_space_by_len() looks up and returns free space in a
 341  * directory cache of at least the given "len". Returns in "handlep"
 342  * the handle supplied when adding the free space in dnlc_dir_add_space().
 343  * Returns DFOUND, DNOENT, DNOCACHE.
 344  */
 345 dcret_t dnlc_dir_rem_space_by_len(dcanchor_t *dcap, uint_t len,
 346     uint64_t *handlep);
 347
 348 /*
 349  * dnlc_dir_rem_space_by_handle() looks up and removes the free space in
 350  * a directory cache with the given handle. Returns DFOUND, DNOENT, DNOCACHE.
 351  */
 352 dcret_t dnlc_dir_rem_space_by_handle(dcanchor_t *dcap, uint64_t handle);
 353
 354 /*
 355  * dnlc_dir_init() initialises a directory anchor
 356  */
 357 #define dnlc_dir_init(dcap) { \
 358         (dcap)->dca_dircache = NULL; \
 359         mutex_init(&(dcap)->dca_lock, NULL, MUTEX_DEFAULT, NULL); }
 360
 361 /*
 362  * dnlc_dir_fini() is called to indicate the anchor is no longer used.
 363  * It ensures there's no directory cache and mutex_destroys the lock
 364  */
 365 void dnlc_dir_fini(dcanchor_t *dcap);
 366
 367 #endif  /* defined(_KERNEL) */
 368
 369 #ifdef  __cplusplus
 370 }
 371 #endif
 372
 373 #endif  /* _SYS_DNLC_H */