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[];                    /* segment name */
  86 } ncache_t;
  87
  88 /*
  89  * Produce size of struct ncache with space allocated in name string.
  90  */
  91 #define NCACHE_SIZE(namelen)    offsetof(ncache_t, name) + (namelen)
  92
  93 /*
  94  * Hash table bucket structure of name cache entries for fast lookup.
  95  */
  96 typedef struct nc_hash  {
  97         ncache_t *hash_next;
  98         ncache_t *hash_prev;
  99         kmutex_t hash_lock;
 100 } nc_hash_t;
 101
 102 /*
 103  * Statistics on name cache
 104  * Not protected by locks
 105  */
 106 /*
 107  * ncstats has been deprecated, due to the integer size of the counters
 108  * which can easily overflow in the dnlc.
 109  * It is maintained (at some expense) for compatability.
 110  * The preferred interface is the kstat accessible nc_stats below, ehich
 111  * is actually shared with directory caching.
 112  */
 113 struct ncstats {
 114         int     hits;           /* hits that we can really use */
 115         int     misses;         /* cache misses */
 116         int     enters;         /* number of enters done */
 117         int     dbl_enters;     /* number of enters tried when already cached */
 118         int     long_enter;     /* deprecated, no longer accounted */
 119         int     long_look;      /* deprecated, no longer accounted */
 120         int     move_to_front;  /* entry moved to front of hash chain */
 121         int     purges;         /* number of purges of cache */
 122 };
 123
 124 struct nc_stats {
 125         kstat_named_t ncs_hits;         /* cache hits */
 126         kstat_named_t ncs_misses;       /* cache misses */
 127         kstat_named_t ncs_neg_hits;     /* negative cache hits */
 128         kstat_named_t ncs_enters;       /* enters */
 129         kstat_named_t ncs_dbl_enters;   /* enters when entry already cached */
 130         kstat_named_t ncs_purge_total;  /* total entries prurged */
 131         kstat_named_t ncs_purge_all;    /* dnlc_purge() calls */
 132         kstat_named_t ncs_purge_vp;     /* dnlc_purge_vp() calls */
 133         kstat_named_t ncs_purge_vfs;    /* dnlc_purge_vfs() calls */
 134         kstat_named_t ncs_purge_fs1;    /* dnlc_purge_fs1() calls */
 135         kstat_named_t ncs_pick_free;    /* found a free ncache */
 136         kstat_named_t ncs_pick_heur;    /* found ncache w/ NULL vpages */
 137         kstat_named_t ncs_pick_last;    /* found last ncache on chain */
 138
 139         /* directory caching stats */
 140
 141         kstat_named_t ncs_dir_hits;     /* dir cache hits */
 142         kstat_named_t ncs_dir_misses;   /* dir cache misses */
 143         kstat_named_t ncs_cur_dirs;     /* current # directories cached */
 144         kstat_named_t ncs_dir_num_ents; /* current # entries cached */
 145         kstat_named_t ncs_dirs_cached;  /* total # directories cached */
 146         kstat_named_t ncs_dir_start_nm; /* dir start no memory */
 147         kstat_named_t ncs_dir_add_nm;   /* add entry/space - no memory */
 148         kstat_named_t ncs_dir_addabort; /* add entry/space - abort */
 149         kstat_named_t ncs_dir_add_max;  /* add entry/space - max exceeded */
 150         kstat_named_t ncs_dir_reme_fai; /* remove entry fail */
 151         kstat_named_t ncs_dir_rems_fai; /* remove space fail */
 152         kstat_named_t ncs_dir_upd_fail; /* update space fail */
 153         kstat_named_t ncs_dir_finipurg; /* fini purges */
 154         kstat_named_t ncs_dir_rec_last; /* reclaim last */
 155         kstat_named_t ncs_dir_recl_any; /* reclaim any */
 156 };
 157
 158 /*
 159  * The dnlc hashing function.
 160  * Although really a kernel macro we export it to allow validation
 161  * of ncache_t entries by mdb. Note, mdb can handle the ASSERT.
 162  *
 163  * 'hash' and 'namlen' must be l-values. A check is made to ensure
 164  * the name length fits into an unsigned char (see ncache_t).
 165  */
 166 #define DNLCHASH(name, dvp, hash, namlen)                       \
 167         {                                                       \
 168                 char Xc;                                        \
 169                 const char *Xcp;                                \
 170                 hash = (int)((uintptr_t)(dvp)) >> 8;            \
 171                 for (Xcp = (name); (Xc = *Xcp) != 0; Xcp++)     \
 172                         (hash) = ((hash) << 4) + (hash) + Xc;   \
 173                 ASSERT((Xcp - (name)) <= ((1 << NBBY) - 1));    \
 174                 (namlen) = Xcp - (name);                        \
 175         }
 176
 177 #if defined(_KERNEL) || defined(_FAKE_KERNEL)
 178
 179 #include <sys/vfs.h>
 180 #include <sys/vnode.h>
 181
 182 extern int ncsize;              /* set in param_init() # of dnlc entries */
 183 extern vnode_t negative_cache_vnode;
 184 #define DNLC_NO_VNODE &negative_cache_vnode
 185
 186 void    dnlc_init(void);
 187 void    dnlc_enter(vnode_t *, const char *, vnode_t *);
 188 void    dnlc_update(vnode_t *, const char *, vnode_t *);
 189 vnode_t *dnlc_lookup(vnode_t *, const char *);
 190 void    dnlc_purge(void);
 191 void    dnlc_purge_vp(vnode_t *);
 192 int     dnlc_purge_vfsp(vfs_t *, int);
 193 void    dnlc_remove(vnode_t *, const char *);
 194 int     dnlc_fs_purge1(struct vnodeops *);
 195 void    dnlc_reduce_cache(void *);
 196
 197 #endif  /* defined(_KERNEL) */
 198
 199
 200 /*
 201  * Directory caching interfaces
 202  * ============================
 203  */
 204
 205 /*
 206  * Typically for large directories, the file names will be the same or
 207  * at least similar lengths. So there's no point in anything more elaborate
 208  * than a simple unordered linked list of free space entries.
 209  * For small directories the name length distribution doesn't really matter.
 210  */
 211 typedef struct dcfree {
 212         uint64_t df_handle;             /* fs supplied handle */
 213         struct dcfree *df_next;         /* link to next free entry in bucket */
 214         uint_t df_len;                  /* length of free entry */
 215 } dcfree_t;
 216
 217 typedef struct dcentry {
 218         uint64_t de_handle;             /* fs supplied and returned data */
 219         struct dcentry *de_next;        /* link to next name entry in bucket */
 220         int de_hash;                    /* hash signature */
 221         uchar_t de_namelen;             /* length of name excluding null */
 222         char de_name[];                 /* name */
 223 } dcentry_t;
 224
 225 /*
 226  * Produce size of struct dcentry with space allocated in name string.
 227  */
 228 #define DCENTTRY_SIZE(namelen)  offsetof(dcentry_t, de_name) + (namelen)
 229
 230 typedef struct dircache {
 231         struct dircache *dc_next;       /* chain - for purge purposes */
 232         struct dircache *dc_prev;       /* chain - for purge purposes */
 233         int64_t dc_actime;              /* dir access time, from lbolt64 */
 234         dcentry_t **dc_namehash;        /* entry hash table pointer */
 235         dcfree_t **dc_freehash;         /* free entry hash table pointer */
 236         uint_t dc_num_entries;          /* no of named entries */
 237         uint_t dc_num_free;             /* no of free space entries */
 238         uint_t dc_nhash_mask;           /* name hash table size - 1 */
 239         uint_t dc_fhash_mask;           /* free space hash table size - 1 */
 240         struct dcanchor *dc_anchor;     /* back ptr to anchor */
 241         boolean_t dc_complete;          /* cache complete boolean */
 242 } dircache_t;
 243
 244 typedef struct dcanchor {
 245         void *dca_dircache;     /* pointer to directory cache */
 246         kmutex_t dca_lock;              /* protects the directory cache */
 247 } dcanchor_t;
 248
 249 /*
 250  * Head struct for doubly linked chain of dircache_t
 251  * The next and prev fields must match those of a dircache_t
 252  */
 253 typedef struct {
 254         dircache_t *dch_next;           /* next in chain */
 255         dircache_t *dch_prev;           /* prev in chain */
 256         kmutex_t dch_lock;              /* lock for the chain */
 257 } dchead_t;
 258
 259
 260 #if defined(_KERNEL)
 261
 262 /*
 263  * Status returns from the directory cache interfaces
 264  */
 265 typedef enum {
 266         DOK,            /* operation sucessful */
 267         DNOCACHE,       /* there is no cache */
 268         DFOUND,         /* entry found */
 269         DNOENT,         /* no entry found */
 270         DTOOBIG,        /* exceeds tunable dnlc_max_dir_cache */
 271         DNOMEM          /* no memory */
 272 } dcret_t;
 273
 274 /*
 275  * dnlc_dir_start() requests that a directory be cached.
 276  * This must be called initially to enable caching on a directory.
 277  * After a successful call, directory entries and free space can be
 278  * added (see below) until the directory is marked complete.
 279  * "num_entries" is an estimate of the current number of
 280  * directory entries. The request is rejected with DNOCACHE
 281  * if num_entries falls below the tunable dnlc_dir_min_size (see
 282  * below), and rejected with DTOOBIG if it's above dnlc_dir_max_size.
 283  * Returns DOK, DNOCACHE, DTOOBIG, DNOMEM.
 284  *
 285  * Due to memory shortages, directory caches can be purged at
 286  * any time. If the last directory cache is purged due to memory
 287  * shortage, then the directory cache is marked internally
 288  * as "no memory". Future returns will all be DNOCACHE until
 289  * the next dnlc_start_dir() which will return DNOMEM once.
 290  * This memory shortage may only be transient. It's up to the
 291  * file system as to what to do about this condition, but an
 292  * attempt to immediately re-build the cache will very likely
 293  * lead to the same shortage of memory and a thrashing situation.
 294  *
 295  * It's file system policy as to when and what size directories to cache.
 296  */
 297 dcret_t dnlc_dir_start(dcanchor_t *dcap, uint_t num_entries);
 298
 299 /*
 300  * dnlc_dir_add_entry() adds an entry (name and handle) into a
 301  * partial or complete cache. "handle" is a file system specific
 302  * quantity that is returned on calls to dnlc_dir_lookup() - see below.
 303  * For example, "handle" for ufs holds the inumber and a directory
 304  * entry offset. Returns DOK, DNOCACHE, DTOOBIG.
 305  */
 306 dcret_t dnlc_dir_add_entry(dcanchor_t *dcap, const char *name, uint64_t handle);
 307
 308 /*
 309  * dnlc_dir_add_space adds free space (length and file system specific
 310  * handle) into a partial or complete cache. "handle" is a file
 311  * system specific quantity that is returned on calls to
 312  * dnlc_dir_rem_space_by_len(). For example, "handle" for ufs holds
 313  * the directory entry offset.  Returns DOK, DNOCACHE, DTOOBIG.
 314  */
 315 dcret_t dnlc_dir_add_space(dcanchor_t *dcap, uint_t len, uint64_t handle);
 316
 317 /*
 318  * dnlc_dir_complete() indicates the previously partial cache is now complete.
 319  */
 320 void dnlc_dir_complete(dcanchor_t *dcap);
 321
 322 /*
 323  * dnlc_dir_purge() deletes a partial or complete directory cache
 324  */
 325 void dnlc_dir_purge(dcanchor_t *dcap);
 326
 327 /*
 328  * dnlc_dir_lookup() lookups a file name in a directory cache
 329  * and returns the file system handle specified on dnlc_dir_add_entry()
 330  * in "handlep". Returns DFOUND, DNOENT, DNOCACHE.
 331  */
 332 dcret_t dnlc_dir_lookup(dcanchor_t *dcap, const char *name, uint64_t *handlep);
 333
 334 /*
 335  * dnlc_dir_update() amends the handle for an entry in a directory cache
 336  * "handle" is the new file system specific handle for the file "name".
 337  * Returns DFOUND, DNOENT, DNOCACHE.
 338  */
 339 dcret_t dnlc_dir_update(dcanchor_t *dcap, const char *name, uint64_t handle);
 340
 341 /*
 342  * dnlc_dir_rem_entry() removes an entry form a directory cache.
 343  * Returns the handle if "handlep" non null.
 344  * Returns DFOUND, DNOENT, DNOCACHE.
 345  */
 346 dcret_t dnlc_dir_rem_entry(dcanchor_t *dcap, const char *name,
 347     uint64_t *handlep);
 348
 349 /*
 350  * dnlc_dir_rem_space_by_len() looks up and returns free space in a
 351  * directory cache of at least the given "len". Returns in "handlep"
 352  * the handle supplied when adding the free space in dnlc_dir_add_space().
 353  * Returns DFOUND, DNOENT, DNOCACHE.
 354  */
 355 dcret_t dnlc_dir_rem_space_by_len(dcanchor_t *dcap, uint_t len,
 356     uint64_t *handlep);
 357
 358 /*
 359  * dnlc_dir_rem_space_by_handle() looks up and removes the free space in
 360  * a directory cache with the given handle. Returns DFOUND, DNOENT, DNOCACHE.
 361  */
 362 dcret_t dnlc_dir_rem_space_by_handle(dcanchor_t *dcap, uint64_t handle);
 363
 364 /*
 365  * dnlc_dir_init() initialises a directory anchor
 366  */
 367 #define dnlc_dir_init(dcap) { \
 368         (dcap)->dca_dircache = NULL; \
 369         mutex_init(&(dcap)->dca_lock, NULL, MUTEX_DEFAULT, NULL); }
 370
 371 /*
 372  * dnlc_dir_fini() is called to indicate the anchor is no longer used.
 373  * It ensures there's no directory cache and mutex_destroys the lock
 374  */
 375 void dnlc_dir_fini(dcanchor_t *dcap);
 376
 377 #endif  /* defined(_KERNEL) */
 378
 379 #ifdef  __cplusplus
 380 }
 381 #endif
 382
 383 #endif  /* _SYS_DNLC_H */